# Is there a complete set of mutually disjoint trios in a (5,8,24) Steiner system?

Question: In a (5,8,24) Steiner system, is it possible to find a set of 759/3=253 trios such that every octad lies in exactly one of these trios?

Background information:

If $X$ is a set of size 24, then a (5,8,24) Steiner system is a set of subsets of $X$ of size 8, called octads, such that every subset of $X$ of size 5 is contained in a unique octad. It is known that a (5,8,24) Steiner system is unique up to a permutation of $X$. Fix such a Steiner system $S$.

It is easy to calculate that there are $\binom{24}{5}/\binom{8}{5} = 759$ octads in $S$. A trio is a set of 3 mutually disjoint octads covering $X$. It is known that every octad lies in exactly 15 trios and hence there are $759 \cdot 15 / 3 = 3795$ trios in $S$.

-

Yes, such a family can be constructed. Let us begin by constructing the Steiner system as supports of words of weight 8 in the extended Golay code. Here the $[23,12,7]$ binary Golay code $G$ is the ideal $G:=R\cdot p$ of $R=F_2[x]/\langle x^{23}+1\rangle$ generated by the factor $$p(x)=1+x+x^5+x^6+x^7+x^9+x^{11}\mid x^{23}+1.$$ We view polynomials as strings of 23 bits simply by listing their coefficients, and index bit positions with the exponents. The code $G$ is extended to a code $\overline{G}$ of length 24 by adding an overall parity bit to the end - call this last position $\infty$ with a view of matching the bit positions with points of the projective line over $F_{23}$. So the polynomial $p(x)$ corresponds to a word of weight 7 in $G$, and in the extended code $\overline{G}$ it becomes a word of weight 8 giving the octad $o_1=\{0,1,5,6,7,9,11,\infty\}$.

Being an ideal $G$ is stable under multiplication by $x$, i.e. the 23-cycle $\alpha(i)\equiv i+1\pmod{23}$ (acting on the bit positions or the set of exponents of $x$, whichever way you prefer). Being an ideal $G$ is also stable under the Frobenius map = squaring. As the order of $2$ modulo $23$ is equal to $11$ this breaks the bit positions/exponents into two 11-cycles: $$\beta=(0)(1,2,4,8,16,9,18,13,3,6,12)(5,10,20,17,11,22,21,19,15,7,14)(\infty)$$ or $\beta(i)\equiv2i\pmod{23}$. We view both of these as permutations in $Aut(\overline{G})\cong M_{24}$. They are both in the point stabilizer of $\infty$.

We see that $\beta\alpha\beta^{-1}=\alpha^2$ ($i\mapsto i+2\pmod{23}$). Therefore $\beta$ normalizes the group $\langle\alpha\rangle$, and together they generate a group $H= \langle \alpha,\beta\rangle\cong C_{23}\rtimes C_{11}$ of size $11\cdot23=253$. It is easy to see that $H$ does not fix any octads. This is because $M_{24}$ acts transitively on the set of $759=3\cdot11\cdot23$ octads, and neither $11^2$ nor $23^2$ divide the order $|M_{24}|$. Therefore the octads are partitioned into three full size orbits of $H$.

With the aid of CAS (I used Mathematica) it is easy to generate all the octads and list all those that have supports disjoint from $o_1$. There are exactly 30 of those (15 pairs, as predicted by your data telling that $o_1$ is a member of exactly 15 trios). The method that I used in generating them spewed out $o_2=\{3,4,8,10,16,19,21,22\}$ as the first octad of this kind. Because $H$ stabilizes $\infty$ it is immediately clear that $o_2$ does not belong to the orbit $H\cdot o_1$. It is straightforward to check that the octad complementing this trio $o_3=\{2,12,13,14,15,17,18,20\}$ does not belong to the orbit $H\cdot o_2$. Thus all the octads belong to exactly one of the orbits $H\cdot o_j, j=1,2,3$. For any $\gamma\in H\le M_{24}$, the octads $\gamma(o_j),j=1,2,3$ obviously form a trio. Thus together these 253 trios cover all the octads as requested.

This solution is admittedly somewhat unsatisfactory in the sense that at a critical point, $o_3\notin H\cdot o_2$, I used brute force. It would not surprise me, if the same thing happened to any trio containing $o_1$. I verified this for one other pair of octads $o_2',o_3'$ completing $o_1$ to a trio. The simple idea of using the group $H$ is my key input. After finding $o_2$ the rest could probably be done without the aid of a computer. After all, the group $H$ consists of affine mappings from $F_{23}\cup\{\infty\}$ to itself of the form $i\mapsto ui+v$, where $u$ is a quadratic residue modulo $23$ and $v\in F_{23}$ is arbitrary.

Edit: Ted already noticed that I had jumped to a 'conjecture' on too scant data. Today I checked out all the 15 trios including $o_1$. The exhaustive tally is that 9 out of those work the same way as the example trio $\{o_1,o_2,o_3\}$. For the remaining 6 trios the two complementary octads actually belong to the same orbit of $H$, and hence those trios cannot be used to solve Ted's question. At least not using this particular conjugate of $H$ (another one may work).

-
Nice answer. I'm accepting but I'm still wondering if there's a way to avoid the computer and at the same time that any $o_2$ disjoint from $o_1$ works. It would be enough to check, for a fixed trio $\{o_1, o_2, o_3\}$, that there is no element of order 11 or 23 which fixes a point of $o_1$ while sending $o_2$ to $o_3$. – Ted Dec 27 '11 at 0:23
Actually, it turns out that the statement in my comment above is not true! Not any choice of octads works. On page 8 of www.maths.qmul.ac.uk/~raw/FSG/notes5.pdf , diagram (5.10), we have an identification of the 24 points of Conway's Miracle Octad Generator (MOG) with the 24 points of the projective line over $F_{23}$, such that $PSL(2,23)$ becomes a subgroup of $M_{24}$. In the MOG, any 2 columns forms an octad. With this identification, the transformation $x \mapsto x/2$ takes the 3rd and 4th columns to the 5th and 6th columns, while fixing $\infty$ which is in the second column. – Ted Dec 30 '11 at 5:54
@Ted: 9 out of 15 work, 6 won't. I was just lucky early on. Sorry about giving you misinformation. – Jyrki Lahtonen Dec 30 '11 at 19:40
I thought the conjecture was reasonable, no worries :) The reason I asked this question because I wanted to draw a diagram of all the octads, and this construction allows me to fit everything in a 23 by 11 array of MOGs, each one of which contains a trio in three different colors. – Ted Dec 31 '11 at 4:03