Problem #26: Let $A\subset\mathbb{N}$ be infinite

---

Progress

Asked by Erdős and Tenenbaum. Ruzsa gave the following simple counterexample: let $A=\{n_1<n_2<\cdots \}$ where $n_l \equiv -(k-1)\pmod{p_k}$ for all $k\leq l$, where $p_k$ denotes the $k$th prime.

A sequence $A$ is a Behrend sequence if almost all integers have a divisor in $A$, so that this question asks whether, for every infinite set $A$, there exists $k\geq 1$ such that $A+k$ is a Behrend sequence.

Davenport and Erdős [DaEr51] (see also Tenenbaum [Te13]) showed that $\sum\frac{1}{a}=\infty$ for every Behrend sequence $A$, which immediately implies the answer to this question is no (taking $A$ any infinite sequence with $\sum \frac{1}{a}<\infty$). (It is therefore strange why Erdős asked this question over 40 years later.)


In the comments van Doorn explains how Ruzsa's construction above can be modified to produce a counterexample with $\sum\frac{1}{a}=\infty$.

Tenenbaum asked the weaker variant (still open) where for every $\epsilon>0$ there is some $k=k(\epsilon)$ such that at least $1-\epsilon$ density of all integers have a divisor of the form $a+k$ for some $a\in A$.