Constructing a polygon within a given circle

What is the regular polygon with the least number of sides that cannot be constructed within a given circle, using only a straightedge and a compass?

A heptagon (seven sides).

Yes, of course. I knew you could get close, but not precisely.

The complete list would start with:
7 sides
9 sides
11 sides
13 sides
14 sides
15 sides
18 sides
19 sides
21 sides

See Constructable Polygon. The only regular polygons that can be constructed are those where the number of sides is a product of a number of distinct Fermat primes multiplied by a power of 2.

–Mark

15 sides is easily doable, since both 5 and 3 are constructible, and are relatively prime.

Of course you are right – my mistake.

Of course you can construct n-sided polygons with a ruled straightedge; I wonder why the Greek geometrists considered that cheating.

Is there anything the Greeks cared about that couldn’t be constructed with a compass and ruler? If there isn’t, that takes most of the game out of the game.

You can make a ruled straightedge easily, using the Greeks’ own techniques (Euclid’s Proposition VI.9). The problem isn’t in putting the marks on the ruler; it’s in interpolating between the marks.

If Wikipedia is to be believed, you can trisect an angle or double a cube using a marked straightedge. You cannot, however, square the circle (which is a problem the Greeks knew of and cared about.) Roughly speaking, doubling the cube becomes possible because the cube root of two is an algebraic number, while π is a transcendental (i.e., non-algebraic) number and so squaring the circle is still impossible.

There’s also a list of the regular n-gons that can and cannot be constructed using a marked straightedge here. In particular, it is still impossible to construct a regular hendecagon.

I don’t know a Fermat prime from a hole in the wall, but would that “power of 2” include 2[sup]0[/sup]? Because otherwise I don’t know how you come up with 3, a number whose regular polygon can be drawn with only a compass.

Yup, 1 is a power of 2.

Yes, as Chronos says, 1 is a power of 2.

Also, “a number of Fermat primes” includes the case of zero Fermat primes, which is why you can construct a square (4 sides = 2^2, with no primes involved).

A Fermat prime is a prime of the form (2^(2^n))+1. There are only 5 known Fermat primes: 3, 5, 17, 257, and 65537.

–Mark