#LyX 2.4 created this file. For more info see https://www.lyx.org/
\lyxformat 620
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass book
\begin_preamble
\input defs
\end_preamble
\use_default_options true
\maintain_unincluded_children no
\language english
\language_package default
\inputencoding utf8
\fontencoding auto
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_roman_osf false
\font_sans_osf false
\font_typewriter_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\float_placement class
\float_alignment class
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry false
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification true
\use_refstyle 1
\use_formatted_ref 0
\use_minted 0
\use_lineno 0
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style english
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tablestyle default
\tracking_changes false
\output_changes false
\change_bars false
\postpone_fragile_content false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\docbook_table_output 0
\docbook_mathml_prefix 1
\end_header

\begin_body

\begin_layout Subsubsection
First Set
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
exerc1[M10]
\end_layout

\end_inset

Express 
\begin_inset Formula $x\bmod y$
\end_inset

 in terms of the sawtooth and 
\begin_inset Formula $\delta$
\end_inset

 functions.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

We have 
\begin_inset Formula $((x))-\frac{1}{2}\delta(x)=x-\lfloor x\rfloor-\frac{1}{2}$
\end_inset

,
 so 
\begin_inset Formula $\lfloor x\rfloor=x-((x))+\tfrac{1}{2}(\delta(x)-1)$
\end_inset

.
 Therefore
\begin_inset Formula 
\begin{multline*}
x\bmod y=x-y\left\lfloor \frac{x}{y}\right\rfloor =x-y\left(\frac{x}{y}-\left(\left(\frac{x}{y}\right)\right)+\frac{1}{2}\left(\delta(\tfrac{x}{y})-1\right)\right)=\\
=\left(\left(\left(\frac{x}{y}\right)\right)+\frac{1-\delta(\frac{x}{y})}{2}\right)y.
\end{multline*}

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc4[M19]
\end_layout

\end_inset

If 
\begin_inset Formula $m=10^{10}$
\end_inset

,
 what is the highest possible value of 
\begin_inset Formula $d$
\end_inset

 (in the notation of Theorem P),
 given that the potency of the generator is 10?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

It's 
\begin_inset Formula $d=2\cdot5^{10}$
\end_inset

.
 First,
 we note that 
\begin_inset Formula 
\[
(2\cdot5^{10})^{9}\bmod10^{10}=2^{9}5^{90}\bmod2^{10}5^{10}=2^{9}5^{10}(5^{80}\bmod2)=m/2\neq0,
\]

\end_inset

 and that 
\begin_inset Formula $(2\cdot5^{10})^{10}\bmod10^{10}=2^{10}5^{100}\bmod2^{10}5^{10}=0$
\end_inset

,
 so if 
\begin_inset Formula $b=d$
\end_inset

 we have potency 10.
 Second,
 we note that,
 since 
\begin_inset Formula $d\mid m$
\end_inset

,
 and any divisor of 
\begin_inset Formula $m$
\end_inset

 greater that 
\begin_inset Formula $2\cdot5^{10}$
\end_inset

 has to be a multiple at least of 
\begin_inset Formula $2^{2}$
\end_inset

 and of 
\begin_inset Formula $5^{2}$
\end_inset

,
 and therefore of 100,
 then 
\begin_inset Formula $b$
\end_inset

 would have to be a multiple of 100 and the potency would be at most 5.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc7[M24]
\end_layout

\end_inset

Give a proof of the reciprocity law (19),
 when 
\begin_inset Formula $c=0$
\end_inset

,
 by using the general reciprocity law of exercise 1.2.4–45.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset


\begin_inset Note Greyedout
status open

\begin_layout Plain Layout
(I had to look up the solution,
 obviously.)
\end_layout

\end_inset

In this case,
 the law reduces to
\begin_inset Formula 
\begin{multline*}
\sigma(h,k,0)+\sigma(k,h,0)=\\
=12\sum_{0\leq j<k}\left(\left(\frac{j}{k}\right)\right)\left(\left(\frac{hj}{k}\right)\right)+12\sum_{0\leq j<h}\left(\left(\frac{j}{h}\right)\right)\left(\left(\frac{kj}{h}\right)\right)=\frac{h}{k}+\frac{k}{h}+\frac{1}{hk}-3.
\end{multline*}

\end_inset

where 
\begin_inset Formula $0<h\leq k$
\end_inset

 are coprime integers.
 The last equation from exercise 1.2.4–45 with 
\begin_inset Formula $k=2$
\end_inset

 tells us that
\begin_inset Formula 
\[
\sum_{1\leq j<n}\left\lfloor \frac{mj}{n}\right\rfloor \left(\left\lfloor \frac{mj}{n}\right\rfloor +1\right)+2\sum_{1\leq j<m}j\left\lceil \frac{jn}{m}\right\rceil =nm(m-1)
\]

\end_inset

for 
\begin_inset Formula $m,n\in\mathbb{N}$
\end_inset

,
 where we multiply by 2 and then set the lower bound of the sums to 1 because terms with 
\begin_inset Formula $j=0$
\end_inset

 evaluate to 0.
 Now,
 since 
\begin_inset Formula $h$
\end_inset

 and 
\begin_inset Formula $k$
\end_inset

 are coprime,
 for 
\begin_inset Formula $j\in\{1,\dots,k-1\}$
\end_inset

,
\begin_inset Formula 
\begin{align*}
\left(\left(\frac{hj}{k}\right)\right) & =\frac{hj}{k}-\left\lfloor \frac{hj}{k}\right\rfloor -\frac{1}{2}=\frac{hj}{k}-\left\lceil \frac{hj}{k}\right\rceil +\frac{1}{2},
\end{align*}

\end_inset

so substituting above,
\begin_inset Formula 
\begin{multline*}
S\coloneqq kh(h-1)=\\
=\sum_{j=1}^{k-1}\left(\frac{hj}{k}-\left(\left(\frac{hj}{k}\right)\right)-\frac{1}{2}\right)\left(\frac{hj}{k}-\left(\left(\frac{hj}{k}\right)\right)+\frac{1}{2}\right)+\\
+2\sum_{j=1}^{h-1}j\left(\frac{kj}{h}-\left(\left(\frac{kj}{h}\right)\right)+\frac{1}{2}\right)=\\
=\frac{h^{2}}{k^{2}}\sum_{j=1}^{k-1}j^{2}-\frac{2h}{k}\sum_{j=1}^{k-1}j\left(\left(\frac{hj}{k}\right)\right)+\sum_{j=1}^{k-1}\left(\left(\frac{hj}{k}\right)\right)^{2}-\frac{k-1}{4}+\frac{2k}{h}\sum_{j=1}^{h-1}j^{2}-\\
-2\sum_{j=1}^{h-1}j\left(\left(\frac{kj}{h}\right)\right)+\frac{h^{2}-h}{2}.
\end{multline*}

\end_inset

Now,
\begin_inset Formula 
\begin{align*}
\sum_{j=1}^{k-1}\left(\left(\frac{hj}{k}\right)\right) & =\sum_{j=1}^{k-1}\left(\left(\frac{j}{k}\right)\right)=\sum_{j=1}^{k-1}\left(\frac{j}{k}-\frac{1}{2}\right)=\frac{k(k-1)}{2k}-\frac{k-1}{2}=0,
\end{align*}

\end_inset

so
\begin_inset Formula 
\begin{multline*}
\sigma(h,k,0)=12\sum_{j=0}^{k-1}\left(\left(\frac{j}{k}\right)\right)\left(\left(\frac{hj}{k}\right)\right)=12\sum_{j=1}^{k-1}\left(\frac{j}{k}-\frac{1}{2}\right)\left(\left(\frac{hj}{k}\right)\right)=\\
=12\sum_{j=1}^{k-1}\frac{j}{k}\left(\left(\frac{hj}{k}\right)\right).
\end{multline*}

\end_inset

In addition,
\begin_inset Formula 
\[
\sum_{j=1}^{k-1}j^{2}=\frac{(k-1)k(2k-1)}{6}=\frac{k}{6}(2k^{2}-3k+1)=\frac{k^{3}}{3}-\frac{k^{2}}{2}+\frac{k}{6},
\]

\end_inset

and in particular
\begin_inset Formula 
\begin{align*}
\sum_{j=1}^{k-1}\left(\left(\frac{hj}{k}\right)\right)^{2} & =\sum_{j=1}^{k-1}\left(\left(\frac{j}{k}\right)\right)^{2}\\
 & =\sum_{j=1}^{k-1}\frac{j^{2}}{k^{2}}-\sum_{j=1}^{k-1}\frac{j}{k}+\frac{k-1}{4}=\frac{k}{3}-\frac{1}{2}+\frac{1}{6k}-\frac{k-1}{2}+\frac{k-1}{4}\\
 & =\frac{k}{3}-\frac{1}{2}+\frac{1}{6k}-\frac{k-1}{4},
\end{align*}

\end_inset

so finally
\begin_inset Formula 
\begin{align*}
S= & \frac{kh^{2}}{3}-\frac{h^{2}}{2}+\frac{h^{2}}{6k}-\frac{h}{6}\sigma(h,k,0)+\frac{k}{3}-\frac{1}{2}+\frac{1}{6k}-\frac{k-1}{2}+\frac{2kh^{2}}{3}-kh+\\
 & +\frac{k}{3}-\frac{h}{6}\sigma(k,h,0)+\frac{h^{2}}{2}-\frac{h}{2}\\
= & kh(h-1)-\frac{h}{2}+\frac{h^{2}}{6k}+\frac{k}{6}+\frac{1}{6k}-\frac{h}{6}\sigma(h,k,0)-\frac{h}{6}\sigma(k,h,0).
\end{align*}

\end_inset

With this,
\begin_inset Formula 
\[
\sigma(h,k,0)+\sigma(k,h,0)=-3+\frac{h}{k}+\frac{k}{h}+\frac{1}{hk}.
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc14[M20]
\end_layout

\end_inset

The linear congruential generator that has 
\begin_inset Formula $m=2^{35}$
\end_inset

,
 
\begin_inset Formula $a=2^{18}+1$
\end_inset

,
 
\begin_inset Formula $c=1$
\end_inset

,
 was given the serial correlation test on three batches of 1000 consecutive numbers,
 and the result was a very high correlation,
 between 
\begin_inset Formula $0.2$
\end_inset

 and 
\begin_inset Formula $0.3$
\end_inset

,
 in each case.
 What is the serial correlation of this generator,
 taken over all 
\begin_inset Formula $2^{35}$
\end_inset

 numbers of the period?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

The generator has full period by 3.2.1.2–A,
 and 
\begin_inset Formula $x'\coloneqq2^{18}-1$
\end_inset

 gives us 
\begin_inset Formula $S(x')=0$
\end_inset

.
 Thus,
 by (17),
 
\begin_inset Formula $C=(2^{35}\sigma(2^{18}+1,2^{35},1)-3+6(2^{35}-2^{18}))/(2^{70}-1)$
\end_inset

.
 Now we calculate the Dedekind coefficient by Theorem D.
\begin_inset Formula 
\begin{align*}
2^{35} & =(2^{17}-1)(2^{18}+1)+(2^{17}+1), & 1 & =0(2^{18}+1)+1;\\
2^{18}+1 & =1(2^{17}+1)+2^{17}, & 1 & =0(2^{17}+1)+1;\\
2^{17}+1 & =1\cdot2^{17}+1 & 1 & =0(2^{17})+1;\\
2^{17} & =2^{17}\cdot1+0, & 1 & =1\cdot1+0.
\end{align*}

\end_inset

The number 
\begin_inset Formula $h'\coloneqq2^{35}-2^{18}+1$
\end_inset

 gives us 
\begin_inset Formula $(2^{18}+1)h'\equiv1\pmod{2^{35}}$
\end_inset

,
 so
\begin_inset Formula 
\begin{multline*}
\sigma(2^{18}+1,2^{35},1)=\frac{(\cancel{2^{18}}+1)+(2^{35}\cancel{-2^{18}}+1)}{2^{35}}+\left((2^{17}-1)-6\cdot0+6\frac{1^{2}}{2^{35}(2^{18}+1)}\right)-\\
-\left(1-6\cdot0+\frac{6\cdot1^{2}}{(2^{18}+1)(2^{17}+1)}\right)+\left(1-6\cdot0+6\frac{1^{2}}{(2^{17}+1)2^{17}}\right)-\left(2^{17}-6\cdot1+6\frac{1^{2}}{2^{17}}\right)\\
\\-3-2+1=\\
=\cancel{1}+\frac{2}{2^{35}}\cancel{+2^{17}}\cancel{-1}+\frac{6}{2^{53}+2^{35}}\cancel{-1}-\frac{6}{2^{35}+2^{18}+2^{17}+1}\cancel{+1}+\frac{6}{2^{34}+2^{17}}\cancel{-2^{17}}+6-\frac{6}{2^{17}}-4=\\
=2+\frac{1}{2^{34}}+6\left(\frac{1}{2^{53}+2^{35}}-\frac{1}{2^{35}+3\cdot2^{17}+1}+\frac{1}{2^{34}+2^{17}}-\frac{1}{2^{17}}\right)=\\
=2+\frac{1}{2^{34}}+6\frac{2^{17}+1-2^{35}\cancel{+2^{36}+2^{18}}-2^{53}\cancel{-2^{36}}-2^{35}\cancel{-2^{18}}}{2^{35}(2^{18}+1)(2^{17}+1)}=\\
=2+\frac{1}{2^{34}}+3\frac{(-2^{36}+1)\cancel{(2^{17}+1)}}{2^{34}(2^{18}+1)\cancel{(2^{17}+1)}}=2+\frac{1}{2^{34}}-3\frac{2^{18}-1}{2^{34}}=2-\frac{3\cdot2^{18}-4}{2^{34}}=\\
=2-\frac{3\cdot2^{16}-1}{2^{32}}=\frac{2^{33}-2^{17}-2^{16}+1}{2^{32}}=\frac{(2^{17}-1)(2^{16}-1)}{2^{32}}.
\end{multline*}

\end_inset

Thus,
\begin_inset Formula 
\begin{multline*}
C=\frac{8(2^{17}-1)(2^{16}-1)-3+6\cdot2^{18}(2^{17}-1)}{2^{70}-1}=\frac{91624920407}{393530540239137101141}\cong\\
\cong2.33\cdot10^{-10}.
\end{multline*}

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc18[M23]
\end_layout

\end_inset

(U.
 Dieter.) Given positive integers 
\begin_inset Formula $h$
\end_inset

,
 
\begin_inset Formula $k$
\end_inset

,
 
\begin_inset Formula $z$
\end_inset

,
 let
\begin_inset Formula 
\[
S(h,k,c,z)=\sum_{0\leq j<z}\left(\left(\frac{hj+c}{k}\right)\right).
\]

\end_inset

Show that this sum can be evaluated in closed form,
 in terms of the generalized Dedekind sums and the sawtooth function.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

Let 
\begin_inset Formula $S_{j}\coloneqq\left(\left(\frac{hj+c}{k}\right)\right)$
\end_inset

 and note that 
\begin_inset Formula $S_{j}=S_{j+k}$
\end_inset

 for all 
\begin_inset Formula $j$
\end_inset

.
 Thus,
 if 
\begin_inset Formula $z>k$
\end_inset

,
\begin_inset Formula 
\[
\sum_{0\leq j<z}\left(\left(\frac{hj+c}{k}\right)\right)=\left\lfloor \frac{z}{k}\right\rfloor \sum_{0\leq j<k}\left(\left(\frac{hj+c}{k}\right)\right)+\sum_{0\leq j<z\bmod k}\left(\left(\frac{hj+c}{k}\right)\right),
\]

\end_inset

so we may assume 
\begin_inset Formula $z\leq k$
\end_inset

 from now on.
 Now,
 
\begin_inset Formula $\left\lfloor \frac{j}{k}\right\rfloor -\left\lfloor \frac{j-z}{k}\right\rfloor $
\end_inset

 is 1 when 
\begin_inset Formula $0\leq j<z$
\end_inset

 and 0 when 
\begin_inset Formula $z\leq j<k$
\end_inset

,
 so
\begin_inset Formula 
\begin{multline*}
S(h,k,c,z)=\sum_{0\leq j<k}\left(\left\lfloor \frac{j}{k}\right\rfloor -\left\lfloor \frac{j-z}{k}\right\rfloor \right)\left(\left(\frac{hj+c}{k}\right)\right)=\\
=\sum_{0\leq j<k}\left(\cancel{\frac{j}{k}}-\left(\left(\frac{j}{k}\right)\right)\cancel{-\frac{1}{2}}-\frac{\cancel{j}-z}{k}+\left(\left(\frac{j-z}{k}\right)\right)\cancel{+\frac{1}{2}}\right)\left(\left(\frac{hj+c}{k}\right)\right)+\\
+\frac{1}{2}\left(\left(\frac{c}{k}\right)\right)-\frac{1}{2}\left(\left(\frac{hz+c}{k}\right)\right)=\\
=\sum_{0\leq j<k}\left(\left(\left(\frac{j-z}{k}\right)\right)+\frac{z}{k}-\left(\left(\frac{j}{k}\right)\right)\right)\left(\left(\frac{hj+c}{k}\right)\right)+\frac{1}{2}\left(\left(\frac{c}{k}\right)\right)-\frac{1}{2}\left(\left(\frac{hz+c}{k}\right)\right).
\end{multline*}

\end_inset

Let's evaluate the sum term by term.
 Clearly the term 
\begin_inset Formula $-\left(\left(\frac{j}{k}\right)\right)$
\end_inset

 sums to 
\begin_inset Formula $-\frac{1}{12}\sigma(h,k,c)$
\end_inset

.
 For the term with 
\begin_inset Formula $\frac{z}{k}$
\end_inset

,
 which is constant,
 we use the argument used to derive Eq.
 (13) in the text with 
\begin_inset Formula $d\coloneqq\gcd\{h,k\}$
\end_inset

.
 Finally,
\begin_inset Formula 
\begin{multline*}
\sum_{0\leq j<k}\left(\left(\frac{j-z}{k}\right)\right)\left(\left(\frac{hj+c}{k}\right)\right)=\sum_{-z\leq j<k-z}\left(\left(\frac{j}{k}\right)\right)\left(\left(\frac{hj+c+hz}{k}\right)\right)=\\
=\frac{1}{12}\sigma(h,k,c+hz).
\end{multline*}

\end_inset

Putting it all together,
\begin_inset Formula 
\[
S(h,k,c,z)=\frac{1}{12}\sigma(h,k,c+hz)-\frac{1}{12}\sigma(h,k,c)+\frac{zd}{k}\left(\left(\frac{c}{d}\right)\right)+\frac{1}{2}\left(\left(\frac{c}{k}\right)\right)-\frac{1}{2}\left(\left(\frac{hz+c}{k}\right)\right).
\]

\end_inset

For 
\begin_inset Formula $z=k$
\end_inset

,
 this simplifies to 
\begin_inset Formula $d\left(\left(\frac{c}{d}\right)\right)$
\end_inset

,
 and since 
\begin_inset Formula $\left\lfloor \frac{z}{k}\right\rfloor +\frac{z\bmod k}{k}=\frac{z}{k}$
\end_inset

,
 it's easy to check that this formula still applies when 
\begin_inset Formula $z>k$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc19[M23]
\end_layout

\end_inset

Show that the 
\emph on
serial test
\emph default
 can be analyzed over the full period,
 in terms of generalized Dedekind sums,
 by finding a formula for the probability that 
\begin_inset Formula $\alpha\leq X_{n}<\beta$
\end_inset

 and 
\begin_inset Formula $\alpha'\leq X_{n+1}<\beta'$
\end_inset

,
 when 
\begin_inset Formula $\alpha$
\end_inset

,
 
\begin_inset Formula $\beta$
\end_inset

,
 
\begin_inset Formula $\alpha'$
\end_inset

,
 and 
\begin_inset Formula $\beta'$
\end_inset

 are given integers with 
\begin_inset Formula $0\leq\alpha<\beta\leq m$
\end_inset

 and 
\begin_inset Formula $0\leq\alpha'<\beta'\leq m$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset


\begin_inset Formula $P(x)\coloneqq\left\lfloor \frac{x-\alpha}{m}\right\rfloor -\left\lfloor \frac{x-\beta}{m}\right\rfloor $
\end_inset

 is 1 precisely when 
\begin_inset Formula $x\in[\alpha,\beta)$
\end_inset

 and 0 for any other 
\begin_inset Formula $x\in[0,1)$
\end_inset

.
 
\begin_inset Formula $Q(x)\coloneqq\left\lfloor \frac{x-\alpha'}{m}\right\rfloor -\left\lfloor \frac{x-\beta'}{m}\right\rfloor $
\end_inset

 works in an analogous manner.
 For a linear congruential sequence given by 
\begin_inset Formula $S(x)\coloneqq(ax+c)\bmod m$
\end_inset

 that has maximum period,
 the probability that 
\begin_inset Formula $x_{n}\in[\alpha,\beta)\land x_{n+1}\in[\alpha',\beta')$
\end_inset

 is
\begin_inset Formula 
\begin{multline*}
\frac{1}{m}\sum_{0\leq x<m}P(x)Q(ax+c)=\\
=\frac{1}{m}\sum_{0\leq x<m}\left(\left\lfloor \frac{x-\alpha}{m}\right\rfloor -\left\lfloor \frac{x-\beta}{m}\right\rfloor \right)\left(\left\lfloor \frac{S(x)-\alpha'}{m}\right\rfloor -\left\lfloor \frac{S(x)-\beta'}{m}\right\rfloor \right)
\end{multline*}

\end_inset

Now,
\begin_inset Formula 
\begin{align*}
\left\lfloor \frac{x-\alpha}{m}\right\rfloor  & =\frac{x}{m}-\frac{\alpha}{m}-\frac{1}{2}-\left(\left(\frac{x-\alpha}{m}\right)\right)+\frac{1}{2}\delta_{x,\alpha},\\
\left\lfloor \frac{S(x)-\alpha'}{m}\right\rfloor  & =\frac{(ax+c)\bmod m-\alpha'}{m}-\left(\left(\frac{ax+c-\alpha'}{m}\right)\right)-\frac{1}{2}+\frac{1}{2}\delta_{S(x)\alpha'}=\\
 & =\left(\left(\frac{ax+c}{m}\right)\right)-\left(\left(\frac{ax+c-\alpha'}{m}\right)\right)-\frac{\alpha'}{m}+\frac{1}{2}(\delta_{S(x)\alpha'}-\delta_{S(x)0}).
\end{align*}

\end_inset

Thus,
 
\begin_inset Formula 
\begin{multline*}
\sum_{0\leq x<m}\left\lfloor \frac{x-\alpha}{m}\right\rfloor \left\lfloor \frac{S(x)-\alpha'}{m}\right\rfloor =\\
=\sum_{0\leq x<m}\left(\left(\frac{x}{m}-\frac{1}{2}\right)-\frac{\alpha}{m}-\left(\left(\frac{x-\alpha}{m}\right)\right)\right)\\
\left(\left(\left(\frac{ax+c}{m}\right)\right)-\left(\left(\frac{ax+c-\alpha'}{m}\right)\right)-\frac{\alpha'}{m}\right)+\\
+\frac{1}{2}\left(\left\lfloor \frac{S(\alpha)-\alpha'}{m}\right\rfloor +\left\lfloor \frac{S^{-1}(\alpha')-\alpha}{m}\right\rfloor -\left\lfloor \frac{S^{-1}(0)-\alpha}{m}\right\rfloor \right)+\frac{1}{4}([S(\alpha)=\alpha']-[S(\alpha)=0]).
\end{multline*}

\end_inset

The terms outside this last sum can be calculated directly.
 Inside the sum,
 we have a product of two sums with three terms each,
 which we may expand into 9 terms.
 For these,
 note that 
\begin_inset Formula $\frac{x}{m}-\frac{1}{2}=\left(\left(\frac{x}{m}\right)\right)-\frac{1}{2}[x=0]$
\end_inset

,
 so for example
\begin_inset Formula 
\[
\sum_{0\leq x<m}\left(\frac{x}{m}-\frac{1}{2}\right)\left(\left(\frac{ax+c-\alpha'}{m}\right)\right)=\frac{1}{12}\delta(a,m,c-\alpha')-\left(\left(\frac{c-\alpha'}{m}\right)\right),
\]

\end_inset

and similarly,
\begin_inset Formula 
\begin{multline*}
\sum_{0\leq x<m}\left(\left(\frac{x-\alpha}{m}\right)\right)\left(\left(\frac{ax+c-\alpha'}{m}\right)\right)=\\
=\sum_{-\alpha\leq x<m-\alpha}\left(\left(\frac{x}{m}\right)\right)\left(\left(\frac{ax+c-\alpha'+\alpha}{m}\right)\right)=\frac{1}{12}\sigma(a,m,c-\alpha'+\alpha).
\end{multline*}

\end_inset

The other terms do not include sawtooth functions and can be expanded mechanically using that 
\begin_inset Formula $\sum_{0\leq x<m}x=\frac{m(m-1)}{2}$
\end_inset

.
 Then we can compute the initial sum as the sum of 4 of these sums.
\end_layout

\begin_layout Subsubsection
Second Set
\end_layout

\begin_layout Standard
In many cases,
 exact computations with integers are quite difficult to carry out,
 but we can attempt to study the probabilities that arise when we take the average real values of 
\begin_inset Formula $x$
\end_inset

 instead of restricting the calculation to integer values.
 Although these results are only approximate,
 they shed some light on the subject.
\end_layout

\begin_layout Standard
It is convenient to deal with numbers 
\begin_inset Formula $U_{n}$
\end_inset

 between zero and one;
 for linear congruential sequences,
 
\begin_inset Formula $U_{n}=X_{n}/m$
\end_inset

,
 and we have 
\begin_inset Formula $U_{n+1}=\{aU_{n}+\theta\}$
\end_inset

,
 where 
\begin_inset Formula $\theta=c/m$
\end_inset

 and 
\begin_inset Formula $\{x\}$
\end_inset

 denotes 
\begin_inset Formula $x\bmod1$
\end_inset

.
 For example,
 the formula for serial correlation now becomes
\begin_inset Formula 
\[
C=\left(\int_{0}^{1}x\{ax+\theta\}\text{d}x-\left(\int_{0}^{1}x\text{d}x\right)^{2}\right)\biggg/\left(\int_{0}^{1}x^{2}\text{d}x-\left(\int_{0}^{1}x\text{d}x\right)^{2}\right).
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc21[HM23]
\end_layout

\end_inset

(R.
 R.
 Coveyou.) What is the value of 
\begin_inset Formula $C$
\end_inset

 in the formula just given?
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

We have
\begin_inset Formula 
\begin{align*}
\int_{0}^{1}x\text{d}x & =\left.\frac{x^{2}}{2}\right|_{x=0}^{1}=\frac{1}{2}, & \int_{0}^{1}x^{2}\text{d}x & =\left.\frac{x^{3}}{3}\right|_{x=0}^{1}=\frac{1}{3},
\end{align*}

\end_inset

and we just need to calculate the more complex integral.
 Assume 
\begin_inset Formula $a>0$
\end_inset

.
 Then the graph for 
\begin_inset Formula $\{ax+\theta\}$
\end_inset

 is a sequence of lines.
 The first goes from 
\begin_inset Formula $(0,\theta)$
\end_inset

 to 
\begin_inset Formula $(\frac{1-\theta}{a},1)$
\end_inset

,
 the next one from 
\begin_inset Formula $(\frac{1-\theta}{a},0)$
\end_inset

 to 
\begin_inset Formula $(\frac{2-\theta}{a},1)$
\end_inset

,
 etc.,
 and the last one goes from 
\begin_inset Formula $(1-\tfrac{\theta}{a},0)$
\end_inset

 to 
\begin_inset Formula $(1,\theta)$
\end_inset

 (we used that 
\begin_inset Formula $a$
\end_inset

 is an integer to calculate this).
 Thus
\begin_inset Formula 
\[
\int_{0}^{1}x\{ax+\theta\}\text{d}x=\sum_{k=1}^{a-1}\int_{\frac{k-\theta}{a}}^{\frac{k+1-\theta}{a}}x(ax+\theta-k)\text{d}x+\int_{0}^{\frac{1-\theta}{a}}x(ax+\theta)\text{d}x+\int_{1-\frac{\theta}{a}}^{1}x(ax+\theta-a)\text{d}x.
\]

\end_inset

Now,
\begin_inset Formula 
\[
\int x(ax+\theta-k)\text{d}x=\frac{a}{3}x^{3}+\frac{\theta-k}{2}x^{2}+C,
\]

\end_inset

so if we call 
\begin_inset Formula $x_{k}\coloneqq\frac{k-\theta}{a}$
\end_inset

 except that 
\begin_inset Formula $x_{0}\coloneqq0$
\end_inset

 and 
\begin_inset Formula $x_{a+1}\coloneqq1$
\end_inset

,
 we have
\begin_inset Formula 
\begin{multline*}
\int_{0}^{1}x\{ax+\theta\}\text{d}x=\sum_{0\leq k\leq a}\int_{x_{k}}^{x_{k+1}}x(ax+\theta-k)\text{d}x=\\
=\sum_{0\leq k\leq a}\left(\frac{a}{3}x_{k+1}^{3}+\frac{\theta-k}{2}x_{k+1}^{2}-\frac{a}{3}x_{k}^{3}-\frac{\theta-k}{2}x_{k}^{2}\right)=\frac{a}{3}+\frac{\theta-a}{2}+\sum_{0<k\leq a}\frac{1}{2}x_{k}^{2}=\\
=\frac{a}{3}+\frac{\theta-a}{2}+\frac{1}{2a^{2}}\sum_{k=1}^{a}(k^{2}-2k\theta+\theta^{2})=\frac{\theta}{2}-\frac{a}{6}+\frac{(a+1)(2a+1)}{12a}-\frac{(a+1)\theta}{2a}+\frac{\theta^{2}}{2a}=\\
=\frac{\theta(\theta-1)}{2a}+\frac{1}{12a}+\frac{1}{4}.
\end{multline*}

\end_inset

Putting it all together,
\begin_inset Formula 
\[
C=\left(\frac{\theta(\theta-1)}{2a}+\frac{1}{12a}+\frac{1}{4}-\frac{1}{4}\right)\biggg/\left(\frac{1}{3}-\frac{1}{4}\right)=\frac{6\theta(\theta-1)+1}{a}.
\]

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc22[M22]
\end_layout

\end_inset

Let 
\begin_inset Formula $a$
\end_inset

 be an integer,
 and let 
\begin_inset Formula $0\leq\theta<1$
\end_inset

.
 If 
\begin_inset Formula $x$
\end_inset

 is a random real number,
 uniformly distributed between 0 and 1,
 and if 
\begin_inset Formula $s(x)=\{ax+\theta\}$
\end_inset

,
 what is the probability that 
\begin_inset Formula $s(x)<x$
\end_inset

?
 (This is the 
\begin_inset Quotes eld
\end_inset

real number
\begin_inset Quotes erd
\end_inset

 analog of Theorem P.)
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

As in the previous exercise,
 let 
\begin_inset Formula $x_{0}\coloneqq0$
\end_inset

,
 
\begin_inset Formula $x_{k}\coloneqq\frac{k-\theta}{a}$
\end_inset

 for 
\begin_inset Formula $k\in\{1,\dots,a\}$
\end_inset

,
 and 
\begin_inset Formula $x_{a+1}\coloneqq1$
\end_inset

,
 for 
\begin_inset Formula $k\in\{0,\dots,a\}$
\end_inset

 and 
\begin_inset Formula $x\in[x_{k},x_{k+1})$
\end_inset

 we have 
\begin_inset Formula $\lfloor ax+\theta\rfloor=k$
\end_inset

 and
\begin_inset Formula 
\[
s(x)=ax+\theta-\lfloor ax+\theta\rfloor<x\iff(a-1)x<\lfloor ax+\theta\rfloor-\theta=k-\theta\iff x<\frac{k-\theta}{a-1},
\]

\end_inset

so in particular 
\begin_inset Formula $s(x)\geq x$
\end_inset

 for 
\begin_inset Formula $x<x_{1}$
\end_inset

 and the probability is
\begin_inset Formula 
\begin{multline*}
\int_{0}^{1}[s(x)<x]\text{d}x=\sum_{k=1}^{a}\int_{x_{k}}^{x_{k+1}}[x<\tfrac{k-\theta}{a-1}]\text{d}x=\sum_{k=1}^{a-1}\left(\frac{k-\theta}{a-1}-\frac{k-\theta}{a}\right)+1-\frac{a-\theta}{a}=\\
=\sum_{k=1}^{a-1}\frac{k-\theta}{a(a-1)}+\frac{\theta}{a}=\left(\frac{1}{2}-\frac{\theta}{a}\right)+\frac{\theta}{a}=\frac{1}{2}.
\end{multline*}

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
rexerc25[M25]
\end_layout

\end_inset

Let 
\begin_inset Formula $\alpha$
\end_inset

,
 
\begin_inset Formula $\beta$
\end_inset

,
 
\begin_inset Formula $\alpha'$
\end_inset

,
 
\begin_inset Formula $\beta'$
\end_inset

 be real numbers with 
\begin_inset Formula $0\leq\alpha<\beta\leq1$
\end_inset

,
 
\begin_inset Formula $0\leq\alpha'<\beta'\leq1$
\end_inset

.
 Under the assumptions of exercise 22,
 what is the probability that 
\begin_inset Formula $\alpha\leq x<\beta$
\end_inset

 and 
\begin_inset Formula $\alpha'\leq s(x)<\beta'$
\end_inset

?
 (This is the 
\begin_inset Quotes eld
\end_inset

real number
\begin_inset Quotes erd
\end_inset

 analog of exercise 19.)
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
answer 
\end_layout

\end_inset

In the notation of the answer to exercise 22,
 assume that 
\begin_inset Formula $\alpha\in[x_{p},x_{p+1})$
\end_inset

 and 
\begin_inset Formula $\beta\in[x_{q},x_{q+1})$
\end_inset

,
 with 
\begin_inset Formula $0\leq p\leq q\leq a$
\end_inset

.
 For 
\begin_inset Formula $x\in[x_{k},x_{k+1})$
\end_inset

,
\begin_inset Formula 
\[
\alpha'\leq s(x)<\beta'\iff\alpha'\leq ax+\theta-k<\beta'\iff x\in\left[\frac{\alpha'+k-\theta}{a},\frac{\beta'+k-\theta}{a}\right).
\]

\end_inset

Note that,
 since 
\begin_inset Formula $s(x)$
\end_inset

 goes from 0 to 1 when 
\begin_inset Formula $x$
\end_inset

 goes from 
\begin_inset Formula $x_{k}$
\end_inset

 to 
\begin_inset Formula $x_{k+1}$
\end_inset

,
 each of these intervals has 
\begin_inset Formula $s(x)$
\end_inset

 enter and exit 
\begin_inset Formula $[\alpha',\beta')$
\end_inset

 and fully contains the interval above.
 Let 
\begin_inset Formula $s_{k}^{-1}(y)\coloneqq\frac{y+k-\theta}{a}$
\end_inset

.
 If 
\begin_inset Formula $p=q$
\end_inset

,
 the probability is
\begin_inset Formula 
\[
\int_{\alpha}^{\beta}[\alpha'\leq s(x)<\beta']\text{d}x=\max\left\{ 0,\min\{\beta,s_{p}^{-1}(\beta')\}-\max\{\alpha,s_{p}^{-1}(\alpha')\}\right\} .
\]

\end_inset

If 
\begin_inset Formula $p\neq q$
\end_inset

,
 we have to consider the two extremes and the 
\begin_inset Formula $q-p-1$
\end_inset

 intervals in the middle,
 each of which contributes 
\begin_inset Formula $\frac{\beta'-\alpha'}{a}$
\end_inset

,
 so the probability in this case is
\begin_inset Formula 
\begin{multline*}
\max\left\{ 0,s_{p}^{-1}(\beta')-\max\{\alpha,s_{p}^{-1}(\alpha')\}\right\} +(q-p-1)\frac{\beta'-\alpha'}{a}+\\
+\max\left\{ 0,\min\{\beta,s_{q}^{-1}(\beta')\}-s_{q}^{-1}(\alpha')\right\} .
\end{multline*}

\end_inset

Note that this last formula is still valid when 
\begin_inset Formula $p=q$
\end_inset

.
\end_layout

\end_body
\end_document