Groupes

En algèbre abstraite, un groupe est un tuple $(G,\ast)$ , où $G$ est un ensemble et $\ast$ est une fonction $G\times G\rightarrow G$ telle que:

• Pour tout $x, y, z$ dans $G$ , $(x\ast y)\ast z=x\ast(y\ast z)$ .

• Il existe un élément $e$ dans $G$ tel que pour tout $x$ dans $G$ , $x\ast e=x$ .

• Pour chaque dans , il existe un élément dans tel que .G y G x ∗ y = $x$$G$$y$$G$$x\ast y=e$

L' ordre d'un groupe est défini comme étant le nombre d'éléments de .$(G,\ast)$$G$

Pour chaque entier strictement positif , il existe au moins un groupe d'ordre . Par exemple, est un tel groupe, où et x + _ny = (x + y) \ mod n .n ( C n , + n ) C n = { 0 , . . . , n - 1 } x + n y = ( x + y $n$$n$$(C_n,+_n)$$C_n=\{0,...,n-1\}$$x+_ny=(x+y)\mod n$

Groupes isomorphes

Soit $G:=\{1,2\}$ et définissons $\ast$ par $x\ast y=(x\times y)\mod3$ . Alors $1\ast1=1=2\ast2$ et $1\ast2=2=2\ast1$ .

De même, $0+_20=0=1+_21$ et $0+_21=1=1+_20$ .

Bien que les éléments et les opérations des groupes $(G,\ast)$ et $(C_2,+_2)$ aient des noms différents, les groupes partagent la même structure.

On dit que deux groupes $(G_1,\ast_1)$ et $(G_2,\ast_2)$ sont isomorphes s'il existe une bijection $\phi:G_1\rightarrow G_2$ telle que $\phi(x\ast_1y)=\phi(x)\ast_2\phi(y)$ pour tous les $x,y$ dans $G_1$ .

Tous les groupes du même ordre ne sont pas isomorphes. Par exemple, le groupe de Klein est un groupe d'ordre 4 qui n'est pas isomorphe à $(C_4,+_4)$ .

Tâche

Écrivez un programme ou une fonction qui accepte un entier non négatif n en entrée et imprime ou renvoie le nombre de groupes non isomorphes d'ordre n .

Cas de test

Input   Output
0       0
1       1
2       1
3       1
4       2
5       1
6       2
7       1
8       5
9       2
10      2
11      1
12      5
13      1
14      2
15      1
16      14
17      1
18      5
19      1
20      5

(extrait de OEIS A000001 )

Règles supplémentaires

• Il n'y a aucune limite sur le temps d'exécution ou l'utilisation de la mémoire.

• Les éléments intégrés qui banalisent cette tâche, tels que Mathematica FiniteGroupCount, ne sont pas autorisés.

• Les règles de code-golf standard s'appliquent.

CJam, 189 187 octets

Celui-ci va être difficile à expliquer ... La complexité du temps est garantie O(scary).

qi:N_3>{,aN*]N({{:L;N,X)-e!{X)_@+L@@t}%{X2+<z{_fe=:(:+}%:+!},}%:+}fX{:G;N3m*{_~{G@==}:F~F\1m>~F\F=}%:*},:L,({LX=LX)>1$f{\_@a\a+Ne!\f{\:M;~{M\f=z}2*\Mff==}:|{;}|}\a+}fX]:~$e`{0=1=},,}{!!}?

Si vous êtes assez courageux, essayez-le en ligne . Sur mon portable merdique, je peux obtenir jusqu'à 6 avec l'interpréteur Java ou 5 dans l'interpréteur en ligne.

Explication

Je n'ai pas une grande formation en mathématiques (je viens de terminer mes études secondaires, je commence CS à l'université la semaine prochaine). Alors, soyez indulgent avec moi si je fais des erreurs, si j'énonce une évidence ou si je fais les choses de manière horriblement inefficace.

Mon approche est une force brute, bien que j'aie essayé de la rendre un peu plus intelligente. Les principales étapes sont les suivantes:

1. Générer tous les opérandes possibles ∗ pour un groupe d'ordre n (c'est-à-dire énumérer tous les groupes d'ordre n );
2. Générer toutes les bijections possibles φ entre deux groupes d'ordre n ;
3. À l'aide des résultats des étapes 1 et 2, déterminez tous les isomorphismes entre deux groupes d'ordre n ;
4. En utilisant le résultat de l'étape 3, comptez le nombre de groupes jusqu'à l'isomorphisme.

Avant d'examiner comment chaque étape est effectuée, retirons du code trivial:

qi:N_             e# Get input as integer, store in N, make a copy
     3>{...}    ? e# If N > 3, do... (see below)
            {!!}  e# Else, push !!N (0 if N=0, 1 otherwise)

L'algorithme suivant ne fonctionne pas correctement avec n <4 , les cas de 0 à 3 sont traités avec une double négation.

Désormais, les éléments d'un groupe seront écrits comme {1, a, b, c, ...} , où 1 est l'élément d'identité. Dans l'implémentation CJam, les éléments correspondants sont {0, 1, 2, 3, ...} , où 0 est l'élément d'identité.

Commençons par l'étape 1. L'écriture de tous les opérateurs possibles pour un groupe d'ordre n équivaut à générer toutes les tables Cayley n × n valides . La première ligne et la première colonne sont triviales: elles sont toutes les deux {1, a, b, c, ...} (de gauche à droite, de haut en bas).

      e# N is on the stack (duplicated before the if)
,a    e# Generate first row [0 1 2 3 ...] and wrap it in a list
  N*  e# Repeat row N times (placeholders for next rows)
    ] e# Wrap everything in a list
      e# First column will be taken care of later

Savoir qu'une table Cayley est aussi un carré latin réduit (en raison de la propriété d'annulation) permet de générer les tables possibles ligne par ligne. À partir de la deuxième ligne (index 1), nous générons toutes les permutations uniques pour cette ligne, en gardant la première colonne fixée à la valeur de l'index.

N({                                 }fX e# For X in [0 ... N-2]:
   {                            }%      e#   For each table in the list:
    :L;                                 e#     Assign the table to L and pop it off the stack
       N,                               e#     Push [0 ... N-1]
         X)                             e#     Push X+1
           -                            e#     Remove X+1 from [0 ... N-1]
            e!                          e#     Generate all the unique permutations of this list
              {         }%              e#     For each permutation:
               X)_                      e#       Push two copies of X+1
                  @+                    e#       Prepend X+1 to the permutation
                    L@@t                e#       Store the permutation at index X+1 in L
                          {...},        e#     Filter permutations (see below)
                                  :+    e#   Concatenate the generated tables to the table list

Bien sûr, toutes ces permutations ne sont pas valides: chaque ligne et colonne doit contenir tous les éléments exactement une fois. Un bloc filtre est utilisé à cet effet (une valeur véridique conserve la permutation, une fausse la supprime):

X2+                 e# Push X+2
   <                e# Slice the permutations to the first X+2 rows
    z               e# Transpose rows and columns
     {        }%    e# For each column:
      _fe=          e#   Count occurences of each element
          :(        e#   Subtract 1 from counts
            :+      e#   Sum counts together
                :+  e# Sum counts from all columns together
                  ! e# Negate count sum:
                    e#   if the sum is 0 (no duplicates) the permutation is kept
                    e#   if the sum is not zero the permutation is filtered away

Notez que je filtre à l'intérieur de la boucle de génération: cela rend le code un peu plus long (par rapport à la génération et au filtrage distincts), mais améliore considérablement les performances. Le nombre de permutations d'un ensemble de taille n est n! , la solution la plus courte nécessiterait donc beaucoup de mémoire et de temps.

Une liste de tables Cayley valides est une grande étape vers l'énumération des opérateurs, mais étant une structure 2D, elle ne peut pas vérifier l'associativité, qui est une propriété 3D. La prochaine étape consiste donc à filtrer les fonctions non associatives.

{                                 }, e# For each table, keep table if result is true:
 :G;                                 e#   Store table in G, pop it off the stack
    N3m*                             e#   Generate triples [0 ... N-1]^3
        {                     }%     e#   For each triple [a b c]:
         _~                          e#     Make a copy, unwrap top one
           {    }:F                  e#     Define function F(x,y):
            G@==                     e#       x∗y (using table G)
                   ~F                e#     Push a∗(b∗c)
                     \1m>            e#     Rotate triple right by 1
                         ~           e#     Unwrap rotated triple
                          F\F        e#     Push (a∗b)∗c
                             =       e#     Push 1 if a∗(b∗c) == (a∗b)∗c (associative), 0 otherwise
                                :*   e#   Multiply all the results together
                                     e#   1 (true) only if F was associative for every [a b c]

Phew! Beaucoup de travail, mais maintenant nous avons énuméré tous les groupes d'ordre n (ou mieux, les opérations dessus - mais l'ensemble est fixe, c'est donc la même chose). Étape suivante: trouver des isomorphismes. Un isomorphisme est une bijection entre deux de ces groupes tels que φ (x ∗ y) = φ (x) ∗ φ (y) . Générer ces bijections dans CJam est trivial: le Ne!fera. Comment pouvons-nous les vérifier? Ma solution part de deux copies de la table Cayley pour x ∗ y . Sur une copie, φ est appliqué à tous les éléments, sans toucher à l'ordre des lignes ou des colonnes. Cela génère le tableau pour φ (x ∗ y) . Sur l'autre les éléments sont laissés comme ils sont, mais les lignes et les colonnes sont mises en correspondance par φ . Autrement dit, la ligne / colonnex devient la ligne / colonne φ (x) . Cela génère le tableau pour φ (x) ∗ φ (y) . Maintenant que nous avons les deux tableaux, il suffit de les comparer: s'ils sont les mêmes, nous avons trouvé un isomorphisme.

Bien sûr, nous devons également générer les paires de groupes pour tester l'isomorphisme. Nous avons besoin de toutes les 2 combinaisons des groupes. On dirait que CJam n'a pas d'opérateur pour les combinaisons. Nous pouvons les générer en prenant chaque groupe et en le combinant uniquement avec les éléments qui le suivent dans la liste. Fait amusant: le nombre de 2 combinaisons est n × (n - 1) / 2 , qui est également la somme des n - 1 premiers nombres naturels. Ces nombres sont appelés nombres triangulaires: essayez l'algorithme sur papier, une ligne par élément fixe, et vous comprendrez pourquoi.

:L                          e# List of groups is on stack, store in L
  ,(                        e# Push len(L)-1
    {                  }fX  e# For X in [0 ... len(L)-2]:
     LX=                    e#   Push the group L[X]
        LX)>                e#   Push a slice of L excluding the first X+1 elements
            1$              e#   Push a copy of L[X]
              f{...}        e#   Pass each [L[X] Y] combination to ... (see below)
                            e#   The block will give back a list of Y for isomorphic groups
                    \a+     e#   Append L[X] to the isomorphic groups
                          ] e# Wrap everything in a list

Le code ci-dessus corrige le premier élément de la paire, L [X] , et le combine avec d'autres groupes (appelons chacun de ces Y ). Il passe la paire à un bloc de test d'isomorphisme que je montrerai dans un instant. Le bloc rend une liste de valeurs de Y pour lesquels L [X] est isomorphe à Y . Ensuite, L [X] est ajouté à cette liste. Avant de comprendre pourquoi les listes sont ainsi configurées, regardons le test d'isomorphisme:

\_@                                      e# Push a copy of Y
   a\a+                                  e# L[X] Y -> [L[X] Y]
       Ne!                               e# Generate all bijective mappings
          \f{                    }       e# For each bijection ([L[X] Y] extra parameter):
             \:M;                        e#   Store the mapping in M, pop it off the stack
                 ~                       e#   [L[X] Y] -> L[X] Y
                  {     }2*              e#   Repeat two times (on Y):
                   M\f=                  e#     Map rows (or transposed columns)
                       z                 e#     Transpose rows and columns
                                         e#     This generates φ(x) ∗ φ(y)
                           \Mff=         e#   Map elements of L[X], generates φ(x ∗ y)
                                =        e#   Push 1 if the tables are equal, 0 otherwise
                                  :|     e#   Push 1 if at least a mapping was isomorphic, 0 otherwise
                                    {;}| e#   If no mapping was isomorphic, pop the copy of Y off the stack

Très bien, nous avons maintenant une liste d'ensembles comme [{L [0], Y1, Y2, ...}, {L [1], Y1, ...}, ...] . L'idée ici est que, par propriété transitive, si deux ensembles ont au moins un élément en commun, alors tous les groupes des deux ensembles sont isomorphes. Ils peuvent être agrégés en un seul ensemble. Comme L [X] n'apparaîtra jamais dans les combinaisons générées par L [X + ...] , après agrégation, chaque ensemble d'isomorphismes aura un élément unique. Ainsi, pour obtenir le nombre d'isomorphismes, il suffit de compter le nombre de groupes qui apparaissent exactement une fois dans tous les ensembles de groupes isomorphes. Pour ce faire, je déballe les ensembles pour qu'ils ressemblent à [L [0], Y1, Y2, ..., L [1], Y1, ...] , trie la liste pour créer des clusters du même groupe et enfin RLE-l'encode.

:~            e# Unwrap sets of isomorphic groups
  $           e# Sort list
   e`         e# RLE-encode list
     {    },  e# Filter RLE elements:
      0=      e#   Get number of occurrences
        1=    e#   Keep element if occurrences == 1
            , e# Push length of filtered list
              e# This is the number of groups up to isomorphism

C'est tout, les amis.

CJam, 73 octets

0ri:Re!Rm*{:Tz0=R,=[R,Te_]m!{~ff{T==}e_}/=&},{:T,e!{:PPff{T==P#}}%$}%Q|,+

La complexité temporelle du code ci-dessus est pire que O (n! ^N ) .

L'entrée n = 4 est déjà trop pour l' interprète en ligne .

En utilisant l' interpréteur Java , l'entrée n = 5 pourrait être possible, si vous avez suffisamment de RAM et de patience.

Trouver des groupes

Étant donné un groupe (G, ∗) d'ordre n , nous pouvons choisir une bijection arbitraire φ: G -> C _n telle que φ (e) = 0 .

φ deviendra un isomorphisme de (G, ∗) et (C _n , ∗ ') si nous définissons ∗' par x ∗ 'y = φ (φ ^-1 (x) ∗ φ ^-1 (y)) .

Cela signifie qu'il suffit d'étudier tous les opérateurs de groupe dans C _n tels que 0 est l'élément neutre.

Nous représenterons un opérateur de groupe ∗ dans C _n par un tableau rectangulaire T de dimensions n × n telles que T [x] [y] = x ∗ y .

Pour générer un tel tableau, nous pouvons commencer par choisir une permutation de C _n pour chacune de ses n lignes.

De cette façon, 0 sera présent dans toutes les lignes (mais pas nécessairement toutes les colonnes ), ce qui signifie que la troisième condition (existence d'une inverse) sera remplie, quel que soit e .

On peut fixer e = 0 en exigeant que la première colonne de T soit égale à C _n . En particulier, la deuxième condition (existence d'un élément neutre) sera remplie.

Pour vérifier que T correspond à un opérateur de groupe, il ne reste plus qu'à vérifier que la première condition (associativité) est vérifiée . Cela peut être fait de manière exhaustive en vérifiant que T [T [x] [y]] [z] == T [x] [T [y] [z]] pour tout x, y, z dans C _n .

Comptage des groupes non isomorphes

La méthode ci-dessus pour trouver des groupes donnera certains groupes isomorphes. Plutôt que d'identifier ceux qui sont isomorphes, nous générons la famille de tous les groupes isomorphes pour chacun d'eux.

Cela peut être réalisé en itérant sur toutes les bijections φ: C _n -> C _n , et en déterminant le tableau associé Tφ , défini par Tφ [x] [y] = φ ^-1 (T [φ (x)] [φ (y )]) .

Il ne reste plus qu'à compter le nombre de familles distinctes.

Que fait le code

0         e# Push 0. For input 0, the remaining code will crash, leaving
          e# this 0 on the stack.
ri:R      e# Read an integer from STDIN and save it in R.
e!        e# Push all permutations of [0 ... R-1].
Rm*       e# Push all arrays of 6 permutations of [0 ... R-1].
{         e# Filter; for each array:
  :T      e#   Save it in T.
  z0=R,=  e#   Check if the first column equals [0 ... R-1].
  [R,Te_] e#   Push [0 ... R-1] and a flattened T.
  m!{     e#   For both pairs (any order):
    ~     e#     Unwrap the pair.
    ff{   e#     For each X in the first: For each Y in the second:
      T== e#       Push T[X][Y].
    }     e#
  }/      e#
  =       e#   Check for equality, i.e., associativity.
  &       e#   Bitwise AND with the previous Boolean
},        e# Keep T iff the result was truthy.
{         e# For each kept array:
  :T      e#   Save it in T
  ,e!     e#   Push all permutations of [0 ... R-1].
  {       e#   For each permutation:
    :PP   e#     Save it in P. Push a copy.
    ff{   e#     For each X in P: For each Y in P:
      T== e#       Push T[X][Y].
      P#  e#       Find its index in P.
    }     e#
  }%      e#
  $       e#   Sort the results.
}%        e#
Q|,       e# Deduplicate and count.
+         e# Add the result to the 0 on the stack.

Python 2 , 515 507 octets

• Enregistré huit octets grâce à Dennis .

def F(n):
 def f(k,*s):n==len(set(s))and S.add(s);{k and f(~-k,j,*s)for j in I}
 def c(k,*G):k and{s in G or c(~-k,s,*G)for s in S}or(I in G)&all((o(x,y)in G)&any(I==o(z,x)for z in G)for x in G for y in G)and A.add(G)
 S=set();A=S-S;I=tuple(range(n));o=lambda x,y:tuple(y[x[j]]for j in I);i=lambda G,H:any(all(o(H[B[i]],H[B[j]])==H[B[[k for k in I if G[k]==o(G[i],G[j])][0]]]for i in I for j in I)for B in S);f(n);c(n);K=list(A);[G in K and{G!=H and i(G,H)and K.remove(H)for H in K}for G in A];return len(K)

Essayez-le en ligne!

$n$$\ \Sigma_n$$n$

Lien vers la version détaillée .