back to
list of publications. back to
list of publications.
back to
list of publications.
back to
list of publications.
back to
list of publications.
back to
list of publications.
back to
list of publications.
back to
list of publications.
back to
list of publications.
back to
list of publications.
back to
list of publications.
back to
list of publications.
back to
list of publications.
back to
list of publications.
back to
list of publications.
back to
list of publications.
back to
list of publications.
back to
list of publications.
In this article, we solve the twisted conjugacy problem for solvable Baumslag--Solitar groups $BS(n,1)$, i.e., we propose an algorithm which, given two elements $u,v \in BS(n,1)$ and an automorphism $\varphi \in \Aut(BS(n,1))$, decides whether $v=(w\varphi)^{-1} u w$ for some $w\in BS(n,1)$. Also, we prove Orbit Decidability for the full automorphism group $\Aut(BS(n,1))$ --- given two words on the generators $u,v\in F(X)$, decide whether the corresponding elements $u,v\in G$ can be mapped to each other by some automorphism in $\Aut(BS(n,1))$--- as well as for cyclic subgroups of $\Out(BS(n,1))$. As a direct consequence, we obtain a solution to the conjugacy problem for certain semidirect products of $BS(n,1)$ by torsion-free hyperbolic groups.
back to
list of publications.
We solve the Multiple endo-Twisted Conjugacy Problem for finitely generated free groups. We also propose a natural generalization of this problem, which is related to the Equalizer Problem.
back to
list of publications.
Maximal binary sequences generated by LFSR circuits can be used to label single-tracked absolute shaft encoders. The number of detectors required to build such encoder is called the combinatorial complexity of the sequence. For a maximal sequence, this is equal to the size to the LFSR. In order to build encoders of arbitrary resolution, this approach has been generalized to non-maximal sequences. A method to obtain sequences of this type with low combinatorial complexity is developed and evaluated in this paper. The error-correcting power of codes obtained from these sequences is also studied.
back to
list of publications.
Let $F$ be a finitely generated free group, and $K\leqslant F$ be a finitely generated, infinite index subgroup of $F$. We show that generically many finitely generated subgroups $H\leqslant F$ have trivial intersection with all conjugates of $K$, thus proving a stronger, generic form of the Hanna Neumann Conjecture. As an application, we show that the equalizer of two free group homomorphisms is generically trivial, which implies that the Post Correspondence Problem is generically solvable in free groups.
back to
list of publications.
An algorithm is constructed that, when given an explicit presentation of a finitely generated nilpotent group $G$, decides for any pair of endomorphisms $\phi, \psi\colon G\to G$ and any pair of elements $u,v\in G$, whether or not the equation $(x\phi)u=v(x\psi)$ has a solution $x\in G$. Thus it is shown that the problem of the title is decidable. Also, we present an algorithm that produces a finite set of generators of the subgroup (equalizer) $Eq_{\phi, \psi}(G)\leq G$ of all elements $u\in G$ such that $u\phi=u\psi$.
back to
list of publications.
We show that among the endomorphisms of the free (non-abelian) group $F_r$ of rank $r$, the set of monomorphisms (the injective endomorphisms) has density one. This contrasts with the known fact that the set of automorphisms has density zero. We show more generally that in the set of homomorphisms from one free group to another (both of rank bigger than one and finite), the set of monomorphisms has density one whereas the set of epimorphisms has density zero.
back to
list of publications.
We introduce the new notion of quotient-saturation as a measure of the immensity of the quotient structure of a group. We present a sufficient condition for a finitely presented group to be quotient-saturated, and use it to deduce that non-elementary finitely presented subgroups of a hyperbolic group (in particular, non-elementary hyperbolic groups themselves) are quotient-saturated. Finally, we elaborate on the previous results to extend the scope of this property to finitely presented acylindrically hyperbolic groups.
back to
list of publications.
In this paper, we explore the behaviour of the fixed subgroups of endomorphisms of free-abelian times free (FATF) groups. We exhibit an algorithm which, given a finitely generated subgroup $H$ of a FATF group $G$, decides whether $H$ is the fixed subgroup of some (finite) family of endomorphisms of $G$ and, in the affirmative case, it finds such a family. The algorithm combines both combinatorial and algebraic methods.
back to
list of publications.
We study the transference through finite index extensions of the notion of equational coherence, as well as its effective counterpart. We deduce an explicit algorithm for solving the following algorithmic problem about size two integral invertible matrices: “given $g; h_1, \ldots , h_s\in PSL_2(Z)$, decide whether $g$ is algebraic over the subgroup $H = \langle h_1,\ldots , h_s\rangle \leqslant PSL2(Z)$ (i.e., whether there exist a non-trivial $H$-equation $w(x)\in H*\langle x\rangle$ such that $w(g) = 1$) and, in the affirmative case, compute finitely many such $H$-equations $w_1(x),\ldots ,w_p(x)\in H*\langle x\rangle$ further satisfying that any $w(x)\in H*\langle x\rangle$ with $w(g) = 1$ is a product of conjugates of $w_1(x),\ldots , w_p(x)$”.
back to
list of publications.
This text is a presentation of the theory of Stallings automata and its applications to the study of subgroups of free groups. We start with the foundations on free groups and graphs/automata, and then proceed to the development of the theory, including detailed arguments and proofs. In the second part, we focus on applications to the lattice of subgroups of free groups, with special accent on the algorithmic aspects. In particular, we cover in detail the membership problem (including explicit rewriting in the given generators), the intersection problem, the finite index problem, and the study of extensions among free groups.
back to
list of publications.
Given a finitely generated subgroup $H$ of a free group $F$, we present an algorithm which computes $g_1,\ldots,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\leqslant F$ and an element $g\in F$, computes a minimal finite set of elements of $H*\gen{x}$ that generate (as a normal subgroup) the ``ideal" $I_H(g) \unlhd H*\gen{x}$ of all ``polynomials" $w(x)$, such that $w(g)=1$. The algorithms, as well as the proofs, are based on the graph-theory 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.
back to
list of publications.
We study the average case complexity of the membership problem for subgroups of free groups, and we show that it is orders of magnitude smaller than the worst case complexity of the best known algorithms. This applies to subgroups given by a fixed number of generators as well as to subgroups given by an exponential number of generators. The main idea behind this result is to exploit a generic property of tuples of words, called the central tree property. An application is given to the average case complexity of the relative primitivity problem, using Shpilrain's recent algorithm to decide primitivity, whose average case complexity is a constant depending only on the rank of the ambient free group.
back to
list of publications.
In the present paper, we analyze closer the non-Howsonicity of the family of free times free-abelian groups $F_n \times Z^m$. On one hand, we give an algorithm to decide, given $k>2$ finitely generated subgroups $H_1, \ldots ,H_k \leq F_n \times Z^m$, whether the intersection $H_1 \cap \cdots \cap H_k$ is again finitely generated and, in the affirmative case, compute a basis for it. On the second hand, we show that any $k$-intersection configuration is realizable in $F_n \times Z^m$, for $n=2$ and $m$ big enough.
back to
list of publications.
In this paper, we consider a natural generalization of the concept of order of an element in a group: an element $g\in G$ is said to have order $k$ in a subgroup $H$ of $G$ (resp., w.r.t. a coset $Hu$) if $k$ is the first strictly positive integer such that $g^k\in H$ (resp., $g^k\in Hu$). 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 (i.e., the set of elements of a given order) w.r.t. 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.
back to
list of publications.
In the present paper, we revisit some of the foundamental properties of the free group, and we present a detailed exposure of the theory of Stallings automata, a geometric interpretation of their subgroups, which has been (and continues to be) very fruitful both, as a way to understand better some classical results, and as an inspiration to prove new ones. We explain some of the most relevant ones.
back to
list of publications.
This survey is intended to be a fast (and reasonably updated) reference for the theory of Stallings automata and its applications to the study of subgroups of the free group, with the main accent on algorithmic aspects. Consequently, results concerning finitely generated subgroups have greater prominence in the paper. However, when possible, we try to state the results with more generality, including the usually overlooked non-(finitely-generated) case.
back to
list of publications.
We extend the classical Stallings theory (describing subgroups of free groups as automata) to direct products of free and abelian groups: after introducing enriched automata (i.e., automata with extra abelian labels), we obtain an explicit bijection between subgroups and a certain type of such enriched automata, which — as ithappens in the free group — is computable in the finitely generated case.This approach provides a neat geometric description of (even non finitely generated) intersections of finitely generated subgroups within this non-Howson family. In particular, we give a geometric solution to the subgroup intersection problem and the finite index problem, providing recursive bases and transversals respectively.
back to
list of publications.
The `degree of $k$-step nilpotence' of a finite group $G$ is the proportion of the tuples $(x_1,\ldots,x_{k+1})\in G^{k+1}$ for which the simple commutator $[x_1,\ldots,x_{k+1}]$ is equal to the identity. In this paper we study versions of this for an infinite group $G$, with the degree of nilpotence defined by sampling $G$ in various natural ways, such as with a random walk, or with a Folner sequence if $G$ is amenable. In our first main result we show that if $G$ is finitely generated then the degree of $k$-step nilpotence is positive if and only if $G$ is virtually $k$-step nilpotent. This generalises both an earlier result of the second author treating the case $k=1$ and a result of Shalev for finite groups, and uses techniques from both of these earlier results. We also show, using the notion of polynomial mappings of groups developed by Leibman and others, that to a large extent the degree of nilpotence does not depend on the method of sampling. As part of our argument we generalise a result of Leibman by showing that if $\varphi$ is a polynomial mapping into a torsion-free nilpotent group then the set of roots of $\varphi$ is sparse in a certain sense. In our second main result we consider the case where $G$ is residually finite but not necessarily finitely generated. Here we show that if the degree of $k$-step nilpotence of the finite quotients of $G$ is uniformly bounded from below then $G$ is virtually $k$-step nilpotent, answering a question of Shalev. As part of our proof we show that degree of nilpotence of finite groups is sub-multiplicative with respect to quotients, generalising a result of Gallagher.
back to
list of publications.
An extension of subgroups $H\leqslant K\leqslant F_A$ of the free group of rank $|A|=r\geqslant 2$ is called onto when, for every ambient free basis $A'$, the Stallings graph $\Gamma_{A'}(K)$ is a quotient of $\Gamma_{A'}(H)$. Algebraic extensions are onto and the converse implication was conjectured by Miasnikov--Ventura--Weil, and resolved in the negative, first by Parzanchevski--Puder for rank $r=2$, and recently by Kolodner for general rank. In this note we study properties of this new type of extension among free groups (as well as the fully onto variant), and investigate their corresponding closure operators. Interestingly, the natural attempt for a dual notion --into extensions-- becomes trivial, making a Takahasi type theorem not possible in this setting.
back to
list of publications.
We introduce the concepts of degree of inertia, $di_G(H)$, and degree of compression, $dc_G(H)$, of a finitely generated subgroup $H$ of a given group $G$. For the case of direct products of free-abelian and free groups, we compute the degree of compression and give an upper bound for the degree of inertia. Imposing some technical assumptions to the supremum involved in the definition of degree of inertia, we introduce the notion called restricted degree of inertia, $di'_G(H)$, and, again for the case $Z^m \times F_n$, we provide an explicit formula relating it to the restricted degree of inertia of its projection to the free part, $di'_{F_n}(H\pi)$.
back to
list of publications.
The classical result by Dyer–Scott about fixed subgroups of finite order automorphisms of $F_n$ being free factors of $F_n$ is no longer true in $Z^m \times F_n$. Within this more general context, we prove a relaxed version in the spirit of Bestvina–Handel Theorem: the rank of fixed subgroups of finite order automorphisms is uniformly bounded in terms of $m, n$. We also study periodic points of endomorphisms of $Z^m \times F_n$, and give an algorithm to compute auto-fixed closures of finitely generated subgroups of $Z^m \times F_n$. On the way, we prove the analog of Day’s Theorem for real elements in $Z^m \times F_n$, contributing a modest step into the project of doing so for any right angled Artin group (as McCool did with respect to Whitehead’s Theorem in the free context).
back to
list of publications.
We give an explicit characterization of which direct products $G$ of surface groups of Euclidean type satisfy that the fixed subgroup of any automorphism (or endomorphism) of $G$ is compressed, and of which is it always inert.
back to
list of publications.
We solve the subgroup intersection problem (SIP) for any RAAG $G$ of Droms type (i.e., with defining graph not containing induced squares or paths of length 3): there is an algorithm which, given finite sets of generators for two subgroups $H,K\leq G$, decides whether $H\cap K$ is finitely generated or not, and, in the affirmative case, it computes a set of generators for $H\cap K$. Taking advantage of the recursive characterization of Droms groups, the proof consists in separately showing that the solvability of SIP passes through free products, and through direct products with free-abelian groups. We note that most of RAAGs are not Howson, and many (e.g., $F_2\times F_2$) even have unsolvable SIP.
back to
list of publications.
We see that one cannot algorithmically decide whether a finitely presented Z-extension admits a finitely generated base group, and we use this fact to prove the undecidability of the BNS invariant. Furthermore, we show the equivalence between the isomorphism problem within the subclass of unique Z-extensions, and the semi-conjugacy problem for deranged outer automorphisms.
back to
list of publications.
We prove that, in a finitely generated residually finite group of subexponential growth, the proportion of commuting pairs is positive if and only if the group is virtually abelian. In particular, this covers the case where the group has polynomial growth (i.e., virtually nilpotent groups, where the hypothesis of residual finiteness is always satisfied). We also show that, for non-elementary hyperbolic groups, the proportion of commuting pairs is always zero.
back to
list of publications.
This volume presents the lecture notes from the authors’ three summer courses offered during the program “Automorphisms of Free Groups: Geometry, Topology, and Dynamics,” held at the Centre de Recerca Matemàtica (CRM) in Bellaterra, Catalonia.
The first two chapters present the basic tools needed, from formal language theory (regular and context-free languages, automata, rewriting systems, transducers, etc) and emphasize their connections to group theory, mostly relating to free and virtually-free groups. The material covered is sufficient to present full proofs of many of the existing interesting characterizations of virtually-free groups. In turn, the last chapter comprehensively describes Bonahon’s construction of Thurston’s compactification of Teichmüller space in terms of geodesic currents on surfaces. It also includes several intriguing extensions of the notion of geodesic current to various other, more general settings.
back to
list of publications.
We solve the twisted conjugacy problem on Thompson's group $F$. We also exhibit orbit undecidable subgroups of $Aut(F)$, and give a proof that $Aut(F)$ and $Aut^+(F)$ are orbit decidable provided a certain conjecture on Thompson's group is true. By using general criteria introduced by Bogopolski, Martino and Ventura, we construct a family of free extensions of $F$ where the conjugacy problem is unsolvable. As a byproduct of our techniques, we give a new proof of a result of Bleak-Fel'shtyn-Gonçalves showing that $F$ has property $R_{\infty}$, and which can be extended to show that Thompson's group $T$ also has property $R_{\infty}$.
back to
list of publications.
Two complexity functions $\alpha_r$ and $\beta_r$ are defined to measure the maximal possible gap between the norm of an automorphism (respectively outer automorphism) of $F_r$ and the norm of its inverse. The exact complexity of $\alpha_2$ and $\beta_2$ is computed. For rank $r\geq 3$, polynomial lower bounds are provided for $\alpha_r$ and $\beta_r$, and the existence of a polynomial upper bound is proved for $\beta_r$.
back to
list of publications.
The Stallings construction for finitely generated subgroups of free groups is generalized by introducing the concept of Stallings section, which allows an efficient computation of the core of a Schreier graph based on edge folding. It is proved that those groups admitting Stallings sections are precisely finitely generated virtually free groups, through a constructive approach based on Basse-Serre theory. Complexity issues and applications are also discussed.
back to
list of publications.
For a compact surface $\Sigma$ (orientable or not, and with boundary or not) we show that the fixed subgroup, $Fix B$, of any family $B$ of endomorphisms of $\pi_1(\Sigma)$ is compressed in $\Sigma$ i.e., $rk(Fix B)\leq rk(H)$ for any subgroup $Fix B \leq H \leq \pi_1(\Sigma)$. On the way, we give a partial positive solution to the inertia conjecture, both for free and for surface groups. We also investigate direct products, $G$, of finitely many free and surface groups, and give a characterization of when $G$ satisfies that $rk(Fix \phi) \leq rk(G)$ for every $\phi \in Aut(G)$.
back to
list of publications.
Available: Paper PDF.A recent collection of papers in the last years have given a renovated interest to the notion of orbit decidability. This is a new quite general algorithmic notion, connecting with several classical results, and closely related to the study of the conjugacy problem for extensions of groups. In the present survey we explain several of the classical results closely related to this concept, and we explain the main ideas behind the connection with the conjugacy problem made by Bogopolski-Martino-Ventura in a recent paper. All the consequences up to date, published in several other papers by other authors, are also commented and reviewed.
back to
list of publications.
In this first volume of the new subseries Research Perspectives CRM Barcelona published by Birkhäuser inside the series Trends in Mathematics, we present seventeen Extended Abstracts corresponding to selected talks given by participants at the CRM Research Programme "Automorphisms of Free Groups: Algorithms, Geometry and Dynamics", coordinated by Juan González-Meneses, Martin Lustig, Alexandra Pettet and Enric Ventura. More than half of them came from the Conference on Automorphisms of Free Groups (held from November 12th to 16th, 2012) and the rest came from talks given at the workshops or the weekly seminar held along the Fall of 2012. We hope that the presentation of this material under the present Extended Abstract form will help authors spread their recent research. Most of the short articles in this volume contain preliminary presentations of new results not yet published in regular research journals.
back to
list of publications.
The notion of Orbit Decidability is reviewed and put in context; and a recent result by Bogopolski-Martino-Ventura is recalled and related to the conjugacy problem. Some recent applications of this result are reviewed, and an interesting variation of the concept of Orbit Decidability is stablished.
back to
list of publications.
In this note we solve the twisted conjugacy problem for braid groups, i.e. we propose an algorithm which, given two braids $u,v\in B_n$ and an automorphism $\varphi \in Aut (B_n)$, decides whether $v=(\varphi (x))^{-1}ux$ for some $x\in B_n$. As a corollary, we deduce that each group of the form $B_n \rtimes H$, a semidirect product of the braid group $B_n$ by a torsion-free hyperbolic group $H$, has solvable conjugacy problem.
back to
list of publications.
We study direct products of free-abelian and free groups with special emphasis on algorithmic problems. After giving natural extensions of standard notions into that family, we find an explicit expression for an arbitrary endomorphism of $\ZZ^m \times F_n$. These tools are used to solve several algorithmic and decision problems for $\ZZ^m \times F_n $: the membership problem, the isomorphism problem, the finite index problem, the subgroup and coset intersection problems, the fixed point problem, and the Whitehead problem.
back to
list of publications.
The usual way to investigate the statistical properties of finitely generated subgroups of free groups, and of finite presentations of groups, is based on the so-called word-based distribution: subgroups are generated (finite presentations are determined) by randomly chosen k-tuples of reduced words, whose maximal length is allowed to tend to infinity. In this paper we adopt a different, though equally natural, point of view: we investigate the statistical properties of the same objects, but with respect to the so-called graph-based distribution, recently introduced by Bassino, Nicaud and Weil. Here, subgroups (and finite presentations) are determined by randomly chosen Stallings graphs whose number of vertices tends to infinity. Our results show that these two distributions behave quite differently from each other, shedding a new light on which properties of finitely generated subgroups can be considered frequent or rare. For example, we show that malnormal subgroups of a free group are negligible in the graph-based distribution, while they are exponentially generic in the word-based distribution. Quite surprisingly, a random finite presentation generically presents the trivial group in this new distribution, while in the classical one it is known to generically present an infinite hyperbolic group.
back to
list of publications.
The Whitehead problem is solved in the class of toral relatively hyperbolic groups (i.e. torsion-free relatively hyperbolic groups with abelian parabolic subgroups): there is an algorithm which, given two finite tuples $(u_1, \ldots ,u_n)$ and $(v_1, \ldots ,v_n)$ of elements of $G$, decides whether there is an automorphism of $G$ taking $u_i$ to $v_i$ for all $i$.
back to
list of publications.
(Free-abelian)-by-free, self-similar groups generated by nite self-similar sets of tree automorphisms and having unsolvable conjugacy problem are constructed. Along the way, orbit undecidable, free subgroups of $GL_d(Z)$, for $d>5$, and $Aut(F_d)$, for $d>4$, are constructed as well.
back to
list of publications.
Let $H$ be a torsion-free $\delta$-hyperbolic group with respect to a finite generating set $S$. Let $a_1,\ldots ,a_n$ and $a_{1*},\ldots ,a_{n*}$ be elements of $H$ such that $a_{i*}$ is conjugate to $a_i$ for each $i=1,\dots ,n$. Then, there is a uniform conjugator if and only if $W(a_{1*},\ldots ,a_{n*})$ is conjugate to $W(a_1,\ldots ,a_n)$ for every word $W$ in $n$ variables and length up to a computable constant depending only on $\delta$, $\sharp{S}$ and $\sum_{i=1}^n |a_i|$.
As a corollary, we deduce that there exists a computable constant $\mathcal{C}=\mathcal{C}(\delta, \sharp S)$ such that, for any endomorphism $\varphi$ of $H$, if $\varphi(h)$ is conjugate to $h$ for every element $h\in H$ of length up to $\mathcal {C}$, then $\varphi$ is an inner automorphism. Another corollary is the following: if $H$ is a torsion-free conjugacy separable hyperbolic group, then $\text{\rm Out}(H)$ is residually finite. When particularizing the main result to the case of free groups, we obtain a solution for a mixed version of the classical Whitehead's algorithm.
back to
list of publications.
Let $F$ be a finitely generated free group. We present an algorithm such that, given a subgroup $H\leqslant F$, decides whether $H$ is the fixed subgroup of some family of automorphisms, or family of endomorphisms of $F$ and, in the affirmative case, finds such a family. The algorithm combines both combinatorial and geometric methods.
back to
list of publications.
We give an explicit recursive presentation for Mihailova's subgroup $M(H)$ of $F_n \times F_n$ corresponding to a finite, concise and Peiffer aspherical presentation $H=\langle x_1, \ldots ,x_n \mid R_1, \ldots ,R_m \rangle$. This partially answers a question of R.I. Grigorchuk, [8, Problem 4.14]. As a corollary, we construct a finitely generated recursively presented orbit undecidable subgroup of $Aut(F_3)$.
back to
list of publications.
This is a joint proceedings volume for two international conferences. The first one “Combinatorial and Geometric Group Theory with Applications” (GAGTA), was held at the University of Dortmund (Germany) from August 27th to 31st, 2007. The second one, “Fields Workshop in Asymptotic Group Theory and Cryptography”, Carleton University (Ottawa, Canada) was held from December 14th to 16th, 2007, followed by “Workshop on Actions on Trees, Non-Archimedian Words, and Asymptotic Cones”, Saint Sauveur (Montreal) from December 17th to 21st, 2007. This volume contains a selection of fourteen refereed articles highlighting several active areas of research in Geometric and Combinatorial Group Theory. The contents is the following: 1- O. Bogopolski and R. Vikentiev, "Subgroups of Small Index in $Aut(F_n)$ and Kazhdan’s Property (T)"; 2- P. Brinkmann, "Dynamics of Free Group Automorphisms"; 3- V. Diekert, A.J. Duncan and A.G. Myasnikov, "Geodesic Rewriting Systems and Pregroups"; 4- E. Frenkel, A.G. Myasnikov and V.N. Remeslennikov, "Regular Sets and Counting in Free Groups"; 5- D. Gonçalves and P. Wong, "Twisted Conjugacy for Virtually Cyclic Groups and Crystallographic Groups"; 6- M. Hock and B. Tsaban, "Solving Random Equations in Garside Groups Using Length Functions"; 7- A. Juhász, "An Application of Word Combinatorics to Decision Problems in Group Theory"; 8- O. Kharlampovich and A.G. Myasnikov, "Equations and Fully Residually Free Groups"; 9- M. Lustig, "The $F_n$-action on the Product of the Two Limit Trees for an Iwip Automorphism"; 10- F. Matucci, "Mather Invariants in Groups of Piecewise-linear Homeomorphisms"; 11- P.V. Morar and A.N. Shevlyakov, "Algebraic Geometry over the Additive Monoid of Natural Numbers: Systems of Coefficient Free Equations"; 12- D. Savchuk, "Some Graphs Related to Thompson’s Group $F$"; 13- R. Weidmann, "Generating Tuples of Virtually Free Groups"; 14- R. Zarzycki, "Limits of Thompson’s Group $F$".
back to
list of publications.
Let $F_n$ be a free group of finite rank $n$. Due to Kapovich-Levitt-Schupp-Shpilrain, two finitely generated subgroups $H$ and $K$ of $F_n$ are said to be volume equivalent in $F_n$ if, for every free and discrete isometric action of $F_n$ on an $\mathbb{R}$-tree $X$, we have $vol_X (H) = vol_X (K)$. We give a more algebraic and combinatorial characterization of volume equivalence and discuss a counterexample of volume equivalence in order to justify our characterization. We also provide a specific example of volume equivalence which shows that volume equivalence does not necessarily imply rank equivalence.
back to
list of publications.
Given a short exact sequence of groups with certain conditions, $1\to F\to G\to H\to 1$, we prove that $G$ has solvable conjugacy problem if and only if the corresponding action subgroup $A\leq Aut(F)$ is orbit decidable. Via Brinkmann’s theorem, this provides a proof of the recent result that free-by-cyclic groups have solvable conjugacy problem. Several examples of free-by-free and free abelian-by-free groups with solvable conjugacy problem are also given. On the way, the twisted conjugacy problem is solved for (virtually) surface groups, and polycyclic groups. As an application, an alternative solution to the conjugacy problem for the automorphism group of the free group of rank 2 is given. On the negative side, we give an example of a group with solvable conjugacy problem but unsolvable twisted conjugacy problem. And we construct the first known example of a $\mathbb{Z}^4$-by-free group with unsolvable conjugacy problem. Also, an alternative proof for the unsolvability of the conjugacy problem in Miller’s free-by-free groups is provided.
back to
list of publications.
Let $M$ be a finitely generated metabelian group explicitly presented in the variety $A^2$ of all metabelian groups. An algorithm is constructed which, for every endomorphism $\varphi \in End(M)$ identical modulo an abelian normal subgroup $N$ containing the derived subgroup $M'$, and for any pair of elements $u, v\in M$, decides if the equation $(x\varphi )u = vx$ has a solution in $M$. Thus, it is shown that the title problem under the assumptions made is algorithmically decidable. Moreover, the twisted conjugacy problem in any polycyclic metabelian group $M$ is decidable for an arbitrary endomorphism $\varphi \in End(M)$.
back to
list of publications.
While Dehn functions, $D(n)$, of finitely presented groups are very well studied in the literature, mean Dehn functions are much less considered. M. Gromov introduced the notion of mean Dehn function of a group, $D_{mean}(n)$, suggesting that in many cases it should grow much more slowly than the Dehn function itself. Using only elementary counting methods, this paper presents some computations pointing into this direction. Particularizing them to the case of any finite presentation of a finitely generated abelian group (for which it is well known that $D(n)\sim n^2$ except in the 1-dimensionlal case), we show that the three variations $D_{osmean}(n)$, $D_{smean}(n)$ and $D_{mean}(n)$ all are bounded above by $Kn(\ln n)^2$, where the constant $K$ depends only on the presentation (and the geodesic combing) chosen. This improves an earlier bound given by Kukina and Roman'kov.
back to
list of publications.
Maximal-length binary sequences have been known for a long time. They have many interesting properties, one of them being that, when taken in blocks of $n$ consecutive positions, they form $2^n-1$ different codes in a closed circular sequence. This property can be used for measuring absolute angular positions as the circle can be divided in as many parts as different codes can be retrieved. This paper describes how can a closed binary sequence with arbitrary length be effectively designed with the minimal possible block-length, using linear feedback shift registers (LFSR). Such sequences can be used for measuring a specified exact number of angular positions, using the minimal possible number of sensors that linear methods allow.
back to
list of publications.
The Whitehead minimization problem consists in finding a minimum size element in the automorphic orbit of a word, a cyclic word or a finitely generated subgroup in a finite rank free group. We give the first fully polynomial algorithm to solve this problem, that is, an algorithm that is polynomial both in the length of the input word and in the rank of the free group. Earlier (classical) algorithms had an exponential dependency in the rank of the free group. It follows that the primitivity problem (to decide whether a word is an element of some basis of the free group) and the free factor problem can also be solved in polynomial time.
back to
list of publications.
This is a joint proceedings volume for two international conferences. The first one, “Asymptotic and Probabilistic Methods in Geometric Group Theory”, was held at the University of Geneva (Switzerland) from June 20th to 25th, 2005. The second one, “Barcelona Conference on Geometric Group Theory”, was held at the Centre de Recerca Matemàtica in Barcelona (Catalonia) from June 28th to July 2nd, 2005. This volume contains a selection of twelve refereed articles highlighting several active areas of research in Geometric and Combinatorial Group Theory. The contents is the following: 1- U. Baumgartner, "Totally Disconnected, Locally Compact Groups as Geometric Objects. A survey of work in progress"; 2- J. Burillo, S. Cleary and B. Wiest, "Computational Explorations in Thompson’s Group F"; 3- T. Ceccherini-Silberstein and M. Coornaert, "On the Surjunctivity of Artinian Linear Cellular Automata over Residually Finite Groups"; 4- Y. de Cornulier and A. Mann, "Some Residually Finite Groups Satisfying Laws"; 5- R.J. Flores, "Classifying Spaces for Wallpaper Groups"; 6- V. Guirardel and G. Levitt, "A General Construction of JSJ Decompositions"; 7- Y. de Cornulier and P. de la Harpe, "Décompositions de Groupes par Produit Direct et Groupes de Coxeter"; 8- A. Ould Houcine, "Limit Groups of Equationally Noetherian Groups"; 9- A. Juhász, "Solution of the Conjugacy Problem and Malnormality of Subgroups in Certain Relative Small Cancellation Group Presentations"; 10- A. Juhász, "Solution of the Membership Problem for Magnus Subgroups in Certain One-Relator Free Products"; 11- M. Lustig, "Conjugacy and Centralizers for Iwip Automorphisms of Free Groups"; and 12- A. Miasnikov, E. Ventura and P. Weil, "Algebraic Extensions in Free Groups".
back to
list of publications.
Let $\phi$ be an automorphism of a free group $F_n$ of rank n, and let $M_{\phi}=F_n \rtimes_{\phi} \mathbb{Z}$ be the corresponding mapping torus of $\phi$. We study the group $Out(M_{\phi})$ under certain technical conditions on $\phi$. Moreover, in the case of rank 2, we classify the cases when this group is finite or virtually cyclic, depending on the conjugacy class of the image of $\phi$ in $GL_2(\mathbb{Z})$.
back to
list of publications.
In this paper we show that the conjugacy problem is solvable in [finitely generated free]-by-cyclic groups, by using a result of O. Maslakova that one can algorithmically find generating sets for the fixed subgroups of free group automorphisms, and one of P. Brinkmann that one can determine whether two cyclic words in a free group are mapped to each other by some power of a given automorphism. The algorithm effectively computes a conjugating element, if it exists. We also solve the power conjugacy problem and give an algorithm to recognize if two given elements of a finitely generated free group are Reidemeister equivalent with respect to a given automorphism.
back to
list of publications.
This volume presents articles by speakers and participants in two AMS special sessions, Geometric Group Theory and Geometric Methods in Group Theory, held respectively at Northeastern University (Boston, MA) and at Universidad de Sevilla (Spain). The expository and survey articles in the book cover a wide range of topics, making it suitable for researchers and graduate students interested in group theory. The contents is the following: M. Cárdenas and F. F. Lasheras, "Properly 3-realizable groups: a survey"; A. Martino and S. O Rourke, "Free actions on $\mathbb{Z}^n$-trees: a survey"; G. Levitt, "Characterizing rigid simplicial actions on trees"; J. González-Meneses, "Improving an algorithm to solve multiple simultaneous conjugacy problems in braid groups"; E. Godelle and L. Paris, "On singular Artin monoids"; O. Bogopolski, "A surface groups analogue of a theorem of Magnus"; V. Addepalli and E. C. Turner, "Shift automorphisms of finite order"; V. Shpilrain, "Counting primitive elements of a free group"; R. Weidmann, "A rank formula for amalgamated products with finite amalgam"; D. Kahrobaei, "A simple proof of a theorem of Karrass and Solitar"; S. W. Margolis, J. Meakin, and Z. Sunik, "Distortion functions and the membership problem for submonoids of groups and monoids"; J. Belk and K.-U. Bux, "Thompson's group $F$ is maximally nonconvex"; S. Cleary and J. Taback, "Seesaw words in Thompson's group $F$"; X. Martin, "Piecewise-projective representation of Thompson's group $T$"; T. Dymarz, "Bijective quasi-isometries of amenable groups"; I. Bumagin, "On definitions of relatively hyperbolic groups"; G. Baumslag, "Embedding wreath-like products in finitely presented groups"; I S. Cleary and J. Taback, "Metric properties of the lamplighter group as an automata group F"; Dahmani, "An example of non-contracting weakly branch automaton group"; and A. Akhmedov, "Travelling salesman problem in groups".
back to
list of publications.
For any finitely generated group $G$ an invariant $\fol G \geq 0$ is introduced which measures the ``amount of non-amenability'' of $G$. If $G$ is amenable, then $\fol G = 0$. If $\fol G > 0$, we call $G$ {\em uniformly non-amenable}. We study the basic properties of this invariant; for example, its behavior when passing to subgroups and quotients of $G$. We prove that the following classes of groups are uniformly non-amenable: non-abelian free groups, non-elementary word-hyperbolic groups, large groups, free Burnside groups of large enough odd exponent, and groups acting acylindrically on a tree. Uniform non-amenability implies uniform exponential growth. We also exhibit a family of non-amenable groups (in particular including all non-solvable Baumslag-Solitar groups) which are not uniformly non-amenable, that is, they satisfy $\fol G=0$. Finally, we derive a relation between our uniform F\o lner constant and the uniform Kazhdan constant with respect to the left regular representation of $G$.
back to
list of publications.
In this paper we prove that the fixed subgroup of an arbitrary family of endomorphisms $\psi_i$, $i\in I$, of a finitely generated free group $F$, is $F$-super-compressed. In particular, $r(\cap_{i\in I} \fix{\psi_i})\leq r(M)$ for every subgroup $M\leq F$ containing $\cap_{i\in I} \fix{\psi_i}$. This provides new evidence towards the inertia conjecture for fixed subgroups of free groups. As a corollary, we show that, in the free group of rank $n$, every strictly ascending chain of fixed subgroups has length at most $2n$.
back to
list of publications.
Let $F$ be a finitely generated free group. By using Bestvina-Handel theory, as well as some further improvements, the eigengroups of a given automorphism of $F$ (and its fixed subgroup among them) are globally analyzed and described. In particular, an explicit description of all subgroups of $F$ which occur as the fixed subgroup of some automorphism is given.
back to
list of publications.
Let $n$ be an arbitrary cardinal, and let $F_n$ be a free group of rank $n$. The \emph{fixed subgroup} of an endomorphism $\psi$ of $F_n$ is the subgroup of elements in $F_n$ fixed by $\psi$. In this paper, the relationship between the family of fixed subgroups of endomorphisms of $F_n$ and the family of fixed subgroups of automorphisms of $F_n$ will be studied. We prove that these two families of subgroups do not coincide for $n\geq 3$, by showing an infinite sequence of explicit examples of retracts of $F_n$ --and so, fixed subgroups of endomorphisms of $F_n$-- which are not fixed subgroups of any automorphism of $F_n$.
back to
list of publications.
This note is a survey of the main results known about fixed subgroups of endomorphisms of finitely generated free groups. A historic point of view is taken, emphasizing the evolution of this line of research, from its beginning to the present time. The article concludes with a section containing the main open problems and conjectures, with some comments and discussions on them.
back to
list of publications.
In this paper it is proved that the set of primitive elements of a nonabelian free group has density zero, i.e. the ratio of primitive elements in increasingly large balls is arbitrarily small. Two notions of density (natural and exponential density) are defined and some of their properties are studied. A class of subsets of the free group (the graphical sets) is defined restricting the occurrence of adjacent letters in the reduced word for an element, and the relation between graphical sets and the set of primitive elements is studied and used to prove the above result.
back to
list of publications.
Let $F$ be a finitely generated free group, and let $n$ denote its rank. A subgroup $H$ of $F$ is said to be {\it automorphism-fixed}, or {\it auto-fixed} for short, if there exists a set $S$ of automorphisms of $F$ such that $H$ is precisely the set of elements fixed by every element of $S$; similarly, $H$ is {\it 1-auto-fixed} if there exists a single automorphism of $F$ whose set of fixed elements is precisely $H$. We show that each auto-fixed subgroup of $F$ is a free factor of a 1-auto-fixed subgroup of $F$. We show also that if (and only if) $n\ge 3$, then there exist free factors of 1-auto-fixed subgroups of $F$ which are not auto-fixed subgroups of $F$. A 1-auto-fixed subgroup $H$ of $F$ has rank at most $n$, by the Bestvina-Handel Theorem, and if $H$ has rank exactly $n$, then $H$ is said to be a {\it maximum-rank} 1-auto-fixed subgroup of $F$, and similarly for auto-fixed subgroups. Hence a maximum-rank auto-fixed subgroup of $F$ is a (maximum-rank) 1-auto-fixed subgroup of $F$. We further prove that if $H$ is a maximum-rank 1-auto-fixed subgroup of $F$, then the group of automorphisms of $F$ which fix every element of $H$ is free abelian of rank at most $n-1$. All of our results apply also to endomorphisms.
back to
list of publications.
We show that, in the free group $F$ of rank $n$, $n$ is the maximal length of strictly ascending chains of maximal rank fixed subgroups, that is, rank $n$ subgroups of the form Fix$\, \phi$ for some $\phi \in Aut(F)$. We further show that, in the rank two case, if the intersection of an arbitrary family of proper maximal rank fixed subgroups has rank two then all those subgroups are equal. In particular, every $G\leq Aut(F)$ with $r($Fix$\, G)=2$ is either trivial or infinite cyclic.
back to
list of publications.
In proving the conjecture of Scott that the rank of the fixed group of an automorphism of a finitely generated free group $F$ is at most the rank of $F$, Bestvina and Handel use a hierarchy for the set of automorphisms of finitely generated free groups and, from their point of view, the irreducible automorphisms of growth rate 1 are the simplest. It is not immediately obvious from what these automorphisms are, and our purpose here is to describe them explicitly.
back to
list of publications.
Let $F$ be a finitely generated free group, let $\phi$ be an injective endomorphism of $F$, and let $S$ be a family of injective endomorphisms of $F$. M. Bestvina and M. Handel proved that the rank of the free subgroup $\mbox{Fix}(\phi)$, which consists of the elements of $F$ fixed by $\phi$, is at most the rank of $F$. By combining their results with graph techniques of J.R. Stallings, we show that, for any subgroup $H$ of $F$, the rank of the intersection $H \cap \mbox{Fix}(\phi)$ is at most the rank of $H$. We deduce that the rank of the free subgroup $\mbox{Fix}(S)$, which consists of the elements of $F$ fixed by every element of $S$, is at most the rank of $F$. The topological proof given by Bestvina-Handel is here translated into the language of groupoids, and many details heretofore left to the reader are meticulously verified.
Available: Extended abstract PDF, Errata PDF.
back to
list of publications.
We study and compare two natural distributions of finitely generated subgroups of free groups. One is based on the random generation of tuples of reduced words; that is the one classically used by group theorists. The other relies on Stallings’ graphical representation of subgroups and in spite of its naturality, it was only recently considered. The combinatorial structures underlying both distributions are studied in this paper with methods of analytic combinatorics. We use these methods to point out the differences between these distributions. It is particularly interesting that certain important properties of subgroups that are generic in one distribution, turn out to be negligible in the other.
back to
list of publications.
Maximal-length binary shift register sequences have been known for a long time. They have many interesting properties, one of them is that when taken in blocks of $n$ consecutive positions they form $2^n-1$ different codes in a closed circular sequence. This property can be used for measuring absolute angular positions as the circle can be divided in as many parts as different codes can be retrieved. This paper describes how a closed binary sequence with arbitrary length can be effectively designed with the minimal possible block-length, using linear feedback shift registers (LFSR). Such sequences can be used for measuring a specified exact number of angular positions, using the minimal possible number of detectors allowed by linear methods.
back to
list of publications.
Let $F$ be a finitely generated free group. We present an algorithm such that, given a subgroup $H\leqslant F$, decides whether $H$ is the fixed subgroup of some family of automorphisms, or family of endomorphisms of $F$ and, in the affirmative case, finds such a family. The algorithm uses both combinatorial and geometric methods.
back to
list of publications.
The aim of this paper is to unify the points of view of three recent and independent papers (Ventura 1997, Margolis, Sapir and Weil 2001 and Kapovich and Miasnikov 2002), where similar modern versions of a 1951 theorem of Takahasi were given. We develop a theory of algebraic extensions for free groups, highlighting the analogies and differences with respect to the corresponding classical field-theoretic notions, and we discuss in detail the notion of algebraic closure. We apply that theory to the study and the computation of certain algebraic properties of subgroups (e.g., being malnormal, pure, inert or compressed, being closed in certain profinite topologies) and the corresponding closure operators. We also analyze the closure of a subgroup under the addition of solutions of certain sets of equations.
back to
list of publications.
Given an endomorphism of a finite dimensional vector space $\Bbb F^{n}_q$ over a finite field, $\varphi :\Bbb F^{n}_q \rightarrow \Bbb F^{n}_q$, we describe the dynamic structure of the function $\varphi$ (that is, the decomposition in cycles of the permutation $\varphi$, in the bijective case) in terms of the elementary divisors of the endomorphism $\varphi$.
back to
list of publications.
The class of Bézout factorial rings is introduced and characterized. Using the factorial properties of such a ring $R$, and given a $n\times m$ matrix $A$ over $R$, we find $P\in GL(n,\, R)$ and $Q\in GL(m,\, R)$ such that $PAQ$ is diagonal with every element in the diagonal dividing the following one.
back to
list of publications.
| © Enric Ventura Capell, 1999 | |
Back to main page. |