\end{itemize}
These considerations lead to the following definition of an iterative
-system.
+system~\cite{GuyeuxThese10}.
\begin{definition}
Iterative systems on a set $\mathcal{X}$ are defined by
In the serial mode, each component is updated one by one, whereas the
parallel mode consists in updating all the components at each iteration,
leading to an usual discrete dynamical system.
-These modes are compiliant with the definition above,
-
-On appelle \emph{itérations parallèles} \index{itérations!parallèles} de $f$ sur
-$\mathcal{X}$ toute itération synchrone $\Sigma = (\mathcal{X}, \mathcal{F})$
-telle que la suite $\mathcal{F}$ est constante égale à $f: \X \to \X$.
-On parle encore d'itérations parallèles $\left(\mathcal{X},f\right)$.
+These modes are compliant with the definition above,
+as the parallel mode consists in considering that the sequence
+$f^n$ defined above is constant equal to a given $f: \mathcal{X}
+\longrightarrow \mathcal{X}$,
+whereas the serial mode can be rewritten as parallel iterations of
+$$ G=F_\mathsf{N} \circ \ldots \circ F_2 \circ F_1 $$
+where, $\forall i \in \llbracket 1, \mathsf{N} \rrbracket $:
+$$\begin{array}{rccc}
+F_i: & \mathcal{X} & \longrightarrow & \mathcal{X}\\
+ & (x_1, \hdots, x_\mathsf{N}) & \longmapsto & \left(x_1, \hdots, x_{i-1},f_i\left(x_1, \hdots, x_\mathsf{N}\right), x_{i+1}, \hdots, x_\mathsf{N}\right).
+\end{array}$$
Finally, iterative systems in chaotic mode, simply called chaotic iterations,
- are defined as follows.
+are defined as follows~\cite{Robert}.
\begin{definition}
Let $f: \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$ and
$S \subset \mathcal{P} \left(\llbracket1,\mathsf{N}\rrbracket\right)^\mathds{N}$.
-\emph{Chaotic iterations} are defined by:
+\emph{Chaotic iterations} $(f, (x^0, S))$ are defined by:
$$\left\{
\begin{array}{l}
x^0 \in \mathds{B}^\mathsf{N} \\
On our side, we have regarded whether these chaotic iterations can
behave chaotically, as it is defined for instance by Devaney, and if so,
in which applicative context this behavior can be profitable.
-This questionning has led to a first necessary condition of non convergence.
+This questioning has led to a first necessary condition of non convergence~\cite{GuyeuxThese10}.
\begin{proposition}
Let $f : \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$ and
$S \in \llbracket 1, \mathsf{N} \rrbracket^{\mathds{N}}$.
If the chaotic iterations $\left(f,(x^0,S)\right)$ are not convergent, then:
\begin{itemize}
-\item either $f$ is not a contraction,
-\item or $S$ is not pseudo-periodic.
+\item either $f$ is not a contraction, meaning that there is no Boolean matrix
+ $M$ of size $\mathsf{N}$ satisfying $\forall x,y\in \mathds{B}^\mathsf{N}$,
+ $d(f(x),f(y)) \leqslant M d(x,y)$, where $d$ is here the ``vectorial distance''
+ defined by $d(x,y) = \left(\begin{array}{c} \delta(x_1,y_1)\\ \vdots \\ \delta(x_\mathsf{N},
+ y_\mathsf{N}) \end{array}\right)$, with $\delta$ the discrete metric defined by $\delta(x,y) = \left\{\begin{matrix} 1 &\mbox{if}\ x\neq y , \\ 0 &\mbox{if}\ x = y \end{matrix}\right.$, and $\leqslant$ is the inequality term by term~\cite{Robert}.
+\item or $S$ is not pseudo-periodic: it is not constituted by an infinite succession of finite sequences, each having any element of $\llbracket
+ 1, \mathsf{N} \rrbracket$ at least once.
\end{itemize}
\end{proposition}
-The quantity of disorder generated by such chaotic iterations, when satisfying
-the proposition above, has then been measured. To do so, chaotic iterations
-have first been rewriten as simple discrete dynamical systems, as follows.
-
-
-
-
-
-
-%\frame{
-%\frametitle{Présentation du problème}
-
-%\begin{tabular}{c||c}
-%MATHS DISCRÈTES & TOPOLOGIE MATHÉMATIQUE \tabularnewline
-%\hline
-%\multirow{2}{5cm}{\centering $f: \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$} & $(\mathcal{X},\tau)$ espace topologique\\
-%& $f : \mathcal{X} \to \mathcal{X}$ continue pour $\tau$\\
-%\hline
-%$S \in \mathcal{S} = \llbracket 1,\mathsf{N}\rrbracket^\mathds{N}$ & \multirow{2}{5cm}{\centering $x^0 \in \mathcal{X}$} \\
-%$x^0 \in \mathds{B}^\mathds{N}$ & \\
-%\hline
-%$x_i^{n+1} = \left\{ \begin{array}{ll} x^{n}_{i} & \textrm{ si } i \neq S^n\\ f(x^{n})_{i} & \textrm{ si } i = S^n \end{array} \right.$ & $\forall n \in \mathds{N}, x^{n+1} = f(x^n)$ \\
-%\end{tabular}
-
-%}
-
-
-
-
-
-
-%\frame{
-%\frametitle{Définitions et notations}
-%\begin{block}{Introduisons quelques fonctions...}
-%\begin{itemize}
-%\item décalage: $\sigma : \mathcal{S} \longrightarrow \mathcal{S}, (S^n)_{n \in \mathds{N}} \mapsto (S^{n+1})_{n \in \mathds{N}}$.
-%\item initiale: $i : \mathcal{S} \longrightarrow \llbracket 1 ; \mathsf{N} \rrbracket, (S^n)_{n \in \mathds{N}} \mapsto S^0$
-%\item $F_f : \llbracket 1 ; \mathsf{N} \rrbracket \times \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N},$ $$(k,E) \longmapsto \left( E_j.\delta(k,j) + f(E)_k.\overline{\delta (k,j)} \right)_{j \in \llbracket 1 ; \mathsf{N} \rrbracket}$$
-%\end{itemize}
-%où $\delta(x,y) = \left\{\begin{array}{ll}
-%0 & \textrm{ si } x=y, \\
-%1 & \textrm{ sinon.}
-% \end{array}\right.
-%$
-%\end{block}
-%}
-
-
-
-
-%\frame{
-%\frametitle{Modélisation des IC}
-%\begin{alertblock}{Modélisation des IC en topologie}
-%Soit $\mathcal{X} = \llbracket 1 ; \mathsf{N} \rrbracket^\mathds{N} \times \mathds{B}^\mathsf{N},$ et $G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right).$
-
-
-%On modélise les itérations chaotiques $\left(f, (S,x^0)\right)$ par le système dynamique discret:
-%$$\left\{
-%\begin{array}{l}
-%X^0 = (S,x^0) \in \mathcal{X}, \\
-%\forall k \in \mathds{N}, X^{k+1} = G_f(X^k).
-%\end{array}
-%\right.$$
-%\end{alertblock}
-
-% \uncover<2>{
-% On peut donc étudier leur désordre topologique.
-% }
-%}
-
-
-
+The second alternative of the proposition above concerns the strategy,
+which should be provided by the outside world. Indeed, in our opinion,
+chaotic iterations can receive a PRNG $S$ as input, and due to
+properties of disorder of $f$, generate a new pseudorandom sequence
+that presents better statistical properties than $S$. Having this
+approach in mind, we thus have searched vectorial Boolean iteration
+functions that are not contractions. The vectorial negation function
+$f_0:\mathds{B}^\mathsf{N} \longrightarrow \mathds{N}^\mathsf{N},$
+$(x_1, \hdots, x_\mathsf{N}) \longmapsto (\overline{x_1}, \hdots,
+\overline{x_\mathsf{N}}) $ is such a function, which served has a
+model in our further studies ($\overline{x}$ stands for the negation
+of the Boolean $x$).
+
+The quantity of disorder generated by such chaotic iterations, when
+satisfying the proposition above, has then been measured. To do so,
+chaotic iterations have first been rewritten as simple discrete
+dynamical systems, as follows.
+
+
+\subsection{Chaotic Iterations as Dynamical Systems}
+
+The problems raised by such a formalization can be summarized as
+follows.
+Chaotic iterations are defined in the discrete mathematics framework,
+considering $x^0 \in \mathds{B}^\mathds{N}$ and $S \in \mathcal{S} = \llbracket 1,\mathsf{N}\rrbracket^\mathds{N}$, and iterations having the
+form
+$$x_i^{n+1} = \left\{ \begin{array}{ll} x^{n}_{i} & \textrm{ si } i \neq S^n\\ f(x^{n})_{i} & \textrm{ si } i = S^n \end{array} \right.$$
+where $f: \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$.
+However, the mathematical theory of chaos takes place into a
+topological space $(\mathcal{X},\tau)$. It studies the iterations
+$x^0 \in \mathcal{X}$, $\forall n \in \mathds{N}, x^{n+1} = f(x^n)$,
+where $f : \mathcal{X} \to \mathcal{X}$ is continuous for the
+topology $\tau$.
+
+To realize the junction between these two frameworks, the following
+material has been introduced~\cite{GuyeuxThese10,bgw09:ip}:
+\begin{itemize}
+\item the shift function: $\sigma : \mathcal{S} \longrightarrow \mathcal{S}, (S^n)_{n \in \mathds{N}} \mapsto (S^{n+1})_{n \in \mathds{N}}$.
+\item the initial function, defined by $i : \mathcal{S} \longrightarrow \llbracket 1 ; \mathsf{N} \rrbracket, (S^n)_{n \in \mathds{N}} \mapsto S^0$
+\item and $F_f : \llbracket 1 ; \mathsf{N} \rrbracket \times \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N},$ $$(k,E) \longmapsto \left( E_j.\delta(k,j) + f(E)_k.\overline{\delta (k,j)} \right)_{j \in \llbracket 1 ; \mathsf{N} \rrbracket}$$
+\end{itemize}
+where $\delta$ is the discrete metric.
-%\frame{
-% \frametitle{Métrique et continuité}
-%Distance sur $\mathcal{X}:$
-%$$d((S,E);(\check{S};\check{E})) = d_e(E,\check{E}) + d_s(S,\check{S})$$
-
-%\noindent où $\displaystyle{d_e(E,\check{E}) = \sum_{k=1}^\mathsf{N} \delta (E_k, \check{E}_k)}$, ~~et~ $\displaystyle{d_s(S,\check{S}) = \dfrac{9}{\textsf{N}} \sum_{k = 1}^\infty \dfrac{|S^k-\check{S}^k|}{10^k}}$.
-%%\end{block}
-%\vspace{0.5cm}
+Let $\mathcal{X} = \llbracket 1 ; \mathsf{N} \rrbracket^\mathds{N} \times \mathds{B}^\mathsf{N},$ and $G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right).$
+Chaotic iterations $\left(f, (S,x^0)\right)$ can be modeled by the
+discrete dynamical system:
+$$\left\{
+\begin{array}{l}
+X^0 = (S,x^0) \in \mathcal{X}, \\
+\forall k \in \mathds{N}, X^{k+1} = G_f(X^k).
+\end{array}
+\right.$$
+Their topological disorder can then be studied.
+To do so, a relevant distance must be defined of $\mathcal{X}$, as
+follows~\cite{GuyeuxThese10,bgw09:ip}:
+$$d((S,E);(\check{S};\check{E})) = d_e(E,\check{E}) + d_s(S,\check{S})$$
+\noindent where $\displaystyle{d_e(E,\check{E}) = \sum_{k=1}^\mathsf{N} \delta (E_k, \check{E}_k)}$, ~~and~ $\displaystyle{d_s(S,\check{S}) = \dfrac{9}{\textsf{N}} \sum_{k = 1}^\infty \dfrac{|S^k-\check{S}^k|}{10^k}}$.
-%\begin{alertblock}{Théorème}
-%La fonction $G_f : (\mathcal{X},d) \to (\mathcal{X},d)$ est continue.
-%\end{alertblock}
+This new distance has been introduced in \cite{bgw09:ip} to satisfy the following requirements.
+\begin{itemize}
+\item When the number of different cells between two systems is increasing, then their distance should increase too.
+\item In addition, if two systems present the same cells and their respective strategies start with the same terms, then the distance between these two points must be small because the evolution of the two systems will be the same for a while. Indeed, the two dynamical systems start with the same initial condition, use the same update function, and as strategies are the same for a while, then components that are updated are the same too.
+\end{itemize}
+The distance presented above follows these recommendations. Indeed, if the floor value $\lfloor d(X,Y)\rfloor $ is equal to $n$, then the systems $E, \check{E}$ differ in $n$ cells. In addition, $d(X,Y) - \lfloor d(X,Y) \rfloor $ is a measure of the differences between strategies $S$ and $\check{S}$. More precisely, this floating part is less than $10^{-k}$ if and only if the first $k$ terms of the two strategies are equal. Moreover, if the $k^{th}$ digit is nonzero, then the $k^{th}$ terms of the two strategies are different.
-%}
+It has then be stated that
+\begin{proposition}
+$G_f : (\mathcal{X},d) \to (\mathcal{X},d)$ is a continuous function
+\end{proposition}
+With all this material, the study of chaotic iterations as a discrete
+dynamical system has then be realized.
+This study is summarized in the next section.
+\subsection{Topological Properties of Chaotic Iterations}
-% \frame{
-% \frametitle{\'Etude de $(\mathcal{X},d)$}
-% \begin{block}{Propriétés de $(\mathcal{X},d)$}
-% \begin{itemize}
-% \item $\mathcal{X}$ est infini indénombrable
-% \vspace{0.15cm}
-% \item $(\mathcal{X},d)$ est un espace métrique compact, complet et parfait
-% \end{itemize}
-% \end{block}
-%
-% \vspace{0.5cm}
-%
-% \begin{block}{\'Etude de $G_{f_0}$}
-% $G_{f_0}$ est surjective, mais pas injective \vspace{0.3cm}\newline $\Rightarrow (\mathcal{X},G_{f_0})$ pas réversible.
-% \end{block}
-
-% }
-
+The topological space on which chaotic iterations are defined has
+firstly been investigated, leading to the following result~\cite{gb11:bc,GuyeuxThese10}:
+\begin{proposition}
+$\mathcal{X}$ is an infinitely countable metric space, being both
+compact, complete, and perfect (each point is an accumulation point).
+\end{proposition}
+These properties are required in some topological specific
+formalization of a chaotic dynamical system, justifying their
+proofs.
+Concerning $G_{f_0}$, it has been stated that~\cite{GuyeuxThese10}.
+\begin{proposition}
+$G_{f_0}$ is surjective, but not injective, and so the dynamical system $(\mathcal{X},G_{f_0})$ is not reversible.
-%%\frame{
-%% \frametitle{Etude des périodes}
-%% \begin{block}{Multiplicité des périodes ?}
-%% Soit $f_0:\mathds{B}^\mathsf{N} \rightarrow \mathds{B}^\mathsf{N}$ la négation vectorielle.
-%% \begin{itemize}
-%% \item $\forall k \in \mathds{N}, Per_{2k+1}(G_{f_0}) = \varnothing, card\left(Per_{2k+2}(G_{f_0})\right)>0$ \vspace{0.3cm} \linebreak $\Rightarrow G_{f_0}$ pas chaotique sur $\mathcal{X}$
-%% \item Cependant :
-%% \begin{itemize}
-%% \item Il y a chaos sur $\mathcal{X}^G = \mathcal{P}\left(\llbracket 1,\mathsf{N}\rrbracket\right)^\mathds{N}\times \mathds{B}^\mathsf{N}$.
-%% \item $G_{f_0}$ possède plus de $n^2$ points périodiques de période $2n$.
-%% \end{itemize}
-%% \end{itemize}
-%% \end{block}
-%% \uncover<2->{
-%% Cette multiplicité des périodes n'est pas le désordre complet...
-%% }
-%%}
+Furthermore, if we denote by $Per_k(f)$ the set of periodic points
+of period $k$ for $f$, we have
+ $\forall k \in \mathds{N}, Per_{2k+1}(G_{f_0}) = \varnothing, card\left(Per_{2k+2}(G_{f_0})\right)>0$.
+\end{proposition}
+
+So $\Rightarrow G_{f_0}$ does not present the existence of points of any period referred as chaos in the article of Li and Yorke~\cite{Li75}.
+However~\cite{GuyeuxThese10}:
+ \begin{itemize}
+ \item This kind of disorder can be stated on $\mathcal{X}^G = \mathcal{P}\left(\llbracket 1,\mathsf{N}\rrbracket\right)^\mathds{N}\times \mathds{B}^\mathsf{N}$.
+ \item $G_{f_0}$ possesses more than $n^2$ points of period $2n$.
+ \end{itemize}
+Additionally, this existence of points of any period has been rejected
+by the community to the benefit of more recent notions of chaos, as
+they are detailed in the following paragraphs.
