Partial word and equality problems and Banach densities

DOI10.1016/J.AIM.2020.107133MaRDI QIDQ2180889zbMATH OpenOpenAlexFDO

Authors Angela Carnevale, Matteo Cavaleri

Publication date 15 May 2020

Published in Advances in Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Banach densities on free groupsequality problemsgeneric computabilityword problems

Mathematics Subject Classification ID

Undecidability and degrees of sets of sentences (03D35) Generators, relations, and presentations of groups (20F05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Abstract: We investigate partial Equality and Word Problems for finitely generated groups. After introducing Upper Banach (UB) density on free groups, we prove that solvability of the Equality Problem on squares of UB-generic sets implies solvability of the whole Word Problem. In particular, we prove that solvability of generic EP implies WP. We then exploit another definition of generic EP, which turns out to be equivalent to generic WP. We characterize in different ways the class of groups with unsolvable UB-generic WP, proving that it contains that of algorithmically finite groups, and it is contained in that of groups with unsolvable generic WP.

Recommendations

• Generic-case complexity, decision problems in group theory, and random walks.
• Følner functions and the generic word problem for finitely generated amenable groups
• Exponentially generic subsets of groups
• scientific article; zbMATH DE number 3918657
• scientific article; zbMATH DE number 3959758

Cites work

• A proof of a sumset conjecture of Erdős
• Algorithmically finite groups.
• Average-case complexity and decision problems in group theory.
• Cogrowth and amenability of discrete groups
• Cogrowth of groups and simple random walks
• Computability of Følner sets
• Computational complexity and the conjugacy problem
• Densities in free groups and \(\mathbb{Z}^k\), visible points and test elements.
• Exponentially generic subsets of groups
• Finitely presented expansions of groups, semigroups, and algebras
• Følner functions and the generic word problem for finitely generated amenable groups
• GENERIC COMPLEXITY OF THE CONJUGACY PROBLEM IN HNN-EXTENSIONS AND ALGORITHMIC STRATIFICATION OF MILLER'S GROUPS
• Generic complexity of undecidable problems
• Generic properties of Whitehead's algorithm and isomorphism rigidity of random one-relator groups.
• Generic-case complexity, decision problems in group theory, and random walks.
• Genericity, the Arzhantseva-Ol'shanskii method and the isomorphism problem for one-relator groups.
• Group-based cryptography
• scientific article; zbMATH DE number 4031953 (Why is no real title available?)
• scientific article; zbMATH DE number 3584635 (Why is no real title available?)
• scientific article; zbMATH DE number 1955470 (Why is no real title available?)
• On a sumset conjecture of Erdős
• Residually finite algorithmically finite groups, their subgroups and direct products.
• Size of subsets of groups and Haar null sets
• Sumsets contained in sets of upper Banach density 1
• The class of groups all of whose subgroups with lesser number of generators are free is generic
• THE CONJUGACY PROBLEM IN AMALGAMATED PRODUCTS I: REGULAR ELEMENTS AND BLACK HOLES
• THE WORD PROBLEM

Cited in

(1)

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

This page was built for publication: Partial word and equality problems and Banach densities

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