exists_signed_nonzero_linear_forms
A family of sums of variables admits a simultaneous nonzero evaluation on finite integer lists whose sizes exceed the selection multiplicities.
Statement
theorem exists_signed_nonzero_linear_forms {E V : Type*} [Fintype E] [Fintype V] [DecidableEq V] (A : E → Finset V) (f : E → V) (hf : ∀ e, f e ∈ A e) (L : V → Finset ℤ) (hL : ∀ v, (Finset.univ.filter (fun e => f e = v)).card < (L v).card) : ∃ x : V → ℤ, (∀ v, x v ∈ L v) ∧ ∀ e, ∑ w ∈ A e, x w ≠ 0
- Source
- Helper for OP-494 in arXiv:2610.30174, following the additive-list coloring argument of arXiv:2302.02190v3, Corollary 5.3. Map the positive-coefficient natural polynomial to the integers, compare its degree with the selected exponent sum, and apply the polynomial nonvanishing theorem.
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- positive_coefficient_selected_linear_productSelecting a variable in each linear form with natural coefficients gives a positive coefficient of the corresponding product monomial.
- Used by 1
- simple_graph_bipartite_additive_lists_of_edge_assignmentA finite bipartite graph admits an additive coloring from arbitrary finite natural label lists when each list size exceeds the number of…
The proof, explained
The theorem is proved by applying Alon's Combinatorial Nullstellensatz to the product polynomial Q(X) = ∏_{e ∈ E} (∑_{w ∈ A(e)} X_w) in ℤ[V]. By choosing one variable f(e) ∈ A(e) from each factor, we obtain a monomial X^t whose coefficient in Q is strictly positive by comparison with an auxiliary polynomial over ℕ. Because each factor is linear, the total degree of Q is at most |E|, which matches the degree of t, proving that deg(Q) = deg(t) = |E|. Since the grid sets satisfy |L(v)| > t(v), the Nullstellensatz guarantees an integer point x ∈ ∏_v L(v) where Q(x) ≠ 0. Because ℤ is an integral domain, the nonvanishing of the product implies that each linear form ∑_{w ∈ A(e)} x(w) is simultaneously nonzero.
Define the exponent multi-index t, polynomial P over ℕ, and polynomial Q over ℤ.
We define the target polynomial Q = ∏ e ∈ E, ∑ w ∈ A e, X w with integer coefficients, along with an identical polynomial P over ℕ and the multi-index t = ∑ e ∈ E, 𝟭_{f e} counting selections of each variable. Simplifying definitions shows that Q is the image of P under the canonical map from ℕ to ℤ.
classical let t : V →₀ ℕ := ∑ e : E, Finsupp.single (f e) 1 let P : MvPolynomial V ℕ := ∏ e : E, ∑ w ∈ A e, X w let Q : MvPolynomial V ℤ := ∏ e : E, ∑ w ∈ A e, X w have hmap : Q = MvPolynomial.map (Nat.castRingHom ℤ) P := by simp [P, Q]
The coefficient of the monomial X^t in Q is nonzero.
By coeff_map, the coefficient of t in Q is the integer cast of its coefficient in P. The lemma positive_coefficient_selected_linear_product ensures this coefficient in P is strictly positive because f e ∈ A e for each e. By Nat.ne_of_gt and Int.ofNat_inj.mp, its integer cast cannot be zero.
uses
coeff_map,positive_coefficient_selected_linear_product,Nat.ne_of_gt,Int.ofNat_inj.mphave ht : Q.coeff t ≠ 0 := by rw [hmap, coeff_map] have h := positive_coefficient_selected_linear_product Finset.univ A f (fun e _ => hf e) change 0 < P.coeff t at h intro hz exact (Nat.ne_of_gt h) (Int.ofNat_inj.mp hz)
The degree of the multi-index t is |E|.
The degree map distributes over the sum defining t using map_sum. Each term Finsupp.single (f e) 1 has degree 1 by Finsupp.degree_single, so the total degree of t is ∑ e ∈ E, 1 = |E|.
uses
map_sum,Finsupp.degree_singlehave htdeg : t.degree = Fintype.card E := by simp [t, map_sum, Finsupp.degree_single]
The total degree of Q is at most |E|.
By MvPolynomial.totalDegree_finsetProd, the total degree of Q is bounded by the sum of the total degrees of the linear factors. Each linear sum has degree at most the maximum degree of its variables (via MvPolynomial.totalDegree_finsetSum and Finset.sup_le), which is at most 1. Summing these bounds via Finset.sum_le_sum gives |E|.
uses
MvPolynomial.totalDegree_finsetProd,Finset.sum_le_sum,MvPolynomial.totalDegree_finsetSum,Finset.sup_lehave hupper : Q.totalDegree ≤ Fintype.card E := by apply (MvPolynomial.totalDegree_finsetProd _ _).trans calc (∑ e : E, (∑ w ∈ A e, (X w : MvPolynomial V ℤ)).totalDegree) ≤ ∑ _e : E, 1 := by apply Finset.sum_le_sum intro e _ apply (MvPolynomial.totalDegree_finsetSum _ _).trans apply Finset.sup_le intro w _ simp _ = Fintype.card E := by simp
The total degree of Q equals the degree of t.
We prove equality by antisymmetry (le_antisymm). The upper bound totalDegree Q ≤ t.degree = |E| was proved in the previous steps. For the lower bound, since coeff t Q ≠ 0, t belongs to the support of Q (MvPolynomial.mem_support_iff.mpr), which forces t.degree ≤ Q.totalDegree by MvPolynomial.le_totalDegree.
uses
le_antisymm,MvPolynomial.le_totalDegree,MvPolynomial.mem_support_iff.mprhave hdeg : Q.totalDegree = t.degree := by apply le_antisymm · simpa only [htdeg] using hupper · change t.sum (fun _ n => n) ≤ Q.totalDegree exact MvPolynomial.le_totalDegree (MvPolynomial.mem_support_iff.mpr ht)
For every variable v ∈ V, the exponent t(v) is strictly less than |L(v)|.
Evaluating t at v via Finsupp.finsetSum_apply and Finsupp.single_apply gives the sum of ones over indices where f e = v, which equals the fiber cardinality |{e ∈ E : f e = v}| by Finset.card_eq_sum_ones and Finset.sum_filter. This matches the hypothesis hL.
uses
Finsupp.finsetSum_apply,Finsupp.single_apply,Finset.card_eq_sum_ones,Finset.sum_filterhave htL : ∀ v, t v < (L v).card := by intro v have hval : t v = (Finset.univ.filter (fun e => f e = v)).card := by simp only [t, Finsupp.finsetSum_apply, Finsupp.single_apply, Finset.card_eq_sum_ones, Finset.sum_filter] rw [hval] exact hL v
There exists an evaluation point x ∈ ∏_{v ∈ V} L(v) where Q(x) ≠ 0.
All hypotheses of Alon's Combinatorial Nullstellensatz (MvPolynomial.combinatorial_nullstellensatz_exists_eval_nonzero) are satisfied: ℤ is an integral domain, the coefficient of t in Q is nonzero, the total degree of Q equals the degree of t, and each grid set L(v) has cardinality strictly greater than t(v). Hence such a point x exists.
uses
MvPolynomial.combinatorial_nullstellensatz_exists_eval_nonzeroobtain ⟨x, hx, hnonzero⟩ := MvPolynomial.combinatorial_nullstellensatz_exists_eval_nonzero Q t ht hdeg L htLThe assignment x makes every linear form ∑_{w ∈ A(e)} x(w) nonzero.
Evaluating Q at x gives the product ∏ e ∈ E, ∑ w ∈ A e, x w ≠ 0. In the integral domain ℤ, a finite product is nonzero if and only if each factor is nonzero (Finset.prod_ne_zero_iff.mp). Using Finset.mem_univ, every factor ∑ w ∈ A e, x w is therefore nonzero.
uses
Finset.prod_ne_zero_iff.mp,Finset.mem_univrefine ⟨x, hx, ?_⟩ have hprod : (∏ e : E, ∑ w ∈ A e, x w) ≠ 0 := by simpa [Q] using hnonzero exact fun e => (Finset.prod_ne_zero_iff.mp hprod) e (Finset.mem_univ _)
coeff_map- Applying a ring homomorphism to a polynomial applies the homomorphism to each of its coefficients.
positive_coefficient_selected_linear_product- In a product of linear forms where each factor contains a distinguished chosen variable, the coefficient of the monomial formed by the product of those chosen variables is strictly positive (over ℕ).
Nat.ne_of_gt- A natural number strictly greater than another cannot equal that number.
Int.ofNat_inj.mp- The canonical embedding from ℕ to ℤ is injective, so an integer equality between casted natural numbers implies equality in ℕ.
map_sum- An additive monoid homomorphism commutes with finite sums.
Finsupp.degree_single- The degree (sum of coordinates) of a single-point finitely supported function with value r is r.
MvPolynomial.totalDegree_finsetProd- The total degree of a finite product of multivariate polynomials is at most the sum of their individual total degrees.
Finset.sum_le_sum- A finite sum is bounded by the sum of term-by-term upper bounds.
MvPolynomial.totalDegree_finsetSum- The total degree of a finite sum of multivariate polynomials is at most the maximum of their individual total degrees.
Finset.sup_le- The supremum of a finite set is at most a given bound if every element of the set is at most that bound.
le_antisymm- If two elements satisfy a ≤ b and b ≤ a in a partial order, then a = b.
MvPolynomial.le_totalDegree- The degree of any monomial appearing with nonzero coefficient in a multivariate polynomial is at most the total degree of the polynomial.
MvPolynomial.mem_support_iff.mpr- A monomial multi-index belongs to the support of a polynomial if its coefficient is nonzero.
Finsupp.finsetSum_apply- Evaluating a finite sum of finitely supported functions at a point equals the sum of their evaluations at that point.
Finsupp.single_apply- A single-point finitely supported function at a with value b evaluates to b at a and 0 elsewhere.
Finset.card_eq_sum_ones- The cardinality of a finite set equals the sum of 1 over all its elements.
Finset.sum_filter- Summing over a filtered subset equals summing an indicator-weighted function over the ambient set.
MvPolynomial.combinatorial_nullstellensatz_exists_eval_nonzero- (Combinatorial Nullstellensatz) If a polynomial over an integral domain has total degree d and a nonzero monomial of degree d, and the size of each variable's grid exceeds its exponent in that monomial, then the polynomial evaluates to a nonzero value at some grid point.
Finset.prod_ne_zero_iff.mp- If a finite product of elements in an integral domain is nonzero, then every factor is nonzero.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set of that type.
- The polynomial P with coefficients in ℕ is an auxiliary object used solely to establish the nonvanishing of the coefficient of t before transferring the result to the integer polynomial Q.
- The equality between the total degree of Q and the degree of the monomial t is established by combining the upper bound from the product structure with the general lower bound that any monomial in the support has degree at most the total degree.
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.
open scoped BigOperatorsopen MvPolynomialtheorem exists_signed_nonzero_linear_forms {E V : Type*} [Fintype E] [Fintype V] [DecidableEq V] (A : E → Finset V) (f : E → V) (hf : ∀ e, f e ∈ A e) (L : V → Finset ℤ) (hL : ∀ v, (Finset.univ.filter (fun e => f e = v)).card < (L v).card) : ∃ x : V → ℤ, (∀ v, x v ∈ L v) ∧ ∀ e, ∑ w ∈ A e, x w ≠ 0 := by classical let t : V →₀ ℕ := ∑ e : E, Finsupp.single (f e) 1 let P : MvPolynomial V ℕ := ∏ e : E, ∑ w ∈ A e, X w let Q : MvPolynomial V ℤ := ∏ e : E, ∑ w ∈ A e, X w have hmap : Q = MvPolynomial.map (Nat.castRingHom ℤ) P := by simp [P, Q] have ht : Q.coeff t ≠ 0 := by rw [hmap, coeff_map] have h := positive_coefficient_selected_linear_product Finset.univ A f (fun e _ => hf e) change 0 < P.coeff t at h intro hz exact (Nat.ne_of_gt h) (Int.ofNat_inj.mp hz) have htdeg : t.degree = Fintype.card E := by simp [t, map_sum, Finsupp.degree_single] have hupper : Q.totalDegree ≤ Fintype.card E := by apply (MvPolynomial.totalDegree_finsetProd _ _).trans calc (∑ e : E, (∑ w ∈ A e, (X w : MvPolynomial V ℤ)).totalDegree) ≤ ∑ _e : E, 1 := by apply Finset.sum_le_sum intro e _ apply (MvPolynomial.totalDegree_finsetSum _ _).trans apply Finset.sup_le intro w _ simp _ = Fintype.card E := by simp have hdeg : Q.totalDegree = t.degree := by apply le_antisymm · simpa only [htdeg] using hupper · change t.sum (fun _ n => n) ≤ Q.totalDegree exact MvPolynomial.le_totalDegree (MvPolynomial.mem_support_iff.mpr ht) have htL : ∀ v, t v < (L v).card := by intro v have hval : t v = (Finset.univ.filter (fun e => f e = v)).card := by simp only [t, Finsupp.finsetSum_apply, Finsupp.single_apply, Finset.card_eq_sum_ones, Finset.sum_filter] rw [hval] exact hL v obtain ⟨x, hx, hnonzero⟩ := MvPolynomial.combinatorial_nullstellensatz_exists_eval_nonzero Q t ht hdeg L htL refine ⟨x, hx, ?_⟩ have hprod : (∏ e : E, ∑ w ∈ A e, x w) ≠ 0 := by simpa [Q] using hnonzero exact fun e => (Finset.prod_ne_zero_iff.mp hprod) e (Finset.mem_univ _)