Few lines through every point: an endless family 5/2 short of half
- Kind
- Theorem, computer-assisted (the count at the busiest points by hand; the upper bound by a computer certificate)
- Status
- Lean 4 upper bounds, exact incidence certificates and independent agent review; unrefereed
- Prior work
- Not found in the searches logged; answers the remark of Lund, Purdy and Smith (2014) that no such family of lines was known; for pseudolines a larger shortfall is in print
On this page
The statement
Take points in the plane, not all on one line, and draw every line through two of them. Write for the number of these connecting lines through the point . Dirac asked in 1951 how small the largest can be; it is about in every known example, and the shortfall measures how far the busiest point falls short of half.
Single sets fall short by in print. For an infinite family, one set for infinitely many , the best in the sources read was Felsner's: points with largest for even , a shortfall of . Lund, Purdy and Smith (2014) wrote: "No infinite family of arrangements of n lines is known such that each member has fewer than n/2 − 3/2 intersection points". And Grünbaum's 2010 conjecture says that, apart from finitely many , the least possible largest is , a shortfall of at most .
Theorem. For every there are explicit sets of points (family A) and of points (family B), not all on one line, in which every point lies on at most of the connecting lines, and some point lies on exactly that many. The shortfall is at every member.
What it refutes. In families A and B the busiest point lies on exactly connecting lines. The paper specifies one point to remove from each set. A point attaining the maximum survives, and every line counted there is still present. The adjacent even examples therefore attain as well. These four sizes are .
The paper gives exact maxima for six odd constructions and six specified even deletions over their stated parameter ranges. These counts give upper bounds on the minimum possible maximum over all planar point sets of each size.
Check it yourself
The points. Pick and four bounds:
| family | |||||
|---|---|---|---|---|---|
| A | |||||
| B |
Write for the point , or for the direction at infinity when . The set is:
- and for every whole with of the same parity as , and for every of the same parity as ;
- and for every even with ;
- , , and for every of the same parity as ;
- the origin.
Every point but the origin lies on one of eight lines through the origin: the two axes, the two diagonals and the four lines of slope and .
Count the smallest member (A, : ). The axes get points each, the diagonals 7 each, the four steep and shallow lines 4 each, and the origin: .
One point by hand. Take . Two other points share a line through exactly when they have the same slope from . For example , and all have slope from : is across and down, is back and 2 up, and is back and up. Grouping all 52 other points by slope gives 24 lines through : 15 that hold two or more other points and 9 that hold one. And .
Half of 53 is . An exact count of all 53 points gives 1 point on 8 lines, 4 on 12, 6 on 14, 4 on 18, 10 on 20 and 28 on 24; no point is on more.
Worked examples
The same count for every , by hand. On the line of the dual picture (each point stands for the line ), the crossings number for A, and for B: some point reaches in every member. A reviewer agent redid this count term by term.
Why no point does worse (the hard half). In the dual picture, the lines of one direction cross a given line at evenly spaced positions. Counting every position from the leftmost start to the rightmost end of the rows that use it can only overcount, and that overcount is a convex function of the line's offset and of on each class of lines. A convex function that is at most at the two edges of its range and does not grow along them is at most everywhere. A computer checks the edges: 4 residue classes for each axis class, 18 for the diagonals and 720 for each of the steep and shallow classes.
Status and who checked it
- What Lean checks. The library proves upper bounds for all six odd constructions and equality for the three odd families with deficit . The third of these has for .
-
What the downloadable checker adds. Run
python3directly on the downloaded verification archive (python3 strong-dirac-*-verification.zip) to verify the boundary counts and the points attaining the bounds in the other three odd families. The paper shows which diagonal to remove so that the maximum survives in each of the six even families. Together these constructions give exceptions to Grünbaum's conjecture in 12 classes modulo 60. -
Proved (computer-assisted). The lower count is by hand. The upper bound rests on a computer certificate written by the agent that found the sets, and on a second certificate written by a falsifier agent without the finder's symmetry shortcut (8, 36 and 1,440 residue classes). Both certificates use one idea, so a flaw in the idea would sit in both. A reviewer agent read the falsifier's program line by line against the mathematics and wrote: "I found no gap"; fed six claims that are false by exactly one, the certifier "refused all six".
- Exact counts, with no overcount at all: every member up to by the falsifier agent (122 sets, the largest 3653 and 3669 points); every line of every member from to 2000, and at = 10,000, 100,003 and 1,000,001 (the largest with 60,000,129 points), by the reviewer agent; and smaller ranges by three more programs. In every one the largest is exactly .
- Limits. No hand proof of the upper bound exists, and no person has read the proof. In the reviewer's words: "Nobody has written the upper bound out by hand, and no certificate of a different principle exists." The claim is for straight lines only.
- Unrefereed. No human referee has read it.
Prior work
Searches run. Three logs by falsifier, reviewer and targeted search agents pass the literature check (33, 72 and 46 searches; 15, 8 and 16 candidates), with no candidate making the same claim. Every source read that lists infinite families names Felsner's and nothing beyond it: Lund, Purdy and Smith (2014), Trok (2020), Dumitrescu (2022), Florek (2025) and Brimkov (1 Nov 2026). An infinite family of point sets, or of straight-line arrangements, with shortfall above was not found in the searches logged.
Still owed: Google Scholar (refused by its monthly cap until 2026-12-01) and a keyed CORE search aimed at this claim (refused by CORE's daily cap); most of the arXiv API, OpenAlex and Semantic Scholar's keyword search, which throttled; the body of Akiyama et al. (2011), the printed Geombinatorics pages and the books in print.
What is known, and not credited here.
- Pseudolines. For curves that cross like lines but need not be straight, a larger shortfall is already in print, in the same 2014 paper: Lund, Purdy and Smith's Theorem 3 gives pseudolines with no pseudoline through more than crossings, a shortfall of , without bound.
- Trok (2020) remarks that "all but finitely many" known counterexamples satisfy the conjecture with ; the remark is about the counterexamples known then and carries no proof, so it is out of date, not contradicted.
- Not the strong Dirac conjecture. The shortfall is a fixed , so the family says nothing against some point on at least lines for a fixed ; it shows only that such a would be at least .
- Felsner's family, Grünbaum's conjecture and Dirac's question are theirs; the claim here is the two families and the proof that they work for every .
Further reading
- Lund, Purdy and Smith, Electronic Journal of Combinatorics 21(2) (2014) #P2.31: the remark this answers, and the pseudoline family.
- Grünbaum, note in Geombinatorics 20 (2010): the conjecture refuted here.
- Dumitrescu, arXiv:2204.06101; Florek, arXiv:2501.18406; Trok, arXiv:2003.02397.
- Few lines through every point: the case of Akiyama et al.'s question, on the same problem.