Minimal generating set size

[Edwin Clark]

On Tue, 14 Mar 2006, Dan Dima wrote:

> Here are some links for the 2-dimensional version of the problem:
> 
> http://mathforum.org/kb/message.jspa?messageID=3545255&tstart=0
> http://www.mathlinks.ro/Forum/viewtopic.php?t=6159
> 
> It seems that:
> a*n^{2/3} <= f(n) <= b*n^{2/3}*log(n).
> 

With the help of the clue that Noga Alon obtained these bounds from one
of the postings I found the following abstract of a paper of his which
has the generalization of the above formula to the d-dimensional case:

MR1118729 (92g:52017)
Alon, N.(IL-TLAV)
Economical coverings of sets of lattice points.
Geom. Funct. Anal. 1 (1991), no. 3, 224--230.

Let $t(n,d)$ be the minimum number $t$ of the $n^d$ integer lattice points 
$\{(x_1,x_2,\cdots, x_d)\colon 1\leq x_i\leq n\}$ in a cube such that the 
$\binom t2$ lines determined by the $t$ chosen lattice points cover all 
$n^d$ lattice points in the cube. It is shown that there are constants 
$c=c(d)$ and $C=C(d)$ such that $cn^{d(d-1)/(2d-1)}\leq t(n,d)\leq 
Cn^{d(d-1)/(2d-1)}\log n$. The special case $d=2$ solves a problem posed 
by Erds and Purdy \ref[see R. Guy, Unsolved problems in number theory, see 
p. 133, Springer, New York, 1981; MR0656313 (83k:10002)].
---------------------------------

In addition I computed the following values for the two dimensional
case: 4,4,4,6,6,7 for the cases n = 1,2,3,4,5,6 where the n-th
square is {(x,y): x,y in {0,1,...,n}}. I plan to add this to the
OEIS soon. I want to first look at Guy's book and the Alon paper
to see if they have calculated more values.

Unless I learn of a better technique, getting exact values for the
three dimensional case for small n looks out of reach for now.

--Edwin