Coordinate distances and
DefinitionRelDecoding_Supplement_coordDistoperator-algebrasp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-informationrelative-decoding
Let and be subspaces (relation codes) and write for the Hamming weight of , the number of its nonzero coordinates.
- The coordinate relative distance is
- The ordinary distance of the target relation code is
Both take values in with the empty minimum equal to ; in particular gives (eqs. (13), (18), (88), (93)). For Pauli sources is the coordinate formula for the intrinsic relative distance, and is the distance governing ordinary (relation-free) decoding.
Formalization Note Values lie in ℕ∞ and sInf ∅ = ⊤; hammingNorm is Mathlib's Hamming weight.
Definition code
import Mathlib
set_option autoImplicit false
namespace RelDecoding.Supplement
/-- The **coordinate relative distance** `d_{A→B} := min{|c| : c ∈ K_B \ K_A}`, with `|c|` the
Hamming weight and the empty minimum `+∞` (so `K_A = K_B` gives `d_{A→B} = +∞`). Shang, Stilck
França, *From Simple Sources to Quantum Advantage: Homomorphic Polynomial Transduction via
Relative Decoding*, arXiv:2609.35101 (held version, sha256 d2be7859…), eq. (13), p.9, and eq. (88),
p.24.
**Formalization Note.** The value lies in `ℕ∞` and `sInf ∅ = ⊤`. `hammingNorm c` is the number of
nonzero coordinates of `c`. The kernels are given as subspaces of `K^s`. -/
noncomputable def coordDist {K : Type*} [Field K] [DecidableEq K] {s : ℕ}
(KA KB : Submodule K (Fin s → K)) : ℕ∞ :=
sInf ((fun c : Fin s → K => (hammingNorm c : ℕ∞)) '' ((KB : Set (Fin s → K)) \ KA))
/-- The **ordinary distance** of the target relation code `d_B := min{|c| : 0 ≠ c ∈ K_B}`, with
the empty minimum `+∞`. Shang, Stilck França, arXiv:2609.35101 (held version, sha256 d2be7859…),
eq. (18), p.9, and eq. (93), p.24.
**Formalization Note.** The value lies in `ℕ∞` and `sInf ∅ = ⊤`. -/
noncomputable def ordDist {K : Type*} [Field K] [DecidableEq K] {s : ℕ}
(KB : Submodule K (Fin s → K)) : ℕ∞ :=
sInf ((fun c : Fin s → K => (hammingNorm c : ℕ∞)) '' {c | c ∈ KB ∧ c ≠ 0})
end RelDecoding.Supplement
Source
Shang, Stilck França, From Simple Sources to Quantum Advantage: Homomorphic Polynomial Transduction via Relative Decoding, arXiv:2609.35101 (held version, sha256 d2be7859…), eq. (13), p.9; eq. (18), p.9; eq. (88), p.24; eq. (93), p.24 (pdf_pages 9, 24)