IMC 2014 · Day 2 · P9

The answer is: $$d(k, n) = \begin{cases} k \cdot n & k, n > 1 \\ k + n & \text{otherwise} \end{cases}$$ Throughout the solution, we shall often say that a hyperplanes skips a point to signify that the plane does not contain that point.

For $n = 1$ the claim is obvious.

For $k = 1$ we have an arbitrary finite set of points in $\mathbb{R}^n$ such that neither hyperplane contains it entirely. We can build a subset of $n + 1$ points step by step: on each step we add a point, not contained in the minimal plane spanned by the previous points. Thus any 1-generic set contains a non-degenerate simplex of $n + 1$ points, and obviously a non-degenerate simplex of $n + 1$ points cannot be reduced without loosing 1-generality.

In the case $k, n > 1$ we shall give an example of $k \cdot n$ points. On each of the Cartesian axes choose $k$ distinct points, different from the origin. Let's show that this set is $k$-generic. There are two types of planes: containing the origin and skipping it. If a plane contains the origin, it either contains all the chose points of a axis or skips all of them. Since no plane contains all axes, it skips the chosen $k$ points on one of the axes. If a plane skips the origin, it it contains at most one point of each axis. Therefore it skips at least $n(k-1)$ points. It remains to verify a simple inequality $n(k-1) \ge k$ which is equivalent to $(n-1)(k-1) \ge 1$ which holds for $n, k > 1$.

The example we have shown is minimal by inclusion: if any point is removed, say a point from axis $i$, then the hyperplane $x_i = 0$ skips only $k - 1$ points, and our set stops being $k$-generic. Hence $d(k, n) \ge kn$.

It remains to prove that Hence $d(k, n) \ge kn$ for $k, n > 1$,

meaning: for each $k$-generic finite set of points, it is possible to choose a $k$-generic subset of at most $kn$ points. Let us call a subset of points minimal if by taking out any point, we loose $k$-generality. It suffices to prove that any minimal $k$-generic subset in $\mathbb{R}^n$ has at most $kn$ points. A hyperplane will be called ample if it skips precisely $k$ points. A point cannot be removed from a $k$-generic set, if and only if it is skipped by an ample hyperplane. Thus, in a minimal set each point is skipped by an ample hyperplane.

Organise the following process: on each step we choose an ample hyperplane, and paint blue all the points which are skipped by it. Each time we choose an ample hyperplane, which skips one of the unpainted points. The unpainted points at each step (after the beginning) is the intersection of all chosen hyperplanes. The intersection set of chosen hyperplanes is reduced with each step (since at least one point is being painted on each step).

Notice, that on each step we paint at most $k$ points. So if we start with a minimal set of more then $nk$ points, we can choose $n$ planes and still have at least one unpainted points. The intersection of the chosen planes is a point (since on each step the dimension of the intersection plane was reduced), so there are at most $nk + 1$ points in the set. The last unpainted point will be denoted by $O$. The last unpainted line (which was formed on the step before the last) will be denoted by $\ell_1$.

This line is an intersection of all the chosen hyperplanes except the last one. If we have more than $nk$ points, then $\ell_1$ contains exactly $k + 1$ points from the set, one of which is $O$.

We could have executed the same process with choosing the same hyperplanes, but in different order. Anyway, at each step we would paint at most $k$ points, and after $n$ steps only $O$ would remain unpainted; so it was precisely $k$ points on each step. On step before the last, we might get a different line, which is intersection of all planes except the last one. The lines obtained in this way will be denoted $\ell_1, \ell_2, \dots, \ell_n$, and each contains exactly $k$ points except $O$. Since we have $O$ and $k$ points on $n$ lines, that is the entire set. Notice that the vectors spanning these lines are linearly independent (since for each line we have a hyperplane containing all the other lines except that line). So by removing $O$ we obtain the example that we've described already, which is $k$-generic.

Remark. From the proof we see, that the example is unique.