Which polygons can be drawn

On 30 March 1796, a nineteen-year-old wrote in his diary that he had constructed a regular seventeen-sided polygon with straightedge and compass. Nobody had drawn a new regular polygon in two thousand years.

The list is strange enough to be worth staring at before any explanation. $3$ and $4$ and $5$ and $6$, then a gap at $7$; $8$ and $10$ and $12$, gaps at $9$ and $11$; $15$, $16$, $17$, and then nothing until $20$.

The question, in numbers #

A regular $n$-gon inscribed in a circle has its corners at angles $\frac{2\pi k}{n}$. Constructing the polygon means constructing the angle $\frac{2\pi}{n}$, which — by the conversion from the previous rung — means constructing the length $\cos\frac{2\pi}{n}$.

So the question is: for which $n$ does $\cos\frac{2\pi}{n}$ have degree a power of two?

Two things about that number are worth having in hand. It is the real part of a complex number $\zeta = e^{2\pi i/n}$ satisfying $\zeta^n = 1$, and the $n$ solutions of that equation sit at the polygon’s own corners, so the polygon and the equation are the same object twice. And the degree of $\zeta$ over the rationals is $\varphi(n)$ — Euler’s totient, the count of numbers below $n$ sharing no factor with it.

The reason the totient appears is worth a sentence. The $n$-th roots of unity form a cyclic group under multiplication, and the ones that generate the whole group — the primitive roots — are exactly $\zeta^k$ with $k$ coprime to $n$. There are $\varphi(n)$ of them, they are permuted among themselves by every symmetry of the situation, and the polynomial they satisfy therefore has degree $\varphi(n)$ and no smaller one will do.

Taking the real part halves the degree, so $\cos\frac{2\pi}{n}$ has degree $\varphi(n)/2$. Either way the conclusion is the same, because a number is a power of two exactly when its half is:

The regular $n$-gon is constructible exactly when $\varphi(n)$ is a power of two.

The same list from the other side #

Gauss stated the criterion differently, in terms of the shape of $n$ rather than the size of a count.

$\varphi$ is multiplicative on coprime parts, and $\varphi(p^e) = p^{e-1}(p-1)$. For that to be a power of two:

• a factor of $2^k$ contributes $\varphi(2^k) = 2^{k-1}$, always a power of two, so any number of factors of two is free;
• an odd prime $p$ appearing to a power $e \ge 2$ contributes a factor of $p$, which is odd and larger than one, so it is fatal;
• an odd prime $p$ appearing once contributes $p-1$, which must itself be a power of two.

A prime that is one more than a power of two is a Fermat prime. So:

$n$ works exactly when it is a power of two times a product of distinct Fermat primes.

The two statements are the same statement. The figure at the top of this page computes both, by routes sharing no code — one factorises $n$ and inspects the odd part, the other adds up the totient — and asserts that they agree at every $n$ it draws. A criterion checked against itself would be worth nothing; two criteria agreeing ninety-eight times is a real check on both.

Why seven fails and five does not #

The abstract criterion is convincing but it is worth watching one case fail in the concrete.

For $n = 7$, $\varphi(7) = 6$, which is not a power of two. Concretely, $2\cos\frac{2\pi}{7}$ satisfies

$$x^3 + x^2 - 2x - 1 = 0,$$

a cubic. If it has a rational root, the root’s numerator divides $1$ and its denominator divides $1$, so the only candidates are $±1$.

Neither is. The cubic is irreducible, the degree is three, and the heptagon is out.

For $n = 5$, $\varphi(5) = 4$, a power of two — and the concrete version is that $2\cos\frac{2\pi}{5} = \frac{\sqrt5-1}{2}$, one square root deep and therefore constructible in one step.

That is the pentagon’s entire secret, and it is why the pentagon and the golden ratio are the same subject: $\frac{1+\sqrt5}{2}$ is the diagonal of a unit pentagon, and $\sqrt5$ is one circle away.

The same blind search aimed at the heptagon’s cosine would have to reach degree three before finding anything, and aimed at $\pi$ it finds nothing at any degree, which is the subject of the last rung of this ladder.

Nine fails, and three does not #

The case that catches people is $n = 9$, because $3$ is a Fermat prime and $9$ is a power of $3$.

The criterion says distinct Fermat primes, and $9 = 3^2$ repeats one. The totient version says $\varphi(9) = 6$, not a power of two. And the concrete version is an equation already seen on this site:

$2\cos\frac{2\pi}{9} = 2\cos 40°$ satisfies $x^3 - 3x - 1 = 0$, which is exactly the trisection cubic for sixty degrees rescaled: $8y^3-6y-1$ with $x = 2y$. That is not a coincidence. Constructing the nine-gon is trisecting the angle of the three-gon, and the two impossibilities are one impossibility.

The same collision explains the rest of the list. $n$ works, $2n$ works — bisecting is free. $n$ works and $3n$ generally does not, because trisecting is not.

The polygon and the equation are one object #

It is worth dwelling on the identification made in passing above, because it is the reason this problem has an answer at all and it is the most surprising thing on the page.

Place the polygon’s corners on the unit circle in the plane of complex numbers. Then the corners are the $n$ solutions of $z^n = 1$, and multiplying complex numbers is turning, so stepping from one corner to the next is multiplication by a fixed number. The polygon is not merely described by the equation; it is the solution set drawn.

That means a question about drawing has become a question about factorising $z^n - 1$ over the rationals, and factorisation is something there are theorems about. The polynomial splits into pieces, one for each divisor of $n$, and the piece belonging to $n$ itself — the cyclotomic polynomial — has degree $\varphi(n)$ and is irreducible. Its irreducibility is a real theorem, due to Gauss, and it is what pins the degree down rather than merely bounding it.

For $n = 5$ the piece is $z^4+z^3+z^2+z+1$, degree $4$. For $n = 7$ it is $z^6+\cdots+1$, degree $6$. For $n = 9$, after dividing out the cube roots of unity, it is $z^6+z^3+1$, degree $6$ again. The two sixes are why neither of those polygons can be drawn, and they are the same six that shows up as the cubics above once the real part is taken.

This is the pattern the site keeps meeting: a construction, an equation and a group turn out to be one object seen from three sides, and the side that answers the question is whichever one has a finite check attached to it. Here it is the equation, and the check is a degree.

What is actually known about the list #

The criterion is complete and the list it produces is not, which is an unusual and slightly uncomfortable position.

The known Fermat primes are

$$3,\quad 5,\quad 17,\quad 257,\quad 65537,$$

being $2^{2^k}+1$ for $k = 0,1,2,3,4$. Fermat conjectured in 1640 that every number of that form is prime. Euler disposed of the next one in 1732 by finding that

$$2^{32}+1 = 4294967297 = 641 \times 6700417,$$

and every subsequent case anyone has managed to test has been composite. No Fermat prime beyond $65537$ is known, and it is not known whether there are finitely many.

So the constructible polygons are completely characterised and cannot be completely listed. There are at least $2^5 = 32$ odd values of $n$ that work — every subset of the five known Fermat primes, including the empty one — and each may be multiplied by any power of two. Whether there are more depends on a question about the primality of enormous numbers that has been open for three hundred and eighty years.

The largest odd constructible polygon anybody can name has

$$3 \times 5 \times 17 \times 257 \times 65537 = 4294967295$$

sides, which is $2^{32}-1$. That number being one less than a power of two is not a coincidence either: it is the product of all five known Fermat primes, and the identity $\prod_{k=0}^{4}(2^{2^k}+1) = 2^{32}-1$ is the same telescoping that makes a difference of squares factor.

Reading the gaps #

The pattern in the grid rewards a little decoding, because each kind of gap has a different cause.

Odd primes that are not Fermat primes. $7, 11, 13, 19, 23, 29, 31, \ldots$ — every one of them fails, because $p-1$ has an odd factor. That accounts for most of the silence: primes are common and Fermat primes are not.

Squares of Fermat primes. $9, 25$ and $289$ fail although $3, 5$ and $17$ succeed. Repeating a prime introduces a factor of that prime into the totient, and the criterion’s word distinct is doing all the work.

Anything carrying a bad factor. $14 = 2 \times 7$ fails because $7$ does, $21 = 3 \times 7$ fails for the same reason, and so on. A polygon is only as constructible as its worst prime.

Products of different Fermat primes, which all work. $15 = 3 \times 5$ and $51 = 3 \times 17$ and $85 = 5 \times 17$ are on the list, and the construction is pleasant: given a regular $p$-gon and a regular $q$-gon with $p$ and $q$ coprime, the $pq$-gon follows because some combination $ap + bq = 1$ lets the two angles be added to make the small one. That is the Chinese remainder theorem doing geometry, and it is the reason $15$ was known to Euclid while $17$ waited two thousand years.

The doubling rule is the last piece: $n$ constructible implies $2n$ constructible, because bisecting an angle is one circle. So each entry on the list drags an infinite chain of doublings behind it, and that is why the filled squares thin out but never stop.

The seventeen-gon, briefly #

Gauss did not merely prove the seventeen-gon possible; he produced the number, and it is worth seeing once because it is what “a tower of square roots” looks like when written out:

$$16\cos\frac{2\pi}{17} = -1+\sqrt{17}+\sqrt{34-2\sqrt{17}}+2\sqrt{17+3\sqrt{17}-\sqrt{34-2\sqrt{17}}-2\sqrt{34+2\sqrt{17}}}.$$

Four square-root signs, nested three deep. The degree is $\varphi(17)/2 = 8 = 2^3$, and the three levels of nesting are the three doublings the tower takes to reach it.

The construction itself was first written down by Johannes Erchinger in the 1820s and takes a few dozen steps. Gauss asked for the polygon on his tombstone; the stonemason declined, reportedly on the grounds that a seventeen-sided figure would be indistinguishable from a circle.

How Gauss got there: splitting the corners into halves #

The nested radicals above look like the output of a machine, and it is worth seeing the machine, because it is the reason the converse of the theorem is true and not merely the reason one polygon is.

The sixteen corners other than $1$ are the powers of a primitive root modulo seventeen. Take $3$: its powers run $3, 9, 10, 13, 5, 15, 11, 16, 14, 8, 7, 4, 12, 2, 6, 1$, visiting every non-zero residue before returning — so raising $\zeta$ to those powers in order visits every corner but one, in a cyclic order that has nothing to do with how the corners sit on the circle.

Now split that cycle by taking alternate entries. Two sets of eight, and adding the corresponding roots of unity gives two numbers, $\eta_0$ and $\eta_1$, called periods. Neither is rational. Their sum is, because together they are all sixteen roots and those add to $-1$; and their product is rational too, because multiplying out gives a sum over all the roots that is symmetric in the two halves. Working it out gives $-4$, so the two periods are the roots of

$$x^2 + x - 4 = 0.$$

One quadratic, and its discriminant is $1 + 16 = 17$ — which is where the outermost $\sqrt{17}$ in Gauss’s expression comes from. It is not an ingredient somebody chose; it is the discriminant of the first split.

Then repeat. Each set of eight splits by alternation into two sets of four, whose sum and product are expressible in the periods already found, so each pair satisfies a quadratic over the field just built. Four sets of four become eight of two, and a set of two is $\zeta^k + \zeta^{-k}$, which is twice a cosine. Four splits, four quadratics, four nested square roots — exactly the four in the displayed formula, nested three deep because the last one is built on the three before it.

The whole construction is one idea applied four times: halve the set of corners, and show the two halves satisfy a quadratic. It works because the group of symmetries permuting the corners is cyclic of order sixteen, and a cyclic group of order $2^k$ has a subgroup of index two, which has one of its own, all the way down. Every halving of the group is a quadratic, and a quadratic is a compass.

That is why the criterion’s sufficiency is not an accident of small cases. Whenever $\varphi(n)$ is a power of two, the same chain exists, the same splitting works, and the polygon is constructible — with a formula nobody would want to write down but whose shape is determined in advance by the chain of halvings. Gauss found the seventeen-gon by noticing that the arithmetic of the corners was cyclic, and everything else followed from a property of a group rather than from anything about circles.

What the figures decide, and what they do not #

The grid at the top of this page is a report on a computation, and it is worth being exact about which one.

For every $n$ it factorises $n$, applies both criteria, and asserts that they agree. That is a genuine check of the equivalence of the two statements at every size drawn — a hundred independent chances for a mistake in either route to show up.

What it does not do is prove the Gauss–Wantzel theorem. The theorem’s forward half is the degree argument of the second rung; its converse half — that every $n$ passing the criterion really can be drawn — needs Galois theory, because the degree being a power of two is not by itself enough, as that essay was careful to say.

The converse is true here for a reason peculiar to roots of unity: their symmetry group is cyclic, and a cyclic group of order $2^k$ has a chain of subgroups stepping down by twos, which is exactly a tower of quadratic extensions. That fact is why Gauss could construct the polygon rather than merely count its degree, and it is the one place in this ladder where the easy direction is not the whole story.

Why this one is the interesting impossibility #

The cube and the angle are single facts. This is a classification, and classifications behave differently.

A single impossibility invites the response “then use a better tool”, and the response is correct: a marked ruler doubles the cube. A classification invites a different question — why that list? — and the answer turns out to have nothing to do with drawing at all. The polygons that can be drawn are the ones whose totient is a power of two, and the totient knows nothing about compasses. It is a count of coprime residues, an object from modular arithmetic that was invented for entirely unrelated reasons.

So the shape of the answer is: a question about instruments turned out to be a question about the multiplicative structure of the whole numbers, and the strangeness of the list is inherited from the strangeness of the Fermat primes. That is a much better return than a single negative result, and it is why this is the theorem Gauss put on his own list of achievements while Wantzel’s two impossibilities went comparatively unremarked.

There is one more consequence worth stating, because it is the sharpest form of the surprise. Whether the list is finite or infinite — that is, whether there are finitely many odd constructible polygons — is an open problem in number theory, not in geometry. Nothing further about compasses will settle it. The question of what can be drawn has been completely converted into a question about which numbers of the form $2^{2^k}+1$ are prime, and there it sits.

Where this ladder goes #

Three of the four classical problems are now closed, and all three closed the same way: a number, a polynomial, a degree that is not a power of two.

The fourth does not work like that at all. Squaring the circle needs $\sqrt\pi$, and the obstruction is not that $\pi$ has the wrong degree — it is that $\pi$ has no degree, satisfying no polynomial equation with whole-number coefficients whatsoever. That is a much stronger statement about a much stranger kind of number, it was proved sixty years after Wantzel, and it is the one impossibility in this field that no figure can carry.