Rows of three, planted on a cubic

In 1821 John Jackson’s Rational Amusement for Winter Evenings set its readers a puzzle in verse: plant nine trees in ten rows of three. It looks impossible. A three-by-three grid of trees gives eight rows — three across, three down, two diagonals — and every rearrangement that adds a row seems to break another.

Ten is possible, and the arrangement that does it is not symmetric in any obvious way. It is nine points on a curve of degree three. The reason a cubic is the right place to plant is that on a cubic, being in a line is a kind of addition, and a set of points closed under addition produces rows of three wholesale.

The question behind the puzzle is the orchard problem: given $n$ points in the plane, what is the largest number of lines holding exactly three of them? It is the mirror image of Sylvester’s question, which asks for as few two-point lines as possible, and it was settled for large $n$ in the same paper and by the same curves.

The ceiling that counting gives #

There is a quick upper bound. Every row of three contains three pairs of points, and no pair of points can lie on two different lines. So the rows use disjoint sets of pairs, and there are $\binom{n}{2}$ pairs in all:

$$t_3 \ \le\ \frac{1}{3}\binom{n}{2} = \frac{n(n-1)}{6}.$$

For nine points that is twelve rows. The bound is met only if every pair of points lies on a row of three — the configuration would be a linear space with all lines of size three, a Steiner triple system — and the ones that exist cannot be drawn with straight lines in the real plane. Sylvester’s theorem forbids it outright: every finite configuration has a line through exactly two of its points, so some pair is always wasted on an ordinary line, and the ceiling is never reached.

The ceiling also says something about what an optimal planting must look like. If $t_3$ is close to $n(n-1)/6$, then almost every pair of trees is on a row of three, and only a few pairs are left over for lines of other sizes. A line of four trees would use six pairs for a single line where two rows of three could have used six pairs for two, so rich lines are wasteful too. A good orchard is therefore made almost entirely of rows of exactly three, with a small remainder of ordinary lines taking the pairs that could not be fitted — and the size of that remainder is exactly what separates the best possible count from the ceiling.

So the truth lies somewhere below $n(n-1)/6$, and the question is how much below. Sylvester himself proposed an answer in the 1860s, and the answer came from a curve.

A curve on which a line is a sum #

The witch of Agnesi is the curve $y = 1/(1 + x^2)$, a bell-shaped hump named — by mistranslation — after Maria Agnesi’s 1748 textbook. Clear the denominator and it is $x^2 y + y = 1$, an equation of degree three: a cubic curve.

Parametrise it by an angle. Put $x = \tan\theta$; then $y = 1/(1 + \tan^2\theta) = \cos^2\theta$. As $\theta$ runs through a half-turn the point $(\tan\theta, \cos^2\theta)$ runs along the whole curve once, and the missing value $\theta = 90°$ corresponds to the point at infinity in the horizontal direction, which the curve approaches at both ends.

Now take a line $y = mx + c$ and ask where it meets the curve. Substituting gives $1 = (1 + x^2)(mx + c)$, that is

$$m x^3 + c x^2 + m x + (c - 1) = 0.$$

Its three roots are $x_i = \tan\theta_i$. By Vieta’s formulas the sum of their pairwise products is the coefficient ratio $m/m = 1$ — always, whatever the line. And the tangent addition formula says

$$\tan(\theta_1 + \theta_2 + \theta_3) = \frac{e_1 - e_3}{1 - e_2},$$

where $e_2$ is exactly that sum of pairwise products. Its denominator is $1 - 1 = 0$. So three points of the witch lie on a line exactly when their angles add up to $90°$, up to a multiple of $180°$. Collinearity has become arithmetic.

Choose the angles to make the arithmetic clean. Take $\theta_j = 90° + j \cdot 180°/n$ for $j = 0, 1, \dots, n - 1$. Three of these add to $270° + (j_1 + j_2 + j_3) \cdot 180°/n$, and that is $90°$ modulo $180°$ exactly when $j_1 + j_2 + j_3$ is a multiple of $n$. So three of the $n$ points are in a row precisely when their labels add to zero modulo $n$ — the arithmetic of a clock with $n$ hours.

The point $j = 0$ is the one at infinity, and it is not an embarrassment. Horizontal lines pass through it, and a horizontal line meets the hump at two points symmetric about the axis, whose labels $j$ and $n - j$ add to $n$. So every horizontal line through a symmetric pair is a row of three, with the third tree planted at infinity. The six-point figure has two such rows and two slanted ones, and the rule predicts all four.

Nine trees in ten rows #

With nine points the rule gives ten rows, and the figure recounts them from the coordinates rather than from the rule.

The count is the number of three-element subsets of $\{0, 1, \dots, 8\}$ whose sum is a multiple of nine. There are 84 subsets in all; they spread over the nine possible remainders almost evenly, and the remainder zero collects ten of them. The four horizontal rows are $\{0, 1, 8\}$, $\{0, 2, 7\}$, $\{0, 3, 6\}$ and $\{0, 4, 5\}$. The six slanted ones are the triples of nonzero labels adding to 9 or 18 — $\{1, 2, 6\}$, $\{1, 3, 5\}$, $\{2, 3, 4\}$, $\{3, 7, 8\}$, $\{4, 6, 8\}$, $\{5, 6, 7\}$ — and the drawing shows each as a straight line through three dots on the hump.

That is Jackson’s puzzle solved, with the solution explained. The trees are not placed by trial; they are the nine elements of a cyclic group, and the rows are the solutions of $a + b + c = 0$ in that group. The ten rows fall two short of the counting ceiling of twelve, and the missing rows correspond to the six ordinary lines, which use up the pairs that could not be placed in a row: six pairs on six ordinary lines, plus thirty pairs on ten rows, is all thirty-six.

Sylvester’s count, and why it comes out #

For general $n$ the number of three-element subsets of $\mathbb{Z}/n$ with sum zero has a closed form. Choose an ordered pair of distinct labels $a, b$; the third label is forced to be $c = -a - b$, and it is admissible unless it coincides with $a$ or $b$. Correct for those coincidences, divide by the six orderings of each triple, and the answer is

$$\left\lfloor \frac{n(n-3)}{6} \right\rfloor + 1.$$

This is Sylvester’s number. For large $n$ it is about $n^2/6$, which is the same order as the counting ceiling $n(n-1)/6$ and only about $n/3$ below it: the cubic construction wastes almost nothing.

The ten-point figure has twelve rows, which is Sylvester’s number for ten and also the true maximum for ten trees, established by exhaustive search. In each figure the rows are drawn from the determinant of every triple of coordinates, not from the rule about labels, and the construction also checks that no line ever meets the curve in four points — a line meets a cubic at most three times, so no row can accidentally grow into a row of four and spoil the count.

Whole numbers are not a group of the right kind #

The addition rule is not special to the witch. On the cubic $y = x^3 - 12x$, three points are in line exactly when their $x$-coordinates add to zero — a line $y = mx + c$ meets it where $x^3 - (12 + m)x - c = 0$, a cubic with no $x^2$ term, whose three roots therefore sum to zero. Since the coordinates can be whole numbers, the rule can be checked with exact integer arithmetic. So why not plant the trees at whole-number points?

The whole numbers from $-4$ to $4$ give eight rows: the four pairs $\{\pm k\}$ with $0$, and the four triples $\{1, 2, -3\}$, $\{1, 3, -4\}$ and their negatives. The cyclic group gave ten. The difference is that the integers have no finite subgroup. A sum like $3 + 4 = 7$ leaves the window, so the pair $\{3, 4\}$ has no third partner and its line is wasted as an ordinary line. In $\mathbb{Z}/9$ nothing ever leaves: every pair has a third element, and the only pairs wasted are the ones whose third element coincides with one of them.

That is the whole secret of the construction. What is wanted is a finite set of points on a cubic that is closed under the operation that collinearity defines, and a finite closed set is a finite subgroup. The curve $y = x^3 - 12x$ has a singular point at infinity of the kind whose smooth points form the additive group of the real line, which has no finite subgroups; the witch’s singular point is of the other kind, whose smooth points form a circle, which has a finite subgroup of every order. On a smooth cubic — an elliptic curve — the real points form one or two circles, and the finite subgroups are there too.

The small numbers that break the pattern #

Sylvester’s number is not always the maximum. Two small cases beat it.

Seven trees can be planted in six rows, one more than the formula’s five. The arrangement is the triangle with its three midpoints and its centroid — the configuration of Kelly and Moser that also has the fewest ordinary lines for its size. Its six rows are the three sides and the three medians, and it is the real plane’s nearest approach to the Fano plane, which would have seven. Eleven trees can be planted in sixteen rows, one more than the formula’s fifteen, by an arrangement found by search.

These exceptions are the reason the orchard problem stayed open so long. Any proof that Sylvester’s number is the maximum has to explain why seven and eleven are different and why the exceptions stop, and a counting argument of the kind that gives the ceiling cannot see the difference between eleven and thirteen. Small cases do not predict large ones here; they contradict them, twice, and then fall silent. The two exceptions are also not built from cubics in any obvious way. Kelly and Moser’s seven points do not lie on a single cubic with the triangle’s lines as chords of a group; they lie on a triangle and its medians, which is a degenerate object — three lines — and the degenerate cubics, unions of lines and conics, are exactly where Green and Tao’s classification has to take special care.

What Green and Tao proved #

In 2013 Ben Green and Terence Tao proved that for every sufficiently large $n$, the maximum number of three-point lines is exactly Sylvester’s number $\lfloor n(n-3)/6 \rfloor + 1$. The same paper proved the Dirac–Motzkin conjecture on the fewest ordinary lines, and the two results come from one structure theorem.

The connection is the counting above, run backwards. A configuration with many rows of three uses up almost all its pairs on those rows, so it has few ordinary lines — the ceiling calculation shows that every pair not covered by a row sits on a line of some other size, and there is not room for many. So an orchard-optimal configuration is a configuration with few ordinary lines, and Green and Tao’s structure theorem says any such configuration lies mostly on a cubic curve. On a cubic, collinearity is the group law, and the configuration is nearly a coset of a finite subgroup. Counting the rows of a subgroup gives exactly Sylvester’s number, and the proof shows that nothing close to a subgroup does better.

The structure theorem needs $n$ to be large, with a threshold far beyond what any search reaches. Between the small cases settled by computer and the threshold, the answer is believed and not proved.

A single choice with three consequences #

The cubic curve does something here that nothing in the statement of the puzzle suggests. The puzzle asks about trees and rows; the answer is a group, and the group lives on a curve because a line meets a cubic in three points and the third point is determined by the other two. That single fact — two points of a cubic determine a third — is the chord-and-tangent construction, and it is the same fact that makes a cubic’s points over a finite field count out so closely to their expected number, and the same fact that lets one rational point on a curve generate others, as a single point of the circle generates every Pythagorean triple by the analogous construction on a conic.

In this essay the construction has done three jobs in the space of one figure: it has explained why the nine trees can be planted, it has counted the rows for every $n$, and — through Green and Tao — it has turned out to be the reason nothing does better. That the arithmetic of a curve settles a question about dots on a page is the connection worth carrying away, and nothing about dots on a page predicts it.

The pairs a good orchard wastes #

Every planting that falls short of the ceiling wastes some pairs on lines that are not rows of three, and the construction says exactly which.

In the cyclic group, a pair $\{a, b\}$ is on a row unless its third element $-a - b$ coincides with $a$ or $b$ — that is, unless $2a + b \equiv 0$ or $a + 2b \equiv 0$. Those are the pairs in which one point is the tangent partner of the other: the line through them touches the curve at one of the two, meeting it there twice, and has no room for a third tree. On the witch with nine points there are exactly six such lines, and they are the six ordinary lines of the nine-point figure. At ten points there are nine. Every wasted pair is a tangent.

That gives the construction a clean accounting. Of the $\binom{n}{2}$ pairs, about $n$ are wasted on tangent lines and every other pair sits in a row of three, so $t_3 \approx (n^2/2 - n)/3 = n(n-3)/6$ — Sylvester’s number, recovered without any counting of subsets. And it shows why the construction cannot be improved within its own terms: a tangent line exists at every point of a cubic, and the pair it produces is wasted however the group is chosen.

It also closes the loop with the other half of the subject. An orchard configuration with $t_3$ close to Sylvester’s number has only about $n$ ordinary lines, not the $n/2$ of Böröczky’s configurations; the two extremal problems are solved by close relatives, not by the same sets. The orchard wants every line through the group’s tangents to be ordinary, which costs $n$ of them, while Böröczky’s sets arrange for the tangents to pick up points at infinity and cost only $n/2$.

Where the pictures run out #

Every figure is a finite check, and the maximum is not. The drawings show that the cubic construction achieves Sylvester’s number for three to fourteen trees; they cannot show that no other arrangement does better. For small $n$ that is known by computer search, which also found the two exceptions. For large $n$ it is Green and Tao’s theorem, and for the $n$ in between it is not known at all.

Collinearity is decided by a margin, not exactly. The witch’s points have irrational coordinates, so the figures decide which triples are collinear in floating point, with a check that every triple is either within $10^{-9}$ of collinear or at least $10^{-3}$ away. The exact statement is the tangent-addition identity above. The integer cubic’s figure, by contrast, is exact.

The point at infinity is drawn as an arrow. One of every set of $n$ trees is at infinity, where the horizontal lines meet, and the drawing can only point at it. Any projective transformation that moves the line at infinity into view would put that tree on the page with all the same rows — at the cost of turning the witch into a curve that no longer looks like a hump, since the curve’s single branch crosses every line, the new one included, and no transformation can make the whole of it bounded.

The best-known values are quoted. The rings in the table for seven and eleven trees are records from the literature, not searches run here, and the table checks only that the construction never exceeds them.

Still open: the middle of the range #

The orchard problem is solved for all large $n$ and, by search, for the small $n$ up to the low teens. What is missing is everything between: for $n$ from the edge of what computers can exhaust to the far edge of Green and Tao’s threshold, the conjecture that Sylvester’s number is the maximum is supported by every example anyone has found and proved by nothing. Whether any third exception exists, after seven and eleven, is not known.

There is also a question about how many optimal configurations there are. Green and Tao show that near-optimal configurations lie close to cosets of subgroups of cubic curves, but the classification is up to a bounded number of changes, and how many genuinely different ways there are to plant $n$ trees in the maximum number of rows — how many of them are projectively distinct, and whether all of them come from cubics exactly rather than approximately — has only partial answers.

And the problem has natural variants that are wide open. Ask for rows of four rather than three and the cubic trick no longer works — a line meets a cubic in only three points, so a set on a cubic has no rows of four at all — and the best constructions and best bounds for four-in-a-row are far apart. Ask the question in three dimensions, for planes through three points or lines through three, and the extremal configurations are not known even conjecturally in most cases.