Aether Catalog definitions — Bridges_BerggrenLatticeReductionDuality
DefinitionBridges_BerggrenLatticeReductionDualityaether-catalogbridges
Definition bundle for the Aether Catalog module Bridges.BerggrenLatticeReductionDuality, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.
Definition code
-- Def bundle generated from Bridges/BerggrenLatticeReductionDuality.lean by skeleton subtraction
import Mathlib
/-!
# Berggren Lattice-Reduction Duality via Triple-Tree Gram Semimodules
This module establishes a structural duality between:
- **Berggren triple trees**: finite-state objects generated by the three Berggren matrices
acting on primitive Pythagorean triples, and
- **Pythagorean Gram lattice presentations**: integer lattice presentations whose Gram data
factors through primitive Pythagorean triples.
## Main results
- `realization_of_admissible_pythagorean_gram_lattice`: every admissible Pythagorean Gram
lattice presentation is realized by a finite Berggren Gram semimodule.
- `exists_reduced_realization`: each realization admits a reduced representative
(Myhill–Nerode style quotient by Gram-behavior equivalence).
- `reduced_realization_unique_up_to_certified_iso`: reduced realizations with equivalent
presentations are isomorphic.
- `certified_reconstruction`: from any lattice presentation one can reconstruct
a certified basis witness with a verified optimality bound.
## Mathematical context
The Berggren tree enumerates all primitive Pythagorean triples starting from (3,4,5) via
three unimodular integer matrices. Each triple (a,b,c) with a²+b²=c² naturally produces
a 2×2 Gram matrix [[a², ab],[ab, b²]]. The key insight is that the Berggren dynamics on
triples induces a well-defined dynamics on Gram profiles, turning the tree into a
reduction calculus for a class of lattice problems.
The duality theorem shows that finite-state semimodule objects over Berggren transitions
precisely classify a natural class of integer lattice presentations, with the minimal
(reduced) semimodule serving as a canonical compressed certificate from which shortest-basis
data can be algorithmically reconstructed.
-/
open Matrix Finset
noncomputable section
/-! ## Section 1: Primitive Pythagorean Triples -/
/-! ## Section 2: Berggren Matrices -/
/-! ## Section 3: Gram Matrices from Pythagorean Triples -/
/-! ## Section 4: Gram Length Spectrum -/
/-! ## Section 5: Triple-Tree Gram Semimodule -/
/-- A triple-tree Gram semimodule: a carrier of states together with a Gram-matrix
assignment on those states (the skeleton-stripped original carried the Berggren
triple-tree carrier and the 2x2 Gram trace map). -/
structure TripleTreeGramSemimodule where
Carrier : Type
gram : Carrier → Matrix (Fin 2) (Fin 2) ℤ
/-- A Pythagorean Gram lattice presentation: rank `n` with Gram data per basis index. -/
structure PythagoreanGramLatticePresentation where
n : ℕ
gram : Fin n → Fin n → ℤ
/-! ## Section 6: Pythagorean Gram Lattice Presentation -/
/-! ## Section 7: Realization -/
/-- A semimodule S realizes a lattice presentation L if there is a surjective map from
basis indices to semimodule states matching Gram traces to diagonal entries. -/
def Realizes (S : TripleTreeGramSemimodule) (L : PythagoreanGramLatticePresentation) : Prop :=
∃ φ : Fin L.n → S.Carrier,
(∀ i, (S.gram (φ i)).trace = L.gram i i) ∧
Function.Surjective φ
/-! ## Section 8: Certified Isomorphism and Witnesses -/
/-! ## Section 9: Main Theorems -/
/-! ### Theorem A: Realization -/
/-! ### Theorem B: Reduced realization -/
/-
**Reduced realization**: Every Pythagorean Gram lattice presentation
has a reduced realization.
-/
/-! ### Uniqueness of reduced realizations -/
/-
**Reduced extensionality**: Two reduced semimodules with equivalent root-behavior
and all-reachable states are isomorphic.
-/
/-! ### Theorem C: Certified reconstruction -/
/-! ## Section 10: Supporting Lemmas -/
/-- A primitive Pythagorean triple: positive integers with a² + b² = c²,
gcd(a,b) = 1, and opposite parity. -/
structure PrimitivePythTriple where
a : ℕ
b : ℕ
c : ℕ
pos_a : 0 < a
pos_b : 0 < b
pos_c : 0 < c
pyth : a * a + b * b = c * c
coprime : Nat.gcd a b = 1
parity : a % 2 = 1 ∧ b % 2 = 0
/-- The base triple (3, 4, 5) is a primitive Pythagorean triple. -/
def baseTriple : PrimitivePythTriple where
a := 3; b := 4; c := 5
pos_a := by omega
pos_b := by omega
pos_c := by omega
pyth := by norm_num
coprime := by decide
parity := by omega
/-
CertifiedIso is symmetric.
-/
/-
CertifiedIso is transitive.
-/
end