exists_nontrivial_solution_of_card_gt
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
- common_space_diagonal_tensor_rank_boundCommon-Space Diagonal Tensor Rank Bound (arXiv:2610.26686, Lemma 3). Let k = n + 1 ≥ 2 (with 1 ≤ n), and let V ⊆ U be a finite set. Let f…
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.
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.
uses
Pi.add_apply,Finset.sum_add_distrib,Finset.sum_congr,Pi.smul_apply,smul_eq_mul,RingHom.id_apply,Finset.mul_sumlet 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 }
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.
have hdim : Module.finrank ℚ (Fin d → ℚ) < Module.finrank ℚ (V → ℚ) := by simp [hcard]
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.
uses
LinearMap.ker_ne_bot_of_finrank_lt,Submodule.ne_bot_iff,LinearMap.mem_kerhave 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
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.
uses
congr_funrefine ⟨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
- The dimension calculation at lines 22–23 relies on `simp` automatically recognizing that the dimension of a function space `ι → ℚ` over ℚ is the cardinality of the finite index type `ι`.
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.
/-- 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