I made a movie recently for my advisor. The movie is so pretty, that I thought I’d share it here: may I present to you randomly drawn dots, where two dots are the same color when they touch!

I’ll be a bit more explicit: a dot is drawn at a random location; if it does not overlap any previous dots, it gets a new color. Otherwise, the dot takes the color of the component it touches. Sometimes a new dot connects many components, and in this case, the new component takes on the color of the largest among the old components.

There’s a lot of neat questions to be asked about such a process: for instance, after drawing n dots, how many components should we expect to see? As you can see in the movie, when you draw only a few dots, most of those dots are isolated and have their own color; but after drawing a ridiculously large number of dots, they are all connected and the same color. And inbetween, something more interesting happens.

Here’s an example of “something more interesting” taken from a larger picture than the above movie:

I’ll briefly introduce the Lights Out puzzle: the game is played on an n-by-n grid of buttons which, when pressed, toggle between a lit and unlit state. The twist is that toggling a light also toggles the state of its neighbors (above, below, right, left—although, on the boundary, lights have fewer neighbors). All the buttons are lit when the game begins, and the goal is to turn all the lights off.

There are two key observations:

• toggling a light twice amounts to doing nothing,
• toggling light $A$ and then light $B$ has the same effect as toggling $B$ and then toggling $A$.

As a result, the order in which we press the buttons is irrelevant. So to solve the n-by-n puzzle, we just need to know whether a button needs to be pressed. My old website had some pictures I made showing solutions for boards of various sizes—pictures where a white pixel meant “press” and a black pixel meant “don’t press.” I assembled these pictures into a video, showing solutions to the Lights Out puzzle for $n \leq 200$:

For as cool as that looks, there’s not much to be discovered (as far as I can tell) from watching these frames flash by. But it does look like about half the buttons have to be pressed to solve the puzzle: why is that?

The still frames of the movie are available here as PNGs in a zipped archive. Here is a solution to the 400-by-400 board:

Finding that solution involved row-reducing a $(400 \cdot 400 + 1)$-by-$400 \cdot 400$ matrix—that’s a matrix with over 25 billion entries. On the other hand, each entry is one bit, so that matrix fits (not coincidentally) in 3 gigabytes of memory. One could surely do better, considering how sparse the matrix is: perhaps we could have a little contest for solving very large Lights Out games.

Besides the fact that all these pictures look awesome, Lights Out is a neat example to motivate some linear algebra over a finite field. It illustrates how satisfying an “easy” local condition (each light must be turned off) might require a globally complicated solution—a lesson for mathematics and for life!

I gave a talk in the Farb and Friends Student Seminar (back in March!) on:

Davis, Michael W. and Januszkiewicz, Tadeusz. Hyperbolization of polyhedra. J. Differential Geom. 1991. 347–388. MR.

This is an awesome paper—well-worth a few words on every blog!

The construction is way easier than you might think. The ingredients:

• A model space $X$ with a map $f : X \to \Delta^n$
• Any simplicial complex $K$ with a nondegenerate (edge-non-collapsing) map $K \to \Delta^n$ (if having a map to $\Delta^n$ seems like a bother, note that the barycentric subdivision $K’$ comes with a map to $\Delta^n$ for free).

Let $X_J = f^{-1}(J)$ for $J$ a subcomplex of $\Delta^n$; we think of this as decomposing $X$ into pieces resembling a simplex.

Now the construction is easy: replace each simplex in $K$ with a corresponding piece of $X$. Or more formally, build the fiber product of $X$ and $|K|$ over $\Delta^n$; this fiber product is denoted by $X \tilde{\Delta} K$ in the paper. From this, we get a natural map $f_K : X \tilde{\Delta} K \to K$.

The vague upshot is this: features of $X$ translate into features of $X \tilde{\Delta} K$, while nonetheless preserving features of $K$. Here are a couple of examples of how assumptions on $X$ lead to consequence for $X \tilde{\Delta} K$.

• If $X$ is path-connected, and for each codimension 1 face $\alpha$ of $\Delta^n$, we have $X_{\alpha} \neq \varnothing$, then $\pi_1(f_K) : \pi_1(X \tilde{\Delta} K) \to \pi_1(K)$ is a surjection.
• If $X$ and $K$ are PL-manifolds, and $\dim X_J = \dim J$, and $\partial X_J = X_{\partial J}$, then $X \tilde{\Delta} K$ is a PL-manifold.

The Romans (among others!) wrote in wax with a stylus; the wax was embedded in boards, which were bound together in pairs. If a Roman were to place clay between these boards, could they make a copy of their wax tablet in the clay?

It strikes me as remarkable that coins were minted so long before books were printed—though I guess the motivation behind minting coins and printing books are rather different.