Algebraic and algorithmic aspects of Zm × Fn : fixed subgroups and quantification of inertia

Abstract

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.

Aquest treball versa sobre la família de grups ZM x Fn, és a dir els grups lliure-abelians per lliure, productes directes d'un nombre finit de còpies de Z i d'un grup lliure Fn. Són un tipus especial de grups right-angled Artin. En aquest treball usem eines de combinatòria, geometria 1-dimensional, i tècniques algebraiques per a jugar amb els elements de ZMm x Fn ti resoldre alguns problemes algorítmics sobre els rangs de subgrups, sobre automorfismes i els seus subgrups de punts fixos, el problema de la intersecció de subgroups i fins i tot una aplicació a la criptografia usant el grup ZM x F_n. La part metodològica principal d'aquest treball involucra l'ús dels grafs de Stallings per a treballar amb els subgrups de Fn; i per a tractar amb la part abeliana usem l'àlgebra lineal estàndard, els sistemes d'equacions i la forma normal de Smith de les matrius enteres. En aquesta tesi estudiem problemes algorísmics de ZMm x Fn, una extensió natural dels grups lliures i un primer pas cap a majors generalitzacions en dues direccions principals: productes semidirectes, i grups parcialment commutatius. Els tres resultats principals d'aquesta tesi són els següents: (1) En el reticle de subgrups del grup lliure la funció de rang no és monòtona respecte la inclusió (i.e., H<=K no implica r(H)<=r(K)). Això fa que sigui interessant definir i estudiar versions relaxades d'aquesta propietat de monotomia. Basades en les definicions clàssiques de compressió i inèrcia de subgrups, introduïm els conceptes de grau de compressió i grau d'inèrcia (dc i di, respectivament) d'un subgrup finitament generat H d'un grup donat G, com un intent de quantificar quan a prop o lluny és H de ser comprimit o inert, és a dir de satisfer l'esmentada propietat de monotonia. En el cas de ZM x Fn, demostrem que el dc és algorítmicament calculable, donem una fita superior per al di, i relacionem aquests dos graus amb els de la projecció H\pi a la part lliure. Amb alguna hipòtesi extra sobre el suprem involucrat en la definició de di, definim una noció alternativa anomenada grau d'inèrcia restringit. En el cas de ZM x Fn, més enllà de la fita superior donada, som capaços de donar una fórmula d'igualtat per aquest grau d'inèrcia restringit. (2) L'estudi de les propietats dels subgrups de punts fixos per automorfismes de grups lliures Fn és molt més complicat però estan ben estudiats a la literatura. El fet que el resultat clàssic de Dyer-Scott sobre els subgrups fixos d'automorfismes d'ordre finit de Fn que són factors lliures de Fn no sigui cert a ZM x F_n, ens dóna la intuïció que els subgrups de punts fixos a ZM x Fn es comportaran de manera més degenerada que en el grup lliure. En aquest context més general, demostrem una versió relaxada en l'esperit del teorema de Bestvina-Handel: el rang dels subgrups fixos d'automorfismes d'ordre finit de ZM x Fn està uniformement acotat en termes només de n i m. Per cada automorfisme donat, és natural de preguntar pels elements que queden fixes. El problema dual consisteix en, donat un subgrup finitament generat H, preguntar si existeix una col·lecció finita d'automorfismes que fixin exactament aquest subgrup en particular, element a element. En aquesta tesi resolem també aquest problema tot donant un algorisme per a calcular clausures auto-fixes de subgrups finitament generats de ZM x Fn. (3) En aquesta tesi desenvolupem un esquema de compartició de secrets traient profit del fet que ZM x Fn no satisfà la propietat de Howson, i.e., conté subgroups finitament generats amb intersecció no finitament generada. Concretament, les claus per als k jugadors seran k subgrups finitament generats de ZM x Fn de manera que qualsevol intersecció sigui no finitament generada, excepte la total, que serà presa com el secret. D'aquesta manera, augmentem significativament la dificultat per part d'una coalició il·legal de jugadors d'obtenir cap informació