Proof with Exponential Diophantine Inequality

Date: 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!