Problem #1112: Let $1\leq d_1

Let $1\leq d_1

SOLVED

---

Progress

Erdő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ás, Hegyvári, and Jin [BHJ97] showed that such an $A$ must exist if $b_{i+1}\geq 2b_i-O(1)$, and that this is best possible.

Erdős and Graham go on to say 'whether such behavior can hold for $A+A+A$ (or more summands) is not known'. The above question is my best interpretation of what they intended.

Bollobás, Hegyvá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.

It follows from the above results that $r_2(2,3)=2$ and that $r_3(2,3)$ does not exist. Chen [Ch00] proved that $r_2(a,b)\leq 2$ for any integers $a<b$ with $b\neq 2a$, and that $r_2(a,2a)\geq 2$ for all integers $a$. The more general question of existence of $r_k(a,b)$ for $k\geq 3$ remains open.

Some further technical non-existence results are given by Tang and Yang [TaYa21].

[Note the stated problem is a generous interpretation of a very ambiguous remark in [ErGr80], so it might be more appropriate to call this a problem 'inspired by Erdős and Graham'.]