Erdős problem #14 — wave 5e report
Accessed and computed on 2026-07-26 (UTC).
Claim labels used below:
- [a] elementary-rigorous — a complete paper proof is given here.
- [b] rigorous modulo named theorem/source — the assertion is exactly what the linked source states, or uses a named result.
- [c] plausible/structural-unverified — useful interpretation or a literature-search miss, not a theorem.
- [d] computational-only — established by the disclosed finite exhaustive computation, not promoted to an asymptotic theorem.
0. Mandatory live-page check
[b, source] I fetched the live page through the Bright Data browser path, not direct curl: erdosproblems.com/14, its LaTeX view, and its discussion thread. The page was last edited 14 September 2025 and displayed:
- status: OPEN;
- claimed proofs: 0;
- currently working: None;
- interested in collaborating: None;
- one comment, which is bibliographic and does not claim a proof.
Thus none of the mandatory stop conditions applies.
Verbatim live statement
[b, source; verbatim]
> Let \(A\subseteq \mathbb{N}\). Let \(B\subseteq \mathbb{N}\) be the set of integers which are representable in exactly one way as the sum of two elements from \(A\).
>
> Is it true that for all \(\epsilon>0\) and large \(N\)
> \[ > \lvert \{1,\ldots,N\}\backslash B\rvert \gg_\epsilon N^{1/2-\epsilon}? > \]
> Is it possible that
> \[ > \lvert \{1,\ldots,N\}\backslash B\rvert =o(N^{1/2})? > \]
Background listed on the live page
[b, source] The page says that the problem was apparently first considered by Erdős and Nathanson, and that Erdős later attributed it to Erdős, Sárközy, and Szemerédi without a reference. It records:
1. a construction with
\[ |\{1,\ldots,N\}\setminus B|\ll_\epsilon N^{1/2+\epsilon} \]
for every \(\epsilon>0\) and all large \(N\);
2. for that discussion, infinitely many \(N\) with a lower bound
\[ |\{1,\ldots,N\}\setminus B|\gg_\epsilon N^{1/3-\epsilon}; \]
3. a finite construction of Erdős and Freud with fewer than
\(2^{3/2}N^{1/2}\) exceptions, with \(2^{3/2}\) suggested as perhaps
essentially optimal.
[b, source] The one comment identifies the Hungarian source of the finite passage as P. Erdős and R. Freud, A Sidon-problémakör, Matematikai Lapok 1991/2, 1–44. It points to printed page 34, PDF page 90, and supplies an English translation. The page states that it has already been updated in response to this comment.
Convention
[a] “One way” must mean an unordered representation, allowing equal summands:
\[ r_A(n):=\#\{(a,b):a,b\in A,\ a\le b,\ a+b=n\}. \]Ordered counting would make every representation by two distinct elements occur twice and would make the live problem qualitatively different. The page's finite analogue uses \(A\subseteq\{1,\ldots,N\}\), so this report follows the positive-integer convention; \(0\notin A\).
1. Primary-source and current-literature check
Sources verified
[b, source] Erdős's 1992 primary paper exists as:
- P. Erdős, Some of my forgotten problems in number theory, Hardy–Ramanujan Journal 15 (1992), 34–50, DOI 10.46298/hrj.1992.125, with the journal PDF.
On printed pages 43–44 it defines \(f(n)\) as the number of representations \(n=a_i+a_j\), and \(B(x)\) as the number of \(n [b, source] I downloaded and inspected the 222-page primary scan of the 1991 Matematikai Lapok volume: Section 4.3.5, printed page 34/PDF page 90, asks for the maximum number of integers up to \(n\) uniquely representable as a sum of two sequence terms. It states that an easy construction has on the order of at most \(2^{3/2}\sqrt n\) exceptions, suggests this may be nearly optimal, and says almost nothing was then known toward a matching lower bound. [b, source] The bibliography item attached by the website, really exists. Its abstract concerns how many sums of a finite Sidon sequence lie below a cutoff. The explicit finite-exception wording checked above is in the Hungarian survey passage identified by the page commenter. [b, source] The other two bibliography records displayed by the live page also exist: I did not obtain full primary scans of these two 1997 papers, so I do not attribute any finer claim to them. [c] Targeted web and citation searches on 2026-07-26 did not locate a later primary paper resolving either exact question. Searches included combinations of the exact 1992 wording, “representable in exactly one way,” “exceptions,” “\(B(x)\),” Erdős/Nathanson/Ruzsa/Freud, and forward-citation queries for the 1992 DOI and the 1991 JNT DOI. This is a documented miss, not a proof that the literature is complete. [c] Papers on unique representation bases for the integers concern subsets of \(\mathbb Z\) whose every integer has one representation and primarily ask how dense the representing set can be. For example, the 2026 paper Solutions to some problems on unique representation bases is about that different problem and does not supply an exception bound for initial intervals in \(\mathbb N\). [b, source] The page labels OEIS A143824 only as “possible.” Inspection shows that A143824 is the maximum size of a Sidon subset of \(\{1,\ldots,n\}\), not the finite exception sequence computed below. Define [a] Elements at least \(N\) cannot occur in a positive-summand representation of an integer at most \(N\), so this is exactly the finite minimization induced by the live problem. [a] \(E(N+1)\ge E(N)\). Proof. Take any \(A\subseteq\{1,\ldots,N\}\). Replacing it by \(A\cap\{1,\ldots,N-1\}\) does not change \(r_A(n)\) for any \(n\le N\). The first \(N\) entries therefore contain at least \(E(N)\) exceptions. Taking the minimum for \(N+1\) proves the claim. \(\square\) [d] The exhaustive result is Equivalently, In the table, the displayed \(A\) is a witness at the right endpoint \(H\). For an earlier \(N\) in the same row, use \(A\cap[1,N-1]\). \(X_H\) is the exception set at the right endpoint. [a for each finite witness; arithmetic independently checked by the script] | \(N\)-range | \(E(N)\) | witness \(A\) at \(H\) | \(X_H=\{n\le H:r_A(n)\ne1\}\) | |---:|---:|---|---| | 1–7 | 1 | \(\{1,2,4,6\}\) | \(\{1\}\) | | 8–17 | 2 | \(\{1,2,4,6,7,14,16\}\) | \(\{1,8\}\) | | 18–27 | 3 | \(\{1,3,4,8,9,11,20,24,25\}\) | \(\{1,3,12\}\) | | 28 | 4 | \(\{1,3,4,8,9,11,20,24,25\}\) | \(\{1,3,12,28\}\) | | 29–35 | 5 | \(\{1,3,4,8,12,13,15,28,32,33\}\) | \(\{1,3,10,16,22\}\) | | 36–42 | 6 | \(\{1,3,6,7,14,15,18,20,36,40\}\) | \(\{1,3,5,11,21,31\}\) | | 43–50 | 7 | \(\{1,3,6,7,14,15,18,20,36,38,45,46\}\) | \(\{1,3,5,11,21,31,39\}\) | | 51–53 | 8 | \(\{1,3,6,7,14,15,18,20,36,40,42,51,52\}\) | \(\{1,3,5,11,21,31,43,44\}\) | | 54–59 | 9 | \(\{1,2,4,9,13,19,23,28,30,31,44,51\}\) | \(\{1,7,9,12,16,19,32,46,53\}\) | | 60–69 | 10 | \(\{1,2,4,9,13,19,23,28,30,31,44,51,64,68\}\) | \(\{1,7,9,12,16,19,32,46,53,60\}\) | | 70–73 | 11 | \(\{1,2,4,9,13,19,23,28,30,31,44,51,64,67\}\) | \(\{1,7,9,12,16,19,32,46,53,60,68\}\) | | 74–78 | 12 | \(\{1,2,4,9,13,19,23,28,30,31,44,51,64,67,77\}\) | \(\{1,7,9,12,16,19,32,46,53,60,68,74\}\) | | 79 | 13 | \(\{1,2,4,9,13,19,23,28,30,31,44,51,64,67,77\}\) | \(\{1,7,9,12,16,19,32,46,53,60,68,74,79\}\) | | 80 | 13 | \(\{1,3,4,9,13,20,27,31,36,37,39,52,68,79\}\) | \(\{1,3,9,11,15,19,20,25,27,40,56,60,72\}\) | Write \(x_k=1_{k\in A}\). At search depth \(k\), membership of \(1,\ldots,k\) has been decided. [a] At that moment \(r_A(k+1)\) is final. Indeed, both positive summands of \(k+1\) are at most \(k\). No later decision can change whether \(k+1\) is exceptional. [a] Every set \(A\subseteq[1,N-1]\) is one root-to-leaf binary path. The accumulated number of finalized exceptions never decreases. Therefore a branch already having at least the best known total can be pruned without discarding a better set. At a leaf, all of \(1,\ldots,N\) have been finalized. This proves the completeness of the enumeration independently of any solver. The core code is: [a] It suffices to run the lower-bound search at the first \(N\) of each plateau. The monotonicity lemma propagates that lower bound to the rest of the plateau, while the displayed witnesses supply the upper bounds. The complete dependency-free checker, including all witnesses, is Run: The full run on CPython 3.12.3, x86-64, produced: [d] The measured node count and elapsed time are reproducibility data, not an asymptotic complexity claim. The script independently checks every witness in two ways: 1. direct nested loops over unordered pairs \(a\le b\); 2. an ordered convolution count \(c(n)\), converted via \[
r_A(n)=\frac{c(n)+1_{\{n\ {\rm even},\,n/2\in A\}}}{2}.
\] The verifier's SHA-256 is [a] Under the literal uniform reading of the notation \(\gg_\epsilon\), in which the constant and the large-\(N\) threshold do not depend on \(A\), the first live question is equivalent to One direction follows by minimizing over finite prefixes. In the other direction, every infinite \(A\) has at least \(E(N)\) exceptions at \(N\). [c] If the intended threshold or constant may depend on the fixed set \(A\), changing finite minimizers prevent this simple equivalence. The live notation has only the subscript \(\epsilon\), but the quantifier convention is not further spelled out on the page. [a] Let \(g(N)=o(\sqrt N)\). There is a single \(A\subseteq\mathbb N\) with \(U_A(N)\le g(N)\) for every \(N\) if and only if, for every \(M\), there is a finite membership string on \([1,M]\) satisfying Proof. Necessity is truncation. For sufficiency, put all such finite membership strings in the binary prefix tree. The tree is finitely branching and has arbitrarily large depth. It is prefix closed because deleting decisions above \(M\) cannot affect sums at most \(M\). König's infinity lemma gives an infinite path, which is the required \(A\). \(\square\) [a] Consequently, merely showing \(E(N)=o(\sqrt N)\), where a different optimizer may be used at each isolated \(N\), would not by itself answer the second question. What is needed is a nested family controlling every earlier cutoff simultaneously. Let \(X=\{n\le N:r_A(n)\ne1\}\), \(E=|X|\), and \(m=|A\cap[1,N-1]|\). [a] The elementary pair count only gives because each of the \(N-E\) unique sums needs a distinct unordered pair. This forces \(m\gtrsim\sqrt{2N}\) when \(E=o(N)\), but supplies no lower bound on \(E\). [a] The obstruction is concentration. We have where terms with \(r_A(n)=0\) contribute zero. The exceptional fibers have no multiplicity cap; a small set \(X\) can absorb many pairs and all of the additive energy \(\sum_n\binom{r_A(n)}2\). Classical Sidon bounds use \(r_A(n)\le1\) for every \(n\), so they do not transfer merely from knowing that most fibers equal one. Put \(F(z)=\sum_{a\in A}z^a\). Then [c, exact missing lemma] A route to the first question would require a quantitative rigidity theorem for \(0\)-\(1\) power series: the first \(N\) coefficients of \((F(z)^2+F(z^2))/2\) cannot equal \(1\) outside fewer than \(N^{1/2-o(1)}\) positions, uniformly over \(F\). Existing Sidon/difference arguments do not prove this because they do not control the unbounded coefficients at the exceptional positions. This coefficient-rigidity statement, or an inverse theorem implying it, is the exact missing ingredient isolated by the computation. [d] At \(N=80\), \(E(80)=13\approx1.453\sqrt{80}\). This is far below the page's general finite construction constant \(2^{3/2}\approx2.828\), but one small value carries no asymptotic implication. The exhaustive node count grows quickly (28,061,147 nodes just for the \(N=79\) lower bound), so this search is suited to small-case certification rather than testing an \(N^{1/2-o(1)}\) asymptotic. [d] The concrete verified progress is the exact finite table \(E(1),\ldots,E(80)\), explicit extremizers, and a transparent exhaustive checker. [a] The compactness reduction also separates isolated finite optima from the nested control actually required by the second live question. [c] Neither asymptotic question is resolved; the remaining wall is a uniform rigidity/inverse theorem preventing collision mass from concentrating on too few exceptional sums. PARTIAL: exact finite exception minima E(N) are exhaustively verified for every 1<=N<=80, with explicit witnesses and a 43,083,585-node from-scratch checker; the asymptotic problem remains open.
Search result, stated narrowly
2. A finite extremal quantity
Monotonicity lemma
3. Exact small cases through \(N=80\)
E(1..80) =
1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 3 3 3
3 3 3 3 3 3 3 4 5 5 5 5 5 5 5 6 6 6 6 6
6 6 7 7 7 7 7 7 7 7 8 8 8 9 9 9 9 9 9 10
10 10 10 10 10 10 10 10 10 11 11 11 11 12
12 12 12 12 13 13
Explicit upper-bound witnesses
4. Why the lower-bound search is exhaustive
def search_for_better(N, claimed_optimum):
representations = [0] * (N + 1)
chosen = []
def dfs(k, exceptions_so_far):
if exceptions_so_far >= claimed_optimum:
return None
if k == N:
return chosen.copy() # would disprove the claimed optimum
# x_k = 0; status of k+1 is now final
answer = dfs(k + 1,
exceptions_so_far + (representations[k + 1] != 1))
if answer is not None:
return answer
# x_k = 1; insert all new unordered pairs (a,k), including (k,k)
changed = []
for a in chosen:
if a + k <= N:
representations[a + k] += 1
changed.append(a + k)
if 2 * k <= N:
representations[2 * k] += 1
changed.append(2 * k)
chosen.append(k)
answer = dfs(k + 1,
exceptions_so_far + (representations[k + 1] != 1))
chosen.pop()
for total in changed:
representations[total] -= 1
return answer
# n=1 is necessarily exceptional for positive summands.
return dfs(1, 1)
5. Standalone re-verification
python runs/erdos14_wave5e_verify.py
All 80 upper bounds pass two independent representation counters.
N= 1: no A has < 1 exceptions; 1 DFS nodes
N= 8: no A has < 2 exceptions; 15 DFS nodes
N=18: no A has < 3 exceptions; 115 DFS nodes
N=28: no A has < 4 exceptions; 563 DFS nodes
N=29: no A has < 5 exceptions; 2,453 DFS nodes
N=36: no A has < 6 exceptions; 9,355 DFS nodes
N=43: no A has < 7 exceptions; 33,931 DFS nodes
N=51: no A has < 8 exceptions; 114,673 DFS nodes
N=54: no A has < 9 exceptions; 369,499 DFS nodes
N=60: no A has < 10 exceptions; 1,144,539 DFS nodes
N=70: no A has < 11 exceptions; 3,419,471 DFS nodes
N=74: no A has < 12 exceptions; 9,927,823 DFS nodes
N=79: no A has < 13 exceptions; 28,061,147 DFS nodes
N=80: lower bound inherited by monotonicity
Exhaustive DFS nodes = 43,083,585
Elapsed = 37.208s
FULL FROM-SCRATCH VERIFICATION PASSED
b865246f555c73dbb2c330e2f2db0e8d75f10ebbe0d7bf090782adacfdf4b20f.6. Clean reductions and what remains
Uniform finite reduction for the first question
Exact compactness reduction for the second question
7. Precise wall for standard methods
8. Conclusion