IntegerVectorsModPermutationGroup

Fiche dév Ens Sup - Recherche
  • Création ou MAJ importante : 26/11/12
  • Correction mineure : 04/09/13
Mots-clés

IntegerVectorsModPermutationGroup : énumeration modulo l'action d'un groupe de permutation

Ce logiciel a été développé (ou est en cours de développement) dans la communauté de l'Enseignement Supérieur et de la Recherche. Son état peut être variable (cf champs ci-dessous) donc sans garantie de bon fonctionnement.
  • Site web
  • Système : UNIX-like, Windows, MacOS X
  • Licence(s) : GPL
  • Etat : diffusé, stable
  • Support : maintenu, développement en cours
  • Concepteur(s) : Nicolas Borie
  • Contact concepteur(s) : nicolas.borie@univ-mlv.fr
  • Laboratoire(s), service(s)... : Labo Maths Orsay

 

Fonctionnalités générales du logiciel

IntegerVectorsModPermutationGroup est un moteur d’énumération des vecteurs d'entiers modulo l'action d'un groupe de permutations.

Soit n un entier positif et G un groupe de permutations, sous groupe du groupe symétrique d'ordre n. Le module Sage IntegerVectorsModPermutationGroup permet l'énumération des tuples de longueur n modulo l'action de G sur les entrées de ces vecteurs. Ce problème généralise l'énumération des graphes non étiquetés à un isomorphisme près. On peut raffiner l'énumération de ces vecteurs d'entiers en imposant des contraintes telles que la somme des entrées ou la taille des entrées dans ces vecteurs.

Ce module est complètement intégré au logiciel Sage depuis sa version 4.7.

Exemple

Voici un exemple pour le groupe cyclique d'ordre 4.

sage: G = PermutationGroup([[(1,2,3,4)]]); G
Permutation Group with generators [(1,2,3,4)]
sage: G.cardinality()
4
sage: S = IntegerVectorsModPermutationGroup(G); S
Integer vectors of length 4 enumerated up to the action of Permutation Group with generators [(1,2,3,4)]
sage: S.cardinality()
+Infinity
sage: it = iter(S)
sage: for i in range(25): v = it.next(); print v, " : ", S.orbit(v)
....:
[0, 0, 0, 0]  :  set([[0, 0, 0, 0]])
[1, 0, 0, 0]  :  set([[1, 0, 0, 0], [0, 0, 1, 0], [0, 1, 0, 0], [0, 0, 0, 1]])
[2, 0, 0, 0]  :  set([[2, 0, 0, 0], [0, 0, 2, 0], [0, 0, 0, 2], [0, 2, 0, 0]])
[1, 1, 0, 0]  :  set([[1, 0, 0, 1], [0, 0, 1, 1], [1, 1, 0, 0], [0, 1, 1, 0]])
[1, 0, 1, 0]  :  set([[0, 1, 0, 1], [1, 0, 1, 0]])
[3, 0, 0, 0]  :  set([[0, 0, 3, 0], [0, 3, 0, 0], [3, 0, 0, 0], [0, 0, 0, 3]])
[2, 1, 0, 0]  :  set([[0, 2, 1, 0], [0, 0, 2, 1], [1, 0, 0, 2], [2, 1, 0, 0]])
[2, 0, 1, 0]  :  set([[0, 1, 0, 2], [0, 2, 0, 1], [1, 0, 2, 0], [2, 0, 1, 0]])
[2, 0, 0, 1]  :  set([[2, 0, 0, 1], [0, 1, 2, 0], [1, 2, 0, 0], [0, 0, 1, 2]])
[1, 1, 1, 0]  :  set([[1, 1, 1, 0], [1, 1, 0, 1], [1, 0, 1, 1], [0, 1, 1, 1]])
[4, 0, 0, 0]  :  set([[4, 0, 0, 0], [0, 4, 0, 0], [0, 0, 4, 0], [0, 0, 0, 4]])
[3, 1, 0, 0]  :  set([[0, 0, 3, 1], [1, 0, 0, 3], [0, 3, 1, 0], [3, 1, 0, 0]])
[3, 0, 1, 0]  :  set([[0, 3, 0, 1], [0, 1, 0, 3], [3, 0, 1, 0], [1, 0, 3, 0]])
[3, 0, 0, 1]  :  set([[0, 0, 1, 3], [3, 0, 0, 1], [0, 1, 3, 0], [1, 3, 0, 0]])
[2, 2, 0, 0]  :  set([[0, 2, 2, 0], [2, 2, 0, 0], [2, 0, 0, 2], [0, 0, 2, 2]])
[2, 1, 1, 0]  :  set([[2, 1, 1, 0], [1, 0, 2, 1], [1, 1, 0, 2], [0, 2, 1, 1]])
[2, 1, 0, 1]  :  set([[0, 1, 2, 1], [1, 0, 1, 2], [2, 1, 0, 1], [1, 2, 1, 0]])
[2, 0, 2, 0]  :  set([[2, 0, 2, 0], [0, 2, 0, 2]])
[2, 0, 1, 1]  :  set([[1, 2, 0, 1], [2, 0, 1, 1], [0, 1, 1, 2], [1, 1, 2, 0]])
[1, 1, 1, 1]  :  set([[1, 1, 1, 1]])
[5, 0, 0, 0]  :  set([[0, 0, 0, 5], [5, 0, 0, 0], [0, 5, 0, 0], [0, 0, 5, 0]])
[4, 1, 0, 0]  :  set([[0, 0, 4, 1], [1, 0, 0, 4], [0, 4, 1, 0], [4, 1, 0, 0]])
[4, 0, 1, 0]  :  set([[0, 4, 0, 1], [1, 0, 4, 0], [0, 1, 0, 4], [4, 0, 1, 0]])
[4, 0, 0, 1]  :  set([[4, 0, 0, 1], [1, 4, 0, 0], [0, 0, 1, 4], [0, 1, 4, 0]])
[3, 2, 0, 0]  :  set([[3, 2, 0, 0], [0, 0, 3, 2], [2, 0, 0, 3], [0, 3, 2, 0]])

Contexte d’utilisation du logiciel

Le développement de ce moteur d'énumération a été nécessaire lors de la thèse de doctorat en théorie effective des invariants de N. Borie, l'auteur du logiciel. Il trouve des applications dans les domaines suivants :

  • Théorie algébrique des invariants,
  • Théorie de Galois effective,
  • Théorie des espèces de structures.
Publications liées au logiciel