はじめに
任意の$\mathbb{F}_2$係数多項式$f$において
$$f(x^2)=\{f(x)\}^2$$
が成り立つ。これは比較的簡単に示せる。
$$f(x)=a_0+\cdots+a_{n-1}x^{n-1}$$
なら、
$$\{f(x)\}^2=\sum_{i=0}^{n-1}a_i^2x^{2i}+2\sum_{i\lt j} a_ia_jx^{i+j}$$
となるが、$\mathbb{F}_2$の標数は2なので、第二項は消えるのである。また、$a_i\in\mathbb{F}_2$ならば$a_i^2=a_i$となるため、恒等式が成立する。
これを見るとある疑問が浮かぶ。一般化できないだろうか？と。
つまり、
$\mathbb{F}_q$係数多項式$f$は常に$f(x^q)=\{f(x)\}^q$となるだろうか？
結論から言うとこれは正しいのだが、上記の2乗の場合の方法を一般化するとなると、ゴリゴリ計算することになって面倒くさいので、もっといい方法でやってみることにする。
事前知識
有限体について
$\mathbb{F}_q$を位数$q$の有限体とする。しかし、有限体の位数は必ず素数の整数乗となるため、$q=p^m $とする。ここで、$p$は素数であって、$m $は正の整数である。
このとき、$\mathbb{F}_q$は標数$p$、つまり$p$倍すると消えることに注意である。
また、任意の$x\in\mathbb{F}_q$に対して、$x^q=x$となる。これは有名事実である。
ちなみに、$\mathbb{F}_q$は$\mathbb{F}_p$の有限次拡大で拡大次数は$m $である。
二項係数modについて
$q=p^m $,$p$は素数,$m $は正の整数とする。
このとき、$1\leq k\leq q-1$に対して、
$${}_qC_{k}\equiv 0\pmod{p}$$
となる。
【証明】
証明の方法は色々ある。一番まともな方法は、ルジャンドルの定理を使う方法である。
ルジャンドルの定理については下記リンク参照
${}_qC_{k}=\dfrac{q!}{k!(q-k)!}$なので、${}_qC_{k}$が$p$で割り切れる回数は、
$$\sum_{n=1}^{\infty}\lfloor\dfrac{p^m}{p^n}\rfloor-\lfloor\dfrac{k}{p^n}\rfloor-\lfloor\dfrac{p^m-k}{p^n}\rfloor$$
となる。
ここで、ガウス記号の性質として、
$$\lfloor x+y\rfloor \geq \lfloor x\rfloor +\lfloor y\rfloor$$
というものがある。三角不等式と不等号の向きが逆なことに注意
よって、この無限級数（実際は有限項）の各項はすべて非負となる。
ここで、$n=m $のとき、
$$\lfloor\dfrac{p^m}{p^m}\rfloor-\lfloor\dfrac{k}{p^m}\rfloor-\lfloor\dfrac{p^m-k}{p^m}\rfloor=1-0-0=1\gt 0$$
なので、この級数の値は正の整数となる。よって$p$で割り切れる回数が0でないため、$p$の倍数である。
【別解】
他にも、飛び道具を使う方法もある。Lucasの定理というものを思い出す。
Lucasの定理についてはリンク参照
${}_qC_{k}$を$p$で割った余りを考えるとき、$q,k$をp進数で表記ものとする。
ここで、
$$q=a_0+a_1p+\cdots +a_mq^m,k=b_0+b_1p+\cdots+b_mq^m $$
である。ただし、$0\leq a_i,b_i\lt p$である。
このとき、
${}_qC_{k}\equiv \prod_{i=0}^{m}{}_{a_i}C_{b_i}\pmod{p}$
である。しかし、$q=p^m $なので、$a_0=a_1=\cdots=a_{m - 1}=0,a_m=1$である。
また、$k\lt p^m $より$b_m=0$である。
よって、${}_{a_m}C_{b_m}={}_{1}C_{0}=1$に注意すると
${}_qC_{k}\equiv \prod_{i=0}^{m - 1}{}_{0}C_{b_i}\pmod{p}$
となる。ここで、$0\lt k$より、ある$i$について$b_i\neq 0$となる。
このとき${}_{0}C_{b_i}\equiv 0\pmod{p}$となる。よって、$m $個の因子の中に0が必ずあるのでmod pで0になる。
証明
証明は帰納法でやる。以下の場合で証明できたら帰納法がきちんと走るはずである。
- $f(x)=a$（定数）の場合
- $f(x)=x$の場合
- $f(x),g(x)$で成り立つならば、$f(x)g(x)$でも成り立つ
- $f(x),g(x)$で成り立つならば、$f(x)+g(x)$でも成り立つ
2.と3.で$f(x)=g(x)=x$とすれば$x^2$でも成り立つ。
同様に、$x^{n-1}$で成り立つならば$f(x)=x^{n-1},g(x)=x$とすれば$x^n$でも成立する。よって、任意の自然数$n$について$f(x)=x^n$は条件を満たす。
$f(x)=x^n,g(x)=a$で3.を適用すれば$ax^n$でも成り立つので、すべての単項式で条件を満たす。
任意の$n-1$次以下の多項式で成り立つならば、
$f(x)=a_0+\cdots+a_{n-1}x^{n-1},g(x)=a_nx^n$はそれぞれ条件をみたすので、
$f(x)+g(x)=a_0+\cdots+a_{n-1}x^{n-1}+a_nx^n$でも条件をみたすので、任意の$n$次以下の多項式で成り立つ。
（また、1.より、任意の0次以下の多項式=定数で成り立つ）
よって、任意の多項式で条件を満たす。
それぞれを示す。
1.$f(x)=a$（定数多項式）のとき
$$f(x^q)=a,\{f(x)\}^q=a^q$$
となる。ここで、$a\in\mathbb{F}_q$なので、$a^q=a$である。よって
$$a=f(x^q)=\{f(x)\}^q=a^q$$
となる、
2. $f(x)=x$のとき
$$f(x^q)=x^q,\{f(x)\}^q=x^q$$
よって明らかに成り立つ。
3. $f(x),g(x)$で成立$\Rightarrow$ $f(x)g(x)$で成立
$$f(x^q)g(x^q)=\{f(x)\}^q\{g(x)\}^q=\{f(x)g(x)\}^q$$
つまり、
$$(fg)(x^q)=\{f(x)\}^q\{g(x)\}^q=\{(fg)(x)\}^q$$
より成立
4. $f(x),g(x)$で成立$\Rightarrow$ $f(x)+g(x)$で成立
二項定理より、
$$\{f(x)+g(x)\}^q=\sum_{i=0}^{q}{}_{q}C_{i} \{f(x)\}^i \{g(x)\}^{q-i}$$
となる。しかし、さきほど示した定理より、${}_{q}C_{i}$は$0\lt i\lt q$ならば$p$の倍数である。$\mathbb{F}_q$の標数は$p$であるため$p$の倍数なら0とみなしても良い。
よって、
$$\{f(x)+g(x)\}^q=\sum_{i=0}^{q}{}_{q}C_{i} \{f(x)\}^i \{g(x)\}^{q-i}\equiv \{f(x)\}^q+\{g(x)\}^q=f(x^q)+g(x^q)$$
よって、
$$\{(f+g)(x)\}^q=(f+g)(x^q)$$
となる。
1.2.3.4すべて示せたので、帰納法が無事走って、任意の多項式$f$で$f(x^q)=\{f(x)\}^q$となることが示された。
おまけ（多変数多項式）
実は、任意の$\mathbb{F}_q$係数多変数多項式$f$で
$$f(x_1^q,\ldots,x_k^q)=\{f(x_1,\ldots,x_k)\}^q$$となる。
証明は1変数の場合とほぼ同じ。より詳しく説明すると
- $f(x_1,\ldots,x_k)=a$（定数）の場合
- $f(x_1,\ldots,x_k)=x_i$の場合$(i=1,\ldots,k)$
- $f(x_1,\ldots,x_k),g(x_1,\ldots,x_k)$で成り立つならば、$(fg)(x_1,\ldots,x_k)$でも成り立つ
- $f(x_1,\ldots,x_k),g(x_1,\ldots,x_k)$で成り立つならば、$(f+g)(x_1,\ldots,x_k)$でも成り立つ
を示せばOKである。
1.2.3より単項式で成り立つことがわかって、4.を加えることで任意の多項式でも成り立つことが分かる。
おまけ2（有理式の場合）
有理式の場合でも成り立つことを示す。
有理式は多項式の商体なので、
任意の多項式$f(x_1,\ldots,x_k),g(x_1,\ldots,x_k)$について、$(f/g)(x_1,\ldots,x_k):=f(x_1,\ldots,x_k)/g(x_1,\ldots,x_k)$で成り立つことが示せればOKである。
ここで、
$$(f/g)(x_1^q,\ldots,x_k^q)=\dfrac{f(x_1^q,\ldots,x_k^q)}{g(x_1^q,\ldots,x_k^q)}$$
$$=\dfrac{\{f(x_1,\ldots,x_k)\}^q}{\{g(x_1,\ldots,x_k)\}^q}$$
$$=\left(\dfrac{f(x_1,\ldots,x_k)}{g(x_1,\ldots,x_k)}\right)^q$$
$$=\{(f/g)(x_1,\ldots,x_k)\}^q$$
より成り立つ。
