Erdős–Turán statistical group theory

What is Erdős–Turán “statistical group theory”? Erdős and Turán published a series of seven papers with this title, from 1965 to 1972, in which they proved many beautiful statistical or counting results about permutations. For example, if ${|\sigma|}$ denotes the order of a permutation ${\sigma\in S_n}$ , they showed that when ${\sigma}$ is chosen uniformly at random ${\log|\sigma|}$ is approximately normally distributed, with mean ${(\log n)^2/2}$ and variance ${(\log n)^3/3}$ . Another typical result, though much simpler, is that if ${A}$ is any subset of ${\{1,\dots,n\}}$ , then the probability that a random permutation contains no cycle with length in ${A}$ is at most ${2\left(\sum_{a\in A} 1/a\right)^{-1}}$ .

Although most of their results are of the above approximate nature, they prove at least one beautiful exact counting result, and I thought I might relate it here.

Theorem 1 If ${q}$ is a prime power then the proportion of ${\sigma\in S_n}$ with order not divisible by ${q}$ is exactly

$\displaystyle \left(1-\frac{1}{q}\right)\left(1-\frac{1}{2q}\right)\cdots\left(1-\frac{1}{\lfloor n/q\rfloor q}\right).$

Proof: The number of ${\sigma\in S_n}$ with ${m_1}$ cycles of length ${v_1}$ , ${m_2}$ cycles of length ${v_2}$ , ${\dots}$ , and ${m_k}$ cycles of length ${v_k}$ , where ${m_1 v_1 + \cdots m_k v_k = n}$ , is

$\displaystyle \frac{n!}{m_1!\cdots m_k! v_1^{m_1}\cdots v_k^{m_k}}.$

Indeed, one can partition ${\{1,\dots,n\}}$ into ${m_i}$ sets of size ${v_i}$ for each ${i}$ in

$\displaystyle \frac{n!}{m_1!\cdots m_k! v_1!^{m_1}\cdots v_k!^{m_k}}$

ways, and then one can arrange each of the ${m_i}$ sets of size ${v_i}$ for each ${i}$ into cycles in

$\displaystyle (v_1 - 1)!^{m_1} \cdots (v_k - 1)!^{m_k}$

ways. Moreover, the order of every such ${\sigma}$ is ${\text{lcm}(v_1,\dots,v_k)}$ , so the order of ${\sigma}$ is divisible by ${q}$ if and only if some ${v_i}$ is divisible by ${q}$ . (This is the where we use the hypothesis that ${q}$ is a prime power.) Thus the proportion of ${\sigma\in S_n}$ with order not divisible by ${q}$ is

$\displaystyle \sum\frac{1}{m_1!\cdots m_k! v_1^{m_1} \cdots v_k^{m_k}},$

where the sum runs over all ${k\geq 0}$ and ${2k}$ -tuples ${(m_1,\dots,m_k,v_1,\dots,v_k)}$ of positive integers such that ${m_1 v_1 + \cdots m_k v_k = n}$ and such that no ${v_i}$ is divisible by ${q}$ . But this is just the coefficient of ${X^n}$ in

$\displaystyle \begin{array}{rcl} \prod_{v:q\not{\mid} v} \sum_{m\geq 0} \frac{X^{mv}}{m! v^m} &=&\prod_{v:q\not\mid v} \exp\left(\frac{X^v}{v}\right) \\ &=& \exp\left(\sum_{v:q\not\mid v} \frac{X^v}{v}\right)\\ &=& \exp\left(\sum_v \frac{X^v}{v} - \sum_v \frac{X^{qv}}{qv}\right)\\ &=& \exp\left(-\log(1-X) + \log(1-X^q)/q\right)\\ &=& \frac{(1-X^q)^{1/q}}{1-X}\\ &=& (1 + X + \cdots + X^{q-1}) (1-X^q)^{-\frac{q-1}{q}}\\ &=& (1+X+\cdots+X^{q-1}) \left(1 + \left(1-\frac{1}{q}\right) X^q + \left(1-\frac{1}{q}\right)\left(1-\frac{1}{2q}\right)X^{2q} + \cdots\right), \end{array}$

where the last equality follows from the binomial formula. This completes the proof. $\Box$

Such an explicit formula should make us feel foolish for having used generating functions. Is there a direct combinatorial proof?

By the way, for those who are not already aware of this invaluable resource, almost all of Erdős’s papers have been made freely available by the Renyi institute.

Erdős–Turán statistical group theory

Published by Sean Eberhard

Leave a Reply Cancel reply

Share this:

Like this:

Related

Published by Sean Eberhard

Leave a Reply Cancel reply