6
$\begingroup$

On the upcoming test I will be given a problem of type:

Find all normal subgroups $H$ in $F_n$ such that $F_n/H \cong G$.

Here $n$ is a small integer, likely 2 or 3, and $G$ is an Abelian group given as product of some cyclic groups.

Question: is there a more-or-less routine algorithm for such problems?

I do know an approach. I count two parameters: the number of epimorphisms $\#(F_n \twoheadrightarrow G)$ and the number of automorphisms $\#Aut(G)$. The answer then is $\frac{\#(F_n\twoheadrightarrow G)}{\#Aut(G)}$. This solution is based on the following facts: 1) every normal subgroup is a kernel of some homomorphism; 2) $F_n/Ker\,\phi \cong G$ if $\phi$ is an epimorphism; 3) $Ker\,\phi=Ker\,\psi$ iff $\psi = \alpha\circ\phi$ for some $\alpha \in Aut(G)$.

The problem is, very often I'm not sure how do I count one or both of these parameters. I could go through all homomorphisms and automorphisms manually, but the numbers in problem are usually too large.

Here are some cases to show how big numbers might be on the actual test. No need to solve them!

  1. $n=3$, $G=\mathbb Z_{13}^{3}$
  2. $n=3$, $G=\mathbb Z_{10}^3\times \mathbb Z$
  3. $n=3$, $G=\mathbb Z_{70}\times \mathbb Z_{30} \times \mathbb Z_{15}$
  4. $n=2$, $G=\mathbb Z_2 \times \mathbb Z_3 \times \mathbb Z_5$
  5. $n=3$, $G=\mathbb Z_{55} \times \mathbb Z_{7} \times \mathbb Z_{77}$
  6. $n=3$, $G=\mathbb Z_{75} \times \mathbb Z_{375} \times \mathbb Z_{125} \times \mathbb Z_{333}$
$\endgroup$
2
  • $\begingroup$ The first two are easy. There is just one such normal subgroup in the first case, namely $[F,F]F^{13}$, and in the second case there are no such $H$, because $G$ is a 4-generator group. Example 4 is also relatively easy, although (according to Magma) there are $72$ such $H$ There will be many more $H$ in the other cases. $\endgroup$
    – Derek Holt
    Oct 29, 2020 at 8:09
  • $\begingroup$ Update: I learned that I personally will not be given this type of problem on my test. Since I'm quite busy with revising everything else, I am not able to read through the given answers, so it will take time for me to determine the best one. Still, thank you all very much, and sorry $\endgroup$
    – dnes
    Nov 1, 2020 at 20:59

2 Answers 2

4
$\begingroup$

To justify your approach you need one more fact:

  • 4: the stabilizer of an epimorpism $F_n \to G$ with respect to the action of $\text{Aut}(G)$ is trivial.

All the groups $G$ are abelian, and to my mind the cleanest way to work with a finite abelian group is to factor it as the product of its $p$-torsion subgroups

$$A \cong \prod_p A_{(p)}$$

(equivalently, its Sylow $p$-subgroups). This is because of the following additional facts, which I'll leave as exercises:

  • 5: $\varphi : F_n \to A$ is an epimorphism iff the projection to each $p$-part $F_n \to A_{(p)}$ is an epimorphism.
  • 6: $\text{Aut}(A) \cong \prod_p \text{Aut}(A_{(p)})$.

This implies that the number $f_n(A) = \frac{|\text{Epi}(F_n, A)|}{|\text{Aut}(A)|}$ satisfies $f_n(A) = \prod_p f_n(A_{(p)})$ which reduces the problem in general to the problem for finite abelian $p$-groups (except for #2 where $A$ is infinite, but in #2 there are no epimorphisms, as you can see by tensoring with either $\mathbb{F}_2$ or $\mathbb{F}_5$).

If $A \cong C_p^k$ is elementary abelian (which occurs in #1, #3, #4, and #5) and $n < k$ then there are no epimorphisms $F_n \to A$. If $n \ge k$ every epimorphism $F_n \to C_p^k$ factors canonically through $C_p^n$ so it suffices to count epimorphisms $C_p^n \to C_p^k$. By taking vector space duals, this is equivalent to counting monomorphisms $C_p^k \to C_p^n$, and the standard argument involving picking one vector at a time gives that there are

$$(p^n - 1)(p^n - p) \dots (p^n - p^{k-1})$$

such epimorphisms, hence

$$f_n(C_p^k) = \frac{(p^n - 1)(p^n - p) \dots (p^n - p^{k-1})}{(p^k - 1) \dots (p^k - p^{k-1})} = {n \choose k}_p$$

which is a $q$-binomial coefficient for $q = p$. This occurs because we are counting subspaces of $C_p^n$ whose dimension is $n-k$ (so whose quotient is isomorphic to $C_p^k$), which gives an alternative argument for this count. This is a bit overkill for the small values of $n$ and $k$ occurring here but you asked for a routine algorithm and this will work no matter how big $n$ and $k$ get!

This handles every problem except #6 at the primes $p = 3, 5$, where we have $A_{(3)} \cong C_3^2 \times C_9$ and $A_{(5)} \cong C_{25} \times C_{125}^2$. I don't know how this goes off the top of my head but a modification of the above argument should work. For starters, every epimorphism from $F_n$ to one of these groups factors through $C_{p^k}^n$ where $p^k = 9, 125$ respectively. You may want to first work $\bmod p$ and then try to lift to $p^k$.

This may or may not have been the intended approach. An alternative is to argue that every epimorphism $F_n \to A$, for $A$ any abelian group, factors through the abelianization $\mathbb{Z}^n$, then try to count subgroups of $\mathbb{Z}^n$ with quotient isomorphic to $A$ using Smith normal form.

$\endgroup$
1
  • 1
    $\begingroup$ I think your second method will be much more efficient, but to enumerate subgroups of an abelian group, you want the Hermite Normal Form rather than the Smith Normal Form. $\endgroup$
    – Derek Holt
    Oct 29, 2020 at 8:37
1
$\begingroup$

Of the problems that you mention, I think that only the first two, which you can do in your head, are suitable for an exam. As I said in my comment, Example 4 is relatively easy, but even then there are $72$ distinct subgroups $H$, and it would not be reasonable to expect you to enumerate them by hand in a test.

Magma has a function for enumerating subgroups of a finite abelian group using the Hermite Normal Form for the generating sets of the subgroups, and I used this on Example 3. (This is essentially the second method proposed by Qiaochu Yuan in his answer.)

The group $G$ in Example 3 has exponent $210$, so all of the subgroups that we are looking for contain $[F_3,F_3]F_3^{210}$, and we are looking for those subgroups $N$ of the finite abelian group ${\mathbb Z}_{210}^3$ with quotient $G$.

Unfortunately the Magma function has no facility for looking for subgroups of a specific order (I wrote the code for the function, and I might consider adding that as an option), and so there was no alternative but to find all subgroups, and there are $332595$ of these.

Of these $5187$ have the required order and quotient group $G$.

In example 5 there are $235011$ subgroups $H$, and I am afraid Example 6, in which $G$ has exponent $41625 = 3^2\cdot 5^3\cdot 37$ is beyond the scope of the software!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.