On a problem of minimal additive complements for not eventually periodic $S$-difference sets

あなたは、整数タイルで作られた無限の廊下に立っていると想像してください。その廊下は両方向にどこまでも続いています。あなたには「跳躍石」と呼ばれる特別な石の集合 $W$ があります。もしあなたが $W$ の中の石の上に立ち、特定の「ヘルパー（助っ人）」の石の集合 $C$ からの一歩を踏み出したとき、あなたは廊下にあるすべてのタイルに着地できる必要があります。数学の言葉で言えば、ヘルパーの石と跳躍石の和が数直線全体を覆うとき、$C$ は $W$ の「加法的補集合（additive complement）」であると言います。

ここで、ひねりが加わります。もし、あなたのヘルパーのコレクションが大きすぎるとしたらどうでしょう？ もし、いくつかの石を捨てても、なおすべてのタイルに到達できるとしたら？ 「最小加法的補集合（minimal additive complement）」とは、使用できるヘルパーの最小のグループのことです。つまり、あまりにも小さく、そこからたった一つの石を取り除くだけで、廊下に誰も到達できない隙間が生じてしまうような、極めて精巧なチームのことです。数学者たちは10年以上にわたってこのパズルに魅了されてきました。もし、あなたの跳躍石のパターンが繰り返されない（「最終的に周期的なのではない」）パターンであり、かつ、それらの間の隙間が特定の数値リストから選ばれた小さなものであれば、あなたは常にこの最小限のチームを見つけることができるのでしょうか？

Min Tang と Wenjing He によるこの論文は、その問いに対して、力強い「イエス」という答えを出しました。著者たちは、跳躍石 $W$ の間の隙間が有限の正の整数のリスト $S$ から選ばれ、かつ、そのリスト内のすべての数字が隙間として無限回現れるという、非常にトリッキーなバージョンの問題に取り組んでいます。彼らは、どのようなリスト $S$ を選んだとしても（少なくとも2つの異なる数字が含まれている限り）、最小加法的補集合を持つ、決して繰り返されることのない数列を構築できることを証明しました。彼らは単に推測したのではなく、これらの数列を作り出すための詳細かつ段階的なレシピを構築し、結果として得られるヘルパーのチームが、確かに最小のチームであることを数学的に証明したのです。

隙間を埋める者たちの物語

Tang と He が行ったことを理解するために、この問題を巨大な無限のモザイクを埋めるゲームとして捉えてみましょう。

登場人物たち

• パターン ($W$): ステッピングストーン（踏み石）の列を想像してください。ある石から次の石までの距離は、決してランダムではありません。それは常に、特定の「メニュー」のサイズから選ばれた数字です。例えば、メニューが $\{3, 5\}$ だとしましょう。つまり、3ステップ進んだり、5ステップ進んだり、次に3、次に3、そしてまた5といった具合です。ルールとして、メニューにあるすべてのサイズを無限回使用しなければならず、かつ、ジャンプのパターンは決して退屈な繰り返しのループ（例：3-5-3-5-3-5と永遠に続くようなもの）に落ち着いてはなりません。これは数学的に「INEP S-差集合（Infinite, Not Eventually Periodic S-difference set）」と呼ばれます。
• ヘルパー ($C$): これらは、隙間に配置される石です。ヘルパーの石の上に立ち、パターン $W$ の中のどの石へもジャンプできるなら、あなたは数直線上のあらゆる整数に到達できるはずです。
• ゴール: 最小のヘルパーの集合を見つけることです。これは、すべてのメンバーが絶対的に不可欠であるような、最小のヘルパーのチームを見つけることを意味します。もし一人でも解雇すれば、そのカバー範囲は崩れてしまいます。

以前の謎
この論文の前では、特定のメニューに対してのみ答えが分かっていました。もしメニューが単に $\{1, 2\}$ であったり、あるいは数字同士に特別な関係（一方が他方の倍数であるなど）があったりする場合、解決策を構築することができました。しかし、$\{3, 7, 11\}$ のような一般的なメニューや、ランダムな数字の組み合わせの場合、問題は未解決のままでした。「隙間が規則的すぎると最小のチームは見つからないかもしれないが、混沌としていれば見つかるかもしれない」という説もありました。この論文の著者たちは、あらゆる有限の隙間のメニューに対して、この問題を決着させようとしたのです。

マスタープラン：架け橋を築く
Tang と He は、単に「存在する」と言ったのではありません。彼らはそれを「構築」したのです。彼らの証明は、無限の峡谷に架かる橋を建設するための建築設計図のようなものです。彼らは、メニューに含まれる最小の数字に応じて、構築を2つの主要なシナリオに分けました。

シナリオ 1：メニューに数字 1 が含まれる場合
最小の隙間が 1 の場合、構築は長い、うねるような道を作ることに似ています。著者たちは、まず小さく扱いやすい石の塊から始めます。次に、巧みな帰納的手法（ステップ・バイ・ステップでの構築）を用いて、その道を永遠に拡張していきます。

• 彼らは石の「ブロック」を作成します。
• ブロックの内部では、数学的なツール（特定の硬貨の額面を使ってお釣りを作る方法を問う「フロベニウスの硬貨問題」に関連するもの）を用いて、石の間の隙間がメニュー $S$ の数字と一致するようにします。
• ヘルパーの石（集合 $C$）を特定の間隔で注意深く配置します。
• 魔法はブロック間の「遷移」で起こります。彼らは、ヘルパーの石がすべての整数に到達できるように隙間を調整しますが、同時に、もし一つのヘルパーを取り除いたとしても、特定の「穴」が現れ、他のどのヘルパーもその穴を埋めることができないように設計します。彼らは、構築における石の間の隙間が特定の法則に従って大きくなっていくことを証明し、それによってパターンが決して繰り返されない一方で、最小のヘルパーチームが完璧に機能することを保証します。

シナリオ 2：メニューが 1 より大きい数字から始まる場合
これはよりトリッキーな部分です。もしメニューの最小値が 3 や 5 である場合、単一のステップだけで隙間を埋めることはできません。著者たちは、より独創的な方法を編み出しました。

• 彼らは、メニューの数字たちが共通の約数を持たない（グループの意味で「互いに素である」）場合でも、道を構築できることに気づきました。
• 彼らは、ヘルパーの石が小さなグループやクラスター（塊）として存在する、より複雑な構造を構築しました。
• 彼らは高度な計数論を用いて、隙間がより大きいにもかかわらず、ヘルパーのクラスターの配置がすべての整数を捉える「網」を作り出すことを示しました。
• 極めて重要なのは、ヘルパーを取り除いたときに残る「穴」が、その特定のヘルパーに固有のものであることを証明した点です。これは、鍵と鍵穴のシステムのようです。ヘルパーAは特定の鍵を開けますが、他のどのヘルパーもその鍵を持っていません。ヘルパーAを取り除けば、その鍵穴は閉まったままになり、カバー範囲は失敗します。

結論
著者たちの構築は厳密です。彼らはコンピュータでシミュレーションしたり、「おそらくこうなるだろう」と示唆したりしたのではありません。彼らは数学的な証明を提供しました。彼らは、有限の正の整数の集合 $S$（少なくとも2つの要素を持つ）に対して、 $S$ の数字のみを用いた、決して繰り返されることのない隙間の数列を作成することが可能であり、その数列に対して、最小の加法的補集合が常に存在することを証明しました。

彼らは、このバージョンの問題に終止符を打ちました。「任意の有限集合 $S$ に対して……は真か？」という問いへの答えは、決定的な「イエス」です。論文は、隙間の混沌とした非反復的な性質が、最小の完璧なヘルパーチームの存在を妨げることはないことを裏付けました。実際、パターンの持つ「混沌」こそが、すべてのヘルパーが不可欠であり、かつ全整数をカバーすることを保証する、解決策を設計するための鍵となったのです。