マルコフ方程式x^2+y^2+z^2=3xyzの正整数解の全列挙性の証明

285

こんにちは、ロダンです。今回はマルコフ方程式 $x^{2} + y^{2} + z^{2} = 3 x y z$ の解を全列挙するアルゴリズムとその性質にちゃんとした証明を与えたいと思います。この辺りの議論は初等的でそんなに難しくないんですが、なぜかネットには日本語で書いてある情報が乏しいんですよね。英語を読めるのであれば選択肢はあるのですが、やっぱり中高生とかにはハードルが高いので、ここに書こうと思います。

マルコフ方程式の正整数解の列挙アルゴリズム

まず、マルコフ方程式 $x^{2} + y^{2} + z^{2} = 3 x y z$ の正整数解を芋蔓式に生成するアルゴリズムを紹介しましょう。次の命題を証明します。

$(a, b, c)$ が $x^{2} + y^{2} + z^{2} = 3 x y z$ の正整数解であるとき、第1成分を変えた $(3 b c - a, b, c)$ 、第2成分を変えた $(a, 3 a c - b, c)$ 、第3成分を変えた $(a, b, 3 a b - c)$ も $x^{2} + y^{2} + z^{2} = 3 x y z$ の正整数解である。

$(3 b c - a, b, c)$ の場合のみ示す。他は同様の方法で示せる。 $a^{2} + b^{2} + c^{2} = 3 a b c$ に注意すると、
$\begin{aligned} (3 b c - a)^{2} + b^{2} + c^{2} = 9 b^{2} c^{2} - 6 a b c + a^{2} + b^{2} + c^{2} \\ = & 9 b^{2} c^{2} - 6 a b c + 3 a b c = 9 b^{2} c^{2} - 3 a b c = 3 (3 b c - a) b c \end{aligned}$
となって、 $(3 b c - a, b, c)$ は整数解である。また、 $3 b c - a = \frac{b^{2} + c^{2}}{a} > 0$ であるから、特に $(3 b c - a, b, c)$ は正整数解でもある。

この操作により、1つ解を見つけてくればそこから新しい解を生み出すことができます。そこでまず1つ解を見つけてくることにしましょう。実は、この方程式の解にはシンプルでわかりやすいものがあります。 $(x, y, z) = (1, 1, 1)$ です。これは

$\begin{array}{r} 1 + 1 + 1 = 3 \cdot 1 \cdot 1 \cdot 1 \end{array}$

で確かにマルコフ方程式の解になっています。ここから命題で与えた操作を使って帰納的に解を生成していくのですが、できるだけ無駄がないようにしたいです。どういうものが無駄なのかというと、例えば $(a, b, c)$ を第1成分を変えて $(α, β, γ) := (3 b c - a, b, c)$ とした後で、このトリプルを再び同じ操作で $(3 β γ - α, β, γ)$ に移すと、これは $(a, b, c)$ となって元に戻ってしまいます。そこで、 $(a, b, c)$ から続けて2度同じ成分を変えないというルールでツリーを作っていきます。すると、ツリーは次のようになります。

$\begin{array}{r} (1, 1, 1) (2, 1, 1) (1, 2, 1) (1, 1, 2) (2, 5, 1) (2, 1, 5) (5, 2, 1) (1, 2, 5) (5, 1, 2) (1, 5, 2) (13, 5, 1) \dots (2, 5, 29) \dots (13, 1, 5) \dots (2, 29, 5) \dots (5, 13, 1) \dots (5, 2, 29) \dots (29, 2, 5) \dots (1, 13, 5) \dots (5, 29, 2) \dots (5, 1, 13) \dots (29, 5, 2) \dots (1, 5, 13) \dots \end{array}$
最初（一番左）だけ第1成分、第2成分、第3成分を変える選択肢があるので3分岐、それ以外の場合は直前に変えた成分以外の成分を変えるので2分岐になっています。
これ以降、このツリーを $T$ とかくことにします。

主定理

さて、解のツリー $T$ が定義されたところで、このツリーの最も重要な性質について紹介することにしましょう。それは定理の形で次のように述べられます。

$T$ の各頂点は全て異なるマルコフ方程式の正整数解である。
任意のマルコフ方程式の正整数解は全て $T$ に含まれる。

この定理は、ツリー $T$ を生成するアルゴリズムが効率よく、かつ漏れなくマルコフ方程式の正整数解を列挙していることを意味しています。さらに、(1)から直ちに次のこともわかります（ややオーバーキル気味ですが）。

定理2

マルコフ方程式の正整数解は無限個存在する。

定理2の証明

このツリーを観察してみると、各3つ組の数の中で大きさが最も大きいのは、常に操作で変えた直後の成分であることに気づきます。例えば上のツリーの頂点 $(29, 5, 2)$ の中で最も大きい成分は第1成分の $29$ ですが、上のツリーでこの頂点がある位置（一番右の下から2番目）に注目してみると、 $(29, 5, 2)$ に変化する直前の頂点は左隣の $(1, 5, 2)$ であり、ちょうど第1成分の $1$ が変化して $29$ になっていることがわかります。この現象は、次の命題を証明することによって常に成り立つことがわかります。

マルコフ方程式の正整数解 $(a, b, c)$ に対して次が成り立つ。

$a \leq max {b, c}$ ならば、 $3 b c - a > max {b, c}$ である。
$b \leq max {a, c}$ ならば、 $3 a c - b > max {a, c}$ である。
$c \leq max {a, b}$ ならば、 $3 a b - c > max {a, b}$ である。

(1)のみを示す。他は同様の方法で示せる。 $(3 b c - a, b, c)$ はマルコフ方程式の正整数解であるから、 $\frac{a^{2} + b^{2} + c^{2}}{a} = 3 b c$ であることに注意すると、
$\begin{array}{r} 3 b c - a - b = \frac{a^{2} + b^{2} + c^{2}}{a} - a - b = \frac{b^{2} + c^{2} - a b}{a} \geq \frac{c^{2}}{a} > 0 \end{array}$
となり、 $3 b c - a > b$ が成り立つ。ここで上の式の最後から2番目の不等号は $a \leq b$ であることを利用している。同様に、
$\begin{array}{r} 3 b c - a - c = \frac{a^{2} + b^{2} + c^{2}}{a} - a - c = \frac{b^{2} + c^{2} - a c}{a} \geq \frac{b^{2}}{a} > 0 \end{array}$
となり、 $3 b c - a > c$ が成り立つ。

この命題により、ツリーの頂点の3つ組の数のうち最も大きい数は、ツリーの深い方に行くにつれてどんどん大きくなっていくことがわかります。この考察から、直ちに次の事実が従います。

命題3

$T$ の頂点であって $(1, 1, 1)$ であるようなものは1つのみ存在する。

また、命題3の裏も成り立ちます。ただし、こちらは命題3よりも少し証明が難しいです（おそらくこの主定理の証明の中では一番難しい部分です）。

マルコフ方程式の正整数解 $(a, b, c)$ に対して次が成り立つ。

$a > max {b, c}$ ならば、 $3 b c - a \leq max {b, c}$ である。
$b > max {a, c}$ ならば、 $3 a c - b \leq max {a, c}$ である。
$c > max {a, b}$ ならば、 $3 a b - c \leq max {a, b}$ である。

(1)のみを示す。他は同様の方法で示せる。ここで、 $b$ と $c$ の大小関係に注目して「 $c \leq b$ ならば $3 b c - a \leq b$ である」ことと「 $b \leq c$ ならば $3 b c - a \leq c$ である」ことを示せば良いが、どちらもほとんど同じ方法で示せるので「 $c \leq b$ ならば $3 b c - a \leq b$ 」のみを示す。以下、 $c \leq b$ を仮定する。関数 $f : R \to R$ を次で定義する：
$\begin{array}{r} f (x) = (x - a) (x - (3 b c - a)) . \end{array}$
仮定から $a > b$ なので、特に $b - a < 0$ であり、したがって $f (b) = (b - a) (b - (3 b c - a)) \leq 0$ を示せば $3 b c - a \leq b$ がいえる。以下、 $f (b) \leq 0$ を示す。 $(a, b, c)$ がマルコフ方程式の解であることから $b^{2} + c^{2} = a (3 b c - a)$ が成り立っているので、これを用いることで $f (b)$ の表示を
$\begin{array}{r} f (b) = (b - a) (b - (3 b c - a)) = b^{2} - 3 b^{2} c + b^{2} + c^{2} = 2 b^{2} - 3 b^{2} c + c^{2} \end{array}$
と変形できる。そこで、関数 $g : R^{2} \to R$ を
$\begin{array}{r} g (y, z) = 2 y^{2} - 3 y^{2} z + z^{2} \end{array}$
とおくと、 $g (b, c) = f (b)$ を満たすので、 $g (b, c) \leq 0$ を示せば良いことになる。 $b = c = 1$ のとき $g (1, 1) = 0$ である。今 $1 \leq c \leq b$ なので（ $c \leq b$ を仮定していたことに注意せよ）、 $g$ の $y$ 方向と $z$ 方向の偏微分が領域 ${(y, z) ∣ 1 \leq z \leq y}$ 上で常に負であれば、この領域内で $y$ 軸正方向、 $z$ 軸正方向について $g (y, z)$ が単調減少なので $0 = g (1, 1) \geq g (b, c)$ となって証明が終わる。実際、 $1 \leq z \leq y$ を満たす $(y, z)$ について
$\begin{array}{r} \frac{\partial g}{\partial y} (y, z) = 4 y - 6 y z < 0, \frac{\partial g}{\partial z} (y, z) = - 3 y^{2} + 2 z \leq - 3 z^{2} + 2 z < 0 \end{array}$
となることが確かめられる。よって示された。

この部分の証明はいろいろな方法が考えられると思います。もっと簡単に示す方法もあるかもしれません。時間がある人は考えてみてください。

追記：命題4の証明の最後の部分、 $g (b, c) \leq 0$ を示すところで $g$ を $y$ と $z$ で偏微分して証明をしていますが、もっと簡単な方法がありました。 $1 \leq c \leq b$ であることから $g (b, c) = 2 b^{2} - 3 b^{2} c + c^{2} \leq 3 b^{2} - 3 b^{2} c = 3 b^{2} (1 - c) \leq 0$ とできます。

命題4は命題3から導出することはできません。「命題3を使って、ツリー $T$ を逆に辿ればいいんじゃないか？」と思う人ももしかしたらいるかもしれませんが、その方法で証明できるのは「 $(a, b, c)$ がツリー $T$ 上の頂点である」場合のみです。いやいや定理2があるんだからそれで十分じゃないか…と思いたくなるところですが、この命題を証明する段階では定理2 (2)の「全てのマルコフ方程式の正整数解がツリー $T$ に含まれる」ことはまだ示せていないので、これを使ってしまうと循環論法に陥ります。

さらにもう一つ、重要な性質を導入します。

マルコフ方程式の正整数解のうち、同じ数が2つ以上含まれているものは $(1, 1, 1), (2, 1, 1), (1, 2, 1), (1, 1, 2)$ の4つ以外には存在しない。

第1成分と第2成分が等しいとき、正整数解は $(1, 1, 1)$ と $(1, 1, 2)$ のどちらかであることを示す（他の成分が等しいときも同様にして示される）。 $(a, a, c)$ がマルコフ方程式の正整数解であるとする。このとき、 $a$ と $c$ は $2 a^{2} + c^{2} = 3 a^{2} c$ を満たすので、これを $c$ についての2次方程式だと思うと、 $c = \frac{3 a^{2} \pm a \sqrt{9 a^{2} - 8}}{2}$ を得る。ここで、 $c$ が整数であることから $9 a^{2} - 8$ は平方数である必要がある。そこで、 $d$ を整数として $9 a^{2} - 8 = d^{2}$ とおいて式変形をすることで、 $(3 a + d) (3 a - d) = 8$ を得る。さて、 $α := 3 a + d, β := 3 a - d$ とおいたとき $α β = 8$ であり、 $α, β$ が両方とも整数であることを考慮すると $(α, β)$ は $\pm (1, 8), \pm (2, 4), \pm (4, 2), \pm (8, 1)$ のいずれかとなる。ここでさらに、連立方程式
$\begin{array}{r} {\begin{cases} 3 a + d = α \\ 3 a - d = β \end{cases} \end{array}$
を解いたときに $a$ が正整数、 $d$ が整数でなければならないので、 $(α, β)$ の候補は $(2, 4), (4, 2)$ に絞られる。このとき、どちらも $a = 1$ である。 $a = 1$ のとき、 $c = 1$ または $2$ なので $(a, a, c)$ は $(1, 1, 1)$ または $(1, 1, 2)$ であることが示された。

以上で、定理2を証明する準備ができました。

定理2の証明

まず(2)を示す。 $(a, b, c)$ をマルコフ方程式の正整数解とする。 $(a, b, c) = (1, 1, 1)$ の場合は明らかなので、 $(a, b, c) \neq (1, 1, 1)$ とする。このとき、命題5から $a, b, c$ の中で最大の成分であるようなものが一意的に定まる（ $a, b, c$ が全て違う数ならこれは明らかであり、2つ以上が同じ数であっても $(a, b, c)$ は $(2, 1, 1), (1, 2, 1), (1, 1, 2)$ のどれかなので成り立つ）。このとき、その最大の成分を選び、それを別の数と入れ替えて新しい解 $(a^{'}, b^{'}, c^{'})$ を構成することを考える：つまり、 $a$ が最大の場合は $(a^{'}, b^{'}, c^{'}) = (3 b c - a, b, c)$ 、 $b$ が最大の場合は $(a^{'}, b^{'}, c^{'}) = (a, 3 a c - b, c)$ 、 $c$ が最大の場合は $(a^{'}, b^{'}, c^{'}) = (a, b, 3 a b - c)$ を考える。命題4から、 $(a^{'}, b^{'}, c^{'})$ の3つの数の中で $(a, b, c)$ から入れ替わった数は、それ以外の2つの数より小さいか等しくなる。後者の場合、 $(a^{'}, b^{'}, c^{'})$ は最大となる成分を2つ以上持つことになるが、命題5からそのような頂点は $(1, 1, 1)$ しか存在しない。したがって、 $(a^{'}, b^{'}, c^{'}) = (1, 1, 1)$ でないならば $a^{'}, b^{'}, c^{'}$ の中で最大の成分が一意的に定まるので、その数を別の数に変えて新しい解 $(a^{″}, b^{″}, c^{″})$ を考える。この手順を繰り返すことで、構成される解に含まれる最大の数をどんどん小さくしていくことができる。ただし命題1からこれらの解は正整数解であるためこの操作は無限に行うことはできず、最終的に $(1, 1, 1)$ に辿り着くことになる。この手順を $(1, 1, 1)$ から逆に辿ると解に含まれる3つの成分のうち最大であるようなものは単調増加していくので、 $(a, b, c)$ が $T$ 上に含まれることがわかる。
次に(1)を示す。(2)を示すときに用いた、 $T$ 上で $(a, b, c)$ から $(1, 1, 1)$ まで辿り着く操作を用いると、仮に $(a, b, c)$ が $T$ 上の2箇所に現れるならば $(1, 1, 1)$ も2箇所に現れることになるが、これは命題3の系に矛盾する。以上から示された。

以上で証明することができました。

主定理からわかるいくつかの性質

ここからは主定理から導かれるマルコフ方程式の解の性質についてみてみましょう。

マルコフ方程式の正整数解に現れる正整数をマルコフ数という。任意のマルコフ数 $c$ に対して、 $c$ が最大となるマルコフ方程式の解 $(a, b, c)$ （ただし $a \leq b \leq c$ とする）が少なくとも1つ存在する。

マルコフ数の定義から、 $c$ を含む正整数解 $(a^{'}, b^{'}, c)$ を少なくとも一つとれる（マルコフ方程式は対称式なので、解に含まれる3つの数の順番は入れ替えて良い。したがって、 $c$ を第3成分としておく）。ここで、 $a^{'} \leq b^{'} \leq c$ である場合は $a^{'} = a, b^{'} = b$ として証明が終わる。そうでない場合は、 $a^{'}, b^{'}$ の大きい方を変えることによって新しい正整数解 $(3 b^{'} c - a^{'}, b^{'}, c)$ または $(a^{'}, 3 a^{'} c - b^{'}, c)$ を考える。命題4から新しい解の $c$ 以外の2成分のうち大きい方は $a^{'}, b^{'}$ の大きい方より小さいので、これを繰り返すことで第1成分と第2成分を $c$ より小さくすることができる。そうしてできた正整数解において、第1成分が第2成分より大きくなっている場合は2つの成分の位置を交換することで条件を満たす $(a, b, c)$ を得る。

この定理により、全てのマルコフ数は解の中の1番大きな数になることができます。しかし、このような解がただ1つかどうかという問題は100年以上未解決です（マルコフ数の単一性予想）。

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

$a$ と $b$ が互いに素であることのみを示す（他は同様にして示される）。 $a$ と $b$ が共通素因数 $d$ を持つとする。このとき、明らかに $3 b c - a$ と $b$ も共通の素因数 $d$ を持つ。また、 $a$ と $3 a c - a$ も共通の素因数 $d$ を持つ。したがって、 $(3 b c - a, b, c), (a, 3 a c - b, c), (a, b, 3 a b - c)$ の第1成分と第2成分は共通の素因数 $d$ を持つことになるが、定理2によって $(1, 1, 1)$ まで遡ることにって $1$ と $1$ が共通の素因数 $d$ を持つことになるため、矛盾する。

$2, 5, 13, 29, 89$ など、小さいマルコフ数に素数が多いのはこの命題7から説明をつけることができます。ちなみにマルコフ数のうち、素数であるものが無限個存在するかどうかは未解決です。個人的には上の単一性予想より解決が難しいのではないかと思います。

また、マルコフ数はフィボナッチ数やペル数といった一見関係なさそうな数たちも含んでいることが知られています。それが次の2つの命題からわかります。

方程式 $x^{2} + y^{2} + 1 = 3 x y$ の $(1, 1)$ 以外の正整数解 $(x, y)$ は、フィボナッチ数を用いて $(x, y) = (F_{2 n - 1}, F_{2 n + 1})$ または $(F_{2 n + 1}, F_{2 n - 1})$ とかける。また逆に、このような形のペアは全て $x^{2} + y^{2} + 1 = 3 x y$ の正整数解である。ただし、フィボナッチ数 $F_{k}$ は次の漸化式で帰納的に定義される数のことを指す。
$\begin{array}{r} F_{0} = 0, F_{1} = 1, F_{k} = F_{k - 1} + F_{k - 2} (k \geq 2) . \end{array}$

$(a, b)$ が方程式 $x^{2} + y^{2} + 1 = 3 x y$ の正整数解であることと、 $(a, b, 1)$ がマルコフ方程式の正整数解であることは同値である。したがって、定理2により $x^{2} + y^{2} + 1 = 3 x y$ の正整数解は $(1, 1)$ から帰納的に $(a, b) \mapsto (3 b - a, b)$ または $(a, b) \mapsto (a, 3 a - b)$ を作用させていったもので全てである。あとは、これらが $(F_{2 n - 1}, F_{2 n + 1})$ または $(F_{2 n + 1}, F_{2 n - 1})$ の表示を持つことを示せば十分である。 $(1, 2) = (F_{1}, F_{3}), (2, 1) = (F_{3}, F_{1})$ であり、これらが $x^{2} + y^{2} + 1 = 3 x y$ の正整数解であることは明らか。 $F_{k + 1} = F_{k} + F_{k - 1} = 2 F_{k - 1} + F_{k - 2} = 3 F_{k - 1} - F_{k - 3}$ が成立するので、 $(F_{2 n - 1}, F_{2 n - 3})$ が $x^{2} + y^{2} + 1 = 3 x y$ の正整数解ならば $(F_{2 n - 1}, 3 F_{2 n - 1} - F_{2 n - 3}) = (F_{2 n - 1}, F_{2 n + 1})$ も正整数解である。 $(F_{2 n - 3}, F_{2 n - 1})$ の場合も同様である。よって示された。

方程式 $x^{2} + y^{2} + 4 = 6 x y$ の $(1, 1)$ 以外の正整数解 $(x, y)$ は、ペル数を用いて $(x, y) = (P_{2 n - 1}, P_{2 n + 1})$ または $(P_{2 n + 1}, P_{2 n - 1})$ とかける。また逆に、このような形のペアは全て $x^{2} + y^{2} + 4 = 6 x y$ の正整数解である。ただし、ペル数 $P_{k}$ は次の漸化式で帰納的に定義される数のことを指す。
$\begin{array}{r} P_{1} = 1, P_{2} = 2, P_{k} = 2 P_{k - 1} + P_{k - 2} (n \geq 3) . \end{array}$

$(a, b)$ が方程式 $x^{2} + y^{2} + 4 = 6 x y$ の正整数解であることと、 $(a, b, 2)$ がマルコフ方程式の正整数解であることは同値である。したがって、定理2により $x^{2} + y^{2} + 4 = 6 x y$ の正整数解は $(1, 1)$ から帰納的に $(a, b) \mapsto (6 b - a, b)$ または $(a, b) \mapsto (a, 6 a - b)$ を作用させていったもので全てである。あとは、これらが $(P_{2 n - 1}, P_{2 n + 1})$ または $(P_{2 n + 1}, P_{2 n - 1})$ の表示を持つことを示せば十分である。 $(1, 5) = (P_{1}, P_{3}), (5, 1) = (P_{3}, P_{1})$ であり、これらが $x^{2} + y^{2} + 4 = 6 x y$ の正整数解であることは明らか。 $P_{k + 1} = 2 P_{k} + P_{k - 1} = 5 P_{k - 1} + 2 P_{k - 2} = 6 P_{k - 1} - P_{k - 3}$ が成立するので、 $(P_{2 n - 1}, P_{2 n - 3})$ が $x^{2} + y^{2} + 4 = 6 x y$ の正整数解ならば $(P_{2 n - 1}, 6 P_{2 n - 1} - P_{2 n - 3}) = (P_{2 n - 1}, P_{2 n + 1})$ も正整数解である。 $(P_{2 n - 3}, P_{2 n - 1})$ の場合も同様である。よって示された。

おわりに

今回はマルコフ方程式の正整数の初等的かつ基本的な性質を紹介しました。2024年の東北大のAO入試ではこの中の定理2の系を証明する問題が出題されましたが、この問題の背景にさらに美しい現象が隠れていることがお分かりいただけたかと思います（定理2の系を証明するだけなら定理2は必要なく、もっと簡単に証明することができます）。しかし、実はマルコフ方程式の沼はまだまだこんなものではありません。その片鱗はたとえばこことかこことかこことかこことかここにもあるし、大学の数学を学べばさらにいろんな世界が広がっていることがわかります。というわけで、この物語の続きを知りたい人は大学に行って大学数学を勉強しましょう（そしていつか僕とも研究をしましょう）！