Authors: Fine, Benjamin
Myasnikov, Alexei
Rosenberger, Gerhard
Title: Generic Subgroups of Group Amalgams
Language (ISO): en
Abstract: For many groups the structure of finitely generated subgroups is generically simple. That is with asymptotic density equal to one a randomly chosen finitely generated subgroup has a particular well-known and easily analyzed structure. For example a result of D.B.A.Epstein says that a finitely generated subgroup of GL(n;R) is generically a free group. We say that a group G has the generic free group property if any finitely generated subgroup is generically a free group. Further G has the strong generic free group property if given randomly chosen elements g_1, ...,g_n in G then generically they are a free basis for the free subgroup they generate. In this paper we show that for any arbitrary free product of finitely generated infinite groups satisfies the strong generic free group property. There are also extensions to more general amalgams - free products with amalgamation and HNN groups. These results have implications in cryptography. In particular several cryptosystems use random choices of subgroups as hard cryptographic problems. In groups with the generic free group property any such cryptosystem may be attackable by a length based attack.
Issue Date: 2008-04-21T08:46:03Z
Appears in Collections:Preprints der Fakultät für Mathematik

Files in This Item:
File Description SizeFormat 
mathematicalPreprint05.pdf282.47 kBAdobe PDFView/Open

This item is protected by original copyright

All resources in the repository are protected by copyright.