Prime Factorization of the Real Numbers | Hacker News Reader

Prime Factorization of the Real Numbers

scrollto.com

2 pointsgoldenkey7 comments

This is a function defined in the real numbers (that are not 0? positive?), but it's not a prime factorization. (Never mind a "unique canonical" factorization as the original title says.)

To define an extension of a well known function it's important that it preserve as much of the original properties as possible. This is an informal requirement, and one of the dark secrets of math is that the definitions are made up and are only a social construct. [1] But after a few years in math you get a good sense of what is a good extension and what is a bad extension. This is a bad extension.

One of the most important properties of the prime factorization is that it behaves good with multiplication. i.e. if

  A = 2^x * 3^y * 5^z
  B = 2^p * 3^q * 5^r

then

  A * B = 2^(x+p) * 3^(y+q) * 5^(z+r)

and this extension doesn't have this property. For example:

  2 = "2^1 ; 3^0 ; 5^0"
  2.5 = "2^(1/2) ; 3^(1/2) ; 5^0"
  2 * 2.5 = 5 = "2^0 ; 3^0 ; 5^1"
              ≠ "2^(1+1/2) ; 3^(1/2) ; 5^0"

---

It is useful to compare it with a good extension. (This is also not standard.) You can define a "prime factorization" of the rational numbers if you allow negative exponents, so the "prime factorization" is the difference between the numerator and the denominator. (this is good, even for the multiple ways to write a fraction)

  2 = 2^1 * 3^0 * 5^0
  2.5 = 2^(-1) * 3^0 * 5^1
  2 * 2.5 = 5 = 2^0 * 3^0 * 5^1
              ≠ 2^(1-1) * 3^0 * 5^(0+1)

IIRC this is not a standard construction, but there are some similar construction like the p-adic order https://en.wikipedia.org/wiki/P-adic_order

I think that this can even be extended to some irrational numbers like

  sqrt(2) = 2^(1/2) * 3^0 * 5^0

but I should check the details. To extend this to all the (positive) real numbers I think it is necessary to use a non numerable base, or something as nasty as that, but this would be far away from a unique and canonical definition.

[1] https://en.wikipedia.org/wiki/Natural_number#Notation

I thank you for the goodies that I will look into. I guess its just a pairing function using the primes .. a decomposition. Guess I oversold it.

But be aware that your tuple for 2.5 is wrong. Sqrt(6) isn't even 2.5.

In[389]:= CanonicalRealFactorization[2.5]

Out[389]= <|2 -> 0.44966, 3 -> 0.55034|>

What you probably aim for is a UFD domain. I'll definitely investigate your links. Thank you!

[1] https://en.wikipedia.org/wiki/Unique_factorization_domain

[sorry for the delay]

UPS. I totally missed the log in the definition. My example of 2.5 is wrong (slightly wrong :))

Anyway, the proposed factorization of 2.5 is something that involves only 2 and 3, but if you multiply it by 2 then magically a 5 appears. So the main problem is still there.

I think that a UFD is not a structure similar to your idea, in particular it doesn't use fractional exponents.

My idea was to use R as a Q-vector space and use the base {log(2); log(3); log(5); log(7); log(11); ...}, but to complete this base you must use the Axiom of Choice, so you get a lot of crazy values, not only the logarithm of the primes. Then the idea is to use this base to express the logarithm of the number.

For example, if x=12 then log(12) = 2 * log(2) + 1 * log(3) that is equivalent to 12 = 2^2 * 3. This construction provides good values for sqrt(2), 1/6 and other simple algebraic numbers. The problem is that if you pick something like pi, you get a decomposition that is not very meaningful.

Right - the error is still present despite your mistake. I understand that I wrote a poor extension. I see what you are doing with the logs, but how do we know that all irrationals and reals are targeted by the log basis - and I think you mention it with regard to pi -- won't we end up with an infinite number of basis elements / factors? I don't want an infinite factorization for reals with a finite komogorolov complexity - there must be a way to get a basis that is finite for reals that have finite descriptions (yet infinite digits.) Because nomatter what, the reals that have infinite descriptions will only be provably factorized by AC, not actually factorized in a tangible sense. And those cases are less interesting to me because I want the utility more for practical investigation of number theory, not the 10th lemma in a non constructive proof.

Just to clarify, each number will have a finite "factorization" using the decomposition in the basis of the Vector Space. The problem is that the base is so big that it is not very meaningful.

To allow an infinite decomposition you must add a topology or a metric to the space, so there is possible to define a convergence of the infinite sum. This are for example https://en.wikipedia.org/wiki/Schauder_basis and https://en.wikipedia.org/wiki/Hilbert_space#Orthonormal_base... . They are not basis in the Vector Space sense, they are an extension. :)

The usual metric doesn't play nice with factorization, so the problem is to choose the right metric. There is s standard trick to use the p-adic order in rationals, but I'm not sure if something similar is defined for multiple primes (It should be possible.) But if you try to complete the rationals with the new metric, you don't get the real numbers, you get a different set.

One recommendation is to think first were are you going to use the new definition/extension. There are just to many form to extend a definition, but it's very difficult to choose the right one (whatever it means). If you know where you are going to use it, you can try to make a tradeoff to get something similar enough to the old definition and something big enough to include more interesting cases.

I'm thinking the only reason this is difficult is because we don't have prime-based formulas for all the interesting reals we care about enough to name. That makes this a lifelong quest to solve but probably other things need to be tackled first in order to make way for it. Thoughts?

Probably you need 3 or 4 semesters of Algebra classes in the university to understand the details. I'll try to explain the main ideas, but this is not my specialization so I don't remember the details :(. Too much Analysis in my life...

A possible way to extend the integer is to consider the Gaussian Integers, that are the numbers a+bi, where a and b are integers and i^2=-1. https://en.wikipedia.org/wiki/Gaussian_integer They have an unique factorization and primes. Some of the normal primes are still primes, for example 3, 7, ... and some of the normal primes are split, foe example 5 = (2+i) * (2-i) . Now 2+i and 2-i are the new primes. Anyway, you still have primes and unique factorization and can live happily there.

Another extensions are a+b.i.sqrt(d) aka Z[sqrt(-d)]. In the case d=2 and d=3 you still have primes and unique factorization. But if you consider d=5 or more, you don't have primes or unique factorization (see for example https://math.stackexchange.com/questions/1141412/mathbb-z-sq... , d=14 is apparently also a good value to get easy examples)

But this examples are extensions of the integer numbers in the complex numbers. You can make similar examples with the real version, i.e. the numbers a+b.sqrt(d) aka Z[sqrt(d)] I tried to use google to find an example of where there is no unique factorization, but I failed. I suspect that perhaps there is an easy way to proof that all of them but I didn't find it now and I'm too lazy to try to prove it. I'm not sure.

Anyway, when you add more roots, you have more problems. You can use the numbers a+b.cubicroot(d)+c.cubicroot(d^2) and try to analyze if they have unique factorization. This is related for example to the proof of the Last Fermat Theorem. The idea is to extend the integers to some more general set of numbers, and if you assume that there are primes and unique factorization the proof is not very difficult. For small exponents the extension use only square roots or cubic roots and it's not too difficult. But for big exponents the idea of unique factorization of the extended numbers fails. Try to look at the history part of https://en.wikipedia.org/wiki/Fermat%27s_Last_Theorem

So ... I don't remember the details now, but I suspect that for a general (algebraic) number it is not possible to have a good generalization of primes.

Reply on news.ycombinator.com