TY - JOUR

T1 - On the degree of univariate polynomials over the integers

AU - Cohen, Gil

AU - Shpilka, Amir

AU - Tal, Avishay

N1 - Publisher Copyright:
© 2017, János Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg.

PY - 2017/6/1

Y1 - 2017/6/1

N2 - We study the following problem raised by von zur Gathen and Roche [6]: 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(n1.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<(dn/c), for some constant c, and d≤2n/15, then either deg(f) ≤ d—1 (e.g., f(x)=(d−1x−n/2) is possible) or deg(f) ≥ n/3 - O(dlogn). 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 integer k = O(n) there exists a polynomial f: {0,..,n}→{0,..,O(2k)} of degree n/3-O(k)≤deg(f)≤n-k. 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 a somewhat not too high and not too low degree, for example of degree n−Ω(logn) for m=n−1.

AB - We study the following problem raised by von zur Gathen and Roche [6]: 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(n1.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<(dn/c), for some constant c, and d≤2n/15, then either deg(f) ≤ d—1 (e.g., f(x)=(d−1x−n/2) is possible) or deg(f) ≥ n/3 - O(dlogn). 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 integer k = O(n) there exists a polynomial f: {0,..,n}→{0,..,O(2k)} of degree n/3-O(k)≤deg(f)≤n-k. 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 a somewhat not too high and not too low degree, for example of degree n−Ω(logn) for m=n−1.

UR - http://www.scopus.com/inward/record.url?scp=85006961122&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85006961122&partnerID=8YFLogxK

U2 - 10.1007/s00493-015-2987-0

DO - 10.1007/s00493-015-2987-0

M3 - Article

AN - SCOPUS:85006961122

SN - 0209-9683

VL - 37

SP - 419

EP - 464

JO - Combinatorica

JF - Combinatorica

IS - 3

ER -