Fabian Arevalo

Discrete geometry · a partial result

Fifteen points and seven ordinary lines: most of the case tree, closed

A SAT attack on the smallest open case of the Dirac–Motzkin conjecture. t2(15) is still unknown. What is settled: if fifteen points span only seven ordinary lines, their two five-point lines must meet, and between one and five of the sixteen pairs joining them are ordinary. 895 refutations, every proof checked.
September 5, 2026 · session of the Matematica research log · code, ledgers and certificates in conjectures/ordinary-lines/

Start here — no maths required

Put some dots on a page, not all in a row, and draw every straight line that passes through at least two of them. A line through exactly two dots is called ordinary. It is a surprisingly old and hard question how few ordinary lines you can get away with.

You can always get at least one, which took until 1944 to prove. The Dirac–Motzkin conjecture says that with n dots you can never do better than n/2 ordinary lines, once n is at least 14. Green and Tao proved it for all large n, but "large" in their proof is astronomically large, and the exact answers are recorded only up to fourteen dots, plus 16, 18 and 22.

Fifteen dots is the smallest case nobody knows. The answer is somewhere between 7 and 9, and this note does not close it. What it does is cut the search down. If fifteen dots really managed only seven ordinary lines, the arrangement would be forced into a very particular shape, and most of the ways that shape could be realised have now been ruled out by a solver, with every refutation independently proof-checked. The tree below is what got closed and what did not.

The whole case tree, and the one branch still standing. Reading down: a fifteen-point set with exactly seven ordinary lines is forced by counting to have two five-point lines and twenty-six three-point lines, nothing else. Those two lines are either disjoint or they meet. The disjoint branch is entirely closed. In the meeting branch, s counts how many of the sixteen pairs joining the two lines span an ordinary line; s = 0 is closed, s ≥ 6 is impossible by a parity argument that was also machine-checked, and two more classes were closed by brute force. Forty-five classes remain. Every number in the readout is summed in your browser from the committed ledgers of solver verdicts. The filled boxes are closed with drat-trim-checked proofs; the hollow one is open, and it is why this page does not claim t2(15) ≥ 8.

What this note adds, and what it does not

  1. The two five-point lines cannot be disjoint. 261 sub-cases, every one refuted, every refutation's proof checked by an independent proof checker. About 41 minutes of solving and 41 of checking, 6.3 gigabytes of proof.
  2. If they meet, at least one of the sixteen joining pairs must be ordinary, and at most five can be. The first half is 411 more refuted cases; the second is a parity argument, proved by hand and then machine-checked on its 83 cases as a control.
  3. The shape is pinned down. Any such configuration has exactly two five-point lines, twenty-six three-point lines, seven ordinary ones, and every point lies on an even number of ordinary lines.
  4. The remaining work is measured, not guessed. The 45 open classes hold 151,309 arrays, and the measured cost is about 25 processor-hours. That is a specific, finite computation someone can now run.
  5. A bookkeeping correction. The value at n = 20 printed as "?" in the sequence entry's comment is not open: t2(20) = 10 and t2(24) = 12 both follow from results already in the literature.

What this is not. It is not a proof of t2(15) ≥ 8, and the interval 7 ≤ t2(15) ≤ 9 is unchanged. Anyone reading this as a solved case is reading it wrong.

AbstractSummary of results

For a set P of n points in the real projective plane, not all collinear, let t2(P) be the number of ordinary lines and t2(n) the minimum over all such P. The Dirac–Motzkin conjecture asserts t2(n) ≥ n/2 for n ≥ 14; Green and Tao proved it for all n ≥ n0 with n0 unspecified and "of double exponential type", and exact values are recorded only for n ≤ 14 and n = 16, 18, 22 (OEIS A003034). We attack n = 15, where 7 ≤ t2(15) ≤ 9 was all that was known.

Melchior's inequality and pair counting force a 15-point set with exactly 7 ordinary lines to have exactly two 5-point lines and twenty-six 3-point lines (Corollary 5.3). We encode "rank-3 chirotope on 15 elements, collinear triples allowed, at most 7 two-element lines" as a SAT instance whose axioms are only necessary conditions satisfied by every real configuration and every rank-3 oriented matroid, and refute it where the two 5-point lines are disjoint (261 sub-cubes, Theorem 6.1) and in the star-free sub-case where they meet (411 arrays, Theorem 6.2), with DRAT proofs checked by drat-trim throughout. Parity disposes of 83 of the remaining 130 sub-cases. The meeting case with 1 ≤ s ≤ 5 ordinary cross pairs, 45 classes and about 151,000 arrays, is not finished, so t2(15) ≥ 8 is not established here. What is established is Corollary 6.4: any 15-point configuration with 7 ordinary lines, real or pseudo, has its two 5-point lines meeting, with between one and five ordinary lines among the pairs joining them, and every point on an even number of ordinary lines.

ResultLabelScope and caveat
Forced line type t5 = 2, t3 = 26, t2 = 7 (Cor 5.3)ProvedMelchior + pair counting
Even ordinary-line degree at every point (Lemma 5.6)ProvedParity
Disjoint 5-point lines impossible (Thm 6.1)Certified261 sub-cubes, all UNSAT, all drat-trim VERIFIED
Meeting, no ordinary cross pair, impossible (Thm 6.2)Certified411 arrays, all UNSAT, all VERIFIED
s ≥ 6 impossible; machine control on 83 classesProved + Certified controlParity proof; 83 UNSAT as a check of it
t2(20) = 10, t2(24) = 12ProvedFrom Csima–Sawyer + Böröczky, both secondary
t2(15) ≥ 8Not established. Equivalent to the unsatisfiability of the 45 open classes.
t2(15)Unknown, still in {7, 8, 9}.

Section 1Background, and one correction

The Sylvester–Gallai theorem is t2(n) ≥ 1; Melchior's argument gives t2(n) ≥ 3; Kelly–Moser (1958) proved t2(n) ≥ 3n/7 and Csima–Sawyer (1993) t2(n) ≥ 6n/13 for n > 7. Both of those are quoted from Green and Tao's introduction; the original papers are paywalled and were not read (secondary.) The upper bound t2(15) ≤ 9 is the Böröczky-type example of Green–Tao Proposition 2.1(iii).

Green and Tao also remark that the conjecture might hold for all n with only two exceptions, 7 and 13, in which case n0 could be taken as low as 14. That is the reason n = 15 is worth a session: it is the first case where nobody knows.

A correction to the A003034 comment

The sequence entry's comment quotes a table with "?" at n = 20. But Csima–Sawyer gives t2(20) ≥ ⌊120/13⌋ = 10 and the Böröczky construction gives t2(20) ≤ 10, so t2(20) = 10; the same argument gives t2(24) = 12. This is a transcription gap in the quoted table, not new mathematics, and it inherits the secondary sourcing of both ingredients.

Section 2The encoding, and why unsatisfiability is enough

The combinatorial abstraction is a rank-3 chirotope on 15 elements with collinear triples allowed. The SAT instance asserts only conditions that every real point configuration and every rank-3 oriented matroid satisfies. That direction is the one that matters:

Lemma 3.1 — soundness

If some set of n points, not all collinear, spans at most m ordinary lines, then Φ(n,m) is satisfiable. Hence Φ(n,m) UNSAT implies t2(n) > m.

There is no completeness theorem in the other direction, and none is needed: a satisfying assignment would prove nothing, and every result on this page is an unsatisfiability result. The same encoding covers pseudoline arrangements, using Melchior's inequality for pseudolines (Bokowski–Pokora, abstract read only) and the topological representation theorem (Björner et al., not consulted) — both secondary.

Every instance carries 91,791 variables and about 655,500 clauses before the precedence clauses. All solving used Kissat 4.0.4 with DRAT logging; all checking used drat-trim in backward mode. Proof files were checked and then deleted; the certificate is the ledger, which records for each instance the SHA-256 of its CNF, the verdict, the proof size and the checker's answer, together with the deterministic generators that rebuild any CNF byte for byte.

Section 3The case split

Pair counting gives Σk≥2 C(k,2) tk(P) = C(n,2); Melchior's inequality gives t2(P) ≥ 3 + Σk≥4 (k−3) tk(P). Together, at n = 15 with t2 = 7:

t5 = 2,   t4 = 0,   t3 = 26,   t2 = 7
Corollary 5.3 — the only surviving line-type distribution

Let L1, L2 be the two 5-point lines and F the free points. Lemma 5.5 turns the configuration into an array φ indexed by L1 × L2: each cross pair either spans an ordinary line, marked with a star, or passes through exactly one free point, whose name fills the cell. So the free points fill a partial Latin square, and the case tree is over the star patterns. Lemma 5.6 constrains the type vectors, which is where the parity argument lives.

Section 4What is closed

Theorem 6.1 · CERTIFIED

No set of 15 points in RP², not all collinear, spans exactly 7 ordinary lines with its two 5-point lines disjoint. The same holds for rank-3 oriented matroids.

s (star entries)sub-cubessolve smax solve sverify sproofs GB
0 (Latin squares)23240.06
116363240.11
2311872560.23
361691561550.33
4168885408371.04
5348822458581.36
66914042341.43
7 (void by Lemma 5.6)13020943121.71
total2612,4725402,4806.3

Every one UNSAT, every proof drat-trim-verified. About 55 minutes wall on two cores.

Theorem 6.2 · CERTIFIED

No set of 15 points, and no rank-3 oriented matroid, spans exactly 7 ordinary lines with its two 5-point lines meeting at a point q and no ordinary line among the 16 pairs (a,b), a ∈ L1∖{q}, b ∈ L2∖{q}.

All 411 fillings, every one UNSAT with a verified proof: 1,212 s solving (median 1.9 s, maximum 14.5 s), 1,384 s checking, 13.1 GB of proofs, 45 minutes on one core.

Proposition 6.3

In the meeting case the number s of ordinary cross pairs satisfies 1 ≤ s ≤ 5: s = 0 by Theorem 6.2, s ≥ 6 by the parity argument of Lemma 5.6. Proved. As a control, all 83 star-classes with s ≥ 6 were run anyway: all UNSAT with verified proofs, 134 s solving, 258 s checking. Certified control.

Where the difficulty lives. Each dot is one of the 261 sub-cubes of Theorem 6.1: horizontally its number s of ordinary cross pairs, vertically the solver's time on a logarithmic scale. Measurement, read from certs/ledger_B_m7.jsonl; the per-s medians drawn through them are computed in your browser from the same points. The pattern is worth a sentence, because it is the reason the open branch is the one it is. Difficulty is concentrated at small and middling s: the median is 63 s at s = 1 and 44 s at s = 2, the single slowest instance (540 s) sits at s = 4, and from s = 6 upward every instance falls in about a second and a half, because those classes are parity-void and the solver sees it immediately. The branch left open in the meeting case is exactly the expensive range, 1 ≤ s ≤ 5.

Section 5What is open, and exactly how much of it

Corollary 6.4

If a set of 15 points in RP² spans only 7 ordinary lines, then its line type is t5 = 2, t3 = 26, t2 = 7; its two 5-point lines meet; between one and five of the sixteen pairs joining them span ordinary lines; and every point lies on an even number of ordinary lines. The Dirac–Motzkin bound t2(15) ≥ 8 is equivalent to the unsatisfiability of the 45 remaining star-classes.

Those 45 classes hold 151,309 fillings. Sub-cube instances for them do not finish: the s = 1 sub-cube ran 20 minutes on Kissat and 10 on CaDiCaL with no verdict; with the type-vector refinement the first instance of that class took 14 seconds and the second ran 10 minutes without one; fixing four cells of one free point still leaves a 300-second timeout. Fully fixed arrays, on the other hand, are refuted quickly, median 0.04 to 0.3 s in an incremental CaDiCaL session, with a heavy tail up to 20 s concentrated on arrays whose six free points carry 3, 3, 3, 2, 2, 2 mixed lines. That puts the whole remaining case at roughly 25 processor-hours, outside this session's budget but well inside somebody's.

Two of the 47 open classes were closed on the way, indices 11 and 22, 70 fillings each, all UNSAT with verified proofs. That is the difference between 47 and 45.

Section 6Calibration, and what did not work

The pipeline reproduces the known values it was pointed at. Highlights from certs/calibration_n9_12.log: n = 9, m = 5 refuted instantly; n = 9, m = 6 gives 4 satisfiable and 2 unsatisfiable cubes; n = 12, m = 5 refuted in 18.5 s; n = 11, m = 6 gives one satisfiable and two unsatisfiable cubes, the harder taking 58.6 s. A positive control on an explicit rational configuration with two 5-point lines is also in the directory.

What did not work, recorded because it is the useful part:

Section 7Reproducing this

ScriptWhat it does
distributions.py 15 7The surviving line-type distributions; one at n = 15, m = 7
cubes.py 15 7The two cubes: 5-point lines disjoint (B) or meeting (A)
subcubes.py B 7The 261 sub-cubes of Theorem 6.1, with CNF generation
fillcubes.pyFill mode: all arrays of a star-class, incremental solving
chiro_sat.py, ordlines_sat.pyThe chirotope encoding Φ(n,m)
verify_chirotope.pyIndependent checker for a satisfying assignment
poscontrol.pyThe explicit rational positive control
certs/*.jsonlThe certificate: per-instance CNF hash, verdict, proof size, checker answer

Run from inside conjectures/ordinary-lines/. Solver: Kissat 4.0.4; checker: drat-trim, backward mode. One solver per instance: the independent confirmation is the proof checker, not a second solver.