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.
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.
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,..., n1} 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^{i}.
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 `01 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 01 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 01 polynomials is not necessarily another 01 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 wellknown structures (such as Z[X], F_{2}[X], P(N)  the set of subsets of N) with satisfying morphisms [my proof of JohnsonTangian conjecture relies heavily on the arrow À® F_{2}[X] Ì F_{16}[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 01 polynomials and readily provide canons (though not necessarily tilings of the line) by product. For instance the product F_{pk} F_{ql} 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 01 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 01 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^{3}+X^{7}+X^{11}+X^{31} (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^{4} 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 !
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 01 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_{1}(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 pperiodic (resp. qperiodic) 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^{1} + X^{2} + ... [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 `nonmetronomic' is selfexplanatory. 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,...,n1}., 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.
A general Vuzacanons `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^{72}1 = (x1)D_{72} (that is to say, divide by x^{72}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 Vuzacanon of order n iff it is possible to write the following identity between the 01 polynomials A, B, Q:

The only point of note is that Q is necessarily a 01 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 Vuzacanons.