A solution to Johnson's Tangian conjecture


A recent problem in musical tilings of the line arose when TANGIAN [T] devised a computerized solution to JOHNSON's problem [J], that is, tiling the line with the pattern 1 1 0 0 1. All the solution appeared to have a length that is a multiple of 15 (and indeed solutions were found for all multiples up to computational limits). Is this general ? If so, why ?


Though A. Tangian imagined a polynomial representation of this problem just in order to explain why it was probably too difficult to solve algebraically, ironically enough it provided the means by which I managed the proof of the following

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.

As shown by [T],

Lemma 1. The problem of tiling is equivalent to solving a diophantine equation in polynomials with 0-1 coefficients:

A(X) J(X) + B(X) J(X2)    [ + C(X) J(X4)...] = Dn(X) = 1 + X + X2 +...+Xn-1

J(X) = 1 + X+X4 will henceforth be called JOHNSON's polynomial - he richly deserves it.

Lemma 2. J is irreducible over F2 = Z/2Z.

Meaning J as an element of F2[X].

Proof. Easy by testing factors: clearly there are no factors of degree 1 (no root), hence any factorisation would be with (irreducible) factors like X2 + a X + b, a,b ‘ F2. But the only irreducible polynomial of degree 2 over F2 is X2+X+1, and it does not divide J.

The reason behind the reason is that a root of X2+X+1 (in F4, the finite field with 4 elements) would be a cubic root a of unity, hence clearly not a root of J: one would get 2a+1 = 0+1 = 0, impossible (the characteristic of the field is still 2!).


Lemma 3. K = F2[X] / (J) is a field with 16 elements.

Proof. A classical result: the ideal J is maximal in the ring F2[X] because J is irreducible. Hence the quotient is a field, isomorphic as a vector space (over field F2) to the polynomials of degree at most 3 (as any polynomial modulo J has one and only one representation as a polynomial of degree < 4, by euclidian division). This set has clearly 24 = 16 elements, with 2 choices for each of the four coefficients.

Thus we achieved a construction (of F16, the one and only field with 16 elements, but it's neither here nor there) of a field where J has a root (indeed, more than one) a.

Lemma 4. Any non zero element x ‘ K* fulfills x15 = 1.

This is LAGRANGE's theorem on the multiplicative (abelian) group K*, which has 15 elements, or a form of FERMAT's (little !) theorem. A short proof: for any given x ‘ K*, the sets

K* = {1,a,b,...}       and        xK* = {x, x a, x b, ...}
are equal (a-> x a being one-to-one and onto). Hence the product of their respective elements is the same, e.g.
1.a.b.... = (x.1)(x.a).(x.b).... = x|K*|(1.a.b....) = x15.1.a.b....
and hence x15 = 1, qed.


The following lemma is not necessary, but it helps understanding precisely where we stand.

Lemma 5. Any root of J (in K) is exactly of order 15.

Proof. The order of an element of group K* must be a divisor of 15 (by Lagrange's theorem). Say a3 = 1; then plugging in J(a) = 0 gives (remembering 1+1 = 0 in K)

0 = a4+a+ 1 = 2 a+ 1 = 1       contradiction
The other case a5 = 1 is impossible too:
0 = a4+a+ 1 = a-1 + a+ 1 = a-1(1+a+a2) = (a3 - 1) a-1(a-1)-1
hence a would be also of order 3 ! So the only possibility is that a is of order 15 (by the way K* ª Z/15Z, not that it matters here).

Lemma 6. If alpha is a root of J (in K) then so are a2, a4,... a2k.

Easy enough: say a4 = - a-1 = a+1 (remember, -1=1 !). Then

a8 = (a+1)2 = a2 + 1       which is to say       J(a2) = 0

This is now also true for a2k by immediate induction.

Proof of the theorem.

Suppose there is a tiling of length n, e.g. there exists polynomials A, B (C) (with 0-1 coefficients) fulfilling

A(X) J(X) + B(X) J(X2)    [+ C(X) J(X4)] = Dn(X) = 1 + X + X2 +...+Xn-1
Let us substitute X = a, a root of J in K. This makes sense as an identity in Z[X] may be quotiented to F2[X] Ã K[X]. Indeed by force of the particular problem we are studying, the coefficients of all polynomials involved are already 0's and 1's !!! The left-hand term vanishes by Lemma 6 (for any number of augmentations). So
0 = Dn(a) = (an - 1)(a-1)-1
Hence an - 1 = 0 and n must be a multiple of the order of a (this is a classical property of the order of an element in a group): by Lemma 5, the proof is now complete.

File translated from TEX by TTH, version 2.21.
On 12 Feb 2002, 10:00.