Aether Catalog definitions — Bridges_BerggrenChronometricAutomata
DefinitionBridges_BerggrenChronometricAutomataaether-catalogbridges
Definition bundle for the Aether Catalog module Bridges.BerggrenChronometricAutomata, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.
Definition code
-- Def bundle generated from Bridges/BerggrenChronometricAutomata.lean by skeleton subtraction
import Mathlib
/-!
# Berggren–Chronometric Reversible Automata via Primitive Triple Orbit Groupoids
# and Causal Entropy Separation
A formal theory connecting the Berggren tree of primitive Pythagorean triples to
reversible computation, automata minimization, causal entropy monotonicity, and
post-quantum security proxies.
## Main Results
* `reverseInv_involutive` — time-reversal is an involution on Berggren word space
* `chronometricLength_append` — chronometric length is additive under concatenation
* `causalCongruence_is_equiv` — causal congruence is an equivalence relation
* `reversible_automaton_factors_through_history_groupoid` — Myhill–Nerode factoring
* `myhill_nerode_chronometric_minimality` — injective embedding of causal quotient
* `entropy_monotone_nonbacktracking` — entropy proxy is monotone in horizon
* `time_reversal_invariant_capacity_le` — capacity bounded by 3^n
* `strict_separation_of_irreversible_quotients` — causal vs irreversible separation
## Cross-Domain Significance
Bridge: connects number theory (Pythagorean triples), automata theory (Myhill–Nerode),
reversible computation (Landauer's principle), entropy monotonicity (thermodynamics),
and post-quantum security (lattice trapdoor cost proxies).
-/
set_option maxHeartbeats 800000
-- ════════════════════════════════════════════════════════════════════════════════
-- § 1. Berggren Alphabet and Word Combinatorics
-- ════════════════════════════════════════════════════════════════════════════════
/-- The Berggren alphabet: the three Berggren tree generator steps
encoding a path in the ternary Berggren tree of primitive Pythagorean triples. -/
inductive BerggrenStep where
| A | B | C
/-- A word in the Berggren alphabet, encoding a path in the ternary Berggren tree
of primitive Pythagorean triples.
Bridge: words are programs in the reversible Pythagorean orbit automaton. -/
abbrev BerggrenWord := List BerggrenStep
namespace BerggrenStep
instance : Inhabited BerggrenStep := ⟨.A⟩
end BerggrenStep
-- ════════════════════════════════════════════════════════════════════════════════
-- § 2. Word Operations and Time Reversal
-- ════════════════════════════════════════════════════════════════════════════════
namespace BerggrenWord
/-
Bridge: time-reversal is an involution on word space, fundamental for
reversible computation and thermodynamic reversibility.
Connects to quantum_control_history_reversal symmetry.
-/
end BerggrenWord
-- ════════════════════════════════════════════════════════════════════════════════
-- § 3. Chronometric Length and Depth
-- ════════════════════════════════════════════════════════════════════════════════
/-
Chronometric length is invariant under time reversal.
Bridge: connects thermodynamic reversibility (time-reversal symmetry)
to cost invariance in reversible computation.
-/
-- ════════════════════════════════════════════════════════════════════════════════
-- § 4. Primitive Pythagorean Triples
-- ════════════════════════════════════════════════════════════════════════════════
/-- A primitive Pythagorean triple (a, b, c) with a² + b² = c² and gcd(a,b) = 1.
Bridge: the arithmetic substrate connecting number theory to computational dynamics
and post_quantum_security via lattice structure. -/
structure PrimitiveTriple where
a : ℤ
b : ℤ
c : ℤ
pos_a : 0 < a
pos_b : 0 < b
pos_c : 0 < c
pythagorean : a * a + b * b = c * c
coprime_ab : Int.gcd a b = 1
-- ════════════════════════════════════════════════════════════════════════════════
-- § 5. Orbit Morphisms and History Groupoid
-- ════════════════════════════════════════════════════════════════════════════════
namespace OrbitMorphism
/-
Bridge: time-reversal is an involution on orbit morphisms, connecting
reversible computation to quantum_control_history_reversal symmetry.
Every computation can be undone and re-undone to recover the original.
-/
end OrbitMorphism
-- ════════════════════════════════════════════════════════════════════════════════
-- § 6. Causal Congruence (Myhill–Nerode Style)
-- ════════════════════════════════════════════════════════════════════════════════
section CausalCongruenceTheory
variable {α : Type*} (eval : BerggrenWord → α)
end CausalCongruenceTheory
-- ════════════════════════════════════════════════════════════════════════════════
-- § 7. Reversible Orbit Automaton
-- ════════════════════════════════════════════════════════════════════════════════
namespace ReversibleOrbitAutomaton
end ReversibleOrbitAutomaton
/-
Bridge: Myhill–Nerode minimality — if an automaton separates all
non-congruent words, the quotient injects into its state space.
Application: lower bound on state complexity for reversible arithmetic automata.
-/
-- ════════════════════════════════════════════════════════════════════════════════
-- § 8. Entropy Proxies and Capacity Bounds
-- ════════════════════════════════════════════════════════════════════════════════
/-
Non-backtracking count is bounded by total branching.
-/
/-
The entropy rate proxy is bounded by 3^n.
Bridge: explicit computational bound for post_quantum_security.
-/
-- ════════════════════════════════════════════════════════════════════════════════
-- § 9. Strict Separation of Irreversible Quotients
-- ════════════════════════════════════════════════════════════════════════════════
/-
Bridge: strict separation of irreversible quotients — causal congruence
is strictly finer than irreversible quotient for the adjacentRepeatCount
observable. Reversible semantics genuinely distinguish histories that
irreversible state-collapse forgets.
Application: Landauer's principle and post_quantum_security separation.
The separation witnesses are [A,B] and [B,A]: both have 0 adjacent repeats,
but appending [A] gives 0 vs 1 repeats respectively.
-/
-- ════════════════════════════════════════════════════════════════════════════════
-- § 10. Additional Structures and Cross-Domain Definitions
-- ════════════════════════════════════════════════════════════════════════════════
-- ════════════════════════════════════════════════════════════════════════════════
-- § 11. Additional Theorems and Cross-Domain Results
-- ════════════════════════════════════════════════════════════════════════════════