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

Finding number of automorphisms for Z/nZ^*

  1. May 15, 2015 #1
    Hi,

    I'm studying Abstract Algebra and was wondering if someone could help me understand a formula for computing ##\big|\operatorname{aut} \mathbb{Z}_n^{*}\big|## using a formula described in this reference:http://www.msri.org/people/members/chillar/files/autabeliangrps.pdf

    Here is the basic formula. I don't understand:

    (1) the definitions for ##c_k## and ##d_k##,
    (2) if the formula is referring to the same ##p## or the prime factors of ##n##, and
    (3) how Sylow p-subgroups are related to this problem although I realize a finite abelian group is equal to a direct product of distinct Sylow p-subgroups as in the example below.

    Given ##\mathbb{Z}_n^{*}=\mathbb{Z}_{p_1^{e_1}}\times \mathbb{Z}_{p_2^{e_2}}\times\cdots\times \mathbb{Z}_{p_n^{e_n}}##,
    define the following ##2n## numbers:
    ##\begin{align*} d_k=\operatorname{max}\{l:e_l=e_k\}\\
    c_k=\operatorname{min}\{l:e_l=e_k\}
    \end{align*}
    ##

    then:
    ##
    \big|\operatorname{aut} \mathbb{Z}_n^{*}\big|=\prod_{k=1}^n p^{d_k}-p^{k-1}\prod_{j=1}^n \left(p^{e_j}\right)^{n-d_j}\prod_{i=1}^n \left(p^{e_i}-1\right)^{n-c_i+1}
    ##

    For example, I know ##\mathbb{Z}_{100}^*\cong \mathbb{Z}_{2^2}^*\times\mathbb{Z}_{5^2}^*\cong\mathbb{Z}_2\times \mathbb{Z}_{20}## and that ##\big|\operatorname{aut}\mathbb{Z}_{100}^*\big|=32##. Could we perhaps go over the formula for this example? Also, I think this is also related to Sylow p-subgroups and I know the two Sylow p-subgroups for this group is ##S_2=\{1,7,43,49,51,57,93,99\}##, and ##S_5=\{1,21,41,61,81\}##.

    I'd like to find the size of the first 500 and wrote a routine to find them using another way and I'd like to check my results with the formula above.

    Ok thanks for reading,
    Jack
     
    Last edited: May 15, 2015
  2. jcsd
  3. May 15, 2015 #2
    I'd have to think about (1) some more. As for the other two:
    • (2) ##p## is fixed. The formula that the author gives describes the number of endomorphisms of each ##H_p## because ##|Aut(G)|## can be recovered from the product ##\prod |Aut(H_p)|##, as the orders of each ##H_p## are pairwise coprime. (Note that ##n## is the number of cyclic p-groups in the product for the Sylow p-subgroup; therein lies your misinterpretation of the formula.)
    • (3) I suppose Sylow p-subgroups aren't related per se, but factorizing groups in this manner is useful because (a) it suffices to consider the Sylow p-subgroups individually, and (b) Sylow p-subgroups have a convenient linear representation, which--voilà--turns the problem into a linear algebra problem, thus making it easier to deal with.
     
  4. May 16, 2015 #3
    Thanks marc,

    I need to more review the article I suppose too; bit tough for me though as it's at the limit of my familiarity with the subject. Just seems there should be a better explanation of that formula (with some good examples) so beginners like me could follow it. This morning I calculated ##\big|\operatorname{aut}\mathbb{Z}_{455}^*\big|=73728##. Just seems like a lot although it is unusual in that the group elements are low-ordered. Not sure the number is correct though so that's why I'd like to check it another way. The number is possible however since ##\mathbb{Z}_{455}^*\cong \mathbb{Z}_4\times\mathbb{Z}_6\times \mathbb{Z}_{12}## and if I choose generators ##\big<(1,0,0),(0,1,0),(0,0,1)\big>## and compute the orders of each element in the product, I get 24 order 4 elements, 56 with order 6 and 192 of order 12 for a total of 258, 048 possible assignments (actually 256, 704 since they need to be distinct).

    I should focus solely on the article here and not the computations:

    I think I'm min-understanding some things:

    First, I think the group ##G## is not equal to ##H_p## but rather a product of ``groups'', ##H_{p_i}## for it's prime divisors of the group order. Take for example ##\mathbb{Z}_{100}^*\cong\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_5## and therefore ##\mathbb{Z}_{100}^*\cong H_2\times H_5##
    where ##H_2=\mathbb{Z}_2\times\mathbb{Z}_2\times\mathbb{Z}_2## and ##H_5=\mathbb{Z}_5## and therefore we would need to use the formula twice, once for ##H_2## and then again for ##H_5## and then since they're co-prime, the total automorphisms is simply the product of these values.

    Could someone confirm for me that I have this part right? If so, then I think I can figure out the rest of the paper?

    Ok thanks,
    Jack
     
    Last edited: May 16, 2015
  5. May 16, 2015 #4
    Indeed, that is correct. With that much, you could probably figure out your question (1) by following through the steps in the calculation.
     
  6. May 16, 2015 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    So if we have ##G = \mathbb{Z}_{p^k}##. Then ##e_1 = k##, ##d_1 = 1## and ##c_1 = 1##. Hence
    [tex]\prod_{k=1}^1 (p^{d_k} - p^{k-1} ) = (p-1)[/tex]
    [tex]\prod_{j=1}^1 (p^{e_j})^{n-d_j} = p^{k-1}[/tex]
    [tex]\prod_{i=1}^1 (p^{e_i-1})^{n-c_i +1} = 1[/tex]
    So the order of the automorphism group is ##p^k (p-1)## (which is exactly ##\phi(p^k)## http://en.wikipedia.org/wiki/Euler's_totient_function#.CF.86.28pk.29_.3D_pk_.E2.88.92_pk.E2.88.921_.3D_pk.E2.88.921.28p_.E2.88.92_1.29)

    For your example, we know that ##\mathbb{Z}_{20}\cong \mathbb{Z}_{2^2} \times \mathbb{Z}_5##. So ##\mathbb{Z}_{100}^* \cong \mathbb{Z}_{2}\times \mathbb{Z}_{2^2}\times \mathbb{Z}_5##.
    It suffices to find the orders of the automorphism groups of ##\mathbb{Z}_{2}\times \mathbb{Z}_{2^2}## and ##\mathbb{Z}_5##. The order of the latter is ##4## by the formula above. For the order of the former, we apply the formula in the paper with ##e_1 =1##, ##e_2 = 2##, ##d_1 =1##, ## d_2 = 2## and ##c_1 = 1##, ##c_2 = 2##. So
    [tex]\prod_{k=1}^2 (2^{d_k} - 2^{k-1} ) = (2^1 - 2^0)(2^2 - 2^1) = 2[/tex]
    [tex]\prod_{j=1}^2 (p^{e_j})^{n-d_j} = (2^1)^{2-1} (2^2)^{2-2} = 2[/tex]
    [tex]\prod_{i=1}^2 (p^{e_i-1})^{n-c_i +1} = (2^0)^{2} (2^1)^{1} = 2[/tex]
    So the order of the automorphism group of ##\mathbb{Z}_{2^2} \times \mathbb{Z}_{2^2} = 8##. So the order of the automorphism group of ##\mathbb{Z}_{100}^*## is ##8\cdot 4 = 32##.

    The Sylow subgroups are obviously related here, since the Sylow subgroups of ##\mathbb{Z}_{2}\times \mathbb{Z}_{2^2}\times \mathbb{Z}_5## are exactly the two parts ##\mathbb{Z}_{2}\times \mathbb{Z}_{2^2}## and ##\mathbb{Z}_5##. This holds in general. So at the start of the problem, you always split the problem up in the Sylow subgroups.
     
  7. May 16, 2015 #6
    I Ok thanks Micormass. I think I have it now:

    $$\begin{align}\mathbb{Z}_{455}^*&\cong \mathbb{Z}_5^*\times \mathbb{Z}_7^*\times \mathbb{Z}_{13}^* \\
    &\cong \mathbb{Z}_4\times\mathbb{Z}_6\times \mathbb{Z}_{12}\\
    &\cong \left(\mathbb{Z}_2\times\mathbb{Z}_{2^2}\times\mathbb{Z}_{2^2}\right)\times\left(\mathbb{Z}_3\times\mathbb{Z}_3\right)=G_2\times G_3
    \end{align}
    $$

    In the case of ##G_2## we have ##e_1=1,e_2=2,e_3=2## with ##d_1=1,d_2=3,d_3=3## and ##c_1=1,c_2=2,c_3=2## so that using the formula:

    ##\left|\operatorname{aut}G_2\right|=(2-1)(2^3-2)(2^3-4)(2^2)(4^0)(4^0)(1)(2^2)(2^2)=(6)(4)(4)(4)=1536##

    A similar calculation yields:

    ##\left|\operatorname{aut}G_3\right|=(3^2-1)(3^2-3)(3^0)(3^0)(3^0)(3^0)=48##

    and ##(1536)(48)=73728## which is the number I calculated by brute computations. I think that's right anyway. Wow! Never thought I'd be able to use this formula. Thanks guys! I'll spend more time with the underlying theory to better understand it.

    Note: I should point out for my benefit and others that the orders of ##G_2## and ##G_3## were relatively prime so that I could simply multiply the number of automorphisms between them to obtain the total automorphisms of the product.
     
    Last edited: May 16, 2015
  8. May 24, 2015 #7
    Just a quick follow-up: Some members in the Math software forum here helped me write Mathematica code to implement the isomorphism and automorphism calculations explained above. I encaplulated the code in a Manipulate so the user can just use a slider-bar to go through the isomorphisms for the first 500 groups. Here's the link:

    https://www.physicsforums.com/threa...at-isomorphic-expression.815056/#post-5118995
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Finding number of automorphisms for Z/nZ^*
  1. Natural numbers Z? (Replies: 6)

  2. Automorphisms of Z^2 (Replies: 2)

Loading...