- Rosenmann, Amnon
- Ventura Capell, Enric
Electronic version of an article published as International Journal of Algebra and Computation, Vol. 34, No. 4, 2024, pp. 439-470 DOI: 10.1142/S0218196724500176 © 2024 World Scientific Publishing Company https://www.worldscientific.com/doi/10.1142/S0218196724500176, Given a finitely generated subgroup H of a free group F, we present an algorithm which computes g_1, ..., g_m \in F, such that the set of elements g \in F, for which there exists a non-trivial H-equation having g as a solution is precisely the disjoint union of the double cosets H \sqcup Hg_1H \sqcup \cdots \sqcup Hg_mH. Moreover, we present an algorithm which, given a finitely generated subgroup H \leq F and an element g \in F, computes a finite set of elements from H \ast \langle x \rangle (of the minimum possible cardinality) generating, as a normal subgroup, the “ideal” I_H(g) \trianglelefteq H \ast \langle x \rangle of all polynomials w(x), such that w(g) = 1. The algorithms, as well as the proofs, are based on the graph-theoretic techniques introduced by Stallings and on the more classical combinatorial techniques of Nielsen transformations. The key notion here is that of dependence of an element g \in F on a subgroup H. We also study the corresponding notions of dependence sequence and dependence closure of a subgroup., The first named author acknowledges the support of the Austrian Science Fund (FWF) project P29355-N35. The second named author acknowledges partial support from the Spanish Agencia Estatal de Investigaci ́on, through grants MTM2017-82740-P and PID2021-126851NB-100 (AEI/ FEDER, UE)., Peer Reviewed, Postprint (author's final draft)