The number of inversions of an arithmetic progression modulo some number

Question

Let $n, m$ be coprime and consider the arithmetic progression $0,n,2n,\dots$ modulo $m$. As $n,m$ are coprime, the sequence repeats itself with a period of $m$. We can also see this sequence as a permutation of $[0, \dots, m-1]$: $k$ is mapped on $kn$ modulo $m$. The question is: how many inversions does the permutation so-defined has? Let us call $I(n,m)$ this number here.

For example with $n=3, m=7$, the progression is $0,3,6,2,5,1,4$ with $9$ inversions (3:2, 3:1, 6:2, 6:5, 6:1, 6:4, 2:1, 5:1, 5:4). Thus $I(3,7) = 9$.

There are some observations we can make. It is quite clear that $I(\cdot,m)$ is $m$-periodic and $I(1,m) = 0$ for all $m$. Thus it is sufficient to look for $2 \leq n \leq m-1$.

I am trying to compute some $I(n,m)$ where $m$ is "large" (the order of a billion). At this point I am wondering few things,

1. Is this doable in closed-form?
2. Is this computable in $O(m)$? Naively we can compute the number of inversions in $O(m^2)$, using a standard merge-sort algorithm we could do it in $O(m \ln m)$, there is a fancier algorithm that can bring this to $O(m \sqrt{\ln m})$, but this does not take advantage of the nature of the arithmetic progression.
3. We could merely use the fact that it is a cycle as well. Is there any efficiency gain between computation of inversions of any permutation versus those of a cycle?
4. Does the problem become simpler when considering $m$ to be a power of $2$ (and thus $n$ to be any odd number less than $m$)?

Let me know if you have any insight, this seemed like it should have an easy answer but I am still stuck.

Actually let me share some closed-form results I have obtained. For $m=2^k$, I found that, $$ I(n,m) = \frac{n-1}{4n} (4^k - (n-1)) + \chi_n(k) 2^k $$ where $\chi_n(\cdot)$ is a periodic sequence. The first sequences are, and they are stopped once they repeat, $$ \chi_1 = 0, \\ \chi_3 = \frac16, -\frac16, \\ \chi_5 = \frac35,0,-\frac35,0 \\ \chi_7 = \frac{15}{14},\frac3{14},\frac3{14} \\ \chi_9 = \frac{14}9,\frac49,-\frac49,-\frac{14}9,-\frac49,\frac49 \\ \chi_{11} = \frac{45}{22},\frac{15}{22},\frac9{22},-\frac9{22},-\frac{15}{22},-\frac{45}{22},-\frac{15}{22},-\frac9{22},\frac9{22},\frac{15}{22}. $$

Answer 1

Define permutations of $1,\dots,m-1$ as $\sigma_{n[m]} \colon k \mapsto kn [m]$. As a computational solution, we can rely on the two following facts,

1. $I(n,m)+I(m-n,m) = \frac{(m-1)(m-2)}2$ for $n \wedge m = 1$ since $\sigma_{m-n[m]} = m - \sigma_{n[m]}$, so either $i<j$ is inverted by the first or the second permutation, while there are $\frac{(m-1)(m-2)}2$ ordered pairs.
2. $I(n,kn+t) = \frac{n(n-1)}2 \frac{k(k-1)}2 + k(I(n,n+t) - I(n,t)) + I(n,t)$, this can be seen by drawing the $(i,\sigma(i))$ graphs of the permutations $\sigma_{n[kn+t]}$, adding $n$ to $m$ adds a whole vertical chunk, the number of inversions appears to take this form, although it would need a formal proof.

A recursive algorithm can then be, noted compute(n,m), working on the assumption that $m,n$ are coprime integers:

1. If $m=1$ there is no inversion, return 0.
2. If $n > m$, by $m$-periodicity of $I(\cdot, m)$, compute $n$ modulo $m$, say $r$, then return compute(r,m) where still $r \wedge m = 1$.
3. If $n>\frac m2$, return (m-1)(m-2)/2 - compute(m-n,m), then from now on $n<\frac m2$. Note $(m-n) \wedge m = 1$.
4. Compute the Euclidean division of $m$ by $n$, that is $m = kn + t$ where $t < n$ is coprime with $n$ (otherwise some $d$ would divide $t,n$ thus $m$ while $m \wedge n = 1$ by assumption).
5. Surely $k \geq 2$ since $n < \frac m2$, this means we can using the second fact. Compute i0 = compute(n,t) and i1 = compute(n,n+t), to finally return n(n-1)k(k-1)/4 + k(i1-i0) + i0

Let us call $T(n,m)$ the complexity of compute(n,m) and $T(m)$ the complexity of the worst compute(n,m) (with $0 < 2n < m$). We have, $$ T(n,m) = 1 + T(n,t) + T(n,n+t), $$ that is, $$ T(m) = 1 + \max_{0<2n<m} T(n,t) + T(n,n+t) \leq 1 + \max_{0<2n<m} T(t) + T(n+t), $$ where $t$ again is $m$ modulo $n$ and $n < \frac m2$ without loss of generality. Note that $t < n$ and $n+t \leq m - n$, so assuming $T(\cdot)$ is nondecreasing, $$ T(m) \leq 1 + \max_{0<2n<m} T(n-1) + T(m-n), $$ thus $T(m) = O(m)$. In average the complexity is probably better, if we think of $t$ to be "random" in $1,\dots,n-1$ (coprime with $n$), then $m-(t + n+t) = n-t$ is in average $\frac n2$ and if further $n$ is random in $1,\dots,m-1$ (coprime again), the average decrease of $m$ is of order $\frac m4$, this could give $O(\ln m)$.

In Python this seems to run quite quick,

from time import time

def inversions(n,m):
    if m <= 1:
        return 0
    if n > m:
        n %= m
    inverse = False
    if 2*n > m:
        n = m-n
        inverse = True

    k,t = divmod(m,n)
    i0 = inversions(n,t)
    i1 = inversions(n,n+t)

    resultat = n*(n-1)*k*(k-1)//4 + k*(i1-i0) + i0
    if inverse:
        return (m-1)*(m-2)//2 - resultat
    return resultat

t1 = time()
N = 123456789
M = 2**27
print("There are", inversions(N,M), "in the", N, "arithmetic progression modulo", M, "computed in", time()-t1, "seconds.")