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 2009
Thursday, April 23, 3:00-4:00, Room 920

V. Roman'kov (Omsk State U.)
The twisted conjugacy problem in solvable groups

Wednesday, April 15, 3:30, Room 920
M. Sohrabi (Carleton)
Title: On the elementary theories of free nilpotent Lie algebras and free
nilpotent groups.

Abstract: In the first part of the talk I shall give an algebraic
description of rings elementary equivalent to a free nilpotent Lie algbera
of finite rank over a characteristic zero integral domain. In the second
part algebraic strucure of a model of the elementary theory of a free
nilpotent group of finite rank will be discussed.

April 3, 2:30-4:30
Nicholas Touikan
Effective Grushko decomposition in f. p. groups with solvable word problem

April 1, 4:30-5:30, Burn 920

Svetla Vassileva (McGill)
The Conjugacy Problem in Free Solvable Groups

Our two main results are that the complexity of the conjugacy problem
for wreath products and for free solvable groups is polynomial. These are
based on the results in [1] and [2].
In her paper [1] Jane Matthews presented an alogrithm for solving the
Conjugacy Problem for a wreath product, AwrB, modulo a general assumption
about the component groups – namely, solvability in polynomial
time of the Conjugacy Problems for A and B and the power problem of
B. We will briefly introduce this algorithm and proceed to show that its
complexity is polynomial time.
We use this result and properties of the Magnus embedding (summarised
in [2]) to show that the conjugacy problem in free solvable groups
is computable in polynomial time.

[1] J. Matthews. The conjugacy problem in wreath products and free metabelian
groups. 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 Magnus
embedding. Algebra i Logika, 9(5):566–578, 1970

March 25, 30, 17:00-18:30, Burn 920
Algebraic Geometry over Solvable Groups
Nikolay Romanovskiy (Novosibirsk)

March 16, 17:00-19:00, room 920

and March 17, 16:00-17:30

Enric Ventura

Title: Twisted conjugacy for free groups, and the conjugacy problem for
some extensions of groups.

Abstract: I'll give a proof of the solvability of the twisted conjugacy
problem in free groups. As a first application, we will give a positive
solution for the conjugacy problem for free-by-cyclic groups. These
techniques extend to a much bigger family of groups, including
free-by-free groups. Here we will obtain a characterization of the
solvability of the conjugacy problem for such family of groups. As a
consequence, we'll find more examples of free-by-free groups with
solvable and unsolvable conjugacy problem. Also, we'll construct the first
known examples of Z4-by-free groups with unsolvable conjugacy problem.
Another nice consequence of all this story (due to Gilbert Levitt) is that
the isomorphism problem for free abelian-by-free (in fact, Z^4-by-F_15)
groups is also unsolvable.

Feb 11 Delaram Kahrobaei, CUNY

Title: Residual Solubility and True Prosoluble Completion of a Group

Residual Properties of groups is a term introduced by Philip Hall in 1954.
Let X be
a class of groups: a group G is residually-X if and only if for every
element g in G there is an epimorph of G to a group in X such that the
corresponding to g is not the identity. In the literature, studying the
solubility of groups was pioneered by Gilbert Baumslag in his celebrated
paper in
1971, where he showed that positive one-relator groups are residually
soluble. I
have studied the notion of residual solubility and verified this property
for several structures of groups. In this talk, I will give an overview of
some of these
results, from generalized free products to one-relator groups.

The true prosoluble completion P\Cal S (G) of a group G is the inverse
limit of the
projective system of soluble quotients of G. The definition proposed by G.
Arzhantseva, P. de la Harpe and myself. In this talk I will describe
examples including free groups, free soluble groups, wreath products,
SL_d(Z) and its congruent subgroups, the Grigorchuk group, and non-free
by Baumslag). I will point out some natural open problems, particularly I
discuss a question of Grothendieck for profinite completions and its
analogue for
true prosoluble and true pronilpotent completions.

Feb 4
Olga Kharlampovich, Limits of relatively hyperboliv groups

Jan 28
Ekaterina Blagoveshchenskaya, St Petersburg, Russia

Almost completely decomposable groups and their
endomorphism rings

An almost completely decomposable group ({\em acd-group}) is a
torsion-free abelian group of finite rank containing a completely
decomposable group (i.e. a direct sum of rank-one groups) as its
subgroup of finite index. The theory of acd-groups has been
intensively developed in the last decades. Monograph "Almost
Completely Decomposable Groups" by A. Mader, collects a
wide variety of the results obtained. In general, group properties
are tightly connected with its endomorphism ring properties. Another
monograph "Endomorphism Rings of Abelian Groups" by P. Krylov, A.
Mikhalev, A. Tuganbaev, provides a comprehensive
foundation for the investigation of such links since it includes the
classical background as well as recent results connecting abelian
groups with their endomorphism rings.
The main basis for combining group and ring approaches in the
particular case of acd-groups is the well-known fact that
endomorphism rings $\End X$ of acd-groups $X$ are also acd-groups
as additive structures. In this way some special methods, which
appeared in the acd-group theory, can be applied to the rings for
examining dual connections between acd-groups and their
endomorphism rings.

Fall 2008

Tullia Dymarz, Yale University
Dec 3, 15:00-17:30; BURN 920
Dec 4, 15:00-17:00; BURN 920
Dec 5, 10:00-12:00; BURN 920

Coarse 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 the
class 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 quasiconformal
maps 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-7
Residually free week at McGill
Jim Howie
“Decision problems and finiteness problems for residually free groups”
Jim Howie, Heriot-Watt University, Edinburgh
Nov 3, 3:30-5:00, BH 920
Nov 4, 4:00-5:30 BH 708
Nov 5, 3:30-4:30 and 5:00-6:00 BH 920

Abstract: 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 solutions
to some decision problems such as the conjugacy problem and membership problem for finitely presented
residually free groups.


A. Miasnikov, “Introduction to fully residually free (limit) groups”
Nov 2, 1:00-2:00, BH 920

D. Serbin, “Graph techniques for fully residually free groups I”
Nov 2, 2:15-3:45, BH 920

I. Bumagin, “Algorithms for fully residually free groups I”
Nov 3, 5:30-6:30, either BH 1028 or BH 1024

D. Serbin, “Graph techniques for fully residually free groups II”
Nov 4, 6:00-7:00, BH 708

N. 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 116

O. Kharlampovich,
 Elementary theory of a free group 6
AE theory of a free group
Wednesday, 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 with
Friday Sept. 26, 3:00-4:30 Room 920 or 1028,

Elementary free groups
Wednesday, Oct 1, 3:30-5:00, Room 920

N. Touikan (McGill)
Equations with two variables and fully residually free groups 3
Monday, 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 with

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 2

Tuesday, Sep. 16 4:00-5:30 O. Kharlampovich
Elementary theory of a free group 2

Wednesday, Sept. 17, 3:30-5:00, Room 920
N. Touikan (McGill)

Wednesday, Sept. 13, 3:30-5:00, Room 920
A. Nikolaev, D. Serbin
Subgroups of fully residually free groups

5:00-6:30 O. Kharlampovich
Elementary 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:30
Burn 920

O. Kharlampovich (McGill)

Implicit function theorem for free groups.

I will briefly outline some of the key points (see below) in our proof
with A. Myasnikov of the Tarski conjectures about the elementary theory of
a free group and talk about the implicit function theorem (see item 3 below).
These conjectures stated that the elementary theory of non-abelian free
groups of different ranks coinside and that this common theory is
decidable. The first conjecture was independently proved by Sela. The key
points are:

1. Development of the algebraic geometry over groups in several papers by
Baumslag, Myasnikov, Remeslennikov and myself;
2. The theory of fully residually free groups (limit groups) and a simple
algebraic description of them, embedding of fully residually free groups
into NTQ groups;
3. Implicit function theorem for regular quadratic and NTQ systems of
equations in free groups, Skolem functions;
4. Elimination process that works in groups with free Lyndon's length
function (which is a development of Makanin-Razborov process for solving
equations in free groups);
5. Description of the solution set of systems of equations with parameters
(independent of the particular values of the parameters), different
finiteness 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. fully
residually free group;
7. Decidability of the AE-theory of a free group, termination of the
decision process;
8. Reduction (non-effective) of an arbitrary formula to a boolean
combination 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. subgroup
of a limit group to be of finite index. This criterion
can be checked effectively which leads to an algorithm
that effectively decides if a f.g. subgroup of a
limit group is of finite index. As another application
of the criterion we obtain an analogue of
Greenberg-Stallings Theorem for limit groups, and
prove that a f.g. non-abelian subgroup of a limit
group 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 partially
commutative groups


Firstly, I will give a criterion for a partially commutative group G to be
a domain. It allows us to reduce the study of algebraic sets over G to the
study of irreducible
algebraic sets, and reduce the elementary theory of G (of a coordinate
group over G) to
the elementary theories of the direct factors of G (to the elementary
theory of coordinate
groups of irreducible algebraic sets).

If time permits, I will establish normal forms for quantifier-free
formulas over a non-abelian directly
indecomposable partially commutative group H. Analogously to the case of
free groups, we
introduce the notion of a generalised equation and prove that the positive
theory of H has
quantifier elimination and that arbitrary first-order formulas lift from H
to $H\ast F$,
where F is a free group of finite rank. As a consequence, the positive
theory of an arbitrary
partially 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 group

Abstract: We will give an exposition of Plandowski's polynomial time
algorithm that solves the word problem for compressed words in a free
group. Using this algorithm Schleimer constructed a polynomial time
algorithm that solves the word problem in the group of automorphisms of a
free group.

Sep. 18. N. Touikan (McGill)
The equation w(x,y)=u over free groups

Using some of the recent techniques used to study the elementary theory of
free 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}. The
paper can be found at:

(Here is a link to our schedule during 2007-2008)

(Here is a link to our schedule during 2005-2006)

(Here is a link to our schedule during 2004-2005)

(Here is a link to our schedule during 2003-2004)

(Here is a link to our schedule during 2002-2003)