Alon's combinatorial Nullstellensatz
ProvedFamousTheorems.combinatorial_nullstellensatzAlon's combinatorial Nullstellensatz. Let be an integral domain and a polynomial in finitely many variables. Suppose the coefficient of a monomial in is nonzero and . Then for any finite sets with , there is a point with for all and .
Alon's theorem (1999) is a powerful tool in additive combinatorics, graph theory and combinatorial number theory. It gives short proofs of the Cauchy–Davenport theorem, the Erdős–Heilbronn conjecture (Dias da Silva–Hamidoune), the Chevalley–Warning theorem and many list-colouring results.
Formalization note. Mathlib's MvPolynomial.combinatorial_nullstellensatz_exists_eval_nonzero. The monomial is an exponent vector t : σ →₀ ℕ with total degree Finsupp.degree t, and MvPolynomial.coeff t f is its coefficient. f.totalDegree is the total degree of f, and MvPolynomial.eval s f evaluates at the point s.
import Mathlib
namespace FamousTheorems
theorem combinatorial_nullstellensatz {R σ : Type*} [CommRing R] [IsDomain R] [Finite σ] (f : MvPolynomial σ R) (t : σ →₀ ℕ)
(ht : MvPolynomial.coeff t f ≠ 0) (ht' : f.totalDegree = Finsupp.degree t) (S : σ → Finset R)
(htS : ∀ i, t i < (S i).card) :
∃ s : σ → R, (∀ i, s i ∈ S i) ∧ MvPolynomial.eval s f ≠ 0 := by sorry
end FamousTheorems