On multivariate polynomials with many roots over a finite grid

Olav Geil*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

In this paper, we consider roots of multivariate polynomials over a finite grid. When given information on the leading monomial with respect to a fixed monomial ordering, the footprint bound [Footprints or generalized Bezout's theorem, IEEE Trans. Inform. Theory 46(2) (2000) 635-641, On (or in) Dick Blahut's 'footprint', Codes, Curves Signals (1998) 3-9] provides us with an upper bound on the number of roots, and this bound is sharp in that it can always be attained by trivial polynomials being a constant times a product of an appropriate combination of terms consisting of a variable minus a constant. In contrast to the one variable case, there are multivariate polynomials attaining the footprint bound being not of the above form. This even includes irreducible polynomials. The purpose of the paper is to determine a large class of polynomials for which only the mentioned trivial polynomials can attain the bound, implying that to search for other polynomials with the maximal number of roots one must look outside this class.

Original languageEnglish
Article number2150136
JournalJournal of Algebra and its Applications
Volume20
Issue number8
ISSN0219-4988
DOIs
Publication statusPublished - 2021

Keywords

  • Finite field
  • finite grid
  • footprint bound
  • multivariate polynomial
  • root
  • variety

Fingerprint

Dive into the research topics of 'On multivariate polynomials with many roots over a finite grid'. Together they form a unique fingerprint.

Cite this