# 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 zN = 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:

1. Find an integer K that generates the multiplicative group of ZN. K = 3 happens to work for N = 5,17,257,65537, so we'll just use that.
2. 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).
3. Let S(m,i) be the sum of every mth root from the list, starting the ith. 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 zN-1 in zN - 1 = 0), and 1 is omitted.
4. 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).
5. 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.
6. 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 4. 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:

1. Carl Friedrich Gauss, Disquitiones Arithmeticae, 1801, section VII. (English translation by Arthur A. Clarke, 1965 (Yale).)
2. 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.