# Finding number of automorphisms for Z/nZ^*

1. May 15, 2015

### 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.

Jack

Last edited: May 15, 2015
2. May 15, 2015

### 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.

3. May 16, 2015

### 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

Last edited: May 16, 2015
4. May 16, 2015

### suremarc

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

5. May 16, 2015

### micromass

Staff Emeritus
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.

6. May 16, 2015

### 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.

Last edited: May 16, 2015
7. May 24, 2015

### 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