Erdős Problem #840

Erdős Problem 840 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/840

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/840.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/840.tex.

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.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

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.