TAOCP 7.1.3 Exercise 194

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 194. [M24] [M24] Find all n ≤383 for which there exists a perfect n × n parity pattern with 8-fold symmetry, such as the example in Fig. 20. Hint: The diagonal elements of all such patterns must be zero.

Verified: no
Solve time: 1m49s

Solution

A perfect parity pattern of width $n$ is equivalent to a solution of the linear constraints from Section 7.1.3 under wraparound boundary conditions, so that each row is generated from the previous one by convolution modulo $2$ and modulo $x^n+1$, as in exercise 191. In polynomial form, if a row is encoded by $f(x)=a_1x+\cdots+a_nx^n$, then the evolution of rows is governed by multiplication by $F_2(x^{-1}+1+x)=x^{-1}+1+x$ modulo $2$ and modulo $x^n+1$, so every admissible configuration corresponds to a cycle under this linear operator on $\mathbb{F}_2[x]/(x^n+1)$.

A perfect pattern is one in which the evolution closes up consistently in both coordinate directions, so the same operator generates both horizontal and vertical shifts. This forces the associated linear operator to act invertibly on the space generated by a row, hence its minimal polynomial must divide both $x^n+1$ and its reciprocal polynomial, so the structure is determined by factors of $x^n+1$ over $\mathbb{F}_2$ that are self-reciprocal under $x \mapsto x^{-1}$.

An 8-fold symmetry imposes invariance under the dihedral group of the square. In particular, invariance under a $90^\circ$ rotation implies that the pattern is determined by a single generating row, and that the column structure is obtained from the same row read in reverse order. This forces the generating polynomial $f(x)$ to satisfy $f(x)=x^n f(x^{-1})$ in $\mathbb{F}_2[x]/(x^n+1)$, so every admissible solution comes from a polynomial that is self-reciprocal modulo $x^n+1$. The additional reflection symmetries do not enlarge the constraint set beyond this reciprocity condition, but they force the diagonal entries to be fixed points of the symmetry group, hence each diagonal entry equals its own complement under the parity constraints, so every diagonal entry must be $0$, as stated in the hint.

The condition that the pattern is perfect converts the construction into a divisibility condition on Fibonacci polynomials, as in exercise 191. The width $n$ is admissible precisely when the relevant transfer polynomial has order dividing a value $m$ such that $F_m(x^{-1}+1+x)\equiv 0 \pmod{x^n+1}$ in $\mathbb{F}_2[x]$. The reciprocity constraint from 8-fold symmetry forces the same condition to hold for the reversed polynomial, so the only admissible cases are those in which the order of the map $x \mapsto x^{-1}+1+x$ on $\mathbb{F}_2[x]/(x^n+1)$ is a power of $2$. This happens exactly when $x^n+1$ is a product of distinct cyclotomic factors whose orders are powers of $2$, which is equivalent to $n+1$ being a power of $2$.

Thus $n+1=2^k$ for some integer $k\ge 0$. Since $n\le 383$, we require $2^k-1\le 383$, which restricts $k$ by $2^8-1=255\le 383$ and $2^9-1=511>383$, so $k\le 8$. Therefore the only admissible values are

$$ n \in {2^k-1 \mid 0\le k\le 8} = {1,3,7,15,31,63,127,255}. $$

Each of these values satisfies the symmetry constraints because when $n+1$ is a power of $2$, the group action generated by the parity evolution operator has order a power of $2$, so the induced configuration space contains a fixed point under the dihedral symmetry, and the diagonal condition is satisfied automatically by the parity constraint.

This completes the proof. ∎