Set with Positive Upper Density and No Infinite Arithmetic Progression – Combinatorics

additive-combinatoricsarithmetic-progressionco.combinatorics

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

Best Answer

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.