On the degree of univariate polynomials over the integers

Gil Cohen, Amir Shpilka, Avishay Tal

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

We study the following problem raised by von zur Gathen and Roche [GR97]: What is the minimal degree of a nonconstant polynomial f: {0,...,n} → {0,...,m}? Clearly, when m = n the function f(x) = x has degree 1. We prove that when m = n - 1 (i.e. the point {n} is not in the range), it must be the case that deg(f) = n - o(n). This shows an interesting threshold phenomenon. In fact, the same bound on the degree holds even when the image of the polynomial is any (strict) subset of {0,...,n}. Going back to the case m = n, as we noted the function f(x) = x is possible, however, we show that if one excludes all degree 1 polynomials then it must be the case that deg(f) = n - o(n). Moreover, the same conclusion holds even if m = O(n 1.475 - ε). In other words, there are no polynomials of intermediate degrees that map {0,...,n} to {0,...,m}. Furthermore, we give a meaningful answer when m is a large polynomial, or even exponential, in n. Roughly, we show that if m < ( n/c d), for some constant c, then either deg(f) ≤ d - 1 (e.g. f(x) = ( x-n/2 d - 1) is possible) or deg(f) ≥ n/3 - O(d log n). So, again, no polynomial of intermediate degree exists for such m. We achieve this result by studying a discrete version of the problem of giving a lower bound on the minimal L , norm that a monic polynomial of degree d obtains on the interval [-1,1]. We complement these results by showing that for every d = o(√n/log n) there exists a polynomial f: {0,...,n} → {0,...,O(n d+0.5)} of degree n/3 - O(d log n) ≤ deg(f) ≤ n - O(d log (n)). Our proofs use a variety of techniques that we believe will find other applications as well. One technique shows how to handle a certain set of diophantine equations by working modulo a well chosen set of primes (i.e. a Boolean cube of primes). Another technique shows how to use lattice theory and Minkowski's theorem to prove the existence of a polynomial with certain properties.

Original languageEnglish (US)
Title of host publicationITCS 2012 - Innovations in Theoretical Computer Science Conference
Pages409-427
Number of pages19
DOIs
StatePublished - Feb 6 2012
Event3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012 - Cambridge, MA, United States
Duration: Jan 8 2012Jan 10 2012

Publication series

NameITCS 2012 - Innovations in Theoretical Computer Science Conference

Other

Other3rd Conference on Innovations in Theoretical Computer Science, ITCS 2012
CountryUnited States
CityCambridge, MA
Period1/8/121/10/12

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'On the degree of univariate polynomials over the integers'. Together they form a unique fingerprint.

  • Cite this

    Cohen, G., Shpilka, A., & Tal, A. (2012). On the degree of univariate polynomials over the integers. In ITCS 2012 - Innovations in Theoretical Computer Science Conference (pp. 409-427). (ITCS 2012 - Innovations in Theoretical Computer Science Conference). https://doi.org/10.1145/2090236.2090269