John Bamberg

Spreading groups

This is a follow-up to the work some of us at UWA have been doing on subproblems to do with the “synchronising hierarchy” of permutation groups. In an earlier post, we announced the discovery of synchronising groups of diagonal type.

The definitions of synchronising/separating/spreading 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.

Next, a permutation group $G\leqslant \mathrm{Sym}(\Omega)$ is non-separating if there exist two subsets $A, B$ of $\Omega$ (other than singleton sets and $\Omega$ ) satisfying $|A| \cdot |B|=|\Omega|$ , for which $|A^g \cap B| = 1$ for all $g \in G$ . A separating group is non-non-separating. Every separating group is synchronising. There exist synchronising groups that are not separating, but they are rare. For an example, take the classical groups $P\Omega(5,p)$ for $p$ prime, in their natural action. By a result in finite-geometry, it is impossible to partition the ambient polar space into ovoids, and through many interesting connections between finite geometry, graph theory, and permutation groups, we get the result.

Another class of permutation groups are the spreading groups. a permutation group $G\leqslant \mathrm{Sym}(\Omega)$ is non-spreading if there exists a nontrivial multisubset $A$ of $\Omega$ , and a subset $B$ of $\Omega$ satisfying $|A|$ divides $|\Omega|$ , and for which $|A^g \cap B| = |A||B|/|\Omega|$ for all $g \in G$ . Spreading groups are separating, and are linked to results on the maximum length of a reset word for finite state automata. Moreover, every 2-set transitive group is spreading, and so we have the following Venn diagram:

We now explain what the orange and violet regions mean. There is one area we have not drawn in, and that’s the class of $\mathbb{Q}I$ groups and they lie between spreading and 2-set transitive. Indeed, one of the big open problems in this area is whether spreading and $\mathbb{Q}I$ are equivalent.

Recall that every synchronising group is primitive of affine, almost simple, or diagonal type. From the recent results of Bray, Cai, Cameron, Spiga, Zhang, and of earlier results on this subject, we have:

For affine groups, synchronising and separating are equivalent.
For diagonal groups, synchronising and separating are equivalent.
For affine groups, spreading and $\mathbb{Q}I$ are equivalent.
A $\mathbb{Q}I$ is 3/2-transitive and hence affine or almost simple.

The violet region in the Venn diagram above represents the affine groups. We know that every affine synchronising group is separating, so the violet region does not cross over to the complement of the separating groups within the synchronising groups.

The orange region in the Venn diagram above represents the diagonal groups. It is nonempty, due to our earlier result. Similar to the affine case, we know that every diagonal synchronising group is separating, so the orange region does not cross over to the complement of the separating groups within the synchronising groups. The shaded orange region is hypothetical: it is possible that there are diagonal spreading groups, and if there were any, then that would deliver a massive breakthrough – there would be spreading groups that are not $\mathbb{Q}I$ .

In recent work with Saul Freedman, we have shown that diagonal groups are not spreading.

Visit to Christchurch, and Bruen chains

Geertrui Van de Voorde from the University of Canterbury (NZ) visited us in November 2022 for two weeks, one week of which I had covid, but we managed to begin a project which would later become a paper (together with Jesse Lansdown). This was continued by my visit to Christchurch in January (supported by Geertrui’s Marsden grant), which was also two weeks, and covid-free this time. Before I write about the research, I would like to first cover the great time I had over the two weeks.

Christchurch is a lovely city, and I was struck by the amazing cycle paths; something that Perth could adapt as a city with similar density. Geertrui was an amazing host (thanks Geertrui!) and has an acute sense for the perfect tourism agenda. First, on the day after I had landed in Christchurch, she took me out for a hike with her family in the beautiful Sumner area, including Godley Head and Taylor’s Mistake (see the pics below).

This was Sunday, and we got down to business on Monday by revisiting everything we had started back in November. The topic was Bruen chains. To keep a long story short, these objects were introduced by Aiden Bruen in 1978 to construct new translation planes. The main idea is that if you derive a translation plane with too many or too few steps, you end up with something you already know: a Hall plane, or André plane. To have a greater guarantee of success, one should take something like (q+3)/2 reguli in a regular spread, such that any two reguli meet in two lines, and any three intersect in the empty set. What we managed to do, was to realise a Bruen chain as a particular clique in a graph that is computationally more amenable for searching. Here is the construction, but I’ll leave the details to the discerning reader. You can find the details in our preprint.

Let $q$ be an odd prime power, and let $\mathcal{E}$ be an elliptic quadric in $PG(3,q)$ . Consider the set of external points: they break into two isometry classes $\mathbb{E}$ , so take one of them. Then fix a point $X$ . Then consider the set of points of $\mathbb{E}$ not equal to $X$ but lying on an external line with $X$ . This will be our set of vertices of our graph $\Gamma_X$ . We join $A$ and $B$ if the intersection of the cones on $X,A,B$ has only singular points. One of our main results is that Bruen chains are in one-to-one correspondence with $(q+1)/2$ -cliques of $\Gamma_X$ .

Curiously, it is known that Bruen chains exist for all prime powers $q$ between 5 and 37 … except for 29! It was shown by Cardinali, Durante, Penttila, and Trombetti that there are no Bruen chains for q=41,43,47,49. We extend their result by showing that there are no Bruen chains for all q between 41 and 97. I’ll finish this story about Bruen chains with a plot of the clique numbers of $\Gamma_X$ . Very weird!

Finally, here are some pictures from my trip midway through my visit of the beautiful vistas in the Mackenzie region (Lakes Tekapo, Pukaki):

Sabbatical in the Netherlands

I am currently on sabbatical, and the longest research visit is occurring now, at the Technical University of Delft. My host is none other than Anurag Bishnoi, who I have long collaborated with. My trip began in mid-April with a delightful conference in Eindhoven: “Combinatorics in Digital Communication”. This conference’s premise was to bring people together from coding theory, information theory, cryptography, finite geometry, and combinatorics. I think this worked really well, and I learnt a lot from the talks given in the areas different to my own. I particularly enjoyed Barbara Terhal’s talk on Quantum Error Correction and the mind-blowing talk by Eitan Yaakobi on DNA storage systems. Here is a photo of TU Eindhoven:

Right now, I’m stationed in Delft (the Netherlands), and enjoying just getting to know one place for a while. Last week, Ferdinand Ihringer (U. Ghent) and Valentina Pepe (La Sapienza) visited, and we had many vibrant discussions on a range of hot research topics. Hopefully some of theses leads will amount to something, but it was at least important to brainstorm together and nut out a few things, and in particular, to try a few things that don’t work. Here is a photo of Valentina and Anurag in deep thought:

I also went along to a net session for a cricket team in Rotterdam, that Anurag is a member of. It suffices to say that my batting was better than my bowling.

I have one more week left, and I’ll be catching up with Krystal Guo (VU Amsterdam) next week, before taking some private days with my family to do some sight-seeing in the area. A big thanks to Anurag who has shown me the best of the Netherlands: the Indian food!

Postscript: I also should blog later about my visit to Christchurch, NZ, earlier this year.

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.

Another postdoc position

Gordon, Michael, and I are currently advertising a 2.5 year postdoc position to work on the ARC Discovery Project “The synchronisation hierarchy of permutation groups” in the CMSC at The University of Western Australia. Applicants should have a PhD in mathematics and a background in permutation groups and/or finite geometry.

The deadline is the 28th of February, 2020.

Details of how to apply can be found at

http://external.jobs.uwa.edu.au/cw/en/job/503992/research-associate-permutation-groups

Irsee (Day 4 and 5)

Thursday began with my own talk, which I had spent hours over-preparing all week! I think it went well, and it was followed by talks in related topics by my student Jesse Lansdown and Ferdinand Ihringer. Overall, it was a very enjoyable list of talks, and in topics I’ve had a dabble in. Thursday evening saw the FinInG group spend a few hours becoming acquainted with Git and BitBucket.

Friday began with a marvellous talk by Kai-Uwe Schmidt … again, on a topic I was familiar with. I missed one of the sessions for another research session with Anurag Bishnoi and Ferdinand Ihringer, but the last session finished the conference off nicely with three nice talks by Gabor Korchámros, Daniele Bartoli, and Simeon Ball. We then had a conference dinner, comprising not only of food, but of impromptu piano performances by Giovanni Longobardi and Jan De Beule. Michel Lavrauw gave an interesting stat during his conference dinner speech: there were 73 attendees and 58 talks! So it was indeed a busy conference.

Irsee (Day 2 and 3)

I’ve been extremely busy at this conference, and so a summary of the past two days comes at once. On Tuesday, we had Dieter Jungnickel’s talk on Hamada’s Conjecture and related things. We then had “design-like” talks for most of the day. I did miss one of the sessions where I had some urgent work to do, but I very much enjoyed the talks that I did attend. In particular, Jim Davis’ talk was spectacular, on difference sets of groups of order 256. Tuesday evening was particularly special with Jan De Beule playing a mini-concert as bookends to an ICA medal presentation. Jan played a set of three Chopin numbers that I knew well, and finished with Beethoven’s Adagio Cantible (2nd movement). Yesterday (Wednesday), we had a short day, for the afternoon was free time. We had three talks: Joachim Rosenthal, Karen Meagher, and Leo Storme. All of these talks were interesting to me, hence why I’m so exhausted! After lunch, a bunch of us went for a long walk out into the local farmlands. On the way back from a small tea/wine/beer-house, it rained a bit, so I was feeling a little wet and wind-swept when we got back. In the evening, we (Michel Lavrauw, Jan De Beule, and I) had our FinInG-demo, which was a success, apart from some problems with the projector at the beginning. Many of the attendees came along, and I hope, we will have some new users of our finite geometry package soon.

Here is a photo from the walk:

Irsee (Day 1)

I am currently at the fifth Irsee conference on “Finite Geometry” which takes place in at the old monastery in the village of Irsee (Germany). The first day consisted mainly of talks on maximum distance rank codes, which is currently a hot topic in finite geometry. The plenary lecture on this topic, by Olga Polverino, was fantastic, and the contributed talks in the morning session continued the theme. One of the main themes was “John Sheekey” who could not attend, but was probably mentioned two-score times in the morning session. I even learnt of a new expression: the Sheekey connection. It has a ring to it! Some talks I expecially enjoyed were by Giuseppe Marino and Geertrui van de Voorde.

The afternoon session was on finite semifields, bent functions, and related objects. Then the late afternoon session was a bit more random, but I particularly enjoyed the talks by Sudhir Ghorpade and my close colleague Tomasz Popiel.

After a long of day of interesting talks and many many research meetings, I was exhausted. Four more days to go!

Guest post: Why mathematicians do not solve the Open Access Problem?

The following is a guest post by Stephen Glasby.

In July 2012 Tim Gowers wrote A new open-access venture from Cambridge University Press. The idea of arXiv overlay journals has been around for over 4 years, and there are very powerful ideas to support them. Why then does the mathematical community seem reluctant to support them?

Let me begin with a some history and context.

It is hard to overstate the importance of Mathematics Reviews (MR) and Zentralblatt (Zbl). Although Zbl had been reviewing journal articles since 1931, antisemitic pressures at that time led to the establishment of MR in 1940 (the last printing of MR was 2012). The electronic database MathSciNet, established in 1996, has made the printed versions of both MR and Zbl obsolete. We all know that MathSciNet is not merely a list of reviews: it contains links to journal articles, authors, references, citations, and related reviews. MR employs about 100 people in An Arbor, Michigan, and these few people have transformed the way we do mathematics. Mathematics is fortunate to have both MathSciNet and the arXiv. The natural sciences, by contrast, do not have an equivalent of MathSciNet!

While MathSciNet could be further improved and extended, I will change tack and now focus on the Open Access Problem: that it is not free to publish/access/reuse research papers. This larger problem affects all of Mathematics. The Open Access Problem applies more generally to the sciences and medicine and it is described, with some solutions, in this broad context in the illustrated video. (Who owns your personal data is a very large issue.) Let us focus on mathematical Open Access problems and solutions, for mathematics has both the arXiv and MathSciNet. When we locate relevant research using MathSciNet, increasingly often, clicking on “article” to download the journal article shows that the article is “owned” by a publishing company, or a learned society, and downloading can cost US$40, or an annual subscription! This is a growing and lasting problem for mathematics, retarding both future research and proper referencing of past research.

One solution to the Open Access Problem, suggested by Tim Gowers and others, is to use arXiv overlay journals. Why is this practical solution not being implemented broadly? Such journals exist, but there are relatively few. I argue below that the solutions are easily implemented, and require essentially no additional effort, and have huge potential benefits. But they do require the mathematical establishment to embrace the change. Let us first look at problems and solutions before addressing the resistance to change.

There are many models for peer-reviewed Open Access publication, these have names such as Platinum, Gold, Diamond, and Green, but non-experts forget the definitions or use non-standard definitions. It seems better say whether articles are free to Publish, Access, Reuse, Typeset and Edited, etc. We will focus on journals that are free to Access (i.e. read and print), and free (or very cheap) to Publish and Reuse (i.e. link to, or republish, content). Clearly Typesetting and Editing are lesser problems for mathematics than the accessibility of past research.

Problem 0: A small fraction of new mathematical research is put on the arXiv before it is published, and this will remain the case for some time.

Solution: Establish journals that do publish on the arXiv, see Problem 2. The arXiv was established in 1991. It has 1.2M papers up to 2016, most are physics, and about 280,000 are in mathematics. MathSciNet lists 2.1M reviews from 1991-2016 so I estimate (very crudely) that about 1/7 of mathematical research papers are on the arXiv. The number of arXiv papers was doubling every 4 years, but this rate is slowing down. It is possible that in a decade the majority of math research papers will have preprint versions posted on the arXiv.

Problem 1: Many of the prestigious journals are owed by publishing companies, or learned societies, which make our research effectively inaccessible because of copyright, and cost of access. The cost of an average mathematics journal is US$1,700/yr and some papers have indefinite copyright. Subscription costs for some journals with shorter copyright periods can cost over US$8,000/yr (e.g. Elsevier’s Nonlinear Analysis).

Solution: Establish new journals that publish for “free” on the arXiv, see Problem 4. The research will be accessible and free (to read) in perpetuity. Moreover, it will be clear that the paper has been peer-reviewed, and MathSciNet can link to the refereed arXiv paper.

Problem 2: New journals have lower impact factors than expensive established journals, and academics must publish in high impact journals to be promoted, to obtain grants, etc.

Solution: If all mathematicians put the refereed and corrected version of their paper on the arXiv (even if it lacked the journal formatting) then this problem would be solved. As remarked above, this is not likely to happen soon. Another solution is to ask the editors of Journal X to resign en masse and establish a new journal called Journal EX (for Electronic Journal of X). The editors will review to the same standard as before so Journal EX must have the same academic standing as Journal X, see Problem 5.

Problem 3: Journal X has Editorial Management software, the new Journal EX would require similar software to be developed and maintained.

Solution: Free Editorial Management software already exists. Learned societies, or grants, or nominal “Publication Fees” could subsidize the cost of maintaining and further developing the software, see Problem 4.

Problem 4: There are unavoidable costs that must be born by the arXiv and MathSciNet. Who will pay for these?

Solution: There are many solutions here. The major costs would be refereeing and editing, but we perform these gratis, and distribution via the arXiv is close to free, so that leaves copy editing and maintaining MathSciNet databases. A growing number of universities have pledged to support fees for Open Access publication for articles written by their faculty, see this link. A nominal Publication Fee could be levied from author(s), or author(s) may be required to donate a nominal sum to a fund to maintain the arXiv, to keep MathSciNet subscriptions low, and to develop and maintain Editorial Management software, and maybe fund some copy editing. (The 2017 pricing for MathSciNet Consortia ranges from US$339.00 per institution to US$11,887.00: a fraction of library subscriptions costs for mathematics journals.)

Problem 5: Editors of high impact journals need not be concerned about egalitarianism and Open Access. Why should they resign en masse from the board of Journal X and form a new Open Access Journal EX?

The three main problems are: critical mass, will, and inertia. The work load of a editor is independent of whether s/he works for a journal that: exploits mathematical creativity, or one that fosters creativity (by rapid, free, accessible publications). I argue that editor intransigence is a major impediment to Open Access publication. I know of cases of individual editors whose libraries do not carry key journals because of cost, and yet these editors do not support Open Access. Why? Gowers suggested that a number of mathematicians have an emotional objection to Open Access publication.

A minority of mathematicians are editors for Open Access journals. Is this minority more concerned about the health of mathematical research than the majority? or are there cogent reasons for maintaining the status quo? I have tried to make new arguments for Open Access publishing in mathematics. A good source for further reading is Tim Gowers blog.

A sad day for blackboards at UWA

Over the next few months, the whole of the Mathematics building at UWA will be refurbished, including air-conditioning on the first floor, a re-design of the administration area, and an overhaul of the surrounding lecture theatres. Weatherburn LT, Blakers LT, and Maths Lecture Room 1, 2, 3 have had their blackboards ripped out, to be replaced with WHITEBOARDS (see the carnage below). I have already given my reservations about this exchange and lost the battle, and I am sure we will regret this move … alas.