Lemma 4.1 — shift versus uniformity
OpenZamirInversion581.Mult.Supplement.lemma_4_1complexity-theoryfinite-fieldslinear-algebrap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a finite field of order , let , and let be any randomized map from matrices to . Put . Let be the law of for uniform invertible , and the law of for uniform invertible , in both cases with independent algorithm coins. Multiplication by acts on a law by multiplying its sampled value, leaving zero fixed. Then both assertions hold:
The field of two elements is included. This distribution identity and nonzero-atom bound are used in both determinant regimes.
Differences from the source:
- generalization: the normalized-answer law of the determinant algorithm D → an arbitrary randomized map D into PMF F, with no time bound; reason: the probability identity and bound do not use a computation model and include every source algorithm
- encoding: nonzero elements and probabilities → units Fˣ and real-valued PMF masses on all of F; reason: unit multiplication fixes zero and every denominator det R is nonzero
Preamble
import Mathlib import Definitions.Def_ZamirInversion581_Mult_Supplement_Statistics set_option autoImplicit false
Formal statement
namespace ZamirInversion581.Mult.Supplement
/-- Lemma 4.1, p.20. All randomized maps are allowed, independently of any time bound. -/
theorem lemma_4_1 (F : Type*) [Field F] [Fintype F] [DecidableEq F]
(n : ℕ) (D : Mat F n → PMF F) (A : Mat F n) :
(∀ d : Fˣ, A.det = (d : F) → maskedLaw D A = shift d (normalized D)) ∧
(A.det = 0 → ∀ z : Fˣ,
mass (maskedLaw D A) (z : F) ≤ 1 / (Fintype.card F - 1 : ℝ)) := by sorry
end ZamirInversion581.Mult.Supplement
Source
Or Zamir, STOC 2027 submission #581 (October 2026), source.pdf SHA-256 175df18b5c98634c390c15a304942f462478044bddc6b15bad02e5a2db2bb917, p.20, Lemma 4.1. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/581.pdf