X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/236f25b2f3a081b11c71bedad6d044d695ce2cca..a57f211cb3b73d523ff516e65f2559b296775c11:/chaos.tex?ds=sidebyside

diff --git a/chaos.tex b/chaos.tex
index 511a11a..dafc635 100644
--- a/chaos.tex
+++ b/chaos.tex
@@ -40,41 +40,41 @@ This necessitates a rigorous proof, which is the aim of this section.
 Consider a topological space $(\mathcal{X},\tau)$ and a continuous function $f :
 \mathcal{X} \rightarrow \mathcal{X}$.
 
-\begin{dfntn}
+\begin{definition}
 The function $f$ is said to be \emph{topologically transitive} if, for any pair of open sets
 $U,V \subset \mathcal{X}$, there exists $k>0$ such that $f^k(U) \cap V \neq
 \varnothing$.
-\end{dfntn}
+\end{definition}
 
-\begin{dfntn}
+\begin{definition}
 An element $x$ is a \emph{periodic point} for $f$ of period $n\in \mathds{N}^*$
 if $f^{n}(x)=x$.% The set of periodic points of $f$ is denoted $Per(f).$
-\end{dfntn}
+\end{definition}
 
-\begin{dfntn}
+\begin{definition}
 $f$ is said to be \emph{regular} on $(\mathcal{X}, \tau)$ if the set of periodic
 points for $f$ is dense in $\mathcal{X}$: for any point $x$ in $\mathcal{X}$,
 any neighborhood of $x$ contains at least one periodic point (without
 necessarily the same period).
-\end{dfntn}
+\end{definition}
 
 
-\begin{dfntn}[Devaney's formulation of chaos~\cite{Devaney}]
+\begin{definition}[Devaney's formulation of chaos~\cite{Devaney}]
 The function $f$ is said to be \emph{chaotic} on $(\mathcal{X},\tau)$ if $f$ is regular and
 topologically transitive.
-\end{dfntn}
+\end{definition}
 
 The chaos property is strongly linked to the notion of ``sensitivity'', defined
 on a metric space $(\mathcal{X},d)$ by:
 
-\begin{dfntn}
+\begin{definition}
 \label{sensitivity} The function $f$ has \emph{sensitive dependence on initial conditions}
 if there exists $\delta >0$ such that, for any $x\in \mathcal{X}$ and any
 neighborhood $V$ of $x$, there exist $y\in V$ and $n > 0$ such that
 $d\left(f^{n}(x), f^{n}(y)\right) >\delta $.
 
 The constant $\delta$ is called the \emph{constant of sensitivity} of $f$.
-\end{dfntn}
+\end{definition}
 
 Indeed, Banks \emph{et al.} have proven in~\cite{Banks92} that when $f$ is
 chaotic and $(\mathcal{X}, d)$ is a metric space, then $f$ has the property of
@@ -163,11 +163,12 @@ However, it can be generalized with $p_i$, $p_i \in \mathcal{P}$,
 functional compositions of $F_f$.
 Thus, for any $p_i \in \mathcal{P}$ we introduce the function 
 $F_{f,p_i} :  \mathds{B}^\mathsf{N} \times \llbracket 1, \mathsf{N} \rrbracket^{p_i}  \rightarrow \mathds{B}^\mathsf{N}$ defined by 
-
-$$
-F_{f,p_i} (x,(u^0, u^1, \hdots, u^{p_i-1}))  \mapsto 
-F_f(\hdots (F_f(F_f(x,u^0), u^1), \hdots), u^{p_i-1}).
-$$
+\[
+\begin{array}{l}
+F_{f,p_i} (x,(u^0, u^1, \hdots, u^{p_i-1}))  \mapsto \\
+\qquad F_f(\hdots (F_f(F_f(x,u^0), u^1), \hdots), u^{p_i-1}).
+\end{array}
+\]
 
 
 The considered space is 
@@ -182,20 +183,27 @@ The sequence $(v^k)_{k \in \Nats}$ defines how many iterations are executed at t
 The sequence $(u^k)_{k \in \Nats}$ defines which elements is modified. 
 
 Let us define the shift function $\Sigma$ for any element of $\mathds{S}_{\mathsf{N},\mathcal{P}}$.
-$$\begin{array}{cccc}
-\Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\longrightarrow
+
+\[
+\begin{array}{cccc}
+\Sigma:&\mathds{S}_{\mathsf{N},\mathcal{P}} &\rightarrow
 &\mathds{S}_{\mathsf{N},\mathcal{P}} \\
-& \left((u^k)_{k \in \mathds{N}},(v^k)_{k \in \mathds{N}}\right) & \longmapsto & \left(\sigma^{v^0}\left((u^k)_{k \in \mathds{N}}\right),\sigma\left((v^k)_{k \in \mathds{N}}\right)\right). 
+& \left((u^k)_{k \in \mathds{N}},(v^k)_{k \in \mathds{N}}\right) & \mapsto & 
+\begin {array}{l}
+    \left(\sigma^{v^0}\left((u^k)_{k \in \mathds{N}}\right), \right. \\
+     \qquad \left. \sigma\left((v^k)_{k \in \mathds{N}}\right)\right).
+ \end{array} 
 \end{array}
-$$
+\]
+
 In other words, $\Sigma$ receives two sequences $u$ and $v$, and
 it operates $v^0$ shifts on the first sequence and a single shift
 on the second one. 
 Let
 \begin{equation}
 \begin{array}{cccc}
-G_f :&  \mathcal{X}_{\mathsf{N},\mathcal{P}} & \longrightarrow & \mathcal{X}_{\mathsf{N},\mathcal{P}}\\
-   & (e,(u,v)) & \longmapsto & \left( F_{f,v^0}\left( e, (u^0, \hdots, u^{v^0-1}\right), \Sigma (u,v) \right) .
+G_f :&  \mathcal{X}_{\mathsf{N},\mathcal{P}} & \rightarrow & \mathcal{X}_{\mathsf{N},\mathcal{P}}\\
+   & (e,(u,v)) & \mapsto & \left( F_{f,v^0}\left( e, (u^0, \hdots, u^{v^0-1}\right), \Sigma (u,v) \right) .
 \end{array}
 \end{equation}
 Then the outputs $(y^0, y^1, \hdots )$ produced by the $\textit{CIPRNG}_f^2(u,v)$ generator 
@@ -245,6 +253,7 @@ $\check{u}^{v^0}$ (on $n$ digits), ..., $\check{u}^{\check{v}^0-1}$ (on $n$ digi
 
 
 
+\newcommand{\ns}{$\hspace{.1em}$}
 
 \begin{xpl}
 Consider for instance that $\mathsf{N}=13$, $\mathcal{P}=\{1,2,11\}$ (so $\mathsf{p}=2$), and that
@@ -262,7 +271,7 @@ $\check{s}=\left\{
 \end{array}
 \right.$.
 
-So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.010004000000000000000000011005 ...$
+So $d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = 0.01\ns00\ns04\ns00\ns00\ns00\ns00\ns00\ns00\ns00\ns00\ns00\ns01\ns10\ns05 ...$
 Indeed, the $p=2$ first digits are 01, as $|v^0-\check{v}^0|=1$, 
 and we use $p$ digits to code this difference ($\mathcal{P}$ being $\{1,2,11\}$, this difference can be equal to 10). We then take the $v^0=1$ first terms of $u$, each term being coded in $n=2$ digits, that is, 06. As we can iterate
 at most $\max{(\mathcal{P})}$ times, we must complete this
@@ -304,16 +313,18 @@ where: % $p=\max \mathcal{P}$ and:
 \begin{itemize}
 \item $d_{\mathds{B}^\mathsf{N}}$ is the Hamming distance,
 \item $\forall s=(u,v), \check{s}=(\check{u},\check{v}) \in \mathcal{S}_{\mathsf{N},\mathcal{P}}$,\newline 
-$$\begin{array}{rcl}
- d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) &= &
-   \sum_{k=0}^\infty \dfrac{1}{10^{(k+1)p+kn\max{(\mathcal{P})}}} 
+\[
+\begin{array}{l}
+ d_{\mathds{S}_{\mathsf{N},\mathcal{P}}}(s,\check{s}) = \\
+  \quad  \sum_{k=0}^\infty \dfrac{1}{10^{(k+1)p+kn\max{(\mathcal{P})}}} 
    \bigg(|v^k - \check{v}^k|  \\
-   & & + \left| \sum_{l=0}^{v^k-1} 
+   \quad\quad + \left| \sum_{l=0}^{v^k-1} 
        \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{(l+1)n}} -
        \sum_{l=0}^{\check{v}^k-1} 
        \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{(l+1)n}} \right| \bigg)
 \end{array}
-$$ %\left| \sum_{l=0}^{v^k-1} \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{l}} - \sum_{l=0}^{\check{v}^k-1} \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{l}}\right|\right)}.$$
+\]
+ %\left| \sum_{l=0}^{v^k-1} \dfrac{u^{\sum_{m=0}^{k-1} v^m +l}}{ 10^{l}} - \sum_{l=0}^{\check{v}^k-1} \dfrac{\check{u}^{\sum_{m=0}^{k-1} \check{v}^m +l}}{ 10^{l}}\right|\right)}.
 \end{itemize}
 
 
@@ -402,7 +413,8 @@ $\Gamma(f)$.
     \caption{$\Gamma(f_0)$}
     \label{graphe1}
   \end{subfigure}%
-  ~ %add desired spacing between images, e. g. ~, \quad, \qquad, \hfill etc.
+  
+~ %add desired spacing between images, e. g. ~, \quad, \qquad, \hfill etc.
   % (or a blank line to force the subfigure onto a new line)
   \begin{subfigure}[b]{0.3\textwidth}
     \centering  
@@ -469,17 +481,17 @@ $V^{k_1+1}=|a_1|$, ..., $V^{k_1+k_2}=|a_{k_2}|$, and by
 $U^{k_1}=a_0^0$, $U^{k_1+1}=a_0^1$, ..., $U^{k_1+V_{k_1}-1}=a_0^{V_{k_1}-1}$,
 $U^{k_1+V_{k_1}}=a_1^{0}$, $U^{k_1+V_{k_1}+1}=a_1^{1}$,...
 
-Let $y=(e,((u^0, ..., u^{\sum_{l=0}^{k_1}v^l-1}, a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., 
- a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},$ \linebreak
- $\check{u}^0, \check{u}^1, ...),(v^0, ..., v^{k_1},|a_0|, ...,
- |a_{k_2}|,\check{v}^0, \check{v}^1, ...)))$. So $y\in \mathcal{B}(x,\varepsilon)$
+Let $y=(e,((u^0, \dots, u^{\sum_{l=0}^{k_1}v^l-1}, a_0^0, \dots, a_0^{|a_0|}, a_1^0, \dots, $ \linebreak 
+$a_1^{|a_1|},\dots, a_{k_2}^0, \dots, a_{k_2}^{|a_{k_2}|},$  
+ $\check{u}^0, \check{u}^1, \dots),(v^0, \dots, v^{k_1},|a_0|, \dots,$\linebreak
+ $|a_{k_2}|,\check{v}^0, \check{v}^1, \dots)))$. So $y\in \mathcal{B}(x,\varepsilon)$
  and $G_{f}^{k_1+k_2}(y)=\check{x}$.
  
  
 Conversely, if $\Gamma_{\mathcal{P}}(f)$ is not strongly connected, then there are 
 2 vertices $e_1$ and $e_2$ such that there is no path between $e_1$ and $e_2$.
 That is, it is impossible to find $(u,v)\in \mathds{S}_{\mathsf{N},\mathcal{P}}$
-and $n \mathds{N}$ such that $G_f^n(e,(u,v))_1=e_2$. The open ball $\mathcal{B}(e_2, 1/2)$
+and $n\in \mathds{N}$ such that $G_f^n(e,(u,v))_1=e_2$. The open ball $\mathcal{B}(e_2, 1/2)$
 cannot be reached from any neighborhood of $e_1$, and thus $G_f$ is not transitive.
 \end{proof}
 
@@ -494,16 +506,17 @@ regular on $(\mathcal{X}_{\mathsf{N},\mathcal{P}}, d)$.
 Let $x=(e,(u,v)) \in \mathcal{X}_{\mathsf{N},\mathcal{P}}$ and $\varepsilon >0$. 
 As in the proofs of Prop.~\ref{prop:trans}, let $k_1 \in \mathds{N}$ such
 that 
-$$\left\{(e, ((u^0, ..., u^{v^{k_1-1}},U^0, U^1, ...),(v^0, ..., v^{k_1},V^0, V^1, ...)) \mid \right.$$
+$$\left\{(e, ((u^0, \dots, u^{v^{k_1-1}},U^0, U^1, \dots),(v^0, \dots, v^{k_1},V^0, V^1, \dots)) \mid \right.$$
 $$\left.\forall i,j \in \mathds{N}, U^i \in \llbracket 1, \mathsf{N} \rrbracket, V^j \in \mathcal{P}\right\}
 \subset \mathcal{B}(x,\varepsilon),$$
 and $y=G_f^{k_1}(e,(u,v))$. $\Gamma_{\mathcal{P}}(f)$ being strongly connected,
-there is at least a path from the Boolean state $y_1$ of $y$ and $e$.
+there is at least a path from the Boolean state $y_1$ of $y$ and $e$ \ANNOT{Phrase pas claire : "from \dots " mais pas de "to \dots"}.
 Denote by $a_0, \hdots, a_{k_2}$ the edges of such a path.
-Then the point:
-$$(e,((u^0, ..., u^{v^{k_1-1}},a_0^0, ..., a_0^{|a_0|}, a_1^0, ..., a_1^{|a_1|},..., 
- a_{k_2}^0, ..., a_{k_2}^{|a_{k_2}|},u^0, ..., u^{v^{k_1-1}},$$
-$$a_0^0, ...,a_{k_2}^{|a_{k_2}|}...),(v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,v^0, ..., v^{k_1}, |a_0|, ..., |a_{k_2}|,...))$$
+Then the point:\linebreak
+$(e,((u^0, \dots, u^{v^{k_1-1}},a_0^0, \dots, a_0^{|a_0|}, a_1^0, \dots, a_1^{|a_1|},\dots, 
+ a_{k_2}^0, \dots,$ \linebreak 
+$\,a_{k_2}^{|a_{k_2}|},u^0, \dots, u^{v^{k_1-1}},a_0^0, \dots,a_{k_2}^{|a_{k_2}|}\dots),$\linebreak
+$(v^0, \dots, v^{k_1}, |a_0|, \dots, |a_{k_2}|,v^0, \dots, v^{k_1}, |a_0|, \dots, |a_{k_2}|,\dots))$
 is a periodic point in the neighborhood $\mathcal{B}(x,\varepsilon)$ of $x$.
 \end{proof}
 
