Montreal Geometric & Combinatorial Group Theory Seminar

 The seminar meets each Wednesday at 4:30pm in 920 Burnside Hall at 805 Sherbrooke West - McGill University.
Winter 2009Thursday, April 23, 3:00-4:00, Room 920V. Roman'kov (Omsk State U.)The twisted conjugacy problem in solvable groupsWednesday, April 15, 3:30, Room 920M. Sohrabi (Carleton)Title: On the elementary theories of free nilpotent Lie algebras and freenilpotent groups.Abstract: In the first part of the talk I shall give an algebraicdescription of rings elementary equivalent to a free nilpotent Lie algberaof finite rank over a characteristic zero integral domain. In the secondpart algebraic strucure of a model of the elementary theory of a freenilpotent group of finite rank will be discussed.April 3, 2:30-4:30Nicholas TouikanEffective Grushko decomposition in f. p. groups with solvable word problemApril 1, 4:30-5:30, Burn 920Svetla Vassileva (McGill)The Conjugacy Problem in Free Solvable GroupsOur two main results are that the complexity of the conjugacy problemfor wreath products and for free solvable groups is polynomial. These arebased on the results in [1] and [2].In her paper [1] Jane Matthews presented an alogrithm for solving theConjugacy Problem for a wreath product, AwrB, modulo a general assumptionabout the component groups – namely, solvability in polynomialtime of the Conjugacy Problems for A and B and the power problem ofB. We will briefly introduce this algorithm and proceed to show that itscomplexity is polynomial time.We use this result and properties of the Magnus embedding (summarisedin [2]) to show that the conjugacy problem in free solvable groupsis computable in polynomial time.[1] J. Matthews. The conjugacy problem in wreath products and free metabeliangroups. T. Am. Math. Soc., 121:329–339, 1966. English transl., Soviet Math.Dokl. 8 (1967), 555–557.[2] V. N. Remeslennikov and V. G. Sokolov. Certain properties of Magnusembedding. Algebra i Logika, 9(5):566–578, 1970March 25, 30, 17:00-18:30, Burn 920Algebraic Geometry over Solvable GroupsNikolay Romanovskiy (Novosibirsk)March 16, 17:00-19:00, room 920 and March 17, 16:00-17:30Enric VenturaTitle: Twisted conjugacy for free groups, and the conjugacy problem forsome extensions of groups.Abstract: I'll give a proof of the solvability of the twisted conjugacyproblem in free groups. As a first application, we will give a positivesolution for the conjugacy problem for free-by-cyclic groups. Thesetechniques extend to a much bigger family of groups, includingfree-by-free groups. Here we will obtain a characterization of thesolvability of the conjugacy problem for such family of groups. As aconsequence, we'll find more examples of free-by-free groups withsolvable and unsolvable conjugacy problem. Also, we'll construct the firstknown examples of Z4-by-free groups with unsolvable conjugacy problem.Another nice consequence of all this story (due to Gilbert Levitt) is thatthe isomorphism problem for free abelian-by-free (in fact, Z^4-by-F_15)groups is also unsolvable.Feb 11 Delaram Kahrobaei, CUNYTitle: Residual Solubility and True Prosoluble Completion of a GroupAbstract:Residual Properties of groups is a term introduced by Philip Hall in 1954.Let X bea class of groups: a group G is residually-X if and only if for everynon-trivialelement g in G there is an epimorph of G to a group in X such that theelementcorresponding to g is not the identity. In the literature, studying theresidualsolubility of groups was pioneered by Gilbert Baumslag in his celebratedpaper in1971, where he showed that positive one-relator groups are residuallysoluble. Ihave studied the notion of residual solubility and verified this propertyfor several structures of groups. In this talk, I will give an overview ofsome of theseresults, from generalized free products to one-relator groups.The true prosoluble completion P\Cal S (G) of a group G is the inverselimit of theprojective system of soluble quotients of G. The definition proposed by G.Arzhantseva, P. de la Harpe and myself. In this talk I will describeexamples including free groups, free soluble groups, wreath products,SL_d(Z) and its congruent subgroups, the Grigorchuk group, and non-freeparafreegroups(discoveredby Baumslag). I will point out some natural open problems, particularly Iwilldiscuss a question of Grothendieck for profinite completions and itsanalogue fortrue prosoluble and true pronilpotent completions.Feb 4Olga Kharlampovich, Limits of relatively hyperboliv groupsJan 28Ekaterina Blagoveshchenskaya, St Petersburg, RussiaAlmost completely decomposable groups  and theirendomorphism ringsAn  almost completely decomposable group ({\em acd-group}) is atorsion-free abelian group of finite rank containing a completelydecomposable group (i.e. a direct sum of rank-one groups) as itssubgroup of finite index. The theory of acd-groups has beenintensively developed in the last decades. Monograph "AlmostCompletely Decomposable Groups" by A. Mader, collects awide variety of the results obtained. In general, group propertiesare tightly connected with its endomorphism ring properties. Anothermonograph "Endomorphism Rings of Abelian Groups" by P. Krylov, A.Mikhalev, A. Tuganbaev,  provides a comprehensivefoundation for the investigation of such links since it includes theclassical background as well as recent results connecting abeliangroups with their endomorphism rings.The main basis for combining group and ring approaches in theparticular case of acd-groups is the well-known fact thatendomorphism rings $\End X$ of  acd-groups $X$ are also  acd-groupsas additive structures. In this way some special methods, whichappeared in the acd-group theory, can be applied to the rings forexamining dual connections between  acd-groups and theirendomorphism rings.Fall 2008Tullia Dymarz, Yale UniversityDec 3, 15:00-17:30; BURN 920Dec 4, 15:00-17:00; BURN 920Dec 5, 10:00-12:00; BURN 920Coarse differentiation and geometry of solvable Lie groups  Abstract In the early 80's Gromov initiated a program of studying finitely generated groups up to quasi-isometry by showing that theclass of lattices in nilpotent Lie groups is quasi-isometrically rigid. Since then, Gromov's program has been carried out for many classes of groups including a complete classification of lattices in semisimple Lie groups. A lattice in a group is a discrete subgroup where the quotient of group by subgroup has finite volume. Lattices in Lie groups are especially natural to study from a quasi-isometry perspective because one can often use the geometry of the ambient Lie group to prove rigidity results about the lattices themselves. Despite this, rigidity for the next natural class of lattices, lattices in solvable Lie groups, remained intractable until recently. The main breakthrough came with Eskin-Fisher-Whyte's development of a technique of coarse differentiation". This technique allowed Eskin-Fisher-Whyte to prove quasi-isometric rigidity for the three dimensional Sol geometry as well as to outline a program for proving rigidity for a large class of solvable Lie groups.        Lecture 1 – “Quasi-isometric rigidity and geometry of Sol and Diestel-Leader graphs”In the first part of this talk we will sketch the proof of quasi-isometric rigidity for cocompact lattices in real hyperbolic spaces. This will give us a framework for all rigidity results proved in these lectures. We will discuss quasi-actions, induced boundary maps, and Tukia's Theorem on quasiconformalmaps of the sphere. Next we will focus on the geometry of three dimensional Sol and related Diestel-Leader graphs. (The same proof works both for Sol and for lattices in the isometry group of DL graphs). Using our framework, we will present an outline of the proof, modulo coarse differentiation, of quasi-isometric rigidity of these spaces.        Lecture 2 – “Coarse differentiation”Although coarse differentiation was developed to analyze quasi-isometries of Sol, the technique can also be applied to arbitrary length spaces. Morally, coarse differentiation can be thought of as an analogue for quasi-isometries of Rademacher's theorem on Lipschitz maps. We will present the general idea behind coarse differentiation and then go through the ideas needed to apply coarse differentiation to Sol and DL graphs.        Lecture 3 – “Geometry and rigidity of solvable Lie groups”Coarse differentiation can also be used to analyze other classes of solvable Lie groups. Peng has used coarse differentiation to prove structure results for quasi-isometries of abelian by abelian solvable Lie groups. For these solvable Lie groups, the boundaries and induced boundary maps are much more complicated. We will describe the geometry of the abelian by cyclic Lie groups and give an idea of how to prove a Tukia-like theorem on the boundaries these solvable Lie groups. Finally we will give some indications of challenges ahead and of current work in progress.Nov 3-7Residually free week at McGillMini-course“Decision problems and finiteness problems for residually free groups”Jim Howie, Heriot-Watt University, EdinburghNov 3, 3:30-5:00, BH 920Nov 4, 4:00-5:30 BH 708Nov 5, 3:30-4:30 and 5:00-6:00 BH 920Abstract: A finitely generated residually free group is known to be embeddable into a direct product of finitely many fully residually free groups. In these lectures I will explain how such embeddings can be used to investigate finiteness properties such as finite presentability, and to provide solutionsto some decision problems such as the conjugacy problem and membership problem for finitely presented residually free groups.TalksA. Miasnikov, “Introduction to fully residually free (limit) groups”Nov 2, 1:00-2:00, BH 920D. Serbin, “Graph techniques for fully residually free groups I”Nov 2, 2:15-3:45, BH 920I. Bumagin, “Algorithms for fully residually free groups I”Nov 3, 5:30-6:30, either BH 1028 or BH 1024D. Serbin, “Graph techniques for fully residually free groups II”Nov 4, 6:00-7:00, BH 708N. Touikan, “Coordinate groups of irreducible two-variable equations over a free group”Nov 6, 4:00-5:00, either BH 1028 or LEA 116.O. Kharlampovich, “Algorithms for fully residually free groups II”Nov 6, 5:30-6:30, either BH 1028 or LEA 116O. Kharlampovich, Elementary theory of a free group 6AE theory of a free groupWednesday, Oct 8, 3:30-5:00, Room 920 O. Kharlampovich Elementary theory of a free group 5(The proof of finiteness results for Hom-diagrams for equations withparameters)Friday Sept. 26, 3:00-4:30 Room 920 or 1028,Elementary free groupsWednesday, Oct 1, 3:30-5:00, Room 920N. Touikan (McGill)Equations with two variables and fully residually free groups 3Monday, Sept. 29, 3:30-5:00, Room 920
 O. Kharlampovich Elementary theory of a free group 3(The proof of finiteness results for Hom-diagrams for equations withparameters)Monday, Sept. 22, 3:30-5:00 Room 920,Tuesday, Sept. 23, 4:00-6:00, Room ?N. Touikan (McGill)Equations with two variables and fully residually free groups 2Tuesday, Sep. 16 4:00-5:30 O. KharlampovichElementary theory of a free group 2Wednesday, Sept. 17, 3:30-5:00, Room 920N. Touikan (McGill)Wednesday, Sept. 13, 3:30-5:00, Room 920A. Nikolaev, D. SerbinSubgroups of fully residually free groups5:00-6:30 O. KharlampovichElementary theory of a free group I(finiteness results for Hom-diagrams for equations with parameters)
Equations with two variables and fully residually free groups(finiteness results for Hom-diagrams for equations with parameters)Wednesday, Sept. 24, 3:30-5:00, Room 920

Winter 2008



WEDNESDAY, April 23, 30, May 7, 14   3:30-4:30Burn 920O. Kharlampovich (McGill)Implicit function theorem for free groups.I will briefly outline some of the key points (see below) in our proofwith A. Myasnikov of the Tarski conjectures about the elementary theory ofa free group and talk about the implicit function theorem (see item 3 below).These conjectures stated that the elementary theory of non-abelian freegroups of different ranks coinside and that this common theory isdecidable. The first conjecture was independently proved by Sela. The keypoints are:1. Development of the algebraic geometry over groups in several papers byBaumslag, Myasnikov, Remeslennikov and myself;2. The theory of fully residually free groups (limit groups) and a simplealgebraic description of them, embedding of fully residually free groupsinto NTQ groups;3. Implicit function theorem for regular quadratic and NTQ systems ofequations in free groups, Skolem functions;4. Elimination process that works in groups with free Lyndon's lengthfunction (which is a development of Makanin-Razborov process for solvingequations in free groups);5. Description of the solution set of systems of equations with parameters(independent of the particular values of the parameters), differentfiniteness conditions;6. Solution of algorithmic problems in f.g. fully residually free groups,infinite words and effectiveness of the JSJ decomposition of a f.g. fullyresidually free group;7. Decidability of the AE-theory of a free group, termination of thedecision process;8. Reduction (non-effective) of an arbitrary formula to a booleancombination of AE-formulas, effective approach to an arbitrary sentence.

<>WEDNESDAY, March 26, 3:30-4:30
Burn 920

A. Miasnikov (McGill)
Elimination Processes in Algebraic Geometry for Groups
Abstract: I will continue discussing different Elimination Processes used
in our work on the Tarski problems (joint with O. Kharlampovich). The
initial version of such a process was introduced by Makanin for solving
equations in a free group.

MONDAY, March 10,  <>12:30-14:00<>
Burn 920
Mahmood Sohrabi (Carleton University)

Title: Hall-Petresco Formula, Mal'cev basis and embeddings of torsion free f.g.
nilpotent groups

Abstract: I'll present a proof of Hall-Petresco formula and describe Mal'cev bases
for torsion free f.g. nilptent groups. Then I'll explain how the fact that products
in the groups described above are given by certain polynomials enable us to embed
them in various structures such as nilpotent Lie groups and groups admitting
exponents in binomial domains.
Feb 18  Mahmood Sohrabi (Carleton University)
Title: Second cohomology group and alternating bilinear maps
Location: Burnside 1120
Time: Monday 12:30- 14:00
Abstract: In this talk I'll discuss a well known correspondence between central extensions of an abelian group $A$ by an abelian group $B$ and alternating bilinearmaps of abelian groups via the second cohomology group $H^2(B,A)$. If time permits I'll discuss connections with the graded lie algebra associated to the lower centralseries of a 2-nilpotent group.

Jan 24. A. Miasnikov (McGill University)
Title: Conjugacy problem for the Grigorchuk group.
Abstract: This problem is polynomial time decidable for the famousGrigorchuk group of intermediate growth.

Fall 2007

Dec. 5 Jose Burillo  (Universitat Politecnica de Catalunia)Computational questions in Thompson's Group F.Nov. 28 A. Nikolaev (McGill University)Title: Finite index subgroups of limit groups.Abstract: We provide a criterion for a f.g. subgroupof a limit group to be of finite index. This criterioncan be checked effectively which leads to an algorithmthat effectively decides if a f.g. subgroup of alimit group is of finite index. As another applicationof the criterion we obtain an analogue ofGreenberg-Stallings Theorem for limit groups, andprove that a f.g. non-abelian subgroup of a limitgroup is of finite index in its commensurator.(jointly with D.Serbin)
Nov. 21 M. Casals-Ruiz (McGill)Title: Elements of Algebraic Geometry and the Positive Theory of partiallycommutative groupsAbstract:Firstly, I will give a criterion for a partially commutative group G to bea domain. It allows us to reduce the study of algebraic sets over G to thestudy of irreduciblealgebraic sets, and reduce the elementary theory of G (of a coordinategroup over G) tothe elementary theories  of the direct factors of G (to the elementarytheory of coordinategroups of irreducible algebraic sets).If time permits, I will establish normal forms for quantifier-freeformulas over a non-abelian directlyindecomposable partially commutative group H. Analogously to the case offree groups, weintroduce the notion of a generalised equation and prove that the positivetheory of H hasquantifier elimination and that arbitrary first-order formulas lift from Hto $H\ast F$,where F is a free group of finite rank. As a consequence, the positivetheory of an arbitrarypartially commutative group is decidable.
Nov. 14.  A. Miasnikov (McGill University)

“The Word Problem in Free Solvable Groups”
We study the computational complexity of the Word Problem (WP) in free solvable groups S(r,d), where r > 1 is the rank and d > 1 is the solvability class of the group. It is known that the Magnus embedding of S(r,d) into matrices provides a polynomial time decision algorithm for WP in a fixed group S(r,d). Unfortunately, the degree of this polynomial grows together with d, so the uniform algorithm is not polynomial in d. I will present a new decision algorithm for WP in S(r,d) that has complexity O(n^3 r d), so it is at most cubic in the length of the input in any free solvable group. Surprisingly, it turned out that a seemingly close problem of computing the geodesic length of elements is NP-complete even in a free metabelian group S(r,2). This particular combination of an easy WP and hard geodesic length problem plays a part in non-commutative cryptography. This is a joint work with A.Ushakov, V.Romankov, and A.Vershik.

Nov. 7.  N. Touikan (McGill)
"NP completeness of the satisfiability problem for quadratic equations in free groups and monoids"

Oct 30. N. Touikan (McGill)
"Complexity of the satisfiability problem for quadratic equations in free groups and monoids"

Oct. 24.  D. Serbin (McGill)
"Automata, infinite words and groups acting on trees",
abstract: "In my talk I am going to introduce finite automata labeled by infinite words of special type and show how they can be used for solving various algorithmic problems in groups whose elements are representable by infinite words. I am going to show how such automata arise geometrically as well as combinatorially".

Oct. 17.  O. Kharlampovich (McGill)
Title: Quadratic equations in free groups and monoids.
Abstract: I will present Diekert and Robson's proof that the satisfiability problem for quadratic equations in a free monoid is NP-hard. I will also discuss quadratic equations in a free group.

Oct. 10. J. Macdonald (McGill)
Compressed words II: applications
We will use compressed words to solve the word problems of Aut(F_n) and free-by-cyclic groups in polynomial time (we follow Shleimer's paper). We'll also give reductions of word problems for semi-direct products, automatic groups, and free products to certain compressed word problems.

Oct. 3. N. Touikan (McGill)Title: Equation w(x,y)=u in a free group, part 2.Sep. 26.  Jeremy Macdonald(McGill)Title: Word problem for compressed words in a free groupAbstract: We will give an exposition of Plandowski's polynomial timealgorithm that solves the word problem for compressed words in a freegroup. Using this algorithm Schleimer constructed a polynomial timealgorithm that solves the word problem in the group of automorphisms of afree group.Sep. 18. N. Touikan (McGill)Title:The equation w(x,y)=u over free groupsAbstract:Using some of the recent techniques used to study the elementary theory offree groups, I will describe the structure of equations of the form w(x,y)= u, where u lies in F and w(x,y) is a word in unknowns {x,y}^\{pm 1}. Thepaper can be found at: http://arxiv.org/abs/0705.4246(Here is a link to our schedule during 2007-2008)<http://www.math.mcgill.ca/wise/ggt/seminar0506.html> (Here is a link to our schedule during 2005-2006)<http://www.math.mcgill.ca/wise/ggt/seminar0506.html> (Here is a link to our schedule during 2004-2005)<http://www.math.mcgill.ca/wise/ggt/seminar0405/seminar0405.html> (Here is a link to our schedule during 2003-2004)<http://www.math.mcgill.ca/wise/ggt/seminar0304.html>  (Here is a link to our schedule during 2002-2003)<http://www.math.mcgill.ca/wise/ggt/seminar0203/seminar0203.htm>