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.
