3
$\begingroup$

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<j\leq n}(x_j-x_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$.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ So the question is whether $\{k \pi_k \bmod n \mid k \in \{1,\dots,n\}\}$ can be distinct? $\endgroup$
    – Artur Riazanov
    Commented Jun 26, 2022 at 15:06
  • $\begingroup$ Let me put it this way - if a counterexample to the question exists, it must have $\pi_n=n$. $\endgroup$
    – Max Alekseyev
    Commented Jun 26, 2022 at 15:22
  • $\begingroup$ 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$. $\endgroup$
    – Andrea Marino
    Commented Jun 26, 2022 at 15:32
  • 1
    $\begingroup$ @AndreaMarino: My comment above is about one particular index $n$ (which is the size of the permutation), and not about the identity permutation. $\endgroup$
    – Max Alekseyev
    Commented Jun 26, 2022 at 15:35
  • 2
    $\begingroup$ 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. $\endgroup$
    – Peter Taylor
    Commented Jun 26, 2022 at 15:54

2 Answers 2

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Wow! I didn't think there was so deep math behind this question! Thanks for the elegant answer. $\endgroup$
    – Andrea Marino
    Commented Jun 26, 2022 at 16:18
  • $\begingroup$ For a full disclosure, I have learned about the paper I cited from this nice answer to another question. $\endgroup$
    – Max Alekseyev
    Commented Jun 26, 2022 at 16:20
  • 6
    $\begingroup$ 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 $\endgroup$
    – Fedor Petrov
    Commented Jun 26, 2022 at 17:12
  • $\begingroup$ Thank you, Max and also Fedor. $\endgroup$
    – T. Amdeberhan
    Commented Jun 29, 2022 at 17:31
3
$\begingroup$

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$

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you, Peter. $\endgroup$
    – T. Amdeberhan
    Commented Jun 29, 2022 at 17:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .