AFTD Auto-Formalizing Theoretical Domains

exists_signed_nonzero_linear_forms

theoremverified

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
Used by 1

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.

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

    lines 10–15

      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]
  2. 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.

    lines 16–22

    uses coeff_map, positive_coefficient_selected_linear_product, Nat.ne_of_gt, Int.ofNat_inj.mp

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

    lines 23–24

    uses map_sum, Finsupp.degree_single

      have htdeg : t.degree = Fintype.card E := by
        simp [t, map_sum, Finsupp.degree_single]
  4. 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|.

    lines 25–36

    uses MvPolynomial.totalDegree_finsetProd, Finset.sum_le_sum, MvPolynomial.totalDegree_finsetSum, Finset.sup_le

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

    lines 37–41

    uses le_antisymm, MvPolynomial.le_totalDegree, MvPolynomial.mem_support_iff.mpr

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

    lines 42–48

    uses Finsupp.finsetSum_apply, Finsupp.single_apply, Finset.card_eq_sum_ones, Finset.sum_filter

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

    lines 49–50

    uses MvPolynomial.combinatorial_nullstellensatz_exists_eval_nonzero

      obtain ⟨x, hx, hnonzero⟩ :=
        MvPolynomial.combinatorial_nullstellensatz_exists_eval_nonzero Q t ht hdeg L htL
  8. The 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.

    lines 51–54

    uses Finset.prod_ne_zero_iff.mp, Finset.mem_univ

      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 _)
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.

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

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