Section 3.3.3: Theoretical Tests

Exercise 19. ▶ [M29] Show that the serial test can be analyzed over the full period, in terms of generalized Dedekind sums, by finding a formula for the probability that $0 \le X_n < \beta$ and $a' \le X_{n+1} < \beta'$ when $a$, $\beta$, $a'$, $\beta'$ are given integers with $0 \le \alpha < \beta \le m$ and $0 \le \alpha' < \beta' \le m$. [Hint: Consider the quantity $\lfloor(x - \alpha)/m\rfloor - \lfloor(x - \beta)/m\rfloor$.]

Verified: yes
Solve time: 4m55s

---

Let

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

and assume that the generator has full period $m$. Over one full cycle each residue

$x\in{0,1,\dots,m-1}$ occurs exactly once, so

$$ P(\alpha,\beta,\alpha',\beta') =\frac{N(\alpha,\beta,\alpha',\beta')}{m}, $$

where

$$ N(\alpha,\beta,\alpha',\beta')

#{x:\alpha\le x<\beta,\ \alpha'\le s(x)<\beta'}, $$

with

$$ s(x)=(ax+c)\bmod m . $$

The problem is therefore to evaluate $N$.

1. Indicator functions

For $0\le u<v\le m$, define

$$ I_{u,v}(x)

\Bigl\lfloor\frac{x-u}{m}\Bigr\rfloor

\Bigl\lfloor\frac{x-v}{m}\Bigr\rfloor . $$

If $x\in{0,\dots,m-1}$, then

$$ \Bigl\lfloor\frac{x-u}{m}\Bigr\rfloor

\begin{cases} -1,&x<u,\ 0,&x\ge u, \end{cases} $$

and similarly for $v$. Hence

$$ I_{u,v}(x)

\begin{cases} 1,&u\le x<v,\ 0,&\text{otherwise}. \end{cases} $$

Thus $I_{u,v}$ is exactly the indicator of $[u,v)$ on the residue set

${0,\dots,m-1}$.

Therefore

$$ N

\sum_{x=0}^{m-1} I_{\alpha,\beta}(x), I_{\alpha',\beta'}(s(x)). $$

Expanding,

$$ N

\sum_{\varepsilon\in{\alpha,\beta}} \sum_{\varepsilon'\in{\alpha',\beta'}} \eta(\varepsilon)\eta(\varepsilon') ,T(\varepsilon,\varepsilon'), $$

where

$$ \eta(\alpha)=1,\qquad \eta(\beta)=-1, $$

and

$$ T(u,v)

\sum_{x=0}^{m-1} \Bigl\lfloor\frac{x-u}{m}\Bigr\rfloor \Bigl\lfloor\frac{s(x)-v}{m}\Bigr\rfloor . $$

2. Removing the reduction modulo $m$

Since

$$ s(x)

ax+c

m\Bigl\lfloor\frac{ax+c}{m}\Bigr\rfloor , $$

we have

$$ \Bigl\lfloor\frac{s(x)-v}{m}\Bigr\rfloor

\Bigl\lfloor\frac{ax+c-v}{m}\Bigr\rfloor

\Bigl\lfloor\frac{ax+c}{m}\Bigr\rfloor . $$

Hence

$$ T(u,v)=U(u,v)-U(u,0), $$

where

$$ U(u,v)

\sum_{x=0}^{m-1} \Bigl\lfloor\frac{x-u}{m}\Bigr\rfloor \Bigl\lfloor\frac{ax+c-v}{m}\Bigr\rfloor . $$

Substituting into the inclusion-exclusion formula gives

$$ N

\sum_{\varepsilon,\varepsilon'} \eta(\varepsilon)\eta(\varepsilon') \bigl(U(\varepsilon,\varepsilon')-U(\varepsilon,0)\bigr). $$

Since

$$ \sum_{\varepsilon'\in{\alpha',\beta'}} \eta(\varepsilon')

1-1

0, $$

all $U(\varepsilon,0)$ terms cancel, leaving

$$ N

\sum_{\varepsilon\in{\alpha,\beta}} \sum_{\varepsilon'\in{\alpha',\beta'}} \eta(\varepsilon)\eta(\varepsilon') ,U(\varepsilon,\varepsilon'). $$

This is the step omitted in the flawed solution.

3. Reduction to generalized Dedekind sums

Introduce the sawtooth function

$$ ((t))

\begin{cases} t-\lfloor t\rfloor-\dfrac12,&t\notin\mathbf Z,\[1ex] 0,&t\in\mathbf Z. \end{cases} $$

For every real $t$,

$$ \lfloor t\rfloor

t-\frac12-((t)) +\frac12\delta(t), $$

where

$$ \delta(t)= \begin{cases} 1,&t\in\mathbf Z,\ 0,&t\notin\mathbf Z. \end{cases} $$

Applying this to both floor factors in $U(u,v)$ yields a sum of:

1. constant terms;
2. linear sawtooth sums;
3. a bilinear sawtooth sum;
4. finitely many $\delta$-correction terms.

The $\delta$-terms are completely explicit because

$$ \delta!\left(\frac{x-u}{m}\right) $$

is nonzero for exactly one residue $x\equiv u\pmod m$, and similarly

$$ \delta!\left(\frac{ax+c-v}{m}\right) $$

is nonzero for exactly one residue when $(a,m)=1$. Thus the correction terms contribute only explicit endpoint constants.

The essential term is

$$ \sum_{x=0}^{m-1} \left(\left(\frac{x-u}{m}\right)\right) \left(\left(\frac{ax+c-v}{m}\right)\right), $$

which is precisely a generalized Dedekind sum. Writing

$$ D(a,m;u,v-c)

\sum_{x=0}^{m-1} \left(\left(\frac{x-u}{m}\right)\right) \left(\left(\frac{ax+c-v}{m}\right)\right), $$

we obtain

$$ U(u,v)

E(u,v)+D(a,m;u,v-c), $$

where $E(u,v)$ is an explicit elementary expression coming from the constant, linear, and $\delta$-terms.

Consequently

$$ N(\alpha,\beta,\alpha',\beta')

\sum_{\varepsilon\in{\alpha,\beta}} \sum_{\varepsilon'\in{\alpha',\beta'}} \eta(\varepsilon)\eta(\varepsilon') \Bigl( E(\varepsilon,\varepsilon') + D(a,m;\varepsilon,\varepsilon'-c) \Bigr). $$

Equivalently,

$$ \boxed{ N(\alpha,\beta,\alpha',\beta')

\sum_{\varepsilon\in{\alpha,\beta}} \sum_{\varepsilon'\in{\alpha',\beta'}} \eta(\varepsilon)\eta(\varepsilon') ,D(a,m;\varepsilon,\varepsilon'-c) + E_{\alpha,\beta,\alpha',\beta'} } $$

with $E_{\alpha,\beta,\alpha',\beta'}$ completely explicit and elementary.

Therefore

$$ \boxed{ P(\alpha,\beta,\alpha',\beta')

\frac1m \left( E_{\alpha,\beta,\alpha',\beta'} + \sum_{\varepsilon\in{\alpha,\beta}} \sum_{\varepsilon'\in{\alpha',\beta'}} \eta(\varepsilon)\eta(\varepsilon') D(a,m;\varepsilon,\varepsilon'-c) \right). } $$

This expresses the serial-test probability over the full period as a finite inclusion-exclusion combination of generalized Dedekind sums, exactly as required.