You are currently browsing the category archive for the ‘group theory’ category.

For many years, my mother has baked a challah nearly every Friday for Shabbat. Occasionally, however, she asks me to do some portion of the challah making, possibly including the braiding. For reasons we’ll see later, I don’t like her braiding algorithm. This post includes several algorithms, written in a way that someone who knows what a braid group is can understand. (I never had much success following those series of diagrams I sometimes see; I always wished someone would write out the braiding process in terms of generators of the braid group, so that’s what I’m going to do here after I give the preliminary definitions.)

Wikipedia’s page on braid groups has lots of interesting things, so I’ll only write a few essential points here, leaving the reader to explore Wikipedia at eir leisure. I’m finding it a bit tricky to give a good informal definition of braids, so I’ll just assume that my reader knows roughly what a braid is and skip to the formal definition.

The braid group on n strands is the group B_n=\langle a_1,\ldots,a_{n-1}\mid a_ia_{i+1}a_i=a_{i+1}a_ia_{i+1} \text{ for } 1\le i\le n-2, \ a_ia_j=a_ja_i \text{ for } |i-j|>1\rangle. In terms of actually playing with braid strands, a_i means interchanging strand i with strand i+1 by putting strand i over strand i+1. It is pretty simple to see that these generators do indeed induce all possible braids (although I haven’t yet said what a braid is), and that the relations ought to hold. Now, of course, a braid is an element of the braid group.

The braid groups become rather complicated quite quickly. While B_0=B_1=0 and B_2=\mathbb{Z}, already B_3 is nonabelian, and it’s isomorphic to the fundamental group of the complement of a trefoil knot in \mathbb{R}^3.

Note also that there is a natural homomorphism \pi:B_n\to S_n that tells us where the strand that started in the i^\text{th} position ends up.

Okay, now it’s time for some challah braiding algorithms. My mother’s usual challah has four strands on the bottom and three on the top. The algorithm for the top braid is pretty natural: (a_1a_2^{-1})^n, where n is decided by the length of the dough ropes.

I’m more concerned about the element of B_4 used for the bottom braid. She uses (a_1a_2^{-1}a_3^{-1}a_2)^n.  If n=1, we have \pi(a_1a_2^{-1}a_3^{-1}a_2)=(142)(3) (in cycle notation). This is already bad news to me: one step of the algorithm produces a single fixed point! I think one step of the algorithm ought to give an n-cycle (here a 4-cycle) or else a pure braid (i.e. a braid in the kernel of \pi). But it gets worse: the strand that starts in position 3 has no undercrossings. So when we’re done, it sits on top of every other strand.

It turns out not to be so bad because the three-strand braid sits on top of the four-strand braid, so the central portion of the four-strand braid is not visible in the finished bread. But aesthetically (and mathematically), this feels like a serious flaw to me.

Fortunately, I found an alternate algorithm for four-strand braiding that lacks these flaws: (a_2a_1a_3^{-1})^n. If n=1, \pi(a_2a_1a_3^{-1})=(1243), which is nice. Furthermore, every strand has both overcrossings and undercrossings. So this is my new preferred braid.

Sometimes, however, it is preferable to braid with six strands. There was an article in the newspaper that explained how to do it, but I was unable to follow it. Fortunately, I found a YouTube video that shows someone doing it (possibly the same way; I can’t tell). I was able to transcribe this method in terms of generators of the braid group. However, I’m not quite sure where it is supposed to end, so my braid may be slightly different from the one shown in the video. The braid is the video is (e^{-1}d^{-1}c^{-1}b^{-1}a^{-1}(bcdeabd^{-1}c^{-1}b^{-1}a^{-1}e^{-1}d^{-1})^n, except that it might stop somewhere in the middle of the (\cdot)^n. I don’t really want to calculate \pi of this braid (computations like this have never been that easy for me), but I would guess that it is a 6-cycle if it stops at an appropriate moment. (Also, it’s not as complicated as the formula would make it seem, since there’s a lot of stuff like moving the strand on the right all the way over to the left, and it takes a lot of generators to express that, even though it’s not complicated when you’re actually braiding dough.)

We first consider integral lexicographic codes (henceforth lexicodes). We enumerate all (infinite to the left) sequences of nonnegative integers that differ in at least m positions from any previous sequence. The first few of these (with m=3) are the following:

…00000

…00111

…00222

…00333

…00444

…00555

…00666

and so forth. But after all those are done, we can continue with:

…01012

…01103

…01230

…01321

…01456

…01547

…01674

…01765

and so forth. After we have finished with all these, we can continue with

…02023

and so forth.

I think one of the nicest possible properties a code can have is linearity (i.e. it forms a vector space over some field). However, it might not appear that this lexicographic code is linear. First of all, there is no obvious field of scalars (since \mathbb{N} is certainly not a field). Furthermore, the addition and multiplication don’t work out correctly. If we add …00222 and …01012, we get …01234, but this is not in our lexicode. Multiplication doesn’t work either: if we multiply …01012 by 2, we get …02024, which is also not in our lexicode.

However, this lexicode is linear! It forms a vector space over the field of (finite) nimbers! So lexicographic codes are mysteriously connected to combinatorial games.

So that’s one kind of lexicode. We can also consider binary lexicodes. In this case, we will restrict ourselves to 24-bit binary lexicodes with m=8. The first few sequences are

000000000000000000000000

000000000000000011111111

000000000000111100001111

000000000000111111110000

000000000011001100110011

and so forth. The list will ultimately contain 4096 sequences. There are 759 of them that contain exactly 8 1’s. These 759 have a very interesting property: for any five-element subset of \{1,2,3,\ldots,24\}, there is exactly one (of the 759) sequences that has 1’s in exactly those five positions. In other words, these sequences form the Steiner system S(5,8,24).

Now for the simple groups. Well, the Mathieu group M_{24} is the automorphism group of S(5,8,24). M_{24} is one of the 26 sporadic finite simple groups.