Finding number of automorphisms for Z/nZ^*

[jackmell]

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

 

[suremarc]

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.

 

[jackmell]

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

 

[suremarc]

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

Indeed, that is correct. With that much, you could probably figure out your question (1) by following through the steps in the calculation.

 

[micromass]

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

So if we have $G = \mathbb{Z}_{p^k}$. Then $e_1 = k$, $d_1 = 1$ and $c_1 = 1$. Hence
$$\prod_{k=1}^1 (p^{d_k} - p^{k-1} ) = (p-1)$$
$$\prod_{j=1}^1 (p^{e_j})^{n-d_j} = p^{k-1}$$
$$\prod_{i=1}^1 (p^{e_i-1})^{n-c_i +1} = 1$$
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
$$\prod_{k=1}^2 (2^{d_k} - 2^{k-1} ) = (2^1 - 2^0)(2^2 - 2^1) = 2$$
$$\prod_{j=1}^2 (p^{e_j})^{n-d_j} = (2^1)^{2-1} (2^2)^{2-2} = 2$$
$$\prod_{i=1}^2 (p^{e_i-1})^{n-c_i +1} = (2^0)^{2} (2^1)^{1} = 2$$
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.

 

[jackmell]

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.

 

[jackmell]

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