On the word problem for just infinite groups

This paper establishes the decidability of the word problem for various classes of just infinite groups with recursively enumerable relations using direct methods independent of the Wilson–Grigorchuk classification, while also constructing specific counterexamples of locally finite groups where the problem is undecidable for certain presentations.

The Gist

Imagine you are a detective trying to solve a mystery inside a massive, infinite city called Group City. The citizens of this city are "words" (strings of letters), and the city has a very special rule: Just Infinite.

What does "Just Infinite" mean? It means the city is huge and never-ending, but if you try to build a wall (a "normal subgroup") to divide it, the only way to do it without destroying the whole city is to make a wall that leaves you with a tiny, finite village on the other side. You can't make a wall that leaves another infinite city behind.

The Word Problem is the detective's main job: You are given a specific word (a secret code), and you must determine if it is actually the "empty" word (meaning it equals nothing, or 1). Is this code a real secret, or is it just noise that cancels itself out?

This paper, written by Alexey Talambutsa, is a guidebook on how to solve this mystery in different types of Group Cities. Here is the breakdown in simple terms:

1. The Finite City (Finitely Generated Groups)

The Scenario: The city has a fixed, small number of starting keys (generators), say 5 keys. The rules (relations) that tell you how these keys interact are being written down one by one by a robot. The robot never stops writing, but it writes them in a logical order.

The Discovery:
The author proves that for these cities, you can always solve the mystery.

• The Analogy: Imagine two detectives working in parallel.
  • Detective A tries to prove the word is "nothing" by checking the robot's list of rules. If the word cancels out, Detective A will eventually find the proof.
  • Detective B tries to prove the word is not "nothing." This is tricky because the list of rules is infinite. However, because the city is "Just Infinite," if the word is not nothing, the city shrinks into a tiny, finite village when you add that word as a rule. Detective B simply starts listing every possible tiny village (finite groups) and checking if the city fits inside one.
• The Result: One of these two detectives is guaranteed to finish their job. If the word is "nothing," Detective A wins. If it's not, the city becomes finite, and Detective B finds a matching tiny village. Since one of them must finish, the mystery is always solvable.

2. The Infinite City with Infinite Keys (Countably Generated Groups)

The Scenario: Now, the city has an infinite number of keys (Key 1, Key 2, Key 3... forever). The robot is still writing rules, but now the sheer number of keys changes the game.

The Bad News (Uniform Problem):
If you ask the detective to solve the mystery for any city with infinite keys just by looking at the list of rules, it's impossible.

• The Analogy: This is like asking a computer to predict if a program will ever stop running (the Halting Problem). The author shows you can trick the system: you can make a city where the rules depend on whether a computer program stops or not. If the program never stops, the city looks one way; if it stops, it looks another. Since we can't know if the program stops, we can't know if the word is "nothing."

The Good News (Fixed Presentation):
However, if you pick one specific city and stick to its specific rules, you can often still solve the mystery, provided the city isn't "locally finite" (meaning it doesn't have tiny finite pockets everywhere).

• The Analogy: If the city is big and sprawling (not locally finite), it has a "core" that is infinite. The detective can focus on just that core. If the word is "nothing," the core collapses into a tiny village. The detective can check if the core collapses. If it does, the word is "nothing." If it doesn't, the word is real.
• The Catch: If the city is made entirely of tiny finite pockets (locally finite), it gets harder. The detective can only solve it if they can predict how fast the city grows. If they can't predict the growth, the mystery might be unsolvable.

3. The "Monolithic" City

The Scenario: Some Just Infinite cities have a "Monolith"—a single, unbreakable core that is part of every single wall you can build.

• The Discovery: If a city has this Monolith, the mystery is always solvable, even with infinite keys.
• The Analogy: Imagine the city has a "King's Secret." If your word is "nothing," it doesn't affect the King. If your word is not "nothing," it must be connected to the King. The detective just needs to check if the word connects to the King. Since the King is a fixed, known entity, the detective can always find the answer.

4. The Impossible City (Undecidable Presentations)

The Twist: The author constructs a specific, bizarre city (based on a mathematical trick called "Shaded Sets") where the rules are written by a robot, but the robot's writing pattern is so chaotic that no detective can ever solve the mystery.

• The Analogy: The robot writes rules based on a "Busy Beaver" function (a number so huge it's impossible to calculate). The rules are set up so that knowing if a specific key is "nothing" is the same as knowing if a computer program will ever stop. Since we know that's impossible to know, the Word Problem for this specific city is unsolvable.
• The Irony: Even though this specific list of rules makes the problem unsolvable, the city itself (the group) is a "Just Infinite" group that could be described by a different list of rules where the problem is solvable. It's like having a map that is intentionally drawn with errors, making the destination impossible to find, even though the destination itself is perfectly real.

Summary

• Small Cities (Finite Keys): Always solvable. Two detectives working together guarantee a solution.
• Big Cities (Infinite Keys):
  • If you ask for a general solution for any city: Impossible.
  • If you look at a specific city: Usually solvable, unless the city is made of tiny, unpredictable pockets.
  • If the city has a "Monolith" (a core): Always solvable.
• The Trap: You can create a specific set of rules for a city that makes the mystery unsolvable, even though the city itself is "normal."

The paper essentially maps out the boundaries of what we can know about these infinite mathematical structures, showing us where our logic holds up and where it hits a wall.

Technical Summary

Here is a detailed technical summary of the paper "On the Word Problem for Just Infinite Groups" by Alexey Talambutsa.

1. Problem Statement

The paper investigates the decidability of the word problem for just infinite groups. A group $G$ is defined as just infinite if it is infinite, but every proper normal subgroup $H \triangleleft G$ has a finite index (i.e., $G/H$ is finite).

The central question addressed is: Given a presentation of a just infinite group with a recursively enumerable (r.e.) set of relations, is there an algorithm to determine whether an arbitrary word in the generators represents the identity element?

The author distinguishes between two scenarios:

1. Fixed Presentation: The group presentation is fixed, and the algorithm takes a word as input.
2. Uniform Word Problem: The algorithm takes the presentation (generators and relations) and a word as input.

2. Methodology

The author employs a combination of classical computability theory and group-theoretic structural properties.

• Parallel Algorithmic Search: The core methodology for decidability proofs involves running two algorithms in parallel:
  • Algorithm A: Enumerates consequences of the relations to prove $x = 1$.
  • Algorithm B: Attempts to prove $x \neq 1$ by constructing finite quotients or utilizing the specific structural properties of just infinite groups (e.g., factoring out the normal closure of $x$).
• Structural Analysis: The proofs leverage the Wilson–Grigorchuk trichotomy theorem, which classifies finitely generated just infinite groups into three types: branch groups, groups containing a finite index direct product of simple groups, and groups containing a finite index direct product of hereditarily just infinite groups.
• Reduction to Undecidable Problems: To prove undecidability, the author constructs specific group presentations where solving the word problem is equivalent to solving the Halting Problem or determining membership in a non-recursive, recursively enumerable set (specifically, a "shaded set" constructed using the Busy Beaver function).
• Shaded Sets and Wreath Products: A novel construction involves "shaded sets" (subsets of $\mathbb{N}$ formed by merging intervals based on a recursive sequence) and iterated wreath products of finite perfect groups to create counterexamples.

3. Key Contributions and Results

A. Finitely Generated Just Infinite Groups

Theorem 1: For any finitely generated just infinite group with a recursively enumerable presentation, the word problem is uniformly decidable.

• Method: The proof uses a parallel search strategy.
  • Proof of $x=1$: Enumerate relations and check if $x$ reduces to identity.
  • Proof of $x \neq 1$: Add the relation $x=1$ to the presentation. If $x \neq 1$ in the original group, the resulting quotient $G/\langle\langle x \rangle\rangle$ is finite (due to the just infinite property). The algorithm enumerates all finite multiplication tables to find an epimorphism from a finite group to this quotient. If found, $x \neq 1$.
• Significance: This result is achieved without relying on the full classification of just infinite groups, proceeding directly from the definition using ideas from Kuznetsov's theorem (for simple groups) and the Dyson–Mostowski theorem (for residually finite groups).

B. Countably Generated Just Infinite Groups

The paper demonstrates that the uniform decidability result for finitely generated groups does not extend to countably generated groups.

Theorem 2: The uniform word problem is undecidable for countably generated just infinite groups (even for the infinite cyclic group).

• Method: A reduction from the Halting Problem. The relations are constructed such that the group is infinite cyclic, but determining if a specific generator is trivial depends on whether a Turing machine halts.

Theorem 3 (Simple Groups): For a countably generated simple group with an r.e. presentation, the word problem for a fixed presentation is decidable.

• Method: Similar to Kuznetsov's theorem. If $x \neq 1$, the quotient $G/\langle\langle x \rangle\rangle$ is trivial. The algorithm checks if a specific non-trivial word $w$ becomes trivial in this quotient.

Theorem 4 (Non-locally finite): For a countably generated just infinite group that is not locally finite, the word problem for a fixed presentation is decidable.

• Method: Since the group is not locally finite, there exists a finitely generated infinite subgroup $H$. The algorithm checks if the image of $H$ in the quotient $G/\langle\langle x \rangle\rangle$ is finite. If $x \neq 1$, the quotient is finite, so the image of $H$ is finite.

Theorem 5 (Locally finite): For a countably generated locally finite just infinite group, the word problem is decidable if and only if there exists a computable, non-decreasing, unbounded function $f(k)$ bounding the size of subgroups generated by the first $k$ generators.

• Significance: This provides a precise condition for decidability in the locally finite case.

Theorem 6 (Monolithic groups): For any monolithic just infinite group (where the intersection of non-trivial normal subgroups is non-trivial) with a countably generated r.e. presentation, the word problem is decidable.

• Method: The algorithm checks if a fixed non-trivial element of the monolith lies in the normal closure of $x$.

C. Undecidability in Locally Finite Groups

Theorem 7: There exist countably generated locally finite just infinite groups with r.e. presentations for which the word problem is undecidable.

• Construction: The author constructs presentations of iterated wreath products $W = \text{Wr}_{i \in \mathbb{Z}^-} C$ (where $C$ is a finite perfect group).
• Mechanism: The relations are modified using a "shaded set" $I(\alpha)$ derived from the Busy Beaver function. The set of indices of generators equal to the identity in the group corresponds exactly to the non-recursive shaded set.
• Implication: This proves that even within the class of locally finite just infinite groups, the word problem can be undecidable if the presentation is not "well-behaved" (i.e., lacks the computable bound function $f(k)$ from Theorem 5).

4. Significance and Conclusion

1. Resolution of the Finitely Generated Case: The paper settles the decidability question for finitely generated just infinite groups, proving they always have a decidable word problem given r.e. relations. This unifies previous results on simple and residually finite groups without needing the complex classification of branch groups.
2. Distinction between Uniform and Fixed Problems: It highlights a sharp divide: while the uniform word problem is undecidable for countably generated groups, the fixed word problem remains decidable for many important subclasses (simple, non-locally finite, monolithic).
3. Characterization of Locally Finite Cases: The paper provides a necessary and sufficient condition (the existence of a computable growth bound) for the decidability of the word problem in countably generated locally finite just infinite groups.
4. Counterexamples: The construction of locally finite just infinite groups with undecidable word problems demonstrates that the property of being "just infinite" is not sufficient to guarantee decidability in the countably generated setting without additional constraints on the presentation.

Conjecture: The author proposes a weakened version of the Boone–Higman conjecture: A finitely generated group has a decidable word problem if and only if it can be embedded into a finitely presented just infinite group.

In summary, Talambutsa establishes that the structural rigidity of just infinite groups generally ensures decidability in the finitely generated case, but this guarantee breaks down in the countably generated setting unless specific computability conditions on the group's growth or structure are met.