15111 LABEL:LastPageMar. 22, 2018Feb. 13, 2019

# The Subpower Membership Problem
for Finite Algebras with Cube Terms

Andrei Bulatova  aSchool of Computing Science
Simon Fraser University
Burnaby BC, Canada V5A 1S6<EMAIL_ADDRESS>,  Peter Mayrb  bDepartment of
Mathematics
University of Colorado
Boulder CO, USA, 80309-0395<EMAIL_ADDRESS>and
Ágnes Szendreib

###### Abstract.

The subalgebra membership problem is the problem of deciding if a given
element belongs to an algebra given by a set of generators. This is one of the
best established computational problems in algebra. We consider a variant of
this problem, which is motivated by recent progress in the Constraint
Satisfaction Problem, and is often referred to as the Subpower Membership
Problem (SMP). In the SMP we are given a set of tuples in a direct product of
algebras from a fixed finite set ${\mathcal{K}}$ of finite algebras, and are
asked whether or not a given tuple belongs to the subalgebra of the direct
product generated by a given set.

Our main result is that the subpower membership problem
$\operatorname{\text{\sc SMP}}({\mathcal{K}})$ is in $\mathsf{P}$ if
${\mathcal{K}}$ is a finite set of finite algebras with a cube term, provided
${\mathcal{K}}$ is contained in a residually small variety. We also prove that
for any finite set of finite algebras ${\mathcal{K}}$ in a variety with a cube
term, each one of the problems $\operatorname{\text{\sc SMP}}({\mathcal{K}})$,
$\operatorname{\text{\sc SMP}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$, and
finding compact representations for subpowers in ${\mathcal{K}}$, is
polynomial time reducible to any of the others, and the first two lie in
$\mathsf{NP}$.

###### Key words and phrases:

membership problem, direct products, few subpowers, cube term, residually
small variety

This material is based upon work supported by the Austrian Science Fund (FWF)
grant no. P24285, the National Science Foundation grant no. DMS 1500254, the
Hungarian National Foundation for Scientific Research (OTKA) grant no. K104251
and K115518, and an NSERC Discovery Grant.

##  1\. Introduction

The subalgebra membership problem is one of the most well established and most
thoroughly studied algorithmic problems in algebra. In this problem we are
given a (finite) set of elements, called generators, of an algebraic structure
(briefly: algebra), and we are asked to check whether or not a given element
belongs to the subalgebra generated by the generators. This question has been
studied within the general algebraic theory [18, 19, 13, 22], and it is also
an important problem in computational group theory [25, 2, 14] where it is
referred to as the subgroup membership problem. In addition to its theoretical
interest, the subalgebra membership problem for general algebraic structures
has found applications in some learning algorithms [8, 4, 15], and the
subgroup membership problem has found applications in areas such as
cryptography [23, 24].

The subgroup membership problem was the first to be studied. The celebrated
algorithm by Sims [25] decides, for any given set of permutations
$a_{1},\dots,a_{k}$ on a finite set $X$, whether or not a given permutation
$b$ belongs to the subgroup of the full symmetric group $\mathbf{S}_{X}$
generated by $a_{1},\dots,a_{k}$. This algorithm has been widely used, and a
number of improvements have been suggested [13, 17, 21]. While Sims’ algorithm
is quite efficient, Kozen [19] proved that if the group $\mathbf{S}_{X}$ is
replaced by the full transformation semigroup on $X$, the subalgebra
membership problem is $\mathrm{PSPACE}$-complete.

Kozen [18] also considered the subalgebra membership problem for infinite
algebras. Clearly, in this case the elements of the algebras in question must
be efficiently represented. The natural approach is to consider algebras that
are finitely presented by a finite set of generators and finitely many
defining relations. Kozen suggested a polynomial time algorithm for this
version of the problem.

Interest in the subalgebra membership problem has been renewed in relation to
the study of the Constraint Satisfaction Problem (CSP). Recall that in a CSP
the goal is to assign values from a certain domain to variables subject to
specified constraints. Representation of the constraints is a very important
issue in the CSP research, especially from the practical perspective, given
the wide variety of constraint types considered. Unfortunately, if we do not
restrict ourselves to a specific constraint type, choices are limited. The
standard approach in the general case (in finite domain CSPs) is to represent
constraints by constraint relations, that is, to give an explicit list of all
the allowed combinations of values. This is clearly not space efficient,
therefore more concise representations of general constraints are highly
sought.

The algebraic approach to the CSP may offer a possible method for representing
general constraints in a better way. Under this approach the constraint
relations are considered along with their _polymorphisms_ , that is,
operations on the set of values which preserve all constraint relations.
Hence, each constraint relation can be viewed as (the underlying set of) a
subalgebra of a direct power of a certain finite algebra associated to the
problem; namely, the algebra on the set of values whose operations are all
polymorphisms described above. Therefore, knowing the polymorphisms, each
constraint relation can be given by a set of generators, which is often much
smaller than the constraint relation (i.e., the generated subalgebra) itself.
In a number of cases the representation of a constraint relation by a set of
generators is exponentially more concise (in the arity of the constraint) than
listing all of its elements. This is especially valuable when the constraint
relations have high arity. But even if we are not in one of those lucky cases,
savings may be substantial.

The main difficulty with representations of this kind, however, is that
although they are very space efficient, they can be inefficient in other
aspects. For example, it is not clear whether or not it is possible to
efficiently check that a tuple belongs to a constraint relation given by
generators, but that check is unavoidable if we want to test if some mapping
is a solution to a CSP. Thus we are led to the following variation of the
subalgebra membership problem suggested by Willard [27]. Let $\mathbf{A}$ be a
finite algebra with finitely many fundamental operations. The _subpower
membership problem_ ($\operatorname{\text{\sc SMP}}$) for $\mathbf{A}$ is the
following decision problem:

$\operatorname{\text{\sc SMP}}(\mathbf{A})$:

  * •

INPUT: $a_{1},\dots,a_{k},b\in\mathbf{A}^{n}$.

  * •

QUESTION: Is $b$ in the subalgebra of $\mathbf{A}^{n}$ generated by
$\\{a_{1},\dots,a_{k}\\}$?

Observe that this problem is different from the problems studied in [13, 19],
since the finite algebra $\mathbf{A}$ is fixed and subalgebras are generated
in direct powers of $\mathbf{A}$.

A naive algorithm for solving $\operatorname{\text{\sc SMP}}(\mathbf{A})$ is
to compute and list all elements of the subalgebra $\mathbf{B}$ of
$\mathbf{A}^{n}$ generated by $\\{a_{1},\dots,a_{k}\\}$, and then check
whether $b$ is in $\mathbf{B}$. Since the size of the input
$a_{1},\ldots,a_{k},b$ is $(k+1)n$, while the best upper bound for the size of
$\mathbf{B}$ is $|A|^{n}$, and for many algebras $\mathbf{A}$, some
subalgebras $\mathbf{B}$ of $\mathbf{A}^{n}$ (say, $\mathbf{B}=\mathbf{A}^{n}$
itself) have generating sets of size $k$ bounded by a polynomial of $n$, the
time complexity of the naive algorithm is exponential. It turns out that
without further restrictions on $\mathbf{A}$, one cannot do better than the
naive algorithm: it follows from the main result of M. Kozik [20] that there
exists a finite algebra $\mathbf{A}$ such that the subpower membership problem
for $\mathbf{A}$ is EXPTIME-complete.

In contrast, for finite algebras $\mathbf{A}$ in many familiar classes, the
subpower membership problem is in $\mathsf{P}$, that is, there is a polynomial
time algorithm for solving the problem. For example, if $\mathbf{A}$ is a
group, then a variant of Sims’ algorithm (cf. [13]) solves the problem in
polynomial time. Other simple algorithms work if $\mathbf{A}$ is a finite
lattice or a finite lattice with additional operations (use the Baker–Pixley
Theorem [1]) or if $\mathbf{A}$ is a finite semilattice. A recent result of A.
Bulatov, M. Kozik, P. Mayr, and M. Steindl [6] extends this observation on
semilattices to any finite commutative semigroup $\mathbf{A}$ by showing that
if $\mathbf{A}$ embeds into a direct product of a Clifford semigroup and a
nilpotent semigroup, then the subpower membership problem for $\mathbf{A}$ is
in $\mathsf{P}$, and for all other finite commutative semigroups $\mathbf{A}$
the problem is $\mathsf{NP}$-complete.

Extending the result on groups mentioned earlier R. Willard [27] proved that
the subpower membership problem is in $\mathsf{P}$ for every finite algebra
$\mathbf{A}$ that is an expansion of a group by multilinear operations. In
particular, this is the case for every finite ring, finite module, and finite
$K$-algebra. It is not known whether this statement remains true if the word
‘multilinear’ is omitted.

Returning to the CSP motivation of the subpower membership problem, the case
in which representing constraint relations by generators is the most
advantageous, is when the finite algebra $\mathbf{A}$ associated to the CSP
has the property that all subalgebras of finite powers $\mathbf{A}^{n}$ of
$\mathbf{A}$ admit small generating sets; here ‘small’ means that the size is
bounded by $p(n)$ for some polynomial $p$ depending only on $\mathbf{A}$.
These algebras have been intensively studied within the theory of constraint
satisfaction problems, and constitute one of the two known major classes of
CSPs for which general polynomial time algorithms were found several years ago
[5, 15]. It was proved in [3] that a finite algebra $\mathbf{A}$ has the
aforementioned property on small generating sets for subalgebras of powers if
and only if $\mathbf{A}$ _has few subpowers_ in the following sense: there is
a polynomial $q$ depending only on $\mathbf{A}$ such that $\mathbf{A}^{n}$ has
at most $2^{q(n)}$ subalgebras. This number is indeed ‘small’, as there exist
finite algebras $\mathbf{A}$ (e.g., semilattices or unary algebras) for which
the number of subalgebras of $\mathbf{A}^{n}$ is doubly exponential in $n$.

Algebras with few subpowers were also characterized in [3] by the existence of
a _cube term_ (to be defined in Section 2.2). Cube terms generalize _Mal’tsev
terms_ and _near unanimity terms_ , which have been studied in algebra since
the 60’s and 70’s, and more recently have played significant roles in
isolating important properties of constraints in CSPs.

The principal research problem addressed in this paper is the following.

Question 1 [15]. Is the subpower membership problem for $\mathbf{A}$ in
$\mathsf{P}$ if $\mathbf{A}$ is a finite algebra with a cube term?

The answer is known to be ‘yes’ if $\mathbf{A}$ has a near unanimity term (by
the Baker–Pixley Theorem [1]), and the answer is not known in general, if
$\mathbf{A}$ has a Mal’tsev term; in fact, as we mentioned earlier, the answer
is not known even if $\mathbf{A}$ is a finite group expanded by further
operations. We will now briefly discuss what the main difficulty seems to be.

Recall from [3] that if a finite algebra $\mathbf{A}$ has a cube term, then
for every subalgebra $\mathbf{B}$ of any finite power $\mathbf{A}^{n}$ of
$\mathbf{A}$ _there exists_ a sort of canonical set of generators, called a
_compact representation_ in [5, 3, 15] or a _frame_ in [10]. Compact
representations played a crucial role in the CSP applications of finite
algebras $\mathbf{A}$ with cube terms (see [15]). For the subpower membership
problem $\operatorname{\text{\sc SMP}}(\mathbf{A})$, a natural approach to
answering the question “Is $b$ in the subalgebra $\mathbf{B}$ of
$\mathbf{A}^{n}$ generated by $a_{1},\dots,a_{k}$?” would be to first find a
compact representation for $\mathbf{B}$, and then use it to answer the
question. The main components of a compact representation for $\mathbf{B}$ are
_witnesses for forks._ For a coordinate position $i\in\\{1,\dots,n\\}$ and for
two elements $c,d\in A$, the tuples $(c_{1},\dots,c_{n}),(d_{1},\dots,d_{n})$
in $\mathbf{B}$ are said to witness that the pair $(c,d)$ is a fork in
$\mathbf{B}$ in position $i$ if $c_{1}=d_{1},\dots,c_{i-1}=d_{i-1}$ and
$c_{i}=c,d_{i}=d$. It turns out (see, e.g., Theorem 23 and the paragraph
preceding Lemma 18) that in order to give a positive answer to Question 1 it
would be sufficient to be able to decide in polynomial time — using only the
specified generators $a_{1},\dots,a_{k}$ — whether or not a given pair
$(c,d)\in A^{2}$ is a fork in $\mathbf{B}$ in a given position $i$ (and if it
is, find witnesses for it in $\mathbf{B}$). This, however, appears to be a
significant problem; cf. Theorems 19, 20, and 23.

Question 1 will remain unresolved in this paper, but we will prove (see
Theorem 28) that the answer to Question 1 is YES in an important special case,
namely when $\mathbf{A}$ belongs to a residually small variety (to be defined
in Section 2.3). For a finite algebra $\mathbf{A}$ with a cube term this
condition is equivalent to the requirement that there exists a natural number
$c$ such that every algebra in the variety generated by $\mathbf{A}$ is a
subalgebra of a product of algebras of size less than $c$. For example, a
finite algebra $\mathbf{A}$ belongs to a residually small variety if it is a
lattice, a module, a group with abelian Sylow subgroups, or a commutative ring
with $1$ whose Jacobson radical $J$ satisfies $J^{2}=0$. Although subpower
membership for all finite groups, rings and lattices is already known to be
tractable by various algorithms, we give a new unified approach that can
handle all of them and also more general algebras in residually small
varieties. So our algorithm is a first step towards finding a polynomial time
algorithm for all algebras with a cube term.

The proof of Theorem 28 does not use compact representations; rather, it
relies on a structure theorem proved in [16] for the subalgebras of finite
powers of an algebra $\mathbf{A}$ with a cube term (or equivalently,
parallelogram term). The application of this structure theorem leads us to
considering subalgebras of finite products
$\mathbf{S}_{1}\times\dots\times\mathbf{S}_{n}$ where the factors
$\mathbf{S}_{1},\dots,\mathbf{S}_{n}$ come from the finite collection
$\mathbb{H}\mathbb{S}\mathbf{A}$ of homomorphic images of subalgebras of
$\mathbf{A}$. As a consequence, it is natural for us to expand the scope of
the subpower membership problem, and define it for any finite set
${\mathcal{K}}$ of finite algebras as follows:

$\operatorname{\text{\sc SMP}}({\mathcal{K}})$:

  * •

INPUT: $a_{1},\dots,a_{k},b\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
with $\mathbf{A}_{1},\ldots,\mathbf{A}_{n}\in{\mathcal{K}}$.

  * •

QUESTION: Is $b$ in the subalgebra of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ generated by
$\\{a_{1},\dots,a_{k}\\}$?

There is an important issue, which is raised by our passage from
$\operatorname{\text{\sc SMP}}(\mathbf{A})$ to $\operatorname{\text{\sc
SMP}}(\mathbb{H}\mathbb{S}\mathbf{A})$: Does the subpower membership problem
get harder when $\mathbf{A}$ is replaced by the set $\mathbb{S}\mathbf{A}$ of
all its subalgebras or by the set $\mathbb{H}\mathbf{A}$ of all its
homomorphic images? It is easy to see that for any finite algebra
$\mathbf{A}$, $\operatorname{\text{\sc SMP}}(\mathbf{A})$ and
$\operatorname{\text{\sc SMP}}(\mathbb{S}\mathbf{A})$ are essentially the same
problem. However, this is not the case for homomorphic images. A surprising
result of M. Steindl [26] shows that there exists a $10$-element semigroup
$\mathbf{S}$ with a $9$-element quotient semigroup $\overline{\mathbf{S}}$
such that $\operatorname{\text{\sc SMP}}(\mathbf{S})$ is in $\mathsf{P}$ while
$\operatorname{\text{\sc SMP}}(\overline{\mathbf{S}})$ is
$\mathsf{NP}$-complete. This shows that the problem $\operatorname{\text{\sc
SMP}}(\mathbb{H}\mathbb{S}\mathbf{A})$ may be harder than
$\operatorname{\text{\sc SMP}}(\mathbf{A})$ (provided
$\mathsf{P}\not=\mathsf{NP}$), and therefore poses the following question for
us:

Question 2. Are the problems $\operatorname{\text{\sc SMP}}({\mathcal{K}})$
and $\operatorname{\text{\sc SMP}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$
polynomial time equivalent if ${\mathcal{K}}$ is a finite set of finite
algebras in a variety with a cube term?

We will prove (see Theorem 17) that the answer to Question 2 is YES. The proof
uses the techniques of compact representations mentioned above. We will also
show that, given a finite set of finite algebras ${\mathcal{K}}$ in a variety
with a cube term, the subpower membership problem $\operatorname{\text{\sc
SMP}}({\mathcal{K}})$ and the problem of finding compact representations for
subalgebras of products of algebras in ${\mathcal{K}}$ are polynomial time
reducible to each other (Theorem 23), and the two problems are in
$\mathsf{NP}$ and $\mathsf{FP}^{\mathsf{NP}}$, respectively (Theorems 20 and
23).

Our results also yield new information on another problem that is closely
related to $\operatorname{\text{\sc SMP}}$, namely the subpower intersection
problem for a finite set ${\mathcal{K}}$ of finite algebras which is defined
as follows:

$\operatorname{\text{\sc SIP}}({\mathcal{K}})$:

  * •

INPUT:
$a_{1},\dots,a_{k},b_{1},\ldots,b_{\ell}\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
with $\mathbf{A}_{1},\ldots,\mathbf{A}_{n}\in{\mathcal{K}}$.

  * •

OUTPUT: Generators for the intersection of the subalgebras of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ generated by
$\\{a_{1},\dots,a_{k}\\}$ and by $\\{b_{1},\ldots,b_{\ell}\\}$.

Assume ${\mathcal{K}}$ is a finite set of finite algebras in a variety with a
cube term. Then it turns out that $\operatorname{\text{\sc
SIP}}({\mathcal{K}})$ has a polynomial time reduction to
$\operatorname{\text{\sc SMP}}({\mathcal{K}})$. Indeed, given compact
representations for two subalgebras $\mathbf{B}$, $\mathbf{C}$ of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ with
$\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{K}}$, Dalmau’s algorithm [15]
yields a compact representation for $\mathbf{B}\cap\mathbf{C}$ in polynomial
time. Hence $\operatorname{\text{\sc SIP}}({\mathcal{K}})$ reduces to finding
compact representations, which is polynomial time equivalent to
$\operatorname{\text{\sc SMP}}({\mathcal{K}})$ (Theorem 23). For the converse,
we do not know whether $\operatorname{\text{\sc SMP}}({\mathcal{K}})$ reduces
to $\operatorname{\text{\sc SIP}}({\mathcal{K}})$ in general. However, it
clearly does for idempotent algebras because for any elements
$a_{1},\dots,a_{k},b$ in $\mathbf{A}_{1}\times\dots\times\mathbf{A}_{k}$, the
subalgebra generated by $\\{a_{1},\dots,a_{k}\\}$ contains $b$ if and only if
that subalgebra has a nonempty intersection with $\\{b\\}$, the subalgebra
generated by $b$. Hence for a finite set of finite algebras ${\mathcal{K}}$ in
an idempotent variety with a cube term the problems $\operatorname{\text{\sc
SMP}}({\mathcal{K}})$, $\operatorname{\text{\sc SIP}}({\mathcal{K}})$, and
finding compact representations are all polynomial time reducible to each
other.

##  2\. Preliminaries

In this section we summarize the concepts and facts from universal algebra
that will be used throughout the paper. For more details the reader is
referred to [7].

For every natural number $m$, we will use the notation $[m]$ for the set
$\\{1,2,\dots,m\\}$. The collection of all $k$-element subsets of a set $S$
will be denoted by $\binom{S}{k}$.

###  2.1. Algebras and varieties

An _algebraic language_ is a set $F$ of function symbols, together with a
mapping $F\to\\{0,1,\dots\\}$ which assigns an _arity_ $k_{f}$ to every symbol
$f\in F$. An _algebraic structure_ (or briefly _algebra_) _in the language
$F$_ is a pair $\mathbf{A}=(A,F^{\mathbf{A}})$ where $A$ is a nonempty set,
called the _universe_ of $\mathbf{A}$, and $F^{\mathbf{A}}$ is a set of
operations $f^{\mathbf{A}}\colon A^{k_{f}}\to A$ on $A$, indexed by elements
of $F$, called the _(basic) operations_ of $\mathbf{A}$. We will say that
$\mathbf{A}=(A;F^{\mathbf{A}})$ is a _finite algebra_ if $A$ is finite, and
$\mathbf{A}$ has a _finite language_ if $F$ is finite.

Let $\mathbf{A}$ be an algebra in the language $F$. If $t$ is a _term_ in the
language $F$ (as defined in first order logic), we will write
$t(x_{1},\dots,x_{n})$ to indicate that all variables occurring in $t$ are
among $x_{1},\dots,x_{n}$ (but some of the variables $x_{1},\dots,x_{n}$ may
not occur in $t$). We may refer to a term $t(x_{1},\dots,x_{n})$ as an _$n$
-ary term_. Each such term $t$ induces an $n$-ary _term operation_
$t^{\mathbf{A}}\colon A^{n}\to A$ of $\mathbf{A}$. Thus, the term operations
of $\mathbf{A}$ are exactly those operations that can be obtained from the
basic operations of $\mathbf{A}$ and from projection operations by
composition. A function $g\colon A^{n}\to A$ is called an $n$-ary _polynomial
operation_ of $\mathbf{A}$ if it has the form
$g(x_{1},\dots,x_{n})=t^{\mathbf{A}}(x_{1},\dots,x_{n},c_{1},\dots,c_{k})$ for
some $(n+k)$-ary term operation $t^{\mathbf{A}}$ and some elements
$c_{1},\dots,c_{k}$ of $\mathbf{A}$.

As in the last two paragraphs, algebras will usually be denoted by boldface
letters, and their universes by the same letters in italics. However, we will
omit the superscript $\mathbf{A}$ from $F^{\mathbf{A}}$, $f^{\mathbf{A}}$, and
$t^{\mathbf{A}}$ whenever there is no danger of confusion.

Terms in a language $F$ encode all computations that are possible in any
algebra $\mathbf{A}$ of the language $F$. Since we are interested in the
complexity of certain computations, we will now discuss what measure of
complexity we will use for terms. Assuming that the language $F$ is finite,
and hence there is a constant bound on the arities of all symbols in $F$, the
complexity of a term $t$ can be captured by the number of function symbols in
$t$, or equivalently, by the number of nodes in the term tree of $t$. This
number will be referred to as _the length of $t$_. If such a term $t$ is
short, say, is polynomially long in some parameter, then it can be efficiently
evaluated in the straightforward way in any algebra, for any given input.
However, even if the term itself is long, it may admit a more concise
representation by an _$F$ -circuit_, i.e., a circuit with gates whose types
correspond to the symbols in $F$. Note that a circuit may evaluate identical
subterms of $t$ only once, and pass on the value to several gates in the
circuit. This is why we will consider the number of gates in such a circuit to
measure the amount of computation needed to evaluate $t$, which may be
exponentially smaller than the length of $t$. More formally, let
$\mathsf{Circ}_{F}(t)$ denote a minimal $F$-circuit representing $t$, that is,
no two gates compute identical subterms. We define the _size of
$\mathsf{Circ}_{F}(t)$_ to be the number of gates in $\mathsf{Circ}_{F}(t)$,
and will use this number to measure the time needed to evaluate $t$. For
$F=\\{f\\}$ a singleton, we also abbreviate $\\{f\\}$-circuit to $f$-circuit.
Further we will omit the reference to $F$ and write $\mathsf{Circ}(t)$ when
the set of gate types is clear from context.

Let $\mathbf{A},\mathbf{B}$, and $\mathbf{A}_{j}$ ($j\in J$) be algebras in
the same language $F$. A mapping $\varphi\colon A\to B$ is said to be a
_homomorphism_ $\varphi\colon\mathbf{A}\to\mathbf{B}$ if

$\varphi(f^{\mathbf{A}}(a_{1},\dots,a_{k_{f}}))=f^{\mathbf{B}}(\varphi(a_{1}),\dots,\varphi(a_{k_{f}}))\quad\text{for
all $f\in F$ and $a_{1},\dots,a_{k_{f}}\in A$.}$

An invertible (i.e., bijective) homomorphism is called an _isomorphism_. We
say that $\mathbf{B}$ is a _homomorphic image_ of $\mathbf{A}$ if there exists
an onto homomorphism $\mathbf{A}\to\mathbf{B}$. Furthermore, we say that
$\mathbf{B}$ is a _subalgebra_ of $\mathbf{A}$, and write
$\mathbf{B}\leq\mathbf{A}$, if $B\subseteq A$ and the inclusion map $B\to A$
is a homomorphism $\mathbf{B}\to\mathbf{A}$; equivalently, $\mathbf{B}$ is a
subalgebra of $\mathbf{A}$ iff $B\subseteq A$ and $f^{\mathbf{B}}$ is the
restriction of $f^{\mathbf{A}}$ to the set $B$ for all $f\in F$. The _direct
product_ $\prod_{j\in J}\mathbf{A_{j}}$ of the algebras $\mathbf{A}_{j}$
($j\in J$) is the unique algebra $\mathbf{A}$ with universe $A:=\prod_{j\in
J}A_{j}$ for which all projection maps $\operatorname{proj}_{\ell}\colon A\to
A_{\ell}$, $(a_{j})_{j\in J}\mapsto a_{\ell}$ ($\ell\in J$) are homomorphisms;
equivalently, $\mathbf{A}$ is the direct product of the algebras
$\mathbf{A}_{j}$ ($j\in J$) iff $\mathbf{A}$ has universe $A:=\prod_{j\in
J}A_{j}$, and its operations $f^{\mathbf{A}}$ act coordinatewise, via
$f^{\mathbf{A}_{j}}$ in coordinate $j\in J$, for all $f\in F$. A subalgebra
$\mathbf{B}$ of a direct product $\prod_{j\in J}\mathbf{A}_{j}$ will be called
a _subdirect subalgebra_ if $\operatorname{proj}_{\ell}(B)=A_{\ell}$ for every
$\ell\in J$.

A _congruence_ of $\mathbf{A}$ is the kernel of a homomorphism with domain
$\mathbf{A}$; equivalently, a congruence of $\mathbf{A}$ is an equivalence
relation on $A$ that is invariant under the operations of $\mathbf{A}$. If
$\vartheta$ is a congruence of $\mathbf{A}$, then there is a unique algebra,
denoted $\mathbf{A}/\vartheta$, whose universe is the set $A/\vartheta$ of
equivalence classes of $\vartheta$, and whose operations are defined so that
the natural map $\nu\colon A\to A/\vartheta$, $a\mapsto a/\vartheta$ is a
homomorphism $\mathbf{A}\to\mathbf{A}/\vartheta$. Here $a/\vartheta$ denotes
the equivalence class of $\vartheta$ containing $a$. The algebra
$\mathbf{A}/\vartheta$ is called a _quotient algebra_ of $\mathbf{A}$. By the
first isomorphism theorem ([7, Theorem II.6.12]), if
$\varphi\colon\mathbf{A}\to\mathbf{B}$ is an onto homomorphism with kernel
$\vartheta$, then $\mathbf{B}$ is isomorphic to $\mathbf{A}/\vartheta$.

For any algebra $\mathbf{A}$, the congruences of $\mathbf{A}$ form a lattice
with respect to inclusion, which is called the _congruence lattice_ of
$\mathbf{A}$, and is denoted by $\operatorname{Con}(\mathbf{A})$. The _meet_
operation $\wedge$ of $\operatorname{Con}(\mathbf{A})$ is simply the set-
theoretic intersection of congruences, and the _join_ operation $\vee$ is the
transitive closure of the union of congruences. The top and bottom elements of
$\operatorname{Con}(\mathbf{A})$ are denoted $1$ and $0$, respectively. For
$\alpha,\beta\in\operatorname{Con}(\mathbf{A})$ with $\alpha\leq\beta$ we
define the _interval_ ${[\\![}\,{\alpha},{\beta}\,{]\\!]}$ by
${[\\![}\,{\alpha},{\beta}\,{]\\!]}:=\\{\gamma\in\operatorname{Con}(\mathbf{A}):\alpha\leq\gamma\leq\beta\\}$.

A congruence $\vartheta\in\operatorname{Con}(\mathbf{A})$ is said to be
_completely meet irreducible_ if for any family $\\{\vartheta_{j}:j\in J\\}$
of congruences of $\mathbf{A}$, $\vartheta=\bigwedge_{j\in J}\vartheta_{j}$
implies that $\vartheta=\vartheta_{j}$ for some $j\in J$. If $\vartheta$ is
completely meet irreducible and $\vartheta\not=1$, then $\vartheta$ has a
unique _upper cover_ $\vartheta^{+}$ in $\operatorname{Con}(\mathbf{A})$, that
is, there is a unique congruence
$\vartheta^{+}\in\operatorname{Con}(\mathbf{A})$ such that
$\vartheta<\vartheta^{+}$ and
${[\\![}\,{\vartheta},{\vartheta^{+}}\,{]\\!]}=\\{\vartheta,\vartheta^{+}\\}$.
We will use the notation $\operatorname{Irr}(\mathbf{A})$ for the set of all
completely meet irreducible congruences of $\mathbf{A}$, excluding $1$. An
algebra $\mathbf{A}$ is said to be _subdirectly irreducible_ if $0\,(\not=1)$
is completely meet irreducible in $\operatorname{Con}(\mathbf{A})$. In this
case the unique minimal non-trivial congruence $0^{+}$ is called the
_monolith_ of $\mathbf{A}$. It follows from the second isomorphism theorem
([7, Theorem II.6.15]) that the subdirectly irreducible quotients of
$\mathbf{A}$ are exactly the algebras $\mathbf{A}/\sigma$,
$\sigma\in\operatorname{Irr}(\mathbf{A})$.

Let $\vartheta$ be a congruence of an algebra $\mathbf{A}$. We will often
write $a\equiv_{\vartheta}b$ instead of $(a,b)\in\vartheta$. If $\mathbf{B}$
is a subalgebra of $\mathbf{A}$, we will say that $\mathbf{B}$ is _saturated
with respect to $\vartheta$_, or $\mathbf{B}$ is a _$\vartheta$ -saturated
subalgebra_ of $\mathbf{A}$, if $b\in B$ and $b\equiv_{\vartheta}a$ imply
$a\in B$ for all $a\in A$. In other words, $\mathbf{B}$ is
$\vartheta$-saturated if and only if its universe is a union of
$\vartheta$-classes of $\mathbf{A}$. For an arbitrary subalgebra $\mathbf{B}$
of $\mathbf{A}$ there exists a smallest $\vartheta$-saturated subalgebra of
$\mathbf{A}$ that contains $\mathbf{B}$, which we denote by
$\mathbf{B}[\vartheta]$; the universe of $\mathbf{B}[\vartheta]$ is
$B[\vartheta]:=\bigcup_{b\in B}b/\vartheta$. Denoting the restrictions of
$\vartheta$ to $\mathbf{B}$ and $\mathbf{B}[\vartheta]$ by
$\vartheta_{\mathbf{B}}$ and $\vartheta_{\mathbf{B}[\vartheta]}$,
respectively, we have by the third isomorphism theorem ([7, Theorem II.6.18])
that the map
$\mathbf{B}/\vartheta_{\mathbf{B}}\to\mathbf{B}[\vartheta]/\vartheta_{\mathbf{B}[\vartheta]}$,
$b/\vartheta_{\mathbf{B}}\mapsto
b/\vartheta_{\mathbf{B}[\vartheta]}(=b/\vartheta)$ is an isomorphism.

For a product $\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ of algebras and
for any set $I\subseteq[n]$, the projection homomorphism

$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}=\prod_{i\in[n]}\mathbf{A}_{i}\to\prod_{i\in
I}\mathbf{A}_{i},\qquad(a_{i})_{i\in[n]}\mapsto(a_{i})_{i\in I}$

will be denoted by $\operatorname{proj}_{I}$. For a subalgebra $\mathbf{B}$ or
for an element $b$ of $\prod_{i\in[n]}\mathbf{A}_{i}$, we will write
$\mathbf{B}|_{I}$ or $b|_{I}$ for $\operatorname{proj}_{I}(\mathbf{B})$ or
$\operatorname{proj}_{I}(b)$, respectively. If $I=\\{j_{1},\dots,j_{k}\\}$,
then the notation $|_{\\{j_{1},\dots,j_{k}\\}}$ will be simplified to
$|_{j_{1},\dots,j_{k}}$.

For any class ${\mathcal{K}}$ of algebras in the same language,
$\mathbb{H}{\mathcal{K}}$, $\mathbb{S}{\mathcal{K}}$, and
$\mathbb{P}{\mathcal{K}}$ denote the classes of all homomorphic images,
subalgebras, and direct products of members of ${\mathcal{K}}$, respectively.

A _variety_ is a class of algebras in the same language that is closed under
taking direct products, subalgebras, and homomorphic images. By Tarski’s
Theorem ([7, Theorem II.9.5]), the smallest variety containing a class
${\mathcal{K}}$ of algebras in the same language equals
$\mathbb{H}\mathbb{S}\mathbb{P}{\mathcal{K}}$. Birkhoff’s Theorem ([7, Theorem
11.9]) characterizes varieties as classes of algebras defined by identities.
In more detail, an _identity_ in a language $F$ is an expression of the form
$s(x_{1},\dots,x_{n})=t(x_{1},\dots,x_{n})$ where $s(x_{1},\dots,x_{n})$ and
$t(x_{1},\dots,x_{n})$ are terms in the language $F$. An algebra $\mathbf{A}$
in the language $F$ _satisfies an identity_
$s(x_{1},\dots,x_{n})=t(x_{1},\dots,x_{n})$ if the $n$-ary term operations
$s^{\mathbf{A}}$ and $t^{\mathbf{A}}$ are equal. Birkhoff’s Theorem is the
statement that for a fixed language, a class ${\mathcal{V}}$ of algebras is a
variety if and only if there exists a set $\Sigma$ of identities such that an
algebra lies in ${\mathcal{V}}$ if and only if it satisfies the identities in
$\Sigma$.

Occasionally, when we want to describe sets of identities where the identities
have a similar form, it will be convenient to represent the identities in
matrix form as follows. For any class ${\mathcal{K}}$ of algebras in the same
language, and for any term $t=t(x_{1},\dots,x_{n})$, if $M$ is an $m\times n$
matrix of variables and $\vec{v}$ is an $m\times 1$ matrix of variables,

${\mathcal{K}}\models t(M)=\vec{v}$ (1)

will denote that the $m$ identities represented by the rows in (1) are true in
${\mathcal{K}}$. For example,

${\mathcal{K}}\models t\left(\begin{matrix}x&x&y\\\
y&x&x\end{matrix}\right)=\left(\begin{matrix}y\\\ y\end{matrix}\right)$ (2)

expresses that the identities $t(x,x,y)=y$ and $t(y,x,x)=y$ hold in
${\mathcal{K}}$, that is, $t$ is a _Mal’tsev_ term for ${\mathcal{K}}$.

###  2.2. Cube Terms and Parallelogram Terms

Let us fix an integer $\mathsf{d}\ (>1)$. A _$\mathsf{d}$ -cube term_ for
${\mathcal{K}}$ is a term $t$ satisfying a set of identities of the form (1)
in two variables $x,y$, where $M$ is a matrix with $\mathsf{d}$ rows such that
every column of $M$ contains at least one $x$, and $\vec{v}$ consists of $y$’s
only. As (2) shows, a Mal’tsev term is a $2$-cube term.

As we mentioned in the introduction, cube terms were introduced in [3] to show
that a finite algebra $\mathbf{A}$ has few subpowers if and only if
$\mathbf{A}$ has a cube term. More manageable terms that are equivalent to
cube terms (e.g., edge terms, star terms) were also found in [3]. In this
paper we will use another family of equivalent terms, called parallelogram
terms, which were introduced in [16].

Let $m$ and $n$ be positive integers and let $\mathsf{d}=m+n$. An
$(m,n)$-parallelogram term for ${\mathcal{K}}$ is a $(\mathsf{d}+3)$-ary term
$P_{m,n}$ such that

${\mathcal{K}}\models P_{m,n}\left(\begin{array}[]{ccc|}x&x&y\\\ x&x&y\\\
&\vdots&\\\ x&x&y\\\ \hline\cr y&x&x\\\ &\vdots&\\\ y&x&x\\\ y&x&x\\\
\end{array}\begin{array}[]{cccccccc}z&y&\cdots&y&y&\cdots&y&y\\\
y&z&&y&y&&y&y\\\ \vdots&&\ddots&&&&&\vdots\\\ y&y&&z&y&&y&y\\\
y&y&&y&z&&y&y\\\ \vdots&&&&&\ddots&&\vdots\\\ y&y&&y&y&&z&y\\\
y&y&\cdots&y&y&\cdots&y&z\\\ \end{array}\right)=\left(\begin{matrix}y\\\ y\\\
\vdots\\\ y\\\ y\\\ \vdots\\\ y\\\ y\end{matrix}\right).$ (3)

Here the rightmost block of variables is a $\mathsf{d}\times\mathsf{d}$ array,
the upper left block is $m\times 3$ and the lower left block is $n\times 3$.

It is easy to see from these definitions that an $(m,n)$-parallelogram term
that is independent of its last $\mathsf{d}$ variables is a Mal’tsev term, and
an $(m,n)$-parallelogram term that is independent of its first $3$ variables
is a $\mathsf{d}$-ary near unanimity term.

The theorem below summarizes the facts we will need later on about cube terms
and parallelogram terms.

######  Theorem 1 (See [3, 16]).

Let ${\mathcal{V}}$ be a variety, and let $\mathsf{d}\,(>1)$ be an integer.

  1. (1)

The following conditions are equivalent:

    1. (a)

${\mathcal{V}}$ has a $\mathsf{d}$-cube term,

    2. (b)

${\mathcal{V}}$ has an $(m,n)$-parallelogram term for all $m,n\geq 1$ with
$m+n=\mathsf{d}$,

    3. (c)

${\mathcal{V}}$ has an $(m,n)$-parallelogram term for some $m,n\geq 1$ with
$m+n=\mathsf{d}$.

  2. (2)

If ${\mathcal{V}}$ has a cube term, then ${\mathcal{V}}$ is congruence
modular.

In statement (2) the phrase ${\mathcal{V}}$ is _congruence modular_ means that
the congruence lattice of every algebra in ${\mathcal{V}}$ is _modular_ ; see,
[11]. The equivalence of the conditions (a)–(c) in statement (1) follows by
combining results from [3, Theorem 4.4] and [16, Theorem 3.5]. Proofs for
statement (2) can be found in [3, Theorem 2.7] and [9, Theorem 3.2].

In view of the equivalence of conditions (a) and (c) in Theorem 1, when we
consider classes of algebras with a $\mathsf{d}$-cube term, we will work with
a $(1,\mathsf{d}-1)$-parallelogram term $P=P_{1,\mathsf{d}-1}$, and we will
also use the following terms derived from $P$:

$\displaystyle s(x_{1},\ldots,x_{\mathsf{d}})$
$\displaystyle{}:=P(x_{1},x_{2},x_{2},x_{1},\ldots,x_{\mathsf{d}}),$ (4)
$\displaystyle p(x,u,y)$ $\displaystyle{}:=P(x,u,y,x,y,\ldots,y).$

For any class ${\mathcal{K}}$ of algebras with a
$(1,\mathsf{d}-1)$-parallelogram term $P$ one can easily deduce from the
$(1,\mathsf{d}-1)$-parallelogram identities that

$\displaystyle{\mathcal{K}}\ \models\ \ $ $\displaystyle y=p(x,x,y),$
$\displaystyle\phantom{y={}}p(x,y,y)=s(x,y,y,\ldots,y),$
$\displaystyle\phantom{y=p(x,y,y)={}}s(y,x,y,\ldots,y)=y,$ (5)
$\displaystyle\phantom{y=p(x,y,y)=s(y,x,y,\ldots,y)}\,\,\,\vdots$
$\displaystyle\phantom{y=p(x,y,y)={}}s(y,y,y,\ldots,x)=y.$

To simplify notation, we also define

$x^{y}:=p(x,y,y)\ (=s(x,y,\dots,y)),$ (6)

and

$s^{\ell}(x_{1},\ldots,x_{\mathsf{d}}):=s(s^{\ell-1}(x_{1},x_{2}\ldots,x_{\mathsf{d}}),x_{2},\ldots,x_{\mathsf{d}})\quad\text{for
all $\ell\geq 1$},$ (7)

where $s^{0}:=x_{1}$. So, $s^{1}=s$ and $s^{\ell}$ is the $\ell$-th iterate of
$s$ in the first variable.

###  2.3. Congruence Modular Varieties: the Commutator and Residual Smallness

Let ${\mathcal{V}}$ be an arbitrary congruence modular variety. There is a
well-behaved commutator operation $[\phantom{n},\phantom{n}]$ on the
congruence lattices of algebras in any such variety ${\mathcal{V}}$, which
extends — and shares many important properties of — the group theoretic
commutator for normal subgroups of groups. For the definition and basic
properties of the commutator operation in ${\mathcal{V}}$ the reader is
referred to [11]. A congruence $\alpha\in\operatorname{Con}(\mathbf{A})$ of an
algebra $\mathbf{A}\in{\mathcal{V}}$ is called _abelian_ if
$[\alpha,\alpha]=0$, and the _centralizer_ of a congruence
$\alpha\in\operatorname{Con}(\mathbf{A})$, denoted $(0:\alpha)$, is the
largest congruence $\gamma\in\operatorname{Con}(\mathbf{A})$ such that
$[\alpha,\gamma]=0$.

Recall that ${\mathcal{V}}$ has a _difference term_ (see [11, Theorem 5.5]),
which we will denote by $d$. In the last two sections of this paper we will
need some properties of abelian congruences, which can be summarized
informally as follows: the difference term $d$ induces abelian groups on the
blocks of all abelian congruences $\alpha$ of all algebras
$\mathbf{A}\in{\mathcal{V}}$; moreover, the term operations of $\mathbf{A}$
are ‘linear between the blocks’ of $\alpha$ with respect to these abelian
groups. The theorem below gives a more precise formulation of these facts.

[[11, Section 9]] Let ${\mathcal{V}}$ be a congruence modular variety with a
difference term $d$, let $\mathbf{A}\in{\mathcal{V}}$, and let $\alpha$ be an
abelian congruence of $\mathbf{A}$.

  1. (1)

For every $o\in A$, the $\alpha$-class containing $o$ forms an abelian group
$(o/\alpha;+_{o},-_{o},o)$ with zero element $o$ for the operations $+_{o}$
and $-_{o}$ defined by

$\qquad x+_{o}y:=d(x,o,y)\quad\text{and}\quad-_{o}x:=d(o,x,o)\quad\text{for
all $x,y\in o/\alpha$.}$

  2. (2)

For every term $g(x_{1},\dots,x_{k})$ in the language of ${\mathcal{V}}$, for
arbitrary elements $o_{1},\dots,o_{k},o\in A$ such that
$g(o_{1},\dots,o_{k})\equiv_{\alpha}o$, and for any tuple
$(a_{1},\dots,a_{k})\in(o_{1}/\alpha)\times\dots\times(o_{k}/\alpha)$,

$\qquad\quad
g(a_{1},a_{2},\dots,a_{k})=g(a_{1},o_{2},\dots,o_{k})+_{o}g(o_{1},a_{2},o_{3},\dots,o_{k})+_{o}\dots{\\\
}+_{o}g(o_{1},\dots,o_{k-1},a_{k})-_{o}(k-1)g(o_{1},o_{2},\dots,o_{k}).\quad$

We will refer to the abelian groups described in statement (1) as the _induced
abelian groups_ on the $\alpha$-classes of $\mathbf{A}$.

For a cardinal $c$, a variety ${\mathcal{V}}$ is called _residually less than
$c$_ if every subdirectly irreducible algebra in ${\mathcal{V}}$ has
cardinality $<c$; ${\mathcal{V}}$ is called _residually small_ if it is
residually less than some cardinal.

[[11]] If $\mathbf{A}$ is a finite algebra that generates a congruence modular
variety ${\mathcal{V}}(\mathbf{A})$, then the following conditions are
equivalent:

  1. (1)

${\mathcal{V}}(\mathbf{A})$ is residually small.

  2. (2)

${\mathcal{V}}(\mathbf{A})$ is residuall less than some natural number.

  3. (3)

For every subdirectly irreducible algebra
$\mathbf{S}\in\mathbb{H}\mathbb{S}(\mathbf{A})$ with abelian monolith $\mu$,
the centralizer $(0:\mu)$ of $\mu$ is an abelian congruence of $\mathbf{S}$.

######  Proof 2.1.

By [11, Theorem 10.15], (1) and (2) are both equivalent to the condition that
the commutator identity $[x\wedge y,y]=x\wedge[y,y]$ holds in the congruence
lattice of every subalgebra of $\mathbf{A}$. The latter is equivalent to (3)
by [12, p. 422].

Now let ${\mathcal{K}}=\\{\mathbf{A}_{1},\dots,\mathbf{A}_{n}\\}$ be a finite
set of finite algebras in a congruence modular variety, and let
${\mathcal{V}}({\mathcal{K}})$ be the variety generated by ${\mathcal{K}}$.
Then ${\mathcal{V}}({\mathcal{K}})$ is the join of the varieties
${\mathcal{V}}(\mathbf{A}_{i})$ for $i\leq n$. Hence, by [11, Theorem 11.1],
${\mathcal{V}}({\mathcal{K}})$ is residually small iff
${\mathcal{V}}(\mathbf{A}_{i})$ is residually small for all $i\leq n$. Thus we
get the following corollary.

######  Corollary 2.

Let ${\mathcal{K}}$ be a finite set of finite algebras in a congruence modular
variety. The variety generated by ${\mathcal{K}}$ is residually small if and
only if for every subdirectly irreducible algebra
$\mathbf{S}\in\mathbb{H}\mathbb{S}({\mathcal{K}})$ with abelian monolith
$\mu$, the centralizer $(0:\mu)$ of $\mu$ is an abelian congruence of
$\mathbf{S}$.

In conclusion of this section, we introduce a slightly technical notion,
_similarity_ , which is an important equivalence relation on the class of
subdirectly irreducible algebras in a congruence modular variety and will play
a role in Sections 5–6. However, a reader of this paper may safely regard the
definition of similarity as a ‘black box’, since similarity only occurs as a
result of using the structure theorem from [16] (see Theorem 24), and in the
algorithms in Section 6, similarity is applied only to a finite set of finite
subdirectly irreducible algebras, therefore checking similarity between them
does not affect the complexity of the algorithms.

To define similarity, let ${\mathcal{V}}$ be a congruence modular variety.
_Similarity_ is a binary relation defined on the class of subdirectly
irreducible algebras in ${\mathcal{V}}$. The definition may be found in [11,
Definition 10.7], and shows that similarity is an equivalence relation. To
decide whether two subdirectly irreducible algebras in ${\mathcal{V}}$ are
similar it is more convenient to use the following characterization given in
[11, Theorem 10.8]: two subdirectly irreducible algebras
$\mathbf{B},\mathbf{C}\in{\mathcal{V}}$ are similar if and only if there
exists an algebra $\mathbf{E}\in\mathcal{V}$ (which can be taken to be a
subdirect subalgebra of $\mathbf{B}\times\mathbf{C}$) and there exist
congruences $\beta,\gamma,\delta,\varepsilon\in\operatorname{Con}(\mathbf{E})$
such that $\mathbf{E}/\beta\cong\mathbf{B}$,
$\mathbf{E}/\gamma\cong\mathbf{C}$ and there is a projectivity
${[\\![}\,{\beta},{\beta^{+}}\,{]\\!]}\searrow{[\\![}\,{\delta},{\varepsilon}\,{]\\!]}\nearrow{[\\![}\,{\gamma},{\gamma^{+}}\,{]\\!]}$
in $\operatorname{Con}(\mathbf{E})$, where $\beta^{+}$ and $\gamma^{+}$ are
the unique upper covers of $\beta$ and $\gamma$, respectively. Here
${[\\![}\,{\beta},{\beta^{+}}\,{]\\!]}\searrow{[\\![}\,{\delta},{\varepsilon}\,{]\\!]}\nearrow{[\\![}\,{\gamma},{\gamma^{+}}\,{]\\!]}$
denotes that $\beta\wedge\varepsilon=\delta,\beta\vee\varepsilon=\beta^{+}$
and $\varepsilon\wedge\gamma=\delta,\varepsilon\vee\gamma=\gamma^{+}$.

##  3\. Compact Representations

Throughout this section we will use the following global assumptions:

  * •

${\mathcal{V}}$ is a variety with a $\mathsf{d}$-cube term ($\mathsf{d}>1$),

  * •

$P$ is a $(1,\mathsf{d}-1)$-parallelogram term in ${\mathcal{V}}$ (the
existence of such a term is ensured by Theorem 1), and

  * •

$s(x_{1},\ldots,x_{\mathsf{d}})$, $p(x,u,y)$, $x^{y}$, and
$s^{\ell}(x_{1},\ldots,x_{\mathsf{d}})$ are the terms defined in (4) and
(6)–(7).

We will not assume that the algebras we are considering are finite, or have a
finite language. Therefore, unless finiteness is assumed explicitly, all
statements and results hold for arbitrary algebras.

Terms in the language of ${\mathcal{V}}$ which can be expressed using $P$
only, will be referred to as _$P$ -terms_. For example, the terms
$s(x_{1},\ldots,x_{\mathsf{d}})$, $p(x,u,y)$, $x^{y}$, and
$s^{\ell}(x_{1},\ldots,x_{\mathsf{d}})$ are $P$-terms. By a _$P$ -subalgebra_
of an algebra $\mathbf{A}\in{\mathcal{V}}$ we mean a subalgebra of the reduct
of $\mathbf{A}$ to the language $\\{P\\}$. We will say that an algebra
$\mathbf{A}\in{\mathcal{V}}$ is _$P$ -generated_ by $R\subseteq A$ if $R$ is a
generating set for the reduct of $\mathbf{A}$ to the language $\\{P\\}$; or
equivalently, if every element of $\mathbf{A}$ is of the form
$t(r_{1},\dots,r_{m})$ for some $m\geq 0$, some elements $r_{1},\dots,r_{m}\in
R$, and some $m$-ary $P$-term $t$. The $P$-subalgebra of an algebra
$\mathbf{A}\in{\mathcal{V}}$ generated by a set $S\,(\subseteq A)$ will be
denoted by $\langle S\rangle_{P}$. Recall that circuit representations of
$P$-terms are called _$P$ -circuits_, as they use only gates of type $P$.

Now we will introduce a variant of the concept of ‘compact representation’
from [3]. One difference is that we will use a less restrictive notion of
‘fork’ than ‘minority fork’, because we want to avoid assuming finiteness of
the algebras considered unless finiteness is necessary for the conclusions.
Another difference is that we will consider subalgebras of products of
algebras, rather than subalgebras of powers of a single algebra. Let
$\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{V}}$, and let $B\subseteq
A_{1}\times\dots\times A_{n}$. For $i\in[n]$ and $\gamma,\delta\in A_{i}$ we
will say that $(\gamma,\delta)$ is a _fork in the $i$-th coordinate of $B$_ if
there exist $b,\widehat{b}\in B$ such that

$b|_{[i-1]}=\widehat{b}|_{[i-1]}\quad\text{and}\quad b|_{i}=\gamma,\ \
\widehat{b}|_{i}=\delta.$ (8)

The set of all forks in the $i$-th coordinate of $B$ will be denoted by
$\operatorname{\text{\sc fork}}_{i}(B)$. Tuples $b,\widehat{b}\in B$
satisfying (8) will be referred to as _witnesses_ for the fork
$(\gamma,\delta)\in\operatorname{\text{\sc fork}}_{i}(B)$. For each $i$ and
$B$ as above and for every positive integer $e$, we define

$\operatorname{\text{\sc
fork}}^{e}_{i}(B):=\\{(\gamma,\delta^{\gamma^{e}}):(\gamma,\delta)\in\operatorname{\text{\sc
fork}}_{i}(B)\\}$

where $\delta^{\gamma^{e}}$ is a short notation for
$(\dots((\delta^{\gamma})^{\gamma})\dots)^{\gamma}$ with $e$ occurrences of
$\gamma$. The elements of $\operatorname{\text{\sc fork}}^{e}_{i}(B)$ will be
called _$e$ -derived forks in the $i$-th coordinate of $B$_. In the case when
$e=1$ we will use the notation $\operatorname{\text{\sc
fork}}^{\prime}_{i}(B)$ instead of $\operatorname{\text{\sc
fork}}^{1}_{i}(B)$, and will call the elements of $\operatorname{\text{\sc
fork}}^{\prime}_{i}(B)$ _derived forks in the $i$-th coordinate of $B$_. The
next lemma shows that derived forks are indeed forks, and they are
‘transferable’, which does not hold for forks in general.

######  Lemma 3.

If $\mathbf{A}_{1},\ldots,\mathbf{A}_{n}\in{\mathcal{V}}$ and $\mathbf{B}$ is
a $P$-subalgebra of $\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$, then

  1. (1)

$\operatorname{\text{\sc fork}}_{i}(B)\supseteq\operatorname{\text{\sc
fork}}^{\prime}_{i}(B)\supseteq\dots\supseteq\operatorname{\text{\sc
fork}}^{e}_{i}(B)\supseteq\operatorname{\text{\sc
fork}}^{e+1}_{i}(B)\supseteq\dots$ for all $i\in[n]$ and $e\geq 1$; moreover,

  2. (2)

for every $(\gamma,\delta)\in\operatorname{\text{\sc fork}}^{\prime}_{i}(B)$
and for every $b\in B$ with $b|_{i}=\gamma$, there is an element
$\widehat{b}\in B$ such that (8) holds, that is, $b$ and $\widehat{b}$ witness
that $(\gamma,\delta)\in\operatorname{\text{\sc fork}}_{i}(B)$.

######  Proof 3.1.

For (2) let $(\gamma,\delta)\in\operatorname{\text{\sc fork}}^{\prime}_{i}(B)$
and let $b\in B$ with $b|_{i}=\gamma$. Then there exists
$(\gamma,\beta)\in\operatorname{\text{\sc fork}}_{i}(B)$ such that
$\delta=\beta^{\gamma}$. Let $c,\widehat{c}\in B$ be witnesses for
$(\gamma,\beta)\in\operatorname{\text{\sc fork}}_{i}(B)$; thus,
$c|_{[i-1]}=\widehat{c}|_{[i-1]}$ and $c|_{i}=\gamma$,
$\widehat{c}|_{i}=\beta$. It follows from the identities in (2.2) that for the
element $\widehat{b}:=p(\widehat{c},c,b)\in B$ we have

$\widehat{b}|_{[i-1]}=p(\widehat{c}|_{[i-1]},c|_{[i-1]},b|_{[i-1]})=b|_{[i-1]},$

and

$\widehat{b}|_{i}=p(\widehat{c}|_{i},c|_{i},b|_{i})=p(\beta,\gamma,\gamma)=\beta^{\gamma}=\delta.$

This proves (2), and also the inclusion $\operatorname{\text{\sc
fork}}_{i}(B)\supseteq\operatorname{\text{\sc fork}}^{\prime}_{i}(B)$ in (1).
The inclusion $\operatorname{\text{\sc
fork}}^{e}_{i}(B)\supseteq\operatorname{\text{\sc fork}}^{e+1}_{i}(B)$ for any
$e\geq 1$ follows by the same argument, using
$\delta=\beta^{\gamma^{e+1}}=(\beta^{\gamma^{e}})^{\gamma}$ and
$\beta^{\gamma^{e}}$ in place of $\delta=\beta^{\gamma}$ and $\beta$.

The following ‘weak transitivity rule’ for forks will also be useful.

######  Lemma 4.

Let $\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{V}}$, and let
$\mathbf{B}$ be a $P$-subalgebra of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$. If $(\gamma,\delta)$ and
$(\beta,\delta)$ are forks in $\operatorname{\text{\sc fork}}_{i}(B)$
witnessed by the pairs $(v,\widehat{v})$ and $(u,\widehat{u})$ in
$\mathbf{B}$, respectively, then the pair

$\Bigl{(}p(p(v,\widehat{v},\widehat{u}),p(v,\widehat{v},\widehat{v}),v),\ \
p(u,v,v)\Bigr{)}$ (9)

in $\mathbf{B}$ is a witness for the fork
$(\gamma,\beta^{\gamma})\in\operatorname{\text{\sc fork}}_{i}(B)$.

######  Proof 3.2.

The choice of $u,\widehat{u},v,\widehat{v}$ implies that
$u|_{[i-1]}=\widehat{u}|_{[i-1]}$, $v|_{[i-1]}=\widehat{v}|_{[i-1]}$, and
$u|_{i}=\beta$, $\widehat{u}|_{i}=\delta=\widehat{v}|_{i}$, $v|_{i}=\gamma$.
Hence,

$p(p(v,\widehat{v},\widehat{u}),p(v,\widehat{v},\widehat{v}),v)|_{[i-1]}\\\
=p(p(v|_{[i-1]},\widehat{v}|_{[i-1]},\widehat{u}|_{[i-1]}),p(v|_{[i-1]},\widehat{v}|_{[i-1]},\widehat{v}|_{[i-1]}),v|_{[i-1]})\\\
=p(u|_{[i-1]},v|_{[i-1]},v|_{[i-1]})=p(u,v,v)|_{[i-1]}$

and

$\displaystyle
p(p(v,\widehat{v},\widehat{u}),p(v,\widehat{v},\widehat{v}),v)|_{i}$
$\displaystyle{}=p(p(\gamma,\delta,\delta),p(\gamma,\delta,\delta),\gamma)=\gamma,$
$\displaystyle p(u,v,v)|_{i}$
$\displaystyle{}=p(\beta,\gamma,\gamma)=\beta^{\gamma}.$

Clearly, $u,\widehat{u},v,\widehat{v}\in\mathbf{B}$ implies that the pair (9)
also lies in $\mathbf{B}$, so the proof of the lemma is complete.

For two sets $B,R\subseteq A_{1}\times\dots\times A_{n}$, we will say that $R$
is a _$(\mathsf{d},e)$ -representation for $B$_ if the following three
conditions are met:

  1. (1)

$R\subseteq B$;

  2. (2)

$R|_{I}=B|_{I}$ for all $I\subseteq[n]$ with $|I|<\mathsf{d}$;

  3. (3)

$\operatorname{\text{\sc fork}}_{i}(R)\supseteq\operatorname{\text{\sc
fork}}^{e}_{i}(B)$ for all $i\in[n]$.

If $e=1$ and the parameter $\mathsf{d}$ of the cube term of ${\mathcal{V}}$ is
clear from the context, then reference to $(\mathsf{d},e)$ will be omitted.

In the special case when $\mathbf{A}_{1},\dots,\mathbf{A}_{n}$ are members of
a fixed finite set ${\mathcal{K}}$ of finite algebras in ${\mathcal{V}}$, and
the maximum size of an algebra in ${\mathcal{K}}$ is
$\mathsf{a}_{{\mathcal{K}}}$, then it is easy to see that every set
$B\subseteq A_{1}\times\dots\times A_{n}$ has a
$(\mathsf{d},e)$-representation $R$ of size

$|R|\leq\sum_{I\subseteq[n],|I|<d}\bigl{|}B|_{I}\bigr{|}+\sum_{i\in[n]}\operatorname{\text{\sc
fork}}^{e}_{i}(B)\leq\binom{n}{\mathsf{d}-1}\mathsf{a}_{{\mathcal{K}}}^{\mathsf{d}-1}+2n\mathsf{a}_{{\mathcal{K}}}^{2}.$

A $(\mathsf{d},e)$-representation $R$ for $B$ of size
$|R|\leq\binom{n}{\mathsf{d}-1}\mathsf{a}_{{\mathcal{K}}}^{\mathsf{d}-1}+2n\mathsf{a}_{{\mathcal{K}}}^{2}$
is called a _compact $(\mathsf{d},e)$-representation_ for $B$.

######  Remark 5.

If ${\mathcal{K}}$ is a finite set of finite algebras in ${\mathcal{V}}$, then
there exists an $e\geq 1$ such that
${\mathcal{K}}\models(x^{y^{e}})^{y^{e}}=x^{y^{e}}$. For such an $e$, the
terms $d(x,y)=y^{x^{e}}$, $p(z,y,x)^{x^{e-1}}$ and
$s^{e}(x_{1},\dots,x_{\mathsf{d}})$ satisfy the identities in [3, Lemma 2.13].
Consequently, for this $e$, our $e$-derived forks and (compact)
$(\mathsf{d},e)$-representations are exactly the minority forks (called
minority indices), and the (compact) representations with minority forks
defined in [3, Definitions 3.1–3.2].

It was proved in [3, Lemma 3.4, Theorem 3.6] that for any subalgebra
$\mathbf{B}$ of a finite power of a finite algebra
$\mathbf{A}\in{\mathcal{V}}$, a compact representation (with minority forks)
generates $\mathbf{B}$. The next theorem is essentially the same result, with
several significant differences, which we will discuss in Remark 7 below.

######  Theorem 6.

Let $e$ be a fixed positive integer. For every integer $n\geq\mathsf{d}$ there
exists a $P$-term $T_{n}$ satisfying the following conditions:

  1. (1)

If $\mathbf{B}$ is a $P$-subalgebra of a product
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ of finitely many algebras
$\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{V}}$, and $R$ is a
$(\mathsf{d},e)$-representation for $\mathbf{B}$, then every element of
$\mathbf{B}$ is produced by a single application of $T_{n}$ to some elements
of $R$. Consequently, $\mathbf{B}$ is $P$-generated by $R$.

  2. (2)

The size of the $P$-circuit $\mathsf{Circ}(T_{n})$ is $O(en^{\mathsf{d}+1})$,
and there is an algorithm that runs in time $O(en^{\mathsf{d}+1})$, which
outputs $\mathsf{Circ}(T_{n})$ for any given $e$ and $n$.

Note that the $P$-terms $T_{n}$ depend on the parameter $e$, but to simplify
notation, we decided to suppress this dependence in the notation of $T_{n}$
(and in the notation of the terms needed to build up $T_{n}$, see Lemma 8). In
this paper we will use Theorem 6 for $e=1$ and $e=2$ only.

######  Remark 7.

The main differences between [3, Lemma 3.4, Theorem 3.6] and Theorem 6 are as
follows:

  * •

As we explained at the beginning of this section, we consider subalgebras of
direct products of finitely many different algebras rather than just
subalgebras of finite direct powers of the same algebra. In addition, we don’t
assume that the algebras are finite, therefore we use a less restrictive
notion of a fork than the notion used in [3], cf. Remark 5.

  * •

Given $e$, we produce a $P$-term $T_{n}$ for every $n$, which describes a
uniform way for obtaining each element of a $P$-subalgebra $\mathbf{B}$ of a
product $\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ in one step from
members of an arbitrary $(\mathsf{d},e)$-representation for $\mathbf{B}$.
Since we are interested in algorithmic applications, the advantage of finding
these terms $T_{n}$ explicitly is that — via the minimal circuit
representation of $T_{n}$ — we can get a useful upper bound on the length of
computations needed to generate elements of $\mathbf{B}$ from members of a
$(\mathsf{d},e)$-representation for $\mathbf{B}$.

First we will prove the following lemma.

######  Lemma 8.

Let $e$ be a fixed positive integer. For every integer $n\geq\mathsf{d}$ there
exists a $P$-term $t_{n}=t_{n}\bigl{(}x,y,z,\overline{w_{I}}\bigr{)}$, where
$\overline{w_{I}}:=(w_{I})_{I\in\binom{[n]}{\mathsf{d}-1}}$ is a tuple of
variables indexed by all $(\mathsf{d}-1)$-element subsets of $[n]$, such that
the following hold:

  1. (1)

For every subset $R$ of a product
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ with
$\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{V}}$, and for every tuple
$b=(b_{1},\dots,b_{n-1},\gamma)$ in
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$, if

    1. (a)

for each $I\in\binom{[n]}{\mathsf{d}-1}$ the set $R$ contains a tuple $b^{I}$
satisfying $b^{I}|_{I}=b|_{I}$, and

    2. (b)

for some element $b^{\prime}=(b_{1},\dots,b_{n-1},\beta)$ of the
$P$-subalgebra $\mathbf{R}^{*}:=\langle R\rangle_{P}$ of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$, the set $R$ contains tuples
$u=(u_{1},\dots,u_{n-1},\gamma)$ and
$\widehat{u}=(u_{1},\dots,u_{n-1},\beta^{\gamma^{e}})$ which are witnesses for
the fork $(\gamma,\beta^{\gamma^{e}})\in\operatorname{\text{\sc
fork}}_{n}(R)$,

then

$b=t_{n}\bigl{(}b^{\prime},\widehat{u},u,\overline{b^{I}}\bigr{)}\quad\text{where}\quad\overline{b^{I}}:=(b^{I})_{I\in\binom{[n]}{\mathsf{d}-1}},$
(10)

and therefore $b$ is in $\mathbf{R}^{*}$.

  2. (2)

The size of the $P$-circuit $\mathsf{Circ}(t_{n})$ is $O(en^{\mathsf{d}})$,
and there is an algorithm that runs in time $O(en^{\mathsf{d}})$, which
outputs $\mathsf{Circ}(t_{n})$ for any given $e$ and $n$.

######  Proof 3.3.

We use a dynamic programming approach to build the tuple $b$ and keep a record
of the sequence of operations we perform so that we obtain the term $t_{n}$ in
the end. For every $\ell\in[n]\setminus[\mathsf{d}-2]$ and for every set
$V^{\prime}\in\binom{[\ell]}{\mathsf{d}-1}$ we construct a $P$-term
$t_{\ell,V^{\prime}}$ which ‘approximates’ $t_{n}$ in the sense that for
$t_{\ell,V^{\prime}}$ in place of $t_{n}$ the equality (10) holds in all
coordinates in $V^{\prime}\cup([n]\setminus[\ell])$ (but may fail in other
coordinates).

For $\ell=n,n-1,\dots,\mathsf{d}-1$ and for every set
$V:=V^{\prime}\cup([n]\setminus[\ell])$ with
$V^{\prime}\in\binom{[\ell]}{\mathsf{d}-1}$ there exists a $P$-term
$t_{\ell,V^{\prime}}=t_{\ell,V^{\prime}}(x,y,z,\overline{w_{I}}^{V})$ with
$\overline{w_{I}}^{V}:=(w_{I})_{I\in\binom{V}{\mathsf{d}-1}}$ such that
whenever the algebras $\mathbf{A}_{1},\dots,\mathbf{A}_{n}$, $\mathbf{R}^{*}$
and the elements $b$, $b^{I}$ $\bigl{(}I\in\binom{[n]}{\mathsf{d}-1}\bigr{)}$,
$b^{\prime}$, $u$, $\widehat{u}$ satisfy the assumptions of Lemma 8 (1), we
have that

$b|_{V}=t_{\ell,V^{\prime}}\bigl{(}b^{\prime},\widehat{u},u,\overline{b^{I}}^{V}\bigr{)}|_{V}\quad\text{where}\quad\overline{b^{I}}^{V}:=(b^{I})_{I\in\binom{V}{\mathsf{d}-1}}.$

######  Proof 3.4 (Proof of Claim 3.3.).

We proceed by induction on $n-\ell$. For $n=\ell$ we have that
$V=V^{\prime}\in\binom{[n]}{\mathsf{d}-1}$. So we can choose
$t_{n,V^{\prime}}(x,y,z,w_{V}):=w_{V}$, and our claim is trivial.

Assume now that $\ell<n$ and that our claim is true for $\ell+1$. To prove the
claim for $\ell$, let $V=V^{\prime}\cup([n]\setminus[\ell])$ with
$V^{\prime}=\\{i_{1},\dots,i_{\mathsf{d}-1}\\}\in\binom{[\ell]}{\mathsf{d}-1}$,
$i_{1}<\dots<i_{\mathsf{d}-1}$. For $j\in[\mathsf{d}-1]$ let
$V^{\prime}_{j}=\\{i_{1},\dots,i_{j-1},i_{j+1},\dots,i_{\mathsf{d}-1},\ell+1\\}$
and $V_{j}:=V\setminus\\{i_{j}\\}=V^{\prime}_{j}\cup([n]\setminus[\ell+1])$.
We will prove that the $P$-term

$t_{\ell,V^{\prime}}\bigl{(}x,y,z,\overline{w_{I}}^{V}\bigr{)}:=P\Bigl{(}s^{e+1}\bigl{(}x,(t_{\ell+1,V^{\prime}_{j}}(x,y,z,\overline{w_{I}}^{V_{j}}))_{j\in[\mathsf{d}-1]}\bigr{)},\\\
p\bigl{(}y,z,t_{\ell+1,V^{\prime}_{1}}(x,y,z,\overline{w_{I}}^{V_{1}})\bigr{)},t_{\ell+1,V^{\prime}_{1}}(x,y,z,\overline{w_{I}}^{V_{1}}),x,\bigl{(}t_{\ell+1,V^{\prime}_{j}}(x,y,z,\overline{w_{I}}^{V_{j}})\bigr{)}_{j\in[\mathsf{d}-1]}\Bigr{)}$
(11)

has the desired properties, where the $P$-terms $t_{\ell+1,V_{j}^{\prime}}$
($j\in[\mathsf{d}-1]$) are supplied by the induction hypothesis. To prove
this, let $\mathbf{A}_{1},\dots,\mathbf{A}_{n}$, $\mathbf{R}^{*}$, and $b$,
$b^{I}$ $\bigl{(}I\in\binom{[n]}{\mathsf{d}-1}\bigr{)}$, $b^{\prime}$, $u$,
$\widehat{u}$ satisfy the assumptions of Lemma 8 (1). By the induction
hypothesis, the elements
$b^{\ell+1,V^{\prime}_{j}}:=t_{\ell+1,V^{\prime}_{j}}\bigl{(}b^{\prime},\widehat{u},u,\overline{b^{I}}^{V_{j}}\bigr{)}$
satisfy the condition $b^{\ell+1,V^{\prime}_{j}}|_{V_{j}}=b|_{V_{j}}$ for all
$j\in[\mathsf{d}-1]$; that is, $b^{\ell+1,V^{\prime}_{j}}|_{V}$ has the form

$b^{\ell+1,V^{\prime}_{j}}|_{V}=(b_{i_{1}},\dots,b_{i_{j-1}},\zeta_{j},b_{i_{j+1}},\dots,b_{i_{\mathsf{d}-1}},b_{\ell+1},\dots,b_{n-1},\gamma)$

for some element $\zeta_{j}\in A_{i_{j}}$ in the $j$-th coordinate. To compute
$t_{\ell,V^{\prime}}(b^{\prime},\widehat{u},u,\overline{b^{I}}^{V})|_{V}$, we
start with evaluating the first two arguments of $P$ in the expression for
$t_{\ell,V^{\prime}}$ in (11).

Using the identities for $s$ in (2.2) we get that

$s\bigl{(}b^{\prime},\bigl{(}t_{\ell+1,V^{\prime}_{j}}(b^{\prime},\widehat{u},u,\overline{b^{I}}^{V_{j}})\bigr{)}_{j\in[\mathsf{d}-1]}\bigr{)}\big{|}_{V}=s(b^{\prime}|_{V},b^{\ell+1,V^{\prime}_{1}}|_{V},\ldots,b^{\ell+1,V^{\prime}_{\mathsf{d}-1}}|_{V})\\\
=s\left(\begin{matrix}b_{i_{1}}&\zeta_{1}&b_{i_{1}}&\dots&b_{i_{1}}\\\
b_{i_{2}}&b_{i_{2}}&\zeta_{2}&\dots&b_{i_{2}}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
b_{i_{\mathsf{d}-1}}&b_{i_{\mathsf{d}-1}}&b_{i_{\mathsf{d}-1}}&\dots&\zeta_{\mathsf{d}-1}\\\
b_{\ell+1}&b_{\ell+1}&b_{\ell+1}&\dots&b_{\ell+1}\\\
\vdots&\vdots&\vdots&&\vdots\\\ b_{n-1}&b_{n-1}&b_{n-1}&\dots&b_{n-1}\\\
\beta&\gamma&\gamma&\dots&\gamma\end{matrix}\right)=\left(\begin{matrix}b_{i_{1}}\\\
b_{i_{2}}\\\ \vdots\\\ b_{i_{\mathsf{d}-1}}\\\ b_{\ell+1}\\\ \vdots\\\
b_{n-1}\\\ \beta^{\gamma}\end{matrix}\right).$

By repeating the same computation $e$ more times so that every time the tuple
just obtained is placed in the first argument of $s$ in the next computation,
we obtain that

$s^{e+1}\bigl{(}b^{\prime},\bigl{(}t_{\ell+1,V^{\prime}_{j}}(b^{\prime},\widehat{u},u,\overline{b^{I}}^{V_{j}})\bigr{)}_{j\in[\mathsf{d}-1]}\bigr{)}\big{|}_{V}=s^{e+1}(b^{\prime}|_{V},b^{\ell+1,V^{\prime}_{1}}|_{V},\ldots,b^{\ell+1,V^{\prime}_{\mathsf{d}-1}}|_{V})\\\
=\left(\begin{matrix}b_{i_{1}}\\\ b_{i_{2}}\\\ \vdots\\\
b_{i_{\mathsf{d}-1}}\\\ b_{\ell+1}\\\ \vdots\\\ b_{n-1}\\\
\beta^{\gamma^{e+1}}\end{matrix}\right).$ (12)

The identities for $p$ in (2.2) yield that

$p\bigl{(}\widehat{u},u,t_{\ell+1,V^{\prime}_{1}}(b^{\prime},\widehat{u},u,\overline{b^{I}}^{V_{1}})\bigr{)}|_{V}=p\bigl{(}\widehat{u}|_{V},u|_{V},b^{\ell+1,V^{\prime}_{1}}|_{V}\bigr{)}\\\
=p\left(\begin{matrix}u_{i_{1}}&u_{i_{1}}&\zeta_{1}\\\
u_{i_{2}}&u_{i_{2}}&b_{i_{2}}\\\ \vdots&\vdots&\vdots\\\
u_{i_{\mathsf{d}-1}}&u_{i_{\mathsf{d}-1}}&b_{i_{\mathsf{d}-1}}\\\
u_{\ell+1}&u_{\ell+1}&b_{\ell+1}\\\ \vdots&\vdots&\vdots\\\
u_{n-1}&u_{n-1}&b_{n-1}\\\
\beta^{\gamma^{e}}&\gamma&\gamma\end{matrix}\right)=\left(\begin{matrix}\zeta_{1}\\\
b_{i_{2}}\\\ \vdots\\\ b_{i_{\mathsf{d}-1}}\\\ b_{\ell+1}\\\ \vdots\\\
b_{n-1}\\\ \beta^{\gamma^{e+1}}\end{matrix}\right).$ (13)

Combining (12) and (13) with the definition of $t_{\ell,V^{\prime}}$, and
using the $(1,\mathsf{d}-1)$-parallelogram identities, we obtain that

$t_{\ell,V^{\prime}}(b^{\prime},\widehat{u},u,\overline{b^{I}}^{V})|_{V}\\\
=P\left(\begin{matrix}b_{i_{1}}&\zeta_{1}&\zeta_{1}&b_{i_{1}}&\zeta_{1}&b_{i_{1}}&\dots&b_{i_{1}}\\\
b_{i_{2}}&b_{i_{2}}&b_{i_{2}}&b_{i_{2}}&b_{i_{2}}&\zeta_{2}&\dots&b_{i_{2}}\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
b_{i_{\mathsf{d}-1}}&b_{i_{\mathsf{d}-1}}&b_{i_{\mathsf{d}-1}}&b_{i_{\mathsf{d}-1}}&b_{i_{\mathsf{d}-1}}&b_{i_{\mathsf{d}-1}}&\dots&\zeta_{\mathsf{d}-1}\\\
b_{\ell+1}&b_{\ell+1}&b_{\ell+1}&b_{\ell+1}&b_{\ell+1}&b_{\ell+1}&\dots&b_{\ell+1}\\\
\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&&\vdots\\\
b_{n-1}&b_{n-1}&b_{n-1}&b_{n-1}&b_{n-1}&b_{n-1}&\dots&b_{n-1}\\\
\beta^{\gamma^{e+1}}&\beta^{\gamma^{e+1}}&\gamma&\beta&\gamma&\gamma&\dots&\gamma\end{matrix}\right)=\left(\begin{matrix}b_{i_{1}}\\\
b_{i_{2}}\\\ \vdots\\\ b_{i_{\mathsf{d}-1}}\\\ b_{\ell+1}\\\ \vdots\\\
b_{n-1}\\\ \gamma\end{matrix}\right)=b|_{V}.$

This completes the proof of Claim 3.3.

The term $t_{n}:=t_{\mathsf{d}-1,[\mathsf{d}-1]}$ constructed in Claim 3.3 for

$V=[n]=\\{1,\ldots,\mathsf{d}-1\\}\cup([n]\setminus[\mathsf{d}-1])$

clearly satisfies the requirement in statement (1) of Lemma 8.

To estimate the size of $\mathsf{Circ}(t_{n})$, note that the term $t_{n}$ has
$\sum_{\ell=\mathsf{d}-1}^{n-1}\binom{\ell}{\mathsf{d}-1}=O(n^{\mathsf{d}})$
distinct subterms of the form $t_{\ell,V^{\prime}}$ where
$\ell\in\\{\mathsf{d}-1,\dots,n-1\\}$ and
$V^{\prime}\in\binom{[\ell]}{\mathsf{d}-1}$. By (11), obtaining each one of
these terms $t_{\ell,V^{\prime}}$ from variables and subterms of the form
$t_{\ell+1,W}$ requires one application of each of $s^{e+1}$, $p$, and $P$,
that is, altogether $e+3$ applications of $P$. Hence $\mathsf{Circ}(t_{n})$
has size $O(en^{\mathsf{d}})$. This proves the first part of statement (2) of
Lemma 8. The second part is an immediate consequence of this estimate and the
definition of $t_{n}$.

Now let $n\geq\mathsf{d}$, and let $t_{n}=t_{n}(x,y,z,\overline{w_{I}})$ be
the $P$-term from Lemma 8. The analogous $P$-terms for $\mathsf{d}\leq m\leq
n$ are $t_{m}=t_{m}(x,y,z,\overline{w_{I}}^{[m]})$ with
$\overline{w_{I}}^{[m]}:=(w_{I})_{I\in\binom{[m]}{\mathsf{d}-1}}$. We will use
these terms to define new $P$-terms

$T_{m}(z^{(\mathsf{d})},\widehat{z}^{(\mathsf{d})},\dots,z^{(m)},\widehat{z}^{(m)},\overline{w_{I}}^{[m]})$

for each $m=\mathsf{d}-1,\mathsf{d},\dots,n$ by recursion as follows:
$T_{\mathsf{d}-1}(w_{[\mathsf{d}-1]}):=w_{[\mathsf{d}-1]}$, and for all $m$
with $\mathsf{d}\leq m\leq n$,

$T_{m}(z^{(\mathsf{d})},\widehat{z}^{(\mathsf{d})},\dots,z^{(m)},\widehat{z}^{(m)},\overline{w_{I}}^{[m]})\\\
{}:=t_{m}\bigl{(}T_{m-1}(z^{(\mathsf{d})},\widehat{z}^{(\mathsf{d})},\dots,z^{(m-1)},\widehat{z}^{(m-1)},\overline{w_{I}}^{[m-1]}),z^{(m)},\widehat{z}^{(m)},\overline{w_{I}}^{[m]}\bigr{)}.$

In particular, for $m=n$, the term is
$T_{n}(z^{(\mathsf{d})},\widehat{z}^{(\mathsf{d})},\dots,z^{(n)},\widehat{z}^{(n)},\overline{w_{I}})$,
because $\overline{w_{I}}^{[n]}=\overline{w_{I}}$.

Note that by this definition, $T_{n}$ has $n-\mathsf{d}+1$ subterms of the
form $T_{m}$ ($m=\mathsf{d},\dots,n$) other than the variable
$T_{\mathsf{d}-1}$. Furthermore, each $T_{m}$ is obtained from $T_{m-1}$ by
applying $t_{m}$ to $T_{m-1}$ and some variables. Since by Lemma 8, the
$P$-circuit $\mathsf{Circ}(t_{m})$ has size $O(em^{\mathsf{d}})$, we get that

$\text{the $P$-circuit }\mathsf{Circ}(T_{n})\text{ has size
}O(en^{\mathsf{d}+1}).$ (14)

######  Lemma 9.

Let $e$ be a fixed positive integer. Assume that
$\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{V}}$ $(n\geq\mathsf{d})$, and
let $b$ be an element and $R$ a subset of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ such that

  1. (a)

for each $I\in\binom{[n]}{\mathsf{d}-1}$ the set $R$ contains a tuple $b^{I}$
satisfying $b^{I}|_{I}=b|_{I}$, and

  2. (b)

for every $m$ with $\mathsf{d}\leq m\leq n$ the set $R$ contains tuples
$u^{(m)},\widehat{u}^{(m)}$ which are witnesses for the fork
$(\gamma,\beta^{\gamma^{e}})\in\operatorname{\text{\sc fork}}_{m}(R)$ where

$\gamma:=b|_{m}\quad\text{and}\quad\beta:=T_{m-1}(u^{(\mathsf{d})},\widehat{u}^{(\mathsf{d})},\dots,u^{(m-1)},\widehat{u}^{(m-1)},\overline{b^{I}}^{[m-1]})|_{m}.$
(15)

Then the following equalities hold:

$b|_{[m]}=T_{m}(u^{(\mathsf{d})},\widehat{u}^{(\mathsf{d})},\dots,u^{(m)},\widehat{u}^{(m)},\overline{b^{I}}^{[m]})|_{[m]}\quad\text{for
all $m=\mathsf{d}-1,\mathsf{d},\dots,n$;}$ (16)

in particular,

$b=T_{n}(u^{(\mathsf{d})},\widehat{u}^{(\mathsf{d})},\dots,u^{(n)},\widehat{u}^{(n)},\overline{b^{I}}).$
(17)

######  Proof 3.5.

Let $\mathbf{R}^{*}$ denote the $P$-subalgebra of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ generated by $R$. For
$m=\mathsf{d}-1,\mathsf{d},\dots,n$ let

$b^{(m)}:=T_{m}(u^{(\mathsf{d})},\widehat{u}^{(\mathsf{d})},\dots,u^{(m)},\widehat{u}^{(m)},\overline{b^{I}}^{[m]}).$

We will proceed by induction to prove that (16) holds, that is,
$b|_{[m]}=b^{(m)}|_{[m]}$ for all $m=\mathsf{d}-1,\mathsf{d},\dots,n$. Then,
for the case when $m=n$, (16) yields the equality (17).

To start the induction, let $m:=\mathsf{d}-1$. Since
$T_{\mathsf{d}-1}(w_{[\mathsf{d}-1]})=w_{[\mathsf{d}-1]}$, we have that
$b^{(\mathsf{d}-1)}=b^{[\mathsf{d}-1]}$, so
$b|_{[\mathsf{d}-1]}=b^{(\mathsf{d}-1)}|_{[\mathsf{d}-1]}$ is clearly true by
assumption (a).

Now assume that $m\geq\mathsf{d}$ and that the equality
$b|_{[m-1]}=b^{(m-1)}|_{[m-1]}$ holds. Then the tuples
$b|_{[m]}\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{m}$ and
$b^{(m-1)}|_{[m]}\in\mathbf{R}^{*}|_{[m]}$ have the form
$(b_{1},\dots,b_{m-1},\gamma)$ and $(b_{1},\dots,b_{m-1},\beta)$,
respectively, where $\gamma$ and $\beta$ are defined by (15). Assumption (b)
implies that $R$ contains tuples $u^{(m)},\widehat{u}^{(m)}\in R$ which are
witnesses for the fork $(\gamma,\beta^{\gamma^{e}})\in\operatorname{\text{\sc
fork}}_{m}(R)$. Then $u^{(m)}|_{[m]}$ and $\widehat{u}^{(m)}|_{[m]}$ are in
$R|_{[m]}$, and they have the form
$u^{(m)}|_{[m]}=(u_{1},\dots,u_{m-1},\gamma)$ and
$\widehat{u}^{(m)}|_{[m]}=(u_{1},\dots,u_{m-1},\beta^{\gamma^{e}})$ for some
$u_{i}\in\mathbf{A}_{i}$ ($i\in[m-1]$). The fact that $R$ satisfies assumption
(a) also implies that the elements $b^{I}|_{[m]}\in R|_{[m]}$ have the
property $(b^{I}|_{[m]})|_{I}=(b|_{[m]})|_{I}$ for all
$I\in\binom{[m]}{\mathsf{d}-1}$.

This shows that the assumptions (a)–(b) of Lemma 8 (1) hold for

  * •

the subset $R|_{[m]}$ and element $b|_{[m]}=(b_{1},\dots,b_{m-1},\gamma)$ of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{m}$,

  * •

the element $b^{(m-1)}|_{[m]}=(b_{1},\dots,b_{m-1},\beta)$ in
$\mathbf{R}^{*}|_{[m]}$, and

  * •

the elements $u^{(m)}|_{[m]}=(u_{1},\dots,u_{m-1},\gamma)$,
$\widehat{u}^{(m)}|_{[m]}=(u_{1},\dots,u_{m-1},\beta^{\gamma^{e}})$, and
$b^{I}|_{[m]}$ $\bigl{(}I\in\binom{[m]}{\mathsf{d}-1}\bigr{)}$ in $R|_{[m]}$.

Thus, Lemma 8 (1) — combined with the definitions of $b^{(m-1)}$ and $T_{m}$ —
implies that

$\displaystyle b|_{[m]}$
$\displaystyle{}=t_{m}(b^{(m-1)}|_{[m]},\widehat{u}^{(m)}|_{[m]},u^{(m)}|_{[m]},\overline{b^{I}|_{[m]}}^{[m]})$
$\displaystyle{}=t_{m}(b^{(m-1)},\widehat{u}^{(m)},u^{(m)},\overline{b^{I}}^{[m]})|_{[m]}$
$\displaystyle{}=t_{m}\bigl{(}T_{m-1}(u^{(\mathsf{d})},\widehat{u}^{(\mathsf{d})},\dots,u^{(m-1)},\widehat{u}^{(m-1)},\overline{b^{I}}^{[m-1]}),\widehat{u}^{(m)},u^{(m)},\overline{b^{I}}^{[m]}\bigr{)}|_{[m]}$
$\displaystyle{}=T_{m}(u^{(\mathsf{d})},\widehat{u}^{(\mathsf{d})},\dots,u^{(m)},\widehat{u}^{(m)},\overline{b^{I}}^{[m]})|_{[m]},$

which is what we wanted to prove.

######  Lemma 10.

Let $e$ be a fixed positive integer, and let $\mathbf{B}$ be a $P$-subalgebra
of a product $\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ of finitely many
algebras $\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{V}}$. If $R$ is a
$(\mathsf{d},e)$-representation for $\mathbf{B}$, then for every element $b$
of $\mathbf{B}$,

  1. (1)

there exist elements $b^{I}$ $(I\in\binom{[n]}{\mathsf{d}-1})$ and
$u^{(m)},\widehat{u}^{(m)}$ $(m=\mathsf{d},\dots,n)$ in $R$ such that
conditions (a)–(b) of Lemma 9 are satisfied,

  2. (2)

hence the equality
$b=T_{n}(u^{(\mathsf{d})},\widehat{u}^{(\mathsf{d})},\dots,u^{(n)},\widehat{u}^{(n)},\overline{b^{I}})$
in (17) holds for $b$.

######  Proof 3.6.

Let $R$ be a $(\mathsf{d},e)$-representation for $\mathbf{B}$, and let $b\in
B$. As before, let $\mathbf{R}^{*}$ denote the $P$-subalgebra of
$\mathbf{A}_{1}\times\dots\times\mathbf{A_{n}}$ generated by $R$. Our
statements will follow from Lemma 9 if we show that $b$ and $R$ satisfy the
assumptions (a)–(b) of that lemma. Condition (a) clearly follows from our
assumptions that $b\in B$ and $R$ is a $(\mathsf{d},e)$-representation for
$\mathbf{B}$. To verify condition (b) we proceed by induction on $m$ to show
that for every $m$ ($\mathsf{d}\leq m\leq n$)

  1. (b)m

$R$ contains tuples $u^{(m)},\widehat{u}^{(m)}$ witnessing the fork
$(\gamma,\beta^{\gamma^{e}})\in\operatorname{\text{\sc fork}}_{m}(R)$ where
$\gamma$ and $\beta$ are defined by (15).

Let $\mathsf{d}\leq m\leq n$, and assume that condition (b)i holds for
$i=\mathsf{d},\dots,m-1$; note that this assumption is vacuously true for the
base case $m=\mathsf{d}$. Our goal is to show that (b)m also holds. Let

$b^{(m-1)}:=T_{m-1}(u^{(\mathsf{d})},\widehat{u}^{(\mathsf{d})},\dots,u^{(m-1)},\widehat{u}^{(m-1)},\overline{b^{I}}^{[m-1]}),$

and let $\gamma$ and $\beta$ be defined by (15); that is, $\gamma=b|_{m}$ and
$\beta=b^{(m-1)}|_{m}$. Since $b^{(m-1)}$ involves only the elements $b^{I}$
$\bigl{(}I\in\binom{[m-1]}{\mathsf{d}-1}\bigr{)}$ and
$u^{(\mathsf{d})},\widehat{u}^{(\mathsf{d})},\dots,u^{(m-1)},\widehat{u}^{(m-1)}$
of $R$, and since our induction hypothesis ensures that these elements satisfy
the assumptions of Lemma 9, we get from Lemma 9 that
$b|_{[m-1]}=b^{(m-1)}|_{[m-1]}$. Here $b\in B$ and $b^{(m-1)}\in
R^{*}\subseteq B$, therefore $b$ and $b^{(m-1)}$ are witnesses in $\mathbf{B}$
for the fork $(\gamma,\beta)\in\operatorname{\text{\sc fork}}_{m}(B)$. Hence,
by Lemma 3, $(\gamma,\beta^{\gamma^{e}})\in\operatorname{\text{\sc
fork}}^{e}_{m}(B)$. So, the fact that $R$ is a $(\mathsf{d},e)$-representation
for $\mathbf{B}$ implies that
$(\gamma,\beta^{\gamma^{e}})\in\operatorname{\text{\sc fork}}_{m}(R)$. Thus,
(b)m holds, as we wanted to show.

######  Proof 3.7 (Proof of Theorem 6).

Statement (1) of Theorem 6 is an immediate consequence of Lemma 10. Statement
(2) of Theorem 6 follows directly from (14) and the definition of $T_{n}$.

We close this section by discussing the following question: given a generating
set for a subalgebra $\mathbf{B}$ of a product
$\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$ (in a variety with a cube
term) and a product congruence $\theta=\theta_{1}\times\dots\times\theta_{n}$
of $\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$ (where
$\theta_{i}\in\operatorname{Con}(\mathbf{B}_{i})$ for all $i\in[n]$), how can
one construct a generating set for the $\theta$-saturation
$\mathbf{B}[\theta]$ of $\mathbf{B}$? This is a crucial step for giving a
positive answer to Question 2 in the introduction, as we explain now.

Suppose that we are given a subalgebra $\mathbf{D}$ of
$\mathbf{B}_{1}/\theta_{1}\times\dots\times\mathbf{B}_{n}/\theta_{n}$ by a
generating set $\\{c_{1},\dots,c_{k}\\}$, along with another element $v$ of
$\mathbf{B}_{1}/\theta_{1}\times\dots\times\mathbf{B}_{n}/\theta_{n}$, and our
task is to decide whether or not $v\in\mathbf{D}$, but we are only allowed to
do computations in $\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$. For the
product congruence $\theta=\theta_{1}\times\dots\times\theta_{n}$ on
$\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$, we can use the natural
isomorphism

$\mathbf{B}_{1}/\theta_{1}\times\dots\times\mathbf{B}_{n}/\theta_{n}\cong(\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n})/\theta,\quad(b_{1}/\theta_{1},\dots,b_{n}/\theta_{n})\mapsto(b_{1},\dots,b_{n})/\theta$

to view the elements $c_{1},\dots,c_{k},v$ and the subalgebra $\mathbf{D}$ of
$\mathbf{B}_{1}/\theta_{1}\times\dots\times\mathbf{B}_{n}/\theta_{n}$ as those
of $(\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n})/\theta$. Now choose
representatives $a_{1},\dots,a_{k},u\,(\in B_{1}\times\dots\times B_{n})$ from
the $\theta$-classes $c_{1},\dots,c_{k},v$, respectively, and let $\mathbf{B}$
be the subalgebra of $\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$ generated
by the set $\\{a_{1},\dots,a_{k}\\}$. Since the definition of
$\mathbf{B}[\theta]$ in Section 2 implies that $\mathbf{B}[\theta]$ is the
full inverse image of $\mathbf{D}$ under the natural homomorphism

$\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}\twoheadrightarrow(\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n})/\theta\cong\mathbf{B}_{1}/\theta_{1}\times\dots\times\mathbf{B}_{n}/\theta_{n},$

we get that $v\in\mathbf{D}$ if and only if $u\in\mathbf{B}[\theta]$. Hence,
we can decide whether $v$ is in $\mathbf{D}$ by a subpower membership
calculation in $\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$, provided we
can construct a generating set for $\mathbf{B}[\theta]$ from the generating
set $\\{a_{1},\dots,a_{k}\\}$ of $\mathbf{B}$ . We now give such a generating
set explicitly.

######  Theorem 11.

Let $\mathbf{B}$ be a subalgebra of
$\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$ with
$\mathbf{B}_{1},\dots,\mathbf{B}_{n}\in{\mathcal{V}}$ $(n\geq\mathsf{d})$, let
$\theta_{i}\in\operatorname{Con}(\mathbf{B}_{i})$ for all $i\in[n]$, and let
$\theta:=\theta_{1}\times\dots\times\theta_{n}\in\operatorname{Con}(\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n})$.
Assume that $G$ is a generating set for $\mathbf{B}$, and
$\Lambda,\Phi\subseteq B[\theta]$ satisfy the following conditions:

  1. (1)

For every $I\in\binom{[n]}{\mathsf{d}-1}$ and for every $\overline{b}\in
B|_{I}$ and $\overline{c}\in B[\theta]|_{I}$ with
$\overline{b}\equiv_{\theta|_{I}}\overline{c}$ there exist
$b_{I,\overline{b}}\in B$ and $c_{I,\overline{c}}\in\Lambda$ such that

$b_{I,\overline{b}}|_{I}=\overline{b},\quad
c_{I,\overline{c}}|_{I}=\overline{c},\quad\text{and}\quad
b_{I,\overline{b}}\equiv_{\theta}c_{I,\overline{c}}.$

  2. (2)

For every $i\in[n]$ and $(\beta,\gamma)\in\theta_{i}$ with $\beta\in B|_{i}$,
there exist $b_{i,\beta}\in B$ and $c_{i,\gamma}\in\Phi$ such that

$b_{i,\beta}|_{i}=\beta,\quad c_{i,\gamma}|_{i}=\gamma,\quad
b_{i,\beta}|_{[i-1]}=c_{i,\gamma}|_{[i-1]},\quad\text{and}\quad
b_{i,\beta}\equiv_{\theta}c_{i,\gamma}.$

Then $G\cup\Lambda\cup\Phi$ is a generating set for $\mathbf{B}[\theta]$.

######  Proof 3.8.

Let $\mathbf{C}$ denote the subalgebra of
$\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$ generated by
$G\cup\Lambda\cup\Phi$. Clearly,
$\mathbf{B}\leq\mathbf{C}\leq\mathbf{B}[\theta]$. To show that
$\mathbf{C}=\mathbf{B}[\theta]$, choose an arbitrary element $d$ in
$\mathbf{B}[\theta]$. Then there exists $b$ in $\mathbf{B}$ such that
$b\equiv_{\theta}d$. Using that $\Lambda$ satisfies condition (1), choose and
fix elements $b^{I}\in B$ and $d^{I}\in\Lambda$ such that

$b^{I}|_{I}=b|_{I},\quad d^{I}|_{I}=d|_{I},\quad\text{and}\quad
b^{I}\equiv_{\theta}d^{I}\quad\text{for each}\quad
I\in\textstyle{\binom{[n]}{\mathsf{d}-1}}.$

We will use the $P$-terms in Lemma 9 with $e=2$ to show that

$d=T_{n}(v^{(\mathsf{d})},\widehat{v}^{(\mathsf{d})},\dots,v^{(n)},\widehat{v}^{(n)},\overline{d^{I}}^{[n]})$
(18)

holds for appropriately chosen elements
$v^{(\mathsf{d})},\widehat{v}^{(\mathsf{d})},\dots,v^{(n)},\widehat{v}^{(n)}$
in $\mathbf{C}$. Since all $d^{I}$ are in $\Lambda\ (\subseteq\mathbf{C})$,
this will show that $d\in\mathbf{C}$, and hence will complete the proof of the
theorem.

By the definition of the term $T_{\mathsf{d}-1}:=w^{[\mathsf{d}-1]}$ and by
the choice of $b^{[\mathsf{d}-1]}$ and $d^{[\mathsf{d}-1]}$ we have that

$b|_{[\mathsf{d}-1]}=b^{[\mathsf{d}-1]}|_{[\mathsf{d}-1]},\quad
d|_{[\mathsf{d}-1]}=d^{[\mathsf{d}-1]}|_{[\mathsf{d}-1]},$

and

$T_{\mathsf{d}-1}(b^{[\mathsf{d}-1]})=b^{[\mathsf{d}-1]}\equiv_{\theta}d^{[\mathsf{d}-1]}=T_{\mathsf{d}-1}(d^{[\mathsf{d}-1]}).$

Now we proceed by induction to show that for every $m=\mathsf{d},\dots,n$
there exist tuples
$u^{(\mathsf{d})},\widehat{u}^{(\mathsf{d})},\dots,u^{(m)},\widehat{u}^{(m)}$
in $\mathbf{B}$ and tuples
$v^{(\mathsf{d})},\widehat{v}^{(\mathsf{d})},\dots,v^{(m)},\widehat{v}^{(m)}$
in $\mathbf{C}$ such that

$\displaystyle b|_{[m]}$
$\displaystyle{}=T_{m}(u^{(\mathsf{d})},\widehat{u}^{(\mathsf{d})},\dots,u^{(m)},\widehat{u}^{(m)},\overline{b^{I}}^{[m]})|_{[m]},$
(19) $\displaystyle d|_{[m]}$
$\displaystyle{}=T_{m}(v^{(\mathsf{d})},\widehat{v}^{(\mathsf{d})},\dots,v^{(m)},\widehat{v}^{(m)},\overline{d^{I}}^{[m]})|_{[m]},$
(20)

and

$u^{(j)}\equiv_{\theta}v^{(j)},\quad\widehat{u}^{(j)}\equiv_{\theta}\widehat{v}^{(j)}\qquad\text{for
all $j=\mathsf{d},\dots,m$,}$ (21)

hence also

$\qquad(B\ni)\
T_{m}(u^{(\mathsf{d})},\widehat{u}^{(\mathsf{d})},\dots,u^{(m)},\widehat{u}^{(m)},\overline{b^{I}}^{[m]})\\\
\equiv_{\theta}T_{m}(v^{(\mathsf{d})},\widehat{v}^{(\mathsf{d})},\dots,v^{(m)},\widehat{v}^{(m)},\overline{d^{I}}^{[m]})\
(\in C).\qquad$ (22)

Then, equality (20) for $m=n$ yields the desired equality (18).

Our induction hypothesis is that the statement in the preceding paragraph is
true for $m-1$, that is, there exist tuples
$u^{(\mathsf{d})},\widehat{u}^{(\mathsf{d})},\dots,u^{(m-1)},\widehat{u}^{(m-1)}$
in $\mathbf{B}$ and tuples
$v^{(\mathsf{d})},\widehat{v}^{(\mathsf{d})},\dots,v^{(m-1)}$,
$\widehat{v}^{(m-1)}$ in $\mathbf{C}$ such that (19)–(22) hold for $m-1$ in
place of $m$. To simplify notation, let

$\displaystyle b^{(m-1)}$
$\displaystyle{}:=T_{m-1}(u^{(\mathsf{d})},\widehat{u}^{(\mathsf{d})},\dots,u^{(m-1)},\widehat{u}^{(m-1)},\overline{b^{I}}^{[m-1]}),$
$\displaystyle d^{(m-1)}$
$\displaystyle{}:=T_{m-1}(v^{(\mathsf{d})},\widehat{v}^{(\mathsf{d})},\dots,v^{(m-1)},\widehat{v}^{(m-1)},\overline{d^{I}}^{[m-1]}).$

Then we have that $b^{(m-1)}|_{[m-1]}=b|_{[m-1]}$ and
$d^{(m-1)}|_{[m-1]}=d|_{[m-1]}$. Let $\gamma:=b|_{m}$,
$\beta:=b^{(m-1)}|_{m}$, $\tau:=d|_{m}$, and $\sigma:=d^{(m-1)}|_{m}$. If we
can show the existence of a pair of witnesses $u^{(m)},\widehat{u}^{(m)}$ in
$\mathbf{B}$ for the fork
$(\gamma,\beta^{\gamma^{2}})\in\operatorname{\text{\sc fork}}_{m}(B)$ and a
pair of witnesses $v^{(m)},\widehat{v}^{(m)}$ in $\mathbf{C}$ for the fork
$(\tau,\sigma^{\tau^{2}})\in\operatorname{\text{\sc fork}}_{m}(C)$ such that
$u^{(m)}\equiv_{\theta}v^{(m)}$ and
$\widehat{u}^{(m)}\equiv_{\theta}\widehat{v}^{(m)}$, then (21)–(22) will
follow for $m$, and by Lemma 9, (19)–(20) will also hold for $m$.

To prove the existence of such $u^{(m)},\widehat{u}^{(m)}$ and
$v^{(m)},\widehat{v}^{(m)}$, notice first that our induction hypothesis that
(22) holds for $m-1$ in place of $m$ has the effect that $(B\ni)\
b^{(m-1)}\equiv_{\theta}d^{(m-1)}\ (\in C)$, so in particular, $(B|_{m}\ni)\
\beta\equiv_{\theta_{m}}\sigma$. By our choice of $b$ and $d$, we also have
that $(B|_{m}\ni)\ \gamma=b|_{m}\equiv_{\theta_{m}}d|_{m}=\tau$. Thus, by our
assumption (2), there exist witnesses $b_{\beta}:=b_{m,\beta}$ and
$c_{\sigma}:=c_{m,\sigma}\in\Phi$ for the fork
$(\beta,\sigma)\in\operatorname{\text{\sc fork}}_{m}(C)$ such that

$b_{\beta}|_{m}=\beta,\quad c_{\sigma}|_{m}=\sigma,\quad
b_{\beta}|_{[m-1]}=c_{\sigma}|_{[m-1]},\quad\text{and}\quad
b_{\beta}\equiv_{\theta}c_{\sigma}.$ (23)

There also exist witnesses $b_{\gamma}:=b_{m,\gamma}\in B$ and
$c_{\tau}:=c_{m,\tau}\in\Phi$ for the fork
$(\gamma,\tau)\in\operatorname{\text{\sc fork}}_{m}(C)$ such that

$b_{\gamma}|_{m}=\gamma,\quad c_{\tau}|_{m}=\tau,\quad
b_{\gamma}|_{[m-1]}=c_{\tau}|_{[m-1]},\quad\text{and}\quad
b_{\gamma}\equiv_{\theta}c_{\tau}.$ (24)

Let $b_{\beta^{\gamma}}:=p(b_{\beta},b_{\gamma},b_{\gamma})$,
$c_{\beta^{\tau}}:=p(b_{\beta},c_{\tau},c_{\tau})$, and
$c_{\sigma^{\tau}}:=p(c_{\sigma},c_{\tau},c_{\tau})$. Clearly,
$b_{\beta^{\gamma}}\in B$ and $c_{\beta^{\tau}},c_{\sigma^{\tau}}\in C$.
Furthermore, the relations in (23)–(24) imply that

$\quad b_{\beta^{\gamma}}|_{m}=\beta^{\gamma},\quad
c_{\beta^{\tau}}|_{m}=\beta^{\tau},\quad
c_{\sigma^{\tau}}|_{m}=\sigma^{\tau},\\\
b_{\beta^{\gamma}}|_{[m-1]}=c_{\beta^{\tau}}|_{[m-1]}=c_{\sigma^{\tau}}|_{[m-1]},\quad\text{and}\quad
b_{\beta^{\gamma}}\equiv_{\theta}c_{\beta^{\tau}}\equiv_{\theta}c_{\sigma^{\tau}}.\qquad$
(25)

It follows that $c_{\beta^{\tau}}$ and $c_{\sigma^{\tau}}$ are witnesses in
$\mathbf{C}$ for the fork
$(\beta^{\tau},\sigma^{\tau})\in\operatorname{\text{\sc fork}}_{m}(C)$.

Since $b$ and $b^{(m-1)}$ are witnesses in $B$ for the fork
$(\gamma,\beta)\in\operatorname{\text{\sc
fork}}_{m}(B)\subseteq\operatorname{\text{\sc fork}}_{m}(C)$, we can apply
Lemma 4 first to $(\tau,\gamma)$ and $(\beta,\gamma)$ to obtain witnesses

$\displaystyle z$
$\displaystyle{}:=p(p(c_{\tau},b_{\gamma},b),p(c_{\tau},b_{\gamma},b_{\gamma}),c_{\tau})\
(\in C)$ $\displaystyle\widehat{z}$
$\displaystyle{}:=p(b^{(m-1)},c_{\tau},c_{\tau})\ (\in C)$

for the fork $(\tau,\beta^{\tau})\in\operatorname{\text{\sc fork}}_{m}(C)$.
The analogous construction for the forks $(\gamma,\gamma)$ and
$(\beta,\gamma)$ yields witnesses

$\displaystyle w$
$\displaystyle{}:=p(p(b_{\gamma},b_{\gamma},b),p(b_{\gamma},b_{\gamma},b_{\gamma}),b_{\gamma})=p(b,b_{\gamma},b_{\gamma})\
(\in B)$ $\displaystyle\widehat{w}$
$\displaystyle{}:=p(b^{(m-1)},b_{\gamma},b_{\gamma})\ (\in B)$

for the fork $(\gamma,\beta^{\gamma})\in\operatorname{\text{\sc
fork}}_{m}(B)$. Since $w,\widehat{w}$ are obtained from $z,\widehat{z}$ by
replacing $c_{\tau}$ with $b_{\gamma}$, the relation
$b_{\gamma}\equiv_{\theta}c_{\tau}$ in (24) implies that $z\equiv_{\theta}w$
and $\widehat{z}\equiv_{\theta}\widehat{w}$. Applying Lemma 4 again, now to
the forks $(\tau,\beta^{\tau})$ and $(\sigma^{\tau},\beta^{\tau})$, we obtain
witnesses

$\displaystyle v^{(m)}$
$\displaystyle{}:=p(p(z,\widehat{z},c_{\beta^{\tau}}),p(z,\widehat{z},\widehat{z}),z)\
(\in C)$ $\displaystyle\widehat{v}^{(m)}$
$\displaystyle{}:=p(c_{\sigma^{\tau}},z,z)\ (\in C)$

for the fork
$(\tau,\sigma^{\tau^{2}})=(\tau,(\sigma^{\tau})^{\tau})\in\operatorname{\text{\sc
fork}}_{m}(C)$. Similarly, for the corresponding forks
$(\gamma,\beta^{\gamma})$ and $(\beta^{\gamma},\beta^{\gamma})$, we get
witnesses

$\displaystyle u^{(m)}$
$\displaystyle{}:=p(p(w,\widehat{w},b_{\beta^{\gamma}}),p(w,\widehat{w},\widehat{w}),w)\
(\in B)$ $\displaystyle\widehat{u}^{(m)}$
$\displaystyle{}:=p(b_{\beta^{\gamma}},w,w)\ (\in B)$

for the fork
$(\gamma,\beta^{\gamma^{2}})=(\gamma,(\beta^{\gamma})^{\gamma})\in\operatorname{\text{\sc
fork}}_{m}(B)$. Since $u^{(m)}$ and $\widehat{u}^{(m)}$ are obtained from
$v^{(m)}$ and $\widehat{v}^{(m)}$ by replacing $z$ with $w$, $\widehat{z}$
with $\widehat{w}$, and $c_{\sigma^{\tau}},c_{\beta^{\tau}}$ with
$b_{\beta^{\gamma}}$, the relations $z\equiv_{\theta}w$,
$\widehat{z}\equiv_{\theta}\widehat{w}$ proved earlier, and the relations
$b_{\beta^{\tau}}\equiv_{\theta}c_{\beta^{\tau}}\equiv_{\theta}c_{\sigma^{\tau}}$
in (25) imply that $v^{(m)}\equiv_{\theta}u^{(m)}$ and
$\widehat{v}^{(m)}\equiv_{\theta}\widehat{u}^{(m)}$. This completes the
induction for (19)–(22) and the proof of the theorem.

##  4\. Algorithms Involving Compact Representations

Throughout this section we will work under the following global assumptions.

  * •

${\mathcal{V}}$ is a variety in a finite language $F$ with a $\mathsf{d}$-cube
term ($\mathsf{d}>1$),

  * •

$P$ is a $(1,\mathsf{d}-1)$-parallelogram term in ${\mathcal{V}}$ (the
existence of such a term is ensured by Theorem 1), and

  * •

${\mathcal{K}}$ is a finite set of finite algebras in ${\mathcal{V}}$.

Our aim in this section is to use the results of Section 3 to show that

  1. $\blacktriangleright$

the problems $\operatorname{\text{\sc SMP}}({\mathcal{K}})$ and
$\operatorname{\text{\sc SMP}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$ are
polynomial time equivalent (Theorem 17),

  2. $\blacktriangleright$

$\operatorname{\text{\sc SMP}}({\mathcal{K}})$ is in $\mathsf{NP}$ (Theorem
20), and

  3. $\blacktriangleright$

$\operatorname{\text{\sc SMP}}({\mathcal{K}})$ and the problem of finding
compact representations for algebras in $\mathbb{S}\mathbb{P}_{\rm
fin}{\mathcal{K}}$ given by their generators are polynomial time reducible to
each other (Theorem 23).

Recall that if $\mathbf{B}$ is a subalgebra of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ with
$\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{K}}$, then a representation
for $\mathbf{B}$ is a subset $R$ of $B$ satisfying conditions (2)–(3) of
Definition 3 (with $e=1$). Condition (2) in the definition makes sure that for
every $I\subseteq[n]$ with $|I|=\min\\{n,\mathsf{d}-1\\}$ and for every tuple
$\overline{b}\in B|_{I}$ there exists an element $r_{I,\overline{b}}$ in $R$
such that $r_{I,\overline{b}}|_{I}=\overline{b}$. Similarly, condition (3)
makes sure that for every derived fork
$(\gamma,\delta)\in\operatorname{\text{\sc fork}}^{\prime}_{i}(B)$ ($i\in[n]$)
there exist elements $u_{i,\gamma,\delta},\widehat{u}_{i,\gamma,\delta}$ in
$R$ which witness that $(\gamma,\delta)\in\operatorname{\text{\sc
fork}}_{i}(R)$. For some of the algorithms we are going to discuss, it will be
convenient to fix these choices for witnesses in $R$. This motivates our
definition of a standardized representation below.

Before the definition, let us note that if $n<\mathsf{d}$, condition (2)
forces $R=B$, so finding representations for $\mathbf{B}$ in this case is
trivial. Therefore, we will assume that $n\geq\mathsf{d}$. Then, by condition
(2), we have $R|_{[\mathsf{d}-1]}=B|_{[\mathsf{d}-1]}$, hence one can easily
find witnesses among the elements $r_{[\mathsf{d}-1],\overline{b}}\in R$ for
the forks in coordinates $i\in[\mathsf{d}-1]$. Therefore, witnesses for forks
are of interest only in coordinates $i=\mathsf{d},\mathsf{d}+1,\dots,n$. (See
also Lemma 10.)

For a subalgebra $\mathbf{B}$ of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ with
$\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{K}}$ ($n\geq\mathsf{d}$), we
will call a representation $R$ for $\mathbf{B}$ a _standardized representation
for $\mathbf{B}$_ if the following conditions are satisfied:

  1. (1)

For every $I\subseteq[n]$ with $|I|=\mathsf{d}-1$ and for every tuple
$\overline{b}\in B|_{I}$, an element $r_{I,\overline{b}}$ of $R$ is fixed so
that $r_{I,\overline{b}}|_{I}=\overline{b}$; this element will be referred to
as _the designated witness in $R$ for $\overline{b}\in R|_{I}$_.

  2. (2)

For every $m$ ($\mathsf{d}\leq m\leq n$) there is a set $F_{m}$ with
$\operatorname{\text{\sc fork}}^{\prime}_{m}(B)\subseteq
F_{m}\subseteq\operatorname{\text{\sc fork}}_{m}(R)$ such that for every
$(\gamma,\delta)\in F_{m}$ a pair
$(u_{m,\gamma,\delta},\widehat{u}_{m,\gamma,\delta})$ in $R^{2}$ is fixed
which witnesses that $(\gamma,\delta)\in\operatorname{\text{\sc
fork}}_{m}(R)$; these elements
$u_{m,\gamma,\delta},\widehat{u}_{m,\gamma,\delta}$ will be referred to as
_the designated witnesses in $R$ for
$(\gamma,\delta)\in\operatorname{\text{\sc fork}}_{m}(R)$_.

  3. (3)

Every element of $R$ has at least one designation.

We will refer to the designated witnesses in (1) and (2) as _local witnesses
for $\mathbf{B}$_ and _fork witnesses for $\mathbf{B}$, respectively._

Formally, a standardized representation for $\mathbf{B}$ is the representation
$R$ together with a _designation function_

$\Bigl{(}\bigl{\\{}(I,\overline{b}):I\in{\textstyle\binom{[n]}{\mathsf{d}-1}},\,\overline{b}\in
B|_{I}\bigr{\\}}\sqcup\bigcup_{m=\mathsf{d}}^{n}\bigl{(}\\{m\\}\times
F_{m}\times[2]\bigr{)}\Bigr{)}\to R,\\\ (I,\overline{b})\mapsto
r_{I,\overline{b}},\ (m,(\gamma,\delta),1)\mapsto u_{m,\gamma,\delta},\
(m,(\gamma,\delta),2)\mapsto\widehat{u}_{m,\gamma,\delta}$ (26)

where the notation is the same as in Definition 4 (1)–(2), and $\sqcup$
denotes disjoint union. Condition (3) in the definition requires the
designation function to be onto. For our purposes in this paper it will be
sufficient to treat the designation function of a standardized representation
informally, as we did in Definition 4.

######  Remark 12.

It is clear that under the assumptions of Definition 4 a standardized
representation for $\mathbf{B}$ is compact. Moreover, it follows from Lemma 10
that if $R$ is a standardized representation for $\mathbf{B}$, then the
equality (17) in Lemma 9 (with $e=1$) holds provided

  * •

$\overline{b^{I}}$ is an enumeration of the elements $b^{I}$ of $R$ designated
to witness $b^{I}|_{I}=b|_{I}$ for all $I\in\binom{[n]}{\mathsf{d}-1}$; and

  * •

for every $\mathsf{d}\leq m\leq n$, the pair $(u^{(m)},\widehat{u}^{(m)})$ is
the designated witness in $R$ for the fork
$(\gamma,\beta^{\gamma})\in\operatorname{\text{\sc fork}}_{m}(R)$ where
$\gamma$ and $\beta$ are determined by (15).

Now we are ready to describe in more detail what we mean by the problem of
finding compact representations for algebras in $\mathbb{S}\mathbb{P}_{\rm
fin}{\mathcal{K}}$ given by their generators:

$\operatorname{\text{\sc CompactRep}}({\mathcal{K}})$:

  * •

INPUT: $a_{1},\dots,a_{k}\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
with $\mathbf{A}_{1},\ldots,\mathbf{A}_{n}\in{\mathcal{K}}$
($n\geq\mathsf{d}$).

  * •

OUTPUT: A standardized representation for the subalgebra of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ generated by
$\\{a_{1},\dots,a_{k}\\}$.

In Subsections 4.3 and 4.5 below we will discuss two different algorithms for
solving $\operatorname{\text{\sc CompactRep}}({\mathcal{K}})$. The idea of the
first algorithm (Algorithm 4) will be key to showing in Subsection 4.4 that
$\operatorname{\text{\sc SMP}}({\mathcal{K}})$ is in $\mathsf{NP}$. The second
algorithm (Algorithm 5), on the other hand, will use $\operatorname{\text{\sc
SMP}}({\mathcal{K}})$ to solve $\operatorname{\text{\sc
CompactRep}}({\mathcal{K}})$. Prior to our first algorithm for
$\operatorname{\text{\sc CompactRep}}({\mathcal{K}})$ we will introduce two
auxiliary algorithms (Subsection 4.1), and then prove in Subsection 4.2 that
the problems $\operatorname{\text{\sc SMP}}({\mathcal{K}})$ and
$\operatorname{\text{\sc SMP}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$ are
polynomial time equivalent.

###  4.1. Two auxiliary algorithms

When we construct standardized representations, the following concepts will be
useful.

Let $\mathbf{A}_{1},\ldots,\mathbf{A}_{n}\in{\mathcal{K}}$ with
$n\geq\mathsf{d}$, and let
$R\subseteq\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$. We will call $R$ a
_partial standardized representation_ if every element of $R$ is designated to
witness either $\overline{b}\in R|_{I}$ for some
$I\in\binom{[n]}{\mathsf{d}-1}$ or a fork in $\operatorname{\text{\sc
fork}}_{m}(R)$ for some $m$ ($\mathsf{d}\leq m\leq n$).

If $R$ is a partial standardized representation that is contained in a
subalgebra $\mathbf{B}$ of $\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$, we
may refer to $R$ as a _partial standardized representation for $\mathbf{B}$_.
If, in addition, $R$ satisfies condition (1) of Definition 4, we will say that
_$R$ contains a full set of designated local witnesses for $\mathbf{B}$_.

Similarly to standardized representations, a partial standardized
representation is formally defined to be a set $R$ satisfying the requirements
of Definition 4.1, together with a _designation function_ , which is a
function mapping onto $R$, similar to (26), but the domain is a subset of the
set

$\Bigl{\\{}(I,\overline{b}):I\in{\textstyle\binom{[n]}{\mathsf{d}-1}},\,\overline{b}\in\prod_{i\in
I}\mathbf{A}_{i}\Bigr{\\}}\sqcup\bigcup_{m=\mathsf{d}}^{n}\bigl{(}\\{m\\}\times
A_{m}^{2}\times[2]\bigr{)}.$

If $R$ is a partial standardized representation for a subalgebra $\mathbf{B}$
of $\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$, then the domain of its
designation function is a subset of the domain indicated in (26). Although we
will usually treat the designation functions of partial standardized
representations $R$ informally, we will consider the size of $R$ to be the
size of the domain of its designation function (not just the cardinality of
the set $R$). In particular, if $R$ is a partial standardized representation
for a subalgebra $\mathbf{B}$ of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ such that $R$ contains a full
set of designated local witnesses for $\mathbf{B}$, then its size is
$\Theta(n^{\mathsf{d}-1})$.

Let $\mathbf{A}_{1},\ldots,\mathbf{A}_{n}\in{\mathcal{K}}$ with
$n\geq\mathsf{d}$, let
$R\subseteq\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ be a partial
standardized representation, and let
$b\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$. We will say that _$b$ is
representable by $R$_ if the following conditions are met:

  1. (1)

for each $I\in\binom{[n]}{\mathsf{d}-1}$, $R$ contains elements $b^{I}$
designated to witness $b^{I}|_{I}=b|_{I}$, and

  2. (2)

for every $\mathsf{d}\leq m\leq n$, $R$ contains designated witnesses
$u^{(m)},\widehat{u}^{(m)}$ for the fork $(\gamma,\beta^{\gamma})$ where
$\beta,\gamma$ are as defined in (15) (with $e=1$).

We will say that _$b$ is completely representable by $R$_ if condition (1) and
the following stronger version of (2) hold:

  1. (2)c

for every $\mathsf{d}\leq m\leq n$, $R$ contains designated witnesses
$u^{(m)},\widehat{u}^{(m)}$ and $v^{(m)},\widehat{v}^{(m)}$ for the forks
$(\gamma,\beta^{\gamma})$ and $(\gamma,\beta)$ in $\operatorname{\text{\sc
fork}}_{m}(R)$ where $\beta,\gamma$ are as defined in (15) (with $e=1$).

The following fact is an easy consequence of Lemma 9.

######  Corollary 13.

Let $R\subseteq\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
$(\mathbf{A}_{1},\ldots,\mathbf{A}_{n}\in{\mathcal{K}},\ n\geq\mathsf{d})$ be
a partial standardized representation. If an element
$b\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ is representable by $R$,
then the equality in (17) holds for $b$ $($with $e=1)$, and hence $b$ is in
the $P$-subalgebra of $\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
generated by $R$.

The proof of Lemma 9 can easily be turned into a polynomial time algorithm for
solving the following problem.

$\operatorname{\text{\sc IsRepresentable}}({\mathcal{K}})$:

  * •

INPUT: $b\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ ($n\geq\mathsf{d}$)
and a partial standardized representation
$R\subseteq\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
($\mathbf{A}_{1},\ldots,\mathbf{A}_{n}\in{\mathcal{K}}$) such that $R$
contains elements $b^{I}$ designated to witness $b^{I}|_{I}=b|_{I}$ for each
$I\in\binom{[n]}{\mathsf{d}-1}$.

  * •

OUTPUT: (YES, $\emptyset$, $S$) or (NO, $S^{\prime}$, $S$) where
$S^{\prime},S\,(\subseteq\langle R\cup\\{b\\}\rangle_{P})$ are lists of
designated witnesses (missing from $R$) for the derived forks and for the
forks that are not derived forks, respectively, so that $b$ becomes
representable(completely representable) by the partial standardized
representation $R\cup S^{\prime}$ ($R\cup S^{\prime}\cup S$, respectively).

Note that the designated witnesses (for forks that are not derived forks)
collected in the set $S$ do not play a role in determining whether or not $b$
is representable, but they will be useful in other algorithms that call
$\operatorname{\text{\sc IsRepresentable}}({\mathcal{K}})$.

######  Lemma 14.

Algorithm 1 solves $\operatorname{\text{\sc IsRepresentable}}({\mathcal{K}})$
in polynomial time.

Algorithm 1 For $\operatorname{\text{\sc IsRepresentable}}({\mathcal{K}})$

0: $b\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ and a partial
standardized representation
$R\subseteq\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
($\mathbf{A}_{1},\ldots,\mathbf{A}_{n}\in{\mathcal{K}}$, $n\geq\mathsf{d}$)
such that $R$ contains elements $b^{I}$ designated to witness
$b^{I}|_{I}=b|_{I}$ for each $I\in\binom{[n]}{\mathsf{d}-1}$

0: (YES, $\emptyset$, $S$) or (NO, $S^{\prime}$, $S$) where
$S^{\prime},S\,(\subseteq\langle R\cup\\{b\\}\rangle_{P})$ are lists of
designated witnesses (missing from $R$) for the derived forks and for the
forks that are not derived forks, respectively, so that $b$ becomes
representable (completely representable) by the partial standardized
representation $R\cup S^{\prime}$ ($R\cup S^{\prime}\cup S$, respectively)

1: $S:=\emptyset$, $S^{\prime}:=\emptyset$,

2: $b^{(\mathsf{d}-1)}:=b^{[\mathsf{d}-1]}$

3: for $m=\mathsf{d},\dots,n$ do

4: $\beta:=b^{(m-1)}|_{m}$, $\gamma:=b|_{m}$, $c:=p(b^{(m-1)},b,b)$

5: if $R\cup S^{\prime}$ has no designated witnesses for
$(\gamma,\beta^{\gamma})\in\operatorname{\text{\sc fork}}_{m}(R\cup
S^{\prime})$ then

6: add $b,c$ to $S^{\prime}$ as designated witnesses for
$(\gamma,\beta^{\gamma})\in\operatorname{\text{\sc fork}}_{m}(R\cup
S^{\prime})$

7: end if

8: if $R\cup S^{\prime}\cup S$ has no designated witnesses for
$(\gamma,\beta)\in\operatorname{\text{\sc fork}}_{m}(R\cup S^{\prime}\cup S)$
then

9: add $b,b^{(m-1)}$ to $S$ as designated witnesses for
$(\gamma,\beta)\in\operatorname{\text{\sc fork}}_{m}(R\cup S^{\prime}\cup S)$

10: end if

11: let $u,\widehat{u}\in R\cup S^{\prime}$ be the designated witnesses for
$(\gamma,\beta^{\gamma})\in\operatorname{\text{\sc fork}}_{m}(R\cup
S^{\prime})$

12: $b^{(m)}=t_{m}(b^{(m-1)},\widehat{u},u,\overline{b^{I}}^{[m]})$

13: end for

14: if $S^{\prime}=\emptyset$ then

15: return (YES, $S^{\prime}$, $S$)

16: else

17: return (NO, $S^{\prime}$, $S$)

18: end if

######  Proof 4.1.

First we prove that Algorithm 1 is correct. In Step 2, $b^{[\mathsf{d}-1]}\in
R$ is the designated witness for
$b^{[\mathsf{d}-1]}|_{[\mathsf{d}-1]}=b|_{[\mathsf{d}-1]}$. The loop in Steps
3–13 follows the induction in the proof of Lemma 9 (with $e=1$). For each
$m=\mathsf{d},\dots,n$, if $b^{(m-1)}$, $S^{\prime}$ and $S$ (with
$S^{\prime}=S=\emptyset$ for $m=\mathsf{d}$ by Step 1) have been constructed
such that $S^{\prime},S\subseteq\langle R\cup\\{b\\}\rangle_{P}$,
$b^{(m-1)}\in\langle R\cup S^{\prime}\rangle_{P}$,and
$b^{(m-1)}|_{[m-1]}=b|_{[m-1]}$, then to construct
$b^{(m)}=t_{m}(b^{(m-1)},\widehat{u},u,\overline{b^{I}}^{[m]})$ we need
designated witnesses $u$, $\widehat{u}$ for the fork
$(\gamma,\beta^{\gamma})\in\operatorname{\text{\sc fork}}_{m}(R\cup
S^{\prime})$ where $\gamma=b|_{m}$ and $\beta=b^{(m-1)}|_{m}$. Furthermore,
for $b$ to be completely representable by $R\cup S^{\prime}\cup S$, we need
designated witnesses $v$, $\widehat{v}$ for the fork
$(\gamma,\beta)\in\operatorname{\text{\sc fork}}_{m}(R\cup S^{\prime}\cup S)$.

Clearly, $b,b^{(m-1)}$ witness the fork
$(\gamma,\beta)\in\operatorname{\text{\sc fork}}_{m}(\langle
R\cup\\{b\\}\rangle_{B})$. It follows that $b$ and $c=p(b^{(m-1)},b,b)$
witness the derived fork $(\gamma,\beta^{\gamma})\in\operatorname{\text{\sc
fork}}^{\prime}_{m}(\langle R\cup\\{b\\}\rangle_{P})$, because
$c|_{[m-1]}=p(b^{(m-1)},b,b)|_{[m-1]}=p(b,b,b)|_{[m-1]}=b|_{[m-1]}$ and
$b|_{m}=\gamma$,
$c|_{m}=p(b^{(m-1)},b,b)|_{m}=p(\beta,\gamma,\gamma)=\beta^{\gamma}$.
Therefore, if the required designated witnesses $u,\widehat{u}$ do not exist
in $R\cup S^{\prime}$, the algorithm (in Steps 5–7) correctly adds $b,c$ to be
the designated witnesses. Similarly, if the required designated witnesses
$v,\widehat{v}$ do not exist in $R\cup S^{\prime}\cup S$, the algorithm (in
Steps 8–10) correctly adds $b,b^{(m-1)}$ to be the designated witnesses.
Notice also that the updated versions $S^{\prime}$ and $S$ maintain the
property $S^{\prime},S\subseteq\langle R\cup\\{b\\}\rangle_{P}$ when the loop
starts over (if $m<n$) or ends (if $m=n$) after computing $b^{(m)}$ in Step
12.

Thus, the standardized representations $R\cup S^{\prime}$ and $R\cup
S^{\prime}\cup S$ satisfy the requirements that $b$ is representable by $R\cup
S^{\prime}$ and completely representable by $R\cup S^{\prime}\cup S$. Since
new designated fork witnesses (at most one pair for each
$m=\mathsf{d},\dots,n$) are added to $S^{\prime}$ or $S$ only if such
witnesses do not exist, but are necessary for the (complete) representability
of $b$, we see that $b$ is representable by $R$ if and only if
$S^{\prime}=\emptyset$. This proves the correctness of Algorithm 1.

To estimate the running time of Algorithm 1, notice that Step 1 requires
constant time, while Steps 2 and 14–18 can be done in time $O(n|R|)$ and
$O(n|S|+n|S^{\prime}|)$, respectively, where $|R|+|S|+|S^{\prime}|\leq
O(n^{\mathsf{d}-1})$. Finally, by Lemma 8 (2) (with $e=1$), if $b$ is
representable by $R$, the computations in the loop in Steps 3–13 require
$O(n^{\mathsf{d}+1})$ applications of $P$. So Steps 3–16 (including the search
for witnesses for forks in $R$) can be done in $O(n^{\mathsf{d}+2})$ time. If
$b$ is not representable by $R$, essentially the same computation is
performed, so the bound $O(n^{\mathsf{d}+2})$ applies in this case as well.
This proves that Algorithm 1 runs in time $O(n^{\mathsf{d}+2})$.

######  Remark 15.

The definition of the $P$-term $T_{n}$ shows that Algorithm 1 may be viewed as
doing the following two computations simultaneously, when it is run on the
inputs $b$ and $R$:

  * •

it evaluates the $P$-term $T_{n}$ (for $e=1$) step-by-step on the tuple
$\overline{b^{I}}$ of designated local witnesses in $R$ and on appropriately
chosen designated fork witnesses
$u^{(\mathsf{d})},\widehat{u}^{(\mathsf{d})},\dots,u^{(n)},\widehat{u}^{(n)}$
to obtain the elements

$b^{(m)}=T_{m}(u^{(\mathsf{d})},\widehat{u}^{(\mathsf{d})},\dots,u^{(m)},\widehat{u}^{(m)},\overline{b^{I}}^{[m]}),\quad
m=\mathsf{d},\dots,n,$

which, for $m=n$, yields the desired representation

$b=T_{n}(u^{(\mathsf{d})},\widehat{u}^{(\mathsf{d})},\dots,u^{(n)},\widehat{u}^{(n)},\overline{b^{I}})$

of $b$;

  * •

at each step, to be able to evaluate $T_{m}$, it produces (namely, it finds in
$R\cup S^{\prime}$ or, if missing, adds to $S^{\prime}$) the designated fork
witnesses $u^{(m)},\widehat{u}^{(m)}$ for derived forks needed for the
evaluation of $T_{m}$, and does the same with the designated fork witnesses
for the corresponding non-derived forks.

So, in addition to some book-keeping to ensure that the necessary designated
fork witnesses (and nothing else) get into the sets $S^{\prime}$ and $S$, the
computations done by Algorithm 1 in the algebra
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ can be performed by a
$P$-circuit $\mathsf{Circ}(T_{n})$ for $T_{n}$, which is expanded at each node
that produces an element $b^{(m-1)}$ ($m=\mathsf{d},\dots,n$) by a single
$P$-gate that also computes $p(b^{(m-1)},b,b)$ (see the definition of $p$ in
(4)). We will denote this expanded circuit by $\mathsf{Circ}^{+}(T_{n})$.
Since $\mathsf{Circ}^{+}(T_{n})$ is obtained from $\mathsf{Circ}(T_{n})$ by
adding at most $n-\mathsf{d}+1$ $P$-gates, it follows from (14) (and $e=1$)
that $\mathsf{Circ}^{+}(T_{n})$ has size
$O(n^{\mathsf{d}+1})+O(n)=O(n^{\mathsf{d}+1})$.

Now we define another problem which will be useful in constructing
standardized representations for subalgebras of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
($\mathbf{A}_{1}\dots,\mathbf{A}_{n}\in{\mathcal{K}}$), and also for the
polynomial time reduction of $\operatorname{\text{\sc
SMP}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$ to $\operatorname{\text{\sc
SMP}}({\mathcal{K}})$:

$\operatorname{\text{\sc LocalRep}}({\mathcal{K}})$:

  * •

INPUT: $a_{1},\dots,a_{k}\in\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$
with $\mathbf{B}_{1},\dots,\mathbf{B}_{n}\in\mathbb{S}{\mathcal{K}}$
($n\geq\mathsf{d}$), and $\theta=\theta_{1}\times\dots\times\theta_{n}$ with
$\theta_{i}\in\operatorname{Con}(\mathbf{B}_{i})$ for all $i\in[n]$. (Let
$\mathbf{B}$ denote the subalgebra of
$\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$ generated by
$\\{a_{1},\dots,a_{k}\\}$.)

  * •

OUTPUT: Partial standardized representation $R$ for the $\theta$-saturation
$\mathbf{B}[\theta]$ of $\mathbf{B}$ such that $R$ is a full set of designated
local witnesses for $\mathbf{B}[\theta]$, and whenever
$r_{I,\overline{b}},r_{I,\overline{d}}\in R$ are designated to witness
$r_{I,\overline{b}}|_{I}=\overline{b}$ and
$r_{I,\overline{d}}|_{I}=\overline{d}$ where $\overline{b}\in\mathbf{B}|_{I}$
and $\overline{b}\equiv_{\theta|_{I}}\overline{d}$, then
$r_{I,\overline{b}}\equiv_{\theta}r_{I,\overline{d}}$.

In particular, if $\theta_{i}=0$ for all $i\in[n]$, then the latter condition
holds vacuously for $R$, therefore the output of $\operatorname{\text{\sc
LocalRep}}({\mathcal{K}})$ is the subset $R$ of a standardized representation
for $\mathbf{B}$, which is a full set of designated local witnesses for
$\mathbf{B}$.

######  Lemma 16.

Algorithm 2 solves $\operatorname{\text{\sc LocalRep}}({\mathcal{K}})$ in
polynomial time.

Algorithm 2 For $\operatorname{\text{\sc LocalRep}}({\mathcal{K}})$

0: $a_{1},\dots,a_{k}\in\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$ with
$\mathbf{B}_{1},\dots,\mathbf{B}_{n}\in\mathbb{S}{\mathcal{K}}$, and
$\theta=\theta_{1}\times\dots\times\theta_{n}$ with
$\theta_{i}\in\operatorname{Con}(\mathbf{B}_{i})$ for all $i\in[n]$
($n\geq\mathsf{d}$). (Let $\mathbf{B}$ denote the subalgebra of
$\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$ generated by
$\\{a_{1},\dots,a_{k}\\}$.)

0: $R$ is a partial standardized representation for $\mathbf{B}[\theta]$ such
that $R$ is a full set of designated local witnesses for $\mathbf{B}[\theta]$,
and whenever $r_{I,\overline{b}},r_{I,\overline{d}}\in R$ are designated to
witness $r_{I,\overline{b}}|_{I}=\overline{b}$ and
$r_{I,\overline{d}}|_{I}=\overline{d}$ where $\overline{b}\in\mathbf{B}|_{I}$
and $\overline{b}\equiv_{\theta|_{I}}\overline{d}$, then
$r_{I,\overline{b}}\equiv_{\theta}r_{I,\overline{d}}$.

1: $R:=\emptyset$

2: for $I\in\binom{[n]}{\mathsf{d}-1}$ do

3: generate $\mathbf{B}|_{I}$ by $\\{a_{1}|_{I},\dots,a_{k}|_{I}\\}$, and
simultaneously,

4: for each $\overline{b}\in\mathbf{B}|_{I}\setminus R|_{I}$ do

5: find an element $r_{I,\overline{b}}\in\mathbf{B}$ such that
$r_{I,\overline{b}}|_{I}=\overline{b}$, include it in $R$, and designate it to
witness $\overline{b}\in R|_{I}$

6: for all $\overline{d}\in\prod_{i\in I}\mathbf{B}_{i}$ such that
$\overline{d}\not=\overline{b}$ and
$\overline{d}|_{j}\equiv_{\theta_{j}}\overline{b}|_{j}$ for all $j\in I$ do

7: include in $R$ the tuple $r_{I,\overline{d}}$ defined by
$r_{I,\overline{d}}|_{I}=\overline{d}$ and $r_{I,\overline{d}}|_{[n]\setminus
I}=r_{I,\overline{b}}|_{[n]\setminus I}$ as a designated witness for
$\overline{d}\in R|_{I}$

8: end for

9: end for

10: end for

######  Proof 4.2.

The correctness of Algorithm 2 is straightforward to check. To estimate its
running time, notice that Step 1 requires constant time, and in Steps 3–9,
each subalgebra $\mathbf{B}|_{I}$ can be generated in a constant number of
steps that depends on ${\mathcal{K}}$ only (and is independent of the size of
the input). Therefore, the running time of the algorithm is determined by the
number $\binom{n}{\mathsf{d}-1}=O(n^{\mathsf{d}-1})$ of iterations of the
outermost loop (Steps 2–10) and the time needed for computing the designated
witnesses that are added to $R$ in each iteration (Steps 3–9) of the loop,
which is bounded above by $O(n)$. Thus, Algorithm 2 runs in
$O(n^{\mathsf{d}})$ time.

###  4.2. The equivalence of $\operatorname{\text{\sc SMP}}({\mathcal{K}})$
and $\operatorname{\text{\sc SMP}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$

In this subsection we prove that the answer to Question 2 in the Introduction
is YES.

######  Theorem 17.

The decision problems $\operatorname{\text{\sc SMP}}({\mathcal{K}})$ and
$\operatorname{\text{\sc SMP}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$ are
polynomial time equivalent.

Algorithm 3 Reduction of $\operatorname{\text{\sc
SMP}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$ to $\operatorname{\text{\sc
SMP}}({\mathcal{K}})$

0: $c_{1},\dots,c_{k},c_{k+1}\in\mathbf{C}_{1}\times\dots\times\mathbf{C}_{n}$
with
$\mathbf{C}_{1},\dots,\mathbf{C}_{n}\in\mathbb{H}\mathbb{S}{\mathcal{K}}$,
$n\geq\mathsf{d}$

0: Is $c_{k+1}$ in the subalgebra $\mathbf{D}$ of
$\mathbf{C}_{1}\times\dots\times\mathbf{C}_{n}$ generated by
$c_{1},\dots,c_{k}$?

1: for $i=1,\dots,n$ do

2: find $\mathbf{A}_{i}\in{\mathcal{K}}$, $\mathbf{B}_{i}\leq\mathbf{A}_{i}$
and $\theta_{i}\in\operatorname{Con}(\mathbf{B}_{i})$ such that
$\mathbf{C}_{i}=\mathbf{B}_{i}/\theta_{i}$

3: end for

4: for $j=1,\dots,k+1$ do

5: find $a_{j}\in B_{1}\times\dots\times B_{n}$ such that
$a_{j}/(\theta_{1}\times\dots\times\theta_{n})=c_{j}$

6: end for

7: $G:=\\{a_{1},\dots,a_{k}\\}$ (let $\mathbf{B}$ denote the subalgebra of
$\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$ generated by $G$)

8: Run $\operatorname{\text{\sc LocalRep}}({\mathcal{K}})$ with the input
$a_{1},\dots,a_{k}\in\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$,
$\theta_{i}\in\operatorname{Con}(\mathbf{B}_{i})$ ($i\in[n]$) to get output
$R$ (a set; the designations will not play a role)

9: $\Lambda:=R$, $\Phi:=\emptyset$

10: for $i=1,\dots,n$ do

11: generate $\mathbf{B}|_{i}$ by $G|_{i}=\\{a_{1}|_{i},\dots,a_{k}|_{i}\\}$,
and simultaneously,

12: for each new $\beta$ in $\mathbf{B}|_{i}$ do

13: find an element $b_{i,\beta}$ generated by $a_{1},\dots,a_{k}$ satisfying
$b_{i,\beta}|_{i}=\beta$

14: for all $\gamma\equiv_{\theta_{i}}\beta$ ($\gamma\in B_{i}$) do

15: add to $\Phi$ the tuple $c_{i,\gamma}$ defined by
$c_{i,\gamma}|_{i}=\gamma$ and
$c_{i,\gamma}|_{[n]\setminus\\{i\\}}=b_{i,\beta}|_{[n]\setminus\\{i\\}}$

16: end for

17: end for

18: end for

19: run $\operatorname{\text{\sc SMP}}({\mathcal{K}})$ with the input
$G\cup\Lambda\cup\Phi\subseteq\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
and $a_{k+1}\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
($\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{K}}$), to get an answer
$\textsf{A}=\textrm{YES}$ or $\textsf{A}=\textrm{NO}$

20: return A

######  Proof 4.3.

$\operatorname{\text{\sc SMP}}({\mathcal{K}})$ is a subproblem of
$\operatorname{\text{\sc SMP}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$, so
$\operatorname{\text{\sc SMP}}({\mathcal{K}})$ is clearly polynomial time
reducible to $\operatorname{\text{\sc
SMP}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$. For the converse we will show that
Algorithm 3 reduces $\operatorname{\text{\sc
SMP}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$ to $\operatorname{\text{\sc
SMP}}({\mathcal{K}})$ in polynomial time.

In Steps 1–3 Algorithm 3 finds the algebras $\mathbf{A}_{i}\in{\mathcal{K}}$,
their subalgebras $\mathbf{B}_{i}$ and their congruences $\theta_{i}$ such
that the algebras $\mathbf{C}_{i}$ in the input are
$\mathbf{C}_{i}=\mathbf{B}_{i}/\theta_{i}$ ($i\in[n]$). In Steps 4–6 tuples
$a_{1},\dots,a_{k+1}\in\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$
$(\leq\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n})$ are found such that for
the product congruence $\theta:=\theta_{1}\times\dots\times\theta_{n}$ we have
$c_{j}=a_{j}/\theta$ for all $j\in[k+1]$. Thus, as we explained in the
paragraph preceding Theorem 11, the set $G=\\{a_{1},\dots,a_{k}\\}$ obtained
in Step 7 is a generating set for a subalgebra $\mathbf{B}$ of
$\mathbf{B}_{1}\times\dots\times\mathbf{B}_{n}$ with the following properties:
$\mathbf{B}[\theta]/\theta{}\cong{}\mathbf{D}$, and $c_{k+1}\in\mathbf{D}$ if
and only if $a_{k+1}\in\mathbf{B}[\theta]$. Therefore, Algorithm 3 gives the
correct answer in Steps 19–20, provided the set $G\cup\Lambda\cup\Phi$
produced earlier in the process is a generating set for $\mathbf{B}[\theta]$.

By Theorem 11 it suffices to check that the set $\Lambda$ constructed in Steps
8–9 satisfies condition (1), while the set $\Phi$ constructed in Steps 9–18
satisfies condition (2) in Theorem 11. For $\Lambda$ this is straightforward
to check. For $\Phi$ note that, given $i\in[n]$ and $\beta\in B|_{i}$ as in
the loop 10–18, the tuple $b_{i,\beta}$ obtained in line 13 belongs to
$\mathbf{B}$. Hence, when the for loop in Steps 14–16 is performed for
$\gamma=\beta$, we get the tuple $c_{i,\beta}=b_{i,\beta}\in B$, which is
added to $\Phi$. This tuple can serve as the tuple denoted $b_{i,\beta}$ in
condition (2) for every $c_{i,\gamma}$ added to $\Phi$ in Steps 14–16. This
shows that the set $\Phi$ constructed in Steps 9–18 satisfies condition (2) in
Theorem 11, and hence finishes the proof of the correctness of Algorithm 3.

Steps 1–7 run in $O(kn)$ time, Steps 8–9 in $O(n^{\mathsf{d}})$ time, while
Steps 10–18 in $O(n^{2})$ time. So, the reduction of $\operatorname{\text{\sc
SMP}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$ to $\operatorname{\text{\sc
SMP}}({\mathcal{K}})$ takes $O(kn^{\mathsf{d}})$ time. For an input of size
$O(kn)$ of $\operatorname{\text{\sc SMP}}(\mathbb{H}\mathbb{S}{\mathcal{K}})$
we get an input of size $O(kn^{\mathsf{d}})$ for $\operatorname{\text{\sc
SMP}}({\mathcal{K}})$.

###  4.3. Finding compact representations: A direct algorithm

Our aim in this subsection is to present an algorithm for
$\operatorname{\text{\sc CompactRep}}({\mathcal{K}})$, which does not rely on
$\operatorname{\text{\sc SMP}}({\mathcal{K}})$. The idea of the algorithm will
be used in the next subsection to prove that $\operatorname{\text{\sc
SMP}}({\mathcal{K}})\in\mathsf{NP}$. A different algorithm for
$\operatorname{\text{\sc CompactRep}}({\mathcal{K}})$, which does rely on
$\operatorname{\text{\sc SMP}}({\mathcal{K}})$, will be presented in
Subsection 4.5.

Recall from Definitions 3 and 4 that if $\mathbf{B}$ is a subalgebra of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
($\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{K}}$, $n\geq\mathsf{d}$),
then for a set $R\subseteq\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ to be
a standardized representation for $\mathbf{B}$, it has to satisfy three
conditions: (i) $R\subseteq\mathbf{B}$ and each element in $R$ has a
designation, (ii) $R$ contains a full set of local witnesses for $\mathbf{B}$,
and (iii) $R$ contains witnesses for all derived forks (and possible some non-
derived forks) of $\mathbf{B}$ in coordinates $\geq\mathsf{d}$. Algorithm 2
(with all $\theta_{i}=0$) yields, in polynomial time, a partial standardized
representation $R_{0}$ consisting of a full set of designated local witnesses
for $\mathbf{B}$. Therefore, the task we are left with is to find a way to
expand $R_{0}$ to $R$ so that both conditions (i) and (iii) are met. To
enforce (i) without relying on $\operatorname{\text{\sc SMP}}({\mathcal{K}})$
we have to make sure that every new element we are adding to $R$ is obtained
by applying operations of $\mathbf{B}$ to elements of $R$ or the given
generators of $\mathbf{B}$. To achieve (iii), we need to ensure that we add
sufficiently many elements to get designated witnesses for all derived forks
of $\mathbf{B}$ in coordinates $\geq\mathsf{d}$. The next lemma shows how this
can be done.

######  Lemma 18.

Let $\mathbf{B}$ be a subalgebra of a product
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ with
$\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{K}}$, $n\geq\mathsf{d}$, and
assume that
$R_{1},R_{2}\subseteq\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ are
partial standardized representations which satisfy conditions (1)–(3) below:

  1. (1)

$R_{1}\subseteq R_{2}\subseteq\mathbf{B}$ and the designation function for
$R_{2}$ extends the designation function for $R_{1}$.

  2. (2)

Every element of $\mathbf{B}$ is completely representable by $R_{1}$ (in
particular, $R_{1}$ contains a full set of designated local witnesses for
$\mathbf{B}$).

  3. (3)

$R_{2}$ contains designated witnesses for the forks that are obtained by the
‘weak transitivity rule’ (cf. Lemma 4) from forks witnessed in $R_{1}$; that
is, for every $i$ $(\mathsf{d}\leq i\leq n)$, if $R_{1}$ has designated
witnesses for $(\gamma,\delta),(\beta,\delta)\in\operatorname{\text{\sc
fork}}_{i}(R_{1})$, then $(\gamma,\beta^{\gamma})\in\operatorname{\text{\sc
fork}}_{i}(R_{2})$ and $R_{2}$ has designated witnesses for it.

Then $R_{2}$ is a standardized representation for $\mathbf{B}$.

######  Proof 4.4.

Let $R_{1},R_{2}\subseteq\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ be
partial standardized representations, which satisfy conditions (1)–(3).
Conditions (1)–(2) imply that $R_{2}$ is a partial standardized representation
for $\mathbf{B}$, which contains a full set of designated local witnesses for
$\mathbf{B}$. Therefore, it remains to show that $R_{2}$ contains designated
witnesses for all derived forks of $\mathbf{B}$ in coordinates
$\geq\mathsf{d}$.

To prove this, let $m\geq\mathsf{d}$, and let
$(\gamma,\sigma)\in\operatorname{\text{\sc fork}}^{\prime}_{m}(B)$. Then there
exists $(\gamma,\beta)\in\operatorname{\text{\sc fork}}_{m}(B)$ such that
$\sigma=\beta^{\gamma}$. Hence, there exist $b,b^{\prime}\in B$ such that
$b|_{[m-1]}=b^{\prime}|_{[m-1]}$ and $b|_{m}=\beta$, $b^{\prime}|_{m}=\gamma$.
By assumption (2), both $b$ and $b^{\prime}$ are completely representable by
$R_{1}$. Since $b|_{[m-1]}=b^{\prime}|_{[m-1]}$, it follows from Lemma 9 that

$b^{(m-1)}=T_{m-1}(u^{(\mathsf{d})},\widehat{u}^{(\mathsf{d})},\dots,u^{(m-1)},\widehat{u}^{(m-1)},\overline{b^{I}}^{[m-1]})=(b^{\prime})^{(m-1)}.$

Let $\delta:=b^{(m-1)}|_{m}\,\bigl{(}=(b^{\prime})^{(m-1)}|_{m}\bigr{)}$.
Since $b$ and $b^{\prime}$ are completely representable by $R_{1}$, $R_{1}$
contains designated witnesses $(u,u^{\prime})$ and $(v,v^{\prime})$ for the
forks $(\beta,\delta),(\gamma,\delta)\in\operatorname{\text{\sc
fork}}_{m}(R_{1})$. Now, assumption (3) makes sure that in this situation,
$R_{2}$ contains designated witnesses for the fork
$(\gamma,\beta^{\gamma})=(\gamma,\sigma)$. This completes the proof.

Recall that $\mathsf{FNP}$ denotes the function problem version of
$\mathsf{NP}$. More precisely, a binary relation $R(x,y)$, where the size of
$y$ is polynomial in the size of $x$, is in $\mathsf{FNP}$ if and only if
there is a deterministic polynomial time algorithm that can determine whether
$R(x,y)$ holds given both $x$ and $y$.

######  Theorem 19.

Algorithm 4 solves $\operatorname{\text{\sc CompactRep}}({\mathcal{K}})$ in
polynomial time by making multiple calls to an oracle $\operatorname{\text{\sc
NeedMoreForkWitnesses}}({\mathcal{K}})$ in $\mathsf{FNP}$.

######  Proof 4.5.

First we define the oracle.

$\operatorname{\text{\sc NeedMoreForkWitnesses}}({\mathcal{K}})$:

  * •

INPUT: Partial standardized representation
$R\subseteq\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
($\mathbf{A}_{1},\ldots,\mathbf{A}_{n}\in{\mathcal{K}}$, $n\geq\mathsf{d}$)
such that $R$ contains designated local witnesses for the subalgebra
$\mathbf{R}^{*}$ of $\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ generated
by $R$

  * •

OUTPUT:
$\bigl{(}\textrm{YES},f,\bigl{(}(u_{j}^{(\mathsf{d})},\widehat{u}_{j}^{(\mathsf{d})},\dots,u_{j}^{(n)},\widehat{u}_{j}^{(n)},\overline{w_{j}^{I}})\bigr{)}_{j=1}^{\ell},b_{1},\dots,b_{\ell},b,\widetilde{R}\bigr{)}$
where

    1. (1)

$f\in F$ is an $\ell$-ary operation symbol (for some $\ell$),

    2. (2)

each pair $(u_{j}^{(m)},\widehat{u}_{j}^{(m)})$ ($j\in[\ell]$, $\mathsf{d}\leq
m\leq n$) is designated to witness a fork in $\operatorname{\text{\sc
fork}}_{m}(R)$,

    3. (3)

the tuples $\overline{w_{j}^{I}}=(w_{j}^{I})_{I\in\binom{[n]}{I}}$
($j\in[\ell]$) are such that each $w_{j}^{I}$ is a designated local witness of
$b_{j}|_{I}\in R|_{I}$,

    4. (4)

$b_{j}=T_{n}(u_{j}^{(\mathsf{d})},\widehat{u}_{j}^{(\mathsf{d})},\dots,u_{j}^{(n)},\widehat{u}_{j}^{(n)},\overline{w_{j}^{I}})$
(with $e=1$) for each $j\in[\ell]$,

    5. (5)

$b=f(b_{1},\dots,b_{\ell})$,

    6. (6)

$b$ is not completely representable by $R$,

    7. (7)

$\widetilde{R}=R\cup S^{\prime}\cup S$ is the partial standardized
representation obtained from the output of $\operatorname{\text{\sc
IsRepresentable}}({\mathcal{K}})$ run on the input $b,R$ (hence, $b$ is
completely representable by $\widetilde{R}$).

NO, if $f$,
$(u_{j}^{(\mathsf{d})},\widehat{u}_{j}^{(\mathsf{d})},\dots,u_{j}^{(n)},\widehat{u}_{j}^{(n)},\overline{w_{j}^{I}})$
($j\in[\ell]$), $b_{1},\dots,b_{\ell}$, and $b$ with these properties do not
exist.

To show that $\operatorname{\text{\sc NeedMoreForkWitnesses}}({\mathcal{K}})$
is in $\mathsf{FNP}$, we have to verify that the length of the output
$(\textrm{YES},\dots,\widetilde{R})$ is bounded by a polynomial of the length
of the input $R$, and there is a polynomial time algorithm which, when $R$ and
$(\textrm{YES},\dots,\widetilde{R})$ are both given, determines whether or not
conditions (1)–(7) hold. The first requirement holds, because the length of
the output is dominated by the length of $\widetilde{R}$, and both $R$ and
$\widetilde{R}$ have length $\Theta(n^{\mathsf{d}})$, as they are partial
standardized representations for $\mathbf{R}^{*}$ which contain a full set of
designated local witnesses for $\mathbf{R}^{*}$.

To prove that the second requirement holds as well, suppose that we are given
a partial standardized representation
$R\subseteq\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
($\mathbf{A}_{1},\ldots,\mathbf{A}_{n}\in{\mathcal{K}}$, $n\geq\mathsf{d}$)
such that $R$ contains designated local witnesses for $\mathbf{R}^{*}$, and we
are given a tuple

$\bigl{(}f,\bigl{(}(u_{j}^{(\mathsf{d})},\widehat{u}_{j}^{(\mathsf{d})},\dots,u_{j}^{(n)},\widehat{u}_{j}^{(n)},\overline{w_{j}^{I}})\bigr{)}_{j=1}^{\ell},b_{1},\dots,b_{\ell},b,\widetilde{R}\bigr{)}.$

Conditions (1)–(3) can be checked in
$O(1)+O(n^{2})+O(n^{\mathsf{d}})=O(n^{\mathsf{d}})$ time as $\ell$ is bounded
by a constant that depends only on ${\mathcal{K}}$. By (14), the circuit
complexity of $T_{n}$ (with $e=1$) is $O(n^{\mathsf{d}+1})$, hence checking
condition (4) requires $\ell\cdot O(n^{\mathsf{d}+2})=O(n^{\mathsf{d}+2})$
time. Condition (5) can be checked in $O(n)$ time. Finally, conditions (6)–(7)
can be checked by running Algorithm 1 for $\operatorname{\text{\sc
IsRepresentable}}({\mathcal{K}})$ with input $b$ and $R$, which requires
$O(n^{\mathsf{d}+2})$ time, and comparing $\widetilde{R}$ with its output.
Note here that $b$ and $R$ form a correct input for Algorithm 1 because, by
construction, $b\in\mathbf{R}^{*}$, so our requirement on $R$ guarantees that
appropriate designated local witnesses for $b$ exist in $R$.

Algorithm 4 Algorithm for $\operatorname{\text{\sc
CompactRep}}({\mathcal{K}})$ (direct)

0: $a_{1},\dots,a_{k}\in\mathbf{A}_{1}\times\dots\mathbf{A}_{n}$ with
$\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{K}}$ ($n\geq\mathsf{d}$)

0: Standardized representation $R$ for the subalgebra $\mathbf{B}$ of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ generated by
$a_{1},\dots,a_{k}$

1: Run Algorithm 2 for $\operatorname{\text{\sc LocalRep}}({\mathcal{K}})$
with input $a_{1},\dots,a_{k}\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
and $\theta_{i}=0$ ($i\in[n]$) to get output $R$

2: for $b\in\\{a_{1},\dots,a_{k}\\}$ do

3: run Algorithm 1 for $\operatorname{\text{\sc
IsRepresentable}}({\mathcal{K}})$ with input $b$ and $R$ to get output (YES,
$S^{\prime}$, $S$) or (NO, $S^{\prime}$, $S$)

4: $R:=R\cup S^{\prime}\cup S$

5: end for

6: while $\operatorname{\text{\sc NeedMoreForkWitnesses}}({\mathcal{K}})$
returns $(\textrm{YES},\dots,\widetilde{R})$ do

7: $R:=\widetilde{R}$

8: end while

9: for $m=\mathsf{d},\dots,n$ do

10: for all $(\gamma,\delta),(\beta,\delta)\in\operatorname{\text{\sc
fork}}_{m}(R)$ which have designated witnesses $(v,\widehat{v})$,
$(u,\widehat{u})$, respectively, in $R$ do

11: if $R$ contains no designated witnesses for $(\gamma,\beta^{\gamma})$ then

12: add $p(p(v,\widehat{v},\widehat{u}),p(v,\widehat{v},\widehat{v}),v)$ and
$p(u,v,v)$ to $R$ and designate them to witness the fork
$(\gamma,\beta^{\gamma})\in\operatorname{\text{\sc fork}}_{m}(R)$

13: end if

14: end for

15: end for

16: return $R$

Now we turn to the analysis of Algorithm 4. To prove its correctness, let
$a_{1},\ldots,a_{k}\in\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$
($\mathbf{A}_{1},\dots,\mathbf{A}_{n}\in{\mathcal{K}}$) be an input for
$\operatorname{\text{\sc CompactRep}}({\mathcal{K}})$ with $n\geq\mathsf{d}$,
and let $\mathbf{B}$ denote the subalgebra of
$\mathbf{A}_{1}\times\dots\times\mathbf{A}_{n}$ generated by
$a_{1},\dots,a_{k}$. We have to show that the set $R$ returned in Step 16 of
Algorithm 4 is a standardized representation for $\mathbf{B}$.

Notice that during Algorithm 4 we only add elements to $R$, and every element
added to $R$ has a designation. Therefore, at every point in the algorithm,
the current version of $R$ is a partial standardized representation, which
extends all previous versions. The description of $\operatorname{\text{\sc
LocalRep}}({\mathcal{K}})$ implies that the version of $R$ produced in Step 1,
which we will denote by $R_{0}$, is a standardized representation for
$\mathbf{B}$ that is a full set of designated local witnesses for
$\mathbf{B}$. In particular, $R_{0}\subseteq\mathbf{B}$.

Next we want to argue that

  1. (1)

throughout all iterations of the for loop in Steps 2–5 and the while loop in
Steps 6–8, $R$ satisfies

$R_{0}\subseteq R\subseteq\mathbf{B};$ (27)

  2. (2)

in every iteration of these two loops, the algorithms for
$\operatorname{\text{\sc IsRepresentable}}({\mathcal{K}})$ and
$\operatorname{\text{\sc NeedMoreForkWitnesses}}({\mathcal{K}})$,
respectively, have a correct input; and

  3. (3)

Algorithm 4 exits the while loop, i.e., $\operatorname{\text{\sc
NeedMoreForkWitnesses}}({\mathcal{K}})$ answers NO for the first time, after
polynomially many iterations.

Statements (1)–(2) follow by induction on the number of iterations by
observing that (27) holds for $R=R_{0}$ at the start of the first iteration of
the for loop; moreover, the descriptions of $\operatorname{\text{\sc