The triangle a triple point buys

Draw five straight lines in a star, and they cut out five triangles round a pentagon. Draw seven with care and eleven triangles appear. Kobon Fujimura, a Japanese writer of puzzles, asked how many non-overlapping triangles $n$ straight lines can form, and Martin Gardner made the question well known. It belongs to the family of questions about how lines and points can sit together, and it is closely tied to the count that forced three ordinary lines, because a count of the same sort gives both the fewest triangles and the most.

Everything about the small cases seemed settled, and tables give 1, 2, 5, 7, 11, 15, 21 for $n$ from 3 to 9. Listing every arrangement turns up something those tables do not say. Up to eight lines, all arrangements of the ordinary kind, in which no three lines pass through a point, can be examined one at a time. At eight lines they stop at 14. Fifteen is real, and it is possible only with an exact coincidence.

A ceiling from counting pieces #

The upper bound is a counting argument of the type that appears throughout this subject. Each of $n$ lines in general position is crossed by the other $n - 1$ at distinct points, which divides it into $n - 2$ bounded pieces and two rays. There are therefore $n(n - 2)$ bounded pieces in all. A triangle uses three of them. And a piece can be a side of at most one triangle: if both of the regions on either side of it were triangles, then their other sides would have to cross in two places, which two straight lines cannot do. So:

$$\text{triangles} \le \left\lfloor \frac{n(n - 2)}{3} \right\rfloor,$$

a bound attributed to Saburo Tamura. At five lines that is exactly five. At seven it is eleven with two pieces unused. It is met at 3, 4, 5, 7 and 9 lines, and at 13, 15 and 17, with constructions that rely on a large amount of symmetry.

G. Clément and J. Bader showed in 2007 that the bound cannot be met when $n$ is $0$ or $2$ modulo 6. Roughly, every piece being used forces an alternating pattern of triangles and other regions along each line, and for those values of $n$ that pattern cannot be closed up. Laurent Bartholdi, Jérémy Blanc and Sébastien Loisel took this further for even $n$. So at $n = 8$, where the first bound gave 16, the improved bound gives 15. The tables say that 15 is reached, and for a long time that appeared to be the end of the story for this value of $n$.

Listing every arrangement #

To list arrangements, it is convenient to loosen “straight line” slightly. Allow pseudolines, curves that run from one side of the plane to the other and cross each other exactly once. A straight-line arrangement in which no three lines meet is one of these. Number the lines by slope. For each triple $i < j < k$ there are only two possibilities for the order in which their three crossings occur from left to right, so an arrangement can be recorded as a plus or minus sign for each triple. Not all sign tables are valid. A table is one exactly when, on every four lines, the four triples read in order change sign at most once. These tables are the signotopes of Stefan Felsner and Helmut Weil, and they can be generated one by one by a straightforward backtracking search.

From the signs, the order of crossings along each line can be read directly. Three lines form a triangular region exactly when the two relevant crossings are neighbours on all three of the lines, since any other line entering the triangle would have to separate them on two sides.

The first column is a check: the counts 2, 8, 62, 908, 24,698 and 1,232,944 are the published numbers of such arrangements, from Donald Knuth’s book on the subject. So nothing was lost or double-counted. And the two right-hand answers are clean. The fewest triangles is exactly $n - 2$ at every size. The most is 1, 2, 5, 7, 11, then 14.

Fourteen. Not the fifteen of the tables. Since pseudolines include straight lines, no straight arrangement without a triple point can have more. A plain climb that adjusts straight lines at random also reaches 14 and stops. Is the census wrong, or are the tables, or is something else going on?

The fifteenth triangle #

The tables ask a slightly different question from the census. Fujimura’s problem says nothing about general position. Lines may pass through a common point. So a search was run that is allowed to do this deliberately, in which one of its moves puts a line through the crossing of two others, or through two such crossings, exactly. It found 15 in a fraction of a second.

The result has two triple points, at which one line passes through crossings of two pairs of other lines. All fifteen triangles were tested: none is entered by any other line, sampling 40,000 points finds no point in two of them, and the shortest side of any triangle is 0.0245, so that none is an artefact of rounding. Only the two intended points come anywhere near being triple. Then the coincidence was removed, by moving that one line by 0.01. The count fell to 14 when it moved one way and to 13 the other way.

So the answer to the question above is that neither is wrong. With triple points allowed, eight lines give 15; with none, they give 14. The bound’s argument assumed that a line has $n - 1$ distinct crossings, but it has room for this case. A triple point loses a bounded piece on each line going through it, but those lost pieces may be ones that would have been unused anyway, and a triangle that sits with a corner at a triple point does not need the third line to keep out of its way. Perturbing a triple point turns it into a tiny triangle, which seems as if it ought to add one. But the regions that touch the point at a corner are changed as well, and in this example the loss outweighs the gain.

It is not obvious from the literature how widely this distinction is recognised. Bartholdi, Blanc and Loisel’s paper deals explicitly with simple arrangements, and the claim here depends on a census, which may well be known to specialists in another form. It is stated here as a computed fact, with no claim of priority. What does seem clear is that eight is the first size where the distinction matters in this range, as the simple maxima at 3 to 7 equal the table’s values.

The floor, and the two-line count #

The bottom of the census is as tidy as the top. The fewest triangles among $n$ lines is $n - 2$.

Samuel Roberts proved this in 1889. It is another of those statements that is intuitively odd. However hard a set of lines tries to avoid forming triangles, it cannot: lines tangent to a convex curve come nearest to succeeding, and these still leave a chain of $n - 2$. The projective version has a cleaner explanation. In the projective plane, where parallels meet, the regions cut out by $n$ lines satisfy a relation from Euler’s formula: with $p_k$ the number of regions with $k$ sides,

$$\sum_k (4 - k)\, p_k = 4,$$

for a simple arrangement. Only triangles contribute positively, so there must be at least four, and this is the same count, in dual form, that Melchior used to force three ordinary lines. Friedrich Levi showed in 1926 that the true projective minimum is $n$, for every arrangement of pseudolines. The upper limit in the projective plane is $n(n - 1)/3$, as a double count of pieces gives, and arrangements meeting it are connected to very symmetrical configurations in which each piece borders a triangle. These can be found for infinitely many $n$, as Harborth, Roudneff, and Füredi and Palásti showed by different means, and the constructions have the same flavour as the rows of three planted on a cubic and the polygons with few ordinary lines.

Lines as points in disguise #

Everything here has a mirror image. The projective duality that turned points into lines sends an arrangement of lines to a set of points, a crossing to a line through two of the points, and a triple point to three points in a row. So a question about triple points in arrangements is the orchard problem in other words, and a line with exactly two points on it, Sylvester’s ordinary line, is a crossing of just two lines. Simple arrangements correspond to point sets with no three in a row, where every line is ordinary. Allowing a triple point means leaving that generic world, and the point sets that sit on as few lines as possible or that concentrate many points on one are the extreme versions of what a triple point begins. Seen this way, a triple point is not a small technical exception. It is the first step away from a generic configuration, and all the deep results of how often points can sit on lines concern what happens when many such coincidences are imposed at once. That the very first coincidences should buy an extra triangle is, in that light, less surprising.

How rare the rich arrangements are #

The average number of triangles is close to the floor. For eight lines, the mean is 8.59 against a floor of 6 and a top of 14, and the arrangements at the top are 480 of the 1,232,944, or 0.039%. Among seven lines, there are just 14 at the top, out of 24,698. Many of those are the same arrangement seen with its lines renumbered, or reflected, so the number of essentially different extremal arrangements is very small. So a search that makes random changes spends almost all its time among mediocre arrangements, and that is one reason why good solutions at larger $n$ were found by hand and with symmetry, not by a machine. Savchuk’s encoding of the problem for a SAT solver, in 2025, did manage to settle the 11-line case at the upper end, proving that no 33-triangle arrangement exists, although at that size only some of the structure of the problem is explored.

Note, too, that this distribution is by combinatorial type. Each arrangement counts once, whatever region of the space of lines it comes from, so that a random set of straight lines would give a different one, and some of the arrangements may not be drawable with straight lines at all. Those that cannot be drawn straight are called non-stretchable. Non-stretchable arrangements begin at nine lines, in a form that comes from Pappus’s theorem. Their existence is the reason the census could not be extended to prove straight-line results at larger $n$ without additional work: deciding whether a pseudoline arrangement can be straightened is as hard as the existential theory of the real numbers, by Nicolai Mnëv’s universality theorem. At eight and below, every pseudoline arrangement is stretchable, as Jacob Goodman and Richard Pollack showed. So this census is really a census of straight lines.

Against the search #

The climb, run for a few seconds at each size, matches the quoted values at nearly every small size: 1, 2, 5, 7, 11, then 14, 21, 25 and 32. The value at 9 lines is the most striking, since 21 meets the bound exactly with all 63 pieces used. It is attained again here by random search, which did not happen at eight. So nine lines’ full use of every piece is easier to find than eight lines’ near-full use. That is part of the same picture, in that the parity restriction stops 16 from occurring at eight, while 14 leaves six unused pieces and 15 only three. A value of 15 with no triple point would need to use all but three pieces, and it is what the census rules out.

The reach of the census #

The method has limits on both sides. Upward, the number of arrangements grows much faster than exponentially: the next value, for nine lines, is 112,018,190, which is possible but was not done here, and ten lines has 18 billion. Sideways, the census covers only simple arrangements. It says nothing about how many triple points could be used, how many arrangements have 15 triangles at eight lines, or whether a 15-triangle arrangement with one triple point exists. The search gave one with two. A proper count including triple points would require a table with three signs for each triple and more complicated rules, and that was not attempted.

The eight-line figure is not a good picture. The search was not asked for one, and several of the triangles are small on the scale of the drawing, which is why they are hard to see. Everything claimed about it comes from the coordinates rather than from looking at the image. And the claim that a triple point is what buys the extra triangle comes down to this one example together with the census. It does not explain in general how to use a triple point.

What was computed and what was quoted #

The arrangements were generated exactly from sign tables, counts matching the published ones up to 8 lines. Triangles were counted from the resulting orders of crossings, and the floor and ceiling at each size were read from the complete list. The straight-line climbs are seeded and give lower bounds. The eight-line arrangement was found by a search with exact crossing moves, then its coordinates were rounded to six places apart from one line constructed through the two crossings, so that its triple points are exact to rounding. Its 15 triangles and the absence of overlap were checked directly, and the perturbations were computed.

Quoted: the upper bound and its improvements, the theorems of Roberts, Levi, Goodman and Pollack, and Mnëv, the counts of arrangements from nine lines up, the Kobon values at larger sizes and Savchuk’s result. The explanation of how Clément and Bader’s parity argument works is an outline only.

Still open: how much can a coincidence buy #

Across all sizes, how much do triple points add to the maximum? The census shows a gain of one at $n = 8$. At sizes such as 10, 12 and 14, the quoted values may or may not use triple points. Nothing here says how large the gain may become, or at which sizes it appears, and nine lines’ census would answer one further case. There is also a question about the value at 11 lines, where 33 is excluded and 32 is known, and at 12, where 38 is known against a bound of 38. For $n = 18$, tables list 93 against a bound of 94.

Is the bound $\lfloor n(n-2)/3 \rfloor$ met for every $n$ congruent to 3 or 5 modulo 6? It has been met for many of those, up to 33 and beyond, by symmetric constructions and SAT-assisted searches. It is not known in general, even though it is widely expected. In the projective plane, the analogous question has a more complete answer, since infinitely many extremal arrangements are known. Why the affine and projective cases should differ so much is not well understood.

One line through two crossings #

A count of pieces caps $n$ lines at $\lfloor n(n - 2)/3 \rfloor$ triangles, Euler’s formula forces at least $n - 2$, and a complete list of simple arrangements finds both ends exactly, up to eight lines. The list stops at 14 for eight lines, one short of the known 15.

That missing triangle comes from an exact coincidence: three lines through one point, twice. Moving one line by a hundredth loses it. So a table of values that looks like one sequence is really two, and they first part at eight. It is a small thing. But a question that seemed to have been finished by hand and by symmetry still holds something that only a complete list could reveal.