请教一道计数+数论题

maomaoxiangcao

$p\in Prime,p \equiv 2\bmod 3,p\neq 2$。

在模 $p$ 的剩余系下，$f(x)=x^3(x<p)$ 构成了一个排列 P。

证明 P 是偶排列当且仅当 $p=4k+3$

Czhang271828

先证明以上是排列 (一般称作置换), 也就是
$$
\mathbb Z/p\mathbb Z\to \mathbb Z/ p\mathbb Z,\quad [x]\mapsto [x^3]
$$
是双射. 显然 $[0]$ 对应 $[0]$, 剩下的是乘法群同态
$$
(\mathbb Z/p\mathbb Z)^\times \to (\mathbb Z/ p\mathbb Z)^\times,\quad [x]\mapsto [x^3].
$$
以上是双射当且仅当其是单射. 也就是 $[a^3]=[1]$ 蕴含 $[a]=[1]$. 若 $a\neq 1$, 则 $a^3\equiv 1\mod p$. 依照 Fermat 小定理, $3$ 是 $p-1$ 的因子, 矛盾.

记 $\varphi$ 是上述映射给出的一个置换, 此时
$$
\prod_{0\leq i<j\leq p-1}\frac{\varphi(i)-\varphi(j)}{i-j}\in \{-1,1\}.
$$
取值 $-1$ 或 $1$ 分别对应奇置换与偶置换. 由于 $p\neq 2$, 不妨将 $\varphi:\mathbb F_p\to \mathbb F_p$ 视作 $p$-元域的同构.

构造 $p^2$-元域 $\mathbb F_{p^2}:=\mathbb F_p[x]\pmod {f}$, 此处 $f$ 是任意给定$\color{red}{^{\text{[1]}}}$的二次首一不可约多项式. 此时 $p^2$ 元域的非零元构成 $(p^2-1)$ 阶乘法群. 由于 $3\mid (p^2-1)$, 故存在 $1\neq \alpha\in \mathbb F_{p^2}$ 使得 $\alpha^3=1$​.

回到置换,
$$
\begin{align*}
&\prod_{0\leq i<j\leq p-1}\frac{\varphi(i)-\varphi(j)}{i-j}\\[6pt]
=\,&\prod_{0\leq i<j\leq p-1}(i-\alpha j)(i-\alpha^2j)\\[6pt]
=\,&(-\alpha)^{-p(p-1)/2}\cdot \prod_{0\leq i<j\leq p-1}(i-\alpha j)(j-\alpha i)\\[6pt]
=\,& (-\alpha)^{-p(p-1)/2}\cdot \left[\prod_{i\neq 0\text{ 且 }j\neq 0}(i-\alpha j)\right]\cdot \left[\prod_{1\leq k\leq p-1}(k-\alpha k)\right]^{-1}\\[6pt]
=\,&(-\alpha)^{-p(p-1)/2}\cdot \frac{\mathbb F_{p^2}\text{ 中非零元素的积}}{(1-\alpha)^{p-1}\cdot \mathbb F_{p}\text{ 中非零元素的积}}\\[6pt]
=\,& (-1)^{p(p-1)/2}\cdot \alpha^{-p(p-1)/2} \cdot \frac{1}{(1-\alpha)^{p-1}\cdot 1}\\[6pt]
=\,&(-1)^{p(p-1)/2}\cdot \alpha^{1-p}\cdot (1-\alpha)^{1-p}.
\end{align*}
$$
最后 $\alpha^{1-p}(1-\alpha)^{1-p}=\frac{\alpha(1-\alpha)}{\alpha^p(1-\alpha)^p}$. 依照 $(x+y)^p=x^p+y^p$, 得
$$
\frac{\alpha(1-\alpha)}{\alpha^p(1-\alpha^p)}=\frac{\alpha(1-\alpha)}{\alpha^2(1-\alpha^2)}=\frac{1}{\alpha+\alpha^2}=-1.
$$
当且仅当 $(-1)^{p(p-1)/2+1}=1$​ 时, 上式是偶置换.

依照题设, $p=6k+5$. 因此上式是偶置换当且仅当 $k$ 是奇数, 即 $p=12m+11$.

------------------------------------

$\color{red}{\text{[1]}}$ 需要补充说明 $2$-次首一不可约多项式的存在性.

记 $\mathbb F_p[x]$ 中 $n$ 次首一不可约多项式有 $a_n$ 个. 依照事实
$$
x^{p^N}-x=\prod_{k\mid N}k\text{ 次首一不可约多项式之积},
$$
故 $p^N=\sum_{k\mid N} a_k$. 依照 Möbius 反演即可.

特别地, $a_2=\frac{p^2-p}{2}>0$.