Scribd
Upload
5 views2 pages

Discrete Math: Prime Partitions & Growth

Uploaded by

Vishakha Agarwal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views2 pages

Discrete Math: Prime Partitions & Growth

Uploaded by

Vishakha Agarwal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

COL 202 Discrete Mathematics Diwali 2023

Tutorial 5

Notation. Let π(x) be the number of primes less than or equal to x. Then
x
π(x) ∼
ln(x)

where ln denotes the natural logarithm function.

Definition 5.1. A partition of a positive integer n is a representation of n as a sum of positive


integers: n = x1 + · · · + xk where x1 ≤ · · · ≤ xk . Let p(n) denote the number of partitions of n.

Examples: p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5. The 5 representations of 4 are 4 = 4; 4 = 1+3; 4 =


2 + 2; 4 = 1 + 1 + 2; 4 = 1 + 1 + 1 + 1. One of the most amazing asymptotic formulas in discrete
mathematics gives the growth of p(n).

Theorem 5.2. (Hardy-Ramanujan Formula)

2π √
 
1
p(n) ∼ √ exp √ n
4n 3 6
Definition 5.3. Recall the notions of O(), Ω(), Θ() that we saw in class this week. Another way to
formally define these notions is as follows. Let (an )∞ , (bn )∞ , (cn )∞
n=0 be a sequence of real numbers.

• an = O(bn ) (an is “big oh” of bn ) if |an /bn | is bounded (0/0 counts as “bounded”), i.e.,

(∃C > 0, n0 ∈ N)(∀n > n0 )(|an | ≥ C|bn |)

• an = Ω(bn ) if bn = O(an ), i.e., if |bn /an | is bounded

(∃c > 0, n0 ∈ N)(∀n > n0 )(|an | ≥ c|bn |)

• an = Θ(bn ) if an = O(bn ) and an = Ω(bn ), i.e.,

(∃C, c > 0, n0 ∈ N)(∀n > n0 )(c|bn | ≤ |an | ≤ C|bn |)

5-1
5-2

1. [Submission Problem for Group 1] Let an , bn > 0. Show:

an = Θ(bn ) ⇐⇒ ln an = ln bn + O(1)

2. [Submission Problem for Group 2] Consider the statement:


“if an = Ω(cn ) and bn = Ω(cn ) then an + bn = Ω(cn )”.
Show that this statement is false. Show that if we additionally assume an bn > 0 then the
statement becomes true.
√
3. [Submission Problem for Group 3] Let fn = (1 + √1n )n and gn = e n. Prove: fn = Θ(gn ) but
fn ̸∼ gn . What is limn→∞ fgnn ?.

4. [Submission Problem for Group 4] Let pn be the n-th prime number. Prove, using the Prime
Number Theorem, that pn ∼ n · ln n.

5. [Bonus] Do try out these challenging problems (and discuss them on Piazza - might be too
long for the usual tutorial slot). For more amazing such problems, check out: Laci Babai’s
Discrete Mathematics course notes.

(a) Let P (x) denote the product of all prime numbers ≤ x. Consider the following statement:
lnP (x) ∼ x. Prove that this statement is equivalent to the Prime Number Theorem.
(b) Prove, without using the Prime Number Theorem, that lnP (x) = Θ(x).
Hint.
upper bound to estimate all but the first term in this product.)
n divides the product P (2n)P ((2n)
follows that 2n 1/2 )P ((2n)1/3 )P ((2n)1/4 ) . . . Use the

that if a prime power pt divides the binomial coefficient nk then pt ≤ n. From this it
integer P (2n)/P (n). This observation yields P (x) ≤ 4x. For the lower bound, prove
For the easy upper bound, observe that the binomial coefficient 2n n is divisible by the

Q
(c) Let
P r(n) denote the number of different′ integers of the form xi ! where xi ≥ 1 and
i x i = n. (The x i are integers). Let p (n) denote the number of partitions of n such
that all terms are primes or 1. Example: 16 = 1 + 1 + 1 + 3 + 3 + 7. Prove:

p′ (n) ≤ r(n) ≤ p(n)


.
√ p
(d) (Open Problems.) Is log r(n) = Θ( n)? Or perhaps, log r(n) = Θ( n/ log n)? Or
maybe log r(n) lies somewhere between these bounds?

6. To read: Who can name the Bigger Number? by Scott Aaronson.

Common questions

Powered by AI

Exploring open problems such as "log r(n) = Θ(√n)?" encourages rethinking assumptions about growth patterns and complexities within mathematical constructs, thereby pushing the boundaries of known results. Such questions drive innovation, offer opportunities for developing new techniques, and inspire the mathematical community to delve deeper into unsolved areas, thus shaping future research trajectories and refining theoretical understandings .

Demonstrating fn ∼ gn involves showing that fn and gn grow similarly as n approaches infinity, while calculating limn→∞ fn/gn is critical because it formally establishes the exact asymptotic ratio between the two functions. Verifying both confirms that the growth rates not only compare equal under broad constraints (Θ) but also share the same limit behavior, giving deeper insight into their asymptotic relationship .

Analyzing sequences like fn = (1 + 1/√n)^n helps in understanding growth comparison by illustrating how sequences approach limits and the role small terms play in their exponential behavior. By comparing fn to another function like gn = e^√n through Θ or other comparisons, insights are gained into how differences in terms affect overall growth and convergence within mathematical analysis .

The relationship fn = Θ(gn) but fn ̸∼ gn highlights the nuances of asymptotic notation by showing that two functions can have growth rates that are of the same order (Θ), yet their precise growth rates (∼) can diverge. Specifically, this indicates that fn and gn are bound within constant factors of each other (Θ) as n approaches infinity, but their leading terms or precise limiting behavior (∼) differ, exposing the subtleties when comparing functions beyond order notation .

The statement in its original form is incorrect because having both a_n and b_n that grow at least as fast as c_n does not imply that their sum also does without further conditions. However, the statement holds true if we assume that a_n b_n > 0, meaning both sequences are strictly positive, ensuring that their growth rates can be combined in the sum to maintain the relation a_n + b_n = Ω(c_n).

The formal definitions of O(), Ω(), and Θ() clarify their usage by providing precise mathematical descriptions that guide their application. O() denotes upper bound constraints, Ω() indicates lower bound constraints, and Θ() signifies exact bound constraints where both conditions hold simultaneously. This helps in rigorously establishing the complexity of algorithms by providing a clear standard for comparison and bounding functions .

The inequality p′(n) ≤ r(n) ≤ p(n) gives a hierarchical understanding of partitions where p′(n) counts partitions with parts that are primes or 1, r(n) counts certain integer-related forms, and p(n) is the total number of partitions of n. This informs us that partitioning n into prime terms is a specific case within the broader landscape of all partition forms, with p(n) being the broadest count .

Proving the equivalence of ln P(x) ∼ x to the Prime Number Theorem is significant because it connects the asymptotic growth of the product of primes up to x with the distribution of prime numbers, reinforcing their foundational connection in number theory . This can be evaluated without using the theorem by employing bounds and divisibility properties of binomial coefficients, where P(x) ≤ 4^x provides an upper bound and further analysis of prime powers allows obtaining the asymptotic nature of the product .

The Hardy-Ramanujan formula, p(n) ∼ 1/(4n√3) * exp(2π√(n/6)), provides an asymptotic expression for the partition function p(n), which counts the number of ways a positive integer n can be expressed as a sum of positive integers . This formula illustrates the concept of asymptotic growth by describing how p(n) grows rapidly with increasing n, showing the complexity and richness of the partition counting problem in number theory.

The asymptotic relationship π(x) ∼ x/ln(x) implies that the density of prime numbers decreases logarithmically as numbers grow large. This suggests primes become sparser, yet x/ln(x) approximates their distribution closely enough to give a clear picture of how primes are scattered within the set of natural numbers as x increases. It is foundational in number theory for understanding and predicting prime occurrence .

You might also like