Polyomino Loops
A neat mathematical idea I found while doodling.
A while ago I wrote about the prescriptive power of maths education, and I wished there was more opportunity for students to be playful and invent ideas of their own, even if they aren’t new or significant. In this post, I’ll share with you an idea of mine, conceived years ago but not properly written down until now, in hopes that you may find some joy in playing with it yourself.
Inspiration!
No mathematical idea comes out of thin air (though some textbooks¹ certainly make stuff seem this way). The inspiration for my idea comes from one day back in high school. I was bored in class and started doodling in my notes. I used the same paper then as I do now, paper with a square grid of dots printed on it. The dots served as a nice guide for my doodle of choice that day, a type of loopy rectangle that reminded me of Celtic knots, or the patterns of an ornate tapestry. I noticed that rectangles of different sizes behaved differently. Some required multiple loops to fill in, while others could be drawn with one long, continuous stroke — those were my favorites.
Soon I had a pretty strong conjecture about when rectangles could be filled in with one loop or not, so I moved on to exploring non-rectangular shapes. Some of those shapes were also singly-looped, but it was much harder to figure out how many loops they would have without actually drawing them.
“There’s some interesting maths going on here,” I thought.²
Formalization!
It’s time to turn vague doodles into precise definitions. Instead of thinking about a grid of dots, I figured it would be better to define things in terms of polyominos, a well-established type of polygon. If P is a polyomino, then a loop of P is a shape drawn on top of P according to the following procedure. Start your pen at the midpoint of a side of a cell of P. Begin drawing a line at a 45-degree angle. If you hit the boundary of P, then “reflect” off the boundary at a 45-degree angle and keep going. Eventually your pen will get back to where you started (why?), and this completes one loop of P.
Two loops are the same if they look the same after completion; the place where you start and the direction you draw in doesn’t matter. The loop number of P is the number of loops of P (duh), and it is written L(P). A polyomino is prime if it has loop number 1.
Conjectures!
Now that we have a precise language to describe things, I’ll present a few conjectures I’m pretty sure are true, with graphical evidence. Proofs are, of course, left to the reader ;)
Loop number for rectangles. If P is an n-by-m rectangular polyomino, then L(P) = gcd(n, m). I’m pretty sure this fact can be proven with some modular arithmetic, and a result of a similar flavor (known since 1991) appears in this Wolfram MathWorld entry.
Scalar multiplication. Let P be a polyomino, and let k be a positive integer. Define kP as the polyomino constructed by “scaling by a factor of k,” i.e., every cell of P gets replaced by a k-by-k square of cells. Then L(kP) = kL(P). This fact seems really nice, so I feel like it ought to be true. It might be proven by arguing that you can “wiggle” a loop a little bit to produce a new loop.
Prime decomposition. Now here’s a spicy one. Suppose P is a polyomino with loops a_1, a_2, …, a_n. Then you can separate the boundary of P into parts based on what loop they touch, and for every i = 1, …, n, the pieces that touch a_i can be put together to form a new polyomino with loop number 1.
This produces a unique set of n prime polyominos that can be thought of as a prime decomposition of P.
Questions?
Finally, here are three big questions I do not know how to answer.
Polyomino multiplication? There’s a natural way to define multiplying a polyomino by an integer, as we have seen. There also seems to be a natural way to decompose a polyomino into primes. My naming convention suggests that there ought to be a nice way to define the product PQ, where P and Q are both polyominos, such that the prime decomposition of PQ is the union of the prime decompositions of P and Q. Does such an operation exist for all P and Q? Does it only exist for certain P and Q? Is PQ even unique? Or perhaps unique up to some notion of equivalence?
Behavior of L(P)? What’s the distribution of L(P) over all polyominos P with n cells?
Loop number for general polyominos? The question that started it all. For a general (possibly non-rectangular) polyomino P, is there a nice way to determine L(P) without explicitly drawing the loops of P? I’m not sure if this problem has a satisfactory solution out there. On the one hand, the quantity L(P) seems very hard to systematically compute, but on the other hand, there are results like Kirchhoff’s theorem³, which gives a really nice way to determine a similar quantity (the number of spanning trees of a graph).
Further reading!
When doing some research for this post I came across a book called Lunda Geometry: Mirror Curves, Designs, Knots, Polyominos, Patterns, Symmetries by Paulus Gerdes. It analyzes traditional South African patterns that are similar to the polyomino loops I’ve discussed here, but richer and more complex. Gerdes appears to ask some really fascinating questions and prove (actually prove, unlike me) some really neat theorems. I might give it a read some time; you should too if you found any of this stuff interesting! And if you make any progress on my conjectures or questions — keep me in the loop :)
- Teaching the tensor product as a “formal linear combination of things” is a big offender in my opinion. This is why you should actually care about tensor products.
- As if I thought in a British accent in high school.
- Shoutout to my friend Heather for reminding me of this theorem when we discussed polyomino loops at Gail’s Bakery :)