X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/blobdiff_plain/7e1869395799899be33ae9c59d7ddf936d3d5907..b67a97afb3770294e649ce1a1ed53af685be00b9:/hamilton.tex

diff --git a/hamilton.tex b/hamilton.tex
index b2c6e54..a48fc62 100644
--- a/hamilton.tex
+++ b/hamilton.tex
@@ -5,9 +5,9 @@ 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.
-This uniformity is a global property on the cycle, \textit{i.e.}
+This uniformity is a global property on the cycle, \textit{i.e.},
 a property that is established while traversing the whole cycle.
-On the opposite side, when the objective is to follow a subpart 
+On the other hand, when the objective is to follow a subpart 
 of the Gray code and to switch each element approximately the 
 same amount of times,
 local properties are wished.
@@ -15,17 +15,17 @@ For instance, the locally balanced property is studied in~\cite{Bykov2016}
 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 
+$f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ by removing an Hamiltonian 
 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 
+$b$ times to produce a pseudorandom 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.
 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:
+However, both algorithms are incompatible 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}
 are not globally balanced.
@@ -40,14 +40,14 @@ namely~\cite{Robinson:1981:CS},~\cite{DBLP:journals/combinatorics/BhatS96},
 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 
+aiming at producing balanced Gray codes, assuming 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 explicitly shown how to construct such a subsequence.
+This work has been strengthened in~\cite{DBLP:journals/combinatorics/BhatS96}
+where the authors have explicitly shown how to build such a subsequence.
 Finally the authors of~\cite{ZanSup04} have presented 
 the \emph{Robinson-Cohn extension} 
-algorithm. There rigorous presentation of this one 
-have mainly allowed them to prove two properties.
+algorithm. Their rigorous presentation of this algorithm
+has 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 
@@ -55,14 +55,14 @@ 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 
-(totally balanced) Gray code. 
+(totally balanced) Gray codes. 
 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.
+which produces a $\mathsf{N}$-bits Gray code.
 
 \begin{enumerate}
 \item \label{item:nondet}Let $l$ be an even positive integer. Find 
@@ -86,10 +86,10 @@ two elements have been exchanged.
 It has been proven in~\cite{ZanSup04} that 
 $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 
+However, step~(\ref{item:nondet}) is not a constructive 
+step that precises how to select the subsequences which ensure that 
 yielded Gray code is balanced.
-Next section shows how to choose the sequence $l$ to have the balance property.
+Following sections show how to choose the sequence $l$ to have the balance property.
 
 \subsection{Balanced Codes}
 Let us first recall how to formalize the balance property of a Gray code.
@@ -118,15 +118,13 @@ 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
+Let  $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$,
+$L^{\textit{st}}=0000,0001,0011, 
+0010,0110,0111,0101,0100,$ \newline $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}
@@ -147,13 +145,13 @@ for any $i$, $1 \le i \le \mathsf{N}$.
 
 
 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.} 
+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$.
+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$ 
+ 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 
@@ -169,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 
 whose transition count is exactly $a_{\mathsf{N}}$ (resp $a_{\mathsf{N}} +2$).
-These two variables are defined by the system 
+Both of these variables are defined by the system 
  
 \[
 \left\{
@@ -188,11 +186,11 @@ c_{\mathsf{N}} &= &\mathsf{N} -  d_{\mathsf{N}}
 \]
 
 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
+Let us first prove 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.} 
+the quotient and the remainder in the Euclidean division
+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 
@@ -202,7 +200,7 @@ 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}$ 
+be the occurrence 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.
 
@@ -240,7 +238,7 @@ 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.
+This latter constraint is obviously established if the system has a solution.
 We thus have the following system.
 
 
@@ -266,7 +264,7 @@ When $3 \le N \le 7$, values are defined as follows:
 \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. 
+It is not difficult to check that all these instanciations verify the aforementioned constraints. 
 
 When  $N  \ge 8$, $\textit{TC}_{\mathsf{N}}(i)$ is defined as follows:
 \begin{equation}
@@ -299,7 +297,7 @@ a_{\mathsf{N}} - 2(a_{\mathsf{N}-2}+2) \\
 
 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$.
+its derivative is strictly positive 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.
 
@@ -321,7 +319,7 @@ for any $\mathsf{N} \ge 8$ and the proof is established.
 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.
+Notice that all such choices lead to an Hamiltonian path.