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

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. F. Amoroso, Sur le diamètre transfini entier d'un intervalle réel, Ann. Inst. Fourier, Grenoble 40 (1990), 885--911. MR 92j:11070
  • 2. E. Aparicio, Methods for the approximate calculation of minimum uniform Diophantine deviation from zero on a segment, Rev. Mat. Hisp.-Amer. 38 (1978), 259--270 (Spanish). MR 80i:10049
  • 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. ------, On some results in the problem of Diophantine approximation of functions by polynomials, Proc. Steklov Inst. Math. 163 (1985), 7--10. MR 86d:41001
  • 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 (M. Artin and J. Tate, eds.), Progress in Math., Vol. 35, Birkhäuser, Boston, 1983, pp. 61--105. MR 86c:11052
  • 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, Math. Surveys monographs, Vol. 17, Amer. Math. Soc., Providence, R. I., 1980. MR 81g:41011
  • 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. A. K. Lenstra, H. W. Lenstra Jr., and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), 515--534. MR 94a:12002
  • 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\H{o}, Problems and Theorems in Analysis, Volume I, Springer-Verlag, New York, 1972. MR 49:8782
  • 18. E. B. Saff and R. S. Varga, On lacunary incomplete polynomials, Math. Z. 177 (1981), 297--314. MR 83a:41008
  • 19. C. L. Siegel, The trace of totally positive and real algebraic integers, Annals of Math. 46 (1945), 302--314. MR 6:257a
  • 20. C. J. Smyth, The mean values of totally real algebraic integers, Math. Comp. 42 (1984), 663--681. MR 86e:11115
  • 21. ------, Totally positive algebraic integers of small trace, Ann. Inst. Fourier 33 (1984), 1--28. MR 86f:11091

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

American Mathematical Society