Universitat Politècnica de Catalunya. Facultat de Matemàtiques i Estadística
In this work we use geometric techniques in order to study certain natural extensions of free groups, and solve several algorithmic problems on them. To this end, we consider the family of free-abelian times free groups (Zm x Fn) as a seed towards further generalization in two main directions: semidirect products, and partially commuative groups (PC-groups). The four principal projects of this thesis are the following: Direct products of free-abelian and free groups We begin by studying the structure of the groups Zm x Fn , with special emphasis on their lattice of subgroups, and their endomorphisms (for which an explicit description is given, and both injectivity and surjectiveness are characterized); to then solve on them algorithmic problems involving both subgroups (the membership problem, the finite index problem, and the subgroup and coset intersection problems), and endomorphisms (the fixed points poblem, the Whitehead problems, and the twisted-conjugacy problem). Algorithmic recognition of infinite-cyclic extensions In the first part, we prove the algorithmic undecidability of several properties (finite generability, finite presentability, abelianity, finiteness, independence, triviality) of the base group of finitely presented cyclic extensions. In particular, we see that it is not possible to decide algorithmically if a finitely presented Z-extension admits a finitely generated base group. This last result allows us to demonstrate the undecidability of the Bieri-Neumann-Strebel (BNS) invariant. In the second part, we prove the equivalence between the isomorphism problem within the subclass of unique Z-extensions, and the semi-conjugacy problem for certain type of outer automorphisms, which we characterize algorithmically. Stallings automata for free-abelian by free groups After recreating in a purely algorithmic language the classic theory of Stallings associating an automaton to each subgroup of the free group, we extend this theory to semi-direct products of the form Zm ¿ Fn. Specifically, we associate to each subgroup of Zm ¿ Fn , an automaton ("enriched" with vectors in Zm), and we see that in the finitely generated case this construction is algorithmic and allows to solve the membership problem within this family of groups. The geometric description obtained also shows (even in the case of direct products) not only that the intersection of finitely generated subgroups can be infinitely generated, but that even when it is finitely generated, the rank of the intersection can not be bound in terms of the ranks of the intersected subgroups. This fact is relevant because it denies any possible extension of the celebrated - and recently proven - Hanna-Neumann conjecture in this direction. Intersection problems for Droms groups After characterizing those partially commutative groups satisfying the Howson property, we combine the algorithmic version of the theorem of the subgroups of Kurosh given by S.V. Ivanov, with the ideas coming from our work on Zm x Fn, to prove the solvability of the subgroup and coset intersection problems within the subfamily of Droms groups (that is, those PC- groups whose subgroups are always again partially commutative).
En aquest treball s'usen tècniques geomètriques per estudiar certes extensions naturals dels grups lliures, i atacar diversos problemes algorísmics sobre elles. A aquest efecte, es considera la família de grups lliure-abelians per lliure (Zm x Fn) com a punt de partida envers generalitzacions en dues direccions principals: productes semidirectes, i grups parcialment commutatius (PC-groups). Els quatre projectes principals d'aquesta tesi es descriuen a continuació. Productes directes de grups lliure-abelians per lliure. Comencem estudiant l'estructura dels grups Zm x Fn, amb especial èmfasi en el seu reticle de subgrups, i el seu monoide d'endomorfismes (per als que es dóna una descripció explícita, i es caracteritzen tant la injectivitat com l'exhaustivitat); per després resoldre sobre ells problemes algorísmics involucrant tant subgrups (el problema de la pertinença, el problema de l'índex finit, i els problemes de la intersecció de subgrups i classes laterals), com endomorfismes (el problema dels punts fixos, els problemes de Whitehead , i el problema de la "conjugació retorçada" o twisted-conjugacy problem). Reconeixement algorítmic d'extensions cícliques. A la primera part, es demostra la indecidibilitat algorísmica de diverses propietats (generabilitad finita, presentabilitad finita, abelianitat, finitud, llibertat, i trivialitat) del grup base de les extensions cícliques finitament presentades. En particular, veiem que no és possible decidir algorítmicament si una Z-extensió finitament presentada admet un grup base finitament generat. Aquest últim resultat ens permet demostrar també la indecidibilitat de l'invariant BNS (de Bieri-Neumann-Strebel). A la segona part, es demostra l'equivalència entre el problema de l'isomorfisme dins de la subclasse de Z-extensions úniques, i el problema de la semi-conjugació per a cert tipus d'automorfismes exteriors, que caracteritzem algorísmicament. Autòmats d'Stallings per a grups lliure-abelians by lliure. Després de recrear en un llenguatge purament algorísmic la teoria clàssica d'Stallings associant un autòmat a cada subgrup del grup lliure, estenem aquesta teoria a productes semidirectes de la forma Zm x Fn . Concretament associem un autòmat "enriquit" amb vectors de Zm a cada subgrup de Zm x Fn , i veiem que en el cas de subgrups finitament generats aquesta construcció és algorísmica i permet resoldre el problema de la pertinença dins d'aquesta família de grups. La descripció geomètrica obtinguda mostra a més (fins i tot en el cas de productes directes), no només que la intersecció de subgrups finitament generats pot ser infinitament generada, sinó que, fins i tot quan és finitament generada, no es pot afitar el rang de la intersecció en termes dels rangs dels subgrups intersecats. Aquest fet és rellevant perquè denega qualsevol possible extensió de la celebrada - i recentment provada - conjectura de Hanna Neumann en aquesta direcció. Problemes de la intersecció per a grups de Droms. Després de caracteritzar els grups parcialment commutatius que satisfan la propietat de Howson, combinem la versió algorísmica del teorema dels subgrups de Kurosh donada per S.V. Ivanov, amb les idees provinents del nostre treball sobre Zm x Fn, per demostrar la resolubilitat dels problemes de la intersecció de subgrups, de classes laterals (i afins) dins la subfamília de PC-grups de Droms (i.e., aquells PC-grups en que tots els subgrups son de nou parcialment commutatius).
512 - Algebra
Àrees temàtiques de la UPC::Matemàtiques i estadística
ADVERTIMENT. L'accés als continguts d'aquesta tesi doctoral i la seva utilització ha de respectar els drets de la persona autora. Pot ser utilitzada per a consulta o estudi personal, així com en activitats o materials d'investigació i docència en els termes establerts a l'art. 32 del Text Refós de la Llei de Propietat Intel·lectual (RDL 1/1996). Per altres utilitzacions es requereix l'autorització prèvia i expressa de la persona autora. En qualsevol cas, en la utilització dels seus continguts caldrà indicar de forma clara el nom i cognoms de la persona autora i el títol de la tesi doctoral. No s'autoritza la seva reproducció o altres formes d'explotació efectuades amb finalitats de lucre ni la seva comunicació pública des d'un lloc aliè al servei TDX. Tampoc s'autoritza la presentació del seu contingut en una finestra o marc aliè a TDX (framing). Aquesta reserva de drets afecta tant als continguts de la tesi com als seus resums i índexs.