Erdős problem 665 — wave w008

Date: 2026-07-28 UTC

Claim labels used below:

• (a) elementary-rigorous: a complete argument or a finite certificate checked exhaustively here.
• (b) rigorous-modulo-named-theorem: the named published theorem is used as an input.
• (c) plausible/structural-unverified: an interpretation or a literature-search miss, not a theorem.
• (d) computational-only: a search observation not used as a proof.

0. Mandatory live-page check

I accessed the live problem page through the Bright Data browser on 2026-07-28, then followed its discussion link to the sole comment. Direct-page tracker metadata was not used as a substitute.

The page showed:

• status OPEN;
• 0 claimed proofs;
• “Currently working on this problem: None”;
• “Interested in collaborating: None”;
• one comment, by BorisAlexeev at 23:11 on 17 January 2026, observing that the formerly allowed trivial choice \(m=1,\ A_1=\{1,\ldots,n\}\) had to be excluded; the comment says the site was updated to address it;
• last page edit: 18 January 2026.

Thus none of the mandatory stop conditions applied.

The source-copy limit permits a 25-word verbatim excerpt. The beginning of the live statement is:

“A pairwise balanced design for \(\{1,\ldots,n\}\) is a collection of sets \(A_1,\ldots,A_m\subseteq\{1,\ldots,n\}\) such that \(2\leq |A_i|<n\) and every pair of distinct elements \(x,y\in\{1,\ldots,n\}\) is”

Here is an exact symbolic transcription of the complete live statement (including the part after that excerpt). Put \(X=\{1,\ldots,n\}\). A family \(\mathcal A=(A_i)_{i=1}^m\) is required to satisfy

The question is

The live page also lists the following known results.

• (b, Erdős–Larson [ErLa82]) If \(h(n)\) denotes the loss below \(\sqrt n\), their construction gives \(h(n)\ll n^{1/2-c}\) for some absolute \(c>0\).
• (b, conditional result in [ErLa82]) Cramér-type bounds for consecutive-prime gaps give \(h(n)\ll(\log n)^2\).
• (b, Shrikhande–Singhi [ShSi85]) For fixed \(c\) and sufficiently large point count, a PBD whose blocks all have size at least \(\sqrt n-c\) embeds in a projective plane whose order is within \(O(c)\) of the square-root scale.
• (b, conditional consequence) If every projective-plane order is a prime power, then the answer to problem 665 is no.
• (b, as stated on the page) Under that same projective-plane conjecture, the optimal loss \(h\) is comparable with the relevant maximal prime-gap function.

The page’s prose/abstract says “order \(n+i\)” while also using \(n\) for the number of PBD points. The primary paper removes the apparent dimensional mismatch: in its proof it puts \(m=\sqrt n\), and Theorem 1.1 embeds into a plane of order \(\lfloor\sqrt n\rfloor+O(c)\); Corollary 1.2 then renames the square-root-scale integer as \(n\).

1. Primary-source literature check

I located and inspected these primary sources rather than relying on search snippets:

1. P. Erdős and J. Larson, On pairwise balanced block designs with the sizes of blocks as uniform as possible, Annals of Discrete Mathematics 15 (1982), 129–134.

(b) Its Theorem 1 gives \(|A_i|=\sqrt n+O(n^{1/2-c})\). Pages 130–134 give the projective-plane/conic deletion construction and the conditional \(O((\log n)^2)\) refinement. The downloaded six-page PDF had SHA-256 9f77e933152c5020279082040b5a3a09f314271be99e8e03eee78f2e952f3c29.

1. S. S. Shrikhande and N. M. Singhi, On a problem of Erdős and Larson, Combinatorica 5(4) (1985), 351–358, DOI 10.1007/BF02579251, with an author-uploaded full text.

(b) Theorem 1.1 proves the near-\(\sqrt n\) embedding statement for sufficiently large \(n\), with the threshold polynomial in \(c\); Corollaries 1.2–1.3 give the bounded-gap implication for projective-plane orders and the conditional negation under the prime-power conjecture.

1. P. Erdős, Some unsolved problems, in Combinatorics, Geometry and Probability (1997), pp. 1–10.

(b) Problem 8 on p. 3 repeats this question, cites Shrikhande–Singhi, and asks for the correct \(h(n)\).

1. P. Erdős, R. A. Duke, J. C. Fowler, and K. T. Phelps, Extremal problems for pairwise balanced designs, Congressus Numerantium 48 (1985), 55–66.

(b) Its further-problems section repeats the question and records Erdős and Larson’s guess that no constant exists.

(c) Exact-title, DOI-forward-citation, author/title, and phrase searches did not locate a later primary paper claiming to settle or improve this specific asymptotic question. The only clearly identified forward item was a 1995 block-design survey. This is a documented search miss, not a claim that no such literature exists.

2. A uniform construction on explicit intervals

Proposition

(b, using existence of \(\mathbf F_q\) for prime-power \(q\)) Let \(q\geq3\) be a prime power. For every

there is a PBD on \(n\) points all of whose blocks have size at least \(q-1\). Consequently every such \(n\) satisfies the desired inequality with the fixed constant \(C=2\):

Proof

Work in \(\operatorname{PG}(2,q)\), which has \(q^2+q+1\) points and \(q+1\) points on every line. Consider

(a) This is a \((q+1)\)-arc. Indeed, a line

meets the affine part in the roots of \(bt^2+at+c\), hence in at most two points unless all coefficients vanish. If the line contains \([0:1:0]\), then \(b=0\), and it has at most one affine root in addition to that point. Thus no line contains three points of \(\mathcal C\).

Choose any \(r\) points of \(\mathcal C\), where \(0\leq r\leq q+1\), and delete them. Trace every projective line on the remaining point set. Every trace has size at least

(a) Every remaining pair still lies in the trace of its unique original projective line, so the traces form a PBD. Its order is

which gives every integer in the asserted interval. Finally,

so \(q-1>\sqrt n-2\). \(\square\)

This is a verified concrete regime, not a solution for all \(n\): even consecutive plane orders leave intervals between these ranges.

3. Exact small-order optimum

Define

where the maximum is over all proper PBDs on \(n\) points.

General upper bound

(a) Every such design with minimum block size \(k\) obeys

To prove this, take a largest block \(B\), of size \(K\), and a point \(x\notin B\), which exists because blocks are proper. The blocks through \(x\), with \(x\) removed, partition the other \(n-1\) points. No one of them can meet \(B\) twice, because then that pair would occur both in it and in \(B\). Thus at least \(K\) blocks pass through \(x\), and

Therefore

Exact table

(a) The following values are exact. Each lower bound is an explicit certificate, and each upper bound follows from (1) plus the exceptional arithmetic arguments below.

| \(n\) | \(f(n)\) | explicit witness: block-size distribution | |---:|---:|:---| | 3 | 2 | \(2^3\) | | 4 | 2 | \(2^6\) | | 5 | 2 | \(2^{10}\) | | 6 | 2 | \(2^{15}\) | | 7 | 3 | \(3^7\) | | 8 | 2 | \(2^{28}\) | | 9 | 3 | \(3^{12}\) | | 10 | 3 | \(3^9\,4^3\) | | 11 | 3 | \(3^{15}\,5^1\) | | 12 | 3 | \(3^4\,4^9\) | | 13 | 4 | \(4^{13}\) | | 14 | 3 | \(3^9\,4^9\,5^1\) | | 15 | 3 | \(3^{35}\) | | 16 | 4 | \(4^{20}\) | | 17 | 4 | \(4^{16}\,5^4\) | | 18 | 3 | \(3^{41}\,4^5\) | | 19 | 3 | \(3^{57}\) | | 20 | 4 | \(4^5\,5^{16}\) | | 21 | 5 | \(5^{21}\) |

The standard witnesses used are:

• all pairs when the attained value is 2;
• \(\operatorname{PG}(2,2)\), \(\operatorname{AG}(2,3)\), \(\operatorname{PG}(2,3)\), \(\operatorname{AG}(2,4)\), and \(\operatorname{PG}(2,4)\);
• deletion of three of the four points on a line of \(\operatorname{PG}(2,3)\) for \(n=10\);
• deletion of four of the five points on a line of \(\operatorname{PG}(2,4)\) for \(n=17\);
• one-point deletions of \(\operatorname{PG}(2,3)\) and \(\operatorname{PG}(2,4)\) for \(n=12,20\);
• at \(n=11\), one 5-block \(H\), with the other six points carrying a one-factorization of \(K_6\): for each \(h\in H\), adjoin \(h\) to the three pairs of one factor;
• the Steiner triple systems \(\operatorname{PG}(3,2)\) and the cyclic STS(19);
• the explicit \(n=14,18\) certificates stored literally in the verifier.

Exceptional upper bounds

The envelope \(U(n)\) is attained except at \(n=8,14,15,18,19\).

• (a), \(n=8\): If \(k=3\), (1) forces every block to have size 3. At a point, the remaining seven points would have to be partitioned into pairs, impossible.
• (a), \(n=14,15\): If \(k=4\), (1) forces every block to have size 4. Then \(n-1\) must be divisible by 3 at every point; neither 13 nor 14 is.
• (a), \(n=18\): A block has size 4 or 5. If \(r_s(x)\) counts the \(s\)-blocks through \(x\), then

\[ 3r_4(x)+4r_5(x)=17, \] whose only nonnegative solution is \((r_4,r_5)=(3,2)\). Hence \(\sum_xr_4(x)=54\), which is not divisible by 4, although it must equal four times the number of 4-blocks.

• (a), \(n=19\): First suppose a 6-block \(B\) exists. For every \(x\notin B\), equality holds in

\[ 18\geq |B|(4-1)=18. \] The six blocks through \(x\) meeting \(B\) therefore all have size 4 and exhaust the blocks through \(x\). No other 5- or 6-block can exist. At a point of \(B\), the 4-blocks would have to partition the 13 outside points into triples, contradicting \(3\nmid13\). If no 6-block exists, all blocks have size 4 or 5 and \[ 3r_4(x)+4r_5(x)=18. \] The only local patterns are \((6,0)\) and \((2,3)\). In either case \(r_4(x)\equiv2\pmod4\), so \(\sum_xr_4(x)\equiv19\cdot2\equiv2\pmod4\), again impossible.

4. Computation and independent re-verification

The standalone checker is erdos665_wavew008_verify.py. It uses only the Python standard library. Its SHA-256 is

298ac33ff4059b408367147c5ae513a4fec48f5c7e82eb308f2a72282c25b773.

Run:

python runs/erdos665_wavew008_verify.py

The core pairwise check is:

def check_pbd(n, blocks):
    normalized = [tuple(sorted(block)) for block in blocks]
    assert len(normalized) == len(set(normalized))
    assert all(2 <= len(block) < n for block in normalized)
    counts = Counter(
        pair
        for block in normalized
        for pair in combinations(block, 2)
    )
    assert set(counts) == set(combinations(range(n), 2))
    assert set(counts.values()) == {1}
    return min(map(len, normalized))

The full checker additionally:

1. constructs the finite affine/projective planes from field arithmetic, including an explicit multiplication table for \(\mathbf F_4\);
2. constructs every small-order witness and checks every pair exactly once;
3. recomputes \(U(n)\);
4. enumerates all possible local incidence vectors at the exceptional orders and checks the global divisibility obstruction;
5. separately checks the equality branch for a hypothetical 6-block at \(n=19\);
6. constructs the standard arc in \(\operatorname{PG}(2,q)\) and checks every deletion count for \(q=3,4,5\).

The observed final output was:

PG(2,q) arc-truncation checks
q=3: n=9..13, verified minima by deletion count 0..4: [4, 3, 2, 2, 2]
q=4: n=16..21, verified minima by deletion count 0..5: [5, 4, 3, 3, 3, 3]
q=5: n=25..31, verified minima by deletion count 0..6: [6, 5, 4, 4, 4, 4, 4]

ALL CHECKS PASSED

(d) Discovery used SciPy/HiGHS and OR-Tools CP-SAT exact-cover models. After fixing a largest block to break symmetry, CP-SAT found the \(n=14\) certificate in 0.29 s and the \(n=18\) certificate in 1.48 s. Three \(n=19\) searches, limited to roughly 30 s each, were inconclusive; the elementary argument above settled that case. Solver output is not used in the proof or verifier.

5. What remains and why this does not close the problem

(b, Shrikhande–Singhi) A positive answer with constant \(C\) would force bounded forward gaps between sufficiently large projective-plane orders (on the square-root scale). Under the prime-power conjecture, known unbounded prime gaps therefore give a negative answer.

(c) Unconditionally, the exact missing structural input for that negative route is an unbounded-gap theorem for orders of finite projective planes. No such theorem is known; current general nonexistence criteria do not exclude all orders in arbitrarily long intervals.

(c) The positive route would need a construction covering the gaps between the prime-power intervals in Section 2 without assuming nearby projective planes. Arc deletion alone cannot do this: a bounded line loss permits only \(O(q)\) deleted points from a plane of order \(q\), and the geometry of the deletion set controls which of those losses can remain bounded.

(d) Brute-force extension is not a plausible uniform route. Already for \(n=50\) and candidate minimum 7, the elementary upper bound permits blocks of sizes 7 and 8, giving \(\binom{50}{7}+\binom{50}{8}>6.3\times10^8\) raw exact-cover columns. A conventional sparse encoding would require tens of GB before search, and an exact classification would realistically cost at least \(10^3\) core-hours (and potentially much more). Such a computation could enlarge the finite table but cannot supply the required “for all sufficiently large \(n\)” step.

PARTIAL: Exact \(f(n)\) for every \(3\le n\le21\), plus a verified \(C=2\) construction for every \(q^2\le n\le q^2+q+1\) with prime-power \(q\); the uniform problem remains blocked by gaps between projective-plane orders.