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 + X⁴ will henceforth be called JOHNSON's polynomial. A finite field with q elements wil be denoted F_q. The gist of the proof is to read the identity (1) in the ring F₂[X] of polynomials with 0-1 coefficients, setting 1+1 = 0.

Lemma 1. J is irreducible over F₂ = Z/2Z.

Meaning from now on J as an element of F₂[X] (any identity in Z[X] gives a new one in F₂[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 X² + a X + b, a,b ‘ F₂. But the only irreducible polynomial of degree 2 over F₂ is X²+X+1, and it does not divide J.

The reason behind the reason is that a root of X²+X+1 (in F₄, 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 = F₂[X] / (J) is the field with 16 elements.

Proof. A classical result: the ideal J is maximal in the ring F₂[X] because J is irreducible. Hence the quotient is a field, isomorphic as a vector space (over field F₂) 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 2⁴ = 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 a², a⁴,a⁸).

(Rem: for non mathematicians, the field K above is just the set of polynomials in a, where we set precisely J(a) = a⁴+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 x¹⁵ = 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 a³ = 1; then plugging in J(a) = 0 gives (remembering 1+1 = 0 in K)

Lemma 5. If a is a root of J (in K) then so are a², a⁴,... a^2k.

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

Indeed, by this lemma, the roots of J ARE a, a²,a⁴ and a⁸ (all different elements of order 15) (notice a¹⁶ = a and hence a^2k = a^{2k mod 4}) and so are the roots of J(X²), because by a straightforward verification, in F₂[X]

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

For the reader. Adapt the proof supra for the polynomial 1+X+X³ 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).