🔢 mathematics

The Nim-Sum of a Random Integer Partition

本論文は、整数分割 $N$ における敗北位置の割合の一次漸近挙動を決定する。その割合は $1/(\sqrt{N}\log N)$ のスケールでゼロに収束するが、自然なスケールで正規化した後、収束することなく、代わりに二進境界付近でのポアソン・パリティ遷移を伴う二進ののこぎり歯状パターンを示す。

原著者： Daewon Kim

公開日 2026-08-28✓ Author reviewed ⓘ

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Daewon Kim

原論文は CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

石の山を用いたゲームを想像してみてください。そこでは、2人のプレイヤーが交互に、単一の山から任意の数の石を取り除きます。目標は、最後に動くこと、あるいは逆に、相手を勝ち筋のない状態に追い込むことです。これはニム（Nim）と呼ばれるゲームであり、戦略的なパズルとして1世紀以上にわたって研究されてきた古典的な問題です。勝利の秘訣は、石の総数を数えることではなく、二進法的な加算と減算を組み合わせた特定のルールを用いて、各山の大きさを組み合わせることにあります。この組み合わせがゼロになった場合、その番で動くプレイヤーは、相手が完璧にプレイすると仮定した場合、負ける運命にあります。数学者たちは数十年にわたり、どのような特定の山の配置に対しても、これらの敗北局面を特定する方法を知ってきました。しかし、より深く、より捉えがたい疑問が残っていました。もし、決まった数の石を集めて、それらをランダムに山に分けたとしたら、その配置が敗北局面となる確率はどのくらいになるのでしょうか。

この問いは、ゲーム理論と、数をより小さな整数に分解する方法を扱う数学分野である整数の分割（整数分割）の研究が交差する場所に位置しています。単一のゲームのルールは正確かつ決定的ですが、開始位置がランダムに選ばれた場合のこれらのゲームの挙動は、驚くほど複雑です。石の総数が大きくなるにつれて、敗北局面の頻度が単純な漸近的パターンに落ち着くのかどうかは、自然な問いです。しかし、ハワイ大学マノア校のデウィオン・キムによる新しい研究は、答えが単なる安定化よりもはるかに複雑であることを明らかにしました。石の総数が増えるにつれて、敗北局面が見つかる生の確率はゼロに向かって減少していきます。しかし、その確率を自然な基準値で調整した「正規化された密度」に注目すると、たとえ石の数がどれほど大きくなっても決して安定することのない、ギザギザとした繰り返しのパターンを描いて振動するのです。

キムの研究は、石の総数が偶数である特定のケースに焦点を当てています。なぜなら、ゲームのルール上、奇数の総数が敗北局面を形成することはあり得ないからです。この研究では、個々の分割をすべて書き出すのではなく、高度な計数手法を用いることで、石の総数が2万に達するまでのあらゆる可能な合計値について、敗北局面の正確な数を算出しました。その結果、正規化された密度は単一の定数値に近づくのではなく、問題の規模に関連する自然なスケールが2の累乗を越えるたびに繰り返される、鋸歯状（のこぎり状）のパターンを描いて激しく上下することを示しています。もし密度をグラフ化すれば、低点から高点へと着実に上昇し、その後急激に下降し、再び上昇を開始するという線が見えるでしょう。このサイクルは無限に繰り返されます。つまり、正規化された密度は、このサイクルのどこにいるかに完全に依存して、特定のベースライン値の1倍から2倍の間のどこかになるのです。

この挙動を駆動しているメカニズムは、ゲームの勝利ルールの二進法的な性質に根ざしています。大きな数がより小さな部分に分解されるとき、最も小さな部分は、二進数の下位ビットをかき混ぜ、それらを一様で予測不能に見せるランダム性の源として機能します。最も大きな部分は非常に稀であるため、結果に影響を与えることは滅多にありません。しかし、部分のサイズには、特定の「中間範囲」が存在し、それがクリティカルなボトルネックとして機能します。この範囲において、部分は結果に影響を与えるほど十分に大きい一方で、消失してしまうほど大きくはありません。この範囲に落ちる部分の数が、結果を左右します。この範囲は、石の総数が増えるにつれてシフトするため、ゲームのバランスが揺れ動きます。規模のスケールが2の累乗の直前にあるとき、バランスはある方向に傾き、その閾値を越えると、バランスが反転し、密度が跳ね上がります。

これを理解するために、時計の針が特定の時間を迎えるたびにリセットされるものの、その針の動く速度自体が時計のサイズによって変化するプロセスと比較してみるとよいでしょう。石の総数が増加するにつれて、部分のサイズの「クリティカルな範囲」は上方へと移動していきます。敗北局面の密度の振動を駆動する主要な要因は、このクリティカルな範囲に含まれる部分の数の偶奇性（パリティ）です。部分の分布は、稀な事象を記述するためにしばしば用いられるポアソン分布に似た法則に従っているため、この範囲における偶数個の部分を持つ確率が振動し、それが鋸歯状のパターンを生み出します。研究は、石の総数が増大するにつれて、正規化された密度が単一の数値に収束するのではなく、その値の集合が、特定のスケーリング因子の1倍から2倍の区間全体を満たすことを確認しています。

この研究は、敗北局面だけでなく、固定された特定のターゲットとなる結果についても拡張されています。二進法的な意味での特定の数を目指す場合でも、任意の固定されたニム和（nim-sum）に対して、密度は同じ一次の減衰を示し、同じ正規化を行った後には、同じ二進的な鋸歯状のプロファイルに従います。これは、ゲームの二進法的な構造が、ランダムな山の分布の中に永続的な署名を残しており、その署名は数の巨大さによっても消し去られることがないことを示唆しています。

理論的な予測を検証するために、著者は合計2万までのあらゆる可能な石の配置について厳密な計算を行いました。これには、大規模な計数問題としての高度な計算手法が必要でした。計算結果は、理論的な予測と驚くほど正確に一致しており、鋸歯状のパターンが実在するものであり、数学モデルによる人工的な産物ではないことを裏付けました。データは、正規化された密度が理論の予測通りに上昇・下降し、規模のスケールが2の累乗を越える正確な瞬間に鋭い遷移が起こることを示しました。

また、研究はこのピークとバレー（谷）の間の遷移の性質についても掘り下げています。グラフは不連続なジャンプがあるように見えますが、統計的な観点からは、その変化は決して一瞬で起こるわけではありません。クリティカルな範囲にある部分の数が偶数か奇数かによって制御されるこの変化は、石の総数が増えるにつれてどんどん狭まっていく範囲の中で、緩やかな推移として現れます。石の総数が増加するにつれて、この平滑化が発生するウィンドウはより狭くなり、見た目にはジャンプがより鋭く見えるようになりますが、数学的な構造としては連続性を保っています。この現象は、なぜ基礎となる数学が滑らかであるにもかかわらず、データがこれほどまでにギザギザに見えるのかを説明しています。

最終的に、この研究は、開始構成がランダムに選ばれた場合のニムにおける敗北局面の分布に関する完全な記述を提供しています。それは、これらの局面の頻度に関する長年の疑問を解決し、それらが単純で安定した傾向に従うのではなく、部分のサイズとゲームの二進法的な構造との間の複雑な相互作用によって支配されていることを示しています。これらの知見は、数学におけるより広範な原理を浮き彫りにしています。すなわち、ランダムで滑らかに見えるシステムであっても、深い算術的構造が、平均化されることに抵抗する持続的で鋭いパターンを作り出すことがあるということです。ゲームの二進法的な性質は、特定の情報のブロックが、システムがいかに大きくなろうとも可視的で影響力のある状態であり続けることを保証し、数字が大きくなるにつれて永遠に繰り返されるリズムを生み出しているのです。

技術要約：ランダムな整数の分割におけるニム和

問題提起
本論文は、総数（トークンの総数） $N$ が固定された通常のニム（Nim）のポジションにおける計数論的性質を調査している。ニムにおいて、ポジションはヒープ（山）のサイズのマルチセットとして定義される。ブートン（Bouton）の定理によれば、ポジションが負けの状態であるための必要十分条件は、ヒープのサイズのビットごとの排他的論理和（XOR）がゼロであることである。ヒープの順序を無視する場合、これらのポジションは整数分割に対応する。

中心となる問題は、比率 $a_N / p(N)$ の漸近挙動を決定することである。ここで、 $p(N)$ は $N$ の全整数分割数であり、 $a_N$ は各部分のXOR和がゼロとなる分割の数である。パリティ（奇偶性）による制限は明白である（ $N$ が奇数の場合、和とXORは最小最下位ビットを共有するため $a_N = 0$ となる）。しかし、偶数 $N$ における負けポジションの分布は、標準的な分割の漸近解析では捉えきれない、複雑で非収束的な振動挙動を示す。具体的には、偶数 $N$ において生の密度はゼロに収束するが、適切に正規化された密度は非収束的な振動挙動を示す。

手法
著者は、組合せ論的分解、確率モデル、および解析的数論を組み合わせた多角的なアプローチを採用している。

組合せ論的分解: 論文では、部分の多重度に基づいて分割 $\lambda$ を2つの構成要素に分解する。部分 $j$ が $c_j$ 回現れるとき、 $c_j = 2r_j + \varepsilon_j$ （ただし $\varepsilon_j \in \{0, 1\}$ ）と書くことができる。偶数個のコピー（ $2r_j$ ）はXOR和において相殺されるため、残るのは「奇数コア」（ $\varepsilon_j=1$ である部分）のみとなる。これにより、問題は「相異なる部分からなる分割」のXORを解析することへと簡約される。
ボルツマン・サンプリング: 独立性を利用するため、研究は総数がランダムであるボルツマン・モデルへと移行する。このモデルにおいて、相異なる部分の包含を示すインジケーターは独立なベルヌーイ変数である。XOR和がゼロになる確率は、整数を臨界スケール $J$ に関する3つの二進的な範囲に分割することで分析される：
- 下位ブロック ( $[1, J)$ ): これらの小さな部分は下位ビットをランダム化し、下位ビットに対してほぼ一様な分布を作り出す。
- 臨界ブロック ( $[J, 2J)$ ): この範囲が一次の確率を決定する。このブロック内のすべての整数は同じ最上位 $J$ ビットを持つ。このブロックのXORの最上位ビットがゼロになるための必要十分条件は、この範囲で選択された部分の個数が偶数であることである。この条件が満たされる場合、下位ブロックは残りの下位ビットの残差と一致しなければならない。
- 上位ブロック ( $[2J, \infty)$ ): これらの大きな部分は稀であり、一次項への寄与は無視できるほど小さい。
二進階層構造とウォルシュ解析: 著者らは、有限公式を導出し、近似を精緻化するために、ウォルシュ解析（ $\mathbb{F}_2$ 上の特性関数による直交性）を利用している。二進階層はボルツマン近似を任意の代数的次数まで精緻化するが、固定サイズへの転送は一次のオーダーにおいてのみ確立されている。より多くの上位ビットを保持することによって公式の階層構造が構築され、これによりボルツマン確率を任意の代数的次数まで決定することが可能となる。
鞍点解析: ボルツマン・モデル（ランダムなサイズ）から、固定サイズ（固定された $N$ ）の分割へと結果を転送するために、生成関数に対する鞍点法を用いる。生成関数の偶性により、2つの等しい鞍点（ $q = e^{-t_N}$ および $q = -e^{-t_N}$ の付近）が特定される。
厳密計算: ウォルシュ公式と中国剰余定理（CRT）に基づいた厳密なアルゴリズムを実装し、 $N=20,000$ までの $a_N$ を計算した。これは、漸近公式の検証および有限サイズ補正の分析に使用される。

主要な結果
論文は、負けポジションの密度の一次漸近挙動を確立している。 $\tau_N = \pi/\sqrt{6N}$ および $B_N = \log(1/\tau_N)/\tau_N$ とする。また、 $J_N$ を乗法的距離において $B_N$ に最も近い2のべき乗とし、 $\Lambda_N = e^{-\tau_N J_N}/\tau_N$ と定義する。

偶数 $N$ に対して、比率は次のように与えられる：
$\frac{a_N}{p(N)} = \frac{1 + e^{-2\Lambda_N} + o(1)}{J_N}$

主な知見は以下の通りである：

非収束性: 正規化された密度 $B_N \frac{a_N}{p(N)}$ は定数に収束しない。その部分列極限の集合は、 $[1, 2]$ の全区間である。
二進鋸歯状波: その挙動は「二進鋸歯状波（dyadic sawtooth）」パターンに従う。 $N$ が増加するにつれ、値は各バイナリ・フェーズ（ $B_N$ が2のべき乗を横切る際）において1から2へと上昇し、スケールが新しい2のべき乗を横切るときに1へと戻る。
ポアソン平滑化: 二進境界における明らかな不連続性は、ポアソン乱数のパリティ則によって、縮小するスケール上で平滑化される。具体的には、 $N$ が境界に接近し、 $\tau_N K - \log(1/\tau_N) \to c$ （ここで $K$ は2のべき乗）となる場合、極限は $1 + e^{-2e^{-c}}$ となる。
一般的なニム和: この結果はゼロのXOR和に固有のものではない。任意の固定されたターゲット・ニム和 $x$ について、ニム和が $x$ となる分割の密度は、パリティ・クラス $N \equiv x \pmod 2$ に沿って同じ一次プロファイルに従う。
厳密なカウント: 論文はOEIS数列A048833をインデックス10,000（総サイズ $N=20,000$ ）まで拡張しており、予測されたスケールと有限サイズ誤差の構造を裏付ける厳密なデータを提供している。

意義と主張
本論文は、制約のない整数分割における負けニム・ポジションの完全な一次漸近記述を提供すると主張している。その意義は、「滑らかな」ランダム構造（整数分割）が、下位ビットがランダム化され、上位ビットの影響が無視できるレベルになった後も、単一の臨界的な二進ブロックが存在することによって、鋭い算術的特徴（バイナリ・パリティ）を保持していることを明らかにした点にある。

本研究は、負けポジションの密度が $\Theta(1/(\sqrt{N} \log N))$ のオーダーであるが、単一の漸近定数を持たないことを示している。著者は、二進階層によってボルツマン近似を任意の代数的次数まで精緻化できることを強調しているが、これは有限サイズ補正が重要である理由を説明している。論文は、非収束性が近似の失敗ではなく、問題の構造的な特徴であることを結論付けており、フェーズ間の遷移はポアソン変数のパリティによって支配されている。

本論文は、増大するターゲット・ニム和や制限付き分割に関する一般的な問題を解決しようとするものではなく、それらを自然な未解決問題として留めている。また、有限サイズ補正の分析が完全な二次漸近定理を構成するとは主張しておらず、それは一様な高次導関数の境界ではなく、形式的な展開に基づいていることを明記している。

関連論文