Tessellating $\mathbb{R}^n$ by bricks.

Edit: Per Tapio's answer, $1 \times 2 \times 3 \times ... \times n$ bricks always suffice, so $s(n)\leq \left(\begin{array}{c} n+1 \\ 2 \end{array}\right)$. Consider the lattice in $\mathbb Z^n$ defined by the equations $x_1 \equiv x_2$ mod $2$, $x_2 \equiv x_3$ mod $3$, ..., $x_{n-1} \equiv x_n$ mod $n$. Place a $1 \times 2 \times ... \times n$ bricks with one corner at each vertex of the lattice. This covers $\mathbb R^n$ because you first round $x_1$ down to the nearest integer, then $x_2$ down to the nearest multiple of two plus $x_1$, .... The second condition is clearly satisfied, since the distance between any two bricks is an integer. We only need to check the first. Equivalently, we check that there cannot be $n+2$ lattice points in a single brick of the same size. Proof: Suppose there were. Then two of them would have to have the same value of $x_n$ mod $n+1$. Since the $x_n$ values of those two points lie in an interval of length $n$, they must be the same. So they have the same value of $x_{n-1}$ mod $n$. By induction, they are identical.

Is this bound sharp? For $n=1$, this is clear. Here is a proof for $n=2$. Form a graph where the faces are bricks, the the edges are the boundaries of bricks, and the vertices are places where two bricks intersect. Suppose that no brick is a hexagon or larger. Then the number of edges in a large reason is no more than $5/2$ the number of faces, and the number of vertices is exactly $2/3$ the number of edges, so the Euler number is at least $F -5/2(1-2/3)F=F/6$ which is $O$ of the area of the region, where it should be $O$ of the boundary. Or "the graph is somewhere between a cube and a dodecahedron, but nowhere near an infinite plane"

Therefore, some face has at least 6 edges. Each edge has length and least $1$, since the two vertices can share at most two faces, so the other faces at each vertex are nonadjacent, so have distance at least $1$. Therefore the perimeter of some face is at least $6$. The perimeter of $[0,a]\times [0,b]$ is of course $2(a+b)$, so $s(2)\geq 3$. There is an explicit example with $s(T)=3$, so we are done.

Obviously parts of this argument generalize to higher dimensions, but it is not clear to me if one can patch up the other parts to make it usable.

If I undderstand the problem correctly one case would be that all bricks are translates of each other in which case a tessalation can be summarized by the lattice of centers of bricks. Up to reordering coordinates, generators for this lattice can be chosen to be the columns of a triangular matrix $M$ and two which differ by an integer triangular basis change are equivalent. In this case $s(M)=dt(M)/L(M)$ where $t(M)$ is the trace of the matrix $M$ and $L(M)$ is the minimum 1-norm of a nonzero lattice element.

Claim: $s(d+1)/(d+1) \geq s(d)/d + 1/2$.

Thus $s(d) \geq d(d+1)/2$.

Proof: If M is obtained by adding a new vector v with diagonal entry r (and dimension) to N then up to translation by the lattice spanned by columns of N, the projection of v to the space spanned by N has 1-norm at least $L(N)/2$ and $s(M)/(d+1)=(t(N)+r)/\min(L(N),L(N)/2 + r) \geq s(N)/d + 1/2$, with equality if $r=L(N)/2$.

There is a large space of lattices achieving this bound.
One simple solution has diagonal entries (brick edge lengths) of (d/2)(2,1,1,...,1) and first off diagonal of (d/2)(1,1,...,1).

Since Ycor took the liberty to edit this 5 year old question and thus to bring it to the front page again, I'll throw in my one cent (not two yet; that may come later).

If you do a lattice tiling by translates, then, as Eric showed, we have no chance to get below the quadratic rate. However, not all tilings are like that. We cannot gain too much, but I think we still can gain somewhat (though I'm not ready to present an example yet).

First, the foolproof part: why not too much. By our conditions, any shift of the ball $B$ or radius $1/2$ in $\ell_1$ cannot intersect two disjoint bricks simultaneously, so we have all bricks intersecting $B$ also intersecting pairwise, which, by the special feature of bricks, means having a common point (bricks are like intervals on the line in this respect). Thus, the covering number for $(K_j+B)$ is at most $d+2$ but the volume of each brick increased $\sum_{\ell\ge 0}\sigma_\ell(\frac{1}{k_1},\dots,\frac 1{k_d})\frac 1{\ell!}$ times where $\sigma_\ell$ is the usual symmetric sum. By the AM-GM used twice, this is at least (here $q=d/s$) $$ \sum_{\ell=0}^d \frac{d!}{(\ell!)^2{(d-\ell)!}}q^\ell\ge\max_{\ell\le d/2}\left(\frac{dq}{2\ell^2}\right)^\ell\approx{e^{c\sqrt{dq}}} $$ if $q\le d$ and, clearly, increasing beyond that point. Thus $dq\le C\log^2 (d+2)$ and $s\ge cd^2\log^{-2}(d+2)$ regardless of whether we use same size bricks or not and whether we follow any regular pattern or not, or even whether we do a tesselation or just covering, killing all Gerhard's hopes for a linear bound.

To be continued...