論文概要

タイトル: A Fast Algorithm for Denumerants with Three Variables
著者: Feihu Liu, Guoce Xin
所属: 首都師範大学 数学科学部（中国）
日付: 2024 年 6 月 27 日

1. 研究の背景と問題定義

• 問題の定義:
  正整数 $a, b, c$ ($a < b < c$) かつ $\gcd(a, b, c) = 1$ に対して、非負整数 $n$ に対する方程式 $ax_1 + bx_2 + cx_3 = n$ の非負整数解の個数を表す関数 $d(n; a, b, c)$ を「Denumerant（デヌメラント）」と呼びます。これは制限付き分割関数（Restricted partition function）の一種です。
• 既存の課題:
  • $k=2$ の場合、Sylvester により明示的な公式が知られています。
  • $k \ge 3$ の場合、Frobenius 数（解が存在しない最大の整数）の計算や、$d(n; a, b, c)$ の計算は困難です。
  • 従来のアルゴリズム（Popoviciu, Lisoněk, Brown et al., Binner など）は、計算量が $O(a_1 a_2)$ や $O(\log a_3)$ 程度であり、変数の大きさ（特に $a_2$ や $a_3$）に依存していました。
• 本研究の目的:
  3 変数の場合において、入力パラメータ $a, b, c$ の対数オーダー、具体的には $O(\log b)$ の時間計算量で $d(n; a, b, c)$ を計算する高速アルゴリズムを提案することです。

2. 手法と主要な技術

本研究は、定数項法（Constant Term Method）と、特定の変換技術（Key Transformation）を組み合わせることで、再帰的な削減プロセスを構築しています。

A. 定数項法（Constant Term Method）

Denumerant を複素変数 $\lambda$ を用いた定数項（Constant Term, CT）として表現します。
$$d(n; a, b, c) = \text{CT}_\lambda \frac{\lambda^{-n}}{(1-\lambda^a)(1-\lambda^b)(1-\lambda^c)}$$
これを厳密に計算するために、 slack variables（$z_1, z_2, z_3$）を導入し、極限操作 $\lim_{z_i \to 1}$ を行います。

B. 部分分数分解と変換定理

• 部分分数分解: 有理関数を部分分数分解し、定数項を各項の極限値の和として抽出します（Corollary 2.2）。
• Key Transformation (Theorem 2.3): $\gcd(u, a)=1$ のとき、以下の等式が成り立ちます。
  $$\text{CT}_\lambda \frac{1}{1-z\lambda^a} F(\lambda) = \text{CT}_\lambda \frac{1}{1-z^{1/u}\lambda^a} F(\lambda^u)$$
  この変換により、分母の指数を操作し、問題の構造を単純化できます。

C. 削減アルゴリズムの核心（Euclid 様再帰）

アルゴリズムは、以下のステップで構成されます。

1. GCD の削減:
   一般の $(a, b, c)$ を、$\gcd(a, b)=1$ となるように変換します（Lemma 3.1）。
2. 2 項への分解:
   定数項を $T(a)$ と $T(b)$ の 2 つの項に分解します（式 9）。
3. 変数の削減（$b=1$ または $a=1$ への帰着）:
   Key Transformation を用いて、$T(a)$ は $b=1$ のケースに、$T(b)$ は $a=1$ のケースにそれぞれ変換します（式 11）。
4. 再帰的計算（Lemma 3.2）:
   符号付き剰余（signed remainder）を用いた Euclid 互除法に似た再帰操作を適用します。
   • 定数項のタイプ $(1^\circ; a, 1, c)$ を、定数項のタイプ $(2^\circ; a, 1, c)$（有理関数として直接計算可能）と、新しい定数項 $(1^\circ; a', 1, c')$ に分解します。
   • ここで、新しい指数 $a'$ は $a' \le a/2$ となります。
   • この操作を $\log a$ 回（または $\log b$ 回）繰り返すことで、最終的に有理関数の和の形に帰着させます。
5. Slack Variables の除去:
   得られた有理関数の和に対して、$z_i \to 1$ の極限を計算します。これにはベクトル $\mu$ を用いた置換と、定数項演算子の線形性を利用した公式（式 16）を適用します。

3. 主要な成果と結果

• アルゴリズムの提案:
  入力 $n, a, b, c$ ($a < b < c$) に対して、$d(n; a, b, c)$ を計算する「Algorithm 1」を提案しました。
• 計算量:
  アルゴリズムの時間計算量は $O(\log b)$ です。
  • 既存の最速のアルゴリズム（Binner, 2020）が $O(\log a_3)$ だったのに対し、本研究は $a < b < c$ の順序において、中間の変数 $b$ に対する対数オーダーを達成しました。
  • 各ステップでの演算は定数時間（$O(1)$）の環演算であり、再帰の深さが対数であるため、全体として対数時間となります。
• 具体例:
  $a=3, b=7, c=11, n=25$ のケースにおいて、アルゴリズムを適用し、正しく $d(25; 3, 7, 11) = 3$ を導出する手順を示しました。

4. 意義と将来展望

• 理論的意義:
  • 定数項法と Key Transformation を組み合わせることで、3 変数の Denumerant 計算において、変数の大きさに依存しない極めて効率的なアルゴリズムを構築しました。
  • Barvinok のアルゴリズム（計算幾何学）の文脈において、定数項を有理関数の和として表現する項数 $N$ が、特定の戦略下で $\log a_1$ の多項式で抑えられることを示唆しています（Lemma 3.2 は戦略 $h=1$ に対応し、項数が $\log a$ 以下になることを保証します）。
• 今後の課題:
  • Open Problem 5.2: 計算量をさらに $O(\log a)$（最小の変数 $a$ に対して）に改善できるアルゴリズムの存在が問われています。現在のアルゴリズムは $O(\log b)$ であり、$a$ と $b$ の差が大きい場合にさらに最適化の余地があります。
  • 一般の $k$ 変数への拡張や、より複雑な戦略 $h$ の検討が今後の研究課題として挙げられています。

結論

この論文は、3 変数の線形ディオファントス方程式の解の個数を計算する問題に対し、定数項法を基盤とした新しい高速アルゴリズムを提案し、$O(\log b)$ の計算量で解を導出可能であることを実証しました。これは数論的組合せ論における重要な進展であり、大規模なパラメータを持つ問題に対する効率的な解決手段を提供しています。