…そして証明はLeanで検証済み
“…and the proof is checked in Lean” (xenaproject.wordpress.com)
要約
この記事は、「Leanで検証された」という形式の主張をどのように解釈すべきかを解説しています。Leanコードから重要な情報を抽出できますが、AI生成コードの場合は事前のテストが必要です。OpenAIの定理ダンプなど、多くのケースでこれらのテストはまだ体系的に行われていません。
全文翻訳
“…そして証明はLeanで検証済み”
この記事は、「この定理はLeanで検証されたため正しい」という形式の主張を、簡単な言葉でどのように解釈するかを説明する試みです。要点は、Leanコードから抽出できる重要なシグナルがありますが、もしそのコードがAI生成されたものであれば、まずいくつかのテストを行う必要があります。ここではそのテストを説明し、多くのケース(OpenAIの定理ダンプなど)では、これらのテストがまだ体系的に行われていないことを指摘します。
はじめに
先月、OpenAIは722本の数学論文からなる定理ダンプを公開しました。そのうち約45%にはLeanコードが付属していました。その後、(Lean化されていない)論文のうち3本が符号エラーのため撤回されました。これに対し、「Leanでコード化された論文は、Leanの仕組み上、間違いなく正しいだろう」と言う人もいるかもしれません。あるいは、「Leanには健全性バグがあり、他にも存在する可能性があり、AIはハックを助長するかもしれないので、Leanによる検証はあまり意味がない」と言う人もいるかもしれません。驚くことではありませんが、真実はもっと微妙であり、この記事はその説明を試みるものです。
この記事は、特にAI生成されたLeanリポジトリに関して、この形式の正しさの主張を始める前に、尋ねるべき4つの質問の連続として構成されています。そして始める前に、OpenAIの定理ダンプの多くの論文について、これらの質問がまだすべて肯定的に答えられていないことを強調しておきます(ただし、これらの質問に答えることを妨げるものは何もありませんし、以下のテストのいずれかが失敗する理由も私にはありません。単に人々がまだそれを行っていないだけです)。
質問1. Leanのステートメントは非公式なステートメントと一致しますか?
Leanリポジトリには通常、「ヘッドライン定理ステートメント」があります。これは、定理のステートメント(証明ではなく!)を定義するコンピュータコードになります。ここではステートメントと証明の間に大きな違いがあることに注意してください。例えば、以下は数学的ステートメントを定義する、完全にコンパイル可能なLeanコードです。
import Mathlib
def is_fermat_last_theorem (a b c n : ℕ) : Prop :=
n ≥ 3 ∧ a^n + b^n = c^n
#check is_fermat_last_theorem
このコードはLeanの数学ライブラリ Mathlib をインポートし、一見するとフェルマーの最終定理のように見える数学的ステートメントを定義していますが、実際には自明に偽のステートメントです。なぜなら、Leanでは ℕ は 0 を含むため、a = b = c = 0 かつ n = 3 とすると反例が得られるからです。これはステートメントがコンパイルするのを妨げません!しかし、このステートメントの証明がコンパイルされるのを妨げるでしょう。Leanは定理のステートメントと定理の証明を注意深く区別しますが、人間は両方のアイデアを「定理」と呼ぶのが得意です。
PDFにLeanコードが付属している場合に、その正しさを判断する際に最初に尋ねるべき質問は、「Leanコードにおける定理のステートメントは何であり、それはPDFの実際の定理ステートメントに対応していますか?」ということです。人間でLeanの専門家であれば、通常(常にではないが)この質問に簡単に答えることができます。例えば、Leanに精通した人間の数学者であれば、上記の2行のコードを読んで、これがフェルマーの最終定理の誤ったステートメントであると観察できるでしょう。
しかし、物事は常にこれほど簡単ではありません。現在、利用可能なライブラリの制約により、形式化された定理のステートメントを理解するためだけに、何千行ものコードを読む必要がある場合があります。現在、これの例は、Hodge予想のステートメントのLean形式化を含む、DeepMindのFormal ConjecturesリポジトリへのPRです。執筆時点では、そのステートメントは、ステートメントを作成するために必要なサイクルクラスマップなどの定義がまだ Mathlib にないため、Mathlib の上に構築された10,000行以上のコードに依存しています(Mathlib は注意深く人間専門家によってチェックされており、信頼できます)。もう一つの例は、Axiomによる有限単純群の分類の形式的に検証された証明の最近の発表です。Axiomのシステムが証明したステートメントは、Tau CetiにあるLeanコードにあります。Tau CetiはAI生成されたLeanコードのライブラリです。ステートメントを含むファイルは、Tau Cetiの250K行以上のLeanコード(900ファイル以上)をインポートしています。そのうち、約5600行のコードが重要です。なぜなら、それらはすべての関連する定義(例えば、ほとんどがまだ Mathlib にない、すべての孤立単純群の定義)を含んでいるからです。人間のチェックなしでは、これが本当に分類の正しいステートメントであると確信することはできません(そして、Tau Cetiにおける孤立単純群の定義が正しいと注意深くチェックしたと主張する人間にはまだ会ったことがないことに注意してください)。実際、このステートメントが正しく形式化されているという最も強力な証拠は、Axiomのコードがそれを証明しているということです!
OpenAIの定理のうち、Leanコードが付属している290件のうち、約38件は、Leanコードが論文の主要な定理をステートメントとしてさえ示しておらず、ましてや証明していないという特性を持っていることに言及する価値があります。そしてOpenAIは決してそう主張していません!彼らは単に「ここに論文に付属するLeanコードがあります」と言っただけです。時にはコードは中間的な結果をステートメントとして示し、証明するだけです。私の印象では、OpenAIは一部の形式化が不完全な段階で公開することにしたため、持っているものをそのまま公開したということです。具体的な例を挙げると、論文194は、可換代数におけるLechの倍数予想を、次元、剰余体、または標数の制限なしに証明すると主張しています。この問題は1960年から未解決です。対応するLeanコードのヘッドライン定理は、論文の補題5.4であることが確認できます。これはすでに印象的な成果ですが、ヘッドラインの結果ではありません。
質問2. コードはコンパイルされますか?
定理のLeanコードが証明しようとしているステートメントを理解したと確信したら、あなた(あるいは、コードベースが巨大な場合は、強力なマシンにアクセスできる友人の一人)は実際にコードをコンパイルする必要があります。
AnthropicがLeanでフェルマーの最終定理の証明を形式化したとき、彼らは私が生成された1300万行のコードを見るように頼みました。私はそれを自分のマシンにダウンロードし、サンドボックスに入れ(AI生成コードが何をするかわからない、理論的にはあなたのファイルをすべて削除する可能性があるため)、コンパイルを試みました。すぐにメモリ不足になりました。私はAnthropicに、コードベースがコンパイルされるのを見ることができない限り、彼らの行ったことについて何も主張できないと伝えました。彼らは私に96コアと500GBのRAMを持つマシンへの一時的なアクセスを提供してくれました。それからコードをコンパイルすることができました。
もちろん、より合理的なサイズのコードベースであれば、合理的なサイズの mesin でコードをコンパイルすることが可能です。例えば、OpenAIによるナビエ・ストークス問題の解決は640K行のコードで、私のラップトップで問題なくコンパイルできます。
再度強調する価値があるでしょう:サンドボックス化しない限り、ランダムなLeanコードをローカルマシンで実行しないでください。Leanの数学ライブラリは、人間がキュレーションし、人間の専門家によってチェックされているため、実行およびビルドするのは安全です。AI生成コードはそうではありません。
質問3. コードはステートメントとして示された定理を証明しますか?
定理のステートメントを確認することの重要性については、質問1で既に述べました。これにより、コードが正しいことを証明していることを確認できます。しかし、ここには追加の複雑さがあります。理想的には、定理のステートメントは、Mathlib 以外のインポートが非常に少ないファイルに含まれているべきです。そうすれば、それを信頼できることがわかります。しかし、定理の証明は、誰も読みたくない何千、あるいは何百万もの行のコードを必然的にインポートします。証明ファイルの何百万行ものコードの中に、x^n を 37 として再定義し、それゆえ a^n + b^n ≠ c^n は左辺が 37+37=74 で右辺が 37 であるため真であると証明するようなトリックが隠されていないと、どうやって確信できるでしょうか?あるいは、定理が真であるという新しい公理を数学に追加するようなトリックはどうでしょうか?別の言い方をすれば、信頼できるコードのみをインポートした Challenge.lean ファイルと、定理のステートメント、そして信頼できないインポートを何百万行もインポートし、定理の証明を示し、見た目は同一である Solution.lean ファイルがある場合、何百万行ものコードのどこかに、ステートメントの意味を変更したり、数学の公理からルールを変更したりするハックがないと、どうやって確信できるでしょうか?
一言で答えれば:lake comparator です。この答えについてはこちらで詳しく読むことができます。しかし要するに、このツールは、信頼できるファイルでステートメントとして示された定理と、信頼できないインポートを通じて証明された定理が同一であり、証明には数学の公理のみが使用されていることをチェックします。
質問4. コードはLeanの公式カーネルのバグを悪用しますか?
これは起こり得ます。Leanのカーネルには健全性バグがあり、発見から4時間後に修正されました。その後、OpenAIによるLeanのコードベースのレビューで、さらにいくつかのバグが見つかり、すべて公表前に修正されました。理論的には、Leanのカーネルにさらに健全性バグが存在する可能性があります。しかし、それは問題ではありません。
なぜ問題ないのでしょうか?なぜなら、Leanには現在、ユーザーによって作成された多くのカーネルがあり、多くの異なる言語で書かれており、少なくとも1つはアセンブリレベルまでバグがないことが形式的に検証されているからです。もし、リワードハッキングがないことを絶対に確実にするなら、ここでも一言で答えられます:lake comparator --paranoid です。まだ発見されていないLeanの公式カーネルのバグを悪用する悪意のあるコードは、まだ発見されていない多くの独立したシステムのバグをすべて同時に悪用しない限り、このテストに合格しません。例えば、Leanカーネルアリーナのこのウェブページは、OpenAIによるナビエ・ストークス問題の解決が、Leanの公式カーネルだけでなく、複数のカーネルによって受け入れられていることを示しています。
最後に一言
Leanコードがコンパイルされ、これらのテストすべてに合格し、したがって定理の正しい証明である可能性が非常に高い場合でも、対応するPDFにも正しい証明が含まれているとは限りません!ナビエ・ストークスが翻訳で失われた論文は、ナビエ・ストークスの記述に関して、実際にはその逆を示しています。上記のすべてのテストはナビエ・ストークスの作業に対して実行されましたが、PDFの証明とLeanの証明が分岐するインスタンスがあります。これらの場合、PDFの証明が大丈夫かどうか、誰が知っているでしょうか!私の理解では、一部の専門家は、PDFを読み通すのではなく、AIを使用してLeanの証明を英語に非形式化し、議論を読んでいるとのことです。
要約/結論
「Leanで検証されているから真実だ」というのは、意味のあるものにすることができます。しかし、「Leanコードがコンパイルされる」以上の作業を行う必要があります。最先端のAIモデルは、これらの作業すべてを行うことができます。しかし、それらは実行される必要があり、(証明に含まれるLeanコードの量によっては)計算コストが高くなる可能性があります。