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:
Thus,
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:
and
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.
Our Solution
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.
and
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
|
and 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.
Karp-Rabin
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.
Open Problems
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
Trackbacks
- New Streaming Algorithms for Old Problems « Gödel’s Lost Letter and P=NP
- What Makes a Knot Knotty? « Gödel’s Lost Letter and P=NP
- Ode To The Math Monthly « Gödel’s Lost Letter and P=NP
- Twin Primes Are Useful | Gödel's Lost Letter and P=NP
- How To Carry Fame | Gödel's Lost Letter and P=NP
- ALogTime, LogCFL, and threshold circuits: dreams of fast solutions | Gentzen translated
Lovely post!
Great post! I love the Karp-Rabin algorithm, it’s beautifully simple, one of the many examples Rabin has given of the power of randomness (your post that mentioned his O(n) closest pair in 2d space algorithm was also interesting). If you pay attention to parameters, it’s also a useful building block for many neat string matching algotithms (finding all palindromes in a long string for example).
Interesting to know the relation to your work on the word problem. Somehow the more complicated solution came first.
One question about balance lemma: suppose we have w = “(((((“, it seems it satisfies mentioned condition, but indeed it doesn’t belong to D.
I am sorry, I made a silly error in the post. The definition and the Balance Lemma are slightly off. First, the definition needs to allow [][][] to be in the language–I have fixed this. Second, the Balance Lemma needs to be fixed too: the string w itself must be [-balanced and (-balanced.
I will update post in am. Thanks for reading so closely. Again sorry for the errors…rjlipton
Did you ever think that a post is unlucky? I seem to be having a great deal of trouble getting this one right. I again an sorry for any trouble or confusion.
Is this post unlucky? At least the following statement is also wrong: “This mapping \( \rho : F_2 \to \mathsf{SL}(2,\mathsf{Z}) \) is a group isomorphism.” It is not an isomorphism, but only a monomorphism. The matrices in the image are congruent to the identity modulo 2…
for D and D2 and in particular the Balance Lemma, is it correct that you’re also assuming the languages are closed under concatenation? e.g. is ([]()) in D?
“A probabilistic log-space machine that has a one-way read only input tape”
Thought provoking! So this is the first streaming algorithm 🙂
Ah, in your fix, you seem to have cut out the part where you defined D2…
It could be added that the one-sided Dyck languages are in TC0
(Lynch’s algorithm seen as a circuit) while the two-sided ones
are NC1-hard as shown in Robinson’s thesis (1993, San Diego).
Is the group generated by the two 2×2 matrices
[3 5]
[0 5]
and
[2 0]
[0 3]
free?
I do not know if these matrices are free? I see the issue. Is there an application in mind. As you may know the prove that the ones I mention are free relies on showing that the sequence of matrices is coded into the one of the entries of the matrix product.
It’s just an open problem that I don’t know how to solve. Seems amazing that such a simple problem could cause difficulties.
I knew Zeke Zalcstein back in the late 70’s and very early 80’s. If you can get my e-mail to him (or let me know his) I’d appreciate it. I know this is the right Zeke as there can be only one Zeke with his nutritional thoughts. I an unique but not as unique as he is.
Thanks.
P.Bauter pbauter@net66.com