Word Problem For Groups - Algebraic Structure and The Word Problem

Algebraic Structure and The Word Problem

There are a number of results that relate solvability of the word problem and algebraic structure. The most significant of these is the Boone-Higman theorem:

A finitely presented group has solvable word problem if and only if it can be embedded in a simple group that can be embedded in a finitely presented group.

It is widely believed that it should be possible to do the construction so that the simple group itself is finitely presented. If so one would expect it to be difficult to prove as the mapping from presentations to simple groups would have to be non-recursive.

The following has been proved by Bernhard Neumann and Angus Macintyre:

A finitely presented group has solvable word problem if and only if it can be embedded in every algebraically closed group

What is remarkable about this is that the algebraically closed groups are so wild that none of them has a recursive presentation.

The oldest result relating algebraic structure to solvability of the word problem is Kuznetsov's theorem:

A recursively presented simple group S has solvable word problem.

To prove this let ⟨X|R⟩ be a recursive presentation for S. Choose a ∈ S such that a ≠ 1 in S.

If w is a word on the generators X of S, then let:

There is a recursive function such that:

f_{\langle X | R\cup \{w\} \rangle}(x) = \left\{\begin{matrix} 0 &\mbox{if}\ x=1\ \mbox{in}\ S_w\\ \mbox{undefined/does not halt}\ &\mbox{if}\ x\neq 1\ \mbox{in}\ S_w. \end{matrix}\right.

Write:

Then because the construction of f was uniform, this is a recursive function of two variables.

It follows that: h(w)=g(w, a) is recursive. By construction:

h(w) = \left\{\begin{matrix} 0 &\mbox{if}\ a=1\ \mbox{in}\ S_w\\ \mbox{undefined/does not halt}\ &\mbox{if}\ a\neq 1\ \mbox{in}\ S_w. \end{matrix}\right.

Since S is a simple group, its only quotient groups are itself and the trivial group. Since a ≠ 1 in S, we see a = 1 in Sw if and only if Sw is trivial if and only if w ≠ 1 in S. Therefore:

h(w) = \left\{\begin{matrix} 0 &\mbox{if}\ w\ne 1\ \mbox{in}\ S\\ \mbox{undefined/does not halt}\ &\mbox{if}\ w=1\ \mbox{in}\ S. \end{matrix}\right.

The existence of such a function is sufficient to prove the word problem is solvable for S.

This proof does not prove the existence of a uniform algorithm for solving the word problem for this class of groups. The non-uniformity resides in choosing a non-trivial element of the simple group. There is no reason to suppose that there is a recursive function that maps a presentation of a simple groups to a non-trivial element of the group. However, in the case of a finitely presented group we know that not all the generators can be trivial (Any individual generator could be, of course). Using this fact it is possible to modify the proof to show:

The word problem is uniformly solvable for the class of finitely presented simple groups.

Read more about this topic:  Word Problem For Groups

Famous quotes containing the words algebraic, structure, word and/or problem:

    “I have no scheme about it,—no designs on men at all; and, if I had, my mode would be to tempt them with the fruit, and not with the manure. To what end do I lead a simple life at all, pray? That I may teach others to simplify their lives?—and so all our lives be simplified merely, like an algebraic formula? Or not, rather, that I may make use of the ground I have cleared, to live more worthily and profitably?”
    —Henry David Thoreau (1817–1862)

    “Communism is a proposition to structure the world more reasonably, a proposition for changing the world. As such, we have to analyze it and, if we deem it reasonable, act upon it.”
    —Friedrich Dürrenmatt (1921–1990)

    “The word “civilization” to my mind is coupled with death. When I use the word, I see civilization as a crippling, thwarting thing, a stultifying thing. For me it was always so. I don’t believe in the golden ages, you see.... Civilization is the arteriosclerosis of culture.”
    —Henry Miller (1891–1980)

    “The great problem of American life [is] the riddle of authority: the difficulty of finding a way, within a liberal and individualistic social order, of living in harmonious and consecrated submission to something larger than oneself.... A yearning for self-transcendence and submission to authority [is] as deeply rooted as the lure of individual liberation.”
    —Wilfred M. McClay, educator, author. The Masterless: Self and Society in Modern America, p. 4, University of North Carolina Press (1994)