Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite color histograms and position symmetrization

Definition
InfoLossLAR_Native_AFT_Histogram

by BoomShaKaLaaaKa · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

finite-probabilityinfo-loss-lar-native-5c3becbstoc-2027

For a vector x:{0,…,d−1}→Cx:\{0,\ldots,d-1\}\to Cx:{0,…,d−1}→C, its histogram records

hx(c)=#{i:x(i)=c}.h_x(c)=\#\{i:x(i)=c\}.hx​(c)=#{i:x(i)=c}.

Each count is encoded as an integer between 000 and ddd. Position permutations act on vectors, and averaging this action defines random relabeling and symmetrization of finite laws. The same interface includes the zero-sum subset when colors carry addition.

Definition code
import Definitions.Def_InfoLossLAR_Native_AFT_TotalVariation
import Mathlib


/-!
# Concrete histograms and uniform position relabeling

This is the finite combinatorial step of reference V7, Corollary 9.21.
Histograms count colors in actual vectors `Fin dimension → Color`. Equality
of histograms is proved equivalent to relabeling positions by a permutation.
-/

namespace AFT

open scoped BigOperators
open scoped Classical

variable {dimension : ℕ} {Color : Type*}

/-- A finite encoding of color counts; every count lies between zero and the
number of positions. Invalid count vectors are permitted in this ambient type. -/
abbrev Histogram (dimension : ℕ) (Color : Type*) := Color → Fin (dimension + 1)

/-- The actual histogram of a vector, with counts defined by color fibers. -/
noncomputable def histogram (vector : Fin dimension → Color) : Histogram dimension Color := by
  classical
  exact fun color => ⟨Fintype.card {position // vector position = color}, by
    have h := Fintype.card_subtype_le (fun position => vector position = color)
    simpa only [Fintype.card_fin, Nat.lt_succ_iff] using h⟩

@[simp] theorem histogram_count (vector : Fin dimension → Color) (color : Color) :
    (histogram vector color : ℕ) = Fintype.card {position // vector position = color} := by
  classical
  rfl

/-- Reindex a vector by a permutation of positions. -/
def relabel (vector : Fin dimension → Color) (permutation : Equiv.Perm (Fin dimension)) :
    Fin dimension → Color := vector ∘ permutation

@[simp] theorem relabel_apply (vector : Fin dimension → Color)
    (permutation : Equiv.Perm (Fin dimension)) (position : Fin dimension) :
    relabel vector permutation position = vector (permutation position) := rfl





/-- Reindexing positions is an equivalence of the entire vector space. -/
def relabelEquiv (permutation : Equiv.Perm (Fin dimension)) :
    (Fin dimension → Color) ≃ (Fin dimension → Color) where
  toFun vector := relabel vector permutation
  invFun vector := relabel vector permutation.symm
  left_inv vector := by ext position; simp [relabel]
  right_inv vector := by ext position; simp [relabel]

variable [Fintype Color]

/-- Apply an independently uniform position permutation to a fixed vector. -/
noncomputable def randomRelabel (vector : Fin dimension → Color) :
    FiniteDist (Fin dimension → Color) :=
  (FiniteDist.uniform (Equiv.Perm (Fin dimension))).map (relabel vector)













namespace FiniteDist

variable {α β γ : Type*} [Fintype α] [Fintype β] [Fintype γ]

/-- Draw a deterministic image and then apply a kernel, or apply their
composition directly. -/
theorem mix_map (distribution : FiniteDist α) (image : α → β)
    (kernel : β → FiniteDist γ) :
    (distribution.map image).mix kernel =
      distribution.mix (fun input => kernel (image input)) := by
  ext output
  simp only [mix_weight, map_weight]
  simp_rw [Finset.sum_mul, ite_mul, zero_mul]
  rw [Finset.sum_comm]
  simp

/-- Deterministic pushforward commutes with a mixture. -/
theorem map_mix (distribution : FiniteDist α) (kernel : α → FiniteDist β)
    (image : β → γ) :
    (distribution.mix kernel).map image =
      distribution.mix (fun input => (kernel input).map image) := by
  ext output
  simp only [mix_weight, map_weight, Finset.mul_sum]
  trans ∑ candidate, ∑ input,
    if image candidate = output then distribution.weight input * (kernel input).weight candidate
      else 0
  · apply Finset.sum_congr rfl
    intro candidate _
    split_ifs <;> simp
  · rw [Finset.sum_comm]
    simp only [mul_ite, mul_zero]



end FiniteDist

/-- Relabel every sampled vector by independent fresh uniform randomness. -/
noncomputable def symmetrize (distribution : FiniteDist (Fin dimension → Color)) :
    FiniteDist (Fin dimension → Color) := distribution.mix randomRelabel







section HistogramKernel

variable [Nonempty Color]















end HistogramKernel

section ZeroSumReference

variable [AddCommMonoid Color]

/-- The concrete zero-sum endpoint set. -/
abbrev ZeroSumVectors (dimension : ℕ) (Color : Type*) [AddCommMonoid Color] :=
  {vector : Fin dimension → Color // ∑ position, vector position = 0}

instance zeroSumVectorsNonempty : Nonempty (ZeroSumVectors dimension Color) :=
  ⟨⟨fun _ => 0, by simp⟩⟩











end ZeroSumReference

end AFT
Source
Local manuscript repository commit 5c3becb254daaa8738368b474349766c1769c2a0; lean/AFT/Histogram.lean; migrated source SHA256 9d3ee194cbde3da95a4c528a9f96cb4d7393a95f5ca8329546f1925e383edbfa; byte-range skeleton from Lean AST, with original retained definitions and proofs.

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