Lifting all elements in $\mathrm{SL}_n(\mathbb{Z}/q\mathbb{Z})$

この論文「LIFTING ALL ELEMENTS IN SLn(Z/qZ)」は、数論的群 $SL_n(\mathbb{Z})$ からその合同部分群による商 $SL_n(\mathbb{Z}/q\mathbb{Z})$ への射影 $\pi_q$ において、すべての要素を「最適」なノルム制約内で持ち上げる（リフトする）問題について研究したものです。

以下に、問題設定、手法、主要な貢献、結果、そしてその意義について詳細にまとめます。

1. 問題設定と背景

• 問題: 任意の $q$ に対して、写像 $\pi_q: SL_n(\mathbb{Z}) \to SL_n(\mathbb{Z}/q\mathbb{Z})$ は全射である（強い近似定理）。ここで、行列 $\gamma \in SL_n(\mathbb{Z})$ のノルム $\|\gamma\|$ を演算子ノルムとする。任意の $x \in SL_n(\mathbb{Z}/q\mathbb{Z})$ に対し、$\pi_q(\gamma) = x$ かつ $\|\gamma\| \le T$ となる $\gamma$ が存在する最小の $T$（直径）はどの程度か？
• 平均ケースと最悪ケースのギャップ:
  • 平均ケース（Almost-diameter）: 最近の研究（Theorem 1.1）により、$q$ が平方因子を持たない場合、$SL_n(\mathbb{Z}/q\mathbb{Z})$ の要素の「ほとんどすべて」は、ノルム $T \approx q^{1+1/n}$ のリフトを持つことが示されている。これは鳩の巣原理による下限と一致する。
  • 最悪ケース（Diameter）: しかし、「すべての」要素をカバーする場合、より大きなノルムが必要になる可能性がある。Sarnak は $n=2$ の場合に $T \approx q^2 \log q$ 程度の上限を示したが、一般の $n$ における厳密な評価は未解決だった。
• 目的: 平均ケース（$q^{1+1/n}$）と最悪ケース（直径）の間のギャップを明確にし、すべての要素をリフトするための最適（またはほぼ最適）なノルム上限と下限を決定すること。

2. 主要な結果

著者らは以下の 2 つの主要定理を証明しました。

• 定理 1.2（下限の証明）:
  任意の $\epsilon > 0$ に対して、十分大きな $q$ に対し、ノルムが $C_{n,\epsilon} q^{2-\epsilon}$ 以上のリフトしか持たないような要素 $x \in SL_n(\mathbb{Z}/q\mathbb{Z})$ が存在する。

  • 意味: 最悪ケースのノルムは $q^2$ に近い。平均ケースの指数 $1+1/n$ と最悪ケースの指数 $2$の比は$2n/(n+1)$であり、$n=2$では$4/3$、$n \to \infty$で$2$ に収束する。これは「大きな穴（big holes）」と呼ばれる現象であり、平均と最悪の間に大きな隔たりがあることを示す。

• 定理 1.3（上限の証明）:
  定数 $C_n$ が存在し、任意の $q$ と任意の $x \in SL_n(\mathbb{Z}/q\mathbb{Z})$ に対して、$\|\gamma\| \le C_n q^2 \log q$ を満たすリフト $\gamma \in SL_n(\mathbb{Z})$ が存在する。

  • 意味: 最悪ケースでも $q^2$ のオーダー（対数因子付き）でリフト可能である。これは Sarnak の $n=2$ における結果を一般化し、わずかに改善したものである。

3. 証明の手法と主要なステップ

定理 1.2（下限）の証明

この証明の核心は、加法組合せ論（Additive Combinatorics）、特にBohr 集合を用いた構成にあります。

1. 対角行列の構成: 特定の対角行列 $x \in SL_n(\mathbb{Z}/q\mathbb{Z})$ を選び、そのリフト $\gamma$ の対角成分が満たさなければならない線形方程式（$SL_n$ の接空間に由来）を解析する。
2. Proposition 1.4: もし $(\mathbb{Z}/q^2\mathbb{Z})^\times$ 内に、$|\beta^n|$ が小さく、かつ $|n\beta|$ が大きい（$q^2$ に近い）ような元 $\beta$ が存在すれば、その $\beta$ を用いた対角行列 $x$ は、ノルムが $q^2$ に近いリフトしか持たないことが示される。
3. Theorem 1.5（大きな $n$ 乗根の存在）: 任意の $q$ に対して、$|\alpha| < C$ かつ $|\beta^n| = |\alpha|$、さらに $|n\beta| > C^{-1}q^{1-1/k}$ を満たす $\alpha, \beta \in (\mathbb{Z}/q\mathbb{Z})^\times$ が存在することを示す。
   • Bohr 集合の議論: 小さな $n$ 乗根の集合から生成される集合を考え、Bohr 集合 $B(A, \rho)$ が非自明であると仮定して矛盾を導く。
   • 一般化された算術級数（GAP）: Bohr 集合は低ランクの GAP で近似できる。この近似構造上で、$\beta$ による乗法が線形作用（行列）として振る舞い、それらが可換かつ $n$ 乗でスカラー行列になることを示す。
   • 対角化と鳩の巣原理: 多数の可換行列が存在すると、それらは同时对角化可能であり、対角成分の $n$ 乗根の比が有理数でなければならないという矛盾が生じる（構成された $\alpha$ は無理数比を持つように選ばれるため）。これにより、そのような $\beta$ が存在し、定理 1.2 が成立する。

定理 1.3（上限）の証明

この証明は Sarnak の $n=2$ における戦略を一般化したもので、2 段階の構成を行います。

1. 最初の $n-1$ 行のリフト: $SL_n(\mathbb{Z}/q\mathbb{Z})$ の最初の $n-1$ 行を、ノルム $O(q \log q)$ の整数行列にリフトする。
   • ここでは、行ベクトルが素数 $p$ に対して線形独立になるように調整する必要がある。数論的性質（Jacobsthal 関数の評価や素数の分布）を用いて、小さな係数でこの条件を満たすリフトが存在することを示す（Proposition 4.1）。
2. 最後の行のリフト: 残りの 1 行を補完して行列式が 1 になるようにする。
   • 最後の行の成分は $O(q^2 \log q)$ のオーダーになることを許容する（Proposition 4.2）。
   • 線形代数（$\mathbb{Z}/q\mathbb{Z}$ 上での基底変換）を用いて、最後の行を $q$ 倍の誤差の範囲内で調整し、最終的な行列を構成する。

4. その他の貢献と考察

• Lemma 1.6: 最初の $n-1$ 行が $T$、最後の行が $T^2$ で抑えられるような $SL_n(\mathbb{Z})$ の要素の個数を評価し、この構成が本質的に最適であることを示唆している。
• アフィン空間と射影空間への拡張（第 5 章）:
  • $SL_n(\mathbb{Z})$ がアフィン空間 $A_q$ や射影空間 $P_q$ に作用する場合の「直径」についても考察を行っている。
  • $P_q$ における直径の上限が $1$（$\log q$の係数）であることを示し、$n=2$の場合に$P_q$の直径が$2$ 倍の「almost-diameter」に達しうることを指摘している。これは LPS グラフの直径問題や、四元数代数の文脈とも関連している。

5. 意義と結論

• 数論的群の幾何学的理解: この研究は、数論的群の「直径」と「平均直径」の間に本質的なギャップが存在することを厳密に証明した点で画期的です。Sarnak が提唱した「big holes」の現象が、$n \ge 2$ のすべての場合に成立することを示しました。
• 手法の革新: 定理 1.2 の証明において、加法組合せ論（Bohr 集合と GAP）を数論的リフト問題に応用した点は、独立した興味深い結果（Theorem 1.5）としても価値があります。
• 最適性の確立: 最悪ケースのノルムが $q^2$ のオーダーであることを示すことで、これ以上改善できない（あるいは $q^{1+1/n}$ から $q^2$ へのギャップは避けられない）という結論に達しました。これは、暗号理論や数論的アルゴリズムにおけるリフト問題の限界を理解する上で重要です。

総じて、この論文は $SL_n(\mathbb{Z})$ の合同部分群による商へのリフト問題における「最悪ケース」の振る舞いを完全に解明し、平均ケースとの対比を通じて、数論的群の構造に関する深い洞察を提供しています。