Steiner Systems

A Steiner system \(S(t,k,v)\) is a collection of k-sized subsets (“blocks”) of the numbers 1 to \(v\). These collections are special because every t-sized subset of the numbers 1 to \(v\) are in exactly one block.

For example, here is a \(S(2,3,7)\) system (also known as the Fano plane):

{1,2,3}
{1,4,5}
{1,6,7}
{2,4,6}
{2,5,7}
{3,4,7}
{3,5,6}

I was introduced to Steiner systems from this review article. There is also good information on Dan Gordon’s page.

Some cool facts about Steiner systems:

Table of \(S(t, t+1, v)\)

Here are the divisibility rules for small \(t\) when \(k = t+1\):

  Divisibility
\(t=1\) \(v \ne 1\text{ mod }2\)
\(t=2\) \(v \ne 0\text{ mod }2\) and \(v \ne 2 \text{ mod }3\)
\(t=3\) \(v \ne 1 \text{ mod }2\) and \(v \ne 0 \text{ mod }3\)
\(t=4\) \(v \ne 0 \text{ mod }2\) and \(v \ne 1 \text{ mod }3\) and \(v \ne 4\text{ mod } 5\)
\(t=5\) \(v \ne 1\text{ mod }2\) and \(v \ne 2 \text{ mod }3\) and \(v \ne 0\text{ mod } 5\)
\(t=6\) \(v \ne 0 \text{ mod }2\) and \(v \ne 0 \text{ mod }3\) and \(v \ne 1\text{ mod } 5\) and \(v \ne 6\text{ mod 7}\)

I’ve listed a table below of small values of \(t\) and \(v\).

  \(t=1\) \(t=2\) \(t=3\) \(t=4\) \(t=5\) \(t=6\)
\(v=1\) - - - - - -
\(v=2\) Trivial - - - - -
\(v=3\) ☠️ Trivial - - - -
\(v=4\) Pairs ☠️ Trivial - - -
\(v=5\) ☠️ ☠️ Trivial - -
\(v=6\) Pairs ☠️ ☠️ Trivial -
\(v=7\) ☠️ ✔️ (Fano) ☠️ ☠️ Trivial
\(v=8\) Pairs ☠️ ✔️ ☠️ ☠️
\(v=9\) ☠️ ✔️ ☠️ ☠️
\(v=10\) Pairs ☠️ ✔️ ☠️ ☠️
\(v=11\) ☠️ ☠️ M\(_{11}\) ☠️
\(v=12\) Pairs ☠️ ☠️ M\(_{12}\) ☠️
\(v=13\) ☠️ ✔️ ☠️ ☠️
\(v=14\) Pairs ☠️ ✔️ ☠️ ☠️
\(v=15\) ☠️ ✔️ ☠️ DNE ☠️
\(v=16\) Pairs ☠️ ✔️ ☠️ DNE ☠️
\(v=17\) ☠️ ☠️ DNE ☠️ DNE
\(v=18\) Pairs ☠️ ☠️ DNE ☠️
\(v=19\) ☠️ ✔️ ☠️ ☠️ DNE
\(v=20\) Pairs ☠️ ✔️ ☠️ ☠️
\(v=21\) ☠️ ✔️ ☠️ ??? ☠️
\(v=22\) Pairs ☠️ ✔️ ☠️ ??? ☠️
\(v=23\) ☠️ ☠️ PSL\(_2\)(23) ☠️ ???
\(v=24\) Pairs ☠️ ☠️ PSL\(_2\)(23) ☠️
\(v=25\) ☠️ ✔️ ☠️ ☠️ ???
\(v=26\) Pairs ☠️ ✔️ ☠️ ☠️
\(v=27\) ☠️ ✔️ ☠️ ??? ☠️
\(v=28\) Pairs ☠️ ✔️ ☠️ ??? ☠️
\(v=29\) ☠️ ☠️ ☠️ ???