Monday, November 09, 2009
Hasse Interrogation
Here's a bit about what I've been working on recently; the concept is something I've been calling "Hasse Interrogation".
Consider an equation -- say x^2 + 51 = y^2. Since this is a simple quadratic, the "Hasse Principle" applies. That means that if you solve the equation mod various primes, and integer solutions exist, then the equation is generally solvable in the rationals (any number that can be expressed as a fraction). This is a nice technique because you can quickly determine if any solutions exist before trying to solve the equation through the normal means (which, in this case, involves factoring 51).
Now, the trick is to break down the equation you're trying to solve into specially-formulated "chunks" and see if they have solutions via an application of the Hasse Principle. If you construct the "chunks" properly, then you can draw various conclusion about what a solution to your would look like.
This is where figurate numbers come in handy -- we can take any quadratic of the form x^2 + n = y^2 and use the Hasse Principle to see if these equations have rational solutions:
4a^2 + n = y^2
9b^2 + n = y^2
25c^2 + n = y^2
49d^2 + n = y^2
You'll notice that the x-variable coefficient is always a square of a prime number. Squares are useful here because they correspond to possible digit groupings for x. Recall that a square number can be written as:
1+3+5+7...
So, imagine that we group digits, like this:
1+3 + 5+7 + 9+11 + 13+15
This would imply that the total length of the square representation of x is divisible by 2. Without going into the rather trivial math behind it, you can presume that if 4a^2 + n = y^2 is solvable, then we can immediately infer that x == 0 mod 2 in our original equation because the digits of the square representation of x will group into twos. The same applies to 9: if 9b^2 + n = y^2 passes the Hasse Principle test, then x == 0 mod 3 (or digits can group into threes).
The fun part (and the part I'm currently working on) is that we can get a useful answer for every prime, thus we can build a "profile" for the variable x (which can be used to determine the arithmetic progression where we may find a non-trivial solution). Again, we use specially-constructed equations and apply the Hasse Principle. For instance, we can determine if these equations have solutions:
9a^2 + n = y^2
9b^2 + 6b + n + 1 = y^2
9c^2 + 12c + n + 1 = y^2
These correspond to x == 0 mod 3, x == 1 mod 3, and x == 2 mod 3 respectively (again, showing this is the case is fairly trivial).
Generally speaking only one of those equations will have integer solutions for a particular value of n. I say generally because, in practice, there are various "obstructions" that you have to take into account. For instance, there is always the trivial answer which can interfere with finding usable solutions. In the case of x^2 + 51 = y^2, the trivial answer is:
25^2 + 51 = 26^2
Hence x could be 25, and therefore x == 0 mod 5 would be a true but not "useful" answer if we're trying to factor 51. Since these "obstructions" are easy to calculate, we can simply avoid testing against primes that factor the trivial case. There is another fly in the ointment, however, and one that appears to run a bit deeper. In many instances a _rational_ solution may exist but an _integer_ solution may not; indeed, with large values of n this appears to often be the case when considering x, such that x is not congruent to 0 mod p (where p is the prime currently under consideration).
As a play-along example, I'll use the handy online Quadratic Diophantine Equation Solver developed by Dario Alpern. Let n = 32743. First, we compute the "trivial" solution. Let x = (n-1)/2, then we have:
16371^2 + 32743 = 16372^2
We will test the value 16371 against each prime we consider to see which answers we should "throw out". We start with p = 2, which gives:
1.) 4a^2 + 32743 = y^2, and
1.) 4b^2 + 4b + 32743 + 1 = y^2
We'll "normalize" these equations by bringing y^2 to the other side so the whole thing equals zero; this gives
3.) 4a^2 + 32743 - y^2 = 0, and
4.) 4b^2 + 4b + 32743 + 1 - y^2 = 0
Plugging these in to Dario's calculator, we get:
3.) has no solutions, therefore x is not congruent to 0 mod 2, and
4.) has solutions, therefore x == 1 mod 2
To see what's happening, be sure to click the radio button for "Step-by-step", in which case equation 3 returns the output:
and equation 4 gives:
Note that we're not concerned with the actual answer here, just whether or not the equations have solutions mod 9, 16, and 25.
Now, remember our trivial answer? It was odd, therefore x == 1 mod 2 could apply to both a "good" x and our "trivial" x. In this case we don't need to discard this solution, since there were only two possibilities. We now move on to p = 3. Our normalized equations are:
5.) 9c^2 + 32743 - y^2 = 0
6.) 9d^2 + 6d + 32743 + 1 - y^2 = 0
7.) 9e^2 + 12e + 32743 + 4 - y^2 = 0
And Dario's calculator gives:
5.) Has solutions, coincides with our "trivial" solution ( 0 == 16371 % 3)
6.) No solutions
7.) No solutions
Since our "trivial" solution was the only possible solution, we can safely assume that a "good" value for x == 0 mod 3. Moving on, let p = 5:
8.) 25f^2 + 32743 - y^2 = 0
9.) 25g^2 + 10g + 32743 + 1 - y^2 = 0
10.) 25h^2 + 20h + 32743 + 4 - y^2 = 0
11.) 25i^2 + 30i + 32743 + 9 - y^2 = 0
12.) 25j^2 + 40j + 32743 + 16 - y^2 = 0
Our "trivial" solution corresponds to 1 mod 5, thus equation 9 is our "suspect" equation in this set:
8.) Has no solutions.
9.) Has solutions, but is "suspect"
10.) Has no solutions.
11.) Has no solutions.
12.) Has solutions, is not "suspect".
So far we have x == 1 mod 2 and x == 0 mod 3. We now have a special case; it's possible that equation 12 could have _rational_ solutions but not have _integer_ solutions (the Hasse Principle only guarantees rational solutions). Thus we cannot throw out equation 9's result that x == 1 mod 5; we now have two possible profiles for x (x == 1 mod 2, x == 0 mod 3, x == 1 mod 5 or x == 4 mod 5). This is the "rational" obstruction that I referred to earlier, and so we may want to throw out this answer completely to keep from "branching" within our possible solution set.
We'll continue, then, to build up the profile and see if we need this solution. So far our worst-case scenario is that x lies in one of two algebraic progressions, which isn't so bad and would be relatively easy to check.
Let p = 7:
13.) 49k^2 + 32743 - y^2 = 0
14.) 49l^2 + 14l + 32743 + 1 - y^2 = 0
15.) 49m^2 + 28m + 32743 + 4 - y^2 = 0
16.) 49n^2 + 42n + 32743 + 9 - y^2 = 0
17.) 49o^2 + 56o + 32743 + 16 - y^2 = 0
18.) 49p^2 + 70p + 32743 + 25 - y^2 = 0
19.) 49q^2 + 84q + 32743 + 36 - y^2 = 0
13.) has no solutions
14.) has no solutions
15.) has solutions, does not correspond to our "trivial" answer
16.) has no solutions
17.) has no solutions
18.) has solutions, corresponds to our "trivial" answer
19.) has no solutions
Again, we have two possible solutions and we've again increased the number of arithmetic progressions we need to check. We have x == 1 mod 2, x == 0 mod 3, and:
i.) x == 1 mod 5, x == 2 mod 7
ii.) x == 1 mod 5, x == 5 mod 7
iii.) x == 4 mod 5, x == 2 mod 7
iv.) x == 4 mod 5, x == 5 mod 7
As you may have noticed, this potential multiplicity of progressions is another "obstruction", and another part of my current work is determining how best to deal with it. For now, a good test is to find the lcm of all your moduli and compare it with the integer square root of n. If the lcm is the first lcm greater than the integer square root of n, then you've gone "far enough". This is possible because y + x and y - x must both divide n; therefore y - x must be less than the square root of n since one divisor of n must always be less than the square root of n. In this case the integer square root of n is 180 and the lcm of (2,3,5,7) is 210, so p = 7 is a good place to stop. Let us, therefore, construct the arithmetic progression that corresponds to roman numeral i:
i.) x == 1 mod 2, x == 0 mod 3, x == 1 mod 5, x == 2 mod 7
For those who've had some exposure to number theory, the obvious answer (and what we'll do) is to apply the Chinese Remainder Theorem, which will produce an equation that spits out allowable x values:
The first congruence states that x == 1 mod 2, hence x = 2t + 1. Substituting this into the the second congruence, we get 2t + 1 == 0 mod 3, or 2t == -1 mod 3, which reduces to t = -1/2 mod 3. Using the "trial and error" method, we get t == 1 mod 3. This is equivalent to t = 3s + 1; plugging into x(t) gives x = 2(3s + 1) + 1, or x = 6s + 3. We use this new equation for x in the third congruence: 6s + 3 == 1 mod 5. This is equivalent to 6s == -2 mod 5, or s == -1/3 mod 5. Using the trial and error method again, we get s == 9/3 mod 5 or s == 3 mod 5. This means s = 5r + 3. Plugging this into x(s), we get x = 6(5r + 3) + 3, or x = 30r + 21. We now replace x in the final congruence: 30r + 21 == 2 mod 7. We "cast out" 7, giving 2r == -5 mod 7 or r == -5/2 mod 7. By trial-and-error this is equivalent to r == 1 mod 7, hence r = 7q + 1. Substitution into x(r), we have x = 30(7q + 1) + 21, or x = 210q + 51.
We can now test this congruence to see if it gives us an answer. Let q = 0, then we have x = 51 and:
x^2 + 32743 = y^2 => 51^2 + 32743 = y^2 => 35344 = y^2, 188 = y. With x = 51, y = 188 we then find gcd(188-51, 32743) = 137, gcd(188+51, 32743) = 239.
And, indeed, 32743 = 137 * 239.
This, in a nutshell, is how the general method of Hasse Interrogation may be applied to solve a quadratic diophantine equation. There are many "kinks" to work out; in this case we got lucky and found the right progression on our first try. Nevertheless, it seems to be a promising route to pursue in solving these kinds of equations and worth further study.
Consider an equation -- say x^2 + 51 = y^2. Since this is a simple quadratic, the "Hasse Principle" applies. That means that if you solve the equation mod various primes, and integer solutions exist, then the equation is generally solvable in the rationals (any number that can be expressed as a fraction). This is a nice technique because you can quickly determine if any solutions exist before trying to solve the equation through the normal means (which, in this case, involves factoring 51).
Now, the trick is to break down the equation you're trying to solve into specially-formulated "chunks" and see if they have solutions via an application of the Hasse Principle. If you construct the "chunks" properly, then you can draw various conclusion about what a solution to your would look like.
This is where figurate numbers come in handy -- we can take any quadratic of the form x^2 + n = y^2 and use the Hasse Principle to see if these equations have rational solutions:
4a^2 + n = y^2
9b^2 + n = y^2
25c^2 + n = y^2
49d^2 + n = y^2
You'll notice that the x-variable coefficient is always a square of a prime number. Squares are useful here because they correspond to possible digit groupings for x. Recall that a square number can be written as:
1+3+5+7...
So, imagine that we group digits, like this:
1+3 + 5+7 + 9+11 + 13+15
This would imply that the total length of the square representation of x is divisible by 2. Without going into the rather trivial math behind it, you can presume that if 4a^2 + n = y^2 is solvable, then we can immediately infer that x == 0 mod 2 in our original equation because the digits of the square representation of x will group into twos. The same applies to 9: if 9b^2 + n = y^2 passes the Hasse Principle test, then x == 0 mod 3 (or digits can group into threes).
The fun part (and the part I'm currently working on) is that we can get a useful answer for every prime, thus we can build a "profile" for the variable x (which can be used to determine the arithmetic progression where we may find a non-trivial solution). Again, we use specially-constructed equations and apply the Hasse Principle. For instance, we can determine if these equations have solutions:
9a^2 + n = y^2
9b^2 + 6b + n + 1 = y^2
9c^2 + 12c + n + 1 = y^2
These correspond to x == 0 mod 3, x == 1 mod 3, and x == 2 mod 3 respectively (again, showing this is the case is fairly trivial).
Generally speaking only one of those equations will have integer solutions for a particular value of n. I say generally because, in practice, there are various "obstructions" that you have to take into account. For instance, there is always the trivial answer which can interfere with finding usable solutions. In the case of x^2 + 51 = y^2, the trivial answer is:
25^2 + 51 = 26^2
Hence x could be 25, and therefore x == 0 mod 5 would be a true but not "useful" answer if we're trying to factor 51. Since these "obstructions" are easy to calculate, we can simply avoid testing against primes that factor the trivial case. There is another fly in the ointment, however, and one that appears to run a bit deeper. In many instances a _rational_ solution may exist but an _integer_ solution may not; indeed, with large values of n this appears to often be the case when considering x, such that x is not congruent to 0 mod p (where p is the prime currently under consideration).
As a play-along example, I'll use the handy online Quadratic Diophantine Equation Solver developed by Dario Alpern. Let n = 32743. First, we compute the "trivial" solution. Let x = (n-1)/2, then we have:
16371^2 + 32743 = 16372^2
We will test the value 16371 against each prime we consider to see which answers we should "throw out". We start with p = 2, which gives:
1.) 4a^2 + 32743 = y^2, and
1.) 4b^2 + 4b + 32743 + 1 = y^2
We'll "normalize" these equations by bringing y^2 to the other side so the whole thing equals zero; this gives
3.) 4a^2 + 32743 - y^2 = 0, and
4.) 4b^2 + 4b + 32743 + 1 - y^2 = 0
Plugging these in to Dario's calculator, we get:
3.) has no solutions, therefore x is not congruent to 0 mod 2, and
4.) has solutions, therefore x == 1 mod 2
To see what's happening, be sure to click the radio button for "Step-by-step", in which case equation 3 returns the output:
First of all we must determine the gcd of all coefficients but the constant term, that is: gcd(4, 0, -1, 0, 0) = 1.
Dividing the equation by the greatest common divisor we obtain:
4 x2 - y2 + 32743 = 0
We try to check the equation modulo the prime divisors of 4.
We try now to solve this equation module 9, 16 and 25.
No solutions found using mod 16, so there are no integer solutions.
and equation 4 gives:
Dividing the equation by the greatest common divisor we obtain:
4 x2 - y2 + 4 x + 32744 = 0
We try now to solve this equation module 9, 16 and 25.
There are solutions, so we must continue...
Note that we're not concerned with the actual answer here, just whether or not the equations have solutions mod 9, 16, and 25.
Now, remember our trivial answer? It was odd, therefore x == 1 mod 2 could apply to both a "good" x and our "trivial" x. In this case we don't need to discard this solution, since there were only two possibilities. We now move on to p = 3. Our normalized equations are:
5.) 9c^2 + 32743 - y^2 = 0
6.) 9d^2 + 6d + 32743 + 1 - y^2 = 0
7.) 9e^2 + 12e + 32743 + 4 - y^2 = 0
And Dario's calculator gives:
5.) Has solutions, coincides with our "trivial" solution ( 0 == 16371 % 3)
6.) No solutions
7.) No solutions
Since our "trivial" solution was the only possible solution, we can safely assume that a "good" value for x == 0 mod 3. Moving on, let p = 5:
8.) 25f^2 + 32743 - y^2 = 0
9.) 25g^2 + 10g + 32743 + 1 - y^2 = 0
10.) 25h^2 + 20h + 32743 + 4 - y^2 = 0
11.) 25i^2 + 30i + 32743 + 9 - y^2 = 0
12.) 25j^2 + 40j + 32743 + 16 - y^2 = 0
Our "trivial" solution corresponds to 1 mod 5, thus equation 9 is our "suspect" equation in this set:
8.) Has no solutions.
9.) Has solutions, but is "suspect"
10.) Has no solutions.
11.) Has no solutions.
12.) Has solutions, is not "suspect".
So far we have x == 1 mod 2 and x == 0 mod 3. We now have a special case; it's possible that equation 12 could have _rational_ solutions but not have _integer_ solutions (the Hasse Principle only guarantees rational solutions). Thus we cannot throw out equation 9's result that x == 1 mod 5; we now have two possible profiles for x (x == 1 mod 2, x == 0 mod 3, x == 1 mod 5 or x == 4 mod 5). This is the "rational" obstruction that I referred to earlier, and so we may want to throw out this answer completely to keep from "branching" within our possible solution set.
We'll continue, then, to build up the profile and see if we need this solution. So far our worst-case scenario is that x lies in one of two algebraic progressions, which isn't so bad and would be relatively easy to check.
Let p = 7:
13.) 49k^2 + 32743 - y^2 = 0
14.) 49l^2 + 14l + 32743 + 1 - y^2 = 0
15.) 49m^2 + 28m + 32743 + 4 - y^2 = 0
16.) 49n^2 + 42n + 32743 + 9 - y^2 = 0
17.) 49o^2 + 56o + 32743 + 16 - y^2 = 0
18.) 49p^2 + 70p + 32743 + 25 - y^2 = 0
19.) 49q^2 + 84q + 32743 + 36 - y^2 = 0
13.) has no solutions
14.) has no solutions
15.) has solutions, does not correspond to our "trivial" answer
16.) has no solutions
17.) has no solutions
18.) has solutions, corresponds to our "trivial" answer
19.) has no solutions
Again, we have two possible solutions and we've again increased the number of arithmetic progressions we need to check. We have x == 1 mod 2, x == 0 mod 3, and:
i.) x == 1 mod 5, x == 2 mod 7
ii.) x == 1 mod 5, x == 5 mod 7
iii.) x == 4 mod 5, x == 2 mod 7
iv.) x == 4 mod 5, x == 5 mod 7
As you may have noticed, this potential multiplicity of progressions is another "obstruction", and another part of my current work is determining how best to deal with it. For now, a good test is to find the lcm of all your moduli and compare it with the integer square root of n. If the lcm is the first lcm greater than the integer square root of n, then you've gone "far enough". This is possible because y + x and y - x must both divide n; therefore y - x must be less than the square root of n since one divisor of n must always be less than the square root of n. In this case the integer square root of n is 180 and the lcm of (2,3,5,7) is 210, so p = 7 is a good place to stop. Let us, therefore, construct the arithmetic progression that corresponds to roman numeral i:
i.) x == 1 mod 2, x == 0 mod 3, x == 1 mod 5, x == 2 mod 7
For those who've had some exposure to number theory, the obvious answer (and what we'll do) is to apply the Chinese Remainder Theorem, which will produce an equation that spits out allowable x values:
The first congruence states that x == 1 mod 2, hence x = 2t + 1. Substituting this into the the second congruence, we get 2t + 1 == 0 mod 3, or 2t == -1 mod 3, which reduces to t = -1/2 mod 3. Using the "trial and error" method, we get t == 1 mod 3. This is equivalent to t = 3s + 1; plugging into x(t) gives x = 2(3s + 1) + 1, or x = 6s + 3. We use this new equation for x in the third congruence: 6s + 3 == 1 mod 5. This is equivalent to 6s == -2 mod 5, or s == -1/3 mod 5. Using the trial and error method again, we get s == 9/3 mod 5 or s == 3 mod 5. This means s = 5r + 3. Plugging this into x(s), we get x = 6(5r + 3) + 3, or x = 30r + 21. We now replace x in the final congruence: 30r + 21 == 2 mod 7. We "cast out" 7, giving 2r == -5 mod 7 or r == -5/2 mod 7. By trial-and-error this is equivalent to r == 1 mod 7, hence r = 7q + 1. Substitution into x(r), we have x = 30(7q + 1) + 21, or x = 210q + 51.
We can now test this congruence to see if it gives us an answer. Let q = 0, then we have x = 51 and:
x^2 + 32743 = y^2 => 51^2 + 32743 = y^2 => 35344 = y^2, 188 = y. With x = 51, y = 188 we then find gcd(188-51, 32743) = 137, gcd(188+51, 32743) = 239.
And, indeed, 32743 = 137 * 239.
This, in a nutshell, is how the general method of Hasse Interrogation may be applied to solve a quadratic diophantine equation. There are many "kinks" to work out; in this case we got lucky and found the right progression on our first try. Nevertheless, it seems to be a promising route to pursue in solving these kinds of equations and worth further study.
