Solving a Quartic Diophantine Equation

Date: 04/23/2008 at 17:07:00
From: Colin
Subject: Solving a strange quartic Diophantine equation

Give other solutions than 0 for the following Diophantine equation
(integer solutions!) 

x^4 + 2191x^3 + 1931x^2 + 1037x + 6754801 = y^2

I did not know any other method than brute force to solve it. But this
cannot be the case for a math question.

I've searched the web for a long time and found a lot of special case
quartic and cubic theory where the equation can easily be turned into
elliptic curves. Unfortunately these are all special case formulas
while my equation seems to be a general quartic.

What I did find was a beautiful document by N. Tzanakis called
"Solving elliptic Diophantine equations by estimating linear forms
in elliptic logarithms. The case of quartic equations"

He tries to solve equations (integer solutions) of the form 
V^2 = aU^4 + bU^3 + cU^2 + dU + e^2. It cannot be a coincidence that
the last part of my equation: 6754801 is a square (2599^2) so that
this document seems to be (partly) about my equation.

However since my math knowledge does not go this far (yet), I cannot
solve the equation. My question is: Could you give me some starting
point and is this equation solvable at all? 

Thanks in advance.

Date: 04/23/2008 at 21:03:18
From: Doctor Vogler
Subject: Re: Solving a strange quartic Diophantine equation

Hi Colin,

Thanks for writing to Dr. Math.  Your Diophantine equation is
teetering right there on the edge of what today's mathematicians can
solve.  But it is special in two ways:  First of all, the polynomial
in x has even degree.  Second, the leading coefficient is a square
(namely, 1).  Because of this, we can solve your equation.  If the
leading coefficient wasn't a square, the best we could do is transform
it to an elliptic curve, and there are three general methods for
finding (provably) all integer points on elliptic curves.  One of the
three methods is the one suggested by Tzanakis, which is sometimes
known by the name of linear forms in elliptic logarithms.  But your
case is easier for the two reasons I mentioned.

Here's how our solution goes.

First notice that if n and m are integers, then either n^2 = m^2, or
n^2 and m^2 differ by at least 2n - 1.  Why is that?  Because the
closest perfect square to n^2 is (n-1)^2.

Now let's complete the square on your polynomial.  Suppose that x and
y are both integers, and

  y^2 = x^4 + 2191x^3 + 1931x^2 + 1037x + 6754801.

Then the right side is close to the polynomial

  (x^2 + 2191/2*x - 4792757/8)^2.

In order to keep things integers, we'll multiply both sides of the
equation by 8^2.  Then your equation is equivalent to

  (8y)^2 = (8x^2 + 8764x - 4792757)^2 + 84007511064x - 22970087353785

Now we apply the statement I made earlier using m = 8y and

  n = 8x^2 + 8764x - 4792757.

That is, either n^2 = m^2, which means that

  84007511064x - 22970087353785 = 0

(and I'll let you explain why no integer satisfies this equation), or
n^2 and m^2 differ by at least 2n - 1.  That means that

  abs(84007511064x - 22970087353785) >= 16x^2 + 17528x - 9585515.

(That's "the absolute value of.")  But this is only possible when x is
sufficiently small, since the quadratic polynomial on the right will
grow faster than the linear polynomial on the left.

If you look at the two quadratic equations, however, you find that
"sufficiently small," in this case, means x is smaller than about 5251
million.  That's a lot of numbers to check.  (It's not quite out of
the realm of feasible on a computer, but it would still take almost a
day on one computer.)

We can do a little better by splitting the work in two pieces.  Let's
look again at our two squares n^2 and m^2.  I said that either n^2 =
m^2, or the two squares differ by at least 2n - 1.  In fact, if m and
n have the same sign, then either n = m + k for some small integer k
(say abs(k) < K) or we have

  abs(n^2 - m^2) >= K(2n - K).

That's because if m and n have the same sign, then

  abs(n + m) = abs(n) + abs(m)

and if k = n - m does *not* satisfy abs(n - m) < K, then that means

  abs(n - m) >= K

and so

  abs(n^2 - m^2) =  abs(n - m)*abs(n + m)
                 >= K*(abs(n) + abs(m))
                 >= K*(abs(n) + abs(n + m - n))
                 >= K*(abs(n) + abs(n) - abs(m - n))
                 >= K*(2*abs(n) - K).
                 >= K*(2n - K).

So let's choose K near the square root of 84007511064/16, such as
50000.  Now if we can test whether n = m + k for abs(k) < 50000 is
possible, then all other solutions will have

  abs(n^2 - m^2) >= 50000(2n - 50000).

Recall that we were taking

  m = 8y
  n = 8x^2 + 8764x - 4792757

So that means that either

  8y = 8x^2 + 8764x - 4792757 - k

for some k between -50000 and +50000, or

  abs(84007511064x - 22970087353785) >=
              800000*x^2 + 876400000*x - 481775700000.

which can't happen if abs(x) > 110000.  So now we can have our
computer check all x between -110000 and +110000 and then also check
all k between -50000 and +50000.  For each x, we test if

  x^4 + 2191x^3 + 1931x^2 + 1037x + 6754801

is a perfect square.  Testing all of these takes less than a second on
a computer, and the only solution is x = 0.  For each k, we take m = n
- k or

  8y = 8x^2 + 8764x - 4792757 - k

and substitute into

  (8y)^2 = (8x^2 + 8764x - 4792757)^2 + 84007511064x - 22970087353785

giving

  (8x^2 + 8764x - 4792757 - k)^2
         = (8x^2 + 8764x - 4792757)^2 + 84007511064x - 22970087353785

  k^2 - 2(8x^2 + 8764x - 4792757)k = 84007511064x - 22970087353785

which is a quadratic equation in x whose discriminant is

  64k^3 + 920703680k^2 + 4415052898501824k + 7057261915168082412096

and this discriminant has to be a perfect square for x to have a
rational solution (such as an integer solution).  So for each k, we
test if that cubic is a perfect square.  Testing all of these takes
less than a second, and the only solution is k = 0, but that's only
because the leading coefficient is zero in this case, and the rational
solution for x is

  x = 22970087353785/84007511064

which is not an integer.

So we conclude that x = 0 is the only integer for which

  x^4 + 2191x^3 + 1931x^2 + 1037x + 6754801

is a perfect square.

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/