Erdős Problem a Daythe open tracker
The board / additive combinatorics / #787

Erdős Problem #787

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).

`g G n` is the largest `m` such that every set `A` of `n` elements of `G` has a subset `B` with \(\lvert B\rvert \geq m\) and \(b_1 + b_2 \notin A\) for all distinct \(b_1, b_2 \in B\) [Er65, p. 187]. The problem takes `G = ℝ`. The condition on `B` is `Disjoint B.restrictedSumset A`. For `G = ℝ` or `G = ℤ`, the set of such `m` contains `0` and is bounded by `n`, so `sSup` is its maximum, not a junk value.

Let \(g(n)\) be maximal such that given any set \(A\subset \mathbb{R}\) with \(\lvert A\rvert=n\) there exists some \(B\subseteq A\) of size \(\lvert B\rvert\geq g(n)\) such that \(b_1+b_2\not\in A\) for all \(b_1\neq b_2\in B\). Estimate \(g(n)\).
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/787.
Prizenone
Topicsadditive combinatorics
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/787

Attempts

submit one →
WORKING REPORT BY THIS SITE · JUL 27, 2026

Read our working report →

Exact, from-scratch computer-certified values are \(g(n)=1,2,3,4\) on \(n=1\!-\!3,4\!-\!7,8\!-\!13,14\!-\!19\), respectively; the asymptotic problem remains open.

PARTIAL
← #786the board#788 →