Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

A Diophantine Determined with a Data-Driven Approach

Date: 06/24/2012 at 01:41:55
From: Mohammad
Subject: Solve 4 x^2 y^2 +x^2 +y^2=n^2

I'm working on an Euler problem, which I have been able to simplify down
to solving the Diophantine equation

   4*x^2*y^2 + x^2 + y^2 = n^2

I have tried searching for an online Diophantine equation solver, but none
supports the form 4*x^2*y^2 +x^2 +y^2 = n^2.

I have also tried making programs to check different values for x, y, and
n, and seeing if they satisfy this condition. When n is huge, this
approach becomes too slow :(

After quite a few more hours of work, I'm wondering if there is any way to
represent x and y in terms of dummy variables u and v so as to simplify
this into a form of u^2 + v^2 = n^2.



Date: 07/07/2012 at 17:38:34
From: Doctor Vogler
Subject: Re: Solve 4 x^2 y^2 +x^2 +y^2=n^2

Hi Mohammad,

Thanks for writing to Dr. Math. 

(Sorry about the delay, but I had to think about this for a while. Long
story short: it certainly can't be simplified into the form 
u^2 + v^2 = n^2.)

That's a really interesting question. For a moment, I thought it might be
useful to factor it into the form

   (4x^2 + 1)(4y^2 + 1) = 4n^2 + 1.

But I couldn't figure out how this was more useful than the original form,
except perhaps if you wanted all solutions for a particular moderately
large value of n.

Next, I tried having a computer generate some small solutions to get an
idea of what the family of solutions looks like. It didn't appear to be a
finite set, and it didn't seem to have an obvious pattern, although I did
notice that there were a lot of solutions where either x or y was very
small. That made me consider firstly what are all of the solutions where 
y = 1 and secondly how to find all of the solutions for other fixed values
of y.

Of course, if y = 0, then all solutions have x = n or x = -n.  If y = 1,
then the equation becomes

   n^2 - 5x^2 = 1.

This is a classic Pell equation. Pell equations are very interesting
equations and well worth learning about, but their solutions are quite
well-understood by those who have studied them. They are related to
quadratic number fields. 

For example, this one is related to the number field Q(sqrt(5)). It turns
out that all solutions have the form ...

   n + x*sqrt(5) = (1/2 + 1/2*sqrt(5))^(6k)
                 = (9 + 4*sqrt(5))^k

... for different integers k. (Positive integers k give you all positive
values for n and x, whereas negative integers k -- as well as integers k
where you negate the right side of the equation -- give you the other
integer solutions for n and x.)

This means that you can find solutions with y = 1 by raising 9 + 4*sqrt(5)
to some power, computing the result exactly in the form a + b*sqrt(5), and
then the solution has n = a, x = b, and y = 1. You can also start with 
n = 1 and x = 0 and then move from one solution to the next by changing n 
and x, respectively, to

   9n + 20x     and     4n + 9x.

This corresponds to multiplying by 9 + 4*sqrt(5). 

Alternately, you can use this fact:

   n - x*sqrt(5) = (9 - 4*sqrt(5))^k

This lets you write out the explicit formula for n and x, which is

   n = [ (9 + 4*sqrt(5))^k + (9 - 4*sqrt(5))^k ]/2,
   x = [ (9 + 4*sqrt(5))^k - (9 - 4*sqrt(5))^k ]/(2*sqrt(5)).

You can do a similar analysis for other values of y. For example, if
y = 2 (or -2), then ...

   n^2 - 17x^2 = 4

... and now the solutions with y = 2 have ...

   n + x*sqrt(17) = 2(4 + sqrt(17))^(2k).

I did this for a few other values of y, and I kept finding a very similar
base for the right side of the equation. The pattern seemed to indicate

   (2y + sqrt(4y^2 + 1))^2.

And the solutions always seemed to be a power of this base times y (or
-y). I knew from my knowledge of quadratic number fields that sometimes
there would be other numbers (quadratic numbers with norm y^2) that you
could also multiply by, but these seemed to show up infrequently for small
values of y.

So next I asked the question: How many of my solutions come from this
form?

   n + x*sqrt(4y^2 + 1) = y(2y + sqrt(4y^2 + 1))^(2k).

So I ran down my list of computer-generated solutions and for each one
computed the value of

          log(n + x*sqrt(4y^2 + 1)) - (log y)
   2k = ---------------------------------------
               log(2y + sqrt(4y^2 + 1))

I found lots of small even integers, as I expected, as well as a number of
non-integers, which was also not terribly surprising. Of course, solutions
come in pairs, since you can always switch x and y, so really this gave me
two different values, for 2k for each solution, one of which always seemed
to be between 0 and 1, and the other was larger than 1. Moreover, when one
was an even integer, the other had to be the smaller non-integer between 0
and 1.

Then I started to notice that even when both values were non-integer
values, the larger would be either 2 more than one of the non-integers I
had gotten previously, or would be 2 minus one that I had gotten
previously. I knew that adding 2 corresponded to multiplying ...

   n + x*sqrt(4y^2 + 1)

... by ...

   (2y + sqrt(4y^2 + 1))^2 = (8y^2 + 1) + (4y)*sqrt(4y^2 + 1).

From here, it wasn't too hard to determine that the other method meant
multiplying by ...

   1/(2y + sqrt(4y^2 + 1))^2 = (2y - sqrt(4y^2 + 1))^2,

... and taking the absolute values of n and x if necessary.

So I knew that I could easily reverse this process and start from a
solution like n = x and y = 0 (or n = y and x = 0) and then repeatedly do
one of the above changes. In fact, I could write out the formulas very
easily. The transformations change one solution (x, y, n) to

  (transf. A) ( (8y^2 + 1)x + 4yn, y, (8y^2 + 1)n + 4xy(4y^2 + 1) )
  (transf. B) ( (8y^2 + 1)x - 4yn, y, (8y^2 + 1)n - 4xy(4y^2 + 1) )
  (transf. C) ( y, x, n )

You can easily check that if (x, y, n) is one integer solution to your
equation, then each of the above three transformations is also an integer
solution to the same equation. Of course, doing A and then B just gets you
back to the same solution again, but you can repeat A (or B) several times
and keep getting new solutions. And doing C twice just gets you back to
the same solution, but when you mix A (or B) with C, then you get
additional solutions. By using this strategy, I was able to generate lots
and lots of solutions, including extremely large ones, in seconds.

The only thing remaining was proving that all solutions can be generated
in this way. To do this, the strategy was to prove that if you start with
any solution to your equation, then you can do transformations A, B, and C
in order to get back to an initial solution with y = 0, because that would
mean that you can do the reverse transformations (A and B are reverses of
one another, and C is its own reverse) to get from the initial solution to
the other one.

So let's suppose that we have some solution (x, y, n) to the equation. If
x, y, or n is negative, then we negate it so that all three are
non-negative. Next, if x < y, then we do transformation C and restart.
Otherwise, if y > 0, we do transformation B and restart. Otherwise, y = 0,
and so we are done.

First I am going to claim that the sum of (the absolute values of) x, 2y,
and n always gets smaller by using the above strategy, until x = 0, since
this will prove that the process will eventually end. (A positive integer
can only get smaller a finite number of times.) If x < y, then swapping x
with y will make x + 2y smaller. Otherwise, we have 0 < y <= x, 0 < n, and
we do transformation B.  

Now, I want to prove that

     [(8y^2 + 1)x - 4yn] + 2y
   + [(8y^2 + 1)n - 4xy(4y^2 + 1)]
                                   < x + 2y + n

This is equivalent to ...

      (8y^2 + 1)x - 4yn
    + (8y^2 + 1)n - 4xy(4y^2 + 1)
                                   < x + n

... and to ...

      (8y^2 - 4y)n < (16y^3 - 8y^2 + 4y)x

Since y > 0, it is also equivalent to ...

         (8y - 4)n < (16y^2 - 8y + 4)x

... and to ...

         (2y - 1)n < (4y^2 - 2y + 1)x.

If we square this, then we get something that we can compare to the
equation

       4 x^2 y^2 + x^2 + y^2 = n^2.

This tells us where to go from here: Since y > 0, and y is an integer,
that means that y >= 1, and therefore

   2y - 1 > 0
   4y - 1 > 0

So,

         y^2 * (4y - 1) > 0.

Also, since x >= y (and y > 0), that means that

       4*y^2*x^2 >= 4*y^4.

Therefore, we conclude that

       4*y^2*x^2 - 4*y^4 + y^2 * (4y - 1) > 0.

Since we know that n^2 = 4 x^2 y^2 + x^2 + y^2, that means that

     [(4y^2 - 2y + 1)x]^2 - [(2y - 1)n]^2
   = [(4y^2 - 2y + 1)x]^2 - (2y - 1)^2*(4*x^2*y^2 + x^2 + y^2)
   =   4*y^2*x^2 - 4*y^4 + 4*y^3 - y^2
   > 0

Therefore,

   [(4y^2 - 2y + 1)x]^2 > [(2y - 1)n]^2.

But since x > 0 and n > 0 and y >= 1 (which implies that 4y^2 > 2y and 
2y > 1), each factor on both sides is positive, so that means that ...

  (4y^2 - 2y + 1)x > (2y - 1)n,

... which is what we wanted to prove!

So we have successfully proven that our strategy for getting to smaller
solutions will always keep getting smaller until y = 0, which means that
we can start from a solution with y = 0 and then do transformations A, B,
and C to get to all other solutions very quickly.

Of course, you'll probably want to use a recursive function to enumerate
all of the solutions, say, less than some particular number, since you
will be able to use transformation A any number of times, followed by
transformation C, followed by more A's, and so on. I'll let you work out
the programmatic details.

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/ 
Associated Topics:
College Number Theory

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/