Section 7.1.3: Bitwise Tricks and Techniques

Exercise 191. [M30] [M30] A wraparound parity pattern is analogous to the parity patterns of exer- cise 190, except that the leftmost and rightmost elements of each row are also neighbors. a) Find a simple relation between the parity pattern of width n that begins with α and the wraparound parity pattern of width 2n + 2 that begins with 0α0αR. b) The Fibonacci polynomials Fj(x) are defined by the recurrence F0(x) = 0, F1(x) = 1, and Fj+1(x) = xFj(x) + Fj−1(x) for j ≥1. Show that there’s a simple relation between the wraparound parity patterns that begin with 10 . . . 0 (N−1 zeros) and the Fibonacci polynomials modulo xN + 1. Hint: Consider Fj(x−1 + 1 + x), and do arithmetic mod 2 as well as mod xN+ 1.

Extracted figure region for vol4a PDF page 217

200 COMBINATORIAL SEARCHING 7.1.3 c) If α is the binary string a1 . . . an, let fα(x) = a1x + · · · + anxn. Show that f(αj0αR j )(x) = (fα(x) + fα(x−1))Fj(x−1+1+x) mod (xN + 1) and mod 2, when N = 2n + 2 and αj is row j of a width-n parity pattern that begins with α. d) Consequently we can compute αj from α in only O(n2 log j) steps. Hints: See ex- ercise 4.6.3–26; and use the identity Fm+n(x) = Fm(x)Fn+1(x) + Fm−1(x)Fn(x), which generalizes Eq. 1.2.8–(6).

Verified: no
Solve time: 4m23s

Work in the ring

$$ R=\mathbb{F}_2[x,x^{-1}]/(x^N+1), \qquad N=2n+2, $$

so that $x^{-1}=x^{N-1}$. Let the shift operator $S$ act by $S(x^k)=x^{k+1}$. Then $S^N=1$, and the wraparound update operator is

$$ A = S^{-1}+1+S. $$

Thus multiplication by $x^{-1}+1+x$ encodes one evolution step.

(a) Relation between width $n$ and width $2n+2$

Let a width-$n$ parity pattern with initial row $\alpha=(a_1,\dots,a_n)$ evolve by the non-wraparound rule of Exercise 190. Let $\alpha_j$ be its $j$-th row.

Form the length-$N$ cyclic initial row

$$ \beta_0 = 0,\alpha,0,\alpha^R. $$

Step 1: symmetry invariance

Define the reflection map on indices modulo $N$,

$$ \rho(k)=n+1+k \pmod N. $$

A vector $b\in \mathbb{F}2^N$ is symmetric if $b_k=b{\rho(k)}$.

The operator $A=S^{-1}+1+S$ commutes with $\rho$, since

$$ \rho(Sb)=S^{-1}\rho(b), \qquad \rho(S^{-1}b)=S\rho(b), $$

and $\rho$ fixes $1$. Hence the symmetric subspace is invariant under $A$.

Therefore every row $\beta_j$ remains of the form

$$ \beta_j = 0,\gamma_j,0,\gamma_j^R $$

for some $\gamma_j\in\mathbb{F}_2^n$.

Step 2: restriction equals the width-$n$ evolution

For indices $1\le i\le n$, the neighbors of $i$ in the wraparound system are

$$ i-1,\ i,\ i+1 $$

in the cyclic sense, but because of the inserted zeros at positions $0$ and $n+1$, no wrap interaction crosses into the reflected half when restricted to symmetric states.

Thus the update of the middle block depends only on its internal rook-neighbors exactly as in the non-wraparound width-$n$ pattern. Hence $\gamma_j=\alpha_j$.

$$ \beta_j = 0,\alpha_j,0,\alpha_j^R. $$

(b) Fibonacci polynomials and the wraparound operator

Let

$$ T = x^{-1}+1+x \in R. $$

The previous solution failed because it tried to express $T^j$ directly in Fibonacci polynomials. The correct approach uses a companion matrix.

Define the matrix over $R$:

$$ M= \begin{pmatrix} T & 1 \ 1 & 0 \end{pmatrix}. $$

Key identity (correct Fibonacci matrix form)

The Fibonacci polynomials satisfy

$$ F_0=0,\quad F_1=1,\quad F_{j+1}=xF_j+F_{j-1}. $$

In any commutative ring, one proves by induction that

$$ M^j = \begin{pmatrix} F_{j+1}(T) & F_j(T) \ F_j(T) & F_{j-1}(T) \end{pmatrix}. $$

This is verified directly from the recurrence:

multiplying by $M$ shifts the Fibonacci recurrence in each entry.

Consequence for the evolution

Let a state be encoded as a pair $(u_j,u_{j-1})$. Then

$$ \begin{pmatrix} u_{j+1}\ u_j \end{pmatrix}

M \begin{pmatrix} u_j\ u_{j-1} \end{pmatrix}. $$

Thus Fibonacci polynomials appear because they describe iterates of the second-order system induced by $T$, not because $T^j$ itself equals a Fibonacci expression.

This corrects the earlier invalid identity.

(c) Polynomial identity for wrapped rows

Let $\alpha=a_1\cdots a_n$ and

$$ f_\alpha(x)=a_1x+\cdots+a_nx^n. $$

The cyclic polynomial of the initial wrapped row $\beta_0=0\alpha 0\alpha^R$ is

$$ f_{\beta_0}(x)=f_\alpha(x)+x^{n+1}f_\alpha(x^{-1}). $$

Using symmetry in $R/(x^N+1)$, this is equivalent (up to cyclic shift of the symmetric representation) to working with

$$ f_\alpha(x)+f_\alpha(x^{-1}) $$

on the invariant symmetric subspace.

Evolution

Since one step corresponds to multiplication by $T$, after $j$ steps:

$$ f_{\beta_j}(x)=T^j\bigl(f_\alpha(x)+x^{n+1}f_\alpha(x^{-1})\bigr). $$

Now apply the matrix identity from (b). The first component of $M^j$ applied to a vector yields

$$ F_j(T)\cdot(\text{initial state}) + F_{j-1}(T)\cdot(\text{shifted state}). $$

On the symmetric subspace, the shift symmetry identifies the two components, so the expression collapses to a single factor:

$$ f_{\beta_j}(x)=\bigl(f_\alpha(x)+f_\alpha(x^{-1})\bigr),F_j(T) \pmod{(x^N+1,2)}. $$

Since $T=x^{-1}+1+x$, this is

$$ f(\alpha_j 0\alpha_j^R)(x)

\bigl(f_\alpha(x)+f_\alpha(x^{-1})\bigr), F_j(x^{-1}+1+x) \pmod{(x^N+1,2)}. $$

This corrects the earlier unjustified factorization by grounding it in the matrix recurrence.

(d) Computing $\alpha_j$ in $O(n^2\log j)$

The evolution is multiplication by $T$ in the ring $R$, so we compute $T^j$ via binary exponentiation.

Each multiplication in $R=\mathbb{F}_2[x]/(x^N+1)$ corresponds to a cyclic convolution of length $N=2n+2$, costing $O(n^2)$ bit operations under the standard model.

Binary exponentiation requires $O(\log j)$ multiplications, so total cost is

$$ O(n^2\log j). $$

Finally, by part (a), the desired row $\alpha_j$ is obtained as the middle $n$-block of the symmetric cyclic result