Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 8 — self-dual completion: dimension count, self-duality and short vectors of K⊥∖KK^\perp\setminus KK⊥∖K

Proved
MetricSelfDualCompletion.Completion.lemma_8

by mikedeng1 · Nov 8, 2026 · Mathlib 0df444a (Lean v4.33.1)

coding-theoryp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-codesself-dual-codes

This is Lemma 8 of the paper, under the construction of §3.1.

Let m≥0m\ge0m≥0 and H≥2mH\ge 2mH≥2m be integers, let M≤F2NM\le\mathbb F_2^NM≤F2N​ be a self-dual code (the host) with d(M)>2Hd(M)>2Hd(M)>2H, let τ(x)=(x,x,0N−2m)\tau(x)=(x,x,0^{N-2m})τ(x)=(x,x,0N−2m) be the repetition embedding F2m→F2N\mathbb F_2^m\to\mathbb F_2^NF2m​→F2N​, and let C≤F2mC\le\mathbb F_2^mC≤F2m​ be any code. Put

K=M∩τ(C)⊥,A=K+τ(C).K=M\cap\tau(C)^\perp,\qquad A=K+\tau(C).K=M∩τ(C)⊥,A=K+τ(C).

Then dim⁡K=N/2−dim⁡C\dim K=N/2-\dim CdimK=N/2−dimC and AAA is self-dual. Moreover KKK is self-orthogonal, d(K)>2Hd(K)>2Hd(K)>2H, and

{v∈K⊥∖K: wt(v)≤H}=τ(C∖{0}).(10)\{v\in K^\perp\setminus K:\ \mathrm{wt}(v)\le H\}=\tau(C\setminus\{0\}).\tag{10}{v∈K⊥∖K: wt(v)≤H}=τ(C∖{0}).(10)

Consequently, if C≠0C\ne0C=0, then

min⁡v∈K⊥∖Kwt(v)=2d(C).(11)\min_{v\in K^\perp\setminus K}\mathrm{wt}(v)=2d(C).\tag{11}v∈K⊥∖Kmin​wt(v)=2d(C).(11)

This is the core of the completion: removing from the host exactly the dim⁡C\dim CdimC dimensions not orthogonal to τ(C)\tau(C)τ(C) and adding τ(C)\tau(C)τ(C) back yields a self-dual code, and the only short words outside KKK are the embedded codewords. KKK is the CSS check space of the paper's quantum application.

Formalization Note The dimension identity is stated both as dim⁡K=N/2−dim⁡C\dim K=N/2-\dim CdimK=N/2−dimC (natural subtraction) and as 2dim⁡K+2dim⁡C=N2\dim K+2\dim C=N2dimK+2dimC=N, which excludes a truncated reading. The minimum in (11) is stated as: some v∈K⊥∖Kv\in K^\perp\setminus Kv∈K⊥∖K has weight 2d(C)2d(C)2d(C), and every such vvv has weight ≥2d(C)\ge 2d(C)≥2d(C). Distances are in N∪{∞}\mathbb N\cup\{\infty\}N∪{∞}. The hypothesis 2m≤N2m\le N2m≤N makes the padding 0N−2m0^{N-2m}0N−2m well-typed.

Differences from the source:

  • generalization: the host MMM "constructed above" by Proposition 7 with Δ=2H+1\Delta=2H+1Δ=2H+1 (self-dual, d(M)>2Hd(M)>2Hd(M)>2H, 4∣N4\mid N4∣N, N=Θ(H)N=\Theta(H)N=Θ(H)) → any self-dual MMM with d(M)>2Hd(M)>2Hd(M)>2H; reason: the lemma's argument uses only self-duality and d(M)>2Hd(M)>2Hd(M)>2H; 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 2m≤N2m\le N2m≤N; reason: excludes only cases where the padding 0N−2m0^{N-2m}0N−2m is undefined (e.g. N=0N=0N=0, M=0M=0M=0, m≥1m\ge1m≥1, where the text's N≥d(M)N\ge d(M)N≥d(M) fails); every host of §3.1 satisfies it.
  • encoding: "H ∈ ℤ, H ⩾ 2m" → H∈NH\in\mathbb NH∈N; reason: H≥2m≥0H\ge 2m\ge0H≥2m≥0; same instances.
  • encoding: "dim K = N/2 − dim C" → also 2dim⁡K+2dim⁡C=N2\dim K+2\dim C=N2dimK+2dimC=N; reason: rules out natural-subtraction truncation; same content over Z\mathbb ZZ.
  • encoding: "min_{v∈K⊥∖K} wt(v) = 2d(C)" → a minimizer of weight 2d(C)2d(C)2d(C) exists and all such vvv weigh at least 2d(C)2d(C)2d(C); reason: the meaning of an attained minimum.
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 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
Source
Rafail Ostrovsky, STOC 2027 submission #5 (October 2026), §3.1, Lemma 8 (equations (10)–(11)), printed p. 7 (PDF p. 9); construction preamble printed pp. 6–7 (PDF pp. 8–9). https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/5.pdf
Human review
  • Endorsed by Shuze Chen · Nov 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Nov 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me