Yikes, four dimensions. As if visualizing a three-dimensional
space of colored and uncolored points wasn’t complicated enough. In the last
post, we showed that a 3D staircase coloring works as an optimal solution for
the Rose Problems we were discussing, but now we have to try and extend that to
higher dimensions. Luckily, we happen to live in a four-dimensional world: three
spatial dimensions and one temporal dimension, and I find visualizations in
this mixed space are actually not that bad.
Let me just start with a simple example to introduce the
idea of thinking in this 4D space. I’m going to call it (3+1)space, because it’s
three dimensions of one type and one dimension of another, as opposed to a true
4D space, with all four dimensions of the same type.
Imagine four blocks in a row horizontally across a table.
Now imagine that you pick them up and lay them on the table so they’re oriented
vertically along it. Or in a stack on top of each other. It doesn’t take much
mental effort to view those changes as a “rotation”. They were along one axis,
or dimension, and you aligned them with another axis, but kept the object
itself very much the same. Now, imagine rotating the four blocks along the axis
of time. You’d see one block, and then it would be replaced with the next one,
and the next one, and the last one, and then there would be nothing.
These three shapes are the same, two along a spatial
dimension, and one along a temporal dimension. There’s a lot of fun you can
have with this, but perhaps we’ll talk about that another time. For now, let’s
return to our transformation of the 3D staircases to 4D. We’re not rotating
anything (yet), but you will need that (3+1)D visualization skill to picture
the next part.
Let’s say we’re in four dimensions, and our rule is “two
colored points in a row is not allowed”. The two dimensional solution to that
is a 2D staircase that looks like this:
And the 3D solution is just layers of that solution,
staggered so they don’t overlap. The (3+1)D solution will just be that 3D
solution, swapping which dots are colored every unit of time!
We can easily verify this, too! We know that there will
never be two in a row along any of the spatial directions, because that was
point of the 3D staircase proof. Now, if we focus on a single point in time,
there will never be two consecutive moments when it’s colored. And the
wonderful thing about our (3+1)D system is that it’s completely equivalent to a
4D system. It’s a lot easier to visualize, but any rules or discoveries here
apply there, too! Therefore, the 4D staircase works!
It’s pretty easy to show that 4D staircases work for
other similar rules, too. Here’s animations of the “three-in-a-row” and “four-in-a-row”
rules, if you’re still skeptical. I can’t show all four dimensions because of
the limitations of computer screens, but you get the picture.
I find these mesmerizing. It’s “perfect”, in a way, how
the length, width, and temporal height of the rows of colored points are all
the same. Try staring at one point to see the temporal height, and you'll notice that it's the same pattern as the vertical and horizontal!
And now, the jump to N dimensions. The technique I’ll be
using is based on the imagining 4D as (3+1)D discussion earlier, but it has a
much wider scope. I can perform an
easy-to-visualize inductive proof on the number of dimensions by using the
following transformation: N dimensions à N dimensions + 1
temporal dimension à N+1 dimensions.
Let me break down the technique. Let’s say we have some N
dimensional space on which something works, like our staircase configuration. I
may not be able to visualize this space, but I can visualize a single point,
line, or plane of this space varying in time. If I can verify that the rule
works, I can say that the new space has N + 1 dimensions, and do the same thing
again to inductively prove that it works for any number of dimensions. This
technique isn’t exactly a revelation in terms of the simple induction behind
it, but it is excellent for helping me (and hopefully you) visualize what’s
going on. Math is at its best when we have that intuitive understanding of what’s
happening, not just a surface level knowledge of what technique to use.
And there we have it. It doesn’t matter what dimension we
start in; we can show that the temporal direction in any staircase will work if
the space is staggered, so we have now shown, that for any rule of the form “X
colored points in a row is not allowed” on any standard N-dimensional space, we
have a solution for the greatest percentage of that space you can cover. The
solution is given by the Staircase coloring specific to (X, N), and the percentage
of the space covered is (X – 1) / X.
That’s… a big deal. There’s a lot more to figure out
here, but we’ve conclusively knocked out a lot of cases of a huge problem. More
on that next time.
