Hi everyone!
Five days have passed since my previous post which was generally well received, so I'll continue doing posts like this for time being.
Abstract algebra is among my favorite subjects. One particular thing I find impressive is the associativity of binary operations. One of harder problems from my contests revolves 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 for both groups and arbitrary magmas.
First part of my post is about Light's associativity test and how it can be used to deterministically check whether an 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 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.
Consider a set $$$G$$$ with $$$|G|=n$$$ and an operation $$$\cdot : G \times G \mapsto G$$$ defined by its Cayley table (that is, $$$(G, \cdot)$$$ is a finite magma).
You need to check if $$$(a \cdot b) \cdot c = a \cdot (b \cdot c)$$$ for all $$$a, b, c \in G$$$ (that is, if it is a semigroup).
Until 1996 there were no known sub-$$$n^3$$$ algorithms for it. In 1949 Alfred Clifford and Gordon Preston published Light's associativity test:
For $$$g \in G$$$ define operations $$$x \circ_g y = (x \cdot g) \cdot y$$$ and $$$x \star_g y = x \cdot (g \cdot y)$$$.
$$$\cdot$$$ is associative if and only if $$$\circ_g \sim \star_g$$$ for every $$$g \in G$$$. Checking it for all $$$g \in G$$$ would take $$$O(n^3)$$$ but if $$$G$$$ has generating set $$$S$$$ it is enough to test the equivalence 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}$$$:
\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}
Some magmas have $$$n$$$ elements in the generating set, for example $$$a \cdot b = \max(a, b)$$$. But if for every $$$a, b \in G$$$ there exists unique $$$x \in G$$$ such that $$$x \cdot a = b$$$ (such $$$G$$$ are called quasigroups) then $$$G$$$ has a generating set of at most $$$\lfloor \log_2 n \rfloor + 1$$$ elements:
Let $$$T \subset G$$$ be such 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 do not occur in $$$\langle T \rangle$$$, which means that $$$|\langle T \cup $$$ {$$$b$$$}$$$\rangle| \geq 2 |\langle T \rangle|$$$, thus adding new elements to non-empty $$$T$$$ until $$$\langle T\rangle=G$$$ is only possible at most $$$\log_2 n$$$ times.
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)$$$.
What if we want to check associativity in arbitrary magma? Probabilistic solution to this was proposed by Sridhar Rajagopalan and Leonard Schulman in 1996. They consider group ring $$$\mathbb Z_2[G]$$$ which elements are formal sums $$$\sum\limits_{g \in G} a_g g$$$ where $$$a_g \in \mathbb Z_2$$$. In this ring:
- $$$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 a conjunction of $$$a_g$$$ and $$$b_g$$$.
$$$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$$$ is a semigroup. Otherwise, probability of it being true for uniformly randomly picked $$$A, B, C$$$ is at most $$$\frac{7}{8}$$$ (explained below), which allows adjusting error probability to $$$\delta$$$ by repeating the same test $$$\log_{8/7}\delta^{-1}$$$ times, making it a total time of $$$O(n^2 \log \delta^{-1})$$$ for the error tolerance $$$\delta$$$.
Proof of it 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_{ijm}F_{mkl}-F_{iml}F_{jkm})a_i b_j c_k = 0 \end{equation} Where summations and products are done in $$$\mathbb Z_2$$$ and $$$F_{ijk}$$$ is a 3-dimensional array (tensor) defined as \begin{equation} F_{ijk} = \begin{cases} 1& \text{if }i \cdot j = k,\newline 0& \text{otherwise}\end{cases} \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 F^n$$$ and calculating the identity with these vectors. Probability of obtaining non-zero result is at least $$$\frac{1}{2^k}$$$.
Since $$$A_{i_1 \dots i_{k+1}}$$$ is non-zero, there has to be vector $$$y_{i_1}$$$ such that \begin{equation} A_{i_1 \dots i_{k+1}} y_{i_1} \neq 0, \end{equation} It means that for every $$$x^{(1)}_{i_1}$$$ such that \begin{equation} A_{i_1 \dots i_{k+1}} x^{(1)}_{i_1}=0, \end{equation} there exists $$$z_{i_1} = x^{(1)}_{i_1}+y_{i_1}$$$ such that \begin{equation} A_{i_1 \dots i_{k+1}} z_{i_1}=A_{i_1 \dots i_{k+1}} y_{i_1} \neq 0, \end{equation} which means that there are at least as many vectors yielding non-zero result as vectors yielding zero. Thus the probability of obtaining non-zero result is at least $$$\frac{1}{2}$$$. It 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}$$$ 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
\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 least $$$\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 to the important conclusion that reduction to group rings can as well be used to test arbitrary read-once (such that each variable occurs at most once on both sides of identity) identities 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.
For Rajagopalan–Schulman test $$$k=3$$$ and the error probability is at most $$$\frac{7}{8}$$$. For Freivalds' test $$$k=1$$$ and the probability is at most $$$\frac{1}{2}$$$.
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!
