文献あり

マルコフ数が互いに素な整数の2乗和でかけることの証明

439

こんにちは、ロダンです。マルコフ数の性質を証明しよう企画の第二弾ということで記事を書いています（第一弾はこちら、この後続くとは限りません）。今回の性質についても日本語で読めて、かつネットに置いてある文献がないということで、証明をちゃんと与えていきたいと思います。ただし、途中有名な定理を使用するところがあり、その証明は適宜文献を参照してもらうことにします。

主定理

まずはマルコフ数の定義からしていきましょう。

マルコフ数

マルコフ方程式 $x^{2} + y^{2} + z^{2} = 3 x y z$ を満たす正整数解に現れる数をマルコフ数という。

マルコフ数の例

$(1, 2, 5)$ はマルコフ方程式の解なので、 $1, 2, 5$ はマルコフ数である。

今回の主定理は次の定理です。

任意のマルコフ数 $c$ に対して、互いに素な（正の）整数の組 ${α, β}$ が存在して、 $c = α^{2} + β^{2}$ とかける。

実際に小さいマルコフ数 $1, 2, 5, 13, 29, 34, 89, 169, 194$ について確かめてみると、

$\begin{aligned} 1 = 0^{2} + 1^{2}, 2 = 1^{2} + 1^{2}, 5 = 1^{2} + 2^{2}, 13 = 2^{2} + 3^{2}, 29 = 2^{2} + 5^{2}, \\ 34 = 3^{2} + 5^{2}, 89 = 5^{2} + 8^{2}, 169 = 5^{2} + 12^{2}, 194 = 5^{2} + 13^{2} \end{aligned}$

となりきちんと定理の主張を満たしていることがわかります。ところで、定理1の条件を満たす $α$ と $β$ は何者なのか？ということも気になると思いますが、これは証明の途中で明らかになります。

証明の準備

まずこの証明を行うにあたって、いくつか既知の事実を与えておきます。

準備1: マルコフ方程式の正整数解の性質

まずはマルコフ数（というよりマルコフ方程式の解）の性質から。

$(a, b, c)$ がマルコフ方程式の正整数解であるとき、 $a, b, c$ は互いに素である。

ステートメントはいたってシンプルですが、証明にはマルコフ方程式の正整数解を生成するツリーを使うなど、かなり奥深いです。第一弾の記事を参照してください。

準備2: 初等整数論についての重要な定理たち

初等的整数論における前提知識を確認しておきましょう。

ルジャンドル記号

$p$ を奇素数とする。整数 $a$ に対して、記号 $(\frac{a}{p})$ を、

$a \equiv x^{2} \mod p$ を満たす $x \neq 0$ が存在する場合 $(\frac{a}{p}) = 1$ ,
$a \equiv x^{2} \mod p$ を満たす $x$ が存在しない場合 $(\frac{a}{p}) = - 1$ ,
$a \equiv 0 \mod p$ を満たす場合 $(\frac{a}{p}) = 0$
と定める。この記号をルジャンドル記号という。

この記号について、今回の証明で必要な性質を挙げておきます。

整数 $a, b$ と奇素数 $p$ について、次が成り立つ。

$(\frac{a b}{p}) = (\frac{a}{p}) (\frac{b}{p})$
$(\frac{- 1}{p}) = 1 \Leftrightarrow p \equiv 1 \mod 4$

上記の性質はオイラーの規準と呼ばれる性質
$\begin{array}{r} (\frac{a}{p}) \equiv a^{\frac{p - 1}{2}} \mod p \end{array}$
から導出できます。詳しくは高校数学の美しい物語さんの記事などを参照してください。さらにこの応用として、次の定理が示されます。

フェルマーの二平方和の定理

奇素数 $p$ に対して、「ある正整数の組 ${α, β}$ が存在して $p = α^{2} + β^{2}$ とかける」ことと、「 $p$ は $4 m + 1$ 型の素数である」ことは同値である。

証明は例えば高校数学の美しい物語さんの記事や Wikipediaの「二個の平方数の和」の項に詳細が載っているのでこちらを参照してください。

定理1の証明

では、実際に定理1を証明していきましょう。まず、次の補題を証明します。

マルコフ数の奇数である正素因数は全てある整数 $m$ を用いて $4 m + 1$ と表される。
偶数であるマルコフ数は $4$ の倍数ではない。

$c$ をマルコフ数とする。まず(1)を示す。 $c$ を含むマルコフ方程式の解 $(a, b, c)$ を一つとる。このとき、 $a^{2} + b^{2} + c^{2} = 3 a b c$ を満たしている。これを変形することで $a^{2} + b^{2} = c (3 a b - c)$ となり、 $a^{2} + b^{2}$ は $c$ で割り切れる。したがって、 $c$ の奇素因数 $p$ でも $a^{2} + b^{2}$ は割り切れる。すなわち、 $a^{2} \equiv - b^{2} \mod p$ である。ここで、命題2より $b$ は $c$ と互いに素であり、特に $b^{2}$ と $p$ は互いに素であるから、 $(\frac{- b^{2}}{p}) = 1$ が成立する。命題3(2)より、補題5を示すためには $(\frac{- 1}{p}) = 1$ を示せば良い。命題3(1)から
$\begin{array}{r} 1 = (\frac{- b^{2}}{p}) = (\frac{b^{2}}{p}) (\frac{- 1}{p}) \end{array}$
が成立している。ルジャンドル記号の定義から明らかに $(\frac{b^{2}}{p}) = 1$ なので、 $(\frac{- 1}{p}) = 1$ である。よって示された。
(2)を示す。 $c = 2^{k} t$ とおく。ここで $k \geq 1$ かつ $t$ は奇数であるとする。このとき、 $k = 1$ であることを示せば十分である。 $c$ を含むマルコフ方程式の解 $(a, b, c)$ を一つとる。 $c$ が偶数であることと $a^{2} + b^{2} = c (3 a b - c)$ であることから $a^{2} + b^{2}$ は偶数である。このとき $a$ と $b$ は両方偶数であるか両方奇数であるかのどちらかであるが、命題2から両方偶数であることはありえず、したがって両方奇数である。このとき、(1)から $a = 4 m + 1, b = 4 m^{'} + 1$ とかける。 $k \geq 2$ を仮定すると、
$\begin{array}{r} 2 \equiv a^{2} + b^{2} + c^{2} = 3 a b c \equiv 0 \mod 4 \end{array}$
が成立することになり、これは矛盾である。したがって、 $c$ は $4$ の倍数ではない。

この先の議論のために、ガウス整数環 $Z [i] = {x + y i ∣ x, y \in Z}$ を考えます。ただし $i$ は虚数単位です。まず基本的な事項について確認しておきます。

$Z [i]$ はノルム $N (a + b i) = \sqrt{a^{2} + b^{2}}$ についてユークリッド整域である。特に、一意分解整域である。
$u \in Z [i]$ について、「 $u$ は単元である」ことと「 $u$ はノルム $1$ の元である」ことは同値であり、これを満たす $u$ は $\pm 1$ と $\pm i$ で全てである。

このあたりは基本的な環論の教科書を参照してください。 $Z [i]$ が一意分解整域であることにより、 $Z [i]$ においては素因数分解や最大公約数を考えることができます。さて、次の命題がこの問題の核心です。

マルコフ数 $c$ を含むマルコフ方程式の正整数解 $(a, b, c)$ を1つとる。このとき、 $c$ と $a + b i$ の $Z [i]$ における最大公約数を $α + β i$ とすると $c = α^{2} + β^{2}$ が成立する。

最大公約数は単元倍による差を除いて一意的であって一意に定まるわけではないのでどんな値を取っても $α^{2} + β^{2}$ が一定なのかが一瞬気になりますが、 $Z [i]$ の単元は命題6(2)よりノルムを変えないので問題ありません。それでは、命題7を示していきましょう。

$c$ を $Z$ において素因数分解したときの表示を $c = p_{1}^{a_{1}} p_{2}^{a_{2}} \dots p_{n}^{a_{n}}$ とする。ただし、 $p_{1}, \dots, p_{n}$ は正であるとする。このとき、補題5より $p_{j}$ は $4 m + 1$ 型の素数または $2$ だから、定理4より任意の $j$ について $p_{j} = α_{j}^{2} + β_{j}^{2}$ を満たす整数の組 ${α_{j}, β_{j}}$ が存在する（ $p_{j} = 2$ のときは $2 = 1^{2} + 1^{2}$ となることに注意）。したがって、 $p_{j} = (α_{j} + β_{j} i) (α_{j} - β_{j} i)$ が成り立つ。ここで、 $c = \prod_{j = 1}^{n} (α_{j} + β_{j} i)^{a_{j}} (α_{j} - β_{j} i)^{a_{j}}$ は $c$ の $Z [i]$ における素因数分解を与えている。実際、 $α_{j} + β_{j} i$ が $(α_{j}^{'} + β_{j}^{'} i) (α_{j}^{″} + β_{j}^{″} i)$ と因数分解されるとき、 $α_{j} - β_{j} i$ は $(α_{j}^{'} - β_{j}^{'} i) (α_{j}^{″} - β_{j}^{″} i)$ と因数分解されるので、 $p_{j} = (α_{j}^{'} + β_{j}^{'} i) (α_{j}^{″} + β_{j}^{″} i) (α_{j}^{'} - β_{j}^{'} i) (α_{j}^{″} - β_{j}^{″} i) = (α_{j}^{' 2} + β_{j}^{' 2}) (α_{j}^{″ 2} + β_{j}^{″ 2})$ が成り立つ。ここで、 $p_{j}$ は $Z$ における素数であるから、 $α_{j}^{' 2} + β_{j}^{' 2} = 1$ または $α_{j}^{″ 2} + β_{j}^{″ 2} = 1$ である。したがって、 $N (α_{j}^{'} + β_{j}^{'} i) = 1$ または $N (α_{j}^{″} + β_{j}^{″} i) = 1$ が成り立つので、命題6(2)から $α_{j}^{'} + β_{j}^{'} i$ または $α_{j}^{″} + β_{j}^{″} i$ のどちらかは単元である。
次に、 $a + b i$ が各 $j$ に対して $p_{j} \neq 2$ のとき $(α_{j} + β_{j} i)^{a_{j}}$ か $(α_{j} - β_{j} i)^{a_{j}}$ のどちらか一方だけを約数に持ち、 $(α_{j} + β_{j} i)^{a_{j}}$ を約数として持つときは $α_{j} - β_{j} i$ を約数としてもたず、 $(α_{j} - β_{j} i)^{a_{j}}$ を約数として持つときは $α_{j} + β_{j} i$ を約数としてもたないことを示す。もし $a + b i$ が $α_{j} + β_{j} i$ と $α_{j} - β_{j} i$ の両方を約数として持つと仮定すると、 $α_{j} + β_{j} i$ と $α_{j} - β_{j} i$ は（ $p_{j} \neq 2$ より）同伴ではないので $a + b i$ は整数 $α_{j}^{2} + β_{j}^{2}$ を約数として持つが、これは $a$ と $b$ が互いに素であることに反する。したがってどちらか一方しか約数として持てない。さらに $c$ は $a^{2} + b^{2}$ の約数であるから、特に $p_{j}^{a_{j}}$ も $a^{2} + b^{2}$ の約数である。したがって、 $a^{2} + b^{2}$ は約数として $(α_{j} + β_{j} i)^{a_{j}} (α_{j} - β_{j} i)^{a_{j}}$ を持っている。 $a^{2} + b^{2} = (a + b i) (a - b i)$ なので、 $a_{j}$ 個の $α_{j} + β_{j} i$ と $a_{j}$ 個の $α_{j} - β_{j} i$ は $a + b i$ と $a - b i$ の約数としてそれぞれ分配され、すくなくとも $a + b i$ と $a - b i$ のどちらかには約数として $α_{j} + β_{j} i$ と $α_{j} - β_{j} i$ が合わせて $a_{j}$ 個以上含まれている。 $a + b i$ と $a - b i$ は互いに共役関係にあるので、 $a + b i$ が約数として $α_{j} + β_{j} i$ を持っているならば、 $a - b i$ は約数として $α_{j} - β_{j} i$ を同じ数だけ持っており、また $a + b i$ が約数として $α_{j} - β_{j} i$ を持っているならば、 $a - b i$ は約数として $α_{j} + β_{j} i$ を同じ数だけ持っていることになる。このことは、 $a + b i$ と $a - b i$ を入れ替えても成立する。以上のことから、 $a + b i$ は約数として $α_{j} + β_{j} i$ と $α_{j} - β_{j} i$ の両方を合わせて $a_{j}$ 個以上持っていることになる。今 $α_{j} + β_{j} i$ と $α_{j} - β_{j} i$ のどちらか一方は1つも持っていないことがわかっているので、 $a + b i$ が各 $j$ に対して $(α_{j} + β_{j} i)^{a_{j}}$ か $(α_{j} - β_{j} i)^{a_{j}}$ のどちらか一方だけを約数に持ち、 $(α_{j} + β_{j} i)^{a_{j}}$ を約数として持つときは $α_{j} - β_{j} i$ を約数としてもたず、 $(α_{j} - β_{j} i)^{a_{j}}$ を約数として持つときは $α_{j} + β_{j} i$ を約数としてもたないことがわかった。
次に、 $p_{j} = 2$ となる $j$ が存在する場合を考える（すなわち、 $c$ が偶数である場合である）。このとき、 $a + b i$ は $(1 + i)^{2}$ を約数として持たない。もし持つとすると、 $1 + i$ と $1 - i$ は同伴なので $(1 + i) (1 - i) = 2$ を約数として持つことになり、これは $a$ と $b$ が互いに素であることに反する。また、 $c$ は $a^{2} + b^{2}$ の約数であることから、特に $2$ が $a^{2} + b^{2}$ の約数でなければならず、したがって直前の議論と合わせることで $2$ の素因子である $1 + i$ （あるいは同じことだが $1 - i$ ）が $a + b i$ の約数としてちょうど1つ含まれることがわかった。
さて、 $a + b i$ が約数として $\prod_{j = 1}^{n} (α_{j} + ε_{j} β_{j})^{a_{j}}$ 　（ただし各 $j$ に対して $ε_{j} \in {\pm 1}$ とする）を持つとすると、上記の議論からこれが $c$ と $a + b i$ の最大公約数 $α + β i$ である。今 $c = \prod_{j = 1}^{n} (α_{j} + ε_{j} β_{j})^{a_{j}} (α_{j} - ε_{j} β_{j})^{a_{j}}$ なので、 $c = (α + β i) (α - β i) = α^{2} + β^{2}$ が成立する（ $c$ が偶数であるときは $p_{j} = 2$ であるような $j$ を含むが、このとき補題5(2)から $a_{j} = 1$ であることがわかり、また $1 + i$ が $a + b i$ における約数かつ $(1 + i)^{2}$ が $a + b i$ の約数でないことから奇素数と同じ議論ができることに注意せよ）。以上から示された。

$p_{j}$ が奇素数の場合は $p_{j} = (α_{j} + β_{j} i) (α_{j} - β_{j} i)$ と素因数分解した際に $α_{j}$ と $β_{j}$ の絶対値が同じ数になることはない（あったら $p$ が $1$ と $p$ 以外の約数を持つことになる）ので $α_{j} + β_{j} i$ と $α_{j} - β_{j} i$ が同伴になることはありませんが、 $p_{j} = 2$ の場合は $1 + i$ と $1 - i$ が同伴なので分けて議論する必要があります。

定理1の証明の締めくくりとして、 $α$ と $β$ が互いに素であるものとしてとれることを示します。

マルコフ数 $c$ について、命題7のように $c = α^{2} + β^{2}$ となる $α$ と $β$ をとると、 $α$ と $β$ は互いに素である。

$α$ と $β$ が $Z$ における共通の素因数 $q$ を持っているとする。このとき、 $α + β i$ は $a + b i$ の $Z [i]$ における約数なので、 $q$ も $a + b i$ の $Z [i]$ における約数である。したがって、 $q$ は $a$ と $b$ の（ $Z$ における）共通の素因数となるが、これは $a$ と $b$ が互いに素であること（命題2）に矛盾する。よって示された。

以上で定理1が示されました。

おわりに

実は私は定理1をスネークグラフという組み合わせ論の道具について論じているCanacki-Schifflerの論文CSで知っていたのですが、専門的でないもう少しシンプルな証明方法はないかと思ってこの内容を $X$ でつぶやいてみたところ、@yotsunvaさんと@sumahola974944さんから親切なリプライをいただいたことでこの証明を完成させることができました。初等整数論の議論と環論の初歩の議論をうまく活用した証明になっており、とても気に入っています。コメントをくださったお二方、ありがとうございました。また、この記事を上げてから命題7の証明の不備（ $p_{j}$ が $2$ の場合についての議論の欠落）を指摘していただいた J. Koizumi さんにも感謝の意を述べたいと思います。ありがとうございました。