文献あり

完全冪となるFibonacci多項式

今回は，Fibonacci多項式$F_n(X) \in \symbb{Z}[X]$が，有限体上の多項式環$\symbb{Z}_q[X]$において完全冪となるための条件について，arXivの論文pfをもとに書いていきます．

Fibonacci数列

最も有名な数列の一つに，Fibonacci数列と呼ばれるものがあります．フィボナッチ数列$f_n$は，次の漸化式によって定義されます：
$$ f_0 = 0, f_1 = 1, f_n = f_{n - 1} + f_{n - 2}\ (n \ge 2)\text{.} $$
Fibonacci数列の最初の10項は
$$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 $$
となります．

Bugeaud, Mignotte, Siksekは，完全冪となるFibonacci数列に関して，次の定理を証明しましたpf

Fibonacci数列で完全冪となるものは，$f_0 = 0, f_1 = f_2 = 1, f_6 = 8, f_{12} = 144$のみである．

Fibonacci多項式

まず最初に，今回の主役となるFibonacci多項式の定義をします．

Fibonacci多項式$F_n(X) \in \symbb{Z}[X]$を，次の漸化式により定義する．
\begin{align} F_0(X) &= 0\text{}\\ F_1(X) &= 1\text{}\\ F_n(X) &= TF_{n - 1}(X) + F_{n - 2}(X)\quad(n \ge 2) \end{align}

Fibonacci多項式の最初の5つは
$$ 0, 1, T, T^2 + 1, T^3 + 2T $$
です．

Fibonacci多項式において，Fibonacci数列におけるBinetの公式の類似が成り立ちます．（以下，この命題2をBinetの公式と呼ぶことにします）

$\alpha(X), \beta(X)$を多項式$T^2 - XT - 1$の根とする．このとき
$$ F_n(X) = \frac{\alpha(X)^n - \beta(X)^n}{\alpha(X) - \beta(X)} \tag{1} $$
が成り立つ．特に，標数が2でない体において
$$ \alpha(X) = \frac{X + \sqrt{X^2 + 4}}{2},\ \beta(X) = \frac{X - \sqrt{X^2 + 4}}{2} $$
であり，
$$ F_n(X) = \frac{\left(\frac{1}{2}X + \frac{1}{2}\sqrt{X^2 + 4}\right)^n - \left(\frac{1}{2}X - \frac{1}{2}\sqrt{X^2 + 4}\right)^n}{\sqrt{X^2 + 4}} $$
が成り立つ．

$n$に関する帰納法．$n = 0, 1$のときは自明．$n \ge 2$とし，$n$より小さい正整数についてはこの命題が成り立つと仮定すると，
\begin{align} F_n(X) &= XF_{n - 1}(X) + F_{n - 2}(X)\\ &=\frac{X \alpha(X)^{n - 1} - X \beta(X)^{n - 1} + \alpha(X)^{n - 2} - \beta(X)^{n - 2}}{\alpha(X) - \beta(X)}\\ &= \frac{\alpha(X)^{n - 2}(X\alpha(X) + 1) - \beta(X)^{n - 2}(X\beta(X) + 1)}{\alpha(X) - \beta(X)}\\ &= \frac{\alpha(X)^n - \beta(X)^n}{\alpha(X) - \beta(X)} \end{align}
となり，(1) が示された．ここで，最後の等号は，$\alpha(X), \beta(X)$がともに多項式$T^2 - XT - 1$の根であることによる．

主定理とその証明

主定理

今回紹介したいのは，pfで証明された次の定理です．（以下，特に説明しない場合は文字はこの定理と同じものとします）

主定理

$j$を正整数とする．$p$を$2j$と互いに素な奇素数とし，$q$を$p$の冪とする．このとき，任意の正整数$n$に対し，Fibonacci多項式$F_n(X)$が$\symbb{F}_q[X]$において$j$乗の元となる（すなわち，ある$p(x) \in \symbb{F}_q[X]$が存在して$F_n(X) = p(X)^j$となる）ための必要十分条件は，ある非負整数$k$が存在して$n = p^{ak}$となることである．ただし，$a = \ord_{2j}(p)$は，群$(\symbb{Z} / 2j \symbb{Z})^\times$における$p$の位数を表す．

証明

以下，pfに沿って証明を行っていきます．

有限体上における$F_n(X)$の分解

$\symbb{F}_q[X]$において，
$$ F_{p^k}(X) = (X^2 + 4)^{\frac{p^k - 1}{2}} $$
が成り立つ．

$k = 0$のときは自明．$k \ge 1$とすると，Binetの公式により
\begin{align} F_{p^k}(X) &= \frac{\alpha(X)^{p^k} - \beta(X)^{p^k}}{\alpha(X) - \beta(X)}\\ &= \frac{(\alpha(X) - \beta(X))^{p^k}}{\alpha(X) - \beta(X)}\\ &= (\alpha(X) - \beta(X))^{p^k - 1}\\&=(X^2 + 4)^{\frac{p^k - 1}{2}} \end{align}
となる．

$n = p^k m$（$m$と$p$は互いに素）とするとき，$F_n(X)$は$\symbb{F}_q[X]$において次のように分解する．
$$ F_{p^k m}(X) = F_{p^k}(X) F_{m}(X)^{p^k}\text{.} $$

Binetの公式により，
\begin{align} F_n(X) &= \frac{\alpha(X)^{p^km} - \beta(X)^{p^km}}{\alpha(X) - \beta(X)}\\&=\frac{(\alpha(X)^m - \beta(X)^m)^{p^k}}{\alpha(X) - \beta(X)}\\&= \frac{(\alpha(X) - \beta(X))^{p^k}}{\alpha(X) - \beta(X)} \frac{(\alpha(X)^{m} - \beta(X)^{m})^{p^k}}{(\alpha(X) - \beta(X))^{p^k}}\\&=\frac{(\alpha(X) - \beta(X))^{p^k}}{\alpha(X) - \beta(X)} \left(\frac{\alpha(X)^m - \beta(X)^m}{\alpha(X) - \beta(X)}\right)^{p^k}\\&=F_{p^k}(X)F_m(X)^{p^k} \end{align}
となり，補題の式を得る．

補題4と5を合わせることにより，次の命題が得られます．

$m$を$p$と互いに素な正整数とするとき，Fibonacci多項式$F_{p^km}(X)$は$\symbb{F}_q[X]$において次のように分解する．
$$ F_{p^km}(X) = (X^2 + 4)^{\frac{p^k - 1}{2}}F_m(X)^{p^k}\text{.} $$

$F_m(X)\ (p \nmid m)$のsquare-free性

命題6により，$F_m(X)$が$\symbb{F}_q[X]$でどのように分解するのかが分かればよいこととなります．実は，$F_m(X)\ (p \nmid m)$は$\symbb{F}_q[X]$においてsquare-free（平方因子を持たない）であることがわかります．

任意の$n \ge 0$に対し
$$ F_n(X) = \prod_{k = 1}^{n - 1} (X - i(\zeta_{2n}^k + \zeta_{2n}^{-k})) $$
が成り立つ．ただし，$i$は$1$の原始$4$乗根を，$\zeta_{2n}$は$1$の原始$2n$乗根を表す．

$m$を$p$と互いに素な正整数とするとき，$F_m(X)$は$\symbb{F}_q[X]$においてsquare-freeである．

$F_m(X)$がsquare-freeでないと仮定する．このとき，補題7により，ある整数$1 \le k < \ell < m$が存在して$\zeta_{2m}^k + \zeta_{2m}^{-k} = \zeta_{2m}^\ell + \zeta_{2m}^{-\ell}$，すなわち$(\zeta_{2m}^{-k} - \zeta_{2m}^{-\ell})(\zeta_{2m}^{k + \ell} + 1) = 0$となるから，$\zeta_{2m}^{-k} = \zeta_{2m}^{-\ell}$または$\zeta_{2m}^{k + \ell} = 1$となるが，$k, \ell$の取り方によりどちらもあり得ない．それゆえ$F_m(X)$はsquare-freeである．

$F_{p^k}(X)$と$F_m(X)$は互いに素である

$\symbb{F}_q[X]$において
$$ F_n(X) \pmod{X^2 + 4} = \begin{cases} (-1)^{\frac{n - 1}{2}}n & (2 \nmid n)\\ (-1)^{\frac{n}{2} + 1} \frac{nX}{2} & (2 \mid n) \end{cases} $$
が成り立つ．

$n$に関する帰納法．$n = 0, 1$のときは明らか．
$n = 2m\ (m \in \symbb{Z})$であるとき，
\begin{align} F_{2m}(X) &= XF_{2m - 1}(X) + F_{2m - 2}(X)\\ &\equiv (-1)^{\frac{2m - 2}{2}}(2m - 1)X + (-1)^{\frac{2m - 2}{2} + 1}(2m - 2)X \cdot \frac{1}{2}\\ &= (-1)^{m - 1}(2m-1)X + (-1)^m(m - 1)X\\ &= (-1)^{m - 1}[(2m - 1) - (m - 1)]X\\ &= (-1)^{m + 1}mX\\ &= (-1)^{\frac{2m}{2} + 1}\frac{2mX}{2} \end{align}
となり，補題が成り立つ．
$n$が奇数であるときも同様に示される．

$n$を$p$と互いに素な正整数とするとき，$\symbb{F}_q[X]$で$F_n(X)$と$X^2 + 4$は互いに素である．

$F_n(X)$と$X^2 + 4$が共通因数を持つと仮定する．このとき，$F_n(X)$と$X^2 + 4$は共通因数$\alpha \in \symbb{F}_{q^2}$を持つ．しかし，補題9により，これはあり得ない．実際，例えば$2 \mid n$の場合，$F_n(\alpha) = (-1)^{\frac{n}{2} + 1}\frac{n}{2}\alpha \neq 0$とならなければならない．

主定理の証明

以上の補題を用いて，定理3の証明を行います．

（十分）命題6により，$F_{p^{ak}}(X) = (X^2 + 4)^{\frac{p^{ak} - 1}{2}}$であり，$p^a \equiv 1 \pmod{2j}$であるから，$\frac{p^{ak} - 1}{2} \equiv 0 \pmod{j}$．それゆえ$F_{p^{ak}}(X)$は$j$乗の元である．

（必要）$n = p^{ak+b}m\ (0 \le k < p, \gcd(p, m) = 1)$とする．このとき，命題6により
$$ F_n(X) = (X^2 + 4)^{\frac{p^{ak + b} - 1}{2}}F_m(X)^{p^{ak + b}} $$
が成り立つ．

$F_n(X)$が$\symbb{F}_q[X]$において$j$乗の元であるとする．

$b > 0$であると仮定する．このとき$p^{ak + b} = p^{ak}p^b \equiv p^b \pmod{2j}$であり，$p^b \not\equiv 1 \pmod{2j}$であるから，$(X^2 + 4)^{\frac{p^{ak + b} - 1}{2}}$は$j$乗の元ではない．よって，命題8，10により矛盾．それゆえ$b = 0$である．

$m > 1$であると仮定する．このとき，$p^{ak} \equiv 1 \pmod{2j}$であるから，$(X^2 + 4)^{\frac{p^{ak} - 1}{2}}$は$j$乗の元であるが，$F_{m}(X)^{p^{ak}}$はそうでない．しかし，仮定により$F_n(X) = (X^2 + 4)^{\frac{p^{ak} - 1}{2}}F_m(X)$は$j$乗の元であり，命題10に矛盾．それゆえ，$m = 1$である．

以上により，$F_{p^{ak + b}m}(X)$が$j$乗の元であるならば，$b = 0, m = 1$，すなわち$n = p^{ak}$である．