Problem 1112

Let $1\leq d_1<d_2$ and $k\geq 3$ . Does there exist an integer $r$ such that if $B=\{b_1<\cdots\}$ is a lacunary sequence of positive integers with $b_{i+1}\geq rb_i$ then there exists a sequence of positive integers $A=\{a_1<\cdots\}$ such that

d_1\leq a_{i+1}-a_i\leq d_2

for all $i\geq 1$ and $(kA)\cap B=\emptyset$ , where $kA$ is the $k$ -fold sumset?

Second statement

For which integers $k \geq 3$ and $1 \leq d_1 < d_2$ does there exist an integer $r$ such that, whenever $B = \{b_1 < b_2 < \cdots\}$ is a sequence of positive integers with $b_{i+1} \geq r b_i$ for all $i$ , there is a sequence of positive integers $A = \{a_1 < a_2 < \cdots\}$ with $d_1 \leq a_{i+1} - a_i \leq d_2$ for all $i \geq 1$ and $(kA) \cap B = \varnothing$ , where $kA$ is the $k$ -fold sumset? In the site's notation: for which $(k, d_1, d_2)$ does $r_k(d_1, d_2)$ exist?

Source: erdosproblems.com/1112

Additive combinatorics

Wiki page

Status

SolvedAnswered

An accepted solution exists. Settled in another form, for example when its parts resolve differently or the question is open-ended.

OPEN (LEAN), the site's label (page last edited 28 December 2025). The site's proof-claims tab carries a full proof claim by Johan Land (announced on the discussion thread on 2026-07-06, submitted as a proof claim on 2026-07-17, with the AI systems used named on the claim page) that a ratio exists exactly when $d_2\ge k+1$ , with a write-up and a Lean 4 development, the development the Formalization field links as the solution; the site's curator confirmed on the thread on 2026-07-13 that the main Lean theorem of the original development formalizes the question and compiles without sorry, a development replaced on 2026-09-13 by the shortened argument described on the claim page. The claim is accepted on its claim page (Land, 2026) on a port of the original development that this corpus built and audited (see Formalization). The curator has verified only the formalization, not the proof, so this page's solved standing departs from the site's label. Bollobás, Hegyvári and Jin [BHJ97] settled one instance, proving that for $k=3$ and gaps in $[2,3]$ no ratio exists, in the stronger varying-ratio form, an accepted partial claim on its claim page (Bollobás, Hegyvári and Jin, 1997). Tang and Yang [TaYa21], credited by the commentary with further technical nonexistence results, have no claim page: the paper is not held and its journal copy is behind a subscription, and its zbMATH review (Zbl 1499.11038) says only that the authors give growth conditions on $B$ under which $B$ has a subsequence inside $kA$ , without naming the instances they settle, so the paper may settle further instances.

Notes

The site's wording begins "Let $1 \leq d_1 < d_2$ and $k \geq 3$ . Does there exist an integer $r$ ...", which can be read two ways: as one yes-or-no assertion quantified over every triple, or as a separate question for each triple. Under the first reading the answer has been no since 1997: Bollobás, Hegyvári and Jin [BHJ97] proved that for $k = 3$ and gaps in $[2,3]$ no ratio exists. The site's curator reads it the second way. The curator's commentary defines $r_k(d_1,d_2)$ as the least ratio that works for a given triple, records that $r_3(2,3)$ does not exist, and says that "the more general question of existence of $r_k(a,b)$ for $k \geq 3$ remains open"; the problem was posted as open with [BHJ97] already in its commentary, which is only consistent with the per-triple reading. The Statement (precise) above states that reading. The curator also notes that the question is the curator's own generous reading of a vague remark of Erdős and Graham [ErGr80, p. 18], so the Statement is the site's question rather than Erdős's words. Under the precise Statement Johan Land's dichotomy (a ratio exists exactly when $d_2 \geq k+1$ , with the ratio $192 d_2$ in the built development and $d_2 + 2$ in the September 2026 revision) settles every triple, so the problem is solved; [BHJ97] settles the triple $(3,2,3)$ and is a partial claim. The site keeps the label OPEN (LEAN): on 13 July 2026 the curator confirmed on the thread that erdos_1112 is a correct formalization and compiles without sorry, and wrote of not yet having tried to understand the proof; the acceptance here rests instead on the port of Land's development that this corpus built and audited.

BHJ97: Bollobás, Béla and Hegyvári, Norbert and Jin, Guoping, On a problem of Erdős and Graham. Discrete Math. (1997), 253-257.
Ch00: Chen, Yong-Gao, On sums and intersects of sequences. Discrete Math. (2000), 351-354.
ErGr80: Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980); p. 18.
TaYa21: Tang, Min and Yang, Quan-Hui, On a problem of Erdős and Graham. Publ. Math. Debrecen (2021), 485-493.

Problem 1112

Second statement

Status

Notes

Proof claims

Discussion