CGC Bulletin 21
Contents
- On some block ciphers and imprimitive groups
- Automata generating free products of groups of order 2
- Constructing arithmetic subgroups of unipotent groups
- Remnant properties in Nielsen coincidence theory
- Some Remarks on the Braided Thompson Group BV
- Noncommutative independence from the braid group B_infinity
- Interpretation of the Arithmetic in certain groups of piecewise affine permutations of an interval
- The Word and Geodesic Problems in Free Solvable Groups
- Interpretation of the Arithmetic in certain groups of piecewise affine permutations of an interval
- Survey on geometric group theory
- Algorithms and Classification in Groups of Piecewise-Linear Homeomorphisms
- Infinitely generated free nilpotent groups: completeness of the automorphism groups
- The automorphism groups of relatively free groups of infinite rank
- Non-degeneracy of Pollard Rho Collisions
- The cyclic sliding operation in Garside groups
Boaz Tsaban
Bulletin's webpage: http://www.cs.biu.ac.il/~tsaban/CGC/cgc.html
1. On some block ciphers and imprimitive groups
A. Caranti, F. Dalla Volta, M. Sala
The group generated by the round functions of a block ciphers is a widely investigated problem. We identify a large class of block ciphers for which such group is easily guaranteed to be primitive. Our class includes the AES and the SERPENT.
http://arxiv.org/abs/0806.4135
2. Automata generating free products of groups of order 2
Dmytro Savchuk, Yaroslav Vorobets
We construct a family of automata with n states, n>3, acting on a rooted binary tree that generate the free products of cyclic groups of order 2.
http://arxiv.org/abs/0806.4801
3. Constructing arithmetic subgroups of unipotent groups
Willem de Graaf and Andrea Pavan
Let G be a unipotent algebraic subgroup of some GL_m(C) defined over Q. We describe an algorithm for finding a finite set of generators of the subgroup G(Z) = G \cap GL_m(Z). This is based on a new proof of the result (in more general form due to Borel and Harish-Chandra) that such a finite generating set exists.
http://arxiv.org/abs/0806.4916
4. Remnant properties in Nielsen coincidence theory
P. Christopher Staecker
We give an extension to coincidence theory of some key ideas from Nielsen fixed point theory involving remnant properties of free group homomorphisms. In particular we extend Wagner's theorem for computing Reidemeister classes for Wagner characteristic homomorphisms, which allows us to compute doubly twisted conjugacy classes in many cases. We also extend Kim's method for homomorphisms with bounded solution length, which leads to an algorithm for computation of the coincidence Nielsen number for mappings on surfaces with boundary whose induced homomorphisms on the fundamental group satisfy a natural remnant condition.
http://arxiv.org/abs/0806.4687
5. Some Remarks on the Braided Thompson Group BV
Kai-Uwe Bux, Dmitriy Sonkin
Matthew Brin and Patrick Dehornoy independently discovered a braided version BV of Thompson's group V. In this paper, we discuss some properties of BV that might make the group interesting for group based cryptography. In particular, we show that BV does not admit a non-trivial linear representation.
http://arxiv.org/abs/0807.0061
6. Noncommutative independence from the braid group $B_\infty$
Rolf Gohm, Claus K\"ostler
We introduce `braidability' as a new symmetry for (infinite) sequences of noncommutative random variables related to representations of the braid group $B_\infty$. It provides an extension of exchangeability which is tied to the symmetric group $S_\infty$. Our key result is that braidability implies spreadability and thus conditional independence, according to the noncommutative extended de Finetti theorem (of C. K\"{o}stler). This endows the braid groups $B_n$ with a new intrinsic (quantum) probabilistic interpretation. We underline this interpretation by a braided extension of the Hewitt-Savage Zero-One Law.
Furthermore we use the concept of product representations of endomorphisms (of R. Gohm) with respect to certain Galois type towers of fixed point algebras to show that braidability produces triangular towers of commuting squares and noncommutative Bernoulli shifts. As a specific case we study the left regular representation of $B_\infty$ and the irreducible subfactor with infinite Jones index in the non-hyperfinite $II_1$-factor $L(B_\infty)$ related to it. Our investigations reveal a new presentation of the braid group $B_\infty$, the `square root of free generator presentation' $F_\infty^{1/2}$. These new generators give rise to braidability while the squares of them yield a free family. Hence our results provide another facet of the strong connection between subfactors and free probability theory and we speculate about braidability as an extension of (amalgamated) freeness on the combinatorial level.
http://arxiv.org/abs/0806.3691
7. Interpretation of the Arithmetic in certain groups of piecewise affine permutations of an interval
Tuna Alt{\i}nel, Alexey Muranov
The Arithmetic is interpreted in all the groups of Richard Thompson and Graham Higman, as well as in other groups of piecewise affine permutations of an interval which generalize the groups of Thompson and Higman. In particular, the elementary theories of all these groups are undecidable. Moreover, Thompson's group $F$ and some of its generalizations interpret the Arithmetic without parameters.
http://arxiv.org/abs/0807.1079
8. The Word and Geodesic Problems in Free Solvable Groups
A. Myasnikov, V. Roman'kov, A. Ushakov, A.Vershik
We study the computational complexity of the Word Problem (WP) in free solvable groups $S_{r,d}$, where $r \geq 2$ is the rank and $d \geq 2$ 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 the polynomial grows together with $d$, so the uniform algorithm is not polynomial in $d$. In this paper we show that WP has time complexity $O(r n \log_2 n)$ in $S_{r,2}$, and $O(n^3 r d)$ in $S_{r,d}$ for $d \geq 3$. However, it turns out, that a seemingly close problem of computing the geodesic length of elements in $S_{r,2}$ is $NP$-complete. We prove also that one can compute Fox derivatives of elements from $S_{r,d}$ in time $O(n^3 r d)$, in particular one can use efficiently the Magnus embedding in computations with free solvable groups. Our approach is based on such classical tools as the Magnus embedding and Fox calculus, as well as, on a relatively new geometric ideas, in particular, we establish a direct link between Fox derivatives and geometric flows on Cayley graphs.
http://arxiv.org/abs/0807.1032
9. Interpretation of the Arithmetic in certain groups of piecewise affine permutations of an interval
Tuna Alt{\i}nel, Alexey Muranov
The Arithmetic is interpreted in all the groups of Richard Thompson and Graham Higman, as well as in other groups of piecewise affine permutations of an interval which generalize the groups of Thompson and Higman. In particular, the elementary theories of all these groups are undecidable. Moreover, Thompson's group $F$ and some of its generalizations interpret the Arithmetic without parameters.
http://arxiv.org/abs/0807.1079
10. Survey on geometric group theory
Wolfgang Lueck
This article is a survey article on geometric group theory from the point of view of a non-expert who likes geometric group theory and uses it in his own research. The sections are: classical examples, basics about quasiisometry, properties and invariants of groups invariant under quasiisometry, rigidity, hyperbolic spaces and CAT(k)-spaces, the boundary of a hyperbolic space, hyperbolic groups, CAT(0)-groups, classifying spaces for proper actions, measurable group theory, some open problems.
http://arxiv.org/abs/0806.3771
11. Algorithms and Classification in Groups of Piecewise-Linear Homeomorphisms
Francesco Matucci
This manuscript represents the author's PhD dissertation thesis.The first part studies decision problems in Thompson's groups F,T,V and some generalizations. The simultaneous conjugacy problem is determined to be solvable for Thompson's group F and suitable larger groups of piecewise-linear homeomorphisms of the unit interval. We determine algorithms to compute roots and centralizers in these groups and to detect periodic points and their behavior by looking at a particular diagram associated to an element. In the second part, we describe the structure of subgroups of the group of all homeomorphisms of the unit circle, with the additional requirement that they contain no non-abelian free subgroup. It is shown that in this setting the rotation number map is a group homomorphism. We give a classification of such subgroups as subgroups of certain wreath products and we show that such subgroups can exist by building examples. Similar techniques are then used to compute centralizers in these groups.
http://arxiv.org/abs/0807.2871
12. Infinitely generated free nilpotent groups: completeness of the automorphism groups
Vladimir Tolstykh
Baumslag conjectured in the 1970s that the automorphism tower of a finitely generated free nilpotent group must be very short.
Let F_{n,c} denote a free nilpotent group of finite rank n at least two and of nilpotency class c at least two. In 1976 Dyer and Formanek proved that the automorphism group of F_{n,2} is even complete (and hence the height of the aumorphism tower of F_{n,2} is two) provided that n is not three; in the case when n=3, the height of the automorphism tower of F_{n,2} is three. The author proved in 2001 that the automorphism group of any infinitely generated free nilpotent of class two is complete.
In his Ph. D. thesis (2003) Kassabov found an upper bound u(n,c) (a natural number) for the height of the automorphism tower of F_{n,c} in terms of n and c, thereby finally proving Baumslag's conjecture. By analyzing the function u(n,c), one can conclude that if c is small compared to n, then the height of the automorphism tower of F_{n,c} is at most three.
The main result of the present paper states that the automorphism group of any infinitely generated free nilpotent group of nilpotency class at least two is complete. Thus the automorphism tower of any free nilpotent group terminates after finitely many steps.
http://arxiv.org/abs/0807.4341 , 26kb)
13. The automorphism groups of relatively free groups of infinite rank
Vladimir Tolstykh
A survey article that presents some recent algebraic and model-theoretic results on the automorphism groups of relatively free groups of infinite rank. The topics include topological aspects, generating sets, descripition of automorpisms and expressive power of the first-order theories.
http://arxiv.org/abs/0807.4343
14. Non-degeneracy of Pollard Rho Collisions
Stephen D. Miller and Ramarathnam Venkatesan
The Pollard Rho algorithm is a widely used algorithm for solving discrete logarithms on general cyclic groups, including elliptic curves. Recently the first nontrivial runtime estimates were provided for it, culminating in a sharp O(sqrt(n)) bound for the collision time on a cyclic group of order n. In this paper we show that for n satisfying a mild arithmetic condition, the collisions guaranteed by these results are nondegenerate with high probability: that is, the Pollard Rho algorithm successfully finds the discrete logarithm.
http://arxiv.org/abs/0808.0469
15. The cyclic sliding operation in Garside groups
Volker Gebhardt and Juan Gonz\'alez-Meneses
We present a new operation to be performed on elements in a Garside group, called cyclic sliding, which is introduced to replace the well known cycling and decycling operations. Cyclic sliding appears to be a more natural choice, simplifying the algorithms concerning conjugacy in Garside groups and having nicer theoretical properties. We show, in particular, that if a super summit element has conjugates which are 'rigid' (that is, which have a certain particularly simple structure), then the optimal way of obtaining such a rigid conjugate through conjugation by positive elements is given by iterated cyclic sliding.
http://arxiv.org/abs/0808.1430
---
END OF ISSUE
