One-way permutations, computational asymmetry and distortion
Jean-Camille Birget ∗
October 30, 2018
Abstract
Computational asymmetry, i.e., the discrepancy between the complexity of transformations
and the complexity of their inverses, is at the core of one-way transformations. We introduce a
computational asymmetry function that measures the amount of one-wayness of permutations. We
also introduce the word-length asymmetry function for groups, which is an algebraic analogue of
computational asymmetry. We relate boolean circuits to words in a Thompson monoid, over a
fixed generating set, in such a way that circuit size is equal to word-length. Moreover, boolean
circuits have a representation in terms of elements of a Thompson group, in such a way that circuit
size is polynomially equivalent to word-length. We show that circuits built with gates that are
not constrained to have fixed-length inputs and outputs, are at most quadratically more compact
than circuits built from traditional gates (with fixed-length inputs and outputs). Finally, we show
that the computational asymmetry function is closely related to certain distortion functions: The
computational asymmetry function is polynomially equivalent to the distortion of the path length
in Schreier graphs of certain Thompson groups, compared to the path length in Cayley graphs of
certain Thompson monoids. We also show that the results of Razborov and others on monotone
circuit complexity lead to exponential lower bounds on certain distortions.
1 Introduction
The existence of one-way functions, i.e., functions that are “easy to evaluate” but “hard to invert”,
is a major open problem. Much of cryptography depends on one-way functions; moreover, indirectly,
their existence is connected to the question whether P is different from NP. In this paper we give some
connections between these questions and some group-theoretic concepts:
(1) We continue the work of [7], [8], and [9], on the relation between combinational circuits, on the one
hand, and Thompson groups and monoids on the other hand. We give a representation of any circuit
by a word over the Thompson group, such that circuit size is polynomially equivalent to word-length.
(2) We establish connections between the existence of one-way permutations and the distortion func-
tion in a certain Thompson group. Distortion is an important concept in metric spaces (e.g., Bourgain
[10]) and in combinatorial group theory (e.g., Gromov [17], Farb [14]).
Overview:
Subsections 1.1 - 1.6 of the present Section define and motivate the concepts used: One-way functions
and one-way permutations; computational asymmetry; word-length asymmetry; reversible computing;
distortion; Thompson groups and monoids. In Section 2 we show that circuits can be represented by
elements of Thompson monoids: A boolean circuit is equivalent to a word over a fixed generating set
∗Supported by NSF grant CCR-0310793. Some of the results of this paper were presented at the AMS Section
Meeting, Oct. 21-23, 2005, Lincoln, Nebraska (http://www.ams.org/amsmtgs/2117 program.html), and at the conference
“Various Faces of Cryptography”, 10 Nov. 2006 at City College of CUNY, New York.
http://arxiv.org/abs/0704.1569v1
http://www.ams.org/amsmtgs/2117_program.html
of a Thompson monoid, with circuit size being equal (or linearly equivalent) to word-length over the
generating set. The Thompson monoids that appear here are monoid generalizations of the Thompson
group G2,1, obtained when bijections are generalized to partial functions [9]. Section 3 shows that
computational asymmetry and word-length asymmetry (for the Thompson groups and monoids) are
linearly related. In Section 4 we give a representation of arbitrary (not necessarily bijective) circuits
by elements of the Thompson group G2,1; circuit size is polynomially equivalent to word-length over
a certain generating set in the Thompson group. In Section 5 we show that the computational
asymmetry function of permutations is polynomially related to a certain distortion in a Thompson
group. Section 6 contains miscellaneous results, in particular that the work of Razborov and others
on monotone circuit complexity leads to exponential lower bounds on certain distortion functions.
1.1 One-way functions and one-way permutations
Intuitively, a one-way function is a function f (mapping words to words, over a finite alphabet), such
that f is “easy to evaluate” (i.e., given x0 in the domain, it is “easy” to compute f(x0)), but “hard
to invert” (i.e., given y0 in the range, it is “hard” to find any x0 such that f(x0) = y0). The concept
was introduced by Diffie and Hellman [13].
There are many ways of defining the words “easy” and “hard”, and accordingly there exist many
different rigorous notions of a one-way function, all corresponding to a similar intuition. It remains
an open problem whether one-way functions exist, for any “reasonable” definition. Moreover, for
certain definitional choices, this problem is a generalization of the famous question whether P 6= NP
[16, 34, 11].
We will base our one-way functions on combinational circuits and their size. The size of a circuit
will also be called its complexity. Below, {0, 1}n (for any integer n ≥ 0) denotes the set of all bitstrings
of length n. A combinational circuit with input-output function f : {0, 1}m → {0, 1}n is an acyclic
boolean circuit with m input wires (or “input ports”) and n output wires (or “output ports”). The
circuit is made from gates of type not, and, or, fork, as well as wire-crossings or wire-swappings. These
gates are very traditional and are defined as follows.
and: (x1, x2) ∈ {0, 1}2 7−→ y ∈ {0, 1}, where y = 1 if x1 = x2 = 1, and y = 0 otherwise.
or: (x1, x2) ∈ {0, 1}2 7−→ y ∈ {0, 1}, where y = 0 if x1 = x2 = 0, and y = 1 otherwise.
not: x ∈ {0, 1} 7−→ y ∈ {0, 1}, where y = 0 if x = 1, y = 1 otherwise.
fork: x ∈ {0, 1} 7−→ (x, x) ∈ {0, 1}2.
Another gate that is often used is the exclusive-or gate,
xor: (x1, x2) ∈ {0, 1}2 7−→ y ∈ {0, 1}, where y = 1 if x1 6= x2, and y = 0 otherwise.
The wire-swapping of the ith and jth wire (i < j) is described by the bit transposition (or bit position
transposition)
τi,j : uxivxjw ∈ {0, 1}ℓ 7−→ uxjvxiw ∈ {0, 1}ℓ, where |u| = i− 1, |v| = j − i− 1, |w| = ℓ− j − 1.
The fork and wire-swapping operations, although heavily used, are usually not explicitly called “gates”;
but because of their important role we will need to consider them explicitly. Other notations for the
gates: and(x1, x2) = x1 ∧ x2, or(x1, x2) = x1 ∨ x2, not(x) = x, xor(x1, x2) = x1 ⊕ x2.
A combinational circuit for a function f : {0, 1}m → {0, 1}n is defined by an acyclic directed graph
drawn in the plane (with crossing of edges allowed). In the circuit drawing, the m input ports are
vertices lined up in a vertical column on the left end of the circuit, and the n output ports are vertices
lined up in a vertical column on the right end of the circuit. The input and output ports and the gates
of the circuit (including the fork gates, but not the wire transpositions) form the vertices of the circuit
graph. We often view the circuit as cut into vertical slices. A slice can be any collection of gates and
wires in the circuit such that no gate in a slice is an ancestor of another gate in the same slice, and
no wire in a slice is an ancestor of another wire in the same slice (unless these two wires are an input
wire and an output wire of a same gate). Two slices do not overlap, and every wire and every gate
belongs to some slice. For more details on combinational circuits, see [32, 43, 11].
The size of a combinational circuit is defined to be the number of gates in the circuit, including
forks and wire-swappings, as well as the input ports and the output ports. For a function f : {0, 1}m →
{0, 1}n, the circuit complexity (denoted C(f)) is the smallest size of any combinational circuit with
input-output function f .
A cause of confusion about gates in a circuit is that gates of a certain type (e.g., and) are tradi-
tionally considered the same, no matter where they occur in the circuit. However, gates applied to
different wires in a circuit are different functions; e.g., for the and gate, (x1, x2, x3) 7→ (x1 ∧ x2, x3) is
a different function than (x1, x2, x3) 7→ (x1, x2 ∧ x3).
1.2 Computational Asymmetry
Computational asymmetry is the core property of one-way functions. Below we will define computa-
tional asymmetry in a quantitative way, and in a later Section we will relate it to the group-theoretic
notion of distortion.
For the existence of one-way functions, it is mainly the relation between the circuit complexity
C(f) of f and the circuit complexity C(f−1) of f−1 that matters, not the complexities of f and of
f−1 themselves. Indeed, a classical padding argument can be used: If we add C(f) “identity wires” to
a circuit for f , then the resulting circuit has linear size as a function of its number of input wires; see
Proposition 1.2 below. (An identity wire is a wire that goes directly from an input port to an output
port, without being connected to any gate.)
In [11] (page 230) Boppana and Lagarias considered logC(f ′)/logC(f) as a measure of one-
wayness; here, f ′ denotes an inverse of f , i.e., any function such that f ◦ f ′ ◦ f = f . Massey and
Hiltgen [25, 19] introduced the phrases complexity asymmetry and computational asymmetry for injec-
tive functions, in reference to the situation where the circuit complexities C(f) and C(f−1) are very
different. The concept of computational asymmetry can be generalized to arbitrary (non-injective)
functions, with the meaning that for every inverse f ′ of f , C(f) and C(f ′) are very different.
In [25] Massey made the following observation. For any large-enough fixed m and for almost all
permutations f of {0, 1}m, the circuit complexities C(f) and C(f−1) are very similar:
C(f) ≤ C(f−1) ≤ 10 C(f)
Massey’s proof is adapted from the Shannon lower bound [35] and the Lupanov upper bound [23] (see
also [19], [32]), from which it follows that almost all functions and almost all permutations (and their
inverses) have circuit complexity close to the Shannon bounds. Massey’s observation can be extended
to the set of all functions f : {0, 1}m → {0, 1}n, i.e., for almost all f and for every inverse f ′ of f , the
complexities C(f) and C(f ′) are within constant factors of each other.
Hence, computationally asymmetric permutations are rare among the boolean permutations overall
(and similarly for functions). This is an interesting fact about computational asymmetry, but by
itself it does not imply anything about the existence or non-existence of one-way functions, not even
heuristically. Indeed, Massey proved his linear relation C(f) = Θ(C(f ′)) in the situation where
C(f) = Θ(2m), and then uses the fact that the condition C(f) = Θ(2m) holds for almost all boolean
permutations and for almost all boolean functions. But there also exist functions with C(f) = O(mk),
with k a small constant. In particular, one-way functions (if they exist) have small circuits; by
definition, one-way functions violate the condition C(f) = Θ(2m).
A well-known candidate for a one-way permutation is the following. For a large prime number p
and a primitive root r modulo p, consider the map x ∈ {0, 1, . . . , p−2} 7−→ rx−1 ∈ {0, 1, . . . , p−2}.
This is a permutation whose inverse, known as the discrete logarithm, is believed to be difficult to
compute.
Measuring computational asymmetry:
Let S{0,1}m denote the set of all permutations of {0, 1}m, i.e., S{0,1}m is the symmetric group. We
will measure the computational asymmetry of all permutations of {0, 1}m (for all m > 0) by defining
a computational asymmetry function, as follows. A function a : N → N is an upper bound on the
computational asymmetry function iff for all all m > 0 and all permutations f of {0, 1}m we have:
C(f−1) ≤ a
. The computational asymmetry function α of the boolean permutations is the
least such function a(.). Hence:
Definition 1.1 The computational asymmetry function α of the boolean permutations is defined as
follows for all s ∈ N : α(s) = max
C(f−1) : C(f) ≤ s, f ∈ S{0,1}m , m > 0
Note that in this definition we look at all combinational circuits, for all permutations in
m>0 S{0,1}m ;
we don’t need to work with non-uniform or uniform families of circuits.
Computational asymmetry is closely related to one-wayness, as the next proposition shows.
Proposition 1.2
(1) For infinitely many n we have: There exists a permutation fn of {0, 1}n such that fn is computed
by a circuit of size ≤ 3n, but f−1n has no circuit of size < α(n).
(2) Suppose that α is exponential, i.e., there is k > 1 such that for all n, α(n) ≥ kn. Then k ≤ 2,
and there is a constant c > 1 such that we have: For every integer n ≥ 1 there exists a permutation
Fn of {0, 1}n which is computed by a circuit of size ≤ c n, but F−1n has no circuit of size < kn.
Proof. (1) By the definition of α, for every m > 0 there exists a permutation F of {0, 1}m such that
F is computed by a circuit of some size CF , but F
−1 has no circuit of size < α(CF ). Let n = CF ,
and let us consider the function fn : {0, 1}CF → {0, 1}CF defined by fn : (x,w) 7−→ (F (x), w), for all
x ∈ {0, 1}m and w ∈ {0, 1}CF−m.
Then fn(x,w) is computed by a circuit of size CF + 2 (CF − m); the term “2 (CF −m)” comes
from counting the input-output wires of w. Hence fn has a circuit of size ≤ 3n. On the other hand,
(y,w) 7−→ f−1n (y,w) = (F−1(y), w) is not computed by any circuit of size < α(CF ), so f−1n has no
circuit of size < α(n).
(2) For every n ≥ 1 there exists a permutation F of {0, 1}n such that F is computed by a circuit of
some size CF , and F
−1 has a circuit of size CF−1 = α(CF ) ≥ kCF ; moreover, F−1 has no circuit of
size < α(CF ). Thus, k
CF ≤ CF−1 ≤ 2n (1 + co lognn ), for some constant co > 1; the latter inequality
comes from the Lupanov upper bound [23] (or see Theorem 2.13.2 in [32]). Hence, k ≤ 2 and n ≤
CF ≤ 1log2 k n + c1
, for some constant c1 > 0. Hence, for all n ≥ 1 there exists a permutation F
of {0, 1}n with circuit size CF ∈ [n, 1log2 k · n+ c1 ·
], such that CF−1 = α(CF ) ≥ kCF ≥ kn. ✷
We will show later that the computational asymmetry function is closely related to the distortion
of certain groups within certain monoids.
Remarks:
Although in this paper we only use the computational asymmetry function of the boolean permuta-
tions, the concept can be generalized. Let Inj({0, 1}m, {0, 1}n) denote the set of all injective functions
{0, 1}m → {0, 1}n. The computational asymmetry function αinj of the injective boolean functions is
defined by
αinj(s) = max
C(f−1) : C(f) ≤ s, f ∈ Inj({0, 1}m, {0, 1}n), m > 0, n > 0
More generally, let ({0, 1}n){0,1}m denote the set of all functions {0, 1}m → {0, 1}n. The computa-
tional asymmetry of all finite boolean functions is defined by
αfunc(s) = max
C(f ′) : C(f) ≤ s, ff ′f = f, f, f ′ ∈ ({0, 1}n){0,1}m , n > 0,m > 0
When we compare functions we will be mostly interested in their asymptotic growth pattern.
Hence we will often use the big-O notation, and the following definitions.
By definition, two functions f1 : N → N and f2 : N → N are linearly equivalent iff there are
constants c0, c1, c2 > 0 such that for all n ≥ c0 : f1(n) ≤ c1 f2(c1n) and f2(n) ≤ c2 f1(c2n).
Notation: f1 ≃lin f2.
Two functions f1 and f2 (from N to N) are called polynomially equivalent iff there are constants
c0, c1, c2, d, e > 0 such that for all n ≥ c0 : f1(n) ≤ c1 f2(c1nd)d and f2(n) ≤ c2 f1(c2ne)e. Notation:
f1 ≃poly f2.
1.3 Wordlength asymmetry
We introduce an algebraic notion that looks very similar to computational asymmetry:
Definition 1.3 Let G be a group, let M be a monoid with generating set Γ (finite or infinite), and
suppose G ⊆M . The word-length asymmetry function of G within M (over Γ) is
λ(n) = max{ |g−1|Γ : |g|Γ ≤ n, g ∈ G}.
The word-length asymmetry function λ depends on G, M , Γ, and the embedding of G in M .
Consider the right Cayley graph of the monoid M with generating set Γ; its vertex set is M and
the edges have the form x
γ−→ γx (for x ∈ M , γ ∈ Γ). For x, y ∈ M , the directed distance d(x, y)
in the Cayley graph is the shortest length over all paths from x to y in the Cayley graph; if no path
from x to y exists, the directed distance is infinite. By “path” we always mean directed path.
Lemma 1.4 Under the above conditions on G, M , Γ, we have for every g ∈ G : d(1, g−1) = d(g,1)
and d(1, g) = d(g−1,1).
Proof. Let η : Γ∗ →M be the map that evaluates generator sequences in M . If v ∈ Γ∗ is the label of
a shortest path from 1 to g−1 in the Cayley graph then g ·η(v) = 1 inM , hence η(v) = g−1. Therefore,
the path starting at g and labeled by v ends at 1; hence d(g,1) ≤ |v| = d(1, g−1). In a similar way
one proves that d(1, g−1) ≤ d(g,1). The equality d(1, g) = d(g−1,1) is also proved in a similar way.
Since |g|Γ is the distance d(1, g) in the graph of M , and since |g−1|Γ = d(1, g−1) = d(g,1), the
word-length asymmetry also measures the asymmetry of the directed distance, to or from the identity
element 1 in the Cayley graph of M , restricted to vertices in the subgroup G.
For distances to or from the identity element of M it does not matter whether we consider the left
Caley graph or the right Caley graph.
1.4 Computational asymmetry and reversible computing
Reversible computing deals with the following questions: If a function f is injective (or bijective) and
computable, can f be computed in such a way that each elementary computation step is injective
(respectively bijective)? And if such injective (or bijective) computations are possible, what is their
complexity, compared to the usual (non-injective) complexity?
One of the main results is the following (Bennett’s theorem [4, 5], and earlier work of Lecerf
[22]): Let f be an injective function, and assume f and f−1 are computable by deterministic Turing
machines with time complexity Tf (.), respectively Tf−1(.). Then f (and also f
−1) is computable
by a reversible Turing machine (in which every transition is deterministic and injective) with time
complexity O(Tf + Tf−1). Note that only injectiveness (not bijectiveness) is used here.
Bennett’s theorem has the following important consequence, which relates reversible computing
to one-way functions: Injective one-way functions exist iff there exist injective functions that have
efficient traditional algorithms but that do not have efficient reversible algorithms.
Toffoli representation
Remarkably, it is possible to “simulate” any function f : {0, 1}m → {0, 1}n (injective or not, one-
way or not) by a bijective circuit; a circuit is called bijective iff the circuit is made from bijective
gates. Here, bijective circuits will be built from the wire swapping operations and the following
bijective gates: not (negation), c-not (the Controlled Not, also called “Feynman gate”) defined by
(x1, x2) ∈ {0, 1}2 7−→ (x1, x1 ⊕ x2) ∈ {0, 1}2, and cc-not (the Doubly Controlled Not, also called
“Toffoli gate”) defined by (x1, x2, x3) ∈ {0, 1}3 7−→ (x1, x2, (x1 ∧ x2)⊕ x3) ∈ {0, 1}3.
Theorem 1.5 (Toffoli [40]). For every boolean function f : {0, 1}m → {0, 1}n there exists a bijective
boolean circuit βf (over the bijective gates not, c-not, cc-not, and wire transpositions), with input-
output function βf : x 0
n ∈ {0, 1}m+n 7−→ f(x) x ∈ {0, 1}n+m.
In other words, f(x) consists of the projection onto the first n bits of βf (x 0
n); equivalently, f(.) =
projn ◦ βf ◦ concat0n(.), where projn projects a string of length n+m to the first n bits, and concat0n
concatenates 0n to the right of a string. See Theorems 4.1, 5.3 and 5.4 of [40], and see Fig. 1 below.
✲ f(x)
Fig. 1: Toffoli representation of the function f .
The Toffoli representation contains two non-bijective actions: The projection at the output, and
the forced setting of the value of some of the input wires.
Toffoli’s proofs and constructions are based on truth tables, and he does not prove anything about
the circuit size of βf (counting the bijective gates), compared to the circuit size of f . The following
gives a polynomial bound on the size of the bijective circuit, at the expense of a large number of input-
and output-wires.
Theorem 1.6 (E. Fredkin, T. Toffoli [15]). For every boolean function f : {0, 1}m → {0, 1}n with
circuit size C(f) there exists a bijective boolean circuit Bf (over a bounded collection of bijective gates,
e.g., not, c-not, cc-not, and wire transpositions), with input-output function
Bf : x 0
n+C(f) ∈ {0, 1}m+n+C(f) 7−→ f(x) z(x) ∈ {0, 1}m+n+C(f)
for some z(x) ∈ {0, 1}m+C(f).
If g : {0, 1}m → {0, 1}m is a permutation then there exists a bijective boolean circuit Ug (over
bijective gates), with input-output function
Ug : x 1
m 0m+C ∈ {0, 1}3m+C 7−→ g(x) g(x) x 0C ∈ {0, 1}3m+C
where C = max{C(g), C(g−1)}, and g(x) is the bitwise complement of g(x).
Later we will introduce another reversible representation of boolean functions by bijective gates;
we will need only one 0-wire, but the gates will be taken from the Thompson group G2,1, i.e., we will
also use non-length-preserving transformations of bitstrings (Theorems 4.1 and 4.2 below).
1.5 Distortion
We will prove later (Theorem 5.10) that computational asymmetry has a lot to do with distortion,
a concept introduced into group theory by Gromov [17] and Farb [14]. Distortion is already known
to have connections with isoperimetric functions (see [28], [29], [24]). A somewhat different problem
about distortion (for finite metric spaces) was tackled by Bourgain [10].
We will use a slightly more general notion of distortion, based on (possibly directed) countably
infinite rooted graphs, and their (directed) path metric.
A weighted directed graph is a structure (V,E, ω) where V is a set (called the vertex set), E ⊆ V ×V
(called the edge set), and ω : E 7−→ R>0 is a function (called the weight function); note that every edge
has a strictly positive weight. It is sometimes convenient to define ω(u, v) = ∞ when (u, v) ∈ V ×V −E.
A path in (V,E) is a sequence of edges (ui, vi) (1 ≤ i ≤ n) such that ui+1 = vi for all i < n, and
such that all elements in {ui : 1 ≤ i ≤ n} ∪ {vn} are distinct; u1 is called the start vertex of this
path, and vn is called the end vertex of this path; the sum of weights
i=1 ω(ui, vi) over the edges
in the path is called the length of the path. Here we do not consider any paths with infinitely many
edges; but we allow V and E to be countably infinite. A vertex w2 is said to be reachable from a
vertex w1 in (V,E) iff there exists a path with start vertex w1 and end vertex w2. If w2 is reachable
from w1 then the minimum length over all paths from w1 to w2 is called the directed distance from
w1 to w2, denoted d(w1, w2); since we only consider finite paths here, this minimum exists. If w2 is
not reachable from w1 then we define d(w1, w2) to be ∞. Clearly we have w1 = w2 iff d(w1, w2) = 0,
and for all u, v, w ∈ V , d(u,w) ≤ d(u, v) + d(v,w). In a directed graph, the function d(., .) need not
be symmetric. The function d : V ×V → R≥0 ∪{∞} is called the directed path metric of (V,E, ω). A
rooted directed weighted graph is a structure (V,E, ω, r) where (V,E, ω) is a directed weighted graph,
r ∈ V , and all vertices in V are reachable from r.
A set M with a function d : M × M → R≥0 ∪ {∞}, satisfying the two axioms w1 = w2 iff
d(w1, w2) = 0, and d(u,w) ≤ d(u, v) + d(v,w), will be called directed metric space (a.k.a. quasi-metric
space).
Any subset G embedded in a directed metric space M becomes a directed metric space by using
the directed distance of M . We call this the directed distance on G inherited from M .
If G ⊆ V for a rooted directed weighted graph (V,E, ω, r), we consider the function ℓ : g ∈ G 7−→
d(r, g) ∈ R≥0, which we call the directed length function on G inherited from (V,E, ω, r). (The value
∞ will not appear here since all of G is reachable from r.)
We now define distortion in a very general way. Intuitively, distortion in a set is a quantitative
comparison between two (directed) length functions that are defined on the same set.
Definition 1.7 Let G be a set, and let ℓ1 and ℓ2 be two functions G → R≥0. The distortion of ℓ1
with respect to ℓ2 is the function δℓ1,ℓ2 : R≥0 → R≥0 defined by
δℓ1,ℓ2(n) = max{ℓ1(g) : g ∈ G, ℓ2(g) ≤ n}.
We will also use the notation δ[ℓ1, ℓ2](.) for δℓ1,ℓ2(.). When we consider a distortion δℓ1,ℓ2(.) we often
assume that ℓ2 ≤ ℓ1 or ℓ2 ≤ O(ℓ1); this insures that the distortion is at least linear, i.e., δℓ1,ℓ2(n) ≥ c n,
for some constant c > 0. We will only deal with functions obtained from the lengths of finite paths
in countable directed graphs, so in that case the functions ℓi are discrete, and the distortion function
exists. The next Lemma generalizes the distortion result of Prop. 4.2 of [14].
Lemma 1.8 Let G be a set and consider three functions ℓ3, ℓ2, ℓ1 : G→ R≥0 such that ℓ1(.) ≥ ℓ2(.) ≥
ℓ3(.). Then the corresponding distortions satisfy: δℓ1,ℓ3(.) ≤ δℓ1,ℓ2 ◦ δℓ2,ℓ3(.).
Proof. The inequalities ℓ1(.) ≥ ℓ2(.) ≥ ℓ3(.) guarantee that the three distortions δℓ1,ℓ3 , δℓ1,ℓ2 , and
δℓ2,ℓ3 are at least as large as the identity map. By definition,
δℓ1,ℓ2
δℓ2,ℓ3(n)
= max{ℓ1(x) : x ∈ G, ℓ2(x) ≤ δℓ2,ℓ3(n)}
= max
ℓ1(x) : x ∈ G, ℓ2(x) ≤ max{ℓ2(z) : z ∈ G, ℓ3(z) ≤ n}
= max
ℓ1(x) : x ∈ G, (∃z ∈ G)
ℓ2(x) ≤ ℓ2(z) and ℓ3(z) ≤ n
≥ max{ℓ1(x) : x ∈ G, ℓ3(x) ≤ n} = δℓ1,ℓ3(n).
The last inequality follows from the fact that if ℓ3(x) ≤ n then for some z (e.g., for z = x):
ℓ2(x) ≤ ℓ2(z) and ℓ3(z) ≤ n. ✷
Examples of distortion:
Distortion and asymmetry are unifying concepts that apply to many fields.
1. Gromov distortion: Let G be a subgroup of a group H, with generating sets ΓG, respectively
ΓH , such that ΓG ⊆ ΓH , and such that ΓG = Γ−1G and ΓH = Γ
H . This determines a Cayley graph
for G and a Cayley graph for H. Now we have two distance functions on G, one obtained from the
Cayley graph of G itself (based on ΓG), and the other inherited from the embedding of G in H. See
[17], [10], and [14].
The Gromov distortion function is a natural measure of the difficulty of the generalized word
problem. A very important case is when both ΓG and ΓH are finite. Here are some results for that
case:
Theorem of Ol′shanskii and Sapir [29] (making precise and proving the outline on pp. 66-67 in [17]):
All Dehn functions of finitely presented groups (and “approximately all” time complexity functions of
nondeterministic Turing machines) are Gromov distortion functions of finitely generated subgroups
of FG2×FG2; here, FG2 denotes the 2-generated free group. Moreover, in [6] it was proved that
FG2×FG2 is embeddable with linear distortion in the Thompson group G2,1. So the theorem of
Ol′shanskii and Sapir also holds for the finitely generated subgroups of G2,1.
Actually, Gromov [17] and Bourgain [10] defined the distortion to be 1
·max{|g|ΓG : |g|ΓH ≤ n, g ∈
G}, i.e., they use an extra factor 1
. However, the connections between distortion, the generalized word
problem, and complexity (as we just saw, and will further see in the present paper) are more direct
without the factor 1
2. Bourgain’s distortion theorem: Given a finite metric space G with n elements, the aim is to
find embeddings of G into a finite-dimensional euclidean space. The two distances of G are its given
distance and the inherited euclidean distance. In this problem the goal is to have small distortion,
as a function of the cardinality of G, while also keeping the dimension of the euclidean space small.
Bourgain [10] found a bound O(n log n) for the distortion (or “O(log n)” in Bourgain’s and Gromov’s
terminology). This is an important result. See also [21], [2], [3].
3. Generator distortion: A variant of Gromov’s distortion is obtained when G = H, but ΓG $ ΓH .
So here we look at the distorting effect of a change of generators in a given group. When ΓG and
ΓH are both finite the generator distortion is linear; however, when ΓG is finite and ΓH is infinite
the distortion becomes interesting. E.g., for the Thompson group G2,1 let us take ΓG to be any finite
generating set, and for ΓH let us take ΓG ∪ {τi,j : 1 ≤ i < j}; here τi,j is the position transposition
defined earlier. Then the generator distortion is exponential (see [7]). Also, the word problem of G2,1
over any finite generating set ΓG is in P, but the word problem of G2,1 over ΓG ∪ {τi,j : 1 ≤ i < j} is
coNP-complete (see [7] and [8]).
4. Monoids and directed distance: Gromov’s distortion and the generator distortion can be
generalized to monoids. We repeat what we said about Gromov distortion, but G and H are now
monoids, and ΓG, respectively ΓH , are monoid generating sets which are used to define monoid Cayley
graphs. We will use the left Cayley graphs. We assume ΓG ⊆ ΓH . In each Cayley graph there is
a directed distance, defined by the lengths of directed paths. The monoid G now has two directed
distance functions, the distance in the Cayley graph ofG itself, and the directed distance thatG inherits
from its embedding into the Cayley graph of H. We denote the word-length of g ∈ G over ΓG by |g|G;
this is the minimum length of all words over ΓG that represent g; it is also the length of a shortest
path from the identity to g in the Cayley graph of G. Similarly, we denote the word-length of h ∈ H
over ΓH by |h|H . The definition of the distortion becomes: δ(n) = max{|g|G : g ∈ G, |g|H ≤ n}.
5. Schreier graphs: Let G, H, and F be groups, where F is a subgroup of H. Let ΓH be a
generating set of ΓH , and assume ΓH = Γ
H . We can define the Schreier left coset graph of H/F
over the generating set ΓH , and the distance function dH/F (., .) in this coset graph. By definition,
this Schreier graph has vertex set H/F (i.e., the left cosets, of the form h · F with h ∈ H), and it has
directed edges of the form h · F γ−→ γg · F , for h ∈ H, γ ∈ ΓH . The graph is symmetric; for every
edge as above there is an opposite edge γh ·F γ
−→ h ·F . Because of symmetry the Schreier graph has
a (symmetric) distance function based on path length, dH/F (., .) : H/F ×H/F → N.
Next, assume that G is embedded into H/F by some injective function G →֒ H/F . Such an
embedding happens, e.g., if G and F are subgroups of H such that G∩F = {1}. Indeed, in that case
each coset in H/F contains at most one element of G (since g1F = g2F implies g
2 g1 ∈ F ∩G = {1}).
The group G now inherits a distance function from the path length in the Schreier graph of H/F .
Comparing this distance with other distances in G leads to distortion functions. E.g., if the group G
is also embedded in a monoid M with monoid generating set ΓM , this leads to the following distortion
function: δG(n) = max{dH/F (F, gF ) : g ∈ G, |g|M ≤ n}.
It will turn out that for appropriate choices of G,F,H, ΓH , and ΓM , this last distortion is polyno-
mially related to the computational asymmetry function α of boolean permutations (Theorem 5.10).
6. Asymmetry functions: We already saw the computational asymmetry function of combinational
circuits, and the word-length asymmetry function of a group embedded in a monoid. More generally,
in any quasi-metric space (S, d), where d(., .) is a directed distance function, an asymmetry function
A : R≥0 → R≥0 can be defined by A(n) = max{d(x2, x1) : x1, x2 ∈ S, d(x1, x2) ≤ n}.
This asymmetry function can also be viewed as the distortion of drev with respect to d in S; here
drev denotes the reverse directed distance, defined by drev(x1, x2) = d(x2, x1).
7. Other distortions:
- Distortion can compare lengths of proofs (or lengths of expressions) in various, more or less pow-
erful proof systems (respectively description languages). Distortion can also compare the duration of
computations or of rewriting processes in various models of computation. Hence, many (perhaps all)
notions of complexity are examples of distortion. Distortion is an algebraic or geometric representation
(or cause) of complexity.
- Instead of length and distance, other measures (e.g., volumes in higher dimension, energy, action,
entropy, etc.) could be used.
1.6 Thompson-Higman groups and monoids
The Thompson groups, introduced by Richard J. Thompson [38, 26, 39], are finitely presented infinite
groups that act as bijections between certain subsets of {0, 1}∗. So, the elements of the Thompson
groups are transformations of bitstrings, and hence they are related to input-output maps of boolean
circuits. In this subsection we define the Thompson group G2,1 (also known as “V ”), as well as its
generalization (by Graham Higman [18]) to the group Gk,1 that partially acts on A
∗, for any finite
alphabet A of size k ≥ 2. We will follow the presentation of [6] (see also [8] and [7]); another reference
is [33], which is also based on string transformations but with a different terminology; the classical
references [38, 26, 39, 18, 12] do not describe the Thompson groups by transformations of finite strings.
Because of our interest in strings and in circuits, we also use generalizations of the Thompson groups
to monoids, as introduced in [9].
Some preliminary definitions, all fairly standard, are needed in order to define the Thompson-
Higman group Gk,1. First, we pick any alphabet A of cardinality |A| = k. By A∗ we denote the set
of all finite words (or “strings”) over A; the empty word ε is also in A∗. We denote the length of
w ∈ A∗ by |w| and we let An denote the set of words of length n. We denote the concatenation of
two words u, v ∈ A∗ by uv or by u · v; the concatenation of two subsets B,C ⊆ A∗ is defined by
BC = {uv : u ∈ B, v ∈ C}. A right ideal of A∗ is a subset R ⊆ A∗ such that RA∗ ⊆ R. A generating
set of a right ideal R is, by definition, a set C such that R is equal to the intersection of all right
ideals that contain C; equivalently, C generates R (as a right ideal) iff R = CA∗. A right ideal R is
called essential iff R has a non-empty intersection with every right ideal of A∗. For u, v ∈ A∗, we call
u a prefix of v iff there exists z ∈ A∗ such that uz = v. A prefix code is a subset C ⊆ A∗ such that
no element of C is a prefix of another element of C. A prefix code C over A is maximal iff C is not
a strict subset of any other prefix code over A. It is easy to prove that a right ideal R has a unique
minimal (under inclusion) generating set CR, and that CR is a prefix code; moreover, CR is a maximal
prefix code iff R is an essential right ideal.
For a partial function f : A∗ → A∗ we denote the domain by Dom(f) and the image (range) by
Im(f). A restriction of f is any partial function f1 : A
∗ → A∗ such that Dom(f1) ⊆ Dom(f), and
such that f1(x) = f(x) for all x ∈ Dom(f1). An extension of f is any partial function of which f
is a restriction. An isomorphism between right ideals R1, R2 of A
∗ is a bijection ϕ : R1 → R2 such
that for all r1 ∈ R1 and all z ∈ A∗: ϕ(r1z) = ϕ(r1) · z. The isomorphism ϕ is uniquely determined
by a bijection between the prefix codes that minimally generate R1, respectively R2. One can prove
[39, 33, 6] that every isomorphism ϕ between essential right ideals has a unique maximal extension
(within the category of isomorphisms between essential right ideals of A∗); we denote this unique
maximal extension by max(ϕ).
Now, finally, we define the Thompson-Higman group Gk,1: It consists of all maximally extended
isomorphisms between finitely generated essential right ideals of A∗. The multiplication consists of
composition followed by maximum extension: ϕ · ψ = max(ϕ ◦ ψ). Note that Gk,1 acts partially and
faithfully on A∗ on the left.
Every element ϕ ∈ Gk,1 can be described by a bijection between two finite maximal prefix codes;
this bijection can be described concretely by a finite function table. When ϕ is described by a maximally
extended isomorphism between essential right ideals, ϕ : R1 → R2, we call the minimum generating
set of R1 the domain code of ϕ, and denote it by domC(ϕ); similarly, the minimum generating set of
R2 is called the image code of ϕ, denoted by imC(ϕ).
Thompson and Higman proved that Gk,1 is finitely presented. Also, when k is even Gk,1 is a simple
group, and when k is odd Gk,1 has a simple normal subgroup of index 2. In [6] it was proved that
the word problem of Gk,1 over any finite generating set is in P (in fact, more strongly, in the parallel
complexity class AC1). In [8, 7] it was proved that the word problem of Gk,1 over Γ∪{τi,j : 1 ≤ i < j} is
coNP-complete, where Γ is any finite generating set of Gk,1, and where τi,j is the position transposition
introduced in Subsection 1.1.
Because of connections with circuits we consider the subgroup lpGk,1 of all length-preserving
elements of Gk,1; more precisely, lpGk,1 = {ϕ ∈ Gk,1 : ∀x ∈ Dom(ϕ), |x| = |ϕ(x)|}. See [8] for
a study of lpGk,1 and some of its properties. In particular, it was proved that lpGk,1 is a direct limit
of finite alternating groups, and that lpG2,1 is generated by the set {N,C, T} ∪ {τi,i+1 : 1 ≤ i},
where N : x1w 7→ x1w, C : x1x2w 7→ x1 (x2 ⊕ x1)w, and T : x1x2x3w 7→ x1x2 (x3 ⊕ (x2 ∧ x1))w
(for x1, x2, x3 ∈ {0, 1} and w ∈ {0, 1}∗). Thus (recalling Subsection 1.4), N,C, T are the not, c-not,
cc-not gates, applied to the first (left-most) bits of a binary string. It is known that the gates not,
c-not, cc-not, together with the wire-swappings, form a complete set of gates for bijective circuits (see
[36, 40, 15]); hence, lpG2,1 is closely related to the field of reversible computing.
It is natural to generalize the bijections between finite maximal prefix codes to functions between
finite prefix codes. Following [9] we will define below the Thompson-Higman monoids Mk,1. First,
some preliminary definitions. A right-ideal homomorphism of A∗ is a total function ϕ : R1 → A∗ such
that R1 is a right ideal, and such that for all r1 ∈ R1 and all z ∈ A∗: ϕ(r1z) = ϕ(r1) · z. It is
easy to prove that Im(ϕ) is then also a right ideal of A∗. From now on we will write a right-ideal
homomorphism as a total surjective function ϕ : R1 → R2, where both R1 and R2 are right ideals. The
homomorphism ϕ is uniquely determined by a total surjective function f : P1 → S2, with P1, S2 ⊂ A∗
where P1 is the prefix code (not necessarily maximal) that generates R1 as a right ideal, and where
S2 is a set (not necessarily a prefix code) that generates R2 as a right ideal; f can be described by a
finite function table.
For two sets X,Y , we say that X and Y “intersect” iff X ∩ Y 6= ∅. We say that a right ideal
R′1 is essential in a right ideal R1 iff R
1 intersects every right ideal that R1 intersects. An essential
restriction of a right-ideal homomorphism ϕ : R1 → R2 is a right ideal-homomorphism Φ : R′1 → R′2
such that R′1 is essential in R1, and for all x
1 ∈ R′1: ϕ(x′1) = Φ(x′1). In that case we also say that ϕ
is an essential extension of Φ. If Φ is an essential restriction of ϕ then R′2 = Im(Φ) will automatically
be essential in R2 = Im(ϕ). Indeed, if I is any no-empty right subideal of R1 then I ∩R′1 6= ∅, hence
∅ 6= Φ(I ∩ R′1) ⊆ Φ(I) ∩ Φ(R′1) = Φ(I) ∩ R′2; moreover, any non-empty right subideal J of R2 is of
the form J = Φ(I), where I = Φ−1(J) is a non-empty right subideal of R1; hence, for any non-empty
right subideal J of R2, ∅ 6= J ∩R′2.
The free monoid A∗ can be pictured by its right Cayley graph, which is easily seen to be the
infinite regular k-ary tree with vertex set A∗ and edge set {(v, va) : v ∈ A∗, a ∈ A}. We simply call
this the tree of A∗. It is a directed, rooted tree, with all paths directed away from the root ε (the
empty word); by “path” we will always mean a directed path. Many of the previously defined concepts
can be reformulated more intuitively in the context of the tree of A∗: A word v is a prefix of a word
w iff v is an ancestor of w in the tree. A set P is a prefix code iff no two elements of P are on a
common path. A set R is a right ideal iff any path that starts in R has all its vertices in R. The
prefix code that generates R consists of the elements of R that are maximal (within R) in the prefix
order, i.e., maximally close (along paths) to the root ε. A finitely generated right ideal R is essential
iff every infinite path eventually reaches R (and then stays in it from there on). Similarly, a finite
prefix code P is maximal iff any infinite path starting at the root eventually intersects P . For two
finitely generated right ideals R′, R with R′ ⊂ R we have: R′ is essential in R iff any infinite path
starting in R eventually reaches R′ (and then stays in it from there on).
Assume now that a total order a1 < a2 < . . . < ak has been chosen for the alphabet A; this means
that the tree of A∗ is now an oriented rooted tree, i.e., the children of each vertex v have a total order
va1 < va2 < . . . < vak. The following can be proved (see [9], Prop. 1.4(1)): Φ is an essential restriction
of ϕ iff Φ can be obtained from ϕ by starting from the table of ϕ and applying a finite number of
restriction steps of the following form: “replace (x, y) in a table by {(xa1, ya1), . . . , (xak, yak)}”.
In the tree of A∗ this means that x and y are replaced by their children xa1, . . . , xak, respectively
ya1, . . . , yak, paired according to the order on the children. One can also prove (see [9], Remark after
Prop. 1.4): Every right ideal homomorphism ϕ with table P → S has an essential restriction ϕ′ that
has a table P ′ → Q′ such that both P ′ and Q′ are prefix codes.
An important fact is the following (see [9], Prop. 1.4(2)): Every homomorphism between finitely
generated right ideals of A∗ has a unique maximal essential extension; we call it the maximum essential
extension of Φ and denote it by max(Φ).
Finally here is the definition of the Thompson-Higman monoid: Mk,1 consists of all maximum es-
sential extensions of homomorphisms between finitely generated right ideals of A∗. The multiplication
is composition followed by maximum essential extension.
One can prove the following, which implies associativity: For all right ideal homomorphisms ϕ1, ϕ2 :
max(ϕ2 ◦ ϕ1) = max(max(ϕ2) ◦ ϕ1) = max(ϕ2 ◦max(ϕ1)).
In [9] the following are proved about the Thompson-Higman monoid Mk,1:
• The Thompson-Higman group Gk,1 is the group of invertible elements of the monoid Mk,1.
• Mk,1 is finitely generated.
• The word problem of Mk,1 over any finite generating set is in P.
• The word problem of Mk,1 over a generating set Γ ∪ {τi,j : 1 ≤ i < j}, where Γ is any finite
generating set of Mk,1, is coNP-complete.
2 Boolean functions as elements of Thompson monoids
The input-output functions of digital circuits map bitstrings of some fixed length to bitstrings of a
fixed length (possibly different from the input length). In other words, circuits have input-output maps
that are total functions of the form f : {0, 1}m → {0, 1}n for some m,n > 0. The Thompson-Higman
monoid Mk,1 has an interesting submonoid that corresponds to fixed-length maps, defined as follows.
Definition 2.1 (the submonoid lepMk,1). Let ϕ : PA
∗ → QA∗ be a right-ideal homomorphism,
where P,Q ⊂ A∗ are finite prefix codes, and where P is a maximal prefix code. Then ϕ is called length
equality preserving iff for all x1, x2 ∈ Dom(ϕ) : |x1| = |x2| implies |ϕ(x1)| = |ϕ(x2)|.
The submonoid lepMk,1 of Mk,1 consists of those elements of Mk,1 that can be represented by
length-equality preserving right-ideal homomorphisms.
It is easy to check that an essential restriction of an element of lepMk,1 is again in lepMk,1, so lepMk,1
is well defined as a subset of Mk,1; moreover, one can easily check that lepMk,1 is closed under
composition, so lepMk,1 is indeed a submonoid of Mk,1.
For ϕ ∈ Mk,1 we have ϕ ∈ lepMk,1 iff there exist m > 0 and n > 0 such that Am ⊂ Dom(ϕ)
and ϕ(Am) ⊆ An. So (by means of an essential restriction, if necessary), ϕ can be represented by a
function table Am → Q ⊆ An with a fixed input length and a fixed output length (but the input and
output lengths can be different).
The motivation for studying the monoid lepMk,1 is the following. Every boolean function f :
{0, 1}m → {0, 1}n (for any m,n > 0) determines an element of lepMk,1, and conversely, this element
of lepMk,1 determines f when restricted to {0, 1}m. By considering all boolean functions as elements
of lepMk,1 we gain the ability to compose arbitrary boolean functions, even if their domain and range
“do not match”. Moreover, in lepMk,1 we are able to generate all boolean functions from gates by
using ordinary functional composition (instead of graph-based circuit lay-outs). The following remains
open:
Question: Is lepMk,1 finitely generated?
However we can find nice infinite generating sets, in connection with circuits.
Proposition 2.2 (Generators of lepMk,1). The monoid lepMk,1 has a generating set of the form
Γ ∪ {τi,i+1 : 1 ≤ i}, for some finite subset Γ ⊂ lepMk,1.
Proof. We only prove the result for k = 2; a similar reasoning works for all k (using k-ary logic).
It is a classical fact that any function f : {0, 1}m → {0, 1}n can be implemented by a combinational
circuit that uses copies of and, or, not, fork and wire-crossings. So all we need to do is to express theses
gates, at any place in the circuit, by a finite subset of lepM2,1 and by positions transpositions τi,i+1.
For each gate g ∈ {and, or} we define an element γg ∈ lepMk,1 by
γg : x1x2w ∈ {0, 1}m 7−→ g(x1, x2) w ∈ {0, 1}m−1.
Similarly we define γnot, γfork ∈ lepMk,1 by
γnot : x1w ∈ {0, 1}m 7−→ x1 w ∈ {0, 1}m,
γfork : x1w ∈ {0, 1}m 7−→ x1 x1 w ∈ {0, 1}m+1.
For each g ∈ {and, or, not, fork}, γg transforms only the first one or two boolean variables, and leaves
the other boolean variables unchanged. We also need to simulate the effect of a gate g on any variable
xi or pair of variables xixi+1, i.e., we need to construct the map
uxixi+1v ∈ {0, 1}m 7−→ u g(xi, xi+1) v ∈ {0, 1}m−1
(and similarly in case where g is not or fork). For this, we apply wire-transpositions to move xixi+1 to
the wire-positions 1 and 2, then we apply γg, then we apply more wire-transpositions in order to move
g(x1, x2) back to position i. Thus the effect of any gate anywhere in the circuit can be expressed as a
composition of γg and position transpositions in {τi,i+1 : 1 ≤ i}. ✷
Proposition 2.3 (Change of generators of lepMk,1). Let {τi,i+1 : 1 ≤ i} be denoted by τ . If
Γ,Γ′ ⊂ lepMk,1 are two finite sets such that Γ∪τ and Γ′∪τ generate lepMk,1, then the word-length over
Γ ∪ τ is linearly related to the word-length over Γ′ ∪ τ . In other words, there are constants c′ ≥ c ≥ 1
such that for all m ∈ lepMk,1 : |m|Γ∪τ ≤ c · |m|Γ′∪τ ≤ c′ · |m|Γ∪τ .
Proof. Since Γ is finite, the elements of Γ can be expressed by a finite set of words of bounded length
(≤ c) over Γ′ ∪ τ . Thus, every word of length n over Γ∪ τ is equivalent to a word of length ≤ c n over
Γ′ ∪ τ . This proves the first inequality. A similar reasoning proves the second inequality. ✷
Proposition 2.4 (Circuit size vs. lepM2,1 word-length).
Let ΓlepM2,1 ∪ {τi,j : 1 ≤ i < j} be a generating set of lepM2,1 with ΓlepM2,1 finite. Let f : {0, 1}m →
Q (⊆ {0, 1}n) be a function defining an element of lepM2,1, and let |f |lepM2,1 the word-length of f
over the generating set ΓlepM2,1 ∪ {τi,j : 1 ≤ i < j}. Let |Cf | be the circuit size of f (using any
finite universal set of gates and wire-swappings). Then |f |lepM2,1 and |Cf | are linearly related. More
precisely, for some constants c1 ≥ co ≥ 1 :
|Cf | ≤ co · |f |lepM2,1 ≤ c1 · |Cf |.
Proof. For the proof we assume that the set of gates for circuits (not counting the wire-transpositions)
is ΓlepM2,1 . If we make a different choice for the universal set of gates for circuits, and a different choice
for the finite portion ΓlepM2,1 of the generating set of lepM2,1 then the inequalities remain the same,
except for the constants c1, co.
The inequality |Cf | ≤ |f |lepM2,1 is obvious, since a word w over ΓlepM2,1 ∪ {τi,j : 1 ≤ i < j} is
automatically a circuit of size |w|.
For the other inequality, we want to simulate each gate of the circuit Cf by a word over ΓlepM2,1 ∪
{τi,j : 1 ≤ i < j}. The reasoning is the same for every gate, so let us just focus on an or gate. The
essential difference between circuit gates and elements of lepM2,1 is that in a circuit, a gate (with
2 input wires, for example) can be applied to any two wires in the circuit; on the other hand, the
functions in lepM2,1 are applied to the first few wires. However, the circuit gate or, applied to (i, i+1)
can be simulated by an element of ΓlepM2,1 and a few wire transpositions, since we have: ori,i+1(.) =
γor ◦ τ2,i+1 ◦ τ1,i(.).
The output wire of ori,i+1(.) is wire number i, whereas the output wire of γor ◦ τ2,i+1 ◦ τ1,i(.) is wire
number 1. However, instead of permuting all the wires in order to place the output of γor τ2,i+1 τ1,i(.)
on wire i, we just leave the output of γor τ2,i+1 τ1,i(.) on wire 1 for now. The simulation of the
next gate will then use appropriate transpositions τ2,j · τ1,k for fetch the correct input wires for the
next gate. Thus, each gate of Cf is simulated by one function in ΓlepM2,1 and a bounded number of
wire-transpositions in {τi,j : 1 ≤ i < j}.
At the output end of the circuit, a permutation of the n output wires is needed in order to send
the outputs to the correct wires; any permutation of n elements can be realized with < n (≤ |Cf |)
transpositions. (The inequality n ≤ |Cf | holds because since we count the output ports in the circuit
size.) ✷
Remark. The above Proposition motivates our choice of generating set of the form Γ∪{τi,j : 1 ≤ i < j}
(with Γ finite) for lepMk,1; in particular, it motivates the inclusion of all the position transpositions
τi,j in the generating set. The Proposition also motivates the definition of word-length in which τi,j
has word-length 1 for all j > i ≥ 1.
Next we will study the distortion of lepMk,1 in Mk,1. We first need some Lemmas.
Lemma 2.5 (Lemma 3.3 in [6]). If P,Q,R ⊆ A∗ are such that PA∗ ∩QA∗ = RA∗ and R is a prefix
code, then R ⊆ P ∪Q.
Proof. For any r ∈ R there are p ∈ P, q ∈ Q and v,w ∈ A∗ such that r = pv = qw. Hence p is a
prefix of q or q is a prefix of p. Let us assume p is a prefix of q = px, for some x ∈ A∗ (the other case
is similar) Hence q = px ∈ PA∗ ∩QA∗ = RA∗, and q is a prefix of r = qw. Since R is a prefix code,
r = q, hence r ∈ Q. ✷
Lemma 2.6 Let P,Q ⊂ A∗ be finite prefix codes, and let θ : PA∗ → QA∗ be a right-ideal homomor-
phism with domain PA∗ and image QA∗. Let S be a prefix code with S ⊂ QA∗. Then θ−1(S) is a
prefix code and θ−1(SA∗) = θ−1(S) A∗.
Proof. First, θ−1(S) is a prefix code. Indeed, if we had x1 = x2u for some x1, x2 ∈ θ−1(S) with u
non-empty, then θ(x1) = θ(x2) u. This would contradict the assumption that S is a prefix code.
Second, θ−1(S) ⊂ θ−1(SA∗), hence θ−1(S) A∗ ⊆ θ−1(SA∗), since θ−1(SA∗) is a right ideal. (Recall
that the inverse image of a right ideal under a right-ideal homomorphism is a right ideal.)
We also want to show that θ−1(SA∗) ⊆ θ−1(S) A∗. Let x ∈ θ−1(SA∗). So, θ(x) = sv for some
s ∈ S, v ∈ A∗, and s = qu for some q ∈ Q, u ∈ A∗. Since θ(x) = quv, we have x = puv for some
p ∈ P with θ(p) = q. Hence θ(pu) = qu = s. Therefore, x = puv with pu ∈ θ−1(s) ⊆ θ−1(S), hence
x ∈ θ−1(S) A∗. ✷
Notation: For a right-ideal homomorphism ϕ : Dom(ϕ) = PA∗ → Im(ϕ) = QA∗, where P,Q ⊂ A∗
are finite prefix codes, we define
ℓ(ϕ) = max{|z| : z ∈ P ∪Q},
For any finite prefix code C ⊂ A∗ we define
ℓ(C) = max{|z| : z ∈ C}.
Lemma 2.7 Let ϕ : Dom(ϕ) = PA∗ → Im(ϕ) = QA∗ be a right-ideal homomorphism, where P and
Q are finite prefix codes. Let R ⊂ A∗ be any finite prefix code. Then we have:
(1) ℓ(ϕ−1(R)) < ℓ(ϕ) + ℓ(R),
(2) ℓ(ϕ(R)) < ℓ(ϕ) + ℓ(R).
Proof. (1) Let r ∈ R ∩ Im(ϕ). Then every element of ϕ−1(r) has the form p1w for some p1 ∈ P
and w ∈ A∗ such that r = q1w for some q1 ∈ Q (with ϕ(p1) = q1). Hence |p1w| = |p1| + |r| − |q1| =
|r|+ |p1| − |q1|. Moreover, |r| ≤ ℓ(R) and |p1| − |q1| < ℓ(ϕ), so |p1w| < ℓ(R) + ℓ(ϕ).
(2) If r ∈ R ∩Dom(ϕ) then ϕ(r) has the form q1v for some q1 ∈ Q and v ∈ A∗ such that r = p1w
for some p1 ∈ P (with ϕ(p1) = q1). Hence |q1v| = |q1| + |r| − |p1| = |r| + |q1| − |p1|. Moreover,
|r| ≤ ℓ(R) and |q1| − |p1| < ℓ(ϕ), so |q1w| < ℓ(R) + ℓ(ϕ). ✷
For any right-ideal homomorphisms ϕi (with i = 1, . . . , N), the composite map ϕN ◦ . . . ◦ ϕ1(.) is a
right-ideal homomorphism. We say that right-ideal homomorphisms Φi (with i = 1, . . . , N) are directly
composable iff Dom(Φi+1) = Im(Φi), for i = 1, . . . , N − 1. The next Lemma shows that we can replace
composition by direct composition.
Lemma 2.8 Let ϕi : Dom(ϕi) = PiA
∗ → Im(ϕi) = QiA∗ be a right-ideal homomorphism (for
i = 1, . . . , N), where Pi and Qi are finite prefix codes. Then each ϕi has a (not necessarily essential)
restriction to a right-ideal homomorphism Φi with the following properties:
• ΦN ◦ . . . ◦ Φ1(.) = ϕN ◦ . . . ◦ ϕ1(.);
• Dom(Φi+1) = Im(Φi), for i = 1, . . . , N − 1;
• ℓ(Φi) ≤
j=1 ℓ(ϕj) for every i = 1, . . . , N .
Proof. We use induction on N . For N = 1 there is nothing to prove. So we let N > 1 and we
assume that the Lemma holds for ϕi : PiA
∗ → QiA∗ with i = 2, . . . , N , i.e., we assume that each
ϕi (for i = 2, . . . , N) has a restriction ϕ
i : P
∗ → Q′iA∗ such that ϕ′N ◦ . . . ◦ ϕ′2 = ϕN ◦ . . . ◦ ϕ2,
P ′i+1 = Q
i (for i = 2, . . . , N − 1), and ℓ(ϕ′i) ≤
j=2 ℓ(ϕj) for every i = 2, . . . , N . From P
i+1 = Q
(for i = 2, . . . , N − 1) it follows that ℓ(ϕ′N ◦ . . . ◦ ϕ′2) ≤ max{ℓ(ϕ′i) : i = 2, . . . , N} ≤
j=2 ℓ(ϕj).
Using the notation ϕ′
[N,2]
for ϕ′N ◦ . . . ◦ ϕ′2 we have Dom(ϕ′[N,2]) = P2A
∗ and Im(ϕ′
[N,2]
) = QNA
When we compose ϕ1 and ϕ
[N,2]
we obtain
ϕ−11 (Q1A
∗ ∩ P2A∗)
Φ1−→ Q1A∗ ∩ P2A∗
[N,2]−→ ϕ′
[N,2]
∗ ∩ P2A∗).
In this diagram, Φ1 is the restriction of ϕ1 to the domain ϕ
1 (Q1A
∗∩P2A∗) and image Q1A∗∩P2A∗;
and Φ′
[N,2]
is the restriction of ϕ′
[N,2]
to the domain Q1A
∗ ∩ P2A∗ and image ϕ′[N,2](Q1A
∗ ∩ P2A∗).
Hence, Φ′
[N,2]
◦Φ1 = ϕ′[N,2] ◦ϕ1, and Dom(Φ
[N,2]
) = Im(Φ1) (= Q1A
∗ ∩P2A∗). So Φ1 and Φ′[N,2] are
directly composable.
By Lemma 2.5 there is a prefix code S ⊂ A∗ such that SA∗ = Q1A∗ ∩ P2A∗ and S ⊆ Q1 ∪ P2.
Hence, ℓ(S) ≤ max{ℓ(Q1), ℓ(P2)} ≤ max{ℓ(ϕ1), ℓ(ϕ′2)} ≤ max{ℓ(ϕ1),
j=2 ℓ(ϕj)} ≤
j=1 ℓ(ϕj).
It follows also that ϕ−11 (Q1A
∗∩P2A∗) = ϕ−11 (SA∗) = ϕ
1 (S) A
∗ (the latter equality is from Lemma
2.6). Since S ⊆ Q1 ∪ P2 implies ϕ−11 (S) ⊆ ϕ
1 (Q1) ∪ ϕ
1 (P2) = P1 ∪ ϕ
1 (P2), we have ℓ(ϕ
1 (S)) ≤
max{ℓ(P1), ℓ(ϕ−11 (P2))}. Obviously, ℓ(P1) ≤ ℓ(ϕ1). Moreover, by Lemma 2.7, ℓ(ϕ
1 (P2)) ≤ ℓ(ϕ1) +
ℓ(P2). Since ℓ(P2) ≤ ℓ(ϕ′2) ≤
j=2 ℓ(ϕj) (the latter “≤” by induction), we have ℓ(ϕ
1 (S)) ≤ ℓ(ϕ1)+
j=2 ℓ(ϕj) =
j=1 ℓ(ϕj).
Since the domain code of Φ1 is ϕ
1 (S) and its image code is S, we conclude that ℓ(Φ1) ≤
j=1 ℓ(ϕj).
Let us now consider any Φ′
[i,2]
, for i = 1, . . . , N . By definition, Φ′
[i,2]
is the restriction of ϕ′i ◦ . . . ◦ϕ′2
to the domain SA∗. So the domain code of Φ′
[i,2]
is S, and we just proved that ℓ(S) ≤
j=1 ℓ(ϕj).
The image code of Φ′
[i,2]
is ϕ′i ◦ . . . ◦ ϕ′2(S). Since S ⊆ Q1 ∪ P2 we have
ϕ′i ◦ . . . ◦ ϕ′2(S) ⊆ ϕ′i ◦ . . . ◦ ϕ′2(Q1) ∪ ϕ′i ◦ . . . ◦ ϕ′2(P2) = ϕ′i ◦ . . . ◦ ϕ′2(Q1) ∪ Q′i.
Therefore: ℓ(ϕ′i ◦ . . . ◦ ϕ′2(S)) ≤ max{ℓ(ϕ′i ◦ . . . ◦ ϕ′2(Q1)), ℓ(Q′i)}.
We have ℓ(Q′i) ≤ ℓ(ϕ′i) ≤
j=2 ℓ(ϕj) (the last “≤” by induction).
By Lemma 2.7, ℓ(ϕ′i ◦ . . . ◦ ϕ′2(Q1)) ≤ ℓ(ϕ′i ◦ . . . ◦ ϕ′2) + ℓ(Q1) ≤ ℓ(ϕ′i ◦ . . . ◦ ϕ′2) + ℓ(ϕ1). And
ℓ(ϕ′i ◦ . . . ◦ ϕ′2) ≤ max{ℓ(ϕ′j) : j = 2, . . . , i}, because Dom(ϕ′r+1) = Im(ϕ′r) for all r = 2, . . . , N − 1.
And by induction, ℓ(ϕ′j) ≤
j=2 ℓ(ϕj). Hence, ℓ(ϕ
i ◦ . . . ◦ ϕ′2(Q1)) ≤
j=1 ℓ(ϕj).
Thus, ℓ(Φ′
[i,2]
j=1 ℓ(ϕj) for every i = 2, . . . , N .
Finally, we factor Φ′
[N,2]
as Φ′
[N,2]
= ΦN ◦ . . . ◦Φ2, where Φi (for i = 2, . . . , N) is defined to be the
restriction of ϕ′i to the domain ϕ
i−1 ◦ . . . ◦ ϕ′2(SA∗) (= Φ′[i−1,2](SA
∗)). Since Dom(ϕ′r+1) = Im(ϕ
(for all r = 2, . . . , N − 1), the domain of ϕ′i is equal to the image of ϕ′i−1 ◦ . . . ◦ ϕ′2. So, the domain
code of Φi is ϕ
i−1 ◦ . . . ◦ϕ′2(S), and its image code is ϕ′i ◦ϕ′i−1 ◦ . . . ◦ϕ′2(S). Since we already proved
that ℓ(ϕ′i ◦ . . . ◦ ϕ′2(S)) ≤
j=1 ℓ(ϕj) (for all i), it follows that ℓ(Φi) ≤
j=1 ℓ(ϕj). ✷
In the next theorem we show that the distortion of lepMk,1 in Mk,1 is at most quadratic (over the
generators considered so far, which include the bit position transpositions). Combined with Proposi-
tion 2.4, this means the following:
Assume circuits are built with gates that are not constrained to have fixed-length inputs and outputs,
but assume the input-output function has fixed-length inputs and outputs. Then the resulting circuits
are not much more compact than conventional circuits, built from gates that have fixed-length inputs
and outputs (we gain at most a square-root in size).
Theorem 2.9 (Distortion of lepMk,1 in Mk,1). The word-length (or Cayley graph) distortion of
lepMk,1 in Mk,1 has a quadratic upper bound; in other words, for all x ∈ lepMk,1:
|x|lepMk,1 ≤ c · (|x|Mk,1)2
where c ≥ 1 is a constant. Here the generating sets used are ΓMk,1 ∪ {τi,j : 1 ≤ i < j} for Mk,1, and
ΓlepMk,1 ∪ {τi,j : 1 ≤ i < j} for lepMk,1, where ΓMk,1 and ΓlepMk,1 are finite. By |x|Mk,1 and |x|lepMk,1
we denote the word-length of x over ΓMk,1 ∪ {τi,j : 1 ≤ i < j}, respectively ΓlepMk,1 ∪ {τi,j : 1 ≤ i < j}.
Proof. We only prove the result for k = 2; a similar proof applies for any k. We abbreviate the set
{τi,j : 1 ≤ i < j} by τ . The choice of the finite sets ΓMk,1 and ΓlepMk,1 does not matter (it only affects
the constant c in the Theorem. By Corollary 3.6 in [9] we can choose ΓMk,1 so that each γ ∈ ΓMk,1
satisfies the following (recall that ℓ(S) denotes the length of the longest words in a set S):
domC(γ) ∪ imC(γ)
≤ 2, and
∣|γ(x)| − |x|
∣ ≤ 1 for all x ∈ Dom(γ).
Let ϕ ∈ lepMk,1, and let w = αN . . . α1 be a shortest word over the generating set ΓMk,1 ∪ τ of
Mk,1, representing ϕ. So N = |ϕ|Mk,1 . We restrict each partial function αi to a partial function α′i such
that imC(α′i) = domC(α
i+1) for i = 1, . . . , N−1, according to Lemma 2.8. Hence, αN ◦ . . .◦α1(.) =
α′N ◦ . . . ◦ α′1(.), and ℓ(α′i) ≤
j=1 ℓ(αj) for every i = 1, . . . , N . Then αN ◦ . . . ◦ α1(.) is a function
{0, 1}m {0, 1}∗ → Q {0, 1}∗, representing ϕ, and we will identify αN ◦ . . . ◦ α1(.) with ϕ. It follows
that domC(α′1) = domC(ϕ) = {0, 1}m, and imC(α′N ) = imC(ϕ) = Q ⊆ {0, 1}n. More generally, it
follows that imC(α′i ◦ . . . ◦ α′1) = imC(α′i), and domC(α′N ◦ . . . ◦ α′i) = domC(α′i).
Since ℓ(α′i) ≤
j=1 ℓ(αj), and ℓ(αj) ≤ 2 for all j, we have for every i = 1, . . . , N : ℓ(α′i) ≤ 2N .
From here on we will simply denote ℓ(α′i) by ℓi. Now, we will replace each α
i ∈ Mk,1 by βi ∈
lepMk,1, such that domC(βi) = {0, 1}ℓi , and imC(βi) ⊆ {0, 1}ℓi+1 ; so βi is length-equality preserving.
This will be done by artificially lengthening those words in domC(α′i) that have length < ℓi and those
words in imC(α′i) that have length < ℓi+1. Moreover, we make βi defined on all of {0, 1}ℓi . In detail,
βi is defined as follows:
• If ℓi ≤ ℓi+1 :
βi(u z) = v z 0
ℓi+1−ℓi−|v|+|u| for all u ∈ domC(α′i), and z ∈ {0, 1}ℓi−|u|; here v = α′i(u);
βi(x) = x 0
ℓi+1−ℓi for all x 6∈ Dom(α′i), |x| = ℓi.
• If ℓi > ℓi+1 :
βi(u z1 z2) = v z1 for all u ∈ domC(α′i) and all z1, z2 ∈ {0, 1}∗ with
|z1| = ℓi+1 − |v|, |z2| = ℓi − ℓi+1 + |v| − |u|; here, v = α′i(u);
βi(x1 x2) = x1 for all x1, x2 ∈ {0, 1}∗ such that x1x2 6∈ Dom(α′i), with
|x1| = ℓi+1, |x2| = ℓi − ℓi+1.
Claim. βN ◦ . . . ◦ β1(.) = ϕ.
Proof of the Claim: We observe first that domC(β1) = domC(α
1) (= domC(ϕ) = {0, 1}m). Next,
assume by induction that for every x ∈ {0, 1}m : α′i−1 ◦ . . . ◦ α′1(x) = u is a prefix of βi−1 ◦ . . . ◦
β1(x) = u z. Then βi(u z) = v z 0
ℓi+1−ℓi−|v|+|u| (if ℓi ≤ ℓi+1); or βi(u z) = v z1 (if ℓi ≥ ℓi+1, with
|z1| = ℓi+1 − |v| and z = z1z2). In either case we find that α′i(α′i−1 ◦ . . . ◦ α′1(x)) = v is a prefix of
βi(βi−1 ◦ . . . ◦ β1(x)) = βi(u z).
Hence, when i = N we obtain for any x ∈ {0, 1}m: βN ◦ . . . ◦ β1(x) = y s is a prefix of
α′N ◦ . . . ◦ α′1(x) = ϕ(x) = y for some y and s with |y s| = ℓN = n. Since y ∈ imC(ϕ) ⊆ {0, 1}n we
conclude that s is empty, hence βN ◦ . . . ◦ β1(x) = α′N ◦ . . . ◦ α′1(x). [End, proof of Claim.]
At this point we have expressed ϕ as a product of N elements βi ∈ lepMk,1, where N = |ϕ|Mk,1 .
We now want to find the word-length of each βi over ΓlepMk,1 ∪ τ , in order to find an upper bound on
the total word-length of ϕ over ΓlepMk,1 ∪ τ . As we saw above, ℓi ≤ 2N for every i = 1, . . . , N .
We examine each generator in ΓMk,1 ∪ τ .
If αi ∈ τ then βi ∈ τ , so in this case |βi|lepMk,1 = 1.
Suppose now that αi ∈ ΓMk,1 . By Proposition 2.4 it is sufficient to construct a circuit that computes
βi; the circuit can then be immediately translated into a word over ΓlepMk,1 ∪ τ with linear increase in
length.
Since domC(αi) ⊆ {0, 1}≤2, we can restrict αi so that its domain code becomes a subset of {0, 1}2;
next, we extend αi to a map α
i that acts as the identity map on {0, 1}2 where αi was undefined. The
image code of α′′i is a subset of {0, 1}≤3. In order to compute βi we first introduce a circuit C(α′′i ) that
computes α′′i . A difficulty here is that α
i does not produce fixed-length outputs in general, whereas
C(α′′i ) has to work with fixed-length inputs and outputs; so the output of C(α
i ) represents the output
of α′′i indirectly, as follows:
The circuit C(α′′i ) has two input bits u = u1u2 ∈ {0, 1}2, and 5 output bits: First there are 3
output bits 03−|v| v ∈ {0, 1}3, where v = α′′i (u); second, there are two more output bits, c1c2 ∈ {0, 1}2,
defined by c1c2 = bin(3− |v|) (the binary representation of the non-negative integer 3− |v|). Hence,
c1c2 = 00 if |v| = 3, c1c2 = 01 if |v| = 2, c1c2 = 10 if |v| = 1; since |v| > 0, the value c1c2 = 11 will
not occur. Thus c1c2 0
3−|v| v contains the same information as v, but has the advantage of having a
fixed length (always 5). The circuit C(α′′i ) can be built with a small constant number of and, or, not,
fork gates, and we will not need to know the details.
We now build a circuit for βi.
• Circuit for βi if ℓi ≤ ℓi+1:
On input u z ∈ {0, 1}ℓi (with u ∈ {0, 1}2), we want to produce the output v z 0ℓi+1−ℓi−|v|+|u|, where
v = α′′i (u).
We first apply the circuit C(α′′i ), thus obtaining c1c2 0
3−|v| v z. Then we apply two fork operations
(always to the last bit in z) to produce c1c2 0
3−|v| v z b b, where b is the last bit of z. Applying a
negation to the first b and an and operation, we obtain c1c2 0
3−|v| v z 0. Applying ℓi+1 − ℓi − 1 more
fork operations to the last 0 yields c1c2 0
3−|v| v z 0ℓi+1−ℓi−1.
Next, we want to move 03−|v| to the right of the output, in order to obtain c1c2 v z 0
3−|v|+ℓi+1−ℓi−1.
For this effect we introduce a controlled cycle. Let κ : x1x2x3 ∈ {0, 1}3 7−→ x3x1x2 be the usual
cyclic permutations of 3 bit positions. The controlled cycle acts as the identity map when c1c2 = 00
or 11, τ1,2 when c1c2 = 01, and κ when c1c2 = 10. More precisely,
κc : c1c2 x1x2x3 ∈ {0, 1}5 7−→
c1c2 x1x2x3 if c1c2 = 00 or 11,
c1c2 x2x1x3 if c1c2 = 01,
c1c2 x3x1x2 if c1c2 = 10.
We apply ℓi copies of κc(c1, c2, ., ., .) (all controlled by the same value of c1c2) to 0
3−|v| v z. The first
κc(c1, c2, ., ., .) is applied to the 3 bits 0
3−|v| v, producing 3 bits y1y2y3; the second κc(c1, c2, ., ., .) is
applied to y2y3 and the first bit of z, producing 3 bits y
3; the third κc(c1, c2, ., ., .) is applied to
3 and the second bit of z, etc. So, each one of the ℓi copies of κc acts one bit further down than
the previous copy of κc. This will yield c1c2 v z 0
3−|v|+ℓi+1−ℓi−1. Finally, to make c1c2 disappear, we
apply two fork operations to c1, then a negation and an and, to make a 0 appear. We combine this 0
with c1 and c2 by and gates, thus transforming 0c1c2 into 0. Finally, an or operation between this 0
and the first bit of v makes this 0 disappear.
The number of gates used to compute βi is O(ℓi+1 + ℓi), which is ≤ O(N).
• Circuit for βi if ℓi > ℓi+1:
On input u z ∈ {0, 1}ℓi (with u ∈ {0, 1}2), we want to produce the output v z1, where v = α′′i (u).
We first apply the circuit C(α′′i ), which yields the output c1c2 0
3−|v| v z. Now we want to erase
the ℓi− ℓi+1+1 last bits of z. For this we apply two fork operations to the last bit of z (let’s call it b),
then a negation and an and, to make a 0 appear. We combine this 0 with the last ℓi − ℓi+1 bits of z,
using that many and gates, turning all these bits into a single 0; finally, an or operation between this 0
and the bit of the remainder of z makes this 0 disappear. At this point, the output is c1c2 0
3−|v| v Z1,
where Z1 is the prefix of length ℓi+1 − 1 of z.
Next, we apply O(ℓi+1) position transpositions to Z1 in order move the two last bits of Z1 to the
front of Z1. Let b1b2 be the last two bits of Z1; so, Z1 = z0b1b2 (where z0 is the prefix of length ℓi+1−3
of z); at this point, the output of the circuit is c1c2 0
3−|v| v b1b2 z0.
We now introduce a fixed small circuit with 7 input bits and 5 output bits, defined by the following
input-output map:
ωc : c1c2 x1x2x3 b1b2 ∈ {0, 1}7 7−→
c1c2 x1x2x3 if c1c2 = 00 or 11,
c1c2 x1x2 b1 if c1c2 = 01,
c1c2 x3 b1b2 if c1c2 = 10.
When this map is applied to c1c2 0
3−|v| v b1b2 the output is therefore given by
ωc : c1c2 0
3−|v| v b1b2 ∈ {0, 1}7 7−→
c1c2 v if |v| = 3,
c1c2 v b1 if |v| = 2,
c1c2 v b1b2 if |v| = 1.
A circuit for ωc can be built with a small fixed number of and, or, not, fork gates, and we will not need
to know the details.
After applying ωc to c1c2 0
3−|v| v b1b2 z0 the output has length ℓi+1 + 2; the “+2” comes from
c1c2. The output is c1c2 v z0, or c1c2 v b1 z0, or c1c2 v b1b2 z0, depending on whether |v| = 3, 2, or 1.
We need to move b1b2 or b1 (or nothing) back to the right-most positions of z0. We do this by
applying ℓi+1 copies of the controlled cycle κc(c1, c2, ., ., .) (all copies controlled by the same value of
c1c2). We proceed in the same way as when we used κc in the previous case, and we obtain the output
c1c2 v z0 (if |v| = 3), or c1c2 v z0 b1 (if |v| = 2), or c1c2 v z0 b1b2 (if |v| = 1).
Finally, we erase c1c2 in the same way as in the previous case, thus obtaining the final output.
The number of gates used to compute βi is O(ℓi+1 + ℓi) ≤ O(N).
This completes the constuction of a circuit for βi. Through this circuit, βi : {0, 1}ℓi → {0, 1}ℓi+1 is
expressed as a word over the generating set ΓlepMk,1 ∪ τ , of length ≤ O(ℓi+1 + ℓi) ≤ O(N).
Since we have described ϕ as a product of N = |ϕ|Mk,1 elements βi ∈ lepMk,1, each of word-length
O(N), we conclude that ϕ has word-length ≤ O(N2) over the generating set ΓlepMk,1 ∪ τ of lepMk,1.
Question: Does the distortion of lepMk,1 inMk,1 (over the generators of Theorem 2.9) have an upper
bound that is less than quadratic?
3 Wordlength asymmetry vs. computational asymmetry
Proposition 3.1 The word-length asymmetry function λ of the Thompson group lpG2,1 within the
Thompson monoid lepM2,1 is linearly equivalent to the computational asymmetry function α:
α ≃lin λ.
Here the generating set used for lepM2,1 is ΓlepM2,1 ∪ {τi,j : 0 ≤ i < j}, where ΓlepM2,1 is finite. The
gates used for circuits are any finite universal set of gates, together with the wire-swapping operations
{τi,j : 0 ≤ i < j}.
We can choose ΓlepM2,1 to consist exactly of the gates used in the circuits; then α = λ.
Proof. For any g ∈ lpG2,1 we have
C(g−1) ≤ c0 · |g−1|lepM2,1 ≤ c0 · λ(|g|lepM2,1) ≤ c0 · λ(c1 · C(g)).
The first and last “≤” come from Prop. 2.4 (since lpG2,1 ⊂ lepM2,1), and the middle “≤” comes from
the definition of λ; c0 and c1 are positive constants. Hence,
α(n) ≤ c0 · λ(c1 n) for all n.
In a very similar way we prove that λ(n) ≤ c′0 · α(c′1 n) for some positive constants c′0, c′1. ✷
Proposition 3.2 The word-length asymmetry function λM2,1 of the Thompson group lpG2,1 within
the Thompson monoid M2,1 is polynomially equivalent to the word-length asymmetry function λlepM2,1
of lpG2,1 within the Thompson monoid lepM2,1. More precisely we have for all n :
λM2,1(n) ≤ c0 · λlepM2,1(c1 n2),
λlepM2,1(n) ≤ c′0 ·
λM2,1(c
where c0, c1, c
1 are positive constants. Here the generating set used for lepM2,1 is ΓlepM2,1 ∪ {τi,j :
0 ≤ i < j}, where ΓlepM2,1 is finite. The generating set used for M2,1 is ΓM2,1 ∪ {τi,j : 0 ≤ i < j},
where ΓM2,1 is a finite generating set of M2,1.
Proof. For any g ∈ lpG2,1 we have
|g−1|M2,1 ≤ c0 · |g−1|lepM2,1 ≤ c0 · λlepM2,1(|g|lepM2,1) ≤ c0 · λlepM2,1(c1 · |g|2M2,1).
The first “≤” holds because lpG2,1 ⊂ lepM2,1 ⊂M2,1 and because of the choice of the generating sets.
The second “≤” holds by the definition of λlepM2,1 . The third “≤” comes from the quadratic distortion
of lepM2,1 in M2,1 (Theorem 2.9). For the same reasons we also have the following:
|g−1|lepM2,1 ≤ c′0 · |g−1|2M2,1 ≤ c
0 · (λM2,1(|g|M2,1))2 ≤ c′0 · (λM2,1(c1 · |g|lepM2,1))2
where c′0, c
1 are positive constants. ✷
4 Reversible representation over the Thompson groups
Theorems 4.1 and 4.2 below introduce a representation of elements of the Thompson monoid lepM2,1 by
elements of the Thompson group G2,1, in analogy with the Toffoli representation (Theorem 1.5 above),
and the Fredkin representation (Theorem 1.6 above). Our representation preserves complexity, up to a
polynomial change, and uses only one constant-0 input. Note that although the functions and circuits
considered here use fixed-length inputs and outputs, the representations is over the Thompson group
G2,1, which includes functions with variable-length inputs and outputs.
In the Theorem below, ΓG2,1 is any finite generating set of G2,1. We denote the length of a word
w by |w|, and we denote the size of a circuit C by |C|. The gates and, or, not will also be denoted
respectively by ∧,∨,¬. We distinguish between a word Wf (over a generating set of G2,1) and the
element wf of G2,1 represented by Wf .
Theorem 4.1 (Representation of boolean functions by the Thompson group). Let f :
{0, 1}m → {0, 1}n be any total function and let Cf be a minimum-size circuit (made of ∧,∨,¬, fork-
gates and wire-swappings τi,j) that computes f . Then there exists a word Wf over the generating set
ΓG2,1 ∪ {τi,i+1 : 1 ≤ i} of G2,1 such that:
• For all x ∈ {0, 1}m: wf (0x) = 0 f(x) x, where wf is the element of G2,1 represented by Wf .
• The length of the word Wf is bounded by |Wf | ≤ O(|Cf |4).
• The largest subscript of any transposition τi,i+1 occurring in Wf has an upper bound ≤ |Cf |2 + 2.
Proof. Wire-swappings in circuits are represented by the position transpositions τi,i+1 ∈ G2,1. The
gates not, or, and and of circuits are represented by the following elements of G2,1:
, ϕ∨ =
0x1x2 1x1x2
(x1 ∨ x2)x1x2 (x1 ∨ x2 )x1x2
, ϕ∧ =
0x1x2 1x1x2
(x1 ∧ x2)x1x2 (x1 ∧ x2 )x1x2
where x1, x2 range over {0, 1}. Hence the domain and image codes of ϕ∨ and ϕ∧ are all equal to
{0, 1}3.
To represent fork we use the following element, in which we recognize σ ∈ F2,1, one of the commonly
used generators of the Thompson group F2,1:
0 10 11
00 01 1
00 01 10 11
000 001 01 1
Note that σ agrees with fork only on input 0, but that is all we will need. By its very essense,
the forking operation cannot be represented by a length-equality preserving element of G2,1, because
G2,1∩ lepM2,1 = lpG2,1 (the group of length-preserving elements of G2,1). A small remark: In [6, 7, 8],
what we call “σ” here, was called “σ−1”.
We will occasionally use the wire-swapping τi,j (1 ≤ i < j); note that τi,j can be expressed in terms
of transpositions of neighboring wires as follows:
τi,j(.) = τi,i+1 τi+1,i+2 . . . τj−2,j−1 τj−1,j τj−2,j−1 . . . τi+1,i+2 τi,i+1(.)
so the word-length of τi,j over {τℓ,ℓ+1 : 1 ≤ ℓ} is ≤ 2(j − i)− 1.
For x = x1 . . . xm ∈ {0, 1}m and f(x) = y = y1 . . . yn ∈ {0, 1}n, we will construct a word Wf over
the generators ΓG2,1 ∪ {τi,i+1 : 1 ≤ i} of G2,1, such that Wf defines the map wf (.) : 0x 7→ 0 f(x) x.
The circuit Cf is partitioned into slices cℓ (ℓ = 1, . . . , L). Two gates g1 and g2 are in the same slice
iff the length of the longest path from g1 to any input port is the same as the length of the longest
path from g2 to any input port. We assume that Cf is strictly layered, i.e., each gate in slice cℓ only
has in-wires coming from slice cℓ−1, and out-wires going toward slice cℓ+1, for all ℓ. To make a circuit
C strictly layered we need to add at most |C|2 identity gates (see p. 52 in [7]). The input-output map
of slice cℓ has the form
cℓ(.) : y
(ℓ−1) = y
(ℓ−1)
1 . . . y
(ℓ−1)
nℓ−1 ∈ {0, 1}nℓ−1 7−→ y(ℓ) = y
1 . . . y
nℓ ∈ {0, 1}nℓ .
Then y(0) = x and y(L) = y, where x ∈ {0, 1}m is the input and y ∈ {0, 1}n is the output of Cf . Each
slice is a circuit of depth 1.
Before studying in more detail how Cf is built from slices, let us see how a slice is built from gates
(inductively, one gate at a time).
Let C be a depth-1 circuit with k + 1 gates, obtained by adding one gate to a depth-1 circuit K
with k gates. Let K(.) : x1 . . . xm 7−→ y1 . . . yn be the input-output map of the circuit K. Assume
by induction that K is represented by a word WK over the generating set ΓG2,1 ∪ {τi,i+1 : 1 ≤ i} of
G2,1. The input-output map of WK is, by induction hypothesis,
wK(.) : 0x1 . . . xm 7−→ 0 y1 . . . yn x1 . . . xm.
The word WC that represents C over G2,1 is obtained as follows from WK ; there are several cases,
depending on the gate that is added to K to obtain C.
Case 1: An identity-gate (or a not-gate) is added to K to form C, i.e.,
C(.) : x1 . . . xmxm+1 7−→ y1 . . . ynxm+1
(or, C(.) : x1 . . . xmxm+1 7−→ y1 . . . ynxm+1).
Then WC is given by
wC : 0x1x2 . . . xmxm+1
σ7−→ 00x1x2 . . . xmxm+1
τ3,m+37−→ 00xm+1 x2 . . . xmx1
ϕ∨7−→
xm+10xm+1 x2 . . . xmx1
τ3,m+37−→ xm+1 0x1x2 . . . xmxm+1
π7−→ 0x1x2 . . . xmxm+1xm+1
wK7−→
0 y1 . . . yn x1 . . . xmxm+1xm+1
π′7−→ 0 y1 . . . yn xm+1 x1 . . . xmxm+1 ,
where π(.) = τm+1,m+2 . . . τ2,3 τ1,2(.) shifts xm+1 from position 1 to position m+ 2, while shifting
0x1 . . . xm one position to the left; and π
′(.) = τm+2,m+3 . . . τn+m+1,n+m+2 τn+m+2,n+m+3(.) shifts
xm+1 from position n+m+ 3 to position n+ 2, while shifting x1 . . . xm one position to the right.
So, WC = π
′ WK π τ3,m+3 ϕ∨ τ3,m+3 σ, noting that functions act on the left. Thus, |WC | =
|WK |+m+n+5 if we use all of {τi,j : 1 ≤ i < j} in the generating set; over {τi,i+1 : 1 ≤ i}, τ3,m+3 has
length ≤ 2m− 1, hence |WC | ≤ 3m + n + 4. If we denote the maximum index in the transpositions
occurring in WC by JC then we have JC = max{JK , n+m+ 3}.
In case a not-gate is added (instead of an identity gate), ϕ∨ is replaced by ϕ¬ ϕ∨ in WC , and the
result is similar.
Case 2: An and-gate (or an or-gate) is added to K to form C, i.e.,
C(.) : x1 . . . xmxm+1xm+2 7−→ y1 . . . yn (xm+1 ∧ xm+2)
(or, C(.) : x1 . . . xmxm+1xm+2 7−→ y1 . . . yn (xm+1 ∨ xm+2)).
Then WC is given by
wC : 0x1x2 . . . xmxm+1xm+2
σ7−→ 00x1x2 . . . xmxm+1xm+2
τ2,m+37−→
τ3,m+47−→
0xm+1xm+2 x2 . . . xm0x1
ϕ∧7−→ (xm+1 ∧ xm+2) xm+1xm+2 x2 . . . xm0x1
τ2,m+37−→
τ3,m+47−→
(xm+1 ∧ xm+2) 0x1x2 . . . xmxm+1xm+2
π7−→ 0x1x2 . . . xm (xm+1 ∧ xm+2) xm+1xm+2
wK7−→
0 y1 . . . yn x1x2 . . . xm (xm+1 ∧ xm+2) xm+1xm+2
π′7−→
0 y1 . . . yn (xm+1 ∧ xm+2) x1x2 . . . xmxm+1xm+2 ,
where π = τm+1,m+2 . . . τ2,3 τ1,2 shifts (xm+1∧xm+2) from position 1 to positionm+2, while shifting
0x1x2 . . . xm one position to the left; and π
′ = τm+2,m+3 . . . τm+n+1,m+n+2 shifts (xm+1 ∧ xm+2)
from position n+m+ 2 to position m+ 2, while shifting x1 . . . xm one position to the right.
So, WC = π
′ WK π τ3,m+4 τ2,m+3 ϕ∧ τ3,m+4 τ2,m+3 σ, hence |WC | = |WK | + n +m + 7 if all
of {τi,j : 1 ≤ i < j} is used in the generating set; over {τi,i+1 : 1 ≤ i}, τ3,m+4 and τ2,m+3 have length
≤ 2(m+ 1)− 1, so |WC | ≤ |WK |+ 5m+ n+ 9. Moreover, JC = max{JK , m+ n+ 2}.
Case 3: A fork-gate is added to K to form C, i.e.,
C(.) : x1 . . . xmxm+1 7−→ y1 . . . yn xm+1xm+1.
Then WC is given by
wC : 0x1x2 . . . xmxm+1
σ27−→ 000x1x2 . . . xmxm+1
τ3,m+47−→ 00xm+1x1x2 . . . xm0
ϕ∨7−→
xm+10xm+1x1x2 . . . xm0
τ1,m+47−→ 00xm+1x1x2 . . . xmxm+1
ϕ∨7−→ xm+10xm+1x1x2 . . . xmxm+1
0x1x2 . . . xmxm+1xm+1xm+1
wK7−→ 0 y1 . . . yn x1x2 . . . xm xm+1xm+1xm+1
π′7−→
0 y1 . . . yn xm+1xm+1 x1x2 . . . xmxm+1 ,
where π = τm+3,m+4 . . . τ1,2 τm+3,m+4 . . . τ3,4 shifts the two copies of xm+1 at the left end from
positions 1 and 3 to positions m+ 3 and m+ 4, while shifting 0 to position 1 and shifting x1 . . . xm
two positions to the left; and π′ = τm+3,m+4 . . . τm+n+2,m+n+3 τm+2,m+3 . . . τm+n+1,m+n+2 shifts
xm+1xm+1 from positions m + n + 2 and m + n + 3 to positions m + 2 and m + 3, while shifting
x1 . . . xm two positions to the right.
So, WC = π
′ WK π ϕ∨ τ1,m+4 ϕ∨ τ3,m+4 σ
2, hence |WC | = |WK | + 2m + n + 10, if all of
{τi,j : 1 ≤ i < j} is used in the generating set; over {τi,i+1 : 1 ≤ i}, τ1,m+4 has length ≤ 2(m+3)−1 and
τ3,m+4 has length ≤ 2m−1. Hence, |WC | ≤ |WK |+6m+n+14. Moreover, JC = max{JK , m+n+3}.
In all cases, |WC | ≤ |WK |+c·(m+n+1) (for some constant c > 1), and JC ≤ max{JK , n+m+3}.
Thus, each slice cℓ, with input-output map cℓ(.) : y
(ℓ−1) 7−→ y(ℓ), is represented by a word Wcℓ with
map wcℓ(.) : 0 y
(ℓ−1) 7−→ 0 y(ℓ) y(ℓ−1), such that |Wcℓ| ≤ c · (n2ℓ−1 + n2ℓ) (for some constant c > 1),
and Jcℓ ≤ nℓ−1 + nℓ + c.
Regarding wire-crossings, we do not include them into other slices; we put the wire-crossings into
pure wire-crossing slices. So we consider two kinds of slices: Slices entirely made of wire-crossings
and identities, slices without any wire-crossings. Wire-crossings in circuits are identical to the group
elements τi,i+1.
We now construct the word Wf from the words Wcℓ (ℓ = 1, . . . , L). First observe that since the
map wcℓ(.) is a right-ideal isomorphism (being an element of G2,1), we not only have
wcℓ(.) : 0 y
(ℓ−1) 7−→ 0 y(ℓ)y(ℓ−1)
but also
wcℓ(.) : 0 y
(ℓ−1)y(ℓ−2) . . . y(1)y(0) 7−→ 0 y(ℓ)y(ℓ−1)y(ℓ−2) . . . y(1)y(0).
Then, by concatenating all Wcℓ (and by recalling that y = y
(L) and x = y(0)) we obtain
wcL wcL−1 . . . wc2 wc1(.) : 0x 7−→ 0 y y(L−1) . . . y(2) y(1) x.
Let πCf be the position permutation that shifts y right to the positions just right of x:
πCf : 0 y y
(L−1) . . . y(2) y(1) x 7−→ 0 y(L−1) . . . y(2) y(1) x y.
Observe that for (WcL−1 . . . Wc2 Wc1)
−1 we have
(wcL−1 . . . wc2 wc1)
−1(.) : 0 y(L−1) . . . y(2) y(1) x y 7−→ 0x y.
Then we have:
wcL wcL−1 . . . wc2 wc1 πCf (wcL−1 . . . wc2 wc1)
−1(.) : 0x 7−→ 0x y .
By using the position permutation πm,n : 0x y 7−→ 0 y x, we now see how to define Wf :
Wf = πm,n WcL WcL−1 . . . Wc2 Wc1 πCf (WcL−1 . . . Wc2 Wc1)
Then we have:
wf (.) : 0x 7−→ 0 y x,
where y = f(x).
Finally, we need to examine the length of the word Wf in terms of the size of the circuit Cf that
computes f : {0, 1}m → {0, 1}n.
The position permutation πm,n shifts the n = |y| letters of y to the left over the m = |x| positions
of x. So, πm,n can be written as the product of nm transpositions in {τi,i+1 : 1 ≤ i}, with maximum
subscript Jπm,n ≤ m+ n+ 1.
The position permutation πCf shifts y to the right from positions in the interval [2, n + 1] within
the string 0 y y(L−1) . . . y(2) y(1) x to positions in the interval [2 +
i=0 ni, 2 +
i=0 ni] within
the string 0 y(L−1) . . . y(2) y(1) x y. Note that
i=0 ni = |Cf | (the size of the circuit Cf ), and
nL = |y| = n, n0 = |x| = m. We shift y starting with the right-most letters of y. This takes
i=0 ni = n (|Cf |−n) transpositions in {τi,i+1 : 1 ≤ i}, with maximum subscript JπCf = |Cf |+2.
We saw already that |Wcℓ | ≤ c (n2ℓ−1 + n2ℓ), and Jcℓ ≤ nℓ−1 + nℓ + c, for some constant c > 1.
Note that
i=0 n
i ≤ (
i=0 ni)
2 = |Cf |2. Hence we have: |Wf | ≤ co |Cf |2, for some constant
co > 1. Moreover, the largest subscript in any transposition occurring in Wf is JWf ≤ |Cf |+ 2.
Recall that we assumed that our circuit Cf was strictly layered, and that the circuit size has to be
squared (at most) in order to make the circuit strictly layered. Thus, if Cf was originally not strictly
layered, our bounds become |Wf | ≤ co |Cf |4, and JWf ≤ |Cf |2 + 2. ✷
The next theorem gives a representation of a boolean permutation by an element of the Thompson
group G2,1; the main point of the theorem is the polynomial bound on the word-length in terms of
circuit size.
Theorem 4.2 (Representation of permutations by the Thompson group). Let g : {0, 1}m →
{0, 1}m be any permutation and let Cg and Cg−1 be minimum-size circuits that compute g, respectively
g−1. Then there exists a word W(g,g−1) over the generating set ΓG2,1 ∪ {τi,i+1 : 1 ≤ i} of G2,1,
representing an element w(g,g−1) ∈ G2,1 such that:
• For all x ∈ Dom(g) and all y ∈ Im(g):
w(g,g−1)(0x) = 0 g(x), and (w(g,g−1))
−1(0 y) = 0 g−1(y),
where (w(g,g−1))
−1 ∈ G2,1 is represented by the free-group inverse (W(g,g−1))−1 of the word W(g,g−1).
• w(g,g−1)(.) and (w(g,g−1))−1 stabilize both 0 {0, 1}∗ and 1 {0, 1}∗.
• We have a length upper bound |W(g,g−1)| = |(W(g,g−1))−1| ≤ O(|Cg|4 + |Cg−1 |4).
• The largest subscript of transpositions τi,i+1 occurring in W(g,g−1) is ≤ max{|Cg|2, |Cg−1 |2} +2.
Note that we distinguish between the word W(g,g−1) (over a generating set of G2,1) and the element
w(g,g−1) of G2,1 represented by W(g,g−1). Also, note that although g is length-preserving (g ∈ lpG2,1),
w(g,g−1) ∈ G2,1 is not length-preserving.
Proof. Consider the position permutation π : 0 y x 7−→ 0x y, for all x, y ∈ {0, 1}m; we express π
as a composition of ≤ m2 position transpositions of the form τi,i+1. Let Wg be the word constructed
in Theorem 4.1 for g, and let Wg−1 be the word constructed for g
−1. We define W(g,g−1) by
W(g,g−1) = (Wg−1)
−1 π Wg.
Then for all x ∈ Dom(g) we have: w(g,g−1) : 0x 7−→ 0 y, where y = g(x). More precisely, for all
x ∈ domC(g),
wg−−→ 0 g(x) x = 0 y x π−→ 0 x y = 0 g−1(y)
−−−−−−→ 0 y = 0 g(x).
Since domC(g) is a maximal prefix code, w(g,g−1) maps 0 {0, 1}∗ into 0 {0, 1}∗ (where defined).
Similarly, for all y ∈ Im(g) = Dom(g−1) we have: (w(g,g−1))−1 : 0 y 7−→ 0x, where x = g−1(y),
y = g(x). Since domC(g−1) is a maximal prefix code, (w(g,g−1))
−1 maps 0 {0, 1}∗ into 0 {0, 1}∗ (where
defined). Hence, elements of 0 {0, 1}∗ are never images of 1 {0, 1}∗. Thus, 1 {0, 1}∗ is also stabilized
by w(g,g−1) and by (w(g,g−1))
The length of the wordW(g,g−1) is bounded as follows: We have |Wg| ≤ co |Cg|4, and |(Wg−1)−1| =
|Wg−1 | ≤ co |Cg−1 |4, by Theorem 4.1. Moreover, π can be expressed as the composition of ≤ m2
(< |Cg|2) transpositions in {τi,i+1 : 1 ≤ i}.
The bound on the subscripts also follows from Theorem 4.1. ✷
5 Distortion vs. computational asymmetry
We show in this Section that the computational asymmetry function α(.) is polynomially related to a
certain distortion of the group lpG2,1.
By Theorem 4.2, for every element g ∈ lpG2,1 there is an element w(g,g−1) ∈ G2,1 which agrees with
g on 0 {0, 1}∗, and which stabilizes 0 {0, 1}∗ and 1 {0, 1}∗ . The main property of W(g,g−1) is that its
length is polynomially bounded by the circuit sizes of g and g−1; that fact will be crucial later. First
we want to study how w(g,g−1) is related to g. Recall that we distinguish between the word W(g,g−1)
(over a generating set of G2,1) and the element w(g,g−1) of G2,1 represented by W(g,g−1).
Theorem 4.2 inspires the following concepts.
Definition 5.1 Let G be a subgroup of G2,1. For any prefix codes P1, . . . , Pk ⊂ {0, 1}∗, the joint
stabilizer (in G) of the right ideals P1{0, 1}∗, . . . , Pk{0, 1}∗ is defined by
StabG(P1, . . . , Pk) =
g ∈ G : g(Pi{0, 1}∗) ⊆ Pi{0, 1}∗ for every i = 1, . . . , k
The fixator (in G) of P1{0, 1}∗ is defined by
FixG(P1) =
g ∈ G : g(x) = x for all x ∈ P1{0, 1}∗)
The fixator is also called “point-wise stabilizer”.
The following is an easy consequence of the definition: FixG(Pi) is a subgroup of G (⊆ G2,1), for
i = 1, . . . , k. If the prefix codes P1, . . . , Pk are such that the right ideals P1{0, 1}∗, . . . , Pk{0, 1}∗ are
two-by-two disjoint, and such that P1 ∪ . . . ∪ Pk is a maximal prefix code, then StabG(P1, . . . , Pk) is
closed under inverse. Hence in this case StabG(P1, . . . , Pk) is a subgroup of G.
In particular, we will consider the following groups:
• The joint stabilizer of 0 {0, 1}∗ and 1 {0, 1}∗,
StabG(0, 1) =
g ∈ G : g(0 {0, 1}∗) ⊆ 0 {0, 1}∗ and g(1 {0, 1}∗) ⊆ 1 {0, 1}∗
• The fixator of 0 {0, 1}∗,
FixG(0) = {g ∈ G : g(x) = x for all x ∈ 0 {0, 1}∗}.
• The fixator of 1 {0, 1}∗,
FixG(1) = {g ∈ G : g(x) = x for all x ∈ 1 {0, 1}∗}.
Clearly, FixG(0) and FixG(1) are subgroups of StabG(0, 1).
Lemma 5.2 (Self-embeddings of G2,1). Let G be a subgroup of G2,1. Then G is isomorphic to
FixG(1) and to FixG(0) by the following isomorphisms:
Λ0 : g ∈ G 7−→ (g)0 ∈ FixG(1)
Λ1 : g ∈ G 7−→ (g)1 ∈ FixG(0)
where (g)0 and (g)1 defined as follows for any g ∈ G2,1:
(g)0 :
0x ∈ 0 {0, 1}∗ 7−→ 0 g(x)
1x ∈ 1 {0, 1}∗ 7−→ 1x (g)1 :
1x ∈ 1 {0, 1}∗ 7−→ 1 g(x)
0x ∈ 0 {0, 1}∗ 7−→ 0x
Proof. It is straightforward to verify that Λ0 and Λ1 are injective homomorphisms. That Λ0 is onto
FixG(1) can be seen from the fact that every element of FixG(1) has a table of the form
0x1 . . . 0xn 1
0y1 . . . 0yn 1
where {x1, . . . , xn} and {y1, . . . , yn} are two maximal prefix codes, and
x1 . . . xn
y1 . . . yn
is an arbitrary
element of G. ✷
Lemma 5.3 Let G be a subgroup of G2,1. Then the direct product G×G is isomorphic to StabG(0, 1)
by the isomorphism
Λ : (f, g) ∈ G×G 7−→
0x 7→ 0 f(x), 1x 7→ 1 g(x)
∈ StabG(0, 1).
Proof. It is straightforward to verify that Λ is a homomorphism. That Λ is onto StabG(0, 1) and
injective follows from the fact that every element of StabG(0, 1) has a table of the form
0x1 . . . 0xm 1x
1 . . . 1x
0y1 . . . 0ym 1y
1 . . . 1y
where {x1, . . . , xm}, {y1, . . . , ym}, {x′1, . . . , x′n}, and {y′1, . . . , y′n}, are maximal prefix codes, and
x1 . . . xm
y1 . . . ym
x′1 . . . x
y′1 . . . y
are arbitrary elements of G (⊆ G2,1). ✷
Lemmas 5.2 and 5.3 reveal certain self-similarity properties of the Thompson group G2,1. (Self-
similarity of groups with total action on an infinite tree is an important subject, see [27]. However,
the action of G2,1 is partial, so much of the known theory does not apply directly.)
The stabilizer and the fixators above have some interesting properties.
Lemma 5.4 .
(1) For all f, g ∈ G: (f)0 (g)1 = (g)1 (f)0
(i.e., the commutator of FixG(0) and FixG(1) is the identity).
(2) FixG(0) · FixG(1) = StabG(0, 1) and FixG(0) ∩ FixG(1) = 1;
(3) StabG(0, 1) is the internal direct product of FixG(0) and FixG(1).
(This is equivalent to the combination of (1) and (2).)
(4) For all f, g ∈ G: Λ(f, g) = Λ0(f) · Λ1(g), Λ0(f) = Λ(f,1), and Λ1(g) = Λ(1, g).
Moreover, FixG(0) = Λ1(G), FixG(1) = Λ0(G), and StabG(0, 1) = Λ(G×G).
Proof. The proof is a straightforward verification. ✷
Lemma 5.5 For every position transposition τi,j, with 1 ≤ i < j, we have
(τi,j)0 = τ2,i+1 ◦ τ3,j+1◦ (τ1,2)0 ◦ τ3,j+1 ◦ τ2,i+1.
Hence, assuming (τ1,2)0 ∈ ΓG2,1 , and abbreviating {τi,j : 0 < i < j} by τ , we have:
|(τi,j)0|ΓG2,1∪τ ≤ 5.
Proof. Recall that for (τ1,2)0 we have, by definition, (τ1,2)0(1w) = 1w, and (τ1,2)0(0x2x3w) =
0x3x2w, for all w ∈ {0, 1}∗ and x2, x3 ∈ {0, 1}. The proof of the Lemma is a straightforward
verification. ✷
Now we arrive at the relation between w(g,g−1) and g.
Lemma 5.6 For all g ∈ lpG2,1 the following relation holds between g and w(g,g−1) :
w(g,g−1) · (g)−10 , (g)
0 · w(g,g−1) ∈ FixlpG2,1(0).
Equivalently,
(g)0 · FixlpG2,1(0) = w(g,g−1) · FixlpG2,1(0), and
FixlpG2,1(0) · (g)0 = FixlpG2,1(0) · w(g,g−1) .
Proof. By Theorem 4.2 we have w(g,g−1)(0x) = 0 g(x) for all x ∈ Dom(g). So, w(g,g−1) and (g)0
act in the same way on 0 {0, 1}∗ . Also, both w(g,g−1) and (g)0 map 0 {0, 1}∗ into 0 {0, 1}∗, and both
map 1 {0, 1}∗ into 1 {0, 1}∗. The Lemma follows from this. ✷
We abbreviate {τi,j : 0 < i < j} by τ . The element w(g,g−1) of G2,1, represented by the word
W(g,g−1), belongs to StablpG2,1(0, 1) as we saw in Theorem 4.2. However, the word W(g,g−1) itself is a
sequence over the generating set ΓG2,1 ∪ τ of G2,1. Therefore, in order to follow the action of W(g,g−1)
and of its prefixes we need to take Fix(0) as a subgroup of G2,1. This leads us to the Schreier left
coset graph of FixG2,1(0) within G2,1, over the generating set ΓG2,1 ∪ τ . By definition this Schreier
graph has vertex set G2,1/FixG2,1(0), i.e., the left cosets, of the form g · FixG2,1(0) with g ∈ G2,1. And
it has directed edges of the form g ·FixG2,1(0)
γ−→ γg ·FixG2,1(0) for g ∈ G2,1, γ ∈ ΓG2,1 ∪ τ . Lemma
5.6 implies that for all g ∈ lpG2,1,
(g)0 · FixG2,1(0) = w(g,g−1) · FixG2,1(0).
We assume that ΓG2,1 = Γ
, so the Schreier graph is symmetric, and hence it has a distance function
based on path length; we denote this distance by
dG/F (., .) : G2,1/FixG2,1(0)×G2,1/FixG2,1(0) −→ N.
Lemma 5.7 There are injective morphisms
g ∈ lpG2,1 →֒ g ∈ G2,1
≃−→ (g)0 ∈ FixG2,1(1)
≃−→ (g)0 · FixG2,1(0) ∈ StabG2,1(0, 1)/FixG2,1(0),
and an inclusion map
(g)0 · FixG2,1(0) ∈ StabG2,1(0, 1)/FixG2,1(0) →֒ (g)0 · FixG2,1(0) ∈ G2,1/FixG2,1(0).
In particular,
g ∈ G2,1 7−→ (g)0 · FixG2,1(0) ∈ G2,1/FixG2,1(0)
is an embedding of G2,1, as a set, into the vertex set G2,1/FixG2,1(0) of the Schreier graph.
Proof. Recall that the map Λ0 : g ∈ G2,1 7−→ (g)0 ∈ FixG2,1(1) is a bijective morphism (Lemma
5.2). Also, the map u ∈ FixG2,1(1) 7−→ u · FixG2,1(0) ∈ G2,1/FixG2,1(0) is injective; indeed, if
u · FixG2,1(0) = v · FixG2,1(0) with u, v ∈ FixG2,1(1) then v−1u ∈ FixG2,1(0) ∩ FixG2,1(1) = {1}.
The map g ∈ G2,1 7−→ (g)0 · FixG2,1(0) ∈ StabG2,1(0, 1)/FixG2,1(0) is a surjective group
homomorphism since FixG2,1(0) is a normal subgroup of StabG2,1(0, 1). Since FixG2,1(0)∩FixG(1) = {1},
this homomorphism is injective from FixG2,1(1) onto StabG2,1(0, 1)/FixG2,1(0).
The combination of these maps provides an isomorphism from G2,1 onto StabG2,1(0, 1)/FixG2,1(0).
Hence we also have an embedding of G2,1, as a set, into the vertex set G2,1/FixG2,1(0) of the Schreier
graph. ✷
Since by Lemma 5.7 we can consider G2,1 as a subset of the vertex set G2,1/FixG2,1(0) of the
Schreier graph, the path-distance dG/F (., .) on G2,1/FixG2,1(0) leads to a distance on G2,1, inherited
from dG/F (., .) :
Definition 5.8 For all g, g′ ∈ G2,1 the Schreier graph distance inherited by G2,1 is
D(g, g′) = dG/F
(g)0 · FixG2,1(0), (g′)0 · FixG2,1(0)
The comparison of the Schreier graph distance D(., .) on lpG2,1 with the word-length that lpG2,1
inherits from its embedding into lepM2,1 leads to the following distortion of lpG2,1:
Definition 5.9 In lpG2,1 we consider the distortion
∆(n) = max{D(1, g) : |g|lepM2,1 ≤ n, g ∈ lpG2,1}.
We now state and prove the main theorem relating ∆(.) and α. Recall that α(.) is the computational
asymmetry function of boolean permutations, defined in terms of circuit size.
Theorem 5.10 (Computational asymmetry vs. distortion). The computational asymmetry
function α(.) and the distortion ∆(.) of lpG2,1 are polynomially related. More precisely, for all n ∈ N :
)1/2 ≤ c′ ·∆(n) ≤ c n4 + c ·
α(c n)
where c ≥ c′ ≥ 1 are constants.
Proof. The Theorem follows immediately from Lemmas 5.11 and 5.12. ✷
Lemma 5.11. There is a constant c ≥ 1 such that for all n ∈ N : ∆(n) ≤ c n4 + c ·
α(c n)
Proof. By Lemma 5.6, (g)0 · FixG2,1(0) = w(g,g−1) · FixG2,1(0), hence
FixG2,1(0), (g)0 · FixG2,1(0)
FixG2,1(0), w(g,g−1) · FixG2,1(0)
Since the wordW(g,g−1) and the Schreier graph use the same generating set, namely ΓG2,1 ∪ τ , we have
FixG2,1(0), w(g,g−1) · FixG2,1(0)
≤ |W(g,g−1)|.
By Theorem 4.2, |W(g,g−1)| ≤ O(|Cg|4 + |Cg−1 |4). And by the definition of the computational
asymmetry function, |Cg−1 | ≤ α(|Cg |). Hence
FixG2,1(0), (g)0 · FixG2,1(0)
≤ O(|Cg|4 + |Cg−1 |4) ≤ O
|Cg|4 + α(|Cg|)4
By Proposition 2.4, |Cg| = O(|g|lepM2,1). Hence, for some constants c′′, c′ ≥ 1,
FixG2,1(0), (g)0 · FixG2,1(0)
≤ c′ · |g|4
lepM2,1
+ c′ · α(c′′ · |g|lepM2,1)4.
Thus,
FixG2,1(0), (g)0 · FixG2,1(0)
: |g|lepM2,1 ≤ n, g ∈ lpG2,1
≤ c′ n4 + c′ α(c′′ n)4.
By Definition 5.9 of the distortion function ∆ we have therefore
∆(n) ≤ c′ n4 + c′ α(c′′ n)4.
This proves the Lemma. ✷
Lemma 5.12 There is a constant c ≥ 1 such that for all n ∈ N : α(n) ≤ c ·∆(c n)2.
Proof. We first prove the following.
Claim: For every g ∈ lpG2,1, the inverse permutation g−1 can be computed by a circuit Cg−1 of size
|Cg−1 | ≤ c · d
FixG2,1(0), (g)0 · FixG2,1(0)
, for some constant c ≥ 1.
Proof of the Claim: There is a wordW ′ of length |W ′| = d
FixG2,1(0), (g)0 ·FixG2,1(0)
over ΓG2,1∪ τ
that labels a shortest path from FixG2,1(0) to (g)0·FixG2,1(0) in the Schreier graph ofG2,1/FixG2,1(0). Let
W = (W ′)−1 (the free-group inverse of W ′), so |W | = |W ′|. Let w be the element of G2,1 represented
by W . Then W labels a shortest path from FixG2,1(0) to (g
−1)0 · FixG2,1(0) in the Schreier graph of
G2,1/FixG2,1(0); this path has length |W | = |W ′| = d
FixG2,1(0), (g)0 · FixG2,1(0)
FixG2,1(0),
(g−1)0 · FixG2,1(0)
We have w · FixG2,1(0) = (g−1)0 · FixG2,1(0), thus for all x ∈ {0, 1}∗ : w(0x) = 0 g−1(x). We now
take the word VWU over the generating set ΓM2,1 ∪ τ of the monoid M2,1, where we choose the words
U and V to be U = (and, not, fork, fork), and V = (or). The functions and, not, fork, or were defined
in Subsection 1.1. Then for all x = x1 . . . xn ∈ {0, 1}∗, with x1, . . . , xn ∈ {0, 1}, we have
x1 . . . xn
fork−→ x1 x1 . . . xn
fork−→ not−→ x1 x1 x1 . . . xn
and−→ 0x1 . . . xn = 0x
W−→ 0 g−1(x) or−→ g−1(x).
The last or combines 0 and the first bit of g−1(x), and this makes 0 disappear. Thus overall,
VWU(x) = g−1(x). The length is |V WU | = |W |+ 5.
Since g−1 ∈ lpG2,1 ⊂ lepM2,1, Theorem 2.9 implies that there exists a word Z over the generators
ΓlepM2,1 ∪ τ of lepM2,1 such that
(1) |Z| ≤ c1 · |VWU |2, for some constant c1 ≥ 1, and
(2) Z represents the same element of lepM2,1 as VWU , namely g
Moreover, by Prop. 2.4, the word Z can be transformed into a circuit of size ≤ c2 · |Z| (for some
constant c2 ≥ 1). This proves that there is a circuit Cg−1 for g−1 of size |Cg−1 | ≤ c · |W |2 (for
some constant c ≥ 1). Since we saw that |W | = dG/F (FixG2,1(0), (g)0 · FixG2,1(0)), the Claim follows.
[End, Proof of the Claim.]
By definition, D(1, g) = dG/F (FixG2,1(0), (g)0 · FixG2,1(0)). Hence, by the Claim above:
|Cg−1 | ≤ c ·
D(1, g)
By Prop. 2.4 the word-length in lepM2,1 and the circuit size are linearly related; hence |g|lepM2,1 ≤
c0 |Cg|, for some constant c0 ≥ 1. Therefore,
α(n) = max{|Cg−1 | : |Cg| ≤ n, g ∈ lpG2,1}
≤ max{|Cg−1 | : |g|lepM2,1 ≤ c0 n, g ∈ lpG2,1}
≤ max
D(1, g)
: |g|lepM2,1 ≤ c0 n, g ∈ lpG2,1
≤ c ·
∆(c0 n)
This proves the Lemma. ✷
6 Other bounds and distortions
6.1 Other distortions in the Thompson groups and monoids
The next proposition gives more upper bounds on the computational asymmetry function α.
Proposition 6.1. Assume ΓlepG2,1 ⊂ ΓlepM2,1 ⊂ ΓM2,1 . Let δlpG,lepM = δ
|.|ΓlpG2,1∪τ , |.|ΓlepM2,1∪τ
be the distortion function of lpG2,1 in the Thompson monoid lepM2,1, based on word-length. Similarly,
let δlpG,M = δ
|.|ΓlpG2,1∪τ , |.|ΓM2,1∪τ
be the distortion function of lpG2,1 in the Thompson monoid
M2,1. Then for some constant c ≥ 1 and for all n ∈ N,
α(n) ≤ c · δlpG,lepM (c n) ≤ c · δlpG,M (c n).
Proof. We first prove that δlpG,lepM (n) ≤ δlpG,M (n). Recall that by definition, δlpG,lepM (n) =
max{|g|lpG2,1 : g ∈ lpG2,1, |g|lepM2,1 ≤ n}, and similarly for δlpG,M(n). Since ΓlepM2,1 ⊂ ΓM2,1 we
have |x|lepM2,1 ≤ |x|M2,1 . Hence, {|g|lpG2,1 : g ∈ lpG2,1, |g|lepM2,1 ≤ n} ⊆ {|g|lpG2,1 : g ∈ lpG2,1,
|g|M2,1 ≤ n}. By taking max over each of these two sets it follows that δlpG,lepM (n) ≤ δlpG,M(n).
Next we prove that α(n) ≤ c·δlpG,lepM (c n). For any g ∈ lpG2,1 we have C(g−1) ≤ O(|g−1|lepM2,1),
by Prop. 3.2. Moreover, |g−1|lepM2,1 ≤ |g−1|lpG2,1 since lpG2,1 is a subgroup of lepM2,1, and since the
generating set used for lpG2,1 (including all τi,j) is a subset of the generating set used for lepM2,1. For
any group with generating set closed under inverse we have |g−1|G = |g|G. And by the definition of
the distortion δlpG,lepM we have |g|lpG2,1 ≤ δlpG,lepM (|g|lepM2,1). And again, by Prop. 3.2, |g|lepM2,1 ≤
O(C(g)). Putting all this together we have
C(g−1) ≤ c1 · |g−1|lepM2,1 ≤ c1 · |g−1|lpG2,1 = c1 · |g|lpG2,1
≤ c1 · δlpG,lepM (|g|lepM2,1) ≤ c1 · δlpG,lepM (c2 C(g)).
Thus, c1 ·δlpG,lepM (c2 C(g)) is an upper bound on C(g−1). Since, by definition, α(C(g)) is the smallest
upper bound on C(g−1), it follows that α(C(g)) ≤ c1 · δlpG,lepM (c2 C(g)). ✷
Recall that in the definition 5.9 of the distortion ∆ we compared D(., .) with the word-length in
lepM2,1. If, instead, we compare D(., .) with the word-length inM2,1 we obtain the following distortion
of lpG2,1 :
δ(n) = max{D(1, g) : |g|M2,1 ≤ n, g ∈ lpG2,1}.
Proposition 6.2 The distortion functions ∆(.) and δ(.) are polynomially related. More precisely,
there are constants c′, c1, c2 ≥ 1 such that for all n ∈ N: ∆(n) ≤ c1 δ(n) ≤ c2 ∆(c′ n2).
Proof. Let’s assume first that ΓlepM2,1 ⊆ ΓM2,1 , from which it follows that |g|M2,1 ≤ |g|M2,1 . Therefore,
{D(1, g) : |g|lepM2,1 ≤ n} ⊆ {D(1, g) : |g|M2,1 ≤ n}. Hence, ∆(n) ≤ δ(n).
By Theorem 2.9, |g|lepM2,1 ≤ c · |g|2M2,1 . So, {D(1, g) : |g|M2,1 ≤ n} ⊆ {D(1, g) : |g|lepM2,1 ≤ c n
Hence, δ(n) ≤ ∆(c n2).
When we do not have ΓlepM2,1 ⊆ ΓM2,1 , the constants in the theorem change, but the statement
remains the same. ✷
6.2 Monotone boolean functions and distortion
On {0, 1}∗ we can define the product order, also called “bit-wise order”. It is a partial order (and in
fact, a lattice order), denoted by “�”, and defined as follows. First, 0 ≺ 1; next, for any u, v ∈ {0, 1}∗
we have u � v iff |u| = |v| and ui � vi for all i = 1, . . . , |u|, where ui (or vi) denotes the ith bit of u
(respectively v).
By definition, a partial function f : {0, 1}∗ → {0, 1}∗ is monotone (also called “product-order
preserving”) iff for all u, v ∈ Dom(f) : u � v implies f(u) � f(v).
The following fact is well known (see e.g., [43] Section 4.5): A function f : {0, 1}m → {0, 1}n is
monotone iff f can be computed by a combinational circuit that only uses gates of type and, or, fork,
and wire-swappings; i.e., not is absent. A circuit of this restricted type is called a monotone circuit.
Razborov [30] proved super-polynomial lower bounds for the size of monotone circuits that solve the
clique problem, and in [31] he proved super-polynomial lower bounds for the size of monotone circuits
that solve the perfect matching problem for bipartite graphs; the latter problem is in P. Tardos [37],
based on work by Alon and Boppana [1], gave an exponential lower bound for the size of monotone
circuits that solve a problem in P; see also [42] (Chapter 14 by Boppana and Sipser). Thus, there exist
problems that can be solved by polynomial-size circuits but for which monotone circuits must have
exponential size. In particular (for some constants b > 1, c > 0), there are infinitely many monotone
functions fn : {0, 1}n → {0, 1}n such that fn has a combinational circuit of size ≤ nc, but fn has no
monotone circuit of size ≤ bn.
Based on an alphabet A = {a1, . . . , ak} with a1 ≺ a2 ≺ . . . ≺ ak we define a partial function
f : A∗ → A∗ to be monotone iff f preserves the product order of A∗. The monotone functions enable
us to define the following submonoid of the Thompson-Higman monoid lepMk,1 :
monMk,1 = {ϕ ∈ lepMk,1 : ϕ can be represented by a monotone function P → Q,
where P and Q are prefix codes, with P maximal }.
An essential extension or restriction of an element of monMk,1 is again in monMk,1, so this set is
well-defined as a subset of lepMk,1. It is easily seen to be closed under composition, so monMk,1 is a
submonoid of lepMk,1.
We saw that all monotone finite functions have circuits made from gates of type and, or, fork.
Hence monM2,1 has the following generating set:
{and, or, fork} ∪ {τi,j : j > i ≥ 1}.
The results about monotone circuit size imply the following distortion result. Again, “exponential”
refers to a function with a lower bound of the form n ∈ N 7−→ exp( c
c′ n), for some constants c′ > 0
and c ≥ 1.
Proposition 6.3 Consider the monoid monM2,1 over the generating set {and, or, fork} ∪ {τi,j : j >
i ≥ 1}, and the monoid lepM2,1 over the generating set ΓlepM2,1 ∪ {τi,j : j > i ≥ 1}, where ΓlepM2,1 is
finite. Then monM2,1 has exponential word-length distortion in lepM2,1.
Proof. Let Γmon = {and, or, fork}. By Prop. 2.4 we have |f |ΓlepM2,1∪τ = |Cf |, where |Cf | denotes the
ordinary circuit size of f . By a similar argument we obtain: |f |Γmon∪τ = |monCf |, where |monCf |
denotes the monotone circuit size of f . We saw that as a consequence of the work of Razborov, Alon,
Boppana, and Tardos, there exists an infinite set of monotone functions that have polynomial-size
circuits but whose monotone circuit-size is exponential. The exponential distortion follows. ✷
Since lepM2,1 has quadratic distortion in M2,1, monM2,1 also has exponential word-length distor-
tion in M2,1.
References
[1] N. Alon, R. Boppana, “The monotone circuit complexity of boolean functions”, Combinatorica 7 (1987)
1-23.
[2] G. Arzhantseva, V. Guba, M. Sapir, “Metrics on diagram groups and uniform embeddings in a Hilbert
space”, Mathematics Arxiv (2004) http://arxiv.org/abs/math.GR/0411605.
[3] G. Arzhantseva, C. Druţu, M. Sapir, “Compression functions of uniform embeddings of groups into Hilbert
and Banach spaces”, Mathematics Arxiv (2006) http://arxiv.org/abs/math.GR/0612378
[4] C.H. Bennett, “Logical reversibility of computation”, IBM J. of Research and Development 17 (Nov. 1973)
525-532.
[5] C.H. Bennett, “Time/Space tradeoffs for reversible computation”, SIAM J. of Computing 18 (1989) 766-
[6] J.C. Birget, “The groups of Richard Thompson and complexity”, International J. of Algebra and Compu-
tation 14(5,6) (Dec. 2004) 569-626 (Mathematics ArXiv: math.GR/0204292, Apr. 2002).
[7] J.C. Birget, “Circuits, coNP-completeness, and the groups of Richard Thompson”, In-
ternational J. of Algebra and Computation 16(1) (Feb. 2006) 35-90 (Mathematics ArXiv:
http://arXiv.org/abs/math.GR/0310335, Oct. 2003).
[8] J.C. Birget, “Factorizations of the Thompson-Higman groups, and circuit complexity”, Mathematics
ArXiv: math.GR/0607349, July 2006.
[9] J.C. Birget, “Monoid generalizations of the Richard Thompson groups”, Mathematics ArXiv:
math.GR/0704.0189, 2 Apr. 2007.
[10] J. Bourgain, “On Lipschitz embedding of finite metric spaces in Hilbert space”, Israel J. of Mathematics
52 (1985) 46-52.
http://arxiv.org/abs/math.GR/0411605
http://arxiv.org/abs/math.GR/0612378
http://arxiv.org/abs/math/0204292
http://arXiv.org/abs/math.GR/0310335
http://arxiv.org/abs/math/0607349
[11] R.B. Boppana, J.C. Lagarias, “One-way functions and circuit complexity”, Information and Computation
74 (1987) 226-240.
[12] J. W. Cannon, W. J. Floyd, W. R. Parry, “Introductory notes on Richard Thompson’s groups”,
L’Enseignement Mathématique 42 (1996) 215-256.
[13] W. Diffie, M.E. Hellman, “New directions in cryptography”, IEEE Transactions in Information Theory 22
(1976) 644-655.
[14] B. Farb, “The extrinsic geometry of subgroups and the generalized word problem”, Proc. London Mathe-
matical Society (3) 68 (1994) 577-593.
[15] E. Fredkin, T. Toffoli, “Conservative logic”, International J. Theoretical Physics 21 (1982) 219-253.
[16] J. Grollman, A. Selman, “Complexity measure for public-key cryptosystems”, SIAM J. on Computing 17
(1988) 309-335.
[17] M. Gromov, “Asymptotic invariants of infinite groups”, in Geometric Group Theory (G. Niblo, M. Roller,
editors), London Mathematical Society Lecture Notes Series 182, Cambridge Univ. Press (1993).
[18] G. Higman, “Finitely presented infinite simple groups”, Notes on Pure Mathematics 8, The Australian
National University, Canberra (1974).
[19] A.P.L. Hiltgen, “Cryptographically relevant contributions to combinatorial complexity”, Dissertation,
ETH-Zürich. Hartung-Gorre Verlag, Konstanz (1994).
[20] A.P.L. Hiltgen, “Construction of feebly-one-way families of permutations”, in Advances in Cryptology –
AUSCRYPT’92, Lecture Notes in Computer Science 718 (1993) 422-434.
[21] P. Indyk, J. Matousek, “Low-distortion embeddings of finite metric spaces”, Chapter 8 in Handbook of
Discrete and Computational Geometry (J.E. Goodman and J. O’Rourke, editors), CRC Press LLC, Boca
Raton, FL; Second Edition (2004).
[22] Y. Lecerf, “Machines de Turing réversibles ...”, Comptes Rendus de l’Académie des Sciences, Paris 257
No. 18 (Oct. 1963) 2597 - 2600.
[23] O.B. Lupanov, “A method of circuit synthesis”, Izv. V.U.Z. Radiofiz. 1 (1958) 120-140.
[24] S. Margolis, J. Meakin, Z. Šuniḱ, “Distortion functions and the membership problem for submonoids of
groups and monoids”, Contemporary Mathematics, AMS, 372 (2005) 109-129.
[25] J.L. Massey, “The Difficulty with Difficulty”, IACR Distinguished Lecture delivered at EUROCRYPT ’96,
July 17, 1996, Saragossa, Spain. ( http://www.iacr.org/publications/dl/ )
[26] R. McKenzie, R.J. Thompson, “An elementary construction of unsolvable word problems in group theory”,
in Word Problems, (W. W. Boone, F. B. Cannonito, R. C. Lyndon, editors), North-Holland (1973) pp.
457-478.
[27] V. Nekrashevych, Self-similar groups, Mathematical Surveys and Monographs vol. 117 (2005), American
Mathematical Society.
[28] A.Y. Ol’shanskii, “On subgroup distortion in finitely presented groups”, Matematicheskii Sbornik 188
(1997) 51-98.
[29] A.Y. Ol’shanskii, M.V. Sapir, “Length and area functions on groups and quasi-metric Higman embedding”,
International J. of Algebra and Computation 11 (2001) 137-170.
[30] A.A. Razborov, “Lower bounds for the monotone complexity of some boolean functions”, Doklady Akademii
Nauk SSSR 281(4) (1985) 798-801. (English transl.: Soviet Mathematical Doklady 31 (1985) 354-357.)
http://www.iacr.org/publications/dl/
[31] A.A. Razborov, “Lower bounds of monotone complexity of the logical permanent function”, Matematich-
eskie Zametki 37(6) (1985) 887-900. (English transl.: Mathematical Notes of the Academy of Sciences of
the USSR 37 (1985) 485-493.)
[32] J.E. Savage, Models of Computation, Addison-Wesley (1998).
[33] E.A. Scott, “A construction which can be used to produce finitely presented infinite simple groups”, J. of
Algebra 90 (1984) 294-322.
[34] A. Selman, “A survey of one-way functions in complexity theory”, Mathematical Systems Theory 25 (1992)
203-221.
[35] C.E. Shannon, “The synthesis of two-terminal switching circuits”, Bell System Technical J. 28 (1949)
59-98.
[36] V. Shende, A. Prasad, I. Markov, J. Hayes, “Synthesis of reversible logic circuits”, IEEE Transactions on
Computer-Aided Design of Integrated Circuits and Systems 22(6) (2003) 710-722.
[37] E. Tardos, “The gap between monotone and non-monotone circuit complexity is exponential”, Combina-
torica 7(4) (1987) 141-142.
[38] Richard J. Thompson, Manuscript (1960s).
[39] R.J. Thompson, “Embeddings into finitely generated simple groups which preserve the word problem”, in
Word Problems II, (S. Adian, W. Boone, G. Higman, editors), North-Holland (1980) pp. 401-441.
[40] T. Toffoli, “Reversible computing”, MIT Laboratory for Computer Science, Technical Memo
MIT/LCS/TM-151 (1980).
[41] T. Toffoli, “Reversible computing”, Automata, Languages and Programming (7th Colloquium), Lecture
Notes in Computer Science 85 (July 1980) 623-644. (Abridged version of [40].)
[42] J. van Leeuwen (editor), Handbook of Theoretical Computer Science, volume A, MIT Press and Elsevier
(1990).
[43] I. Wegener, The complexity of boolean functions, Wiley/Teubner (1987).
Jean-Camille Birget
Dept. of Computer Science
Rutgers University at Camden
Camden, NJ 08102, USA
birget@camden.rutgers.edu
	Introduction
	 One-way functions and one-way permutations
	Computational Asymmetry
	Wordlength asymmetry
	Computational asymmetry and reversible computing
	Distortion
	Thompson-Higman groups and monoids
	Boolean functions as elements of Thompson monoids
	Wordlength asymmetry vs. computational asymmetry
	Reversible representation over the Thompson groups
	Distortion vs. computational asymmetry
	Other bounds and distortions
	Other distortions in the Thompson groups and monoids
	 Monotone boolean functions and distortion

  Computational asymmetry, i.e., the discrepancy between the complexity of
transformations and the complexity of their inverses, is at the core of one-way
transformations. We introduce a computational asymmetry function that measures
the amount of one-wayness of permutations. We also introduce the word-length
asymmetry function for groups, which is an algebraic analogue of computational
asymmetry. We relate boolean circuits to words in a Thompson monoid, over a
fixed generating set, in such a way that circuit size is equal to word-length.
Moreover, boolean circuits have a representation in terms of elements of a
Thompson group, in such a way that circuit size is polynomially equivalent to
word-length. We show that circuits built with gates that are not constrained to
have fixed-length inputs and outputs, are at most quadratically more compact
than circuits built from traditional gates (with fixed-length inputs and
outputs). Finally, we show that the computational asymmetry function is closely
related to certain distortion functions: The computational asymmetry function
is polynomially equivalent to the distortion of the path length in Schreier
graphs of certain Thompson groups, compared to the path length in Cayley graphs
of certain Thompson monoids. We also show that the results of Razborov and
others on monotone circuit complexity lead to exponential lower bounds on
certain distortions.

Introduction
The existence of one-way functions, i.e., functions that are “easy to evaluate” but “hard to invert”,
is a major open problem. Much of cryptography depends on one-way functions; moreover, indirectly,
their existence is connected to the question whether P is different from NP. In this paper we give some
connections between these questions and some group-theoretic concepts:
(1) We continue the work of [7], [8], and [9], on the relation between combinational circuits, on the one
hand, and Thompson groups and monoids on the other hand. We give a representation of any circuit
by a word over the Thompson group, such that circuit size is polynomially equivalent to word-length.
(2) We establish connections between the existence of one-way permutations and the distortion func-
tion in a certain Thompson group. Distortion is an important concept in metric spaces (e.g., Bourgain
[10]) and in combinatorial group theory (e.g., Gromov [17], Farb [14]).
Overview:
Subsections 1.1 - 1.6 of the present Section define and motivate the concepts used: One-way functions
and one-way permutations; computational asymmetry; word-length asymmetry; reversible computing;
distortion; Thompson groups and monoids. In Section 2 we show that circuits can be represented by
elements of Thompson monoids: A boolean circuit is equivalent to a word over a fixed generating set
∗Supported by NSF grant CCR-0310793. Some of the results of this paper were presented at the AMS Section
Meeting, Oct. 21-23, 2005, Lincoln, Nebraska (http://www.ams.org/amsmtgs/2117 program.html), and at the conference
“Various Faces of Cryptography”, 10 Nov. 2006 at City College of CUNY, New York.
http://arxiv.org/abs/0704.1569v1
http://www.ams.org/amsmtgs/2117_program.html
of a Thompson monoid, with circuit size being equal (or linearly equivalent) to word-length over the
generating set. The Thompson monoids that appear here are monoid generalizations of the Thompson
group G2,1, obtained when bijections are generalized to partial functions [9]. Section 3 shows that
computational asymmetry and word-length asymmetry (for the Thompson groups and monoids) are
linearly related. In Section 4 we give a representation of arbitrary (not necessarily bijective) circuits
by elements of the Thompson group G2,1; circuit size is polynomially equivalent to word-length over
a certain generating set in the Thompson group. In Section 5 we show that the computational
asymmetry function of permutations is polynomially related to a certain distortion in a Thompson
group. Section 6 contains miscellaneous results, in particular that the work of Razborov and others
on monotone circuit complexity leads to exponential lower bounds on certain distortion functions.
1.1 One-way functions and one-way permutations
Intuitively, a one-way function is a function f (mapping words to words, over a finite alphabet), such
that f is “easy to evaluate” (i.e., given x0 in the domain, it is “easy” to compute f(x0)), but “hard
to invert” (i.e., given y0 in the range, it is “hard” to find any x0 such that f(x0) = y0). The concept
was introduced by Diffie and Hellman [13].
There are many ways of defining the words “easy” and “hard”, and accordingly there exist many
different rigorous notions of a one-way function, all corresponding to a similar intuition. It remains
an open problem whether one-way functions exist, for any “reasonable” definition. Moreover, for
certain definitional choices, this problem is a generalization of the famous question whether P 6= NP
[16, 34, 11].
We will base our one-way functions on combinational circuits and their size. The size of a circuit
will also be called its complexity. Below, {0, 1}n (for any integer n ≥ 0) denotes the set of all bitstrings
of length n. A combinational circuit with input-output function f : {0, 1}m → {0, 1}n is an acyclic
boolean circuit with m input wires (or “input ports”) and n output wires (or “output ports”). The
circuit is made from gates of type not, and, or, fork, as well as wire-crossings or wire-swappings. These
gates are very traditional and are defined as follows.
and: (x1, x2) ∈ {0, 1}2 7−→ y ∈ {0, 1}, where y = 1 if x1 = x2 = 1, and y = 0 otherwise.
or: (x1, x2) ∈ {0, 1}2 7−→ y ∈ {0, 1}, where y = 0 if x1 = x2 = 0, and y = 1 otherwise.
not: x ∈ {0, 1} 7−→ y ∈ {0, 1}, where y = 0 if x = 1, y = 1 otherwise.
fork: x ∈ {0, 1} 7−→ (x, x) ∈ {0, 1}2.
Another gate that is often used is the exclusive-or gate,
xor: (x1, x2) ∈ {0, 1}2 7−→ y ∈ {0, 1}, where y = 1 if x1 6= x2, and y = 0 otherwise.
The wire-swapping of the ith and jth wire (i < j) is described by the bit transposition (or bit position
transposition)
τi,j : uxivxjw ∈ {0, 1}ℓ 7−→ uxjvxiw ∈ {0, 1}ℓ, where |u| = i− 1, |v| = j − i− 1, |w| = ℓ− j − 1.
The fork and wire-swapping operations, although heavily used, are usually not explicitly called “gates”;
but because of their important role we will need to consider them explicitly. Other notations for the
gates: and(x1, x2) = x1 ∧ x2, or(x1, x2) = x1 ∨ x2, not(x) = x, xor(x1, x2) = x1 ⊕ x2.
A combinational circuit for a function f : {0, 1}m → {0, 1}n is defined by an acyclic directed graph
drawn in the plane (with crossing of edges allowed). In the circuit drawing, the m input ports are
vertices lined up in a vertical column on the left end of the circuit, and the n output ports are vertices
lined up in a vertical column on the right end of the circuit. The input and output ports and the gates
of the circuit (including the fork gates, but not the wire transpositions) form the vertices of the circuit
graph. We often view the circuit as cut into vertical slices. A slice can be any collection of gates and
wires in the circuit such that no gate in a slice is an ancestor of another gate in the same slice, and
no wire in a slice is an ancestor of another wire in the same slice (unless these two wires are an input
wire and an output wire of a same gate). Two slices do not overlap, and every wire and every gate
belongs to some slice. For more details on combinational circuits, see [32, 43, 11].
The size of a combinational circuit is defined to be the number of gates in the circuit, including
forks and wire-swappings, as well as the input ports and the output ports. For a function f : {0, 1}m →
{0, 1}n, the circuit complexity (denoted C(f)) is the smallest size of any combinational circuit with
input-output function f .
A cause of confusion about gates in a circuit is that gates of a certain type (e.g., and) are tradi-
tionally considered the same, no matter where they occur in the circuit. However, gates applied to
different wires in a circuit are different functions; e.g., for the and gate, (x1, x2, x3) 7→ (x1 ∧ x2, x3) is
a different function than (x1, x2, x3) 7→ (x1, x2 ∧ x3).
1.2 Computational Asymmetry
Computational asymmetry is the core property of one-way functions. Below we will define computa-
tional asymmetry in a quantitative way, and in a later Section we will relate it to the group-theoretic
notion of distortion.
For the existence of one-way functions, it is mainly the relation between the circuit complexity
C(f) of f and the circuit complexity C(f−1) of f−1 that matters, not the complexities of f and of
f−1 themselves. Indeed, a classical padding argument can be used: If we add C(f) “identity wires” to
a circuit for f , then the resulting circuit has linear size as a function of its number of input wires; see
Proposition 1.2 below. (An identity wire is a wire that goes directly from an input port to an output
port, without being connected to any gate.)
In [11] (page 230) Boppana and Lagarias considered logC(f ′)/logC(f) as a measure of one-
wayness; here, f ′ denotes an inverse of f , i.e., any function such that f ◦ f ′ ◦ f = f . Massey and
Hiltgen [25, 19] introduced the phrases complexity asymmetry and computational asymmetry for injec-
tive functions, in reference to the situation where the circuit complexities C(f) and C(f−1) are very
different. The concept of computational asymmetry can be generalized to arbitrary (non-injective)
functions, with the meaning that for every inverse f ′ of f , C(f) and C(f ′) are very different.
In [25] Massey made the following observation. For any large-enough fixed m and for almost all
permutations f of {0, 1}m, the circuit complexities C(f) and C(f−1) are very similar:
C(f) ≤ C(f−1) ≤ 10 C(f)
Massey’s proof is adapted from the Shannon lower bound [35] and the Lupanov upper bound [23] (see
also [19], [32]), from which it follows that almost all functions and almost all permutations (and their
inverses) have circuit complexity close to the Shannon bounds. Massey’s observation can be extended
to the set of all functions f : {0, 1}m → {0, 1}n, i.e., for almost all f and for every inverse f ′ of f , the
complexities C(f) and C(f ′) are within constant factors of each other.
Hence, computationally asymmetric permutations are rare among the boolean permutations overall
(and similarly for functions). This is an interesting fact about computational asymmetry, but by
itself it does not imply anything about the existence or non-existence of one-way functions, not even
heuristically. Indeed, Massey proved his linear relation C(f) = Θ(C(f ′)) in the situation where
C(f) = Θ(2m), and then uses the fact that the condition C(f) = Θ(2m) holds for almost all boolean
permutations and for almost all boolean functions. But there also exist functions with C(f) = O(mk),
with k a small constant. In particular, one-way functions (if they exist) have small circuits; by
definition, one-way functions violate the condition C(f) = Θ(2m).
A well-known candidate for a one-way permutation is the following. For a large prime number p
and a primitive root r modulo p, consider the map x ∈ {0, 1, . . . , p−2} 7−→ rx−1 ∈ {0, 1, . . . , p−2}.
This is a permutation whose inverse, known as the discrete logarithm, is believed to be difficult to
compute.
Measuring computational asymmetry:
Let S{0,1}m denote the set of all permutations of {0, 1}m, i.e., S{0,1}m is the symmetric group. We
will measure the computational asymmetry of all permutations of {0, 1}m (for all m > 0) by defining
a computational asymmetry function, as follows. A function a : N → N is an upper bound on the
computational asymmetry function iff for all all m > 0 and all permutations f of {0, 1}m we have:
C(f−1) ≤ a
. The computational asymmetry function α of the boolean permutations is the
least such function a(.). Hence:
Definition 1.1 The computational asymmetry function α of the boolean permutations is defined as
follows for all s ∈ N : α(s) = max
C(f−1) : C(f) ≤ s, f ∈ S{0,1}m , m > 0
Note that in this definition we look at all combinational circuits, for all permutations in
m>0 S{0,1}m ;
we don’t need to work with non-uniform or uniform families of circuits.
Computational asymmetry is closely related to one-wayness, as the next proposition shows.
Proposition 1.2
(1) For infinitely many n we have: There exists a permutation fn of {0, 1}n such that fn is computed
by a circuit of size ≤ 3n, but f−1n has no circuit of size < α(n).
(2) Suppose that α is exponential, i.e., there is k > 1 such that for all n, α(n) ≥ kn. Then k ≤ 2,
and there is a constant c > 1 such that we have: For every integer n ≥ 1 there exists a permutation
Fn of {0, 1}n which is computed by a circuit of size ≤ c n, but F−1n has no circuit of size < kn.
Proof. (1) By the definition of α, for every m > 0 there exists a permutation F of {0, 1}m such that
F is computed by a circuit of some size CF , but F
−1 has no circuit of size < α(CF ). Let n = CF ,
and let us consider the function fn : {0, 1}CF → {0, 1}CF defined by fn : (x,w) 7−→ (F (x), w), for all
x ∈ {0, 1}m and w ∈ {0, 1}CF−m.
Then fn(x,w) is computed by a circuit of size CF + 2 (CF − m); the term “2 (CF −m)” comes
from counting the input-output wires of w. Hence fn has a circuit of size ≤ 3n. On the other hand,
(y,w) 7−→ f−1n (y,w) = (F−1(y), w) is not computed by any circuit of size < α(CF ), so f−1n has no
circuit of size < α(n).
(2) For every n ≥ 1 there exists a permutation F of {0, 1}n such that F is computed by a circuit of
some size CF , and F
−1 has a circuit of size CF−1 = α(CF ) ≥ kCF ; moreover, F−1 has no circuit of
size < α(CF ). Thus, k
CF ≤ CF−1 ≤ 2n (1 + co lognn ), for some constant co > 1; the latter inequality
comes from the Lupanov upper bound [23] (or see Theorem 2.13.2 in [32]). Hence, k ≤ 2 and n ≤
CF ≤ 1log2 k n + c1
, for some constant c1 > 0. Hence, for all n ≥ 1 there exists a permutation F
of {0, 1}n with circuit size CF ∈ [n, 1log2 k · n+ c1 ·
], such that CF−1 = α(CF ) ≥ kCF ≥ kn. ✷
We will show later that the computational asymmetry function is closely related to the distortion
of certain groups within certain monoids.
Remarks:
Although in this paper we only use the computational asymmetry function of the boolean permuta-
tions, the concept can be generalized. Let Inj({0, 1}m, {0, 1}n) denote the set of all injective functions
{0, 1}m → {0, 1}n. The computational asymmetry function αinj of the injective boolean functions is
defined by
αinj(s) = max
C(f−1) : C(f) ≤ s, f ∈ Inj({0, 1}m, {0, 1}n), m > 0, n > 0
More generally, let ({0, 1}n){0,1}m denote the set of all functions {0, 1}m → {0, 1}n. The computa-
tional asymmetry of all finite boolean functions is defined by
αfunc(s) = max
C(f ′) : C(f) ≤ s, ff ′f = f, f, f ′ ∈ ({0, 1}n){0,1}m , n > 0,m > 0
When we compare functions we will be mostly interested in their asymptotic growth pattern.
Hence we will often use the big-O notation, and the following definitions.
By definition, two functions f1 : N → N and f2 : N → N are linearly equivalent iff there are
constants c0, c1, c2 > 0 such that for all n ≥ c0 : f1(n) ≤ c1 f2(c1n) and f2(n) ≤ c2 f1(c2n).
Notation: f1 ≃lin f2.
Two functions f1 and f2 (from N to N) are called polynomially equivalent iff there are constants
c0, c1, c2, d, e > 0 such that for all n ≥ c0 : f1(n) ≤ c1 f2(c1nd)d and f2(n) ≤ c2 f1(c2ne)e. Notation:
f1 ≃poly f2.
1.3 Wordlength asymmetry
We introduce an algebraic notion that looks very similar to computational asymmetry:
Definition 1.3 Let G be a group, let M be a monoid with generating set Γ (finite or infinite), and
suppose G ⊆M . The word-length asymmetry function of G within M (over Γ) is
λ(n) = max{ |g−1|Γ : |g|Γ ≤ n, g ∈ G}.
The word-length asymmetry function λ depends on G, M , Γ, and the embedding of G in M .
Consider the right Cayley graph of the monoid M with generating set Γ; its vertex set is M and
the edges have the form x
γ−→ γx (for x ∈ M , γ ∈ Γ). For x, y ∈ M , the directed distance d(x, y)
in the Cayley graph is the shortest length over all paths from x to y in the Cayley graph; if no path
from x to y exists, the directed distance is infinite. By “path” we always mean directed path.
Lemma 1.4 Under the above conditions on G, M , Γ, we have for every g ∈ G : d(1, g−1) = d(g,1)
and d(1, g) = d(g−1,1).
Proof. Let η : Γ∗ →M be the map that evaluates generator sequences in M . If v ∈ Γ∗ is the label of
a shortest path from 1 to g−1 in the Cayley graph then g ·η(v) = 1 inM , hence η(v) = g−1. Therefore,
the path starting at g and labeled by v ends at 1; hence d(g,1) ≤ |v| = d(1, g−1). In a similar way
one proves that d(1, g−1) ≤ d(g,1). The equality d(1, g) = d(g−1,1) is also proved in a similar way.
Since |g|Γ is the distance d(1, g) in the graph of M , and since |g−1|Γ = d(1, g−1) = d(g,1), the
word-length asymmetry also measures the asymmetry of the directed distance, to or from the identity
element 1 in the Cayley graph of M , restricted to vertices in the subgroup G.
For distances to or from the identity element of M it does not matter whether we consider the left
Caley graph or the right Caley graph.
1.4 Computational asymmetry and reversible computing
Reversible computing deals with the following questions: If a function f is injective (or bijective) and
computable, can f be computed in such a way that each elementary computation step is injective
(respectively bijective)? And if such injective (or bijective) computations are possible, what is their
complexity, compared to the usual (non-injective) complexity?
One of the main results is the following (Bennett’s theorem [4, 5], and earlier work of Lecerf
[22]): Let f be an injective function, and assume f and f−1 are computable by deterministic Turing
machines with time complexity Tf (.), respectively Tf−1(.). Then f (and also f
−1) is computable
by a reversible Turing machine (in which every transition is deterministic and injective) with time
complexity O(Tf + Tf−1). Note that only injectiveness (not bijectiveness) is used here.
Bennett’s theorem has the following important consequence, which relates reversible computing
to one-way functions: Injective one-way functions exist iff there exist injective functions that have
efficient traditional algorithms but that do not have efficient reversible algorithms.
Toffoli representation
Remarkably, it is possible to “simulate” any function f : {0, 1}m → {0, 1}n (injective or not, one-
way or not) by a bijective circuit; a circuit is called bijective iff the circuit is made from bijective
gates. Here, bijective circuits will be built from the wire swapping operations and the following
bijective gates: not (negation), c-not (the Controlled Not, also called “Feynman gate”) defined by
(x1, x2) ∈ {0, 1}2 7−→ (x1, x1 ⊕ x2) ∈ {0, 1}2, and cc-not (the Doubly Controlled Not, also called
“Toffoli gate”) defined by (x1, x2, x3) ∈ {0, 1}3 7−→ (x1, x2, (x1 ∧ x2)⊕ x3) ∈ {0, 1}3.
Theorem 1.5 (Toffoli [40]). For every boolean function f : {0, 1}m → {0, 1}n there exists a bijective
boolean circuit βf (over the bijective gates not, c-not, cc-not, and wire transpositions), with input-
output function βf : x 0
n ∈ {0, 1}m+n 7−→ f(x) x ∈ {0, 1}n+m.
In other words, f(x) consists of the projection onto the first n bits of βf (x 0
n); equivalently, f(.) =
projn ◦ βf ◦ concat0n(.), where projn projects a string of length n+m to the first n bits, and concat0n
concatenates 0n to the right of a string. See Theorems 4.1, 5.3 and 5.4 of [40], and see Fig. 1 below.
✲ f(x)
Fig. 1: Toffoli representation of the function f .
The Toffoli representation contains two non-bijective actions: The projection at the output, and
the forced setting of the value of some of the input wires.
Toffoli’s proofs and constructions are based on truth tables, and he does not prove anything about
the circuit size of βf (counting the bijective gates), compared to the circuit size of f . The following
gives a polynomial bound on the size of the bijective circuit, at the expense of a large number of input-
and output-wires.
Theorem 1.6 (E. Fredkin, T. Toffoli [15]). For every boolean function f : {0, 1}m → {0, 1}n with
circuit size C(f) there exists a bijective boolean circuit Bf (over a bounded collection of bijective gates,
e.g., not, c-not, cc-not, and wire transpositions), with input-output function
Bf : x 0
n+C(f) ∈ {0, 1}m+n+C(f) 7−→ f(x) z(x) ∈ {0, 1}m+n+C(f)
for some z(x) ∈ {0, 1}m+C(f).
If g : {0, 1}m → {0, 1}m is a permutation then there exists a bijective boolean circuit Ug (over
bijective gates), with input-output function
Ug : x 1
m 0m+C ∈ {0, 1}3m+C 7−→ g(x) g(x) x 0C ∈ {0, 1}3m+C
where C = max{C(g), C(g−1)}, and g(x) is the bitwise complement of g(x).
Later we will introduce another reversible representation of boolean functions by bijective gates;
we will need only one 0-wire, but the gates will be taken from the Thompson group G2,1, i.e., we will
also use non-length-preserving transformations of bitstrings (Theorems 4.1 and 4.2 below).
1.5 Distortion
We will prove later (Theorem 5.10) that computational asymmetry has a lot to do with distortion,
a concept introduced into group theory by Gromov [17] and Farb [14]. Distortion is already known
to have connections with isoperimetric functions (see [28], [29], [24]). A somewhat different problem
about distortion (for finite metric spaces) was tackled by Bourgain [10].
We will use a slightly more general notion of distortion, based on (possibly directed) countably
infinite rooted graphs, and their (directed) path metric.
A weighted directed graph is a structure (V,E, ω) where V is a set (called the vertex set), E ⊆ V ×V
(called the edge set), and ω : E 7−→ R>0 is a function (called the weight function); note that every edge
has a strictly positive weight. It is sometimes convenient to define ω(u, v) = ∞ when (u, v) ∈ V ×V −E.
A path in (V,E) is a sequence of edges (ui, vi) (1 ≤ i ≤ n) such that ui+1 = vi for all i < n, and
such that all elements in {ui : 1 ≤ i ≤ n} ∪ {vn} are distinct; u1 is called the start vertex of this
path, and vn is called the end vertex of this path; the sum of weights
i=1 ω(ui, vi) over the edges
in the path is called the length of the path. Here we do not consider any paths with infinitely many
edges; but we allow V and E to be countably infinite. A vertex w2 is said to be reachable from a
vertex w1 in (V,E) iff there exists a path with start vertex w1 and end vertex w2. If w2 is reachable
from w1 then the minimum length over all paths from w1 to w2 is called the directed distance from
w1 to w2, denoted d(w1, w2); since we only consider finite paths here, this minimum exists. If w2 is
not reachable from w1 then we define d(w1, w2) to be ∞. Clearly we have w1 = w2 iff d(w1, w2) = 0,
and for all u, v, w ∈ V , d(u,w) ≤ d(u, v) + d(v,w). In a directed graph, the function d(., .) need not
be symmetric. The function d : V ×V → R≥0 ∪{∞} is called the directed path metric of (V,E, ω). A
rooted directed weighted graph is a structure (V,E, ω, r) where (V,E, ω) is a directed weighted graph,
r ∈ V , and all vertices in V are reachable from r.
A set M with a function d : M × M → R≥0 ∪ {∞}, satisfying the two axioms w1 = w2 iff
d(w1, w2) = 0, and d(u,w) ≤ d(u, v) + d(v,w), will be called directed metric space (a.k.a. quasi-metric
space).
Any subset G embedded in a directed metric space M becomes a directed metric space by using
the directed distance of M . We call this the directed distance on G inherited from M .
If G ⊆ V for a rooted directed weighted graph (V,E, ω, r), we consider the function ℓ : g ∈ G 7−→
d(r, g) ∈ R≥0, which we call the directed length function on G inherited from (V,E, ω, r). (The value
∞ will not appear here since all of G is reachable from r.)
We now define distortion in a very general way. Intuitively, distortion in a set is a quantitative
comparison between two (directed) length functions that are defined on the same set.
Definition 1.7 Let G be a set, and let ℓ1 and ℓ2 be two functions G → R≥0. The distortion of ℓ1
with respect to ℓ2 is the function δℓ1,ℓ2 : R≥0 → R≥0 defined by
δℓ1,ℓ2(n) = max{ℓ1(g) : g ∈ G, ℓ2(g) ≤ n}.
We will also use the notation δ[ℓ1, ℓ2](.) for δℓ1,ℓ2(.). When we consider a distortion δℓ1,ℓ2(.) we often
assume that ℓ2 ≤ ℓ1 or ℓ2 ≤ O(ℓ1); this insures that the distortion is at least linear, i.e., δℓ1,ℓ2(n) ≥ c n,
for some constant c > 0. We will only deal with functions obtained from the lengths of finite paths
in countable directed graphs, so in that case the functions ℓi are discrete, and the distortion function
exists. The next Lemma generalizes the distortion result of Prop. 4.2 of [14].
Lemma 1.8 Let G be a set and consider three functions ℓ3, ℓ2, ℓ1 : G→ R≥0 such that ℓ1(.) ≥ ℓ2(.) ≥
ℓ3(.). Then the corresponding distortions satisfy: δℓ1,ℓ3(.) ≤ δℓ1,ℓ2 ◦ δℓ2,ℓ3(.).
Proof. The inequalities ℓ1(.) ≥ ℓ2(.) ≥ ℓ3(.) guarantee that the three distortions δℓ1,ℓ3 , δℓ1,ℓ2 , and
δℓ2,ℓ3 are at least as large as the identity map. By definition,
δℓ1,ℓ2
δℓ2,ℓ3(n)
= max{ℓ1(x) : x ∈ G, ℓ2(x) ≤ δℓ2,ℓ3(n)}
= max
ℓ1(x) : x ∈ G, ℓ2(x) ≤ max{ℓ2(z) : z ∈ G, ℓ3(z) ≤ n}
= max
ℓ1(x) : x ∈ G, (∃z ∈ G)
ℓ2(x) ≤ ℓ2(z) and ℓ3(z) ≤ n
≥ max{ℓ1(x) : x ∈ G, ℓ3(x) ≤ n} = δℓ1,ℓ3(n).
The last inequality follows from the fact that if ℓ3(x) ≤ n then for some z (e.g., for z = x):
ℓ2(x) ≤ ℓ2(z) and ℓ3(z) ≤ n. ✷
Examples of distortion:
Distortion and asymmetry are unifying concepts that apply to many fields.
1. Gromov distortion: Let G be a subgroup of a group H, with generating sets ΓG, respectively
ΓH , such that ΓG ⊆ ΓH , and such that ΓG = Γ−1G and ΓH = Γ
H . This determines a Cayley graph
for G and a Cayley graph for H. Now we have two distance functions on G, one obtained from the
Cayley graph of G itself (based on ΓG), and the other inherited from the embedding of G in H. See
[17], [10], and [14].
The Gromov distortion function is a natural measure of the difficulty of the generalized word
problem. A very important case is when both ΓG and ΓH are finite. Here are some results for that
case:
Theorem of Ol′shanskii and Sapir [29] (making precise and proving the outline on pp. 66-67 in [17]):
All Dehn functions of finitely presented groups (and “approximately all” time complexity functions of
nondeterministic Turing machines) are Gromov distortion functions of finitely generated subgroups
of FG2×FG2; here, FG2 denotes the 2-generated free group. Moreover, in [6] it was proved that
FG2×FG2 is embeddable with linear distortion in the Thompson group G2,1. So the theorem of
Ol′shanskii and Sapir also holds for the finitely generated subgroups of G2,1.
Actually, Gromov [17] and Bourgain [10] defined the distortion to be 1
·max{|g|ΓG : |g|ΓH ≤ n, g ∈
G}, i.e., they use an extra factor 1
. However, the connections between distortion, the generalized word
problem, and complexity (as we just saw, and will further see in the present paper) are more direct
without the factor 1
2. Bourgain’s distortion theorem: Given a finite metric space G with n elements, the aim is to
find embeddings of G into a finite-dimensional euclidean space. The two distances of G are its given
distance and the inherited euclidean distance. In this problem the goal is to have small distortion,
as a function of the cardinality of G, while also keeping the dimension of the euclidean space small.
Bourgain [10] found a bound O(n log n) for the distortion (or “O(log n)” in Bourgain’s and Gromov’s
terminology). This is an important result. See also [21], [2], [3].
3. Generator distortion: A variant of Gromov’s distortion is obtained when G = H, but ΓG $ ΓH .
So here we look at the distorting effect of a change of generators in a given group. When ΓG and
ΓH are both finite the generator distortion is linear; however, when ΓG is finite and ΓH is infinite
the distortion becomes interesting. E.g., for the Thompson group G2,1 let us take ΓG to be any finite
generating set, and for ΓH let us take ΓG ∪ {τi,j : 1 ≤ i < j}; here τi,j is the position transposition
defined earlier. Then the generator distortion is exponential (see [7]). Also, the word problem of G2,1
over any finite generating set ΓG is in P, but the word problem of G2,1 over ΓG ∪ {τi,j : 1 ≤ i < j} is
coNP-complete (see [7] and [8]).
4. Monoids and directed distance: Gromov’s distortion and the generator distortion can be
generalized to monoids. We repeat what we said about Gromov distortion, but G and H are now
monoids, and ΓG, respectively ΓH , are monoid generating sets which are used to define monoid Cayley
graphs. We will use the left Cayley graphs. We assume ΓG ⊆ ΓH . In each Cayley graph there is
a directed distance, defined by the lengths of directed paths. The monoid G now has two directed
distance functions, the distance in the Cayley graph ofG itself, and the directed distance thatG inherits
from its embedding into the Cayley graph of H. We denote the word-length of g ∈ G over ΓG by |g|G;
this is the minimum length of all words over ΓG that represent g; it is also the length of a shortest
path from the identity to g in the Cayley graph of G. Similarly, we denote the word-length of h ∈ H
over ΓH by |h|H . The definition of the distortion becomes: δ(n) = max{|g|G : g ∈ G, |g|H ≤ n}.
5. Schreier graphs: Let G, H, and F be groups, where F is a subgroup of H. Let ΓH be a
generating set of ΓH , and assume ΓH = Γ
H . We can define the Schreier left coset graph of H/F
over the generating set ΓH , and the distance function dH/F (., .) in this coset graph. By definition,
this Schreier graph has vertex set H/F (i.e., the left cosets, of the form h · F with h ∈ H), and it has
directed edges of the form h · F γ−→ γg · F , for h ∈ H, γ ∈ ΓH . The graph is symmetric; for every
edge as above there is an opposite edge γh ·F γ
−→ h ·F . Because of symmetry the Schreier graph has
a (symmetric) distance function based on path length, dH/F (., .) : H/F ×H/F → N.
Next, assume that G is embedded into H/F by some injective function G →֒ H/F . Such an
embedding happens, e.g., if G and F are subgroups of H such that G∩F = {1}. Indeed, in that case
each coset in H/F contains at most one element of G (since g1F = g2F implies g
2 g1 ∈ F ∩G = {1}).
The group G now inherits a distance function from the path length in the Schreier graph of H/F .
Comparing this distance with other distances in G leads to distortion functions. E.g., if the group G
is also embedded in a monoid M with monoid generating set ΓM , this leads to the following distortion
function: δG(n) = max{dH/F (F, gF ) : g ∈ G, |g|M ≤ n}.
It will turn out that for appropriate choices of G,F,H, ΓH , and ΓM , this last distortion is polyno-
mially related to the computational asymmetry function α of boolean permutations (Theorem 5.10).
6. Asymmetry functions: We already saw the computational asymmetry function of combinational
circuits, and the word-length asymmetry function of a group embedded in a monoid. More generally,
in any quasi-metric space (S, d), where d(., .) is a directed distance function, an asymmetry function
A : R≥0 → R≥0 can be defined by A(n) = max{d(x2, x1) : x1, x2 ∈ S, d(x1, x2) ≤ n}.
This asymmetry function can also be viewed as the distortion of drev with respect to d in S; here
drev denotes the reverse directed distance, defined by drev(x1, x2) = d(x2, x1).
7. Other distortions:
- Distortion can compare lengths of proofs (or lengths of expressions) in various, more or less pow-
erful proof systems (respectively description languages). Distortion can also compare the duration of
computations or of rewriting processes in various models of computation. Hence, many (perhaps all)
notions of complexity are examples of distortion. Distortion is an algebraic or geometric representation
(or cause) of complexity.
- Instead of length and distance, other measures (e.g., volumes in higher dimension, energy, action,
entropy, etc.) could be used.
1.6 Thompson-Higman groups and monoids
The Thompson groups, introduced by Richard J. Thompson [38, 26, 39], are finitely presented infinite
groups that act as bijections between certain subsets of {0, 1}∗. So, the elements of the Thompson
groups are transformations of bitstrings, and hence they are related to input-output maps of boolean
circuits. In this subsection we define the Thompson group G2,1 (also known as “V ”), as well as its
generalization (by Graham Higman [18]) to the group Gk,1 that partially acts on A
∗, for any finite
alphabet A of size k ≥ 2. We will follow the presentation of [6] (see also [8] and [7]); another reference
is [33], which is also based on string transformations but with a different terminology; the classical
references [38, 26, 39, 18, 12] do not describe the Thompson groups by transformations of finite strings.
Because of our interest in strings and in circuits, we also use generalizations of the Thompson groups
to monoids, as introduced in [9].
Some preliminary definitions, all fairly standard, are needed in order to define the Thompson-
Higman group Gk,1. First, we pick any alphabet A of cardinality |A| = k. By A∗ we denote the set
of all finite words (or “strings”) over A; the empty word ε is also in A∗. We denote the length of
w ∈ A∗ by |w| and we let An denote the set of words of length n. We denote the concatenation of
two words u, v ∈ A∗ by uv or by u · v; the concatenation of two subsets B,C ⊆ A∗ is defined by
BC = {uv : u ∈ B, v ∈ C}. A right ideal of A∗ is a subset R ⊆ A∗ such that RA∗ ⊆ R. A generating
set of a right ideal R is, by definition, a set C such that R is equal to the intersection of all right
ideals that contain C; equivalently, C generates R (as a right ideal) iff R = CA∗. A right ideal R is
called essential iff R has a non-empty intersection with every right ideal of A∗. For u, v ∈ A∗, we call
u a prefix of v iff there exists z ∈ A∗ such that uz = v. A prefix code is a subset C ⊆ A∗ such that
no element of C is a prefix of another element of C. A prefix code C over A is maximal iff C is not
a strict subset of any other prefix code over A. It is easy to prove that a right ideal R has a unique
minimal (under inclusion) generating set CR, and that CR is a prefix code; moreover, CR is a maximal
prefix code iff R is an essential right ideal.
For a partial function f : A∗ → A∗ we denote the domain by Dom(f) and the image (range) by
Im(f). A restriction of f is any partial function f1 : A
∗ → A∗ such that Dom(f1) ⊆ Dom(f), and
such that f1(x) = f(x) for all x ∈ Dom(f1). An extension of f is any partial function of which f
is a restriction. An isomorphism between right ideals R1, R2 of A
∗ is a bijection ϕ : R1 → R2 such
that for all r1 ∈ R1 and all z ∈ A∗: ϕ(r1z) = ϕ(r1) · z. The isomorphism ϕ is uniquely determined
by a bijection between the prefix codes that minimally generate R1, respectively R2. One can prove
[39, 33, 6] that every isomorphism ϕ between essential right ideals has a unique maximal extension
(within the category of isomorphisms between essential right ideals of A∗); we denote this unique
maximal extension by max(ϕ).
Now, finally, we define the Thompson-Higman group Gk,1: It consists of all maximally extended
isomorphisms between finitely generated essential right ideals of A∗. The multiplication consists of
composition followed by maximum extension: ϕ · ψ = max(ϕ ◦ ψ). Note that Gk,1 acts partially and
faithfully on A∗ on the left.
Every element ϕ ∈ Gk,1 can be described by a bijection between two finite maximal prefix codes;
this bijection can be described concretely by a finite function table. When ϕ is described by a maximally
extended isomorphism between essential right ideals, ϕ : R1 → R2, we call the minimum generating
set of R1 the domain code of ϕ, and denote it by domC(ϕ); similarly, the minimum generating set of
R2 is called the image code of ϕ, denoted by imC(ϕ).
Thompson and Higman proved that Gk,1 is finitely presented. Also, when k is even Gk,1 is a simple
group, and when k is odd Gk,1 has a simple normal subgroup of index 2. In [6] it was proved that
the word problem of Gk,1 over any finite generating set is in P (in fact, more strongly, in the parallel
complexity class AC1). In [8, 7] it was proved that the word problem of Gk,1 over Γ∪{τi,j : 1 ≤ i < j} is
coNP-complete, where Γ is any finite generating set of Gk,1, and where τi,j is the position transposition
introduced in Subsection 1.1.
Because of connections with circuits we consider the subgroup lpGk,1 of all length-preserving
elements of Gk,1; more precisely, lpGk,1 = {ϕ ∈ Gk,1 : ∀x ∈ Dom(ϕ), |x| = |ϕ(x)|}. See [8] for
a study of lpGk,1 and some of its properties. In particular, it was proved that lpGk,1 is a direct limit
of finite alternating groups, and that lpG2,1 is generated by the set {N,C, T} ∪ {τi,i+1 : 1 ≤ i},
where N : x1w 7→ x1w, C : x1x2w 7→ x1 (x2 ⊕ x1)w, and T : x1x2x3w 7→ x1x2 (x3 ⊕ (x2 ∧ x1))w
(for x1, x2, x3 ∈ {0, 1} and w ∈ {0, 1}∗). Thus (recalling Subsection 1.4), N,C, T are the not, c-not,
cc-not gates, applied to the first (left-most) bits of a binary string. It is known that the gates not,
c-not, cc-not, together with the wire-swappings, form a complete set of gates for bijective circuits (see
[36, 40, 15]); hence, lpG2,1 is closely related to the field of reversible computing.
It is natural to generalize the bijections between finite maximal prefix codes to functions between
finite prefix codes. Following [9] we will define below the Thompson-Higman monoids Mk,1. First,
some preliminary definitions. A right-ideal homomorphism of A∗ is a total function ϕ : R1 → A∗ such
that R1 is a right ideal, and such that for all r1 ∈ R1 and all z ∈ A∗: ϕ(r1z) = ϕ(r1) · z. It is
easy to prove that Im(ϕ) is then also a right ideal of A∗. From now on we will write a right-ideal
homomorphism as a total surjective function ϕ : R1 → R2, where both R1 and R2 are right ideals. The
homomorphism ϕ is uniquely determined by a total surjective function f : P1 → S2, with P1, S2 ⊂ A∗
where P1 is the prefix code (not necessarily maximal) that generates R1 as a right ideal, and where
S2 is a set (not necessarily a prefix code) that generates R2 as a right ideal; f can be described by a
finite function table.
For two sets X,Y , we say that X and Y “intersect” iff X ∩ Y 6= ∅. We say that a right ideal
R′1 is essential in a right ideal R1 iff R
1 intersects every right ideal that R1 intersects. An essential
restriction of a right-ideal homomorphism ϕ : R1 → R2 is a right ideal-homomorphism Φ : R′1 → R′2
such that R′1 is essential in R1, and for all x
1 ∈ R′1: ϕ(x′1) = Φ(x′1). In that case we also say that ϕ
is an essential extension of Φ. If Φ is an essential restriction of ϕ then R′2 = Im(Φ) will automatically
be essential in R2 = Im(ϕ). Indeed, if I is any no-empty right subideal of R1 then I ∩R′1 6= ∅, hence
∅ 6= Φ(I ∩ R′1) ⊆ Φ(I) ∩ Φ(R′1) = Φ(I) ∩ R′2; moreover, any non-empty right subideal J of R2 is of
the form J = Φ(I), where I = Φ−1(J) is a non-empty right subideal of R1; hence, for any non-empty
right subideal J of R2, ∅ 6= J ∩R′2.
The free monoid A∗ can be pictured by its right Cayley graph, which is easily seen to be the
infinite regular k-ary tree with vertex set A∗ and edge set {(v, va) : v ∈ A∗, a ∈ A}. We simply call
this the tree of A∗. It is a directed, rooted tree, with all paths directed away from the root ε (the
empty word); by “path” we will always mean a directed path. Many of the previously defined concepts
can be reformulated more intuitively in the context of the tree of A∗: A word v is a prefix of a word
w iff v is an ancestor of w in the tree. A set P is a prefix code iff no two elements of P are on a
common path. A set R is a right ideal iff any path that starts in R has all its vertices in R. The
prefix code that generates R consists of the elements of R that are maximal (within R) in the prefix
order, i.e., maximally close (along paths) to the root ε. A finitely generated right ideal R is essential
iff every infinite path eventually reaches R (and then stays in it from there on). Similarly, a finite
prefix code P is maximal iff any infinite path starting at the root eventually intersects P . For two
finitely generated right ideals R′, R with R′ ⊂ R we have: R′ is essential in R iff any infinite path
starting in R eventually reaches R′ (and then stays in it from there on).
Assume now that a total order a1 < a2 < . . . < ak has been chosen for the alphabet A; this means
that the tree of A∗ is now an oriented rooted tree, i.e., the children of each vertex v have a total order
va1 < va2 < . . . < vak. The following can be proved (see [9], Prop. 1.4(1)): Φ is an essential restriction
of ϕ iff Φ can be obtained from ϕ by starting from the table of ϕ and applying a finite number of
restriction steps of the following form: “replace (x, y) in a table by {(xa1, ya1), . . . , (xak, yak)}”.
In the tree of A∗ this means that x and y are replaced by their children xa1, . . . , xak, respectively
ya1, . . . , yak, paired according to the order on the children. One can also prove (see [9], Remark after
Prop. 1.4): Every right ideal homomorphism ϕ with table P → S has an essential restriction ϕ′ that
has a table P ′ → Q′ such that both P ′ and Q′ are prefix codes.
An important fact is the following (see [9], Prop. 1.4(2)): Every homomorphism between finitely
generated right ideals of A∗ has a unique maximal essential extension; we call it the maximum essential
extension of Φ and denote it by max(Φ).
Finally here is the definition of the Thompson-Higman monoid: Mk,1 consists of all maximum es-
sential extensions of homomorphisms between finitely generated right ideals of A∗. The multiplication
is composition followed by maximum essential extension.
One can prove the following, which implies associativity: For all right ideal homomorphisms ϕ1, ϕ2 :
max(ϕ2 ◦ ϕ1) = max(max(ϕ2) ◦ ϕ1) = max(ϕ2 ◦max(ϕ1)).
In [9] the following are proved about the Thompson-Higman monoid Mk,1:
• The Thompson-Higman group Gk,1 is the group of invertible elements of the monoid Mk,1.
• Mk,1 is finitely generated.
• The word problem of Mk,1 over any finite generating set is in P.
• The word problem of Mk,1 over a generating set Γ ∪ {τi,j : 1 ≤ i < j}, where Γ is any finite
generating set of Mk,1, is coNP-complete.
2 Boolean functions as elements of Thompson monoids
The input-output functions of digital circuits map bitstrings of some fixed length to bitstrings of a
fixed length (possibly different from the input length). In other words, circuits have input-output maps
that are total functions of the form f : {0, 1}m → {0, 1}n for some m,n > 0. The Thompson-Higman
monoid Mk,1 has an interesting submonoid that corresponds to fixed-length maps, defined as follows.
Definition 2.1 (the submonoid lepMk,1). Let ϕ : PA
∗ → QA∗ be a right-ideal homomorphism,
where P,Q ⊂ A∗ are finite prefix codes, and where P is a maximal prefix code. Then ϕ is called length
equality preserving iff for all x1, x2 ∈ Dom(ϕ) : |x1| = |x2| implies |ϕ(x1)| = |ϕ(x2)|.
The submonoid lepMk,1 of Mk,1 consists of those elements of Mk,1 that can be represented by
length-equality preserving right-ideal homomorphisms.
It is easy to check that an essential restriction of an element of lepMk,1 is again in lepMk,1, so lepMk,1
is well defined as a subset of Mk,1; moreover, one can easily check that lepMk,1 is closed under
composition, so lepMk,1 is indeed a submonoid of Mk,1.
For ϕ ∈ Mk,1 we have ϕ ∈ lepMk,1 iff there exist m > 0 and n > 0 such that Am ⊂ Dom(ϕ)
and ϕ(Am) ⊆ An. So (by means of an essential restriction, if necessary), ϕ can be represented by a
function table Am → Q ⊆ An with a fixed input length and a fixed output length (but the input and
output lengths can be different).
The motivation for studying the monoid lepMk,1 is the following. Every boolean function f :
{0, 1}m → {0, 1}n (for any m,n > 0) determines an element of lepMk,1, and conversely, this element
of lepMk,1 determines f when restricted to {0, 1}m. By considering all boolean functions as elements
of lepMk,1 we gain the ability to compose arbitrary boolean functions, even if their domain and range
“do not match”. Moreover, in lepMk,1 we are able to generate all boolean functions from gates by
using ordinary functional composition (instead of graph-based circuit lay-outs). The following remains
open:
Question: Is lepMk,1 finitely generated?
However we can find nice infinite generating sets, in connection with circuits.
Proposition 2.2 (Generators of lepMk,1). The monoid lepMk,1 has a generating set of the form
Γ ∪ {τi,i+1 : 1 ≤ i}, for some finite subset Γ ⊂ lepMk,1.
Proof. We only prove the result for k = 2; a similar reasoning works for all k (using k-ary logic).
It is a classical fact that any function f : {0, 1}m → {0, 1}n can be implemented by a combinational
circuit that uses copies of and, or, not, fork and wire-crossings. So all we need to do is to express theses
gates, at any place in the circuit, by a finite subset of lepM2,1 and by positions transpositions τi,i+1.
For each gate g ∈ {and, or} we define an element γg ∈ lepMk,1 by
γg : x1x2w ∈ {0, 1}m 7−→ g(x1, x2) w ∈ {0, 1}m−1.
Similarly we define γnot, γfork ∈ lepMk,1 by
γnot : x1w ∈ {0, 1}m 7−→ x1 w ∈ {0, 1}m,
γfork : x1w ∈ {0, 1}m 7−→ x1 x1 w ∈ {0, 1}m+1.
For each g ∈ {and, or, not, fork}, γg transforms only the first one or two boolean variables, and leaves
the other boolean variables unchanged. We also need to simulate the effect of a gate g on any variable
xi or pair of variables xixi+1, i.e., we need to construct the map
uxixi+1v ∈ {0, 1}m 7−→ u g(xi, xi+1) v ∈ {0, 1}m−1
(and similarly in case where g is not or fork). For this, we apply wire-transpositions to move xixi+1 to
the wire-positions 1 and 2, then we apply γg, then we apply more wire-transpositions in order to move
g(x1, x2) back to position i. Thus the effect of any gate anywhere in the circuit can be expressed as a
composition of γg and position transpositions in {τi,i+1 : 1 ≤ i}. ✷
Proposition 2.3 (Change of generators of lepMk,1). Let {τi,i+1 : 1 ≤ i} be denoted by τ . If
Γ,Γ′ ⊂ lepMk,1 are two finite sets such that Γ∪τ and Γ′∪τ generate lepMk,1, then the word-length over
Γ ∪ τ is linearly related to the word-length over Γ′ ∪ τ . In other words, there are constants c′ ≥ c ≥ 1
such that for all m ∈ lepMk,1 : |m|Γ∪τ ≤ c · |m|Γ′∪τ ≤ c′ · |m|Γ∪τ .
Proof. Since Γ is finite, the elements of Γ can be expressed by a finite set of words of bounded length
(≤ c) over Γ′ ∪ τ . Thus, every word of length n over Γ∪ τ is equivalent to a word of length ≤ c n over
Γ′ ∪ τ . This proves the first inequality. A similar reasoning proves the second inequality. ✷
Proposition 2.4 (Circuit size vs. lepM2,1 word-length).
Let ΓlepM2,1 ∪ {τi,j : 1 ≤ i < j} be a generating set of lepM2,1 with ΓlepM2,1 finite. Let f : {0, 1}m →
Q (⊆ {0, 1}n) be a function defining an element of lepM2,1, and let |f |lepM2,1 the word-length of f
over the generating set ΓlepM2,1 ∪ {τi,j : 1 ≤ i < j}. Let |Cf | be the circuit size of f (using any
finite universal set of gates and wire-swappings). Then |f |lepM2,1 and |Cf | are linearly related. More
precisely, for some constants c1 ≥ co ≥ 1 :
|Cf | ≤ co · |f |lepM2,1 ≤ c1 · |Cf |.
Proof. For the proof we assume that the set of gates for circuits (not counting the wire-transpositions)
is ΓlepM2,1 . If we make a different choice for the universal set of gates for circuits, and a different choice
for the finite portion ΓlepM2,1 of the generating set of lepM2,1 then the inequalities remain the same,
except for the constants c1, co.
The inequality |Cf | ≤ |f |lepM2,1 is obvious, since a word w over ΓlepM2,1 ∪ {τi,j : 1 ≤ i < j} is
automatically a circuit of size |w|.
For the other inequality, we want to simulate each gate of the circuit Cf by a word over ΓlepM2,1 ∪
{τi,j : 1 ≤ i < j}. The reasoning is the same for every gate, so let us just focus on an or gate. The
essential difference between circuit gates and elements of lepM2,1 is that in a circuit, a gate (with
2 input wires, for example) can be applied to any two wires in the circuit; on the other hand, the
functions in lepM2,1 are applied to the first few wires. However, the circuit gate or, applied to (i, i+1)
can be simulated by an element of ΓlepM2,1 and a few wire transpositions, since we have: ori,i+1(.) =
γor ◦ τ2,i+1 ◦ τ1,i(.).
The output wire of ori,i+1(.) is wire number i, whereas the output wire of γor ◦ τ2,i+1 ◦ τ1,i(.) is wire
number 1. However, instead of permuting all the wires in order to place the output of γor τ2,i+1 τ1,i(.)
on wire i, we just leave the output of γor τ2,i+1 τ1,i(.) on wire 1 for now. The simulation of the
next gate will then use appropriate transpositions τ2,j · τ1,k for fetch the correct input wires for the
next gate. Thus, each gate of Cf is simulated by one function in ΓlepM2,1 and a bounded number of
wire-transpositions in {τi,j : 1 ≤ i < j}.
At the output end of the circuit, a permutation of the n output wires is needed in order to send
the outputs to the correct wires; any permutation of n elements can be realized with < n (≤ |Cf |)
transpositions. (The inequality n ≤ |Cf | holds because since we count the output ports in the circuit
size.) ✷
Remark. The above Proposition motivates our choice of generating set of the form Γ∪{τi,j : 1 ≤ i < j}
(with Γ finite) for lepMk,1; in particular, it motivates the inclusion of all the position transpositions
τi,j in the generating set. The Proposition also motivates the definition of word-length in which τi,j
has word-length 1 for all j > i ≥ 1.
Next we will study the distortion of lepMk,1 in Mk,1. We first need some Lemmas.
Lemma 2.5 (Lemma 3.3 in [6]). If P,Q,R ⊆ A∗ are such that PA∗ ∩QA∗ = RA∗ and R is a prefix
code, then R ⊆ P ∪Q.
Proof. For any r ∈ R there are p ∈ P, q ∈ Q and v,w ∈ A∗ such that r = pv = qw. Hence p is a
prefix of q or q is a prefix of p. Let us assume p is a prefix of q = px, for some x ∈ A∗ (the other case
is similar) Hence q = px ∈ PA∗ ∩QA∗ = RA∗, and q is a prefix of r = qw. Since R is a prefix code,
r = q, hence r ∈ Q. ✷
Lemma 2.6 Let P,Q ⊂ A∗ be finite prefix codes, and let θ : PA∗ → QA∗ be a right-ideal homomor-
phism with domain PA∗ and image QA∗. Let S be a prefix code with S ⊂ QA∗. Then θ−1(S) is a
prefix code and θ−1(SA∗) = θ−1(S) A∗.
Proof. First, θ−1(S) is a prefix code. Indeed, if we had x1 = x2u for some x1, x2 ∈ θ−1(S) with u
non-empty, then θ(x1) = θ(x2) u. This would contradict the assumption that S is a prefix code.
Second, θ−1(S) ⊂ θ−1(SA∗), hence θ−1(S) A∗ ⊆ θ−1(SA∗), since θ−1(SA∗) is a right ideal. (Recall
that the inverse image of a right ideal under a right-ideal homomorphism is a right ideal.)
We also want to show that θ−1(SA∗) ⊆ θ−1(S) A∗. Let x ∈ θ−1(SA∗). So, θ(x) = sv for some
s ∈ S, v ∈ A∗, and s = qu for some q ∈ Q, u ∈ A∗. Since θ(x) = quv, we have x = puv for some
p ∈ P with θ(p) = q. Hence θ(pu) = qu = s. Therefore, x = puv with pu ∈ θ−1(s) ⊆ θ−1(S), hence
x ∈ θ−1(S) A∗. ✷
Notation: For a right-ideal homomorphism ϕ : Dom(ϕ) = PA∗ → Im(ϕ) = QA∗, where P,Q ⊂ A∗
are finite prefix codes, we define
ℓ(ϕ) = max{|z| : z ∈ P ∪Q},
For any finite prefix code C ⊂ A∗ we define
ℓ(C) = max{|z| : z ∈ C}.
Lemma 2.7 Let ϕ : Dom(ϕ) = PA∗ → Im(ϕ) = QA∗ be a right-ideal homomorphism, where P and
Q are finite prefix codes. Let R ⊂ A∗ be any finite prefix code. Then we have:
(1) ℓ(ϕ−1(R)) < ℓ(ϕ) + ℓ(R),
(2) ℓ(ϕ(R)) < ℓ(ϕ) + ℓ(R).
Proof. (1) Let r ∈ R ∩ Im(ϕ). Then every element of ϕ−1(r) has the form p1w for some p1 ∈ P
and w ∈ A∗ such that r = q1w for some q1 ∈ Q (with ϕ(p1) = q1). Hence |p1w| = |p1| + |r| − |q1| =
|r|+ |p1| − |q1|. Moreover, |r| ≤ ℓ(R) and |p1| − |q1| < ℓ(ϕ), so |p1w| < ℓ(R) + ℓ(ϕ).
(2) If r ∈ R ∩Dom(ϕ) then ϕ(r) has the form q1v for some q1 ∈ Q and v ∈ A∗ such that r = p1w
for some p1 ∈ P (with ϕ(p1) = q1). Hence |q1v| = |q1| + |r| − |p1| = |r| + |q1| − |p1|. Moreover,
|r| ≤ ℓ(R) and |q1| − |p1| < ℓ(ϕ), so |q1w| < ℓ(R) + ℓ(ϕ). ✷
For any right-ideal homomorphisms ϕi (with i = 1, . . . , N), the composite map ϕN ◦ . . . ◦ ϕ1(.) is a
right-ideal homomorphism. We say that right-ideal homomorphisms Φi (with i = 1, . . . , N) are directly
composable iff Dom(Φi+1) = Im(Φi), for i = 1, . . . , N − 1. The next Lemma shows that we can replace
composition by direct composition.
Lemma 2.8 Let ϕi : Dom(ϕi) = PiA
∗ → Im(ϕi) = QiA∗ be a right-ideal homomorphism (for
i = 1, . . . , N), where Pi and Qi are finite prefix codes. Then each ϕi has a (not necessarily essential)
restriction to a right-ideal homomorphism Φi with the following properties:
• ΦN ◦ . . . ◦ Φ1(.) = ϕN ◦ . . . ◦ ϕ1(.);
• Dom(Φi+1) = Im(Φi), for i = 1, . . . , N − 1;
• ℓ(Φi) ≤
j=1 ℓ(ϕj) for every i = 1, . . . , N .
Proof. We use induction on N . For N = 1 there is nothing to prove. So we let N > 1 and we
assume that the Lemma holds for ϕi : PiA
∗ → QiA∗ with i = 2, . . . , N , i.e., we assume that each
ϕi (for i = 2, . . . , N) has a restriction ϕ
i : P
∗ → Q′iA∗ such that ϕ′N ◦ . . . ◦ ϕ′2 = ϕN ◦ . . . ◦ ϕ2,
P ′i+1 = Q
i (for i = 2, . . . , N − 1), and ℓ(ϕ′i) ≤
j=2 ℓ(ϕj) for every i = 2, . . . , N . From P
i+1 = Q
(for i = 2, . . . , N − 1) it follows that ℓ(ϕ′N ◦ . . . ◦ ϕ′2) ≤ max{ℓ(ϕ′i) : i = 2, . . . , N} ≤
j=2 ℓ(ϕj).
Using the notation ϕ′
[N,2]
for ϕ′N ◦ . . . ◦ ϕ′2 we have Dom(ϕ′[N,2]) = P2A
∗ and Im(ϕ′
[N,2]
) = QNA
When we compose ϕ1 and ϕ
[N,2]
we obtain
ϕ−11 (Q1A
∗ ∩ P2A∗)
Φ1−→ Q1A∗ ∩ P2A∗
[N,2]−→ ϕ′
[N,2]
∗ ∩ P2A∗).
In this diagram, Φ1 is the restriction of ϕ1 to the domain ϕ
1 (Q1A
∗∩P2A∗) and image Q1A∗∩P2A∗;
and Φ′
[N,2]
is the restriction of ϕ′
[N,2]
to the domain Q1A
∗ ∩ P2A∗ and image ϕ′[N,2](Q1A
∗ ∩ P2A∗).
Hence, Φ′
[N,2]
◦Φ1 = ϕ′[N,2] ◦ϕ1, and Dom(Φ
[N,2]
) = Im(Φ1) (= Q1A
∗ ∩P2A∗). So Φ1 and Φ′[N,2] are
directly composable.
By Lemma 2.5 there is a prefix code S ⊂ A∗ such that SA∗ = Q1A∗ ∩ P2A∗ and S ⊆ Q1 ∪ P2.
Hence, ℓ(S) ≤ max{ℓ(Q1), ℓ(P2)} ≤ max{ℓ(ϕ1), ℓ(ϕ′2)} ≤ max{ℓ(ϕ1),
j=2 ℓ(ϕj)} ≤
j=1 ℓ(ϕj).
It follows also that ϕ−11 (Q1A
∗∩P2A∗) = ϕ−11 (SA∗) = ϕ
1 (S) A
∗ (the latter equality is from Lemma
2.6). Since S ⊆ Q1 ∪ P2 implies ϕ−11 (S) ⊆ ϕ
1 (Q1) ∪ ϕ
1 (P2) = P1 ∪ ϕ
1 (P2), we have ℓ(ϕ
1 (S)) ≤
max{ℓ(P1), ℓ(ϕ−11 (P2))}. Obviously, ℓ(P1) ≤ ℓ(ϕ1). Moreover, by Lemma 2.7, ℓ(ϕ
1 (P2)) ≤ ℓ(ϕ1) +
ℓ(P2). Since ℓ(P2) ≤ ℓ(ϕ′2) ≤
j=2 ℓ(ϕj) (the latter “≤” by induction), we have ℓ(ϕ
1 (S)) ≤ ℓ(ϕ1)+
j=2 ℓ(ϕj) =
j=1 ℓ(ϕj).
Since the domain code of Φ1 is ϕ
1 (S) and its image code is S, we conclude that ℓ(Φ1) ≤
j=1 ℓ(ϕj).
Let us now consider any Φ′
[i,2]
, for i = 1, . . . , N . By definition, Φ′
[i,2]
is the restriction of ϕ′i ◦ . . . ◦ϕ′2
to the domain SA∗. So the domain code of Φ′
[i,2]
is S, and we just proved that ℓ(S) ≤
j=1 ℓ(ϕj).
The image code of Φ′
[i,2]
is ϕ′i ◦ . . . ◦ ϕ′2(S). Since S ⊆ Q1 ∪ P2 we have
ϕ′i ◦ . . . ◦ ϕ′2(S) ⊆ ϕ′i ◦ . . . ◦ ϕ′2(Q1) ∪ ϕ′i ◦ . . . ◦ ϕ′2(P2) = ϕ′i ◦ . . . ◦ ϕ′2(Q1) ∪ Q′i.
Therefore: ℓ(ϕ′i ◦ . . . ◦ ϕ′2(S)) ≤ max{ℓ(ϕ′i ◦ . . . ◦ ϕ′2(Q1)), ℓ(Q′i)}.
We have ℓ(Q′i) ≤ ℓ(ϕ′i) ≤
j=2 ℓ(ϕj) (the last “≤” by induction).
By Lemma 2.7, ℓ(ϕ′i ◦ . . . ◦ ϕ′2(Q1)) ≤ ℓ(ϕ′i ◦ . . . ◦ ϕ′2) + ℓ(Q1) ≤ ℓ(ϕ′i ◦ . . . ◦ ϕ′2) + ℓ(ϕ1). And
ℓ(ϕ′i ◦ . . . ◦ ϕ′2) ≤ max{ℓ(ϕ′j) : j = 2, . . . , i}, because Dom(ϕ′r+1) = Im(ϕ′r) for all r = 2, . . . , N − 1.
And by induction, ℓ(ϕ′j) ≤
j=2 ℓ(ϕj). Hence, ℓ(ϕ
i ◦ . . . ◦ ϕ′2(Q1)) ≤
j=1 ℓ(ϕj).
Thus, ℓ(Φ′
[i,2]
j=1 ℓ(ϕj) for every i = 2, . . . , N .
Finally, we factor Φ′
[N,2]
as Φ′
[N,2]
= ΦN ◦ . . . ◦Φ2, where Φi (for i = 2, . . . , N) is defined to be the
restriction of ϕ′i to the domain ϕ
i−1 ◦ . . . ◦ ϕ′2(SA∗) (= Φ′[i−1,2](SA
∗)). Since Dom(ϕ′r+1) = Im(ϕ
(for all r = 2, . . . , N − 1), the domain of ϕ′i is equal to the image of ϕ′i−1 ◦ . . . ◦ ϕ′2. So, the domain
code of Φi is ϕ
i−1 ◦ . . . ◦ϕ′2(S), and its image code is ϕ′i ◦ϕ′i−1 ◦ . . . ◦ϕ′2(S). Since we already proved
that ℓ(ϕ′i ◦ . . . ◦ ϕ′2(S)) ≤
j=1 ℓ(ϕj) (for all i), it follows that ℓ(Φi) ≤
j=1 ℓ(ϕj). ✷
In the next theorem we show that the distortion of lepMk,1 in Mk,1 is at most quadratic (over the
generators considered so far, which include the bit position transpositions). Combined with Proposi-
tion 2.4, this means the following:
Assume circuits are built with gates that are not constrained to have fixed-length inputs and outputs,
but assume the input-output function has fixed-length inputs and outputs. Then the resulting circuits
are not much more compact than conventional circuits, built from gates that have fixed-length inputs
and outputs (we gain at most a square-root in size).
Theorem 2.9 (Distortion of lepMk,1 in Mk,1). The word-length (or Cayley graph) distortion of
lepMk,1 in Mk,1 has a quadratic upper bound; in other words, for all x ∈ lepMk,1:
|x|lepMk,1 ≤ c · (|x|Mk,1)2
where c ≥ 1 is a constant. Here the generating sets used are ΓMk,1 ∪ {τi,j : 1 ≤ i < j} for Mk,1, and
ΓlepMk,1 ∪ {τi,j : 1 ≤ i < j} for lepMk,1, where ΓMk,1 and ΓlepMk,1 are finite. By |x|Mk,1 and |x|lepMk,1
we denote the word-length of x over ΓMk,1 ∪ {τi,j : 1 ≤ i < j}, respectively ΓlepMk,1 ∪ {τi,j : 1 ≤ i < j}.
Proof. We only prove the result for k = 2; a similar proof applies for any k. We abbreviate the set
{τi,j : 1 ≤ i < j} by τ . The choice of the finite sets ΓMk,1 and ΓlepMk,1 does not matter (it only affects
the constant c in the Theorem. By Corollary 3.6 in [9] we can choose ΓMk,1 so that each γ ∈ ΓMk,1
satisfies the following (recall that ℓ(S) denotes the length of the longest words in a set S):
domC(γ) ∪ imC(γ)
≤ 2, and
∣|γ(x)| − |x|
∣ ≤ 1 for all x ∈ Dom(γ).
Let ϕ ∈ lepMk,1, and let w = αN . . . α1 be a shortest word over the generating set ΓMk,1 ∪ τ of
Mk,1, representing ϕ. So N = |ϕ|Mk,1 . We restrict each partial function αi to a partial function α′i such
that imC(α′i) = domC(α
i+1) for i = 1, . . . , N−1, according to Lemma 2.8. Hence, αN ◦ . . .◦α1(.) =
α′N ◦ . . . ◦ α′1(.), and ℓ(α′i) ≤
j=1 ℓ(αj) for every i = 1, . . . , N . Then αN ◦ . . . ◦ α1(.) is a function
{0, 1}m {0, 1}∗ → Q {0, 1}∗, representing ϕ, and we will identify αN ◦ . . . ◦ α1(.) with ϕ. It follows
that domC(α′1) = domC(ϕ) = {0, 1}m, and imC(α′N ) = imC(ϕ) = Q ⊆ {0, 1}n. More generally, it
follows that imC(α′i ◦ . . . ◦ α′1) = imC(α′i), and domC(α′N ◦ . . . ◦ α′i) = domC(α′i).
Since ℓ(α′i) ≤
j=1 ℓ(αj), and ℓ(αj) ≤ 2 for all j, we have for every i = 1, . . . , N : ℓ(α′i) ≤ 2N .
From here on we will simply denote ℓ(α′i) by ℓi. Now, we will replace each α
i ∈ Mk,1 by βi ∈
lepMk,1, such that domC(βi) = {0, 1}ℓi , and imC(βi) ⊆ {0, 1}ℓi+1 ; so βi is length-equality preserving.
This will be done by artificially lengthening those words in domC(α′i) that have length < ℓi and those
words in imC(α′i) that have length < ℓi+1. Moreover, we make βi defined on all of {0, 1}ℓi . In detail,
βi is defined as follows:
• If ℓi ≤ ℓi+1 :
βi(u z) = v z 0
ℓi+1−ℓi−|v|+|u| for all u ∈ domC(α′i), and z ∈ {0, 1}ℓi−|u|; here v = α′i(u);
βi(x) = x 0
ℓi+1−ℓi for all x 6∈ Dom(α′i), |x| = ℓi.
• If ℓi > ℓi+1 :
βi(u z1 z2) = v z1 for all u ∈ domC(α′i) and all z1, z2 ∈ {0, 1}∗ with
|z1| = ℓi+1 − |v|, |z2| = ℓi − ℓi+1 + |v| − |u|; here, v = α′i(u);
βi(x1 x2) = x1 for all x1, x2 ∈ {0, 1}∗ such that x1x2 6∈ Dom(α′i), with
|x1| = ℓi+1, |x2| = ℓi − ℓi+1.
Claim. βN ◦ . . . ◦ β1(.) = ϕ.
Proof of the Claim: We observe first that domC(β1) = domC(α
1) (= domC(ϕ) = {0, 1}m). Next,
assume by induction that for every x ∈ {0, 1}m : α′i−1 ◦ . . . ◦ α′1(x) = u is a prefix of βi−1 ◦ . . . ◦
β1(x) = u z. Then βi(u z) = v z 0
ℓi+1−ℓi−|v|+|u| (if ℓi ≤ ℓi+1); or βi(u z) = v z1 (if ℓi ≥ ℓi+1, with
|z1| = ℓi+1 − |v| and z = z1z2). In either case we find that α′i(α′i−1 ◦ . . . ◦ α′1(x)) = v is a prefix of
βi(βi−1 ◦ . . . ◦ β1(x)) = βi(u z).
Hence, when i = N we obtain for any x ∈ {0, 1}m: βN ◦ . . . ◦ β1(x) = y s is a prefix of
α′N ◦ . . . ◦ α′1(x) = ϕ(x) = y for some y and s with |y s| = ℓN = n. Since y ∈ imC(ϕ) ⊆ {0, 1}n we
conclude that s is empty, hence βN ◦ . . . ◦ β1(x) = α′N ◦ . . . ◦ α′1(x). [End, proof of Claim.]
At this point we have expressed ϕ as a product of N elements βi ∈ lepMk,1, where N = |ϕ|Mk,1 .
We now want to find the word-length of each βi over ΓlepMk,1 ∪ τ , in order to find an upper bound on
the total word-length of ϕ over ΓlepMk,1 ∪ τ . As we saw above, ℓi ≤ 2N for every i = 1, . . . , N .
We examine each generator in ΓMk,1 ∪ τ .
If αi ∈ τ then βi ∈ τ , so in this case |βi|lepMk,1 = 1.
Suppose now that αi ∈ ΓMk,1 . By Proposition 2.4 it is sufficient to construct a circuit that computes
βi; the circuit can then be immediately translated into a word over ΓlepMk,1 ∪ τ with linear increase in
length.
Since domC(αi) ⊆ {0, 1}≤2, we can restrict αi so that its domain code becomes a subset of {0, 1}2;
next, we extend αi to a map α
i that acts as the identity map on {0, 1}2 where αi was undefined. The
image code of α′′i is a subset of {0, 1}≤3. In order to compute βi we first introduce a circuit C(α′′i ) that
computes α′′i . A difficulty here is that α
i does not produce fixed-length outputs in general, whereas
C(α′′i ) has to work with fixed-length inputs and outputs; so the output of C(α
i ) represents the output
of α′′i indirectly, as follows:
The circuit C(α′′i ) has two input bits u = u1u2 ∈ {0, 1}2, and 5 output bits: First there are 3
output bits 03−|v| v ∈ {0, 1}3, where v = α′′i (u); second, there are two more output bits, c1c2 ∈ {0, 1}2,
defined by c1c2 = bin(3− |v|) (the binary representation of the non-negative integer 3− |v|). Hence,
c1c2 = 00 if |v| = 3, c1c2 = 01 if |v| = 2, c1c2 = 10 if |v| = 1; since |v| > 0, the value c1c2 = 11 will
not occur. Thus c1c2 0
3−|v| v contains the same information as v, but has the advantage of having a
fixed length (always 5). The circuit C(α′′i ) can be built with a small constant number of and, or, not,
fork gates, and we will not need to know the details.
We now build a circuit for βi.
• Circuit for βi if ℓi ≤ ℓi+1:
On input u z ∈ {0, 1}ℓi (with u ∈ {0, 1}2), we want to produce the output v z 0ℓi+1−ℓi−|v|+|u|, where
v = α′′i (u).
We first apply the circuit C(α′′i ), thus obtaining c1c2 0
3−|v| v z. Then we apply two fork operations
(always to the last bit in z) to produce c1c2 0
3−|v| v z b b, where b is the last bit of z. Applying a
negation to the first b and an and operation, we obtain c1c2 0
3−|v| v z 0. Applying ℓi+1 − ℓi − 1 more
fork operations to the last 0 yields c1c2 0
3−|v| v z 0ℓi+1−ℓi−1.
Next, we want to move 03−|v| to the right of the output, in order to obtain c1c2 v z 0
3−|v|+ℓi+1−ℓi−1.
For this effect we introduce a controlled cycle. Let κ : x1x2x3 ∈ {0, 1}3 7−→ x3x1x2 be the usual
cyclic permutations of 3 bit positions. The controlled cycle acts as the identity map when c1c2 = 00
or 11, τ1,2 when c1c2 = 01, and κ when c1c2 = 10. More precisely,
κc : c1c2 x1x2x3 ∈ {0, 1}5 7−→
c1c2 x1x2x3 if c1c2 = 00 or 11,
c1c2 x2x1x3 if c1c2 = 01,
c1c2 x3x1x2 if c1c2 = 10.
We apply ℓi copies of κc(c1, c2, ., ., .) (all controlled by the same value of c1c2) to 0
3−|v| v z. The first
κc(c1, c2, ., ., .) is applied to the 3 bits 0
3−|v| v, producing 3 bits y1y2y3; the second κc(c1, c2, ., ., .) is
applied to y2y3 and the first bit of z, producing 3 bits y
3; the third κc(c1, c2, ., ., .) is applied to
3 and the second bit of z, etc. So, each one of the ℓi copies of κc acts one bit further down than
the previous copy of κc. This will yield c1c2 v z 0
3−|v|+ℓi+1−ℓi−1. Finally, to make c1c2 disappear, we
apply two fork operations to c1, then a negation and an and, to make a 0 appear. We combine this 0
with c1 and c2 by and gates, thus transforming 0c1c2 into 0. Finally, an or operation between this 0
and the first bit of v makes this 0 disappear.
The number of gates used to compute βi is O(ℓi+1 + ℓi), which is ≤ O(N).
• Circuit for βi if ℓi > ℓi+1:
On input u z ∈ {0, 1}ℓi (with u ∈ {0, 1}2), we want to produce the output v z1, where v = α′′i (u).
We first apply the circuit C(α′′i ), which yields the output c1c2 0
3−|v| v z. Now we want to erase
the ℓi− ℓi+1+1 last bits of z. For this we apply two fork operations to the last bit of z (let’s call it b),
then a negation and an and, to make a 0 appear. We combine this 0 with the last ℓi − ℓi+1 bits of z,
using that many and gates, turning all these bits into a single 0; finally, an or operation between this 0
and the bit of the remainder of z makes this 0 disappear. At this point, the output is c1c2 0
3−|v| v Z1,
where Z1 is the prefix of length ℓi+1 − 1 of z.
Next, we apply O(ℓi+1) position transpositions to Z1 in order move the two last bits of Z1 to the
front of Z1. Let b1b2 be the last two bits of Z1; so, Z1 = z0b1b2 (where z0 is the prefix of length ℓi+1−3
of z); at this point, the output of the circuit is c1c2 0
3−|v| v b1b2 z0.
We now introduce a fixed small circuit with 7 input bits and 5 output bits, defined by the following
input-output map:
ωc : c1c2 x1x2x3 b1b2 ∈ {0, 1}7 7−→
c1c2 x1x2x3 if c1c2 = 00 or 11,
c1c2 x1x2 b1 if c1c2 = 01,
c1c2 x3 b1b2 if c1c2 = 10.
When this map is applied to c1c2 0
3−|v| v b1b2 the output is therefore given by
ωc : c1c2 0
3−|v| v b1b2 ∈ {0, 1}7 7−→
c1c2 v if |v| = 3,
c1c2 v b1 if |v| = 2,
c1c2 v b1b2 if |v| = 1.
A circuit for ωc can be built with a small fixed number of and, or, not, fork gates, and we will not need
to know the details.
After applying ωc to c1c2 0
3−|v| v b1b2 z0 the output has length ℓi+1 + 2; the “+2” comes from
c1c2. The output is c1c2 v z0, or c1c2 v b1 z0, or c1c2 v b1b2 z0, depending on whether |v| = 3, 2, or 1.
We need to move b1b2 or b1 (or nothing) back to the right-most positions of z0. We do this by
applying ℓi+1 copies of the controlled cycle κc(c1, c2, ., ., .) (all copies controlled by the same value of
c1c2). We proceed in the same way as when we used κc in the previous case, and we obtain the output
c1c2 v z0 (if |v| = 3), or c1c2 v z0 b1 (if |v| = 2), or c1c2 v z0 b1b2 (if |v| = 1).
Finally, we erase c1c2 in the same way as in the previous case, thus obtaining the final output.
The number of gates used to compute βi is O(ℓi+1 + ℓi) ≤ O(N).
This completes the constuction of a circuit for βi. Through this circuit, βi : {0, 1}ℓi → {0, 1}ℓi+1 is
expressed as a word over the generating set ΓlepMk,1 ∪ τ , of length ≤ O(ℓi+1 + ℓi) ≤ O(N).
Since we have described ϕ as a product of N = |ϕ|Mk,1 elements βi ∈ lepMk,1, each of word-length
O(N), we conclude that ϕ has word-length ≤ O(N2) over the generating set ΓlepMk,1 ∪ τ of lepMk,1.
Question: Does the distortion of lepMk,1 inMk,1 (over the generators of Theorem 2.9) have an upper
bound that is less than quadratic?
3 Wordlength asymmetry vs. computational asymmetry
Proposition 3.1 The word-length asymmetry function λ of the Thompson group lpG2,1 within the
Thompson monoid lepM2,1 is linearly equivalent to the computational asymmetry function α:
α ≃lin λ.
Here the generating set used for lepM2,1 is ΓlepM2,1 ∪ {τi,j : 0 ≤ i < j}, where ΓlepM2,1 is finite. The
gates used for circuits are any finite universal set of gates, together with the wire-swapping operations
{τi,j : 0 ≤ i < j}.
We can choose ΓlepM2,1 to consist exactly of the gates used in the circuits; then α = λ.
Proof. For any g ∈ lpG2,1 we have
C(g−1) ≤ c0 · |g−1|lepM2,1 ≤ c0 · λ(|g|lepM2,1) ≤ c0 · λ(c1 · C(g)).
The first and last “≤” come from Prop. 2.4 (since lpG2,1 ⊂ lepM2,1), and the middle “≤” comes from
the definition of λ; c0 and c1 are positive constants. Hence,
α(n) ≤ c0 · λ(c1 n) for all n.
In a very similar way we prove that λ(n) ≤ c′0 · α(c′1 n) for some positive constants c′0, c′1. ✷
Proposition 3.2 The word-length asymmetry function λM2,1 of the Thompson group lpG2,1 within
the Thompson monoid M2,1 is polynomially equivalent to the word-length asymmetry function λlepM2,1
of lpG2,1 within the Thompson monoid lepM2,1. More precisely we have for all n :
λM2,1(n) ≤ c0 · λlepM2,1(c1 n2),
λlepM2,1(n) ≤ c′0 ·
λM2,1(c
where c0, c1, c
1 are positive constants. Here the generating set used for lepM2,1 is ΓlepM2,1 ∪ {τi,j :
0 ≤ i < j}, where ΓlepM2,1 is finite. The generating set used for M2,1 is ΓM2,1 ∪ {τi,j : 0 ≤ i < j},
where ΓM2,1 is a finite generating set of M2,1.
Proof. For any g ∈ lpG2,1 we have
|g−1|M2,1 ≤ c0 · |g−1|lepM2,1 ≤ c0 · λlepM2,1(|g|lepM2,1) ≤ c0 · λlepM2,1(c1 · |g|2M2,1).
The first “≤” holds because lpG2,1 ⊂ lepM2,1 ⊂M2,1 and because of the choice of the generating sets.
The second “≤” holds by the definition of λlepM2,1 . The third “≤” comes from the quadratic distortion
of lepM2,1 in M2,1 (Theorem 2.9). For the same reasons we also have the following:
|g−1|lepM2,1 ≤ c′0 · |g−1|2M2,1 ≤ c
0 · (λM2,1(|g|M2,1))2 ≤ c′0 · (λM2,1(c1 · |g|lepM2,1))2
where c′0, c
1 are positive constants. ✷
4 Reversible representation over the Thompson groups
Theorems 4.1 and 4.2 below introduce a representation of elements of the Thompson monoid lepM2,1 by
elements of the Thompson group G2,1, in analogy with the Toffoli representation (Theorem 1.5 above),
and the Fredkin representation (Theorem 1.6 above). Our representation preserves complexity, up to a
polynomial change, and uses only one constant-0 input. Note that although the functions and circuits
considered here use fixed-length inputs and outputs, the representations is over the Thompson group
G2,1, which includes functions with variable-length inputs and outputs.
In the Theorem below, ΓG2,1 is any finite generating set of G2,1. We denote the length of a word
w by |w|, and we denote the size of a circuit C by |C|. The gates and, or, not will also be denoted
respectively by ∧,∨,¬. We distinguish between a word Wf (over a generating set of G2,1) and the
element wf of G2,1 represented by Wf .
Theorem 4.1 (Representation of boolean functions by the Thompson group). Let f :
{0, 1}m → {0, 1}n be any total function and let Cf be a minimum-size circuit (made of ∧,∨,¬, fork-
gates and wire-swappings τi,j) that computes f . Then there exists a word Wf over the generating set
ΓG2,1 ∪ {τi,i+1 : 1 ≤ i} of G2,1 such that:
• For all x ∈ {0, 1}m: wf (0x) = 0 f(x) x, where wf is the element of G2,1 represented by Wf .
• The length of the word Wf is bounded by |Wf | ≤ O(|Cf |4).
• The largest subscript of any transposition τi,i+1 occurring in Wf has an upper bound ≤ |Cf |2 + 2.
Proof. Wire-swappings in circuits are represented by the position transpositions τi,i+1 ∈ G2,1. The
gates not, or, and and of circuits are represented by the following elements of G2,1:
, ϕ∨ =
0x1x2 1x1x2
(x1 ∨ x2)x1x2 (x1 ∨ x2 )x1x2
, ϕ∧ =
0x1x2 1x1x2
(x1 ∧ x2)x1x2 (x1 ∧ x2 )x1x2
where x1, x2 range over {0, 1}. Hence the domain and image codes of ϕ∨ and ϕ∧ are all equal to
{0, 1}3.
To represent fork we use the following element, in which we recognize σ ∈ F2,1, one of the commonly
used generators of the Thompson group F2,1:
0 10 11
00 01 1
00 01 10 11
000 001 01 1
Note that σ agrees with fork only on input 0, but that is all we will need. By its very essense,
the forking operation cannot be represented by a length-equality preserving element of G2,1, because
G2,1∩ lepM2,1 = lpG2,1 (the group of length-preserving elements of G2,1). A small remark: In [6, 7, 8],
what we call “σ” here, was called “σ−1”.
We will occasionally use the wire-swapping τi,j (1 ≤ i < j); note that τi,j can be expressed in terms
of transpositions of neighboring wires as follows:
τi,j(.) = τi,i+1 τi+1,i+2 . . . τj−2,j−1 τj−1,j τj−2,j−1 . . . τi+1,i+2 τi,i+1(.)
so the word-length of τi,j over {τℓ,ℓ+1 : 1 ≤ ℓ} is ≤ 2(j − i)− 1.
For x = x1 . . . xm ∈ {0, 1}m and f(x) = y = y1 . . . yn ∈ {0, 1}n, we will construct a word Wf over
the generators ΓG2,1 ∪ {τi,i+1 : 1 ≤ i} of G2,1, such that Wf defines the map wf (.) : 0x 7→ 0 f(x) x.
The circuit Cf is partitioned into slices cℓ (ℓ = 1, . . . , L). Two gates g1 and g2 are in the same slice
iff the length of the longest path from g1 to any input port is the same as the length of the longest
path from g2 to any input port. We assume that Cf is strictly layered, i.e., each gate in slice cℓ only
has in-wires coming from slice cℓ−1, and out-wires going toward slice cℓ+1, for all ℓ. To make a circuit
C strictly layered we need to add at most |C|2 identity gates (see p. 52 in [7]). The input-output map
of slice cℓ has the form
cℓ(.) : y
(ℓ−1) = y
(ℓ−1)
1 . . . y
(ℓ−1)
nℓ−1 ∈ {0, 1}nℓ−1 7−→ y(ℓ) = y
1 . . . y
nℓ ∈ {0, 1}nℓ .
Then y(0) = x and y(L) = y, where x ∈ {0, 1}m is the input and y ∈ {0, 1}n is the output of Cf . Each
slice is a circuit of depth 1.
Before studying in more detail how Cf is built from slices, let us see how a slice is built from gates
(inductively, one gate at a time).
Let C be a depth-1 circuit with k + 1 gates, obtained by adding one gate to a depth-1 circuit K
with k gates. Let K(.) : x1 . . . xm 7−→ y1 . . . yn be the input-output map of the circuit K. Assume
by induction that K is represented by a word WK over the generating set ΓG2,1 ∪ {τi,i+1 : 1 ≤ i} of
G2,1. The input-output map of WK is, by induction hypothesis,
wK(.) : 0x1 . . . xm 7−→ 0 y1 . . . yn x1 . . . xm.
The word WC that represents C over G2,1 is obtained as follows from WK ; there are several cases,
depending on the gate that is added to K to obtain C.
Case 1: An identity-gate (or a not-gate) is added to K to form C, i.e.,
C(.) : x1 . . . xmxm+1 7−→ y1 . . . ynxm+1
(or, C(.) : x1 . . . xmxm+1 7−→ y1 . . . ynxm+1).
Then WC is given by
wC : 0x1x2 . . . xmxm+1
σ7−→ 00x1x2 . . . xmxm+1
τ3,m+37−→ 00xm+1 x2 . . . xmx1
ϕ∨7−→
xm+10xm+1 x2 . . . xmx1
τ3,m+37−→ xm+1 0x1x2 . . . xmxm+1
π7−→ 0x1x2 . . . xmxm+1xm+1
wK7−→
0 y1 . . . yn x1 . . . xmxm+1xm+1
π′7−→ 0 y1 . . . yn xm+1 x1 . . . xmxm+1 ,
where π(.) = τm+1,m+2 . . . τ2,3 τ1,2(.) shifts xm+1 from position 1 to position m+ 2, while shifting
0x1 . . . xm one position to the left; and π
′(.) = τm+2,m+3 . . . τn+m+1,n+m+2 τn+m+2,n+m+3(.) shifts
xm+1 from position n+m+ 3 to position n+ 2, while shifting x1 . . . xm one position to the right.
So, WC = π
′ WK π τ3,m+3 ϕ∨ τ3,m+3 σ, noting that functions act on the left. Thus, |WC | =
|WK |+m+n+5 if we use all of {τi,j : 1 ≤ i < j} in the generating set; over {τi,i+1 : 1 ≤ i}, τ3,m+3 has
length ≤ 2m− 1, hence |WC | ≤ 3m + n + 4. If we denote the maximum index in the transpositions
occurring in WC by JC then we have JC = max{JK , n+m+ 3}.
In case a not-gate is added (instead of an identity gate), ϕ∨ is replaced by ϕ¬ ϕ∨ in WC , and the
result is similar.
Case 2: An and-gate (or an or-gate) is added to K to form C, i.e.,
C(.) : x1 . . . xmxm+1xm+2 7−→ y1 . . . yn (xm+1 ∧ xm+2)
(or, C(.) : x1 . . . xmxm+1xm+2 7−→ y1 . . . yn (xm+1 ∨ xm+2)).
Then WC is given by
wC : 0x1x2 . . . xmxm+1xm+2
σ7−→ 00x1x2 . . . xmxm+1xm+2
τ2,m+37−→
τ3,m+47−→
0xm+1xm+2 x2 . . . xm0x1
ϕ∧7−→ (xm+1 ∧ xm+2) xm+1xm+2 x2 . . . xm0x1
τ2,m+37−→
τ3,m+47−→
(xm+1 ∧ xm+2) 0x1x2 . . . xmxm+1xm+2
π7−→ 0x1x2 . . . xm (xm+1 ∧ xm+2) xm+1xm+2
wK7−→
0 y1 . . . yn x1x2 . . . xm (xm+1 ∧ xm+2) xm+1xm+2
π′7−→
0 y1 . . . yn (xm+1 ∧ xm+2) x1x2 . . . xmxm+1xm+2 ,
where π = τm+1,m+2 . . . τ2,3 τ1,2 shifts (xm+1∧xm+2) from position 1 to positionm+2, while shifting
0x1x2 . . . xm one position to the left; and π
′ = τm+2,m+3 . . . τm+n+1,m+n+2 shifts (xm+1 ∧ xm+2)
from position n+m+ 2 to position m+ 2, while shifting x1 . . . xm one position to the right.
So, WC = π
′ WK π τ3,m+4 τ2,m+3 ϕ∧ τ3,m+4 τ2,m+3 σ, hence |WC | = |WK | + n +m + 7 if all
of {τi,j : 1 ≤ i < j} is used in the generating set; over {τi,i+1 : 1 ≤ i}, τ3,m+4 and τ2,m+3 have length
≤ 2(m+ 1)− 1, so |WC | ≤ |WK |+ 5m+ n+ 9. Moreover, JC = max{JK , m+ n+ 2}.
Case 3: A fork-gate is added to K to form C, i.e.,
C(.) : x1 . . . xmxm+1 7−→ y1 . . . yn xm+1xm+1.
Then WC is given by
wC : 0x1x2 . . . xmxm+1
σ27−→ 000x1x2 . . . xmxm+1
τ3,m+47−→ 00xm+1x1x2 . . . xm0
ϕ∨7−→
xm+10xm+1x1x2 . . . xm0
τ1,m+47−→ 00xm+1x1x2 . . . xmxm+1
ϕ∨7−→ xm+10xm+1x1x2 . . . xmxm+1
0x1x2 . . . xmxm+1xm+1xm+1
wK7−→ 0 y1 . . . yn x1x2 . . . xm xm+1xm+1xm+1
π′7−→
0 y1 . . . yn xm+1xm+1 x1x2 . . . xmxm+1 ,
where π = τm+3,m+4 . . . τ1,2 τm+3,m+4 . . . τ3,4 shifts the two copies of xm+1 at the left end from
positions 1 and 3 to positions m+ 3 and m+ 4, while shifting 0 to position 1 and shifting x1 . . . xm
two positions to the left; and π′ = τm+3,m+4 . . . τm+n+2,m+n+3 τm+2,m+3 . . . τm+n+1,m+n+2 shifts
xm+1xm+1 from positions m + n + 2 and m + n + 3 to positions m + 2 and m + 3, while shifting
x1 . . . xm two positions to the right.
So, WC = π
′ WK π ϕ∨ τ1,m+4 ϕ∨ τ3,m+4 σ
2, hence |WC | = |WK | + 2m + n + 10, if all of
{τi,j : 1 ≤ i < j} is used in the generating set; over {τi,i+1 : 1 ≤ i}, τ1,m+4 has length ≤ 2(m+3)−1 and
τ3,m+4 has length ≤ 2m−1. Hence, |WC | ≤ |WK |+6m+n+14. Moreover, JC = max{JK , m+n+3}.
In all cases, |WC | ≤ |WK |+c·(m+n+1) (for some constant c > 1), and JC ≤ max{JK , n+m+3}.
Thus, each slice cℓ, with input-output map cℓ(.) : y
(ℓ−1) 7−→ y(ℓ), is represented by a word Wcℓ with
map wcℓ(.) : 0 y
(ℓ−1) 7−→ 0 y(ℓ) y(ℓ−1), such that |Wcℓ| ≤ c · (n2ℓ−1 + n2ℓ) (for some constant c > 1),
and Jcℓ ≤ nℓ−1 + nℓ + c.
Regarding wire-crossings, we do not include them into other slices; we put the wire-crossings into
pure wire-crossing slices. So we consider two kinds of slices: Slices entirely made of wire-crossings
and identities, slices without any wire-crossings. Wire-crossings in circuits are identical to the group
elements τi,i+1.
We now construct the word Wf from the words Wcℓ (ℓ = 1, . . . , L). First observe that since the
map wcℓ(.) is a right-ideal isomorphism (being an element of G2,1), we not only have
wcℓ(.) : 0 y
(ℓ−1) 7−→ 0 y(ℓ)y(ℓ−1)
but also
wcℓ(.) : 0 y
(ℓ−1)y(ℓ−2) . . . y(1)y(0) 7−→ 0 y(ℓ)y(ℓ−1)y(ℓ−2) . . . y(1)y(0).
Then, by concatenating all Wcℓ (and by recalling that y = y
(L) and x = y(0)) we obtain
wcL wcL−1 . . . wc2 wc1(.) : 0x 7−→ 0 y y(L−1) . . . y(2) y(1) x.
Let πCf be the position permutation that shifts y right to the positions just right of x:
πCf : 0 y y
(L−1) . . . y(2) y(1) x 7−→ 0 y(L−1) . . . y(2) y(1) x y.
Observe that for (WcL−1 . . . Wc2 Wc1)
−1 we have
(wcL−1 . . . wc2 wc1)
−1(.) : 0 y(L−1) . . . y(2) y(1) x y 7−→ 0x y.
Then we have:
wcL wcL−1 . . . wc2 wc1 πCf (wcL−1 . . . wc2 wc1)
−1(.) : 0x 7−→ 0x y .
By using the position permutation πm,n : 0x y 7−→ 0 y x, we now see how to define Wf :
Wf = πm,n WcL WcL−1 . . . Wc2 Wc1 πCf (WcL−1 . . . Wc2 Wc1)
Then we have:
wf (.) : 0x 7−→ 0 y x,
where y = f(x).
Finally, we need to examine the length of the word Wf in terms of the size of the circuit Cf that
computes f : {0, 1}m → {0, 1}n.
The position permutation πm,n shifts the n = |y| letters of y to the left over the m = |x| positions
of x. So, πm,n can be written as the product of nm transpositions in {τi,i+1 : 1 ≤ i}, with maximum
subscript Jπm,n ≤ m+ n+ 1.
The position permutation πCf shifts y to the right from positions in the interval [2, n + 1] within
the string 0 y y(L−1) . . . y(2) y(1) x to positions in the interval [2 +
i=0 ni, 2 +
i=0 ni] within
the string 0 y(L−1) . . . y(2) y(1) x y. Note that
i=0 ni = |Cf | (the size of the circuit Cf ), and
nL = |y| = n, n0 = |x| = m. We shift y starting with the right-most letters of y. This takes
i=0 ni = n (|Cf |−n) transpositions in {τi,i+1 : 1 ≤ i}, with maximum subscript JπCf = |Cf |+2.
We saw already that |Wcℓ | ≤ c (n2ℓ−1 + n2ℓ), and Jcℓ ≤ nℓ−1 + nℓ + c, for some constant c > 1.
Note that
i=0 n
i ≤ (
i=0 ni)
2 = |Cf |2. Hence we have: |Wf | ≤ co |Cf |2, for some constant
co > 1. Moreover, the largest subscript in any transposition occurring in Wf is JWf ≤ |Cf |+ 2.
Recall that we assumed that our circuit Cf was strictly layered, and that the circuit size has to be
squared (at most) in order to make the circuit strictly layered. Thus, if Cf was originally not strictly
layered, our bounds become |Wf | ≤ co |Cf |4, and JWf ≤ |Cf |2 + 2. ✷
The next theorem gives a representation of a boolean permutation by an element of the Thompson
group G2,1; the main point of the theorem is the polynomial bound on the word-length in terms of
circuit size.
Theorem 4.2 (Representation of permutations by the Thompson group). Let g : {0, 1}m →
{0, 1}m be any permutation and let Cg and Cg−1 be minimum-size circuits that compute g, respectively
g−1. Then there exists a word W(g,g−1) over the generating set ΓG2,1 ∪ {τi,i+1 : 1 ≤ i} of G2,1,
representing an element w(g,g−1) ∈ G2,1 such that:
• For all x ∈ Dom(g) and all y ∈ Im(g):
w(g,g−1)(0x) = 0 g(x), and (w(g,g−1))
−1(0 y) = 0 g−1(y),
where (w(g,g−1))
−1 ∈ G2,1 is represented by the free-group inverse (W(g,g−1))−1 of the word W(g,g−1).
• w(g,g−1)(.) and (w(g,g−1))−1 stabilize both 0 {0, 1}∗ and 1 {0, 1}∗.
• We have a length upper bound |W(g,g−1)| = |(W(g,g−1))−1| ≤ O(|Cg|4 + |Cg−1 |4).
• The largest subscript of transpositions τi,i+1 occurring in W(g,g−1) is ≤ max{|Cg|2, |Cg−1 |2} +2.
Note that we distinguish between the word W(g,g−1) (over a generating set of G2,1) and the element
w(g,g−1) of G2,1 represented by W(g,g−1). Also, note that although g is length-preserving (g ∈ lpG2,1),
w(g,g−1) ∈ G2,1 is not length-preserving.
Proof. Consider the position permutation π : 0 y x 7−→ 0x y, for all x, y ∈ {0, 1}m; we express π
as a composition of ≤ m2 position transpositions of the form τi,i+1. Let Wg be the word constructed
in Theorem 4.1 for g, and let Wg−1 be the word constructed for g
−1. We define W(g,g−1) by
W(g,g−1) = (Wg−1)
−1 π Wg.
Then for all x ∈ Dom(g) we have: w(g,g−1) : 0x 7−→ 0 y, where y = g(x). More precisely, for all
x ∈ domC(g),
wg−−→ 0 g(x) x = 0 y x π−→ 0 x y = 0 g−1(y)
−−−−−−→ 0 y = 0 g(x).
Since domC(g) is a maximal prefix code, w(g,g−1) maps 0 {0, 1}∗ into 0 {0, 1}∗ (where defined).
Similarly, for all y ∈ Im(g) = Dom(g−1) we have: (w(g,g−1))−1 : 0 y 7−→ 0x, where x = g−1(y),
y = g(x). Since domC(g−1) is a maximal prefix code, (w(g,g−1))
−1 maps 0 {0, 1}∗ into 0 {0, 1}∗ (where
defined). Hence, elements of 0 {0, 1}∗ are never images of 1 {0, 1}∗. Thus, 1 {0, 1}∗ is also stabilized
by w(g,g−1) and by (w(g,g−1))
The length of the wordW(g,g−1) is bounded as follows: We have |Wg| ≤ co |Cg|4, and |(Wg−1)−1| =
|Wg−1 | ≤ co |Cg−1 |4, by Theorem 4.1. Moreover, π can be expressed as the composition of ≤ m2
(< |Cg|2) transpositions in {τi,i+1 : 1 ≤ i}.
The bound on the subscripts also follows from Theorem 4.1. ✷
5 Distortion vs. computational asymmetry
We show in this Section that the computational asymmetry function α(.) is polynomially related to a
certain distortion of the group lpG2,1.
By Theorem 4.2, for every element g ∈ lpG2,1 there is an element w(g,g−1) ∈ G2,1 which agrees with
g on 0 {0, 1}∗, and which stabilizes 0 {0, 1}∗ and 1 {0, 1}∗ . The main property of W(g,g−1) is that its
length is polynomially bounded by the circuit sizes of g and g−1; that fact will be crucial later. First
we want to study how w(g,g−1) is related to g. Recall that we distinguish between the word W(g,g−1)
(over a generating set of G2,1) and the element w(g,g−1) of G2,1 represented by W(g,g−1).
Theorem 4.2 inspires the following concepts.
Definition 5.1 Let G be a subgroup of G2,1. For any prefix codes P1, . . . , Pk ⊂ {0, 1}∗, the joint
stabilizer (in G) of the right ideals P1{0, 1}∗, . . . , Pk{0, 1}∗ is defined by
StabG(P1, . . . , Pk) =
g ∈ G : g(Pi{0, 1}∗) ⊆ Pi{0, 1}∗ for every i = 1, . . . , k
The fixator (in G) of P1{0, 1}∗ is defined by
FixG(P1) =
g ∈ G : g(x) = x for all x ∈ P1{0, 1}∗)
The fixator is also called “point-wise stabilizer”.
The following is an easy consequence of the definition: FixG(Pi) is a subgroup of G (⊆ G2,1), for
i = 1, . . . , k. If the prefix codes P1, . . . , Pk are such that the right ideals P1{0, 1}∗, . . . , Pk{0, 1}∗ are
two-by-two disjoint, and such that P1 ∪ . . . ∪ Pk is a maximal prefix code, then StabG(P1, . . . , Pk) is
closed under inverse. Hence in this case StabG(P1, . . . , Pk) is a subgroup of G.
In particular, we will consider the following groups:
• The joint stabilizer of 0 {0, 1}∗ and 1 {0, 1}∗,
StabG(0, 1) =
g ∈ G : g(0 {0, 1}∗) ⊆ 0 {0, 1}∗ and g(1 {0, 1}∗) ⊆ 1 {0, 1}∗
• The fixator of 0 {0, 1}∗,
FixG(0) = {g ∈ G : g(x) = x for all x ∈ 0 {0, 1}∗}.
• The fixator of 1 {0, 1}∗,
FixG(1) = {g ∈ G : g(x) = x for all x ∈ 1 {0, 1}∗}.
Clearly, FixG(0) and FixG(1) are subgroups of StabG(0, 1).
Lemma 5.2 (Self-embeddings of G2,1). Let G be a subgroup of G2,1. Then G is isomorphic to
FixG(1) and to FixG(0) by the following isomorphisms:
Λ0 : g ∈ G 7−→ (g)0 ∈ FixG(1)
Λ1 : g ∈ G 7−→ (g)1 ∈ FixG(0)
where (g)0 and (g)1 defined as follows for any g ∈ G2,1:
(g)0 :
0x ∈ 0 {0, 1}∗ 7−→ 0 g(x)
1x ∈ 1 {0, 1}∗ 7−→ 1x (g)1 :
1x ∈ 1 {0, 1}∗ 7−→ 1 g(x)
0x ∈ 0 {0, 1}∗ 7−→ 0x
Proof. It is straightforward to verify that Λ0 and Λ1 are injective homomorphisms. That Λ0 is onto
FixG(1) can be seen from the fact that every element of FixG(1) has a table of the form
0x1 . . . 0xn 1
0y1 . . . 0yn 1
where {x1, . . . , xn} and {y1, . . . , yn} are two maximal prefix codes, and
x1 . . . xn
y1 . . . yn
is an arbitrary
element of G. ✷
Lemma 5.3 Let G be a subgroup of G2,1. Then the direct product G×G is isomorphic to StabG(0, 1)
by the isomorphism
Λ : (f, g) ∈ G×G 7−→
0x 7→ 0 f(x), 1x 7→ 1 g(x)
∈ StabG(0, 1).
Proof. It is straightforward to verify that Λ is a homomorphism. That Λ is onto StabG(0, 1) and
injective follows from the fact that every element of StabG(0, 1) has a table of the form
0x1 . . . 0xm 1x
1 . . . 1x
0y1 . . . 0ym 1y
1 . . . 1y
where {x1, . . . , xm}, {y1, . . . , ym}, {x′1, . . . , x′n}, and {y′1, . . . , y′n}, are maximal prefix codes, and
x1 . . . xm
y1 . . . ym
x′1 . . . x
y′1 . . . y
are arbitrary elements of G (⊆ G2,1). ✷
Lemmas 5.2 and 5.3 reveal certain self-similarity properties of the Thompson group G2,1. (Self-
similarity of groups with total action on an infinite tree is an important subject, see [27]. However,
the action of G2,1 is partial, so much of the known theory does not apply directly.)
The stabilizer and the fixators above have some interesting properties.
Lemma 5.4 .
(1) For all f, g ∈ G: (f)0 (g)1 = (g)1 (f)0
(i.e., the commutator of FixG(0) and FixG(1) is the identity).
(2) FixG(0) · FixG(1) = StabG(0, 1) and FixG(0) ∩ FixG(1) = 1;
(3) StabG(0, 1) is the internal direct product of FixG(0) and FixG(1).
(This is equivalent to the combination of (1) and (2).)
(4) For all f, g ∈ G: Λ(f, g) = Λ0(f) · Λ1(g), Λ0(f) = Λ(f,1), and Λ1(g) = Λ(1, g).
Moreover, FixG(0) = Λ1(G), FixG(1) = Λ0(G), and StabG(0, 1) = Λ(G×G).
Proof. The proof is a straightforward verification. ✷
Lemma 5.5 For every position transposition τi,j, with 1 ≤ i < j, we have
(τi,j)0 = τ2,i+1 ◦ τ3,j+1◦ (τ1,2)0 ◦ τ3,j+1 ◦ τ2,i+1.
Hence, assuming (τ1,2)0 ∈ ΓG2,1 , and abbreviating {τi,j : 0 < i < j} by τ , we have:
|(τi,j)0|ΓG2,1∪τ ≤ 5.
Proof. Recall that for (τ1,2)0 we have, by definition, (τ1,2)0(1w) = 1w, and (τ1,2)0(0x2x3w) =
0x3x2w, for all w ∈ {0, 1}∗ and x2, x3 ∈ {0, 1}. The proof of the Lemma is a straightforward
verification. ✷
Now we arrive at the relation between w(g,g−1) and g.
Lemma 5.6 For all g ∈ lpG2,1 the following relation holds between g and w(g,g−1) :
w(g,g−1) · (g)−10 , (g)
0 · w(g,g−1) ∈ FixlpG2,1(0).
Equivalently,
(g)0 · FixlpG2,1(0) = w(g,g−1) · FixlpG2,1(0), and
FixlpG2,1(0) · (g)0 = FixlpG2,1(0) · w(g,g−1) .
Proof. By Theorem 4.2 we have w(g,g−1)(0x) = 0 g(x) for all x ∈ Dom(g). So, w(g,g−1) and (g)0
act in the same way on 0 {0, 1}∗ . Also, both w(g,g−1) and (g)0 map 0 {0, 1}∗ into 0 {0, 1}∗, and both
map 1 {0, 1}∗ into 1 {0, 1}∗. The Lemma follows from this. ✷
We abbreviate {τi,j : 0 < i < j} by τ . The element w(g,g−1) of G2,1, represented by the word
W(g,g−1), belongs to StablpG2,1(0, 1) as we saw in Theorem 4.2. However, the word W(g,g−1) itself is a
sequence over the generating set ΓG2,1 ∪ τ of G2,1. Therefore, in order to follow the action of W(g,g−1)
and of its prefixes we need to take Fix(0) as a subgroup of G2,1. This leads us to the Schreier left
coset graph of FixG2,1(0) within G2,1, over the generating set ΓG2,1 ∪ τ . By definition this Schreier
graph has vertex set G2,1/FixG2,1(0), i.e., the left cosets, of the form g · FixG2,1(0) with g ∈ G2,1. And
it has directed edges of the form g ·FixG2,1(0)
γ−→ γg ·FixG2,1(0) for g ∈ G2,1, γ ∈ ΓG2,1 ∪ τ . Lemma
5.6 implies that for all g ∈ lpG2,1,
(g)0 · FixG2,1(0) = w(g,g−1) · FixG2,1(0).
We assume that ΓG2,1 = Γ
, so the Schreier graph is symmetric, and hence it has a distance function
based on path length; we denote this distance by
dG/F (., .) : G2,1/FixG2,1(0)×G2,1/FixG2,1(0) −→ N.
Lemma 5.7 There are injective morphisms
g ∈ lpG2,1 →֒ g ∈ G2,1
≃−→ (g)0 ∈ FixG2,1(1)
≃−→ (g)0 · FixG2,1(0) ∈ StabG2,1(0, 1)/FixG2,1(0),
and an inclusion map
(g)0 · FixG2,1(0) ∈ StabG2,1(0, 1)/FixG2,1(0) →֒ (g)0 · FixG2,1(0) ∈ G2,1/FixG2,1(0).
In particular,
g ∈ G2,1 7−→ (g)0 · FixG2,1(0) ∈ G2,1/FixG2,1(0)
is an embedding of G2,1, as a set, into the vertex set G2,1/FixG2,1(0) of the Schreier graph.
Proof. Recall that the map Λ0 : g ∈ G2,1 7−→ (g)0 ∈ FixG2,1(1) is a bijective morphism (Lemma
5.2). Also, the map u ∈ FixG2,1(1) 7−→ u · FixG2,1(0) ∈ G2,1/FixG2,1(0) is injective; indeed, if
u · FixG2,1(0) = v · FixG2,1(0) with u, v ∈ FixG2,1(1) then v−1u ∈ FixG2,1(0) ∩ FixG2,1(1) = {1}.
The map g ∈ G2,1 7−→ (g)0 · FixG2,1(0) ∈ StabG2,1(0, 1)/FixG2,1(0) is a surjective group
homomorphism since FixG2,1(0) is a normal subgroup of StabG2,1(0, 1). Since FixG2,1(0)∩FixG(1) = {1},
this homomorphism is injective from FixG2,1(1) onto StabG2,1(0, 1)/FixG2,1(0).
The combination of these maps provides an isomorphism from G2,1 onto StabG2,1(0, 1)/FixG2,1(0).
Hence we also have an embedding of G2,1, as a set, into the vertex set G2,1/FixG2,1(0) of the Schreier
graph. ✷
Since by Lemma 5.7 we can consider G2,1 as a subset of the vertex set G2,1/FixG2,1(0) of the
Schreier graph, the path-distance dG/F (., .) on G2,1/FixG2,1(0) leads to a distance on G2,1, inherited
from dG/F (., .) :
Definition 5.8 For all g, g′ ∈ G2,1 the Schreier graph distance inherited by G2,1 is
D(g, g′) = dG/F
(g)0 · FixG2,1(0), (g′)0 · FixG2,1(0)
The comparison of the Schreier graph distance D(., .) on lpG2,1 with the word-length that lpG2,1
inherits from its embedding into lepM2,1 leads to the following distortion of lpG2,1:
Definition 5.9 In lpG2,1 we consider the distortion
∆(n) = max{D(1, g) : |g|lepM2,1 ≤ n, g ∈ lpG2,1}.
We now state and prove the main theorem relating ∆(.) and α. Recall that α(.) is the computational
asymmetry function of boolean permutations, defined in terms of circuit size.
Theorem 5.10 (Computational asymmetry vs. distortion). The computational asymmetry
function α(.) and the distortion ∆(.) of lpG2,1 are polynomially related. More precisely, for all n ∈ N :
)1/2 ≤ c′ ·∆(n) ≤ c n4 + c ·
α(c n)
where c ≥ c′ ≥ 1 are constants.
Proof. The Theorem follows immediately from Lemmas 5.11 and 5.12. ✷
Lemma 5.11. There is a constant c ≥ 1 such that for all n ∈ N : ∆(n) ≤ c n4 + c ·
α(c n)
Proof. By Lemma 5.6, (g)0 · FixG2,1(0) = w(g,g−1) · FixG2,1(0), hence
FixG2,1(0), (g)0 · FixG2,1(0)
FixG2,1(0), w(g,g−1) · FixG2,1(0)
Since the wordW(g,g−1) and the Schreier graph use the same generating set, namely ΓG2,1 ∪ τ , we have
FixG2,1(0), w(g,g−1) · FixG2,1(0)
≤ |W(g,g−1)|.
By Theorem 4.2, |W(g,g−1)| ≤ O(|Cg|4 + |Cg−1 |4). And by the definition of the computational
asymmetry function, |Cg−1 | ≤ α(|Cg |). Hence
FixG2,1(0), (g)0 · FixG2,1(0)
≤ O(|Cg|4 + |Cg−1 |4) ≤ O
|Cg|4 + α(|Cg|)4
By Proposition 2.4, |Cg| = O(|g|lepM2,1). Hence, for some constants c′′, c′ ≥ 1,
FixG2,1(0), (g)0 · FixG2,1(0)
≤ c′ · |g|4
lepM2,1
+ c′ · α(c′′ · |g|lepM2,1)4.
Thus,
FixG2,1(0), (g)0 · FixG2,1(0)
: |g|lepM2,1 ≤ n, g ∈ lpG2,1
≤ c′ n4 + c′ α(c′′ n)4.
By Definition 5.9 of the distortion function ∆ we have therefore
∆(n) ≤ c′ n4 + c′ α(c′′ n)4.
This proves the Lemma. ✷
Lemma 5.12 There is a constant c ≥ 1 such that for all n ∈ N : α(n) ≤ c ·∆(c n)2.
Proof. We first prove the following.
Claim: For every g ∈ lpG2,1, the inverse permutation g−1 can be computed by a circuit Cg−1 of size
|Cg−1 | ≤ c · d
FixG2,1(0), (g)0 · FixG2,1(0)
, for some constant c ≥ 1.
Proof of the Claim: There is a wordW ′ of length |W ′| = d
FixG2,1(0), (g)0 ·FixG2,1(0)
over ΓG2,1∪ τ
that labels a shortest path from FixG2,1(0) to (g)0·FixG2,1(0) in the Schreier graph ofG2,1/FixG2,1(0). Let
W = (W ′)−1 (the free-group inverse of W ′), so |W | = |W ′|. Let w be the element of G2,1 represented
by W . Then W labels a shortest path from FixG2,1(0) to (g
−1)0 · FixG2,1(0) in the Schreier graph of
G2,1/FixG2,1(0); this path has length |W | = |W ′| = d
FixG2,1(0), (g)0 · FixG2,1(0)
FixG2,1(0),
(g−1)0 · FixG2,1(0)
We have w · FixG2,1(0) = (g−1)0 · FixG2,1(0), thus for all x ∈ {0, 1}∗ : w(0x) = 0 g−1(x). We now
take the word VWU over the generating set ΓM2,1 ∪ τ of the monoid M2,1, where we choose the words
U and V to be U = (and, not, fork, fork), and V = (or). The functions and, not, fork, or were defined
in Subsection 1.1. Then for all x = x1 . . . xn ∈ {0, 1}∗, with x1, . . . , xn ∈ {0, 1}, we have
x1 . . . xn
fork−→ x1 x1 . . . xn
fork−→ not−→ x1 x1 x1 . . . xn
and−→ 0x1 . . . xn = 0x
W−→ 0 g−1(x) or−→ g−1(x).
The last or combines 0 and the first bit of g−1(x), and this makes 0 disappear. Thus overall,
VWU(x) = g−1(x). The length is |V WU | = |W |+ 5.
Since g−1 ∈ lpG2,1 ⊂ lepM2,1, Theorem 2.9 implies that there exists a word Z over the generators
ΓlepM2,1 ∪ τ of lepM2,1 such that
(1) |Z| ≤ c1 · |VWU |2, for some constant c1 ≥ 1, and
(2) Z represents the same element of lepM2,1 as VWU , namely g
Moreover, by Prop. 2.4, the word Z can be transformed into a circuit of size ≤ c2 · |Z| (for some
constant c2 ≥ 1). This proves that there is a circuit Cg−1 for g−1 of size |Cg−1 | ≤ c · |W |2 (for
some constant c ≥ 1). Since we saw that |W | = dG/F (FixG2,1(0), (g)0 · FixG2,1(0)), the Claim follows.
[End, Proof of the Claim.]
By definition, D(1, g) = dG/F (FixG2,1(0), (g)0 · FixG2,1(0)). Hence, by the Claim above:
|Cg−1 | ≤ c ·
D(1, g)
By Prop. 2.4 the word-length in lepM2,1 and the circuit size are linearly related; hence |g|lepM2,1 ≤
c0 |Cg|, for some constant c0 ≥ 1. Therefore,
α(n) = max{|Cg−1 | : |Cg| ≤ n, g ∈ lpG2,1}
≤ max{|Cg−1 | : |g|lepM2,1 ≤ c0 n, g ∈ lpG2,1}
≤ max
D(1, g)
: |g|lepM2,1 ≤ c0 n, g ∈ lpG2,1
≤ c ·
∆(c0 n)
This proves the Lemma. ✷
6 Other bounds and distortions
6.1 Other distortions in the Thompson groups and monoids
The next proposition gives more upper bounds on the computational asymmetry function α.
Proposition 6.1. Assume ΓlepG2,1 ⊂ ΓlepM2,1 ⊂ ΓM2,1 . Let δlpG,lepM = δ
|.|ΓlpG2,1∪τ , |.|ΓlepM2,1∪τ
be the distortion function of lpG2,1 in the Thompson monoid lepM2,1, based on word-length. Similarly,
let δlpG,M = δ
|.|ΓlpG2,1∪τ , |.|ΓM2,1∪τ
be the distortion function of lpG2,1 in the Thompson monoid
M2,1. Then for some constant c ≥ 1 and for all n ∈ N,
α(n) ≤ c · δlpG,lepM (c n) ≤ c · δlpG,M (c n).
Proof. We first prove that δlpG,lepM (n) ≤ δlpG,M (n). Recall that by definition, δlpG,lepM (n) =
max{|g|lpG2,1 : g ∈ lpG2,1, |g|lepM2,1 ≤ n}, and similarly for δlpG,M(n). Since ΓlepM2,1 ⊂ ΓM2,1 we
have |x|lepM2,1 ≤ |x|M2,1 . Hence, {|g|lpG2,1 : g ∈ lpG2,1, |g|lepM2,1 ≤ n} ⊆ {|g|lpG2,1 : g ∈ lpG2,1,
|g|M2,1 ≤ n}. By taking max over each of these two sets it follows that δlpG,lepM (n) ≤ δlpG,M(n).
Next we prove that α(n) ≤ c·δlpG,lepM (c n). For any g ∈ lpG2,1 we have C(g−1) ≤ O(|g−1|lepM2,1),
by Prop. 3.2. Moreover, |g−1|lepM2,1 ≤ |g−1|lpG2,1 since lpG2,1 is a subgroup of lepM2,1, and since the
generating set used for lpG2,1 (including all τi,j) is a subset of the generating set used for lepM2,1. For
any group with generating set closed under inverse we have |g−1|G = |g|G. And by the definition of
the distortion δlpG,lepM we have |g|lpG2,1 ≤ δlpG,lepM (|g|lepM2,1). And again, by Prop. 3.2, |g|lepM2,1 ≤
O(C(g)). Putting all this together we have
C(g−1) ≤ c1 · |g−1|lepM2,1 ≤ c1 · |g−1|lpG2,1 = c1 · |g|lpG2,1
≤ c1 · δlpG,lepM (|g|lepM2,1) ≤ c1 · δlpG,lepM (c2 C(g)).
Thus, c1 ·δlpG,lepM (c2 C(g)) is an upper bound on C(g−1). Since, by definition, α(C(g)) is the smallest
upper bound on C(g−1), it follows that α(C(g)) ≤ c1 · δlpG,lepM (c2 C(g)). ✷
Recall that in the definition 5.9 of the distortion ∆ we compared D(., .) with the word-length in
lepM2,1. If, instead, we compare D(., .) with the word-length inM2,1 we obtain the following distortion
of lpG2,1 :
δ(n) = max{D(1, g) : |g|M2,1 ≤ n, g ∈ lpG2,1}.
Proposition 6.2 The distortion functions ∆(.) and δ(.) are polynomially related. More precisely,
there are constants c′, c1, c2 ≥ 1 such that for all n ∈ N: ∆(n) ≤ c1 δ(n) ≤ c2 ∆(c′ n2).
Proof. Let’s assume first that ΓlepM2,1 ⊆ ΓM2,1 , from which it follows that |g|M2,1 ≤ |g|M2,1 . Therefore,
{D(1, g) : |g|lepM2,1 ≤ n} ⊆ {D(1, g) : |g|M2,1 ≤ n}. Hence, ∆(n) ≤ δ(n).
By Theorem 2.9, |g|lepM2,1 ≤ c · |g|2M2,1 . So, {D(1, g) : |g|M2,1 ≤ n} ⊆ {D(1, g) : |g|lepM2,1 ≤ c n
Hence, δ(n) ≤ ∆(c n2).
When we do not have ΓlepM2,1 ⊆ ΓM2,1 , the constants in the theorem change, but the statement
remains the same. ✷
6.2 Monotone boolean functions and distortion
On {0, 1}∗ we can define the product order, also called “bit-wise order”. It is a partial order (and in
fact, a lattice order), denoted by “�”, and defined as follows. First, 0 ≺ 1; next, for any u, v ∈ {0, 1}∗
we have u � v iff |u| = |v| and ui � vi for all i = 1, . . . , |u|, where ui (or vi) denotes the ith bit of u
(respectively v).
By definition, a partial function f : {0, 1}∗ → {0, 1}∗ is monotone (also called “product-order
preserving”) iff for all u, v ∈ Dom(f) : u � v implies f(u) � f(v).
The following fact is well known (see e.g., [43] Section 4.5): A function f : {0, 1}m → {0, 1}n is
monotone iff f can be computed by a combinational circuit that only uses gates of type and, or, fork,
and wire-swappings; i.e., not is absent. A circuit of this restricted type is called a monotone circuit.
Razborov [30] proved super-polynomial lower bounds for the size of monotone circuits that solve the
clique problem, and in [31] he proved super-polynomial lower bounds for the size of monotone circuits
that solve the perfect matching problem for bipartite graphs; the latter problem is in P. Tardos [37],
based on work by Alon and Boppana [1], gave an exponential lower bound for the size of monotone
circuits that solve a problem in P; see also [42] (Chapter 14 by Boppana and Sipser). Thus, there exist
problems that can be solved by polynomial-size circuits but for which monotone circuits must have
exponential size. In particular (for some constants b > 1, c > 0), there are infinitely many monotone
functions fn : {0, 1}n → {0, 1}n such that fn has a combinational circuit of size ≤ nc, but fn has no
monotone circuit of size ≤ bn.
Based on an alphabet A = {a1, . . . , ak} with a1 ≺ a2 ≺ . . . ≺ ak we define a partial function
f : A∗ → A∗ to be monotone iff f preserves the product order of A∗. The monotone functions enable
us to define the following submonoid of the Thompson-Higman monoid lepMk,1 :
monMk,1 = {ϕ ∈ lepMk,1 : ϕ can be represented by a monotone function P → Q,
where P and Q are prefix codes, with P maximal }.
An essential extension or restriction of an element of monMk,1 is again in monMk,1, so this set is
well-defined as a subset of lepMk,1. It is easily seen to be closed under composition, so monMk,1 is a
submonoid of lepMk,1.
We saw that all monotone finite functions have circuits made from gates of type and, or, fork.
Hence monM2,1 has the following generating set:
{and, or, fork} ∪ {τi,j : j > i ≥ 1}.
The results about monotone circuit size imply the following distortion result. Again, “exponential”
refers to a function with a lower bound of the form n ∈ N 7−→ exp( c
c′ n), for some constants c′ > 0
and c ≥ 1.
Proposition 6.3 Consider the monoid monM2,1 over the generating set {and, or, fork} ∪ {τi,j : j >
i ≥ 1}, and the monoid lepM2,1 over the generating set ΓlepM2,1 ∪ {τi,j : j > i ≥ 1}, where ΓlepM2,1 is
finite. Then monM2,1 has exponential word-length distortion in lepM2,1.
Proof. Let Γmon = {and, or, fork}. By Prop. 2.4 we have |f |ΓlepM2,1∪τ = |Cf |, where |Cf | denotes the
ordinary circuit size of f . By a similar argument we obtain: |f |Γmon∪τ = |monCf |, where |monCf |
denotes the monotone circuit size of f . We saw that as a consequence of the work of Razborov, Alon,
Boppana, and Tardos, there exists an infinite set of monotone functions that have polynomial-size
circuits but whose monotone circuit-size is exponential. The exponential distortion follows. ✷
Since lepM2,1 has quadratic distortion in M2,1, monM2,1 also has exponential word-length distor-
tion in M2,1.
References
[1] N. Alon, R. Boppana, “The monotone circuit complexity of boolean functions”, Combinatorica 7 (1987)
1-23.
[2] G. Arzhantseva, V. Guba, M. Sapir, “Metrics on diagram groups and uniform embeddings in a Hilbert
space”, Mathematics Arxiv (2004) http://arxiv.org/abs/math.GR/0411605.
[3] G. Arzhantseva, C. Druţu, M. Sapir, “Compression functions of uniform embeddings of groups into Hilbert
and Banach spaces”, Mathematics Arxiv (2006) http://arxiv.org/abs/math.GR/0612378
[4] C.H. Bennett, “Logical reversibility of computation”, IBM J. of Research and Development 17 (Nov. 1973)
525-532.
[5] C.H. Bennett, “Time/Space tradeoffs for reversible computation”, SIAM J. of Computing 18 (1989) 766-
[6] J.C. Birget, “The groups of Richard Thompson and complexity”, International J. of Algebra and Compu-
tation 14(5,6) (Dec. 2004) 569-626 (Mathematics ArXiv: math.GR/0204292, Apr. 2002).
[7] J.C. Birget, “Circuits, coNP-completeness, and the groups of Richard Thompson”, In-
ternational J. of Algebra and Computation 16(1) (Feb. 2006) 35-90 (Mathematics ArXiv:
http://arXiv.org/abs/math.GR/0310335, Oct. 2003).
[8] J.C. Birget, “Factorizations of the Thompson-Higman groups, and circuit complexity”, Mathematics
ArXiv: math.GR/0607349, July 2006.
[9] J.C. Birget, “Monoid generalizations of the Richard Thompson groups”, Mathematics ArXiv:
math.GR/0704.0189, 2 Apr. 2007.
[10] J. Bourgain, “On Lipschitz embedding of finite metric spaces in Hilbert space”, Israel J. of Mathematics
52 (1985) 46-52.
http://arxiv.org/abs/math.GR/0411605
http://arxiv.org/abs/math.GR/0612378
http://arxiv.org/abs/math/0204292
http://arXiv.org/abs/math.GR/0310335
http://arxiv.org/abs/math/0607349
[11] R.B. Boppana, J.C. Lagarias, “One-way functions and circuit complexity”, Information and Computation
74 (1987) 226-240.
[12] J. W. Cannon, W. J. Floyd, W. R. Parry, “Introductory notes on Richard Thompson’s groups”,
L’Enseignement Mathématique 42 (1996) 215-256.
[13] W. Diffie, M.E. Hellman, “New directions in cryptography”, IEEE Transactions in Information Theory 22
(1976) 644-655.
[14] B. Farb, “The extrinsic geometry of subgroups and the generalized word problem”, Proc. London Mathe-
matical Society (3) 68 (1994) 577-593.
[15] E. Fredkin, T. Toffoli, “Conservative logic”, International J. Theoretical Physics 21 (1982) 219-253.
[16] J. Grollman, A. Selman, “Complexity measure for public-key cryptosystems”, SIAM J. on Computing 17
(1988) 309-335.
[17] M. Gromov, “Asymptotic invariants of infinite groups”, in Geometric Group Theory (G. Niblo, M. Roller,
editors), London Mathematical Society Lecture Notes Series 182, Cambridge Univ. Press (1993).
[18] G. Higman, “Finitely presented infinite simple groups”, Notes on Pure Mathematics 8, The Australian
National University, Canberra (1974).
[19] A.P.L. Hiltgen, “Cryptographically relevant contributions to combinatorial complexity”, Dissertation,
ETH-Zürich. Hartung-Gorre Verlag, Konstanz (1994).
[20] A.P.L. Hiltgen, “Construction of feebly-one-way families of permutations”, in Advances in Cryptology –
AUSCRYPT’92, Lecture Notes in Computer Science 718 (1993) 422-434.
[21] P. Indyk, J. Matousek, “Low-distortion embeddings of finite metric spaces”, Chapter 8 in Handbook of
Discrete and Computational Geometry (J.E. Goodman and J. O’Rourke, editors), CRC Press LLC, Boca
Raton, FL; Second Edition (2004).
[22] Y. Lecerf, “Machines de Turing réversibles ...”, Comptes Rendus de l’Académie des Sciences, Paris 257
No. 18 (Oct. 1963) 2597 - 2600.
[23] O.B. Lupanov, “A method of circuit synthesis”, Izv. V.U.Z. Radiofiz. 1 (1958) 120-140.
[24] S. Margolis, J. Meakin, Z. Šuniḱ, “Distortion functions and the membership problem for submonoids of
groups and monoids”, Contemporary Mathematics, AMS, 372 (2005) 109-129.
[25] J.L. Massey, “The Difficulty with Difficulty”, IACR Distinguished Lecture delivered at EUROCRYPT ’96,
July 17, 1996, Saragossa, Spain. ( http://www.iacr.org/publications/dl/ )
[26] R. McKenzie, R.J. Thompson, “An elementary construction of unsolvable word problems in group theory”,
in Word Problems, (W. W. Boone, F. B. Cannonito, R. C. Lyndon, editors), North-Holland (1973) pp.
457-478.
[27] V. Nekrashevych, Self-similar groups, Mathematical Surveys and Monographs vol. 117 (2005), American
Mathematical Society.
[28] A.Y. Ol’shanskii, “On subgroup distortion in finitely presented groups”, Matematicheskii Sbornik 188
(1997) 51-98.
[29] A.Y. Ol’shanskii, M.V. Sapir, “Length and area functions on groups and quasi-metric Higman embedding”,
International J. of Algebra and Computation 11 (2001) 137-170.
[30] A.A. Razborov, “Lower bounds for the monotone complexity of some boolean functions”, Doklady Akademii
Nauk SSSR 281(4) (1985) 798-801. (English transl.: Soviet Mathematical Doklady 31 (1985) 354-357.)
http://www.iacr.org/publications/dl/
[31] A.A. Razborov, “Lower bounds of monotone complexity of the logical permanent function”, Matematich-
eskie Zametki 37(6) (1985) 887-900. (English transl.: Mathematical Notes of the Academy of Sciences of
the USSR 37 (1985) 485-493.)
[32] J.E. Savage, Models of Computation, Addison-Wesley (1998).
[33] E.A. Scott, “A construction which can be used to produce finitely presented infinite simple groups”, J. of
Algebra 90 (1984) 294-322.
[34] A. Selman, “A survey of one-way functions in complexity theory”, Mathematical Systems Theory 25 (1992)
203-221.
[35] C.E. Shannon, “The synthesis of two-terminal switching circuits”, Bell System Technical J. 28 (1949)
59-98.
[36] V. Shende, A. Prasad, I. Markov, J. Hayes, “Synthesis of reversible logic circuits”, IEEE Transactions on
Computer-Aided Design of Integrated Circuits and Systems 22(6) (2003) 710-722.
[37] E. Tardos, “The gap between monotone and non-monotone circuit complexity is exponential”, Combina-
torica 7(4) (1987) 141-142.
[38] Richard J. Thompson, Manuscript (1960s).
[39] R.J. Thompson, “Embeddings into finitely generated simple groups which preserve the word problem”, in
Word Problems II, (S. Adian, W. Boone, G. Higman, editors), North-Holland (1980) pp. 401-441.
[40] T. Toffoli, “Reversible computing”, MIT Laboratory for Computer Science, Technical Memo
MIT/LCS/TM-151 (1980).
[41] T. Toffoli, “Reversible computing”, Automata, Languages and Programming (7th Colloquium), Lecture
Notes in Computer Science 85 (July 1980) 623-644. (Abridged version of [40].)
[42] J. van Leeuwen (editor), Handbook of Theoretical Computer Science, volume A, MIT Press and Elsevier
(1990).
[43] I. Wegener, The complexity of boolean functions, Wiley/Teubner (1987).
Jean-Camille Birget
Dept. of Computer Science
Rutgers University at Camden
Camden, NJ 08102, USA
birget@camden.rutgers.edu
	Introduction
	 One-way functions and one-way permutations
	Computational Asymmetry
	Wordlength asymmetry
	Computational asymmetry and reversible computing
	Distortion
	Thompson-Higman groups and monoids
	Boolean functions as elements of Thompson monoids
	Wordlength asymmetry vs. computational asymmetry
	Reversible representation over the Thompson groups
	Distortion vs. computational asymmetry
	Other bounds and distortions
	Other distortions in the Thompson groups and monoids
	 Monotone boolean functions and distortion
