Suugaku Girl supplementary handout for chapter 2: Prime numbers

She doesn't seem that excited

So last time, Tetra was being enlightened by MC-kun about definitions. This actually arises from MC-kun using prime numbers as a motivating example.

Primes are megas important in mathematics and even more important today. The entire branch of mathematics called number theory is all about studying the properties of prime numbers. They’re so useful that we’ve done stuff like extend the notion of prime elements to algebraic structures called rings or apply analytic techniques to learn more about them, but we’ll stick with elementary number theory for now.

Now, for hundreds of years, we’d been studying number theory only because it’s cool and mathematicians love prime numbers. Last time, I mentioned some examples of math preceding useful applications. Well, number theory is a really good example of that, because in the 70s, we found a use for it, which is its main use today, in cryptography. There have been some new techniques using some algebra as well, but for the most part, modern cryptography relies on the hardness of factoring primes. Neat!

Okay, so we’re back to the original question that MC-kun tries to get Tetra to answer, which is, what is a prime number?

Definition. An integer $p$ is prime if and only if $p\geq 2$ and the only positive divisors of $p$ are 1 and itself.

MC-kun explains that the motivation for excluding 1 from the definition of a prime number is because we want to be able to say that we can write every number as a unique product of prime numbers. This is very useful, because now we know we can break down every number like this and we can tell them apart because they’re guaranteed to have a unique representation. This is called unique prime factorization.

Theorem. Let $a > 0$ be an integer. Then we can write $a = p_1p_2\cdots p_k$ for some primes $p_1,\dots,p_k$. This representation is unique up to changing the order of terms.

We can show this by induction on $a$. We’ve got $a=2$ so that’s pretty obvious. So let’s say that every integer $k\lt a$ can be decomposed like this and suppose we can’t decompose $a$ into prime numbers, assuming $a$ itself isn’t already a prime since it would just be its own prime decomposition. Then we can factor $a=cd$ for some integers $c$ and $d$. But both $c$ and $d$ are less than $a$, which means they can be written as a product of primes, so we just split them up into their primes and multiply them all together to get $a$. Tada.

As a sort of side note, I mentioned before that primes are so useful that we wanted to be able to extend the idea of prime elements into rings. Well, it turns out for certain rings, it isn’t necessarily true that numbers will always have a unique representation when decomposed into primes. This is something that comes up in algebraic number theory, which is named so because it involves algebraic structures and techniques. This was invented while we were trying to figure out if Fermat’s Last Theorem was actually true (which needed this and other fun mathematical inventions from the last century that implies that Fermat was full of shit when he said he had a proof).

So at the end of the chapter, after Tetra gets her chair kicked over by the megane math girl, we’re treated to a note that acts as a sort of coda to the chapter that mentions that there are infinitely many primes. How do we know this?

Suppose that there are only finitely many primes. Then we can just list all of the prime numbers, like on Wikipedia or something. So we’ve got our list of primes $p_1,p_2,\dots,p_k$. So let’s make a number like $N=1+p_1\cdots p_k$. Well, that number is just a regular old number, so we can break it down into its prime factors. We already know all the primes, so it has to be divisible by one of them, let’s say $p_i$.

Now we want to consider the greatest common divisor of the two numbers, which is just the largest number that divides both of them. We’ll denote this by $\gcd(a,b)$. So since $p_i$ is a factor of $N$, we’ve got $\gcd(N,p_i)=p_i$. But then that gives us $p_i=\gcd(N,p_i)=\gcd(p_i,1)=1$ by a lemma that says that for $a=qb+r$, we have $\gcd(a,b)=\gcd(b,r)$. This means that we have $p_i=1$, which is a contradiction, since 1 isn’t a prime number, and so I guess there are actually infinitely many primes.

So the nice thing is that we won’t run out of prime numbers anytime soon, which is very useful because as we get more and more computing power, we’ll have to increase the size of the keys we use in our cryptosystems. Luckily, because factoring is so hard, we don’t need to increase that size very much before we’re safe for a while. Or at least until we develop practical quantum computers.

Suugaku Girl supplementary handout for chapter 2: On definitions

An introduction to mathematical writing

In chapter 2 of Suugaku Girl, we’re introduced to the third component of the little love triangle that’s forming. Tetra is the underclassman that the main character is tutoring and she’s one of the many people who think they might like math but school eventually beats that silly thought out of them.

Anyone who’s taken a real math class will know that by the end of it, your notes are essentially a giant list of definitions, theorems, and proofs along with an example thrown in once in a while. By a real math class, I mean a math class that’s actually concerned about reasoning about how we get our theorems instead of focusing on how to use them for practical applications. I did my undergrad at a school where math has its own faculty and where there’s a lot of rivalry between the various faculties. Everyone in math often jokes about how an example suffices as a proof for engineers and their ilk.

I checked your textbook for a proof and it said that we’ve done enough examples for it to be plausible. Must have been written by engineers.
— Vanderburg, PMATH 340 (F09)

Here, Tetra falls into the same trap when the main character asks her to define what prime numbers are. So MC-kun has to explain how definitions work. First of all, definitions have to be precise, just like theorems. It’s pretty easy to lose marks for misstating theorems and definitions by leaving off an edge case for 0 or 1 or something silly like that. Of course, that leads Tetra to question why these things need to be so precise and arbitrary.

One of the things I realized about math is that it’s all about trying to do things with the definitions you start out with. You can kind of see that in how the number system is built up. We can start with plain old numbers that we use to count things. And then we can add things to it. Like, what happens if we have less of a thing, how would we represent that? Tada, we’ve got negative numbers. Okay, now what if we have a part of a thing? Now we’ve got fractions. And so on and so forth. We realize that not every number can be written as a fraction and suddenly we’ve defined real numbers.

I’m sure we’ve all wondered why complex numbers work out the way they do. It’s because we’ve defined everything to work out like that. Some guy tried to take the square root of a negative number and found that it didn’t work out very well, so we defined the square root of -1 to be $i$. Now we have this $i$ thing, what can we do with it? Well, we can just start writing crazy things like $3 + i + 4i^2 + 5i^3 + 9i^4 + 2i^5 + 6i^6$, but then we realize that it just becomes $2-2i$. Well, okay that’s kind of neat.

But now we know that all complex numbers can be written as $a+bi$ with $a,b\in\mathbb{R}$. So someone along the line must’ve been like, what would happen if we tried to graph these things? So we treat $a$ as the $x$ component and $b$ as the $y$ component and it turns out we can think of complex numbers as other structures like a vector or just a 2-tuple or something. And suddenly, this gives us a way to compare complex numbers, by taking the length of the vector that they define. And now that we have vectors, we can do some weird geometry stuff with them. We can think of these things as the length of the vector and the angle that they form. And then you can go crazy and talk about roots of unity or what multiplication of complex numbers might mean.

The point is that all of mathematics is built up like this. You start off with some definitions or premises and you go nuts. Of course, you don’t have to use the same definitions as everyone else. The problem with doing that is you might not end up with anything interesting. Like, what if we did something nuts and defined 1 to be a prime number like so many people do when they leave off that condition? Well, not much, we’d probably just rephrase all of our theorems to exclude 1.

On the other hand, sometimes when we play around with definitions, we do end up with something interesting. For instance, we can define something called the extended complex numbers, which is just the set $\mathbb{C}\cup\{\infty\}$. Yep, we just say okay, infinity is a number now, deal with it. So what can we do now?

Well, we can divide by 0 now.

I imagine there might be a few people who might flip out at this notion, but yes, since $\infty$ is included in our number system, we can define $\frac{1}{0}=\infty$. Of course, we can’t do everything — $0\times\infty$ and $\infty-\infty$ still don’t mean anything. But if you’ve been paying attention, you might be going, okay well, we can divide by 0, but what else can we do? Dividing by 0 is kinda meaningless if there’s nothing new we can do.

As it turns out, the extended complex numbers defines a very different geometric object. If we remember from the example of the complex numbers, we can basically define every complex number as a vector over a two-dimensional plane. Here, with the extended complex numbers, we can define every number as a line passing through something called the Riemann sphere. And like the complex plane, this sphere lets us create weird relationships between numbers and angles and stuff. This turns out to have interesting properties in complex analysis and quantum mechanics.

So yes, definitions are often arbitrary. Why? Because it’s just useful and interesting that way. You could argue that it’s because nature forces us to define things a certain way. Kind of like, of course you can’t take a square root of a negative number, you just can’t do it! What happens, though, is that we always seem to end up finding useful things that line up with our mathematics rather than inventing our mathematics to do useful things with. After all, mathematicians have been playing around with imaginary numbers for at least a few decades before electromagnetism was even discovered.

Suugaku Girl supplementary handout for chapter 1: Sequences

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.