Suppose the largest gap is D>1 and at least two of the gaps 1,2,...,D appear infinitely many times. I think the answer is NO. But I find it difficult to formulate a necessary and sufficient condition for the sequence to have an infinitely long arithmetic progression. A related question is about the existence of finite arithmetic progressions of any given length k and the answer is YES.
5
-
2$\begingroup$ Do you mean arbitrarily long arithmetic progressions or do you mean such a set must include all terms of the form $a + kd$ for some $a,d$ and $k \in \mathbb{N}$? $\endgroup$– Stanley Yao XiaoCommented Nov 9, 2022 at 22:01
-
$\begingroup$ @StanleyYaoXiao I mean the second, the infinite set {a+kd: k \in N}. The finite arithmetic progression version has been addressed in the linked question. $\endgroup$– Kai WangCommented Nov 10, 2022 at 3:13
-
1$\begingroup$ I think it suffices to take a Sturmian word and interpret its symbols as gaps of lengths 1 and 2... $\endgroup$– Ilya BogdanovCommented Nov 10, 2022 at 9:49
-
4$\begingroup$ The obvious random construction will almost surely produce a counterexample. Baire category argument also works. $\endgroup$– Terry TaoCommented Nov 10, 2022 at 12:27
-
1$\begingroup$ Doesn't this simple idea work? Enumerate the positive increasing arithmetic sequences (all initial values and step sizes) and at the nth step, select a term of the nth sequence; the first term that's more than 1 greater than the previous selected term. So, no consecutive numbers and intersects every infinite arithmetic sequence. The complement has gaps of size 1 and fails to contain any infinite arithmetic sequence. $\endgroup$– Zach TeitlerCommented Apr 11, 2023 at 0:20
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
It is well known and easy to see (as in the old math.se question An example showing that van der Waerden's theorem is not true for infinite arithmetic progressions) that $\mathbb N$ can be partitioned into two sets $A$ and $B$ neither of which contains an infinite arithmetic progression.
Plainly, for such $A$ and $B$, the set $$\{2n:n\in A\}\cup\{2n+1:n\in B\}$$ has maximum gap $D=3$ and contains no infinite arithmetic progression.
$\begingroup$
$\endgroup$
4
Here is an example of a set $S$ where the maximal gap is $D=2$ and which even is dense in the sense that $$\forall \epsilon>0:\exists N_\epsilon>1: \forall N\geq N_\epsilon\wedge k>0 : \frac{\#([k+1,k+N]\cap S)}{ N}>1-\epsilon.,$$ but which contains no infinite arithmetic progression $\{a\,m +b: m\geq m_0\}.$
Denote by $\pi_a$ the $a$-th prime, and by $T(p,a)$ the numbers recursively defined by $$T(0,a)=\pi_a,~~T(p+1,a)~=~2^{T(p,a)}.$$ This construction ensures that for $(p_1,a_1)\neq(p_2,a_2)$, one has $T(p_1,a_1)\neq T(p_2,a_2)$.
For $p\geq1$ and $a>1$, there is exactly one $c(p,a)\in [T(p,a),T(p,a)+a-1]$ with $c(p,a) \equiv p \mod a$, and these intervals are pairwise separated such that $|c(p_1,a_1)-c(p_2,a_2)|>1$ for $(p_1,a_1)\neq(p_2,a_2)$. Choosing $$S~=~\mathbb{N} \backslash \{c(p,a): p\geq 1,a>1\},$$ therefore has maximal gap $D=2$ and because each arithmetic progression $\{a\,m +b: m\geq m_0\}$ contains infinitely many $c(p,a)$, the set $S$ contains no arithmetic progression. $S$ is dense in the above sense because $$\#([k+1,k+N]\cap S) \geq N-\log_2 N.$$
-
$\begingroup$ Per the statement $|c(p_1,a_1)-c(p_2,a_2)|>1$: what if we have a Mersenne prime and the corresponding adjacent power of two? (Perhaps we are only considering odd $\pi_a$?) $\endgroup$ Commented Dec 11, 2022 at 13:29
-
$\begingroup$ @Bill Bradley: $a>1$ implies $\pi_a$ odd. $\endgroup$ Commented Dec 11, 2022 at 19:09
-
2$\begingroup$ Can't you just enumerate the infinite arithmetic progressions, construct a very rapidly increasing sequence of numbers that meets all of them, and take the complement? $\endgroup$– bofCommented Apr 11, 2023 at 5:25
-
$\begingroup$ @bof: This is exactly what $c(p,a)$ is supposed to achieve :) $\endgroup$ Commented Apr 12, 2023 at 20:45