Lemma 3.7 — forcing every field value: when of coordinates equal
ProvedOptTwoSrcExt.lemma_3_7extractorsfinite-fieldsp2o-gran-per-chapterp2o-plan-bookp2o-v1pseudorandomnesssymmetric-polynomialstwo-source-extractors
Let be a power of two, , and a field of characteristic two, and let be the elementary symmetric polynomial of degree in variables.
- If any specified of equal , then, for arbitrary values of the other coordinates,
- On Boolean inputs , is strict majority: if more than half of the coordinates equal , and otherwise.
The merger of the sumset seed applies to field-valued views; this lemma lets a majority of good views force any prescribed output value.
Formalization Note is Multiset.esymm of at degree ; "characteristic two" is CharP F 2; strict majority is .
Differences from the source:
- encoding: σ_D(z_1, …, z_s); strict majority → Multiset.esymm of the multiset of coordinates at degree D; 2·#{i : z_i = 1} > s; reason: Lean convention; same instances
Preamble
import Mathlib
Formal statement
namespace OptTwoSrcExt
/-- **Lemma 3.7 (Forcing every field value).**
Li, *Asymptotically Optimal Two Source Extractors for Arbitrary Constant Entropy Rate*, STOC 2027
submission (manuscript sha256 2edb00b2…), Lemma 3.7, printed p.33 (PDF p.35): "Let D be a power of
two, let s = 2D − 1, and let F have characteristic two. If any specified D of z1, . . . , zs equal α,
then σD(z1, . . . , zs) = α^D (3.15) for arbitrary values of the other coordinates. On Boolean inputs,
σD is strict majority."
Let `D = 2^j`, `s = 2D − 1`, and `F` a field of characteristic two; `σ_D` is the elementary symmetric
polynomial of degree `D` in `s` variables.
1. If `z ∈ F^s` has `z_i = α` for all `i` in some set `S` of `D` indices, then `σ_D(z) = α^D`.
2. If every `z_i ∈ {0, 1}`, then `σ_D(z) = 1` when more than half of the `s` coordinates equal `1`,
and `σ_D(z) = 0` otherwise.
**Formalization Note.** `σ_D(z)` is `Multiset.esymm` of the multiset `{z₁, …, z_s}` at degree `D`;
"strict majority" is `2·#{i : z_i = 1} > s`. -/
theorem lemma_3_7 {F : Type*} [Field F] [CharP F 2] [DecidableEq F] (D : ℕ) (hD : ∃ j : ℕ, D = 2 ^ j) :
(∀ (z : Fin (2 * D - 1) → F) (α : F) (S : Finset (Fin (2 * D - 1))),
S.card = D → (∀ i ∈ S, z i = α) →
(Finset.univ.val.map z).esymm D = α ^ D) ∧
(∀ z : Fin (2 * D - 1) → F, (∀ i, z i = 0 ∨ z i = 1) →
(Finset.univ.val.map z).esymm D =
if 2 * D - 1 < 2 * (Finset.univ.filter fun i => z i = 1).card then 1 else 0) := by sorry
end OptTwoSrcExt
Source
X. Li, Asymptotically Optimal Two Source Extractors for Arbitrary Constant Entropy Rate, STOC 2027 submission (manuscript sha256 2edb00b2…), Lemma 3.7, p.33 (PDF p.35)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.