Rank profiles, normalized laws, and ambiguity subgroups
DefinitionZamirInversion581_Mult_Supplement_StatisticsLet be a finite field, , and let be a matrix dimension. Uniform finite probabilities and expectations use the published uniform-average definition. Put
where is uniform on all matrices. For a profile and a subspace , set
The maximum norm is the maximum of the absolute coordinates together with zero; hence it is zero when . Profiles are extended by zero outside only to make the definition total; the lemma never uses those indices. A subspace average on an empty set is zero, but every dimension used by the lemma has a nonempty Grassmannian.
For any randomized map , let
where are uniform invertible matrices with independent algorithm coins. For , is the law of for ; it fixes zero. Write . With , define
Finally as a subset of , so . These are unconditional finite probability and group objects, shared by all three supporting lemmas.
import Mathlib
import Definitions.Def_ZamirInversion581_Mult_Uniform
set_option autoImplicit false
namespace ZamirInversion581.Mult.Supplement
/-! Finite rank profiles (§3.3, pp.13–15) and normalized laws (§4.2–4.4, pp.19–22).
The source is Zamir, STOC 2027 #581, pinned PDF 175df18b…917.
No machine or trapdoor assumption enters these objects. -/
variable {F : Type*} [Field F] [Fintype F] [DecidableEq F]
abbrev Mat (F : Type*) (n : ℕ) := Matrix (Fin n) (Fin n) F
noncomputable def singularity (F : Type*) [Field F] [Fintype F] (n : ℕ) : ℝ :=
unifProb (fun X : Mat F n => X.det = 0)
noncomputable def rankMass (F : Type*) [Field F] [Fintype F] (n r : ℕ) : ℝ :=
unifProb (fun X : Mat F n => X.rank = r)
noncomputable def corankMass (F : Type*) [Field F] [Fintype F] (n j : ℕ) : ℝ :=
rankMass F n (n - j)
noncomputable def rankBaseline (F : Type*) [Field F] [Fintype F] (n : ℕ) : ℝ :=
(Finset.univ : Finset (Fin (n + 1))).sup' Finset.univ_nonempty
(fun r => rankMass F n r)
/-- Sup norm including the zero-dimensional case. -/
noncomputable def maxNorm {m : ℕ} (x : Fin m → ℝ) : ℝ :=
(insert 0 (Finset.univ.image (fun i => |x i|))).sup' (by simp) id
/-- Uniform subspaces; `Fintype.ofFinite` supplies only the canonical finite enumeration. -/
noncomputable def subspaces (F : Type*) [Field F] [Fintype F] (n k : ℕ) :
Finset (Submodule F (Fin n → F)) := by
classical
letI := Fintype.ofFinite (Submodule F (Fin n → F))
exact Finset.univ.filter (fun W => Module.finrank F W = k)
/-- Total extension of a profile by zero; only indices at most n occur in the lemma. -/
def profileAt {n m : ℕ} (b : Fin (n + 1) → Fin m → ℝ) (j : ℕ) : Fin m → ℝ :=
if h : j < n + 1 then b ⟨j, h⟩ else 0
/-- Display (1): average over subspaces W of dimension n-j, coordinate by coordinate. -/
noncomputable def maskedProfile {n m : ℕ} (b : Fin (n + 1) → Fin m → ℝ)
(V : Submodule F (Fin n → F)) (j : ℕ) : Fin m → ℝ :=
fun i => (∑ W ∈ subspaces F n (n - j),
profileAt b (j + Module.finrank F (V ⊓ W : Submodule F (Fin n → F))) i) / ((subspaces F n (n - j)).card : ℝ)
/-- Natural ceiling of the positive base-q logarithm in Lemma 3.4. -/
noncomputable def cutoff (F : Type*) [Fintype F] (η : ℝ) : ℕ :=
⌈Real.log (100 / η) / Real.log (Fintype.card F : ℝ)⌉₊
/-- Multiplication action on probability laws; zero is fixed. -/
noncomputable def shift (a : Fˣ) (P : PMF F) : PMF F :=
P.map (fun x => (a : F) * x)
noncomputable def mass (P : PMF F) (z : F) : ℝ := (P z).toReal
/-- Finite maximum, rather than an unbounded real supremum. -/
noncomputable def distLaw (P Q : PMF F) : ℝ :=
(Finset.univ : Finset F).sup' Finset.univ_nonempty (fun z => |mass P z - mass Q z|)
/-- Law of D(Y)/det Y for uniform invertible Y, independent D coins. -/
noncomputable def normalized {n : ℕ} (D : Mat F n → PMF F) : PMF F :=
(PMF.uniformOfFintype (GL (Fin n) F)).bind fun Y =>
(D (Y : Mat F n)).map (fun z => z / (Y : Mat F n).det)
/-- Law of D(RA)/det R for uniform invertible R. -/
noncomputable def maskedLaw {n : ℕ} (D : Mat F n → PMF F) (A : Mat F n) : PMF F :=
(PMF.uniformOfFintype (GL (Fin n) F)).bind fun R =>
(D ((R : Mat F n) * A)).map (fun z => z / (R : Mat F n).det)
/-- Display (5), including its heavy-atom condition. -/
noncomputable def nearSymmetries (ε : ℝ) (P : PMF F) : Set Fˣ :=
{a | ε / 2 ≤ mass P (a : F) ∧ distLaw P (shift a P) ≤ 6 * (ε ^ 2 / 10000)}
noncomputable def ambiguity (ε : ℝ) (P : PMF F) : Subgroup Fˣ :=
Subgroup.closure (nearSymmetries ε P)
/-- Multiplicative coset as a subset of F; the singular coset is {0}. -/
def fieldCoset (H : Subgroup Fˣ) (z : F) : Set F :=
{w | ∃ h : H, w = z * (h.val : F)}
end ZamirInversion581.Mult.Supplement