Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Aether Catalog definitions — Tropical_NeuralCoding_TropicalPruning

Definition
Tropical_NeuralCoding_TropicalPruning

by raver1975 · Sep 17, 2026 · Mathlib c5ea003 (Lean v4.30.0)

aether-catalogtropical

Definition bundle for the Aether Catalog module Tropical.NeuralCoding.TropicalPruning, transplanted by skeleton subtraction; supplies the types and constants the catalog's theorems import.

Definition code
-- Def bundle generated from Tropical/NeuralCoding/TropicalPruning.lean by skeleton subtraction
import Mathlib

/-!
# Tropical Polynomial Pruning: Certified Semantic Compression

This file establishes the mathematical foundations for **tropical polynomial pruning**,
a framework for certified compression and interpretability of piecewise-linear models
(such as ReLU neural networks) through tropical geometry.

## Overview

A tropical polynomial is a finite maximum of affine forms. Canonical pruning removes
monomials (affine templates) that are *strictly* dominated on a finite domain — meaning
there exists another monomial that is at least as large everywhere and strictly larger
somewhere. This yields an equivalent but potentially smaller tropical polynomial.

## Key Design Choice: Strict Domination

We use **strict domination** (≤ everywhere, < somewhere) rather than weak domination
(≤ everywhere). This is essential because weak domination can cause mutual elimination
of functionally equivalent but structurally distinct monomials, breaking the preservation
theorem. Strict domination is acyclic on finite sets, ensuring that the pruning process
terminates with correct semantics.

## Main Results

* `canonicalOn_eval_eq` — **Theorem A**: Canonical pruning preserves evaluation.
* `max_affine_relu_bridge` — Max of affine forms is ReLU-computable.
* `relu_tropical_pruning_sound` — **Theorem B**: ReLU-tropical pruning soundness.
* `card_canonicalOn_le` — **Theorem D**: Canonical support ≤ original support.
-/

noncomputable section

open Finset BigOperators

/-! ## Core Definitions -/

/-- A tropical monomial (affine template) in `n` variables.
    Represents `x ↦ bias + ∑ᵢ weight i * x i`. -/
structure TPMonomial (n : ℕ) where
  bias : ℝ
  weight : Fin n → ℝ
  deriving DecidableEq

namespace TPMonomial

/-- Evaluate a tropical monomial at a point. -/
def eval {n : ℕ} (m : TPMonomial n) (x : Fin n → ℝ) : ℝ :=
  m.bias + ∑ i, m.weight i * x i


end TPMonomial

/-- A tropical polynomial: a nonempty finite set of monomials.
    Evaluation takes the supremum (max). -/
structure TPoly (n : ℕ) where
  support : Finset (TPMonomial n)
  nonempty : support.Nonempty

namespace TPoly

/-- Evaluate: max over monomial evaluations. -/
def eval {n : ℕ} (p : TPoly n) (x : Fin n → ℝ) : ℝ :=
  p.support.sup' p.nonempty (fun m => m.eval x)


end TPoly

/-- **Strict domination**: `m` is strictly dominated by `m'` on domain `D` if
    `m.eval x ≤ m'.eval x` for all `x ∈ D`, and `m.eval x < m'.eval x` for
    some `x ∈ D`. This is acyclic on finite domains, which is essential for
    the pruning preservation theorem. -/
def StrictlyDominatedOn {n : ℕ} (D : Finset (Fin n → ℝ)) (m m' : TPMonomial n) : Prop :=
  (∀ x ∈ D, m.eval x ≤ m'.eval x) ∧ (∃ x ∈ D, m.eval x < m'.eval x)

/-- A monomial is strictly dominated in a polynomial if some other support monomial
    strictly dominates it on the entire domain. -/
def IsStrictlyDominated {n : ℕ} (D : Finset (Fin n → ℝ)) (p : TPoly n)
    (m : TPMonomial n) : Prop :=
  ∃ m' ∈ p.support, m' ≠ m ∧ StrictlyDominatedOn D m m'

instance instDecStrictlyDominatedOn {n : ℕ} (D : Finset (Fin n → ℝ))
    (m m' : TPMonomial n) : Decidable (StrictlyDominatedOn D m m') :=
  inferInstanceAs (Decidable ((∀ x ∈ D, m.eval x ≤ m'.eval x) ∧
    (∃ x ∈ D, m.eval x < m'.eval x)))

instance instDecIsStrictlyDominated {n : ℕ} (D : Finset (Fin n → ℝ))
    (p : TPoly n) (m : TPMonomial n) :
    Decidable (IsStrictlyDominated D p m) :=
  inferInstanceAs (Decidable (∃ m' ∈ p.support, m' ≠ m ∧ StrictlyDominatedOn D m m'))

namespace TPoly

/-- **Canonical pruning**: remove strictly dominated monomials.
    Falls back to `p` if the filter empties. -/
def canonicalOn {n : ℕ} (D : Finset (Fin n → ℝ)) (p : TPoly n) : TPoly n :=
  let filtered := p.support.filter (fun m => ¬IsStrictlyDominated D p m)
  if h : filtered.Nonempty then ⟨filtered, h⟩ else p



end TPoly

/-! ## Helper lemmas -/


/-
There exists a monomial achieving the sup'.
-/

/-
For strictly dominated m by m', if we follow the chain of strict dominations
    in a finite set, we eventually reach an undominated element with value ≥ m.
-/

/-! ## Theorem A: Canonical pruning preserves evaluation -/

/-
**Theorem A (Canonical Pruning Preserves Semantics).**

    Removing all monomials that are strictly dominated (≤ everywhere, < somewhere)
    on the domain does not change the evaluation at any domain point.

    The proof uses two key facts:
    1. Canonical support ⊆ original support, so canonical eval ≤ original eval.
    2. For each monomial m in the original support, there exists an undominated
       monomial m' with m'(x) ≥ m(x), because strict domination is acyclic on
       finite sets. Thus original eval ≤ canonical eval.
-/

/-! ## ReLU bridge -/

/-- ReLU function. -/
def reluFn (x : ℝ) : ℝ := max x 0


/-! ## Theorem B: ReLU-tropical pruning soundness -/

/-- Construct a tropical polynomial from an affine family. -/
def TPoly.ofAffineFamily {n k : ℕ} (A : Fin k → (Fin n → ℝ))
    (b : Fin k → ℝ) (hk : 0 < k) : TPoly n where
  support := Finset.univ.image (fun i => TPMonomial.mk (b i) (A i))
  nonempty := ⟨_, Finset.mem_image.mpr ⟨⟨0, hk⟩, Finset.mem_univ _, rfl⟩⟩


/-! ## Theorem C direction: essential monomials survive -/

/-
**Theorem C (Uniquely-Maximal Monomial Survives).**
    If `m` is *strictly* the maximum at some domain point (beats all other
    monomials), then `m` cannot be strictly dominated and thus survives
    canonical pruning.

    This is the interpretability direction: monomials with unique witness
    points are guaranteed to survive as essential decision templates.
-/

/-! ## Theorem D: Compression bound -/


end

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me