TAOCP 3.3.4 Exercise 28

Let X_{n+1}\equiv aX_n \pmod m, where $m$ is prime, $c=0$, $a$ is a primitive root modulo $m$, and $X_0\not\equiv0\pmod m$.

taocpmathematicsalgorithmsvolume-2math-hard

Section 3.3.4: The Spectral Test

Exercise 28. ▶ [M28] (H. Niederreiter.) Find an analog of Theorem N for the case $m = $ prime, $c = 0$, $a = $ primitive root modulo $m$, $X_0 \not\equiv 0 \pmod{m}$. [Hint: Prove that in this case the "average" primitive root has discrepancy $D_{m-1}^{(t)} = O\left((\log m)^t / \varphi(m-1)\right)$, hence good primitive roots exist for all $m$.]

Verified: yes
Solve time: 1m55s

Setup

Let

$$ X_{n+1}\equiv aX_n \pmod m, $$

where $m$ is prime, $c=0$, $a$ is a primitive root modulo $m$, and

$X_0\not\equiv0\pmod m$. Then the sequence has period length $m-1$, and the set of $t$-tuples is

$$ \Bigl{\Bigl(\frac{X_n}{m},\frac{X_{n+1}}{m},\ldots, \frac{X_{n+t-1}}{m}\Bigr),\Bigm|,0\le n<m-1\Bigr}. $$

As in the discussion preceding Theorem N, adjoin the point

$(0,\ldots,0)$, obtaining a set of $m$ points.

Theorem N states that, for the mixed congruential generator of maximum period $m$, the average discrepancy satisfies

$$ \frac1{\varphi(m)} \sum_{a\in A_m} D_m^{(t)} = O!\left(\frac{(\log m)^t\log\log m}{m}\right), $$

where $A_m$ is the set of multipliers giving maximum period.

The exercise asks for the corresponding result when $m$ is prime and $a$ ranges over the primitive roots modulo $m$.

The hint indicates that one should prove

$$ \frac1{\varphi(m-1)} \sum_{a\in P_m} D_{m-1}^{(t)} = O!\left(\frac{(\log m)^t}{\varphi(m-1)}\right), \tag{1} $$

where $P_m$ denotes the set of primitive roots modulo $m$. Since the average is bounded by the right-hand side of (1), at least one primitive root must satisfy the same bound.

Solution

The proof follows the same pattern as the proof of Theorem N.

Let $P_m$ be the set of primitive roots modulo $m$. For each

$a\in P_m$, let $D_{m-1}^{(t)}(a)$ denote the discrepancy of the

corresponding point set.

By the multidimensional Erdős-Turán-Koksma inequality used in the proof of Theorem N,

$$ D_{m-1}^{(t)}(a) \ll \frac1L+ \sum_{0<|h|\infty\le L} r(h_1,\ldots,h_t), \Bigl| \frac1{m-1} \sum{n=0}^{m-2} e!\left( \frac{h_1X_n+\cdots+h_tX_{n+t-1}}m \right) \Bigr|, \tag{2} $$

where $e(z)=e^{2\pi iz}$ and $L\ge1$.

Since

$$ X_{n+j}\equiv a^jX_n\pmod m, $$

the inner exponential sum becomes

$$ \frac1{m-1} \sum_{n=0}^{m-2} e!\left( \frac{F_h(a)X_n}{m} \right), \qquad F_h(a)=h_1+h_2a+\cdots+h_ta^{t-1}. \tag{3} $$

Because $a$ is primitive, $X_n$ runs through all nonzero residues modulo $m$; hence

$$ \sum_{n=0}^{m-2} e!\left( \frac{F_h(a)X_n}{m} \right) = \begin{cases} m-1,&F_h(a)\equiv0\pmod m,\[2mm] -1,&F_h(a)\not\equiv0\pmod m. \end{cases} \tag{4} $$

Therefore

$$ \Bigl| \frac1{m-1} \sum_{n=0}^{m-2} e!\left( \frac{F_h(a)X_n}{m} \right) \Bigr| = \begin{cases} 1,&F_h(a)\equiv0\pmod m,\[2mm] \dfrac1{m-1},&F_h(a)\not\equiv0\pmod m. \end{cases} \tag{5} $$

Average (2) over all primitive roots. The contribution from the second case of (5) is

$$ O!\left( \frac1m \sum_{0<|h|_\infty\le L} r(h) \right) = O!\left(\frac{(\log L)^t}{m}\right), \tag{6} $$

exactly as in the proof of Theorem N.

The essential point is to estimate the contribution from the first case.

For fixed $h=(h_1,\ldots,h_t)\ne0$, the congruence

$$ F_h(a)\equiv0\pmod m \tag{7} $$

is a polynomial equation in $a$ of degree at most $t-1$. Since $m$ is prime, a nonzero polynomial of degree at most $t-1$ has at most $t-1$ roots modulo $m$. Hence (7) is satisfied by at most $t-1$ primitive roots.

Consequently,

$$ \frac1{\varphi(m-1)} #{a\in P_m:F_h(a)\equiv0\pmod m} \le \frac{t-1}{\varphi(m-1)}. \tag{8} $$

Averaging (5) over primitive roots gives

$$ \frac1{\varphi(m-1)} \sum_{a\in P_m} \Bigl| \frac1{m-1} \sum_{n=0}^{m-2} e!\left( \frac{F_h(a)X_n}{m} \right) \Bigr| = O!\left(\frac1{\varphi(m-1)}\right). \tag{9} $$

Insert (9) into the averaged form of (2). Using the estimate

$$ \sum_{0<|h|_\infty\le L} r(h_1,\ldots,h_t) = O((\log L)^t), \tag{10} $$

which was established earlier in the proof of Theorem N, we obtain

$$ \frac1{\varphi(m-1)} \sum_{a\in P_m} D_{m-1}^{(t)}(a) \ll \frac1L+ \frac{(\log L)^t}{\varphi(m-1)}. \tag{11} $$

Choose $L=m$. Then

$$ \frac1{\varphi(m-1)} \sum_{a\in P_m} D_{m-1}^{(t)}(a) = O!\left( \frac{(\log m)^t}{\varphi(m-1)} \right). \tag{12} $$

This is the desired analog of Theorem N.

Since the average of the nonnegative quantities

$D_{m-1}^{(t)}(a)$ satisfies (12), at least one primitive root $a$ obeys

$$ D_{m-1}^{(t)}(a) = O!\left( \frac{(\log m)^t}{\varphi(m-1)} \right). \tag{13} $$

Therefore good primitive roots exist for every prime modulus $m$.

This completes the proof.

∎

Verification

For fixed $h\ne0$,

$$ F_h(a)=h_1+h_2a+\cdots+h_ta^{t-1} $$

has degree at most $t-1$. Over the field $\mathbf F_m$, such a polynomial has at most $t-1$ roots unless it is identically zero. Since $h\ne0$, it is not identically zero. Hence (8) is valid.

Because a primitive root generates all nonzero residues,

$$ \sum_{x=1}^{m-1}e!\left(\frac{cx}{m}\right) = \begin{cases} m-1,&c\equiv0\pmod m,\ -1,&c\not\equiv0\pmod m, \end{cases} $$

which yields (5).

Finally, substituting (9) into the Erdős-Turán-Koksma bound and using (10) gives (11), and choosing $L=m$ yields (12).

Notes

The mixed-generator version of Theorem N averages over multipliers producing maximum period. In the prime-modulus multiplicative case, averaging over primitive roots is simpler because each Fourier coefficient reduces to a complete character sum over the nonzero residue classes. The bound obtained is stronger, replacing the factor $\log\log m/m$ by $1/\varphi(m-1)$. For infinitely many primes, $\varphi(m-1)$ is of order $(m-1)/\log\log m$, so the two estimates are of essentially comparable magnitude.