On the Guy-Kelly Conjecture for the No-Three-In-Line Problem

この論文は、No-Three-In-Line 問題における Guy-Kelly の予想に関する誤りをガボール・エッルマンが 2004 年に発見した経緯と、その誤りの具体的な場所および修正された上界の導出について、以前文献で詳述されなかった詳細を明らかにするものである。

要約

この論文は、数学の「パズル」のような問題について書かれた、少し専門的ですが非常に面白い内容です。専門用語を抜きにして、**「点と線のゲーム」**という物語として、わかりやすく説明しましょう。

1. 問題の舞台：「点の森」と「三人組」

まず、想像してみてください。
広大な正方形の広場（グリッド）に、$n \times n$ 個の「点」が整然と並んでいます。
ここで、あるルールがあります。

「この広場から、できるだけ多くの点を選びなさい。ただし、選んだ点の中から『3 個』を選んで、それらが一直線に並んではいけません」

これが**「ノ・スリー・イン・ライン（3 点一直線なし）問題」**です。
例えば、将棋の盤面や、ドット絵のマス目のようなイメージです。

• 簡単なルール： 横一列、縦一列、斜め一列に 3 個並ぶのは NG です。
• 目標： できるだけ多くの点（人数）を、このルールを守って広場に配置したい。

2. 昔の予想：「2 倍」の壁

これまで、数学者たちはこの問題について長い間議論してきました。

• 簡単な上限： 「横一列に 2 人までしか座れない」と考えると、最大で「2 倍（$2n$）」の人数までなら配置できそうです。実際、小さい盤面（64 マス以内）では、この「2 倍」の人数を達成できていました。
• ギイとケリーの予想（1968 年）： しかし、盤面が無限に大きくなるとどうなるか？
  有名な数学者ギイ（Guy）とケリー（Kelly）は、ある**「確率の計算（推測）」**を使って、実は「2 倍」よりも少し少ない人数が限界だと予想しました。
  彼らが導き出した「魔法の数字」は、およそ $1.814 \times n$ でした。
  （※元の論文では、円周率 $\pi$ やルート 3 を使った複雑な式で表されています）

3. 発見された「小さなミス」

しかし、2004 年、ガボール・エランマンという研究者が、ギイとケリーの計算の中に**「小さなミス」**を見つけました。

彼らの計算は、**「点を選ぶ確率」**をシミュレーションするものでした。

• 彼らの間違い： 計算の途中で、**「2 人（2n）」**という固定された数字を使って計算してしまっていたのです。
• 本当の状況： 実際には、**「k 人（kn）」**という、変化する人数で計算すべきでした。

これを例え話にすると、

「お菓子を取り合うゲームで、『2 人』が参加する時の計算式を使って、『10 人』が参加する時の結果を推測してしまった」
というようなミスです。

この「2 人」と「k 人」の入れ違いが、最終的な答えを少しだけ歪めていました。

4. 修正された答え：より正確な「魔法の数字」

このミスを修正すると、ギイとケリーの予想は少し変わりました。

• 元の予想： 約 $1.814 \times n$
• 修正後の予想： 約 $1.814 \times n$（数値は同じに見えますが、導き出される式がシンプルになり、数学的に正しくなりました）

論文の著者（ポール・ヴァウティア）は、この**「どこにミスがあったか」と「どう直せば正しい答えになるか」を、初めて詳しく書き残しました。
以前は「ミスがあったらしい」という噂だけでしたが、「ミスは計算式のこの行にあり、ここをこう直せば OK」**という具体的な地図が初めて世に出たのです。

5. この論文の重要性：なぜ大事なのか？

この論文は、新しい数学の定理を発見したわけではありません。
むしろ、**「過去の偉大な数学者が書いた、少しの誤りを丁寧に修正し、その理由を明らかにした」**という点に価値があります。

• メタファー：
  昔の建築家が建てた素晴らしい塔（ギイとケリーの理論）に、小さなひび割れ（計算ミス）が見つかりました。
  この論文は、そのひび割れが**「どこにあり、なぜ起きたのか、どう修理すれば塔がより強固になるか」**を詳しく説明する「修理マニュアル」のようなものです。

まとめ

1. 問題： 点のマス目から、一直線に並ばないように最大何点取れるか？
2. 昔の答え： 数学者が「確率の計算」で、約 1.814 倍が限界だと予想した。
3. 発見： 計算過程で「人数」を間違えて代入していたミスが見つかった。
4. 結論： そのミスを直すと、予想は数学的に正しい形に修正された。
5. 意義： この「ミスの場所」と「修正方法」を初めて詳しく記録したのが、この論文です。

つまり、**「偉大な数学者の計算ミスを、親切に、かつ正確に直してあげた」**という、数学の歴史をより正確にするための小さなけれど重要な一歩です。

技術概要

以下は、Paul M. Voutier による論文「ON THE GUY-KELLY CONJECTURE FOR THE NO-THREE-IN-LINE PROBLEM」の技術的な要約です。

1. 問題の背景：ノ・スリー・イン・ライン問題

本論文は、離散幾何学における古典的な問題である「ノ・スリー・イン・ライン問題（No-Three-in-Line Problem）」に関するものです。

• 定義: $S_n$ を $1 \le x, y < n$を満たす整数座標$(x, y)$からなる$n^2$個の点の集合とします。$f_n$を、$S_n$の部分集合$T$において「どの 3 点も同一直線上にない」という条件を満たす$T$ の最大サイズと定義します。
• 既知の結果: 単純な鳩の巣原理により、$f_n \le 2n$ が成り立ちます。実際、$n \le 64$ の範囲では $f_n = 2n$ であることが知られています（$n=64$ の解は 2026 年 2 月に Prellberg によって確認されました）。
• 未解決の課題: $n$ が十分に大きい場合、$f_n < 2n$ となるかどうか、そしてその漸近的な挙動がどうなるかが問題となります。

2. 従来の仮説と Guy-Kelly の議論

1968 年の Guy と Kelly の論文 [3] では、確率的な手法（ヒューリスティック）を用いて $f_n$ の漸近挙動に関する以下の予想が立てられました。
$$f_n \sim \left(\frac{2\pi^2}{3}\right)^{1/3} n \approx 1.81 \dots n$$
この導出は、$S_n$ からランダムに選んだ 3 点が同一直線上にある確率を計算し、その事象が独立であると仮定して、$kn$ 個の点を含む集合に同一直線上の 3 点が存在しない確率を評価するプロセスに基づいています。

3. 発見された誤りと訂正

著者 Voutier は、Gabor Ellmann が 2004 年（または 2005 年）に発見した Guy と Kelly の論理における誤りについて、その詳細を初めて文献として公表します。

• 誤りの所在: Guy と Kelly の元の論文 [3] の 530 ページ、式 (5) を導出する過程（同ページの -4 行目）にあります。
• 誤りの内容: 彼らは $2n$個の点に関する評価を用いた際に、変数の扱いにミスがありました。具体的には、$k$個の点（$kn$点）に関する評価を行うべき箇所において、$2n$という特定の値を代入する際、項$-2$を誤って使用し、本来あるべき$-k$ を見落としていました。
  • 誤り：$-2 + 3k^3/\pi^2$
  • 正解：$-k + 3k^3/\pi^2$
• 結果: この誤りを修正すると、確率評価式が変化し、$k$ の臨界値が再計算されます。

4. 主要な成果と新しい予想

誤りの訂正により、以下の新しい漸近予想が導き出されました。

• 修正された予想:
  $$f_n \sim \frac{\pi}{\sqrt{3}} n \approx 1.813799 \dots n$$
  これは、元の予想 $\left(\frac{2\pi^2}{3}\right)^{1/3} n$ と数値的には非常に近い値ですが、数学的な導出過程と定数項が異なります。
• 導出の概要:
  1. 3 点が同一直線上にある確率を $O(\frac{\log n}{n^2})$ と評価。
  2. $kn$ 個の点からなる集合において、どの 3 点も同一直線上にない確率を、独立事象の積として近似（指数関数形式）。
  3. 得られた確率が $n \to \infty$ で 0 に収束する条件（$k - 3k^3/\pi^2 < 0$）を求め、$k > \pi/\sqrt{3}$ となることを示す。
  4. これにより、$f_n$ が $\frac{\pi}{\sqrt{3}} n$ に漸近すると結論付けられます。

5. 論文の意義と貢献

• 文献の補完: Ellmann による誤りの指摘は私的な通信やウェブ上の断片的な情報として存在していましたが、その誤りの「正確な数学的場所」と「訂正プロセス」が学術文献として体系的に記述されたのは本論文が初めてです。
• 独立性仮定への言及: 著者は、Guy-Kelly の議論が「事象の独立性」を仮定している点について、最近の議論（Kaplan のセミナーや Prellberg の研究など）で疑問視されていることにも触れています。Prellberg は独立仮定を疑いつつも、訂正された上限値の導出を別ルートで行っています。
• 結論: 本論文は、ノ・スリー・イン・ライン問題における重要な定数値の訂正を裏付け、その数学的根拠を明確化することで、離散幾何学の研究に貢献しています。

6. 結論

Gabor Ellmann によって発見された Guy-Kelly の論理の誤り（$2n$と$kn$の混同に起因する項の欠落）を詳細に解説し、訂正された上で$f_n \sim \frac{\pi}{\sqrt{3}} n$ という新しい漸近予想を確立しました。これは、長年議論されてきたこの問題の定数項に関する理解を深める重要なステップとなります。