2024-07-18: This is gonna be my first WIP post in this series. I’ll post my results as I go. Unlike previous posts where I did the work then posted it, this one is gonna require more work to do so I’m making the decision to drip feed this post as I go. I’ll update the date as I go.
Introduction
Welcome back to the blog, to this series on analysing binary operators (then counting them up).
Today we’ll be working on counting operators that have associativity. Given an operator \(f:S\times{S}\rightarrow{S}\) for a finite set S, f is considered associative if and only if \(\forall{a,b,c\in{S}}:f(a,f(b,c))=f(f(a,b),c)\).
Let’s use \(\cdot\) to represent f as an infix operator, rewriting the assertion to: \(\forall{a,b,c\in{S}}:a\cdot{(b\cdot{c})}=(a\cdot{b})\cdot{c}\). Hopefully this actually looks pretty normal, if a bit pointless for your usual operations. It means that brackets are irrelevant to the result; you can evaluate leftward pairs or rightward pairs and the value is the same. So we can just write \(a\cdot{b}\cdot{c}\) and not worry about choosing a version; both “interpretations” of it have the same result.
This is one of the first truly interesting algebraic constraints we are considering in the series. Commutativity and identities are much easier constraints to reason about, primarily because they impose a constraint on the results (the “cells” of the table) and their nature with each other. Associativity forces constraints from the row and column onto the value of the cell itself. The cell is itself an element, so the constraints of the row and column on the cell impose new constraints on other rows and columns (representing the cell element).
The language of operators
The associative property looks really similar to a grammar rule for some language. What do I mean by that?
A set S along with an operator on that set creates a language with an alphabet \(S\cup\{\cdot\}\) where \(\cdot\) is the symbol for application of the operator. The rules for the language are as follows:
- \(A:=a\in{S}\)
- \(T = A | (T)\cdot{(T)}\)
where T is the final language expression we use. For S={a, b}, the terms
- \(a\), \(b\)
- \(a\cdot{b}\)
- \((a\cdot{a})\cdot{((b\cdot{b})\cdot{(b\cdot{a})})}\)
are all valid in our language. This language is infinite due to the
recursive nature of the terminal T. How does associativity fit in
here? It’s a form of rewrite rule.
A rewrite rule is simply an equivalence between terms in a language. A rewrite rule is written as \(\alpha\rightarrow\beta\) for any two terms \(\alpha,\beta\in{T}\). In practice, this means any term \(\alpha\) can be trivially rewritten as \(\beta\) in the language. Note this also works the other way around: \(\beta\) can be rewritten as \(\alpha\).
Operator application is a set of rewrite rules
Even without any of the properties we’ve figured out so far, we already have a set of rewrite rules due to the operator! Say \(f(a,b)=c\) for \(a,b,c\in{S}\). This can be considered the rewrite rule \(a\cdot{b}\rightarrow{c}\). So any specific operator provides \(|S|^2\) rewrite rules for us to use. We’ll categorise these rewrite rules as “application” because they arise from applying the operator and getting the result.
This simple set of rules can also be used to rewrite any \(\alpha\in{T}\): I claim that any term can be rewritten to an element in S.
Proof:
- Any \(a\cdot{b}\) can be rewritten as an element of S as operators must have defined output for any input by virtue of being a function.
- Any term \(\alpha=a\cdot{b}\) can be rewritten to an element of S
- Therefore any term can be rewritten as an element of S by recursively rewriting sub terms
Currently all terms are bracketed; you can’t have something like \(a\cdot{b}\cdot{c}\) by the definition of the language. If you did, it would make the application rules non-deterministic as you could potentially rewrite any term multiple ways (rewrite \(a\cdot{b}\) or \(b\cdot{c}\) first?). That is where associativity steps in!
Associativity is a rewrite rule
Associativity as a rewrite rule would be \((a\cdot{b})\cdot{c}\rightarrow{a\cdot{(b\cdot{c})}}\) where \(a,b,c\in{S}\). Through the application rules, this extends to any term \(a,b,c\) (i.e. they can be arbitrarily large terms themselves) because any arbitrary term can be rewritten down to an element of S by the proof earlier.
Say \(a\cdot{b}=d\) and \(b\cdot{c}=e\). Then, using application, the associativity rule may be rewritten as \(d\cdot{c}=a\cdot{e}\). d and e are just arbitrary elements chosen by the operator, but they’ve now got a relation between them due to some terminal expression that evaluates to them. Do you see how this can get complicated quickly?
Starting small
S={0} is trivially associative, just as it’s trivially commutative and trivially admits an identity. Let’s instead consider S={0, 1}.
The table for any operator on S will look like:
| 0 | 1 | |
|---|---|---|
| 0 | a | b |
| 1 | c | d |
where \(a,b,c,d\in{S}\).
Associativity deals with any 3 elements of S, rewriting the expression. Since S is size 2, there are 8 ways we can write a 3 term expression using just S which happen to be the numbers 0 to 7 in binary. Associativity imposes a rewrite rule on all of them.
To write these rules, I’ll be using \(a,b,c,d\) to represent the values of the different operator applications. Here they are:
- \(a\cdot{0}\rightarrow{0\cdot{a}}\)
- \(a\cdot{1}\rightarrow{0\cdot{c}}\)
- \(c\cdot{0}\rightarrow{0\cdot{b}}\)
- \(c\cdot{1}\rightarrow{0\cdot{d}}\)
- \(b\cdot{0}\rightarrow{1\cdot{a}}\)
- \(b\cdot{1}\rightarrow{1\cdot{c}}\)
- \(d\cdot{0}\rightarrow{1\cdot{b}}\)
- \(d\cdot{1}\rightarrow{1\cdot{d}}\)
That’s a lot of rules and algebra to consider. The good thing is that \(a,b,c,d\in{S}\) so there’s only two choices for each element. If we were doing this by brute force, finding some \(a,b,c,d\) which satisfied these constraints, we’d only need to iterate through \(2^4=16\) different combinations before finding one.
Decision tree
Let’s structure our search as a tree. Each depth of the tree is a variable we are assigning, each edge is a specific choice for that value. The leaves will be booleans which represent if that specific path in the tree satisfies the constraints available.
4 levels of depth, 2 children per node means 31 nodes in total, of which 15 are just variable placeholders and 16 are leaves.
However, if some choice of value for a variable leads to a contradiction, then the rest of the subtree leading from that node are useless to consider anyway, right? E.g. setting a=a_0, b=b_0 leads to a contradiction, then we don’t need to consider the tree spawning from b=b_0. We call this a “dead tree”: the root of this subtree leads to a contradiction, so any branches are useless to traverse anyway.
What we therefore need is an algorithm for figuring out the dead trees.
Figuring out a dead trees
SAT is an NP problem, and is super close to what we’re trying to solve here. That means that generating a satisfying assignment automatically takes non polynomial time to complete. However, checking if a specific assignment satisfies the constraints is actually polynomial time (certification HAS to be in P after all). So it should be possible to generate the tree in exponential time, then in polynomial time remove all the dead trees.
This is really goddamn slow. But until some insight is formed, I see no better way to do this right now.
Forming a decision tree
a = 0
There are 4 valid configurations here.
-
b = 0
Let’s examine our constraints for c:
- \(c\cdot{0}=0\)
- \(0\cdot{c}=c\)
- \(c\cdot{1}=0\cdot{d}\)
- \(1\cdot{c}=c\)
For d:
- \(d\cdot{0}=0\)
-
c = 0
-
d = 0
Valid configuration.
-
d = 1
Valid configuration.
-
-
c = 1
-
d = 1
By the constraint \(1\cdot{c}=c\) we get that \(d=c\) which means if c=1, d=1. It cannot be 0. Valid configuration
-
-
b = 1
Let’s examine our constraints for c:
- \(c\cdot{0}=c\)
- \(0\cdot{c}=c\)
- \(c\cdot{1}=0\cdot{d}\)
- \(1\cdot{c}=d\)
Notice how the third constraint hasn’t changed because we haven’t set d or c.
For d:
- \(d\cdot{0}=d\)
-
c = 0
-
d = 1
By the 4th constraint, \(1\cdot{c}=d\), we get \(b=d\) which means d must be 1. Valid configuration.
-
-
c = 1
By the first constraint, \(c\cdot{0}=c\) which implies \(1\cdot{0}=c\) but \(b=0\) while \(c=1\). Hence this is a dead tree. Invalid configuration.
a = 1
-
b = 0
-
c = 0
- d = 0
- d = 1
-
c = 1
- d = 0
- d = 1
-
-
b = 1
-
c = 0
- d = 0
- d = 1
-
c = 1
- d = 0
- d = 1
-