The integer Chebyshev problem

Abstract

We are concerned with the problem of minimizing the supremum norm on an interval of a nonzero polynomial of degree at most<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"><mml:semantics><mml:mi>n</mml:mi><mml:annotation encoding="application/x-tex">n</mml:annotation></mml:semantics></mml:math></inline-formula>with integer coefficients. This is an old and hard problem that cannot be exactly solved in any nontrivial cases. We examine the case of the interval<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-bracket 0 comma 1 right-bracket"><mml:semantics><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">]</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">[0,1]</mml:annotation></mml:semantics></mml:math></inline-formula>in most detail. Here we improve the known bounds a small but interesting amount. This allows us to garner further information about the structure of such minimal polynomials and their factors. This is primarily a (substantial) computational exercise. We also examine some of the structure of such minimal “integer Chebyshev” polynomials, showing for example that on small intevals<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-bracket 0 comma delta right-bracket"><mml:semantics><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mi>δ<!-- δ --></mml:mi><mml:mo stretchy="false">]</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">[0, \delta ]</mml:annotation></mml:semantics></mml:math></inline-formula>and for small degrees<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d"><mml:semantics><mml:mi>d</mml:mi><mml:annotation encoding="application/x-tex">d</mml:annotation></mml:semantics></mml:math></inline-formula>,<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="x Superscript d"><mml:semantics><mml:msup><mml:mi>x</mml:mi><mml:mrow class="MJX-TeXAtom-ORD"><mml:mi>d</mml:mi></mml:mrow></mml:msup><mml:annotation encoding="application/x-tex">x^{d}</mml:annotation></mml:semantics></mml:math></inline-formula>achieves the minimal norm. There is a natural conjecture, due to the Chudnovskys and others, as to what the “integer transfinite diameter” of<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-bracket 0 comma 1 right-bracket"><mml:semantics><mml:mrow><mml:mo stretchy="false">[</mml:mo><mml:mn>0</mml:mn><mml:mo>,</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">]</mml:mo></mml:mrow><mml:annotation encoding="application/x-tex">[0,1]</mml:annotation></mml:semantics></mml:math></inline-formula>should be. We show that this conjecture is false. The problem is then related to a trace problem for totally positive algebraic integers due to Schur and Siegel. Several open problems are raised.