Algebraic and algorithmic aspects of zm × fn: fixed subgroups and quantification of inertia

• Autores: Mallika Roy
• Directores de la Tesis: Enric Ventura i Capell (dir. tes.)
• Lectura: En la Universitat Politècnica de Catalunya (UPC) ( España ) en 2020
• Idioma: español
• Tribunal Calificador de la Tesis: Pascal Weil (presid.) , Natalia Castellana i Vila (secret.) , Laura Ciobanu (voc.)
• Texto completo no disponible (Saber más ...)
• Resumen

  • This work is based on the family of groups Z^m x F_n, namely free-abelian times free groups, direct products of finitely many copies of Z and a finitely generated free group F_n. These are a special type of right-angled Artin groups. In this work we use general combinatorics, one dimensional geometry and algebraic techniques to play with elements of Z^m x F_n to solve some algorithmic problems concerning ranks of the subgroups, automorphisms and its fixed point subgroups, subgroup intersection problem heading towards a cryptography application using the group Z^m x F_n. The core methodology of this work involves the use of Stallings graph to work with subgroups of F_n and to deal with the abelian part we use linear algebra, systems of equations, Smith normal form of integral matrices, etc. This thesis is to study algorithmic problems of Z^m x F_n, a natural extension of free groups and a first step towards further generalization into another two main directions: semi-direct products, and partially commutative groups. The three principal projects of this thesis are the following:

    (1) In the lattice of subgroups of a free group, the rank function is not monotone with respect to inclusion (i.e., H<=K does not imply r(H)<=r(K)). This makes it interesting to define and study relaxed versions for this monotonic property. Based on the classical definitions of compressed and inert subgroups, we introduce the concepts of degrees of compression and inertia (dc and di) of a finitely generated subgroup H of a given group G, as an attempt to quantify how close (or far) is H from being compressed and inert and so, from satisfying the aforementioned monotonic property. In the case of Z^m x F_n, we show that the dc is algorithmically computable, we give an upper bound for the di, and relate both degrees with those of the projection H\pi to the free part. With some extra assumptions over the supremum involved in the definition of di, we define another notion called restricted degree of inertia. In the case of Z^m x F_n, beyond giving the upper bound, we are able to give an equality formula for the restricted degree of inertia.

    (2) The study of the properties of fixed point subgroups by automorphisms of free groups F_n is much more complicated but they are well studied in the literature. The classical result by Dyer–Scott about fixed subgroups of finite order automorphisms of F_n being free factors of F_n is no longer true in Z^m x F_n, gives us the feeling that fixed point subgroups in Z^m x F_n have more degenerated behaviour than in the free group. Within this more general context, we prove a relaxed version in the spirit of Bestvina-Handel Theorem: the rank of fixed subgroups of finite order automorphisms is uniformly bounded in terms of n and m. For any given automorphism it is a very natural question to ask for the elements which are fixed by that automorphism. The dual problem to this is, for a given finitely generated subgroup H, to ask whether there exists a finite collection of automorphisms which fix exactly that particular subgroup H point-wise. In this text we also solve this dual problem and give an algorithm to compute auto-fixed closures of finitely generated subgroups of Z^m x F_n.

    (3) In this project we develop a secret-sharing scheme taking advantage of the fact that Z^m x F_n does not satisfy the Howson property, i.e., it contains finitely generated subgroups whose intersection is not finitely generated. Concretely, the shares for the k players are going to be k finitely generated subgroups of Z^m x F_n such that every intersection of shares is not finitely generated, except the full intersection, which is taken as the secret. This way we significantly increase the difficulty for an illegal coalition of players to extract any practical additional information about the secret. We prove that for any integer k, one can effectively built such a family of subgroups of and to give an effective algorithm to compute the secret.