f(x) = 2x + 1 を mod 5 で繰り返し合成させるとどうなるか？

先日話題になった FF5の記事(1) や FF5の記事(2) の議論の中で

$f(x) = 2x + 1 \in \mathbb{F}_5[x]$

として

$a_n = f^n(a) = f\circ f\circ \cdots \circ f(a)$

なる数列について考えていました。

要するに、1次多項式 $f(x) = 2x+1$ を考えて $\bmod{5}$ で $f$ を繰り返し合成させるとどうなるか？という問題を考察していたわけです。

考えてみるとなかなか面白かったので、今日の記事ではこの問題について掘り下げてみようと思います。

フェルマーの小定理っぽい？

まずは、具体的に計算していきましょう。以下すべて有限体 $\mathbb{F}_5$ 上で考えます。

$\begin{align} f(x) &= 2x + 1 \\ f^2(x) &= f(2x + 1) = 2(2x + 1) + 1 = 4x + 3 \\ f^3(x) &= f(4x + 3) = 2(4x + 3) + 1 = 8x + 7 = 3x + 2 \\ f^4(x) &= f(3x + 2) = 2(3x + 2) + 1 = 6x + 5 = x \\ f^5(x) &= f(x) = 2x + 1 \\ \end{align}$

４行目あたりで「おっ」って思いますよね。結果だけまとめると

$\begin{align} f(x) &= 2x + 1 \\ f^2(x) &= 4x + 3 \\ f^3(x) &= 3x + 2 \\ f^4(x) &= x \\ f^5(x) &= 2x + 1 \\ f^6(x) &= 4x + 3 \\ f^7(x) &= 3x + 2 \\ f^8(x) &= x \\ f^9(x) &= 2x + 1 \\ &\vdots \end{align}$

これが繰り返されます。4回合成するごとに、 $f^{4n}(x) = x$ となっていることが観察できます。

つまり、

$f^4 = \text{id}$ （恒等写像）

が成り立つということです。

この現象はさながらフェルマーの小定理のようです。フェルマーの小定理とは、 $p$ を素数として $a \in \mathbb{F}_p^{\times}$ に対して

$a^{p-1} = 1$

が成り立つというものでした。状況はそっくりですね。

しかも、今回は $\mathbb{F}_5$ 上の多項式を考えているわけですから、 $p = 5$ とすると、指数が $p - 1 = 4$ となって、指数までも一致しています。

これは一体どのように解釈したらよいでしょうか。もしかして、有限体上の多項式の合成についても、フェルマーの小定理の類似が成り立つんでしょうか。

ここで頭に浮かぶのは、フェルマーの小定理の一般化です。群論的なフェルマーの小定理があったことを思い出しましょう。
tsujimotter.hatenablog.com

一般に群 $G$ を考えて、 $G$ の任意の元 $g$ に対し

$g^n = e$

が成り立ちます。ここで $n$ は $G$ の位数とし、 $e$ は $G$ の単位元です。

フェルマーの小定理は、有限体の乗法群 $\mathbb{F}_p^\times$ を $G$ としたときの系となっています。 $\mathbb{F}_p^\times$ の位数は $p - 1$ なので、たしかに一致しています。

さて、では今回のケースは、いったいどんな群になっているのでしょうか。

一般線形群 $\operatorname{GL}_2(\mathbb{F}_p)$

一般線形群とは、簡単にいってしまうと行列の群のことです。

2つの2次元正方行列

$A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}, \;\; B = \begin{pmatrix} e & f \\ g & h \end{pmatrix}$

は、掛け算した結果も2次元正方行列になります。

また、行列 $A$ は行列式 $ad - bc \neq 0$ のとき、そのときに限り逆行列 $A^{-1}$ を持ちます。したがって、「行列式が0でない2次元正方行列全体」は群をなします。係数を体 $K$ としたとき、この群を（2次元）一般線形群 $\operatorname{GL}_2(K)$ といいます。

今回考えたいのは、 $K = \mathbb{F}_p$ とした有限体係数の2次元正方行列の群 $\operatorname{GL}_2(\mathbb{F}_p)$ です。

この群が今回の問題にどう関係するのかという点について説明します。

$x \in \mathbb{F}_p$ に対して、 $\begin{pmatrix} a & b \\ c & d \end{pmatrix} \in \operatorname{GL}_2(\mathbb{F}_p)$ による作用を次の式で定義します：

$\displaystyle x \mapsto \begin{pmatrix} a & b \\ c & d \end{pmatrix}x := \frac{ax + b}{cx + d}$

いわゆる一次分数変換です。この変換が群作用になっていることは、

$\displaystyle \begin{pmatrix} a & b \\ c & d \end{pmatrix} \left(\begin{pmatrix} e & f \\ g & h \end{pmatrix}x\right) = \left(\begin{pmatrix} a & b \\ c & d \end{pmatrix}\begin{pmatrix} e & f \\ g & h \end{pmatrix}\right)x$

を確認してみればよいでしょう（やったことない人はぜひやってみよう）。

群の作用について慣れていない人もいるかと思います。要するに「 $x$ に行列 $B$ を作用させてから、行列 $A$ を作用させたもの」

$\displaystyle \begin{pmatrix} a & b \\ c & d \end{pmatrix} \left(\begin{pmatrix} e & f \\ g & h \end{pmatrix}x\right)$

は、「行列の積 $AB$ を先に計算しておいて、その $AB$ を $x$ に作用させたもの」

$\displaystyle \left(\begin{pmatrix} a & b \\ c & d \end{pmatrix}\begin{pmatrix} e & f \\ g & h \end{pmatrix}\right)x$

に一致するということです。

これらが一致するというのは、なかなか不思議です。一次分数変換というものが「うまく」定義されているなと思うのです。

さて、以上のように一次分数変換を定義すると、先の $f(x) = 2x + 1$ は

$\displaystyle \begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix}x = \frac{2x + 1}{0x + 1} = f(x)$

なる変換であったと捉えることができます。

$f(x)$ の $n$ 回合成は

$\displaystyle f^n(x) = \begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix}\circ \cdots \circ \begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix}\circ \begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix}x$

とみなすことができますが、群作用の性質より、行列を先に掛け算してもよいので

$\displaystyle f^n(x) = \begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix}^n x$

と行列の $n$ 乗を作用させたものに一致します。

つまり一次分数変換の視点で見ると、 $f(x)$ の $n$ 回合成とは「行列群 $\operatorname{GL}_2(\mathbb{F}_p)$ の元の $n$ 乗」にほかならないのです。

一次分数変換の視点を得ると、 $G = \operatorname{GL}_2(\mathbb{F}_p)$ としたときの群論のフェルマーの小定理を考えたくなるのは自然な発想でしょう。

この場合、 $\operatorname{GL}_2(\mathbb{F}_p)$ の単位元は単位行列 $I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ ですから、 $n =\#G$ として

$\displaystyle \begin{pmatrix} a & b \\ c & d \end{pmatrix}^{\# G} = I$

が成り立ちます。

そこで、 $\operatorname{GL}_2(\mathbb{F}_p)$ の位数を考えましょう。結果から言うと

$\begin{align} \# \operatorname{GL}_2(\mathbb{F}_p) &= (p^2 - 1)(p^2 - p) \\ &= (p-1)(p+1)p(p-1) \end{align}$

が答えです。これをどのように導くかについては以下の補足にて説明します。

（補足）線形変換は、ベクトル空間 $V$ の基底ベクトル $\langle u_1, u_2\rangle, \; \langle v_1, v_2\rangle$ の間の変換であることに着目します。基底 $\langle u_1, u_2\rangle$ を固定して、行き先の基底 $\langle v_1, v_2\rangle$ の組合せの総数を数えればよいでしょう。

$V = \mathbb{F}_p^2$ とします。まず、 $v_1$ としては $0$ でない $V$ のベクトルをとります。これは $p^2 - 1$ 通りあります。次に、 $v_1$ と一次独立なベクトル $v_2$ をとります。 $v_1$ に一次従属なベクトルは $p$ 個ですから、 $v_2$ として $p^2 - p$ 通りのベクトルがとれます。

したがって、行き先の基底 $\langle v_1, v_2\rangle$ の総数は $(p^2 - 1)(p^2 - p)$ 通りです。

$p = 5$ とすると、

$\# \operatorname{GL}_2(\mathbb{F}_5) = (5 - 1)\cdot (5 + 1)\cdot 5\cdot (5-1) = 4^2\cdot 5 \cdot 6$

が得られます。群論のフェルマーの小定理により

$\displaystyle \begin{pmatrix} a & b \\ c & d \end{pmatrix}^{4^2\cdot 5 \cdot 6} = I$

が成り立ちます。

したがって、 $G$ の任意の元 $g$ の位数は $\# G$ の約数となります。よって $4^2\cdot 5 \cdot 6$ の約数が $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$ の位数になります。

冒頭で述べた通り

$\begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix}^4 = I$

ですから、 $\begin{pmatrix} 2 & 1 \\ 0 & 1 \end{pmatrix}$ の位数は $4$ だったわけです。

$4^2\cdot 5 \cdot 6$ はたしかに $4$ を約数に持ちますから、理屈は通ってますね。

というわけで、一旦まとめます。

$f(x) = \frac{2x + 1}{0x + 1}$ の $\operatorname{GL}_2(\mathbb{F}_5)$ における位数が $4$ だったのは、 $\operatorname{GL}_2(\mathbb{F}_5)$ の位数が $4^2\cdot 5 \cdot 6$ で、 $4$ はその約数だから、というのがここまでの結論です。

アフィン群

ここまでの議論で $f(x) = 2x + 1$ の問題について理解が深まった気がしますが、まだ不満は残ります。

位数が $4$ であることが示したかったことですが、 $4\cdot 5^2 \cdot 6$ の約数であることまでしか突き止められませんでした。これは、 $\operatorname{GL}_2(\mathbb{F}_p)$ という群が大き過ぎたのが原因です。

実際に考えたいのは、 $\operatorname{GL}_2(\mathbb{F}_p)$ の中でも特に

$\begin{pmatrix} a & b \\ 0 & 1 \end{pmatrix}$

の形の元だけです。したがって、このような元のなす $\operatorname{GL}_2(\mathbb{F}_p)$ の部分群を考えたくなります。これをアフィン群といいます。

一般に体 $K$ に対してアフィン群 $\operatorname{Aff}(K)$ を、 $f(x) = ax + b$ という形の $K$ 係数多項式で、 $x \mapsto f(x)$ が逆変換 $f^{-1}$ を持つもの全体のなす群として定義しましょう。これは明らかに $\operatorname{GL}_2(K)$ の部分群です。

$f(x) = ax + b$ が逆行列を持つ条件はなんでしょうか。 $f(x) = ax + b, \; g(x) = cx + d$ を考えて、この合成 $f \circ g$ を考えます。

$\begin{align} f\circ g(x) &= a(cx + d) + b \\ &= acx + (b + ad) \end{align}$

$f\circ g = \operatorname{id}$ となる必要十分条件は

$ac = 1$ かつ $b + ad = 0$

ですが、このような $c, d$ が存在する条件は $a \in K^\times$ であることがわかります。 $a \in K^\times$ であれば、 $a^{-1}$ が存在するので、 $c = a^{-1}, \; d = -a^{-1}b$ として上記の条件を満たします。逆に $ac = 1$ を満たすなら $a^{-1}$ が存在することもわかります。

ここで、 $K = \mathbb{F}_p$ とすると、 $f(x) \in \operatorname{Aff}(\mathbb{F}_p)$ は、 $f(x) = ax + b$ という形をしていて、 $a \in \mathbb{F}_p^\times, \; b \in \mathbb{F}_p$ を満たすもの全体であるとわかりました。

もう少しだけ、 $\operatorname{Aff}(\mathbb{F}_p)$ の群構造について調べてみましょう。アフィン変換 $f(x), g(x) \in \operatorname{Aff}(\mathbb{F}_p)$ の合成の式

$f\circ g(x) = a(cx + d) + b = acx + (b + ad)$

を思い出すと、 $(a, b), \; (c, d) \in \mathbb{F}_p^\times \times \mathbb{F}_p$ に対して

$(a, b)\times (c, d) = (ac, \; b + ad)$

という積の構造が入っていると考えることができます。ぱっと見はよくわからない式ですね。

ここで少し頭を柔軟にして、上の式を解釈したいと思います。 $ad$ という式は、乗法群 $\mathbb{F}_p^\times$ の元 $a$ が、加法群 $\mathbb{F}_p$ の元 $d$ に

$d^a := ad$

のように作用していると考えます。 $(ac, \; b + ad)$ は、第１成分は乗法群 $\mathbb{F}_p^\times$ の元 $a, c$ 同士の単純な積、第２成分は加法群 $\mathbb{F}_p$ の元 $b, d$ 同士の単純な演算 $b + d$ の $d$ の方に $a$ が作用したもの、と捉えることができます。

ごちゃごちゃ言ってしまいましたが、要するにこれは半直積 $\mathbb{F}_p^\times \ltimes \mathbb{F}_p$ の定義そのものであるというのがいいたかったことです。

すなわち、アフィン群との群同型

$\operatorname{Aff}(\mathbb{F}_p) \simeq \mathbb{F}_p^\times \ltimes \mathbb{F}_p$

が成り立つということです。

さて、この同型より $\mathbb{F}_5^\times \ltimes \mathbb{F}_5$ の位数が $4\cdot 5$ であることから、 $f(x) = ax + b$ の $\operatorname{Aff}(\mathbb{F}_p)$ における位数が $4\cdot 5$ の約数であることがわかります。

もっと具体的に計算する

さて、上の同型 $ax + b \mapsto (a, b)$ を使って $\operatorname{Aff}(\mathbb{F}_5)$ の元を $\mathbb{F}_5^\times \ltimes \mathbb{F}_5$ に移して具体的に計算してみましょう。

$2x + 1 \mapsto (2, 1)$ ですから、そのべき乗は次のようになります：

$f^1(x) = 2x + 1 \;\; \mapsto \;\; (2, 1)$

$f^2(x) = 4x + 3 \;\; \mapsto \;\; (4, 3)$

$f^3(x) = 3x + 2 \;\; \mapsto \;\; (3, 2)$

$f^4(x) = 1x + 0 \;\; \mapsto \;\; (1, 0)$

最初に考察したように $4$ 回で単位元 $(1, 0)$ に戻るというわけですね。

ここで、第１成分に着目すると、

$\begin{align} 2^1 &= 2, \\ 2^2 &= 4, \\ 2^3 &= 3, \\ 2^4 &= 1 \end{align}$

と回って $1$ に到達しています。まさに（元々の） $\mathbb{F}_5^\times$ のフェルマーの小定理そのものになっています！

$(a, b)$ の第１成分に着目すると、 $(a, b)^n = (a^n, \ast)$ と単純にかけるというのがポイントのようです。そこでは、乗法群 $\mathbb{F}_p^\times$ のフェルマーの小定理がそのまま適用できます。

第２成分はどうなっているでしょうか。具体的に計算すると以下のようになります。

$\begin{align} (a, b)^1 &= (a, b) \\ (a, b)^2 &= (a^2, b(1 + a)) \\ (a, b)^3 &= (a^3, b(1 + a + a^2)) \\ (a, b)^4 &= (a^4, b(1 + a + a^2 + a^3)) \end{align}$

どうやら規則性がありそうです。

$a^4 = 1$ より、第２成分も $4$ 回ぴったりで $0$ に戻ってくれば $(a, b)$ の位数が $4$ の約数になるわけですが、そのようなことが一般に起こり得るか考えてみましょう。

つまり

$b(1 + a + a^2 + a^3) = 0$

$\mathbb{F}_p$ は体（つまり整域）より

$b = 0$ または $1 + a + a^2 + a^3 = 0$

が、 $(a, b)^4 = (1, 0)$ である必要十分条件です。

$a \neq 1$ のとき、 $1 + a + a^2 + a^3 = (1 - a^4)(1 - a)^{-1}$ が言えます。 $\mathbb{F}_5^\times$ のフェルマーの小定理により $a^4 = 1$ ですから、 $1 + a + a^2 + a^3 = 0$ が成り立ちます。

逆に $1 + a + a^2 + a^3 = 0$ のとき、 $a \neq 1$ が成り立ちます。
（対偶 $a = 1 \; \Longrightarrow \; 1 + a + a^2 + a^3 \neq 0$ より）

よって、 $(a, b)^4 = (1, 0)$ である必要十分条件

$a \neq 1$ または $b = 0$

が得られました。これは、アフィン変換 $f(x) = ax+b$ の $\operatorname{Aff}(\mathbb{F}_p)$ における位数が $4$ の約数であるような必要十分条件でもあります。

ほぼ大半の位数が $1, 2, 4$ のいずれかになるということですね。面白い！

また、 $a = 1, \; b\neq 0$ のケースについては、 $f(x) = x + b$ という形になるので、位数は $5$ となることがわかります。

これまでの議論は、一般の $p$ においても成り立ちますから次の定理がいえるでしょう。

定理（ $\operatorname{Aff}(\mathbb{F}_p)$ におけるフェルマーの小定理）

$p$ を素数とし， $f(x) = ax + b$ を $\mathbb{F}_p$ 係数の1次多項式とする．

(i) $a \neq 1$ または $b = 0$ のとき，またそのときに限り次が成り立つ：

$f^{p-1} = \operatorname{id}$

(ii) $a = 1$ かつ $b \neq 0$ のとき，またそのときに限り次が成り立つ：

$f^{p} = \operatorname{id}$

というわけで、 $f(x) = 2x + 1$ の $\operatorname{Aff}(\mathbb{F}_5)$ における位数が $4$ だったのは、乗法群 $\mathbb{F}_5^\times$ の位数が $4$ であり、さらに $f(x)$ の1次の係数 $2$ が $1$ ではないから、というのが結論です。

一般に $ax + b$ という変換を考えたとしても、 $a \neq 1$ または $b = 0$ であれば、同じように位数が $4$ の約数になるということもわかってしまいました。 $f(x) = 2x + 1$ が位数4になったのは偶然ではなかったというわけですね。

終わりに

今回は、 $f(x) = 2x + 1$ という変換の $\bmod{5}$ における合成が、なんだかフェルマーの小定理っぽいなというところから始まって、その位数について２通りの方法で考察しました。実際に、ほとんど元々のフェルマーの小定理にそっくりな定理が成り立つことがわかりました。なかなか面白い問題でしたね。

一般線形群という視点、さらに $f(x)$ の属する群がアフィン群という部分群に相当して、その群構造が半直積 $\mathbb{F}_5^\times \ltimes \mathbb{F}_5$ になることについては、unaoyaさんに教えていただきました（今回の記事のほとんど全部ですね）。ありがとうございます。

群の半直積については、群論を勉強する中で登場した記憶はあるのですが、今回の記事をまとめるまではなんだかよくわかっていませんでした。半直積の構造が、アフィン群という実に自然な対象の中に現れるということに驚きました。

なお、アフィン群というと、 $n$ 次元ベクトル空間 $V$ のアフィン変換 $x \mapsto Ax + b$ の群を指すことが一般的です。今回は $n = 1$ の特殊ケースであることを補足しておきます。