gpt pro 5.2 attempt on Math-5852

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$.