# Avoiding Monotone Arithmetic Progressions in Permutations of Integers

Sarosh Adenwalla

###### Abstract

A permutation of the integers avoiding monotone arithmetic progressions of
length $6$ was constructed in (Geneson, 2018). We improve on this by
constructing a permutation of the integers avoiding monotone arithmetic
progressions of length $5$. We also construct permutations to show that
$\beta_{\mathbb{Z^{+}}}(4)=1$, $\beta_{\mathbb{Z}}(3)\geq\frac{3}{10}$,
$\beta_{\mathbb{Z}}(4)\geq\frac{2}{3}$ and $\alpha_{\mathbb{Z}}(4)=1$. In
(Davis et al, 1977) they constructed a doubly infinite permutation of the
positive integers that avoids monotone arithmetic progressions of length $4$.
We construct a doubly infinite permutation of the integers avoiding monotone
arithmetic progressions of length $5$. A permutation of the positive integers
that avoided monotone arithmetic progressions of length $4$ with odd common
difference was constructed in (LeSaulnier and Vijay, 2011). We generalise this
result and show that for each $k\geq 1$, there exists a permutation of the
positive integers that avoids monotone arithmetic progressions of length $4$
with common difference not divisible by $2^{k}$. In addition, we specify the
structure of permutations of $[1,n]$ that avoid length $3$ monotone arithmetic
progressions mod $n$ as defined in (Davis et al, 1977) and provide a
multiplicative result on permutations that avoid length $k$ monotone
arithmetic progressions mod $n$.

##  1 Introduction

A permutation, $a_{1},a_{2},a_{3}\ldots$, avoids monotone arithmetic
progressions of length $k$ if there does not exist an increasing or decreasing
subsequence of the permutation that forms a $k$ term arithmetic progression.
We will refer to monotone arithmetic progressions of length $k$ as $k$-APs.
Clearly, if a permutation avoids $k$-APs then it avoids $h$-APs for any $h>k$.
In [4], Davis et al proved that the positive integers cannot be permuted to
avoid $3$-APs and can be permuted to avoid $5$-APs and in [1], Geneson proved
that the integers can be permuted to avoid $6$-APs. We prove that the integers
can be permuted to avoid $5$-APs. These results leave open the questions of
whether there exist permutations avoiding $4$-APs in the integers and the
positive integers. Note that if there exists a permutation, $P$, of the
integers avoiding $k$-APs, then the subsequence of positive integers in $P$
forms a permutation of the positive integers avoiding $k$-APs. Therefore if
there does not exist a permutation of the positive integers avoiding $k$-APs,
then there does not exist a permutation of the integers avoiding $k$-APs. We
can work towards answering these open questions by considering the largest
subset of the integers (or positive integers) that can be permuted to avoid
$3$-APs or $4$-APs. Let $\alpha_{\mathbb{Z^{+}}}(k)$ be the supremum of
$\limsup_{n\rightarrow\infty}\frac{|S\cap[1,n]|}{n}$ and
$\beta_{\mathbb{Z^{+}}}(k)$ be the supremum of
$\liminf_{n\rightarrow\infty}\frac{|S\cap[1,n]|}{n}$, over all sets of
positive integers $S$ that can be permuted to avoid $k$-APs. These are the
upper and lower density functions for the positive integers, as defined in
[5]. We can define similar functions for the integers, whereby
$\alpha_{\mathbb{Z}}(k)$ is the supremum of
$\limsup_{n\rightarrow\infty}\frac{|R\cap[-n,n]|}{2n}$ and
$\beta_{\mathbb{Z}}(k)$ is the supremum of
$\liminf_{n\rightarrow\infty}\frac{|R\cap[-n,n]|}{2n}$ over all sets of
integers $R$ that can be permuted to avoid $k$-APs. These are the upper and
lower density functions for the integers which were first defined in [1]. In
[5] it was shown that $\alpha_{\mathbb{Z^{+}}}(4)=1$,
$\alpha_{\mathbb{Z^{+}}}(3)\geq\frac{1}{2}$ and
$\beta_{\mathbb{Z^{+}}}(3)\geq\frac{1}{4}$. These are currently the best known
bounds and the authors of [5] conjectured that the latter two bounds are
equalities.

In [1], it was proved that $\alpha_{\mathbb{Z}}(k)=\beta_{\mathbb{Z}}(k)=1$
for all $k\geq 6$. Our result that the integers can be permuted to avoid
$5$-APs implies that $\alpha_{\mathbb{Z}}(5)=\beta_{\mathbb{Z}}(5)=1$. It was
also shown in [1] that
$\alpha_{\mathbb{Z}}(3)\geq\frac{1}{2},\beta_{\mathbb{Z}}(3)\geq\frac{1}{6}$
and $\beta_{\mathbb{Z^{+}}}(4)\geq\frac{1}{2}$. We improve on the latter
results to show that $\beta_{\mathbb{Z}}(3)\geq\frac{3}{10}$ and
$\beta_{\mathbb{Z^{+}}}(4)=1$. We use the result that
$\alpha_{\mathbb{Z}}(3)\geq\frac{1}{2}$ to prove that if
$\alpha_{\mathbb{Z^{+}}}(3)=\frac{1}{2}$ as conjectured, then
$\alpha_{\mathbb{Z}}(3)=\frac{1}{2}$. Further, we show that
$\alpha_{\mathbb{Z}}(4)=1$ and $\beta_{\mathbb{Z}}(4)\geq\frac{2}{3}$. All of
these results have been proved by explicitly constructing permutations that
avoid $k$-APs and attain those densities. There has not been any result found
or technique developed towards upper bounding these values strictly below $1$.

Another way of moving towards answering whether $4$-AP free permutations of
the positive integers exist is to consider permutations with restrictions on
the common difference of any $4$-APs that appear. In [5], it was shown that
the positive integers can be permuted to avoid $4$-APs with odd common
difference (all $4$-APs have common difference divisible by $2$). We
generalise this to show that, for any $k\geq 1$, the positive integers can be
permuted to avoid $4$-APs with common difference not divisible by $2^{k}$
(i.e. all $4$-APs in the permutation have common difference divisible by
$2^{k}$).

In [4], it was shown that the positive integers can be partitioned into $3$
sequences that each avoid $3$-APs. We show that the integers can be
partitioned into $3$ sequences that each avoid $3$-APs. It was also shown in
[4] that the positive integers can be arranged into a doubly infinite
permutation, $\ldots a_{-2},a_{-1},a_{0},a_{1},a_{2}\ldots,$ that avoids
$4$-APs but cannot be arranged in a doubly infinite permutation that avoids
$3$-APs. Note that this implies that the integers cannot be arranged in a
doubly infinite permutation that avoids $3$-APs. We will show that there
exists a doubly infinite permutation of the integers that avoids $5$-APs. The
question of whether there exists a doubly infinite permutation of the integers
avoiding $4$-APs is still open.

Let $a_{1},a_{2},\ldots,a_{n}$ be a permutation of $[1,n]$. Then a subsequence
of this permutation, $a_{i_{1}},a_{i_{2}},\ldots,a_{i_{k}}$, is a $k$-AP mod
$n$ if, for $d$ not equal to $0$ and some integer $a$,

$a_{i_{t}}\equiv a+td\mod n$

for $1\leq t\leq k$. For example $4,2,5,1,3$ contains $3$-APs mod $5$ such as
$4,2,5$ and $4,5,1$. Let $n$ be called $k$-permissible if [1,n] can be
permuted to avoid $k$-APs mod $n$. In [3], Nathanson shows that the $n$ is
$3$-permissible if and only if $n$ is a power of 2. A different proof of this
is given in [2]. It is proven in [4] and [2] that for all $n$, $n$ is
$5$-permissible, which means all $n$ are $k$-permissible for all $k\geq 5$. It
is not known which $n$ are $4$-permissible. We show that $n$ is
$k$-permissible if and only if all the prime factors of $k$ are
$k$-permissible, improving on a result in [3]. This allows us to prove that
all $n$ that have no prime factors greater than $13$ are $4$-permissible. We
also show that any permutation of [1,$2^{k}$] avoiding $3$-APs mod $2^{k}$
must obey a certain structure. From this we determine that there are
$2^{2^{k}-1}$ such permutations which was proven in [6].

The way we improve the results in these areas is by using modular arithmetic
in creating these permutations. This is used in [4] where terms are arranged
based on their parity in a doubly infinite permutation and in [5]. Any $k$-AP
with terms that are distinct mod $n$ must form a $k$-AP mod $n$ with distinct
terms. So by grouping integers in a given interval together in the permutation
by their residues mod $2^{k}$ for some $k$ (having been rearranged to avoid
$3$-APs), and ordering those residues in a way that avoids $3$-APs mod $2^{k}$
we can avoid $3$-APs appearing in certain ways in the permutation. This has
been used in Theorems $1$, $3$, $4$ and $5$. Although it is intuitive to think
that constructing these permutations for the integers is more difficult than
constructing them for the positive integers, there is a way of using the
structure of the integers to increase the lower density of a permutation of a
subset of the integers that avoids $3$-APs. We can choose the subset we use by
initially picking an interval of positive integers, $[a,b]$, to be our subset
and then adding $[-d,-c]$ followed by $[e,f]$ and $[-h,-g]$ etc where
$a<b<c<d<e<f<g<h$ are carefully chosen positive integers. In this way, we
alternate between positive intervals and negative intervals, with each
interval of greater length and with integers of greater absolute value than
the last interval. By doing this, the gap between $b$ and $e$ or between $d$
and $g$ can be large enough to avoid $3$-APs while the gap between $b$ and $c$
or $f$ and $g$ can be smaller. Due to this, we can find permutations that
avoid $3$-APs without reducing the lower density as much. This was used in
Theorem $6$.

Declarations of interest: none. This research did not receive any specific
grant from funding agencies in the public, commercial, or not-for-profit
sectors.

##  2 5-AP Free Permutations

We will first construct a permutation of the integers, $P$, that avoids
$5$-APs. We use that any finite subset of the integers can be permuted to
avoid $3$-APs, as proven in [4]. If S is a permutation of a set of integers,
$s_{1},s_{2},s_{3},\ldots,s_{n}$, and $a,b$ are integers, then let $aS+b$ be
$a\times s_{1}+b,a\times s_{2}+b,a\times s_{3}+b,\ldots,a\times s_{n}+b$, so
the relative order of the terms is maintained. Note that $S$ avoids $k$-APs if
and only if $aS+b$ avoids $k$-APs for non zero $a$ as
$s_{i_{1}},s_{i_{2}},\ldots,s_{i_{k}}$ is a $k$-AP if and only if $a\times
s_{i_{1}}+b,a\times s_{i_{2}}+b,\ldots,a\times s_{i_{k}}+b$ is a $k$-AP. Also,
if $T$ is another permutation of some set of integers,
$t_{1},t_{2},t_{3},\ldots,t_{r}$, then let $S,T$ denote the concatenation of
the two permutations,
$s_{1},s_{2},s_{3},\ldots,s_{n},t_{1},t_{2},t_{3},\ldots,t_{r}$. Throughout
the following constructions, our permutations are made up of intervals that
have been permuted to avoid $3$-APs. We call such intervals blocks.

######  Theorem 1.

There exists a permutation of the integers, $P$, that avoids $5$-APs.

###### Proof.

Let $X_{i}$ be a permutation of the integers in
$[-8^{i},-8^{i-1}-1]\cup[8^{i-1},8^{i}-1]$. $P$ will be constructed using
these blocks. Let

$X_{1}=-8,-4,4,-6,2,-2,6,-7,1,-3,5,-5,3,7$
$X_{2n}=8X_{2n-1}+7,8X_{2n-1}+3,8X_{2n-1}+5,8X_{2n-1}+1,8X_{2n-1}+6,8X_{2n-1}+2,8X_{2n-1}+4,8X_{2n-1}$
$X_{2n+1}=8X_{2n},8X_{2n}+4,8X_{2n}+2,8X_{2n}+6,8X_{2n}+1,8X_{2n}+5,8X_{2n}+3,8X_{2n}+7$

Note that the integers in each block are grouped together by their residue
classes mod $8$. In all odd indexed blocks, including $X_{1}$, the order of
the residue classes is $0,4,2,6,1,5,3,7$ and in all even indexed blocks the
order is $7,3,5,1,6,2,4,0$.

Then let $P=0,X_{1},-1,X_{2},X_{3},X_{4},X_{5},\ldots$.

We will assume that $P$ contains a $5$-AP and derive a contradiction. Denote
the terms of this progression as $a_{1},a_{2},a_{3},a_{4},a_{5}$, with common
difference $d$.

First we prove that each $X_{i}$ avoids $3$-APs by induction. Clearly $X_{1}$
avoids $3$-APs by inspection. Assume $X_{k}$ avoids $3$-APs for some $k$. Note
that $X_{k+1}$ is made up of sub-blocks of the form $8X_{k}+a$ for
$a\in\\{0,1,2,3,4,5,6,7\\}$. Then $8X_{k}+a$ avoids $3$-APs for any integer
$a$. So any $3$-AP in $X_{k+1}$ cannot have all terms in one sub-block
$8X_{k}+a$ for some $a\in\\{0,1,2,3,4,5,6,7\\}$. Assume there exists a $3$-AP
in $X_{k+1}$, with terms $b_{1},b_{2},b_{3}$, which we shall prove cannot
exist. As $b_{1},b_{2},b_{3}$ must belong to more than one sub-block of the
form $8X_{k}+a$, the common difference of the terms is not divisible by $8$.
So $b_{1}$ and $b_{2}$ belong to different sub-blocks and $b_{2}$ and $b_{3}$
belong to different sub-blocks. Therefore due to how $X_{k+1}$ is constructed
from sub-blocks of the form $8X_{k}+a$, $b_{1}$ and $b_{3}$ belong to
different sub-blocks as well. So $b_{1},b_{2},b_{3},$ all have different
residues mod $8$ and so $b_{1}$ mod $8$, $b_{2}$ mod $8$, $b_{3}$ mod $8$ form
a $3$-AP mod $8$ with distinct terms. However the order of the sub-blocks (and
therefore the order of the residue classes mod $8$) in $X_{k+1}$ means that
$X_{k+1}$ avoids $3$-APs mod $8$ with distinct terms. This can be seen by
inspecting the permutations $0,4,2,6,1,5,3,7$ and $7,3,5,1,6,2,4,0$, the
orders of the residue classes mod $8$ in the blocks. Therefore there is no
such $b_{1},b_{2},b_{3}$ in $X_{k+1}$. So all $X_{i}$ avoid $3$-APs by
induction.

Case 1 First we will consider the case where $a_{2}$ and $a_{3}$ are in
different blocks. Denote the block $a_{2}$ belongs to as $X_{i}$. Then as
$a_{1}$ appears before $a_{2}$ in $P$, $|a_{1}|,|a_{2}|\leq 8^{i}$ and
$|d|<2\times 8^{i}$. By the triangle inequality, $|a_{3}|=|a_{2}+d|<3\times
8^{i}$. But as $a_{3}$ appears after $a_{2}$ in $P$ and is in a different
block to $a_{2}$, it follows that $a_{3}$ is in $X_{i+1}$. Similarly
$|a_{4}|<5\times 8^{i}$, $|a_{5}|<7\times 8^{i}$ and appear after $a_{3}$ in
$P$. So $a_{4}$ and $a_{5}$ are also in $X_{i+1}$. But then
$a_{3},a_{4},a_{5}$ form a $3$-AP in $X_{i+1}$ which is a contradiction.

Case 2 Now we consider the case when $a_{2}$ and $a_{3}$ are in the same
block, denoted $X_{i}$. As $a_{2}$ and $a_{3}$ are in $X_{i}$, $|a_{2}|<8^{i}$
and $|a_{3}|<8^{i}$ so $|d|<2\times 8^{i}$. By the triangle inequality,
$|a_{4}|<3\times 8^{i}$, and as $X_{i}$ avoids $3$-APs, $a_{4}$ cannot be in
$X_{i}$. Therefore $a_{4}$ is in $X_{i+1}$. As $|a_{5}|<5\times 8^{i}$ and as
$a_{5}$ appears in $P$ after $a_{4}$, it follows that $a_{5}$ is in $X_{i+1}$.
So $a_{2},a_{3},a_{4},a_{5}$ form a $4$-AP with $a_{2},a_{3}$ in $X_{i}$ and
$a_{4},a_{5}$ in $X_{i+1}$. We show that this cannot occur by proving that
there can be no such $4$-AP over consecutive blocks $X_{i}$ and $X_{i+1}$. In
fact this shows that there can be no $4$-AP over consecutive blocks at all as
the only other way there could be is if there were either $3$ consecutive
terms in $X_{i}$ or $3$ consecutive terms in $X_{i+1}$ which cannot happen.
Let $b_{1},b_{2},b_{3},b_{4}$ be a $4$-AP with common difference $d$ and with
$b_{1},b_{2}$ in $X_{i}$ and $b_{3},b_{4}$ in $X_{i+1}$.

If $d$ is not divisible by $4$, then $b_{1},b_{2},b_{3},b_{4}$ are distinct
mod $8$ and as they form a $4$-AP, $b_{1}$ mod $8$, $b_{2}$ mod $8$, $b_{3}$
mod $8$, $b_{4}$ mod $8$ form a $4$-AP mod $8$ with distinct terms. However
the order of the residue classes mod 8 of $X_{i},X_{i+1}$ is either
$7,3,5,1,6,2,4,0,4,2,6,1,4,3,7$ or $0,4,2,6,1,5,3,7,3,5,1,6,2,4,0$ depending
on whether $i$ is even or odd. These sequences do not contain $4$-APs mod $8$
so there is no such $4$-AP with $d$ not divisible by $4$.

If $d\equiv 4$ mod $8$, then $b_{1}\equiv b_{3}$ mod $8$ and $b_{2}\equiv
b_{4}$ mod $8$ while $b_{1}$ is not equivalent to $b_{2}$ mod $8$. So there
exists $x,y\in\\{0,1,2,3,4,5,6,7\\}$ such that $b_{1}\equiv b_{3}\equiv x$ mod
$8$ and $b_{2}\equiv b_{4}\equiv y$ mod $8$. As $b_{1}$ appears in $X_{i}$
before $b_{2}$ then $x$ appears before $y$ in the order of the residue classes
mod $8$ of $X_{i}$. As $b_{3}$ appears in $X_{i+1}$ before $b_{4}$ then $x$
appears before $y$ in the order of the residue classes mod $8$ of $X_{i+1}$.
But by the definition of $X_{i}$ and $X_{i+1}$, if $x$ appears before $y$ in
the order of the residue classes mod $8$ of $X_{i}$ then $y$ appears before
$x$ in the order of the residue classes mod $8$ of $X_{i+1}$. Therefore no
such $4$-AP with $d\equiv 4$ mod $8$ exists.

Finally consider the case where $d\equiv 0$ mod $8$. Proceed by induction on
$i$. First note that there is no $4$-AP with $b_{1},b_{2}$ in $X_{1}$,
$b_{3},b_{4}$ in $X_{2}$ and $d\equiv 0$ mod $8$. This can be seen as the only
terms in $X_{1}$ with a difference divisible by $8$ are

$\\{-4,4\\},\\{-6,2\\},\\{-2,6\\},\\{-7,1\\},\\{-3,5\\},\\{-5,3\\}$

So the only possible such progressions are

$\\{-4,4,12,20\\},\\{-6,2,10,18\\},\\{-2,6,14,22\\},\\{-7,1,9,17\\},\\{-3,5,13,21\\},\\{-5,3,11,19\\}$

However $2$ appears before $1$ in $X_{1}$, so $20$ appears before $12$ in
$X_{2}$ and similarly $18$ appears before $10$, $22$ appears before $14$, $17$
appears before $9$, $21$ appears before $13$ and $19$ appears before $11$. So
there is no $4$-AP with the first two terms in $X_{1}$ and the last two terms
in $X_{2}$ with common difference $d\equiv 0$ mod $8$. Assume there is no
$4$-AP with the first two terms in $X_{k-1}$ and the last two terms in $X_{k}$
with common difference $d\equiv 0$ mod $8$. Now consider a $4$-AP,
$b_{1},b_{2},b_{3},b_{4}$, with $b_{1},b_{2},$ in $X_{k}$ and $b_{3},b_{4}$ in
$X_{k+1}$ for $d\equiv 0$ mod $8$ and $k>1$. Then there exists
$w\in\\{0,1,2,3,4,5,6,7\\}$ such that $b_{1}\equiv b_{2}\equiv b_{3}\equiv
b_{4}\equiv w$ mod $8$ and $b_{1},b_{2}$ are in the sub-block $8X_{k-1}+w$ of
$X_{k}$, $b_{3},b_{4}$ are in the sub-block $8X_{k}+w$ of $X_{k+1}$. Then let
$c_{1}=b_{1}-w,c_{2}=b_{2}-w,c_{3}=b_{3}-w,c_{4}=b_{4}-w$. So $c_{j}$ is the
multiple of $8$ that is less than or equal to $b_{j}$ for $j\in\\{1,2,3,4\\}$.
As the smallest integer in $[8^{k-1},8^{k}-1]$ is a multiple of $8$ when
$k>1$, and the smallest integer of $[-8^{k},-8^{k-1}-1]$ is a multiple of 8,
$c_{j}$ is in the same block as $b_{j}$. So $c_{1},c_{2}$ are in $X_{k}$ and
$c_{3},c_{4}$ are in $X_{k+1}$. As $c_{1},c_{2},c_{3},c_{4}$ are multiples of
$8$, $c_{1},c_{2}$ are in the sub-block $8X_{k-1}$ and $c_{3},c_{4}$ are in
the sub-block $8X_{k}$. As $b_{1}$ appears before $b_{2}$ in $8X_{k-1}+w$,
$b_{1}-w=c_{1}$ appears before $b_{2}-w=c_{2}$ in $8X_{k-1}$. As $b_{3}$
appears before $b_{4}$ in $8X_{k}+w$, $b_{3}-w=c_{3}$ appears before
$b_{4}-w=c_{4}$ in $8X_{k}$. Note that $8X_{k-1}$ is in $X_{k}$ and $8X_{k}$
is in $X_{k+1}$ so $8X_{k-1}$ appears before $8X_{k}$ in $P$. So as
$b_{1},b_{2},b_{3},b_{4}$ is a $4$-AP in $P$,
$b_{1}-w,b_{2}-w,b_{3}-w,b_{4}-w$ is a $4$-AP in $P$ with the same common
difference $d$. Therefore $c_{1},c_{2},c_{3},c_{4}$ is a $4$-AP in $P$ with
common difference $d$ with all terms and $d$ being divisible by $8$. As
$c_{1}$ appears in the sub-block $8X_{k-1}$ before $c_{2}$ and $c_{3}$ appears
in the sub-block $8X_{k}$ before $c_{4}$, $\frac{c_{1}}{8}$ appears before
$\frac{c_{2}}{8}$ in $X_{k-1}$ and $\frac{c_{3}}{8}$ appears before
$\frac{c_{4}}{8}$ in $X_{k}$. So
$\frac{c_{1}}{8},\frac{c_{2}}{8},\frac{c_{3}}{8},\frac{c_{4}}{8}$ is a $4$-AP
in $X_{k-1}$ and $X_{k}$. Denote the common difference of this progression by
$d^{\prime}$ and note that $d^{\prime}=\frac{d}{8}$. We have shown that if the
common difference is not divisible by $8$, the progression cannot exist. So
$d^{\prime}\equiv 0$ mod $8$. However this contradicts our inductive
assumption. So no such $4$-AP with common difference divisible by $8$ exists
with terms in $X_{k}$ and $X_{k+1}$. This completes the induction so no $4$-AP
with common difference divisible by $8$ appears in $P$ with terms in
consecutive blocks $X_{i},X_{i+1}$. So no $4$-AP with terms in consecutive
blocks appears in $P$.

Case 3 The final case is when $a_{2}$ or $a_{3}$ are equal to $0$ or $-1$.
$a_{2}$ and $a_{3}$ cannot be $0$ as $0$ is the first term of $P$ and $a_{1}$
must appear in $P$ before $a_{2}$ and $a_{3}$. If $a_{2}$ is $-1$ then $a_{1}$
appears before $a_{2}$ in $P$ so $-8\leq a_{1}\leq 7$ so $|d|\leq 8$. So
$|a_{3}|\leq 9$, $|a_{4}|\leq 17$ and $|a_{5}|\leq 25$. As $a_{3},a_{4},a_{5}$
appear in $P$ after $-1$, they are all in $X_{2}$. But they would form a
$3$-AP which is a contradiction as $X_{2}$ avoids these. So $a_{2}$ cannot be
$-1$. If $a_{3}$ is $-1$ then $a_{1},a_{2},a_{3}$ is a $3$-AP contained in
$0,X_{1},-1$. As $a_{3}$ is odd, $a_{1}$ must be odd. By considering how
$X_{1}$ is ordered, $a_{2}$ must be odd. So $d$ must be even which implies
that the difference between $a_{1}$ and $a_{3}=-1$ is divisible by $4$. The
only options for $a_{1}$ are then $-5,3$ and $7$. So $a_{2}$ must either be
$-3,1$ or $3$. However $-3$ appears in $P$ before $-5$, $1$ appears before $3$
and $3$ appears before $7$. This means $a_{3}$ cannot be $-1$.

So $P$ avoids $5$-APs.∎

This implies that $\alpha_{\mathbb{Z}}(5)=\beta_{\mathbb{Z}}(5)=1$. We now
prove the same for doubly infinite permutations. Theorem $2$ follows easily
from Theorem $1$ if we take $P$ to be the permutation defined above and
consider a doubly infinite permutation $S$ where $2P+1$ is the permutation in
$S$ that continues to the left and $2P$ is the permutation in $S$ that
continues to the right. Below we provide an alternative permutation.

######  Theorem 2.

There exists a doubly infinite permutation of the integers, T, that avoids
$5$-APs.

###### Proof.

Consider the doubly infinite permutation

$T=\dots,Z_{2i},Z_{2i-2},\ldots,Z_{6},Z_{4},Z_{2},0,Z_{1},-1,Z_{3},Z_{5},\ldots,Z_{2i-1},Z_{2i+1},\ldots$

where $Z_{i}$ is a permutation of the integers in
$[-8^{i},-8^{i-1}-1]\cup[8^{i-1},8^{i}-1]$ that avoids $3$-APs. Assume $T$
contains a $5$-AP $a_{1},a_{2},a_{3},a_{4},a_{5}$ with common difference $d$.
Denote the block $a_{2}$ belongs to as $Z_{j}$.

Case 1 Let $a_{3}$ be in $Z_{i}$ with $i\geq j$ and $i$ odd. Then
$|a_{2}|,|a_{3}|\leq 8^{i}$ and $|d|<2\times 8^{i}$. $a_{4},a_{5}$ cannot both
be in $Z_{i}$ as $a_{3},a_{4},a_{5}$ would form a $3$-AP. So $a_{5}$ must be
in a block that appears after $Z_{i}$ and therefore, as $i$ is odd,
$|a_{5}|\geq 8^{i+1}$. But as $|a_{5}|=|a_{3}+2d|<5\times 8^{i}$, we reach a
contradiction. So $a_{3}$ is not in $Z_{i}$ for odd $i$ with $i\geq j$.

Case 2 Let $a_{3}$ be in $Z_{i}$ for $i<j$. As $a_{3}$ appears in $T$ after
$a_{2}$, $j$ is even. Assume $a_{2}$ is negative. The cases where $a_{2}$ is
positive are similar.

Case 2a Let $a_{3}\in Z_{i}$, $a_{3}<0$, for $i<j-1$. So
$a_{2}\in[-8^{j},-8^{j-1}-1]$ and $a_{3}\in[-8^{i},-8^{i-1}-1]$. Therefore
$8^{j-1}-8^{i}<d<8^{j}-8^{i-1}$ so $8^{j-1}-2\times 8^{i}<a_{4}<8^{j}-2\times
8^{i-1}$. $a_{4}$ cannot be in $Z_{j}$ as $a_{2}$ is in $Z_{j}$ and $a_{3}\in
Z_{i}$ appears between $a_{2}$ and $a_{4}$. Therefore $8^{j-1}-2\times
8^{i}<a_{4}<8^{j-1}$ which means $a_{4}$ is in $Z_{j-1}$. So
$8^{j-1}-8^{i}<\frac{a_{4}-a_{2}}{2}=d<\frac{8^{j}+8^{j-1}}{2}$ which means
$8^{j-1}<2\times 8^{j-1}-3\times
8^{i}<a_{5}<\frac{1}{2}8^{j}+\frac{3}{2}8^{j-1}=\frac{11}{2}8^{j-1}$. So
$a_{5}\in Z_{j}$ which is not possible as $a_{2}$ is in $Z_{j}$ and $a_{3}$ is
not.

Case 2b Let $a_{3}\in Z_{j-1}$, $a_{3}<0$ so $a_{2}\in[-8^{j},-8^{j-1}-1]$ and
$a_{3}\in[-8^{j-1},-8^{j-2}-1]$ which means $0<d<8^{j}-8^{j-2}$. Note that
$j-1$ is odd and as $a_{3},a_{4},a_{5}$ cannot all be in $Z_{j-1}$, $a_{5}$
appears after $Z_{j-1}$ in an odd indexed block. So $a_{5}\geq 8^{j}$ or
$a_{5}\leq-8^{j}$. However as $a_{5}>a_{2}$, $a_{5}\geq 8^{j}$. Therefore
$\frac{8^{j}+8^{j-1}}{3}<\frac{a_{5}-a_{2}}{3}=d<8^{j}-8^{j-2}$. So $2\times
8^{j-1}=\frac{-2\times 8^{j-1}+8^{j}}{3}<a_{4}<8^{j}-2\times 8^{j-2}$. This
means $a_{4}$ is in $Z_{j}$ which is not possible as $a_{2}\in Z_{j}$ and
$a_{3}$ is not.

Case 2c Let $a_{3}\in Z_{i}$ for $i<j$ and let $a_{3}>0$. Then
$a_{2}\in[-8^{j},-8^{j-1}-1]$, $a_{3}\in[8^{i-1},8^{i}-1]$ and
$8^{i-1}+8^{j-1}<d$. So $a_{1}\in Z_{k}$ for $k\geq j$, $k$ even, as $a_{1}$
appears before $a_{2}$ in $K$ and $a_{1}\in[-8^{k},-8^{k-1}-1]$ as
$a_{1}<a_{2}$. If $k>j$ then this is the same as Cases $2a$ and $2b$ but
instead of considering $a_{2}$ and $a_{3}$ we consider $a_{1}$ and $a_{2}$.

If $k=j$ then $d<8^{j}-8^{j-1}=7\times 8^{j-1}$. Therefore $8^{i-1}\leq
a_{3}<6\times 8^{j-1}$. It follows that $8^{j-1}+2\times 8^{i-1}<a_{4}<6\times
8^{j-1}+7\times 8^{j-1}=13\times 8^{j-1}$. $a_{4}$ cannot be in $Z_{j}$
because $a_{2}\in Z_{j}$ and $a_{3}$ is not, so $8^{j}\leq a_{4}<13\times
8^{j-1}$. Therefore
$\frac{9}{2}8^{j-1}=\frac{8^{j}+8^{j-1}}{2}<\frac{a_{4}-a_{2}}{2}=d<7\times
8^{j-1}$. This means $8^{j-1}=8^{j}-7\times 8^{j-1}<a_{4}-d=a_{3}<6\times
8^{j-1}$ so $a_{3}$ is in $Z_{j}$. This cannot happen as $a_{3}\in Z_{i}$ for
$i<j$.

Case 3 Let $j$ be even and $a_{3}\in Z_{j}$. Then $|d|<2\times 8^{j}$. So
$|a_{1}|\leq|a_{2}|+|d|<3\times 8^{j}$. $a_{1}$ cannot be in $Z_{j}$ as
$a_{1},a_{2},a_{3}$ would form a $3$-AP in $Z_{j}$ so as $j$ is even and
$a_{1}$ appears before $a_{2}$, $|a_{1}|\geq 8^{j+1}$. This implies
$8^{j+1}\leq|a_{1}|<3\times 8^{j}$ which is a contradiction.

Case 4 Finally consider the case where one of $a_{2}$ or $a_{3}$ is either $0$
or $-1$. If $a_{2}$ or $a_{3}$ were $0$ then $a_{1},a_{2},a_{3}$ or
$a_{2},a_{3},a_{4}$ would be a $3$-AP in $T$ with $0$ as the middle term. This
would involve $0$ appearing between a term and its additive inverse in $T$. So
the only such $3$-APs in $T$ are $-8^{i},0,8^{i}$ and $8^{i},0,-8^{i}$ as all
other terms belong to the same block as their additive inverse. So the only
possible $5$-APs are $-2\times 8^{i},-8^{i},0,8^{i},2\times 8^{i}$

$2\times 8^{i},8^{i},0,-8^{i},-2\times 8^{i}$

$8^{i},0,-8^{i},-2\times 8^{i},-3\times 8^{i}$

$-3\times 8^{i},-2\times 8^{i},-8^{i},0,8^{i}$

$3\times 8^{i},2\times 8^{i},8^{i},0,-8^{i}$

$-8^{i},0,8^{i},2\times 8^{i},3\times 8^{i}$

However $8^{i}$ and $-2\times 8^{i}$ belong to the same block so $0$ does not
appear between them. Therefore the first four $5$-APs do not occur in $T$.
$8^{i},2\times 8^{i},3\times 8^{i}$ belong to $Z_{i+1}$ which avoids $3$-APs
and therefore the fifth and sixth $5$-APs do not occur in $T$. So neither
$a_{2}$ or $a_{3}$ can be $0$.

Similarly if $a_{2}$ or $a_{3}$ were $-1$, then $-1$ would be the middle term
of a $3$-AP. The only such progressions are $-8^{i}-1,-1,8^{i}-1$ and
$8^{i}-1,-1,-8^{i}-1$ as all other terms, $r$, belong to the same block as
$-r-2$. So the only possible $5$-APs are
$2\times 8^{i}-1,8^{i}-1,-1,-8^{i}-1,-2\times 8^{i}-1$

$-2\times 8^{i}-1,-8^{i}-1,-1,8^{i}-1,2\times 8^{i}-1$

$-8^{i}-1,-1,8^{i}-1,2\times 8^{i}-1,3\times 8^{i}-1$

$3\times 8^{i}-1,2\times 8^{i}-1,8^{i}-1,-1,-8^{i}-1$

$-3\times 8^{i}-1,-2\times 8^{i}-1,-8^{i}-1,-1,8^{i}-1$

$8^{i}-1,-1,-8^{i}-1,-2\times 8^{i}-1,-3\times 8^{i}-1$

However $-8^{i}-1$ and $2\times 8^{i}-1$ belong to the same block so $-1$ does
not appear in $T$ between them. So the first four $5$-APs do not appear in
$T$. $-8^{i}-1,-2\times 8^{i}-1,-3\times 8^{i}-1$ belong to $Z_{i+1}$ which
avoids $3$-APs and therefore the fifth and sixth $5$-APs do not appear in $T$.

Therefore $T$ avoids $5$-APs. ∎

##  3 Monotone Arithmetic Progressions with restricted common difference

We now prove that for any $k\geq 1$ there is a permutation of the positive
integers that avoids $4$-APs with common difference not divisible by $2^{k}$.
As $n$ is $3$-permissible iff $n$ is a power of $2$, it is equivalent to prove
that for any $3$-permissible $n$, the positive integers can be permuted to so
that all $4$-APs have a common difference divisible by $n$.

######  Theorem 3.

For every $n$ that is $3$-permissible, there exists a permutation of the
positive integers such that all $4$-APs in the permutation have common
difference divisible by $n$.

###### Proof.

Let $X_{i}^{j}$ be a permutation of the positive integers equivalent to $j\mod
n$ in $[3^{i},3^{i+n})$ that avoids $3$-APs (in fact, the proof works with
$[a^{i},a^{i+n})$ for any $a\geq 3$). We will refer to $X_{i}^{j}$ as a block.
Note that a block only contains integers from one residue class mod $n$. Then
let $S=s_{1},s_{2},\ldots,s_{n}$ be a permutation of the integers in $[1,n]$
such that $S$ avoids $3$-APs mod $n$. Now define $r(i)$ as the unique integer
$r\in[1,n]$ such that $r\equiv i\mod n$, noting that $b_{i}=b_{i+n}$. Finally
let $c_{i}=\lceil\frac{i}{n}\rceil n-r(i)+1$. Then let

$R=X_{c_{-n+1}}^{b_{-n+1}},X_{c_{-n+2}}^{b_{-n+2}},\ldots,X_{c_{-n+i}}^{b_{-n+i}},\ldots,X_{c_{-1}}^{b_{-1}},X_{c_{0}}^{b_{0}},X_{c_{1}}^{b_{1}},X_{c_{2}}^{b_{2}},X_{c_{3}}^{b_{3}},\ldots,X_{c_{i}}^{b_{i}},\ldots$

which means

$R=X_{0}^{s_{1}},X_{-1}^{s_{2}},X_{-2}^{s_{3}},\ldots,X_{-i}^{s_{i+1}},\ldots,X_{-n+2}^{s_{n-1}},X_{-n+1}^{s_{n}},X_{n}^{s_{1}},X_{n-1}^{s_{2}},X_{n-2}^{s_{3}},\ldots,X_{n-i}^{s_{i+1}},\ldots,X_{2}^{s_{n-1}},X_{1}^{s_{n}},$
$X_{2n}^{s_{1}},X_{2n-1}^{s_{2}},\ldots,X_{n+2}^{s_{n-1}},X_{n+1}^{s_{n}},X_{3n}^{s_{1}},\ldots,X_{tn}^{s_{1}},X_{tn-1}^{s_{2}},\ldots,X_{tn-i}^{s_{i+1}},\ldots,X_{(t-1)n+2}^{s_{n-1}},X_{(t-1)n+1}^{s_{n}},X_{(t+1)n}^{s_{1}}\ldots$

This is a permutation of all positive integers as for all integers $i\geq 0$,
there are exactly $n$ blocks that each contain all the integers equivalent to
a distinct residue mod $n$ in the interval $[3^{i},3^{i+n})$. We will show
that any $4$-AP in $R$ has common difference $d\equiv 0\mod n$.

To prove this, we assume that $R$ contains a $4$-AP,
$m_{1},m_{2},m_{3},m_{4},$ with common difference $d$ not equivalent to $0\mod
n$ and use this to obtain a contradiction.

Note that if $X_{i}^{s_{l}}$ and $X_{k}^{s_{l^{\prime}}}$ appear in $R$ then
$i\equiv k\mod n$ iff $s_{l}=s_{l^{\prime}}$, and if $X_{i}^{s_{l}}$ appears
in $R$ before $X_{k}^{s_{l}}$ then $i<k$.

So take $d$ not equivalent to $0\mod n$, $m_{2}\equiv s_{l_{1}}\mod n$,
$m_{3}\equiv s_{l_{2}}\mod n$ and $m_{4}\equiv s_{l_{3}}\mod n$. Then let
$m_{2}\in X_{j}^{s_{l_{1}}}$, $m_{3}\in X_{h}^{s_{l_{2}}}$ and $m_{4}\in
X_{k}^{s_{l_{3}}}$. We will show that $l_{1}<l_{2}<l_{3}$.

First assume $d>0$. Letting $(t-1)n<j\leq tn$, we find that
$m_{1},m_{2}<3^{j+n}$ and $d=m_{2}-m_{1}<3^{j+n}$ so $m_{3}<2\times 3^{j+n}$
and $m_{4}<3^{j+n+1}$. Therefore, as $m_{3}$ and $m_{4}$ appear after $m_{2}$
in $R$, $(t-1)n<j,h,k<j+n+1$ so $(t-1)n<j,h,k\leq j+n\leq(t+1)n$. So the order
of the blocks in $R$ is:

$X_{tn}^{s_{1}},X_{tn-1}^{s_{2}},X_{tn-2}^{s_{3}},X_{tn-3}^{s_{4}},\ldots,X_{(t-1)n+2}^{s_{n-1}},X_{(t-1)n+1}^{s_{n}},$
$X_{(t+1)n}^{s_{1}},X_{(t+1)n-1}^{s_{2}},X_{(t+1)n-2}^{s_{3}},\ldots,X_{tn+2}^{s_{n-1}},X_{tn+1}^{s_{n}}$

We break this into two cases.

Case 1 If $(t-1)n<h\leq tn$, then because $m_{3}\in X_{h}^{s_{l_{2}}}$ appears
after $m_{2}\in X_{j}^{s_{l_{1}}}$ in $R$, $h\leq j$. If $h=j$ then $m_{2}$
and $m_{3}$ are in the same block so $m_{3}\equiv m_{2}\mod n$ and $d\equiv
0\mod n$ which is a contradiction. Therefore $(t-1)n<h<j\leq tn$ so
$X_{j}^{s_{l_{1}}}$ and $X_{h}^{s_{l_{2}}}$ are of the form
$X_{tn-i}^{s_{i+1}}$ for $0\leq i\leq n-1$. This means $h<j$ implies
$l_{1}<l_{2}$. Note that $m_{3}<3^{h+n}$ and $d=m_{3}-m_{2}<3^{h+n}$ so
$m_{4}=m_{3}+d<3^{h+n+1}$. Then as $m_{4}\in X_{k}^{s_{l_{3}}}$ we have
$k<h+n+1$, so $(t-1)n<k\leq h+n<(t+1)n$.

Case 1a If $(t-1)n<k\leq tn$, then because $m_{4}\in X_{k}^{s_{l_{3}}}$
appears after $m_{3}\in X_{h}^{s_{l_{2}}}$ in $R$, $k\leq h$. If $k=h$ then
$m_{3}$ and $m_{4}$ are in the same block so $m_{4}\equiv m_{3}\mod n$ and
$d\equiv 0\mod n$ which is a contradiction. Therefore $(t-1)n<k<h<tn$ and so
$l_{2}<l_{3}$.

Case 1b Otherwise $tn<k\leq h+n<(t+1)n$. If $k=h+n$ we have $k\equiv h\mod n$
so $s_{l_{2}}=s_{l_{3}}$. It follows that $m_{4}\equiv m_{3}\mod n$ which
implies $d\equiv 0\mod n$ which is a contradiction. Therefore
$tn<k<h+n<(t+1)n$ and $h+n\equiv h\mod n$ so $l_{2}<l_{3}$.

Case 2 If $tn<h\leq j+n\leq(t+1)n$ then note that if $h=j+n$ it follows that
$s_{l_{1}}=s_{l_{2}}$. So $m_{3}\equiv m_{2}\mod n$ and $d\equiv 0\mod n$
which is a contradiction. Therefore $tn<h<j+n\leq(t+1)n$ and so $l_{1}<l_{2}$.
As $tn<h<(t+1)n$ and $m_{4}\in X_{k}^{s_{l_{3}}}$ appears after $m_{3}\in
X_{h}^{s_{l_{2}}}$ in $R$, it follows that either $tn<k\leq h$ or $k>(t+1)n$.
But $k\leq(t+1)n$ and therefore $tn<k\leq h$. Note that if $k=h$ then
$m_{4}\equiv m_{3}\mod n$ so $d\equiv 0\mod n$ which is a contradiction.
Therefore $tn<k<h<(t+1)n$ so $l_{2}<l_{3}$.

In either case we have that $l_{1}<l_{2}<l_{3}$. As $S$ is a permutation of
$[1,n]$, $s_{v}\equiv s_{w}\mod n$ iff $s_{v}=s_{w}$ iff $v=w$ so
$s_{l_{1}},s_{l_{2}},s_{l_{3}}$ are distinct mod $n$. $S$ avoids $3$-APs mod
$n$ and $l_{1}<l_{2}<l_{3}$, so $s_{l_{1}},s_{l_{2}},s_{l_{3}}$ cannot form a
$3$-AP mod $n$. This implies $m_{2},m_{3},m_{4}$ is not a $3$-AP and so
$m_{1},m_{2},m_{3},m_{4}$ is not a $4$-AP.

Next take $d<0$. Then as $m_{2}\in X_{j}^{s_{l_{1}}}$ and
$m_{3}<m_{2}<3^{j+n}$, $(t-1)n<h<j+n\leq(t+1)n$. Again, we break this into two
cases.

Case 1 If $(t-1)n<h\leq tn$ then because $m_{3}\in X_{h}^{s_{l_{2}}}$ appears
after $m_{2}\in X_{j}^{s_{l_{1}}}$ in $R$, $h\leq j$. If $h=j$ then $m_{2}$
and $m_{3}$ are in the same block so $m_{3}\equiv m_{2}\mod n$ and $d\equiv
0\mod n$ which is a contradiction. Therefore $(t-1)n<h<j\leq tn$ and similarly
to the case $d>0$, this means $l_{1}<l_{2}$. As $m_{4}<m_{3}<3^{h+n}$,
$(t-1)n<k<h+n<(t+1)n$.

Case 1a If $(t-1)n<k\leq tn$, then because $m_{4}\in X_{k}^{s_{l_{3}}}$
appears after $m_{3}\in X_{h}^{s_{l_{2}}}$ in $R$, $k\leq h$. If $k=h$ then
$m_{3}$ and $m_{4}$ are in the same block so $m_{4}\equiv m_{3}\mod n$ and
$d\equiv 0\mod n$ which is a contradiction. Therefore $(t-1)n<k<h<tn$ and so
$l_{2}<l_{3}$.

Case 1b Otherwise $tn<k<h+n<(t+1)n$. As $h+n\equiv h\mod n$, $l_{2}<l_{3}$.

Case 2 If $tn<h<j+n\leq(t+1)n$ then $l_{1}<l_{2}$. As $tn<h<(t+1)n$ and
$m_{4}\in X_{k}^{s_{l_{3}}}$ appears after $m_{3}\in X_{h}^{s_{l_{2}}}$ in
$R$, it follows that either $tn<k\leq h$ or $k>(t+1)n$. But $k\leq(t+1)n$ and
therefore $tn<k\leq h$. Note that if $k=h$ then $m_{4}\equiv m_{3}\mod n$ so
$d\equiv 0\mod n$ which is a contradiction. Therefore $tn<k<h<(t+1)n$ so
$l_{2}<l_{3}$.

In either case we have that $l_{1}<l_{2}<l_{3}$. Similarly to the case $d>0$,
this implies $m_{2},m_{3},m_{4}$ is not a $3$-AP and so
$m_{1},m_{2},m_{3},m_{4}$ is not a $4$-AP.

Therefore there are no $4$-APs in $R$ with common difference not divisible by
$n$. ∎

##  4 Density Bounds

We now prove new density bounds. These improved lower bounds are given by
alternating between blocks with positive and negative terms or by blocks with
different residues mod a power of $2$. Under certain orderings of these
blocks, this increases the lower density by reducing the size of the gaps
required to avoid $3$-APs and $4$-APs. We use the permutations from the
previous section to construct a permutation that avoids $4$-APs.

######  Theorem 4.

$\beta_{\mathbb{Z^{+}}}(4)=1$

###### Proof.

Choose $k\geq 1$ and let $n=2^{k}$. Let $a\geq 3$. Then let $X_{i}^{j}$ be a
permutation of the integers equivalent to $j\mod n$ in the interval
$[a^{i},\frac{a^{i+n}}{2})$ that avoids $3$-APs. Then consider the following
permutation $R^{\prime}$.

$R^{\prime}=X_{c_{-n+1}}^{b_{-n+1}},X_{c_{-n+2}}^{b_{-n+2}},\ldots,X_{c_{-n+i}}^{b_{-n+i}},\ldots,X_{c_{-1}}^{b_{-1}},X_{c_{0}}^{b_{0}},X_{c_{1}}^{b_{1}},X_{c_{2}}^{b_{2}},X_{c_{3}}^{b_{3}},\ldots,X_{c_{i}}^{b_{i}},\ldots$

which means

$R^{\prime}=X_{0}^{s_{1}},X_{-1}^{s_{2}},X_{-2}^{s_{3}},\ldots,X_{-i}^{s_{i+1}},\ldots,X_{-n+2}^{s_{n-1}},X_{-n+1}^{s_{n}},X_{n}^{s_{1}},X_{n-1}^{s_{2}},X_{n-2}^{s_{3}},\ldots,X_{n-i}^{s_{i+1}},\ldots,X_{2}^{s_{n-1}},X_{1}^{s_{n}},$
$X_{2n}^{s_{1}},X_{2n-1}^{s_{2}},\ldots,X_{n+2}^{s_{n-1}},X_{n+1}^{s_{n}},X_{3n}^{s_{1}},\ldots,X_{tn}^{s_{1}},X_{tn-1}^{s_{2}},\ldots,X_{tn-i}^{s_{i+1}},\ldots,X_{(t-1)n+2}^{s_{n-1}},X_{(t-1)n+1}^{s_{n}},X_{(t+1)n}^{s_{1}}\ldots$

This is a permutation of the same form as $R$ from Theorem $3$ but with
integers in intervals of the form $[\frac{a^{i+n}}{2},a^{i+n})$ removed. For
any integers $x,y$ in $R^{\prime}$, if $x$ appears before $y$ in $R^{\prime}$
then $x$ appears before $y$ in the permutation $R$ from Theorem $3$. So as $R$
avoids $4$-APs with common difference not divisible by $n$, $R^{\prime}$
avoids such $4$-APs as well. Assume $R^{\prime}$ contains a $4$-AP with common
difference, $d$, which must be divisible by $n$. Then denote this $4$-AP by
$m_{1},m_{2},m_{3},m_{4}$ and let the block $m_{2}$ belongs to be $X_{i}^{j}$
so $m_{2}<\frac{a^{i+n}}{2}$. Therefore
$d=m_{2}-m_{1}<m_{2}<\frac{a^{i+n}}{2}$ and so $m_{3}=m_{2}+d<a^{i+n}$. As
$d\equiv 0\mod n$, this means $m_{1}\equiv m_{2}\equiv m_{3}\equiv m_{4}\equiv
j\mod n$. As $m_{3}$ appears in $R^{\prime}$ after $m_{2}$, $m_{3}$ is either
in $X_{i}^{j}$ or $m_{3}$ is in $X_{f}^{j}$ for $f\geq i+n$. If $m_{3}$ is in
$X_{f}^{j}$ for $f\geq i+n$, then $m_{3}\geq a^{i+n}$ which is a
contradiction. So $m_{3}$ is in $X_{i}^{j}$. Similarly,
$m_{4}=m_{3}+d<a^{i+n}$ and $m_{4}$ must be in $X_{i}^{j}$. However
$m_{2},m_{3},m_{4}$ forms a $3$-AP in $X_{i}^{j}$ which is a contradiction as
$X_{i}^{j}$ avoids $3$-APs. Therefore there is no $4$-AP in $R^{\prime}$.

$\frac{|R^{\prime}\cap[1,a^{N}]|}{a^{N}}=\frac{a^{n}-2}{2n}\frac{\sum_{i=1}^{N-n}a^{i}}{a^{N}}+\frac{a^{N}-a^{N-1}}{na^{N}}+\frac{a^{N}-a^{N-2}}{na^{N}}+\ldots+\frac{a^{N}-a^{N-n+1}}{na^{N}}=$
$\frac{a^{n}-2}{2n}\frac{a^{N-n+1}-a}{a^{N}(a-1)}+\frac{n-1}{n}-\frac{1}{n}\left(\frac{1}{a}+\frac{1}{a^{2}}+\ldots+\frac{1}{a^{n-1}}\right)=$
$\frac{2n-1}{2n}+\frac{1}{2n(a-1)}+\frac{1}{na^{N-1}(a-1)}-\frac{1}{2na^{N-n-1}(a-1)}-\frac{1}{na^{n-1}(a-1)}-\frac{1}{n}\left(\frac{1-\frac{1}{a^{n-1}}}{a-1}\right)=$
$\frac{2n-1}{2n}+\frac{1}{na^{N-1}(a-1)}-\frac{1}{2na^{N-n-1}(a-1)}-\frac{1}{2n(a-1)}$

Therefore

$\liminf_{N\rightarrow\infty}\frac{|R^{\prime}\cap[1,N]|}{N}=\frac{2n-1}{2n}-\frac{1}{2n(a-1)}=1-\frac{a}{2n(a-1)}$

As $k$ can be chosen to be arbitrarily large, $n=2^{k}$ can be arbitrarily
large (while $a\geq 3$ can be fixed) so as

$\lim_{n\rightarrow\infty}1-\frac{a}{2n(a-1)}=1$

we have $\beta_{Z^{+}}(4)=1$. ∎

######  Theorem 5.

$\beta_{\mathbb{Z}}(4)\geq\frac{2}{3}$ and $\alpha_{\mathbb{Z}}(4)=1$

###### Proof.

Consider the permutation

$T=X_{2},Y_{1},X_{4},Y_{3},\ldots,X_{2n},Y_{2n-1},X_{2n+2},Y_{2n+1}\ldots$

where $X_{i}$ is a permutation of the even integers in
$[a^{i},\frac{a^{i+2}}{3}-1]\cup[-\frac{a^{i+2}}{3}+1,-a^{i}]$ which avoid
$3$-APs and $Y_{i}$ is a permutation of the odd integers in
$[a^{i},\frac{a^{i+2}}{3}-1]\cup[-\frac{a^{i+2}}{3}+1,-a^{i}]$ which avoid
$3$-APs for $a>3$, $a$ divisible by $3$. We will show $T$ avoids $4$-APs.
Assume there exists a $4$-AP with terms $a_{1},a_{2},a_{3},a_{4},$ with common
difference $d$.

Case 1 Let $a_{1}$ and $a_{2}$ belong to the same block. WLOG let this be
$X_{i}$. Then $a_{3}$ cannot be in $X_{i}$, and $a_{1},a_{2},d,$ are even.
$|d|<\frac{2}{3}a^{i+2}$ so $-a^{i+2}<a_{3}<a^{i+2}$. As $a_{3}$ is even and
appears after $X_{i}$, $|a_{3}|\geq a^{i+2}$. So this case cannot occur.

Case 2 Let $a_{1}$ be in $X_{i}$ and $a_{2}$ be in $X_{j}$. Then $j>i+1$ and
$d$ is even. So $|d|<\frac{a^{j+2}}{3}+\frac{a^{i+2}}{3}$ and
$|a_{3}|<\frac{2}{3}a^{j+2}+\frac{a^{i+2}}{3}<a^{j+2}$. As $a_{3}$ is even, if
it appears after $X_{j}$ then $|a_{3}|\geq a^{j+2}$. Therefore $a_{3}$ is in
$X_{j}$. So $|a_{4}|<\frac{2}{3}a^{j+2}+\frac{a^{i+2}}{3}<a^{j+2}$ and
similarly $a_{4}$ is in $X_{j}$. But then $a_{2},a_{3},a_{4}$ are all in
$X_{j}$ which cannot occur as $X_{j}$ avoids $3$-APs. The case where $a_{1}$
is in $Y_{i}$ and $a_{2}$ is in $Y_{j}$ is similar.

Case 3 Let $a_{1}$ be in $X_{i}$ and $a_{2}$ be in $Y_{j}$ for $j>i$. Then $d$
is odd and $|d|<\frac{a^{j+2}}{3}+\frac{a^{i+2}}{3}$. Therefore
$|a_{3}|<\frac{2}{3}a^{j+2}+\frac{a^{i+2}}{3}<a^{j+3}$. But as $a_{3}$ is even
and occurs after $Y_{j}$, $|a_{3}|\geq a^{j+3}$. So this case cannot occur.

Case 4 Let $a_{1}$ be in $X_{i}$ and $a_{2}$ be in $Y_{i-1}$. Then $d$ is odd
and so $a_{3}$ is even and appears after $Y_{i-1}$, therefore $|a_{3}|\geq
a^{i+2}$. $|d|=|a_{2}-a_{1}|<\frac{a^{i+1}}{3}+\frac{a^{i+2}}{3}$ and so
$|a_{3}|=|a_{2}+d|<\frac{a^{i+2}}{3}+\frac{2}{3}a^{i+1}<a^{i+2}$. So this case
cannot occur.

Case 5 Let $a_{1}$ be in $Y_{i}$ and $a_{2}$ be in $X_{j}$. Then $j>i+2$, $d$
is odd and $|d|<\frac{a^{j+2}}{3}+\frac{a^{i+2}}{3}$. So
$|a_{3}|<\frac{2}{3}a^{j+2}+\frac{a^{i+2}}{3}<a^{j+3}$ and as $a_{3}$ is odd
and appears after $X_{j}$, this means $a_{3}$ is in $Y_{j-1}$ or $Y_{j+1}$.

Case 5a Let $a_{3}$ be in $Y_{j-1}$. Then $|a_{3}|<\frac{a^{j+1}}{3}$ and so
$|a_{4}|=|a_{3}+d|<\frac{a^{j+2}}{3}+\frac{a^{j+1}}{3}+\frac{a^{i+2}}{3}<a^{j+2}$.
But as $a_{4}$ is even and appears after $Y_{j-1}$, $|a_{4}|\geq a^{j+2}$. So
this case cannot occur.

Case 5b Let $a_{3}$ be in $Y_{j+1}$. Then $|a_{3}|<\frac{a^{j+3}}{3}$ so
$|a_{4}|<\frac{a^{j+3}}{3}+\frac{a^{j+2}}{3}+\frac{a^{i+2}}{3}<a^{j+4}$. But
as $a_{4}$ is even and appears after $Y_{j+1}$, $|a_{4}|\geq a^{j+4}$. So this
case cannot occur.

Therefore $T$ avoids $4$-APs.

$\frac{|T\cap[-a^{n},a^{n}]|}{2a^{n}}=\frac{a^{2}-3}{6}\frac{\sum_{i=1}^{n-2}a^{i}}{a^{n}}+\frac{a^{n}-a^{n-1}}{2a^{n}}=\frac{a^{2}-3}{6}\frac{a^{n-1}-a}{a^{n}(a-1)}+\frac{1}{2}-\frac{1}{2a}=\frac{a-3}{6(a-1)}-\frac{a^{2}-3}{6a^{n-1}(a-1)}+\frac{1}{2}$

It follows that

$\liminf_{N\rightarrow\infty}\frac{|T\cap[-N,N]|}{2N}=\frac{a-3}{6(a-1)}+\frac{1}{2}=\frac{2}{3}-\frac{1}{3(a-1)}$

As $a$ can be arbitrarily large, $\beta_{\mathbb{Z}}(4)\geq\frac{2}{3}$.

$\frac{|T\cap[-\frac{a^{n}}{3},\frac{a^{n}}{3}]|}{2\frac{a^{n}}{3}}=\frac{a^{2}-3}{2}\frac{\sum_{i=1}^{n-2}a^{i}}{a^{n}}+3\frac{\frac{a^{n}}{3}-a^{n-1}}{2a^{n}}=\frac{a^{2}-3}{2}\frac{a^{n-1}-a}{a^{n}(a-1)}+\frac{1}{2}-\frac{3}{2a}=\frac{a-3}{2(a-1)}-\frac{a^{2}-3}{2a^{n-1}(a-1)}+\frac{1}{2}$

So

$\limsup_{N\rightarrow\infty}\frac{|T\cap[-N,N]|}{2N}=\frac{a-3}{2(a-1)}+\frac{1}{2}=1-\frac{1}{a-1}$

As $a$ can be arbitrarily large, $\alpha_{\mathbb{Z}}(4)=1$. ∎

######  Theorem 6.

$\beta_{\mathbb{Z}}(3)\geq\frac{3}{10}$

###### Proof.

Consider the permutation

$K=Y_{0},X_{1},Y_{2},X_{3},Y_{4},\ldots,X_{2k-1},Y_{2k}\ldots$

where $X_{i}$ is a permutation of $[2^{i},\lfloor\frac{8}{5}2^{i}\rfloor]$
which avoids $3$-APs and $Y_{i}$ is a permutation of
$[-\lfloor\frac{8}{5}2^{i}\rfloor,-2^{i}]$ which avoids $3$-APs. We shall show
$K$ avoids $3$-APs. Let $a_{1},a_{2},a_{3}$ be a $3$-AP with common difference
$d$ and let $a_{1}$ be in the block $X_{i}$. The cases where $a_{1}$ are in
$Y_{i}$ are similar. Note that $a_{2}$ must be in $X_{i}$ or $X_{j}$ for
$j>i+1$ or $Y_{k}$ for $k>i$.

Case 1 If $a_{2}$ is in $X_{i}$ then $|d|<\frac{3}{5}2^{i}$. So
$0<\frac{2}{5}2^{i}<a_{3}<\frac{11}{5}2^{i}<2^{i+2}$. But as $a_{3}$ cannot be
in $X_{i}$ and so appears in $K$ after $X_{i}$, $a_{3}\geq 2^{i+2}$ or
$a_{3}\leq-2^{i+1}<0$.

Case 2 If $a_{2}$ is in $X_{j}$ for $j>i+1$ then
$2^{j}-\frac{8}{5}2^{i}<d<\frac{8}{5}2^{j}-2^{i}$ so
$\frac{8}{5}2^{j}=2^{j+1}-\frac{8}{5}2^{j-2}\leq
2^{j+1}-\frac{8}{5}2^{i}<a_{3}<\frac{16}{5}2^{j}-2^{i}<2^{j+2}$. But there are
no terms in $K$ between $\frac{8}{5}2^{j}$ and $2^{j+2}$.

Case 3 If $a_{2}$ is in $Y_{k}$ for $k>i$ then
$-\frac{8}{5}2^{k}-\frac{8}{5}2^{i}<d\leq-2^{k}-2^{i}$ so
$-2^{k+2}=-\frac{16}{5}2^{k}-\frac{8}{5}2^{k-1}\leq-\frac{16}{5}2^{k}-\frac{8}{5}2^{i}<a_{3}\leq-2^{k+1}-2^{i}<-\frac{8}{5}2^{k}$.
But there are no terms in $K$ in this range.

So $K$ avoids $3$-APs. By considering

$\frac{|K\cap[-2^{n},2^{n}]|}{2\times
2^{n}}=\frac{3}{5}\frac{\sum_{i=1}^{n-1}2^{i}}{2^{n+1}}=\frac{3}{10}\frac{2^{n}-2}{2^{n}}$

we see that

$\liminf_{N\rightarrow\infty}\frac{|K\cap[-N,N]|}{2N}=\frac{3}{10}$

and so $\beta_{\mathbb{Z}}(3)\geq\frac{3}{10}$. ∎

It is of interest to note that

$\alpha_{\mathbb{Z}}(k)=\sup_{R}\limsup_{n\rightarrow\infty}\frac{|R\cap[-n,n]|}{2n}=\sup_{R}\limsup_{n\rightarrow\infty}\left(\frac{|R\cap[1,n]|}{2n}+\frac{|R\cap[-n,-1]|}{2n}\right)$
$\leq\sup_{R}\limsup_{n\rightarrow\infty}\frac{|R\cap[1,n]|}{2n}+\sup_{R}\limsup_{n\rightarrow\infty}\frac{|R\cap[-n,-1]|}{2n}$
$=\sup_{S}\limsup_{n\rightarrow\infty}\frac{|S\cap[1,n]|}{2n}+\sup_{S}\limsup_{n\rightarrow\infty}\frac{|S\cap[1,n]|}{2n}=\sup_{S}\limsup_{n\rightarrow\infty}\frac{|S\cap[1,n]|}{n}=\alpha_{\mathbb{Z^{+}}}(k)$

where the supremum is taken over all subsets $R$ of the integers (all subsets
$S$ of the positive integers respectively) that avoid $k$-APs. Note that
$\alpha_{\mathbb{Z^{+}}}(k)=\alpha_{\mathbb{Z}}(k)=1$ for all $k\geq 4$ as
$\alpha_{\mathbb{Z^{+}}}(4)=\alpha_{\mathbb{Z}}(4)=1$ from [5] and Theorem
$5$. If the conjecture in [5] is true and
$\alpha_{\mathbb{Z^{+}}}(3)=\frac{1}{2}$, then as
$\frac{1}{2}\leq\alpha_{\mathbb{Z}}(3)\leq\alpha_{\mathbb{Z^{+}}}(3)$ by [1]
and the above inequality, we would have
$\alpha_{\mathbb{Z^{+}}}(3)=\alpha_{\mathbb{Z}}(3)=\frac{1}{2}$.

In [4], it is shown that the positive integers can be partitioned into $3$
sequences that each avoid $3$-APs. By using the same argument as in Theorem
$6$, it can be shown that when
$X_{i}^{\prime}=[\lceil\frac{8}{5}2^{i}\rceil,\lfloor\frac{64}{25}2^{i}\rfloor]$
and
$Y_{i}^{\prime}=[-\lfloor\frac{64}{25}2^{i}\rfloor,-\lceil\frac{8}{5}2^{i}\rceil]$,

$K^{\prime}=Y_{0}^{\prime},X_{1}^{\prime},Y_{2}^{\prime},X_{3}^{\prime},Y_{4}^{\prime},\ldots,X_{2k-1}^{\prime},Y_{2k}^{\prime}\ldots$

avoids $3$-APs. Similarly, when
$X_{i}^{\prime\prime}=[\lceil\frac{64}{25}2^{i}\rceil,2^{i+2}]$ and
$Y_{i}^{\prime\prime}=[-2^{i+2},-\lceil\frac{64}{25}2^{i}\rceil]$,

$K^{\prime\prime}=0,1,Y_{0}^{\prime\prime},X_{1}^{\prime\prime},Y_{2}^{\prime\prime},X_{3}^{\prime\prime},Y_{4}^{\prime\prime},\ldots,X_{2k-1}^{\prime\prime},Y_{2k}^{\prime\prime}\ldots$

avoids $3$-APs. As the set $K\cup K^{\prime}\cup K^{\prime\prime}$ is the set
of all integers, and each avoids $3$-APs, we can partition the integers into
$3$ sequences that each avoid $3$-APs. It was noted in [5] that if
$\alpha_{\mathbb{Z^{+}}}(3)+\beta_{\mathbb{Z^{+}}}(3)<1$ then the positive
integers cannot be partitioned into $2$ sequences that each avoid $3$-APs.
Similarly if $\alpha_{\mathbb{Z}}(3)+\beta_{\mathbb{Z}}(3)<1$ then the
integers cannot be partitioned into $2$ sequences that each avoid $3$-APs.

##  5 Monotone Arithmetic Progressions Mod n

In [3], Nathanson proved that if $b=p_{1}p_{2}\ldots p_{t}$ for $p_{i}<k$ not
necessarily distinct and if $m$ is $k$-permissible then $mb$ is
$k$-permissible. As it is clear that if $p_{i}<k$ then $p_{i}$ is
$k$-permissible, the next result generalises this.

######  Theorem 7.

If $n$ and $m$ are $k$-permissible, then so is $mn$.

###### Proof.

Let $a_{1},\ldots,a_{n}$ be a permutation of $[1,n]$ that avoids $k$-APs mod
$n$ and let $b_{1},\ldots,b_{m}$ be a permutation of $[1,m]$ that avoids
$k$-APs mod $m$.

Then consider

$S=m(a_{1}-1)+b_{1},m(a_{2}-1)+b_{1},\ldots,m(a_{n}-1)+b_{1},m(a_{1}-1)+b_{2},m(a_{2}-1)+b_{2},\ldots,m(a_{n}-1)+b_{2},$
$m(a_{1}-1)+b_{3},\ldots,m(a_{1}-1)+b_{m},m(a_{2}-1)+b_{m},\ldots,m(a_{n}-1)+b_{m}$

We will show that $S$ is a permutation of $[1,mn]$ that avoids $k$-APs mod
$mn$ and therefore show $mn$ to be $k$-permissible. First note that this is a
permutation of $[1,mn]$ as $m(a_{i}-1)$ runs through all multiples of $m$ from
$0\times m$ to $(n-1)\times m$ and $b_{i}$ runs through all integers from $1$
to $m$. Assume there exists a $k$-AP mod $mn$, $c_{1},c_{2},\ldots,c_{k}$ with
common difference $d$ in $S$.

Case 1 Assume $d$ is divisible by $m$ so there exists an integer $0<t<n$ such
that $d=mt$. Then all terms of the progression are equivalent to each other
mod $m$ so $a_{1}\equiv a_{2}\equiv\ldots\equiv a_{k}\equiv b_{s}\mod{m}$ for
some $s\in\\{1,\ldots,m\\}$. Then the $k$-AP is contained in
$m(a_{1}-1)+b_{s},m(a_{2}-1)+b_{s},\ldots,m(a_{n}-1)+b_{s}$. So
$c_{i}=m(a_{r_{i}}-1)+b_{s}$ and $r_{i}$ is a strictly increasing sequence for
$1\leq i\leq k$ due to how the terms are ordered in $S$. Then
$m(a_{r_{i}}-1)+b_{s}+d\equiv m(a_{r_{i+1}}-1)+b_{s}\mod mn$. So
$m(a_{r_{i}}-1)+d\equiv m(a_{r_{i+1}}-1)\mod mn$ and therefore
$a_{r_{i}}-1+t\equiv a_{r_{i+1}}-1\mod n$. This means $a_{r_{i}}+t\equiv
a_{r_{i+1}}\mod n$. The terms $a_{r_{i}}\mod n$ are all distinct. This is
because if $a_{r_{i}}\equiv a_{r_{j}}\mod n$ then as
$a_{r_{i}},a_{r_{j}}\in[1,n]$, $a_{r_{i}}=a_{r_{j}}$ and so $c_{i}=c_{j}$. But
the terms of the $k$-AP are all distinct so $i=j$. So the sequence
$a_{r_{1}},a_{r_{2}},\ldots,a_{r_{k}}$ forms a $k$-AP mod $n$ with common
difference $t$ and is contained in $a_{1},a_{2},\ldots,a_{n}$ which is a
contradiction.

Case 2 Assume $m$ does not divide $d$. Then every pair of consecutive terms in
the progression, $c_{i}$ and $c_{i+1}$, have different residues mod $m$ and as
terms in $S$ are arranged in blocks of their residues mod $m$, every term in
the $k$-AP is distinct mod $m$. Note that the residues mod $m$ of the terms in
$S$ are in the order $b_{1},b_{2},\ldots,b_{m}$. So
$c_{i}=m(a_{f_{i}}-1)+b_{g_{i}}$ where $g_{i}$ is a strictly increasing
sequence for $1\leq i\leq k$. It follows that
$m(a_{f_{i}}-1)+b_{g_{i}}+d\equiv m(a_{f_{i+1}}-1)+b_{g_{i+1}}\mod mn$.
Therefore $m(a_{f_{i}}-1)+b_{g_{i}}+d\equiv m(a_{f_{i+1}}-1)+b_{g_{i+1}}\mod
m$ and so $b_{g_{i}}+d\equiv b_{g_{i+1}}\mod m$. The terms $b_{g_{i}}\mod m$
are all distinct. This is because if $b_{g_{i}}\equiv b_{g_{j}}\mod m$ then as
$b_{g_{i}},b_{g_{j}}\in[1,m]$, $b_{g_{i}}=b_{g_{j}}$. This means $c_{i}\equiv
c_{j}\mod m$ and so $i=j$. Then the sequence
$b_{g_{1}},b_{g_{2}},\ldots,b_{g_{k}}$ forms a $k$-AP mod $m$ with common
difference $d$ and is contained in $b_{1},\ldots,b_{m}$ which is a
contradiction. ∎

This implies that if all the primes dividing $n$ are $k$ permissible, so is
$n$. Conversely, we know from Nathanson [3], that if $m$ is not $k$
permissible and $m$ divides $n$ then $n$ is not $k$-permissible. One way to
see this is that $m$ not being $k$-permissible means every permutation of the
integers in $[1,m]$ contains a $k$-AP mod $m$ and when this progression is
multiplied by the integer $\frac{n}{m}$, it becomes a $k$-AP mod $n$. For any
permutation of $[1,n]$, the subsequence comprised of terms that are multiples
of $\frac{n}{m}$ is a permutation of the integers in $[1,m]$ multiplied by
$\frac{n}{m}$ so it contains a $k$-AP mod $n$.

Together this implies that $n$ is $k$-permissible iff all prime factors of $n$
are $k$-permissible. Therefore we can restrict our attention to prime $n$.
With this it is quite easy to rederive the result that the $n$ that are
$3$-permissible are the powers of $2$ (see [3] or [2] for alternate proofs).
Any permutation of $[1,2]$ clearly avoids $3$-APs mod $2$. For any odd prime
$p$ and permutation $a_{1},\ldots,a_{p}$ of $[1,p]$,
$a_{1},a_{2},2a_{2}-a_{1}\mod p$ forms a $3$-AP mod $p$. This is because
$2a_{2}-a_{1}\mod p$ must be distinct from $a_{1}$ and $a_{2}$ as otherwise
$a_{1}\equiv a_{2}\mod p$ which is a contradiction as $a_{1},a_{2},$ are
distinct integers of $[1,p]$. Using this with Theorem $7$ implies $n$ is
$3$-permissible iff $n$ is a power of $2$.

We can also use Theorem $7$ to determine an infinite number of $n$ that are
$4$-permissible. The following permutations show that all primes less than or
equal to $13$ are $4$-permissible.

$2,1$ $3,1,2$ $5,1,3,4,2$ $7,1,4,5,6,3,2$ $11,1,9,10,5,3,6,2,4,8,7$
$13,1,12,7,3,9,6,4,8,10,11,2,5$

So all $n$ with no prime factors greater than $13$ are $4$-permissible.

We now find the structure of all permutations of $[1,2^{k}]$ which avoid
$3$-APs mod $2^{k}$. First, for completeness, we prove the following result
that is found in [4] and [2].

######  Lemma 8.

Let $k\geq 1$. For permutations of $[1,2^{k-1}]$, $A$ and $B$, that avoid
$3$-APs mod $2^{k-1}$, $2A,2B-1$ and $2A-1,2B$ are permutations of $[1,2^{k}]$
that avoid $3$-APs mod $2^{k}$. There are $2^{2^{k}-1}$ such permutations that
avoid $3$-APs mod $2^{k}$.

###### Proof.

As $A$ and $B$ are permutations of $[1,2^{k-1}]$, $2A$ contains exactly the
even integers in $[1,2^{k}]$ and $2B-1$ contains exactly the odd integers in
$[1,2^{k}]$. So $2A,2B-1$ is a permutation of $[1,2^{k}]$. Assume $2A,2B-1$
contains a $3$-AP mod $2^{k}$ with terms $a_{1},a_{2},a_{3}$ and common
difference $d$. As $a_{3}\equiv a_{1}+2d\mod 2^{k}$, it follows that
$a_{3}\equiv a_{1}\mod 2$ so either $a_{1}$ and $a_{3}$ are in $2A$ or $a_{1}$
and $a_{3}$ are in $2B-1$. Therefore either $a_{1},a_{2},a_{3},$ are in $2A$
or $a_{1},a_{2},a_{3},$ are in $2B-1$ and in both cases $d$ is even.

As $a_{1}\equiv a_{2}+d\mod 2^{k}$ and $a_{2}\equiv a_{3}+d\mod 2^{k}$, in the
first case, $\frac{a_{1}}{2}\equiv\frac{a_{2}}{2}+\frac{d}{2}\mod 2^{k-1}$ and
$\frac{a_{2}}{2}\equiv\frac{a_{3}}{2}+\frac{d}{2}\mod 2^{k-1}$. As $a_{1}$
appears before $a_{2}$ and $a_{2}$ appears before $a_{3}$ in $2A$,
$\frac{a_{1}}{2}$ appears before $\frac{a_{2}}{2}$ and $\frac{a_{2}}{2}$
appears before $\frac{a_{3}}{2}$ in $A$. So
$\frac{a_{1}}{2},\frac{a_{2}}{2},\frac{a_{3}}{2},$ is a $3$-AP mod $2^{k-1}$
with common difference $\frac{d}{2}$ in $A$. But this contradicts $A$ avoiding
$3$-APs mod $2^{k-1}$.

Similarly in the second case,
$\frac{a_{1}+1}{2},\frac{a_{2}+1}{2},\frac{a_{3}+1}{2},$ form a $3$-AP mod
$2^{k-1}$ with common difference $\frac{d}{2}$ in $B$. But this contradicts
$B$ avoiding $3$-APs mod $2^{k-1}$.

So $2A,2B-1$ avoids $3$-APs mod $2^{k}$. The same argument applies to
$2A-1,2B$. Let $\psi(k)$ be the number of permutations of $[1,2^{k}]$ that
avoid $3$-APs mod $2^{k}$ that are of the form $2A-1,2B$ or $2A,2B-1$ for some
$A$ and $B$ that avoid $3$-APs mod $2^{k-1}$. Then $\psi(k)=2\psi(k-1)^{2}$ as
there are $\psi(k-1)$ choices of $A$, $\psi(k-1)$ choices of $B$ and $2$
choices of $2A-1,2B$ or $2A,2B-1$. As it is clear that $\psi(1)=2$, it is easy
to check that $\psi(k)=2^{2^{k}-1}$. ∎

Let $[a+mb]^{\prime}$ be a permutation of all the integers in $[1,2^{k}]$ that
are equivalent to $a+mb\mod 2^{k}$, where $a,b$ are fixed integers and $m$ can
be any odd integer, that avoids $3$-APs mod $2^{k}$. That is,
$[a+mb]^{\prime}$ contains all integers in $[1,2^{k}]$ that are equivalent to
$a+b$ mod $2b$. The latter part of the below theorem was also proven in [6].

######  Theorem 9.

Permutations of $[1,2^{k}]$ that avoid $3$-APs mod $2^{k}$ are exactly those
of the form

$a,a+2^{k-1}\mod
2^{k},[a+m2^{k-2}]^{\prime},[a+m2^{k-3}]^{\prime},\ldots,[a+m2]^{\prime},[a+m]^{\prime}$

for some $a\in[1,2^{k}].$ There are $2^{{2^{k}}-1}$ such permutations and for
$k\geq 1$ they are also exactly those that are of the form $2A,2B-1$ or
$2A-1,2B$ for permutations $A,B$ of $[1,2^{k-1}]$ that avoid $3$-APs mod
$2^{k-1}$.

###### Proof.

Let $P$ be a permutation of $[1,2^{k}]$ that avoids $3$-APs mod $2^{k}$. We
shall prove this has the claimed structure by induction on $r$ where $r$ is
defined below. If $k=0$ or $k=1$, $P$ trivially satisfies the structure in the
theorem. Note that this structure can be rewritten as

$[a+m2^{k}]^{\prime},[a+m2^{k-1}]^{\prime},[a+m2^{k-2}]^{\prime},[a+m2^{k-3}]^{\prime},\ldots,[a+m2]^{\prime},[a+m]^{\prime}$

as the first two blocks only contain one term each. Additionally, the block
$[a+m2^{k-t}]^{\prime}$ has $2^{t-1}$ terms in it for $1\leq t\leq k$. Let the
first term of $P$ be $a$. Then denote the second term by $b$. $a,b,2b-a\mod
2^{k}$ forms a $3$-AP mod $2^{k}$ in $P$, unless $2b-a\equiv a\mod 2^{k}$ or
$2b-a\equiv b\mod 2^{k}$. If $2b-a\equiv b\mod 2^{k}$ then $a\equiv b\mod
2^{k}$ but as $a,b\in[1,2^{k}]$, $a=b$. But $a$ and $b$ are distinct. If
$2b-a\equiv a\mod 2^{k}$ then $b\equiv a\mod 2^{k-1}$ so $b=a$ or
$b=a+2^{k-1}\mod 2^{k}$. $b$ is distinct from $a$ so the second term is
$a+2^{k-1}\mod 2^{k}$. So the first $2^{1}$ terms are in the order as claimed.

Now assume that the first $2^{r}$ terms are in the order as claimed for some
$1\leq r\leq k-1$. This corresponds to the first $2^{r}$ terms being
$[a+m2^{k}]^{\prime},[a+m2^{k-1}]^{\prime},\ldots,[a+2^{k-r}]^{\prime}$ as
$1+\sum_{i=1}^{r}2^{i-1}=2^{r}$. Label the $2^{r}+i$th term in $P$ by $x_{i}$.
Then the following term is $x_{1}$. For any term $y$ appearing before $x_{1}$,
if $2x_{1}-y\mod 2^{k}$ appeared in $P$ after $x_{1}$, then
$y,x_{1},2x_{1}-y\mod 2^{k}$ forms a $3$-AP mod $2^{k}$. $2x_{1}-y\mod 2^{k}$
cannot be equal to $x_{1}$ as this implies that $x_{1}\equiv y\mod 2^{k}$ and
therefore that $x_{1}=y$ which is a contradiction as $x_{1}$ and $y$ are
distinct terms of the permutation of $[1,2^{k}]$. So for all terms $y$
appearing before $x_{1}$, $2x_{1}-y\mod 2^{k}$ must appear in $P$ before
$x_{1}$. All terms appearing in $P$ before $x_{1}$ are equivalent to
$a+2^{k-l}\mod 2^{k}$ for $0\leq l\leq r$ so they are equivalent to $a\mod
2^{k-r}$. So for any $y$ before $x_{1}$, $2x_{1}-y\equiv a\mod 2^{k-r}$ and
$y\equiv a\mod 2^{k-r}$. Therefore $2x_{1}\equiv 2a\mod 2^{k-r}$ and so
$x_{1}\equiv a\mod 2^{k-r-1}$. So $2^{k-(r+1)}$ divides $x_{1}-a$. Assume
$x_{1}$ is not equivalent to $a+m2^{k-(r+1)}\mod 2^{k}$ for some odd $m$. Then
$x_{1}\equiv a+m2^{k-l}\mod 2^{k}$ for some odd $m$ and some $r+1<l\leq k$ as
all terms with $l\leq r$ occur before $x_{1}$. However this implies that
$2^{k-l}$ is the highest power of $2$ that divides $x_{1}-a$ and so
$2^{k-(r+1)}$ does not divide $x_{1}-a$. This contradiction implies that
$x_{1}\equiv a+m2^{k-(r+1)}\mod 2^{k}$ for some odd $m$.

Now consider $x_{i}$ for some fixed $i$, $2\leq i\leq 2^{r}$. Then for all
terms $y$ before $x_{1}$ in $P$, $2x_{i}-y\mod 2^{k}$ cannot appear after
$x_{i}$ in $P$ as $P$ avoids $3$-APs mod $2^{k}$. $2x_{i}-y\mod 2^{k}$ cannot
equal $x_{i}$ as then $x_{i}\equiv y\mod 2^{k}$ and so $x_{i}=y$ which is a
contradiction as $y$ appears in $P$ before $x_{i}$. It follows that
$2x_{i}-y\mod 2^{k}$ appears in $P$ before $x_{i}$. If there exists $y$ before
$x_{1}$ such that $2x_{i}-y\mod 2^{k}$ occurs before $x_{1}$ then by the
argument above for $x_{1}$, $x_{i}\equiv a+m2^{k-(r+1)}\mod 2^{k}$ for $m$
odd.

Denote the first $2^{r}$ terms of $P$ by $y_{1},y_{2},\ldots,y_{2^{r}}$.
Otherwise for each of the $y_{j}$ before $x_{1}$ in $P$, $1\leq j\leq 2^{r}$,
there exists $n$, $1\leq n<i\leq 2^{r}$, such that $2x_{i}-y_{j}\equiv
x_{n}\mod 2^{k}$. As there are $2^{r}$ values of $y_{j}$ and less than $2^{r}$
values of $n$, by the pigeonhole principle there must exist distinct $1\leq
j<h\leq 2^{r}$ and an $n$, $1\leq n<i\leq 2^{r}$, such that
$2x_{i}-y_{j}\equiv x_{n}\equiv 2x_{i}-y_{h}\mod 2^{k}$. However then
$y_{j}\equiv y_{h}\mod 2^{k}$ but as $y_{j}$ and $y_{h}$ are terms of a
permutation of $[1,2^{k}]$, this implies $y_{j}=y_{h}$ and so $j=h$. This is a
contradiction.

So $x_{i}\equiv a+m_{i}2^{k-(r+1)}\mod 2^{k}$ for $m_{i}$ odd and $1\leq i\leq
2^{r}$. As there are $2^{r}$ terms equivalent to $a+m2^{k-(r+1)}\mod 2^{k}$
for $m$ odd in $[1,2^{k}]$, $x_{1},x_{2},\ldots,x_{2^{r}}$ are exactly these
terms. As $P$ avoids $3$-APs mod $2^{k}$, so does
$x_{1},x_{2},\ldots,x_{2^{r}}$. Therefore $x_{1},x_{2},\ldots,x_{2^{r}}$ is a
permutation of the form $[a+m2^{k-(r+1)}]^{\prime}$. So the first $2^{r+1}$
terms of $P$ are ordered as claimed. Therefore the induction is completed. So
all the permutations of $[1,2^{k}]$ that avoid $3$-APs mod $2^{k}$ are of the
form

$a,a+2^{k-1}\mod
2^{k},[a+m2^{k-2}]^{\prime},[a+m2^{k-3}]^{\prime},\ldots,[a+m2]^{\prime},[a+m]^{\prime}$

Now we show that all permutations of this form avoid $3$-APs mod $2^{k}$.
Assume there exists a $3$-AP mod $2^{k}$, $a_{1},a_{2},a_{3}$, in such a
permutation. Then $a_{1}\equiv a+m2^{k-l}\mod 2^{k}$ for an odd $m$ and an
$l$, $0\leq l\leq k$, $a_{2}\equiv a+n2^{k-s}\mod 2^{k}$ for an odd $n$ and an
$s$, $l\leq s\leq k$, as $a_{2}$ appears after $a_{1}$ and $a_{3}\equiv
a+c2^{k-v}\mod 2^{k}$ for an odd $c$ and a $v$, $s\leq v\leq k$, as $a_{3}$
appears after $a_{2}$.

Case 1 If $s=l$ then $a_{3}\equiv 2a_{2}-a_{1}\equiv a+2^{k-s}(2n-m)\equiv
a+r2^{k-s}\mod 2^{k}$ for $r=2n-m$ odd. So $a_{1},a_{2},a_{3},$ are all in
$[a+m2^{k-s}]^{\prime}$ which avoids $3$-APs mod $2^{k}$.

Case 2 If $s>l$ then $s\geq l+1\geq 1$. So $a_{3}\equiv 2a_{2}-a_{1}\equiv
a+2^{k-s+1}(n-m2^{s-l-1})\mod 2^{k}$ implies that $2^{k-s+1}$ divides
$a_{3}-a$ as $n-m2^{s-l-1}$ is an integer and $k-s+1\leq k$. But this
contradicts $a_{3}\equiv a+c2^{k-v}\mod 2^{k}$ for $c$ odd and $s\leq v\leq k$
as this implies the highest power of $2$ that could divide $a_{3}-a$ is
$2^{k-s}$.

So permutations of $[1,2^{k}]$ that avoid $3$-APs mod $2^{k}$ are exactly
those of the form

$a,a+2^{k-1}\mod
2^{k},[a+m2^{k-2}]^{\prime},[a+m2^{k-3}]^{\prime},\ldots,[a+m2]^{\prime},[a+m]^{\prime}$

Let $1\leq t\leq k$. Then a permutation of $[1,2^{t-1}]$ that avoids $3$-APs
mod $2^{t-1}$, has been multiplied by $2^{k-t+1}$, had $a-2^{k-t}$ added to
its terms and then been reduced mod $2^{k}$ is a permutation of the form
$[a+m2^{k-t}]^{\prime}$. Additionally each permutation of the form
$[a+m2^{k-t}]^{\prime}$ that has had $2^{k-t}-a$ added to its terms, been
divided by $2^{k-t+1}$ and reduced mod $2^{t-1}$ is a permutation of
$[1,2^{t-1}]$ that avoids $3$-APs mod $2^{t-1}$. So the number of possible
permutations that are of the form $[a+m2^{k-t}]^{\prime}$ is the same as the
number of permutations of $[1,2^{t-1}]$ that avoid $3$-APs mod $2^{t-1}$.

Let $\phi(k)$ be the number of permutations of $[1,2^{k}]$ that avoid $3$-APs
mod $2^{k}$. Then as this is the number of permutations of the form
$a,a+2^{k-1}\mod
2^{k},[a+m2^{k-2}]^{\prime},[a+m2^{k-3}]^{\prime},\ldots,[a+m2]^{\prime},[a+m]^{\prime}$,
$\phi(k)=2^{k}\phi(k-1)\phi(k-2)\ldots\phi(2)\phi(1)\phi(0)$ as there are
$2^{k}$ choices for $a$ and there are $\phi(t-1)$ choices for
$[a+m2^{k-t}]^{\prime}$ for $1\leq t\leq k$. As $\phi(0)=1$ is clear, it is
straightforward to check that $\phi(k)=2^{2^{k}-1}$. For $k\geq 1$ this is the
same as the number of permutations that are of the form $2A,2B-1$ or $2A-1,2B$
for permutations $A,B$ of $[1,2^{k-1}]$ that avoid $3$-APs mod $2^{k-1}$. As
permutations of the form $2A,2B-1$ or $2A-1,2B$ avoid $3$-APs mod $2^{k}$,
this implies that these permutations are all of the permutations that avoid
$3$-APs mod $2^{k}$ for $k\geq 1$. ∎

## References

  * [1] Jesse Geneson.  Forbidden arithmetic progressions in permutations of subsets of the integers.  Discrete Mathematics, 342:1489–1491, 2019.
  * [2] Gyula Károlyi Peter Komjáth.  Well ordering groups with no monotone arithmetic progressions.  Order, 34:299–306, 2017.
  * [3] Melvyn B Nathanson.  Permutations, periodicity, and chaos.  Journal of Combinatorial Theory, Series A, 22(1):61–68, 1977.
  * [4] J.A. Davis R.C. Entringer R.L. Graham G.J. Simmons.  On permutations containing no long arithmetic progressions.  Acta Arithmetica, 34:81–90, 1977.
  * [5] Timothy D. LeSaulnier Sujith Vijay.  On permutations avoiding arithmetic progressions.  Discrete Mathematics, 311(2-3):205–207, 2011.
  * [6] Marcel K. Goh Rosie Y. Zhao.  Arithmetic subsequences in a random ordering of an additive set.  Integers Electronic Journal of Combinatorial Number Theory, 21:A89, 2021.