Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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).

share|improve this answer
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.