Abstract: following other people's ideas on 'tiling the line', the author tries to make use of the convenient tool of polynomials over various structures. This enables to define several species of 'polynomial tilings', may give new insight on solved but complicated problems (such as Hajòs theorem) and even provides with elegant solutions to recent conjectures.

Keywords: tiling, mosaics, rythmic canons, Vuza canons, Johnson's problem.

Introduction. The ideas exposed here made the bulk of a communication to the MaMux seminar at IRCAM on the 9 of february, 2002.

Having perused preprints from MMs FRIPERTINGER and TANGIAN (also speakers in the same meeting), one of which made use of the Möbius inversion and the other putting forward a polynomial formulation of Tom Johnson's problem, I was tempted to explore in greater detail the advantages of using the considerable mathematical knowledge about polynomials to explore tiling problems in the field of rythmic canons.

Several ideas are just ideas - more or less promising - but some of them proved worth their while. Consequently I will mention some unfinished bits of work when I feel they deserve it.

1. Tom Johnson's problem.

It is elsewhere related how Andranik TANGIAN expressed the problem of tiling the line with the rhythmic pattern (1 1 0 0 1) and its augmentations `without gap or double beat' as a diophantine equation in polynomials:

My very first idea was that factorisations of the polynomial

Both Tom Johnson and Andranik Tangian noticed that empirical (or computerised) solutions of (1) have lengths that are multiples of 15. Indeed, the number of solutions with length 15 k is a rapidly increasing function of k:

Theorem. Any tiling of the line by the pattern 1 1 0 0 1 and its binary augmentations (eg 1 0 1 0 0 0 0 0 1, 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1...) has a length that is a multiple of 15.

2. Cyclotomic polynomials

Let us return to the fundamental problem of tiling the line, or of rhythmic canons. We consider hereafter the following problem:

Find two subsets A,B of M = {0,1,..., n-1} for which

The polynomial translation of this is:

Find two polynomials P, Q with coefficients in {0,1} for which

The correspondence between subsets and polynomials is straightforward, setting for instance P = c_A = å_{i Î A} Xⁱ.

This kind of `characteristic polynomial' (like characteristic functions of a set) reminds of Vuza [V4] and leads to very difficult mathematical problems. In this simple case, it reminds one of the adjacency matrix of a graph.

Now we must factor D_n as a product of two `0-1 polynomials'. The general solution of this is not known, but the polynomial formulation helps to tackle the matter.

In my talk I tried to stress the point that the set À of all 0-1 polynomials is worth considering, though it suffers from terrible flaws: it is not closed under the usual composition laws (+, ×, °) , that is to say a combination of two 0-1 polynomials is not necessarily another 0-1 polynomial (try adding one such polynomial with itself !)

Still it is an interesting set, the closest indeed to the problem of tiling the line and its study should perhaps be considered. On the one hand, it branches to excellent and well-known structures (such as Z[X], F₂[X], P(N) - the set of subsets of N) with satisfying morphisms [my proof of Johnson-Tangian conjecture relies heavily on the arrow À® F₂[X] Ì F₁₆[X]); on the other, some concepts may be adapted and studied in À, such as divisibility, ideals, aso. Such results as I have found in >this direction are still scarce, as of now, and I won't expose them yet.

One line of thought that does reap some interesting rewards is to consider À as a subset of Z[X]. In this ring, the ultimate >factorization of D_n is known and the (irreducible) factors are very close to À: indeed many of them are IN À. I state the following classical results without proof, they should be found in any classical textbook in commutative algebra.

The irreducible factors in Z[X] or Q[X] of D_p are the polynomials

The degree of F_n is given by EULER totient function, it is the number of integers relatively prime to n, that is to say the regular (multiplicative) elements of the ring (Z_n,+,.) or the generators (additively) of the group (Z_n,+).

Notice that the cyclotomic polynomials F_n are monic polynomials, with integer coefficients. Indeed usually most of the coefficients are 0's or ±1's.

See a table here.

As one will easily see, many cyclotomic polynomials are indeed 0-1 polynomials and readily provide canons (though not necessarily tilings of the line) by product. For instance the product F_p^k F_q^l is always a canon (with holes, but without overlapping).

As these are irreducible factors, any factorisation of D_n in the product of two polynomials with integer coefficients, and hence in 0-1 polynomials, must be a partition of the canonic factorization D_n = '_{1 < d |n} F_d. In the example above, set p = 3, q = 5: then a very >simple rhytmic canon is (1 1 1) repeated 5 times, ie

· With a table of cyclotomic polynomials, it is a simple matter to find all factorizations in 0-1 polynomials by way of a computer search. This can (and will) be bettered with some pruning of the binary tree of all possible partitions.

· (just illustrating the power of the notion) Tom Johnson mentioned the case of the pattern (0 3 7 11 31) and the difficulty of knowing whether it tiles the line (Johnson considered a more general notion of `tiling loops', see his paper here).

From a look at the roots (in the complex field) of the polynomial 1+X³+X⁷+X¹¹+X³¹ (one of which is for example 1.04200725545+ 0.1323321581 i, and the only real one being -0.8339814982286) neither of which lies on the unit circle, it is obvious that this cannot be a product of cyclotomic polynomials; hence it can't be a factor of any D_n, for any n, meaning the pattern won't tile any line.

· Easier: by the same line of reasoning, the 'Johnson's polynomial' 1+X+X⁴ cannot tile the line by itself (the roots are either smaller or greater than 1). The more complicated problem of tiling the line with it and a number of its augmentations does have solutions as Johnson and Tangian have found, but of course it is much more difficult to prove in the abstract !

3. Vuza canons and polynomial tilings.

The notion of Vuza canons, or as he put it `regular complementary of maximal category', is now more or less common knowledge. The polynomial approach enables to look for special species of canon, by simply factoring D_n in cyclotomic polynomials and trying all the recombinations to get all rythmic canons:

· a polynomial canon of length n is simply a solution of P×Q = >D_n, P and Q being 0-1 polynomials.

· an aperiodic canon is a polynomial canon in which neither P nor Q are `periodic', meaning P (resp. Q) won't satisfy any relation of the kind P(X) = P₁(X^k) for some k > 1.

· an irreducible (polynomial) canon is a canon for which neither P nor Q is composed, e.g. one excludes that P = R°S (here is an example of a reducible polynomial:

But hope remains, insofar as

Proposition. In any polynomial canon, at most one of the factors P,Q is periodic.

Proof: Suppose P (resp. Q) is p-periodic (resp. q-periodic) and P.Q = D_n. Then necessarily P(X) = 1+X^p + ... and Q(X) = 1 + X^q+... and P.Q = 1 + X^inf(p,q) + ... cannot be equal to D_n = 1 + X¹ + X² + ... [the special >case p = q being worse].

Some interesting canons DO exist, anyway, for

· A non metronomic canon is a polynomial canon in which neither factor is of the form D_d(X^l) = >1+X^l+X^2l >+...+X^dl.

The term `non-metronomic' is self-explanatory. Some examples: for n = 24 the solutions are

These canons are numerous, from the above lemma it is possible at least to arrange for the rhythmic pattern to be irregular, so I think this is a useful dingo for composers.

In this example, the rhythmic pattern is regular (though non metronomic), hence this is not a Vuza canon. Generally speaking, there is a hierarchy:

Proposition. Any irreducible polynomial canon is aperiodic. Any aperiodic canon is irregular, and is a Vuza canon.

The reverse of the last sentence is not true: an aperiodic canon provides a tiling of the integer range {0,1,2,...,n-1}., while a Vuza canon tiles Z/nZ. That means that an aperiodic canon is (would be) a tight kind of Vuza canon. Hence, too, it is useless to look for such canons of length

I have found direct demonstrations of the impossibility of (most of) such n's, using only simple properties of cyclotomic polynomials. Let us mention one of these demonstrations as an example: I think it helps getting a better understanding of why such lengths are forbidden.

4. Between Vuza-canons and aperiodic canons.

A general Vuza-canons `of order n' stretches over the range 0... n. Here is one of the shorter examples, for n = 72 (computed by Andreatta [A]):

It can be formalized more prettily by euclidean division: one expands the product, then takes it modulo x⁷²-1 = (x-1)D₇₂ (that is to say, divide by x⁷²-1 and take the remainder).

Hence a characterization of Vuza canons, that may help to get at them form a theoretical point of view:

Proposition. There exists a Vuza-canon of order n iff it is possible to write the following identity between the 0-1 polynomials A, B, Q:

The only point of note is that Q is necessarily a 0-1 polynomial, which is easy to prove.

This proposition suggests that factorizations of D_n (maybe in adequate finite rings) could be the key to a real understanding of Vuza-canons.