MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Fix a finite group $G$, and let $f_G:\mathbb{N}\rightarrow\mathbb{N}$ be defined by setting $f_G(n)$ to be the largest $m$ such that $S_n$ contains $m$ disjoint (pairwise-intersecting at 1) copies of $G$. In other words, $f_G(n)$ is the optimal number of $G$'s that can be packed into $S_n$ without unnecessary overlap. Clearly $f_G$ starts with a string of zeros, monotonically increases and is unbounded. It would seem spectacularly ambitious to actually compute this function for $G$ remotely complicated.

Q1 - Does $f_G$ determine $G$?

In case the affirmative does hold generally, I'd also be curious to know if a stronger result is true:

Q2 - Does there necessarily exist an $n$ (depending on $G$) such that $f_G(n)\neq f_{H}(n)$ for all $H$ distinct from $G$? In other words, can we be assured that a finite amount of computation would be sufficient to distinguish $G$ from all other finite groups?

An affirmative answer to Q2 would mean that $G$ is classified by a pair of (hopefully computable) integers.

Both answers are affirmative for groups of (very) small order since they're the only ones that even fit in the first few symmetric groups, but I don't see any hope to prove/disprove them in general.

share|cite|improve this question
The string of zeros you mention need not continue for at least $n<|G|$. It could end as soon as $n!$ reaches $|G|$. – Andreas Blass Oct 16 '12 at 23:50
Is it clear that the Klein four group and $\mathbb{Z}/4\mathbb{Z}$ have different sequences? – Noah Schweber Oct 17 '12 at 0:40
Noah, I think the sequence for the Klein four group begins 0, 0, 0, 3, 5 and the sequence for $\Bbb{Z}_4$ begins 0, 0, 0, 3, 15. Interesting question, Jon. Reminds me of an algebra prelim question where we were asked to find the smallest $n$ for which various groups embedded into $S_n$. – Brian Hopkins Oct 17 '12 at 1:16
@Andreas: you're right. I don't know what I was thinking. – Jon Cohen Oct 17 '12 at 2:50
I believe that your function $f_G(n)$ is an utterly difficult object, because it involves a problem which is quite hard for itself: Let $V$ be the set of subgroups of $S_n$ which are isomorphic to $G$. Consider the graph with set of vertices $V$, and an edge between $u$ and $v$ if $u$ and $v$ intersect in $1$. So $f_G(n)$ is the size of a maximum clique of your graph! This is a difficult issue, even for simple types of graphs. I think that your graph doesn't have specific properties which help in that situation, except for trivial situations like $G$ having prime order. – Peter Mueller Oct 17 '12 at 8:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.