Блог пользователя adamant

Автор adamant, история, 3 года назад, По-английски

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:

  1. $$$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$$$;
  2. $$$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 ring $$$R$$$ (in our case $$$R = \mathbb Z_2$$$) can be checked by uniformly independently sampling vectors $$$x^{(1)}, \dots, x^{(k)}$$$ on $$$R^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!

  • Проголосовать: нравится
  • +158
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why is the density of associative triples at most $$$\frac78$$$?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    That's explained in the third section. Take $$$k=3$$$ and consider $$$H_{ijkl} = F_{ijkl} - G_{ijkl}$$$, so that you need to count the density of $$$H_{ijkl} a_i b_j c_k = 0$$$ solutions which is proven to be at most $$$\frac{2^3-1}{2^3}=\frac{7}{8}$$$. You may also refer to lemma 2.1 of Rajagopalan and Schulman original work if their approach is more appealing to you.

    I can further explain my view of it, but I'd need some more specific questions...

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      Oh I just blocked at that statement and didn't read further, because I thought you were using something from before... Nevermind.

      Fun fact: if $$$G$$$ is a non-abelian group, the maximum density of commutative pairs is $$$\frac58$$$. But if $$$G$$$ is not a group, the commuting probability can be any rational number.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I added some clarification to the post, hopefully it will prevent somebody from doing the same :)

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I personally find the topic interesting and have previously read up on it before when I was trying to bruteforce the number of semigroups of order n (turns out it's a super hard problem: https://math.stackexchange.com/questions/105438/how-many-associative-binary-operations-there-are-on-a-finite-set)

But how do you use it in CP? Unlike polynomial identity testing (which organically comes up in string hashing problems), there doesn't seem to be many situations where you have an operator defined by a cayley table where you specifically want to know if it's associative or not. What are some clever ways to apply it? I can only think of really dumb direct applications which doesn't make for interesting CP problems (e.g., Alice wrote an mathematical expression with a custom binary operator but deleted all her parentheses. Determine if her expression is still correct.)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How to apply it for you case? When the specific sequence of operands is given.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Uh I was thinking of the really really stupid direct application case (input is n and a single cayley table, determine if parentheses matter)

      Are you asking how to do it if operands are known but the cayley table is unknown? And to produce such an associative operator? In that case a table of all identity should work.

      Multiple different operators might be more interesting? Idk

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Operands are known, Cayley table is known. Check if there are two ways to put brackets between them which produce different results. That's how I read it.