# What is the complete classification of the uniform tesselations?

A uniform tesselation is a set of regular polygons in the plane that meet edge to edge, such that any two vertices are related by a symmetry of the whole figure. Regular polygons include self-intersecting star polygons.

Wikipedia gives 11 convex and 14 star tesselations (as well as some others with infinite polygons, let's not count these for the moment). They cite Grünbaum, which in turn cites Coxeter. However, neither of them claim to have a complete set.

I tried to solve this problem myself, and started by considering the case of a tiling with a (subgroup of the) p4m symmetry group. After a whole day, I made some observations:

1. If two pairs of two vertices of a regular polygon in this tesselation are related by a translation (that's a mouthful), their angle must be a multiple of $$\frac{\pi}{4}$$. This is a consequence of the fact that angles in an integer lattice have rational tangents and Niven's Theorem for tangents.
2. At most $$12$$ pairs of vertices in a regular polygon in this tiling may be related by a translation. This is a corollary of 1. and of my conjecture that only regular polygons with $$6n$$ sides have sides/diagonals with a rational ratio, since these translations must have one of eight directions, and there can only be three vectors with the same or opposite direction (lest two of these have an irrational ratio). $$12$$ can be strengthened into $$10$$ since no two translation vectors of the same length can have an angle of $$45^{\circ}$$ (since lattice regular octagons don't exist). Better bounds can be made for specific $$n$$-gons (based on whether $$n$$ is a multiple of $$2$$, $$4$$ or $$6$$).
3. Only regular polygons with $$3$$, $$4$$, $$5$$, $$6$$, $$7$$, $$8$$, $$9$$, $$10$$ or $$12$$ sides can appear. Consequence of 2., the pigeonhole principle (between any nine vertices, two are related by a translation), and some casework.
4. Every vertex may only be connected to other $$17$$. Consequence of 2., since the connected vertices must be embedded in a $$2520$$-gon.
5. If a regular $$p$$-gon appears with $$p\ge3$$ prime, there must be at least $$\frac{p+1}{2}$$ of them per vertex. This is because $$\frac{p+1}{2}$$ of the vertices of the polygon must be mutually related by rotations, but none of those rotations can preserve the $$p$$-gon (since the symmetries of a $$p$$-gon for $$p$$ odd aren't included in p4m).

This reduces the number of cases to a finite, but huge amount. I couldn't get any further, and that didn't even take into account the other possible symmetry groups (which I hope can be done in an analogous manner).

I believe that 3. and 4. might be considerably strengthened. All of the listed tilings with symmetry group (a subgroup of) p4m use only triangles, squares and octagons/octagrams. Likewise, the rest of the tilings use only these plus hexagons and dodecagons/dodecagrams. And none of these tilings have vertices connected to more than $$6$$ other ones. But proving these restrictions (which would bring the problem to a manageable scale) will probably require an approach distinct to my own.

• By the way, if my approach can be fixed, I reckon the bound to be improved is the bound in 4. If we did change $17$ to $6$, this would leave only $\frac{20^6}{2}=32000000$ cases (counting retrograde faces), a still huge but computationally manageable amount. – ViHdzP Apr 6 '20 at 5:46
• Also, $16$-gons can be discarded by checking that we could only have 8 pairs of vertices related by a translation, but however we arranged them, we'd create a non-discrete translation group. – ViHdzP Apr 6 '20 at 16:02

A complete proof can be found in "The Symmetries of Things" by Conway, Burgiel, and Goodman-Strauss, Chapter 19 ("Archimedean tilings", which is their term for "uniform tilings"). There are 11 Archimedean tessellations of finite, convex polygons. Table 19.1 has the complete list.

• I appreciate the reference, but that deals only with tesselations with convex faces and vertex figures, the first 11 examples I mentioned. I’m considering a strictly greater set of objects. – ViHdzP Apr 6 '20 at 2:41

The article Tiling with Regular Star Polygons by Joseph Myers presents two uniform edge-to-edge tilings by regular star-polygons which were not included in Grünbaum and Shephard's list in Tilings and Patterns, section 2.5. This makes a total of 23 uniform tilings by regular star polygons and convex polygons, and 11 uniform tilings by regular convex polygons only.

Grünbaum and Shephard broke them down into 4 in which every corner of a tile is a vertex of the tiling, and 17 in which not all corners are vertices. Myers breaks them down differently, into 6 in which some dent is a vertex, and 17 in which no dent is a vertex. His two new tilings are in the latter group, and two of Grünbaum's 17 (the ones in Figure 2.5.4(c) and (i)) are reclassified to the former group.

Myers's article also presents a proof of completeness—or rather "an outline of how it may be verified", with many details left to the reader—which I have not gone through myself.

• The linked article deals with star polygons in the traditional sense, not in the self-intersecting sense. Still a nice read, so thanks for that. – ViHdzP Apr 7 '20 at 2:57
• At first glance the tilings in that paper did not seem uniform to me, but that is because it only considers points where 3 or more tiles meet to be vertices. So for example a square tile could have only 2 vertices if its other two corners were inside dents of a star tile. – Jaap Scherphuis Apr 9 '20 at 12:18