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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.