Mathematics of Computation

Author(s): Peter Borwein; Tamás Erdélyi.
Journal: Math. Comp. 65 (1996), 661-681.
MSC (1991): Primary 11J54, 11B83
Retrieve article in: PDF
This article is available free of charge

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.

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 and , 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

Peter Borwein
Affiliation: Department of Mathematics and Statistics, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6
Email: pborwein@cecm.sfu.ca

Tamás Erdélyi
Affiliation: Department of Mathematics, Texas A & M University, College Station, Texas 77843
Email: terdelyi@math.tamu.edu

DOI: 10.1090/S0025-5718-96-00702-8
PII: S 0025-5718(96)00702-8
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.
Copyright of article: Copyright 1996, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2009, American Mathematical Society Privacy Statement		Search the AMS