Lemma 4.2 — a small proper ambiguity subgroup
OpenZamirInversion581.Mult.Supplement.lemma_4_2complexity-theoryfinite-fieldslinear-algebrap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a finite field with , write , and let . Let be probability laws on with and . Define
Then is proper and, writing , all the following conclusions hold:
The precise bound controls the determinant ambiguity left by preprocessing. Neither the factor six nor the denominator 10000 is replaced by an unspecified constant.
Differences from the source:
- generalization: P is a normalized-answer law and Phat its empirical approximation → arbitrary probability laws P and Phat satisfying the same heavy-atom and approximation hypotheses; reason: the lemma uses only these laws and inequalities; every empirical calibration is included
- encoding: generated multiplicative subgroup and its order → Subgroup.closure in Fˣ and its natural cardinal, cast to real numbers for inequalities; reason: this is exactly the finite subgroup generated by the displayed set S
Preamble
import Mathlib import Definitions.Def_ZamirInversion581_Mult_Supplement_Statistics set_option autoImplicit false
Formal statement
namespace ZamirInversion581.Mult.Supplement
/-- Lemma 4.2, p.22; event (4) and definition (5), without restricting P to a normalized law. -/
theorem lemma_4_2 (F : Type*) [Field F] [Fintype F] [DecidableEq F]
(hq : 2 < Fintype.card F) (ε : ℝ) (hε : 0 < ε) (P Phat : PMF F)
(hp : 1 / (Fintype.card F - 1 : ℝ) + ε ≤ mass P 1)
(hevent : distLaw Phat P ≤ ε ^ 2 / 10000) :
let H := ambiguity ε Phat
H ≠ ⊤ ∧
(Nat.card H : ℝ) < 1 / (1 / (Fintype.card F - 1 : ℝ) + ε / 2) ∧
Nat.card H ∣ Fintype.card F - 1 ∧
(Nat.card H : ℝ) < (Fintype.card F - 1 : ℝ) ∧
(Nat.card H : ℝ) < 2 / ε ∧
(Nat.card H : ℝ) < 1 / (mass P 1 - ε / 4) := by sorry
end ZamirInversion581.Mult.Supplement
Source
Or Zamir, STOC 2027 submission #581 (October 2026), source.pdf SHA-256 175df18b5c98634c390c15a304942f462478044bddc6b15bad02e5a2db2bb917, p.22, Lemma 4.2. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/581.pdf