# Long anti-arithmetic permutation

A permutation is a sequence $$(a_1, \ldots, a_n)$$ in which each number $$1, \ldots, n$$ appears precisely once. We call a sequence anti-arithmetic if there are no non-trivial arithmetic subsequences in it; that is, if there are no $$i < j < k$$ such that $$(a_i, a_j, a_k)$$ is an arithmetic sequence.

An example of an anti-arithmetic sequence of length 6 is $$(3, 5, 4, 6, 1, 2).$$

Intuitively it seems "hard" to me for a long sequence to be anti-arithmetic. For example, suppose that you have built about half the sequence so far; then adding any element $$a$$ near $$n/2$$ requires that the elements of $$1, \ldots, n$$ you have used so far mirror (almost) exactly around $$a$$, and there are lots of ways for this to go wrong.

In particular, I do not know how to create anti-arithmetic sequences of arbitrary length.

Are there anti-arithmetic sequences of arbitrarily high length? How can I construct those?

I am asking this question because of Kattis problem Antiarithmetic?; googling the word "antiarithmetic" gets me only references to this recreational programming problem. I am not looking for a solution to the problem, only for some more intuition about antiarithmetic sequences.

Edit: Some programming strongly suggests that such anti-arithmetic sequences continue to appear for higher $$n$$. The following (unoptimized, but a fair bit faster than brute force) script shows anti-arithmetic sequences of length up to 40 very quickly, and that there are about 74904 such sequences of length 15.

def extend_aas(length, partial_sequence=[]):
results = []
for i in range(length):
if i in partial_sequence:
continue
for j in partial_sequence:
if 0 <= i + i - j < length and (i + i - j not in partial_sequence):
break
else:
yield partial_sequence + [i]

def get_aases(length, partial=[]):
for extended in extend_aas(length, partial):
if len(extended) == length:
yield extended
else:
for result in get_aases(length, extended):
yield result

for n in range(1, 41):
print(n, next(get_aases(n)))

for n in range(1, 16):
print(n, len(list(get_aases(n))))


However, this still does not give me intuition for why this might be the case.

• Couldn't you simply reorder $\mathbb{Z}$, for example, such that you have $(0,1,-1,2,-2,3,-3,\cdots)$? – JacobCheverie Apr 16 at 13:31
• @JacobCheverie Then $i = 1, j = 3, k = 5$ gives the arithmetic sequence $(0, -1, -2)$. – Arthur Apr 16 at 13:41
• @Arthur I thought you just couldn't have three in a row. I read Kattis and I see the issue with my thinking. Thanks – JacobCheverie Apr 16 at 14:21
• I agree with your intuition that this seems very difficult for large $n$. Have you tried coding this up to find such sequences for $n=7, 8, 9$ etc? – antkam Apr 16 at 14:41
• @antkam I have not, but I have some reason to believe that large such sequences exist (I'm being purposely vague here). Let me see if I can find them for the $n$ you suggest with a quick script.... – Mees de Vries Apr 16 at 14:48

If $$(a_1, \ldots, a_n)$$ and $$(b_1, \ldots, b_n)$$ are AASs of length $$n$$, then we claim that $$(2a_1, \ldots, 2a_n, 2b_1 - 1, \ldots, 2b_n-1)$$ is an AAS of length $$2n$$. Indeed it is clear that every integer $$1, \ldots, 2n$$ appears precisely once, the even ones in the first half and the odd ones in the second half. Furthermore, suppose towards a contradiction that it contains a non-trivial arithmetic sequence. If that sequence is of the form $$(2a_i, 2a_j, x)$$ then we must have that $$x$$ is even, therefore $$x = 2a_k$$. But then $$(a_i, a_j, a_k)$$ would be an arithmetic sequence in $$(a_1, \ldots, a_n)$$. For a similar reason,we cannot have an arithmetic sequence $$(2b_i - 1, 2b_j - 1, x)$$. Finally, a sequence $$(2a_i, 2b_j - 1, x)$$ cannot be arithmetic either, because $$x$$ would have to be even, but no even number occurs after an odd one.
Note furthermore that you can reverse the order of the odd and even parts, and the same argument goes through. This means that if there are $$k$$ AASs of length $$n$$, then this construction gives $$2k^2$$ different AASs of length $$2k$$. Since there is trivially 1 AAS of length 1, this tells us that there are at least $$2^{2^n - 1}$$ AASs of length $$2^n$$. Since the number of AASs of length $$n$$ is bounded by the greatest power of 2 below $$k$$ and the least power of 2 greater than $$k$$, this in particular shows that there are exponentially many length $$k$$ AASs.