# Determining if a set is a Generating Set given a known group rank

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?

• 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. – Moishe Kohan Dec 3 '17 at 4:14
• @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. – Myridium Dec 3 '17 at 4:24
• No, this does not make $s$ redundant. – Moishe Kohan Dec 3 '17 at 4:27
• @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. – Myridium Dec 3 '17 at 4:30
• Exactly! Just think about the case of a finite cyclic group of prime order. – 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...