TAOCP 7.1.3 Exercise 65
Let u(x)=\sum_{i=0}^{n-1} u_i x^i \pmod 2,\qquad v(x)=\sum_{i=0}^{n-1} v_i x^i \pmod 2, and let the corresponding integers be
Section 7.1.3: Bitwise Tricks and Techniques
Exercise 65. [M16] The binary polynomial $u(x) = u_0 + u_1 x + \cdots + u_{n-1} x^{n-1} \pmod{2}$ can be represented by the integer $u = (u_{n-1} \ldots u_1 u_0)_2$. If $u(x)$ and $v(x)$ correspond to integers $u$ and $v$ in this way, what polynomial corresponds to $u \updownarrow v$?
Verified: yes
Solve time: 1m07s
Solution
Let
$$ u(x)=\sum_{i=0}^{n-1} u_i x^i \pmod 2,\qquad v(x)=\sum_{i=0}^{n-1} v_i x^i \pmod 2, $$
and let the corresponding integers be
$$ u=(u_{n-1}\ldots u_1 u_0)2,\qquad v=(v{n-1}\ldots v_1 v_0)_2. $$
By the definition of the zipper operation $z = u \updownarrow v$, the binary expansion of $z$ is obtained by interleaving bits of $u$ and $v$, so that for all $k \ge 0$,
$$ z_{2k}=u_k,\qquad z_{2k+1}=v_k. $$
Let $w(x)$ be the polynomial corresponding to $z$, so
$$ w(x)=\sum_{j\ge 0} z_j x^j \pmod 2. $$
Substituting the definition of the coefficients gives
$$ w(x)=\sum_{k\ge 0} u_k x^{2k} + \sum_{k\ge 0} v_k x^{2k+1} \pmod 2. $$
Factor each sum using powers of $x^2$:
$$ \sum_{k\ge 0} u_k x^{2k}=\sum_{k\ge 0} u_k (x^2)^k = u(x^2), $$
and
$$ \sum_{k\ge 0} v_k x^{2k+1}=x \sum_{k\ge 0} v_k (x^2)^k = x,v(x^2). $$
Hence
$$ w(x)=u(x^2)+x,v(x^2)\pmod 2. $$
Thus the polynomial corresponding to $u \updownarrow v$ is
$$ \boxed{u(x^2)+x,v(x^2)}. $$
This completes the solution. ∎