The Word Problem for Free Groups
The word problem for free groups is in DLOG
Zeke Zalcstein worked, before he retired a few years ago, on the boundary between mathematics and computational complexity. He started his career in mathematics, and then Zeke moved into computational complexity theory. His PhD advisor was John Rhodes who is an expert on many things, including the structure of semigroups; Rhodes has recently worked on the P=NP question himself; more on that in another post. The picture is John Rhodes since Zeke is camera shy.
I have known Zeke since I was a graduate student at Carnegie-Mellon and he was faculty there. Later, Zeke worked at a number of universities, including Stony-Brook, and then spend the latter part of his career as a program director at CISE/NSF.
Zeke loves to laugh, he is funny, he knows tons of mathematics–especially algebra, but he is a character in the best sense of the word. For example, he is very particular about what he eats and drinks, even his water cannot be just any water. When Zeke was at Stony-Brook he discovered that there was a water source in a certain open field that had the best water in the world. Not just Stony-Brook, the world. The water source was a faucet coming out of the ground, in an otherwise empty field. I asked Zeke where the water came from, the faucet was simply connected to a pipe that came out of the ground, no label, no sign, nothing. Did it come from a spring, from a well, or from the city water main? Zeke said he just knew it was great water.
Unfortunately, one day Zeke fell and broke his arm so it was impossible for him to drive for several weeks. While Zeke was incapacitated, a certain graduate student was kind enough to make periodic trips out to the faucet, fill up plastic jugs with the special water, and deliver them to Zeke.
I was once telling this story to John Hennessy, who is the President of Stanford University. He started to laugh, and confirmed the story: John had been the graduate student who was kind enough to help Zeke.
Enough, on to the main topic of today’s post. Zeke and I worked together on a number of problems over the years, and today I will talk about one that has a curious history, a neat proof, and a interesting application that never really happen.
The Problem and Our Results
The problem is: what is the space complexity of the word problem for the free group on two letters? This is not how we first heard the problem, but it is equivalent to what we were asked. The free group on two letters “a” and “b” is the group where the only relationships are:
It is called the free group since these are the minimal relations that can hold in any group. As usual the word problem is to determine given any word over whether or not it equals . For the rest, when we say word problem, we mean “the word problem for the free group on two letters.”
Zeke and I proved:
Theorem: The word problem is in .
Actually we can proved more:
Theorem: A probabilistic log-space machine that has a one-way read only input tape can solve the word problem with error at most , for any .
There is a simple linear time algorithm for the word problem. The algorithm uses a pushdown store, which is initially empty. The algorithm processes each input symbol as follows: If the top of the pushdown is and , then pop off the top of the pushdown; if not, then push onto the pushdown. Then, go to the next input symbol. When there is no more input symbols accept only if the pushdown is empty. The algorithm clearly runs in linear time, and it is not hard to show that it is correct.
This algorithm uses linear space: a string that starts with many ‘s will, for example, require the pushdown to hold many symbols. Thus, the goal is to find a different algorithm that avoids using so much space.
My on-going agenda, in these posts, is to explain the role people play in doing research. In the next two sections I will explain the “curious history” of the question: who I “think” first asked the question, and why they may have asked the question. Then, I will explain the how we solved the problem and proved a theorem. You can skip the next two sections and get right to the proof method. No history. No background. But, I hope that you find the history and motivation interesting. Your choice.
Who Asked the Question?
My memory for technical conversations is usually pretty good, but this question on the space complexity of the word problem has a murky history. My version is that at a STOC conference, years ago, Juris Hartmanis mentioned a related problem to a number of us over a coffee break. I instantly liked the problem, and during the next few months Zeke and I worked on the problem, until we found a solution.
At the next conference, FOCS, we told Juris our solution to “his” problem. Juris said that he liked the problem, liked our solution, but he had never asked us the problem. Who knows. At least we did not call the paper: “On a Conjecture of Hartmanis.” I still believe, sometimes, that maybe Juris told it to us, but I must be confused. Anyway I think you will like the method we used to solve it.
Why Did They Ask It?
The problem that someone asked us, was not what is the space complexity of the word problem for the free group on two letters. Instead we were asked a more “language” type question that is the same as the word problem. We were asked: what is the space complexity of a certain language ?
Before defining it may help to explain where comes from. Define the following language over the alphabet that contains two types of parentheses: “” and “” and “” and “”. A string is in provided the application of the following rules eventually lead to the empty string:
is in the language, but
is not. Note, is closed under concatenation.
The language consists of expressions with two types of parentheses that are well nested: sometimes it is called the Dyck language. Each must have a matching and also each must have a matching . Moreover, the two types of parentheses must not get in each others way, thus
is not in .
The Dyck language is a context-free language, and is central to the theory of context-free language theory. Thus, another way to define is by the following context free grammar: (The symbol is the empty string.)
The following is an easy theorem:
Theorem: The language is in .
I will now explain how to prove this theorem; to do this we need the notion of matching parentheses. In a string say that matches provided and as we count left-to-right is the first time that starting with that the number of and are equal. There is a similar definition for the parentheses and . We call and left parentheses and and right parentheses.
Call a string good provided it satisfies the following:
- for every left parentheses of either type there is a matching right one of the same type;
- for every right parentheses of either type there is a matching left one of the same type;
- if matches and matches , then and are disjoint intervals or one wholly contains the other.
The last means that there is no overlapping matches. It should be clear that checking whether or not a string is good can be done easily in log-space.
Lemma: A string is good if and only if is in .
It is easy to see that all strings in are good. So suppose that there is a good string that is not in . Select the shortest possible string . The first symbol of must be a left parentheses by (2). So assume that . There must be a right parentheses in by (1) so assume that is the first one. Clearly, . Suppose that . Then, the previous must equal ; otherwise, would not be the shortest possible counterexample. Thus,
where are all left parentheses. By (2) the matches some earlier , but the matches some later and this contradicts (3).
Next suppose that . Then, the previous must equal ; otherwise, would not be the shortest possible counterexample. Thus,
where again are all left parentheses. By (2) the matches some earlier , but the matches some later and this contradicts (3).
Now let us finally define the language It is a variation of the Dyck language that allows a different type of pairing of the symbols. This difference makes proving that it lies in harder. This is the question, someone asked us–I guess not Juris. Sometimes is called a “two-sided” Dyck language.
A string is in provided the application of the following rules eventually lead to the empty string:
The point of is that the parentheses have a type but no “direction.”
The trouble with is there does not seem to be a counterpart to the notion of matching; a string of the form:
could have the match with a that comes earlier. This is why I do not know a direct counting method to recognize . I guess this is why someone asked us the question. I wish I could remember who.
Zeke and I knew two insights, one trivial and the other based on a classic result from group theory. The first is that is really the same as accepting the words from a free group on two letters.
The second insight is that the free group on two letters has a faithful representation over integer valued matrices; this result was proved by Ivan Sanov in 1947.
Theorem: There are two integer matrices so that the mapping and is a faithful representation of the free group on .
Actually we can construct the matrices explicitly. Consider the following two matrices: is
Both matrices are invertible and further their inverses are also integer matrices The map that sends
defines a mapping from the free group on two letters, to : the latter is the matrices over the integers with determinant This mapping is a group isomorphism.
That means that we can replace the word problem by: does a sequence of matrices over equal the identity matrix . This transformation of the word problem into a problem about matrices is the key to our results. For example,
Here is how Zeke and I use this transformation to prove the our theorem. We show how to check whether or not
is equal to where each is from . The obvious way to do this is to compute matrix and see if it is equal to . The difficulty with this approach is that the matrix may have entries that are too large and cannot be stored in log-space.
We solve this with the Chinese Remainder Theorem. Suppose that is a prime with at most bits. Let . A log-space machine can pass over the input and compute the product : this means that we do all the arithmetic modulo , but we still are multiplying matrices. Then, the machine checks whether or not . If it does not, then clearly , and we can reject the input. The machine does this for all primes of the given size. If all , then the machine accepts.
We claim that this algorithm is correct. The insight is that if is not equal to , then has some non-zero entry, which cannot be too large. Then, by the Chinese Remainder Theorem we have a contradiction, and so the algorithm is correct. This uses the well known fact that
where the product is over primes and .
Finally, the probabilistic result follows in essentially the same way. The only difference is that now the machine randomly selects one prime to check. We then argue that the non-zero entry of is unlikely to be divisible by a randomly selected prime. This relies the simple fact that the non-zero entry can only have a polynomial number of prime factors. Thus, as long as we randomly select the prime from a large enough set, it is unlikely that the non-zero entry will be modulo the prime.
What does the Karp-Rabin pattern matching algorithm have to do with our result on the word problem? Indeed. Dick Karp and Michael Rabin are both famous for so many things, but one of my favorites of their results is their randomized pattern matching algorithm.
Rabin has told how they first thought of their algorithm. They needed a way to hash strings that had a certain property, and our mapping from the free group to matrices modulo a prime worked perfectly. So at one time they were using the same technology that we used to solve the word problem in log-space.
Unfortunately for Zeke and I, they quickly got rid of the matrix ideas and replaced them by a much simpler method. But Michael has repeatedly told me that the matrix ideas played a role in his initial thinking.
Our proof method could handle a larger class of word problems, than just the word problem for free groups. Suppose that is any linear group over the rationals. Then, the word problem for this group can also be solved in . One can even prove more, but see our paper for the details. Thus, many infinite groups have word problems that can be done in log-space.
The power of matrix representation theory is something that you may be able to use to solve other problems. I believe that we have not made as much use of the power of representation methods in other parts of computer science as perhaps we could. In any event the mapping may itself be useful to you.
Now if I could only recall who initially asked me the problem