I'm considering more promotional type posts so I'll note now that in the last 30 days, which does go back a bit into October but mostly was in November, this blog has had according to Google Analytics and Woopra--a real-time analytics software--visits from over 60 countries (63 from Google Analytics since October 22nd and 62 according to Woopra since October 24th).
Top 5 countries in terms of visitor counts from Woopra:
1. United States
2. United Kingdom
3. Canada
4. Australia
5. India
Top 5 by visit counts from Google Analytics and Woopra:
1. United Kingdom
2. United States
3. Australia
4. Canada
5. India
Slight variation is from visit versus visitor counts (didn't see how to get visit counts by country in Google Analytics though I'm sure there's a way). The bulk of visitors are from the United States and the United Kingdom with a disproportionate share of visits from the UK given its population numbers versus that of the US. That is, per person the blog is much more popular in the UK than in the US.
Ok, enough blog promotion. This post is an experiment. Of course I'm looking to build readership counts by letting visitors realize that they're part of a select group of people from around the world who are coming to this blog. I'm starting the tag "marketing" for these type posts.
James Harris
Sunday, November 22, 2009
Saturday, November 21, 2009
Algebraic integer error
Here's an example of something mathematically weird. I'm going to show you a situation where you multiply by 7, but then can't seem to divide it back off, in the ring of algebraic integers:
7(175x2 - 15x + 2) = (5a1(x) + 7)(5a2(x)+ 7)
where the a's are roots of
a2 - (7x-1)a + (49x2 - 14x) = 0.
There is the 7 as promised on the left hand side, and you can see 7 on the right, but can you divide it back off? Let's try:
175x2 - 15x + 2 = (5a1(x)/7 + 1)(5a2(x)+ 7)
where the a's are still the roots of
a2 - (7x-1)a + (49x2 - 14x) = 0.
Did that work? Well that is a guess that one of the roots has 7 has a factor, so let's stick in a number, like x=1, as that's easy and we get:
a2 - 6a + 35 = 0.
But it's possible to prove that in the ring of algebraic integers that neither of the roots of that quadratic has 7 as a factor.
So with my little clever example I've managed to show you a situation where you can multiply by 7, yet be incapable of dividing that 7 back off in the ring of algebraic integers.
I stumbled across this problem back in 2002 (though it took me a while to figure out what was going on), and even got a paper published on it which was withdrawn by the editors of the journal when some Usenet people emailed their protest. The journal had one more edition and then died. That is, the editors killed it, shutting down publication.
The archives are now kept by the European agency EMIS.
I have a lot of pages on this blog covering this area, where you can get a list by clicking the label "nonpolynomial factorization" below.
What I did was solve the mathematical problem of why the ring of algebraic integers captures that 7, and will not let go, which I call entanglement, and I also got the huge bonus of being able to figure out the proper ring to replace the ring of algebraic integers which I call the object ring, where it is the first post on this blog, to give you some idea of its importance.
I got to name my own ring!!! HUGE bonus!!!
Real life is complicated though, as in fantasy, mathematicians are these "beautiful minds" who love mathematics and of course, love being correct. But this little beastie of an error blows up a lot of what many of them think they knew, as of course it should, as consider what you thought you knew from basic algebra:
7(x2 + 3x + 2) = (7x + 7)(x + 2)
And divide off the 7 easily enough:
(x2 + 3x + 2) = (x + 1)(x + 2)
You should be able to do the same regardless of the ring, so yeah, the ring of algebraic integers has a remarkable flaw that blocks algebra itself--removes basic algebraic operations like dividing that 7 back off--so yeah, that's kind of big.
The error means that the ring of algebraic integers can be used to appear to prove just about anything as that is a quirk that mathematical errors often give you, which is another reason why they can be so nasty.
So why haven't mathematicians acknowledged?
Well this thing has been around for over a hundred years!!! As long as the ring of algebraic integers has been around. It devastates over a hundred years of number theory in "pure math" areas where because the research was not practical, people didn't realize it doesn't work!
(Nice thing about practical mathematics is that if you get, say, a bridge design wrong, the damn thing will fall down!)
Poor bastards. You almost have to feel sorry for them: some of them with prestige and awards, positions in academia at top universities, and their math is crap.
I've been upset with them before but as I get older I can appreciate why they would run away from the truth. Each day continuing in error for them is a gift. Another day when they are still "special" to the world as top mathematicians, and not those poor people whose life's work got hosed by a brutal, abstract error in some old number theory.
Poor bastards.
James Harris
7(175x2 - 15x + 2) = (5a1(x) + 7)(5a2(x)+ 7)
where the a's are roots of
a2 - (7x-1)a + (49x2 - 14x) = 0.
There is the 7 as promised on the left hand side, and you can see 7 on the right, but can you divide it back off? Let's try:
175x2 - 15x + 2 = (5a1(x)/7 + 1)(5a2(x)+ 7)
where the a's are still the roots of
a2 - (7x-1)a + (49x2 - 14x) = 0.
Did that work? Well that is a guess that one of the roots has 7 has a factor, so let's stick in a number, like x=1, as that's easy and we get:
a2 - 6a + 35 = 0.
But it's possible to prove that in the ring of algebraic integers that neither of the roots of that quadratic has 7 as a factor.
So with my little clever example I've managed to show you a situation where you can multiply by 7, yet be incapable of dividing that 7 back off in the ring of algebraic integers.
I stumbled across this problem back in 2002 (though it took me a while to figure out what was going on), and even got a paper published on it which was withdrawn by the editors of the journal when some Usenet people emailed their protest. The journal had one more edition and then died. That is, the editors killed it, shutting down publication.
The archives are now kept by the European agency EMIS.
I have a lot of pages on this blog covering this area, where you can get a list by clicking the label "nonpolynomial factorization" below.
What I did was solve the mathematical problem of why the ring of algebraic integers captures that 7, and will not let go, which I call entanglement, and I also got the huge bonus of being able to figure out the proper ring to replace the ring of algebraic integers which I call the object ring, where it is the first post on this blog, to give you some idea of its importance.
I got to name my own ring!!! HUGE bonus!!!
Real life is complicated though, as in fantasy, mathematicians are these "beautiful minds" who love mathematics and of course, love being correct. But this little beastie of an error blows up a lot of what many of them think they knew, as of course it should, as consider what you thought you knew from basic algebra:
7(x2 + 3x + 2) = (7x + 7)(x + 2)
And divide off the 7 easily enough:
(x2 + 3x + 2) = (x + 1)(x + 2)
You should be able to do the same regardless of the ring, so yeah, the ring of algebraic integers has a remarkable flaw that blocks algebra itself--removes basic algebraic operations like dividing that 7 back off--so yeah, that's kind of big.
The error means that the ring of algebraic integers can be used to appear to prove just about anything as that is a quirk that mathematical errors often give you, which is another reason why they can be so nasty.
So why haven't mathematicians acknowledged?
Well this thing has been around for over a hundred years!!! As long as the ring of algebraic integers has been around. It devastates over a hundred years of number theory in "pure math" areas where because the research was not practical, people didn't realize it doesn't work!
(Nice thing about practical mathematics is that if you get, say, a bridge design wrong, the damn thing will fall down!)
Poor bastards. You almost have to feel sorry for them: some of them with prestige and awards, positions in academia at top universities, and their math is crap.
I've been upset with them before but as I get older I can appreciate why they would run away from the truth. Each day continuing in error for them is a gift. Another day when they are still "special" to the world as top mathematicians, and not those poor people whose life's work got hosed by a brutal, abstract error in some old number theory.
Poor bastards.
James Harris
Sunday, November 15, 2009
Solving quadratic residues
Remarkably my surrogate factoring research leads to a simple way to solve quadratic residues.
Given a quadratic residue q modulo N, with N a non-unit odd natural number, and k, where
k2 = q mod N
you can solve for k, using T = (1 + α2)q mod N, so T = (1 + α2)q + jN, where j is a non-zero integer, and α is a natural number of your choice.
You next check each factorization of T to find positive f1 and f2 such that f1f2 = T and then you get k simply enough from
k = α(1 + 2α2)-1(f1 + f2) mod N
where a key relation is T - k2 - f12 = 0 mod N, so T - f12 must be a quadratic residue modulo N.
That means, for instance, that if the first trivial factorization of T does not work, then none will, as f1 mod N will remain the same.
So let's try it. Let N = 35, and q=29 (I'll explain how I picked it later). Then with α=1, T = 2(29) mod 35, which is T = 23 mod 35.
You can use even T, but here I'll use the first odd, which is T = 93, and it does work with f1 = 93, and f2 = 1, as I get:
k = 3-1(93 + 1) mod 35 = 12(94) mod 35 = 1128 mod 35 = 8 mod 35.
And k = 8 mod 35 is a correct answer.
And now you can see how I picked that example as knowing that 35 has 5 and 7 as factors I picked the first k coprime to 35 that would not give a perfect square:
82 = 29 mod 35
Ok, so I picked k=8 as it was the first case where you get a non-square for the quadratic residue coprime to 35. Why not do the next?
So let's move up one still with α=1 and do, k=9.
So q = 11 mod 35, and T = 22 mod 35, so I can try T = 57.
The trivial factorization didn't work--which means no trivial factorization will--so I'll do the non-trivial one:
f1 = 19, and f2 = 3 so,
k = 3-1(19 + 3) mod 35 = 12(22) mod 35 = 264 mod 35 = 19 mod 35.
192 = 11 mod 35
so it worked!
And you can see that f1 also is the answer, and in general one of the factors will often be the answer with α=1, and one always will be if N is a prime number.
And that is a factoring example, as I know k=9 is a solution, so I have
192 = 92 mod 35
so (19-9)(19+9) = 0 mod 35, so (10)(28) = 0 mod 35,
and you pull 5 and 7 as factors with a gcd.
Remarkably there are 4 equations which I call constraints which decide when this approach will work:
1. f1 = αk mod p
2. f2 = α-1(1 + α2)k mod p
3. z = (2α)-1(1 + 2α2)k mod p
and
4. y = (2α)-1k mod p
where p is a prime factor of N.
All of those congruences must be true for a solution, but notice the k in each of them. If despite the congruence k is a factor of any two then it must be a factor of T as well, otherwise no solution.
For instance with q=2 and p=31, there is a solution with α=1 and T = 128, where f1 = 8, f2 = 16, give z = 12, y = 4, k = 8.
The 4 constraints provide a rich behavior which can guide selecting values for α, as notice that if k is even, and T is not, then you can be blocked with α=1, but then α=3 may work if k is coprime to 3.
Rather than check the 4 constraints for each prime factor of N, you can simply try several different values for α, as you have its modular inverse in 3 of the 4 constraints, while keeping α small so that its modular inverse is likely to be as large as possible.
So for any given α it'd make sense to only try a few T's and then move to a different α, as one of the 4 constraints may be blocking for some prime factor of N.
James Harris
Given a quadratic residue q modulo N, with N a non-unit odd natural number, and k, where
k2 = q mod N
you can solve for k, using T = (1 + α2)q mod N, so T = (1 + α2)q + jN, where j is a non-zero integer, and α is a natural number of your choice.
You next check each factorization of T to find positive f1 and f2 such that f1f2 = T and then you get k simply enough from
k = α(1 + 2α2)-1(f1 + f2) mod N
where a key relation is T - k2 - f12 = 0 mod N, so T - f12 must be a quadratic residue modulo N.
That means, for instance, that if the first trivial factorization of T does not work, then none will, as f1 mod N will remain the same.
So let's try it. Let N = 35, and q=29 (I'll explain how I picked it later). Then with α=1, T = 2(29) mod 35, which is T = 23 mod 35.
You can use even T, but here I'll use the first odd, which is T = 93, and it does work with f1 = 93, and f2 = 1, as I get:
k = 3-1(93 + 1) mod 35 = 12(94) mod 35 = 1128 mod 35 = 8 mod 35.
And k = 8 mod 35 is a correct answer.
And now you can see how I picked that example as knowing that 35 has 5 and 7 as factors I picked the first k coprime to 35 that would not give a perfect square:
82 = 29 mod 35
Ok, so I picked k=8 as it was the first case where you get a non-square for the quadratic residue coprime to 35. Why not do the next?
So let's move up one still with α=1 and do, k=9.
So q = 11 mod 35, and T = 22 mod 35, so I can try T = 57.
The trivial factorization didn't work--which means no trivial factorization will--so I'll do the non-trivial one:
f1 = 19, and f2 = 3 so,
k = 3-1(19 + 3) mod 35 = 12(22) mod 35 = 264 mod 35 = 19 mod 35.
192 = 11 mod 35
so it worked!
And you can see that f1 also is the answer, and in general one of the factors will often be the answer with α=1, and one always will be if N is a prime number.
And that is a factoring example, as I know k=9 is a solution, so I have
192 = 92 mod 35
so (19-9)(19+9) = 0 mod 35, so (10)(28) = 0 mod 35,
and you pull 5 and 7 as factors with a gcd.
Remarkably there are 4 equations which I call constraints which decide when this approach will work:
1. f1 = αk mod p
2. f2 = α-1(1 + α2)k mod p
3. z = (2α)-1(1 + 2α2)k mod p
and
4. y = (2α)-1k mod p
where p is a prime factor of N.
All of those congruences must be true for a solution, but notice the k in each of them. If despite the congruence k is a factor of any two then it must be a factor of T as well, otherwise no solution.
For instance with q=2 and p=31, there is a solution with α=1 and T = 128, where f1 = 8, f2 = 16, give z = 12, y = 4, k = 8.
The 4 constraints provide a rich behavior which can guide selecting values for α, as notice that if k is even, and T is not, then you can be blocked with α=1, but then α=3 may work if k is coprime to 3.
Rather than check the 4 constraints for each prime factor of N, you can simply try several different values for α, as you have its modular inverse in 3 of the 4 constraints, while keeping α small so that its modular inverse is likely to be as large as possible.
So for any given α it'd make sense to only try a few T's and then move to a different α, as one of the 4 constraints may be blocking for some prime factor of N.
James Harris
Subscribe to:
Posts (Atom)
