How many elements have to verify the associativity property in a group?

Question

If this is a duplicate please mark it down.

We know that if $(G,\ast)$ is a group then it must verify the associative property, that is, $$\forall x,y,z\in G:\quad x\ast(y\ast z)\quad=\quad(x\ast y)\ast z\,.$$

My question is how many elements have to verify the associativity in a group?

I suspect that it must be $$\frac{n!}{3!},$$ where $n$ is the order of $G$.

Is that right?

Thank you!

EDIT: as you have opined I would like to know the worst case, that is, in those where we have not realized the inheritance that can have an operation within the group or any other factor that reduces the number of check rows (yes, "silly" mode activated!). If you want, you can propose the best level if certain restrictions occur (be Abelian, etc.) :)!

Answer 1

If you want to do an absolute brute-force proof, then yes, you may have to check a lot of permutations of the group's elements, but $n!/3!$ is greater than the number of permutations you have to check for any group of more than $6$ elements. You only need to check permutations of three elements with repetition, which means $n^3$ cases to check.

For the linked problem, in which the group has only $6$ elements, $n!/3!$ actually underestimates the number of possible permutations: you would actually need to check $6^3 = 216$ cases, whereas $6!/3!$ is only $120.$

Answer 2

In “Verification of Identities” (1997), Rajagopalan and Schulman discuss associativity testing for binary operations on a finite set of $n$ elements. For certain types of operations, a random algorithm works with high probability. However:

This random sampling approach does not work in general. For every $n≥3$, there exists an operation with just one nonassociative triple.

(Page 3.)

So the answer to your question, unfortunately, is that in the general case one must check all $n^3$ triples of elements. (Not $\frac{n!}6$ as you suggested.)

The Rajagopalan and Schulman paper has more to say that may be useful to you anyway.

---

Since R&S don't say, here's a very simple example of an operation with only one nonassociative triple. Consider the set $\{0, 1, 2, \ldots n-1\}$ (for $n\ge 3$) with the following operation:

$a\ast b = 0$ in all cases, except $2\ast 1=2$.

Then it is easy to show that $a\ast(b\ast c) = (a\ast b)\ast c$ with only one exception: Since $b\ast c\ne 1$, the left side must be equal to $0$. And, except in the one case $(2\ast 1)\ast 1 = 2\ast 1 = 2$, the right side will be $0$ also.)

Answer 3

As I explained in my comments, I do not understand the question, but it has got plenty of upvotes, so I guess others do understand it. But I think there are two distinct questions that you could be asking here.

I guess we are agreed that we are given a finite set $G$ of size $n$ and an operation $*:G \times G \to G$ i.e. for all $g,h \in G$, $g*h$ is a known element of $G$. (The problem I have with your wording is that you persist in referring to $G$ as a group, but the whole point is that we don't know yet whether it is a group.)

Two questions we can ask are

1. Is $*$ associative? I think that most posters have been addressing that question. From the answers and references it looks as though there are probabilistic algorithms that work faster, but no deterministic method is known that is better than $O(n^3)$ in the worst case.

2. Does $*$ define a group? It is interesting that this is apparently asking us to check more conditions than Question 1, but it can be decided in time $O(n^2 \log n)$ in all cases, which is quicker than just checking associativity.

The reason for this is that we start by checking for the existence of an identity element and inverses, which can be done in $O(n^2)$. If the answer is no, then $*$ is not a group and we are done. But if the answer is yes, then we can make use of that to speed up checking associativity. Roughly you do that by finding a generating set $S$ for $G$ of size at most $\log_2 n$. To test associativity it then suffices to check $(gh)s=g(hs)$ for all $g,h \in G$ and $s \in S$.

This was also asked here.