10
$\begingroup$

Let us call the $\ell_1$-product of intervals $[0,k_1]\times...\times [0,k_n]$ a brick of size $k_1+...+k_n$. Consider a tessellation $T$ of $\mathbb{R^n}$ by (shifted) bricks so that every point belongs to at most $n+1$ bricks and the $\ell_1$-distance between any two disjoint bricks is at least 1 (thus every two bricks can share only the boundary points). Let $s(T)$ be the maximal size of a brick in that tessellation. Let $s(n)$ be the minimum of all $s(T)$. For example, $s(1)=1$ (we tessellate $\mathbb{R}$ by intervals $[i,i+1]$), $s(2)\le 3$ (we can tessellate ${\mathbb R}^2$ by $2\times 1$-bricks so that each point belongs to at most 3 bricks). It is easy to have a tessellation with $s(T) \sim 2^n$, so $s(n)$ is at most exponential.

Question. What is $s(n)$? Does $s(n)$ grow exponentially with $n$?

Update It looks like the question is completely answered when we assume that all bricks are isometric by Will (upper bound) and Eric (lower bound). What if we tile by different bricks? How about arbitrary convex regions (same properties: every point belongs to at most $n+1$ regions, every two disjoint rejions are at distance at least 1, and, of course, different regions may share only boundary points)? Can we achive livear upper bound on the diameter of a tile? Can there be a constant upper bound?

$\endgroup$
4
  • 2
    $\begingroup$ I'm not familiar with the concept of $\ell_1$-product. Could you explain? $\endgroup$ Jul 12, 2012 at 19:25
  • 1
    $\begingroup$ It is just the product of intervals (i.e. the set of all points $(x_1,...,x_n)$ with $0\le x_i\le k_i, i=1,...,n$ with $\ell_1$-metric, i.e. the distance between $(x_1,...,x_n)$ and $(y_1,...,y_n)$ is $\sum |x_i-y_i|$. $\endgroup$
    – user6976
    Jul 12, 2012 at 19:41
  • $\begingroup$ What would the $\ell_2$-product of intervals be? $\endgroup$ Jul 12, 2012 at 20:03
  • 2
    $\begingroup$ @Tom: It would be the same set but with a distance $\sqrt{\sum |x_i-y_i|^2}$ and with a correspondingly different definition of size. $\endgroup$ Jul 12, 2012 at 20:38

5 Answers 5

7
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ It looks right but why "Equivalently, we check that there cannot be $n+2$ lattice points in a single brick of the same size"? $\endgroup$
    – user6976
    Jul 13, 2012 at 7:15
  • $\begingroup$ If we put a brick with the top-right-north-etc. corner at each point in the lattice, then $n+2$ of those bricks colliding at a point $P$ is equivalent to $n+2$ lattice points lying in a brick whose bottom-left-south-etc. corner is at $P$, since that's the inverse of the "contained in a brick starting at" relation. $\endgroup$
    – Will Sawin
    Jul 13, 2012 at 12:49
  • $\begingroup$ I think I understand the proof. It is very nice. $\endgroup$
    – user6976
    Jul 13, 2012 at 13:25
  • $\begingroup$ I have some ideas about lower bounds but nothing strong enough to actually provide a good general-case lower bound. $\endgroup$
    – Will Sawin
    Jul 13, 2012 at 15:47
  • $\begingroup$ @Will: There is a reference to your answer here: front.math.ucdavis.edu/1008.3868 Thanks again! $\endgroup$
    – user6976
    Jul 25, 2012 at 15:59
6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ @Eric: Thank you! $\endgroup$
    – user6976
    Jul 14, 2012 at 6:13
  • $\begingroup$ What if we allow bricks of different sizes? $\endgroup$
    – user6976
    Jul 14, 2012 at 6:16
5
$\begingroup$

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...

$\endgroup$
3
  • $\begingroup$ I "took the liberty" to edit this question (namely add 2 tags) only a few minutes or hours after "jeq" edited Tapio Rajala's answer. So I'm not responsible for bringing it to the front page (I usually take such opportunities for such edits). [Unfortunately the precise time of edits is not available -it was possibly available at the time you wrote this-, although it would be a trivial feature, also useful for checking chronology between different answers.] $\endgroup$
    – YCor
    Dec 8, 2017 at 23:05
  • 1
    $\begingroup$ @YCor Come on, I'm not accusing you of anything. Quite on the contrary: this is a nice problem and I missed the thread entirely 5 years ago :-) $\endgroup$
    – fedja
    Dec 8, 2017 at 23:26
  • $\begingroup$ Then it's not thanks to me that you eventually stumbled on it :) $\endgroup$
    – YCor
    Dec 8, 2017 at 23:35
4
$\begingroup$

So far I thought about $n=3$ and it seems that at least you can improve from the example $T$ with $S(T) = 2^n -1 = 7$. Namely a tessellation with length $3+2+1 = 6$ suffices:

     (source)

$\endgroup$
1
$\begingroup$

I will go out on a limb and pretend I understand the question and suggest the following for an answer.

Mark's example of 1x2 bricks in two dimensions can be modified to use 1x1 bricks, perhaps at the expense of his constraint on the distance between disjoint blocks. For 3 dimensions, it should be clear that alternating layers of the same 2d pattern of cubes can be arranged so that every point belongs to at most 4 bricks, using bricks of length 3.

I submit without proof (since my multi-dimensional imager is not working at present) that for each such pattern in n dimensions, one can repeat and shift it so that each point is shared by at most (n+2) bricks of length n+1. Simply look at the points shared by most bricks in n dimensions, thicken to the next dimension, then place a brick squarely on top of such a point. It should be apparent that the layer can be shifted so that no point is shared by more than 1 more brick when a dimension is added. If the distance constraint needs larger bricks, scale the sides as needed.

At worst, this idea if wrong will give Mark an opportunity to clarify the situation.

EDIT: Now I understand the problem better. The difficulty with the above is that the constraint of each point on at most n+1 bricks when applied to the unit cube forces the offset to be smaller (1/2^n) as the dimension increases. That suggests to me that the point might need to be different distances from disjoint bricks in each dimension, which in turn suggests a quadratic lower bound for s(n). I will leave this here and update it with any better ideas I obtain. END EDIT.

Gerhard "Ask Me About System Design" Paseman, 2012.07.12

$\endgroup$
8
  • $\begingroup$ Implicit in my understanding is that every point in R^n belongs to at least one brick. If this is not the case, I recommend "decorate regularly" instead of "tessellate". Gerhard "Ask Me About System Design" Paseman, 2012.07.12 $\endgroup$ Jul 12, 2012 at 20:45
  • $\begingroup$ Isn't this just a proof of finiteness of $s(n)$? I am not sure but I think that thinking carefully about the scale factor here is how you get the $2^n$ upper bound. I think it's not too hard to show that the optimal laminated lattice-style construction has $s(n)=O(2^n)$, because every time you go up a dimension you cut the shortest path, at best, in half. $\endgroup$
    – Will Sawin
    Jul 12, 2012 at 20:49
  • $\begingroup$ I may have the wrong picture, but since he is summing lengths, I don't see why the bricks have to have a side longer than 2, so s(n) should still be of order O(n). Anyway, I have faith in Mark's not keeping quiet if I am wrong. Gerhard "Or If I Am Right" Paseman, 2012.07.12 $\endgroup$ Jul 12, 2012 at 21:01
  • 1
    $\begingroup$ Every point belongs to exactly one brick or it is on the boundary of a brick. I do not think it is possible to use 1 by 1 bricks to tile the plane as required. Will is right: in order to get $2^n$: double the previous tessellation (rescale it by 2), then divide $\mathbb{R}^{n+1}$ by layers of thickness 1, each of the layers tessellate as $\mathbb{R}^{n}$ (the doubled tessellation multiplied by the unit interval), then shift the tessellation in odd layers by a half of the brick. The question is whether it is possible to get better bound on the sizes of bricks. $\endgroup$
    – user6976
    Jul 12, 2012 at 21:01
  • $\begingroup$ OK. Can I use 2x2 bricks and still get a linear upper bound eventually? Gerhard "Does Not Fit? Force It!" Paseman, 2012.07.12 $\endgroup$ Jul 12, 2012 at 21:16

Your Answer

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