TAOCP 7.1.2 Exercise 68
Let $x = x_1 \ldots x_n$ and interpret it as an integer k = \sum_{i=1}^n x_i 2^{n-i}, \qquad 0 \le k < 2^n.
Section 7.1.2: Boolean Evaluation
Exercise 68. [M25] Consider the $n$-bit $\pi$ function $\pi_n(x_1 \ldots x_n)$, whose value is the $(x_1 \ldots x_n)$th bit to the right of the most significant bit in the binary representation of $\pi$. Does the method of exercise 4.3.1–39, which describes an efficient way to compute arbitrary bits of $\pi$, prove that $C(\pi_n) < 2^n/n$ for sufficiently large $n$?
Verified: yes
Solve time: 2m30s
Let $x = x_1 \ldots x_n$ and interpret it as an integer
$$ k = \sum_{i=1}^n x_i 2^{n-i}, \qquad 0 \le k < 2^n. $$
The function $\pi_n(x_1,\ldots,x_n)$ is the $k$th bit to the right of the most significant bit in the binary expansion of $\pi$. Thus $\pi_n$ is a Boolean function on $n$ input bits.
We use the method of exercise 4.3.1–39, which gives a BBP-type digit-extraction procedure for $\pi$. The key property of that method is that the $k$th binary digit of $\pi$ can be computed using arithmetic on integers whose lengths are polynomial in $\log k$, and using a number of arithmetic operations that is also polynomial in $\log k$. In other words, there exists a constant $c$ such that the method computes the $k$th bit in time
$$ T(k) = O((\log k)^c). $$
Now substitute $k < 2^n$. Then $\log k \le n$, so
$$ T(k) = O(n^c). $$
Hence the function $\pi_n$ is computable by a deterministic algorithm in time polynomial in $n$.
We now convert this to a Boolean circuit. A standard simulation argument shows that any deterministic algorithm running in time $T(n)$ can be transformed into a Boolean circuit of size $O(T(n)^c)$ for some fixed constant $c$, by unrolling the computation into gates for each step and using polynomial-size circuits for basic arithmetic on $O(n)$-bit numbers. Therefore there exists a constant $c'$ such that
$$ C(\pi_n) \le n^{c'}. $$
Finally, since exponential growth dominates polynomial growth, for sufficiently large $n$ we have
$$ n^{c'} < \frac{2^n}{n}. $$
Thus, for all sufficiently large $n$,
$$ C(\pi_n) < \frac{2^n}{n}. $$
This completes the corrected proof. ∎