TAOCP 3.5 Exercise 17

Section 3.5: What Is a Random Sequence?

Exercise 17. [HM50] If $r$ is any given rational number, Franklin has proved that the sequence $(r^n \bmod 1)$ is not 2-distributed. But is there any rational number $r$ for which this sequence is equidistributed? In particular, is the sequence equidistributed when $r = \frac{3}{2}$? [See K. Mahler, Mathematika 4 (1957), 122–124.]

Verified: yes
Solve time: 1m13s

Setup

Let $r = p/q$ be a rational number with $\gcd(p,q) = 1$, $q \ge 1$, and consider the sequence

$U_n = r^n \bmod 1, \quad n = 0, 1, 2, \ldots,$

viewed as a $[0,1)$ sequence. A sequence $(U_n)$ is equidistributed if for all real numbers $0 \le u < v \le 1$ we have

$\lim_{N \to \infty} \frac{1}{N} #{0 \le n < N : u \le U_n < v} = v - u.$

We are asked to determine whether there exists a rational $r$ such that $(r^n \bmod 1)$ is equidistributed, and in particular whether $r = 3/2$ produces an equidistributed sequence.

Solution

Let $r = p/q$ with $p > q \ge 1$ and $\gcd(p,q) = 1$. Then

$U_n = \left(\frac{p}{q}\right)^n \bmod 1 = \frac{p^n}{q^n} \bmod 1 = \frac{p^n \bmod q^n}{q^n}.$

Observe that $p^n \bmod q^n$ can take at most $q^n$ distinct integer values, all lying in ${0,1,\dots,q^n - 1}$. Therefore $U_n$ belongs to the finite set

$\mathcal{S}_n = \left{0, \frac{1}{q^n}, \frac{2}{q^n}, \dots, \frac{q^n - 1}{q^n}\right}.$

We now consider the case $r = 3/2$. Then

$U_0 = 1, \quad U_1 = 3/2 \bmod 1 = 1/2, \quad U_2 = (3/2)^2 \bmod 1 = 9/4 \bmod 1 = 1/4, \quad U_3 = (3/2)^3 \bmod 1 = 27/8 \bmod 1 = 3/8, \ldots$

A key observation is that for any rational $r = p/q$ with $q > 1$, the sequence $(r^n \bmod 1)$ takes values in the additive group generated by $1/q$ under multiplication by $p$. In particular, it is always contained in the set of rational numbers with denominators that are powers of $q$. Consequently, the sequence is not dense in $[0,1)$, because it cannot approximate arbitrary real numbers to arbitrary precision. Equidistribution requires that for any interval $[u,v) \subset [0,1)$, the fraction of terms in that interval converges to $v-u$, which is impossible if the sequence cannot approach all points densely.

Formally, if the sequence were equidistributed, then for any $0 < \varepsilon < 1/q$, the interval $[0, \varepsilon)$ would eventually contain some term $U_n$. But $U_n$ always has denominator $q^n$, so for $n$ large enough, $U_n \ge 1/q^n > \varepsilon$. This contradiction shows that $(r^n \bmod 1)$ is never equidistributed when $r$ is rational with $q > 1$.

The only remaining case is $q = 1$, i.e., $r$ is an integer. If $r = 1$, then $U_n = 0$ for all $n \ge 1$, which is clearly not equidistributed. If $r = k \ge 2$, then $U_n = k^n \bmod 1 = 0$ for all $n \ge 1$, again not equidistributed. Therefore, no rational $r$ produces an equidistributed sequence.

Verification

Consider the denominators of terms in the sequence. If $r = p/q$ with $q > 1$, then $U_n = p^n/q^n \bmod 1$ has denominator $q^n$, a strictly increasing sequence of integers. Equidistribution requires that, for any interval $[u,v)$, there exists a term in that interval for all sufficiently large $n$. However, $U_n \in {0, 1/q^n, \dots, (q^n-1)/q^n}$, which means the minimal positive value is $1/q^n > 0$, and for $n$ large enough it exceeds any fixed small interval. This confirms that $(r^n \bmod 1)$ cannot be equidistributed.

For $r = 3/2$, the denominators of the sequence are powers of $2$, and the sequence takes values in ${0, 1/2, 1/4, 3/4, 1/8, 3/8, \dots}$, a set that is not dense in $[0,1)$. Thus $r = 3/2$ does not yield an equidistributed sequence.

Notes

A more general statement, proved by Mahler, is that for any rational $r \neq \pm 1$, the sequence $(r^n \bmod 1)$ is not even 2-distributed, as noted in the exercise. The intuition is that rational powers modulo 1 can only produce finitely many fractional parts modulo 1 over integer exponents. Equidistribution is only possible for irrational $r$ in certain situations, for example, when $r$ is a Pisot number or satisfies certain Diophantine conditions.

This completes the proof.

∎

$$ \boxed{\text{No rational number } r \text{ produces an equidistributed sequence } (r^n \bmod 1), \text{ in particular } r = 3/2 \text{ does not.}} $$