Erdős problem 1159 — wave w035
Date: 2026-07-29 (UTC)
Claim labels
Every substantive claim is tagged as requested:
- [a] elementary-rigorous, with the proof written in the report;
- [b] rigorous modulo the explicitly named published theorem;
- [c] plausible/structural-unverified;
- [d] computational-only (a solver observation, not a theorem).
No novelty is claimed for results already present in the cited literature. The useful output here is a from-scratch synthesis, explicit certificates, an independently implemented checker, and a sharply delimited computational wall.
Step 0: live-page audit, before doing mathematics
[d] I fetched the live page through the Bright Data browser, not datacenter curl (which returned a Cloudflare challenge). On 2026-07-29 the page showed OPEN, 0 claimed proofs, Currently working on this problem: None, Interested in collaborating: None, and no other worker/interest markers. Hence the mandatory stop condition did not trigger. The page says it was last edited 2026-04-10.
The verbatim live statement is:
Determine whether there exists a constant \(C>1\) such that the following holds.
Let \(P\) be a finite projective plane. Must there exist a set of points \(S\) such that \(1\leq \lvert S\cap \ell\rvert\leq C\) for all lines \(\ell\)?
[d] The live page's listed known-results text is:
A set which meets all lines at once is called a blocking set. In [Er81] Erdős asks the stronger question of whether this is true for all pairwise balanced block designs.
Erdős, Silverman, and Stein [ESS83] proved this is true with \(\lvert S\cap\ell\rvert\ll\log n\) for all lines \(\ell\) (where \(n\) is the order of the projective plane).
See also [664] for a stronger question. This problem is mentioned after Problem 68 on Green's open problems list.
[d] The sole discussion comment, by Zach Hunter at 15:45 on 2026-02-01, reads:
Ben mentions this problem below Problem 68 of his list of problems.
(The site has been updated to address this comment.)
Live sources:
Notation and the strict-inequality convention
[a] For a particular plane \(\Pi\), put
This is an integer. The live question is whether \(\sup_\Pi c(\Pi)<\infty\).
[a] Older papers say that a family has property \(B(k)\) when \(0<|S\cap L|<k\). Thus their parameter \(k\) equals the live page's maximum intersection bound \(C\) plus one. I use the live convention throughout.
Primary-source literature check
- [b] Erdős–Silverman–Stein, *Intersection properties of families
containing sets of nearly the same size*, Ars Combinatoria 15 (1983), 247–259, really exists and its abstract states the projective-plane \(O(\log n)\) result. Its introduction asks exactly for an absolute \(B(c)\) bound. A current paper records the sharper constant formulation: for every fixed \(c>2e\), \(k(n)<c\log n\) for all sufficiently large \(n\). Primary PDF
- [b] Bruen–Fisher, Blocking sets and complete \(k\)-arcs, Pacific
Journal of Mathematics 53 (1974), 73–84, proves in Theorem 6(iv) that in every projective plane of order at least \(5\), every (nontrivial) blocking set has a line containing at least four of its points. Theorem 12 gives an explicit maximum-four construction in every \(\mathrm{PG}(2,3^r)\), \(r\ge2\). Primary PDF
- [b] Béres–Illés, *Computational investigation of the covering number of
finite projective planes with small order*, Alkalmazott Matematikai Lapok 17, 397–411, independently derives the same \(B(4)\) obstruction from the three incidence-count equations and reports heuristic constructions for prime orders through \(89\). Those larger-order values are upper bounds, not exact optima. In particular, the paper explicitly says its CPLEX run already failed to prove optimality at \(q=7\). Full-text record
- [b] Asgarli–Ghioca–Yip, Blocking sets from a union of plane curves,
arXiv:2510.15332v1 (2025), exists and says the Erdős question is “still wide open.” Its Theorem 1.2 proves that an odd-order Desarguesian plane needs \(\Omega(\log q)\) nonsingular conics if their union is to block; Theorem 3.1 says a curve of bounded total degree whose components are reflexive cannot block for sufficiently large \(q\) relative to that degree; Theorem 1.3 gives the corresponding fixed-degree-union obstruction in growing characteristic. arXiv abstract and PDF
- [c] Green's list (most recent update stated there: December 2025) goes
further only as speculation: after Problem 68 it says that as \(q\) ranges over sufficiently large primes, it is speculated that even a bound such as \(1000\) does not exist. This is not a theorem and is not used as one. Primary PDF, p. 33
[c] Searches by the exact problem wording, property B(s), bounded line-intersection blocking sets, and the cited names found no primary source claiming either a uniform construction for all planes or an unbounded lower bound. This is a search report, not a proof of absence. The live status and the 2025 arXiv paper agree that the general problem remains open.
Elementary lower bound, rederived from scratch
Let \(\Pi\) have order \(q\), so it has
points and lines, and every line has \(q+1\) points. Let \(s=|S|\), and let \(n_i\) be the number of lines meeting \(S\) in exactly \(i\) points.
No value \(C\le2\)
[a] If every line meets \(S\) in one or two points, then counting lines, incidences, and pairs of selected points gives
Consequently
Its discriminant is
for every \(q\ge2\). Therefore every finite projective plane has \(c(\Pi)\ge3\).
No value \(C\le3\) once \(q\ge5\)
[a] If intersections are in \(\{1,2,3\}\), the analogous counts are
Eliminating \(n_1,n_3\) gives
As a quadratic in \(s\), its discriminant is
For \(q\ge5\), \(\Delta_3<0\); since the leading coefficient is negative, \(n_2<0\) for every real \(s\), a contradiction. Hence
This proof is elementary and uniform, but not new: it is the short incidence-count core of the cited Bruen–Fisher/Béres–Illés result.
A closed-form exact infinite regime
[b] Let \(F=\mathbb F_{3^r}\), \(r\ge2\), and choose a nonsquare \(t\in F^\times\). In the affine part of \(\mathrm{PG}(2,F)\), Bruen–Fisher take
The two affine curves overlap at \((0,0)\), so \(|S|=2q\).
[b] The line at infinity meets \(S\) once. A vertical affine line meets it in two or three points. For a nonvertical line \(y=mx+b\) with \(m\ne0\), the intersections with the two cubics are the roots of
In characteristic \(3\), their discriminants are \(m^3\) and \((m/t)^3\). Exactly one is a square. The finite-field cubic discriminant criterion then says that one cubic has exactly one root, while the other has zero or three, so the line meets \(S\) in one or four points. Horizontal lines are handled by the bijectivity of \(x\mapsto x^3\). Thus every line meets \(S\) between one and four times.
Combining this published construction with the elementary lower bound gives the exact infinite family
[d] The independent checker below reconstructs the fields and verifies all lines for \(q=9\) and \(q=27\), without a finite-field or geometry package.
Explicit checked small cases
Coordinates are canonical homogeneous triples. Over a prime field they are reduced modulo \(q\); over \(\mathbb F_4\) the checker uses \(\mathbb F_2[u]/(u^2+u+1)\).
| Plane | \(|S|\) | secant histogram \(\{i:n_i\}\) | verified conclusion | status | |---|---:|---|---|---| | \(\mathrm{PG}(2,2)\) | 3 | \(\{1:6,3:1\}\) | \(c=3\) | [a] lower + explicit line | | \(\mathrm{PG}(2,3)\) | 6 | \(\{1:6,2:3,3:4\}\) | \(c=3\) | [a] lower + [d] finite certificate | | \(\mathrm{PG}(2,4)\) | 7 | \(\{1:14,3:7\}\) | \(c=3\) | [a] lower + [d] Baer certificate | | \(\mathrm{PG}(2,5)\) | 9 | \(\{1:18,2:6,3:4,4:3\}\) | \(c=4\) | [a] lower + [d] finite certificate | | \(\mathrm{PG}(2,7)\) | 17 | \(\{1:20,2:10,3:12,4:15\}\) | \(c=4\) | [a] lower + [d] finite certificate | | \(\mathrm{PG}(2,9)\) | 18 | \(\{1:50,2:9,3:16,4:16\}\) | \(c=4\) | [a+b] lower + cubic theorem; [d] checked | | \(\mathrm{PG}(2,27)\) | 54 | \(\{1:470,2:27,3:52,4:208\}\) | \(c=4\) | [a+b] lower + cubic theorem; [d] checked | | \(\mathrm{PG}(2,11)\) | 28 | \(\{1:40,2:31,3:31,4:14,5:17\}\) | \(4\le c\le5\) | [a] lower, [d] found finite certificate |
The prime-field certificates not already obvious from the description are:
q=3:
{(1,0,0),(1,0,2),(1,1,0),(1,1,2),(1,2,1),(0,1,0)}
q=5:
{(1,0,0),(1,0,2),(1,0,3),(1,0,4),(1,1,3),
(1,2,4),(1,3,0),(1,4,0),(0,1,0)}
q=7:
{(0,1,0),(1,0,0),(1,0,3),(1,0,4),(1,0,6),
(1,1,1),(1,1,3),(1,1,4),(1,1,5),
(1,2,2),(1,2,3),(1,2,4),(1,2,6),
(1,3,1),(1,4,1),(1,5,0),(1,6,0)}
q=11 (maximum intersection 5):
{(0,0,1),
(1,0,6),(1,0,7),(1,0,9),(1,0,10),
(1,1,4),(1,1,6),(1,1,7),(1,1,8),
(1,2,1),(1,2,4),(1,2,6),(1,2,7),
(1,3,2),(1,3,8),(1,4,3),(1,4,4),(1,5,5),(1,6,3),
(1,7,0),(1,7,7),(1,8,7),(1,8,9),
(1,9,3),(1,9,6),(1,10,3),(1,10,6),(1,10,10)}
[d] The checker reports that each histogram passes the three independent identities, which themselves follow by the elementary counts [a]
The unresolved \(q=11,C=4\) computation
[a] The exact feasibility model uses one Boolean \(x_P\) for each of the 133 points and the 266 inequalities
[a] A valid symmetry break is available. Any blocking set contains an inclusion-minimal blocking subset; every selected point of such a subset lies on a tangent (a line meeting it once). Since \(\mathrm{PGL}(3,11)\) is transitive on incident point-line flags, one may fix \((0,0,1)\in S\) and the line \(x=0\) as a tangent, forcing the other eleven variables on that line to zero.
The core search model used was:
P = ([(1,a,b) for a in range(q) for b in range(q)]
+ [(0,1,a) for a in range(q)] + [(0,0,1)])
rows = [[i for i,p in enumerate(P)
if sum(p[j]*line[j] for j in range(3)) % q == 0]
for line in P]
x = [model.NewBoolVar(f"x{i}") for i in range(len(P))]
for row in rows:
model.Add(sum(x[i] for i in row) >= 1)
model.Add(sum(x[i] for i in row) <= C)
model.Add(x[P.index((0,0,1))] == 1)
for i in rows[P.index((1,0,0))]:
if i != P.index((0,0,1)):
model.Add(x[i] == 0)
# Valid because lines through any point outside S inject q+1 points into S:
model.Add(sum(x) >= q + 1)
[d] For \(q=11,C=4\), deterministic one-worker CP-SAT ran for 60.0 s, visited 1,647,804 branches with 302,342 conflicts, and returned UNKNOWN. A separate sequential-counter CNF had 4,389 variables and 9,189 clauses; Kissat also timed out at 60 s. Neither timeout is evidence of infeasibility. For \(C=5\), CP-SAT found the displayed 28-point certificate in 2.48 s, and the independent script verifies it.
[c] A responsible next exact computation would be a certified portfolio for \(q=11,C=4\): roughly 32 solver/encoding/symmetry variants at two core-hours each (64 core-hours), retaining a DRAT/LRAT proof if UNSAT or a witness if SAT. If that fails, an isomorph-free enumeration by possible secant spectra is likely a \(10^2\)–\(10^3\) core-hour project. These are engineering budgets, not predictions of completion, and were not run here.
Why the standard machinery stalls
[a] Independent Bernoulli sampling cannot by itself reach a constant. If points are selected with probability \(p\), a line is empty with probability approximately \(e^{-p(q+1)}\). There are approximately \(q^2\) lines, so even the basic union-bound scale requires \(p(q+1)\gtrsim2\log q\). But this is also the mean intersection with a line, already logarithmic. Correlated selection or a substantial alteration argument is indispensable.
[b] The most obvious bounded-degree algebraic replacement is also blocked in growing characteristic. A union of curves of total degree \(D\) meets a line in at most \(D\) points unless it contains that line, but Asgarli–Ghioca–Yip Theorem 3.1 shows that a fixed-degree reflexive union has a positive proportion of skew lines for sufficiently large \(q\). Thus a uniform positive solution cannot come merely from a fixed collection of fixed-degree reflexive curves over \(\mathbb F_q\) as the characteristic grows.
[c] The exact missing structural ingredient is therefore one of:
- a bounded-intersection construction with strong global correlations that
works in arbitrary (including non-Desarguesian) planes; or
- for a negative solution, a lower bound \(c(\mathrm{PG}(2,p))\to\infty\)
(or another explicit family of planes), going strictly beyond the universal lower bound \(4\).
No such lemma is proved here. In particular, lower bounds for unions of bounded-degree curves cannot be promoted to lower bounds for arbitrary point sets.
Reproduction code and output
The complete standalone checker is erdos1159_wavew035_reverify.py (SHA-256 08597e759e35634dc26ab4e144444ad4d192b475d69f1dc984ebeaf55c32daf1). It has no nonstandard dependencies. It implements quotient finite fields, checks irreducibility of the defining polynomials, reconstructs all projective points and lines, checks the incidence axioms, checks every witness and all three global count identities, and rebuilds the cubic construction.
Run:
python runs/erdos1159_wavew035_reverify.py
Observed output:
symbolic obstructions: C>=3 for q>=2; C>=4 for q>=5
PG(2,2) line: q=2, |S|=3, max=3, histogram={1: 6, 3: 1}
PG(2,3): q=3, |S|=6, max=3, histogram={1: 6, 2: 3, 3: 4}
PG(2,4) Baer subplane PG(2,2): q=4, |S|=7, max=3, histogram={1: 14, 3: 7}
PG(2,5): q=5, |S|=9, max=4, histogram={1: 18, 2: 6, 3: 4, 4: 3}
PG(2,7): q=7, |S|=17, max=4, histogram={1: 20, 2: 10, 3: 12, 4: 15}
PG(2,11) upper-bound witness: q=11, |S|=28, max=5, histogram={1: 40, 2: 31, 3: 31, 4: 14, 5: 17}
Bruen--Fisher cubic construction in PG(2,9): q=9, |S|=18, max=4, histogram={1: 50, 2: 9, 3: 16, 4: 16}
Bruen--Fisher cubic construction in PG(2,27): q=27, |S|=54, max=4, histogram={1: 470, 2: 27, 3: 52, 4: 208}
ALL CHECKS PASSED
PARTIAL: The general problem remains open; verified \(C\ge4\) for every plane of order at least 5, exact \(c(\mathrm{PG}(2,3^r))=4\) for all \(r\ge2\), exact checked values through the listed small Desarguesian cases, and \(4\le c(\mathrm{PG}(2,11))\le5\) with an explicit certificate.