Structural Conjectures for 4 x n Chomp: Unique Extension, Asymptotic Ratios, and Period-112 Geometry

アーナヴ・ガールによる論文「4 × n チョムプの構造的仮説：一意な拡張、漸近比、および周期 112 の幾何学」の詳細な技術的概要を以下に示す。

1. 問題定義

本論文は、$4 \times n$ の長方形グリッド上で行われる組み合わせゲーム「チョムプ」を調査する。

• ゲームの規則: プレイヤーは交互に、あるマスとそれより上および右にあるすべてのマスを除去する。左上のマス $(1,1)$ は「毒」であり、それを取らされるプレイヤーが敗北する。
• 目的: P 位置（先手プレイヤーが勝つ位置、すなわち現在のプレイヤーにとっての敗北位置）を特定すること。
• 背景: $1 \times n$ および $2 \times n$ のケースは完全に解明されており、$3 \times n$ には部分的なアルゴリズム的解が存在するが、$4 \times n$ のケースには体系的な計算分析が存在しなかった。本論文は、P 位置を表形式化し、背後にある構造的パターンを特定することで、このギャップを埋めることを目指している。

2. 手法

著者は、ボード幅 $n = 500$ までの P 位置を計算するために、C++ で最適化された後方ソルバーを開発した。

• 状態表現:
  • 位置は、各行のマス数を表す非増加のタプル $(a, b, c, d)$（ただし $a \ge b \ge c \ge d \ge 0$）として表現される。
  • ビットパック: 各タプルは、メモリ使用量を最小化し、ハッシュ速度を最大化するために、4 つの 16 ビットフィールドを用いて単一の uint64 整数にエンコードされる。
• アルゴリズム設計:
  • 疎な格納: P 位置のみがハッシュセットに格納される。ソルバーは、既知の P 位置への移動が見つかり次第、N 位置（現在のプレイヤーにとっての勝利位置）を早期に終了させる。
  • ボトムアップ評価: 状態は総セル数の増加順に処理され、ある状態を評価する前にすべての後続状態が解決されることを保証する。
• パフォーマンス:
  • $n \le 500$ に対して 4,316,097 の P 位置を計算。
  • 実行時間：Apple M4 プロセッサ上で約 70 分。
  • メモリ使用量：ピーク時 45 MB。
• 検証:
  • 既知の $2 \times n$ 数式（$c=d=0$ の場合、$b=a-1$ となる）に対して検証。
  • $3 \times n$ の部分ケース（$d=0$）において、$n=50$ まで独立した Python ソルバーと相互検証。
  • データ出力における初期の列アライメントのバグを修正。

3. 主要な貢献と結果

計算されたデータセットの分析から、4 つの主要な構造的仮説が導き出された。

A. 仮説 1：一意な拡張性

• 主張: 任意の有効な行長のトリプル $(a, b, c)$ に対して、$(a, b, c, d)$ が P 位置となるような整数 $d$ は高々 1 つしか存在しない。
• 含意: 射影写像 $\pi: (a, b, c, d) \to (a, b, c)$ は、P 位置の集合上で単射である。
• 重要性: これは、$4 \times n$ ゲームが $3 \times n$ ゲームの「決定論的リフト」であることを示唆している。すべての $(a, b, c)$ が P 位置に拡張されるわけではない（約 20% のみ）が、拡張が存在する場合、4 行目の長さ $d$ は一意に強制される。これは、そのような単純な単射写像が以前に確立されていなかった $3 \times n$ のケースとは対照的である。

B. 仮説 2：漸近比

• 主張: ボード幅 $a \to \infty$ となるにつれて、P 位置における行長の比は一定の定数に収束する：
  • $b/a \to L_1 \approx 0.762$
  • $c/a \to L_2 \approx 0.499$
  • $d/a \to L_3 \approx 0.224$
• 手法: ウィンドウ付き中央値、ローリングウィンドウ、およびべき乗則曲線フィッティングを通じて推定。
• 観察: これらの定数に対する正確な代数的恒等式は見つからなかった。しかし、$L_3 \approx 0.224$ は $\cos(3\pi/7) \approx 0.2225$ に驚くほど近いため、潜在的な隠れた代数的関係が示唆される。

C. 仮説 3：周期 112 のモジュラー構造

• 主張: P 位置に拡張されるトリプル $(a, b, c)$ の集合は、基本周期が112であるモジュラー構造を示す。
• 証拠:
  • $d$ 値の系列の自己相関分析により、ラグ 112 で鋭いピークが観測される。
  • $c$ と $(a-b) \pmod{112}$ のみを使用したロジスティック分類器は、拡張可能性を79% の精度で予測する。
  • カイ二乗検定により、他の法数と比較して法数 112 が最も強力な統計的分離（$\chi^2 = 12,433$）を提供することが確認された。
• 解釈: $112 = \text{lcm}(7, 8) \times 2$ である。因子 7 はおそらく $3 \times n$ 部分ゲームの周期性に由来するが、因子 8 は未解明であり（ビットパックのアーティファクトは除外）、その起源は不明である。

D. 仮説 4：線形円錐幾何学

• 主張: 拡張されるトリプル $(a, b, c)$ の集合は、$\mathbb{R}^3$ 内の線形円錐を形成する。
• 幾何学: 固定された $c$ に対して、有効な $(a, b)$ の範囲は連続的な帯域を形成する。この帯域の幅は $c$ に比例して線形的に増加する：
  $$\text{width}(c) \approx \frac{11}{8} \cdot c + f(c \pmod{112})$$
  ここで、$f$ は有界な周期関数である。傾き $11/8 = 1.375$ は、スライスベースの測定から導き出された。

4. 意義と今後の方向性

• 構造的洞察: 本発見は、$4 \times n$ チョムプが以前に疑われていたよりも豊かで決定論的な構造を有しており、「一意な拡張」性により $3 \times n$ のケースよりも単純である可能性を示唆している。
• 一般化: 著者は、一意な拡張性がすべての $k$ に対する $k \times n$ チョムプに一般化される可能性を仮説として立てており、すべてのチョムプゲームが解明済みの $2 \times n$ ケースによって再帰的に決定されることを示唆している。
• 未解決の問題:
  1. 証明: 一意な拡張性を組み合わせ論的に証明できるか？
  2. 代数的極限: 漸近比は共通の多項式の根か？
  3. 高次元: これは $5 \times n$ にも当てはまるか？（$O(n^5)$ の状態空間が必要）。
  4. 周期の起源: 112 サイクルにおける周期 8 の成分の源は何か？
  5. 閉形式: 拡張可能なトリプルの約 20% を閉形式のマスクで記述できるか？

本論文はまた、$d$ 値の系列をオンライン整数列大百科事典（OEIS）に A395126 として提出したことを付記している。コードとデータは、著者の GitHub リポジトリを介して公開されている。