Monthly Archives: August 2011

Suugaku Girl supplementary handout for chapter 1: Sequences

Posted on by
Reply

That really isn't enough terms to identify as Fibonacci

Suugaku Girl is a manga about people who really like math. The great thing about it is that it contains a substantial amount of math. This is also great because it will give me plenty to blog about.

The first chapter of Suugaku Girl is about the main character’s initial meeting with Milka, our socially retarded genius meganekko. She just starts spouting out numbers and, for whatever reason, he feels compelled to guess what comes next. And that is apparently the beginning of this love story.

In the chapter, we’re introduced to a few sequences, some of which are famous and some of which you might not have considered a sequence. It’ll probably help to understand what a sequence is beyond just being a bunch of numbers in a prescribed order.

Formally, we define a sequence as a function $a:S\to R$. The set $S$ is basically our index and is $\{1,2,…,n\}$ if $a$ is a finite sequence or the set of natural numbers $\mathbb{N}$ if we’re dealing with an infinite sequence. Normally, functions are written as $a(n)$, but, as was alluded to before, we refer to terms by index as in $a_n$.

However, $R$ can be any set. In the case of Suugaku Girl, it seems to be sticking with integers, but we can have sequences of bitstrings, vectors, complex numbers, functions, or whatever. What this also means is that a sequence doesn’t necessarily need to have a “pattern”, but can really be any ordered list of numbers (or functions or vectors or…).

Milka also brings up the idea of infinite sequences. A lot of the time, people will try to “solve” a sequence by completing it when they’re given only the first few terms. But, like Milka suggests, what they’re doing in that case is assuming that the rest of the sequence goes on as initially implied. Really, we can define any sequence we like with any behaviour we like. Again, remember that a sequence can be anything we want it to be. In fact, the sequence that Milka defines using the digits of π is kind of like that in that it’s completely arbitrary and doesn’t really have the kind of sequence definitions we’re used to seeing.

For finite sequences, we can just list all of the terms of our sequence like $(1,1,1,1,1,1000000,1)$. Obviously, we can’t do that for an infinite sequence. Luckily, a lot of the time we define sequences that have some sort of useful pattern that we can represent in a succinct way. Sometimes, like the digits of π sequence, this is harder.

We can try to formally define all of the sequences that were given in the manga. For instance, the Fibonacci sequence $(a_n)_{n=1}^\infty$ is commonly defined as $a_n = a_{n-2} + a_{n-1}$, but we have to give the first two terms $a_1 = 1, a_2 = 1$. The second sequence (which we’ll call $(b_n)_{n=1}^\infty$) takes a bit more work to define. We’ll need to define $p_n$ to be the $n$th prime number and then we can define $b_n = p_n \times p_{n+1}$. The third sequence $(c_n)_{n=1}^\infty$ is easy, it’s just $c_n = n^n$. And we can formalize the last one, which I’ll call $(d_n)_{n=1}^\infty$, just like the first two with a few more words. We let $\pi = q_1q_2q_3\cdots$ be the decimal expansion of π. Then $d_n = 2\cdot q_n$.

So that’s all fine, but what exactly are sequences used for? I’m pretty sure everyone’s learned about arithmetic and geometric sequences in grade school. Obviously, we can study sequences and their behaviour on their own. We can talk about whether they increase or decrease or how fast they grow or whether they converge. Apart from that, I don’t remember seeing sequences used for something besides sequences until analysis.

Analysis is basically the field of pure math that formalizes the concepts that we’re introduced to in calculus and generalizes them to spaces. Limits are a fundamental idea in calculus and analysis and these are defined by how a sequence converges. And this is where those weird sequences of vectors or functions comes into play, since we can talk about the convergence of a sequence of vectors or a sequence of functions in these other spaces that we want to do analysis in.

That’s probably the easiest example of an “application” of sequences. For myself, over the last few months I’ve read about automatic sequences, which are sequences that can be generated by a deterministic finite automaton. This gives us a way to relate automata theory to number theory and algebra. For instance, once we have k-automatic sequences, we can talk about k-regular sequences and come up with power series with respect to certain rings and fields and bla bla bla.

If you ever want to find out what crazy sequence you might have a part of, check out the Online Encyclopedia of Integer Sequences.

Brian Mulroney on the Usagi Drop ending

Posted on by
4

「うさぎドロップ」/「 LC斐爾 」

One of the few famous quotes in Canadian politics is one by Brian Mulroney, leader of the Progressive Conservative Party of Canada and the 18th Prime Minister of Canada, during the 1984 campaign. As the leader of the Liberal Party of Canada that took over after Pierre Trudeau resigned, John Turner inherited Trudeau’s premiership (yes, we can swap prime ministers without elections) and government in the latter part of his term. Just before resigning, Trudeau had appointed a ton of loyalists to various positions.

Technically, it is the Governor General of Canada (who acts as the representative the Crown) who makes these appointments, but he or she only does so on the advice of the prime minister. In this case, the appointments had only been recommended by Trudeau but weren’t finalized by the governor general when Turner became prime minister, so he could have stopped them. During the 1984 leaders’ debate, Mulroney attacked Turner for allowing these appointments and Turner replied that he had no option. This was the lead-in to Mulroney’s famous line:

You had an option, sir. You could have said, ‘I am not going to do it. This is wrong for Canada, and I am not going to ask Canadians to pay the price.’ You had an option, sir — to say ‘no’ — and you chose to say ‘yes’ to the old attitudes and the old stories of the Liberal Party. That sir, if I may say respectfully, that is not good enough for Canadians.

This left Turner shattered in the debate and pretty much won the election for Mulroney. Unfortunately, ever since then, media coverage of electoral debates has always focused on finding that snappy equivalent knockout line, but no one has produced one since.

I like Usagi Drop. Yes, I have read the entire thing. No, the ending was not what I would have liked, but I’m not particularly angry about it. I mean, 95% of it was great, which is a far better ratio than most stuff out there. What’s more is that I think the initial reaction absent the surrounding context made it seem much worse than it actually was, especially with the important reveal that Rin isn’t actually Grandpa’s biological kid.

In fact, I’d say that I don’t really have a problem with most of the ending “arc” and it’s only the very last chapter that makes me raise an eyebrow. I can buy that Rin could have developed romantic feelings for Daikichi. After all, I think it’s an important note that she sees him as a guardian and not her father. He’s always simply been Daikichi to her.

The problem, then, and the part I find hard to believe is Daikichi’s response, which pretty much amounts to a ‘welp, guess I have no choice’. It’s really strange because, even though he was clearly uncomfortable the idea, he didn’t put up that much resistance. It’s strange enough that he offers to wait two years and hopes the problem might go away. After the two year wait period, Rin kind of goes ‘hey, it’s been two years’ and he’s sort of resigned to the whole thing.

What I’m struck by with Usagi Drop’s ending is that Daikichi had an option: he could have said no, but he chose to say yes. It would have been perfectly fine for him to say no. Rin couldn’t have seriously been expecting Daikichi to reciprocate. She would’ve been fine if things continued the way they were. She was prepared to have things stay the same. Things might’ve been awkward for a while, but a ‘no’ would have closed the matter. Instead, we’re left with, well, whatever it is that we have now.

I’d like to stress again that I still think the manga is excellent, even the second half of it. However, Daikichi’s response is baffling and his rationale is unconvincing. Quite frankly, it’s not good enough, especially for such an otherwise great manga. I’ll defend it, but I’ll concede that the end is not at all what I wanted.

Clannad again

Posted on by
Reply

「CLANNAD」/「嘎哦」

Much to dad’s disappointment, I finally played through the Clannad visual novel. At first, I figured that I wouldn’t get much out of it since the anime was a sufficiently faithful adaptation of the visual novel. Then, I was bored and figured that since I already friggin love Clannad so much, it wouldn’t hurt to go through it again.

For the most part, I’m pretty glad I did. The most impressive thing about the anime adaptation was that there were elements in both the anime and visual novel that I preferred over the other. The differences in what was chosen for adaptation were pretty minor. While they didn’t affect the overall character of the story, reading it again with those changed details makes it a slightly different experience.

I played it with a walkthrough and the first impression I had was being glad that someone made a walkthrough because that game would have been impossible to beat without one. It’s easily the hardest one I’ve played and has some weird flags, like completing certain routes immediately before other ones and other things that would’ve been impossible to know about. This is in addition to being long and having a billion routes with the most surprising characters getting their own routes.

Obviously, the biggest advantage the visual novel has over anime is time. Nothing felt rushed when I watched the anime, but seeing the relationships develop felt a lot more natural in the visual novel. This isn’t just limited to Nagisa and, obviously, it’s more important for each girl if you’re on their route. But I think the relationships that benefit the most from this are with the main players who aren’t Nagisa in After Story: Akio, Sanae, and Yoshino.

The most unsettling thing was watching Tomoya develop romantic relationships with girls who weren’t Nagisa. And not just that but almost every girl’s route. Like, Ryou, Kyou, Kotomi, and Tomoyo were okay, since I was sufficiently prepared for it by the anime. But Fuko, Yukine, and Misae were all lolwut.

It was surprising to see Nagisa’s route involving so many pieces of the other routes. It made it really easy for the anime to just take a sought detour and finish each route off. I think the route that changed the most in the anime was Yukine’s route, which had that weird drama with the brother being secretly dead. In other routes, though, Nagisa’s absence felt really strange. This is most obvious in the Sunohara siblings arc, when, Sanae is super eager to help you for no reason.

So what about the stuff that didn’t make the cut for the anime? Again, I have to note how impressed I am that the anime managed to fit almost everything in in a way that makes sense. Even some stuff that didn’t make it initially found its way back in through the extra episodes. Of that stuff, I didn’t find that reading it added much that the anime didn’t handle. Of course, I would be down for a Tomoyo After anime of some sort.

The biggest exclusion was Kappei’s route, which makes sense since he’s practically invisible until you decide to enter his route. That makes me wonder why his route is included in the game. Is it because they felt sorry for Ryou getting shafted hard in Kyou’s route? It’s really weird.

The other story that doesn’t happen in the anime is Akio’s little escapade. What I found kind of strange about his route is that it’s a branch off of After Story that gets its own ending. I don’t see why it couldn’t have just been rolled in with the rest of it like Sanae’s or Yoshino’s was.

While After Story remained largely the same, there are some important differences in the visual novel’s account of the development of Tomoya’s and Nagisa’s relationship. The visual novel doesn’t really give Nagisa many things to be happy about. I was surprised that their initial failure to get the theatre club going was actually the starting point of their formal relationship. And then there’s Nagisa getting sick almost immediately after the play and her terrible school life after Tomoya graduates.

There’s a lot more focus on their relationship too, since all of that running around doing stuff for and making friends with the other girls is all gone. In the anime, Nagisa is able to participate in all of this helping and friend making stuff, but in her story in the visual novel, she doesn’t really get any breaks like that. Basically, it’s all about how Tomoya and Nagisa build their relationship in spite of all the crap that gets thrown their way.

For the most part, the anime is excellent. It’s one of very few anime adaptations of a visual novel that’s a perfectly fine substitute for the anime. If you do choose to play it, do know that it is super long. Unless you have a lot of time and you really like Clannad, you probably won’t get much out of playing it instead of or after watching the anime.

The Future Gadget Lab vs. Kolmogorov complexity

Posted on by
6

「Steins;Gate」/「いさりび」

In Steins;Gate 12, the Future Gadget Lab is faced with a problem. They need to send a copy of a person’s memory, or about 3.24 TB, to the past, but they can only send 36 bytes. What is a MADDO SCIENTISTO to do? What they end up doing is sending that data to the Large Hadron Collider to compress with a black hole. Problem solved! Or is it?

Obviously, using a black hole to compress data is silly, since a black hole would probably just destroy the data. In fact, it’s probably unnecessary, since if it were physically possible to achieve that kind of compression, you’d be able to do it on any computer because of the Church-Turing thesis. The only thing that would change is how quickly the algorithm would run. Luckily, in theoretical computer science, when dealing with the question of whether something is possible or not, we don’t care how long it’ll take. So, is there a compression algorithm that can give us the desired result?

Basically what we’re doing when were compressing stuff is we’re trying to rewrite a bunch if zeroes and ones, or strings, into a smaller bunch of zeroes and ones that mean the same thing. In general, this is impossible to do, since there are less strings of zeroes and ones when you have less digits, so you can’t arbitrarily stuff, say eight bits of information into seven bits. What you can do is create a way to describe the zeroes and ones in a way that is smaller than what you start out with.

For instance, we can describe strings of zeroes and ones in plain English. It’s shorter to write “one hundred zeroes followed by one hundred ones” than writing

00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
11111111111111111111111111111111111111111111111111
11111111111111111111111111111111111111111111111111

The obvious problem with our compression scheme so far is that there are some strings that are not very easy to describe and it might be longer to describe in English than it would be to just write the bits themselves.

Again, it appears to be difficult to create a compression scheme that works for any old string. It’s much easier to create such an algorithm when you know something about the kind of string you want to compress, like if it’s a certain size or if it has any patterns or something. In the case of the FG lab, we know they won’t need to worry about compressing strings of length 288 or less. Unfortunately, there isn’t much more we know about the strings they want to compress other than the fact that they’re huge.

Actually, there’s another problem, which is that they need a way to decompress the string they’ve sent. If I give you a description of the string in English, it’s not going to do you any good unless you already know English. So in addition to sending a compressed string, they need to send information about the compression scheme they used, all in 36 bytes.

In information theory, the length of the shortest description of a string $x$ is its Kolmogorov complexity, which we’ll denote $C(x)$. Formally, $C(x)$ is defined in terms of encodings of Turing machines that generate $x$, but it’s pretty easy to argue that the choice of how we describe $x$ doesn’t matter up to a constant term.

We know that $C(x) \leq |x| + O(1)$ (where $|x|$ is the length of $x$), since we can always just write out $x$. We also know that for every length $n$, we can always find a string $x$ such that $C(x) \geq |x|$ since there are $2^n$ strings of length $n$ but only $2^{n-1}$ shorter descriptions of those strings. These strings that can’t be compressed are defined to be random.

We can quantify this idea of compressibility by saying that a string $x$ is $c$-compressible if $C(x) \leq |x| – c$. And so, we can argue about how likely it is that we have a string that can be compressed to the degree that we want. For strings of length $n$, we have that at least $2^n – 2^{n-c+1} + 1$ of them are incompressible by $c$.

We have some numbers, so let’s play around with them. Remember from earlier that the approximate size of Okarin’s memories is 3.24 TB, or $3.24 \times 2^{40} \times 8$ bits, while the limit we can send is 36 $\times$ 8 = 288 bits. If we want to squeeze Okarin’s memories into a text message, we’ll have
$$c = 3.24 \times 2^{40} \times 8 – 288 = 2.849934139166592 \times 10^{13}.$$
WolframAlpha helpfully tells me that this is slightly more than 1.4 times as many red blood cells in the human body.

We can calculate the probability that we have a compressible string by figuring out the probability that incompressible, which we can do with our lower bound on the number of incompressible strings we have. Taking $n = 3.24 \times 2^{40} \times 8$, the probability is given by
$$1 – \frac{2^n – 2^{n-c+1} + 1}{2^n} = \frac{1}{2^{c-1}} – \frac{1}{2^n}.$$
Plugging our numbers in, we get
$$\frac{1}{2^{3.24 \times 2^{40} \times 8 – 288 – 1}} – \frac{1}{2^{3.24 \times 8 \times 2^{40}}}.$$

And unfortunately, after this step, WolframAlpha kind of refused to try to do the computation. I gave it a shot on my laptop in Python but all that happened was CPU usage went up to 100% for a few minutes and it started eating all of my memory. I kind of wanted to keep using my computer instead of waiting it out for a MemoryError exception, so I interrupted it. Doing some further estimation, I threw $2^{2^{40}}$ at WolframAlpha, since it’s kind of about the same neighbourhood in magnitude as the number we’re trying to get. Apparently, it’s a number that’s about 300 billion digits long, so one in that are the kind of odds you’re looking at.

I guess this is another way of saying there’s no chance in hell that what the FG Lab tried to do would ever work. And remember that we’re not talking about any particular compression algorithms or technologies here. We can’t come up with a better algorithm or scheme. We can’t use faster computers. We can’t use quantum computers (Holevo’s theorem says that we can’t, in general, use less qubits than classical bits for the same string). From an information theoretic standpoint, it is impossible.

But I’m pretty sure everyone already could’ve guessed that anyway.