Random Permutations

This is a research blog, but it is hard to think about much other than coronavirus in this unique time. Here are some thoughts.

Some extreme fears:

Let’s get these out of the way first.

People keep greedily stock-piling and vulnerable people go without necessary resources, or people get injured in the frenzy. More generally, I am worried about panic, mob mentality, riots, looting, etc.
Blame. Blame China for creating the thing, blame the government for mismanaging, blame your neighbour for infecting you, blame the stockpilers (see point 1).
Social distance. Not in the sense of infection control (see wikipedia), which is practical and good, but in a more general sense of developing selfishness, nationalism, every-man-for-himself-ism, the opposite of solidarity. A unique feature of the current crisis is that our usual mechanisms for showing unity are mostly compromised.
Tip of the iceberg: maybe this is just phase 1, and the virus will keep mutating and mutating, and who knows what will happen.

More concretely, and most obviously, I am worried about the safety of people I know. I will leave “how to think about the risk” for some other time (or some other author).

An extreme hope: virtual connectivity

It sounds frivolous compared to my list of fears, but just now it’s one of my big hopes for humans. In this era of technology we deserve to be much better at this. The only reason I don’t use Skype more is the technology seems just slightly crap, e.g., with dropped or slow connections, or the interaction is just slightly clumsy, with the natural timing of conversation out of step. The current crisis could drive change here: technologically, much like how war invented the microwave, but also just by forcing us to practice and develop the social protocol.

Why do I consider that important? Because I think it’s a key step for us as a global society to travel less, and traveling less will not only slow the spread of disease but also help to slow climate change, which after all is still a much greater existential threat to the race, but lacks (at least for now) the shock-and-awe necessary to generate a collective response.

In short, I am hoping that a global crisis like the current one compels us to develop tools quickly that we are going to need anyway, and virtual connectivity is my big example.

A message from Queens’ College Acting Senior Tutor

I liked this message from Queens’ College Acting Senior Tutor, Prof Martin Dixon, to students, a much-needed message of responsibility and leadership:

Equally, do not underestimate the positive impact that you can make. Perhaps you may not realise, but being a student at Cambridge causes people to hold you in high regard. Your words and actions will be listened to and watched. You are among the very best students in the world, and you can lead by example. A kind word, a simple act of support, a calming of panic, can have a profound effect on those around you. You may not want this responsibility, but you have it. You also have the opportunity to demonstrate what it means to be a Cambridge student in a time of uncertainty. Please live up to the faith we have in you.

Source: the tab, Emily Hyde & Claudia Rowan, 2020/03/13

Of course, the message applies much more broadly than to just students at Cambridge. Anybody with any sort of visible status has the responsibility to think calmly and critically in this time of crisis, as their decisions and opinions are more liable to influence and spread.

Isaac Newton and the black death

Yes, Isaac Newton invented calculus, optics, gravity, etc, etc, during the great plague (1665–1666), the last major recurrence of bubonic plague in England. Therefore, so says everybody recently it seems, lots of excellent ground-breaking research is going to happen over the next couple of months. Maybe, but I’m not as confident. Here are some counterpoints.

Most science is done in labs these days.
Science that isn’t done in labs (e.g., mathematics, theoretical physics) is often about collective understanding, and sharing ideas is essential.
Lots of people have, like, 2-year-olds at home.
Isaac Newton didn’t have minute-by-minute updates on the progress of the disease.

More on point 2: Mathematics at its heart is often about developing collective understanding: that’s why giving talks is so cental, to give people the opportunity to interpose questions off the cuff, test their understanding, bounce ideas off each other. Reading and writing papers is an equally important part of the process, but a much slower part of the process.

Personally

Personally, my usual research is not much affected: I normally work from my office at home and collaborate remotely, mostly by email. In the coming months I hope to work on virtual colloquia, virtual teaching, etc. It will be interesting to see where we get to in a couple months’ or a year’s time.

Best wishes to anyone reading this. Stay safe, be sensible, don’t panic. Stay in touch.

Problem 1 Let ${G}$ be a group of order ${n}$ . Is there a bijection ${f \colon G \to G}$ such that the map ${x \mapsto x f(x)}$ is also a bijection?

For example, if ${G}$ has odd order, you can just take ${f(x) = x}$ . Then ${x f(x) = x^2}$ , and because every element has odd order this defines a bijection. If ${G = \mathbf{F}_2^d}$ , then it suffices to find a linear map without an eigenvalue. Cyclic groups of even order never have complete mappings (option 1: stop reading and try to prove this as a diverting puzzle; option 2: read on, and it will be explained and become essential).

In general, a solution to Problem 1 is called a complete mapping. The definition of complete mapping is a little strange. Here is some motivation, if you want some. The construction of finite projective planes is a problem going back to Euler. You can think of a finite projective plane as a collection of ${n-1}$ mutually orthogonal ${n \times n}$ Latin squares, where two Latin squares are termed orthogonal if, when superimposed, the ${n^2}$ pairs of symbols are distinct. The most familiar Latin square is the cyclic Latin square, which has entries ${i + j \bmod n}$ for ${0 \leq i, j < n}$ . More generally, for any group ${G}$ of order ${n}$ , the multiplication table of ${G}$ is an ${n \times n}$ Latin square. If you write down what it means for another square to be orthogonal to the ${G}$ -based Latin square, you will find yourself re-inventing the definition of complete mapping.

Another motivation, of possibly broader interest, is simply that counting complete mappings turns out to be interesting and difficult, and requires us to hone some counting skills that, we hope, will be applicable elsewhere.

The concerted effort to answer Problem 1 began with Hall and Paige (1955). First, there is an obstruction, beginning with cyclic groups of even order. More generally, consider the abelianization ${G^\textup{ab}}$ of ${G}$ , and suppose all the elements of ${G}$ have nontrivial sum in ${G^\textup{ab}}$ . Then if ${f}$ is a bijection the elements ${x f(x)}$ will sum up to zero, so ${x f(x)}$ cannot possibly be a bijection. Therefore in order for a complete mapping to exist, we must have ${\prod G \in [G, G]}$ . Hall and Paige proved that this condition is equivalent to the Sylow 2-subgroups of ${G}$ being trivial or noncyclic. Henceforth this condition will be called the Hall–Paige condition. Conversely, Hall and Paige conjectured that Problem 1 has a solution as long as ${G}$ satisfies their condition.

Conjecture 2 (Hall–Paige) Every group satisfying the Hall–Paige condition has a complete mapping.

Progress on the Hall–Paige conjecture was slow. Hall and Paige (1955) proved the conjecture for solvable groups and symmetric and alternating groups, but progress on the full conjecture didn’t really get under way until the classification was established. For a complete history, see the book by Evans. Aschbacher (1990) proved various restrictions on the form of a minimal counterexample. The real breakthrough came in 2009 when Wilcox showed that a minimal counterexample would have to be simple, and furthermore could not be any of the simple groups of Lie type, which leaves only the Tits group and the 26 sporadic groups. At this point the problem is in principle a finite check, but still a mammoth one. Combining Wilcox’s technology with extensive computer algebra, Evans ruled out all of the remaining groups, with one exception: the fourth Janko group ${J_4}$ , a group of order ${86775571046077562880 \approx 9 \times 10^{19}}$ , and finally ${J_4}$ was ruled out by Bray in work that remained unpublished until last year. Thus the Hall–Paige conjecture was proved. Although many people contributed, it is customary to attribute the final result to Wilcox, Evans, and Bray.

Meanwhile, another strand of study was developing. Suppose we take just the cyclic group ${G = C_n}$ . We know there is at least one complete mapping as long as ${n}$ is odd. But how many are there?

Problem 3 How many complete mappings does the cyclic group ${C_n}$ have?

This problem can be compared with the well-known ${n}$ queens puzzle: how many ways can you place ${n}$ queens on an ${n \times n}$ chessboard so that no two are attacking? If you make the chessboard toroidal, so that going off one edge brings you back on the opposite one, and if you only allow the queens to use one of the two diagonals, then you get an equivalent question.

Heuristically, there are ${n!}$ bijections ${f}$ , and for each the function ${x\mapsto x f(x)}$ has a roughly ${n!/n^n}$ chance of being a bijection, so you can guess that the number of complete mappings is about ${n!^2 / n^n}$ ; this conjecture is attributed to Vardi (1991) (in a weaker form) and Wanless (2011).

Conjecture 4 (Vardi–Wanless) The number of complete mappings of ${C_n}$ is asymptotically ${(e^{-1} + o(1))^n n!}$ .

This is where additive combinatorics enters. A few years ago Freddie Manners, Rudi Mrazović, and I started thinking about Problem 3, motivated by the observation that it can be thought of as requesting the number of solutions to

$\displaystyle \pi_1 + \pi_2 = \pi_3$

(or additive triples) with ${\pi_1, \pi_2, \pi_3 \in S}$ , where ${S \subset C_n^n}$ is the set of bijections. The usual tool for counting additive triples (or solutions to any linear equation) is Fourier analysis; hence the problem reduces to understanding the Fourier transform of ${S}$ . After barking up this tree (for quite a while), we were eventually able to prove the Vardi–Wanless conjecture. In fact we proved something even more precise: the solution to Problem 3 turns out to be asymptotically

$\displaystyle (e^{-1/2} + o(1)) n!^2/n^{n-1},$

which differs from the Vardi–Wanless guess (though they never made a guess so precise) in two important respects: there is an extra factor of ${n}$ , and a factor of ${e^{-1/2}}$ (what the hell?).

Since the key to unlocking Problem 3 is Fourier analysis, it seems like we are using the abelianness of ${C_n}$ in an absolutely essential way, but today Freddie and Rudi and I have a new announcement: we can count complete mappings in nonabelian groups too, and the asymptotic is essentially unchanged.

Theorem 5 Let ${G}$ be a group of order ${n}$ satisfying the Hall–Paige condition. Then the number of complete mappings of ${G}$ is asymptotically

$\displaystyle (e^{-1/2} + o(1)) |G^\textup{ab}| n!^2 / n^n.$

Here are some other highlights from our paper:

The asymptotic above is begging for a heuristic explanation. We give one! It uses something called the principle of maximum entropy, which I personally can’t wait to use again. Basically, if ${f}$ is a random bijection, ${x \mapsto x f(x)}$ is more prone to collisions than a random function, and, heuristically, has a Gibbs distribution with a particular partition function, and a calculation shows that its probability of being a bijection is therefore smaller by a constant factor.
We evaluate the next term in the asymptotic! We actually show that the number of complete mappings is
$\displaystyle e^{-1/2} (1 + (1/3 + \textup{inv}(G)/4)/n + O(1/n^2)) |G^\textup{ab}| n!^2/n^n,$

where ${\textup{inv}(G)}$ is the proportion of involutions in ${G}$ . This verifies another conjecture of Wanless: that elementary abelian ${2}$ -groups have the most complete mappings of any group of the same order. We can keep going, in principle, but really we would rather not: there is a combinatorial explosion in the number of “collision types” (in a sense we make precise), and to give the next term in the asymptotic you need to sum over all of these.
Orthogonally, we can give effective estimates instead of asymptotics. For example, we can show that as long as ${|G| > 10^5}$ and all nontrivial complex representations of ${G}$ have degree at least ${21}$ , then ${G}$ has a positive number of complete mappings (in fact, within a constant factor of ${n!^2/n^n}$ such). By combining a few such effective statements, we can cover all the simple sporadic groups, apart from the two smallest ${M_{11}}$ and ${M_{12}}$ . You can view this as a second-generation proof of the Evans–Bray contribution to the Hall–Paige conjecture. In fact, our proof covers all nonabelian finite simple groups except for some alternating groups, some ${\textup{PSL}_2(q)'s}$ , and about ten other groups that we list.