Crazy Math

More on "Hasse Interrogation"

2010-02-12T14:36:00.001-08:00

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.

Thoughts on Goldbach Conjecture

2010-01-08T15:42:00.001-08:00

...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:

	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...

Hasse and Hensel

2009-11-24T11:24:00.001-08:00

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.

Hasse Interrogation

2009-11-09T11:40:00.001-08:00

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:

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.

Figurate Numbers and factoring, pt. 2

2009-01-26T10:24:00.000-08:00

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.

Figurate numbers and factoring, a gentle intro

2008-12-09T12:32:00.000-08:00

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.

MOD and XOR

2005-02-22T10:59:00.000-08:00

...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).

update and indexes

2004-08-24T00:44:00.000-07:00

I have not fallen off the face of the earth, although I do now find myself in an interesting place, trying to determine where to go next.

Let's begin with Z, which I define here as the set of all integers greater than 1. Factor all of the members of Z, which is infinite. What do you get? The first answer that might spring to mind is "the set of all primes", which I'll denote as P. O.k., but is that _really_ what you get? Actually, it isn't. What you really get is all the primes, each counted an infinite number of times. For instance, if I completely factor 8, I get 2 * 2 * 2. That's three 2s, not one, and if I factored all the integers I'd wind up with quite a lot of 2s. The same could be said for 3, 5, 7, etc. So, if we throw all our factors into a set we can definte this set as P_2. It's similar to P, in that P is included in P_2, but it is an order of infinity greater than P.

Ah, but we can go further. What if, for instance, we count all the powers of a prime seperately? In this case, a number such as 8 is equal to 2^3. If we now re-order our set we've gained another degree of infinity, for now we have all the prime powers counted infinitely, along with all the primes counted infinitely and the infinity of primes, and I denote this set as P_3.

And this, I think, leads to an interesting and most basic question. Which, if any, of these three sets is "the right one"? I tend towards P_2, but this is only because I don't like the idea of considering each power of a prime as a seperate case. It's an arbitrary distinction to be sure, but since this is my math blog and I'm just thinking out loud here I'll declare, by fiat, that P_2 is my favorite of these three sets.

If that were all we'd have quite a bit to think about, because now there's an interesting issue to address. In the set P_2 we're implying that all the 2s, for instance, are seperate. This is a question that I can't begin to address, but its interesting to consider if that were actually the case. By "actually the case", I mean that making this distinction would have some mathematically significant purpose.

In my mind it does, and this is because by profession I do alot of database programming. In programming databases, one deals often with "relational" data. This means that an object can be related to another object or group of objects. Think of the structure of a company, for instance. The parent company may have divisions, and these divisions can have children. We can draw this relationship, and it'll look like a tree, with the branches representing different "child" divisions. Let's say that we wanted to search through this tree to see if division a is related to some other division, maybe f. We can write a routine that will figure out all of the relations and put them into a table with two columns, one for "parents" and one for "children". Thus f will appear as a "child" and a as a "parent" no matter how many levels may seperate them. If we compare our tree and our two-column table, we see that the table is quite a bit larger than the tree, and both are larger than the number of divisions within the company.

In case you didn't catch the analogy, the "divisions" represent the primes; the "tree" represents all the positive integers. If we took all the "divisions" listed in the two-column table and put them into one set, with each "division" grouped together into its own subset, we'd have a set that's analogous to P_2.

The rules that define the relationships are what cause the generation of the extra information that results in our P_2 set being larger than the set of primes. What are those rules? Is there one algorithm that states them or mimics them? Can such an algorithm be devised? That's the question at the root of the problem of factoring, and I believe that the concept of the set P_2 can help us better approach the problem.

Now, that line of thought has occupied me for the last few weeks. If that were all, it would be fine and good. However, that is not all, and that's why I'm putting up this post.

We have not taken into consideration here the concept of unit addition.

My examination of this subject is incomplete, but here's where my thoughts have been going in the last couple of days. We can construct the set P_2 in a different manner than simply factoring all the integers greater than 1. Instead, let us use unit addition to break apart each integer into its prime component. I say "component" because that's what unit addition is all about -- one number is the "unit", and it is added to itself some n number of times. Take for example the number 6. This number, in unit addition terms, can be broken down two ways -- 2 + 2 + 2 = 6, and 3 + 3 = 6. This is fundamentally different than the factoring case, where we get 3 * 2 = 6, and the resulting set will therefore be different. It won't look different to us (it's still the set of all primes, each prime counted an infinite number of times), but a very interesting thing happens when we look at the individual prime units.

Let us assign an index number to each occurance of a prime in the set P_2 created by "factoring" into primes and P_2 created by reversing the unit addition process. Now, we will recombine the various elements to produce the set Z again, only this time let's add up all the index values for the numbers used. So, in the case of the number 2, the index value is one in both our sets P_2 because in both sets it is the first occurance of the number 2. We have the same story with 3, and now we get to 4. In the case of four, we have a.) the second two multiplied by the third two -- this gives us a combined index value of 5, and b.) the second two plus the third two, which again gives an index sum of 5. We move on to 5, which will have an index sum of 1 in both sets. However, 6 is where we start to run into the fun stuff. In the multiplicative set, we have a.) the fourth two times the second three for an index sum of 6, and b.) either the fourth two plus the fifth two plus the sixth two, which gives us an index sum of 4 + 5 + 6, or 15; or the second three plus the third three, which gives us an index sum of 5.

I think that's enough for tonight; it's late and I need sleep (a crazy day of programming awaits tomorrow). I hope this gives you some food for thought. Who knows if it's actually useful...

Fractals, Fractals everywhere

2004-07-15T16:27:00.000-07:00

I wanted to be doubly sure I understood the definition of a fractal before I posted this, so I've been doing some research into fractals. More specifically, I've been looking at fractal sequences, and I think I'm sure enough about the definition of fractal sequences to state the following:

Let Z = all positive integers greater than 0.
BigOmega(Z) is a fractal sequence.
BigOmega(Z2), Z2 = all odd positive integers greater than 0, is also a fractal sequence.

I haven't, for some reason, been able to find that stated on the 'net. So I'm stating it here without argument, but these sequences are very much self-similar. If you start with a prime p, and take the set of all all the numbers in the sequence divisible by that prime, BigOmega of that set will be the same as BigOmega(Z) + BigOmega(p) . This is true of the set of all positive integers, all even integers, and all odd integers.

A more formal approach to defining the factoring problem

2004-07-09T15:39:00.000-07:00

I've been thinking more (of course) about factoring. Here's some thoughts; I'm recording them here mostly so I won't forget what I was thinking (it's more portable and permanent than paper):

Let II equal the set of all "Information". I believe there's already a well-defined "universal" set, but I don't know it's symbol. Anyway, all sets of numbers are subsets of this "Information" set. Since this is the set of all "Information", for kicks we'll throw into this set all possible logical operations, all math functions, etc. Z, the set of positive integers, is a subset of this universal set. R, the subset of rational numbers, is also a subset of this set. It seems to me that most apporaches to factoring are based on techniques applied mostly to the set Z. What if we include the set R? In R, a number like 7 has factors, because it can also correspond to 70, 700, 7000, etc. Namely, 7/2 = 3.5, which is equivalent to 7 * 5 / 10, or 35/10. It could also be equal, for that matter, to 700/20, and so on. Thus while 7 has no factors in Z besides one and itself, it _does_ have factors in R. Perhaps there is some logical or functional subset of II which, when given a member of I, determines whether it has factors in R as well as I.

I'm trying to formalize this because I've found that by symbolically representing things I sometimes see stuff that I otherwise wouldn't see. Anyway, some food for thought.

Conjecture

2004-06-24T16:51:00.000-07:00

Here'a a conjecture (my first):

Let S{n - x} represent the set of all numbers in the set {2^n .. 2^(n + 1) - 1} with n - x factors. If n = 3, S{n - 1} therefore represents the set of all numbers in the set {2^3..(2^4 - 1)} with n - 1, or 2, factors. Let us progress through the sets from n = 1 to n = infinity. As we progress from set to set, each subset S{n - x} will eventually reach a maximum "size". For instance, in any set {2^n .. 2^n - 1}, the maximum number of members with n - 1 factors is 5. Each subset S{n - x} "begins" with a set of prime numbers (these occur when n - x = 1), and "end" in some other set. Let us define the "length" of a set as the number of sets between the "beginning" set and the "ending" set, _not_ including those two sets.

Conjecture: The "length" of a set S(n - x) = the xth member of the Lower Wythoff sequence.

Or, in other words, the "length" of S(n - x); x = 1 is 1, x = 2 is 3, x = 3 is 4, x = 4 is 6, x = 5 is 8, and so on. If we add 2 to each member of the Lower Wythoff sequence, we get the absolute length (i.e., the length including the first and last set).

Errors, errors, aren't they fun?

2004-06-18T15:41:00.000-07:00

So, my somewhat scatterbrained post from yesterday (I was noticing several logical nonsequitirs, among other delights) also contained an interesting error, and one which kinda throws a wrench in the works. It's like this: All is fine and good with the symbolic representation of the composition of some set, up until n = 5. However, we run into a problem in n = 5. Namely, we can't say that Cd3 (i.e. the third degree composite) is odd. n = 5 is this set -- {32..65}. Now, the smallest n-degree odd composite is 3^x. The first few values are 3, 9, 27, 81... If you've noticed, there is no member of {32..63} with a factorization of 3^x. Since 3^x is the smallest possible odd composite of degree x, the only possible members of {Cd3} in {32..63} have to be even, since the range of the function BigOmega is smooth. No biggie, since that's the case we can just figure out whether or not 3^x lies in a set and work things out from there. The problem, though, lies in the symbolic representation I laid out in the last post. In it, I defined Cdn as representing an odd composite of degree n. It turns out this is not always the case -- Cdn could also represent an even composite. This means the set of all {Cdn} can include both even or odd numbers, that it overlaps with the even members and thus cannot be rigidly defined as meaning "an odd composite of degree n". Instead, the definition should be "a composite of degree n". This gums up our ability to count symbolically represented even and odd numbers in these sets. I.e., if we look at {E, P} (which has a symbol count of 2), there are two members represented symbolically. However, if we look now at {{{E, P} * 2} & P} * 2 | {Cd2} & {P} (which has a symbol count of 5), we can't say with a certainty whether Cd2 contains even numbers, odd numbers, or both. By definition all even numbers have been defined symbolically and we cannot assume that, say, {Cd2} doesn't include {P * 2}, which means we cannot say with certainty that the symbol count equals 5. Since we can't accurately count the symbolic representation of the set, we cannot say with accuracy how many symbolic representations there are in the set _without_ figuring out first if that particular set includes some number 3^x.

I kind of knew this was true in the back of my mind, but it wasn't until I worked out the symbolic representation for {32..63} that I realized the obvious error. That doesn't mean, though, that all is lost. Sometime in the next few days I'll post about an interesting consequence of the disjointed overlap of n = y and 3^x. We already know that, with the exception of the set {2, 3} we never have a set where the largest odd composite is 3^n. This would mean that 2^n and 3^n were in the same set, which they cannot be since the _smallest_ number with n possible factors is 2^n, and therefore 3^n has to occur in at least the next set, i.e. n + 1. Until then, you might want to consider the set of numbers output by performing BigOmega for each member of the set {2..256}. It will figure prominently in the next post...

Further results on composition of sets of the form {2^n..2^(n + 1) - 1}

2004-06-16T13:36:00.000-07:00

A few posts ago I asked "what is the smallest number x with n = BigOmega(x)" (I didn't phrase the question quite that way, but that's what I meant...). The answer is 2^n. I.e., the smallest number with BigOmega(x) = 2 is 2^2, or 4 (BigOmega(4) = 2). Since this is the case, using successive values of 2^n to divide the integers is a logical way to examine the properties of BigOmega(x). These sets can be expressed generally like this: {2^n..2^(n+1) - 1}.

I've been interested in these sorts of sets for awhile, mostly because they have interesting properties. To give you a more concrete idea of what these sets look like, here a a few:

{2, 3} = {2^1..2^2 - 1}, or n = 1
{4, 5, 6, 7} = {2^2..2^3 - 1}, or n = 2
{8, 9, 10, 11, 12, 13, 14, 15} = {2^3..2^4 - 1}, or n = 3

and so on.

We can define rules that govern these sets fairly easily. Notice, for instance, that when we move from set to set, the even members of the next set are equal to the odd numbers of the previous set times 2. As an example, the even members of n = 2 are 4 and 6, which are derived as follows:

4 = 2 * 2
6 = 3 * 2

This can also be expressed as {2, 3} * 2.

If we were to take BigOmega of all the members of a set with n = y, we'd see that the _range_ of BigOmega is always (1..y), or all the integers beween 1 and y. For example, using n = 2 again we have BigOmega{4, 5, 6, 7} = {2, 1, 2, 1}. Therefore the range of BigOmega over (1..y) is "smooth" (meaning there are no skips). For some other set where n = 15, BigOmega of that set will range over (1..15), without skipping any integers between 1 and 15. Because of how these sets are constructed we can also deduce that the first member will always be even for n > 0. We will now use these rules, and some symbols defined below, to define a symbolic representation of the "composition" of these sets.

Let P represent any prime. E represents the only even prime, 2, and Cdn represents some odd composite number of degree n (ex: Cd3 is a 3rd degree, odd composite). For example, 27 is an odd composite number of degree 3, because BigOmega(27) = 3. In other words, we use BigOmega to determine the "degree" of a number. We use the pipe symbol, "|", to seperate even and odd elemets of a set or group of sets. Even elements will always be listed on the left, and odd elements on the right of the pipe symbol.

We now construct sets using these symbols to represent the "structure" of some set {2^n..2^(n+1) - 1}. For illustrative purposes, I'm going to list the members of these sets explicitly. Below each set is a short explanation of what all the symbols mean:

{2, 3} = {2^1..2^2 - 1} = {E, | P}
This set contains one prime P and the even prime, E.

{4, 5, 6, 7} = {{E, P} * 2} | {P}
This set contains all members of the previous set multiplied by 2, and at least one new member, an odd prime P. The rules governing these sets disallow an odd composite from appearing in this set.

{8, 9, 10, 11, 12, 13, 14, 15} =

{{{E, P} * 2} & P} * 2 | {Cd2} & {P}

This set contains all the members of the previous set multiplied by 2, and at least one new prime and one new second-degree odd composite.

If we count the number of members represented symbolically in each of our sets, we get our series.

Generating function: 1 + 1 = 2, 2 + 1 = 3, 3 + 2 = 5, 5 + 3 = 8, 8 + 4 = 12, 12 + 5 = 17, and so on.

The size of each set is easily determined (size = 2^n), thus we can see how our "error" grows as we progress from set to set:

known	total size	unknown
2	2	0
3	4	1
5	8	3
8	16	8
12	32	20
17	64	47
23	128	105
30	256	226
38	512	474
47	1024	977

We can also see how the error grows for the "even" numbers and "odd" numbers. Because of how our sets are constructed, the number of even and odd members is simply (2^n)/2, thus in set {2^2..2^3 - 1}, the size of the even and odd sets is (2^2/2), or 2. from our symbolic representation above, we can then determine the "error" for even and odd members seperately:

known even	size even	unknown
1	1	0
2	2	0
3	4	1
5	8	3
8	16	8
12	32	20
17	64	47
23	128	105
30	256	226
38	512	474

known odd	size odd	unknown
1	1	0
1	2	1
2	4	2
3	8	5
4	16	12
5	32	27
6	64	58
7	128	121
8	256	248
9	512	503

That's probably as much crazy math as any one person can handle for a day, so we'll stop here. More to come later.

Further thoughts

2004-06-06T06:12:00.000-07:00

Two thoughts:

a.) Factoring isn't the inverse of multiplication, it's the inverse of addition.

b.) While "unit" addition with any number other than 1 cannot produce a series which contains primes, addition using _offsets_ will. Example -- unit addition with 2 + 2(Z) (2, 4, 6, 8...) as opposed to unit addition of 2 with an offset of +1, i.e. 2 + 3(Z) (2, 5, 8, 11, 14, 17...). Not all offset series will contain primes.

1 is an interesting number

2004-06-06T02:37:00.000-07:00

The number 1. I've been thinking about it alot recently, due to the fact that it "acts" different than the other numbers. for instance, in the case of the primes they all have two factors -- the number one and themselves. These aren't useful (well, that's the prevailing opinion anyway...) factors, but they do point out the main difference between the number one and the other real numbers. Namely, one divided by itself is itself. While we can get any other integer to behave like the number one with respect to BigOmega (by performing what was described a few posts below as "unit addition"), none will act exactly the same. Any other integer will create a pattern where the least number of factors any member can have is two. In this sense, the only way to produce prime numbers is by performing unit addition with the number one. All the other "primes" using other units will have at least two factors. This is not counting, of course, our "universal" factors -- one and the number itself. The really interesting part of all this is that the concept of any number divided by itself equals one applies to all sorts of suspects outside the set of positive integers; rational numbers, irrational numbers, imaginary numbers, complex numbers, etc. PI divided by PI is one, even though no end has been found to the digits in PI. My gut tells me that part of the answer to knowing a number's factor base is found in a solid understanding of what the concept of one really means, and how to disassemble its behaviour and duplicate it elsewhere. That's an odd concept, transmuting the logical behaviour of 1 to another number, say, 22. But who says it's impossible? Perhaps it is, but 1 is still an interesting number (even if it is the loneliest).

Real Math

2004-05-25T14:29:00.000-07:00

...And here's some real math:

http://scholar.lib.vt.edu/theses/available/etd-32298-93111/unrestricted/etd.pdf

This is a very good paper that explains the current state-of-the-art in factoring. There might be other stuff on the horizon, but as far as meat-and-potatos in-use factoring is concerned, the General Number Field Sieve method is it. The paper has a very good introduction section which explains several concepts that I've always wanted to understand -- Factor base, "smooth", etc. It also includes worked examples (although I haven't made it to those yet) and a step-by-step of how the whole thing works. It's a rather long paper, so cuddle up with a pen and paper and play along for a few nights after work for maximum fun. Combined with the video lectures by David Deutsch linked below, these two sources are a good place to go for introductions (if you already have some physics and math under your belt) to the topics of factoring and quantum computing. Anyway, I figure that if I should ever actually come up with something useful for factoring, I should understand how it relates to the current algorithm and be able to explain how it's different. Plus, it's never a bad thing to learn _real_ math and physics!

Factoring, continued

2004-05-22T12:43:00.000-07:00

Here's the first part in a series about my investigations into factoring. As I said earlier, I think that any "algorithm" (I'll use that word to mean both computer programs (classical or quantum) and equations) that successfully factors numbers in polynomial time should output all the factors and simultaneously output Bigomega.

Let's begin by looking at the _function_ Bigomega. It is defined as a function which outputs all of the factors of a number with multiplicity. Bigomega of 1 thru 10 is {1, 1, 1, 2, 1, 2, 1, 3, 2, 2}. Now, let's say we want to know Bigomega of any number x multiplied by 1 thru 10. The answer will be Bigomega{1..10} + Bigomega(x). So, if we were to use the number 3, then Bigomega of our new set (i.e., 3 * {1..10}) is {1, 2, 2, 3, 2, 3, 2, 4, 3, 3}. Note what happens with the number 1. When you multiply any number by 1, you get the same number, thus multiplying by 1 has no effect on Bigomega, so from here on out when speaking about multiplication we'll skip the number 1 (one, though, will become much more interesting in a moment...).

For now, let's formalize this a bit:

I = set of all positive integers
S = some subset {n1...nx} of I
x = member of I

So, Bigomega(S * x) = Bigomega S + Bigomega x, S > 1
For S = 1, Bigomega(S * x) = Bigomega x

Multiplication, then, is pretty straightforward...right? Let's now examine the case of addition. Before getting into sets, we'll start simple. Take, for instance, the case of the number 3. Add 1 to 3 we get 4. Bigomega of 3 = 1, while Bigomega of 4 = 2. Add 1 again, we get 5, and Bigomega of 5 is 1. If we do this on to infinity, we'll end up with Bigomega I, I > 3. Let's make this more interesting. Consider, for a moment, what multiplication really means. If we write "3 * 5", we could just as easily say "add three to itself 5 times", or "add 5 to itself 3 times". In other words, multiplication is just a special case of addition. It's some "unit" x (which is a member of I) added to itself n number of times. So, multiplciation is just "unit addition". Let's consider that for a moment -- "unit addition" creates the same Bigomega output as multiplication. Whether we add 1 to itself some n number of times or 5 to itself some n number of times, the result will be the same - Bigomega(x) + Bigomega(n).

So, if that's the case... Let me introduce a concept I've been playing with that I call "offset". I'm still looking into it, which means I don't understand everything about it. Anyway, it works like this. Say we use a unit of 10. 10 + 10 = 10 * 2 = 20. Bigomega(20) = 3 (because 20 = 2 * 2 * 5). What if, instead of doing 10 + 10, we do 10 + 9, 10 + 9 + 9, etc.? We'll get 10, 19, 28, 37, and so on. In this case, the "offset" is +1. This is so because our series could also be expressed as 1 + 9, 1 + 9 + 9, etc. These "offset" series produce different patterns of output for Bigomega. One of the areas I'm interested in examining is how these sets relate to each other. You may have noticed that for some set created by using 9 as the unit of addition, there are exactly 9 possible offisets which won't repeat themselves. Note that if you extended all 9 sets to infinity and combined them, you'd end up with the set I, I > 9. Now, if you're really paying attention you'll notice something cool here. If we start with, say, 1 + 9, then continue on up to 8 + 9, we'll get every number except multiples of 9. So, we now add in 9 + 9, or offset 0... This system is feeding back on itself, i.e. that last set is simply 9 * I. We _have_ to have a "unit" set if we want to recombine the sets to get I, I > 9. The implications of this are very interesting, namely, that within the set of integers I, the basic pattern Bigomega(I) + Bigomega(x) repeats itself many, many times. Bigomega I _is_ the basic pattern, but it's composed on an infinite number of copies of itself!

I'll go ahead and stop here for now. In the meantime, let me give you something to think about until my next post (whenever that is). What is the smallest possible number with n number of factors? Or, in other words, what's the smallest possible number with 3 factors? with 4? And so on.

Thoughts on factoring

2004-05-20T11:52:00.000-07:00

[sarcasm] Anybody who's anybody these days thinks about factoring [/sarcasm]. It's a beautiful thing, really, to be able to factor very large integers in polynomial time. Anyway, we're not there yet. I think therefore it's o.k. to be a bit creative when approaching the problem. Here's my approach. The first, and most important question in my opinion, is what would an algorithm or equation that factored large numbers do? That seems simple up front - well, factor the number of course. But there's the rub. You don't know (unless you're factoring RSA numbers or someone tells you, or you construct the number yourself) how many factors a number _has_ before you start. So, in my opinion a successful factoring algorithm or equation would do two things. First, it would output the number of factors in the number (my personal view is that this would include multiple instances of the same factor, so that 16 has four factors (2 * 2 * 2 * 2)). Second, it would produce all the factors in one interation. That, to me, is what the equation or algorithm would do. To summarize -- output Bigomega (the upper-case Greek letter that signifies "primes counted with multiplicity") and output all the factors, without using a recursive loop to find successive factors.

Quantum computing provides interesting possibilities as far as these "requirements" are concerned. In fact, one of the two main algorithms discovered so far for quantum computers is a factoring algorithm. However this algorithm finds one factor at a time -- http://en.wikipedia.org/wiki/Shor%27s_algorithm by computing the "period" of the function A^r Mod N, where a is a pseudo-random number less than n. I've noticed some similarities between some of the math I'm working on and some of the math used in quantum computing [er, that's because they use the same kinds of math - ed]

Where does that leave me? High and dry, first off (I haven't even begun to find anything yet). It may be that an equation or algorithm with these output requirements doesn't exist, that I'm following a cold trail. Nevertheless, it's what I have to work with so I'm pursuing it. Over the next few days I'll post the stuff I've been doing. I should, of course, put a warning here -- WARNING: I don't have a degree in math although I studied a fair amount of it in college. My basic math skills are somewhere south of "suck", so don't take any math I present here as either a.) accurate, or b.) representative of the rest of mathematics. There are huge numbers of people out there whose skills far surpass mine. I just do this because, for me, it's fun and I really don't know if it might be useful or not. In the event any of it is, I'd like my "work" to be out there for other folks to use. Besides, someone out there might be able to offer useful corrections, although I suspect anyone with the skills to do so has better things to do.

Mo link

2004-05-19T21:52:00.000-07:00

http://www.allsci.com/parallel.html

A cool experiment demonstrating quantum interference that you can do at home.

Cool link

2004-05-18T12:22:00.000-07:00

http://www.quiprocone.org/Protected/DD_lectures.htm

If you've ever wanted to learn about quantum computing, here's a resource. Each lecture is an hour-long video (about 66 megs download size). So far, there are three. Highly recommended.

More on harmonic logic

2004-05-18T10:14:00.000-07:00

O.k., some further thoughts: Say we have a simple oscillator, a NOT gate which feeds back on itself. We set the system into "motion", and sample values immediately before the NOT gate, at some time T, and immediately after the gate, at some time T + dT, where dT is the time necessary to traverse the gate. If the system is clocked with a crystal or some other means, then dT is always the same to within some margin of error. What if we made dT random and isolated the system? If we sampled values before and after the gate, we'd still get the same "weight" for 1 and 0 (50% each). However, if dT is random and we have no way of measuring it, then we don't know if, at a particular instant, we'll measure a 1 or a 0. I wonder how similar this situation would be to the state of "superposition", the quantum state where the probability of finding the value of some variable in a system to be a or b is, essentially, the only valid description of the "state" of the system. For example, if an electron is provided exactly one-half of the energy to jump from energy level a to energy level b, then the probability of finding that electron in either energy level is 50%. And that's as specific as we can be about the state of the electron with respect to it's location in one of the two energy levels. That is, of course, until we measure which state the electron inhabits, or the system gains or loses energy. So, is the NOT gate system with random dT in a state of "superposition"? My assignment to myself today is to try and figure out if that's the case.

Harmonic logic

2004-05-17T11:33:00.000-07:00

Along the lines with the first post below, I had another idea -- this one's easier to play with. The idea is to construct harmonic logic systems that oscillate between two or more logical states. You can take, for instance, the output of a NOT gate and feed it back into itself. If you feed it a 0, it spits out a 1, which then goes back through and becomes a 0, etc. Anyway, when you extend the idea to include classical "oscillator" behaviour (and, perhaps, quantum system behaviour) things could get interesting (i.e., how does the concept of "resonance" apply to a system of logic gates?). More fun is to be had if we include reversible logic, and maybe even mix the two. This one is a bit easier to play with than the quantum stuff I mentioned in the post below; the concepts of classical and reversible logic are much more accessible than those of classical and quantum wave dynamics. Anyway, more food for thought.

Welcome to crazy math

2004-05-17T11:18:00.000-07:00

Hi, you've just arrived at crazy math, my own little corner on the web where I post random wierd ideas about stuff I think is interesting. Most of it has to do with math, etc. Most of it is pretty crazy and naieve, but hey we're having fun... Without further adieu, here's a random crazy idea for the day:

Harmonic quantum computing

The idea is this -- I don't know how nasty the math is for this (i.e., is it possible? Does anyone care?), but I had this idea the other night that it might be possible to build a hybrid classical/quantum computer. Instead of trying to keep a quantum system in the state of coherence for a long period of time (i.e., more than a few seconds), is it possible to design a system that oscillates between classical and quantum states? If so, then perhaps a computer could be built to take advanatage of this state flipping to perform both classical and quantum computations. I'm just barely beginning to pound into my head the math behind quantum computing, if you want more information check out this wonderful site. There are some obvious problems with this (how do you store all the information from the quantum cycle during the classical cycle), so I doubt it'd be terribly useful. It's fun to think about, though.