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.

  • 26
    $\begingroup$ Enumerate all the arithmetic progressions as $A_n$. Now remove from $\mathbb N$ the $2^n$-th element of $A_n$ for each $n$. $\endgroup$ – Wojowu Jun 6 at 21:33
  • 1
    $\begingroup$ So sets that contradict this exist? Excellent! Thank you. :) $\endgroup$ – MCS Jun 6 at 21:35
  • 8
    $\begingroup$ 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. $\endgroup$ – Henry Cohn Jun 6 at 22:49
  • 7
    $\begingroup$ 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. $\endgroup$ – Jan-Christoph Schlage-Puchta Jun 7 at 12:35
  • $\begingroup$ 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. $\endgroup$ – Benjamin Dickman Jun 9 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.

  • 6
    $\begingroup$ 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. $\endgroup$ – Matt F. Jun 7 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.

  • 5
    $\begingroup$ 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)$. $\endgroup$ – Wojowu Jun 7 at 12:45
  • 1
    $\begingroup$ 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. $\endgroup$ – Martin Sleziak Jun 7 at 12:51
  • 1
    $\begingroup$ @Wojowu: absolutely - my bad; I have edited the answer. $\endgroup$ – Seva Jun 7 at 12:58
  • 2
    $\begingroup$ @Wojowu Doesn't Szemeredi's theorem just require positve upper density? $\endgroup$ – bof Jun 7 at 15:46
  • 1
    $\begingroup$ @GH from MO: Thanks for editing (which I take as an extra hint to what you wrote on your profile page)... $\endgroup$ – Seva Jun 13 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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