Proposition 4.2 — sharp degree–distance criterion: iff preserves on
ProvedRelDecoding.proposition_4_2Let and be finite-dimensional Hilbert spaces, let be operators on and operators on (no further assumption on them), and let be the unital -algebra they generate. Let be a unital -homomorphism with . Write for the normalized trace, , for the span of the identity and of all marked words with and , and for the relative distance (Definition 4.1).
Then for every integer :
- the condition
is equivalent to
- in particular, if , then is an isometry from onto : for every , and is injective on .
The criterion says exactly how far a homomorphism, which always transports polynomials, also transports the normalized operator states: every degree- polynomial state of the source is carried to the corresponding target state with its normalization intact precisely when 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
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
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.