9
$\begingroup$

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.) :)!

$\endgroup$
  • 2
    $\begingroup$ Do you mean how many triples you have to check to ensure that associativity holds? $\endgroup$ – rwbogl Jul 23 '18 at 2:28
  • 2
    $\begingroup$ Well the worst case is certainly $|G|^3$, but some can be ruled out because of the identity. If $G$ is non-abelian, then I don't think you can cancel out the $3!$ permutations of $xyz$. Maybe someone knows a clever algorithm! $\endgroup$ – rwbogl Jul 23 '18 at 2:32
  • 1
    $\begingroup$ +1 Cool question! $\endgroup$ – JavaMan Jul 23 '18 at 2:46
  • 1
    $\begingroup$ As rwbogl points out, one needn't check the cases where any of $x, y, z$ are the identity, so an upper bound for general $G$ is $(|G| - 1)^3$. This is clearly sharp in the case $G = \Bbb Z_2$; NB the conjectured bound $n! / 3!$ fails in this case. $\endgroup$ – Travis Jul 23 '18 at 2:51
  • 1
    $\begingroup$ @manooooh Can you state precisely which of my claims you believe to be incorrect? I'm also not sure what exactly you mean by, "Note that the property holds for, in best of cases, 3 elements." $\endgroup$ – Travis Jul 23 '18 at 3:17
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks! I would like to know the answer in the worst case, that is, in those where we have not realized the inheritance that an operation has. So it would be, without any reduction, $n^3$? $\endgroup$ – manooooh Jul 23 '18 at 3:13
  • 1
    $\begingroup$ Indeed $n^3$ is the "worst case" number of checks that you are looking for. $\endgroup$ – David K Jul 23 '18 at 3:24
  • 1
    $\begingroup$ If you really do not have "any other factor that reduces the number of check rows" then I don't see how you decide not to check $1\cdot(0\cdot-1)$ and $1\cdot(-1\cdot0)$ in addition to $-1\cdot(0\cdot1),$ or even how you decide not to check $1\cdot(1\cdot1).$ As has been noted in recent comments, however, it seems reasonable that you would at least eliminate some rows involving the identity without checking them, if you have already proved enough of the other group properties to make this safe. $\endgroup$ – David K Jul 24 '18 at 20:32
  • 1
    $\begingroup$ To put it in brief, if some rows are too silly to check even in "maximum silly mode", then indeed the number to check would be fewer than $n^3$ rows. $\endgroup$ – David K Jul 24 '18 at 20:34
  • 1
    $\begingroup$ $\forall x,y,z$ definitely includes the case $x=y=z$ and all cases where two of the terms are equal. $\endgroup$ – David K Jul 24 '18 at 20:57
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Wow! Thank you for your answer. In a fast-lecture in page 3. says "(...) For every $n\:\geq\:3$ (...)". Btw I will take a look later. $\endgroup$ – manooooh Jul 23 '18 at 6:17
  • 1
    $\begingroup$ A blog post about what I did to find the example. $\endgroup$ – MJD Jul 23 '18 at 17:59
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do what you want. Mark it as a duplicate. I do not care about the upvotes. Ah, by the way: The group must be finite. Imagine that if we have group $(\mathbb Z_n,\overline +)$ it has infinite elements and in this way it is impossible to verify the associativity. $\endgroup$ – manooooh Jul 24 '18 at 17:27
  • $\begingroup$ I don't want to mark it as a duplicate. What I find most interesting about this discussion is that there are two distinct questions, and the question "is this a group?" which seems to be asking more than the question "is this operation associative?" is actually easier to answer. I am not sure what you mean by $({\mathbb Z}_n,\mp)$. ${\mathbb Z}_n$ normally denotes a finite set/group/ring of size $n$. $\endgroup$ – Derek Holt Jul 24 '18 at 17:54
  • $\begingroup$ Why would be important to know if this is a group? I am just asking a formula; a way to know the rows of associative operations we need to do for finite groups, even if we don't know yet if this is a group. And yes, $\mathbb Z_n$ is the set of integres modulo $n$ and $\overline +$ is the sum of classes. $\endgroup$ – manooooh Jul 24 '18 at 18:08
  • 1
    $\begingroup$ But then ${\mathbb Z}_n$ is a finite group. And it is associative. I still don't know what you are asking. Are you asking Question 1 in my answer above? $\endgroup$ – Derek Holt Jul 24 '18 at 18:52
  • $\begingroup$ Yes, sorry, take the aditive abelian group $(\mathbb Z,+)$. I'm not asking any of your two questions. $\endgroup$ – manooooh Jul 24 '18 at 19:24

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.