2022/11/18 by Dario Ascari, Ascari, Dario
Mathematics · Computer Science · #Geometric and Algebraic Topology #semigroups and automata theory #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2211.10276
Let F be a finitely generated free group, and let H≤ F be a finitely generated subgroup. An equation for an element g∈ F with coefficients in H is an element w(x)∈ H*⟨ x ⟩ such that w(g)=1 in F; the degree of the equation is the number of occurrences of x and x-1 in the cyclic reduction of w(x). Given an element g∈ F, we consider the ideal \mathfrakIg⊆ H*⟨ x ⟩ of equations for g with coefficients in H; we study the structure of \mathfrakIg using context-free languages. We describe a new algorithm that determines whether \mathfrakIg is trivial or not; the algorithm runs in polynomial time. We also describe a polynomial-time algorithm that, given d∈ℕ, decides whether or not the subset \mathfrakIg,d⊆\mathfrakIg of all degree-d equations is empty. We provide a polynomial-time algorithm that computes the minimum degree dmin of a non-trivial equation in \mathfrakIg. We provide a sharp upper bound on dmin. Finally, we study the growth of the number of (cyclically reduced) equations in \mathfrakIg and in \mathfrakIg,d as a function of their length. We prove that this growth is either polynomial or exponential, and we provide a polynomial-time algorithm that computes the type of growth (including the degree of the growth if it's polynomial).