Lemma 8.4.5 — even restricted distances outnumber odd ones
ProvedMatousekLP.Codes.even_pairs_ge_odd_pairscoding-theorycombinatoricsp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1
Let be a set of indices and an arbitrary set of words. Write for the number of indices with . Then
Pairs are ordered, and pairs are included.
This parity statement is the combinatorial core of Delsarte's inequalities: summed over suitable index sets it yields the Krawtchouk constraints of the linear program.
Formalization Note The index set is a Finset (Fin n) (positions shifted to ).
Preamble
import Mathlib import Definitions.Def_MatousekLP_Codes_Basic open Finset
Formal statement
namespace MatousekLP.Codes
/-- Lemma 8.4.5, p. 161: for every set of indices `I` and every `C ⊆ {0,1}^n`, the number of
ordered pairs `(w, w') ∈ C²` with `d_H^I(w, w')` even is at least the number of such pairs with
`d_H^I(w, w')` odd. -/
theorem even_pairs_ge_odd_pairs {n : ℕ} (I : Finset (Fin n)) (C : Finset (Word n)) :
#{p ∈ C ×ˢ C | Odd (restrictedDist I p.1 p.2)} ≤
#{p ∈ C ×ˢ C | Even (restrictedDist I p.1 p.2)} := by sorry
end MatousekLP.Codes
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 161, Lemma 8.4.5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.