From 242a74fc4215d3d5e02596d38d43bb96fbc59de6 Mon Sep 17 00:00:00 2001
From: Juan Marín Noguera <juan@mnpi.eu>
Date: Mon, 3 Mar 2025 12:47:54 +0100
Subject: 3.3.3 Theoretical tests

---
 3.3.3.lyx | 1370 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 1370 insertions(+)
 create mode 100644 3.3.3.lyx

(limited to '3.3.3.lyx')

diff --git a/3.3.3.lyx b/3.3.3.lyx
new file mode 100644
index 0000000..71fc21f
--- /dev/null
+++ b/3.3.3.lyx
@@ -0,0 +1,1370 @@
+#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 
+\[
+\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_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{align*}
+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{align*}
+
+\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 
+\[
+\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_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+6\frac{1^{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}\cdot1}\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 
+\[
+C=\frac{8(2^{17}-1)(2^{16}-1)-3+6\cdot2^{18}(2^{17}-1)}{2^{70}-1}=\frac{91624920407}{393530540239137101141}\cong2.33\cdot10^{-10}.
+\]
+
+\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 
+\[
+\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_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 
+\[
+\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_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 
+\[
+\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_inset
+
+Note that this last formula is still valid when 
+\begin_inset Formula $p=q$
+\end_inset
+
+.
+\end_layout
+
+\end_body
+\end_document
-- 
cgit v1.2.3