CGC Bulletin 26

eZine lover (@eZine)

Published in 

CGC Bulletin

 · 9 months ago

Contents

1. Braids and crossed modules
2. Equations and fully residually free groups
3. Fast growth in F{\o}lner sets for Thompson's group F
4. Effective indices of subgroups in one-relator groups with free quotients
5. The discrete logarithm problem in the group of non-singular circulant matrices
6. Complexity of relations in the braid group
7. Small braids having a big Ultra Summit Set
8. An automata theoretic approach to the generalized word problem in graphs of groups
9. Conjugacy in normal subgroups of hyperbolic groups
10. Journal of Mathematical Cryptology 3 (1)
11. Geodesic rewriting systems and pregroups
12. Regular sets and counting in free groups
13. Combinatorial distance between braid words
14. Group theory in cryptography
15. Submonoids and rational subsets of groups with infinitely many ends
16. Groups with free regular length functions in Z^n
17. A Note on Topologically-Trivial Braids
18. Presentations of Graph Braid Groups
19. Some geodesic problems in groups
20. On computing geodesics in Baumslag-Solitar groups
21. REESSE1+ . Reward . Proof by Experiment

Regards,

Boaz Tsaban

Bulletin's webpage: http://www.cs.biu.ac.il/~tsaban/CGC/cgc.html

1. Braids and crossed modules

Johannes Huebschmann

We describe Artin's braid group on a (fixed) finite number of strings as a crossed module over itself. In particular, we interpret the braid relations as crossed module structure relations.

http://arxiv.org/abs/0904.3895

2. Equations and fully residually free groups

Olga Kharlampovich, Alexei Myasnikov

This paper represents notes of the mini-courses given by the authors at the GCGTA conference in Dortmund (2007), Ottawa-Saint Sauveur conference (2007), Escola d'Algebra in Rio de Janeiro (2008) and Alagna (Italy, 2008) conference on equations in groups. We explain here the Elimination process for solving equations in a free group which has Makanin-Razborov process as a prototype. We also explain how we use this process to obtain the structure theorem for finitely generated fully residually free groups and many other results.

http://arxiv.org/abs/0904.4482

3. Fast growth in F{\o}lner sets for Thompson's group F

Justin Tatch Moore

The purpose of this note is to prove a lower bound on the F{\o}lner function for Thompson's groups F.

http://arxiv.org/abs/0905.1118

4. Effective indices of subgroups in one-relator groups with free quotients

Thomas Koberda

Given a one-relator group, we give an effective estimate on the minimal index of a subgroup with a nonabelian free quotient. We show that the index is bounded by a polynomial in the length of the relator word. We also provide a lower bound on the index.

http://arxiv.org/abs/0905.2713

5. The discrete logarithm problem in the group of non-singular circulant matrices

Ayan Mahalanobis

The discrete logarithm problem is one of the backbones in public key cryptography. In this paper we study the discrete logarithm problem in the group of circulant matrices over a finite field. This gives rise to secure and fast public key cryptosystems.

http://arxiv.org/abs/0905.3135

6. Complexity of relations in the braid group

Joel Hass, Arkadius Kalka, Tahl Nowik

We show that for any given n, there exists a sequence of words a_k in the generators sigma_1, ... sigma_{n-1} of the braid group B_n, representing the identity element of B_n, such that the number of braid relations of the form sigma_i sigma_{i+1} sigma_i = sigma_{i+1} sigma_i sigma_{i+1} needed to pass from a_k to the empty word is quadratic with respect to the length of a_k.

http://arxiv.org/abs/0906.0137 , 155kb)

7. Small braids having a big Ultra Summit Set

Maxim Prasolov

In [J.Birman, V.Gebhardt, J.Gonzalez-Meneses, Conjugacy in Garside groups I: cyclings, powers and rigidity] authors asked: (open question 2) is the size of USS of a rigid pseudo-Anosov braid is bounded above by some polynomial in the number of strands and the braid length? We answer this question in the negative.

http://arxiv.org/abs/0906.0076

8. An automata theoretic approach to the generalized word problem in graphs of groups

Markus Lohrey and Benjamin Steinberg

We give a simpler proof using automata theory of a recent result of Kapovich, Weidmann and Myasnikov according to which so-called benign graphs of groups preserve decidability of the generalized word problem. These include graphs of groups in which edge groups are polycyclic-by-finite and vertex groups are either locally quasiconvex hyperbolic or polycyclic-by-finite and so in particular chordal graph groups (right-angled Artin groups).

http://arxiv.org/abs/0905.4395

9. Conjugacy in normal subgroups of hyperbolic groups

Armando Martino, Ashot Minasyan

Let N be a finitely generated normal subgroup of a Gromov hyperbolic group G. We establish criteria for N to have solvable conjugacy problem and be conjugacy separable in terms of the corresponding properties of G/N. We show that the version of Rips's construction, found by Haglund and Wise, is hereditarily conjugacy separable. We then use it to produce first examples of finitely generated conjugacy separable groups that contain non-conjugacy separable subgroups of finite index.

http://arxiv.org/abs/0906.1606

10. Journal of Mathematical Cryptology, Volume 3, Number 1 (May 2009)

Distortion maps for supersingular genus two curves
Steven D. Galbraith, Jordi Pujola`s, Christophe Ritzenthaler, and Benjamin Smith

Families of genus 2 curves with small embedding degree
Laura Hitt

One-round secure comparison of integers
Ian F. Blake and Vladimir Kolesnikov

Hash function requirements for Schnorr signatures
Gregory Neven, Nigel P. Smart, and Bogdan Warinschi

http://www.reference-global.com/toc/jmc/3/1

11. Geodesic rewriting systems and pregroups

Volker Diekert, Andrew J. Duncan, Alexei Miasnikov

(To appear in "Combinatorial and Geometric Group Theory, Dortmund and Carleton Conferences".)

In this paper we study rewriting systems for groups and monoids, focusing on situations where finite convergent systems may be difficult to find or do not exist. We consider systems which have no length increasing rules and are confluent and then systems in which the length reducing rules lead to geodesics. Combining these properties we arrive at our main object of study which we call geodesically perfect rewriting systems. We show that these are well-behaved and convenient to use, and give several examples of classes of groups for which they can be constructed from natural presentations. We describe a Knuth-Bendix completion process to construct such systems, show how they may be found with the help of Stallings' pregroups and conversely may be used to construct such pregroups.

http://arxiv.org/abs/0906.2223

12. Regular sets and counting in free groups

Elizaveta Frenkel, Alexei G. Myasnikov, Vladimir N. Remeslennikov

In this paper we study asymptotic behavior of regular subsets in a free group F of finite rank, compare their sizes at infinity, and develop techniques to compute the probabilities of sets relative to distributions on F that come naturally from no-return random walks on the Cayley graph of F. We apply these techniques to study cosets, double cosets, and Schreier representatives of finitely generated subgroups of F and also to analyze relative sizes of regular prefixed-closed subsets in F.

http://arxiv.org/abs/0906.2850

13. Combinatorial distance between braid words

Patrick Dehornoy

We give a simple naming argument for establishing lower bounds on the combinatorial distance between (positive) braid words.

http://arxiv.org/abs/0906.3814

14. Group theory in cryptography

Simon R. Blackburn, Carlos Cid, Ciaran Mullan

This paper is a guide for the pure mathematician who would like to know more about cryptography based on group theory. The paper gives a brief overview of the subject, and provides pointers to good textbooks, key research papers and recent survey papers in the area.

http://arxiv.org/abs/0906.5545

15. Submonoids and rational subsets of groups with infinitely many ends

Markus Lohrey and Benjamin Steinberg

In this paper we show that the membership problems for finitely generated submonoids and for rational subsets are recursively equivalent for groups with two or more ends.

http://arxiv.org/abs/0907.0787

16. Groups with free regular length functions in Z^n

Olga Kharlampovich, Alexei Miasnikov, Vladimir Remeslennikov, Denis Serbin

This is the first paper in a series of three where we take on the unified theory of non-Archimedean group actions, length functions and infinite words. Our main goal is to show that group actions on Z^n-trees give one a powerful tool to study groups. All finitely generated groups acting freely on -trees also act freely on some Z^n-trees, but the latter ones form a much larger class. The natural effectiveness of all constructions for $Z^n-actions (which is not the case for R-trees) comes along with a robust algorithmic theory. In this paper we describe the algebraic structure of finitely generated groups acting freely and regularly on Z^n-trees and give necessary and sufficient conditions for such actions.

http://arxiv.org/abs/0907.2356 , 29kb)

17. A Note on Topologically-Trivial Braids

Orlin Stoytchev

We give a simple characterization of braids that can be unplaited keeping separately their upper ends and their lower ends tied together

http://arxiv.org/abs/0907.2318

18. Presentations of Graph Braid Groups

Daniel Farley and Lucas Sabalka

Let G be a graph. The (unlabeled) configuration space of n points on G is the space of all n-element subsets of G. The fundamental group of such a configuration space is called a graph braid group. We use a version of discrete Morse theory to compute presentations of all graph braid groups, for all finite connected graphs G and all natural numbers n.

http://arxiv.org/abs/0907.2730

19. Some geodesic problems in groups

Murray Elder, Eric Fusy, Andrew Rechnitzer

We consider several algorithmic problems concerning geodesics in finitely generated groups. We show that the three geodesic problems considered by Miasnikov et al [arXiv:0807.1032] are polynomial-time reducible to each other. We study two new geodesic problems which arise in a previous paper of the authors [arXiv:0902.0202].

http://arxiv.org/abs/0907.3258

20. On computing geodesics in Baumslag-Solitar groups

Volker Diekert and J\"urn Laun

We introduce the peak normal form of elements of the Baumslag-Solitar groups BS(p,q). This normal form is very close to the length-lexicographical normal form, but more symmetric. Both normal forms are geodesic. This means the normal form of an element $u^{-1}v$ yields the shortest path between $u$ and $v$ in the Cayley graph. The main result of this paper is that we can compute the peak normal form in polynomial time if $p$ divides $q$. As consequence we can compute geodesic lengths in this case. In particular, this gives a partial answer to Question 1 in Elder et al. 2009, arXiv.org:0907.3258 For arbitrary $p$ and $q$ it is possible to compute the peak normal form for elements in the horocyclic subgroup and, more generally, for elements which we call hills. This approach leads to a linear time reduction of the problem of computing geodesics to the problem of computing geodesics for Britton-reduced words where the $t$-sequence starts with $t^{-1}$ and ends with $t$. To solve the general case in polynomial time for arbitrary $p$ and $q$ remains a challenging open problem.

http://arxiv.org/abs/0907.5114

21. REESSE1+ . Reward . Proof by Experiment

Shenghui Su, Shuwang Lu

The article states what is a proof, what is provable security, and what are approaches to provable security, thinks that the provable security is a type of asymptotic, relative, and dynamic security, and is only a complement to but not a replacement of exact security or concrete security from security analysis. Lastly, a reward is offered for the solution of three REESSE1+ problems, which may be regarded as a type of security proof by experiment.

http://arxiv.org/abs/0908.0482

---

END OF ISSUE