6
$\begingroup$

This question already has an answer here:

Given an $n \times n$ multiplication table, can one check if it represents a group in $o(n^3)$ time? All properties can be checked by mindless try-all possibilities loops:

  • Whether there is an identity element can be checked in $O(n^2)$ time.
  • Whether every element has an inverse can be checked in $O(n^2)$ time.
  • And associativity can be checked in $O(n^3)$ time.

My question is:

Q. Is there a faster algorithm for arbitrary tables, a subcubic algorithm?

This hardly needs illustration, but here is a multiplication table that would be $D_4$ if the two highlighted entries were swapped:


      GroupXTable8
There is an identity element $1$, and every element has an inverse, but associativity fails: $$2 \cdot (5 \cdot 3) \neq (2 \cdot 5) \cdot 3$$ $$2 \cdot 4 \neq 6 \cdot 3$$ $$3 \neq 8$$ So this table does not represent a group.

$\endgroup$

marked as duplicate by Bjorn Poonen, Will Sawin, Chris Godsil, Tony Huynh, Ryan Budney Nov 13 '14 at 3:19

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.