\documentclass[12pt]{article}
\usepackage{amsfonts, amsmath, amsthm, amssymb, stmaryrd}
\usepackage[all]{xy}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.5in}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0in}
\setlength{\headsep}{0in}
\setlength{\parskip}{0pt}
\setlength{\parindent}{20pt}

\newcounter{fixmectr}
\def\fixme#1{\addtocounter{fixmectr}{1} \textbf{FIXME \#\thefixmectr.} (#1)}
\def\head#1{\medskip \noindent \textbf{#1}.}

\newtheorem{theorem}{Theorem}

\begin{document}

\begin{center}
  \bf
This Talk is Under Construction \\
Berkeley Math Circle 2001--2002 \\
Kiran Kedlaya
\end{center}

\head{The straightedge and compass operations}
\begin{enumerate}
\item[(a)]
Given two points, we may construct the line through them.
\item[(b)]
Given two points, we may construct the circle centered at one point passing
through the other point.
\item[(c)]
Given two lines, two circles, or a line and a circle, we may construct
their intersection points.
\end{enumerate}

Recall some things you can construct from these steps:
\begin{itemize}
\item the perpendicular bisector of the segment joining two points;
\item the angle bisectors of two given lines;
\item the circle through three given points;
\item a segment of length $\sqrt{a}$, given segments of length 1 and $a$;
\item the regular hexagon, pentagon and 17-gon (!);
\end{itemize}
and some things you've probably heard cannot be constructed from these steps:
\begin{itemize}
\item the trisectors of an arbitrary angle;
\item a regular heptagon (7-gon) or nonagon (9-gon);
\item a segment of length $\sqrt[3]{2}$, given segments of length $1$ and $2$.
\end{itemize}

We call a real number $r$ \emph{(straightedge and compass) constructible}
if, starting from two points
at distance 1, we can produce two more points at distance $|r|$ by a finite
sequence of straightedge and compass operations. We call a complex
number constructible if its real and imaginary parts are constructible.
Then:
\begin{enumerate}
\item the number 1 is constructible;
\item if $r$ and $s$ are constructible, then so are $r+s$, $r-s$, and $rs$;
\item if $r \neq 0$ is constructible, so is $1/r$;
\item if $r$ is constructible, so are $\pm \sqrt{r}$;
\item a number $z$ is constructible if and only if it can be written in
terms of rational numbers using only addition, subtraction, multiplication,
division and square roots.
\end{enumerate}
In particular, each constructible number is \emph{algebraic}: it is the root
of some polynomial with integer coefficients. A famous theorem of Lindemann
states that $\pi$ is transcendental (not algebraic); that's why one cannot
``square the circle''. But there are algebraic numbers that are not
constructible, such as $\sqrt[3]{2}$.

\head{Warning} The next part of the discussion belongs to the subject of
abstract algebra, so may involve some ideas you may not have seen before;
but I hope the intuition will be clear.
(A subset of that is what is called ``linear algebra''; that's pretty much
all I'm really using.)

Given a finite set $S$ of algebraic numbers, the set of complex numbers
obtained from $S$ and the rational numbers
by addition, subtraction, multiplication and division forms what is called a
\emph{number field}. If $K$ is a number field, we can always find $z_1,
\dots, z_n$ in $K$ such that
\[
K = \{
a_1 z_1 + \cdots + a_n z_n: a_1, \dots, a_n \in \mathbb{Q}
\}
\]
and that representation is not redundant (there's only way to write any
element of $K$ this way). Such a set $\{z_1, \dots, z_n\}$ is called a 
\emph{basis} of $K$, and the number $n$ turns out not to depend on the 
choice of the basis
(a fact from linear algebra that I'm not going to prove now).
That number is called the \emph{degree} of the number field. For example,
the number field $K$ generated by $\sqrt[3]{2}$ has degree 3, because we can
take $z_1 = 1, z_2 = \sqrt[3]{2}, z_3 = \sqrt[3]{4}$. And if $S$ consists
of a single primitive $n$-th root of unity $e^{2\pi i/n}$, then the degree
of $K$ turns out to be the Euler phi function $\phi(n)$.

\begin{theorem}
If $S$ is a finite set of constructible numbers and $K$ is the number field
they generate, then the degree of $K$ is a power of 2.
\end{theorem}
\begin{proof}[Sketch]
We prove this by induction on the size of $S$. It's obvious if $S$ is
of size zero, since then $S = \mathbb{Q}$. Suppose $S = S_1 \cup \{\sqrt{s}\}$,
and assume
that the degree of the number field $K_1$ generated by $S_1$ is a power
of 2 and that $s \in K_1$. If $\sqrt{s}$
is already in $K_1$, then $K = K_1$ and we're done. Otherwise,
pick a basis $z_1, \dots, z_n$ of $K_1$; then I claim that
$z_1, \dots, z_n, z_1 \sqrt{s}, \dots, z_n \sqrt{s}$ is a basis of $K$.
Certainly every element of $K$ can be written as
\[
a_1 z_1 + \cdots + a_n z_n + b_1 z_1 \sqrt{s} + \cdots + b_n z_n \sqrt{s}
\]
with the $a_i$ and $b_i$ all rational. So we only have to check that there
aren't two ways to write some number; in fact, we only have to check that
there is no way to write 0 besides using all zeroes. If we had a nontrivial
way to write zero, we could write $a = a_1 z_1 + \cdots + a_n z_n$ and
$b = b_1 z_1 + \cdots + b_n z_n$, which are both elements of $K_1$.
Then $a + b \sqrt{s} =0$; if $b$ were nonzero, then $\sqrt{s} = -a/b$
would be in $K_1$, contradiction. So $b=0$ and hence $a=0$; but since
$z_1,\dots, z_n$ is a basis of $K_1$, this can only happen if the
$a_i$ and $b_i$ are all zero.

Conclusion: the degree of $K$ is exactly twice that of $K_1$, so it's also
a power of 2. 

Why this is only a sketch: You can always arrange for this 
induction to work at the cost of making $S$ larger. (Given whatever numbers
you started with, you have to toss in the ``intermediate'' numbers you
needed to construct them.) So you have to check that if the degree of a
number field is a power of 2, then the degree of any number field
it contains is also a power of 2, which requires a little more linear
algebra.
\end{proof}
So for example, $\sqrt[3]{2}$ is not constructible, because the number field
it generates has degree 3. Also, $e^{2\pi i/7}$ and $e^{2\pi i/9}$ both
generate number fields of degree 6, so they're not constructible either;
thus the regular 7-gon and 9-gon cannot be constructed with straightedge
and compass!

It turns out the converse is also true: if an algebraic number generates a
number field whose degree is a power of 2, then it is constructible. I won't
prove this, but I'll give you an example. A 17-th root of unity $e^{2\pi i/17}$
generates a number field of degree 16, so this converse says that a regular
17-gon is constructible. That is, we can write $e^{2\pi i/17}$ in terms
of rational numbers using square roots. We'll do that in the next section.
One can do likewise for a 65537-gon, since 65537 is prime and
$\phi(65537) = 2^{16}$; we won't do this here.

\head{Example: constructing the 17-gon}

In case you've never seen the construction of the 17-gon (due to Gauss), it's
worth a look, in part because it's a very simple example of a notion
from abstract algebra called a ``Galois group''.

Here's the idea: let $z = e^{2\pi i/17}$ be a primitive 17th root of unity.
Note that $3$ is a primitive root modulo 17, so that $1, 3, \dots, 3^{15}$
cover all the nonzero residue classes modulo 17. Now write
\begin{align*}
-1 = x_0 &= z + z^3 + z^{3^2} + \cdots + z^{3^{15}} \\
x_1 &= z + z^{3^2} + z^{3^4} + \cdots + z^{3^{14}} \\
x_2 &= z + z^{3^4} + z^{3^8} + z^{3^{12}} \\
x_3 &= z + z^{3^8} \\
x_4 &= z.
\end{align*}
Gauss realized that each $x_i$ can be written as the root of a quadratic
polynomial in terms of the previous ones. I'll leave it to you to check
my arithmetic:
\begin{align*}
  x_1(-1-x_1) &= -4 \\
x_2(x_1-x_2) &= -1 \\
x_3(x_2-x_3) &= \frac{x_1x_2 - x_1 +x_2-3}{2} \\
x_4(x_3-x_4) &= 1.
\end{align*}
How do you guess this? I don't know how Gauss did it, but they are predicted
by \emph{Galois theory}. That's the branch of mathematics that tells us that
you can't write the roots of a general degree 5 polynomial in terms of
the coefficients using addition, subtraction, multiplication, division, and
taking $n$-th roots (the way the quadratic formula does this in degree 2,
and analogous formulas are known in degree 3 and 4).

Here's how the prediction is made in that language: the Galois group of
the number field generated by $z$ is a cyclic group of order 16, generated by
the map $g$
that sends $z^{i}$ to $z^{3i}$. (The point is that this map preserves
addition and multiplication, since all it's doing is changing from one
17-th root of unity to another.) The map $g$ fixes only rational numbers;
the maps $g^2$, $g^4$, $g^8$ fix number fields of degree 2, 4, 8, respectively.
The image of $x_1$ under $g$ is precisely $-1-x_1$, so the product
$x_1(-1-x_1)$ is fixed by $g$ and so must be some rational number.
Likewise, the image of $x_2$ under $g^2$ is $x_1-x_2$, so the product
$x_2(x_1-x_2)$ is fixed by $g^2$ and so must be in the number field generated
by $x_1$, and so forth.

\head{The marked straightedge operations}

In using the marked straightedge to trisect angles, Archimedes assumed an 
additional axiom: (here $d$ is the length marked on the straightedge)
\begin{enumerate}
\item[(d)]
Given a line $\ell$, a circle $C$, and a point $P$, 
we can construct
all pairs of points $Q$ and $R$, with $Q$ on $\ell$ and $R$ on $C$,
such that the line $QR$ passes through $P$ and the
distance $QR$ is equal to $d$.
\end{enumerate}
But you might as well go a little further, replacing the line $\ell$ by
another circle:
\begin{enumerate}
\item[(e)]
Given circles $C_1$ and $C_2$ and a point $P$, 
we can construct
all pairs of points $Q$ and $R$, with $Q$ on $C_1$ and $R$ on $C_2$,
such that the line $QR$ passes through $P$ and the
distance $QR$ is equal to $d$.
\end{enumerate}

We can define \emph{marked straightedge constructible} real and complex
numbers as you might expect, but the definition will depend on the distance
$d$ between the marks on the straightedge. The ``right'' definition is
to take $d=1$, the same as the distance between the two starting points. (Or 
if you like, just take one starting point, and use the marked straightedge
to produce the second one!)

\head{The ``solid'' operations}

The ancient Greeks considered a geometric object to be ``solid'' constructible
if if could be obtained using the ordinary straightedge and compass operations
plus the ability to draw conic sections. One can phrase this as follows:
\begin{enumerate}
\item[(d)]
Given five points, we may construct the conic section (parabola, hyperbola,
ellipse, or degenerate conic) through them.
\item[(e)]
Given a conic section and a line, circle or another conic, we may construct
their intersection points.
\end{enumerate}

Likewise, one can define solid constructible real and complex numbers.
It turns out that a complex number $r$ is constructible if and only if:
\begin{itemize}
\item $r$ is algebraic, i.e., $P(r) =0$ for some polynomial $P$ with
integer coefficients;
\item for some such $P$, the number field generated by \emph{all} of the roots
of $P$ has degree a power of 2 times a power of 3. (It's enough to check
this for the polynomial $P$ of smallest degree, called the \emph{minimal 
polynomial} of $r$.)
\end{itemize}
Warning: the second condition is stronger than saying that the number
field generated by $r$ alone has degree a power of 2 times a power of 3.
For example, if $P$ is a ``general'' polynomial of degree 6 with integer
coefficients, then the number field generated by $r$ itself will have degree
6 but the number field generated by all of the roots of $P$ will have
degree $6! = 720$, which has the bad prime factor 5.

For a nice exposition of this, see the article ``Constructions Using a
Compass and Twice-Notched Straightedge'' by Arthur Baragar, in the February
2002 \emph{American Mathematical Monthly}. He also includes a discussion of
the marked straightedge case, but a precise characterization of the
constructible numbers in that case is still unknown.

\head{The origami operations}

The Japanese art of paper folding gives an entirely different approach to
constructing geometric figures. Here is one set of axioms for ``origami
geometry''; there may be others in the literature. (This one is from an
``origami mathematics'' web site.)

\begin{enumerate}
\item[(a)]
Given two points, we may construct the line through them.
\item[(b)]
Given two points, we may construct the perpendicular bisector of the segment
joining the two points (i.e., we may fold one point onto another).
\item[(c)]
Given two lines, we may form the angle bisector of either angle between them
(i.e, we may fold one line onto another).
\item[(d)]
Given a line and a point, we may construct the perpendicular to the line
through the point.
\item[(e)]
Given points $P,Q$ and a line $\ell$, we may construct the line $\ell_1$
through $P$  such that the reflection of $Q$ across $\ell_1$
lies on $\ell$.
\item[(f)]
Given points $P_1$ and $P_2$ and lines $\ell_1$ and $\ell_2$, we may
construct the line(s) $m$ such that the reflection of $P_1$ across
$m$ lies on $\ell_1$, and the reflection of $P_2$ across $m$
lies on $\ell_2$.
\end{enumerate}

\head{Challenge problems}

Some of these are discussed in the article by Baragar mentioned above,
which I again heartily recommend; he also includes many more challenge
problems. Warning: the characterizations of
constructible numbers involves the notion of a ``Galois group'', which
we haven't talked about.

\begin{enumerate}
\item
Find a construction of a regular 7-gon using marked straightedge.
\item
You might wonder why I didn't state a version of the marked straightedge
axiom (d) with two lines instead of a line and a circle. Prove that actually
the resulting construction can already done with straightedge and compass.
\item
Prove that origami constructions (a)-(e) can also be accomplished 
with straightedge and compass. (The only subtle one is (e).)
\item
Find constructions for trisecting a given angle and doubling a cube
using origami. (This will imply that origami construction (f) cannot be
accomplished with straightedge and compass.)
\item
Find a regular polygon that cannot be constructed using origami.
Even better, find a characterization of origami constructible numbers.
(I believe the latter is unsolved!)
\end{enumerate}

\end{document}