# SCIENTIFIC PROGRAMS AND ACTIVITIES

November 23, 2014

## 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.

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.

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