Dependence over subgroups of free groups (Q6573211)

Let \(G\) be a group and \(H\) a subgroup of \(G\). An (univariate) ``polynomial'' over \(H\) is an element \(w(x)\) of the free product \(H\ast \langle x \rangle\), where \(\langle x \rangle\) is the infinite cyclic group. Namely \[w(x) = h_{0}x^{e_{1}}h_{1}x^{e_{2}} \cdots x^{e_{n-1}}h_{n-1}x^{e_{n}}h_{n}\] with \(h_{i}\in H\) and \(e_{i}=\pm 1\). The number \(n=\sum _{i=1}^{n}\mid e_{i}\mid \) is the degree of the polynomial \(w(x)\). Given a \(w(x)\in H\ast \langle x \rangle\), a question is to decide if there exist \(g\in G\) such that \(w(g) = 1 \in G\). Therefore, if the equation \(w(x) = 1 \) has a solution in \(G\) and when it has solutions, the question is to describe the set of all such solutions and its structure.\N\NIn this paper, the authors study the above kind of equations in the case where the (over)group \(G\) is a free group and the subgroup \(H\) is a finitely generated subgroup.\N\NBefore describing the main results, we quote some definitions and terminology.\N\NDefinition 1.1. Let \(G\) be a group, \(H\leq G\) a subgroup\Nand \(g\in G\). We say that \(g\) is dependent on \(H\) if there exists a non-trivial \(H\)-equation\N\(w(x)=1\) that is satisfied by \(g\). More generally, \(g\) is dependent on a subset \(S\subseteq G\)\Nif it is dependent on the subgroup \(H = \langle S \rangle \). We denote by \(\mathrm{dep}_{G}(H)\) the set of elements in \(G\) that depend on \(H\) and by \(\mathrm{Dep}_{G}(H) = \langle \mathrm{dep}_{G}(H) \rangle\), the subgroup they generate, which is called the dependence subgroup of \(H\). When there is no risk of confusion, we shall delete the subscript \(G\) from the notation.\N\NEquivalent definitions for dependence of elements in the setting of free groups are given in Proposition 2.1 of the paper.\N\NDefinition 1.7. Let \(H\leq G\). The subgroup \(H\) is called dependence-closed if \(\mathrm{Dep}(H) = H\), i.e. if the only elements \(g\in G\) which are solutions to non-trivial \(H\)-equations are those \(g\in H\). For example, any free factor of \(G\) is clearly dependence-closed.\N\NProperties of a dependence-closed subgroup are given in Proposition 1.11 of the paper.\N\NThe first main result of the paper is the following:\N\NTheorem 4.1. Let \(F(A)\) be the free group with basis \(A\). Given a finite set of generators of total length \(n\) for a finitely generated subgroup \(H\leq F(A)\),\None can algorithmically compute a finite set\N\(\{ g_{0} = 1, g_{1}, \dots , g_{m} \}\) of elements of \(F(A)\) that depend on \(H\)\Nand such that \(\mathrm{dep}(H)\) is the disjoint union of the corresponding\Ndouble cosets in \(O(n^{3} log^{\ast}(n))\) time, \(\mathrm{dep}(H) = H \sqcup Hg_{1}H \sqcup \cdots \sqcup Hg_{m}H\).\N\NA dual notion (in a sense), of the set \(\mathrm{dep}(H)\) of elements in \(G\) that are dependent on \(H\), is the notion of the ``ideal'' of an element of the group \(G\). Namely, given a \(g\in G\), it is defined as\N\(I_{H}(g) = \{ w(x)\in H\ast \langle x \rangle \mid w(g) = 1 \} \triangleleft H\ast \langle x \rangle\). Is it trivial or non-trivial? If it is non-trivial, one can compute a finite set of generators (as a normal subgroup)?\N\N\N\NTheorem 5.3. Let \(H\leq F(A)\) be a finitely generated subgroup of rank \(n\) and let \(1 \neq g\in F(A)\) be dependent on \(H\) and such that\N\(\operatorname{rk}( \langle H, g \rangle )= m\leq n\). Then, there exists an algorithm that, given\Na finite set of generators for \(H\), computes a set of \(n+1-m\) normal generators of the\Nideal \(I_{H}(g)\unlhd H\ast \langle x \rangle\):\N\N\(I_{H}(g) = \langle \langle w_{1}(x), \dots , w_{n-m+1}(x) \rangle \rangle\).\N\NThe authors give two proofs of this theorem. The first is based on Nielsen transformations and the second one on Stallings graph-theoretic techniques providing, respectively, an algebraic and a geometric reason for such equations to exist.\N\NWhen \(H\) is not dependence-closed then \(\operatorname{dep}(H)\), the set of all dependent elements on \(H\), strictly contains \(H\). But then, when constructing the subgroup \(\operatorname{Dep}(H)\) generated by these elements, new elements may arise, which depend on \(\operatorname{Dep}(H)\) but not on \(H\). Therefore, an ascending sequence of subgroups \(H_{0}\leq H_{1}\leq H_{2}\leq \cdots \leq \) is defined by \(H_{0} = H\) and\N\(H_{i} = \operatorname{Dep}(H_{i-1})\). The dependence closure of \(H\) is defined to be the subgroup\N\(\hat{\operatorname{Dep}}(H) =\bigcup _{i\geq 0}H_{i}\).\N\NThe question is: When this ascending sequence stabilizes after finitely many steps? In this case the smallest index \(j\) such that \(H_{j} = \hat{\operatorname{Dep}}(H)\) is called the dependence length of \(H\) and denoted by \(\operatorname{depl}(H)\).\N\NProposition 7.3. Let \(H\) be a finitely generated subgroup of \( F(A)\) and let \(n\) be the total length of the given generators of \(H\). Then\N\N(i) \(\operatorname{depl}(H)\leq n\) and it is computable;\N\N(ii) \(\operatorname{rk}(\hat{\operatorname{Dep}}(H))\leq \operatorname{rk}(H)\) and one can effectively compute a basis for \(\hat{\operatorname{Dep}}(H)\) in \(O(n^{4} \log^{\ast}(n))\)\Ntime.\N\NIn Section 6, classes of subgroups of a free group which are\Npreserved under the dependence operator are developed. See Propositions 6.1, 6.3, 6.4 in the paper.\N\NThe paper concludes with some interesting open problems. One of them is answered by \textit{B. Steinberg} [``Stable finiteness of ample groupoid algebras, traces and applications'', Preprint, \url{arXiv:2207.11194}].