8
$\begingroup$

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).)

Improve this question
$\endgroup$
5
  • $\begingroup$ 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$. $\endgroup$
    – Roland Bacher
    May 2, 2011 at 7:23
  • $\begingroup$ 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. $\endgroup$
    – H A Helfgott
    May 2, 2011 at 16:08
  • $\begingroup$ Can you clarify what "support" means? $\endgroup$
    – JSE
    May 6, 2011 at 18:03
  • $\begingroup$ 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... $\endgroup$
    – Paul Johnson
    May 6, 2011 at 18:42
  • $\begingroup$ Yes, that's what we (or at least I) mean. $\endgroup$
    – H A Helfgott
    May 7, 2011 at 17:46

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.