Relative order and spectrum in free and related groups

DOI10.1142/S0219199722500663MaRDI QIDQ6186944zbMATH OpenFDO

Authors Jordi Delgado, Enric Ventura Capell, Alexander Zakharov

Publication date 10 January 2024

Published in Communications in Contemporary Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

spectrumfree grouprootdecision problemOrderundecidable problemrelative orderalgorithmic problemStallings autonoma

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Abstract: In this paper, we consider a natural generalization of the concept of order of an element in a group: an element $ginG$ is said to have order $k$ in a subgroup $H$ of $G$ ( esp wrt a coset $Hu$) if $k$ is the first strictly positive integer such that $g^{k}inH$ ( esp $g^{k}inHu$). We study this notion and its algorithmic properties in the realm of free groups and some related families. Both positive and negative (algorithmic) results emerge in this setting. On the positive side, among other results, we prove that the order of elements, the set of orders (called spectrum), and the set of preorders (ie the set of elements of a given order) wrt finitely generated subgroups are always computable in free and free times free-abelian groups. On the negative side, we provide examples of groups and subgroups having essentially any subset of natural numbers as relative spectrum; in particular, non-recursive and even non-recursively enumerable sets of natural numbers. Also, we take advantage of Mikhailova's construction to see that the spectrum membership problem is unsolvable for direct products of nonabelian free groups.

Recommendations

• Quantifying orbit detection: \(\varphi\)-order and \(\varphi\)-spectrum
• SIMPLE ORDERINGS FOR FREE PARTIALLY COMMUTATIVE GROUPS
• Explicit left orders on free groups extending the lexicographic order on free monoids.
• On ordering free groups.
• Spaces of orders and their Turing degree spectra

Cites work

• scientific article; zbMATH DE number 3138253 (Why is no real title available?)
• scientific article; zbMATH DE number 5343239 (Why is no real title available?)
• scientific article; zbMATH DE number 530148 (Why is no real title available?)
• A RESIDUALLY FINITE VERSION OF RIPS'S CONSTRUCTION
• A list of applications of Stallings automata
• Algorithmic problems for free-Abelian times free groups.
• CLOSED SUBGROUPS IN PRO-V TOPOLOGIES AND THE EXTENSION PROBLEM FOR INVERSE AUTOMATA
• Degrees of compression and inertia for free-abelian times free groups
• Finding all solutions of equations in free groups and monoids with involution
• Fixed subgroups and computation of auto-fixed closures in free-abelian times free groups
• Groups whose elements have given orders
• Introduction to group theory. Translated from the Russian. With a new chapter.
• ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM
• On an algorithm to decide whether a free group is a free factor of another
• On convex hulls and the quasiconvex subgroups of \(F_m\times\mathbb Z^n\).
• On fixed subgroups of maximal rank
• On the dynamics of extensions of free-abelian times free groups endomorphisms to the completion
• On torsion in finitely presented groups.
• Primitive words, free factors and measure preservation.
• Stallings automata for free-times-abelian groups: intersections and index
• Stallings foldings and subgroups of free groups
• Topology of finite graphs
• Turing computability. Theory and applications
• Two-letter group codes that preserve aperiodicity of inverse finite automata.
• Unsolvable Problems in Groups With Solvable Word Problem
• \texttt{PSPACE}-complete problems for subgroups of free groups and inverse finite automata

Cited in

(1)

• Quantifying orbit detection: \(\varphi\)-order and \(\varphi\)-spectrum

This page was built for publication: Relative order and spectrum in free and related groups

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