6
$\begingroup$

Given an input table with binary operation $\circ$. I want to check whether given input table represents a group or not.

I need to verify the four axioms of a group.

  1. The identity I can find it by just scanning the first row of the given table. -----$\mathcal{O}(|G|)$ running time.
  2. Find the closure operation ie.e for any $x,y \in G$, I need to show that $x \circ y \in G $.------$\mathcal{O}(|G|^2)$
  3. An inverse of an element.----$\mathcal{O}(|G|^2)$ Running time.
  4. Associativity operation. -----$\mathcal{O}(|G|^3)$

Which gives me a $\mathcal{O}(|G|^3)$ running time algorithm to check whether the input table corresponds to some group.

Question : What is the fastest algorithm to check whether the input table is a group?

Model of computation is RAM, which computing $x \circ y$ takes constant time.

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ Nice question! Computational group theory is the field (*baddum-tsh*) that covers this kind of thing. $\endgroup$ – David Richerby Sep 16 '18 at 9:14
  • $\begingroup$ @DavidRicherby What's a better tagging? Does computer-algebra apply or should there be a new one? $\endgroup$ – Raphael♦ Sep 16 '18 at 9:26
  • $\begingroup$ @Raphael I'm not sure. To me, "computer algebra" seems to be more about what high school maths teachers call algebra (manipulating equations) rather than what mathematicians call algebra (group theory, linear algebra, etc.). But I don't have any real knowledge of the area. $\endgroup$ – David Richerby Sep 16 '18 at 9:29
  • $\begingroup$ @Raphael A quick search for "group" suggests that we have plenty of questions about computing with groups, so a tag would probably be appropriate. $\endgroup$ – David Richerby Sep 16 '18 at 9:31
  • $\begingroup$ $O(n^2)$ is the lower bound as you must check each $(x, y)$ combination for closure by an adversary argument (let the combination that you didn't check return a non-group element). So only associativity checking is where progress can be made. $\endgroup$ – orlp Sep 16 '18 at 9:46
4
$\begingroup$

There is a non-trivial randomized algorithm that can solve this in $O(n^2 \log (1/\delta))$ time, where $\delta>0$ is the desired error probability. See

Verification of Identities. Sridhar Rajagopalan and Leonard J. Schulman. SIAM Journal on Computing, 29(4), pp.1155-1163.

Improve this answer
$\endgroup$

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.