# Separating Circuits: Switching Lemmas and Random Restrictions

Bruce Changlong Xu
May 31st, 2021

###### Abstract

The field of Circuit Complexity utilises careful analysis of Boolean Circuit
Functions in order to extract meaningful information about a range of
complexity classes. In particular, the complexity class $P/\text{Poly}$ has
played a central role in much of the historical attempts to tackle the problem
of whether solution and verification are equivalent i.e. the central $P$
versus $NP$ problem. Whilst circuits can potentially be easier to analyse than
Turing Machines due to their non-uniform nature of computation (program size
is allowed to depend on the input size), it is notoriously hard to establish
lower bounds for them. In this report, we will touch upon several results
published by Hastad, Sipser and Razborov that will highlight a dynamic
interplay between circuit complexity and many of the central ideas of modern-
day complexity theory, and in particular the central importance of Hastad’s
Switching Lemma.

Keywords: Natural Proofs, Circuit Complexity, Lower Bounds, P-Poly, Uniform
and Non-uniform Complexity, Hastad’s Switching Lemma, Restriction and
Polynomial Methods, Literature Review

###### Contents

  1. 1 Introduction and Context
    1. 1.1 Historical Context
    2. 1.2 Setup and Definitions
    3. 1.3 Shannon’s Proof
    4. 1.4 Karl-Lipton Theorem
  2. 2 Hastad’s Switching Lemma [AB07]
    1. 2.1 Statement of the Lemma
    2. 2.2 Depth $2$ Circuit Computing Parity
    3. 2.3 Lower-bound on PARITY
    4. 2.4 Matching Upper Bound on Parity
    5. 2.5 Proof of the Switching Lemma
    6. 2.6 Proof that PARITY $\notin$ $AC^{0}$
  3. 3 Beyond Canonical Hastad [Bea94]
    1. 3.1 Other Restriction Methods
    2. 3.2 Consequences of Parity not in $AC^{0}$
    3. 3.3 Comparison with Polynomial Method

##  1 Introduction and Context

###  1.1 Historical Context

Circuit complexity is a branch of Computational Complexity theory in which
Boolean functions are classified according to the size or depth of the Boolean
Circuits that compute them. Where the circuit-size complexity of a Boolean
function $f$ is the minimal size of any circuit computing $f$. The circuit-
depth complexity of a Boolean function $f$ is the minimal depth of any circuit
computing $f$. Boolean functions and the corresponding complexity behind these
functions have been under thorough study since the publication of Claude
Shannon’s seminal paper in the year of $1949$, which demonstrated that almost
all Boolean Functions on $n$ variables require circuits of size $O(2^{n}/n)$.

Our motivations for studying circuit complexity are multi-faceted. Circuit
complexity is a reasonable measure for the difficulty measure for functions
that take only finitely many inputs i.e. through the lens of circuit
complexity, we are able to deduce very meaningful conclusions about finite-
input problems - we have more control over the study of program size of
algorithms on finite bit instances than if we were simply analyzing the same
problem through the lens of Turing Computation. There are also close
connections between circuit complexity, de-randomisation and by extension the
complexity class BPP.

The best known lower bound on the circuit size for a problem in NP is
currently $4.5n-o(n)$, [AB07] this is not very strong and much lower than
expected, yet we are still stuck at this stage. For the Polynomial Hierarchy,
better lower bounds are known - for example for every $k>0$, some language in
the Polynomial Hierarchy require circuits of size $\Omega(n^{k})$.

Whilst proving circuit lower bounds is notoriously difficult, super-polynomial
lower bounds have been proved under certain restrictions on the family of
circuits used. The first function for which such bounds were obtained was the
parity function, which computes the sum of input bits modulo $2$. The proof
that PARITY was not contained in the complexity class $AC^{0}$ was first
established independently by Ajitai in $1982$ and by Furst, Saxe and Sipser in
$1984$, after which in $1987$ Hastad proved the even stronger result that any
family of constant-depth circuits computing the parity function require
exponential size, where he applied his famous and powerful switching lemma,
utilising the key idea of random restrictions, which Rossman, Servedio and Tan
extended to the idea of random Projections to prove an average-case depth
hierarchy theorem for Boolean Circuits [RST15].

###  1.2 Setup and Definitions

######  Definition 1.

$t$-CNF is an AND of clauses of width at most $t$. A clause of width $t$ is an
OR of $t$ literals. For example, $x_{1}\lor\bar{x_{2}}\lor x_{4}$ is a clause
of width $3$, and $(x_{1}\lor x_{2})\land(\bar{x}_{1}\lor\bar{x}_{2})$ is a
$2$-CNF and another example of a $3$-CNF:

$(A\lor\neg B\lor\neg C)\land(\neg D\lor E\lor F)$

######  Definition 2.

$s$-DNF is an OR of disjuncts of width at most $s$, where a disjunct of width
$s$ is an AND of $s$ literals, with an example below:

$(A\land\neg B\land\neg C)\lor(\neg D\land E\land F)$

######  Definition 3.

A restriction $\rho$ is a mapping from $\\{x_{1},\cdots,x_{n}\\}$ to
$\\{0,1*\\}$. A random restriction $\rho\in R(p,q)$, $0\leq p,q\leq 1$ is a
random restriction such that:

$P_{\rho}[\rho(x_{i})=*]=p$ $P_{\rho}[\rho(x_{i})=0]=(1-p)q$
$P_{\rho}[\rho(x_{i})=1]=(1-p)(1-q)$

independently, for each $i$.

######  Definition 4.

$AC^{k}$ is the class of functions computable by polynomial size and $O((\log
n)^{k})$ depth circuits over infinitely many AND and infinitely many OR and
NOT gates

######  Definition 5.

$NC^{k}$ is the class of functions computable by polynomial size and $O((\log
n)^{k})$ depth circuits over $2$-AND and $2$-OR and NOT gates

In particular we know that
$\text{AC}^{k}\subseteq\text{NC}^{k+1}\subseteq\text{AC}^{k+1}$

######  Definition 6.

The complexity class $P/\text{Poly}$ is defined as the set of languages
recognised by a polynomial-time Turing Machine with polynomial-bounded
advice111We say that a Turing Machine has access to an advice family
$\\{a_{n}\\}_{n\geq 0}$ where each $a_{n}$ is a string if while computing on
an input of size $n$, the machine is allowed to examine $a_{n}$. The advice is
said to have polynomial size if there is a $c\geq 0$ such that $|a_{n}|\leq
n^{c}$ function and its relation with circuit complexity is encoded in the
fact that:

$P_{/\text{poly}}=\cup_{c\in\mathbb{N}}\text{SIZE}(n^{c})$

######  Definition 7.

###  1.3 Shannon’s Proof

We present Shannon’s beautiful non-constructive proof below.

Shannon (1949) There is a constant $c$ such that every $n$-ary Boolean
Function has Circuit Complexity at most $2^{n}/cn$

###### Proof.

Fix an $n$-ary function $F:\\{0,1\\}^{n}\to\\{0,1\\}$. Let
$x=(x_{1},x_{2},\cdots,x_{n})$ denote the input vector for some integer $k$ to
be specified later and define $y=(x_{1},\cdot,sx_{k})$ and
$z=(x_{k+1},\cdots,x_{n})$.

We begin by constructing a $2^{k}\times 2^{n-k}$ truth table for $F$, where
each row is specified by a possible value of $y$ and each column by a possible
value of $z$. Suppose that there are only $t$ different column vectors in this
matrix. The inequality $t\leq 2^{n-k}$ is obvious; less obvious but still
trivial is the inequality $t\leq 2^{t}$. Let $F_{i}(z)=1$ if column $z$ has
the the $i$-th pattern and $0$ otherwise. Similarly, let $G_{i}(y)$ be the
function specified by the $i$-th column vector. Then we can write:

$F(x)=F(y,z)=\cup_{i=1}^{n}G_{i}(y)\land F_{i}(z)$

Suppose for the moment that all the $1$ in this table are restricted to $s$ of
the $2^{k}$ rows. This immediately implies that $t\leq 2^{s}$. Under this
assumption, we can build a circuit for $F$ as follows. The inputs are
connected to two binary-to-positional converters $B_{k}$ and $B_{n-k}$ which
requires $2^{k}+2^{n-k}$ gates. For each $i$ between $1$ and $t$, we add two
trees of ORs connected by a single AND to compute $F_{i}(y)\land G_{i}(z)$ for
each $i$ this requires $2^{k}+2^{n-k}+1$ gates. Finally, we connect all these
with another tree of $t\leq 2^{s}$ OR gates. The total number of gates used in
this special case is at most $2(2^{k}+2^{n-k})+2^{s}+1$.

Now back to the general case. We can write any $n$-ary function $F$ as a dis-
junction $2^{k}/s$ different $n$-ary functions, each of which has a truth
table with at most $s$ non-zero rows. To construct a circuit for $F$, we build
a circuit for each of its $s$-row components, sharing a single pair of binary-
to-positional converters. The total gate count for this construction is at
most:

$2^{k}+2^{n-k}+\frac{2^{k}}{s}(2^{k}+2^{n-k}+2^{s}+1)=2^{k}+2^{n-k}+\frac{2^{n}+2^{k}(2^{s}+s^{k}+1)}{s}$

Finally, we are free to choose the parameters $k$ and $s$ to minimize this
gate count. If we take $k=2\log n$ and $s=n-2\log n$, then the total gate
count is at most:

$n^{2}+\frac{2^{n}}{n^{2}}+\frac{2^{n}+n^{2}(2^{n}/n^{2}+n^{2}+1)}{n-2\log
n}=n^{2}+\frac{2^{n}}{n^{2}}+\frac{2^{n+1}+n^{4}+n^{2}}{n-2\log
n}=O(\frac{2^{n}}{n})$

∎

###  1.4 Karl-Lipton Theorem

The Karl-Lipton Theorem justifies why circuit lower bounds is a viable way to
attack the $P$ versus $NP$ problem.

Karl-Lipton Theorem: $\text{PH}\neq\sum_{2}\Rightarrow\text{NP}\subseteq
P_{\text{/poly}}$

###### Proof.

Suppose $\text{NP}\subseteq P_{/\text{poly}}$. We will show that this implies
$\text{PH}\subseteq\sum_{2}$. Note that $\text{PH}\subseteq\sum_{2}$ and
$\prod_{2}\subseteq\sum_{2}$ are equivalent; if the latter were true then by
swapping quantifier order, we have that $\sum_{3}=\sum_{2}$, collapsing the
Polynomial Hierarchy.

By assumption that $\text{NP}\subseteq P_{/\text{poly}}$ there exists a
polynomially sized circuit family $\\{C_{n}\\}$, which decides SAT. This
implies that there exists a polynomial size circuit family $\\{C_{*n}\\}$
which, given a boolean formula $\phi$, finds a satisfying assignment for it.

We construct $\\{C_{*n}\\}$ in the following way: we choose a free variable
and substitute $1$ or $0$ for it, then run the decider. If the decider says
that one of these boolean formulas has a satisfying assignment, repeat this
process on another free variable. When there are no more free variables, we
will have substituted a satisfying assignment into $\phi$.

Let $L\in\prod_{2}$. Then $x\in L\iff\forall u\exists v\text{ s.t.
}\phi(x,u,v)=0$

Then $\exists C*\forall u\phi(x,u,C*(x,u))=0$. That is, there exists a circuit
which outputs an unsatisfying assignment for $\phi$ for any $u$. Then
$L\in\sum_{2}$ and the theorem is proven.
∎

##  2 Hastad’s Switching Lemma [AB07]

Arguments using restrictions (partial assignments to input variables) to
simplify unbounded fan-in Boolean circuits have been quite successful for
obtaining lower bounds on circuit size and depth, oracles to separate
complexity classes, lower bounds on time, processors and memory of PRAMs as
well as on the complexity of proofs in bounded-depth proof systems.

Ultimately the key intuition behind Hastad’s switching lemma is to show that
an AND of small ORs can be written as an OR of small ANDs if an appropriate
restriction is applied. In particular, we can reduce the depth of formulas by
$1$ at the expense of reducing the number of input variables.

The core to their effectiveness is that they simplify the formulas without
completely trivialising the functions that are being computed. Therefore,
there is a certain element of creativity attributed to this choice of
restrictions, since one chooses a family of restrictions that is tailored to
the function being computed and argues that some member of the family has the
desired properties. As long as the random restriction is likely to kill a
clause, the switching lemma should work.

The history of switching lemmas traces back to Furst, Sax and Sipser, but in
this project we will be looking at the most powerful of these switching
lemmas, which is attributed to Hastad.

$\downarrow$

###  2.1 Statement of the Lemma

######  Theorem 1.

Let $f$ be some Boolean Function which can be written as some $t$-CNF. Then,
for any integer $s\geq 1$, any $p\in[0,1]$ we have that:

$P_{\rho\in R(p,1/2)}[f|_{\rho}\text{is not }s-\text{DNF}]\leq(5pt)^{s}$

Here $f_{\rho}$ is not $s$-DNF means $f|_{\rho}$ can not be written as $s$-DNF

The argument of Hastad’s switching lemma involves the probabilistic method, in
particular we argue that the probability that a restriction from the family
fails to have the desired properties is strictly less than $1$. For example,
we can consider an OR of small ANDs and each term in turn. Essentially a term
that is falsified by a restriction does not contribute any variables to the
AND of small ORs and for each term that is not falsified it is more likely
that the term is satisfied than that any variable is contributed in the AND of
small ORs.

Note that one very important feature of this lemma is that the probability on
the right hand side of the inequality $(5pt)^{s}$ does not depend on the
number of variables. The notion of the random restriction is actually key to
Hastad’s Switching Lemma. Indeed if we consider the threshold function
$\text{Th}_{k}^{n}(x)$, which is $1$ if and only if:

$x_{1}+x_{2}+\cdots+x_{n}\geq k$

We can readily see that $\text{Th}_{k}^{n}(x)$ can be written as $k$-DNF and
$(n-k)$-CNF but not as a $(n-k-1)$-CNF. Indeed if $k$ is fixed and $n$ goes to
infinity, this example shows, in general, that $t$-CNF can not be written as
an $s$-DNF, where $s=s(t)$ only depends on $t$.

###  2.2 Depth $2$ Circuit Computing Parity

###  2.3 Lower-bound on PARITY

Theorem: For any $d\geq 2$, $\text{PAR}_{n}$ can not be computed by depth-$d$
size $2^{cn^{1/(d-1)}}$ circuit when $n$ is sufficiently large, where $c$ is a
reasonable constant, say $1/11$

###### Proof.

Assume for sake of contradiction that $\text{PAR}_{n}$ can be computed by some
depth $d$ size $S$ circuit $C(x)$, where

$S<2^{cn^{1/(d-1)}}$

and the constant $c$ will be determined later. Without loss of generality,
assume that our circuit $C(x)$ is already in standard form (depth $d$ size $S$
circuit can be transformed to standard form of depth $d$ size $dS$, for which
we only need to make the constant $c$ slightly larger, that is, $c+\epsilon$
for any $\epsilon>0$.

Now view $C(x)$ as a depth $d+1$ circuit by adding a dummy layer consist of
AND or OR gates of fan-in $1$ to the bottom, alternating each layer. The
motivation is to apply switching lemma for $t=1$. Indeed applying the
switching lemma to this circuit with parameter $t=1$, $s=(1+\delta)c_{H}\log
S$ and $p=1/(2c_{H})$ where $\delta>0$ is an arbitrarily small constant, and
$c_{H}$ denotes the constant $5$ in Hastad’s Switching Lemma. That is, we will
apply random restriction $\rho\in R(1/(2c_{H}),1/2)$. For each gate in the
second bottom layer, which is $1$-CNF or $1$-DNF with probability at least:

$1-(c_{H}pt)^{s}=1-(\frac{1}{2})^{(1+\delta)c_{H}\log S}\geq 1-S^{1-\delta}$

that gate can be written as $s$-DNF. If all the bottom gates can be switched,
we get a depth $d$ circuit of bottom fan-in $s=(1+\delta)c_{H}\log S$.

Now apply the random restriction $\rho_{i}\in R(p,1/2)$ where:

$p=1/(2c_{H}s)=1/(2(1+\delta)c_{H}\log S)$

for $i=1,2,\cdots,d-2$. For $\rho_{1}$, for each gate in the second bottom
layer, by switching lemma, with probability at least:

$1-(c_{H}pt)^{2}\geq 1-S^{1-\delta}$

this $t$-CNF can be converted to an $s$-DNF where $t=s=(1+\delta)\log S$. For
each $\rho_{i}$, the depth of the circuit is supposed to be reduced by $1$.
Finally, it remains to count the number of times we have applied the switching
lemma, which is at most $S$, the total number of gates in the original
circuit. Apply a union bound, with probability $\geq 1-S^{-\delta}\to 1$,
circuit $C(x)|_{\rho}$ can be converted to a depth $2$ size $S$ circuit where:

$\rho=\rho_{d-2}\circ\cdots\circ\rho_{0}\in R(1/(2c_{H}(2(1+\delta)\log
S)^{d-2}),1/2)$

Now that we have proved that $C(x)|_{\rho}$ can be written as a depth $2$ size
$S$ circuit with high probability, we observe that parity is still a parity
function or its negation after applying any restriction in possibly less
number of variables. let us count the number of free variables after applying
$p$. The expected number of free variables is:

$\frac{n}{2c_{H}(2c_{H}(1+\delta)\log S)^{d-2}}$

By the Chernoff bound, we claim:

$m=|\rho^{-1}(*)|>\frac{n}{2c_{H}(2c_{H}(1+2\delta)\log S)^{d-2}}$

with high probability. It is not difficult to prove that any depth $2$ circuit
computing $\text{PAR}_{m}$ should have bottom fan-in $m$, which implies that:

$(1+\delta)\log S\geq m\geq n/(2c_{H}(2c_{H}(1+3\delta)\log S)^{d-2})$

This implies that $S\geq 2^{n^{(d-1)}/((2+3\delta)c_{H})}$. Therefore, as long
as constant $c<1/(2c_{H})$, our theorem holds.

∎

###  2.4 Matching Upper Bound on Parity

Now we present an equivalent upper bound up to a constant factor for PARITY.
Indeed for depth $3$, we observe that:

$\text{PAR}_{n}(x_{1},\cdots,x_{n})=\text{PAR}_{m}(\text{PAR}_{m}(y_{1}),\cdots,\text{PAR}_{m}(y_{m}))$

where $m=\sqrt{n}$ and
$y_{1}=(x_{1},\cdots,x_{m}),y_{2}=(x_{m+1},\cdots,x_{2m})$ etc. For the
$\text{PAR}_{m}$ on the outside, write it as $m$-CNF of size $2^{m-1}+1$ and
for the $\text{PAR}_{m}$ inside, write it as $m$-DNF of size $2^{m-1}+1$ which
is a depth $4$ circuit of size

$(1+m)(2^{m-1}+1)\leq n2^{\sqrt{n}}$

To make it depth $3$, simply merge two layers in the middle, both of which are
OR gates and the size will not increase. Using the same argument we can prove:

######  Theorem 2.

For any $d\geq 2$, $\text{PAR}_{n}$ can be computed by depth $d$ circuit of
size at most

$n2^{n^{1/(d-1)}}$

Now if the depth $d\geq\log n$¡ it turns out that there exists linear size
circuits computing $\text{PAR}_{n}$.

######  Theorem 3.

$\text{PAR}_{n}$ can be computed by depth $\lceil\log n\rceil$ circuit of size
$2n-1$

###### Proof.

Build a complete binary tree with $n$ leaves, corresponding to variables
$x_{1},\cdots,x_{n}$; all non-leaf nodes are $\text{XOR}=\text{PAR}_{2}$
gates. Since the depth of the binary tree is $d=\lceil\log n\rceil$, the
number of non-leaf nodes is:

$(n-2^{d-1})+2^{d-2}+2^{d-3}+\cdots+1=n-1$

For each XOR gate, we need $2$ gates to implement (recall that XOR can be
either written as $2$-CNF or $2$-DNF, and apply the gates merging technique
again) except for the top gate ($3$ gates are needed). The total number of
gates is $2(n-1)+1=2n-1$

∎

###  2.5 Proof of the Switching Lemma

Let the DNF $F=T_{1}\lor T_{2}\lor\cdots\lor T_{m}$. We restrict variables in
two stages.

Stage 1: Restrict variable with probability $\sqrt{p}$, $f\to f|_{\rho_{1}}$:

$x_{i}=\begin{cases}0\text{ with probability }\frac{1-\sqrt{p}}{2}\\\
x_{i}\text{ with probability }\sqrt{p}\\\ 1\text{ with probability
}\frac{1-\sqrt{p}}{2}\end{cases}$

In the first case, we consider terms with fan-in $\geq 4\log S$ we have that:

$P[\text{Any Term with fan-in}\geq 4\log S\neq
0]\leq(\frac{1+\sqrt{p}}{2})^{4\log S}\leq(\frac{2}{3})^{4\log
S}\leq\frac{1}{S^{3}}$

Therefore, we have that:

$P[\exists\text{Term with fan-in}\geq 4\log S\text{doesn't become
}0]\leq\frac{1}{S^{2}}$

In the second case, we consider terms with fan-in $\leq 4\log S$:

$P[T_{i}\text{depends on }c_{0}\text{variables}]\leq(4\log
S)^{c_{0}}(\sqrt{p})^{c_{0}}\leq\frac{1}{S^{3}}$

Therefore it must be the case that:

$P[\exists\text{term with fan-in}\leq 4\log S,\text{depends on }\geq
c_{0}\text{variables}]\leq\frac{1}{S^{2}}$

where $c_{0}$ is a constant depending on $c_{1}$, so now the DNF is also a
$c_{0}$-DNF.

Stage 2: Restrict variables in $f|_{\rho_{1}}$ with probability $\sqrt{p}$
$\to$ $f|_{\rho_{1}\cup\rho_{2}}$:

$x_{i}=\begin{cases}0\text{ with probability }\frac{1-\sqrt{p}}{2}\\\
x_{i}\text{ with probability }\sqrt{p}\\\ 1\text{ with probability
}\frac{1-\sqrt{p}}{2}\end{cases}$

In the first case, there are many disjoint terms $T_{1},\cdots,T_{l}$ with
$l\geq 3^{c_{0}}4\log S$ so that:

$P[T_{i}=1]\geq(\frac{1}{3})^{c_{0}}$ $P[T_{i}\neq
1]\leq(1-\frac{1}{3})^{c_{0}}$ $P[\exists T_{i}=1]\geq
1-((1-\frac{1}{3})^{c_{0}})^{l}=1-2^{-l/3^{c_{0}}}\geq 1-\frac{1}{S^{2}}$

In the second case, the maximum number of disjoint $T_{i}$’s is $\leq 4\log
S$.

Now if we select disjoint $T_{i}$’s greedily, we find that there exists a set
$H$ with $4c_{0}3^{c_{0}}\log S$ variables such that $\forall i$ we have that
$H\cap T_{i}\neq\emptyset$

To finish off the proof, we first restrict variables of $H$, and we can find a
constant $b$ such that the number of unset variables in $H\leq b$. We
subsequently restrict variables not in $H$, and use induction on $c_{0}$.

Now Razborov provided a simpler version of this proof which is presented in
$[AB07]$:

###### Proof.

We will present a more simplified proof of the Switching Lemma due to
Razborov. Let $R_{t}$ denote the set of all restrictions to $t$ variables,
where $t\geq n/2$. Then:

$|R_{t}|={n\choose t}2^{t}$

The set of bad restrictions $\rho$ \- those for which $D(f|_{\rho})>s$ is
greater than $s$ \- is a subset of these. To show that this subset is small,
we give a one-to-one mapping from it to the Cartesian product of three sets:
$R_{t+s}$, the set of restrictions to $(t+s)$ variables, a set
$\text{code}(k,s)$ of size $k^{O(s)}$ and the set $\\{0,1\\}^{s}$ (The set
$\text{code}(k,s)$ is explained below). This Cartesian product has size
${n\choose t+s}2^{t+s}k^{O(s)}2^{s}$. Thus the probability of picking a bad
restriction is bounded by:

$\frac{{n\choose t+s}2^{t+s}k^{O(s)}2^{s}}{{n\choose t}2^{t}}$

Intuitively, this ratio is small because $k,s$ are to be thought of as
constant and $t>n/2$, and therefore:

${n\choose t}2^{t}>>{n\choose t+s}2^{t+s}$

Formally, by using the correct constants as well as the approximation
${n\choose a}\sim(ne/a)^{a}$ we can upper-bound the ratio as follows:

$(\frac{7(n-t)k}{n})^{2}$

Therefore to prove the Switching Lemma it suffices to describe the one-to-one
mapping mentioned above. This uses the notion of a canonical decision tree for
$f$. We take the $k$-DNF circuit for $f$ and order its terms (i.e. the $\land$
gates in Figure $1$) arbitrarily and within each term we order the variables.
The canonical decision tree queries all the variables in the first term in
order, then all the variables in the second term, and so on until the function
value is determined.

Suppose that restriction $\rho$ is bad, that is, $D(f|_{\rho})>s$. The
canonical decision tree for $f|_{\rho}$ is defined in the same way as for $f$,
using the same order for terms and variables. Since the decision tree
complexity of $f|_{\rho}$ is at least $s$, there is a path of length at least
$s$ from the root to a least. This path defines a partial assignment to the
input variables; denote it by $\pi$. The rough intuition is that the one-to-
one mapping takes $\rho$ to itself plus $\pi$.

let us reason about restriction $\rho$. None of the $\land$ gates outputs $1$
under $\rho$, otherwise $f|_{\rho}$ would be determined and would not require
a decision tree. Some terms output $0$, but not all, since that would also fix
the overall output. Imagine walking down the path $\pi$. Let $t_{1}$ be the
first term that is not set to zero under $\rho$. Then $\pi$ must query all the
unfixed variables in $t_{1}$. Denote the part of path $\pi$ that deals with
$t_{1}$ by $\pi_{1}$; that is, $\pi_{1}$ is an assignment to the variables of
$t_{1}$. Since $f$ is not determined even after $s$ steps in $\pi$, we
conclude that $\pi_{1}$ sets $t_{1}$ to zero.

Let $t_{2}$ be the next term not yet set to zero by $\rho$ and $\pi_{1}$;
again, the path must set $t_{2}$ to zero. Let $\pi_{2}$ denote the assignment
to the variables of $t_{2}$ along the path. Then $\pi_{2}$ also sets $t_{2}$
to zero. This process continues until we have dealt with $m$ terms when $\pi$
has reached depth $s$. Each of these terms was not set by $\rho$ and, except
perhaps for $\pi_{m}$, is set to zero after $s$ queries in $\pi$. The disjoint
union of these $\pi_{i}$ terms contains assignments for at least $s$ variables
that were unfixed in $\rho$.

Our mapping will map $\rho$ to:

$([\rho\cup\sigma_{1}\cup\cdots\cup\sigma_{m}],c,z)$

where the term $\sigma_{i}$ is the unique set of assignments that makes
$t_{i}$ true, $c=c_{1}c_{2},\cdots,c_{m}$ is in $\text{code}(k,s)$ and
$z\in\\{0,1\\}^{s}$. In defining this mapping we are crucially relying on the
fact that there is only one way to make a term true, namely to set all its
literals to $1$.

To show that the mapping is one-to-one, we show how to invert it uniquely.
This is harder than it looks since a priori there is no way to identify $\rho$
from $\rho\cup\sigma_{1}\cup\cdots\cup\sigma_{m}$. The main idea is that the
information in $c$ and $z$ allows us to extract $\rho$ from the union.

Suppose that we are given the assignment
$\rho\cup\sigma_{1}\cdots\cup\sigma_{m}$. We can plug this assignment into $f$
and then infer which term serves as $t_{1}$. It is the first one to be set
true. The first $k$ bits of $c$, say $c_{1}$, are an indicator string showing
which variables in $t_{1}$ are set by $\sigma_{1}$. We can reconstruct
$\pi_{1}$ from $\sigma_{1}$ using the string $z$, which indicates which of the
$s$ bits fixed in the decision tree differ between the $\pi$ assignments and
the $\sigma$ assignments.

Having reconstructed $\pi_{1}$, we can work out which term is $t_{2}$: it is
the first true term under the restriction
$\rho\cup\pi_{1}\cup\sigma_{2}\cdots\cup\sigma_{m}$. The next $k$ bits of $c$,
denoted $c_{2}$, give us $\sigma_{2}$ and continue this process until we have
processed all $m$ terms and figured out what $\sigma_{1},\cdots,\sigma_{m}$
are. Thus we have figured out $\rho$, so the mapping is one-to0one.

Finally, we define the set $\text{code}(k,s)$: this is the set of all
sequences of $k$-bit binary strings in which each string has at least one $1$
bit and the total number of $1$ bits is at most $s$. It can be shown by
induction on $s$ that:

$|\text{code}(k,s)|\leq(\frac{k}{\ln 2})^{s}$

∎

###  2.6 Proof that PARITY $\notin$ $AC^{0}$

We will prove this theorem in two steps, the first of which we will show that
for any given $AC_{0}$ circuit, there is a low degree polynomial that
approximates the circuit, and the second of which we will show that parity
cannot be approximated by a low degree polynomial.

Lemma: Every function $f:\mathbb{F}_{p}^{n}\to\mathbb{F}$ is computed by a
unique polynomial of degree at most $p-1$ in each variable.

###### Proof.

Given any $a\in\mathbb{F}_{p}^{n}$, consider the polynomial:

$1_{a}=\prod_{i=1}^{n}\prod_{z\in\mathbb{F}_{p},z_{i}\neq
a_{i}}\frac{(X_{i}-z_{i})}{(a_{i}-z_{i})}$

We have that:

$1_{a}(b)=\begin{cases}1\text{ if }a=b\\\ 0\text{ else}\end{cases}$

Furthermore, each variable has degree at most $p-1$ in each variable. Now
given any function $f$, we can represent $f$ using the polynomial:

$f(X_{1},\cdots,X_{n})=\sum_{a\in\mathbb{F}_{p}^{n}}f(a)\cdot 1_{a}$

To prove that this polynomial is unique, note that the space of polynomials
whose degree is at most $p-1$ ine ach variable is spanned by monomials where
the degree in each of the variables is at most $p-1$, so it is a space of
dimension $p^{n}$ (i.e. there are $p^{p^{n}}$ monomials).

Similarly, the space of functions $f$ is also of dimension $p^{n}$. Therefore
the correspondence must be one to one.
∎

Suppose that we are given a circuit $C\in\text{AC}_{0}$, we build an
approximating polynomial gate by gate. The input gates are relatively
straightforward, $x_{i}$ is a good approximation to the $i$-th input.
Similarly, the negation of $f_{i}$ is the same as the polynomial $1-f_{i}$.

The difficult case is a function like $f_{1}\land f_{2}\land\cdots\land f_{t}$
which can be computed by a single gate in the circuit. The naive approach
would be to use the polynomial $\prod_{i=1}^{t}f_{i}$. However, this gives a
polynomial whose degree may be as large as the fan-in of the gate, which is
too large for our purposes.

We will use the following trick, let $S\subset[t]$ be a completely random set,
and consider the function $\sum_{i\in S}f_{i}$. Then we have the following
claim.

Claim: If there is some $j$ such that $f_{j}\neq 0$, then $P_{S}[\sum_{i\in
S}f_{i}=0]\leq 1/2$

###### Proof.

Observe that for every set $T\subseteq[n]-\\{j\\}$, it cannot be that both:

$\sum_{i\in T}f_{i}=0$

and:

$f_{j}+\sum_{i\in T}f_{i}=0$

Therefore at most half of the sets can give a non-zero sum. ∎

Now note that squaring turns non-zero values into $1$, so let us select
independent uniformly random sets $S_{1},\cdots,S_{t}\subseteq[t]$ and use the
approximation:

$g=1-\prod_{k=1}^{l}(1-(\sum_{i\in S_{k}}f_{i})^{2})$

Claim: If each $f_{i}$ has degree at most $r$, then $g$ has degree at most
$2lr$ and:

$P[g\neq f_{1}\lor f_{2}\lor\cdots\lor f_{t}]\leq 2^{-l}$

Overall, if the circuit is of depth $h$, and has $s$ gates, then this process
produces a polynomial whose degree is at most $(2l)^{h}$ that agrees with the
circuit on any fixed input except with probability $s2^{-l}$ by the union
bound. Therefore in expectation, the polynomial we produce will compute the
correct value on a $1-s2^{-l}$ fraction of all inputs.

Setting $l=\log^{2}n$ we obtain a polynomial of degree $\text{polylog}(n)$
that agrees with the circuit on all but one percent of the inputs.

Now it remains to prove the following theorem.

Theorem: Let $f$ be any polynomial over $\mathbb{F}_{3}$ in $n$ variables
whose degree is $d$. Then $f$ can compute the parity on at most
$1/2+O(d/\sqrt{n})$ fraction of all inputs.

###### Proof.

Consider the polynomial:

$g(Y_{1},\cdots,Y_{n})=f(Y_{1}-1,Y_{2}-1,\cdots,Y_{n}-1)+1$

The key point is that when $Y_{1},\cdots,Y_{n}\in\\{1,-1\\}$, if $f$ computes
the parity of $n$ bits, then $g$ computes the product $\prod_{i}Y_{i}$.
Therefore, we have found a degree $d$ polynomial that can compute the same
quantity as the product of $n$ variables. We shall show that this computation
cannot work on a large fraction of inputs using a counting argument.

Let $T\subseteq\\{1,-1\\}^{n}$ denote the set of inputs for which
$g(y)=\prod_{i}y_{i}$. To complete the proof, it will suffice to show that $T$
consists of at most $1/2+O(d/\sqrt{n})$ fraction of all strings.

Consider the set of all functions $q:T\to\mathbb{F}_{3}$. This is a space
dimension $|T|$. We shall show how to compute every such function using a low
degree polynomial.

By Fact $2$, every such function $q$ can be computed by a polynomial. Note
that in any such polynomial, since $y_{i}\in\\{-1,1\\}$, we have that
$y_{i}^{2}=1$ so we can assume that each variable has degree at most $1$. Now
suppose $I\subset[n]$ is a set of size more than $n/2$, then for $y\in T$:

$\prod_{i\in I}y_{i}=(\prod_{i=1}^{n}y_{i})(\prod_{i\notin
I}y_{i})=g(y)(\prod_{i\notin I}y_{i})$

In this way, we can express every monomial of $q$ with low degree terms, and
so obtain a polynomial of degree at most $n/2+d$ that computes $q$.

The space of all such polynomials is spanned by $\sum_{i=0}^{n/2+d}{n\choose
i}$ monomials. Therefore we get that:

$|T|\leq\sum_{i=0}^{n/2+d}{n\choose i}$ $\leq
2^{n}/2+\sum_{i=n/2+1}^{d}{n\choose i}$ $\leq 2^{n}/2+O(d\cdot
2^{n}/\sqrt{n})=2^{n}(1/2+O(d/\sqrt{n}))$

∎

##  3 Beyond Canonical Hastad [Bea94]

Whilst uniform restrictions consider the variables set equally likely to
values $0$ or $1$, we can also consider restrictions whether the input
variables are set to these values with imbalanced probability. This method is
used to get circuit lower bounds for the CLIQUE problem.

The key idea is to provide weights to restrictions which reflect the
probability of the restriction being chosen as a random member of the set.
Indeed suppose that in the context of Hastad’s switching lemma, we wanted to
argue that there is a restriction which is strongly biased towards setting
bits to $1$ and keeps the decision tree height small. The basic switching
Lemma does not give us this information because as $n$ gets large it is much
more unlikely to get a restriction with even a constant factor bias than the
probability of failure.

###  3.1 Other Restriction Methods

The $\text{Stars}_{m}$ restriction is defined as a map from
$\\{x_{1},\cdots,x_{n}\\}\to\\{0,1,*\\}$ with exactly $m$ stars and behaves
similarly to $R_{m/n}$. The corresponding switching lemma is:

$P[\text{DT}_{\text{depth}}(k-\text{DNF}_{\text{Stars}_{m}}\geq t]\leq
O((m/n)k)^{t}$

Consider the $q$-biased $p$-restriction $R_{p,q}$:

$R_{p,q}(x_{i})=\begin{cases}*\text{ w.p. }p\\\ 1\text{ w.p. }(1-p)q\\\
0\text{ w.p. }(1-p)(1-q)\end{cases}$

Now the corresponding switching lemma (for $q\leq 0.5$) is as follows:

$P[\text{DT}_{\text{depth}}(k-DNF|_{R_{p,q}}\geq t]\leq O(pk/q)^{t}$

This is typically used for average case lower bounds under $q$-biased
distributions on $\\{0,1\\}^{n}$.

Another switching lemma forms the foundation of the so-called ”clique
switching lemma” for the random restriction on ${n\choose 2}$ variables such
that the stars are edges of a clique on a $p$-random set of vertices and the
non-stars are set to $1$ with probability $q$ and $0$ with probability $1-q$.

The corresponding switching lemma for $q\leq 0.5$ is as follows:

$P{\text{DT}_{\text{depth}}}(k-\text{DNF}_{\text{Clique}_{p,q}})\geq t]\leq
O(pk/q^{O(k+t)})^{t}$

In particular, this provides a $n^{\Omega(k/d^{2})}$ lower bound for
$k$-$\text{CLIQUE}_{n}$. Readers are encouraged to look at [Bea94] for a more
in-depth analysis on these biased-restrictions, their applications and
motivations.

###  3.2 Consequences of Parity not in $AC^{0}$

$\text{PARITY}\notin\text{AC}_{0}$ is the way to obtain an oracle that
separates PSPACE from the Polynomial Hierarchy. Hence, no proof that
relativises can be used to separate PSPACE from the Polynomial hierarchy.
There are many consequences of this result threaded throughout Complexity
Theory literature, where three of the key results are highlighted below.

Fourier Concentration: The Fourier expansion of a boolean function is it’s
representation as a low-degree polynomial. Using Hastad’s switching lemma, we
can show that the Fourier Expansion of any function in $AC^{0}$ has all of
it’s larger coefficients concentrated on it’s low order Fourier coefficients;
$AC^{0}$ functions can be approximated by low degree polynomials.

Pseudo-Random Generators for $AC^{0}$: De-randomization studies the
possibility of removing or reducing the amount of randomization used by
randomized algorithms while still maintaining their efficiency and
correctness. Nisan and Wigderson have proved that the randomized analogues of
$AC^{0},RAC^{0}$ and $BPAC^{0}$ can be de-randomized in poly-logarithmic space
and quasi-polynomial time.

$AC^{0}$-Circuit SAT and $\\#$-SAT Algorithms: Given an $AC^{0}$ circuit
,determine whether there exists an input $x$ which evaluates that circuit to
$1$. Impagliazzo, Matthew and Paturi have demonstrated that Hastad’s Switching
Lemma can be used to provide non-trivial algorithms for $AC^{0}$-circuit SAT.

###  3.3 Comparison with Polynomial Method

The polynomial method for proving lower bounds on PARITY is similar to the
method of random restrictions in the sense that we take advantage of a
property which is common to all circuits of small size and constant depth with
PARITY does not have. This property is that circuits of small size and
constant depth can be represented by low degree polynomials with high
probability.

In particular, we use the following fact and two lemmas to prove the result.

Fact: Any function $g:\\{0,1\\}^{n}\to\mathbb{R}$ has degree at most $d$ if
and only if $\hat{g}_{\alpha}=0$ for all $\alpha$ such that $|\alpha|>d$

Lemma 1: For every circuit $C$ of size $S$ and depth $d$, there is a function
$g:\\{0,1\\}^{n}\to\mathbb{R}$ of degree $O((\log S)^{2d})$ such that $g$ and
$C$ agree on at least $3/4$ fraction of $\\{0,1\\}^{n}$

###### Proof.

Given a circuit $C$ of size $S$ and depth $d$, for every gate we pick
independently an approximating function $g_{i}$ with parameter
$\epsilon=\frac{1}{4S}$ and replace the gate by $g_{i}$. Then for a given
input, the probability that the new function so defined computes $C(x)$
correctly is at least the probability that the results of all the gates are
correctly computed, which is at least $\frac{3}{4}$. In particular, there is a
function among those generated this way that agrees with $C()$ on at least
$3/4$ fraction of inputs. Each $g_{i}$ has degree at most $O(\log S)^{2}$,
because the fan-in of each gate is at most $S$, and the degree of the function
defined in the construction is at most $O((\log S)^{2d}$.

∎

Lemma 2: Let $g:\\{0,1\\}^{n}\to\mathbb{R}$ be a function that agrees with
PARITY on at least $3/4$ fraction of $\\{0,1\\}^{n}$. Then the degree of $g$
is $\Omega(\sqrt{n})$

###### Proof.

Let $g:\\{0,1\\}^{n}\to\mathbb{R}$ be a function of degree at most $t$ that
agrees with PARITY on at least $3/4$ fraction of inputs. Let
$G:\\{-1,1\\}^{n}\to\mathbb{R}$ be defined as:

$G(x)=1-2g(\frac{1}{2}-\frac{1}{2}x_{1},\cdots,\frac{1}{2}-\frac{1}{2}x_{n})$

Now note that $G$ is still of degree at most $t$, and $G$ agrees with the
function $\prod(x_{1},\cdots,x_{n})=x_{1}\cdot x_{2}\cdots x_{n}$ on at least
$3/4$ fraction of $\\{-1,1\\}^{n}$.

Define $A$ to be the set of $x\in\\{-1,1\\}^{n}$ such that $G(x)=\prod(x)$:

$A=\\{x:G(x)=\prod_{i=1}^{n}x_{i}\\}$

Then $|A|\geq\frac{3}{4}\cdot 2^{n}$ by our initial assumption. Now consider
the set $F$ of all functions $f:A\to\mathbb{R}$. These form a vector space of
dimension $|A|$ over the reals. We know that any function $f$ in this set can
be written as:

$f(x)=\sum_{\alpha}\hat{f}_{\alpha}\prod_{i\in\alpha}x_{i}$

Over $A$, $G(x)=\prod_{i=1}^{n}x_{i}$ and therefore for $x\in A$:

$\prod_{i\in\alpha}x_{i}=G(x)\prod_{i\notin\alpha}x_{i}$

Now by our initial assumption, $G(x)$ is a polynomial of degree at most $t$.
Therefore, for every $\alpha$ such that $|\alpha|\geq\frac{n}{2}$, we can
replace $\prod_{i\in\alpha}x_{i}$ by a polynomial of degree less than or equal
to $t+\frac{n}{2}$. Every such function $f$ which belong to $F$ can be written
as a polynomial of degree at most $t+\frac{n}{2}$. Hence the set
$\\{\prod_{i\in\alpha}x_{i}\\}_{|\alpha|\leq t+\frac{n}{2}}$ forms a basis for
the set $S$. As there must be at least $|A|$ such monomials, this implies
that:

$\sum_{k=0}^{t+\frac{n}{2}}{n\choose k}\geq\frac{3}{4}\cdot 2^{n}$

And in particular:

$\sum_{k=\frac{n}{2}}^{t+\frac{n}{2}}{n\choose k}\geq\frac{1}{4}\cdot 2^{n}$

Now we know from Stirling’s approximation that every binomial coefficient
${n\choose k}$ is at most $O(2^{n}/\sqrt{n})$, and therefore we obtain:

$O(\frac{t}{\sqrt{n}}\cdot 2^{n})\geq\frac{1}{4}\cdot 2^{n}$

This implies that $t=\Omega(\sqrt{n})$. ∎

And the theorem is subsequently proved as follows.

###### Proof.

From Lemma $1$, we have that there is a function
$g:\\{0,1\\}^{n}\to\mathbb{R}$ that agrees with PARITY on a $3/4$ fraction of
$\\{0,1\\}^{n}$, whose degree is at most $O((\log S)^{2d})$. From Lemma $2$,
we can deduce that the degree of $g$ must be at least $\Omega(\sqrt{n})$ so
that:

$(\log S)^{2d}=\Omega(\sqrt{n})$

which is equivalent to:

$S=2^{\Omega(n^{1/4d})}$

∎

In comparison with the polynomial method, the method of random restrictions
prove a stronger and tighter lower bound. Furthermore, they use a property of
the parity function which is true of other functions. Therefore, it truly is a
general method to attack circuit lower bounds.

Polynomial methods can also accomplish this, and further has the advantage
that it can be applied to any circuit model in which gates can be approximated
by low-degree polynomials. For example, consider the $\text{AC}0$ model in
which we have NOT gates, unbounded fan-in AN and OR gates and also MOD3 gates
that, given boolean inputs $x_{1},\cdots,x_{n}$ output $1$ if and only if
$\sum_{i}x_{i}\equiv 1\lor 2\mod 3$.

The method of random restrictions cannot be applied to such circuits, because
a MOD3 gate has a value that remains under-determined as long as at least
three variables are not fixed and requires a CNF of size exponential in the
number of non-fixed variables. We can prove that every $AC0^{3}$ circuit of
depth $d$ that computes PARITY must size at least $2^{\Omega(n^{1}/(4d)}$.

## References

  * [AB07]

S. Arora, B. Barak, Computational Complexity: A Modern Approach, Princeton
University (2007) https://theory.cs.princeton.edu/complexity/book.pdf

  * [ASWZ20]

R. Alweiss, S. Lovett, K. Wu, J. Zhang, Improved Bounds for the Sunflower
Lemma, Princeton University, UCSD, Peking University, Harvard University
(2019) https://dl.acm.org/doi/pdf/10.1145/3357713.3384234

  * [Bea94]

P. Beame, A Switching Lemma Primer, The University of Toronto (1994)
https://www.cs.toronto.edu/~toni/Courses/Complexity2015/handouts/primer.pdf

  * [Bor72]

A. Borodin, Computational Complexity and the Existence of Complexity Gaps,
University of Toronto (1972) https://dl.acm.org/doi/pdf/10.1145/321679.321691

  * [BH09]

P. Beame, D. Huynh-Ngoc, Multiparty Communication Complexity and Threshold
Circuit Size of $AC^{0}$, The University of Washington Department of Computer
Science (2009) https://homes.cs.washington.edu/~beame/papers/multiac0j.pdf

  * [Coh12]

G. Cohen, A Taste of Circuit Complexity Pivoted at
$\text{NEXP}\subsetneq\text{ACC}^{0}$ (and more), Weizmann Institute of
Science (2012)

  * [CRTY19]

L. Chen, R. Rothblum, R. Tell, E. Yogev, On Exponential-Time Hypotheses,
Derandomization, and Circuit Lower Bounds, Electronic Colloquium on
Computational Complexity (2019) https://eccc.weizmann.ac.il/report/2019/169/

  * [Fur08]

J. Furtado, An Introduction to Computational Complexity, MIT 6.080: Great
Ideas in Theoretical Computer Science, Massachusetts’s Institute of Technology

  * [GNW99]

O. Goldreich, N. Nisan, A. Wigderson, On Yao’s XOR-Lemma, Electronic
Colloquium on Computational Complexity (1999), pp. 10-29
http://www.wisdom.weizmann.ac.il/~oded/COL/yao.pdf

  * [Gol05]

P. Goldreich, Texts in Computational Complexity: $\text{P}/\text{Poly}$ and
PH, Department of Computer Science and Applied Mathematics, Weizmann Institute
Israel (2005)

  * [GP14]

J. Grochow, T. Pitassi, Circuit Complexity, Proof Complexity and Polynomial
Identity Testing, (2014)

  * [GW04]

O. Goldreich, A. Wigderson, Computational Complexity, Weizmann Institute of
Science, Institute of Advanced Study (2004)

  * [Jun12]

S. Junka, Boolean Function Complexity: Advances and Frontiers, Algorithms and
Combinatorics, Vol. $27$ (2012) ISBN: $978$-$3$-$642$-$24507$-$7$

  * [L20]

S. Lovett, CSE200: Complexity Theory, Circuit Lower Bounds, UC San Diego
Department of Computer Science

  * [Mos16]

D. Moshkovitz, Derandomization Implies Circuit Lower Bounds, MIT: Advanced
Complexity Theory (2016)
https://ocw.mit.edu/courses/mathematics/18-405j-advanced-complexity-theory-
spring-2016/lecture-notes/MIT18_405JS16_CircuitLower.pdf

  * [Mor19]

H. Morizumi, Some Results on the Circuit Complexity of Bounded Width Circuits
and Non-deterministic Circuits, Shimane University (2019)
https://arxiv.org/pdf/1811.01347.pdf

  * [RST15]

Benjamin Rossman, Rocco A. Servedio, and Li-Yang Tan. An average-case depth
hierarchy theorem for Boolean circuits. In Proceedings of the 56th Annual
Symposium on Foundations of Computer Science, $2015$
https://arxiv.org/pdf/1504.03398.pdf

  * [TTV09]

L. Trevisan, M. Tulsiani, S. Vadhan, Regularity, Boosting and Efficiently
Stimulating Every High-Entropy Distribution SEAS Harvard (2009), pp. 1-11
https://people.seas.harvard.edu/~salil/research/regularity-ccc09.pdf

  * [Wig19]

A. Wigderson, Mathematics and Computation: A Theory Revolutionizing Technology
and Science, Princeton University Press (2019)
https://www.math.ias.edu/files/Book-online-Aug0619.pdf

  * [Weg87]

I. Wegener, The Complexity of Boolean Functions, Johan Wolfgang Goethe-
Universitat (1987)

  * [Wil10]

R. Williams, Non-uniform $ACC$ Circuit Lower Bounds, IBM Almaden Research
Center (2010) https://www.cs.cmu.edu/~ryanw/acc-lbs.pdf

  * [Wil14]

R. Williams, Algorithms for Circuits and Circuits for Algorithms: Connecting
the Tractable and Intractable, IEEE Conference on Computational Complexity
(2014) https://people.csail.mit.edu/rrw/ICM-survey.pdf


# The Rank of the Endomorphism Monoid of a Partition

João Araújo and Csaba Schneider  Informatics Research Laboratory
Computer and Automation Research Institute
1518 Budapest Pf. 63
Hungary Centro de Álgebra da Universidade de Lisboa
Av. Prof. Gama Pinto 2
1649-003 Lisboa
Portugal Email<EMAIL_ADDRESS>WWW: www.sztaki.hu/$\sim$schneider
Universidade Aberta
R. Escola Politécnica 147
1269-001 Lisboa
Portugal Centro de Álgebra
Universidade de Lisboa
1649-003 Lisboa
Portugal Email<EMAIL_ADDRESS>
###### Abstract.

The rank of a semigroup is the cardinality of a smallest generating set. In
this paper we compute the rank of the endomorphism monoid of a non-trivial
uniform partition of a finite set, that is, the semigroup of those
transformations of a finite set that leave a non-trivial uniform partition
invariant. That involves proving that the rank of a wreath product of two
symmetric groups is two and then use the fact that the endomorphism monoid of
a partition is isomorphic to a wreath product of two full transformation
semigroups. The calculation of the rank of these semigroups solves an open
question.

###### Key words and phrases:

transformation semigroups, rank, relative rank, wreath product, symmetric
groups

###### 1991 Mathematics Subject Classification:

20M20, 20B30, 20E22

##  1\. Introduction

If $S$ is a semigroup and $U$ is a subset of $S$ then we say that $U$
generates $S$ if every element of $S$ is expressible as a word in the elements
of $U$. We use the convention that the empty word represents the identity
element. The rank of a semigroup $S$, denoted by $\mbox{\emph{\mbox{\rm
rank}\,}}S$, is the minimum among the cardinalities of its generating sets. It
is well-known that a finite full transformation semigroup has rank 3, while a
finite full partial transformation semigroup has rank 4 (see [14, Exercises
1.9.7 and 1.9.13]). Similar results were proved for many different classes of
transformation semigroups (such as total, partial, partial one-to-one, order
preserving) and their ideals; see [4, 10, 15, 20, 22].

Some generalizations of the notion of rank, for instance the idempotent rank
and the nilpotent rank, also attracted a great deal of attention (see [5, 9,
19], among others).

Finally, in recent years, the notion of relative rank has been subjected to
extensive research (see for example [7, 13, 11, 12, 16]). Relative rank is a
useful notion when dealing with finite semigroups (see Lemma 3.1), and it is
crucial when dealing with uncountable semigroups. In fact, in such semigroups,
the notion of rank is not very informative as the rank and the cardinality
coincide. To a large extent, this line of research was prompted by two old
papers by Sierpiński [24] and by Banach [3] (see also [2]).

In this paper we deal with the endomorphism monoid of a non-trivial uniform
partition. We prove that the rank of such semigroup is 4, thus settling a
problem posed in [17]. We also calculate the ranks of some related
transformation semigroups.

If $X$ is a finite set then the set of transformations on $X$ form the full
transformation monoid on $X$ and is denoted by ${\sf T}(X)$. We assume that
transformations act on the right; that is, if $x\in X$ and $f\in{\sf T}(X)$,
then $xf$ denotes the image of $x$ under $f$. Let $\mathcal{P}$ be a partition
of $X$; that is, $\mathcal{P}=\\{P_{1},\ldots,P_{m}\\}$ where
$P_{1},\ldots,P_{m}\subseteq X$, $P_{i}\cap P_{j}=\emptyset$ whenever $i\neq
j$, and $X=P_{1}\cup\cdots\cup P_{m}$. The equivalence relation that
corresponds to a partition $\mathcal{P}$ is denoted $\sim_{\mathcal{P}}$. The
elements of ${\sf T}(X)$ that preserve the partition $\mathcal{P}$ form a
semigroup and is denoted by ${\sf T}(X,\mathcal{P})$. Using symbols,

$\begin{array}[]{rcl}{\sf T}(X,\mathcal{P})&=&\\{f\in{\sf
T}(X)\mid(\forall{P_{i}\in\mathcal{P}})(\exists{P_{j}\in\mathcal{P}})\
P_{i}f\subseteq P_{j}\\}\\\ &=&\\{f\in{\sf T}(X)\mid\mbox{if
}x\sim_{\mathcal{P}}y\mbox{ then }xf\sim_{\mathcal{P}}yf\\}.\end{array}$

The partition $\mathcal{P}$ is called uniform if $|P_{i}|=|P_{j}|$ for all
$i,\ j\in\\{1,\ldots,m\\}$. The main result of Huisheng’s paper [17] is that
for a uniform partition $\mathcal{P}$ the rank of ${\sf T}(X,\mathcal{P})$ is
at most 6, or smaller in some degenerate cases. Huisheng’s proof relied on the
observation that there is a strong relationship between $\mbox{\emph{\mbox{\rm
rank}\,}}{\sf T}(X,\mathcal{P})$ and the rank of the group $G$ of invertible
transformations in ${\sf T}(X,\mathcal{P})$. He proved that the rank of $G$ is
at most 4 (or smaller in some degenerate cases). In the present paper, we are
able to show, for $|X|\geqslant 3$, that $\mbox{\emph{\mbox{\rm rank}\,}}G=2$
(see Theorem 4.1). In order to facilitate the proof of our results, we use the
concept of wreath products of transformation semigroups; see Section 2.

We can also consider the rank of some further interesting semigroups related
to a partition $\mathcal{P}$ of a set $X$. Let us define

$\begin{array}[]{rcl}\Sigma(X,\mathcal{P})&=&\\{f\in{\sf T}(X)\ |\
x\sim_{\mathcal{P}}y\mbox{ if and only if }xf\sim_{\mathcal{P}}yf\\},\mbox{
and}\\\ \Gamma(X,\mathcal{P})&=&\\{f\in{\sf
T}(X,\mathcal{P})\mid(\forall{P_{i},\ P_{j}\in\mathcal{P}})\ \mbox{ either
}P_{i}f\cap P_{j}\neq\emptyset\mbox{ or }P_{i}f=P_{j}\\}.\\\ \end{array}$

It is routine to check that $\Sigma(X,\mathcal{P}),\
\Gamma(X,\mathcal{P})\leqslant{\sf T}(X,\mathcal{P})$.

The following theorem improves Huisheng’s result and settles the problem of
determining the rank of ${\sf T}(X,\mathcal{P})$. It also gives the rank of
$\Sigma(X,\mathcal{P})$ and $\Gamma(X,\mathcal{P})$. A partition of $X$ is
said to be trivial if it has $1$ or $|X|$ parts (that is, the trivial
partitions are the identity and the universal partitions).

######  Theorem 1.1.

If $X$ is a finite set such that $|X|\geqslant 3$, and $\mathcal{P}$ is a non-
trivial uniform partition of $X$, then $\mbox{\emph{\mbox{\rm rank}\,}}{\sf
T}(X,\mathcal{P})=4$ and $\mbox{\emph{\mbox{\rm
rank}\,}}\Sigma(X,\mathcal{P})=\mbox{\emph{\mbox{\rm
rank}\,}}\Gamma(X,\mathcal{P})=3$.

##  2\. Wreath products of transformation semigroups

We define the wreath product of two transformation semigroups following [25]
(see also [21, Chapter 10]). The material of this section is well-known,
however, we felt that it was necessary to present it in order to make the
paper self-contained and also to set our system of notation. Let $S$ and $R$
be two transformation semigroups acting on the sets $Y$ and $Z$, respectively,
and let $B$ denote the set of functions $f:Z\rightarrow S$. The underlying set
of the wreath product $S\,{\sf wr}\,R$ is the Cartesian product $B\times R$
and to each element $(f,r)\in B\times R$, we assign a transformation of the
set $Y\times Z$ defined by

(1) $(y,z)(f,r)=(yf(z),zr)\quad\mbox{for all}\quad y\in Y,\ z\in Z,\ f\in B,\
r\in R.$

It is easy to see that this assignment is injective and that the image of this
assignment is closed under composition; that is, the image is a subsemigroup
of ${\sf T}(Y\times Z)$.

From now on we assume that the sets $Y$ and $Z$ are finite and that $S$ and
$R$ are monoids, that is, they contain the identity transformation ${\rm id}$.
Let us assume without loss of generality that $Y=\\{1,\ldots,n\\}$ and
$Z=\\{1,\ldots,m\\}$. In this case, a function $f:Z\rightarrow S$ can be
represented as the $m$-tuple $(s_{1},\ldots,s_{m})$ where $f(i)=s_{i}$ for all
$i\in\\{1,\ldots,m\\}$. This defines a bijection between $B\times R$ and
$S^{m}\times R$, and, in turn, between $S\,{\sf wr}\,R$ and $S^{m}\times R$.
Therefore we may view an element of $S\,{\sf wr}\,R$ as a pair
$((s_{1},\ldots,s_{m}),r)$ where $s_{1},\ldots,s_{m}\in S$ and $r\in R$. The
element $((s_{1},\ldots,s_{m}),r)$ will more briefly be denoted by
$(s_{1},\ldots,s_{m})r$. Setting $s=(s_{1},\ldots,s_{m})$ the same element can
be written as $sr$. By (1), the action of $(s_{1},\ldots,s_{m})r$ on a pair
$(y,z)\in Y\times Z$ is given by

(2) $(y,z)(s_{1},\ldots,s_{m})r=(ys_{z},zr).$

Let $S\leqslant{\sf T}(Y)$ and $R\leqslant{\sf T}(Z)$ be transformation
monoids as above. Then $S$ and $R$ can naturally be embedded into the wreath
product $S\,{\sf wr}\,R$. Indeed, we may consider the following submonoids of
$S\,{\sf wr}\,R$:

(3) $\overline{S}_{i}=\\{({\rm id},\ldots,{\rm
id},\stackrel{{\scriptstyle\mbox{\footnotesize$i$-th component}}}{{s}},{\rm
id}\ldots,{\rm id}){\rm id}\in S\,{\sf wr}\,R\ |\ s\in S\\},$

and

(4) $\overline{R}=\\{({\rm id},\ldots,{\rm id})r\in S\,{\sf wr}\,R\ |\ r\in
R\\}.$

Set, for $i=\\{1,\ldots,m\\}$, $\overline{Y}_{i}=\\{(y,i)\ |\ y\in Y\\}$. Easy
computation shows that the elements of $\overline{S}_{i}$ leave the set
$\overline{Y}_{i}$ invariant, and $\overline{S}_{i}$, considered as a
transformation monoid on $\overline{Y}_{i}$, is isomorphic to the
transformation monoid $S$. Let us further define
$\overline{Z}=\\{\overline{Y}_{1},\ldots,\overline{Y}_{m}\\}$. Then
$\overline{R}$ leaves $\overline{Z}$ invariant, and $\overline{R}$, considered
as a transformation monoid on $\overline{Z}$, is isomorphic to $R$. Since
$\overline{S}_{1}\times\cdots\times\overline{S}_{m}\cong S^{m}$ and
$\overline{R}\cong R$, we may consider $S^{m}$ and $R$ as submonoids of
$S\,{\sf wr}\,R$.

Since $R$ is assumed to be a transformation monoid on the set
$Z=\\{1,\ldots,m\\}$, we may define a homomorphism $\vartheta:R\rightarrow
S^{m}$:

$(r\vartheta)(s_{1},\ldots,s_{m})=(s_{1r},\ldots,s_{mr}).$

We note that the action of $\mbox{End}(S^{m})$ on $S^{m}$ is a left-action.
The homomorphism $\vartheta$ is useful for expressing the operation in
$S\,{\sf wr}\,R$. Indeed, let $s_{1},\ s_{2}\in S^{m}$ and $r_{1},\ r_{2}\in
R$. Then, viewing $s_{1}r_{1}$ and $s_{2}r_{2}$ as elements of $S\,{\sf
wr}\,R$, easy computation shows that

(5) $(s_{1}r_{1})(s_{2}r_{2})=(s_{1}(r_{1}\vartheta)s_{2})(r_{1}r_{2}).$

Therefore the wreath product $S\,{\sf wr}\,R$ can also be viewed as the
semidirect product $S^{m}\rtimes R$ of $S^{m}$ and $R$ with respect to the
homomorphism $\vartheta:R\rightarrow\mbox{End}(S^{m})$ (see [21, page 186]).
In particular, if $r$ is an invertible element of $R$ and $s\in S^{m}$, then,
considering $s$ and $r$ as elements of $S\,{\sf wr}\,R$, equation (5) implies
that

(6) $rsr^{-1}=(r\vartheta)s.$

Therefore conjugation by an invertible element of $R$ leaves $S^{m}$
invariant, and the conjugation action of $R$ is given by the homomorphism
$\vartheta$. Indeed, from the last displayed line we obtain that
$s^{r}=r^{-1}sr=(r^{-1}\vartheta)s$. Note that the conjugation action of the
element $r$ is actually given by the endomorphism $r^{-1}\vartheta$. The
reason for this is that we assumed that endomorphisms act on the left, while
the usual definition makes the conjugation action a right-action. Further, if
$r$ is an invertible element of $R$ and $i,\ j\in\\{1,\ldots,m\\}$ such that
$ir=j$ then (6) implies that
$\overline{S}_{i}^{r}=(r^{-1}\vartheta)\overline{S}_{i}=\overline{S}_{j}$.

For a finite set $X$, the invertible elements of ${\sf T}(X)$ form the
symmetric group ${\sf S}{(X)}$. If $\mathcal{P}$ is a partition of $X$ then
set ${\sf S}{(X,\mathcal{P})}={\sf T}(X,\mathcal{P})\cap{\sf S}{(X)}$. The
next lemma connects the semigroups related to a partition to wreath products.

######  Lemma 2.1.

Let $Y=\\{1,\ldots,n\\}$ and $Z=\\{1,\ldots,m\\}$, set $X=Y\times Z$, and let
$\mathcal{P}$ denote the partition
$\\{\\{(1,1),\ldots,(n,1)\\},\ldots,\\{(1,m),\ldots,(n,m)\\}\\}$. Then

  1. (i)

${\sf T}(X,\mathcal{P})={\sf T}(Y)\,{\sf wr}\,{\sf T}(Z)$;

  2. (ii)

$\Sigma(X,\mathcal{P})={\sf T}(Y)\,{\sf wr}\,{\sf S}{(Z)}$;

  3. (iii)

$\Gamma(X,\mathcal{P})={\sf S}{(Y)}\,{\sf wr}\,{\sf T}(Z)$;

  4. (iv)

${\sf S}{(X,\mathcal{P})}={\sf S}{(Y)}\,{\sf wr}\,{\sf S}{(Z)}$.

###### Proof.

Since the proofs of these statements are very similar to each other, we only
verify assertion (ii). Let $(y_{1},z_{1}),\ (y_{2},z_{2})\in Y\times Z$ and
assume that $t_{1},\ldots,t_{m}\in{\sf T}(Y)$ $s\in{\sf S}{(Z)}$ so that
$(t_{1},\ldots,t_{m})s\in{\sf T}(Y)\,{\sf wr}\,{\sf S}{(Z)}$. Set
$w=(t_{1},\ldots,t_{m})s$. We have, for $i=1,\ 2$, that

$(y_{i},z_{i})w=(y_{i},z_{i})(t_{1},\ldots,t_{m})s=(y_{i}t_{z_{i}},z_{i}s).$

Thus, if $(y_{1},z_{1})\sim_{\mathcal{P}}(y_{2},z_{2})$, then $z_{1}=z_{2}$,
and then $z_{1}s=z_{2}s$; hence, in this case,
$(y_{1},z_{1})w\sim_{\mathcal{P}}(y_{2},z_{2})w$. Conversely, if
$(y_{1},z_{1})w\sim_{\mathcal{P}}(y_{2},z_{2})w$, then $z_{1}s=z_{2}s$, which,
using that $s$ is a invertible, gives that $z_{1}=z_{2}$; therefore
$(y_{1},z_{1})\sim_{\mathcal{P}}(y_{2},z_{2})$. This shows that
$w\in\Sigma(X,\mathcal{P})$, and so ${\sf T}(Y)\,{\sf wr}\,{\sf
S}{(Z)}\leqslant\Sigma(X,\mathcal{P})$.

Suppose now that $x\in\Sigma(X,\mathcal{P})$. Then the defining property of
$\Sigma(X,\mathcal{P})$ implies that $x$ induces a permutation on the set
$\mathcal{P}$. Since there is a one-to-one correspondence between
$\mathcal{P}$ and $Z=\\{1,\ldots,m\\}$, we obtain that $x$ induces a
permutation on $Z$. Let this permutation be $s$. For $i=1,\ldots,m$, let us
define a transformation $t_{i}\in{\sf T}(Y)$. Let $j\in\\{1,\ldots,m\\}$ such
that $ix=j$. Then, for all $k\in\\{1,\ldots,n\\}$ there is some
$l_{k}\in\\{1,\ldots,n\\}$ such that $(k,i)x=(l_{k},j)$. Let $t_{i}$ be the
transformation that maps $k$ to $l_{k}$ for all $k\in\\{1,\ldots,n\\}$. Then
routine computation shows that $x=(t_{1},\ldots,t_{m})s$, and so $x\in{\sf
T}(Y)\,{\sf wr}\,{\sf S}{(Z)}$. Thus, $\Sigma(X,\mathcal{P})\leqslant{\sf
T}(Y)\,{\sf wr}\,{\sf S}{(Z)}$, and so ${\sf T}(Y)\,{\sf wr}\,{\sf
S}{(Z)}=\Sigma(X,\mathcal{P})$ ∎

##  3\. Relative rank of semigroups

Let $U\subseteq S$ be a subset of a semigroup $S$. The relative rank of $S$
modulo $U$, denoted by $\mbox{\emph{\mbox{\rm rank}\,}}{(S:U)}$, is the
minimum among the cardinalities of subsets $V$ of $S$ such that $S=\langle
V\cup U\rangle$. The relative rank was introduced in [13]. The next lemma
shows that the rank of a transformation semigroup is related to its relative
rank modulo the unit group.

######  Lemma 3.1.

Let $S$ be a finite transformation semigroup and let $G$ be the group of units
in $S$. If $U\subseteq S$ such that $\bigl{<}U\bigr{>}=S$, then $\bigl{<}U\cap
G\bigr{>}=G$. In particular, $\mbox{\emph{\mbox{\rm
rank}\,}}S=\mbox{\emph{\mbox{\rm rank}\,}}{(S:G)}+\mbox{\emph{\mbox{\rm
rank}\,}}G$.

###### Proof.

It suffices to show that $G\leqslant\bigl{<}U\cap G\bigr{>}$, and so suppose
that $g\in G$. Since $U$ is a generating set of $S$, we obtain that
$g=u_{1}u_{2}\cdots u_{r}$ with some $u_{1},\ldots,u_{r}\in U$. Since $g$ is
invertible, we obtain that $u_{1},\ldots,u_{r}$ must also be invertible, and
so $u_{1},\ldots,u_{r}\in G$. Thus $g\in\bigl{<}U\cap G\bigr{>}$, and hence
the assertion follows. ∎

Next we determine the relative ranks of ${\sf T}(X,\mathcal{P})$,
$\Sigma(X,\mathcal{P})$ and $\Gamma(X,\mathcal{P})$ modulo their unit groups.

######  Lemma 3.2.

If $X$ is a finite set and $\mathcal{P}$ is a uniform partition of $X$, then

$\mbox{\emph{\mbox{\rm rank}\,}}{({\sf T}(X,\mathcal{P}):{\sf
S}{(X,\mathcal{P})})}=2,$

and

$\mbox{\emph{\mbox{\rm rank}\,}}{(\Gamma(X,\mathcal{P}):{\sf
S}{(X,\mathcal{P})})}=\mbox{\emph{\mbox{\rm
rank}\,}}{(\Sigma(X,\mathcal{P}):{\sf S}{(X,\mathcal{P})})}=1.$

###### Proof.

We may suppose without loss of generality that $X=Y\times Z$ where
$Y=\\{1,\ldots,n\\}$, $Z=\\{1,\ldots,m\\}$ and $\mathcal{P}$ is the partition

$\\{\\{(1,1),\ldots,(n,1)\\},\ldots,\\{(1,m),\ldots,(n,m)\\}\\}.$

By Lemma 2.1, ${\sf T}(X,\mathcal{P})={\sf T}(Y)\,{\sf wr}\,{\sf T}(Z)$,
$\Sigma(X,\mathcal{P})={\sf T}(Y)\,{\sf wr}\,{\sf S}{(Z)}$,
$\Gamma(X,\mathcal{P})={\sf S}{(Y)}\,{\sf wr}\,{\sf T}(Z)$, and ${\sf
S}{(X,\mathcal{P})}={\sf S}{(Y)}\,{\sf wr}\,{\sf S}{(Z)}$, and so it suffices
to show that

(7) $\mbox{\emph{\mbox{\rm rank}\,}}{({\sf T}(Y)\,{\sf wr}\,{\sf T}(Z):{\sf
S}{(Y)}\,{\sf wr}\,{\sf S}{(Z)})}=2$

and

(8) $\mbox{\emph{\mbox{\rm rank}\,}}{({\sf T}(Y)\,{\sf wr}\,{\sf S}{(Z)}:{\sf
S}{(Y)}\,{\sf wr}\,{\sf S}{(Z)})}=\mbox{\emph{\mbox{\rm rank}\,}}{({\sf
S}{(Y)}\,{\sf wr}\,{\sf T}(Z):{\sf S}{(Y)}\,{\sf wr}\,{\sf S}{(Z)})}=1.$

Let $\overline{\alpha}$ denote the transformation in ${\sf T}(Y)$ such that
$1\overline{\alpha}=2$ and $i\overline{\alpha}=i$ for all
$i\in\\{2,\ldots,n\\}$. Then ${\sf T}(Y)=\bigl{<}{\sf
S}{(Y)}\cup\\{\overline{\alpha}\\}\bigr{>}$ (see [14, Exercise 1.9.7]). Set
$\alpha=(\overline{\alpha},{\rm id},\ldots,{\rm id}){\rm id}$ and $\beta=({\rm
id},\ldots,{\rm id})\overline{\alpha}$. We claim that

(9) $\displaystyle{\sf T}(Y)\,{\sf wr}\,{\sf S}{(Z)}$ $\displaystyle=$
$\displaystyle\bigl{<}{\sf S}{(Y)}\,{\sf wr}\,{\sf
S}{(Z)}\cup\\{\alpha\\}\bigr{>},$ (10) $\displaystyle{\sf S}{(Y)}\,{\sf
wr}\,{\sf T}(Z)$ $\displaystyle=$ $\displaystyle\bigl{<}{\sf S}{(Y)}\,{\sf
wr}\,{\sf S}{(Z)}\cup\\{\beta\\}\bigr{>},$ (11) $\displaystyle{\sf T}(Y)\,{\sf
wr}\,{\sf T}(Z)$ $\displaystyle=$ $\displaystyle\bigl{<}{\sf S}{(Y)}\,{\sf
wr}\,{\sf S}{(Z)}\cup\\{\alpha,\beta\\}\bigr{>}.$

For $i\in\\{1,\ldots,m\\}$, let us define the following submonoids of ${\sf
T}(Y)\,{\sf wr}\,{\sf T}(Z)$:

$\displaystyle\overline{T}_{i}$ $\displaystyle=$ $\displaystyle\\{({\rm
id},\ldots,{\rm id},\stackrel{{\scriptstyle\mbox{\footnotesize$i$-th
component}}}{{t}},{\rm id},\ldots,{\rm id}){\rm id}\in{\sf T}(Y)\,{\sf
wr}\,{\sf T}(Z)\ |\ t\in{\sf T}(Y)\\},$ $\displaystyle\overline{S}_{i}$
$\displaystyle=$ $\displaystyle\\{({\rm id},\ldots,{\rm
id},\stackrel{{\scriptstyle\mbox{\footnotesize$i$-th component}}}{{s}},{\rm
id}\ldots,{\rm id}){\rm id}\in{\sf T}(Y)\,{\sf wr}\,{\sf T}(Z)\ |\ s\in{\sf
S}{(Y)}\\},$ $\displaystyle\overline{{\sf T}(Z)}$ $\displaystyle=$
$\displaystyle\\{({\rm id},\ldots,{\rm id})t\in{\sf T}(Y)\,{\sf wr}\,{\sf
T}(Z)\ |\ t\in{\sf T}(Z)\\},$ $\displaystyle\overline{{\sf S}{(Z)}}$
$\displaystyle=$ $\displaystyle\\{({\rm id},\ldots,{\rm id})s\in{\sf
T}(Y)\,{\sf wr}\,{\sf T}(Z)\ |\ s\in{\sf S}{(Z)}\\}.$

Let us first prove (9). As $\alpha\in{\sf T}(Y)\,{\sf wr}\,{\sf S}{(Z)}$, we
find that $\bigl{<}{\sf S}{(Y)}\,{\sf wr}\,{\sf
S}{(Z)}\cup\\{\alpha\\}\bigr{>}\leqslant{\sf T}(Y)\,{\sf wr}\,{\sf S}{(Z)}$.
Since ${\sf T}(Y)=\bigl{<}{\sf S}{(Y)}\cup\\{\overline{\alpha}\\}\bigr{>}$, we
obtain that
$\overline{T}_{1}=\bigl{<}\overline{S}_{1}\cup\\{\alpha\\}\bigr{>}$, and hence
$\overline{T}_{1}\leqslant\bigl{<}{\sf S}{(Y)}\,{\sf wr}\,{\sf
S}{(Z)}\cup\\{\alpha\\}\bigr{>}$. For all $i\in\\{1,\ldots,m\\}$, there is
some $r\in{\sf S}{(Z)}$ such that $1r=i$, and, as discussed before Lemma 2.1,
we obtain that $r^{-1}\overline{T}_{1}r=\overline{T}_{i}$. Therefore
$\overline{T}_{1},\ldots,\overline{T}_{m}\leqslant\bigl{<}{\sf S}{(Y)}\,{\sf
wr}\,{\sf S}{(Z)}\cup\\{\alpha\\}\bigr{>}$. As $\overline{{\sf
S}{(Z)}}\leqslant\bigl{<}{\sf S}{(Y)}\,{\sf wr}\,{\sf
S}{(Z)}\cup\\{\alpha\\}\bigr{>}$ and ${\sf T}(Y)\,{\sf wr}\,{\sf
S}{(Z)}=(\overline{T}_{1}\times\cdots\times\overline{T}_{m})\rtimes\overline{{\sf
S}{(Z)}}$, we obtain that ${\sf T}(Y)\,{\sf wr}\,{\sf
S}{(Z)}\leqslant\bigl{<}{\sf S}{(Y)}\,{\sf wr}\,{\sf
S}{(Z)}\cup\\{\alpha\\}\bigr{>}$, and so the required equality holds.

Now we show that (10). As $\beta\in{\sf S}{(Y)}\,{\sf wr}\,{\sf T}(Z)$, we
have that $\bigl{<}{\sf S}{(Y)}\,{\sf wr}\,{\sf
S}{(Z)}\cup\\{\beta\\}\bigr{>}\leqslant{\sf S}{(Y)}\,{\sf wr}\,{\sf T}(Z)$. As
${\sf T}(Y)=\bigl{<}{\sf S}{(Y)}\cup\\{\overline{\alpha}\\}\bigr{>}$, we
obtain that $\overline{{\sf T}(Z)}=\bigl{<}\overline{{\sf
S}{(Z)}}\cup\\{\beta\\}\bigr{>}$. As ${\sf S}{(Y)}\,{\sf wr}\,{\sf
T}(Z)=(\overline{S}_{1}\times\cdots\times\overline{S}_{m})\rtimes\overline{{\sf
T}(Z)}$, we obtain that ${\sf S}{(Y)}\,{\sf wr}\,{\sf
T}(Z)\leqslant\bigl{<}{\sf S}{(Y)}\,{\sf wr}\,{\sf
S}{(Z)}\cup\\{\beta\\}\bigr{>}$, and so the claim is proved.

As ${\sf T}(Y)\,{\sf wr}\,{\sf
T}(Z)=(\overline{T}_{1}\times\cdots\times\overline{T}_{m})\rtimes\overline{{\sf
T}(Z)}$, the arguments in the previous two paragraphs show that ${\sf
T}(Y)\,{\sf wr}\,{\sf T}(Z)\leqslant\bigl{<}{\sf S}{(Y)}\,{\sf wr}\,{\sf
S}{(Z)}\cup\\{\alpha,\beta\\}\bigr{>}$. As $\alpha,\ \beta\in{\sf T}(Y)\,{\sf
wr}\,{\sf T}(Z)$, we obtain (11).

As ${\sf S}{(Y)}\,{\sf wr}\,{\sf S}{(Z)}$ is a proper submonoid of each of the
monoids ${\sf T}(Y)\,{\sf wr}\,{\sf T}(Z)$, ${\sf T}(Y)\,{\sf wr}\,{\sf
S}{(Z)}$ and ${\sf S}{(Y)}\,{\sf wr}\,{\sf T}(Z)$, equation (8) must be valid.
In order to show (7), it suffices to prove that $\mbox{\emph{\mbox{\rm
rank}\,}}{({\sf T}(Y)\,{\sf wr}\,{\sf T}(Z):{\sf S}{(Y)}\,{\sf wr}\,{\sf
S}{(Z)})}>1$. Suppose that $\gamma\in{\sf T}(Y)\,{\sf wr}\,{\sf T}(Z)$ such
that $\bigl{<}{\sf S}{(Y)}\,{\sf wr}\,{\sf
S}{(Z)}\cup\\{\gamma\\}\bigr{>}={\sf T}(Y)\,{\sf wr}\,{\sf T}(Z)$. Then there
are $g,\ g_{1},\ldots,g_{k}\in{\sf S}{(Y)}\,{\sf wr}\,{\sf S}{(Z)}$, such that
$g\gamma g_{1}\gamma\cdots\gamma g_{k}=\alpha$. Thus $\gamma
g_{1}\gamma\cdots\gamma g_{k}=g^{-1}\alpha$ and hence $\ker\gamma\subseteq\ker
g^{-1}\alpha=\\{((1,1)g,(2,1)g)\\}\cup\Delta$, where $\Delta=\\{(x,x)\mid x\in
X\\}$. Since $\gamma\not\in{\sf S}{(Y)}\,{\sf wr}\,{\sf S}{(Z)}$, we obtain
that $\ker\gamma=\\{((1,1)g,(2,1)g)\\}\cup\Delta$. Similarly, there exist $h,\
h_{1},\ldots,h_{k}\in{\sf S}{(Y)}\,{\sf wr}\,{\sf S}{(Z)}$ such that $h\gamma
h_{1}\gamma\cdots\gamma h_{k}=\beta$, Thus $\gamma h_{1}\gamma\cdots\gamma
h_{k}=h^{-1}\beta$ and hence

$\ker\gamma\subseteq\ker
h^{-1}\beta=\\{((1,1)h,(1,2)h),\ldots,((n,1)h,(n,2)h)\\}\cup\Delta.$

Hence, for some $i\in\\{1,\ldots,n\\}$, we have
$((1,1)g,(2,1)g)=((i,1)h,(i,2)h)$, that is,
$((1,1),(2,1))gh^{-1}=((i,1),(i,2))$. This, however, is a contradiction,
because $(1,1)\sim_{\mathcal{P}}(2,1)$, but $(i,1)\not\sim_{\mathcal{P}}(i,2)$
and the transformation $gh^{-1}$ preserves the equivalence relation
$\sim_{\mathcal{P}}$.

Therefore we verified that $\bigl{<}{\sf S}{(Y)}\,{\sf wr}\,{\sf
S}{(Z)}\cup\\{\gamma\\}\bigr{>}$ is a proper submonoid of the wreath product
${\sf T}(Y)\,{\sf wr}\,{\sf T}(Z)$, which shows that equation (7) must hold. ∎

##  4\. The Rank of ${\sf S}{(X,\mathcal{P})}$

In this section we prove the following theorem.

######  Theorem 4.1.

If $X$ is a finite set such that $|X|\geqslant 3$ and $\mathcal{P}$ is a
uniform partition of $X$ then ${\sf S}{(X,\mathcal{P})}$ is generated by two
elements.

In our terminology, the previous theorem gives that $\mbox{\emph{\mbox{\rm
rank}\,}}{\sf S}{(X,\mathcal{P})}=2$. We note that the rank of a transitive
permutation group, such as ${\sf S}{(X,\mathcal{P})}$, is defined in
permutation group theory as the number of orbits of a point-stabilizer. Thus,
in order to avoid possible confusion, we decided to state the theorem above
without using the notation $\mbox{\emph{\mbox{\rm rank}\,}}{\sf
S}{(X,\mathcal{P})}$.

Theorem 1.1 will follow from Lemmas 3.1 and 3.2 and Theorem 4.1.

Using the fact that ${\sf S}{(X,\mathcal{P})}$ is isomorphic to a wreath
product ${\sf S}{(Y)}\,{\sf wr}\,{\sf S}{(Z)}$, it is not difficult to see
that ${\sf S}{(X,\mathcal{P})}$ is generated by four elements. Indeed,
consider the subgroups $\overline{{\sf S}{(Y)}}_{i}$ and $\overline{{\sf
S}{(Z)}}$ defined in (3) and (4). Since ${\sf S}{(Y)}\,{\sf wr}\,{\sf
S}{(Z)}=(\overline{{\sf S}{(Y)}}_{1}\times\cdots\times\overline{{\sf
S}{(Y)}}_{m})\rtimes{\sf S}{(Z)}$ and ${\sf S}{(Z)}$ is transitive by
conjugation on the subgroups $\overline{{\sf S}{(Y)}}_{i}$, we obtain that
${\sf S}{(Y)}\,{\sf wr}\,{\sf S}{(Z)}=\bigl{<}\overline{{\sf
S}{(Y)}}_{1},\overline{{\sf S}{(Z)}}\bigr{>}$. Since $\overline{{\sf
S}{(Y)}}_{1}$ and $\overline{{\sf S}{(Z)}}$ are full symmetric groups, they
are generated by two elements, and so we obtain that ${\sf S}{(Y)}\,{\sf
wr}\,{\sf S}{(Z)}$ is generated by at most four elements. Essentially this is
proved in [17, Theorem 2.6].

Before proving Theorem 4.1, we state two simple lemmas.

Let $G$ be a permutation group acting on the set $\\{1,\ldots,n\\}$ and let
$\mathbb{F}$ be a field. Let $V$ denote the $n$-dimensional vector space over
$\mathbb{F}$ with basis $\\{e_{1},\ldots,e_{n}\\}$. The group $G$ can be
thought of as a permutation group on the set $\\{e_{1},\ldots,e_{n}\\}$, and
this defines an $\mathbb{F}G$-module structure on $V$ as follows:

$e_{i}g=e_{ig}\quad\mbox{for}\quad i\in\\{1,\ldots,n\\}\mbox{ and }g\in G.$

The module $V$ is called the permutation module for $G$ over $\mathbb{F}$.

The following lemma is well-known; see, for instance, [18, Lemma 5.3.4].

######  Lemma 4.1.

If $X=\\{1,\ldots,n\\}$, then the permutation module for ${\sf S}{(X)}$ over a
field $\mathbb{F}$ of characteristic $p$ has precisely two proper non-trivial
submodules:

$\displaystyle U_{1}$ $\displaystyle=$ $\displaystyle\left\\{(a,a,\ldots,a)\
|\ a\in\mathbb{F}\right\\}\quad\mbox{and}$ $\displaystyle U_{2}$
$\displaystyle=$ $\displaystyle\left\\{(a_{1},\ldots,a_{n})\ |\
a_{1}+\cdots+a_{n}=0\right\\}.$

Further, if $p\mid n$ then $U_{1}\leqslant U_{2}$; otherwise $V=U_{1}\oplus
U_{2}$.

Suppose that $G=G_{1}\times\cdots\times G_{k}$ where the $G_{i}$ are finite
groups. For $I\subseteq\\{G_{1},\ldots,G_{k}\\}$ the function
$\varrho_{I}:G\rightarrow\prod_{G_{i}\in I}G_{i}$ is the natural projection
map. We also write $\varrho_{i}$ for $\varrho_{\\{G_{i}\\}}$. A subgroup $X$
of $G$ is said to be a strip if for each $i=1,\ldots,k$ either
$X\varrho_{i}=1$ or $X\varrho_{i}\cong X$. The set of $G_{i}$ such that
$X\varrho_{i}\neq 1$ is called the support of $X$ and is denoted ${\sf
Supp}\,X$. Two strips $X_{1}$ and $X_{2}$ are disjoint if ${\sf
Supp}\,X_{1}\cap{\sf Supp}\,X_{2}=\emptyset$. A strip $X$ is said to be full
if $X\varrho_{i}=G_{i}$ for all $G_{i}\in{\sf Supp}\,X$, and $X$ is called
non-trivial if $|{\sf Supp}\,X|\geqslant 2$. A subgroup $K$ of $G$ is said to
be subdirect if $K\varrho_{i}=G_{i}$ for all $i$.

We recall a well-known lemma on finite simple groups which can be found in
[23, page 328]. The proof of the lemma is elementary and does not use the
finite simple group classification.

######  Lemma 4.2.

Let $M$ be a direct product of finitely many non-abelian, finite simple groups
and let $H$ be a subdirect subgroup of $M$. Then $H$ is the direct product of
pairwise disjoint full strips of $M$.

The wreath product of two transformation semigroups $S$ and $R$ was defined in
Section 2, and the definition can also be used to construct the wreath product
of two permutation groups $G$ and $H$. Recall that the wreath product $G\,{\sf
wr}\,H$ is isomorphic to $G^{m}\rtimes H$ and a typical element of $G\,{\sf
wr}\,H$ is denoted by $(\pi_{1},\ldots,\pi_{m})\sigma$ where $\pi_{i}\in G$
and $\sigma\in H$. Setting $\pi=(\pi_{1},\ldots,\pi_{m})$, the same element
can also be written as $\pi\sigma$. The following lemma facilitates the
calculations in $G\,{\sf wr}\,H$.

######  Lemma 4.3.

Let $\pi\sigma,\ \pi_{1}\sigma_{1},\ \pi_{2}\sigma_{2}\in G\,{\sf wr}\,H$
where $G$ and $H$ are as above. Then

  1. (i)

$\pi_{1}\sigma_{1}\pi_{2}\sigma_{2}=\pi_{1}(\pi_{2})^{\sigma_{1}^{-1}}\sigma_{1}\sigma_{2}$;

  2. (ii)

$(\pi\sigma)^{-1}=(\pi^{-1})^{\sigma}\sigma^{-1}$;

  3. (iii)

$(\pi\sigma)^{n}=\pi\pi^{\sigma^{-1}}\pi^{\sigma^{-2}}\cdots\pi^{\sigma^{-n+1}}\sigma^{n}$.

In particular the projection map $\varrho:G\,{\sf wr}\,H\rightarrow H$ defined
by $\pi\sigma\mapsto\sigma$ is a homomorphism.

###### Proof.

The assertion that $\varrho$ is a homomorphism follows from (i). The rest can
be verified using (5) and (6). ∎

Now we are ready to prove Theorem 4.1. Permutations of a finite set will be
written as products of disjoint cycles.

###### The proof of Theorem 4.1.

By Lemma 2.1(iv), it suffices to show, for $Y=\\{1,\ldots,n\\}$ and
$Z=\\{1,\ldots,m\\}$, that the group $W={\sf S}{(Y)}\,{\sf wr}\,{\sf S}{(Z)}$
is generated by two elements whenever $nm\geqslant 3$. Since, for a finite set
$Y$, the group ${\sf S}{(Y)}$ is generated by two elements, we may assume that
$n\geqslant 2$ and $m\geqslant 2$. Let ${{\sf A}{(Y)}}$ denote the group of
even permutations of $Y$. Then ${{\sf A}{(Y)}}$ is a normal subgroup of index
two of ${\sf S}{(Y)}$. As $W={\sf S}{(Y)}^{m}\rtimes{\sf S}{(Z)}$, we may
consider the subgroups ${{\sf A}{(Y)}}^{m}$ and ${\sf S}{(Y)}^{m}$ of $W$ and
let $A$ and $S$ denote these subgroups respectively.

Let us define

$\displaystyle x$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{ll}({\rm id},(1,2),{\rm id},\ldots,{\rm
id})(1,2,\ldots,m)&\mbox{if either $n$ or $m$ is odd}\\\ ({\rm id},(1,2),{\rm
id},\ldots,{\rm id})(2,3,\ldots,m)&\mbox{otherwise}\end{array}\right.$
$\displaystyle y$ $\displaystyle=$ $\displaystyle((1,2,\ldots,n),{\rm
id},\ldots,{\rm id})(1,2).$

Set $M=\left<x,y\right>$ and we claim that $M=W$.

Let $\varrho:W\rightarrow{\sf S}{(Z)}$ denote the natural projection map in
Lemma 4.3. If either $n$ or $m$ is odd then
$\left<(1,2),(1,2,\ldots,m)\right>\leqslant M\varrho$; otherwise
$\left<(1,2),(2,3,\ldots,m)\right>\leqslant M\varrho$. As

$\left<(1,2),(1,2,\ldots,m)\right>=\left<(1,2),(2,3,\ldots,m)\right>={\sf
S}{(Z)},$

we obtain that $M\varrho={\sf S}{(Z)}$. As $S=\ker\varrho$, in order to prove
that $M=W$, it suffices to show that $S\leqslant M$.

Next we claim that $A\leqslant M$. If $n=2$, then $A=1$, and so we may assume
that $n\geqslant 3$. First we suppose that $n=3$. In this case
$A\cong(C_{3})^{m}$ and so $A$ can be viewed as a $W$-module over
$\mathbb{F}_{3}$, and, in particular, it can be viewed as a ${\sf
S}{(Z)}$-module over the same field. In fact, $A$ is the natural permutation
module for ${\sf S}{(Z)}$. Since $M\varrho={\sf S}{(Z)}$, the intersection
$A\cap M$ is an ${\sf S}{(Z)}$-submodule of $A$. Now
$y^{2}=((1,2,3),(1,2,3),{\rm id},\ldots,{\rm id})$ and so $y^{2}\in A\cap M$,
but, if $m\geqslant 3$, then $y^{2}$ is not an element of either of the two
proper submodules listed in Lemma 4.1. Therefore $A\cap M=A$, and so
$A\leqslant M$ follows when $n=3$ and $m\geqslant 3$. The case $(n,m)=(3,2)$
can be checked using a computer algebra package such as GAP [8] or Magma [6].

Let us assume that $n=4$, that is, $Y=\\{1,\ldots,4\\}$, and, as above, we may
also assume without loss of generality that $m\geqslant 3$. Note that ${{\sf
A}{(Y)}}$ admits the decomposition ${{\sf A}{(Y)}}=U\rtimes V$ where
$U=\left<(1,2)(3,4),(1,3)(2,4)\right>$ and $V=\left<(1,2,3)\right>$. Further,
$U$ can be considered as an irreducible $V$-module over $\mathbb{F}_{2}$.

Let $m$ be odd and set $z_{1}=(x^{m}y^{2})^{2}$. As

$x^{m}y^{2}=((1,3,4),(1,3,4),(1,2),\ldots,(1,2)),$

we obtain that $z_{1}=(x^{m}y^{2})^{2}=((1,4,3),(1,4,3),{\rm id},\ldots,{\rm
id})$. As $M\varrho={\sf S}{(Z)}$, the subgroup $M$ has an element of the form
$\pi(2,3)$ where $\pi\in S$. Then set $z=z_{1}^{\pi(2,3)}$ and compute that
$z=z_{1}^{\pi(2,3)}=(\sigma_{1},{\rm id},\sigma_{3},{\rm id},\ldots,{\rm id})$
where $\sigma_{1}$ and $\sigma_{3}$ are three-cycles in ${\sf S}{(Y)}$. Now
set

$w_{1}=(x^{m})^{y^{4}}x^{m}=((1,2)(3,4),(1,2)(3,4),{\rm id},\ldots,{\rm id})$

and consider the element $w=w_{1}^{z}w_{1}$. Now, as the first component of
$z\in S$ is a non-trivial three cycle, the element $w$ is of the form
$w=(\sigma,{\rm id},\ldots,{\rm id})$ where
$\sigma\in\\{(1,2)(3,4),(1,3)(4,2),(1,4)(2,3)\\}$.

Assume now that $m$ is even and set $z=(x^{m-1}y^{2})^{4}$. Easy computation
yields that

$z=(x^{m-1}y^{2})^{4}=({\rm id},(1,3,4),{\rm id},\ldots,{\rm id})$

and that

$w=(x^{m-1})^{y^{4}}x^{m-1}=({\rm id},(1,2)(3,4),{\rm id},\ldots,{\rm id}).$

As $V$ is irreducible on $U$, the computation above shows that the
$\left<z\right>$-submodule generated by $w$ coincides with $U\times
1\times\cdots\times 1$ of $m$ is odd, and $1\times U\times 1\times\cdots\times
1$ if $m$ is even. Thus $U\times 1\times\cdots\times 1\leqslant M$ in the
former case, and $1\times U\times 1\times\cdots\times 1\leqslant M$ in the
latter. As $M\varrho={\sf S}{(Z)}$, we also obtain that $U^{m}\leqslant M$.

Now the quotient $A/U^{m}\cong V^{m}\cong(C_{3})^{m}$ can be considered as a
permutation module for ${\sf S}{(Z)}$ over $\mathbb{F}_{3}$, and as $(M\cap
A)/U^{m}\unlhd M/U^{m}$ and $M\varrho={\sf S}{(Z)}$, we obtain that $(M\cap
A)/U^{m}$ is a ${\sf S}{(Z)}$-submodule. However, the image of the element $z$
above is not in either of the proper submodules listed in Lemma 4.1, and so we
obtain that $(M\cap A)/U^{m}=A/U^{m}$ which shows that $A\leqslant M$.

Hence we have shown that $A\leqslant M$ if $n\leqslant 4$. Assume now that
$n\geqslant 5$. In this case ${{\sf A}{(Y)}}$ is a non-abelian finite simple
group and so $A$ is a non-abelian characteristically simple group.

Set $Q=M\cap S$. Clearly, $Q\leqslant S$ and $Q\unlhd M$. Let us show that $Q$
is a subdirect subgroup of $S={\sf S}{(Y)}^{m}$. If $n$ or $m$ is odd then set
$z=x^{m}=((1,2),(1,2),\ldots,(1,2))$; otherwise set $z=x^{m-1}=({\rm
id},(1,2),(1,2),\ldots,(1,2))$. Further,

$y^{2}=((1,2,\ldots,n),(1,2,\ldots,n),{\rm id},\ldots,{\rm id}).$

Therefore $z,\ y^{2}\in Q$. Let $\varrho_{2}$ denote the second coordinate
projection $\varrho_{2}:S\rightarrow{\sf S}{(Y)}$. Since
$z\varrho_{2}=(1,2)\in Q\varrho_{2}$ and $y^{2}\varrho_{2}=(1,2,\ldots,n)\in
Q\varrho_{2}$, we obtain that $Q\varrho_{2}={\sf S}{(Y)}$. Simple computation
shows that if $\tau\in Q$ and $\pi\sigma\in M$ then
$\tau^{\pi\sigma}\varrho_{2\sigma}=\tau^{\pi}\varrho_{2}$. Therefore

${\sf S}{(Y)}=Q\varrho_{2}=Q^{\pi\sigma}\varrho_{2\sigma}=Q\varrho_{2\sigma}.$

As $Q\varrho_{2}={\sf S}{(Y)}$, it follows that $Q\varrho_{i}={\sf S}{(Y)}$
for all $i$, and so $Q$ is a subdirect subgroup of $S={\sf S}{(Y)}^{m}$.
Consider the commutator subgroup $Q^{\prime}$. Since $S^{\prime}=A$, we obtain
that $Q^{\prime}\leqslant A$. Further, as $Q\varrho_{i}={\sf S}{(Y)}$, we also
obtain, for all $i$, that $Q^{\prime}\varrho_{i}={{\sf A}{(Y)}}$. Therefore
$Q^{\prime}$ is a subdirect subgroup of $A={{\sf A}{(Y)}}^{m}$. Set $R=M\cap
A$. Since $Q^{\prime}\leqslant R$ and $Q^{\prime}$ is a subdirect subgroup, we
obtain that so is $R$; that is, by Lemma 4.2, $R$ is a direct product of
disjoint strips.

Let $S$ be a strip in $R$ and let $\mathcal{S}\subseteq\\{1,\ldots,m\\}$ be
the support of $S$. We claim that $\mathcal{S}$ is a block for the action of
${\sf S}{(Z)}$. Indeed, if $\sigma\in{\sf S}{(Z)}$ then there is some $\pi\in
S$ such that $\pi\sigma\in M$. Then $S^{\pi\sigma}$ is strip in $R$ and so
either $S=S^{\pi\sigma}$ or $S\cap S^{\pi\sigma}=1$. The support of
$S^{\pi\sigma}$ is $\mathcal{S}^{\sigma}$. Thus either
$\mathcal{S}^{\sigma}=\mathcal{S}$ or
$\mathcal{S}^{\sigma}\cap\mathcal{S}=\emptyset$, which shows that
$\mathcal{S}$ is a block, as required. Since ${\sf S}{(Z)}$ is primitive on
$\\{1,\ldots,m\\}$ either $|\mathcal{S}|=1$ or $\mathcal{S}=\\{1,\ldots,m\\}$.
If the latter holds, then $Q$ is a strip. This, however, is impossible.
Indeed, if $m=2$ and $n$ is odd, then set $z=xy=({\rm
id},(1,2)(1,2,\ldots,n))$; if $m=2$ and $n$ is even then set
$z=xy^{2}=((1,2,\ldots,n),(1,2)(1,2,\ldots,n))$; if $m\geqslant 3$, then set
$z=y^{2}=((1,2,\ldots,n),(1,2,\ldots,n),{\rm id},\ldots,{\rm id})$. Then in
all cases $z^{2}\in R$, but $z^{2}$ is not in a full strip (if $m=2$ and $n$
is even then note that the first component of $z^{2}$ is of order $n/2$ and
the second is of order $n-1$). Thus $|\mathcal{S}|=1$, and so $A\leqslant M$.

This completes the proof of the claim that that $A\leqslant M$ for all $n$ and
$m$.

Note that $A$ is a normal subgroup of $W$ and let $x\mapsto\widehat{x}$ denote
the natural homomorphism $W\rightarrow W/A$. If $H\leqslant W$, then
$\widehat{H}$ denotes the image $HA/A$ of $H$. Then $\widehat{W}\cong
C_{2}\,{\sf wr}\,{\sf S}{(Z)}$ and $\widehat{S}\cong(C_{2})^{m}$. We claim
that $\widehat{S}\leqslant\widehat{M}$. Note that
$\widehat{M}\cap\widehat{S}\unlhd\widehat{M}$. If $\pi\sigma\in\widehat{M}$
and $u\in\widehat{M}\cap\widehat{S}$ then $u^{\pi\sigma}=u^{\sigma}$. As
$u^{\pi\sigma}\in\widehat{M}\cap\widehat{S}$ we obtain that
$u^{\sigma}\in\widehat{M}\cap\widehat{S}$ which shows that
$\widehat{M}\cap\widehat{S}$ is a ${\sf S}{(Z)}$-submodule of
$\widehat{S}\cong(C_{2})^{m}$. It is clear that $\widehat{S}$ is the natural
permutation module for ${\sf S}{(Z)}$ over $\mathbb{F}_{2}$. Lemma 4.1 lists
the non-trivial proper submodules $U_{1}$ and $U_{2}$ of $\widehat{S}$.

If both $n$ and $m$ are even then $\widehat{x}^{m-1}=(0,1,\ldots,1)$ and this
element is not in either $U_{1}$ or $U_{2}$. Hence
$\widehat{S}\leqslant\widehat{M}$. If this is not the case, then
$\widehat{x}^{m}=(1,1,\ldots,1)$ which shows that $U_{1}\leqslant\widehat{M}$.
If $n$ is even and $m$ is odd then $\widehat{y}^{2}=(1,1,0,\ldots,0)$ and so
$U_{2}\leqslant\widehat{M}$. Therefore in this case $U_{1}\oplus
U_{2}\leqslant\widehat{M}$ follows.

Suppose that $n$ is odd. If $m=2$ then $xy=({\rm id},(1,2)(1,2,\ldots,n))$.
Thus $\widehat{xy}$ is not in either of the proper submodules listed in Lemma
4.1. Hence $\widehat{S}\leqslant\widehat{M}$ follows in this case. If
$m\geqslant 3$, then

$xy=({\rm id},(1,2),{\rm id},\ldots,{\rm id},(1,2,\ldots,n))(2,3\ldots,m).$

Let $\pi=({\rm id},(1,2),{\rm id},\ldots,{\rm id},(1,2,\ldots,n))$ and
$\sigma=(2,3,\ldots,m)$ so that $xy=\pi\sigma$. As $\sigma^{m-1}=1$, it
follows from Lemma 4.3 that

$(xy)^{m-1}=\pi\pi^{\sigma^{-1}}\ldots\pi^{\sigma^{-m+2}}.$

Thus $(xy)^{m-1}$ is of the form $({\rm id},\pi_{2},\ldots,\pi_{m})$ where,
for $i=2,\ldots,m$, the permutation $\pi_{i}$ is either $(1,2)(1,2,\ldots,n)$
or $(1,2,\ldots,n)(1,2)$, that is, $\pi_{i}$ is a cycle with length $n-1$. As
$n$ is odd, $\pi_{i}\not\in{{\sf A}{(Y)}}$, and so
$(\widehat{xy})^{m-1}=(0,1,1,\ldots,1)$. Now if $m$ is even then
$(\widehat{xy})^{m-1}$ is not an element of $U_{1}$ or $U_{2}$, and so
$\widehat{S}\leqslant\widehat{M}$ follows also in this case. If $m$ is odd
then this shows that $U_{2}\leqslant\widehat{M}$, and as we proved above that
$U_{1}\leqslant\widehat{M}$, it follows that
$\widehat{S}\leqslant\widehat{M}$.

Thus we have shown that $S\leqslant M$ as required. As explained above, $M=W$
now follows. ∎

The main result of the paper can now be proved.

###### The proof of Theorem 1.1.

As usual, we assume without loss of generality that $X=Y\times Z$ where
$Y=\\{1,\ldots,n\\}$, $Z=\\{1,\ldots,m\\}$ and $\mathcal{P}$ is the partition

$\\{\\{(1,1),\ldots,(n,1)\\},\ldots,\\{(1,m),\ldots,(n,m)\\}\\}.$

By Lemmas 2.1, 3.1, 3.2 and Theorem 4.1,

$\mbox{\emph{\mbox{\rm rank}\,}}{{\sf T}(X,\mathcal{P})}=\mbox{\emph{\mbox{\rm
rank}\,}}{({\sf T}(X,\mathcal{P}):{\sf
S}{(X,\mathcal{P})})}+\mbox{\emph{\mbox{\rm rank}\,}}{{\sf
S}{(X,\mathcal{P})}}\\\ =\mbox{\emph{\mbox{\rm rank}\,}}{({\sf T}(Y)\,{\sf
wr}\,{\sf T}(Z):{\sf S}{(Y)}\,{\sf wr}\,{\sf S}{(Z)})}+\mbox{\emph{\mbox{\rm
rank}\,}}{{\sf S}{(Y)}\,{\sf wr}\,{\sf S}{(Z)}}=4.$

The assertions concerning $\mbox{\emph{\mbox{\rm
rank}\,}}\Gamma(X,\mathcal{P})$ and $\mbox{\emph{\mbox{\rm
rank}\,}}\Sigma(X,\mathcal{P})$ can be proved very similarly. ∎

## Acknowledgment

We acknowledge with gratitude some conversations with John D. Dixon, Peter M.
Neumann and Joseph J. Rotman.

The first author was partially supported by FCT and FEDER, Project POCTI-
ISFL-1-143 of Centro de Algebra da Universidade de Lisboa, and by FCT and
PIDDAC through the project PTDC/MAT/69514/2006.

The second author is grateful to the Centro de Álgebra da Universidade de
Lisboa for the invitation and the hospitality; he was also supported by the
Hungarian Scientific Research Fund (OTKA) grant F049040.

## References

  * [1] J. Araújo and J. D. Mitchell.  Relative ranks in the monoid of endomorphisms of an independence algebra.  Monatsh. Math., 151(1):1–10, 2007.
  * [2] J. Araújo, J. D. Mitchell, and N. Silva.  On generating countable sets of endomorphisms.  Algebra Universalis, 50(1):61–67, 2003.
  * [3] S. Banach.  Sur un theorème de M. Sierpiński.  Fund. Math., 25:5–6, 1935.
  * [4] George Barnes and Inessa Levi.  Ranks of semigroups generated by order-preserving transformations with a fixed partition type.  Comm. Algebra, 31(4):1753–1763, 2003.
  * [5] George Barnes and Inessa Levi.  On idempotent ranks of semigroups of partial transformations.  Semigroup Forum, 70(1):81–96, 2005.
  * [6] Wieb Bosma, John Cannon, and Catherine Playoust.  The Magma algebra system I: The user language.  J. Symbolic Comput., 24(3-4):235–265, 1997.  Computational algebra and number theory (London, 1993).
  * [7] J. Cichoń, J. D. Mitchell, and M. Morayne.  Generating continuous mappings with Lipschitz mappings.  Trans. Amer. Math. Soc., 359(5):2059–2074 (electronic), 2007.
  * [8] The GAP Group.  GAP – Groups, Algorithms, and Programming, Version 4.4.10, 2007\.
  * [9] G. U. Garba.  On the nilpotent ranks of certain semigroups of transformations.  Glasgow Math. J., 36(1):1–9, 1994.
  * [10] Gracinda M. S. Gomes and John M. Howie.  On the ranks of certain semigroups of order-preserving transformations.  Semigroup Forum, 45(3):272–282, 1992.
  * [11] P. M. Higgins, J. M. Howie, J. D. Mitchell, and N. Ruškuc.  Countable versus uncountable ranks in infinite semigroups of transformations and relations.  Proc. Edinb. Math. Soc. (2), 46(3):531–544, 2003.
  * [12] P. M. Higgins, J. D. Mitchell, M. Morayne, and N. Ruškuc.  Rank properties of endomorphisms of infinite partially ordered sets.  Bull. London Math. Soc., 38(2):177–191, 2006.
  * [13] Peter M. Higgins, John M. Howie, and Nikola Ruškuc.  Generators and factorisations of transformation semigroups.  Proc. Roy. Soc. Edinburgh Sect. A, 128(6):1355–1369, 1998.
  * [14] John M. Howie.  Fundamentals of semigroup theory, volume 12 of London Mathematical Society Monographs. New Series.  The Clarendon Press Oxford University Press, New York, 1995.  Oxford Science Publications.
  * [15] John M. Howie and Robert B. McFadden.  Idempotent rank in finite full transformation semigroups.  Proc. Roy. Soc. Edinburgh Sect. A, 114(3-4):161–167, 1990.
  * [16] John M. Howie, N. Ruškuc, and P. M. Higgins.  On relative ranks of full transformation semigroups.  Comm. Algebra, 26(3):733–748, 1998.
  * [17] Pei Huisheng.  On the rank of the semigroup $T_{E}(X)$.  Semigroup Forum, 70(1):107–117, 2005.
  * [18] Peter Kleidman and Martin Liebeck.  The subgroup structure of the finite classical groups, volume 129 of London Mathematical Society Lecture Note Series.  Cambridge University Press, Cambridge, 1990.
  * [19] Inessa Levi.  Nilpotent ranks of semigroups of partial transformations.  Semigroup Forum, 72(3):459–476, 2006.
  * [20] Inessa Levi and Steve Seif.  Combinatorial techniques for determining rank and idempotent rank of certain finite semigroups.  Proc. Edinb. Math. Soc. (2), 45(3):617–630, 2002.
  * [21] J. D. P. Meldrum.  Wreath products of groups and semigroups, volume 74 of Pitman Monographs and Surveys in Pure and Applied Mathematics.  Longman, Harlow, 1995.
  * [22] Maria Isabel Marques Ribeiro.  Rank properties in finite inverse semigroups.  Proc. Edinburgh Math. Soc. (2), 43(3):559–568, 2000.
  * [23] Leonard L. Scott.  Representations in characteristic $p$.  In The Santa Cruz Conference on Finite Groups (Univ. California, Santa Cruz, Calif., 1979), volume 37 of Proc. Sympos. Pure Math., pages 319–331. Amer. Math. Soc., Providence, R.I., 1980.
  * [24] Wacł aw Sierpiński.  Sur les suites infinies de fonctions définies dans les ensembles quelconques.  Fund. Math., 24:209–212, 1935.
  * [25] Howard Straubing.  The wreath product and its applications.  In Formal properties of finite automata and applications (Ramatuelle, 1988), volume 386 of Lecture Notes in Comput. Sci., pages 15–24. Springer, Berlin, 1989.