8.2 Combinatorial Nullstellensatz

The Combinatorial Nullstellensatz theorem is a powerful tool in additive combinatorics. It links polynomial vanishing on grids to the existence of combinatorial objects, proving key results in number theory and finite fields.

This theorem shines in proving the existence of subsets with specific properties. By constructing clever polynomials, we can derive tight bounds on combinatorial quantities and solve tricky problems in additive number theory.

Combinatorial Nullstellensatz Theorem

Statement and Proof

Top images from around the web for Statement and Proof

• 

  Graphs of Polynomial Functions | Intermediate Algebra View original

  Is this image relevant?

• 

  co.combinatorics - Important formulas in Combinatorics - MathOverflow View original

  Is this image relevant?

• 

  combinatorics - A problem in Combinatorial Analysis - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Graphs of Polynomial Functions | Intermediate Algebra View original

  Is this image relevant?

• 

  co.combinatorics - Important formulas in Combinatorics - MathOverflow View original

  Is this image relevant?

1 of 3

Top images from around the web for Statement and Proof

• 

  Graphs of Polynomial Functions | Intermediate Algebra View original

  Is this image relevant?

• 

  co.combinatorics - Important formulas in Combinatorics - MathOverflow View original

  Is this image relevant?

• 

  combinatorics - A problem in Combinatorial Analysis - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  Graphs of Polynomial Functions | Intermediate Algebra View original

  Is this image relevant?

• 

  co.combinatorics - Important formulas in Combinatorics - MathOverflow View original

  Is this image relevant?

1 of 3

• The Combinatorial Nullstellensatz theorem asserts if a polynomial $P(x_1, ..., x_n)$ vanishes on a grid $S_1 \times ... \times S_n$, where each $S_i$ is a finite set, then there exist non-negative integers $t_1, ..., t_n$ such that:
  • The coefficient of $x_1^{t_1} ... x_n^{t_n}$ in $P(x_1, ..., x_n)$ is non-zero
  • $|S_i| > t_i$ for all $i$
• The proof relies on the fact a non-zero polynomial cannot vanish on a grid larger than the sum of the degrees of its variables
• Proceeds by contradiction, assuming the coefficient of $x_1^{t_1} ... x_n^{t_n}$ is zero for all choices of $t_i$ satisfying $|S_i| > t_i$
  • Shows this leads to a contradiction with the polynomial vanishing on the grid $S_1 \times ... \times S_n$
• Proves the existence of combinatorial objects with certain properties by constructing a suitable polynomial and applying the theorem to it

Key Concepts and Techniques

• Vanishing of a polynomial on a grid relates to its coefficients
• Non-zero polynomial cannot vanish on a grid larger than the sum of the degrees of its variables
• Contradiction is used in the proof
  • Assumes coefficient is zero for all choices satisfying a condition
  • Shows this contradicts the polynomial vanishing on the grid
• Proves existence of combinatorial objects by constructing a polynomial and applying the theorem

Applications in Additive Combinatorics

Subsets with Additive Properties

• Proves existence of subsets of a finite abelian group whose elements sum to a prescribed value
  • Constructs a suitable polynomial encoding the desired additive property
  • Shows the polynomial vanishes on a suitable grid
• Proves existence of arithmetic progressions in subsets of integers (Roth's theorem, Szemerédi's theorem)

Equations over Finite Fields

• Derives bounds on the number of solutions to equations over finite fields
  • Constructs polynomials vanishing on the set of solutions
  • Applies the Combinatorial Nullstellensatz theorem
• Obtained bounds can be tight, giving the exact value of the combinatorial quantity in question

Polynomial Coefficients and Roots

Vieta's Formulas

• Express the coefficients in terms of the elementary symmetric polynomials in the roots
• Constant term of a monic polynomial equals the product of its roots, up to sign
• Sum of the roots of a monic polynomial equals the negative of the coefficient of the second-highest degree term
• $k$-th elementary symmetric polynomial in the roots of a monic polynomial equals the coefficient of the $(n-k)$-th degree term, up to sign
  • $n$ is the degree of the polynomial

Importance for Combinatorial Nullstellensatz

• Understanding the relationship between coefficients and roots is crucial for applying the theorem
• Theorem relates the vanishing of a polynomial on a grid to its coefficients
• Coefficients encode information about the roots and their symmetric polynomials

Bounds on Combinatorial Quantities

Deriving Bounds

• Derives upper and lower bounds on combinatorial quantities (size of largest subset with additive properties)
• Constructs a polynomial vanishing on a grid corresponding to the combinatorial quantity of interest
• Uses the degree of the polynomial to derive a bound

Example: Subset Sum Problem

• Proves any subset of the integers $\{1, 2, ..., 2n-1\}$ of size $n$ must contain a pair of elements that sum to $2n$
  • Constructs a suitable polynomial
  • Applies the Combinatorial Nullstellensatz theorem
• Bounds obtained can be tight, giving the exact value of the combinatorial quantity

Other Applications

• Deriving bounds on the size of subsets with certain additive properties
• Bounding the number of solutions to equations over finite fields
• Proving the existence of combinatorial objects satisfying specific constraints