Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-02-11T06:49:30.405Z Has data issue: false hasContentIssue false
  • English
  • Français

Bounding the Number of Common Zeros of Multivariate Polynomials and Their Consecutive Derivatives

Part of: Real and complex fields Finite fields and commutative rings (number-theoretic aspects) Computational aspects and applications

Published online by Cambridge University Press:  03 August 2018

O. GEIL  and
U. MARTÍNEZ-PEÑAS
O. GEIL
Affiliation:
Department of Mathematical Sciences, Aalborg University, Skjernvej 4A, 9220 Aalborg, Denmark (e-mail: olav@math.aau.dk)
U. MARTÍNEZ-PEÑAS
Affiliation:
Department of Mathematical Sciences, Aalborg University, Skjernvej 4A, 9220 Aalborg, Denmark (e-mail: olav@math.aau.dk) Department of Electrical and Computer Engineering, University of Toronto, 10 King's College Road, Toronto, Ontario M5S 3G4, Canada (e-mail: umberto@comm.utoronto.ca)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We upper-bound the number of common zeros over a finite grid of multivariate polynomials and an arbitrary finite collection of their consecutive Hasse derivatives (in a coordinate-wise sense). To that end, we make use of the tool from Gröbner basis theory known as footprint. Then we establish and prove extensions in this context of a family of well-known results in algebra and combinatorics. These include Alon's combinatorial Nullstellensatz [1], existence and uniqueness of Hermite interpolating polynomials over a grid, estimations of the parameters of evaluation codes with consecutive derivatives [20], and bounds on the number of zeros of a polynomial by DeMillo and Lipton [8], Schwartz [25], Zippel [26, 27] and Alon and Füredi [2]. As an alternative, we also extend the Schwartz-Zippel bound to weighted multiplicities and discuss its connection to our extension of the footprint bound.

MSC classification

Primary: 11T06: Polynomials
Secondary: 12D10: Polynomials 13P10: Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 28 , Issue 2 , March 2019 , pp. 253 - 279
Copyright
Copyright © Cambridge University Press 2018 

References

[1] Alon, N. (1999) Combinatorial Nullstellensatz. Combin. Probab. Comput. 8 7–29.Google Scholar
[2] Alon, N. and Füredi, Z. (1993) Covering the cube by affine hyperplanes. European J. Combin. 14 79–83.Google Scholar
[3] Ball, S. and Serra, O. (2009) Punctured combinatorial Nullstellensätze. Combinatorica 29 511–522.Google Scholar
[4] Bishnoi, A., Clark, P. L., Potukuchi, A. and Schmitt, J. R. (2018) On zeros of a polynomial in a finite grid. Combin. Probab. Comput. 27 310–333.Google Scholar
[5] Bruen, A. A. (1992) Polynomial multiplicities over finite fields and intersection sets. J. Combin. Theory Ser. A 60 19–33.Google Scholar
[6] Clark, P. L. (2014) The combinatorial Nullstellensätze revisited. Electron. J. Combin. 21 1–17.Google Scholar
[7] Cox, D., Little, J. and O'Shea, D. (2007) Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Springer.Google Scholar
[8] DeMillo, R. A. and Lipton, R. J. (1978) A probabilistic remark on algebraic program testing. Inform. Process. Lett. 7 193–195.Google Scholar
[9] Dvir, Z., Kopparty, S., Saraf, S. and Sudan, M. (2013) Extensions to the method of multiplicities, with applications to Kakeya sets and mergers. SIAM J. Comput. 42 2305–2328.Google Scholar
[10] Gasca, M. and Sauer, T. (2000) Polynomial interpolation in several variables. Adv. Comput. Math. 12 1–377.Google Scholar
[11] Geil, O. and Høholdt, T. (2000) Footprints or generalized Bezout's theorem. IEEE Trans. Inform. Theory 46 635–641.Google Scholar
[12] Geil, O. and Thomsen, C. (2013) Weighted Reed–Muller codes revisited. Des. Codes Cryptogr. 66 195–220.Google Scholar
[13] Geil, O. and Thomsen, C. (2017) More results on the number of zeros of multiplicity at least r. Discrete Math. 340 1028–1038.Google Scholar
[14] Hasse, H. (1936) Theorie der höheren Differentiale in einem algebraischen Funktionenkörper mit vollkommenem Konstantenkörper bei beliebiger Charakteristik. J. Reine Angew. Math. 175 50–54.Google Scholar
[15] Hirschfeld, J. W. P., Korchmaros, G. and Torres, F. (2008) Algebraic Curves over a Finite Field, Princeton University Press.Google Scholar
[16] Høholdt, T. (1998) On (or in) the Blahut footprint. In Codes, Curves, and Signals: Common Threads in Communications (Vardy, A., ed.), Springer, pp. 3–7.Google Scholar
[17] Høholdt, T., van Lint, J. H. and Pellikaan, R. (1998) Algebraic geometry codes. In Handbook of Coding Theory (Pless, V. S. and Huffman, W. C., eds), Elsevier, Vol. 1, pp. 871–961.Google Scholar
[18] Huffman, W. C. and Pless, V. (2003) Fundamentals of Error-Correcting Codes, Cambridge University Press.Google Scholar
[19] Kopparty, S. (2015) List-decoding multiplicity codes. Theory Comput. 11 149–182.Google Scholar
[20] Kopparty, S., Saraf, S. and Yekhanin, S. (2014) High-rate codes with sublinear-time decoding. J. Assoc. Comput. Mach. 61 28.Google Scholar
[21] Kós, G. and Rónyai, L. (2012) Alon's Nullstellensatz for multisets. Combinatorica 32 589–605.Google Scholar
[22] Lorentz, R. A. (2000) Multivariate Hermite interpolation by algebraic polynomials: A survey. J. Comput. Appl. Math. 122 167–201.Google Scholar
[23] Michałek, M. (2010) A short proof of combinatorial Nullstellensatz. Amer. Math. Monthly 117 821–823.Google Scholar
[24] Pellikaan, R. and Wu, X.-W. (2004) List decoding of q-ary Reed–Muller codes. IEEE Trans. Inform. Theory 50 679–682. Extended version: http://www.win.tue.nl/~ruudp/paper/43-exp.pdfGoogle Scholar
[25] Schwartz, J. T. (1980) Fast probabilistic algorithms for verification of polynomial identities. J. Assoc. Comput. Mach. 27 701–717.Google Scholar
[26] Zippel, R. (1979) Probabilistic algorithms for sparse polynomials. In Proc. International Symposium on Symbolic and Algebraic Computation (EUROSAM '79), Springer, pp. 216–226.Google Scholar
[27] Zippel, R. (1989) An explicit separation of relativised random and polynomial time and relativised deterministic polynomial time. Technical report, Cornell University, Ithaca, NY, USA.Google Scholar