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 1, 2, ..., n in the first row. Select a direction (left or right) and cycle the sequence through one position in that direction: 2, 3, ..., n, 1. Use the resulting sequence to fill the second row. Apply the same procedure to that sequence (always cycling in the same direction) and so on, filling consecutive rows of the square. On the (n+1)-st rotation, the outcome is the original system. But that's alright - by then, the square was completely filled and a Latin square constructed.

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 1-1 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 infinity-plus-one 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 25, 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.


This applet requires Sun's Java VM 2 which your browser may perceive as a popup. Which it is not. If you want to see the applet work, visit Sun's website at https://www.java.com/en/download/index.jsp, download and install Java VM and enjoy the applet.


What if applet does not run?

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.

0    0    0
1    1    0+1
2    10    0+2
3    11    1+2
4    100    0+4
5    101    1+4
6    110    2+4
7    111    3+4
8    1000    0+8
9    1001    1+8
10    1010    2+8
11    1011    3+8
12    1100    4+8
13    1101    5+8
14    1110    6+8
15    1111    7+8
16    10000    0+16

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 Snw, Sne, Sse, and Ssw. Snw is the square from the previous step. Copy it into three other squares, and lastly add 1 (the side of Snw) to every element of Sne and Ssw. Assume a corner square of size 2n has been filled. Denote it as Snw. Copy it into adjacent squares Sne, Sse, and Ssw and add 2n to every element of Sne and Ssw.

Every corner square of side 2n is a Latin square with elements 0, 1, ..., 2n-1. This is established by induction from the properties of the binary system implied by the table. Therefore, the whole quadrant is a Latin square. This is the same argument as counting to infinity - every step is finite. The argument goes as follows. Assume, on the contrary, that in a row N there is either a missing element or an element that appears at least twice. In the latter case, let M be the column of the second occurrence of that element in row N. Choose a power 2s of 2 exceeding both M and N. From the foregoing discussion, that corner square with side 2s is Latin. However, by our assumption, there is an element inside the square that occurs twice in row N. In the former case, let N stand for the missing element. Then row N in the Latin square of side 2s, does not contain M. Which is also impossible. Contradiction.

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

  1. J. Cofman, Numbers and Shapes Revisited, Clarendon Press, 1995
  2. R. Rucker, Infinity and the Mind, Princeton University Press, 1995

Latin Squares

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny

71471470