If a set has infinitely many multiples of each integers, then it intersects (S-S) for any set S with positive upper density

Question

I wanted to know whether above statement is true. If it is, how can one go about proving it?

Say A $\subset\mathbb{N}$ is a set such that $\forall$ k $\in\mathbb{N}$ , A contains infinitely many multiples of k. Let S $\subset\mathbb{N}$ is such that limsup$_{n\rightarrow\infty}$ $\frac{|S \cap [1,n]|}{n}$ $>$ 0 i.e. S has positive upper density. Is it true that A $\cap$ (S-S) $\neq\emptyset$.

Answer 1

The statement is not true.

Let $A = \{(2k)! : k \in \mathbb N\}$. We construct a large $A$-difference-free set $S$ iteratively: for each $k$, we'll construct $S_k$ to be a subset of $\{0, 1, \dots, (2k)!-1\}$ such that $S_k - S_k \cap A = \varnothing$, and extend $S_k$ to form $S_{k+1}$.

Start with pretty much any base case you like; e.g., take $S_3 = \{42\}$ because $42$ is your favorite number.

To construct $S_{k+1}$ from $S_k$, let $d = (2k)! + (2k-2)!$ and take the union $$ S_k \cup (S_k + d) \cup (S_k + 2d) \cup \dotsb $$ for as long as possible without exceeding $(2k+2)!$. This is $\Theta(k^2)$ translates of $S_k$. Call this union $S_{k+1}$.

First, we show that $S_{k+1} - S_{k+1} \cap A = \varnothing$. There are three cases:

• $S_{k+1} - S_{k+1}$ does not contain $(2i)!$ for $i<k$ because the gap $d$ is too large for different translates of $S_k$ to be differ by $(2i)!$, and within the same translate of $S_k$, we already know $S_k - S_k$ does not contain $(2i)!$.
• $S_{k+1} - S_{k+1}$ does not contain $(2i)!$ for $i>k$ because all the elements of $S_{k+1}$ are smaller than $(2i)!$.
• Suppose $S_{k+1} - S_{k+1}$ contains $(2k)!$. Only adjacent differences $S_k + jd$ and $S_k + (j+1)d$ are close enough for two of their elements to differ by $(2k)!$. But $$x + jd + (2k)! = y + (j+1)d \implies x + (2k)! = y + d \implies x = y + (2k-2)!,$$ and this cannot happen for any $x,y \in S_k$ because $S_k - S_k \cap A = \varnothing$.

Second, we show that $S_{k+1}$'s density in $\{0,1,\dots,(2k+2)!-1\}$ is not much lower than $S_k$'s density in $\{0,1,\dots,(2k)!-1\}$.

By translating by $d$, we are looking at $S_k$'s density in $\{0,1,\dots,d-1\}$ instead of $\{0,1,\dots,(2k)!-1\}$, which is off by a factor of $\frac{(2k)!}{(2k)!+(2k-2)!} = 1 - O(\frac1{k^2})$. Also, the last translate of $S_k$ might be cut off a little bit to avoid exceeding $(2k+2)!$, but there are $\Theta(k^2)$ translates, so this also hurts density by at most a factor of $1 - O(\frac1{k^2})$. Products of the form $$ \prod_k \left(1 - O(\tfrac1{k^2})\right) $$ converge to positive values, so we get a positive lower bound on the density of $S_k$ in $\{0,1,\dots,(2k)!-1\}$ for all $k$. Therefore $S = \bigcup_k S_k$ has a positive upper density and yet $(S - S) \cap A = \varnothing$.