3.3.4 The Spectral Test

2 files changed, 804 insertions, 0 deletions

diff --git a/3.3.4.lyx b/3.3.4.lyx
new file mode 100644
index 0000000..1c06b60
--- /dev/null
+++ b/3.3.4.lyx
@@ -0,0 +1,781 @@
+#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 Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+exerc1[M10]
+\end_layout
+
+\end_inset
+
+To what does the spectral test reduce in 
+\emph on
+one
+\emph default
+ dimension?
+ (In other words,
+ what happens when 
+\begin_inset Formula $t=1$
+\end_inset
+
+?)
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+In this case 
+\begin_inset Formula $\nu_{1}^{-1}$
+\end_inset
+
+ is the maximum distance between points in 
+\begin_inset Formula $\{x/m\}_{x=0}^{m-1}$
+\end_inset
+
+,
+ which is 
+\begin_inset Formula $m^{-1}$
+\end_inset
+
+,
+ so 
+\begin_inset Formula $\nu_{1}=m$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc4[M23]
+\end_layout
+
+\end_inset
+
+Let 
+\begin_inset Formula $u_{11}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $u_{12}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $u_{21}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $u_{22}$
+\end_inset
+
+ be elements of a 
+\begin_inset Formula $2\times2$
+\end_inset
+
+ integer matrix such that 
+\begin_inset Formula $u_{11}+au_{12}\equiv u_{21}+au_{22}\equiv0\pmod m$
+\end_inset
+
+ and 
+\begin_inset Formula $u_{11}u_{22}-u_{21}u_{12}=m$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Prove that all integer solutions 
+\begin_inset Formula $(y_{1},y_{2})$
+\end_inset
+
+ to the congruence 
+\begin_inset Formula $y_{1}+ay_{2}\equiv0\pmod m$
+\end_inset
+
+ have the form 
+\begin_inset Formula $(y_{1},y_{2})=(x_{1}u_{11}+x_{2}u_{21},x_{1}u_{12}+x_{2}u_{22})$
+\end_inset
+
+ for integer 
+\begin_inset Formula $x_{1}$
+\end_inset
+
+,
+ 
+\begin_inset Formula $x_{2}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+If,
+ in addition,
+ 
+\begin_inset Formula $2|u_{11}u_{21}+u_{12}u_{22}|\leq u_{11}^{2}+u_{12}^{2}\leq u_{21}^{2}+u_{22}^{2}$
+\end_inset
+
+,
+ prove that 
+\begin_inset Formula $(y_{1},y_{2})=(u_{11},u_{12})$
+\end_inset
+
+ minimizes 
+\begin_inset Formula $y_{1}^{2}+y_{2}^{2}$
+\end_inset
+
+ over all nonzero solutions to the congruence.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+Assume 
+\begin_inset Formula $a\in\mathbb{Z}$
+\end_inset
+
+ and 
+\begin_inset Formula $m\in\mathbb{N}^{*}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Clearly all pairs of integers 
+\begin_inset Formula $(p,q)$
+\end_inset
+
+ can be written as 
+\begin_inset Formula $(p,q)=z_{1}(m,0)+z_{2}(-a,1)+z_{3}(1,0)$
+\end_inset
+
+ for some 
+\begin_inset Formula $z_{1},z_{2},z_{3}\in\mathbb{Z}$
+\end_inset
+
+ with 
+\begin_inset Formula $0\leq z_{3}<m$
+\end_inset
+
+.
+ Moreover,
+ solutions to the congruence are precisely those pairs with 
+\begin_inset Formula $z_{3}=0$
+\end_inset
+
+,
+ and we just have to prove that 
+\begin_inset Formula $(m,0)$
+\end_inset
+
+ and 
+\begin_inset Formula $(-a,1)$
+\end_inset
+
+ can be expressed as an integer linear combination of 
+\begin_inset Formula $(u_{11},u_{12})$
+\end_inset
+
+ and 
+\begin_inset Formula $(u_{21},u_{22})$
+\end_inset
+
+.
+ 
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+For 
+\begin_inset Formula $(m,0)$
+\end_inset
+
+,
+ 
+\begin_inset Formula $u_{22}(u_{11},u_{12})-u_{12}(u_{21},u_{22})=(m,0)$
+\end_inset
+
+.
+ For 
+\begin_inset Formula $(a,-1)$
+\end_inset
+
+,
+ if 
+\begin_inset Formula $j,k\in\mathbb{Z}$
+\end_inset
+
+ are such that 
+\begin_inset Formula $u_{11}=jm-au_{12}$
+\end_inset
+
+ and 
+\begin_inset Formula $u_{21}=km-au_{22}$
+\end_inset
+
+,
+ we can expand to get 
+\begin_inset Formula $m=u_{11}u_{22}-u_{21}u_{12}=ju_{22}m-ku_{12}m$
+\end_inset
+
+,
+ so 
+\begin_inset Formula $ju_{22}-ku_{12}=1$
+\end_inset
+
+,
+ and then 
+\begin_inset Formula $ju_{21}-ku_{11}=-aju_{22}+aku_{12}=-a(ju_{22}-ku_{12})=-a$
+\end_inset
+
+,
+ so 
+\begin_inset Formula $(-a,1)=-k(u_{11},u_{12})+j(u_{21},u_{22})$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Enumerate
+If 
+\begin_inset Formula $x_{1},x_{2}\in\mathbb{Z}$
+\end_inset
+
+ are not both 0,
+ then
+\begin_inset Formula 
+\begin{multline*}
+(x_{1}u_{11}+x_{2}u_{21})^{2}+(x_{1}u_{12}+x_{2}u_{22})^{2}=\\
+=x_{1}^{2}(u_{11}^{2}+u_{12}^{2})+x_{2}^{2}(u_{21}^{2}+u_{22}^{2})+2x_{1}x_{2}(u_{11}u_{21}+u_{21}u_{22}).
+\end{multline*}
+
+\end_inset
+
+If 
+\begin_inset Formula $x_{1}x_{2}(u_{11}u_{21}+u_{21}u_{22})\geq0$
+\end_inset
+
+,
+ then this is greater or equal to
+\begin_inset Formula 
+\[
+x_{1}^{2}(u_{11}^{2}+u_{12}^{2})+x_{2}^{2}(u_{21}^{2}+u_{22}^{2})\geq(x_{1}^{2}+x_{2}^{2})(u_{11}^{2}+u_{12}^{2})\geq u_{11}^{2}+u_{12}^{2}.
+\]
+
+\end_inset
+
+Otherwise 
+\begin_inset Formula $x_{1},x_{2}\neq0$
+\end_inset
+
+ and,
+ if 
+\begin_inset Formula $|x_{1}|\leq|x_{2}|$
+\end_inset
+
+,
+ then the above is greater than or equal to
+\begin_inset Formula 
+\[
+x_{1}^{2}(u_{11}^{2}+u_{12}^{2}-2(u_{11}u_{21}+u_{21}u_{22}))+x_{2}^{2}(u_{21}^{2}+u_{22}^{2})\geq x_{2}^{2}(u_{21}^{2}+u_{22}^{2})\geq u_{11}^{2}+u_{12}^{2},
+\]
+
+\end_inset
+
+whereas the case with 
+\begin_inset Formula $|x_{1}|\geq|x_{2}|$
+\end_inset
+
+ is analogous.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc15[M20]
+\end_layout
+
+\end_inset
+
+Let 
+\begin_inset Formula $U$
+\end_inset
+
+ be an integer vector satisfying (15).
+ How many of the 
+\begin_inset Formula $(t-1)$
+\end_inset
+
+-dimensional hyperplanes defined by 
+\begin_inset Formula $U$
+\end_inset
+
+ intersect the unit hypercube 
+\begin_inset Formula $\{(x_{1},\dots,x_{t})\mid0\leq x_{j}<1\text{ for }1\leq j\leq t\}$
+\end_inset
+
+?
+ (This is approximately the number of hyperplanes in the family that will suffice to cover 
+\begin_inset Formula $L_{0}$
+\end_inset
+
+.)
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+The hyperplanes are defined by 
+\begin_inset Formula $\{\{X\mid X\cdot U=q\}\}_{q\in\mathbb{Z}}$
+\end_inset
+
+,
+ so we need to find the maximum and minimum integer values for 
+\begin_inset Formula $X\cdot U$
+\end_inset
+
+ when 
+\begin_inset Formula $X\in[0,1)^{n}$
+\end_inset
+
+,
+ which exist because 
+\begin_inset Formula $0\cdot U=0\in\mathbb{Z}$
+\end_inset
+
+.
+ The maximum and minimum real values when 
+\begin_inset Formula $X\in[0,1]^{n}$
+\end_inset
+
+ are,
+ respectively,
+ 
+\begin_inset Formula $M\coloneqq u_{1}\frac{1+\text{sgn}u_{1}}{2}+\dots+u_{t}\frac{1+\text{sgn}u_{t}}{2}$
+\end_inset
+
+ and 
+\begin_inset Formula $m\coloneqq u_{1}\frac{1-\text{sgn}u_{1}}{2}+\dots+u_{t}\frac{1-\text{sgn}u_{t}}{2}$
+\end_inset
+
+,
+ which happen to be integers,
+ so we have 
+\begin_inset Formula 
+\[
+M-m+1=u_{1}\text{sgn}u_{1}+\dots+u_{t}\text{sgn}u_{t}+1=|u_{1}|+\dots+|u_{t}|+1
+\]
+
+\end_inset
+
+hyperplanes.
+\end_layout
+
+\begin_layout Standard
+However,
+ one of these hyperplanes might only cover points in 
+\begin_inset Formula $[0,1]^{n}\setminus[0,1)^{n}$
+\end_inset
+
+.
+ This happens precisely when 
+\begin_inset Formula $(1,\dots,1)\cdot U=u_{1}+\dots+u_{t}$
+\end_inset
+
+ is either 
+\begin_inset Formula $M$
+\end_inset
+
+ or 
+\begin_inset Formula $m$
+\end_inset
+
+,
+ that is,
+ when all of the 
+\begin_inset Formula $u_{i}$
+\end_inset
+
+ are nonnegative or nonpositive.
+ Thus,
+ the actual number of hyperplanes is
+\begin_inset Formula 
+\[
+|u_{1}|+\dots+|u_{t}|+1-[u_{1},\dots,u_{t}\leq0]-[u_{1},\dots,u_{t}\geq0].
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc19[HM25]
+\end_layout
+
+\end_inset
+
+Suppose step S5 were changed slightly,
+ so that a transformation with 
+\begin_inset Formula $q=1$
+\end_inset
+
+ would be performed when 
+\begin_inset Formula $2V_{i}\cdot V_{j}=V_{j}\cdot V_{j}$
+\end_inset
+
+.
+ (Thus,
+ 
+\begin_inset Formula $q=\lfloor(V_{i}\cdot V_{j}/V_{j}\cdot V_{j})+\frac{1}{2}\rfloor$
+\end_inset
+
+ whenever 
+\begin_inset Formula $i\neq j$
+\end_inset
+
+.) Would it still be possible for Algorithm S to get into an infinite loop?
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer 
+\end_layout
+
+\end_inset
+
+No.
+ If 
+\begin_inset Formula $2|V_{i}\cdot V_{j}|>V_{j}\cdot V_{j}$
+\end_inset
+
+ in some step,
+ then
+\begin_inset Formula 
+\[
+(V_{i}-qV_{j})\cdot(V_{i}-qV_{j})=V_{i}\cdot V_{i}-2qV_{i}\cdot V_{j}+V_{j}\cdot V_{j}<V_{i}\cdot V_{i},
+\]
+
+\end_inset
+
+because 
+\begin_inset Formula $q$
+\end_inset
+
+ has the same sign as 
+\begin_inset Formula $V_{i}\cdot V_{j}$
+\end_inset
+
+ and therefore 
+\begin_inset Formula $V_{j}\cdot V_{j}<2|V_{i}\cdot V_{j}|\leq2qV_{i}\cdot V_{j}$
+\end_inset
+
+,
+ so 
+\begin_inset Formula $V_{i}\cdot V_{i}$
+\end_inset
+
+ decreases and,
+ since it is an integer,
+ it cannot decrease for infinitely many steps.
+ Thus,
+ an infinite loop would eventually only contain steps where 
+\begin_inset Formula $2V_{i}\cdot V_{j}=V_{j}\cdot V_{j}$
+\end_inset
+
+,
+ which are the ones we allow now,
+ and since there are only finitely many integer vectors with a given norm,
+ 
+\begin_inset Formula $V$
+\end_inset
+
+ would have to repeat at some point.
+ However,
+ in these cases 
+\begin_inset Formula $q=1$
+\end_inset
+
+,
+ so the steps are equivalent to multiplying 
+\begin_inset Formula $V$
+\end_inset
+
+ by an elementary matrix with 1s at the diagonal and at some other value and 0s everywhere else.
+ These matrices cannot result in an identity matrix when multiplying them because they don't have negative entries.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+rexerc32[M21]
+\end_layout
+
+\end_inset
+
+Let 
+\begin_inset Formula $m_{1}=2^{31}-1$
+\end_inset
+
+ and 
+\begin_inset Formula $m_{2}=2^{31}-249$
+\end_inset
+
+ be the moduli of generator (38).
+\end_layout
+
+\begin_layout Enumerate
+Show that if 
+\begin_inset Formula $U_{n}=(X_{n}/m_{1}-Y_{n}/m_{2})\bmod1$
+\end_inset
+
+,
+ we have 
+\begin_inset Formula $U_{n}\approx Z_{n}/m_{1}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Let 
+\begin_inset Formula $W_{0}=(X_{0}m_{2}-Y_{0}m_{1})\bmod m$
+\end_inset
+
+ and 
+\begin_inset Formula $W_{n+1}=aW_{n}\bmod m$
+\end_inset
+
+,
+ where 
+\begin_inset Formula $a$
+\end_inset
+
+ and 
+\begin_inset Formula $m$
+\end_inset
+
+ have the values stated in the text following (38).
+ Prove that there is a simple relation between 
+\begin_inset Formula $W_{n}$
+\end_inset
+
+ and 
+\begin_inset Formula $U_{n}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+answer
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $Z_{n}/m_{1}=(X_{n}/m_{1}-Y_{n}/m_{1})\bmod1\approx(X_{n}/m_{1}-Y_{n}/m_{2})\bmod1=U_{n}$
+\end_inset
+
+.
+ The difference is at most 
+\begin_inset Formula $|Y_{n}/m_{1}-Y_{n}/m_{2}|=Y_{n}\left|\frac{1}{2^{31}-1}-\frac{1}{2^{31}-249}\right|=Y_{n}\frac{248}{(2^{31}-1)(2^{31}-249)}<\frac{248}{2^{31}-1}<2^{-23}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+We have 
+\begin_inset Formula $mU_{0}=(X_{0}m/m_{1}-Y_{0}m/m_{2})\bmod m=(X_{0}m_{2}-Y_{0}m_{1})\bmod m=W_{0}$
+\end_inset
+
+,
+ and also
+\begin_inset Formula 
+\begin{multline*}
+U_{n+1}=(aX_{n}\bmod m_{1}/m_{1}-aY_{n}\bmod m_{2}/m_{2})\bmod1=\\
+=a(X_{n}/m_{1}-Y_{n}/m_{2})\bmod1=aU_{n}\bmod1,
+\end{multline*}
+
+\end_inset
+
+so by induction 
+\begin_inset Formula $W_{n}\equiv mU_{n}$
+\end_inset
+
+.
+\end_layout
+
+\end_body
+\end_document
diff --git a/index.lyx b/index.lyx
index 06e5d04..fca6bc2 100644
--- a/index.lyx
+++ b/index.lyx
@@ -2077,6 +2077,29 @@ A10+R25
 The Spectral Test
 \end_layout
 
+\begin_layout Standard
+\begin_inset CommandInset include
+LatexCommand input
+filename "3.3.4.lyx"
+literal "false"
+
+\end_inset
+
+
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+
+\family typewriter
+A10+R25
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
 \begin_layout Section
 Other Types of Random Quantities
 \end_layout