Let $p$ be an odd prime. It is well-known that $$\det[i^{j-1}]_{1\le i,j\le p-1}=\prod_{1\le i<j\le p-1}(j-i)\not\equiv0\pmod p.$$ I'm curious about the behavior of the permanent $\text{per}[i^{j-1}]_{1\le i,j\le p-1}$ modulo powers of $p$. This leads me to formulate the following conjecture on the basis of my computation.

Conjecture. If $p$ is a Fermat prime, then $$\text{per}[i^{j-1}]_{1\le i,j\le p-1}\equiv\frac{p-1}2!\ p\pmod{p^2}.$$ If $n\not\equiv2\pmod4$ and $n$ is not a Fermat prime, then $$\text{per}[i^{j-1}]_{1\le i,j\le n-1}\equiv 0\pmod{n^2}.$$ For $n\equiv2\pmod4$, we have $$\text{per}[i^{j-1}]_{1\le i,j\le n-1}\not\equiv 0\pmod{n}.$$

QUESTION: Is the above conjecture true?

Now I show that $\text{per}[i^{j-1}]_{1\le i,j\le p-1}\equiv0\pmod p$ for any odd prime $p$. (It is easy to see that this implies that $n\mid \text{per}[i^{j-1}]_{1\le i,j\le n}$ for all $n=3,4,\ldots$.) Let $g$ be a primitive root modulo $p$. Then $$\text{per}[i^{j-1}]_{1\le i,j\le p-1}\equiv\sum_{\sigma\in S_{p-1}}\prod_{i=1}^{p-1}g^{i(\sigma(i)-1)}=\prod_{i=1}^{p-1}g^{-i}\times\text{per}[g^{ij}]_{1\le i,j\le p-1}\pmod p.$$ Thus we may appy my argument in the related question 316836 to get that $\text{per}[i^{j-1}]_{1\le i,j\le p-1}\equiv0\pmod p$ since the order of $g$ mod $p$ is the even number $p-1$.

Your comments are welcome!

  • $\begingroup$ Great questions ... Do you know if this problem has links with the problem "P=NP" ?? $\endgroup$ – Lenilson Ferreira Sep 25 '19 at 23:21
  • $\begingroup$ why on earth would there be such a connection? $\endgroup$ – kodlu Sep 25 '19 at 23:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.