Aether Catalog definitions — Bridges_GraphTheory_ModularCFDynamics
DefinitionBridges_GraphTheory_ModularCFDynamicsaether-catalogbridges
Definition bundle for the Aether Catalog module Bridges.GraphTheory.ModularCFDynamics, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.
Definition code
-- Def bundle generated from Bridges/GraphTheory/ModularCFDynamics.lean by skeleton subtraction
import Mathlib
/-
Copyright (c) 2025 Harmonic. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
-/
/-!
# Modular Continued-Fraction Dynamics and Periodicity Detection
## Overview
This file develops a theory connecting continued-fraction expansions to modular
dynamics, establishing that eventually periodic CF sequences produce eventually
periodic convergent sequences modulo any modulus, and that graph-theoretic
invariants built from these modular convergents inherit the periodicity.
## Main Definitions
- `CFState`: State of the CF convergent recurrence (p_{n-1}, p_n, q_{n-1}, q_n)
- `IsEventuallyPeriodic`: A sequence that becomes periodic after some index
- `ModularCFGraph`: Novel structure encoding the filtered graph built from
convergents mod p
- `FilteredGraphSeq`: Sequence of graphs with periodicity properties
## Main Results
- `eventually_periodic_comp`: Composition preserves eventual periodicity
- `consecutive_pair_periodic`: Periodicity transfers through pair functions
- `transition_count_eventually_periodic`: Graph edge counts inherit periodicity
- `modular_cf_graph_vertex_bound`: Bounded vertex count for modular CF graphs
- `betti_periodic_of_edge_periodic`: Cross-domain bridge to topology
- `finite_state_orbit_periodic`: Pigeonhole-based orbit periodicity on finite types
-/
open Finset Function
namespace ModularCFDynamics
/-! ## §1. Eventually Periodic Sequences -/
/-- A sequence `f : ℕ → α` is **eventually periodic** with preperiod `N` and period `T`
if `T > 0` and for all `n ≥ N`, `f(n + T) = f(n)`. -/
def IsEventuallyPeriodic {α : Type*} (f : ℕ → α) (N T : ℕ) : Prop :=
0 < T ∧ ∀ n, N ≤ n → f (n + T) = f n
/-- A purely periodic sequence is eventually periodic with preperiod 0. -/
def IsPurelyPeriodic {α : Type*} (f : ℕ → α) (T : ℕ) : Prop :=
IsEventuallyPeriodic f 0 T
/-! ## §2. Continued Fraction Convergent Recurrence -/
/-- The **CF convergent recurrence** state: tracks (p_{n-1}, p_n, q_{n-1}, q_n). -/
@[ext]
structure CFState (α : Type*) where
pPrev : α
pCurr : α
qPrev : α
qCurr : α
deriving DecidableEq
instance {α : Type*} [Fintype α] : Fintype (CFState α) :=
Fintype.ofEquiv (α × α × α × α) {
toFun := fun ⟨a, b, c, d⟩ => ⟨a, b, c, d⟩
invFun := fun s => ⟨s.pPrev, s.pCurr, s.qPrev, s.qCurr⟩
left_inv := fun ⟨_, _, _, _⟩ => rfl
right_inv := fun ⟨_, _, _, _⟩ => rfl
}
variable {α : Type*}
/-- Advance the CF state by one step given the next CF coefficient `a`. -/
def CFState.step [Add α] [Mul α] (s : CFState α) (a : α) : CFState α where
pPrev := s.pCurr
pCurr := a * s.pCurr + s.pPrev
qPrev := s.qCurr
qCurr := a * s.qCurr + s.qPrev
/-- Initial CF state. -/
def CFState.init [Zero α] [One α] [Add α] [Mul α] (a₀ : α) : CFState α where
pPrev := 1
pCurr := a₀
qPrev := 0
qCurr := 1
/-- Iterate the CF recurrence for `n` steps starting from initial state. -/
def cfIterate [Add α] [Mul α] [Zero α] [One α] (coeffs : ℕ → α) : ℕ → CFState α
| 0 => CFState.init (coeffs 0)
| n + 1 => (cfIterate coeffs n).step (coeffs (n + 1))
/-! ## §3. Modular CF Dynamics -/
/-- The CF state modulo m, working in `ZMod m`. -/
abbrev ModCFState (m : ℕ) := CFState (ZMod m)
/-- The modular CF iteration. -/
def modCFIterate (m : ℕ) (coeffs : ℕ → ZMod m) : ℕ → ModCFState m :=
cfIterate coeffs
/-! ## §4. Modular CF Graph (Novel Structure) -/
/-- A **Modular CF Graph** encodes the transition graph of convergent pairs modulo p.
Vertices are elements of (ZMod p)², edges connect consecutive pairs. -/
structure ModularCFGraph (p : ℕ) where
windowSize : ℕ
vertices : Finset (ZMod p × ZMod p)
edges : Finset ((ZMod p × ZMod p) × (ZMod p × ZMod p))
edge_src_mem : ∀ e ∈ edges, e.1 ∈ vertices
edge_tgt_mem : ∀ e ∈ edges, e.2 ∈ vertices
/-- Build the modular CF graph from the first N convergents. -/
noncomputable def buildModularCFGraph (p : ℕ) [NeZero p]
(coeffs : ℕ → ZMod p) (N : ℕ) : ModularCFGraph p where
windowSize := N
vertices :=
(Finset.range N).image (fun n =>
let s := modCFIterate p coeffs n
(s.pCurr, s.qCurr))
edges :=
((Finset.range N).filter (· + 1 < N)).image (fun n =>
let s₁ := modCFIterate p coeffs n
let s₂ := modCFIterate p coeffs (n + 1)
((s₁.pCurr, s₁.qCurr), (s₂.pCurr, s₂.qCurr)))
edge_src_mem := by
intro e he
simp only [Finset.mem_image, Finset.mem_filter, Finset.mem_range] at he ⊢
obtain ⟨n, ⟨hn, _⟩, rfl⟩ := he
exact ⟨n, hn, rfl⟩
edge_tgt_mem := by
intro e he
simp only [Finset.mem_image, Finset.mem_filter, Finset.mem_range] at he ⊢
obtain ⟨n, ⟨_, hn2⟩, rfl⟩ := he
exact ⟨n + 1, hn2, rfl⟩
/-! ## §5. Periodicity Transfer Theorems -/
/-! ## §6. Pigeonhole-Based Finite Orbit Periodicity -/
/-
**Finite state orbit periodicity**: On a finite type, iterating any function
produces an eventually periodic sequence.
Proof by pigeonhole: among the first `card α + 1` iterates, two must be equal.
This gives the cycle detection that powers the modular CF periodicity theorem.
-/
/-! ## §7. Cross-Domain Bridge: Graph Invariants → Barcode Periodicity -/
/-- A **filtered graph sequence** assigns to each natural number a graph. -/
structure FilteredGraphSeq (V : Type*) where
edges : ℕ → Finset (V × V)
/-- Eventually periodic edge sets. -/
def FilteredGraphSeq.IsEventuallyPeriodicEdges {V : Type*}
(G : FilteredGraphSeq V) (N T : ℕ) : Prop :=
0 < T ∧ ∀ n, N ≤ n → G.edges (n + T) = G.edges n
/-- A **Betti number function** extracts a topological invariant from a graph. -/
def BettiFunction (V : Type*) [DecidableEq V] [Fintype V] :=
Finset (V × V) → ℕ
/-! ## §8. Concrete Examples -/
/-- The golden ratio φ = [1; 1, 1, 1, ...] has purely periodic CF. -/
def goldenRatioCF : ℕ → ℕ := fun _ => 1
/-- √2 = [1; 2, 2, 2, ...] has eventually periodic CF. -/
def sqrt2CF : ℕ → ℕ
| 0 => 1
| _ + 1 => 2
/-! ## §9. Full Pipeline Theorem -/
/-! ## §10. Falsifiable Conjecture -/
end ModularCFDynamics