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.
2. [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)\).
3. [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.
2. williamwkcook, 2025-09-11: OEIS A031436 counts proper linear spaces but
does not encode the requested size histogram.
3. 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
\[ b_k(\mathcal D)=\#\{B\in\mathcal D:|B|=k\},\qquad M(\mathcal D)=\max_{2\le kwhere 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
\[ \sum_{k=2}^{n-1}\binom{k}{2}b_k=\binom n2. \tag{1} \]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]
2. 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].**
3. 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].
4. 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)
5. 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
\[ v=q^2+q+1, \]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
\[ \frac1v\sum_\ell(x_\ell-\mu)^2 =\frac{s q(v-s)}{v^2}\le \frac q4. \tag{2} \]Proof. Every point is on \(q+1\) lines, and every unordered point pair
is on exactly one line. Thus
\[ \sum_\ell x_\ell=s(q+1),\qquad \sum_\ell x_\ell(x_\ell-1)=s(s-1), \]so \(\sum_\ell x_\ell^2=s(s+q)\). Substitution gives
\[ v\sum_\ell x_\ell^2-\left(\sum_\ell x_\ell\right)^2 =s q(v-s), \]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
\[ |x_\ell-\mu|<\sqrt q. \]There are at most \(2\sqrt q+2\) integer values in this interval.
Consequently some exact value \(t\) occurs on at least
\[ \frac{3v}{4(2\sqrt q+2)}=\Omega(q^{3/2}) \tag{3} \]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
\[ \forall q\gg1\;\exists\hbox{ prime }p: 2qBertrand a prime
\[ 2\sqrt n\le p\le4\sqrt n \]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
\[ \forall n\gg1\;\exists(q,p)\in\mathcal C: 0\le qp-n\le Hq. \tag{5} \]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:
| \(n\) | \(f(n)\) | histogram \(k:b_k\) of witness | arithmetic profiles rejected at cap \(f(n)-1\) | DFS states |
|---:|---:|:---|---:|---:|
| 3 | 3 | \(2:3\) | 0 | 0 |
| 4 | 3 | \(2:3,3:1\) | 1 | 1 |
| 5 | 4 | \(2:4,4:1\) | 2 | 6 |
| 6 | 4 | \(2:3,3:4\) | 5 | 20 |
| 7 | 6 | \(2:6,6:1\) | 14 | 125 |
| 8 | 6 | \(2:4,3:6,4:1\) | 25 | 880 |
| 9 | 6 | \(2:6,3:6,4:2\) | 46 | 6,579 |
| 10 | 6 | \(2:6,3:5,4:4\) | 81 | 46,946 |
| 11 | 6 | \(2:4,3:5,4:6\) | 141 | 288,695 |
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
\[ 4+5\binom32+6\binom42=4+15+36=55=\binom{11}{2}. \]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).
2. 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.
3. Choose an uncovered edge. Its block is unique, so branch over every
still-allowed clique containing that edge whose pairs are all
uncovered.
4. 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.