On zeros of a polynomial in a finite grid
From MaRDI portal
Publication:4635504
DOI10.1017/S0963548317000566zbMATH Open1388.05198arXiv1508.06020OpenAlexW2963350742MaRDI QIDQ4635504FDOQ4635504
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)
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.
Full work available at URL: https://arxiv.org/abs/1508.06020
Recommendations
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)
Cites Work
- A probabilistic remark on algebraic program testing
- Démonstration d'une hypothèse de M. Artin
- Covering Numbers in Linear Algebra
- Title not available (Why is that?)
- Fast Probabilistic Algorithms for Verification of Polynomial Identities
- On the second weight of generalized Reed-Muller codes
- Weighted Reed-Muller codes revisited
- Affine Cartesian codes
- On the second Hamming weight of some Reed-Muller type codes
- On generalized ReedMuller codes and their relatives
- Covering finite fields with cosets of subspaces
- The blocking number of an affine space
- Blocking Sets in Desarguesian Projective Planes
- Title not available (Why is that?)
- Colorings and orientations of graphs
- Covering the cube by affine hyperplanes
- Punctured combinatorial Nullstellensätze
- Algebraically solvable problems: describing polynomials as equivalent to explicit solutions
- Bemerkung zur vorstehenden Arbeit von Herrn Chevalley
- How many \(s\)-subspaces must miss a point set in \(\mathrm{PG}(d, q)\)
- Partial covers of \(\mathrm{PG}(n, q)\)
- Warning's second theorem with restricted variables
- The Combinatorial Nullstellensätze revisited
- On Zeros of a Polynomial in a Finite Grid
- More results on the number of zeros of multiplicity at least \(r\)
- Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
- Erratum. Punctured combinatorial Nullstellensätze
Cited In (23)
- On the Alon-Füredi bound
- Decoupling for moment manifolds associated to Arkhipov-Chubarikov-Karatsuba systems
- Three Combinatorial Perspectives on Minimal Codes
- Multilinear Schwartz-Zippel \(\operatorname{mod} \mathrm{N}\) and lattice-based succinct arguments
- Graph polynomials and group coloring of graphs
- Polynomials that vanish to high order on most of the hypercube
- VSS from distributed ZK proofs and applications
- Circuit amortization friendly encodingsand their application to statistically secure multiparty computation
- Uncertainty in finite planes
- Rinocchio: SNARKs for ring arithmetic
- An isogeny-based ID protocol using structured public keys
- 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
- Polynomials vanishing on grids: the Elekes-Rónyai problem revisited
- Aggregating Falcon signatures with LaBRADOR
- On Zeros of a Polynomial in a Finite Grid
- Covering almost all the layers of the hypercube with multiplicities
- 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)
