Proof with Exponential Diophantine InequalityDate: 03/10/2008 at 15:36:45 From: John Subject: Claim: |2^(n+1/2) - 3^m|<1 if and only if n = m = 1. I would like to know how to prove the following claim...or, at least, obtain some hints as to how to proceed. Claim: Let m and n be positive integers. Then Abs|2^(n+1/2) - 3^m| < 1 if and only if n = m = 1. Using Mathematica, I have shown it to be true for all m if n < 10^5 and for all n if m < 10^5. I have proved it to be true when the gcd(2m+1,n) is not equal to one. Accordingly, I need a proof of it when 2m+1 and n are relatively prime. Date: 03/12/2008 at 20:14:30 From: Doctor Vogler Subject: Re: Claim: |2^(n+1/2) - 3^m|<1 if and only if n = m = 1. Hi John, Thanks for writing to Dr. Math. I'd be interested to see your proof for the case where gcd(2m+1,n) is not one. The only idea that comes to my mind is to use Diophantine approximation, which is a very sophisticated (and complicated) tool for dealing with exponential Diophantine problems using inequalities. The idea is that there are theorems giving lower bounds for expressions of the form x log a + y log b, for example. We can put your inequality in this form too. For example, you want to find integers which satisfy abs|2^(n+1/2) - 3^m| < 1 or -1 < 2^(n+1/2) - 3^m < 1. Dividing by 2^(n+1/2), we get -2^(-n-1/2) < 1 - 3^m*2^(-n-1/2) < 2^(-n-1/2). or 1 - 2^(-n-1/2) < 3^m*2^(-n-1/2) < 1 + 2^(-n-1/2). Then we can take the logs and get log(1 - 2^(-n-1/2)) < m*log 3 - (n+1/2)*log 2 < log(1 + 2^(-n-1/2)). Using the inequalities -x < log (1 - x) < 0 and 0 < log (1 + x) < x + x^2, valid for small positive x, we get -2^(-n-1/2) < m*log 3 - (n+1/2)*log 2 < 2^(-n-1/2) + 2^(-2n-1). and -2^(-n+1/2) < (2m)*log 3 - (2n+1)*log 2 < 2^(-n+1/2) + 2^(-2n). Then we need to use a theorem giving a lower bound for a linear form in logarithms. The idea of bounding logarithmic forms came from Alan Baker, who basically created a branch of mathematics by doing so. His original results were generalized and improved (such as by giving tighter bounds) by himself and others many times. One such theorem is the following, by Baker and Wustholz (proved in the journal article "Logarithmic forms and group varieties," J. Reine Angew. Math., 442, 19-62, 1993). Theorem: Suppose that n >= 2, and x_1, ... x_n are algebraic numbers not equal to 0 or 1, and K is a number field containing x_1 through x_n and has degree d over Q (the field of rational numbers). Define a modified height by hm(x) = max{ h(x), |log x|/d, 1/d }. Then if b_1, ... b_n are integers with b_1 log x_1 + ... + b_n log x_n =/= 0 and B = max{ |b_1|, ..., |b_n| } >= 3, then -c*hm(x_1)*...*hm(x_n)*log B < log |b_1 log x_1 + ... + b_n log x_n| where c = 18*(n+1)!*n^(n+1)*(32d)^(n+2)*log(2nd). In case you're less familiar with algebraic numbers and heights, I'll specialize this theorem to the case where the x's are integers. Theorem: Suppose n >= 2, and x_1, ... x_n are integers bigger than 1. Define hm(x) = max{ log x, 1 } (which is log x unless x = 2, in which case it's 1). Then if b_1, ... b_n are integers with b_1 log x_1 + ... + b_n log x_n =/= 0 and B = max{ |b_1|, ..., |b_n| } >= 3, then -c*hm(x_1)*...*hm(x_n)*log B < log |b_1 log x_1 + ... + b_n log x_n| where c = 18*(n+1)!*n^(n+1)*(32)^(n+2)*log(2n). In your case, since we want a lower bound for |(2m)*log 3 - (2n+1)*log 2|, which can't be zero (I'll leave it to you to prove this), we take x_1 = 3, x_2 = 2, b_1 = 2m, b_2 = -(2n+1), B = 2n+1 (I'll leave it to you to explain why 2n+1 > 2m), and c = 18*3!*2^3*32^4*log(4) < 1255940637, so e^(-1255940637 * log(3) * log(2n+1)) < |(2m)*log 3 - (2n+1)*log 2| < 2^(-n+1/2) + 2^(-2n) < 2^(-n+1) (where the last inequality is valid for n >= 1). Taking logs again, we get -1255940637 * log(3) * log(2n+1) < (-n+1)*log(2) which implies n < 1 + 1990618813 * log(2n + 1). Of course, if n is very large, like n > 10^100, then this is impossible (you can prove this by induction, for example), so n <= 10^100, which implies that n < 1 + 1990618813 * log(10^101) < 462940489671 which implies that n < 1 + 1990618813 * log(925880979343) < 54849533729. Repeating a few more times, we get n < 50436566565. Of course, you still don't want to check 50 billion values for n in Mathematica. So next we use continued fractions. You see, the best rational approximations to a real number are always continued fraction convergents of the real number. For example, see Wikipedia: Continued Fractions http://en.wikipedia.org/wiki/Continued_fraction and click on Best rational approximations in the "contents" box (or scroll down). Well, if |(2m)*log 3 - (2n+1)*log 2| < 2^(-n+1) for n large (say n > 10^5, since you already checked up to that point), then (2n+1)/(2m) is an especially good approximation to (log 3)/(log 2), since |(log 3)/(log 2) - (2n+1)/(2m)| < 1/(2^(n-1)*(log 2)*(2m)). So the continued fraction for (log 3)/(log 2) begins 1, 1, 1, 2, 2, 3, 1, 5, 2, 23, 2, 2, 1, 1, 55, 1, 4, 3, 1, 1, 15, 1, 9, 2, 5, 7, 1, 1, 4, 5, 17, 5, 1, 17, .... and the list of convergents begins 1, 2, 3/2, 8/5, 19/12, 65/41, 84/53, 485/306, 1054/665, 24727/15601, 50508/31867, 125743/79335, 176251/111202, 301994/190537, 16785921/10590737, 17087915/10781274, 85137581/53715833, 272500658/171928773, 357638239/225644606, 630138897/397573379, 9809721694/6189245291, 10439860591/6586818670, 103768467013/65470613321, 217976794617/137528045312, 1193652440098/753110839881, 8573543875303/5409303924479, 9767196315401/6162414764360, 18340740190704/11571718688839, 83130157078217/52449289519716, 433991525581789/273818166287419, 7460986091968630/4707358116405839, .... So we can just check these values for (2n+1)/(2m), and it turns out that none of them are remotely close enough to (log 3)/(log 2) to satisfy the original inequality -1 < 2^(n+1/2) - 3^m < 1, and later convergents will always have n > 51 billion, so that means that we've checked everything we need to! And the only solution is the one you found. There is also a generalization to the method of continued fractions which works when your problem involves a linear form in more than two logarithms, and it uses lattice basis reduction. But I've probably already overwhelmed you with too much sophisticated math for now, so I'll leave off. Nevertheless, if you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ Date: 03/20/2008 at 22:37:55 From: John Subject: Thank you (Claim: |2^(n+1/2) - 3^m|<1 if and only if n = m = 1.) Wow! After studying your proof, I feel about the way Dorothy must have felt after she first saw the Wizard of Oz. I am impressed with what you did and appreciate getting the answer you provided. It was quite understandable. Thank you! |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/