Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Commutative Monoid and some properties

  1. Aug 19, 2011 #1
    For reference, let [itex]\mathbb N^{\infty}[/itex] denote the set of all [itex]\infty[/itex]-tuples of the form [itex](n_{1}, n_{2}, \dots)[/itex] with [itex]n_{i}\in \mathbb N ,\,\forall i[/itex], and let [itex]\mathbb N^{*}=\{1,2,3,\dots\}[/itex].

    Let [itex]n\in\mathbb N^{*}[/itex]. Then by the Fundamental Theorem of Arithmetic, we can represent [itex]n[/itex] as a unique factorization of primes. That is [tex]n=p_{1}^{e_{1}} p_{2}^{e_{2}}\cdots=\prod_{k=1}^{\infty} p_{k}^{e_{k}}.[/tex] Define a function [itex]\phi :\mathbb N^{*} \to \mathbb N^{\infty}[/itex] such that [itex]\phi(n)=(e_{1},e_{2},\dots)=(e_{k})_{k=1}^{\infty}[/itex]. Further, define a binary operation [itex]\oplus:\mathbb N^{\infty}\times\mathbb N^{\infty}\to\mathbb N^{\infty}[/itex] such that [tex]\oplus((a_{1},a_{2},\dots),(b_{1},b_{2},\dots))=(a_{1}+b_{1},a_{2}+b_{2},\dots).[/tex]

    I will now show that [itex](\mathbb N^{\infty},\oplus)[/itex] is a commutative monoid.
    • Let [itex]u,v\in\mathbb N^{\infty}[/itex] with [itex]u=(a_{k})_{k=1}^{\infty}[/itex] and [itex]v=(b_{k})_{k=1}^{\infty}[/itex]. Then [itex]u\oplus v=(a_{k}+b_{k})_{k=1}^{\infty}=(b_{k}+a_{k})_{k=1}^{\infty}=v\oplus u[/itex]. Since [itex]a_{k}+b_{k}=b_{k}+a_{k}\in\mathbb N,\,\forall k[/itex], it follows that [itex]u\oplus v=v\oplus u\in\mathbb N^{\infty}[/itex]. So [itex](\mathbb N^{\infty},\oplus)[/itex] is both closed and commutative, as required.

    • Let [itex]u,v,w\in\mathbb N^{\infty}[/itex] with [itex]u=(a_{k})_{k=1}^{\infty}[/itex],[itex]v=(b_{k})_{k=1}^{\infty}[/itex] and [itex]w=(c_{k})_{k=1}^{\infty}[/itex]. Then [itex](u\oplus v)\oplus w=((a_{k}+b_{k})+c_{k})_{k=1}^{\infty}=(a_{k}+(b_{k}+c_{k}))_{k=1}^{\infty}=u\oplus (v\oplus w)[/itex]. Thus [itex](\mathbb N^{\infty},\oplus)[/itex] is associative.

    • Let [itex]1_{\mathbb N^{\infty}}\in\mathbb N^{\infty}[/itex] such that [itex]1_{\mathbb N^{\infty}}=(0,0,\dots)[/itex]. Then for any [itex]u=(a_{k})_{k=1}^{\infty}\in\mathbb N^{\infty}[/itex], we have [itex]1_{\mathbb N^{\infty}}\oplus u=(0+a_{k})_{k=1}^{\infty}=(a_{k})_{k=1}^{\infty}=(a_{k}+0)_{k=1}^{\infty}=u\oplus 1_{\mathbb N^{\infty}}[/itex]. Thus, [itex]1_{\mathbb N^{\infty}}[/itex] is the identity element of [itex](\mathbb N^{\infty},\oplus)[/itex].

    Thus, [itex](\mathbb N^{\infty},\oplus)[/itex] is a commutative monoid.

    Now I will show that [itex]\phi[/itex] is a commutative monoid homomorphism.

    • Let [itex]a,b\in\mathbb N[/itex]. Then by the Fundamental Theorem of Arithmetic, both [itex]a[/itex] and [itex]b[/itex] have a unique factorization of primes. That is [itex]a=\prod_{k=1}^{\infty} p_{k}^{e_{k}}[/itex] and [itex]b=\prod_{k=1}^{\infty} p_{k}^{f_{k}}[/itex]. Then [itex]ab=\prod_{k=1}^{\infty} p_{k}^{e_{k}+f_{k}}[/itex]. So we have [itex]\phi (ab)=\phi (\prod_{k=1}^{\infty} p_{k}^{e_{k}+f_{k}})=(e_{k}+f_{k})_{k=1}^{\infty}=(e_{k})_{k=1}^{\infty}\oplus (f_{k})_{k=1}^{\infty}=\phi(a)\oplus\phi(b)[/itex], as required.

    An interesting result to is to show that [itex]\phi[/itex] is actually a commutative monoid isomorphism. I leave this up to the reader.[EDIT: THIS IS INCORRECT IF WE'RE WORKING WITH [itex]\mathbb N^{\infty}[/itex]]

    I've been messing around with this, and you can get some pretty cool new operations on numbers. Now that they are "basically" vectors, you can start making new operations like dot product, tensor product, their 'length' with respect to different norms. My favourite so far has been showing a homomorphism from [itex]\mathbb N^{\infty}\to\mathbb P[x]^{\infty}[/itex], the set of all polynomials with one variable. Once this is done, you can create a new binary operation such that you take two numbers from [itex]\mathbb N^{*}[/itex], convert both separately by [itex]\phi[/itex] to [itex]\mathbb N^{\infty}[/itex], then to [itex]\mathbb P[x]^{\infty}[/itex], and do normal polynomial multiplication, then convert that polynomial all the way back to [itex]\mathbb N^{*}[/itex].

    I also feel (severely speculative), if you can figure out some way with all these new operations to define a homomorphic addition within [itex]\mathbb N^{\infty}[/itex], we could find a simpler solution to Fermat's Last Theorem.

    You can also play around with it more finitely, which I can explain a bit later, but my fingers are tired from typing.

    If you have input, or come up with your own results, or have criticisms, please contribute! I would like to see if these definitions bring out anything cool.
     
    Last edited: Aug 19, 2011
  2. jcsd
  3. Aug 19, 2011 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    This is false. [itex]\phi[/itex] is not surjective. For example (1,1,1,1,...) is never reached.

    You might be interested in http://en.wikipedia.org/wiki/Supernatural_numbers :smile:
     
  4. Aug 19, 2011 #3
    geez, I wish I had seen that before typing all that up.

    An isomorphism would exist if you worked in [itex]\mathbb Z_{p}[/itex] instead? That is, pick a prime [itex]p[/itex], and for all primes [itex]1<p_{1}<p_{2}<\cdots<p_{n}=p[/itex], we can define an isomorphism [itex]\phi:\mathbb Z_{p}\to\mathbb Z_{p}^{n}[/itex] such that if [itex]a\in\mathbb Z_{p}[/itex] then [itex]\phi(a)=(e_k)_{k=1}^{n}[/itex] where [tex]a=\prod_{k=1}^{n}p_{k}^{e_{k}}.[/tex] Wouldn't [itex]\phi[/itex] even be a commutative group isomorphism?

    Maybe I even want [itex]p_{n}<p[/itex]? I have to think about this more and make it more rigourous.

    Thank you for the link though!
     
  5. Aug 19, 2011 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    You mean to say [itex]\mathbb{Z}_p^*\rightarrow \mathbb{Z}_p^n[/itex], right?? Well, that could work. I suggest you try to prove it!

    In general, something that might work is [itex]\mathbb{N}^{(\infty)}[/itex]: that are all the tuples [itex](n_1,n_2,n_3,...)[/itex] such that only a finite number of terms are nonzero. You'll have better luck proving that an isomorphism.

    Also, there is no need to work with [itex]\mathbb{N}[/itex] for this. You can also do the same thing for [itex]\mathbb{Q}[/itex]. So we can define a map

    [tex]\mathbb{Q}^*\rightarrow \mathbb{Z}^{(\infty)}[/tex]

    This are some things you should ponder on. But the OP was verry interesting!
     
  6. Aug 19, 2011 #5
    Thanks for the help!

    And yes, I did mean [itex]\mathbb Z_{p}^{*}\to\mathbb Z_{p}^{n}[/itex]. That fixes the problem that caused me to ask if we should have [itex]p_{n}<p[/itex].

    I also want to give an example of what I meant with the polynomials. I don't want to type out the entire definition of the operation I'm going to use, but I hope the example gives light to it:

    [tex]6\otimes8\simeq(1,1,0,\dots)\otimes'(3,0,0,\dots) \simeq (1+x)(3)=3+3x\simeq(3,3,0,\dots)\simeq 2^{3}3^{3}=8\times 27=216.[/tex]

    This operation can also be shown to be commutative. However in this case, [itex](0,0,0,\dots)[/itex] acts as a 'absorbing' element, not unlike [itex]0[/itex] with respect to [itex](\mathbb Z,\cdot)[/itex].

    I haven't done any group theory or abstract algebra officially, this is all just what I'm starting to pull from Artin's Algebra. I really like it so far :)

    I'll also work on that isomorphism.

    Also, could that operation be used in cryptography?
     
  7. Aug 19, 2011 #6

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Hmmm, that polynomial thing is quite interesting. I've not yet encountered such a thing, but it reminds me in some way of group rings. It should be worth studying your operation in that context.
     
  8. Aug 19, 2011 #7
    The interesting part is that the 'product' of any two primes, results in another prime. I thought that was cool.
     
  9. Aug 21, 2011 #8
    Fix [itex]p[/itex] prime. We can define a function [itex]\parallel\cdot\parallel_{\phi_{p}}:\mathbb N^{*}\to\mathbb R[/itex] such that for all [itex]a\in\mathbb N^{*}[/itex], we have [tex]\parallel a\parallel_{\phi_{p}}=\,\parallel \phi(a)\parallel_{p}.[/tex] This can give us a sense of 'length' that each number has. For example: [tex]\parallel6\parallel_{\phi_{2}}=\,\parallel \phi(6)\parallel_{2}=\parallel (1,1,0,\dots)\parallel_{2}=\sqrt{2},[/tex][tex]\parallel 8\parallel_{\phi_{2}}=\,\parallel \phi(8)\parallel_{2}=\parallel(3,0,\dots)\parallel_{2}=3,[/tex]and[tex]\parallel 7\parallel_{\phi_{2}}=\,\parallel \phi(7)\parallel_{2}=\parallel (0,0,0,1,0,\dots)\parallel_{2}=1.[/tex]Note that [itex]6<7[/itex] but [itex]\parallel7\parallel_{\phi_{2}}<\parallel6\parallel_{\phi_{2}}[/itex].

    I've also thought about making an encryption algorithm changing letters to irreducible polynomials over [itex]\mathbb N^{*}[/itex] using my operation I defined in one of the earlier posts. You could even go further to making words map to matrices in RCF, or something like that. I know nothing about cryptography though ahahah.

    We can even make a sort of inner product of in [itex]\mathbb N^{*}[/itex] and fool around in there. For example, [tex]\langle6,8\rangle_{\phi}=\langle(1,1,0,\dots),(3,0,0,\dots)\rangle=3.[/tex]Note that we could show that all primes are orthogonal to one another.
     
    Last edited: Aug 21, 2011
  10. Aug 21, 2011 #9

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    What if you defined [itex]\mathbb{N}^\infty[/itex] as the set of all (countably) infinite sequences with only finitely many nonzero entries....
     
  11. Aug 21, 2011 #10
    micromass already mentioned that I believe, and I'm using that criterion for [itex]\mathbb N^{\infty}[/itex] in the paper I'm writing to show this to a professor of mine who I hope to help me push out some cool results.
     
  12. Aug 21, 2011 #11

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Argh, I completely missed that post when I skimmed the thread. :frown:
     
  13. Aug 21, 2011 #12
    No worries! I'm no less thankful for your input. Its something that allows a lot of this to hold, and I completely missed it when I was defining things originally. I've uploaded my paper so far, I'm adding and proof reading it as I go along and discover new things. I haven't added the new 'length' idea, nor the 'inner product' stuff.
     

    Attached Files:

  14. Aug 21, 2011 #13

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Interesting paper!!
    Allow me to make some remarks:

    - in Theorem 2, you can even show injectivity. So these things are a submonoid.
    - Prime factorizations exist over the rationals too, for example: 5/6=[itex]2^{-1}3^{-1}5[/itex]. So your map phi generalizes to
    [itex]\phi:\mathbb{Q}^*\rightarrow \mathbb{Z}^\infty[/itex]
    - There is a small problem with the definition after theorem 2. The thing [itex]\sum{a_kx^k}[/itex] is NOT a polynomial. Indeed, polynomials have only a finite amount of terms. However, it is a formal power series. So you need [itex]\psi[/itex] to go the the formal power series.
     
  15. Aug 21, 2011 #14
    Thank you very much micromass!

    If I generalize [itex]\phi:\mathbb{Q}^{*}\to\mathbb{Z}^{\infty}[/itex], does this not also give me a group?

    Also, if I define [itex]\mathbb{P}[X]^{\infty}[/itex] to be the single-variable polynomials with only a finite amount of nonzero coefficients, would this fix the problem arisen in your third point?
     
  16. Aug 21, 2011 #15

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Also, the thing you posted will not be a norm of course, since it won't satisfy it's properties. Here's something you can do to save it

    Let [itex]\Phi:\mathbb{Q}^*\rightarrow \mathbb{Z}^{(\infty)}:q\rightarrow (q_1,q_2,...)[/itex]

    For example [itex]\Phi(5/6)=(-1,-1,1,0,0,0,...)[/itex]

    Try to define a norm like

    [tex]\|q\|=\sum_{i=1}^{+\infty}{2^{-q_i}}[/tex]

    I guess this would define a norm if you also define [itex]\|0\|=0[/itex].
    My inspiration of course comes from the p-adic numbers...
     
  17. Aug 21, 2011 #16

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Yes, I believe so!

    Yes.
     
  18. Aug 21, 2011 #17
    I'm just confused here how my 'norm' doesn't work :(

    I'm just taking any [itex]n[/itex], bringing it to [itex]\mathbb{N}^{\infty}[/itex], and taking the Euclidean norm.

    I think you mean [itex]\|1\|=0[/itex], since [itex]0\notin\mathbb{Q}^{*}[/itex]
     
  19. Aug 21, 2011 #18

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Well, it might work. But you need to prove that
    [itex]\|\alpha x\|=|\alpha|\|x\|~\text{and}~\|x+y\|\leq \|x\|+\|y\|[/itex]

    No, I meant what I said. Of course 0 is not in there, but I put it in there. The reason is that we want to have a vector space, and 0 needs to be an element of the vector space.

    Of course, you don't NEED the norm properties, but it would be nice to have them....
     
  20. Aug 21, 2011 #19
    But wouldn't [itex]1[/itex] be the zero of the vector space since [tex]\Phi(1)=(0,0,\dots).[/tex] And by your norm, wouldn't [tex]\|1\|=\sum^{+\infty}_{i=1}2^{-q_{i}}=1+1+\cdots=+ \infty[/tex].

    Just to add too, if we are trying to get a vector space, then would the [itex]\oplus[/itex] generalized to [itex]\mathbb{Z}^{\infty}[/itex] be vector addition, and exponentiation in [itex]\mathbb{Q}^{*}[/itex] be the scalar multiplication?
     
  21. Aug 21, 2011 #20

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    That's nice, but I doubt that this will give you an actualy vector space...
    Remember that a vector space must be defined over a field. So I'm not sure what your scalar multiplication will be?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook