Bounding Mixed Exponential-Algebraic Diophantine Equations

Date: 10/21/2010 at 06:46:32
From: Nick
Subject: solve in natural numbers the equation 2^x+x^2=3^y+y^3.

Dear Doctor Math, 

I'm trying to solve this system of equations, where k is an integer:

   2^x - 3^y = k
   y^3 - x^2 = k

The obvious solution is (x,y) = (3,2). I think that is the only one -- but
I can't prove it.

I know papers that discuss such equations invoke Baker's method and lower
bounds of the forms

   |a^x - b^y|
   |y^3 - x^2|

Date: 10/23/2010 at 21:20:34
From: Doctor Vogler
Subject: Re: solve in natural numbers the equation 2^x+x^2=3^y+y^3.

Hi Nick,

Thanks for writing to Dr. Math. 

That looks like a challenging Diophantine equation to solve, particularly
because it is mixed exponential (2^x, 3^y) and algebraic (x^2, y^3). I
suspect that modular arithmetic won't get you very far on this one, which
is usually the easy way to solve these kinds of equations. Perhaps Baker's
method is indeed your best bet. If you haven't used it before, then I
would recommend a book by Nigel Smart, entitled "The Algorithmic
Resolution of Diophantine Equations."

The basic idea is that there are various theorems which will give you a
lower bound on the quantity ...

   x log 2 - y log 3

... which depends on the size of x and y. The bounds generally have this
form, for some constant C:

   log | x log 2 - y log 3 | > -C * log max(|x|, |y|)

We use this theorem like so. Suppose

   2^x + x^2 = 3^y + y^3.

Then it follows that ...

   2^x * 3^-y = 1 + (3^-y)(y^3 - x^2)

... so that

   x log 2 - y log 3 = log(1 + (3^-y)(y^3 - x^2)).

The left side of the equation is our linear form in logarithms. The right
side of the equation is very close (when y is large) to the quantity

   (3^-y)(y^3 - x^2)
   
Using our inequality from Baker Theorem, we get

  log | log(1 + (3^-y)(y^3 - x^2)) | > -C * log max(|x|, |y|)

This is pretty close to ...

  log | (3^-y)(y^3 - x^2) | > -C * log max(|x|, |y|)

... and that's the same as ...

  -y log 3 + log|y^3 - x^2| > -C * log max(|x|, |y|)

... or

  log|y^3 - x^2| + C * log max(|x|, |y|) > y log 3

Notice that the left side of this equation involves logs of y, while the
right side does not. So you can use this equation to show that y can't be
too large and still solve your Diophantine equations.

Unfortunately, even for your case -- which is as simple as you can get,
with two variables and integer operands -- a typical theorem that gives a
lower bound on a linear form in logarithms will have a constant that is in
the millions or billions or so. So your upper bound on y is generally
pretty big -- too big to actually test all of the y values up to the
bound.

Here, a technique such as lattice reduction, which uses the actual values
of the logarithms (to a finite precision) and a large bound on y, would
reduce it to something more reasonable, or at least small enough that a
computer could then try all of the y values up to the given bound.

It's all a lot of work, but it's pretty straight-forward, and the end
result is that Baker's Theorem gives a way to completely solve your
Diophantine equations.

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: 10/25/2010 at 04:52:36
From: Nick
Subject: Thank you (solve in natural numbers the equation 2^x+x^2=3^y+y^3.)

Thank you!

Let me study what you wrote and try to solve the equation. If I need some
more help, I'll write back.

Yours sincerely,

Nick