Admissible sequences with disjoint $r$-fold sum sets: how small can the gaps $a_{n+1}-a_n$ be? (Erdős #875)
Statement
Let $A=\{a_1<a_2<\cdots\}\subset \mathbb{N}$ be an infinite set such that the sets $$S_r = \{ a_1+\cdots +a_r : a_1<\cdots<a_r\in A\}$$ (the sums of $r$ distinct elements of $A$) are disjoint for distinct $r\geq 1$ — so the value of a sum of distinct elements of $A$ determines how many summands were used. How fast can such a sequence grow? How small can $a_{n+1}-a_n$ be? In particular, for which $c$ is it possible that $a_{n+1}-a_n\leq n^{c}$?
Acceptance. FULLY RESOLVES: determine the optimal gap exponent — identify the infimum $c_0$ of constants $c$ for which an admissible sequence with $a_{n+1}-a_n\leq n^{c}$ (for all large $n$) exists, with (i) an explicit construction and complete admissibility proof attaining every $c>c_0$ (or $c_0$ itself), and (ii) a proof that no admissible sequence achieves $c<c_0$. Machine-checkable (Lean/Coq) proof preferred; otherwise a complete written proof with all steps. ADVANCES: (a) an explicit admissible sequence with a proven polynomial gap bound $a_{n+1}-a_n\leq n^{c}$ for a concrete $c$, or even with $a_{n+1}/a_n\to 1$, with a complete proof that all $S_r$ are pairwise disjoint; (b) a proof that admissibility forces $a_{n+1}-a_n$ to exceed some explicit growth rate infinitely often; (c) computationally constructed admissible prefixes of substantial length via greedy/backtracking search, with reproducible code, machine-checkable admissibility certificates for the prefix, and an empirical gap-growth analysis. Deliver the construction + proof, or the proof file, or the search code + certified prefixes.
Background
A problem of Deshouillers and Erdős [Er98], the infinite version of Erdős #874 (erdosproblems.com/874); such sets are sometimes called admissible. Listed as open on erdosproblems.com/875 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics'). For orientation: the powers of 2 are admissible (a sum of $r$ distinct powers of 2 has binary weight exactly $r$, so $S_r$ and $S_s$ are disjoint for $r\neq s$), but they grow geometrically. The problem asks how slowly an admissible sequence can grow: Erdős wrote that it is not 'completely trivial to find such a sequence for which $a_{n+1}/a_n\to 1$', and the site notes it is unclear whether Deshouillers and Erdős even knew of one — polynomial gap bounds $a_{n+1}-a_n\leq n^c$ are the quantitative target, with no bounds stated on the page in either direction. The same distinct-length-sums property for finite subsets of arbitrary sets is Erdős #789 (erdosproblems.com/789), where the extremal size is known to lie between $(n\log n)^{1/3}$ and $n^{1/2}$. As of the fetch date the site flags comment activity claiming partial results not yet incorporated into the remarks (7 comments; thread at erdosproblems.com/forum/thread/875) — a solver should check that thread first. The attacker's tools: explicit digit- or congruence-based constructions with full admissibility proofs; greedy/backtracking computer construction of long admissible prefixes (admissibility of a finite prefix is finitely checkable) to measure attainable gap growth; and counting arguments for lower bounds on gaps.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #875 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #874 — the finite version | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.