nus_collision_subspace
def
The right kernel of the collision matrix of A ⊆ Z/pZ: the submodule of functions x : A → Z/pZ with x a + x b = x c + x d for every collision a + b = c + d inside A. Its codimension, n − finrank, is the F_p-rank of the collision matrix.
Statement
def nus_collision_subspace (p : ℕ) (A : Finset (ZMod p)) : Submodule (ZMod p) (↥A → ZMod p)- Source
- step towards nus_min_card_ge_near_quadratic
- Verified
- 20 Oct 2026
- Axioms
- none listed
- Used by 1
- nus_collision_subspace_finrank_ge_twoFor a NUS set A ⊆ Z/pZ, the space of F_p-valued collision-preserving functions on A has dimension at least 2: the constant functions and…
Lean source view module on GitHub
/-- The F_p-valued collision-preserving functions on A, i.e. the right kernel of the collision matrix (paper Section 2). -/ def nus_collision_subspace (p : ℕ) (A : Finset (ZMod p)) : Submodule (ZMod p) (↥A → ZMod p) where carrier := {x | ∀ a b c d : ↥A, ((a : ZMod p) + (b : ZMod p) = (c : ZMod p) + (d : ZMod p)) → x a + x b = x c + x d} zero_mem' := by intro a b c d _; simp add_mem' := by intro x y hx hy a b c d h have h1 := hx a b c d h have h2 := hy a b c d h simp only [Pi.add_apply] calc x a + y a + (x b + y b) = (x a + x b) + (y a + y b) := by ring _ = (x c + x d) + (y c + y d) := by rw [h1, h2] _ = x c + y c + (x d + y d) := by ring smul_mem' := by intro r x hx a b c d h have h1 := hx a b c d h simp only [Pi.smul_apply] calc r • x a + r • x b = r • (x a + x b) := by rw [smul_add] _ = r • (x c + x d) := by rw [h1] _ = r • x c + r • x d := by rw [smul_add]