Skip to content

Erdős Problem #665

Editorial depth: Reviewed explanatory article — evidence qualified.
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.

The question in plain language

How nearly equal in size can the blocks of a pairwise balanced design be? In Erdős Problem #665, a design on \(n\) points is a family of proper blocks \(A_1,\ldots,A_m\) satisfying \(2\leq |A_i|<n\), with every unordered pair of different ground points contained in exactly one block. The question is whether a constant \(C>0\) suffices to guarantee a design for every sufficiently large \(n\) with all block sizes greater than \(\sqrt n-C\).

Importantly, \(C\) must not depend on \(n\); and the requirement \(|A_i|<n\) excludes a meaningless one-block construction. The maintained status is OPEN.

A small example

On the seven residues modulo seven, let \(D=\{0,1,3\}\), and take the seven translated blocks \(D+i\) (\(i=0,\ldots,6\)). Their six nonzero oriented differences cover all six nonzero residues exactly once, so every pair of distinct points lies in exactly one three-point block. This is the Fano plane of order two.

Every block has size three and all blocks are proper. The exact pair-counting identity is \(7\binom32=\binom72=21\). Since \(3>\sqrt7\), this tiny example satisfies the proposed lower bound with \(C=0\); it does not solve the problem for every sufficiently large \(n\).

What is known

Each unordered pair appears in one and only one block, so every design satisfies the fundamental counting identity

\[ \sum_{i=1}^m\binom{|A_i|}{2}=\binom n2. \]

An entire projective plane of order \(q\) supplies \(n=q^2+q+1\) points and the same number of lines, each with \(q+1\) points. Since \(q+1>\sqrt{q^2+q+1}\), this produces excellent designs for special sizes \(n\). The issue is that the assertion concerns all sufficiently large integers \(n\), not only those admitting known projective planes.

The original 1982 Erdős–Larson journal chapter, Annals of Discrete Mathematics 15, 129–134, has a publisher summary giving uniform constructions with block sizes \(\sqrt n+O(n^{1/2-c})\) for some positive \(c\). Its abstract notes a conditional refinement to error \(O((\log n)^2)\) under strong conjectures on gaps between consecutive primes. Neither estimate supplies an unconditional constant error.

Shrikhande and Singhi's 1985 paper, Combinatorica 5, 351–358, gives an embedding obstruction for near \(\sqrt n\) blocks. As reported by its author abstract and the maintained problem source, a negative solution follows assuming that every finite projective plane has prime-power order. This conjectural restriction must not be treated as a proved classification of finite projective planes.

GCL's current state

The authenticated original RESULT/1 source return retains its original BOUNDED_TASK_DESIGNED disposition and mathematical qualifications. This source-grounded explanation is editorially reviewed through the exact-hash EC-BULK-005-R8 protected transaction, effective on protected merge. It is not a fresh proof of the attributed mathematical theorem or an internally replayed Lean certificate.

Critical source-scope distinction: Special projective-plane orders do NOT settle every sufficiently large n; no constant-C general theorem claimed.

What remains

Read and verify the original Erdős–Larson and Shrikhande–Singhi theorem pages. The bounded successor is to make the embedding argument and the conjectured prime-power restriction into a two-column assumptions-and-conclusion table. Only then decide whether a proposed near-constant improvement is an unconditional theorem or a conditional implication.

Any computation must enforce the proper-block and unique-pair-cover conditions exactly. Testing finitely many values of \(n\) cannot decide this infinite problem. Editorial critical review, protected publication, actual mathematical rendering verification and separate V2 admission remain required.

Sources and claim boundaries

Boundary: no unconditional resolution, no complete primary full-text proof review, no Lean replay, no protected publication or editorial admission.

Editorial provenance: protected R8 source-critical review. Original issue-level source and research-proof holds remain. Status: REVIEWED explanatory article; full historical theorem proofs, unresolved conjectures and external Lean proofs are not newly certified.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1936 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_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