Differences between revisions 2 and 3
 ⇤ ← Revision 2 as of 2005-10-21 12:34:09 → Size: 6301 Editor: EwartShaw Comment: removed bulk of my comments - feel free to remove rest. ← Revision 3 as of 2008-12-08 10:45:39 → ⇥ Size: 6206 Editor: anonymous Comment: converted to 1.6 markup Deletions are marked like this. Additions are marked like this. Line 84: Line 84: That aside, the external literature sheds quite a bit of light on this subject. For example, a rational prime y is also a gaussian prime if (and only if) 3 = 4 | y. This follows from [http://en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_two_squares Fermat's theorem on sums of two squares]. That aside, the external literature sheds quite a bit of light on this subject. For example, a rational prime y is also a gaussian prime if (and only if) 3 = 4 | y. This follows from [[WikiPedia:Fermat%27s_theorem_on_sums_of_two_squares|Fermat's theorem on sums of two squares]]. Line 87: Line 87: [http://mathworld.wolfram.com/GaussianPrime.html Gaussian Primes at MathWorld] [[BR]][http://en.wikipedia.org/wiki/Gaussian_integer Gaussian integers at Wikipedia] [[BR]][http://en.wikipedia.org/wiki/Eisenstein_prime Eisenstein primes] A concept somewhat analogous to Gaussian Primes, but based on the third root of 1 (which might prevent factorizing negative integers, except that negative 1 is given special treatment such that the negative of a prime number is also considered prime) rather than on the square root of _1. [[MathWorld:GaussianPrime|Gaussian Primes at MathWorld]] <
>[[WikiPedia:Gaussian_integer|Gaussian integers at Wikipedia]] <
>[[WikiPedia:Eisenstein_prime|Eisenstein primes]] A concept somewhat analogous to Gaussian Primes, but based on the third root of 1 (which might prevent factorizing negative integers, except that negative 1 is given special treatment such that the negative of a prime number is also considered prime) rather than on the square root of _1. Line 92: Line 92: [[BR]] <
> Line 98: Line 98: * "Pseudo" in the page title is mis-spelled. -- RogerHui [[DateTime(2005-10-16T21:22:23Z)]] * "Pseudo" in the page title is mis-spelled. -- RogerHui <> Line 100: Line 100: * "([http://mathworld.wolfram.com/Pseudoprime.html Pseudoprime])" is already a widely recognised and well-defined mathematical term, so I think 0j1 etc. need to be called something else, especially as the idea of "primes" is linked with that of unique factorisation. As you are trying to split the hydrogen atom 1, "quark" would be a cute name, at least for the [[latex($\omega=\sqrt[3]{1}\approx$)]]_0.5j0.866025 underlying the Eisenstein integers (the origin of the term being "three quarks for Muster Mark" - Finnegan's Wake). Sorry for veering off topic, but at least this section is possibly temporary!-- EwartShaw [[DateTime(2005-10-16T23:31:23Z)]] * "([[MathWorld:Pseudoprime|Pseudoprime]])" is already a widely recognised and well-defined mathematical term, so I think 0j1 etc. need to be called something else, especially as the idea of "primes" is linked with that of unique factorisation. As you are trying to split the hydrogen atom 1, "quark" would be a cute name, at least for the <>_0.5j0.866025 underlying the Eisenstein integers (the origin of the term being "three quarks for Muster Mark" - Finnegan's Wake). Sorry for veering off topic, but at least this section is possibly temporary!-- EwartShaw <> Line 102: Line 102: * Oops, sorry about the mis-spelling. Assuming we can come up with some acceptable name for relatively prime primitive factors, how should we go about renaming this page? -- ["Raul Miller"] [[DateTime(2005-10-17T03:48:07Z)]] * Oops, sorry about the mis-spelling. Assuming we can come up with some acceptable name for relatively prime primitive factors, how should we go about renaming this page? -- [[Raul Miller]] <> Line 104: Line 104: * How about calling them "Primoids"? These were hideous mutant creatures, and were similarly only finally named in the end-credits :-) (google for inferno primoids).-- EwartShaw [[DateTime(2005-10-18T10:21:00Z)]] * How about calling them "Primoids"? These were hideous mutant creatures, and were similarly only finally named in the end-credits :-) (google for inferno primoids).-- EwartShaw <> Line 106: Line 106: * Actually, I've been leaning towards "Unique Factors" for things like _1 and 0, and "Unique Factorizations" for the essay as a whole. This might require I change some of the grammar, but the whole thing could probably do with an overhaul. -- ["Raul Miller"] [[DateTime(2005-10-18T13:07:30Z)]] * Actually, I've been leaning towards "Unique Factors" for things like _1 and 0, and "Unique Factorizations" for the essay as a whole. This might require I change some of the grammar, but the whole thing could probably do with an overhaul. -- [[Raul Miller]] <>

# Initial explorations

q: gives the prime factorization of positive integers. But what about larger domains?

If the domain were integers, there would need to be a way to factorize 0, and to factorize negative numbers. Including 0 and _1 as unique factors would be one way of achieving this.

If the domain were complex integers, the issue becomes more complex. First off, instead of _1 we should probably use 0j1. This lets us focus our attention on a single quadrant of the complex numbers. Any complex number can be represented as the product of a number whose real and imaginary components are non-negative with 0j1 raised to some power.

A function to determine which power of 0j1 to use is:

qj1=: [: #. [: ~:/\rows 0: > |.@+.

To find quadrant 1 numbers corresponding to arbitrary numbers, use (* 0j1"_ ^ qj1).

To find if a quadrant 1 number is relatively prime, you could use:

pcp= (2: = [: +/@, [: */"1 [: (= <.) [: +. ] % (>: j./ ])@i.@>.@|)"0

Note, however, that this completely changes the concept of what's prime and what's not.

   pcp i. 30
0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0
(e. p:) i. 30
0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1
I. ((e. p:) ~: pcp) i. 30
2 5 13 17 29

Why doesn't pcp indicate that some prime numbers are prime? It's because of the definition of primality buried in pcp. Basically, pcp considers a number to be prime only if there are no more than three complex integers (one, itself and 0j1) which can be multiplied together to produce the number. And, some prime numbers have complex integer roots.

   1j1 * 0j_1
2
2j1 * 1j2 * 0j_1
5
3j2 * 2j3 * 0j_1
13
4j1 * 1j4 * 0j_1
17
5j2 * 2j5 * 0j_1
29

Note that I'm using 0j_1 instead of 0j1^3 to avoid roundoff error (at the time of this writing, J appears to be using logarithms to compute 0j1^3).

Here's a snapshot of some of these unique factors for complex numbers numbers (with 0 as a placeholder for positions occupied by non-unique-factors).

   (* pcp) j./~ i. 10
0   0   0 0j3   0   0   0 0j7   0   0
0 1j1 1j2   0 1j4   0 1j6   0   0   0
0 2j1   0 2j3   0 2j5   0 2j7   0   0
3   0 3j2   0   0   0   0   0 3j8   0
0 4j1   0   0   0 4j5   0   0   0 4j9
0   0 5j2   0 5j4   0 5j6   0 5j8   0
0 6j1   0   0   0 6j5   0   0   0   0
7   0 7j2   0   0   0   0   0 7j8   0
0   0   0 8j3   0 8j5   0 8j7   0   0
0   0   0   0 9j4   0   0   0   0   0

TODO: define a function (analogous to q:) to factorize numbers in terms of these complex unique factors

# Ruminations

The body of literature on this subject seems to be best found by searching for "Gaussian Integers" and/or "Gaussian Primes". My main departure from that approach is restricting my consideration to the first quadrant. Regular prime numbers (where the domain is solely positive integers) are called "Rational Primes" for contrast.

From my point of view, the only prime factors of one of these primes is 0j1 and itself. However, because 1 (0j1^4) may be included arbitrarily many times (just as it may be with regular primes) it's important to be careful when making statements about these primes.

On the other hand, you can't just ignore the term 0j1 as you can with 1 in the context of regular integers. Or rather, if you do, you wind up with four times as many primes as are really needed. From my point of view, the terms 0 and 0j1 deserve special care in the context of factorizations (to keep things simple), and I'm happy to call them unique factors instead of primes. But I'm uncomfortable stating that 0j3, _3 and 0j_3 primes when they can be expressed as the product of sequences containing only 3 and (multiple copies of) 0j1.

That aside, the external literature sheds quite a bit of light on this subject. For example, a rational prime y is also a gaussian prime if (and only if) 3 = 4 | y. This follows from Fermat's theorem on sums of two squares.

Gaussian Primes at MathWorld
Gaussian integers at Wikipedia
Eisenstein primes A concept somewhat analogous to Gaussian Primes, but based on the third root of 1 (which might prevent factorizing negative integers, except that negative 1 is given special treatment such that the negative of a prime number is also considered prime) rather than on the square root of _1.

## Commentary

You can use @SIG@ to sign your comments. This section is possibly temporary(?).

• "Pseudo" in the page title is mis-spelled. -- RogerHui 2005-10-16 21:22:23

• "(Pseudoprime)" is already a widely recognised and well-defined mathematical term, so I think 0j1 etc. need to be called something else, especially as the idea of "primes" is linked with that of unique factorisation. As you are trying to split the hydrogen atom 1, "quark" would be a cute name, at least for the _0.5j0.866025 underlying the Eisenstein integers (the origin of the term being "three quarks for Muster Mark" - Finnegan's Wake). Sorry for veering off topic, but at least this section is possibly temporary!-- EwartShaw 2005-10-16 23:31:23

• Oops, sorry about the mis-spelling. Assuming we can come up with some acceptable name for relatively prime primitive factors, how should we go about renaming this page? -- Raul Miller 2005-10-17 03:48:07

• How about calling them "Primoids"? These were hideous mutant creatures, and were similarly only finally named in the end-credits (google for inferno primoids).-- EwartShaw 2005-10-18 10:21:00

• Actually, I've been leaning towards "Unique Factors" for things like _1 and 0, and "Unique Factorizations" for the essay as a whole. This might require I change some of the grammar, but the whole thing could probably do with an overhaul. -- Raul Miller 2005-10-18 13:07:30

Essays/UniqueFactors (last edited 2008-12-08 10:45:39 by anonymous)