AFTD Auto-Formalizing Theoretical Domains

exists_nontrivial_solution_of_card_gt

theoremverified

If a finite set V has cardinality strictly greater than d, then for any d functions p_j : U -> ℚ, there exists a non-zero function h : V -> ℚ such that ∑_{x ∈ V} h(x) p_j(x) = 0 for all j in Fin d.

Statement

theorem exists_nontrivial_solution_of_card_gt {U : Type*} (V : Finset U) (d : ℕ)
    (p : Fin d → U → ℚ) (hcard : d < V.card) :
    ∃ h : V → ℚ, h ≠ 0 ∧ ∀ j : Fin d, ∑ x : V, h x * p j x = 0
Source
arXiv:2610.26686 Lemma 3 proof
Verified
22 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

Read back from the Lean

For any type U, any finite set V : Finset U, any natural number d, and any family of functions p : Fin d → U → ℚ, if d < V.card (the number of equations is strictly less than the number of elements in V), then there exists a function h : V → ℚ such that h ≠ 0 (i.e., h is not identically zero) and, for every j : Fin d, the sum over all x : V of h x * p j x is equal to 0.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The homogeneous system of d linear equations in |V| unknowns is expressed as a ℚ-linear map L from the |V|-dimensional space V → ℚ to the d-dimensional space Fin d → ℚ. Since the number of variables |V| strictly exceeds the number of equations d, the kernel of L is non-trivial by dimension theory (rank-nullity). Any non-zero element h in the kernel provides the desired non-trivial solution.

  1. There is a ℚ-linear map L : (V → ℚ) →ₗ[ℚ] (Fin d → ℚ) defined by L(h)(j) = ∑ x : V, h(x) * p(j, x).

    We define the function L and check the two linear map requirements: additivity and compatibility with scalar multiplication. In both cases, we establish equality of functions into ℚ pointwise using extensionality (`ext j`). For additivity, we expand pointwise addition with `Pi.add_apply`, split the summation with `Finset.sum_add_distrib`, and match the terms using `Finset.sum_congr` and ring arithmetic. For scalar multiplication, we expand the scalar action with `Pi.smul_apply`, `smul_eq_mul`, and `RingHom.id_apply`, factor the scalar out of the sum with `Finset.mul_sum`, and conclude using `Finset.sum_congr` and ring arithmetic.

    lines 5–21

    uses Pi.add_apply, Finset.sum_add_distrib, Finset.sum_congr, Pi.smul_apply, smul_eq_mul, RingHom.id_apply, Finset.mul_sum

      let L : (V → ℚ) →ₗ[ℚ] (Fin d → ℚ) := {
        toFun := fun h j => ∑ x : V, h x * p j x
        map_add' := fun h1 h2 => by
          ext j
          simp only [Pi.add_apply]
          rw [← Finset.sum_add_distrib]
          apply Finset.sum_congr rfl
          intro x _
          ring
        map_smul' := fun c h => by
          ext j
          simp only [Pi.smul_apply, smul_eq_mul, RingHom.id_apply]
          rw [Finset.mul_sum]
          apply Finset.sum_congr rfl
          intro x _
          ring
      }
  2. The dimension of the codomain Fin d → ℚ as a ℚ-vector space is strictly less than the dimension of the domain V → ℚ.

    The ℚ-dimension of the space of functions from a finite set into ℚ equals the cardinality of the domain set, so dim(Fin d → ℚ) = d and dim(V → ℚ) = |V|. Since d < |V| by assumption (`hcard`), the simplifier evaluates the dimensions and deduces the strict inequality.

    lines 22–23

      have hdim : Module.finrank ℚ (Fin d → ℚ) < Module.finrank ℚ (V → ℚ) := by
        simp [hcard]
  3. The kernel of L contains a non-zero function h : V → ℚ.

    Because the dimension of the target space is strictly smaller than that of the domain, `LinearMap.ker_ne_bot_of_finrank_lt` implies that the kernel of L is non-trivial (ker L ≠ ⊥). Rewriting this non-triviality with `Submodule.ne_bot_iff` provides an element h ∈ ker L with h ≠ 0. Finally, `LinearMap.mem_ker` converts the kernel membership into the equation L(h) = 0.

    lines 24–27

    uses LinearMap.ker_ne_bot_of_finrank_lt, Submodule.ne_bot_iff, LinearMap.mem_ker

      have hker : LinearMap.ker L ≠ ⊥ := LinearMap.ker_ne_bot_of_finrank_lt hdim
      rw [Submodule.ne_bot_iff] at hker
      rcases hker with ⟨h, h_mem, h_ne⟩
      rw [LinearMap.mem_ker] at h_mem
  4. The function h is a non-trivial solution to the system: h ≠ 0 and ∑ x : V, h(x) * p(j, x) = 0 for all j in Fin d.

    We provide h as the witness. Its non-zeroness is immediate. For any equation index j ∈ Fin d, evaluating the identity L(h) = 0 at j via `congr_fun` gives L(h)(j) = 0, which by definition of L is ∑ x : V, h(x) * p(j, x) = 0.

    lines 28–30

    uses congr_fun

      refine ⟨h, h_ne, fun j => ?_⟩
      have hj := congr_fun h_mem j
      exact hj
congr_fun
equality of functions implies equality of their evaluations at any input: if f = g, then f(a) = g(a)
Finset.mul_sum
multiplication distributes over a finite sum from the left: a * ∑ i ∈ s, f(i) = ∑ i ∈ s, a * f(i)
Finset.sum_add_distrib
the sum of a sum over a finite set equals the sum of the individual sums: ∑ x ∈ s, (f(x) + g(x)) = ∑ x ∈ s, f(x) + ∑ x ∈ s, g(x)
Finset.sum_congr
two sums over equal finite sets are equal if their summands agree at every element
LinearMap.ker_ne_bot_of_finrank_lt
a linear map from a higher-dimensional finite-dimensional vector space to a lower-dimensional one has a non-trivial kernel
LinearMap.mem_ker
a vector belongs to the kernel of a linear map if and only if the map evaluates to zero on that vector
Pi.add_apply
addition of functions is defined pointwise: (f + g)(i) = f(i) + g(i)
Pi.smul_apply
scalar multiplication of functions is defined pointwise: (a • f)(i) = a • f(i)
RingHom.id_apply
the identity ring homomorphism acts as the identity on elements: (RingHom.id R)(x) = x
smul_eq_mul
in a ring viewed as a module over itself, scalar multiplication coincides with ring multiplication: a • b = a * b
Submodule.ne_bot_iff
a submodule is non-trivial (not equal to the zero submodule ⊥) if and only if it contains a non-zero element

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

/-- A homogeneous system of d equations in more than d unknowns over ℚ has a non-trivial solution. -/theorem exists_nontrivial_solution_of_card_gt {U : Type*} (V : Finset U) (d : ℕ)    (p : Fin d → U → ℚ) (hcard : d < V.card) :    ∃ h : V → ℚ, h ≠ 0 ∧ ∀ j : Fin d, ∑ x : V, h x * p j x = 0 := by  let L : (V → ℚ) →ₗ[ℚ] (Fin d → ℚ) := {    toFun := fun h j => ∑ x : V, h x * p j x    map_add' := fun h1 h2 => by      ext j      simp only [Pi.add_apply]      rw [← Finset.sum_add_distrib]      apply Finset.sum_congr rfl      intro x _      ring    map_smul' := fun c h => by      ext j      simp only [Pi.smul_apply, smul_eq_mul, RingHom.id_apply]      rw [Finset.mul_sum]      apply Finset.sum_congr rfl      intro x _      ring  }  have hdim : Module.finrank ℚ (Fin d → ℚ) < Module.finrank ℚ (V → ℚ) := by    simp [hcard]  have hker : LinearMap.ker L ≠ ⊥ := LinearMap.ker_ne_bot_of_finrank_lt hdim  rw [Submodule.ne_bot_iff] at hker  rcases hker with ⟨h, h_mem, h_ne⟩  rw [LinearMap.mem_ker] at h_mem  refine ⟨h, h_ne, fun j => ?_⟩  have hj := congr_fun h_mem j  exact hj
See it in the graphDiscuss this resultChallenge it