Cayley graphs of free groups and monoids

This is a Cayley graph:



Its nodes represent elements of the free group generated by {a, b}.  It goes out in 4 directions from the origin:  ${a, b, a^{-1}, b^{-1}}$.

This is an animated GIF of the same graph:

But it only recursively repeat in 3 directions, as $a \cdot a^{-1} = 1$ ("going backwards") is cancelled out.

The graph itself is of fractal dimension, but it is embedded on the 2D plane (of dimension 2), that is because the group is generated by 2 elements.

If we ignore the non-commutativity of the group, in other words $a \cdot b = b \cdot a$, then we don't have to shrink the edges, and the Cayley graph becomes a regular grid like this:

This can be regarded simply as the direct product of the generator groups {a} and {b}.  And it clearly shows why 2 dimensions are needed.

But interestingly, we can also plot the Cayley graph of a free group with 3 elements on the 2D plane.

My first attempt is to divide the full circle of $360^\circ$ into 6 points, with 3 points representing {a, b, c} and 3 others the inverses.  But unfortunately there is a "clash" between some elements:

So the solution is to shrink the edges not by 1/2 but by 1/3.  This is the result:

This trick can work for any number of generators, by just cutting 2n divisions of the full circle.  For example this is case n=4:

Case n=10:

Free monoids

What if we ignore the inverse elements, so we get free monoids?  We can have 4 elements {a, b, c, d} and the graph is as follows:

It is clear that the nodes are "space-filling" as every point in the square can be expressed as a binary fraction.

Thus every point uniquely identifies a word in the free monoid generated by 4 elements.  Beware that some edges are overlapping in this graph.

The case of n=3 monoid is a bit interesting, as it turns out to be the Sierpinsky triangle!

When n gets big, the monoid graphs looks exactly the same as the group graphs for n/2.  For example, this is monoid, n=20:

And this is monoid, n=100:

Code

The code is very short, written in HTML5 Canvas and Javascript.  You can download the .zip here.

Why the interest?

I am interested in this because the free groups / monoids can represent logical formulas (when the logic is in algebraic form).  If we add a "gray scale" or "colors" to the nodes, that gives them extra dimensions that can be regarded as truth values.  Thus, an entire knowledge base can be represented by such a continuously-colored graph.

In other words, we have a geometric representation of knowledge elements that can be multiplied and added together.  Multiplication is the monoid action, whereas addition is the scalar addition of truth (color) values.

I will write about this last idea in more details.... later :)