With the advent of quantum computers, the security of number-theoretic cryptography has been compromised. Consequently, new cryptosystems have been suggested in the field of non-commutative group theory. In this thesis, we provide all the necessary background to understand and work with the Artin groups. We then show that Artin groups of finite type and Artin groups of large type possess an easily-computable normal form by explicitly writing the algorithms. This solution to the word problem makes these groups candidates to be cryptographic platforms. Finally, we present some combinatorial problems that can be used in group-based cryptography and we conjecture, through empirical evidence, that the conjugacy problem in Artin groups of large type is not a hard problem.

With the advent of quantum computers, the security of number-theoretic cryptography has been compromised. Consequently, new cryptosystems have been suggested in the field of non-commutative group theory. In this thesis, we provide all the necessary background to understand and work with the Artin groups. We then show that Artin groups of finite type and Artin groups of large type possess an easily-computable normal form by explicitly writing the algorithms. This solution to the word problem makes these groups candidates to be cryptographic platforms. Finally, we present some combinatorial problems that can be used in group-based cryptography and we conjecture, through empirical evidence, that the conjugacy problem in Artin groups of large type is not a hard problem.

With the advent of quantum computers, the security of number-theoretic cryptography has been compromised. Consequently, new cryptosystems have been suggested in the field of non-commutative group theory. In this thesis, we provide all the necessary background to understand and work with the Artin groups. We then show that Artin groups of finite type and Artin groups of large type possess an easily-computable normal form by explicitly writing the algorithms. This solution to the word problem makes these groups candidates to be cryptographic platforms. Finally, we present some combinatorial problems that can be used in group-based cryptography and we conjecture, through empirical evidence, that the conjugacy problem in Artin groups of large type is not a hard problem.

No description available.

Nous pre´sentons une condition sur les groupes de Garside que nous appelons la structure de Dehornoy. Une ite´ration d’une telle structure conduit a` une ordre a` gauche sur le groupe. Nous montrons des conditions pour qu’un groupe de Garside admet une structure de Dehornoy, et nous appliquons ce crite`re pour prouver que les groupes d’Artin de type A et I2(m), m ≥ 4, ont des structures de Dehornoy. Nous montrons que les ordres a` gauche sur les groupes d’Artin de type A obtenus a` partir de leurs structures de Dehornoy sont les ordres de Dehornoy. Dans le cas des groupes d’Artin du type I2(m), m ≥ 4, nous montrons que les ordres a` gauche de´rive´es de leurs structures de Dehornoy co¨ıncident avec les ordres obtenus a` partir des plongements de ces groupes dans les groupes de tresses. / We introduce a condition on Garside groups that we call Dehornoy structure. An iteration of such a structure leads to a left order on the group. We show conditions for a Garside group to admit a Dehornoy structure, and we apply these criteria to prove that the Artin groups of type A and I2(m), m ≥ 4, have Dehornoy structures. We show that the left orders on the Artin groups of type A obtained from their Dehornoy structures are the Dehornoy orders. In the case of the Artin groups of type I2(m), m ≥ 4, we show that the left orders derived from their Dehornoy structures coincide with the orders obtained from embeddings of the groups into braid groups.

Orientador: Dessislava Hristova Kochloukova / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-20T20:07:55Z (GMT). No. of bitstreams: 1 Almeida_KisnneyEmilianode_D.pdf: 833428 bytes, checksum: 3f425f5150e4ce7915c42d59f2a772be (MD5) Previous issue date: 2012 / Resumo: A teoria de ?-invariantes surgiu do trabalho de Bieri e Strebel, que definiram o primeiro ?-invariante, apenas para grupos metabelianos, e o usaram para descrever os grupos metabelianos finitamente gerados [BiSt]. Posteriormente, foram definidos os ?m-invariantes homotópicos e homológicos de grupos finitamente gerados arbitrários [BiNSt]. Estes são certos subconjuntos da esfera de caracteres profundamente relacionados às propriedades de finitude Fm e FPm, respectivamente. Os grupos de Artin formam uma grande classe de grupos, cada um associado a um grafo rotulado, que inclui algumas subclasses importantes, como "Braid groups" e "Rightangled Artin groups"...Observação: O resumo, na íntegra, poderá ser visualizado no texto completo da tese digital / Abstract: The ?-invariants theory arose from the work of Bieri and Strebel, who defined the first ?-invariant, for metabelian groups only, and used it to describe the finitely presented metabelian groups [BiSt]. Later on, the homotopical and homological ?m-invariants of arbitrary finitely generated groups were defined [BiRe]. These are certain subsets of the sphere of characters deeply related to the finiteness properties Fm and FPm, respectively. The Artin groups form a large class of groups, each one associated to a labeled graph, that includes some important subclasses, as Braid groups and Right-angled Artin groups...Note: The complete abstract is available with the full electronic document / Doutorado / Matematica / Doutor em Matemática

The objects of study in this thesis are automorphism groups of free and right-angled Artin groups. Right-angled Artin groups are defined by a presentation where the only relations are commutators of the generating elements. When there are no relations the right-angled-Artin group is a free group and if we take all possible relations we have a free abelian group. We show that if no finite index subgroup of a group $G$ contains a normal subgroup that maps onto $mathbb{Z}$, then every homomorphism from $G$ to the outer automorphism group of a free group has finite image. The above criterion is satisfied by SL$_m(mathbb{Z})$ for $m geq 3$ and, more generally, all irreducible lattices in higher-rank, semisimple Lie groups with finite centre. Given a right-angled Artin group $A_Gamma$ we find an integer $n$, which may be easily read off from the presentation of $A_G$, such that if $m geq 3$ then SL$_m(mathbb{Z})$ is a subgroup of the outer automorphism group of $A_Gamma$ if and only if $m leq n$. More generally, we find criteria to prevent a group from having a homomorphism to the outer automorphism group of $A_Gamma$ with infinite image, and apply this to a large number of irreducible lattices as above. We study the subgroup $IA(A_Gamma)$ of $Aut(A_Gamma)$ that acts trivially on the abelianisation of $A_Gamma$. We show that $IA(A_Gamma)$ is residually torsion-free nilpotent and describe its abelianisation. This is complemented by a survey of previous results concerning the lower central series of $A_Gamma$. One of the commonly used generating sets of $Aut(F_n)$ is the set of Whitehead automorphisms. We describe a geometric method for decomposing an element of $Aut(F_n)$ as a product of Whitehead automorphisms via Stallings' folds. We finish with a brief discussion of the action of $Out(F_n)$ on Culler and Vogtmann's Outer Space. In particular we describe translation lengths of elements with regards to the `non-symmetric Lipschitz metric' on Outer Space.

My dissertation focuses on the existence of metrics of non-positive curvature for the simplicial complexes constructed recently by Tom Brady and Daan Krammer for the braid groups and other Artin groups of finite type. In particular, for each Artin group of finite type, there is a recently constructed finite simplicial Eilenberg-Mac Lane space known as its Brady-Krammer complex. The Brady-Krammer complexes are highly symmetric objects. Prior work on the relationship between the Brady-Krammer complexes and the theory of CAT(0)spaces has produced some positive results in low-dimensions. More specifically, the Brady-Krammer complexes of dimension at most 3 have been shown to support piecewise Euclidean metrics of non-positive curvature. Similarly, the 4dimensional Brady-Krammer complexes of type A4 and type B4 also support such metrics. In every instance, the metrics assigned respect all of the symmetries alluded to above. The main results of my dissertation show that this pattern does not extend to the Brady-Krammer complexes of type F4 and D4. These are the first negative results known about the curvature of these Brady-Krammer complexes. The proofs of my main theorems involve a combination of combinatorial results and computer calculations. These negative results are particularly striking since Ruth Charney, John Meier and Kim Whittlesey have shown that a particular complex closely related to each Brady-Krammer complex admits an asymmetric metric satisfying a weak version of non-positive curvature. Thus, one corollary of my results is that the weak asymmetric version of a CAT(0) metric (initially defined by Mladen Bestvina) is strictly weaker than the traditional version.

My dissertation focuses on the existence of metrics of non-positive curvature for the simplicial complexes constructed recently by Tom Brady and Daan Krammer for the braid groups and other Artin groups of finite type. In particular, for each Artin group of finite type, there is a recently constructed finite simplicial Eilenberg-Mac Lane space known as its Brady-Krammer complex. The Brady-Krammer complexes are highly symmetric objects. Prior work on the relationship between the Brady-Krammer complexes and the theory of CAT(0)spaces has produced some positive results in low-dimensions. More specifically, the Brady-Krammer complexes of dimension at most 3 have been shown to support piecewise Euclidean metrics of non-positive curvature. Similarly, the 4dimensional Brady-Krammer complexes of type A4 and type B4 also support such metrics. In every instance, the metrics assigned respect all of the symmetries alluded to above. The main results of my dissertation show that this pattern does not extend to the Brady-Krammer complexes of type F4 and D4. These are the first negative results known about the curvature of these Brady-Krammer complexes. The proofs of my main theorems involve a combination of combinatorial results and computer calculations. These negative results are particularly striking since Ruth Charney, John Meier and Kim Whittlesey have shown that a particular complex closely related to each Brady-Krammer complex admits an asymmetric metric satisfying a weak version of non-positive curvature. Thus, one corollary of my results is that the weak asymmetric version of a CAT(0) metric (initially defined by Mladen Bestvina) is strictly weaker than the traditional version.

Dans la première partie de cette thèse on étudiera la conjecture de généricité: dans le graphe de Cayley du groupe modulaire d'une surface fermée on regarde une boule centrée à l'identité et on s'intéresse à la proportion de sommets pseudo-Anosov dans cette boule. La conjecture de généricité affirme que cette proportion doit tendre vers 1 quand le rayon de la boule tend vers l'infini. On montre qu'elle est bornée inférieurement par un nombre strictement positif et on montre des résultats similaires pour une grande classe de sous-groupes du groupe modulaire. On présente aussi des résultats analogues pour des groupes d'Artin-Tits de type sphérique, en sachant que dans ce cas, être pseudo-Anosov est analogue à agir loxodromiquement sur un complexe delta-hyperbolique convenable. Dans la deuxième partie on donne des résultats sur les sous-groupes paraboliques des groupes d'Artin-Tits de type sphérique: le standardisateur minimal d'une courbe dans le disque troué est la tresse minimale positive qui la fait devenir ronde. On construit un algorithme pour le calculer d'une façon géométrique. Ensuite, on généralise le problème pour les groupes d'Artin-Tits de type sphérique. On montre aussi que l'intersection de deux sous-groupes paraboliques est un sous-groupe parabolique et que l'ensemble de sous-groupes paraboliques est un treillis par rapport à l'inclusion. Finalement, on définit le complexe simplicial des sous-groupes paraboliques irréductibles, et on le propose comme l'analogue du complexe de courbes. / In the first part of this thesis we study the genericity conjecture: In the Cayley graph of the mapping class group of a closed surface we look at a ball of large radius centered on the identity vertex, and at the proportion of pseudo-Anosov vertices among the vertices in this ball. The genericity conjecture states that this proportion should tend to one as the radius tends to infinity. We prove that it stays bounded away from zero and prove similar results for a large class of subgroups of the mapping class group. We also present analogous results for Artin--Tits groups of spherical type, knowing that in this case being pseudo-Anosov is analogous to being a loxodromically acting element. In the second part we provide results about parabolic subgroups of Artin-Tits groups of spherical type: The minimal standardizer of a curve on a punctured disk is the minimal positive braid that transforms it into a round curve. We give an algorithm to compute it in a geometrical way. Then, we generalize this problem algebraically to parabolic subgroups of Artin--Tits groups of spherical type. We also show that the intersection of two parabolic subgroups is a parabolic subgroup and that the set of parabolic subgroups forms a lattice with respect to inclusion. Finally, we define the simplicial complex of irreducible parabolic subgroups, and we propose it as the analogue of the curve complex for mapping class groups.