The Algebraic Integer Transfinite Diameter

In this paper we continue a study, recently initiated by Borwein, Pinner and Pritsker [2], of the algebric integer transfinite diameter of a real interval. We write the normalized supremum on an interval I as Note that this is not a norm. Then the algebric integer transfinite diameter is defined as where the infimum is taken over all non-constant algebric polynomials with integer coefficients. We callthe algebric integer transfinite diameter of I (also called the algebric integer Chebyshev constant [1, 2]). Clearly where denotes the integer transfinite diameter, defined using the same infimum, but taken over the larger set of all non-constant polynomials with integer coefficients [3, 4, 5]. Furtherthe capacity or transfinite diameter of I [6, 14], which can be defined again using the same infimum, but this time taken over all non-constant algebric polynomials with real coefficients. It is well known thatfor an interval I of lengthFurther, ifthenby [2] so that the challenge for evaluatingas forlies in intervals with For these intervals we knowfrom [2, Prop. 1.2] thatHowever, in contrast to the study ofin the algebric case it is possible to evaluate exactly over some such intervals. Our first result is the following. Theorem 1.1. All intervals I of length 1 haveIn fact, slightly more is true: if Furthermore for any b < 1 there is an interval I with while for h > 1.064961507 there is an interval I with The proof, which is essentially a corollary of Theorem 1.2 (a) below, is discussed in Section 5.

Available online at www.ignited.in Page 2

The numbers, 1.008848 and 1.064961507 in Theorem 1.1, like most numerical values given in this paper, are approximations to some exact algebraic number. These numbers are rounded in the correct direction, if necessary, to ensure an inequality still holds. The polynomial equations that they satisfy are given within the text. We have tried to do this for all numerical values. To measure the range of lengths of intervals having a particular algebric integer transfinite diameter t, we introduce the following two functions: It follows from [2, Prop. 1.3] that bothandare nondecreas- ing functions of t. Alsosee Lemma 3.1(a) below. We give (Proposition 3.1) general method for finding upper and lower bounds for and apply these methods to get such bounds for They are constructive, using both the LLL basis-reduction algorithm and the Simplex method. These techniques were first applied in this area by Borwein and Erdelyi [3], and then by Habsieger and Salvy [7]. These bounds are given in Theorem 4.1 and Proposition 4.1 - see also Figures 1 and 2. we pushed this method further, and were able to say more. Theorem 1.2. We have and Further properties ofandare given in Lemma 3.1.

In this section, we state some old and some more new results, and (perhaps a little recklessly) make four conjectures. The following result is simple but fundamental. It is useful for determining lower bounds for Lemma BPP (Borwein, Pinner and Pritsker [2, p.1905]). Let be a nonmonic irreducible polynomial with integer coefficients, all of whose roots lie in the interval I. Thenfor every algebric integer polynomial P, so thatFurthermore, if thenand for every root and Res The proof follows straight from the classical fact that, for the conjugates of

(1)

is a nonzero integer, giving

(2)

This result is a variant of a similar one in the theory of—see Lemma 7.1. We call such a valuein Lemma BPP an obstruction for I, with obstruction polynomial. From Lemma BPP we see thatis bounded below by the supremum of all such obstructions. If this supremum is attained by some valuecoming fromthen we sayis a maximal obstruction, andis a maximal obstruction polynomial. It is not known whether such a polynomial exists for all intervals I of length less than 4 (see Conjecture 2.3).

Available online at www.ignited.in Page 3

We say that the algebric integer polynomial P(x) is an optimal algebric integer Chebyshev polynomial for I ifIf I has a maximal ob- structionwithand an optimal algebric integer Chebyshev polynomial P then we say that P attains the maximal obstruction. Throughout this paper, P(x) will denote a algebric integer polynomial, a nonmonic integer polynomial and R x any integer polynomial. One very nice property of the algebric integer transfinite diameter problem, not shared by its nonmonic cousin, is that often exact values can be computed forIn all cases where this has been done, including Theorem 1.1, it was achieved by finding a maximal obstruction, and a corresponding optimal algebric integer Chebyshev polynomial. Simple examples of this are given ([2, Theorem 1.5]) by the intervalsforwhere is a maximal obstruction polynomial, and P x x is an optimal algebric integer Chebyshev polynomial. For n= 1,with Q{x) = 2x— 1 and P(x) =x(x^ 1). This was the case too in [2, Section 5] in the proof of the Farey Interval conjecture for small-denominator intervals. A much less obvious example is the interval I = [—0.3319,0.7412], of length 1.0731. Here, we havewith maximal obstruction polynomial 7x3 — 7x2 + 1 and where P is the optimal algebric integer Chebyshev polynomial of degree 670320. (Tighter endpoints for this interval, and its length, can be computed by solving the equationThe discovery of this polynomial required the use of Lemma 6.1 below. For the nonmonic transfinite diameterPritsker [13, Theorem1.7] has recently proved that no integer polynomial R x can attain this value being achieved only by a normalized product of infinitely many polynomials. An immediate consequence of his result is the following. Proposition 2.1. If an interval I has an optimal algebric integer Chebyshev polynomial then A fundamental question for both the algebric and nonmonic integer trans- finite diameter of an interval is whether its value can be computed exactly. In [2, Conjecture 5.1], Borwein et al make a conjecture for Farey intervals (intervalswhereand ) concerning the exact value of their algebric transfinite diameter. Conjecture BPP(Farey Interval Conjecture [1, p. 82], [2, Conjecture 5.1]). Suppose thatis a Farey interval, neither of whose endpoints is an integer. Then Borwein et al verify their conjecture for all Farey intervals having the denominatorsless than 22. In Section 8 we extend the verification to some infinite families of Farey intervals (Theorems 8.2 and 8.3). We next investigate what happens towhen b is close to For these intervals, some surprising things happen. Using the polynomial P(x) = x, we know thatIn fact it appears likely thatclearly a non-decreasing function of b, has a left discontinu ity atOn the other hand, we show in Theorem 9.1 that is locally constant on an interval of positive lengthto the right of Further,

Available online at www.ignited.in Page 4

Theorem 9.2 gives much larger values forfor n = 2,3 and 4, as well as an upper bound for In fact, more may be true. Conjecture 2.1 (Zero-endpoint Interval Conjecture). Ifis an in terval withthenwhereis the smallest integerfor which What little we know aboutfor b 1 is given in Theorem 9.2 (c), (d). Both Conjecture BPP and Conjecture 2.1 are a consequence of the following conjecture. Conjecture 2.2 (Maximal obstruction impliesConjecture). If an interval I oflength less than 4 has a maximal obstruction m, then We were at first tempted to conjecture here thatas well as equaling its maximal obstruction, is always attained by some algebric integer polynomial. However, the following counterexample eliminates this possibility in general. Counterexample 2.1. The polynomial 7x3 + 4x2 — 2x — 1 is a maximal obstruction polynomialfor the interval I = [—0.684,0.517]. However, there is nomonic integer polynomial P withequal to the maximal obstruction for I. This result is proved in Section 10. Our next result proves the existence of maximal obstructions for many intervals. Theorem 2.1. Every interval not containing an integer in its interior has a maximal obstruction. Based on Conjecture 2.2 and Theorem 2.1 we make the following conjecture. Conjecture 2.3 (Maximal Obstruction Conjecture). Every interval of length less than 4 has a maximal obstruction. We do not have much direct evidence for this conjecture. However, our next conjecture, Conjecture 2.4, implies it. To describe this implication, we need the following notion, taken from Flammang, Rhin and Smyth [5]. An irreducible polynomialwithall of whose roots lie in an interval I, and for whichis greater than the (nonmonic) transfinite diameteris called a critical polynomial for I. Here we are interested only in nonmonic critical polynomials. It may be that every interval of length less than 4 has infinitely many nonmonic critical polynomials - see Proposition 2.2 below. We make the following weaker conjecture. Conjecture 2.4 (Critical Polynomial Conjecture). Every interval of length less than 4 has at least one nonmonic critical polynomial. From Theorem 2.1 below, this conjecture is true for intervals not containing an integer. For intervals I of length less than 4 that do contain an integer (say 0), then, sincethe polynomial x is a critical polynomial for I. Thus 'nonmonic' is an important word in this conjecture. In Theorem 7.1 we prove that Conjecture 2.4 implies Conjecture 2.3. More interestingly, we also prove in Corollary 7.1 that Conjecture 2.2 and Conjecture 2.3 together imply Conjecture 2.4. We observe in passing the following conditional result for the integer transfinite diameter Proposition 2.2. Suppose that an interval I has infinitely many critical polynomialsThen This result is proved in Section 7. Montgomery [11, p.182] conjectured this result unconditionally for the interval I 0 1 .

The following lemma contains some simple properties, as well as alternative definitions, ofand

Available online at www.ignited.in Page 5

Proof. First note that, by [2, equation (1.11)],for the zero-length intervalfrom which (b) follows. Part (c) follows from the fact that To prove (d), takeThen the set contains 0 (by (b)), so is nonempty. Putand takeSince implies that([2, Prop. 1.3]), anywith also lies in S, so thatHenceOn the other hand, for each d s there is an interval I withandHence giving Now (a) follows straight from (b) and (d). The proof of (e), similar to that of (d), is left as an exercise for the reader. Finally, part (f) follows from the fact that forwe have (see for instance [2]). Next, we give a simple lemma, needed for applying Proposition 3.1 below. Lemma 3.2. Suppose that{i=1,... ,n) are intervals with and putThen (a) Any interval of length at least M contains an integer translate of some If. (b) Any interval of length at most m is contained in an integer translate of some If. Proof. Given an interval I of lengthwe can, after translation by an integer, assume thatwherefor some (a) Suppose thatThenso that (b) Suppose thatThenso that The following proposition will be used to obtain explicit upper and lower bounds forandfor particular values of t.

(a) Ifwith integer coefficients andhas roots spanning an interval of lengththen for anywe have (b) Suppose that we have a finite set of polynomialswith allwith the property that every interval of lengthcontains an integer translate of the roots of at least one of the polynomialsThen (c) Suppose that we have a finite set of intervals If such that for each If there is a algebric integer polynomial Pf withSuppose too that every interval of length I is contained in an integer translate of someThen

Available online at www.ignited.in Page 6

(d) Iffor some algebric integer polynomial P and interval I of length , then

a. Given such aand interval I of length, andthen from Lemma BPP we haveso that, from the def inition of, we have b. Suppose that every interval I of lengthcontains some integer translate of the set of roots of some. Then, by Lemma BPP, Hencefor any interval of length, and so c. Here, for every interval I of lengthwithsay, (with), we have so thatanywith. Hence. d. If andthen, so that.

• Borwein, Peter. Computational excursions in analysis and number theory, Springer- Verlag, New York, 2002. MR 03m: 11045

• P. B. Borwein, C. G. Pinner, and I. E. Pritsker, Algebric integer Chebyshev problem, Math. Comp. 72 (2003), 1901-1916. MR 04e: 11022

• Peter Borwein and Tam'as Erd'elyi, The integer Chebyshev problem, Math. Comp. 65 (1996), no. 214, 661-681. MR 96g:11077

• G. V. Chudnovsky, Number theoretic applications of polynomials with rational coefficients defined by extremality conditions. Arithmetic and geometry, Vol. I, 61-105, Progr. Math., 35, Birkhduser Boston, Boston, MA, 1983. MR 86c: 11052

• V. Flammang, G. Rhin, and C. J. Smyth, The integer transfinite diameter of intervals and totally real algebraic integers, J. Th'eor. Nombres Bordeaux 9 (1997), no. 1,137168. MR 98g: 11119

• G. M. Goluzin, Geometric theory of functions of a complex variable, Translations of Mathematical Monographs, Vol. 26, American Mathematical Society, Providence, R.I., 1969. MR 40 #308

• Laurent Habsieger and Bruno Salvy, On integer Chebyshev polynomials, Math. Comp. 66 (1997), no. 218, 763-770. MR 97f: 11053

• Kevin G. Hare, Some applications of the LLL algorithm, Proceedings from the Maple Summer Workshop, 2002, Maple Software, Waterloo, 2002.

• K. Lenstra, H. W. Lenstra, Jr., and L. Lov 'asz, Factoring polynomials with rational coefficients, Math. Ann. 261 (1982), no. 4, 515-534. MR 84a: 12002

• J.F. McKee and C.J. Smyth, Salem numbers of trace — 2 and traces of totally positive algebraic integers, Proc. 6th. Algorithmic number theory Symposium, (University of Vermont, 13 - 18 June 2004), Lecture Notes in Comput. Sci., vol. 3076, Springer, Berlin, 2004, pp. 327-337.

• Montgomery, Hugh L. Ten lectures on the interface between analytic number theory and harmonic analysis. CBMS Regional Conference Series in Mathematics, 84. American Mathematical Society, Providence, RI, 1994. MR 96i: 11002

• Igor E. Pritsker, Chebyshev polynomials with integer coefficients, Analytic and geometric inequalities and applications, Math. Appl., vol. 478, Kluwer Acad. Publ., Dordrecht, 1999, pp. 335-348. MR 2001h:30007

• Small polynomials with integer coeffi cients, J. Anal. Math, (to appear).

 Thomas Ransford, Potential theory in the complex plane, London Mathematical Society Student Texts,

Available online at www.ignited.in Page 7

vol. 28, Cambridge University Press, Cambridge, 1995. MR 96e:31001

• Raphael M. Robinson, Algebraic equations with span less than 4, Math. Comp. 18 (1964), 547-559. MR 29 #6624

• Schrijver, Theory of linear and integer programming, John Wiley & Sons Ltd., Chichester, 1986, A Wiley-Interscience Publication. MR 88m:90090

• Christopher Smyth, Totally positive algebraic integers of small trace, Ann. Inst. Fourier (Grenoble) 34 (1984), no. 3, 1-28. MR 86f: 11091

• Vladimir G. SprindZuk, Classical Diophantine equations, Lecture Notes in Mathematics, vol. 1559, Springer-Verlag, Berlin, 1993, Translated from the 1982 Russian original. MR 95g: 11017

• Weiss, Edwin. Algebraic numbertheory. McGraw-Hill Book Co., Inc., New York-San Francisco-Toronto-London 1963 (Reprinted by Dover Publications, Inc., Mineola, NY, 1998.) MR 28 #3021