Monday 10 September 2007

co.combinatorics - Diagonally-cyclic Steiner Latin squares

A Steiner triple system is a decomposition of $K_n$ into $K_3$, such as $S={013,026,045,124,156,235,346}$. Steiner triple systems give rise to a Steiner Latin squares, such as $L$ below.



[L=left(begin{matrix}
0 & 3 & 6 & 1 & bf{5} & 4 & 2 \\
3 & 1 & 4 & 0 & 2 & bf{6} & 5 \\
6 & 4 & 2 & 5 & 1 & 3 & bf{0} \\
bf{1} & 0 & 5 & 3 & 6 & 2 & 4 \\
5 & bf{2} & 1 & 6 & 4 & 0 & 3 \\
4 & 6 & bf{3} & 2 & 0 & 5 & 1 \\
2 & 5 & 0 & bf{4} & 3 & 1 & 6
end{matrix}right)]



We define $L=(l_{ij})$ by $l_{ii}=i$ for all $i$ and $l_{ij}=k$ whenever $ijk$ is a triangle in $S$.



Note: Typically, Steiner Latin squares are viewed in an algebraic context and referred to as "Steiner quasigroups" -- Steiner quasigroups correspond to isomorphism classes of Steiner Latin squares, whereas for this question, I'm interested in the "labelled" case.



In some instances, such as $L$ above, the Latin square obtained is a diagonally-cyclic Latin square. That is, $L$ satisfies the identity $l_{(i+1)(j+1)}=l_{ij}+1 pmod n$, for all $i,j in mathbb{Z}_n$, where the indices are taken modulo $n$ also. I've highlighted (in bold) an orbit of an entry of $L$ under this symmetry.




Which Steiner triple systems give rise to diagonally-cyclic Steiner Latin squares?




The above question was my original question, however, as Douglas Zare points out, these are precisely the Steiner triple systems that admit the automorphism $(0,1,ldots,n-1)$.



Proof: If $L$ is a Steiner Latin square derived from $S$ then $(i,j,k)$ is an entry in $L$ if and only if it $ijk$ is an element of $S$. For $L$ to be diagonally-cyclic, if $(i,j,k)$ is an entry of $L$ then so is $(i+1,j+1,k+1) pmod n$. Therefore $(i+1)(j+1)(k+1)$ is also an element of $S$. The converse is true by definition.



Since that was such an easy task, lets look at a (hopefully) more interesting question.



Let $L=(l_{ij})$ be a diagonally-cyclic Steiner Latin square. Let $sigma$ be the permutation defined by $sigma(j)=l_{0j}$ (that is, the first row of $L$). Then $sigma$ is an orthomorphism of $mathbb{Z}_n$. That is, $sigma$ is a permutation of $mathbb{Z}_n$ and the map defined by $i mapsto sigma(i)-i pmod n$ is also a permutation of $mathbb{Z}_n$.



In the above example $sigma=(0)(13)(26)(45)$.




Which orthomorphisms of $mathbb{Z}_n$ arise from diagonally-cyclic Steiner Latin squares?


No comments:

Post a Comment