支払えない最大の金額を、ついにぴったり抑え込む

何種類かの硬貨だけを無制限に受け付け、おつりは決して出さないレジを想像してほしい。ちょうど支払える金額もあれば、決して支払えない金額もある。数学者は硬貨の額面を生成元と呼び、一見すると単純な問いを立てる。支払えない最大の金額はいくらか。

決して支払えない金額

すべてに共通する約数をもたない整数a₁ < a₂ < … < aₙを考える。これらの数を、それぞれ好きな回数だけ足し合わせて得られる合計は「表現可能」であるという。表現可能でない整数は有限個しかない。そのうち最大のものがフロベニウス数Fである。（額面の一つが1なら、どんな金額でも支払えるので、Fは−1と定める。）

小さな例を挙げよう。3、4、6の硬貨なら、3、4、6、7、8と、それ以降のすべての金額を支払えるが、1、2、5は決して支払えない。したがってF = 5である。3と6には共通の約数があることに注意してほしい。大切なのは、3つすべてに共通する約数がないことだ。

硬貨が2種類なら、厳密な答えがある。シルベスターの公式F(a₁, a₂) = a₁a₂ − a₁ − a₂である。3種類以上の場合、仕事はFを上から抑えること、つまり、Fが硬貨から計算されるある値を超えないことを証明することになる。

しぶとい2倍の因子

ポール・エルデシュとロナルド・グラハムは、生成元が3つ以上の場合について次のことを証明した。

F ≤ 2aₙ₋₁⌊aₙ/n⌋ − aₙ

ここでaₙは最大の値、aₙ₋₁は2番目に大きい値、nは値の個数であり、⌊ ⌋は切り捨てを表す。シルベスターの公式と同じく、大きいほうから2つの硬貨が関わっている。

2人は最悪の場合、つまりn個の値がすべてt以下のときに取りうる最大のFも見積もった。2人の見積もりのあいだにあるおよそ2倍の開きから、エルデシュ問題#433として記録されている予想が生まれた。ジャック・ディクスミエはこれを解決し、さらに、あらゆる組に対して成り立つもっと単純な上界**F ≤ aₙ²/(n − 1)**も証明した。2倍の因子は消えたが、2番目に大きい硬貨も一緒に消えてしまった。

大きいほうから2つの硬貨を両方残す

浙江大学コンピュータ科学技術学院のLin Chen、Tingwei Hu、Yuchen Mao、Guochuan Zhangは、両方を手に入れたいと考えた。2倍の因子をなくし、しかも2番目に大きい硬貨を残すことである。2つ以上の値からなる任意の組に対して成り立つ、彼らの答えは次のとおりだ。

F ≤ aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙ − 1

ここで⌈ ⌉は切り上げを表す。エルデシュとグラハムの上界と比べると、2倍の因子が消えている。その代わりに、nではなくn − 1で割り、切り上げている。ディクスミエの上界と比べると、2番目に大きい硬貨が最大の硬貨に比べて小さいとき、新しい上界はかなり小さくなりうる。

3、4、6の例では、エルデシュとグラハムの上界は10、ディクスミエの上界は18を与え、新しい上界は4 × 3 − 6 − 1 = 5、つまりちょうど真の値を与える。これは驚くにはあたらない。この組は、上界にちょうど達するようにつくられた、後で述べる極端な例の族に属しているからだ。論文は、典型的な組についての比較は示していない。

金額を余りで仕分ける

証明は、エルデシュとグラハムの道筋をたどる。すべての金額を、最大の硬貨aₙで割った余りによって仕分ける。小さいほうの硬貨の和がある余りに達すれば、そこにaₙを何枚か足すことで、同じ余りをもつそれより大きいすべての金額に到達できる。課題は、どの余りにも安く到達できることを示すことである。

鍵となる道具は、和の集合がどれだけ大きくなければならないかについてのクネーザーの定理だ。エルデシュとグラハムはこれを使って、約aₙ/n枚の硬貨の和が余りの半分より多くをカバーすることを示し、それを2倍にしてすべての余りをカバーした。こうした和に含まれる硬貨は1枚あたり高々aₙ₋₁の価値なので、硬貨の枚数を2倍にすればコストも2倍になる。これが2倍の因子の由来である。

新しい証明では、⌈aₙ/(n − 1)⌉枚の硬貨の和を使う。これらの和が一部の余りを取りこぼすとき、クネーザーの定理によれば、取りこぼされた余りはでたらめに散らばっているのではなく、一定の間隔で並んだ余りの族をまるごと形づくる。欠けている族が多いほど、小さいほうの硬貨は、到達した各族により多く詰め込まれなければならない。そのため、そうした族にはどれも小さい硬貨がいくつか含まれ、欠けている族に届くために追加で必要になる数枚の硬貨は安くすむ。合計は決して⌈aₙ/(n − 1)⌉ × aₙ₋₁を超えない。

この最初のステップで得られるのは、最後の「− 1」がない上界である。最後の1単位は、ただ1通りでしかつくれない和についてのScherkとKempermanの定理にもとづく、別の議論から得られる。その議論は、境界上の金額aₙ₋₁⌈aₙ/(n − 1)⌉ − aₙそのものが常に支払えることを示す。謝辞によれば、著者たちはまず弱いほうの上界を証明した。その後GPT-6が、それを1だけ下げる議論を見つけるのを助け、さらに上界をこれ以上下げられないことの証明や英文の校正も手伝った。著者たちは、最終的な原稿については自分たちが責任を負うと述べている。

ちょうど限界に達する例

この上界はこれ以上下げられない。n ≥ 3のどの場合についても、著者たちはFがちょうどこの上界に等しくなる組を無限に多く構成している。任意のq ≥ 2をとり、q、2q、…、(n − 1)qという値に(n − 2)q + 1を加える。1つを除いてすべてqの倍数なので、q単独で支払えない金額は、これらを使っても支払えない。この組は2種類の硬貨qと(n − 2)q + 1のように振る舞い、シルベスターの公式は新しい上界とちょうど一致するFを与える。n = 3、q = 3とすると、この方法で生まれるのはまさに先ほどの3、4、6の例である。

硬貨が少ないほど、天井は低く

この上界は、密度の観点から読むこともできる。小さいほうからi個の値と最大の値からなる縮小した組でも、それらがまだ共通の約数をもたない限り、上界は成り立つ。硬貨を取り除いても支払いは難しくなるだけなので、縮小した組について証明された天井は、元の組についても成り立つ。結果を左右するのはおおよそaᵢ/iで、これは最初のi個の値が1からaᵢまでの数をどれだけ密に埋めるかの逆数にあたる。最も密なグループが勝つ。とくに、残りの硬貨すべてに共通する約数がまだない場合には、2番目に大きい硬貨はいつでも単に脇に置いてよい、と著者たちは指摘している。

この論文は純粋に理論的なものにとどまっている。典型的な硬貨の組で新しい上界がどれだけ小さくなるかについての数字は示しておらず、上界が最良であることが証明されているのは、額面が3種類以上の場合だけである。