Følner functions and the generic word problem for finitely generated amenable groups

DOI10.1016/J.JALGEBRA.2018.06.017zbMATH Open1427.20037arXiv1703.04133OpenAlexW2603535217MaRDI QIDQ1663531FDOQ1663531

Matteo Cavaleri

Publication date: 21 August 2018

Published in: Journal of Algebra (Search for Journal in Brave)

Abstract: We introduce and investigate different definitions of effective amenability, in terms of computability of F{o}lner sets, Reiter functions, and F{o}lner functions. As a consequence, we prove that recursively presented amenable groups have subrecursive F{o}lner function, answering a question of Gromov, for the same class of groups we prove that solvability of the Equality Problem on a generic set (generic EP) is equivalent to solvability of the Word Problem on the whole group (WP), thus providing the first examples of finitely presented groups with unsolvable generic EP. In particular, we prove that for finitely presented groups, solvability of generic WP doesn't imply solvability of generic EP.

Full work available at URL: https://arxiv.org/abs/1703.04133

Recommendations

• Computability of Følner sets
• Partial word and equality problems and Banach densities
• Exponentially generic subsets of groups
• Generic-case complexity, decision problems in group theory, and random walks.
• scientific article; zbMATH DE number 3959758

zbMATH Keywords

word problemdiscrete amenable groupseffective amenabilitygeneric computabilitygeneric equality problemFølner functions

Mathematics Subject Classification ID

Cut-elimination and normal-form theorems (03F05) Means on groups, semigroups, etc.; amenable groups (43A07) Decidability of theories and sets of sentences (03B25) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Word problems, etc. in computability and recursion theory (03D40)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithmically finite groups.
• Generic complexity of undecidable problems
• ALMOST EVERY GROUP IS HYPERBOLIC
• Entropy and isoperimetry for linear and non-linear group actions.
• Title not available (Why is that?)
• Algorithmically complex residually finite groups
• Cellular Automata and Groups
• Group-based cryptography
• A small simplification in hyperbolic groups
• Generic-case complexity, decision problems in group theory, and random walks.
• Generic computability, Turing degrees, and asymptotic density
• ASYMPTOTIC DENSITY AND COMPUTABLY ENUMERABLE SETS
• On isoperimetric profiles of finitely generated groups.
• Title not available (Why is that?)
• A quasi-isometric embedding theorem for groups.
• Piecewise automatic groups.
• The class of groups all of whose subgroups with lesser number of generators are free is generic
• Fast growth in the Følner function for Thompson's group \(F\).
• THE WORD PROBLEM
• Genericity, the Arzhantseva-Ol'shanskii method and the isomorphism problem for one-relator groups.
• Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.
• Exponentially generic subsets of groups
• Topological dimension and dynamical systems. Translated from the French by the author
• Random walks on free solvable groups
• Computability of Følner sets
• Speed of random walks, isoperimetry and compression of finitely generated groups

Cited In (7)

• On decidability of amenability in computable groups
• Fluctuation bounds for ergodic averages of amenable groups
• Computability of Følner sets
• Sofic profiles of \(S(\omega)\) and computability
• Computable paradoxical decompositions
• Partial word and equality problems and Banach densities
• Graph automaton groups

This page was built for publication: Følner functions and the generic word problem for finitely generated amenable groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1663531)