7
$\begingroup$

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

$\endgroup$

3 Answers 3

9
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ You can also choose a random subset of a fixed size, say $p n^d$. $\endgroup$ Jun 21, 2012 at 18:28
  • 1
    $\begingroup$ 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). $\endgroup$
    – js21
    Jun 22, 2012 at 15:20
6
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – Seva
    Jun 21, 2012 at 7:57
  • 2
    $\begingroup$ 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. $\endgroup$
    – js21
    Jun 21, 2012 at 15:59
  • 1
    $\begingroup$ 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 $\endgroup$ Jun 21, 2012 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.