Hello! I’m Peter!
Blog
-
Polytopes with Lattice Coordinates
Problems 21, 66, and 116 in my Open Problem Collection concern polytopes with lattice coordinates—that is, polygons, polyhedra, or higher-dimensional analogs with vertices the square or triangular grids. (In higher dimensions, I’m most interested in the \(n\)-dimensional integer lattice and the \(n\)-simplex honeycomb).
The \(A334581(4) = 84\) ways to place an equilateral triangle on the tetrahedral grid with four points per side. 
Illustration showing three of the \(\binom{7+2}{4} = 126\) equilateral triangles on a grid with seven points per side. This was largely inspired by one of my favorite mathematical facts: given a triangular grid with \(n\) points per side, you can find exactly \(\binom{n+2}{4}\) equilateral triangles with vertices on the grid. However, it turns out that there isn’t a similarly nice polynomial description of tetrahedra in a tetrahedron or of triangles in a tetrahedron. (Thanks to Anders Kaseorg for his Rust program that computed the number of triangles in all tetrahedra with 1000 or fewer points per side.)
The \(4\)-simplex (the \(4\)-dimensional analog of a triangle or tetrahedron) with \(n-1\) points per side, has a total of \(\binom{n+2}{4}\) points, so there is some correspondence between points in some \(4\)-dimensional polytope, and triangles in the triangular grid. This extends to other analogs of this problem: the number of squares in the square grid is the same as the number of points in a \(4\)-dimensional pyramid.
The \(\binom{n+2}{4}\) equilateral triangles
I put a Javascript applet on my webpage that illustrates a bijection between size-\(4\) subsets of \(n+2\) objects and triangles in the \(n\)-points-per-side grid. You can choose different subsets and see the resulting triangles. (The applet does not work on mobile.)
The solid blue triangle corresponding to the subset \(\{4,5,8,15\} \subseteq \{1,2,\dots,16\}\). 
The two smaller numbers in the subset give the size and orientation of the blue triangle, and the two larger numbers give the position. Polygons with vertices in \(\mathbb{Z}^n\)
This was also inspired by Mathologer video “What does this prove? Some of the most gorgeous visual ‘shrink’ proofs ever invented”, where Burkard Polster visually illustrates that the only regular polygons with vertices in \(\mathbb{Z}^n\) (and thus the \(n\)-simplex honeycomb) are equilateral triangles, squares, and regular hexagons.
Polyhedra with vertices in \(\mathbb{Z}^3\)
There are some surprising examples of polyhedra in the grid, including cubes with no faces parallel to the \(xy\)-, \(xz\)-, or \(yz\)-planes.
An example of a cube from Ionascu and Obando: the convex hull of \(\{(0,3,2),(1,1,4),(2,2,0),(2,5,3),(3,0,2),(3,3,5),(4,4,1),(5,2,3)\}\) While there are lots of polytopes that can be written with vertices in \(\mathbb{Z}^3\), Alaska resident and friend RavenclawPrefect cleverly uses Legendre’s three-square theorem to prove that there’s no way to write the uniform triangular prism this way! However, he provides a cute embedding in \(\mathbb{Z}^5\): the convex hull of $$\scriptsize{\{(0,0,1,0,0),(0,1,0,0,0),(1,0,0,0,0),(0,0,1,1,1),(0,1,0,1,1),(1,0,0,1,1)}\}.$$
Polygons on a “centered \(n\)-gon”
I asked a question on Math Stack Exchange, “When is it possible to find a regular \(k\)-gon in a centered \(n\)-gon“—where “centered \(n\)-gon” refers to the diagram that you get when illustrating central polygonal numbers. These diagrams are one of many possible generalizations of the triangular, square, and centered hexagonal grids. (Although it’s worth noting that the centered triangular grid is different from the ordinary triangular grid.)
If you have any ideas about this, let me know on Twitter or post an answer to the Stack Exchange question above.
A catalog of polytopes and grids
On my OEIS wiki page, I’ve created some tables that show different kinds of polytopes in different kinds of grids. There are quite a number of combinations of polygons/polyhedra and grids that either don’t have an OEIS sequence or that I have been unable to find.
Square Rectangular Centered Square Triangular Centered Hexagonal Equilateral Triangle – – – A000332 A008893 Square A002415 A130684 A006324 – – Regular Hexagon – – – A011779 A000537 Regular Polygon A002415 A130684 A006324 ? A339483* Triangle A045996 A334705 ? ? A241223 Rectangle A085582 A289832 ? – – Right Triangle A077435 ? ? ? A241225 OEIS sequences for polygons on 2-dimensional grids.
Sequences marked with “*” are ones that I’ve authored, cells marked with “—” have no polygons, and cells marked with “?” do not have a corresponding sequence that I know of.Cubic Tetrahedral Octahedral Equilateral Triangle A102698 A334581* A342353* Square A334881* A334891* ? Regular Hexagon A338322* ? ? Regular Polygon A338323* ? ? Triangle ? ? ? Rectangle ? ? ? Right Triangle ? ? ? Regular Tetrahedron A103158 A269747 ? Cube A098928 ? ? Octahedron A178797 ? ? Platonic Solid A338791 ? ? OEIS sequences for polytopes on 3-dimensional grids.
Sequences marked with “*” are ones that I’ve authored, and cells marked with “?” do not have a corresponding sequence that I know of.If you’re interested in working on filling in some of the gaps in this table, I’d love it if you let me now! And if you’d like to collaborate or could use help getting started, send me a message on Twitter!
-
Parity Bitmaps from the OEIS
My friend Alec Jones and I wrote a Python script that takes a two-dimensional sequence in the On-Line Encyclopedia of Integer Sequences and uses it to create a one-bit-per-pixel (1BPP) “parity bitmaps“. The program is simple: it colors a given pixel is black or white depending on whether the corresponding value is even or odd.
A048152 parity bitmap, rescaled through Lospec’s Pixel Art Scaler. 
A207409 parity bitmap. An Unexpected Fractal
We’ve now run the script on over a thousand sequences, but we still both agree on our favorite: the fractal generated by OEIS sequence A279212.
Fill an array by antidiagonals upwards; in the top left cell enter \(a(0)=1\); thereafter, in the \(n\)-th cell, enter the sum of the entries of those earlier cells that can be “seen” from that cell.
Notice that in the images below, increasing the rows and columns by a factor of \(2^n\) seems to increase the “resolution”, because the parity bitmap is self similar at 2x the scale. We still don’t have a good explanation for why we’d expect these images are fractals. If you know, please answer our question about it on Math Stack Exchange. (Alec and I have generated these images up to 16384 × 32768 resolution, roughly 536 megapixels.)
The Construction of the Sequence
The sequence is built up by “antidiagonals”, as shown in the GIF below. In the definition, “seen” means every direction a chess queen can move that already has numbers written down (i.e. north, west, northwest, or southwest). That is, look at all of the positions you can move to, add them all up, write that number in your square, move to the next square, and repeat. (The number in cell \(C\) also counts the number of paths a queen can make from \(C\) to the northwest corner using only N, NW, W, SW moves.)
(Interestingly, but only tangentially related: Code Golf Stack Exchange User flawr noticed that the number of north/west rook walks is related to the number of ways of partitioning a \(1 \times n\) grid into triangles.)
Parity Bitmaps for Other Sequences
It’s worth noting that many sequences are all black, consist of simple repeating patterns, or look like static. However, chess-type constructions, as illustrated by the GIF above, the one above yield images that look like the Sierpiński triangle. (See A132439 and A334017 below, and look at A334016 and A334745 via their OEIS entries.) Look below for a couple other sequences with interesting images too.
I ordered a poster-sized print of the A279212 fractal for Alec, and he framed it in his office.
Alec’s fractal, framed above his fountain pen ink and tasteful books. Some ideas for further exploration:
- See more images I’ve already generated, I have hundreds of images available for download on my Github page.
- Check out my Twitter bot @oeisTriangles that tweets related images.
- Download the Python script to run on other sequences.
- Share any ideas that this sparked for you—I’m @PeterKagey on Twitter!
-
Stacking LEGO Bricks
Back in May, I participated in The Big Lock-Down Math-Off from The Aperiodical. In the Math-Off, I went head-to-head against Colin Beveridge (who has, hands-down, my favorite Twitter handle: @icecolbeveridge). Colin wrote about using generating functions to do combinatorics about Peter Rowlett’s toy Robot Caterpillar. Coincidentally and delightfully, I wrote about using generating functions to do combinatorics about Peter Kagey’s toy LEGOs.
Counting LEGO configurations is a problem dating back to at least 1974, when Jørgen Kirk Kristiansen counted that there are 102,981,500 ways to stack six 2×4 LEGOs of the same color into a tower of height six. According to Søren Eilers, Jørgen undercounted by 4!
One of the 102,981,504 ways to stack six 2×4 LEGOs into a tower of height six. In my Math-Off piece, I wrote about a fact that I learned from Math Stack Exchange user N. Shales—a fact that may be my (and Doron Zeilberger’s) favorite in all of mathematics: there are exactly \(3^{n-1}\) ways to make a tower out of \(1 \times 2\) LEGO bricks following some simple and natural rules. Despite this simple formula, the simplest known proof is relatively complicated and uses some graduate-level combinatorial machinery.
The Rules
- The bricks must lie in a single plane.
- No brick can be directly on top of any other.
- The bottom layer must be a continuous strip.
- Every brick that’s not on the bottom layer must have at least one brick below it.
An tower that violates rule 1. 
A tower that violates rule 2. 
A tower that violates rule 3. 
A tower that violates rule 4. Gouyou-Beauchamps and Viennot first proved this result in their 1988 statistical mechanics paper, but the nicest proof that I know of can be found in Miklós Bóna’s Handbook of Enumerative Combinatorics (page 26). Bóna’s proof decomposes the stacks of blocks in a clever way and then uses a bit of generating function magic.
Other rules
In preparation for the Math-Off piece, I asked a question on Math Stack Exchange about counting the number of towers without Rule 2. The user joriki provided a small and delightful modification of Bóna’s proof that proves that there are \(4^{n-1}\) towers if only rules 1, 3, and 4 are followed.
It might also be interesting to consider the 14 other subsets of the rules. I encourage you to compute the number of corresponding towers and add any new sequences to the On-Line Encyclopedia of Integer Sequences. If you do so, please let me know! And I’d be happy to work with you if you’d like to contribute to the OEIS but don’t know how to get started.
Another natural question to ask: How many different towers can you build out of \(n\) bricks if you consider mirror images to be the same? In the example above with the red bricks, there are six different towers, because there are three pairs of mirror images. By Burnside’s Lemma (or a simpler combinatorial argument) this is equivalent to counting the number of symmetric brick stacks. If there are \(s(n)\) symmetric towers with \(n\) bricks, then there are \(\displaystyle \frac 12 (3^{n-1}+s(n))\) towers. For \(n = 4\), there are three such towers, shown below in blue.
I asked about this function on Math Stack Exchange and wrote a naive Haskell program to compute the number of symmetric towers consisting of \(n \leq 19\) bricks, which I added to the OEIS as sequence A320314. OEIS contributor Andrew Howroyd impressively extended the sequence by 21 more terms. I also added sequence \(A264746 = \frac 12 (3^{n-1}+A320314(n))\), which counts towers up to reflection, and A333650, which is a table that gives the number of towers with \(n\) bricks and height \(k\).
Stacking Ordinary Bricks
It is also interesting to count the number of (stable) towers that can be made out of ordinary bricks without any sort of mortar. I asked on Math Stack Exchange for a combinatorial rule for determining when a stack of ordinary bricks is stable. MSE user Jens commented that this problem is hard, and pointed to the OEIS sequence A168368 and the paper “Maximum Overhang” by Mike Paterson, Yuval Peres, Mikkel Thorup, Peter Winkler, and Uri Zwick, which provides a surprising example of a tower that one might expect to be stable, but in fact is not.
A surprising example of an unstable tower.
See Figure 5 of the Paterson, Peres, Thorup, Winkler, and Zwick paper.I’d still like to find a combinatorial rule, or implement a small physics engine, to determine when a stack of bricks is stable.
These problems and some generalizations can be found in Problem 33 of my Open Problem Collection. If you’d like to collaborate on any of these problems, let me know on Twitter. If you find yourself working on your own, I’d love for you to keep me updated with your progress!
(The graphics of LEGO bricks were rendered using the impressive and free LEGO Studio from BrickLink.)
