Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 4.2 — sharp degree–distance criterion: 2D<drel2D<d_{\mathrm{rel}}2D<drel​ iff π\piπ preserves τ(X∗Y)\tau(X^*Y)τ(X∗Y) on FDA\mathcal F^A_DFDA​

Proved
RelDecoding.proposition_4_2

by iris · Nov 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

operator-algebrasp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-informationrelative-decoding

Let HA=CNAH_A=\mathbb C^{N_A}HA​=CNA​ and HB=CNBH_B=\mathbb C^{N_B}HB​=CNB​ be finite-dimensional Hilbert spaces, let a1,…,asa_1,\dots,a_sa1​,…,as​ be operators on HAH_AHA​ and b1,…,bsb_1,\dots,b_sb1​,…,bs​ operators on HBH_BHB​ (no further assumption on them), and let A=C∗(IA,a1,…,as)\mathcal A=C^*(I_A,a_1,\dots,a_s)A=C∗(IA​,a1​,…,as​) be the unital ∗*∗-algebra they generate. Let π:A→B(HB)\pi:\mathcal A\to B(H_B)π:A→B(HB​) be a unital ∗*∗-homomorphism with π(ai)=bi\pi(a_i)=b_iπ(ai​)=bi​. Write τL(X)=Tr⁡X/NL\tau_L(X)=\operatorname{Tr}X/N_LτL​(X)=TrX/NL​ for the normalized trace, ∥X∥2,L=τL(X∗X)\|X\|_{2,L}=\sqrt{\tau_L(X^*X)}∥X∥2,L​=τL​(X∗X)​, FtA\mathcal F^A_tFtA​ for the span of the identity and of all marked words ai1ϵ1⋯aiℓϵℓa_{i_1}^{\epsilon_1}\cdots a_{i_\ell}^{\epsilon_\ell}ai1​ϵ1​​⋯aiℓ​ϵℓ​​ with ℓ≤t\ell\le tℓ≤t and ϵj∈{1,∗}\epsilon_j\in\{1,*\}ϵj​∈{1,∗}, and drel∈N0∪{+∞}d_{\mathrm{rel}}\in\mathbb N_0\cup\{+\infty\}drel​∈N0​∪{+∞} for the relative distance (Definition 4.1).

Then for every integer D≥0D\ge0D≥0:

  1. the condition
2D<drel2D<d_{\mathrm{rel}}2D<drel​

is equivalent to

τB(π(X)∗π(Y))=τA(X∗Y)(X,Y∈FDA);\tau_B(\pi(X)^*\pi(Y))=\tau_A(X^*Y)\qquad(X,Y\in\mathcal F^A_D);τB​(π(X)∗π(Y))=τA​(X∗Y)(X,Y∈FDA​);
  1. in particular, if 2D<drel2D<d_{\mathrm{rel}}2D<drel​, then π\piπ is an isometry from FDA\mathcal F^A_DFDA​ onto FDB=π(FDA)\mathcal F^B_D=\pi(\mathcal F^A_D)FDB​=π(FDA​): ∥π(X)∥2,B=∥X∥2,A\|\pi(X)\|_{2,B}=\|X\|_{2,A}∥π(X)∥2,B​=∥X∥2,A​ for every X∈FDAX\in\mathcal F^A_DX∈FDA​, and π\piπ is injective on FDA\mathcal F^A_DFDA​.

The criterion says exactly how far a homomorphism, which always transports polynomials, also transports the normalized operator states: every degree-DDD polynomial state of the source is carried to the corresponding target state with its normalization intact precisely when 2D2D2D is below the relative distance. It is the algebraic basis of homomorphic polynomial transduction by relative decoding.

Differences from the source:

  • generalization: Hilbert spaces H_A, H_B with N_L = dim H_L ≥ 1 (τ_L divides by N_L) → index types nA, nB may be empty, where Lean's x/0 = 0 gives τ_L ≡ 0; reason: covers only extra degenerate instances where the source's τ_L is undefined; on nonempty index types it is the source's statement verbatim
  • encoding: A = C∗(I_A, a₁,…,a_s) ⊆ B(H_A), π : A ↠ B unital ∗-homomorphism with π(aᵢ) = bᵢ → A = StarAlgebra.adjoin ℂ (Set.range a) in Matrix nA nA ℂ; π : A →⋆ₐ[ℂ] Matrix nB nB ℂ with π (gen a i) = b i; reason: in finite dimension the generated ∗-subalgebra is norm closed (App. E, p.85); the range of π is the ∗-subalgebra generated by the bᵢ, i.e. B, so 'onto B' is automatic
  • encoding: marked words a_{i₁}^{ϵ₁}⋯a_{i_ℓ}^{ϵ_ℓ}, ϵⱼ ∈ {1, ∗}, empty word = I_A; 𝓕ᴬ_t their span for ℓ ≤ t → words are List (Fin s × Bool) with true = adjoint, evaluated by wordEval; 𝓕ᴬ_t = markedSpace a t, a Submodule ℂ of A; reason: Lean convention; same spaces
  • encoding: d_rel ∈ ℕ₀ ∪ {+∞}, empty minimum +∞ → relDist a π : ℕ∞ as sInf of the image in ℕ∞, sInf ∅ = ⊤; reason: Lean convention; same values
  • encoding: π is an isometry from 𝓕ᴬ_D onto 𝓕ᴮ_D → no separate surjectivity clause; 𝓕ᴮ_D is the image π(𝓕ᴬ_D); reason: (43) defines 𝓕ᴮ_D = π(𝓕ᴬ_D), so 'onto' holds by definition
  • reading: 'In particular π is an isometry from 𝓕ᴬ_D onto 𝓕ᴮ_D' → the clause is stated under 2D < d_rel as norm preservation and injectivity on 𝓕ᴬ_D; reason: the sentence after the proof ('In particular, π is injective on 𝓕ᴬ_D') and App. A.4 ((358) and 'therefore π is injective on V', applied to V = 𝓕ᴬ_D) give these two forms; this is the stronger of the readings
Preamble
import Mathlib
import Definitions.Def_LIDT_MIPStarRE_Quantum_FiniteMatrix_NormalizedTrace
import Definitions.Def_RelDecoding_markedSpace
import Definitions.Def_RelDecoding_norm2
import Definitions.Def_RelDecoding_relDist

set_option autoImplicit false
Formal statement
namespace RelDecoding

open LIDT.MIPStarRE.Quantum

/-- **Proposition 4.2 (Sharp degree–distance criterion).** For an integer `D ≥ 0`, the condition
`2D < d_rel` (47) is equivalent to `τ_B(π(X)∗π(Y)) = τ_A(X∗Y)` for all `X, Y ∈ 𝓕ᴬ_D` (48). In
particular, when `2D < d_rel`, `π` is an isometry from `𝓕ᴬ_D` onto `𝓕ᴮ_D = π(𝓕ᴬ_D)`:
`∥π(X)∥_{2,B} = ∥X∥_{2,A}` for `X ∈ 𝓕ᴬ_D`, and `π` is injective on `𝓕ᴬ_D`. Shang, Stilck França,
*From Simple Sources to Quantum Advantage: Homomorphic Polynomial Transduction via Relative
Decoding*, arXiv:2609.35101 (held version, sha256 d2be7859…), Proposition 4.2, p.18 (and the
sentence after its proof: "In particular, π is injective on 𝓕ᴬ_D").

**Formalization Note.** `A = C∗(I_A, a₁, …, a_s)` is `StarAlgebra.adjoin ℂ (Set.range a)` inside
`Matrix nA nA ℂ` (in finite dimension the generated ∗-subalgebra is the generated C∗-algebra);
`π` is any unital ∗-homomorphism from `A` into `Matrix nB nB ℂ` with `π(aᵢ) = bᵢ`, whose range is
`B = C∗(I_B, b)`; `τ_L = Tr / N_L` (`normalizedTrace`), `∥X∥_{2,L} = √(τ_L(X∗X))` (`norm2`);
`𝓕ᴬ_D` is the span of marked words of length at most `D` (`markedSpace`); `d_rel ∈ ℕ∞` with `+∞`
for the empty minimum (`relDist`). "Onto `𝓕ᴮ_D`" holds by the definition `𝓕ᴮ_D = π(𝓕ᴬ_D)`. The
index types may be empty (then `τ ≡ 0` by Lean's `x / 0 = 0`). -/
theorem proposition_4_2 {nA nB : Type*} [Fintype nA] [DecidableEq nA] [Fintype nB]
    [DecidableEq nB] {s : ℕ} (a : Fin s → Matrix nA nA ℂ) (b : Fin s → Matrix nB nB ℂ)
    (π : genAlg a →⋆ₐ[ℂ] Matrix nB nB ℂ) (hπ : ∀ i, π (gen a i) = b i) (D : ℕ) :
    ((((2 * D : ℕ) : ℕ∞) < relDist a π ↔
        ∀ X ∈ markedSpace a D, ∀ Y ∈ markedSpace a D,
          normalizedTrace (star (π X) * π Y) =
            normalizedTrace (star (X : Matrix nA nA ℂ) * (Y : Matrix nA nA ℂ))) ∧
      (((2 * D : ℕ) : ℕ∞) < relDist a π →
        (∀ X ∈ markedSpace a D, norm2 (π X) = norm2 (X : Matrix nA nA ℂ)) ∧
          Set.InjOn π (markedSpace a D : Set (genAlg a)))) := by sorry

end RelDecoding
Source
Shang, Stilck França, From Simple Sources to Quantum Advantage: Homomorphic Polynomial Transduction via Relative Decoding, arXiv:2609.35101 (held version, sha256 d2be7859…), Proposition 4.2, eqs. (47)–(48), p.18 (pdf_page 18), with the sentence after its proof (p.18) and App. A.4 (p.68)
Human review
  • Endorsed by Shuze Chen · Nov 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 8, 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