7
$\begingroup$

I have a question. I am supposed to prove the following theorem:

Let $n \in \mathbb{N}$ be a natural number.

Show that:

the number of nonisomorphic groups of order $n$ is less than or equal to $n^{n^2}$.

My reasoning:

A set $G$ is a group if it's equiped with a binary operation/map: $G\times G \rightarrow G, \space (g_1,g_2)\rightarrow g_1 \circ g_2$. Additionally two groups $G,H$ are isomorphic $G \cong H$ if there exists a isomorphism $f:G \rightarrow H$.

Now, for each such map $G\times G \rightarrow G$ we get a different group. Because there are $n^{n^2}$ such different maps (for $|G|=n$), the number of all possible different groups should be $\leq n^{n^2}$. And since we have different binary operations defined on the same set, we should get different multiplication (Cayley) tables, we would have $f(a)\star f(b)\neq f(a \circ b)$ for $a,b \in G$ and some bijection $f$ . Meaning that, since homomorphisms don't exist, all those different groups are nonisomorphic and we have therefore shown the above theorem to be true.

More intuitively:

The statement of beeing (non) isomorphic can be translated to (not) having the same multiplication table. If we have a group of order $n$, then the multiplication table should be of size $n\times n= n^2$. Each of the $n^2$ entries (in the table) has $n$ possible entries, representing a different choice of the above mentioned binary operation. Because those possibilities multiply, we would have: $n\times \cdots \times n=n^{n^2}$ and each table beeing different, those groups are nonisomorphic.

My question:

Is my reasoning, in both cases, correct? Am I missing something? How would I prove, more formally, that for different binary operations defined on the same set we get different nonisomorphic groups?

Related questions:

Number of distinct groups of order n upto isomorphism, for a fixed integer n.

The number of groups of order n(upto isomorphism)is

Comment: I am a physicist and don't have major ambitions in abstract algebra, please be nice.

$\endgroup$
12
  • 1
    $\begingroup$ Just considering multiplication tables works. It gives a very very weak upper bound. If you are trying to show two binary operations give nonisomorphic groups, you would have to show there is no isomorphism, which is much more complicated. $\endgroup$ Feb 5, 2020 at 22:59
  • 2
    $\begingroup$ You write that "all those different groups are nonisomorphic"... are you saying that if two groups have different multiplication tables they are not isomorphic? That's definitely not true... $\endgroup$ Feb 5, 2020 at 23:11
  • 2
    $\begingroup$ You only need to establish an upper bound here. It's enough to show that there is an injective mapping from the isomorphism classes to the set of $n \times n$ matrices with entries in $\{1,2, \ldots, n\}$. This is not a surjective mapping. $\endgroup$ Feb 5, 2020 at 23:13
  • 2
    $\begingroup$ It isn't very clear mathematical writing to say "the number of nonisomorphic groups of order $n \le n^{n^2}$" (because it looks like you are comparing $n$ with $n^{n^2}$ and you are not). You should say "the number of nonisomorphic groups of order $n$ is less than or equal to $n^{n^2}$, or "let $k$ be then number of nonisomorphic groups of order $n$, then $k \le n^{n^2}$". $\endgroup$
    – Rob Arthan
    Feb 5, 2020 at 23:18
  • 1
    $\begingroup$ I think a better upper bound would be $\frac{(n-1)^{(n-1)^2}}{(n-1)!}$ (here $0^0$ is set to be $1$). This is still a weak bound. $\endgroup$ Feb 6, 2020 at 0:45

2 Answers 2

4
$\begingroup$

You seem to be assuming that if the multiplication tables are different the groups are not isomorphic, but that is not true. What is true is that if the tables are the same the groups are isomorphic. Your argument that there are at most $n^{n^2}$ tables is correct, which shows that there are no more nonisomorphic groups than that.

You can do much better by noting that the table has to have each element once in each column of the table. As there are $n!$ possible columns there are at most $n!^n\approx \left(\left(\frac ne\right)^n\right)^n(2\pi n)^{n/2}$ nonisomorphic groups. For $n=10$ this is $4\cdot 10^{65}$ instead of $10^{100}$ and for $n=100$ it is about $10^{15797}$ instead of $10^{20000}$. Of course, you can do much better by considering that each row must also have one of each element, but I don't see a quick way to quantify that.

$\endgroup$
7
  • 1
    $\begingroup$ There is a small gain by considering that the row and column for the identity element don't have any freedom. So the $n$'s can be replaced by $n-1$'s. $\endgroup$
    – 2'5 9'2
    Feb 6, 2020 at 6:27
  • $\begingroup$ "...by considering that each row must also have one of each element..." So the table is an $n\times n$ reduced Latin square. There are upper bound formulas for the number of reduced Latin squares. $\endgroup$
    – 2'5 9'2
    Feb 6, 2020 at 6:45
  • $\begingroup$ @alex.jordan: Yes, it is a Latin square. Then you need associative as well. I don't know how to compute the first, even. $\endgroup$ Feb 6, 2020 at 6:47
  • $\begingroup$ @RossMillikan "You seem to be assuming that if the multiplication tables are different the groups are not isomorphic, but that is not true." But what if we have different multiplication tables for groups based on the same set? Could you provide an example? $\endgroup$
    – Luka
    Feb 6, 2020 at 11:51
  • 1
    $\begingroup$ The correspondence you are talking about is the isomorphism. The Wikipedia article on Latin squares says one square can be permuted in up to $n!^3$ ways, which come from reordering the rows, reordering the columns, and swapping the numbers. In your count of $n^{n^2}$ you are ignoring these permutations. You can avoid many of them by considering reduced Latin squares, but those are hard to count and not all of them are groups. $\endgroup$ Feb 6, 2020 at 14:04
2
$\begingroup$

Here's how to do a little better than $n^{n^2}$. For a group $G$, define $d(G)$ to be the least positive integer $k$ such that $G$ can be generated by $k$ elements and let $f(n)$ denote the number of non-isomorphic groups of order $n$.

We first show that if $|G| = n$ then $d(G) \leq \log n$. Let $1=G_0 <G_1 <G_2 <\dots < G_r = G$ be a maximal chain of subgroups. Let $g_i \in G_i \setminus G_{i−1}$ for $1 \leq i \leq r$. Then $\langle g_1, \ldots ,g_i \rangle = G_i$, as one easily sees by induction. In particular, $G$ can be generated by $r$ elements. Now by Lagrange’s Theorem $$ |G| = \prod_{i=1}^r [G_i : G_{i-1}] \geq 2^r.$$

Hence $r \leq \lfloor \log n \rfloor$. Then by Cayley’s theorem $G\leq S_n$ and so $f(n)$ is at most the number of subgroups of order $n$ in $S_n$ which is at most the number of $\lfloor \log n \rfloor$-generator subgroups of $S_n$ which is at most the number of $\lfloor \log n \rfloor$-element subsets of $S_n$. This last quantity is $\leq (n!)^{\log n} \leq n^{n \log n}$.

$\endgroup$
4
  • 5
    $\begingroup$ You have a lot of strange characters in your MathJax $\endgroup$ Feb 6, 2020 at 6:40
  • $\begingroup$ It actually looks ok on the mobile version... @the_fox could you please elaborate on the chain and the generating set part, I don't quite follow you there... $\endgroup$
    – Luka
    Feb 6, 2020 at 23:10
  • $\begingroup$ @the_fox for $g \in G_i \backslash G_{i-1}$ you probably mean elements that are in $G_i$ but not in $G_{i-1}$, not the group of right cosets, right? $\endgroup$
    – Luka
    Feb 6, 2020 at 23:18
  • $\begingroup$ @Luka Yes, that's right. $\endgroup$
    – the_fox
    Feb 8, 2020 at 14:23

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.