## Covering a (hyper)cube with lines

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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

-

## 3 Answers

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 at 18:28

1
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). – js Jun 22 at 15:20

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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.

-

2
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 at 7:57

2
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. – js Jun 21 at 15:59

1
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 at 16:42
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 74, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9429336786270142, "perplexity_flag": "head"}