How many ways are there to pick $n$ points on the finite affine plane $(\Bbb F_q)^2$ such that no three are collinear?

Question

How many ways are there to pick $n$ points on the finite affine plane $(\Bbb F_q)^2$ such that no three are collinear?

For example, how many ways can we pick $5$ points on $\Bbb F_{32}\times\Bbb F_{32}$, no three collinear? (Is this brute-forceable, I wonder?)

The collinearity condition can be expressed as follows: the points $(a_0,b_0)$, $(a_1,b_1)$, and $(a_2,b_2)$ are collinear iff: $$\begin{vmatrix}1&1&1\\a_0&a_1&a_2\\b_0&b_1&b_2\end{vmatrix}=0$$ Thus the question makes sense over a finite field.

Conjecture: Call this number $f_n(q)$. Then $f_n$ is a polynomial in $q$ for fixed $n$.

Is this conjecture true?

---

This is a cross-post of a question I previously asked on Math Stack Exchange, so you can see the comments there for some discussion. (They seem to have determined that $f_5$ is a polynomial, but I haven't verified this.)

The obvious strategy is inclusion-exclusion, but there are some difficulties. See the diagrams in this Imgur album. The first, the eleven-point extended pentagon (the ten points of a pentagram together with its center), can only be realized in fields possessing a $\sqrt5$; the latter, the nine-point Hesse configuration, can only be realized in fields possessing a $\sqrt{-3}$. (Citations for these can be found in the comments to the Math SE post.) An inclusion-exclusion-based approach would not only have to determine when each configuration occurs in each field, which already seems to require algebraic machinery that I do not possess, but how often.

Answer 1

This is not an answer to your question but a long remark on naive bruteforceability (using a computer) for counting all choices of five points in $\mathbb F_{32}^2$ satisfying your condition.

There are ${1024\choose 5}\sim 10^{13}$ possible configurations which is a bit huge but one can use the action of the affine group (which has $1024\cdot 1023\cdot 992$ elements if I did not make a stupid mistake) and work with orbits. There are therefore roughly $O(10^6)$ orbits to consider.

Concretely, every orbit has a representant with one point at the origin and two other points forming the standard basis (i.e. we can assume that $(0,0),(1,0),(0,1)$ are among the five points). There are now ${1021\choose 2}\sim 500\ 000$ choices for the last two points. One has then to check your condition (which is more or less straightforward) and one has to compute the 'multiplicity' (i.e. how many different choices of the last two points yield the same orbit). In order to do this, we consider all $5\cdot 4\cdot 3=60$ ordered triplets of three distinct points among these five points, send them affinely to $(0,0),(1,0),(0,1)$ and count the number of different pairs corresponding to the remaining two points. Weighting each solution with the inverse of this 'multiplicity' and going over all possibilities yields the result (this takes probably only a few seconds, the hard part is all the coding).

With this naive approach, the complexity for counting the number of solutions is $O(q^4)$. It will therefore probably take a couple of hours for a field with roughly $1000$ elements.