From 4f670b750af5c11e1eac16d9cd8556455f89f46a Mon Sep 17 00:00:00 2001
From: Juan Marín Noguera <juan@mnpi.eu>
Date: Fri, 16 May 2025 22:18:44 +0200
Subject: Changed layout for more manageable volumes

---
 3.3.4.lyx | 781 --------------------------------------------------------------
 1 file changed, 781 deletions(-)
 delete mode 100644 3.3.4.lyx

(limited to '3.3.4.lyx')

diff --git a/3.3.4.lyx b/3.3.4.lyx
deleted file mode 100644
index 1c06b60..0000000
--- a/3.3.4.lyx
+++ /dev/null
@@ -1,781 +0,0 @@
-#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
-- 
cgit v1.2.3