# How does one enumerate $\mathrm{Aut}(G)$, or at least compute $|\mathrm{Aut}(G)|$?

I know that the automorphisms in $\mathrm{Aut}(G)$ preserve the order of elements of $G$, so if $G$ is partitioned according to $\mathrm{Ord}$ (order), the product of the cardinalities of the equivalence classes in $G/\mathrm{Ord}$ imposes an upper bound on the number of possible automorphisms of $G$. (This is so at least for finite $G$.)

For example, for $D_{12}$ (the dihedral group of order $12$) I count

• 1 element of order 1
• 7 elements of order 2
• 2 elements of order 3
• 2 elements of order 6

So, for $D_{12}$ the product described above is $1\cdot 7\cdot 2\cdot 2 = 28$.

But if $G$ is generated by $n < |G|$ elements then I'm tempted to say that only these elements should matter for the argument given above, and therefore, only the equivalence classes for these $n$ elements should appear in the product mentioned above. Thus, for example, since $D_{12}$ is generated by $n = 2$ elements, one (call it $\alpha$) of order $2$ and one (call it $x$) of order $6$, the product of the cardinalities of their $G/\mathrm{Ord}$ equivalence classes is $7 \cdot 2 = 14$.

In any case, $\mathrm{Inn}(G) \lhd \mathrm{Aut}(G)$, and therefore, I expect $|\mathrm{Inn}(D_{12})|$ to be a divisor of $|\mathrm{Aut}(D_{12})|$. Unfortunately, AFAICT, $|\mathrm{Inn}(D_{12})| = 6$, which is not a divisor of either of the numbers computed above ($28$ or $14$). (I count that the conjugacy classes of the generators $\alpha$ and $x$ have cardinalities $3$ and $2$, respectively; hence $|\mathrm{Inn}(D_{12})| = 3 \cdot 2 = 6$.)

The only way out I can see to avoid a contradiction is to conclude that the number computed by taking the product of cardinalities of classes in $G/\mathrm{Ord}$ provides only an upper bound $|\mathrm{Aut}(G)$. (I'm not at all convinced by argument, but I'm too tired at the moment to think of a watertight proof or refutation of it.)

I have several questions:

1. Where did my reasoning go wrong above?
2. Is there an algorithm for enumerating $\mathrm{Aut}(G)$ (or at least for computing $|\mathrm{Aut}(G)|$), at least for finite $G$?
3. I'd be interested in finding about tools/resources to facilitate these computations; they're rather tedious to do by hand. (Especially in cases where "pure reasoning" goes awry, as it did above, it'd be nice to have computational tools for independently confirming one's reasoning.)
• "Is there an algorithm for enumerating Aut(G) (or at least for computing |Aut(G)|), at least for finite G?" No. – Martin Brandenburg Jan 25 '14 at 11:47
• Why do you say that? There is certainly a naive algorithm for finite $G$: just look at all permutations of $G$ and check which are automorphisms. There are more practical algorithms that are used by programs like GAP and Magma. There are even algorithms for some classes of infinite groups - i.e. those for which the isomorphism problem is solvable. – Derek Holt Jan 25 '14 at 12:15

## 3 Answers

You claim that the product of the cardinalities of the sets of elements of each order gives an upper bound on the size of the automorphism group, but this is clearly wrong: take the Klein four group. Its automorphism group has six elements, but your proposed upper bound, $1 \cdot 3 = 3$, is too small. Wei Zhou gives the correct upper bound that arises form this reasoning, $1! \cdot 3! = 6$.

Your second bound is correct (but probably only because you have generators of different orders).

Another mistake is thinking that there are no positive integers less than 14 that are divisible by 6. In fact there are two: 6 and 12. The correct size is 12.

In your example $D_{12}$, there are 7 elements of order 2, so there are $7!$ permutations. So the upper bound of $|Aut(D_{12})|$ is $1!\cdot (7!)\cdot (2!) \cdot (2!)$.

I know for finite abelian group $G$, there are fomula for $|Aut(G)|$. But I dont know the general case.

The direct approach gives you the "product of factorials" bound. You can make it better by the following idea: let's call $g \in G$ $k$-divisible if there exists $h \not\in <g>$ such that $h^k=g$. Then the $k$-divisibility property also respects automorphisms and you can further divide your set of the elemets of fixed order to smaller subsets (and get the product of smaller factorials).

Another approach is to use conjugacy classes: the automorphism must permute conjugacy classes but usually they have different cardinalities.This approach can be useful for finding outer automorphisms because inner automorphisms preserves conjugacy classes. This works well for $S_n$ and $A_n$.