6

This is a question I came up with while playing tetris, not any homework assignment. I tried thinking about it myself but it seems very complicated, and so I thought it would be a good idea to post the question here.

I do not have the precise language to formulate my question, so I'll begin attempting to explain the question by first looking at the 2d case.

Consider the 2d grid, whose vertices are Z^2, considering of squares of unit length. There are connected shapes in this grid, like the shapes you get in tetris. Some of those shapes, however, are special, in that under any 2 different isometries of the grid, you get 2 different shapes (can't translate one to coincide with the other). My question concerns the smallest such shape. In 2d it's quite easy, since there aren't a lot of possibilities - it's the L shape with one longer side: L shape

The following shape, however, is not special: shape 2 since you can reflect it along the vertical axis and get the same shape.

And so my question is if we move on to 3 dimensions or higher, what is the minimal special shape (consisting of least number of blocks)? Is there anything known about the sequence of the size of the smallest special shape in n dimensions?

wilkersmon
  • 798
  • 6
  • 18
  • 3
    This is a nice and original question! Generalizing the Tetris L block to a shape in $n \geq 2$ dimensions with orthogonal "legs" of length $k + 1$ in the $k$th direction (say, with oriented right-hand orientation) gives an upper bound of $\frac{1}{2} n (n + 1) + 1$, which is $1$ greater than the $n$th triangular number. – Travis Willse Feb 20 '19 at 22:50

1 Answers1

1

For $n\ge 6$, it takes $n+1$ blocks - see part 2 for the construction. For $2\le n\le 5$, it takes $n+2$ blocks. The $n+2$-block shape that works:

Part 1

Label the blocks based on their centers, placed at lattice points. The shape that does it has blocks at $(-1,0,0,\dots)$, $(0,0,0,\dots)$, $(1,0,0,\dots)$, $(1,1,0,\dots)$, $(1,1,1,\dots)$, and so on until we fill in all of the coordinates with ones.

Why does this work? We prove it inductively, taking the $2$-dimensional L-shape as the base case and showing that an isometry (of any dimension) that fixes the shape must fix each individual block. Our shape is a "worm" with each block connected to two others except for the ends which are only connected to one block each. The two ends are also distinguishable; only one is part of a three-block straight line. Call that end the "head" and the end that isn't part of such a block the tail.

So then, suppose an isometry maps the shape to itself. Since numbers of connections stay the same, the ends must map to the ends. Since the ends are distinguishable, the head must map to the head and the tail must map to the tail. Cut off the tail block, reducing us to the shape with one less dimension. By the inductive hypothesis, the isometry fixes each block of the reduced shape. Add the fixed tail block back in, and the isometry fixes all of the blocks.

Finally, take the $n$-dimensional shape and restrict our isometry to an isometry of $\mathbb{R}^n$. The vector differences between centers of blocks span $\mathbb{R}^n$, so an isometry that fixes every block fixes a spanning set, and must fix all of $\mathbb{R}^n$. Done.

Part 2

While the above shape always works, it isn't necessarily minimal. To pin down the exact minimum, first note that any shape with $n$ or fewer blocks in it fits in $n-1$ or fewer dimensions; each new block is connected to a previous block, and those $\le n-1$ vectors don't span the full space. Then we just have to take an isometry that fixes all of the dimensions the shape is in, and reflects in one of the other dimensions. Therefore, the minimum is always at least $n+1$.

For $n\ge 6$, the minimum is equal to $n+1$. The seven blocks of the six-dimensional shape: $(0,0,0,0,0,0)$, $(1,0,0,0,0,0)$, $(0,1,0,0,0,0)$, $(0,1,1,0,0,0)$, $(0,0,0,1,0,0)$, $(0,0,0,1,1,0)$, $(0,0,0,1,1,1)$. We have a base block with three "tails" of different lengths coming from it, and that base block is the only block connected to more than two other blocks. Since the tails have different lengths, they're distinguishable and any isometry must fix each tail. Like our $n+2$ example, this uses all the dimensions, and thus any isometry that fixes all the blocks fixes everything.
For $n>6$, we extend this shape by adding more blocks to the longest tail, up to $(0,0,0,1,1,1,\dots,1)$. All the key properties remain, and the shape has no nontrivial isometries.

Part 3

That leaves $n\le 5$. To get a slightly better understanding, I'll turn to graph theory here; if we take the blocks as vertices and adjacent connections as edges, we have a graph. A shape of $n+1$ blocks that uses all dimensions must have its graph be a tree; the $n$ edges are linearly independent, and there are no cycles

Now, any graph automorphism of this tree induces an isometry of the shape. We will now show that any tree on three to six vertices has nontrivial automorphisms, and thus any $n$-dimensional shape of $n+1$ blocks has a nontrivial isometry for $2\le n\le 5$.

Three vertices: There's only one tree up to automorphism. Swapping the two ends is an automorphism.

Four vertices: There are two trees up to automorphism:

Four-vertex trees

Both of them have nontrivial automorphisms; reverse the order for the first, shuffle the leaves for the second.

Five vertices: There are three trees up to automorphism:

Five-vertex trees

All have nontrivial automorphisms, easily visualized.

Six vertices: There are six trees up to automorphism:

Six-vertex trees

Once again, all have nontrivial automorphisms; swapping tails of equal length always works.

jmerry
  • 19,403