X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/prng_gpu.git/blobdiff_plain/cc60d282e05dc7a348f70d66ebfb2173e0a82a79..12410996f49b94978103d0ba32d17f85c89fa51a:/prng_gpu.tex

diff --git a/prng_gpu.tex b/prng_gpu.tex
index 307f55d..082c379 100644
--- a/prng_gpu.tex
+++ b/prng_gpu.tex
@@ -50,7 +50,84 @@ Interet de générer des nombres alea sur GPU
 
 Présentation des itérations chaotiques
 
-\section{blabla}
+
+
+
+\section{The relativity of disorder}
+\label{sec:de la relativité du désordre}
+
+\subsection{Impact of the topology's finenesse}
+
+Let us firstly introduce the following notations.
+
+\begin{notation}
+$\mathcal{X}_\tau$ will denote the topological space $\left(\mathcal{X},\tau\right)$, whereas $\mathcal{V}_\tau (x)$ will be the set of all the neighborhoods of $x$ when considering the topology $\tau$ (or simply $\mathcal{V} (x)$, if there is no ambiguity).
+\end{notation}
+
+
+
+\begin{theorem}
+\label{Th:chaos et finesse}
+Let $\mathcal{X}$ a set and $\tau, \tau'$ two topologies on $\mathcal{X}$ s.t. $\tau'$ is finer than $\tau$. Let $f:\mathcal{X} \to \mathcal{X}$, continuous both for $\tau$ and $\tau'$.
+
+If $(\mathcal{X}_{\tau'},f)$ is chaotic according to Devaney, then $(\mathcal{X}_\tau,f)$ is chaotic too.
+\end{theorem}
+
+\begin{proof}
+Let us firstly establish the transitivity of $(\mathcal{X}_\tau,f)$.
+
+Let $\omega_1, \omega_2$ two open sets of $\tau$. Then $\omega_1, \omega_2 \in \tau'$, becaus $\tau'$ is finer than $\tau$. As $f$ is $\tau'-$transitive, we can deduce that $\exists n \in \mathds{N}, \omega_1 \cap f^{(n)}(\omega_2) = \varnothing$. Consequently, $f$ is $\tau-$transitive.
+
+Let us now consider the regularity of $(\mathcal{X}_\tau,f)$, \emph{i.e.}, for all $x \in \mathcal{X}$, and for all $\tau-$neighborhood $V$ of $x$, there is a periodic point for $f$ into $V$.
+
+Let $x \in \mathcal{X}$ and $V \in \mathcal{V}_\tau (x)$ a $\tau-$neighborhood of $x$. By definition, $\exists \omega \in \tau, x \in \omega \subset V$.
+
+But $\tau \subset \tau'$, so $\omega \in \tau'$, and then $V \in \mathcal{V}_{\tau'} (x)$. As $(\mathcal{X}_{\tau'},f)$ is regular, there is a periodic point for $f$ into $V$, and the regularity of $(\mathcal{X}_\tau,f)$ is proven.
+\end{proof}
+
+\subsection{A given system can always be claimed as chaotic}
+
+Let $f$ an iteration function on $\mathcal{X}$ having at least a fixed point. Then this function is chaotic (in a certain way):
+
+\begin{theorem}
+Let $\mathcal{X}$ a nonempty set and $f: \mathcal{X} \to \X$ a function having at least a fixed point.
+Then $f$ is $\tau_0-$chaotic, where $\tau_0$ is the trivial (indiscrete) topology on $\X$.
+\end{theorem}
+
+
+\begin{proof}
+$f$ is transitive when $\forall \omega, \omega' \in \tau_0 \setminus \{\varnothing\}, \exists n \in \mathds{N}, f^{(n)}(\omega) \cap \omega' \neq \varnothing$.
+As $\tau_0 = \left\{ \varnothing, \X \right\}$, this is equivalent to look for an integer $n$ s.t. $f^{(n)}\left( \X \right) \cap \X \neq \varnothing$. For instance, $n=0$ is appropriate.
+
+Let us now consider $x \in \X$ and $V \in \mathcal{V}_{\tau_0} (x)$. Then $V = \mathcal{X}$, so $V$ has at least a fixed point for $f$. Consequently $f$ is regular, and the result is established.
+\end{proof}
+
+
+
+
+\subsection{A given system can always be claimed as non-chaotic}
+
+\begin{theorem}
+Let $\mathcal{X}$ be a set and $f: \mathcal{X} \to \X$.
+If $\X$ is infinite, then $\left( \X_{\tau_\infty}, f\right)$ is not chaotic (for the Devaney's formulation), where $\tau_\infty$ is the discrete topology.
+\end{theorem}
+
+\begin{proof}
+Let us prove it by contradiction, assuming that $\left(\X_{\tau_\infty}, f\right)$ is both transitive and regular.
+
+Let $x \in \X$ and $\{x\}$ one of its neighborhood. This neighborhood must contain a periodic point for $f$, if we want that $\left(\X_{\tau_\infty}, f\right)$ is regular. Then $x$ must be a periodic point of $f$.
+
+Let $I_x = \left\{ f^{(n)}(x), n \in \mathds{N}\right\}$. This set is finite because  $x$ is periodic, and $\mathcal{X}$ is infinite, then $\exists y \in \mathcal{X}, y \notin I_x$.
+
+As $\left(\X_{\tau_\infty}, f\right)$ must be transitive, for all open nonempty sets $A$ and $B$, an integer $n$ must satisfy $f^{(n)}(A) \cap B \neq \varnothing$. However $\{x\}$ and $\{y\}$ are open sets and $y \notin I_x \Rightarrow \forall n, f^{(n)}\left( \{x\} \right) \cap \{y\} = \varnothing$.
+\end{proof}
+
+
+
+
+
+
+\section{Chaos on the order topology}
 
 \subsection{The phase space is an interval of the real line}
 
@@ -251,13 +328,13 @@ In other words, $\mathcal{X}$ is approximately equal to $\big[ 0, 2^\mathsf{N} \
 \end{figure}
 
 
-We have written a Python program to represent the chaotic iterations with the vectorial negation on the real line $\mathds{R}$. Various representations of these CIs are given in Figures \ref{fig:ICs}, \ref{fig:ICs2} and \ref{fig:ICs3}. It can be remarked that the function $g$ is \alert{affine par morceaux}: it is linear on each interval having the form $\left[ \dfrac{n}{10}, \dfrac{n+1}{10}\right[$, $n \in \llbracket 0;2^{10}\times 10 \rrbracket$ \alert{and its line has a pent equal to 10}. Let us justify these claims:
+We have written a Python program to represent the chaotic iterations with the vectorial negation on the real line $\mathds{R}$. Various representations of these CIs are given in Figures \ref{fig:ICs}, \ref{fig:ICs2} and \ref{fig:ICs3}. It can be remarked that the function $g$ is a piecewise linear function: it is linear on each interval having the form $\left[ \dfrac{n}{10}, \dfrac{n+1}{10}\right[$, $n \in \llbracket 0;2^{10}\times 10 \rrbracket$ and its slope is equal to 10. Let us justify these claims:
 
 \begin{proposition}
 \label{Prop:derivabilite des ICs}
-Chaotic iterations $g$ defined on $\mathds{R}$ are \alert{infiniment dérivables} on $\big[ 0, 2^{10} \big[$, except on the 10241 points in $I$ defined by $\left\{ \dfrac{n}{10} ~\big/~ n \in \llbracket 0;2^{10}\times 10\rrbracket \right\}$.
+Chaotic iterations $g$ defined on $\mathds{R}$ have derivatives of all orders on $\big[ 0, 2^{10} \big[$, except on the 10241 points in $I$ defined by $\left\{ \dfrac{n}{10} ~\big/~ n \in \llbracket 0;2^{10}\times 10\rrbracket \right\}$.
 
-Furthermore, on each interval of the form $\left[ \dfrac{n}{10}, \dfrac{n+1}{10}\right[$, with $n \in \llbracket 0;2^{10}\times 10 \rrbracket$, the function $g$ is \emph{affine}. \alert{It is a line of pent equal to 10}: $\forall x \notin I, g'(x)=10$.
+Furthermore, on each interval of the form $\left[ \dfrac{n}{10}, \dfrac{n+1}{10}\right[$, with $n \in \llbracket 0;2^{10}\times 10 \rrbracket$, $g$ is a linear function, having a slope equal to 10: $\forall x \notin I, g'(x)=10$.
 \end{proposition}
 
 
@@ -271,7 +348,7 @@ To sum up, the action of $g$ on the points of $I$ is as follows: first, make a m
 \end{proof}
 
 \begin{remark}
-Finally, chaotic iterations are elements of the large family of functions that are \alert{chaotiques linéaires par morceaux}, like the tent map, the \alert{doublement de l'angle}, \emph{etc.}
+Finally, chaotic iterations are elements of the large family of functions that are both chaotic and piecewise linear (like the tent map).
 \end{remark}
 
 
@@ -308,7 +385,7 @@ If $D(x^n,x) \to 0$, then $D_e(x^n,x) = 0$ at least for $n$ larger than a given
 Additionally, $D_s(x^n, x) \to 0$, then $\forall k \in \mathds{N}^*, \exists N_k \in \mathds{N}, n \geqslant N_k \Rightarrow D_s(x^n,x) \leqslant 10^{-k}$. This means that for all $k$, an index $N_k$ can be found such that, $\forall n \geqslant N_k$, all the $x^n$ have the same $k$ firsts digits, which are the digits of $x$. We can deduce the convergence $\Delta(x^n,x) \to 0$, and thus the result.
 \end{proof}
 
-The conclusion of these propositions is that the proposed metric is more \alert{précise} than the Euclidian distance, that is:
+The conclusion of these propositions is that the proposed metric is more precise than the Euclidian distance, that is:
 
 \begin{corollary}
 $D$ is finer than the Euclidian distance $\Delta$.
@@ -330,22 +407,22 @@ This corollary can be reformulated as follows:
 
 \subsubsection{Chaos according to Devaney}
 
-We have recalled previously that the chaotic iterations $\left(\Go, \mathcal{X}_d\right)$ are chaotic according to the formulation of Devaney. We can deduce that they are chaotic on $\mathds{R}$ too, when considering the \alert{topology of order}, because:
+We have recalled previously that the chaotic iterations $\left(\Go, \mathcal{X}_d\right)$ are chaotic according to the formulation of Devaney. We can deduce that they are chaotic on $\mathds{R}$ too, when considering the order topology, because:
 \begin{itemize}
 \item $\left(\Go, \mathcal{X}_d\right)$ and $\left(g, \big[ 0, 2^{10} \big[_D\right)$ are semiconjugate by $\varphi$,
 \item Then $\left(g, \big[ 0, 2^{10} \big[_D\right)$ is a system chaotic according to Devaney, because the semiconjugacy preserve this character.
-\item But the topology generated by $D$ is finer than the topology generated by the Euclidian distance $\Delta$ -- which is the \alert{topology of order}.
-\item According to Theorem \ref{Th:chaos et finesse}, we can deduce that the chaotic iterations $g$ are indeed chaotic, as defined by Devaney, for the \alert{topology of order} on $\mathds{R}$.
+\item But the topology generated by $D$ is finer than the topology generated by the Euclidian distance $\Delta$ -- which is the order topology.
+\item According to Theorem \ref{Th:chaos et finesse}, we can deduce that the chaotic iterations $g$ are indeed chaotic, as defined by Devaney, for the order topology on $\mathds{R}$.
 \end{itemize}
 
 This result can be formulated as follows.
 
 \begin{theorem}
 \label{th:IC et topologie de l'ordre}
-The chaotic iterations $g$ on $\mathds{R}$ are chaotic according to the Devaney's formulation, when $\mathds{R}$ has his usual topology, which is the \alert{topology of order}.
+The chaotic iterations $g$ on $\mathds{R}$ are chaotic according to the Devaney's formulation, when $\mathds{R}$ has his usual topology, which is the order topology.
 \end{theorem}
 
-Indeed this result is \alert{weaker} than the theorem establishing the chaos for the finer topology $d$. However the Theorem \ref{th:IC et topologie de l'ordre} still remains important. Indeed, we have studied in our previous works a set different from the usual set of study ($\mathcal{X}$ instead of $\mathds{R}$), in order to be as close as possible from the computer: the properties of disorder proved theoretically will then be preserved when computing. However, we could wonder whether this change does not lead to a disorder of a lower quality. In other words, have we replaced a situation of a good disorder lost when computing, to another situation of a disorder preserved but of bad quality. Theorem \ref{th:IC et topologie de l'ordre} prove exactly the contrary.
+Indeed this result is weaker than the theorem establishing the chaos for the finer topology $d$. However the Theorem \ref{th:IC et topologie de l'ordre} still remains important. Indeed, we have studied in our previous works a set different from the usual set of study ($\mathcal{X}$ instead of $\mathds{R}$), in order to be as close as possible from the computer: the properties of disorder proved theoretically will then be preserved when computing. However, we could wonder whether this change does not lead to a disorder of a lower quality. In other words, have we replaced a situation of a good disorder lost when computing, to another situation of a disorder preserved but of bad quality. Theorem \ref{th:IC et topologie de l'ordre} prove exactly the contrary.