TAOCP 5.1.1 Exercise 19

Let \(n > 1\) be an integer and let \(m\) be an integer with \(\gcd(m,n)=1\).

taocpmathematicsalgorithmsvolume-3math-hard

Section 5.1.1: Inversions

Exercise 19. [M28] (C. Meyer.) When $m$ is relatively prime to $n$, we know that the sequence ($m \bmod n$)(2$m \bmod n$) $\ldots$ (($n$-1)$m \bmod n$) is a permutation of ${1, 2, \ldots, n-1}$. Show that the number of inversions of this permutation can be expressed in terms of Dedekind sums (see Section 3.3.3).

Verified: yes
Solve time: 1h03m

Setup

Let (n > 1) be an integer and let (m) be an integer with (\gcd(m,n)=1).
The sequence
[ a_k = k m \bmod n \qquad (1 \le k \le n-1) ] is a permutation of ({1,2,\dots,n-1}). We want the number of inversions of this permutation, i.e. [ I(m,n) = #\bigl{(i,j) : 1 \le i < j \le n-1,; a_i > a_j\bigr}. ] The Dedekind sum (s(m,n)) (see Section 3.3.3) is defined by [ s(m,n) = \sum_{k=1}^{n-1} \left(!\left(\frac{k}{n}\right)!\right) \left(!\left(\frac{km}{n}\right)!\right), ] where (((x)) = x - \lfloor x \rfloor - \frac12) for non‑integer (x) and (((x)) = 0) for integer (x).
Because (k/n) and (km/n) are never integers for (1 \le k \le n-1) when (\gcd(m,n)=1), we may write [ s(m,n) = \sum_{k=1}^{n-1} \left(\frac{k}{n}-\frac12\right) \left(\frac{km}{n} - \left\lfloor\frac{km}{n}\right\rfloor - \frac12\right). ]

Solution

Step 1. Inversion condition in terms of floor functions.
For (i<j) we have [ a_i = i m - n\left\lfloor\frac{i m}{n}\right\rfloor,\qquad a_j = j m - n\left\lfloor\frac{j m}{n}\right\rfloor. ] The inequality (a_i > a_j) is equivalent to [ n\Bigl(\left\lfloor\frac{j m}{n}\right\rfloor - \left\lfloor\frac{i m}{n}\right\rfloor\Bigr) > (j-i)m. ] Let (d = j-i). Since (\lfloor (i+d)m/n \rfloor - \lfloor i m/n \rfloor) equals either (\lfloor d m/n \rfloor) or (\lfloor d m/n \rfloor + 1), the inequality holds exactly when the larger value occurs, i.e. when [ \left\lfloor\frac{j m}{n}\right\rfloor - \left\lfloor\frac{i m}{n}\right\rfloor = \left\lfloor\frac{(j-i)m}{n}\right\rfloor + 1. ] Thus [ I(m,n) = \sum_{1\le i<j\le n-1} \Bigl( \left\lfloor\frac{j m}{n}\right\rfloor

  • \left\lfloor\frac{i m}{n}\right\rfloor
  • \left\lfloor\frac{(j-i)m}{n}\right\rfloor \Bigr). ]

Step 2. Evaluate the triple sum.
Changing the order of summation, [ \begin{aligned} \sum_{i<j} \left\lfloor\frac{j m}{n}\right\rfloor &= \sum_{j=2}^{n-1} (j-1)\left\lfloor\frac{j m}{n}\right\rfloor,\[4pt] \sum_{i<j} \left\lfloor\frac{i m}{n}\right\rfloor &= \sum_{i=1}^{n-2} (n-1-i)\left\lfloor\frac{i m}{n}\right\rfloor,\[4pt] \sum_{i<j} \left\lfloor\frac{(j-i)m}{n}\right\rfloor &= \sum_{d=1}^{n-2} (n-1-d)\left\lfloor\frac{d m}{n}\right\rfloor. \end{aligned} ] The second and third sums are identical, hence [ I = \sum_{j=2}^{n-1} (j-1)\left\lfloor\frac{j m}{n}\right\rfloor

  • 2\sum_{k=1}^{n-2} (n-1-k)\left\lfloor\frac{k m}{n}\right\rfloor. ] Combining the coefficients for (k=1,\dots,n-1) (noting (\lfloor m/n\rfloor = 0)) gives [ I = \sum_{k=1}^{n-1} (3k - 2n + 1)\left\lfloor\frac{k m}{n}\right\rfloor. \tag{1} ]

Step 3. Relate (1) to Dedekind sums.
Write the coefficient as [ 3k - 2n + 1 = 3n\Bigl(\frac{k}{n}-\frac12\Bigr) - \Bigl(\frac{n}{2}-1\Bigr). ] Then [ I = 3n\sum_{k=1}^{n-1} \Bigl(\frac{k}{n}-\frac12\Bigr) \left\lfloor\frac{k m}{n}\right\rfloor

  • \Bigl(\frac{n}{2}-1\Bigr)\sum_{k=1}^{n-1} \left\lfloor\frac{k m}{n}\right\rfloor. \tag{2} ]

The second sum is classical: because the residues (km \bmod n) run through (1,\dots,n-1), [ \sum_{k=1}^{n-1} \left\lfloor\frac{k m}{n}\right\rfloor = \frac{1}{n}\Bigl(m\frac{n(n-1)}{2} - \frac{n(n-1)}{2}\Bigr) = \frac{(m-1)(n-1)}{2}. \tag{3} ]

For the first sum we use the definition of the Dedekind sum: [ \begin{aligned} s(m,n) &= \sum_{k=1}^{n-1} \Bigl(\frac{k}{n}-\frac12\Bigr) \Bigl(\frac{km}{n} - \left\lfloor\frac{km}{n}\right\rfloor - \frac12\Bigr) \ &= \sum_{k=1}^{n-1} \Bigl(\frac{k}{n}-\frac12\Bigr) \Bigl(\frac{km}{n} - \frac12\Bigr)

  • \sum_{k=1}^{n-1} \Bigl(\frac{k}{n}-\frac12\Bigr) \left\lfloor\frac{km}{n}\right\rfloor. \end{aligned} ] The first sum evaluates to [ \sum_{k=1}^{n-1} \Bigl(\frac{k^2 m}{n^2} - \frac{k}{2n} - \frac{km}{2n} + \frac14\Bigr) = \frac{m(n-1)(n-2)}{12n}. ] Therefore [ \sum_{k=1}^{n-1} \Bigl(\frac{k}{n}-\frac12\Bigr) \left\lfloor\frac{km}{n}\right\rfloor = \frac{m(n-1)(n-2)}{12n} - s(m,n). \tag{4} ]

Step 4. Substitute (3) and (4) into (2). [ \begin{aligned} I &= 3n\Bigl(\frac{m(n-1)(n-2)}{12n} - s(m,n)\Bigr)

  • \frac{n-2}{2}\cdot\frac{(m-1)(n-1)}{2} \ &= \frac{m(n-1)(n-2)}{4} - 3n,s(m,n)
  • \frac{(n-2)(m-1)(n-1)}{4} \ &= \frac{n-1}{4}\Bigl( m(n-2) - (n-2)(m-1) \Bigr) - 3n,s(m,n) \ &= \frac{n-1}{4},(n-2) - 3n,s(m,n). \end{aligned} ]

Thus the number of inversions of the permutation ((m \bmod n)(2m \bmod n)\ldots((n-1)m \bmod n)) is [ \boxed{I(m,n) = \frac{(n-1)(n-2)}{4} - 3n,s(m,n)}. ]

Verification

We test the formula on three independent examples by computing the inversion count directly and comparing with the formula.

  1. (n=5,; m=2).
    Sequence: (2,4,1,3). Inversions: ((2,1), (4,1), (4,3)) → (I=3).
    (s(2,5)=0) (sum of (((k/5))((2k/5))) is (0)).
    Formula: (\frac{4\cdot3}{4} - 15\cdot 0 = 3). ✓

  2. (n=7,; m=2).
    Sequence: (2,4,6,1,3,5). Inversions: ((2,1), (4,1), (4,3), (6,1), (6,3), (6,5)) → (I=6).
    (s(2,7) = \frac{1}{14}).
    Formula: (\frac{6\cdot5}{4} - 21\cdot\frac{1}{14} = 7.5 - 1.5 = 6). ✓

  3. (n=8,; m=3).
    Sequence: (3,6,1,4,7,2,5).
    Inversions: ((3,1),(3,2),; (6,1),(6,4),(6,2),(6,5),; (4,2),; (7,2),(7,5)) → (I=9).
    (s(3,8) = \frac{1}{16}).
    Formula: (\frac{7\cdot6}{4} - 24\cdot\frac{1}{16} = 10.5 - 1.5 = 9). ✓

All direct counts match the formula, confirming the derivation. ∎

Notes

The result holds for any coprime (m,n) with (n>1); if (m) is not in the range (1\le m < n) we simply replace (m) by (m \bmod n) because both the permutation and the Dedekind sum depend only on (m) modulo (n).