# Is there a set of positive integers of density 1 which contains no infinite arithmetic progression?

Let $$V$$ be a set of positive integers whose natural density is 1. Is it necessarily true that $$V$$ contains an infinite arithmetic progression?—i.e., that there are non-negative integers $$a,b,\nu$$ with $$0\leq b\leq a-1$$ so that: $$\left\{ an+b:n\geq\nu\right\} \subseteq V$$

In addition to an answer, any references on the matter would be most appreciated.

• Enumerate all the arithmetic progressions as $A_n$. Now remove from $\mathbb N$ the $2^n$-th element of $A_n$ for each $n$. Jun 6, 2019 at 21:33
• So sets that contradict this exist? Excellent! Thank you. :)
– MCS
Jun 6, 2019 at 21:35
• Generalizing Wojowu’s construction shows that “density 1” can be achieved in the strongest possible way: for any function $f$ that tends to infinity, no matter how slowly, there is a set of non-negative integers containing at least $n-f(n)$ integers between $1$ and $n$ for each $n$ but no infinite arithmetic progression. Jun 6, 2019 at 22:49
• A more constructive way would be the following: Take any increasing function $f$, and put $V=\mathbb{N}\setminus\bigcup_{n\geq 1} [f(n), f(n)+n]$. If $f$ grows faster than $n^2$, than $V$ has density 1. By increasing the growth of $f$ you can make $\mathbb{N}\setminus V$ arbitrary small. Jun 7, 2019 at 12:35
• The answer I had in mind is already written up here. This example arises in a different context [finding arbitrarily long strings of consecutive composite numbers] and/but satisfies the criterion here, too. Jun 9, 2019 at 18:45

Another construction is to let $$n \notin V$$ if and only if $$n$$ begins with at least $$\sqrt{\log{n}}$$ consecutive '9's when written in decimal. This satisfies the stronger property that there is no non-constant polynomial $$f : \mathbb{N} \rightarrow \mathbb{N}$$ whose image is contained entirely in $$V$$.

Here is a concrete counterexample (where $$\mathbb{N}$$ is the set of positive integers): $$V:=\mathbb{N}\setminus\{a^2b^2+b:a,b\in\mathbb{N}\}.$$ It is straightforward to see that $$V$$ has density $$1$$, but it does not contain an infinite arithmetic progression.

• Here is a straightforward proof for anyone else who found the density non-obvious: In $\{(a,b):a^2b^2+b<N\}$, each value of $b$ has at most $\sqrt{N}/b$ values of $a$. Also $b<\sqrt{N}$. So the cardinality of the set is at most $$\sum_{b=1}^\sqrt{N} \frac{\sqrt{N}}{b} < 2\int_1^{\sqrt{N}+1}\frac{\sqrt{N}}{b}db< 2\sqrt{N}\ln(N)$$ Since $2\sqrt{N}\ln(N)/N\rightarrow 0$, the density of these sets goes to 0. Jun 7, 2019 at 19:04

Yet another concrete counterexample: $$\bigcup_{n=1}^\infty [n^3+n,(n+1)^3].$$ More generally, any set containing arbitrarily long gaps is free of infinite arithmetic progressions, and has natural density $$1$$ if the gaps are properly spaced.

Incidentally, an incomparably subtler question is whether any set of positive natural density contains arbitrarily long arithmetic progressions. This was conjecture by Erdős and Turán in 1936 and famously proved by Szemerédi almost 40 years later.

• Szemeredi theorem asks for sets with positive natural density. For density $1$ the problem is almost trivial - if a set doesn't contain a $k$-AP for some $k$, it in particular contains no block of $k$ consecutive elements, which implies it has density at most $k/(k+1)$. Jun 7, 2019 at 12:45
• I will add a link to an older post related to arbitrarily long gaps and densities: Density of a set of natural numbers whose differences are not bounded. Jun 7, 2019 at 12:51