Aether Catalog definitions — Bridges_SharpExponentLowerBounds
DefinitionBridges_SharpExponentLowerBoundsaether-catalogbridges
Definition bundle for the Aether Catalog module Bridges.SharpExponentLowerBounds, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.
Definition code
-- Def bundle generated from Bridges/SharpExponentLowerBounds.lean by skeleton subtraction
import Mathlib
/-
Copyright (c) 2025 Harmonic. All rights reserved.
Released under Apache 2.0 license.
-/
/-!
# Sharp Exponent Lower Bounds for Exchange Descent
This file develops a **lower-bound obstruction theory** for exchange descent
algorithms, complementing the upper-bound theory in `DepthSensitiveExchangeDescent.lean`.
## Main Results
* `descent_length_ge_layerDrop` — Abstract layer forcing: any descent path through
a layered state space must have length at least the total layer drop.
* `adversarial_descent_lower_bound` — Every descent chain in an adversarial family
has length at least the forced layer drop.
* `exponent_gap_is_single_power` — The gap between upper-bound exponent `d-k` and
lower-bound exponent `d-k-1` is exactly one power of `d`.
* `decisionTree_leaves_le_pow_depth` — Decision-tree depth lower bounds from
leaf counts, bridging to computational complexity.
## Key New Concepts
* `LayerProfile` — Stratification with bounded-step constraint.
* `AdversarialExchangeFamily` — Exchange system with layer-profile witness.
* `DecisionTree` — Simple decision-tree model for cross-domain bridge.
* `RankedSetSystem` — Algebraic combinatorics bridge via rank stratification.
-/
open Finset Function
noncomputable section
/-! ## Part 1: Layer Profile — Abstract Lower-Bound Engine -/
/-- A **layer profile** on a type `α`. The function `layer : α → ℕ` assigns
each state to a layer. Any admissible step can decrease the layer by at most 1.
This is the abstract lower-bound engine. -/
structure LayerProfile (α : Type*) where
layer : α → ℕ
top : ℕ
bottom : ℕ
top_ge_bottom : bottom ≤ top
/-- The **forced layer drop**: minimum number of layers any descent must traverse. -/
def forcedLayerDrop {α : Type*} (L : LayerProfile α) : ℕ :=
L.top - L.bottom
/-! ### Theorem 1: Layer Forcing Lower Bound -/
/-! ## Part 2: Exchange System Definitions -/
/-- An **exchange step** on `Fin d → ℤ`: modifies exactly two coordinates by ±1. -/
def IsExchStep {d : ℕ} (x y : Fin d → ℤ) : Prop :=
∃ i j : Fin d, i ≠ j ∧
y i = x i + 1 ∧ y j = x j - 1 ∧
∀ k, k ≠ i → k ≠ j → y k = x k
/-- An **improving exchange step**: feasible, exchange, and objective-decreasing. -/
def IsImprovingExchStep {d : ℕ} (S : Finset (Fin d → ℤ))
(f : (Fin d → ℤ) → ℤ) (x y : Fin d → ℤ) : Prop :=
x ∈ S ∧ y ∈ S ∧ IsExchStep x y ∧ f y < f x
/-- **Directional exchange certificate (DLC)**. -/
def HasExchDLC {d : ℕ} (S : Finset (Fin d → ℤ))
(f : (Fin d → ℤ) → ℤ) : Prop :=
∀ x ∈ S, ∀ y ∈ S, f y < f x →
∃ z, IsImprovingExchStep S f x z
/-- **Depth-graded exchange certificate**. -/
def ExchDLC_k {d : ℕ} :
ℕ → Finset (Fin d → ℤ) → ((Fin d → ℤ) → ℤ) → Prop
| 0, _, _ => True
| k + 1, S, f => HasExchDLC S f ∧ ExchDLC_k k S f
/-- A **descent chain** of `n` improving steps. -/
structure ExchDescentChain {d : ℕ} (S : Finset (Fin d → ℤ))
(f : (Fin d → ℤ) → ℤ) (n : ℕ) where
seq : Fin (n + 1) → (Fin d → ℤ)
mem : ∀ i, seq i ∈ S
step : ∀ (i : Fin n),
IsImprovingExchStep S f (seq i.castSucc) (seq i.succ)
/-! ## Part 3: Adversarial Exchange Family -/
/-- An **adversarial exchange family** in dimension `d` with depth `k`:
an exchange system with a start state and a layer profile demonstrating
that all descent paths are long. -/
structure AdversarialExchangeFamily (d k : ℕ) where
S : Finset (Fin d → ℤ)
f : (Fin d → ℤ) → ℤ
start : Fin d → ℤ
start_mem : start ∈ S
cert : ExchDLC_k k S f
profile : LayerProfile (Fin d → ℤ)
start_at_top : profile.layer start = profile.top
terminal_at_bottom : ∀ x ∈ S,
(¬∃ z, IsImprovingExchStep S f x z) → profile.layer x = profile.bottom
layerStep : ∀ x y, IsImprovingExchStep S f x y →
profile.layer x ≤ profile.layer y + 1
/-! ## Part 4: Theorem 1 — Layer Forcing for Exchange Descent -/
/-
**Theorem 1: Layer forcing for exchange descent chains.**
Every descent chain from the start to a terminal state has length at least
the forced layer drop.
Proof: Apply `descent_length_ge_layerDrop` with the layer function
composed with the chain sequence. The step constraint follows from
`layerStep`, and the boundary conditions from `start_at_top` and
`terminal_at_bottom`.
-/
/-
**Descent chain length bound from any layer function.**
A direct formulation: any layer function with step bound gives
a lower bound on chain length.
-/
/-! ## Part 5: Theorem 2 — Exponential Gap Analysis -/
/-
**Exponential gap theorem**: `d^(d-k) = d * d^(d-k-1)`.
The upper and lower bounds differ by exactly one power of `d`.
-/
/-- **Adversarial layer count**: `d^(d-k-1)` when `k+1 < d`, else `1`. -/
def adversarialLayerCount (d k : ℕ) : ℕ :=
if k + 1 < d then d ^ (d - k - 1) else 1
/-
**Layer count ratio**: `adversarialLayerCount * d = d^(d-k)`.
-/
/-
**Full depth gives constant complexity**: `adversarialLayerCount d (d-2) = d`.
-/
/-! ## Part 6: Decision-Tree Bridge (Cross-Domain Connection) -/
/-- A **decision tree**: internal nodes query a predicate, leaves output a value. -/
inductive DecisionTree (α β : Type*) where
| leaf (b : β) : DecisionTree α β
| branch (query : α → Bool) (left right : DecisionTree α β) : DecisionTree α β
/-- The **depth** of a decision tree. -/
def DecisionTree.depth {α β : Type*} : DecisionTree α β → ℕ
| .leaf _ => 0
| .branch _ l r => 1 + max l.depth r.depth
/-- **Number of leaves** in a decision tree. -/
def DecisionTree.numLeaves {α β : Type*} : DecisionTree α β → ℕ
| .leaf _ => 1
| .branch _ l r => l.numLeaves + r.numLeaves
/-
**Leaves bounded by depth**: a binary tree of depth `d` has at most `2^d` leaves.
-/
/-! ## Part 7: Ranked Set Systems (Algebraic Combinatorics Bridge) -/
/-- A **ranked set system**: finite ground set with a rank function. -/
structure RankedSetSystem (α : Type*) where
ground : Finset α
rank : α → ℕ
maxRank : ℕ
/-- The **rank gap** of a ranked set system. -/
def rankGap {α : Type*} (M : RankedSetSystem α) : ℕ := M.maxRank
/-! ## Part 8: Falsifiable Conjecture -/
/-! ## Part 9: Verified Algorithm -/
/-- **Build a layer profile** with `T` forced layers from a layer function. -/
def buildLayerProfile (α : Type*) (ℓ : α → ℕ) (T : ℕ) : LayerProfile α where
layer := ℓ
top := T
bottom := 0
top_ge_bottom := Nat.zero_le T
/-! ## Part 10: Combining Upper and Lower Bounds -/
/-
**Combined bound theorem**: `d^(d-k-1) * d = d^(d-k)`.
The lower bound times `d` equals the upper bound exponent.
-/
end