Many approaches have been developed to solve the problem of building
-a Gray code in a $\mathsf{N}$ cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04,Bykov2016}, 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{DBLP:journals/combinatorics/BhatS96,ZanSup04} focus on
balanced Gray codes. In the transition sequence of these codes,
The current context is to provide a function
$f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ by removing a Hamiltonian
-cycle in the $\mathsf{N}$ cube. Such a function is going to be iterated
+cycle in the $\mathsf{N}$-cube. Such a function is going to be iterated
$b$ times to produce a pseudo random number,
\textit{i.e.} a vertex in the
-$\mathsf{N}$ cube.
+$\mathsf{N}$-cube.
Obviously, the number of iterations $b$ has to be sufficiently large
to provide a uniform output distribution.
-To reduce the number of iterations, the provided Gray code
-should ideally possess the both balanced and locally balanced properties.
+To reduce the number of iterations, it can be claimed
+that the provided Gray code
+should ideally possess both balanced and locally balanced properties.
However, none of the two algorithms is compatible with the second one:
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}
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
+exists a Gray code such that all transition count numbers
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
\end{enumerate}
It has been proven in~\cite{ZanSup04} that
-$S_{\mathsf{N}}$ is transition sequence of a cyclic $\mathsf{N}$-bits Gray code
+$S_{\mathsf{N}}$ is the 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
\begin{xpl}
-Let $L^*=000,100,101,001,011,111,110,010$ be the Gray code that corresponds to
+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,$
+$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
+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
\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$.
+$a_{\mathsf{N}}= 2 \left\lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \right\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)$
whose transition 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}} -\mathsf{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 an integer.
Let us first proove that both $c_{\mathsf{N}}$ and $d_{\mathsf{N}}$ are positive
We thus have
-$$
+\[
\begin{array}{rcl}
\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i)
&\ge&
\frac{2^{\mathsf{N}}-2N}{\mathsf{N}}
-2 \left( \frac{2^{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\
&\ge&
-\dfrac{(\mathsf{N} -2).2^{\mathsf{N}}-2N.2^{\mathsf{N-2}}-6N(N-2)}{\mathsf{N.(N-2)}}\\
+\frac{(\mathsf{N} -2).2^{\mathsf{N}}-2N.2^{\mathsf{N-2}}-6N(N-2)}{\mathsf{N.(N-2)}}\\
\end{array}
-$$
+\]
A simple variation study of the function $t:\R \rightarrow \R$ such that
$x \mapsto t(x) = (x -2).2^{x}-2x.2^{x-2}-6x(x-2)$ shows that
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: "main"
+%%% ispell-dictionary: "american"
+%%% mode: flyspell
+%%% End:
