Research note · Discrete geometry
Draw some straight lines across a page, no two parallel, and never three of them through the same point. The lines cut the page into regions, and some of those regions are triangles. How many triangles can you force, if you place the lines as cleverly as possible?
This is Kobon Fujimura’s problem, and it is unreasonably hard. With ten lines you can get 25 triangles, and nobody has ever done better. With eighteen the record has stood at 93 for years, and the question of whether 94 is possible has been in the tables since 2007, marked as undecided.
There is a clean counting argument that stops you going too far. Each line is chopped into pieces by the others, eighteen lines give 288 usable pieces in all, and every triangle needs three of them, all to itself. So 94 triangles would consume 282 pieces and leave just 6 spare. That sounds like plenty of room, but a second argument says each “perfect” line, one with no pieces wasted, forces a wasted piece somewhere else, and those two facts fight each other. Drag the target in the figure and watch them close in.
At exactly 94 they close so tightly that the arrangement would have to have a very specific shape: precisely twelve perfect lines and precisely six with exactly one piece wasted each. That rigidity is what makes the question answerable by machine, because there are only 18,564 ways to choose which six lines are the wasteful ones, and symmetry cuts that to 561 genuinely different cases. All 561 were checked, and all 561 are impossible. So 94 cannot happen and the answer is 93.
Except that this was already known. Partway through the session, reading the reference list of a recent paper, the author found that Jeremy Blanc proved it in 2008 by a short counting argument, published in a journal the tables did not cite. So what is above is an independent confirmation of a known theorem by an unrelated method, which is worth something but is not a discovery, and it is labelled that way throughout. The part of this note that is not a rediscovery is in section 6, and it is a problem with the numbers everyone is quoting.
Everything below is the technical version. If you read one section, read section 6: it is the only part that is not a confirmation of something already known.
For a simple arrangement of n pseudolines in the Euclidean plane let as3(n) be the maximum number of bounded triangular faces. Bartholdi, Blanc and Loisel (2008) proved as3(n) ≤ ⌊n(n − 7/3)/3⌋ for even n and tabulated as3(n) for n ≤ 30; the first entry their computation could not close is n = 18, where they report 93 ≤ as3(18) ≤ 94. We encode simple Euclidean pseudoline arrangements as rank-3 signotopes (Felsner–Weil), express the triangle count through the n(n−2) bounded segments, derive from BBL’s own counting that a 94-triangle arrangement of 18 pseudolines would have exactly twelve perfect lines and six lines carrying exactly one unused segment each, and decide the resulting instance by cube-and-conquer over the 561 dihedral orbits of the six-line set. All 561 cubes are UNSAT and all 561 DRAT proofs are drat-trim-verified.
The entry is not open. Blanc (arXiv:0801.2845, Geombinatorics 21 (2011) 5–17), Theorem 1, proves a3(A) ≤ n(n − 5/2)/3 for n ≡ 0, 4 (mod 6), which is 93 at n = 18, and his Theorem 3 states that this bound is reached for every n ≤ 30 except 11 and 12. So as3(18) = 93 has been a theorem since 2008, and the computation reported here is an independent, machine-checked rediscovery of one instance of it by an unrelated method. What remains open at n = 18 is the Kobon number for arrangements with concurrent triples or parallels; section 6 records what the literature actually proves about that.
Kobon Fujimura’s triangle problem asks for the largest number K(n) of non-overlapping triangles formed by n straight lines in the plane (OEIS A006066); the triangles in question are the bounded triangular faces of the arrangement. Two relaxations are standard: allow pseudolines instead of lines, and restrict to simple arrangements, meaning no three lines concurrent and all pairs crossing. Bartholdi, Blanc and Loisel write as3(n) for the simple pseudoline maximum in the affine plane and prove that as3(n) ≤ ⌊n(n − 7/3)/3⌋ for even n.
Their Theorem 1.4 tabulates as3(n) for n ≤ 30, exact for n ≤ 17 and for odd n ≤ 29, with two-value entries where their depth-first search could not finish: 93–94 at n = 18, 116–117 at n = 20, 143–144 at n = 22. They say explicitly that as the unused edge budget increases, the search quickly becomes intractable when looking for imperfect arrangements. At n = 18 the bound is exactly 94, an integer, so 94 triangles would use 282 of the 288 bounded segments and leave an unused edge budget of six. That entry has stood since the 2007 preprint.
Scope. We work with simple arrangements of pseudolines. Every simple arrangement of straight lines is one, so a negative answer for pseudolines is a negative answer for lines in general position. It says nothing about arrangements with concurrent triples or parallel lines, which the Kobon problem allows. That distinction is the whole subject of section 6.
Label the pseudolines 1, …, n by their vertical order at x = −∞. A 3-signotope on [n] is a map σ from 3-subsets {i<j<k} to {+, −} such that for every 4-subset a<b<c<d the sequence σ(abc), σ(abd), σ(acd), σ(bcd) changes sign at most once. By Felsner and Weil, marked simple arrangements of n pseudolines in the Euclidean plane are in bijection with 3-signotopes on [n], the sign σ(ijk) recording the orientation of the triangle formed by lines i, j, k. We fix σ(ijk) = + iff line j passes above the crossing point of lines i and k.
For a line r and two other lines a < b, line a crosses r before b, left to right, iff σ(sorted{r,a,b}) = −.
The proof splits on which of the three sorted labels is r and reads off the vertical order at the crossing in each case; in all three the smaller-labelled line comes first exactly when σ = −. The consequence is that the local sequence of each line, the order of its n − 1 crossings, is a function of σ, and the signotope axiom is exactly what makes these orders mutually consistent. As a control, enumerating the models of the axiom clauses gives 8, 62, 908, 24698 signotopes for n = 4, 5, 6, 7, matching OEIS A006245, and a greedy left-to-right sweep realises every one of them as a wiring diagram.
Each line carries n − 1 crossings and hence n − 2 bounded segments, so there are n(n − 2) bounded segments in all. Lines i < j < k bound a triangular face iff the crossings with j and k are adjacent along i, those with i and k adjacent along j, and those with i and j adjacent along k. Every triangle therefore consumes three segments, and no segment can serve two triangles, which is the accounting the next section runs on.
Call a line perfect if all its n − 2 segments are used by triangles. BBL’s bound rests on the following, which we restate and reprove because the certificate depends on it.
Let L be a perfect line of a simple arrangement of an even number n of pseudolines, and let M, N be the lines through the first and last crossing of L. Then one of the two segments of M starting at M∩L, or one of the two segments of N starting at N∩L, is unused.
Proof, after BBL. The n − 2 triangles along L lie alternately inside and outside the region Δ bounded by L, M, N; as n − 2 is even, the first and last lie on opposite sides, so one of them, say the last, is outside Δ. Its side on N is one of the two segments of N at N∩L. The other segment s of N at N∩L points into Δ; a triangle with side s would have a side on L starting at L∩N, which can only be the last bounded segment of L, already the side of the last triangle and of no other. So s is unused. □
The parity is essential, and this is checked rather than assumed: for odd n the lemma fails, and the checker finds violations exactly there, 406 among the 2,520 perfect-line instances of the 24,698 arrangements with n = 7, and none among all 908 arrangements with n = 6, 30,000 arrangements with n = 8, or the extremal arrangements found by SAT for n = 8, 10, 12, 14.
An unused segment with endpoints N∩L and N∩X can be associated in this way only to L or to X, so to at most two perfect lines. With m perfect lines this gives #unused ≥ m/2, while #used ≤ m(n−2) + (n−m)(n−3) = n(n−3) + m. Those two inequalities are the entire proof of the classical bound, and at n = 18 they are what the figure at the top of this page plots.
A simple arrangement of 18 pseudolines with 94 triangular faces has exactly 12 perfect lines, and each of the other 6 lines has exactly one unused segment.
Proof. #used = 282 and #unused = 6. From 282 ≤ 270 + m we get m ≥ 12; from 6 ≥ m/2 we get m ≤ 12. The 6 imperfect lines carry the 6 unused segments, at least one each, hence exactly one each. □
In such an arrangement every unused segment lies on an imperfect line N, and both lines L, X through its endpoints are perfect, with N∩L the first or last crossing along L and N∩X the first or last crossing along X.
Proof. The association of Lemma 3.1 maps the 12 perfect lines injectively into the 12 endpoint slots of the 6 unused segments, each slot being the image only of the other line through it. So it is a bijection: every endpoint of every unused segment is the extreme crossing of a perfect line. The carrying line is imperfect because it carries an unused segment. □
Both propositions use nothing beyond Lemma 3.1 and counting. They are consequences, so adding them as clauses to a search for a 94-triangle arrangement is sound: any such arrangement satisfies them. That soundness direction is the only one that matters, and it is why the certificate is a valid refutation rather than a refutation of a restricted problem.
By Proposition 3.2 the set S of imperfect lines is a 6-subset of [18]. The signotope model carries a dihedral symmetry of order 4n: shifting the sweep direction relabels the lines cyclically with a sign rule, and reflection in a horizontal axis reverses the order and flips every orientation. Its action on the labels is the dihedral group of the 18-cycle, so we may replace the arrangement by its image under the group element sending S to the lexicographically least member of its orbit, and by a further global flip assume σ(123) = −.
There are 561 orbits, covering all C(18,6) = 18,564 subsets. This count was obtained twice, by enumerating canonical forms and independently by Burnside’s lemma for D18 acting on 6-subsets of the 18-cycle, and the label action of the signotope maps was checked to coincide with D18.
No simple arrangement of 18 pseudolines in the Euclidean plane has 94 bounded triangular faces; with Bader’s straight-line arrangement, as3(18) = 93.
Certificate. All 561 cubes are UNSAT (kissat 4.0.4, one core each; 5.0 core-hours in total, median 18 s, hardest cube #503 at 585 s), and all 561 DRAT proofs were checked by drat-trim (8.2 core-hours). The proofs total 27.75 GB and were deleted after verification; the SHA-256 and size of every proof are listed with its cube in data/cubes_T2.csv, and each is regenerable by cubes.py. This means the repository holds the hash manifest and the verification verdicts, not the proofs themselves, which is a weaker artifact than a downloadable proof and is stated as such.
The lemma-free cube variant, 955 orbit representatives with no structural lemma assumed, was generated but not run; the plain n = 18 instance with no structural lemma at all was not finished. So the certificate depends on Lemma 3.1 through Propositions 3.2 and 3.3. Those are published and reproved here and checked computationally on all even-n cases available, but a reader who wants a certificate resting on nothing but the signotope axioms does not have one.
The pipeline was validated against every value of BBL’s Theorem 1.4 that this hardware could reach, with every SAT model decoded and its triangle count recomputed twice, once by the adjacency test and once by counting three-sided faces of the sweep.
| n | as3(n) [BBL] | SAT at the value | UNSAT at value + 1 |
|---|---|---|---|
| 8 | 14 | 0.2 s | 0.2 s |
| 9 | 21 | 0.1 s | odd; bound n(n−2)/3 |
| 10 | 25 | 1.2 s | 1.8 s |
| 11 | 32 | 2.5 s | 0.7 s |
| 12 | 37 | 1.7 s | 392 s |
| 13 | 47 | 1.9 s | — |
| 14 | 53 | 150 s | not finished in 40 min |
| 15 | 65 | 21 s | — |
| 16 | 72 | 236 s | — |
The n = 12, t = 38 and n = 14, t = 54 instances are the closest analogues of n = 18, t = 94, each with an unused budget of six, but they are not tight: at n = 12 the counting only gives 6 ≤ m ≤ 12, a corridor rather than a point. That is precisely why the plain instance grows hard while the tight cubes at n = 18 finish in seconds, and it is the reason the n = 18 case turned out to be easier than the smaller ones that surround it.
This section is the part of the note that is not a rediscovery. It is flagged, not settled: it reports a mismatch between what the cited theorems prove and what the catalogues record, and does not claim to resolve it.
The Kobon problem allows three lines through a point. The bounds in circulation do not.
We have not found a proof of the even-n bound for non-simple arrangements, and we have not tried to produce one. Either that proof exists and the column is right for a reason not recorded in the cited sources, or it does not and two entries need widening. Establishing which is the natural next step, and it is a literature question before it is a mathematical one.