# Checking whether given binary operation is a group operation

Given a binary function $f: [1..n] \times [1..n] \to [1..n]$ how to check that this operation is a group operation on $[1..n]$?

It's obvious that this can be done in $O(n^3)$ time just by checking all group properties. The most time-expensive property is associativity. Also it's clear that it could not be done faster than $O(n^2)$ time since you should at least examine all values $f(i,j)$.

The question is if there is any algorithm to solve this problem in time faster than $O(n^3)$?

Indeed, S. Rajagopalan and L. Schulman prove that this can be done in $O(n^2\log n)$ time in the paper "Verifying identities" from the proceedings of the 37th annual symposium on foundations of computer science. Their algorithm is applied to operations with cancellative properties, but checking if a binary operation has the cancellative property can be done in $O(n^2)$ time.