Punctured combinatorial Nullstellensätze

../

corollary_2_2: Bounds the size of every product grid containing a polynomial's nonzero values.

corollary_3_2: Finds a grid point of order below t from coordinate bounds on a top-degree term.

corollary_4_2: Gives coordinate lower bounds on an original monomial without the false upper bounds.

corollary_4_3: Bounds nonzero values by minimizing a product subject to coordinate and degree constraints.

grid_ideal_reduction: Makes the grid-ideal normal form, degree bounds and one-variable divisibility explicit.

theorem_2_1: States the external ideal-membership theorem with its total-degree control.

theorem_3_1: Represents a polynomial vanishing to order at least t in the t-th grid-ideal power.

theorem_4_1: Factors the remainder of a polynomial with multiple zeros outside a smaller grid.

theorem_5_1: Bounds a point set meeting hyperplanes from a product of concurrent lines outside a hole.

theorem_5_2: Derives the bound (n+t−1)(q−1)+1 for a point set meeting every affine hyperplane t times.

theorem_5_3: Bounds a hyperplane family covering a grid t times outside a smaller product while missing a point.

theorem_5_4: Requires at least the sum of the side lengths in hyperplanes when exactly one grid point is missed.

theorem_5_5: Transfers the nonzero-value product bound to a grid not fully covered by hyperplanes.

---

Simeon Ball and Oriol Serra, Punctured combinatorial Nullstellensätze, Combinatorica 29 (2009), 511–522, DOI 10.1007/s00493-009-2509-z. The publisher record gives issue date September 2009 and online publication 24 August 2010. The separately filed 2011 erratum corrects Corollary 4.2.

Source versions

The edition read is the nine-page corrected author manuscript dated 14 June 2011, available from the author's website. It includes the erratum's removal of the false exponent upper bounds in Corollary 4.2. All labels and page numbers on the result pages are this manuscript's unless marked otherwise. The manuscript, from the author's website, which states no terms, prints no notice; the term is unstated.

The earlier author manuscript, from the same website, is dated 21 January 2009 and has ten pages; it likewise prints no notice. Its Corollary 4.2 (p. 6) carries the upper bounds $|S_i|-1\ge r_i$ that the erratum removes, with a proof and an example that the corrected manuscript drops. Neither manuscript is the journal's typeset article, which was not read, so no page-by-page equivalence with its twelve printed pages is claimed.

Results

Let $S_i\subseteq\mathbb F$ be finite nonempty sets and $g_i(X_i)=\prod_{s\in S_i}(X_i-s)$. The paper quotes Alon's Combinatorial Nullstellensatz as Theorem 2.1 (p. 2) and derives from it Corollary 2.2 (p. 2), a lower bound on any grid containing the nonzero values of a polynomial in terms of a maximum-degree term.

Theorem 3.1 (p. 3) extends Theorem 2.1 to zeros of multiplicity $t$: such a polynomial is a combination of products of $t$ of the $g_i$ with degree-controlled coefficients. Corollary 3.2 (p. 4) turns this into a criterion, in terms of a maximum-degree term, for a grid point of multiplicity at most $t-1$.

Theorem 4.1 (p. 5), the punctured Nullstellensatz, treats a polynomial with zeros of multiplicity at least $t$ on the grid except at some point of a smaller grid $\prod_iD_i$: its remainder is divisible by $\prod_ig_i/l_i$, and if $f$ is nonzero at a point of $\prod_iD_i$ then $\deg f\ge(t-1)\max_j(|S_j|-|D_j|)+\sum_i(|S_i|-|D_i|)$. Corollary 4.2 (p. 6) gives a term of $f$ with exponents $r_i\ge|S_i|-|D_i|$ when the nonzero values lie in $\prod_iD_i$, and Corollary 4.3 (p. 6) is the Alon–Füredi lower bound on the number of nonzero grid values.

Section 5 applies Theorem 4.1 to geometry over a field:

Reading notes

The result pages record where the print is read rather than taken literally:

• Theorems 3.1 and 4.1 count a repeated index in $\tau$ as often as it occurs, as the proof of Corollary 3.2 does, and read multiplicity $t$ as multiplicity at least $t$.
• Corollary 4.2 is read with the hypothesis of Theorem 4.1 that $f$ is nonzero at some grid point; the published erratum, separately, removes the earlier upper bounds.
• In the proof of Corollary 4.3 the set $D_n$ consists of the fibres that are nonzero at some point of the remaining grid.
• The proof of Theorem 5.1 writes $|A|=\deg f$; it needs only $\deg f\le|A|$.
• The remark after Theorem 5.3 omits the condition, required by the theorem, that the origin be uncovered.
• Theorem 5.5 prints $y_i\le|S_n|$, read as $y_i\le|S_i|$.

Every result page is at read depth claims checked, against the corrected manuscript.

Bears on. None. The paper names no Erdős problem, and no problem page cites it.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.