Synchronising diagonal type groups exist

Recently, Michael Giudici, Jesse Lansdown, Gordon Royle and I have constructed a couple of examples of synchronising groups that are radically different from the known examples. You can find the details in our preprint here.

What is a synchronising group?

The definition came about from the study of synchronising words for finite-state automata. Motivated by the Černý Conjecture on the length of reset words in synchronising automata, Arnold and Steinberg, and independently Araújo, introduced the notion of a synchronising group. We say that a permutation group $G$ is synchronising if for any non-bijective transformation $f$ , the transformation semigroup $\langle G, f\rangle$ is synchronising; that is, it contains a constant map (aka. reset word). It was observed in Peter Neumann’s seminal article in 2009 that a synchronising permutation group is primitive. Moreover, the possible O’Nan-Scott types for a synchronising group are heavily restricted. We have just three types: (i) Affine, (ii) Almost Simple, (iii) Diagonal. There are many examples in the first two cases known, but it wasn’t known until now whether the third case was nonempty.

What was known about synchronising diagonal groups?

Due to the fine work of many people, the shape of a diagonal type group had been whittled down. The diagonal group $D(T,n)$ is defined as follows. Firstly, $T$ is a nonabelian simple group, and $n$ is a positive integer at least 2. The domain for our group action will be the direct product $T^{n-1}$ . The group $T^n$ acts diagonally on this set in the following action:

$(t_2,\ldots,t_n)^{(x_1,\ldots,x_n)}=(x_1^{-1}t_2x_2,\ldots, x_1^{-1}t_nx_n)$

We can include inner automorphisms acting identically on each coordinate in $D(T,n)$ , we can have permutations of the coordinates, and also a funny involution (which I won’t describe here). These generate the largest diagonal type primitive group on this domain, and a diagonal primitive group is a subgroup of $D(T,n)$ containing the socle $T^n$ .

Bray, Cai, Cameron, Spiga, Zhang (arXiv, 2018) showed that synchronising diagonal type groups have $n=2$ . Moreover, they showed that “synchronising” and “separating” are equivalent for diagonal type primitive groups. In particular, if $T$ as an exact factorisation, then $T\times T$ is non-synchronising. For more, see Peter Cameron’s excellent post on this major breakthrough.

The examples

Take $T=PSL(2,q)$ , where $q\in\{13,17\}$ . These are the smallest values for which it was not known if the group $T\times T$ acting in diagonal action was synchronising or not. (For $q\equiv 0,2,4\pmod{4}$ , and $q\in\{5,29\}$ , we have an exact factorisation of $PSL(2,q)$ . The case $q=9$ was shown to give a non-synchronising example). Then we show that $G=T\times T$ acting on $T$ in diagonal action is synchronising. To show this, we needed to show that the action is separating and apply Bray, Cai, Cameron, Spiga, Zhang’s result that synchronisation and separation are equivalent for diagonal actions. To show that these groups are separating required us to show that every $G$ -invariant undirected graph on $T$ has $\alpha\omega\ne |T|$ where $\alpha$ and $\omega$ are the maximum sizes of a coclique and clique (respectively) of the graph. This in turn needed the theory of association schemes, and in particular, design-orthogonality, to reduce the problem to the analysis of just a small number of graphs.