6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Couldn't you simply reorder $\mathbb{Z}$, for example, such that you have $(0,1,-1,2,-2,3,-3,\cdots)$? $\endgroup$ – JacobCheverie Apr 16 at 13:31
  • $\begingroup$ @JacobCheverie Then $i = 1, j = 3, k = 5$ gives the arithmetic sequence $(0, -1, -2)$. $\endgroup$ – Arthur Apr 16 at 13:41
  • $\begingroup$ @Arthur I thought you just couldn't have three in a row. I read Kattis and I see the issue with my thinking. Thanks $\endgroup$ – JacobCheverie Apr 16 at 14:21
  • $\begingroup$ 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? $\endgroup$ – antkam Apr 16 at 14:41
  • $\begingroup$ @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.... $\endgroup$ – Mees de Vries Apr 16 at 14:48
6
$\begingroup$

Yes, there are anti-arithmetic sequences (AASs) of any length.

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.

Since there is at least one anti-arithmetic sequence, there are arbitrariy long anti-arithmetic sequences. From a longer AAS we can always make a shorter one by simply taking only the lower numbers from the sequence, so there are AASs of any length.

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.

$\endgroup$
  • 1
    $\begingroup$ nice! i tried on and off today to generalize from a shorter sequence to a longer one. turns out the key is to generalize from TWO shorter sequences. :) $\endgroup$ – antkam Apr 17 at 7:10
  • 1
    $\begingroup$ @antkam, the idea came from your suggestion to find some more sequences; when looking at the output of the code I noticed that the AASs I found tended to have many elements with the same parity at the beginning. So, thank you for the inspiration! $\endgroup$ – Mees de Vries Apr 17 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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