CGC Bulletin 27
Contents
- Compressed words and automorphisms in fully residually free groups
- On Shavgulidze's Proof of the Amenability of some Discrete Groups of Homeomorphisms of the Unit Interval
- Journal of Mathematical Cryptology Vol. 3
- Growing words in the free group on two generators
- Diophantine Geometry over Groups IX: Envelopes and Imaginaries
- Topology of Random Right Angled Artin Groups
- On the Relations Between Diffie-Hellman and ID-Based Key Agreement from Pairings
- Asymptotic Behaviour of Return Probabilities of Random Walks on Free Products of Groups
- Finitely generated infinite simple groups of infinite commutator width and vanishing stable commutator length
- Gr\"obner-Shirshov bases for braid groups in Adyan-Thurston generators
- Computing fixed closures in free groups
- Structure Theorems for Subgroups of Homeomorphisms Groups
- On certain permutation representations of the braid group
- The monomorphism problem in free groups
- A finitary version of Gromov's polynomial growth theorem
- A note on the definition of small overlap monoids
Regards,
Boaz Tsaban
Bulletin's webpage: http://www.cs.biu.ac.il/~tsaban/CGC/cgc.html
1. Compressed words and automorphisms in fully residually free groups
Jeremy Macdonald
We show that the compressed word problem in a finitely-generated fully residually free group (F -group) is decidable in polynomial time, and use the result to show that the word problem in the automorphism group of such a group is decidable in polynomial time.
http://arxiv.org/abs/0908.0569
2. On Shavgulidze's Proof of the Amenability of some Discrete Groups of Homeomorphisms of the Unit Interval
Matthew G. Brin, and many others
Notes that elaborate on the details of a Theorem of Shavgulidze that implies the amenability of R. J. Thompson's group F.
http://arxiv.org/abs/0908.1353
3. Journal of Mathematical Cryptology Vol. 3
A cryptographic primitive based on hidden-order groups
Amitabh Saxena and Ben Soh
Improved security analysis for OMAC as a pseudorandom function
Mridul Nandi
Subset sum pseudorandom numbers: fast generation and distribution
Joachim von zur Gathen and Igor E. Shparlinski
Another look at some fast modular arithmetic methods
M. Jason Hinek and Charles C. Y. Lam
4. Growing words in the free group on two generators
Bobbe J. Cooper, Eric S. Rowland
This paper is concerned with minimal length representatives of equivalence classes of F_2 under Aut F_2. We give a simple inequality characterizing words of minimal length in their equivalence class. We consider an operation that "grows" words from other words, increasing the length, and we study root words -- minimal words that cannot be grown from other words. Root words are "as minimal as possible" in the sense that their characterization is the boundary case of the minimality inequality. The property of being a root word is respected by equivalence classes, and the length of each root word is divisible by 4.
5. Diophantine Geometry over Groups IX: Envelopes and Imaginaries
Zlil Sela
This paper is the ninth in a sequence on the structure of sets of solutions to systems of equations in free and hyperbolic groups, projections of such sets (Diophantine sets), and the structure of definable sets over free and hyperbolic groups. In the ninth paper we associate a Diophantine set with a definable set, and view it as the Diophantine envelope of the definable set. We use the envelope and duo limit groups that were used in proving stability of the theory of free and torsion-free hyperbolic groups [Se9], to study definable equivalence relations, and in particular, to classify imaginaries over these groups.
http://arxiv.org/abs/0909.0774
6. Topology of Random Right Angled Artin Groups
Armindo Costa and Michael Farber
In this paper we study topological invariants of a class of random groups. Namely, we study right angled Artin groups associated to random graphs and investigate their Betti numbers, cohomological dimension and topological complexity. The latter is a numerical homotopy invariant reflecting complexity of motion planning algorithms in robotics. We show that the topological complexity of a random right angled Artin group assumes, with probability tending to one, at most three values. We use a result of Cohen and Pruidze which expresses the topological complexity of right angled Artin groups in combinatorial terms. Our proof deals with the existence of bi-cliques in random graphs.
http://arxiv.org/abs/0909.0887
7. On the Relations Between Diffie-Hellman and ID-Based Key Agreement from Pairings
Shengbao Wang
This paper studies the relationships between the traditional Diffie-Hellman key agreement protocol and the identity-based (ID-based) key agreement protocol from pairings.
For the Sakai-Ohgishi-Kasahara (SOK) ID-based key construction, we show that identical to the Diffie-Hellman protocol, the SOK key agreement protocol also has three variants, namely \emph{ephemeral}, \emph{semi-static} and \emph{static} versions. Upon this, we build solid relations between authenticated Diffie-Hellman (Auth-DH) protocols and ID-based authenticated key agreement (IB-AK) protocols, whereby we present two \emph{substitution rules} for this two types of protocols. The rules enable a conversion between the two types of protocols. In particular, we obtain the \emph{real} ID-based version of the well-known MQV (and HMQV) protocol.
Similarly, for the Sakai-Kasahara (SK) key construction, we show that the key transport protocol underlining the SK ID-based encryption scheme (which we call the "SK protocol") has its non-ID counterpart, namely the Hughes protocol. Based on this observation, we establish relations between corresponding ID-based and non-ID-based protocols. In particular, we propose a highly enhanced version of the McCullagh-Barreto protocol.
http://arxiv.org/abs/0909.1388
8. Asymptotic Behaviour of Return Probabilities of Random Walks on Free Products of Groups
Elisabetta Candellero and Lorenz A. Gilch
Suppose we are given finitely generated groups $\Gamma_1,...,\Gamma_m$ equipped with irreducible random walks. Thereby we assume that the expansions of the corresponding Green functions at their radii of convergence contain only logarithmic or root terms as singular terms (except from some degenerate cases). We consider transient random walks on the free product $\Gamma_1 \ast >... \ast\Gamma_m$ and give a complete classification of the possible asymptotic behaviour of the corresponding $n$-step return probabilities. They either inherit a law of the form $\varrho^{n\delta} n^{-\lambda_i}$ from one of the free factors $\Gamma_i$ or obey a $\varrho^{n\delta} n^{-3/2}$-law, where $\varrho<1$ is the corresponding spectral radius and $\delta$ is the period of the random walk. In addition, we determine the full range of the asymptotic behaviour in the case of nearest neighbour random walks on free products of the form $\Z^{d_1}\ast ... \ast \Z^{d_m}$.
http://arxiv.org/abs/0909.1893
9. Finitely generated infinite simple groups of infinite commutator width and vanishing stable commutator length
Alexey Muranov
It is shown that there exists a finitely generated infinite simple group of infinite commutator width and infinite square width in which every conjugation-invariant norm is stably bounded, and in particular the stable commutator length vanishes. Moreover, a recursive presentation of such a group with decidable word and conjugacy problems is constructed.
http://arxiv.org/abs/0909.2294
10. Gr\"obner-Shirshov bases for braid groups in Adyan-Thurston generators
Yuqun Chen and Chanyan Zhong
In this paper, we give a Gr\"obner-Shirshov basis of the braid group $B_{n+1}$ in Adyan-Thurston generators. We also deal with the braid group of type $\bf{B}_{n}$. As results, we obtain a new algorithm for getting the Adyan-Thurston normal form, and a new proof that the braid semigroup $B^+_{n+1}$ is the subsemigroup in $B_{n+1}$.
http://arxiv.org/abs/0909.3639
11. Computing fixed closures in free groups
Enric Ventura
Let $F$ be a finitely generated free group. We present an algorithm such that, given a subgroup $H\leqslant F$, decides whether $H$ is the fixed subgroup of some family of automorphisms, or family of endomorphisms of $F$ and, in the affirmative case, finds such a family. The algorithm combines both combinatorial and geometric methods.
http://arxiv.org/abs/0910.0713
12. Structure Theorems for Subgroups of Homeomorphisms Groups
Collin Bleak, Martin Kassabov, Francesco Matucci
Let Homeo(S^1) represent the full group of homeomorphisms of the unit circle S^1, and let A represent the set of subgroups of Homeo(S^1) satisfying the two properties that if G is in A then (1) G contains only orientation-preserving homeomorphisms of S^1 and (2) G contains no non-abelian free subgroups. In this article we use classical results about homeomorphisms of the circle and elementary dynamical methods to derive various new and old results about the groups in A; we give a general structure theorem for such groups, a classification of the solvable subgroups of R. Thompson's group T, and a new proof of Margulis' Theorem that given G in A the circle S^1 admits a G-invariant probability measure.
http://arxiv.org/abs/0910.0218
13. On certain permutation representations of the braid group
Valentin Vankov Iliev
This paper is devoted to the proof of a structural theorem, concerning certain homomorphic images of Artin braid group on $n$ strands in finite symmetric groups. It is shown that any one of these permutation groups is the semidirect product of the symmetric group on $n$ letters by an appropriate abelian group.
http://arxiv.org/abs/0910.1727
14. The monomorphism problem in free groups
Laura Ciobanu, Abderezak Ould Houcine
Let $F$ be a free group of finite rank. We say that the monomorphism problem in $F$ is decidable if for any two elements $u$ and $v$ in $F$, there is an algorithm that determines whether there exists a monomorphism of $F$ that sends $u$ to $v$. In this paper we show that the monomorphism problem is decidable and we provide an effective algorithm that solves the problem.
http://arxiv.org/abs/0910.1899
15. The twisted conjugacy problem for pairs of endomorphisms in nilpotent groups
V. Roman'kov, E. Ventura
An algorithm is constructed that, when given an explicit presentation of a finitely generated nilpotent group $G,$ decides for any pair of endomorphisms $\varphi, \psi : G \to G$ and any pair of elements $u, v \in G,$ whether or not the equation $(x\varphi)u = v (x\psi)$ has a solution $x \in G.$ Thus it is shown that the problem of the title is decidable. Also we present an algorithm that produces a finite set of generators of the subgroup (equalizer) $Eq_{\varphi, \psi}(G) \leq G$ of all elements $u \in G$ such that $u \varphi = u \psi .$
http://arxiv.org/abs/0910.3463
15. A finitary version of Gromov's polynomial growth theorem
Yehuda Shalom, Terence Tao
We show that for some absolute (explicit) constant $C$, the following holds for every finitely generated group $G$, and all $d >0$:
If there is some $ R_0 > \exp(\exp(Cd^C))$ for which the number of elements in a ball of radius $R_0$ in a Cayley graph of $G$ is bounded by $R_0^d$, then $G$ has a finite index subgroup which is nilpotent (of step $<C^d$). An effective bound on the finite index is provided if "nilpotent" is replaced by 'polycyclic", thus yielding a non-trivial result for finite groups as well.
http://arxiv.org/abs/0910.4148
16. A note on the definition of small overlap monoids
Mark Kambites
Small overlap conditions are simple and natural combinatorial conditions on semigroup and monoid presentations, which serve to limit the complexity of derivation sequences between equivalent words in the generators. They were introduced by J.H.Remmers, and more recently have been extensively studied by the present author. However, the definition of small overlap conditions hitherto used by the author was slightly more restrictive than that introduced by Remmers; this note eliminates this discrepancy by extending the recent methods and results of the author to apply to Remmers' small overlap monoids in full generality.
http://arxiv.org/abs/0910.4511
---
END OF ISSUE
