A niggling problem

Preparing my talk for the Research Day, I was reminded of a problem I can’t solve, that has niggled me for many years. Maybe someone else can solve it, or maybe I will be encouraged to do it myself. Here it is with some background.

A quasigroup is a set Q with a binary operation whose “Cayley table” is a Latin square. The Cayley table has rows and columns indexed by Q, and the entry in row a and column b is the composition or product ab. The Latin square condition means that

  • each element occurs once in each row; that is, given a and b, there is a unique x such that ax = b.
  • each element occurs once in each column; that is, given a and b, there is a unique y such that ya = b.

A loop is a quasigroup with an identity element e (satisfying ex = xe = x). If we label the first row and column with e, we see that the row labels coincide with the elements in the first column, and the column labels coincide with the elements in the first row.

In a quasigroup Q, the operatiions “left multiplication by a” (given by λa:xax) and “right multiplication by a” (given by ρa:xxa) are permutations. These permutations generate a subgroup of the symmetric group on Q, which is clearly transitive: to map a to b, we multiply by the element given by the “division axiom”. The group generated by all the left and right multiplications is called the multiplication group of Q.

In a loop, it is also important to consider the subgroup of the multuiplication group which is the stabiliser of the identity element e: this is called the inner multiplication group.

The multiplication group of Q may be the full symmetric group. Indeed, this is the “uninteresting case”. (This is one of the situations in which a smaller group is more interesting.) There are a couple of motivations for this view:

  • Jonathan Smith and Ken Johnson have developed a character theory of quasigroups, based on that for groups. In their theory, the character theory of Q is “trivial” if and only if the multiplication group of Q is doubly transitive.
  • A class of loops defined by Bruck and Paige in 1956 consists of the automorphic loops, those for which the inner multiplication group consists of automorphisms of the loop. This class includes groups, for which the inner multiplication group consists precisely of the inner automorphisms (conjugations) xa−1xa. The automorphism group of a loop is never the symmetric group except in some small cases, since there exist elements a and b for which ab is different from a and b (provided that |Q| ≥ 4), and the stabiliser of a and b in the automorphism group fixes their product.

Since it is no secret that there are a huge number of quasigroups, most not very interesting, the following result is not a surprise:

Theorem Almost all quasigroups have the property that their multiplication group is the symmetric group.

“Almost all” here means that the proportion of n-element quasigroups with this property tends to 1 as n tends to infinity.

(There is a diversion necessary here, and a small story. As I have set it up, we are counting “labelled” quasigroups, in which the elements are numbered q1, …, qn. It would be more natural to count them up to isomorphism. In fact this is the same, since almost all quasigroups have trivial automorphism group and so have n! labellings.

The fact that almost all Latin squares have trivial automorphism group was proved independently by Laci Babai and me at about the same time; the proof also works for Steiner triple systems and 1-factorisations of complete graphs. Laci got the result for Steiner triple systems into print first, and the rest became “folklore” for a while. It depended on the proof of the van der Waerden permanent conjecture by Egorychev and Falikman — more precisely, a weaker version proved earlier by Bang suffices.)

The proof is interesting, as it relies on a lovely theorem of Łuczak and Pyber:

Theorem Almost all elements of the symmetric group Sn lie in no proper transitive subgroup of Sn except possibly the alternating group An.

Now the multiplication group of a quasigroup is transitive, as we noted, and it contains the first row of the Latin square (regarded as a permutation); for a random quasigroup, this is a random permutation. So it is almost always the symmetric or alternating group. The final step uses a theorem of Häggkvist and Janssen, according to which the proportion of Latin squares whose rows are all even permutations is exponentially small.

Now the niggling problem is:

Problem Is it also true that almost all loops have multiplication group the symmetric group?

The above argument doesn’t work, because the first row of the Cayley table of a loop is the identity. However, the second row is a derangement. One of the oldest results in probability theory is that a positive proportion of elements of the symmetric group (in the limit, 1/e) are derangements; and since almost none of them lie in “small” proper subgroups of Sn, the argument concludes as before.

But this is not correct. The second row of a random Latin square whose first row is the identity is not a uniform random derangement, since the fist two rows can be extended to a Latin square in different numbers of ways depending on the chosen derangement.

For example, of the nine derangements in S4, three of them are products of two transpositions, and have four extensions to a Latin square; the other six are 4-cycles, and have only two extensions. So each derangement of the first type has probability 1/6, whereas one of the second type has probability 1/12.

Remarkably, it turns out (empirically) that this non-uniformity rapidly washes out as n increases:

Conjecture The probability distribution on derangements defined as above (where the probability of a derangement is the probability that a random Latin square with first row the identity has that derangement as its second row) tends very rapidly to the uniform distribution as n tends to infinity.

For example, for n = 7, the numbers of extensions of the first two rows to a Latin square for the various cycle structures of derangements are

  • (7): 6566400
  • (2,5): 6604800
  • (2,2,3): 6635520
  • (3,4): 6543360

So, from differing by a factor of 2 for n = 4, the probabilities agree to within a little over 1% for n = 7. For larger values, the agreement is even more striking.

There are some results by Nick Cavenagh, Catherine Greenhill and Ian Wanless on bounding the ratios of these probabilities, but they are very far even from showing that the ratios tend to 1.

If it could be shown that this distribution tends to uniform faster than the error term in the Łuczak–Pyber theorem, we would have solved the problem. But there may be other ways to attack it which I haven’t thought of yet.

While I am on the subject, I would like to say a bit more about the Häggkvist–Janssen theorem.

Problem What can be said about the distribution of the number of rows of a random Latin square which (as permutations) have even parity?

Since the message of the preceding conjecture is that there is a lot of near-independence in quite large pieces of a random Latin square, the natural conjecture would be that the distribution is close to binomial with parameter 1/2, at least for large n.

Evidence supports this conjecture fairly well, but the tails of the distribution seem a little heavier than it would predict. The exponential bound in the Häggkvist–Janssen theorem is substantially larger than 1/2n, and examination of small Latin squares suggests that this is with good reason.

But my feeling is that this is an effect of the small sizes which we can deal with. “Interesting” Latin squares are likely to be far from typical in this respect. For example, in the Cayley table of a group, either all rows have the same parity, or there are equally many even and odd rows. (The first alternative holds if the Sylow 2-subgroups of the group in question are cyclic.) These and other interesting quasigroups may be biasing the statistics. I expect it to hold for large squares.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in open problems and tagged , , , , . Bookmark the permalink.

3 Responses to A niggling problem

  1. Sean Eberhard says:

    Hi Peter,

    Your conjecture about the distribution of the second row of a Latin square with first row the identity is interesting and challenging, but it seems like it might be overkill for your problem. We should be able to prove directly that almost all loops have multiplication group the symmetric group by arguing as follows. Fix a transitive subgroup H of S_n that we might be worried about. The number of Latin squares all of whose rows are in H is bounded by |H|^n = n!^n / [S_n : H]^n. On the other hand the total number of Latin squares is n!^n / e^(n^2 + o(n^2)) (a theorem of van Lint and Wilson I think?). Thus we need only worry about transitive subgroups H of index at most e^(n + o(n)), i.e., only H = A_n and H = S_{n/2} wr S_2. Admittedly I don’t immediately see how to deal with H = S_{n/2} wr S_2. Can the theorem of Häggkvist and Janssen you mention (which I know nothing about) be adapted somehow to different subgroups H?

    • Indeed, this should not be too hard. But to me the “second row” conjecture is the most interesting bit. Computation shows that the distribution of the second row of a random Latin square with normalised first row tends extremely rapidly to the uniform distribution on derangements. Nobody has even got close to this yet. But even result much weaker than the truth would settle the loops question essentially without any extra work.
      I am sure that the “second row” conjecture is just the tip of the iceberg. There should be a general conjecture that says that the entries in any set of cells of a random Latin square are close to random subject to the obvious constraints, provided the set is not too large. But I don’t have a precise formulation of this.

  2. Sean Eberhard says:

    I agree that the second row conjecture, as well as the extensions you suggest, are very interesting, but to me they are subsumed by the more general challenge of pinning down the estimate n!^n/e^(n^2 + o(n^2)) more exactly, say up to a factor of 1+o(1). A proof of the correct asymptotic here should allow you to see the effect on the total count, if any, of any local constraints.

    For what it’s worth, I now see one way to deal with H = S_{n/2} wr S_2, completing my earlier sketch. The proof of the upper bound n!^n/e^(n^2 + o(n^2)) for the total number of Latin squares proceeds purely row-by-row: it bounds the number of choices for each subsequent row uniformly over all choices of previous rows. So we can bound the number of Latin squares all of whose rows lie in H by saying that there are at most |H|^k ways to fill out the first k rows, then proceeding with the previous method to bound the number of choices for the remaining n-k rows. By taking k to be n/10 or so, this results in a bound which is smaller than n!^n/e^(n^2 + o(n^2)) by a factor of e^(cn^2) for some constant c.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s