A set with positive upper density whose difference set does not contain an infinite arithmetic progression

Question

For $S \subset \mathbb{N}$ define $S-S=\{x-y:x \in S, y \in S\}$.

As noted below there is a simple example showing that a set $S \subset \mathbb{N}$ with positive upper density has a sumset $S+S=\{x+y:x \in S, y \in S\}$ with $S+S$ containing only finite length arithmetic progressions. However the case for the difference set seems not so obvious to me hence the question:

What is an example of a set S with positive upper density in $\mathbb{N}$ such that $S-S$ does not contain an infinite arithmetic progression?

Here is the example for the sumset $S+S$, in fact for any $hS=S+\dots+S$, taken from Erdos, Nathason and Sarkozy's paper "Sumsets Containing Infinite Arithmetic Progressions":

"Let $(t_n)$ be a strictly increasing sequence of positive integers such that $t_{n+1}/t_n$ tends to infinity, and let the set $A$ be the union of the intervals $[t_{2n}+1, t_{2n+1}]$. Then $A$ has upper asymptotic density $d_U(A) = 1$ and lower asymptotic density $d_L(A)=0$. For fixed $h$ and all sufficiently large $n$, the sumset $hA$ is disjoint from the interval $[h t_{2n-1} + 1, t_{2n}]$. Thus, $hA$ contains arbitrarily long gaps, and so cannot contain an infinite arithmetic progression."

Answer 1

Let $\langle x\rangle$ denote the fractional part of a real number $x$ (i.e. $\langle x \rangle := x- \lfloor x\rfloor $, where $\lfloor x\rfloor $ is the greatest integer less than or equal to $x$).

Let $\alpha \in \mathbb R$ be irrational and let $S:=\{n\in \mathbb Z: \langle n\alpha \rangle \in (0,1/4)\}$. The upper (and lower) density of $S$ is $1/4$; this is a consequence of Weyl's theorem on uniform distribution. Also, $S-S\subseteq \{n\in \mathbb Z: \langle n\alpha\rangle \in (3/4,1)\cup [0,1/4)\}$.

To see that $S-S$ does not contain an infinite arithmetic progression $\{a+bn:n\in \mathbb N\}$, note that $b\alpha$ is irrational if $b\in \mathbb Z\setminus \{0\}$, so the values $\langle (a+bn)\alpha \rangle$ are dense in $[0,1]$. So if $S-S$ contained an infinite AP, the values $\{\langle n\alpha \rangle:n\in S-S\}$ would be dense in $[0,1]$, but $\langle n\alpha\rangle \in (3/4,1)\cup [0,1/4)$ for $n\in S-S$.

This example $S$ is a Bohr neighborhood in $\mathbb Z$. Generally, if you want an example or counterexample of some structure in $S-S$, where $S$ has positive upper density, it's natural to look among Bohr neighborhoods: Følner ZBL0058.02302 proved that if $S$ has positive upper Banach density, then $S-S$ contains (up to upper Banach density 0) a Bohr neighborhood of $0$. Since every Bohr neighborhood $B$ of $0$ contains a set of the form $B'-B'$, where $B'$ is a Bohr neighborhood, $S-S$ itself is not too far from containing a difference set of a Bohr neighborhood.

Ruzsa's section Sumsets and structure in ZBL1221.11026 and Hegyvári and Ruzsa's article ZBL1333.05042 are both good references on the relationship between Bohr sets and difference sets.

Answer 2

A similar to John Griesmer's example is the set $S:=\{\lfloor n\alpha\rfloor,n=1,2,\ldots\}$, where $\alpha>100$ is an irrational number. Note that $\lfloor n\alpha\rfloor-\lfloor k\alpha\rfloor=\lfloor (n-k)\alpha\rfloor+\delta$ where $|\delta|\leqslant 1$. But for any arithmetic progression $A,A+D,A+2D,\ldots$ we may find a term which is within distance, say, 1 from some $k\alpha+\alpha/2$ with integer $k$ (this is because the set $\{k\alpha-mD:k,m\in \mathbb{Z}_{>0}\}$ is everywhere dense by Kronecker lemma.) It does not belong to $S-S$ by above.

Answer 3

If the complement of $S-S$ contains two integers that are relatively prime, the density of $S$ is strictly smaller than 1/2. So a density of 1/2 is not possible.

It is possible to get the density of $S$ arbitrarily close to 1/2. To show this, note that there are countably many infinite arithmetic sequences and number them $L_1,L_2,L_3,\ldots$. For each natural number $k$ we will recursively define $a_k\in L_k$ and an $a_k+1$-periodic set $S_k$ such that $a_i\not\in S_k-S_k$ for $i\leq k$. The sequence $(a_k)$ will be increasing. We can assume that $a_1=1$ and choose $S_1$ the odd numbers.

For the recursion step, pick $a_{k+1} \in L_{k+1}$ large enough. Let $S_{k+1}$ be the $a_{k+1}$-periodic extension of the set $S_k\cap \{1,2,\ldots,a_{k+1}-a_k\}$. The difference between the different 'parts' of $S_{k+1}$ is larger than $a_k$, so $S_{k+1}-S_{k+1}$ still does not contain $a_i$ for $i\leq k$. Moreover, since $1\not\in S_{k+1}-S_{k+1}$ and $S_{k+1}$ is $a_{k+1}+1$-periodic, also $a_{k+1}\not\in S_{k+1}-S_{k+1}$. The density of $S_{k+1}$ will be at most $\frac{a_k}{a_{k+1}}$ less than the density of $S_k$.

Since the first $a_k$ numbers do not change after $S_k$ is fixed, we can define the limit set $S$, which will have density arbitrarily close to 1/2. It will contain all $a_k$, so it will not contain an infinite arithmetic sequence.