resolution conflit

[16dcc.git] / hamilton.tex

diff --git a/hamilton.tex b/hamilton.tex
index 5764995e4960a5a40fb38253ae9016511cc4bb88..17d93803a0d523ddadc31cfe930449bc6a996f41 100644 (file)
--- a/hamilton.tex
+++ b/hamilton.tex
@@ -17,11 +17,12 @@ and an algorithm that establishes locally balanced Gray codes is given.
 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
 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

-$b$ time to produce a pseudo random number, \textit{i.e.} a vertex in the 
+$b$ times to produce a pseudo random number,
+\textit{i.e.} a vertex in the 

 $\mathsf{N}$ cube.
 Obviously, the number of iterations $b$ has to be sufficiently large 
 to provide a uniform output distribution.
 $\mathsf{N}$ cube.
 Obviously, the number of iterations $b$ has to be sufficiently large 
 to provide a uniform output distribution.

-To reduced the number of iterations, the provided Gray code
+To reduce the number of iterations, the provided Gray code

 should ideally possess the 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,
 should ideally possess the 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,


@@ -35,16 +36,16 @@ 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}, 
 \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
+and~\cite{ZanSup04} have addressed the problem 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}
 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.
+where the authors have explicitly shown how to construct such a subsequence.

 Finally the authors of~\cite{ZanSup04} have presented 
 the \emph{Robinson-Cohn extension} 
 Finally the authors of~\cite{ZanSup04} have presented 
 the \emph{Robinson-Cohn extension} 

-algorithm. There rigourous presentation of this one 
+algorithm. There rigorous 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.
 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.


@@ -67,16 +68,16 @@ which produces a $n$-bits Gray code.
 $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 
 $$
 $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
+s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, \dots , 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).
 $$
 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}$ 
+\item\label{item:u'}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$.
   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 
+\item\label{item:VW} 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} 
 two elements have been exchanged.
 \item The transition sequence $S_{\mathsf{N}}$ is thus the concatenation $U^R, V, W'$.
 \end{enumerate} 


@@ -87,10 +88,10 @@ 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.
 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.
+Next section shows how to choose the sequence $l$ to have the balance property.

 
 \subsection{Balanced Codes}
 
 \subsection{Balanced Codes}

-Let us first recall how to formalize the balancy property of a Gray code.
+Let us first recall how to formalize the balance 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 
 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 


@@ -131,7 +132,7 @@ the code is neither balanced nor totally balanced.
 
 
 \begin{thrm}\label{prop:balanced}
 
 
 \begin{thrm}\label{prop:balanced}

-Let $\mathsf{N}$ in $\Nats$, and $a_{\mathsf{N}}$ be defined by
+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
 $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


@@ -144,7 +145,7 @@ for any $i$, $1 \le i \le \mathsf{N}$.
 
 
 
 
 
 

-The proof is done by induction on $\mathsf{N}$. Let us imadialty verify 
+The proof is done by induction on $\mathsf{N}$. Let us immediately 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$.
 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$.


@@ -166,7 +167,7 @@ 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 
 
 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$).
+whose transition count is exactly $a_{\mathsf{N}}$ (resp $a_{\mathsf{N}} +2$).

 These two variables are defined by the system 
  
 $$
 These two variables are defined by the system 
  
 $$


@@ -181,18 +182,149 @@ c_{\mathsf{N}}a_{\mathsf{N}} + d_{\mathsf{N}}(a_{\mathsf{N}}+2) & = & 2^{\mathsf
 \qquad 
 \left\{
 \begin{array}{lcl}
 \qquad 
 \left\{
 \begin{array}{lcl}

-d_{\mathsf{N}} & = & \dfrac{2^{\mathsf{N}} -n.a_{\mathsf{N}}}{2} \\
+d_{\mathsf{N}} & = & \dfrac{2^{\mathsf{N}} -\mathsf{N}.a_{\mathsf{N}}}{2} \\

 c_{\mathsf{N}} &= &\mathsf{N} -  d_{\mathsf{N}}
 \end{array}
 \right.
 $$
 
 c_{\mathsf{N}} &= &\mathsf{N} -  d_{\mathsf{N}}
 \end{array}
 \right.
 $$
 

-Since $a_{\mathsf{N}$ is even, $d_{\mathsf{N}}$ is defined.
-Moreover, both $c_{\mathsf{N}}$ and  $d_{\mathsf{N}}$ are obviously positves.
+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
+integers.
+Let $q_{\mathsf{N}}$ and $r_{\mathsf{N}}$, respectively, be  
+the quotient and the remainder in the Euclidean disvision
+of $2^{\mathsf{N}}$ by $2\mathsf{N}$, \textit{i.e.} 
+$2^{\mathsf{N}} = q_{\mathsf{N}}.2\mathsf{N} + r_{\mathsf{N}}$, with $0 \le r_{\mathsf{N}} <2\mathsf{N}$.
+First of all, the integer $r$ is even since $r_{\mathsf{N}} = 2^{\mathsf{N}} - q_{\mathsf{N}}.2\mathsf{N}= 2(2^{\mathsf{N}-1} - q_{\mathsf{N}}.\mathsf{N})$. 
+Next,  $a_{\mathsf{N}}$ is $\frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}}$. Consequently 
+$d_{\mathsf{N}}$ is $r_{\mathsf{N}}/2$ and is thus a positive integer s.t. 
+$0 \le d_{\mathsf{N}} <\mathsf{N}$.
+The proof for $c_{\mathsf{N}}$ is obvious.

 
 
 
 

+For any $i$, $1 \le i \le \mathsf{N}$, let $zi_{\mathsf{N}}$ (resp. $ti_{\mathsf{N}}$ and $bi_{\mathsf{N}}$) 
+be the occurence number of element $i$ in the sequence $u_0, \dots, u_{l-2}$ 
+(resp. in the sequences $s_{i_1}, \dots , s_{i_l}$ and $v$)
+in step (\ref{item:nondet}) of the algorithm.
+
+Due to the definition of $u'$ in step~(\ref{item:u'}), 
+$3.zi_{\mathsf{N}} + ti_{\mathsf{N}}$ is the
+ number of element $i$ in the sequence $U$.
+It is clear that the number of element $i$ in the sequence $V$ is 
+$2bi_{\mathsf{N}}$ due to step (\ref{item:VW}). 
+We thus have the following system:
+$$
+\left\{
+\begin{array}{lcl}
+3.zi_{\mathsf{N}} + ti_{\mathsf{N}} + 2.bi_{\mathsf{N}} + \textit{TC}_{\mathsf{N}-2}(i) &= &\textit{TC}_{\mathsf{N}}(i) \\
+zi_{\mathsf{N}} + ti_{\mathsf{N}}  + bi_{\mathsf{N}} & =& \textit{TC}_{\mathsf{N}-2}(i)
+\end{array}
+\right.
+\qquad 
+\Leftrightarrow 
+$$
+
+\begin{equation}
+\left\{
+\begin{array}{lcl}
+zi_{\mathsf{N}} &= & 
+\dfrac{\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) - bi_{\mathsf{N}}}{2}\\
+ti_{\mathsf{N}} &= & \textit{TC}_{\mathsf{N}-2}(i)-zi_{\mathsf{N}}-bi_{\mathsf{N}}
+\end{array}
+\right.
+\label{eq:sys:zt1}
+\end{equation}
+
+In this set of 2 equations with 3 unknown variables, let $b_i$ be set with 0.
+In this case, since $\textit{TC}_{\mathsf{N}}$ is even (equal to $a_{\mathsf{N}}$ 
+or to $a_{\mathsf{N}}+2$), the variable  $zi_{\mathsf{N}}$ is thus an integer.
+Let us now prove that the resulting system has always positive integer 
+solutions $z_i$, $t_i$, $0 \le z_i, t_i \le \textit{TC}_{\mathsf{N}-2}(i)$ 
+and s.t. their sum is equal to $\textit{TC}_{\mathsf{N}-2}(i)$. 
+This latter consraint is obviously established if the system has a solution.
+We thus have the following system.
+
+
+
+\begin{equation}
+\left\{
+\begin{array}{lcl}
+zi_{\mathsf{N}} &= & 
+\dfrac{\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) }{2}\\
+ti_{\mathsf{N}} &= & \textit{TC}_{\mathsf{N}-2}(i)-zi_{\mathsf{N}}
+\end{array}
+\right.
+\label{eq:sys:zt2}
+\end{equation}
+
+The definition of $\textit{TC}_{\mathsf{N}}(i)$ depends on the value of $\mathsf{N}$.
+When $3 \le N \le 7$, values are defined as follows:
+\begin{eqnarray*}
+\textit{TC}_{3} & = & [2,2,4] \\
+\textit{TC}_{5} & = & [6,6,8,6,6] \\
+\textit{TC}_{7} & = & [18,18,20,18,18,18,18] \\
+\\
+\textit{TC}_{4} & = & [4,4,4,4] \\
+\textit{TC}_{6} & = & [10,10,10,10,12,12] \\
+\end{eqnarray*}
+It is not hard to verify that all these instanciations verify the aformentioned contraints. 
+
+When  $N  \ge 8$, $\textit{TC}_{\mathsf{N}}(i)$ is defined as follows:
+\begin{equation}
+\textit{TC}_{\mathsf{N}}(i) = \left\{
+\begin{array}{l} 
+a_{\mathsf{N}} \textrm{ if } 1 \le i \le c_{\mathsf{N}} \\
+a_{\mathsf{N}}+2 \textrm{ if } c_{\mathsf{N}} +1 \le i \le c_{\mathsf{N}} + d_{\mathsf{N}} 
+\end{array}
+\right.
+\label{eq:TCN:def}
+\end{equation}
+
+
+We thus  have
+$$
+\begin{array}{rcl} 
+\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) 
+&\ge& 
+a_{\mathsf{N}} - 2(a_{\mathsf{N}-2}+2) \\
+&\ge& 
+\frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}}
+-2 \left( \frac{2^{\mathsf{N-2}}-r_{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\
+&\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)}}\\
+\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 
+its derivative is strictly postive if $x \ge 6$ and $t(8)=224$.
+The integer $\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i)$ is thus positive 
+for any $\mathsf{N} \ge 8$ and the proof is established.
+
+
+% \begin{table}[ht]
+% $$
+% \begin{array}{|l|l|l|l|l|l|}
+% \hline
+% \mathsf{N}     & 3 & 4 & 5 & 6  & 7\\
+% \hline
+% a_{\mathsf{N}} & 2 & 4 & 6 & 10 & 18\\
+% \hline
+% \end{array}
+% $$
+% \label{tab:an}
+% \caption{First values of  $a_{\mathsf{N}}$}
+% \end{table}
+
+For each element $i$, we are then left to choose $zi_{\mathsf{N}}$ positions 
+among $\textit{TC}_{\mathsf{N}}(i)$, which leads to 
+${\textit{TC}_{\mathsf{N}}(i) \choose zi_{\mathsf{N}} }$ possibilities.
+Notice that all such choices lead to a hamiltonian path.
+

 
 
 
 
 
 
 
 

-\subsection{Toward a local uniform distribution of switches}