Before beginning I must acknowledge two mathematicians to whom I am indebted. It was John Wild, who got me going on this, early in 2002, when he explained to me that a perfect tiling is one in which a single shape, most often a square, is tiled as a mosaic of smaller squares. If there are no holes and no overlaps, and if every one of the smaller squares used to tile the big square has a different dimension, the tiling is "perfect." Wild also gave me an article by Erich Friedman, which explained that a perfect square tiling with 69 inner squares was found by Smith Stone and Brooks in 1938, that one of 55 was published by Sprague in 1939, and that the quest for solutions of smaller orders continued until Duijvestijn found one of order 21, with only 21 inner squares. There are apparently no smaller solutions, and no additional solutions of order 21, but there are 8 of order 22, 12 of order 23, 26 of order 24, 160 solutions of order 25, 441 solutions of order 26, and so on. The second mathematician to whom I am indebted is Erich Neuwirth who, some months later, carried my computer searches further than I was able to do myself.

Like Jon Wild, I was more interested in one-dimensional tiling than two-dimensional tiling, and it was not difficult to formulate a one-dimensional equivalent of the perfect square tiling problem. How can we tile a line with triplets, that is, with groups of three evenly spaced points or beats? One can form a triplet, for example, by filling points 3, 4, and 5, or points 0, 5, and 10, or points 9, 20, and 31. The triplets must together form a tiling that is closed, that is, it must cover a line of consecutive points with a beginning and ending, rather than wrapping around as a loop, and all triplets must have different intervals or speeds. There are no solutions of order 2 (two triplets, filling a total of 6 beats), order 3 (three triplets filling 9 beats), or order 4 (four triplets filling 16 beats), but there is one solution (and a mirror of the same thing) of order 5, placing five triplets onto a line of 15 points in this way:

There are no solutions of order 6 and no obvious reason why there shouldn’t be, but for order 7 one finds solutions such as this.

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
one to one
two to one
four to one
five to one
seven to one
eight to one
ten to one

There are a total of 9 solutions for perfect triplet tilings of order 7, each of which can be reversed, giving 18 in all.

6 solutions with tempo ratios: (1 2 3 4 5 6 9)

(((0 9 18) (2 8 14) (1 6 11) (12 16 20) (7 10 13) (15 17 19) (3 4 5))

((0 9 18) (7 13 19) (5 10 15) (12 16 20) (11 14 17) (4 6 8) (1 2 3))

((1 10 19) (3 9 15) (8 13 18) (12 16 20) (11 14 17) (0 2 4) (5 6 7))

((1 10 19) (5 11 17) (2 7 12) (0 4 8) (3 6 9) (16 18 20) (13 14 15))

((2 11 20) (1 7 13) (5 10 15) (0 4 8) (3 6 9) (12 14 16) (17 18 19))

((2 11 20) (6 12 18) (9 14 19) (0 4 8) (7 10 13) (1 3 5) (15 16 17))))

2 solutions with tempo ratios: (1 2 3 5 6 7 9)

(((0 9 18) (5 12 19) (8 14 20) (6 11 16) (4 7 10) (13 15 17) (1 2 3))

((2 11 20) (1 8 15) (0 6 12) (4 9 14) (10 13 16) (3 5 7) (17 18 19))))

2 solutions with tempo ratios: (1 3 4 5 6 7 9)

(((1 10 19) (2 9 16) (0 6 12) (8 13 18) (7 11 15) (14 17 20) (3 4 5))

((1 10 19) (4 11 18) (8 14 20) (2 7 12) (5 9 13) (0 3 6) (15 16 17))))

2 solutions with tempo ratios: (1 2 3 4 6 8 9)

(((0 9 18) (4 12 20) (7 13 19) (2 6 10) (8 11 14) (1 3 5) (15 16 17))

((2 11 20) (0 8 16) (1 7 13) (10 14 18) (6 9 12) (15 17 19) (3 4 5))))

2 solutions with tempo ratios 2 3 4 5 6 8 9)

(((0 9 18) (3 11 19) (1 7 13) (5 10 15) (8 12 16) (14 17 20) (2 4 6))

((2 11 20) (1 9 17) (7 13 19) (5 10 15) (4 8 12) (0 3 6) (14 16 18))))

2 solutions with tempo ratios: (1 3 5 6 7 8 9)

(((0 9 18) (4 12 20) (3 10 17) (7 13 19) (1 6 11) (2 5 8) (14 15 16))

((2 11 20) (0 8 16) (3 10 17) (1 7 13) (9 14 19) (12 15 18) (4 5 6))))

2 solutions with tempo ratios (1 2 4 5 7 8 10)

(((0 10 20) (1 9 17) (5 12 19) (8 13 18) (3 7 11) (2 4 6) (14 15 16))

((0 10 20) (3 11 19) (1 8 15) (2 7 12) (9 13 17) (14 16 18) (4 5 6)))))

It is interesting to consider the tempo ratios we find here. There are 120 ways of combining 7 tempos out of 10 possible tempos. Why do only these 7 combinations permit perfect triplet tilings? It is not difficult to observe that tiles (0 10 20) and (0 9 18) can never be combined in a single tiling 21 points long. One might also demonstrate why the tempo ratios 3, 6 and 9 always occur together, if they occur at all. But it is not clear how our analysis could go further than this.

For triplet tilings of 24 points, order eight, there are 34 solutions plus 34 mirrors, and again tempos 3 and 6 and 9 always occur together or not at all. The solutions include 16 out of 165 possible combinations of the 11 tempos, taken 8 at a time.

It is tempting to assume that orders 9, 10, 11, and higher will permit increasing numbers of perfect triplet tilings. But since there are no solutions for tilings of order 6, there may also be exceptions among higher orders.

As a composer, it was the 15-point five-tempo tiling that seemed the most remarkable, and this provided the essential material for Tilework for Piano, completed late in 2003.

Simply investigating higher orders mostly involves waiting for the computer, and there are certainly more fruitful ways to proceed. Where might one continue investigating one-dimensional perfect tilings? It seemed possible that there might be perfect quadruplet tilings as well, that is, using tiles like (0 1 2 3), (0 3 6 9), (0 5 10 15), but Erich Neuwirth confirmed that there are no cases of this for the first seven orders, up to a length of 28. Of course, this does not prove anything about higher orders, if we recall that the smallest perfect square tiling is of order 21, but it did not seem worthwhile to search further into quadruplet tilings.

Duplet tiliings, however, proved interesting, because here, rather than having optional combinations of tempos, there is only one combination. A perfect duplet tiling of order n, filling 2n points, requires n different tempos, from 1 : 1 to n : 1..

The motif (0,1) tiles a line of two points, solving the problem for order one, but this is clearly trivial. One can not tile a line of four points with (0,1) and (0,2), and one can not tile a line of six points with (0,1), (0,2), and (0,3), but a perfect duplet tiling of order four, does exist:

4 to 1	0				4
1 to 1		1	2
3 to 1				3			6
2 to 1						5		7

As before, an exact reversal of this also tiles the line, but here we shall consider an original and retrograde pair to be one single solution.

Similarly, duplet tiling of the fifth order is possible, with tempos in ratio 5: 4: 3: 2: 1, and here there are three solutions, or pairs of solutions:

4 to 1	0				4
1 to 1		1	2
5 to 1				3					8
2 to 1						5		7
3 to 1							6			9
5 to 1	0					5
1 to 1		1	2
3 to 1				3			6
4 to 1					4				8
2 to 1								7		9
4 to 1	0				4
5 to 1		1					6
1 to 1			2	3
3 to 1						5			8
2 to 1								7		9

As with perfect triplet tilings, we are considering only closed tilings, with a beginning and ending, but in the case of perfect duplet tilings there is an important difference. Here open tilings do not exist for any order. This was not at all the case before. With perfect triplet tilings of order five, for example, only one closed tiling exists, the one I used for my piano piece, but there are 23 other solutions such as this one, that make open tilings:

With perfect duplet tilings, a line of 2n points must be filled with duplets of speeds 1, 2, 3,…,n, all points fall within the line, and redefining the solution as an open tiling would require using some ratios greater than n:1.

No perfect sixth order duplet tiling exists, either open or closed, and we do not need a computer search to be sure, because we can demonstrate this with the "parity argument," something I learned about from Jon Wild in the context of polyominoes. The 12-point line has 6 odd points and 6 even points, and each motif must cover either even points or odd points or one of each. Using the parity argument, one can never be sure that a tiling is possible, but one can be sure that a tiling is not possible if the even and odd points can not be covered with the available motifs. In this case the six motifs must tile a 12-point line, and since 12 is the product of 3 * 4, the points modulo 3 and modulo 4 must all be covered an equal number of times. But without going further than modulo 2, one can already see that there is a problem. In the list below, consider the possible combinations. The six odd points and the six even points of our 12-point line can not be filled with these six motifs. The best one can do is tile 7 odd points and 5 even ones or 5 odd points and 7 even ones.

Motif odd and even points that can be covered

(0,1) 1,1

(0,2) 2,0 or 0,2

(0,3) 1,1

(0,4) 2,0 or 0,2

(0,5) 1,1

(0,6) 2,0 or 0,2

Similarly, to tile the 7^th order, filling a line of 14 points with 7 motifs, the odd and even number of points must be tiled the same number of times, and again the situation does not permit this. Working with the list below, we must end up filling 6 odd points and 8 even ones, or the other way around.

Motif odd and even points that can be covered

(0,1) 1,1

(0,2) 2,0 or 0,2

(0,3) 1,1

(0,4) 2,0 or 0,2

(0,5) 1,1

(0,6) 2,0 or 0,2

(0,7) 1,1

The parity argument allows us to continue this logic, which alternates every two orders. For orders 6 and 7, a perfect duplet tiling is impossible, for orders 8 and 9 it is possible, for orders 10 and 11 it is impossible, and so on. Jon Wild recently found 376 perfect duplet tilings of order 8, and there are no doubt thousands of solutions farther out there if one wishes to run the computer long enough to find them.

The greater problem for mathematicians is to try to figure out what possible connections this might have with other branches of mathematical research, and what general wisdom we might derive from observations about perfect tilings. For the moment even the well researched perfect square tilings remain largely in the category of mathematical games, not taken very seriously above the level of Scientific America. But perhaps a wider significance will be seen later, and perhaps some good music can also emerge. At least I am working on it

Book and Articles by Tom Johnson

Self-Similar Melodies, 1996, 289 pp. Like Rational Melodies, Tilework, Tilework for Piano, and other compositions, available from Editions 75, 75 rue de la Roquette, 75011 Paris. email: tom@johnson.org. Web site: www.tom.johnson.org

"Automatic Music" in Actes des Journées d'informatique musicale 98, pp. F1 - 1 to F1 — 5, CNRS-LMA, 31 Chemin Joseph-Alguier, 13402 Marseille Cedex 20.

"Self-Replicating Loops" in Journées d’Informatique musicale, 1999, CEMAMu, CNET-B403, 38-40, rue du Général Leclerc, 92794 Issy-les-Moulineaux Cedex 9

"Objets mathématiques trouvés," Seminaire Entretemps: Musique, mathématiques et philosophie, IRCAM, January 2001. also available at www.tom.johnson.org.

"Tiling the line (Pavage de la ligne)," Journées de l’informatique musicale, June 2001, Bourges. Institut international de musique éléctroacoustique de Bourges, BP 39 18001, Bourges cedex.

"Tiling the Line in Theory and in Practice, Seminaire MaMux, IRCAM, February 2002.

"Some Observations on Tiling Problems," Seminaire MaaMuX, IRCAM, January, 2003

"Tiling Melodies, Tiling Chords," Computer Music Modeling and Retrieval, June 2003, LIRMM, CNRS, Université de Montpellier II.

"Music and Combinations," meeting sponsored by La Métive, La Creuse, December 2003.