Bonjour, j'aimerais savoir comment vous justifiez que deux éléments d'un groupe admettant une certaine présentation sont distincts.

Pour prendre un exemple concret, le groupe diédral D2n admet la présentation < r,s | r^n, s², rs = sr^-1 >, on peut montrer que tout élément s'écrit s^i r^j avec i entre 0 et 1 et j entre 0 et n-1 mais comment montrer simplement que cette forme caractérise exactement les éléments ?

Procéder au cas par cas est relativement évident, par exemple on peut facilement montrer que sr² ≠ sr sinon on aurait r = e. Maintenant le problème c'est de faire le cas général. Concrètement il suffirait de calculer dans le groupe libre engendré par s et par r le sous-groupe normal engendré par les 3 relations, auquel cas on saurait exactement quels assemblages sont neutres et on aurait donc toutes les égalités et non égalités. Le problème c'est que ce sous-groupe est relativement dégueu à exprimer.

Dans ce cas précis le plus simple semble être de faire une disjonction de cas sur la valeur des exposants en s, mais ça semble peu de généraliser à des présentations un peu plus compliquées.

Je pense pas qu'il y ait de moyens simples pour faire ce genre de choses ça me rappelle un peu le problème du mot démontré par Tarski, qui affirme qu'il n'existe aucun algorithme permettant de dire que deux groupes avec des représentations différentes si égaux ou non.
Je ne sais pas s'il y a vraiment de lien avec ce que tu demandes, mais si on arrivait à expliciter une façon de faire simple permettant de faire ce que tu aimerais ... ben ça me semble puissant quoi

Mais ouais dans le cas précis du groupe diédral, le plus simple est de regarder la puissance de s. Mais effectivement ça se généralise mal ... Par exemple, si on s'amuse à retirer la relation s², la puissance de s est a priori complètement libre, ce qui complique énormément les choses.

Tout ça pour te dire que ça me semble chaud

Le 21 mai 2020 à 13:44:23 Quiquine2 a écrit :
Je pense pas qu'il y ait de moyens simples pour faire ce genre de choses ça me rappelle un peu le problème du mot démontré par Tarski, qui affirme qu'il n'existe aucun algorithme permettant de dire que deux groupes avec des représentations différentes si égaux ou non.
Je ne sais pas s'il y a vraiment de lien avec ce que tu demandes, mais si on arrivait à expliciter une façon de faire simple permettant de faire ce que tu aimerais ... ben ça me semble puissant quoi

Mais ouais dans le cas précis du groupe diédral, le plus simple est de regarder la puissance de s. Mais effectivement ça se généralise mal ... Par exemple, si on s'amuse à retirer la relation s², la puissance de s est a priori complètement libre, ce qui complique énormément les choses.

Tout ça pour te dire que ça me semble chaud

J'avoue que c'est aussi le sentiment que j'ai. En fait je pense qu'il est possible qu'on puisse algorithmiquement déterminer si deux assemblages sont égaux dans le cas d'un nombre fini de générateurs et de relations mais que ça soit avec une méthode bourrine avec une grande complexité algorithmique.

Après j'espérais qu'il y aurait des "astuces" au moins pour les présentations de groupes finis usuels.

En fait je pense qu'il est possible qu'on puisse algorithmiquement déterminer si deux assemblages sont égaux dans le cas d'un nombre fini de générateurs et de relations mais que ça soit avec une méthode bourrine avec une grande complexité algorithmique.

Non, il y a des groupes / monoïdes dont le problème du mot est indécidable même quand tout est fini. La preuve consiste en gros à simuler une machine de Turing, et pour ça tu n'as besoin que d'un nombre fini de générateurs (les symboles sur le ruban) et de relations (les règles de réécriture de la machine).

Après j'espérais qu'il y aurait des "astuces" au moins pour les présentations de groupes finis usuels.

Une méthode générale (pour les monoïdes) c'est d'imposer une direction sur tes relations (au lieu d'écrire s^n = e, tu prends s^n => e), ce qui te donne un système de réécriture. (En gros : en partant d'un mot fini sur ton ensembles de générateurs, tu peux remplacer un sous-mot s^n par e, mais pas le contraire)

Si tu prouves que ton système de réécriture:
- termine : pas de séquence infinie de réécritures en partant d'un mot valide. Par exemple "le nombre de lettres diminue strictement"
- est confluent : tous les chemins de réécriture partant d'un mot donné terminent sur le même mot final, appelé "forme normale".

Alors tu peux décider le problème du mot pour ce monoïde : tu as juste à calculer les formes normales et regarder si elles sont égales.

Par contre, cette méthode ne marche pas toujours : le théorème de squier dit qu'il existe un monoïde finiment présenté, dont le problème du mot est décidable, mais qui n'admet aucun système de réécriture confluent qui termine.

Pour les groupes je suppose qu'on peut adapter cette technique en mettant les s^-1, r^-1 comme générateurs, et en rajoutant les relations qui vont bien

Intéressant. T'as des mots clés pour en apprendre plus sur le sujet ?

J'ai l'impression que "Problème du mot" renvoie vers ces trucs là en général.

Pour les systèmes de réécriture :
- pour prouver que ça termine : relation bien fondée / relation Noethérienne
- pour prouver la confluence : propriété de Church-Rosser, paires critiques, lemme de Newman
Le livre de référence a l'air d'être "Term Rewriting and All That"

Je crois que les bases de Gröbner ont un rapport mais je sais pas trop dans quelle mesure.

Le 21 mai 2020 à 22:14:18 Choucador a écrit :
J'ai l'impression que "Problème du mot" renvoie vers ces trucs là en général.

Pour les systèmes de réécriture :
- pour prouver que ça termine : relation bien fondée / relation Noethérienne
- pour prouver la confluence : propriété de Church-Rosser, paires critiques, lemme de Newman
Le livre de référence a l'air d'être "Term Rewriting and All That"

Je crois que les bases de Gröbner ont un rapport mais je sais pas trop dans quelle mesure.

Merci.