Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Reduced-word types and finite polynomial-support operations

Definition
Nonadditivity_Linearization

by JWang226 · Oct 7, 2026 · Mathlib c5ea003 (Lean v4.30.0)

combinatoricsfree-groupsholevo-additivity-gap-v100quantum-information

Let L={0,1,2,3}L=\{0,1,2,3\}L={0,1,2,3}, with inverse a−1=3−aa^{-1}=3-aa−1=3−a, and set F(a)={b∈L:b≠a−1}F(a)=\{b\in L:b\ne a^{-1}\}F(a)={b∈L:b=a−1}. Reduced tails satisfy

Ta(0)={∗},Ta(m+1)=∐b∈F(a)Tb(m),∣F(a)∣=3,∣Ta(m)∣=3m.T_a(0)=\{\ast\},\qquad T_a(m+1)=\coprod_{b\in F(a)}T_b(m),\qquad |F(a)|=3,\quad |T_a(m)|=3^m.Ta​(0)={∗},Ta​(m+1)=b∈F(a)∐​Tb​(m),∣F(a)∣=3,∣Ta​(m)∣=3m.

A nonempty reduced word of length m+1m+1m+1 is a first letter together with such a tail. The bundle provides finite type structures and the inverse-involution identity. For a finite subset SSS of a group GGG, it also defines

S−1S={g−1h:g,h∈S}S^{-1}S=\{g^{-1}h:g,h\in S\}S−1S={g−1h:g,h∈S}

and proves its membership characterization. Finally, for real scalars x,yx,yx,y, the nonnegative relative norm error is max⁡{0,x/y−1}\max\{0,x/y-1\}max{0,x/y−1}. These discrete types, support operations, and scalar error quantities are the imported combinatorial infrastructure for polynomial reductions.

Definition code
import Lean.Elab.Tactic.Omega
import Mathlib.Algebra.Order.BigOperators.Ring.Finset
import Mathlib.Analysis.CStarAlgebra.Matrix
import Mathlib.Analysis.Matrix.Order
import Mathlib.Analysis.Normed.Operator.Basic
import Mathlib.Data.Fin.Rev
import Mathlib.Data.Finset.Prod
import Mathlib.Data.Fintype.Sigma
import Mathlib.Data.Matrix.Block
import Mathlib.Data.Matrix.ColumnRowPartitioned
import Mathlib.Data.Real.Basic
import Mathlib.Data.Real.Sqrt
import Mathlib.LinearAlgebra.Matrix.Hermitian
import Mathlib.Tactic.Linarith
import Mathlib.Tactic.NormNum
import Mathlib.Tactic.Positivity
import Mathlib.Tactic.Ring

/-
Copyright (c) 2026 the Nonadditivity project contributors.
All rights reserved. See COPYRIGHT.md for licensing and attribution.
-/



















/-!
# Algebraic and numerical steps in polynomial linearization

This file proves the finite support bound, Gram factorization identities,
Hermitian dilation identities, the scalar backward-error calculation, and the
geometric word-count calculation used in Sections 3 and Appendix A of
`nonadditivity.tex`.

The analytic existence of the positive block matrix with the stated operator
norm bound is not assumed globally or declared as an axiom here. The Gram
identities below apply to any supplied square-root factor; the error theorem
states its norm-identity hypotheses explicitly.
-/

set_option backward.isDefEq.respectTransparency false

namespace Nonadditivity.Linearization

open scoped BigOperators

section Support

variable {G : Type*} [Group G] [DecidableEq G]

/-- The finite set `S⁻¹ S`, represented without a pointwise-set convention. -/
def differenceSupport (S : Finset G) : Finset G :=
  (S ×ˢ S).image (fun gh => gh.1⁻¹ * gh.2)

@[simp] theorem mem_differenceSupport {S : Finset G} {w : G} :
    w ∈ differenceSupport S ↔ ∃ g ∈ S, ∃ h ∈ S, g⁻¹ * h = w := by
  simp only [differenceSupport, Finset.mem_image, Finset.mem_product]
  constructor
  · rintro ⟨⟨g,h⟩, ⟨hg,hh⟩, hw⟩
    exact ⟨g,hg,h,hh,hw⟩
  · rintro ⟨g,hg,h,hh,hw⟩
    exact ⟨(g,h), ⟨hg,hh⟩, hw⟩









end Support

section Gram

variable {ι κ ν : Type*} [Fintype ι] [Fintype κ] [Fintype ν]
variable {A : Type*} [NonUnitalSemiring A] [StarRing A]







end Gram

section PositiveMatrices

open scoped ComplexOrder MatrixOrder Matrix.Norms.L2Operator

variable {ι ν : Type*} [Fintype ι] [DecidableEq ι] [Fintype ν]









end PositiveMatrices

section Dilation

variable {ι : Type*} [Fintype ι]
variable {A : Type*} [NonUnitalSemiring A] [StarRing A]







end Dilation

section ErrorTransfer





/-- Nonnegative relative excess used for every intermediate polynomial. -/
noncomputable def relativeNormError (a b : ℝ) : ℝ := max 0 (a / b - 1)

@[simp] theorem relativeNormError_nonneg (a b : ℝ) : 0 ≤ relativeNormError a b :=
  le_max_left _ _







end ErrorTransfer

section OperatorCauchySchwarz

variable {ι : Type*} {E F 𝕜 : Type*}
variable [NontriviallyNormedField 𝕜] [SeminormedAddCommGroup E] [SeminormedAddCommGroup F]
variable [NormedSpace 𝕜 E] [NormedSpace 𝕜 F]









end OperatorCauchySchwarz

section HilbertCoefficientEnergy

variable {ι E F 𝕜 : Type*} [RCLike 𝕜]
variable [NormedAddCommGroup E] [InnerProductSpace 𝕜 E] [CompleteSpace E]
variable [NormedAddCommGroup F] [InnerProductSpace 𝕜 F] [CompleteSpace F]





end HilbertCoefficientEnergy

section Counts

/-- The four oriented letters of a free group on two generators. -/
abbrev Letter := Fin 4

/-- `0 ↔ 3` and `1 ↔ 2` form the two inverse pairs. -/
def inverseLetter (a : Letter) : Letter := a.rev

@[simp] theorem inverseLetter_inverse (a : Letter) :
    inverseLetter (inverseLetter a) = a := by simp [inverseLetter]



/-- Legal letters following `a`: all letters except its inverse. -/
abbrev FollowingLetter (a : Letter) := {b : Letter // b ≠ inverseLetter a}

@[simp] theorem card_followingLetter (a : Letter) :
    Fintype.card (FollowingLetter a) = 3 := by
  simp [FollowingLetter, Fintype.card_subtype_compl]

/-- A genuine reduced tail; each next letter excludes the previous inverse. -/
def ReducedTail (a : Letter) : ℕ → Type
  | 0 => Unit
  | n + 1 => Σ b : FollowingLetter a, ReducedTail b.val n

noncomputable instance reducedTailFintype (a : Letter) (n : ℕ) :
    Fintype (ReducedTail a n) := by
  induction n generalizing a with
  | zero => exact inferInstanceAs (Fintype Unit)
  | succ n ih =>
    change Fintype (Σ b : FollowingLetter a, ReducedTail b.val n)
    letI : ∀ b : FollowingLetter a, Fintype (ReducedTail b.val n) := fun b => ih b.val
    infer_instance

/-- Exactly three choices are available for each subsequent letter. -/
@[simp] theorem card_reducedTail (a : Letter) (n : ℕ) :
    Fintype.card (ReducedTail a n) = 3 ^ n := by
  induction n generalizing a with
  | zero => simp [ReducedTail]
  | succ n ih =>
    change Fintype.card (Σ b : FollowingLetter a, ReducedTail b.val n) = _
    rw [Fintype.card_sigma]
    simp [ih, pow_succ, mul_comm]

/-- A nonempty reduced word of length `t+1` is its first letter and reduced tail. -/
abbrev ReducedWord (t : ℕ) := Σ a : Letter, ReducedTail a t








end Counts

end Nonadditivity.Linearization
Source
https://github.com/JWang226/Holevo-Additivity-Gap/blob/635aa93eb3a2310b79fd5371e2ce311914ec5887/Nonadditivity/Linearization.lean#L48-L427
Human review
  • Endorsed by Shuze Chen · Oct 9, 2026

    Confirmed by the moderator at approval.

  • Endorsed by JWang226 · Oct 9, 2026

    Confirmed by the mission captain (proposal self-audit).

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