Erdős problem #734 — live-page audit, exact small orders, and two structural corrections

Accessed 2026-07-27 UTC. Claim labels used throughout:

• [a] elementary-rigorous;
• [b] rigorous modulo the explicitly named published theorem;
• [c] plausible/structural/unverified;
• [d] computational-only.

Outcome

The problem is not solved here. The verified progress is:

1. [d] The exact extremal values are

\[ (f(3),f(4),\ldots,f(11))=(3,3,4,4,6,6,6,6,6), \] where \(f(n)\) is the smallest possible maximum multiplicity of one block size in a proper \(n\)-point PBD. Explicit witnesses and an independent exhaustive lower-bound search are in runs/erdos734_wave7j_reverify.py.

1. [a] Restricting the lines of one projective plane of order \(q\) to

any dense set of its points necessarily leaves one exact intersection size on \(\Omega(q^{3/2})=\Omega(n^{3/4})\) lines. This follows from an exact second-moment identity, so that entire classical route cannot attain \(O(\sqrt n)\).

1. [a] The conditional theorem in the 2026 comment note has a

quantifier gap at the arbitrary-\(n\) step. Its conjecture gives some prime \(p\) for each \(q\), whereas the proof chooses a new \(p\) from \(n\) and then assumes a code exists at that chosen pair. A precise covering-window hypothesis that repairs this is given below.

0. Mandatory live-page check

I fetched the live problem and discussion through the Bright Data browser, not datacenter curl:

• <https://www.erdosproblems.com/734>
• <https://www.erdosproblems.com/latex/734>
• <https://www.erdosproblems.com/forum/thread/734>

The live LaTeX view gives the following statement verbatim:

Find, for all large \(n\), a non-trivial pairwise balanced block design \(A_1,\ldots,A_m\subseteq \{1,\ldots,n\}\) such that, for all \(t\), there are \(O(n^{1/2})\) many \(i\) such that \(\lvert A_i\rvert=t\).

It then defines a PBD by requiring every pair in \(\{1,\ldots,n\}\) to be in exactly one \(A_i\).

Gate result [a, live-page observation]. The page says OPEN, has 0 claimed proofs, “Currently working on this problem: None,” and “Interested in collaborating: None.” Therefore the requested stop condition did not apply.

The page lists the de Bruijn--Erdős \(m\ge n\) result and Erdős's remark that he expected the problem not to be very difficult. Its three comments, newest first, are:

1. MalekZ, 2026-04-30: a link to a 13-page note claiming only a

conditional finite-field reduction and cataloguing failed approaches; the note explicitly says that it is not a solution.

1. williamwkcook, 2025-09-11: OEIS A031436 counts proper linear spaces but

does not encode the requested size histogram.

1. DesmondWeisenberg, 2025-08-24: the \(m\ge n\) statement needs

non-triviality, and the page should define “trivial.”

The linked note is Malek Zribi, Erdos Problem 734: Conditional Reduction, Obstructions, and Current Finite-Field Target (2026-04-30), <https://drive.google.com/file/d/1dp5tbTjJR3t1jdvDUO90U3gxZp2nxySe/view>. I read all 13 pages. It has SHA-256 1a10aa412299c9be2dbee66335ace4721c4274ca6f8fdf672ffe68c9914ea86b. Comments on the site are explicitly marked unverified.

1. Exact formulation

Following the original Erdős--Purdy definition and Gyárfás's terminology, a proper/non-trivial PBD has blocks of sizes \(2,\ldots,n-1\). Singleton blocks are irrelevant, and the sole \(n\)-point block is excluded. Put

and

where the minimum is over proper PBDs of order \(n\). [a] The live problem is exactly \(f(n)=O(\sqrt n)\).

Every PBD obeys the elementary pair count

By the de Bruijn--Erdős theorem every proper PBD has at least \(n\) blocks. Gyárfás's sharp theorem on the maximum number of distinct line sizes then gives \(f(n)>\sqrt n/2\). [b: de Bruijn--Erdős (1948) and Gyárfás Theorem 1/Corollary 2 (2002)].

2. Primary-source literature audit

1. N. G. de Bruijn and P. Erdős, On a combinatorial problem,

Proceedings KNAW 51 (1948), 1277--1279, <https://pure.tue.nl/ws/portalfiles/portal/4300528/597479.pdf?download=1>. The publisher scan's Theorem 1 states \(m\ge n\), with equality cases. [b]

1. P. Erdős and G. Purdy, Some Combinatorial Problems in the Plane,

JCTA 25 (1978), 205--210, <https://users.renyi.hu/~p_erdos/1978-42.pdf>. On pp. 207--208 they define the same \(F(n)\), conjecture square-root order, and label as Theorem 2 the bound \[ F(n)\le c n^{3/4}. \] Their construction restricts a projective plane to a random \(n\)-set; the paper explicitly suppresses the “somewhat laborious” probability calculations. [b: Erdős--Purdy Theorem 2; its omitted calculation was not reconstructed here].

1. P. Erdős, *On the combinatorial problems which I would most like to

see solved*, Combinatorica 1 (1981), 25--42, <https://www.renyi.hu/~p_erdos/1981-16.pdf>. Page 35 contains the statement quoted by the live page. [a, source verification].

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, <https://users.renyi.hu/~p_erdos/1985-12.pdf>. Page 64 restates the question as whether \(f(n)<c\sqrt n\). [a, source verification].

1. A. Gyárfás, *Erdős Problems on Irregularities of Line Sizes and Point

Degrees*, Bolyai Society Mathematical Studies 11 (2002), 367--373, <https://www.renyi.hu/~gyarfas/Cikkek/101_Gyarfas_ErdosProblemsOnIrregularitiesOfLineSizesAndPointDegrees.pdf>. Section 2 still calls this the Erdős--Purdy conjecture and records the \(O(n^{3/4})\) bound. [a, source verification].

I searched the exact problem title/number, “minimum number of line size repetitions,” \(f_2(n)\), \(F(n)\), and combinations of “pairwise balanced design,” “block sizes,” and “multiplicity.” I found the sources above and work on other PBD parameters, but no later primary source improving the \(n^{3/4}\) exponent or settling this question. [c] This is an honest search miss, not a proof that no such literature exists.

For reproducibility, the locally inspected primary PDFs have SHA-256 hashes:

d0517b81e85557e4138309dbe44b4eae96c86452bcba36c76d262ba698a738c7  de Bruijn--Erdos 1948
a9164995f6d11ff382d92cacad915255dfed8b211d15a5549d9860f6c66fd7c5  Erdos--Purdy 1978
4387d2868a46fdee206ab7e249de1c1f93407eb7ed65232ec674efb70001adee  Erdos 1981
1be0256857eb96c11d19a0d5df225f5578f9cb5380ec69642bc349ae50ee69cf  Gyarfas 2002

3. A sharp obstruction to projective-plane truncation

Gyárfás writes that a dense set of points in a projective plane of order \(q\) has one line size repeated at least \(c_2q^{3/4}\) times. That is the exponent as printed. It is weaker than even the immediate pigeonhole bound \(\Omega(q)\), and does not support the adjacent claim that this route cannot improve \(O(n^{3/4})\). [c] It is likely a typographical exponent. The following elementary calculation supplies the needed statement.

Proposition [a]. Let \(\Pi\) be a projective plane of order \(q\), let

and let \(S\) be any \(s\)-point subset. For each line \(\ell\), put \(x_\ell=|\ell\cap S|\), and let \(\mu=s(q+1)/v\). Then

Proof. Every point is on \(q+1\) lines, and every unordered point pair is on exactly one line. Thus

so \(\sum_\ell x_\ell^2=s(s+q)\). Substitution gives

which is (2). The final inequality is \(s(v-s)\le v^2/4\). \(\square\)

It follows from (2) that at least \(3v/4\) lines satisfy

There are at most \(2\sqrt q+2\) integer values in this interval. Consequently some exact value \(t\) occurs on at least

lines. If \(s\ge c q^2\) for fixed \(c>0\), then for all sufficiently large \(q\) the values in this interval are at least \(2\), so these are actual retained PBD blocks. Since \(s=\Theta(q^2)\), (3) is \(\Omega(s^{3/4})\), not \(O(\sqrt s)\). [a]

The verifier constructs \(\mathrm{PG}(2,p)\) from scratch and checks the cross-multiplied identity for all \(2^7\) subsets at \(p=2\), all \(2^{13}\) subsets at \(p=3\), and fixed samples at \(p=5,7\). [d]

4. Quantifier gap in the 2026 conditional note

Write \(C(q,p)\) for “the required flat sloped code exists at \((q,p)\).” Conjecture 2.2 of the note says

In its arbitrary-\(n\) section, however, the note first chooses by Bertrand a prime

and then defines \(q=\lceil n/p\rceil\). It proceeds by “using the flat sloped code” at this new \((q,p)\). Formula (4) gives no code at that chosen prime. Nor does (4) say that the products \(q p\) belonging to coded pairs have \(O(q)\) gaps. Thus, even granting all the note's finite-field and concentration lemmas, its Theorem 2.6 does not follow from Conjecture 2.2 as stated. [a]

A sufficient corrected hypothesis is the following covering condition. There are constants \(H,c,C>0\) and a family \(\mathcal C\) of coded pairs \((q,p)\), with \(cq\le p\le Cq\), such that

Indeed, (5) lets one distribute the \(qp-n\) deleted points with at most \(H\) holes in every one of the \(q\) groups. The note's diagonal lift and hole-histogram lemma then give the desired \(O(p)=O(\sqrt n)\) multiplicity. [b: conditional on the note's exact code and hole-histogram lemmas]. A stronger but simpler repair would require a flat code for every sufficiently large admissible pair \((q,p)\) in a fixed ratio interval.

This is a genuine uniformity requirement: constructing codes for infinitely many or even one-per-\(q\) finite instances does not by itself settle “for all large \(n\).”

5. Exact computation for \(3\le n\le11\)

The exact table is:

All entries are [d]: exact exhaustive computation, not a uniform theorem.

For example, the following zero-based blocks give the optimal \(n=11\) witness:

{0,1}, {0,9}, {1,9}, {6,10},
{0,2,7}, {1,3,4}, {2,3,8}, {4,5,7}, {5,8,9},
{0,3,5,6}, {0,4,8,10}, {1,2,5,10},
{1,6,7,8}, {2,4,6,9}, {3,7,9,10}.

There are four pairs, five triples, and six quadruples. Their pair capacities total

The checker verifies that the 55 covered pairs are distinct.

Why the lower-bound search is exhaustive

To refute a cap \(C\), the verifier does the following.

1. Enumerate every integer vector

\((b_2,\ldots,b_{n-1})\in\{0,\ldots,C\}^{n-2}\) satisfying (1).

1. In any design with such a vector, choose a largest block. Since

\(K_n\) is vertex-transitive, relabel it to \(\{0,\ldots,k-1\}\); this loses no possible design.

1. Choose an uncovered edge. Its block is unique, so branch over every

still-allowed clique containing that edge whose pairs are all uncovered.

1. Decrement the corresponding \(b_k\) quota and recurse. Reject if the

remaining quota capacities do not equal the number of uncovered edges. Memoization stores only states already proved impossible.

Every possible clique decomposition therefore follows one of the branches, and every rejected branch violates either exact pair coverage or its prescribed histogram. [a: completeness of the finite algorithm]. The resulting values remain labelled [d] because the enumeration is machine-executed.

The complete source is runs/erdos734_wave7j_reverify.py. It uses only the Python standard library; it does not trust the CP-SAT model used during discovery. Reproduction command and observed output:

python -u runs/erdos734_wave7j_reverify.py

n= 3: f(n)=3; histogram={2: 3}; lower-cap profiles=0; states=0
n= 4: f(n)=3; histogram={2: 3, 3: 1}; lower-cap profiles=1; states=1
n= 5: f(n)=4; histogram={2: 4, 4: 1}; lower-cap profiles=2; states=6
n= 6: f(n)=4; histogram={2: 3, 3: 4}; lower-cap profiles=5; states=20
n= 7: f(n)=6; histogram={2: 6, 6: 1}; lower-cap profiles=14; states=125
n= 8: f(n)=6; histogram={2: 4, 3: 6, 4: 1}; lower-cap profiles=25; states=880
n= 9: f(n)=6; histogram={2: 6, 3: 6, 4: 2}; lower-cap profiles=46; states=6579
n=10: f(n)=6; histogram={2: 6, 3: 5, 4: 4}; lower-cap profiles=81; states=46946
n=11: f(n)=6; histogram={2: 4, 3: 5, 4: 6}; lower-cap profiles=141; states=288695
PG(2,2): 128 subsets checked (all subsets)
PG(2,3): 8192 subsets checked (all subsets)
PG(2,5): 264 subsets checked (fixed sample)
PG(2,7): 264 subsets checked (fixed sample)
ALL CHECKS PASSED in 81.605 seconds

6. Exact remaining wall

The direct finite search does not supply a construction uniform in \(n\). The best upper bound located remains \(O(n^{3/4})\), modulo the Erdős--Purdy theorem whose probability calculation is omitted in their paper. [b]

The standard one-projective-plane truncation cannot do better than \(\Omega(n^{3/4})\) by (2)--(3). [a] The finite-field route in the 2026 note still needs both:

1. flat exact shifted-correlation codes, not merely small examples; and
2. enough parameter uniformity to satisfy the covering condition (5).

No theorem found in the search supplies either item. That is the precise current wall, rather than a claim that the problem is merely “probably open.”

PARTIAL: exact f(n)=(3,3,4,4,6,6,6,6,6) for 3<=n<=11 with a from-scratch exhaustive verifier; proved an Omega(n^(3/4)) projective-truncation obstruction and isolated a quantifier gap in the current conditional note, but no all-n construction.