The 3rd annual π day anime and mathematics post: A symmetric group of friends of degree 5

「ふいにコネクト」/「ものくろあくたー。」

It’s that day of the year again.

Kokoro Connect’s premise made a lot of people raise their eyebrows, because really, what good can come from body-switching shenanigans? Well, let’s think about this for a second. We have a group of five kids and every once in a while, at random, they switch into the others’ bodies at random. What does that sound like? That’s right, a permutation!

Interestingly enough, the idea of connecting body-switching with permutations isn’t new. The Futurama writers did it and apparently got a new theorem out of it. What differs in the case of Kokoro Connect and Futurama is that in Futurama, the body-switching could only happen in twos. These are called transpositions. Obviously, this isn’t the case for Kokoro Connect. This doesn’t make too much of a difference since it turns out we can write out any permutation we want as a series of transpositions, but that wouldn’t be very fun for Heartseed.

We write permutations in the following way. If we let Taichi = 1, Iori = 2, Inaban = 3, Aoki = 4, and Yui = 5, we’ll have $(1 2 3 4 5)$ representing the identity permutation, when everyone’s in their own body. If Heartseed wanted to make Aoki and Yui switch places, he’d apply the following permutation
$$ \left( \begin{array}{ccccc} 1&2&3&4&5 \\ 1&2&3&5&4 \end{array} \right) $$
While it’s helpful for seeing exactly what goes where, especially when we start dealing with multiple permutations, this notation is a bit cumbersome, so we’ll only write the second line ($(12354)$) to specify a permutation.

For the purposes of this little exercise, we’ll consider applying a permutation as taking whoever’s currently in a given body. That is, say we permute Aoki and Taichi to get $(4 2 3 1 5)$. In order to get everyone back into their own bodies, we have to apply $(4 2 3 1 5)$ again, which takes Aoki, who’s in Taichi’s body, back into Aoki’s body.

So let’s begin with something simple. How many different ways are there for the characters to body switch? Both who is switched and who they switch with is entirely random. Again, since the switches aren’t necessarily transpositions, this means that we can end up with cycles like in episode 2, when Yui, Inaban, and Aoki all get switched at the same time. This can be written as $(1 2 4 5 3)$.

But this is just the number of permutations that can happen on a set of five elements, which is just 5! = 120. Of course, that includes the identity permutation, which just takes all elements to themselves, so the actual number of different ways the characters can be swapped is actually 119.

Anyhow, we can gather up all of these different permutations into a set and give it the function composition operation and it becomes a group. A group $(G,\cdot)$ is an algebraic structure that consists of a set $G$ and an operation $\cdot$ which satisfy the group axioms:

  • Closure: for every $a$ and $b$ in $G$, $a\cdot b$ is also in $G$
  • Associativity: for every $a$, $b$, and $c$ in $G$, $(a\cdot b)\cdot c = a\cdot (b\cdot c)$
  • Identity: there exists $e$ in $G$ such that for every $a$ in $G$, $e\cdot a = a \cdot e = a$
  • Inverse: for every $a$ in $G$, there exists $b$ in $G$ such that $a\cdot b = b\cdot a = e$

In this case, we can think of the permutations themselves as elements of a group and we take permutation composition as the group operation. Let’s go through these axioms.

Closure says that if have two different configurations of body swamps, say Taichi and Iori ($(2 1 3 4 5)$) and Iori and Yui ($(1 5 3 4 2)$), then we can apply them one after the other and we’d still have a body swap configuration: $(2 5 3 4 1)$. That is, we won’t end up with something that’s not a body swap. This seems like a weird distinction to make, but it’s possible to define a set that doesn’t qualify as a group. Say I want to take the integers under division as a group ($(\mathbb Z, \div)$). Well, it breaks closure because 1 is an integer and 2 is an integer but $1 \div 2$ is not an integer.

Associativity says that it doesn’t matter what order we choose to apply our operations in. If we have three swaps, say Taichi and Inaban ($(3 2 1 4 5)$), Aoki and Yui ($(1 2 3 5 4)$), and Iori and Yui $(1 5 3 4 2)$ and we want to apply them in that order. Then as long as they still happen in that order, it doesn’t matter which one we apply first. We’d have
$$((32145)(12354))(15342) = (32154)(15342) = (34152)$$
and
$$(32145)((12354)(15342)) = (32145)(14352) = (34152)$$

The identity means that there’s a configuration that we can apply and nothing will change. That’d be $(12345)$. And inverse means that there’s always a single body swap that we can make to get everyone back in their own bodies.

As it turns out, the group of all permutations on $n$ objects is a pretty fundamental group. These groups are called the symmetric groups and are denoted by $S_n$. So the particular group we’re working with is $S_5$.

So what’s so special about $S_5$? Well, as it turns out it’s the first symmetric group that’s not solvable, a result that’s from Galois theory and has a surprising consequence.

Évariste Galois was a cool dude, proving a bunch of neat stuff up until he was 20, when he got killed in a duel because of some drama which is speculated to be of the relationship kind, maybe not unlike Kokoro Connect (it probably wasn’t anything like Kokoro Connect at all). Among the things that he developed was the field that’s now known as Galois theory, which is named after him. What’s cool about Galois theory is that it connects two previously unrelated concepts in algebra: groups and fields.

One of the most interesting things that came out of Galois theory is related to the idea of solving polynomials. I’m sure we’re all familiar with the quadratic formula. Well, in case you aren’t, here it is:

$$x = \frac{-b \pm \sqrt{b^2 – 4ac}}{2a}$$

This neat little formula gives us an easy way to find the complex roots of any second degree polynomial. It’s not too difficult to derive. And we can do that for cubic polynomials too, which takes a bit more work to derive. And if we want to really get our hands dirty, we could try deriving the general form of roots for polynomials of degree four. And wait until you try to do it for degree five polynomials.

That’s because, eventually, you’ll give up. Why? Well, it’s not just hard, but it’s impossible. There is no general formula using radicals and standard arithmetic operations for the roots for any fifth degree (or higher!) polynomial. The reason behind this is because $S_5$ is the Galois group for the general polynomial of degree 5. Unfortunately, proving that fact is a bit of a challenge to do here since it took about 11 weeks of Galois theory and group theory to get all the machinery in place, so we’ll have to leave it at that.

The 2nd annual π day anime and mathematics post

「涼宮ハルヒの消失」/「茨乃」

Happy $\pi$ day. Once again, Nadeko will bring us in:

Snowy Mountain Syndrome is the third story in The Rampage of Haruhi Suzumiya, the fifth volume of the light novel. It’s the first story that has yet to be animated. It’s also a story that contains the dread spectre of mathematics.

So our SOS-dan is stuck in a mysterious cabin in the middle of a snowstorm on a mountain. They find a mysterious contraption that has an equation displayed:

$$x-y=(D-1)-z$$

and they are to provide $x$, $y$, and $z$. Koizumi and Kyon are confused, but Haruhi rightly identifies this equation as Euler’s polyhedron formula, which is also very often referred to as just Euler’s formula. If you’re referring to it in context, it doesn’t matter that much, but it’s useful to distinguish between all the other things that Euler discovered, which is a hell of a lot.

First, we should probably go over some basic definitions. When we talk about graphs, we’re not talking about bar graphs or pie charts or the like. We’re also not talking about graphs of polynomials on a cartesian plane or other such functions. Graphs are a mathematical structure which, when drawn, looks like a bunch of circles and lines.

Formally, a graph is a pair $G = (V,E)$ where $V$ is a set of vertices and $E$ is a set of edges. Vertices can be any old thing, but each edge is defined as a pair $(u,v)$ where $u$ and $v$ are vertices in $V$. When we draw graphs, we just draw a vertex as a circle and draw an edge as a line that connects the two vertices it’s defined as.

And that’s it! That’s the most general definition of a graph, which means we can end up with a graph that’s completely empty or a graph that’s just a bunch of vertices with no edges in between them. We can even have multiple edges going in between two vertices. Of course, often times, we’d like to add some more constraints, depending on what we want to do with our graphs. Very often, we’d like to restrict the number of edges between two vertices to one and that’s what we’ll do.

Back to the formula, usually it’s given as $\chi=v-e+f$, where $v$ is the number of vertices, $e$ is the number of edges, $f$ is the number of faces, and $\chi$ is called the Euler characteristic. That makes $x=v$, $y=e$, $f=z$ and $D-1=\chi$. Now, the only thing here that we haven’t seen defined yet is a face. Intuitively, we can see that’s just the space that’s bounded by the edges.

What I find strange is the explanation in the novel that $D$ stands for the dimension of the polyhedra. As far as I know, this only works in the three-dimensional case for platonic solids. Once we generalize the structures to other kinds of polyhedra and topological surfaces, that analogy breaks down.

Anyhow, the way the formula is applied in the book is the use that I’m most familiar with, which is as a property of a planar graph. For planar graphs, $\chi=2$. In the novel, they deduce that $\chi=1$ since $D=2$ and that only works because they didn’t count the large face outside of the edges as a face, which we usually do.

But what is a planar graph? Well, if you go back to our definition of a graph, you might notice that all we’ve done is said that it’s a bunch of vertices and edges. We’ve said nothing about how to draw a graph. Usually, we represent vertices as circles and edges as lines in between those circles, but other than that, there’s really nothing telling you what order to draw your circles in or whether your lines have to be completely straight or not or how far apart everything has to be. How you choose to represent your graph is up to you, although if you draw your graph weirdly, you might make the people trying to read it angry.

Informally, a planar graph is a graph that you can draw with none of the edges crossing each other. This seems like a kind of silly thing to be worried about, because it seems like you could just keep on drawing a graph until it works out. Well, for edges with a lot of vertices and edges, it’s not obvious and even for really small graphs. For instance:

At a glance, it doesn’t look like the drawing on the right is planar, but all we have to do is drag one of the vertices into the middle to get the drawing on the left and it turns out they’re both the same graph, $K_4$, the complete graph of order 4.

That’s where Euler’s formula comes in really handy. It gives us a way of figuring out whether or not our graph is planar or not without having to fiddle around with placing edges properly and stuff. You already know how many vertices and edges you’ve got, so all you need to do is make sure you’ve got the right number of faces.

So it’s probably pretty clear at this point that you can’t draw every graph without the edges crossing. We can say something interesting about those graphs too, which just turns out to be another characterization of planar graphs, but oh well. But first, we have to introduce the concept of graph minors.

Suppose we have a graph $G=(V,E)$ and an edge $e=(u,v) \in E(G)$. If we contract the edge $e$, we essentially merge the two vertices into a new vertex, let’s call it $w$, and every edge that had an endpoint at $u$ or $v$ now has $w$ as the corresponding endpoint. Then a graph $H$ is a graph minor of $G$ if we can delete and contract a bunch of edges in $G$ to get $H$ (or a graph that’s isomorphic to $H$).

It turns out that every non-planar graph can be reduced to a minor of one of two graphs. The first is $K_5$, the complete graph of order 5:

The second is $K_{3,3}$, the complete bipartite graph 3,3:

These two graphs are the smallest non-planar graphs, otherwise we’d be able to reduce them further to get another non-planar graph. Like I mentioned before, this is a characterization for planar graphs too, since a planar graph can’t contain a $K_5$ or $K_{3,3}$ minor.

I guess I’ll end by saying that graphs are hella useful, especially in computer science. A lot of people complain about never using math like calc ever. If you’re a developer, you’ll run into graphs everywhere. It’s pretty amazing how many structures and concepts can be represented by a bunch of circles and lines.

The (1st annual?) π day anime and mathematics lecture

Happy $\pi$ day. We’ll begin with an obligatory video.

One of the reasons I enjoyed Summer Wars so much is because the main character’s superpower is math. Well, okay, you say, he’s really good at math, but so what? A lot of people complain about the implausibility of OZ, but those of us with a basic understanding of cryptography and number theory will have been drawn to Kenji’s quick problem solving work with an eyebrow raised. So let’s talk about why Kenji is a wizard.

Kenji doing some friggin mathematics

Kenji doing some friggin mathematics

We’ll start with modular arithmetic, which Kenji mentions to Natsuki on the train ride to Ueda. When we divide numbers, we often end up with remainders. Suppose we divide some integer $k$ by $N$ and we get a remainder of $r$. Then we say that $k$ and $r$ are equivalent $\bmod{N}$ and we denote that by $k = r \bmod{N}$. Because it’s how division works, for any integer $k, r$ will be some number from $0$ to $N-1$. It turns out a lot of arithmetic operations work the same way in modular arithmetic: adding, subtracting, and multiplying numbers and then taking the modulus of the result will give you the same number as adding, subtracting, and multiplying the moduli of the numbers you started out with.

However, division doesn’t work as we would expect it to. So we have to think about division (or the equivalent operation) differently. Instead of thinking of division as splitting a group of stuff into smaller groups, we’ll think of it as multiplying by an inverse. What’s an inverse? Well, we can try thinking of it in terms of addition. It’s pretty intuitive that subtraction is the opposite of addition. If we have some integer $k$, then the additive inverse of $k$ is $-k$. When we add $k$ and $-k$, we get $0$, the additive identity. The identity is just the special number that we can add to anything and get that same thing back unchanged ($n+0 = n$). In the same way, if we multiply $k$ by its inverse, $k^{-1}$, then we’ll get $1$, since $k \times 1$ is just $k$ again. What this means is that the inverse of $k \bmod{N}$ is just some other number $j$ from $0$ to $N-1$ such that $j\cdot k = 1 \bmod{N}$ and it’s just multiplication again.

Now, the problem with this is that it’s not guaranteed that there’s always an inverse hanging around in $\bmod{N}$. In particular, if $k$ and $N$ share any divisors, then $k$ won’t have an inverse $\bmod{N}$. This is interesting because it also tells us that if we consider integers mod a prime number $P$, then every integer $\bmod{P}$ has an inverse, since $P$ doesn’t share any divisors with any integers from $0$ to $P-1$. We call these things that have inverses units. So if we have a unit $k$, then $k^m$ is also a unit, for any integer $m$. We even have a funny function $\phi$ defined such that $\phi(n)$ is the number of units in $\bmod{n}$.

Love Machine solicits help

Love Machine solicits help

So taking everything we’ve learned, we can set up a cryptosystem! The one we’ll be looking at is called RSA, after the guys who invented it. We have Bob who wants to securely send a message $M$ to Alice. Alice chooses two prime numbers $p$ and $q$ and figures out $m = pq$. She also goes and figures out $\phi(m)$, which happens to be $(p-1)(q-1)$. Finally, she picks some integer $k$, a unit in $\bmod{\phi(m)}$. She lets everyone know $m$ and $k$, but she keeps $p$, $q$, and $\phi(m)$ secret.

So Bob wants to send $M$, which is just his message conveniently in number form. He makes $M$ into a number between $0$ and $m$, and if $M$ is too big, he can just break it up into chunks. Bob figures out the smallest $b$ such that $b = a^k \bmod{m}$ and sends $b$ over to Alice. Now, since Alice has $k$ and $\phi(m)$, she can also find $k^{-1}$ pretty easily. Once she has that, she can get the original message by figuring out $b^{k^{-1}} = (M^k)^{k{-1}} = M \bmod{m}$, since $kk^{-1} = 1 \bmod \phi(m)$.

The interesting thing here is that all of the information is out there for someone to encrypt a message to send to Alice, but no one is able to decrypt it. Well, they’re able to decrypt it if they know what $p$ and $q$ are, since once they’ve got that, they can get $\phi(m)$. But it turns out getting $p$ and $q$ from $m$ (which Alice just throws up on the interwebs) is really hard. And it really works for reals, because RSA is pretty widely deployed for things like keeping your credit card information safe while you send it through the tubes to Amazon.

A conveniently displayed ciphertext

A conveniently displayed ciphertext

Let’s go back and think about units some more. Of course, there are only $N$ numbers in the integers $\bmod{N}$, so there’s a point at which $k^m$ is just $1$ again and starts over. If $k^m = 1 \bmod{N}$, we say that $m$ is the order of $k$. But why do we care about finding the order of $k$?

It turns out finding the order of elements is very, very similar to factoring an integer into primes and other related problems, like discrete logarithms. If we can find orders of elements, it won’t be too hard to figure out how to factor a number. In this case, the eavesdropper wants to figure out what $p$ and $q$ are, so they’ll want to factor $m$. And it turns out a lot of other public-key cryptosystems (like elliptic curves) are based on the difficulty of factoring.

How hard could it be? Well, we could just check every possibility, which doesn’t seem that bad for a number like 48, but once we get into numbers that are hundreds of digits long, that might start to suck. It turns out the fastest known algorithms for order finding take approximately $e^{O(\log N \log \log N)^{\frac{1}{2}}}$ steps. Current key lengths for RSA are at least 1024 bits, which would give us about 4.4 x 1029 operations. Assuming three trillion operations per second (3 GHz), it’d take a PC about 4.7 billion years. Sure, you could just throw more powerful computers at it, but they’d just double the key size and suddenly, you’d need to do 1044 operations.

It's a lot easier to write math than typeset it

It's a lot easier to write math than typeset it

Well, that’s not entirely true. One of the breakthroughs in quantum computing was coming up with a fast algorithm for factoring. It turns out quantum order finding takes $O((\log N)^2 \log \log N \log \log \log N)$ steps, which, for a 1024-bit key is just over 60 operations. Doubling the key-size to 2048 bits only increases the number of operations by just over 20. Unfortunately (or fortunately, because we’d be pretty screwed if someone could easily break RSA right now), we haven’t built any quantum computers that large yet, nor are we capable of doing so anytime soon.

tl;dr – Kenji is a quantum computer.