Theorem 4.1 — full punctured tensor Tanner construction
OpenQuantumCupGates644.ConstantWeight.Supplement.theorem_4_1For every n≥0 and t≥2, the actual graph Γ(n,t) is bipartite, has maximum degree at most 2n, and has code-independent local coordinate bijections. For every finite field F and every tuple C_i⊆F^{2n} with dimensions k_i≤n and distance bounds d_i>n, the specified local systems yield
At a layer-i vertex, the local code is exactly the corresponding puncturing of C_i. The puncture and coordinate bijection are chosen before any codes: the second half at the first layer, the first half at the last layer, and all coordinates at interior layers. If both half-punctures of C_i have radius-ρ_i time-T_i decoders, the Tanner code has
The running time is the exact compositional elementary-operation bound; no coefficient is replaced by unspecified overhead. The empty n=0 case and zero-dimensional codes are retained.
Differences from the source:
- encoding: one-based finite coordinate sets and quotient logical spaces → Fin labels and full-preimage logical subspaces; reason: the relabellings are bijective and the published CSS convention represents the same quotients
- encoding: exact decoder time (t−1)n^(t−1)∑T_i → the same bound for operational circuits whose constituent program clocks are T_i; reason: coordinate wiring has no arithmetic cost and circuit composition sums actual primitive clocks; no exact Turing simulation claim is made
- generalization: integer minimum-distance parameters → nonnegative real lower bounds for constituent-code distances; reason: substituting the source minimum distances recovers the source bound; every factor d_i minus n is positive and monotone on the stated domain
import Definitions.Def_QuantumCupGates644_ConstantWeight_Supplement_punctured
namespace QuantumCupGates644.ConstantWeight.Supplement
open scoped BigOperators
open Classical
theorem theorem_4_1 (n t : ℕ) (ht : 2 ≤ t) :
(puncturedGraph n t).Bipartite ∧
(puncturedGraph n t).DegreeAtMost (2*n) ∧
(puncturedGraph n t).ne = (t-1)*n^t ∧
(∀ v : Fin (puncturedGraph n t).nv,
∃ b : localPuncture v ≃ (puncturedGraph n t).incident v,
∀ a, localCoordinates v (b a) = a.val) ∧
∀ (F : Type) [Field F] [Fintype F]
(C : Fin t → Code F (Fin (2*n))) (d : Fin t → NNReal),
(∀ i, Module.finrank F (C i) ≤ n) →
(∀ i, DistanceAtLeast (C i) (d i)) → (∀ i, (n : ℝ) < d i) →
Module.finrank F (puncturedSystem C).tanner = ∏ i, Module.finrank F (C i) ∧
DistanceAtLeast (puncturedSystem C).tanner (∏ i, ((d i : ℝ)-n)) ∧
(∀ v, (puncturedSystem C).localCode v =
(C (vertexLayer v)).map (LinearMap.funLeft F F (localCoordinates v))) ∧
∀ (ρ : Fin t → NNReal) (T : Fin t → ℕ),
(∀ i b, DecodesClassical (halfPuncture (C i) b) (ρ i) (T i)) →
DecodesClassical (puncturedSystem C).tanner (∏ i, (ρ i : ℝ))
((t-1)*n^(t-1)*(∑ i, T i)) := by sorry
end QuantumCupGates644.ConstantWeight.Supplement