Range bound from bounded diff
Provedrange_bound_from_bounded_diffaether-catalogbridges
Formal statement of range_bound_from_bounded_diff from the Aether Catalog (Bridges). The mathematical content is given by the Lean statement below; a human-readable write-up is pending.
theorem range_bound_from_bounded_diff(m : ℕ) (f : (Fin m → Bool) → ℤ)
(c : ℕ) (hbd : ∀ (x : Fin m → Bool) (i : Fin m) (b : Bool),
|f x - f (Function.update x i b)| ≤ c) :
∀ x y : Fin m → Bool, |f x - f y| ≤ m * c := by sorry
Formalization Note Transplanted verbatim from the Aether Catalog source Bridges/NeuralCoding/TropicalSpectralConcentration.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.
Preamble
-- Thm stub generated from Bridges/NeuralCoding/TropicalSpectralConcentration.lean
import Mathlib
import Definitions.Def_Bridges_NeuralCoding_TropicalSpectralConcentration
/-
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 -/
open TropicalFiltration
/-! ## Part 2: Euler–Poincaré Identity -/
/-! ## Part 3: Universality under Weight Transport -/
/-! ## Part 4: Rank–Nullity Bridge -/
/-! ## 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 -/
/-! ## Part 8: Telescoping and Transport Composition -/
/-! ## Part 9: Concatenation and Additivity -/
/-! ## Part 10: Inductive Characterization -/
/-! ## 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.
-/Formal statement
theorem range_bound_from_bounded_diff(m : ℕ) (f : (Fin m → Bool) → ℤ)
(c : ℕ) (hbd : ∀ (x : Fin m → Bool) (i : Fin m) (b : Bool),
|f x - f (Function.update x i b)| ≤ c) :
∀ x y : Fin m → Bool, |f x - f y| ≤ m * c := by sorrySource