Primes in LCM recurrences

本論文「Primes in LCM recurrences（LCM 漸化式における素数）」は、Benoît Cloitre によって 2008 年に導入された、最大公約数（GCD）に基づく Rowland の素数生成漸化式の LCM（最小公倍数）版に関する研究です。

以下に、問題の背景、手法、主要な貢献、結果、および意義について詳細な技術的サマリーを記述します。

1. 問題の背景と定義

Rowland の漸化式（GCD 版）:
2008 年、Rowland は以下の漸化式が常に 1 または素数である「初項差」を生成することを示しました。
$$a_1 = 7, \quad a_n = a_{n-1} + \gcd(n, a_{n-1}) \quad (n \ge 2)$$
この場合、$a_n - a_{n-1}$ は常に 1 または素数となります。

本研究の対象（LCM 版）:
著者は同年、以下の LCM 版漸化式（OEIS A135504）を導入しました。
$$a_1 = 1, \quad a_n = a_{n-1} + \text{lcm}(n, a_{n-1}) \quad (n \ge 2)$$
ここで注目すべき量は、乗法的増分 $b_n$ です。
$$b_n = \frac{a_n}{a_{n-1}} - 1 = \frac{n}{\gcd(n, a_{n-1})}$$
初期値は $2, 1, 2, 5, 1, 7, \dots$ となります。

主要な予想（Conjecture 1.1）:
すべての $n \ge 2$ に対して、増分 $b_n$ は 1 または素数である。
数値計算では $n=10^6$ までこの予想は確認されていますが、完全な証明は未解決です。

2. 難点と障壁（Linnik の壁）

GCD から LCM への変更は問題の本質を 2 点で変化させます。

1. 累積効果: $a_n$ は過去のすべての増分の積 $a_n = \prod_{k=2}^n (1+b_k)$ となるため、過去のすべての情報が永続的に符号化されます。
2. Linnik の定理との関連: Ruiz-Cabello は、この予想の点ごとの証明には、任意の素数 $p$ と $k \ge 1$ に対して、$q \equiv -1 \pmod p$ かつ $q < p^{k+1}$ となるような少なくとも $k$ 個の素数 $q$ の存在が必要であることを示しました。これは、Linnik の定理における定数 $L=2$ のケースに相当します。
   • 現在の Linnik の定理の最良の既知の bound は $L \le 5$ (Xylouris) であり、$L=2$ は未解決のオープン問題です。したがって、点ごとの証明は現在の数論の技術では不可能な壁に直面しています。

3. 手法：コンパニオン・スクリー法（Companion-Sieve Framework）

著者は、点ごとの証明ではなく「平均的な」アプローチを採用することで、Linnik の壁を回避しました。

• 決定論的部分の抽出: $a_{n-1}$ の $p$ 進評価を直接扱う代わりに、素数インデックス $q$ における増分 $(1+b_q) = q+1$ からなる決定論的な部分積 $C_{n-1}$ を抽出します。
• 上界の緩和: 正確な商 $b_n$ の代わりに、扱いやすい上界（コンパニオン）を導入します。
  • $B^{(P)}_n := n / \gcd(n, C_{n-1})$
  • さらに、重複を無視し、各素数 $p$ が $(q+1)$ を通じて少なくとも 1 回現れたかどうかのみをカウントする「1-hit コンパニオン」$B^{(1)}_n$ を定義します。
• 不足（Deficit）の概念: 素数 $p$ に対する「1-hit 不足」$\delta^{(1)}_p(n)$ を定義します。
  $$\delta^{(1)}_p(n) = \max\{0, v_p(n) - S^{(1)}_p(n-1)\}$$
  ここで $S^{(1)}_p(m)$ は $m$ 以下の $q \equiv -1 \pmod p$ となる素数の個数です。
• 不足判定基準: もし $\sum_p \delta^{(1)}_p(n) \le 1$ ならば、$b_n$ は 1 または素数になります。

このアプローチにより、問題は「素数の等分布（Bombieri-Vinogradov 定理など）を用いた、等差数列における素数の個数に関する平均的な評価問題」に変換されました。

4. 主要な結果

定理 1.2（密度 1 の定理）

$b_n \in \{1\} \cup \mathbb{P}$ となる整数 $n$ の集合は、漸近密度 1 を持ちます。

• 証明の概要: Bombieri-Vinogradov 定理を用いて、中程度の moduli における素数の誤差項を平均的に制御します。小素数、中素数、大素数に分類し、それぞれで不足が 1 以下となることを示します。例外となる整数の集合は密度 0 です。

定理 1.3（有効な有限縮小）

任意の $P_0 \ge 2$ に対して、計算可能な上限 $N^*(P_0)$ が存在し、$n \ge N^*(P_0)$ において、予想の反例が存在するならば、その反例 $b_n$ のすべての素因数は $P_0$ より大きい必要があります。

• 意義: 反例を探す際、小さな素因数を持つケースは排除され、巨大な素因数のみを考慮すればよいことが示されました。

定理 1.4 & 1.5（双子素数との関係と K=2 版）

漸化式を $x_n = 2x_{n-1} + \text{lcm}(n, x_{n-1})$ と変更した K=2 版（$c_n$ と定義）を研究しました。

• 双子素数の検出: この系列の増分パターンは双子素数と密接に関連しています。
  • $c_p = 1$ となる素数 $p$ は、$p-2$ が素数（双子素数）であることを示唆します（$p=7$ を除く）。
  • 逆に、双子素数 $(p, p+2)$ に対して、$p>5$ なら $c_p=p$ かつ $c_{p+2}=1$ となります。
• 条件付き密度 1 定理: 双子素数の分布に関する Brun 型の上限仮定と、素数インデックスでの振る舞いに関する仮定の下で、K=2 版も密度 1 の性質を持つことを証明しました。

5. 追加の予想と未解決問題

残された障壁（密度 1 以外の部分）を克服するために、2 つの新しい予想が提示されました。これらは現在の無条件の技術と Montgomery の予想の間に位置します。

1. 予想 7.2（平方窓内の第 2 素数）:
   すべての素数 $p \ge 17$ に対して、$\pi(p^2; p, -1) \ge 2$（$p^2$ 未満に $-1 \pmod p$ となる素数が少なくとも 2 つ存在する）が成り立つ。

   • これにより、$p^2$ で割れる整数に対する「大素数の平方因子」の障壁が解消されます。

2. 予想 7.3（除数安全な等分布）:
   整数 $n$ の素因数 $p$ に対して、誤差項 $E(n-1; p, -1)$ が平均的な Bombieri-Vinogradov のレベルではなく、個々の $n$ に対して制御可能であるという仮説です。

   • これにより、「中程度の bad moduli」の障壁が解消されます。

もし Elliott-Halberstam 予想（$\vartheta > 1/2$）と予想 7.3 が成り立てば、すべての十分大きな $n$ に対して元の予想が証明されることが示唆されます。

6. 意義と結論

• 理論的意義: 単純な算術的漸化式が、素数の等分布（特に等差数列における素数）の深い結果を検証・必要とする窓を開くことを示しました。
• 手法の革新: 点ごとの証明の困難さ（Linnik の壁）を、平均的な等分布定理（Bombieri-Vinogradov）と「コンパニオン・スクリー」という新しい枠組みを用いて回避し、密度 1 の結果を無条件に証明しました。
• 双子素数との接続: K=2 版の漸化式が双子素数を「検出」するメカニズムを持つことを明らかにし、数論的構造と素数分布の間の新たなつながりを示しました。
• 将来の展望: 残された障壁（大素数の平方因子、2 つの大素数の積、個別的な bad moduli）を克服するための具体的な予想が提示され、今後の研究の道筋が示されました。

本論文は、素数生成漸化式という具体的な対象を通じて、現代解析数論の最前線の問題（Linnik の定数、双子素数予想、Elliott-Halberstam 予想など）と深く結びついた重要な貢献を果たしています。