Relative order and spectrum in free and related groups

DOI10.1142/S0219199722500663arXiv2105.03798MaRDI QIDQ6186944FDOQ6186944

Authors: Jordi Delgado, Enric Ventura Capell, Alexander Zakharov 

Publication date: 10 January 2024

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

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.

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

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

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)

Cites Work

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