Synchronization and all that, 2

The story I told in the last post is not over.

The recent development is that we spotted a mistake in the paper. An easy mistake to make: we had simply used the symbol n in two different places with different meanings, and then proceeded to get them confused.

The fix required arguments considerably longer than the ones we had given. The fact that we were able to fix the proof reasonably quickly shows the power of Delsarte’s ideas for studying association schemes. His thesis (published in the Philips Research Reports in 1973) is the foundation for much subsequent work in both coding theory and combinatorial design theory.

Anyway, in the course of this fix, we discovered that we had left out an example. This doesn’t affect our conjectures, which are asymptotic: they assert that, for fixed k, for large enough n,the symmetric group of degree n acting on k-sets is non-separating if and only if a Steiner system S(t,k,n) exists for some t with 0 < t < n.

The main change is that, for k = 4, “large enough” should mean “at least 10” rather than “at least 9”.

The reason is as follows. Consider the graph whose vertices are the 4-subsets of {1,…,9}, two vertices joined if they intersect in 1 or 3 points. Then the clique number and the chromatic number of this graph are both equal to 9; and hence S9 acting on the 135 vertices of the graph is non-synchronizing (as explained in the preceding post).

I leave as an exercise the proof that the graph has clique number 9. (Your job is to find nine subsets of {1,…9}, each of size 4, and having the property that any two meet in 1 or 3 points.)

The fact that the chromatic number is 9 was proved (in different language) by Breach and Street in 1988. They showed that the 4-subsets of a 9-set can be partitioned into 9 copies of the Steiner system S(3,4,8), each omitting one of the nine points. (They called such a configuration an “overlarge set” of Steiner systems, as opposed to a “large set”, where each Steiner system uses all of the points.)

Their proof, as I recall, was in part computational. But a couple of years later, Cheryl Praeger and I were able to give a conceptual proof, based on the remarkable geometric concept of triality, specifically over the field of 2 elements. Here is a brief summary. I restrict to the 2-element field, though much of this works for an arbitrary field.

Consider the quadratic form

x1x2+x3x4+x5x6+x7x8.

It defines a quadric consisting of 135 points of the 7-dimensional projective space over GF(2). The maximal subspaces contained in this quadric are “solids” (3-dimensional subspaces), and fall into two families, where two solids are in the same family if they intersect in a line or are disjoint, and in different families if they intersect in a plane or a point. There are 135 planes in each family. Also there are 1575 lines on the quadric.

Consider the quadric as an incidence structure, where the incidence between points, lines, and solids is inclusion, and two solids are incident if they intersect in a plane. (We regard incidence as a symmetric relation, so that a line is incident with a point if and only if the point is incident with the line.) It turns out that this structure has some additional, unexpected symmetries: we can permute cyclically the sets of points, solids in the first family, and solids in the second family, while preserving the family of lines and the incidence relation. This symmetry is the “triality” map on the quadric.

Now here is a concrete realisation of the quadric. As our 8-dimensional vector space V, we take all the binary words of length 9 with even weight. (These are the words orthogonal to the all-1 word with respect to the usual inner product, so they do form a subspace.) Now it can be shown that the function mapping v to half the weight of v mod 2 (that is, words of weight 0, 4 and 8 map to 0, words of weight 2 and 6 map to 1, in GF(2)) is a quadratic form on V, equivalent under linear transformation to the one given above. The quadric consists of the (9 choose 4)+(9 choose 8)=135 wordds of weight 4 or 8. The 9 words of weight 8 form an ovoid on the quadric, a maximal set of points with no pair lying on a line of the quadric. (The third point on the line joining two points of weight 8 has weight 2.) The stabiliser of the ovoid is the symmetric group S9, so by counting we find that there are 960 ovoids.

Applying the triality map turns an ovoid into a spread, a set of 9 pairwise disjoint solids (necessarily all from the same family) covering each point of the quadric.

Now what does a solid look like in our interpretation? It is a 4-dimensional vector subspace of V, all of whose elements have weight 4 or 8 (since it is contained in the quadric). It is easy to see that such a subspace must consist of the zero vector, a word of weight 8, and 14 words of weight 4 forming the blocks of a S(3,4,8) on the support of the word of weight 8. So each of the 9 solids in a spread contains one of the nine words of weight 8 and 14 of the 126 words of weight 4, and we have our large set of Steiner systems.

Now the classification up to isomorphism is found by writing down two beautiful examples (each with a doubly transitive automorphism group), counting how many copies of each there are (the index of its automorphism group in the symmetric group), and checking that these numbers add up to 1920 (the number of images of ovoids under the triality map and its inverse).

This was presented at the 1988 Italian combinatorics conference in the beautiful town of Ravello, and published in the conference proceedings. The publisher was a small outfit called the Mediterranean Press. I believe I heard a rumour that they were no longer in business. So, with Cheryl’s agreement, I have posted a scan of the paper here. (The paper by Breach and Street is in the Journal of Combinatorial Mathematics and Combinatorial Computing in 1988.)

A final note: this paper is also referred to in my notes On doing geometry in CAYLEY.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in doing mathematics, exposition 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 )

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