4
$\begingroup$

Let $p$ and $q$ be relatively prime. Consider the $p\times q$ matrix $A$ containing the entries $1, 2, 3, \dots, pq$, which is formed via $a_{11} = 1, a_{22} = 2, \dots, a_{p-1,q-1} = pq-1, a_{pq} = pq$, using a torus wrap at the edges.

For example with $p=5$ and $q=3$, $A$ looks like:

\begin{bmatrix} 1 & 11 & 6\\\ 7 & 2 & 12\\\ 13 & 8 & 3\\\ 4 & 14 & 9\\\ 10 & 5 & 15 \end{bmatrix}

I am interested in counting the inversions in $A$, that is, cases of $a_{ij} > a_{kl}$, with $k > i$ and $l > j$.

For instance, in the example $a_{12} = 11$ and $a_{43} = 9$ forms an inversion, and there are $6$ inversions altogether.

We can show that, in general, the number of inversions in $A$ is

$$\binom{\frac{(p-1)(q-1)}{2}}{2}.$$

Is there a reference for this result?

$\endgroup$
  • $\begingroup$ You may like to assume $\gcd(p,q)=1$. $\endgroup$ – T. Amdeberhan Feb 10 '17 at 12:56
  • 1
    $\begingroup$ For the less visual thinkers: You are counting the pairs $\left(i,j\right) \in \left\{0,1,\ldots,pq-1\right\}^2$ satisfying $i > j$ but $i \% p < j \% p$ and $i \% q < j \% q$, where $k \% r$ means the remainder of $k$ modulo $r$. $\endgroup$ – darij grinberg Mar 13 '17 at 9:09
1
$\begingroup$

I do not know of a reference. I have a different interest in results like these which I include here.

Color the left and top borders red, and ask for a specific interval of consecutive numbers that will be red. One can show that at most two consecutive numbers can be red, unless one chooses p to be 2, then one can get 3 consecutive numbers to be red.

So what? Generalizing to higher dimensions, a similar construction for three dimensions with the numbering proceeding in the direction (1,1,1) shows that you can get anywhere from 3 up to 5 consecutive numbers colored red. Since we are using a torus topology (oh, and I count pq followed by 1 as being consecutive), it turns out that it doesn't matter which slices we color, as long as exactly one slice (of codimension 1) perpendicular to each axis is chosen. For d dimensions, we can go from d consecutive red numbers up to a number I call C(d)-1, which is the maximum over all choices of pairwise coprime edges p,q,...,r.

Here C(d) is a function defined by Ernst Jacobsthal, which is the maximum over all integers n with d distinct prime factors of g(n), which in turn is the smallest number in which any interval of length g(n) is guaranteed to have a number coprime to n. It is conjectured that C(d) has growth less than quadratic in d, but this is not known.

Gerhard "Following A Path Less Taken" Paseman, 2017.02.10.

$\endgroup$

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.