path: root/vol2/3.3.4.lyx

#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