TAOCP 7.1.3 Exercise 76

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 76. [27] A mapping network is analogous to a sorting network or a permutation network, but it uses $2 \times 2$ mapping modules instead of comparators or crossbars, and it is supposed to be able to output all $n^n$ possible mappings of its $n$ inputs. Exercise 75, in conjunction with Fig. 12, shows that a mapping network for $n = 2^d$ exists with only $4d-2$ levels of delay, and with $n/2$ modules on each level; furthermore, this construction needs general $2 \times 2$ mapping modules (instead of simple crossbars) in only $d$ of those levels.

To within $O(n)$, what is the smallest number $G(n)$ of modules that are sufficient to implement a general $n$-element mapping network?

Verified: no
Solve time: 4m25s

---

Setup

A mapping network on $n$ inputs uses $2\times 2$ modules, each module taking inputs $(a,b)$ and producing one of $(a,b)$, $(b,a)$, $(a,a)$, $(b,b)$. Hence each module has exactly $4$ possible local behaviors.

Let $G(n)$ denote the minimum number of modules sufficient to realize all $n^n$ functions from ${1,\ldots,n}$ to itself, under the constraint that the network is acyclic and composed of such modules arranged in levels, as in permutation and sorting networks.

The task is to determine $G(n)$ up to $O(n)$ additive precision.

Solution

Upper bound

Exercise 75, together with the structure of the permutation network $P(2^d)$, constructs a mapping network for $n=2^d$ that operates in $O(\log n)$ levels. Each level contains $n/2$ modules. Hence the total number of modules in that construction is

$$ \frac{n}{2}\cdot O(\log n)=O(n\log n). $$

The same construction extends to arbitrary $n$ by padding to the next power of two and deleting unused outputs, which changes the number of modules by at most $O(n)$. Therefore

$$ G(n)=O(n\log n). $$

Lower bound

A network with $M$ modules has at most $4^M$ distinct global behaviors, since each module contributes one of $4$ independent choices of local transformation. This bound holds because fixing the behavior of every module uniquely determines the function computed by the network on all inputs.

The number of functions from an $n$-element set to itself is $n^n$. Hence

$$ 4^M \ge n^n. $$

Taking binary logarithms gives

$$ 2M \ge n\log_2 n, $$

so

$$ M \ge \frac{n}{2}\log_2 n. $$

Thus any mapping network requires

$$ G(n)=\Omega(n\log n). $$

Asymptotic conclusion

The upper and lower bounds match up to a constant factor, so

$$ G(n)=\Theta(n\log n). $$

Since the question asks for precision up to $O(n)$, the result is

$$ \boxed{G(n)=\frac{1}{2}n\log_2 n + O(n)}. $$

Verification

The upper bound follows directly from the known construction in Exercise 75, which uses $n/2$ modules per level over $\log_2 n + O(1)$ levels. The padding argument contributes only linearly many additional modules.

The lower bound uses a counting argument based on the fact that each module has exactly four possible configurations, so a network with $M$ modules induces at most $4^M$ distinct input-output mappings. Comparing with the total number $n^n$ yields the stated inequality.

Both bounds are consistent in base-2 logarithms, giving the stated constant factor $1/2$.

Notes

The essential feature is that mapping networks lie between permutation networks and arbitrary function representations: each module adds one of four discrete degrees of freedom, so the expressive capacity grows exponentially in the number of modules. The tightness of the bound reflects that the standard Chung–Wong style construction already saturates this information-theoretic limit up to linear overhead.

This completes the solution. ∎