[math-fun] Generalizing integers and primes (was Re: Simple finite group problem)
Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
"Keith F. Lynch" <kfl@KeithLynch.net> wrote:
Are those the only two interesting ways of generalizing integers to the complex plane?
No. Let D be any square-free positive integer > 1 and consider numbers of the form p+q.sqrt(d) where p,q are rational; this forms a field; the algebraic integers in the field are either the numbers of the form p+q.sqrt(d) where p,q are integers, or the numbers of the form p+q(1+sqrt(d))/2 where p,q are integers, and these are by any reasonable criteria an "interesting way of generalizing integers to the complex plane".
You don't mention i. Are these numbers all real? I once played with numbers in the form a + b*sqrt(2), where a and b are integers. Those appear to form a field. My intention was to find a way to efficiently factor large integers. My plan was to find "second-order primes" which factor ordinary primes, "third-order primes" which factor second-order primes, etc. Then I'd find which of the first thousand or so, say, tenth-order primes divide the number I'm trying to factor. I'd then combine them by pairs or triples to find ninth-order primes which would of course also factor the target number. I'd then combine those by pairs or triples to find eighth-order primes which would of course also factor the target number. And I'd work my way up until I had the first-order (regular integer) primes which factor the target number. I'm indifferent to the nature of these higher-order primes. They could be complex, quaternions, algebraic, matrices, or something entirely new and weird. And the operation might not even be ordinary multiplication except in the last step. Gaussian primes looked like a promising set of second-order primes, except for two things: Only about half of all regular primes have Gaussian prime divisors, and there's no obvious candidate for third-order primes. One of my approaches was to form a field of two-part real algebraic numbers in the form a + b*sqrt(2) for second-order primes, another field consisting of four-part numbers based on the 4th roots of 2 for third-order primes, another field consisting of eight-part numbers based on the 8th roots of 2 for fourth-order primes, etc. But it turned out that the only regular prime any of these numbers would non-trivially divide was 2 itself. Sticking in cube roots of 2, square roots of 3, etc., didn't help much.
On 23/05/2016 04:39, Keith F. Lynch wrote:
Are those the only two interesting ways of generalizing integers to the complex plane?
No. Let D be any square-free positive integer > 1 and consider numbers of the form p+q.sqrt(d) where p,q are rational; ... You don't mention i. Are these numbers all real?
Whoops. I meant p + q.sqrt(-d). (Or else: let D be any square-free integer other than 1 and, etc. The case where the thing you sqrt() is positive works perfectly well, but indeed it has nothing much to do with complex numbers.)
I once played with numbers in the form a + b*sqrt(2), where a and b are integers. Those appear to form a field.
If you let a,b be rational then they form a field. If you let a,b be integers then they form a ring, which is in fact the ring of algebraic integers contained in that field.
My intention was to find a way to efficiently factor large integers. My plan was to find "second-order primes" which factor ordinary primes,
If d is a quadratic residue mod p (but not a multiple of p) then in (the ring of integers of) the field Q(sqrt(d)) p splits into two primes whose product is p. But you need to be careful in this area -- e.g., in most of these rings you don't have unique factorization, and for some purposes you need to consider not prime *numbers* but things called prime *ideals* which are more complicated. I don't think any of this will help with factoring large numbers, though. (But see e.g. https://en.wikipedia.org/wiki/Quadratic_sieve and https://en.wikipedia.org/wiki/General_number_field_sieve for some powerful factoring techniques that are slightly related...)
Gaussian primes looked like a promising set of second-order primes, except for two things: Only about half of all regular primes have Gaussian prime divisors, and there's no obvious candidate for third-order primes.
Using any quadratic field it turns out that about half of all primes "split". You could get your higher-order primes by looking at larger extensions -- e.g., go from Q(sqrt(2)) to Q(sqrt(2),sqrt(3)). But only half the primes that split the first time will split again the second time, and the computations will get more painful, and I don't think this will help you factor large numbers. (But, important note, I'm not a real number theorist and I could be wrong.) -- g
Fix some squarefree positive integer d. Then the field K = Q(sqrt(-d)) = {K + L sqrt(-d) | K, L in Z} is the same as all ratios (K + L sqrt(-d)) / (M + N sqrt(-d)) for K, L, M, N in Z. Or what's the same thing, all expressions {a + b sqrt(-d) | a, b in Q}. ----- Its ring of algebraic integers can be defined as O_K = {y in K | P(y) = 0}, where P is an monic polynomial over the integers. It's not immediately obvious that O_K is closed under addition and multiplication, but it is. ----- It turns out that: O_K = Z[sqrt(-d)] if d != 1 (mod 4) and O_K = Z[(1+sqrt(-d))/2] if d = 1 (mod 4), as I think was mentioned previously. The units of a ring are defined as those elements having a multiplicative inverse. ----- An irreducible element z of O_K (normally assumed to be nonzero and not a unit) is one for which any factorization z = xy is such that at least one of x and y is a unit. ----- O_K is defined to have unique factorization when every nonzero element z is the product of irreducible elements and a unit, such that: For any two such factorizations, there is a one-to-one correspondence between the irreducible elements in one factorization and those in the other, such that each corresponding pair is equal up to multiplication by a unit. ----- Then one of my favorite theorems was conjectured by Gauss in 1801: The set of d for which the ring O_K has unique factorization is precisely {1, 2, 3, 7, 11, 19, 43, 67, 163}. Gauss had shown that each O_K for any d on this list has unique factorization; his conjecture was that these are the only such d. This was proven by Heegner in 1952. It was later reproved by Deuring in 1968 and Stark in 1969, who both thought Heegner's proof contained a gap. It is now generally viewed as not really containing a gap. —Dan _____ P.S. In the late 1870s, Dedekind built on Kummer's theory of ideal numbers to show that the ring of ideals of any O_K (in greater generality than just for the imaginary quadratic fields) has unique factorization.
On May 23, 2016, at 2:06 AM, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
On 23/05/2016 04:39, Keith F. Lynch wrote:
Are those the only two interesting ways of generalizing integers to the complex plane?
No. Let D be any square-free positive integer > 1 and consider numbers of the form p+q.sqrt(d) where p,q are rational; ... You don't mention i. Are these numbers all real?
Whoops. I meant p + q.sqrt(-d). (Or else: let D be any square-free integer other than 1 and, etc. The case where the thing you sqrt() is positive works perfectly well, but indeed it has nothing much to do with complex numbers.)
I once played with numbers in the form a + b*sqrt(2), where a and b are integers. Those appear to form a field.
If you let a,b be rational then they form a field. If you let a,b be integers then they form a ring, which is in fact the ring of algebraic integers contained in that field.
My intention was to find a way to efficiently factor large integers. My plan was to find "second-order primes" which factor ordinary primes,
If d is a quadratic residue mod p (but not a multiple of p) then in (the ring of integers of) the field Q(sqrt(d)) p splits into two primes whose product is p.
But you need to be careful in this area -- e.g., in most of these rings you don't have unique factorization, and for some purposes you need to consider not prime *numbers* but things called prime *ideals* which are more complicated.
I don't think any of this will help with factoring large numbers, though.
(But see e.g. https://en.wikipedia.org/wiki/Quadratic_sieve and https://en.wikipedia.org/wiki/General_number_field_sieve for some powerful factoring techniques that are slightly related...)
Gaussian primes looked like a promising set of second-order primes, except for two things: Only about half of all regular primes have Gaussian prime divisors, and there's no obvious candidate for third-order primes.
Using any quadratic field it turns out that about half of all primes "split". You could get your higher-order primes by looking at larger extensions -- e.g., go from Q(sqrt(2)) to Q(sqrt(2),sqrt(3)). But only half the primes that split the first time will split again the second time, and the computations will get more painful, and I don't think this will help you factor large numbers.
(But, important note, I'm not a real number theorist and I could be wrong.)
-- g
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Dan Asimov -
Gareth McCaughan -
Keith F. Lynch