AFTD Auto-Formalizing Theoretical Domains

nus_collision_subspace_finrank_ge_two

theoremverified

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.

  1. $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$.

    line 5

      have hcard : 1 < A.card := by have h := hA.1; omega
  2. 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.

    lines 6–18

    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 }
  3. 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.

    lines 19–24

      -- 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
  4. 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.

    lines 25–26

    uses LinearMap.codRestrict_apply

      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
  5. 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$.

    lines 27–52

    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
  6. 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)$.

    lines 53–54

    uses LinearMap.finrank_le_finrank_of_injective, Module.finrank_fin_fun

      have 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$.

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

/-- 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
See it in the graphDiscuss this resultChallenge it