Is there an algorithm to check whether a subset generates a group?

Question

I’m new to abstract algebra, so recently, I came up with a curious question: Given a group $G$ and a subset $S$ of $G$, is there a general algorithm to decide whether $\langle S \rangle = G$?

A special case which I find interesting is when $G = S_n$ (finite symmetric groups), can we still come up with such algorithm to decide this problem? If possible, is the algorithm efficient (i.e in polynomial time)?

(I think if the search space $G$ is finite, I might be able to come up with an exponential time brute force algorithm which takes $g_1, g_2 \in S$ and put $g_1g_2, g_2g_1$ back to $S$ repeatedly until there is no more new elements; not sure though if this is correct.)

A concrete formulation of this question is more like: “Does the problem of checking whether $S$ generates $G$ in P, EXP, or even decidable or not?” for $G = S_n$, for finite $G$, and for general $G$.

Answer 1

In the Cayley (multiplication) table model, this problem reduces to membership testing (Cayley Group Membership, or CGM).

Instance: Let $G$ be a finite group given by its multiplication table. Let $S \subseteq G$, and let $x \in G$.

Decision: Is $x \in \langle S \rangle$?

It is known that CGM belongs to $\textsf{L}$. We may use a logspace transducer to write down the Cayley graph $\text{Cay}(G, S)$. We then apply Reingold's logspace pathfinding algorithm to decide if there is a path from the identity element of $G$ to $x$.

To test whether $G = \langle S \rangle$, we apply the above algorithm for each $x \in G$.

In certain cases, we can achieve alternate parallel bounds (uniform $\textsf{AC}$ circuits of depth $\text{poly } \log \log |G|$). See: https://www.sciencedirect.com/science/article/pii/S0022000001917647

Edit: Even in the permutation group setting, membership testing is in $\textsf{NC}$ (https://ix.cs.uoregon.edu/~luks/NC.pdf). If I remember correctly from the last time I did the analysis, at most $O(\log m)$ iterations suffice (where $m$ is the number of generators- i.e., the size of the input), and each iteration is $\textsf{AC}^{1}$-computable. This gives us a bound of $\textsf{AC}^{2}$. Multiplying permutations is $\textsf{FL}$-complete ($\textsf{FL}$ is the class of logspace-computable functions, as opposed to decision problems); see Cook--McKenzie (https://www.cs.utoronto.ca/~sacook/homepage/cook_mckenzie.pdf). So we have a lower bound on how much better we can do.

This technique is still theoretical. I would be surprised if it led to efficient practical implementations.

Answer 2

Good question! The answer depends delicately on how you are given $G$; for computational questions about groups "given a group $G$" is subtle. If $G$ is given by a finite presentation then this problem is already undecidable if $S$ is empty; that is, it's undecidable whether a finite presentation presents the trivial group.

More generally we have the following theorem analogous to Rice's theorem for finite presentations of groups:

A property $\mathcal{P}$ of finitely presentable groups is Markov if

• There exists $G_+ \in \mathcal{P}$ (a positive witness).
• There exists a finitely presented group $G_-$ (a negative witness) such that if $G_- \leq G$, then $G \notin \mathcal{P}$. (Our sources for this post are again Notes of Gilbert Baumslag and a survey by Chuck Miller.)

Theorem (Adyan–Rabin 1957/58). If a property $\mathcal{P}$ of finitely presented groups is Markov, then there is no algorithm to decide $\mathcal{P}$ among all finitely presented groups.

Things are probably better for $G$ finite; I think the Todd-Coxeter algorithm might do it but I haven't checked the details carefully. I don't know what its runtime is. "Polynomial time" is a bit ambiguous here because it's not clear what parameter we want a polynomial in.

Reading about the unsolvability of the word problem might also be useful context.