Reused writeup on Math-5852 (gpt pro 5.2)

Erdős Problem 734 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/734

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/734.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/734.tex.

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$. $A_1,\ldots,A_m$ is a pairwise balanced block design if every pair in $\{1,\ldots,n\}$ is contained in exactly one of the $A_i$. Erdős [Er81] writes 'this will be probably not be very difficult to prove but so far I was not successful'. Erdős and de Bruijn [dBEr48] proved that if $A_1,\ldots,A_m\subseteq \{1,\ldots,n\}$ is a pairwise balanced block design then $m\geq n$, and this implies there must be some $t$ such that there are $\gg n^{1/2}$ many $t$ with $\lvert A_i\rvert=t$. References [Er81] Erdős, P., On the combinatorial problems which I would most like to see solved . Combinatorica $1981$, 25-42. [dBEr48] de Bruijn, N. G. and Erdős, P., On a combinatorial problem . Nederl. Akad. Wetensch., Proc. $1948$, 1277--1279 = Indagationes Math. 10, 421--423.

1) FORMAL RESTATEMENT.

A family of subsets ("blocks") $A_1,\dots,A_m\subseteq [n]:=\{1,\dots,n\}$ is a pairwise balanced block design (PBD) if:

• every unordered pair $\{x,y\}\subseteq [n]$ with $x\neq y$ is contained in exactly one block $A_i$.

The problem asks: for all sufficiently large $n$, does there exist a nontrivial PBD $A_1,\dots,A_m$ such that for every integer $t$, \[ \#\{i:\;|A_i|=t\}=O(n^{1/2}) \quad\text{(uniformly in $t$)}? \]

Ambiguity/nontriviality. The single-block design $\{A_1=[n]\}$ is a PBD (every pair lies in that unique block). This is presumably the "trivial" design. The minimal corrected interpretation consistent with standard usage is:

"nontrivial" means $m\ge 2$ (equivalently, not the single block $[n]$).

Under this interpretation, every block must have size at most $n-1$.

2) QUICK LITERATURE/CONTEXT CHECK.

The statement records that de Bruijn and Erdős proved $m\ge n$ for any PBD, and that this forces some block size to occur $\gg \sqrt n$ times. I will reprove $m\ge n$ (Lemma 734.3) and the $\Omega(\sqrt n)$ multiplicity consequence (Proposition 734.4) directly.

3) ATTACK PLAN.

Proof-track (construction).

• Reformulate the problem as a decomposition of the edge set of $K_n$ into cliques $K_{|A_i|}$, one clique per block.
• Attempt to build a clique decomposition with about $\sqrt n$ occurrences of each clique size, requiring about $\sqrt n$ distinct sizes.

Disproof-track (obstructions).

• Use necessary counting identities to show any PBD forces some size class to be too large, or forces too many repeated sizes.

In this write-up I develop the standard identities and the sharp lower bound that some size must occur $\Omega(\sqrt n)$ times, matching the target order.

4) WORK.

Fast reality check (small $n$).

• $n=2$: only PBD is one block of size $2$ (trivial).
• $n=3$: blocks $\{1,2\},\{1,3\},\{2,3\}$ form a PBD, but the size-$2$ multiplicity is $3\not=O(\sqrt 3)$ in the asymptotic sense.
• "Near-pencil" construction for general $n$: one block of size $n-1$ plus $n-1$ blocks of size $2$ gives a nontrivial PBD, but the size-$2$ multiplicity is $n-1\gg \sqrt n$, so it fails the required bound.

Lemma 734.1 (Pair-count identity). If $A_1,\dots,A_m\subseteq [n]$ is a PBD, then \[ \sum_{i=1}^m \binom{|A_i|}{2}=\binom{n}{2}. \]

Proof. Each block $A_i$ contains exactly $\binom{|A_i|}{2}$ unordered pairs. In a PBD, every unordered pair of distinct elements of $[n]$ lies in exactly one block, so counting pairs by the block that contains them gives the identity. $\square$

Lemma 734.2 (Pointwise partition identity). Fix $v\in[n]$. Then \[ \sum_{i:\,v\in A_i} (|A_i|-1)=n-1. \] Consequently, \[ \sum_{i=1}^m |A_i|(|A_i|-1)=n(n-1). \]

Proof. Fix $v$. For each other point $u\in[n]\setminus\{v\}$, the pair $\{u,v\}$ lies in exactly one block, say $A_{i(u)}$. Thus, as $u$ ranges over $[n]\setminus\{v\}$, the other points in blocks containing $v$ form a disjoint partition of $[n]\setminus\{v\}$ by the sets $A_i\setminus\{v\}$ (with $v\in A_i$). Therefore the total number of elements in this partition is \[ \sum_{i:\,v\in A_i} |A_i\setminus\{v\}|=\sum_{i:\,v\in A_i} (|A_i|-1)=|[n]\setminus\{v\}|=n-1. \] Summing this identity over all $v\in[n]$ counts each block $A_i$ exactly $|A_i|$ times, giving \[ \sum_{v\in[n]}\sum_{i:\,v\in A_i} (|A_i|-1)=\sum_{i=1}^m \sum_{v\in A_i} (|A_i|-1)=\sum_{i=1}^m |A_i|(|A_i|-1)=\sum_{v\in[n]} (n-1)=n(n-1). \] $\square$

Lemma 734.3 (de Bruijn--Erdős inequality $m\ge n$ for nontrivial PBDs). Let $A_1,\dots,A_m\subseteq[n]$ be a PBD that is not the single block $[n]$. Then $m\ge n$.

Proof. Form the $n\times m$ incidence matrix $M$ with entries $M_{v,i}=1$ if $v\in A_i$ and $0$ otherwise. Consider the $n\times n$ matrix $B:=MM^\top$.

For distinct points $u\neq v$, the $(u,v)$ entry of $B$ equals the number of blocks containing both $u$ and $v$, which is $1$ by the PBD property. Thus $B_{uv}=1$ for $u\neq v$.

For the diagonal entries, $B_{vv}$ equals the number of blocks containing $v$, denote this by $r_v\ge 1$.

Therefore $B$ has the form \[ B = J - I + D, \] where $J$ is the all-ones matrix, $I$ is the identity, and $D$ is the diagonal matrix with $D_{vv}=r_v$.

We claim $B$ is nonsingular. Suppose $Bx=0$ for some vector $x\in\mathbb R^n$. Writing the $v$th component: \[ 0=(Bx)_v = \sum_{u\neq v} x_u + r_v x_v = \left(\sum_{u=1}^n x_u\right) - x_v + r_v x_v = s + (r_v-1)x_v, \] where $s:=\sum_{u=1}^n x_u$. Thus for each $v$, \[ (r_v-1)x_v = -s. \tag{$\ast$} \] If there exists $v$ with $r_v=1$, then $(\ast)$ gives $0\cdot x_v=-s$, hence $s=0$, and then $(\ast)$ gives $(r_u-1)x_u=0$ for all $u$, so $x_u=0$ for all $u$ with $r_u>1$. For $u$ with $r_u=1$, we still have $s=\sum x_u=0$, so the sum of $x_u$ over those $u$ is $0$. But if $r_u=1$, then $u$ lies in exactly one block. In a PBD, if a point lies in exactly one block, that block must contain all other points (otherwise some pair with $u$ would not be covered), forcing the design to be the single block $[n]$, contradicting nontriviality. Hence in a nontrivial PBD we have $r_v\ge 2$ for all $v$.

Thus $r_v-1>0$ for all $v$, and from $(\ast)$ we obtain $x_v = -s/(r_v-1)$ for all $v$. Summing over $v$ gives \[ s=\sum_{v=1}^n x_v = -s\sum_{v=1}^n \frac{1}{r_v-1}. \] The sum on the right is positive, so the only solution is $s=0$, and then $x_v=0$ for all $v$. Therefore $B$ is nonsingular, so $\mathrm{rank}(B)=n$.

Now $\mathrm{rank}(B)=\mathrm{rank}(MM^\top)\le \mathrm{rank}(M)\le m$. Hence $n\le m$, as required. $\square$

Proposition 734.4 (Some block size occurs $\Omega(\sqrt n)$ times). Let $A_1,\dots,A_m\subseteq[n]$ be a nontrivial PBD. Then there exists an integer $t$ with \[ \#\{i:\ |A_i|=t\}\ \ge\ \frac{\sqrt n}{2\sqrt 2}. \]

Proof. By Lemma 734.1, \[ \frac{1}{m}\sum_{i=1}^m |A_i|(|A_i|-1)=\frac{2}{m}\sum_{i=1}^m \binom{|A_i|}{2}=\frac{2\binom{n}{2}}{m}=\frac{n(n-1)}{m}. \] By Lemma 734.3, $m\ge n$, hence the average of $|A_i|(|A_i|-1)$ over $i$ is at most $n-1$.

Therefore at least half of the indices $i$ satisfy \[ |A_i|(|A_i|-1)\le 2(n-1). \] For such an $i$, we have $|A_i|^2\le |A_i|(|A_i|-1)+|A_i|\le 2(n-1)+|A_i|\le 2n-2+|A_i|$, which implies $|A_i|\le 2\sqrt{2n}$ for all sufficiently large $n$; a simpler direct bound is obtained by solving $t(t-1)\le 2(n-1)$, giving $t\le \frac{1+\sqrt{1+8(n-1)}}{2}<\sqrt{2n}+1$. Thus for all these $\ge m/2$ blocks, their sizes lie in the set $\{2,3,\dots,\lfloor \sqrt{2n}+1\rfloor\}$, which has fewer than $\sqrt{2n}$ possible values.

By the pigeonhole principle, some size $t\le \sqrt{2n}+1$ occurs at least \[ \frac{m/2}{\sqrt{2n}}\ \ge\ \frac{n/2}{\sqrt{2n}}\ =\ \frac{\sqrt n}{2\sqrt 2} \] times. $\square$

5) VERIFICATION.

• Lemma 734.1 and Lemma 734.2 are direct double-counting/partition arguments; checked that "exactly one block per pair" is used correctly.
• Lemma 734.3: verified the nonsingularity argument. The key subtlety is ruling out $r_v=1$ in a nontrivial PBD: if $v$ lies in a unique block $A$, then for each $u\neq v$ the unique block containing $\{u,v\}$ must be $A$, so $u\in A$, hence $A=[n]$, forcing triviality.
• Proposition 734.4: verified the averaging step and the pigeonhole count of possible sizes $\le \sqrt{2n}+1$.

6) FINAL. UNRESOLVED

(i) Strongest proved partial result: any nontrivial PBD satisfies $m\ge n$ (Lemma 734.3) and therefore must have some block size occurring at least $\frac{\sqrt n}{2\sqrt2}$ times (Proposition 734.4). This shows the target order $O(\sqrt n)$ multiplicity per size is best possible up to constants.

(ii) First gap: construct, for all sufficiently large $n$, a nontrivial PBD on $[n]$ in which every size class occurs at most $C\sqrt n$ times for an absolute constant $C$.

(iii) Top 3 next moves:

1. Recast as a clique decomposition of $K_n$ and attempt an explicit "many sizes" decomposition: choose $\Theta(\sqrt n)$ clique sizes each used $\Theta(\sqrt n)$ times so that total edge count matches $\binom{n}{2}$ and local degree constraints (Lemma 734.2) are satisfiable.
2. Attempt an inductive construction: start from a known PBD on $n_0$ points and add points while splitting/merging blocks so that size multiplicities stay $O(\sqrt n)$.
3. Computational exploration for moderate $n$ via SAT/ILP search on clique decompositions with multiplicity caps, to guess a workable pattern of block sizes.

(iv) Minimal counterexample structure (if such designs do not exist): an infinite set of integers $n$ such that every nontrivial PBD on $[n]$ has some size $t$ occurring more than $C\sqrt n$ times (for every fixed $C$), i.e., the minimum possible maximum multiplicity grows faster than $\sqrt n$.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.