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.
Friday, January 08, 2010
Thoughts on Goldbach Conjecture
...Yeah, and who doesn't have thoughts on the Goldbach Conjecture? It's attracted the gaze of this amateur, and so I'll try to wade into the waters slowly.
There's an interesting sequence in the OEIS -- A144650. I like it because, when you view it as a triangular array, it makes a nice pattern (click on the link, then click on "tabl" in the "Keyword" section). So what about it? These are the indices of the odd composites, taken from the set of all odd numbers. So, if you list them out:
1, 3, 5, 7, 9, 11, 13, 15, 19, 21, 23, 25 ...
And pick the values at indices indicated by sequence A144650, you'll get all of the odd composites:
5 = 9
8 = 15
13 = 25
11 = 21
18 = 35
and so on.
This sequence is ordered in a particular way, though, and it's the ordering that's interesting (at least to me). The value at index 5 is 3^2. The value at index 8 is 3*5. The value at index 13 is 5*5. The value at index 11 is 3*7. The value at index 18 is 5*7. Shown visually, you can see that we're reading the columns out of a product table:
O.k., you might ask, so what's the big deal? The fun part of this is it suggests to us a way to convert the Goldbach Conjecture in to a Goldbach Property -- in other words, we can devise a testable statement that determines whether or not any set of positive integers S can be used to construct a sum table that contains all of the even positive integers.
Let's go back to our set of odd numbers. I'm going to give the set a name, A:
A = {x: x>0, x == 1 mod 2}
Which is a fancy way of saying the set A contains all integers (greater than zero) such that x == 1 mod 2, or x is an odd positive integer.
We can construct a number of functions which generate the individual terms of A, but I happen to like this one:
ax - a + 1 = n, a = 2, n is included in A
Or, simplified (after replacing "a" with "2"): 2x - 1 = n
-----------
Now for our first trick. Let's define a set B to be all the even integers:
B = {z: z>0, z == 0 mod 2}
And a function to generate its members:
az - a + 2 = p, a = 2, p is included in B
It is pretty easy to show that the sum of two values from set A will be included in set B:
ax - a + 1 + ay - a + 1 = p, p is included in B
Simplify:
ax + ay - 2a + 2 = p.
Let a = 2:
2x + 2y - 4 + 2 = p
2x + 2y - 2 = p
And it follows from inspection that this will always produce a value p such that p == 0 mod 2.
So, we can restate the equation for generating set B from values of set A as:
ax - a + 1 + ay - a + 1 = az - a + 2
Let's simplify; first gather all the variables and constants:
ax + ay - 2a + 2 = az - a + 2
Subtract 2 from both sides:
ax + ay - 2a = az - a
We can now divide through by a, removing it entirely from the equation:
x + y - 2 = z - 1
x + y - 1 = z
Interesting... What does this tell us? Remember we defined the equation that generated all values of A as:
ax - a + 1 = n, a = 2
But now the value of a doesn't matter... That means we could use any value we wanted for a and end up with the same result. For instance, let's set a = 5. Plugging into the equation above we get:
5x - 4 = n
This, in turn, will generate a new set of integers that I'll call C:
C = {1, 6, 11, 16, 21, 26, ...}
Remember, though, that we also defined a set B, which in the case of a = 2 was the even integers. Well, we can now generate a new set, which I'll call D, using the same equation for generating B but setting a = 5:
5x - 3 = r
D = {2, 7, 12, 17, 22, 27, 32, 37, ...}
Here's the fun part -- sets C and D are related to each other in the same ways as A and B. First:
let x, y be included in A, then:
x + y = z, z included in B
x * y = w, w included in A
What this means is that if I add together two elements of A, then I'll get an element of B. If I multiply two elements of A, then I'll get another element of A.
The additive relationship is the basis for the Goldbach Conjecture, and the multiplicative rule is the basis for determining primality.
Primality:
Since x * y, where x and y are included in A, is also included in A, it allows us to define the concept of "relatively prime". Meaning, in other words, that if a value of A cannot be stated in the form x * y, with x and y both included in A, then that number is relatively prime with respect to A. Remember, A is the set of all odd numbers. So, it follows that all odd numbers that are prime have no divisors in set A, and we can check this exhaustively by dividing any member n of A by all the values of A less than the square root of n.
Goldbach:
Now that we have a way to define primes in the set A, we can restate the Goldbach Conjecture as a statement about set relationships. Let:
A = {n: n == 1 mod 2}
B = (q: q == 0 mod 2}
Take x,y such that x and y are included in A and are relatively prime to A. Then all the members q of set B can be expressed as the sum x + y = q.
Now that we've defined what "relatively prime means, we now have a way to define the Goldbach Property in terms of relative primality:
let X be the set expressed by the equation ax - a + 1 = p
let Y be the set expressed by the equation ay - a + 2 = q
Then, the Goldbach Property is:
The property that, if a_i and b_j are included in X and are relatively prime to all members of X, then any member q of Y can be expressed as a_i + b_j = q, for not necessarily distinct values of i and j.
----------
What does this mean in practice? Well, I'm not entirely sure. For one thing, by picking different values of a we can generate an infinite number of sequences that look and behave like A144650:
a = 2, sequence = 5, 8, 13, 11, 18, 25 ...
a = 3, sequence = 6, 10, 17, 14, 23, 32 ...
a = 4, sequence = 7, 12, 21, 17, 28, 39 ...
And so on (and in both directions, i.e. a = 1, 0, -1, -2 -- more on that later). What does that mean, then? Note that these are the indices of all the "composites" within each sequence. By exclusion, we can be sure then that any value at an index not in these sequences is "prime". As the sequences get bigger, so do the number of primes in a sequence.
Which is all a really long way of getting to the point -- at what value of a can we prove the Goldbach Property for the sequence generated by a? The distribution of relative primes is changing, as we go from sequence to sequence, in a very regular sort of way, thus I presume that all the machinery arrayed against the classic Goldbach Conjecture will also fail to prove whether or not any sequence generated by any value of a fulfills the Goldbach Property as I've defined it here. I don't know if that's entirely true; most of the efforts at proving Goldbach have involved demonstrating that some statistical function produces values within a certain range of bounds, which then translates into statements like "every even integer is the sum of, at most, 20 primes".
So, perhaps, we have a new way to attack the problem. Go waaay back near the top and notice that the value for a ultimately doesn't matter:
x + y - 1 = z
This is ultimate a statement about the indices -- if you take the indices x and y from A, add them, then subtract 1, you'll get the value at index z from set B. Let's test this:
x = 2, y = 3:
2 + 3 - 1 = 4
Which means:
3 + 5 = 8
and, indeed, by inspection we can see that from set A:
{1, 3, 5, 7, 9 ...} the values at indices 2 and 3, when added together, equal the value at index 4 in set B:
{2, 4, 6, 8}
Applying this to the Goldbach Conjecture, then, we're really concerned about whether or not the set of prime indices "codes" for all the integers. In other words, let:
P = {2, 3, 4, 6, 7, 9 ...}
P1 = P_i - 1 = {1, 2, 3, 5, 6, 8...}
Let x_i be included in P and y_j be included in P1. Then we want to show that:
x_i + y_j = z, for all z included in Z, where Z = {n: n > 2, n is an integer}
As we range over all possible values for i and j.
Anyways, some food for thought...
There's an interesting sequence in the OEIS -- A144650. I like it because, when you view it as a triangular array, it makes a nice pattern (click on the link, then click on "tabl" in the "Keyword" section). So what about it? These are the indices of the odd composites, taken from the set of all odd numbers. So, if you list them out:
1, 3, 5, 7, 9, 11, 13, 15, 19, 21, 23, 25 ...
And pick the values at indices indicated by sequence A144650, you'll get all of the odd composites:
5 = 9
8 = 15
13 = 25
11 = 21
18 = 35
and so on.
This sequence is ordered in a particular way, though, and it's the ordering that's interesting (at least to me). The value at index 5 is 3^2. The value at index 8 is 3*5. The value at index 13 is 5*5. The value at index 11 is 3*7. The value at index 18 is 5*7. Shown visually, you can see that we're reading the columns out of a product table:
| 3 | 5 | 7 | 9 | |
| 3 | 9 | 15 | 21 | 27 |
| 5 | 25 | 35 | 45 | |
| 7 | 49 | 63 | ||
| 9 | 81 |
O.k., you might ask, so what's the big deal? The fun part of this is it suggests to us a way to convert the Goldbach Conjecture in to a Goldbach Property -- in other words, we can devise a testable statement that determines whether or not any set of positive integers S can be used to construct a sum table that contains all of the even positive integers.
Let's go back to our set of odd numbers. I'm going to give the set a name, A:
A = {x: x>0, x == 1 mod 2}
Which is a fancy way of saying the set A contains all integers (greater than zero) such that x == 1 mod 2, or x is an odd positive integer.
We can construct a number of functions which generate the individual terms of A, but I happen to like this one:
ax - a + 1 = n, a = 2, n is included in A
Or, simplified (after replacing "a" with "2"): 2x - 1 = n
-----------
Now for our first trick. Let's define a set B to be all the even integers:
B = {z: z>0, z == 0 mod 2}
And a function to generate its members:
az - a + 2 = p, a = 2, p is included in B
It is pretty easy to show that the sum of two values from set A will be included in set B:
ax - a + 1 + ay - a + 1 = p, p is included in B
Simplify:
ax + ay - 2a + 2 = p.
Let a = 2:
2x + 2y - 4 + 2 = p
2x + 2y - 2 = p
And it follows from inspection that this will always produce a value p such that p == 0 mod 2.
So, we can restate the equation for generating set B from values of set A as:
ax - a + 1 + ay - a + 1 = az - a + 2
Let's simplify; first gather all the variables and constants:
ax + ay - 2a + 2 = az - a + 2
Subtract 2 from both sides:
ax + ay - 2a = az - a
We can now divide through by a, removing it entirely from the equation:
x + y - 2 = z - 1
x + y - 1 = z
Interesting... What does this tell us? Remember we defined the equation that generated all values of A as:
ax - a + 1 = n, a = 2
But now the value of a doesn't matter... That means we could use any value we wanted for a and end up with the same result. For instance, let's set a = 5. Plugging into the equation above we get:
5x - 4 = n
This, in turn, will generate a new set of integers that I'll call C:
C = {1, 6, 11, 16, 21, 26, ...}
Remember, though, that we also defined a set B, which in the case of a = 2 was the even integers. Well, we can now generate a new set, which I'll call D, using the same equation for generating B but setting a = 5:
5x - 3 = r
D = {2, 7, 12, 17, 22, 27, 32, 37, ...}
Here's the fun part -- sets C and D are related to each other in the same ways as A and B. First:
let x, y be included in A, then:
x + y = z, z included in B
x * y = w, w included in A
What this means is that if I add together two elements of A, then I'll get an element of B. If I multiply two elements of A, then I'll get another element of A.
The additive relationship is the basis for the Goldbach Conjecture, and the multiplicative rule is the basis for determining primality.
Primality:
Since x * y, where x and y are included in A, is also included in A, it allows us to define the concept of "relatively prime". Meaning, in other words, that if a value of A cannot be stated in the form x * y, with x and y both included in A, then that number is relatively prime with respect to A. Remember, A is the set of all odd numbers. So, it follows that all odd numbers that are prime have no divisors in set A, and we can check this exhaustively by dividing any member n of A by all the values of A less than the square root of n.
Goldbach:
Now that we have a way to define primes in the set A, we can restate the Goldbach Conjecture as a statement about set relationships. Let:
A = {n: n == 1 mod 2}
B = (q: q == 0 mod 2}
Take x,y such that x and y are included in A and are relatively prime to A. Then all the members q of set B can be expressed as the sum x + y = q.
Now that we've defined what "relatively prime means, we now have a way to define the Goldbach Property in terms of relative primality:
let X be the set expressed by the equation ax - a + 1 = p
let Y be the set expressed by the equation ay - a + 2 = q
Then, the Goldbach Property is:
The property that, if a_i and b_j are included in X and are relatively prime to all members of X, then any member q of Y can be expressed as a_i + b_j = q, for not necessarily distinct values of i and j.
----------
What does this mean in practice? Well, I'm not entirely sure. For one thing, by picking different values of a we can generate an infinite number of sequences that look and behave like A144650:
a = 2, sequence = 5, 8, 13, 11, 18, 25 ...
a = 3, sequence = 6, 10, 17, 14, 23, 32 ...
a = 4, sequence = 7, 12, 21, 17, 28, 39 ...
And so on (and in both directions, i.e. a = 1, 0, -1, -2 -- more on that later). What does that mean, then? Note that these are the indices of all the "composites" within each sequence. By exclusion, we can be sure then that any value at an index not in these sequences is "prime". As the sequences get bigger, so do the number of primes in a sequence.
Which is all a really long way of getting to the point -- at what value of a can we prove the Goldbach Property for the sequence generated by a? The distribution of relative primes is changing, as we go from sequence to sequence, in a very regular sort of way, thus I presume that all the machinery arrayed against the classic Goldbach Conjecture will also fail to prove whether or not any sequence generated by any value of a fulfills the Goldbach Property as I've defined it here. I don't know if that's entirely true; most of the efforts at proving Goldbach have involved demonstrating that some statistical function produces values within a certain range of bounds, which then translates into statements like "every even integer is the sum of, at most, 20 primes".
So, perhaps, we have a new way to attack the problem. Go waaay back near the top and notice that the value for a ultimately doesn't matter:
x + y - 1 = z
This is ultimate a statement about the indices -- if you take the indices x and y from A, add them, then subtract 1, you'll get the value at index z from set B. Let's test this:
x = 2, y = 3:
2 + 3 - 1 = 4
Which means:
3 + 5 = 8
and, indeed, by inspection we can see that from set A:
{1, 3, 5, 7, 9 ...} the values at indices 2 and 3, when added together, equal the value at index 4 in set B:
{2, 4, 6, 8}
Applying this to the Goldbach Conjecture, then, we're really concerned about whether or not the set of prime indices "codes" for all the integers. In other words, let:
P = {2, 3, 4, 6, 7, 9 ...}
P1 = P_i - 1 = {1, 2, 3, 5, 6, 8...}
Let x_i be included in P and y_j be included in P1. Then we want to show that:
x_i + y_j = z, for all z included in Z, where Z = {n: n > 2, n is an integer}
As we range over all possible values for i and j.
Anyways, some food for thought...
Tuesday, November 24, 2009
Hasse and Hensel
A note about the rational "obstructions" to Hasse Interrogation -- I think that Hensel lifting might provide a way to determine if a particular equation that passes the Hasse Principle test has rational or integer solutions, but I'm still not quite comfortable enough with it to know for sure. If so, then we could "test" potential rational solutions by applying Hensel lifting to see if the answer remains rational when "lifted". Anyways, lots to study so it's back to the books for now.
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.
Monday, January 26, 2009
Figurate Numbers and factoring, pt. 2
Since my last post I've been playing a bit more specifically with square and triangle figurate numbers. And, there is an interesting modification you can do to turn an equation like this:
i.) c^2 == d^2 mod (n)
into this:
ii.) x^2 + ax == y^2 mod (b)
For example, let n = 51. We want to find:
iii.) c^2 == d^2 mod 51
So that we can factor 51. This can be modified so that we solve:
iv.) x^2 + 16x == y^2 mod 13
instead of the original congruence. Why would we want to do this? That is still, for me, an open question. In the book "Number Theory" by George E. Andrews there's a similar problem posed in section 9-4 (pg 127 in the Dover paperback edition):
"4. Does x^2 + 5x == 12 (mod 31) have a solution?"
The answer, in my view, hinges on several key issues. First, does knowing the factors of 16 and 13 make equation iv easier to solve or, more specifically, quicker to compute? Second, do all of the values of x and y which satisfy the congruence give us "useful" numbers for factoring n?
If the answer to the first two questions is yes, then we wind up with an interesting recursion -- let us assume for a moment that a and b (16 and 13 in equation iv, respectively) were very large numbers that were difficult to factor. If equation ii really is faster than i to solve, then it could be used to find the factors of a and b, which could in turn be used to factor n. Thus one could continue downward, if necessary, to factor large numbers by factoring smaller numbers first.
When I have a better grasp of what's going on, perhaps I can approach that recursion issue and see if it leads to a contradiction via infinite descent.
i.) c^2 == d^2 mod (n)
into this:
ii.) x^2 + ax == y^2 mod (b)
For example, let n = 51. We want to find:
iii.) c^2 == d^2 mod 51
So that we can factor 51. This can be modified so that we solve:
iv.) x^2 + 16x == y^2 mod 13
instead of the original congruence. Why would we want to do this? That is still, for me, an open question. In the book "Number Theory" by George E. Andrews there's a similar problem posed in section 9-4 (pg 127 in the Dover paperback edition):
"4. Does x^2 + 5x == 12 (mod 31) have a solution?"
The answer, in my view, hinges on several key issues. First, does knowing the factors of 16 and 13 make equation iv easier to solve or, more specifically, quicker to compute? Second, do all of the values of x and y which satisfy the congruence give us "useful" numbers for factoring n?
If the answer to the first two questions is yes, then we wind up with an interesting recursion -- let us assume for a moment that a and b (16 and 13 in equation iv, respectively) were very large numbers that were difficult to factor. If equation ii really is faster than i to solve, then it could be used to find the factors of a and b, which could in turn be used to factor n. Thus one could continue downward, if necessary, to factor large numbers by factoring smaller numbers first.
When I have a better grasp of what's going on, perhaps I can approach that recursion issue and see if it leads to a contradiction via infinite descent.
Tuesday, December 09, 2008
Figurate numbers and factoring, a gentle intro
O.k., back to factoring. Chances are you're familiar with at least one set of figurate numbers -- the squares:
1, 4, 9, 16, 25, 36, 49, etc...
The sequence of squares can be generated very easily through addition; simply add up x number of odd numbers (starting with 1) to find x^2:
1^2 = 1
2^2 = 1 + 3
3^2 = 1 + 3 + 5
4^2 = 1 + 3 + 5 + 7
etc...
There are many other "kinds" of figurate numbers, but they all have the same simple rule for generating them. Here are a couple of examples:
triangle numbers:
-----------------
1 = 1
3 = 1 + 2
6 = 1 + 2 + 3
10 = 1 + 2 + 3 + 4
etc... (see http://www.research.att.com/~njas/sequences/A000290)
square numbers:
---------------
1 = 1
4 = 1 + 3
9 = 1 + 3 + 5
16 = 1 + 3 + 5 + 7
etc... (see http://www.research.att.com/~njas/sequences/A000290)
pentagonal numbers:
-------------------
1 = 1
5 = 1 + 4
12 = 1 + 4 + 7
22 = 1 + 4 + 7 + 10
etc... (see http://www.research.att.com/~njas/sequences/A000326)
And so on. Essentially, if you successively add any sequences of constant-spaced integers starting at 1, you'll get some sort of figurate number.
Why are figurate numbers important? First off, most modern factoring methods rely on a simple observation by Fermat, namely that if you can solve:
x^2 - y^2 = N
Where N is some number you want to factor, then you can find the factors of N directly using x and y, since x^2 - y^2 factors into (x+y)(x-y). This has been modified slightly for current factoring methods to read:
x^2 = y^2 mod N
Which means "x^2 is congruent to y^2 modulo N". One way to think of it is if you divide x^2 and y^2 by N then you get the same remainder:
16 = 25 mod 9 --> 16/9 = 1 remainder 7, 25/9 = 2 remainder 7.
Then plug in:
(4+5) = 9; (5-4) = 1
In this case we discovered a "trivial" solution; all integers have them. Here's an example of a non-trivial case:
64 = 4 mod 15 --> 4/15 = remainder 4, 64/15 4 remainder 4.
Plugging in we get:
(8 - 2) = 6; (8 + 2) = 10;
Ack, you may be thinking, neither of those numbers divide 15! This is true, but they each share at least one divisor with 15. So we compute the Greatest Common Divisor (gcd):
gcd(15,6) = 3; gcd(10,15) = 5
I won't go into it here but computing the gcd is very easy (it's based on the Chinese Remainder Theorem).
What about all of those other figurate numbers? Let's examine for a moment what x^2 - y^2 = N represents in terms of the "figurate representations" of x, y, and N. For instance, let x = 8, y = 2, and N = 60:
1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 = 64
1 + 3 = 4
-
----------------------------------------
5 + 7 + 9 + 11 + 13 + 15 = 60
Notice that the figurate representation of 60 consists of 6 integers. That number 6 isn't a coincidence -- the length of any figurate representation that's greater than 2 will be a number that shares a divisor with N. In other words 6 and 60 share a divisor (in this case 6 divides 60). So do 8 and 64. Some other examples:
5+7+9+11 = 32, 32 shares a divisor with 4
4+5+6+7 = 22, 22 shares a divisor with 4
4+7+10+13+16+19+22 = 91, 91 shares a divisor with 7
Hence if we can find any figurate representation of N with length greater than 2, we can factor N. That is, essentially, what x^2 - y^2 = N means; you're finding a "difference of squares" that represents a valid representation of N with a length greater than 2. So we can then replace any other figurate number into Fermat's equation and it still holds true. Let F_a(n) represent the nth figurate number of "order" a; F_1(n) is the nth triangle number, F_2(n) is the nth square number, and so on. Then Fermat's equation can be rewritten as:
F_a(x) - F_a(y) = N
And, (I believe, I have yet to write out the proof although it should be fairly trivial) the modern modification of Fermat's equation should also hold for all F_a(n):
F_a(x) = F_a(y) mod N
The inclusion of other figurate numbers in these two equations is the basis for my various attempts at cracking the factoring problem.
1, 4, 9, 16, 25, 36, 49, etc...
The sequence of squares can be generated very easily through addition; simply add up x number of odd numbers (starting with 1) to find x^2:
1^2 = 1
2^2 = 1 + 3
3^2 = 1 + 3 + 5
4^2 = 1 + 3 + 5 + 7
etc...
There are many other "kinds" of figurate numbers, but they all have the same simple rule for generating them. Here are a couple of examples:
triangle numbers:
-----------------
1 = 1
3 = 1 + 2
6 = 1 + 2 + 3
10 = 1 + 2 + 3 + 4
etc... (see http://www.research.att.com/~njas/sequences/A000290)
square numbers:
---------------
1 = 1
4 = 1 + 3
9 = 1 + 3 + 5
16 = 1 + 3 + 5 + 7
etc... (see http://www.research.att.com/~njas/sequences/A000290)
pentagonal numbers:
-------------------
1 = 1
5 = 1 + 4
12 = 1 + 4 + 7
22 = 1 + 4 + 7 + 10
etc... (see http://www.research.att.com/~njas/sequences/A000326)
And so on. Essentially, if you successively add any sequences of constant-spaced integers starting at 1, you'll get some sort of figurate number.
Why are figurate numbers important? First off, most modern factoring methods rely on a simple observation by Fermat, namely that if you can solve:
x^2 - y^2 = N
Where N is some number you want to factor, then you can find the factors of N directly using x and y, since x^2 - y^2 factors into (x+y)(x-y). This has been modified slightly for current factoring methods to read:
x^2 = y^2 mod N
Which means "x^2 is congruent to y^2 modulo N". One way to think of it is if you divide x^2 and y^2 by N then you get the same remainder:
16 = 25 mod 9 --> 16/9 = 1 remainder 7, 25/9 = 2 remainder 7.
Then plug in:
(4+5) = 9; (5-4) = 1
In this case we discovered a "trivial" solution; all integers have them. Here's an example of a non-trivial case:
64 = 4 mod 15 --> 4/15 = remainder 4, 64/15 4 remainder 4.
Plugging in we get:
(8 - 2) = 6; (8 + 2) = 10;
Ack, you may be thinking, neither of those numbers divide 15! This is true, but they each share at least one divisor with 15. So we compute the Greatest Common Divisor (gcd):
gcd(15,6) = 3; gcd(10,15) = 5
I won't go into it here but computing the gcd is very easy (it's based on the Chinese Remainder Theorem).
What about all of those other figurate numbers? Let's examine for a moment what x^2 - y^2 = N represents in terms of the "figurate representations" of x, y, and N. For instance, let x = 8, y = 2, and N = 60:
1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 = 64
1 + 3 = 4
-
----------------------------------------
5 + 7 + 9 + 11 + 13 + 15 = 60
Notice that the figurate representation of 60 consists of 6 integers. That number 6 isn't a coincidence -- the length of any figurate representation that's greater than 2 will be a number that shares a divisor with N. In other words 6 and 60 share a divisor (in this case 6 divides 60). So do 8 and 64. Some other examples:
5+7+9+11 = 32, 32 shares a divisor with 4
4+5+6+7 = 22, 22 shares a divisor with 4
4+7+10+13+16+19+22 = 91, 91 shares a divisor with 7
Hence if we can find any figurate representation of N with length greater than 2, we can factor N. That is, essentially, what x^2 - y^2 = N means; you're finding a "difference of squares" that represents a valid representation of N with a length greater than 2. So we can then replace any other figurate number into Fermat's equation and it still holds true. Let F_a(n) represent the nth figurate number of "order" a; F_1(n) is the nth triangle number, F_2(n) is the nth square number, and so on. Then Fermat's equation can be rewritten as:
F_a(x) - F_a(y) = N
And, (I believe, I have yet to write out the proof although it should be fairly trivial) the modern modification of Fermat's equation should also hold for all F_a(n):
F_a(x) = F_a(y) mod N
The inclusion of other figurate numbers in these two equations is the basis for my various attempts at cracking the factoring problem.
Tuesday, February 22, 2005
MOD and XOR
...I've been looking into multi-valued logic. If you implement an adder in any _n_ valued logic, you can see distinct differences between the equivalent XOR and AND operations that make up the truth tables in these logics. For instance:
XOR b_2_
---------
0 1
0 0 1
1 1 0
AND b_2_
---------
0 1
0 0 0
1 0 1
Now, let's examine b_3_:
XOR b_3_
---------
0 1 2
0 0 1 2
1 1 2 0
2 2 0 1
AND b_3_
---------
0 1 2
0 0 0 0
1 0 0 1
2 0 1 1
If we generalize this across all _n_ valued logics, we can see that to mathematically implement these truth tables is relatively easy. For some number A and some number B converted to base _n_ (so A in base _n_ will be some set of values {a1, a2, etc.}, as will b), we can find XOR and AND using the following equations:
a(x) XOR b(x) = a(x) + b(x) MOD _n_
a(x) AND b(x) = floor((a(x) + b(x)) / n)
where a(x) and b(x) are members from {a1, a2 .. a(x)) and {b1, b2 .. b(x)} (as defined above) with the same index value x. For example, in base 2 the XOR of a(x) = 1 and b(x) = 1 is:
a(x) + b(x) = 1 + 1 = 2, and
0 = 2 MOD 2 (note: I'm not following the convention where the number immediately following the equal sign represents the result of A MOD B).
AND is computed as:
floor((1 + 1) / 2) = floor(2 / 2) = 1
So, our thought experiment for the week is this -- what does it mean, considering how we've defined XOR above, when we perform some operation x MOD y? Further, does the relationship between the MOD function and XOR lead us to any new methods for carrying out modular arithmetic? I suspect someone has already addressed this but I haven't found anything about it yet. Anyway, I'll report back later with my findings (however trivial they may be).
XOR b_2_
---------
0 1
0 0 1
1 1 0
AND b_2_
---------
0 1
0 0 0
1 0 1
Now, let's examine b_3_:
XOR b_3_
---------
0 1 2
0 0 1 2
1 1 2 0
2 2 0 1
AND b_3_
---------
0 1 2
0 0 0 0
1 0 0 1
2 0 1 1
If we generalize this across all _n_ valued logics, we can see that to mathematically implement these truth tables is relatively easy. For some number A and some number B converted to base _n_ (so A in base _n_ will be some set of values {a1, a2, etc.}, as will b), we can find XOR and AND using the following equations:
a(x) XOR b(x) = a(x) + b(x) MOD _n_
a(x) AND b(x) = floor((a(x) + b(x)) / n)
where a(x) and b(x) are members from {a1, a2 .. a(x)) and {b1, b2 .. b(x)} (as defined above) with the same index value x. For example, in base 2 the XOR of a(x) = 1 and b(x) = 1 is:
a(x) + b(x) = 1 + 1 = 2, and
0 = 2 MOD 2 (note: I'm not following the convention where the number immediately following the equal sign represents the result of A MOD B).
AND is computed as:
floor((1 + 1) / 2) = floor(2 / 2) = 1
So, our thought experiment for the week is this -- what does it mean, considering how we've defined XOR above, when we perform some operation x MOD y? Further, does the relationship between the MOD function and XOR lead us to any new methods for carrying out modular arithmetic? I suspect someone has already addressed this but I haven't found anything about it yet. Anyway, I'll report back later with my findings (however trivial they may be).
