On zeros of a polynomial in a finite grid

DOI10.1017/S0963548317000566MaRDI QIDQ4635504zbMATH OpenOpenAlexFDO

Authors Anurag Bishnoi, Pete L. Clark, Aditya Potukuchi, John Schmitt

Publication date 23 April 2018

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorial aspects of commutative algebra (05E40) Polynomials over finite fields (11T06) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Combinatorial structures in finite projective spaces (51E20) Blocking sets, ovals, (k)-arcs (51E21)

Abstract: A 1993 result of Alon and F"uredi gives a sharp upper bound on the number of zeros of a multivariate polynomial over an integral domain in a finite grid, in terms of the degree of the polynomial. This result was recently generalized to polynomials over an arbitrary commutative ring, assuming a certain "Condition (D)" on the grid which holds vacuously when the ring is a domain. In the first half of this paper we give a further Generalized Alon-F"uredi Theorem which provides a sharp upper bound when the degrees of the polynomial in each variable are also taken into account. This yields in particular a new proof of Alon-F"uredi. We then discuss the relationship between Alon-F"uredi and results of DeMillo-Lipton, Schwartz and Zippel. A direct coding theoretic interpretation of Alon-F"uredi Theorem and its generalization in terms of Reed--Muller type affine variety codes is shown which gives us the minimum Hamming distance of these codes. Then we apply the Alon-F"uredi Theorem to quickly recover (and sometimes strengthen) old and new results in finite geometry, including the Jamison/Brouwer-Schrijver bound on affine blocking sets. We end with a discussion of multiplicity enhancements.

Recommendations

• On the Alon-Füredi bound
• Punctured combinatorial Nullstellensätze
• A generalization of Alon's combinatorial nullstellensatz
• On the number of zero-patterns of a sequence of polynomials
• More results on the number of zeros of multiplicity at least \(r\)

Cites work

• scientific article; zbMATH DE number 3651744 (Why is no real title available?)
• scientific article; zbMATH DE number 1250549 (Why is no real title available?)
• A probabilistic remark on algebraic program testing
• Affine Cartesian codes
• Algebraically solvable problems: describing polynomials as equivalent to explicit solutions
• Bemerkung zur vorstehenden Arbeit von Herrn Chevalley
• Blocking Sets in Desarguesian Projective Planes
• Colorings and orientations of graphs
• Covering finite fields with cosets of subspaces
• Covering numbers in linear algebra
• Covering the cube by affine hyperplanes
• Démonstration d'une hypothèse de M. Artin
• Erratum. Punctured combinatorial Nullstellensätze
• Extensions to the method of multiplicities, with applications to Kakeya sets and mergers
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• How many \(s\)-subspaces must miss a point set in \(\mathrm{PG}(d, q)\)
• More results on the number of zeros of multiplicity at least \(r\)
• On generalized ReedMuller codes and their relatives
• On the second Hamming weight of some Reed-Muller type codes
• On the second weight of generalized Reed-Muller codes
• On zeros of a polynomial in a finite grid
• Partial covers of \(\mathrm{PG}(n, q)\)
• Punctured combinatorial Nullstellensätze
• The Combinatorial Nullstellensätze revisited
• The blocking number of an affine space
• Warning's second theorem with restricted variables
• Weighted Reed-Muller codes revisited

Cited in

(24)

• On the Alon-Füredi bound
• Decoupling for moment manifolds associated to Arkhipov-Chubarikov-Karatsuba systems
• On zeros of a polynomial in a finite grid
• Graph polynomials and group coloring of graphs
• Multilinear Schwartz-Zippel \(\operatorname{mod} \mathrm{N}\) and lattice-based succinct arguments
• Polynomials that vanish to high order on most of the hypercube
• Circuit amortization friendly encodingsand their application to statistically secure multiparty computation
• Uncertainty in finite planes
• VSS from distributed ZK proofs and applications
• Rinocchio: SNARKs for ring arithmetic
• An isogeny-based ID protocol using structured public keys
• The Multivariate Schwartz--Zippel Lemma
• Three combinatorial perspectives on minimal codes
• Minimum distance functions of complete intersections
• Subspace coverings with multiplicities
• On multivariate polynomials with many roots over a finite grid
• Chevalley-Warning at the boundary
• Covering grids with multiplicity
• Bounding the Number of Common Zeros of Multivariate Polynomials and Their Consecutive Derivatives
• Aggregating Falcon signatures with LaBRADOR
• Covering almost all the layers of the hypercube with multiplicities
• More results on the number of zeros of multiplicity at least \(r\)
• Polynomials over structured grids
• CSI-SharK: CSI-FiSh with sharing-friendly keys

This page was built for publication: On zeros of a polynomial in a finite grid

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