Hi everyone!
Five days passed since my previous post, so I guess I'll continue doing posts like this for time being.
Abstract algebra was among my favorite subjects. One particular thing I found quite impressive is the associativity of binary operations. One of harder problems from my contests revolves exactly around this property as you need to construct an operation with a given number of non-associative triples. This time I want to talk about how one can check this property both for groups and for arbitrary magmas.
First part of my post goes about Light's associativity test and how it can be used to deterministically check whether some operation defines a group in $$$O(n^2 \log n)$$$. Second part of the post is about Rajagopalan and Schulman probabilistic identity testing which allows to test associativity of arbitrary operation in $$$O(n^2 \log n \log \delta^{-1})$$$ where $$$\delta$$$ is error tolerance. Finally, the third part of my post is dedicated to the proof of Rajagopalan–Schulman method and bears some insights into identity verification in general and higher-dimensional linear algebra.
For convenience, these three parts are separated by horizontal rule.
Let $$$(G, \cdot)$$$ be a finite magma (that is, a set $$$G$$$ with $$$|G|=n$$$ and an operation $$$\cdot : G \times G \mapsto G$$$) defined by its Cayley table.
You need to check if it is a semigroup (that is, if $$$(a \cdot b) \cdot c = a \cdot (b \cdot c)$$$ for all $$$a, b, c \in G$$$).
Despite the task being quite well-known, until 1996 there were no known sub-$$$n^3$$$ algorithms for this task. In 1949 Alfred Clifford and Gordon Preston published the following procedure, attributed as Light's associativity test:
Let $$$g \in G$$$ be arbitrary magma element. Define operations $$$x \circ_g y = (x \cdot g) \cdot y$$$ and $$$x \star_g y = x \cdot (g \cdot y)$$$.
By definition, $$$\cdot$$$ is associative if and only if $$$\circ_g \sim \star_g$$$ for every $$$g \in G$$$. Checking these identities for all $$$g \in G$$$ would take $$$O(n^3)$$$ time but it can be proven that if $$$(G, \cdot)$$$ has generating set $$$S$$$ then it is enough to test the equivalence of operations only for $$$g \in S$$$, which follows from the fact that $$$\circ_a = \star_a$$$ and $$$\circ_b = \star_b$$$ implies $$$\circ_{a\cdot b} = \star_{a \cdot b}$$$ as well:
\begin{equation} x \cdot ((a \cdot b) \cdot y) = x \cdot (a \cdot (b \cdot y)) = (x \cdot a)\cdot (b \cdot y) = ((x \cdot a) \cdot b) \cdot y = (x \cdot (a \cdot b)) \cdot y \end{equation}
It doesn't help for the generic case as there are associative magmas with $$$n$$$ elements in the minimum generating set, for example $$$A$$$ consists of numbers $$$1$$$, $$$2$$$, $$$\dots$$$, $$$n$$$ and $$$a \cdot b = \max(a, b)$$$. But it turns out that if $$$(G, \cdot)$$$ is a quasigroup, that is for every $$$a, b \in G$$$ there exists unique $$$x \in G$$$ such that $$$x \cdot a = b$$$ then $$$(G, \cdot)$$$ has a generating set of at most $$$\lfloor \log_2 n \rfloor + 1$$$ elements.
Let $$$T \subset G$$$ be such set that $$$\langle T \rangle \neq G$$$ where $$$\langle T \rangle$$$ is the closure of $$$T$$$ under $$$\cdot$$$ and let $$$b \in G \setminus \langle T \rangle$$$. Due to quasigroup properties, all elements $$$b \cdot a$$$ where $$$a \in \langle T \rangle$$$ are unique and are not present in $$$\langle T \rangle$$$, which means that $$$|\langle T \cup $$$ {$$$b$$$}$$$\rangle| \geq 2 |\langle T \rangle|$$$, that is adding new elements to non-empty $$$T$$$ until $$$\langle T\rangle=G$$$ is only possible at most $$$\log_2 n$$$ times, which allows to find generating set in $$$O(n^2 \log n)$$$.
It is possible to test the magma for being a quasigroup in $$$O(n^2)$$$, thus the whole associativity testing with Light's test can be done in $$$O(n^2 \log n)$$$ if both conditions need to be present. In particular, every group is also a quasigroup, thus it is possible to deterministically check if given magma is a group in $$$O(n^2 \log n)$$$.
But what if we really want to check associativity in arbitrary magma? Probabilistic solution to this was proposed by Sridhar Rajagopalan and Leonard Schulman in 1996. To nail this bugaboo they consider so-called group ring $$$\mathbb Z_2[G]$$$ which elements are formal sums of the form $$$\sum\limits_{g \in G} a_g g$$$ where $$$a_g \in \mathbb Z_2$$$. In this ring, addition and multiplication of elements $$$A=\sum\limits_{g \in G} a_g g$$$ and $$$B=\sum\limits_{g \in G} b_g g$$$ are defined:
- $$$A+B=\sum\limits_{g\in G} (a_g \oplus b_g)g$$$ where $$$a_g \oplus b_g$$$ is an xor of $$$a_g$$$ and $$$b_g$$$;
- $$$A\cdot B=\sum\limits_{g\in G} \left(\bigoplus\limits_{x \cdot y = g}a_x b_y\right)g$$$ where $$$a_g b_g$$$ is the conjunction of $$$a_g$$$ and $$$b_g$$$.
It can be proven $$$A \cdot (B \cdot C) = (A \cdot B) \cdot C$$$ holds for all $$$A, B, C \in \mathbb Z_2[G]$$$ if and only if $$$(G, \cdot)$$$ is a semigroup. Moreover, if it is not a semigroup, probability of $$$A \cdot (B \cdot C) = (A \cdot B) \cdot C$$$ for uniformly randomly picked $$$A, B, C$$$ is at most $$$\frac{7}{8}$$$, which allows adjusting error probability to $$$\delta$$$ by repeating the same test $$$\log_\frac{8}{7}\delta^{-1}$$$ times, making it a total time of $$$O(n^2 \log \delta^{-1})$$$ for the error tolerance $$$\delta$$$.
Proof here is in a way similar to Freivalds' algorithm which checks $$$(AB-C)x=0$$$ for matrices to verify that $$$AB=C$$$. In the associativity case, $$$A \cdot (B \cdot C) - (A \cdot B) \cdot C=0$$$ is checked and it may be rewritten in Einstein notation as \begin{equation} (F_{ijkl}-G_{ijkl})a_i b_j c_k = 0 \end{equation} Where summations and products are done in $$$\mathbb Z_2$$$ and $$$F_{ijkl}$$$, $$$G_{ijkl}$$$ are 4-dimensional arrays (tensors) defined as \begin{equation} \begin{matrix} F_{ijkl} = \begin{cases} 1& \text{if }(i \cdot j) \cdot k = l,\newline 0& \text{otherwise}\end{cases} & G_{ijkl} = \begin{cases} 1& \text{if }i \cdot (j \cdot k) = l,\newline 0& \text{otherwise}\end{cases} \end{matrix} \end{equation}
For better understanding, the matrix identity from Freivalds' algorithm looks like this in Einstein notation \begin{equation} (A_{ik} B_{kj} -C_{ij})x_j = 0 \end{equation}
We will prove probability bounds for both tests in a similar generic manner. Let $$$A_{i_1 \dots i_{k+1}}$$$ be a rank $$$k+1$$$ non-zero tensor. Then
\begin{equation} A_{i_1 \dots i_{k+1}} x^{(1)}_{i_1} \dots x^{(k)}_{i_k} = 0 \end{equation}
where addition and multiplication is done in some field $$$\mathbb F$$$ (in our case $$$\mathbb F = \mathbb Z_2$$$) can be checked by uniformly independently sampling vectors $$$x^{(1)}, \dots, x^{(k)}$$$ on $$$\mathbb Z_2^n$$$ and calculating the identity with these vectors. Probability of obtaining non-zero result is at least $$$\frac{1}{2^k}$$$.
To begin with, let's look on the probability of $$$A_{i_1 \dots i_{k+1}} x^{(1)}_{i_1}=0$$$. Since $$$A_{i_1 \dots i_{k+1}}$$$ is non-zero, there has to be vector $$$y_{i_1}$$$ such that $$$A_{i_1 \dots i_{k+1}} y_{i_1} \neq 0$$$. This means that for every vector $$$x^{(1)}_{i_1}$$$ such that $$$A_{i_1 \dots i_{k+1}} x^{(1)}_{i_1}=0$$$, there exists a vector $$$z_{i_1} = x^{(1)}_{i_1}+y_{i_1}$$$ such that $$$A_{i_1 \dots i_{k+1}} z_{i_1}=A_{i_1 \dots i_{k+1}} y_{i_1} \neq 0$$$, which means that there are at least as many vectors yielding non-zero result as vectors yielding zero result. This, in turn, means that the probability of obtaining non-zero result is at least $$$\frac{1}{2}$$$. This also proves base case $$$k=1$$$.
Now to make an induction step we should note that $$$A_{i_1 \dots i_{k+1}} x^{(1)}_{i_1}$$$, if it is non-zero, can be perceived as a rank $$$k$$$ tensor $$$B_{i_2 \dots i_{k+1}} = A_{i_1 \dots i_{k+1}} x^{(1)}_{i_1}$$$, so we now deal with the identity
\begin{equation} B_{i_2 \dots i_{k+1}} x^{(2)}_{i_2} \dots x^{(k)}_{i_k} = 0 \end{equation}
For which, by induction, probability of producing non-zero is at $$$\frac{1}{2^{k-1}}$$$. Since $$$x^{(2)}, \dots, x^{(k)}$$$ are chosen independently from $$$x^{(1)}$$$, probabilities of having non-zero can be multiplied directly leading to the $$$\frac{1}{2^k}$$$ probability of having non-zero result in the initial identity.
This result leads us to the important conclusion that reduction to group rings can as well be used to test arbitrary read-once identities (such that each variable occurs at most once on both sides of identity) on operations defined by their Cayley table. In particular, if the composed operation depends on $$$k$$$ variables, testing it requires $$$O(n^2 k)$$$ time and yields at most $$$\frac{2^k-1}{2^k}$$$ error probability.
As a friendly reminder, this post is of my mindbun series. Once in a while I write something of interest to me, usually related to computer science and the mathematics it requires, and post it in the Telegram channel (English) and VK group (partially Russian). Hop in if you find this stuff interesting and/or want to get new posts first-hand!
