Erdős Problem #1112

declared status 'open'. Formalized: no. 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? Current best: Erd\H{o}s and Graham [ErGr80] noted that if $B=\{b_1<b_2<\cdots\}$ with $b_1\geq 5$ and $b_{i+1}\geq 2b_i$ then there is a set $A=\{a_1<a_2<\cdots\}$ with $2\leq a_{k+1}-a_k\leq 3$ for all $k$ such that $(A+A)\cap B=\emptyset$. Bollob\'{a}s, Hegyv\'{a}ri, and Jin [BHJ97] provide a negative answer in that, for any sequence of integers $1\leq r_1<r_2<\cdots$, there is a $B$ as above with $b_{i+1}\geq r_ib_i$ such that $(A+A+A)\cap B\neq\emptyset$ for any $A$ with $2\leq a_{i+1}-a_i\leq 3$. They define, more generally, $r_k(d_1,d_2)$ as the smallest $r$ (if it exists) such that if $b_{i+1}\geq rb_i$ then there exists $A$ with $d_1\leq a_{i+1}-a_i\leq d_2$ such that $(kA)\cap B=\emptyset$, where $kA$ is the $k$-fold sumset. The more general question of existence of $r_k(a,b)$ for $k\geq 3$ remains open. Prize: no. Tags: additive combinatorics.

Notation is rendered from the stored source. The pinned checkout remains the exact record.