Introduction
Welcome back to this series on binary operators(?1)
Today we’ll be counting up commutative binary operators. In the previous post we counted all general binary operators, so this post will be counting a subset of that. A binary operator is commutative if and only if the ordering of parameters is irrelevant to the output i.e. \(\forall{x,y\in{S}}:f(x,y)=f(y,x)\) where f is some binary operator over S. Addition and multiplication over the integers are certainly commutative, but subtraction and division are not.
Adding a constraint generally lowers the number of candidates in the set. This general idea is in the same vein as creating a “subtype” of some type: the subtype has a stricter contract (so to speak) than the base type on an object, hence the subtype must have less viable candidates than the base type.
How do we go about counting this?
A simple approach
One way would be to use some set theory: if we consider the set of binary operators over S (call it B) and the set of all commutative binary operators over S (call it C), certainly the latter is a subset of the former (\(C\subset{B}\)). To count C, we’d just count B and subtract all the binary operators that aren’t commutative i.e. \(B\backslash{C}\). However, I couldn’t quickly think up a way to mathematically construct and then count the non commutative binary operators so I gave up doing it this way (but I’d be happy to read of a way to do so if you come up with it).
Instead, I used a model to visualise and express binary operators.
Operators as tables
Binary operators are binary because they take exactly two inputs and spit out one output. There’s a few models you can use for them but for such a basic problem I think a table would be good. Everyone knows what a table is, and they’re quite intuitive to work with.
A table that models some binary operator requires that every cell at some row and some column is simply the application of the binary operator. Let \(S=\mathbb{Z}_2\) and the binary operator be \(+\)2. The table for this would look like:
| 0 | 1 | |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 1 | 0 |
Using this table you can get the result of any addition in \(\mathbb{Z}_2\). \(x+y\) is simply the cell at row \(x\) and column \(y\).
There’s loads of results you can make just on this construct, such as noticing cyclic subgroups in \(\mathbb{Z}_n\) by using subtables of the original table, which I’ll maybe make a post about at some point.
Let’s see if we can solve the problem from the previous post using our model. The problem of counting the number of binary operators for a finite set S is the same as counting how many unique \(|S|\times{|S|}\) tables we can construct, each table representing a binary operator. Each cell of the table is an element of \([n]\) and there are \(n^2\) cells, so \(n^{n^2}\) tables makes complete sense.
Note: it’s always good to see a result you’ve already proved pop out of an alternative model for a problem. It usually means the alternative model is correct.
Counting operators using tables (the nice way)
Let’s consider the tables for some commutative operator over any set of size 1, 2, 3 and 4. I’ll be using free variables and letters cos we’re being so abstract but just think of them as placeholders for numbers.
| a | |
|---|---|
| a | a |
| a | b | |
|---|---|---|
| a | aa | ba |
| b | ab | bb |
| a | b | c | |
|---|---|---|---|
| a | aa | ba | ca |
| b | ab | bb | cb |
| c | ac | bc | cc |
| a | b | c | d | |
|---|---|---|---|---|
| a | aa | ba | ca | da |
| b | ab | bb | cb | db |
| c | ac | bc | cc | dc |
| d | ad | bd | cd | dd |
Can you see the pattern here?
The pattern
If you exclude the self squares on the leading diagonal i.e. aa,
bb, etc. the remaining cells can be paired up with exactly one other
cell by the commutative constraint e.g. we can pair ab with ba.
So in fact all cells can be described as either a self square or the
same as exactly one other cell.
Obviously if we set some value for ab this sets the value of ba
due to commutativity. So setting half of these non square cells should
set the other half. In other words, setting ab and setting ba
lead to the same operator so we don’t need to count both.
Count it up, count it up, count it up, count it
Well there are \(n^2\) cells in total, and n of them are squares, so there must be \(n^2 - n\) non squares. Halving that gives \(\frac{n^2-n}{2}\) which is the actual number of non square cells we need to set. \(n+\frac{n^2-n}{2}\) is the total number of cells we need to set in order to define the entire table (square cells plus the non square cells we have to set).
Simplifying, this is the same as \(\frac{n^2+n}{2}\). Each cell still has n possible choices, so the total number of commutative binary operators is \(n^{\frac{n^2+n}{2}}\).
To phrase this in terms of boxes and balls3, by the constraint of commutativity we’ve reduced the number of boxes we need to fill up. Another way of thinking about it is that when we fill certain boxes (non square cells), they automatically fill another box. This leads to our expressions above.
Counting operators using an algorithm (the chad way)
That result (\(n^{\frac{n^2+n}{2}}\)) is quite nice. The astute among you may notice that the exponent here is actually the closed form of a classical construct: \(\sum_{i=1}^n{i}=\frac{n(n+1)}{2}\).
The pairing setup done with the tables doesn’t seem to have anything to do with summing consecutive numbers, but we can explain this by creating an algorithm which generates an arbitrary commutative binary operator.
The general idea I’ve got is to define some algorithm which will arbitrarily generate a commutative binary operator. It’ll set just the right stuff, and use the commutative constraint to do the rest. If we can prove that this algorithm works and that it’s the best way of generating an operator then certainly the runtime semantics of it will be equivalent to the combinatorial semantics of the actual object in question.
In less fluffy language: if the algorithm is really good at its job then we can say that proved aspects of the algorithm are statements on the nature of commutative binary operators.
The algorithm
- \(\forall{x\in{S}}:\) set \(f(x, x)\)
- For x from 1 to |S|
- \(\forall{y\in{S}, y>x}:\) set \(f(x, y)\)
In prose, in step 1 the algorithm sets every square cell. By that we mean it sets an arbitrary number for it, which could be anything.
In step 2, we iterate from 1 to the size of the set S. In each iteration, we set all the cells “greater” than x. Note that we’re utilising the ordering of the numbering over S but it’s not like any specific numbering is particularly important; we could use any numbering and this algorithm would work.
1) Each iteration reduces the number of cells directly set
The number of cells set per step is \(|S|-x\) and as x increases this will obviously decrease
2) All cells are set by the algorithm
This is the same as saying that the algorithm actually does its goddamn job.
- Take any finite set S of size n
- Step 1 of the algorithm sets the n cells in the leading diagonal, so we can consider them set.
Lemma 1: “for each iteration of step 2 (where \(x\in{[n]}\)), the cells that aren’t directly set on row x by step 2.1 are set by previous iterations”.
What this means in prose is that the cells “less than” x that aren’t set by the algorithm are actually set by previous iterations.
I argue Lemma 1 is equivalent to “all cells are set by the algorithm”. For each iteration we set some portion of the row and by the end of the algorithm we’ve gone through every row. If we can prove that, per iteration, the portion of the row that isn’t directly set by the algorithm is set somewhere else then by the end of the algorithm every cell in every row is set.
Proving Lemma 1, therefore, is equivalent to proving “all cells are set by the algorithm”.
Proving Lemma 1
- Let’s use strong induction on x for step 2
- x = 1
- step 1 sets \(f(1,1)\)
- step 2.1 sets \(\{f(1, y) : y > 1\}\)
- Hence the statement is vacuously true for x = 1 (all cells are set in one step, and there isn’t a previous iteration)
- Assume \(\exists{k\in{[n]}}:\forall{x\in{[k - 1]}}:\) the statement is true
- Let \(x=k\), so there are \(|S|-k\) cells that step 2.1 sets directly
and k cells that aren’t set directly
- The set \(\{f(x, z) : z\in{S}\land{z\leq{x}}\}\) are all the cells not set in the current iteration
- \(z=x\) is set in Step 1 so we can exclude it from consideration
- \(\forall{z\in{S},z<x}:\) consider the iteration of step 2.1 where
x=z
- By inductive hypothesis, all cells for row z are set (cos it’s
less than k)
- Hence \(\{f(z, a) : a\in{S}\}\) are all set
- By commutative constraint \(\{f(a, z) : a\in{S}\}\) are all set
- In particular, \(x\in{S}\implies{f(x,z)}\) is set
- By inductive hypothesis, all cells for row z are set (cos it’s
less than k)
- Thus, at step \(x=k\) all cells not directly set are set by previous iterations
- Thus by the principle of induction, all cells that aren’t directly set at any iteration of step 2 are set by previous iterations.
3) Number of cells directly set are necessary and sufficient
Expanding the title, the number of cells set by the algorithm are necessary and sufficient for completely defining any commutative operator4.
The sufficient condition comes from the previous theorem: by setting only these cells we can set all cells, so whatever cells we do set are sufficient for completely defining the operator. Necessary means we cannot skip seting any cell that we do set: every cell set is necessary to defining the operator.
We’ll prove this by arguing that if a cell we should directly set (according to the algorithm) isn’t, then the operator is not defined.
- Say we don’t directly set cell \((a,b)\in{S\times{S}}\)
- The only cells the algorithm directly sets are \(\forall{x\in{S}}:f(x, x)\) and \(\forall{x,y\in{S},y>x}:f(x,y)\)
- Therefore (a,b) can be:
- A square cell i.e. a = b
- If we don’t set the square cell f(a, a) then the operator is not defined as there are no constraints that can be used to define it
- Or a cell where \(b > a\)
- If we don’t set cell f(a, b) then the cell f(b, a), which isn’t directly set by the algorithm either, isn’t set either
- This cannot be defined using any further constraints, therefore the operator would be not defined
- A square cell i.e. a = b
- Therefore, if any of the cells we do set aren’t set the operator is ill defined.
4) The number of cells directly set is the sum!
Step 1 sets exactly \(|S|\) cells.
Step 2 sets \(\sum_{x=1}^{|S|}(|S|-x)\) cells in total, for each step x. We can rearrange this sum trivially to \(\sum_{x=1}^{|S|-1}{x}\).
In total we set \(|S| + \sum_{x=1}^{|S|-1}{x}\) which is the same as \(\sum_{i=1}^{|S|}{i}\).
The number of cells directly set are the necessary and sufficient number of cells to completely express a commutative binary operator. Another way of putting it is that the number of directly set cells are the number of free variables we can tweak to create a commutative binary operator.
Each free variable has n choices. Hence the number of commutative binary operators must be \(n^{\sum_{i=1}^{n}i}=n^\frac{n(n+1)}{2}\).
A percentage to consider
We now know how many overall binary operators exist (\(n^{n^2}\)) and how many commutative binary operators exist (\(n^{\frac{n^2+n}{2}}\)). A natural question is: how many binary operators are commutative?
\[\frac{n^{\frac{n^2+n}{2}}}{n^{n^2}}=n^{\frac{n^2+n}{2}-n^2}=n^{\frac{n-n^2}{2}}=n^{\frac{n(1-n)}{2}}\]
| n | % |
|---|---|
| 1 | 100.0 |
| 3 | 3.7 |
| 5 | 1.024e-05 |
| 10 | 1e-43 |
| 20 | 6.37e-246 |
So commutative binary operators can be considered incredibly rare over all binary operators. By just having set of 3 elements, the number of commutative operators gets to just 3.7% of all operators.
Conclusion
This took much longer to write up than the previous one, mostly because of the latter portion where we formally prove the semantics of an algorithm. Theoretical CS proofs are always so much more busy work than general mathematical proofs (at least in algebra). But still, it was fun to use my degree a bit.
I think the next post I’ll try and see what happens if we introduce an identity.
-
I don’t really know what the topic of this series is per se, just kinda making it up as I go. ↩︎
-
Binary addition is a binary operator, who would’ve thought! ↩︎
-
My combinatorics professor loved this model for explaining certain numeric expressions and how they came about, and now I can’t stop using it ↩︎
-
If a is necessary for b, we cannot exclude a or any component of a to get b. If a is sufficient for b, then by having a we can get b. In logical jargon, a is necessary for b means \(b\implies{a}\) and a is sufficient for b is \(a\implies{b}\). Therefore, if a is necessary and sufficient for b, then \(a\iff{b}\). ↩︎