Lemma 3.4 — weighted rank-profile separation
OpenZamirInversion581.Mult.Supplement.lemma_3_4complexity-theoryfinite-fieldslinear-algebrap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be any finite field of order , let , let , and let . Write for uniform , and set . Assume and
For every and every -dimensional subspace , define , where is uniform over subspaces of dimension . Then
The constants are independent of the field and of . This gives the shared separation statement for the invertibility, rank, and determinant reductions.
Differences from the source:
- encoding: maximum norm on vectors and the distribution K_{j,d} → finite maxima including zero and an explicit d-dimensional subspace V, with W uniform in its Grassmannian; reason: the equivalent subspace description is stated immediately before display (1); dimension zero has norm zero
- encoding: indices 0 through n and real base-q logarithm → Fin (n+1), a zero extension used only in total definitions, and the natural ceiling of log(100/η)/log(q); reason: all indices in the conclusion are in range, since j≤J<n and dim(V∩W)≤n-j; the logarithm is positive
Preamble
import Mathlib import Definitions.Def_ZamirInversion581_Mult_Supplement_Statistics set_option autoImplicit false
Formal statement
namespace ZamirInversion581.Mult.Supplement
/-- Lemma 3.4, pp.14–15: all constants are literal and uniform in the field and vector dimension. -/
theorem lemma_3_4 (F : Type*) [Field F] [Fintype F] [DecidableEq F]
(n m : ℕ) (η : ℝ) (b : Fin (n + 1) → Fin m → ℝ)
(hη : 0 < η) (hη₁ : η ≤ 1)
(hb : ∀ j i, 0 ≤ b j i ∧ b j i ≤ 1)
(hn : cutoff F η < n)
(hsep : η ≤ ∑ j ∈ Finset.Icc 1 n,
corankMass F n j * maxNorm (profileAt b j - profileAt b 0)) :
∀ d : ℕ, 1 ≤ d → d ≤ n → ∀ V : Submodule F (Fin n → F),
Module.finrank F V = d →
∃ j : ℕ, j ≤ cutoff F η ∧
η / 100 < maxNorm (maskedProfile b V j - profileAt b j) := by sorry
end ZamirInversion581.Mult.Supplement
Source
Or Zamir, STOC 2027 submission #581 (October 2026), source.pdf SHA-256 175df18b5c98634c390c15a304942f462478044bddc6b15bad02e5a2db2bb917, p.14, Lemma 3.4. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/581.pdf