Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Suppose we have a known group G and an unknown subgroup H. The permutation representation of G on the cosets of H gives a permutation group C, which is known. Is it possible to identify the generators of H using this information? If so, how? If not, what further information is needed?

(For background, my G is the modular group PSL(2,Z); H is a not-necessarily-congruence subgroup of G. C is sometimes called a "cartographic group").

Many thanks!

share|improve this question
    
In what sense is $C$ known if you don't know what $H$ is (and hence don't know what the cosets of $H$ are)? Do you only know $C$ as an abstract group? Do you know its action on the cosets as an abstract group action? –  Qiaochu Yuan Aug 6 '12 at 20:43

2 Answers 2

up vote 5 down vote accepted

Choose a set of generators for $G$. Draw the Cayley graph of the action of $G$ on $G/H$. Choose a set of generators for the fundamental group of the graph. For each generator of the fundamental group, multiply the generators of $G$ corresponding to the edges together in order. This will be a set of generators for $H$.

Proof: Each element of $H$ is a product of the generators of $G$ which, in the action of $G$ on $G/H$, preserves the identity coset. Thus it's a product of generators that forms a closed loop of the Cayley graph. Homotoping that loop to a composition of the generators of the fundamental group does not change the element it refers to. You now have an expression for each element of $H$ in terms of the supposed generators of $H$, so they are in fact the generators of $H$.

share|improve this answer

(I wanted to post this a comment on @Will Sawin's answer, but I don't have the rep yet. Also it turned out to be convenient to flesh it out a little longer than comment.)

Will's answer assumes that you know a fixed element of $G/H$ that you can use as your basepoint for the fundamental group, namely the identity coset $H$. If you don't know that, you can't recover $H$ exactly, you can only recover $H$ up to conjugacy. (The permutation actions of $G$ on $G/H$ and $G/H'$ are permutationally isomorphic iff $H$ and $H'$ are conjugate subgroups.)

For example, in the case of $PSL(2,\mathbb{Z})$, this means that subgroups-up-to-conjugacy of index $n$ are in bijective correspondence with pairs of permutations $(a,b)$ on $[n]$ such that $a^{2} = b^{3} = 1$ (picking some natural generators of $PSL(2,\mathbb{Z}) \cong \mathbb{Z}_2 * \mathbb{Z}_3$)

and $\langle a, b\rangle$ acts transitively on $[n]$, up to the relation $(a,b) \sim (a',b')$ if there is a permutation $\pi \in S_{n}$ such that $\pi a \pi^{-1} = a'$ and $\pi b \pi^{-1} = b'$ (permutational isomorphism).

Subgroups (not up to conjugacy, but on the nose) are classified by the same pairs, but where the $\pi$ that we are allowed to conjugate by must fix, say, $1 \in [n]$ (corresponding to the identity coset of $H$ in $G/H$).

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.