Mojito bien mérité pour les modérateurs

samok
samok
dans Fondements et Logique
Je pense que le lemme de Burnside n'est pas un lemme, et, qu'il n'est pas de Burnside.

Big bisous :)

Réponses

  • samok
    samok

    Compléter la suite logique :

    $\mathbb{N}, \,\mathbb{Z}, \,\mathbb{D}, \,\mathbb{Q}, \,\mathbb{R}, \,\mathbb{C}\, \ldots$





  • gebrane
    gebrane
    -

    LemmeI1

    Le lemme de Burnside... Outre le fait qu'il n'est pas dû à Burnside et qu'on peut le considérer autrement qu'un lemme, ce résultat obscur de la théorie des groupes permet de faire des choses hallucinantes ! Si si ! Il permet par exemple de compter le nombre de colliers que l'on peut faire avec 3 perles rouges, 3 perles bleues et 5 perles vertes. Il permet aussi de compter le nombre de colliers que l'on peut faire avec 6 perles jaunes, 3 perles bleues, une perle verte et une perle rouge.

    Il permet en fait de répondre à n'importe quel problème de dénombrement avec des perles ! (et certains problèmes sans perle : combien y a-t-il de façons de partager un paquet de Vache qui rit (aux isométries près) entre 3 personnes, combien existe-t-il de sudokus réellement différents, etc.). Le lemme de Burnside est l'exemple typique de l'énoncé abstrait d'un domaine abstrait qui trouve des applications concrètes dans des domaines concrets (pour peu que l'on aime fabriquer des colliers). 

    Exemple I-2
    Pour réaliser de tels dénombrements, il faut seulement s'intéresser de près à la théorie des groupes agissant sur un ensemble. Au diable la théorie, passons directement à la pratique : pour cela, il nous faut un groupe et un ensemble. Pour ce premier exemple, prenons l'ensemble des colliers rouges et bleus à 5 perles :

    Colliers_5
    Sept colliers bicolores à 5 perles, parmi les 32 existants

    Cet ensemble contient 25 (=32) éléments (chaque perle pouvant être de deux couleurs).

    Quand on regarde les exemples, on voit certains colliers sont les mêmes, à une rotation près (par exemple, le 3ème se déduisent du deuxième par une rotation d'un cinquième de tour). Puisqu'il nous faut également un groupe, c'est naturellement que l'on prend celui des rotations du pentagone.

    rotations_5
    Il existe 5 rotations (r1, r2, r3, r4 et r5) qui transforment ce pentagone en lui-même : elles forment le groupe des rotations du pentagone. Appelons ce groupe Z/5Z.

    L'ensemble des 5 rotations du pentagone forment un groupe (la succession de deux rotations est toujours une rotation, et il existe une rotation neutre).

    rotation_r2
    Le groupe agit sur l'ensemble : sous l'action de la rotation r2 (2 cinquièmes de tour), le collier est transformé en un collier différent. Certains colliers ne sont pas transformé sous l'effet d'une rotation (les colliers d'une seule couleur)

    La question est donc de trouver le nombre de colliers différents en tenant compte que certains sont identiques (moyennant l'action du groupe Z/5Z sur l'ensemble des colliers). Pour chaque élément du groupe, certains colliers restent inchangés : par exemple, sous l'effet de la rotation r1 (un cinquième de tour), le collier tout rouge est inchangé. Le lemme de Burnside dit alors la chose suivante : le nombre que l'on cherche est la moyenne des nombres de colliers inchangés.

    Procédons donc au calcul :
    - la rotation r1 : elle ne fixe que deux colliers : le tout rouge et le tout bleu. (2 colliers)
    - la rotation r2 : idem (2 colliers)
    - la rotation r3 : idem (2 colliers)
    - la rotation r4 : idem (2 colliers)
    - la rotation r5 (qui est en fait une rotation neutre) : aucun collier n'est transformé par cette rotation. Elle fixe donc les 32 colliers.

    La moyenne est donc : (2+2+2+2+32)/5 = 8

    Il y a donc 8 colliers différents !

    8colliers

    Exemple I-3
    Deuxième exemple, un peu plus parlant : combien y a t-il de façons de partager équitablement une boîte de Vache qui rit entre 3 personnes, sachant que deux partages sont équivalents s'ils se déduisent l'un de l'autre par une rotation ou une symétrie.

    On a donc besoin d'un ensemble : ça sera celui des partages de Vache qui rit entre 3 personnes (Cyan, Magenta et Jaune). Cyan prend deux parts parmi les six (2 parmi 6 = 15 possibilités), Magenta prend deux parts parmi les 4 restantes (2 parmi 4 = 6 possibilités), Jaune prend les deux dernières (1 possibilité). Au total, il y a donc 15 × 6 × 1 = 90 partages différents.

    partageVQR
    Quatre partages de Vache qui rit, parmi les 90 existants. Les deux premiers sont équivalents (par une rotation), les deux derniers également (par une symétrie axiale).

    Il nous faut également un groupe. On va prendre le groupe D6, le groupe des isométries de l'hexagone. Il contient 12 éléments : l'identité (Id), 5 rotations (r1, r2, r3, r4 et r5, respectivement de 1, 2, 3, 4 et 5 sixièmes de tour) et 6 symétries axiales (s1, s2, s3, s4, s5 et s6).

    D6Les 12 isométries du groupe D6.

    De la même façon que précédemment, les isométries agissent sur les partages, et en laissent certains fixes. Voyons dans le détail :
    - Id laisse fixe l'ensemble des partages (90 partages)
    - r1 et r5 (rotations) n'en fixent aucun (2×0 partages)
    - r2 et r4 (rotations) n'en fixent aucun (2×0 partages)
    - r3 (symétrie centrale) laisse fixe les partages où les parts sont opposés (6 partages)
    - s1, s3 et s5 (symétries axiales) laisse fixe les partages où les parts sont symétriques, l'axe ne coupe pas de parts (3×6 partages)
    - s2, s4 et s6 (symétries axiales) laisse fixe les partages où les parts sont symétriques, l'axe coupant une paire de parts (3×6 partages)

    Au final, il y a donc (90+2×0+2×0+6+3×6+3×6)/12 = 11 partages possibles !

    partageVQR11

    Application I-4
    On pourrait multiplier les exemples utilisant les groupes d'isométries des polygones ou polyèdres réguliers ("combien y a-t-il de façons de peindre les faces d'un cube de façon à ce que 3 faces soient rouges, 2 jaunes et 1 bleue ?"), mais on peut également répondre à l'aide de Burnside à cette question primordiale : "combien existe-t-il de sudokus réellement différents" ?

    Un dénombrement minutieux (*) permet de montrer qu'il en existe 6670903752021072936960., mais on sait qu'il en existe en réalité beaucoup moins que ça : peut-on réellement considérer deux grilles de sudokus différentes si l'une est le reflet de l'autre dans un miroir ?

    Deux grilles de sudokus sont donc équivalentes si on peut passer de l'une à l'autre en faisant une (ou plusieurs) des opérations suivantes :
    - permutation des nombres
    - permutation de deux colonnes au sein d'un même pile (bloc de 3 colonnes)
    - permutation de deux blocs de colonnes
    - permutation de deux lignes au sein d'un même bande (groupe de 3 lignes)
    - permutation de deux blocs de lignes
    - transposition (inversion des lignes et des colonnes)
    - rotation
    - symétrie axiale

    En mettant de côté la permutation des nombres, les opérations légales ne sont que des permutations des 81 cases du sudoku.

    Combien existe-t-il de grilles de sudokus équivalentes ? Le lemme de Burnside approche !

    Il nous faut donc un ensemble. On ne va pas prendre les 6670903752021072936960 grilles différentes : c'est beaucoup trop. Quitte à permuter les nombres, on peut toujours se ramener à une grille dont la première région est "1-2-3/4-5-6/7-8-9". On dira que deux grilles sont semblables si on peut passer de l'une à l'autre en permutant les chiffres.
    Puisqu'il existe 9! = 362880 permutations de 9 chiffres, on peut se ramener à l'ensemble des 18383222420692992 grilles de sudoku non semblables.

    Il nous faut également un groupe, celui des permutations légales de la grille de Sudoku. Avec le logiciel adéquat, on peut montrer qu'il existe 3359232 opérations légales. En tenant compte des classes de conjugaison (certaines opérations se comportent de la même façon - dans l'exemple précédent, c'était le cas de  r1 et r5, ou de s1, s3 et s5 ), on peut se ramener à l'étude 275 (classes de conjugaisons de) permutations de la grille de Sudoku.

    sudok_invariant
    La grille de sudoku est invariante (à une similitude près) sous l'opération "permutation [...] bande"

    Pour chacune de ces 275 opérations, il faut trouver le nombre de grilles fixées (à une similitude près)
    - Pour l'opération Id, 18383222420692992 grilles sont fixées.
    - Pour l'opération "permutation des colonnes 1, 2 et 3", aucune grille n'est fixée.
    - Pour l'opération "permutation circulaire des colonnes au sein de chaque pile, puis permutation circulaire des lignes au sein de la troisième bande", un dénombrement minutieux montre que 21233664 grilles sont fixées (à une similitude près).
    - etc.

    En appliquant alors le lemme de Burnside, on trouve qu'il existe 5472730538 grilles de sudokus réellement différentes !

    Alors ?! Qui a dit que la théorie des groupes n'avait pas d'applications concrètes ?...

    • 201010 cette nouvelle anne est-elle intressante episode 11


    Lorsque notre cher Nico, le professeur, intervient dans une question d'analyse, c'est une véritable joie pour les lecteurs..


  • NicoLeProf
    NicoLeProf
    samok a dit :
    Compléter la suite logique :
    $\mathbb{N}, \,\mathbb{Z}, \,\mathbb{D}, \,\mathbb{Q}, \,\mathbb{R}, \,\mathbb{C}\, \ldots$
    $\mathbb{H}$ je dirais .
    Tu es très drôle samok avec tes trolls ^^' :D:D:D
    Lorsque notre cher Gebrane, le 😄 farceur, intervient dans une question d'algèbre, c'est une véritable joie pour les lecteurs.


  • gebrane
    gebrane
    Je crois que AD peut nous en parler de ce lemme obscur de la theorie des groupes
    Lorsque notre cher Nico, le professeur, intervient dans une question d'analyse, c'est une véritable joie pour les lecteurs..


  • Dom
    Dom
    Après $\mathbb C$, je mettrais $\mathbb H$. 
  • gebrane
    gebrane
    Moi je mettrais $\mathbb R^3$ pour ne pas sauter une dimension
    Lorsque notre cher Nico, le professeur, intervient dans une question d'analyse, c'est une véritable joie pour les lecteurs..


  • Médiat_Suprème
    Médiat_Suprème
    $\mathbb{N}, \,\mathbb{Z}, \,\mathbb{D}, \,\mathbb{Q}, \,\mathbb{R}, \,\mathbb{C},\,  \mathbb{H}, \, \mathbb{O} , \, \mathbb{S} , \, \mathbb{T} ,\,\mathbb{X} ,\, \cdots$$
    $
    Il ne faut pas respirer la compote, ça fait tousser.

    J'affirme péremptoirement que toute affirmation péremptoire est fausse
  • llorteLEG
    llorteLEG
    Modifié (July 2023)
    14 26 4 17 18 3 8 15 19 20 24 
    Je comprends pas la suite logique
  • Martial
    Martial
    D'accord avec @Médiat_Suprème, qui une fois de plus m'a coupé l'herbe sous les pieds.
  • Martial
    Martial
    Cerise sur le gôto : je crois qu'on note $\mathbb{A}$ la limite inductive de cette suite. J'aimerais bien voir la tête de c'huistiole.
  • Dom
    Dom
    Par contre tout me semble construit avec l’algèbre sauf $\mathbb R$ peut-être. Me trompé-je ?
  • Médiat_Suprème
    Médiat_Suprème
    Modifié (July 2023)
    Martial a dit :
     je crois qu'on note $\mathbb{A}$ la limite inductive de cette suite. 
    Je confirme, et ch'te bestiole n'est pas si compliquée, car toutes les opérations algébriques se passent dans une de ces algèbres.
    Dom, à partir de $\mathbb C$, ce sont les algèbres sur $\mathbb R$ obtenues par la méthode de Cayley-Dickson (standard)
    Il ne faut pas respirer la compote, ça fait tousser.

    J'affirme péremptoirement que toute affirmation péremptoire est fausse
  • Dom
    Dom
    Je n’y connais rien…

    Je sais qu’on obtient plein de corps qui sont sur-corps de $\mathbb Q$ et sous-corps de $\mathbb R$. En a-t-on un plus grand que tous ? Est-ce que la limite inductive est $\mathbb R$ ?


  • Médiat_Suprème
    Médiat_Suprème
    Modifié (July 2023)
    Si on prend une suite (indexée par $\mathbb N$ ) de corps inclus les uns dans les autres et de degré de transcendance croissant  de 1 en 1 (sur $\mathbb Q$), il n'y a pas de plus grand, mais la limite n'est pas $\mathbb R$, dont le degré de transcendance est $2^{\aleph_0}$ (sur $\mathbb Q$).

    Si je ne dis pas de bêtises.
    Il ne faut pas respirer la compote, ça fait tousser.

    J'affirme péremptoirement que toute affirmation péremptoire est fausse
  • Martial
    Martial
    @Médiat_Suprème : Merci pour tes explications concernant $\mathbb{A}$.
    Par ailleurs tu ne dis pas de bêtises dans ton exemple ci-dessus : ta limite inductive est dénombrable, donc elle ne peut pas être égale à $\mathbb{R}$. Maintenant, si tu mets un bon ordre sur l'ensemble des nombres réels qui sont transcendants sur $\mathbb{Q}$ et si tu construis successivement $\mathbb{Q}(x_0)$, puis $\mathbb{Q}(x_0,x_\alpha)$, où $\alpha$ est le premier ordinal tel que $x_\alpha$ est transcendant sur $\mathbb{Q}(x_0)$ etc, en prenant les réunions aux limites, je pense qu'à l'arrivée (i.e. après $2^{\aleph_0}$ étapes, tu vas obtenir $\mathbb{R}$... Mais en gros ça revient à redémontrer l'existence des bases de transcendance.
    Si je ne dis pas de bêtises...
  • Martial
    Martial
    A la réflexion tu n'as pas vraiment besoin de faire la manip ci-dessus, tu peux très bien construire $\mathbb{Q}(x_0)$, puis $\mathbb{Q}(x_0,x_1)$, puis $\mathbb{Q}(x_0,x_1,x_2)$ etc. Simplement il se peut que certains de ces corps soient égaux, sachant malgré tout que tu peux extraire de cette suite une sous-suite strictement croissante de longueur $2^{\aleph_0}$.
  • Médiat_Suprème
    Médiat_Suprème
    @Martial : nous sommes d'accord, de mon côté, je voulais juste donner un contrexemple à @Dom
    Il ne faut pas respirer la compote, ça fait tousser.

    J'affirme péremptoirement que toute affirmation péremptoire est fausse
  • Dom
    Dom
    Oui, merci bien. Sans pouvoir plonger au fond des choses, c’est déjà passionnant. 😀
  • samok
    samok
    Modifié (July 2023)
    Quand vous aurez fini, vous compléterez celle-ci : 
    $\mathbb{C}, \,\mathbb{R}, \,\mathbb{Q}, \,\mathbb{D}, \,\mathbb{Z}, \,\mathbb{N}\, \ldots$
    Bisous d'ours de la Grande Ourse :)
  • AD
    AD
    Le week-end est maintenant largement dépassé.
    Il est temps de fermer.
    AD.
Cette discussion a été fermée.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Français