Remarks and problems about algorithmic descriptions of groups

Basic Information

• Paper ID: 2111.01190
• Title: Remarks and problems about algorithmic descriptions of groups
• Author: Emmanuel Rauzy
• Classification: math.GR (Group Theory), math.LO (Mathematical Logic)
• Submission Date: First submitted November 2, 2021; Second version June 21, 2024
• Paper Link: https://arxiv.org/abs/2111.01190

Abstract

Inspired by the Groves-Wilton theorem, this paper proposes studying the lattice structure of numberings of marked group isomorphism classes as a rigorous and comprehensive framework for investigating global decision problems in finitely generated groups. The article establishes Rice and Rice-Shapiro theorems for recursive presentations and analogous results for co-recursive presentations. The author provides an algorithmic characterization of finitely presentable groups as the semi-decidability of two decision problems: the word problem and the marked quotient problem. The paper explains how to utilize this result to define algorithmic generalizations of finite presentations and finally discusses the incomplete answers provided by the Adian-Rabin theorem in several respects.

Research Background and Motivation

Problem Background

The study of decision problems in group theory originated from three famous problems posed by Max Dehn in 1911: the word problem, the conjugacy problem, and the isomorphism problem. These problems were motivated by topology, particularly the study of fundamental groups. Traditionally, these problems have been studied primarily for finitely presented groups.

Core Motivation

The main motivation of this paper derives from an important theorem of Groves and Wilton:

Theorem 1: There exists an algorithm that, given a presentation of a group G and a solution to the word problem in G, can determine whether G is a free group.

This result indicates that constructing a theory of global decision problems using only finite presentations as the fundamental finite description of groups is insufficient. Instead, one should use finite presentations together with an algorithm for the word problem.

Research Significance

1. Theoretical Refinement: Provides a more rigorous theoretical framework for global decision problems in groups
2. Algorithmic Characterization: Gives algorithmic characterizations of finitely presentable groups
3. Generalization Foundation: Establishes the foundation for algorithmic generalizations of finite presentations

Core Contributions

1. Proposes a Lattice Theory Framework for Numberings: Establishes the lattice structure of numberings of marked group isomorphism classes as a unified framework for studying global decision problems
2. Establishes Rice and Rice-Shapiro Theorems: Develops corresponding Rice and Rice-Shapiro theorems for recursive and co-recursive presentations
3. Algorithmic Characterization of Finitely Presentable Groups: Proves that a group is finitely presentable if and only if it has semi-decidable word problem and semi-decidable marked quotient problem
4. Introduces the Marked Quotient Problem: Proposes a new decision problem concept and analyzes its properties
5. Analyzes Limitations of the Adian-Rabin Theorem: Points out incompleteness of classical results in several respects

Methodology Details

Basic Concept Definitions

Marked Groups and Numberings

• k-marked group: A pair (G,S) where G is a group and S∈G^k is a k-tuple generating G
• Numbering: A partial surjection ν: ⊆ℕ → X from a subset of natural numbers to a set X
• Computable Function: A function f: X → Y is (ν,μ)-computable if there exists a partial computable function F such that for all n∈dom(ν), f∘ν(n) = μ∘F(n)

Lattice Operations

For two numberings ν and μ, define:

• Disjunction ν∨μ: (ν∨μ)(2k) = ν(k), (ν∨μ)(2k+1) = μ(k)
• Conjunction ν∧μ: dom(ν∧μ) = {⟨n,m⟩ | n∈dom(ν), m∈dom(μ), ν(n)=μ(m)}

Main Numbering Types

1. νFP: Finite presentation numbering
2. νRP: Recursive presentation numbering
3. νco-RP: Co-recursive presentation numbering
4. νWP: Word problem algorithm numbering (νRP ∧ νco-RP)
5. νMQA: Marked quotient algorithm numbering

Scott Topology

Define Scott topology on the lattice of k-marked groups (Gk,→), where:

• Scott open sets are upsets that cannot be reached by directed unions
• Compact elements are precisely finitely presentable marked groups

Technical Innovations

1. Unified Numbering Framework

By unifying different types of group descriptions within the numbering theory framework, one can rigorously compare the expressive power of different description methods.

2. Introduction of the Marked Quotient Problem

Definition: Given a marked group (G,S), its marked quotient problem is to determine whether a marked group (H,S') given by a recursive presentation is a marked quotient of (G,S).

The introduction of this concept allows decomposing finite presentations into local information (word problem) and global information (marked quotient problem).

3. Generalization of Rice-Shapiro Theorem

Theorem 4 (Rice-Shapiro Theorem for Recursive Presentations): If P is a property of marked groups that is semi-decidable from recursive presentations, then there exists a computably enumerable sequence of finite presentations such that a group satisfies P if and only if it is a marked quotient of some group defined by these presentations.

Experimental Setup

This paper is primarily theoretical research without traditional experimental setup, but includes extensive constructive proofs and algorithmic analysis.

Theoretical Verification Methods

1. Constructive Proofs: Proving existence results through explicit algorithm construction
2. Diagonalization Techniques: Using diagonalization methods similar to the halting problem to prove undecidability
3. Reduction Methods: Reducing problems to known undecidable problems

Main Results

1. Algorithmic Characterization of Finitely Presentable Groups

Theorem 7: A marked group (G,S) is finitely presentable if and only if it has semi-decidable word problem and semi-decidable marked quotient problem. Formalized as numbering equivalence: νFP ≡ νRP ∧ νMQA

2. Generalization of Rice's Theorem

Corollary 5: For groups with recursive presentations, there exists no non-trivial decidable marked group property. Corollary 37: For groups with co-recursive presentations, there exists no non-trivial decidable group property.

3. Topological Characterization

Corollary 30: The topology generated by sets semi-decidable from recursive presentations is precisely the Scott topology on the lattice of marked groups.

4. Relative Marked Quotient Algorithm

Proposition 54: The lamp group Z/2Z≀Z has a marked quotient algorithm for the class of finite groups. Proposition 55: The lamp group cannot be finitely presented as a residually finite group.

Related Work

Classical Decision Problem Theory

• Dehn Problems: Classical study of word problem, conjugacy problem, and isomorphism problem
• Adian-Rabin Theorem: Undecidability of Markov properties
• Higman Embedding Theorem: Embedding properties of recursively presentable groups

Computability Theory

• Malcev Numbering Theory: Computable representations of mathematical objects
• Rice's Theorem: Undecidability of program properties
• Banach-Mazur Computability: Computability concepts on real numbers

Geometric Group Theory

• Limit Group Theory: Universal theory models of free groups
• Hyperbolic Groups: Algorithmic decidability of geometric properties
• CAT(0) Groups: Properties of non-positively curved groups

Conclusions and Discussion

Main Conclusions

1. Effectiveness of the Numbering Lattice Framework: Demonstrates that numbering lattice theory provides an effective mathematical framework for studying global decision problems in groups
2. Essence of Finite Presentations: Reveals that finite presentations are essentially combinations of weak local information (semi-decidable word problem) and strong global information (semi-decidable marked quotient problem)
3. Universality of Rice's Theorem: Demonstrates the broad applicability of Rice's theorem in group theory

Limitations

1. Incomplete Theory for Co-recursive Presentations: Lacks a complete Rice-Shapiro theorem for co-recursive presentations
2. Insufficient Classification at Higher Arithmetic Levels: Classification of properties at higher levels of the arithmetic hierarchy remains incomplete
3. Complexity of Constructions: Some constructions require sophisticated techniques, potentially limiting practical applications

Future Directions

1. Problem 40: Establish a complete Rice-Shapiro theorem for co-recursive presentations
2. Problem 62: Precise classification of more group properties in the arithmetic hierarchy
3. Problem 64: Establish sufficient conditions for undecidability in the case of finite presentations plus word problem algorithm

In-Depth Evaluation

Strengths

1. Theoretical Innovation: Proposes a novel numbering lattice framework, providing a unified perspective on decision problems in group theory
2. Technical Depth: Skillfully combines computability theory with group theory, demonstrating sophisticated proof techniques
3. Problem-Oriented: Clearly formulates multiple important open problems, directing future research
4. Systematicity: Systematically investigates group description problems from multiple angles (recursive, co-recursive, relative algorithms)

Weaknesses

1. Limited Practical Applicability: Primarily theoretical research with limited direct application value to practical group-theoretic computation
2. High Technical Threshold: Requires deep background in both computability theory and group theory, potentially limiting its scope of influence
3. Incomplete Results: Some results remain open, such as the Rice-Shapiro theorem for co-recursive presentations

Impact

1. Theoretical Contribution: Provides new mathematical tools for decision problem theory in group theory
2. Interdisciplinary: Promotes cross-fertilization between group theory and computability theory
3. Methodological Value: The numbering lattice method may be applicable to studying other algebraic structures

Applicable Scenarios

1. Theoretical Group Theory Research: Provides new tools for studying algorithmic properties of groups
2. Computable Algebra: Extension to computability studies of other algebraic structures
3. Complexity Theory: Provides group-theoretic perspectives on algorithmic complexity analysis

References

The paper cites 69 important references covering classical and cutting-edge work in group decision problems, computability theory, geometric group theory, and other related fields, reflecting the depth and breadth of the research.

Overall Assessment: This is a high-quality theoretical mathematics paper with significant theoretical value in the study of decision problems in group theory. By introducing the numbering lattice framework, the author provides a novel research perspective on this classical field and obtains a series of profound theoretical results. Although its practical applicability is relatively limited, its theoretical contributions and methodological value make it an important reference in the field.