A Salem-Spencer-Type Construction for Large Subsets of Integer Grids with No Isosceles Right Triangles

あなたは、グリッドの交差点だけで構成された巨大で無限の都市、数学の世界（具体的には、離散的な対象の数え上げ、配置、パターンの発見を扱う「組合せ論」という分野）における、謎を解こうとする探偵であると想像してください。この都市において、「通り」は単なる数字であり、「建物」は $(x, y)$ 座標のように2つの数字が出会う点です。

解決すべき謎は、非常に特定のルールに基づいています。あなたは、ある特定の形が厳格に禁止されている、可能な限り大きな「近隣地域（点の部分集合）」を構築したいと考えています。その形とは、直角二等辺三角形です。あなたはこの三角形をよく知っています。それは、一つの角が完璧な90度（紙の角のような）であり、その角に接する2つの辺の長さが全く同じであるという特徴を持っています。数学者たちが長年問い続けてきた問題は、「どれほど大きな近隣地域を作れば、意図せずしてこの禁止された三角形が生まれてしまうのか？」ということです。

これは単なる幾何学のゲームではありません。これは、数字がどのように振る舞うか、どのようにデータを暗号化するか、あるいは宇宙の構造をどのように理解するかという深い問題へとつながっています。もし、三角形を含まない巨大な近隣地域を見つけることができれば、それは、単純なパターンを回避しながら数字を配置する、隠された複雑な方法が存在することを意味します。何十年もの間、数学者たちはその答えが「非常に大きい」ものから「ほぼ街全体」の間にあることを知っていましたが、最小の「大きな近隣地域」と最大の近隣地域の間のギャップは膨大なものでした。それは、宝箱が砂漠のどこかにあることは分かっているものの、それが一粒の砂の下に埋まっているのか、それとも山の金の下にあるのかさえ分からないような状態でした。

---

この論文の大きな発見： 「三角形のない」都市を築く新しい方法

この論文において、数学者の Gyula Károlyi と József Solymosi は、以前考えられていたよりもはるかに大きな、新しい近隣地域を構築しました。彼らは、直角二等辺三角形を避けるグリッド内の点の部分集合を構築することに成功し、その構築法は、その規模が $n$（$n$ はグリッドのサイズ）に対しておよそ $n^{1.3}$ の割合で成長することを証明しました。

彼らがどのようにしてこれを成し遂げたかを理解するために、ブロックを使ってタワーを組み立てようとしている場面を想像してください。ただし、特定の「悪い」形を作るようなブロックの積み方はできないという厳しいルールがあります。過去、数学者たちは、ブロックを単独では完全に安全なものとして選ぶことで、これらのタワーを構築しようとしてきました。しかし、Károlyi と Solymosi は、より賢い方法があることに気づきました。彼らは「ピーリング（皮剥き）」と呼ばれる手法を用いました。これは、たとえタワーが少しグラついていても、特定の順序に従ってブロックを一つずつ取り除いていけば、最終的に全体が安全になるという、ジェンガのようなものです。

魔法の材料

著者らは、これを実現するためにいくつかの巧妙なトリックを使用しました。

1. ガウス整数（「魔法のグリッド」）： 通常の数字ではなく、彼らはガウス整数と呼ばれる特別な種類の数字を使用しました。これらは、すべての点が $x$ 座標と $y$ 座標を持つグリッド上の点として扱われますが、それらは単一の魔法の数字として扱われます。これにより、通常の数字では不可能な方法で、ブロックを回転させたり移動させたりすることが可能になりました。
2. 「繰り上がりなし」のアルファベット： 数字を加算するとき、時に「繰り上がり」が発生します（例：$9 + 1 = 10$ で 1 が繰り上がる）。著者らは、もしそれらを足し合わせて三角形を作るとしても、計算が次のレベルへと決して「繰り上がらない」ような、特別な「数字のセット（小さな点のグループ）」を見つけ出しました。これにより、局所的なルールが単純に保たれます。
3. ピーリングの順序（秘伝のソース）： これが最も斬新な部分です。彼らは、一度にすべてを見ると三角形を含むことになる 281 個の点を見つけました。しかし、彼らはこれらの点を削除するための特定の順序を発見しました。最初の点を削除すれば、その点を角とする三角形は残りません。次に次の点を削除し、以下同様に進めます。やり終える頃には、残された集合は完全に安全なものになっています。それは、全員が円になって手をつないでいる部屋のようなものですが、特定の順序に従って退場を求めれば、誰かが傷つく前に円が崩壊していくようなものです。

結果： 大きな飛躍

彼らは強力な AI ツールである AlphaEvolve（完璧な配置を見つけ出すために、何百万もの可能性を探索するのを助けたもの）を使用して、281 個の点を用いた「ピーリングの順序」を見つけ出しました。

彼らがこの手法をサイズ $n$ のグリッドに適用したとき、少なくとも $n^{1.3178...}$ のサイズを持つ、三角形を含まない部分集合が存在することを証明しました。

比較のために：

• 以前は、最善の既知の下限はもっと小さかった（約 $n^{1.05}$）ものです。
• 最善の既知の上限（理論的な限界）は、およそ $n^2$ を対数因子で割ったものです。
• 彼らの結果である $n^{1.3}$ は、この大きな隔たりを埋め、このような三角形を含まない近隣地域が、以前想定されていたよりもはるかに大きいことを示しています。

彼らが「行わなかった」こと

この論文が主張していないことを注記しておくことは重要です。彼らは $n^{1.3}$ が数学的に可能な絶対的な最大サイズであることを証明したわけではありません。彼らは、数学的に可能な限り最大となる「完璧な」近隣地域を見つけたわけでもありません。また、281 が彼らの特定の手法で使用できる最大の点数であることも証明していません。彼らは単に、非常に優れたものを見つけたに過ぎません。

論文には、彼らの新しい下限（$n^{1.3}$）と上限（$n^2$）の間に、依然として「大きな隔たり」があることが明記されています。謎は完全には解明されていませんが、彼らは間違いなく、これまで誰よりも大きなパズルのピースを見つけ出したのです。

まとめ

この論文は、伝統的な数学的論理と現代の AI 探索を組み合わせた勝利です。数字をグリッド上の点として扱い、「繰り上がりなし」のゾーンを見つけ、危険な点を一つずつ取り除くための巧妙な「ピーリング」戦略を用いることで、著者らは、私たちが考えていたよりもはるかに大きな「三角形のない」都市を構築できることを示しました。これは、問題を静的な壁としてではなく、除去という動的なプロセスとして捉え直すことで、数字の世界の新たな可能性を切り拓くことができるという、新鮮な視点の見事な例です。