Suppose I have a finitely generated group $G$ of known rank $n$, and a set $\{s_i\}$ of $n$ group elements. Are there some simple necessary and sufficient conditions to determine whether $s_i$ generates $G$? (Suppose that I don't have any known generating set which I can try to generate with the $\{s_i\}$.)

For example, I think this is a necessary condition:

  • $\forall s \in \{s_i\} \; \;\not \exists g \in G \; : \; \langle s\rangle \subset \langle g \rangle$

Is it also sufficient?

  • $\begingroup$ Your condition is not necessary, you can always take $g=s^{-1}$. You probably mean that $<s>$ is a proper subgroup of $<g>$. In any case, this condition is neither necessary nor sufficient. $\endgroup$ – Moishe Kohan Dec 3 '17 at 4:14
  • $\begingroup$ @MoisheCohen - you're right, that's what I meant. I'm pretty sure the condition is necessary. Suppose $s = g^2$. Then you cannot generate $g$ except by using the other $s_i$. But then that makes $s$ redundant, and so your generating set is equivalent to one of cardinality $n-1$, hence not a generating set for a rank $n$ group. $\endgroup$ – Myridium Dec 3 '17 at 4:24
  • $\begingroup$ No, this does not make $s$ redundant. $\endgroup$ – Moishe Kohan Dec 3 '17 at 4:27
  • $\begingroup$ @MoisheCohen - if the other $\{s_i\}$ generate $g$, then they also generate $g^2 = s$. But maybe you need a combination of $s$ with the other $s_i$ to make $g$? I suppose this could happen. $\endgroup$ – Myridium Dec 3 '17 at 4:30
  • $\begingroup$ Exactly! Just think about the case of a finite cyclic group of prime order. $\endgroup$ – Moishe Kohan Dec 3 '17 at 4:32

The group $\langle a, t; t^{-1}at=a^2\rangle$ has rank two and is generated by the set $\{a^2, t\}$. However, $\langle a^2\rangle\lneq\langle a\rangle$ (this follows from Magnus' Freiheitssats*, as $\langle a\rangle\cong\mathbb{Z}$). Therefore, your condition is neither necessary or sufficient.

I would suspect that in general there does not exist an algorithm to determine, for a group $G$ of rank $n$, if a given $n$-element subset of generates the whole group $G$. However, I cannot come up with a proof at the moment...

*See Magnus, Karrass and Solitar, Combinatorial Group Theory, 1965

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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