Large Steiner Systems

Construct an $(n,q,r)$-Steiner system with $n > q > r > 5$, $r < 10$, and $n < 200$.

Notability: Solid result

Solved: No

Contributor: Kunal Marwaha

Field: Combinatorics

On this page:

About the problem Attempts by AI AI prompts Mathematician survey

About the problem

Steiner systems are highly-symmetrical combinatorial objects with applications in experimental design and error-correcting codes. They have been actively studied since the mid-1800s.

The formal definition is simple: given a set $S$ of size $n$, an $(n,q,r)$-Steiner system is a set of $q$-sized subsets of $S$ such that every $r$-sized subset of $S$ is contained in exactly one of the $q$-sized subsets.

Perhaps surprisingly, no example of a Steiner system with $r > 5$ is known, despite a theorem, proven in 2014, that many such examples do exist. While there is no guarantee that an example exists with $n < 200$ and $5 < r < 10$, there is also no reason to expect this not to be the case. It seems unlikely that even an optimized brute-force search could solve this problem, with a novel conceptual approach likely required.

Warm-up: we ask for a Steiner system with $r = 5$. Such examples are well-known and AI systems are readily able to produce them.

Full write-up

Attempts by AI

We have evaluated the following models on this problem. “Warm-up” refers to an easier variant of the problem with a known solution.

Model

Problem

Solved

Logs

GPT-5.2 Pro

Warm-up

Yes

GPT-5.2 Pro

Full Problem

Gemini 3 Deep Think

Full Problem

AI Prompts

Warm-up

Let [n] be the elements {1,...,n}. Call T a q-subset of [n] if T⊆[n] and the size of T is q.

A (n,q,r)-Steiner system S is a set of q-subsets of [n] such that every r-subset of [n] is contained in exactly 1 element of S.

Your task is to find a (n,q,r)-Steiner system for any n > q > r, r = 5, and n < 200.

Return the Steiner system as a multi-line string. In the first line, specify n, q, and r exactly as #n,q,r. Each subsequent line lists the elements of a q-subset in S separated by whitespace. For example, the below is a valid (7,3,2)-Steiner system.

#7,3,2
1 2 4
2 3 5
3 4 6
4 5 7
5 6 1
6 7 2
1 3 7

Full problem

Let [n] be the elements {1,...,n}. Call T a q-subset of [n] if T⊆[n] and the size of T is q.

A (n,q,r)-Steiner system S is a set of q-subsets of [n] such that every r-subset of [n] is contained in exactly 1 element of S.

Your task is to find a (n,q,r)-Steiner system for any n > q > r > 5, where r < 10 and n < 200.

Return the Steiner system as a multi-line string. In the first line, specify n, q, and r exactly as #n,q,r. Each subsequent line lists the elements of a q-subset in S separated by whitespace. For example, the below is a valid (7,3,2)-Steiner system.

#7,3,2
1 2 4
2 3 5
3 4 6
4 5 7
5 6 1
6 7 2
1 3 7

Mathematician survey

The author assessed the problem as follows.

# of mathematicians highly familiar with the problem: a majority of those working on a specialized topic (≈10)

# of mathematicians who have made a serious attempt to solve the problem: 2–4

Rough guess of how long it would take an expert human to solve the problem: 3–12 months

Notability of a solution: a solid result in a subfield

A solution would be published: in a standard specialty journal

Likelihood of a solution generating more interesting math: fairly likely: the problem is rich enough that most solutions should open new avenues

Probability that the problem is solvable as stated: 60–80%