Lemma 12 — all-ones normalization of a binary code
ProvedMetricSelfDualCompletion.Completion.lemma_12This is Lemma 12 of the paper.
For every binary linear code with one can efficiently construct a code such that
Here is the all-ones vector and the minimum distance, . "Efficiently construct" means: one fixed deterministic polynomial-time algorithm maps every basis of to a basis of .
The lemma puts the all-ones word into a code while keeping the smaller of its primal and dual distances; it is the first step of the passage from dual-good codes to self-dual codes (Proposition 14).
Formalization Note The algorithm is a PvsNP.PolyTimeComputable function; its input is a row basis of encoded with its dimensions in unary, its output a row basis of . and are included.
Differences from the source:
- encoding: "one can efficiently construct" → a fixed
PvsNP.PolyTimeComputablefunction, chosen before and , mapping an encoded row basis of (dimensions in unary) to an encoded row basis of ; reason: codes are specified by bases (§2.1) and the machine model measures input length; no instance changes. - reading: "construct a code " from → one per , reached from every row basis of ; reason: is constructed from the code ; the stronger reading (the output may not depend on which basis of is given).
import Mathlib import Definitions.Def_QAlgorithms_Defs_TensorCode import Definitions.Def_PvsNP import Definitions.Def_MetricSelfDualCompletion_Completion_Codes import Definitions.Def_MetricSelfDualCompletion_Completion_Encoding
namespace MetricSelfDualCompletion.Completion
open QAlgorithms
/-- Lemma 12 (All-ones normalization), printed p. 10 / PDF p. 12. For every code `D ⩽ F₂ⁿ`,
`n ⩾ 1`, there is a code `E ⩽ F₂^{2n}` with `dim E = n`, `1_{2n} ∈ E` and
`min{d(E), d(E^⊥)} ⩾ min{d(D), d(D^⊥)}`, and one fixed deterministic polynomial-time machine maps
every row basis of `D` to a row basis of `E`. -/
theorem lemma_12 :
∃ f : List Bool → List Bool, PvsNP.PolyTimeComputable f ∧
∀ (n : ℕ), 1 ≤ n → ∀ D : Submodule (ZMod 2) (Fin n → ZMod 2),
∃ E : Submodule (ZMod 2) (Fin (2 * n) → ZMod 2),
Module.finrank (ZMod 2) E = n ∧ allOnes (2 * n) ∈ E ∧
min (minDistCode D) (minDistCode (codeDual D)) ≤
min (minDistCode E) (minDistCode (codeDual E)) ∧
∀ (k : ℕ) (B : Fin k → Fin n → ZMod 2), IsRowBasis B D →
∃ (r : ℕ) (B' : Fin r → Fin (2 * n) → ZMod 2),
IsRowBasis B' E ∧ f (encMatrix B) = encMatrix B' := by sorry
end MetricSelfDualCompletion.Completion
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.