# Constructing 17, 257, and 65537 sided polygons

Classically, the only regular polygons that could be constructed with
ruler and compass were those with 3, 4, 5, or 15 sides and those times
powers of 2 (since bisection is easy). Karl Friedrich Gauss in 1801
published a proof that side numbers that were prime and of the form
2^2^m + 1 (known as Fermat primes) could be constructed, and claimed
he had a proof only those could be (aside from the resulting constructions for
the products of single powers of Fermat primes and powers of 2).
Wantzel later published a completed proof.
The only known Fermat primes are N = 3, 5, 17, 257, and 65537.
For more history, see
Wikipedia.
The central idea is to view the vertices of the polygon on a unit circle
as complex numbers, solutions of z^{N} = 1. The vertices are thus "Nth roots
of unity". Gauss showed certain sums of roots could be solved recursively
in terms of other sums with quadratic equations, winding up with the
sum of a conjugate pair of roots, half of which gives the real part of
a root. Since quadratic equations can be solved with ruler and compass,
the construction can be done.

Algorithm:

- Find an integer K that generates the multiplicative group of Z
_{N}.
K = 3 happens to work for N = 5,17,257,65537, so we'll just use that.
- List the powers of K mod N, i.e. for N = 17 we have 1, 3, 9, 10, ...
This list has N-1 elements, since 0 does not occur, not being in the
multiplicative group. List the N-1 roots in this order (omitting 1).
- Let S(m,i) be the sum of every m
^{th} root from the list,
starting the i^{th}. We will only use powers of 2 for m.
Note that S(1,0) = -1, since all N roots sum to 0 (the coefficient of
z^{N-1} in z^{N} - 1 = 0), and 1 is omitted.
- It turns out that S(2*m,i)*S(2*m,i+m) is a linear combination of
S(m,j) and lower terms with integer coefficients.
Also, S(2*m,j)+S(2*m,j+m) = S(m,j).
Starting with S(1,0) = -1,
we can recursively solve quadratic equations for all the S(m,i).
- For m = (N-1)/2, it turns out S(m,i) is the sum of two conjugate
roots, so S((N-1)/2,i) is the x coordinate of those two roots, say U and V.
- The chord between any two roots (say 1 and U, or U and V) can be
use to lay off chords around the unit circle to construct all N vertices.

The non-obvious step is finding a linear combination in step 3.
Just for fun, I wrote a program to find such combinations.
The method used is to write the product as a symbolic sum of roots,
and then Gaussian elimination to find the coefficients;
luckily the elimination matrix starts sparse and gets steadily
sparser as solving proceeds. Even for a 65537-gon, the whole
set of eliminations takes under 10 minutes and uses under 60 MB,
using sparse matrix techniques. The output is in the form
of a Mathematica file of successive quadratic formulas that
wind up with the desired value. I also generated JavaSketchpad
files, which wind up looking pretty ugly, and the 65537-gon file
is too big to run on my system.
## 17-gon

Uses 4 quadratic equation solutions.
Mathematica file.
## 257-gon

Uses 24 quadratic equation solutions.
Mathematica file.
## 65537-gon

Uses 1141 quadratic equation solutions. Luckily, if you want to
try the construction by hand, the number of terms in the linear
combinations peaks at only 92.
Mathematica file. (There are more than
1141 quadratic solutions here, since I'm counting using both roots
as one equation, which can be done with one geometric construction,
but uses two Mathematica formulas here.)
References:

- Carl Friedrich Gauss, Disquitiones Arithmeticae, 1801, section VII.
(English translation by Arthur A. Clarke, 1965 (Yale).)
- Christian Gottlieb, "The Simple and Straightforward Construction of the
Regular 257-gon," Mathematical Intelligencer, vol. 21, no. 1, 1999, p. 31-37.

Back to constructions.

Back to Ken Brakke's home page.