Copy Link

Add to Bookmark

Report

CGC Bulletin 23

eZine lover (@eZine)

Published in

CGC Bulletin

· 9 months ago

The automorphism group of accessible groups
Almost all one-relator groups with at least three generators are residually finite
Unsolvability of the isomorphism problem for [free abelian]-by-free groups
Metric properties of higher-dimensional Thompson's groups
On finite Thurston type orderings of braid groups
Journal of Mathematical Cryptology 2(3): Contents
A recursive presentation for Mihailova's subgroup
Non-cyclic graph associated with a group
Left-Garside categories, self-distributivity, and braids
Geometric entropy of geodesic currents on free groups
On Systems of Equations over Free Partially Commutative Groups
A variant of Wiener's attack on RSA
On right-angled Artin groups without surface subgroups
Mather invariants in groups of piecewise-linear homeomorphisms
Tree-pair Diagrams, the Word Problem, and the Metric for Generalizations of Thompson's Group F on more than One Integer
Every braid admits a short sigma-definite representative
Compressed word problems in HNN-extensions and amalgamated products
Reducing conjugacy in the full diffeomorphism group of R to conjugacy in the subgroup of orientation-preserving maps
Strongly Contracting Geodesics in Outer Space
Two-generator subgroups of the pure braid group
Phase transitions in infinitely generated groups, and related problems in additive number theory
"Set-theoretical" solutions of the quantum Yang-Baxter equation and a class of Garside groups
New Permutation Representations of the Braid Group
New Presentations of Thompson's Groups and Applications
The R- and L-orders of the Thompson-Higman monoid M_{k,1} and their complexity
Proving finitely presented groups are large by computer
An Effective Lower Bound for Group Complexity of Finite Semigroups and Automata

Have a fruitful 2009,

Boaz Tsaban

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

1. The automorphism group of accessible groups

Mathieu Carette

In this article, we study the outer automorphism group of a group G decomposed as a finite graph of group with finite edge groups and finitely generated vertex groups with at most one end. We show that Out(G) is essentially obtained by taking extensions of relative automorphism groups of vertex groups, groups of Dehn twists and groups of automorphisms of free products. We apply this description and obtain a criterion for Out(G) to be finitely presented, as well as a necessary and sufficient condition for Out(G) to be finite. Consequences for hyperbolic groups are discussed.

http://arxiv.org/abs/0810.0043

2. Almost all one-relator groups with at least three generators are residually finite

Iva Kozakova, Mark Sapir

We prove that with probability tending to 1, a 1-relator group with at least 3 generators and relator of length n is residually finite, virtually residually (finite p)-group for all sufficiently large p, and coherent. The proof uses both combinatorial group theory and non-trivial results about Brownian motions, bridges and excursions in R^k.

http://arxiv.org/abs/0809.4693

3. Unsolvability of the isomorphism problem for [free abelian]-by-free groups

Gilbert Levitt

The isomorphism problem for [free abelian]-by-free groups is unsolvable.

http://arxiv.org/abs/0810.0935

4. Metric properties of higher-dimensional Thompson's groups

Jose Burillo and Sean Cleary

Higher-dimensional Thompson's groups nV are finitely presented groups described by Brin which generalize dyadic self-maps of the unit interval to dyadic self-maps of n-dimensional unit cubes. We describe some of the metric properties of higher-dimensional Thompson's groups. We give descriptions of elements based upon tree-pair diagrams and give upper and lower bounds for word length in terms of the size of the diagrams. Though these upper and lower bounds are somewhat separated, we show that there are elements realizing the lower bounds and that the fraction of elements which are close to the upper bound converges to 1, showing that the bounds are optimal and that the upper bound is generically achieved.

http://arxiv.org/abs/0810.3926

5. On finite Thurston type orderings of braid groups

Tetsuya Ito

We give an combinatorial description of finite Thurston type ordering $<_{T}$ of positive braid monoid $B_{n}^{+}$ by introducing the notion of $\C$-normal form. Our $\C$-normal form can be seen as a generalization of Burckel's normal form and Dehornoy's $\Phi$-normal form about Dehornoy's standard braid ordering. Using this description, we determine order type of well-ordered set $(B_{n},<_{T})$ for all finite Thurston type ordering $<_{T}$. Finally, we explore the relationships between our normal form and Dehornoy's $M$-normal form for locally Garside monoids.

http://arxiv.org/abs/0810.4074

6. Journal of Mathematical Cryptology 2(3): Contents

Some applications of finite geometry for secure network coding Sz. L. Fancsali and P. Ligeti

Rethinking low genus hyperelliptic Jacobian arithmetic over binary fields: interplay of field arithmetic and explicit formul? R. Avanzi, N. Th?riault, and Z. Wang

A complete characterization of the evolution of RC4 pseudo random generation algorithm Riddhipratim Basu, Shirshendu Ganguly, Subhamoy Maitra, and Goutam Paul

Advanced stochastic methods in side channel analysis on block ciphers in the presence of masking Werner Schindler

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

7. A recursive presentation for Mihailova's subgroup

O. Bogopolski and E. Ventura

We give an explicit recursive presentation for Mihailova's subgroup $M(H)$ of $F_n \times F_n$ corresponding to a finite, concise and Peiffer aspherical presentation $H=< x_1,..., x_n \mid R_1,..., R_m>$. This partially answers a question of R.I. Grigorchuk, [8, Problem 4.14]. As a corollary, we construct a finitely generated recursively presented orbit undecidable subgroup of $Aut(F_3)$.

http://arxiv.org/abs/0810.0690

8. Non-cyclic graph associated with a group

Alireza Abdollahi and A. Mohammadi Hassanabadi

We associate a graph $\mathcal{C}_G$ to a non locally cyclic group $G$ (called the non-cyclic graph of $G$) as follows: take $G\backslash Cyc(G)$ as vertex set, where $Cyc(G)=\{x\in G | < x,y> \text{is cyclic for all} y\in G\}$ is called the cyclicizer of $G$, and join two vertices if they do not generate a cyclic subgroup.

For a simple graph $\Gamma$, $w(\Gamma)$ denotes the clique number of $\Gamma$, which is the maximum size (if it exists) of a complete subgraph of $\Gamma$. In this paper we characterize groups whose non-cyclic graphs have clique numbers at most 4. We prove that a non-cyclic group $G$ is solvable whenever $w(\mathcal{C}_G)<31$ and the equality for a non-solvable group $G$ holds if and only if $G/Cyc(G)\cong A_5$ or $S_5$.

http://arxiv.org/abs/0810.0345

9. Left-Garside categories, self-distributivity, and braids

Patrick Dehornoy (LMNO)

In connection with the emerging theory of Garside categories, we develop the notions of a left-Garside category and of a locally left-Garside monoid. In this framework, the connection between the self-distributivity law LD and braids amounts to the result that a certain category associated with LD is a left-Garside category, which projects onto the standard Garside category of braids. This approach leads to a realistic program for establishing the Embedding Conjecture of [Dehornoy, Braids and Self-distributivity, Birkhauser (2000), Chap. IX].

http://arxiv.org/abs/0810.4698

10. Geometric entropy of geodesic currents on free groups

Ilya Kapovich and Tatiana Nagnibeda

A \emph{geodesic current} on a free group $F$ is an $F$-invariant measure on the set $\partial^2 F$ of pairs of distinct points of $\partial F$. The space of geodesic currents on $F$ is a natural companion of Culler-Vogtmann's Outer space $cv(F)$ and studying them together yields new information about both spaces as well as about the group $Out(F)$. The main aim of this paper is to introduce and study the notion of {\it geometric entropy} $h_T(\mu)$ of a geodesic current $\mu$ with respect to a point $T$ of $cv(F)$, which can be viewed as a length function on $F$. The geometric entropy is defined as the slowest rate of exponential decay of $\mu$-measures of bi-infinite cylinders in $F$, as the $T$-length of the word defining such a cylinder goes to infinity. We obtain an explicit formula for $h_{T'}(\mu_T)$, where $T,T'$ are arbitrary points in $cv(F)$ and where $\mu_T$ denotes a Patterson-Sullivan current corresponding to $T$. It involves the volume entropy $h(T)$ and the extremal distortion of distances in $T$ with respect to distances in $T'$. It follows that, given $T$ in the projectivized outer space $CV(F)$, $h_{T'}(\mu_T)$ as function of $T'\in CV(F)$ achieves a strict global maximum at $T'=T$. We also show that for any $T\in cv(F)$ and any geodesic current $\mu$ on $F$, $h_T(\mu)\le h(T)$, where the equality is realized when $\mu=\mu_T$. For points $T\in cv(F)$ with simplicial metric (where all edges have length one), we relate the geometric entropy of a current and the measure-theoretic entropy.

http://arxiv.org/abs/0810.4728

11. On Systems of Equations over Free Partially Commutative Groups

Montserrat Casals-Ruiz and Ilya Kazachkov

Using an analogue of Makanin-Razborov diagrams, we give an effective description of the solution set of systems of equations over a partially commutative group (right-angled Artin group) $G$. Equivalently, we give a parametrisation of $Hom(H, G)$, where $H$ is a finitely generated group.

http://arxiv.org/abs/0810.4867

12. A variant of Wiener's attack on RSA

Andrej Dujella

Wiener's attack is a well-known polynomial-time attack on a RSA cryptosystem with small secret decryption exponent d, which works if d<n^{0.25}, where n=pq is the modulus of the cryptosystem. Namely, in that case, d is the denominator of some convergent p_m/q_m of the continued fraction expansion of e/n, and therefore d can be computed efficiently from the public key (n,e).

There are several extensions of Wiener's attack that allow the RSA cryptosystem to be broken when d is a few bits longer than n^{0.25}. They all have the run-time complexity (at least) O(D^2), where d=Dn^{0.25}. Here we propose a new variant of Wiener's attack, which uses results on Diophantine approximations of the form |\alpha - p/q| < c/q^2, and "meet-in-the-middle" variant for testing the candidates (of the form rq_{m+1} + sq_m) for the secret exponent. This decreases the run-time complexity of the attack to O(D log(D)) (with the space complexity O(D)).

http://arxiv.org/abs/0811.0063

13. On right-angled Artin groups without surface subgroups

Sang-hyun Kim

We study the class $\mathcal N$ of graphs, the right-angled Artin groups defined on which do not contain surface subgroups. We prove that a presumably smaller class $\mathcal N'$ is closed under amalgamating along complete subgraphs, and also under adding bisimplicial edges. It follows that chordal graphs and chordal bipartite graphs belong to $\mathcal N'$.

http://arxiv.org/abs/0811.1946

14. Mather invariants in groups of piecewise-linear homeomorphisms

Francesco Matucci

We describe the relation between two characterizations of conjugacy in groups of piecewise-linear homeomorphisms, discovered by Brin and Squier in \cite{brin2} and Kassabov and Matucci in \cite{kama}. Thanks to the interplay between the techniques, we produce a simplified point of view of conjugacy that allows ua to easily recover centralizers and lends itself to generalization.

http://arxiv.org/abs/0811.2370

15. Tree-pair Diagrams, the Word Problem, and the Metric for Generalizations of Thompson's Group F on more than One Integer

Claire Wladis

We consider Thompson's group F(n_1,...,n_k), where n_1,...,n_k are in the set {2,3,4,...} and k is a natural number. We highlight several differences between the cases k=1 and k>1, including the fact that minimal tree-pair diagram representatives of elements, in the case k>1, may not be unique. We establish how to find minimal tree-pair diagram representatives of elements of F(n_1,...,n_k) in the case k>1, and we prove several theorems describing the equivalence of trees and tree-pair diagrams. We introduce a unique normal form for elements of F(n_1,...,n_k) (with respect to the standard infinite generating set developed by Melanie Stein) which provides a solution to the word problem, and we give sharp upper and lower bounds on the metric (i.e. geodesic distance in the Cayley graph) with respect to the standard finite generating set.

http://arxiv.org/abs/0811.3036

16. Every braid admits a short sigma-definite representative

Jean Fromentin

A result by Dehornoy (1992) says that every nontrivial braid admits a sigma-definite word representative, defined as a braid word in which the generator sigma_i with maximal index i appears with exponents that are all positive, or all negative. This is the ground result for ordering braids. In this paper, we enhance this result and prove that every braid admits a sigma-definite word representative that, in addition, is quasi-geodesic. This establishes a longstanding conjecture. Our proof uses the dual braid monoid and a new normal form called the rotating normal form.

http://arxiv.org/abs/0811.3902

17. Compressed word problems in HNN-extensions and amalgamated products

Niko Haubold and Markus Lohrey

It is shown that the compressed word problem for an HNN-extension with base group H and finite associated subgroups is polynomial time Turing-reducible to the compressed word problem for H. An analogous result for amalgamated free products is shown as well.

http://arxiv.org/abs/0811.3303

18. Reducing conjugacy in the full diffeomorphism group of R to conjugacy in the subgroup of orientation-preserving maps

Anthony G. O'Farrell and Maria Roginskaya

Let $\Diffeo=\Diffeo(\R)$ denote the group of infinitely-differentiable diffeomorphisms of the real line $\R$, under the operation of composition, and let $\Diffeo^+$ be the subgroup of diffeomorphisms of degree +1, i.e. orientation-preserving diffeomorphisms. We show how to reduce the problem of determining whether or not two given elements $f,g\in \Diffeo$ are conjugate in $\Diffeo$ to associated conjugacy problems in the subgroup $\Diffeo^+$. The main result concerns the case when $f$ and $g$ have degree -1, and specifies (in an explicit and verifiable way) precisely what must be added to the assumption that their (compositional) squares are conjugate in $\Diffeo^+$, in order to ensure that $f$ is conjugated to $g$ by an element of $\Diffeo^+$. The methods involve formal power series, and results of Kopell on centralisers in the diffeomorphism group of a half-open interval.

http://arxiv.org/abs/0811.3370

19. Strongly Contracting Geodesics in Outer Space

Yael Algom-Kfir

We study the Lipschitz metric on Outer Space and prove that fully irreducible elements of Out(F_n) act by hyperbolic isometries with axes which are strongly contracting. As a corollary, we prove that the axes of fully irreducible automorphisms in the Cayley graph of Out(F_n) are stable, meaning that a quasi-geodesic with endpoints on the axis stays within a bounded distance from the axis.

http://arxiv.org/abs/0812.1555

20. Two-generator subgroups of the pure braid group

Christopher J Leininger and Dan Margalit

We show that any two elements of the pure braid group either commute or generate a free group, settling a question of Luis Paris. Our proof involves the theory of 3-manifolds and the theory of group actions on trees.

http://arxiv.org/abs/0812.1783

21. Phase transitions in infinitely generated groups, and related problems in additive number theory

Melvyn B. Nathanson

Let A be an infinite set of generators for a group G, and let L_A(r) denote the number of elements of G whose word length with respect to A is exactly r. The purpose of this note is to determine all growth functions L_A(r) associated to infinite generating sets for groups, and to describe a phase transition phenomenon associated with infinite generating sets. A list of open problems is also.included.

http://arxiv.org/abs/0811.3990

22. "Set-theoretical" solutions of the quantum Yang-Baxter equation and a class of Garside groups

Fabienne Chouraqui

We establish a one-to-one correspondence between structure groups of non-degenerate, involutive and braided "set-theoretical" solutions of the quantum Yang-Baxter equation and Garside groups with a certain presentation. Moreover, we show that the solution is indecomposable if and only if its structure group is a $\Delta-$pure Garside group.

http://arxiv.org/abs/0811.4064

23. New Permutation Representations of the Braid Group

Amiel Ferman, Tahl Nowik, Robert Schwartz, Mina Teicher

We give a new infinite family of group homomorphisms from the braid group B_k to the symmetric group S_{mk} for all k and m \geq 2. Most known permutation representations of braids are included in this family. We prove that the homomorphisms in this family are non-cyclic and transitive. For any divisor l of m, 1\leq l < m, we prove in particular that if \frac{m}{l} is odd then there are 1 + \frac{m}{l} non-conjugate homomorphisms included in our family.

We define a certain natural restriction on homomorphisms B_k to S_n, common to all homomorphisms in our family, which we term 'good', and of which there are two types.

We prove that all good homomorphisms B_k to S_{mk} of type 1 are included in the infinite family of homomorphisms we gave. For m=3, we prove that all good homomorphisms B_k to S_{3k} of type 2 are also included in this family.

Finally, we refute a conjecture made by Matei and Suciu regarding permutation representations of braids and give an updated conjecture.

http://arxiv.org/abs/0811.4204

24. New Presentations of Thompson's Groups and Applications

Uffe Haagerup and Gabriel Picioroaga

We find new presentations for the Thompson's groups $F$, the derived group $F^{'}$ and the intermediate group $D$. These presentations have a common ground in that their relators are the same and only the generating sets differ. As an application of these presentations we extract the following consequences: the cost of the group $F^{'}$ is 1 hence the cost cannot decide the (non)amenability question of $F$; the $II_1$ factor $L(F^{'})$ is inner asymptotically abelian and the reduced $C^*$-algebra of $F$ is not residually finite dimensional.

http://arxiv.org/abs/0812.0037

25. The R- and L-orders of the Thompson-Higman monoid M_{k,1} and their complexity

Jean-Camille Birget

We study the monoid generalization M_{k,1} of the Thompson-Higman groups, and we characterize the R- and the L-preorder of M_{k,1}. Although M_{k,1} has only one non-zero J-class and k-1 non-zero D-classes, the R- and the L-preorder are complicated; in particular, <_R is dense (even within an L-class), and <_L is dense (even within an R-class).

We study the computational complexity of the R- and the L-preorder. When inputs are given by words over a finite generating set of M_{k,1}, the R- and the L-preorder decision problems are in P. The main result of the paper is that over a "circuit-like" generating set, the R-preorder decision problem of M_{k,1} is Pi_2^P-complete, whereas the L-preorder decision problem is coNP-complete. We also prove related results about circuits: For combinational circuits, the surjectiveness problem is Pi_2^P-complete, whereas the injectiveness problem is coNP-complete.

http://arxiv.org/abs/0812.4434

26. Proving finitely presented groups are large by computer

J.O.Button

We present a theoretical algorithm which, given any finite presentation of a group as input, will terminate with answer yes if and only if the group is large. We then implement a practical version of this algorithm using Magma and apply it to a range of presentations. Our main focus is on 2-generator 1-relator presentations where we have a complete picture of largeness if the relator has exponent sum zero in one generator and word length at most 12, as well as when the relator is in the commutator subgroup and has word length at most 18. Indeed all but a tiny number of presentations define large groups. Finally we look at fundamental groups of closed hyperbolic 3-manifolds, where the algorithm readily determines that a quarter of the groups in the Snappea closed census are large.

http://arxiv.org/abs/0812.4264

27. An Effective Lower Bound for Group Complexity of Finite Semigroups and Automata

Karsten Henckell, John Rhodes and Benjamin Steinberg

The question of computing the group complexity of finite semigroups and automata was first posed in K. Krohn and J. Rhodes, \textit{Complexity of finite semigroups}, Annals of Mathematics (2) \textbf{88} (1968), 128--160, motivated by the Prime Decomposition Theorem of K. Krohn and J. Rhodes, \textit{Algebraic theory of machines, {I}: {P}rime decomposition theorem for finite semigroups and machines}, Transactions of the American Mathematical Society \textbf{116} (1965), 450--464. Here we provide an effective lower bound for group complexity.

http://arxiv.org/abs/0812.3499

---

END OF ISSUE