Skip to main content
More interesting question...
Source Link
Douglas S. Stones
  • 4.2k
  • 2
  • 37
  • 53

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?

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?

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?

Source Link
Douglas S. Stones
  • 4.2k
  • 2
  • 37
  • 53

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?