Aether Catalog definitions — Bridges_NeuralCoding_TropicalSpectralConcentration
DefinitionBridges_NeuralCoding_TropicalSpectralConcentrationaether-catalogbridges
Definition bundle for the Aether Catalog module Bridges.NeuralCoding.TropicalSpectralConcentration, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.
Definition code
-- Def bundle generated from Bridges/NeuralCoding/TropicalSpectralConcentration.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.
# Tropical Spectral Concentration Theory
This file develops the theory of **tropical spectral concentration**: how the
cycle-birth distribution of a weighted graph filtration concentrates, and how
it connects to classical graph invariants.
## Main Definitions
* `TropicalSpectrum` — ordered list of cycle-birth weights (tropical eigenvalues)
* `tropicalCycleRank` — cycle rank from filtration data
* `mcDiarmidRadius` — concentration radius from bounded differences
## Main Results
1. Euler–Poincaré decomposition (edges = merges + cycles)
2. Universality under weight transport
3. Rank–Nullity bridge to algebraic graph theory
4. Bounded differences for concentration
5. Cumulative monotonicity of cycle-birth CDF
6. Cross-domain bridge: tropical topology ↔ matrix algebra
7. Falsifiable spectral gap conjecture
-/
open Finset BigOperators
/-! ## Part 1: Tropical Spectrum — A Novel Mathematical Structure -/
/-- A filtration step recording an edge insertion with weight and connectivity status. -/
structure TFiltStep where
weight : ℚ
isCycleBirth : Bool
deriving DecidableEq, Inhabited
/-- A tropical weighted filtration: vertex count + ordered edge insertions. -/
structure TropicalFiltration where
numVerts : ℕ
steps : List TFiltStep
numVerts_pos : 0 < numVerts := by omega
namespace TropicalFiltration
/-- Count of cycle-birth events. -/
def cycleCount (F : TropicalFiltration) : ℕ :=
F.steps.countP (·.isCycleBirth)
/-- Count of merge events. -/
def mergeCount (F : TropicalFiltration) : ℕ :=
F.steps.countP (fun s => !s.isCycleBirth)
/-- Total number of edges. -/
def edgeCount (F : TropicalFiltration) : ℕ :=
F.steps.length
/-- The **tropical spectrum**: weights at which cycle births occur.
This is our novel mathematical structure — the tropical analogue
of the eigenvalue spectrum. -/
def tropicalSpectrum (F : TropicalFiltration) : List ℚ :=
(F.steps.filter (·.isCycleBirth)).map (·.weight)
/-- Cumulative cycle-birth count at threshold t. -/
def cycleBirthCountLE (F : TropicalFiltration) (t : ℚ) : ℕ :=
F.steps.countP (fun s => s.isCycleBirth && decide (s.weight ≤ t))
/-- Apply a function to all weights, preserving classification. -/
def mapWeights (F : TropicalFiltration) (φ : ℚ → ℚ) : TropicalFiltration where
numVerts := F.numVerts
steps := F.steps.map (fun s => ⟨φ s.weight, s.isCycleBirth⟩)
numVerts_pos := F.numVerts_pos
/-- Extract the Boolean classification flags. -/
def flags (F : TropicalFiltration) : List Bool :=
F.steps.map (·.isCycleBirth)
end TropicalFiltration
/-! ## Part 2: Euler–Poincaré Identity -/
/-! ## Part 3: Universality under Weight Transport -/
/-! ## Part 4: Rank–Nullity Bridge -/
/-- The **tropical cycle rank**: number of independent cycles. -/
def tropicalCycleRank (F : TropicalFiltration) : ℤ :=
(F.cycleCount : ℤ)
/-! ## Part 5: Bounded Differences via List Surgery
We prove that changing a single step's classification
changes the cycle count by at most 1. -/
/-
Replacing one element in a list changes countP by at most 1 (upper direction).
This uses List.set instead of List.modify for cleaner API.
-/
/-
**Theorem 4 (Bounded Differences).**
Changing a single step's isCycleBirth flag changes the cycle count
by at most 1. This is the key ingredient for McDiarmid concentration.
**Proof**: Use countP_set_le in both directions.
-/
/-! ## Part 6: Cumulative Monotonicity -/
/-
**Theorem 5 (Cumulative Monotonicity).**
The cycle-birth counting function is monotone: s ≤ t → count(s) ≤ count(t).
-/
/-
The cycle-birth count is bounded by the total cycle count.
-/
/-! ## Part 7: Cross-Domain Bridge — Tropical ↔ Matrix Algebra -/
/-- A simple graph adjacency matrix over ℚ. -/
def AdjMatrix (n : ℕ) := Matrix (Fin n) (Fin n) ℚ
/-- The degree of vertex i. -/
def adjDegree {n : ℕ} (A : AdjMatrix n) (i : Fin n) : ℚ :=
∑ j : Fin n, A i j
/-- The degree sum. -/
def degreeSum {n : ℕ} (A : AdjMatrix n) : ℚ :=
∑ i : Fin n, adjDegree A i
/-- The trace of a square matrix. -/
def matTrace {n : ℕ} (A : AdjMatrix n) : ℚ :=
∑ i : Fin n, A i i
/-- A simple graph has zero diagonal and symmetric entries. -/
def isSimpleAdj {n : ℕ} (A : AdjMatrix n) : Prop :=
(∀ i, A i i = 0) ∧ (∀ i j, A i j = A j i)
/-! ## Part 8: Telescoping and Transport Composition -/
/-! ## Part 9: Concatenation and Additivity -/
/-- Concatenation of filtrations (same vertex set). -/
def concatFilt (F G : TropicalFiltration) (_h : F.numVerts = G.numVerts) :
TropicalFiltration where
numVerts := F.numVerts
steps := F.steps ++ G.steps
numVerts_pos := F.numVerts_pos
/-! ## Part 10: Inductive Characterization -/
/-- A single-step filtration. -/
def singleStep (n : ℕ) (hn : 0 < n) (s : TFiltStep) : TropicalFiltration where
numVerts := n
steps := [s]
numVerts_pos := hn
/-! ## Part 11: Range Bound via Bounded Differences -/
/-
**Theorem 12 (Deterministic Range Bound).**
If f has bounded differences with constant c on m Boolean variables,
then the range of f has diameter at most m·c.
**Proof**: By induction on m, modifying one coordinate at a time
along a path from x to y.
-/
/-! ## Part 12: McDiarmid Concentration Radius -/
/-- The McDiarmid concentration radius. -/
noncomputable def mcDiarmidRadius (m : ℕ) (α : ℝ) : ℝ :=
Real.sqrt ((m : ℝ) * Real.log (2 / α) / 2)
/-
For valid confidence levels, the squared radius recovers the argument.
-/
/-! ## Part 13: Worked Examples -/
/-! ## Part 14: Falsifiable Conjecture -/