A solution of the 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.

J(X) = 1 + X + X4 will henceforth be called JOHNSON's polynomial. A finite field with q elements wil be denoted Fq. The gist of the proof is to read the identity (1) in the ring F2[X] of polynomials with 0-1 coefficients, setting 1+1 = 0.


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

Meaning from now on J as an element of F2[X] (any identity in Z[X] gives a new one in F2[X]), though the converse is not true).

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 2. K = F2[X] / (J) is the 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 a field K where J has a root a (indeed, more than one: see Lemma 5 where it is proven that the others are a2, a4,a8).

(Rem: for non mathematicians, the field K above is just the set of polynomials in a, where we set precisely J(a) = a4+a+1 = 0. The Lemma states that this is a field, that is to say any non-zero element has an inverse for multiplication).


Lemma 3. 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.


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


Lemma 4. 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 5. If a 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.

Indeed, by this lemma, the roots of J ARE a, a2,a4 and a8 (all different elements of order 15) (notice a16 = a and hence a2k = a2k mod 4) and so are the roots of J(X2), because by a straightforward verification, in F2[X]

J(X2) = J(X)2     J(X2k) = J(X)2k    (X® X2 is the famous Frobenius automorphism)


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 5 (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 face=symbol>a (this is a classical property of the order of an element in a group): by Lemma 4, the proof is now complete.


For the reader. Adapt the proof supra for the polynomial 1+X+X3 and prove that any solution of this variant of the Johnson's problem has a length multiple of 7 (and hence of 21, as any tile is of length 3).

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