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
- References:
- how to solve the integer equation Abs[3^x-2^y]=1
- From: a boy <a.dozy.boy@gmail.com>
- how to solve the integer equation Abs[3^x-2^y]=1