Computable Følner sequences of amenable groups

Basic Information

• Paper ID: 2509.11806
• Title: Computable Følner sequences of amenable groups
• Authors: Karol Duda, Aleksander Ivanov
• Classification: math.GR (Group Theory), math.LO (Mathematical Logic)
• Publication Date: October 11, 2025 (arXiv v2)
• Paper Link: https://arxiv.org/abs/2509.11806

Abstract

This paper investigates computable Følner sequences in computably enumerable amenable groups. The authors generalize fundamental results of M. Cavaleri concerning the existence of such sequences to groups without the assumption of finite generation. Simultaneously, the work opens new research directions on this topic, such as the complexity of effective Følner sequence families. The paper also discusses potential extensions of the methodology to metric groups.

Research Background and Motivation

Problem Context

1. Amenability Theory: Amenable groups constitute an important concept in group theory with broad applications in harmonic analysis, geometric group theory, and topological dynamics
2. Følner Condition: Følner sequences serve as an essential tool for characterizing amenable groups, providing a combinatorial characterization of amenability
3. Computability Theory: Studying classical mathematical concepts from the perspective of algorithmic complexity represents an important trend in modern mathematical logic

Research Motivation

1. Theoretical Generalization: Cavaleri's work is restricted to finitely generated recursively presented groups, whereas amenability does not require the finite generation condition
2. Algorithmic Complexity: A deeper understanding of the algorithmic complexity of effective Følner sequences is needed
3. Application Extension: Exploring the application prospects of this theory in metric groups

Limitations of Existing Approaches

1. Cavaleri's results are limited to finitely generated groups
2. Lack of systematic study of the complexity of Følner sequence families
3. Metric groups have not been considered

Core Contributions

1. Generalization of Main Theorem: Extends Cavaleri's results on finitely generated groups to computably enumerable numbered groups
2. Complexity Analysis: Proves that the set of effective Følner sequences belongs to the Π₀₃ class and is Π₀₃-complete in certain abelian group cases
3. Convergence Modulus Study: Analyzes the complexity of convergence moduli corresponding to Følner sequences
4. Metric Group Extension: Provides a theoretical framework for amenability of computable metric groups

Methodology Details

Core Concept Definitions

Numbered Groups

Definition 2.1: Let G be a group and ν : ℕ → G be a surjective function. The pair (G,ν) is called a numbered group, and ν is called a numbering of G.

Følner Sets

Definition 2.6: Given n ∈ ℕ and D ⊂fin G, a finite subset F ⊂fin G is called a 1/n-Følner set with respect to D if:

∀x ∈ D, |F \ xF|/|F| ≤ 1/n

Effective Amenability

Definition 3.1: A numbered group (G,ν) is Σ-amenable if there exists an algorithm that, for all (n,D) where n ∈ ℕ and D ⊂fin ℕ, finds a set F ⊂fin ℕ such that F has a subset F' ⊆ F satisfying ν(F') ∈ FølG,ν(D)(n).

Definition 3.2: A numbered group (G,ν) is computably amenable if there exists an algorithm that, for all (n,D), finds a finite set F ⊂ ℕ such that ν(F) ∈ FølG,ν(D)(n) and |F| = |ν(F)|.

Main Theoretical Results

Theorem 1 (Characterization of Computably Enumerable Groups)

Let (G,ν) be a computably enumerable numbered group. Then the following conditions are equivalent:

1. G is amenable
2. (G,ν) has a computable Reiter function
3. (G,ν) has a subrecursive Følner function
4. (G,ν) is Σ-amenable

Furthermore, the computable amenability of (G,ν) is equivalent to its computability.

Theorem 2 (Complexity Analysis)

The set of all effective Følner sequences belongs to the Π₀₃ class and is Π₀₃-complete in certain abelian group cases.

Technical Innovations

1. Numbered Group Methodology: Employs the concept of numbered groups to provide a unified treatment of computability issues
2. Hierarchical Complexity: Distinguishes between two levels of complexity: Σ-amenability and computable amenability
3. Metric Generalization: Extends the theory to metric groups

Experimental Setup

Theoretical Verification

This work is primarily theoretical, with results verified through rigorous mathematical proofs:

1. Constructive Proofs: Existence results are established through algorithmic constructions
2. Complexity Reductions: Complexity lower bounds are proven via reductions
3. Counterexample Construction: Specific examples are constructed to demonstrate the unboundedness of convergence moduli

Concrete Examples

• Integer Group ℤ: Standard Følner sequence F = ({-i,-i+1,...,0,...,i-1,i} | i ∈ ℕ)
• Direct Sum Group ⊕n∈ωℤ: Used to prove Π₀₃-completeness

Experimental Results

Main Results

Theorem 3 (Convergence Modulus)

For any total computable function f : ℕ → ℕ, there exists a computable x₀ ∈ 2^ℤ such that the sequence mᵢ(x₀) converges to 0, but for each k ∈ ℕ there exists j > f(k) such that |mⱼ(x₀)| ≥ 1/k.

Theorem 4 (Metric Group Case)

A computably enumerable numbered metric group (G,d,ν) is computably amenable if and only if it is amenable and computable.

Complexity Analysis Results

1. Upper Bound: The set of effective Følner sequences ∈ Π₀₃
2. Lower Bound: For G = ⊕n∈ωℤ, this set is Π₀₃-complete
3. Convergence: Convergence moduli cannot be bounded by primitive recursive functions

Related Work

Foundational Theory

1. Cavaleri's Work: Computable amenability of finitely generated recursively presented groups
2. Moryakov's Contributions: Effective Birkhoff ergodic theorem
3. Classical Amenability Theory: Følner conditions, Reiter conditions, etc.

Computational Complexity

1. Computable Algebra: General theory of numbered structures
2. Arithmetic Hierarchy: Classification of complexity classes
3. Real Computability: Ko-Friedman theory

Conclusions and Discussion

Main Conclusions

1. Successfully generalizes Cavaleri's results to the non-finitely generated case
2. Establishes a complete complexity characterization of effective Følner sequences
3. Provides a theoretical framework for metric groups

Limitations

1. The Reiter function theory for metric groups remains incomplete
2. Some constructions are non-constructive
3. Algorithmic efficiency issues in practical applications

Future Directions

1. Develop a complete Reiter theory for metric groups
2. Investigate computable amenability for other classes of groups
3. Explore connections with topological dynamics

In-Depth Evaluation

Strengths

1. Theoretical Depth: Deep integration of classical group theory with modern computability theory
2. Technical Innovation: Systematic application of the numbered group methodology
3. Completeness: Provides a complete picture from existence to complexity
4. Generalizability: Successfully generalizes classical results to more general settings

Weaknesses

1. Practical Applicability: Primarily theoretical results; algorithmic efficiency in practice requires further investigation
2. Completeness: Metric group theory remains incomplete
3. Examples: Lacks analysis of more concrete groups

Impact

1. Theoretical Contribution: Provides new tools for computable group theory
2. Interdisciplinary: Connects group theory, logic, and computational complexity
3. Future Research: Provides a framework for related research areas

Applicable Scenarios

1. Theoretical research in computable group theory
2. Complexity analysis in algorithmic group theory
3. Computability problems in topological dynamics

References

Key references include:

• M. Cavaleri's pioneering work on computable Følner functions
• Standard textbooks on classical amenability theory
• Foundational theory of computable algebra
• Recent results by Schneider-Thom on amenability of topological groups

This paper makes important contributions at the intersection of theoretical group theory and computability theory. It not only generalizes existing results but also opens new research directions. Its rigorous mathematical arguments and systematic theoretical framework provide a solid foundation for subsequent research.