On a Generalization of Waring’s 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© Chenglong Zou, 2013 Abstract Pupyrev’s paper “Effectivization of a Lower Bound for ∥∥(4/3)k∥∥” provides partial results to the assertion that ∥∥(4/3)k∥∥ > (4/9)k for k ≥ 6, which is equivalent to a generalization of Waring’s 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, α, β, γ 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 Φ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Computing log Φ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3 Waring’s 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 − Ck) and Dk . . . . . . . . . . . . . . . . . . . . . . . 18 iv Chapter 1 Introduction 1.1 Background Waring’s 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] · 2k − 1 = ([( 3 2 )k] − 1 ) · 2k + (2k − 1) · 1k, we have the lower bound g(k) ≥ 2k + [( 3 2 )k] − 2, where [x] denotes the largest integer less than or equal to x. Waring’s conjecture asserts that the inequality is in fact an equality, and it is known that{( 3 2 )k} ≤ 1− ( 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’s 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 ≥ 3 is that when k ≥ 6, gN (k) = N k + [( N + 1 N )k] − 2, and this is equivalent to the inequality∥∥∥∥∥ ( N + 1 N )k∥∥∥∥∥ ≥ ( N + 1 N2 )k , (1.2) 1 where ‖x‖ denotes the distance from x to the closest integer, i.e. ‖x‖ = min({x}, 1− {x}). In 1957, Mahler[2] showed that for any 0 ≤ C < 1, there exists a constant k0 = k0(C) depending on C such that ∥∥∥(3/2)k∥∥∥ > Ck (1.3) when k ≥ 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−(1−10 64). Later, Beukers[4] improved on this result and obtained proved (1.3) for C = 2−0.9, by using Padé 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 Padé approximations of bino- mial power series, although none have succeeded in obtaining C ≥ 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 ≤ 471600000. Regarding (1.2), Both Zudilin and Pupyrev previously showed that∥∥∥∥∥ ( 4 3 )k∥∥∥∥∥ > Ck holds with C = 0.4914 and C = 0.4910 respectively for sufficiently large k ≥ 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,∥∥∥∥∥ ( 4 3 )k∥∥∥∥∥ > 0.4456k. We also check computationally that for 1 < k ≤ 2207008,∥∥∥∥∥ ( 4 3 )k∥∥∥∥∥ > ( 4 9 )k by adapting the algorithm by Delmer and Deshouillers. By combining these results, we have the following: Theorem 2. Let k ≥ 6. Then g3(k) = 3 k + [ 4 3 ]k − 2. 2 1.2 Preliminaries To estimate {(4/3)k}, we use the identity 1 (1− z)m+1 = ∞∑ n=0 ( m+ n m ) zn, valid for z ∈ (1,−1). With z = 4/3, we have Lemma 1. Suppose a, b are integers such that 3a ≤ b. Then( 4 3 )2(b+1) − 2b−3a+1(−1)a ∞∑ ν=0 ( a+ b+ ν b )( −1 8 )ν 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 )−(b+1) = 2b+1 ∞∑ l=0 ( b+ l b )( 1 8 )l (−1)l = 2b−3a+1 ∞∑ l=0 ( b+ l b ) 23(a−l)(−1)−l = 2b−3a+1(−1)a ∞∑ l=0 ( b+ l b ) 23(a−l)(−1)a−l = 2b−3a+1(−1)a ( a−1∑ l=0 ( b+ l b ) 23(a−l)(−1)a−l + ∞∑ l=a ( b+ l b ) 23(a−l)(−1)a−l ) . The left sum is clearly an integer, hence reindexing the right sum with l = ν + a gives( 4 3 )2(b+1) − 2b−3a+1(−1)a ∞∑ ν=0 ( b+ a+ ν b )( −1 8 )ν ∈ Z. Hence, the magnitude of ∥∥(4/3)2(b+1)∥∥ can be determined by studying the magnitude of∥∥∥∥∥ ∞∑ ν=0 ( b+ a+ ν b )( −1 8 )ν∥∥∥∥∥ , so we will consider the function F (z) = F (a, b; z) = ∞∑ ν=0 ( a+ b+ ν b ) zν , and estimate the magnitude of ‖F (−1/8)‖. To accomplish this, we have the following two lemmas from Zudilin [7] (see Lemma 1 and Lemma 3): 3 Lemma 2. Suppose n ∈ Z with n ≤ b. Define Qn(z−1) to be such that Qn(z −1) = (a+ b+ n)! (a+ n− 1)!n!(b− n)! ∫ 1 0 ta+n+1(1− t)b−n(1− z−1t)n dt, and Rn(z) such that Rn(z) = (a+ b+ n)! (a+ n− 1)!n!(b− n)!z n ∫ 1 0 tn(1− t)a+n−1(1− zt)−(a+b+n)−1 dt. Then Qn(z), Rn(z) ∈ Z[x], and there exists a polynomial Pn(z) ∈ Z[x] such that Qn(z −1)F (z) = Pn(z−1) +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 > √ a+ b+ n, define ep,n = min µ∈Z ( − { −a+ n p } + {−a+ n+ µ p } + { µ p } − { a+ b+ n p } + { a+ b+ µ p } + { n− µ p }) , and Φ = Φ(a, b, n) = ∏ p> √ a+b+n pep,n . Then Φ−1Qn(z),Φ−1Pn(z) ∈ Z[x]. 4 Chapter 2 Computing estimates 2.1 Basic estimates To estimate the bound on ∥∥(4/3)k∥∥, we will henceforth assume the following about a, b and n: write a = αm, b = βm and n = γm, with the condition that γ, β− γ ≥ 2. First, we use Lemma 2 and the relation in Lemma 1 to relate ∥∥(4/3)k∥∥ and the magnitudes of Qn(−8) and Rn(−1/8). Lemma 4. Suppose k ≥ 3, and write k = 2(βm+ 1) + j, where 0 ≤ j < 2β. If∣∣∣∣Rn(−18 ) Φ−12b−3a+1+2j(−1)a ∣∣∣∣ < 23 , (2.1) then we have the bound ∥∥∥(4/3)k∥∥∥ > Φ 32β|Qn(−8)| . (2.2) Proof. Using (1.4), at z = −1/8 and multiply through by Φ−12b−3a+1+2j(−1)a, we have Qn(−8)Φ−13j ( 4 3 )j 2b−3a+1(−1)aF ( a, b,−1 8 ) = Pn(−8)Φ−12b−3a+1+2j(−1)a + Rn ( −1 8 ) Φ−12b−3a+1+2j(−1)a. Applying Lemma 1 with k = 2(b+ 1) + j, we have( 4 3 )j 2b−3a+1(−1)aF ( a, b,−1 8 ) − ( 4 3 )k ∈ Z. Thus Qn(−8)Φ−13j ∥∥∥(4/3)k∥∥∥ = Mk +Rn(−1 8 ) Φ−12b−3a+1+2j(−1)a for some integer Mk ∈ Z. Hence if (2.1) holds,∣∣∣Qn(−8)Φ−13j ∥∥∥(4/3)k∥∥∥∣∣∣ ≥ |Mk| − ∣∣∣∣Rn(−18 ) Φ−12b−3a+1+2j(−1)a ∣∣∣∣ > 13 , 5 and rearranging gives the desired conclusion:∥∥∥(4/3)k∥∥∥ > ∣∣∣∣ Φ3j+1Qn(−8) ∣∣∣∣ ≥ ∣∣∣∣ Φ32βQn(−8) ∣∣∣∣ . To estimate the magnitudes of Qn(−8) and Rn(−1/8), we use their integral representations as seen in Lemma 2. However, instead of looking at Qn(−8), Rn(−1/8) directly, we will estimate the logarithm of these values. We begin by bounding the factorial coefficient in their representations. Lemma 5. Given α, β, γ,m ∈ Z, with γ, β − γ ≥ 2, we have log ( (αm+ βm+ γm)! (αm+ γm− 1)!(γm)!(βm− γm)! ) ≤ mA(α, β, γ) + log(α+ γ), (2.3) where the function A(α, β, γ) is given by A(α, β, γ) = (α+ β + γ) log(α+ β + γ)− (α+ γ) log(α+ γ)− γ log γ − (β − γ) log(β − γ). Proof. Denote the quantity on the left hand side of (2.3) by L. Using Stirling’s formula (see Abramowitz[11]), given by log((s− 1)!) = log Γ(s) = ( s− 1 2 ) log s− s+ log √ 2pi + 2 ∫ ∞ 0 arctan( ts) e2pit − 1 dt, valid for s > 0, and applying it to L gives us L = m(α+ β + γ) log(m(α+ β + γ) + 1) + 1 2 log(m(α+ β + γ) + 1) −m(α+ γ) log(m(α+ γ)) + 1 2 log(m(α+ γ)) −mγ log(mγ + 1)− 1 2 log(mγ + 1) −m(β − γ) log(m(β − γ) + 1)− 1 2 log(m(β + γ) + 1) − log(2pi) + 1 + I, (2.4) where I = 2 ∫ ∞ 0 1 e2pit − 1 ( arctan ( t a+ b+ c+ 1 ) − arctan ( t a+ c ) − arctan ( t c+ 1 ) − arctan ( t b− c+ 1 )) dt. By observation, we see I is negative. Considering the inequalities x− x 2 2 ≤ log(1 + x) ≤ x, valid for x ∈ (0, 1), and combining it with the identity log(n+ 1) = log n+ log ( 1 + 1 n ) , 6 we have log n+ 1 n − 1 2n2 ≤ log(n+ 1) ≤ log n+ 1 n , valid for n > 1. Applying these inequalities to (2.4) gives us L ≤ m(α+ β + γ) log(α+ β + γ) +m(α+ β + γ) logm+ 1 + 1 2 log(m(α+ β + γ)) + 1 2m(α+ β + γ) −m(α+ γ) log(α+ γ)−m(α+ γ) logm+ 1 2 log(m(α+ γ)) −mγ log γ −mγ logm− 1 + 1 2mγ − 1 2 logmγ − 1 2mγ + 1 4(mγ)2 −m(β − γ) log(β − γ)−m(β − γ) logm− 1 + 1 2m(β − γ) − 1 2 log(m(β − γ))− 1 2m(β − γ) + 1 4(m(β − γ))2 − log 2pi + 1. Collecting appropriate terms gives us L ≤ mA(α, β, γ) + 1 2 (log(α+ β + γ) + log(α+ γ)− log γ − log(β − γ)) + 1 2m(α+ β + γ) + 1 4(mγ)2 + 1 4(m(β − γ))2 − log 2pi. Using the inequality log(x+ y) ≤ log x+ log y, we have 1 2 (log(α+ β + γ) + log(α+ γ)− log γ − log(β − γ) ≤ log(α+ γ) + 1 2 (log((β − γ) + γ)− log γ − log(β − γ)) ≤ log(α+ γ), and 1 2m(α+ β + γ) + 1 4(mγ)2 + 1 4(m(β − γ))2 ≤ 1 ≤ log 2pi, hence the result follows. The next step is to bound both integrals. Lemma 6. Given α, β, γ,m ∈ Z with γ, β − γ ≥ 2, and z < 0, we have∫ 1 0 t(α+γ)m−1(1− t)(β−γ)m(1− z−1t)γm dt ≤Mm−11 δ1, and ∫ 1 0 tγm(1− t)(α+γ)m−1(1− zt)−(α+β+γ)m−1 dt ≤Mm−12 δ2, 7 where M1 = max t∈[0,1] |tα+γ(1− t)β−γ(1− z−1t)γ |, M2 = max t∈[0,1] |tγ(1− t)α+γ(1− zt)−(α+β+γ)|, δ1 = ∫ 1 0 tα+γ−1(1− t)β−γ(1− z−1t)γ dt, δ2 = ∫ 1 0 tγ(1− t)α+γ−1(1− zt)−(α+β+γ)−1 dt. Proof. This follows from the triangle inequality. Thus, we have the following estimates for Qn(z −1), Rn(z): Lemma 7. Given a, b, n, z, write a = αm, b = βm, n = γm for α, β, γ,m ∈ Z, and suppose γ, β − γ ≥ 2. Suppose also that z < 0. Then log |Qn(z−1)| ≤ m(A(α, β, γ) + logM1) + log(α+ γ) + log δ1 − logM1, (2.5) and log |Rn(z)| ≤ m(A(α, β, γ) + logM2 + γ log z) + log(α+ γ) + log δ2 − logM2. (2.6) Here, the values M1,M2, δ1, δ2 depend on z. Combining these estimates with Lemma 4 gives us a lower bound for ∥∥(4/3)k∥∥, along with a necessary condition for the bound to be valid. Lemma 8. Let α, β, γ ∈ Z be given with γ, β − γ ≥ 2. If m(A(α, β, γ) + logM2 + (β − 3α− 3γ) log 2)− log Φ < 0, (2.7) then for sufficiently large m, if k = (2βm+ 1) + j for some 0 ≤ j < 2β, log ∥∥∥(4/3)k∥∥∥ > m(logM1 −A(α, β, γ)) + log Φ. (2.8) Proof. From Lemma 4, taking logarithms on both sides of (2.1) gives log ∣∣∣∣Rn(−18 ) Φ−12b−3a ∣∣∣∣+O(1) < 0, so (2.6) implies (2.7) for sufficiently large m. Hence taking logarithms on both sides of (2.2) gives log ∥∥∥(4/3)k∥∥∥ > log Φ− log |Qn(−8)|+O(1), which implies (2.8). 8 At this stage, we recall that α, β, γ are not yet fixed, so we want to pick α, β, γ so that both inequalities are satisfied, which requires computing the constants A(α, β, γ),M1,M2,Φ given arbi- trary α, β, γ. A(α, β, γ) is a value that can be computed directly, and M1,M2 may also be computed directly since d dt log ( tα+γ(1− t)β−γ(1− z−1t)γ ) = α+ γ t − β − γ 1− t − z−1γ 1− z−1t , and d dt log ( tγ(1− t)α+γ(1− zt)−(α+β+γ) ) = γ t − α+ γ 1− t + z(α+ β + γ) 1− 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 Φ given arbitrary α, β, γ is the non-trivial element to optimizing effective bounds for ∥∥(4/3)k∥∥. 2.2 Preliminaries for computing log Φ To estimate log Φ, recall from Lemma 3 that Φ is the product of primes p such that ep,n = 1. Using this fact, we can bound log Φ using the Chebyshev function θ(x): Lemma 9. Define ϕ(x) to be ϕ(x) = min y∈[0,1) (−{(α+ γ)x}+ {−(α+ γ)x− y}+ {y} − {(α+ β + γ)x}+ {(α+ β)x+ y}+ {γx− y}), so that ϕ(m/p) = en,p. Then if ϕ(x) = 1 for x ∈ ⋃ i (ai, bi) ⊆ (0, 1), we have the bound log Φ ≥ [ √ m/(α+β+γ)]−1∑ N=0 ∑ i ( θ ( m ai +N ) − θ ( m bi +N )) , (2.9) where θ(x) is the Chebyshev function, i.e. θ(x) = ∑ p≤x log p. Proof. Suppose p ∈ ( 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 > √ a+ b+ n, we must have m/N > √ a+ b+ n, hence if p ∈ √ m/(α+β+γ)⋃ N=0 ⋃ i ( m bi +N , m ai +N ) , en,p = 1 or equivalently, p divides log Φ. The desired result then follows from the identity log ∏ p∈(x,y) p = θ(y)− θ(x). Thus, understand the magnitude log Φ first requires understanding when ϕ(x) = 1. From the definition of ϕ(x), this can be understood by knowing when a equation of the form {δ1 + y}+ {δ2 − y}+ {δ1 + δ2} = 1 holds, given arbitrary δ1, δ2. The following lemmas establish these conditions. Lemma 10. Let 0 ≤ δ < 1. Then for x ∈ [0, 1), {δ − x}+ {x} − δ = 1 (2.10) if and only if x ∈ (δ, 1). Proof. The left hand side of (2.10) is a function whose range is {0, 1}, and discontinuous only at x = δ. If x ≤ δ, {δ − x}+ {x} − {δ} = δ − x+ x− δ = 0, hence we must have x ∈ (δ, 1). To prove sufficiency, write x = δ + ε, where ε > 0 is sufficiently small. Then {δ − x}+ {x} − {δ} = 1− ε+ δ + ε− δ = 1, hence by continuity, (2.10) holds when x ∈ (δ, 1). By using a substitution, we have the following: Lemma 11. Let 0 ≤ δ1, δ2 < 1. Then for x ∈ [0, 1), {δ1 − x}+ {δ2 + x} − {δ1 + δ2} = 1 (2.11) if and only if x ∈ (δ1, 1− δ2) if δ1 + δ2 < 1,[0, 1− δ2) ∪ (δ1, 1) otherwise. Proof. Write x = y − δ2 and substitute into (2.11). Then by Lemma 10, we have equality if and only y ∈ ({δ1 + δ2}, 1). Now, if δ1 + δ2 < 1, then this is equivalent to δ1 < x < 1− δ2. Otherwise, we have δ1 − 1 < x < 1− δ2, which is equivalent modulo Z to x ∈ [0, 1− δ2) ∪ (δ1, 1). 10 We these lemmas at hand, we may now apply this to the generalized form of ϕ(x): Lemma 12. Let p, q, r ∈ Z, 0 ≤ x < 1. Then min y∈[0,1) {px− y}+ {y} − {px}+ {qx− y}+ {rx+ y} − {(q + r)x} = 1 (2.12) if and only if {px} < 1− {rx} < {qx}. Proof. Note that (2.12) holds if and only if one of {px− y}+ {y} − {px} = 1 (2.13) or {qx− y}+ {rx+ y} − {(q + r)x} = 1 (2.14) holds for every choice of y ∈ [0, 1). From Lemma 10 and Lemma 11, (2.13) holds for y ∈ ({px}, 1), and (2.14) holds either for y ∈ ({qx}, 1− {rx}) or y ∈ [0, 1− {rx}) ∪ ({qx}, 1) depending on whether or not {qx}+ {rx} > 1. Therefore, for (2.12) to hold, we want either ({px}, 1) ∪ ({qx}, 1− {rx}) = [0, 1) or ({px}, 1) ∪ [0, 1− {rx}) ∪ ({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− {rx}, which completes the proof. Now that the required condition for which ϕ(x) = 1 is expressed as an inequality, the final step is to obtain the equivalent statement in the form x ∈ U , where U is a union of intervals. Now, {px} < 1− {rx} is equivalent to {px}+ {rx} < 1, and 1− {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 ∈ Z+ with gcd(p, q) = 1. Let P1, . . . , Pp+q−2 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 ∈ [ 0, 1 p+ q ) ∪ ( p+q−2⋃ i=1 ( Pi, i+ 1 p+ q )) . Proof. Consider the function f(x) = {px}+ {qx} − {(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− ε, for sufficiently small ε > 0. Then {px}+ {qx} = 1− pε+ { qn p − pε } . Since gcd(p, q) = 1, qn/p is not an integer, hence when ε 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→1+ f(x) = 1, there must be p+ q − 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 ϕ(x) = 1, given arbitrary α, β, γ. Lemma 14. Let α, β, γ ∈ Z be given, with γ, β − γ ≥ 2. Set p = −(α + γ), q = α + β, r = γ, and suppose that p, q, r are pairwise coprime. For coprime s, t ∈ Z+, define P (s, t, i) to be the ith smallest element amongst {n/s : 0 < n < s} ∪ {n/t : 0 < n < t}. Then ϕ(x) = 1 when x ∈ ( q−2⋃ i=1 ( i q , P (|p|, p+ q, i) ) ∪ ( 1− 1 q , 1 )) ∩ ( q+r−2⋃ i=1 ( i q + r , P (q, r, i) ) ∪ ( 1− 1 q + r , 1 )) . Proof. From Lemma 12, we must have {px} < 1 − {qx} < {rx} for ϕ(x) = 1. The first inequality yields {px}+ {qx} < 1, or equivalently, {−(α+ γ)x}+ {(α+ β)x} − {(β − γ)x} = 0. (2.15) Now, {−(α+γ)x} = 1−{(α+γ)x} when (α+γ)x /∈ Z, hence assuming this, (2.15) is equivalent to 1− {(α+ γ)x}+ {(α+ β)x} − {(β − γ)x} = 0, that is, {|p|x}+ {(p+ q)x} − {qx} = 1. 12 By Lemma 13, this holds when x ∈ q−2⋃ i=1 ( i q , P (|p|, p+ q, i) ) ∪ ( 1− 1 q , 1 ) . The second inequality gives 1 < {qx}+ {rx}, and since q, r > 0, we can directly apply Lemma 13, which yields x ∈ q+r−2⋃ i=1 ( i q + r , P (q, r, i) ) ∪ ( 1− 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} − {(p+ q)x} = {p d dx } + {q d dx } − { (p+ q) d dx } , hence the adjustment to Lemma 13 with the assumption that gcd(p, q) = d gives x ∈ d−1⋃ i=0 [ i d , i d + d p+ q ) ∪ (p+q)/d−2⋃ j=1 ( i d + P (p d , q d , j ) , i d + d(j + 1) p+ q ) . The next step is to use these results and describe how to compute Φ given α, β, γ. 2.3 Computing log Φ Given that ϕ(x) can be solved algorithmically, we can estimate log Φ. We first use the following estimates for θ(x): θ(x) < ( 1 + 1 36260 ) x < 1.000028x, valid for x > 0 (see Dusart[12]), and θ(x) > 0.998x, valid for x > 487381 (see Rosser and Schoenfeld[13]). Now, provided 0.998 m ai +N − 1.000028 m bi +N > 0, we can use these estimates with (2.9) in order to obtain an inequality of the form log Φ > N0−1∑ N=0 ∑ i 0.998 m ai +N − 1.000028 m bi +N + i0∑ i=1 0.998 m ai +N0 − 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 ≥ 2βm, this will give an effective bound k0 ≥ 487381 · 2β(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 α, β, γ, the values A(α, β, γ), M1, M2, and log Φ can be calculated in a straightforward manner, so we can use a computer to determine the choice of α, β, γ that minimizes k0 and satisfies Lemma 4. The algorithm to determine the values α, β, γ is as follows: 1. Determine an upper bound N , and initialize k0 = −1,α0 = 0, β0 = 0, γ0 = 0. 2. Iterate through triples (α, β, γ) satisfying 1 ≤ α, β, γ ≤ N with 3α ≤ β, and γ, β − γ ≥ 2. (a) Compute A(α, β, γ), M1, M2. (b) Compute the solution set to ϕ(x) = 1 given α, β, γ as a union of intervals (ai, bi). (c) Compute the smallest value of ai +N such that N0−1∑ N=0 ∑ i 0.998 m ai +N − ( 1 + 1 36260 ) m bi +N + i0∑ i=1 0.998 m ai +N0 − ( 1 + 1 36260 ) m bi +N0 ≥ mmax(A(α, β, γ) + logM2 + (β − 3α− 3γ) log 2), A(α, β, γ)− logM1 + 2β log(4/9)). If no such value exists, stop computing. (d) Calculate k = 487381 · 2β(ai +N). If k < k0, or k0 = −1, then set k0 = k, α0 = α, β0 = β, γ0 = γ. 3. At the end of the computations, the values α = α0, β = β0, γ = γ0 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’s Conjecture 3.1 Effective Bounds We now present values of α, β, γ that give k0 = 2207008. Pick α = 10, β = 30, γ = 13. Then A(α, β, γ) < 56.800135956, logM1 < −4.00634559211, logM2 < −25.761050321, log δ1 < −5.382886636, log δ2 < −27.064259491, log(α+ γ) < 3.135494216. To estimate log Φ, we use the intervals( 2 53 , 1 23 ) ∪ ( 3 53 , 1 17 ) ∪ ( 4 53 , 1 13 ) , which is a partial solution set to ϕ(x) = 1. This gives log Φ > 0.998 ( 53 2 + 53 3 + 53 4 ) m− 1.00002758(23 + 17 + 13)m > 4.3m provided 53m/4 > 487381. Applying Lemma 4 with Lemma 7 gives log |Rn ( −1 8 ) Φ−12b−3a+1+2j(−1)a − log(2/3) < m(A(α, β, γ)− logM2 − log Φ + (β − 3α− 3γ) log 2) + log(α+ γ) + log δ2 − logM2 − log(2/3) < −0.293654406m+ 0.7336727574 < 0 15 for m > 36783, as required. Hence log ∥∥∥(4/3)k∥∥∥ > m(log Φ−A(α, β, γ)− logM1) + log δ1 − logM1 > −48.493790363m− 1.3765410438 > −0.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} · 3k, Dk = [4/3]k. Then for all k ≥ 1, we have Dk+1 = Dk + [ Dk 3 ] + [{ Dk 3 } + 4Ck 3Ak ] , and Ck+1 = 3Ak ({ Dk 3 } + 4Ck 3Ak − [{ 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 ≥ 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 · 3k+1, hence [{ Dk 3 } + 4Ck 3Ak ] ≤ 1, 16 and 3Ak ({ Dk 3 } + 4Ck 3Ak − [{ 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 ≤ s < 3. Depending on the sign of sAk + 4Ck −Ak+1, we have two outcomes: (a) If sAk + 4Ck −Ak+1 < 0, set Dk+1 = Dk + p, Ck+1 = sAk + 4Ck. (b) Otherwise, set Dk+1 = Dk + p+ 1, Ck+1 = sAk + 4Ck −Ak+1. Now, the inequality min(Ck, Ak − Ck) > Dk implies ∥∥∥∥∥ ( 4 3 )k∥∥∥∥∥ ≥ ( 4 9 )k , so we have the program check min(Ck, Ak − Ck) > Dk to verify it. The values for k = n214 are presented below. 17 Table 3.1: Values of Ak, Bk,min(Ck, Ak − Ck) and Dk k logAk214 logBk214 log min(Ck214 , Ak214 − 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, “An ideal Waring problem with restricted summands”, Acta Arith. 66(2), 125- 132 (1994). [2] K. Mahler, “On the fractional parts of real numbers (II)”, Mathematika 4, 122-124 (1957). [3] A. Baker and J. Coates, “Fractional parts of powers of rationals,” Math. Proc. Cambridge Philos. Soc. 77, 269-279 (1975). [4] F. Beukers, “Fractional parts of powers of rationals,” Math. Proc. Cambridge Philos. Soc. 90, 13-20 (1981). [5] A. K. Dubitkas, “A lower bound for the quantity ∥∥(3/2)k∥∥,” Uspekhi Mat. Nauk 45 (4), 153-154, (1990) [Russian Math. Surveys 45 (4), 163-164 (1990)]. [6] L. Habsieger, “Explicit lower bounds for ∥∥(3/2)k∥∥,” Acta Arith. 106 (3), 299-309 (2003). [7] W. Zudilin, “A new lower bound for ∥∥(3/2)k∥∥,” J. Théor. Nombres Bordeaux 19 (1), 311-323 (2007) [8] Yu. A. Pupyrev, “Effectivization of a Lower Bound for ∥∥(4/3)k∥∥,” Mathematical Notes, Vol. 85, No. 6, 877-885, (2009). [9] F. Delmer and J.-M. Deshouillers, “The computation of g(k) in Waring’s problem,” Math. Comp. 54 (190), 885-893 (1990). [10] J. Kubina and M. Wunderlich, “Extending Waring’s conjecture up to 471 600 000,” Math. Comp. 55 (192), 815-820, (1990). [11] M. Abramowitz and I. Stegun, “Handbook of Mathematical Functions,” (2002). [12] P. Dusart, “Estimates of some functions over primes without R.H.”, arXiv preprint, arXiv:1002.0442 [math.NT], (2010). [13] J. B. Rosser and L. Schoenfeld, “Sharper Bounds for the Chebyshev Functions θ(x) and ψ(x),” Mathematics of Computation, Vol. 29, No. 129, 243-269 (1975). 19
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- On a generalization of Waring's conjecture
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
On a generalization of Waring's conjecture Zou, Chenglong 2013
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | On a generalization of Waring's conjecture |
Creator |
Zou, Chenglong |
Publisher | University of British Columbia |
Date Issued | 2013 |
Description | Pupyrev's paper "Effectivization of a Lower Bound for (4/3)^k " 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. |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2013-05-16 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0071968 |
URI | http://hdl.handle.net/2429/44477 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2013-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2013_fall_zou_chenglong.pdf [ 236.08kB ]
- Metadata
- JSON: 24-1.0071968.json
- JSON-LD: 24-1.0071968-ld.json
- RDF/XML (Pretty): 24-1.0071968-rdf.xml
- RDF/JSON: 24-1.0071968-rdf.json
- Turtle: 24-1.0071968-turtle.txt
- N-Triples: 24-1.0071968-rdf-ntriples.txt
- Original Record: 24-1.0071968-source.json
- Full Text
- 24-1.0071968-fulltext.txt
- Citation
- 24-1.0071968.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0071968/manifest