Corollary 8.4.6 —
ProvedMatousekLP.Codes.character_sum_nonnegcoding-theorycombinatoricsp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1
For every set of words and every word ,
where is the sum modulo 2 and is the scalar product of 0/1 vectors, i.e. the number of positions where both and have a one.
This is the sign form of Lemma 8.4.5 used in the proof of Proposition 8.4.4.
Formalization Note The sum is over the ordered pairs of C ×ˢ C, computed in ; is a natural number.
Preamble
import Mathlib import Definitions.Def_MatousekLP_Codes_Basic open Finset
Formal statement
namespace MatousekLP.Codes
/-- Corollary 8.4.6, p. 161: for every `C ⊆ {0,1}^n` and every `v ∈ {0,1}^n`,
`∑_{(w,w') ∈ C²} (-1)^{(w ⊕ w')ᵀ v} ≥ 0`. -/
theorem character_sum_nonneg {n : ℕ} (C : Finset (Word n)) (v : Word n) :
0 ≤ ∑ p ∈ C ×ˢ C, (-1 : ℤ) ^ dot (xorWord p.1 p.2) v := by sorry
end MatousekLP.Codes
Source
Matoušek & Gärtner, Understanding and Using Linear Programming, Springer 2007, p. 161, Corollary 8.4.6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.