Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



On Integer Chebyshev Polynomials

Authors: Laurent Habsieger and Bruno Salvy
Journal: Math. Comp. 66 (1997), 763-770
MSC (1991): Primary 11J54, 11-04, 41A10, 41-04
MathSciNet review: 1401941
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We are concerned with the problem of minimizing the supremum norm on $\lbrack 0,1\rbrack $ of a nonzero polynomial of degree at most $n$ with integer coefficients. We use the structure of such polynomials to derive an efficient algorithm for computing them. We give a table of these polynomials for degree up to $75$ and use a value from this table to answer an open problem due to P. Borwein and T. Erdélyi and improve a lower bound due to Flammang et al.

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

  • [BE95] Peter Borwein and Tamás Erdélyi, The integer Chebyshev problem, Mathematics of Computation 65 (1996), 661-681. MR 96g:11077
  • [Ber67] Emiliano Aparicio Bernardo, Sobre la aproximación de las funciones mediante polinomios de coeficientes enteros, Actas de la Octava Reunión Anual de Matemáticos Españoles (Madrid), 1967, pp. 21-33. MR 41:4066
  • [Ber88] Emiliano Aparicio Bernardo, On the asymptotic structure of the polynomials of minimal diophantic deviation from zero, Journal of Approximation Theory 55 (1988), 270-278. MR 90b:41010
  • [Fla95] Valérie Flammang, Sur le diamètre transfini entier d'un intervalle à extrémités rationnelles, Annales de l'Institut Fourier 45 (1995), no. 3, 779-793. MR 96i:11083
  • [FRS95] V. Flammang, G. Rhin, and C. J. Smyth, The integer transfinite diameter of intervals and totally real algebraic integers, Tech. Report MS-95-033, Department of Mathematics and Statistics, University of Edinburgh, 1995.
  • [KNA94] Naoyoshi Kanamaru, Takao Nishizeki, and Tetsuo Asano, Efficient enumeration of grid points in a convex polygon and its application to integer programming, International Journal of Computational Geometry & Applications 4 (1994), no. 1, 69-85. MR 95b:90060
  • [Mon94] Hugh L. Montgomery, Ten lectures on the interface between analytic number theory and harmonic analysis, CBMS Regional Conference Series in Mathematics, vol. 84, AMS, October 1994. MR 96i:11002
  • [Nai82] M. Nair, On Chebyshev-type inequalities for primes, American Mathematical Monthly 89 (1982), no. 2, 126-129. MR 83f:10043

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11J54, 11-04, 41A10, 41-04

Retrieve articles in all journals with MSC (1991): 11J54, 11-04, 41A10, 41-04

Additional Information

Laurent Habsieger
Affiliation: Laboratoire d’Algorithmique Arithmétique, CNRS UMR 9936, Université Bordeaux 1, 351 cours de la Libération, F-33405 Talence Cedex, France

Bruno Salvy
Affiliation: INRIA Rocquencourt, Domaine de Voluceau, B.P. 105, F-78153 Le Chesnay Cedex, France

Received by editor(s): October 18, 1995
Received by editor(s) in revised form: May 3, 1996
Article copyright: © Copyright 1997 American Mathematical Society

American Mathematical Society