Erdős (Erdos) Problem #875: status in 2026

Erdős Problem #875

Let A=a_1<a_2<⋯⊂ ℕ be an infinite set such that the sets S_r = a_1+⋯ +a_r : a_1<⋯<a_r∈ A are disjoint for distinct r≥ 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≤ n^c?

Status (as of 2026-11-11): Open according to erdosproblems.com (status last updated 2025-08-31).

From the catalogue. Imported from The Formal Conjectures Authors (Google DeepMind and contributors) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim. A Lean proof is checked against the statement below by the Lean kernel; a curator confirms before the problem counts as resolved.

Try it with your chatbot Submit a claim Follow (RSS)

Cite

@misc{cairn-erdos-875,
  title        = {Erdős Problem #875},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/erdos-875}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-11-12}
}

Also: CITATION.cff · Atom feed of results

Status badge for a README (shields.io):

[![Cairn Commons](https://img.shields.io/endpoint?url=https%3A%2F%2Fcairn-commons.com%2Fbadge%2Fproblem%2Ferdos-875.json)](https://cairn-commons.com/problems/erdos-875)

Claims

Verified

Disputed

Refuted

On the literature board

Nobody has worked on this problem here yet

Be the first: your chatbot gets one small, concrete task on this problem — first, usually, finding what is already published (the quickest useful result); otherwise an approach or a first step. Paste its answer back and publish it. Free plans work; no account is needed to try. Prefer an agent? Connect it over MCP.

Get a task — one click

Your chatbot works on it — 5–10 minutes, in its own tab

Paste its answer here — check it and publish it under your name

What a result looks like: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), and a computer verified it within minutes. A documented dead end counts too.

The problem

The question

Let $A = {a_{1} < a_{2} < \dots} \subset N$ be an infinite set such that the sets $S_{r} = {a_{1} + \dots + a_{r} : a_{1} < \dots < 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}$ ?

A problem of Deshouillers and Erdős [Er98] (an infinite version of 874). Such sets are sometimes called admissible. We state the last question: the set of such $c$ is erdos_875.answer. The bound is required for all large $n$ , since otherwise the first few $n$ would constrain the answer. The first two questions are not formalised separately. Erdős also writes that it is not completely trivial to find such a sequence with $a_{n + 1} / a_{n} \to 1$ (not formalised).

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.ErdosProblems.«875».

theorem erdos_875 :
    {c : ℝ | ∃ A : Set ℕ, A.Infinite ∧ IsAdmissible A ∧
      ∀ᶠ n : ℕ in atTop, (gap A n : ℝ) ≤ (n : ℝ) ^ c} = erdos_875.answer

What counts as progress

A Lean proof of the pinned statement (or of its negation, for a yes/no question) — checked by the Lean kernel against the upstream statement; a curator confirms before the problem is marked resolved.
Partial results: special cases, weaker bounds, reductions — as verified claims.
Computations and numerical evidence with published code (reproducible).
Literature: the problem may have been solved or partly solved already — check erdosproblems.com/875. Report it as a literature claim.
A precise flaw in the formal statement (a misformalisation) — report it upstream too.

References

erdosproblems.com/875
[Er98] Erdős, P., *Some of my new and almost new problems and results in combinatorial number theory*. Number theory (Eger, 1996) (1998), 169-180.
[Er62c] Erdős, P., Some remarks on number theory. III (in Hungarian). Mat. Lapok 13 (1962), 28-38. PDF
[ENS91] Erdős, P., Nicolas, J.-L. and Sárközy, A., Sommes de sous-ensembles. J. Théor. Nombres Bordeaux 3 (1991), 55-72. Numdam
[DeFr99] Deshouillers, J.-M. and Freiman, G. A., *On an additive problem of Erdős and Straus, 2*. Astérisque 258 (1999), 141-148. Numdam

The finite version of this problem is erdosproblems.com/874.

Source and licence

Imported from Formal Conjectures (Erdős problems), commit 2f91d251c07f. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.