Results on the Equivalence Problem for Finite Groups

Stanley Burris and John Lawrence

Abstract. The equivalence problem for a finite nilpotent group has polynomial time complexity, even when the terms have parameters from the group. The same result holds for the dihedral groups D_{n}.

The terms for groups (in the language ·,^{−1}, e) are defined inductively by:

(1) variables are terms

(2) e is a term

(3) t is a term implies t^{−1} is a term

(4) s, t are terms implies s · t is a term.

Given a group G we define the polynomials of G to be the terms obtained when we add names for the elements of G to our constant symbols, i.e.,

(1) variables are polynomials

(2) g is a polynomial for g denoting an element of G

(3) p is a polynomial implies p^{−1} is a polynomial

(4) p, q are polynomials implies p · q is a polynomial.

The term equivalence problem for a group G is to determine, for any two terms p, q, if they define the same function on G, i.e., if the identity p ≈ q holds on G.

The polynomial equivalence problem for a group G is to determine, for any two polynomials p, q, if they define the same function on G, i.e., if the identity p ≈ q holds on G.

One can, of course, define these equivalence problems for any algebra. In Hunt & Stearns [4] (1990) it is proved that the polynomial equivalence problem for a finite nilpotent ring has polynomial time complexity. And Burris & Lawrence [3] (1992) show that for finite nonnilpotent rings the term equivalence problem is co-NP-complete.

It is easy to see that for any finite algebra A both the term and the polynomial equivalence problem are in co-NP. So if P = NP then both problems for A have polynomial complexity. However it is widely believed that P ≠ NP.

The classification of the equivalence problem for finite groups is begun in this paper. (The results were announced in [1].) We will show that the polynomial

Date: July 31, 2002.

Key words and phrases: evquivalence problem, finite groups, terms, polynomials, automated theorem proving, computational complexity.

We are grateful to Joel Berman for his comments on a earlier version of this paper. And both authors thank NSERC for funding which has supported this research.

equivalence problem for any finite nilpotent group, or any dihedral group D_{2k+1}, is of polynomial time complexity.

Now we turn to finite nilpotent groups. A group G = ⟨G, ·,^{−1}, e⟩ is nilpotent if it satisfies a (left-normed) commutator identity

[x_{0}, ⋯, x_{n}] ≈ e.  (1)

If G is nilpotent we say it is nilpotent class c if c is the smallest n such that (1) holds.

In the next definition we use [ , ] as a binary operation symbol (for the commutator).

Definition 1. The collection PC of pure commutator polynomials is defined by: (1) variables are in PC

(2) g is in PC for g denoting an element of G

(3) p, q are in PC implies [p, q] is in PC.

Definition 2. The leaf count function lc on PC is defined by:

• lc(x) = 1 for x a variable

• lc(g) = 1 for g naming an element of G

• lc([s, t]) = lc(s) + lc(t).

The leaf count function gives the number of leaves when a member of PC is viewed as a binary tree.

Lemma 3. For G a nilpotent class c group and for p from PC we have

(a) lc(p) = c implies G ⊧ p · z ≈ z · p for z a variable not appearing in p, and

(b) lc(p) > c implies G ⊧ p ≈ e.

Proof. This follows from the basic commutator calculus—see Lemma 33.35, p. 86, of H. Neumann [6] (1967). □

Definition 4. Given a polynomial p let var(p) be the set of variables occurring in p.

Lemma 5. Let G be a finite nilpotent class c group and let p(x_{1}, ⋯, x_{k}) be a polynomial of G. Let S_{0}, ⋯, S_{m} be an ordering of the subsets of {1, ⋯, k} of size at most c, and such that i < j ⟹ |S_{i}| ≤ |S_{j}|. For 1 ≤ i ≤ k we assume S_{i} ≈ {x_{i}}. Then one can find, for each S_{i}, a product γ_{i} of pure commutator polynomials p_{ij} such that

(a) var(p_{ij}) = {x_{s} : s ∈ S_{i}}, for all i, j, and

(b) G ⊧ p(x_{1}, ⋯, x_{k}) ≈ γ_{0} ⋯ γ_{m}.

Proof. This is our version of Theorem 33.45, p. 89, of H. Neumann [6] (1967). First put p(x_{1}, ⋯, x_{k}) into the form y_{1} ⋯ y_{ℓ} where each y_{i} is in the set {x_{1}, ⋯, x_{k}}, or is the name of an element of G. Then apply the following group identity

x · y ≈ y · x · [x, y]  (2)

to put y_{1} ⋯ y_{ℓ} in the form g_{0} · x_{1}^{n_{1}} ⋯ x_{k}^{n_{k}} · s(x_{1}, ⋯, x_{k}), where g_{0} ∈ G and s(x_{1}, ⋯, x_{k}) is a product of pure commutators p, with lc(p) ≤ c and var(p) ≥ 2 for each such p. Then let γ_{0} = g_{0}, and let γ_{i} = x_{i}^{n_{i}} for 1 ≤ i ≤ k.

Next apply the identity (2) to s(x_{1}, ⋯, x_{k}) to pull the pure commutator terms involving exactly two variables to the left side, with appropriate grouping, to give γ_{k+1}, ⋯, γ_{k+\binom{k}{2}}. Etc. □

Lemma 6. Let G be a nilpotent class c group, and let p(x_{1}, ⋯, x_{k}) be a polynomial of G. Let γ_{0}, ⋯, γ_{m} be as in Lemma 5. Then

G ⊧ p(x_{1}, ⋯, x_{k}) ≈ e  iff  G ⊧ γ_{i} ≈ e  for 0 ≤ i ≤ m.

Proof. (⟹) From Lemma 5 we know from G ⊧ p ≈ e that G ⊧ γ_{0} ⋯ γ_{m} ≈ e. Putting all variables equal to e shows that γ_{0} = e. Then putting all variables except x_{i} equal to e gives G ⊧ γ_{i} ≈ e, for 1 ≤ i ≤ k. Thus G ⊧ γ_{k+1} ⋯ γ_{m} ≈ e. Let var(γ_{k+1}) = {x_{i_{1}}, x_{i_{2}}}. Next by putting all variables except x_{i_{1}}, x_{i_{2}} equal to e we have G ⊧ γ_{k+1} ≈ e. Etc.

The converse is obvious using Lemma 5. □

Proposition 7. Let p(x_{1}, ⋯, x_{k}) be a polynomial of a nilpotent class c group G. Then

G ⊧ p(x_{1}, ⋯, x_{k}) ≈ e  iff  G ⊧ p(σx_{1}, ⋯, σx_{k}) ≈ e

for all σ such that (a) σx_{i} ∈ {x_{i}, e}, and

(b) |{i : σx_{i} ≠ e}| ≤ c.

Proof. (⟹) This is obvious.

(⟸) Let σ satisfy (a) and (b). Choose S_{0}, ⋯, S_{m} and γ_{0}, ⋯, γ_{m} as in Lemma 5, and let j be such that S_{j} = {i : σx_{i} ≠ e}. Then, from Lemma 5,

G ⊧ p(σx_{1}, ⋯, σx_{k}) ≈ ∏_{S_{i}⊆S_{j}} γ_{i},

so

G ⊧ ∏_{S_{i}⊆S_{j}} γ_{i} ≈ e.

As we run over the possible σ we see that this last assertion holds for any j ≤ m. Then, working through the S_{j}’s in order, we see that, for j ≤ m,

G ⊧ γ_{j} ≈ e.

But then we can apply Lemma 6 to obtain

G ⊧ p(x_{1}, ⋯, x_{k}) ≈ e.
□

Theorem 8. Let G be a finite nilpotent group. Then the polynomial equivalence problem for G is of polynomial time complexity.

Proof. Let G be nilpotent class c, and let p(x_{1}, ⋯, x_{k}) be a polynomial of G. Let

T = {(a_{1}, ⋯, a_{k}) : |{i : a_{i} ≠ e}| ≤ c}.

By Proposition 7 we see that

G ⊧ p(x⃗) ≈ e  iff  p(a⃗) = e  for a⃗ ∈ T.

Now • |T | = Σ_{i≤c}\binom{k}{i}(|G| − 1)^{i}, so T is of polynomial size,

• finding T is a polynomial time procedure, and

• checking p(a⃗) = e is a polynomial time procedure. Thus we have a polynomial time procedure to determine if G ⊧ p ≈ e. □

The idea of formulating the algorithm in terms of a polynomial size test set T is due to Joel Berman. It also applies to the results of Hunt & Stearns on finite nilpotent rings.

Next we will see that finite nilpotent groups are not the only ones with a polynomial equivalence problem of polynomial time complexity.

Theorem 9. The polynomial equivalence problem for the dihedral group D_{n} is of polynomial time complexity, for n odd.

Proof. First we look at the case that n is odd. Let a, b ∈ D_{n} with o(a) = n, o(b) = 2. Then all elements of D_{n} can be written in the form a^{u}b^{v}, where u, v are integers. Now we have

(a^{u_{1}}b^{v_{1}})(a^{u_{2}}b^{v_{2}}) = a^{u_{1}+(−1)^{v_{1}} u_{2}}b^{v_{1}+v_{2}},

or, abbreviating a^{u}b^{v} to (u, v), we have

(u_{1}, v_{1}) · (u_{2}, v_{2}) = (u_{1} + (−1)^{v_{1}}u_{2}, v_{1} + v_{2}).

By induction this leads to

(u_{1}, v_{1}) ⋯ (u_{ℓ}, v_{ℓ}) = (u_{1} + (−1)^{v_{1}}u_{2} + ⋯ + (−1)^{v_{1}+···+v_{ℓ−1}}u_{ℓ}, v_{1} + ⋯ + v_{ℓ}). (3)

Now a polynomial p(x_{1}, ⋯, x_{k}) of D_{n} can be put, in polynomial time, into the form y_{1} ⋯ y_{ℓ}, where each y_{i} ∈ {x_{1}, ⋯, x_{k}} ∪ D_{n}. Let α : {1, ⋯, ℓ} ⟹ {1, ⋯, k}∪D_{n} be such that y_{i} = x_{αi} if y_{i} is a variable, and y_{i} = αi if y_{i} = g ∈ D_{n}. Replace each y_{i} by (u_{αi}, v_{αi}), meaning: (i) a pair of variables (over the integers) if αi ∈ {1, ⋯, k}, or (ii) a pair of integers such that g = a^{u_{αi}}b^{v_{αi}} if αi = g ∈ D_{n}. This leads to p(x_{1}, ⋯, x_{n}) corresponding to

(a^{u_{α1}}b^{v_{α1}}) ⋯ (a^{u_{αℓ}}b^{v_{αℓ}}),

or, in our abbreviated notation,

(u_{α1}, v_{α1}) ⋯ (u_{αℓ}, v_{αℓ}).

Then, by (3),

D_{n} ⊧ p(x_{1}, ⋯, x_{k}) ≈ e

holds iff

u_{α1} + (−1)^{v_{α1}}u_{α2} + ⋯ + (−1)^{v_{α1}+···+v_{α(ℓ−l)}}u_{αℓ} ≡ 0 mod n
v_{α1} + ⋯ + v_{α_{ℓ}} ≡ 0 mod 2,

and, by putting all, or all but one, of the variable u_{αi}’s equal to 0, we see that these two equations hold iff

Σ_{αi∈D_{n}} (−1)^{v_{α1}+···+v_{α(i−1)}}u_{αi} ≡ 0 mod n  (4)
Σ_{αi=s} (−1)^{v_{α1}+···+v_{α(i−1)}} ≡ 0 mod n, for 1 ≤ s ≤ k  (5)
v_{α1} + ⋯ + v_{α_{ℓ}} ≡ 0 mod 2.  (6)

Now each v_{α1} + ⋯ + v_{α(i−1)} is a sum of variables and integers, so the equations (4) and (5) can be written in the form

ϵ_{1} · (−1)^{a_{11}v_{1}+···+a_{1k}v_{k}} + ⋯ + ϵ_{r} · (−1)^{a_{r1}v_{1}+···+a_{rk}v_{k}} ≡ 0 mod n,  (7)

where ϵ_{i} ∈ {0, ⋯, n − 1}, a_{ij} ∈ {0, 1}, and no two rows of the r × k matrix (a_{ij}) are the same. Let η_{i} = (−1)^{v_{i}}, and define a ring polynomial q ∈ Z_{n}[w_{1}, ⋯, w_{k}] by

q(w_{1}, ⋯, w_{k}) = ∑_{1≤i≤r} ϵ_{i} · ∏_{1≤j≤k} w_{j}^{a_{ij}}.

As the η_{i} can independently take on the values in {1, −1}, and no other values, the equation (7) is equivalent to

q vanishing in Z_{n} as the w_{i} range over {1, −1}.  (8)

Now the final part of the polynomial algorithm is to realize that (8) holds iff

q(w_{1}, ⋯, w_{k}) is simply the 0 polynomial.  (9)

This can be proved by induction on k, namely show that if q is not the zero polynomial then for some assignment c_{i} of values of the w_{i} in {1, −1} we have q(c_{1}, ⋯, c_{k}) ≠ 0 in Z_{n}.

The proof proceeds simply by writing q(w_{1}, ⋯, w_{k}) in the form

q′(w_{1}, ⋯, w_{k−1}) + (1 − w_{k}) · q′′(w_{1}, ⋯, w_{k−1}),

and noting that if q is not the zero polynomial then choose a ±1 assignment of w_{1}, ⋯, w_{k−1} such that one of q′ and q′′ does not vanish in Z_{n}. Then either w_{k} = 1 or w_{k} = −1 will yield a nonvanishing value of q(w_{1}, ⋯, w_{k}) since we have assumed n is odd. Item (9) gives us a polynomial time algorithm to determine if the equations in (4) and (5) hold. And determining if (6) holds is quite easy.

This takes care of the case for n odd. To handle the general case let n = 2^{k} · m, where m is odd. Then one can embed D_{n} into D_{2^{k}} × D_{m}, and both D_{2^{k}} and D_{m} embed into D_{n}. Thus one has a polynomial time algorithm for the polynomial equivalence problem for D_{n} as one has such for D_{m} by the above, and for D_{2^{k}} by Theorem 9 (as D_{2^{k}} is nilpotent). □

The result for D_{n} holds, by the same methods, for other finite groups which can be presented by defining relations of the form o(a) = n, o(b) = m, and b^{−1}ab = a^{j}, where gcd(j, n) = 1 and o(j) = 2 in Z_{n}. On the other hand Lawrence has proved that any finite nonsolvable group has a co-NP-complete term equivalence problem—hence the following question is appropriate.

Problem 1. Does every finite solvable group have a term [polynomial] equivalence problem of polynomial time complexity?

References

[1] S. Burris, Computers and universal algebra: some directions. Algebra Universalis 34 (1995), 61–71.

[2] S. Burris and J. Lawrence, The equivalence problem for finite rings. J. Symbolic Computation 15 (1993), 67–71.

[3] S. Burris and H.P. Sankappanavar, A Course in Universal Algebra. Springer-Verlag, 1981.

[4] H.B. Hunt III and R.E. Stearns The complexity of equivalence for commutative rings. J. Symbolic Computation 10 (1990), 411–436.

[5] O.G. Kharlampovich and M.V. Sapir, Algorithmic problems in varieties.

Internat. J. Algebra Comput. 5 (1995), 379–602.

[6] H. Neumann, Varieties of Groups. Springer-Verlag, 1967.

Dept. of Pure Mathematics, University of Waterloo, Waterloo, Ont., Canada N2L 3G1

  E-mail address: snburris@thoralf.uwaterloo.ca

Dept. of Pure Mathematics, University of Waterloo, Waterloo, Ont., Canada N2L 3G1

  E-mail address: jwlawren@math.uwaterloo.ca