Discrete geometry · a partial result
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.
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.
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.
| Result | Label | Scope and caveat |
|---|---|---|
| Forced line type t5 = 2, t3 = 26, t2 = 7 (Cor 5.3) | Proved | Melchior + pair counting |
| Even ordinary-line degree at every point (Lemma 5.6) | Proved | Parity |
| Disjoint 5-point lines impossible (Thm 6.1) | Certified | 261 sub-cubes, all UNSAT, all drat-trim VERIFIED |
| Meeting, no ordinary cross pair, impossible (Thm 6.2) | Certified | 411 arrays, all UNSAT, all VERIFIED |
| s ≥ 6 impossible; machine control on 83 classes | Proved + Certified control | Parity proof; 83 UNSAT as a check of it |
| t2(20) = 10, t2(24) = 12 | Proved | From Csima–Sawyer + Böröczky, both secondary |
| t2(15) ≥ 8 | Not established. Equivalent to the unsatisfiability of the 45 open classes. | |
| t2(15) | Unknown, still in {7, 8, 9}. | |
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.
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.
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:
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.
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:
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.
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-cubes | solve s | max solve s | verify s | proofs GB |
|---|---|---|---|---|---|
| 0 (Latin squares) | 2 | 3 | 2 | 4 | 0.06 |
| 1 | 1 | 63 | 63 | 24 | 0.11 |
| 2 | 3 | 118 | 72 | 56 | 0.23 |
| 3 | 6 | 169 | 156 | 155 | 0.33 |
| 4 | 16 | 888 | 540 | 837 | 1.04 |
| 5 | 34 | 882 | 245 | 858 | 1.36 |
| 6 | 69 | 140 | 4 | 234 | 1.43 |
| 7 (void by Lemma 5.6) | 130 | 209 | 4 | 312 | 1.71 |
| total | 261 | 2,472 | 540 | 2,480 | 6.3 |
Every one UNSAT, every proof drat-trim-verified. About 55 minutes wall on two cores.
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.
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.
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.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.
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:
| Script | What it does |
|---|---|
distributions.py 15 7 | The surviving line-type distributions; one at n = 15, m = 7 |
cubes.py 15 7 | The two cubes: 5-point lines disjoint (B) or meeting (A) |
subcubes.py B 7 | The 261 sub-cubes of Theorem 6.1, with CNF generation |
fillcubes.py | Fill mode: all arrays of a star-class, incremental solving |
chiro_sat.py, ordlines_sat.py | The chirotope encoding Φ(n,m) |
verify_chirotope.py | Independent checker for a satisfying assignment |
poscontrol.py | The explicit rational positive control |
certs/*.jsonl | The 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.