Friday 27 June 2014

Group theory and fractals

So, it's been a long time since my triptych of posts on set theory and infinity. The reason was that I didn't really find the tone I was looking for, and I couldn't decide whether I was too technical, or not enough. I've had an idea in my brain for a while though, and I thought it was best to just keep trying, so without further ado, I'll just pretend last post isn't about 6 months ago, and jump right into it.

What I want to talk about this time is something called group theory. In this article, I plan to first explain what is group theory, which will be the rather technical part, but hopefully not too complicated, I'll try to give a few clues as to why is it super duper interesting, and I'll end up tying group theory with a cool thing about fractals I actually learned this year, which (hopefully) will be easy enough to comprehend.

The most obvious thing I can say, is that group theory is the study of groups. Now that I've effectively dodged the question, it's time to explain what a group is:

I've already explained what a set is, at its core, it's really just "a thing containing stuff". By which I mean that the elements of the set don't interact with each other, they're abstract stuff and that's it. So the only thing that can distinguish a set from the other, is its cardinality, which means the number of elements within the set.

A group is one of the simplest structure we can put on top of a set, basically, it's about creating (or having) a law that tells us how elements interact. A law is something that takes 2 elements in, and spit one out.

An example of this would be the set of all integers, with the addition. If I give you two numbers, and tell you to add them, you are effectively applying the "addition" law to 2 elements of the set.

A group is usually noted between parenthesis, with first the name of the set, and then the name of the law, like this: (G, +), unless the operation is obvious, in which case we'll simply call it G.

To be a group though, this law needs to satisfy a few conditions:

Let G be a set, and $\circ$ a law on the elements of G, then (G, $\circ$) is a group if:
1) For all a, b, and c in G, (a $\circ$ b) $\circ$ c = a $\circ$ (b $\circ$ c); (associativity)

2) There is an element e in G so that for all a in G, a $\circ$ e = a; (identity element)

3) For all a in G, there is an element b in G so that a $\circ$ b = e. (inverse element)

Back to our first example of integers and addition, we can now see that is indeed a group:

1) The addition is clearly associative, this is primary stuff.
2) 0 is the identity element: adding 0 to any integer does not change the integer.
3) For any integer, adding its opposite will give 0.

The addition does satisfy each of the 3 conditions, so integers with the addition form a group.

Do note though, that the set of all integers with the multiplication is NOT a group, because:
1) The multiplication is clearly associative (again, primary stuff);
2) 1 is the identity element;
3) If you take any integer other than 1 or -1; its inverse will not be an integer. The inverse element of 2 for instance would be $\frac{1}{2}$, which is clearly not an integer.

So integers with the multiplication can not be a group, because there are some elements who do not have an inverse within the set, which means the 3rd condition isn't satisfied.

Another thing worth mentioning: it is never, at any point, said that a group needs to be commutative. Which means that if (G, $\circ$) is a group, you do not necessarily have $a \circ b = b \circ a$. The easiest example of this that I know of is matrices multiplication, which isn't a very hard thing, but is mind-numbingly boring, so I'll refrain.

Now that we have our structure, and know how it works, we might be interested in trying to see what we can study given a group, here a few classic question that may arise when dealing with groups:
1) The existence of what we call a "subgroup". Basically, if you have (G, $\circ$) a group and you're able to pick some elements from G to form a subset G', and the result (G', $\circ$) is still a group, we'll say that G' is a subgroup of G.

If we stick to the example of the group of all integers, we could consider the group of all even integers. If you add two even numbers, you'll still get an even number, and you're obviously still satisfying all the conditions.

If you take all the odd integers though, it doesn't work. One reason might be that you don't have the zero. So let's consider all odd integers, plus zero. We're still stuck, because then, what does 1+1 equals to ? It can't be 2, since, in that new set G' containing only odd integers and zero, the two doesn't exist. Our law actually becomes ill-defined, which means we don't have a law, so this can't be a group.

2) The existence of a generating set. Again, let's take (G, $\circ $) a group. Can we create a subset A of elements of G so that, by using ONLY those elements and their inverse, and combining them using our law, we're able to reach every element of G ?

Again, back to our example. The set A is pretty easy to find here: $\lbrace 1 \rbrace $ actually fits the bill. You can reach any positive integer by just adding 1 again and again, and you reach any negative integer by adding its inverse, -1, again and again.

Do note that it's the only generating set though. Apart from all the obvious one (who would consist of just taking a generating set and just adding stuff on top of it), we can see that $ \lbrace 4, 7 \rbrace$ would also be a generating set. That's because 4 + 4 - 7 = 1, so if we want to reach a positive integer n, we just need to add 2n worth of 4, and n worth of -7. Actually, any pair of number who have no common divisor would make a generator set, that's just Bézout's identity.

3) If the group isn't commutative, a lot more questions present themselves, we may for example wonder if there's a subgroup of elements who actually are commutative (what we'll call the "center" of the group). Again, the easiest example for this comes with matrices, since we know that at least every multiples of the identity matrix will be in the center. That's a bit more technical though, and definitely something I want to talk about, but probably in another article.

So, that was basically my introduction to group theory. I'll try to find an interesting approach to it next time, probably introduce some interesting (and a bit less obvious) groups, and try to get some fun stuff to do with our definitions. But for now, I promised fractals ! But how can we go from such a dry concept to fractals ? Well, pretty easily actually.

We'll use something called the Cayley graph. Let's say we have our usual (G, $\circ$) a group. Let's also say that we have A a set of generators of G. Now we take up a sheet of paper, and we make a point, representing the identity element. Our first step will be easy: from the identity, we apply our operation to every element of A and our point. Once we've done that, we repeat that step from the points we just reached. Again, example:

Let's keep with our example of all integers, and $A = \lbrace 1 \rbrace$, our original point will be the 0.

1st step: we add 1 to 0 by drawing a line from 0 to 1, and we also subtract 1 from 0 by drawing a line from 0 to -1.

2nd step: we do the same operation, but starting from the points we just reached, which are 1 and -1. First, we add 1 to 1, and we reach 2. We also subtract 1 from 1, and get back to 0. We do the same from -1, we reach 0 again, and -2.

3rd step, same operation, starting from -2, 0, 2. The points we reach are now -3, -1, 1, and 3.

And now me iterate that process.

After applying that operation infinity times, we'll have drawn a line. Not very exciting... But that's because we took the boringest of all groups.

So let's take a different group this time, we won't bother saying what G is, because G will be a hot mess, let's just say that the operation will be a multiplication, that it is not commutative, and that our group will basically be the group generated by all the way of multiplying 2 elements, named a and b.

This is actually a VERY BIG groupe, since we are not assuming commutativity, it means that $ab \neq ba$. So basically the elements of our group will be all the words you can write using only a and b, without the right to move them around. So this would be an element of our group: aaababaababbabbabaababa. And it equals nothing except itself. And since you have no upper bound to the number of letters you can use to write a word, you clearly have an infinity of elements. Actually, you could make words using only a, and as long as you write "a" a different number of times, the numbers would not be equal. Which means we already have an infinite numbers of words using only the letter a...

So now, back to drawing our graph, we start from writing the identity element, and we have $A = \lbrace a, b \rbrace$, which means that we have 4 things to do to our neutral element: multiply by a, multiply by b, multiply by $a^{-1}$ (or "divide by a", if you prefer) and multiply by $b^{-1}$ (or divide by b).

Here are the results, in which I also reveal that I write like a 7 year old:









I did not label all extremities in the last one because 1) I'm lazy and 2) it only overcharges the drawing, and is not really necessary.

For those who don't know what exactly is a fractal, the rough idea is that it's a geometrical construction that usually has a iterative process, can always fit within a certain area, and yet have an infinite "length of line". For the curious, I'll add the proof that what I've defined is indeed a fractal, but it's probably safe to skip if you don't really care about that.

So, the exact process of drawing that fractals is actually as follow:
Initialization: Create a point. From that point, multiply it by each element of the set of generators of your group, and their inverse.
Iteration: From the points you've created on last step, multiply each of those by each element of the set of generators of your group, and their inverse. If you reach new points, draw them at a distance $\frac{1}{2^n}$, where n is the number of times you've iterated.

First of all, let's prove we can iterate ad nauseam on my drawing, an always fit within a certain area. For that, we'll calculate the maximum distance a point can be from the original point on the plane. Obviously, the furthest point at any given time will always be the one going straight forward (so, powers of a, powers of b, as well as their negative powers). So we just need to prove that those don't go at infinity. It's a pretty simple calculation, take it the way you want it, it's either Zenon's paradox, or it's a p-series or ("série de Riemann" for us Frenchies) for the math-savviest amongst us, anyway, we can easily say that no point will be further than a distance 2, so our drawing will always be contained within a circle of radius 2.

Now let's prove we have an infinite length of line. For that, we need to calculate the length we'll draw at each iteration. Which mean counting how many new lines we draw each time. Again, the calculation is fairly easy: either a point is "old", in which case it has 4 "neighbours", and will never draw any new line, or it's new, in which case it has one neighbour, and will draw 3 new ones on this iteration. So we need to count, at each step, how many point have only one neighbour.

After initialization, we have 4 points. Each of these will have one operation bouncing them back, and will create 3 new isolated points. On the next step, each of these points will also have one operation bouncing them back to an old point, and 3 operations who will create new isolated points. Which means that, at the n-th step, we'll create $4 \times 3^n$ new isolated points. So the length of line we'll actually draw at the n-th step will be:

$\underbrace{4 \times 3^n}_{number\ of\ lines} \times \underbrace{\frac{1}{2^n}}_{length\ of\ each\ line} = 4 \times \frac{3^n}{2^n} = 4 \times (\frac{3}{2})^n $

Which, again, pretty obviously goes to infinity. If you need to convince yourself, you can just valuate it for a few values:

At 1st step, we'll draw 14 units of line.
At 10th step, we'll draw $\approx$ 228 units of line.
At 100th step, we'll draw $\approx$ 1626244710140860949 units of line. Don't draw a 100 steps.


Finally, for an already long post, a quick return to group theory, for a quick proof. I said that there had to be an identity element, but can there be 2 ? The answer is no, and here's the proof why:

Let's take (G, +) a group, and let's assume we have $e_1$ and $e_2$ two identity elements. Then we have the following:

$e_1 + e_2 = e_1$

Because $e_2$ is the identity element, so $e_1$ has to be unchanged by the operation. But we also have:

$e_1 + e_2 = e_ 2$

Because $e_1$ is the identity element, so $e_2$ has to be unchanged by the operation. We then have:

$$\begin{cases}
e_1 + e_2 = e_1\\
e_1 + e_2 = e_1
\end{cases}
\Longrightarrow
e_1 = e_2$$


So there you go, introductive crash course to group theory, and an easy way to generate fractals with just letters and an operation. Hope you liked it, and maybe it'll take me less than half a year to write the sequel to this.