An analogue to Dixon's theorem for automaton groups

Abstract : Dixon's famous theorem states that the group generated by two random permutations of a finite set is generically either the whole symmetric group or the alternating group. In the context of random generation of finite groups this means that it is hopeless to wish for a uniform distribution – or even a non-trivial one – by drawing random permutations and looking at the generated group. Mealy automata are a powerful tool to generate groups, including all finite groups and many interesting infinite ones, whence the idea of generating random finite groups by drawing random Mealy automata. In this paper we show that, for a special class of Mealy automata that generate only finite groups, the distribution is far from being uniform since the obtained groups are generically a semi-direct product between a direct product of alternating groups and a group generated by a tuple of transpositions.
Type de document :
Communication dans un congrès
Workshop on Analytic Algorithmics and Combinatorics (ANALCO), Jan 2017, Barcelone, Spain. 〈http://www.siam.org/meetings/analco17/〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01378815
Contributeur : Thibault Godin <>
Soumis le : lundi 10 octobre 2016 - 18:09:51
Dernière modification le : jeudi 11 janvier 2018 - 06:27:39
Document(s) archivé(s) le : samedi 4 février 2017 - 01:36:00

Fichiers

Dixon_ANALCO_abs.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01378815, version 1
  • ARXIV : 1610.03301

Collections

Citation

Thibault Godin. An analogue to Dixon's theorem for automaton groups. Workshop on Analytic Algorithmics and Combinatorics (ANALCO), Jan 2017, Barcelone, Spain. 〈http://www.siam.org/meetings/analco17/〉. 〈hal-01378815〉

Partager

Métriques

Consultations de la notice

151

Téléchargements de fichiers

46