"Science, Faculty of"@en . "Mathematics, Department of"@en . "DSpace"@en . "UBCV"@en . "Zou, Chenglong"@en . "2013-05-16T09:12:12Z"@en . "2013"@en . "Master of Science - MSc"@en . "University of British Columbia"@en . "Pupyrev's paper \"Effectivization of a Lower Bound for"@en . "(4/3)^k"@en . "\" provides partial results to the assertion that the distance from (4/3)^k to the nearest integer is at least (4/9)^k when k is at least 6. This is equivalent to a generalization of Waring's conjecture, which asks about the representation of integers as the sum of powers. In this writeup, we follow his work in order to complete his results. Part of the work depends on three constants, alpha, beta and gamma, which can be chosen almost without restriction, so we develop an algorithm that determines the best choice of constants for our purposes."@en . "https://circle.library.ubc.ca/rest/handle/2429/44477?expand=metadata"@en . "On a Generalization of Waring\u00E2\u0080\u0099s Conjecture by Chenglong Zou B.Sc, University of Waterloo, 2011 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF Master of Science in THE FACULTY OF GRADUATE STUDIES (Mathematics) The University of British Columbia (Vancouver) May 2013 c\u00C2\u00A9 Chenglong Zou, 2013 Abstract Pupyrev\u00E2\u0080\u0099s paper \u00E2\u0080\u009CEffectivization of a Lower Bound for \u00E2\u0088\u00A5\u00E2\u0088\u00A5(4/3)k\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0080\u009D provides partial results to the assertion that \u00E2\u0088\u00A5\u00E2\u0088\u00A5(4/3)k\u00E2\u0088\u00A5\u00E2\u0088\u00A5 > (4/9)k for k \u00E2\u0089\u00A5 6, which is equivalent to a generalization of Waring\u00E2\u0080\u0099s conjecture about the representation of integers as the sum of powers. In this writeup, we follow his work in order to complete his results. Part of the work depends on three constants, \u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3 which can be chosen almost without restriction, so we develop an algorithm that determines the best choice of constants for our purposes. ii Table Of Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Table Of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Computing estimates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.1 Basic estimates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Preliminaries for computing log \u00CE\u00A6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Computing log \u00CE\u00A6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3 Waring\u00E2\u0080\u0099s Conjecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.1 Effective Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.2 Computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 iii List of Tables 3.1 Values of Ak, Bk,min(Ck, Ak \u00E2\u0088\u0092 Ck) and Dk . . . . . . . . . . . . . . . . . . . . . . . 18 iv Chapter 1 Introduction 1.1 Background Waring\u00E2\u0080\u0099s problem concerns the function g(k), where g(k) is defined to be such that any integer can be written as the sum of at most g(k) k-th powers. By considering the integer[( 3 2 )k] \u00C2\u00B7 2k \u00E2\u0088\u0092 1 = ([( 3 2 )k] \u00E2\u0088\u0092 1 ) \u00C2\u00B7 2k + (2k \u00E2\u0088\u0092 1) \u00C2\u00B7 1k, we have the lower bound g(k) \u00E2\u0089\u00A5 2k + [( 3 2 )k] \u00E2\u0088\u0092 2, where [x] denotes the largest integer less than or equal to x. Waring\u00E2\u0080\u0099s conjecture asserts that the inequality is in fact an equality, and it is known that{( 3 2 )k} \u00E2\u0089\u00A4 1\u00E2\u0088\u0092 ( 3 4 )k (1.1) implies this conjecture. Here {x} denotes the fractional part of x, i.e. x = [x]+{x}. A generalization of Waring\u00E2\u0080\u0099s problem (for example, see Bennett[1]) concerns the function gN (k), defined to be such that any integer can be written as the sum of at most gN (k) k-th powers from the set {1, Nk, (N + 1)K , . . .}, and here g2(k) = g(k). The analogous conjecture for N \u00E2\u0089\u00A5 3 is that when k \u00E2\u0089\u00A5 6, gN (k) = N k + [( N + 1 N )k] \u00E2\u0088\u0092 2, and this is equivalent to the inequality\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5 ( N + 1 N )k\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5 \u00E2\u0089\u00A5 ( N + 1 N2 )k , (1.2) 1 where \u00E2\u0080\u0096x\u00E2\u0080\u0096 denotes the distance from x to the closest integer, i.e. \u00E2\u0080\u0096x\u00E2\u0080\u0096 = min({x}, 1\u00E2\u0088\u0092 {x}). In 1957, Mahler[2] showed that for any 0 \u00E2\u0089\u00A4 C < 1, there exists a constant k0 = k0(C) depending on C such that \u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5(3/2)k\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5 > Ck (1.3) when k \u00E2\u0089\u00A5 k0, however this constant is ineffective. For the case of g(k), finding an effective k0 for C = 0.75, combined with computational work would imply (1.1). Thus there has been significant effort put into finding values of C with effective k0. The first non-trivial result is due to Baker and Coates[3], who obtained effective bounds for (1.3) with C = 2\u00E2\u0088\u0092(1\u00E2\u0088\u009210 64). Later, Beukers[4] improved on this result and obtained proved (1.3) for C = 2\u00E2\u0088\u00920.9, by using Pade\u00CC\u0081 ap- proximations of binomial series. Similar strategies have since been used; Dubitkas[5], Habsieger[6], Zudilin[7] and Pupyrev[8] have all obtained such results using the Pade\u00CC\u0081 approximations of bino- mial power series, although none have succeeded in obtaining C \u00E2\u0089\u00A5 0.75 so far. Supplementing these results are the work of Delmer and Deshouillers[9], who described and analyzed an algorithm for calculating values of g(k), and Kubina and Wunderlich[10], who computationally verified the inequality for k \u00E2\u0089\u00A4 471600000. Regarding (1.2), Both Zudilin and Pupyrev previously showed that\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5 ( 4 3 )k\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5 > Ck holds with C = 0.4914 and C = 0.4910 respectively for sufficiently large k \u00E2\u0089\u00A5 k0, with effective k0 in both cases. However, the constants that follows from the proofs are on the order of 1018, making a computational approach to complete a proof of (1.2) for N = 3 time-consuming, as Kubina and Wunderlich stated to have taken 240 hours of computation in their paper. Instead, by relaxing the constant C obtained, we can significantly reduce the order of k0. By adapting the proof used by Pupyrev, we will prove the following result: Theorem 1. Let k0 = 2207008. Then for any k > k0,\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5 ( 4 3 )k\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5 > 0.4456k. We also check computationally that for 1 < k \u00E2\u0089\u00A4 2207008,\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5 ( 4 3 )k\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5 > ( 4 9 )k by adapting the algorithm by Delmer and Deshouillers. By combining these results, we have the following: Theorem 2. Let k \u00E2\u0089\u00A5 6. Then g3(k) = 3 k + [ 4 3 ]k \u00E2\u0088\u0092 2. 2 1.2 Preliminaries To estimate {(4/3)k}, we use the identity 1 (1\u00E2\u0088\u0092 z)m+1 = \u00E2\u0088\u009E\u00E2\u0088\u0091 n=0 ( m+ n m ) zn, valid for z \u00E2\u0088\u0088 (1,\u00E2\u0088\u00921). With z = 4/3, we have Lemma 1. Suppose a, b are integers such that 3a \u00E2\u0089\u00A4 b. Then( 4 3 )2(b+1) \u00E2\u0088\u0092 2b\u00E2\u0088\u00923a+1(\u00E2\u0088\u00921)a \u00E2\u0088\u009E\u00E2\u0088\u0091 \u00CE\u00BD=0 ( a+ b+ \u00CE\u00BD b )( \u00E2\u0088\u00921 8 )\u00CE\u00BD is an integer. Proof. We have the following sequence of manipulations:( 4 3 )2(b+1) = ( 16 9 )b+1 = 2b+1 ( 1 + 1 8 )\u00E2\u0088\u0092(b+1) = 2b+1 \u00E2\u0088\u009E\u00E2\u0088\u0091 l=0 ( b+ l b )( 1 8 )l (\u00E2\u0088\u00921)l = 2b\u00E2\u0088\u00923a+1 \u00E2\u0088\u009E\u00E2\u0088\u0091 l=0 ( b+ l b ) 23(a\u00E2\u0088\u0092l)(\u00E2\u0088\u00921)\u00E2\u0088\u0092l = 2b\u00E2\u0088\u00923a+1(\u00E2\u0088\u00921)a \u00E2\u0088\u009E\u00E2\u0088\u0091 l=0 ( b+ l b ) 23(a\u00E2\u0088\u0092l)(\u00E2\u0088\u00921)a\u00E2\u0088\u0092l = 2b\u00E2\u0088\u00923a+1(\u00E2\u0088\u00921)a ( a\u00E2\u0088\u00921\u00E2\u0088\u0091 l=0 ( b+ l b ) 23(a\u00E2\u0088\u0092l)(\u00E2\u0088\u00921)a\u00E2\u0088\u0092l + \u00E2\u0088\u009E\u00E2\u0088\u0091 l=a ( b+ l b ) 23(a\u00E2\u0088\u0092l)(\u00E2\u0088\u00921)a\u00E2\u0088\u0092l ) . The left sum is clearly an integer, hence reindexing the right sum with l = \u00CE\u00BD + a gives( 4 3 )2(b+1) \u00E2\u0088\u0092 2b\u00E2\u0088\u00923a+1(\u00E2\u0088\u00921)a \u00E2\u0088\u009E\u00E2\u0088\u0091 \u00CE\u00BD=0 ( b+ a+ \u00CE\u00BD b )( \u00E2\u0088\u00921 8 )\u00CE\u00BD \u00E2\u0088\u0088 Z. Hence, the magnitude of \u00E2\u0088\u00A5\u00E2\u0088\u00A5(4/3)2(b+1)\u00E2\u0088\u00A5\u00E2\u0088\u00A5 can be determined by studying the magnitude of\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5 \u00E2\u0088\u009E\u00E2\u0088\u0091 \u00CE\u00BD=0 ( b+ a+ \u00CE\u00BD b )( \u00E2\u0088\u00921 8 )\u00CE\u00BD\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5 , so we will consider the function F (z) = F (a, b; z) = \u00E2\u0088\u009E\u00E2\u0088\u0091 \u00CE\u00BD=0 ( a+ b+ \u00CE\u00BD b ) z\u00CE\u00BD , and estimate the magnitude of \u00E2\u0080\u0096F (\u00E2\u0088\u00921/8)\u00E2\u0080\u0096. To accomplish this, we have the following two lemmas from Zudilin [7] (see Lemma 1 and Lemma 3): 3 Lemma 2. Suppose n \u00E2\u0088\u0088 Z with n \u00E2\u0089\u00A4 b. Define Qn(z\u00E2\u0088\u00921) to be such that Qn(z \u00E2\u0088\u00921) = (a+ b+ n)! (a+ n\u00E2\u0088\u0092 1)!n!(b\u00E2\u0088\u0092 n)! \u00E2\u0088\u00AB 1 0 ta+n+1(1\u00E2\u0088\u0092 t)b\u00E2\u0088\u0092n(1\u00E2\u0088\u0092 z\u00E2\u0088\u00921t)n dt, and Rn(z) such that Rn(z) = (a+ b+ n)! (a+ n\u00E2\u0088\u0092 1)!n!(b\u00E2\u0088\u0092 n)!z n \u00E2\u0088\u00AB 1 0 tn(1\u00E2\u0088\u0092 t)a+n\u00E2\u0088\u00921(1\u00E2\u0088\u0092 zt)\u00E2\u0088\u0092(a+b+n)\u00E2\u0088\u00921 dt. Then Qn(z), Rn(z) \u00E2\u0088\u0088 Z[x], and there exists a polynomial Pn(z) \u00E2\u0088\u0088 Z[x] such that Qn(z \u00E2\u0088\u00921)F (z) = Pn(z\u00E2\u0088\u00921) +Rn(z). (1.4) Finally, to refine the estimate further, we may factor out prime factors of Qn(z), Pn(z) as follows: Lemma 3. Let a, b, n be given. For p > \u00E2\u0088\u009A a+ b+ n, define ep,n = min \u00C2\u00B5\u00E2\u0088\u0088Z ( \u00E2\u0088\u0092 { \u00E2\u0088\u0092a+ n p } + {\u00E2\u0088\u0092a+ n+ \u00C2\u00B5 p } + { \u00C2\u00B5 p } \u00E2\u0088\u0092 { a+ b+ n p } + { a+ b+ \u00C2\u00B5 p } + { n\u00E2\u0088\u0092 \u00C2\u00B5 p }) , and \u00CE\u00A6 = \u00CE\u00A6(a, b, n) = \u00E2\u0088\u008F p> \u00E2\u0088\u009A a+b+n pep,n . Then \u00CE\u00A6\u00E2\u0088\u00921Qn(z),\u00CE\u00A6\u00E2\u0088\u00921Pn(z) \u00E2\u0088\u0088 Z[x]. 4 Chapter 2 Computing estimates 2.1 Basic estimates To estimate the bound on \u00E2\u0088\u00A5\u00E2\u0088\u00A5(4/3)k\u00E2\u0088\u00A5\u00E2\u0088\u00A5, we will henceforth assume the following about a, b and n: write a = \u00CE\u00B1m, b = \u00CE\u00B2m and n = \u00CE\u00B3m, with the condition that \u00CE\u00B3, \u00CE\u00B2\u00E2\u0088\u0092 \u00CE\u00B3 \u00E2\u0089\u00A5 2. First, we use Lemma 2 and the relation in Lemma 1 to relate \u00E2\u0088\u00A5\u00E2\u0088\u00A5(4/3)k\u00E2\u0088\u00A5\u00E2\u0088\u00A5 and the magnitudes of Qn(\u00E2\u0088\u00928) and Rn(\u00E2\u0088\u00921/8). Lemma 4. Suppose k \u00E2\u0089\u00A5 3, and write k = 2(\u00CE\u00B2m+ 1) + j, where 0 \u00E2\u0089\u00A4 j < 2\u00CE\u00B2. If\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3Rn(\u00E2\u0088\u009218 ) \u00CE\u00A6\u00E2\u0088\u009212b\u00E2\u0088\u00923a+1+2j(\u00E2\u0088\u00921)a \u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3 < 23 , (2.1) then we have the bound \u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5(4/3)k\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5 > \u00CE\u00A6 32\u00CE\u00B2|Qn(\u00E2\u0088\u00928)| . (2.2) Proof. Using (1.4), at z = \u00E2\u0088\u00921/8 and multiply through by \u00CE\u00A6\u00E2\u0088\u009212b\u00E2\u0088\u00923a+1+2j(\u00E2\u0088\u00921)a, we have Qn(\u00E2\u0088\u00928)\u00CE\u00A6\u00E2\u0088\u009213j ( 4 3 )j 2b\u00E2\u0088\u00923a+1(\u00E2\u0088\u00921)aF ( a, b,\u00E2\u0088\u00921 8 ) = Pn(\u00E2\u0088\u00928)\u00CE\u00A6\u00E2\u0088\u009212b\u00E2\u0088\u00923a+1+2j(\u00E2\u0088\u00921)a + Rn ( \u00E2\u0088\u00921 8 ) \u00CE\u00A6\u00E2\u0088\u009212b\u00E2\u0088\u00923a+1+2j(\u00E2\u0088\u00921)a. Applying Lemma 1 with k = 2(b+ 1) + j, we have( 4 3 )j 2b\u00E2\u0088\u00923a+1(\u00E2\u0088\u00921)aF ( a, b,\u00E2\u0088\u00921 8 ) \u00E2\u0088\u0092 ( 4 3 )k \u00E2\u0088\u0088 Z. Thus Qn(\u00E2\u0088\u00928)\u00CE\u00A6\u00E2\u0088\u009213j \u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5(4/3)k\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5 = Mk +Rn(\u00E2\u0088\u00921 8 ) \u00CE\u00A6\u00E2\u0088\u009212b\u00E2\u0088\u00923a+1+2j(\u00E2\u0088\u00921)a for some integer Mk \u00E2\u0088\u0088 Z. Hence if (2.1) holds,\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3Qn(\u00E2\u0088\u00928)\u00CE\u00A6\u00E2\u0088\u009213j \u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5(4/3)k\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3 \u00E2\u0089\u00A5 |Mk| \u00E2\u0088\u0092 \u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3Rn(\u00E2\u0088\u009218 ) \u00CE\u00A6\u00E2\u0088\u009212b\u00E2\u0088\u00923a+1+2j(\u00E2\u0088\u00921)a \u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3 > 13 , 5 and rearranging gives the desired conclusion:\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5(4/3)k\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5 > \u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3 \u00CE\u00A63j+1Qn(\u00E2\u0088\u00928) \u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3 \u00E2\u0089\u00A5 \u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3 \u00CE\u00A632\u00CE\u00B2Qn(\u00E2\u0088\u00928) \u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3 . To estimate the magnitudes of Qn(\u00E2\u0088\u00928) and Rn(\u00E2\u0088\u00921/8), we use their integral representations as seen in Lemma 2. However, instead of looking at Qn(\u00E2\u0088\u00928), Rn(\u00E2\u0088\u00921/8) directly, we will estimate the logarithm of these values. We begin by bounding the factorial coefficient in their representations. Lemma 5. Given \u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3,m \u00E2\u0088\u0088 Z, with \u00CE\u00B3, \u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3 \u00E2\u0089\u00A5 2, we have log ( (\u00CE\u00B1m+ \u00CE\u00B2m+ \u00CE\u00B3m)! (\u00CE\u00B1m+ \u00CE\u00B3m\u00E2\u0088\u0092 1)!(\u00CE\u00B3m)!(\u00CE\u00B2m\u00E2\u0088\u0092 \u00CE\u00B3m)! ) \u00E2\u0089\u00A4 mA(\u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3) + log(\u00CE\u00B1+ \u00CE\u00B3), (2.3) where the function A(\u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3) is given by A(\u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3) = (\u00CE\u00B1+ \u00CE\u00B2 + \u00CE\u00B3) log(\u00CE\u00B1+ \u00CE\u00B2 + \u00CE\u00B3)\u00E2\u0088\u0092 (\u00CE\u00B1+ \u00CE\u00B3) log(\u00CE\u00B1+ \u00CE\u00B3)\u00E2\u0088\u0092 \u00CE\u00B3 log \u00CE\u00B3 \u00E2\u0088\u0092 (\u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3) log(\u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3). Proof. Denote the quantity on the left hand side of (2.3) by L. Using Stirling\u00E2\u0080\u0099s formula (see Abramowitz[11]), given by log((s\u00E2\u0088\u0092 1)!) = log \u00CE\u0093(s) = ( s\u00E2\u0088\u0092 1 2 ) log s\u00E2\u0088\u0092 s+ log \u00E2\u0088\u009A 2pi + 2 \u00E2\u0088\u00AB \u00E2\u0088\u009E 0 arctan( ts) e2pit \u00E2\u0088\u0092 1 dt, valid for s > 0, and applying it to L gives us L = m(\u00CE\u00B1+ \u00CE\u00B2 + \u00CE\u00B3) log(m(\u00CE\u00B1+ \u00CE\u00B2 + \u00CE\u00B3) + 1) + 1 2 log(m(\u00CE\u00B1+ \u00CE\u00B2 + \u00CE\u00B3) + 1) \u00E2\u0088\u0092m(\u00CE\u00B1+ \u00CE\u00B3) log(m(\u00CE\u00B1+ \u00CE\u00B3)) + 1 2 log(m(\u00CE\u00B1+ \u00CE\u00B3)) \u00E2\u0088\u0092m\u00CE\u00B3 log(m\u00CE\u00B3 + 1)\u00E2\u0088\u0092 1 2 log(m\u00CE\u00B3 + 1) \u00E2\u0088\u0092m(\u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3) log(m(\u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3) + 1)\u00E2\u0088\u0092 1 2 log(m(\u00CE\u00B2 + \u00CE\u00B3) + 1) \u00E2\u0088\u0092 log(2pi) + 1 + I, (2.4) where I = 2 \u00E2\u0088\u00AB \u00E2\u0088\u009E 0 1 e2pit \u00E2\u0088\u0092 1 ( arctan ( t a+ b+ c+ 1 ) \u00E2\u0088\u0092 arctan ( t a+ c ) \u00E2\u0088\u0092 arctan ( t c+ 1 ) \u00E2\u0088\u0092 arctan ( t b\u00E2\u0088\u0092 c+ 1 )) dt. By observation, we see I is negative. Considering the inequalities x\u00E2\u0088\u0092 x 2 2 \u00E2\u0089\u00A4 log(1 + x) \u00E2\u0089\u00A4 x, valid for x \u00E2\u0088\u0088 (0, 1), and combining it with the identity log(n+ 1) = log n+ log ( 1 + 1 n ) , 6 we have log n+ 1 n \u00E2\u0088\u0092 1 2n2 \u00E2\u0089\u00A4 log(n+ 1) \u00E2\u0089\u00A4 log n+ 1 n , valid for n > 1. Applying these inequalities to (2.4) gives us L \u00E2\u0089\u00A4 m(\u00CE\u00B1+ \u00CE\u00B2 + \u00CE\u00B3) log(\u00CE\u00B1+ \u00CE\u00B2 + \u00CE\u00B3) +m(\u00CE\u00B1+ \u00CE\u00B2 + \u00CE\u00B3) logm+ 1 + 1 2 log(m(\u00CE\u00B1+ \u00CE\u00B2 + \u00CE\u00B3)) + 1 2m(\u00CE\u00B1+ \u00CE\u00B2 + \u00CE\u00B3) \u00E2\u0088\u0092m(\u00CE\u00B1+ \u00CE\u00B3) log(\u00CE\u00B1+ \u00CE\u00B3)\u00E2\u0088\u0092m(\u00CE\u00B1+ \u00CE\u00B3) logm+ 1 2 log(m(\u00CE\u00B1+ \u00CE\u00B3)) \u00E2\u0088\u0092m\u00CE\u00B3 log \u00CE\u00B3 \u00E2\u0088\u0092m\u00CE\u00B3 logm\u00E2\u0088\u0092 1 + 1 2m\u00CE\u00B3 \u00E2\u0088\u0092 1 2 logm\u00CE\u00B3 \u00E2\u0088\u0092 1 2m\u00CE\u00B3 + 1 4(m\u00CE\u00B3)2 \u00E2\u0088\u0092m(\u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3) log(\u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3)\u00E2\u0088\u0092m(\u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3) logm\u00E2\u0088\u0092 1 + 1 2m(\u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3) \u00E2\u0088\u0092 1 2 log(m(\u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3))\u00E2\u0088\u0092 1 2m(\u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3) + 1 4(m(\u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3))2 \u00E2\u0088\u0092 log 2pi + 1. Collecting appropriate terms gives us L \u00E2\u0089\u00A4 mA(\u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3) + 1 2 (log(\u00CE\u00B1+ \u00CE\u00B2 + \u00CE\u00B3) + log(\u00CE\u00B1+ \u00CE\u00B3)\u00E2\u0088\u0092 log \u00CE\u00B3 \u00E2\u0088\u0092 log(\u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3)) + 1 2m(\u00CE\u00B1+ \u00CE\u00B2 + \u00CE\u00B3) + 1 4(m\u00CE\u00B3)2 + 1 4(m(\u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3))2 \u00E2\u0088\u0092 log 2pi. Using the inequality log(x+ y) \u00E2\u0089\u00A4 log x+ log y, we have 1 2 (log(\u00CE\u00B1+ \u00CE\u00B2 + \u00CE\u00B3) + log(\u00CE\u00B1+ \u00CE\u00B3)\u00E2\u0088\u0092 log \u00CE\u00B3 \u00E2\u0088\u0092 log(\u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3) \u00E2\u0089\u00A4 log(\u00CE\u00B1+ \u00CE\u00B3) + 1 2 (log((\u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3) + \u00CE\u00B3)\u00E2\u0088\u0092 log \u00CE\u00B3 \u00E2\u0088\u0092 log(\u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3)) \u00E2\u0089\u00A4 log(\u00CE\u00B1+ \u00CE\u00B3), and 1 2m(\u00CE\u00B1+ \u00CE\u00B2 + \u00CE\u00B3) + 1 4(m\u00CE\u00B3)2 + 1 4(m(\u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3))2 \u00E2\u0089\u00A4 1 \u00E2\u0089\u00A4 log 2pi, hence the result follows. The next step is to bound both integrals. Lemma 6. Given \u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3,m \u00E2\u0088\u0088 Z with \u00CE\u00B3, \u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3 \u00E2\u0089\u00A5 2, and z < 0, we have\u00E2\u0088\u00AB 1 0 t(\u00CE\u00B1+\u00CE\u00B3)m\u00E2\u0088\u00921(1\u00E2\u0088\u0092 t)(\u00CE\u00B2\u00E2\u0088\u0092\u00CE\u00B3)m(1\u00E2\u0088\u0092 z\u00E2\u0088\u00921t)\u00CE\u00B3m dt \u00E2\u0089\u00A4Mm\u00E2\u0088\u009211 \u00CE\u00B41, and \u00E2\u0088\u00AB 1 0 t\u00CE\u00B3m(1\u00E2\u0088\u0092 t)(\u00CE\u00B1+\u00CE\u00B3)m\u00E2\u0088\u00921(1\u00E2\u0088\u0092 zt)\u00E2\u0088\u0092(\u00CE\u00B1+\u00CE\u00B2+\u00CE\u00B3)m\u00E2\u0088\u00921 dt \u00E2\u0089\u00A4Mm\u00E2\u0088\u009212 \u00CE\u00B42, 7 where M1 = max t\u00E2\u0088\u0088[0,1] |t\u00CE\u00B1+\u00CE\u00B3(1\u00E2\u0088\u0092 t)\u00CE\u00B2\u00E2\u0088\u0092\u00CE\u00B3(1\u00E2\u0088\u0092 z\u00E2\u0088\u00921t)\u00CE\u00B3 |, M2 = max t\u00E2\u0088\u0088[0,1] |t\u00CE\u00B3(1\u00E2\u0088\u0092 t)\u00CE\u00B1+\u00CE\u00B3(1\u00E2\u0088\u0092 zt)\u00E2\u0088\u0092(\u00CE\u00B1+\u00CE\u00B2+\u00CE\u00B3)|, \u00CE\u00B41 = \u00E2\u0088\u00AB 1 0 t\u00CE\u00B1+\u00CE\u00B3\u00E2\u0088\u00921(1\u00E2\u0088\u0092 t)\u00CE\u00B2\u00E2\u0088\u0092\u00CE\u00B3(1\u00E2\u0088\u0092 z\u00E2\u0088\u00921t)\u00CE\u00B3 dt, \u00CE\u00B42 = \u00E2\u0088\u00AB 1 0 t\u00CE\u00B3(1\u00E2\u0088\u0092 t)\u00CE\u00B1+\u00CE\u00B3\u00E2\u0088\u00921(1\u00E2\u0088\u0092 zt)\u00E2\u0088\u0092(\u00CE\u00B1+\u00CE\u00B2+\u00CE\u00B3)\u00E2\u0088\u00921 dt. Proof. This follows from the triangle inequality. Thus, we have the following estimates for Qn(z \u00E2\u0088\u00921), Rn(z): Lemma 7. Given a, b, n, z, write a = \u00CE\u00B1m, b = \u00CE\u00B2m, n = \u00CE\u00B3m for \u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3,m \u00E2\u0088\u0088 Z, and suppose \u00CE\u00B3, \u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3 \u00E2\u0089\u00A5 2. Suppose also that z < 0. Then log |Qn(z\u00E2\u0088\u00921)| \u00E2\u0089\u00A4 m(A(\u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3) + logM1) + log(\u00CE\u00B1+ \u00CE\u00B3) + log \u00CE\u00B41 \u00E2\u0088\u0092 logM1, (2.5) and log |Rn(z)| \u00E2\u0089\u00A4 m(A(\u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3) + logM2 + \u00CE\u00B3 log z) + log(\u00CE\u00B1+ \u00CE\u00B3) + log \u00CE\u00B42 \u00E2\u0088\u0092 logM2. (2.6) Here, the values M1,M2, \u00CE\u00B41, \u00CE\u00B42 depend on z. Combining these estimates with Lemma 4 gives us a lower bound for \u00E2\u0088\u00A5\u00E2\u0088\u00A5(4/3)k\u00E2\u0088\u00A5\u00E2\u0088\u00A5, along with a necessary condition for the bound to be valid. Lemma 8. Let \u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3 \u00E2\u0088\u0088 Z be given with \u00CE\u00B3, \u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3 \u00E2\u0089\u00A5 2. If m(A(\u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3) + logM2 + (\u00CE\u00B2 \u00E2\u0088\u0092 3\u00CE\u00B1\u00E2\u0088\u0092 3\u00CE\u00B3) log 2)\u00E2\u0088\u0092 log \u00CE\u00A6 < 0, (2.7) then for sufficiently large m, if k = (2\u00CE\u00B2m+ 1) + j for some 0 \u00E2\u0089\u00A4 j < 2\u00CE\u00B2, log \u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5(4/3)k\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5 > m(logM1 \u00E2\u0088\u0092A(\u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3)) + log \u00CE\u00A6. (2.8) Proof. From Lemma 4, taking logarithms on both sides of (2.1) gives log \u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3Rn(\u00E2\u0088\u009218 ) \u00CE\u00A6\u00E2\u0088\u009212b\u00E2\u0088\u00923a \u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3\u00E2\u0088\u00A3+O(1) < 0, so (2.6) implies (2.7) for sufficiently large m. Hence taking logarithms on both sides of (2.2) gives log \u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5(4/3)k\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5 > log \u00CE\u00A6\u00E2\u0088\u0092 log |Qn(\u00E2\u0088\u00928)|+O(1), which implies (2.8). 8 At this stage, we recall that \u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3 are not yet fixed, so we want to pick \u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3 so that both inequalities are satisfied, which requires computing the constants A(\u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3),M1,M2,\u00CE\u00A6 given arbi- trary \u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3. A(\u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3) is a value that can be computed directly, and M1,M2 may also be computed directly since d dt log ( t\u00CE\u00B1+\u00CE\u00B3(1\u00E2\u0088\u0092 t)\u00CE\u00B2\u00E2\u0088\u0092\u00CE\u00B3(1\u00E2\u0088\u0092 z\u00E2\u0088\u00921t)\u00CE\u00B3 ) = \u00CE\u00B1+ \u00CE\u00B3 t \u00E2\u0088\u0092 \u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3 1\u00E2\u0088\u0092 t \u00E2\u0088\u0092 z\u00E2\u0088\u00921\u00CE\u00B3 1\u00E2\u0088\u0092 z\u00E2\u0088\u00921t , and d dt log ( t\u00CE\u00B3(1\u00E2\u0088\u0092 t)\u00CE\u00B1+\u00CE\u00B3(1\u00E2\u0088\u0092 zt)\u00E2\u0088\u0092(\u00CE\u00B1+\u00CE\u00B2+\u00CE\u00B3) ) = \u00CE\u00B3 t \u00E2\u0088\u0092 \u00CE\u00B1+ \u00CE\u00B3 1\u00E2\u0088\u0092 t + z(\u00CE\u00B1+ \u00CE\u00B2 + \u00CE\u00B3) 1\u00E2\u0088\u0092 zt , hence calculating the values of t that maximizes M1,M2 is equivalent to determining the zeroes of certain quadratic equations. Therefore determining bounds for log \u00CE\u00A6 given arbitrary \u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3 is the non-trivial element to optimizing effective bounds for \u00E2\u0088\u00A5\u00E2\u0088\u00A5(4/3)k\u00E2\u0088\u00A5\u00E2\u0088\u00A5. 2.2 Preliminaries for computing log \u00CE\u00A6 To estimate log \u00CE\u00A6, recall from Lemma 3 that \u00CE\u00A6 is the product of primes p such that ep,n = 1. Using this fact, we can bound log \u00CE\u00A6 using the Chebyshev function \u00CE\u00B8(x): Lemma 9. Define \u00CF\u0095(x) to be \u00CF\u0095(x) = min y\u00E2\u0088\u0088[0,1) (\u00E2\u0088\u0092{(\u00CE\u00B1+ \u00CE\u00B3)x}+ {\u00E2\u0088\u0092(\u00CE\u00B1+ \u00CE\u00B3)x\u00E2\u0088\u0092 y}+ {y} \u00E2\u0088\u0092 {(\u00CE\u00B1+ \u00CE\u00B2 + \u00CE\u00B3)x}+ {(\u00CE\u00B1+ \u00CE\u00B2)x+ y}+ {\u00CE\u00B3x\u00E2\u0088\u0092 y}), so that \u00CF\u0095(m/p) = en,p. Then if \u00CF\u0095(x) = 1 for x \u00E2\u0088\u0088 \u00E2\u008B\u0083 i (ai, bi) \u00E2\u008A\u0086 (0, 1), we have the bound log \u00CE\u00A6 \u00E2\u0089\u00A5 [ \u00E2\u0088\u009A m/(\u00CE\u00B1+\u00CE\u00B2+\u00CE\u00B3)]\u00E2\u0088\u00921\u00E2\u0088\u0091 N=0 \u00E2\u0088\u0091 i ( \u00CE\u00B8 ( m ai +N ) \u00E2\u0088\u0092 \u00CE\u00B8 ( m bi +N )) , (2.9) where \u00CE\u00B8(x) is the Chebyshev function, i.e. \u00CE\u00B8(x) = \u00E2\u0088\u0091 p\u00E2\u0089\u00A4x log p. Proof. Suppose p \u00E2\u0088\u0088 ( m bi +N , m ai +N ) . Then rearranging gives ai +N < m p < bi +N, 9 hence en,p = 1. Since we also require p > \u00E2\u0088\u009A a+ b+ n, we must have m/N > \u00E2\u0088\u009A a+ b+ n, hence if p \u00E2\u0088\u0088 \u00E2\u0088\u009A m/(\u00CE\u00B1+\u00CE\u00B2+\u00CE\u00B3)\u00E2\u008B\u0083 N=0 \u00E2\u008B\u0083 i ( m bi +N , m ai +N ) , en,p = 1 or equivalently, p divides log \u00CE\u00A6. The desired result then follows from the identity log \u00EF\u00A3\u00AB\u00EF\u00A3\u00AD \u00E2\u0088\u008F p\u00E2\u0088\u0088(x,y) p \u00EF\u00A3\u00B6\u00EF\u00A3\u00B8 = \u00CE\u00B8(y)\u00E2\u0088\u0092 \u00CE\u00B8(x). Thus, understand the magnitude log \u00CE\u00A6 first requires understanding when \u00CF\u0095(x) = 1. From the definition of \u00CF\u0095(x), this can be understood by knowing when a equation of the form {\u00CE\u00B41 + y}+ {\u00CE\u00B42 \u00E2\u0088\u0092 y}+ {\u00CE\u00B41 + \u00CE\u00B42} = 1 holds, given arbitrary \u00CE\u00B41, \u00CE\u00B42. The following lemmas establish these conditions. Lemma 10. Let 0 \u00E2\u0089\u00A4 \u00CE\u00B4 < 1. Then for x \u00E2\u0088\u0088 [0, 1), {\u00CE\u00B4 \u00E2\u0088\u0092 x}+ {x} \u00E2\u0088\u0092 \u00CE\u00B4 = 1 (2.10) if and only if x \u00E2\u0088\u0088 (\u00CE\u00B4, 1). Proof. The left hand side of (2.10) is a function whose range is {0, 1}, and discontinuous only at x = \u00CE\u00B4. If x \u00E2\u0089\u00A4 \u00CE\u00B4, {\u00CE\u00B4 \u00E2\u0088\u0092 x}+ {x} \u00E2\u0088\u0092 {\u00CE\u00B4} = \u00CE\u00B4 \u00E2\u0088\u0092 x+ x\u00E2\u0088\u0092 \u00CE\u00B4 = 0, hence we must have x \u00E2\u0088\u0088 (\u00CE\u00B4, 1). To prove sufficiency, write x = \u00CE\u00B4 + \u00CE\u00B5, where \u00CE\u00B5 > 0 is sufficiently small. Then {\u00CE\u00B4 \u00E2\u0088\u0092 x}+ {x} \u00E2\u0088\u0092 {\u00CE\u00B4} = 1\u00E2\u0088\u0092 \u00CE\u00B5+ \u00CE\u00B4 + \u00CE\u00B5\u00E2\u0088\u0092 \u00CE\u00B4 = 1, hence by continuity, (2.10) holds when x \u00E2\u0088\u0088 (\u00CE\u00B4, 1). By using a substitution, we have the following: Lemma 11. Let 0 \u00E2\u0089\u00A4 \u00CE\u00B41, \u00CE\u00B42 < 1. Then for x \u00E2\u0088\u0088 [0, 1), {\u00CE\u00B41 \u00E2\u0088\u0092 x}+ {\u00CE\u00B42 + x} \u00E2\u0088\u0092 {\u00CE\u00B41 + \u00CE\u00B42} = 1 (2.11) if and only if x \u00E2\u0088\u0088 \u00EF\u00A3\u00B1\u00EF\u00A3\u00B2\u00EF\u00A3\u00B3(\u00CE\u00B41, 1\u00E2\u0088\u0092 \u00CE\u00B42) if \u00CE\u00B41 + \u00CE\u00B42 < 1,[0, 1\u00E2\u0088\u0092 \u00CE\u00B42) \u00E2\u0088\u00AA (\u00CE\u00B41, 1) otherwise. Proof. Write x = y \u00E2\u0088\u0092 \u00CE\u00B42 and substitute into (2.11). Then by Lemma 10, we have equality if and only y \u00E2\u0088\u0088 ({\u00CE\u00B41 + \u00CE\u00B42}, 1). Now, if \u00CE\u00B41 + \u00CE\u00B42 < 1, then this is equivalent to \u00CE\u00B41 < x < 1\u00E2\u0088\u0092 \u00CE\u00B42. Otherwise, we have \u00CE\u00B41 \u00E2\u0088\u0092 1 < x < 1\u00E2\u0088\u0092 \u00CE\u00B42, which is equivalent modulo Z to x \u00E2\u0088\u0088 [0, 1\u00E2\u0088\u0092 \u00CE\u00B42) \u00E2\u0088\u00AA (\u00CE\u00B41, 1). 10 We these lemmas at hand, we may now apply this to the generalized form of \u00CF\u0095(x): Lemma 12. Let p, q, r \u00E2\u0088\u0088 Z, 0 \u00E2\u0089\u00A4 x < 1. Then min y\u00E2\u0088\u0088[0,1) {px\u00E2\u0088\u0092 y}+ {y} \u00E2\u0088\u0092 {px}+ {qx\u00E2\u0088\u0092 y}+ {rx+ y} \u00E2\u0088\u0092 {(q + r)x} = 1 (2.12) if and only if {px} < 1\u00E2\u0088\u0092 {rx} < {qx}. Proof. Note that (2.12) holds if and only if one of {px\u00E2\u0088\u0092 y}+ {y} \u00E2\u0088\u0092 {px} = 1 (2.13) or {qx\u00E2\u0088\u0092 y}+ {rx+ y} \u00E2\u0088\u0092 {(q + r)x} = 1 (2.14) holds for every choice of y \u00E2\u0088\u0088 [0, 1). From Lemma 10 and Lemma 11, (2.13) holds for y \u00E2\u0088\u0088 ({px}, 1), and (2.14) holds either for y \u00E2\u0088\u0088 ({qx}, 1\u00E2\u0088\u0092 {rx}) or y \u00E2\u0088\u0088 [0, 1\u00E2\u0088\u0092 {rx}) \u00E2\u0088\u00AA ({qx}, 1) depending on whether or not {qx}+ {rx} > 1. Therefore, for (2.12) to hold, we want either ({px}, 1) \u00E2\u0088\u00AA ({qx}, 1\u00E2\u0088\u0092 {rx}) = [0, 1) or ({px}, 1) \u00E2\u0088\u00AA [0, 1\u00E2\u0088\u0092 {rx}) \u00E2\u0088\u00AA ({qx}, 1) = [0, 1). Since the former union is an open interval, equality can never hold, therefore we must have {qx}+ {rx} > 1. We must also have {px} < 1\u00E2\u0088\u0092 {rx}, which completes the proof. Now that the required condition for which \u00CF\u0095(x) = 1 is expressed as an inequality, the final step is to obtain the equivalent statement in the form x \u00E2\u0088\u0088 U , where U is a union of intervals. Now, {px} < 1\u00E2\u0088\u0092 {rx} is equivalent to {px}+ {rx} < 1, and 1\u00E2\u0088\u0092 {rx} < {qx} is equivalent to {qx}+ {rx} > 1, so we only need to know the solution set of inequalities of the form {px}+ {qx} < 1, since we can take the complement of the solution set when the sign is reversed. This gives us: 11 Lemma 13. Let p, q \u00E2\u0088\u0088 Z+ with gcd(p, q) = 1. Let P1, . . . , Pp+q\u00E2\u0088\u00922 be the rationals in (0, 1) of the form n/p or n/q in ascending order. Then {px}+ {qx} < 1 if and only if x \u00E2\u0088\u0088 [ 0, 1 p+ q ) \u00E2\u0088\u00AA ( p+q\u00E2\u0088\u00922\u00E2\u008B\u0083 i=1 ( Pi, i+ 1 p+ q )) . Proof. Consider the function f(x) = {px}+ {qx} \u00E2\u0088\u0092 {(p+ q)x}. This function has range {0, 1}, and f(x) = 0 if and only if {px} + {qx} < 1. Furthermore, f(x) can only be discontinuous at points of the form n/p, n/q, n/(p+ q), therefore any maximal interval (x1, x2) for which f(x) = 0 must have x1, x2 of the form n/p, n/q, n/(p+ q). Write x = n/p\u00E2\u0088\u0092 \u00CE\u00B5, for sufficiently small \u00CE\u00B5 > 0. Then {px}+ {qx} = 1\u00E2\u0088\u0092 p\u00CE\u00B5+ { qn p \u00E2\u0088\u0092 p\u00CE\u00B5 } . Since gcd(p, q) = 1, qn/p is not an integer, hence when \u00CE\u00B5 is sufficiently small, f(x) = 1. However, f(n/p) = 0, hence at n/p, f(x) has a point of discontinuity where it changes from 1 to 0. By symmetry, n/q is also a point of discontinuity where it changes from 1 to 0. Therefore, since f(0) = 0 and limx\u00E2\u0086\u00921+ f(x) = 1, there must be p+ q \u00E2\u0088\u0092 1 points of discontinuity where the function changes from 0 to 1, hence they correspond to the rationals n/(p + q). Thus, if f(x) = 0 on an interval (x1, x2), x1 must be of the form n/p or n/q, and x2 must be of the form n/(p+ q). We can now determine when \u00CF\u0095(x) = 1, given arbitrary \u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3. Lemma 14. Let \u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3 \u00E2\u0088\u0088 Z be given, with \u00CE\u00B3, \u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3 \u00E2\u0089\u00A5 2. Set p = \u00E2\u0088\u0092(\u00CE\u00B1 + \u00CE\u00B3), q = \u00CE\u00B1 + \u00CE\u00B2, r = \u00CE\u00B3, and suppose that p, q, r are pairwise coprime. For coprime s, t \u00E2\u0088\u0088 Z+, define P (s, t, i) to be the ith smallest element amongst {n/s : 0 < n < s} \u00E2\u0088\u00AA {n/t : 0 < n < t}. Then \u00CF\u0095(x) = 1 when x \u00E2\u0088\u0088 ( q\u00E2\u0088\u00922\u00E2\u008B\u0083 i=1 ( i q , P (|p|, p+ q, i) ) \u00E2\u0088\u00AA ( 1\u00E2\u0088\u0092 1 q , 1 )) \u00E2\u0088\u00A9 ( q+r\u00E2\u0088\u00922\u00E2\u008B\u0083 i=1 ( i q + r , P (q, r, i) ) \u00E2\u0088\u00AA ( 1\u00E2\u0088\u0092 1 q + r , 1 )) . Proof. From Lemma 12, we must have {px} < 1 \u00E2\u0088\u0092 {qx} < {rx} for \u00CF\u0095(x) = 1. The first inequality yields {px}+ {qx} < 1, or equivalently, {\u00E2\u0088\u0092(\u00CE\u00B1+ \u00CE\u00B3)x}+ {(\u00CE\u00B1+ \u00CE\u00B2)x} \u00E2\u0088\u0092 {(\u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3)x} = 0. (2.15) Now, {\u00E2\u0088\u0092(\u00CE\u00B1+\u00CE\u00B3)x} = 1\u00E2\u0088\u0092{(\u00CE\u00B1+\u00CE\u00B3)x} when (\u00CE\u00B1+\u00CE\u00B3)x /\u00E2\u0088\u0088 Z, hence assuming this, (2.15) is equivalent to 1\u00E2\u0088\u0092 {(\u00CE\u00B1+ \u00CE\u00B3)x}+ {(\u00CE\u00B1+ \u00CE\u00B2)x} \u00E2\u0088\u0092 {(\u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3)x} = 0, that is, {|p|x}+ {(p+ q)x} \u00E2\u0088\u0092 {qx} = 1. 12 By Lemma 13, this holds when x \u00E2\u0088\u0088 q\u00E2\u0088\u00922\u00E2\u008B\u0083 i=1 ( i q , P (|p|, p+ q, i) ) \u00E2\u0088\u00AA ( 1\u00E2\u0088\u0092 1 q , 1 ) . The second inequality gives 1 < {qx}+ {rx}, and since q, r > 0, we can directly apply Lemma 13, which yields x \u00E2\u0088\u0088 q+r\u00E2\u0088\u00922\u00E2\u008B\u0083 i=1 ( i q + r , P (q, r, i) ) \u00E2\u0088\u00AA ( 1\u00E2\u0088\u0092 1 q + r , 1 ) . Combining both inclusions gives the desired conclusion. This lemma allows us to compute the intervals mechanically, since determining P (x, y, i) can be calculated at the same time as calculating the values n/x, n/y, and computing the intersection of a pair of intervals is also straightforward. The lemmas can also be modified to account for the case when the integers are not pairwise coprime. In this case it suffices to note that if gcd(p, q) = d, {px}+ {qx} \u00E2\u0088\u0092 {(p+ q)x} = {p d dx } + {q d dx } \u00E2\u0088\u0092 { (p+ q) d dx } , hence the adjustment to Lemma 13 with the assumption that gcd(p, q) = d gives x \u00E2\u0088\u0088 d\u00E2\u0088\u00921\u00E2\u008B\u0083 i=0 \u00EF\u00A3\u00AB\u00EF\u00A3\u00AD[ i d , i d + d p+ q ) \u00E2\u0088\u00AA \u00EF\u00A3\u00AB\u00EF\u00A3\u00AD(p+q)/d\u00E2\u0088\u00922\u00E2\u008B\u0083 j=1 ( i d + P (p d , q d , j ) , i d + d(j + 1) p+ q )\u00EF\u00A3\u00B6\u00EF\u00A3\u00B8\u00EF\u00A3\u00B6\u00EF\u00A3\u00B8 . The next step is to use these results and describe how to compute \u00CE\u00A6 given \u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3. 2.3 Computing log \u00CE\u00A6 Given that \u00CF\u0095(x) can be solved algorithmically, we can estimate log \u00CE\u00A6. We first use the following estimates for \u00CE\u00B8(x): \u00CE\u00B8(x) < ( 1 + 1 36260 ) x < 1.000028x, valid for x > 0 (see Dusart[12]), and \u00CE\u00B8(x) > 0.998x, valid for x > 487381 (see Rosser and Schoenfeld[13]). Now, provided 0.998 m ai +N \u00E2\u0088\u0092 1.000028 m bi +N > 0, we can use these estimates with (2.9) in order to obtain an inequality of the form log \u00CE\u00A6 > N0\u00E2\u0088\u00921\u00E2\u0088\u0091 N=0 \u00E2\u0088\u0091 i 0.998 m ai +N \u00E2\u0088\u0092 1.000028 m bi +N + i0\u00E2\u0088\u0091 i=1 0.998 m ai +N0 \u00E2\u0088\u0092 1.000028 m bi +N0 . 13 This inequality will be valid provided m ai0 +N0 > 487381, that is, m > 487381(ai0 +N0). Now, recalling that k \u00E2\u0089\u00A5 2\u00CE\u00B2m, this will give an effective bound k0 \u00E2\u0089\u00A5 487381 \u00C2\u00B7 2\u00CE\u00B2(ai0 +N0), where equality will hold if Lemma 8 holds for m > 487381(ai0 + N0). Note that we only need to satisfy (2.7) and (2.8), so we only need to pick the smallest value of ai0 + N0 that satisfies both equations. The conclusion to draw from this is given \u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3, the values A(\u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3), M1, M2, and log \u00CE\u00A6 can be calculated in a straightforward manner, so we can use a computer to determine the choice of \u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3 that minimizes k0 and satisfies Lemma 4. The algorithm to determine the values \u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3 is as follows: 1. Determine an upper bound N , and initialize k0 = \u00E2\u0088\u00921,\u00CE\u00B10 = 0, \u00CE\u00B20 = 0, \u00CE\u00B30 = 0. 2. Iterate through triples (\u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3) satisfying 1 \u00E2\u0089\u00A4 \u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3 \u00E2\u0089\u00A4 N with 3\u00CE\u00B1 \u00E2\u0089\u00A4 \u00CE\u00B2, and \u00CE\u00B3, \u00CE\u00B2 \u00E2\u0088\u0092 \u00CE\u00B3 \u00E2\u0089\u00A5 2. (a) Compute A(\u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3), M1, M2. (b) Compute the solution set to \u00CF\u0095(x) = 1 given \u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3 as a union of intervals (ai, bi). (c) Compute the smallest value of ai +N such that N0\u00E2\u0088\u00921\u00E2\u0088\u0091 N=0 \u00E2\u0088\u0091 i 0.998 m ai +N \u00E2\u0088\u0092 ( 1 + 1 36260 ) m bi +N + i0\u00E2\u0088\u0091 i=1 0.998 m ai +N0 \u00E2\u0088\u0092 ( 1 + 1 36260 ) m bi +N0 \u00E2\u0089\u00A5 mmax(A(\u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3) + logM2 + (\u00CE\u00B2 \u00E2\u0088\u0092 3\u00CE\u00B1\u00E2\u0088\u0092 3\u00CE\u00B3) log 2), A(\u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3)\u00E2\u0088\u0092 logM1 + 2\u00CE\u00B2 log(4/9)). If no such value exists, stop computing. (d) Calculate k = 487381 \u00C2\u00B7 2\u00CE\u00B2(ai +N). If k < k0, or k0 = \u00E2\u0088\u00921, then set k0 = k, \u00CE\u00B10 = \u00CE\u00B1, \u00CE\u00B20 = \u00CE\u00B2, \u00CE\u00B30 = \u00CE\u00B3. 3. At the end of the computations, the values \u00CE\u00B1 = \u00CE\u00B10, \u00CE\u00B2 = \u00CE\u00B20, \u00CE\u00B3 = \u00CE\u00B30 will either all be 0, in which case no bound can be calculated and a larger choice of N should be used, otherwise using those values will yield an effective bound which is at least k0. 14 Chapter 3 Waring\u00E2\u0080\u0099s Conjecture 3.1 Effective Bounds We now present values of \u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3 that give k0 = 2207008. Pick \u00CE\u00B1 = 10, \u00CE\u00B2 = 30, \u00CE\u00B3 = 13. Then A(\u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3) < 56.800135956, logM1 < \u00E2\u0088\u00924.00634559211, logM2 < \u00E2\u0088\u009225.761050321, log \u00CE\u00B41 < \u00E2\u0088\u00925.382886636, log \u00CE\u00B42 < \u00E2\u0088\u009227.064259491, log(\u00CE\u00B1+ \u00CE\u00B3) < 3.135494216. To estimate log \u00CE\u00A6, we use the intervals( 2 53 , 1 23 ) \u00E2\u0088\u00AA ( 3 53 , 1 17 ) \u00E2\u0088\u00AA ( 4 53 , 1 13 ) , which is a partial solution set to \u00CF\u0095(x) = 1. This gives log \u00CE\u00A6 > 0.998 ( 53 2 + 53 3 + 53 4 ) m\u00E2\u0088\u0092 1.00002758(23 + 17 + 13)m > 4.3m provided 53m/4 > 487381. Applying Lemma 4 with Lemma 7 gives log |Rn ( \u00E2\u0088\u00921 8 ) \u00CE\u00A6\u00E2\u0088\u009212b\u00E2\u0088\u00923a+1+2j(\u00E2\u0088\u00921)a \u00E2\u0088\u0092 log(2/3) < m(A(\u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3)\u00E2\u0088\u0092 logM2 \u00E2\u0088\u0092 log \u00CE\u00A6 + (\u00CE\u00B2 \u00E2\u0088\u0092 3\u00CE\u00B1\u00E2\u0088\u0092 3\u00CE\u00B3) log 2) + log(\u00CE\u00B1+ \u00CE\u00B3) + log \u00CE\u00B42 \u00E2\u0088\u0092 logM2 \u00E2\u0088\u0092 log(2/3) < \u00E2\u0088\u00920.293654406m+ 0.7336727574 < 0 15 for m > 36783, as required. Hence log \u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5(4/3)k\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5 > m(log \u00CE\u00A6\u00E2\u0088\u0092A(\u00CE\u00B1, \u00CE\u00B2, \u00CE\u00B3)\u00E2\u0088\u0092 logM1) + log \u00CE\u00B41 \u00E2\u0088\u0092 logM1 > \u00E2\u0088\u009248.493790363m\u00E2\u0088\u0092 1.3765410438 > \u00E2\u0088\u00920.80822983938k > log(0.4456k), valid for k > 2207008. 3.2 Computations The remaining values of k can be checked with a computer. We verify this using a method derived from [9] which uses the following recursion: Lemma 15. Define Ak = 3 k, Bk = 4 k, Ck = {(4/3)k} \u00C2\u00B7 3k, Dk = [4/3]k. Then for all k \u00E2\u0089\u00A5 1, we have Dk+1 = Dk + [ Dk 3 ] + [{ Dk 3 } + 4Ck 3Ak ] , and Ck+1 = 3Ak ({ Dk 3 } + 4Ck 3Ak \u00E2\u0088\u0092 [{ Dk 3 } + 4Ck 3Ak ]) . Furthermore, the value [{ Dk 3 } + 4Ck 3Ak ] is either 0 or 1. Proof. For k = 1, A1 = 3, B1 = 4, D1 = 1, C1 = 1 and D2 = 1, C2 = 7, so the equation holds. For k \u00E2\u0089\u00A5 2, from the definition of Ak, Bk, Ck, Dk, we have 4k = Bk = AkDk + Ck. Hence Ak+1Dk+1 + Ck+1 = Bk+1 = 4(AkDk + Ck) = Ak+1Dk +AkDk + 4Ck = Ak+1 ( Dk + [ Dk 3 ]) + 3Ak { Dk 3 } + 4Ck Since Ck < 3 k, 3Ak { Dk 3 } + 4Ck < 2 \u00C2\u00B7 3k+1, hence [{ Dk 3 } + 4Ck 3Ak ] \u00E2\u0089\u00A4 1, 16 and 3Ak ({ Dk 3 } + 4Ck 3Ak \u00E2\u0088\u0092 [{ Dk 3 } + 4Ck 3Ak ]) < 3k+1, which completes the induction step. This gives the following algorithm: Suppose for fixed k, Ak, Bk, Ck and Dk have been computed. Then we derive the values for k + 1 as follows: 1. Ak+1 = 2Ak +Ak, where a bitshift is used for multiplication by 2. 2. Bk+1 = 4Bk, where a bitshift is used for multiplication by 4. 3. Intermediate values p, s are calculated satisfying Dk = 3p+ s with 0 \u00E2\u0089\u00A4 s < 3. Depending on the sign of sAk + 4Ck \u00E2\u0088\u0092Ak+1, we have two outcomes: (a) If sAk + 4Ck \u00E2\u0088\u0092Ak+1 < 0, set Dk+1 = Dk + p, Ck+1 = sAk + 4Ck. (b) Otherwise, set Dk+1 = Dk + p+ 1, Ck+1 = sAk + 4Ck \u00E2\u0088\u0092Ak+1. Now, the inequality min(Ck, Ak \u00E2\u0088\u0092 Ck) > Dk implies \u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5 ( 4 3 )k\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5\u00E2\u0088\u00A5 \u00E2\u0089\u00A5 ( 4 9 )k , so we have the program check min(Ck, Ak \u00E2\u0088\u0092 Ck) > Dk to verify it. The values for k = n214 are presented below. 17 Table 3.1: Values of Ak, Bk,min(Ck, Ak \u00E2\u0088\u0092 Ck) and Dk k logAk214 logBk214 log min(Ck214 , Ak214 \u00E2\u0088\u0092 Ck214) logDk214 1 17999.6637375 22713.0468126 17998.6923988 4713.38307505 2 35999.3274751 45426.0936252 35998.1793671 9426.7661501 3 53998.9912126 68139.1404378 53998.198119 14140.1492251 4 71998.6549502 90852.1872504 71997.8090283 18853.5323002 5 89998.3186877 113565.234063 89996.6381003 23566.9153752 10 179996.637375 227130.468126 179995.217209 47133.8307505 15 269994.956063 340695.702189 269992.868237 70700.7461257 20 359993.274751 454260.936252 359991.28823 94267.661501 25 449991.593438 567826.170315 449990.752047 117834.576876 30 539989.912126 681391.404378 539987.883665 141401.492251 35 629988.230814 794956.638441 629983.460249 164968.407627 40 719986.549502 908521.872504 719985.503399 188535.323002 45 809984.868189 1022087.10657 809982.788389 212102.238377 50 899983.186877 1135652.34063 899981.320388 235669.153752 60 1079979.82425 1362782.80876 1079978.79713 282802.984503 70 1259976.46163 1589913.27688 1259975.50036 329936.815253 80 1439973.099 1817043.74501 1439971.8212 377070.646004 90 1619969.73638 2044174.21313 1619968.6568 424204.476754 100 1799966.37375 2271304.68126 1799964.49024 471338.307505 110 1979963.01113 2498435.14938 1979962.06757 518472.138255 120 2159959.6485 2725565.61751 2159958.37834 565605.969006 130 2339956.28588 2952696.08564 2339953.51905 612739.799756 135 2429954.60457 3066261.3197 2429953.67181 636306.715132 18 Bibliography [1] M. A. Bennett, \u00E2\u0080\u009CAn ideal Waring problem with restricted summands\u00E2\u0080\u009D, Acta Arith. 66(2), 125- 132 (1994). [2] K. Mahler, \u00E2\u0080\u009COn the fractional parts of real numbers (II)\u00E2\u0080\u009D, Mathematika 4, 122-124 (1957). [3] A. Baker and J. Coates, \u00E2\u0080\u009CFractional parts of powers of rationals,\u00E2\u0080\u009D Math. Proc. Cambridge Philos. Soc. 77, 269-279 (1975). [4] F. Beukers, \u00E2\u0080\u009CFractional parts of powers of rationals,\u00E2\u0080\u009D Math. Proc. Cambridge Philos. Soc. 90, 13-20 (1981). [5] A. K. Dubitkas, \u00E2\u0080\u009CA lower bound for the quantity \u00E2\u0088\u00A5\u00E2\u0088\u00A5(3/2)k\u00E2\u0088\u00A5\u00E2\u0088\u00A5,\u00E2\u0080\u009D Uspekhi Mat. Nauk 45 (4), 153-154, (1990) [Russian Math. Surveys 45 (4), 163-164 (1990)]. [6] L. Habsieger, \u00E2\u0080\u009CExplicit lower bounds for \u00E2\u0088\u00A5\u00E2\u0088\u00A5(3/2)k\u00E2\u0088\u00A5\u00E2\u0088\u00A5,\u00E2\u0080\u009D Acta Arith. 106 (3), 299-309 (2003). [7] W. Zudilin, \u00E2\u0080\u009CA new lower bound for \u00E2\u0088\u00A5\u00E2\u0088\u00A5(3/2)k\u00E2\u0088\u00A5\u00E2\u0088\u00A5,\u00E2\u0080\u009D J. The\u00CC\u0081or. Nombres Bordeaux 19 (1), 311-323 (2007) [8] Yu. A. Pupyrev, \u00E2\u0080\u009CEffectivization of a Lower Bound for \u00E2\u0088\u00A5\u00E2\u0088\u00A5(4/3)k\u00E2\u0088\u00A5\u00E2\u0088\u00A5,\u00E2\u0080\u009D Mathematical Notes, Vol. 85, No. 6, 877-885, (2009). [9] F. Delmer and J.-M. Deshouillers, \u00E2\u0080\u009CThe computation of g(k) in Waring\u00E2\u0080\u0099s problem,\u00E2\u0080\u009D Math. Comp. 54 (190), 885-893 (1990). [10] J. Kubina and M. Wunderlich, \u00E2\u0080\u009CExtending Waring\u00E2\u0080\u0099s conjecture up to 471 600 000,\u00E2\u0080\u009D Math. Comp. 55 (192), 815-820, (1990). [11] M. Abramowitz and I. Stegun, \u00E2\u0080\u009CHandbook of Mathematical Functions,\u00E2\u0080\u009D (2002). [12] P. Dusart, \u00E2\u0080\u009CEstimates of some functions over primes without R.H.\u00E2\u0080\u009D, arXiv preprint, arXiv:1002.0442 [math.NT], (2010). [13] J. B. Rosser and L. Schoenfeld, \u00E2\u0080\u009CSharper Bounds for the Chebyshev Functions \u00CE\u00B8(x) and \u00CF\u0088(x),\u00E2\u0080\u009D Mathematics of Computation, Vol. 29, No. 129, 243-269 (1975). 19"@en . "Thesis/Dissertation"@en . "2013-11"@en . "10.14288/1.0071968"@en . "eng"@en . "Mathematics"@en . "Vancouver : University of British Columbia Library"@en . "University of British Columbia"@en . "Attribution-NonCommercial-NoDerivatives 4.0 International"@en . "http://creativecommons.org/licenses/by-nc-nd/4.0/"@en . "Graduate"@en . "On a generalization of Waring's conjecture"@en . "Text"@en . "http://hdl.handle.net/2429/44477"@en .