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.

17-gon

Uses 4 quadratic equation solutions. Mathematica file. Here is the sequence of calculations to find the x coordinate of vertex number 3 on the unit circle, counting counterclockwise from vertex 1 on the x-axis: 

a0 = -1

prod = 4*a0
a1 = (a0 + Sqrt[a0^2 - 4*prod])/2

prod = 4*a0
a2 = (a0 - Sqrt[a0^2 - 4*prod])/2

prod = 1*a0
a5 = (a1 - Sqrt[a1^2 - 4*prod])/2

prod = 1*a0
a6 = (a2 - Sqrt[a2^2 - 4*prod])/2

prod = 1*a6
a13 = (a5 + Sqrt[a5^2 - 4*prod])/2

x2 = a13/2

257-gon

Uses 24 quadratic equation solutions. Mathematica file. Here is the sequence of calculations to find the x coordinate of vertex number 33 on the unit circle, counting counterclockwise from vertex 1 on the x-axis: 
a0 = -1

prod = 64*a0
a1 = (a0 + Sqrt[a0^2 - 4*prod])/2

prod = 64*a0
a2 = (a0 - Sqrt[a0^2 - 4*prod])/2

prod = 16*a0
a3 = (a1 + Sqrt[a1^2 - 4*prod])/2

prod = 16*a0
a4 = (a2 + Sqrt[a2^2 - 4*prod])/2

prod = 16*a0
a5 = (a1 - Sqrt[a1^2 - 4*prod])/2

prod = 16*a0
a6 = (a2 - Sqrt[a2^2 - 4*prod])/2

prod = 5*a0 - 1*a1 - 2*a3
a7 = (a3 + Sqrt[a3^2 - 4*prod])/2

prod = 5*a0 - 1*a2 - 2*a4
a8 = (a4 - Sqrt[a4^2 - 4*prod])/2

prod = 5*a0 - 1*a1 - 2*a5
a9 = (a5 + Sqrt[a5^2 - 4*prod])/2

prod = 5*a0 - 1*a2 - 2*a6
a10 = (a6 - Sqrt[a6^2 - 4*prod])/2

prod = 5*a0 - 1*a1 - 2*a3
a11 = (a3 - Sqrt[a3^2 - 4*prod])/2

prod = 5*a0 - 1*a2 - 2*a4
a12 = (a4 + Sqrt[a4^2 - 4*prod])/2

prod = 5*a0 - 1*a1 - 2*a5
a13 = (a5 - Sqrt[a5^2 - 4*prod])/2

prod = 5*a0 - 1*a2 - 2*a6
a14 = (a6 + Sqrt[a6^2 - 4*prod])/2

prod = 1*a1 + 2*a4 + 1*a7 - 2*a8 + 1*a9
a15 = (a7 + Sqrt[a7^2 - 4*prod])/2

prod = 1*a2 + 2*a5 + 1*a8 - 2*a9 + 1*a10
a16 = (a8 + Sqrt[a8^2 - 4*prod])/2

prod = 1*a1 + 2*a6 + 1*a9 - 2*a10 + 1*a11
a17 = (a9 + Sqrt[a9^2 - 4*prod])/2

prod = 1*a2 + 2*a3 + 1*a10 - 2*a11 + 1*a12
a18 = (a10 + Sqrt[a10^2 - 4*prod])/2

prod = 1*a1 + 2*a4 + 1*a11 - 2*a12 + 1*a13
a19 = (a11 + Sqrt[a11^2 - 4*prod])/2

prod = 1*a2 + 2*a5 + 1*a12 - 2*a13 + 1*a14
a20 = (a12 + Sqrt[a12^2 - 4*prod])/2

prod = 1*a1 + 2*a6 + 1*a13 - 2*a14 + 1*a7
a21 = (a13 - Sqrt[a13^2 - 4*prod])/2

prod = 1*a2 + 2*a3 + 1*a14 - 2*a7 + 1*a8
a22 = (a14 + Sqrt[a14^2 - 4*prod])/2

prod = 1*a1 + 2*a4 + 1*a7 - 2*a8 + 1*a9
a23 = (a7 - Sqrt[a7^2 - 4*prod])/2

prod = 1*a2 + 2*a5 + 1*a8 - 2*a9 + 1*a10
a24 = (a8 - Sqrt[a8^2 - 4*prod])/2

prod = 1*a1 + 2*a6 + 1*a9 - 2*a10 + 1*a11
a25 = (a9 - Sqrt[a9^2 - 4*prod])/2

prod = 1*a2 + 2*a3 + 1*a10 - 2*a11 + 1*a12
a26 = (a10 - Sqrt[a10^2 - 4*prod])/2

prod = 1*a1 + 2*a4 + 1*a11 - 2*a12 + 1*a13
a27 = (a11 - Sqrt[a11^2 - 4*prod])/2

prod = 1*a2 + 2*a5 + 1*a12 - 2*a13 + 1*a14
a28 = (a12 - Sqrt[a12^2 - 4*prod])/2

prod = 1*a1 + 2*a6 + 1*a13 - 2*a14 + 1*a7
a29 = (a13 + Sqrt[a13^2 - 4*prod])/2

prod = 1*a2 + 2*a3 + 1*a14 - 2*a7 + 1*a8
a30 = (a14 - Sqrt[a14^2 - 4*prod])/2

prod = 1*a23 + 1*a24 + 1*a25 + 1*a28
a39 = (a23 - Sqrt[a23^2 - 4*prod])/2

prod = 1*a24 + 1*a25 + 1*a26 + 1*a29
a40 = (a24 - Sqrt[a24^2 - 4*prod])/2

prod = 1*a30 + 1*a15 + 1*a16 + 1*a19
a46 = (a30 + Sqrt[a30^2 - 4*prod])/2

prod = 1*a15 + 1*a16 + 1*a17 + 1*a20
a47 = (a15 - Sqrt[a15^2 - 4*prod])/2

prod = 1*a16 + 1*a17 + 1*a18 + 1*a21
a48 = (a16 - Sqrt[a16^2 - 4*prod])/2

prod = 1*a22 + 1*a23 + 1*a24 + 1*a27
a54 = (a22 + Sqrt[a22^2 - 4*prod])/2

prod = 1*a23 + 1*a24 + 1*a25 + 1*a28
a55 = (a23 + Sqrt[a23^2 - 4*prod])/2

prod = 1*a30 + 1*a40 - 1*a46
a71 = (a39 - Sqrt[a39^2 - 4*prod])/2

prod = 1*a22 + 1*a48 - 1*a54
a111 = (a47 + Sqrt[a47^2 - 4*prod])/2

prod = 1*a7 - 1*a15 - 1*a55 - 1*a71
a239 = (a111 - Sqrt[a111^2 - 4*prod])/2

x32 = a239/2

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.) The list of formulas is too bulky to put here, so see the file.

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.

Back to Ken Brakke's home page.