0
$\begingroup$

This question was partly inspired by my previous one, here: A strengthening of the Green-Tao theorem. As in that question, I will restate the definition of a maximal arithmetic progression. Let $k$ be an integer greater than or equal to $2$. Given a subset $S$ of the positive integers, I define an arithmetic progression in $S$ of length $k$ to be maximal if it can't be extended to one of length $k+1$ or higher while still staying in the set $S$. For some counterexamples, if $S$ is the set of prime numbers, then the arithmetic progression $(5,7)$ is not maximal, because it can be extended to $(3,5,7)$, and neither is $(5,11,17)$, because it can be extended to $(5,11,17,23,29)$.

Now, for the question proper. Does there exist an infinite subset $S$ of the positive integers whose complement in the positive integers is also infinite, such that $S$ has no infinite arithmetic progressions, but has arbitrarily large arithmetic progressions, and also, there exists at least one $k \geq 2$ such that $S$ does not have a maximal arithmetic progression of length $k$? In fact, is there an example where for every $k \geq 2$, $S$ does not have a maximal arithmetic progression of length $k$? From the answer to my previous question, I know that the set of primes does not satisfy my question, it satisfies all except the last condition.

$\endgroup$

2 Answers 2

1
$\begingroup$

Does there exist an infinite subset $S$ of the positive integers whose complement in the positive integers is also infinite, such that $S$ has no infinite arithmetic progressions, but has arbitrarily large arithmetic progressions, and also, there exists at least one $k\geq2$ such that $S$ does not have a maximal arithmetic progression of length $k$ ?

Consider the following set of positive integers $S= \{1, 2, 4, 6, 8, 11, 14, 17, 20,\dots\}$. Constructed by the following pseudocode when END = $\infty$:

S = []
i = 0 # iteration
j = 1 # step
n=1 # actual number
for (i=0; i<END, i++){
    for (k = 0; k<j; k++){
        S.append(n)
        n += j
    }
    j++
}

Essentially we're picking a number and we're adding an arithmetic progression of lenght 1 and step 1. Then we add the numbers to create a progression of step 2 and lenght 2 and so on.

Thus we have arbitrary long arithmetic progressions but we don't have an infinite one, as all of them will be of a fixed amount. Finally, the complement of S in the positive integers is obviously infinite, as $\forall x \in S, x>2$ we have $x+1 \notin S$, and so if S is infinite, his complement must be also infinite.

By construction, S has one maximal arithmetic progression of every length possible, thus, if we eliminate the terms correspondent to the specified k we search we have constructed an example of the set you searched.

In fact, is there an example where for every $k\geq2$ , $S$ does not have a maximal arithmetic progression of length $k$?

To awnser this second part we will follow a similar argument. Consider now $S=\{1, 2, 4, 5, 10, 11, ...\}$. We have constructed this by using the following pseudocode:

n = 1
list = []
for (i=0; i<END; i++) {
   list.append(n)
   n++
   list.append(n)
   n = n*2
}

Then $S$ has an infinite amount of 2-maximal arithmetic progressions.

Let's see that there are no bigger arithmetic progressions. If there were to exist a 3-arithmetic progression (even if it's not maximal) we would have $x \in S, \exists k \in \mathbb{Z}^+$ such that $x, x+k, x+2k \in S$.

For construction, $k$ cannot be 1, then let $k>1$. If $x\in S$ then $x+k \notin S$ if $k<x$ as the next number in $S$ bigger than $x+1$ is at least $2x$ (it may be $2(x+1)$). Then for us to have $x, x+k, x+2k \in S$, $k$ must satisfy $k\geq x, k\geq x+k$. Particularly, we'd need $k \geq x+k \implies 0 \geq x$ which is a contradiction.

Therefore, have no such thing as a 3-arithmetic progression, as we tried to prove.

New contributor
Victor Ruiz is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
1
$\begingroup$

The last question has a negative answer. If $S$ contains arbitrarily large arithmetic progressions, note $(s_1,\dots,s_n)$ the first one with $n\ge 2$.

Assume $S$ has no maximal arithmetic progression. Then this progression can be extended on the right (by minimality condition). Now we deduce by induction that this progression can be extended indefinitely. So $S$ contains at least one infinite arithmetic progression.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.