Erdős problem #819 — wave w016

Date: 2026-07-28 UTC

Claim labels

• [a] elementary-rigorous: proved here without an external theorem.
• [b] rigorous-modulo-named-theorem: the deduction is rigorous assuming the

explicitly named theorem.

• [c] plausible/structural-unverified: not claimed as a theorem.
• [d] computational-only/source-verified: an exact finite computation or a

direct observation from a fetched source. The finite mathematical claims are independently recomputed by runs/erdos819_wavew016_reverify.py.

0. Mandatory live-page check

[d: live-page observation] I fetched <https://www.erdosproblems.com/819> and its discussion thread through the Bright Data cloud browser on 2026-07-28. The live page rendered as OPEN.

The current problem statement, copied verbatim from the page's LaTeX view, is:

Let $f(N)$ be maximal such that there exists $A\subseteq \{1,\ldots,N\}$ with $\lvert A\rvert=\lfloor N^{1/2}\rfloor$ such that $\lvert (A+A)\cap [1,N]\rvert=f(N)$. Estimate $f(N)$.

The listed known result, also copied verbatim from the LaTeX view, is:

Erd\H{o}s and Freud \cite{ErFr91} proved\[\left(\frac{3}{8}-o(1)\right)N \leq f(N) \leq \left(\frac{1}{2}+o(1)\right)N,\]and note that it is closely connected to the size of the largest quasi-Sidon set (see [840]).

Opening the page's dynamic bibliography displayed:

• [Er91] P. Erdős, *Problems and results in combinatorial analysis and

combinatorial number theory, in Graph theory, combinatorics, and applications*, Vol. 1 (Kalamazoo, MI, 1988), 397–406 (1991), MR 1170793.

• [ErFr91] P. Erdős and R. Freud, On sums of a Sidon-sequence,

J. Number Theory 38 (1991), 196–205, MR 1111371.

[d: complete marker audit]

| live-page field | value | |---|---:| | status | OPEN | | comments | 2 | | claimed proofs | 0 | | interested in collaborating | None | | currently working on this problem | None | | formalised statement? | No |

The first comment, by leon2k2k2k at 15:40 on 15 May 2026, says:

We obtain $\liminf_{N\to\infty}f(N)/N\geq(16\sqrt2-17)/12\approx0.469$. This improves the Erdős–Freud 1991 lower bound of $3/8$ and closes most of the gap to the upper bound of $1/2$. Writeup at https://leon2k2k2k.github.io/erdos819.pdf.

The construction is a reflected two-copy of a maximum Sidon set with random shifts, taken along the subsequence $N=4q^2$: $A=B\cup C$ with $B=a+S$ and $C=N/2+\lfloor uN/2\rfloor-b-S$, where $S\subset[0,M]$ is an asymptotically maximum Sidon set of size $q$ and $a,b$ are uniform in a small interval. The overlap of the Sidon set and its reflected copy is controlled by Pikhurko's uniformity lemma (Lemma 10 of his 2006 paper), which is the core technical input. Random-shift optimization then gives a closed-form expected score $F(u)=1-2u^2-(1-2u)^3/12$, maximized at $u^*=3/2-\sqrt2$. An interpolation argument lifts from the subsequence $N=4q^2$ to all sufficiently large $N$. The construction and strategy are inspired by Pikhurko's Lemma 12. Found with the help of GPT-5.5 + Rethlas; verified by hand.

The second comment, by Nat Sothanaphan at 15:53 on 17 May 2026, says:

I ran standard check which found no issue.

The page explicitly labels user comments as unverified. There is no claimed proof of the whole problem and no current worker, so the mandatory stop condition did not apply.

1. Literature and source audit

Sources actually checked

1. [d] The publisher record for Erdős–Freud exists at

DOI 10.1016/0022-314X(91)90083-N90083-N). Its abstract defines, for a Sidon sequence in $[n]$, the maximum number of pair sums below $n$. The live problem page, rather than an inaccessible reconstruction of the full 1991 article, is the ground truth used here for the displayed $3/8$ and $1/2$ bounds.

1. [d] Oleg Pikhurko's primary paper

Dense Edge-Magic Graphs and Thin Additive Bases exists as arXiv:math/0309029 and as Discrete Mathematics 306 (2006), 2097–2107, DOI 10.1016/j.disc.2006.05.003. I downloaded and read the published PDF. Lemma 10 says that an asymptotically maximum Sidon set $S\subset[n]$ satisfies, for every interval $I$ and fixed residue class $\ell\bmod m$, \[ |S\cap I\cap(\ell+m\mathbb Z)| =\frac{|I|}{m\sqrt n}+o(\sqrt n). \] Lemma 12 really does use two randomly shifted reflected copies $B=s+S$ and $C=n-t-S$ and inclusion–exclusion to bound a sumset.

1. [d] The comment's redirect resolves to Yu Leon Liu's nine-page

manuscript Erdős #819: Reflected Sidon Lower Bound, dated 15 May 2026. The fetched file's SHA-256 is d320a2bd69aef766c3bd7726f19a142d3189ff17fb8691ccee45cadcd5f39a22. It contains the theorem stated in the comment and cites Pikhurko's Lemmas 10 and 12. I found no arXiv identifier or journal publication for this manuscript.

1. [d] A newer primary paper that cites Erdős–Freud,

Croot–Mao–Pohoata–Sheffer–Yip, A combinatorial large sieve for Sidon sets, distances, and norm forms, arXiv:2606.17487v2 (24 June 2026), discusses Erdős–Freud only as a source for equidistribution of dense Sidon sets. Its searchable full text contains neither 819, 3/8, nor quasi-Sidon; it does not settle this truncated sumset problem.

Independent audit of the May 2026 comment

[b: modulo Pikhurko Lemma 10, Bose–Chowla, the prime number theorem, and the classical Sidon upper bound] I found no defect in the manuscript's lower bound

This is not being promoted to live-page ground truth; it is a separate audit of an unrefereed comment.

Here is the dependency chain checked:

1. For every large integer $q$, thinning a Bose–Chowla set at the least prime

$p\ge q$ gives a $q$-element Sidon set $S\subset[0,M]$ with $M=(1+o(1))q^2$.

1. Pikhurko's Lemma 10 gives the interval-and-residue uniformity needed to

derive the triangular local densities for $\Sigma=S+S$ and $\Delta=S-S$.

1. For $N=4q^2$, the shifted reflected copies

\[ B=a+S,\qquad C=N/2+\lfloor uN/2\rfloor-b-S \] are disjoint $q$-sets in $[N]$ when the random shifts $a,b$ lie in a sufficiently small interval. Thus $A=B\cup C$ has exactly $\sqrt N$ elements.

1. Conditioning on one shift at a time justifies the two overlap products in

the inclusion–exclusion calculation. Integrating the three triangular profiles gives \[ \frac{2}{N}\,\mathbb E|(A+A)\cap[N]| \geq F(u)-O(\eta)-o(1),\qquad F(u)=1-2u^2-\frac{(1-2u)^3}{12}. \]

1. The exact calculation

\[ F'(u)=-4u+\frac{(1-2u)^2}{2} \] has its unique root in $(0,1/4)$ at $u_=3/2-\sqrt2$, and $F(u_)/2=c$. The standalone verifier recomputes this in exact arithmetic in $\mathbb Q(\sqrt2)$, including all five integral terms.

1. For arbitrary $N$, taking $q=\lfloor\sqrt N/2\rfloor$ gives

$4q^2=N-o(N)$ and requires adjoining at most one point, which cannot decrease the truncated sumset. This validates the interpolation step.

[c: search miss, not a nonexistence claim] Exact-statement, exact-title, DOI, citation, arXiv, and Sidon-bibliography searches found no other primary source that resolves #819 or improves the upper bound. The only post-page advance located is Liu's May 2026 personal manuscript. A missed paper remains possible.

2. Exact loss identity

Put

For a fixed $m$-set $A\subset[N]$, let

Define

Thus $O_N$ counts overflowing unordered pairs and $C_N$ counts the collision excess among nonoverflowing pairs.

Lemma [a] (loss identity).

Proof. The $T_m$ unordered pairs split by their sum. Every pair with sum above $N$ contributes one to $O_N$. For a represented sum $s\le N$, exactly one of its $r_A(s)$ pairs contributes one distinct element to the truncated sumset, while the remaining $r_A(s)-1$ contribute to $C_N$. Summing gives the identity. ∎

In particular, $f(N)\le T_m$. This identity also isolates the asymptotic problem exactly: a uniform improvement

would follow from, and at this scale is equivalent to, proving

for every $A\subset[N]$ of size $\lfloor\sqrt N\rfloor$.

3. Reduction of exact ceiling attainment to Golomb rulers

Let $G(m)$ be the least length $x_m-x_1$ of an increasing integer $m$-tuple

whose positive differences $x_j-x_i$ are all distinct. Such a tuple is a Golomb ruler. Over the integers, distinct positive differences are equivalent to distinct unordered pair sums, i.e. the Sidon property: a nontrivial equality of two pair sums rearranges to an equality of two positive differences, and the converse rearrangement works as well.

Proposition [a].

Proof.

If $f(N)=T_m$, then all $T_m$ unordered pairs from an extremizing $A$ have distinct sums and every such sum is at most $N$. In particular $2\max A\le N$, so $A\subset[1,\lfloor N/2\rfloor]$, and $A$ is a Sidon set. Translate it so that its minimum is $1$. This preserves all differences and gives a ruler of length at most $\lfloor N/2\rfloor-1$. Hence $G(m)\le\lfloor N/2\rfloor-1$, equivalently $N\ge2(G(m)+1)$.

Conversely, translate an optimal ruler to $1=x_1<\cdots<x_m=G(m)+1$. Its unordered pair sums are distinct and are all at most $2(G(m)+1)\le N$. It is therefore an admissible $A$ attaining all $T_m$ sums. ∎

This is a complete reduction only for attaining the absolute pair-count ceiling. It does not by itself give a positive-proportion asymptotic loss.

4. From-scratch exact computation

Golomb ruler certificate

[d] The verifier fixes the first mark at $1$ (translation loses nothing) and recursively enumerates every increasing completion. When a new mark $x$ is inserted, it rejects the branch exactly if one of the new differences $x-a$ repeats a used difference. It finds a witness at length $G(m)$ and exhausts the full search tree at length $G(m)-1$.

| $m$ | exact $G(m)$ | ruler in $[1,G(m)+1]$ | nodes proving no ruler one unit shorter | nodes finding displayed-length ruler | |---:|---:|---|---:|---:| | 1 | 0 | $(1)$ | 0 | 1 | | 2 | 1 | $(1,2)$ | 1 | 2 | | 3 | 3 | $(1,2,4)$ | 2 | 3 | | 4 | 6 | $(1,2,5,7)$ | 8 | 5 | | 5 | 11 | $(1,2,5,10,12)$ | 66 | 11 | | 6 | 17 | $(1,2,5,11,13,18)$ | 459 | 39 | | 7 | 25 | $(1,2,5,11,19,24,26)$ | 4,254 | 203 | | 8 | 34 | $(1,2,5,10,16,23,33,35)$ | 36,348 | 1,041 |

The search does not import a ruler table or use an optimizer.

Exact values through 80

Theorem [a+d]. The exact values of the live-page function for $1\le N\le80$ are:

| $N$ | $f(N)$ | |---:|---:| | $1$ | $0$ | | $2\ldots3$ | $1$ | | $4\ldots8$ | $3$ | | $9\ldots15$ | $6$ | | $16\ldots24$ | $10$ | | $25\ldots35$ | $15$ | | $36\ldots48$ | $21$ | | $49\ldots51$ | $27$ | | $52\ldots63$ | $28$ | | $64\ldots69$ | $35$ | | $70\ldots80$ | $36$ |

Proof. For each $N$, the proposition and the exhaustively certified $G(m)$ decide whether the ceiling $T_m$ is possible. When it is possible, the displayed ruler supplies a witness. When it is not possible, integrality gives $f(N)\le T_m-1$. The following three witnesses attain that smaller bound in all non-ceiling cases:

• $N=1$: $A=\{1\}$ has its sole pair sum $2>N$, so its score is $0$.
• $49\le N\le51$:

\[ A=\{1,2,4,9,18,22,24\}. \] All 28 unordered pairs have sum at most 48; the only collision is \[ 2+24=4+22=26. \] Thus the score is $27$.

• $64\le N\le69$:

\[ A=\{1,3,10,13,26,27,31,32\}. \] All 36 unordered pairs have sum at most 64; the only collision is \[ 26+32=27+31=58. \] Thus the score is $35$.

The same witness remains valid as $N$ increases inside its fixed-$m$ interval. This proves every row. ∎

5. Verification and reproducibility

The standalone verifier is runs/erdos819_wavew016_reverify.py. It uses only the Python standard library. It independently:

1. exhausts the Golomb-ruler searches through eight marks;
2. checks the sharp ceiling criterion directly for every $N\le80$;
3. recomputes every truncated sumset and both loss terms for every witness;
4. checks the compressed exact table against the 80 recomputed values; and
5. verifies the May 2026 constant and stationary point exactly in

$\mathbb Q(\sqrt2)$.

Reproduction command:

python3 runs/erdos819_wavew016_reverify.py

The run completed in 1.43 seconds on this VM and ended with:

2026 comment algebra: u*=3/2-sqrt(2), c=(16sqrt(2)-17)/12=0.468951416497460 [exactly checked]

ALL CHECKS PASSED

6. What remains and the precise wall

[a] The exact loss identity shows what a nontrivial upper bound must do: prove a positive-proportion lower bound on $O_N(A)+C_N(A)$ uniformly over all square-root-size sets. Merely proving that a perfect ruler cannot fit gives only a loss of one, not $\Omega(N)$.

[c] The available dense-Sidon uniformity theorem does not supply this missing stability statement. Pikhurko's Lemma 10 controls sets with essentially no repeated differences in one interval. A near-extremizer for #819 may instead balance overflowing pairs against collisions across multiple reflected blocks, as Liu's construction explicitly does. The missing lemma is therefore a truncated near-Sidon stability theorem forcing

for some fixed $\delta>0$, or else a classification showing why no such $\delta$ can hold. No checked source provides it.

[d: computation boundary] Extending the exact table past $80$ also stops being a tiny ruler calculation. Already $N=81$ has $\binom{81}{9}=260{,}887{,}834{,}350$ candidate sets if attacked directly. At a realistic optimized rate of 1–5 million fully scored candidates per second, an unpruned scan would cost about 14.5–72.5 core-hours, before producing a checkable upper-bound certificate. I did not run that computation on this VM.

PARTIAL: Proved the exact ceiling–Golomb-ruler equivalence and, with a dependency-free exhaustive certificate plus explicit one-collision constructions, determined f(N) exactly for every N<=80; independently audited the unrefereed 2026 lower bound 0.4689514164... modulo its named Sidon theorems, while the asymptotic upper-bound stability lemma remains open.