An Orthogonal Mate for a Latin Square Based on an Asymmetric Tile, II

Year: 2024 Authors: Stephen M. Gagola, Jr.

Core claim

An arbitrary curved asymmetric tile can generate an 8 by 8 Latin square with an orthogonal mate.

Topics

Latin squares, orthogonal mates, asymmetric tiles, tile-based puzzles

Domains

combinatorics, finite algebra, orthomorphisms, Latin squares, mathematical art, tiling, pattern design, Escher-style construction

Methods

geometric tile construction, counting arguments, algebraic isotopy, color-based illustration

Media

curved tiles, colored puzzle pieces, Latin square diagrams

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2024 Conference Proceedings

An Orthogonal Mate for a Latin Square Based on an Asymmetric Tile, II

Stephen M. Gagola, Jr.

Department of Mathematics, Kent State University, Kent, Ohio, USA; gagola@math.kent.edu

Abstract

We describe here the second of two asymmetric tiles created by the artist Peter Raedschelders in his construction of an 8 by 8 Latin square. The symbols of the square are the eight distinct orientations of the tile, and these fit snugly together in the style of M. C. Escher to form the Latin square. Unlike his first tile which uses even and odd functions to describe the sides of the tile, the artist’s second tile may be constructed from an arbitrary (but reasonable) curve appearing on one side of the tile, with the other sides being determined from this. By using some algebra and colors, we illustrate that the resulting Latin square has an orthogonal mate.

Latin Squares

A Latin square is an $n$ by $n$ table consisting of $n$ distinct symbols appearing in each of its rows and columns. Although these symbols usually are numbers or letters, other symbols may be used as in Margaret Kepner’s collection [4] of Latin squares of size 7 by 7.

Two Latin squares of the same size (perhaps using different symbols) are orthogonal if, whenever the squares are super-imposed, no duplication appears among the various pairs of symbols. A concrete example of this appears in Figure 5 where there are two overlapping Latin squares. Ignoring colors, one Latin square consists of eight distinct shapes appearing in each row and column. However, ignoring shapes and only considering colors, each row and column contains eight distinct colors. Orthogonality here simply means that tiles receiving the same color are all oriented differently.

Construction of the Tile

The first tile that Peter Raedschelders used in constructing his Latin square had two identical odd functions appearing on adjacent sides of the tile, and two even functions (one being the negative of the other) appearing on the remaining sides. The Latin square resulting from that tile, including its algebraic properties and the construction of an orthogonal mate, was analyzed in [2]. The tile considered here however will instead have on one side an arbitrary continuous curve that has no symmetry, and the remaining sides will be determined by it. The curve itself must satisfy some mild constraints but it could have vertical lines or even double back on itself. An example of a Latin square built from such a tile appears in [3] as well as in Figure 4.

Starting with the top of a square, plot the graph of a continuous curve from one corner to the other (which we identify with the points $(-1,0)$ and $(1,0)$ on the $x$ -axis). To guarantee that a tile can be constructed, we also require that the curve lie within the “ ${\ell }_1$ -disk”: $|x|+|y|\le 1$ . The graph of the reflection of this curve through the origin is placed on both the left and right sides of the square (equivalently, rotate the top curve counterclockwise $90^{\circ }$ about its right endpoint, and clockwise $90^{\circ }$ about its left endpoint). Finally, the curve at the bottom is obtained by reflecting the top curve through its $y$ -axis, and then rotating it around $180^{\circ }$ degrees to fit on the bottom. (Equivalently, the bottom curve is the reflection of the top curve through a horizontal axis passing through the tile’s center.) Figure 1 shows an example of a tile constructed in this way, as well as its sides, unfolded, to its right.

Gagola Jr.

Notice that the top side of the tile fits snugly against both the right and left side of a second congruent tile without flipping over, while the bottom side fits snugly after flipping. A key property of these tiles is that when three are fitted together non-colinearly then a fourth tile will fit uniquely forming a 2 by 2 configuration.

Figure 1: Anatomy of a tile. Note the position of the principal axis.

Included in the figure is the tile’s “Principal Axis”. Its defining property is that it separates the two opposite sides of the tile whose curves become congruent by a $180^{\circ }$ degree rotation of the tile. The principal axis is not an axis of symmetry, but it does have some interesting features. Notice that when two tiles are fitted together, their principal axes are orthogonal (perpendicular) to each other. Moreover, when the two tiles are both flipped along their respective principal axes, the resulting tiles still fit snugly together. A consequence of this is that when all the tiles in a Latin square are flipped in this manner, the “puzzle pieces” still fit snugly together and a new Latin square emerges! (Flipping across the principal axis is not the only transformation of the tiles that works like this. See the last paragraph of the section below on Other Isotopies and Symmetries.)

Using the curve on the right or left side as the new top side to construct a tile according to the scheme above will produce a tile that is not congruent to the original tile even though it uses the same curves along its sides as the original tile. So tiles constructed according to the scheme above actually come in dual pairs. (Using other sides for the new top side, even flipping the tile over, will not produce any new tiles.)

The requirement that the curve should lie in the ${\ell }_1$ -disk $|x|+|y|\le 1$ guarantees that a tile, and its dual, exists. But the requirement does not have to be strictly enforced. However, there is the risk that even if a tile may be constructed, its dual may not be constructible. Such a tile is called a “rogue” tile. Figure 2 shows the dual of the tile constructed above, as well as a tile that can be thought of as a caricature of the original tile. It is a rogue.

Figure 2: A dual tile and a rogue, with principal axes shown.

Geometry, Combinatorics, and some Counting

After constructing several congruent copies of the tile described in the last section, piecing them together in various ways to form a puzzle (say 8 by 8) becomes a problem in geometry and combinatorics.

Consider first constructing the top row of an 8 by 8 puzzle. After choosing the first piece to place at the left (there are 8 choices), there are only 2 ways to fit the next and succeeding pieces. Therefore, there are $8\cdot 2^7=1024$ possible eight-element top rows to build. Similarly, starting down from the first piece again,

An Orthogonal Mate for a Latin Square Based on an Asymmetric Tile, II

there are $2^7=128$ ways to complete an eight-element column on the left side. By a remark made in the previous section, there is now only one way to fit a tile in row 2, column 2 (and then row 2, column 3, etc.). In other words, a puzzle is uniquely determined by its top and left sides, and there are $1024\cdot 128=131072$ puzzles in all. Of course most of these aren’t Latin squares.

For a Latin square to emerge it is necessary that the top row, as well as the left column, consist of eight distinct orientations of the tile, and it isn’t clear at this point that this condition is sufficient.

We return to the problem of constructing the top row, but we make sure all orientations are distinct. As before, there are 8 choices for the first piece. The two choices for the second piece to fit are necessarily different from the first (principal axes are orthogonal), and even though the third piece to fit has a principal axis parallel to the first, both choices for this third piece are still necessarily different from the first. This pattern persists: pieces differing by 2 units are necessarily oriented differently, even though their principal axes are parallel. Therefore, the two choices for position 4 are necessarily different from the tile occupying position 2. At this point the situation becomes rigid. One of the two tiles that can fit in position 5 already appears in the first position. Moreover, the left and right sides of these two tiles exactly match. This pattern also persists: tiles with matching left and right sides may be paired off, and in any row of 8 tiles in which all orientations are distinct, two tiles of a pair will always be four units apart. The entire row therefore is determined by the first four pieces, and there are $8\cdot 2^3=64$ possible rows. Figure 3 illustrates one of these.

Figure 3: The distinct orientations of eight congruent tiles. These may be fitted together to form a row of a Latin square.

The remarks made about rows in the last paragraph also apply to columns, the only difference being that matching pairs of tiles now are determined by top and bottom sides instead. So in building a Latin square, once the top row is chosen there are $2^3=8$ ways to complete the left side, and this means that there are at most $64\cdot 8=512$ Latin squares possible.

There is one further remark to make about these special eight-element rows: the last tile in position 8 may be removed and placed on the left side of the tile in position 1 where it will fit snugly. Therefore these rows can be cyclically rotated. Because these rows necessarily occur in Latin squares, the columns of any Latin square may be cyclically rotated as well, producing new Latin squares. More is possible: since tiles appearing 4 units apart have the same left and right sides, two columns of any Latin square differing by 4 units may be exchanged! These special rearrangements (permutations really) of columns of Latin squares also apply to the rows of any Latin square as well.

From these considerations, and the existence of a single Latin square, it follows that the upper estimate of 512 Latin squares is exact! Starting from a Latin square, cyclically rotate columns until a desired piece appears in position 1 of the first row. Then to get the desired piece in position 2, if it is not already there, exchange columns 2 and 6. Exchanging columns 3 and 7, as well as 4 and 8 if needed now produces in the top row any one of the 64 special rows containing differently oriented tiles. Once this is done, the first column may now be rearranged by exchanging (as needed) rows 2 and 6, 3 and 7, and 4 and 8. Therefore, starting from a single Latin square, at least 512 Latin squares may be produced by using allowable permutations of rows and columns. The bound of 512 is exact.

This is a good place to introduce some notation. We define two Latin squares, say $L_1$ and $L_2$ , to be isotopic if $L_1$ can be transformed into $L_2$ by permuting rows, columns, and permuting or even changing the symbols. If ${\sigma }_1,{\sigma }_2$ , and ${\sigma }_3$ are the permutations of the rows, columns, and bijection of symbols used (respectively), the triple $[{\sigma }_1,{\sigma }_2,{\sigma }_3]$ is called an isotopy from $L_1$ to $L_2$ .

Gagola Jr.

Figure 4: One of eight Latin squares having $90^{\circ }$ rotational symmetry based on orientations of an asymmetric tile. Rows and columns are indexed by elements of the group $C_4\times C_2$ .

Symmetries (Autotopies)

In the previous section we saw that any two Latin squares based on the tiles that we used were isotopic. In fact the isotopy had the form $[{\sigma }_1,{\sigma }_2,1]$ , where 1 denotes the identity permutation applied to the symbols (tiles): tiles retained their orientations as rows and columns are permuted. These isotopies are called proper. If $\varphi$ is the transformation sending a tile to its flipped version along its principal axis, then $[1,1,\varphi ]$ is an example of an isotopy whose third coordinate is nontrivial.

An isotopy $[{\sigma }_1,{\sigma }_2,{\sigma }_3]$ that sends a Latin square back to itself is called an autotopy (proper autotopy if ${\sigma }_3=1$ ), and these may be “multiplied componentwise”:

Under this binary operation, the autotopies form a group (the proper autotopies forming a subgroup).

If ${\sigma }_2$ is an allowable permutation applied to the columns of the Latin square of Figure 4, it might be possible to restore the resulting square back to its original by applying an appropriate permutation ${\sigma }_1$ to its rows. But there is no guarantee of this. However, if we can recover the original Latin square by an allowable permutation of its rows, say ${\sigma }_1$ , then $[{\sigma }_1,{\sigma }_2,1]$ is a proper autotopy of our square.

For example, if columns 4 and 8 of the Latin square of Figure 4 are exchanged (in cycle notation this permutation is $\sigma =(48)$ ), then no permutation of the rows will restore it. Another permutation of the columns that doesn’t work is the cyclic rotation $\gamma =(12345678)$ where the first column moves to the second, etc. However composing these two (from left to right) yields the column permutation

An Orthogonal Mate for a Latin Square Based on an Asymmetric Tile, II

which permits the following row permutation

to restore the Latin square. In other words, $[{\alpha }_1,{\alpha }_2,1]$ is a proper autotopy of the Latin square. It is in fact an element of order 4 in the group of proper autotopies.

It can be checked that if the columns are rearranged according to the allowable permutation ${\beta }_2=(15)(26)(37)(48)$ , then composing the permutation $(15)(26)$ with the square of the cyclic rotation ${\gamma }^2=(1357)(2468)$ yields

which is a permutation of the rows restoring the original Latin square. Therefore, $[{\beta }_1,{\beta }_2,1]$ is another proper autotopy of the Latin square. These two autotopies generate a commutative group of order 8 which abstractly is the direct product of cyclic groups of orders 4 and 2. We will denote this group by $C_4\times C_2=\{1,a,a^2,a^3,b,ab,a^{2}b,a^{3}b\}$ where $a^4=1$ , $b^2=1$ and $ab=ba$ .

In general, the multiplication table $M$ of a group $G$ with $n$ elements is a Latin square. If its rows and columns are indexed by $G$ itself, then the $x,y$ entry of $M$ is the group product $xy$ . Notice that if $g\in G$ is any fixed element then $xy=x{g}^{-1}\cdot gy$ . This means that if the rows and columns of $M$ are permuted according to the permutations ${\sigma }_1(x)=x{g}^{-1}$ and ${\sigma }_2(y)=gy$ respectively, then $[{\sigma }_1,{\sigma }_2,1]$ is a proper autotopy of $M$ . In other words, the $n$ group elements of $G$ give rise to $n$ distinct proper autotopies of $M$ .

We already have found 8 proper autotopies of the Latin square of Figure 4, and these can be “reverse engineered” to render Figure 4 as the multiplication table of $C_4\times C_2$ . If the columns (and the tiles in the first row) are labeled, in order, by: $1,a,a^2,a^3,b,ab,a^{2}b,a^{3}b$ , and if the rows are labeled by: $1,ab,a^2,a^{3}b,a^{2}b,a^3,b,a$ , then the permutation ${\alpha }_2=(1234)(5678)$ corresponds to ${\sigma }_2(y)=ay$ (multiplication by $a$ ) and ${\alpha }_1=(1638)(2745)$ corresponds to ${\sigma }_1(x)=x{a}^{-1}$ (multiplication by $a^{-1}$ ). So the group element $a$ gives rise to the proper autotopy $[{\alpha }_1,{\alpha }_2,1]$ . Similarly, $b$ gives rise to $[{\beta }_1,{\beta }_2,1]$ .

We now have a multiplication table!

Finding a Mate

The multiplication table of a finite group, viewed as a Latin square, has an orthogonal mate if and only if some rearrangement of its columns is a mate. This is essentially Theorem 1.13 of [1].

Since the columns of our Latin square in Figure 4 are indexed by the group $C_4\times C_2$ , what needs to be found is a permutation, say $\sigma$ , of its elements so that the table whose $x,y$ entry is $x\cdot \sigma (y)$ is a Latin square that is orthogonal to our Latin square. Equivalently, we need to find an isotopy of the form $[1,\sigma ,1]$ transforming our Latin square to an orthogonal mate. Such a permutation $\sigma$ , should it exist, is called an orthomorphism. The criterion for a permutation to be an orthomorphism is that the associated function $\tau$ given by $\tau (g)=g^{-1}\cdot \sigma (g)$ needs to be a permutation of the group as well. (When this happens, the function $\tau$ is called a complete mapping.) Luckily, an orthomorphism for $C_4\times C_2$ does exist, and we exhibit one in Table 1. We replace group elements appearing as symbols in the mate by colors, and these appear in the table as well. The resulting superimposed Latin squares (using tiles and colors) appear in Figure 5.

Table 1: An orthomorphism of $C_4\times C_2$ and its associated complete mapping.

Gagola Jr.

Figure 5: A puzzle laser cut from colored transparent acrylic sheets depicting two orthogonal Latin squares.

Other Isotopies and Symmetries

Figures 6 and 7 show Latin squares constructed from tiles different from but associated to the one we considered in the previous sections. The first is its dual tile, and the second is a rogue tile constructed by narrowing and elongating the protrusion at the top edge, moving it slightly to the right.

If a tile is not a rogue (in other words, a dual tile exists) and if $\psi$ denotes the natural bijection from tiles to their duals, then $[1,1,\psi ]$ is an isotopy of Latin squares. This is the case in the situation of the Latin squares of Figures 5 and 6 (ignoring colors). More generally, if two tiles are constructed using the scheme mentioned in the Construction section, but starting with two unrelated curves “at the top”, then their associated Latin squares are isotopic by an isotopy of the form $[1,1,\theta ]$ where $\theta$ is a natural bijection from tiles of the first type to tiles of the second. This is the case for the Latin squares appearing in Figures 5 and 7 (ignoring colors again), as well as Figures 6 and 7. In this last case (where colors match orientations), the bijection of tiles preserves color.

There are many versions of Raedschelders’ second tile, but all 512 Latin squares constructed from any one of these are isotopic. This is so because all assemblages to produce an 8 by 8 Latin square will result unavoidably in the multiplication table of $C_4\times C_2$ (up to isotopy) and no other group. In particular, the fact that we chose to work with one of the 8 Latin squares that had $90^{\circ }$ rotational symmetry had no bearing on the final result; any one of the other 504 Latin squares would do just as well. The only difference would be that different permutations would appear in the autotopy groups.

An Orthogonal Mate for a Latin Square Based on an Asymmetric Tile, II

Figure 6: A Latin square constructed from a dual tile. Colors match orientations, so only one Latin square is depicted.

We already observed that $[1,1,\varphi ]$ is an isotopy of Latin squares where $\varphi$ is the transformation of tiles given by flipping a tile along its principal axis. Since all Latin squares considered here are properly isotopic, some rearrangement of rows and columns is possible that will restore the original Latin square without permuting tiles. In fact, the same permutation ${\gamma }^4$ applied to rows and columns does the job. Here $\gamma$ is the usual cyclic permutation $\gamma =(12345678)$ . In particular, $[{\gamma }^4,{\gamma }^4,\varphi ]$ is an autotopy of any one of the 512 Latin squares built from the tile we have been considering here.

Somewhat surprisingly, other permutations in place of $\varphi$ also work in the third coordinate. If ${\varphi }_2$ denotes the permutation sending a tile to the unique second tile whose left and right sides match, then $[1,1,{\varphi }_2]$ is an isotopy of Latin squares that is undone by applying ${\gamma }^4$ to the columns. In other words, $[1,{\gamma }^4,{\varphi }_2]$ is an autotopy of Latin squares. Similarly, if ${\varphi }_1$ is the permutation pairing tiles whose top and bottom sides match, then $[1,1,{\varphi }_1]$ is an isotopy that is undone by $[{\gamma }^4,1,1]$ . In other words $[{\gamma }^4,1,{\varphi }_2]$ is also an autotopy. Notice that ${\varphi }_1{\varphi }_2={\varphi }_2{\varphi }_1=\varphi$ , and $\{1,{\varphi }_1,{\varphi }_2,\varphi \}$ is the Klein 4-group.

Concluding Remarks

We mentioned that the multiplication table of a finite group, when viewed as a Latin square, has an orthogonal mate if and only if some rearrangement of its columns will be a mate. What is remarkable about that result is that an orthogonal mate may exist which is not even isotopic to the multiplication table. Nevertheless, that mate can be ‘tweaked’ to produce another that is. Given a finite group $G$ , is it easy to find an orthomorphism? For groups of odd order, it is. The mapping $\sigma (g)=g^{-1}$ is an orthomorphism. (So is $\sigma (g)=g^2$ .)

Gagola Jr.

Figure 7: A Latin square constructed from a rogue tile. Colors match orientations.

For groups of even order, the situation is completely different. For example, cyclic groups of even order do not possess an orthomorphism. Moreover, there doesn’t seem to be any algorithm to produce an orthomorphism for those groups of even order that possess one. In particular, the orthomorphism given in Table 1 was produced by “trial and error”. (For that group, several exist so it wasn’t that hard to find one.)

Finally we remark that the two tile types discovered by Raedschelders are not the only ones that can be used to build an 8 by 8 Latin square. There is one other (and only one other) type, and unlike Raedschelders’ tiles, several Latin squares having different isotopy types can be built using this new tile. We hope to present these new Latin squares and their mathematical properties in the near future.

References

[1] A. B. Evans. Orthogonal Latin Squares Based on Groups, Springer, Developments in Mathematics, Vol 57, 2018. [2] S. M. Gagola, Jr. “An Orthogonal Mate for a Latin Square Based on an Asymmetric Tile”, Bridges Conference Proceedings, Halifax, Nova Scotia, Canada, July 27-31, 2023, pp. 501-504. http://archive.bridgesmathart.org/2023/bridges2023-501. [3] B. Grünbaum. “Levels of Orderliness: Global and Local Symmetry.” Proceedings of a symposium at the Wenner-Gren Centre, Stockholm. Portland Press, London 2002. Vol 1, pp. 51-61. [4] M. Kepner. “Latin Fandango” and “Latin Fandango II.” Bridges Art Exhibition Catalog, 2016, p. 75. http://gallery.bridgesmathart.org/exhibitions/2016-bridges-conference/renpek1010 [5] P. Raedschelders. “Semimagic Tiling Based on an Asymmetrical Tile.” Geominatorics 10 (2000), pp. 45-50.