\documentclass{amsart}
\usepackage{amssymb,amsfonts,latexsym,amsmath}

\begin{document}

\title{Chapter 4 Threshold functions  and transformations}

\begin{abstract} The first two sections describe basic
properties and combinatorial characterization of threshold
functions.  One-to-one threshold transformations of $\{
0,1\} ^{n}$ are self-dual.  A self-dual Boolean
transformation is a threshold transformation if and only if
each of the Boolean functions that represent the
transformation in a [\;]-representation introduced in
Chapter 2.4 is a threshold function. Then in the last two
sections, we construct minimal one-to-one threshold
transformations which are circular or skew-circular.  As a
result, it is found out that each of them is reflective through
some isometries of order 2, so that it is isometrically
equivalent to a threshold transformation such that its graph
consists of 2-cycles and loops, and its inverse is also a
threshold transformation.
\end{abstract} 
\maketitle

\newcommand{\stku}[1]{\stackrel{#1}{\longrightarrow}}
\newcommand{\stkd}[1]{\stackrel{\longrightarrow}{#1}}
\newcommand{\downl}[1]{{#1}\downarrow}
\newcommand{\downr}[1]{\downarrow{#1}}

\section*{4.1 Basic properties of threshold
functions\label{s:BPThF}}
A Boolean function $f: \mathbf{Q}^{n} \rightarrow  \mathbf{Q} =
\{ 0,1\} $ is called a \emph{threshold function}, if the sets $f$
and $\neg f$ are separated by a hyperplane in the real $n$-
dimensional space $\mathbf{R}^{n}$.  In other words, $f$ is a
threshold function, if there exist a real $n$-vector $w =
(w_{1},...,w_{n})$ and a real number $\theta $ such that
$$
    fx = \mathrm{bool}(wx-\theta ),
\eqno (4.1.1) 
$$
where $wx = w_{1}\cdot x_{1}+...+w_{n}\cdot x_{n}$, the inner
product of $w$ and $x$, and 
$$
\mathrm{bool}(u) =  \left\{
       \begin{array}{ll}
           1 & \mbox{if $u > 0$,} \\
           0 & \mbox{if $u \leq  0$.}
       \end{array}    
           \right.
$$
Here $w$ is called the \emph{weight vector} and $\theta $ is
called the \emph{threshold value} of $f$.  Threshold functions
$f$ and $g$ are called \emph{simultaneously realizable}, if both
can be defined with the same weight vector.  A threshold
transformation $F$ of $\mathbf{Q}^{n}$ is a natural
generalization of a threshold function from $\mathbf{Q}^{n}$ to
$\mathbf{Q}$ such that each $p_{i}F$ is a threshold function.

    Since the pioneering work of McCulloch and Pitts (1943), a
great number of theoretical and experimental studies (e.g.
Arimoto, 1963; Amari, 1972;  Goles-Chacc, 1980; Goles \& Olivos,
1981; Hopfield, 1982; Goles, Fogelman-Soulie \& Pellegrin, 1985;
Cottrell, 1988; Blum, 1990; Blessloff \& Taylor, 1991 etc.) have
been made on neural networks.  The information process on neural
networks is mathematically summarized as threshold
transformations.  However, their mathematical properties are yet
to be clarified by rigorous analysis.  In practical models,
important transformations are those whose iterative operations
transform a subset whose points share a certain common pattern
into a smaller set.  Although these transformations are not one-
to-one, we deal with one-to-one transformations in the first
place, hoping the study will help us with general threshold
transformations.  In particular our goal in this chapter is to
investigate simple threshold transformations that are minimal,
one-to-one, and circular.

    Various properties of threshold transformations should
reflect those of a threshold functions.  Therefore, we describe
these properties with or without proof in the first two sections
of this chapter as basic properties and combinatorial
characterizations.  Most of these results were obtained in the
1960s and contained in Hu (1965) and Muroga (1971).  Some of them
are main propositions, and others are minor but used later in
this book.\\

\textbf{Proposition 4.1.1}  Let $f$ be a threshold function:
$\mathbf{Q}^{n} \rightarrow  \mathbf{Q}$.  Then (i) $\neg f$ is a
threshold function, (ii) $\bar{\neg}f$ is a threshold function,
and
(iii) $F$ and $\neg \bar{\neg}f$ are simultaneously realizable.

\begin{proof}  We have a real $n$-vector $w$ and a real number
$\theta $ such that $fx = 1$ iff $wx-\theta  > 0$.  Therefore,
$fx = 0$ that is $(\neg f)x = 1$ iff $wx-\theta \leq  0$, that
is, $-wx+\theta \geq  0$.  Since $\mathbf{Q}^{n}$ is a finite
set, there exists $\eta \geq \theta $ such that $-wx+\theta \geq 
0$ iff $-wx+\eta  > 0$.  Therefore, $(\neg f)x = 1$ iff $(-w)x-
\eta  > 0$, so that $\neg f$ is a threshold function.  (ii) $fx =
1$ iff $wx-\theta  > 0$ implies that $f(\bar{\neg}x) = 1$ iff
$w(\bar{\neg}x)-\theta  > 0$,
that is, $w(l-x)-\theta  > 0$, that is, $(-w)x-
(\theta -wl) > 0$, where $l$ is the $n$-vector such that $l_{i} =
1$ for every $i$.  Therefore, $f\bar{\neg}$ that is,
$\bar{\neg}f$ is a
threshold function.  (iii) is clear from the above proof of (i)
and (ii).
\end{proof}

\textbf{Proposition 4.1.2}  If $f$ is a threshold function:
$\mathbf{Q}^{n} \rightarrow  \mathbf{Q}$ and $p_{j}$ is the
projection function: $\mathbf{Q}^{n} \rightarrow  \mathbf{Q}$,
then $p_{j}\vee f$, $\neg p_{j}\vee f$, $p_{j}\cdot f$, and $\neg
p_{j}\cdot f$ are threshold functions: $\mathbf{Q}^{n}
\rightarrow  \mathbf{Q}$.  

\begin{proof}  Let $f$ be a threshold function.  Then there
exists a real $n$-vector $w$ and a real number $\theta $ such
that $fx = 1$ iff $wx-\theta  > 0$.

    Let $\delta  > n\cdot \mathrm{max}|w_{i}| + |\theta |$, and
let $v_{j} = w_{j}+\delta $, $v_{i} = w_{i}$
for every $i \ne  j$.    Then, if $x_{j} = 1$, then $vx-\theta  =
wx-\theta +\delta  > 0$; if $x_{j} = 0$, then $vx-\theta  = wx-
\theta $.  Therefore, $x_{j} = 1$ or $fx = 1$, if and only if
$vx-\theta  > 0$, so that $p_{j}\vee f$ is a threshold function. 
Further, $\neg p_{j}\cdot f$ = $\neg (p_{j}\vee \neg f)$, so that
$\neg p_{j}\cdot f$ is a threshold function. 

    Let $\eta  = (n-1)\mathrm{max}|w_{i}| - \theta $, and
let $v_{j} = w_{j}+\eta $, $v_{i} = w_{i}$ for every $i \ne  j$,
and $\zeta  = \theta +\eta $.  Then, if $x_{j} = 1$, then $vx-
\zeta  = wx-\theta $; if $x_{j} = 0$, then $vx-\zeta  =
w_{1}x_{1}+..+w_{j-1}x_{j-1}+w_{j+1}x_{j+1} +..+w_{n}x_{n}-\theta
-\eta \leq  (n-1)\mathrm{max}|w_{i}| -\theta -\eta  = 0$.  
Therefore, $x_{j} = 1$ and $fx = 1$, if and only if $vx-\zeta  >
0$, so that $p_{j}\cdot f$ is a threshold function.  Further,
$\neg p_{j}\vee f = \neg (p_{j}\cdot \neg f)$, so that $\neg
p_{j}\vee f$ is a threshold function.
\end{proof}           

\textbf{Proposition 4.1.3}  Let $f$ be a Boolean function:
$\mathbf{Q}^{n} \rightarrow  \mathbf{Q}$ and $p_{n+1}$ be the
projection: $\mathbf{Q}^{\{n+1\}} \rightarrow  \mathbf{Q}$.  If
$f\cdot p_{n+1}$ or $f\vee p_{n+1}$ is a threshold function, then
$f$ is a threshold function. \\

\textbf{Proposition 4.1.4} (Muroga, Toda, \& Takasu, 1961;
Winder,
1962; Muroga,1971,  Theorem 8.1.1.2)  If $f: \mathbf{Q}^{n}
\rightarrow  \mathbf{Q}$ and $g: \mathbf{Q}^{n} \rightarrow 
\mathbf{Q}$ are simultaneously realizable threshold functions,
then $h: \mathbf{Q}^{n+1} \rightarrow  \mathbf{Q}$ defined by $h
= (\neg p_{n+1})\cdot f\vee p_{n+1}\cdot g$  is a threshold
function from $\mathbf{Q}^{n+1}$ to $\mathbf{Q}$.\\

\textbf{Proposition 4.1.5}  If $f$ is a threshold function, then
$fT$ and $Tf$ are threshold functions for any isometry $T$ of
$\mathbf{Q}^{n}$.\\

\textbf{Notation} For a set of Boolean functions or variables
 $\{.\}$, let $S_{m}\{ .\}$ denote the disjunction of all
conjunctions of $m$ elements of $\{ .\}$.  For example, $S_{2}\{
p_{1},p_{2},p_{3}\} = p_{1}\cdot p_{2}\vee p_{1}\cdot p_{3}\vee
p_{2}\cdot p_{3}$.\\

\textbf{Proposition 4.1.6}  If $f$ is a threshold function:
$Q^{n} \rightarrow  Q$,  then
$$
     g = S_{k}\{p_{n+1},..,p_{n+m}\}\vee S_{k-
1}\{p_{n+1},..,p_{n+m}\}\cdot f
$$
is a threshold function: $Q^{n+m} \rightarrow  Q$.  
\begin{proof}  Let $f$ be a threshold function.  Then there
exists a real $n$-vector $w$ and a real number $\theta $ such
that $fx = 1$ iff $wx - \theta  > 0$.
     In order to prove the proposition, it is sufficient to
determine the threshold vector $(w,v)$ such that $v = (\delta
,\delta ,..\delta )$ and a threshold value $\eta $ for $g$.
Then it is sufficient to determine $\delta $ and $\eta $ such
that
\begin{eqnarray*}
(1) &&wx + k\delta  > \eta  \mbox{ for any $x$,}\\  
(2) &&wx + (k-1)\delta  > \eta  \mbox{ iff $wx > \theta $,}\\
(3) &&wx + (k-2)\delta  \leq  \eta  \mbox{ for any $x$.}
\end{eqnarray*}
(2) is equivalent to $wx + (k-1)\delta  + \theta  > \theta  +
\eta $ iff $wx > \theta $.  Therefore, let
$$
      (k-1)\delta  + \theta  = \eta .
\eqno (4.1.2)
$$
Then (2) is satisfied. By substituting (4.1.2) for $\eta $ in (1)
and (3), we obtain $\mathrm{min}(wx) + k\delta  > (k-1)\delta  +
\theta $, i.e.
$$
     \delta  > -\mathrm{min}(wx) + \theta ,
\eqno (4.1.3)
$$
and $\mathrm{max}(wx) + (k-2)\delta  \leq  (k-1)\delta  + \theta
$,
i.e.
$$
     \delta  \geq  \mathrm{max}(wx) - \theta .
\eqno (4.1.4)
$$
Therefore, let
$$
     \delta  > \mathrm{max}(\sum_{i}|w_{i}|+\theta ,
\sum_{i}|w_{i}|-\theta ).
\eqno (4.1.5)
$$
Then (4.1.3) and (4.1.4) are satisfied. Thus we determined
desired $\delta $ and $\eta $ by (4.1.5) and (4.1.2).
\end{proof}
    
\textbf{Proposition 4.1.7}  If $f$ is a threshold function:
$\mathbf{Q}^{N} \rightarrow  \mathbf{Q}$, $\mathbf{M}$ is a
proper subset of $\mathbf{N}$, and $a$ is an element of $Q^{M}$,
then $f|a$ is a threshold function: $\mathbf{Q}^{N\backslash
M} \rightarrow  \mathbf{Q}$.  
\begin{proof}  Let $f$ be a threshold function.  Then there
exists a real $n$-vector $w$ and a real number $\theta $ such
that $fx = 1$ iff $wx - \theta  > 0$.  Therefore, $(f|a)x =
f(a,x) = 1$ iff $(P_{M}w)a + (P_{N\backslash M}w)x - \theta  >
0$, i.e.
$$
          (P_{N\backslash M}w)x - (\theta +(P_{M}w)a) > 0. 
$$
Therefore, $f|a$ is a threshold function with the weight
vector $P_{N\backslash M}w$ and the threshold value $\theta
+(P_{M}
w)a$.
\end{proof}

\section*{4.2 Combinatorial properties\label{s:CP}}
A Boolean function $f$ is called $m$-summable, if there exist
$a^{(1)},...,a^{(k)}$ and $b^{(1)},...,b^{(k)}$ such that $2 \leq 
k \leq  m$, and $a^{(i)} \in f$, $b^{(i)} \in \neg f$ for every
$i$ such that $1 \leq  i \leq  k$, $a^{(i)} \in  f^{(i)} \in \neg
f$, for every $i$ such that $1 \leq  i \leq  k$, and
$$
        \sum_{i=1}^k a^{(i)} = \sum_{i=1}^k b^{(i)},
$$
where the sums are performed in $\mathbf{R}^{n}$.  If $f$ is not
$m$-\emph{summable}, $f$ is called $m$-\emph{asummable}.  If $f$
is $m$-summable for some $m$, $f$ is called $summable$.  If $f$
is not summable, $f$ is called \emph{asummable}.  The following
proposition characterizes threshold functions in place of linear
separability of $f$ expressed by (4.1.1).\\

\textbf{Proposition 4.2.1} (Elgot 1961; Chow 1961)  A Boolean
function $f$ is a threshold function if and only if $f$ is
asummable.

\begin{proof}  In the definition of threshold functions in 
Section 1, the condition that $f$ and $\neg f$ are separated by a
hyperplane in the real $n$-space $\mathbf{R}^{n}$ can be replaced
with the fact that $f$ and $\neg f$ are separated by a hyperplane
in the rational $n$-space.  Further, the latter condition is
equivalent to the fact that the convex hull of $f$ and the convex
hull of $\neg f$ are disjoint.  The last condition is equivalent
to the fact that $f$ is asummable.
\end{proof}

\textbf{Corollary 4.2.2}  If a Boolean function $f$ is a
threshold function, then $f$ is 2-asummable.\\

Attempts to characterize a threshold function combinatorially in
place of linear separability had been made to replace the linear
separability conditions (4.1.1), which is described in terms of
the weight vector and the threshold value.  Unfortunately, there
is no such combinatorial expression that describes a necessary
and sufficient condition for a Boolean function to be a threshold
function.  For example, the asummability condition described by
Proposition 4.2.1 involves an unlimited number of equations. 
Therefore, only some necessary conditions for threshold functions
are available.  We describe here some of these  necessary but not
sufficient conditions in the following because of their own
value, but we use only Corollaries 4.2.2 and  4.2.4 in this book. 
 
   Let $f$ be a Boolean function defined on $\mathbf{Q}^{n}$. 
If
$$
        f|q \subseteq  f|\bar{\neg}q \; \mbox{or}\;  
f|\bar{\neg}q \subseteq f|q   
$$
for every $q \in \mathbf{Q}^{M}$ for every $M \subseteq
\mathbf{N}$ such that $|M| \leq  k$, then $f$ is called $k$-
\emph{monotonic}.  In particular, $f$ is called \emph{unate} if
$k = 1$, and $f$ is called \emph{completely monotonic} if $k =
n$.  The following theorem due to Elgot (1961) gives a condition
equivalent to 2-asummability.  The proof is also found in Muroga
(1971, Chapter 3).\\

\textbf{Theorem 4.2.3} (Elgot, 1961)  A Boolean function of
$\mathbf{Q}^{n}$ is 2-asummable if and only if it is completely
monotonic.

\begin{proof}  Assume that $f$ is 2-summable.  By definition,
there exists $x, y \in  f$ and $u, v \in \neg f$ such that $x+y =
u+v$.  Then $x_{i} = y_{i} = u_{i} = v_{i}$ if and only if
$(x+y)_{i}$ is 0 or 1.  Let $K = \{ i \mid  x_{i} = y_{i} = u_{i}
= v_{i}\}$, $L = \{ i \mid  i \notin  K \; \mbox{and}\; x_{i} =
u_{i}\}$, and $M = \{ i \mid  i \notin  K \; \mbox{and}\; x_{i}
\ne  u_{i}\}$.  Then $\mathbf{N}$ is the union mutually disjoint
$K$, $L$, and $M$.  Further, neither $L$ nor $M$ is empty,
since $x$ is either $u$ or $v$ otherwise,
contrary to the fact $x \in  f$ and $u, v \in \neg f$.  Let
$P_{K}x = a$, $P_{L}x = b$, and $P_{M}x = c$.  Then, $x =
(a,b,c)$, $y = (a,\bar{\neg}b,\bar{\neg}c)$,
$u = (a,b,\bar{\neg}c)$, $z = (a,\bar{\neg}b,c)$.
Considering $x$ and $v$, $(a,c) \in f|b$ and
$(a,c) \in \neg f|\bar{\neg}b = \neg (f|\bar{\neg}b)$, so
that $f|b \subseteq  f|\bar{\neg}b$ does not hold. 
Considering $y$ and $u$, $(a,\bar{\neg}c) \in  f|\bar{\neg}b$
and $(a,\bar{\neg}c) \in \neg
f|b = \neg (f|b)$, so that $f|\bar{\neg}b \subseteq 
f|b$.  Therefore, f is not completely monotonic.

    Conversely, assume that $f$ is not completely monotonic.  By
definition, there exists a such that neither $f|a \subseteq 
f|\bar{\neg}a$ nor $f|\bar{\neg}a \subseteq f|a$. 
Therefore, there exist $b$ and $c$ such that $(b,a) \in  f$,
$(b,\bar{\neg}a) \in \neg f$, $(c,\bar{\neg}a) \in  f$, and
$(c,a) \in \neg f$.  Since $(b,a)+(c,\bar{\neg}a) =
(b,\bar{\neg}a)+(c,a)$, $f$ is 2-summable. 
\end{proof}               

\textbf{Corollary 4.2.4} (Muroga, Toda, \& Takasu, 1960)  If $f$
is a threshold function defined on $\mathbf{Q}^{n}$ and $k \in 
\mathbf{N}$, then either $f|0$ or $f|1$ is a subset of the other,
and both are threshold functions, where $0,1 \in
\mathbf{Q}^{{k}}$.\\

Another combinatorial condition for 2-asummability was given by
Yajima and Ibaraki in terms of prime implicants of the Boolean
function:\\

\textbf{Theorem 4.2.5} (Yajima \& Ibaraki, 1968)  A Boolean
function $f$ is 2-asummable, if and only if (i) $f$ is unate and
(ii) if $u_{1}\cdot u_{2}\cdot w$ and $v_{1}\cdot v_{2}\cdot w$
are any prime implicants of $f$, where terms $u_{1}\cdot u_{2}$
and $v_{1}\cdot v_{2}$ contain no common projection $p_{i}$,
then there exists a prime $implicant$ $z$ of $f$ such that $z
\subseteq  u_{1}\cdot v_{1}\cdot w$ or $z \subseteq  u_{2}\cdot
v_{2}\cdot w$.\\

\textbf{Proposition 4.2.6}  If a point $q$ and $\neg q$ belong to
a
threshold function $f$ from $\mathbf{Q}^{n}$ to $\mathbf{Q}$,
then $|f| \geq  2^{n-1}+1$.

\begin{proof}  If both $q$ and $\bar{\neg}q$ belong to $f$, then
the
2-asummability condition for $f$ requires that for any $r \in 
\mathbf{Q}^{n}$, either $r$ or $\bar{\neg}r$ or both belong to
$f$. 
\end{proof}

The following Theorem (Ueda, 1977, 1979) gives a necessary
condition for a Boolean function to be a threshold function in
terms of the stabilizer of $f$.  Let $f$ be a Boolean function
from $\mathbf{Q}^{n}$ to $\mathbf{Q}$.  Let $i$ and $j$ be
elements of $\mathbf{N}$.  We define the binary relation $\succeq
_{f}$ by 
$$
        i \succeq _{f} j \; \mbox{if}\;  i = j \; \mbox{or}\; 
f|10 \supseteq  f|01,
$$
where 10 and 01 are elements of $\mathbf{Q}^{\{i,j\}}$.
Further, we define
$$
        i \sim _{f} j \; \mbox{if}\;  i \succeq _{f} j \;
\mbox{and}\;  j \succeq _{f} i.    
$$

\textbf{Proposition 4.2.7} (Winder, 1962; Muroga, Toda, \&
Takasu,
1961)  The binary relation $\succeq _{f}$ is a preorder, i.e.
reflective and transitive, and hence the binary relation $\sim
_{f}$ is an equivalence relation on $\mathbf{N}$.\\

\textbf{Theorem 4.2.8} (Ueda, 1977, 1979)  Let $f$ be 2-monotonic
Boolean function defined on $\mathbf{Q}^{n}$.  Then $\mathbf{N}$
is partitioned into sets $M_{1},...,M_{k}$ for some $k$ such that
the stabilizer of $f$ is the direct product of the $k$ symmetric
groups $\mathrm{SYM}(M_{1}),..,\mathrm{SYM}(M_{k})$.

\begin{proof}  Let a permutation $\sigma \in 
\mathrm{SYM}(\mathbf{N})$ be
an element of the stabilizer of $f$.  Let $\sigma $ be expressed
by the disjoint composition of permutations as $\sigma  = \tau
\odot ..\odot \upsilon \odot ..\odot \omega $.  Let $\tau  =
(s_{1},...,s_{h})$.  Since $f$ is 2-monotonic, the preorder
$\succeq _{f}$ is total, i.e. $i \succeq _{f} j$ or $j \succeq
_{f} i$ for every pair $i,j$ of $\mathbf{N}$, and $\sim _{f}$ is
an equivalence relation on $\mathbf{N}$ by Proposition 4.2.7. 
Let the set of all equivalence classes determined by
$\sim _{f}$ be $\{M_{1},...,M_{k}\}$.

    If $s_{1} \succeq _{f} s_{2}$ then $\sigma s_{1} \succeq
_{\sigma f} \sigma s_{2}$, so that $s_{2} \succeq _{f} s_{3}$,
since $\sigma f = f$.  Therefore, $s_{1} \succeq _{f} s_{2}
\succeq _{f} ... \succeq _{f} s_{h} \succeq _{f} s_{1}$, and
hence $s_{1} \sim _{f} s_{2} \sim _{f} ... \sim _{f} s_{h}$. 
Similarly if $s_{2} \succeq _{f} s_{1}$ then $s_{1} \sim _{f}
s_{2} \sim _{f} ... \sim _{f} s_{h}$.  Therefore, all non-fixed
elements on each cycle $\upsilon $ of the disjoint composition
are elements of some equivalence class $M_{j}$.     

      Now let $i \sim _{f} j$, $i \ne  j$.  Then by the
definition of $\sim _{f}$, $f|10 = f|01$.  Therefore,
$(i,j)f = f$ for the interchange $(i,j) \in 
\mathrm{SYM}(\mathbf{N})$. 
Therefore, the stabilizer of $f$ is the direct product of
$\mathrm{SYM}(M_{1}),...,\mathrm{SYM}(M_{k})$.
\end{proof}

\section*{4.3 Basic properties of transformations\label{s:BPT}}
A Boolean transformation $F$ of $\mathbf{Q}^{n}$ is called a
threshold transformation, if $F_{i} = p_{i}F$ is a threshold
function for every $i$.  That is, there exists an $n\times n$
real matrix $W$ and real column $n$-vector $h$ such that 
$$
        Fx = \mathrm{Bool}(Wx - h),
\eqno (4.3.1) 
$$
where
$$
(\mathrm{Bool}(x))_{i} =  \left\{
        \begin{array}{ll}
           1 & \mbox{if $x_{i} > 0$,} \\
         0 & \mbox{if $x_{i} \leq  0$},
        \end{array}    
            \right.
$$
for every $i$.  Here $W$ is called the \emph{weight matrix} and
$h$ is called the \emph{threshold vector} of $F$.
    Now, we consider the set $\{ -1,1\} $ in place of $\mathbf{Q}
= \{ 0,1\} $.  As described in Chapter 2.1, a transformation $F$
of $\mathbf{Q}^{n}$ and a transformation $G$ of $\{ -1,1\} ^{n}$
is equivalent, if $G = \mathrm{Bool}^{-1}\circ F\circ
\mathrm{Bool}$ or $F =
\mathrm{Sgn}^{-
1}\circ G\circ \mathrm{Sgn}$, where
$$
(\mathrm{Sgn}(y))_{i} =  \left\{
      \begin{array}{ll}
           1 & \mbox{if $y_{i} > 0$,} \\
        -1 & \mbox{if $y_{i} \leq  0$},
       \end{array} 
            \right.
$$
that is, the following diagram is commutative.
$$
\begin{array}{ccc}
       \mathbf{Q}^{n} &   \stku{F}&   \mathbf{Q}^{n} \\
    \downl{\mathrm{Sgn}}&      & \downr{\mathrm{Sgn}} \\        
        \{ -1,1\} ^{n} & \stkd{G} & \{ -1,1\} ^{n}.
\end{array}
$$
If $\mathrm{Bool}$ and $\mathrm{Sgn}$ are respectively restricted
to $\{ -1,1\}
^{n}$ and $\mathbf{Q}^{n}$, then
$$
    \mathrm{Bool}(x) = (1/2)(x+l) \; \mbox{and}\; 
\mathrm{Sgn}(y)  = 2y-l,
$$
where $l$ is the column $n$-vector whose every coordinate is 1. 
Therefore, if $F$ is a threshold transformation defined by
(4.3.1),
then
\begin{eqnarray*}
    Gy &=& \mathrm{Sgn}(\mathrm{Bool}(W(1/2(y+l))-h)) \\
       &=& \mathrm{Sgn}(W(1/2(y+l))-h)\\
       &=& \mathrm{Sgn}(Wy-(2h-Wl)).
\end{eqnarray*}
Generally, $H$ is said to be a \emph{threshold transformation} of
$\{ -1,1\} ^{n}$ if there is a real                               
   
$n\times n$ matrix $V$ and a real $n$-vector $r$ such that
$$
         Hy = \mathrm{Sgn}(Vy-r).
\eqno (4.3.2) 
$$
Here $V$ is called the \emph{weight matrix} and $s$ is called the
\emph{threshold vector} of $H$.  Thus we showed that, in the
above commutative diagram, if $F$ is a threshold transformation,
then $G$ is a threshold transformation defined with the same
weight matrix $W$.  Conversely, let $H$ be defined by (4.3.2). 
Then the corresponding equivalent transformation $J$ is
\begin{eqnarray*}
        Jx &=& \mathrm{Bool}(\mathrm{Sgn}(V(2x-l)-r))\\
           &=& \mathrm{Bool}(\mathrm{Sgn}(Vx-(1/2)(Vl+r)))\\
           &=& \mathrm{Bool}(Vx-(1/2)(Vl+r)).
\end{eqnarray*}
Therefore $J$ is a threshold transformation defined by the same
weight matrix $V$.  An advantage of using $\{ -1,1\} ^{n}$ for
threshold functions and transformations in place of
$\mathbf{Q}^{n}$ is apparent in the following propositions and
theorem.\\

\textbf{Proposition 4.3.1}  Let $H$ be a threshold transformation
of $\{ -
1,1\} ^{n}$ defined by (4.3.2).  If the threshold vector $r$ is
the zero vector, and if there is no point $y$ in $\{ -1,1\} ^{n}$
such that $(Vy)_{i} = 0$ for some $i$, then $H$ is self-dual. 
Conversely, if $H$ is self-dual, then $Hy = \mathrm{Sgn}(Vy)$,
and there is no point of $\{ -1,1\} ^{n}$ such that $(Vy)_{i} =
0$ for some $i$.
\begin{proof}  Let $Hy = \mathrm{Sgn}(Vy)$ for every $y$.  Then
$(H-)y = H(-y) = \mathrm{Sgn}(V(-y)) = \mathrm{Sgn}(-(Vy))$ for
every $y$.  If there is no point $y$ of $\{ -1,1\} ^{n}$ such
that $(Vy)_{i} = 0$ for some, then $\mathrm{Sgn}(-(Vy)) = -
\mathrm{Sgn}(Vy) = -Hy$, so that $H- = -H$, that is $H$ is
self-dual.

Conversely, let $H$ be self-dual and $Hy =
\mathrm{Sgn}(Vy-r)$ for every $y$.  Then by slightly changing
$r$, we can obtain $r\prime $ such that $Hy = \mathrm{Sgn}(Vy-
r\prime )$ and there is no point $y$ such that $(Vy-r\prime )_{i}
= 0$ for some $i$.  Then, $-\mathrm{Sgn}(V(-y)-r\prime ) =
\mathrm{Sgn}(-(V(-y)-r\prime )) = \mathrm{Sgn}(Vy+r\prime )$ and
$-\mathrm{Sgn}(V(-y)-r\prime ) = \mathrm{Sgn}(Vy-r\prime )$, so
that $\mathrm{Sgn}(Vy+r\prime ) = \mathrm{Sgn}(Vy-r\prime )$ for
every $y$.  If $r\prime _{i} \ne  0$, then $(Vy)_{i} > |r\prime
_{i}|$ or $(Vy)_{i} < -|r\prime _{i}|$, so
that $\mathrm{Sgn}((Vy)_{i}-r\prime _{i}) =
\mathrm{Sgn}((Vy)_{i})$ and there is no $y$ such that $(Vy)_{i} =
0$.  Therefore, $Hy = \mathrm{Sgn}(Vy)$, and there is no $y$ such
that $(Vy)_{i} = 0$ for some $i$.  \end{proof}

The following Proposition 4.3.2 (i) shows that the set of the
Boolean isometries is a subset of the one-to-one threshold
transformations.  As defined in Chapter 2.2, transformations $F$
and $G$ of $\mathbf{Q}^{n}$ are called \emph{isometrically
equivalent} if there exist isometries $S$ and $T$ of
$\mathbf{Q}^{n}$ such that $G = SFT$.  The following Proposition
4.3.2 (ii) shows that if $F$ is a threshold transformation and $G$
is isometrically equivalent to $F$, then $G$ is also a threshold
transformation.  The set of all Boolean isometries is the
subgroup of the transformation group consisting of all one-to-one
self-dual transformations.  The following Theorem 4.3.3 shows 
that the set of the one-to-one threshold transformations is
a subset of the set of the one-to-one self-dual transformations.\\

\textbf{Proposition 4.3.2}  (i) Orthogonal transformations are
threshold transformations.  (ii) If $F$ is a threshold
transformation and $T$ is an orthogonal transformation, then $FT$
and $TF$ are threshold transformations.  (iii) If $F$ is an
threshold transformation, then $F$ is orthogonally equivalent to
a minimal threshold transformation.

\begin{proof} (i) If $T \in  O\{-1,1\} ^{n}$ then there exists an
orthogonal matrix $A$ such that $Ty = Ay = \mathrm{Sgn}(Ay)$ for
every $y$.

(ii) Let $G$ be a threshold transformation of $\{ -1,1\} ^{n}$
defined $Gy = \mathrm{Sgn}(Vy-r)$, and let $T \in  O\{ -1,1\}
^{n}$ defined by $Ty = Ay$, where $V$ and $A$ are $n\times n$
real matrix, and $r$ is a real $n$-vector.  Then
\begin{eqnarray*}
    (GT)y &=& \mathrm{Sgn}(V(Ay)-r) = \mathrm{Sgn}((VA)y-r), \\
    (TG)y &=& A\mathrm{Sgn}(Vy-r) = A\mathrm{Sgn}(Vy-r\prime ),
\end{eqnarray*}
where $r\prime $ is obtained by modifying $r$ so that there is no
point $y \in  \{ -1,1\} ^{n}$ such that $(Vy-r\prime )_{i} = 0$
for some $i$.  Then
$$
    (TG)y = \mathrm{Sgn}(A(Vy-r\prime )) = \mathrm{Sgn}((AV)y-
Ar\prime ).
$$
(iii) is clear from (ii) and the definition of minimal
transformations.
\end{proof} 

\textbf{Theorem 4.3.3} One-to-one threshold transformations are
self-dual.

\begin{proof}  Let $F = (F_{1},...,F_{n})$, where $F_{i} =
p_{i}F$, be a one-to-one threshold transformation of
$\mathbf{Q}^{n}$; then $|\neg F_{i}|  = |F_{i}|$.  Therefore,
if a point $q$ and its complement $\bar{\neg}q$ belong to
$F_{i}$, then another point $r$ and its complement $\bar{\neg}r$
must be in $\neg F_{i}$.  This contradicts the 2-asummability of
$F_{i}$, because $(q+\bar{\neg}q)/2 = (r+\bar{\neg}r)/2$ in
$\mathbf{R}^{n}$.  Therefore, $F_{i}$ is self-dual, so that $F$
is self-dual.
\end{proof}

\textbf{Proposition 4.3.4}  Let a self-dual Boolean function
$F_{i}: \mathbf{Q}^{n} \rightarrow  \mathbf{Q}$ be defined as 
$$
        F_{i} = p_{i}\cdot g_{i}\vee \neg p_{i}\cdot (\neg
\bar{\neg}g_{i}).
$$
for a Boolean function $g_{i}: \mathbf{Q}^{\mathbf{N}\backslash
i} \rightarrow  \mathbf{Q}$.  Then $F_{i}$ is a threshold
function if and only if $g_{i}$ is a threshold function.
\begin{proof}  If $g_{i}$ is a threshold function, then $g_{i}$
and $\neg \bar{\neg}g_{i}$ are simultaneously realizable
threshold functions by Proposition 4.1.1 (iii).  Therefore, $F_{i}$ is also
a threshold function according to Proposition 4.1.4.  If $F_{i}$ is
a threshold function, clearly $g_{i}$ is also a threshold function. 
\end{proof} 

\textbf{Corollary 4.3.5}  A self-dual Boolean transformation $F$
represented as $[f_{1},...,f_{n}]$ is a threshold transformation,
if and only if $f_{i}$ is a threshold function for every $i$.\\

The above corollary implies that $\langle f \rangle $ is a
threshold transformation if and only if $f$ is a threshold
function, and $\langle\langle f\rangle\rangle $ is a threshold
transformation if and only if $f$ is a threshold function. 
Finally, the following two propositions are clear.\\

\textbf{Proposition 4.3.6}  Let $G$ be a threshold transformation
of $\mathbf{Q}^{n+1}$.  If the transformations $H$ and $L$ of
$\mathbf{Q}^{n}$ are defined by $H_{i}(x_{1},...,x_{n}) =
G_{i}(x_{1},...,x_{n},1)$ and $L_{i}(x_{1},...,x_{n}) =
G_{i}(x_{1},...,x_{n},0)$ for $i = 1,..,n$, then $H$ and $L$ are
threshold transformations.
\begin{proof}  There exists a real $(n+1)\times (n+1)$ matrix $E$
and a real $(n+1)$-vector $h$ such that
$$
        Gx = \mathrm{Bool}(Ex-h).
$$
Let $h_{i}\prime  = h_{i}-E_{in+1}$ and $E\prime _{ij} = E_{ij}$
for $1 \leq  i,j \leq  n$.  Then clearly
$$
         Hx = \mathrm{Bool}(E\prime x-h\prime ).
$$
Therefore, $H$ is a threshold transformation.
 \end{proof}

\textbf{Proposition 4.3.7}  Let $L$ and $M$ be disjoint subsets
of $\mathbf{N}$.  If $F$ is a threshold transformation of
$\mathbf{Q}^{L}$, and if $G$ is a threshold transformation of
$\mathbf{Q}^{M}$. Then the direct product of $F$ and $G$ is a
threshold transformation.\\

\begin{proof}  The proof is clear from the definitions of
threshold transformations and the direct product.
\end{proof}

\textbf{Proposition 4.3.8} If $|f_k| \leq 2^{n-2}$ for $F =
[f_{1},...,f_{n}]$, then
$$
          (f_{k}|1) \subseteq   \neg \bar{\neg}(f_{k}|1).
$$
\begin{proof}  Assume that $(f_{k}|1) \subseteq   \neg
\bar{\neg}(f_{k}|1)$, i.e. $\neg (f_{k}|1) \supseteq 
\bar{\neg}(f_{k}|1)$ does not hold.  Then there exists some $x$
such that  $P_{\mathbf{N}\backslash k}x \in \bar{\neg}(f_k|1)$
and $P_{\mathbf{N}\backslash k}x \in (f_k|1)$.  Therefore, by
Proposition 4.2.6, $|f| = \bar{\neg}(f_{k}|1) \geq  2^{n-1}+1$.
\end{proof}

\textbf{Corollary 4.3.9} If $F = [f_{1},...,f_{n}]$ is a self-
dual minimal threshold transformation, then
$$
     (f_{i}|1) \subseteq   \neg \bar{\neg}(f_{i}|1)
\mbox{for every $i$.}
$$
\begin{proof}  Assume that $(f_k|1) \subseteq \neg
\bar{\neg}(f_{k}|1)$ does not hold for some $k$.  Then by
Proposition 4.3.8, $|f_k| \geq 2^{n-2} + 1$. Then
$|\bar{\neg}(f_k|1)| = |f_k| \geq 2^{n-2}+1$. Therefore,
$|\bar{\neg}(f_k|1)| < |f_k|$.  Hence, $F$ is not minimal,
because
$\mathrm{Var}(k^-F) < \mathrm{Var}F$ by Proposition 2.4.3.
\end{proof}


\section*{4.4 Circular one-to-one transformations\label{s:COOT}}
Let $F = \langle f\rangle $ for $\mathbf{Q}^{n}$ be a circular
threshold transformation, then $F$ is isometrically equivalent to
a circular minimal self-dual transformation $\langle g\rangle $
by Theorem 2.5.2 of Chapter 2.  Further $\langle g\rangle $ is a
threshold transformation by Proposition 4.3.2 (ii) of the present
chapter.  Therefore, in this section we construct minimal,
circular, one-to-one threshold transformations.

There are two naive approaches for obtaining a one-to-one
threshold transformations.  One is to construct a one-to-one
transformation first and modify it to a threshold transformation. 
The other is to construct a threshold transformation first and
modify it to a one-to-one transformation. 

We exclude from here compressible transformations, which are
described in Chapter 5.2.  In the follwing Examples, $F = \langle
f\rangle $ is a transformation of $\mathbf{Q}^{n}$. \\

\textbf{Notation}  In this section, $\mu  \in 
\mathrm{SYM}(\mathbf{N})$ denotes the linear permutation of
coefficients $(-1,2)$, that is,
$$
 \mu  = (2,n)(3,n-1)\cdot \cdot \cdot  (i,n-i+2)\cdot \cdot \cdot
([(n-1)/2+1,n+1-[((n-1)/2]).
$$

\textbf{Example 4.4.1}  $n$ is odd $(n = 2m+1)$.
$$
        f = p_{1}\cdot \cdot \cdot p_{m+1}\cdot \neg p_{m+2}\cdot
\cdot \cdot \neg p_{2m+1}.
$$
$\mathrm{GRAPH}(F)$ consists of one $2n$-cycle and loops.  E.g.
\begin{eqnarray*}
    11100 &\rightarrow & 01100 \rightarrow  01110 \rightarrow 
00110 \rightarrow  ...\\
            &\rightarrow & 11000 \rightarrow  11100.
\end{eqnarray*}
For $n = 3$, $F$ is isometrically equivalent to the compressible
transformation $\langle p_1\cdot p_2\cdot p_3\rangle$.  $F$ is
uniquely minimal for $n \geq  5$.\\

As a generalization of Example 4.4.1, we now determine a
condition for the transformation $F = \langle f\rangle $ of
$\mathbf{Q}^{n}$ for $n = 2m + 1$ such that
$$
 f = p_{1}\cdot q_{2}\cdot ...\cdot q_{n}, \quad \mbox{where
$q_{i} = p_{i}$ or $\neg p_{i}$ for every $i$}
$$
to be one-to-one.   

     Let $f = \{x\}$, a one-element set, where $x =
(1,x_{2},...,x_{n})$.  We assume $Fx = (0,x_{2},...,x_{n})$. In
order to determine a condition for $F(\mathrm{Car}F) =
\mathrm{Car}F$, suppose $Fx = \bar{\neg}\rho n^{h-1}x$ for $0 <
h-1 < n$.  Then
$$
     p_{1}x = 1, \quad 1^{-}x = \bar{\neg}\rho ^{h-1}x,
\eqno (4.4.1)
$$
that is, 
$$
     (0,x_{2},...,x_{n}) = (\neg x_{n+2-1+},..,\neg x_{n},0,\neg
x_{2},..,\neg x_{n+2-(h+1)}),
$$
that is,
$$
\neg x_{1} = 0 = \neg x_{n+2-h}, x_{2} = \neg x_{n+2-(h-1)},..,
x_{h-1}^{ }= \neg x_{n}, x_{h} = 0, x_{h+1} = \neg x_{2},..,
x_{n} = \neg x_{n+2-(h+1)},
$$
that is,
$$
\begin{array}{r}
x_{h} = 0, x_{h+(h-1)} = \neg x_{h}, x_{h+2(h-1)} = \neg x_{h+(h-
1)},...,\\
x_{n+2-h} = \neg x_{n+2-(h+(h-1))}, \neg x_{1} = 0 = \neg x_{n+2-
h},
\end{array}
\eqno (4.4.2)
$$
     If $h-1$ is relatively prime with $n$, the system of
equations (4.4.2) sequentially and uniquely determines $x_{i}$
from $x_{h}$ to $x_{1}$ by step $h-1$ of their subscripts. 
Further, the values of $x_{i}$ change $n-1$ times as the values
of $x_{i}$ are determined from $x_{h}$ to $x_{1}$.  Since $n-1$
is even, $x_{i}$ is consistently determined for every $i$.\\

\textbf{Example 4.4.2}  $n = 7$ and $h-1 = 2$.  The equation
$1^{-}x = \bar{\neg}(\rho )^{2}x$ for $x = (1,x_{2},..,x_{7})$ is
$$
     \neg x_{1} = 0 = \neg x_{6}, x_{2} = \neg x_{7}, x_{3} = 0,
x_{4} = \neg x_{2}, x_{5} = \neg x_{3}, x_{6} = \neg x_{4}, x_{7}
= \neg x_{5},
$$
that is,
$$
     x_{3} = 0, x_{5} = \neg x_{3}, x_{7} = \neg x_{5}, x_{2} =
\neg x_{7}, x_{4} = \neg x_{2},
     x_{6} = \neg x_{4}, \neg x_{1} = 0 = x_{6}.
$$
The solution is $x = 1100110$.  

Now assume $0 < h-1 < n$ is relatively prime with $n$, and let
$x$ be the solution of (4.4.1).  Then
\begin{eqnarray*}
     (\bar{\neg}\rho ^{h-1})^{2}x &=& (\bar{\neg}\rho ^{h-
1})(1^{-}x)\\
             &=& (\neg x_{n-h+2},..,\neg x_{n},1,\neg
x_{2},..,\neg x_{n-h+1})\\
               &=& h^{-}\bar{\neg}(\rho ^{h-1}x)\\
               &=& h^{-}1^{-}x.
\end{eqnarray*}
In general,
$$
\begin{array}{lll}
     (\bar{\neg}\rho ^{h-1})^{i}x &=& (1+(i-1)(h-1))^{-}(1+(i-
2)(h-1))^{-}
               ...(1+(h-1))^{-}1^{-}x\\
          & & \qquad \mbox{for any positive integer $i$.}
\end{array}
\eqno (4.4.3)
$$  
Therefore, $(\bar{\neg}\rho ^{h-1})^{i}x$ for $i = 1,..,2n-1$ are
all different from $x$. 

     Let $f = \{x \}$ and $F = \langle f\rangle $.  Then
$$
          Fx = 1^{-}x = \bar{\neg}\rho ^{h-1}x,
$$
and $F$ is one-to-one with one $2n$-cycle.

     To test whether $F$ is reflective or not, suppose $F$ is 
reflective through $\mu $.  Then $\mu Fx = \bar{\neg}x$ by
Proposition 3.4.2.  That is,
$$
     (0,x_{n,}x_{n-1},..,x_{2}) = (0,\neg x_{2},\neg
x_{3},..,x_{n}),
$$
so that $x_{i} = \neg x_{n+2-i}$, for every $i \geq  2$, that
is,$x = \bar{\neg}1^{-}\mu x$.

     we transform the system of equations (4.4.1) by replacing
$x$ with $\bar{\neg}1^{-}\mu x$.  Then we have
$$
    p_{1}(\bar{\neg}1^{-}\mu x) = 1, \quad
   1^{-}(\bar{\neg}1^{-}\mu x) = \bar{\neg}\rho ^{h-1}(\bar{\neg}1^{-}\mu x).
\eqno (4.4.4)
$$
By (4.4.2), (4.4.4) is equivalent to
$$
\begin{array}{r}
     \neg x_{n+2-h} = 0, \neg x_{n+2-(h+h-1)} = x_{n+2-h},
     \neg x_{n+2-(h+2(h-1))} = x_{n+2-(h+(h-1))},...,\\
     \neg x_{h} = x_{h+(h-1)}, \neg x_{1} = 0 = x_{h}.
\end{array}
\eqno (4.4.5)
$$
Clearly, (4.4.5) is equivalent to (4.4.2).  That is, the system
of equations (4.4.1) is invariant under the transformation
$\bar{\neg}1^{-}\mu $, so that the solution x of (4.4.1) is also
invariant under $\bar{\neg}1^{-}\mu $, i.e. $\bar{\neg}1^{-}\mu x
= x$.

     Now let $F = \langle f\rangle $ for $f = \{x\}$. Then
$$
  \mu Fx = (0,x_{n},x_{n-1},..,x_{2}), \quad \mbox{while 
$\bar{\neg}x = (0,\neg x_{2},\neg x_{3},...\neg x_{n})$}.
$$.
Therefore,
$$
     \mu Fx = \bar{\neg}x,
$$
since $\bar{\neg}1^{-}\mu x = x$.  Also
$$
     \lambda F(f\cup \bar{\neg}f)^{c} \cap  \bar{\neg}f =
\emptyset,
$$
since $\lambda F$ is one-to-one. Therefore, by Proposition
3.4.2, $F$ is reflective through any linear permutation of order
2. Thus we obtained the following theorem.\\

\textbf{Theorem 4.4.3}  Assume $0 < h-1 < n$ is relatively prime
with odd $n$.  Then there exists a one-to-one reflective
transformation $F = \langle f\rangle $ of $\mathbf{Q}^{n}$ such
that
\begin{eqnarray*}
     f &=& p_{1}\cdot \alpha _{2}q_{2}\cdot ...\cdot \alpha
_{n}q_{n}, \quad \mbox{where $\alpha _{i} = I_{\mathbf{Q}}$ or
$\neg $ for every $i$,}\\
     F &=& \bar{\neg}\rho ^{h-1} \quad \mbox{on $\mathrm{Car}F$.}
\end{eqnarray*}
In this case, f is uniquely determined by (4.4.2).  $F$ has one
$2n$-cycle.\\ 

Note that  $F = \bar{\neg}\rho ^{h-1}$ on $\mathrm{Car}F$ does
not gurantee $F$ to be reflective, although any isometry is
reflective.  For example, let $f = \{1110010, 1001011, 1000110\}$
and $F = \langle f\rangle $.  Then $F = \bar{\neg}\rho ^{2}$ on
$\mathrm{Car}F$, but $F$ is not reflective.\\

\textbf{Example 4.4.4}  For Example 4.4.2, we have $F = \langle
f\rangle $,
$f =  1\cdot 2\cdot \neg 3\cdot \neg 4\cdot 5\cdot 6\cdot \neg
7$.  The $14$-cycle of $F$ is
$$
\begin{array}{ccccccccccccc}
1100110&\rightarrow &0100110&\rightarrow &0110110&\rightarrow
&0110010&\rightarrow &0110011&\rightarrow & 
0010011&\rightarrow &0011011\\
      \uparrow  &&&&&&&&&&&& \downarrow\\                   
1100100&\leftarrow &1101100&\leftarrow &1001100&\leftarrow
&1001101&\leftarrow &1001001&\leftarrow &1011001&\leftarrow &
0011001             
\end{array}
$$                                 
   
\textbf{Example 4.4.5}  Let $F = \langle f\rangle $ be a
transformation 
described in Theorem 4.4.3 and let $F^{2} = \langle g\rangle $. 
Let $f = \{x\}$.  Then $F^{2}x = \{1,h\}^{-}x$ by (4.4.3), so
that
$$
     g = \{x, \bar{\neg}\rho ^{-(h-1)}x\}.
$$
On the other hand, $1^{-}x = \bar{\neg}\rho ^{(h-1)}x$, so that 
\begin{eqnarray*}
            \bar{\neg}\rho ^{-(h-1)}1^{-}x &=& x,\\
          (\rho ^{-(h-1)}1)^{-}\bar{\neg}\rho ^{-(h-1)}x &=& x,\\
          \bar{\neg}\rho ^{-(h-1)}x &=& (\rho ^{-(h-1)}1)^{-}x.
\end{eqnarray*}
Therefore,
$$
     g = \{x, (\rho ^{-(h-1)}1)^{-}x\}.
$$
Therfore, $F^{2}$ is a threshold transformation.  Similarly,
$F^{3}$ is athreshold transformation.\\
          
\textbf{Example 4.4.6} $n$ is even ($n = 2m$, $n \geq  4$).
We start from a one-to-one transformation  $F= \langle f\rangle$
defined by 
$$
     f = p_{1}\cdot \cdot \cdot p_{m+1}\cdot \neg p_{m+2}\cdot
\cdot \cdot \neg p_{2m}\vee p_{1}\cdot \cdot \cdot p_{m-1}\cdot
\neg p_{m}\cdot \cdot \cdot \neg p_{2m}.
$$
Then we add
$$
     g = p_{1}\cdot \cdot \cdot p_{m}\cdot \neg p_{m+1}\cdot
\cdot \cdot \neg p_{2m}\vee p_{1}\cdot \cdot \cdot p_{m-1}\cdot
\neg p_{m}\cdot \cdot \cdot \neg p_{2m}.
$$
to get a threshold transformation
$$
  H = \langle f\rangle\odot \langle g\rangle = \langle h\rangle. 
$$
Then 
$$
     h = p_1\cdot ..\cdot p_{m-1}\cdot (p_{m}\vee \neg p_{m+1})
\cdot \neg p_{m+2}\cdot ..\cdot \neg p_{2m}.
$$
$\mathrm{GRAPH}(H)$ consists of three $n$-cycles and loops.  E.g. 
\begin{eqnarray*}
      1100 &\rightarrow & 0110 \rightarrow  0011 \rightarrow 
1001 \rightarrow  1100,\\
    1110 &\rightarrow & 0111 \rightarrow  1011 \rightarrow  1101
\rightarrow  1110,\\
      1000 &\rightarrow & 0100 \rightarrow  0010 \rightarrow 
0001 \rightarrow  1000.
\end{eqnarray*}
For $n = 4$, $H$ is not minimal and isometrically equivalent
to the compressible transformation $\langle p_1\cdot p_2\cdot
p_3\cdot p_4\rangle$.  $H$ is uniquely minimal for $n \geq  6$.\\

In the following, we construct one-to-one circular
transformations of small dimensions, and then modify them to
general dimensions if possible.  In $F = \langle f\rangle $, $f$
is expressed with skipped $p$ in these examples.\\

\textbf{Example 4.4.7} Start with $110010$ and add $110100$ to
create a one-to-one transformation.  Then, to make it a threshold
transformation, add $110110$ to obtain
$$
          f = 1\cdot 2\cdot \neg 3\cdot (4\vee 5)\cdot \neg 6
$$
$\mathrm{GRAPH}(F)$ consists of three 6-cycles and loops.  The
flow graph is 
$$
  \;  [1\cdot 2\cdot \neg 3\cdot 4\cdot \neg 5\cdot \neg
6]\partial , \quad
[1\cdot 2\cdot \neg 3\cdot 4\cdot 5\cdot \neg 6]\partial .
$$  
$f$ can be generalized to
\begin{eqnarray*}
     f &=& 1\cdot 2\cdot \neg 3\cdot 4\cdot (\neg 5\vee \neg
6)\cdot 7\cdot \neg 8,\\
     f &=& 1\cdot 2 \neg 3\cdot 4\cdot \neg 5\cdot (6\vee
7)\cdot \neg 8\cdot 9\cdot \neg 10,\\
     f &=& 1\cdot 2 \neg 3\cdot 4\cdot \neg 5\cdot 6 \cdot (\neg
7\vee \neg 8)\cdot 9\cdot \neg 10 \cdot 11 \cdot \neg 12,
\end{eqnarray*}
and so on.  In general, $\mathrm{GRAPH}(F)$ consists of three
$2m$-cycles and loops.

$f$ can also be generalized to
\begin{eqnarray*}
     f &=& 1\cdot ..\cdot m\cdot \neg (m+1)\cdot ..\cdot \neg
(2m-1)\\
       & & \quad \cdot (2m\vee (3m-1))\cdot ((2m+1)\cdot ..\cdot
3m-2)\cdot (\neg (3m)\cdot ..\cdot \neg (4m-2).
\end{eqnarray*}
$\mathrm{GRAPH}(F)$ consists of three $(4m-2)$-cycles and
loops.\\ 

\textbf{Example 4.4.8}  Start with $111010$.  Add $101000$,
$101110$, and $100010$ to create a one-to-one transformation
having the cycle $\mathrm{Orb}_{\rho }111010$.   Then add
$101010$ and $111000$ and get a one-to-one threshold
transformation $F$ defined by
$$
     f = 1\cdot 3\cdot \neg 4\cdot \neg 6\vee 1\cdot (3\vee \neg
4)\cdot \neg 2\cdot 5\cdot \neg 6.
$$
$\mathrm{GRAPH}(F)$ consists of three 6-cycles, one 2-cycle and
loops.  A flow graph is 
$$
   \; [1\cdot 2\cdot 3\cdot \neg 4\cdot 5\cdot \neg 6]\partial ,
\quad 
[1\cdot 2\cdot 3\cdot \neg 4\neg 5\neg 6]\partial , \quad [1\cdot
\neg 2\cdot 3\cdot \neg 4\cdot 5\cdot \neg 6]\partial .
$$

\textbf{Example 4.4.9}
$$
    f = 1\cdot 2\cdot \neg 3\cdot \neg 6\vee 1\cdot 2\cdot 4\cdot
\neg 5\cdot \neg 6\vee 1\cdot \neg 3\cdot 4\cdot \neg 5\cdot \neg
6.    
$$
$\mathrm{GRAPH}(F)$ consists of four 6-cycles, two 3-cycles and
loops.  A flow graph is 
$$
\;    [1\cdot 2\cdot 3\cdot 4\cdot \neg 5\cdot \neg 6]\partial
,\quad
[1\cdot 2\cdot \neg 3\cdot 4\cdot 5\cdot \neg 6]\partial , \quad
[1\cdot 2\cdot \neg 3\cdot 4\cdot \neg 5\cdot \neg 6]\partial .
$$

\textbf{Example 4.4.10}
$$
    f = 1\cdot 2\cdot \neg 3\cdot \neg 6\vee 1\cdot 2\cdot \neg
5\cdot \neg 6\vee 1\cdot \neg 3\cdot 4\cdot \neg 5\cdot \neg 6.
$$
$\mathrm{GRAPH}(F)$ consists of five 6-cycles, two 3-cycles and
loops.  A flow graph is
$$
\begin{array}{cc}
  \;  [1\cdot 2\cdot 3\cdot 4\cdot \neg 5\cdot \neg 6]\partial ,
&
[1\cdot 2\cdot 3\cdot \neg 4\cdot \neg 5\cdot \neg 6]\partial ,
\\
  \; [1\cdot 2\cdot \neg 3\cdot 4\cdot \neg 5\cdot \neg
6]\partial ,
& [1\cdot 2\cdot \neg 3\cdot 4\cdot 5\cdot \neg 6]\partial .
\end{array}
$$

\textbf{Example 4.4.11}
$$
   f = 1\cdot 2\cdot 3\cdot \neg 4\cdot \neg 5\vee 1\cdot 2\cdot
3\cdot \neg 4\cdot \neg 6\vee 1\cdot 2\cdot \neg 4\cdot \neg
5\cdot \neg 6\vee 1\cdot 3\cdot \neg 4\cdot \neg 5\cdot \neg 6.
$$
$\mathrm{GRAPH}(F)$ consists of six 4-cycles, one 6-cycle and
loops.  A flow graph is
$$
\;    [1\cdot 2\cdot 3\cdot 4\cdot \neg 5\cdot \neg 6]
\leftrightarrow  [1\cdot 2\cdot 3\cdot \neg 4\cdot 5\cdot \neg
6],
\quad 
[1\cdot 2\cdot 3\cdot \neg 4\cdot \neg 5\cdot \neg 6]\partial .
$$

\textbf{Example 4.4.12}  
$$
    f = 1\cdot 2\cdot \neg 5\cdot \neg 6\vee 1\cdot 2\cdot 3\cdot
\neg 4\cdot \neg 6.
$$
$\mathrm{GRAPH}(F)$ consists of three 6-cycles, two 12-cycle and
loops.  A flow graph is 
\begin{eqnarray*}
\;    [1\cdot 2\cdot 3\cdot 4\cdot \neg 5\cdot \neg 6]\partial
,&&
[1\cdot 2\cdot 3\cdot \neg 4\cdot \neg 5\cdot \neg 6]\partial ,\\
   \; [1\cdot 2\cdot 3\cdot \neg 4\cdot 5\cdot \neg 6]
&\leftrightarrow & [1\cdot 2\cdot \neg 3\cdot 4\cdot \neg 5\cdot
\neg 6].
\end{eqnarray*}

\textbf{Example 4.4.13}
$$
    f = 1\cdot 2\cdot \neg 3\cdot \neg 6\vee 1\cdot 2\cdot 4\cdot
\neg 5\cdot \neg 6.
$$
$\mathrm{GRAPH}(F)$ consists of five 6-cycles and loops.  The
flow graph
is 
$$
  \;  [1\cdot 2\cdot 3\cdot 4\cdot \neg 5\cdot \neg 6]\partial ,
\quad
[1\cdot 2\cdot \neg 3\cdot 4\cdot 5\cdot \neg 6]\partial , \quad
[1\cdot 2\cdot \neg 3\cdot 4\cdot \neg 5\cdot \neg 6]\partial .
$$

\textbf{Example 4.4.14}
$$
  f = 1\cdot 2\cdot \neg 3\cdot \neg 6\vee 1\cdot 2\cdot \neg
5\cdot \neg 6.
$$
$\mathrm{GRAPH}(F)$ consists of six 6-cycles and loops.  A flow
graph is 
$$
\begin{array}{ll}
\;    [1\cdot 2\cdot 3\cdot 4\cdot \neg 5\cdot \neg 6]\partial ,&
[1\cdot 2\cdot 3\cdot \neg 4\cdot \neg 5\cdot \neg 6]\partial ,
\\
  \; [1\cdot 2\cdot \neg 3\cdot 4\cdot 5\cdot \neg 6]\partial ,&
[1\cdot 2\cdot \neg 3\cdot 4\cdot \neg 5\cdot \neg 6]\partial . 
\end{array}
$$

\textbf{Example 4.4.15} $n \geq  4$. 
$$
    f = p_{1}\cdot p_{2}\cdot S_{n-3}\{ p_{3},...,p_{n}\} .
$$
If $n$ is even, $\mathrm{GRAPH}(F)$ consists of two $n$-cycles,
one 2-cycle and loops. E.g. 
\begin{eqnarray*}
    1110 &\rightarrow & 0010 \rightarrow  1011 \rightarrow  1000
\rightarrow  1110,\\
    1101 &\rightarrow & 0100 \rightarrow  0111 \rightarrow  0001
\rightarrow  1101,\\
    1111 &\rightarrow & 0000 \rightarrow  1111. 
\end{eqnarray*}
If $n$ is odd, $\mathrm{GRAPH}(F)$ consists of one $2n$-cycle,
one 2-cycle and loops.  E.g.
\begin{eqnarray*}
    11110 &\rightarrow & 00010 \rightarrow  11011 \rightarrow 
01000\\
            &\rightarrow & 01111 \rightarrow  00001 \rightarrow 
11101 \rightarrow  00100\\
    10111 &\rightarrow & 10000 \rightarrow  11110,\\
     11111 &\rightarrow & 00000 \rightarrow  11111.
\end{eqnarray*}

\textbf{Example 4.4.16} $n = 4m+2$, $m \geq  1$.
\begin{eqnarray*}
 f &=& p_{1}\cdot \cdot \cdot p_{m+1}\cdot \neg p_{m+2}\cdot
\cdot \cdot \neg p_{2m+1}\cdot p_{2m+3}\cdot \cdot \cdot
p_{3m+1}\cdot \neg p_{3m+3} \\
 && \quad \cdot \cdot \cdot \neg p_{4m+2} \cdot (p_{2m+2}\vee
p_{3m+2}).
\end{eqnarray*}
$\mathrm{GRAPH}(F)$ consists of three $n$-cycles and loops.  E.g.
\begin{eqnarray*}
    110100 &\rightarrow & 010110 \rightarrow  010011 \rightarrow 
011001 \\
            &\rightarrow & 001101 \rightarrow  100101 \rightarrow 
110100,\\
    101001 &\rightarrow & 101100 \rightarrow  100110 \rightarrow 
110010 \\
            &\rightarrow & 011010 \rightarrow  001011 \rightarrow 
101001,\\
    110110 &\rightarrow & 010010 \rightarrow  011011 \rightarrow 
001001 \\
            &\rightarrow & 101101 \rightarrow  100100 \rightarrow 
110110. 
\end{eqnarray*}

\textbf{Example 4.4.17}  $f$ is defined recursively as follows,
where $f = f^{(n)}$  for $\mathbf{Q}^{n}$: 
\begin{eqnarray*}
    f^{(4)} &=& p_{1}\cdot p_{2}\cdot \neg p_{3}\cdot \neg
p_{4},\\
 f^{(5)} &=& p_{1}\cdot p_{2}\cdot \neg p_{4}\cdot \neg p_{5}.\\
    f^{(n)} &=& p_{1}\cdot p_{2}\cdot \neg p_{n-1}\cdot \neg
p_{n}\vee f^{(n-2)}\cdot \neg p_{n}.
\end{eqnarray*}\\

The proof that $f$ is a one-to-one threshold transformation is
described in the following.\\   

\textbf{Proposition 4.4.18}  $f$ of Example 4.4.17 is a threshold 
function.
\begin{proof} $f^{(n)}$ can be expressed as $f^{(n)}= p_{1}\cdot
p_{2}\cdot \neg p_{n}\cdot (\neg p_{n-1}\vee f^{(n-2)})$.  If
$f^{(n-2)}$ is a threshold function, then $f^{(n)}$ is a
threshold function by Proposition 4.1.2.
\end{proof}

\textbf{Lemma 4.4.19}  A point $x = (x_{1},...,x_{n})$ belongs to
$f^{(n)}$ if and only if (i) $x_{1} = x_{2} = 1$, $x_{n} = 0$,
and (ii) there exist consecutive 0s in $x$, and there exist no
consecutive 1s after the last consecutive 0s and before $x_{1}$.

\begin{proof}  This characterization of $f$ follows from its
recursive definition above.
\end{proof}

\textbf{Lemma 4.4.20}  $\mu Ff \subseteq  \bar{\neg}f$.
\begin{proof}  Let $x \in  f$.  (i)  If $x = 111x_{3}\cdot \cdot
\cdot x_{n-1}0$, then $Fx = 011(Fx)_{4}\cdot \cdot \cdot (Fx)_{n-
1}0$, so that $\mu Fx \in  \bar{\neg}f$ by Lemma 4.4.19. 
Similarly,
(ii) 
If $x = 1100x_{5}\cdot \cdot \cdot x_{n-1}0$, then $Fx =
0110(Fx)_{5}\cdot \cdot \cdot (Fx)_{n-1}0$, so that $\mu Fx \in 
\bar{\neg}f$.  (iii) If $x = 110101\cdot \cdot \cdot
0100x_{2m+1}\cdot
\cdot \cdot x_{n-1}0$ then $Fx = 0101\cdot \cdot \cdot
0110(Fx)_{2m+1}\cdot \cdot \cdot (Fx)_{n-1}0$, so that $\mu Fx
\in  \bar{\neg}f$.  (iv) If $x = 110101\cdot \cdot \cdot
011x_{2m}\cdot \cdot \cdot x_{n-1}0$, then $Fx = 010101\cdot
\cdot \cdot 011(Fx)_{2m}\cdot \cdot \cdot (Fx)_{n-1}0$, so that
$\mu Fx \in  \bar{\neg}f$.
\end{proof}

\textbf{Lemma 4.4.21}  $\mu F(f\vee \bar{\neg}f)^{c }\cap 
\bar{\neg}f = \emptyset $.
\begin{proof}  Let $x \notin  f\cup \bar{\neg}f$.  If $x_{1} =
1$,
then $(\mu Fx)_{1} = 1$, so that $\mu Fx \notin  \bar{\neg}f$. 
Let
x$_{1} = 0$.  Then $(Fx)_{1} = 0$, since $x \notin  \bar{\neg}f$. 
(i)  Let $(x_{1},x_{2}) = 00$.  Then $((Fx)_{1},(Fx)_{2}) = 00$,
so that $(\mu Fx)_{n} = 0$, and hence $\mu Fx \notin 
\bar{\neg}f$.   
(ii) Let $(x_{1},x_{2}) = 01$.  (iia)  If $x \in \rho f$ then
$(Fx)_{2} = 0$, so that $(\mu Fx)_{n} = 0$, and hence $\mu Fx
\notin  \bar{\neg}f$.  Let $x \notin \rho f$.   (iib)  Let
$x_{3}= 0$. 
If $x_{n} = 1$, then $(Fx)_{n} = 1$, so that $(\mu Fx)_{2} = 1$,
and hence $\mu Fx \notin  \bar{\neg}f$.  Let $x_{n} = 0$.  Let
the
first same consecutive elements be $(x_{i},x_{i+1}) = 00$, i.e.
$x = 010\cdot \cdot \cdot 10100x_{i+2}\cdot \cdot \cdot 0$. Then
$Fx = 010\cdot \cdot \cdot 10100(Fx)_{i+2}\cdot \cdot \cdot $, so
that $\mu Fx = 0(Fx)_{n}\cdot \cdot \cdot 00101\cdot \cdot \cdot
01 \notin  \bar{\neg}f$.   Let the first same consecutive
elements be
$(x_{i},x_{i+1}) =11$.  Then $x = 010\cdot \cdot \cdot
1011x_{i+2}\cdot \cdot \cdot 0$.  Then $Fx = 010\cdot \cdot \cdot
1001(Fx)_{i+2}\cdot \cdot \cdot $, so that $\mu Fx \notin 
\bar{\neg}f$.  (iic)  Let $x_{3}
= 1$.  Since $x = 011x_{4}\cdot \cdot
\cdot \notin \rho f$, $x_{n} = 1$.  Therefore, $Fx =
01(Fx)_{3}\cdot \cdot \cdot 1$, so that $\mu Fx = 01(\mu
Fx)_{3}\cdot \cdot \cdot \notin  \bar{\neg}f$.
\end{proof}

\textbf{Proposition 4.4.22}  $F$ is reflective through $\mu $. 

\begin{proof}  Apply the results of Lemmas 4.4.20 and 4.4.21 to
Proposition 3.4.2 of Chapter 3.
\end{proof}

From Propositions 4.4.18 and 4.4.22 it follows that\\

\textbf{Proposition 4.4.23}  The transformation of Example 4.4.17 
is a one-to-one threshold  transformation.\\

\textbf{Proposition 4.4.24}  Any transformation $F$ in this
section is reflective through any linear permutation of slope
$-1$.  In particular, $F^{-1}$ is isometrically similar to $F$
and a threshold transformation.

\begin{proof}  Let $F = \langle f \rangle $.  We have already
proved that $F$ of Example 4.4.17 is reflective through any
linear permutation of slope $-1$.  It is easily confirmed that 
$\mu Fx \in  \bar{\neg}f$ for every $x \in  f$ and $\mu Fx \notin 
\bar{\neg}f$ for every $x \notin  f\vee \bar{\neg}f$ for the
other examples. 
Therefore, by Proposition 3.4.2 of Chapter 3, $F$ is reflective
through any linear permutation of slope $-1$.
\end{proof}

\textbf{Corollary 4.4.25}  Any transformation in this section is
isometrically equivalent to threshold transformations whose
graphs consist of 2-cycles and loops.\\

\section*{4.5  Skew-circular one-to-one transformations}
     
     In this section, we construct minimal, skew-circular,
one-to-one threshold transformations.  All transformations
$F = \langle\langle f\rangle\rangle $ of $\mathbf{Q}^{n}$ in the
examples of this section are threshold transformations,
since $f$ are threshold functions.  They are also mutually
isometrically non-equivalent and uniquely minimal.
     
\textbf{Notation}  Let $\lambda $ and $\mu  \in 
\mathrm{SYM}(\mathbf{N})$ denote the linear permutations of
coefficients $(-1,1)$ and $(-1,2)$ respectively, that is,
\begin{eqnarray*}
      \lambda  &=& (1,n)\cdot (2,n-1)\cdot \cdot \cdot
(i,n-i+1)\cdot \cdot \cdot ([n/2],n-[n/2]+1),\\ 
      \mu  &=& (2,n)\cdot (3,n-1)\cdot \cdot \cdot (i,n-i+2)\cdot
     \cdot \cdot ([(n-1)/2]+1,n+1-[(n-1)/2]). 
\end{eqnarray*}
     
\textbf{Example 4.5.1}  $F = \langle\langle f\rangle\rangle$,
where $f = p_{1}\cdot \cdot \cdot p_{i}\cdot \cdot \cdot
p_{n}$, is a one-to-one threshold transformation, which is
reflective through $\lambda $.   Further, $\mathrm{CS}(F)
= \{(1,2n), (2^{n}-2n,1)\}$.\\ 
     
     As a generalization of Example 4.5.1, we now determine
a condition for the transformation $F = \langle\langle
f\rangle\rangle $ of $\mathbf{Q}^{n}$ such that
$f = p_{1}\cdot q_{2}\cdot ...\cdot q_{n}$, where
$q_{i} = p_{i}$ or $\neg p_{i}$ for every $i$, 
to be one-to-one.   
          
     Let $f = \{ x\}$ , a one-element set, where
$x = (1,x_{2},..,x_{n})$.  We assume $Fx =
(0,x_{2},..,x_{n})$.
In order to determine a condition for
$F(\mathrm{Car}F) = \mathrm{Car}F$, suppose
$Fx = (\rho n^{-})^{h-1}x$ for $0 < h-1 < 2n$.  Then
$$
      p_{1}x = 1, \quad 1^{-}x = (\rho n^{-})^{h-1}x. 
\eqno (4.5.1)
$$
If $0 < h-1 < n$, then 
$$
     (0,x_{2},..,x_{n}) = (\neg x_{n+2-h},..,\neg
      x_{n},1,x_{2},..,x_{n+2-(h+1)}),
$$
that is,
$$
\begin{array}{r}
     \neg x_{1} = 0 = \neg x_{n+2-h}, x_{2} = \neg
     x_{n+2-(h-1)},..., x_{h-1} = \neg x_{n},\\
      x_{h} = 1, x_{h+1} = x_{2},..., x_{n} =
x_{n+2-(h+1)},
\end{array}
$$
that is,
$$
\begin{array}{r}
     x_{h} = 1, x_{h+(h-1)} = \alpha _{h}x_{h},\;
     x_{h+2(h-1)} = \alpha _{h+(h-1)}x_{h+(h-1)},..,\\
     x_{n+2-h} = \alpha _{n+2-(h+(h-1))}x_{n+2-(h+(h-1))},\;
     \neg x_{1} = 0 = \neg x_{n+2-h},
\end{array}
\eqno (4.5.2)
$$
where
$$
      \alpha _{i } =  \left \{
    \begin{array}{ll}
        \neg   & \mbox{for $n+2-(h-1) \leq  i \leq  n$,}\\
        I_{\mathbf{Q}} \quad \mbox{(identity)} &
	\mbox{for $2 \leq  i \leq n+2-(h+1)$}.
          \end{array}
                    \right.
$$                                                          
   In particular, the number of $i$ such that
$\alpha _{i} = \neg $ is $h-2$.
     
         If $n < h-1 < 2n$, then for $h' = h - n$, 
$$
     (0,x_{2},...,x_{n}) = (x_{n+2-h'},..,x_{n},0,\neg
     x_{2},..,\neg x_{n+2-(h'+1)}),
$$
that is,
$$
\begin{array}{r}
    x_{h'} = 0,\; x_{h'+(h'-1)} = \alpha '_{h'}x_{h'},\;
    x_{h'+2(h'-1)} = \alpha '_{h'+(h'-1)}x_{h'+(h'-1)},..,\\
    x_{n+2-h'} = \alpha '_{n+2-(h'+(h'-1))}x_{n+2-(h'+(h'-1))},\;
    \neg x_{1} = 0 = x_{n'+2-h'},
\end{array}
\eqno (4.5.2)'
$$
where
$$
    \alpha '_{i } =  \left \{
         \begin{array}{ll}
     I_{\mathbf{Q}} & \quad \mbox{for $n+2-(h'-1)\leq
     i\leq n$,}\\
       \neg & \quad \mbox{for $2 \leq i \leq n+2-(h'+1)$,}
       \end{array}
               \right.
$$
particularly the number of $i$ such that $\alpha _{i} =
\neg $ is $n-h'$.  
          
      If $0 < h-1 < n$ is relatively prime with $n$, the
system of equations (4.5.2) sequentially and uniquely
determines $x_{i}$ from $x_{h} = 1$ to $\neg x_{1} = 0$
by step $h-1$ of their subscripts.  Further, the values of
$x_{i}$ change $h-1$ times as the values of $x_{i}$ are
determined from $x_{h}$ to $x_{1}$.   Therefore, if $h-1$
is relatively prime with $2n$, then $x_{i}$ is consistently
determined for every $i$.

Similarly, if $0 < h'-1 < n$, $h'-1$ is relatively prime
with $n$, and $n-h'$ is even (i.e. $n < h-1 < 2n$ and $h-1$ is
relatively prime with $2n$), then (4.5.2)' is uniquely
solved.

Consequently (4.5.1) is uniquely solved if $0 < h < 2n$ and
$h$ is relatively prime with $2n$.\\ 
          
\textbf{Example 4.5.2}  Let $n = 7$ and $h-1 = 9$.  The
equation $1^{-}x = (\rho 7^{-})^{9} = \bar{\neg}(\rho
7^{-})^{2}x$ for $x = (1,x_{2},..,x_{7})$ is
$$
     \begin{array}{r}
     \neg x_{1} = 0 = x_{6}, x_{2} = x_{7}, x_{3} = 0,
x_{4}  = \neg x_{2},\\
    x_{5} = \neg x_{3}, x_{6} = \neg x_{4}, x_{7} =
\neg x_{5},
\end{array}
$$
that is,
$$
    \begin{array}{r}
     x_{3} = 0, x_{5} = \neg x_{3}, x_{7} = \neg x_{5},
     x_{2} = x_{7},\\
     x_{4} = \neg x_{2}, x_{6} = \neg x_{4}, \neg
x_{1} = 0 = x_{6}.
\end{array}
$$
The solution is $x = 1001100$.\\  
          
   Now assume $0 < h-1 < 2n$ and $h-1$ is relatively prime
with $2n$, and let $x$ be the solution of (4.5.1).  Then
\begin{eqnarray*}
      ((\rho n^{-})^{h-1})^{2}x &=& (\rho
     n^{-})^{h-1}(1^{-}x)\\
          &=&  (\neg x_{n-h+2},..,\neg
     x_{n},0,x_{2},..,x_{n-h+1})\\
         &=& h^{-}((\rho n^{-})^{h-1}x)\\
         &=& h^{-}1^{-}x.
\end{eqnarray*}
In general,
$$
\begin{array}{lll}
         (\rho n^{-})^{i(h-1)}x &=& (1+(i-1)(h-1))^{-}
         (1+(i-2)(h-1))^{-}...(1+(h-1))^{-}1^{-}x\\
     & & \qquad \mbox{for every positive integer $i$}.
\end{array}
\eqno (4.5.3)
$$
Therefore, $(\rho n^{-})^{i(h-1)}x$ for
$i = 1,..,2n-1$ are all different from $x$ and
$(\rho n^{-})^{n(h-1)}x = \bar{\neg}x$.  Let $f = \{ x\}$
and $F = \langle\langle f\rangle\rangle $.  Then
$$
        Fx = 1^{-}x = (\rho n^{-})^{h-1}x,
$$
and $F$ is one-to-one with one $2n$-cycle. 
     
      Now we transform the system of equations (4.5.1) by
replacing $x$ with $\mu x$.  Then we have
$$
    p_{1}(\mu x) = 1, \quad 1^{-}\mu x) = \bar{\neg}
     (\rho n^{-})^{h-1}(\mu x).
\eqno (4.5.5)
$$
If $0 < h-1 < n$, then by (4.5.2), (4.5.5) is equivalent to
$$
\begin{array}{r}
     x_{n+2-h} = 1, x_{n+2-(h+h-1)} = \epsilon _{h}x_{n+2-h},
x_{n+2-(h+2(h-1))} = \epsilon _{h+(h-1)}x_{n+2-(h+(h-1))},...,\\
x_{h} = \epsilon _{n+2-(h+(h-1))}x_{h+(h-1)}, x_{1} = 0
=  \neg x_{h}.
\end{array}
\eqno (4.5.6)
$$
If $2 \leq  i \leq  n+2-(h+1)$, then
$$
   n+2-(h-1)-(n+2)+(h+1) \leq  n+2-(h-1)-i \leq  n+2 -(h-1)-2,
$$
so that $2 \leq  n+2-(h+1)$.  Therefore, if $i + j = n+2-(h-1)$,
then $\epsilon _{i} = \epsilon _{j}$ by (4.5.3).  Therefore,
(4.5.6) is equivalent to (4.5.2).  That is, the system of
equations (4.5.1) is invariant under $\mu $, so that the
solution $x$ of (4.5.1) is also invariant under $\mu $, i.e. $\mu x =
x$.  The same is true for $n < h < 2n$.
      
    Now let $F = \langle\langle f\rangle\rangle $ for $f =
     \{x\}$. Then
$$
   \lambda Fx = (x_{n},x_{n-1},..,x_{2},0), \quad \mbox{while
     $\bar{\neg}(\rho n^{-})^{n-1}x = (x_{2},x_{3},...x_{n},0)$}. 
$$
     Therefore,
$$
           \lambda Fx = \bar{\neg}(\rho n^{-})^{n-1}x,
$$
     since $\mu x = x$.  Also
$$
    \lambda F(f\cup \bar{\neg}f)^{c} \cap  \bar{\neg}(\rho
n^{-})^{n-1}f = \emptyset ,
$$
since $\lambda F$ is one-to-one. Therefore, by Proposition
3.4.5,
$F$ is reflective through $(\rho n^{-})^{i}\lambda $ for
every $i$. Thus we obtained the following theorem.
       
\textbf{Theorem 4.5.3}  Assume $0 < h-1 < 2n$ is relatively
prime with $2n$,  Then there exists a one-to-one reflective
transformation $F = \langle\langle f\rangle\rangle $ of
$\mathbf{Q}^{n}$ such that
\begin{eqnarray*}
      f &=& p_{1}\cdot \alpha _{2}q_{2}\cdot ...\cdot \alpha
     _{n}q_{n}, \quad \mbox{where $\alpha _{i} = I_{\mathbf{Q}}$
or  $\neg $ for every $i$,}\\
    F &=& (\rho n^{-})^{h-1} \quad \mbox{on $\mathrm{Car}F$.}
\end{eqnarray*}
     In this case, $f$ is uniquely determined by (4.5.2) or
(4.5.2)'.   $F$ has one $2n$-cycle.\\
      
\textbf{Example 4.5.4}  For Example 4.5.2, we have $F =
\langle\langle f\rangle\rangle $, $f = 1\cdot \neg 2\cdot
\neg 3\cdot 4\cdot 5\cdot \neg 6\cdot \neg 7$.  The
$14$-cycle of $F$ is
$$
     \begin{array}{c}
1001100 \rightarrow  0001100 \rightarrow  0011100
\rightarrow 0011000 \rightarrow  0011001 \rightarrow  0111001\\
\rightarrow  0110001 \rightarrow  0110011 \rightarrow 
     1110011 \rightarrow  1100011 \rightarrow  1100111\\
 \rightarrow  1100110 \rightarrow  1000110 \rightarrow 
     1001110 \rightarrow 1001100. 
\end{array}
$$
     
\textbf{Example 4.5.5}  Consider $F$ of Example 4.5.1.  Then
   $F^{2} = \langle\langle p_{1}\cdot \cdot \cdot \cdot
p_{n-1}\rangle\rangle $ is a one-to-one threshold transformation.
$F^{2}$ is reflective through $\lambda $, since $F$ is reflective
through $\lambda $.  $\mathrm{CS}(F^{2}) =
\{ (2,n), (2^{n}-2n,1)\}$.  Further, $F^{3}
= \langle\langle  p_{1}\cdot \cdot \cdot p_{n-2}\cdot 
(p_{n-1}\vee \neg p_{n-1})\rangle\rangle $ is also an
incompressible and inexpansible threshold transformation
that is reflective through $\lambda $.\\
     
\textbf{Example 4.5.6}  Let $F = \langle\langle
f\rangle\rangle $ be the self-dual transformation of
$\mathbf{Q}^{n}$ defined by
$$
   f = p_{1}\cdot p_{2}\cdot S_{n-4}\{p_{3},p_{4},...,
   p_{n-1}\}\cdot p_{n}.
$$
The proof of the reflectiveness and hence one-to-one of F is
given in the following.\\
     
\textbf{Lemma 4.5.7}  Let $F$ of Example 4.5.6 be
 $[f_{1},...,f_{n}]$.   If $i \ne  j$, then $f_{i}\cap
(f_{j}\vee \bar{\neg}f_{j}) = \emptyset $.
\begin{proof} $f_{i} = (\rho n^{-})^{i-1}f$ by definition. 
     First, $f_{1}\cap f_{i} = \emptyset $ for every $i \ne  1$
by the following reasons: $x \in  f_{2}$ implies $x_{1 }= 0$,
while $x \in  f_{1}$ implies $x_{1} = 1$; $x \in  f_{3}$
implies $x_{2} = 0$, while $x \in  f_{1}$ implies $x_{2} = 1$.
If $i \geq 4$, then $x \in  f_{i}$ implies that the density of
$x$ is less than $n-2$, while the density of any $x \in  f_{1}$
is $n-1$ or $n$. 
     Next, $f_{i} = (\rho n^{-})^{i-1}f_{1}$ and $f_{j} = (\rho
n^{-})^{i-1}f_{j-i+1}$, and $(\rho n^{-})^{i-1}$ is one-to-one,
so that $f_{i}\cap f_{j} = \emptyset $ for every $i \ne  j$. 
Similarly, we can show that $f_{i}\cap \bar{\neg}f_{j} =
\emptyset $
for every $i \ne  j$.
\end{proof}
     
\textbf{Lemma 4.5.8}  $\lambda (\mathrm{Car}F) \subseteq 
\mathrm{Car}F$ in Example 4.5.6.
\begin{proof}  Let $f_{i}$ be decomposed as $f_{i} =
g_{i}\vee h_{i}$, where
\begin{eqnarray*}
    g_{1} &=& p_{1}\cdot p_{2}\cdot p_{3}\cdot \cdot
\cdot p_{n-2}\cdot \neg p_{n-1}\cdot p_{n},\\
h_{1} &=& p_{1}\cdot p_{2}\cdot S_{n-5}\{
p_{3},p_{4},...,p_{n-2}\} \cdot  p_{n-1}\cdot p_{n}.\\
g_{i} &=& (\rho n^{-})^{i-1}g_{1} \; \mbox{for every}\;
i,\\
 h_{i} &=& (\rho n^{-})^{i-1}h_{1} \; \mbox{for every}\; i.
\end{eqnarray*}
     
Then it can be shown that $\lambda g_{i} = \bar{\neg}g_{n-i+4}$
or $g_{n-i+4}$, and $\lambda h_{i} = \bar{\neg}h_{n-i+2}$
or $h_{n-i+2}$ for every $i$.  For example, suppose 
$4 \leq  i \leq  n-1$.   Then 
\begin{eqnarray*}
 g_{i} &=& p_{i}\cdot p_{i+1}\cdot \cdot \cdot p_{n}\cdot
\neg p_{1}\cdot \cdot \cdot \neg p_{i-3}\cdot
p_{i-2}\cdot \neg p_{i-1}. \\
\lambda g_{i} &=& p_{n-i+1}\cdot p_{n-i}\cdot \cdot \cdot
 p_{1}\cdot \neg p_{n}\cdot \neg p_{n-1}\cdot \cdot \cdot
\neg p_{n-i+4}\cdot p_{n-i+3}\cdot \neg p_{n-i+2} \\
&=& \neg p_{n-i+4}\cdot \neg p_{n-i+5}\cdot \cdot \cdot
\neg p_{n}\cdot p_{1}\cdot \cdot \cdot p_{n-i+1}\cdot
\neg p_{n-i+2}\cdot p_{n-i+3} \\
&=& \bar{\neg}g_{n-i+4}. \\
h_{i} &=& p_{i}\cdot p_{i+1}\cdot S_{n-5}\{
 p_{i+2},..,p_{n},\neg p_{1},..,\neg p_{i-3 }\}\cdot \neg
p_{i-2}\cdot \neg p_{i-1}.\\
\lambda h_{i} &=& p_{n-i+1}\cdot p_{n-i}\cdot S_{n-5}\{
p_{n-i-1},..,p_{1},\neg p_{n},..,\neg p_{n-i+4}\} \cdot
\neg p_{n-i+3}\cdot \neg p_{n-i+2}\\
&=& \neg p_{n-i+2}\cdot \neg p_{n-i+3}\cdot S_{n-5}\{
\neg p_{n-i+4},..,\neg p_{n},p_{1},..,p_{n-i-1}\}\cdot
p_{n-i}\cdot p_{n-i+1}\\
&=& \bar{\neg}h_{n-i+2}. 
\end{eqnarray*}
Therefore, $\lambda (\mathrm{Car}F) \subseteq \mathrm{Car}F$. 
\end{proof}
     
\textbf{Proposition 4.5.9}  $F$ in Example 4.5.6 is a
one-to-one threshold transformation, which is reflective through
$\lambda $.
     
\begin{proof} $F$ is clearly a threshold transformation.  To
prove that $F$ is reflective through $\lambda $, we will
show that  (i) $\lambda Ff_{i} \subseteq  \bar{\neg}f_{\lambda
i}$ for every $i$ and (ii) $\lambda F(f_{i}\cup \bar{\neg}f_{i})^{c}
\cap \bar{\neg}f_{\lambda i} = \emptyset $ for every $i$.
     (i)  Let $x \in  f_{i}$ for some $i$.  Then if $2 \leq  i
\leq  n-1$, then
$$
         x_{i}\cdot x_{i+1}\cdot S_{n-4}\{ x_{i+2},..,x_{n},\neg
     x_{1},..,\neg x_{i-2}\} \cdot \neg x_{i-1} = 1.
$$
\begin{eqnarray*}
   \bar{\neg}f_{\lambda i} &=& \bar{\neg}f_{n-i+1} \\
   &=& \neg p_{n-i+1}\cdot \neg p_{n-i+2}\cdot S_{n-4}\{
\neg p_{n-i+3},..,\neg p_{n},p_{1},..,p_{n-i-1}\}\cdot  p_{n-i}.
\end{eqnarray*}
By Lemma 4.5.7, 
$$
     \lambda Fx = (x_{n},..,x_{i+1},\neg x_{i},x_{i-1},..,x_{1}). 
$$
Therefore, 
$$
   f_{\lambda i}\bar{\neg}(\lambda Fx) = x_{i}\cdot \neg
     x_{i-1}\cdot
     S_{n-4}\{ \neg x_{i-2},..,\neg x_{1},x_{n},..,x_{i+2}\}
\cdot x_{i+1} = 1,
$$
that is, $\lambda Fx \in  \bar{\neg}f_{\lambda i}$. 
Similarly, if $x \in  f_{i}$ for $i = 1$ or $n$,
then $\lambda Fx \in \bar{\neg}f_{\lambda i}$. 
     (ii)  Let $x \notin  f_{i}\cup \bar{\neg}f_{i}$.  (iia) If
$x \in f_{j}\cup \bar{\neg}f_{j}$ for some $j \ne  i$ then $\lambda
Fx \in f_{\lambda j}\cup \bar{\neg}f_{\lambda j}$ by (ii),
so that $\lambda Fx \notin  \bar{\neg}f_{\lambda i}$ by
Lemma 4.5.7.  (iib) Let $x \notin f_{j}\cup \bar{\neg}f_{j}$
for every $j$.  Then $x$ is a fixed point of $F$, so that
$\lambda Fx = \lambda x$.  Suppose $\lambda
Fx \in \bar{\neg}f_{k}$ for some $k$.  Then $\lambda x \in 
\bar{\neg}f_{k}$, so that $x = \lambda (\lambda x) \in
\bar{\neg}f_{l}$ for some $l$ by Lemma 4.5.8, which is
a contradiction.  Consequently, by Proposition 3.3.2 of Chapter 3,
$F$ is reflective through $\lambda$.
\end{proof}
     
\textbf{Example 4.5.10}  Let $n = 5$ and $F = \langle\langle
1\cdot 3\cdot 4\cdot (\neg 2\vee \neg 5)\rangle\rangle $. 
$\mathrm{GRAPH}(F)$ consists of three 10-cycles and two
loops.   The flow graph is
$$
     \;    [1\cdot 2\cdot 3\cdot 4\cdot 5]  \leftrightarrow 
[1\cdot
     \neg 2\cdot 3\cdot 4\cdot 5], \quad [1\cdot 2\cdot \neg
3\cdot 4\cdot 5]\partial .
$$
     $F$ is reflective through $\lambda $.\\
     
\textbf{Example 4.5.11}  The following transformations
$\langle\langle f^{(i)} \rangle\rangle$ of $\mathbf{Q}^{i}$
are expected to be one-to-one and reflective through $\lambda $.
\begin{eqnarray*}
    f^{(4)} &=& 1\cdot  2\cdot  (3\vee 4),\quad f^{(6)} =
1\cdot 
     2\cdot  (3\vee 4\cdot  (5\vee 6)),...\\
       f^{(5)} &=& 1\cdot  2\cdot  (3\vee 4\cdot  5),\quad
f^{(7)}
     = 1\cdot  2\cdot  (3\vee 4\cdot  (5\vee 6\cdot  7)),...
\end{eqnarray*}
     
\textbf{Open Question}  All one-to-one minimal threshold
transformations we have so far are reflective through some
isometries of order $2$ as well as all isometries.  Whether
it is true for all minimal one-to-one threshold transformations is
an open question.\\
     
\end{document}
    
 