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

\begin{document}
\title{Chapter 2 Representations of basic Boolean
transformations}
\begin{abstract}
Orthogonal transformations of $\{ -1,1\} ^{n}$ are
restrictions to $\{ -1,1\} ^{n}$ of orthogonal
transformations of the real $n$-dimensional space
$\mathbf{R}^{n}$ that map $\{ -1,1\} ^{n}$ onto itself. 
Corresponding equivalent transformations of $\{ 0,1\}
^{n}$, that is, Boolean transformations, are called Boolean
isometries.  A minimal Boolean transformation is a one which
has the minimum number of coordinates changed under it among
isometrically equivalent transformations.  A self-dual Boolean
transformation is a one that commutes with the complementation
of all coordinates.  The possible graphs of one-to-one self-dual
transformations are completely determined.  Any self-dual
Boolean transformation can be expressed by Boolean functions
which are concerned with only those points whose coordinates
are changed by the transformation.  A circular transformation
is a one which commutes with rotations of coordinates, and if
it is self-dual, then only one Boolean function can represent
it.  A skew-circular transformation is similarly defined and
represented.  
\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*{2.1 Boolean isometries\label{s:BI}}
Boolean transformations of $\mathbf{Q}^{n}$ are simplest
transformations and play a fundamental role in computer systems. 
They are ubiquitous in computer science and discrete mathematics. 
However, a general theory that supports various results in
different branches has not been established.  In this chapter, we
describe representations of Boolean transformations belonging to
some basic classes.  These representations are used in the
following chapters as basic devices for the present study of
threshold transformations and  neural networks.
   
    A simple Boolean transformation is a permutation of
coordinates.  If $\tau $ is a permutation of $\mathbf{N}$, i.e.
an element
of $\mathrm{SYM}(\mathbf{N})$, then $\tau $ defines the
permutation $H\tau
$ of the coordinates of $\mathbf{Q}^{n}$ by the P\'{o}lya action
$H$, as described in Chapter 1.3, by
$$
        (H\tau )(x_{1},x_{2},..,x_{n}) = (x_{\tau ^{-1}1},x_{\tau
^{-1}2},..,x_{\tau ^{-1}n})
$$
We omit the P\'{o}lya action $H$ hereafter and write $\tau x$ in
place of $(H\tau )x$ for an element $x$ of $\mathbf{Q}^{n}$. 
Another simple transformation of $\mathbf{Q}^{n}$ is a
complementation of coordinates.  Let $J^{-}$ for $J = \{ 
s,t,..,w\} \subseteq  \mathbf{N}$ denote the complementation of
the $s$th,
$t$th,..,$w$th coordinates defined by
$$
        J^{-}x = (x_{1},..,\neg x_{s},..,\neg x_{t},..,\neg
x_{w},..,x_{n}).
$$
If $J$ is a one element-set $\{ s\}$, then $J^{-}$ is denoted by
$s^{-}$.  Also $\mathbf{N}^{-}$ is denoted by $\bar{\neg}$.

    For the composition of a permutation of coordinates $\tau $
and a complementation $J^{-}$, we have
\begin{eqnarray*}
    J^{-}\tau (x_{1},x_{2},..,x_{n}) &=& J^{-}(x_{\tau ^{-
1}1},x_{\tau ^{-1}2},..,x_{\tau ^{-1}n}) \\
         &=& (x_{\tau ^{-1}1},..,\neg x_{\tau ^{-1}s},..,\neg
x_{\tau ^{-1}t},..,\neg x_{\tau ^{-1}w},..,x_{\tau ^{-1}n}) \\    
     &=& \tau (\{\tau ^{-1}s,\tau ^{-1}t,..,\tau ^{-1}w\}^{-
}(x_{1},x_{2},..,x_{n})).
\end{eqnarray*}
Therefore,
$$
         J^{-}\tau  = \tau (\tau ^{-1}J)^{-}, \mbox{ i.e. $\tau
K^{-} = (\tau K)^{-}\tau$ },
\eqno (2.1.1) 
$$
The inverse of $\tau J^{-}$ is, therefore,  
$$\
\begin{array}{lll}
        (\tau J^{-})^{-1} &=& (J^{-})^{-1}\tau ^{-1} = J^{-}\tau
^{-1} \\
              &=& \tau ^{-1}(\tau J)^{-}.
\end{array}
\eqno (2.1.2) 
$$
For the composition of $\sigma J^{-}$ and $\tau K^{-}$, we have
$$
\begin{array}{lll}
        \sigma J^{-}\circ \tau K^{-} &=& \sigma \tau (\tau ^{-
1}J)^{-}K^{-} \\
             &=& \sigma \tau (\tau ^{-1}J\dot{+}K)^{-}.
\end{array}
\eqno (2.1.3) 
$$
We have also obtained:\\

\textbf{Proposition 2.1.1}
The set $O(\mathbf{Q}^{n})$ of all products of a finite number of
permutations and complementations of coordinates of
$\mathbf{Q}^{n}$ consists of $n!2^{n}$ elements, each uniquely
expressed as a product $\tau J^{-}$, where $\tau $ is a
permutation of $\mathbf{N}$, and $J^{-}$ is a complementation. 
Further,
$O(\mathbf{Q}^{n})$ is a transformation group for
$\mathbf{Q}^{n}$.\\

The identity transformation of $\mathbf{Q}^{n}$ will be denoted
by $I$.  Clearly $(\bar{\neg})^{-1} = \bar{\neg}$.  If $x =
(x_{1},x_{2},..,x_{n}) \in  \mathbf{Q}^{n}$, then $\bar{\neg}x$
is
called the complement of $x$.  Then we have
$$
        \bar{\neg}T = T\bar{\neg} \; \mbox{for every $T$ of}\; 
O(\mathbf{Q}^{n}).
$$

    Let $\mathbf{B}$ the set of all Boolean functions from
$\mathbf{Q}^{n}$ to $\mathbf{Q}$.  The group $O(\mathbf{Q}^{n})$
further defines the P\'{o}lya action on $\mathbf{B}$ by
$$
        (Tf)x = f(T^{-1}x),
$$
for each $T \in   O(\mathbf{Q}^{n})$ and $f \in  \mathbf{B}$.  It
is clear from the definition that $x \in  f$ if and only if $Tx
\in  Tf$.  In other words, $(Tf)^{-1}1 = T(f^{-1}1)$, so that the
application of $T$ to a function $f$ is equivalent to the
application of $T$ to the set $f$ through the P\'{o}lya action on
$\mathbf{Q}^{n}$.  For example, the set $\bar{\neg}f$ is the set
of
complements of all points of $f^{-1}1$, while the set $\neg f =
f^{-1}0$.

    Sometimes it is more convenient to use the set $\{ -1,1\}
^{n}$ in place of $\mathbf{Q}^{n} = \{  0,1\} ^{n}$ and to
consider a corresponding transformation of $\{ -1,1\} ^{n}$ for a
transformation of $\mathbf{Q}^{n}$.  This is made possible by the
bijection between $\{ -1,1\} ^{n}$ and $\mathbf{Q}^{n}$ obtained
by the function $\mathrm{Sgn}$ from the \emph{real
$n$-dimensional space}
$\mathbf{R}^{n}$ onto $\{ -1,1\} ^{n}$ defined by
$$
(\mathrm{Sgn}(y))_{i} =  \left\{
                  \begin{array}{ll}
           1 & \mbox{if $y_{i} > 0$,} \\ 
        -1 & \mbox{if $y_{i} \leq  0$},
                \end{array} 
            \right.
$$
or the function $Bool$ from $\mathbf{R}^{n}$ onto
$\mathbf{Q}^{n}$ defined by
$$
(\mathrm{Bool}(x))_{i} =  \left\{
                  \begin{array}{ll}
           1 & \mbox{if}\;  x_{i} > 0,\\ 
         0 & \mbox{if}\;  x_{i} \leq  0,
                \end{array}    
            \right.
$$
    The \emph{Hamming distance} $d_{H}$ is defined on both
$\mathbf{Q}^{n}$ and $\{ -1,1\} ^{n}$ as
$$
        d_{H}(x,y) = |\{ i\mid  x_{i} \ne  y_{i}\}|.
$$
When both $\mathbf{Q}^{n}$ and $\{ -1,1\} ^{n}$ are imbedded in
$\mathbf{R}^{n}$, they represent geometric $n$-\emph{dimensional
cubes} or $n$-\emph{cubes} with each element being their vertex
and each pair $(x,y)$ of elements such that $d_{H}(x,y) = 1$
being their edge.  

    If $\mathrm{Sgn}$ is restricted to $\mathbf{Q}^{n}$ and
$\mathrm{Bool}$ is
restricted to $\{ -1,1\} ^{n}$, then
$$
         \mathrm{Bool} = \mathrm{Sgn}^{-1}.  
$$
A transformation $F$ of $\mathbf{Q}^{n}$ and a transformation $G$
of $\{ -1,1\} ^{n}$ is \emph{equivalent} if
$$
        G = \mathrm{Sgn}\circ F\circ \mathrm{Sgn}^{-1},
$$
that is, the following diagram is \emph{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}
$$
The transformation of $\{ -1,1\} ^{n}$ corresponding to the
transformation $J^{-} = \{  s,t,..,w\}^{-}$ of $\mathbf{Q}^{n}$
is the inversion of corresponding coordinates.  We will use the
same symbols for these operations in $\{ -1,1\} ^{n}$.  Threfore,
\begin{eqnarray*}
    J^{-}y &=& \{  s,t,..,w\}^{-}(y_{1},y_{2},..,y_{n}) \\
       &=& (y_{1},..,-y_{s},..,-y_{t},..,-y_{w},..,y_{n}).
\end{eqnarray*}
However, $\mathbf{N}^{-}$ is the scalar multiplication by $-1$ in
$\mathbf{R}^{n}$,
so that it is denoted by $-$ when no confusion occurs.   
    Applying a permutation $\tau $ to a point $y \in  \{  -1,1\}
^{n}$ by the P\'{o}lya action is made by multiplying $y$ by a
particular $n\times n$ orthogonal matrix $P$ over $\mathbf{R}$
such that each row has only one non-zero element, which is 1, and
each column has only one non-zero element, which is 1.  Also
applying an inversion $J^{-}$ to $y$ is made by multiplying $y$
by a diagonal matrix $D$ such that $D_{ii} = -1$ if $i \in  J$,
and $D_{ii} = 1$ if $i \notin  J$.  Therefore, $PD$ is a matrix
representing an orthogonal transformation of $\mathbf{R}^{n}$
with respect to the basis $\{ 10\cdot \cdot 0, 010\cdot \cdot 0,
... , 0 \cdot \cdot 01 \}$ that maps $\{ -1,1\} ^{n}$ onto
itself.  Conversely, let $T$ be an orthogonal transformation of
$\mathbf{R}^{n}$ that maps $\{ -1,1\} ^{n}$ onto itself.  If a
point $c \in  \mathbf{R}^{n}$ is the center of a face of the
$n$-cube $\{ -1,1\} ^{n}$, then $c_{i} = 1$ or $-1$ for some $i$
and $c_{i} = 0$ for every other $i$, and $c$ must be sent into
the center of a face by $T$.  Also since the set of $n$ centers
$\{ 10\cdot \cdot 0, 010\cdot \cdot 0,.., 0\cdot \cdot 01 \}$
constitutes an orthogonal basis of $\mathbf{R}^{n}$, the matrix
representing $T$ with respect to this basis is $PD$ for some $P$
and $D$ described above.  Thus we have obtained:\\ 

\textbf{Proposition 2.1.2}
  The set $O(\{-1,1\} ^{n})$ of transformations of $\{ -1,1\}
^{n}$ that are equivalent to elements of $O(\mathbf{Q}^{n})$ is
the set of all orthogonal transformations of $\mathbf{R}^{n}$
that map $\{ -1,1\} ^{n}$ onto itself, each transformation being
expressed by a multiplication by an orthogonal matrix such that
each row has only one non-zero element, which is 1 or $-1$, and
each column has only one non-zero element, which is 1 or $-1$. \\

By the above proposition, an element of $O(\mathbf{Q}^{n})$ is
called a (\emph{Boolean}) \emph{isometry} of $\mathbf{Q}^{n}$
hereafter; an element of $O(\{-1,1\} ^{n})$ is called an
\emph{orthogonal transformation}.  Note that $O(\{-1,1\} ^{n})$
is the same as $O(\mathbf{Q}^{n})$ as a group and well known as a
finite reflection subgroup of $O(\mathbf{R}^{n})$, the group of
orthogonal transformations of $\mathbf{R}^{n}$ (see e.g. Grove \&
Benson, 1985).  Further, the following Proposition 2.1.4 shows
$O(\{-1,1\} ^{n})$ is the set of all one-to-one linear
transformations that map $\{ -1,1\} ^{n}$ onto itself. \\

\textbf{Lemma 2.1.3}
$v \in  \{  -1,1\} ^{n}$ and $v= (v^{(1)}+...+ v^{(n)})/(n-2)$
for linearly independent vectors $v^{(i)} \in  \{  -1,1\} ^{n}$,
then $d_{H}(v,v^{(i)}) = 1$ for every $i = 1,...,n$.

\begin{proof}
Let $v \in  \{  -1,1\} ^{n}$ and $v = (v^{(1)}+...+v^{(n)})/(n-
2)$ for linearly independent vectors $v^{(i)} \in  \{  -1,1\}
^{n}$.  Let $v = 11\cdot \cdot \cdot 1$ without loss of
generality.  Then $(v^{(i)}_{1}+...+v^{(i)}_{n})\cdot (n-2) = 1$
for every $i = 1,..,n$.  Let the number of $-1$s in $\{
v^{(1)}_{j},...,v^{(n)}_{j}\}$ be $k$.  Then $(n-k)-k = n-2$, so
that $k = 1$ for every $j$.  Suppose the number of $-1$s in
$v^{(i)}$ is more than 1 for some $i$.  Then there exists some
$l$ such that $v^{(l)} = 11\cdot \cdot \cdot 1 = v$.  Let $l = 1$
without loss of generality.  Then $(1 - 1/(n-2))v^{(1)} =
(v^{(2)}+...+v^{(n)})/(n-2)$ contrary to the linear independence
of $v^{(1)},...,v^{(n)}$.  Therefore, $d_{H}(v,v^{(i)}) = 1$ for
every $i = 1,...,n$.
\end{proof}    


\textbf{Proposition 2.1.4}
If $T$ is a one-to-one linear transformation of $\mathbf{R}^{n}$
that maps $\{ -1,1\} ^{n}$ onto itself, then $T$ is an orthogonal
transformation.

\begin{proof}  This proposition is clear for $n \leq  2$.  Let
$T$ be a one-to-one linear transformation of $\mathbf{R}^{n}$
that maps $\{ -1,1\} ^{n}$ onto itself for $n \geq  3$.  Let $v
=1\cdot \cdot \cdot 1,v^{(1)} = -11\cdot \cdot 1,v^{(2)} = 1-
11\cdot \cdot 1,...,v^{(n)} = 1\cdot \cdot 1-1$.  Since $v =
(v^{(1)}+...+v^{(n)})/(n-2)$, and $T$ is linear, $Tv =
(Tv^{(1)}+...+Tv^{(n)})/(n-2)$. $Tv$ and $Tv^{(i)}$ are elements
of $\{ -1,1\} ^{n}$ for every $i$.  Since $T$ is one-to-one, and
$v^{(i)}$ are linearly independent, $Tv^{(i)}$ are also linearly
independent.  Therefore, by Lemma 2.1.3, $d_{H}(Tv, Tv^{(i)}) =
1$
for every $i = 1,...,n$ and $Tv^{(i)} \ne  Tv^{(j)}$ for every $i
\ne  j$.  Therefore, $(Tv^{(i)},Tv^{(i)}) = n =
(v^{(i)},v^{(i)})$ for every $i$ and $(Tv^{(i)},Tv^{(j)}) = n-4 =
(v^{(i)},v^{(j)})$ for every $i \ne  j$.  On the other hand, $\{
v^{(1)},...,v^{(n)}\}$ is a basis of $\mathbf{R}^{n}$. 
Therefore, $T$ is an orthogonal transformation.
\end{proof}


\textbf{Proposition 2.1.5}  Any isometry $T \in  
O(\mathbf{Q}^{n})$ can be decomposed as a disjoint composition 
$$
        T = \sigma _{1}J_{1}^{-}\odot ... \odot \sigma
_{k}J_{k}^{-}\odot \iota J_{k+1}^{-},
$$
where $\sigma_{i}$ is a cyclic permutation, $J_{i} \subseteq
\mathrm{Car}\sigma_{i}$
for each $i = 1,...,k$, and $J_{k+1} \subseteq
\mathbf{N}\backslash\bigcup_{i}\mathrm{Car}\sigma_{i}$, and
$\iota$ is the identity on
$\mathbf{N}\backslash\bigcap_{i}\mathrm{Car}\sigma_{i}$.


\begin{proof}  Let $T$ be an isometry of $\mathbf{Q}^{n}$.  Then
$T$ is expressed as $T = \tau J^{-}$ by Proposition 2.1.1, where
$\tau \in  \mathrm{SYM}(\mathbf{N})$ and $J \subseteq 
\mathbf{N}$.
  If $\tau $ is not the identity permutation, then, by
Proposition 1.2.2 of Chapter
1, $\tau  = \sigma _{1}\odot ...\odot \sigma _{k}$, where
$\sigma_{i}$
 is a cyclic permutation of length at least 2,  and
$\mathrm{Car}\sigma_{i}$
 and $\mathrm{Car}\sigma_{j}$ are disjoint if $i \ne j$.  Let
 $J_{i} = J\cap\mathrm{Car}\sigma_{i}$ for each $i = 1,..,k$, and
$J_{k+1} =
J\cap(\mathbf{N}\backslash\bigcup_{i}\mathrm{Car}\sigma_{i})$.
 Then $T$ can be expressed by the disjoint composition shown
above.
\end{proof}

As a group, $O(\mathbf{Q}^{n})$ is also the wreath product of
$\mathrm{SYM}(\mathbf{N})$ by the $\mathrm{SYM}(\{-1,1\} )$ (see
Krishnamurthy, 1986 or Williamson, 1985 for the definition of the
wreath product).  In this case, $O(\mathbf{Q}^{n})$ can be
regarded as a transformation group on the $2n$-point set $\{ 1,-
1,2,-2,..,n,-n\}$.  The transformation is defined by $\tau J^{-}x
= (\mathrm{Sgn}x)\tau |x|$ if $|x| \notin  J$, and
$\tau J^{-}x = -(\mathrm{Sgn}x)\tau |x|$ if $|x| \in 
J$. However, we are always concerned with transformations on
$\mathbf{Q}^{n}$ or $\{ -1,1\} ^{n}$, so that reducing the domain
of transformations in this way will not help us.\\


\section*{2.2 Minimal and maximal transformations}
In the present study, we are mainly concerned with
threshold transformations that are not isometries of
$\mathbf{Q}^{n}$.  However, in order to characterize non-
isometrical transformations, we investigate their relations to
isometries. 

     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$.  Clearly, a
transformation is an isometry if and only if it is isometrically
equivalent to the identity.  If $G = T^{-1}FT$ for an isometry
$T$, then $G$ is called \emph{isometrically similar} to $F$.  In
this case, the graphs of $F$ and $G$ are not only isomorphic
under the isomorphism induced by $T$, but also $T$ preserves the
Euclidean distance and hence the Hamming distance between every
pair of points.  If $G = SFT$ for isometries $S$ and $T$, then $G
= T^{-1}(TSF)T$.  Therefore, the graph of any transformation
isometrically equivalent to $F$ is obtained from $F$ by applying
an isometry after $F$, if we regard two isomorphic graphs induced
by an isometry $T$ as the same.  If $F$ and $G$ are
transformations of $\{ -1,1\} ^{n}$, and if $G = SFT$ for some
orthogonal transformations $S$ and $T$ of $\{ -1,1\} ^{n}$, then
$G$ is called \emph{orthogonally equivalent} to $F$.  If $G =
T^{-1}FT$ for some orthogonal transformation $T$ of $\{ -1,1\}
^{n}$, then $G$ is called \emph{orthogonally similar} to $F$.   

    As shown by Proposition 2.1.4, orthogonal transformations of
$\{ -1,1\} ^{n}$ are the only one-to-one linear transformations
of $\mathbf{R}^{n}$ that map $\{ -1,1\} ^{n}$ onto itself. 
Therefore, by reducing non-isometrical transformations to the
isometrically equivalent simplest forms, we may be able to
extract some nonlinear aspects, such as reflected in their
graphs, that are unique to the non-isometrical  transformations.  

    First we introduce the \emph{variation} of $F$ denoted by
$\mathrm{Var}(F)$ for a transformation $F$ of $\mathbf{Q}^{n}$ as
the total number of coordinates that change under $F$.  That is,
$$
        \mathrm{Var}(F)= \sum_{x \in \mathbf{Q}^n}d_H(x,Fx).
$$


\textbf{Example 2.2.1}
$Var(I) = 0$, $Var(\bar{\neg}) = n\cdot 2^{n}$.\\

\textbf{Proposition 2.2.2}
If $F$ and $G$ are isometrically similar, then $\mathrm{Var}(F)
= \mathrm{Var}(G)$.

\begin{proof}  If $T$ is an isometry, then
\begin{eqnarray*}
      \mathrm{Var}(T^{-1}FT)&=&\sum_{x \in
\mathbf{Q}^n}d_H(x,(T^{-1}FT)x)\\
&=&\sum_{x \in \mathbf{Q}^n}d_H(Tx,T(T^{-1}FT)x)\\
&=&\sum_{x \in \mathbf{Q}^n}d_H(Tx,F(Tx))\\
&=&\sum_{y \in \mathbf{Q}^n}d_H(y,Fy) = \mathrm{Var}(F)
\end{eqnarray*}
\end{proof} 

We call a Boolean transformation $F$ \emph{minimal}, if
$\mathrm{Var}(F) \leq  \mathrm{Var}(TF)$ for every isometry $T$. 
We call a minimal transformation $F$ \emph{uniquely minimal}, if
$TF$ is not minimal for any non-identity isometry $T$. 
Similarly, we call a Boolean transformation $F$ \emph{maximal},
if $\mathrm{Var}(F) \geq  \mathrm{Var}(TF)$ for every isometry
$T$.  We call a maximal transformation $F$ \emph{uniquely
maximal}, if $TF$ is not maximal for any non-identity isometry
$T$.

    Let $F$ and $G$ be isometrically equivalent and uniquely
minimal; then $G = SFT$ for some isometries $S$ and $T$. 
Therefore, $G =T^{-1}TSFT$.  Since $G$ is minimal, $TSF$ is
minimal.  Since $F$ is uniquely minimal, $TS$ = $I$.  Therefore
$G = T^{-1}FT$.  The discussion above is summarized in the
following theorem.\\

\textbf{Theorem 2.2.3}  If $F$ is a Boolean transformation, then
there exists an isometry $S$ such that $SF$ is minimal.  If $F$
and $G$ are uniquely minimal and isometrically equivalent, then
$F$ and $G$ are isometrically similar.\\

\textbf{Example 2.2.4}  If $T$ is an isometry, then $T$ is
isometrically equivalent to the identity transformation $I$,
which is uniquely minimal, and $T$ is isometrically equivalent
to the uniquely maximal transformation $\bar{\neg}$.\\

Proposition 2.2.5  $F$ is minimal if and only if $\bar{\neg}F$ is
maximal. $F$ is uniquely  minimal if and only if $\bar{\neg}F$ is
uniquely maximal. 

\begin{proof}  We have $d_{H}(x,\bar{\neg}y) = n - d_{H}(x,y)$
for
every $x, y \in  \mathbf{Q}^{n}$.  Therefore, the proof is clear
from $\mathrm{Var}(\bar{\neg}F) = n\cdot 2^{n} -
\mathrm{Var}(F)$.
\end{proof}


\section*{2.3 Self-dual transformations\label{s:SDT}}
A Boolean function $f$ defined on $\mathbf{Q}^{n}$ is called
\emph{self-dual}, if $\bar{\neg}f = \neg f$.  Similarly, a
transformation $F$ of $\mathbf{Q}^{n}$ is called
\emph{self-dual}, if $F\bar{\neg} = \bar{\neg}F$.  The
transformation $G$
of $\{ -1,1\} ^{n}$ equivalent to a self-dual transformation of
$\mathbf{Q}^{n}$ satisfies $-G = G-$ and is also called
\emph{self-dual}.  Let $F$ be expressed as $F =
(F_{1},...,F_{n})$, where $F_{i} = p_{i}F$.   Then, $F$ is
self-dual if and only if $F_{i}$ is self-dual for every $i$.\\

\textbf{Example 2.3.1}  If $\tau $ is a permutation of
$\mathbf{N}$, then
$\tau $ and $\bar{\neg}\tau  (= \tau \bar{\neg})$ are self-dual. 
Conversely, if $T$ is a self-dual isometry of $\mathbf{Q}^{n}$,
then $T = \tau $ or $\bar{\neg}\tau $ for a permutation $\tau $
of $\mathbf{N}$.\\

 If $F$ and $G$ are self-dual, then $FG$ is clearly self-dual. 
Further, by the following proposition, the set of all self-dual
one-to-one transformations of $\mathbf{Q}^{n}$ is a
transformation group. \\


\textbf{Proposition 2.3.2}  If $F$ is a one-to-one self-dual
transformation, then $(\bar{\neg}F)^{-1} = \bar{\neg}F^{-1}$, and 
$F^{-1}$ is also self-dual.

\begin{proof} Let $F$ be one-to-one and self-dual.  Then
$\bar{\neg}F\bar{\neg}F^{-1} =
FF^{-1} = I$.  Therefore, $(\bar{\neg}F)^{-1} =
\bar{\neg}F^{-1}$.  On the other hand, 
$(\bar{\neg}F)^{-1} = F^{-1}\bar{\neg}^{-1} = F^{-1}\bar{\neg}$,
so that
$\bar{\neg}F^{-1}= F^{-1}\bar{\neg}$. 
 \end{proof}



Now, we shall describe graphs of one-to-one self-dual
transformations, though they are rather obvious and partly
described in Ishii (1970).  We call a self-dual transformation
$H$ \emph{elementary}, when if $H = F\odot G$, and both $F$ and
$G$ are self-dual, then $F$ or $G$ is the identity $I$.  From
these definitions the following proposition is clear.\\

\textbf{Proposition 2.3.3}  Any self-dual transformation is a
disjoint composition of one or several elementary self-dual
transformations.\\
 
The graph of any one-to-one transformation of a finite set
consists of a set of disjoint cycles.  In general, let $A = \{ 
(s_{1},t_{1}),...,(s_{k},t_{k})\}$, where $s_{i} \geq  1$ and
$t_{i} \geq  1$ are integers for every $i$, $t_{i} \ne  t_{j}$
for $i \ne  j$, and $s_{1}\cdot t_{1}+...+s_{k}\cdot t_{k}  =
2^{n}$.  We call $A$ a \emph{cycle structure} for
$\mathbf{Q}^{n}$.  We say that the cycle structure $A$ is
\emph{realized} by a transformation $F$ of $\mathbf{Q}^{n}$, or
that the cycle structure $\mathrm{CS}(F)$ of $F$ is $A$, and
write $\mathrm{CS}(F) = A$, if the set of all cycles of
$\mathrm{GRAPH}(F)$ consists of $s_{1}$ $t_{1}$-cycles, ... ,
and $s_{k}$ $t_{k}$-cycles.  A subset $C$ of $\mathbf{Q}^{n}$
such that $\bar{\neg}C$ = $C$ is called a \emph{complete set}.\\

\textbf{Proposition 2.3.4}  If $F$ is an elementary one-to-one
self-dual transformation which is not the identity, then
$\mathrm{CS}(F) = \{ (1,t), (2^{n}-t,1)\}$ for some even $t \geq 
2$,or $\mathrm{CS}(F) = \{ (2,t), (2^{n}-2t,1)\}$ for some $t
\geq 2$.  Conversely, the cycle structure $\{ (1,t),
(2^{n}-t,1)\}$ for some even $s \geq  2$, and the cycle structure
$\{ (2,t), (2^{n}-2t,1)\}$ for some $t \geq  2$ are realized by
some elementary self-dual transformations of $\mathbf{Q}^{n}$.

\begin{proof}  Let $q$ be a point on a $t$-cycle such that $t
\geq  2$ of an elementary one-to-one self-dual transformation
$F$.  If $\bar{\neg}q$ is in the same cycle, then $\bar{\neg}(Fq)
=
F(\bar{\neg}q)$ and $Fq$ are in the same cycle.  Inductively, if
$x$ is any
point on this cycle, then $\bar{\neg}x$ is also on the same
cycle. 
Therefore, in this case, $t$ is even, and this cycle and loops
form $\mathrm{GRAPH}(F)$.  If $\bar{\neg}q$ is on another cycle,
then
$F^{m}q$ is on the first cycle and $\bar{\neg}(F^{m}q) =
F^{m}(\bar{\neg}
q)$ is on the second cycle for every $m$.  The two cycles and
loops form $\mathrm{GRAPH}(F)$.  Conversely, if $t$ is a
positive integer, consider a complete set $C \subseteq 
\mathbf{Q}^{n}$
such that $|C| = 2t$, and let $C = A\cup B$ such that
$A\cap B = \emptyset $ and if $x \in  A$ then $\bar{\neg}x \in 
B$
and if $x \in  B$ then $\bar{\neg}x \in  A$.  Construct a
transformation
$F$ composed of fixed points and one $t$-cycle ranging over $A$.
$G = F\odot \bar{\neg}F\bar{\neg}$ is elementary and self-dual,
and
$\mathrm{CS}(G) = \{  (2,t), (2^{n}-2t,1)\}$.  If $t$ is even,
consider $G$ defined above for a complete set $C$ such that
$|C| = t$.  For a point $q$ in $C$, define $H$ as $Hq =
G(\bar{\neg}q)$,
and $H(\bar{\neg}q) = Gq$ and $Hx = Gx$ for every other $x$.
$H$ is elementary and self-dual and 
$\mathrm{CS}(H) = \{ (1,t),(2^{n}-t,1)\}$.
\end{proof}

\textbf{Theorem 2.3.5}  The necessary and sufficient condition
for
a cycle structure\\
 $\{ (s_{1},t_{1}),...,(s_{k},t_{k})\}$ such that
 $s_{1}\cdot t_{1}+...+s_{k}\cdot t_{k} = 2^{n}$ to be
realized by a self-dual transformation of $\mathbf{Q}^{n}$ is
that $t_{i}s_{i}$ is even for every $i$.

\begin{proof}  By decomposing one-to-one self-dual
transformations into elementary self-dual transformations
we obtain the necessary part.
 For the sufficiency, express $\mathbf{Q}^{n}$
as a mutually disjoint union of $s_{i}$ complete sets with
$t_{I}$ elements for even $t_{i}$ and $s_{i}/2$ complete sets
with $2t_{i}$ elements for odd $t_{i}$ and the rest of
$\mathbf{Q}^{n}$.  Following the proof of Proposition 2.3.4,
construct self-dual elementary transformations composed of fixed
points and one $t_{i}$-cycle for even $t_{i}$ and two 
$t_{i}$-cycles for odd $t_{i}$ ranging over each complete set. 
The disjoint composition of these elementary transformations
realizes the given cycle structure.
\end{proof}


\section*{2.4 [ ]-representations\label{s:BR}}
Assume that the transformation $F = (F_{1},...,F_{n})$ of
$\mathbf{Q}^{n}$, where $F_{i} = p_{i}F$, is self-dual.  A
necessary and sufficient condition for $x \in  \mathbf{Q}^{n}$
to be a point such that $x_{i} = 1$ and $(Fx)_{i} = 0$ is that $x
\in  p_{i}\cdot \neg F_{i}$.  Let $f_{i}$ be defined as 
$$
        f_{i} = p_{i}\cdot \neg F_{i}
\eqno (2.4.1) 
$$
for every $i$.  Then $\neg f_{i} = \neg (p_{i}\cdot \neg F_{i})=
\neg p_{i}\vee F_{i}$, so that $p_{i}\cdot \neg f_{i} =
p_{i}\cdot F_{i}$.  Also $\bar{\neg}f_{i} = (p_{i}\cdot \neg
F_{i})\bar{\neg} = (p_{i}\bar{\neg})\cdot (\neg F_{i}\bar{\neg})
= \neg
p_{i}\cdot F_{i}$.  Since $F_{i} = p_{i}\cdot F_{i}\vee \neg
p_{i}\cdot F_{i}$, we obtain
$$
        F_{i} = p_{i}\cdot \neg f_{i}\vee \bar{\neg}f_{i}.
\eqno (2.4.2) 
$$

    Conversely, for any Boolean function $f_{i}$ such that
$f_{i}
= p_{i}\cdot f_{i}$ for every $i$, let $F_{i}$ be defined by
(2.4.2).  Then
\begin{eqnarray*}
    \neg \bar{\neg}F_{i} &=& \neg ((p_{i}\bar{\neg})\cdot (\neg
f_{i}\bar{\neg})\vee f_{i})\\
        &=& (\neg ((p_{i}\bar{\neg})\cdot (\neg
f_{i}\bar{\neg})))\cdot \neg f_{i}\\
        &=& (p_{i}\vee f_{i}\bar{\neg})\cdot \neg f_{i} =
p_{i}\cdot \neg f_{i}\vee (f_{i}\bar{\neg})\cdot \neg f_{i}.
\end{eqnarray*}
However, $(f_{i}\bar{\neg})\cdot f_{i} = ((p_{i}\cdot
f_{i})\bar{\neg})\cdot p_{i}\cdot
f_{i} = \neg p_{i}\cdot (f_{i}\bar{\neg})\cdot
p_{i}\cdot f_{i} = \emptyset $.  Therefore, 
$$
        \neg \bar{\neg}F_{i} = F_{i},
$$
so that $F = (F_{1},...,F_{n})$ is a self-dual transformation. 
Further,
\begin{eqnarray*}
    p_{i}\cdot \neg F_{i} &=& p_{i}\cdot \neg (p_{i}\cdot \neg
f_{i}\vee f_{i}\bar{\neg}) = p_{i}\cdot \neg (p_{i}\cdot \neg
f_{i})\cdot (\neg f_{i}\bar{\neg})\\
        &=& p_{i}\cdot (\neg p_{i}\vee f_{i})\cdot (\neg
(p_{i}\cdot f_{i})\bar{\neg}) = p_{i}\cdot f_{i}\cdot (p_{i}\vee
(\neg
f_{i}\bar{\neg})\\
        &=& f_{i}\vee f_{i}\cdot \neg f_{i}\bar{\neg} = f_{i}.
\end{eqnarray*}
Therefore, (2.4.1) is satisfied.
 
   Consequently, any self-dual transformation $F$ such that $F
= (F_{1},...,F_{n})$ will be represented by a [\;]-representation
as
$$
        F = [f_{1},...,f_{n}],
\eqno (2.4.3) 
$$
where if $x =(x_{1},...,x_{n}) \in  f_{i}$ then $x_{i} = 1$, and
the relations between $F_{i}$ and $f_{i}$ are given above by
(2.4.1) and (2.4.2).\\

\textbf{Example 2.4.1}  Let
$F = [p_{1}\cdot p_{2}\cdot p_{3},\neg p_{1}\cdot p_{2},\neg
p_{1}\cdot \neg p_{2}\cdot
p_{3}]$ be a transformation of $\mathbf{Q}^{3}$.
We express $F$ in the following tables.

$$
 \begin{tabular}{l|l}
   $f_{1}$ &  $\bar{\neg} f_{1}$ \\ \hline
   $ f_{2}$ &  $\bar{\neg} f_{2}$ \\ \hline
  $ f_{3}$ &  $\bar{\neg} f_{3}$  
\end{tabular}
\; = \;
\begin{tabular}{l|l}
    $1\cdot 2 \cdot 3$ &  $\neg 1\cdot \neg 2\cdot \neg 3$ \\
\hline
    $\neg 1\cdot 2$ &  $1\cdot \neg 2$ \\ \hline
   $\neg 1\cdot \neg 2 \cdot 3$ &  $1\cdot 2\cdot \neg 3$ 
\end{tabular}
\; = \; \begin{tabular}{l|l}
    $111$&  $000$ \\ \hline
  $011$ & $100$ \\
  $010$&  $101$ \\ \hline
  $001$ &  $110$ 
\end{tabular}
$$

Then we obtain GRAPH(F):
$$
\begin{array}{ccccccccc}
 101 & \rightarrow & 111 & \rightarrow& 011& \rightarrow &001
&&\\
     &&     \uparrow     &&&&      \downarrow &&\\
     &&       110 & \leftarrow & 100 &  \leftarrow &  000 & 
\leftarrow & 010  
\end{array}
$$    

    The advantage of the form (2.4.3) is not only its absorption
of
$F_{i}$'s self-duality.  We have clearly
$$
           \mathrm{Car}F = \bigcup_{I=1}^n (f_{i}\cup
\bar{\neg}f_{i}).
$$
In fact, the points of $f_{i}$, whose $i$th coordinate is 1, are
transformed into points whose $i$th coordinate is 0, while the
points of $\bar{\neg}f_{i}$ , whose $i$th coordinate is 0, are
transformed into points whose $i$th coordinate is 1.  And these
are all the changes on $\mathbf{Q}^{n}$ when $F$ is applied. 
Therefore, if $F$ is self-dual and represented as
$[f_{1},...,f_{n}]$, then clearly
$$
         \mathrm{Var}(F) = 2 \sum_{i=1}^n |f_{i}|.
\eqno (2.4.4) 
$$
Further, if $F = [f_{1},...,f_{n}]$, $G = [g_{1},...,g_{n}]$,
and
$\mathrm{Car}F$ and $\mathrm{Car}G$ are disjoint, then $F+G =
[f_{1}\vee g_{1},...,f_{n}\vee g_{n}]$.    
    Now, let $F_{i}$ be a Boolean function expressed as 
$$
        F_{i} =  p_{i}\cdot g_{i}\vee (\neg p_{i})\cdot h_{i},
\eqno (2.4.5)
$$
for some $g_{i}, h_{i}: \mathbf{Q}^{\mathbf{N}\backslash i}
\rightarrow 
\mathbf{Q}$.  Then 

$$
\begin{array}{lll}
        f_{i} &=& p_{i}\cdot \neg F_{i} \\
           &=& p_{i}\cdot \neg g_{i}.
\end{array}
\eqno (2.4.6) 
$$

Further,
\begin{eqnarray*}
    \neg \bar{\neg}F_{i} &=& \neg (\neg p_{i}\cdot
(g_{i}\bar{\neg})\vee
p_{i}\cdot (h_{i}\bar{\neg}))\\
        &=& (p_{i}\vee \neg g_{i}\bar{\neg})\cdot (\neg p_{i}\vee
\neg h_{i}\bar{\neg})\\
        &=& p_{i}\cdot (\neg h_{i}\bar{\neg})\vee \neg p_{i}\cdot
(\neg g_{i}\bar{\neg})\vee (\neg h_{i}\bar{\neg})\cdot (\neg
g_{i}\bar{\neg})\\
 &=& p_{i}\cdot (\neg h_{i}\bar{\neg})\vee \neg p_{i}\cdot (\neg
g_{i}\bar{\neg})\vee p_{i}\cdot (\neg h_{i}\bar{\neg})\cdot (\neg
g_{i}\bar{\neg})\vee \neg p_{i}\cdot (\neg h_{i}\bar{\neg})\cdot
(\neg g_{i}\bar{\neg})\\
        &=& p_{i}\cdot (\neg h_{i}\bar{\neg})\vee \neg p_{i}\cdot
(\neg g_{i}\bar{\neg}). 
\end{eqnarray*}
Therefore, $\neg \bar{\neg}F_{i} = F_{i}$, if and only if $h_{i}
= \neg g_{i}\bar{\neg}$, that is, 
$$
        F_{i} = p_{i}\cdot g_{i}\vee \neg p_{i}\cdot (\neg
\bar{\neg}g_{i}).
\eqno (2.4.7) 
$$

\textbf{Proposition 2.4.2}  If $F = [f_{1},...,f_{n}]$ then
$$
        k^{-}F = [f_{1},..,f_{k-1},p_{k}\cdot \neg
f_{k},f_{k+1},..,f_{n}].
$$

\begin{proof}  Let $k^{-}F = [g_{1},..,g_{k},..,g_{n}]$.  Then
$g_{k} = p_{k}\cdot \neg (\neg F_{k}) = p_{k}\cdot F_{k}$ by
(2.4.1), so that $g_{k} = p_{k}\cdot (p_{k}\cdot \neg f_{k}\vee
\bar{\neg}f_{k}) = p_{k}\cdot \neg f_{k}\vee p_{k}\cdot
(\bar{\neg}f_{k})$
by (2.4.2).  Since $(\bar{\neg}f_{k})x = 1$ implies
$(\bar{\neg}x)_{k} =
1$, i.e. $x_{k} = 0$, we have $p_{k}\cdot (\bar{\neg}f_{k}) = 0$. 
Therefore, $g_{k} = p_{k}\cdot \neg f_{k}$.  Clearly $g_{i} =
f_{i}$ for any other $i$.
\end{proof}

\textbf{Notation}  If $F = [f_1,...,f_n]$, then $f_i|1$ is the
function from $\mathbf{Q}^{\mathbf{N}\backslash i}$ to
$\mathbf{Q}$ defined by 
$$
          (f_i|1)x = f_i(x,1),
$$
where $(x,1)$ is the point of $\mathbf{Q}^{\mathbf{N}}$ obtained
by adding the $i$th coordinate $1$ to $x$, i.e.
$$
          P_M(x,1) = x \quad \mbox{and} \quad p_i(x,1) = 1.
$$

\textbf{Proposition 2.4.3}   If $F = [f_{1},...,f_{n}]$ then
$$
               Fk^{-} = [k^{-}f_{1},..,p_{k}\cdot (\neg
     \bar{\neg}(f_{k}|1)),..,k^{-}f_{n}].
$$
\begin{proof}  Let $Fk- = [g_{1}, ..,g_{k},..,g_{n}]$.  If
$i \ne  k$, then 
$$
\begin{array}{llll}
  g_{i} &=& p_{i}\cdot \neg (Fk^{-})_{i} &\\
        &=& p_{i}\cdot \neg p_{i}(Fk^{-})\\
       &=& (p_{i}\cdot \neg (p_{i}F))k^{-} \\             
       & =& f_{i}k^{-}&    \qquad \mbox{by (2.4.1)}\\
       &=& k^{-}f_{i}.&    \qquad \mbox{Polya action}\\
       g_{k} &=& p_{k}\cdot \neg (Fk^{-})_{k}&\\
       &=& p_{k}\cdot (\neg p_{k}(Fk^{-}))&\\
       &=& p_{k}\cdot (\neg (p_{k}\cdot \neg f_{k}\vee
     \bar{\neg}f_{k})k^{-}) & \qquad \mbox{by (2.4.2)}\\
      &=& p_{k}\cdot ((\neg (p_{k}\cdot \neg f_{k})\cdot \neg
     \bar{\neg}f_{k})k^{-})&\\
      &=& p_{k}\cdot (((\neg p_{k}\vee f_{k})\cdot \neg
     \bar{\neg}f_{k})k^{-})&\\
      &=& p_{k}\cdot ((\neg p_{k}\cdot \neg
\bar{\neg}f_{k}\vee
     f_{k}\cdot \neg \bar{\neg}f_{k})k^{-}).&
     \end{array}
$$
     Since
$$
      p_{k}\cdot (f_{k}k^{-}) = p_{k}\cdot ((p_{k}\cdot
f_{k})k^{-}) = p_{k}\cdot
     (p_{k}k^{-})\cdot (f_{k}k^{-}) =p_{k}\cdot (\neg p_{k})\cdot
(f_{k}k^{-}) = 0, 
$$
$$
\begin{array}{llll}
g_{k} &=& p_{k}\cdot ((\neg p_{k}\cdot \neg
\bar{\neg}f_{k})k^{-})&\\
     &=& p_{k}\cdot p_{k}\cdot ((\neg
\bar{\neg}f_{k})k^{-})&\\
     &=& p_{k}\cdot (\neg f_{k}\bar{\neg})k^{-})&
\qquad \mbox{Polya action}\\
    & =&p_{k}\cdot (\neg f_{k}(\mathbf{N}\backslash k)^{-})&\\
    &=& p_{k}\cdot (\neg (p_{k}\cdot
    (f_{k}|1))(\mathbf{N}\backslash k)^{-})&\\
    &=& p_{k}\cdot ((\neg p_{k}\vee \cdot (\neg
   (f_{k}|1)))(\mathbf{N}\backslash k)^{-})&\\
    &=& p_{k}\cdot (\neg p_{k}\vee \neg (f_{k}|1)\bar{\neg})&\\
    & =& p_{k}\cdot (\neg (f_{k}|1)\bar{\neg})&\\
    &=& p_{k}\cdot (\neg \bar{\neg}(f_{k}|1)).& \qquad
   \mbox{Polya action}
\end{array}
$$
\end{proof}


If $F = [f_{1},...,f_{n}]$ then
$$
       Fk^{-} = [k^{-}f_{1},..,p_{k}\cdot (\neg
\bar{\neg}(f_{k}|1),..,k^{-}f_{n}].
$$
\begin{proof}  Let $Fk^{-} = [g_{1}, ..,g_{k},..,g_{n}]$.   
If  $i \ne  k$, then
\begin{eqnarray*}
g_{i} &=& p_{i}\cdot \neg (Fk^{-})_{i}\\
     & =& p_{i}\cdot \neg p_{i}Fk^{-}  \\
   &=& (p_{i}\cdot \neg p_{i}F)k^{-}\\
     & =& f_{i}k^{-}\\
     & =& k^{-}f_{i}. \\
g_{k} &=& p_{k}\cdot \neg (Fk^{-})_{k}\\
     & =& p_{k}\cdot (\neg p_{k}Fk^{-}) \\
   &=& p_{k}\cdot (\neg (p_{K}\cdot \neg f_{k}\vee
\bar{\neg}f_{k})k^{-}) \\
   &=& p_{k}\cdot ((\neg (p_{K}\cdot \neg f_{k})\cdot \neg
\bar{\neg}f_{k})k^{-}) \\
   &=& p_{k}\cdot (((\neg p_{K}\vee f_{k})\cdot \neg
\bar{\neg}f_{k})k^{-}) \\
   &=& p_{k}\cdot ((\neg p_{K}\cdot \neg \bar{\neg}f_{k}\vee
f_{k}\cdot \neg \bar{\neg}f_{k})k^{-}).
\end{eqnarray*}
If $g_{k}x= 1$ then $x_{k} = 1$.  But if $x_{k} = 1$ then
$f_{k}k^{-}x= 0$, since $f_{k}y = 1$ implies $y_{k}  = 1$. 
Therefore,
\begin{eqnarray*}
     g_{k} &=& p_{k}\cdot ((\neg p_{K}\cdot \neg
\bar{\neg}f_{k})k^{-})= p_{k}\cdot p_{K}\cdot ((\neg
\bar{\neg}f_{k})k^{-}) \\
          &=& p_{k}\cdot (\neg f_{k}\bar{\neg})k^{-}) =p_{k}\cdot
(\neg f_{k}(N\backslash k)^{-}) \\
          &=& p_{k}\cdot (\neg (p_{k}\cdot (f_{k}|1))(N\backslash
k)^{-
}) \\
     &=& p_{k}\cdot ((\neg p_{k}\vee \cdot (\neg
(f_{k}|1)))(N\backslash k)^{-})  \\
          &=& p_{k}\cdot (\neg p_{k}\vee  \neg
(f_{k}|1)\bar{\neg}) = p_{k}\cdot (\neg (f_{k}|1)\bar{\neg})  \\
          &=& p_{k}\cdot (\neg \bar{\neg}(f_{k}|1)).   
\end{eqnarray*}
\end{proof} 

Let $F = [f_{1},..,f_{m}]$ and $G = [g_{n+1},..,g_{m+n}]$ be
respectively self-dual
transformations of $\mathbf{Q}^{M}$ and $\mathbf{Q}^{N}$, where
$M = \{1,...,m\}$
and $N = \{m+1,..,m+n\}$.  Then the direct product  $F\times G$,
which is the transformation of $\mathbf{Q}^{M\cup N}$, is also
self-dual and represented by
$$
     F\times G = [f_{1}\circ P_{M},..,f_{m}\circ
P_{M},g_{m+1}\circ
P_{N},..,g_{m+n}\circ P_{N}].
\eqno (2.4.8) 
$$

\textbf{Example 2.4.4}  Let  $F =[p_{1}\cdot p_{2}\cdot
p_{3},\neg p_{1}\cdot
p_{2},\neg p_{1}\cdot \neg p_{2}\cdot p_{3}]$ and
and $G = [p_{4}\cdot p_{5},\neg p_{4}\cdot p_{5}]$ be
respectively transformations of
$\mathbf{Q}^{\{1,2,3\}}$ and $\mathbf{Q}^{\{4,5\}}$.

$\mathrm{GRAPH}(F)$ is illustrated in Example 2.4.1. 
$\mathrm{GRAPH}(G)$ is 
$$
\begin{array}{ccc}
 11 & \rightarrow & 01\\
     \uparrow  &     & \downarrow \\
  10  & \leftarrow & 00  
\end{array}
$$    
Then
$$
F\times G = [p_{1}\cdot p_{2}\cdot p_{3},\neg p_{1}\cdot
p_{2},\neg p_{1}\cdot \neg
p_{2}\cdot p_{3},p_{4}\cdot p_{5},\neg p_{4}\cdot p_{5}.
$$
$\mathrm{GRAPH}(F\times G)$ is
$$
\begin{array}{ccccccccccc}
10110 &\rightarrow& 11111 &\rightarrow& 01101 &\rightarrow& 00100
&\rightarrow&
00010 &\leftarrow& 01000 \\
&&  \uparrow &&&&&&  \downarrow && \\
&&  11010 &&&&&&    10011 && \\
&&  \uparrow &&&&&&\downarrow  && \\ 
&&   10000&&&&&&  11001 &&\\
&&   \uparrow &&&&&& \downarrow  && \\ 
01011&\rightarrow& 00001 &\leftarrow& 00111 &\leftarrow& 01110
&\leftarrow& 11100
&\leftarrow& 10101, \\
01001 &\rightarrow& 00000 &\rightarrow& 10010 &\rightarrow& 11011
&\rightarrow&
11101 &\leftarrow& 10111 \\
&&  \uparrow &&&&&& \downarrow && \\
&&  00101 &&&&&& 01100 && \\
&& \uparrow &&&&&& \downarrow && \\
&& 01111 &&&&&& 00110&& \\
&& \uparrow    &&&&&& \downarrow&&  \\
10100 &\rightarrow& 11110 &\leftarrow& 11000 &\leftarrow&
10001&\leftarrow& 00011
&\leftarrow& 01010. 
\end{array}
$$ 


\section*{2.5 Circular and skew-circular
transformations\label{s:CSCT}}
Let $\rho $ be the cyclic permutation $(1,2,..,n)$ of
$\mathbf{N}$. 
The
transformation $\rho $ defined by the P\'{o}lya action on
$\mathbf{Q}^{n}$ is the right rotation of  coordinates of
$\mathbf{Q}^{n}$, that is, $\rho (x_{1}, x_{2},..,x_{n}) =
(x_{n},x_{1},..,x_{n-1})$ for every $x = (x_{1},x_{2},..,x_{n})
\in  \mathbf{Q}^{n}$.  A transformation $F$ of $\mathbf{Q}^{n}$
is called \emph{circular}, if $F\rho  = \rho F$.  A
transformation $G$ is isometrically similar to a circular
transformation, if and only if $G$ satisfies $G\sigma  = \sigma
G$ for some $n$-cyclic permutation $\sigma  = (s_{1},
s_{2},..,s_{n})$.

If $F$ and $G$ are circular, then clearly $FG$
is also circular.  If $F$ is circular and one-to-one, then
$F\rho = \rho F$ i.e. $\rho ^{-1}F^{-1} = F^{-1}\rho ^{-1}$.  By
applying $\rho $ to the left and right of each side of the last
equation, we obtain $F^{-1}\rho $ = $\rho F^{-1}$, so that $F^{-
1}$ is also circular.

    Let $F = (F_{1},...,F_{n})$ be a transformation of
$\mathbf{Q}^{n}$, where $F_{i} = p_{i}F$.  Then $\rho F =
(F_{n},
F_{1},...,F_{n-1})$, while $F\rho  = (F_{1}\rho , F_{2}\rho
,...,F_{n}\rho ) = (\rho ^{-1}F_{1},\rho ^{-1}F_{2},...,\rho ^{-
1}F_{n})$  Therefore, $F$ is circular if and only if $F_{i} =
\rho F_{i-1}$ for every $i$, that is, 
$$
        F_{i} = \rho ^{i-1}F_{1}
\eqno (2.5.1) 
$$
for every $i$.  Further,\\

\textbf{Proposition 2.5.1}  A self-dual transformation $F =
[f_{1},...,f_{n}]$, where $f_{i} = p_{i}\cdot \neg F_{i}$, is
circular if and only if
$$
         f_{i} = \rho ^{i-1}f_{1}.
\eqno (2.5.2) 
$$

\begin{proof}  From (2.5.1) it follows that $F$ is circular and
self-dual, if and only if
\begin{eqnarray*}
F &=& [p_{1}\cdot \neg F_{1},p_{2}\cdot \neg (\rho
F_{1}),..,p_{i}\cdot \neg (\rho ^{i-1}F_{1},..,p_{n}\cdot \neg
(\rho ^{n-1}F_{1})]\\
    &=& [p_{1}\cdot \neg F_{1},\rho (p_{1}\cdot \neg
F_{1}),..,\rho ^{i-1}(p_{1}\cdot \neg F_{1}),..,\rho ^{n-
1}(p_{1}\cdot \neg F_{1})]
\end{eqnarray*}
Therefore, $F$ is circular and self-dual if and only if (2.5.2)
holds. 
\end{proof}

We briefly write
$$
        F = \langle f \rangle 
$$
for $F = [f,..,\rho ^{i-1}f,...,\rho ^{n-1}f]$, where
$p_{1}\cdot
f = f$.  From (2.4.4),
$$
        \mathrm{Var}(F) = 2n|f|.
\eqno (2.5.3) 
$$

\textbf{Theorem 2.5.2}  Let $F = \langle f \rangle $ be a
circular
self-dual transformation.  Then (i) $F$ is isometrically
equivalent to a circular minimal self-dual transformation.  (ii)
If $|f| \leq  2^{n-3}$ then $F$ is minimal.  (iii) If
$|f| < 2^{n-3}$, then $F$ is uniquely minimal.

\begin{proof}  Let $F = (F_{1},...,F_{n})$, where $F_{i} =
p_{i}F$.  (i) Suppose $|p_{1}\cdot \neg F_{j}| < 
|p_{1}\cdot \neg F_{1}|$.  If $\sigma  = \rho ^{-j+1}$, then
$\sigma F$ is circular, and $(\sigma F)_{1} =F_{j}$, so that
$|p_{1}\cdot \neg (\sigma F)_{1}| =|p_{1}\cdot \neg
F_{j}| < |p_{1}\cdot \neg F_{1}|$.  Therefore, by
(2.5.3) we have $\mathrm{Var}(\sigma F) < \mathrm{Var}(F)$.  Let
a new $F$ be the $\sigma F$.  Similarly, if $|p_{1}\cdot
F_{j}| < |p_{1}\cdot \neg F_{1}|$, then $(\sigma
\bar{\neg})F$ is circular, and $\mathrm{Var}((\sigma
\bar{\neg})F) <
\mathrm{Var}(F)$.  Then let a new $F$ be the $(\sigma
\bar{\neg})F$. 
Repeat the above procedure until there is no such $j$ as above. 
Then we obtain a transformation that is isometrically equivalent
to $F$, circular, and minimal.\\
(ii) Let $j \ne  1$.  We have
\begin{eqnarray*}
    |p_{1}\cdot \neg F_{j}| &=& |p_{1}\cdot
p_{j}\cdot \neg F_{j}| + |p_{1}\cdot \neg p_{j}\cdot
\neg F_{j}| \\
         &=& |\bar{\neg}(p_{1}\cdot p_{j}\cdot \neg
F_{j})| + |p_{1}\cdot \neg p_{j}\cdot \neg F_{j}| \\
         &=& |\neg p_{1}\cdot \neg p_{j}\cdot F_{j}| +
(|p_{1}\cdot \neg p_{j}| -|p_{1}\cdot \neg p_{j}\cdot
F_{j}|),
\end{eqnarray*}
because $F_{j}$ is self-dual.  Therefore,
$$
    |p_{1}\cdot \neg F_{j}| \geq  2^{n-2} - |f|,
$$
since $|p_{1}\cdot \neg p_{j}| = 2^{n-2}$ and $|\neg
p_{1}\cdot \neg p_{j}\cdot F_{j}| + |p_{1}\cdot \neg
p_{j}\cdot F_{j}| = |\neg p_{j}\cdot F_{j}| = |f|$.  Similarly
$|p_{1}\cdot F_{j}| \geq 
2^{n-2}-|f|$ and $|p_{1}\cdot F_{1}| = 2^{n-1}-|f|$. 
By (i), there exists an isometry $T$ such that $TF$ is minimal,
circular, and self-dual.  Therefore, if $|f| \leq  2^{n-
3}$, then $\mathrm{Var}(TF) \geq  2n\cdot (2^{n-2}-|f|)
\geq  2n\cdot (2^{n-2}-2^{n-3}) = 2n\cdot 2^{n-3} \geq
2n|f|  = \mathrm{Var}(F)$, so that $F$ is minimal.\\
(iii) is clear from the proof of (ii).
\end{proof}


\textbf{Example 2.5.3}  $n$ is even ($n = 2m$). $F = \langle f
\rangle $,
$$
        f = p_{1}\cdot \cdot \cdot p_{ m}\cdot \neg p_{m+1}\cdot
\cdot \cdot \neg p_{2m}.                 
$$
$\mathrm{GRAPH}(F)$ consists of loops and one $n$-cycle, which
is
$$
    1\cdot \cdot \cdot 10\cdot \cdot \cdot 0 \rightarrow 
01\cdot
\cdot \cdot 10\cdot \cdot \cdot 0 \rightarrow  ...
        \rightarrow  1\cdot \cdot \cdot 10\cdot \cdot \cdot 01
\rightarrow  1\cdot \cdot \cdot 10\cdot \cdot \cdot 0.
$$
$F$ is uniquely minimal for $n \geq 4$.\\

In later chapters we will encounter some self-dual
transformations $F$ of $\mathbf{Q}^{n}$ which are not circular
but commutative with $\rho n^{-}$, that is, $F\rho n^{-} = \rho
n^{-}F$.  We call such a transformation skew-circular. 
Skew-circular transformations are
self-dual, since $(\rho n^{-})^{n} = \bar{\neg}$.\\

\textbf{Proposition 2.5.4}  A self-dual transformation $F =
[f_{1},...,f_{n}]$, where $f_{i} = p_{i}\cdot \neg F_{i}$, is
skew-circular if and only if 
$$
        f_{i} = (\rho n^{-})^{i-1}f_{1} \; \mbox{for every}\;  i.
$$

\begin{proof}  Let $F = (F_{1},...,F_{n})$ be a self-dual
transforma-tion, where $F_{i} = p_{i}F$.  Then $\rho n^{-}F =
(\neg F_{n},F_{1},...,F_{n-1})$, while $F\rho n^{-} = (F_{1}\rho
n^{-},F_{2}\rho n^{-},...,F_{n}\rho n^{-})$.  Therefore, $F$ is
commutative with $\rho n^{-}$ if and only if 
\begin{eqnarray*}
F_{1} &=& \neg F_{n}(\rho n^{-})^{-1} = \neg \rho n^{-}F_{n}, \\
    F_{2} &=& F_{1}(\rho n^{-})^{-1} = \rho n^{-}F_{1},\\
     F_{3} &=& F_{2}(\rho n^{-})^{-1} = (\rho n^{-})^{2}F_{1},\\
        & &    . . . . . \\
    F_{n} &=& F_{n-1}(\rho n^{-})^{-1} = (\rho n^{-})^{n-1}F_{1},
\end{eqnarray*}
From the last equation, it follows that $\rho n^{-}F_{n} = (\rho
n^{-})^{n}F_{1} =  \bar{\neg}F_{1} =\neg F_{1}$, which is the
first equation.  Therefore, $F$ is commutative with $\rho n^{-}$
if
and only if $F_{i} = (\rho n^{-})^{i-1}F_{1}$ for every $i$.  If
F
is represented as $F = [f_{1},...,f_{n}]$, then this is
equivalent to
\begin{eqnarray*}
        f_{i} &=& p_{i}\cdot \neg F_{i} = p_{i}\cdot \neg (\rho
n^{-})^{i-1}F_{1}\\
            &=& (\rho n^{-})^{i-1}p_{1}\cdot (\rho n^{-})^{i-
1}(\neg F_{1})\\
            &=& (\rho n^{-})^{i-1}(p_{1}\cdot \neg F_{1})\\
            &=& (\rho n^{-})^{i-1} f_{1}.
\end{eqnarray*}
\end{proof}

$F = [f,..,(\rho n^{-})^{i-1}f,...,(\rho n^{-})^{n-1}f]$ , where
$p_{1}\cdot f = f$, is hereafter briefly denoted by
$$
        F = \langle\langle f\rangle\rangle .
$$
Then (2.5.3) also holds.\\     

\textbf{Example 2.5.5}  $F = \langle\langle f\rangle\rangle $,
$$
        f = p_{1}\cdot \cdot \cdot p_{i}\cdot \cdot \cdot p_{n}.
$$
$\mathrm{GRAPH}(F)$ consists of loops and one $2n$-cycle, for
example, for $n = 4$,
$$
\begin{array}{ccccccc}
    1111& \rightarrow & 0111&\rightarrow & 0011& \rightarrow& 
0001 \\
     \uparrow &&&&&& \downarrow\\
   1110& \rightarrow& 1100& \rightarrow& 1000& \rightarrow&
0000\\
    1101\partial ,&&  1011\partial , && 1001\partial , 
&&1010\partial ,   \\
   0101\partial , &&0110\partial , &&0010\partial
,&& 0100\partial .
\end{array}
$$
A transformation isometrically similar to this transformation was
first given by Masters and Mattson (1966).\\

Let $T$ be an isometry of $\mathbf{Q}^{n}$.  As described in
Section 2.1, $T$ is uniquely expressed as a product $T = \tau
J^{-}$ of a permutation $\tau $ and a complementation $J^{-}$. 
Let $T$ be circular, then, by definition, $\tau J^{-}\rho $ =
$\rho \tau J^{-}$.  Therefore, by (2.1.1), $\tau \rho (\rho ^{-
1}J)^{-} = \rho \tau J^{-}$, so that $\tau \rho  = \rho \tau $
and $\rho ^{-1}J = J$.  The first equation implies $\tau $ is a
linear permutation of slope 1, i.e. $\tau  = \rho ^{k}$ for some
$k \in  \mathbf{Z}_{n}$.   From the second equation follows $J =
\mathbf{N}$ or $\emptyset $.  Therefore
$$
        T = \rho ^{k} \; \mbox{or}\;  T = \rho ^{k}\bar{\neg} \;
\mbox{for
some}\;  k.
\eqno (2.5.4) 
$$
Conversely, it is clear that any $T$ that satisfies (2.5.4) is a
circular transformation.
    Next, we determine skew-circular isometries.  First, if
$\tau
$ is a permutation of $\mathbf{N}$, and if $L$ and $M$ are
subsets of
$\mathbf{N}$,
then it is clear that 
$$
        \tau (L\dot{+}M) = \tau (L)\dot{+}\tau (M).
\eqno (2.5.5) 
$$

\textbf{Lemma 2.5.6}  Let $\rho  = (1,2,..,m)$ and $i \ne  j$ are
elements of $\mathbf{N}_{m}$.   Then
$$
        X\dot{+}\rho ^{-1}X = \{ i,j\},
\eqno (2.5.6) 
$$
if and only if $X = \{ i+1,...,j\}$ or $X = \{ j+1,...,i\}$.

\begin{proof}  The if part is clear.  To prove the only if part,
suppose that both $X$ and $Y$ are solutions of (2.5.6).  Then
$X\dot{+}\rho ^{-1}X = Y\dot{+}\rho ^{-1}Y$, so that
$(X\dot{+}\rho ^{-1}X)\dot{+}(Y\dot{+}\rho ^{-1}Y) = \emptyset
$,
i.e. $(X\dot{+}Y)\dot{+}\rho ^{-1}(X\dot{+}Y) = \emptyset $ by
(2.5.5).  Therefore, $X\dot{+}Y = \emptyset $ or $X\dot{+}Y =
\mathbf{N}_{m}$, i.e. $Y = X$ or $Y = X^{c}$.
\end{proof}

Let $T = \tau J^{-}$ be a skew-circular isometry of
$\mathbf{Q}^{n}$.  Then, by definition, $\tau J^{-}\rho n^{-} =
\rho n^{-}\tau J^{-}$.  Therefore, by (2.1.1), $\tau \rho {\rho
^{-1}J\dot{+}{n}}^{-} = \rho \tau {J\dot{+}{\tau ^{-1}n}}^{-}$,
so that $\tau \rho  = \rho \tau $ and $\rho ^{-1}J\dot{+}{n} =
J\dot{+}{\tau ^{-1}n}$.  From the first equation follows $\tau 
=
\rho ^{k}$ for some $k \in  \mathbf{Z}_{n}$.   Then, from the
second equation follows $J\dot{+}\rho ^{-1}J = \{ n-k\}\dot{+}\{
n\}$. Therefore, by Lemma 2.5.6, $J = \{ n-k+1,...,n\}$ or $J =
\{
1,...,n-k\}$, so that  
$$
    T = \rho ^{k}\{n-k+1,...,n\}^{-} \; \mbox{or}\;  T = \rho
^{k}\{1,...,n-k\}^{-} \; \mbox{for some}\; k.
\eqno (2.5.7) 
$$
Conversely, it is clear that any $T$ satisfies (2.5.7) is a
skew-circular transformation.  Thus we have obtained the
following proposition.\\

\textbf{Proposition 2.5.7}  Let $T$ be an isometry of
$\mathbf{Q}^{n}$.  Then (i) $T$ is circular if and only if $T =
\rho ^{k}$  or $T = \rho ^{k}\bar{\neg}$ for some $k$.  (ii) $T$
is skew-circular if and only if $T = \rho
^{k}\{n-k+1,...,n\}^{-}$ or
$T = \rho ^{k}\{1,...,n-k\}^{-}$ for some $k$. \\


\section*{2.6. Flow graphs \label{s:FT}}
Let a transformation $F$ of $\mathbf{Q}^{n}$ be commutative with
any element $\tau$ of a
group $\mathbf{G}$ acting on $\mathbf{Q}^{n}$.  For a subset $S$
of $\mathbf{Q}^{n}$,
let $[S]$ denote $\mathrm{Orb}_{\mathbf{G}}S$.  Then, a
transformation $F^{\sim }$ of
the orbit set  $\{ [x] \mid x \in  \mathbf{Q}^{n}\}$ is naturally
defined by $F^{\sim }[x] =
[Fx]$.  We call $F^{\sim }$ the \emph{flow} of $F$.  For example,
if $F$ is self-dual and
circular,
then $\mathbf{G}$ is $\langle \rho , \bar{\neg}\rangle$, that is,
the group generated by the
rotation $\rho$ and complementation $\bar{\neg}$. 

     An outline of the flow $F^{\sim }$ can be described by a
\emph{flow graph} with an arc
set $A$  such that (i) If $(X,Y) \in  A$, then $X$ and $Y$ are
orbits, that is, $X = [C]$
and $Y = [D]$ for some $C$ and $D$, and $X \subseteq
\mathrm{Car}F$ and $FX \cap Y
\ne \emptyset$; 
(ii)  If $x \in \mathrm{Car}F$, then there exists an arc $(X,Y)
\in A$ such that $x \in  X$
and $Fx \in  Y$;
(iii) Any cycle $X \rightarrow  ... \rightarrow  Z \rightarrow 
X$  (including a loop) of
$\mathrm{GRAPH}(F^{\sim })$ is a subgraph of the flow graph.
(iv) Any cycle $X \rightarrow  ... \rightarrow  Z \rightarrow  X$
(including a loop) of the
flow graph is a cycle of $\mathrm{GRAPH}(F^{\sim })$. 

 Note that all cycles and loops as well as some asymptotic
properties of $F^{\sim }$ are
described by this flow graph. 
In particular, if $F$ is one-to-one, then $F^{\sim }$ is
completely represented.  In the
following example, a Boolean function is expressed with skipped
$p$; for example, $1\cdot
2\cdot (\neg 3\vee 4)$ denotes $p_{1}\cdot p_{2}\cdot (\neg
p_{3}\vee p_{4})$.  A Boolean
function $f$ also denotes the set $f^{-1}(1)$, and $\sim $
denotes $\sim_{\langle \rho, \bar{\neg} \rangle }$.\\

\textbf{Example 2.6.1}  Let $F = \langle f \rangle $, $f = 1\cdot
2\cdot 3\neg 6$, be a transforma-tion of $\mathbf{Q}^{6}$. 
Since $F$ is circular self-dual,
 $\mathrm{Car}F = [f]$.
  We have
\begin{eqnarray*}
    f = 1\cdot 2\cdot 3\neg 6 &=& 1\cdot 2\cdot 3\cdot (4\vee
5)\cdot \neg 6\cup 1\cdot 2\cdot 3\cdot \neg 4\cdot \neg 5\cdot
\neg 6,\\
    1\cdot 2\cdot 3\cdot (4\vee 5)\cdot \neg 6) &\rightarrow
_{F}& \neg 1\cdot 2\cdot 3\cdot (4\vee 5)\cdot \neg 6,\\
    1\cdot 2\cdot 3\cdot \neg 4\cdot \neg 5\cdot \neg 6)
&\rightarrow _{F}& \neg 1\cdot 2\cdot 3\cdot 4\cdot \neg 5\cdot
\neg 6 \sim  1\cdot 2\cdot 3\cdot \neg 4\cdot \neg 5\cdot \neg
6,\\
    \neg 1\cdot 2\cdot 3\cdot (4\vee 5)\cdot \neg 6
         &=& \neg 1\cdot 2\cdot 3\cdot 4\cdot \neg 5\cdot \neg
6\cup \neg 1\cdot 2\cdot 3\cdot 4\cdot 5\cdot \neg 6\cup \neg
1\cdot 2\cdot 3\cdot \neg 4\cdot 5\cdot \neg 6,\\
    \neg 1\cdot 2\cdot 3\cdot 4\cdot 5\cdot \neg 6 &\rightarrow
_{F}& \neg 1\cdot \neg 2\cdot 3\cdot 4\cdot 5\cdot \neg 6 \sim 
1\cdot 2\cdot 3\cdot \neg 4\cdot \neg 5\cdot \neg 6,\\
     \neg 1\cdot 2\cdot 3\cdot \neg 4\cdot 5\cdot \neg 6 &\notin
& \mathrm{Car}F.
\end{eqnarray*}
Therefore, a flow graph of $F$ is
$$
    [1\cdot 2\cdot 3\cdot (4\vee 5)\neg 6] 
 \begin{array}{lc}
    &  [1\cdot 2\cdot 3\cdot \neg 4\cdot \neg 5\cdot \neg
6]\partial  \\
   \nearrow & \uparrow \\
 \rightarrow & [\neg 1\cdot 2\cdot 3\cdot 4\cdot 5\cdot \neg 6]\\ 

   \searrow & \\
   & [\neg 1\cdot 2\cdot 3\cdot \neg 4\cdot 5\cdot \neg 6],
 \end{array}
$$
that is,
$$
    [1\cdot 2\cdot 3\cdot (4\vee 5)\neg 6] 
 \begin{array}{lc}
    &  [1\cdot 2\cdot 3\cdot \neg 4\cdot \neg 5\cdot \neg
6]\partial  \\
   \nearrow & \uparrow \\
   \rightarrow & [1\cdot 2\cdot 3\cdot 4\cdot \neg 5\cdot \neg 6]
\\  
   \searrow & \\
   & [1\cdot 2\cdot \neg 3\cdot 4\cdot \neg 5\cdot \neg 6].
 \end{array}
$$

\end{document}