Covering a (hyper)cube with lines

Question

Let $K_n$ be the sets of vectors $x \in \mathbb{Z}^d $ with each coordinates $x_i$ between $1$ and $n$. For any subset $A$ of $K_n$, let $S(A)$ be the set of points $x \in K_n$ which are on some line containing at least two points of $A$ (in other words, $S(A)$ is the union of the lines passing through - at least - two points of $A$).

Such a set $A$ is said to generate $K_n$ if $S(A) = K_n$. Now let $r_d(n)$ be the smallest size of a generating subset of $K_n$.

Question : What are the best known bounds on $r_d(n)$ ? (The first non trivial case is $d=2$)

This problem may be "well-known" ; I'm almost sure this question has already been studied, but I didn't find any reference, and Google gives nothing.

The trivial bound is $r_d(n) \gg_d n^{\frac{d}{2}- \frac{1}{2}} $ : taking a generating subset of size $r_d(n)$, there are at most $O(r_d(n)^2)$ lines to consider, each one intersecting $K_n$ in at most $n$ points, so that $|K_n| \ll r_d(n)^2 \times n$.

A refinement of this argument (a typical line contains much less than $n$ points of $K_n$) gives a lower bound $r_d(n) \gg_d n^{\frac{d}{2}- \frac{1}{4} - \frac{1}{4(2d-1)} } $.

Answer 1

I think the probabilistic method gives an A of size $O_d(n^{d/2}\sqrt\log n)$. (Formula updated according to js's comment.)

Put every point to A independently with probability p. What is the probability that a point x will be in S(A)? For any x, we can find $\Omega(n^d)$ pairs of points that are all different such that x lies on the line of any pair. (This is true because e.g. for d=2 if x is in the bottom-left part of $K_n$, then we can take the $n/4\times n/4$ grid upper-right from it, contract the $n/8 \times n/8$ bottom-left of this grid, and double each point from x to get its pair.)

The probability that both points of a fixed pair are in A is $p^2$, the probability that no such pair exists is $(1-p^2)^{n^d}$. So if $n^d(1-p^2)^{n^d}<1$, then we are done using the union bound. Unless I am mistaken this is true if $p>\Omega_d(n^{-d/2}\sqrt\log n)$.

Now of course we cannot be sure about how big A is. But if we replace the above $<1$ with a $<1/2$, then we can even add the condition that A should be at most $pn^d$, for which the probability is $\ge 1/2$. So we get $O_d(n^{d/2}\sqrt\log n)$ points. Maybe this can be further improved with some more advanced probabilistic methods.

Answer 2

Not an answer, but a comment too long to fit the space.

You may be interested to know that for finite projective geometries, the property in question has a dedicated name: namely, a set $A\subset PG(r,q)$ is called $\rho$-saturating, if every point of $PG(r,q)$ is contained in a subspace, generated by $\rho+1$ points from $A$. However, to my understanding, Not much is known about such sets, with the exception of the case where $\rho=1$ and $q=2$. It would be equally natural, of course, to consider the problem for the finite affine geometries: how small can be a set $A\subset{\mathbb F}_q^r$ given that every point of ${\mathbb F}_q^r$ is on a line through two points of $A$?

Answer 3

Are you interested in upper bounds? For $d=2$, if $n=2m$ is even, then a centrally placed $2\times m$ bar seems to generate $K_n$. This gives $r_2(n)\le n$, quite far from your lower bound.