Lemma 1: left and right identities are equivalent

• Say I have a left identity a and a right identity b on the same operator
• By definition:
  1. \(\forall{x\in{S}}:f(a,x)=x\)
  2. \(\forall{x\in{S}}:f(x,b)=x\)
• By specialising 1 (x=b): \(f(a,b)=b\)
• By specialising 2 (x=a): \(f(a,b)=a\)
• Since f is a function, f(a,b) is a constant
• Therefore \(a=b\)

Corollary 2: left and right identity implies a complete identity

By lemma 1, any left and any right identity over the same operator are equivalent. Since they’re equivalent, either identity is both a left and a right one. By definition, therefore, they are a complete identity

Corollary 3: complete identity implies a left identity and a right identity

Obviously, if \(a\in{S}\) is a complete identity we can classify a as a left identity and a right identity.

Multiple identities preclude other identities

So a left and right identity will make a complete identity, and there can only be one complete identity.

What if I had two left identities? Or two right identities? I argue having multiple of one removes the possibility of the other, therefore removing the possibility of a complete identity.

Constructor for operators with a complete identity

This one is a bit trite, mostly cos the reasoning is so simple. The problem of generating operators with complete identities is the same as generating tables that have a fixed row and column. How should we design an algorithm for this?

Constructor for commutative operators with a complete identity

This will be the first time we’re combining constraints together. The conditions of an operator being commutative and an operator having a complete identity are independent; one doesn’t affect the likelihood of the other.

Therefore we can go from either direction: think about commutative operators then filter for those with a complete identity, or think about operators with a complete identity and filter out for those that are commutative. I’ll go for the former because the space of commutative operators is easy for me to visualise as a table.

We’ve made a simple table condition for a complete element: a row and column that are completely fixed to certain values. If we look at the constructor we made back in part 2, we can just fit the constructor I made earlier into this. This should be really easy to perform analysis on, using the proofs we made in part 2’s constructor.

Number of left identities

A left identity fixes a row in a table. That means we have \(n(n-1)\) cells left to choose values for. Since there are still n choices per cell, \(n^{n(n-1)}\) choices.

Number of right identities

Using the same argument as for left identities, \(n^{n(n-1)}\).

Number of complete identities

Both a row and a column are fixed. That means \(2n-1\) cells are fixed (2n for both the row and column, minus 1 for over counting). Therefore \(n^2 - 2n + 1\) cells are free to choose values for. n choices per cell means \(n^{n^2-2n+1}\) possibilities.

Number of possible operators with some identity

Same as asking \(|L\cup{R}|\). By inclusion-exclusion principle, \(|L\cup{R}|=|L|+|R|-|L\cap{R}|\)

\(|L|+|R|=2n^{n^2-n}\) and \(|L\cap{R}|=n^{n^2-2n+1}\).

Therefore \(|L\cup{R}|=2n^{n^2-n}-n^{n^2-2n+1}\).

We can simplify by simplifying \(L\cap{R}\): \(n^2-2n+1=(n-1)^2\) so we can factor that exponent in \(L\cap{R}\): \[n^{(n-1)^2}=(n^{n-1})^{n-1}=(\frac{n^n}{n})^{n-1}=\frac{n^{n(n-1)}}{n^{n-1}}\]

Then we can factor it out of \(|L\cup{R}|\): \[2n^{n^2-n}-n^{n^2-2n+1}=2n^{n(n-1)}-\frac{n^{n(n-1)}}{n^{n-1}}=n^{n(n-1)}(2-\frac{1}{n^{n-1}})\]

Therefore \(|L\cup{R}|=n^{n(n-1)}(2-\frac{1}{n^{n-1}})\)

Number of commutative operators with complete identity

Let’s use the constructor we made for this.

The number of cells fixed represent our free variables: the cells set in step 1 must be set to those values and cannot be changed.

The size of \(S\backslash\{1\}\) is \(|S|-1=n-1\). The number of cells set directly in step 2 and 3, by theorem 4 from post 2, is \(\sum_{i=1}^{n-1}{i}\).

Since each of these cells can be any of the n values from \([n]\leftrightarrow{S}\), we have \(n^{\frac{(n-1)n}{2}}\) possible options for a commutative operator that also admits a complete identity. The exponent comes from the sum we derived in the previous paragraph.

Probability of some identity given a binary operator

This is simply the ratio \(\frac{|L\cup{R}|}{n^{n^2}}\).

\[\frac{n^{n(n-1)}(2-n^{1-n})}{n^{n^2}}=\frac{n^{n^2}n^{-n}(2-n^{1-n})}{n^{n^2}}=\frac{2-n^{1-n}}{n^n}\]

In comparison to commutative operators, an operator admitting some identity is actually quite likely. Of course, it’s still exceedingly rare for large n. Nevertheless, it shows that the constraint of having an identity element is actually looser than being commutative, which makes sense.

Probability of a complete identity in a binary operator

We want to find \(\frac{|L\cap{R}|}{n^{n^2}}\). I suspect this will be a very hard scaling expression, though I think it’ll still be more likely than commutativity.

\[\frac{n^{(n-1)^2}}{n^{n^2}}=\frac{n^{(n-1)^2}}{n^{(n-1)^2}n^{2n-1}}=\frac{1}{n^{2n-1}}=n^{1-2n}\]

Wow, so up to 5 the chances of having a complete identity element is slightly worse than getting a commutative operator. Past that the chances are much better for a complete identity element. That makes sense as \(2n\) is slower than \(n^2/2\) in terms of growth. Also the chances of getting a complete identity is exponentially worse than getting some identity, which makes complete sense.

Probability that an operator with some identity has complete identity

That is \(\frac{|C|}{|L\cup{R}|}\).

\[\frac{n^{(n-1)^2}}{n^{n(n-1)}(2-n^{1-n})}=\frac{n^{(n-1)^2}}{n^{n-1}n^{(n-1)^2}(2-n^{1-n})}=\] \[\frac{1}{n^{n-1}(2-n^{1-n})}=n^{1-n}{(\frac{2n^{n-1}-1}{n^{n-1}})}^{-1}=n^{1-n}\frac{n^{n-1}}{2n^{n-1}-1}=\frac{1}{2n^{n-1}-1}\]

So given an identity the chances of having a complete identity are on the same order of magnitude as the chances of having an identity in any operator at all. This makes complete sense: if we have an identity and we’re checking if we have a complete one, that is the same as asking if we have the other type of identity i.e. if I have a left identity and I’m asking if it’s a complete identity, I need a right identity. This is why the chances of having a complete identity in any binary operator are so low: it’s almost a squaring of the probability!

Probability of an operator being commutative and having complete identity

That is \(\frac{n^{\frac{n(n-1)}{2}}}{n^{n^2}}\).

\[\frac{n^{\frac{n(n-1)}{2}}}{n^{n^2}}=n^{\frac{n^2-n}{2}}n^{-n^2}=n^{-\frac{n^2+n}{2}}=n^{-\frac{n(n+1)}{2}}\]

Just from this sample graph alone, along with the fact that we can assert the number of these objects is lower than general commutative operators, we can definitely say these are rare operators. Though later on the difference in orders of magnitude lessens (purely due to how tiny these probabilities get), this operator is still several orders of magnitude less likely to occur than the previous rarest object: the commutative operator.