number theory – Random Permutations

Recall that a Moore graph (of diameter 2) is a regular graph of girth ${5}$ and diameter ${2}$ . Equivalently, it is a triangle-free graph such that any two nonadjacent vertices have a unique common neighbour. There are famously few Moore graphs: only the 5-cycle of degree 2, the Petersen graph of degree 3, and the Hoffman–Singleton graph of degree 7, and possibly a graph (or even several graphs) of degree ${57}$ and order ${3250}$ (the “missing Moore graph”). This is the Hoffman–Singleton theorem.

The Hoffman–Singleton theorem being too mysterious, it is tempting to try to find a weakening of the definition of a Moore graph that allows a few more graphs but still finitely many. One hopes that the “finitely many” part would have some more direct combinatorial proof (as opposed to the algebraic voodoo that goes into Hoffman–Singleton). Such a conjecture was recently posed by Wood and stated in a paper of Devillers, Kamcev, McKay, O Cathain, Royle, Van de Voorde, Wanless, and Wood.

Conjecture 1 For every integer ${t \ge 2}$ there are only finitely many triangle-free ${K_{2,t}}$ -free graph with diameter ${2}$ apart from stars.

For ${t = 2}$ this is immediate from Hoffman–Singleton. The authors (Devillers, Kamcev, …) find almost ${6}$ million examples of such graphs with ${t=3}$ , but “nothing suggestive of an infinite class”. However, the following construction (which arose in conversations with Padraig O Cathain) disproves the conjecture for ${t = 7}$ .

Let ${p}$ be a prime congruent to ${11}$ mod ${12}$ . This condition ensures that ${-1}$ and ${-3}$ are quadratic nonresidues. Let ${G = \mathbf{F}_p^2}$ and let ${A = \{(x, \pm x^2) : x \in \mathbf{F}_p, x \ne 0\}}$ . Now consider the Cayley graph ${\mathrm{Cay}(G, A)}$ . Equivalently, this is the graph with vertex set $\mathbf{Z}/p\mathbf{Z} \times \mathbf{Z}/p\mathbf{Z}$ and $(x_1, y_1)$ joined to $(x_2, y_2)$ if and only if $y_1 - y_2 = \pm (x_1 - x_2)^2 \ne 0$ . We claim ${\mathrm{Cay}(G, A)}$ is triangle-free, ${K_{2,7}}$ -free, and diameter-2.

Claim 1: ${\mathrm{Cay}(G, A)}$ is triangle-free. Equivalently, ${A}$ is sum-free.

Proof: We must check that there do not exist nonzero ${x, y, z}$ such that ${(x, \pm x^2) + (y, \pm y^2) + (z, \pm z^2) = 0}$ . Equivalently, we must check that

$\displaystyle (x+y)^2 \pm x^2 \pm y^2 = 0$

implies ${xy(x+y) = 0}$ . There are four cases, depending on the two signs:

${(-, -)}$ : We get ${2xy = 0}$ .

${(-, +)}$ : We get get ${2(x+y)y = 0}$ .

${(+, -)}$ : We get ${2(x+y)x = 0}$ .

${(+, +)}$ : We get ${x^2 + xy + y^2 = 0}$ . Since the polynomial ${X^2 + X + 1}$ has discriminant ${-3}$ , which is a quadratic nonresidue, it follows that ${x = y = 0}$ .

Claim 2: ${\mathrm{Cay}(G, A)}$ is ${K_{2,7}}$ -free and diameter- ${2}$ . In fact, we have ${2 \le 1_A * 1_A(g) \le 6}$ for every nonzero ${g \notin A}$ .

Here ${1_A * 1_A(g)}$ is the number of solutions to ${a_1 + a_2 = g}$ with ${a_1, a_2 \in A}$ . It is an exercise to check that the first statement follows from the second, so we just prove the second.

Proof: Let ${g = (z, w)}$ be a nonzero point not in ${A}$ . First assume ${z \ne 0}$ . The value of ${1_A*1_A(g)}$ is the number of quadruples ${(x, y, \epsilon_1, \epsilon_2)}$ with ${x, y \in \mathbf{F}_p}$ nonzero and ${\epsilon_1, \epsilon_2 = \pm 1}$ such that

$\displaystyle x + y = z, \qquad \epsilon_1 x^2 + \epsilon_2 y^2 = w.$

For fixed ${z, w, \epsilon_1, \epsilon_2}$ is equivalent to count ${x \ne 0}$ such that

$\displaystyle \epsilon_1 x^2 + \epsilon_2 (x-z)^2 = w.$

If the signs are equal then this is a nontrivial quadratic equation, so there are at most ${2}$ solutions. If the signs are different then we get a linear equation

$\displaystyle 2xz - z^2 = \epsilon_1 w,$

which has a unique solution. If that solution is ${0}$ or ${z}$ then we get ${w = \pm z^2}$ , contrary to the assumption that ${g \notin A}$ .

Now assume ${z = 0}$ and ${w}$ is nonzero. Then ${1_A * 1_A(g)}$ is the number of triples ${(x, \epsilon_1, \epsilon_2)}$ with ${x}$ nonzero such that ${(\epsilon_1 + \epsilon_2) x^2 = w}$ . If the signs are different there are no solutions, since ${w}$ is nonzero. Otherwise the equation is ${2 \epsilon_1 x^2 = w}$ . Since ${-1}$ is a quadratic nonresidue, one of the choices of sign gives ${0}$ solutions and the other gives ${2}$ solutions. Therefore ${1_A * 1_A(g) = 2}$ .

Thus in all cases ${2 \le 1_A * 1_A(g) \le 6}$ , as claimed.

1. Boston–Shalev for conjugacy classes

Last week Daniele Garzoni and I uploaded to the arxiv a preprint on the Boston–Shalev conjecture for the conjugacy class weighting. The Boston–Shalev conjecture in its original form predicts that, in any finite simple group $G$ , in any transitive action, the proportion of elements acting as derangements is at least some universal constant $c > 0$ . This conjecture was proved by Fulman and Guralnick in a long series of papers. Daniele and I looked at conjugacy classes instead, and we found an analogous result to be true: the proportion of conjugacy classes containing derangements is at least some universal constant $c' > 0$ .

Our proof depends on the correspondence between semisimple conjugacy classes in a group of Lie type and polynomials over a finite field possibly with certain restrictions: either symmetry or conjugate-symmetry. We studied these sets of polynomials from an “anatomical” perspective, and we needed to prove several nontrivial estimates, e.g., for

the number of polynomials with a factor of a given degree (which is closely related the “multiplication table problem”),
the number of polynomials with an even or odd number of irreducible factors,
the number of polynomials with no factors of small degree,
or the number of polynomials factorizing in a certain way (e.g., as $f = gg^*$ , $g$ irreducible, $g^*$ the reciprocal polynomial).

For a particularly neat example, we found that, if the order of the ground field is odd, exactly half the self-reciprocal polynomials have an even number of irreducible factors — is there a simple proof of this fact?

2. Growth in Linear Groups

Yesterday Brendan Murphy, Endre Szabo, Laci Pyber, and I uploaded a substantial update to our preprint Growth in Linear Groups, in which we prove one general form of the “Helfgott–Lindenstrauss conjecture”. This conjecture asserts that if a symmetric subset $A$ of a general linear group $\mathrm{GL}_n(F)$ ( $n$ bounded, $F$ an arbitrary field) exhibits bounded tripling, $|A^3| \le K|A|$ , then $A$ suffers a precise structure: there are subgroup $H \trianglelefteq \Gamma \le \langle A \rangle$ such that $\Gamma / H$ is nilpotent of class at most $n-1$ , $H$ is contained in a bounded power $A^{O_n(1)}$ , and $A$ is covered by $K^{O_n(1)}$ cosets of $\Gamma$ . Following prodding by the referee and others, we put a lot more work in and proved one additional property: $\Gamma$ can be taken to be normal in $\langle A \rangle$ . This seemingly technical additional point is actually very subtle, and I strongly doubted whether it was true late into the project, more-or-less until we actually proved it.

We also added another significant “application”. This is not exactly an application of the result, but rather of the same toolkit. We showed that if $G \le \mathrm{GL}_n(F)$ (again $F$ an arbitrary field) is any finite subgroup which is $K(n)$ -quasirandom, for some quantity $K(n)$ depending only on $n$ , then the diameter of any Cayley graph of $G$ is polylogarithmic in the order of $|G|$ (that is, Babai’s conjecture holds for $G$ ). This was previously known for $G$ simple (Breuillard–Green–Tao, Pyber–Szabo, 2010). Our result establishes that it is only necessary that $G$ is sufficiently quasirandom. (There is a strong trend in asymptotic group theory of weakening results requiring simplicity to only requiring quasirandomness.)

The intention of our paper is more-or-less to “polish off” the theory of growth in bounded rank. By contrast, growth in high-rank simple groups is still poorly understood.

3. The Kelley–Meka result

Not my own work, but it cannot go unmentioned. There was a spectacular breakthrough in additive combinatorics last week. Kelley and Meka proved a Behrend-like upper bound for the density of a subset $A \subset \{1, \dots, n\}$ free of three-term arithmetic progressions (Roth’s theorem): the density of $A$ is bounded by $\exp(-c (\log n)^\beta)$ for some constants $c, \beta > 0$ . Already there are other expositions of the method which are also worth looking at: see the notes by Bloom and Sisask and Green (to appear, possibly).

Until this work, density $1 /\log n$ was the “logarithmic barrier”, only very recently and barely overcome by Bloom and Sisask. Now that the logarithmic barrier has been completely smashed, it seems inevitable that the new barometer for progress on Roth’s theorem is the exponent $\beta$ . Kelley and Meka obtain $\beta = 1/11$ , while the Behrend construction shows $\beta \le 1/2$ .