Transversal Difference Numbers in Finite Abelian Quotients

技術要約：有限アーベル剰余における横断的差数（Transversal Difference Numbers）

問題提起
本論文は、有限アーベル群のペア $(G, H)$ （ただし $H \le G$）における横断的差数（transversal difference number）$\delta(G, H)$ について研究している。$G/H$ に対する横断集合 $T \subseteq G$ とは、$H$ の各剰余類から正確に1つの代表元を含む集合である。$T$ のサイズは $|G/H|$ で固定されているが、その差サポート $D(T) = T - T = \{t_1 - t_2 : t_1, t_2 \in T\}$ のサイズは、$H$ の $G$ への埋め込み方によって変化する。中心となる問題は、以下の最小サポートサイズを決定することである：
$$\delta(G, H) = \min_{T} |D(T)|$$
この不変量は、差集合問題（要素の多重度に焦点を当てるもの）や差基底問題（集合のサイズが可変であるもの）とは異なるものである。ここでは、集合のサイズは固定されており、目的はサポートの最小化である。

動機
主な動機は、完全準同型暗号（FHE）、特に Peikert と Pepin による「Vive Galois!」フレームワークに由来する。この文脈において、横断集合は、円分部分体にわたる自己同型拡大のための CRT（中国剰余定理）基底をインデックス化するために使用される。これらの操作に必要な「周囲の自己同型ラベル（ambient automorphism labels）」の集合は、差サポート $T - T$ に対応する。$|T - T|$ を最小化することは、パッキングされたブートストラップ・プロシージャにおける、個別の自己同型操作（および関連するキー・スイッチング・コスト）の数を減らすことに繋がる。本論文は、$\delta(G, H)$ が、特定の実装コストやセキュリティ・パラメータに依存しない、ラベル集合の理論的な下限を測定するものであることを明らかにしている。

手法
著者らは、以下の加法組合せ論および有限アーベル群論のツールを用いている：

1. ファイバー分解（Fiber Decomposition）: 剰余方向 $a \in G/H$ に基づいて差サポート $D(T)$ を分解する。
2. シングルトン削減（Singleton Reduction）: 「シングルトン方向」（差ファイバーのサイズが1となる方向）を特定し、それらが $H$ と交わりを持たない部分群へと持ち上げられることを示し、その部分群による商をとることで、問題を「原始的（primitive）」な横断集合へと簡約化する。
3. クネーザーの定理（Kneser's Theorem）: 和集合（および差集合）のスタビライザーに基づく下限を利用して、直積群や鎖（chains）の推定を精緻化する。
4. 有限体パラメトリゼーション: $G = (\mathbb{Z}/p^2\mathbb{Z})^2$ という特定のケースにおいて、横断集合を関数 $f: \mathbb{F}_p^2 \to \mathbb{F}_p^2$ のグラフとしてモデル化する。差サポートは、**キャリー補正された有限体微分（carry-corrected finite-field derivatives）**を通じて分析され、問題は和積現象（sum-product phenomena）および像の拡大へと結び付けられる。
5. 確率的および多項式的手法: ランダムなリフティング引数と、固定多項式のリフティング解析を用いて、平方平面（square-plane）の場合の漸近的挙動を確立する。

主要な結果と貢献

1. 一般の下限:
   論文は以下の一様な下限を確立している：
   $$\delta(G, H) \ge 2|G/H| - m(G, H)$$
   ここで $m(G, H)$ は、$G$ のうち $H$ と交わりを持たない部分群の最大次数である。この下限は、シングルトン・ファイバーの分析と原始的横断集合への簡約によって導出される。

2. 巡回剰余（Cyclic Quotients）:
   この下限は、すべての巡回剰余に対して**シャープ（鋭い）**であることが証明されている。$G/H$ が位数 $q$ の巡回群である場合、$\delta(G, H) = 2q - m(G, H)$ である。この結果は既知のケースを一般化し、巡回的な周囲群に対する厳密な公式を提供する。

3. 直積族と交差横断推定:
   クネーザーの定理を用いることで、一方が「非分離（nonsplit）」な巡回 $p$ 群であり、他方が任意の群である直積群に対する厳密な公式を導出している。具体的には、$G = C_{p^a} \times L$ および $H = p^b C_{p^a} \times \{0\}$ （ただし $1 \le b < a$）の場合、$\delta(G, H) = |L|(2p^b - 1)$ となる。これは、直積構造が、「同一素数」の非分離座標が含まれない限り、しばしば乗法的であることを示している。

4. 平方平面の障害（奇素数）:
   論文は、$G_p = (\mathbb{Z}/p^2\mathbb{Z})^2$ および $H_p = pG_p$ （奇素数 $p$ に対して）を、巡回理論および直積理論が破綻する最初の真に新しい障害として特定している。

   • 予想: $\delta(G_p, H_p) = (2p - 1)^2$ である。この値は「座標ボックス」横断（標準的なリフト）に対応する。
   • 無条件の下限: 著者らは $\delta(G_p, H_p) \ge 3p^2 - p - 1$ を証明している。
   • 証拠:
     • 小素数: 決定論的な検証により、$p=3$ および $p=5$ において予想が正しいことが確認されている。
     • ランダム・リフティング: 一様にランダムな横断集合は、$p \to \infty$ のとき、予想される境界を満たす確率が1に収束することが示されている。
     • 固定多項式: 十分に大きな素数に対して、いかなる固定された整数多項式リフティング規則も反例を生み出すことはできないことが証明されている。

5. 2次トーションの障害:
   $p=2$ のケースにおいて、もし $G/H$ が $C_2 \times C_2$ 部分群を含む場合、下限は厳密に $2|G/H| + 1$ へと改善されることが証明されており、これにより2次トーションのケースが奇素数の理論から分離される。

意義と主張
本論文は、横断的差数の研究における最初の真に新しい残留的障害、すなわち同一素数の平方平面 $(\mathbb{Z}/p^2\mathbb{Z})^2$ を孤立させたことを主張している。巡回および混合素数のケースは完全に解決されている一方で、奇素数の平方平面のケースは依然として予想の段階にある。

著者らは、自らの研究を、有限アーベル剰余の「残留的（residual）」な幾何学に関する厳密な代数的調査として位置付けている。彼らは、自らの結果が FHE 実装の問題を直接解決するものではない（実行時間やセキュリティは $|T-T|$ 以外の要因にも依存するため）ことを明言しており、むしろそのようなシステムの Galois/CRT ブックキーピングにおけるラベル集合の正確な代数的下限を提供することを目的としている。技術的な核心は、この群論的問題を有限体の微分像へと翻訳し、その後、これらの像を境界付けるために包含および多項式の手法を適用することにある。

未解決問題
論文は、平方平面の予想を中心的な未解決問題として提示して締めくくっている。また、高ランクの平方モジュラス剰余 $(\mathbb{Z}/p^2\mathbb{Z})^r$ に関する問いや、一般の下限に対して厳密な改善を強いる原始的な剰余幾何学の分類についても問いを投げかけている。