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

  • $\begingroup$ Why consider S - S? Seems to me it's a compelling and convincing-enough claim that A ought to intersect just S by itself $\endgroup$ – Rob Bland Apr 1 at 5:23
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Apr 1 at 5:54
  • $\begingroup$ @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$. $\endgroup$ – 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<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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.