Skip to main content
MathOverflow

Return to Question

Post Timeline

Removed the ? in title after previous edit.
Link
Ivan Meir
Ivan Meir
  • 5.1k
  • 3
  • 35
  • 43

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

deleted 11 characters in body; edited title
Source Link
Greg Martin
Greg Martin
  • 13.1k
  • 2
  • 51
  • 77

Give a A set with positive upper density whose difference set does not contain an infinite length arithmetic progression?

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 of unbounded length?

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

Give a set with positive upper density whose difference set does not contain an infinite length arithmetic progression

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 arithmetic progression of unbounded length?

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

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

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

Became Hot Network Question
Source Link
Ivan Meir
Ivan Meir
  • 5.1k
  • 3
  • 35
  • 43

Give a set with positive upper density whose difference set does not contain an infinite length arithmetic progression

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 arithmetic progression of unbounded length?

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