gpt pro 5.2 attempt on Math-652, version 2

Round 2: A variance method lower bound

Round-2 objective

We pursue path (A) (proof direction: a stronger universal lower bound). Round 1 established the averaging bound $\max_x r(x)>N/4$ (Lemma 36.1) and exhibited an interval construction with $\max_x r(x)=N/2$ for even $N$ (Lemma 36.2). The principal gap left in Round 1 is to improve the universal lower bound toward the best-known constants. In this round we prove a strictly stronger, fully rigorous universal estimate: \[ \max_x r(x)\ \ge\ \frac{N}{\sqrt{8-\frac{1}{N^2}}}\ >\ \frac{N}{\sqrt 8}. \] In particular, the minimum overlap constant satisfies $c\ge 1/\sqrt 8\approx 0.353553$, improving the Round 1 bound $c\ge 1/4$.

Round-1 foundation used

We use the following Round 1 results as black boxes (no re-proofs):

• The setup: a partition $A\sqcup B=\{1,2,\dots,2N\}$ with $|A|=|B|=N$, and $r(x)=\#\{(a,b)\in A\times B: a-b=x\}$.
• The counting identity $\sum_x r(x)=N^2$, hence Lemma 36.1: $\max_x r(x)\ge N^2/(4N-1)>N/4$.
• Lemma 36.2 (interval construction) as a sanity check; it is not used in the proofs below.

New insight / tool (Round-2)

The new ingredient is a second-moment constraint. Choose independent random variables $a\sim \mathrm{Unif}(A)$ and $b\sim \mathrm{Unif}(B)$, and set $D:=a-b$. Then \[ \mathbb P(D=x)=\frac{r(x)}{N^2},\qquad \max_x\mathbb P(D=x)=\frac{\max_x r(x)}{N^2}. \] We combine:

• an upper bound on $\mathrm{Var}(D)$ coming only from the fact that $A$ and $B$ are complementary equal halves of $[2N]$, and
• a lower bound on $\mathrm{Var}(D)$ in terms of the maximum atom $\max_x\mathbb P(D=x)$, obtained by smoothing an integer-valued law by a continuous uniform random variable.

Attack plan (Round-2)

The Round 1 gap is that averaging alone forces only $\max_x r(x)\gtrsim N/4$. To improve this, we:

1. interpret $r(x)/N^2$ as the law of $D=a-b$;
2. show $\mathrm{Var}(D)\le (4N^2-1)/6$;
3. show that if $p:=\max_x\mathbb P(D=x)$ then $\mathrm{Var}(D)\ge \frac{1}{12p^2}-\frac{1}{12}$;
4. combine $2$--$3$ and solve for $p$, hence for $\max_x r(x)$.

Work (Round-2)

Let \[ M:=\max_x r(x). \] With $D=a-b$ as above, we have \[ \max_x\mathbb P(D=x)=\frac{M}{N^2}. \]

Lemma 36.3 (variance upper bound for $D=a-b$). For every partition $A\sqcup B=[2N]$ with $|A|=|B|=N$, \[ \mathrm{Var}(D)\ \le\ \frac{4N^2-1}{6}. \]

Proof. Since $a$ and $b$ are independent, $\mathrm{Var}(D)=\mathrm{Var}(a)+\mathrm{Var}(b)$. Write \[ S:=\sum_{i=1}^{2N} i = N(2N+1),\qquad Q:=\sum_{i=1}^{2N} i^2=\frac{(2N)(2N+1)(4N+1)}{6}. \] Let $A_1:=\sum_{a\in A}a$ and $A_2:=\sum_{a\in A}a^2$, so $B_1=S-A_1$, $B_2=Q-A_2$. Then \[ \mathrm{Var}(a)=\frac{A_2}{N}-\left(\frac{A_1}{N}\right)^2, \qquad \mathrm{Var}(b)=\frac{B_2}{N}-\left(\frac{B_1}{N}\right)^2. \] Hence \[ \mathrm{Var}(a)+\mathrm{Var}(b) =\frac{A_2+B_2}{N}-\frac{A_1^2+B_1^2}{N^2} =\frac{Q}{N}-\frac{A_1^2+(S-A_1)^2}{N^2}. \] But \[ A_1^2+(S-A_1)^2 =2\left(A_1-\frac{S}{2}\right)^2+\frac{S^2}{2}\ \ge\ \frac{S^2}{2}. \] Therefore \[ \mathrm{Var}(D)\le \frac{Q}{N}-\frac{S^2}{2N^2}. \] Compute $\frac{Q}{N}=\frac{(2N+1)(4N+1)}{3}$ and $\frac{S^2}{2N^2}=\frac{(2N+1)^2}{2}$, so \[ \mathrm{Var}(D) \le (2N+1)\left(\frac{4N+1}{3}-\frac{2N+1}{2}\right) =(2N+1)\cdot\frac{2N-1}{6} =\frac{4N^2-1}{6}. \] $\square$

Lemma 36.4 (integer-valued variance lower bound from bounded atoms). Let $X$ be an integer-valued random variable such that $\mathbb P(X=k)\le p$ for all $k\in\mathbb Z$, where $0<p\le 1$. Then \[ \mathrm{Var}(X)\ \ge\ \frac{1}{12p^2}-\frac{1}{12}. \]

Proof. Let $U\sim\mathrm{Unif}(-\tfrac12,\tfrac12)$ be independent of $X$, and set $Y:=X+U$. For each integer $k$, on the interval $[k-\tfrac12,k+\tfrac12)$ the density of $Y$ equals $\mathbb P(X=k)$, so $Y$ has a density $f$ satisfying \[ 0\le f(y)\le p\ \text{ for all }y\in\mathbb R,\qquad \int_{\mathbb R} f(y)\,dy=1. \] Let $\mu:=\mathbb E[Y]$ and $Z:=Y-\mu$. Then $\mathrm{Var}(Y)=\mathbb E[Z^2]$ and the density of $Z$ is a translate of $f$, hence also bounded by $p$. Therefore, for any $r\ge 0$, \[ \mathbb P(|Z|\le r)\le \int_{-r}^{r} p\,dt=2rp, \quad\text{so}\quad \mathbb P(|Z|>r)\ge \max(0,1-2rp). \] Using the tail integral identity \[ \mathbb E[Z^2]=\int_0^{\infty} \mathbb P(Z^2>t)\,dt =\int_0^{\infty} 2r\,\mathbb P(|Z|>r)\,dr \] (the second equality is the substitution $t=r^2$, $dt=2r\,dr$), we obtain \[ \mathrm{Var}(Y)=\mathbb E[Z^2] \ge \int_0^{1/(2p)} 2r(1-2rp)\,dr =\left[r^2-\frac{4p}{3}r^3\right]_{0}^{1/(2p)} =\frac{1}{12p^2}. \] Finally, since $Y=X+U$ with $X\perp U$, $ \mathrm{Var}(Y)=\mathrm{Var}(X)+\mathrm{Var}(U)=\mathrm{Var}(X)+1/12 $. Thus $ \mathrm{Var}(X)+1/12\ge 1/(12p^2) $, i.e. $ \mathrm{Var}(X)\ge 1/(12p^2)-1/12 $. $\square$

Theorem 36.5 (universal lower bound $>N/\sqrt8$). For every $N\ge 1$ and every partition $A\sqcup B=[2N]$ with $|A|=|B|=N$, \[ M=\max_x r(x)\ \ge\ \frac{N}{\sqrt{8-\frac{1}{N^2}}}\ >\ \frac{N}{\sqrt 8}. \] Consequently the minimum overlap constant satisfies $c\ge 1/\sqrt 8\approx 0.353553$.

Proof. Apply Lemma 36.4 to $X=D$. Here $p:=\max_x\mathbb P(D=x)=M/N^2$, so Lemma 36.4 gives \[ \mathrm{Var}(D)\ \ge\ \frac{1}{12p^2}-\frac{1}{12} =\frac{N^4}{12M^2}-\frac{1}{12}. \] Lemma 36.3 gives the universal upper bound $\mathrm{Var}(D)\le (4N^2-1)/6$. Combining, \[ \frac{N^4}{12M^2}-\frac{1}{12}\ \le\ \frac{4N^2-1}{6} \quad\Rightarrow\quad \frac{N^4}{12M^2}\ \le\ \frac{8N^2-1}{12}. \] Multiplying by $12$ and rearranging yields $ N^4/M^2\le 8N^2-1 $, hence \[ M^2\ \ge\ \frac{N^4}{8N^2-1} \quad\Rightarrow\quad M\ \ge\ \frac{N^2}{\sqrt{8N^2-1}}=\frac{N}{\sqrt{8-\frac{1}{N^2}}}. \] This proves the theorem. $\square$

Adversarial verification

• Distribution identity. Each ordered pair $(a,b)\in A\times B$ is equally likely, so $\mathbb P(D=x)=r(x)/N^2$ exactly.
• Lemma 36.4 hypotheses. The only hypothesis is that $X$ is integer-valued and its atoms are bounded by $p$. Smoothing by $U$ converts the discrete law to a continuous density bounded by $p$ on all of $\mathbb R$, so the interval bound $\mathbb P(|Z|\le r)\le 2rp$ is valid.
• Tail integral identity. The identity $\mathbb E[Z^2]=\int_0^{\infty} \mathbb P(Z^2>t)dt$ holds for nonnegative random variables by Tonelli's theorem; the substitution $t=r^2$ is elementary.
• Small $N$. For $N=1$, the bound gives $M\ge 1/\sqrt 7$, which forces $M\ge 1$ since $M\in\mathbb Z_{\ge 1}$. No exceptional cases arise.
• Consistency with Round 1 computations. The exhaustive table for $N\le 11$ in Round 1 has $M(N)/N\ge 0.429\ldots$, which is comfortably above $1/\sqrt 8$.

Final

UNRESOLVED (but strictly advanced). We have improved the universal lower bound from Lemma 36.1: $\max_x r(x) > N/4$ to the stronger bound of Theorem 36.5: $\max_x r(x) > N/\sqrt 8$. The exact optimal constant $c$ remains open.

Completion estimate

COMPLETION: 45%.

References

• Round 1 notes and computations contained in 36.tex.
• Ethan Patrick White, "Erdős' minimum overlap problem," arXiv:2201.05704.

Round 3: Sharpness of the variance method and a barrier at $1/\sqrt 8$

Round-3 objective

We pursue path (A) (proof direction), but in "gap-closure" mode: the Round 2 lower bound $c\ge 1/\sqrt 8$ is still far below the current record range. The main goal of this round is to isolate (with proof) why the variance method of Round 2 cannot be pushed past $1/\sqrt 8$ without injecting genuinely new structure. Concretely, we prove that both ingredients of Round 2---the variance upper bound (Lemma 36.3) and the atom/variance lower bound (Lemma 36.4)---are individually sharp, and hence the constant $1/\sqrt 8$ is an intrinsic barrier for any argument that treats $D=a-b$ only as an arbitrary integer-valued law with bounded variance.

For context (not used in the proofs below), the current record bounds for the asymptotic constant are extremely narrow: $0.379005 < c < 0.380924$ (White's lower bound and AlphaEvolve's upper bound).

Round-2 foundation used

We use the following Round 2 statements as black boxes:

• Lemma 36.3: for every partition $A\sqcup B=[2N]$ with $|A|=|B|=N$, the random difference $D=a-b$ satisfies $\mathrm{Var}(D)\le (4N^2-1)/6$.
• Lemma 36.4: for any integer-valued random variable $X$ with $\max_k \mathbb P(X=k)\le p$, $\mathrm{Var}(X)\ge 1/(12p^2)-1/12$.
• Theorem 36.5: combining the two yields $\max_x r(x)\ge N/\sqrt{8-1/N^2}>N/\sqrt 8$.

New insight / tool (Round-3)

The new content is a sharpness and barrier analysis:

• We identify an equality case for Lemma 36.4 (discrete uniform distributions), proving that Lemma 36.4 cannot be improved under its stated hypotheses.
• We give an explicit partition $A\sqcup B=[2N]$ (for even $N$) achieving equality in Lemma 36.3, proving that the variance upper bound is also best possible.
• We combine these to formalize a "variance-method barrier": no proof that only inputs "$D$ is integer-valued" and "$\mathrm{Var}(D)\le (4N^2-1)/6$" can yield a universal constant better than $1/\sqrt 8$.
• As a byproduct, we extract a structural necessary condition: any near-extremal configuration with $\max_x r(x)$ close to $N/\sqrt 8$ must have its first moment nearly balanced ($\sum_{a\in A} a$ close to $\sum_{b\in B} b$).

Attack plan (Round-3)

The gap after Round 2 is that the best-known constants are near $0.38$, while the variance method yields only $1/\sqrt 8\approx 0.3536$. To understand what is missing, we:

1. prove sharpness of the atom/variance inequality (Lemma 36.4);
2. prove sharpness of the variance upper bound (Lemma 36.3);
3. conclude that improving Theorem 36.5 requires new constraints on the law of $D$ beyond its variance (e.g. constraints coming from the fact that $D$ is a difference of two uniform measures supported on complementary subsets of $[2N]$).

Work (Round-3)

Lemma 36.6 (sharpness of Lemma 36.4). For each integer $m\ge 0$, let $X$ be uniform on $\{-m,-m+1,\dots,m\}$. Then $\max_k \mathbb P(X=k)=p=1/(2m+1)$ and \[ \mathrm{Var}(X)=\frac{1}{12p^2}-\frac{1}{12}. \] In particular, Lemma 36.4 is best possible as stated.

Proof. Here $p=1/(2m+1)$. By symmetry $\mathbb E[X]=0$ and \[ \mathrm{Var}(X)=\mathbb E[X^2]=\frac{1}{2m+1}\sum_{k=-m}^m k^2 =\frac{2}{2m+1}\sum_{k=1}^m k^2 =\frac{2}{2m+1}\cdot\frac{m(m+1)(2m+1)}{6} =\frac{m(m+1)}{3}. \] On the other hand, \[ \frac{1}{12p^2}-\frac{1}{12}=\frac{(2m+1)^2-1}{12}=\frac{4m(m+1)}{12}=\frac{m(m+1)}{3}, \] so equality holds. $\square$

Lemma 36.7 (sharpness of Lemma 36.3 for even $N$). Assume $N$ is even and set \[ A:=\{1,2,\dots,\tfrac{N}{2}\}\ \cup\ \{\tfrac{3N}{2}+1,\tfrac{3N}{2}+2,\dots,2N\}, \qquad B:=[2N]\setminus A. \] Then $|A|=|B|=N$ and for the associated random difference $D=a-b$, \[ \mathrm{Var}(D)=\frac{4N^2-1}{6}. \] Hence the variance upper bound of Lemma 36.3 is attained.

Proof. The set $A$ consists of $N/2$ pairs $(i,2N+1-i)$ for $1\le i\le N/2$. Each such pair sums to $2N+1$, hence \[ A_1:=\sum_{a\in A} a=\frac{N}{2}(2N+1)=\frac{S}{2}, \qquad S:=\sum_{j=1}^{2N} j = N(2N+1). \] Therefore also $B_1=S-A_1=S/2$, i.e. $A_1=B_1$. In the computation of Lemma 36.3 we had \[ \mathrm{Var}(D)=\frac{Q}{N}-\frac{A_1^2+B_1^2}{N^2}, \qquad Q:=\sum_{j=1}^{2N} j^2. \] Since $A_1=B_1=S/2$, we have $A_1^2+B_1^2=S^2/2$, which is exactly the minimal value used in Lemma 36.3. Thus equality holds throughout the proof of Lemma 36.3 and $\mathrm{Var}(D)=Q/N-S^2/(2N^2)=(4N^2-1)/6$. $\square$

Theorem 36.8 (variance-method barrier at $1/\sqrt 8$). Consider the class of all integer-valued random variables $X$ with $\mathrm{Var}(X)\le (4N^2-1)/6$. For such $X$, any lower bound of the form $\max_k \mathbb P(X=k)\ge C/N$ valid for all $N$ must satisfy $C\le 1/\sqrt 8$. Equivalently, the constant $1/\sqrt 8$ appearing in Theorem 36.5 is optimal for any argument that uses only the information "$D$ is integer-valued" and "$\mathrm{Var}(D)\le (4N^2-1)/6$".

Proof. Fix $N\ge 1$ and define $m:=\lfloor \sqrt{2}\,N-1\rfloor$. Let $X$ be uniform on $\{-m,-m+1,\dots,m\}$. Then by Lemma 36.6, \[ \max_k \mathbb P(X=k)=\frac{1}{2m+1} \quad\text{and}\quad \mathrm{Var}(X)=\frac{m(m+1)}{3}. \] Using $m\le \sqrt{2}N-1$, we have \[ m(m+1)\le (\sqrt{2}N-1)(\sqrt{2}N)=2N^2-\sqrt{2}N\le 2N^2-\tfrac12, \] hence \[ \mathrm{Var}(X)=\frac{m(m+1)}{3}\le \frac{2N^2-\tfrac12}{3}=\frac{4N^2-1}{6}. \] Therefore $X$ belongs to the stated variance-bounded class. But also \[ \frac{1}{2m+1}=\frac{1+o(1)}{2\sqrt{2}\,N}=\frac{1+o(1)}{\sqrt{8}\,N} \qquad (N\to\infty). \] Consequently, no universal inequality of the form $\max_k \mathbb P(X=k)\ge C/N$ can hold with $C>1/\sqrt 8$ on this class. $\square$

Corollary 36.9 (near-extremizers force near-balanced first moment). Let $A\sqcup B=[2N]$, $|A|=|B|=N$, and write $A_1:=\sum_{a\in A} a$, $S:=\sum_{j=1}^{2N} j=N(2N+1)$, and $\delta:=A_1-S/2$. Let $M:=\max_x r(x)$. Then \[ \delta^2\ \le\ \frac{N^2}{2}\left(\frac{4N^2-1}{6}-\frac{N^4}{12M^2}+\frac{1}{12}\right). \] In particular, if $M\le cN$ for some fixed $c$, then $|\delta|=O(N^2)$, and as $c\downarrow 1/\sqrt 8$ the right-hand side forces $|\delta|=o(N^2)$.

Proof. From the identity in the proof of Lemma 36.3 we have the exact formula \[ \mathrm{Var}(D)=\frac{Q}{N}-\frac{A_1^2+(S-A_1)^2}{N^2} =\frac{4N^2-1}{6}-\frac{2\delta^2}{N^2}. \] (Indeed, $A_1^2+(S-A_1)^2=2\delta^2+S^2/2$.) On the other hand, Theorem 36.5 begins with the inequality (from Lemma 36.4) $ \mathrm{Var}(D)\ge N^4/(12M^2)-1/12. $ Combining yields \[ \frac{4N^2-1}{6}-\frac{2\delta^2}{N^2}\ \ge\ \frac{N^4}{12M^2}-\frac{1}{12}, \] which rearranges to the claimed bound on $\delta^2$. $\square$

Adversarial verification

• Lemma 36.6. The variance computation is exact and the equality check against $1/(12p^2)-1/12$ is algebraic; no hidden regularity assumptions are used.
• Lemma 36.7. The construction requires $N$ even to make the endpoints $N/2$ and $3N/2$ integral. The sum identity uses the explicit pairing $(i,2N+1-i)$. Equality in Lemma 36.3 is correctly characterized by $A_1=B_1$, which holds here.
• Theorem 36.8. We only claim a methodological barrier for variance-only arguments. The random variables $X$ used in the proof need not arise as $a-b$ for any partition; this is intentional, as the theorem is about what can be deduced from variance constraints alone.
• Corollary 36.9. The exact variance formula is consistent with Lemma 36.3 (it immediately implies Lemma 36.3 because $\delta^2\ge 0$). The rearrangement is straightforward.

Final

UNRESOLVED (but strictly advanced). Beyond the Round 2 bound $c\ge 1/\sqrt 8$, we have now proved that $1/\sqrt 8$ is a genuine barrier for the entire "variance-only" proof strategy: improving the universal lower bound requires additional structural constraints on the representation function $r$, not just its second moment. We also extracted a quantitative structural condition (Corollary 36.9) showing that near-extremizers must have nearly balanced first moment.

Completion estimate

COMPLETION: 55%.

References

• Round 2 notes in 36_v2.tex.
• T. F. Bloom (ed.), Erdős Problem #36 discussion thread ("minimum overlap problem"), online resource.
• Ethan Patrick White, "Erdős' minimum overlap problem," arXiv:2201.05704.