Problem 875

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\}

are disjoint for distinct $r\geq 1$ . 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}$ ?

Source: erdosproblems.com/875

Additive combinatorics

Wiki page

Status

Open

No claim settles this problem.

Open. The site's label is OPEN (on 2026-09-18 and on 2026-10-06). What the primary sources give, each with the page it comes from: every infinite admissible $A$ has $A(x)\le2\sqrt{x+1/4}-1$ for $x\ge N_0$ (Theorem 1 of Deshouillers and Freiman applied to $A\cap[1,x]$ ), so $a_n\ge n(n+2)/4$ for large $n$ and a gap bound $a_{n+1}-a_n\le n^c$ for all large $n$ forces $c\ge1$ ; Erdős, Nicolas and Sárközy construct an infinite admissible $A$ with $A(x)\gg x^{5-2\sqrt6}$ (Théorème 2), whence $a_n\ll n^{5+2\sqrt6}$ and trivially $a_{n+1}-a_n\ll n^{5+2\sqrt6}$ ( $5+2\sqrt6=9.899\ldots$ ), with an implied constant; Erdős (1962) had constructed such a sequence with $A(x)>cx^\alpha$ for an unspecified $\alpha>0$ . The two one-line deductions are made on this page and named as such. So $c\ge1$ is necessary, and every $c>5+2\sqrt6$ is possible for all large $n$ ; no source found places $c$ between them, and none gives an admissible sequence with $a_{n+1}/a_n\to1$ (Erdős's 1998 remark is quoted from the site; the paper is not held). A note in the site's thread, generated with GPT-5.5 Pro and accompanied by a Lean development, claims gaps at most $n^{3+2\sqrt2}$ for every $n$ and $o(n^{3+2\sqrt2})$ , with $3+2\sqrt2=5.828\ldots$ ; it has a partial claim page, Mazur's admissible sequence, with status claimed, and is not a source for the bounds above. This is a bounded negative finding, not a certificate of openness.

Er98: Erdős, P., Some of my new and almost new problems and results in combinatorial number theory. Number theory (Eger, 1996), de Gruyter (1998), 169--180. Not held; the site's only key, quoted through the site's commentary.
ENS91: Erdős, P., Nicolas, J.-L. and Sárközy, A., Sommes de sous-ensembles. Sém. Théor. Nombres Bordeaux (2) 3 (1991), no. 1, 55--72, doi:10.5802/jtnb.42. Section 5, pp. 65--69: Théorème 2. Library home: Erdős, Nicolas and Sárközy 1991; result page Théorème 2.
DeFr99: Deshouillers, J.-M. and Freiman, G. A., On an additive problem of Erdős and Straus, 2. Astérisque 258 (1999), 141--148. Theorem 1, p. 142. Library home: Deshouillers 1999; result page Theorem 1.
DeFr95: Deshouillers, J.-M. and Freiman, G. A., On an additive problem of Erdős and Straus, 1. Israel J. Math. 92 (1995), 33--43, doi:10.1007/BF02762069. Theorem 1, p. 34: an admissible subset of $[1,N]$ has at most $2N^{1/2}+CN^{5/12}$ elements, the earlier bound superseded by Theorem 1 of [DeFr99] and giving the same $c\ge1$ by the same deduction. Library home: Deshouillers and Freiman 1995; result page Theorem 1.
Er62c: Erdős, P., Számelméleti megjegyzések, III. Mat. Lapok 13 (1962), 28--38 (Hungarian); the construction (16') on printed p. 34 and the English summary, p. 38. Library home: Erdős 1962; result page Theorem IV (the construction is recorded there).
Ma26: Mazur, L. (with GPT-5.5 Pro listed as first author), On an absolute-gap variant of Erdős Problem #875: an infinite admissible set with $a_{n+1}-a_n\le n^{3+2\sqrt2}$ and little-o gaps. A note under docs/ of the GitHub repository lechmazur/erdos_875 (created 2026-05-07; its head revision of 2026-05-09 is pinned by the links of the claim page), beside a Lean development; linked from the thread on 7 May 2026. Read status: the README, the statement map and the note's statements checked; the proofs unread. Claim page: Mazur's admissible sequence.

Problem 875

Status

Proof claims

Discussion