The induced punctured tensor graph and its local coordinate maps
DefinitionQuantumCupGates644_ConstantWeight_Supplement_puncturedFor integers n and t, a layer-i vertex is a direction-i column with high coordinates before i and low coordinates after i. The graph is the induced subgraph of the column-intersection graph: two vertices in different ordered layers are adjacent exactly when their fixed coordinates agree wherever both are specified. The disjoint puncture has pieces
The definitions retain actual intersection points, coordinate-deletion endpoints, and the restriction map from the entire t-fold tensor code to the graph edges. At a layer-i vertex, the local image is the given code C_i evaluated at every incident intersection coordinate. Its puncture is the second half at layer 1, the first half at layer t, and all coordinates in an interior layer. The graph, these sets and the coordinate maps are all independent of the codes.
This supplies the concrete objects of Claims 4.2–4.3 and Theorem 4.1. Their geometric bijection and restriction isomorphism are not assumed by any definition. The case n=0 is retained.
import Definitions.Def_QuantumCupGates644_ConstantWeight_Supplement_tanner
import Definitions.Def_QuantumCupGates644_ConstantWeight_Supplement_decoder
noncomputable section
namespace QuantumCupGates644.ConstantWeight.Supplement
open scoped BigOperators
open Classical
/-- A direction-i column with high coordinates before i and low ones after i.
This type is empty at n=0,t≥2, exactly as in the paper. -/
abbrev ColumnVertex (n t : ℕ) :=
(i : Fin t) × ({k : Fin t // k ≠ i} → Fin n)
def columnCoordinate {n t : ℕ} (v : ColumnVertex n t)
(k : Fin t) (h : k ≠ v.1) : Fin (2*n) :=
⟨(v.2 ⟨k,h⟩).val + if k < v.1 then n else 0, by
have := (v.2 ⟨k,h⟩).isLt
split <;> omega⟩
/-- Edges of the induced graph Γ-bar[V], before relabelling by Fin. -/
abbrev ColumnEdge (n t : ℕ) :=
{vw : ColumnVertex n t × ColumnVertex n t // vw.1.1 < vw.2.1 ∧
∀ (k : Fin t) (h₁ : k ≠ vw.1.1) (h₂ : k ≠ vw.2.1),
columnCoordinate vw.1 k h₁ = columnCoordinate vw.2 k h₂}
def puncturedGraph (n t : ℕ) : Graph where
nv := Fintype.card (ColumnVertex n t)
ne := Fintype.card (ColumnEdge n t)
tail e := Fintype.equivFin _ ((Fintype.equivFin (ColumnEdge n t)).symm e).val.1
head e := Fintype.equivFin _ ((Fintype.equivFin (ColumnEdge n t)).symm e).val.2
distinct e := by
intro h
have hv := (Fintype.equivFin (ColumnVertex n t)).injective h
have hl := ((Fintype.equivFin (ColumnEdge n t)).symm e).property.1
have := congrArg (fun v : ColumnVertex n t => v.1) hv
exact (ne_of_lt hl) this
/-- The intersection point of two adjacent axis-parallel columns. -/
def edgePoint {n t : ℕ} (e : ColumnEdge n t) (k : Fin t) : Fin (2*n) :=
if h : k = e.val.1.1 then columnCoordinate e.val.2 k (by
have := e.property.1
intro he
exact (ne_of_lt this) (h.symm.trans he))
else columnCoordinate e.val.1 k h
/-- The disjoint puncture E = disjoint-union E_i, with high coordinates
through position i and low coordinates after i. -/
abbrev PuncturePoint (n t : ℕ) := Fin (t-1) × (Fin t → Fin n)
def puncturePoint {n t : ℕ} (e : PuncturePoint n t) : Fin t → Fin (2*n) :=
fun k => ⟨(e.2 k).val + if k.val ≤ e.1.val then n else 0, by
have := (e.2 k).isLt
split <;> omega⟩
def deletedColumn {n t : ℕ} (e : PuncturePoint n t) (i : Fin t) : ColumnVertex n t :=
⟨i,fun k => e.2 k.val⟩
variable {F : Type} [Field F] {n t : ℕ}
def restrictE : ((Fin t → Fin (2*n)) → F) →ₗ[F] (PuncturePoint n t → F) :=
LinearMap.funLeft F F puncturePoint
def vertexLayer (v : Fin (puncturedGraph n t).nv) : Fin t :=
((Fintype.equivFin (ColumnVertex n t)).symm v).1
def localCoordinates (v : Fin (puncturedGraph n t).nv)
(e : (puncturedGraph n t).incident v) : Fin (2*n) :=
edgePoint ((Fintype.equivFin (ColumnEdge n t)).symm e.val) (vertexLayer v)
def localPuncture (v : Fin (puncturedGraph n t).nv) : Finset (Fin (2*n)) :=
Finset.univ.filter (fun a =>
if (vertexLayer v).val = 0 then n ≤ a.val
else if (vertexLayer v).val + 1 = t then a.val < n else True)
/-- The local image is exactly the given column code evaluated on all
incident intersection coordinates. The graph and this map contain no C. -/
def puncturedSystem (C : Fin t → Code F (Fin (2*n))) :
LocalSystem F (puncturedGraph n t) :=
LocalSystem.ofCodes (fun v => (C (vertexLayer v)).map
(LinearMap.funLeft F F (localCoordinates v)))
def restrictGraph : ((Fin t → Fin (2*n)) → F) →ₗ[F]
(Fin (puncturedGraph n t).ne → F) :=
LinearMap.funLeft F F (fun e => edgePoint ((Fintype.equivFin (ColumnEdge n t)).symm e))
def Graph.Bipartite (G : Graph) : Prop :=
∃ side : Fin G.nv → Bool, ∀ e, side (G.tail e) ≠ side (G.head e)
end QuantumCupGates644.ConstantWeight.Supplement