The integer Chebyshev problem: computational explorations

The integer Chebyshev problem deals with finding polynomials of degree at most n with integer coefficients having minimal supremum norm on a domain D and then analyzing the nth root behavior of the supremum norm of these polynomials as n tends to infinity. The limiting value of the nth root of the supremum norms is called the integer Chebyshev constant for D and the polynomials are called nth integer Chebyshev polynomials on D. The problem has a long history on the intervals [0,1] and [0,1/4], and although the structure of such polynomials is not well understood, it is known that certain critical polynomials must be factors of relatively high multiplicity. Progress is made here by extending the method of Wu to include all known critical polynomials on these intervals which results in an increase in the best known lower bounds for the degree to which many of these critical polynomials must divide an nth integer Chebyshev polynomial. For the unrestricted case on [0,1], this results in an increase for all known critical polynomials. On the interval [0,1/4], it results in an increase for all known nonlinear critical polynomials. Towards finding nth integer Chebyshev polynomials, each stage of the method of Habsieger and Salvy is improved and nth integer Chebyshev polynomials for the unit interval are given for all n less than or equal to 145. As a final result in the single variable case, the upper bound on the integer Chebyshev constant of the unit interval is decreased to 1/2.36482727. The move to the bivariate case on the unit square is then made in two ways and the basic results, which include existence of the limits, initial bounds on the integer Chebyshev constants, symmetry conditions, and the method of computation are extended. For the computation of nth integer Chebyshev polynomials on the unit square, a new application of the integer relation algorithm PSLQ is used to take advantage of symmetry.