Many approaches have been developed to solve the problem of building
-a Gray code in a $\mathsf{N}$ cube~\cite{}, according to properties
+a Gray code in a $\mathsf{N}$ cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04,Bykov2016}, according to properties
the produced code has to verify.
-For instance,~\cite{ZanSup04,DBLP:journals/combinatorics/BhatS96} focus on
+For instance,~\cite{DBLP:journals/combinatorics/BhatS96,ZanSup04} focus on
balanced Gray codes. In the transition sequence of these codes,
the number of transitions of each element must differ
at most by 2.
balanced Gray codes that are generated by state of the art works~\cite{ZanSup04,DBLP:journals/combinatorics/BhatS96} are not locally balanced. Conversely,
locally balanced Gray codes yielded by Igor Bykov approach~\cite{Bykov2016}
are not globally balanced.
-This section thus show how the non deterministic approach
+This section thus shows how the non deterministic approach
presented in~\cite{ZanSup04} has been automatized to provide balanced
Hamiltonian paths such that, for each subpart,
-the number of swiches of each element is as constant as possible.
+the number of switches of each element is as uniform as possible.
+\subsection{Analysis of the Robinson-Cohn extension algorithm}
+As far as we know three works,
+namely~\cite{Robinson:1981:CS},~\cite{DBLP:journals/combinatorics/BhatS96},
+and~\cite{ZanSup04} have adressed the probem of providing an approach
+to produce balanced gray code.
+The authors of~\cite{Robinson:1981:CS} introduced an inductive approach
+aiming at producing balanced Gray codes, provided the user gives
+a special subsequence of the transition sequence at each induction step.
+This work have been strengthened in~\cite{DBLP:journals/combinatorics/BhatS96}
+where the authors have explicitely shown how to construct such a subsequence.
+Finally the authors of~\cite{ZanSup04} have presented
+the \emph{Robinson-Cohn extension}
+algorithm. There rigourous presentation of this one
+have mainly allowed them to prove two properties.
+The former states that if
+$\mathsf{N}$ is a 2-power, a balanced Gray code is always totally balanced.
+The latter states that for every $\mathsf{N}$ there
+exists a Gray code such that all transition count numbers are
+are 2-powers whose exponents are either equal
+or differ from each other by 1.
+However, the authors do not prove that the approach allows to build
+(totally balanced) Gray code.
+What follows shows that this fact is established and first recalls the approach.
+
+Let be given a $\mathsf{N}-2$-bit Gray code whose transition sequence is
+$S_{\mathsf{N}-2}$. What follows is the
+ \emph{Robinson-Cohn extension} method~\cite{ZanSup04}
+which produces a $n$-bits Gray code.
+
+\begin{enumerate}
+\item \label{item:nondet}Let $l$ be an even positive integer. Find
+$u_1, u_2, \dots , u_{l-2}, v$ (maybe empty) subsequences of $S_{\mathsf{N}-2}$
+such that $S_{\mathsf{N}-2}$ is the concatenation of
+$$
+s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, . . . , s_{i_l-1}, u_{l-2}, s_{i_l}, v
+$$
+where $i_1 = 1$, $i_2 = 2$, and $u_0 = \emptyset$ (the empty sequence).
+\item Replace in $S_{\mathsf{N}-2}$ the sequences $u_0, u_1, u_2, \ldots, u_{l-2}$
+ by
+ $\mathsf{N} - 1, u'(u_1,\mathsf{N} - 1, \mathsf{N}) , u'(u_2,\mathsf{N}, \mathsf{N} - 1), u'(u_3,\mathsf{N} - 1,\mathsf{N}), \dots, u'(u_{l-2},\mathsf{N}, \mathsf{N} - 1)$
+ respectively, where $u'(u,x,y)$ is the sequence $u,x,u^R,y,u$ such that
+ $u^R$ is $u$ in reversed order.
+ The obtained sequence is further denoted as $U$.
+\item Construct the sequences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$, and let $W'$ be $W$ where the first
+two elements have been exchanged.
+\item The transition sequence $S_{\mathsf{N}}$ is thus the concatenation $U^R, V, W'$.
+\end{enumerate}
+
+It has been proven in~\cite{ZanSup04} that
+$S_{\mathsf{N}}$ is transition sequence of a cyclic $\mathsf{N}$-bits Gray code
+if $S_{\mathsf{N}-2}$ is.
+However, the step~(\ref{item:nondet}) is not a constructive
+step that precises how to select the subsequences which ensures that
+yielded Gray code is balanced.
+Next section shows how to choose the sequence $l$ to have the balancy property.
+
+\subsection{Balanced Codes}
+Let us first recall how to formalize the balancy property of a Gray code.
+Let $L = w_1, w_2, \dots, w_{2^\mathsf{N}}$ be the sequence
+of a $\mathsf{N}$-bits cyclic Gray code.
+The transition sequence
+$S = s_1, s_2, \dots, s_{2^n}$, $s_i$, $1 \le i \le 2^\mathsf{N}$,
+indicates which bit position changes between
+codewords at index $i$ and $i+1$ modulo $2^\mathsf{N}$.
+The \emph{transition count} function
+$\textit{TC}_{\mathsf{N}} : \{1,\dots, \mathsf{N}\} \rightarrow \{0, \ldots, 2^{\mathsf{N}}\}$
+gives the number of times $i$ occurs in $S$,
+\textit{i.e.}, the number of times
+the bit $i$ has been switched in $L$.
+
+The Gray code is \emph{totally balanced} if $\textit{TC}_{\mathsf{N}}$
+is constant (and equal to $\frac{2^{\mathsf{N}}}{\mathsf{N}}$).
+It is \emph{balanced} if for any two bit indices $i$ and $j$,
+$|\textit{TC}_{\mathsf{N}}(i) - \textit{TC}_{\mathsf{N}}(j)| \le 2$.
+
+
+
+\begin{xpl}
+Let $L^*=000,100,101,001,011,111,110,010$ be the Gray code that corresponds to
+the Hamiltonian cycle that has been removed in $f^*$.
+Its transition sequence is $S=3,1,3,2,3,1,3,2$ and its transition count function is
+$\textit{TC}_3(1)= \textit{TC}_3(2)=2$ and $\textit{TC}_3(3)=4$. Such a Gray code is balanced.
+
+Let now
+$L^4=0000, 0010, 0110, 1110, 1111, 0111, 0011, 0001, 0101,$
+$0100, 1100, 1101, 1001, 1011, 1010, 1000$
+be a cyclic Gray code. Since $S=2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4$ $\textit{TC}_4$ is equal to 4 everywhere, this code
+is thus totally balanced.
+
+On the contrary, for the standard $4$-bits Gray code
+$L^{\textit{st}}=0000,0001,0011,0010,0110,0111,0101,0100,1100,$
+$1101,1111,1110,1010,1011,1001,1000$,
+we have $\textit{TC}_4(1)=8$ $\textit{TC}_4(2)=4$ $\textit{TC}_4(3)=\textit{TC}_4(4)=2$ and
+the code is neither balanced nor totally balanced.
+\end{xpl}
+
+
+\begin{thrm}\label{prop:balanced}
+Let $\mathsf{N}$ in $\Nats$, and $a_{\mathsf{N}}$ be defined by
+$a_{\mathsf{N}}= 2 \lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \rfloor$.
+There exists then a sequence $l$ in
+step~(\ref{item:nondet}) of the \emph{Robinson-Cohn extension} algorithm
+such that all the transition counts $\textit{TC}_{\mathsf{N}}(i)$
+are $a_{\mathsf{N}}$ or $a_{\mathsf{N}}+2$
+for any $i$, $1 \le i \le \mathsf{N}$.
+\end{thrm}
+
+
+
+
+
+The proof is done by induction on $\mathsf{N}$. Let us imadialty verify
+that it is established for both odd and even smallest values, \textit{i.e.}
+$3$ and $4$.
+For the initial case where $\mathsf{N}=3$, \textit{i.e.} $\mathsf{N-2}=1$ we successively have: $S_1=1,1$, $l=2$, $u_0 = \emptyset$, and $v=\emptyset$.
+Thus again the algorithm successively produces
+$U= 1,2,1$, $V = 3$, $W= 2, 1, 1,3$, and $W' = 1,2,1,3$.
+Finally, $S_3$ is $1,2,1,3,1,2,1,3$ which obviously verifies the theorem.
+ For the initial case where $\mathsf{N}=4$, \textit{i.e.} $\mathsf{N-2}=2$
+we successively have: $S_1=1,2,1,2$, $l=4$,
+$u_0,u_1,u_2 = \emptyset,\emptyset,\emptyset$, and $v=\emptyset$.
+Thus again the algorithm successively produces
+$U= 1,3,2,3,4,1,4,3,2$, $V = 4$, $W= 3, 1, 2, 1,2, 4$, and $W' = 1, 3, 2, 1,2, 4 $.
+Finally, $S_4$ is
+$
+2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4
+$
+such that $\textit{TC}_4(i) = 4$ and the theorem is established for
+odd and even initial values.
+
+
+For the inductive case, let us first define some variables.
+Let $c_{\mathsf{N}}$ (resp. $d_{\mathsf{N}}$) be the number of elements
+whose transistion count is exactly $a_{\mathsf{N}}$ (resp $a_{\mathsf{N}} +2$).
+These two variables are defined by the system
+
+$$
+\left\{
+\begin{array}{lcl}
+c_{\mathsf{N}} + d_{\mathsf{N}} & = & \mathsf{N} \\
+c_{\mathsf{N}}a_{\mathsf{N}} + d_{\mathsf{N}}(a_{\mathsf{N}}+2) & = & 2^{\mathsf{N}}
+\end{array}
+\right.
+\qquad
+\Leftrightarrow
+\qquad
+\left\{
+\begin{array}{lcl}
+d_{\mathsf{N}} & = & \dfrac{2^{\mathsf{N} -n.a_{\mathsf{N}}}{2} \\
+c_{\mathsf{N}} = \mathsf{N} - d_{\mathsf{N}}
+\end{array}
+\right.
+$$
+
+Since $a_{\mathsf{N}$ is even, $d_{\mathsf{N}}$ is defined.
+Both $c_{\mathsf{N}}$ and $d_{\mathsf{N}}$ are obviously positves.
+
+
+
+
+
+
+\subsection{Toward a local uniform distribution of switches}
