Few lines through every point
- Kind
- Theorem, an explicit construction with a proof
- Status
- Proved and verified in Lean 4; also checked line by line by a reviewer agent; unrefereed
- Prior work
- Not found in the searches logged; the open case of Akiyama, Ito, Kobayashi and Nakamura (2011); the grid is Felsner's arrangement
On this page
The statement
Put points in the plane, not all on one line, and draw the line through every two of them. For a point , let be the number of these connecting lines through . Dirac (1951) guessed that some point always lies on at least about of them.
Akiyama, Ito, Kobayashi and Nakamura (2011) asked, for every , for points, not all on one line, with every point on at most connecting lines. They settled every except with (). Their abstract:
"In this paper, we settle the problem for every integer n except n = 12k + 11 (k >= 4). The latter case remains open."
Theorem. For every even , the set of points of the projective plane
- and for every whole number from to except , and ;
- for every from to except and ;
- , , and
is not all on one line, and every point lies on at most of its connecting lines. As runs over , runs over : every with . A projective map sending a line that misses to infinity moves the set into the ordinary plane and keeps every count.
Check it yourself
- The count of points. .
- The set in the ordinary plane. The line misses for every , so with gives the points , , , , , and : points on three lines through one point, plus three more.
- One point by hand, , . Under duality the point is the line , and the lines through the point are the crossing points on that line. It meets the lines at heights and the lines at ; the three medians add nothing. That is 16 heights, plus one crossing at infinity: .
- The whole of . The number of points on each count of lines: 1 point on 6, 3 on 12, 7 on 14, 4 on 15, 16 on 16 and 4 on 17. None is on more than 17.
Worked examples
The recipe is a grid with eight lines taken out. Under duality, becomes a set of lines: the lines and ( from to , except , , ) and (except , ); the three medians , and ; and the line at infinity. The grid with its medians and the line at infinity is Felsner's arrangement ; the recipe removes eight of its lines. At that leaves 31 grid lines, 3 medians and the line at infinity: 35 lines, one for each point.
Why "even ". Exact counts of for to :
| 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 23 | 29 | 35 | 41 | 47 | 53 | 59 | 65 | 71 | 77 | 83 | |
| largest | 12 | 16 | 17 | 22 | 23 | 28 | 29 | 34 | 35 | 40 | 41 |
| 11 | 14 | 17 | 20 | 23 | 26 | 29 | 32 | 35 | 38 | 41 |
Every even from 6 to 14 holds, with the largest reached at exactly four points; fails by one, and every odd fails.
Why it holds for every . The proof counts crossing points on each kind of line. On a line the crossing heights are whole numbers in a range of values, plus possibly one half-integer from a median, and each whole number that no other line hits takes one off. For the range is already small enough; for the lines nearest the edge, the eight removed lines make exactly enough heights go missing. The heaviest lines are and , with exactly .
Status and who checked it
- Proved and verified in Lean 4: for every even by a written
proof and inside Lean 4 (
lean/StrongDirac/, 198 pure-kernel declarations, closing every modulo 12 and exact tightness at ). A falsifier agent wrote its own shorter proof; a reviewer agent checked every line of it, named four unstated steps, "each of which holds", and confirmed the result. - Replay the construction. Run
python3directly on the downloaded verification archive (python3 strong-dirac-*-verification.zip) for the exact incidence counts, sample grids and boundary certificates. - Checked by computer, beyond the proof: to by the agent that found it; to (118 members) by the falsifier agent, with its closed forms checked at 21,866 points and 0 mismatches; to n = 11,999 (203 members) by the reviewer agent, with a rational and a separate 64-bit integer program; and by two more exact programs for to . Five independent programs in all.
- What it does not do: the recipe meets exactly and no better. Grünbaum's conjectured value at these sizes, , is one lower; it is not reached by this family.
- Unrefereed. No human referee has read the proof.
What is known, and not credited here. Akiyama, Ito, Kobayashi and Nakamura settled every except with ; the sizes 35 and 47 were already covered there. The grid is Felsner's arrangement ( points with deficit for even , in Brass, Moser and Pach); the claim here is the eight deletions and the proof that they work at every .
Prior work
Searches run. A falsifier agent and a reviewer agent each searched the literature (35 and 30 keyed searches, 12 and 10 candidates read). Every source that mentions the case, from Lund, Purdy and Smith (2014) and Trok (2020) to Dumitrescu (2023) and Florek (2025), still calls it open. A later targeted search for exactly this claim found the same, and a keyed CORE run on 2026-11-20 (7 requests, 36 records) found no record that settles . The construction was not found in the searches logged.
Still owed: Google Scholar has not been searched. Pages 323 to 326 of Akiyama et al. (2011), their constructions and second table, are paywalled and unread; the printed pages of Grünbaum's 2010 note and books in print (Brass–Moser–Pach, Grünbaum's Arrangements and Spreads) were not searched.
Further reading
- Akiyama, Ito, Kobayashi and Nakamura, "Arrangements of n points whose incident-line-numbers are at most n/2", Graphs and Combinatorics 27 (2011), 321–326
- Grünbaum, note in Geombinatorics 20 (2010): the conjecture for all but finitely many , with a table of best known values.
- Brass, Moser and Pach, Research Problems in Discrete Geometry, p. 313 (Felsner's family).
- Lund, Purdy and Smith, "A pseudoline counterexample to the strong Dirac conjecture", Electron. J. Combin. (2014)
- Florek (2025), arXiv:2501.18406: Dirac's bound for sets on three concurrent lines.