Additive Bases from Primitive Dyck Words: Regular Underapproximations, Motzkin Coding, and Digit Lifting

あなたは、非常に特殊な種類の数パズルを解こうとしている探偵だと想像してください。数学の世界には、加法的数論と呼ばれる分野があり、そこではシンプルながらもトリッキーな問いを投げかけます。「特定のグループに含まれるすべての数字を、いくつかの特別な『構成要素』となる数字を足し合わせることで作り出すことができるか？」という問いです。これは、限られたレゴブロックを使って、そのブロックだけですべての可能なタワーの高さを構築できるかどうかを知るゲームのようなものです。時には2つのブロックが必要なこともあれば、時には10個必要なこともあります。このゲームの「位数（オーダー）」とは、あらゆるタワーを作るために必要となる最大数のブロックのことです。

このゲームをプレイするために、数学者たちは非常に具体的な構成要素となるブロックを使用します。これらのブロックは、バイナリ（コンピュータ言語の0と1）で書いたときに、完璧にバランスの取れた括弧のように見える数字です。数学では、これらは**ディック語（Dyck words）**と呼ばれます。例えば、1100は有効なブロックです。なぜなら、1を「上」へのステップ、0を「下」へのステップとして扱うと、2回上がり、2回下がるものの、一度も開始地点を下回ることがないからです。著者たちは、これらをさらに絞り込んだ、**原始的（primitive）**なブロックに焦点を当てています。これらは「原子的な」破片であり、それ以上小さなバランスの取れたペアに分解することができません。大きな問いは、これらすべての原始的なブロックを足し合わせて、あらゆる偶数を作るとき、最大でいくつのブロックが必要になるか、ということです。

この論文は、2つの異なる数学的ツールを組み合わせることで、このパズルを解くためのマスタークラスとなっています。著者たちは、これらのバイナリ・ブロックが、モツキン・パス（Motzkin path）と呼ばれる別の種類のパスと秘密の関係を持っていることを発見しました。これにより、問題を（ベース4の言語である）別の言語へと翻訳し、より簡単に解けるようにしたのです。彼らは、ほとんどの偶数はわずかな数のブロックで構築できる一方で、構築するのが非常に難しい、執拗な数字のグループが存在することを証明しました。具体的には、46という数字が最も難しく、8個のブロックを必要とし、他にも7個を必要とする数字がいくつかあることを突き止めました。しかし、彼らはまた、848を超えると、どんなに大きな偶数であっても、6個以下のブロックで構築できることを証明しました。これは、膨大な数の宇宙の中で「ワーストケース（最悪のシナリオ）」を見つけ出し、混沌が終わり、秩序が始まる正確な場所を証明する物語です。

バイナリ・バランサーの物語

冒険に飛び込みましょう。栗山隆之氏を中心とする著者たちは、バランスの取れたバイナリ文字列の言語から来る数字の集合を調査しています。赤（1）と青（0）の光の列を想像してください。「ディック語」とは、赤と青の光が同じ数あり、かつ左から右へ数えていったときに、どの時点においても青の数が赤の数を超えることがない文字列のことです。それは、ステップを合わせるまでステージから降りることができないダンスのようなものです。

著者たちが興味を持っているのは、「原始的な」ダンサーたちです。これらは、最初に戻る（高さゼロになる）のが、まさに最後の一回だけである文字列のことです。もし文字列が途中でゼロに戻るなら、それは2つの小さなダンスを繋ぎ合わせたものであり、原始的なものではありません。彼らはこれらの文字列を（バイナリとして読み取ることで）数字として扱い、これらの原始的な数字を足し合わせて、あらゆる偶数を作るためにいくつの数字が必要かを問います。

秘密のコード：バイナリからベース4へ
この論文における素晴らしい一手は、これらのバイナリ文字列に隠された構造があることに気づいた点です。ビットをペアにする（00, 01, 10, 11）と、それらはベース4のシステムにおける桁（0, 1, 2, 3）として機能します。著者たちは完璧なマップを発見しました。すなわち、すべての原始的なディック数（最小の2を除く）は、3で始まり0で終わるベース4の数であり、その中間に「モツキン」の単語を持つものと対応しているのです。

モツキン・ワードを、上がったり、下がったり、あるいは平坦に進んだりできるパス（ただし、決して地面の下には行かない）と考えてください。この接続こそが、この論文の「ロゼッタ・ストーン」です。これにより、複雑なバイナリ文字列に関する難しい問題を、よりクリーンなベース4の数とこれらの平坦な歩行パスに関する問題へと翻訳することが可能になります。この翻訳によって、彼らが研究している数の集合が「デジタル的に閉じている（digitally closed）」こと、つまり、ある数の中に含まれる数字があれば、特定の桁を付け加えることで新しい数を生成できることが多いということが明らかになりました。

二段構えの戦略
パズルを解くために、著者たちは4で割ったときの振る舞いに基づいて、二段構えの攻撃を仕掛けます。

1. 「簡単な」トラック（4の倍数）： 4で割り切れる数に対して、著者たちは「規則的な下近似（regular underapproximation）」を用います。これは、もっと簡単に言えば、扱いやすい、より単純で予測可能な部分集合を見つけたことを意味します。彼らは、このより単純な集合が、大きな4の倍数をわずか6個のブロックで構築するのに十分強力であることを証明しました。
2. 「トリッキーな」トラック（4 mod 2の数）： 4で割ったときに余りが2になる数（6, 10, 14など）の場合、この単純な集合では不十分です。ここでは、「モツキン・コード化」された家族の全力を活用します。彼らは、このより大きく複雑な家族が、これらの数をわずか5個のブロックで構築できることを証明しました。

「リフティング（持ち上げ）」の魔法
彼らが検証した数だけでなく、どのようにして「すべての」大きな数に対してこれが成り立つと言えるのでしょうか？ 彼らは**「桁のリフティング（digit lifting）」**という手法を用います。想像してみてください、ある一定の高さまで届く小さな梯子があるとします。著者たちは、ある連続した範囲の数を特定の数のブロックで構築できるならば、ブロックの端に特定の数字を付け加えるだけで、より大きなすべての数を構築する能力を「リフト（持ち上げる）」できるという定理を証明しました。これは、「高さ100のタワーを構築できれば、自動的に高さ400、401、402などのタワーも構築できる」という魔法のルールを持っているようなものです。これにより、彼らは有限の検証済みリストから、そのパターンが永遠に続くことを証明することができます。

結果：執拗な数字たち
道具を整えた後、著者たちは例外を分類するために作業に取り掛かりました。彼らは、ほとんどの偶数は構築しやすい一方で、より多くのブロックを必要とする特定の「執拗な」数字のリストがあることを発見しました。

• 難易度のチャンピオン： 数は46が最も困難です。これは7個以下のブロックでは構築できず、厳密に8個を必要とします。
• ランナーアップ（次点）： 7個のブロックを必要とする他の数は10個あります：34, 44, 98, 154, 198, 202, 206, 838, 842, 846 です。
• 閾値（しきい値）： 著者たちは、848が魔法の数字であることを証明しました。848以上のすべての偶数は、6個以下のブロックで構築できます。

彼らは単に推測したのではなく、この閾値までのすべてのケースを検証するために正確なコンピュータ計算を用い、そして数学的証明を用いて、それが無限に続くことを示しました。

なぜこれが重要なのか
この論文は、異なる数学の領域――コンピュータサイエンス（言語とオートマトン）、組合せ論（パスと木）、そして数論（加法）――がいかに美しく共演できるかを示す素晴らしい例です。著者たちは単に数字のリストを見つけたのではありません。彼らはフレームワークを構築したのです。複雑で非反復的なパターン（「文脈自由」言語）を持つ数字の集合であっても、その大部分をカバーする単純で反復的なパターン（「正規」言語）を見つけ出し、その隙間を埋めるために全容の複雑さを利用できることを示したのです。

彼らはまた、「オーダー」がルールによって変わることも発見しました。もし4の倍数だけを見るなら、5個のブロックしか必要ありません。しかし、4 mod 2の数を含めると、必要数は6に跳ね上がります。そして、もし絶対的なワーストケース（46を含む）を見るならば、8個が必要になります。

結局のところ、この論文は完全な地図を与えてくれます。どの数字が厄介者であるか、どこでトラブルが終わるのか、そして、これらの特別なバイナリ・ブロックを使用して、あらゆる大きな偶数を構築するための構成的アルゴリズム（ステップ・バイ・ステップのレシピ）を私たちは知っています。それは、一見混沌とした問題を図的な秩序を持つシステムへと変え、抽象的な数の世界においても、常に発見されるのを待っているパターンが存在することを証明しています。