Mazzola, Guerino / Noll, Thomas / Lluis-Puebla, Emilio: Perspectives in Mathematical and Computational Music Theory

4.2 A Tiny Step in an Unexpected Direction

When I first tried tackling Johnson’s problem I wrongly considered Galois groups of cyclotomic fields over the rationals. Fortunately this was avoidable, and a much simpler idea worked: If such polynomial identities in $Z[x]$ represent tilings, they are also identities in the ring of polynomials with coefficients in any field (as the only numbers involved in the calculations are 0’s and 1’s): see Theorem 14 below.

The first idea that comes to mind is to study the case of the smallest field, with two elements, e.g. $GF [2] = Z/2Z = F = {0,1} 2$ . The correspondence with the set of 0-1 polynomials is the closest possible: it is one to one and onto, though unfortunately the latter set is not closed under either addition or multiplication.

Indeed such identities in $F [x] 2$ remain true when expanding the field to any field with characteristic 2. Now computing relation (1) in such a field with elements of (multiplicative) order 15 yield the solution. The smallest such field is $GF [2,4] = F 16$ . It in fact is the decomposition field of $J(x)$ over $F 2$ : That means it it the cheapest way to get a root (indeed, four different roots) of $J(x)$ (this is because $J(x)$ is easily seen to be irreducible in $F [x] 2$ ). Any of these roots, say $r (- F 16$ , is exactly of order 15, meaning that $rn = 1$ iff $n$ is a multiple of 15³

³: Using Lagrange’s or Fermat’s small theorem, it is easily seen that for any $r (- F*,r15 =1 16$ . It only remains to check that if $J(r) =0$ , $r$ cannot be of order 1,3 or 5.

Furthermore, in $F2[x]$ one has $J(x2) = (J(x))2$ (this is true for all polynomials over a field of characteristic 2 because in these fields »1+1=0 «). Hence $r$ is also a root of $J(x2),J(x4),...$ .

But then equation 1 yields

2 n-1 n -1 0+ 0 [+0 ...] = 1 +r + r + ...+ r = (1- r ).(1- r)

So $rn = 1$ , hence $15 |n$ , qed.

This does not always work: for the motif ${0,1,3}$ for instance, one only gets $7 |n$ by the same method. But as all tiles play three notes, a solution must have at least length $21 = 3 .7|n$ , as is indeed the case (the smallest solution is 21 long). Worse still, this method provides only a necessary condition, which looks a long way from ascertaining whether a solution does exist ! And it is pretty difficult to haul solutions from similar equations in $F2[x]$ (which are numerous) back to $Z[x]$ . I could only prove a simple criteria, akin to $(T 1)$ :

Theorem 14 An identity of the kind $A(x).B(x) + C(x).D(x) + ...= W (x)$ (only sums and products) in $F2[x]$ also holds in $Z[x]$ if, and only if, it holds when a non negative real number $a > 0$ is substituted for $x$ .

Proof (sketched): otherwise cancellations occur, as in this example:

3 2 3 2 (1+x+x )+(x+x +x ) = 1+x in F2[x] but not in Z[x] : indeed 3+3 > 2.

This is a strange situation: we ponder in which cases the canonical injection $F [X] --> Z[X] 2$ works like a ring morphism ! Taking $a = 1$ we are not far from condition $(T 1)$ . Taking $a = 2$ or higher, Mersenne numbers and rep-units appear.