Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Label matrix A=[w1⋯ws]A=[w_1\cdots w_s]A=[w1​⋯ws​], relation code KA=ker⁡AK_A=\ker AKA​=kerA and ordered products W(c)W(c)W(c)

Definition
RelDecoding_Supplement_labelKer

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

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

Let KKK be a field and let w1,…,wsw_1,\dots,w_sw1​,…,ws​ be labels of the marked generators, vectors in KκK^\kappaKκ for a finite coordinate set κ\kappaκ.

  1. The label matrix is A=[w1⋯ws]A=[w_1\cdots w_s]A=[w1​⋯ws​], the κ×s\kappa\times sκ×s matrix whose iii-th column is wiw_iwi​.
  2. The relation code is KA=ker⁡A={c∈Ks: ∑iciwi=0}K_A=\ker A=\{c\in K^s:\ \sum_i c_i w_i=0\}KA​=kerA={c∈Ks: ∑i​ci​wi​=0}.
  3. A label (x,z)∈Kn×Kn(x,z)\in K^n\times K^n(x,z)∈Kn×Kn is read as the column vector (x,z)∈K2n(x,z)\in K^{2n}(x,z)∈K2n, xxx-part first.
  4. For matrices a1,…,asa_1,\dots,a_sa1​,…,as​ and c∈(Z/q)sc\in(\mathbb Z/q)^sc∈(Z/q)s the ordered product is
W(c)=a1c1⋯ascs,W(c)=a_1^{c_1}\cdots a_s^{c_s},W(c)=a1c1​​⋯ascs​​,

with factors in increasing index order and exponents the representatives ci∈{0,…,q−1}c_i\in\{0,\dots,q-1\}ci​∈{0,…,q−1}.

These are the objects of eqs. (81)–(82), (153)–(154) and (254): KAK_AKA​ records which ordered products of the marked terms are scalar, and WL(c)=ζL(c)IW_L(c)=\zeta_L(c)IWL​(c)=ζL​(c)I for c∈KLc\in K_Lc∈KL​ defines their phases. Here K=F2K=\mathbb F_2K=F2​ for Pauli and Majorana labels and K=FpK=\mathbb F_pK=Fp​ for Weyl labels.

Formalization Note The kernel is LinearMap.ker of Matrix.mulVecLin. The empty ordered product is the identity.

Definition code
import Mathlib

set_option autoImplicit false

namespace RelDecoding.Supplement

/-- The **label matrix** `A = [w₁ ⋯ w_s]` whose `i`-th column is the label `wᵢ ∈ K^κ` of the
`i`-th marked generator. Shang, Stilck França, *From Simple Sources to Quantum Advantage:
Homomorphic Polynomial Transduction via Relative Decoding*, arXiv:2609.35101 (held version, sha256
d2be7859…), eqs. (81), (153), (254), pp.23, 35, 46.

**Formalization Note.** The field `K` is `ZMod 2` for Pauli and Majorana labels and `ZMod p` for
Weyl labels; the row index type `κ` is the label coordinate set. -/
def labelMatrix {K κ : Type*} {s : ℕ} (w : Fin s → κ → K) : Matrix κ (Fin s) K :=
  Matrix.of fun k i => w i k

/-- The **relation code** `K_A = ker A ⊆ K^s` of the label matrix `A = [w₁ ⋯ w_s]`: the vectors
`c` with `Σᵢ cᵢ wᵢ = 0`. Shang, Stilck França, arXiv:2609.35101 (held version, sha256 d2be7859…),
eqs. (81), (153), (254), pp.23, 35, 46. -/
def labelKer {K κ : Type*} [Field K] {s : ℕ} (w : Fin s → κ → K) : Submodule K (Fin s → K) :=
  LinearMap.ker (labelMatrix w).mulVecLin

/-- A label `(x, z) ∈ K^n × K^n` read as the column vector `(x, z) ∈ K^{2n}`, X-part first
(the coordinates `Fin n ⊕ Fin n`). Used for Pauli labels (`K = F₂`, eq. (77)) and Weyl labels
(`K = F_p`, eq. (226)). -/
def pairVec {K : Type*} {n : ℕ} (u : (Fin n → K) × (Fin n → K)) : Fin n ⊕ Fin n → K :=
  Sum.elim u.1 u.2

/-- The **ordered product** `W(c) = a₁^{c₁} ⋯ a_s^{c_s}` of a family of matrices `a₁, …, a_s`
for a label vector `c ∈ (ℤ/q)^s`, with factors in increasing index order and exponents the
representatives `cᵢ ∈ {0, …, q − 1}`. Shang, Stilck França, arXiv:2609.35101 (held version, sha256
d2be7859…), eqs. (82), (154), pp.23, 35 (with `q = 2`, so `cᵢ ∈ {0, 1}`).

**Formalization Note.** The empty product (`s = 0`) is the identity. -/
def orderedProd {N : Type*} [Fintype N] [DecidableEq N] {s q : ℕ}
    (a : Fin s → Matrix N N ℂ) (c : Fin s → ZMod q) : Matrix N N ℂ :=
  (List.ofFn fun i => a i ^ (c i).val).prod

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…), eqs. (81)–(82), p.23; (153)–(154), p.35; (254), p.46 (pdf_pages 23, 35, 46)

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