# 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:

- If you have a Steiner system \(S(t,k,v)\), you can make a Steiner system \(S(t-1, k-1, v-1)\) by choosing all blocks with a certain number, and deleting that number.
- Steiner systems follow divisibility rules: \(S(t,k,v)\) only can exist if \({k-i \choose t-i}\) divides \({v-i \choose t-i}\) for all \(i \in \{0,\cdots,t-1\}\).

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

- Some values of \((t, t+1, v)\) have no associated Steiner system:
- “☠️”, “❌”, “❎”, “✖”: No Steiner system can exist because of divisibility rules.
- ”-“: These values do not form a valid Steiner system; \(t\) must be smaller than \(v\).
- “DNE”: There are no Steiner systems S(4, 5, 15) or S(4, 5, 17), as computationally verified here.

- Some values do have a Steiner system:
- “
**Trivial**”: There is always a Steiner system \(S(t,k,k)\) with one block including all numbers from 1 to k. - “
**Pairs**”: If \(v\) is even, then pairing all numbers from 1 to v forms a Steiner system \(S(1, 2, v)\). - “
**✔️**”: There are Steiner systems at each \(v\) that satisfies the divisibility rules, as shown for t=2 and for t=3. - “
**M**\(_{12}\)”, “**M**\(_{11}\)”: The Steiner system S(5, 6, 12) corresponds to the Mathieu group**M**\(_{12}\), which induces S(4, 5, 11) and Mathieu group**M**\(_{11}\). - “
**PSL\(_2\)(23)”**: There is a known Steiner system S(5, 6, 24), as described here and here, which induces S(4, 5, 23).

- “
- For the entries marked “
”, we simply don’t know if there’s a Steiner system here!*???*

\(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\) | ☠️ | ❌ | ☠️ | ❎ | ☠️ | ??? |