nus_collision_subspace_finrank_ge_two
For 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 the label map a ↦ a are both collision-preserving, and they are linearly independent because A has at least two distinct elements.
Statement
theorem nus_collision_subspace_finrank_ge_two {p : ℕ} [Fact p.Prime] {A : Finset (ZMod p)}
(hA : finset_has_no_unique_sums A) :
2 ≤ Module.finrank (ZMod p) ↥(nus_collision_subspace p A)- Source
- step towards nus_min_card_ge_near_quadratic
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- nus_collision_subspaceThe 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…
- finset_has_no_unique_sumsA has no unique sums (is NUS): |A| ≥ 2 and every sum a + b with a, b ∈ A has at least two representations as an unordered pair from A.
- finset_unordered_sum_rep_countr_{A,2}(s): the number of unordered pairs {a, b} (a = b allowed) of elements of A with a + b = s.
The proof, explained
To show that the collision subspace has dimension at least 2, we construct an explicit 2-dimensional family of collision-preserving functions: the affine-linear maps $a \mapsto u_0 + u_1 a$ parameterized by $(u_0, u_1) \in (\mathbb{Z}/p\mathbb{Z})^2$. Any affine map preserves additive collisions because $a + b = c + d$ directly implies $(u_0 + u_1 a) + (u_0 + u_1 b) = (u_0 + u_1 c) + (u_0 + u_1 d)$. Since $A$ has at least two distinct elements, evaluating an affine map at two points uniquely recovers its coefficients, proving that the parameterization is injective. The existence of this injective linear map from $(\mathbb{Z}/p\mathbb{Z})^2$ into the collision subspace immediately implies that the subspace has dimension at least 2.
$A$ contains at least two distinct elements ($|A| > 1$).
By definition of a set having no unique sums, $|A| \ge 2$ (`hA.1`), which immediately implies $|A| > 1$.
have hcard : 1 < A.card := by have h := hA.1; omega
Affine evaluation $(u_0, u_1) \mapsto (a \mapsto u_0 + u_1 a)$ defines a linear map $F : (\mathbb{Z}/p\mathbb{Z})^2 \to (A \to \mathbb{Z}/p\mathbb{Z})$.
We define $F$ by sending a pair of coefficients $u = (u_0, u_1)$ to the affine-linear function $a \mapsto u_0 + u_1 a$. Linearity requires preserving addition and scalar multiplication by elements of $\mathbb{Z}/p\mathbb{Z}$. Both properties hold by unfolding pointwise operations (`Pi.add_apply`, `Pi.smul_apply`, `smul_eq_mul`, `RingHom.id_apply`) and applying commutative ring arithmetic.
uses
Pi.add_apply,Pi.smul_apply,smul_eq_mul,RingHom.id_apply-- The 2-dimensional space of maps `a ↦ c 0 + c 1 * a`, i.e. affine-linear maps. let F : (Fin 2 → ZMod p) →ₗ[ZMod p] (↥A → ZMod p) := { toFun := fun u a => u 0 + u 1 * (a : ZMod p) map_add' := by intro x y ext a simp only [Pi.add_apply] ring map_smul' := by intro r x ext a simp only [Pi.smul_apply, smul_eq_mul, RingHom.id_apply] ring }
Every affine-linear map in the image of $F$ belongs to the collision subspace of $A$.
Given $a, b, c, d \in A$ with $a + b = c + d$, we check whether $F(u)(a) + F(u)(b) = F(u)(c) + F(u)(d)$. Expanding $F(u)$ yields $2 u_0 + u_1(a + b)$ on the left and $2 u_0 + u_1(c + d)$ on the right. Multiplying the collision equation $a + b = c + d$ by $u_1$ directly equates the two sides.
-- Every such map is collision-preserving. have hmem : ∀ u : Fin 2 → ZMod p, F u ∈ nus_collision_subspace p A := fun u => by intro a b c d h show u 0 + u 1 * (a : ZMod p) + (u 0 + u 1 * (b : ZMod p)) = u 0 + u 1 * (c : ZMod p) + (u 0 + u 1 * (d : ZMod p)) linear_combination (u 1) * h
Restricting the codomain of $F$ yields a linear map $G : (\mathbb{Z}/p\mathbb{Z})^2 \to \text{nus\_collision\_subspace } p\ A$ that agrees pointwise with $F$.
Because every $F(u)$ lies in the collision subspace, we use `LinearMap.codRestrict` to restrict the target of $F$ to the submodule `nus_collision_subspace p A`. By `LinearMap.codRestrict_apply`, the map $G(u)$ equals $F(u)$ when viewed in the ambient function space.
uses
LinearMap.codRestrict_applylet G : (Fin 2 → ZMod p) →ₗ[ZMod p] ↥(nus_collision_subspace p A) := F.codRestrict _ hmem have hG : ∀ u, (G u : ↥A → ZMod p) = F u := fun u => LinearMap.codRestrict_apply _ _ u
The linear map $G$ is injective.
Suppose $G(x) = G(y)$ for $x, y \in (\mathbb{Z}/p\mathbb{Z})^2$. Coercing to the ambient function space via `congrArg Subtype.val` gives $F(x) = F(y)$, so $x_0 + x_1 a = y_0 + y_1 a$ for all $a \in A$ by `congrFun`. Since $|A| > 1$, there exist distinct elements $a, b \in A$ (`Finset.one_lt_card.mp`). Subtracting the equality at $b$ from that at $a$ yields $(x_1 - y_1)(a - b) = 0$. Because $a \ne b$, their difference is non-zero (`sub_ne_zero.mpr`). Over the field $\mathbb{Z}/p\mathbb{Z}$, a product of two elements is zero only if one factor is zero (`mul_eq_zero.mp`), which forces $x_1 - y_1 = 0$ (`sub_eq_zero.mp`), so $x_1 = y_1$. Substituting $x_1 = y_1$ back into the equation at $a$ and cancelling the common linear term (`add_right_cancel`) leaves $x_0 = y_0$. By function extensionality over the two-element index set `Fin 2`, $x = y$.
uses
congrArg,Subtype.val,congrFun,Finset.one_lt_card.mp,sub_ne_zero.mpr,mul_eq_zero.mp,sub_eq_zero.mp,add_right_cancel-- Injectivity: two distinct points of A separate the coefficients. have hinj : Function.Injective G := by intro x y hxy have hF : F x = F y := by rw [← hG x, ← hG y, congrArg Subtype.val hxy] have hpt : ∀ a : ↥A, x 0 + x 1 * (a : ZMod p) = y 0 + y 1 * (a : ZMod p) := by intro a exact congrFun hF a obtain ⟨a, ha, b, hb, hab⟩ := Finset.one_lt_card.mp hcard have hd : (x 1 - y 1) * (a - b) = 0 := by have h1 := hpt ⟨a, ha⟩ have h2 := hpt ⟨b, hb⟩ linear_combination h1 - h2 have hne : (a - b) ≠ 0 := sub_ne_zero.mpr hab have h1 : x 1 = y 1 := by rcases mul_eq_zero.mp hd with h | h · exact sub_eq_zero.mp h · exact absurd h hne have h0 : x 0 = y 0 := by have h := hpt ⟨a, ha⟩ rw [h1] at h exact add_right_cancel h funext i fin_cases i · simpa using h0 · simpa using h1
The dimension of the collision subspace over $\mathbb{Z}/p\mathbb{Z}$ is at least 2.
By `LinearMap.finrank_le_finrank_of_injective`, the injective linear map $G$ ensures that $\operatorname{finrank}((\mathbb{Z}/p\mathbb{Z})^2) \le \operatorname{finrank}(\text{nus\_collision\_subspace } p\ A)$. The domain $(\mathbb{Z}/p\mathbb{Z})^2$ has dimension 2 by `Module.finrank_fin_fun`, which yields $2 \le \operatorname{finrank}_{\mathbb{Z}/p\mathbb{Z}}(\text{nus\_collision\_subspace } p\ A)$.
uses
LinearMap.finrank_le_finrank_of_injective,Module.finrank_fin_funhave hle := LinearMap.finrank_le_finrank_of_injective hinj rwa [Module.finrank_fin_fun] at hle
Pi.add_apply- The value of the sum of two functions at a point is the sum of their values: $(f + g)(x) = f(x) + g(x)$.
Pi.smul_apply- The value of a scalar multiple of a function at a point is the scalar multiple of its value: $(c \cdot f)(x) = c \cdot f(x)$.
smul_eq_mul- In a ring acting on itself, scalar multiplication coincides with ring multiplication: $c \cdot x = c * x$.
RingHom.id_apply- The identity ring homomorphism leaves elements unchanged: $\operatorname{id}(x) = x$.
LinearMap.codRestrict_apply- Evaluating a linear map whose codomain has been restricted to a submodule yields the same result as evaluating the original map in the ambient space.
congrArg- If two inputs are equal, a function takes the same value on both: $x = y \implies f(x) = f(y)$.
Subtype.val- The canonical inclusion map that extracts the underlying value from an element of a subtype.
congrFun- If two functions are equal, they take the same value at any argument: $f = g \implies f(x) = g(x)$.
Finset.one_lt_card.mp- If a finite set has cardinality strictly greater than 1, it contains at least two distinct elements.
sub_ne_zero.mpr- If two elements are not equal, their difference is non-zero: $a \ne b \implies a - b \ne 0$.
mul_eq_zero.mp- In a field or integral domain, if a product is zero, then at least one factor is zero: $x y = 0 \implies x = 0 \lor y = 0$.
sub_eq_zero.mp- If the difference between two elements is zero, the elements are equal: $a - b = 0 \implies a = b$.
add_right_cancel- In an additive cancellative monoid or group, adding the same element on the right can be cancelled: $a + c = b + c \implies a = b$.
LinearMap.finrank_le_finrank_of_injective- An injective linear map between modules over a field implies that the dimension of the domain is at most the dimension of the codomain.
Module.finrank_fin_fun- The dimension of the standard coordinate space $R^n$ (represented as `Fin n → R`) over $R$ is $n$.
- The 2-dimensional parameter space is represented formally as `Fin 2 → ZMod p`, where index 0 represents the constant term and index 1 represents the linear coefficient.
- The map $G$ is formally defined via `LinearMap.codRestrict`, which restricts the codomain of the affine evaluation map $F$ from the ambient function space $A \to \mathbb{Z}/p\mathbb{Z}$ to the submodule `nus_collision_subspace p A`.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The modular half of Hou-Yang Lemma 2.1: the F_p-collision kernel of a NUS set has dimension at least 2, i.e. the modular rank of the collision matrix is at most n-2. -/theorem nus_collision_subspace_finrank_ge_two {p : ℕ} [Fact p.Prime] {A : Finset (ZMod p)} (hA : finset_has_no_unique_sums A) : 2 ≤ Module.finrank (ZMod p) ↥(nus_collision_subspace p A) := by have hcard : 1 < A.card := by have h := hA.1; omega -- The 2-dimensional space of maps `a ↦ c 0 + c 1 * a`, i.e. affine-linear maps. let F : (Fin 2 → ZMod p) →ₗ[ZMod p] (↥A → ZMod p) := { toFun := fun u a => u 0 + u 1 * (a : ZMod p) map_add' := by intro x y ext a simp only [Pi.add_apply] ring map_smul' := by intro r x ext a simp only [Pi.smul_apply, smul_eq_mul, RingHom.id_apply] ring } -- Every such map is collision-preserving. have hmem : ∀ u : Fin 2 → ZMod p, F u ∈ nus_collision_subspace p A := fun u => by intro a b c d h show u 0 + u 1 * (a : ZMod p) + (u 0 + u 1 * (b : ZMod p)) = u 0 + u 1 * (c : ZMod p) + (u 0 + u 1 * (d : ZMod p)) linear_combination (u 1) * h let G : (Fin 2 → ZMod p) →ₗ[ZMod p] ↥(nus_collision_subspace p A) := F.codRestrict _ hmem have hG : ∀ u, (G u : ↥A → ZMod p) = F u := fun u => LinearMap.codRestrict_apply _ _ u -- Injectivity: two distinct points of A separate the coefficients. have hinj : Function.Injective G := by intro x y hxy have hF : F x = F y := by rw [← hG x, ← hG y, congrArg Subtype.val hxy] have hpt : ∀ a : ↥A, x 0 + x 1 * (a : ZMod p) = y 0 + y 1 * (a : ZMod p) := by intro a exact congrFun hF a obtain ⟨a, ha, b, hb, hab⟩ := Finset.one_lt_card.mp hcard have hd : (x 1 - y 1) * (a - b) = 0 := by have h1 := hpt ⟨a, ha⟩ have h2 := hpt ⟨b, hb⟩ linear_combination h1 - h2 have hne : (a - b) ≠ 0 := sub_ne_zero.mpr hab have h1 : x 1 = y 1 := by rcases mul_eq_zero.mp hd with h | h · exact sub_eq_zero.mp h · exact absurd h hne have h0 : x 0 = y 0 := by have h := hpt ⟨a, ha⟩ rw [h1] at h exact add_right_cancel h funext i fin_cases i · simpa using h0 · simpa using h1 have hle := LinearMap.finrank_le_finrank_of_injective hinj rwa [Module.finrank_fin_fun] at hle