Asymptotics of the Tchoukaillon array and a conjecture of Beluhov

技術要約：チュカヨン配列の漸近性とベルーホフの予想

問題設定
本論文は、一列のマカラ・ソリティア・ゲームから生じる正の整数の無限配列 $\mathcal{C}_{i,j}$ である、チュカヨン配列（Tchoukaillon array）の漸近的挙動を扱う。この配列は、すべての正の整数が正確に一度ずつ現れるように定義されている（$\mathbb{N}^2 \to \mathbb{Z}^+$ の全単射）。配列の境界の漸近的挙動は既知であったが（列0はフラヴィウス・ジョセフース篩に対応し $\mathcal{C}_{i,0} \sim \frac{\pi}{4}i^2$、行0はチュカヨン数に対応し $\mathcal{C}_{0,j} \sim \frac{1}{\pi}(j+1)^2$）、一般的な内部の項 $\mathcal{C}_{i,j}$ の挙動は未解決の問題であった。

N. ベルーホフ（N. Beluhov）は、数値的証拠に基づき、大きな $i$ および $j$ に対して、以下の近似式が成り立つと予想した：
$$\mathcal{C}_{i,j} \approx \frac{(\pi i + 2j)^2}{4\pi}$$
本論文の目的は、この予想を証明し、厳密な誤差項を提供し、レベル集合 $\{(i,j) : \mathcal{C}_{i,j} \le V\}$ の漸近的な形状を決定することである。

手法
証明は、「トレース（軌跡）」の手法に基づいている。これは、配列の構成から視点を変え、配列の次数 $k$ が増加するにつれて、単一の整数値 $M$ の軌跡を追跡するというものである。

1. トレース漸化式： 著者は、次数 $k$ の配列における値 $M$ の位置を示す座標 $(X_k, Y_k)$ を定義する。$k=1$ のときの位置 $(M-1, 0)$ から出発して、値 $M$ は次数 $N = i+j+1$ における最終的な位置 $(i, j)$ へと移動する。その運動は、以下の結合された床関数（floor recurrence）に従う：
   $$X_k = X_{k-1} - \left\lfloor \frac{Y_{k-1}}{k} \right\rfloor, \quad Y_k = Y_{k-1} - \left\lfloor \frac{X_{k-1}}{k} \right\rfloor$$
   この漸化式は $X$ と $Y$ に関して対称であり、この構造的特徴が解析において極めて重要となる。

2. 共役幅（Conjugate Widths）： 漸化式の減少量を直接合計する代わりに、著者は「共役幅」$R_m$ および $S_m$ を導入する。これらは、減少量がレベル $m$ を超えるステップの数を表す。これにより、問題を減少量の「階段状」の和へと変換する。

3. 丸めによる線形化： 幅の漸化式には床関数が含まれている。著者は、これらが、最近接整数への丸め誤差によって摂動を受けた下三角線形システムとしてモデル化できることを示す。丸め項を取り除くことで、システムは中心二項係数によって駆動される2つのスカラー漸化式へとデカップリング（分離）される。

4. ウォリス・モード（Wallis Modes）： 線形化されたシステムは、$c_m = \binom{2m}{m}/4^m$ および $w_m = 1/(2m c_m)$ という数列を含む2つの異なるモード（固有ベクトル）を生み出す。これらの数列は、$\pi$ に関するウォリスの公式に関連している。最終的な漸近公式に現れる定数 $\pi$ および $2$ は、境界の定理からではなく、配列の再帰からのみ導かれるこれらのモードを通じて自然に現れる。

5. 誤差の均衡： $M$ を幅から復元するために、著者は「単一レベル読み取り（single-level reading）」戦略を用いる。彼らは、2つの競合する誤差源を均衡させる：特定のレベル $m$ で $M$ を読み取る際の「サンドイッチ」誤差（$m$ が大きくなるにつれて減少する）と、幅の丸めによる「量子化」誤差（$m$ とともに増加する）である。最適な均衡は $m \asymp N^{2/3}$ で発生し、最終的な誤差界を与える。

主な貢献および結果

1. ベルーホフの予想の証明： 本論文は、$N = i+j+1 \to \infty$ のとき、
   $$\mathcal{C}_{i,j} = \frac{(\pi i + 2j + 2)^2}{4\pi} + O(N^{4/3})$$
   がすべての $i, j \ge 0$ に対して一様に成り立つことを証明した。これにより、ベルーホフの予想（主要項に対応）が確認され、中心化された明示的な主項が提供された。

2. 平方根則： 同等に、項の平方根は漸近的に線形である：
   $$\sqrt{\mathcal{C}_{i,j}} = \frac{\sqrt{\pi}}{2}i + \frac{1}{\sqrt{\pi}}(j+1) + O(N^{1/3})$$
   これは、内部における成長率が、2つの端（列0と行0）の成長率の線形混合であることを示している。

3. レベル集合の幾何学的形状： 系として、本論文は、レベル領域 $\{(i,j) : \mathcal{C}_{i,j} \le V\}$ が、直線 $\pi i + 2j = 2\sqrt{\pi V} - 2$ によって境界付けられた漸近的な三角形であり、幅 $O(V^{1/6})$ の境界層を持つことを確立している。

4. 整数の特定アルゴリズム： トレース漸化式は、与えられた整数 $M$ に対して行と列のインデックス $(i, j)$ を決定するための $O(\sqrt{M})$ アルゴリズムを導く。これは、配列内の整数の位置を迅速に決定する方法に関するクヌース（Knuth）の問いに答えるものである。

意義および主張
本論文は、境界については既知の結果があるものの、依然として未解決であったチュカヨン配列の漸近的構造を解決したと主張している。主な意義は以下の通りである：

• 再帰から定数を導出： 漸近公式に現れる定数 $\pi$ および $2$ は、既存の境界定理とは独立して、ウォリスの公式を介した配列の再帰的定義から本質的に導かれることが示された。
• 一様性： この結果は、配列全体にわたる一様な推定を提供し、既知の端の挙動の間の溝を埋めるものである。
• 手法的な洞察： 単一の整数の「トレース」を解析し、床関数漸化式を丸み誤差を伴う線形システムに変換する手法は、同様の組合せ論的配列に対する新しいアプローチを提示している。

著者は控えめに、証明された誤差項は $O(N^{4/3})$ であるが、数値的証拠は真の誤差が $O(N)$（あるいは平方根のスケールでは $O(1)$）であることを示唆していると述べている。しかし、現在の証明は単一レベルにおける点推定に依存しており、より優れた界を得るために必要な、レベル間の丸め誤差の相関を制御する手法にはまだ至っていない。著者は、より鋭い誤差項の特定を未解決問題として残している。