18.317 Combinatorics, Probability, and Computations on Groups 19 September 2001

Lecture 5

Lecturer: Igor Pak Scribe: Dennis Clark

Proof of a Lemma

Our plan here is to prove the following lemma, needed in the fixed proof of Erdős-Turan’s theorem: Lemma 1 Suppose A = {1 ≤ a_{1} < a_{2} < ⋯ < a_{r} ≤ n}. Then:

P r(σ ∈ S_{n}has no cycles in A) < \frac{1}{∑_{i=1}^{r} a_{i}}  (1)

But we’ll need a few sublemmas first. Sublemma 2

E(# of l-cycles in σ ∈ S_{n}) = \frac{1}{l}  (2)

Proof:

E = \binom{n}{l}\frac{(l − 1)!(n − l)!}{n!} = \frac{1}{l}  (3)

Sublemma 3 Assume l ≠ m, and l + m ≤ n. Then:

E(# of l-cycles · # of m-cycles in σ ∈ S_{n}) = \frac{1}{l m}  (4)

Proof: First, we take the sum in the first equation over the number of ways to split n into an l-subset, and m-subset, and an n − m − l subset.

E = ∑ P r(cycle at l-subset and cycle at m-subset)  (5)

Then, recognize that all of the probabilities will be symmetric, so we can just multiply appropriately:

E = \binom{n}{l, m, n − l − m} · \frac{(l − 1)!(m − 1)!(n − m − l)!}{n!}  (6)
= \frac{n!(l − 1)!(m − 1)!(n − m − l)!}{l!m!(n − m − l)!n!}  (7)
= \frac{1}{lm}  (8)

As a corollary, we get:

Corollary 4

E(# of cycles in σ) = 1 + \frac{1}{2} + ⋯ + \frac{1}{n} ≈ log n + γ + O(\frac{1}{n})  (9)

where γ is a constant. Proof:

E = ∑_{l} E(# of l-cycles) = ∑ \frac{1}{l}  (10)

Another sublemma, here departing from Erdős-Turan: Sublemma 5

E((# of l-cycles)^{2}) = \{ \begin{matrix}\frac{1}{l} & if 2l > n \\ \frac{1}{l} + \frac{1}{l^{2}} & if 2l ≤ n \end{matrix}  (11)

Proof: To start, observe that

E(# of l-cycles) = \frac{1}{l} ∑_{i=1}^{n} P r(i ∈ l-cycle) = \frac{1}{l}  (12)

from the proof of Sublemma 2. This gives: Corollary 6 P r(i ∈ l-cycle) = \frac{1}{n}. Therefore the total number of cycles is approimately log n. Similarly, Erdős-Turan obtain

log(∏ cycle length) ≈ \frac{1}{2} log^{2} n  (13)

So then we can observe that the square of the number of l-cycles is precisely the number of ordered pairs of elements belonging to l-cycles divided by l^{2}, which yields:

E = \frac{1}{l^{2}} ∑_{i=1}^{n} ∑_{ij1}^{n} P r(i ∈ l-cycle andj ∈ l-cycle)  (14)
= \frac{1}{l^{2}} (∑_{i=1}^{n} P r(i ∈ l-cycle) + ∑_{i≠j}^{n} P r(i ∈ l-cycle)P r(j ∈ l-cycle|i ∈ l-cycle))  (15)

We consider the sums one at a time. First, the first sum is equal to:

\frac{1}{l^{2}} · n · \frac{1}{n} = \frac{1}{l^{2}}  (16)

from Corollary 6. Let us consider now the second sum, which is equal to

\frac{1}{l^{2}} · n · \frac{1}{n} · (n − 1) (\frac{l − 1}{n − 1} + \frac{n − l}{n − 1} · \frac{1}{n − l} )  (17)

The justification for the fractions inside the parentheses is as follows: consider that the element i is already in an l-cycle. We want the probability that j is in an l-cycle. First, the probability that j is in the same l-cycle as i is simply \frac{l−1}{n−1}, since j can be in any of n − 1 places, l − 1 of which are what we’re looking for. The second summand is the probability that j is among the remaining points but is in an l-cycle anyway, which can only happen if l + l ≤ n. So we get the following:

E((# of l-cycles)^{2}) = \{ \begin{matrix}\frac{1}{l^{2}} + \frac{1}{l^{2}} · (l − 1) & if 2l > n \\ \frac{1}{l^{2}} + \frac{1}{l^{2}} · l & if 2l ≤ n \end{matrix}  (18)

Which then gives us:

E = \{ \begin{matrix}\frac{1}{l} & if 2l > n \\ \frac{1}{l} + \frac{1}{l^{2}} & if 2l ≤ n \end{matrix}  (19)

as needed.

Then, we return at last to the proof of Lemma 1:

Proof:

We first estimate the expected value of the number of A-cycles:

E(# of A-cycles) = ∑_{i=1}^{r} E(# of a_{i}-cycles) = ∑_{i=1}^{r} \frac{1}{a_{i}}  (20)

This gives:

E((# of A-cycles)^{2}) = ∑_{i≠j}^{r} E(#a_{i}-cycles · #a_{j}cycles) + ∑_{i=1}^{r} E((#a_{i}-cycles)^{2})  (21)

Applying the two main sublemmas to the two sums yields:

≤ 2 ∑_{1≤i<j≤r} \frac{1}{a_{i}a_{j}} + ∑_{i} (\frac{1}{a_{i}^{2}} + \frac{1}{a_{i}} ) = ∑_{i} \frac{1}{a_{i}} + (∑_{i} \frac{1}{a_{i}} )^{2}  (22)

Now, let X be a random variable describing the number of A-cycles. We have

V ar(# of A-cycles) = V ar(X) = E(X^{2}) − (E(X))^{2}  (23)
= (∑_{i} \frac{1}{a_{i}} + (∑_{i} \frac{1}{a_{i}} )^{2}) − (∑_{i} \frac{1}{a_{i}} )^{2} = ∑_{i} \frac{1}{a_{i}}  (24)

From here and Chebyshev inequality we get the following:

P r(X = 0) = P r(X + E(X) ≤ E(X))  (25)
≤ \frac{V ar(X)}{(E(X)^{2})}  (26)

≤ \frac{∑ \frac{1}{a_{i}}}{(∑ \frac{1}{a_{i}})^{2}}  (27)

≤ (∑_{i} \frac{1}{a_{i}} )^{−1}  (28)

Lecture 5: 19 September 2001 4 which proves the lemma.