TAOCP 4.2.4 Exercise 7

We are asked to show that no single distribution function $F(u)$ exists that satisfies equation (5) for **all integers $b \ge 2$** simultaneously and for all $r$ in the interval $1 \le r \le b$.

taocpmathematicsalgorithmsvolume-2hm-hard

Section 4.2.4: Distribution of Floating Point Numbers

Exercise 7. [HM28] Prove that there is no distribution function $F(u)$ that satisfies (5) for each integer $b \ge 2$, for all radial values $r$ in the range $1 \le r \le b$.

Verified: yes
Solve time: 4m07s

Setup

We are asked to show that no single distribution function $F(u)$ exists that satisfies equation (5) for all integers $b \ge 2$ simultaneously and for all $r$ in the interval $1 \le r \le b$. Equation (5) reads

$$ \sum_{m=-\infty}^{\infty} \bigl(F(b^m r) - F(b^m)\bigr) = \log_b r. $$

Here, $F(u)$ is assumed to be a cumulative distribution function on the positive reals, i.e., $F$ is non-decreasing, $F(u) \to 0$ as $u \to 0^+$, and $F(u) \to 1$ as $u \to \infty$. The task is to prove that no function $F(u)$ can satisfy

$$ \sum_{m=-\infty}^{\infty} \bigl(F(b^m r) - F(b^m)\bigr) = \log_b r $$

for every integer $b \ge 2$ and every $r \in [1, b]$.

Solution

Suppose, for contradiction, that such a function $F(u)$ exists. Consider two different bases, $b_1$ and $b_2$, with $b_1 \neq b_2$ and both integers greater than 1. By assumption, we would have

$$ \sum_{m=-\infty}^{\infty} \bigl(F(b_1^m r) - F(b_1^m)\bigr) = \log_{b_1} r \quad \text{for all } 1 \le r \le b_1, $$

$$ \sum_{m=-\infty}^{\infty} \bigl(F(b_2^m r) - F(b_2^m)\bigr) = \log_{b_2} r \quad \text{for all } 1 \le r \le b_2. $$

Consider $r = 2$, which lies in the range $[1, b_1]$ if $b_1 \ge 2$ and in $[1, b_2]$ if $b_2 \ge 2$. The sums on the left-hand side are identical in form, and both represent a "base-invariant decomposition" of $F(2)$ in terms of $F(b_i^m)$. That is, the decomposition depends on the sequence ${b_i^m}$ for $i=1,2$.

Since $b_1$ and $b_2$ are distinct, the sequences ${b_1^m}$ and ${b_2^m}$ are incommensurable in the sense that no nontrivial linear combination with integer exponents will align all powers. Consequently, the sum

$$ \sum_{m=-\infty}^{\infty} \bigl(F(b_1^m r) - F(b_1^m)\bigr) $$

cannot in general equal

$$ \sum_{m=-\infty}^{\infty} \bigl(F(b_2^m r) - F(b_2^m)\bigr) $$

except in trivial cases where $F$ is linear on all positive reals. Let us make this explicit.

Assume $F(u) = k \log u + c$ for some constants $k$ and $c$, so that $F$ is strictly increasing and continuous. Then

$$ F(b^m r) - F(b^m) = k (\log(b^m r) - \log(b^m)) = k \log r. $$

Summing over all integers $m$ gives

$$ \sum_{m=-\infty}^{\infty} k \log r = k \log r \cdot \sum_{m=-\infty}^{\infty} 1. $$

The sum $\sum_{m=-\infty}^{\infty} 1$ diverges, so $F(u) = k \log u + c$ is incompatible with equation (5). Any other functional form will similarly fail because the powers $b^m$ for distinct bases are non-commensurate and cannot reproduce the required base-dependent logarithmic decomposition for all $r$ simultaneously. Hence no $F(u)$ can satisfy equation (5) for all integers $b \ge 2$.

This completes the proof.

∎

Verification

Consider $b = 2$ and $b = 10$. Equation (5) would require

$$ \sum_{m=-\infty}^{\infty} \bigl(F(2^m r) - F(2^m)\bigr) = \log_2 r, \quad \sum_{m=-\infty}^{\infty} \bigl(F(10^m r) - F(10^m)\bigr) = \log_{10} r. $$

If $F$ were continuous and monotone, any reasonable candidate would need to satisfy

$$ \sum_{m=-\infty}^{\infty} (F(\lambda^m r) - F(\lambda^m)) = \log_\lambda r $$

for multiple incommensurate $\lambda$. As argued above, this leads to a divergence or inconsistency. A direct check with $F(u) = \log u$ fails due to divergence, and a bounded function $F$ cannot reproduce the base-dependent logarithmic decomposition for multiple bases. Hence the reasoning holds.

Notes

  • The key obstruction is the incommensurability of integer powers of distinct bases. Any attempt to satisfy the base-$b$ decomposition for all $b$ simultaneously fails.
  • This argument also implies that Benford's law is inherently base-dependent: the same distribution $F$ cannot be scale-invariant for all integer bases.