Lemma 13 — prefix-sum self-dual construction
ProvedMetricSelfDualCompletion.Completion.lemma_13coding-theoryp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1self-dual-codes
This is Lemma 13 of the paper.
Let and let be a binary linear code containing the all-ones vector . Let be the prefix-sum map, with , and . Then
- is an invertible linear map;
- for all and ,
- is self-dual, ;
- (with and ).
This converts a code with the all-ones word and good primal and dual distances into a self-dual code of twice the length.
Formalization Note Item 1 is a linear equivalence from the subspace onto that agrees with ; is the restriction of a linear map on (see the Codes definition for the 0-based coordinate layout). Distances are in .
Differences from the source:
- encoding: "Φ : E × E⊥ → P is an invertible linear map" → a linear equivalence whose values are those of ; reason: Lean form of "invertible linear map onto "; same content.
- encoding: 1-based coordinates, pair at positions → 0-based, pair at positions ; reason:
Fin nindexing; same map.
Preamble
import Mathlib import Definitions.Def_QAlgorithms_Defs_TensorCode import Definitions.Def_PvsNP import Definitions.Def_MetricSelfDualCompletion_Completion_Codes import Definitions.Def_MetricSelfDualCompletion_Completion_Encoding
Formal statement
namespace MetricSelfDualCompletion.Completion
open QAlgorithms
/-- Lemma 13 (Prefix-sum self-dual construction), printed p. 11 / PDF p. 13. For `n ⩾ 1` and a
code `E ⩽ F₂ⁿ` containing `1ₙ`, the prefix-sum map `Φ` restricted to `E × E^⊥` is a linear
isomorphism onto `P = Φ(E, E^⊥)`; `Φ(c, w)^⊤ Φ(c', w') = c^⊤ w' + w^⊤ c'` for all
`c, c' ∈ E`, `w, w' ∈ E^⊥`; `P` is self-dual and `d(P) ⩾ min{d(E^⊥), 2 d(E)}`. -/
theorem lemma_13 (n : ℕ) (hn : 1 ≤ n) (E : Submodule (ZMod 2) (Fin n → ZMod 2))
(hE : allOnes n ∈ E) :
(∃ e : (E.prod (codeDual E)) ≃ₗ[ZMod 2] (prefixSumCode E),
∀ x : E.prod (codeDual E),
((e x : Fin (2 * n) → ZMod 2)) =
prefixSumMap n (x : (Fin n → ZMod 2) × (Fin n → ZMod 2))) ∧
(∀ c ∈ E, ∀ c' ∈ E, ∀ w ∈ codeDual E, ∀ w' ∈ codeDual E,
prefixSumMap n (c, w) ⬝ᵥ prefixSumMap n (c', w') = c ⬝ᵥ w' + w ⬝ᵥ c') ∧
IsSelfDual (prefixSumCode E) ∧
min (minDistCode (codeDual E)) (2 * minDistCode E) ≤ minDistCode (prefixSumCode E) := by sorry
end MetricSelfDualCompletion.Completion
Source
Rafail Ostrovsky, STOC 2027 submission #5 (October 2026), §5.2, Lemma 13, printed p. 11 (PDF p. 13). https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/5.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.