The cheapest curves at each degree

Two circles for the price of one searched the equations of four catalogue curves for a cheaper one and found none, except on the circle, where a second concentric circle came along for nothing. That search was confined to one family at a time: the multiples of one curve’s own equation. It answered whether a given curve had been priced fairly — the question the price is on the equation had raised by padding equations and watching their cost move. It could not say which curves are cheap, because it only ever looked at curves somebody had already chosen.

This essay runs the same search on the whole space, which is the form a demand that is an equation gives every problem in this field. Take every polynomial in $x$ and $y$ of degree at most $d$ — every curve of that degree the arm could be asked to draw — and ask which of them costs the compiled machine the fewest terms. The answer is a census of the cheapest curves at each degree, and it comes back far simpler than anyone would guess from the costs the field has published. It does not depend on the degree at all.

What a term is, and why the search can be exhaustive #

The compiler turns a polynomial into a machine by first rewriting it in the arm’s own variables. The tip of a two-link arm with equal links $\ell$ sits at $\ell(\cos\alpha + \cos\beta,\ \sin\alpha + \sin\beta)$, and every curve is a sum of cosines: substitute that into any polynomial and it becomes a constant plus a finite sum of terms $\cos(m\alpha + n\beta + \phi)$ with whole numbers $m$ and $n$. Each surviving pair $(m, n)$ is a term, and each term is a gadget in the machine — an angle multiplied, an angle added, an offset rotated to its angle. What a curve costs is how many pairs survive, and the constant is free.

The rewriting is linear in the polynomial’s coefficients. So for any chosen set $S$ of frequency pairs, the polynomials whose expansion lives inside $S$ — every other pair’s amplitude nought — form a linear subspace, the null space of the rows belonging to the pairs outside $S$. That turns “the cheapest curve of degree $d$” into a question with a finite answer. Try every $S$ of one pair, then every $S$ of two, and so on. The first size at which some $S$ admits a polynomial of exactly degree $d$ is the minimum, and since every set of that size is tried, every support that reaches the minimum is found.

“Exactly degree $d$” matters. A polynomial of lower degree is also in the space and is usually cheaper, since a circle is always in the space of sextics. So a support counts only if the polynomials it admits include one whose degree-$d$ part is not nought. And a support counts at its own size only if a generic member of its subspace uses every pair in it, so a set that admits a curve through fewer of its pairs is attributed to the smaller set.

The census #

At degree six a polynomial has 28 coefficients and its expansion can reach 42 frequency pairs, and a polynomial chosen with nothing special about it uses all 42. The search found the minimum at one pair. At degree five, 21 coefficients and 30 pairs; the search tried all 30 single pairs and all 435 pairs of pairs, and the minimum is two. The whole table is short:

One term at every even degree and two at every odd one, and at every degree exactly one support reaches the minimum: the single pair $(k, -k)$ at degree $2k$, and the two pairs $(k, -k-1)$ and $(k+1, -k)$ at degree $2k+1$. Degree sets the size of the space and the price of a generic curve, which grows as the square of the degree. It sets no floor at all under the cheapest one.

That overturns an assumption the field’s own vocabulary carries. Five bars for a line, four hundred for a quintic is a scale of rising difficulty, and it was measured on catalogue curves, each of which is generic for its degree in the sense that matters: nothing about it cancels. A curve that was chosen for the arm rather than for its shape can have any degree and still cost what a circle costs.

One symmetry forbids anything cheaper #

The census is a measurement to degree six. The reason it comes out this way is short enough to hold at every degree, and it is a fact about the arm, not about curves.

The arm’s two links are the same length. Swap them — call the first link’s angle $\beta$ and the second’s $\alpha$ — and the tip does not move, since $\cos\alpha + \cos\beta$ and $\sin\alpha + \sin\beta$ do not care which is which. Every polynomial in $x$ and $y$ therefore expands to something unchanged by swapping $\alpha$ and $\beta$, and its amplitude on the pair $(m, n)$ equals its amplitude on $(n, m)$. On random polynomials of every degree to six the two amplitudes agree to the last bit of the arithmetic.

So a term comes with its mirror unless it is its own mirror, and a pair is its own mirror — after folding each cosine’s two conjugate halves together — only on the two diagonals of the picture. On $m = -n$ the term is $\cos(k\alpha - k\beta + \phi) = \cos(k\theta + \phi)$ with $\theta = \alpha - \beta$ the angle between the links, and the tip’s distance from the pivot depends on $\theta$ alone: $r^2 = 2\ell^2(1 + \cos\theta)$. Level sets of such a term are circles about the pivot. On $m = n$ the term is $\cos(k(\alpha + \beta) + \phi)$, and $(\alpha + \beta)/2$ is the direction of the tip from the pivot. A term there depends only on which way the tip points, so it is constant along every ray from the pivot — and a polynomial that is constant along every ray through a point is constant, because every ray passes through that point. A lone $m = n$ term is never an equation.

That leaves the $m = -n$ diagonal as the only place a single term can be a curve. At degree $2k$ the one-term curves are functions of $\cos\theta$ of the right degree, which is $\cos k\theta = c$ and nothing else.

At odd degree there is not even that. Each factor of $x$ or $y$ in a monomial moves one of $m$ or $n$ by one, so a polynomial of odd degree reaches only pairs with $m + n$ odd. Both diagonals have $m + n$ even — nought on one, $2k$ on the other — so no term of an odd-degree curve is its own mirror, every term brings its mirror with it, and an odd-degree curve costs at least two. The census finds that two is reached, by exactly one mirror pair at each odd degree, and it finds nothing at one.

k circles for the price of one #

The even-degree minimisers are Chebyshev’s polynomials in disguise. $\cos k\theta$ is the $k$-th Chebyshev polynomial of $\cos\theta$, and $\cos\theta = r^2/2\ell^2 - 1$ is a quadratic in $x$ and $y$, so $\cos k\theta$ is a polynomial of degree $2k$. It has one term, because it is one cosine. And $\cos k\theta = c$, for any level $c$ between −1 and 1, is $k$ concentric circles about the pivot, one for each angle $\theta_j$ in $(0, \pi)$ at which the cosine takes that value.

At $c = 0.3$ with unit links, one circle sits at squared radius 2.600, two at 3.612 and 0.388, three at 3.825, 1.797 and 0.378, and four at 3.901, 2.623, 1.377 and 0.099. The compiled machine for each traces one of its circles — 2.600, 3.612, 1.797 and 2.623 in turn — and sits on it to $5 \times 10^{-14}$ of its squared radius over its whole run. Two circles for the price of one found the case $k = 2$ as a coincidence and explained it by parity: two circles whose squared radii sum to $4\ell^2$ make an even polynomial in $\cos\theta$, which has only even harmonics. That is $\cos 2\theta = c$ exactly — its two roots in $\cos\theta$ are $\pm\sqrt{(1+c)/2}$. The parity rule then said six circles in three such pairs cost three terms, which is true of the pairs it built. The census says six circles can cost one, if they are placed where $\cos 6\theta = c$ puts them, and the compiler that built the pairs confirms it: that curve has degree twelve and one term.

So the free circle was never a property of pairs. It is the whole Chebyshev family, and pairing is the first member of it that parity alone could see.

The lead left by the circle’s tie asked whether free partners are always circles. On the whole space of equations to degree six, the answer is yes. Every one-term curve lies on the $m = -n$ diagonal, where the level sets are circles about the pivot. Nothing else comes free with anything.

At odd degree, a line with circles thrown in #

The odd-degree minimum is a mirror pair, $(k, -k-1)$ and $(k+1, -k)$, and the pair has a meaning as clear as the circles’. The two exponentials $e^{i((k+1)\alpha - k\beta)}$ and $e^{i((k+1)\beta - k\alpha)}$ share a factor $e^{i(\alpha+\beta)/2}$, the tip’s direction. What is left is $e^{i(k+\frac12)\theta} + e^{-i(k+\frac12)\theta} = 2\cos\big((k+\tfrac12)\theta\big)$. The tip itself is $2\ell\cos(\theta/2)$ in that same direction, so the pair’s real part is the tip’s projection on some fixed line through the pivot, times

$$W_k(\cos\theta) = \frac{\cos\big((k+\tfrac12)\theta\big)}{\cos(\theta/2)},$$

which is a polynomial in $\cos\theta$ of degree $k$ — Chebyshev’s polynomial of the fourth kind. The cheapest curve of degree $2k + 1$ is therefore $x \cdot W_k(\cos\theta) = c$, turned to any direction about the pivot.

At degree three, with unit links, it is $x(x^2 + y^2 - 3) = c$. At the level nought it factors, into the line $x = 0$ through the pivot and the circle of squared radius 3. A line through the pivot costs two terms on its own, and the circle comes with it free, as the second circle came with the first. At degree five the level-nought curve is the same line with two circles, at squared radii $(5 \pm \sqrt5)/2$, 3.618 and 1.382. At any other level the curve is a single irreducible piece: a cubic, or a quintic, costing exactly what a straight line costs.

That completes the answer to the lead. The free partners are circles about the pivot, always, and what they partner is either another circle — at even degree — or a line through the pivot, at odd degree. Both are drawn from the two things the arm can compute without any work: its links’ relative angle and the direction of its tip.

Conics: one term, then nothing until three #

The census can be run one size past the minimum, and at degree two the result is a price list for conics that no hand calculation would have produced.

A circle about the pivot costs one term. Nothing of degree two costs two: the search tried all fifteen pairs of the six frequency pairs a conic can reach and not one admits a conic. The next price is three, and exactly two supports reach it. One is $(0,1), (1,0), (1,-1)$ — the circle term and a line’s mirror pair — which is a circle centred anywhere. The other is $(0,2), (1,1), (2,0)$ — a mirror pair and the direction term — which is a rectangular hyperbola centred on the pivot, or at the level nought a pair of lines crossing there at right angles. Measured on examples, an ellipse about the pivot costs four, a pair of lines crossing at the pivot at any other angle four, a rectangular hyperbola centred elsewhere five, and a parabola or a general conic six.

The mirror argument narrows the candidates for a two-term conic to very few. A conic reaches six pairs: two self-mirrored ones, the circle term $(1,-1)$ and the direction term $(1,1)$, and two mirror pairs, $(1,0)$ with $(0,1)$ and $(2,0)$ with $(0,2)$. Two terms means either both self-mirrored pairs or one mirror pair. The exhaustion is what rules each out: neither choice admits a polynomial of degree two, and the census’s null spaces say so directly. A line’s mirror pair is a line and nothing more, and the other mirror pair becomes a curve only with the direction term added — the rectangular hyperbola at three.

Terms are one currency, and bars are another #

The field has always tracked more than terms, and doubling is cheaper than adding is why the census cannot be read as a statement about machines of the same size.

The cheapest curves’ machines have 5 bars at degree one, 11 at degree two, 27 at three, 17 at four, 37 at five, 27 at six, 23 at eight, and 33 at ten and at twelve. A single term $\cos k\theta$ still needs the angle $\theta$ multiplied by $k$, and the multiplier is built from doubling gadgets and adders. Four is two doublings, so degree eight is cheaper than degree six, whose three is a doubling and an addition. The odd degrees carry two terms, each needing its own multiplied angle, and they cost more than the even degrees on either side of them.

So the census does not say a degree-twelve curve is as easy as a circle. It says the part of the machine that grows with a generic curve’s degree — the transport of dozens of computed angles to wherever they are summed — is absent from these curves, and what remains grows like the number of doublings in $k$. Degree twelve costs 33 bars. A quintic from the catalogue costs about four hundred.

Two routes to the same curves #

The census’s supports and the Chebyshev construction are separate computations. The census knows nothing about Chebyshev: it enumerates sets of frequency pairs and solves for null spaces. The construction knows nothing about null spaces: it builds $T_k$ and $W_k$ by their recurrences, substitutes $\cos\theta = r^2/2 - 1$, and expands. At every degree from one to six, the one support the census finds is exactly the set of pairs the construction’s own expansion has. And the three-dimensional family of cubics it finds — a constant and two directions — is $x \cdot W_1 = c$ turned about the pivot.

What the census does not settle #

Degree seven and above. The census is exhaustive to six. The mirror argument holds at every degree and the Chebyshev curves reach its bound at every degree, so the minimum is one or two at every degree; that the minimising support is unique beyond six is not measured.

Arms with unequal links. Everything rests on swapping the links leaving the tip alone. With links of different lengths the swap moves the tip, the mirror symmetry is gone, and the circle terms are no longer the only self-mirrored ones. Whether the cheapest curves then cost more, or fewer, is not measured.

Which component the machine draws. Each Chebyshev curve is several circles, and the compiled machine traces one of them — a mechanism moves continuously and the circles are disjoint. The census counts terms for the whole vanishing set, not for the component a designer wanted.

Precision at high degree. The one-term reading at degree twelve depends on cancellations among coefficients in the thousands, and two circles for the price of one found such cancellations fail in double precision at degree sixteen. The census stops at six partly for that reason.

Still open: the cheapest curve near a given one #

The census says which curves are cheap, and the answer is narrow: circles about the pivot, and lines through it, in Chebyshev’s arrangements. A designer rarely wants one of those. What a designer has is a curve — a cam track, a coupler path, an ellipse — and the question the census makes askable is how far the nearest cheap curve is.

The distinct argument would be a trade between terms and exactness. Fix a target curve and a budget of $s$ terms, and find the curve with that many terms that is closest to the target over the arc a machine would draw. At $s$ equal to the target’s own count the distance is nought; below it the distance is positive, and the sequence of distances as $s$ falls is a price curve that no measurement here has drawn. Exact costs more than close measured the same trade for approximate straight-line mechanisms against exact ones. This would be the version inside the compiler, and it would say whether a catalogue curve’s cost is spread over many terms that each matter, or concentrated in a few large ones with a long tail that a close machine could drop.