# Covering a (hyper)cube with lines

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

-

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.

-
You can also choose a random subset of a fixed size, say $p n^d$. –  Douglas Zare Jun 21 '12 at 18:28
A nice application of the probabilistic method ! Remark : the constant in the $\Omega(n^d)$ depends on $d$, so the final bound should be $O_d (n^{d/2} \log n)$, or $O_d (n^{d/2} \sqrt{\log n} )$ if I'm not mistaken (also, $r_d(2) = 2^d$ gives a lower bound for the implicit constant). An other remark : for $d=2$, this is essentially the same as the bound $r_2(n) = O(n)$ (as pointed out below by Gerry Myerson). –  js21 Jun 22 '12 at 15:20

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

-

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.

-
In fact, for any $d\ge 1$ one can get $r_d(n)\ll_d n^{d-1}$ just by considering the points on the boundary. However, this is likely to be very far from the truth. –  Seva Jun 21 '12 at 7:57
More generally, $r_1(n) = 2$ and $r_d(n) \leq n \times r_{d-1}(n)$ (by taking $n$ copies of a $(d-1)$-dimensional generating set). I expect $n^{d/2}$ to be closer to the truth than $n^{d-1}$ (for large $d$), but I suspect a good upper bound might be harder to obtain than lower bounds. –  js21 Jun 21 '12 at 15:59
For n=2, js gives an exact bound. It may be fruitful to consider $r_d(3)$ and $r_d(4)$ for small $d$. Gerhard "Ask Me About Small Cases" Paseman, 2012.06.21 –  Gerhard Paseman Jun 21 '12 at 16:42