Friday, February 12, 2010
More on "Hasse Interrogation"
I realized that I'd sort of buried the lede in my post below about what I called "Hasse Interrogation". The idea is pretty elementary and I'm kind of surprised it hasn't popped up in the usual places (I've been searching the literature, web, asking around, etc for a few months now). Here are the basics:
1.) Certain families of Diophantine equations adhere to the Hasse Principle (a.k.a the local-global principle). Namely, if an equation has solutions in a.) the real numbers, and b.) every p-adic field, then it also has rational solutions. There are some equations that are known to be "violators" -- they're solvable "locally" (i.e., over some p-addic field) but don't have a rational solution.
2.) Hasse Interrogation is, essentially, like asking a bunch of "what if" questions and stitching together the answers to get a better sense of what a solution might look like. Consider this equation:
x^2 + 35 = y^2
We know a few things about x and y, but those things aren't particularly useful for finding all of the solutions to the equation. For instance, since 35 is odd there will be a "trivial" solution, with x = (35 - 1) / 2 = 17 and y = 18: 17^2 + 35 = 18^2. But there is at least one other solution. So we ask questions, like this:
what if x was divisible by 2 --> then we replace x with 2a
what if x wasn't divisible by 2 --> then we replace x with 2b + 1
You can keep going, too:
what if x was divisible by 3? Then we could replace x with 3c.
what if x was divisible by 3 with a remainder of 1? Then x = 3d + 1.
what if x was divisible by 3 with a remainder of 2? Then x = 3d + 2.
And so on.
3.) We can apply the Hasse Principle to see if our "question" have "answers". Namely:
If x is divisible by 2, then x = 2a, so x^2 -> 4a^2 and our equation becomes:
4a^2 + 35 = y^2
Now, we don't have to actually solve that equation. Instead, we can simply apply the Hasse Principle to see if it has any rational solutions. If it does, then x could be of the form 2a. If not, and replacing x with 2a + 1 is soluble, then we know that x must be of the form 2a + 1. That means x == 1 mod 2.
4.) If we compile enough of these congruences, then we can establish a "profile" for x. For instance:
x = 2a has no rational solutions
x = 2b + 1 does, so x == 1 mod 2
x = 3c has no rational solutions
x = 3d + 1 has no rational solutions
x = 3e + 2 does, so x == 2 mod 3
These are nice because we can combine them via the Chinese Remainder Theorem to figure out what x might "look like". This method essentially builds a sieve as each congruence hones the "profile" we have of x.
5.) There are issues; for instance, a particular equation might have a whole bunch of rational solutions but what we really want are integer solutions. Those rational solutions can interfere with finding an integer solution, so one needs to devise a way to weed them out if possible. For instance, say you know that x == 1 mod 2, x == 2 mod 3, but you find that x == 1 mod 5 and x == 4 mod 5. We then would have to test the case of (x == 1 mod 2, x == 2 mod 3, x == 1 mod 5) and (x == 1 mod 2, x == 2 mod 3, x == 4 mod 5).
One way to approach this is, perhaps, to rephrase the question. For instance, x^2 + 35 = y^2 can also be written as m^2 + 16m + 13 = n^2 (the transformation is somewhat trivial but not necessarily obvious). One could apply Hasse Interrogation to this equation (which is, essentially, the same equation approached in a different way) and then figure out the mapping from values of m and n to values of x and y. I haven't tried this specific approach yet, it may or may not work. But it's an example of a larger set of possible solution methods for these situations.
Anyways, that's the gist of how it works. Any equation that satisfies the Hasse Principle could be subjected to this method of seeking specific solutions. For instance:
x^2 + y^2 + z^2 = q^2 + 23
or
a^2 + b - c^2 = d^2 + e
And so on.
1.) Certain families of Diophantine equations adhere to the Hasse Principle (a.k.a the local-global principle). Namely, if an equation has solutions in a.) the real numbers, and b.) every p-adic field, then it also has rational solutions. There are some equations that are known to be "violators" -- they're solvable "locally" (i.e., over some p-addic field) but don't have a rational solution.
2.) Hasse Interrogation is, essentially, like asking a bunch of "what if" questions and stitching together the answers to get a better sense of what a solution might look like. Consider this equation:
x^2 + 35 = y^2
We know a few things about x and y, but those things aren't particularly useful for finding all of the solutions to the equation. For instance, since 35 is odd there will be a "trivial" solution, with x = (35 - 1) / 2 = 17 and y = 18: 17^2 + 35 = 18^2. But there is at least one other solution. So we ask questions, like this:
what if x was divisible by 2 --> then we replace x with 2a
what if x wasn't divisible by 2 --> then we replace x with 2b + 1
You can keep going, too:
what if x was divisible by 3? Then we could replace x with 3c.
what if x was divisible by 3 with a remainder of 1? Then x = 3d + 1.
what if x was divisible by 3 with a remainder of 2? Then x = 3d + 2.
And so on.
3.) We can apply the Hasse Principle to see if our "question" have "answers". Namely:
If x is divisible by 2, then x = 2a, so x^2 -> 4a^2 and our equation becomes:
4a^2 + 35 = y^2
Now, we don't have to actually solve that equation. Instead, we can simply apply the Hasse Principle to see if it has any rational solutions. If it does, then x could be of the form 2a. If not, and replacing x with 2a + 1 is soluble, then we know that x must be of the form 2a + 1. That means x == 1 mod 2.
4.) If we compile enough of these congruences, then we can establish a "profile" for x. For instance:
x = 2a has no rational solutions
x = 2b + 1 does, so x == 1 mod 2
x = 3c has no rational solutions
x = 3d + 1 has no rational solutions
x = 3e + 2 does, so x == 2 mod 3
These are nice because we can combine them via the Chinese Remainder Theorem to figure out what x might "look like". This method essentially builds a sieve as each congruence hones the "profile" we have of x.
5.) There are issues; for instance, a particular equation might have a whole bunch of rational solutions but what we really want are integer solutions. Those rational solutions can interfere with finding an integer solution, so one needs to devise a way to weed them out if possible. For instance, say you know that x == 1 mod 2, x == 2 mod 3, but you find that x == 1 mod 5 and x == 4 mod 5. We then would have to test the case of (x == 1 mod 2, x == 2 mod 3, x == 1 mod 5) and (x == 1 mod 2, x == 2 mod 3, x == 4 mod 5).
One way to approach this is, perhaps, to rephrase the question. For instance, x^2 + 35 = y^2 can also be written as m^2 + 16m + 13 = n^2 (the transformation is somewhat trivial but not necessarily obvious). One could apply Hasse Interrogation to this equation (which is, essentially, the same equation approached in a different way) and then figure out the mapping from values of m and n to values of x and y. I haven't tried this specific approach yet, it may or may not work. But it's an example of a larger set of possible solution methods for these situations.
Anyways, that's the gist of how it works. Any equation that satisfies the Hasse Principle could be subjected to this method of seeking specific solutions. For instance:
x^2 + y^2 + z^2 = q^2 + 23
or
a^2 + b - c^2 = d^2 + e
And so on.
