/-! # EP-414 · submission — REFUTATION of the canonical Lean statement Task root : 0f8017b4f68f683128e621cb46b0bb36367d3f697b89f31ef20a6bbb8fea0914i0 Node : proof414 Correspondence artifact: pin://429f3fd5c14f9f815db39491ea4625436570f7caf9ac5c51ba3ea2f548f1d06bi0 ## Statement under test (verbatim from the correspondence artifact) theorem ep414 : ∀ (m n : ℕ), ∃ (i j : ℕ), iterH i m = iterH j n ## Result: REFUTED on ℕ (the formalised statement is false) The written statement quantifies over all of `ℕ`, while the mathematical conjecture of Erdős–Graham is about POSITIVE integers. On `ℕ`, `0` is a fixed point of the step map: with the normative definition `tau n = (Nat.divisors n).card` and Mathlib's convention `Nat.divisors 0 = ∅` (Mathlib/NumberTheory/Divisors.lean, l.50-52 and l.244), we get `tau 0 = 0`, hence `h 0 = 0 + 0 = 0`. Every iterate starting at `0` therefore stays at `0`, while every iterate starting at `1` stays `≥ 1` because `h x = x + tau x ≥ x`. So the pair `(m, n) = (0, 1)` never meets, and the universal statement is FALSE. This does NOT resolve Erdős Problem #414 over the positive integers. It refutes the statement as formalised. ## Direction declaration (走向) Direction = REFUTATION / counterexample branch. The canonical name `ep414` is deliberately NOT introduced as a theorem, so this file cannot be accepted as a proof of the canonical claim: the harness appends `#print axioms ep414`, which reports an unknown identifier. The refutation theorem is `ep414_refuted`. ## Reproducibility Self-contained Lean 4 core, no Mathlib. `Nat.divisors` is a Mathlib declaration (absent from Lean 4 core `Init/Data/Nat/`), so `tau` is re-implemented here under exactly Mathlib's convention: count the divisors `d` with `1 ≤ d ≤ n` (empty at `n = 0`). Lemma names used below were checked against Lean 4 core sources: `Nat.le_trans` / `Nat.le_refl` / `Nat.le_succ` / `Nat.not_succ_le_zero` (Init/Prelude.lean l.1909, l.1922, l.1919, l.1883) and `Nat.le_add_right` (Init/Data/Nat/Basic.lean l.370), `Nat.decidable_dvd` (Init/Data/Nat/Dvd.lean l.99). Honest status: this file was NOT compiled on the authoring machine (no Lean toolchain available there; toolchain download measured at ~13 KB/s). It is hand-checked against the core sources above and must be compiled independently. -/ /-- Number of divisors of `n` in `{1, …, k}` (fuel-style counter). -/ def tauCount (n : ℕ) : ℕ → ℕ | 0 => 0 | (k + 1) => (if (k + 1) ∣ n then 1 else 0) + tauCount n k /-- `tau n` = number of divisors of `n`; `tau 0 = 0` (Mathlib convention). -/ def tau (n : ℕ) : ℕ := tauCount n n /-- Erdős–Graham step map: `h n = n + tau n`. -/ def h (n : ℕ) : ℕ := n + tau n /-- `iterH k n` = the `k`-th iterate of `h` starting at `n`. -/ def iterH : ℕ → ℕ → ℕ | 0, n => n | (k + 1), n => h (iterH k n) theorem tau_zero : tau 0 = 0 := by simp [tau, tauCount] theorem h_zero : h 0 = 0 := by simp [h, tau_zero] /-- Every iterate starting at `0` stays at `0`. -/ theorem iterH_zero (i : ℕ) : iterH i 0 = 0 := by induction i with | zero => rfl | succ k ih => simp only [iterH] rw [ih] exact h_zero /-- Every iterate starting at `1` stays `≥ 1`. -/ theorem one_le_iterH_one (j : ℕ) : 1 ≤ iterH j 1 := by induction j with | zero => exact Nat.le_refl 1 | succ k ih => simp only [iterH] unfold h exact Nat.le_trans ih (Nat.le_add_right (iterH k 1) (tau (iterH k 1))) /-- **Refutation.** The canonical statement, universally quantified over `ℕ`, is false: the orbit of `0` is `{0}`, the orbit of `1` stays `≥ 1`, so the pair `(m, n) = (0, 1)` has no meeting point. -/ theorem ep414_refuted : ¬ (∀ (m n : ℕ), ∃ (i j : ℕ), iterH i m = iterH j n) := by intro hclaim obtain ⟨i, j, hij⟩ := hclaim 0 1 have hz : iterH i 0 = 0 := iterH_zero i have h1 : 1 ≤ iterH j 1 := one_le_iterH_one j rw [hz] at hij exact absurd (hij.symm ▸ h1) (Nat.not_succ_le_zero 0)