Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The integer Chebyshev problem

Authors: Peter Borwein and Tamás Erdélyi
Journal: Math. Comp. 65 (1996), 661-681
MSC (1991): Primary 11J54, 11B83
MathSciNet review: 1333305
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We are concerned with the problem of minimizing the supremum norm on an interval of a nonzero polynomial of degree at most $n$ 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 $[0,1]$ 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 $[0, \delta ]$ and for small degrees $d$, $x^{d}$ achieves the minimal norm. There is a natural conjecture, due to the Chudnovskys and others, as to what the ``integer transfinite diameter'' of $[0,1]$ 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.

References [Enhancements On Off] (What's this?)

  • 1. Francesco Amoroso, Sur le diamètre transfini entier d’un intervalle réel, Ann. Inst. Fourier (Grenoble) 40 (1990), no. 4, 885–911 (1991) (French, with English summary). MR 1096596
  • 2. Emiliano Aparicio Bernardo, Methods for the approximate calculation of the minimum uniform Diophantine deviation from zero on a segment, Rev. Mat. Hisp.-Amer. (4) 38 (1978), no. 6, 259–270 (Spanish). MR 531469
  • 3. ------, New bounds on the minimal Diophantine deviation from zero on $[0,1]$ and $[0,1/4]$, Actus Sextas Jour. Mat. Hisp.-Lusitanas (1979), 289--291.
  • 4. ------, On some systems of algebraic integers of D.S. Gorshkov and their application in calculus, Rev. Mat. Hisp.-Amer. 41 (1981), 3--17 (Spanish).
  • 5. È. Aparisio, Some results in the problem of Diophantine approximations of functions by polynomials, Trudy Mat. Inst. Steklov. 163 (1984), 6–9 (Russian). International conference on analytical methods in number theory and analysis (Moscow, 1981). MR 769861
  • 6. P. Borwein and T. Erdélyi, Polynomials and polynomial inequalities, Springer-Verlag, New York, 1995.
  • 7. P. Borwein and C. Ingalls, The Prouhet Tarry Escott problem revisited, Math. Enseign. 40 (1994), 3--27.
  • 8. G. V. Chudnovsky, Number theoretic applications of polynomials with rational coefficients defined by extremality conditions, Arithmetic and geometry, Vol. I, Progr. Math., vol. 35, Birkhäuser Boston, Boston, MA, 1983, pp. 61–105. MR 717590
  • 9. M. Fekete, Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten, Math. Zeit. 17 (1923), 228--249.
  • 10. Le Baron O. Ferguson, Approximation by polynomials with integral coefficients, Mathematical Surveys, vol. 17, American Mathematical Society, Providence, R.I., 1980. MR 560902
  • 11. V. Flammang, Sur la longeur des entiers algébriques totalement positifs, preprint.
  • 12. D. Hilbert, Ein Beitrag zur Theorie des Legendreschen Polynoms, Acta Math. 18 (1894), 155--159.
  • 13. B. Kashin, On algebraic polynomials with integer coefficients with least deviation from zero on an interval, preprint.
  • 14. Tateaki Sasaki, Tomokatsu Saito, and Teruhiko Hilano, Analysis of approximate factorization algorithm. I, Japan J. Indust. Appl. Math. 9 (1992), no. 3, 351–368. MR 1189944, 10.1007/BF03167271
  • 15. H. L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, CBMS, Vol. 84, Amer. Math. Soc., Providence, R. I., 1994. CMP 95:02
  • 16. I. Schur, Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganz-zahligen Koeffizienten, Math. Zeit. 1 (1918), 377--402.
  • 17. G. Pólya and G. Szegő, Problems and theorems in analysis. Vol. I: Series, integral calculus, theory of functions, Springer-Verlag, New York-Berlin, 1972. Translated from the German by D. Aeppli; Die Grundlehren der mathematischen Wissenschaften, Band 193. MR 0344042
  • 18. Edward B. Saff and Richard S. Varga, On lacunary incomplete polynomials, Math. Z. 177 (1981), no. 3, 297–314. MR 618197, 10.1007/BF01162064
  • 19. Carl Ludwig Siegel, The trace of totally positive and real algebraic integers, Ann. of Math. (2) 46 (1945), 302–312. MR 0012092
  • 20. C. J. Smyth, The mean values of totally real algebraic integers, Math. Comp. 42 (1984), no. 166, 663–681. MR 736460, 10.1090/S0025-5718-1984-0736460-5
  • 21. Christopher Smyth, Totally positive algebraic integers of small trace, Ann. Inst. Fourier (Grenoble) 34 (1984), no. 3, 1–28 (English, with French summary). MR 762691

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11J54, 11B83

Retrieve articles in all journals with MSC (1991): 11J54, 11B83

Additional Information

Peter Borwein
Affiliation: Department of Mathematics and Statistics, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6

Tamás Erdélyi
Affiliation: Department of Mathematics, Texas A & M University, College Station, Texas 77843

Keywords: Transfinite diameter, integers, diophantine approximation, trace, Chebyshev, polynomial
Received by editor(s): April 25, 1994
Received by editor(s) in revised form: September 5, 1994, and February 12, 1995
Additional Notes: Research supported in part by NSERC of Canada.
Article copyright: © Copyright 1996 American Mathematical Society