Possible Sizes of Sumsets

あなたは、手元にある材料が整数のみであるキッチンに立つシェフだと想像してください。あなたには特定のレシピがあります。それは、これら（整数）の数をごく一掴み手に取り、あらゆる方法で混ぜ合わせ、作成できる「ユニークな合計フレーバー（和）」の総数を数えるというものです。これは、数の振る舞いを研究する数学の一分野である「加法的組合せ論」の世界です。中心となる問いはシンプルですが、非常にトリッキーです。もし、特定の数の材料（例えば $k$ 個）を選び、それらを $h$ 回ずつ混ぜ合わせた場合、どれほど多くの異なる結果が得られるでしょうか？

積み木遊びのようなものだと考えてください。もし、ブロックが小さく整然と積み重なっている（算術級数である）なら、それらを足し合わせると、予測可能で密な集まりが得られます。しかし、もしブロックをバラバラに散らしてしまったら（2の累乗のように）、結果は広大で疎な風景へと爆発的に広がります。数学者たちは、これらの結果のクラスター（集まり）の「サイズ」にはどのようなものがあり得るのか、ということを長年研究してきました。ブロックの組み合わせによって、どのような結果が得られるのでしょうか？

アイザック・ラジャゴパルによるこの論文は、このパズルを深く掘り下げています。この論文は、特定のルールに焦点を当てています。つまり、あなたは $k$ 個の整数を持つ集合を持っており、それらを $h$ 回加算した（同じ数を何度でも使ってよい）ときの和集合のサイズを知りたいと考えています。著者は、ほとんどの大きな集合において、得られる和のサイズは、ほぼ完璧で途切れのない数列を形成することを証明しています。ただし、いくつかの特定の、予測可能な「穴」がある場合には限ります。しかし、この論文はまた、特定の小さな、あるいは特殊な組み合わせにおいては、どのようにブロックを配置しても決して到達できない、完全に不可能な領域が存在することも示しています。

大いなる和集合の探索

例えば、あなたが $k$ 個の異なる整数が入った袋を持っているとしましょう。あなたはゲームをすることにしました。袋の中から $h$ 個の数を選び（同じ数を何度でも選んでよい）、それらを足し合わせ、その合計を書き留めます。これをあらゆる組み合わせに対して行ったとき、あなたは新しいリストを手に入れます。この新しいリストの「サイズ」とは、そこに含まれるユニークな数の数にすぎません。

数学者は、この新しいリストを $h$ 重和集合（$h$-fold sumset） と呼びます。大きな疑問は、材料の数（$k$）と、それらを混ぜ合わせる回数（$h$）を固定した場合、この新しいリストのサイズとして取り得る値はすべて何であるか、ということです。

長年、私たちは絶対的な最小値と最大値を知っていました。最小値は、あなたの数字が $1, 2, 3, 4$のように密集しているときに起こります。最大値は、それらが$1, 2, 4, 8$ のように幾何級数的に広がっているときに起こります。しかし、その中間はどうなのでしょうか？ すべての数を得ることができるのでしょうか、それとも、決して存在し得ない「ゴーストナンバー（幽霊数）」が存在するのでしょうか？

禁止された三角形

論文は、既知の事実を確認することから始まります。そこには、得ることが不可能な数があるということです。グラフを描いて、水平軸を材料の袋のサイズ（$k$）、垂直軸を混ぜ合わせる回数（$h$）とした場合を想像してください。著者は、$\Delta_{h,k}$ （デルタと読みます）と呼ばれる特定の形状を定義しています。

$\Delta_{h,k}$ を、可能性のマップにおける「禁止された三角形」だと考えてください。この論文は、ある厳しいルールを証明しています。どのように数字を配置したとしても、和集合のサイズがこの三角形の中に着地することはありません。

例えば、7つの数字があり、それらを6回混ぜ合わせる場合、特定のサイズの範囲が完全に空の状態になります。あなたはサイズが37の和集合を得ることも、サイズが924の和集合を得ることもできますが、もしそれらがこの禁止ゾーン内に落ちるならば、サイズが40、41、または42の和集合を得ることはできません。この論文は、「集合の直径（最小値と最大値の距離）」を利用した巧妙なトリックを用いて、これを証明しています。数字が近すぎれば、和は小さくなりすぎます。数字が遠すぎれば、和は大きすぎます。「禁止された三角形」とは、決して到達できない、あのぎこちない中間領域なのです。

隙間を埋めること（ほとんどの場合）

この論文の主要な発見は、この禁止された三角形の「外側」で何が起こるかという点です。著者は、もしあなたの数字の袋が十分に大きい場合（具体的には、$k$ が $h$ に依存するある定数よりも大きい場合）、最小値と最大値の間にあるすべての数が、禁止された三角形の中にあるものを除いて、すべて可能であることを証明しています。

それは、バケツに水を満たすようなものです。あなたは底の部分（禁止された三角形）を埋めることはできないと分かっていますが、一度そこを通り過ぎれば、三角形のすぐ上から縁に至るまで、好きなレベルまでバケツを満たすことができます。他に謎めいた隙間はありません。

この論文は、非常に巧妙な**非構成的（non-constructive）**な手法を用いています。すべての可能なサイズに対して具体的な数字の集合を構築する（それには永遠に時間がかかるでしょう）代わりに、著者は集合を生成する「機械」を構築します。この機械の設定をわずかに微調整することで、結果として得られる和集合のサイズは滑らかに変化します。変化が滑らかで連続的であるため、この機械は範囲内のあらゆる整数値を通過しなければなりません。それはダイヤルを回すようなものです。各目盛りがどこにあるかを知る必要はありません。ただ、ダイヤルが始点から終点まで滑らかに動くのであれば、その間のすべての数に必ず当たるはずなのです。決定的なのは、この証明は特定のサイズを実現する集合が「存在する」ことを保証しますが、どの集合がその特定のサイズを作り出すのかという「どの集合か」までは教えてくれないということです。

3の特別なケース

この論文はまた、$h=3$（数字を3回混ぜ合わせる）という特定の、長年の謎も解決しています。ここでの著者の主張は、大きな袋の数字を必要とせず、もしあなたが2つより多くの数字（$k > 2$）を持っていれば、すべての可能な和集合のサイズを得ることができる、ということです。ただし、唯一の特定の「ゴーストナンバー」である $3k - 1$ だけは除きます。

例えば、5つの数字があり、それらを3回混ぜ合わせる場合、可能なサイズは最小値から最大値までとなりますが、$14$ という数だけは除外されます。あなたは13を得ることもでき、15を得ることもできますが、14は不可能です。これは、この特定のシナリオに対する完全かつ正確な回答です。

まだ残されている謎

この論文は、大きな集合の場合と $h=3$ の場合のケースを解決しましたが、いくつかの扉を開けたままにしています。著者は、この「全範囲、ただし三角形を除く」というルールは、材料の数 $k$ が混ぜ合わせる回数 $h$ よりも大きい限り、より小さな集合に対しても実際に成り立つのではないか、という大胆な推測（予想）を提示しています。

しかし、この論文は、非常に小さな集合の場合や、混ぜ合わせる回数が材料の数よりもはるかに多い場合、ルールが再び複雑になることを認めています。禁止された三角形の外側にも、まだ見つけられていない他の隙間が存在する可能性があります。また、著者は、この問題が人工知能（具体的には、ChatGPTの一種が証明の最適化に役立ったことに言及しています）を用いて解決できる可能性があることも示唆しており、この数学の未来には、人間とコンピュータが協力して完璧な配置を見つけ出す作業が関わってくることを示唆しています。

要約すると、この論文は「和集合の宇宙」の地図を描いています。数字が行くことのできない禁止区域を示し、材料が十分に多ければ、それ以外の場所では風景が繋がり、完結していることを証明しています。それは混沌とした問いを、いくつかの神秘的な穴を除いて、クリーンで予測可能なパターンへと変えるものです。そして、数学者たちが理解するために何年も費やすであろう、いくつかの謎めいた空白を残しています。