research – 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.

I just uploaded to the arxiv my paper Diameter of classical groups generated by transvections. This paper is a small further step in the direction of Babai’s conjecture on the diameter of simple groups, which predicts for any (nonabelian) finite simple group ${G}$ and for any generating set ${S}$ , the number of elements of ${S}$ needed to represent any element of ${G}$ is bounded by ${(\log |G|)^C}$ for some constant ${C}$ . Roughly this means that finite simple groups are “well-connected”, and starting from any generators you can “find” any element of the group rapidly.

The “Pyber programme” suggests that Babai’s conjecture is really three problems. Assume ${G}$ is either ${A_n}$ or a classical group with defining module ${\mathbf F_q^n}$ , say ${\mathrm{SL}_n(q)}$ . The degree of an element ${g \in G}$ is the size of its support if ${G = A_n}$ or the rank of ${g - 1}$ if ${G}$ is classical. Now the three problems are:

Given arbitrary generators, find an element of degree at most ${0.9 n}$ .
Given a set of generators including an element of degree at most ${0.9 n}$ , find an element of minimal degree.
Given a set of generators including an element of minimal degree, find everything.

(In each problem, “find” really means “establish the existence of an element whose length in the generators is bounded by ${(\log |G|)^C}$ ”.)

The third problem is actually trivial for ${A_n}$ . Note that ${\log |A_n| = \log n! \approx n \log n}$ , so “polynomial in ${\log |G|}$ ” = “polynomial in ${n}$ ”. Now suppose a set of generators includes a ${3}$ -cycle (an element of minimal degree in the alternating group). There are fewer than ${n^3}$ such ${3}$ -cycles, and ${G}$ acts on the ${3}$ -cycles transitively by conjugation, so all ${3}$ -cycles have length at most ${n^3}$ in the generators. Every element of ${A_n}$ can be written as the product of at most ${n}$ such ${3}$ -cycles, so every element of ${A_n}$ has length at most ${n^4}$ in the generators.

But for classical groups the third problem is highly nontrivial. In the case of ${G = \mathrm{SL}_n(q)}$ , the elements of minimal degree are the transvections. The number of transvections is comparable to ${q^{2n}}$ , i.e., exponential in ${n}$ , so such a cheap argument is not available. But, the third problem is now solved anyway (with the exception of orthogonal groups — see below!). This is what my paper is about. The case of odd characteristic had been done already by Garonzi, Halasi, and Somlai (omitting some cases in characteristic ${3}$ ), but the (most complicated) case of characteristic ${2}$ is covered in my paper.

The basic approach, following the previous work of Garonzi, Halasi, and Somlai, is to reduce as much of the algebra as possible to combinatorics. We can make an analogy with the symmetric group ${S_n}$ . Let ${T \subset S_n}$ be a set of transpositions ${(ij)}$ (where ${1 \le i < j \le n}$ ). The transposition graph ${\Gamma}$ is defined to have vertex set ${\{1, \dots, n\}}$ and an edge ${i \sim j}$ whenever ${(ij) \in T}$ . Let ${G}$ be the group generated by ${T}$ . Then the following are equivalent:

${\Gamma}$ is connected,
${G}$ is transitive,
${G = S_n}$ .

This illustrates one simple way in which algebra can be reduced to combinatorics. There is an analogous object for transvections called the transvection graph (though really it is a directed graph), and it can be used to understand when a set of transvections in ${\mathrm{SL}_n(q)}$ generates an irreducible subgroup, but it is necessary to introduce several more gadgets (mostly combinatorial) to understand whether they actually generate ${\mathrm{SL}_n(q)}$ .

Most of the work in the paper involves leveraging a theorem of Kantor classifying the irreducible subgroups generated by transvections. For each type of such subgroup, we try to build a combinatorial “certificate” that our set of transvections is not trabbed in that type of subgroup. For example, if our transvections are not trapped in a symplectic group then there must be a “nonsymplectic cycle” in the transvection graph. This industrial use of Kantor’s theorem is the novel idea of my paper.

What about orthogonal groups? What I really mean is ${\Omega_n^\varepsilon(q)}$ , the index-2 subgroup of ${\mathrm{SO}_n(q)}$ . These groups do not contains transvections! The elements of minimal degree have degree ${2}$ ; they are called “long root elements”. Kantor’s theorem also classifies subgroups generated by long root elements, so in principle this problem can be approached in broadly the same way, but we need a suitable variant of the transvection graph (the “long root element graph”?). Even more generally, it does not seem out of reach to prove Babai’s conjecture under the hypothesis that the generators contain an element of bounded degree.

Do these problems sound interesting to you? Are you looking for PhD opportunities in algebra or combinatorics? Consider coming to Belfast to do your PhD! Write to me by email if you are interested (with an introduction and CV).

On a personal note, this paper was quite a slog, and slowly came together over the course of about 8 months of off-and-on effort. That time is not proportionally reflected in the length of the paper but it may be in the technicality of some of the arguments. A particularly challenging part was coming up with a certificate (as described above) for symmetric-type subgroups, i.e., irreducible subgroups of ${\mathrm{SL}_n(q)}$ isomorphic to either ${S_{n+1}}$ or ${S_{n+2}}$ (acting on the deleted permutation module). In the end the argument is not especially difficult but it took a lot of care getting everything right.

By contrast, another paper I recently put on the arxiv was the result of a moment of inspiration and only a day or so of working out the details and writing up. Which paper will get into a better journal I wonder?

Category: research

An infinite sequence of triangle-free K_{2,7}-free graphs of diameter 2

Babai’s conjecture for generating sets containing transvections