# What is the smallest $n$ for which the usual “counting sizes of conjugacy classes” proof of simplicity fails for $A_n$?

A common proof of the simplicity of $A_5$ proceeds as follows.

First, note that a normal subgroup is always a union of conjugacy classes. Also, a subgroup has order dividing the size of the group by Lagrange's theorem. Any normal subgroup will contain the conjugacy class with the identity. Now if we look at unions of conjugacy classes of $A_5$ where we include $\{(1)\}$ in the union, there only two cases where the size of the union divides the order $A_5$. These are the cases where the union is all of $A_5$ or just $\{(1)\}$. Hence $A_5$ must be simple.

This same proof also works for $A_6$. But in general we cannot deduce the simplicity of $A_n$ for $n \geq 5$ with the same proof. According to this article it turns out that for example, $1 + \frac{n(n-1)(n-2)}{3}$ divides $n!/2$ when $n = 68$. Note that $\frac{n(n-1)(n-2)}{3}$ is the size of the conjugacy class of $3$-cycles in $A_n$ when $n \geq 5$.

Question: Is $n = 68$ the smallest positive integer where the proof fails? In the article they say that this "seems to be the smallest counterexample". However, counting all the possible sums of conjugacy classes of $A_n$ becomes computationally difficult very quickly (as is noted in the article). Hence actually demonstrating this might be hard.

-
An optimization to the proof is probably well-known: If $N \unlhd A_n$, then $N \cap A_{n-1} \unlhd A_{n-1}$, so either $A_{n-1} \leq N$ (for all conjugates of $A_{n-1}$) or $A_{n-1} \cap N = 1$, so either $N=A_n$ or $N$ is quasi-regular and $|N| \leq n$. So one only needs to check very tiny conjugacy classes (and there are not any, since $A_n$ does not embed in $S_{n-1}$). – Jack Schmidt Aug 7 '13 at 20:26
See also math.stackexchange.com/questions/402862/… where it is shown there are lots of solutions to the similar problem in Sn, and math.stackexchange.com/questions/41773/example-of-a-group/… where the proof fails in a smaller simple group. – Jack Schmidt Aug 8 '13 at 14:13

I ran a small magma program and it turns out that the answer is $n=9$, when there are suddenly 14 extra solutions (on top of the usual two trivial ones).

For each of these, the number of non-trivial conjugacy classes involved is between 7 and 10 (out of a possible 17) and the number of elements involved is either half or a third of all the elements.

For example, $A_9$ has

1 identity element

378 elements with shape $(2^2)$

945 elements with shape $(2^4)$

2240 elements with shape $(3^3)$

7560 elements with shape $(4,2)$

11340 elements with shape $(4^2)$

25920 elements with shape $(7)$

24192 elements with shape $(5,3)$, falling into two conjugacy classes of size 12096 each (we pick only one of these)

for a total of 60480, which is a third of the order of $A_9$.

EDIT: I did a quick check, and there are even more solutions for $n=10$. To check further, I would need to write my program more cleverly, as it runs out of memory at the moment, but my guess is that there are always solution for $n\geq 9$, as the number of subsets of conjugacy classes grows very quickly.

-
For shape (5,3) in $A_9$, I count 24192. – Mikko Korhonen Jul 21 '15 at 19:01
You are right, but they split into two conjugacy classes, I'll edit to clarify. – verret Jul 21 '15 at 19:05
Just out of curiosity, I checked, and there are solutions that do not use any conjugacy classes that get fused in $S_9$. – verret Jul 21 '15 at 19:10
Thanks, I think this should do it. – Mikko Korhonen Jul 21 '15 at 21:08
In case you are interested, for $n=10$ there are 223 non-trivial solutions, they use from 8 to 17 non-trivial conjugacy classes (out of 23) and the proportion of elements used is in $\{1/2,1/3,1/4,1/5,1/6\}$. – verret Jul 22 '15 at 2:31