---
name: Lehmer's totient conjecture 深掘り (2026-04-20 朝)
description: Lehmer 1932 (φ(n)|n-1 ⟹ n prime) の n ≤ 10^5 検証 0 violations + Lean 4 8 zero-sorry + 奇数 r dominance 新発見.
type: project
originSessionId: 79081859-fd56-4821-a0d2-932be27d647a
---
# Lehmer's Totient Conjecture 深堀 (2026-04-20)

## 対象問題

**Lehmer 1932**: ∀n≥2, φ(n) | (n-1) ⟹ n 素数.

- 94 年間 OPEN
- 実証: n < 10³⁰ (Cohen/Hagis 2011 et al.)
- 必要条件: Lehmer counterexample は odd / squarefree / ≥14 prime factors

## 本 session 成果

### 1. 実証 (`scripts/lehmer-totient-verify-rei-lens.ts`)

- n ∈ [2, 10⁵] で **0 violations** ✅
- 9,592 primes (= π(10⁵)) が自明方向を通過
- 実行時間 < 1 秒 (smallest prime factor sieve)

### 2. Lean 4 `LehmerTotient.lean` (8 theorems, zero-sorry)

- `no_lehmer_counterexamples_leq_1000` — n ≤ 1000 で Lehmer 反例ゼロ (native_decide)
- `all_primes_leq_1000_are_lehmer` — 自明方向 Lean 4 化
- `lehmer_equiv_prime_leq_1000` — iff for n ∈ [2,1000]
- `prime_implies_lehmer_holds` — 構造的証明 (Nat.totient_prime 使用, decide ではない)
- `pi_1000_equals_168` — sanity check
- Build time 21 秒 under Mathlib v4.27.0

### 3. ★ 新発見: 奇数 r dominance ★

Near-miss distribution (n-1) mod φ(n) = r for n ≤ 10⁵:

| r | count | 比率 |
|---|---|---|
| 0 (Lehmer/prime) | 9,592 | 9.59% |
| **1** | **5,133** | **5.13%** |
| 2 | 3 | 0.003% |
| **3** | **2,762** | 2.76% |
| 4 | 3 | 0.003% |
| **5** | **1,929** | 1.93% |
| 6 | 2 | 0.002% |
| **7** | **1,492** | 1.49% |
| 8 | 5 | 0.005% |
| 9 | 3 | 0.003% |

**★ 奇数 r が偶数 r を 1000 倍以上の密度で支配 ★**

理由の推測: n 偶数なら n-1 奇数, φ(n) 偶数なので r = (n-1) mod φ(n) 必ず奇数. n odd なら n-1 偶数, φ(n) 偶数なので r 偶数. 偶数 n は n ≤ 10⁵ で 1/2 だが、そのうち φ(n) が large な場合 r = n-1 そのまま = 奇数に落ちる. 

### 4. Rei HARD_96 overlap

5,689/9,592 primes = **59.31%** が HARD_96 residue に落ちる.

Coprimality baseline: HARD_96 の coprime-to-6 部分 (19/24) に primes > 3 が均等分布すると仮定すれば 19/32 = **59.4%**.

→ **Rei-specific signal は無し** (Oppermann の primeHi +14.97% / Legendre の top-5 {5,7,11,17,19} のような非対称性は本問題では未発見)

## 新規 AI 生成 open question (Q22-Q25)

**Q22**: Why does odd r strongly dominate even r in the near-miss distribution (n-1) mod φ(n)? Is this a purely structural (parity) effect, or are there deeper residue-class biases?

**Q23**: What is the smallest "k-Lehmer" number (composite n with φ(n) | (n-k)) for small k > 1?
  - k=1: (Lehmer, open)
  - k=2: smallest such n?
  - k=3: ...

**Q24**: Does the Rei HARD_96 exact match-to-baseline (59.31% vs 59.4%) indicate that Lehmer's problem is "topologically coprime-neutral" in contrast to Collatz atomic cores?

**Q25**: Lehmer's necessary conditions require ≥14 prime factors. Rei's atomic cores are primes × small factors. Does n=ATOMIC_CORE imply φ(n) relationship structure with Collatz peak primes (577, etc.)?

## D-FUMT₈ 状況

| 項目 | state |
|---|---|
| Lehmer n ≤ 10⁵ 実証 | TRUE (0 violations) |
| Lehmer 全般 ∀n | NEITHER (1932 OPEN) |
| Lean 4 finite proof n ≤ 1000 | TRUE |
| Q22 odd r dominance 因果説明 | NEITHER → FLOWING (parity 仮説) |
| Q23 k-Lehmer 小例 | NEITHER |
| Q24 HARD_96 baseline 一致 | TRUE (coincidence or structural?) |

## commit

`(commit ID upon push)`

## 次候補

1. Q22 parity 仮説の 厳密検証 (even n の分布を切り分け)
2. Q23 k-Lehmer 探索 for k ∈ [2, 10]
3. Paper 120 合冊候補: Legendre + Lehmer + Andrica/ES + Q19-Q25
4. Gilbreath's / Agoh-Giuga 等の他 unsolved problems 深堀継続