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

\begin{document}

\title{Chapter 5 Modification of threshold transformations}

\begin{abstract} After the graph structures of self-dual one-to-
one transformations are described, a construction method of
generating minimal one-to-one threshold transformations from
lower dimensional ones through face copies and orbit
modifications are presented.  Theorems that concern one-to-one
threshold transformations and support the method are also proved. 
Then compression and expansion of threshold transformations are
described.  Then in addition to one-to-one threshold
transformations in Chapter 4, some classes of incompressible and
compressible one-to-one threshold transformations are given.  In
particular, all currently known one-to-one minimal incompressible
threshold transformations are proved to be reflective. Finally,
it is proved  that there exists a threshold transformation of $\{
0,1\} ^{n}$ such that for any $1 \leq  k \leq  2^{n}$, its graph
has a $k$-cycle that is the only cycle or loop.  This enhanced
Arimoto theorem has an important implication on dynamical systems
of neural networks described in the remaining chapters. 
\end{abstract}
\maketitle

\section*{5.1 Orbit modification\label{s:OM}}
If $F$ is a threshold transformation, its graph drew considerable
interest in the 1960s and early 70s  (Arimoto, 1963; Masters \&
Mattson; 1966, Ishii, 1970; Ishii \& Miyazaki, 1972; etc.). 
These studies provided some construction procedures for finding a
threshold transformation that satisfies given conditions for its
graph. However, they were mainly concerned with proper subgraphs
of $\mathrm{GRAPH}(F)$ and did not bring out concrete results for
the whole graph structure of a transformation except the ones
given in Arimoto (1963) and Masters \& Mattson (1966).  Since
what characterizes a transformation is its (whole) graph
structure rather than the structure of its particular proper
subgraph, our goal here is to fill part of that vacancy.  In
order to simplify the problem we limit our scope to graphs of
one-to-one transformations and use the results of Chapters 3 and
4, which dealt with reflective transformations and circular
one-to-one threshold transformations.


     We have already proved that a one-to-one threshold
transformation $F$ is self-dual (Theorem 4.3.3 of Chapter 4), so
that $F$ can be represented by $F = [f_{1},...,f_{n}]$, where
$f_{i} = p_{i}\cdot \neg (p_{i}F)$.  Further, by Corollary 4.3.5
of Chapter 4, $F$ is a threshold transformation, if and only if
each $f_{i}$ is a threshold function.

    Theorem 2.3.5 of Chapter 2 completely determines the cycle
structures of one-to-one self-dual transformations.  However,
such a condition for one-to-one threshold transformations is
unknown.  Therefore, it is necessary to try to construct a one-
to-one threshold transformation individually in order to
determine whether a given cycle structure is realized by a
threshold transformation or not.  In this section we prove two
properties concerning face copies of one-to-one threshold
transformations.  Then. based on these results, we discuss a
method of constructing higher dimensional one-to-one threshold
transformations from lower dimensional ones. The method is orbit
modification,
which we applied in Chapter 3.5.  It was part of more general
construction
 procedures given by Ishii \& Miyazaki (1972).  Here we formulate
it in terms
of [\;]-representations.\\

\textbf{Lemma 5.1.1}  Let $M = \{ n+1,...,n+m\}$ and $C \subseteq 
\mathbf{Q}^{M}$ be a complete set.  If $g$ is a threshold
function: $\mathbf{Q}^{n+m} \rightarrow  \mathbf{Q}$ such that $g
= f\cdot 1_{C}$ for some $f: \mathbf{Q}^{\mathbf{N}} \rightarrow 
\mathbf{Q}$ and the characteristic function $1_{C}:
\mathbf{Q}^{M} \rightarrow   \mathbf{Q}$ , then $C =
\mathbf{Q}^{M}$.

\begin{proof}  Let $g =  f\cdot 1_{C}$ be a threshold function. 
Let $q \in g$; then $r = \{ n+1,...,n+m\} ^{-}q \in g$.  If
$q\prime  = (q_{1},..,q_{n},a_{n+1},..,a_{n+m}) \notin  g$ for
some point $(a_{n+1},...,a_{n+m}) \in 
\mathbf{Q}^{\{n+1,...,n+m\}}$, then $r\prime  = \{ n+1,...,n+m\}
^{-}q\prime  \notin  g$.  Since $q+r = q\prime +r\prime $, $g$ is
2-summable, so that we have a contradiction to the fact that $g$
is a threshold function (Corollary 4.2.2 of Chapter 4).
\end{proof}


\textbf{Theorem 5.1.2}  If $G$ is a one-to-one threshold
transformation of $\mathbf{Q}^{n+m}$, and none of the $(n+1)$th,
... and $(n+m)$th coordinates of any point of $\mathbf{Q}^{n+m}$
changes under $G$, then $G$ is the $(n+1,...,n+m)$th face copies
of a
one-to-one threshold transformation of $\mathbf{Q}^{n}$.
 
\begin{proof}  Let $q$ be a point on a cycle of any
transformation $H$ of $\mathbf{Q}^{n+m}$.  For any $i$, if $q$
changes its ith coordinate from 1 to 0 under $H$, then another
point on the same cycle must change its $i$th coordinate from 0
to 1 under $H$.  Moreover, on the same cycle, the number of
points that change their $i$th coordinates from 1 to 0 must be
the same as the number of points that change their $i$th
coordinates from 0 to 1.  Let $M = \{ n+1,...,n+m\}$ and $a$ be a
point of $\mathbf{Q}^{M}$.

    From the given condition, each cycle of $G$ is contained
either in $P_{M}^{-1}a$ or outside $P_{M}^{-1}a$, where $P_{M}$
is the projection function: $\mathbf{Q}^{n+m} \rightarrow 
\mathbf{Q}^{M}$.  Therefore, the number of $q \in  P_{M}^{-1}a$
such that $q$ changes its $i$th coordinate from 1 to 0 under $G$
and the number of $r \in  P_{M}^{-1}a$  such that $r$ changes its
$i$th coordinate from 0 to 1 under $G$ are the same.  Let $G =
[g_{1},..,g_{n},\emptyset ,..,\emptyset ]$; then the number of $q
\in  g_{i}$ such that $P_{M}q = a$ and the number of $r \in 
g_{i}$ such that $P_{M}r = \bar{\neg}a$ are the same.  Let $q$ be
an arbitrary point of $g_{i}$ and $r = M^{-}q$.  If $r \in \neg
g_{i}$, then there exist $q\prime  \in  g_{i}$ and $r\prime  \in
\neg g_{i}$ such that $P_{M}q\prime = \neg P_{M}q$ and $r\prime 
= M^{-}q\prime $.  Hence, $q+q\prime  = r+r\prime $, $q$ and
$q\prime $ are points of $g_{i}$, and $r$ and $r\prime $ are
points of $\neg g_{i}$, so that $g_{i}$ is 2-summable, contrary
to the fact that $g_{i}$ is a threshold function (Corollary 4.2.2
of Chapter 4).  Hence, there exist some $f_{i}:
\mathbf{Q}^{\mathbf{N}}
\rightarrow  \mathbf{Q}$ and a complete set $C_{i} \subseteq 
\mathbf{Q}^{M}$ such that $g_{i} = f_{i}\cdot 1_{Ci}$.  Since
$C_{i} = \mathbf{Q}^{M}$ by Lemma 5.1.1, we have $G = F\times
I_{\mathbf{Q}^{M}}$, where $F = [f_{1},...,f_{n}]$, and $F$ is a
one-to-one threshold transformation.  \end{proof}


\textbf{Theorem 5.1.3}  Let $G$ be a minimal one-to-one threshold
transformation of $\mathbf{Q}^{n+1}$. Then there exists a self-
dual threshold transformation $F$ of $\mathbf{Q}^{n}$ such that
if both $q \in  \mathbf{Q}^{n+1}$ and $(n+1)^{-}q$ change or
neither changes their $i$th coordinate under $G$ for $i =
1,...,n$, then $Gq  = (F\times I_{\mathbf{Q}^{\{n+1\}}})q$. 

\begin{proof}  Let $G = [g_{1},...,g_{n+1}]$.  Let
$$
        f_{i} = (g_{i}|0)\cup (g_{i}|1) \; \mbox{or}\; 
f_{i}
= (g_{i}|0)\cap (g_{i}|1)
$$
for $i = 1,...,n$, where $0,1 \in  \mathbf{Q}^{\{n+1\}}$.  Then
$F = [f_{1},...,f_{n}]$ is a threshold transformation of
$\mathbf{Q}^{n}$ by Corollary 4.2.4 of Chapter 4.  If both a
point
$q \in  \mathbf{Q}^{n+1}$ and $q\prime  = (n+1)^{-}q$ change or
neither changes their $i$th coordinate under $G$ for $i =
1,...,n$, and only one of them changes its $(n+1)$th coordinate,
then $Gq = Gq\prime $, contrary to the fact that $G$ is one-to-
one.  Suppose both $q$ and $q\prime $ change their $(n+1)$th
coordinates.  Then $q \in  g_{n+1}$ and $q\prime  \in
\bar{\neg}g_{n+1}$,
or $q \in  \bar{\neg}g_{n+1}$ and $q\prime  \in  g_{n+1}$. 
By Proposition 4.2.6 of Chapter 4, $|g_{n+1}| \geq  2^{n-1}
+1$; hence $G$ is not minimal, because $\mathrm{Var}((n+1)^{-}G)
< \mathrm{Var}(G)$.  Therefore, neither $q$ nor $q\prime $
changes its $(n+1)$th coordinate, and $F$ satisfies the desired
condition.  \end{proof}

\textbf{Orbit modification}  Theorem 5.1.3 shows that any minimal
one-to-one threshold transformation $G = [g_{1},...,g_{n+1}]$ of
$\mathbf{Q}^{n+1}$ can be constructed from a self-dual threshold
transformation $F = [f_{1},...,f_{n}]$ through its $(n+1)$th
face copies $F\times I_{\mathbf{Q}^{\{n+1\}}} = [f_{1}\circ
P_{\mathbf{N}},..,f_{n}\circ P_{\mathbf{N}},\emptyset ]$;
$g_{i}$ for $i = 1,...,n$
is obtained by adding or deleting a subset of either the face
$\neg p_{n+1}$ or $p_{n+1}$ to or from $f_{i}\cdot
1_{\mathbf{Q}^{\{n+1\}}}$.  Further, $g_{n+1}$ is composed of
$q$, $\bar{\neg}q$, $(n+1)^{-}q$ or $(n+1)^{-}\bar{\neg}q$ for
some of these added or deleted points $q$.  The $(n+1)$th
coordinates of
two of the four are 1, but $g_{n+1}$ can not contain both because
of the minimality of $G$.  By Theorem 5.1.2, $g_{n+1} \ne
\emptyset
$ for $G$ to be one-to-one, unless $G = F\times
I_{\mathbf{Q}^{\{n+1\}}}$.  The method of constructing $G$ from
$F\times I_{\mathbf{Q}^{\{n+1\}}}$ in this way is orbit
modification
described in 3.5.  More generally, we may construct a
new threshold transformation $G$ from $F\times
I_{\mathbf{Q}^{\{n+1,..,n+m\}}}$ by orbit modification.\\
 

\section*{5.2  Expansion and compression}  

let $D = \{D_{1},...,D_{m}\}$ be a partition of $\mathbf{N} =
\mathbf{N}_{n}$, and let $\delta $ be a function from
$\mathbf{N}_{n}$ to $\mathbf{M} = \mathbf{N}_{m}$ defined by
$\delta j = i$ if $j \in  D_{i}$.  Let $\gamma $ be a function
from $\mathbf{M}$ to $\mathbf{N}$ such that $\gamma i$ is a
representative element of $D_{i}$.  Further let $\epsilon $ be a
function from $\mathbf{N} \rightarrow  \{I_{\mathbf{Q}},\neg \}$
such that $\epsilon _{j} = I_{\mathbf{Q}}$ for every
representative element $j \in  \gamma \mathbf{M}$.

     Let the function $H: \mathbf{Q}^{m} \rightarrow 
\mathbf{Q}^{n}$ be defined by
$$
          p_{j}H = \epsilon _{j}p_{\delta j} \quad \mbox{for
every $j \in  \mathbf{N}$.}
\eqno (5.2.1)
$$
Clearly $H$ is an injection. In particular, if $i \in 
\mathbf{M}$ and $j = \gamma i$, then $p_{j}H = p_{\delta j}$,
since $\delta \gamma $ is the identity and $\epsilon _{\gamma i}
= I_{\mathbf{Q}}$ for every $i \in  \mathbf{M}$. Therefore, 
$$
          p_{i} = p_{\gamma i}H for i \in  \mathbf{M}, 
$$
so that $p_{\delta j} = p_{\gamma \delta j}H$.  Therefore, from
(4.2.1),  
$$
          p_{j} = (\epsilon j)p_{\gamma \delta j} \quad \mbox{for
every $j$ on $H\mathbf{Q}^{m}$.}
\eqno (5.2.2)
$$

     Now, given a transformation $F$ of $\mathbf{Q}^{m}$, define
a transformation $E$ of $\mathbf{Q}^{n}$ by
$$
          E = \left\{
\begin{array}{ll}
 HFH^{-1}, & \mbox{on $H\mathbf{Q}^{m}$,}\\                       
        
 \mbox{Identity} & \mbox{on $(H\mathbf{Q}^{m})^{c}$.}
\end{array}
          \right.   
\eqno (5.2.3)
$$
$E$ is caled an \emph{expansion} of $F$.

     Conversely given a transformation $E$ of $\mathbf{Q}^{n}$,
define $i \sim _{F} j$ for $i,j \in  \mathbf{N}$ if $x_{i} =
x_{j}$ for every $x \in  \mathrm{Car}E\cup E(\mathrm{Car}E)$ or
$x_{i} = \neg x_{j}$ for every $x \in  \mathrm{Car}E \cup 
E(\mathrm{Car}E)$.  Clearly $\sim _{F}$ is an equivalence
relation on $\mathbf{N}$.  Let $D = \{D_{1},...,D_{m}\}$ be the
set of all equivalence classes defined by $\sim _{F}$. Let
$\gamma i$ be a representative element of $D_{i}$.  Let $\delta :
\mathbf{N} \rightarrow  \mathbf{M}$ be defined by $\delta j = i$
if $j \in  D_{i}$.  Then $p_{j} = \epsilon _{j}p_{\gamma \delta
j}$ for every $j \in  \mathbf{N}$ on $\mathrm{Car}E \cup 
E(\mathrm{Car}E)$, where $\epsilon _{j} = I_{\mathbf{Q}}$
(matrmidentity) or $\neg $. In particular, $\epsilon _{\gamma i}
= I_{\mathbf{Q}}$ for every $i \in  \mathbf{M}$.  Therefore, the
function $H: \mathbf{Q}^{m} \rightarrow  \mathbf{Q}^{n}$ can be
defined by (5.2.1).  Define the transformation $F$ of
$\mathbf{Q}^{m}$ by
$$
          F = H^{-1}EH.
\eqno (5.2.4)
$$
Then $F$ is well-defined, since $\mathrm{Car}E \cup 
E(\mathrm{Car}E) \subseteq  H\mathbf{Q}^{m}$.  $F$ is called a
\emph{compression} of $E$.  Further, $E$ is called
\emph{compressible},  if $|D_{j}| \geq  2$ for some $j$, and
\emph{incompressible} otherwise.  $F$ is self-dual if and only if
$E$ is self-dual.

     Let $E = [e_{1},...,e_{n}]$, and let $F = [f_{1},...,f_{m}]$
be defined by (5.2.4).  Then,
$$
\begin{array}{lll}
     f_{j} &=& p_{j} \cdot  \neg (H^{-1}EH)_{j}\\
      &=& \epsilon _{\gamma j}p_{\delta \gamma j} \cdot  \neg
(EH)_{\gamma j}\\
          &=& p_{\gamma j}(\epsilon _{1}p_{\delta 1},...,\epsilon
_{n}p_{\delta n})\cdot \neg E_{\gamma j}(\epsilon _{1}p_{\delta
1},...,\epsilon _{n}p_{\delta n})\\
          &=& e_{\gamma j}(\epsilon _{1}p_{\delta 1},...,\epsilon
_{n}p_{\delta n}).
\end{array}
\eqno (5.2.5)
$$

Conversely let $E$ is defined by (5.2.3) from given $F$.  Then,
since (5.2.2) is necessary on $H\mathbf{Q}^{m}$,
$$ 
     e_{i} = p_{i}\cdot \neg E_{i} = p_{i}\cdot \neg (HFH^{-
1})_{i}\cdot \Pi 
_{k\in \mathbf{N}}(p_{k}(=)\epsilon _{k}p_{\gamma \delta k}),
$$                          
and
\begin{eqnarray*}   
p_{i}\cdot \neg (HEH^{-1})_{i} &=& \epsilon _{i}p_{\gamma \delta
i}\cdot \neg \epsilon _{i}(EH^{-1})_{\delta i}\\
          &=& (\epsilon _{i}p_{\delta i}\cdot \neg \epsilon
_{i}F_{\delta i})(p_{\gamma 1},...,p_{\gamma m}) 
\end{eqnarray*}
Therefore,
$$
     e_{i} = \left\{
\begin{array}{ll}   
f_{\delta i}(p_{\gamma 1},..,p_{\gamma m})\cdot \Pi _{k\in
\mathbf{N}}(p_{k}(=)\epsilon _{k}p_{\gamma \delta k}) 
          & \mbox{if $\epsilon _{i} = I_{\mathbf{Q}}$,}\\
\bar{\neg}f_{\delta i}(p_{\gamma 1},..,p_{\gamma m})\cdot \Pi
_{k\in \mathbf{N}}(p_{k}(=)\epsilon _{k}p_{\gamma \delta k})
          & \mbox{if $\epsilon _{i} = \neg $.}
\end{array}
     \right.
\eqno (5.2.6)
$$

\textbf{Example 5.2.1}  Let $\mathbf{M} = \mathbf{N}_{1}$, $F =
[p_{1}]$ be the transformation of $\mathbf{Q}^{\mathbf{M}}$,
$\mathbf{N} = \mathbf{N}_{n}$, $D = \{\mathbf{N}\}$, $\gamma 1 =
1$, and $\epsilon _{i} = I_{\mathbf{Q}}$, for every $i \in 
\mathbf{M}$.  $\mathrm{Car}E  = \{1...1, 0...0\}$, and $Ex =
\bar{\neg}x$.  Therefore, $E = \langle e\rangle $,
$$
          e = p_{1}\cdot p_{2}\cdot \cdot \cdot p_{n}.
$$

\textbf{Proposition 5.2.2}  Let $\mathbf{M} = \mathbf{N}_{m}$ and
$\mathbf{N} = \mathbf{N}_{2m}$, $D = \{D_{1},..,D_{m}\}$, $D_{i}
= \{i,m+i\}$, and $\gamma i = i$, $\epsilon _{m+i} = \neg $ for
every $i$.  Let $F = \langle\langle f\rangle\rangle $,
$$ 
     f = p_{1}\cdot \alpha _{2}p_{2}\cdot ...\cdot \alpha
_{m}p_{m}, \quad \mbox{where $\alpha _{i} = I_{\mathbf{Q}}$ or
$\neg $ for every $i$.}
$$
Then the expansion $E$ of $F$ is $\langle e\rangle $,
$$
     e = p_{1}\cdot \alpha _{2}p_{2}\cdot ...\cdot \alpha
_{m}p_{m}\cdot \neg p_{m+1}\cdot \neg \alpha _{2}p_{m+2}\cdot
...\cdot \neg \alpha _{m}p_{2m}.      
\eqno (5.2.7)
$$
\begin{proof}  Let $\rho _{m}$ be the rotation $(1...m)$ and
$\rho _{2m}$ be the rotation $(1...2m)$.  Let $f = \{x\}$,
$p_{1}x = 1$.  Then, by (5.2.6),
\begin{eqnarray*}
e_{i} &=& \{(\rho _{m}m-)^{i-1}x,\bar{\neg}(\rho _{m}m^{-)i-
1}x)\}\\
     &=& \{(\neg x_{m+2-i},..,\neg x_{m},x_{1},x_{2},..,x_{m+2-
(i+1)})\} \quad \mbox{for $i \in  \mathbf{M}$},\\
e_{i} &=& \{(\bar{\neg}(\rho _{m}m^{-)-(i-m-1)}x,(\rho _{m}m^{-)-
(i-m-1)}x)\}\\   
     &=& \{(x_{2m+2-i},..,x_{m},\neg x_{1},\neg x_{2},..,\neg
x_{2m+2-(i+1)})\} \quad \mbox{for $i \in  \mathbf{N}\backslash
\mathbf{M}$.}\\
\rho _{2m}^{i-1}e_{1} &=& \{(\rho _{2m}^{i-1}(x_{1},..,x_{m},\neg
x_{1},..,\neg x_{m})\}\\
     &=& \{(\neg x_{m+2-i},..\neg x_{m},x_{1},..,x_{m-i+1})\} =
e_i \quad \mbox{for $i \in  \mathbf{M}$,}\\
\rho _{2m}^{i-1}e_{1} &=& \{(\rho _{2m}^{i-1}(x_{1},..,x_{m},\neg
x_{1},..,\neg x_{m})\}\\
     &=& \{(x_{2m+2-i},..x_{m},\neg x_{1},..,\neg x_{2m-i+1})\} =
e_i \quad \mbox{for $i \in  \mathbf{N}\backslash \mathbf{M}$.}
\end{eqnarray*}
Therefore, $e_{i }= \rho _{2m}^{i-1}e_{1}$, that is, $E$ is a
circular ransformation $\langle e\rangle $ defined by (5.2.7).
\end{proof}


\textbf{Example 5.2.3}  The simplest case in proposition 5.2.2 is
when $f = p_{1}\cdot ..\cdot p_{m.}$ Then $E = \langle e\rangle
$,
$$
     e = p_{1}\cdot p_{2}\cdot ...\cdot p_{m}\cdot \neg
p_{m+1}\cdot \neg p_{m+2}\cdot ...\cdot \neg p_{2m}.             
$$
The $2m$-cycle of $E$ is
$$
\begin{array}{ccccccc}
     1...10...0 &\rightarrow & 01...10...0& \rightarrow & ...&
\rightarrow  &0...01...10\\  
        \uparrow &&&&&& \downarrow  \\
     1...10...01  &\leftarrow &     & ...&         &\leftarrow& 
0...01...1
\end{array}
$$
$E$ is uniquely minimal for $m \geq  2$.  

\textbf{Example 5.2.4}  Let $0 < h-1 < 2m$ be relatively prime
with $2m$, and let $F = \langle\langle f\rangle\rangle $ be a
one-to-one skew-circular transformation described in Theorem
4.5.3.  
\begin{eqnarray*}
     f &=& p_{1}\cdot \alpha _{2}p_{2}\cdot ..\cdot \alpha
_{m}p_{m},\\
     F &=& (\rho m^{-})^{h-1} \quad \mbox{on $\mathrm{Car}F$.}
\end{eqnarray*}
Then we obtain the expansion $E = \langle e\rangle $,
$$
     e = p_{1}\cdot \alpha _{2}p_{2}\cdot ..\cdot \alpha
_{m}p_{m}\cdot \neg p_{m+1}\cdot \neg \alpha _{2}p_{m+2}\cdot
..\cdot \neg \alpha _{m}p_{2m}.
$$
Thereore, 
$$
          E = \rho ^{h-1} \quad \mbox{on $\mathrm{Car}E$.}
$$

     As an example, let
$$
          e = 1\cdot 2\cdot \neg 3\cdot 4\cdot -5\cdot -6\cdot
7\cdot \neg 8.
$$
and compare the cycles of F and E.
$$
\begin{array}{ccccccc}
          1101 &\rightarrow & 0101 &\rightarrow & 0100
&\rightarrow & 0110 \\
            \uparrow     &&&&&&                \downarrow   \\
          1001 &\leftarrow & 1011 &\leftarrow & 1010 &\leftarrow
& 0010 \\
     11010010 &\rightarrow & 01011010 &\rightarrow & 01001011
&\rightarrow & 01101001\\
       \uparrow     &&&&&&                             
\downarrow     \\
     10010110 &\leftarrow & 10110100 &\leftarrow & 10100101
&\leftarrow & 00101101 
\end{array}
$$
We have also the following proposition similar to Proposition
5.2.2.

\textbf{Propositin 5.2.5}  Let  $\mathbf{N} = \mathbf{N}_{2m}$, 
$D = \{D_{1},...,D_{m}\}$, $D_{i} = \{i,m+i\}$, $\gamma i = i$,
and $\epsilon (m+i) = I_{\mathbf{Q}}$ for every $i$.
 Let $F = \langle f\rangle $,
$$   
     f = p_{1}\cdot \alpha _{2}p_{2}\cdot ...\cdot \alpha
_{m}p_{m}, \quad \mbox{where $\alpha _{i} = I_{\mathbf{Q}}$ or
$\neg $ for every $i$.}
$$
Then the expamsion $E$ of $F$ is a circular transformation
$\langle e\rangle $,
$$
     e = p_{1}\cdot \epsilon _{2}p_{2}\cdot ...\cdot \epsilon
_{m}p_{m}\cdot p_{m+1}\cdot \epsilon _{2}p_{n+2}\cdot ...\cdot
\epsilon _{m}p_{2m}.
$$

\textbf{Example 5.2.6}  Let $0 < h-1 < m$ be relatively prime
with odd $m$, and let $F = \langle f\rangle $ be a one-to-one
skew-circular transformation described in Theorem 4.4.3. 
\begin{eqnarray*}
     f &=& p_{1}\cdot \alpha _{2}p_{2}\cdot ..\cdot \alpha
_{m}p_{m},\\
     F &=& \bar{\neg}\rho ^{h-1} \quad \mbox{on $\mathrm{Car}F$.}
\end{eqnarray*}
Then we obtain the expansion $E = \langle e\rangle $,
$$
     e = p_{1}\cdot \alpha _{2}p_{2}\cdot ..\cdot \alpha
_{m}p_{m}\cdot p_{m+1}\cdot \alpha _{2}p_{m+2}\cdot ..\cdot
\alpha _{m}p_{2m,}
$$
Therefore,
$$
          E = \bar{\neg}\rho ^{h-1} \quad \mbox{on
$\mathrm{Car}E$.}
$$

In general, if $F$ is a threshold transformation, then its
compression $E$ is also a threshold transformation, but the
converse is not necessarily true.  However, we have the following
theorem.

\textbf{Proposition 5.2.7}  $F$ is a self-dual threshold
transformation if and only if, for its compression $E =
[e_{1},e_{2},..,e_{m}]$ defined by (5.2.2), $e_{j}$ is a
threshold function for every $j$, and for each $l$ such that
$|\mathbf{M}_{t}| \geq  2$ and for each $j$,
$$
          e_{j} \subseteq  p_{t} \quad \mbox{or} \quad e_{j}
\subseteq  \neg p_{t}.
$$
\begin{proof}  Let $F = [f_{1},...,f_{n}]$ be a self-dual
transformation of $\mathbf{Q}^{n}$ and $E = [e_{1},...,e_{m}]$ be
a self-dual transformation of $\mathbf{Q}^{m}$ defined by
(5.2.2).  Suppose that there exist $y, y\prime  \in  e_{j}$ such
that $y_{t} = 0$ and $y\prime _{t} = 1$ for some $t$  such that
$|\mathbf{M}_{t}| \geq  2$.  Then there exists some $s$ such that
$s \ne  \gamma t$ and $t = \delta s$.  Let $i = \gamma j$, $Hy =
x$, and $Hy\prime  = x\prime $.  Then $\delta i = j$.  Also, $x,
x\prime  \in  e_{\delta i}(p_{\gamma 1},..,p_{\gamma m})$, $x_{k}
= \epsilon _{k}x_{\gamma \delta k}$, and $x\prime _{k} = \epsilon
_{k}x\prime _{\gamma \delta k}$ for every $k$, so that $x,
x\prime  \in  f_{i}$ by (5.2.3).  Further,
$$
x_{\gamma t} = y_{t} = 0,\; x\prime _{\gamma t} = 1,\; x_{s} =
\epsilon _{s}y_{\delta s} = \epsilon _{s}y_{t} = \epsilon
_{s}0,\; x\prime _{s} = \epsilon _{s}1.
$$
Let $z$ and $z\prime $ of $\mathbf{Q}^{n}$ be defined as
$$
\begin{array}{lll}
     z_{\gamma t} = 0, & z_{s} = \epsilon _{s}1,& z_{u}  = x_{u}
\;\mbox{for every other $u$;}\\
     z\prime _{\gamma t} = 1,& z\prime _{s} = \epsilon _{s}0,&
z\prime _{u} = x\prime _{u} \;\mbox{for every other $u$.}
\end{array}
$$
  Since $\gamma t \sim _{F} s$, both $z$ and $z\prime $ are fixed
points of $F$, so that they are elements of $\neg f_{i}$. 
However, $x+x\prime  = z+z\prime $ in $R^{n}$, i.e. $f_{i}$ is
$2$-summable, contrary to the fact that $f_{i}$ is a threshold
function.  The "if" part of this theorem is obvious.  
\end{proof}

     As seen from Proposition 5.2.7, an expansion of an
incompressible threshold transformation may be a threshold
transformation or not.  If there exists some  threshold
transformation which is an expansion of a given threshold
transformation, then the given threshold transformation may be
called expansible.  Thus, threshold transformations can be
classified as follows.
$$
\begin{array}{ccc}
     &Threshold transformations&\\
     &      \swarrow \quad    \searrow  &\\
     Compressible & & Incompressible\\
        &&\\
     &Threshold transformations&\\
          &   \swarrow \quad  \searrow  &\\
   Expansible &  & Inexpansible
\end{array}
$$

\section*{5.3 Incompressible transformations\label{s:IT}}
We gave circular and skew-circular threshold transformations in
Sections 4.4 and 4.5.  In this section we try to construct
general, minimal, non-compressible, one-to-one threshold
transformations by orbit modification discussed in Section 5.1,
although I have found only one example except trivial ones, which
are face copies of or isometrically similar to circular or skew-
circular transformations.
   
    In the end of Chapter 4, we raised an open question about
whether all  minimal one-to-one threshold transformations are
reflective through some isometries of order $2$, so that their
inverses are also threshold transformations.  We have not solved
this question, but we will show that all currently known
one-to-one threshold transformations that are minimal and
incompressible are reflective through some isometries of order 2. 
Combined with the result in Chapter 3.2  that any isometry is
reflective through some isometry of order 2, these results
tentatively indicate that one-to-one threshold transformations do
not completely digress from isometries, despite selectiveness for
non-fixed points in the former.  These results also help to find
a one-to-one threshold transformation.
 
Constructing a threshold bijection is in turn a good
preparation for constructing a neural network, since not only
similar methods can be applied to the two subjects, but also a
dynamical neural network having an attractor is often constructed
by modifying a one-to-one threshold transformation, as shown in
Chapters 6 and 7.  In the following, the expression of cycle
structures introduced in Chapter 2.3 is used.\\

\textbf{Example 5.3.1}  Let $n = 2m+2$.  Consider the
transformation $F$ of Example 5.3.2 (3) for dimension $n-1$,
i.e.,
$F = [f,\rho f,...,\rho ^{n-2}f]$, where
\begin{eqnarray*}
        f &=& f_{1}\vee f_{2},\\
        f_{1} &=& p_{1}\cdot \cdot \cdot p_{m+1}\cdot \neg
p_{m+2}\cdot \cdot \cdot \neg p_{2m+1},\\
        f_{2} &=& p_{1}\cdot \cdot \cdot p_{m}\cdot \neg
p_{m+1}\cdot \cdot \cdot \neg p_{2m+1}.
\end{eqnarray*}
The non-fixed points of the $n$th face copies of $F$ form four
$(n-1)$-cycles, for example,
$$
\begin{array}{c}
    111001 \rightarrow 011101 \rightarrow  001111 \rightarrow 
100111 \rightarrow  110011 \rightarrow  111001,\\
    110001 \rightarrow 011001 \rightarrow  001101 \rightarrow 
000111 \rightarrow  100011 \rightarrow  110001,\\
    111000 \rightarrow 011100 \rightarrow  001110 \rightarrow 
100110 \rightarrow  110010 \rightarrow  111000,\\
    110000 \rightarrow  011000 \rightarrow  001100 \rightarrow 
000110 \rightarrow  100010 \rightarrow  110000.
\end{array}
$$

Since $F$ is reflective through the linear permutation $\nu $ of
coefficients $(-1,n)$, i.e. $\nu  = (1,n-1)(2,n-2)\cdot \cdot
\cdot (n/2-1, n/2+1)$, its $n$th face copies are also reflective
through $\nu $ by Proposition 3.5.1 (i) of Chapter 3.  Let $c$ be
the point defined by $c_{i} = 1$ for $1 \leq   i \leq   n/2 - 1$,
$c_{i} = 0$ for $n/2 \leq  i \leq  n-1$, and $c_{n} = 1$, and let
$d$ be the point defined by $d_{i} = 1$ for $1 \leq   i \leq  
n/2$, and $d_{i} = 0$ for $n/2+1 \leq  i \leq  n$  ($c = 110001$,
$d = 111000$ in this example).  Then applying Proposition 3.5.4
of
Chapter 3, we obtain
\begin{eqnarray*}
      G &=& [g_{1},...,g_{n}],\\
      g_{i} &=& \rho ^{i-1}f_{1}\vee \rho ^{i-1}f_{2}\cdot \neg
p_{n} \; \mbox{for}\;  i = 1,...,m+1,\\
      g_{i} &=& \rho ^{i-1}f_{1}\cdot p_{n}\vee \rho ^{i-1}f_{2}
\; \mbox{for}\;  i = m+2,...,2m+1,\\
      g_{n} &=& f_{2}\cdot p_{n}.
\end{eqnarray*}
$G$ is a threshold transformation, since $g_{i}$ is a threshold
function for every $i$. $F$  is reflective through $\nu $,
incompressible, inexapansible, and
$$
        \mathrm{CS}(G) = \{ (1,n), (2,n-1), (2^{n}-3n+2,1)\} .
$$
In the above example, the four cycles are changed into
$$
\begin{array}{ccccccccccc}
111001& \rightarrow & 011101& \rightarrow & 001111& \rightarrow &
100111& \rightarrow & 110011& \rightarrow & 111001,\\
110001&  &  &  &  &  &  000111& \rightarrow & 100011& \rightarrow
& 110001,\\
 \downarrow &   &   &   &   &    \nearrow  &   &   &   &   &\\
111000& \rightarrow & 011100& \rightarrow & 001110&  &  &  &  & 
&\\
110000& \rightarrow & 011000& \rightarrow & 001100& \rightarrow &
000110& \rightarrow & 100010& \rightarrow & 110000.
\end{array}
$$


As described above, all one-to-one minimal threshold
transformations we have found so far, including $G$ in the above
Example 5.3.1, are reflective through some Boolean isometries of
order 2.  However, there exists a compressible, minimal,
one-to-one threshold transformation that is not reflective, as
given in the following Example 5.3.2.  On the other hand, there
exists an incompressible, non-minimal, one-to-one threshold
transformation that is not reflective, as given in the following
Example 5.3.3.  Therefore, incompressibility as well as
minimality is necessary for the conjecture.\\

\textbf{Example 5.3.2} (Minimal, compressible, non-reflective
one-to-one threshold transformation).
  $n = 6$. $F = [f_{1},\ldots,f_{6}]$,
  \begin{eqnarray*}
  f_{1} &=& 1\cdot \neg 2\cdot \neg 3\cdot \neg 4\cdot (\neg
  5\vee \neg 6),\\
  f_{2} &=& 1\cdot 2\cdot \neg 3\cdot \neg 4\cdot (\neg 5\vee
  \neg 6),\\                            
  f_{3} &=& f_{4} = 1\cdot 2\cdot 3\cdot 4\cdot (\neg 5\vee \neg
  6),\\
  f_{5} &=& f_{6} = 1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6.
  \end{eqnarray*}
  $F$ is compressible, since $3 \sim_{F} 4$. Suppose $F$ is
  reflective through $\tau J^-$.  Since $|f_1|=|f_2|=|f_3|=|f_4|
  = 3$ and $|f_5| = |f_6|= 1$, $\tau \{ 5,6 \}=\{ 5,6 \}$ by
Corollary 3.3.3 of Chapter 3.  Since $f_6 \ni 111111 \to_F
111100$,
  $J=\{ 1,2,3,4 \}$ by Proposition 3.3.2 (i),(ii) of Chapter 3.
However,
  $$
  f_2 \ni 110000 \to_F 100000 \to_{J^-} 011100 \to_\tau x \notin 
  f_{\tau 2},
  $$
  which contradicts Proposition 3.3.2 (i) of Chapter 3.\\

\textbf{Example 5.3.3}
 (Non-minimal, incompressible, non-reflective one-to-one
threshold transformation).
Let $G = \langle\langle g\rangle\rangle$ , $g = p_1\cdot p_2 \cdot 
p_3\cdot p_4$, on $\mathbf{Q}^4$.  Let $F = (3,4)1^{-}G$.  Then
 Then $F = [f_{1},f_{2},f_{3},f_{4}]$, 
  \begin{eqnarray*}
   f_{1} &=& 1\cdot (\neg 2\vee \neg 3\vee \neg 4),\\
   f_{2} &=& \neg 1\cdot 2\cdot 3\cdot 4,\\
   f_{3} &=& (\neg 1\vee \neg 2)\cdot 3\cdot \neg 4,\\
   f_{4} &=& (\neg 1\cdot \neg 2\vee \neg 3)\cdot 4.
  \end{eqnarray*}
  Then $|f_{1}| = 7$, $|f_{2}| = 1$, $|f_{3}|  = 3$, $|f_{4}| =
  5$.  Suppose that $F$ is reflective through $T = \tau  J^{-}$. 
  Then $\tau  = \iota $ by Corollary 3.3.3 of Chapter 3.  On the
other hand, $\{ 0000,1111 \}$ is the set of fixed points of $F$. 
  Therefore, $J = \emptyset$ or $J = \mathbf{N}_{4}$.  In either
case, $F^{2} = I$, which is not true.  Therefore, $F$ is not
reflective through any Boolean isometry.\\


\section*{5.4 Compressible transformations\label{s:ComT}}
We gave circular, compressible, threshold transformations in
Section 5.2.  In this section we seek general, compressible
minimal, threshold transformations constructed by orbit
modification described in Section 5.1.  First, we determine the
cycle structures of threshold transformations obtained by
expansion from the skew-circular transformation of Example
5.3.2.\\

\textbf{Proposition 5.4.1}  For any $n$ and even $k$ such that $k
\leq  2n$, the cycle structure $\{ (1,k),(2^{n}-k,1)\}$ is
realized
by a threshold transformation.

\begin{proof}  Let           
$$
f_{i} =
\left\{
    \begin{array}{ll}
         x_{1}\cdot \cdot \cdot x_{i}\cdot \neg x_{i+1}\cdot
\cdot \cdot \neg x_{n} & \mbox{for $i \leq  k/2 - 1$},\\
         x_{1}   x_{n} & \mbox{for $i \geq  k/2$}. 
    \end{array}
\right.    
$$
Then $F = [f_{1},...,f_{n}]$ realizes the desired cycle
structure.  E.g. if $n = 5$, and $k = 6$, then 
$$
\begin{array}{l}
    11111 \rightarrow  11000 \rightarrow 10000 \rightarrow 
00000\\
      \qquad \rightarrow 00111 \rightarrow  01111 \rightarrow 
11111.
\end{array}
$$
\end{proof}

The $n$-dimensional $F$ of Proposition 5.4.1 is obtained from the
$n$th face copies of the $(n-1)$-dimensional $F$ by orbit
connection.  Note that $i\sim _{F}j$ for every $i,j \in  \{
k/2,k/2+1,..,n\}$.      

    Proposition 5.4.1 can be further generalized into the
following
proposition.\\

\textbf{Proposition 5.4.2}  If $n \geq  4$ is even, then the
cycle
structure $\{ (1,n),(2,n-2),(2^{n}-3n+4,1)\}$ is realized by a
threshold transformation.

\begin{proof}  Let $n = 2m+2$.  Consider the transformation of
Example 4.4.2 of Chapter 4 for $\mathbf{Q}^{2m}$.  Specifically,
$F =
[f,\rho f,...,\rho ^{2m-1}f]$, where
$$
        f = p_{1}\cdot p_{2}\cdot \cdot \cdot p_{m}\cdot \neg
p_{m+1}\cdot \cdot \cdot \neg p_{2m}.
$$
From the $(2m+1,2m+2)$th face copies of $F$ through orbit
connection, we obtain $G = [g_{1},...,g_{2m+2}]$, where
\begin{eqnarray*}
    g_{i} &=& (\rho ^{i-1}f)\cdot (\neg p_{2m+1}\vee \neg
p_{2m+2}) \; \mbox{for $i =1,...,m$},\\ 
    g_{i} &=& (\rho ^{i-1}f)\cdot (p_{2m+1}\vee p_{2m+2}) \mbox{
for $i = m+1,...,2m$},\\
    g_{2m+1} &=& g_{2m+2} = f\cdot p_{2m+1}\cdot p_{2m+2}.
\end{eqnarray*}
The threshold transformation $G$ realizes the desired cycle
structure.  E.g.
$$
\begin{array}{l}
        1000 \rightarrow  0100 \rightarrow  0111 \rightarrow 
1011 \rightarrow  1000,\\
          1010 \rightarrow 0110 \rightarrow  1010,\\
        1001 \rightarrow 0101 \rightarrow  1001.
\end{array}
$$
\end{proof}

\textbf{Proposition 5.4.3}  For any $n, m$ and even $k$ such that
$1 \leq  m < n$ and $k \leq  2m$, the cycle structure $\{
(1,k+2),(2^{n-m}-2,k), (2^{n}-k2^{n-m}+k-2,1)\}$ is realized by a
threshold transformation.

\begin{proof}  Let the $m$-dimensional threshold transformation
of Proposition 5.4.1 be $[f_{1},...,f_{m}]$.  If $G =
[g_{1},...,g_{n}]$ is defined as
$$
    g_{i} = \left\{
  \begin{array}{ll}
       f_{i} (\neg p_{m+1}\vee ...\vee \neg p_{n}) & \mbox{for}\; 
i = 1,...,m,\\
      p_{i}   p_{n} & \mbox{for}\;  i = m+1,...,n,
  \end{array}
\right.
$$
then $G$ realizes the desired cycle structure.  E.g. if $n = 5$,
$m = 3$ and $k = 4$, then
$$
\begin{array}{l}
    10000 \rightarrow  00000 \rightarrow  00011 \rightarrow 
01111\\
               \qquad \rightarrow  11111 \rightarrow  11100
\rightarrow  10000,\\
    10001 \rightarrow  00001 \rightarrow  01101 \rightarrow 
11101 \rightarrow  10001,\\
    10010 \rightarrow  00010 \rightarrow  01110 \rightarrow 
11110 \rightarrow  10010,\\
 01110 \rightarrow  11110 \rightarrow 10010 \rightarrow 
00010 \rightarrow  01110,\\
    01101 \rightarrow  11101 \rightarrow 10001 \rightarrow 
00001 \rightarrow  01101.
\end{array}
$$
\end{proof}

\section*{5.5 An enhanced Arimoto theorem\label{s:EAThm}}
Arimoto's theorem (1963, Theorem 2, p. 20) proved that for any
positive integer $k$ such that $k \leq  2^{n}$, there exists a
threshold transformation $F$ of $\mathbf{Q}^{n}$ such that the
graph of $F$ has a $k$-cycle as its subgraph.  Here we prove a
stronger theorem using [\;]-representations of self-dual
threshold transformations and construction methods introduced in
Ueda (1992).  Unlike Arimoto (1963), the present more
combinatorial and simpler proof does not require the concept of
\emph{bordering points} and the construction of weight matrices
and threshold vectors.\\

A special case of orbit modification is used in the proof of the
next theorem.
It was first introduced by Arimoto (1963).\\
 
     Consider a self-dual transformation $F = [f_{1},..,f_{n}]$
 of $\mathbf{Q}^{n}$.   Let $q$ be a point of $\mathbf{Q}^{n}$. 
We modify $f_{i}$
 into $g_{i}$ for each $i$ in the following way.    If $q_{i}=
1$, then let $g_{i} = f_{i}\cup q$ if $q \notin f_{i}$, and let
$g_{i} = f_{i}\backslash q$
if $q \in   f_{i}$.  If $q_{i} = 0$ then let $g_{i} = f_{i}\cup
\bar{\neg}q$ if $\bar{\neg}q
\notin f_{i}$, and let $g_{i} =  f_{i}\backslash \bar{\neg}q$ if
$\bar{\neg}q \in  f_{i}$. 
We have $Gq = \bar{\neg}Fq$, $G(\bar{\neg}q) = Fq$, and $Gx = Fx$
for every other
$x$ for $G = [g_{1},..,g_{n}]$ thus constructed.   Let $C$ be the
cycle or loop on which
$q$ is located, and let $k$ be the length of $C$.  If
$\bar{\neg}\mathbf{C} = \mathbf{C}$
then $C$ is divided into two new $k/2$-cycles.  If
$\bar{\neg}\mathbf{C} = \mathbf{D}$
for another $k$-cycle $D$, then $C$ and $D$ are united into one
new  $2k$-cycle.  These
situations are illustrated in Figs. 1  and 2.  In particular, $G$
is one-to one, if $F$ is
one-to-one.  However,  If $F$ is a threshold transformation, $G$
is not a threshold
transformation except in special cases, since $g_{i}$ are not
necessarily threshold functions. 
The self-dual transformation $G$ is called Arimoto's orbit
modification of $F$ at $q$. \\
$$
\begin{array}{ccccccccccccc}
&&   \circ &\rightarrow& \circ& \rightarrow&  q& \rightarrow&  r&
\rightarrow& \circ&
& \\
&&&&     \uparrow &&&&&&            \downarrow&&\\
&&&&       \circ& \leftarrow &\bar{\neg}r& \leftarrow&
\bar{\neg}q& \leftarrow& \circ&
\leftarrow& \circ  \\
&&&&&&  \Downarrow &&&&&&\\
\circ& \rightarrow& \circ& \rightarrow&  q& &&&  r& \rightarrow
&\circ&&\\
&&  \uparrow& &   \downarrow&&&&  \uparrow& &  \downarrow&&\\
&&    \circ& \leftarrow& \bar{\neg}r&&&&     \bar{\neg}q&
\leftarrow& \circ&
\leftarrow&\circ
\end{array}
$$ 
\begin{center}\textbf{Fig. 1}\end{center}
$$
\begin{array}{ccccccccccccc}
\circ& \rightarrow& \circ& \rightarrow&  q& &&&  r& \rightarrow
&\circ&&\\
&&  \uparrow& &   \downarrow&&&&  \uparrow& &  \downarrow&&\\
&&  \circ& \leftarrow& \bar{\neg}r&&&& \bar{\neg}q& \leftarrow&
\circ&
\leftarrow&\circ\\
&&&&&&  \Downarrow &&&&&&\\
&&   \circ &\rightarrow& \circ& \rightarrow&  q& \rightarrow&  r&
\rightarrow& \circ&
& \\
&&&&     \uparrow &&&&&&            \downarrow&&\\
&&&&       \circ& \leftarrow &\bar{\neg}r& \leftarrow&
\bar{\neg}q& \leftarrow& \circ&
\leftarrow& \circ 
\end{array}
$$  
\begin{center}\textbf{Fig. 2}\end{center}

\textbf{Theorem 5.5.1} (Arimoto, 1963)  There exist a threshold
transformation $F$ of $\mathbf{Q}^{n}$ such that
$\mathrm{GRAPH}(F)$ consists of one $2^{n}$-cycle, i.e. a
Hamiltonian cycle.

\begin{proof}  We construct a desired $F$ by iterating copying
and Arimoto's orbit modification.
(1) For $n = 1$, one 2-cycle is realized by the 
transformation $F = [f_{1}]$, $f_{1} = \{ 1\} = p_{1}$.
$\mathrm{GRAPH}(F)$ is
$$
        1 \rightarrow  0 \rightarrow  1. 
$$
(2) For $n = 2$, two 2-cycles are realized by the face copies $F
=
[f_{1},f_{2}]$,
$f_{1} = p_{1}$, $f_{2} = \emptyset $. $\mathrm{GRAPH}(F)$ is
$$
\begin{array}{c}
        11 \rightarrow 01 \rightarrow  11,\\
        00 \rightarrow 10 \rightarrow  00.
\end{array}
$$
(3) For $n = 2$, one $2^{2}$-cycle is realized by $F =
[f_{1},f_{2}]$, which is Arimoto's orbit modification at $11$,
\begin{eqnarray*}
   f_{1} &=& p_{1}\backslash 11 = p_{1}\cdot \neg p_{2},\\
   f_{2} &=& \{ 11\} = p_{1}\cdot p_{2},
\end{eqnarray*}
where $\backslash 11$ means the deletion of $11$. 
$\mathrm{GRAPH}(F)$ is now
$$
\begin{array}{ccccc}
       11&    &    01&  \rightarrow& 11.\\
 \downarrow& & \uparrow & & \\  
     10& \rightarrow& 00&  & 
\end{array}
$$
(4) For $n = 3$, two $2^{2}$-cycles are realized by $F =
[f_{1},f_{2},f_{3}]$,
\begin{eqnarray*}
    f_{1} &=& p_{1}\cdot \neg p_{2}, \\
    f_{2} &=& p_{1}\cdot p_{2}, \\
    f_{3} &=& \emptyset .
\end{eqnarray*}
$\mathrm{GRAPH}(F)$ is
$$
\begin{array}{c}
        111 \rightarrow 101 \rightarrow  001 \rightarrow  011
\rightarrow  111,\\
        000 \rightarrow 010 \rightarrow  110 \rightarrow  100
\rightarrow  000.
\end{array}
$$
(5) For $n = 3$, one $2^{3}$-cycle is realized by $F =
[f_{1},f_{2},f_{3}]$,
\begin{eqnarray*}
        f_{1} &=& (p_{1}\cdot \neg p_{2})\cup 111 = p_{1}\cdot
(\neg p_{2}\vee p_{3}),\\
        f_{2} &=& (p_{1}\cdot p_{2})\backslash 111 = p_{1}\cdot
p_{2}\cdot \neg p_{3},\\
        f_{3} &=& \{ 111\} = p_{1}\cdot p_{2}\cdot p_{3}, 
\end{eqnarray*}
where $\cup 111$ means the addition of 111. $\mathrm{GRAPH}(F)$
is 
$$
\begin{array}{ccccccccccccc}
   111& & & & & & 101& \rightarrow & 001& \rightarrow & 011&
\rightarrow & 111.\\
    \downarrow & & & & & & \uparrow & & & & & & \\
  010& \rightarrow & 110& \rightarrow & 100& \rightarrow & 000& &
& & & &
\end{array}
$$
In general, if one $2^{k}$-cycle
$$
    1^{k} = x^{(1)} \rightarrow  x^{(2)} \rightarrow  ...
\rightarrow  x^{(2^{k})} \rightarrow  x^{(1)}
$$
is realized by $F = [f_{1},..,f_{k}]$, then two $2^{k}$-cycles
$$
\begin{array}{ccccccccc}
  1^{k+1} =  x^{(1)}1&   \rightarrow &  x^{(2)}1& \rightarrow &
...& \rightarrow &  x^{(2^{k})}&   \rightarrow &   x^{(1)}1,\\ 
  0^{k+1} = (\mathbf{N}_k^{-}x^{(1)})0& \rightarrow &
(\mathbf{N}_k^{-}x^{(2)})0&
\rightarrow & ...& \rightarrow & (\mathbf{N}_k^{-}x^{(2^{k})})0&
\rightarrow & (\mathbf{N}_k^{-}x^{(1)})0 
\end{array}
$$
are realized by $F\prime  = [f_{1}\circ
P_{\mathbf{N}_k},..,f_{k}\circ
P_{\mathbf{N}_k},\emptyset ]$.  Here $1^{k} = 1\cdot \cdot \cdot
1 \in 
\mathbf{Q}^{k}$ and $0^{k+1} = 0\cdot \cdot \cdot 0 \in 
\mathbf{Q}^{k+1}$.  Therefore, one $2^{k+1}$-cycle
$$
\begin{array}{ccccccccccccccc}
x^{(1)}1&  &  &  &  &  &  x^{(2)}1& \rightarrow &
x^{(3)}1&\rightarrow& \ldots&
\rightarrow & x^{(2^{k})}1&\rightarrow &x^{(1)}1,\\
 \downarrow & & & & & & & \nwarrow & & & &&&&\\
(\bar{\neg}x^{(2)})0&\rightarrow& (\bar{\neg}x^{(3)})0&
\rightarrow&
\ldots& \rightarrow& (\bar{\neg}x^{(2^{k})})0& \rightarrow&
(\bar{\neg}x^{(1)})0&  &  &
& & & 
\end{array}
$$
is realized by a self-dual transformation $G$ such that
$G(x^{(1)}1) = \bar{\neg}F\prime
(x^{(1)}1)$ and $G(x^{(j)}1) = F\prime (x^{(j)}1)$ for every $j
\ne 1$.  This $G = [g_{1},..,g_{k+1}]$ can be defined by
$$
    g_{i} = \left\{
  \begin{array}{ll}
     f_{i}\circ P_{\mathbf{N}_k}\backslash 1^{k+1} & \mbox{if}\; 
1^{k+1} \in  f_{i}\circ
P_{\mathbf{N}_k},\\ 
     f_{i}\circ P_{\mathbf{N}_k}\cup 1^{k+1} & \mbox{if}\; 
1^{k+1} \notin  f_{i}\circ
P_{\mathbf{N}_k},\\
     g_{k+1} = \{ 1^{k+1} \} &.
  \end{array}
\right.
$$
Further, if $1^{k} \in  f_{i}$ then $1^{k+1} \in  f_{i}\circ
P_{\mathbf{N}_k}$; if $1^{k}
\notin  f_{i}$ then $1^{k+1} \notin  f_{i}\circ
P_{\mathbf{N}_k}$.  Therefore, if $1^{k}
\in  f_{k}$, $1^{k} \notin  f_{k-1}$, $1^{k} \in 
f_{k-2}$, and $1^{k} \notin  f_{k-3}$,..,for $F$, then $g_{k} =
f_{k}\circ
P_{\mathbf{N}_k}\backslash 1^{k+1}$, $g_{k-1} = f_{k-1}\circ
P_{\mathbf{N}_k}\cup
1^{k+1}$, $g_{k-2} = f_{k-2}\circ P_{\mathbf{N}_k}\backslash
1^{k+1}$, $g_{k-3} =
f_{k-3}\circ P_{\mathbf{N}_k}\cup 1^{k+1}$, ... 
  
    By repeating the above process of constructing $G$ from $F$,
we obtain $F =
[f_{1},..,f_{n}]$,
\begin{eqnarray*}
    f_{1} &=& \left\{
 \begin{array}{l}
  p_{1}\cdot (\neg p_{2}\vee p_{3}\cdot (\neg p_{4}\vee
p_{5}\cdot (\neg p_{6}\vee p_{7}\cdot 
                (..\cdot (\neg p_{n-4}\vee p_{n-3}\cdot (\neg
p_{n-2}\vee p_{n-1}\cdot \neg p_{n}))..)\\
                         \qquad  \mbox{if $n$ is even,}\\
  p_{1}\cdot (\neg p_{2}\vee p_{3}\cdot (\neg p_{4}\vee
p_{5}\cdot (\neg p_{6}\vee ..\vee p_{n-4}\cdot (\neg p_{n-3}\vee
p_{n-2}\cdot (\neg p_{n-1}\vee p_{n}))..)\\
               \quad \mbox{if $n$ is odd,}
\end{array}
      \right.\\
     & &. . . .\\
f_{n-3} &=& p_{1}\cdot \cdot \cdot p_{n-3}\cdot (\neg p_{n-2}\vee
p_{n-1}\cdot \neg p_{n}),\\
   f_{n-2} &=& p_{1}\cdot \cdot \cdot p_{n-2}\cdot (\neg
p_{n-1}\vee p_{n}),\\
   f_{n-1} &=& p_{1}\cdot \cdot \cdot p_{n-1}\cdot \neg p_{n},\\
   f_{n} &=& p_{1}\cdot \cdot \cdot p_{n}.
\end{eqnarray*}
$\mathrm{GRAPH}(F)$ consists of one $2^{n}$-cycle, and $f_{i}$ is
a threshold function
for every $i$ by Proposition 4.1.2 of Chapter 4 (Read these
equations upward from the bottom
and backward from the right).
\end{proof}

The next tables illustrate the process of creating $F$ for $n =
3$ in the
proof of Theorem 5.5.1.  In
the tables, each left column shows $f_{1},..,f_{n}$, and each
right column shows $\bar{\neg}f_{1},
\bar{\neg}f_{2},..,\bar{\neg}f_{n}$, where a function
$f$ is expressed by $f^{-1}1$, and *
denotes $\{ 0,1\} $.\\

$$
\begin{tabular}{l|l}
 $1$ &  $0$
\end{tabular}
\;\rightarrow \;
\begin{tabular}{l|l}
   $1*$ &  $0*$ \\ \hline
   $\emptyset$  & $\emptyset$ 
\end{tabular}
\;\rightarrow \;
\begin{tabular}{l|l}
   $1*\backslash 11$&  $0*\backslash 00$\\ \hline
     $11$ &   $00$ 
 \end{tabular}
= \begin{tabular}{l|l}
   $10$ &  $01$ \\ \hline
    $11$ &   $00$ 
 \end{tabular}
$$
$$
\rightarrow \;
 \begin{tabular}{l|l}
   $10*$ &  $01*$ \\ \hline
   $11*$ &  $00*$ \\ \hline
   $\emptyset$  & $\emptyset$  
\end{tabular}
\;\rightarrow\;
\begin{tabular}{l|l}
    $10*\cup 111$ &  $01*\cup 000$ \\ \hline
    $11*\backslash 111$ &  $00*\backslash 000$ \\ \hline
   $111$ &  $000$ 
\end{tabular}
= \begin{tabular}{l|l}
    $10*$&  $01*$ \\
    $111$&  $000$ \\ \hline
    $110$&  $001$ \\ \hline
   $111$ &  $000$ 
\end{tabular}
$$


\textbf{Theorem 5.5.2} (Ueda, 1997)  There exists a threshold
transformation $H$ of $\mathbf{Q}^{n}$ such that for any $k \leq 
2^{n}$, $\mathrm{GRAPH}(H)$ has a $k$-cycle that is the only
cycle or loop. 
   
\begin{proof}  Consider the one-to-one self-dual threshold
transformation $F = [f_{1},..,f_{n}]$ of $\mathbf{Q}^{n}$
constructed in the proof of Theorem 5.5.1 such that
$\mathrm{GRAPH}(F)$ consists of one $2^{n}$-cycle, which is
$$
        1^{n} = x^{(1)} \rightarrow  x^{(2)} \rightarrow  ...
\rightarrow  x^{(2^{n})} \rightarrow  x^{(1)}. 
$$
Let $F\prime $ be the transformation of $\mathbf{Q}^{n+1}$
defined by $F\prime  = [f_{1}\circ P_{\mathbf{N}},..,f_{n}\circ
P_{\mathbf{N}},\emptyset ]$.  Then 
$$
\begin{array}{ccccccccccc}
    1^{n+1} & =&  x^{(1)}1& \rightarrow & x^{(2)}1& \rightarrow &
...& \rightarrow &  x^{(2^{n})}1& \rightarrow & x^{(1)}1,\\
    0^{n+1}& =& (\bar{\neg}x^{(1)})0& \rightarrow &
(\bar{\neg}x^{(2)})0&
\rightarrow & ...& \rightarrow & (\bar{\neg}x^{(2^{n})})0&
\rightarrow
& (\bar{\neg}x^{1})0 
\end{array}
$$
are the two $2^{n}$-cycles of $F\prime $.  The modification
$x^{(1)}1 \rightarrow  x^{(j)}1$ and $(\bar{\neg}x^{(1)})0
\rightarrow 
(\bar{\neg}x^{(j)})0$ changes $\mathrm{GRAPH}(F\prime )$ into
$$
\begin{array}{ccccccccccc}
  x^{(2)}1& \rightarrow& \ldots& \rightarrow & x^{(j-1)}1& & & &
& & \\
 & & &  & \downarrow& & & & & & \\    
 & & x^{(1)}1& \rightarrow & x^{(j)}1& \rightarrow& \ldots&
\rightarrow & x^{(2^{n})}1& \rightarrow & x^{(1)}1,\\
 (\bar{\neg}x^{(2)})0& \rightarrow& \ldots& \rightarrow &
(\bar{\neg}x^{(j-1)})0 & & & & & & \\ 
 & & & & \downarrow& & & & & &\\     
 & & (\bar{\neg}x^{(1)})0& \rightarrow & (\bar{\neg}x^{(j)})0&
\rightarrow& \ldots& \rightarrow& (\bar{\neg}x^{(2^{n})})0&
\rightarrow
& (\bar{\neg}x^{(1)})0,
\end{array}
$$
which has two $(2^{n}-j+2)$-cycles that are the only cycles or
loops. $F\prime $ has been changed by this modification into $G =
[g_{1},..,g_{n},\emptyset ]$, where
$$
    g_{i} = \left\{
  \begin{array}{ll}
   f\prime _{I}  &  \mbox{if}\;  x^{(2)}_{i} = x^{(j)}_i,\\ 
   f\prime _{I}\cup 1^{n+1} &  \mbox{if}\;  x^{(2)}_{i} = 1
\mbox{and } x^{(j)}_{i} = 0,\\
   f\prime _{i}\backslash 1^{n+1} &  \mbox{if}\;  x^{(2)}_{i} = 0
\; \mbox{and}\;  x^{(j)}_{i} = 1. 
  \end{array}
\right.
$$
As shown in the proof of Theorem 5.5.1, $g_{i}$ is a threshold
function for every $i$.  Let the transformation $H$ of
$\mathbf{Q}^{n}$ be defined by
$$
        H_{i}(x_{1},..,x_{n}) = G_{i}(x_{1},..,x_{n},1)
$$
for $i = 1,..,n$.  Then $H$ is a threshold transformation by
Proposition 4.3.6 of Chapter 4.  Further, $\mathrm{GRAPH}(H)$ is 
$$
\begin{array}{ccccccccccc}
 x^{(2)}& \rightarrow& \ldots& \rightarrow& x^{(j-1)}& & & & 
& & \\
 & & & &  \downarrow& & & & & & \\
& & x^{(1)}& \rightarrow& x^{(j)}& \rightarrow& \ldots&
\rightarrow& x^{(2^{n})}& \rightarrow& x^{(1)},
\end{array}
$$
which has one $(2^{n}-j+2)$-cycle, and this cycle is the only
cycle or loop.
\end{proof}

The next tables illustrate the process of creating $H$ for $n =
3$ having one 5-cycle in the proof of Theorem 5.5.2.\\

$$
\begin{array}{ccc}
 F\prime :
\begin{tabular}{l|l}
   $10**$&  $01**$ \\
   $111*$&  $000*$ \\ \hline
    110*&  $001*$ \\ \hline 
    $111*$&  $000*$ \\ \hline
   $\emptyset$  & $\emptyset$    
\end{tabular}
& \rightarrow &
G:
\begin{tabular}{l|l}
   $10**$&  $01**$ \\
   $111*$&  $000*$ \\ \hline
    $110*$&  $001*$ \\ 
    $1111$&  $0000$ \\ \hline 
    $111*$&  $000*$ \\ \hline
    $\emptyset$  & $\emptyset$    
\end{tabular}
\end{array}
$$

$\mathrm{GRAPH}(G)$ is
$$
\begin{array}{ccccccccccccc} 
 0101& \rightarrow & 1101& \rightarrow & 1001& & & & & & & &\\
   &  &  &  & \downarrow & & & & & & & & \\
   &  & 1111& \rightarrow & 0001& \rightarrow & 1011&
\rightarrow & 0011& \rightarrow & 0111& \rightarrow & 1111,\\
 1010& \rightarrow & 0010& \rightarrow & 0110& & & & & & & &\\ 
  &  &  &  & \downarrow &  & & & & & & & \\     
  & & 0000& \rightarrow & 1110& \rightarrow & 0100&
\rightarrow & 1100& \rightarrow & 1000& \rightarrow & 0000.
\end{array}
$$

$\mathrm{GRAPH}(H)$ is
$$
\begin{array}{ccccccccccccc}
 010& \rightarrow & 110& \rightarrow & 100& & & & & & & & \\
     &  &  & &  \downarrow & & & & & & & & \\
    & & 111& \rightarrow & 000& \rightarrow & 101&
\rightarrow & 001& \rightarrow & 011& \rightarrow & 111.
\end{array}
$$

\end{document}


