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

Let H be a subgroup of Sym(n) that is not too large - say $|H| = |Sym(n)|^{o(1)}$. (A group that is especially interesting in this context is the abelian group H = {products of powers of $\pi_1$,...,$\pi_k$}, where $\pi_1$,$\pi_2$,...,$\pi_k$ are disjoint cycles of distinct lengths, k about $\sqrt{n}$, each length also about $\sqrt{n}$.)

If I conjugate H by a few random elements, will H stick in different directions? To make this precise: will the map

$H \times H \times ... \times H \to Sym(n)$ given by
$(h_1,h_2,...,h_l)\mapsto g_1 h_1 g_1^{-1} ... g_l h_l g_l^{-1}$ ($l=O(1)$)

be in some sense close to being injective for g_1,...,g_l random elements of Sym(n)? (By "close to being injective", I mean, say, that if two tuples $(h_1,h_2,...,h_l)$, $(h_1',h_2',...,h_l')$ map to the same element of Sym(n), then one of the elements $h_1 h_1'^{-1}$, ... , $h_l h_l'^{-1}$ has small support (support < 0.1n, say).)

share|cite|improve this question
I think you need some condition on the support of $H$ (as in your example) and not on the cardinality of $H$. The birthday theorem shows that you are essentially correct if the support of $H$ is much smaller than $\sqrt{n}$ (say $n^{1/2-\epsilon}$). Another result (I ignore its first appearance) states however that two random (for the uniform probability) permutation generate asymptotically $S_n$ or its alternating subgroup $A_n$ with probability $1$. – Roland Bacher May 2 '11 at 7:23
I would say the right condition isn't quite on the cardinality or the support. Things seem to work if the group is very small (size O(n^O(1))) or of very small support, but in both cases "very small" is too small to be truly interesting. In the example I gave, neither the cardinality nor the support of H are very small. Rather, one interesting thing is that H seems to have a large subset S such that, for any distinct h, h' in S, the quotient h^{-1} h' has large support. I would be interested in an answer even for just the particular (abelian) H I have mentioned. – H A Helfgott May 2 '11 at 16:08
Can you clarify what "support" means? – JSE May 6 '11 at 18:03
Jordan -- the standard use of "support" for an element $g$ of $S_n$ that I've seen is just the elements of $[n]$ that $g$ moves -- the support is the complement of the fixed point set. Presumably that's what they mean... – Paul Johnson May 6 '11 at 18:42
Yes, that's what we (or at least I) mean. – H A Helfgott May 7 '11 at 17:46

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.