{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T15:34:40Z","timestamp":1770737680737,"version":"3.49.0"},"reference-count":35,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2018,2,15]],"date-time":"2018-02-15T00:00:00Z","timestamp":1518652800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2018,5]]},"abstract":"<jats:p>A 1993 result of Alon and F\u00fcredi 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 \u2018Condition (D)\u2019 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\u2013F\u00fcredi 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\u2013F\u00fcredi. We then discuss the relationship between Alon\u2013F\u00fcredi and results of DeMillo\u2013Lipton, Schwartz and Zippel. A direct coding theoretic interpretation of Alon\u2013F\u00fcredi theorem and its generalization in terms of Reed\u2013Muller-type affine variety codes is shown, which gives us the minimum Hamming distance of these codes. Then we apply the Alon\u2013F\u00fcredi theorem to quickly recover \u2013 and sometimes strengthen \u2013 old and new results in finite geometry, including the Jamison\u2013Brouwer\u2013Schrijver bound on affine blocking sets. We end with a discussion of multiplicity enhancements.<\/jats:p>","DOI":"10.1017\/s0963548317000566","type":"journal-article","created":{"date-parts":[[2018,2,15]],"date-time":"2018-02-15T08:55:18Z","timestamp":1518684918000},"page":"310-333","source":"Crossref","is-referenced-by-count":24,"title":["On Zeros of a Polynomial in a Finite Grid"],"prefix":"10.1017","volume":"27","author":[{"given":"ANURAG","family":"BISHNOI","sequence":"first","affiliation":[]},{"given":"PETE L.","family":"CLARK","sequence":"additional","affiliation":[]},{"given":"ADITYA","family":"POTUKUCHI","sequence":"additional","affiliation":[]},{"given":"JOHN R.","family":"SCHMITT","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,2,15]]},"reference":[{"key":"S0963548317000566_ref16","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90067-4"},{"key":"S0963548317000566_ref10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02940714"},{"key":"S0963548317000566_ref11","doi-asserted-by":"publisher","DOI":"10.4169\/amer.math.monthly.119.01.065"},{"key":"S0963548317000566_ref6","doi-asserted-by":"publisher","DOI":"10.1112\/blms\/18.2.132"},{"key":"S0963548317000566_ref31","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1954.1057465"},{"key":"S0963548317000566_ref35","first-page":"216","volume-title":"Proc. EUROSAM 79","author":"Zippel","year":"1979"},{"key":"S0963548317000566_ref18","doi-asserted-by":"publisher","DOI":"10.1137\/100783704"},{"key":"S0963548317000566_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/s00022-006-1889-0"},{"key":"S0963548317000566_ref13","unstructured":"Clark P. L. Fattening up Warning's second theorem. arXiv:1506.06743"},{"key":"S0963548317000566_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-012-9714-2"},{"key":"S0963548317000566_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2009.07.008"},{"key":"S0963548317000566_ref24","first-page":"96","article-title":"Generalized Reed\u2013Muller codes","volume":"51","author":"Kasami","year":"1968","journal-title":"Electron. Commun. Japan"},{"key":"S0963548317000566_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-009-2509-z"},{"key":"S0963548317000566_ref29","first-page":"6","article-title":"Application of Boolean algebra to switching circuit design and to error detection","volume":"EC\u20133","author":"Muller","year":"1954","journal-title":"IRE Trans. Electronic Computers"},{"key":"S0963548317000566_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-008-9211-9"},{"key":"S0963548317000566_ref23","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(77)90001-2"},{"key":"S0963548317000566_ref1","doi-asserted-by":"publisher","DOI":"10.1006\/eujc.1993.1011"},{"key":"S0963548317000566_ref20","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-012-9680-8"},{"key":"S0963548317000566_ref25","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58575-3"},{"key":"S0963548317000566_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01204715"},{"key":"S0963548317000566_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(70)90214-7"},{"key":"S0963548317000566_ref26","unstructured":"Lipton R. The curious history of the Schwartz\u2013Zippel lemma. https:\/\/rjlipton.wordpress.com\/2009\/11\/30"},{"key":"S0963548317000566_ref4","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-011-2837-7"},{"key":"S0963548317000566_ref12","doi-asserted-by":"crossref","DOI":"10.37236\/4359","article-title":"The combinatorial Nullstellens\u00e4tze revisited","volume":"21","author":"Clark","year":"2014","journal-title":"Electron. J. Combin."},{"key":"S0963548317000566_ref5","unstructured":"Bishnoi A. , Clark P. L. , Potukuchi A. and Schmitt J. R. (2017) On zeros of a polynomial in a finite grid. arXiv:1508.06020v2"},{"key":"S0963548317000566_ref7","first-page":"61","volume-title":"Current Research Topics in Galois Geometry","author":"Blokhuis","year":"2011"},{"key":"S0963548317000566_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(78)90013-4"},{"key":"S0963548317000566_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ffa.2013.06.004"},{"key":"S0963548317000566_ref22","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1515\/crll.1936.175.50","article-title":"Theorie der h\u00f6heren Differentiale in einem algebraischen Funktionenk\u00f6rper mit vollkommenem Konstantenk\u00f6rper bei beliebiger Charakteristik","volume":"175","author":"Hasse","year":"1936","journal-title":"J. Reine Angew. Math."},{"key":"S0963548317000566_ref34","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/BF02940715","article-title":"Bemerkung zur vorstehenden Arbeit von Herrn Chevalley","volume":"11","author":"Warning","year":"1935","journal-title":"Abh. Math. Sem. Hamburg"},{"key":"S0963548317000566_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-015-3267-8"},{"key":"S0963548317000566_ref21","first-page":"384","article-title":"More results on the number of zeros of multiplicity at least r,","volume":"79","author":"Geil","year":"2017","journal-title":"Discrete Mathematics"},{"key":"S0963548317000566_ref32","doi-asserted-by":"crossref","DOI":"10.37236\/734","article-title":"Algebraically solvable problems: Describing polynomials as equivalent to explicit solutions","volume":"15","author":"Schauz","year":"2008","journal-title":"Electron. J. Combin."},{"key":"S0963548317000566_ref30","unstructured":"Ore \u00d6. (1922) \u00dcber h\u00f6here Kongruenzen. Norsk Mat. Forenings Skrifter Ser. I #7."},{"key":"S0963548317000566_ref33","doi-asserted-by":"publisher","DOI":"10.1145\/322217.322225"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548317000566","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,14]],"date-time":"2022-08-14T11:08:37Z","timestamp":1660475317000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548317000566\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,15]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["S0963548317000566"],"URL":"https:\/\/doi.org\/10.1017\/s0963548317000566","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2,15]]}}}