The price of a construction

Three theorems about the classical instruments all have the same shape. The straightedge buys nothing: a compass alone reaches every point that a compass and straightedge reach together. One circle and a straightedge: a straightedge reaches all of them too, if a single circle has been drawn somewhere. The compass that will not open: a compass fixed at one opening, with a straightedge, loses nothing either. Each theorem takes something away and shows the reach is unchanged.

None of them says what the reach costs, and the cost changes a great deal. Reach is settled by these theorems; price is not, and the subject that prices a construction is called geometrography. It was founded by Émile Lemoine in 1888, and its unit is a single movement of the hand.

A bill for every movement #

Lemoine broke every construction into five elementary acts. Laying the edge of the ruler through a point is one act, and drawing the line along it is another, so a line through two given points costs three: two placements of the ruler, one stroke. Putting a leg of the compass on a point is an act, and so is drawing the circle, so a circle with a given centre through a given point also costs three: one leg on the centre, one on the point, one sweep. A fifth act, putting a leg on an unspecified point of a line, never arises in anything below.

The total is the construction’s simplicity. The placements alone — the acts where the hand must hit a point, and can miss it — make up its exactitude, a measure of how many chances for error there were. A stroke cannot be inaccurate in the same way; the line goes where the ruler lies.

The hero figure is the textbook midpoint. Circle 1 is drawn about $A$ through $B$, and costs three. Circle 2 is drawn about $B$ with the same opening, and costs two — the compass already holds the radius, so only the centre needs placing. Their two crossings are joined by line 3, and the segment itself is drawn as line 4, each costing three, and the midpoint is where lines 3 and 4 cross. Eleven acts, seven of them placements. The saving on circle 2 is the whole reason Lemoine’s accounting is interesting: the modern compass remembers its opening, and a construction that exploits that memory is cheaper than one that does not.

Every construction on this page was run, not described. The circles and lines were computed, the intersections found and chosen by position, and the result checked at the end — here, that the point found is exactly halfway along. The bill is then read off the run.

The compass alone pays more #

The midpoint can be found with no ruler at all, and the straightedge buys nothing showed how: step the radius three times round a circle to reach the point $C$ twice as far from $A$ as $B$ is, then send $C$ back through the circle about $A$ by inversion.

Seven circles. The first four share one opening, the length $AB$, so after the first they cost two acts each: that is the stepping round circle 1 that lands on $C$. Circle 5 needs a new opening, $CA$, twice as long; circle 6 another, the distance from $D$ back to $A$; circle 7 reuses it, because $E$ is $D$’s mirror image and lies at the same distance from $A$. Seventeen acts in all, ten of them placements.

Dropping the ruler raised the price from 11 to 17. That is the general pattern, and it is predictable. The compass-only theorem is proved by showing how to find, with circles alone, every intersection that involves a line — a line meeting a circle, or two lines meeting — and each such simulation takes a fixed number of extra circles. So a construction with a given number of line steps can be translated into a compass-only construction at a cost of a bounded number of extra acts per line step: the price rises by at most a constant factor. The reach is the same; the factor is the price of the missing instrument.

The factor can be worse than this example suggests. The midpoint is a case where the compass-only route is unusually clean, because inversion does exactly the work needed. A general line–line intersection with the compass alone takes considerably more circles than two lines take with a ruler, and a construction built mostly out of lines can grow by a large multiple when the ruler is taken away.

Euclid’s compass, which forgets #

The modern compass holds its opening when lifted. Euclid’s postulates do not grant that. The third postulate allows a circle to be drawn with a given centre through a given point — a circle defined by two points, not by a centre and a remembered length. The traditional reading is that Euclid’s compass collapses when lifted from the paper, and the second proposition of the Elements is there to show that the loss does not matter: a length can still be copied to any other point.

The construction is ingenious and long. Build an equilateral triangle $ABD$ on $AB$, with circles 1 and 2. Draw the lines $DA$ and $DB$ and extend them. Circle 5, about $B$ through $C$, meets the extension of $DB$ at $G$, so $BG$ equals $BC$. Circle 6, about $D$ through $G$, meets the extension of $DA$ at $L$; since $DA = DB$ and $DL = DG$, subtracting gives $AL = BG = BC$. Circle 7, about $A$ through $L$, is finally the circle that was wanted.

It costs twenty-one acts. With a compass that holds its opening, the same circle costs four: a leg on $B$, a leg on $C$, a leg on $A$, and the sweep. The collapsing compass reaches the same circle — Euclid’s proposition proves it always can — at more than five times the price. And every circle in the construction costs the full three acts, because a collapsing compass can never reuse an opening; the saving the modern compass made on circle 2 of the midpoint is not available here at all.

So the “compass equivalence theorem”, as Proposition I.2 is sometimes called, is exactly the kind of statement the earlier theorems were: the reach is unchanged. Lemoine’s accounting shows what the equivalence hides. Anyone who has ever set a compass to a length and carried it across a drawing has been spending four acts on something that, done Euclid’s way, takes twenty-one.

A cheaper way to copy a length #

Euclid’s route is not the cheapest, even with his instruments. There is a construction that copies a length with a collapsing compass and no ruler at all, and it is cheaper than his.

The idea is a reflection. Circles 1 and 2, about $A$ through $C$ and about $C$ through $A$, cross at two points $X$ and $Y$ that lie on the perpendicular bisector of $AC$ — the mirror line that swaps $A$ and $C$. Reflecting $B$ in that line gives a point $B'$ whose distance from $C$ equals $B$’s distance from $A$, because a reflection preserves distances and sends $A$ to $C$. And $B'$ can be found without drawing the mirror line: it is the second crossing of the circles about $X$ and about $Y$ through $B$, since every point of the mirror is equidistant from $B$ and $B'$. Circle 5, about $C$ through $B'$, is the one wanted.

Five circles, fifteen acts. Euclid’s own instruments could have done his second proposition for fifteen instead of twenty-one, and without the ruler. The saving is not a matter of cleverness in bookkeeping; the two constructions use different ideas, one a pair of similar triangles made by extending lines, the other a reflection made by pairs of circles. Lemoine’s measure is what makes the comparison possible at all — without a price there is no sense in which one proof of the same fact is cheaper than another.

The regular hexagon, almost for free #

Some constructions are very cheap, and the reason is always the same: an opening reused many times.

The first circle sets the opening to the radius, three acts. Every later circle has the same radius, centred on a corner already found, and costs two: circle 2, about $A$, gives the corners on either side of it, and three more circles give the other three corners. Eleven acts for six points, fewer than two per corner — against eleven for the single midpoint of the first figure. The hexagon is cheap because the side of a regular hexagon equals its radius, so one opening does every job, and this is the geometric fact that the compass-only midpoint quietly exploited when it stepped the radius three times round a circle to double a length.

The whole bill, compared #

Put side by side, the constructions show which choices cost what.

Three comparisons stand out. The midpoint costs 11 with ruler and compass and 12 with ruler and collapsing compass — the only difference being circle 2, which can no longer reuse circle 1’s opening. It costs 17 with the compass alone and 21 with a collapsing compass alone: removing the ruler costs more than removing the compass’s memory. Copying a length runs from 4 to 21 across the instruments, the widest spread in the table, because it is the one task where the memory of the compass is the task. The hexagon costs about as much as the midpoint while producing six points, which is what an efficient construction looks like: every act does work for several later ones.

The table has a moral that the theorems cannot state. The three theorems about weakened instruments each said that nothing is lost. Measured, something is always lost, and the amounts differ by factors of five. Which instrument to give up depends entirely on the task: a draughtsman copying many lengths needs a compass that remembers, and one bisecting many segments can do without the memory at little cost.

A cost model before there were machines #

Geometrography is easy to dismiss as bookkeeping for draughtsmen, and in 1888 that is roughly what it was: Lemoine wanted a way to say that one construction of a triangle’s inscribed circle was better than another, and “better” had to mean fewer movements of the hand. What he actually built was something with a longer future — a cost model, a fixed list of elementary operations each charged one unit, against which any procedure can be priced and any two procedures for the same task compared.

That is exactly the move the theory of algorithms makes. What two points can build already treated the instruments as two operations applied to a growing set of points, which is the language of a machine; Lemoine’s contribution was to count the applications. Once they are counted, a new kind of question becomes askable: not can this point be reached, but how cheaply, and is the cheapest route known. Those are the questions that turn a solvability theorem into a complexity theorem, and the compass-only theorem is a clean example of the shift — its proof by inversion in a circle is a reduction, a way of simulating one machine’s operation by a fixed number of another’s, and the fixed number is what bounds the extra cost.

The pattern recurs across mathematics. The rules of a proof system reach exactly the valid formulas, and how long the proofs must be is a separate and much harder question; the instance that has to be guessed is one place where the cost, not the reach, is what carries the difficulty. Geometrography is the same distinction drawn with a ruler: two instrument sets with identical reach can differ by factors of five in price, and the price is what a user of the instruments actually pays.

Why a cheapest construction is hard to certify #

Every bill in the table is the price of a construction. Whether it is the price of the cheapest construction for its target is a different question, and a much harder one.

To show that the midpoint cannot be found with the compass alone in fewer than some number of acts, every construction with fewer acts has to be ruled out. There is no algebraic shortcut: the constructible numbers are priced in square roots, and that pricing says how many field extensions a point needs, which is a lower bound on the number of intersections but says almost nothing about circles that are drawn only to help. A construction’s cost depends on the order of its steps, on which openings are reused, on which intersections are chosen, and the number of possible sequences explodes with each step: each new point multiplies the circles that could be drawn next.

So cheapest constructions are found the way the rest of this collection finds things it cannot derive — by exhaustive search — and only for small targets. Computer searches over all constructions of a few steps have settled the minimum for a number of simple tasks, such as bisecting a segment or an angle, erecting a perpendicular, or inscribing a square, when the count is of circles and lines drawn. For anything larger the search is out of reach. That is the sense in which the compass that will not open called geometrography the one part of this subject with open problems in it: the reach of every instrument set is known exactly, and the price of almost nothing is.

What the drawings cannot show #

The act of placing. Lemoine’s exactitude counts placements because they are where error enters, and every construction here is computed in exact positions. A drawing made by hand would have a small error at every placement and the errors would compound through each later step; the figures show the idealised construction and no amount of looking at them conveys how much a long construction drifts on paper. That drift is what exactitude was invented to predict.

That the chosen construction is the right one. The figures draw one construction per task, chosen because it is classical or cheap. Other constructions reach the same point by different routes and at different prices, and nothing in a picture of one route shows that a cheaper route exists. The reflection figure is the proof by example: Euclid’s construction, drawn alone, looks perfectly efficient.

Which conventions the bill depends on. Lemoine’s five acts are one reasonable way of pricing a construction, and different conventions give different numbers. Some later accounts count only circles and lines drawn, some charge for choosing an intersection, some treat reusing an opening as a separate act. The rankings in the table are fairly robust to these changes; the exact numbers are not, and should be read as prices in one currency.

Still open: the cheapest route to the familiar figures #

For the simplest constructions, exhaustive search has found the fewest circles and lines needed. For the figures that made the subject famous — the regular pentagon, the regular 17-gon whose constructibility Gauss proved in 1796, the constructions of classical triangle geometry — no construction is known to be the cheapest possible. Many constructions of the 17-gon have been published, each shorter than the last by some count, and there is no proof that any of them cannot be beaten.

The obstacle is the one above. A lower bound on cost has to account for every possible auxiliary circle, and no known invariant of the constructible points does that. Whether any general method exists for proving a construction cheapest — short of searching every shorter one — is not known.

Reach and price #

The theorems about weakened instruments answer the question of reach and are finished. Lemoine’s accounting answers the question of price, and it tells a different story: a missing ruler multiplies the cost of a midpoint by about one and a half, a compass that forgets its opening multiplies the cost of copying a length by five, and a cleverer construction with the same forgetful compass can claw back a third of that. The hexagon comes nearly free, because one opening does all its work.

What the theorems establish once, for every construction, the bill establishes one construction at a time — and the cheapest construction for a given target is, for almost every target anyone cares about, unknown.