On the equation 1^k+2^k+...+x^k=y^n for fixed x
Full text
ON THE EQUATION 1k+ 2k+···+xk=ynFOR FIXED x A. B´ ERCZES, L. HAJDU, T. MIYAZAKI, AND I. PINK Dedicated to K´alm´an Gy˝ory on the occassion of his 75th birthday. Abstract. We provide all solutions of the title equation in positive integers x, k, y, n with 1 ≤x < 25 and n≥3. For these values of the parameters, our result gives an affirmative answer to a related, classical conjecture of Sch¨affer. In our proofs we combine several tools: Baker’s method (in particular, sharp bounds for the linear combinations of logarithms of two algebraic numbers), polynomial-exponential congruences and computational methods. 1. Introduction Let xand kbe positive integers. Write Sk(x)=1k+ 2k+···+xk. The equation (1) Sk(x) = yn in unknown positive integers k, n, x, y with n≥2 has a long history. The case (k, n) = (2,2) has already been considered by Lucas [9], [10], Watson [17] and others. Here we do not give details; the interested reader may consult to the book [15], the papers [4], [1], [3] and the references given therein. It is long known that when (k, n) is one of the pairs (2) (1,2),(3,2),(3,4),(5,2), then (1) has infinitely many solutions. These solutions can be described easily. As the first deep general result, in 1956 Sch¨affer [14] proved that 2010 Mathematics Subject Classification. 11D61, 11D41. Key words and phrases. Power sums, powers, Sch¨affer’s conjecture, polynomialexponential equations and congruences. Research supported in part by the University of Debrecen, by the OTKA grants K100339 and NK101680, and by the T´ AMOP-4.2.2.C-11/1/KONV-20120001 project. The project has been supported by the European Union, co-financed by the European Social Fund. This paper was supported by the J´anos Bolyai Scholarship of the Hungarian Academy of Sciences. The research was also granted by the Austrian science found (FWF) under the project P 24801-N26. The third author was supported by Grant in Aid for JSPS Fellows (No.25484). 1
2 A. B´ ERCZES, L. HAJDU, T. MIYAZAKI, AND I. PINK if (k, n) is fixed and is not in the list (2), then equation (1) has only finitely many solutions. Sch¨affer’s proof was ineffective. Still, for some (small) pairs (k, n) he was able to show that equation (1) has only the trivial solution (x, y) = (1,1). Beside this, he conjectured that for (k, n) not in the list (2), equation (1) has the only nontrivial solution (x, k, y, n) = (24,2,70,2). Considerably later, Gy˝ory, Tijdeman and Voorhove [5] gave an effective proof for Sch¨affer’s result, in the much more general case where the exponent nis also unknown. Moreover, Pint´er [12] (under some mild assumptions) proved that for the nontrivial solutions n < ck log(2k) holds, where cis an effectively computable absolute constant. For further results about equation (1) and its generalizations we refer to the book [15] and the papers [4], [1], [3], and the references there. The conjecture of Sch¨affer has been verified under certain assumptions for the parameters involved. Beside the ”small” fixed pairs (k, n) considered by Sch¨affer [14], Jacobson, Pint´er and Walsh [7] verified the conjecture for n= 2 and even values of kwith 2 ≤k≤58. Later, Bennett, Gy˝ory and Pint´er [1] proved that the conjecture holds for any n≥2 with 1 ≤k≤11. Further, Pint´er [13] verifed Sch¨affer’s conjecture for the even values of nwith n > 4, provided that kis odd with 1≤k < 170. Recently, Hajdu [6] proved that Sch¨affer’s conjecture holds under certain assumptions made on x, letting all the other parameters free. Among other results, he has proved that the conjecture is true if x≡ 0,3 (mod 4) and x < 25. The main tools in the proof of this result were the 2-adic valuation of Sk(x) and local methods for polynomialexponential congruences. The purpose of the present paper is to extend the results in [6] for all values of xwith x < 25. It is important to mention that for this purpose we need different tools than those used in [6]. The reason is that for the remaining values of xwith x < 25 (i.e. those with x≡1,2 (mod 4)) the methods used in [6] are not applicable. To prove our main theorem, we need to combine sharp upper bounds for linear forms in two logarithms and polynomial-exponential congruences, and we also make use of involved computational facilities. The reason why we stop at x < 25 (though our method in principle is capable to cover larger intervals for x) is the following. The total running time of our computer calculations for x= 21 (the value of xrequiring heavy computations) was already around six days. For larger values of x, the bounds appearing in Table 1 would be significantly worse, resulting in much longer running times in the computational part. Since solving the equation for such values of xwould rise questions more of technical
ON THE EQUATION 1k+ 2k+· · · +xk=ynFOR FIXED x3 and computational type, and also because of a nice property of x= 24 (being the only value with a non-trivial solution), we decided to stop at this point. The structure of the paper is the following. In the next section we give our main result. In the third section we give an overview of our strategy to prove our main theorem, and we provide several lemmas. Finally, in the last section we give the proof of our main result. 2. The main result Our main result is the following. Theorem 2.1. All solutions of equation (1) in positive integers x, k, y, n with x < 25 and n≥3are given by (x, k, y, n) = (1, k, 1, n),(8,3,6,4). As a simple consequence we obtain the following immediate Corollary 2.1. For x < 25 and n≥3, Sch¨affer’s conjecture is true. Remark. We mention that in case of n= 2, in view of the identity S3(x) = x(x+1) 22, equation (1) has many more solutions with x < 25. 3. Lemmas In this section we give some lemmas which are needed in the proof of Theorem 2.1. First we get rid of those values of xfor which equation (1) is already solved. Lemma 3.1. Suppose that x∈ {1,2,3,4,7,8,11,12,15,16,19,20,23,24}. Then equation (1) with n≥3has only the trivial solution with (x, y) = (1,1). Proof. The case x= 1 is trivial. When x= 2, the only solution to (1) is given by (x, k, y, n) = (2,3,3,2) (where we have n= 2). This fact is well-known; it follows e.g. from the nice result of Mih˘ailescu [11] concerning the Catalan equation. All the other cases are handled by Hajdu [6]. In view of the above lemma, we may assume that we have x∈ {5,6,9,10,13,14,17,18,21,22}. In these cases, the strategy of our proof is the following. First, using Baker’s method (for linear forms in two logarithms) we prove that one
4 A. B´ ERCZES, L. HAJDU, T. MIYAZAKI, AND I. PINK of the exponential variables kand nhas to be ”small”. For this we use results of Laurent [8]. Then the remaining cases will be handled separately. It is important to mention that we need to provide rather sharp upper bounds for kand n(which makes the proofs of our corresponding lemmas rather technical). The reason is that the ”small” values of kand nneed to be handled separately, one by one, by a numerical method, and the running time of our algorithm is very sensitive for the initial upper bounds for these parameters. When kis small, since xis fixed, the left hand side of equation (1) is fixed, and we only need to perform a simple check (which for ”large” values of kcan still be rather time consuming). When nis ”small” then for each possible values of n, we solve (1) locally, as a polynomialexponential congruence. At this stage we also make use of the program package Magma [2]. We note that this is the point where we need to require the assumption n > 2, since in case of n= 2 some of the occurring equations cannot be handled locally. So we start with deriving upper bounds for the exponential variables k, n in equation (1). As we have mentioned, for this purpose we use Baker’s method for linear forms in logarithms of two algebraic numbers. We need to introduce some notation. For an algebraic number αof degree dover Q, we define the absolute logarithmic height of αby the following formula: h(α) = 1 d log |a0|+ d X i=1 log max1,|α(i)|!, where a0is the leading coefficient of the minimal polynomial of αover Z, and α(1), α(2), ... , α(d)are the conjugates of αin the field of complex numbers. Let α1and α2be multiplicatively independent algebraic numbers with |α1| ≥ 1 and |α2| ≥ 1. Consider the linear form in two logarithms: Λ=b2log α2−b1log α1, where log α1,log α2are any determinations of the logarithms of α1, α2 respectively, and b1, b2are positive integers. We shall use the following result due to Laurent [8]. Lemma 3.2 ([8], Theorem 2).Let ρand µbe real numbers with ρ > 1 and 1/3≤µ≤1. Set σ=1+2µ−µ2 2, λ =σlog ρ.
ON THE EQUATION 1k+ 2k+· · · +xk=ynFOR FIXED x5 Let a1, a2be real numbers such that ai≥max {1, ρ|log αi|−log |αi|+ 2Dh(αi)}(i= 1,2), where D= [Q(α1, α2) : Q]/[R(α1, α2) : R]. Let hbe a real number such that h≥max Dlog b1 a2 +b2 a1+ log λ+ 1.75+ 0.06, λ, Dlog 2 2. We assume that a1a2≥λ2. Put H=h λ+1 σ, ω = 2 + 2r1 + 1 4H2, θ =r1 + 1 4H2+1 2H. Then we have log |Λ| ≥ −Ch02a1a2−√ωθh0−log C0h02a1a2 with h0=h+λ σ, C =C0 µ λ3σ, C0=sCσωθ λ3µ, where C0= ω 6+1 2sω2 9+8λω5/4θ1/4 3√a1a2H1/2+4 31 a1 +1 a2λω H!2 . Using this lemma, we show the following. Lemma 3.3. Let A={5,6,9,10,13,14,17,18,21,22}and consider equation (1) with x∈Ain integer unknowns (k, y, n)with k≥83, y ≥ 2and n≥3a prime. Then for y > x2we have n≤n0, for y > 106even n≤n1holds, and for y≤x2we have k≤k1, where n0=n0(x), n1= n1(x)and k1=k1(x)are given in Table 1. Proof. In the course of the proof we will always assume that x∈Aand we distinguish three cases according to y > x2,y > 106or y≤x2. Case I. y > x2 We may suppose, without loss of generality, that nis large enough, that is (3) n>n0. Further, by k≥83 we easily deduce that for every x∈Awe have (4) 1k+ 2k+···+xk<2xk<(x+ 1)k,
6 A. B´ ERCZES, L. HAJDU, T. MIYAZAKI, AND I. PINK x n0(y > x2)n1(y > 106)k1(y≤x2) 5 14,000 6,100 78,000 6 21,000 10,100 121,000 9 52,000 28,000 304,000 10 65,000 36,000 381,000 13 111,000 64,000 651,000 14 129,000 75,000 754,000 17 187,000 113,000 1,099,000 18 209,000 127,100 1,224,000 21 278,000 174,100 1,633,000 22 244,000 168,000 1,466,000 Table 1. Bounding nand kunder the indicated conditions and (5) 1k+ 2k+···+ (x−1)k<2(x−1)k. Since y > x2by (1), (4) and x≥5 we get that (6) k≥2n. Using (6) and the fact that nis odd we may write kin the form (7) k=Bn +rwith B≥1,0≤ |r| ≤ n−1 2. We show that in (7) we have r6= 0. On the contrary, suppose r= 0. Then, using (1) and (5) we infer by (7) that 2(x−1)k>1+2k+···+ (x−1)k=yn−xk=yn−xBn = (y−xB)(yn−1+···+xB(n−1))≥xB(n−1). Hence n < log x log x x−1+log 2 Blog x x−1. This together with x≤22 and B≥1 implies n < 82, which contradicts (3). Thus, r6= 0. On dividing equation (1) by ynwe obviously get (8) 1 −xk yn=s yn, where s= 1k+ 2k+. . . + (x−1)k. Using (7) and (8) we infer that (9) xr·xB yn −1 =s yn.
ON THE EQUATION 1k+ 2k+· · · +xk=ynFOR FIXED x7 Put (10) Λr=(rlog x−nlog y xBif r > 0, |r|log x−nlog xB yif r < 0. In what follows we find upper and lower bounds for log |Λr|. We distinguish two subcases according to 1−xk yn≥0.795 or 1 −xk yn<0.795, respectively. If 1 −xk yn≥0.795 then by (1) and (4) we immediately obtain a contradiction, so we may assume that the latter case holds. It is well known (see Lemma B.2 of [16]) that for every z∈Rwith |z−1|<0.795 one has (11) |log z|<2|z−1|. On applying inequality (11) with z=xk/ynwe get by (8), (9), (10) and xk6=ynthat (12) |Λr|<2s yn. Observe that (1) implies (13) k < nlog y log x. Thus by (12), (5) and (13) we infer that log |Λr|<−logx x−1 log x(log y)n+ log 4.(14) Next, for a lower bound for log |Λr|, we shall use Lemma 3.2 with (α1, α2, b1, b2) = (y xB, x, n, rif r > 0, xB y, x, n, |r|if r < 0. Using (1) and (4) one can easily check that α1>1 and α2>1. We show that α1, α2are multiplicatively independent. Assume the contrary. Then the set of prime factors of ycoincides with that of x. Since yis odd (as x6≡ 0,3 (mod 4)), hence xis also odd, that is, x∈ {5,9,13,17,21}. If xis a prime, i.e. x∈ {5,13,17}, then yhas to be a power of x, and equation (1) can be written as 1k+ 2k+···+xk=xm, k ≥2, m ≥2.
8 A. B´ ERCZES, L. HAJDU, T. MIYAZAKI, AND I. PINK One can verify that this equation has no solution (since xk< xm< 2xk< xk+1). If x= 9, then yhas to be a power of 3, and equation (1) can be written as 1k+ 2k+···+ 9k= 3m, k ≥2, m ≥2. Taking this equation modulo 4, we have 3+2·(−1)k≡(−1)m(mod 4). This implies that mis even, and we find 1k+ 2k+···+ 9k= 9m/2, which, as we already know, has no solution. If x= 21, then the set of prime factors of the integer 1k+ 2k+···+ 21k should be {3,7}. However, we can observe that the above integer is not divisible by 3 if kis even, and that it is divisible by 11 provided that kis odd. This is a contradiction. To sum up, we may assume that α1, α2are multiplicatively independent. Now, we apply Lemma 3.2 with the following choice of parameters (ρ, µ): for every x∈Awe choose µ= 0.57 uniformly, and set (15) ρ=(7.7 if x∈A\{22}, 7 if x= 22. In what follows we shall derive upper bounds for the quantities ρ|log αi|−log |αi|+ 2Dh(αi),(i= 1,2) occurring in Lemma 3.2. Since D= 1 and α2>1, for i= 2 we get (16) ρ|log α2|−log |α2|+ 2Dh(α2)=(ρ+ 1) log x. For i= 1 we obtain (17) ρ|log α1|−log |α1|+ 2Dh(α1)<ρ+ 1 2log x+ 2 log y−2 log g, where g= gcd(x, y). To verify that (17) is valid we shall estimate log α1and h(α1) from above, by using equation (1), i.e. s+xBn+r=yn. Observe h(α1) = h xB y≤log max{xB, y}−log g=(log y−log gif r > 0, log xB−log gif r < 0. If r > 0, then αn 1=y xBn=xr+s xBn =xr1 + s xk<2xr(as s<xk),
ON THE EQUATION 1k+ 2k+· · · +xk=ynFOR FIXED x9 so log α1<log 2 n+r nlog x≤log 2 n+n−1 2nlog x, whence ρ|log α1|−log |α1|+ 2Dh(α1)< <log 2 nlog x+n−1 2n(ρ−1) log x+ 2 log y−2 log g which by (15), (3) and x≥5 clearly implies (17). If r < 0, then αn 1=xB yn =x−r1−s yn< x−r=x|r|, so log α1<|r| nlog x≤n−1 2nlog x, and log xB= log α1+ log y < n−1 2nlog x+ log y, and we get ρ|log α1|−log |α1|+ 2Dh(α1)< <n−1 2n(ρ−1) + n−1 nlog x+ 2 log y−2 log g, which by (3) again implies (17). In view of (16) we can obviously take for every x∈A (18) a2= (ρ+ 1) log x. For the values a1we do the following. If we can calculate the exact value of g= gcd(x, y) then we use for a1the upper bound occurring in (17), while if we do not know the exact value of g= gcd(x, y) we use (17) with g= 1. Namely, we can take a1as (19) a1=(ρ+1 2log x+ 2 log yif x∈A\{22}, ρ+1 2log x+ 2 log y−2 log 11 if x= 22. To see that the choice of a1for x= 22 is valid we observe that (20) (Sk(22) ≡0 (mod 3) and Sk(22) 6≡ 0 (mod 9) if kis even, Sk(22) ≡0 (mod 11) if kis odd, Since by (3) nis large in equation (1), we may assume that kis odd, hence (20) together with (1), implies y≡0 (mod 11). Thus, since y
16 A. B´ ERCZES, L. HAJDU, T. MIYAZAKI, AND I. PINK Lemma 3.5. Let A={5,6,9,10,13,14,17,18,21,22}. Assume that equation (1) has a solution (x, k, y, n)with x∈Asuch that either: (i) k≥83 and x2< y ≤106, or (ii) k≥83 and y≤x2. Then we have n < 12. Proof. In the case (ii), by Lemma 3.3 we immediately get k≤k1. In the case of (i), by Lemma 3.3 we get n≤n0, which together with (1) and the assumption y≤106gives the estimate k < nlog y log x≤6n0log 10 log x. Put k0:= max n6n0log 10 log x, k1o, which for given xis a fixed number. For given x∈Alet us take any fix value of kwith 2 ≤k≤k0. For every prime 2 ≤p≤106we check whether Sk(x) is divisible by p (in fact we compute Sk(x) (mod p) and we check if it is 0 or not). If pdivides Sk(x), then we check if Sk(x) is also divisible by p12 or not. During our computations for every possible pair (x, k) we either found that there is no prime p≤106dividing Sk(x) at all, which by y≤106 proves there is no solution, or we could find a prime divisor p≤106 of Sk(x) with the property that p12 does not divide Sk(x) leading to the conclusion that n < 12. The computations were performed again in Magma [2]. Lemma 3.6. The only solution of equation (1) with 5≤x < 25 and n≥3under the assumption k≤100 is (x, k, y, n) = (8,3,6,4). Proof. A direct computation of Sk(x) for all possible pairs (k, x) corresponding to the requirements of Lemma 3.6, and checking whether it is a perfect power can be done in Magma [2] in a few seconds. 4. Proof of Theorem 2.1 In principle the proof is a simple combination of the above proved lemmas, namely of Lemma 3.3, Lemma 3.4, Lemma 3.5 and Lemma 3.6. Proof of Theorem 2.1. Clearly, it is enough to prove the theorem for n= 4 and for odd prime values of n. Further, the cases x∈ {1,2,3,4,7,8,11,12,15,16,19,20,23,24} are handled by Lemma 3.1. So now we only need to prove Theorem 2.1 for x∈A={5,6,9,10,13,14,17,18,21,22}.
ON THE EQUATION 1k+ 2k+· · · +xk=ynFOR FIXED x17 We split the proof into several subcases. The case k≤100 is completely covered by Lemma 3.6, so for the rest of the proof we may assume k > 100. If y > 106then by Lemma 3.3 we have n≤n1, and by Lemma 3.4 we know that there is no solution for 3 ≤n≤ n1, n prime or n= 4. This concludes the proof of Theorem 2.1 whenever y > 106. For y≤106by Lemma 3.5 we have n < 12. Thus by x≥5 from (1) we get the estimate k < nlog y log x≤66 log 10 log 5 <100, which has been treated already. References [1] M. A. Bennett, K. Gy˝ory, ´ A. Pint´er, On the Diophantine equation 1k+ 2k+ ···+xk=yn, Compos. Math. 140 (2004), 1417–1431. [2] W. Bosma, J. Cannon and C. Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), 235–265. [3] K. Gy˝ory, T. Kov´acs, Gy. P´eter, ´ A. Pint´er, Equal values of standard counting polynomials, Publ. Math. Debrecen 84 (2014), 259–277. [4] K. Gy˝ory, ´ A. Pint´er, On the equation 1k+ 2k+···+xk, Publ. Math. Debrecen 62 (2003), 403–414. [5] K. Gy˝ory, R. Tijdeman and M. Voorhoeve, On the equation 1k+2k+···+xk= yz, Acta Arith. 37 (1980), 234–240. [6] L. Hajdu, On a conjecture of Sch¨affer concerning the equation Sk(x) = yn, J. Number Theory 155 (2015), 129–138. [7] M. Jacobson, ´ A. Pint´er, G. P. Walsh, A computational approach for solving y2= 1k+ 2k+···+xk, Math. Comp. 72 (2003), 2099–2110. [8] M. Laurent, Linear forms in two logarithms and interpolation determinants II, Acta Arith. 133 (2008), 325–348. [9] ´ E. Lucas, Problem 1180, Nouvelles Ann. Math. 14 (1875), 336. [10] ´ E. Lucas, Solution de Question 1180, Nouvelles Ann. Math. 16 (1877), 429– 432. [11] P. Mih˘ailescu, Primary Cyclotomic Units and a Proof of Catalan’s Conjecture, J. Reine Angew. Math. 572 (2004), 167–195. [12] ´ A. Pint´er, A note on the equation 1k+ 2k+···+ (x−1)k=ym, Indag. Math. (N.S.) 8(1997), 119–123. [13] ´ A. Pint´er, On the power values of power sums, J. Number Theory 125 (2007), 412–423. [14] J. J. Sch¨affer, The equation 1p+ 2p+···+np=mq, Acta Math. 95 (1956), 155–189. [15] T. N. Shorey and R. Tijdeman, Exponential Diophantine equations, Cambridge University Press, Cambridge, 1986. [16] N. P. Smart, The Algorithmic Resolutions of Diophantine Equations, Cambridge University Press, Cambridge, 1998.
18 A. B´ ERCZES, L. HAJDU, T. MIYAZAKI, AND I. PINK [17] G. N. Watson, The problem of the square pyramid, Messenger of Math. 48 (1918), 1–22. A. B´ erczes and L. Hajdu, University of Debrecen, Institute of Mathematics H-4010 Debrecen, P.O. Box 12. Hungary E-mail address:[email protected] E-mail address:[email protected] T. Miyazaki Faculty of Science and Engineering, Gunma University, Gunma, 376-8515, Japan E-mail address:[email protected] I. Pink Institute of Mathematics, University of Debrecen H-4010 Debrecen, P.O. Box 12, Hungary and University of Salzburg Hellbrunnerstrasse 34/I A-5020 Salzburg, Austria E-mail address:[email protected]; [email protected]