

Winter 2009
Thursday, April 23, 3:004: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:304:30
Nicholas Touikan
Effective Grushko decomposition in f. p. groups with solvable word problem
April 1, 4:305: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:0018:30, Burn 920
Algebraic Geometry over Solvable Groups
Nikolay Romanovskiy (Novosibirsk)
March 16, 17:0019:00, room 920
and March 17, 16:0017: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 freebycyclic groups. These
techniques extend to a much bigger family of groups, including
freebyfree 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 freebyfree groups with
solvable and unsolvable conjugacy problem. Also, we'll construct the first
known examples of Z4byfree groups with unsolvable conjugacy problem.
Another nice consequence of all this story (due to Gilbert Levitt) is that
the isomorphism problem for free abelianbyfree (in fact, Z^4byF_15)
groups is also unsolvable.
Feb 11 Delaram Kahrobaei, CUNY
Title: Residual Solubility and True Prosoluble Completion of a Group
Abstract:
Residual Properties of groups is a term introduced by Philip Hall in 1954.
Let X be
a class of groups: a group G is residuallyX if and only if for every
nontrivial
element g in G there is an epimorph of G to a group in X such that the
element
corresponding to g is not the identity. In the literature, studying the
residual
solubility of groups was pioneered by Gilbert Baumslag in his celebrated
paper in
1971, where he showed that positive onerelator 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 onerelator 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 nonfree
parafree
groups(discovered
by Baumslag). I will point out some natural open problems, particularly I
will
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 acdgroup}) is a
torsionfree abelian group of finite rank containing a completely
decomposable group (i.e. a direct sum of rankone groups) as its
subgroup of finite index. The theory of acdgroups 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 acdgroups is the wellknown fact that
endomorphism rings $\End X$ of acdgroups $X$ are also acdgroups
as additive structures. In this way some special methods, which
appeared in the acdgroup theory, can be applied to the rings for
examining dual connections between acdgroups and their
endomorphism rings.
Fall 2008
Tullia Dymarz, Yale University
Dec 3, 15:0017:30; BURN 920
Dec 4, 15:0017:00; BURN 920
Dec 5, 10:0012: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 quasiisometry by showing that the
class of lattices in nilpotent Lie groups is quasiisometrically 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 quasiisometry 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 EskinFisherWhyte's development of a technique of ``
coarse differentiation". This technique allowed EskinFisherWhyte to prove quasiisometric 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 – “Quasiisometric rigidity and geometry of Sol and DiestelLeader graphs”
In the first part of this talk we will sketch the proof of quasiisometric 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 quasiactions, 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 DiestelLeader 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
quasiisometric rigidity of these spaces.
Lecture 2 – “Coarse differentiation”
Although coarse differentiation was developed to analyze quasiisometries of Sol, the technique can also be applied to arbitrary length spaces.
Morally, coarse differentiation can be thought of as an analogue for quasiisometries 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 quasiisometries 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 Tukialike theorem on the boundaries these solvable Lie groups. Finally we will give some indications of challenges ahead and of current work in progress.
Nov 37
Residually free week at McGill
Minicourse
“Decision problems and finiteness problems for residually free groups”
Jim Howie, HeriotWatt University, Edinburgh
Nov 3, 3:305:00, BH 920
Nov 4, 4:005:30 BH 708
Nov 5, 3:304:30 and 5:006: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.
Talks
A. Miasnikov, “Introduction to fully residually free (limit) groups”
Nov 2, 1:002:00, BH 920
D. Serbin, “Graph techniques for fully residually free groups I”
Nov 2, 2:153:45, BH 920
I. Bumagin, “Algorithms for fully residually free groups I”
Nov 3, 5:306:30, either BH 1028 or BH 1024
D. Serbin, “Graph techniques for fully residually free groups II”
Nov 4, 6:007:00, BH 708
N. Touikan, “Coordinate groups of irreducible twovariable equations over a free group”
Nov 6, 4:005:00, either BH 1028 or LEA 116.
O. Kharlampovich, “Algorithms for fully residually free groups II”
Nov 6, 5:306: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:305:00, Room 920
O. Kharlampovich
Elementary theory of a free group 5
(The proof of finiteness results for Homdiagrams for equations with
parameters)
Friday Sept. 26, 3:004:30 Room 920 or 1028,
Elementary free groups
Wednesday, Oct 1, 3:305:00, Room 920
N. Touikan (McGill)
Equations with two variables and fully residually free groups 3
Monday, Sept. 29, 3:305:00, Room 920
O. Kharlampovich
Elementary theory of a free group 3
(The proof of finiteness results for Homdiagrams for equations with
parameters)
Monday, Sept. 22, 3:305:00 Room 920,
Tuesday, Sept. 23, 4:006:00, Room ?
N. Touikan (McGill)
Equations with two variables and fully residually free groups 2
Tuesday, Sep. 16 4:005:30 O. Kharlampovich
Elementary theory of a free group 2
Wednesday, Sept. 17, 3:305:00, Room 920
N. Touikan (McGill)
Wednesday, Sept. 13, 3:305:00, Room 920
A. Nikolaev, D. Serbin
Subgroups of fully residually free groups
5:006:30 O. Kharlampovich
Elementary theory of a free group I
(finiteness results for Homdiagrams for equations with parameters)
Equations with two variables and fully residually free groups
(finiteness results for Homdiagrams for equations with parameters)
Wednesday, Sept. 24, 3:305:00, Room 920
Winter 2008
WEDNESDAY, April 23, 30, May 7, 14 3:304: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 nonabelian 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 MakaninRazborov 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 AEtheory of a free group, termination of the
decision process;
8. Reduction (noneffective) of an arbitrary formula to a boolean
combination of AEformulas, effective approach to an arbitrary sentence.
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
GreenbergStallings Theorem for limit groups, and
prove that a f.g. nonabelian subgroup of a limit
group is of finite index in its commensurator.
(jointly with D.Serbin)
Nov. 21 M. CasalsRuiz (McGill)
Title: Elements of Algebraic Geometry and the Positive Theory of partially
commutative groups
Abstract:
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 quantifierfree
formulas over a nonabelian 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 firstorder 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.
“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 NPcomplete 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 noncommutative 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
NPhard.
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
freebycyclic groups in polynomial time (we follow Shleimer's paper).
We'll also give reductions of
word problems for semidirect 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)
Title:
The equation w(x,y)=u over free groups
Abstract:
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: http://arxiv.org/abs/0705.4246
(Here is a link to our schedule during 20072008)
<http://www.math.mcgill.ca/wise/ggt/seminar0506.html>
(Here is a link to our schedule during 20052006)
<http://www.math.mcgill.ca/wise/ggt/seminar0506.html>
(Here is a link to our schedule during 20042005)
<http://www.math.mcgill.ca/wise/ggt/seminar0405/seminar0405.html>
(Here is a link to our schedule during 20032004)
<http://www.math.mcgill.ca/wise/ggt/seminar0304.html>
(Here is a link to our schedule during 20022003)
<http://www.math.mcgill.ca/wise/ggt/seminar0203/seminar0203.htm>