Infinite Latin Squares
A Latin square of order n is an n×n array of n symbols in which every symbol occurs exactly once in each row and column of the array. There are several very simple ways to obtain Latin squares of any given order n. For example, write the sequence of integers
Assume now we wish to construct an infinite Latin square. More accurately, the square expands in two directions: rightwards and downwards. The problem is to fill the square (or rather a quadrant) with integers 0, 1, 2, 3, ... so that every term of the sequence will appear in every row and every column of the quadrant exactly once. (I started the sequence with 0 for the convenience sake. The reason will become clear later. However, this should be obvious that any countable collection of arbitrary objects would serve as well.)
Will the cycling procedure that served us so well in the finite case work now? Can we cycle through an infinite sequence? In principle, we can. However, the result  1, 2, 3, .... 0, where 0 follows all the rest of the numbers  is no longer a sequence. It is impossible to fit it into the second row of the quadrant. For a row in that table does not have a last cell whereas 0 is the very last element of the rotated sequence. The set remains countable as it was before. But now the order of elements is also important. There is no order preserving 11 correspondence between the two ordered sets, 0, 1, 2, 3, ... and 1, 2, 3, .... 0. If such one existed, what element from the first set would correspond to 0 in the second? Think of the next element. What would correspond to it from the second set?
Rudy Rucker poses the following problem:
"I have five fingers on my left hand," means the same thing as, "When I count up all the fingers on my left hand, the last number I say is five." What might "I have ∞ fingers on my left hand" mean?
The answer is that it would mean you have infinityplusone fingers. A curious thing about infinity is that you never count up to it. You count through every finite stage but never reach the last finger. If there is an "∞ finger", then it comes after an infinity of fingers and indicates that you have infinity fingers plus one more (which you named ∞). Still, the problem of constructing an infinite Latin square has infinitely many solutions. The applet below is intended to demonstrate one possible approach. Starting in the quadrant's corner with zero, we expand the square step by step, doubling its side on every step. With the side beyond 2^{5}, the font needed is so small that the numbers become blurred and indistinguishable. Instead, the applet shows a colorful carpet with a color for every term determined modulo a selected number.
The solution at hand derives from the traditional notion of the positional number system. Let's have a short table of a few first integers in the binary system.
We start with 0  one (1) single number. Use this 1 as a clue. To get the second number, add 1 to zero just once. After that we shall have two (2) numbers: 0 and 1. Add 2 to the two of them to obtain the next two numbers. We have now four (4): 0, 1, 2, 3. Add 4 to all four in turn to get the next four, and so on. In the binary system, each step consists of writing all previously obtained numbers twice and prepending the binary digit 1 to the second copy of every number. The construction of the Latin square is very similar. First, fill the corner square of size 1x1 with the number 0. On the next step, we get a square of size 2x2. The latter consists of four squares equal in size to the square on the previous step. I'll denote them generically as S_{nw}, S_{ne}, S_{se}, and S_{sw}. S_{nw} is the square from the previous step. Copy it into three other squares, and lastly add 1 (the side of S_{nw}) to every element of S_{ne} and S_{sw}. Assume a corner square of size 2^{n} has been filled. Denote it as S_{nw}. Copy it into adjacent squares S_{ne}, S_{se}, and S_{sw} and add 2^{n} to every element of S_{ne} and S_{sw}. Every corner square of side 2^{n} is a Latin square with elements 0, 1, ..., This construction solves problem M1123 from the Russian magazine Kvant [Cofman, p 107]: Is it possible to place into each cell of a doubly infinite array of square cells a natural number so that each row of the cells and every column contains any natural number exactly once? References
Latin Squares
Contact Front page Contents Algebra Store Copyright © 19962017 Alexander Bogomolny
