gpt pro 5.2 attempt on Math-5932

Let $f(N)$ be the size of the largest quasi-Sidon subset $A\subset\{1,\ldots,N\}$, where we say that $A$ is quasi-Sidon if\[\lvert A+A\rvert=(1+o(1))\binom{\lvert A\rvert}{2}.\]How does $f(N)$ grow? Considered by Erdős and Freud [ErFr91], who proved\[\left(\frac{2}{\sqrt{3}}+o(1)\right)N^{1/2} \leq f(N) \leq \left(2+o(1)\right)N^{1/2}.\](Although both bounds were already given by Erdős in [Er81h].) Note that $2/\sqrt{3}=1.15\cdots$. The lower bound is taking a genuine Sidon set $B\subset [1,N/3]$ of size $\sim N^{1/2}/\sqrt{3}$ and taking the union with $\{N-b : b\in B\}$. The upper bound was improved by Pikhurko [Pi06] to\[f(N) \leq \left(\left(\frac{1}{4}+\frac{1}{(\pi+2)^2}\right)^{-1/2}+o(1)\right)N^{1/2}\](the constant here is $=1.863\cdots$). The analogous question with $A-A$ in place of $A+A$ is simpler, and there the maximal size is $\sim N^{1/2}$, as proved by Cilleruelo . See also [30] , [819] , and [864] . References [Er81h] Erdős, P., Some problems and results on additive and multiplicative number theory . Analytic number theory (Philadelphia, Pa., 1980) $1981$, 171-182. [ErFr91] Erdős, P. and Freud, R., On sums of a {S}idon-sequence . J. Number Theory $1991$, 196--205. [Pi06] Pikhurko, Oleg, Dense edge-magic graphs and thin additive bases . Discrete Math. $2006$, 2097--2107.

1) FORMAL RESTATEMENT

For $A\subseteq\{1,2,\dots,N\}$ define the sumset \[ A+A:=\{a+a': a,a'\in A\} \subseteq \{2,3,\dots,2N\}. \] Write $m:=|A|$. In asymptotic statements we consider sequences $A=A(N)$ with $m=m(N)\to\infty$.

Call $A$ quasi-Sidon if \[ |A+A| = (1+o(1))\binom{m}{2}, \] i.e. there exist errors $\varepsilon_N\to 0$ with \[ |A+A| = (1+\varepsilon_N)\binom{m}{2}. \] Define \[ f(N):=\max\{|A|: A\subseteq\{1,\dots,N\}\text{ is quasi-Sidon}\}. \] The question is: determine the growth rate of $f(N)$ (especially the leading constant in $f(N)\sim c\sqrt N$ if it exists).

2) QUICK LITERATURE/CONTEXT CHECK

I will not browse or use outside facts beyond the problem text. The problem text itself records that Erdős and Freud proved \[ \left(\frac{2}{\sqrt{3}}+o(1)\right)\sqrt N \le f(N) \le (2+o(1))\sqrt N, \] with a later improved upper constant $1.863\dots$. Below I (a) re-derive the easy universal upper bound $2\sqrt N+O(1)$ directly, and (b) fully verify the mechanism behind the stated lower bound (the "reflection" construction from a Sidon set).

3) ATTACK PLAN

• Prove the universal upper bound from $|A+A|\le 2N-1$.
• Prove that a genuine Sidon set is automatically quasi-Sidon.
• Prove the reflection lemma: if $B\subset[1,N/3]$ is Sidon then $A:=B\cup\{N-b:b\in B\}$ is quasi-Sidon and satisfies an explicit sumset count.
• Do a small-$N$ brute-force computation as a sanity check (exact Sidon maxima for $N\le 30$).

4) WORK

Fast reality check (exact Sidon maxima for small $N$). As a proxy for quasi-Sidon, I computed the maximum size of a genuine Sidon subset $B\subseteq\{1,\dots,N\}$ (all sums $b_i+b_j$ with $i\le j$ distinct) for $5\le N\le 30$. The exact maxima obtained were:

This is consistent with sizes on the order of $\sqrt N$.

Lemma 4.1 (Universal upper bound). If $A\subseteq\{1,\dots,N\}$ is quasi-Sidon with $|A|=m\to\infty$, then \[ m\le (2+o(1))\sqrt N. \] In particular $f(N)\le (2+o(1))\sqrt N$.

Proof. Since $A\subseteq\{1,\dots,N\}$ we have $2\le a+a'\le 2N$, hence $|A+A|\le 2N-1$. If $A$ is quasi-Sidon then $|A+A|=(1+o(1))\binom{m}{2}$, so for large $N$, \[ (1+o(1))\binom{m}{2} \le 2N. \] Using $\binom{m}{2}=\frac{m^2-m}{2}\sim \frac{m^2}{2}$ as $m\to\infty$, this implies $(1+o(1))\frac{m^2}{2}\le 2N$, i.e. $m^2\le (4+o(1))N$, hence $m\le (2+o(1))\sqrt N$. $\Box$

Lemma 4.2 (Sidon $\Rightarrow$ quasi-Sidon). Let $A\subseteq\{1,\dots,N\}$ have $|A|=m\to\infty$. Assume $A$ is a genuine Sidon set in the sense that all sums $a+a'$ with $a\le a'$ are distinct. Then \[ |A+A| = \binom{m}{2}+m = \left(1+O\left(\frac{1}{m}\right)\right)\binom{m}{2}, \] so $A$ is quasi-Sidon.

Proof. Distinctness of sums for $a\le a'$ means there is exactly one sum for each unordered pair $\{a,a'\}$, with $a\ne a'$ contributing $\binom{m}{2}$ sums and $a=a'$ contributing $m$ diagonal sums $2a$. Thus $|A+A|=\binom{m}{2}+m$. Dividing by $\binom{m}{2}$ gives $1+\frac{m}{\binom{m}{2}}=1+\frac{2}{m-1}=1+O(1/m)=1+o(1)$. $\Box$

Lemma 4.3 (Reflection construction from a Sidon set). Let $N\ge 1$ and let $B\subseteq\{1,\dots,\lfloor N/3\rfloor\}$ be a genuine Sidon set with $|B|=t\to\infty$. Define \[ C:=\{N-b: b\in B\}\subseteq\{\lceil 2N/3\rceil,\dots,N-1\}, \qquad A:=B\cup C. \] Then $|A|=2t$ and \[ |A+A| = 2t^2+1. \] In particular \[ |A+A| = \left(1+O\left(\frac{1}{t}\right)\right)\binom{|A|}{2}, \] so $A$ is quasi-Sidon.

iProof. We decompose $A+A$ into three disjoint ranges:

• $B+B \subseteq [2,2\lfloor N/3\rfloor] \subseteq [2,2N/3]$;
• $C+C = (N-B)+(N-B)=2N-(B+B) \subseteq [4N/3,2N-2]$;
• $B+C = B+(N-B)=N+(B-B) \subseteq [\lceil 2N/3\rceil+1, \lfloor 4N/3\rfloor-1]$.

These intervals are pairwise disjoint, so \[ |A+A| = |B+B| + |C+C| + |B+C|. \] Because $B$ is Sidon, all sums $b+b'$ with $b\le b'$ are distinct, hence \[ |B+B|=\frac{t(t+1)}{2}. \] The map $s\mapsto 2N-s$ is a bijection between $B+B$ and $C+C$, so $|C+C|=|B+B|=t(t+1)/2$.

It remains to compute $|B+C|$. Note that $B+C = \{N + (b-b'): b,b'\in B\}$, so $|B+C| = |B-B|$. We claim that for a Sidon set, ordered differences are unique except for the zero difference: if \[ b_1-b_2=b_3-b_4 \] with $b_i\in B$ and $b_1\ne b_2$, then $(b_1,b_2)=(b_3,b_4)$. Indeed, the difference equality rearranges to \[ b_1+b_4 = b_3+b_2. \] By the Sidon property (uniqueness of sums as unordered pairs), the multiset $\{b_1,b_4\}$ must equal $\{b_3,b_2\}$. If $b_1\ne b_2$ then necessarily $b_1=b_3$ and $b_4=b_2$, which forces $b_2=b_4$ and then also $b_2=b_4$; in particular $(b_1,b_2)=(b_3,b_4)$. Thus every nonzero ordered difference $b-b'$ occurs exactly once, while the zero difference occurs for every pair $(b,b)$. Hence \[ |B-B| = 1 + (t^2-t) = t^2-t+1. \] Therefore \[ |A+A| = \frac{t(t+1)}{2}+\frac{t(t+1)}{2}+(t^2-t+1) = t(t+1)+t^2-t+1 = 2t^2+1. \] Finally, $\binom{|A|}{2}=\binom{2t}{2}=2t^2-t$, and \[ \frac{|A+A|}{\binom{|A|}{2}} = \frac{2t^2+1}{2t^2-t} = 1 + \frac{t+1}{2t^2-t} = 1+O\left(\frac{1}{t}\right)=1+o(1), \] so $A$ is quasi-Sidon. $\Box$

Comment (how the stated lower bound arises). Lemma 4.3 shows that if one has a Sidon set $B\subseteq[1,N/3]$ of size $t\sim \sqrt{N/3}$, then the reflected union produces a quasi-Sidon set of size $|A|=2t\sim \frac{2}{\sqrt3}\sqrt N$. The existence of such $B$ (and hence the stated lower bound) is part of what the problem text attributes to Erdős and Freud.

5) VERIFICATION

• Lemma 4.1 uses only the trivial range $A+A\subseteq\{2,\dots,2N\}$.
• Lemma 4.2 correctly counts diagonal sums $2a$ separately from off-diagonal sums.
• In Lemma 4.3 the disjointness of the three sum ranges is checked via the bounds $B\subseteq[1,N/3]$ and $C\subseteq[2N/3,N]$.
• The difference-uniqueness claim used in Lemma 4.3 was derived directly from the Sidon sum-uniqueness property.

6) FINAL

UNRESOLVED

(i) Strongest proved partial result. A direct proof of the universal upper bound $f(N)\le (2+o(1))\sqrt N$ (Lemma 4.1), and a complete verification that the "reflection" construction from a Sidon set $B\subset[1,N/3]$ produces a quasi-Sidon set $A$ with an exact sumset count $|A+A|=2|B|^2+1$ (Lemma 4.3).

(ii) First gap (crisp). Determine the optimal constant $c$ (or even narrow it to a single value) such that $f(N)=(c+o(1))\sqrt N$.

(iii) Top 3 next moves.

1. Identify and analyze candidate extremal constructions for quasi-Sidon sets (e.g., reflected Sidon-type constructions), and compute their achieved constant.
2. Prove a structural theorem: if $|A+A|=(1+o(1))\binom{|A|}{2}$ then $A$ must resemble (in a precise sense) a Sidon set or a reflected Sidon set; turn this into a sharper upper bound on $|A|$.
3. Compute exact/near-exact values of $f(N)$ for moderate $N$ (via ILP / SAT / backtracking) under a concrete finite-$N$ proxy for "$o(1)$", to conjecture the limiting constant.

(iv) What a minimal counterexample would likely look like. Any counterexample to a conjectured constant $c$ would be a family $A\subseteq[1,N]$ with $|A|\approx c\sqrt N$ in which almost all pair sums are distinct, but whose sumset still fits inside $[2,2N]$. Such a set must have very few additive collisions, so it should be close to a Sidon set (possibly after a reflection/translation), and the obstruction to improving the constant should come from a delicate packing of nearly distinct sums into the fixed interval.