Cryptography Part 2: More rambling

Impossibility proofs have always fascinated me. Solving a problem is one thing. Failing to solve a problem is another. But there is something really special about proving nobody can solve it, ever, even if they are smarter than you. (Guess where I am going with this.)

The Delian problem is provably unsolvable. This was not discovered until the 1800s, but the proof is accessible to any mathematically-inclined high school student. So I am going to walk through it. “Seriously, Nemo? You are going to cover an abstract algebra class in a blog post?” Sure, why not?

This will be long, detailed, and almost completely off-topic. Feel free to skip to the last few paragraphs if you just want the punch line.

As usual, if you are reading this in an RSS reader and the equations look like nonsense, click through to the actual post. And ask your RSS provider to install MathJax.

Suppose instead of doubling a cube, we wanted to double a square. That is, given segment AB of length 1, construct a segment of length \(\sqrt{2}\) using straightedge and compass.

Here is one way. Just like last time, draw a small circle centered at B passing through A, then extend AB to cross that circle at C. Draw two larger circles, one centered at A passing through C, the other centered at C passing through A. Let D be an intersection of these larger circles. Draw BD intersecting the small circle at E:

Segment AE has length \(\sqrt{2}\).

(Word of advice: Writing raw SVG is a little bit like pulling your own teeth.)

In general, given two segments, it is possible to add, subtract, multiply, or divide them, using only straightedge and compass. That is, if two segments have lengths \(a\) and \(b\), you can construct a new segment of length \(a+b\), \(a-b\), \(ab\), or \(a/b\). Also, given a segment of length \(r\), you can construct one of length \(\sqrt{r}\). I hope these are all plausible enough to leave as exercises (hint: similar triangles).

More interestingly, these five operations — add, subtract, multiply, divide, and square root — are all you can do. To see this requires inventing analytic geometry, which is one reason the Delian problem took 2000 years to resolve. Set up a 2D Cartesian coordinate system with A at (0,0) and B at (1,0). Observe that straightedge and compass constructions involve nothing more than introducing new points by finding the intersections of lines and circles based on existing points. In the Cartesian plane, any line may be described by a linear equation based on two points, while any circle may be described by a quadratic equation based on its center and radius. The coordinates of the intersection of any pair of these (line with line, line with circle, or circle with circle) may be found by solving either a linear or a quadratic equation. Since the quadratic formula involves only addition, subtraction, multiplication, division, and square root, it follows that new intersections of lines and circles can only introduce coordinates based on the coordinates of existing points combined with these five operations.

If you start with segment AB of length 1, and all you can do is add, subtract, multiply, divide, and extract square roots, what lengths can you make? Well, you can add 1 to itself to get 2 by doubling AB. You can add 1 to that to get 3. And so on. So any integer is constructible. You can also divide, so any rational number (that is, any \(a/b\) where \(a\) and \(b\) are integers) is also constructible.

Finally, you can extract square roots. That lets you cover a lot of ground, in some ways. Consider:

$$\sqrt{\sqrt{2*\sqrt{\sqrt{2*\sqrt{\sqrt{2*\frac{96389}{76504}}}}}}}$$

This expression involves only integers, multiplication, division, and square root, so its value is constructible with straightedge and compass. And it is close enough to \(\sqrt[3]{2}\) to fool Google Calculator.

Of course, its value is not exactly \(\sqrt[3]{2}\), and neither is any other combination of integers using only these five operations. Proving this takes around three lines if your name is “Galois”, but for me it will take a little longer.

The key to the argument is to ignore square roots for a minute and just think about the four basic operations of addition, subtraction, multiplication, and division. What numbers can you generate starting from 1 and repeatedly applying these?

Obviously, you can generate any integer by adding 1 to itself repeatedly. And you can generate any rational number by dividing two integers.

But that is all you can do. Given any two rational numbers, their sum, difference, product, and quotient are themselves all rational. You cannot “escape” from the rational numbers just by adding, subtracting, multiplying, or dividing, and a mathematician would say the rationals are closed under these operations. Any set of numbers closed under these basic operations — i.e. any set from which you cannot “escape” by addition, subtraction, multiplication, or division — is called a number field, or simply a field. The field of rational numbers is important enough to have its own symbol: \(\mathbb{Q}\). When you see \(\mathbb{Q}\), think “all rational numbers”.

\(\sqrt{2}\) is not an element of \(\mathbb{Q}\); that is, \(\sqrt{2}\) cannot be expressed as the ratio of two integers. The proof of this was known to Euclid, and I omit it here.

To “escape” from the set of rational numbers, let’s try adjoining \(\sqrt{2}\) to them, then combining the elements from that new set with addition, subtraction, multiplication, and division, repeatedly. What numbers can you generate now?

Obviously, you can generate any number of the form \(p + q\sqrt{2}\) where \(p\) and \(q\) are rational. Can you generate anything else?

No. Suppose you have two numbers of the form \(a + b\sqrt{2}\) and \(c + d\sqrt{2}\) where \(a\), \(b\), \(c\), and \(d\) are rational. Whether you take their sum, difference, product, or quotient, the result is of the form \(p + q\sqrt{2}\) where \(p\) and \(q\) are also rational. (Try it.) So numbers of this form are all you can generate; you cannot “escape” just by combining them with the four basic operations. In other words, these numbers — \(p + q\sqrt{2}\), with \(p\) and \(q\) in \(\mathbb{Q}\) — form a field. Mathematicians have a shorthand notation for this field, too; they call it \(\mathbb{Q}(\sqrt{2})\). In math-speak, all elements of \(\mathbb{Q}(\sqrt{2})\) are expressible as \(p + q\sqrt{2}\) where \(p\) and \(q\) are elements of \(\mathbb{Q}\).

We can keep going. Starting from \(\mathbb{Q}(\sqrt{2})\), we can adjoin another element, like \(\sqrt{3}\) or \(\sqrt{1+\sqrt{2}}\). A field created this way, by adjoining a new element to a smaller field, is called a field extension. In general, for a field \(F\), the field extension you get by adjoining an element \(x\) is denoted \(F(x)\).

So, one way to look at straightedge-and-compass constructions is like this. You start with a bunch of numbers from the field \(\mathbb{Q}\). As long as you only add, subtract, multiply, and divide, you stay in that field. The first time you take a square root of a non-square rational number \(\alpha\), you “escape” into the extension field \(F_1 = \mathbb{Q}(\sqrt{\alpha})\). Then, as long as you only add, subtract, multiply, and divide, you stay in that field… Until you take the square root of some non-square \(\beta\) in \(F_1\), at which point you “escape” into the field \(F_2 = F_1(\sqrt{\beta})\).

And so on. Any straightedge-and-compass construction generates a tower of fields \(F_1, F_2, \ldots\), where each \(F_n\) is created by taking a square root in \(F_{n-1}\) and adjoining it. (We define \(F_0 = \mathbb{Q}\).) All numbers in \(F_n\) are expressible as \(p + q\sqrt{r}\), where \(p\), \(q\), and \(r\) come from the previous field \(F_{n-1}\) and \(r\) is not a perfect square in \(F_{n-1}\). Numbers appearing “for the first time” in \(F_n\) — that is, appearing in \(F_n\) but not \(F_{n-1}\) — have \(q\) non-zero.

Now, suppose some straightedge-and-compass construction could generate \(\sqrt[3]{2}\). Then either \(\sqrt[3]{2}\) would be rational — which it isn’t — or it would appear for the first time in some \(F_n\) and therefore be expressible as \(p + q\sqrt{r}\), where \(p, q, r\) are from \(F_{n-1}\), \(r\) is not a perfect square in \(F_{n-1}\), and \(q\) is not zero.

So let \((p + q\sqrt{r})^3 = 2\). Expand that binomial and collect terms to find:

$$(p^3 + 3pq^2r) + (3p^2q + q^3)\sqrt{r} = 2$$

Observe that the coefficient on \(\sqrt{r}\) — that is, \(3p^2q + q^3\) — must be zero. If it were not, we could solve this equation for \(\sqrt{r}\) in terms of values from \(F_{n-1}\), which would make \(r\) a perfect square in \(F_{n-1}\), meaning we never “escaped” from that field at all, a contradiction.

It follows that \(p – q\sqrt{r}\) is also a cube root of 2; just take this value, cube it, and compare to the expression above, remembering that \(3p^2q + q^3\) is zero.

But, since \(q \neq 0\), \(p + q\sqrt{r}\) and \(p – q\sqrt{r}\) are distinct real numbers. Since cube root is a strictly increasing function, every real number has exactly one real cube root. Thus we have reached a contradiction and \(\sqrt[3]{2}\) is not constructible.

The impossibility of the Delian problem was first proven by a guy named Pierre Wantzel in 1837, but the underlying math was found by Galois who was building on Gauss. (“Who was the greatest mathematician, Gauss or Euler?” is sort of the math geek equivalent of “pirates vs. ninjas”. Except that ninjas are obviously way cooler.)

I stole this particular proof from the greatest general-interest math book of all time.