gpt pro 5.2 attempt on Math-654

Erdős Problem #40

FORMAL RESTATEMENT

For $A\subseteq\mathbb N$ let $1_A$ be its indicator function and define the additive convolution \[ (1_A*1_A)(n):=\sum_{k\in\mathbb Z}1_A(k)\,1_A(n-k), \] which counts ordered representations $n=a+b$ with $a,b\in A$.

Given a function $g:\mathbb N\to(0,\infty)$ with $g(N)\to\infty$, determine for which $g$ the following implication holds: \[ \left(\exists c>0\ \forall N\ge N_0:\ |A\cap[1,N]|\ge c\,\frac{N^{1/2}}{g(N)}\right)\ \Longrightarrow\ \limsup_{n\to\infty}(1_A*1_A)(n)=\infty. \]

QUICK LITERATURE/CONTEXT CHECK

The problem statement notes this is a strengthening of another conjecture (Erdős--Turán, referenced as [28] there). I do not use any outside results; the work below is limited to basic double-counting bounds that are unconditional.

ATTACK PLAN

Proof track: Combine density information $|A\cap[1,N]|$ with additive-energy estimates to force some $n$ with many representations.

Disproof track: Construct sets $A$ with $|A\cap[1,N]|$ close to $N^{1/2}/g(N)$ while keeping $(1_A*1_A)(n)$ bounded, thereby falsifying the implication.

Here I only obtain basic necessary/insufficient conditions from first-moment bounds.

WORK

Fast reality check.

For $A=[1,m]$ we have $|A\cap[1,N]|=\min\{m,N\}$ and $(1_A*1_A)(n)$ is of order $m$ for $n\approx m$, so unboundedness is easy for very dense $A$. Conversely, for a finite Sidon set $A\subseteq[1,N]$ all sums are distinct so $(1_A*1_A)(n)\le 2$, showing bounded representation is compatible with size $\asymp \sqrt N$ for a single scale $N$.

Lemma 40.1 (average representation lower bound).

Let $A\subseteq\mathbb N$ and fix $N\ge1$. Put $m:=|A\cap[1,N]|$ and define \[ r_N(n):=\sum_{k=1}^{N}1_A(k)\,1_A(n-k) \quad\text{for }2\le n\le 2N, \] which counts ordered representations $n=a+b$ with $a,b\in A\cap[1,N]$. Then \[ \sum_{n=2}^{2N} r_N(n)\ =\ m^2, \qquad\text{hence}\qquad \max_{2\le n\le 2N} r_N(n)\ \ge\ \frac{m^2}{2N-1}. \]

Proof. We double-count ordered pairs $(a,b)\in (A\cap[1,N])^2$. Each ordered pair contributes $1$ to exactly one value of $r_N(n)$, namely $n=a+b\in[2,2N]$. Therefore \[ \sum_{n=2}^{2N} r_N(n)=|(A\cap[1,N])|^2=m^2. \] Averaging over the $2N-1$ integers $n\in\{2,3,\dots,2N\}$ gives the stated maximum lower bound. $\square$

Lemma 40.2 (bounded representation forces $|A\cap[1,N]|\ll \sqrt N$).

Assume there exists $R\ge1$ such that $(1_A*1_A)(n)\le R$ for all $n\in\mathbb N$. Then for every $N\ge1$, \[ |A\cap[1,N]|\ \le\ \sqrt{R(2N-1)}\ <\ \sqrt{2RN}. \]

Proof. With $m=|A\cap[1,N]|$ and $r_N(n)$ as in Lemma 40.1, note $r_N(n)\le (1_A*1_A)(n)\le R$ for all $n$ (because $r_N(n)$ counts only representations using summands $\le N$). Hence \[ m^2\ =\ \sum_{n=2}^{2N} r_N(n)\ \le\ \sum_{n=2}^{2N} R\ =\ R(2N-1). \] Taking square roots yields the claim. $\square$

VERIFICATION

• Lemma 40.1: checked the sum is over exactly $2N-1$ integers and that every ordered pair contributes exactly once.
• Lemma 40.2: the inequality $r_N(n)\le (1_A*1_A)(n)$ holds because $r_N$ restricts to summands in $[1,N]$.
• Note these bounds are too weak for the regime $m\asymp \sqrt N/g(N)$ with $g(N)\to\infty$, since then $m^2/(2N)\asymp 1/g(N)^2\to0$.

FINAL

UNRESOLVED

(i) Strongest proved partial result. If $(1_A*1_A)(n)$ is uniformly bounded by $R$, then necessarily $|A\cap[1,N]|<\sqrt{2RN}$ for all $N$ (Lemma 40.2). Conversely, for any $N$, any set $A\cap[1,N]$ of size $m$ forces some $n\le 2N$ to have at least $m^2/(2N-1)$ ordered representations using summands $\le N$ (Lemma 40.1).

(ii) First gap (crisp statement). I cannot determine (prove or refute) whether there exists any divergent $g(N)$ for which \[|A\cap[1,N]|\gg \frac{\sqrt N}{g(N)}\ \text{for all large $N$}\] already forces $\limsup_n (1_A*1_A)(n)=\infty$.

(iii) Top 3 next moves (concrete).

1. Try to prove a second-moment/energy bound: show that if $|A\cap[1,N]|$ is as large as $\sqrt N/g(N)$ for all large $N$, then $\sum_{n\le 2N}(1_A*1_A)(n)^2$ must be large enough to force a large maximum by Cauchy--Schwarz.
2. Attempt an explicit construction (disproof track): build $A$ as a union of well-separated finite sets with bounded additive representation (e.g. near-Sidon blocks) while maintaining the required lower bound on $|A\cap[1,N]|$.
3. Computation: for candidate $g$ (e.g. $\log\log N$), search numerically for finite sets $A\subseteq[1,N]$ of size $\approx \sqrt N/g(N)$ minimizing $\max_n (1_A*1_A)(n)$, to guess the threshold behavior.

(iv) What a minimal counterexample would likely look like. A counterexample for a specific slowly growing $g$ would likely be a "block-union" set $A$ whose initial segments $A\cap[1,N]$ behave like near-optimal $B_2[O(1)]$ sets at each scale (so representation counts stay bounded), with blocks spaced so that cross-block sums do not pile up.