Algorithmically complex residually finite groups

DOI10.1007/S13373-017-0103-ZzbMATH Open1423.20022arXiv1204.6506OpenAlexW2964336870WikidataQ59611694 ScholiaQ59611694MaRDI QIDQ1682244FDOQ1682244

Authors: Olga Kharlampovich, Alexei Myasnikov, Mark Sapir 

Publication date: 29 November 2017

Published in: Bulletin of Mathematical Sciences (Search for Journal in Brave)

Abstract: We construct the first examples of an algorithmically complex finitely presented residually finite groups and first examples of finitely presented residually finite groups with arbitrarily large (recursive) Dehn function and depth function. The groups are solvable of class 3. We also prove that the universal theory of finite solvable of class 3 groups is undecidable.

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

Recommendations

• Publication:5749462
• Residually finite algorithmically finite groups, their subgroups and direct products.
• Algorithms for polycyclic-by-finite groups
• The algorithmic theory of polycyclic-by-finite groups
• scientific article; zbMATH DE number 1419254
• Algorithmic theory of solvable groups
• Groups with orderings of arbitrary algorithmic complexity
• scientific article; zbMATH DE number 4042057
• On certain residually finite groups

zbMATH Keywords

word problemdepth functionMinsky machineDehn function

Mathematics Subject Classification ID

Residual properties and generalizations; residually finite groups (20E26) Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Solvable groups, supersolvable groups (20F16)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Cubulating random groups at density less than \(1/6\).
• Title not available (Why is that?)
• Word Problems Solvable in Logspace
• Title not available (Why is that?)
• ALGORITHMIC PROBLEMS IN VARIETIES
• Varieties of groups
• Title not available (Why is that?)
• Golod-Shafarevich groups: a survey.
• Subgroups of finitely presented groups
• ALMOST EVERY GROUP IS HYPERBOLIC
• The decision problem for some classes of sentences without quantifiers
• Subgroups of small Cancellation Groups
• Quantifying residual finiteness.
• Subgroups of Direct Products of Free Groups
• Bounding the residual finiteness of free groups.
• Hydra group doubles are not residually finite.
• Hydra groups.
• Title not available (Why is that?)
• Solution of the restricted Burnside problem for 2-groups
• SOLUTION OF THE RESTRICTED BURNSIDE PROBLEM FOR GROUPS OF ODD EXPONENT
• Polynomial maps over finite fields and residual finiteness of mapping tori of group endomorphisms
• Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
• Infinite string rewrite systems and complexity
• Isoperimetric and isodiametric functions of groups
• Isoperimetric function of the Baumslag-Gersten group.
• The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
• A non-cyclic one-relator group all of whose finite quotients are cyclic
• Cubulating graphs of free groups with cyclic edge groups.
• Title not available (Why is that?)
• Isoperimetric inequalities and the homology of groups
• Unsolvability of the universal theory of finite groups
• Finite index subgroups in profinite groups.
• Algorithmic problems in varieties of semigroups
• Title not available (Why is that?)
• Subgroups of finitely presented metabelian groups
• A RESIDUALLY FINITE VERSION OF RIPS'S CONSTRUCTION
• Hyperbolic hydra.
• Polynomial Maps over p -Adics and Residual Properties of Mapping Tori of Group Endomorphisms
• The Extrinsic Geometry of Subgroups and the Generalized Word Problem
• A family of groups with nice word problems
• A Finitely Generated Residually Finite Group with an Unsolvable Word Problem
• SOME DUALITY CONJECTURES FOR FINITE GRAPHS AND THEIR GROUP THEORETIC CONSEQUENCES
• Title not available (Why is that?)
• THE WORD PROBLEM FOR SOLVABLE LIE ALGEBRAS AND GROUPS
• LENGTH AND AREA FUNCTIONS ON GROUPS AND QUASI-ISOMETRIC HIGMAN EMBEDDINGS
• On finitely generated soluble linear groups
• Asymptotic invariants, complexity of groups and related problems.
• Minsky Machines and Algorithmic Problems
• Generation of polycyclic groups
• On the parallel complexity of linear groups
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (21)

• Dehn functions of finitely presented metabelian groups
• Obstruction to a Higman embedding theorem for residually finite groups with solvable word problem
• Residually finite algorithmically finite groups, their subgroups and direct products.
• The large-scale geometry of locally compact solvable groups
• Effective twisted conjugacy separability of nilpotent groups
• Computability of Følner sets
• Full residual finiteness growths of nilpotent groups
• Følner functions and the generic word problem for finitely generated amenable groups
• Amenable groups without finitely presented amenable covers
• Isomorphism of finitely generated solvable groups is weakly universal.
• Quantifying local embeddings into finite groups
• Hydra group doubles are not residually finite.
• Zariski closures and subgroup separability
• Residual finiteness and strict distortion of cyclic subgroups of solvable groups
• Quantifying separability in limit groups via representations
• The set of quantum correlations is not closed
• Title not available (Why is that?)
• Computability of finite quotients of finitely generated groups
• Intersection growth in groups
• Taming the hydra: the word problem and extreme integer compression
• Minsky Machines and Algorithmic Problems

This page was built for publication: Algorithmically complex residually finite groups

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