Synchronization update

There is some recent news about the synchronization project. Two steps forward have occurred.

The set-up

Here is a brief recapitulation.

Let G be a transitive permutation group on Ω, where |Ω| = n.

  • We say that G is non-synchronizing if there is a k-subset A and k-partition P of Ω, with 1 < k < n, such that for all g in G, Ag is a transversal for P; G is synchronizing otherwise.
  • We say that G is non-separating if there are subsets A and B of Ω such that |A|, |B| > 1, |A|·|B| = n, such that, for all g in G, |AgB| = 1; G is separating otherwise.

The “official” definition of synchronization hearks back to the origin of this concept in automata theory; but what is said above will do for now. Note that if G is non-synchronizing, then A and any part of P witness the fact that G is non-separating; hence separating implies synchronizing.

For the record, I also mention the graph-theoretic interpretation of these concepts:

  • G is non-synchronizing if there exists a non-trivial (i.e. not complete or null) G-invariant graph with clique number equal to chromatic number; it is synchronizing otherwise.
  • G is non-separating if there exists a non-trivial G-invariant graph with the product of clique number and independence number equal to the number of vertices; it is separating otherwise.

Now a synchronizing group is primitive (i.e. preserves no non-trivial equivalence relation), as we can see from the graph-theoretic interpretation by observing that an imprimitive group preserves a complete multipartite graph. Also, a synchronizing group is basic (in the O’Nan–Scott classification), since a non-basic graph preserves a Hamming graph. So O’Nan–Scott tells us that such a group is affine, diagonal or almost simple.

Regular subgroups

While I was in Shenzhen earlier this month, I was given a preprint by Qi Cai and Hua Zhang showing that, for groups of affine type, synchronization and separation are equivalent. Just before I left, Mohammed Aljohani had told me that the same is true for groups of diagonal type with two socle factors.

There is in fact a common approach to these two results. Suppose that the group G has a regular subgroup H. This means that there is a unique element of H mapping any given point of Ω to any other. Choosing a fixed element α of Ω to correspond to the identity, we can let the element αh correspond to h, for any h in H. Thus we identify Ω with H. Now the following two propositions are straightforward to prove:

Proposition 1 If A and B witness non-separation, then A−1 and B give an exact factorisation of H (this means that any element of H is uniquely expressible as xy with x in A−1 and y in B).

Proposition 2 If A and B give an exact factorisation of H, then the sets Ab for b in B form a partition of H, and this partition and the subset B witness non-synchronization.

These results come close to showing that synchronization and separation are equivalent for groups with regular subgroups; but there is that pesky business about the inverses which I can’t get around in general. But there is a special case where everything works fine. Note that a G-invariant graph must be a Cayley graph for the subgroup H (admitting the right action of H as automorphisms). If any such graph also admits the left action of H, then A being a clique implies that A−1 is a clique, and so the gap is closed. This is the case if G contains both the left and right actions of H, which is true in the 2-factor diagonal case. It is also true in the abelian case, since these actions are then the same. But in a group of affine type, the translation group is an abelian regular subgroup; so we recover the above special cases.

Diagonal groups

It is also the case that diagonal groups with k factors in the socle, for k > 2, are necessarily non-synchronizing. This, it turned out, had already been proved by Pablo Spiga, but the manuscript had been lost, so I had to re-do his arguments myself. I do not want to go through it here, since defining the diagonal groups is a moderately complicated business; but I want to mention a remarkable feature of the proof.

There is a natural graph associated with a diagonal group, which is the union of k overlapping copies of a Hamming graph, or can be regarded as a Hamming graph with some “diagonal edges” added. This is closely related to some work Cheryl Praeger and Csaba Schneider discussed at the Shenzhen conference. It is possible to show that, for a diagonal group with k simple factors T in the socle, where k > 2, this graph has clique number and chromatic number equal to |T|.

For the clique number, this is easy to see; the cliques are visible in the Hamming graphs (which have dimension k−1 over the alphabet T). The trick is to show that the chromatic number is also equal to |T|, by colouring the graph using T as the set of colours. For k even, there is a simple direct rule for the colouring; but for k odd, this requires the truth of the Hall–Paige conjecture, fairly recently proved.

The Hall–Paige conjecture

A complete mapping on a group G is a bijection φ from G to itself with the property that the map xxφ(x) is also a bijection. The latter map, which I will call ψ, is also called an orthomorphism of G.

The existence of a complete mapping has the effect of producing a Latin square orthogonal to the Cayley table of G. And now we see the relevance to non-synchronization. For the case of three factors, the graph referred to above is just the Latin square graph associated with the Cayley table of G (the vertices are the cells, and are joined if they are in the same row or column or have the same entry), and a Latin square orthogonal to the Cayley table gives a proper colouring of this graph with |G| colours.

Hall and Paige conjectured that a group has a complete mapping if and only if its Sylow 2-subgroups are not cyclic. They proved the necessity of the condition, and its sufficiency for alternating groups. Wilcox reduced the proof of the conjecture to the case of simple groups, and dealt with groups of Lie type except for the Tits group. Evans did this group and also all the sporadic simple groups except for J4, which was handled by Bray. Thus the conjecture is proved, the only small problem being that John Bray has not yet published his proof.

Conclusion

Groups which are synchronizing but not separating are very rare. We have one infinite family of examples, and one sporadic example, and that is all.

But these recent developments show that such a group must be almost simple. So at least we know where they are hiding!

Advertisements

About Peter Cameron

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

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.