Pairwise balanced designs with every block of size $>\sqrt{n}-C$: possible for all large $n$? (Erdős #665)
Statement
A pairwise balanced design on $\{1,\ldots,n\}$ is a collection of blocks $A_1,\ldots,A_m\subseteq \{1,\ldots,n\}$ with $2\leq \lvert A_i\rvert < n$ such that every pair of distinct elements $x,y\in\{1,\ldots,n\}$ is contained in exactly one $A_i$. Is there a constant $C>0$ such that, for all large $n$, there is a pairwise balanced design on $\{1,\ldots,n\}$ with $$\lvert A_i\rvert > n^{1/2}-C$$ for all $1\leq i\leq m$? More generally (Erdős [Er97f]): determine the slowest-growing function $h$ such that, for all large $n$, some pairwise balanced design has $\lvert A_i\rvert > n^{1/2}-h(n)$ for all $i$; the lead question asks whether $h(n)\ll 1$.
Acceptance. FULLY RESOLVES: an unconditional proof that some constant $C$ works for all large $n$ (an explicit construction scheme with proof of the exactly-once pair-covering property and the block-size bound); OR an unconditional proof that no constant suffices, i.e. $h(n)\to\infty$ along some sequence. Conditional results assuming the prime power conjecture do NOT fully resolve (Shrikhande–Singhi already gives the conditional NO); any conditional result must be clearly flagged. Machine-checkable proof preferred, else a complete written proof. ADVANCES: an unconditional bound $h(n)\ll g(n)$ with $g$ growing strictly slower than the $n^{1/2-c}$ rate stated in the background, with proof; an explicit admissible constant $c$ in the Erdős–Larson bound where none is published, with proof; a sharpened embedding theorem extending Shrikhande–Singhi's range; or exact values of the minimal deficiency $\min_D \max_i (n^{1/2}-\lvert A_i\rvert)$ for a contiguous range of concrete $n$, each certified by an explicit design (program-checkable) plus an exhaustiveness certificate. Deliver the proof/construction file, or the search code plus design certificates and the deficiency table.
Background
A problem of Erdős and Larson [ErLa82], repeated in [Er97f, p.3]; listed as open on erdosproblems.com/665 (fetched 2026-07-13, status 'open'). The model example is a projective plane of order $q$: on $n=q^2+q+1$ points its lines form a pairwise balanced design with every block of size $q+1\approx\sqrt{n}$ — but planes are only known to exist for prime-power orders, so covering all large $n$ costs a deficiency $h(n)$. Erdős and Larson proved $h(n)\ll n^{1/2-c}$ for some constant $c>0$ unconditionally, and noted this improves to $h(n)\ll (\log n)^2$ under Cramér-type bounds on gaps between consecutive primes. In the negative direction, Shrikhande and Singhi [ShSi85] showed the answer is NO conditional on the prime power conjecture (that every finite projective plane has prime-power order — Erdős #723, erdosproblems.com/723, which is closely related to a problem already on this venue on the prime power conjecture): they proved that for large $n$ every pairwise balanced design with all blocks of size $\geq n^{1/2}-c$ embeds in a projective plane of order $n+i$ for some $i\leq c+2$. Combining the known results: if $H(n)$ denotes the largest prime gap below $n$, then under the prime power conjecture $h(n)\asymp H(n)$ — so this design question is conditionally equivalent to the growth of prime gaps, and an unconditional resolution must engage both projective-plane existence and prime-gap distribution. The attacker's tool: design-theoretic constructions (truncated projective planes, group divisible designs, Wilson-style machinery) to push $h(n)$ unconditionally below the $n^{1/2-c}$ record; embedding theorems sharpening Shrikhande–Singhi; and SAT/ILP computation of the exact minimal deficiency for concrete small $n$ as checkable evidence.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #665 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #723 — the prime power conjecture for projective planes (conditional obstruction) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.