Erdős problem 864 — wave 6p

Access date: 2026-08-12 (UTC); original live-page audit 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 gate was refreshed on 2026-08-12 before the finite extension below; the page was still OPEN, with 0 proof claims and no current worker or collaborator.

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.

1. The primary, open-access paper

Erdős, Some of my Forgotten Problems in Number Theory (1992), DOI 10.46298/hrj.1992.125, 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.

1. [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.

1. [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.

1. 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 the updated computation, \(m=18\) and \(\binom{18}{2}=153\). If \(q\leq6\), then \(D\leq30\), so (2) forces \(L\geq123\). If \(q=7\) and there is a midpoint, then \(D=36\) and \(L\geq117\). Therefore:

Any valid 18-set of diameter at most 115 has either \(q\geq8\), or \(q=7\) without a midpoint. In particular, at least 14 of its 18 elements lie in the reflected core \(R\). [A]

There are exactly five cases:

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\leq115\), the largest possible lower mark is 57, and that coordinate is included.

A valid reflected core of size \(r\) has exactly \(\lfloor r^2/4\rfloor\) distinct positive differences (its only duplicated pairs are reflection partners), 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;

1. 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 115 has relative coordinate in \([-(115-T),115]\). A tuple is retained exactly when its total diameter is at most 115. 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 updated certification search took 52.09 seconds. [D]

Exhaustion result

The default run produced:

No case produced an 18-set of diameter at most 115. [D]

As an independent sanity check, a separately written implementation using direct pair-sum arrays and the reverse enumeration order returned the same lower-half counts:

k=9: 51140 leaves
k=8: 1697946 leaves
k=7: 3367288 leaves

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 earlier target-17 exhaustive run gave no valid 17-set of diameter at most

1. 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]

The 2026-08-12 extension uses the normalized 18-point witness

After translating by one, this is a subset of \(\{1,\ldots,117\}\), and its only repeated sum is

Thus \(F(117)\ge18\). The exhaustive result gives no valid 18-set of diameter at most 115, so \(F(N)\le17\) for \(N\le116\). The 17-point witness above gives the matching lower bound for every \(N\ge107\). Hence

The final equality again uses \(F(N+1)\le F(N)+1\). [D]

5. Target 19: the next exact boundary

The same reflection reduction can be pushed one target farther. For a normalized 19-point set there are 171 positive-difference occurrences. Under diameter 133, the difference count leaves exactly six possible exact reflected-core sizes:

A 13-point core would already force diameter at least \(171-(7-1)^2=135\), and a smaller core is no better. Thus the case split is complete. [A]

Two independently organized exhaustive implementations exclude all six cases through diameter 133. The direct reflected-orbit search and the independent Golomb-lower-half audit agree on every valid-core count:

core 19:          0
core 18:      1,297
core 17:     22,271
core 16:  1,920,748
core 15:  1,565,022
core 14: 22,183,488

No core extends to a valid 19-point set. The core-14 run separately records each of the 85 centers from 49 through 133, and a coverage checker verifies that every center occurs exactly once. [D]

The normalized witness

has only the repeated sum

Translating by one gives a valid 19-set in \(\{1,\ldots,135\}\). Together with the 18-point witness above and the nonexistence computation, this proves

For the last equality, \(F(134)=18\) and \(F(N+1)\leq F(N)+1\) give the upper bound, while the displayed witness gives the lower bound. [D]

The frozen verification bundle contains both implementations, complete outputs, exact-center coverage and count comparisons, the target-18 regression, sanitizer/debug controls, and a SHA-256 manifest: verification/864/exact-through-135. An early scratch enumerator omitted one inclusive endpoint for even cores at odd centers; that result was retracted before publication. The corrected source reran every affected branch, and the independent implementation—which never used the faulty expression—agrees on all six counts. [D]

6. Target 20: exact values through 153

The same reflected-core method closes the next boundary. A 10-mark Golomb ruler

gives the reflected 20-point set

Its only repeated sum is 152, with exactly the ten reflection representations. A definition-level checker recounts all 210 unordered diagonal-inclusive pairs rather than trusting the construction. Translating by one supplies a valid 20-set in \(\{1,\ldots,153\}\). [A,D]

For the upper bound, translate a hypothetical 20-set of diameter at most 151 to have minimum zero. Here \(\binom{20}{2}=190\). Substituting the two formulas for \(D\) above into (2) leaves exactly these seven reflected-core cases:

The next case has a 13-point core, \(D=36\), and diameter at least 154, so the list is exhaustive. Two independently organized C++ searches then exclude every retained case. Their exact valid-core totals agree:

core 20:           0
core 19:         489
core 18:     240,837
core 17:     758,979
core 16:  27,176,695
core 15:  11,169,166
core 14: 109,972,454

The direct search covers 239 individually recorded center slices for core sizes 16, 15, and 14, plus complete whole-range runs for core sizes 17 through 20. Its coverage audit rejects a missing or duplicate legal center. The independent Golomb-lower-half program reconstructs the seven cases in a different order, obtains the same core totals, and terminates with no valid 20-set of diameter at most 151. [D]

This proves

Indeed, the previous section supplies \(F(135)=19\), heredity gives the lower bound through 152, and the exhaustion gives the matching upper bound. Finally \(F(153)\leq F(152)+1=20\), while the displayed construction gives equality. [D]

The frozen bundle contains both search sources, complete direct logs, the independent transcript, exact count and center-coverage comparisons, positive and sanitizer controls, the refreshed live gate, and a SHA-256 manifest: verification/864/exact-through-153. An invalid scratch shortcut briefly skipped low core centers by applying a bound on the total diameter; it was retracted before any claim. Every omitted center was rerun, the canonical logs contain the complete ranges, and the independent audit agrees. The earlier inclusive-endpoint correction is also present in both frozen implementations. [D]

The OEIS entry A389182 still ended at \(N=100\) when refreshed on 2026-08-12. Together, the computations above extend it by fifty-three exact terms:

7. 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 (8) 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 (9). 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\), \(F(107)=\cdots=F(116)=17\), \(F(117)=\cdots=F(134)=18\), \(F(135)=\cdots=F(152)=19\), and \(F(153)=20\); the asymptotic \(2/\sqrt3\) upper bound remains open.