The fewest moves to draw it

The price of a construction counted the cost of classical constructions the way Émile Lemoine did in 1888, pricing every movement of the hand, and found that the familiar methods are far from free. It ended with a question it could not answer: for the figures that made geometry famous, is any known construction the cheapest possible? Proving that a construction cannot be shortened requires ruling out every shorter one, and no invariant of the constructible points does that.

For small constructions there is another way: try every shorter one. Start from two points and list every line and every circle that could be drawn; for each, list every line and circle that could be drawn next; and so on. At each depth, either some sequence reaches the target or none does, and when none does at depth $d$ and one does at depth $d + 1$, the minimum is $d + 1$ — proved, not guessed. The only obstacle is that the number of sequences explodes, and the question is how far the search can reach before it does.

This essay runs that search. It measures cost in the simplest way — one move is one line or one circle — and finds the minimum for seven targets, with ruler and compass and with the compass alone. The answers are small numbers, and several of them are not what a textbook construction would suggest.

Four moves for the midpoint, and six without a ruler #

The rules are Euclid’s. The known points at the start are $A = (0, 0)$ and $B = (1, 0)$. A move draws either the line through two known points or the circle centred at one known point and passing through another. Every point where the new object crosses an object already drawn becomes known. A target is constructed when all its points are known.

The midpoint of $AB$ takes four moves: the circle about $A$ through $B$, the circle about $B$ through $A$, the line through the two points where they cross, and the line $AB$ itself — the midpoint is where the last two lines meet. That is the construction every textbook gives, and the search confirms that no three moves reach the midpoint. It examined 55 configurations in all to be sure.

Without the ruler, the midpoint cannot be found as the crossing of two lines, because there are no lines. It must appear as the crossing of two circles. The straightedge buys nothing proved that the compass alone can construct every point that ruler and compass can — the Mohr–Mascheroni theorem — and the search makes the price concrete: six circles, against four moves with both instruments. No construction with five circles exists; the search examined 45,611 configurations of five circles or fewer before finding six.

Seven targets, with and without the ruler #

The table collects the minimum for seven targets. Some are free of lines by nature. The apex of the equilateral triangle on $AB$ takes two circles either way: it is the crossing of the circle about $A$ through $B$ and the circle about $B$ through $A$, Euclid’s first proposition. The regular hexagon on $AB$ takes five either way, and the ruler cannot help at all.

Others need lines, and the compass pays for their absence. The point beyond $B$, twice as far from $A$, is two moves with a ruler — the line $AB$ and the circle about $B$ through $A$ — and three circles without. The midpoint is four against six. The point above $A$ at the distance $AB$, making a right angle, is five against six. The two far corners of the square on $AB$ are five against seven. The point a third of the way from $A$ to $B$ is five against seven.

The three-circle construction of the doubled point shows how the compass makes up for the missing line. The first two circles, about $A$ through $B$ and about $B$ through $A$, cross at the two apexes above and below $AB$. The third is centred at the lower apex and passes through the upper one, so its radius is $\sqrt 3$ — and it meets the circle about $B$ exactly at $(2, 0)$, because that point is also $\sqrt 3$ from the lower apex. The line $AB$ is never drawn; the point where it would have crossed the circle about $B$ is found as the crossing of two circles instead, at the cost of one extra circle.

Two patterns stand out. The compass alone never does better, as it could not, since every compass-only construction is also a ruler-and-compass construction. And the penalty is small — at most two circles in every case here. The Mohr–Mascheroni theorem says the ruler is dispensable; the table says that, for these constructions, dispensing with it costs almost nothing.

The ruler alone reaches nothing #

The table has no third column, and the reason is instructive. With the ruler alone, starting from two points, exactly one move is possible — the line $AB$ — and it crosses nothing, so no new point ever appears. The ruler alone cannot construct even the midpoint from these two points, and the obstruction goes deeper than the count of moves: every construction with a ruler alone commutes with projective transformations of the plane, and a projective transformation can move the midpoint of a segment while fixing its ends.

One circle, and a straightedge showed that a single circle drawn once, with its centre marked, is enough to restore everything: the Poncelet–Steiner theorem. The search model here gives that circle a price, and the ruler-plus-one-circle constructions of that essay could be searched the same way, with the circle drawn once and every later move a line. The minimum costs would be higher than with a free compass, and they measure how much the compass is used for, rather than whether it is needed.

How the search avoids repeating itself #

The search is iterative deepening: try every construction of one move, then of two, then of three, stopping at the first depth at which the target appears. The first success is therefore the minimum, and every failure at a smaller depth is part of the proof. The same idea underlies every computer proof that consists of exhausting cases, from the four-colour theorem’s hundreds of configurations, which four colours and a proof nobody can read described, to the tables of small constructions here.

Without care the search would repeat itself hopelessly. Drawing circle 1 then circle 2 produces the same points as drawing circle 2 then circle 1, and a search that treated them as different would do the same work twice at every step, and $d!$ times over at depth $d$. So a configuration is identified by the set of objects drawn, ignoring their order, and a configuration already explored with at least as many moves left is never explored again. That one rule turns an impossible search into a feasible one for depths up to seven.

The square in five moves #

A textbook builds a square by raising a perpendicular at $A$, marking the length $AB$ along it, and repeating at $B$ — a construction whose perpendiculars alone cost several moves each. The search needs no idea of perpendiculars. It tries every line and circle available at each step and reports the first sequence that works: five moves, two lines and three circles, reaching both far corners at once.

The construction it finds uses a line through two crossing points of circles that happens to meet a circle exactly at a corner. That is typical of minimal constructions: they exploit coincidences — three objects through one point, a crossing that lands exactly where it is needed — that a systematic method would never rely on and a search finds immediately. The cheapest construction is rarely the most explicable one.

This is also why cheapest constructions are hard to prove by hand. A textbook construction can be checked step by step; a claim that nothing shorter exists is a claim about every sequence, including the ones that exploit coincidences nobody has noticed. The search notices them all, because it does not look for them — it enumerates.

The hexagon, where the ruler has nothing to add #

The regular hexagon is the cleanest case. Its corners and centre are all apexes of equilateral triangles built on known segments, and each apex is the crossing of two circles of equal radius. Five circles reach all of them, and the search with ruler and compass finds the same minimum: five moves, all circles. A line through two known points never produces a hexagon’s corner more cheaply than a circle does.

That makes the hexagon the one target in the table where the Mohr–Mascheroni theorem is not merely true but costless. It is also the figure the compass that will not open could draw most easily with a compass fixed at one opening, since every circle in the minimal construction has radius $|AB|$ — a coincidence of the target, not of the method.

A third, the first target that halving cannot reach #

Every other target in the table lies at a distance from $A$ built from halves, square roots and equilateral triangles. A third is different: $\tfrac13$ is not reachable by halving, and a construction must produce the factor three somewhere. With ruler and compass the search finds five moves; with the compass alone, seven circles, and the search had to rule out every construction of six circles first.

That compass-only minimum was the hardest number in the table to establish. The search examined 120,864 configurations of six circles or fewer, every one built and checked, before seven could be declared the minimum. Finding a seven-circle construction then required going one level further, where the configurations number in the millions. The whole computation takes about half a minute, and each further circle multiplies the work many times over.

How fast the configurations multiply #

The search is only possible because it counts each configuration once. Two sequences that draw the same circles in a different order produce the same points, and a search that did not notice would repeat itself endlessly; merging them cuts the work enormously. Even so, the count grows fast. With both instruments there are 3 configurations after one move, 16 after three, and 205 after four. Each configuration has more points, so it offers more moves, and the growth accelerates.

At the start the compass alone is slower to grow — it cannot draw a line through the two starting points, and its first two circles produce only the two apex points, so after two moves it has a single configuration. But it catches up, because every circle creates up to two new points with each earlier circle, while a line crossing a line creates at most one. Past four moves the counts run into thousands and then millions, and exhaustive search reaches only to about seven moves for either instrument.

That is why the question the previous essay left open is still open for the famous figures. A regular pentagon on $AB$ needs more moves than the search can reach, and the regular 17-gon that Gauss constructed in 1796 needs dozens. For those, every published construction is an upper bound, and nobody has a lower bound worth the name.

What the search measures, and what Lemoine measured #

Lemoine’s accounting, which the price of a construction followed, counted hand movements: placing the compass point, opening the compass, drawing the circle, each separately. A circle drawn with a compass already open to the right width costs less than one that must be reset. Under that accounting a construction that reuses one radius is cheap, and Euclid’s collapsing compass, which cannot hold a width, is expensive.

The search here counts objects, not movements: one line or one circle is one move, however it was set up. Under this count the collapsing compass costs nothing extra — a circle about one known point through another is exactly what Euclid’s compass draws — and the two accountings rank constructions differently. The four-move midpoint uses circles of the same radius twice, which Lemoine’s count would reward further; the six-circle compass-only midpoint uses several radii and would be priced higher.

Neither count is the true cost; each answers a different question. Lemoine’s is about the labour of a draughtsman. The count of objects is about the logical depth of a construction — how many steps of the form “take the crossing of these two” separate the target from the starting points — and it is the one for which a machine can prove minimality.

Still open: the cheapest pentagon #

For the regular pentagon on a given side, the regular heptadecagon, and the constructions of classical triangle geometry — the nine-point centre, the Brocard points — the fewest moves is unknown. Constructions are known, and some are known to be short, but no proof shows that any cannot be beaten. The search’s reach, about seven moves, falls short of all of them: every construction of the regular pentagon known takes more moves than that.

Two approaches might extend the reach. One is cleverer search: symmetry, since a construction and its mirror image are the same up to reflection; and pruning, since a move that creates no new point useful to any target can often be discarded. Each saves a constant factor against growth that is faster than exponential. The other is a lower bound that is not a search — some quantity attached to a set of points that grows by a bounded amount with each move, so that a target far from the start in that quantity needs many moves. Algebraic degree is such a quantity, and every step is a square root used it to decide what can be constructed at all; but degree grows too slowly to bound the moves in any construction anyone wants to know about. A vertex of the regular pentagon on $AB$ has coordinates of degree 4 over the rationals, and each move can at most double the degree of the points it creates, so at least two moves are needed — a bound that is true, proved, and useless, when the known constructions take several times as many.

The same search could be run with other instruments. Allow a move that slides a marked ruler until a marked length fits between two curves — the neusis of the mark that changes what is reachable — and new targets become reachable, among them a third of any angle. The minimum cost of trisecting with a marked ruler is a well-posed question of exactly the kind answered here, and its answer depends, as every answer here does, on precisely which moves are allowed. Whether a better invariant exists is not known.

What the pictures cannot show #

Every minimum in the table was established by the same exhaustive search, run afresh whenever the figures are made: it fails at the depth below the minimum and succeeds at the minimum. The constructions drawn are the first ones the search happened to find at that depth; there are often several of the same length, and a different order of trying moves would draw a different one. The search works with floating-point coordinates rounded to seven decimal places to recognise when two points coincide, so a pair of points closer than about $10^{-7}$ would be merged wrongly; none of the configurations reached here comes near that scale, but the search does not prove it.

The cost model is also a choice. A construction that uses a circle centred at a known point with a radius copied from elsewhere — allowed by a compass that holds its opening — is not a single move in this model, and allowing it would lower some of the numbers. The minima are minima for Euclid’s rules as stated here, and the essay’s claims are about those rules only.