Solving Some Tiling Problems with Polynomials




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:

A(X) J(X) + B(X) J(X2) + C(X) J(X4) = 1+X+X2+...+Xn-1        (1)
where J(X) = 1 + X + X4 represents Johnson's pattern and A,B,C are polynomials with 0 or 1 as only coefficients and represent the schedule of voices entries.

My very first idea was that factorisations of the polynomial

Dn(X) = 1+X+X2+...+Xn-1 >       (2)
in factors with integer coefficients are very well known: the irreducible factors are the cyclotomic polynomials, discussed in great detail below. This factorization approach is rewarding only when there are no sums in the left-hand side of (1).

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:

S(1) = 1        S(2) = 6        S(3) = 20        S(4) = 97      ...
We will show here how the polynomial approach allows to prove this Johnson-Tangian conjecture :


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

(A,B) M        (a, b) a+b
is one-to-one and onto. If A is a pattern (e.g. 1 1 0 0 1) and B an entry-table, this represents a canon, with copies of A translated by the action of B making up the tiles of the tiling.

The polynomial translation of this is:

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

P×Q = Dn

The correspondence between subsets and polynomials is straightforward, setting for instance P = cA = i A Xi.

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 Dn 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], F2[X], P(N) - the set of subsets of N) with satisfying morphisms [my proof of Johnson-Tangian conjecture relies heavily on the arrow F2[X] F16[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 Dn 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 Dp are the polynomials

Fn(X) =
'
d < n, dn = 1 
(X - xd) =
'
d < n, dn = 1 
(X - e2idp/n)
where n is any divisor of p (greater than 1).

The degree of Fn 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 (Zn,+,.) or the generators (additively) of the group (Zn,+).

Notice that the cyclotomic polynomials Fn 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 Fpk Fql is always a canon (with holes, but without overlapping).

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

D15 = >(1+X+X2)(1+X3+X6+X9+X12) >= F3 ×(F5 ×F15)
This simple result has many interesting consequences:

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+X3+X7+X11+X31 (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 Dn, for any n, meaning the pattern won't tile any line.

Easier: by the same line of reasoning, the 'Johnson's polynomial' 1+X+X4 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 Dn 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 = >Dn, 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) = P1(Xk) 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 = RS (here is an example of a reducible polynomial:

R(X) = 1+X2     S(X) = X+X3    P(X) = R(S(X)) = 1+S(X)2 = 1 + X2 + 2 X4 + X6
Now the first definition is too general, the last too restrictive, the middle one should be just right. Unfortunately computer searching has so far failed to reveal any. Theoretical arguments show that if a solution exists of length n, then n must be a rather heavily composite number (because of Hajos/Vuza theorem, see below).

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 = Dn. Then necessarily P(X) = 1+Xp + ... and Q(X) = 1 + Xq+... and P.Q = 1 + Xinf(p,q) + ... cannot be equal to Dn = 1 + X1 + X2 + ... [the special >case p = q being worse].


Some interesting canons DO exist, anyway, for

n = 16, 24, 32, 36, 40, 48, 54, 56, 60, 64, 72, 80, 81, 84,88, 90, 96, 100, 104, 108, 112, 120, ...
I define here this new species:

A non metronomic canon is a polynomial canon in which neither factor is of the form Dd(Xl) = >1+Xl+X2l >+...+Xdl.

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

1 + X + X4 + X5
1 + X2 + X8 + X10 + X16 + X18
1 + X + X2 + X6 + X7 + X8
1 + X3 + X12 + X15
1 + X + X4 + X5 + X8 + X9
1 + X2 + X12 + X14
1 + X2 + X4 + X12 + X14 + X16
1 + X + X6 + X7
and the four dual solutions (reversing the roles of the two factors). Let us remind the reader that, for instance, the last solution means the pattern (0 1 6 7) e.g. (X X - - - - X X) with the entry table (0 2 4 12 14 16).

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

n = pa , pa q , p2 q2 , p q r , p q r s ,...
and generally speaking all the cases mentioned in (both) Hajos and Vuza's theorems.

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]):

( 1 + x8 + x16 + x18 + x26 + x34 ) ( 1 + x + x5 + x6 + x12 + x25 + x29 + x36 + x42 + x48 + x49 + x53 )
This product outpasses x72 of course; one has to apply a reduction modulo 72 on the degrees to get D72. The rule would be

IF p 72 THEN xp xp-72

It can be formalized more prettily by euclidean division: one expands the product, then takes it modulo x72-1 = (x-1)D72 (that is to say, divide by x72-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:

A ×B = (xn - 1)×Q+ Dn =
(x-1)Q+1
Dn

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 Dn (maybe in adequate finite rings) could be the key to a real understanding of Vuza-canons.


File translated from TEX by TTH, version 2.21.
On 18 Mar 2002, 21:29.