Equations Over Groups: A Mess
Equations over groups and their relationship to complexity theory
Denis Thérien is an expert on low level complexity, especially the computational theory of groups and related algebraic structures. In a 2005 press release announcing his promotion to an administrator at McGill, it was stated that he is:
an accomplished mathematician, whose research interests include complexity theory, classifying problems in terms of resources required to compute their solution.
Indeed. I like the phrase, “classifying problems in terms of resources required to compute their solution”—very well said.
Today I want to talk about solving equations over groups, and its relationship to complexity theory.
I have two reasons for discussing this. As I discussed previously, there is a chance to solve one of the main open problems in low level complexity theory, if we could show certain equations over groups have solutions. The question is the famous one left open by David Barrington: can bounded width computations over solvable groups compute ? David’s famous theorem showed that such bounded computations can do this over simple groups. Barrington, Straubing, and Thérien worked on this problem proving some partial results, but the main question is unresolved. If solvable groups could, indeed, work in place of simple groups, then the following surprising result would be true:
This is the last theorem proved in Barrington’s paper: if solvable groups can compute , then the above is true. Second, the theory of equations over groups is potentially useful to computational complexity in other ways. The theory is quite difficult, since groups can behave badly in many ways. But I hope this short introduction to the area will make you want to learn more, and perhaps solve some open problems. Either resolve Barrington’s question conclusively rather than conditionally, or find more applications of the theory of equations. Or something else.
Equations Over A Group
Let’s start to look at equations over a group. As usual we will use to denote the product of and in a group. Also the interesting cases are almost always when the groups are non-commutative, so is not he same as in general.
What is an equation over a group ? An example of an equation is:
Note, are in and is the unknown. The equation has a solution over provided there is an element in so that
Many times such an equation will not have a solution: that is for all in the above is false. This does not stop us. A natural idea is to ask: is there a group so that and for a in
In a sense we have extended the group and added enough elements to it so that the equation has a solution. Note, this is exactly the issue that bothered early mathematicians, what do you do with the equation
over the rationals? There is no solution, but there is one in a larger world—but you need to add the square root of .
The obvious question is: can we always find the larger group so this is possible?
No Fundamental Theorem Of Groups
The answer, you may have guessed, is that there is no analog of the Fundamental Theorem of Algebra (FTA). There are group equations that cannot be solved even if we can extend the group and add new elements. This is the reason the theory is so different from solving equations over fields.
Pick any finite group with elements and so that and . This is nothing more than asking for a group with an element of order and another with a different order. To make it interesting let’s also assume that is not the identity element. Now consider the equation:
The unknown is, as usual, the . I claim that this equation has no solution in any group that contains . Assume there was an in some larger group. Rewrite the equation as
Then, square both sides of the equation,
This is a contradiction. Thus, there is no FTA for group equations.
A Partial Fundamental Theorem
A pretty case where there always is a solution is given by the following almost fifty year old theorem proved in 1962 by Frank Levin:
Theorem: Suppose that is a finite group, and let
be an equation in the variable , where each is in . Then, there is a finite group that contains as a subgroup, and in the equation has a solution.
Even better the proof is quite constructive, and actually proves much more. Besides giving explicitly some properties of are preserved. For example, if is a soluble group, then so is .
I will not have time to explain the proof, but it is interesting that the proof uses the wreath product of groups. Recall the wreath product of groups is very close to the famous zig-zag product of graphs—the wreath product is an older construction. See the great survey by Shlomo Hoory, Nathan Linial, and Avi Wigderson for an introduction to how products are used in expander graphs and other wonderful things.
Note, Levin’s theorem does not allow the “bad” equation that has no solution. It does this by simply not allowing anywhere. The following is fine:
since we can get positive powers of by repeating. But we cannot get negative powers of .
Toward The General Case
I am not an expert, not even close, on equations over groups. I do hope the above shows some of the issues that arise in even the most basic cases. I really need theorems that handle systems of equations and more complex situations.
There is one further general comment that I would like to make. There is a beautiful conjecture that is called the Kervaire-Laudenbach Conjecture. It attempts to handle inverses—as we have seen this is not trivial.
The conjecture looks at the following equations:
where are in . The equation is conjectured to be solvable provided
Recall the bad equation was
which violates this constraint: .
Let’s call a group universal if Barrington’s theorem can be proved over this group. We know the following key insights:
- If is a finite non-abelian simple group, then is universal.
- If is nilpotent, then it is not universal.
- If is solvable and universal, then is contained in
Perhaps we should call such a group a Barrington group, but I hope universal is fine.
The relationship between universal solvable groups and equations over groups is that there are equation systems so if they have a solution, then there is a universal solvable group. I have many such families and will discuss them in detail another time. The general idea is to encode an “AND” gate by the equations. Here is an example of a system : Let be the variables, and let be an element in solvable group . There are four equations:
where is equal to , or based on the rule: If is in or then ; otherwise, it is . Note, we assume that . If can be solved over some solvable group then that group is universal.
I probably made an error in the indices in the above system . Then idea is this: The product . Then, if is placed in the first positions or the last positions the product is still . However, if both are done then the product is equal to . The tricky part if working out the indices to reflect the overlap part, since there two ‘s yield .
The main issue, I believe, is to understand the theory of group equations better. I feel that this would help us in complexity theory a great deal. As noted it could even solve some of the main open questions in the area of low level complexity.
I would like to point out that there is very nice work on the complexity of solving equations over groups. See the paper of Mikael Goldmann and Alexander Russell for a number of results. For example they prove: that the problem of determining if a (single) equation has a solution is NP-complete for all non-solvable groups . Perhaps I will discuss these and related results in the future.