Alon's nullstellensatz for multisets

DOI10.1007/S00493-012-2758-0zbMATH Open1289.05457arXiv1008.2901OpenAlexW1992807073MaRDI QIDQ377804FDOQ377804

Authors: Géza Kós, Lajos Rónyai 

Publication date: 7 November 2013

Published in: Combinatorica (Search for Journal in Brave)

Abstract: Alon's combinatorial Nullstellensatz (Theorem 1.1 from cite{Alon1}) is one of the most powerful algebraic tools in combinatorics, with a diverse array of applications. Let $F$ be a field, $S_1,S_2,\mathrm{...},S_n$ be finite nonempty subsets of $F$. Alon's theorem is a specialized, precise version of the Hilbertsche Nullstellensatz for the ideal of all polynomial functions vanishing on the set $S=S_{1}imes{S}_{2}imes\mathrm{...}imes{S}_{n}subseteq{F}^n$. From this Alon deduces a simple and amazingly widely applicable nonvanishing criterion (Theorem 1.2 in cite{Alon1}). It provides a sufficient condition for a polynomial $f(x_1,\mathrm{...},x_n)$ which guarantees that $f$ is not identically zero on the set $S$. In this paper we extend these two results from sets of points to multisets. We give two different proofs of the generalized nonvanishing theorem. We extend some of the known applications of the original nonvanishing theorem to a setting allowing multiplicities, including the theorem of Alon and F"uredi on the hyperplane coverings of discrete cubes.

Full work available at URL: https://arxiv.org/abs/1008.2901

Recommendations

• A generalized combinatorial nullstellensatz for multisets
• Some extensions of Alon's Nullstellensatz
• A generalization of Alon's combinatorial nullstellensatz
• A short proof of combinatorial Nullstellensatz
• scientific article; zbMATH DE number 1735789

zbMATH Keywords

combinatorial nullstellensatzmultisets

Mathematics Subject Classification ID

Combinatorial aspects of commutative algebra (05E40) Polynomials in real and complex fields: location of zeros (algebraic theorems) (12D10)

Cites Work

• Title not available (Why is that?)
• An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal
• Some tapas of computer algebra
• Combinatorial Nullstellensatz
• Title not available (Why is that?)
• Restricted set addition: the exceptional case of the Erdős-Heilbronn conjecture
• On a conjecture of Graham and Häggkvist with the polynomial method
• A new extension of the Erdős-Heilbronn conjecture
• Covering the cube by affine hyperplanes
• Sumsets in vector spaces over finite fields
• On value sets of polynomials over a field
• Old and new formulas for the Hopf-Stiefel and related functions
• The distribution of polynomials over finite fields, with applications to the Gowers norms
• Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
• On the solvability of some special equations over finite fields
• Punctured combinatorial Nullstellensätze

Cited In (12)

• Some extensions of Alon's Nullstellensatz
• Covering symmetric sets of the Boolean cube by affine hyperplanes
• Polynomials that vanish to high order on most of the hypercube
• THE NUMBER OF ROOTS OF A POLYNOMIAL SYSTEM
• The sizes of restricted sums of multisets
• A Snevily-type inequality for multisets
• On product decomposition
• Subspace coverings with multiplicities
• Bounding the Number of Common Zeros of Multivariate Polynomials and Their Consecutive Derivatives
• Covering almost all the layers of the hypercube with multiplicities
• A new approach to constant term identities and Selberg-type integrals
• A generalized combinatorial nullstellensatz for multisets

This page was built for publication: Alon's nullstellensatz for multisets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q377804)