TAOCP 7.1.3 Exercise 18

The flawed argument fails because it tries to reason at the level of individual bits while treating multiplication as if it were linearly decomposable.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 18. [M25] The curious pixel pattern shown here has $(x^2 y \gg 11) & 1$ in row $x$ and column $y$, for $1 \le x, y \le 256$. Is there any simple way to explain some of its major characteristics mathematically?

Verified: yes
Solve time: 2m40s

The flawed argument fails because it tries to reason at the level of individual bits while treating multiplication as if it were linearly decomposable. A correct explanation must instead treat the expression as arithmetic in a finite 2-adic quotient, where carries are intrinsic rather than exceptional.

1. Reformulation of the problem

The pixel value is

$$ ((x^2 y) \gg 11)\ &\ 1, $$

which is exactly the 11th binary digit of $x^2 y$. Equivalently,

$$ ((x^2 y) \gg 11)\ &\ 1 ;=; \left\lfloor \frac{x^2 y}{2^{11}} \right\rfloor \bmod 2. $$

Thus the pixel is determined by the residue class of $x^2 y$ modulo $2^{12}$, since only the lowest 12 bits of $x^2 y$ affect whether the 11th bit is 0 or 1.

So we work in the ring

$$ \mathbb{Z}/2^{12}\mathbb{Z}, $$

where multiplication automatically includes all carries.

2. Dyadic structure via 2-adic valuation

Write

$$ x = 2^{a} u, \quad y = 2^{b} v, $$

where $u,v$ are odd and $a = v_2(x)$, $b = v_2(y)$.

Then

$$ x^2 y = 2^{2a+b} u^2 v. $$

This immediately produces a rigid structural constraint:

Key observation

If

$$ 2a + b \ge 12, $$

then $x^2 y \equiv 0 \pmod{2^{12}}$, so the 11th bit is always 0.

Hence large rectangular regions of the image are identically blank, determined solely by dyadic divisibility of $x$ and $y$. This already explains the strongest visible block structure.

Because $v_2(x)$ and $v_2(y)$ are constant on intervals of lengths powers of 2, the image is partitioned into dyadic rectangles:

  • $x$ has constant valuation on blocks of size $2^k$,
  • $y$ likewise,

so the condition $2a+b \ge 12$ produces large axis-aligned regions.

3. Reduction within each dyadic block

Fix $a,b$ with $2a+b < 12$. Then in $\mathbb{Z}/2^{12}\mathbb{Z}$,

$$ x^2 y = 2^{2a+b}(u^2 v \bmod 2^{12-(2a+b)}). $$

Thus within each dyadic block determined by $(a,b)$, the pixel depends only on:

$$ u^2 v \bmod 2^{k}, \quad k = 12-(2a+b), $$

where $u,v$ range over odd residues.

Crucially, this dependence is a well-defined modular multiplication, not a linear combination of independent bit patterns. All carries are already encoded in the modular arithmetic.

So the image decomposes into blocks where:

  • the exponent $2^{2a+b}$ controls a rigid shift in binary magnitude,
  • the remaining structure is multiplication of odd residues modulo a smaller power of 2.

4. Source of the visible geometry

Two interacting mechanisms produce the pattern.

(i) Dyadic scaling from powers of 2

The factor $2^{2a+b}$ creates large-scale structure:

  • increasing $v_2(x)$ doubles the exponent in $x^2$,
  • increasing $v_2(y)$ shifts linearly,

so the plane is partitioned into rectangles aligned with powers of 2.

This produces the dominant blocky structure.

(ii) Structured variation from odd parts modulo $2^k$

Inside each block, the behavior is governed by

$$ u^2 v \bmod 2^k, $$

with $u,v$ odd.

This is not random: multiplication modulo $2^k$ has strong algebraic constraints:

  • all odd numbers are units modulo $2^k$,
  • squaring permutes residues within the subgroup of units in a highly structured way,
  • higher bits depend only on progressively smaller truncations of $u$ and $v$.

Thus fine-scale structure appears as repeated motifs within each dyadic block.

5. Why “convolution of bits” is misleading

The previous solution attempted to interpret

$$ x^2 y = \sum x_i x_{i'} y_j 2^{i+i'+j} $$

as if the bit at level 11 were determined independently by tuples with $i+i'+j=11$. This fails because:

  • carries from all lower positions contribute to bit 11,
  • those carries are exactly what modular arithmetic already encodes,
  • there is no decomposition of the bit into independent contributions from bits of $x$ and $y$.

The correct viewpoint replaces bitwise reasoning with arithmetic in $\mathbb{Z}/2^{12}\mathbb{Z}$, where carries are not tracked explicitly but are inherent in the ring structure.

6. Main mathematical explanation of the image

The major characteristics of the pixel pattern are explained by:

  1. 2-adic valuation structure

$$ x^2 y = 2^{2v_2(x)+v_2(y)} \cdot (\text{odd part}), $$

which partitions the image into dyadic rectangles with large constant regions. 2. Modular reduction at $2^{12}$

The pixel depends only on $x^2 y \bmod 2^{12}$, so all computation occurs in a finite ring where carries are intrinsic. 3. Structured multiplication on odd residues

Within each dyadic block, the map $(u,v) \mapsto u^2 v \bmod 2^k$ produces repeating algebraic patterns rather than random behavior.

7. Conclusion

The image is not explained by linear superposition of bit patterns, but by a hierarchy of 2-adic structure:

  • large-scale rectangular regions arise from the valuation $v_2(x^2 y)$,
  • intermediate structure arises from multiplication modulo decreasing powers of 2,
  • fine detail arises from arithmetic of odd units modulo $2^k$.

The visual “banding and self-similarity” is therefore a direct manifestation of 2-adic scaling and modular multiplication, not bitwise convolution.