2
$\begingroup$

I know that Szemerédi's theorem states that any set of integers with positive natural density contains arbitrary long arithmetic progressions. However, does this imply that such a set contains an infinite arithmetic progression? It seems to me that they are not exactly equivalent because the longer progressions may occur only among greater integers in the set. Is this known to be true as well or is there a counterexample?

$\endgroup$

2 Answers 2

2
$\begingroup$

For $n\in\Bbb Z^+$ let $A_n=\{n!-k:0\le k<n\}$, and let $S=\Bbb Z^+\setminus\bigcup_{n\in\Bbb Z^+}A_n$. Since $S$ contains arbitrarily long gaps, $S$ cannot contain an infinite arithmetic sequence. However,

$$\frac{|S\cap[n!]|}{n!}=1-\frac{n(n+1)}{2n!}=1-\frac{n+1}{2(n-1)!}$$

for $n>1$, so $S$ has asymptotic density $1$.

$\endgroup$
0
$\begingroup$

Try constructing a counterexample like follows. Try to construct the earliest (starting at $1$) sequence of integers that contains a growing pattern of arithmetic progressions yet no infinitely long one. Go by intuition for now. I come up with $$1, 2; \ \ 4,5,6; \ \ 8,9,10,11; \ \ 13, 14, 15, 16, 17; \ \ 19,20,21,22,23,24; \ \ 26,27,28,29,30,31,32; \ \dots $$ (semi-colons denote our intentional arithmetic sequences). It consists of the integers $\geq 1$ minus the elements: $3, 7, 12, 18, 25, 33, \dots$. Look this up using Online Encyclopedia of Integer Sequences. So it's probably given by the formula: $$ a(n) = n(n+5)/2 $$ Prove that. Now all you have to prove is that for any $m, b \in \Bbb{Z}_{\geq 1}$:, $b + mk = a(n)$, has a solution $n,k \in \Bbb{Z}_{\geq 1}$, or in other words any infinitely long progression has an element deleted, and hence our constructed sequence contains no infinitely long arithmetic sequence. I don't know how to do that, so I leave it to you.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .