The Alon-Nathanson-Ruzsa polynomial method #
The core of the polynomial method for restricted sums in ZMod p: elimination
polynomials, the vanishing-coefficient lemma on product grids, and the main
theorem ANR_polynomial_method giving a non-vanishing-coefficient criterion
for lower-bounding restricted sumsets.
Lemma 2.2 : A multivariate polynomial that vanishes on a large product finset is the zero polynomial
Definition of elimination polynomials g_i
Equations
- eliminationPolynomials A i = ∏ a ∈ A i, (MvPolynomial.X i - MvPolynomial.C a)
Instances For
The sum of variables polynomial
Equations
- sumXPolynomial = ∑ i : Fin (k + 1), MvPolynomial.X i
Instances For
The restricted sumset S from the ANR theorem
Equations
- restrictedSumset h A = Finset.image (fun (f : Fin (k + 1) → ZMod p) => ∑ i : Fin (k + 1), f i) ({f ∈ Fintype.piFinset A | (MvPolynomial.eval f) h ≠ 0})
Instances For
The polynomial Q = h * ∏_{e∈E} (∑X_i - e)
Equations
- constructionPolynomial h E = h * (Multiset.map (fun (e : ZMod p) => sumXPolynomial - MvPolynomial.C e) E).prod
Instances For
Alternative name for clarity. Here use k explicitly
Equations
- productPolynomial k E = (Multiset.map (fun (e : ZMod p) => sumXPolynomial - MvPolynomial.C e) E).prod
Instances For
Lemma 2.1.1 : Construction_polynomial vanishes on ∏ A_i
Lemma 2.1.3.1 : About total degree of sumX
Lemma 2.1.3.3 : The total degree of the product polynomial ∏_{e∈E} (∑X_i - C e) is equal to |E| (Induction steps from J.J. Zhang).
Lemma 2.1.4 : The total degree of the construction polynomial is equal to the sum of c_i
Lemma 2.1.5 : The coefficient of a term of maximal degree in the product $\prod (S - e)$ is the same as in $S^{|E|}$
Lemma 2.1.6 : The coefficient of a specific term in the construction polynomial is non-zero under certain conditions
Lemma 2.1.7 : The elimination polynomial $g_i$ for a given index $i$ and set $A_i$
Lemma 2.1.8 : A single step in the monomial reduction process, reducing the degree in variable i
Lemma 2.1.9 : Existence of a remainder polynomial R with bounded degrees matching Q on specified points
Lemma 2.1.10 : If a polynomial Q vanishes on a grid defined by sets A_i and has total degree at most the sum of the sizes of these sets minus one, then the coefficient of the monomial defined by these sizes is zero
Lemma 2.1.11 : If two polynomials P and Q are equal or their difference has a total degree less than m, then the coefficients of the monomial defined by c in h * P and h * Q are equal, given that h.totalDegree + m equals the sum of c_i
Lemma 2.1.12 : The total degree of the difference between the product of linear terms and the corresponding power of the sum polynomial is less than the size of the multiset
Alon-Nathanson-Ruzsa Polynomial Method (Theorem 2.1)
Proof outline (by contradiction):
- Assume the conclusion is false, so the restricted sumset S has at most m elements;
extend S to a multiset E of Z_p with |E| = m (
extendToSize). - Construct the polynomial Q(x_0,...,x_k) = h(x_0,...,x_k) * prod_{e in E} (x_0+...+x_k - e)
(
constructionPolynomial):- deg(Q) = deg(h) + m = sum c_i (
constructionPolynomial_totalDegree) - Q vanishes on prod A_i, since each grid point sums to an element of E
(
constructionPolynomial_vanishes) - The coefficient of the monomial prod x_i^{c_i} in Q is nonzero, since it agrees with
the corresponding coefficient of h * (x_0+...+x_k)^m
(
constructionPolynomial_coeff_target_generalized)
- deg(Q) = deg(h) + m = sum c_i (
- By Lemma 2.1.10 (
coeff_target_eq_zero_of_vanishes_on_grid), a polynomial of total degree at most sum c_i that vanishes on prod A_i has zero coefficient at prod x_i^{c_i}: reducing Q modulo the elimination polynomials g_i = prod_{a in A_i} (x_i - a) leaves the target coefficient unchanged (exists_remainder), and the reduced polynomial vanishes identically by Lemma 2.2 (eq_zero_of_eval_zero_at_prod_finset). - Steps 2 and 3 contradict each other, so |S| >= m + 1; m < p follows since S is a subset of Z_p.