Erdős Problem a Daythe open tracker

Erdős Problem #876

OPENdatabase updated 2025-08-31

No proof or disproof is known, and it isn't known whether a finite computation could settle it.

What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).

`A` is *sum-free* in the sense of Erdős: its elements are positive and no element is a sum of distinct smaller elements of `A`. The condition `0 < a` fits \(A\subset\mathbb{N}\) with \(\mathbb{N}=\{1,2,\ldots\}\) and makes the empty sum \(0\) harmless. A single smaller element cannot equal `a`, so only sums of \(r\geq 2\) elements matter. This differs from the usual `IsSumFree`: sums of any number of distinct smaller elements are forbidden, but \(a=b+b\) is allowed.

For an infinite set `A = {a₁ < a₂ < ⋯}`, `Nat.nth (· ∈ A) k` is \(a_{k+1}\), because the enumeration starts at index `0`. Hence `gap A n` is \(a_{n+1}-a_n\) for \(n\geq 1\). The value at `n = 0` is junk and is never used, since the statements below only concern large `n`.

`maxRecipSum` is the supremum of \(\sum_{a\in A}1/a\) over infinite sum-free sets `A`. Only convergent sums are taken (`HasSum`), so no junk value occurs. The set of values is nonempty (the powers of \(2\) give \(2\)) and bounded above by \(103\) [Er62c], so `sSup` is the true supremum, which may or may not be attained.

Let \(A=\{a_1<a_2<\cdots\}\subset \mathbb{N}\) be an infinite sum-free set - that is, there are no solutions to \[a=b_1+\cdots+b_r\] with \(b_1<\cdots<b_r<a\in A\). How small can \(a_{n+1}-a_n\) be? Is it possible that \(a_{n+1}-a_n<n\)? The gap question is discussed by Erdős in [Er98]. We state the second question. The inequality \(a_{n+1}-a_n<n\) is required for all large \(n\), because it fails for \(n=1\). The first question is vaguer and is not formalised.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 6 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/876.
Prizenone
Topicsadditive combinatorics
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/876
WORKING REPORT BY THIS SITE · JUL 28, 2026

Read our working report →

The live page is marked OPEN but lists 1 partial claimed proof (Liam Price using GPT-5.6 Sol Pro, submitted 2026-07-18) asserting that every infinite sum-free sequence satisfies \(\limsup_{n\to\infty}

SKIPPED