Uncategorized – Page 6 – Random Permutations

Let ${G}$ be a locally compact abelian group and let ${M(G)}$ be the Banach algebra of regular complex Borel measures on ${G}$ . Given ${\mu\in M(G)}$ its Fourier transform

$\displaystyle \hat{\mu}(\gamma) = \int \overline{\gamma}\,d\mu,$

is a continuous function defined on the Pontryagin dual ${\hat{G}}$ of ${G}$ . If the measure ${\mu}$ is “nice” in some way then we expect some amount of regularity from the function ${\hat{\mu}}$ . For instance if ${\mu}$ is actually an element of the subspace ${L^1(G)\subset M(G)}$ of measures absolutely continuous with respect to the Haar measure of ${G}$ then the Riemann-Lebesgue lemma asserts ${\hat{\mu}\in C_0(\hat{G})}$ .

The idempotent theorem of Cohen, Helson, and Rudin describes the structure of measures ${\mu}$ whose Fourier transform ${\hat{\mu}}$ takes a discrete set of values, or equivalently, since ${\|\hat{\mu}\|_\infty\leq\|\mu\|}$ , a finite set of values. To describe the theorem, note that we can define ${P(\mu)}$ for any polynomial ${P}$ by taking appropriate linear combinations of convolution powers of ${\mu}$ , and moreover we have the relation ${\widehat{P(\mu)} = P(\hat{\mu})}$ , where on the right hand side we apply ${P}$ pointwise. Thus if ${\hat{\mu}}$ takes only the values ${a_1,\dots,a_n}$ then by setting

$\displaystyle P_i(x) = \prod_{j\neq i} (x-a_j)/(a_i-a_j)$

we obtain a decomposition ${\mu = a_1\mu_1 + \cdots + a_n\mu_n}$ of ${\mu}$ into a linear combination of measures ${\mu_i=P_i(\mu)}$ whose Fourier transforms ${\hat{\mu_i} = P_i(\hat{\mu})}$ take only values ${0}$ and ${1}$ . Such measures are called idempotent, because they are equivalently defined by ${\mu\ast\mu=\mu}$ . By the argument just given it suffices to characterise idempotent measures: this explains the name of the theorem.

The most obvious example of an idempotent measure is the Haar measure ${m_H}$ of a compact subgroup ${H\leq G}$ . Moreover we can multiply any idempotent measure ${\mu}$ by a character ${\gamma\in\hat{G}}$ to obtain a measure ${\gamma\mu}$ defined by

$\displaystyle \int f \,d(\gamma\mu) = \int f\gamma\,d\mu.$

This measure ${\gamma\mu}$ will again be idempotent, as

$\displaystyle \begin{array}{rcl} \int f\,d(\gamma \mu\ast\gamma \mu) &=& \int\int f(x+y)\gamma(x)\gamma(y)\,d\mu(x)d\mu(y) \\ &=& \int\int f(x+y) \gamma(x+y)\,d\mu(x)d\mu(y) \\ &=& \int f\gamma\,d\mu. \end{array}$

If we add or subtract two idempotent measures then though we may not have again an idempotent measure we certainly have a measure whose Fourier transform takes integer values. On reflection, it feels more natural in the setting of harmonic analysis to require that ${\hat{\mu}}$ takes values in a certain discrete subgroup than to require that it take values in ${\{0,1\}}$ , so we relax our restriction so. The idempotent theorem states that we have already accounted for all those ${\mu}$ such that ${\hat{\mu}}$ is integer-valued.

Theorem 1 (The idempotent theorem) For every ${\mu\in M(G)}$ such that ${\hat{\mu}}$ is integer-valued there is a finite collection of compact subgroups ${G_1,\dots,G_k\leq G}$ , characters ${\gamma_1,\dots,\gamma_k\in\hat{G}}$ , and integers ${n_1,\dots,n_k\in\mathbf{Z}}$ such that

$\displaystyle \mu = n_1\gamma_1 m_{G_1} + \cdots + n_k\gamma_k m_{G_k}.$

As a consequence we deduce a structure theorem for ${\mu}$ with ${\hat{\mu}}$ taking finitely many values, as we originally wanted: for every such ${\mu}$ there is a finite collection of compact subgroups ${G_1,\dots,G_k\leq G}$ , characters ${\gamma_1,\dots,\gamma_k\in\hat{G}}$ , and complex numbers ${a_1,\dots,a_k\in\mathbf{C}}$ such that

$\displaystyle \mu = a_1\gamma_1 m_{G_1} + \cdots + a_k \gamma_k m_{G_k}.$

The theorem was first proved in the case of ${G=\mathbf{R}/\mathbf{Z}}$ by Helson in 1953: in this case the theorem states simply that if ${\hat{\mu}}$ is integer-valued then it differs from some periodic function in finitely many places. In 1959 Rudin gave the theorem its present form and proved it for ${(\mathbf{R}/\mathbf{Z})^d}$ . Finally in 1960 Cohen proved the general case, in the same paper in which he made the first substantial progress on the Littlewood problem. The proof was subsequently simplified a good deal, particularly by Amemiya and Ito in 1964. We reproduce their proof here.

First note that if ${\hat{\mu}}$ is integer-valued then ${\mu}$ is supported on a compact subgroup. Indeed by inner regularity there is a compact set ${K}$ such that ${|\mu|(K^c)<0.1}$ , the set ${U}$ of all ${\gamma\in\hat{G}}$ such that ${|1-\gamma|<0.1/\|\mu\|}$ on ${K}$ is then open, and if ${\gamma\in U}$ then

$\displaystyle \|\gamma\mu-\mu\| = \int_G |\gamma-1|\,d|\mu| \leq \int_K + \int_{K^c} < 0.1 + 0.1 < 1.$

But if ${\gamma\mu\neq\mu}$ then

$\displaystyle \|\gamma\mu-\mu\|\geq \|\widehat{\gamma\mu}-\hat{\mu}\|_\infty \geq 1,$

so ${\gamma\mu=\mu}$ for all ${\gamma\in U}$ . Thus ${\Gamma=\{\gamma\in\hat{G}: \gamma\mu=\mu\}}$ is an open subgroup of ${\hat{G}}$ , so by Pontryagin duality its preannihilator ${\Gamma^\perp = \{g\in G: \gamma(g)=1 \text{ for all }\gamma\in\Gamma\}}$ is a compact subgroup of ${G}$ . Clearly ${\mu}$ is supported on ${\Gamma^\perp}$ . Thus from now on we assume ${G}$ is compact.

Fix a measure ${\mu\in M(G)}$ and let ${A=\{\gamma\mu: \gamma\in\hat{G}\}}$ .

Lemma 2 If ${\nu}$ is a weak* limit point of ${A}$ then ${\|\nu\|<\|\mu\|}$ .

Proof: Fix ${\epsilon>0}$ and suppose we could find ${f\in C(G)}$ such that ${\|f\|_\infty\leq 1}$ and ${\int f\,d\nu > (1-\epsilon)\|\mu\|}$ . Let ${\gamma\mu}$ be close enough to ${\nu}$ that ${\Re\int f\gamma\,d\mu > (1-\epsilon)\|\mu\|}$ . Write ${\mu = \theta|\mu|}$ and ${f\gamma\theta = g + ih}$ . Then if ${Z}$ is the complex number ${Z = \int (g+i|h|)\,d|\mu|}$ , then ${|Z|\leq\|\mu\|}$ and

$\displaystyle \Re Z = \int g \,d|\mu| = \Re\int f\gamma\,d\mu > (1-\epsilon)\|\mu\|,$

so we must have

$\displaystyle \Im Z = \int |h|\,d|\mu| \leq (1-(1-\epsilon)^2)^{1/2}\|\mu\| \leq 2\epsilon^{1/2}\|\mu\|.$

Thus also

$\displaystyle \int |1 - f\gamma\theta| \,d|\mu| \leq \int |1 - g|\,d|\mu| + \int |h|\,d|\mu| \leq 3\epsilon^{1/2}\|\mu\|.$

But if this holds for both ${\gamma_1\mu}$ and ${\gamma_2\mu}$ , say with ${\gamma_1\mu\neq\gamma_2\mu}$ , then we have

$\displaystyle 1\leq \|\gamma_1\mu-\gamma_2\mu\| \leq \int |\gamma_1 - f\gamma_1\gamma_2\theta|\,d|\mu| + \int |\gamma_2 - f\gamma_1\gamma_2\theta|\,d|\mu| \leq 6\epsilon^{1/2}\|\mu\|,$

so ${\epsilon \geq 1/(36\|\mu\|^2)}$ , so

$\displaystyle \|\nu\| \leq \|\mu\| - \frac{1}{36\|\mu\|}.$

This proves the lemma. $\Box$

Lemma 3 If ${\nu}$ is a weak* limit point of ${A}$ then ${\nu}$ is singular with respect to the Haar measure ${m_G}$ of ${G}$ .

Proof: By the Radon-Nikodym theorem we have a decomposition ${\mu = f m_G + \mu_s}$ for some ${f\in L^1(G)}$ and some ${\mu_s}$ singular with respect to ${m_G}$ . By the Riemann-Lebesgue lemma then ${\nu}$ is a limit point of ${\{\gamma\mu_s:\gamma\in\hat{G}\}}$ . Thus for any open set ${U}$ and ${f\in C(G)}$ such that ${\|f\|_\infty\leq 1}$ and ${f=0}$ outside of ${U}$ we have

$\displaystyle \left|\int f\,d\nu\right| \leq \sup_\gamma \left|\int f\gamma \,d\mu_s\right| \leq |\mu_s|(U),$

so ${|\nu|(U)\leq |\mu_s|(U)}$ . This inequality extends to Borel sets in the usual way, so ${\nu}$ is singular. $\Box$

The theorem follows relatively painlessly from the two lemmas. Fix ${\mu\in M(G)}$ with ${\hat{\mu}}$ integer-valued and let ${A = \{\gamma\mu: \int\gamma\,d\mu\neq 0\}}$ . Then ${\overline{A}}$ is weak* compact, so because ${\|\cdot\|}$ is lower semicontinuous in the weak* topology there is some ${\nu\in\overline{A}}$ of minimal norm. Since ${\int d\nu}$ is an integer different from ${0}$ we must have ${\nu\neq 0}$ . Thus by Lemma~2 the set ${\{\gamma\nu: \int\gamma\,d\nu\neq 0\}}$ is finite. But this implies that

$\displaystyle \nu = (n_1 \gamma_1 + \cdots + n_k \gamma_k) m_H \ \ \ \ \ (1)$

for some ${n_1,\dots,n_k\in\mathbf{Z}}$ , ${\gamma_1,\dots,\gamma_k\in\hat{G}}$ , and ${H=\{\gamma:\gamma\nu=\nu\}^\perp}$ the support group of ${\nu}$ . In particular ${\nu}$ is absolutely continuous with respect to ${m_H}$ , so because ${\nu|_H}$ is in the weak* closure of ${\{\gamma\mu|_H:\gamma\in\hat{G}\}}$ we deduce from Lemma 2 that ${\nu|_H = \gamma\mu|_H}$ for some ${\gamma}$ . Thus ${\mu|_H}$ is a nonzero measure of the form (1) and we have an obvious mutually singular decomposition

$\displaystyle \mu = \mu|_H + (\mu-\mu|_H).$

Since ${\|\mu-\mu|_H\| = \|\mu\| - \|\mu|_H\|\leq\|\mu\|-1}$ the theorem follows by induction.

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.

Category: Uncategorized

The idempotent theorem

Erdős–Turán statistical group theory