How many points should we remove so that there are no n points lying on a line?

Question

Problem. For any integer $n\geq 2$, how many points should we remove from $\{(x,y,z)\colon\, x,y,z\in \{0,1,\ldots, n-1\}\}$ so that there are no $n$ points lying on a line?

Let $f(n)$ denote the minimum number of points satisfying the above problem. Then clearly we have $f(n)\leq n^3-(n-1)$. This trivial upper bound is tight for $n=2$, i.e., $f(2)=7$.

For each pair $(y,z)\in\{0,1,\cdots,n−1\}^2$, let $\ell_{y,z}$ be the line containing points $(0,y,z),(1,y,z),\ldots,(n−1,y,z)$. Then these $n^2$ lines are pairwise point-disjoint. In order to destroy these lines, we need to remove at least $n^2$ points. Hence, $f(n)\geq n^2$. This argument is in fact equivalent to say that the transversal number (or covering number) is at least the matching number of a hypergraph defined based on our problem. This bound is not always tight. In particular, I can show that $f(3)=11$.

Answer 1

Let me first prove that $f(n) = n^2 + O(n)$, then give a heuristic why $f(n) = n^2$ for big enough $n$ (which maybe could be made into an actual proof with enough perseverance) and then explain why I find the problem statement slightly unnatural, and what I think should be the right version.

For the first, note that most of the lines have the form $(\cdot, x, y)$, $(x, \cdot, y)$ or $(x, y, \cdot)$, and there are $3n^2$ such lines, and the number of remaining lines is $O(n)$ ($6n+4$ if my math is correct). To exlude all these lines consider $\{0, \ldots , n-1\}$ as $\mathbb{Z}/n\mathbb{Z}$, and consider the set of points $(x, y, x+y)$ (there are $n^2$ points in it). Note that it intersects each of the aformentioned lines, and for each of the remaining $O(n)$ lines we can pick remove one point on it for a total of $n^2+O(n)$ points.

For the second, although my construction of the set intersecting main lines may appear to be quite rigid, in fact there is a whole lot of such sets, so it is very foreseeable that we can pick these $n^2$ points in such a way that we cover all the extra lines as well by chance, if $n$ is big enough. If we went one dimension down (from $3$ to $2$), then the sets covering main lines correspond to permutations, and we just have to cover 2 diagonals, which is doable if $n\ge 3$, I expect similar to be possible in dimension $3$ (and all higher dimensions, as long as $n$ is big enough).

The above, in particular my construction of the intersecting set, suggests that we should consider points not lying in $\mathbb{R}^3$, but really in $(\mathbb{Z}/n\mathbb{Z})^3$, and then consider lines in this space, that is we should allow lines to "wrap around" the sides of the cube. Then I expect the answer to actually be $n^3-(n-1)^3$, and at least in the case $n$ being prime I imagine it being provable with some version of the combinatorial Nullstellensatz.

Answer 2

For small enough fixed $n$, you can solve the (set covering) problem via integer linear programming as follows. Let $L$ be the set of lines with $n$ points, and let $P_\ell$ be the set of points in line $\ell \in L$. Let binary decision variable $x_{ijk}$ indicate whether point $(i,j,k)$ is removed. The problem is to minimize $\sum_{i,j,k} x_{ijk}$ subject to linear constraints $$\sum_{(i,j,k)\in P_\ell} x_{ijk} \ge 1 \quad \text{for all $\ell\in L$}$$

For $n\in\{2,\dots,40\}$, the only exceptions to $f(n)=n^2$ turn out to be $$f(2)=7, f(3)=11, f(4)=19, f(5)=28, f(6)=39.$$