Thresholds $r_k(d_1,d_2)$: bounded-gap sequences whose $k$-fold sumsets avoid lacunary sets (Erdős #1112)
Statement
Let $1\leq d_1<d_2$ and $k\geq 3$. Does there exist an integer $r$ such that if $B=\{b_1<b_2<\cdots\}$ is a lacunary sequence of positive integers with $b_{i+1}\geq rb_i$ for all $i$, then there exists 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=\emptyset$, where $kA=\{x_1+\cdots+x_k:x_1,\ldots,x_k\in A\}$ is the $k$-fold sumset? Following Bollobás–Hegyvári–Jin, write $r_k(d_1,d_2)$ for the smallest such $r$ when one exists; the problem is to determine for which triples $(d_1,d_2,k)$ with $k\geq 3$ the threshold $r_k(d_1,d_2)$ exists (it is known not to exist for some parameters — see background).
Acceptance. FULLY RESOLVES: a proof — machine-checkable (Lean/Coq) preferred, else a complete written proof — determining exactly for which triples $(d_1,d_2,k)$ with $1\leq d_1<d_2$ and $k\geq 3$ the threshold $r_k(d_1,d_2)$ exists (and, where it exists, giving its value or bounds). ADVANCES: a proof settling existence or non-existence of $r_k(d_1,d_2)$ for any explicit family of parameters not already covered by the results stated in the background (e.g. $r_3(d_1,d_2)$ for gap windows other than $[2,3]$, or any $k\geq 4$ case); a proof extending the Tang–Yang non-existence region; or a Lean formalisation of the statement together with the known [BHJ97]/[Ch00] results. Computer searches over residue patterns may support a construction but cannot alone certify a statement about all infinite lacunary sequences. Deliver the proof file (plus any supporting search code).
Background
This is Bloom's formalisation of a remark of Erdős and Graham [ErGr80, p.18]; the site itself notes the stated problem is a 'generous interpretation of a very ambiguous remark', so it is best regarded as a problem inspired by Erdős–Graham. Listed as open on erdosproblems.com/1112 (fetched 2026-07-13, status 'open', tagged 'additive combinatorics'; page last edited 28 December 2025). The two-fold case is understood: Erdős and Graham [ErGr80] noted that if $b_1\geq 5$ and $b_{i+1}\geq 2b_i$ then there is an $A$ with gaps in $[2,3]$ and $(A+A)\cap B=\emptyset$; Bollobás, Hegyvári, and Jin [BHJ97] showed such an $A$ exists whenever $b_{i+1}\geq 2b_i-O(1)$ and that this is best possible, giving $r_2(2,3)=2$. Chen [Ch00] proved $r_2(a,b)\leq 2$ for any integers $a<b$ with $b\neq 2a$, and $r_2(a,2a)\geq 2$ for all $a$. For three or more summands, Erdős–Graham wrote that 'whether such behavior can hold for $A+A+A$ (or more summands) is not known'. Here [BHJ97] gives a strong negative result: for any sequence of integers $1\leq r_1<r_2<\cdots$ there is a $B$ with $b_{i+1}\geq r_ib_i$ such that $(A+A+A)\cap B\neq\emptyset$ for every $A$ with gaps in $[2,3]$ — so $r_3(2,3)$ does not exist. Tang and Yang [TaYa21] give further technical non-existence results. The general existence question for $r_k(d_1,d_2)$ with $k\geq 3$ (for which gap windows, if any, does a threshold exist?) remains open. Caveat for a would-be solver: the site records that a solution claim has been posted in the problem's comment section but has not been vetted or incorporated into the remarks — do a literature/forum check before investing effort. The attacker's tool: Bollobás–Hegyvári–Jin-style diagonal constructions of bad lacunary $B$ (for non-existence) versus explicit periodic/near-periodic constructions of $A$ with certified sumset avoidance (for existence), with finite computer searches over residue patterns guiding both; the final artifact is a proof about infinite sequences.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1112 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #1112 — discussion thread (contains an unvetted solution claim) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.