14
$\begingroup$

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

$\endgroup$
4
  • 5
    $\begingroup$ To test whether $<S>=S_n$, the method of Parker and Nikolai is very quick, and the Schreier-Sims algorithm proves polynomial time. $\endgroup$
    – ahulpke
    Sep 17 at 19:40
  • 4
    $\begingroup$ Testing whether $\langle S \rangle= S_n$ is interesting, because there is a probabilistic algorithm which, in the case when $S_n = \langle S \rangle$, confirms that this is the case very fast with high probability. So if it fails to confirm that $S_n= \langle S \rangle$ then it is very likely but not certain that $S_n \ne \langle S \rangle$. To verify this you have to use slower (but still polynomial-time) algorithms such as Scvhreier-Sims. $\endgroup$
    – Derek Holt
    Sep 17 at 20:32
  • $\begingroup$ Answers in the comments look interesting for the case of $G = S_n$. Can anybody provide me some more information to the "probabilistic algorithm" which in case when $S_n = \langle S \rangle$, confirms that this is the case very fast with high probability? Thanks in advance. $\endgroup$ Sep 18 at 10:50
  • 2
    $\begingroup$ See my answer to this question - that question was about generating sets of size $2$, but the algorithm works for arbitrary generating sets. $\endgroup$
    – Derek Holt
    Sep 18 at 13:44

2 Answers 2

16
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Hmm… Then I think the general case might be too vague. Let’s just consider finite G with a function f which decides whether x is in G or not in constant time, and all group operations (multiplication and find inverse) are considered done in constant time. By “polynomial time” I mean polynomial in size of S. $\endgroup$ Sep 17 at 19:46
  • $\begingroup$ @Sirawit'Plum'P., This is getting sufficiently specialized that I suspect it might be best to post that as a new question, rather than leaving comments here. It's likely that there is some trivial problem with how you are representing $G$. For instance, consider the trivial group $\{0\},+$ vs the two-element group $\{0,1\},+$ with $1+1=0$; if we are given only the set $S=\{0\}$ and a way to test membership and do group operations in constant time, we can't distinguish whether the group is the trivial group or the two-element group, so $G$ hasn't been uniquely specified. $\endgroup$
    – D.W.
    Sep 18 at 4:43
  • $\begingroup$ Yes, looks like I'm not clear (and actually unable to come up with my own model to go with this). However, @ml0105 provided a concrete model with an answer so no need to post as a new question. $\endgroup$ Sep 18 at 10:40
  • 1
    $\begingroup$ Adian's four papers on the Adian-Rabin theorem were recently translated into English, and can be found on the arXiv. This also has more background on the theorem. Note that deciding triviality was proved already in 1957, while the general "Markov property" (not terminology used by either Adian or Rabin) formulation only appeared in 1958. $\endgroup$ Sep 19 at 8:02
6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ This looks like what I'm looking for, in the finite case of G, and this answers my question completely. $\endgroup$ Sep 18 at 10:48
  • 5
    $\begingroup$ This is excellent as a theoretical answer to the question, but it should be borne in mind that it has very limited practical use. For computing with large finite groups, the Cayley graph model is not useful, and practical algorithms use representations of the group as subgroups of $S_n$ or of ${\rm GL}(n,q)$ for suitable $n$ and $q$, together with specialized methods for computing with finite solvable groups. $\endgroup$
    – Derek Holt
    Sep 18 at 11:16
  • $\begingroup$ This answer, together with this comment, answers the question for finite groups. And the comments in the question answers the question for symmetric groups $S_n$, so I think it would be ready to mark this question as solved. $\endgroup$ Sep 19 at 16:37

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.