Erdős Problem #722: Steiner systems
Necessary conditions and explicit infinite families, 24 September 2026.
Statement and scope
For fixed $k>r$, do the divisibility conditions \[
\binom{k-i}{r-i}\mid\binom{n-i}{r-i}\quad(0\leq i<r)
\] suffice, for large $n$, for an $r$-$(n,k,1)$ design? Keevash proved that they do. Here we prove the conditions and construct several exact families, including every Steiner triple system order $n\equiv3\pmod6$. The general absorption theorem is not reconstructed.
Double counting every necessary condition
Fix an $i$-subset $S$ of the ground set. There are $\binom{n-i}{r-i}$ $r$-subsets containing $S$. Every block that contains $S$ accounts for $\binom{k-i}{r-i}$ of them. A block covering such an $r$-subset necessarily contains $S$, and no $r$-subset is counted twice. Thus the number of blocks containing $S$ is exactly \[
\lambda_i=\binom{n-i}{r-i}\big/\binom{k-i}{r-i},
\] which must be an integer. In particular the number of blocks is $\binom nr/\binom kr$. For $r=1$, these conditions reduce to $k\mid n$, which is sufficient by partitioning the ground set into $k$-element sets.
A construction for every $n\equiv3\pmod6$
Let $q=2t+1$ be odd and take the $3q$ points $\mathbb Z_q\times\mathbb Z_3$. Division by two is well defined in $\mathbb Z_q$. Use the blocks \[
\{(x,0),(x,1),(x,2)\}\quad(x\in\mathbb Z_q)
\] and, for each unordered pair of distinct $x,y\in\mathbb Z_q$ and each $i\in\mathbb Z_3$, \[
\{(x,i),(y,i),((x+y)/2,i+1)\}.
\] All blocks have three distinct points. Two points on the same level, with different first coordinates, determine the second type of block uniquely. For points on different levels, orient the pair uniquely as $(x,i),(z,i+1)$. If $x=z$, its unique block is vertical. If $x\ne z$, the unique second point at level $i$ must be $(2z-x,i)$, which is different from $(x,i)$. This supplies exactly one block. Thus every pair occurs once, proving a $2$-$(6t+3,3,1)$ design. The block count is $q+3\binom q2=3q(3q-1)/6$, as required.
Affine line designs
For a prime power $q$ and $d\geq2$, take the points of $\mathbb F_q^d$ and all affine lines $x+\mathbb F_qv$ with $v\ne0$, each line included once. Every line has $q$ points. Two distinct points $x,y$ lie on the unique affine line $x+\mathbb F_q(y-x)$: any line containing them has that direction. Therefore these are $2$-$(q^d,q,1)$ designs when $q>2$. The existence and elementary vector-space properties of finite fields are standard inputs in this family.
Steiner quadruple systems on powers of two
Take $V=\mathbb F_2^d$, $d\geq2$, and all four-element subsets whose vector sum is zero. Three distinct points $x,y,z$ have the unique completion $w=x+y+z$. This is distinct from all three: for example $w=x$ would force $y=z$. The completed block sums to zero, and any block containing that triple must have this fourth point. Thus we obtain a $3$-$(2^d,4,1)$ design, with exactly $\binom{2^d}{3}/4$ blocks.
Outcome and remaining gap
Attempt status: unresolved. Necessary divisibility, the full $r=1$ case, all triple-system orders $3$ modulo $6$, and the stated higher-dimensional families are proved. They cover only special parameter families. Nothing here converts an arbitrary admissible large order for arbitrary fixed $r,k$ into a design; the absorption and approximate-decomposition machinery addressing that gap is substantive. Sources:
https://www.erdosproblems.com/722; P. Keevash,
The existence of designs,
https://arxiv.org/abs/1401.3665, and
A short proof of the existence of designs,
https://arxiv.org/abs/2411.18291. The explicit constructions are classical reconstructions, not novelty claims; no local formal verification is claimed.
COMPLETION ESTIMATE
COMPLETION: 45%