2017-01-04

高木関数

定理解説

今、目の前に高木貞治博士の論文集があります。高木貞治博士が28歳ぐらいのときに出版された論文

T. Takagi, A simple example of a continuous function without derivative, Proc. Phys. Math. Japan, (1903) Vol. 1, pp. 176-177.

は一ページ半に満たないものですが(Proceeding)、最初にそのような当時の感覚では病的な関数を発見したWeierstrassの例(1872年)に比べて、至る所微分不可能な連続関数の簡単な例を与えた有名な論文です。この高木関数とか高木曲線として有名な関数を、できるだけ博士が論文中で使用している記号のまま紹介したいと思います。

f:id:integers:20170103004248p:plain:w400

Dirichlet関数(高数美物語、アジマティクス、インテジャーズ)は至る所不連続な関数で有名な関数であり、それは当然至る所微分不可能ですが、Weierstrassの例や高木博士の例はある意味一段階レベルアップした病的な関数です。超有名ではありますが、Dirichlet関数のように大学の授業で必ず習うというわけではないです。あと、フラクタルになっています。

論文に沿った紹介

$[0, 1]$ 区間の実数 $t$ を

$\displaystyle t=\sum^n\frac{c_n}{2^n}$

と $2$ 進展開する(ただし、 $c_n$ は $0$ または $1$ )。各正整数 $n$ に対して $\tau_n$ と $\tau'_n$ を

$\begin{align} \tau_n &= \frac{c_n}{2^n}+\frac{c_{n+1}}{2^{n+1}}+\frac{c_{n+2}}{2^{n+2}}+\cdots \\ \tau'_n &= \frac{1}{2^{n-1}}-\tau_n\end{align}$

と定める(これは $t$ に依存して定まるが、 $t$ の $2$ 進展開が二通りある場合であってもその展開の仕方には依らない)。そうして、 $\gamma_n$ を

$\displaystyle \gamma_n = \begin{cases}\tau_n & (c_n=0)\\ \tau'_n & (c_n=1)\end{cases}$

によって定める(これも $t$ のみに依存する)。このとき、 $[0, 1]$ 区間上の関数 $f(t)$ を

$\displaystyle f(t) = \sum_{1, \infty}^n\gamma_n$

によって定義する*1(これが高木関数と呼ばれているもの)。

$\pi_n$ および $\nu_n$ をそれぞれ $c_1, c_2, \dots, c_n$ における $0$ の個数および $1$ の個数とし( $\pi_n+\nu_n=n$ )、 $a_n$ を

$\displaystyle a_n = \begin{cases}\nu_n & (c_n=0)\\ \pi_n & (c_n=1)\end{cases}$

と定めると、

$\displaystyle f(t) = \sum\frac{a_n}{2^n}$

と書けることが容易にわかる(①)。 $f(t)$ は $[0, 1]$ 上定義される連続関数である(②)。これが、至るところ微分不可能であることは特別な $\Delta t$ に対する $\displaystyle \frac{\Delta f}{\Delta t}$ を計算することによって証明できる：

まず、 $c_n=0, \$ $\displaystyle \Delta t = \frac{1}{2^n}$ の場合は

$\displaystyle \frac{\Delta f}{\Delta t} = \pi_n-\nu_n-2^{n+1}\tau_{n+1}$

が成り立つ(③)。また、 $c_{n-1}=0, \ c_n=0, \$ $\displaystyle \Delta t = \frac{1}{2^n}$ の場合は

$\displaystyle \frac{\Delta f}{\Delta t} = \pi_n-\nu_n$

である(④)。

従って、 $c_n=0, \ c_{n+1}=0$ のときは、 $\displaystyle \Delta t=\frac{1}{2^n}$ のときの $\displaystyle \frac{\Delta f}{\Delta t}$ の値と $\displaystyle \Delta t=\frac{1}{2^{n+1}}$ のときの $\displaystyle \frac{\Delta f}{\Delta t}$ の値の差は $1-2^{n+1}\tau_{n+2}$ で与えられる(⑤)。

また、 $c_n=0, \ c_{n+1}=1$ のときは、 $\displaystyle \Delta t=\frac{1}{2^n}$ のときの $\displaystyle \frac{\Delta f}{\Delta t}$ の値と $\displaystyle \Delta t=\frac{1}{2^{n+1}}$ のときの $\displaystyle \frac{\Delta f}{\Delta t}$ の値の差は $2^{n+1}\tau_{n+2}$ で与えられる(⑤)。

$n$ はいくらでも大きくできるので、これより微分不可能性が従う(⑥)。

補足

①(高木の公式)の補足
$\overline{c_n}=1-c_n$ と書くことにします。 $c_n=0$ のときは、 $j \leq n$ なる $j$ に対して

$\displaystyle \gamma_j = \tau'_j = \frac{\overline{c_j}}{2^j}+\cdots +\frac{\overline{c_n}}{2^n}+\cdots$

であるときに $a_n$ に寄与します( $\overline{c_n}=1$ )。こうなるのは $c_j=1$ のときなので、 $a_n$ は $c_1, \dots, c_{n}$ までの $1$ の個数 $\nu_n$ に等しいことがわかります。

$c_n=1$ のときは、 $j \leq n$ なる $j$ に対して

$\displaystyle \gamma_j=\tau_j = \frac{c_j}{2^j}+\cdots +\frac{c_n}{2^n}+\cdots$

であるときに $a_n$ に寄与します。こうなるのは $c_j=0$ のときなので、 $a_n$ は $c_1, \dots, c_n$ までの $0$ の個数 $\pi_n$ に等しいことがわかります。

距離関数を使った表示
高木関数を $T(t)$ と書くことにしましょう。一般的な関数を表す記号である $f(t)$ よりは固有名詞っぽくなります。実数 $t$ に対して、 $t$ と $t$ に一番近い整数の距離を $\langle \! \langle t \rangle \! \rangle$ と書くことにします(これはLagariasさんが使っている記号です。文献によって記号が異なります*2 )。 $t \in [0, 1]$ に対しては $\displaystyle \gamma_n=\frac{\langle \! \langle 2^{n-1}t \rangle \! \rangle}{2^{n-1}}$ が成り立ち、

$\displaystyle T(t) = \sum_{n=1}^{\infty}\frac{\langle \! \langle 2^{n-1}t \rangle \! \rangle}{2^{n-1}}= \sum_{n=0}^{\infty}\frac{\langle \! \langle 2^{n}t \rangle \! \rangle}{2^{n}}$ ー⑦

と簡潔に表されることがわかります。これは明らかに一様収束する級数ですが、

$\displaystyle [0, 1] = \bigcup_{k=0}^{2^{n+1}-1}\left[ \frac{k}{2^{n+1}}, \frac{k+1}{2^{n+1}}\right]$

と分割すると、 $\displaystyle t \in \left[ \frac{k}{2^{n+1}}, \frac{k+1}{2^{n+1}}\right]$ に対して

$\displaystyle \frac{\langle \! \langle 2^{n}t \rangle \! \rangle}{2^{n}} = \begin{cases}t-\frac{k}{2^{n+1}} & (k\in 2\mathbb{Z}) \\ \frac{k+1}{2^{n+1}}-t & (k+1 \in 2\mathbb{Z}) \end{cases}$ ー⑧

と書けるので、 $\displaystyle \frac{\langle \! \langle 2^{n}t \rangle \! \rangle}{2^{n}}$ はギザギザした $[0, 1]$ 上連続な関数であり、従って $f(t)$ も連続であることがわかります(これで②の理由がわかりました)。

高木関数のアニメーションを載せているサイトを見つけたのでリンクを貼っておきます：高木関数

有理性
高木関数は有理数を有理数に写す関数です。つまり、 $t$ が有理数ならば $T(t)$ も有理数になります。実際、 $t$ が有理数ならば $2^nt$ の既約分数表示における分母の取り得る値は $n$ を動かしたときに有界なので、 $\langle \! \langle 2^nt\rangle \! \rangle$ は周期的になります。よって、⑦の表示と等比級数の和の公式から $T(t)$ が有理数になることがわかります。

高木関数の値域
$T(t)$ の値の取り得る範囲は $[0, 2/3]$ です。 $T(t) \geq 0$ , $T(0)=T(1)=0$ , $t \in (0, 1)$ に対して $T(t) > 0$ であることは定義からすぐわかります。 $x \geq 0$ に対して

$\displaystyle \langle \! \langle x \rangle \! \rangle + \frac{1}{2} \langle \! \langle 2x \rangle \! \rangle \leq \frac{1}{2}$

であることは $x$ の小数部分について丁寧に４通りに場合分けすれば示せるので、⑦において和を二つずつペアにしてこの不等式を適用すると

$\displaystyle T(t) \leq \frac{1}{2}+\frac{1}{2^3}+\frac{1}{2^5}+\cdots = \frac{2}{3}$

と評価できます。任意の非負整数 $n$ に対して $\langle \! \langle 2^n\frac{1}{3} \rangle \! \rangle=\frac{1}{3}$ なので、 $T(\frac{1}{3})=\frac{2}{3}$ です。

③の補足
$t$ を明示する場合は $\tau_n(t)$ のように表示することにします(明示しなければ $t$ の場合)。 $c_n=0, \$ $\displaystyle \Delta t = \frac{1}{2^n}$ とします。

$k \geq n+1$ のときは $\tau_k(t) = \tau_k(t+\Delta t)$ なので、 $\gamma_k(t) = \gamma_k(t+\Delta t)$

$c_n=0$ なので、 $\gamma_n(t)=\tau_n(t) = \tau_n$

$c_n(t+\Delta t) = 1$ なので

$\displaystyle \gamma_n(t+\Delta t) = \tau'_n(t+\Delta t) = \frac{1}{2^{n-1}}-\tau_n(t+\Delta t) = \frac{1}{2^{n-1}}-\left( \frac{1}{2^n}+\tau_n(t) \right) = \frac{1}{2^n}-\tau_n$

$k \leq n-1$ のときは $\displaystyle \tau_k(t+\Delta t) = \frac{1}{2^n}+\tau_k(t)$ なので、

$c_k=0$ ならば

$\displaystyle \gamma_k(t+\Delta t) = \tau_k(t+\Delta t) = \frac{1}{2^n}+\tau_k(t) = \frac{1}{2^n}+\gamma_k(t)$

$c_k=1$ ならば

$\begin{align} \gamma_k(t+\Delta t) &= \tau'_k(t+\Delta t) = \frac{1}{2^{k-1}}-\tau_k(t+\Delta t) = \frac{1}{2^{k-1}}-\frac{1}{2^n}-\tau_k(t) \\ &=\tau'_k(t) -\frac{1}{2^n} = \gamma_k(t) - \frac{1}{2^n}\end{align}$

以上より

$\displaystyle \Delta f = f(t+\Delta t)-f(t) = \frac{\pi_{n-1}}{2^n}-\frac{\nu_{n-1}}{2^n}+\frac{1}{2^n}-2\tau_n$

$\pi_n=\pi_{n-1}+1, \ \nu_n=\nu_{n-1}, \ \tau_{n+1}=\tau_n$ なので③が得られました。

④の補足
これは計算が合わないというか、③を考えるとおかしいのですが、 $c_n=1$ の誤植です。 $c_{n-1}=0, \ c_n=1, \$ $\displaystyle \Delta t = \frac{1}{2^n}$ とします。このときも $k \leq n$ のときを考えれば十分です。 $c_{n-1}(t+\Delta t) = 1$ 、 $c_n(t+\Delta t) = 0$ に注意します。

$\displaystyle \gamma_n(t) = \tau'_n(t) = \frac{1}{2^{n-1}}-\tau_n(t), \$ $\displaystyle \gamma_n(t+\Delta t) = \tau_n(t+\Delta t) = \tau_n(t)-\frac{1}{2^n}$ なので、

$\displaystyle \Delta \gamma_n = 2\tau_n-\frac{3}{2^n}$

$\gamma_{n-1}(t) = \tau_{n-1}(t) = \tau_n$ 、

$\displaystyle \gamma_{n-1}(t+\Delta t) = \frac{1}{2^{n-2}}-\tau_{n-1}(t+\Delta t) = \frac{1}{2^{n-2}}-\left( \frac{1}{2^{n-1}}+\tau_n(t)-\frac{1}{2^n} \right) = \frac{3}{2^n}-\tau_n$

$k \leq n-2$ ならば

$\displaystyle \tau_k(t+\Delta t) = \tau_k(t) -\frac{1}{2^n}+\frac{1}{2^{n-1}} = \tau_k(t) + \frac{1}{2^n}$

以上より

$\displaystyle \Delta f = \frac{\pi_{n-2}}{2^n}-\frac{\nu_{n-2}}{2^n} +\left( \frac{3}{2^n}-2\tau_n\right) + \left( 2\tau_n-\frac{3}{2^n} \right)$

$\pi_n = \pi_{n-2}+1, \ \nu_n = \nu_{n-2}+1$ より④が得られました。

⑤の補足
$c_n=0, \ c_{n+1}=0$ のときは③から

$\left. \frac{\Delta f}{\Delta t} \right|_{\Delta t = \frac{1}{2^{n+1}}} - \left. \frac{\Delta f}{\Delta t} \right|_{\Delta t = \frac{1}{2^{n}}} = (\pi_{n+1}-\nu_{n+1}-2^{n+2}\tau_{n+2}) - (\pi_n-\nu_n-2^{n+1}\tau_{n+1})$

$\pi_{n+1}=\pi_n+1, \ \nu_{n+1}=\nu_n, \ \tau_{n+2}=\tau_{n+1}$ なので、これは $1-2^{n+1}\tau_{n+2}$ に等しいことがわかります。

$c_n=0$ 、 $c_{n+1}=1$ のときは③、④から

$\left. \frac{\Delta f}{\Delta t} \right|_{\Delta t = \frac{1}{2^{n+1}}} - \left. \frac{\Delta f}{\Delta t} \right|_{\Delta t = \frac{1}{2^{n}}} = (\pi_{n+1}-\nu_{n+1})-(\pi_n-\nu_n-2^{n+1}\tau_{n+1})$

$\pi_{n+1}=\pi_n$ 、 $\nu_{n+1}=\nu_n+1$ 、 $\displaystyle \tau_{n+2} = \tau_{n+1}-\frac{1}{2^{n+1}}$ なので、これは $2^{n+1}\tau_{n+2}$ に等しいです。以上で⑤が確認できました。

⑥の補足
微分係数 $\displaystyle \lim_{\Delta t \to 0}\frac{\Delta f}{\Delta t}$ が存在すれば、

$\displaystyle \left. \frac{\Delta f}{\Delta t} \right|_{\Delta t = \frac{1}{2^{n+1}}} - \left. \frac{\Delta f}{\Delta t} \right|_{\Delta t = \frac{1}{2^{n}}}$

は $n$ を大きくするといくらでも小さくなっていく必要があります。例えば $t$ の $2$ 進展開に $\cdots 000 \cdots$ という部分が無数にあったとしましょう。このとき、 $000$ の部分を $\displaystyle \frac{c_n}{2^n}+\frac{c_{n+1}}{2^{n+1}}+\frac{c_{n+2}}{2^{n+2}}$ とすれば、⑤より

$\displaystyle \left. \frac{\Delta f}{\Delta t} \right|_{\Delta t = \frac{1}{2^{n+1}}} - \left. \frac{\Delta f}{\Delta t} \right|_{\Delta t = \frac{1}{2^{n}}} = 1-2^{n+1}\tau_{n+2} \geq \frac{1}{2}$

なので微分係数を持ち得ないことがわかります。 $t$ の $2$ 進展開の様子で幾つかの場合分けをすることにより⑤を使って $f(t)$ は至る所微分不可能であることを確認できます。ただ、私の確認した方法が高木博士の意図した方法である自信が全くないので、ここでは別の導出方法を解説することにします。

至るところ微分不可能であることのBillingsleyによる証明
$t \in [0, 1)$ *3は正整数 $n$ 毎に或る整数 $0 \leq k \leq 2^n-1$ が存在して

$\displaystyle \frac{k}{2^n} \leq t < \frac{k+1}{2^n}$

と挟むことができる。 $u_n=\frac{k}{2^n}$ 、 $v_n=\frac{k+1}{2^n}$ とおこう。このとき、

$\displaystyle \frac{T(v_n)-T(u_n)}{v_n-u_n} = \sum_{j=0}^{n-1}\frac{\frac{\langle \! \langle 2^jv_n \rangle \! \rangle}{2^j}-\frac{\langle \! \langle 2^ju_n \rangle \! \rangle}{2^j}}{v_n-u_n}$

であり*4、この和の中身は傾きを表しているが、それは⑧からわかるように $\pm 1$ である。従って、 $t$ を固定したときに

$\displaystyle \lim_{n \to \infty}\frac{T(v_n)-T(u_n)}{v_n-u_n}$

は存在しない。ところが、高木関数の $t$ での微分係数が存在すれば、上記極限が存在して同じ値に収束するはずである(このことは簡単な $\varepsilon$ - $\delta$ 論法で示せる)。すなわち、高木関数は至る所微分不可能である。 Q.E.D.

関数等式

定理高木関数は次のような関数等式を満たす：

$T(t) = T(1-t), \quad \displaystyle 2T\left( \frac{t}{2} \right) = T(t)+t$

また、高木関数はこれらの関数等式を満たすような $[0, 1]$ 上定義された連続関数として特徴づけられる。

証明. 任意の非負整数 $n$ に対して $\langle \! \langle 2^nt \rangle \! \rangle = \langle \! \langle 2^n(1-t) \rangle \! \rangle$ であることから最初の関数等式がわかる。二つ目の関数等式は、 $\langle \! \langle \frac{t}{2} \rangle \! \rangle = \frac{t}{2}$ であることに注意すれば、

$\displaystyle 2T\left( \frac{t}{2} \right) = 2\left\langle \! \left\langle \frac{t}{2} \right\rangle \! \right\rangle + 2\left( \sum_{n=1}^{\infty}\frac{\langle \! \langle 2^n\frac{t}{2} \rangle \! \rangle}{2^n}\right) = t+T(t)$

と示される。これらの関数等式から、 $[0, 1]$ 区間に含まれる全ての $2$ 進有理数の値を決めることができるので、 $[0, 1]$ に含まれる $2$ 進有理数全体は $[0, 1]$ で稠密であることと連続性から $T(t)$ は一意に決定されることがわかる。 Q.E.D.

リーマン予想

次のような定理があることを知りました。証明はフォローしていないので紹介に留めます。

Kanemitsu-Yoshimoto (2000) $N$ を正の整数として、 $\mathcal{F}_N$ を既約分数表示した際の分母が $N$ 以下であるような $[0, 1]$ 区間内の有理数全体集合とする。このとき、Riemann予想は次の高木関数を用いて表される漸近公式が任意の正の実数 $\varepsilon > 0$ に対して成立することと同値である：

$\displaystyle \sum_{\rho \in \mathcal{F}_N}T(\rho)-\#\mathcal{F}_N\int_0^1T(t)dt = O(N^{\frac{1}{2}+\varepsilon}), \quad (N \to \infty)$

*1:論文中で著者が定義したものであっても"We define ~"と書く慣習がありますが、この論文では"I define $f(t)$ by"と書かれています。

*2: $\mathrm{dist}(t, \mathbb{Z})$ は意味がわかりやすくて良い記号ですが、表記が長くなってしまいます。

*3: $t=1$ での微分不可能性は次の節の $T(t)=T(1-t)$ からわかるように $t=0$ における微分不可能性と同値。

*4: $j \geq n$ に対して $\displaystyle \frac{\langle \! \langle 2^jv_n \rangle \! \rangle}{2^j}=\frac{\langle \! \langle 2^ju_n \rangle \! \rangle}{2^j}=0$ であることに注意。

2017-01-02

ウェダーバーンの定理

定理解説

環と言ったら可換環のことを指すというようなことはなくて、普通は非可換環も含めて環なので、可換環しか扱わないような場合は最初に明言する必要があります。 $1$ を持つかなども基本的には書かなければなりません。一方、体と言ったら普通は可換体を表します。非可換の場合も含める場合は斜体とか可除環と呼ぶことが殆どです。次の定理は非常に基本的な事実です：

定理 (Wedderburn, Dickson) 有限斜体は可換である。

基本的な事実ではありますが、「有限性が可換性を保証する」と読めるので、初見では驚きの定理でもあります。証明はたくさん知られており、コホモロジー論からBrauer群が消えることを言うことも出来ますし、Skolem–Noetherを使う証明や、類等式を使う証明などをよく見る気がします。

しかしながら、Zsigmondyの定理を使う証明があることを知りました。せっかくZsigmondyの定理についてまとめたので、Zsigmondyの定理 - INTEGERS

それを使った証明を紹介することにします。Sylowの定理は既知と仮定します。

証明

$K$ を有限斜体とする。 $K$ の素体を $K(p)$ とする( $p$ は素数で $K(p) \simeq \mathbb{F}_p$ )。 $n:=[K:K(p)]$ とおく( $n \geq 2$ を考えれば十分)。

$n=2$ のとき
$K\setminus K(p)$ の元 $a$ を任意にとる。このとき, $a$ が生成する $K$ の部分体 $F$ は $K(p)$ には一致しないため、元の個数を考えると $K=F$ ということになる。これは可換。

$n > 2$ , $(n, p) \neq (6, 2)$ のとき
Zsigmondyの定理によって、 $p^n-1$ の素因数 $q$ であって、任意の $1 \leq k \leq n-1$ に対して $q \nmid p^k-1$ なるものが存在する。 $K^{\times}$ は位数 $p^n-1$ の有限群であるから、位数 $q$ の元 $a \in K^{\times}$ が存在する(これはSylowの定理より弱いCauchyの定理と呼ばれている事実から分かる)。 $a$ の生成する $K$ の部分体 $F$ を考える。 $k:=[F:K(p)]$ とおく。このとき、 $\#F^{\times}=p^k-1$ なので、 $q \mid p^k-1$ である。従って、 $q$ の性質から $k=n$ となって、 $K=F$ を得る。すなわち、 $K$ は可換である。

$(n, p) = (6, 2)$ のとき
$\#K^{\times}=2^6-1=63=9\times 7$ なので、Sylowの定理より位数 $9$ の部分群 $G$ が存在する(位数 $9$ の群は可換なものしかない)*1。 $G$ の生成する $K$ の部分体を $F$ とする。 $k:=[F:K(2)]$ とおくと( $k \leq 6$ )、 $\#F^{\times}=2^k-1$ であるが、 $G$ は $F^{\times}$ の部分群なので $9 \mid 2^k-1$ でなければならない。こうなるのは $k=6$ のときのみである。すなわち、 $K=F$ であり、これは可換である。

Q.E.D.

*1:体の乗法群の有限部分群は巡回群であるが、これは一般の斜体では成り立たない。正標数の斜体については成立することがHersteinによって証明されているが、その証明にはWedderburnの定理を用いるので注意が必要である。

2016-12-30

Zsigmondyの定理

定理解説整数整数-63

高校数学の美しい物語さんの記事

mathtrain.jp

を初めて見たとき、一つだけ知らない定理がありました。それがZsigmondyの定理です：

Zsigmondyの定理 $a, b$ を互いに素な自然数とし、 $n$ を $2$ 以上の整数とする。このとき、 $2^6-1^6$ および $n=2$ かつ $a+b$ が $2$ の冪であるという例外ケースを除いて、 $a^n-b^n$ の或る素因数 $p$ が存在して、 $p$ は $1 \leq k \leq n-1$ なる任意の $k$ に対して $a^k-b^k$ を割り切らない。

この定理は1892年にZsigmondyによって発見・証明され、1904年にBirkhoffとVandiverによって再証明されています。この記事ではZsigmondyの定理のBirkhof-Vandiverによる証明をMichelsが整理したものを解説します。定理の主張を満たすような素因数のことを原始的素因数と呼ぶことにします。

準備の補題

自然数 $n$ に対して、 $\Phi_n(X)$ を第 $n$ 円分多項式とする。基本事項として

$\displaystyle X^n-1=\prod_{d\mid n}\Phi_d(X)$ ー①

および

$\displaystyle \Phi_n(X)=\prod_{d \mid n}(X^{\frac{n}{d}}-1)^{\mu(d)}$ ー②

が成り立つことを思い出します。ここで、 $\mu(d)$ はMöbius関数です。

補題１ $p$ を素数、 $n, k$ を自然数とする。このとき、

$\displaystyle \Phi_{p^kn}(X) = \begin{cases}\Phi_n(X^{p^k}) & p\mid n\\ \displaystyle \frac{\Phi_n(X^{p^k})}{\Phi_n(X^{p^{k-1}})} & p \nmid n \end{cases}$

が成り立つ。特に、任意の整数 $a$ に対して $\Phi_{p^kn}(a)$ は $\Phi_n(a^{p^k})$ を割り切る。

証明. ②を用いることによって容易に確認できる。 Q.E.D.

補題２ $p$ を素数とし、 $n=p^kq$ であるとする。ここで、 $k, q$ は自然数で $q$ は $p$ で割り切れない。このとき、整数 $a$ が $\Phi_n(a) \equiv 0 \pmod{p}$ を満たすならば、 $a \bmod{p}$ の乗法群 $\mathbb{F}_p^{\times}$ における位数は $q$ である。

証明. $p \mid \Phi_n(a)$ なので、①より $p \mid a^n-1$ である。Fermatの小定理より $a^n-1 \equiv a^q-1 \pmod{p}$ であり、結局 $p \mid a^q-1$ となる。すなわち、 $a \bmod{p}$ は確かに $\mathbb{F}_p^{\times}$ の元であって、その位数を $e$ とすると $e \mid q$ が成り立つ。補題１より $\Phi_n(a) \mid \Phi_q(a^{p^k})$ であり、Fermatの小定理より $\Phi_q(a^{p^k}) \equiv \Phi_q(a) \pmod{p}$ であるから $p \mid \Phi_q(a)$ ー③がわかる。 $e < q$ であると仮定して矛盾を導く。②より $a^e-1=\prod_{d \mid e}\Phi_d(a)$ なので、或る $d \mid e$ が存在して $p \mid \Phi_d(a)$ ー④が成り立つ。 $e < q$ であることから、③と④より多項式 $X^q-1=\prod_{r \mid q}\Phi_r(X)$ は $\mathbb{F}_p[X]$ に還元して考えると重根をもつことになる。しかしながら、重根を持てるのは $p \mid q$ の場合のみである。従って、我々は矛盾に到達した。 Q.E.D.

補題３ $n$ を自然数、 $a$ を整数とし、 $p$ を $\Phi_n(a)$ の素因数とする。このとき、 $p \equiv 1 \pmod{n}$ または $p \mid n$ のいずれかが成立する。

証明. これは鈴木の定理の記事105：円分多項式の係数と鈴木の定理 - INTEGERSにおける補題７に他ならない。 Q.E.D.

補題４(指数持ち上げ補題) $p$ を奇素数とし、 $p$ で割り切れない相異なる整数 $x, y$ が $x\equiv y \pmod{p}$ なる関係を満たすとき、任意の自然数 $n$ に対して

$\mathrm{ord}_p(x^n-y^n) = \mathrm{ord}_p(x-y)+\mathrm{ord}_p(n)$

が成り立つ。

証明. 別途記事を書いた:指数持ち上げ補題 - INTEGERS Q.E.D.

補題５ $n$ を自然数とし、 $x > 1$ を実数とする。このとき、不等式

$(x-1)^{\varphi(n)} \leq \Phi_n(x) < (x+1)^{\varphi(n)}$

が成り立つ。また、一つ目の不等式における等号は $n=2$ でのみ成立する。ここで、 $\varphi(n)$ はEulerのトーシェント関数である。

証明. $\zeta$ が絶対値 $1$ の複素数であれば三角不等式

$x-1 \leq \left|x-\zeta\right| \leq x+1$

が成立する。一つ目の不等式は $\zeta=1$ のときのみ、二つ目の不等式は $\zeta=-1$ のときのみ等号が成立する。この不等式を全ての $1$ の原始 $n$ 乗根について考えて掛け合わせることにより

$\displaystyle (x-1)^{\varphi(n)} \leq \prod_{\zeta}\left|x-\zeta\right| < (x+1)^{\varphi(n)}$

が得られる。一つ目の不等式で等号が成立するのは $\varphi(n)=1$ のときのみであり、それは $n=2$ のときである。二つ目の不等式は $x-1 < x+1$ であることから常に等号は成立しない。さて、定義より不等式の真ん中の数は $\left|\Phi_n(x)\right|$ であり、②より $x > 1$ であることから $\Phi_n(x) > 0$ である。 Q.E.D.

Zsigmondyの定理の証明

$a, b, n$ はZsigmondyの定理の主張に現れるようなものとして固定する。ただし、 $a > b$ とする(主張の本質は変わらない)。また、例外ケースではないと仮定する。

$n=2$ のとき $a^2-b^2=(a-b)(a+b)$ で、例外ケースでないことから $a+b$ は奇素数因子を持ち、それが原始的となる。何故ならば、もし、 $a-b$ も割り切るならば $a$ と $b$ を割り切ることになり互いに素であるという仮定に反するからである。

従って、以下 $n > 2$ とする。

若干の帰着
原始的素因数の存在を示すということは、 $a^n-b^n$ の素因数 $p$ が存在して $1 \leq k \leq n-1$ なる任意の $k$ に対して $p$ は $a^k-b^k$ を割り切らないことを示すということである(定義そのもの)。しかしながら、実際には

$a^n-b^n$ の素因数 $p$ が存在して、 $n$ の任意の真の約数 $d$ に対して $p$ が $a^d-b^d$ を割り切らなければ $p$ は原始的素因数である。

が成り立つ。これを確認するには $a^n-b^n$ の素因数 $p$ に対して、 $p$ が $a^k-b^k$ の素因数であるような最小の自然数 $k$ をとったときに $k \mid n$ となっていることを示せばよい。 $a, b$ は互いに素であるからともに $p$ で割り切れないことに注意する。 $bc \equiv 1 \pmod{p}$ なる整数 $c$ を一つとる*1。 $p \mid a^k-b^k$ は $p \mid (ac)^k-1$ と同値である。よって、 $k$ の最小性から $ac\bmod{p}$ の $\mathbb{F}_p^{\times}$ における位数は $k$ である。 $p \mid (ac)^n-1$ でもあるから $k \mid n$ がわかる。

証明方針

$\Phi_n(X, Y)$ を斉次円分多項式とする。すなわち、

$\displaystyle \Phi_n(X, Y) = Y^{\varphi(n)}\Phi_n\left( \frac{X}{Y} \right)$ ー⑤

$\displaystyle X^n-Y^n=\prod_{d \mid n}\Phi_d(X, Y)$ ー⑥

$\displaystyle \Phi_n(X, Y) = \prod_{d \mid n}(X^{\frac{n}{d}}-Y^{\frac{n}{d}})^{\mu (d)}$ ー⑦

が成り立つ。円分多項式に関する命題は大抵の場合斉次版に書き換えることができる。

示したいことは $a^n-b^n$ が原始的素因数を持つことであるが、 $a^n-b^n$ の因数のうち原始的素因数からなる部分を $P_n$ とする。すなわち、 $\mathcal{P}$ を $a^n-b^n$ の原始的素因数全体からなる集合とするとき、

$\displaystyle P_n:=\prod_{p \in \mathcal{P}}p^{\mathrm{ord}_p(a^n-b^n)}$

と定義される。 $\mathcal{P}=\emptyset$ ならば $P_n:=1$ とする。しからば、我々が示すべきことは $P_n > 1$ となる。

ところで、各原始的素因数は⑥より $d\mid n$ なる $d$ に対する $\Phi_d(a, b)$ のいずれかに住んでいるが、原始的素因数の定義と⑦を合わせて考えると $d < n$ なる $d$ に対する $\Phi_d(a, b)$ には住んでいないことがわかる。すなわち、 $P_n$ は $\Phi_n(a, b)$ に格納されているのである。そこで、

$\Phi_n(a, b)=\lambda_nP_n$

と $\lambda_n$ を導入する。我々は $P_n$ 自体を攻めるのではなく、 $\lambda_n$ を攻めるという方針をとることにする。証明のKeyは $\lambda_n$ は殆ど素因数を持ち得ないことを示すことである。具体的にいうと、 $\lambda_n$ は素因数を持ったとしても高々一つであり、更にその素因数の指数は $1$ であることを示すことができる。この証明に指数持ち上げ補題が巧みに用いられることになる。そうして、 $\lambda_n$ が十分に小さいことを示した後に補題５を使って $\Phi_n(a, b)$ を下から評価することによって $P_n$ も下から評価できるという寸法である。

$\lambda_n$ の構造

$\lambda_n$ が素因数 $p$ を持ったと仮定する。このとき、

$p \mid n$ を示す。 $p=2$ のときは補題３のうち、 $p \equiv 1 \pmod{n}$ は成り立たない( $n > 1$ なので)。よって、 $p \mid n$ が成り立つ。

$p$ は奇素数であるとする。 $p \nmid n$ と仮定して矛盾を導く。 $\lambda_n$ の素因数は原始的ではないため、「若干の帰着」の内容と合わせると、 $d \mid n$ , $d < n$ であって $p \mid a^d-b^d$ なるものが存在する。まず、⑥より

$\displaystyle \Phi_n(a, b) \left| \ \frac{a^n-b^n}{a^d-b^d} \right.$

であり、特に

$\displaystyle p \left| \ \frac{a^n-b^n}{a^d-b^d} \right.$ ー⑧

であることがわかる。一方、 $a^d \equiv b^d \pmod{p}$ であって $d \mid n$ であるから、指数持ち上げ補題を適用すると

$\mathrm{ord}_p(a^n-b^n) = \mathrm{ord}_p(a^d-b^d)$

が成り立つことがわかる( $p \nmid n$ と仮定していることに注意)。これは⑧と矛盾する。以上により $p \mid n$ が示された。つまり、 $\lambda_n$ の素因数は $n$ の素因数によって支配される(とりあえずそんなにたくさんはないことがわかった)。 $p \mid \lambda_n$ を引き続き仮定する。

$\lambda_n$ の素因数は $p$ のみであることを示す。 $n=p^kq$ と表示する。ここで、 $k, q$ は自然数で $q$ は $p$ で割り切れない。補題１は斉次版でも成り立つため

$\Phi_n(a, b) \mid \Phi_q(a^{p^k}, b^{p^k})$

が成り立ち、Fermatの小定理より $\Phi_q(a^{p^k}, b^{p^k}) \equiv \Phi_q(a, b) \pmod{p}$ であるから、 $p \mid \Phi_q(a, b)$ である。 $bc \equiv 1 \pmod{p}$ なる整数 $c$ をとると $p \mid \Phi_q(ac)$ が成り立つので、補題３より $p \equiv 1 \pmod{q}$ または $p \mid q$ となる。今、 $p \nmid q$ であるから $p \equiv 1 \pmod{q}$ が成立することがわかる。特に、 $p > q$ である。 $r$ を $n$ の $p$ 以外の素因数としよう(これは $q\neq 1$ のときのみ考える)。すると、 $r \mid q$ なので、 $p > q$ と合わせて $p > r$ でなければならない。先ほど $p \mid n$ を示したことと合わせて

$\lambda_n$ の素因数は存在すれば $n$ の素因数のうち最大のものとして特徴付けられる。特に、 $\lambda_n$ の素因数はあったとしても一つである

ことが示された。引き続き $p \mid \lambda_n$ と仮定しよう。今示したことから $\lambda_n=p^j$ と書けることがわかる。

$j=1$ であることを示す。 $p=2$ のときから示す。 $n$ の最大の素因数が $2$ ということになるので、 $n$ は $2$ の冪である。 $n > 2$ としているのだから、 $n/2$ も $2$ の冪である。⑦とMöbius関数の性質より

$\displaystyle \Phi_n(a, b) = \frac{a^n-b^n}{a^{\frac{n}{2}}-b^{\frac{n}{2}}} = a^{\frac{n}{2}}+b^{\frac{n}{2}}$

である。 $a, b$ が互いに素であることと $2 \mid \lambda_n \mid \Phi_n(a, b)$ から $a$ と $b$ はともに奇数である。すなわち、 $\Phi_n(a, b)$ は奇数の平方数の和になっていることがわかった。従って、 $\Phi_n(a, b) \equiv 2 \pmod{4}$ である。すなわち、 $\Phi_n(a, b)$ は単偶数(i.e. $j=1$ )である。

次に $p$ が奇素数であるとする。 $p \mid a^d-b^d$ なる $d \mid n$ を任意に考える。今までと同じように $c$ をとると、 $p \mid \Phi_n(a, b)$ であることから $p \mid \Phi_n(ac)$ であることがわかり、補題２より $ac\bmod{p}$ の $\mathbb{F}_p^{\times}$ での位数は $q$ である( $n=p^kq$ という設定は続ける)。一方、 $p \mid (ac)^d-1$ なので、 $q \mid d$ であることがわかる。このことから、⑦を考えると

$j=\mathrm{ord}_p(\lambda_n) = \mathrm{ord}_p(\Phi_n(a, b))=\mathrm{ord}_p(a^n-b^n)-\mathrm{ord}_p(a^{\frac{n}{p}}-b^{\frac{n}{p}})$

となる( $\mu$ の値が $0$ とならない因子のみを考えればよく、そのようなもののうち最後の二つ以外は $p$ で割れない)。 $p$ が原始的でないことを考えると、上の議論と合わせて $a^{\frac{n}{p}}-b^{\frac{n}{p}}$ は実際に $p$ で割り切れることがわかるので、 $x=a^{\frac{n}{p}}$ , $y=b^{\frac{n}{p}}$ , $n=p$ として指数持ち上げ補題を適用することができる。従って、

$j=\mathrm{ord}_p(a^n-b^n)-\mathrm{ord}_p(a^{\frac{n}{p}}-b^{\frac{n}{p}})=\mathrm{ord}_p(p)=1$

を得る。以上をもって、 $\lambda_n$ は $1$ であるか、或る素数 $p$ に対して $\lambda_n=p$ となることが示された。

証明の完結

$\lambda_n=1$ のとき補題５( $n > 2$ に注意)より

$P_n = \Phi_n(a, b) > (a-b)^{\varphi(n)} \geq 1$

よって、 $P_n > 1$ が示された。

$\lambda_n=p, a-b > 1$ のとき補題５より

$\displaystyle P_n= \frac{1}{p}\Phi_n(a, b) > \frac{1}{p}(a-b)^{\varphi(n)} \geq \frac{2^{p-1}}{p} \geq 1$

となって、 $P_n > 1$ が示された( $p \mid n$ なので $\varphi(n) \geq p-1$ )。

$\lambda_n=p, a-b = 1$ のとき $\Phi_n(a, b) > p$ を示せばよい。 $p \mid a^n-b^n$ なので $p$ は奇数である(今、 $a, b$ のパリティは異なる)。 $n=p^kq$ とおく。いつも通り $k, q$ は自然数で $q$ は $p$ で割り切れないものとする。 $k > 1$ と仮定する。 $n=p^{k-1}pq$ と考えて補題１の斉次版を適用すると

$\Phi_n(a, b) = \Phi_{pq}(a^{p^{k-1}}, b^{p^{k-1}})$

が成り立ち、

$\displaystyle \Phi_{pq}(a^{p^{k-1}}, b^{p^{k-1}}) \geq (a^{p^{k-1}}-b^{p^{k-1}})^{\varphi(pq)} \geq a^p-b^p = \sum_{i=0}^{p-1}\binom{p}{ i}b^i > p$

と評価できる。 $k=1$ 、すなわち $n=pq$ の場合を考える。補題１の斉次版と補題５の斉次版より

$\displaystyle \Phi_n(a, b) = \frac{\Phi_q(a^p, b^p)}{\Phi_q(a, b)} > \frac{(a^p-b^p)^{\varphi(q)}}{(a+b)^{\varphi(q)}} \geq \frac{a^p-b^p}{a+b}$

と評価できる。 $p \geq 3$ のとき関数 $y=\frac{(x+1)^p-x^p}{x}$ は $x \geq 1$ で単調増加なので、

$\displaystyle \Phi_n(a, b) > \frac{a^p-b^p}{a+b} \geq \frac{(2^p-1)b}{2b+1} \geq \frac{2^p-1}{3}$

となるが、 $p > 3$ だとこれは $p$ より大きい。こうして、 $p=3$ の場合が残った。 $n=pq$ で、前に示したように $q < p=3$ なのだから、 $n=3, 6$ しかありえない。

$n=3$ としよう。 $a^3-b^3=(a-b)(a^2+ab+b^2)=a^2+ab+b^2 > 1$ なので、 $a^2+ab+b^2$ の素因数は原始的である(「若干の帰着」に注意)。最終的に $n=6$ の場合が残ったが、

$\displaystyle \Phi_6(a, b) = \frac{(a^6-b^6)(a-b)}{(a^2-b^2)(a^3-b^3)} = \frac{a^3+b^3}{a+b} = a^2-ab+b^2 = b^2+b+1$

なので、 $b > 1$ ならば $\Phi_6(a, b) > 3=p$ が示される。 $b=1, a=2$ のときは、例外ケースであった。 Q.E.D.

あとがき

Zsigmondyの定理は古い結果ですが、今ではZsigmondyの定理を特殊な場合として含む、はるかに強力な結果が得られています：
integers.hatenablog.com

この記事を書いたことによって、インテジャーズでは高校数学の美しい物語さんの「整数論の美しい定理７つ」の記事で紹介されている７つの定理のうち、フェルマーの最終定理以外の証明を解説したことになります。あと一つ！

*1: $c$ の存在証明は integers.hatenablog.com に書きました。