MathGroup Archive 2009

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: how to solve the integer equation Abs[3^x-2^y]=1

  • To: mathgroup at smc.vnet.net
  • Subject: [mg103043] Re: [mg102988] how to solve the integer equation Abs[3^x-2^y]=1
  • From: Daniel Lichtblau <danl at wolfram.com>
  • Date: Sat, 5 Sep 2009 05:36:11 -0400 (EDT)
  • References: <200909031110.HAA24198@smc.vnet.net>

a boy wrote:
> Does the equation |3^x-2^y|=1 give only 4 groups of solution?
> (x,y)= (0,1),
>           (1,1),
>          (1,2),
>           (2,3)
> 
> can anyone give any else solution?
> when the two integers x and y become bigger and bigger, is there a
> pair integer (x,y) to give a small value for  |3^x-2^y|? Or else,how
> to prove the equation |3^x-2^y|=1having only 4 groups of integer
> solution?

You now have a proof, at least for one of the two cases. I'll show a 
method to find solutions to related problems, or show that there are no 
solutions in certain size ranges.

The general problem: find solutions to

j^m - k^n = s

where j<k are given integers, m and n are unknown nonnegative integer 
exponents, and s is a small integer (small being dependent on various 
sizes that show up; this is a bit of hand-waving).

We thus have j^m approximately equal to k^n in the sense that their 
ratio is close to 1 (this is one place where "s small" enters). That is

m*log(j) - n*log(k) is approximately zero.

In a bit more detail, suppose the equation has a solution. Take logs on 
both sides of
k^n = j^m - s
we obtain
n*log(k) = m*log(j) + log(1-s/j^m)
Now observe we can approximate the right hand side, to first order, as
m*log(j) - s/j^m

Suppose we wish to find solutions in the range u<m<2*u, and also suppose 
u is not "tiny" (say, u>=10; we can handle smaller cases by brute 
force). We set up an integer lattice as follows.

round(j^u*log(j))    1    0
round(j^u*log(k))    0    1

Then there is an element in this lattice of the form {x,m,n} where x is 
"small". Indeed, it is in the ballpark of j^u*s/j^m, and this is no 
larger than s by assumption on u<m. Thus we have a lattice element no 
larger than roughly 3*u (since clearly n<m<2*u).

We can use LatticeReduce to find such a lattice element. For two rows it 
is guaranteed (from basic literature on the topic) to produce a row no 
larger than twice the smallest element in the lattice.

Case 1: If the second and third elements of the smallest row 
significantly exceeds twice the above value, then clearly there is no 
solution in the desired range. (Significant, in this case, depends on 
various estimates, size of s, etc. In practice the adverb can be removed 
provided s is small). Notice that a sufficiently large "small" vector 
implies nonexistence of solutions in a range perhaps larger than 2*u.

Case 2: If the second and third elements of the smallest row are in the 
desired size range, then we check to see if it gives a solution {m,n}. 
Note (see example below): the solution we obtain might have j<=u.

Case 2 b: If not, then our test is inconclusive. I believe there are 
planar lattice reduction refinements that might be used to show there 
are no other sufficiently small lattice elements to satisfy the 
equation, but this would take more work than I'm willing to do.

Here is an example. We look for m, n so that 3^m - 13^n is small (I use 
these because I know there is such a pair). I'll look for a solution 
with m in the range 5 to 10.

mult = 3^5;
a = 3;
b = 13;
lat = Round[{{mult*Log[3],1,0}, {mult*Log[13],0,1}}]
Out[35]= {{267, 1, 0}, {623, 0, 1}}

In[36]:= redlat = LatticeReduce[lat]
Out[36]= {{0, 7, -3}, {89, -2, 1}}

Our small solution has m=7, n=3. We see what this gives.

In[37]:= {3^7,13^3}
Out[37]= {2187, 2197}

So they differ by 10.

If I use a multiplier of 3^10 I get the same solution (this time the 
small vector is {-270,7,-3}). While we (again) obtain a solution for 
which u<10, there is nothing above to claim this cannot happen.

If I go to 3^20, that is, try for u<20<40, our smallest row is
{77044, -21365, 9151}. This is the "greatly exceeds" case, so we have no 
solutions with 10<m<20.

I apologize for a bit of sloppiness in the statements and exposition. 
I'm sure it could be made more precise, but not without more time and 
effort than I'm willing to give, and more length than most anyone would 
be willing to read.

Daniel Lichtblau
Wolfram Research







  • Prev by Date: Re: random variable
  • Next by Date: Thumbnail Method Option
  • Previous by thread: Re: how to solve the integer equation Abs[3^x-2^y]=1
  • Next by thread: Re: how to solve the integer equation Abs[3^x-2^y]=1