平方数であるようなマルコフ数は169以外にあるか？

こんにちは、ロダンです。今回は解説記事ではなくちょっとした問題を、その背景とともに紹介したいと思います。

問題

問題を述べるために必要な定義をしておきます。

マルコフ方程式は対称式なのでその正整数解の各成分の位置は交換可能ですが、ここで定めたマルコフトリプルの場合はそうではないことに注意してください。第3成分が最大であるようなものを考えているので、$(a,b,m)$がマルコフトリプルならば$(b,a,m)$もそうですが、$m$は第1成分や第2成分と交換することはできません。

では本題。次の問題を考えます。

まず$169$がマルコフ数であることを確認しておきましょう。$(x,y,z)=(2,29,169)$とすればこれはマルコフトリプルなので、$169$はマルコフ数です。ちなみに$1$はマルコフ方程式の正整数解に現れる整数ですが、$1$が最大であるような整数解は$(1,1,1)$しかなく、ここでのマルコフトリプルの定義は3つの成分が相異なることを条件に持っているため、$(1,1,1)$はマルコフトリプルではありません。したがって、$1$はここでのマルコフ数には該当しません。

さて、ではそれ以外に平方数であるようなマルコフ数はあるのでしょうか？というのが問題1です。

この記事では、この問題に答えは出さず（というかそもそもまだわかってないので答えようがないです）、このような問題を考える背景について掘り下げます。数学という学問において、「重要な問題」とは、「なぜこのような問題を考えるのか？」という疑問に対してしっかりとした回答がある問題です。そのような問題は数学の新しい展開の鍵となるので、必然的に重要な位置を占めることになるのです。この記事によって、この問題を考える重要性を知っていただけますと幸いです。

問題の背景

平方数かつマルコフ数であるような数の位置付け

唐突ですが、次のような概念を導入することにします。

この原始平方和トリプルはマルコフトリプルと同じく第1成分と第2成分を入れ替えることが可能で、第3成分は他と入れ替えられない特徴を持っています。さて、この平方和トリプルを他の概念から構成する方法を考えてみましょう。

まずは、マルコフトリプルから原始平方和トリプルを構成することを考えてみます。その上で重要となる定理を紹介します。

上記の命題は 上の記事 の命題7で証明しています(命題7では最大公約数を$\alpha +\beta i$として取っていますがここを$\alpha -\beta i$としても本質は変わりません)。一意性について言及はしていませんが、エクササイズということにしておきたいと思います。ガウス整数の単元が$\{\pm 1,\pm i\}$しかないことからすぐに従います。このような操作でマルコフトリプル$(a,b,m)$から得られる原始平方和トリプル$(\alpha ,\beta ,m)$のことを、マルコフトリプル$(a,b,m)$から誘導される原始平方和トリプルと呼ぶことにしましょう。

マルコフトリプルから誘導される$\alpha$と$\beta$の平方和トリプル内の順番は$m$を含むマルコフトリプルに依存することに注意してください。例えば$(a,b,m)$から誘導される原始平方和トリプルが$(\alpha ,\beta ,m)$であるとき、$(b,a,m)$から誘導される原始平方和トリプルは$(\beta ,\alpha ,m)$です。

具体例を見ておきましょう。

次に、原始平方和トリプルを別のトリプルから構成する方法を考えてみます。平方和と聞いたときに、次の概念を思い浮かべた人も多いはずです。

いわゆる「直角三角形に現れる整数」のことですね。例えば、$(3,4,5)$や$(5,12,13)$などが原始ピタゴラストリプルに該当し、またこれによって$5$や$13$が原始ピタゴラス数です。マルコフトリプルと同様に第1成分と第2成分は交換できますが、第3成分は他の成分とは交換できません。

こちらのトリプルからも平方和トリプルを構成することができます。こちらはマルコフトリプルの場合と比べると非常に簡単で、原始ピタゴラストリプル$(a,b,c)$が与えられたとき、$(a,b,c^2)$が原始平方和トリプルです。これを原始ピタゴラストリプル$(a,b,c)$から誘導される原始平方和トリプルと呼ぶことにしましょう。こっちはマルコフトリプルから誘導されるものと比べると構成が非常に簡単ですが、一応具体例を見ておきます。

さて、ここまでで原始平方和トリプルの中にはマルコフトリプルから誘導されるものと原始ピタゴラストリプルから誘導されるものがありますという話をしてきました。すなわち、下の図のようになっているわけです。
原始平方和トリプルの内訳

ここで、赤の斜線で引いた2つのクラスの共通部分に入るものはなんでしょうか？というのが気になるところですね。これこそが、平方数であるようなマルコフ数が第3成分に来るような原始平方和トリプルなのです。次の命題が成立します。

つまり平方数であるようなマルコフ数を考えることは、図1の赤斜線の部分に入るような原始平方和トリプルを考えることと等価なのです！ちなみに、問題1から$169$は平方数であるようなマルコフ数ですが、これに対応する原始平方和トリプルは$(5,12,169)$と$(12,5,169)$です。今のところ、これ以外のトリプルで図1の赤斜線に入るようなものは見つかっていません。

マルコフトリプル、原始ピタゴラストリプルの列挙アルゴリズム

さて、ここからはさらにこの2つの原始平方和トリプルのクラスについて掘り下げていきましょう。前の節で紹介したように、マルコフトリプルと原始ピタゴラストリプルは原始平方和トリプルを生み出す種なわけですが、両者ともに全列挙するツリーがあることが知られています。まずはマルコフトリプルの方から。

マルコフツリーはこんな感じのツリーになります。

$$\begin{array}{r}(1,2,5)(2,5,29)(1,5,13)(5,29,433)(2,29,169)(5,13,194)(1,13,34)(29,433,37666)\cdots (5,433,6466)\cdots (29,169,14701)\cdots (2,169,985)\cdots (13,194,7561)\cdots (5,194,2897)\cdots (13,34,1325)\cdots (1,34,89)\cdots \end{array}$$

このとき、次の定理が成り立ちます。

この定理は本質的には この記事 の定理2で証明を与えています。

なお、$(a,b,c)$と$(b,a,c)$のうち現れなかった方は最初の頂点を$(2,1,5)$として同じ世代ルールで生成されたツリーの方を考えればそっちに現れます。

次に原始ピタゴラストリプルの方を見てみましょう。

こっちは3分岐のツリーです。原始ピタゴラスツリーはこんな感じのツリーになります。

$$\begin{array}{r}(3,4,5)(5,12,13)(21,20,29)(15,8,17)(7,24,25)\cdots (55,48,73)\cdots (45,28,53)\cdots (39,80,89)\cdots (119,120,169)\cdots (77,36,85)\cdots (33,56,65)\cdots (65,72,97)\cdots (35,12,37)\cdots \end{array}$$

このとき、次の定理が成り立ちます。

証明は 高校数学の美しい物語さんの記事 が詳しいです。

さてこれらのマルコフツリーと原始ピタゴラスツリー、2分岐と3分岐の違いはありますし世代ルールも全然違いますが、定理3と定理4はよく似ていますね。この2つのツリーの共通点を見出せれば大変面白いのですが、このままではあまりにもルールが違いすぎて比較が難しそうです。そこで、これらのツリーの頂点を、2つのトリプルの共通フォーマットである原始平方和トリプルに書き換えてしまいましょう。まずはマルコフツリーの方を書き換えてみることにします。各頂点のマルコフトリプルを、そこから誘導される原始平方和トリプルに置き換えます。

$$\begin{array}{r}(2,1,5)(5,2,29)(2,3,13)(12,17,433)(5,12,169)(13,5,194)(5,3,34)(75,179,37666)\cdots (29,75,6466)\cdots (70,99,14701)\cdots (29,12,985)\cdots (75,44,7561)\cdots (44,31,2897)\cdots (34,13,1325)\cdots (5,8,89)\cdots \end{array}$$
原始ピタゴラスツリーの方も同様に書き換えてみましょう。

$$\begin{array}{r}(3,4,25)(5,12,169)(21,20,841)(15,8,289)(7,24,625)\cdots (55,48,5329)\cdots (45,28,2809)\cdots (39,80,7921)\cdots (119,120,28561)\cdots (77,36,7225)\cdots (33,56,4225)\cdots (65,72,9409)\cdots (35,12,1369)\cdots \end{array}$$

どうですか？この2つのツリーになにか共通の構造のようなものが見えてきませんか？ちなみに僕はいまのところ全く見えません。ただ、目標として次のような問題が考えられます。

(1)ができたらそれだけでも結構面白いことだと思うし、(2)ができたらかなりの大事件だと思います。(2)は一見途方もない夢物語に思えますが、わずかな手がかりはあります。それは平方数かつマルコフ数である$169$が含まれる$(5,12,169)$というトリプルです。この頂点は2つのツリーにおける共通のトリプルなので、もし(2)を実現するようなツリーがあるとしたら$(5,12,169)$の周りは次のようになっているはずです。

$$\begin{array}{r}(3,4,25)(5,12,169)(7,24,625)\cdots (55,48,5329)\cdots (45,28,2809)\cdots (5,2,29)(70,99,14701)\dots (29,12,985)\dots \end{array}$$
実際はさらにいくつかつながっている辺があるかもしれませんが。どうですか？何か見えますかね？ちなみに僕にはまだ何も見えてません。こんなことを考えるなんて、荒唐無稽なのではないかとすら思えてきます。まあ、そう思ってなかったらこんなところに書かずに一人もしくは限られた複数人でこっそり研究してますからね。でも、何があるかわからないのです。もしかしたら、このツリーの世代ルールは実は簡潔に記述できるのかもしれないし、想定外の面白い事象が見つかるかもしれません。こういうときに$(5,12,169)$のような手頃な観察対象があると、このような愚かかもしれない考察をもう少し頑張ってみようという気になるわけです。まあでもやっぱり本当に荒唐無稽な試みかもしれないし、実際そうだったというパターンもいっぱいあるのですが。

ということで、$(5,12,169)$のようなトリプルを他にも見つけたい、見つからないならそれはそれで何かのヒントになるかもしれない…と思って冒頭の問題1が生まれた、というお話でした。

問題1の具体的な計算進捗

さて、問題1のモチベーションもわかったところで現在の計算進捗についてお伝えしておきます。具体的にどんな計算を行なっているかというと、「調べる整数に一定の上限を設け、その上限を超えないような全てのマルコフ数について平方数かどうかを全て判定する」というようなことをプログラムを組んでやっています。否、プログラムをChatGPT（通称：チャッピー）に書いてもらってそれを動かしています。前まで使っていたものは平方数判定がうまく機能していないという指摘をp進大好きbot( @non_archimedean )さんから受けました。改良版も提供していただいたのでこちらを掲載いたします。ご提供ありがとうございました！Pythonで動きます。

      import time
# 最大値制限の入力
max_value_limit = 10 ** int(input("max_value_limit: 10 ^ "))
B = (2**3)*3*5*7*11*13*17
# mod B で許可された値のリスト
allowed_mod_B = [0]*B
for i in range(B):allowed_mod_B[i*i%B] = 1
print(f"mod {B}平方数の比率: {sum(allowed_mod_B)/B}")
root = (1, 2, 5, 1%B, 2%B, 5%B)
# 平方数かどうかを判定する関数
def is_perfect_square(n):
    l, r = 0, n+1
    while l < r-1:
        m = (l+r)>>1
        if m * m > n:r =m
        else:l = m
    return l * l == n
# ツリー構築
def build_tree():
    stack = [root]  # スタックに初期ノードを追加
    while stack:
        a, b, c, a_mod, b_mod, c_mod = stack.pop()
        # 最大値の制限をチェック
        if c > max_value_limit:
            continue
        # 現在のノードの最大値を判定
        mod_value = c_mod
        #print(f"判定対象: {c}, mod {B}: {mod_value}")
        # mod B フィルタを適用
        if allowed_mod_B[mod_value] == 1:
            #print(f"mod {B} フィルタ通過: {mod_value}")
            if is_perfect_square(c):
                print(f"平方数: (a, b, c) = {a,b,c}")
            #else:
                #print(f"平方数ではない: {c}")
        #else:
            #print(f"mod {B} フィルタでスキップ: {c}")
        # 子ノードを生成
        child1 = (b, c, 3 * b * c - a, b_mod, c_mod, (3 * b_mod * c_mod - a_mod) % B)
        child2 = (a, c, 3 * a * c - b, a_mod, c_mod, (3 * a_mod * c_mod - b_mod) % B)
        # 子ノードを追加（制限を満たす場合のみ）
        if child1[2] <= max_value_limit:  # 第3成分（c）をチェック
            stack.append(child1)
        if child2[2] <= max_value_limit:  # 第3成分（c）をチェック
            stack.append(child2)
# ベンチマーク開始
start_time = time.time()
# ツリーを構築
build_tree()
end_time = time.time()
# ベンチマーク結果を表示
print(f"ツリー構築の実行時間: {end_time - start_time:.6f} 秒")
    

私はプログラミングの素人なのでこのプログラムがいいものなのかどうかわからないし、そもそもこうやって公衆の面前でチャッピー産のプログラムを貼り付けることも正直恥ずかしいのですが、つよつよな人が改良してくれることを期待して晒そうと思います。
うまく機能しなかったコードは墓場（目次参照）に移しました。
何をやっているかはなんとなくわかる（というかそうじゃないとチャッピーに指示できないですよね）ので説明しておくと、最初に上限値を設定して、マルコフツリーを構成していきます。1つノードを追加するたびに、そのノードの第3成分が平方数かどうかを判定します。ただし、ノードを生成したあとでそのノードの第3成分が設定した上限値を超えていたらノードの追加をしません。このようにして、ノードを追加できなくなるまでノードの追加と第3成分の平方数判定を繰り返します。上限値以下の第3成分を持つ全てのノードを全て追加し終わったら、同時に上限値以下の全てのマルコフ数の平方数判定も終わっているという算段です。なお、第3成分の重複チェックは行なっていません。重複が起こらないとは限らないのですが、マルコフ予想という予想により、全てのノードの第3成分は重複しないだろうと言われています。

また判定する際に、毎回平方数かどうかを素直にチェックするのは時間がかかるので、$1008$で割った余りが平方数のものに該当するかどうかで足切りをして時間を節約しています。割る数に$1008$を採用しているのは、足切りを通過できる整数が64種類しかないために、全体の約94%の整数に対して平方数の判定をする必要がなくなるような効率のいい数字だからです。 この記事 を見て、チャッピーに採用をお願いしたところこの足切りのおかげで確かに早くなりました。

modフィルターは$2042040$に強化されました。足切り率98.6%です。

また、ベンチマークの結果を最後に表示するようにしています。終わったことを知らせるサインであると同時に、どれくらいかかったかを知ることで次どれくらいの値で試そうかという指針が立つからです。あとは動作チェック用に平方数を判定する際にステータスを出力するオプションがついてます（今はコメントアウトしてあります）。

さて、このプログラムで${10}^{4000}$までのマルコフ数について計算を行ってみたところ、だいたい50分で計算が終わりました。その結果ですが、
計算結果

$169$以外の平方数は検出されませんでした。マジか。流石にこれだけの領域を探せばあと1つくらい見つかるんじゃないかとは思ったのですが、ないんですかね。プログラムが改修されたことで見つかったらどうしようとかちょっと思ってたのは秘密。

最後に

というわけで、今回はマルコフ数に関する1つの問題提起を行いました。この話初めて聞いた、どこから引っ張ってきたんだと思う人もいるかもしれませんが、これは私がここ数日で考えた話です。マルコフツリーと原始ピタゴラスツリーの間にある「なんかよく似てて関係ありそうだな〜」というような感覚を、数学的に考えやすいように整備しました。

一般にはあまり知られていないことだと思っていますが、解くべき問題にこうやってしっかりとした意味を与えたり、問題自体を考えやすいように体裁を整えることも数学者の大事な仕事です（少なくとも僕はそう思っています）。もちろんまだ問題自体は解かれてはいないわけですが、この作業は数学という学問を行う上で問題を解くことと同じくらい重要な作業であり、これによってその研究は半分くらい終わったと言ってもいいと思います。

ということでこの辺りで今回のお話は終わりにしたいと思います。この話の続きが気になる人は、自分で考察を進めてみてください。僕に許可を求める必要はありません、勝手にやってもらって大丈夫です。ではまた。

チャッピーが書いたコードのお墓

最初に記事に載せていた、平方数判定の関数が浮動小数点の誤差の関係で大きい（いうほど大きくない）数に対してうまく働かないコードを掲載して供養とします。現行のコードのように、二分探索で平方数かどうか判定するのが主流のようです。チャッピーは有能だけど、こちらもちゃんと知識を持っていないとうまく使いこなせないということの良い例ですね。でもこうやって恥を承知でコードを晒しておくとちゃんとした人がいろいろアドバイスをくれることがあるので掲載しててよかったなとも思っています。

      import time
import networkx as nx
# ツリーを表す有向グラフを作成
G = nx.DiGraph()
# 最大値制限の入力
max_value_limit = int(input("max_value_limit: ")) 
# 初期親ノード
root = (1, 2, 5)
G.add_node(root, subset=0)  # ルートノードのsubset_keyを設定
# mod 1008 で許可された値のリスト
allowed_mod_1008 = {
    0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 112, 121, 144, 148, 169, 193, 196,
    217, 225, 256, 288, 289, 324, 337, 340, 352, 361, 385, 400, 436, 441, 448,
    457, 484, 505, 513, 529, 532, 553, 576, 585, 592, 625, 673, 676, 688, 697,
    721, 729, 736, 756, 772, 784, 793, 820, 841, 865, 868, 889, 900, 928, 945, 961
}
# 平方数かどうかを判定する関数
def is_perfect_square(n):
    if n < 0:
        return False
    sqrt_n = int(n**0.5)
    return sqrt_n * sqrt_n == n
# ツリー構築
def build_tree():
    stack = [(root, 0)]  # スタックに初期ノードを追加
    while stack:
        parent, subset = stack.pop()
        a, b, c = parent
        # 最大値の制限をチェック
        if c > max_value_limit:
            continue
        # 現在のノードの最大値を判定
        mod_value = c % 1008
        #print(f"判定対象: {c}, mod 1008: {mod_value}")
        # mod 1008 フィルタを適用
        if mod_value in allowed_mod_1008:
            #print(f"mod 1008 フィルタ通過: {mod_value}")
            if is_perfect_square(c):
                print(f"平方数: {c}")
            #else:
                #print(f"平方数ではない: {c}")
        #else:
            #print(f"mod 1008 フィルタでスキップ: {c}")
        # 子ノードを生成
        child1 = (b, c, 3 * b * c - a)
        child2 = (a, c, 3 * a * c - b)
        # 子ノードを追加（制限を満たす場合のみ）
        if child1[2] <= max_value_limit:  # 第3成分（c）をチェック
            G.add_edge(parent, child1)
            G.add_node(child1, subset=subset + 1)
            stack.append((child1, subset + 1))
        if child2[2] <= max_value_limit:  # 第3成分（c）をチェック
            G.add_edge(parent, child2)
            G.add_node(child2, subset=subset + 1)
            stack.append((child2, subset + 1))
# ベンチマーク開始
start_time = time.time()
# ツリーを構築
build_tree()
end_time = time.time()
# ベンチマーク結果を表示
print(f"ツリー構築の実行時間: {end_time - start_time:.6f} 秒")
    

おまけ

チャッピーというと、僕は朽木ルキアに入った義魂丸を真っ先に思い浮かべます。これを言いたいがためにこの記事を書いたのでした。終わり。