Ideals of equations for elements in a free group and Stallings folding

Abstract Let $H\le F$ be two finitely generated free groups. Given $g\in F$ , we study the ideal $\mathfrak I_g$ of equations for g with coefficients in H , i.e. the elements $w(x)\in H*\langle x\rangle$ such that $w(g)=1$ in F . The ideal $\mathfrak I_g$ is a normal subgroup of $H*\langle x\rangle$ , and it’s possible to algorithmically compute a finite normal generating set for $\mathfrak I_g$ ; we give a description of one such algorithm, based on Stallings folding operations. We provide an algorithm to find an equation in w(x)\in $\mathfrak I_g$ with minimum degree, i.e. such that its cyclic reduction contains the minimum possible number of occurrences of x and x −1 ; this answers a question of A. Rosenmann and E. Ventura. More generally, we show how to algorithmically compute the set D g of all integers d such that $\mathfrak I_g$ contains equations of degree d ; we show that D g coincides, up to a finite set, with either $\mathbb N$ or $2\mathbb N$ . Finally, we provide examples to illustrate the techniques introduced in this paper. We discuss the case where ${\text{rank}}(H)=1$ . We prove that both kinds of sets D g can actually occur. We show that the equations of minimum possible degree aren’t in general enough to generate the whole ideal $\mathfrak I_g$ as a normal subgroup.