Erdős Problem #819

Erdős Problem 819 --- collection record

PROVENANCE AND STATUS

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

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/819.tex.

REUSED SOURCE 1

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

Erdos Problem #819

FORMAL RESTATEMENT.

For each positive integer $N$, let \[ m := \lfloor N^{1/2}\rfloor. \] Define $f(N)$ to be the maximum of \[ |(A+A)\cap [1,N]| \] over all subsets $A\subseteq\{1,2,\dots,N\}$ with $|A|=m$, where $A+A:=\{a+b:\ a,b\in A\}$ and $[1,N]=\{1,2,\dots,N\}$. The problem asks to estimate $f(N)$.

QUICK LITERATURE/CONTEXT CHECK.

The statement records that Erdős and Freud proved \[ \left(\frac{3}{8}-o(1)\right)N \le f(N) \le \left(\frac{1}{2}+o(1)\right)N. \] I do not use any results not already stated in the problem text.

ATTACK PLAN.

Upper bounds: use counting of unordered pairs to control how many distinct sums can appear. Lower bounds: construct explicit $A$ producing many sums in $[1,N]$; as a baseline, compute small $N$ exactly to see what is achievable.

WORK.

Lemma 819.1 (unconditional counting upper bound). Let $m=\lfloor \sqrt N\rfloor$. For every $A\subseteq[1,N]$ with $|A|=m$, \[ |(A+A)\cap[1,N]| \le \binom{m+1}{2} = \frac{m(m+1)}{2} \le \frac{N}{2} + O(\sqrt N). \]

Proof. Every sum $s\in A+A$ can be represented as $s=a+b$ with $a,b\in A$. If we ignore order, each unordered pair $\{a,b\}$ with $a,b\in A$ produces at most one sum. There are exactly $\binom{m}{2}$ unordered pairs with $a\ne b$ and $m$ diagonal pairs $\{a,a\}$, so in total there are $\binom{m}{2}+m=\binom{m+1}{2}$ unordered pairs. Distinct sums are at most the number of unordered pairs, hence $|A+A|\le \binom{m+1}{2}$, and a fortiori $|(A+A)\cap[1,N]|\le \binom{m+1}{2}$. Since $m^2\le N < (m+1)^2$, we have $m^2\le N$ and $m\le \sqrt N$, giving $\binom{m+1}{2}\le \frac{1}{2}N + O(\sqrt N)$. $\square$

Lemma 819.2 (baseline lower bound). For $m=\lfloor\sqrt N\rfloor$, taking $A=\{1,2,\dots,m\}$ gives \[ |(A+A)\cap[1,N]| \ge 2m-1 = 2\lfloor\sqrt N\rfloor-1. \]

Proof. If $A=\{1,2,\dots,m\}$ then \[ A+A = \{2,3,\dots,2m\}. \] All these sums are $\le 2m\le 2\sqrt N\le N$ for $N\ge4$; in any case, $(A+A)\cap[1,N]$ contains $\{2,3,\dots,2m\}$. Thus $|(A+A)\cap[1,N]|\ge 2m-1$. $\square$

FAST REALITY CHECK (exact values for $N\le 30$). I exhaustively computed $f(N)$ for $1\le N\le 30$ by enumerating all subsets $A\subseteq[1,N]$ of size $m=\lfloor\sqrt N\rfloor$. The maximal values found were: \[ \begin{array}{c|c|c} N & m & f(N)\\\hline 1 & 1 & 0\\ 2\le N\le 3 & 1 & 1\\ 4\le N\le 8 & 2 & 3\\ 9\le N\le 15 & 3 & 6\\ 16\le N\le 24 & 4 & 10\\ 25\le N\le 30 & 5 & 15 \end{array} \] For example, at $N=16$ the set $A=\{1,2,4,8\}$ achieves $f(16)=10$.

VERIFICATION.

Lemma 819.1: the only step is the injection "distinct sums $\le$ unordered pairs"; this is valid because each unordered pair produces a single integer sum, though multiple pairs may collide. Lemma 819.2: sums of the initial segment form the full interval $[2,2m]$; checking the intersection with $[1,N]$ is immediate. The computed $f(N)$ values are finite enumerations and can be rechecked.

FINAL.

UNRESOLVED.

1. (i) Strongest proved partial results here: the unconditional upper bound $f(N)\le \binom{\lfloor\sqrt N\rfloor+1}{2} = \frac{1}{2}N+O(\sqrt N)$ (Lemma 819.1), matching the scale of the upper bound stated in the problem, and the explicit lower bound $f(N)\ge 2\lfloor\sqrt N\rfloor-1$ (Lemma 819.2). Exact values for $N\le 30$ were computed.
2. (ii) First gap: produce (or rigorously derive) a linear-in-$N$ lower bound $f(N)\ge cN$ with an explicit constant $c>0$ using only arguments developed here (i.e. without importing the stated Erdős--Freud result).
3. (iii) Top 3 next moves: $1$ attempt a probabilistic construction of a size-$\sqrt N$ set $A$ for which many $s\le N$ have at least one representation $s=a+b$; $2$ search computationally for maximizers for larger $N$ (e.g. $N\le 60$) to guess structure; $3$ prove structural lemmas relating large $|(A+A)\cap[1,N]|$ to quasi-Sidon behaviour (few collisions) to approach the $\sim \tfrac12 N$ barrier.
4. (iv) A minimal counterexample to any claimed linear lower bound would be a sequence $N_j\to\infty$ such that every $A\subseteq[1,N_j]$ with $|A|=\lfloor\sqrt{N_j}\rfloor$ satisfies $|(A+A)\cap[1,N_j]|=o(N_j)$; the small-$N$ data already contradict this behaviour at low scales, suggesting any counterexample would require subtle additive structure.

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.

Erdos Problem #819

FORMAL RESTATEMENT.

For each positive integer $N$, let \[ m := \lfloor N^{1/2}\rfloor. \] Define $f(N)$ to be the maximum of \[ |(A+A)\cap [1,N]| \] over all subsets $A\subseteq\{1,2,\dots,N\}$ with $|A|=m$, where $A+A:=\{a+b:\ a,b\in A\}$ and $[1,N]=\{1,2,\dots,N\}$. The problem asks to estimate $f(N)$.

QUICK LITERATURE/CONTEXT CHECK.

The statement records that Erdős and Freud proved \[ \left(\frac{3}{8}-o(1)\right)N \le f(N) \le \left(\frac{1}{2}+o(1)\right)N. \] I do not use any results not already stated in the problem text.

ATTACK PLAN.

Upper bounds: use counting of unordered pairs to control how many distinct sums can appear. Lower bounds: construct explicit $A$ producing many sums in $[1,N]$; as a baseline, compute small $N$ exactly to see what is achievable.

WORK.

Lemma 819.1 (unconditional counting upper bound). Let $m=\lfloor \sqrt N\rfloor$. For every $A\subseteq[1,N]$ with $|A|=m$, \[ |(A+A)\cap[1,N]| \le \binom{m+1}{2} = \frac{m(m+1)}{2} \le \frac{N}{2} + O(\sqrt N). \]

Proof. Every sum $s\in A+A$ can be represented as $s=a+b$ with $a,b\in A$. If we ignore order, each unordered pair $\{a,b\}$ with $a,b\in A$ produces at most one sum. There are exactly $\binom{m}{2}$ unordered pairs with $a\ne b$ and $m$ diagonal pairs $\{a,a\}$, so in total there are $\binom{m}{2}+m=\binom{m+1}{2}$ unordered pairs. Distinct sums are at most the number of unordered pairs, hence $|A+A|\le \binom{m+1}{2}$, and a fortiori $|(A+A)\cap[1,N]|\le \binom{m+1}{2}$. Since $m^2\le N < (m+1)^2$, we have $m^2\le N$ and $m\le \sqrt N$, giving $\binom{m+1}{2}\le \frac{1}{2}N + O(\sqrt N)$. $\square$

Lemma 819.2 (baseline lower bound). For $m=\lfloor\sqrt N\rfloor$, taking $A=\{1,2,\dots,m\}$ gives \[ |(A+A)\cap[1,N]| \ge 2m-1 = 2\lfloor\sqrt N\rfloor-1. \]

Proof. If $A=\{1,2,\dots,m\}$ then \[ A+A = \{2,3,\dots,2m\}. \] All these sums are $\le 2m\le 2\sqrt N\le N$ for $N\ge4$; in any case, $(A+A)\cap[1,N]$ contains $\{2,3,\dots,2m\}$. Thus $|(A+A)\cap[1,N]|\ge 2m-1$. $\square$

FAST REALITY CHECK (exact values for $N\le 30$). I exhaustively computed $f(N)$ for $1\le N\le 30$ by enumerating all subsets $A\subseteq[1,N]$ of size $m=\lfloor\sqrt N\rfloor$. The maximal values found were: \[ \begin{array}{c|c|c} N & m & f(N)\\\hline 1 & 1 & 0\\ 2\le N\le 3 & 1 & 1\\ 4\le N\le 8 & 2 & 3\\ 9\le N\le 15 & 3 & 6\\ 16\le N\le 24 & 4 & 10\\ 25\le N\le 30 & 5 & 15 \end{array} \] For example, at $N=16$ the set $A=\{1,2,4,8\}$ achieves $f(16)=10$.

VERIFICATION.

Lemma 819.1: the only step is the injection "distinct sums $\le$ unordered pairs"; this is valid because each unordered pair produces a single integer sum, though multiple pairs may collide. Lemma 819.2: sums of the initial segment form the full interval $[2,2m]$; checking the intersection with $[1,N]$ is immediate. The computed $f(N)$ values are finite enumerations and can be rechecked.

FINAL.

UNRESOLVED.

1. (i) Strongest proved partial results here: the unconditional upper bound $f(N)\le \binom{\lfloor\sqrt N\rfloor+1}{2} = \frac{1}{2}N+O(\sqrt N)$ (Lemma 819.1), matching the scale of the upper bound stated in the problem, and the explicit lower bound $f(N)\ge 2\lfloor\sqrt N\rfloor-1$ (Lemma 819.2). Exact values for $N\le 30$ were computed.
2. (ii) First gap: produce (or rigorously derive) a linear-in-$N$ lower bound $f(N)\ge cN$ with an explicit constant $c>0$ using only arguments developed here (i.e. without importing the stated Erdős--Freud result).
3. (iii) Top 3 next moves: $1$ attempt a probabilistic construction of a size-$\sqrt N$ set $A$ for which many $s\le N$ have at least one representation $s=a+b$; $2$ search computationally for maximizers for larger $N$ (e.g. $N\le 60$) to guess structure; $3$ prove structural lemmas relating large $|(A+A)\cap[1,N]|$ to quasi-Sidon behaviour (few collisions) to approach the $\sim \tfrac12 N$ barrier.
4. (iv) A minimal counterexample to any claimed linear lower bound would be a sequence $N_j\to\infty$ such that every $A\subseteq[1,N_j]$ with $|A|=\lfloor\sqrt{N_j}\rfloor$ satisfies $|(A+A)\cap[1,N_j]|=o(N_j)$; the small-$N$ data already contradict this behaviour at low scales, suggesting any counterexample would require subtle additive structure.