9
$\begingroup$

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

$\endgroup$

3 Answers 3

13
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ John thank you for this great answer which I found really helpful and unexpected. The Bohr neighbourhood concept is very interesting thanks for the references! $\endgroup$
    – Ivan Meir
    Feb 21, 2022 at 17:46
7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Another very interesting example thank you. Simple to understand and quite intuitive. $\endgroup$
    – Ivan Meir
    Feb 21, 2022 at 17:50
6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ It's taken me a while to absorb this solution. I definitely like the fact that it essentially stays within the integers for the construction. Would you be able to expand on your opening paragraph explaining why a density of more than 1/2 is unachievable as I'm not completely clear on the argument? $\endgroup$
    – Ivan Meir
    Feb 23, 2022 at 13:26
  • $\begingroup$ Suppose a and b are relatively prime and not in S-S. If the density of S is 1/2, then there are arbitrarily long stretches of integers where S contains at least half of them. Then, for each x in this stretch, either $x\in S$ or $x+a\in S$. Also either $x\in S$ or $x+b\in S$. Since we can write $ma+nb=1$ for some integers $m,n$, it will follow that $x\in S$ implies either $x+1\in S$ or $x+1\not\in S$ (depending on parity of $m+n$). In both cases we get a contradiction. $\endgroup$
    – Squala
    Feb 23, 2022 at 13:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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