arXiv:1607.07156v1 [math.GR] 25 Jul 2016

LOW GROWTH EQUATIONAL COMPLEXITY
MARCEL JACKSON
Abstract. The equational complexity function βV : N → N of an equational
class of algebras V bounds the size of equation required to determine membership of n-element algebras in V. Known examples of finitely generated
varieties V with unbounded equational complexity have growth in Ω(nc ), usually for c ≥ 21 . We show that much slower growth is possible, exhibiting
O(log32 (n)) growth amongst varieties of semilattice ordered inverse semigroups
and additive idempotent semirings. We also examine a quasivariety analogue
of equational complexity, and show that a finite group has polylogarithmic
quasi-equational complexity function, bounded if and only if all Sylow subgroups are abelian.

1. Introduction
In this article, an algebra means a universal algebra, though our primary focus
is on the class of finite groups and finite semilattice-ordered semigroups. For a
fixed signature S of operations, an equation is an expression u ≈ v, where u and
v are terms in S. The equation is satisfied in an algebra in the signature S if all
interpretations θ of the variables into the universe of the algebra results in uθ = vθ.
The class of all S-algebras satisfying some given system of equations is called the
variety defined by the equations. A variety is always closed under homomorphisms
(H), isomorphic copies of subalgebras (S) and direct products (P), and conversely,
every H, S, P closed class of similar algebras is a variety, definable by the equations
holding true in all of its members; see Birkhoff [3] or a text such as Burris and
Sankappanavar [4]. We let V(K) denote the the variety generated by a class K, and
write V(A) to denote V({A}) when A is a single algebra.
A challenging computational problem arises when one wishes to decide membership of a finite algebra B in a variety V: even when V = V(A) for a finite algebra A,
this problem can be as hard as 2EXPTIME-complete (Kozik [17]), and even amongst
almost classical algebras, such as semigroups, there are examples for which the
problem is NP-hard (Jackson and McKenzie [12], Jackson [11]) and co-NP-complete
(Kunc, Klima and Polak [15]). For general varieties V—even recursively axiomatizable varieties—the problem can be undecidable (see Hirsch and Hodkinson [8]
for example). Such membership problems are obviously fundamental in the general
study of varieties, but they are also an important particular case of the more general
situation of deciding membership of finite algebras in “pseudovarieties”: classes of
finite algebras closed under H, S and taking finitary direct products. A substantial
motivation for this more general case is that many questions in formal languages
can be recast in terms of membership problems for semigroup pseudovarieties. See
2000 Mathematics Subject Classification. Primary: 08B05; Secondary: 20M07, 20D99.
The author was partially supported by ARC Discovery Project DP1094578 and Future Fellowship 120100666.
1

2

MARCEL JACKSON

Almeida [1], Eilenberg [6] or Rhodes and Steinberg [27] for general theory, and
Volkov [28] for some important concrete example cases where the pseudovariety is
the finite part of V(A) for some finite semigroup A.
As every variety V has an equational characterization, a first attempt at deciding membership of a candidate algebra B in V might be to explore satisfaction of
these characterizing equations. Indeed, when V admits a characterization in terms
of finitely many equations, then testing these equations provides a polynomial time
algorithm to decide membership. Even when there is no finite equational characterization for V, the equational theory of V may still be well behaved enough for
an approach in this style. In particular, if B fails some identity of V, it must fail
some identity of V involving at most as many variables as there are generators for
B. When V is locally finite (and in particular, when V is finitely generated), there
always exists a finite set of equations of V that capture the n-variable equational
theory (for any n); this follows from Birkhoff’s Finite Basis Theorem [4, Theorem
V.4.2]. When V = V(A) for a finite algebra A, it is possible to calculate a concrete
bound on the size of the required n-variable equations, and thus obtain an inprinciple algorithm for deciding membership. The equational complexity function
βV captures exactly these notions.
The equational complexity function βV : ω → ω of V is defined by letting βV (n)
be the smallest number ℓ such that for every algebra B of size less than n, if B ∈
/V
then there is an equation of V failing on B and with length at most ℓ. Equivalently,
βV (n) is the smallest number ℓ such that for algebras of size less than n, lying in
V is equivalent to satisfying the equations true in V of length at most ℓ. If V is the
variety generated by a single finite algebra A then we also write βA in place of βV .
Obviously, the definition of βV depends on the precise definition of “length”. We
follow McNulty, Szekély and Willard [22] and define the length to be the number
of symbols in the concatenation of the bracket-free prefix expressions for the two
terms in the equation. Thus the law x · (y · y −1 ) ≈ x becomes ·x·y −1 yx of size 7
(noting that the expression “−1” is here a single operation symbol).
Existing work on equational complexity has had two main focal points. The
first is to identify the limits of fast growth of βA . In Kun and Vértesi [18] it
is shown that Θ(nk ) growth is possible (for any k ∈ N), while Kozik [16] showed
that at least exponential growth is possible. McNulty, Szekely and Willard [22] give
numerous concrete examples of algebras whose equational complexity is sandwiched
somewhere between linear and quadratic growth, while Jackson and McNulty [13]
give a linear growth rate for the equational complexity of Lyndon’s algebra.
The second focus of existing work relates to a long-standing open problem due
to Eilenberg and Schützenberger [5]: if the pseudovariety of A can be defined by
finitely many equations, is it true that the variety generated by a finite algebra A
can be defined by finitely many equations? It is a straightforward exercise to verify that (for finite signature), the function βV is bounded above by a constant if
and only if V can be defined, amongst finite algebras by a finite set of equations.
Thus the Eilenberg-Schützenberger problem is equivalent to asking: is it true that
every finite algebra with bounded equational complexity has a finite basis for its
equations? These connections are explored in [22] (though there is other work relating to the Eilenberg-Schützenberger conjecture that avoids discussion of equational
complexity).

LOW GROWTH EQUATIONAL COMPLEXITY

3

In Jackson and McNulty [13] it is suggested that as well as finding high growth
equational complexity, there should be equal interest in finding slow but unbounded
growth. In particular, algebras of very slow, but unbounded growth, appear to be
more likely related to difficult unresolved issues relating to axiomatizability. No
contributions have been made in this direction to date, with all examples known to
the author at the time of writing growing at least at Ω(nc ), where c ≥ 1/2 is typical.
In the present article we show that a finite naturally semilattice-ordered Clifford
semigroup always has equational complexity in O(log 32 (n)) (where logk (n) denotes
the polylog (log(n))k ) and identify those with β-function in O(1); see Theorem 4.1.
The smallest example with non-constant bounded (but slow) equational complexity
has 9 elements. To prove this we begin by introducing a corresponding theory of
quasi-equational complexity, which refers to quasi-equations and quasivarieties in
place of equations and varieties. This concept also appears interesting enough in
its own right, but is integral to our approach. We show in Theorem 3.1 that every
finite group has quasi-equational complexity in O(log32 (n)) and identify precisely
those with growth in O(1). (These ideas appear to have some relationship with the
Short Presentation Conjecture of Babai, Goodman, Kantor, Luks and Pálfy [2];
see Remark 3.2.) We then apply methods developed in [10] to obtain corresponding results for the equational complexity of naturally semilattice-ordered Clifford
semigroups and examples from additive idempotent semirings.
2. Equations, quasi-equations and quasi-equational complexity
Throughout, we use lower case letters (with or without subscripts) for variables
and boldface lower case letters (with or without subscripts) for generic terms and
words built from variables. Thus u will always denote a word or term in an alphabet
of variables, while u will denote an individual variable. We let Eq(A) denote the
set of all equations true on an algebra A (in some fixed, but otherwise arbitrary
countably infinite set of variables). The notation Eqn (A) will denote the subset of
Eq(A) consisting of those equations of size at most n.
A quasi-equation is an expression of the form


& ui ≈ vi → u ≈ v
1≤i≤n

for some n ≥ 0, where each of the ui and vi are terms, & is logical conjunction
and → is logical implication. A quasi-equation is satisfied by an algebra if every
interpretation of the variables that leads to the premise of the implication being
true also leads to the conclusion being true. Equations correspond to the case of
n = 0. The class of algebras defined by a system of quasi-equations is known as a
quasivariety and is closed under S, P and ultraproducts Pu . Every S, P, Pu closed
class—an indeed, any SPPu -closed class—is a quasivariety, and when A is a finite
algebra, then the quasivariety generated by A can be written as SP(A), without
ultraproducts. It is obvious from the syntactic definitions and also the semantic
equivalent conditions, that every variety is a quasivariety. We direct the reader to [4,
Chapter 5] or Gorbunov [7] for a treatment of quasivarieties and quasi-equations.
Equational complexity generalises to quasi-equational complexity in an obvious
way: up to big-O equivalence, again by concatenating all terms in prefix notation.
Thus the quasi-equation x · y ≈ y · x → x ≈ y becomes ·xy·yxxy of length 8. We
let β Q denote the quasi-equational complexity function of the quasivariety Q, also

4

MARCEL JACKSON

writing β A to denote β SPPu (A) . For a fixed variety V (hence also a quasivariety),
the relationship β V (n) ≤ βV (n) for all n follows immediately from the definitions,
but in contrast βA and β A may be quite different because the classes SPPu (A)
and HSP(A) are, in general, quite different.
3. Finite groups with polylog quasi-equational complexity.
Ol’shanskiı̆ [24] has shown that the quasivariety SP(G) of a finite group G has
a finite axiomatization by quasi-equations if and only if all Sylow subgroups of G
are abelian. When G has a finite basis for its quasi-equations, then the quasiequational complexity of G is bounded by a constant. When G has no finite basis
for its quasi-equations (that is, when it contains a nonabelian Sylow subgroup),
then it follows from Ol’shanskiı̆’s argument [24] that for all n there is a finite group
H such that every n-generated subgroup of H lie in the quasivariety of G, but that
H itself does not. It follows that β G (|H|) > β G (n), so that β G grows unbounded.
The rest of this section is devoted to showing that this growth can be contained
within the class O(log32 (n)), thus proving the following theorem.
Theorem 3.1. Let G be a finite group. If all Sylow subgroups of G are abelian,
then the quasi-equational complexity function β G is bounded by a constant. If G
contains a nonabelian Sylow subgroup, then β G is unbounded, but lies in O(log32 (n)).
This is true for all subsignatures of {·, −1 , 1} containing ·.
We leave discussion of the final sentence to the end of this section (see Remark 3.7). Observe that to complete the proof of the other statements in Theorem
3.1 it only remains to show that β G can be found in O(log32 (n)) (for any finite group
G; we will not need to use the fact that G contains a nonabelian subgroup). To
prove this we begin by showing that for any fixed finite group G, and H ∈ V(G),
then if H ∈
/ SP(G) there is a quasi-equation of size O(log32 (|H|)) satisfied by G
and failing on H. In particular, if G has a nonabelian Sylow subgroup—whence
generates a nonfinitely axiomatizable quasivariety—this shows that membership of
finite groups H in the quasivariety SP(G) can be verified by testing quasi-equations
of size only up to O(log32 (|H|)). We use this to show that the flat extension of the
finite group G exhibits equational complexity bounded by O(log32 (|H|)), but (when
G has a nonabelian Sylow subgroup) not by any constant.
Remark 3.2. The first half of the argument is closely related to the results of
Babai, Goodman, Kantor, Luks and Pálfy [2] who show that it is possible to associate with each finite group H a presentation of short size. The authors of [2] state
a Short Presentation Conjecture: that the presentation of H can be made to be of
total size O(log32 (|H|)).
The Short Presentation Conjecture is not resolved here, but our approach is at
least slightly reminiscent of the methods invoked in [2]. We consider an arbitrary
finite group H in the variety of a fixed finite group G and examine a composition
series for H, lifting presentations for the various simple groups to one for H. The
precise description is quite different to that in [2]. Also, because the simple groups
arising from the composition series also lie in V(G), we have access to the following
fact. (This folklore lemma was pointed out to the author by Mikhail Volkov.)
Lemma 3.3. Let G be a finite group. Up to isomorphism, there are only finitely
many finite simple groups in the variety V(G).

LOW GROWTH EQUATIONAL COMPLEXITY

5

Proof. Claim 51.22 of H. Neumann [23] shows that all simple groups in V(G) have
order at most |G|.

We examine composition series to lift presentations for these to short presentations to arbitrary H ∈ V(G). This approach is common to Babai et al. though the
precise construction of the presentation is quite different. In a further deviation
from Babai et al. [2], we will also require the additional property that every element
of H can be written as a short product of generators: O(log 32 (|H|)) would suffice,
but O(log2 (|H|)) is shown.
In the following lemma we consider group presentations in the variety of groups,
using the convention that relators are single words. Thus, if w is a relator, we mean
that w = 1 in the group.
Lemma 3.4. (The lifting lemma.) Let N E M be finite groups and assume that
• N has presentation ha1 , . . . , ak | {wi : i = 1, . . . , k ′ }i, and
• M/N has presentation hN b1 , . . . , N bℓ | {N vi : i = 1, . . . , ℓ′ }i,
where wi are some words in the alphabet {a1 , . . . , ak }, and vi are some words in
the alphabet {b1 , . . . , bℓ }. Then M is generated by the set {a1 , . . . , ak , b1 , . . . , bℓ }
and can be presented by the following words:
(1) wi for i = 1, . . . , k ′ ;
(2) (for each i = 1, . . . , k and j = 1, . . . , ℓ) wi,j bi aj−1 bi−1 where wi,j is a word
of minimal length representing the element bi aj in the coset Nbi ;
(3) (for each i = 1, . . . , ℓ′ ) u−1
i vi , where ui is a word of minimal length in the
alphabet {a1 , . . . , ak } for which vi = ui .
Moreover, every element of M can be written in the form wa wb , where wa is a
word in the generators a1 , . . . , ak and wb is a word in the generators b1 , . . . , bℓ .
Proof. First note that the presentation is well-defined and that each of the given
words does equal 1 in M. This is immediate for Item (1). For Item (2), as bi N =
N bi , and aj ∈ N , we have that bi aj ∈ N bi , showing the existence of wi,j ∈ N with
−1
bi aj = wi,j bi in M; note then that wi,j bi a−1
= 1. For item (3), observe that as
j bi
N vi is in the presentation of M/N we have that vi ∈ N , so that there exists a word
ui in the generators {a1 , . . . , ak } with vi = ui and hence u−1
i vi = 1. This each of
the relator words is equal to 1 in M as required. Also, every element h of M lies
in a coset of the form Nwb of M, where wb is a product of the elements bi . Thus
there is an element wa ∈ N such that h = wa wb . So {a1 , . . . , ak , b1 , . . . , bℓ } is a set
of generators of M. It remains to show that if w is a word in {a1 , . . . , ak , b1 , . . . , bℓ }
equal to 1 in M, then this fact can be deduced using the given list of relators.
Assume that w is a product in the generators that is equal to 1. First observe that
the laws of the second kind ensure that w can be written in the form va vb , where
va is a product of the elements a1 , . . . , ak while vb is a product of the elements
b1 , . . . , bℓ . Now as w = 1 we have Nvb = N. This may be achieved by use of
the laws of the third kind: invoking laws of the second kind freely to move all
generated occurrences of generators in a1 , . . . , ak to the left of any from b1 , . . . , bℓ .
Thus eventually we obtain a deduction of va vb = ua , where ua is a product of
a1 , . . . , ak that is equal to 1 in M, and hence in N. This can be established using
laws of the first kind.


6

MARCEL JACKSON

Lemma 3.5. There is a constant c such that every finite group H ∈ V(G) has a
presentation hC; Ri of total length at most c log32 (|H|) and such that every element
in H can be written as a product of length at most 2|G| log2 (|H|).
Proof. By Lemma 3.3 there are only finitely many finite simple groups in the variety
generated by G, say {S1 , . . . , Sp }. Thus there is a constant bound on the size of
a presentation for the Si . Now consider the composition series {e} = H0 E H1 E
H2 E · · · E Hm = H. Observe that m ≤ log2 (|H|), because |Hi | ≤ |H2i | and that
each Hi+1 /Hi ∈ I{S1 , . . . , Sp } (the isomorphism closure of {S1 , . . . , Sp }). Now
Lemma 3.4 enables the inductive construction of a presentation for H: at the
(i + 1)th step, the group Hi+1 plays the role of M in Lemma 3.4, and the group
Hi plays the role of N. At completion, a set of generators
a1,1 , . . . , a1,n1 , . . . , am,1 , . . . , am,nm
has been constructed for H, where at the (i + 1)th step of the induction, the
elements a1,1 , . . . , ai,ni played the role of the elements a1 , . . . , ak in the lemma,
while ai+1,1 , . . . , ai+1,ni+1 played the role of the b1 , . . . , bℓ .
(1) Let # gen denote the largest generating set for the fixed selection of presentations for {S1 , . . . , Sp }. Inductively let gen(1) denote the number of
generators for H1 ∈ {S1 , . . . , Sp } (so gen(1) = n1 ) and gen(i + 1) be the
number of generators for Hi+1 as constructed from Hi and the quotient
Pi
Hi+1 /Hi ∈ {S1 , . . . , Sp }. It is routine to see that gen(i) =
j=1 nj ≤
i · # gen. We now count the size of this presentation, and the worst case
upper bound on the length of a product of generators needed to express
elements of H.
(2) Let # len denote the worst case minimal length of any product of generators
required to represent elements of {S1 , . . . , Sp }. Inductively, let len(1) be the
worst case minimal length of a word required to represent elements of H1 ,
and let len(i + 1) denote the shortest length of a product of generators required to represent elements in Hi+1 as constructed using Lemma 3.4. Note
that by the final statement of Lemma 3.4 we have len(i+1) ≤ # len + len(i)
so that len(i) ≤ i · # len.
(3) Let # rel denote the largest number of relations used in the fixed selection of
presentations for {S1 , . . . , Sp }. Inductively let rel(1) denote the number of
relations for H1 ∈ {S1 , . . . , Sp } and rel(i+1) be the number of relations constructed for Hi+1 using Lemma 3.4 from Hi and the quotient Hi+1 /Hi ∈
{S1 , . . . , Sp }. Note that rel(i + 1) ≤ rel(i) + # gen · gen(i) + # gen.
(4) # rellen denotes the maximal length of any relation appearing in the fixed
presentations for {S1 , . . . , Sp }. Inductively, rellen(1) denotes the maximal
length of any relation in the presentation for H1 , and rellen(i + 1) denotes
the maximal length of any relation in the presentation constructed for Hi+1 .
Note that
(1)

(2)

(3)

z }| { z }| { z
}|
{
rellen(i + 1) ≤ max{rellen(i), 3 + len(i), # len + len(i)}

where the numbering states which case of Lemma 3.4 the expression derives from.
We have a system of 4 simultaneous recurrence relations, however we have already
observed easy bounds for gen(i) and len(i). These can be substituted into the

LOW GROWTH EQUATIONAL COMPLEXITY

7

recurrence relations for rel(i) and rellen(i). For rel(i) we have, after substituting
the bound # gen ·i for gen(i):
rel(i + 1) ≤ rel(i) + i · # gen2 +# gen .
If we solve this system in the case of equality, we obtain an upper bound for rel(i).
The homogeneous solution is constant, and in the inhomogeneous expression is
linear (in the variable i), so that the particular solution (and then general solution)
is a quadratic in i. In particular then, rel(m) ∈ O(log22 (|H|)).
Finally, for rellen(i) we observed
rellen(i + 1) ≤ max{rellen(i), 3 + len(i), # len + len(i)}.
Using len(i) ≤ i·# len and putting c = max{3, # len, # rellen} we get rellen(i+1) ≤
max{rellen(i), c + i · # len}. Inductively (given that rellen(1) ≤ c and c + i · # len is
strictly increasing in i), we then obtain rellen(i) ≤ c + i · # len. Thus # rellen(m) ∈
O(log2 (|H|)).
Combining all this, at completion, we have obtained a presentation for H = Hm
in O(log2 (|H|)) generators, with at most O(log22 |H|) relations, each of maximal
length O(log2 |H|). Thus the total length of the presentation is in O(log32 (|H|)).
Also, every element of H can be written as a O(log 2 (|H|)) length product of the
constructed generating set.

Lemma 3.6. For a finite group G, if H is a finite group and H ∈
/ Q(G), then
there is a quasi-equation φ satisfied by G and failing on H and the total length of
φ is O(log32 (|H|)).
Proof. By the theorem of Oates-Powell [26], there is a finite basis for the variety
generated by G. Let us fix such a basis, and denote it by Σ. Observe that there is
a constant bound on the size of equations in Σ (because it’s finite) so if H ∈
/ V(G)
then H fails an identity of Σ, and we are done. Now assume that H ∈ V(G). As
H ∈
/ Q(G) there is an element h ∈ H\{1} such that every homomorphism from
H into G identifies h with 1. By Lemma 3.5, we may select a presentation hC; Ri
for H of total length O(log32 (|H|)) and assume that h is written as a product w of
generators of length at most O(log2 (|H|)). Let φ be the quasi-identity


& u ≈ 1 → w ≈ 1.
(†)
u∈R

Then G |= φ and H does not. The total length of φ is O(log 32 (|H|)), as required. 
Remark 3.7. Lemma 3.6 remains true in the signatures {·}, {·, 1} and {·, −1 }.
Proof. We consider the case of {·}, with the other cases following by using a subset
of the argument. We are given a presentation hA | Ri for a group G, where R is
a set of group words in the alphabet A. To remove −1 from the signature, first let
A−1 denote the set {a−1 | a ∈ A}, which we now treat as an alphabet disjoint to
A. Observe that the law (xy)−1 ≈ y −1 x−1 allows us to assume that each w ∈ R is
a semigroup word in the alphabet A ∪ A−1 . Then hA ∪ A−1 | R ∪ {aa−1 | a ∈ A}i
is a monoid presentation for G (in the signature {·, 1}). To remove 1 from the
signature, add it as a generator and add the relators g · 1 = g and 1 · g = g for
each generator g ∈ A ∪ A−1 ∪ {1} to R. It is easy to see that the total length of
the presentation is extended by only a constant factor, while the shortest length

8

MARCEL JACKSON

of a product to represent an element remains unchanged. The quasi-equation in
Equation (†) is amended accordingly, with “u ∈ R” replaced by “u ≈ 1 ∈ R”. 
Lemma 3.6 completes the proof of Theorem 3.1, except for the statements about
signature. Remark 3.7 shows that the theorem holds in each of the described
signatures.
4. Polylog equational complexity for a semilattice ordered inverse
semigroup
Recall that an inverse semigroup is an involuted semigroup satisfying xx−1 yy −1 ≈
yy xx−1 ; see a text such as Howie [9], Lawson [19] or Petrich [25]. A naturally
semilattice-ordered inverse semigroup is an inverse semigroup with a second binary operation ∧ satisfying the usual semilattice axioms, along with left and right
distributivity of · over ∧, and the law
−1

x ∧ y ≈ x(x ∧ y)−1 (x ∧ y)
which ties the usual semilattice order defined by ∧ to the usual inverse semigroup
theoretic order defined by ·, −1 . An inverse semigroup is said to be a Clifford
semigroup if the idempotent elements are central: xx−1 y ≈ yxx−1 .
Naturally semilattice-ordered Clifford semigroups can be found in the work of
Leech [20, 21] as well as in the study of algebras of injective partial maps, such as
in Jackson and Stokes [14].
The main result of this section and of the article is the following theorem.
Theorem 4.1. Let C be a finite naturally semilattice-ordered Clifford semigroup.
If all subgroups of C have only abelian Sylow subgroups, then C has a finite basis for
its equational theory and βC is bounded by a constant. Otherwise, βC is unbounded
by lies in O(log32 (n)).
We also observe in Remark 4.9 that one may similarly obtain examples of
finite additive idempotent semirings with equational complexity growing within
O(log32 (n)).
The remainder of the section concerns the relevant definitions and proofs to
arrive at Theorem 4.1. We now employ a method developed in [10] for translating
quasi-equations of partial algebras into equations of some other kind of algebraic
structure. When applied to groups (as partial algebras that happen to be total), one
arrives at the class of semilattice-ordered Clifford semigroups; this tight relationship
is developed in Sections 7.7 and 7.8 of [10].
Definition 4.2. Let G = hG; ·, −1 i be a group and 0 be a symbol not appearing
in G. Define the flat extension of ♭(G) to be the algebra on the set G ∪ {0} with
operations ·, −1 , ∧, with · and −1 extended by letting 0 be an absorbing element
and by
(
x if x = y
x∧y =
0 otherwise.
We also allow the same notation for other signatures, in particular, for {·}.
The flat extension of a group is a naturally semilattice-ordered Clifford semigroup
and is subdirectly irreducible. It follows from Theorems 5.3 and 7.5 of [10] that the
class of subdirectly irreducible naturally semilattice-ordered Clifford semigroups is
precisely the isomorphism closure of the class of flat extensions of groups.

LOW GROWTH EQUATIONAL COMPLEXITY

9

The following lemma is essentially a trivial consequence of Sections 7.7 and 7.8
of [10], along with the fact a quasivariety generated by a finite set of finite groups
is equal to the quasivariety generated by a single finite group. We sketch a proof
for completeness.
Lemma 4.3. The variety generated by a finite naturally semilattice-ordered Clifford
semigroup C is equal to one generated by the flat extension of a finite group G, with
G obtained as the direct product of a family of subgroups of the {·}-reduct of C.
Proof. Let C be a finite naturally semilattice-ordered Clifford semigroup, and let
C1 , . . . , Cn be a complete list of its subdirectly irreducible quotients. By elementary universal algebraic considerations, the variety V generated by S is equal to
the variety generated by {C1 , . . . , Cn }. By [10, Theorems 7.5 and 5.3], each of
the Ci is isomorphic to the flat extension of some group Gi . Each ♭(Gi ) is a homomorphic image of C, but by taking ∧-minimal elements of C from each kernel
class of this homomorphism (which exist as C is finite), it follows thatQeach Gi is
in fact isomorphic to a subgroup of C. Let G be the direct product i Gi . The
quasivariety generated by G is equal to that generated by {G1 , . . . , Gn }. Hence
by [10, Theorem 5.3], the variety V can equivalently be generated by ♭(G).

In the case of a finite group (or of a finite naturally semilattice-ordered semigroup), it is not necessary that the operation −1 be included, as it is a term function in multiplication: by x−1 = xd−1 , where d is the period. Notice that x−1 y (or
xd−1 y) is a term function acting as a second projection. The following lemma summarises some of the key facts regarding varieties generated by the flat extensions,
in the case where there is a second-projection term. It is part of Theorems 5.3
and 5.12 of [10].
Lemma 4.4. [10] Let Q be a quasivariety of algebraic structures (of some fixed finite
type) on which there is a two-variable term x ⊲ y acting as second projection: Q |=
x ⊲ y ≈ y. Then the class of subdirectly irreducible members of V({♭(H) | H ∈ Q})
is I({♭(H) | H ∈ Q}). Moreover, Q has a finite axiomatization by quasi-equations
if and only if V({♭(H) | H ∈ Q}) has a finite axiomatization by equations.
The last sentence in this lemma is proved in [10] using [10, Lemma 5.9], which
gives an explicit translation of quasi-equations in the language of Q to equations in
the language of {♭(H) | H ∈ Q}. The translation involves only a linear adjustment
in length when ⊲ is a fundamental operation, however in the present setting we
have ⊲ only as term function, which can potentially result in an exponential increase
in the length of the expression. The issue is easily resolved: the following is a
slight recasting of a particular case of [10, Lemma 5.9], that avoids the exponential
blowout.
Lemma 4.5. Let &1≤i≤n (ui ≈ vi ) → u0 ≈ v0 be a quasi-equation in the language
of a single binary operation and with the property that every variable appearing
in the expression appears somewhere in the premise of the implication. Then the
quasi-equation
ρ :=

& (ui ≈ vi ) → u0 ≈ v0

1≤i≤n

10

MARCEL JACKSON

holds on a group H of exponent d if and only if the following equation holds on
♭(H):
 Y
d
 Y
d
♭
d
ρ :=
(ui ∧ vi ) (u0 ∧ v0 ) ≈
(ui ∧ vi ) .
(∗)
1≤i≤1

1≤i≤1

Proof. Let 0 denote the bottom element with respect to ∧ in ♭(H). If ρ fails
in H under some interpretation of the variables θ into H, then considering θ as
an interpretation
into ♭(H) we have the right hand side of ρ♭ in (∗) taking the
Q
value θ(( 1≤i≤1 (ui ∧ vi ))d ) = 1, while as θ(u0 ) 6= θ(v0 ) the left hand side involves
θ(u0 ∧ v0 ) = θ(u0 ) ∧ θ(v0 ) = 0. So ρ♭ fails on ♭(H).
Now assume that ρ holds on H. It is clear that if the right hand side of ρ♭ takes
the value 0 under some interpretation of
Q the variables in ♭(H), then so does the
left hand side. Let us assume then that 1≤i≤1 (ui ∧ vi ) does not take the value 0
under some interpretation θ Q
of the variables of the equation into ♭(H). Note that
all variables in ρ♭ appear in 1≤i≤1 (ui ∧ vi ), so in fact θ is an interpretation into
H. Also, as x ∧ y = 0 unless x = y, we must have that θ(ui ) = θ(vi ) in H (for every
i = 1, . . . , n). As H |= &1≤i≤n (ui ≈ vi ) → u0 ≈ v0 it follows that θ(u0 ) = θ(v0 )
also, from which it is easily seen that both the left hand side and the right hand
side of ρ♭ take the value 1.

Note that if G is fixed and H ∈ V(G), then the exponent of H is bounded by
that of G, hence the quasi-equation found in Lemma 3.6 translates via Lemma 4.5
to an equation of size O(log3 (|H|)).
Let A be a finite algebra. A jump point of βA is a number n ∈ N such that
βA (n − 1) < β(n). A βA -critical algebra is a finite algebra B such that
• |B| is a jump point for βA ;
• B satisfies all identities of A up to complexity βA (|B|) − 1
• B fails some identity of A with complexity βA (|B|).
In other words, β-critical algebras are the algebras that force an increase in βA .
Lemma 4.6. Every βA -critical algebra is subdirectly irreducible.
Proof. Let B be βA -critical, and let u ≈ v ∈ Eq(A) be an equation of complexity
βA (|B|) failing on B under the assignment φ. Let θ be a maximal meet irreducible
congruence of B separating φ(u) and φ(v); let C := B/θ, a subdirectly irreducible
algebra. Now C fails u ≈ v, but also satisfies EqβA (|B|)−1 (A), since B does. Hence
βB (|C|) ≥ βA (|B|), however as |B| is a jump point it follows that |B| = |C| and
that θ is trivial. Hence B is subdirectly irreducible.

Lemma 4.7. Let A be a finite algebra with unbounded equational complexity. Let
f : R → R be a nondecreasing real function such that whenever B is a βA -critical
algebra of size less than n, there is an equation in Eqf (n) (A) failing on B. Then
βA is bounded above by f .
Proof. Say that βA (n) = m. Thus there is a βA -critical algebra B with fewer than
n elements failing some equation of A of m, but satisfying Eqm−1 (A). Hence B
fails some equation satisfied by A and of length at most f (|B|). So f (n) ≥ f (|B|) ≥
m = βA (n), as required.


LOW GROWTH EQUATIONAL COMPLEXITY

11

Theorem 4.8. Let G be a finite group containing a nonabelian Sylow subgroup.
Then the equational complexity of ♭(G) is not eventually constant but grows within
O(log32 (n)).
Proof. By Lemmas 4.6 and 4.7 we only need to show that there is a constant c > 0
such that for n sufficiently large, n-element subdirectly irreducible algebras outside
of V(♭(G)) fail an equation in Eq(♭(G)) of size at most c log32 (n).
The Oates-Powell Theorem [26] shows that variety of G can be axiomatized by
a finite system of equations. As this variety is a quasivariety and as equations are
quasi-equations, Lemma 4.4 shows that there is a finitely system Σ of equations
in the signature {∧, ·, 1} for which the subdirectly irreducible models are (up to
isomorphism) precisely the algebras ♭(H), where H ∈ V(G); the same applies in
the signature {∧, ·}.
Let m be greater than the size of the longest equation in Σ, and consider a
subdirectly irreducible algebra not in V(♭(G)), but satisfying all equations of ♭(G)
up to size < m. In particular, S satisfies Σ so is of the form ♭(H) for some finite
group H ∈ V(G). As ♭(H) ∈
/ V(♭(G)), Lemma 4.4 shows that H ∈
/ Q(G) and
so Lemma 3.6 shows that there is a quasi-equation of size O(log 32 (|H|)) failing on
H but holding on G. Then Lemma 4.5 shows that there is an equation of size
O(log32 (|H|)) failing on H and holding on ♭(G).

Finally we may complete the proof of the main result.
Proof of Theorem 4.1. Lemma 4.3 implies that V(C) is equal to V(♭(G)), where G
is a group. Moreover, C has a nonabelian Sylow subgroup if and only if G has a
nonabelian Sylow subgroup.
By [24], the group G has a finite basis for its quasi-equations if and only if all of its
Sylow subgroups are abelian. Hence, by Lemma 4.3, it follows that V(C) = V(♭(G))
has a finite basis for its equations if and only if C has all of its Sylow subgroups
abelian. When C has a finite equational basis we obtain βC ∈ O(1). Otherwise,
Theorem 4.8 shows that βC is unbounded but in O(log32 (n)).

Remark 4.9. When a finite group G is considered in the signature {·}, then
the algebra ♭(G) is an example of an additive idempotent semiring, which also
has O(log32 (n)) growth equational complexity provided G has a nonabelian Sylow
subgroup.
The smallest groups with a nonabelian Sylow subgroup are the 8-element nonabelian groups. Thus, the methods in this section produce 9-element examples of
semilattice-ordered Clifford semigroups and semirings with slow growth equational
complexity.
References
1. J. Almeida, Finite Semigroups and Universal Algebra, World Scientific, Singapore 1994.
2. L. Babai, A.J. Goodman, W.M. Kantor, E.M. Luks, P.P. Pálfy, Short presentations for finite
groups, J. Algebra, 194 (1997), 79–112.
3. G. Birkhoff, On the Structure of Abstract Algebras, Math. Proc. Cambridge Philos. Soc. 31
(1935), 433–454.
4. S. Burris and V.P. Sankappanavar, A Course in Universal Algebra, Graduate Texts in Mathematics, Springer Verlag, 1981.
5. S. Eilenberg and M.-P. Schützenberger, On pseudovarieties, Adv. Math. 19 (1976), 413–418.

12

MARCEL JACKSON

6. S. Eilenberg, Automata, Languages and Machines Vol B, Pure and Applied Mathematics,
Academic Press, New York, 1976.
7. V.A. Gorbunov, Algebraic Theory of Quasivarieties, Consultants Bureau, New York, 1998.
8. R. Hirsch and I. Hodkinson, Representability is not decidable for finite relation algebras,
Trans. Amer. Math. Soc. 353 (2001), 1403–1425.
9. J.M. Howie, Fundamentals of Semigroup Theory, 2nd edition. Oxford University Press, New
York (1995)
10. M. Jackson, Flat algebras and the translation of universal Horn logic to equational logic, J.
Symbolic Logic, 73 (2008), 90–128.
11. M. Jackson, Flexible constraint satisfiability and a problem in semigroup theory, manuscript,
2015 arXiv:1512.03127.
12. M. Jackson and R. McKenzie, Interpreting graph colorability in finite semigroups, Internat.
J. Algebra Comput. 16 (2006), 119–140.
13. M. Jackson and G. F. McNulty, The equational complexity of Lyndon’s algebra, Algebra
Univers. 65 (2011), 243–262.
14. M. Jackson and T. Stokes, Identities in the algebra of partial maps, Internat. J. Algebra
Comput. 16 (2006), 1131–1159.
15. O. Klı́ma, M. Kunc and L. Polák, Deciding piecewise k-testability, manuscript, 2014.
16. M. Kozik, On Some Complexity Problems in Finite Algebras, Ph.D. thesis, Vanderbilt University, 2004.
17. M. Kozik, A 2EXPTIME complete varietal membership problem, SIAM J. Comput. 38 (2009),
2443–2467.
18. G. Kun, and V. Vértesi, The membership problem in finite flat hypergraph algebras, Internat.
J. Algebra Comput. 17 (2007), 449–459.
19. M.V. Lawson, Inverse Semigroups: the theory of partial symmetries, World Scientific, 1998.
20. J. Leech, Inverse monoids with a natural semilattice ordering, Proc. London Math. Soc. (3)
70 (1995) 146–182.
21. J. Leech, On the foundations of inverse monoids and inverse algebras, Proc. Edinburgh Math.
Soc. (2) 41 (1998) 1–21.
22. G.F. McNulty, Z. Székely, R. Willard, Equational complexity of the finite algebra membership
problem, Internat. J. Algebra Comput. 18 (2008), 1283–1319.
23. H. Neumann, Varieties of groups, Ergebnisse der Mathematik und ihrer Grenzgebiete Volume
37, Springer-Verlag, 1967.
24. A.Ju. Ol′ s̆anskiı̆, Varieties of finitely approximable groups, Izv. Akad. Nauk. SSSR Ser. Mat.
33 (1969), 915–927 [Russian; English translation in Math. USSR Izv. 3 (1969), 867–877].
25. M. Petrich, Inverse Semigroups, Wiley, 1984.
26. S. Oates and M.B. Powell, Identical relations in finite groups, J. Algebra 1 (1964), 11–39.
27. J. Rhodes and B. Steinberg, J. Rhodes and B. Steinberg. The q-theory of finite semigroups.
Springer Monographs in Mathematics. Springer, New York, 2009.
28. M.V. Volkov, Reflexive relations, extensive transformations and piecewise testable languages
of a given height, Internat. J. Algebra Comput. 14 (2004), 817–827.
Department of Mathematics and Statistics, La Trobe University, Victoria 3086, Australia
E-mail address: M.G.Jackson@latrobe.edu.au

