Aether Catalog definitions — Bridges_OperadicTropicalization
DefinitionBridges_OperadicTropicalizationaether-catalogbridges
Definition bundle for the Aether Catalog module Bridges.OperadicTropicalization, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.
Definition code
-- Def bundle generated from Bridges/OperadicTropicalization.lean by skeleton subtraction
import Mathlib
/-!
# Operadic Tropicalization of Neural Architectures
This file establishes a formal bridge between **operad theory**, **tropical algebra**, and
**neural architecture classification**. The central result is a certified tropical
reconstruction theorem: bounded neural architectures admit complete tropical operadic
invariants that classify them up to structural congruence.
## Main Results
### Structures and Definitions
* `ArchExpr` — tree-structured operadic expressions (free operad elements)
* `TropicalArchProfile` — tropical complexity profile with depth, width, generator count
* `StructuralCongr` — structural congruence on architecture expressions
* `tropicalValuation` — the operadic tropical valuation functor
* `ArchitectureSkeleton` — canonical skeleton type for architecture reconstruction
* `reconstructSkeleton` — reconstruction of canonical skeleton from tropical profile
### Key Theorems
* `tropicalValuation_compose` — functoriality under sequential composition
* `tropicalValuation_parallel` — functoriality under parallel composition
* `seqMul_tropAdd_distrib_left` — tropical semiring distributivity
* `tropicalValuation_structural_congr` — invariance under structural congruence
* `depth_width_genCount_tradeoff` — depth × width ≥ generatorCount
* `certified_operadic_tropical_reconstruction` — the main reconstruction theorem
* `tropical_profile_complete_for_bounded_architecture_congruence` — completeness
## Bridge: connects operad theory (compositional syntax) → tropical algebra (min-plus) →
ML architecture theory (depth/width classification) → automata theory (Myhill–Nerode) →
certified compression (canonical minimization)
## References
- Loday, Vallette: "Algebraic Operads"
- Maclagan, Sturmfels: "Introduction to Tropical Geometry"
- Cohen, Gaubert, Quadrat: "Max-plus algebra and system theory"
-/
noncomputable section
namespace OperadicTropicalization
/-! ## Section 1: Architecture Expressions (Free Operad)
An `ArchExpr` is an element of the free operad on one generator, representing
a neural architecture built from:
- `generator`: a single computation module (layer, attention head, etc.)
- `identity`: the identity/pass-through operation
- `compose`: sequential composition (depth increases additively)
- `parallel`: parallel composition (width increases additively)
-/
/-- Architecture expression: element of the free operad on one generator.
Bridge: connects operadic composition theory to neural architecture design. -/
inductive ArchExpr where
| generator : ArchExpr
| identity : ArchExpr
| compose : ArchExpr → ArchExpr → ArchExpr
| parallel : ArchExpr → ArchExpr → ArchExpr
deriving DecidableEq
namespace ArchExpr
/-- Sequential depth: length of the longest sequential computation path.
Compose adds depths (sequential); parallel takes max (concurrent). -/
@[simp] def depth : ArchExpr → ℕ
| generator => 1
| identity => 0
| compose e₁ e₂ => e₁.depth + e₂.depth
| parallel e₁ e₂ => max e₁.depth e₂.depth
/-- Generator count: total number of computation modules.
Both compose and parallel sum counts (all generators are used). -/
@[simp] def generatorCount : ArchExpr → ℕ
| generator => 1
| identity => 0
| compose e₁ e₂ => e₁.generatorCount + e₂.generatorCount
| parallel e₁ e₂ => e₁.generatorCount + e₂.generatorCount
/-- Maximum width: the widest parallel cross-section.
Sequential composition takes max (pipeline bottleneck);
parallel composition sums widths (resources allocated side by side). -/
@[simp] def maxWidth : ArchExpr → ℕ
| generator => 1
| identity => 0
| compose e₁ e₂ => max e₁.maxWidth e₂.maxWidth
| parallel e₁ e₂ => e₁.maxWidth + e₂.maxWidth
/-- Canonical sequential chain of `k` generators: depth k, width 1, genCount k. -/
def kChain : ℕ → ArchExpr
| 0 => .identity
| k + 1 => .compose .generator (kChain k)
/-! ### Basic structural lemmas -/
/-! ### kChain and wideParallel profile lemmas -/
/-
**Depth-width-generator tradeoff**: the product of depth and max width
is at least the generator count. This is the operadic analogue of the
circuit complexity lower bound: you need enough "area" to fit all generators.
Bridge: connects tropical geometry (area of Newton polytope) to circuit
complexity (depth × width lower bounds).
-/
end ArchExpr
/-! ## Section 2: Tropical Architecture Profile
The `TropicalArchProfile` is the tropical codomain of the valuation functor.
It carries two composition operations (sequential and parallel) corresponding
to the two operadic compositions, and a tropical addition (component-wise min)
making it an idempotent semiring-like structure. -/
/-- Tropical architecture profile: the signature of an architecture's complexity.
Bridge: connects tropical geometry (valuations) to ML (architecture metrics). -/
@[ext] structure TropicalArchProfile where
depthVal : ℕ
widthVal : ℕ
genVal : ℕ
deriving DecidableEq, Repr
namespace TropicalArchProfile
/-- Sequential composition of profiles (tropical "multiplication" for depth-like
operations): depth adds, width takes max, generators add.
Bridge: captures how sequential layer stacking increases depth additively. -/
def seqMul (p q : TropicalArchProfile) : TropicalArchProfile :=
⟨p.depthVal + q.depthVal, max p.widthVal q.widthVal, p.genVal + q.genVal⟩
/-- Parallel composition of profiles: depth takes max, width adds, generators add.
Bridge: captures how parallel branching increases width additively. -/
def parMul (p q : TropicalArchProfile) : TropicalArchProfile :=
⟨max p.depthVal q.depthVal, p.widthVal + q.widthVal, p.genVal + q.genVal⟩
/-- Tropical addition: component-wise minimum. This is the idempotent
"addition" of tropical algebra, selecting the "cheapest" profile. -/
def tropAdd (p q : TropicalArchProfile) : TropicalArchProfile :=
⟨min p.depthVal q.depthVal, min p.widthVal q.widthVal, min p.genVal q.genVal⟩
/-- The unit profile: identity element for both seqMul and parMul. -/
def unit : TropicalArchProfile := ⟨0, 0, 0⟩
/-- The generator profile: profile of a single computation module. -/
def gen : TropicalArchProfile := ⟨1, 1, 1⟩
/-- Component-wise partial order on profiles. -/
instance : LE TropicalArchProfile where
le p q := p.depthVal ≤ q.depthVal ∧ p.widthVal ≤ q.widthVal ∧ p.genVal ≤ q.genVal
/-! ### Sequential composition monoid laws -/
/-! ### Parallel composition commutative monoid laws -/
/-! ### Tropical addition semilattice laws -/
/-! ### Tropical distributivity
The key tropical semiring law: sequential composition distributes over
tropical addition. This is the operadic analogue of the fundamental
property `a + min(b,c) = min(a+b, a+c)` in tropical arithmetic.
Bridge: connects idempotent semiring theory to certified architecture optimization —
composing with the "best of two alternatives" equals the best of the two compositions. -/
end TropicalArchProfile
/-! ## Section 3: The Tropical Valuation Functor
The tropical valuation maps architecture expressions to their tropical profiles.
It is functorial with respect to both sequential and parallel composition:
this is the core "functor" property that makes the valuation useful for
classification. -/
/-- The tropical valuation functor: maps an architecture expression to its
tropical complexity profile.
Bridge: connects operadic syntax (tree structure) to tropical algebra
(min-plus coordinates), enabling classification via tropical invariants. -/
def tropicalValuation : ArchExpr → TropicalArchProfile
| .generator => ⟨1, 1, 1⟩
| .identity => ⟨0, 0, 0⟩
| .compose e₁ e₂ =>
let v₁ := tropicalValuation e₁
let v₂ := tropicalValuation e₂
⟨v₁.depthVal + v₂.depthVal, max v₁.widthVal v₂.widthVal, v₁.genVal + v₂.genVal⟩
| .parallel e₁ e₂ =>
let v₁ := tropicalValuation e₁
let v₂ := tropicalValuation e₂
⟨max v₁.depthVal v₂.depthVal, v₁.widthVal + v₂.widthVal, v₁.genVal + v₂.genVal⟩
/-! ## Section 4: Structural Congruence
The structural congruence on architecture expressions captures the algebraic
rewriting rules of operadic composition: associativity, identity laws, and
commutativity of parallel composition. This is the operadic analogue of
the Myhill–Nerode equivalence.
Bridge: connects operad theory (presentation by generators and relations)
to automata theory (state equivalence) to certified ML compression
(architecture normalization). -/
/-- Structural congruence: the equivalence relation on architecture expressions
generated by the operadic rewriting rules. Two expressions are structurally
congruent if they represent the same "abstract architecture" modulo
associativity, identity, and parallel commutativity. -/
inductive StructuralCongr : ArchExpr → ArchExpr → Prop where
| refl (e) : StructuralCongr e e
| symm {e₁ e₂} : StructuralCongr e₁ e₂ → StructuralCongr e₂ e₁
| trans {e₁ e₂ e₃} : StructuralCongr e₁ e₂ → StructuralCongr e₂ e₃ → StructuralCongr e₁ e₃
| compose_assoc (e₁ e₂ e₃) :
StructuralCongr (.compose (.compose e₁ e₂) e₃) (.compose e₁ (.compose e₂ e₃))
| compose_id_left (e) : StructuralCongr (.compose .identity e) e
| compose_id_right (e) : StructuralCongr (.compose e .identity) e
| parallel_comm (e₁ e₂) : StructuralCongr (.parallel e₁ e₂) (.parallel e₂ e₁)
| parallel_assoc (e₁ e₂ e₃) :
StructuralCongr (.parallel (.parallel e₁ e₂) e₃) (.parallel e₁ (.parallel e₂ e₃))
| parallel_id_left (e) : StructuralCongr (.parallel .identity e) e
| parallel_id_right (e) : StructuralCongr (.parallel e .identity) e
| congr_compose (e₁ e₁' e₂ e₂') : StructuralCongr e₁ e₁' → StructuralCongr e₂ e₂' →
StructuralCongr (.compose e₁ e₂) (.compose e₁' e₂')
| congr_parallel (e₁ e₁' e₂ e₂') : StructuralCongr e₁ e₁' → StructuralCongr e₂ e₂' →
StructuralCongr (.parallel e₁ e₂) (.parallel e₁' e₂')
/-
**The tropical valuation is invariant under structural congruence.**
This is the central soundness theorem: operadic rewrites do not change
the tropical complexity profile.
Bridge: connects operad presentation theory to tropical invariant theory —
the valuation is a well-defined function on the quotient operad.
-/
/-! ## Section 5: Profile Congruence and Completeness
The profile congruence identifies two expressions when they have the same
tropical profile. The key theorems:
1. Structural congruence implies profile congruence (soundness).
2. Profile congruence is a complete invariant within bounded classes. -/
/-- Profile congruence: two expressions are profile-equivalent when they
have the same tropical valuation.
Bridge: this is the "tropical shadow" of operadic equivalence. -/
def profileCongr : Setoid ArchExpr where
r e₁ e₂ := tropicalValuation e₁ = tropicalValuation e₂
iseqv := ⟨fun _ => rfl, fun h => h.symm, fun h₁ h₂ => h₁.trans h₂⟩
/-! ## Section 6: Bounded Architecture Classification
For bounded architecture classes (bounded depth, width, generator count),
the tropical profile takes values in a finite set. This enables finite
classification: there are only finitely many distinct tropical signatures
in any bounded class.
Bridge: connects tropical geometry (finite Newton polytopes) to
circuit complexity (bounded circuit classification). -/
/-- Predicate for membership in a bounded architecture class. -/
def InBoundedClass (e : ArchExpr) (G D W : ℕ) : Prop :=
e.generatorCount ≤ G ∧ e.depth ≤ D ∧ e.maxWidth ≤ W
/-- The finite set of all achievable profiles within bounds. -/
def BoundedProfileSet (G D W : ℕ) : Finset TropicalArchProfile :=
(Finset.range (D + 1) ×ˢ (Finset.range (W + 1) ×ˢ Finset.range (G + 1))).image
fun ⟨d, w, g⟩ => ⟨d, w, g⟩
/-
The bounded profile set has at most (D+1)*(W+1)*(G+1) elements.
-/
/-
The tropical valuation of a bounded expression lies in the bounded profile set.
This is the key finiteness theorem: bounded architectures have bounded profiles.
-/
/-! ## Section 7: Canonical Skeleton and Reconstruction
The canonical skeleton is the tropical profile itself. Reconstruction
from the profile is the identity on profiles. The key theorems establish
that this reconstruction is well-defined, unique, and invariant under
both structural and profile congruence.
Bridge: connects tropical reconstruction (recovering a polytope from
its tropicalization) to ML architecture compression (canonical form). -/
/-- Architecture skeleton: the canonical representative data for an architecture class.
The skeleton IS the tropical profile — it carries exactly the information
needed to classify the architecture. -/
abbrev ArchitectureSkeleton := TropicalArchProfile
/-- Reconstruct the canonical skeleton from a tropical profile.
Bridge: connects tropical geometry (tropicalization) to ML (architecture search). -/
def reconstructSkeleton (p : TropicalArchProfile) : ArchitectureSkeleton := p
/-- A skeleton is canonical-minimal for an expression when it equals its profile. -/
def IsCanonicalMinimalSkeleton (e : ArchExpr) (S : ArchitectureSkeleton) : Prop :=
tropicalValuation e = S
/-! ## Section 8: Main Reconstruction Theorems
These are the culminating results: certified operadic tropical reconstruction
for bounded architecture classes. -/
/-! ## Section 9: Composition Bounds and Architecture Complexity
Additional structural theorems relating architecture complexity measures
through tropical valuation properties. -/
/-
Sequential composition preserves bounded class membership.
-/
/-
Parallel composition preserves bounded class membership.
-/
/-
The tropical valuation of a sequential composition is bounded by the
sequential product of the individual bounds.
-/
/-
**Depth-width tradeoff for profiles**: profile depth × width ≥ generators.
This is the profile-level formulation of the fundamental complexity bound.
-/
end OperadicTropicalization