A More Efficient Algorithm for Finding the Number of Permutations of $\mathbb{ZZ}/n\mathbb{ZZ}$ with Distinct Partial Sums

技術要約：$\mathbb{Z}/n\mathbb{Z}$ の部分和がすべて異なる置換の数を求めるためのより効率的なアルゴリズム

問題提起
本論文は、偶数 $n$ に対する整数加法群 $\mathbb{Z}/n\mathbb{Z}$ における特定の置換の列挙について扱う。核心となる問題は、部分和（あるいは群の文脈における「階乗」）がすべて異なる置換 $\sigma = (\sigma_0, \sigma_1, \dots, \sigma_{n-1})$ の数を数えることである。具体的には、本論文は、$\mathbb{Z}/2k\mathbb{Z}$ の置換における「差集合（difference sets）」の数を数える、オンライン整数列大百科事典（OEIS）の数列 A141599 に焦点を当てている。

置換が「異なる差」を持つとは、集合の値 $d_i \equiv \sigma_i - \sigma_{i-1} \pmod n$ （$1 \le i \le n-1$）が $\mathbb{Z}/n\mathbb{Z}$ のすべての非ゼロ要素をちょうど一度ずつ含むことを指す。著者らは、このような置換は $n$ が偶数の場合にのみ存在することを指摘している。計算上の課題は、全置換の総数（$n!$）が階乗的に増大するため、総当たりによる列挙が大きな $n$ に対しては実行不可能であるという点にある。

手法
著者らは、探索空間を早期に枝刈りすることで、従来の総当たりアプローチを大幅に改善する再帰的バックトラッキング・アルゴリズムを提案している。その手法は、主に以下の3つの柱に基づいている。

1. 差集合とシーケンシング（Sequencings）の間の全単射
   本論文は、「異なる差を持つ差集合」と $\mathbb{Z}/n\mathbb{Z}$ の「シーケンシング」との間の形式的な全単射（定理1）を確立している。シーケンシングは、部分和 $s(\sigma, i) = \sum_{j=0}^i \sigma_j$ がすべて異なる置換として定義される。証明により、差集合 $D_\tau = (d_1, \dots, d_{n-1})$ はシーケンシング $\sigma = (0, d_1, \dots, d_{n-1})$ に写像でき、その逆も可能であることが示されている。これにより、著者らは差集合を直接数える代わりに、シーケンシングを数えることができる。

2. 乗算による対称性の削減
   補題2を利用して、著者らは、もし $\sigma$ がシーケンシングであり、$r$ が $n$ と互いに素な整数（$\gcd(r, n) = 1$）であるならば、要素ごとの積 $(r\sigma_0, r\sigma_1, \dots, r\sigma_{n-1})$ もまたシーケンシングになるという性質を利用している。これにより、アルゴリズムは特定の「枝」（$0, 1$から始まる置換）の個数を計算し、他の枝を考慮するためにオイラーのトーシェント関数$\phi(n/d)$ を掛けることで、個別に計算することなくカウントを行うことができる。

3. 再帰的な枝刈り（アルゴリズム2）
   新しいアルゴリズムの核となるのは、部分的な置換を構築する再帰的探索である。全置換を検証する従来の総当たり法とは異なり、このアルゴリズムは「部分和（partials）」の状態を保持する。

• 枝刈りの論理： 部分的な置換に新しい要素を加えた結果、部分和が既に現れた値であるか、あるいは（不適切に）0 になった場合、その枝は即座に放棄される。
• 効率性： これにより、無効な部分シーケンスを拡張する $(n-k)!$ 個の置換を探索することを防ぐ。例えば、$\mathbb{Z}/20\mathbb{Z}$ において、部分シーケンス $(0, 1, 19)$ はインデックス2で部分和が 0 となるため無効であり、アルゴリズムはこの枝全体を破棄し、バリデータへの $17!$ 回もの呼び出しを節約する。

主な貢献

• OEIS A141599 の新項の算出： 改善されたアルゴリズムを用いて、著者らは第10、11、12項（$n=20, 22, 24$ に対応）を算出した。値は以下の通りである：
  • $n=20$: 5,074,931,072
  • $n=22$: 298,557,044,000
  • $n=24$: 21,224,961,132,544
    第10項および第11項は、Bert Dobbelaere によって独立して検証されている。
• 理論的統一： 本論文は、差集合とシーケンシングの間の全単射に関する厳密な証明を提供し、古典的な結果（Gilbert, Gordon）と現在の計算的アプローチを統一している。
• アルゴリズムの最適化： 部分和の衝突に基づく早期終了を伴う再帰的枝探索の導入は、この特定の計数問題において現在知られている最も効率的な手法である。

結果とデータ分析
本論文は、偶数 $n \le 22$ に対するシーケンシングの数と全置換数（$n!$）を比較したデータ（表1および表2）を提示している。結果は、シーケンシングの割合が $n$ の増加とともに厳密かつ急速に減少することを示しており、$n$ が 1 ステップ進むごとに約 1 桁減少している。$n=22$ の場合、その比率は約 $2.66 \times 10^{-10}$ である。

この経験的な証拠は、枝刈り戦略の有効性を裏付けている。有効なシーケンシングは全置換の空間において極めて疎（sparse）であるため、完全な置換を生成して検証することは非効率である。無効な部分経路を即座に排除する再帰的アプローチは、観察された希薄さと一致している。

意義と主張
著者らは、自身のアルゴリズムが数列 A141599 の項を計算するための、現在知られている中で最も効率的な手法であると主張している。彼らは、時間計算量は依然として超多項式（指数関数よりはるかに悪いが、$O(n!)$ よりは良いと思われる）であるが、枝刈り技術は、無効な枝に対する無駄な計算を避けることで、総当たり法に対して「厳密な改善」を提供すると論じている。

論文は、さらなる計算アルゴリズムの改善は、新たな数学的変換が特定されない限り限定的であると控えめに結論付けている。具体的には、将来の進展は、既知の少数のシーケンシングから与えられた $n$ に対する全集合を写像できる完全な変換集合（互いに素な整数による乗算を超えたもの）を特定できるかどうかに依存する可能性があると示唆している。しかし、彼らはこの研究においてそのような変換を提案しておらず、現在の再帰的アプローチが、定義された問題に対して最先端（state-of-the-art）であると述べている。