HN 日本語サマリー

← 一覧へ戻る
科学・技術

あらゆる階数のマジックヘキサゴンは存在する

There Are Magic Hexagons of Every Order (gukov.dev)

174 pointsby gukoff28 コメント

要約

この記事は、数字が配置された六角形のグリッド上で、すべての直線上の数字の合計が一定になる「マジックヘキサゴン」について解説しています。通常の「正規マジックヘキサゴン」は非常に稀であることが示され、その発見の難しさが語られます。著者は、対称性の導入と「ポテンシャルフィールド」という表現を用いることで探索空間を大幅に縮小し、AI(LLM)を活用したカスタムソルバーを用いて、これまで知られていなかった多くの階数のマジックヘキサゴンを発見した経緯を紹介しています。

全文翻訳

あらゆる次数でマジックヘキサゴンは存在する

数字の19に何が特別なのでしょうか?

この疑問は、先月、YSDAの卒業生たちの会話の中で持ち上がりました。学校が19周年を迎えたのです。誰かが19は双子素数だと指摘しました。別の誰かが、19は唯一の非自明な正規マジックヘキサゴンのセルの数だと答えました。

ところで、「マジックヘキサゴン」とは何でしょうか?そこから始めましょう。

マジックスクエアとマジックヘキサゴン

おそらくマジックスクエアについてはご存知でしょう。マジックスクエアとは、すべての行、すべての列、そして両方の主対角線が同じ合計値(マジックコンスタントと呼ばれる)になるような数字の正方形グリッドです。通常、数字は連続していること(通常は $1$ から $n^2$ まで)を要求し、それを正規マジックスクエアと呼びます。そうでなければ、すべてのセルに同じ数字を入れることができ、それは正方形を埋める非常に退屈な方法になります。

マジックスクエアは何千年もの間知られており、現在では非常によく理解されています。すべての次数 $n>2$ の正規マジックスクエアを構築するためのアルゴリズムがあります。

マジックヘキサゴンは、このアイデアを六角形のグリッドに適用したものです。そのセルは3つの方向に直線状に並び、そのようなすべての直線は同じ合計を持つ必要があります。スクエアと同様に、マジックヘキサゴンは、次数 $n$ のヘキサゴンの総セル数である $1$ から $3n^2-3n+1$ までの連続した数字を含む場合、正規と呼ばれます。

上記に見られるのは、その回転や鏡像を除けば、存在する唯一の非自明な正規マジックヘキサゴンです。証明は単純です。3つの方向のそれぞれにおいて、セルは $2n-1$ 本の直線に分割されます。したがって、すべての数字の合計は $2n-1$ で割り切れる必要があります。すべての次数 $n>3$ について、$1$ から $3n^2-3n+1$ までの数字の合計はこの割り算テストに失敗します。

さて、ここで話を終えるのは面白くありません。より興味深いものにするために、いわゆる異常マジックヘキサゴンを見てみましょう。ここでは制約を1つ緩和します。グリッド上の数字は依然として連続している必要がありますが、必ずしも $1$ から始まる必要はありません。

この小さな緩和により、突然新しい解が現れるようになります。

しかし、それらを見つけるのは簡単ではありません。マジックスクエアとは異なり、公式な構築方法や決定論的なアルゴリズムはありませんでした。唯一知られているアプローチは、膨大な検索空間をさまようことでした。 Wikipedia によると、2026年7月現在、知られている最大の解は、2024年にKlaus Meffertによって発見された次数 $n=9$ のヘキサゴンでした。

では…これらの解を見つけるのがこれほど難しいのはなぜでしょうか?そして、試してみるのはどうでしょうか?

章 1: 観察を行う(人間の脳で)

2つの独立した制約の間には、明確な緊張関係があります。

  1. 数字は連続している必要があります。
  2. 線は長さが異なりますが、すべての線合計は等しくなければなりません。

以前の解は、人々がすでにいくつかの探索アルゴリズムを試しており、おそらくそれらをうまく最適化していたことを示唆していました。そのため、分野を進歩させたいのであれば、探索を速くすることではなく、検索空間を小さくすることに焦点を当てるべきだと考えました。

観察:反対称ヘキサゴンははるかに単純である

まず、グリッド上の数字をある $K$ に対する対称区間 $-K,\ldots,K$ に制限しましょう。すべての線合計が等しい場合、これは各線合計がゼロであることを要求することと同等です。

次に、中央に $0$ を置き、180度回転させたときの反対側のセルが反対の値を持つことを要求します。一方のセルが $x$ を含む場合、その反対側のセルは $-x$ を含みます。

制約がどれだけ消えるかに注目してください。中心を通るすべての線は、反対側のペアが相殺されるため、自動的にゼロになります。他のすべての線には、反対側の反対側の数字の合計を持つ反対側の線があります。一方の線がゼロに合計される場合、もう一方もゼロに合計されます。

もちろん、制約を単純化することにはリスクが伴います。おそらく、反対称性を満たす解は全く存在しないかもしれません。この時点では、酔っ払いの方程式に従って、反対称性は単に有望な探索場所でした。

しかし、ゼロサムヘキサゴンについて考え始めると、別の構造が現れました。

観察:すべてのゼロサムヘキサゴンは同じ6点リングから構築される

任意の六角形グリッド、ゼロサムかどうかにかかわらず、考えてみましょう。任意の内部点を囲む6つのセルを取り、交互のパターン ([-1,+1,-1,+1,-1,+1]) を追加します。中央のセルは変更しません。

このリングに交差するすべての直線は、寄与を受けないか、または2つの反対の寄与($+1$ と $-1$)を受け取ります。したがって、その合計は変更されません。このパターンの任意の倍数を追加しても、単一の線合計は変更されません。

これらの局所的な交互リングは基底を形成します。すべてのゼロサムヘキサゴンは、それらのユニークな線形結合として構築できます。簡潔さのため証明は省略しますが、アイデアはかなり単純です。外側の層から始めて、そのセルを相殺するリング係数を選択し、層を剥がして帰納法で内側へ続けます。

したがって、次数 $n$ のゼロサムヘキサゴンには2つの等価な表現があります。

  • 可視的なセルの値。
  • 各局所リングがどれだけ含まれているかを記録する、次数 $(n-1)$ のポテンシャルフィールド。

ポテンシャルフィールド表現も、構築によってすべての線合計制約を満たします。しかし、可視的な値が異なり連続していることを保証するものではありません。それらは依然として困難なグローバル制約です。

以下は、次数3の反対称ヘキサゴンのポテンシャルフィールドで遊ぶことができます。ポテンシャルフィールドを変更しても、ヘキサゴンの線合計はゼロのままであることに注意してください。しかし、ヘキサゴンを「マジック」にすることは、依然として非常に難しい課題です。

(残念ながら、このプレイグラウンドはモバイルリーダーには小さく見えます)

この表現は反対称性ともよく合います。反対称ヘキサゴンのポテンシャルフィールドは、それ自体が対称です。

アイデアは、任意の配置の中から探索し、壊れた線を繰り返し修復する代わりに、すべての線がすでにゼロに合計される空間内でのみ探索できるということです。これは、ソルバーにとって(あるいはそうでないかもしれませんが)検索空間を小さくする可能性があります。

章 2: 新しいヘキサゴンを見つける(AIがコードを書く)

同時期に、私はMidnight Code Cup 2026というプログラミングコンテストのプレソルブ問題を手伝っていました。このコンテストではLLMの使用が明確に奨励されています。そのタスクの多くは最適化問題です。私の主な収穫は、LLMがドメイン固有のソルバーを開発する上で非常に効果的であり、Z3やOR-Toolsのような汎用ツールをはるかに凌駕できるということでした。

そのため、別の汎用制約ソルバーに頼る代わりに、GPT-5.6 Solにアクセスし、問題に対するより自由度を与えました。反対称性の制約とポテンシャルフィールド表現を指摘しました。モデルは関連する概念を検索し、問題をHeffter配列(指定されたゼロサム条件を持つ符号付き整数の組み合わせ配置)に結びつけました。問題は同一ではありませんが、その関連性は、影響を受ける合計を制御しながら、値を整理し交換するためのより良い方法を示唆しました。

結果として得られたプログラムは、汎用制約ソルバーアプローチを捨て、カスタムシミュレーテッドアニーリングを採用しました。その後、数回の最適化ラウンドを通じてデューデリジェンスを行いました。モデルにホットループにNumbaを使用するように依頼し、perfでメモリ割り当てと乱数生成のボトルネックを特定し、最終的にプログラムからさらに50%のパフォーマンスを引き出しました。これが最終結果です。

その後、数日間、約24コアのCPUで自宅のサーバーで実行させました。

期待通り、より小さな検索空間と専門化されたソルバーの組み合わせは驚くほどうまく機能しました。すぐに、 $n=21$ までのすべての次数のマジックヘキサゴンを発見しました。それらは以下の通りです。

マジックヘキサゴン

[

[画像: Order 21の異常ゼロサムマジックヘキサゴン]

](https://gukov.dev/assets/svg/magic-hexagons/MagicHexagon-Order21-sum_zero.svg)

ポテンシャルフィールド

[

[画像: Order 21のマジックヘキサゴンのポテンシャルフィールド]

](https://gukov.dev/assets/svg/magic-hexagons/potential_MagicHexagon-Order21-sum_zero.svg)

次数

21

読み込み中...

セルの値は混沌としてノイズが多いように見えます。それらのポテンシャルフィールドはそうではありません。それらは地形図に似ており、広い傾斜、尾根、谷、そして驚くほど滑らかな遷移があります。

この滑らかさが手がかりなのか、それとも単に検索のアーティファクトなのかは、まだわかりませんでした。いずれにせよ、それらの風景を見て、より大きな構造が隠れているのではないかと疑わないのは困難でした。

章 3: すべてのヘキサゴンを見つける(AIが主導する)

より大きな解を繰り返し見つけることは、自然に次のような推測を促しました。

これは強力な主張でした。このプロジェクト以前は、異常マジックヘキサゴンはほんの一握りしか知られていませんでした。そして、反対称性という追加の制約を課したことを忘れないでください。

しかし、数学におけるAIの最近の成功に触発され、それがどのようにこの問題に取り組むか興味がありました。AIは最初からそれを証明できるでしょうか?

2つのAIシステムを試すことにしました。

  • GPT-5.6 Sol: 私の個人サブスクリプションを通じて利用可能な最も強力な汎用モデル。
  • Aristotle: Lean指向の定理証明エージェント。

最初にGPT-5.6 Sol (high)に問題ステートメント、既知の解、およびいくつかの追加の直感を与えました。新しい仮説や可能な構築を提案し、問題をより小さな部分に分割し始めました。作業は進展しました。この段階では、私はまだ主導権を握っていると感じていました。馴染みのない数学的仕組みを学び、議論をチェックし、生産性の低い方向を却下し、ほとんどの場合、私が理解できるプロセスを導いていました。

数日間の反復を経て、問題はいくつかの主要な補題に還元されたため、Aristotleを呼び出して並行して形式的な証明を追求しました。

最終的に、プロセスは停滞しました。両方のエージェントは楽観的でしたが、明らかな行き詰まりで、意味のある進歩なしに同じアイデアを繰り返していました。推測を、無限に多くの異常マジックヘキサゴンが存在するという、より控えめな主張に弱めました。新しい仮説や非構成的なアプローチさえも探求しました。

それでも、壁にぶつかりました。

その後、GPT-5.6 Sol (max)を採用しました。これは何時間も推論しましたが…証明を見つけることもできませんでした。しかし、クレジットを使い果たす前に、いくつかの新しいアイデアを生み出しました。それらのアイデアはプロジェクトの共有コンテキストの一部となり、後続の会話で利用可能になりました。

ある会話で、私が再びGPT-5.6 Sol (high)を証明に向けて導いていたとき、それは以前のアイデアのいくつかを取り上げ、ブレークスルーのように見えるものに組み合わせました。計算でそれをチェックした後、私は16で割り切れる $n>800$ のすべての次数に対する構成的な議論を得ました。

その足がかりが確立されると、作業は本当に勢いを増しました。反復を重ねるごとに、GPT-5.6 Sol (high)に構築を一般化するように促しました。まず8で割り切れる次数、次に4で割り切れる次数、次に2で割り切れる次数、そして最終的に割り切れる条件を完全に削除しました。証明された閾値も800から114に低下しました。

閾値114は正しく解釈することが重要です。これは、証明の不等式と組み合わせの選択が理論的に正当化しやすい、便利な上限です。実際には、同じ方法がその閾値をはるかに下回る場合でもうまく機能するため、構築の根本的な制限ではないようです。

一般的な構築が存在すると、再びプッシュしました。今回はシンプルさと決定論のために。初期の構築には、以前の試みから継承された多くの特殊ケース、補助的な選択肢、および機械部品が含まれていたことは明らかでした。案の定、GPT-5.6 Sol (high)は構築内の冗長性を繰り返し発見し、それらをよりクリーンな決定論的アルゴリズムに置き換えました。

数十回の長い会話と数日間の推論を経て、推測は解決されました。そして結果は構成的です。これらのヘキサゴンが存在することを単に主張するだけでなく、比較的低い次数から始まるそれらを構築するためのアルゴリズムを提供します。以前に総当たりで見つけた $n=21$ までの有限な証拠と組み合わせると、$n>3$ のすべての次数をカバーします。

この投稿の執筆時点では、証明はLeanで形式化されておらず、独立して検証されていないことに注意することが重要です。これが自然な次のステップになるでしょう。

そして、構築によって生成された、はるかに大きな次数のヘキサゴンの例をいくつか示します。パターンに気づきましたか?

次数

500

読み込み中...

章 4: 反省

  • このプロジェクトはAIを副操縦士として、私が運転席に座って始めました。終わりには、私はより乗客に近くなっていました。AIが多くの創造的な作業を行い、私は有望に思える方向にそれを少しだけ導きました。

私の人間の脳で生まれたアイデアのいくつかが役立ったことを嬉しく思います。反対称性は最終的な構築において大きな役割を果たしますが、ポテンシャルフィールドは…それほどではありません。それでも、それらの滑らかさは興味深く、おそらくさらに発見すべきことがあるでしょう。

  • GPT-5.6 Solは驚くほど有能な数学的推論者ですが、トンネルビジョンの両刃の剣を持っています。選ばれた方向には非常に深く入り込むことができます。その方向が正しければ、これは信じられないほど強力です。間違っている場合は、ループ内にアービター(別のモデル、または私の場合は人間)を置いて、全体像を思い出させ、意味のある進歩が止まったときに気づくようにするのが良いでしょう。

  • モデルがインターネットにアクセスできたことは不可欠でした。それは、私が予測して事前に提供できなかった関連論文や数学的概念を見つけました。それが、私がCodexではなくChatGPT Webインターフェースを使用した理由の1つです。もう1つは個人的な理由でした。休暇中にこのプロジェクトを主に精神的な演習として維持したかったのです。そうでなければ、コンピューターの前に座り続ける別のソフトウェアエンジニアリングプロジェクトになってしまうでしょう。しかし、真剣な証明キャンペーンのためには、より体系的なセットアップを使用するでしょう。複数のモデルが並行して動作し、議論を提案および批判するための明確な役割、永続的な共有コンテキスト、およびexa.aiのようなサービスを介したインターネット検索へのアクセスです。

  • ソフトウェアエンジニアリングでは、LLMがコード生成を安価にした後、コードレビューがボトルネックになりました。静的型付け言語、静的解析、テストは、人間の検証作業の負担を軽減できるため、これまで以上に重要になりました。

数学も同様の問題に直面しています。AIは、人々が責任を持って検証できるよりも速く、候補となる理論や証明を生成できます。Leanやその他の機械検証可能な証明システムは、生成と並行して検証をスケーリングする方法を提供することで、コミュニティに計り知れない恩恵をもたらす必要があります。

  • このプロジェクト中に発見された技術が、他の組み合わせ構築問題に適用され、単一の六角形のパズルの解決策よりも一般的なものに発展させることができるかどうか疑問に思います。Heffter配列が自然に思い浮かびます。

  • この物語が19という数字への興味から始まり、3より大きいすべての次数のマジックヘキサゴンの構築で終わったのは面白いです。残された課題は、証明を機械で検証可能にすることです。今やAristotleとleanprover/comparatorはいくつかの仕事をする必要があります。