Erdős problem 864 — wave 6p

Access date: 2026-07-27 (UTC).

Claim labels used below:

• [A] elementary-rigorous;
• [B] rigorous modulo the explicitly named theorem/source;
• [C] plausible or structural but unverified;
• [D] computational-only (the exhaustive algorithm and its completeness reduction are supplied).

0. Mandatory live-page audit

I fetched both the rendered problem page and its discussion thread through the

Bright Data browser path:

• <https://www.erdosproblems.com/864>
• <https://www.erdosproblems.com/forum/discuss/864> (redirected to

/forum/thread/864)

The live page says OPEN, 0 claimed proofs, and **Currently working on

this problem: None**. “Interested in collaborating” is also None. Thus the

mandatory stop condition did not fire.

Verbatim live statement

> Let \(A \subseteq \{1,\ldots,N\}\) be a set such that there exists at most

> one \(n\) with more than one solution to \(n=a+b\) (with \(a\leq b\in A\)).

> Estimate the maximal possible size of \(|A|\) - in particular, is it true

> that

> \[ > |A|\leq (1+o(1))\frac{2}{\sqrt 3}N^{1/2}? > \]

Everything else listed on the live page/thread

• [B] The page attributes to Erdős and Freud the lower bound

\[ |A|\geq (1+o(1))\frac{2}{\sqrt3}N^{1/2}. \]

Its construction takes a genuine Sidon set

\(B\subset[1,N/3]\), of size \(\sim N^{1/2}/\sqrt3\), and unions it

with \(\{N-b:b\in B\}\).

• [B] For the analogous difference question \(n=a-b\), the page says

Erdős and Freud prove the maximum is \(\sim N^{1/2}\).

• The page calls #864 a weaker form of open problem #840 and links OEIS

A389182.

• Comment by TerenceTao, 2025-10-23: the extremizers through \(N=69\)

and structural observations are in

GitHub issue 143.

• Comment by DesmondWeisenberg, 2025-08-11: [B] if \(\sigma\) is the

exceptional sum, the parts of \(A\) on the two sides of \(\sigma/2\) are

individually Sidon. If \(h(M)\) is the largest Sidon subset of an interval

of length \(M\), this gives

\[ F(N)\leq \max_{0\leq k\leq N}(h(k)+h(N-k)) \leq(\sqrt2+o(1))N^{1/2}, \]

using the classical \(h(M)=(1+o(1))\sqrt M\).

• The discussion has exactly those two comments. It has no claimed proof and

no worker marker.

The GitHub computation is no longer the end of the external finite data:

OEIS A389182 was extended by Alper Ferudun on 2026-07-12 and currently gives

exact terms through \(N=100\). In particular, the first unlisted value was

\(F(101)\), not \(F(70)\).

1. Literature audit

I searched exact phrases for the one-exception condition, the title/DOI

citation graph of Erdős–Freud, and later Sidon/quasi-Sidon literature.

1. [Erdős and Freud, On sums of a Sidon-sequence, JNT 38

(1991), 196–205](https://doi.org/10.1016/0022-314X(91)90083-N) exists with

exactly that bibliographic record. The publisher abstract concerns sums of

a Sidon sequence. The publisher did not expose the full article text in

this run.

2. The primary, open-access paper

[Erdős, Some of my Forgotten Problems in Number Theory (1992),

DOI 10.46298/hrj.1992.125](https://hrj.episciences.org/125/pdf), pp. 39–40,

explicitly states the one-exception sum problem, says the

\(2/\sqrt3\) lower constant is possible, and contrasts it with the

difference version. This directly verifies the historical attribution.

3. [O’Bryant’s annotated Sidon bibliography

(2004)](https://www.combinatorics.org/ojs/index.php/eljc/article/download/DS11/pdf/)

describes the Erdős–Freud paper’s dense-Sidon and quasi-Sidon results, but

I found no entry resolving the one-exception question.

4. [Pikhurko, Dense edge-magic graphs and thin additive bases

(2006)](https://pikhurko.github.io/E/Pikhurko06dm.pdf) improves the much

broader quasi-Sidon upper bound (problem #840) to constant \(1.863\ldots\).

It does not give a bound competitive with the \(\sqrt2\) comment for the

much stronger one-exception hypothesis.

5. OpenAlex lists 19 works citing the 1991 DOI, through 2023. Searching those

titles/available abstracts and exact phrases such as “one repeated sum,”

“one exception,” and “at most one repeated” found no later paper asserting

a solution of #864. This is a search miss, not a proof that no such paper

exists.

Thus the best asymptotic upper bound I could verify specifically for the live

one-exception statement is the \((\sqrt2+o(1))\sqrt N\) argument in the live

comment. I found no primary source claiming the conjectured constant.

2. New structural reduction

Let \(F(N)\) denote the maximum in the problem. Translation preserves all

sum-equality relations. Hence a valid \(m\)-set in \([N]\) can be normalized

to minimum \(0\) and diameter at most \(N-1\). The condition is also

hereditary under taking subsets. [A]

Difference–reflection lemma

Let \(\sigma\) be the unique exceptional sum. Suppose the same positive

difference has two distinct representations

Then

These are two distinct pair representations of a common sum, so that sum must

be \(\sigma\). Consequently

Thus every positive difference has multiplicity at most two, and a

double representation consists exactly of a pair and its reflection in

\(\sigma/2\). [A]

Put

Reflection \(x\mapsto\sigma-x\) partitions \(R\) into \(p\) two-element

orbits and possibly the fixed midpoint \(\sigma/2\). Among the

\(\binom{|R|}{2}\) unordered distinct pairs in \(R\), exactly the \(p\)

complementary pairs are fixed. All other pairs occur in two-element

reflection orbits, and each such orbit is one duplicated positive-difference

value. Therefore

is exactly the number of duplicated positive-difference values. Hence, if

\(m=|A|\) and \(L=\max A-\min A\),

This is not merely an inequality about counts: the preceding argument also

characterizes every permitted duplicate. [A]

Let \(q\) be the number of unordered representations of \(\sigma\), with a

double \(a+a\) allowed.

• Without a midpoint, \(|R|=2q,\ p=q\), so \(D=q(q-1)\).
• With a midpoint, \(|R|=2q-1,\ p=q-1\), so \(D=(q-1)^2\).

For \(m=17\), \(\binom{17}{2}=136\). If \(q\leq6\), then \(D\leq30\), and

(2) forces \(L\geq106\). Therefore:

> Any valid 17-set of diameter at most 105 has \(q\geq7\), so at least 13 of

> its 17 elements lie in the reflected core \(R\). [A]

There are exactly five cases:

| \(q\) | midpoint? | \(|R|\) | unpaired outliers |

|---:|:---:|---:|---:|

| 9 | yes | 17 | 0 |

| 8 | no | 16 | 1 |

| 8 | yes | 15 | 2 |

| 7 | no | 14 | 3 |

| 7 | yes | 13 | 4 |

No other case can occur: representations of one sum are disjoint pairs, apart

from the possible midpoint.

3. Exhaustive computation

Why the enumeration is complete

Normalize a reflected core \(R\) so that \(\min R=0\), \(\max R=T\); then its

reflection sum is \(T\). Write its lower half as

If \(|R|=2k\), then

If \(|R|=2k+1\), then \(T\) is even and

The set \(B\) is an ordinary Sidon set: a repeated sum inside \(B+B\) would

be below \(T\), while \(T\) is already the exceptional sum of \(R\).

Equivalently, all positive differences of \(B\) are distinct. [A]

The checker therefore generates every possible \(B\) by distinct-difference

backtracking. The inclusive endpoint is important: for \(T\leq105\), the

largest possible lower mark is 52, and that coordinate is included.

A centrally symmetric \(r\)-set has \(\lfloor r^2/4\rfloor\) distinct

positive differences (reflection orbits of its unordered pairs), so

This supplies finite starting bounds for every core size. [A]

For each generated \(B\) and every admissible \(T\), the checker:

1. constructs \(R\);

2. counts every unordered pair sum and retains it only if \(T\) is the sole

repeated sum;

3. adds the required 0–4 exact-core outliers in increasing coordinate order.

With the core at \([0,T]\), every possible outlier from a total configuration

of diameter at most 105 has relative coordinate in

\([-(105-T),105]\). A tuple is retained exactly when its total diameter is at

most 105. Because \(R\) is the exact reflected core, an outlier and its

reflection cannot both be selected.

When adding a new point \(z\), its new sums \(z+x\) are mutually distinct.

Therefore it is enough to bit-test them against all old represented sums.

Once a second repeated sum occurs, later additions cannot repair it, so this

incremental rejection is monotone and exhaustive. [A]

Reproducible code

The standalone checker is

erdos864_wave6p_reverify.py. It contains:

• a direct Python pair-sum checker for the witnesses;
• the readable pure-Python exhaustive implementation (--python-full);
• the same full search in embedded C++17, compiled in a temporary directory

for the default fast run. It uses no SAT/MIP solver and no downloaded data.

Run:

python runs/erdos864_wave6p_reverify.py

Environment used:

Python 3.12.3
g++ 13.3.0
x86_64

The corrected certification run took 16.58 seconds. [D]

Exhaustion result

The default run produced:

| core \(|R|\) | outliers | Sidon lower halves | core candidates \((B,T)\) | valid cores | extension nodes | FNV-64 digest |

|---:|---:|---:|---:|---:|---:|:---|

| 17 | 0 | 392,150 | 885,866 | 0 | 0 | 14650fb0739d0383 |

| 16 | 1 | 392,150 | 2,163,886 | 2,028 | 2,028 | ff130165e24a8f87 |

| 15 | 2 | 1,376,518 | 5,509,996 | 16,392 | 16,408 | 7913f4993e7ca9a3 |

| 14 | 3 | 1,376,518 | 12,396,578 | 656,453 | 706,995 | 955a0f4080d93547 |

| 13 | 4 | 820,998 | 4,991,020 | 327,016 | 654,560 | 1b89857026b80612 |

No case produced a 17-set of diameter at most 105. [D]

As an independent sanity check, a separate pure-Python DFS that only

recomputed the Sidon lower halves returned:

k=8: 392150 leaves, 2316355 nodes
k=7: 1376518 leaves, 2266368 nodes
k=6: 820998 leaves, 1001335 nodes

These leaf counts agree exactly with the compiled full search. [D]

4. Exact new values

The normalized 16-point witness is

Its only repeated sum is \(85\), with eight representations. Translating by

one gives the set in \(\{1,\ldots,86\}\)

whose exceptional sum is

All other unordered pair sums are distinct. [A], directly checkable by

the supplied pair counter.

The exhaustive result gives no valid 17-set of diameter at most 105. Thus

\(F(106)\leq16\), while \(A_{16}\) gives \(F(N)\geq16\) for every

\(N\geq86\). Hence

[D]

The normalized 17-point witness is

After translating by one,

Its only repeated sum is

Thus \(F(107)\geq17\). Also \(F(N+1)\leq F(N)+1\): remove \(N+1\) if it is

selected. Combining this with (3) gives

[D]

This extends the currently posted OEIS table by seven exact terms:

| \(N\) | 101 | 102 | 103 | 104 | 105 | 106 | 107 |

|---:|---:|---:|---:|---:|---:|---:|---:|

| \(F(N)\) | 16 | 16 | 16 | 16 | 16 | 16 | 17 |

5. What remains asymptotically

The finite result does not settle the live asymptotic question.

The difference–reflection lemma identifies the obstruction precisely: many

duplicate differences may be supported by a large reflected core. In the

fully symmetric even case,

validity is equivalent to \(B\) being Sidon and

Equivalently, \(S\notin B+B+D^+(B)\). [A]

The safe Erdős–Freud construction takes \(S>3\max B\), making (5)

automatic. A sharp asymptotic proof even in this symmetric subclass would

follow from the missing uniform statement

No theorem found in the literature search supplies (6). The general problem

also needs control of elements outside the reflected core. This is the exact

structural wall; elementary difference counting alone allows too many

reflection-supported duplicates and does not reach \(2/\sqrt3\).

PARTIAL: Exact exhaustive computation extends A389182 with \(F(101)=\cdots=F(106)=16\) and \(F(107)=17\); the asymptotic \(2/\sqrt3\) upper bound remains open.