Directed Tanner systems with specified generator bases
DefinitionQuantumCupGates644_ConstantWeight_Supplement_tannerLet Γ be a finite directed graph and F a field. A system of local codes assigns an F-linear code to each incident-edge set E(v), together with a basis that specifies its injective generator matrix. The associated Tanner code is
The degree-zero basis is the disjoint union of the local generator bases. The differential sends local vectors to the difference of their edge values at the tail and head. Local dualization acts on the local images and chooses bases for the resulting dual spaces. Schur multiplication uses the published classical-code operation. The multiplication and extendability conditions are separate predicates.
This layer supplies the exact graph and local-code data used by the transformations; it assumes no distance, gate or decoder guarantee. Endpoints are distinct. Edge labels permit parallel edges, which do not change the incidence-counting arguments.
import Definitions.Def_QuantumCupGates644_ConstantWeight_classical_codes
noncomputable section
namespace QuantumCupGates644.ConstantWeight.Supplement
open scoped BigOperators
open Classical
/-- A finite directed graph; parallel edges are harmless. Degree counts both
incoming and outgoing edges. Endpoints are distinct, as for the source graphs. -/
structure Graph where
nv : ℕ
ne : ℕ
tail : Fin ne → Fin nv
head : Fin ne → Fin nv
distinct : ∀ e, tail e ≠ head e
variable {F : Type} [Field F]
def Graph.incident (G : Graph) (v : Fin G.nv) : Finset (Fin G.ne) :=
Finset.univ.filter (fun e => G.tail e = v ∨ G.head e = v)
def Graph.DegreeAtMost (G : Graph) (Δ : ℕ) : Prop :=
∀ v, (G.incident v).card ≤ Δ
def Graph.LeftToRight (G : Graph) : Prop :=
∃ side : Fin G.nv → Bool, ∀ e, side (G.tail e) = false ∧ side (G.head e) = true
/-- Local images with their specified generator bases. No distance,
multiplication, extendability, or decoding assertion is bundled. -/
structure LocalSystem (F : Type) [Field F] (G : Graph) where
localCode : ∀ v : Fin G.nv, Code F (G.incident v)
basis : ∀ v, Module.Basis (Fin (Module.finrank F (localCode v))) F (localCode v)
variable {G : Graph}
def LocalSystem.tanner (S : LocalSystem F G) : Code F (Fin G.ne) :=
⨅ v : Fin G.nv, (S.localCode v).comap
(LinearMap.funLeft F F (Subtype.val : G.incident v → Fin G.ne))
def LocalSystem.ofCodes (C : ∀ v : Fin G.nv, Code F (G.incident v)) : LocalSystem F G :=
⟨C, fun v => Module.finBasis F (C v)⟩
def LocalSystem.dualSystem (S : LocalSystem F G) : LocalSystem F G :=
.ofCodes (fun v => dual (S.localCode v))
def LocalSystem.schurSystem (S T : LocalSystem F G) : LocalSystem F G :=
.ofCodes (fun v => schur (S.localCode v) (T.localCode v))
abbrev LocalSystem.ZeroBasis (S : LocalSystem F G) :=
(v : Fin G.nv) × Fin (Module.finrank F (S.localCode v))
/-- Generator matrix extended by zero away from its vertex. -/
def LocalSystem.coeff (S : LocalSystem F G) (a : S.ZeroBasis) (e : Fin G.ne) : F :=
if h : e ∈ G.incident a.1 then (S.basis a.1 a.2 : G.incident a.1 → F) ⟨e,h⟩ else 0
/-- Equation (5): tail minus head. -/
def LocalSystem.delta (S : LocalSystem F G) : Matrix (Fin G.ne) S.ZeroBasis F :=
fun e a => (if G.tail e = a.1 then S.coeff a e else 0) -
(if G.head e = a.1 then S.coeff a e else 0)
/-- The factors in A^(r), with the last local system dualized. -/
def factors {r : ℕ} (S : Fin r → LocalSystem F G) : Fin r → LocalSystem F G :=
fun j => if j.val + 1 = r then (S j).dualSystem else S j
/-- The source Schur product of the first r-1 local images. The r=1
empty product is included only to make the operation total. -/
def prefixProduct {r : ℕ} (S : Fin r → LocalSystem F G) (v : Fin G.nv) : Code F (G.incident v) :=
((List.ofFn S).take (r-1)).foldl (fun C T => schur C (T.localCode v))
(Submodule.span F {fun _ => 1})
def Multiplication {r : ℕ} (S : Fin r → LocalSystem F G) : Prop :=
∀ (v : Fin G.nv) (j : Fin r), j.val + 1 = r → prefixProduct S v ≤ (S j).localCode v
def AddressMultiplication {r : ℕ} (S : Fin r → LocalSystem F G)
(S₀ : LocalSystem F G) : Prop :=
∀ (v : Fin G.nv) (j : Fin r), j.val + 1 = r →
schur (S₀.localCode v) (prefixProduct S v) ≤ (S j).localCode v
def Extendable {r : ℕ} (S : Fin r → LocalSystem F G) (M : Finset (Fin G.ne)) : Prop :=
∀ j : Fin r, j.val + 1 < r → IsExtendable (S j).tanner M
end QuantumCupGates644.ConstantWeight.Supplement