Essays/UniqueFactors

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.

See also

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. -- Roger Hui <<DateTime(2005-10-16T21:22:23Z)>>

• "(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 $\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!-- Ewart Shaw <<DateTime(2005-10-16T23:31:23Z)>>

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

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

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