合同数について

定理 100万(10⁶)以下の自然数が合同数か否かは全て決定された.

合同数とは3辺の長さが全て有理数であるような直角3角形の面積となるような 整数のことであり, それらを全て決定するという問題は古くから考えられて来ました. 例えば3辺の長さが3,4,5の直角3角形の面積は6なので6は合同数であることはすぐにわかりますが, 3辺の長さが全て有理数でかつ面積が1となる直角3角形は存在せず, 1が合同数ではないことはFermat(フェルマー)によって示されていました. (3辺の長さが1,2,√5 であるような直角3角形の面積は1ですが, √5は無理数です.) これまでに, 素因数の個数やそれらを8で割った余りに制限を付けた整数が 合同数であるかどうかを調べた結果や(例えば8で割って3余る素数は合同数ではないなど), 合同数である(ない)ための判定条件などといった結果は数多く得られていますが, 今のところ, 与えられた自然数が合同数か否かを確かめるアルゴリズムは知られていません. (下に書くTunnellさんの結果はそれに近いものを与えていますが.)

合同数を小さい方から全て決定していくという試みも, 計算機の性能の向上とともに 進められていったのですが, 出版されている論文で一番広い範囲で決定を 行っているものは

F. Nemenzo: All congruent numbers less than 40000, Proc. Japan Acad. Ser. A, 74 (1998), 29-31.

ではないかと思います. この論文では42552以下の合同数, 非合同数を全て決定しています. その後10年近い月日が経っていますので, もう少し広い範囲で 決定がなされているかもしれませんが(例えば42553が合同数であることは わかっていました), 10万まででも完全に決定したという報告は (論文でもwebページなどでも)見当たりません. (もし既にどこかで公表されているようでしたら, 教えて頂けると助かります.)

次の結果は知られていました.

予想 8で割った余りが5,6,7となる自然数は全て合同数である.
定理 (Elkies) 100万以下の自然数に対し, 上の予想は正しい.

このElkiesさんの結果は研究集会ANTS-Vで 発表され, その報告集にも原稿が掲載されています. (preprint版はここで手に入ります.) Elkiesさんが作成している 計算数論のページでも 解説や計算結果を見ることが出来ます.

直角3角形の全ての辺の長さをn倍にすれば面積はn²倍となるため, 合同数となるかどうかは平方数を掛けても変化しないことは明らかです. そこで, 最初に述べた定理を確かめるためには, Elkiesさんの結果を認めると, 後は

(@) 平方因子を持たず, 8で割った余りが1,2,3

という条件を満たす100万以下の自然数に対して, それが合同数かどうかを 調べれば良いわけです. (Elkiesさんが扱った場合とは違い, 合同数となる場合もならない場合もあります.) 今回はその計算を, いくつかのソフトを利用して実行しました. 具体的な計算手順は以下の通りです.

1. Tunnellの結果を利用して, 100万以下の合同数の候補および非合同数を全て決定する.
   ここにあるように, 自然数nが合同数であることは y²=x³-n²x という方程式が y≠0 であるような 有理数解(x,y)を持つことと同値です. このような方程式が定める平面上の曲線は 楕円曲線 と呼ばれ, そのような有理数解の存在は その楕円曲線の「Mordell-Weil群の階数」が正であること, とも言い換えられます. 更に, (100万ドルの賞金がかかっていることでも有名な) Birch, Swinnerton-Dyer予想が正しければ, その楕円曲線に付随するL関数の中心値と呼ばれる値が0になることとも同値です. Tunnellさんは論文

   J. B. Tunnell: A classical Diophantine problem and modular forms of weight 3/2, Invent. math. 72 (1983), 323-334.

   において, 自然数nに対応する楕円曲線のL関数の中心値が0になるかどうかを 有限の時間で判定するアルゴリズムを与えました. つまりBirch, Swinnerton-Dyer予想が正しいという仮定の下では, 与えられた自然数が合同数であるか否かを(比較的容易に)判定できる訳です. このアルゴリズムをCで実装し, 条件(@)を満たす100万以下(実際には1000万以下)の 自然数に対して計算を行いました. この計算によりそれらの自然数が合同数と非合同数の候補に分けられるのですが, 非合同数と判定された数はBirch, Swinnerton-Dyer予想に関する

   J. Coates and A. Wiles: On the conjecture of Birch and Swinnerton-Dyer, Invent. math. 39 (1977), 223-251.

   の結果により, 実際に非合同数となることが保証されています. つまり後は合同数候補が実際に合同数であることを確認すれば良い訳です.

2. 1.の合同数候補が実際に合同数であるかどうかを mwrank を 用いて調べる.
   合同数の候補の自然数nが実際に合同数であることを示すためには, 3辺の長さが有理数で面積がnの直角3角形を見つけてしまえば良いのですが, 手がかりなしではなかなか大変です. 例えば41は条件(@)を満たす2番目に小さい合同数候補ですが, 面積が41の直角3角形は一番見つけ易そうなもので, 3辺の長さが 1023/40,3280/1023,1054721/40920となります. これくらいであれば計算機を少し走らせれば見つけられると思いますが, そのような方法では10000以下の合同数を全て決定することも難しいと思われます. しかし, 合同数であるかどうかを楕円曲線の話に翻訳し, 近年著しく発展している楕円曲線のMordell-Weil群の「explicit descent」に関する 理論やその周辺の結果を利用することで, 合同数であることの確認 (y²=x³-n²x の有理数解(x,y)の探索)を 効率良く行うことが出来ます.
   Cremonaさんが開発している mwrank は 2-descent によって 楕円曲線のMordell-Weil群を計算するというプログラムです. この mwrank によりステップ1の合同数候補に対応する楕円曲線のMordell-Weil群の 計算を行い, 実際に合同数となっているかどうかの確認を行いました. これにより候補の大半(9割以上)は合同数であることを確認できますが, 確かめられない(時間がかかり過ぎる)ものもいくらか残ります.
3. 2.で残った合同数候補を Magma の FourDescent コマンド等を 用いて調べ, 合同数を全て決定.
   Magma はシドニー大学の計算代数グループによって開発が行われているソフトウェアで, 整数論や代数幾何などに関連する計算を幅広く行うことが出来ます. 楕円曲線に関するコマンドも多数用意されており, 有償ですが大変便利なソフトです. (別に宣伝するつもりではないですが..) そのMagmaに実装されているFourDescentというコマンドは, その名の通り楕円曲線のMordell-Weil群の4-descentを行うもので, その他の関連するコマンドと組み合わせることで 2-descentでは 手が届かないような楕円曲線上の有理点(楕円曲線を定める方程式の有理数解)でも いくらか発見出来る場合があります. ステップ2で残った合同数候補の楕円曲線に対してそれらのコマンドを適用したところ, 全てで有理点を発見することが出来, めでたく全て合同数であると確認できました. (ただし, ちょっとした工夫が必要な場合もありました.) なお, 4-descentは2-descentを更に先に延ばす計算であり, いきなり4-descentだけを 行うというわけではありません. 特にMagmaにも2-descentを行うコマンド(TwoDescent)があり, それを行った後に4-descentへと進むことになります. その意味ではステップ2での計算を Magma で行うことも可能なのですが, 計算速度や信頼性の点から, そちらでは mwrank を利用しました.
4. データを整理し, Magma および Risa/Asir を 用いて再確認.
   これまでの段階で合同数かどうかの判定は全て終わっているのですが, 念のため, データの整理とともに, 合同数であると判定されたものに対して, 見つかった y²=x³-n²x の有理数解が 本当に解となっているかどうかの再確認を行いました. この確認は(少々大きな)有理数の計算さえ出来れば十分なので, 様々なソフトで行うことが出来るのですが, 使い慣れている Magma と Risa/Asir を利用しました. この確認で間違いは見つかりませんでした.

1-10m 10m-20m 20m-30m 30m-40m 40m-50m 50m-60m 60m-70m 70m-80m 80m-90m 90m-100m

各圧縮ファイルにはそれぞれ以下の3つのファイルが含まれています.

• congr-**-** : その範囲の合同数一覧 (空白区切り)
• noncongr-**-** : その範囲の非合同数一覧 (空白区切り)
• **-**_?.list : 合同数であることの検証データ. フォーマットは以下の通り:
  合同数, Mordell-Weil群の階数の上限, 同下限, x座標1, y座標1, x座標2,…

範囲	1-10m	10m-20m	20m-30m	30m-40m	40m-50m	50m-60m	60m-70m	70m-80m	80m-90m	90m-100m
(@)を満たす自然数	30389	30393	30398	30392	30401	30393	30400	30384	30418	30379
合同数	3660	3228	3045	2909	2773	2718	2680	2630	2592	2498
非合同数	26729	27165	27353	27483	27628	27675	27720	27754	27826	27881

となりました. ただし, 今回の計算は「合同数であると予想されるものが実際に合同数であることを確認する」 ところに意味があり, 個数がこのようになることは (計算が間違っていなければ)既に知られていたことだと思われます.

上にも述べた通り, 自然数nが合同数であることは, 楕円曲線 y²=x³-n²x がy≠0なる有理点(x,y)を持ち, Mordell-Weil群の階数が正となることと同値です. つまり検証データにおいてはMordell-Weil群の階数の下限が0でないことが 合同数であることを意味しています. それに続く数値が y²=x³-n²x の有理数解(x,y)であり, この関係式を使えば 面積がnとなる直角3角形を与えることも出来ます. このように, 合同数であることは(それが大変なのですが)直角3角形(もしくは 楕円曲線の有理点)を見つけてしまえば, 確認すること自体は難しくありません. 一方, 合同数でないことを確かめるには何らかの方法で直角3角形の非存在を 証明しなくてはならないため, 一般には簡単ではないはずなのですが, 先に述べたTunnellさんらの結果により, さほど大きくない(例えば1000万程度までの)数であれば 単純な計算で確認することが出来ます. つまりここに挙げた計算結果は簡単にチェックすることが可能です. どなたかチェックして頂けたら (そして間違いがあったらご指摘頂けると) とてもありがたいです. (合同数の方の検算はステップ4で検算をしましたが, 非合同数の方は特に検算をしていません.)

もうお気づきかもしれませんが, 今回の計算は既に知られている結果, アルゴリズム, そしていくつかのソフトに実装されているコマンドなどを 単純に組み合わせて利用しただけであり, 数学的に, もしくは計算の面において, 何か新しいこと開発したというようなことは一切ありません. 計算機やソフトウェアなどの性能向上と数学自体の進歩によって, これくらいのことならばさほど苦しまなくても出来るようになっていることに驚き, きりの良いところまで計算してまとめておこうと思ったのが, このページを作った動機です. なお, ほとんどの計算は1台のPCで行いました(2005年末と2006年5月). 気が向いたときに少し計算を進める, というようにしていたため 総計算時間はよくわかりませんが, 90万-100万の計算で丸1日くらいだったと思われます. (もっと新しいのPCなら倍以上の早さで計算できそうですが..) それだけ聞くともっと先まで計算を伸ばせそうに思えるかもしれませんが, 後半はかなり手強い例も現れていましたので, 次にきりの良い10⁷まで全て決定するというのは (今の段階では)簡単ではないだろうと思います. (Elkiesさんが扱った場合も計算が残っているはずですし.)

計算データに関する注意

• ステップ2で利用した mwrank はwindows版を自らコンパイルするのが面倒だったので, Steinさんが開発している SAGE のパッケージとして 組み込まれているものを利用しました. (SAGE本体は今回の計算には使っていません.)
• mwrank は -S 0 オプションを付けて計算しています. 特に, 得られた有理点はMordell-Weil群の階数が確定している場合でもMordell-Weil群の 生成元とはなっていないものが大部分であると思われます. (つまりもっと「複雑でない」有理数解がある可能性が高いということです.)
• Mordell-Weil群の階数の上限はmwrankの結果を採用しています. 4-descentを使って上限をより良く出来る場合もあるのですが, MagmaのFourDescentコマンドにはいくつかバグがあったようで, 明らかにおかしな出力を返す場合がありましたので, 今のところデータには反映させていません. (計算はV2.12-19で行いました. 最新のV2.13でバグが完全に直っているかは確認していません.) mwrankの結果に間違いが全くないかどうかはわかりませんが, かなり長く使われてきた プログラムですので, 信頼度は高いと思われます.
• バグがあると思われるコマンドを利用した訳ですが, 一旦有理点(有理数解)が見つかってしまえば, それに間違いがないかどうかは 容易に確認できますし, そのバグは(少なくとも合同数であるかどうかには)影響しません. (「あるはずの有理数解がないと判定されてしまう」という方向のものです.)