Lemma 8 — self-dual completion: dimension count, self-duality and short vectors of
ProvedMetricSelfDualCompletion.Completion.lemma_8This is Lemma 8 of the paper, under the construction of §3.1.
Let and be integers, let be a self-dual code (the host) with , let be the repetition embedding , and let be any code. Put
Then and is self-dual. Moreover is self-orthogonal, , and
Consequently, if , then
This is the core of the completion: removing from the host exactly the dimensions not orthogonal to and adding back yields a self-dual code, and the only short words outside are the embedded codewords. is the CSS check space of the paper's quantum application.
Formalization Note The dimension identity is stated both as (natural subtraction) and as , which excludes a truncated reading. The minimum in (11) is stated as: some has weight , and every such has weight . Distances are in . The hypothesis makes the padding well-typed.
Differences from the source:
- generalization: the host "constructed above" by Proposition 7 with (self-dual, , , ) → any self-dual with ; reason: the lemma's argument uses only self-duality and ; hosts from Proposition 7 are instances, so it specializes to the source.
- encoding: "τ(x) = (x, x, 0^{N−2m})" with "N ⩾ d(M) > 2H ⩾ 2m" → hypothesis ; reason: excludes only cases where the padding is undefined (e.g. , , , where the text's fails); every host of §3.1 satisfies it.
- encoding: "H ∈ ℤ, H ⩾ 2m" → ; reason: ; same instances.
- encoding: "dim K = N/2 − dim C" → also ; reason: rules out natural-subtraction truncation; same content over .
- encoding: "min_{v∈K⊥∖K} wt(v) = 2d(C)" → a minimizer of weight exists and all such weigh at least ; reason: the meaning of an attained minimum.
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 8 (Self-dual completion), printed p. 7 / PDF p. 9, under the construction of §3.1: a
self-dual host `M ⩽ F₂ᴺ` with `d(M) > 2H`, `H ⩾ 2m`, the repetition embedding
`τ(x) = (x, x, 0^{N−2m})` (well-typed: `2m ⩽ N`), `K = M ∩ τ(C)^⊥`, `A = K + τ(C)`. Then
`dim K = N/2 − dim C`, `A` is self-dual, `K` is self-orthogonal, `d(K) > 2H`,
`{v ∈ K^⊥ ∖ K : wt(v) ⩽ H} = τ(C ∖ {0})` (10), and for `C ≠ 0`,
`min_{v ∈ K^⊥ ∖ K} wt(v) = 2 d(C)` (11). -/
theorem lemma_8 (m H N : ℕ) (M : Submodule (ZMod 2) (Fin N → ZMod 2)) (hM : IsSelfDual M)
(hdM : ((2 * H : ℕ) : ℕ∞) < minDistCode M) (hH : 2 * m ≤ H) (hN : 2 * m ≤ N)
(C : Submodule (ZMod 2) (Fin m → ZMod 2)) :
Module.finrank (ZMod 2) (completionK M C) = N / 2 - Module.finrank (ZMod 2) C ∧
2 * Module.finrank (ZMod 2) (completionK M C) + 2 * Module.finrank (ZMod 2) C = N ∧
IsSelfDual (completionA M C) ∧
IsSelfOrthogonal (completionK M C) ∧
((2 * H : ℕ) : ℕ∞) < minDistCode (completionK M C) ∧
{v | v ∈ codeDual (completionK M C) ∧ v ∉ completionK M C ∧ hammingNorm v ≤ H} =
repEmbed m N '' {x | x ∈ C ∧ x ≠ 0} ∧
(C ≠ ⊥ →
(∃ v ∈ codeDual (completionK M C), v ∉ completionK M C ∧
(hammingNorm v : ℕ∞) = 2 * minDistCode C) ∧
∀ v ∈ codeDual (completionK M C), v ∉ completionK M C →
2 * minDistCode C ≤ (hammingNorm v : ℕ∞)) := by sorry
end MetricSelfDualCompletion.Completion
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.