tt

[HindawiJournalOfChaos.git] / IH / notations.tex

\section{Notations and Terminologies}
\label{not}
% \subsection{Notations}
% \r
In what follows, $\mathbb{B}$ denotes the Boolean set $\{0,1\}$,\r
$S^{n}$ stands for the $n^{th}$ term of a sequence $S$,\r
$V_{i}$ is for the $i^{th}$ component of a vector $V$, and \r
$\llbracket0;N\rrbracket$ is the integer interval $\{0,1,\hdots,N\}$.

\begin{color}{red} Compléter éventuellement les notations\end{color}.
\r
% Furthermore, the following definitions will be used in this document.\r
% \r
% \begin{Def}%[Discrete Boolean metric]\r
% \label{def:discret-Boolean-metric}\r
% The \emph{discrete Boolean metric} is the\r
% application $\delta: \mathds{B} \longrightarrow \mathds{B}$ defined by\r
% $\delta(x,y)=0\Leftrightarrow x=y.$\r
% \end{Def}\r
% \r
% 
\subsection{The mathematical theory of chaos}


From  a  mathematical point  of  view,  deterministic  chaos has  been
thoroughly studied  these last decades, with  different research works
that  have   provided  various  definitions  of   chaos.   Among  these
definitions, the  one given  by Devaney~\cite{Devaney} is  perhaps one of the
most established ones.

Consider  a topological  space $(\mathcal{X},\tau)$  and  a continuous
function $f$ on  $\mathcal{X}$.  Topological transitivity occurs when,
for  any point, any  neighborhood of  its future  evolution eventually
overlap with any other given region. More precisely,

\begin{Def}
 $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 \emptyset$.
\end{Def}

This property  implies that a  dynamical system cannot be  broken into
simpler  subsystems.  It  is intrinsically  complicated and  cannot be
simplified.  Besides, a dense set  of periodic points is an element of
regularity that a chaotic dynamical system has to exhibit.

\begin{Def}
 An element (a point) $x$ is a \emph{periodic element} (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{Def}

\begin{Def}
 $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.
\end{Def}

This  regularity ``counteracts'' the  effects of  transitivity.  Thus,
due to these two properties, two points close to each other can behave
in a completely different  manner, leading to unpredictability for the
whole system.  Then,

\begin{Def}[Devaney's chaos]
 $f$ is said to be \emph{chao\-tic} on $(\mathcal{X},\tau)$ if $f$ is
 regular and topologically transitive.
\end{Def}

The chaos property is related to the notion of ``sensitivity'',
defined on a metric space $(\mathcal{X},d)$ by:

\begin{Def} \label{sensitivity} 
 $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 \geq 0$ such
 that $d\left(f^{n}(x), f^{n}(y)\right) >\delta $. 
 
 $\delta$ is called the \emph{constant of sensitivity} of $f$.
\end{Def}

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 sensitive  dependence  on  initial conditions  (this
property was formerly an element  of the definition of chaos).  
% To sum
% up, quoting Devaney in~\cite{Devaney}, a chaotic dynamical system ``is
% unpredictable   because  of  the   sensitive  dependence   on  initial
% conditions.   It  cannot  be   broken  down  or  simplified  into  two
% subsystems which do not  interact because of topological transitivity.
% And  in the midst  of this  random behavior,  we nevertheless  have an
% element  of  regularity''.    Fundamentally  different  behaviors  are
% consequently possible and occur in an unpredictable way.
% 

\subsection{Chaotic iterations and watermarking scheme}\r
\label{sec:chaotic iterations}\r
\r
\r
Let us consider  a \emph{system} with a finite  number $\mathsf{N} \in\r
\mathds{N}^*$ of \emph{cells}, so that each  cell has a\r
Boolean  \emph{state}. A sequence which  elements belong into $\llbracket 1;\mathsf{N}\r
\rrbracket $ is a \emph{strategy}. Finally, the set of all strategies is\r
denoted by $\llbracket 1, \mathsf{N} \rrbracket^\mathds{N}.$\r
\r
\begin{Def}\r
\label{Def:chaotic iterations}\r
The      set       $\mathds{B}$      denoting      $\{0,1\}$,      let\r
$f:\mathds{B}^{\mathsf{N}}\longrightarrow  \mathds{B}^{\mathsf{N}}$ be\r
a  function  and  $S\in  \llbracket 1, \mathsf{N} \rrbracket^\mathds{N}$.  The  \r
\emph{chaotic      iterations}  (CIs)   are     defined      by     $x^0\in\r
\mathds{B}^{\mathsf{N}}$ and\r
\begin{equation*}\r
\forall    n\in     \mathds{N}^{\ast     },    \forall     i\in\r
\llbracket1;\mathsf{N}\rrbracket ,x_i^n=\left\{\r
\begin{array}{ll}\r
  x_i^{n-1} &  \text{ if  }S^n\neq i \\\r
  \left(f(x^{n-1})\right)_{S^n} & \text{ if }S^n=i.\r
\end{array}\right.\r
\end{equation*}\r
\end{Def}\r
\r
In other words, at the $n^{th}$ iteration, only the $S^{n}-$th cell is\r
\textquotedblleft  iterated\textquotedblright .\r
Let us now recall how to define a suitable metric space where chaotic iterations\r
are continuous~\cite{guyeux10}.\r
\r
Let $\delta $ be the \emph{discrete Boolean metric}, $\delta\r
(x,y)=0\Leftrightarrow x=y.$ Given a function $f$, define the function:\r
\begin{equation*}\r
\begin{array}{ll}\r
F_{f}: & \llbracket1;\mathsf{N}\rrbracket\times \mathds{B}^{\mathsf{N}} \r
\longrightarrow  \mathds{B}^{\mathsf{N}} \\\r
& (k,E)  \longmapsto  \left( E_{j}.\delta (k,j)+f(E)_{k}.\overline{\delta\r
(k,j)}\right) _{j\in \llbracket1;\mathsf{N}\rrbracket}%\r
\end{array}%\r
\end{equation*}%\r
\noindent Consider the phase space\r
%\begin{equation}\r
$\mathcal{X} = \llbracket 1 ; \mathsf{N} \rrbracket^\mathds{N} \times\r
\mathds{B}^\mathsf{N}$,\r
%\end{equation}\r
\noindent and the map defined on $\mathcal{X}$ by:\r
\begin{equation}\r
G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right), \label{Gf}\r
\end{equation}\r
\noindent where $\sigma :\r
(S^{n})_{n\in \mathds{N}}\in \llbracket 1, \mathsf{N} \rrbracket^\mathds{N}\longrightarrow (S^{n+1})_{n\in\r
\mathds{N}}$ and %$i$ is the \emph{initial function} \r
$i:(S^{n})_{n\in \mathds{N}} \in \llbracket 1, \mathsf{N} \rrbracket^\mathds{N}\longrightarrow S^{0}$. Then chaotic iterations  can be described by \r
the following discrete dynamical system:\r
\begin{equation}\r
\left\{\r
\begin{array}{l}\r
X^0 \in \mathcal{X} \\\r
X^{k+1}=G_{f}(X^k).%\r
\end{array}%\r
\right.\r
\end{equation}%\r
\r
To study whether this dynamical system is chaotic~\cite{Devaney}, a distance between  $X = (S,E), Y =\r
(\check{S},\check{E})\in\r
\mathcal{X}$ has been introduced in~\cite{guyeux10} as follows:\r
$d(X,Y)=d_{e}(E,\check{E})+d_{s}(S,\check{S})$, where \r
\begin{itemize}\r
\item $\displaystyle{d_{e}(E,\check{E})}  =  \displaystyle{\sum_{k=1}^{\mathsf{N}%\r
}\delta (E_{k},\check{E}_{k})}$, \r
\item $\displaystyle{d_{s}(S,\check{S})}  =  \displaystyle{\dfrac{9}{\mathsf{N}}%\r
\sum_{k=1}^{\infty }\dfrac{|S_k-\check{S}_k|}{10^{k}}}.$\r
\end{itemize}\r
\r
\r
This distance has been introduced to satisfy the following requirements. If the floor\r
value $\lfloor d(X,Y)\rfloor $ is equal to $n$, then the systems $E, \check{E}$\r
differ in $n$ cells. In addition, its floating part is less than $10^{-k}$ if and only if the first\r
$k$ terms of the two strategies are equal. Moreover, if the $k^{th}$ digit is\r
nonzero, then the $k^{th}$ terms of the two strategies are different.\r
With this metric, it has been proven that~\cite{guyeux10},\r
\r
\begin{Th}\r
$G_{f_{0}}$ is continuous and chaotic in $(\mathcal{X},d)$.\r
\end{Th}\r
\r
\r
\r