強制労働の工場で生まれた問い：トゥランのレンガ工場

1944年7月、ハンガリーの首都ブダペスト近郊のレンガ工場。焼き上がったレンガを積んだ台車がレールの交差に差しかかるたびに跳ね、レンガが地面に散らばりました。

台車を押していたのは、強制労働に駆り出されていた数学者パール・トゥランです。汗をかき、悪態をつきながら、彼はひとつの問いにとりつかれます。「このレールの交差は、最少で何か所まで減らせるのか」。

この問いは「トゥランのレンガ工場問題」と呼ばれ、82年にわたって数学者を退けてきました。2026年10月6日（米国時間）、OpenAIは社内の未公開AIモデルが書いた数学論文群を公開し、その中で、この問題と兄弟分の「ヒルの予想」を両方とも解いたと主張しています。

主張のうち、どこまでが機械で確かめられ、どこからがまだ「主張」にとどまるのか。その答えを読む手がかりは、一度は「解けた」とされながら11年後に穴が見つかった、この問題自身の歴史の中にあります。

トゥランのレンガ工場問題 Executive Summary（情報図解）

レールが交わるたびに台車は脱線した

トゥランは1910年、ブダペストに生まれました。1940年9月、ユダヤ系であることを理由に労働奉仕部隊へ召集され、以後は各地の収容所を転々とします。

レンガ工場の光景は、彼自身が晩年に書いた短い文章に残っています。1977年に創刊された専門誌『Journal of Graph Theory』の巻頭言「A Note of Welcome（歓迎のことば）」です（引用は筆者訳）。

レンガを焼く窯がいくつかあり、焼いたレンガを積んでおく屋外の置き場がいくつかありました。すべての窯は、すべての置き場とレールで結ばれていました。（中略）仕事そのものは難しくありませんでした。厄介なのは交差だけでした。台車はそこでたいてい脱線し、レンガがこぼれ落ちたのです。

時間のロスは、彼らにとって「ここでは語らない理由で」貴重なものでした。そのうえでトゥランは、交差の数を最少にしていればこの損失も最小にできたはずだと考え、「では、交差の最少数はいくつなのか」と問います。

数日考えて、目の前の工場なら改善できることは分かりました。しかし、窯がm個、置き場がn個という一般の場合の厳密な答えは、とても難しく見えました。彼は「家族の身を案じる日々が終わるまで」この問題を棚上げにします。

数学は、その4年前にも彼を支えていました。1940年、線路工事の現場でトゥランの名前を耳にした将校は、たまたま学士院の紀要を刷る印刷所で校正係をしていた人物で、彼の原稿を読んだことがありました。将校はトゥランを木材置き場の案内係に回し、トゥランはそこで紙も使わずに一つの問題を解き切ります。

それが現在「トゥランの定理」と呼ばれる、極値グラフ理論の出発点です。本人はその数日間を、こう書き残しています。

知的な自由、そしてある程度まで抑圧から精神的に解き放たれているという感覚が、この恍惚をいっそう深めました。

3軒の家と電気・ガス・水道

レンガ工場問題の最小のかたちは、多くの人が子どもの頃に一度は挑んだパズルと同じです。3軒の家それぞれに、電気・ガス・水道の3本の線を引く。ただし線どうしを交差させてはいけない。

何度描き直しても、最後の1本がどうしても他の線をまたいでしまいます。平らな紙の上では、交差ゼロは不可能だと証明されています。

窯が3つ、置き場が3つの工場は、このパズルとまったく同じ形をしています。違いは「交差させるな」ではなく「交差を最少にせよ」と問う点です。答えは1回です。

3軒の家と電気・ガス・水道。素直に描くと交差9回、置き方を工夫すると1回

一般の場合を頭に描くには、点を2列に並べるのがいちばん簡単です。上の列に窯をm個、下の列に置き場をn個並べ、上の点すべてと下の点すべてを線で結びます。線は全部でm×n本になります。

このとき点はどこに動かしてもよく、線も自由に曲げてよいものとします。そのうえで、線どうしの交差の数を最少にする描き方を探すのがレンガ工場問題です。数学の言葉では、この図形を「完全二部グラフ K(m,n)」、交差の最少数を「交差数」と呼びます。

上の図の左側のように、2列のまま直線で結ぶと、3×3でも交差は9回になります。右側のように点の置き方を変えるだけで、交差は1回まで減ります。どこまで減らせるかは、置き方の工夫しだいです。

十字に振り分ければ交差は減る

1952年、トゥランはポーランドを訪れ、講演でこの問題を紹介しました。それを聞いたポーランドの数学者カジミェシュ・ザランキェヴィチとカジミェシュ・ウルバニクは、それぞれ独立に答えを発表します。

ザランキェヴィチの描き方は、驚くほど単純です。紙に十字の線を引き、窯を横の線の左右に半分ずつ、置き場を縦の線の上下に半分ずつ置いて、すべて直線で結びます。

ザランキェヴィチの描き方。窯4つと置き場7つで交差18回

この描き方で生まれる交差の数は、次の式で計算できます。⌊ ⌋は「小数点以下を切り捨てる」という記号です。

Z(m, n) = ⌊m/2⌋ × ⌊(m−1)/2⌋ × ⌊n/2⌋ × ⌊(n−1)/2⌋

計算は見た目より簡単です。片側の数を半分にして切り捨てた値と、1つ減らしてから半分にして切り捨てた値を掛けます。これを両側で行い、最後に掛け合わせるだけです。

3×3（3軒の家）：(1×1)×(1×1)＝1
2×n：点が2個の側が(1×0)＝0なので、相手が何個でも交差ゼロで描ける
4×7（上の図）：(2×1)×(3×3)＝18
10×10：(5×4)×(5×4)＝400

ザランキェヴィチは1954年、この描き方が最良であり、どんな描き方でもこれより交差は減らせないという証明を論文として発表しました。問題は、ここで一度「解決済み」になったのです。

「描ける」と「それ以下は無理」は別の仕事

ここで、この問題の本当の難しさが顔を出します。「交差18回で描ける」と示すには、実際に1枚描いて見せれば十分です。

一方、「17回以下では絶対に描けない」と示すには、考えうるすべての描き方を一つ残らず排除する必要があります。点の置き場所は無数にあり、線はどれほど曲がりくねっていても許されます。

数学では前者を「上界」、後者を「下界」と呼びます。上界は具体例ひとつで足りますが、下界は「どんな工夫をしても無理」という全否定です。

上界は1枚描けば示せるが、下界はすべての描き方を相手にする

今回のOpenAIの論文自身も、「決まった描き方の交差を数えても上界しか得られない。すべての描き方にわたる最小値を確定するには、下界の議論が別に要る」と明記しています。

11年間誰も気づかなかった証明の穴

ザランキェヴィチの証明は、権威ある学術誌『Fundamenta Mathematicae』に載り、10年以上にわたって定理として扱われました。穴を見つけたのは、1965年のポール・ケイネンと1966年のゲルハルト・リンゲルです。2人はそれぞれ独立に、帰納法の一部が成り立っていないことに気づきました。

証明は、点の数を増やしながら結論を積み上げる帰納法の形をとっていました。点の数が奇数から偶数へ進む段は正しかったものの、偶数から奇数へ進む段が成立していなかったのです。

この顛末を、英国生まれの数学者リチャード・ガイは1969年、「ザランキェヴィチの定理の衰亡（The decline and fall of Zarankiewicz's theorem）」という題の論文にまとめました。「定理」は「予想」へと格下げされます。

ザランキェヴィチ自身は、この穴が見つかる前の1959年に亡くなっています。彼も戦争の傷を負った一人で、ドイツ占領下で禁じられた地下教育に携わり、強制収容所へ送られた経験を持っていました。

1977年の巻頭言で、トゥランはこう書いています。

しかしリンゲルが、公表された証明に穴を見つけました。多大な努力にもかかわらず、その穴はいまだ誰にも埋められていません。

少しずつ埋まっていった地図

穴が見つかった後の半世紀は、正しいと確かめられた範囲を少しずつ広げる歴史でした。

1970年：ダニエル・クライトマンが、片側の点が6個以下なら式が正しいことを証明
1993年：ダグラス・ウッドールが、7列×7〜10などの場合をコンピュータで確認
2006年：ド・クレルクらが、大きな場合でも式の値の少なくとも83%の交差は避けられないことを証明
2023年：バログらが、両側の点数が等しい場合についてこの割合を約91%まで引き上げ

クライトマンはさらに、もし式が間違っている例があるなら、その最小の例では両側の点の数がどちらも奇数になることも示しています。それでも、全ての場合を覆う証明は空白のまま残りました。

この問題には兄弟分がいます。2列に分けず、n個の点のすべての組を線で結ぶ「完全グラフ」の交差数です。こちらの予想式を最初に見つけたのは数学者ではなく、英国の構成主義の画家アンソニー・ヒルと、友人の米国人画家ジョン・アーネストでした。

1959年春までに2人がたどり着いた式は、ガイが1960年に論文で紹介し、1963年にはヒル自身が数学者フランク・ハラリーと共著で発表しました。これが「ハラリー＝ヒル予想（ヒルの予想）」です。式が予言する交差数は、点が5個から14個までで、1、3、9、18、36、60、100、150、225、315と続きます。

ヒルの式どおりの描き方。8個の点を一直線に並べ、線を上下に振り分けると交差18回

こちらも、正しいと確かめられたのは点が12個まで（2007年、パンとリクター）と、13・14個（2021年、アイヒホルツァー）です。どちらもコンピュータの力を借りた証明でした。ガイは2020年3月に103歳で、ヒルは同年10月に90歳で亡くなっています。

1940年から2026年までの年表

OpenAIは何を「解いた」と主張しているのか

OpenAIが公開したのは、GitHub上のリポジトリ「openai/math」です。722本の論文を372の「結果ファミリー」に束ねたもので、READMEによれば、モデルには約4,000問の未解決問題が投げられ、1件あたり平均でChatGPT Proの思考およそ3時間分の計算が使われました。

レンガ工場問題はその165番目に載っています。見出しは「ハラリー＝ヒルとザランキェヴィチの交差数公式」で、説明文は次のとおりです。

ハラリー＝ヒル予想と、ザランキェヴィチの定式化によるトゥランのレンガ工場問題を解決し、すべての完全グラフと完全二部グラフの交差数を決定する。

主張の範囲は、文字どおり「全部」です。

レンガ工場問題（ザランキェヴィチ予想）：すべての正の整数m、nについて、交差数はZ(m, n)に等しい
ヒルの予想：すべての点の数nについて、完全グラフの交差数はヒルの式に等しい

2026年以前に確かめられていた範囲と、今回の主張

これを支えるのは、どちらも著者名が「OpenAI」、日付が2026年9月23日の2本の論文です。完全グラフの論文が13ページ、二部グラフの論文が16ページと、半世紀の難問の証明としては短い部類に入ります。

ヒルの予想について、これまですべてのnで示されていたのは、「点を一直線上に並べ、線をその上下に振り分ける描き方に限れば」といった、描き方に制限をつけた場合でした。今回の論文は制限をつけず、描き方そのものを代数の情報に置き換えます。

具体的には、2本の線がどちら向きに交差したか、各点のまわりで線がどんな順番で出ていくかを数の表（行列）に書き込み、線形代数の不等式に持ち込みます。論文自身の言葉を借りれば、「描画の幾何を、2つの線形代数の命題から切り離す」証明です。

Leanが確かめたこととまだ確かめられていないこと

今回の主張を、ありふれた「AIが難問を解いた」という話と分けているのは、Leanによる形式証明が付いている点です。Leanは、数学の証明を一行ずつコンピュータに検査させるためのプログラミング言語です。

Leanの上では、「ここは明らか」という省略も、権威ある学術誌への信頼も、検査の前では無力です。ザランキェヴィチの証明のような帰納法の穴があれば、そこで検査が止まります。

リポジトリの説明（lean/docs/165.md）によれば、形式化の範囲は次のとおりです。

ヒルの予想：点の数nが3以上のすべての場合について、交差数がヒルの式に等しいことを証明。下界の証明に加え、式どおりの交差数で描ける図も実際に構成
ザランキェヴィチ予想：すべての正の整数m、nについて等式を証明し、式の値を達成する描き方も構成

形式化された「交差数」の定義も、課題ファイルで確認できます。点は平面上の相異なる位置に置き、線は自分自身と交わらない連続な曲線であれば、どれほど曲がっていてもよいとされています。

交差は有限個で、接するだけの接点や3本が1点で交わる描き方は除き、同じ2本が何度交わっても毎回1回と数えます。これは交差数の研究で標準的に使われてきた約束事です。

公開されたファイルの規模は、二部グラフ側が339ファイル・約2万600行、完全グラフ側が46ファイル・約1万8,000行です。両方のフォルダを検索した範囲では、証明を飛ばすための「sorry」も、独自の公理の追加も、0件でした。

一方で、Leanのチェックが保証しないこともはっきりしています。

命題が正しく書けているか：Leanが確かめるのは「形式化された命題」と「形式化された証明」が噛み合っていることまでです。その命題が数学者の言う予想と本当に同じかを判断するのは、人間の読み手です
第三者による再検証：2026年10月7日時点で、外部の研究者がこの検証を自分の環境で走らせたという報告は、確認できた範囲ではゼロです
論文の査読：13ページと16ページの論文本体は、査読前の段階です
新しさと功績の帰属：アイデアが本当に新しいのか、既存研究の組み合わせなのかは、Leanの守備範囲の外です

どこまで確かめられているか（2026年10月7日時点）

マサチューセッツ工科大学の数学者アンドリュー・サザーランドは、今回のリリース全体について、Scientific Americanの取材に「モデルが公開され、人々が結果を再現できるようになるまでは、単一のエージェントが一発で問題を解いたという主張は未検証として扱うべきです。証拠を求めるべきです」と語っています。今回の165番について、専門家による個別の論評は、10月7日時点で確認できた範囲ではゼロです。

主張と証明の距離を示す前例もあります。2018年には、2人の研究者が工学系の学術誌で、2つの予想の公式をどちらも示したと主張する論文を出しました。OpenAIの論文はこの論文に触れたうえで、決まった描き方を数えるだけでは下界にならないと指摘しています。

11年の穴と機械の検算

ザランキェヴィチの証明が11年間生き延びたのは、読んだ人々が、権威ある学術誌と高名な数学者の名前を信頼したからです。人間の査読は、ときに信頼で穴を見落とします。

Leanが信じるのは、一行ずつの検査の結果だけです。皮肉なことに、AIが書いた今回の証明は、70年前に人間が書いた証明が一度も受けなかった種類の検査に、最初からかけられる形で差し出されています。

ただし、問いの形は変わります。「証明は正しいか」の多くを機械が引き受けるぶん、「そもそも正しい問いを証明したのか」「その証明に新しい発想はあるのか」という問いが、人間の側に残ります。

この構図は、数学の外にもそのまま当てはまります。AIが書いた報告書やコードを受け取る場面でも、少なくとも3つの層を分けて読む必要があります。

主張：AIが「できた」と言っていること
機械で検証された範囲：テストや形式検証が実際に通った部分
人が判断すべき範囲：問いの立て方は正しいか、本当に役に立つか

「上界と下界」の違いも、会議室でそのまま使える物差しです。「この施策で経費を2割削れました」は、成功例を1つ示せば言えます。「これ以上はどうやっても削れません」は、すべての代替案を潰さなければ言えないはずの、ずっと重い主張です。

82年後に届いた返事

トゥランは「歓迎のことば」を、こう結んでいます。

この雑誌で、ほかの多くの重要な成果とともに、上に挙げた未解決問題の解決を読めることを願い、望みながら、筆を置きます。

この文章が雑誌に載ったのは、彼の死後のことです。1976年9月26日、白血病のため66歳で亡くなっていました。妻で数学者のヴェラ・ショーシュは病名を本人に伏せ、盟友ポール・エルデシュは後年、トゥランが仕事を「後回し」にしたまま世を去ったことを惜しんでいます。

台車が脱線してから82年。返事は、トゥランが望んだ専門誌ではなく、GitHubのリポジトリに、機械が書いた形で届きました。それがトゥランの待っていた答えかどうかを決めるのは、Leanの検査結果を読み、論文を読み込む人間の数学者です。