CGC Bulletin 24
Contents
- On Shephard Groups with Large Triangles
- A new Garside structure for braid groups of type (e,e,r)
- Cryptanalysing the Critical Group: Efficiently Solving Biggs's Discrete Logarithm Problem
- Parameters for which the Lawrence-Krammer representation is reducible
- On identities in Thompson's group
- Counting elements and geodesics in Thompson's group $F$
- The congruence subgroup problem for braid groups: Thurston's proof
- Journal of Mathematical Cryptology December 2008, Vol. 2, No. 4
- On Dehn functions of infinite presentations of groups
- Finite Thurston type orderings on dual braid monoids
- From Thompson to Baer-Suzuki: a sharp characterization of the solvable radical
- NNRU, a noncommutative analogue of NTRU
- Makanin-Razborov Diagrams over Free Products
- One Variable Equations in Torsion-Free Hyperbolic Groups
- Computing equations for residually free groups
- A new metric criterion for non-amenability III: Non-amenability of R.Thompson's group F
Regards,
Boaz Tsaban
Bulletin's webpage: http://www.cs.biu.ac.il/~tsaban/CGC/cgc.html
1. On Shephard Groups with Large Triangles
Uri Weiss
Shephard groups are common extensions of Artin and Coxeter groups. They appear, for example, in algebraic study of manifolds. An infinite family of Shephard groups which are not Artin or Coxeter groups is considered. Using techniques form small cancellation theory we show that the groups in this family are bi-automatic.
http://arxiv.org/abs/0901.0094
2. A new Garside structure for braid groups of type (e,e,r)
Ruth Corran, Matthieu Picantin
We describe a new presentation for the complex reflection groups of type (e,e,r) and their braid groups. A diagram for this presentation is proposed. The presentation is a monoid presentation which is shown to give rise to a Garside structure. A detailed study of the combinatorics of this structure leads us to describe it as _post-classical_.
http://arxiv.org/abs/0901.0645
3. Cryptanalysing the Critical Group: Efficiently Solving Biggs's Discrete Logarithm Problem
Simon R. Blackburn
Abstract: Biggs has recently proposed the critical group of a certain class of finite graphs as a platform group for cryptosystems relying on the difficulty of the discrete log problem. The paper uses techniques from the theory of Picard groups on finite graphs to show that the discrete log problem can be efficiently solved in Biggs's groups. Thus this class of groups is not suitable as a platform for discrete log based cryptography.
http://eprint.iacr.org/2008/170
4. Parameters for which the Lawrence-Krammer representation is reducible
Claire I. Levaillant and David B. Wales
We show that the Lawrence-Krammer representation based on two parameters that was used by Bigelow and independently Krammer to show the linearity of the braid group is generically irreducible, but that when its parameters are specialized to some nonzero complex numbers, the representation is reducible. To do so, we construct a representation of the BMW algebra inside the Lawrence-Krammer space. As a representation of the braid group, this representation is equivalent to the Lawrence-Krammer representation, where the two parameters of the algebra are related to the parameters of the Lawrence-Krammer representation. We give all the complex values of the parameters for which the representation is reducible and describe the invariant subspaces in some cases. We show that for these values of the parameters and other values, the BMW algebra is not semisimple.
http://arxiv.org/abs/0901.3856
5. On identities in Thompson's group
Evgenii S. Esyp
In this article we prove that Thompson's group does not belong to any algebraic variety.
http://arxiv.org/abs/0902.0199
6. Counting elements and geodesics in Thompson's group $F$
Murray Elder, Eric Fusy, Andrew Rechnitzer
We present two quite different algorithms to compute the number of elements in the sphere of radius $n$ of Thompson's group $F$ with standard generating set. The first of these requires polynomial time and space and allows us to compute the size of the spheres of radius $n$ with $n \leq 1500$. The second algorithm requires exponential time and polynomial space, but additionally computes the number of geodesics and is generalisable to many other groups. Using the resulting series data we find that the growth rate of the group is bounded above by $2.62167...$. This is very close to Guba's lower bound of $\tfrac{3+\sqrt{5}}{2}$. Indeed, numerical analysis of the series data strongly suggests that the growth rate of the group is exactly $\tfrac{3+\sqrt{5}}{2}$.
http://arxiv.org/abs/0902.0202
7. The congruence subgroup problem for braid groups: Thurston's proof
D. B. McReynolds
In this article we present an unpublished proof of W. Thurston that pure braid groups have the congruence subgroup property.
http://arxiv.org/abs/0901.4663
8. Journal of Mathematical Cryptology December 2008, Vol. 2, No. 4
Another look at non-standard discrete log and Diffie-Hellman problems Neal Koblitz and Alfred Menezes
Identification and signatures based on NP-hard problems of indefinite quadratic forms Rupert J. Hartung and Claus-Peter Schnorr
Polylogarithmic two-round argument systems Thilo Mie
Minimal weight expansions in Pisot bases Christiane Frougny and Wolfgang Steiner
Two attacks on a sensor network key distribution scheme of Cheng and Agrawal M. B. Paterson and D. R. Stinson
9. On Dehn functions of infinite presentations of groups
R.I. Grigorchuk and S.V. Ivanov
We introduce two new types of Dehn functions of group presentations which seem more suitable (than the standard Dehn function) for infinite group presentations and prove the fundamental equivalence between the solvability of the word problem for a group presentation defined by a decidable set of defining words and the property of being computable for one of the newly introduced functions (this equivalence fails for the standard Dehn function). Elaborating on this equivalence and making use of this function, we obtain a characterization of finitely generated groups for which the word problem can be solved in nondeterministic polynomial time. We also give upper bounds for these functions, as well as for the standard Dehn function, for two well-known periodic groups one of which is an infinite 2-group of intermediate growth and the other is a free Burnside group of sufficiently large exponent.
http://arxiv.org/abs/0902.1358
10. Finite Thurston type orderings on dual braid monoids
Tetsuya Ito
We give a combinatorial description of a finite Thurston type ordering $<$ on the dual braid monoid $B_{n}^{+*}$ by introducing the $\C$-normal form and prove that the order-type of the well-ordered set $(B_{n}^{+*},<)$ is $\omega^{\omega^{n-2}}$. The $\C$-normal form can be seen as a generalization of the rotating normal form defined by Fromentin and it is also a natural extension of $\C$-normal form of the positive braid monoids defined by the author.
http://arxiv.org/abs/0902.0833
11. From Thompson to Baer-Suzuki: a sharp characterization of the solvable radical
Nikolai Gordeev, Fritz Grunewald, Boris Kunyavskii, Eugene Plotkin
We prove that an element $g$ of prime order $>3$ belongs to the solvable radical $R(G)$ of a finite (or, more generally, a linear) group if and only if for every $x\in G$ the subgroup generated by $g, xgx^{-1}$ is solvable. This theorem implies that a finite (or a linear) group $G$ is solvable if and only if in each conjugacy class of $G$ every two elements generate a solvable subgroup.
http://arxiv.org/abs/0902.1912 ,
12. NNRU, a noncommutative analogue of NTRU
Nitin Vats
NTRU public key cryptosystem is well studied lattice-based Cryptosystem along with Ajtai-Dwork and GGH systems. Underlying NTRU is a hard mathematical problem of finding short vectors in a certain lattice. (Shamir 1997) presented a lattice-based attack by which he could find the original secret key or alternate key. Shamir concluded if one designs a variant of NTRU where the calculations involved during encryption and decryption are non-commutative then the system will be secure against Lattice based attack.This paper presents a new cryptosystem with above property and we have proved that it is completely secure against Lattice based attack. It operates in the non-commutative ring M=M_k Z[X]/(X^n - I_{k*k}, where M is a matrix ring of k*k matrices of polynomials in R={Z}[X]/(X^n-1). Moreover We have got speed improvement by a factor of O(k^{1.624) over NTRU for the same bit of information.
http://arxiv.org/abs/0902.1891
13. Makanin-Razborov Diagrams over Free Products
E. Jaligot and Z. Sela
This paper is the first in a sequence on the first order theory of free products. In the first paper we generalize the analysis of systems of equations over free and (torsion-free) hyperbolic groups, and analyze system of equations over free products. To do that we introduce limit groups over the class of free products, and show that a finitely presented group has a canonical (finite) collection of maximal limit quotients. We further extend this finite collection and associate a Makanin-Razborov diagram over free products with a finitely presented group. This MR diagram encodes all the quotients of a given finitely presented group that are free products, all its homomorphisms into free products, and equivalently all the solutions to a given system of equations over a free product.
http://arxiv.org/abs/0902.2493
14. One Variable Equations in Torsion-Free Hyperbolic Groups
Abderezak Ould Houcine
Let $\Gamma$ be a torsion-free hyperbolic group such that any two-generator subgroup of $\Gamma$ is free. We show that the set of solutions of a system of equations with one variable in $\Gamma$ is a finite union of points and cosets of centralizers.
http://arxiv.org/abs/0902.3599
15. Computing equations for residually free groups
Vincent Guirardel and Gilbert Levitt
We show that there is no algorithm deciding whether the maximal residually free quotient of a given finitely presented group is finitely presentable or not.
Given a finitely generated subgroup G of a finite product of limit groups, we discuss the possibility of finding an explicit set of defining equations (i.e. of expressing G as the maximal residually free quotient of an explicit finitely presented group).
http://arxiv.org/abs/0902.2119
16. A new metric criterion for non-amenability III: Non-amenability of R.Thompson's group F
Azer Akhmedov
We present new metric criteria for non-amenability and discuss applications. The main application of the results of this paper is the proof of non-amenability of R.Thompson's group F. This is a continuation of the series of papers on our criteria for non-amenability. The current paper is independent of other papers in the series.
http://arxiv.org/abs/0902.3849
---
END OF ISSUE
