12
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 31
    $\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, 2019 at 21:33
  • 1
    $\begingroup$ So sets that contradict this exist? Excellent! Thank you. :) $\endgroup$
    – MCS
    Jun 6, 2019 at 21:35
  • 9
    $\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, 2019 at 22:49
  • 8
    $\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, 2019 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, 2019 at 18:45

4 Answers 4

Reset to default
14
$\begingroup$

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

Improve this answer
$\endgroup$
22
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 7
    $\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, 2019 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, 2019 at 12:51
  • 1
    $\begingroup$ @Wojowu: absolutely - my bad; I have edited the answer. $\endgroup$
    – Seva
    Jun 7, 2019 at 12:58
  • 2
    $\begingroup$ @Wojowu Doesn't Szemeredi's theorem just require positve upper density? $\endgroup$
    – bof
    Jun 7, 2019 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, 2019 at 19:07
21
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 8
    $\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$
    – user44143
    Jun 7, 2019 at 19:04
2
$\begingroup$

The set $$S:=\mathbb{N}_0\backslash\{a^2+b^3, a,b\in\mathbb{N}_0\}$$ has natural density $1$. In fact, this set has at least $X-O(X^{5/6})$ elements up to $X$.

However, this set has no infinite arithmetic progressions, which can be proved by using the Chevalley-Warning theorem.

Another set is: $$S:=\mathbb{N}_0\backslash\{a^2b^3+c^2d^3, a,b,c,d\in\mathbb{N}_0\}$$. In fact, this set has $X-(X\cdot\log(x)^{1-2^{1/3}+o(1)})$ elements up to $X$. See https://www.google.com/url?sa=t&source=web&rct=j&url=https://academic.oup.com/jlms/article-abstract/71/1/69/932674&ved=2ahUKEwj6wsXU6_v9AhUI2KQKHYWaAUQQFnoECAgQAQ&usg=AOvVaw1pqzWVcHEyLDiHfvTUQ96n for more details.

Improve this answer
$\endgroup$

Your Answer

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

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