Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Aether Catalog definitions — Novelty_BerggrenTreeZetaCore

Definition
Novelty_BerggrenTreeZetaCore

by raver1975 · Sep 14, 2026 · Mathlib c5ea003 (Lean v4.30.0)

aether-catalognovelty

Definition bundle for the Aether Catalog module Novelty.BerggrenTreeZetaCore, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.

Definition code
-- Def bundle generated from Novelty/BerggrenTreeZetaCore.lean by skeleton subtraction
import Mathlib

/-!
# The Berggren tree of primitive Pythagorean triples: seeds, words, and the hypotenuse

This file is the combinatorial backbone for the "zeta function of the Berggren tree"
project.  It sets up the Berggren ternary tree in its *Euclid-seed* coordinates and
proves the two facts that make an analytic theory possible at all:

* the map `w ↦ seed w` from ternary words to Euclid seeds is a **bijection** onto the
  set of admissible seeds `S = {(m,n) : n < m, 0 < n, gcd(m,n) = 1, m + n odd}`
  (`seed_bijective_onto_seeds`, `seedEquiv`);
* the hypotenuse of a node is `c(w) = m² + n²` (`hyp`), so the tree zeta function is a
  Dirichlet series over `S`.

The three Berggren matrices act on the seed by
`L (m,n) = (2m - n, m)`, `M (m,n) = (2m + n, m)`, `R (m,n) = (m + 2n, n)`,
and we check (`berggren_matrix_L/M/R`) that on the triple `(m²-n², 2mn, m²+n²)` these are
exactly the classical Berggren matrices
`A₁ = !![1,-2,2; 2,-1,2; 2,-2,3]`, `A₂ = !![1,2,2; 2,1,2; 2,2,3]`,
`A₃ = !![-1,2,2; -2,1,2; -2,2,3]` (the last one is `B₃` of `Shared.BerggrenTrees.B`).

## Main results

* `seed_isSeed` — every node of the tree is an admissible Euclid seed;
* `isSeed_reachable` — **completeness** (Berggren's theorem): every admissible seed is a
  node of the tree;
* `seed_injective` — **uniqueness**: distinct words give distinct nodes;
* `seedEquiv` — the resulting equivalence `List (Fin 3) ≃ {p // IsSeed p}`;
* `node_isPPT` — every node carries a primitive Pythagorean triple;
* `hyp_le_silver_pow`, `Mspine_hyp` , `Rspine_hyp` — the growth dichotomy: the largest
  hypotenuse at depth `k` grows like the square of the silver ratio `(1+√2)² = 3+2√2`,
  while the `R`-spine grows only quadratically (`2k² + 6k + 5`).
-/

namespace BerggrenZeta

/-! ## Part A. Seeds, moves and the tree -/

/-- Admissible Euclid seeds: `n < m`, `n ≥ 1`, `gcd (m,n) = 1` and `m + n` odd.
These parametrise primitive Pythagorean triples via `(m²-n², 2mn, m²+n²)`. -/
def IsSeed (p : ℕ × ℕ) : Prop :=
  p.2 < p.1 ∧ 0 < p.2 ∧ Nat.Coprime p.1 p.2 ∧ (p.1 + p.2) % 2 = 1

/-- Berggren move `L` in seed coordinates (matrix `A₁`). -/
def mvL (p : ℕ × ℕ) : ℕ × ℕ := (2 * p.1 - p.2, p.1)

/-- Berggren move `M` in seed coordinates (matrix `A₂`), the Pell/silver branch. -/
def mvM (p : ℕ × ℕ) : ℕ × ℕ := (2 * p.1 + p.2, p.1)

/-- Berggren move `R` in seed coordinates (matrix `A₃ = B₃`). -/
def mvR (p : ℕ × ℕ) : ℕ × ℕ := (p.1 + 2 * p.2, p.2)

/-- The three Berggren moves indexed by `Fin 3`. -/
def step (i : Fin 3) (p : ℕ × ℕ) : ℕ × ℕ :=
  match i with
  | 0 => mvL p
  | 1 => mvM p
  | _ => mvR p

/-- The node of the Berggren tree reached by the word `w` (read right to left),
in Euclid-seed coordinates.  The root is the seed `(2,1)` of the triple `(3,4,5)`. -/
def seed : List (Fin 3) → ℕ × ℕ
  | [] => (2, 1)
  | i :: w => step i (seed w)

/-- The hypotenuse `c(w) = m² + n²` of the node `w`. -/
@[simp] theorem seed_cons (i : Fin 3) (w : List (Fin 3)) :
    seed (i :: w) = step i (seed w) := rfl

def hyp (w : List (Fin 3)) : ℕ := (seed w).1 ^ 2 + (seed w).2 ^ 2

/-- The even leg `2mn` of the node `w`. -/
def legEven (w : List (Fin 3)) : ℕ := 2 * (seed w).1 * (seed w).2

/-- The odd leg `m² - n²` of the node `w`. -/
def legOdd (w : List (Fin 3)) : ℕ := (seed w).1 ^ 2 - (seed w).2 ^ 2



/-! ## Part B. The seed condition is preserved by the moves -/

theorem coprime_mvL {m n : ℕ} (h : Nat.Coprime m n) (hnm : n < m) :
    Nat.Coprime (2 * m - n) m := by
  have hd : Nat.gcd (2 * m - n) m ∣ n := by
    have h1 : Nat.gcd (2 * m - n) m ∣ 2 * m - n := Nat.gcd_dvd_left _ _
    have h2 : Nat.gcd (2 * m - n) m ∣ 2 * m := Dvd.dvd.mul_left (Nat.gcd_dvd_right _ _) 2
    have := Nat.dvd_sub h2 h1
    rwa [show 2 * m - (2 * m - n) = n by omega] at this
  have hdm : Nat.gcd (2 * m - n) m ∣ m := Nat.gcd_dvd_right _ _
  have : Nat.gcd (2 * m - n) m ∣ Nat.gcd m n := Nat.dvd_gcd hdm hd
  rw [h] at this
  exact Nat.eq_one_of_dvd_one this

theorem coprime_mvM {m n : ℕ} (h : Nat.Coprime m n) :
    Nat.Coprime (2 * m + n) m := by
  have hd : Nat.gcd (2 * m + n) m ∣ n := by
    have h1 : Nat.gcd (2 * m + n) m ∣ 2 * m + n := Nat.gcd_dvd_left _ _
    have h2 : Nat.gcd (2 * m + n) m ∣ 2 * m := Dvd.dvd.mul_left (Nat.gcd_dvd_right _ _) 2
    have := Nat.dvd_sub h1 h2
    rwa [show 2 * m + n - 2 * m = n by omega] at this
  have hdm : Nat.gcd (2 * m + n) m ∣ m := Nat.gcd_dvd_right _ _
  have : Nat.gcd (2 * m + n) m ∣ Nat.gcd m n := Nat.dvd_gcd hdm hd
  rw [h] at this
  exact Nat.eq_one_of_dvd_one this

theorem coprime_mvR {m n : ℕ} (h : Nat.Coprime m n) :
    Nat.Coprime (m + 2 * n) n := by
  have hd : Nat.gcd (m + 2 * n) n ∣ m := by
    have h1 : Nat.gcd (m + 2 * n) n ∣ m + 2 * n := Nat.gcd_dvd_left _ _
    have h2 : Nat.gcd (m + 2 * n) n ∣ 2 * n := Dvd.dvd.mul_left (Nat.gcd_dvd_right _ _) 2
    have := Nat.dvd_sub h1 h2
    rwa [show m + 2 * n - 2 * n = m by omega] at this
  have hdn : Nat.gcd (m + 2 * n) n ∣ n := Nat.gcd_dvd_right _ _
  have : Nat.gcd (m + 2 * n) n ∣ Nat.gcd m n := Nat.dvd_gcd hd hdn
  rw [h] at this
  exact Nat.eq_one_of_dvd_one this

theorem isSeed_mvL {p : ℕ × ℕ} (hp : IsSeed p) : IsSeed (mvL p) := by
  obtain ⟨h1, h2, h3, h4⟩ := hp
  refine ⟨?_, ?_, coprime_mvL h3 h1, ?_⟩ <;> simp only [mvL] <;> omega

theorem isSeed_mvM {p : ℕ × ℕ} (hp : IsSeed p) : IsSeed (mvM p) := by
  obtain ⟨h1, h2, h3, h4⟩ := hp
  refine ⟨?_, ?_, coprime_mvM h3, ?_⟩ <;> simp only [mvM] <;> omega

theorem isSeed_mvR {p : ℕ × ℕ} (hp : IsSeed p) : IsSeed (mvR p) := by
  obtain ⟨h1, h2, h3, h4⟩ := hp
  refine ⟨?_, ?_, coprime_mvR h3, ?_⟩ <;> simp only [mvR] <;> omega

theorem isSeed_step (i : Fin 3) {p : ℕ × ℕ} (hp : IsSeed p) : IsSeed (step i p) := by
  fin_cases i
  · exact isSeed_mvL hp
  · exact isSeed_mvM hp
  · exact isSeed_mvR hp

/-- **Every node of the Berggren tree is an admissible Euclid seed.** -/
theorem seed_isSeed (w : List (Fin 3)) : IsSeed (seed w) := by
  induction w with
  | nil =>
    have h21 : seed [] = (2, 1) := rfl
    simp only [h21]
    exact ⟨by norm_num, by norm_num, by decide, by norm_num⟩
  | cons i w ih => exact isSeed_step i ih

/-! ## Part C. Completeness: every admissible seed occurs in the tree -/

/-- A seed is *reachable* if it is the node of some word. -/
def Reachable (p : ℕ × ℕ) : Prop := ∃ w : List (Fin 3), seed w = p

theorem reachable_root : Reachable (2, 1) := ⟨[], rfl⟩

theorem Reachable.mvL {p : ℕ × ℕ} (h : Reachable p) : Reachable (mvL p) := by
  obtain ⟨w, rfl⟩ := h; exact ⟨0 :: w, rfl⟩

theorem Reachable.mvM {p : ℕ × ℕ} (h : Reachable p) : Reachable (mvM p) := by
  obtain ⟨w, rfl⟩ := h; exact ⟨1 :: w, rfl⟩

theorem Reachable.mvR {p : ℕ × ℕ} (h : Reachable p) : Reachable (mvR p) := by
  obtain ⟨w, rfl⟩ := h; exact ⟨2 :: w, rfl⟩

/-- **Berggren completeness.**  Every admissible Euclid seed is a node of the tree. -/
theorem isSeed_reachable : ∀ p : ℕ × ℕ, IsSeed p → Reachable p := by
  intro p
  obtain ⟨m, n⟩ := p
  induction m using Nat.strong_induction_on generalizing n with
  | _ m ih =>
    intro hp
    obtain ⟨h1, h2, h3, h4⟩ := hp
    simp only at h1 h2 h3 h4
    by_cases hroot : m = 2 * n
    · -- `m = 2n`: coprimality forces the root
      have hn : n = 1 := by
        have : n ∣ Nat.gcd m n := Nat.dvd_gcd ⟨2, by omega⟩ dvd_rfl
        rw [h3] at this; exact Nat.eq_one_of_dvd_one this
      have hm2 : m = 2 := by omega
      subst hn; subst hm2; exact reachable_root
    rcases lt_trichotomy m (2 * n) with hlt | heq | hgt
    · -- parent `(n, 2n - m)` via move `L`
      have hpar : IsSeed (n, 2 * n - m) := by
        refine ⟨show 2 * n - m < n by omega, show 0 < 2 * n - m by omega, ?_,
          show (n + (2 * n - m)) % 2 = 1 by omega⟩
        have hd : Nat.gcd n (2 * n - m) ∣ m := by
          have hA : Nat.gcd n (2 * n - m) ∣ 2 * n :=
            Dvd.dvd.mul_left (Nat.gcd_dvd_left _ _) 2
          have hB : Nat.gcd n (2 * n - m) ∣ 2 * n - m := Nat.gcd_dvd_right _ _
          have := Nat.dvd_sub hA hB
          rwa [show 2 * n - (2 * n - m) = m by omega] at this
        have : Nat.gcd n (2 * n - m) ∣ Nat.gcd m n :=
          Nat.dvd_gcd hd (Nat.gcd_dvd_left _ _)
        rw [h3] at this; exact Nat.eq_one_of_dvd_one this
      have := (ih n (by omega) _ hpar).mvL
      have heq2 : mvL (n, 2 * n - m) = (m, n) := by
        simp only [mvL]
        exact Prod.ext (by simp; omega) (by simp)
      rwa [heq2] at this
    · exact absurd heq hroot
    · rcases lt_trichotomy m (3 * n) with hlt3 | heq3 | hgt3
      · -- parent `(n, m - 2n)` via move `M`
        have hpar : IsSeed (n, m - 2 * n) := by
          refine ⟨show m - 2 * n < n by omega, show 0 < m - 2 * n by omega, ?_,
            show (n + (m - 2 * n)) % 2 = 1 by omega⟩
          have hd : Nat.gcd n (m - 2 * n) ∣ m := by
            have hA : Nat.gcd n (m - 2 * n) ∣ 2 * n :=
              Dvd.dvd.mul_left (Nat.gcd_dvd_left _ _) 2
            have hB : Nat.gcd n (m - 2 * n) ∣ m - 2 * n := Nat.gcd_dvd_right _ _
            have := dvd_add hA hB
            rwa [show 2 * n + (m - 2 * n) = m by omega] at this
          have : Nat.gcd n (m - 2 * n) ∣ Nat.gcd m n :=
            Nat.dvd_gcd hd (Nat.gcd_dvd_left _ _)
          rw [h3] at this; exact Nat.eq_one_of_dvd_one this
        have := (ih n (by omega) _ hpar).mvM
        have heq2 : mvM (n, m - 2 * n) = (m, n) := by
          simp only [mvM]
          exact Prod.ext (by simp; omega) (by simp)
        rwa [heq2] at this
      · -- `m = 3n` forces `n = 1`, `m = 3`, contradicting the parity condition
        exfalso
        have hn : n = 1 := by
          have : n ∣ Nat.gcd m n := Nat.dvd_gcd ⟨3, by omega⟩ dvd_rfl
          rw [h3] at this; exact Nat.eq_one_of_dvd_one this
        omega
      · -- parent `(m - 2n, n)` via move `R`
        have hpar : IsSeed (m - 2 * n, n) := by
          refine ⟨show n < m - 2 * n by omega, show 0 < n by omega, ?_,
            show (m - 2 * n + n) % 2 = 1 by omega⟩
          have hd : Nat.gcd (m - 2 * n) n ∣ m := by
            have hA : Nat.gcd (m - 2 * n) n ∣ 2 * n :=
              Dvd.dvd.mul_left (Nat.gcd_dvd_right _ _) 2
            have hB : Nat.gcd (m - 2 * n) n ∣ m - 2 * n := Nat.gcd_dvd_left _ _
            have := dvd_add hA hB
            rwa [show 2 * n + (m - 2 * n) = m by omega] at this
          have : Nat.gcd (m - 2 * n) n ∣ Nat.gcd m n :=
            Nat.dvd_gcd hd (Nat.gcd_dvd_right _ _)
          rw [h3] at this; exact Nat.eq_one_of_dvd_one this
        have := (ih (m - 2 * n) (by omega) _ hpar).mvR
        have heq2 : mvR (m - 2 * n, n) = (m, n) := by
          simp only [mvR]
          exact Prod.ext (by simp; omega) (by simp)
        rwa [heq2] at this

/-! ## Part D. Uniqueness: the word is determined by the node -/

theorem mvL_window {p : ℕ × ℕ} (hp : IsSeed p) :
    (mvL p).2 < (mvL p).1 ∧ (mvL p).1 < 2 * (mvL p).2 := by
  obtain ⟨h1, h2, _, _⟩ := hp; constructor <;> (simp [mvL]; omega)

theorem mvM_window {p : ℕ × ℕ} (hp : IsSeed p) :
    2 * (mvM p).2 < (mvM p).1 ∧ (mvM p).1 < 3 * (mvM p).2 := by
  obtain ⟨h1, h2, _, _⟩ := hp; constructor <;> (simp [mvM]; omega)

theorem mvR_window {p : ℕ × ℕ} (hp : IsSeed p) :
    3 * (mvR p).2 < (mvR p).1 := by
  obtain ⟨h1, h2, _, _⟩ := hp; simp [mvR]; omega

theorem mvL_inj {p q : ℕ × ℕ} (hp : IsSeed p) (hq : IsSeed q) (h : mvL p = mvL q) : p = q := by
  obtain ⟨h1, h2, _, _⟩ := hp
  obtain ⟨g1, g2, _, _⟩ := hq
  have h' := congrArg Prod.fst h
  have h'' := congrArg Prod.snd h
  simp [mvL] at h' h''
  exact Prod.ext (by omega) (by omega)

theorem mvM_inj {p q : ℕ × ℕ} (h : mvM p = mvM q) : p = q := by
  have h' := congrArg Prod.fst h
  have h'' := congrArg Prod.snd h
  simp [mvM] at h' h''
  exact Prod.ext (by omega) (by omega)

theorem mvR_inj {p q : ℕ × ℕ} (h : mvR p = mvR q) : p = q := by
  have h' := congrArg Prod.fst h
  have h'' := congrArg Prod.snd h
  simp [mvR] at h' h''
  exact Prod.ext (by omega) (by omega)

/-- Nodes at positive depth are never the root: the root is the unique seed with `m = 2n`. -/
theorem step_ne_root (i : Fin 3) {p : ℕ × ℕ} (hp : IsSeed p) : step i p ≠ (2, 1) := by
  intro h
  fin_cases i
  · have hw := mvL_window hp
    rw [show mvL p = ((2 : ℕ), (1 : ℕ)) from h] at hw
    simp only at hw
    omega
  · have hw := mvM_window hp
    rw [show mvM p = ((2 : ℕ), (1 : ℕ)) from h] at hw
    simp only at hw
    omega
  · have hw := mvR_window hp
    rw [show mvR p = ((2 : ℕ), (1 : ℕ)) from h] at hw
    simp only at hw
    omega

theorem step_inj_index {i j : Fin 3} {p q : ℕ × ℕ} (hp : IsSeed p) (hq : IsSeed q)
    (h : step i p = step j q) : i = j := by
  fin_cases i <;> fin_cases j <;> first
    | rfl
    | (exfalso
       first
       | (have h1 := mvL_window hp; have h2 := mvM_window hq;
          simp only [step] at h; rw [h] at h1; omega)
       | (have h1 := mvL_window hp; have h2 := mvR_window hq;
          simp only [step] at h; rw [h] at h1; omega)
       | (have h1 := mvM_window hp; have h2 := mvL_window hq;
          simp only [step] at h; rw [h] at h1; omega)
       | (have h1 := mvM_window hp; have h2 := mvR_window hq;
          simp only [step] at h; rw [h] at h1; omega)
       | (have h1 := mvR_window hp; have h2 := mvL_window hq;
          simp only [step] at h; rw [h] at h1; omega)
       | (have h1 := mvR_window hp; have h2 := mvM_window hq;
          simp only [step] at h; rw [h] at h1; omega))

/-- **Uniqueness of the Berggren word.**  The map `w ↦ seed w` is injective. -/
theorem seed_injective : Function.Injective seed := by
  intro w₁
  induction w₁ with
  | nil =>
    intro w₂ h
    cases w₂ with
    | nil => rfl
    | cons j w =>
      exact absurd h.symm (step_ne_root j (seed_isSeed w))
  | cons i w ih =>
    intro w₂ h
    cases w₂ with
    | nil => exact absurd h (step_ne_root i (seed_isSeed w))
    | cons j w' =>
      have hij : i = j := step_inj_index (seed_isSeed w) (seed_isSeed w') h
      subst hij
      simp only [seed_cons] at h
      have : seed w = seed w' := by
        fin_cases i
        · exact mvL_inj (seed_isSeed w) (seed_isSeed w') h
        · exact mvM_inj h
        · exact mvR_inj h
      rw [ih this]

/-- **The Berggren tree is exactly the set of Euclid seeds.** -/
theorem seed_bijective_onto_seeds :
    Function.Bijective (fun w : List (Fin 3) => (⟨seed w, seed_isSeed w⟩ : {p // IsSeed p})) := by
  constructor
  · intro w₁ w₂ h
    exact seed_injective (congrArg Subtype.val h)
  · rintro ⟨p, hp⟩
    obtain ⟨w, hw⟩ := isSeed_reachable p hp
    exact ⟨w, by simp [hw]⟩

/-- The bijection between Berggren words and Euclid seeds. -/
noncomputable def seedEquiv : List (Fin 3) ≃ {p : ℕ × ℕ // IsSeed p} :=
  Equiv.ofBijective _ seed_bijective_onto_seeds


/-! ## Part E. The Pythagorean triple at a node, and the Berggren matrices -/



/-- The integer triple `(a, b, c)` at the node `w`. -/
def triple (w : List (Fin 3)) : ℤ × ℤ × ℤ :=
  (((seed w).1 : ℤ) ^ 2 - ((seed w).2 : ℤ) ^ 2, 2 * (seed w).1 * (seed w).2,
    ((seed w).1 : ℤ) ^ 2 + ((seed w).2 : ℤ) ^ 2)




end BerggrenZeta

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me