December 14-16, 2007
Fields Workshop in Asymptotic Group Theory and Cryptography
at Carleton University
|
|
|
ORGANIZERS: Olga Kharlampovich (McGill) and Inna Bumagin
(Carleton).
|
|
Abstracts
|
Gregory Bell
Mapping class groups have finite asymptotic dimension
We show how results from work on the asymptotic dimension of a
fundamental group of a developable complex of groups can be applied
to show that mapping class groups have finite asymptotic dimension.
This talk is joint work with Alexander Dranishnikov.
Andrew Duncan
Universal equivalence of pregroups and partially commutative
groups
In 1971, while studying ends of groups, Stallings introduced
a generalisation of amalgamated product of groups -- called a pregroup,
which is a kind of partial group. The universal group $U(P)$ of
a pregroup $P$ as a universal object (in the sense of category theory)
such that the partial operations on $P$ extend to group operations
on $U(P)$. This gives a convenient and versatile generalisation
of the fundamental group of a graph of groups. The following general
question arises. Which properties of pregroups and relations between
pregroups carry over to the respective universal groups? In this
talk I shall indicate how universal equivalence of pregroups extends
to universal equivalence of universal groups and give some applications
to partially commutative groups.
(Co-authorsI. V. Kazachkov and V. N. Remeslennikov)
Murray Elder
Stallings' group has a quadratic Dehn function.
This is joint work with Will Dison, Tim Riley and Robert Young.
In the 60's Stallings came up with a finitely presented group whose
3-dimensional integral homology is not finitely presented, or is
not of type FP_3 or F_3. In this talk I will present a series of
algorithms which combine to prove that every word representing 1
can be reduced to the empty word using at most a quadratic number
of relators, proving a quadratic Dehn function. So the class of
groups with quadratic Dehn function is weirder and wilder than you
might have expected.
Bob Gilman
Efficiency of group-theoretic algorithms.
As most decision problems for finitely presented groups are
recursively unsolvable, the usual approaches to estimating time
complexity do not work. We will discuss some alternative methods.
C. K. Gupta
Automorphisms, Primitive Systems, Test Sets.
The test rank of the group G of solvable products of m non -trivial
free abelian groups A1,....,Am of finite ranks is equal to m-1 if
we consider the solvable variety of length n, n greater than equal
to 2.
This is my most recent work with E.I. Timoshenko. As a Corollary
we obtain that the test rank of a free solvable group of rank r
and length n for r greater than equal to 2 is r--1 answering a question
of Fine and Shpilrain. Also, I shall mention some other our most
recent results.
Vadim Kaimanovich
Ergodic properties of boundary actions and Nielsen's method
Ilya Kapovich
Geometric Intersection Number and analogues of the Curve Complex
for free groups.
We prove the existence of a canonical Bonahon-type continuous
$Out(F_N)$-invariant "geometric intersection form" $i\overline{cv}(F_N)
x Curr(F_N)\to \mathbb R$. Here $Curr(F_N)$ is the space of geodesic
currents on $F_N$ and $\overline{cv}(F_N)$ is is the closure of
unprojectivized Culler-Vogtmann's Outer space $cv(F_N)$ in the equivariant
Gromov-Hausdorff convergence topology (or, equivalently, in the
length function topology). It is known that $\overline{cv}(F_N)$
consists of all very small minimal isometric actions of $F_N$ on
$\mathbb R$-trees. The projectivization of $\overline{cv}(F_N)$
provides a free group analogue of Thurston's compactification of
the Teichm\"uller space.
As an application, using the \emph{intersection graph} determined
by the intersection form, we show that several natural analogues
of the
curve complex in the free group context have infinite diameter.
This talk is based on joint work with Martin Lustig.
Francesco Matucci
Cryptanalysis of the Shpilrain-Ushakov protocol in Thompson's
group.
We show an attack on the Shpilrain-Ushakov protocol for Thompson's
group F, based on the representation of F as a group of piecewise-linear
functions. Our attack exposes the private keys used in the protocol
in every instance. We compare it to other proposed attacks and observe
that our approach is specific to the group F, and has only a limited
range of generalization to other platform groups.
Alexei Miasnikov
The Word and Geodesic Problems 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 on the class of all free solvable groups
of finite rank. 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 n of the input in any free solvable group.
Surprisingly, it turned out that the problem of computing the
geodesic length of elements is NP-hard even in a free metabelian
group S(r,2). To show this we use some geometric ideas coming from
flows on Cayley graphs. This is a joint work with A.Ushakov, V.Romankov,
and A.Vershik.
Andrey Nikolaev
Finite index subgroups of limit groups.
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)
Alexander Olshanskii
On some oscillating Dehn functions of groups
Tim Riley
Survey talk I -Outstanding problems in low-dimensional topology
and group theory
There is an intriguing web of hard problems at the intersection
of group theory and low-dimensional topology. They include the Poincaré
Conjecture, the Andrews-Curtis Conjecture, the Whitehead Asphericity
Conjecture, the Zeeman Conjecture, the Relation Gap Problem, the
D(2) Conjecture, and the Eilenberg-Ganea Conjecture. I will describe
these problems and some of their interconnections.
-----------------------------------------------------------------------
Survey talk II
The geometry of the Conjugacy Problem
The Conjugacy Problem for a finitely generated group is to give
an algorithm which, on input two words, declares whether or not
they represent conjugate elements of the group.
If the group is finitely presented then its Conjugacy Problem can
be investigated geometrically through the study of annuli. I will
discuss
these annuli in a number of groups such as hyperbolic groups, CAT(0)
groups, biautomatic groups, nilpotent groups, Thompson's group and
Stallings' group and I will give many open questions.
Research talk (Saint Sauveur)
Hydra groups
I will describe a family of groups exhibiting wild features
in the context of their Conjugacy Problems. These features stem
from manifestations of "Hercules versus the hydra battles".
This is joint work with Martin Bridson.
Mark Sapir (Talk in Ottawa)
Percolation in Cayley graphs of groups
I will give a survey of known results about percolation in transitive
graphs. I will also talk about results of my student, Iva Kozakova,
about critical percolation on Cayley graphs of amalgamated products
and HNN extensions. Some open problems related to percolation will
be also formulated.
Mark Sapir (Talks in St. Sauveur)
Asymptotic cones of groups
I will talk about using asymptotic cones to deduce some algebraic
and geometric properties of groups. In particular I will give conceptually
easy proofs of the Kaimanovich-Masur theorem and the Birman-Lubotzky-McCarthy
theorem about subgroups of mapping class groups, and theorems about
homomorphisms of groups into relatively hyperbolic groups.
Dmytro Savchuk
Some graphs related to Thompson's group F
We explicitly construct an induced subgraph of the left Cayley
graph of Thompson's group F with respect to the generating set {x_0,x_1},
containing all vertices of the form wx_n for w in the monoid generated
by x_0 and x_1 and n>=0. We show that this graph is non-amenable.
Also we describe the structure of the Shcreier graphs of the action
of F on the set of ordered tuples of dyadic rational numbers from
the
interval (0,1) and show that these graphs are amenable.
Denis Serbin
"Automata, infinite words and groups acting on trees".
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.
Vladimir Shpilrain
How mathematicians can contribute to cryptography
Until now, mathematicians who want to contribute to cryptography
have been primarily trying to come up with new key establishment
protocols. These attempts have been easily dismissed by cryptographers
who do not want competition, on the grounds of "lack of
security proofs". In this talk, I will explain that there is
an "hierarchy" of cryptographic products in terms of how
easy they are to dismiss on these grounds. In particular, I will
show that it is possible to design a zero-knowledge authentication
scheme whose breaking (i.e., obtaining a secret key) is NP-complete.
Ben Steinberg
Submonoids and Rational Subsets of Right-Angled Artin Groups.
We show that the following are equivalent for a right-angled
Artin group associated to a graph \Gamma:
1. Membership in finitely generated submonoids is decidable.
2. Membership in rational subsets is decidable.
3. The graph \Gamma does not contain an induced 4-cycle or an induced
path of with of length 3.
In particular, the right-angled Artin group associated to a path
of length 4 has decidable generalized word problem, but undecidable
membership in finitely generated submonoids, which is the first
example of such to our knowledge.
This is joint work with Markus Lohrey.
Zoran Sunic
Forbidden patterns and groups of tree automorphisms
We provide a characterization of finitely constrained groups
(analog of shifts of finite type) of tree automorphisms in terms
of branch groups. Further, we provide graphical representation of
groups defined as factors of finitely constrained groups (analog
of sofic shifts).
We prove that there are no infinite, topologically finitely generated,
finitely constrained groups of binary tree automorphisms defined
by forbidden patterns of size (at most) two. The last result is
an application of a general result that roughly says that a finitely
constrained group defined by patterns appearing in a contracting
group contains a dense, countable, regular branch, contracting subgroup.
Nicholas Touikan
The equation w(x,y)=u over free groups.
We investigate the structures of solutions to equations of the
form w(x,y)=u where u is a fixed element of a free group F and x,y
are unknowns. Our techniques rely on; and serve as an explicit illustration
of; the theory developed by Olga Kharlampovich, Alexei Miasnikov,
and, independently, by Zlil Sela to describe the set of homomorphisms
of a f.g. group G into a free group F. In particular we describe
the arising Hom or Makanin-Razborov diagrams and describe the possible
canonical automorphisms.
Top
For additional information contact gensci(PUT_AT_SIGN_HERE)fields.utoronto.ca
