Hostname: page-component-745bb68f8f-mzp66 Total loading time: 0 Render date: 2025-02-06T23:14:57.100Z Has data issue: false hasContentIssue false
  • English
  • Français

On Zeros of a Polynomial in a Finite Grid

Part of: Finite fields and commutative rings (number-theoretic aspects) Algebraic combinatorics Finite geometry and special incidence structures

Published online by Cambridge University Press:  15 February 2018

ANURAG BISHNOI ,
PETE L. CLARK ,
ADITYA POTUKUCHI  and
JOHN R. SCHMITT
ANURAG BISHNOI
Affiliation:
Freie Universität Berlin, Institut für Mathematik, Arnimallee 3, 14195 Berlin, Germany. (e-mail: anurag.2357@gmail.com)
PETE L. CLARK
Affiliation:
Department of Mathematics, University of Georgia, Athens, GA 30605, USA (e-mail: plclark@gmail.com)
ADITYA POTUKUCHI
Affiliation:
Department of Computer Science, Rutgers University, Piscataway, NJ 08854, USA (e-mail: apotu.57@gmail.com)
JOHN R. SCHMITT
Affiliation:
Department of Mathematics, Middlebury College, Middlebury, VT 05753, USA (e-mail: jschmitt@middlebury.edu)
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.

A 1993 result of Alon and Füredi 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üredi 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üredi. We then discuss the relationship between Alon–Füredi and results of DeMillo–Lipton, Schwartz and Zippel. A direct coding theoretic interpretation of Alon–Füredi 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üredi 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.

MSC classification

Primary: 05E40: Combinatorial aspects of commutative algebra
Secondary: 11T06: Polynomials 11T71: Algebraic coding theory; cryptography 51E20: Combinatorial structures in finite projective spaces 51E21: Blocking sets, ovals, $k$-arcs
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 27 , Issue 3 , May 2018 , pp. 310 - 333
Copyright
Copyright © Cambridge University Press 2018 

References

[1] Alon, N. and Füredi, Z. (1993) Covering the cube by affine hyperplanes. European J. Combin. 14 79–83.Google Scholar
[2] Alon, N. and Tarsi, M. (1992) Colorings and orientations of graphs. Combinatorica 12 125–134.Google Scholar
[3] Ball, S. and Serra, O. (2009) Punctured combinatorial Nullstellensätze. Combinatorica 29 511–522.CrossRefGoogle Scholar
[4] Ball, S. and Serra, O. (2011) Erratum: Punctured combinatorial Nullstellensätze. Combinatorica 31 377–378.Google Scholar
[5] Bishnoi, A., Clark, P. L., Potukuchi, A. and Schmitt, J. R. (2017) On zeros of a polynomial in a finite grid. arXiv:1508.06020v2Google Scholar
[6] Blokhuis, A. and Brouwer, A. E. (1986) Blocking sets in Desarguesian projective planes. Bull. London Math. Soc. 18 132–134.Google Scholar
[7] Blokhuis, A., Sziklai, P. and Szőnyi, T. (2011) Blocking sets in projective spaces. In Current Research Topics in Galois Geometry (De Beule, J. and Storme, L., eds), Nova Academic, pp. 61–84.Google Scholar
[8] Brouwer, A. E. and Schrijver, A. (1978) The blocking number of an affine space. J. Combin. Theory Ser. A 24 251–253.Google Scholar
[9] Carvalho, C. (2013) On the second Hamming weight of some Reed–Muller type codes. Finite Fields Appl. 24 88–94.CrossRefGoogle Scholar
[10] Chevalley, C. (1935) Démonstration d'une hypothèse de M. Artin. Abh. Math. Sem. Univ. Hamburg 11 73–75.Google Scholar
[11] Clark, P. L. (2012) Covering numbers in linear algebra. Amer. Math. Monthly 119 65–67.CrossRefGoogle Scholar
[12] Clark, P. L. (2014) The combinatorial Nullstellensätze revisited. Electron. J. Combin. 21 #P4.15.CrossRefGoogle Scholar
[13] Clark, P. L. Fattening up Warning's second theorem. arXiv:1506.06743Google Scholar
[14] Clark, P. L., Forrow, A. and Schmitt, J. R. (2017) Warning's second theorem with restricted variables. Combinatorica 37 397–417.Google Scholar
[15] Delsarte, P., Goethals, J.-M. and MacWilliams, F. J. (1970) On generalized Reed–Muller codes and their relatives. Inform. Control 16 403–442.CrossRefGoogle Scholar
[16] DeMillo, R. A. and Lipton, R. (1978) A probabilistic remark on algebraic program testing. Inform. Process. Lett. 7 193–195.Google Scholar
[17] Dodunekov, S., Storme, L. and Van de Voorde, G. (2010) Partial covers of PG(n, q). European J. Combin. 31 1611–1616.Google Scholar
[18] 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
[19] Geil, O. (2008) On the second weight of generalized Reed–Muller codes. Des. Codes Cryptogr. 48 323–330.CrossRefGoogle Scholar
[20] Geil, O. and Thomsen, C. (2013) Weighted Reed–Muller codes revisited. Des. Codes Cryptogr. 66 195–220.Google Scholar
[21] Geil, O. and Thomsen, C. (2017) More results on the number of zeros of multiplicity at least r, Discrete Mathematics, 79, 384–410.Google Scholar
[22] 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.CrossRefGoogle Scholar
[23] Jamison, R. E. (1977) Covering finite fields with cosets of subspaces. J. Combin. Theory Ser. A 22 253–266.Google Scholar
[24] Kasami, T., Lin, S. and Peterson, W. W. (1968) Generalized Reed–Muller codes. Electron. Commun. Japan 51 96–104.Google Scholar
[25] van Lint, J. H. (1999) Introduction to Coding Theory, third edition, Vol. 86 of Graduate Texts in Mathematics, Springer.CrossRefGoogle Scholar
[26] Lipton, R. The curious history of the Schwartz–Zippel lemma. https://rjlipton.wordpress.com/2009/11/30Google Scholar
[27] López, H. H., Renterá-Márquez, C. and Villarreal, R. H. (2014) Affine Cartesian codes. Des. Codes Cryptogr. 71 5–19.CrossRefGoogle Scholar
[28] Metsch, K. (2006) How many s-subspaces must miss a point set in PG(d, q). J. Geom. 86 154–164.CrossRefGoogle Scholar
[29] Muller, D. (1954) Application of Boolean algebra to switching circuit design and to error detection. IRE Trans. Electronic Computers EC–3 (3) 6–12.Google Scholar
[30] Ore, Ö. (1922) Über höhere Kongruenzen. Norsk Mat. Forenings Skrifter Ser. I #7.Google Scholar
[31] Reed, I. S. (1954) A class of multiple-error-correcting codes and the decoding scheme. IRE Trans. Information Theory PGIT–4 38–49.Google Scholar
[32] Schauz, U. (2008) Algebraically solvable problems: Describing polynomials as equivalent to explicit solutions. Electron. J. Combin. 15 #R10.Google Scholar
[33] Schwartz, J. T. (1980) Fast probabilistic algorithms for verification of polynomial identities. J. Assoc. Comput. Mach. 27 701–717.CrossRefGoogle Scholar
[34] Warning, E. (1935) Bemerkung zur vorstehenden Arbeit von Herrn Chevalley. Abh. Math. Sem. Hamburg 11 76–83.Google Scholar
[35] Zippel, R. (1979) Probabilistic algorithms for sparse polynomials. In Proc. EUROSAM 79, Vol. 72 of Lecture Notes in Computer Science, Springer, pp. 216–226.Google Scholar