Robert's Mistakes

on associativity

Nov 19, 2021

Note that this is an unfinished blog post.

From ncatlab

another diagram:

From ncatlab

The law of associativity allows to change the order in which operations are applied.

a(bc) = (ab)c

example: subtraction and division are nonassociative

(32)1=0,but3(21)=2 (3-2)-1 = 0, \textrm{but} \\ 3-(2-1) = 2

(8/4)/2=1,but8/(4/2)=4 (8/4)/2 = 1, \textrm{but} \\ 8/(4/2) = 4

Associativity and commutativity are independent

define a(+)b = a+int(b), then a(+)(b(+)c) = (a(+)b)(+)c, but a(+)b != b(+)a

Example by D.S Grimsditch in The Mathematical Gazette Vol 55 No. 393, I learned about it from John Cook.

Desargue's theorem is equivalent to associativity

Put a projection center (eye, viewpoint) on a plane. Draw three lines through that point, and two triangles with vertices on these three lines. You'll find that you can extend the sides of the triangles such that the points these meet, again, lie on a line.

Desargue's theorem can be proved for projective spaces having 3 or more dimensions, but in 2 dimensions there are non-Desarguian (projective) planes!

Just as Pappus' theorem says that the coordinate ring is commutative (its multiplication), Desargue's theorem says that it's associative.

measuring associativity: the associator

a(bc)(ab)ca(bc) - (ab)c

Tamari lattice

Haya Friedman and Tamari (1967) and later simplified by Samuel Huang and Tamari (1972)

TnT_n can be defined as the poset of all parenthesizations of nn variables with the order generated by rightwards reassociation (ab)c < a(bc).

or equivalently as the poset of all binary trees with n internal nodes.

Associahedra or Stasheff polytopes

Stasheff expressed that these should rather be called Tamari-Stasheff polytopes.

Jim Stasheff wrote a paper about convex n-polytopes on which we can conveniently map those expressions with n variables that the associative law makes equivalent. For n=4, this is a pentagon. Each corner is one such expression, and we get an edge between every pair of coners which differ only by a single bracket change:

  a((bc)d)  (a(bc))d

a(b(cd))      ((ab)c)d

       (ab)(cd)

For n=5 we get a 3-polyhedron which looks like a cube where one has cut off three edges with different orientations such that there is no vertex joining two of them.

It contains a few (non-regular) pentagons, which correspond to associahedra of subexpressions.

Loday's realization

Jean-Louis Loday found a simple way to realize Associahedra as a convex hull of integer coordinates.

Wikimedia Commons http://commons.wikimedia.org/wiki/File:Polytope_K3.svg

Jean-Louis Loday, Realization of the Stasheff polytope, Archiv der Mathematik 83 (2004), 267-278. (https://dx.doi.org/10.1007%2Fs00013-004-1026-y)

example: categories are associative

Associativity can be seen as a defining property for category theory.

associativity is commutativity on a higher level, part 1

We can combine our multiplication with an element to obtain a left-operator or a right operator. This allows us to write associativity as a form of commutativity:

(l_a o r_c) b = (r_c o l_a) b

if l_x = r_x then we have plain commutativity

This can be extended to arbitrary n! Given a syntax tree, we can imagine to swap neighbouring parts of the tree. Higher levels of associativity should allow rotating larger parts of the tree, without implying smaller rotations! Thanks again to Jason Hise on Twitter for prompting me to look at this generalized form of associativity!

associativity is commutativity on a higher level, part 2

The wedge product is associative, and it can give us a geometrict intuition about associativity which turns out to be very similar to commutativitiy.

Wedging two vectors measures the signed area of the prallelogram spanned by the vectors. Wedging three vectors does the same for the three dimensional prallelpiped. Appending the third vector to our product is like sweeping the area spanned by the first two along the third vector.

Now, if the wedge product were commutative, then we could combine three vectors at will, and expect that to give the same area. But that's not quite true, because switching two vectors in a wedge product will also switch the sign of the result. So we can't do that, but we can still change the order in which we evaluate subexpressions.

So the product abca \wedge b \wedge c is the area aba \wedge b swept along cc, or the product bcb \wedge c swept along a!

Intuitively, we could also sweep cac \wedge a along bb, and that's actually true for the wedge product! In general, we just have to make sure to compensate any sign flips caused by bringing aa and cc together by either wedging bb from the left or right respectively.

generalization: power associativity

Power associativity looks like associativity, but is only allowed if all operands are the same:

(xx)x=x(xx) (x x) x = x (x x)

https://en.wikipedia.org/wiki/Power_associativity

Obviously, any associative algebra is also power associative. The same is true for alternative algebras, like the octonions.

example: octonion multiplication is nonassociative

instead, they're alternative!

generalization: alternative algebras

Alternative algebras are a bit more general:

x(xy)=(xx)yleft alternative identityy(xx)=(yx)xright alternative identityx(yx)=(xy)xflexible identity x(xy) = (xx)y \textrm{left alternative identity} \\ y(xx) = (yx)x \textrm{right alternative identity} \\ x(yx) = (xy)x \textrm{flexible identity}

Any two of these imply the other. These are just those algebras for which the associator is alternating:

(ab)ca(bc)=1 (ab)c - a(bc) = -1

The octonions are nonassociative, but an alternative algebra.

generalization: Jacobi identity

Jacobi's identity is a mutant version of associative law:

a×(b timesc)=(a×b)×c+b×(a×c) a \times (b \ times c) = (a \times b) \times c + b \times (a \times c)

It is a defining feature for Lie algebras.

example: hyperbolic vector addition is nonassociative

The addition of vectors goes back to the combination of line segments, and is usually defined using a parallel of A throught the tip of B. In hyperbolic space, this isn't uniquely defined, so instead we'd draw a line from -B to A/2, and then lengthen that line so it's twice as long. That definition is unique and gives the usual vector sum in the euclidean case. However, this is not associative.

As explained earlier, this implies that hyperbolic vector addition isn't commutative either. The difference between A+B and B+A is a rotation. Both sums give a hyperbolic vector of the same length, and after noting that it's obvious that the transformation must be a rotation. More surprisingly the difference between (A+B)+C and A+(B+C) is also a rotation!

Associativity is an euclidean property!

But the Bol identity holds for hyperbolic vector additon! It also holds for quandles!

generalization: Bol identities

There are two Bol identities, one for a left Bol loop

a(b(ac))=(a(ba))c a(b(ac)) = (a(ba))c

and one for a right Bol loop:

((ca)b)a=c((ab)a) ((ca)b)a = c((ab)a)

Bol loops are also power associative. Either of these identites has the interesting consequence that any left inverse results in the existence of a right inverse.

Bol loops admit a slight generalization to Bruck loops, where (ab)1=a1b1(ab)^{-1} = a^{-1}b^{-1} also holds, and those have applications in special relativity.

https://en.wikipedia.org/wiki/Bol_loop

Moufang loops

Moufang loops in many ways similar to groups, just that they are not associative.

Any Bol loop which is both, a left Bol loop and a right Bol loop is a Moufang loop. Or you could just take one Bol identity together with the flexible identity (see alternative algebras above) and derive the other Bol identity from that. All this can be written down in a more symmetrical way known as Moufang identities:

z(x(zy))=((zx)z)yx(z(yz))=((xz)y)z(zx)(yz)=(z(xy))z(zx)(yz)=z((xy)z) z(x(zy)) = ((zx)z)y \\ x(z(yz)) = ((xz)y)z \\ (zx)(yz) = (z(xy))z \\ (zx)(yz) = z((xy)z)

An alternative notation can be given using left and right operators. This is equivalent to the first two identities:

LzLzLz(y)=Lzzz(y)RzRyRz(x)=Rzyz(x) L_z L_z L_z (y) = L_{zzz} (y) \\ R_z R_y R_z (x) = R_{zyz} (x)

Lz(x)Rz(y)=LzRz(xy)=RzLz(xy) L_z (x) R_z (y) = L_z R_z (xy) = R_z L_z (xy)

Moufang loops also require the inverse property, which implies that left and right inverses exist:

x1(xy)=y=(yx)x1 x^{-1}(xy) = y = (yx)x^{-1}

Using inverses we can write the left and right identities in a more useful form:

(xy)z=(xz1)(zyz)x(yz)=(xyx)(x1z) (xy)z = (xz^{-1})(zyz) \\ x(yz) = (xyx)(x^{-1}z)

https://en.wikipedia.org/wiki/Moufang_loop

Any Moufang loop is an alternative algebra, which can be seen by setting various variables to the identity.

Octonion multiplication without zero forms a Moufang loop.

Links

Alexander Postnikov, Permutohedra, associahedra and beyond http://math.mit.edu/~apost/papers/permutohedron.pdf

The n-Category Lab on associativity: https://ncatlab.org/nlab/show/associativity