Blocking sets meeting every line at most $C$ times: uniform over all projective planes? (Erdős #1159)
Statement
Determine whether there exists a constant $C>1$ such that the following holds: for every finite projective plane $P$, there is a set of points $S$ such that $$1\leq \lvert S\cap \ell\rvert \leq C$$ for every line $\ell$ of $P$. (A set of points meeting every line is called a blocking set; the question asks whether every finite projective plane — Desarguesian or not, of any order — admits a blocking set that meets no line more than a bounded number of times, with the bound uniform over all planes.)
Acceptance. FULLY RESOLVES: a proof that some absolute constant $C$ works for every finite projective plane — the argument must apply to all planes (not only Desarguesian ones) and all sufficiently large orders together with the finitely many small ones — as a complete written proof or machine-checkable; OR a proof of unboundedness: an explicit infinite family of planes together with a proof that every blocking set in the $n$-th member meets some line in at least $f(n)\to\infty$ points. A finite computation alone cannot close this. ADVANCES: an improvement of the Erdős–Silverman–Stein $O(\log n)$ bound stated in the background to a strictly slower-growing function, even restricted to a natural class such as Desarguesian planes $PG(2,q)$, with proof; a proof that a bounded $C$ suffices for $PG(2,q)$ for all $q$; exact values of the minimal achievable $\max_\ell \lvert S\cap\ell\rvert$ for every known plane of order up to a stated bound (at least through order 9), each certified by a witness set $S$ (checkable by a program against the plane's incidence data) plus an optimality certificate (SAT/ILP); or a resolution of the stronger pairwise-balanced-design version in either direction. Deliver the proof file, or the incidence data + search code + per-plane witness and optimality certificates.
Background
Recorded in Vaughan's problem collection [Va99, 4.70]; listed as open on erdosproblems.com/1159 (fetched 2026-07-13, status 'open'). In [Er81] Erdős asked the stronger question of whether the same holds for all pairwise balanced block designs. The best known general result is due to Erdős, Silverman, and Stein [ESS83]: every projective plane of order $n$ has a blocking set $S$ with $\lvert S\cap\ell\rvert \ll \log n$ for all lines $\ell$ (a probabilistic bound), so the open gap is between $O(\log n)$ and $O(1)$. A stronger question is Erdős #664 (erdosproblems.com/664), and the problem is mentioned after Problem 68 on Ben Green's open problems list. Note the classical bounded-intersection candidates fail: a Baer subplane of $PG(2,q)$ is a blocking set but meets some lines in $\sqrt{q}+1$ points, which grows with the order. Since planes of small order are completely classified (unique planes of orders 2–8, exactly four planes of order 9, none of order 10 by Lam–Thiel–Swiercz), the per-plane optimum is a concrete finite computation there. The attacker's tool: SAT/ILP search for blocking sets minimising the maximum line-intersection in all known planes of order $\leq 11$ (establishing exact per-plane constants and evidence for or against a uniform $C$), plus probabilistic or algebraic constructions (e.g. in Desarguesian planes) to beat the $\log n$ barrier.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1159 (T. F. Bloom) | website |
| REF-02 | Ben Green, open problems list (mentioned after Problem 68) | website |
| REF-03 | Erdős Problem #664 — a stronger question on bounded-intersection blocking sets | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.