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.
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.
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.
Number of mathematicians highly familiar with the problem:
a majority of those working on a specialized topic (≈10)
Number 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%