Twitterの問題の解説 ((n^2-2)^2-2…≡n modp

こんにちは.

今回は, Twitterで出した以下の問題の解説をしようと思います.
${}$

${}$

方針

$f(X)=X^2-2$, $F(X)=f(f(f(f(f(X)))))-X$として, 各素数$p$に対して有限体$\Fp$での$F$の根の個数が分かれば良いです.

$f$が2倍角の公式に似ていることに着目すると, $f(\zeta+\zeta^{-1})=\zeta^2+\zeta^{-2}$となることがわかるので, $F(\zeta+\zeta^{-1})=\zeta^{32}+\zeta^{-32}-\zeta-\zeta^{-1}$となり, $\zeta$を$1$の$31$乗根とすると$\zeta+\zeta^{-1}$は$F$の根になっていることが分かります.

つまり, 元の方程式は, 32倍角の公式で元に戻る値は, という問題なのです. 実際, $\mathbb{R}$上では, $\zeta_{31}+\zeta_{31}^{-1}=2\cos\frac{2\pi}{31}$は$F$の根になっています.

このように具体的に解は構成できるように見えますが, しかし例えば$p=31$のときは$1$の原始$31$乗根は存在しないため, 困ってしまいます.

そこで, まず$\bar{\mathbb{Q}}$で解をとり, それを各$\Fp$に落とすという方針で, まとめて議論していきます.

${}$

解答

${}$

一般に $f(X)=X^2-2,\ F(X)=\underbrace{f(f(\cdots f}_n(X)))-X$ として, $F$ の$\Fp$での根の数を調べる.

まず$\bar{\mathbb{Q}}$での根を求めると,

$$ F(\zeta+\zeta^{-1})=\zeta^{2^n}+\zeta^{-2^n}-(\zeta+\zeta^{-1})$$

から, $\zeta$が$1$の$2^n-1$乗根か$2^n+1$乗根ならこでは$0$より,
$$ S=\{2\}\cup\{\zeta_{2^n-1}^i+\zeta_{2^n-1}^{-i}\}_{1\leq i\leq\frac{2^n-2}2}\cup\{\zeta_{2^n+1}^i+\zeta_{2^n+1}^{-i}\}_{1\leq i\leq\frac{2^n}2}$$
の$2^n$個が$F$の$\bar{\mathbb{Q}}$での根である. ここで一般に$\zeta_k$は$1$の原始k乗根を表す. $S$の表示を整理して
$$ S=\{2\}\cup\{\ \zeta_k^i+\zeta_k^{-i}\mid \ k|2^n\pm1,\ k\neq1,\ \gcd(i,k)=1,\ 0< i<\tfrac k2\}$$
としておく. $N=(2^n+1)(2^n-1)$として, $S$は$\mathbb{Q}[\zeta_N]$の整数環$\Z[\zeta_N]$に含まれている.
${}$

代数的整数論により, $\Z[\zeta_N]$において素イデアル分解を$(p)=\prod_{i=1}^g\mathfrak p_i^e$として,
$$ \psi:\Z[\zeta_N]\twoheadrightarrow\Z[\zeta_N]/\mathfrak{p}_1\stackrel{\sim}{\longrightarrow}\F_{p^f}$$
とおくと, $\psi(S)\cap\Fp$の要素数が, $F$の$\Fp$での根の数である.

$\Z[\zeta_N][X]\twoheadrightarrow\F_{p^f}[X]$による$F$の像を考えれば, （$\F_{p^f}$では重根があるかもしれないが）$F$の像の根は, $F$の根の像に一致する. 従って, 根の像$\psi(S)$と$\F_p$の共通部分が$\Fp$での根全体となる.

${}$

$\psi(S)$を調べるためには, $N$の素因数$q$に対して$\psi(\zeta_{q^m})$を調べればよい.

（$q=p$のとき：）　$(\zeta_{p^m}-1)^{p^m}\in(p)\subset \mathfrak{p}_1$ より$ \zeta_{p^m}-1\in\mathfrak{p}_1$なので$\psi(\zeta_{p^m})=1$.

（$q\neq p$ のとき：）　$\psi(\zeta_{q^m})^{q^{m-1}}\neq1$を示せばよい. もしそうでなければ$\zeta_q-1\in \mathfrak{p}_1$だが, $( \zeta_q-1)^q\in \mathfrak{p}_1 \cap (q)=0$で矛盾. □

${}$

補題より, $\psi(\zeta_k)=\zeta_{k'}$（ただし$k=p^ak'$, $k'$は$p$の倍数でない）とわかる. これにより$S$の像を計算すると,

$$ S=\{2\}\cup\{\ \zeta_k^i+\zeta_k^{-i}\mid \ k|2^n\pm1,\ k\neq1,\ \gcd(i,k)=1,\ 0< i<\tfrac k2\}$$
$$ \psi(S)=\{2\}\cup\{\ \zeta_k^i+\zeta_k^{-i}\mid \ p\!\!\not{}| \, k|\,2^n\pm1,\ k\neq1,\ \gcd(i,k)=1,\ 0< i<\tfrac k2\}$$

である.
${}$

最後に$\zeta_k^i+\zeta_k^{-i}\in \Fp$となる条件を求める.

$$ \begin{align*}\zeta_k^i+\zeta_k^{-i}\in \Fp\iff& \zeta_k+\zeta_k^{-1}\in \Fp \\ \iff& (\zeta_k+\zeta_k^{-1})^p=\zeta_k+\zeta_k^{-1}\\ \iff& \zeta_k^p+\zeta_k^{-p}=\zeta_k+\zeta_k^{-1}\\ \iff& \{\zeta_k^p,\zeta_k^{-p}\}=\{\zeta_k,\zeta_k^{-1}\}\\ \iff& \zeta_k^{p\pm1}=1\\ \iff& p\equiv\pm1\mod k \end{align*}$$

ただし, 3行目から4行目への変形では, 和と積が等しい2数は集合として等しい（解と係数の関係）を用いた.

同様の理由から$\zeta_k^i+\zeta_k^{-i}$たちは全て異なることと合わせて,

$$ \#(\psi(S)\cap\Fp )=1+\sum_{\begin{gather*}k|2^n\pm1,\ k\neq1\\p\equiv\pm1\mod k\end{gather*}} \frac12\p(k)$$

により, 各$p$に対する$n$の個数が計算できる.

${}$

（ただし, これで分かるのは$\Fp$での根の個数なのに対し, 元の条件は$0< n< p$だったので, $n=0$が解の場合だけ特殊であるが, そのような$p$は$p=2$だけである. このとき$n$の可能性は1つである.）

従って, 求める答えは
$$ 1+\sum_{2< p<100} \bigg(1+\sum_{\begin{gather*}k|32\pm1,\ k\neq1\\p\equiv\pm1\mod k\end{gather*}} \frac12\p(k) \bigg)$$

である.

${}$

各$p$に対し, $\sum$の条件を満たす$k$は何か考える. $k$の可能性は$k=3,11,31,33$のみなので, それぞれが$p\equiv \pm1\mod k$を満たす$p$を求めると,

$k=3$が満たす：全ての$p>3$
$k=11$が満たす：$p=23,43,67,89$
$k=31$が満たす：$p=61$
$k=33$が満たす：$k=67$

となる. 従って, 解$n$の個数は
${}$
$p=23,43,89$では $1+\sum_{k=3,11}\frac12\p(k)=7$個

$p=61$では $1+\sum_{k=3,31}\frac12\p(k)=17$個

$p=67$では $1+\sum_{k=3,11,33}\frac12\p(k)=17$個
${}$
であり, その他の$p>3$では$1+\sum_{k=3}\tfrac12\varphi(k)=2$個となる. $p=2,3$では1つである.

100未満の素数は25個であることから, 答えは$1+1+7\times3+17+17+(25-7)\times2=$$93$個である.
${}$

補足

最初に2倍角の公式の5回合成だと見えて, 1の31乗根と33乗根を考えれば良いと分かっても, $\F_{31}$などでは重解が出てよく分からなくなってしまうことから, 少し工夫が必要という問題でした.

今回の方程式の$\Fp$での解の個数は, $\mathrm{mod}\ 31,33$で決まっているので, $p$を$31\times 33$で割った余りで個数が分類できるということになります. では, 一般に方程式の$\Fp$での解の個数が$p$を何かで割った余りで分類できるかというと, 常にそうとは限りません.

実は, 類体論により, 方程式の$\mathbb{Q}$上分解体がAbel拡大であればそうであることが示せますが, Abelでない場合にはmodで決まらない例があります.

今回の例から, 解が1の冪根を使って表せる場合は一般に$p$のmodで個数が決まりそうだなという気がしますが, Abel拡大の場合は類体論と密接に関係しているKronecker-Weberの定理より必ず解は1の冪根を使って表せるので, 感覚的には納得がいきますね.

${}$

それでは, 読んでくださった方, ありがとうございました.
${}$

${}$