§3.2, equations (13)–(14) — every source coset: distance doubles and short words are the embedded coset
ProvedMetricSelfDualCompletion.Completion.eq_13_14coding-theoryp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1self-dual-codes
These are equations (13) and (14) of §3.2 of the paper, under the construction of §3.1 (as in Lemma 8).
Let , , let be self-dual with , , any code, and . Then for every ,
and
Here .
With , (14) is clause (iii) of the main theorem, and (13) is its clause (ii); for general , (14) identifies the short words of every coset of that meets the image of .
Formalization Note Membership is written , and as the image of . The hypothesis makes well-typed.
Differences from the source:
- generalization: the host of §3.1 built by Proposition 7 → any self-dual with ; reason: the argument uses only these two properties; Proposition 7 hosts 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; every host of §3.1 satisfies it.
- encoding: "H ∈ ℤ" → ; reason: ; same instances.
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
/-- §3.2, equations (13)–(14), printed p. 8 / PDF p. 10, under the construction of §3.1 (as in
Lemma 8): for every `y ∈ F₂ᵐ`, `dist(τ(y), A) = 2 dist(y, C)` (13) and
`{p ∈ τ(y) + A : wt(p) ⩽ H} = τ(y + C)` (14). -/
theorem eq_13_14 (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)) (y : Fin m → ZMod 2) :
distToCode (repEmbed m N y) (completionA M C) = 2 * distToCode y C ∧
{p | p - repEmbed m N y ∈ completionA M C ∧ hammingNorm p ≤ H} =
repEmbed m N '' {x | x - y ∈ C} := by sorry
end MetricSelfDualCompletion.Completion
Source
Rafail Ostrovsky, STOC 2027 submission #5 (October 2026), §3.2, equations (13)–(14), printed p. 8 (PDF p. 10). 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.