Fabian Arevalo

Research note · Discrete geometry

18 pseudolines, 93 triangles: a rediscovery, and an audit of the upper bounds

A cube-and-conquer SAT campaign confirms that no simple arrangement of 18 pseudolines has 94 triangles. Blanc proved this in 2008, which the session discovered mid-run, so the computation is an independent machine check rather than a new theorem. The genuinely new part is a flagged audit of the Kobon upper-bound column.
September 2, 2026 · produced in a Claude Code research session (AI-assisted, disclosed) · code, data & cube records in the companion repository.

Start here: no maths required

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.

Target t 94
The whole counting argument, evaluated live rather than quoted. For 18 pseudolines and a target of t triangles, the two shaded regions are the constraints on m, the number of perfect lines. From below, using every triangle’s three private edges: m ≥ 3t − 270. From above, because each perfect line forces a wasted edge and each wasted edge can serve at most two perfect lines: m ≤ 2(288 − 3t). Below t = 94 the two leave a wide corridor and the search space is hopeless, which is exactly what Bartholdi, Blanc and Loisel reported. At t = 94 they meet at the single value m = 12, which is the rigidity that makes the machine search finish. At t = 95 they cross, so no arrangement exists at all: that crossing is a proof of the classical bound, visible in one drag of the slider.

What this note adds

  1. A machine-checked confirmation that 94 is impossible, by a method unrelated to the published proof. 561 cases, all impossible, each with a formal proof file checked by an independent proof checker: 5.0 core-hours to solve, 8.2 more to verify. This is a rediscovery. Blanc proved the same statement in 2008 by counting. The value here is that a general-purpose pipeline, validated against every value in the published table up to 16 lines, reaches the same answer from a completely different direction.
  2. The rigidity that made it possible, proved. Any 94-triangle arrangement of 18 pseudolines has exactly twelve perfect lines and exactly six lines wasting exactly one edge each. That is the figure above, and it is what turns an intractable search into 561 quick ones.
  3. An audit of the numbers in circulation, flagged and not settled. The upper bounds quoted for the Kobon problem at even numbers of lines are theorems about arrangements in general position. But the Kobon problem allows three lines through a point, and the record-holding arrangements at 8, 12 and 14 lines do exactly that: each beats the general-position maximum by one. So applying that bound to them is not valid. On the literature as cited, the honest brackets are 54 ≤ K(14) ≤ 55 and 93 ≤ K(18) ≤ 95, not the exact 54 and the upper bound 94 that the catalogues record.

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.

AbstractSummary of results

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.

Prior work, found mid-session

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.

Section 1The problem

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.

Section 2Signotopes, triangles and segments

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.

Lemma 2.2 · order along a line · PROVED

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.

Section 3The tight structure at n = 18

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.

Lemma 3.1 · BBL association lemma, even n · PROVED

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.

Proposition 3.2 (T1) · PROVED

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. □

Proposition 3.3 (T2) · PROVED

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.

Section 4Cube and conquer

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.

Theorem 4.1 · CERTIFIED · an instance of Blanc’s Theorem 1

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.

Show
The whole campaign, one marker per case, read from the committed cube record. The 18,564 ways to choose which six lines are imperfect collapse under the symmetry into 561 classes, and each was refuted separately. Sorted solve times on a log scale: the median cube takes 18 seconds and the hardest 585, a spread of a factor of 300 across cases that differ only in which six labels were chosen. Verification is the more expensive half, 8.2 core-hours against 5.0 for solving, which is the usual price of a checkable proof. The orbit-size view is the arithmetic check that the case split is complete: sizes 3, 6, 9, 18 and 36 occur, and the sizes sum to exactly 18,564, so every six-subset is covered exactly once. That sum is recomputed in your browser from the 561 committed orbit sizes rather than quoted.

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.

Section 5Controls

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.

nas3(n) [BBL]SAT at the valueUNSAT at value + 1
8140.2 s0.2 s
9210.1 sodd; bound n(n−2)/3
10251.2 s1.8 s
11322.5 s0.7 s
12371.7 s392 s
13471.9 s—
1453150 snot finished in 40 min
156521 s—
1672236 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.

Section 6An audit of the upper-bound column

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.

Hover or tap a column for the exact numbers at that n.
Everything measured against the simple-arrangement maximum, so that gaps of one or two are visible at all. The horizontal zero line is as3(n), the most triangles achievable in general position, which is a theorem for every n shown. Above it: the BBL floor bound that the catalogues quote, and the Clément–Bader general-configuration bound where their formula applies. The filled circles are the best arrangements known. Read the three columns at n = 8, 12 and 14: the record sits one above the zero line, so those arrangements are provably not in general position, and the bound being quoted for them is a general-position theorem. At n = 18 the record is still on the zero line, which is what this session confirmed; the honest bracket there runs up to the Clément–Bader value, not to the quoted one. All values are computed from the published formulas in your browser; the records are the ones this note’s sources state, and n = 10 and 16 carry no record marker because the sources consulted here did not state one.

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.

Section 7What failed

Section 8Open questions

  1. Is the even-n bound true for non-simple arrangements? The audit of section 6 either has an answer in the literature that we failed to find, or it does not, in which case proving the bound for configurations with multiple points, or exhibiting a 55-triangle arrangement of 14 lines with triple points, is the real open problem here.
  2. Report the audit upstream. The OEIS A006066 upper-bound column and the exactness claim at a(14) both deserve a note, after a second reading of Clément–Bader’s Lemma 1. That is a decision for the publishing step, per the repository’s policy on external submissions.
  3. A lemma-free certificate. The 955 plain cubes were generated and not run. Running them would remove the dependence on Lemma 3.1 and leave a refutation resting only on the signotope axioms.
  4. Blanc’s own conjecture. The signotope toolkit is validated end to end and the nearest genuinely open simple-arrangement question it could attack is Blanc’s Conjecture 1.0.1 for projective arrangements at n = 32, whether ps3(32) = 329.