CGC Bulletin 25
Contents
- Conference: Advances in Group Theory and Applications 2009
- Domains of proper discontinuity on the boundary of Outer space
- A linear-time algorithm to compute geodesics in solvable Baumslag-Solitar groups
- Tilings and Submonoids of Metabelian Groups
- How to read the lenght of a braid from its curve diagram
- A note on Renner monoids
- Some quadratic equations in the free group of rank 2
- Presentations of subgroups of the braid group generated by powers of band generators
- Free group automorphisms with many fixed points at infinity
- Limits of relatively hyperbolic groups and Lyndon's completions
- The Thompson-Higman monoids M_{k,i}: the J-order, the D-relation, and their complexity
- On the Baker's map and the Simplicity of the Higher Dimensional Thompson Groups nV
- On Systems of Equations over Free Products of Groups
- On endomorphisms of torsion-free hyperbolic groups
- Groups Elementarily Equivalent to a Free 2-nilpotent Group of Finite Rank
- Twisted conjugacy classes in nilpotent groups
- The Conjugacy Problem in Amalgamated Products I: Regular Elements and Black Holes
- Generic complexity of the Conjugacy Problem in HNN-extensions and algorithmic stratification of Miller's groups
- On the universal theory of torsion and lacunary hyperbolic groups
- A Magnus theorem for some one-relator groups
- Strong law of large numbers on graphs and groups with applications -- I
- Intersections of conjugates of Magnus subgroups of one-relator groups
Regards,
Boaz Tsaban
Bulletin's webpage: http://www.cs.biu.ac.il/~tsaban/CGC/cgc.html
1. Conference: Advances in Group Theory and Applications 2009
Hotel Lo Scoglio, Porto Cesareo (Lecce, ITALY): June, 8th - 12th, 2009
http://poincare.unile.it/adv2009/organiz.htm
2. Domains of proper discontinuity on the boundary of Outer space
Ilya Kapovich and Martin Lustig
Motivated by the work of McCarthy and Papadopoulos for subgroups of mapping class groups, we construct domains of proper discontinuity in the compactified Outer space and in the projectivized space of geodesic currents for any "sufficiently large" subgroup of $Out(F_N)$ (that is, a subgroup containing a hyperbolic iwip).
As a corollary we prove that for $N\ge 3$ the action of $Out(F_N)$ on the subset of $\mathbb PCurr(F_N)$ consisting of all projectivized currents with full support is properly discontinuous.
http://arxiv.org/abs/0902.4263
3. A linear-time algorithm to compute geodesics in solvable Baumslag-Solitar groups
Murray Elder
We present an algorithm to convert a word of length $n$ in the standard generators of the solvable Baumslag-Solitar group $BS(1,p)$ into a geodesic word, which runs in linear time and space in $n$ on a random access machine.
http://arxiv.org/abs/0903.0216
4. Tilings and Submonoids of Metabelian Groups
Markus Lohrey and Benjamin Steinberg
In this paper we show that membership in finitely generated submonoids is undecidable for the free metabelian group of rank 2 and for the wreath product $\mathbb Z\wr (\mathbb Z\times \mathbb Z)$. We also show that subsemimodule membership is undecidable for finite rank free $(\mathbb Z\times \mathbb Z)$-modules. The proof involves an encoding of Turing machines via tilings. We also show that rational subset membership is undecidable for two-dimensional lamplighter groups.
http://arxiv.org/abs/0903.0648
5. How to read the length of a braid from its curve diagram
Bert Wiest
We prove that the length a braid, in the sense of Garside, is equal to a winding-number type invariant of the curve diagram of the braid.
http://arxiv.org/abs/0904.0224
6. A note on Renner monoids
Eddy Godelle
We provide every Renner monoids with a monoid presentation, and we introduce a length function which extends the Coxeter length function.
http://arxiv.org/abs/0904.0926
7. Some quadratic equations in the free group of rank 2
Daciberg Goncalves, Elena Kudryavtseva, Heiner Zieschang
For a given quadratic equation with any number of unknowns in any free group F, with right-hand side an arbitrary element of F, an algorithm for solving the problem of the existence of a solution was given by Culler. The problem has been studied by the authors for parametric families of quadratic equations arising from continuous maps between closed surfaces, with certain conjugation factors as the parameters running through the group F. In particular, for a one-parameter family of quadratic equations in the free group F_2 of rank 2, corresponding to maps of absolute degree 2 between closed surfaces of Euler characteristic 0, the problem of the existence of faithful solutions has been solved in terms of the value of the self-intersection index mu: F_2 --> Z[F_2] on the conjugation parameter. The present paper investigates the existence of faithful, or non-faithful, solutions of similar families of quadratic equations corresponding to maps of absolute degree 0.
http://arxiv.org/abs/0904.1421
8. Presentations of subgroups of the braid group generated by powers of band generators
Michael L\"onne
According to the Tits conjecture proved by Crisp and Paris, [CP], the subgroups of the braid group generated by proper powers of the Artin elements are presented by the commutators of generators which are powers of commuting elements. Hence they are naturally presented as right-angled Artin groups. The case of subgroups generated by powers of the band generators is more involved. We show that the groups are right-angled Artin groups again, if all generators are proper powers with exponent at least 3. We also give a presentation in cases at the other extreme, when all generators occur with exponent 1 or 2, which is far from being that of a right-angled Artin group.
http://arxiv.org/abs/0904.1469
9. Free group automorphisms with many fixed points at infinity
Andre Jaeger, Martin Lustig
A concrete family of automorphisms alpha_n of the free group F_n is exhibited, for any n > 2, and the following properties are proved: alpha_n is irreducible with irreducible powers, has trivial fixed subgroup, and has 2n-1 attractive as well as 2n repelling fixed points at bdry F_n. As a consequence of a recent result of V Guirardel there can not be more fixed points on bdry F_n, so that this family provides the answer to a question posed by G Levitt.
http://arxiv.org/abs/0904.1533
10. Limits of relatively hyperbolic groups and Lyndon's completions
O. Kharlampovich, A. Myasnikov
In this paper we describe finitely generated groups $H$ universally equivalent (with constants from $G$ in the language) to a given torsion-free relatively hyperbolic group $G$ with free abelian parabolics. It turns out that, as in the free group case, the group $H$ embeds into the Lyndon's completion $G^{\mathbb{Z}[t]}$ of the group $G$, or, equivalently, $H$ embeds into a group obtained from $G$ by finitely many extensions of centralizers. Conversely, every subgroup of $G^{\mathbb{Z}[t]}$ containing $G$ is universally equivalent to $G$. Since finitely generated groups universally equivalent to $G$ are precisely the finitely generated groups discriminated by $G$ the result above gives a description of finitely generated groups discriminated by $G$.
http://arxiv.org/abs/0904.2423
11. The Thompson-Higman monoids M_{k,i}: the J-order, the D-relation, and their complexity
Jean-Camille Birget
The Thompson-Higman groups G_{k,i} have a natural generalization to monoids M_{k,i}, and inverse monoids Inv_{k,i}. We study some structural features of M_{k,i} and Inv_{k,i} and investigate the computational complexity of decision problems. The main interest of these monoids is their close connection with circuits and circuit complexity.
The maximal subgroups of M_{k,1} are isomorphic to the groups G_{k,j} (1 \leq j \leq k-1); so we rediscover all the Thompson-Higman groups within M_{k,1}.
The Green relations \leq_J and \equiv_D of M_{k,1} can be decided in deterministic polynomial time when the inputs are words over a finite generating set of M_{k,1}.
When a circuit-like generating set is used for M_{k,1} then deciding \leq_J is coDP-complete. The multiplier search problem for \leq_J is xNPsearch-complete, whereas the multiplier search problems of \leq_R and \leq_L are not in xNPsearch unless NP = coNP.
Deciding \equiv_D for M_{k,1} when the inputs are words over a circuit-like generating set, is \oplus_{k-1}.NP-complete. For Inv_{k,1} over a circuit-like generating set, deciding \equiv_D is \oplus_{k-1} P-complete.
http://arxiv.org/abs/0904.2479
12. On the Baker's map and the Simplicity of the Higher Dimensional Thompson Groups nV
Matthew G. Brin
We show that the baker's map is a product of transpositions (particularly pleasant involutions), and conclude from this that an existing very short proof of the simplicity of Thompson's group V applies with equal brevity to the higher dimensional Thompson groups nV.
http://arxiv.org/abs/0904.2624
13. On Systems of Equations over Free Products of Groups
Montserrat Casals-Ruiz, Ilya Kazachkov
Using an analogue of Makanin-Razborov diagrams, we give a description of the solution set of systems of equations over an equationally Noetherian free product of groups $G$. Equivalently, we give a parametrisation of the set $Hom(H, G)$ of all homomorphisms from a finitely generated group $H$ to $G$. Furthermore, we show that every algebraic set over $G$ can be decomposed as a union of finitely many images of algebraic sets of NTQ systems. If the universal Horn theory of $G$ (the theory of quasi-identities) is decidable, then our constructions are effective.
http://arxiv.org/abs/0903.2096
14. On endomorphisms of torsion-free hyperbolic groups
O. Bogopolski, E. Ventura
Let $H$ be a torsion-free $\delta$-hyperbolic group with respect to a finite generating set $S$. Let $a_1,..., a_n$ and $a_{1*},..., a_{n*}$ be elements of $H$ such that $a_{i*}$ is conjugate to $a_i$ for each $i=1,..., n$. Then, there is a uniform conjugator if and only if $W(a_{1*},..., a_{n*})$ is conjugate to $W(a_1,..., 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 $\phi$ of $H$, if $\phi(h)$ is conjugate to $h$ for every element $h\in H$ of length up to $\mathcal {C}$, then $\phi$ 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.
http://arxiv.org/abs/0903.2306
15. Groups Elementarily Equivalent to a Free 2-nilpotent Group of Finite Rank
Alexei G. Myasnikov, Mahmood Sohrabi
In this paper we find a characterization for groups elementarily equivalent to a free nilpotent group $G$ of class 2 and arbitrary finite rank.
http://arxiv.org/abs/0903.2406
16. Twisted conjugacy classes in nilpotent groups
V. Romankov
Let $N$ be a finitely generated nilpotent group. Algorithm is constructed such, that for every automorphism $\phi \in Aut(N)$ defines the Reidemeister number $R(\phi).$ It is proved that any free nilpotent group of rank $r = 2$ or $r = 3$ and class $c \geq 4r,$ or rank $r \geq 4$ and class $c \geq 2r,$ belongs to the class $R_{\infty}.$
http://arxiv.org/abs/0903.3455
17. The Conjugacy Problem in Amalgamated Products I: Regular Elements and Black Holes
Alexandre V. Borovik, Alexei G. Myasnikov, Vladimir N. Remeslennikov
We discuss the time complexity of the word and conjugacy search problems for free products $G = A \star_C B$ of groups $A$ and $B$ with amalgamation over a subgroup $C$. We stratify the set of elements of $G$ with respect to the complexity of the word and conjugacy problems and show that for the generic stratum the conjugacy search problem is decidable under some reasonable assumptions about groups $A,B,C$.
http://arxiv.org/abs/0903.3751
18. Generic complexity of the Conjugacy Problem in HNN-extensions and algorithmic stratification of Miller's groups
Alexandre V. Borovik, Alexei G. Myasnikov, Vladimir N. Remeslennikov
We discuss time complexity of The Conjugacy Problem in HNN-extensions of groups, in particular, in Miller's groups. We show that for "almost all", in some explicit sense, elements, the Conjugacy Problem is decidable in cubic time. It is worth noting that the Conjugacy Problem in a Miller group may have be undecidable. Our results show that "hard" instances of the problem comprise a negligibly small part of the group.
http://arxiv.org/abs/0903.3754
19. On the universal theory of torsion and lacunary hyperbolic groups
D. Osin
We show that the universal theory of torsion groups is strongly contained in the universal theory of finite groups. This answers a question of Dyson. We also prove that the universal theory of some natural classes of torsion groups is undecidable. Finally we observe that the universal theory of the class of hyperbolic groups is undecidable and use this observation to construct a lacunary hyperbolic group with undecidable universal theory. Surprisingly, torsion groups play an important role in the proof of the latter results.
http://arxiv.org/abs/0903.3978
20. A Magnus theorem for some one-relator groups
Oleg Bogopolski, Konstantin Sviridov
We will say that a group G possesses the Magnus property if for any two elements u,v in G with the same normal closure, u is conjugate to v or v^{-1}. We prove that some one-relator groups, including the fundamental groups of closed nonorientable surfaces of genus g>3 possess this property. The analogous result for orientable surfaces of any finite genus was obtained by the first author [Geometric methods in group theory, Contemp. Math, 372 (2005) 59-69].
http://arxiv.org/abs/0904.1143
21. Strong law of large numbers on graphs and groups with applications -- I
Natalia Mosina and Alexander Ushakov
We introduce the notion of the mean-set (expectation) of a graph-(group-)valued random element $\xi$ and prove a generalization of the strong law of large numbers on graphs and groups. Furthermore, we prove an analogue of the classical Chebyshev's inequality for $\xi$. We show that our generalized law of large numbers, as a new theoretical tool, provides a framework for practical applications; namely, it has implications for cryptanalysis of group-based authentication protocols. In addition, we prove several results about configurations of mean-sets in graphs and their applications. In particular, we discuss computational problems and methods of computing of mean-sets in practice and propose an algorithm for such computation.
http://arxiv.org/abs/0904.1005
22. Intersections of conjugates of Magnus subgroups of one-relator groups
Donald J Collins
In the theory of one-relator groups, Magnus subgroups, which are free subgroups obtained by omitting a generator that occurs in the given relator, play an essential structural role. In a previous article, the author proved that if two distinct Magnus subgroups M and N of a one-relator group, with free bases S and T are given, then the intersection of M and N is either the free subgroup P generated by the intersection of S and T or the free product of P with an infinite cyclic group.
The main result of this article is that if M and N are Magnus subgroups (not necessarily distinct) of a one-relator group G and g and h are elements of G, then either the intersection of gMg^{-1} and hNh^{-1} is cyclic (and possibly trivial), or gh^{-1} is an element of NM in which case the intersection is a conjugate of the intersection of M and N.
http://arxiv.org/abs/0904.1358
---
END OF ISSUE
