TAOCP 3.3.4 Exercise 26

Consider a linear congruential sequence $(X_n)$ defined by $X_{n+1} = (a X_n + c) \bmod m, \quad 0 \le X_n < m,$ with full period length $m$.

taocpmathematicsalgorithmsvolume-2math-medium

Section 3.3.4: The Spectral Test

Exercise 26. [M22] Explain why the derivation of ($x_3$) leads to a similar bound on

$$\left|\sum_{0 \le n < N} e^{2\pi i u X_n}\right|$$

for $0 < q < m$.

Verified: no
Solve time: 3m33s

Solution

Consider a linear congruential sequence $(X_n)$ defined by

$X_{n+1} = (a X_n + c) \bmod m, \quad 0 \le X_n < m,$

with full period length $m$. Let $0 < q < m$ be an integer, and define

$S_N = \sum_{0 \le n < N} e^{2\pi i u X_n/m},$

where $u$ is an integer not divisible by $m$. We wish to show that the derivation of ($x_3$) in Section 3.3.4 leads to a bound on $|S_N|$ similar to that obtained there.

The derivation of ($x_3$) bounds sums of the form

$\sum_{0 \le n < N} e^{2\pi i (u_1 X_n + u_2 X_{n+1})/m}$

by expressing $X_{n+1}$ in terms of $X_n$, which converts the sum into a geometric progression modulo $m$. Specifically, since

$X_{n+1} \equiv a X_n + c \pmod m,$

we can write

$e^{2\pi i u X_{n+1}/m} = e^{2\pi i u (a X_n + c)/m} = e^{2\pi i u c/m} \cdot \bigl(e^{2\pi i u a/m}\bigr)^{X_n}.$

Consequently, the sum $S_N$ becomes

$S_N = \sum_{0 \le n < N} \left(e^{2\pi i u a/m}\right)^{X_n} \cdot e^{2\pi i u c/m} = e^{2\pi i u c/m} \sum_{0 \le n < N} \left(e^{2\pi i u a/m}\right)^{X_n}.$

The sequence $(X_n)$ itself is generated linearly modulo $m$, so the values of $X_n$ are distinct modulo $m$ over a full period. Hence, the sum

$\sum_{0 \le n < m} \left(e^{2\pi i u a/m}\right)^{X_n}$

is a geometric series with ratio $\rho = e^{2\pi i u a/m} \ne 1$ for $0 < u < m$. The standard geometric sum formula gives

$\left|\sum_{0 \le n < m} \rho^n\right| = \left|\frac{1 - \rho^m}{1 - \rho}\right| \le \frac{2}{|1 - \rho|}.$

Applying the inequality $|1 - e^{2\pi i \theta}| \ge 2 |\theta|$ for $0 \le \theta \le 1/2$, with $\theta = u a / m \bmod 1$, we obtain

$|S_N| \le \frac{1}{|\sin(\pi u a/m)|} \le \frac{m}{\pi \min(u a \bmod m, m - u a \bmod m)}.$

This is precisely the type of bound derived in ($x_3$), where the exponential sum over two consecutive terms is reduced to a geometric progression and bounded in terms of the minimal distance to an integer multiple of $m$.

Hence, for any $0 < q < m$, the sum

$\sum_{0 \le n < N} e^{2\pi i u X_n/m}$

satisfies a bound of the same form as in ($x_3$), namely, an absolute value bounded by a multiple of $m$ divided by the minimal fractional distance of $u a / m$ to an integer. This completes the argument. ∎