# Vandermonde $V_n$ mod $n$

Consider the all-familiar Vandermonde determinant $$V_n(x_1,\dots,x_n)$$ of the matrix of $$(i,j)$$-entries $$M_n(i,j)=x_j^{i-1}$$ so that $$V_n(x_1,\dots,x_n)=\prod_{1\leq i Let's specialize the variables $$x_k=k\pi_k$$ where $$\pi\in\mathfrak{S}_n$$ is a permutation of $$n$$ letters $$\{1,2,\dots,n\}$$.

Assume $$n>3$$. I like to ask:

QUESTION. Is this true? $$V_n(1\pi_1,2\pi_2,\dots,n\pi_n)$$ is congruent to $$0$$ moduluo $$n$$ for any permutation $$\pi\in\mathfrak{S}_n$$.

• So the question is whether $\{k \pi_k \bmod n \mid k \in \{1,\dots,n\}\}$ can be distinct? Commented Jun 26, 2022 at 15:06
• Let me put it this way - if a counterexample to the question exists, it must have $\pi_n=n$. Commented Jun 26, 2022 at 15:22
• If $n$ is not prime, all the divisors $d$ appears in the product in the factor $(d+1)^2-1^2$. If $p$ is prime it is not true: for $p=2$, $V(1,4) = 4-1 = 3$ is odd. PS i am assuming @MaxAlekseyev is true, that is the only relevant permutation is $\pi_k =k$. Commented Jun 26, 2022 at 15:32
• @AndreaMarino: My comment above is about one particular index $n$ (which is the size of the permutation), and not about the identity permutation. Commented Jun 26, 2022 at 15:35
• Further, a counterexample must have $n$ prime. Suppose to the contrary that $n = pm$ with $p$ prime and $m > 1$, and let $A$ be the elements of $[n]$ which are divisible by $p$. There must be exactly $|A|$ values of $k$ for which $k \pi_k \in A$; if $p | k$ or $p | \pi_k$ then $k \pi_k \in A$; so either we have too many products divisible by $p$ or all of the products divisible by $p$ are divisible by $p^2$; either way, we don't get distinct products. Commented Jun 26, 2022 at 15:54

Per comments above, for a counterexample we have with necessity $$\pi_n=n$$ and prime $$n$$. The case $$n=2$$ is trivial, so I assume that $$n$$ is an odd prime.

The elements $$U:=\{ 1,2,\dots,n-1\}$$ form the unit group of $$GF(n)$$ and the mapping $$i\mapsto i\pi_i$$ has to be a permutation of $$U$$. Such mappings are called complete and it's known that they do not exists whenever the group has a nontrivial, cyclic Sylow 2-subgroup. In our case, $$U$$ has an even order and thus a nontrivial Sylow 2-subgroup, and at the same time all its subgroups are cyclic. Hence, no complete mappings exist, providing an affirmative answer to the question.

• Wow! I didn't think there was so deep math behind this question! Thanks for the elegant answer. Commented Jun 26, 2022 at 16:18
• For a full disclosure, I have learned about the paper I cited from this nice answer to another question. Commented Jun 26, 2022 at 16:20
• Elementary argument: if $k\pi_k$ is a permutation of $U$, then $\prod k\pi_k$ is congruent modulo $p$ to $\prod k=(p-1)!$, that contradicts to Wilson's theorem Commented Jun 26, 2022 at 17:12
• Thank you, Max and also Fedor. Commented Jun 29, 2022 at 17:31

OP asked me to fill in the details of my comment, and in attempting to do so I realised that I claimed too much. However, a very similar argument proves a weaker result which is strong enough to support Max Alekseyev's answer (or Fedor Petrov's comment to it).

Theorem: if there is a counterexample, the smallest $$n$$ which is a counterexample is prime.

Suppose to the contrary that there is a counterexample and that the smallest counterexample is $$n = ab$$ with $$a, b > 1$$. We note that the non-vanishing of the determinant encodes the property that $$k \to k \pi_k \bmod n$$ is a permutation. The multiples of $$a$$ map to multiples of $$a$$; the values of $$k$$ for which $$a | \pi_k$$ also map to multiples of $$a$$. Therefore to preserve the bijective nature of the mapping, we require $$\pi$$ to map multiples of $$a$$ to multiples of $$a$$.

Considering the restriction of $$\pi$$ to multiples of $$a$$ we can define $$\sigma_k = \frac{\pi_{ak}}{a}$$ which must be a permutation of $$[b]$$. But then $$k \to k \sigma_k$$ is also a permutation of $$[b]$$, so we have a smaller counterexample, contradicting our assumption. $$\blacksquare$$

• Thank you, Peter. Commented Jun 29, 2022 at 17:30