14
$\begingroup$

It is a well-known result on group theory that if a group has many pairs of commuting elements then it is abelian.

This motivated the following pseudo-conjecture.

If a (possibly infinite) set $S$ with a binary operation $\cdot$ is such that for many triples $a,b,c\in S$ it holds $(a\cdot b)\cdot c = a \cdot (b\cdot c)$, then $(S,\cdot)$ is a semigroup.

Exploring a little bit on this, a colleague told me he has read somewhere (he can't remember where) that the statement above is false.

If $S$ is a finite set, then there exists a binary operation $\star$ that satisfies $(a\star b)\star c = a\star(b\star c)$ for all but just one ordered triple $(a,b,c)\in S\times S\times S$.

Such a result implies that an algorithm that checks if a certain operation is associative must check indeed all triples of elements, which is kind of funny and rather unintuitive (to me, at least).

We couldn't find a proof of this last result, although playing with small sets it seems to be true.

My questions are the following:

1) Does anybody here know a reference for this result?

2) Is there a constructive proof for such an example?

$\endgroup$
4
  • 3
    $\begingroup$ Related: mathoverflow.net/questions/311209/… , and the answer mathoverflow.net/a/311213 . $\endgroup$
    – LSpice
    Jan 21, 2020 at 16:58
  • $\begingroup$ Suppose you show it true for small almost semi group S. Then let S' have S as a proper substructure, let z in S' and z not in S, and declare x*y be z for x and y with at least one outside of S. Then S' fails associativity at exactly the same spot as does S. So you just need one example on three elements for S, or even on two elements if such exists. Gerhard "Small Failures Are Easily Propagated" Paseman, 2020.01.21. $\endgroup$ Jan 21, 2020 at 17:14
  • 5
    $\begingroup$ math.stackexchange.com/a/2860039 $\endgroup$ Jan 21, 2020 at 17:42
  • $\begingroup$ Concerning randomized algorithms to test associativity, the basic idea of the Rajagopalan–Schulman algorithm is outlined in rjlipton.wordpress.com/2010/06/03/… $\endgroup$ Jan 21, 2020 at 17:45

1 Answer 1

15
$\begingroup$

The result you quoted appears in this reference: G. Szasz, Die Unabhängigkeit der Assoziativitätsbedingungen, Acta. Sci. Math. Szeged 15 (1953), 20-28.

The Szasz theorem requires that the set $S$ have at least four elements, though it is also true for sets of size $3$.

Szasz' proof is constructive and goes as follows. Assuming $a$, $u$, $v$ and $w$ are distinct members of $S$, define $a\cdot a = u$, $a\cdot u = v$ and $x\cdot y = w$, for any $(x,y)$ other than $(a,a)$ and $(a,u)$. Then a case by case verification shows that $(a\cdot a)\cdot a = w\neq v = a\cdot(a\cdot a)$ but that, for every other triple $(x,y,z)\in S^3$, we have $(x\cdot y)\cdot z = x\cdot(y\cdot z)$.

Direct enumeration shows that there are (up to isomorphism) $10$ magmas of order $3$ with exactly one non-associative triple. (There are $124$ of order $4$.)

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.