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

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$$.

• If you are interested in higher-dimensional version, you may be interested in the Hales--Jewett theorem ( en.m.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem; see discussion of the density version). Jun 9 at 6:19
• If you remove the roughly $3n^2$ points that have a zero coordinate, there will be no more lines, so $f(n)=\Theta(n^2)$. Jun 9 at 7:33
• @IlyaBogdanov For Hales-Jewett, a subtle difference is that the set of lines omits some of the diagonals that are included here. Jun 9 at 12:37
• @RobPratt: I do not see such diagonals; may you show a sample difference? Jun 9 at 21:04
• From the Wikipedia link: "Note that the line 13, 22, 31, while a valid line for the game tic-tac-toe, is not considered a combinatorial line." Jun 9 at 22:03

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.

• Yes, the number of lines is $3(n+1)^2+1$: oeis.org/A056107 Jun 9 at 13:10
• The part at the end where you mention cyclic groups relates closely to my question: mathoverflow.net/questions/446574/… Jun 11 at 13:39

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.$$

• It's worth adding this sequence to the OEIS if not yet. Jun 10 at 9:42
• After 7,11,19,28,39 this is likely to be just a sequence of perfect squares, not sure if this is interesting enough for OEIS... Jun 12 at 15:47