Commutative, but not associative

I’ve been wondering for awhile if commutativity implies associativity in mathematics. That is, for any given binary operation, if it is commutative, is it also associative?

I’ve never seen this implication stated, but I’ve also never thought of a counter-example. Until now! So I thought I’d quickly share it.

First, to state the problem – every commutative operation I’ve seen is also associative. This means that if a * b = b * a, for any given operation *, then it’s also true that a * (b * c) = (a * b) * c.

It somehow makes intuitive sense that commutativity be a “more powerful” property than associativity. After all, if an operation can have its terms switched, and survive intact, surely it can weather a little order-of-operations rearrangement!

In any event, I came up with this function which is commutative, but not associative. In Haskell:

f :: Ord a => [a] -> [a] -> [a]
f x y = if x < y then x ++ y else y ++ x

It takes two lists, and concatenates them in sorted order. Thus, swapping the operands has no effect on the outcome, but the operation (like regular concatenation) is inherently non-associative.

[2] `f` ([1] `f` [3]) == [1,3,2]
([1] `f` [3]) `f` [2] == [1,3,2] (commutes)
([2] `f` [1]) `f` [3] == [1,2,3] (does not associate)

Mandelbrot Set – A Rorschach test on fire

I’ve been listening to the marvellous works of Jonathan Coulton (best known among gamers for Still Alive, the song at the end of Portal). These songs are nerdy and great, and really get in your head.

Now when a song gets in my head with the chorus lyrics:

Just take a point called c in the complex plane. Let z₁ be z squared plus c. And z₂ is z₁ squared plus c. And z₃ is z₂ squared plus c, and so on. If the series of z‘s will always stay close to z and never trend away, that point is in the Mandelbrot set.

- From the song Mandelbrot Set by Jonathan Coulton – free download

My inner code monkey can’t help but want to implement it. So I did.

I resolved to implement a program which generates a view of the Mandelbrot set just using the lyrics of the song, plus this blog post I found by the song’s author with some minor addenda:

• You take a point called c, not z, in the complex plane (I corrected the lyrics above; you can easily hear “Zee” as “C” in the song anyhow).
• You need to initialize the first z to 0+0i.

With this in mind, I got out my trusty Python and started hacking away, writing the song lyrics in comments and filling in the code. I hit “go” and ended up with this:

Mandelbrot Set, computed just from the lyrics

(Note that it took a couple of goes to get the parameters right, but I didn’t have to tinker with the algorithm itself at all!)

Fantastic!! Instantly generated that famous “bulbous pointy form”.

Then I hit the wiki and got a few tips on producing a coloured version. With a little bit more hacking, I managed to produce this:

Coloured Mandelbrot Set

Note the colour bands: not an image compression artefact but a property of the method used to select the colour (based on the discrete number of iterations it took for the point to “trend away”). There’s a way the Wikipedia article suggests to solve this, which is how they generate the spectacular image at the top, but I haven’t get it working yet.

Also note that the coloured version is “just for fun”. This is a set of numbers – you’re either in or you’re out. The black pixels in the coloured version are in the set; the coloured ones basically show you by how much that pixel missed out on being in the set. But the first picture I generated is a mathematically correct (approximation of) the set itself.

I’d post the code, but I just figured out that WordPress doesn’t allow non-image attachments. Grr! I’ll figure out some way later on.

And by the way, because some of us were discussing it (from the same post),

I’ve always wanted for [Benoît Mandelbrot] to hear it, but I fear his corrections. Which is why I just emailed him the mp3. Hopefully he will not be offended by the line in which I joke that he is not dead (yet). Or by the above-described mathematical shortcomings. Or by the “too-much-rocking” that I put in there.

Well it looks like he at least read the lyrics, and was pretty impressed