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

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$$.

• Why consider S - S? Seems to me it's a compelling and convincing-enough claim that A ought to intersect just S by itself – Rob Bland Apr 1 at 5:23
• The question in the title seems to be very different from the question in the body (and it's not clear what Sq in the title is). Please edit for clarity/accuracy. – Gerry Myerson Apr 1 at 5:54
• @RobBland If $A$ is the even numbers and $S$ is the odd numbers, then $A$ contains infinitely many multiples of any $k$ and $S$ has upper density $\frac12$, but $A \cap S = \varnothing$. It's $S-S$ that intersects (and equals) $A$. – Misha Lavrov Apr 4 at 0:41

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 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$$.