Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-26T14:55:06.509Z Has data issue: false hasContentIssue false
  • English
  • Français

On Zeros of a Polynomial in a Finite Grid

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

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: [email protected])
PETE L. CLARK
Affiliation:
Department of Mathematics, University of Georgia, Athens, GA 30605, USA (e-mail: [email protected])
ADITYA POTUKUCHI
Affiliation:
Department of Computer Science, Rutgers University, Piscataway, NJ 08854, USA (e-mail: [email protected])
JOHN R. SCHMITT
Affiliation:
Department of Mathematics, Middlebury College, Middlebury, VT 05753, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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