Computability of Følner sets

DOI10.1142/S0218196717500382MaRDI QIDQ4596402zbMATH OpenOpenAlexFDO

Authors Matteo Cavaleri

Publication date 1 December 2017

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

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

zbMATH Keywords

amenable groupsFølner functionFølner setsword problem

Mathematics Subject Classification ID

Word problems, etc. in computability and recursion theory (03D40) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Means on groups, semigroups, etc.; amenable groups (43A07)

Abstract: We define the notion of computability of F{o}lner sets for finitely generated amenable groups. We prove, by an explicit description, that the Kharlampovich group, a finitely presented solvable group with unsolvable word problem, has computable F{o}lner sets. We also prove computability of F{o}lner sets for a group that is extension of an amenable group with solvable word problem by a finitely generated group with computable F{o}lner sets with subrecursive distortion function. Moreover we obtain some known and some new upper bounds for the F{o}lner function in these particular extensions.

Recommendations

• Følner functions and the generic word problem for finitely generated amenable groups
• Computability of finite quotients of finitely generated groups
• Algorithmically insoluble problems about finitely presented solvable groups, Lie and associative algebras. I
• Fast growth in the Følner function for Thompson's group \(F\).
• Folner sets of alternate directed groups

Cites work

• A quasi-isometric embedding theorem for groups.
• Algorithmically complex residually finite groups
• Cellular automata and groups
• Combinatorial group theory.
• Entropy and isoperimetry for linear and non-linear group actions.
• Fast growth in the Følner function for Thompson's group \(F\).
• Følner functions and the generic word problem for finitely generated amenable groups
• Følner Nets for Semidirect Products of Amenable Groups
• scientific article; zbMATH DE number 3845867 (Why is no real title available?)
• scientific article; zbMATH DE number 3762288 (Why is no real title available?)
• On isoperimetric profiles of finitely generated groups.
• Piecewise automatic groups.
• Random walks on free solvable groups
• Relative subgroup growth and subgroup distortion
• Solvable groups with polynomial Dehn functions
• Solved and unsolved problems around one group.
• Topological dimension and dynamical systems. Translated from the French by the author

Cited in

(15)

• The complexity types of computable sets
• Følner functions and the generic word problem for finitely generated amenable groups
• Warsaw discs and semicomputability
• Computability of finite quotients of finitely generated groups
• On decidability of amenability in computable groups
• Partial word and equality problems and Banach densities
• Sofic profiles of \(S(\omega)\) and computability
• Singular coverings and non‐uniform notions of closed set computability
• Computable copies of ℓ p 1
• scientific article; zbMATH DE number 800363 (Why is no real title available?)
• Folner sets of alternate directed groups
• Computable paradoxical decompositions
• Graph automaton groups
• Computable Følner monotilings and a theorem of Brudno
• Fluctuation bounds for ergodic averages of amenable groups

This page was built for publication: Computability of Følner sets

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