MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

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.

share|cite|improve this answer
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$?

share|cite|improve this answer

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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