Skip to content

Erdős Problem #1159

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: combinatorics.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

UNACCEPTED DRAFT — mathematical editorial review pending

This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.

Review the underlying draft on GitHub.

The question in plain language

Erdős Problem #1159. Does one constant work for every finite projective plane, guaranteeing a point set that touches every line but does not put too many chosen points on any line?

\[ 1\le |S\cap\ell|\le C\quad\text{for every line }\ell\text{ of every finite projective plane}. \]

For every FINITE projective plane P of arbitrary order q (not just Desarguesian prime-power planes), ask if there exists an ABSOLUTE constant C>1 independent of q and P and some point set S such that EVERY line ℓ satisfies 1≤|S∩ℓ|≤C. Such S is a line-hitting/blocking set with UNIFORMLY bounded intersection. Standard 'blocking set' definitions sometimes exclude an entire line; the mathematical condition stated here does NOT. Check degenerate q and possible non-Desarguesian planes; this is not a finite-computation-decidable universal statement.

A small example

Construct PG(2,2) (Fano) and PG(2,3) as one-dimensional projective classes of nonzero vectors in F_q^3, with lines orthogonal to nonzero linear forms. Exhaustive enumeration of ALL point subsets verifies minimal feasible largest line intersection C_min=3 for q=2 and also C_min=3 for q=3. Fano has NO 2-colourable point partition with every line nonmonochromatic, so C=2 fails; choosing one complete Fano line gives C=3 (self-intersection 3, any other line intersection 1). q=3 enumeration finds 6-point S meeting each 4-point line between 1 and3. This finite evidence does not establish any universal q-independent C or treat non-Desarguesian projective planes.

What is known

https://www.erdosproblems.com/1159 OPEN, Vardi [Va99,4.70], Erdős [Er81] stronger related question for pairwise balanced block designs; Erdős–Silverman–Stein [ESS83] guarantee 1≤|S∩ℓ|≪log q for every line, not an absolute constant. Green problem list and #664 related. Published proof not independently checked, and improvement from logarithmic bound to fixed C is unknown.

GCL's current state

Authenticated original-issue source return establishes the bounded question, relevant external results, and independently tested finite fixture. The reproducible checks are in ci/erdos_compendium_007_phase18_checks.py.

The source return disposition is PARTIAL. Neither an original-paper proof review nor any Lean kernel replay or protected editorial acceptance has been completed.

What remains

ERDOS-1159-BLOCKING-CRITICAL-001: deterministic mandatory critical review. Source-lock ESS83 and Er81 original logarithmic statement and formal plane axioms, verify projective order and arbitrary plane coverage. Independently reproduce exhaustive q=2,3 computations and a simple proof no Fano C=2; attempt improved large-order bounds without assuming non-Desarguesian exclusion. Required independent nonauthor critic must review proof/claim boundaries before approving critical sample.

General C absolute OPEN, no original theorem proof replay; mandatory independent critical sample NOT COMPLETE. No Lean certification.

Sources and claim boundaries

https://www.erdosproblems.com/1159 ; [Er81],[ESS83],[Va99,4.70]; #664; exact finite projective geometry fixture.

This is a locally validated, UNACCEPTED editorial draft. Assertions beyond the exact finite checks are attributed to original external sources and remain subject to source-fidelity review.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2430 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: FORMAL_SOURCE_REFRESH_REQUIRED.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction