Proved theorem Lean Unrefereed

Few lines through every point: an endless family 5/2 short of half

Edition 4 · On this site since · last revised · Verify & co-author
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
  1. The statement
  2. Check it yourself
  3. Worked examples
  4. Status and who checked it
  5. Prior work
  6. Further reading

The statement

Take nn points in the plane, not all on one line, and draw every line through two of them. Write t(p)t(p) for the number of these connecting lines through the point pp. Dirac asked in 1951 how small the largest t(p)t(p) can be; it is about n/2n/2 in every known example, and the shortfall n/2−max⁡pt(p)n/2 - \max_p t(p) measures how far the busiest point falls short of half.

Single sets fall short by 7/27/2 in print. For an infinite family, one set for infinitely many nn, the best in the sources read was Felsner's: 6K+76K + 7 points with largest t=3K+2t = 3K + 2 for even KK, a shortfall of 3/23/2. 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 nn, the least possible largest tt is G(n)=2⌊n/4⌋G(n) = 2\lfloor n/4 \rfloor, a shortfall of at most 3/23/2.

Theorem. For every s=0,1,2,…s = 0,\allowbreak 1,\allowbreak 2,\allowbreak \dots there are explicit sets of 60s+5360s + 53 points (family A) and of 60s+6960s + 69 points (family B), not all on one line, in which every point lies on at most (n−5)/2(n - 5)/2 of the connecting lines, and some point lies on exactly that many. The shortfall is 5/25/2 at every member.

What it refutes. In families A and B the busiest point lies on exactly G(n)−2G(n)-2 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 G(n)−2G(n)-2 as well. These four sizes are 60s+52,60s+53,60s+68,60s+6960s+52,\allowbreak 60s+53,\allowbreak 60s+68,\allowbreak 60s+69.

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 s≥0s \ge 0 and four bounds:

family aa ee bb mm nn
A 9s+79s + 7 3s+23s + 2 8s+68s + 6 5s+35s + 3 60s+5360s + 53
B 9s+99s + 9 3s+23s + 2 8s+88s + 8 5s+55s + 5 60s+6960s + 69

Write (p:q:c)(p : q : c) for the point (p/c,q/c)(p/c,\allowbreak q/c), or for the direction (p,q)(p,\allowbreak q) at infinity when c=0c = 0. The set is:

  • (1:0:c)(1 : 0 : c) and (0:1:c)(0 : 1 : c) for every whole cc with ∣c∣≤a|c| \le a of the same parity as aa, and for every ∣c∣≤e|c| \le e of the same parity as ee;
  • (1:1:c)(1 : 1 : c) and (1:−1:c)(1 : -1 : c) for every even cc with ∣c∣≤b|c| \le b;
  • (1:2:c)(1 : 2 : c), (1:−2:c)(1 : -2 : c), (2:1:c)(2 : 1 : c) and (2:−1:c)(2 : -1 : c) for every ∣c∣≤m|c| \le m of the same parity as mm;
  • 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 ±2\pm 2 and ±1/2\pm 1/2.

Count the smallest member (A, s=0s = 0: a,e,b,m=7,2,6,3a,\allowbreak e,\allowbreak b,\allowbreak m = 7,\allowbreak 2,\allowbreak 6,\allowbreak 3). The axes get 8+3=118 + 3 = 11 points each, the diagonals 7 each, the four steep and shallow lines 4 each, and the origin: 22+14+16+1=5322 + 14 + 16 + 1 = 53.

One point by hand. Take P=(−1/7,0)P = (-1/7,\allowbreak 0). Two other points share a line through PP exactly when they have the same slope from PP. For example (0,−1/3)(0,\allowbreak -1/3), (−1,2)(-1,\allowbreak 2) and (−1/4,1/4)(-1/4,\allowbreak 1/4) all have slope −7/3-7/3 from PP: (0,−1/3)(0,\allowbreak -1/3) is 1/71/7 across and 1/31/3 down, (−1,2)(-1,\allowbreak 2) is 6/76/7 back and 2 up, and (−1/4,1/4)(-1/4,\allowbreak 1/4) is 3/283/28 back and 1/41/4 up. Grouping all 52 other points by slope gives 24 lines through PP: 15 that hold two or more other points and 9 that hold one. And 24=(53−5)/224 = (53 - 5)/2.

Half of 53 is 261226\tfrac12. 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 ss, by hand. On the line x=ax = a of the dual picture (each point (p:q:c)(p : q : c) stands for the line px+qy=−cpx + qy = -c), the crossings number (a+e+2)+b+2(3s+2)+2(2s+1)+1=30s+24(a + e + 2) + b + 2(3s + 2) + 2(2s + 1) + 1 = 30s + 24 for A, and 30s+3230s + 32 for B: some point reaches (n−5)/2(n - 5)/2 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 ss on each class of lines. A convex function that is at most (n−5)/2(n - 5)/2 at the two edges of its range and does not grow along them is at most (n−5)/2(n - 5)/2 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 5/25/2. The third of these has n=60s+61n=60s+61 for s≥1s\ge1.
  • What the downloadable checker adds. Run python3 directly 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 s=60s = 60 by the falsifier agent (122 sets, the largest 3653 and 3669 points); every line of every member from s=0s = 0 to 2000, and at ss = 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 tt is exactly (n−5)/2(n - 5)/2.
  • 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 3/23/2 was not found in the searches logged. On 2026-11-22, a Google Scholar sweep (6 queries) found no prior work stating this claim.

Still owed: 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 paywalled body of Akiyama et al. (2011), 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 18j+718j + 7 pseudolines with no pseudoline through more than 8j+28j + 2 crossings, a shortfall of j+3/2j + 3/2, without bound.
  • Trok (2020) remarks that "all but finitely many" known counterexamples satisfy the conjecture with c0=3/2c_0 = 3/2; 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 5/25/2, so the family says nothing against some point on at least n/2−cn/2 - c lines for a fixed cc; it shows only that such a cc would be at least 5/25/2.
  • 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 ss.

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 n=12k+11n = 12k + 11 of Akiyama et al.'s question, on the same problem.