More results on the number of zeros of multiplicity at least r

DOI10.1016/J.DISC.2017.01.004MaRDI QIDQ512588zbMATH OpenOpenAlexFDO

Authors Olav Geil, Casper Thomsen

Publication date 27 February 2017

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

footprint boundmultiplicitymultivariate polynomialSchwartz-Zippel boundzeros of polynomial

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Polynomials in general fields (irreducibility, etc.) (12E05) Cryptography (94A60)

Abstract: We consider multivariate polynomials and investigate how many zeros of multiplicity at least $r$ they can have over a Cartesian product of finite subsets of a field. Here r is any prescribed positive integer and the definition of multiplicity that we use is the one related to Hasse derivatives. As a generalization of material in [2,5] a general version of the Schwartz-Zippel was presented in [8] which from the leading monomial -- with respect to a lexicographic ordering -- estimates the sum of zeros when counted with multiplicity. The corresponding corollary on the number of zeros of multiplicity at least $r$ is in general not sharp and therefore in [8] a recursively defined function $D$ was introduced using which one can derive improved information. The recursive function being rather complicated, the only known closed formula consequences of it are for the case of two variables [8]. In the present paper we derive closed formula consequences for arbitrary many variables, but for the powers in the leading monomial being not too large. Our bound can be viewed as a generalization of the footprint bound [10,6] -- the classical footprint bound taking not multiplicity into account.

Recommendations

• Counting polynomials with zeros of given multiplicities in finite fields
• On zeros of a polynomial in a finite grid
• On multivariate polynomials with many roots over a finite grid
• On the multiplicity of zeros of polynomials over arbitrary finite dimensional k-algebras
• Multiplicity estimates: a Morse-theoretic approach

Cites work

• A Note on the Generalisation of the Guruswami–Sudan List Decoding Algorithm to Reed–Muller Codes
• Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
• Footprints or generalized Bezout's theorem
• scientific article; zbMATH DE number 1756454 (Why is no real title available?)
• Ideals, varieties, and algorithms. An introduction to computational algebraic geometry and commutative algebra
• Improved decoding of Reed-Solomon and algebraic-geometry codes
• List Decoding of<tex>$q$</tex>-ary Reed–Muller Codes
• On the Alon-Füredi bound
• Weighted Reed-Muller codes revisited

Cited in

(9)

• On the multiplicity of zeros of polynomials over arbitrary finite dimensional k-algebras
• Generalized Hamming weights of affine Cartesian codes
• The maximum number of zeros of \(r(z) - \overline{z}\) revisited
• Weighted Reed-Muller codes revisited
• Counting polynomials with zeros of given multiplicities in finite fields
• Interactions of zeros of polynomials and multiplicity matrices
• On zeros of a polynomial in a finite grid
• The Multivariate Schwartz--Zippel Lemma
• Bounding the Number of Common Zeros of Multivariate Polynomials and Their Consecutive Derivatives

This page was built for publication: More results on the number of zeros of multiplicity at least \(r\)

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