Remarques et problèmes concernant les descriptions algorithmiques des groupes

Informations de base

• ID de l'article: 2111.01190
• Titre: Remarks and problems about algorithmic descriptions of groups
• Auteur: Emmanuel Rauzy
• Classification: math.GR (théorie des groupes), math.LO (logique mathématique)
• Date de publication: Première soumission le 2 novembre 2021, deuxième version le 21 juin 2024
• Lien de l'article: https://arxiv.org/abs/2111.01190

Résumé

Inspiré par le théorème de Groves et Wilton, cet article propose d'étudier la structure de treillis de la numérotation des classes d'isomorphisme de groupes marqués, comme cadre rigoureux et complet pour l'étude des problèmes de décision globaux des groupes finiment engendrés. L'article établit les théorèmes de Rice et Rice-Shapiro pour les représentations récursives, et des résultats analogues pour les représentations corécursives. L'auteur fournit une caractérisation algorithmique des groupes finiment présentables, à savoir la semi-décidabilité de deux problèmes de décision : le problème du mot et le problème des quotients marqués. L'article explique comment utiliser ce résultat pour définir des généralisations algorithmiques des présentations finies, et discute enfin des réponses incomplètes fournies par le théorème d'Adian-Rabin sous plusieurs aspects.

Contexte et motivation de la recherche

Contexte du problème

L'étude des problèmes de décision en théorie des groupes remonte aux trois célèbres problèmes posés par Max Dehn en 1911 : le problème du mot, le problème de conjugaison et le problème d'isomorphisme. La motivation de ces problèmes provient de la topologie, en particulier de l'étude des groupes fondamentaux. Traditionnellement, ces problèmes ont été principalement étudiés pour les groupes finiment présentables.

Motivation centrale

La motivation principale de cet article provient d'un théorème important de Groves et Wilton : Théorème 1 : Il existe un algorithme qui, étant donné une présentation d'un groupe G et une solution au problème du mot dans G, peut déterminer si G est un groupe libre.

Ce résultat indique qu'il est insuffisant de construire une théorie des problèmes de décision globaux des groupes en utilisant uniquement les présentations finies comme description finie fondamentale d'un groupe, mais qu'il faut plutôt utiliser les présentations finies augmentées d'un algorithme pour le problème du mot.

Signification de la recherche

1. Perfectionnement théorique : Fournir un cadre théorique plus rigoureux pour les problèmes de décision globaux des groupes
2. Caractérisation algorithmique : Donner les caractéristiques algorithmiques des groupes finiment présentables
3. Applications généralisées : Poser les fondations pour les généralisations algorithmiques des présentations finies

Contributions principales

1. Proposition du cadre théorique du treillis de numérotation : Établissement de la structure de treillis de la numérotation des classes d'isomorphisme de groupes marqués comme cadre unifié pour l'étude des problèmes de décision globaux
2. Établissement des théorèmes de Rice et Rice-Shapiro : Établissement des théorèmes de Rice et Rice-Shapiro correspondants pour les représentations récursives et corécursives
3. Caractérisation algorithmique des groupes finiment présentables : Preuve qu'un groupe est finiment présentable si et seulement s'il possède un problème du mot semi-décidable et un problème des quotients marqués semi-décidable
4. Introduction du problème des quotients marqués : Proposition d'un nouveau concept de problème de décision et analyse de ses propriétés
5. Analyse des limitations du théorème d'Adian-Rabin : Mise en évidence de l'incomplétude du résultat classique sous plusieurs aspects

Explication détaillée des méthodes

Définitions des concepts fondamentaux

Groupes marqués et numérotations

• Groupe k-marqué : Un couple (G,S) où G est un groupe et S∈G^k est un k-uplet engendrant G
• Numérotation : Une surjection partielle ν: ⊆ℕ → X d'un sous-ensemble des nombres naturels vers un ensemble X
• Fonction calculable : Une fonction f: X → Y est (ν,μ)-calculable s'il existe une fonction partiellement calculable F telle que pour tout n∈dom(ν), on ait f∘ν(n) = μ∘F(n)

Opérations de treillis

Pour deux numérotations ν et μ, on définit :

• Disjonction ν∨μ : (ν∨μ)(2k) = ν(k), (ν∨μ)(2k+1) = μ(k)
• Conjonction ν∧μ : dom(ν∧μ) = {⟨n,m⟩ | n∈dom(ν), m∈dom(μ), ν(n)=μ(m)}

Types de numérotations principales

1. νFP : Numérotation des présentations finies
2. νRP : Numérotation des représentations récursives
3. νco-RP : Numérotation des représentations corécursives
4. νWP : Numérotation des algorithmes du problème du mot (νRP ∧ νco-RP)
5. νMQA : Numérotation des algorithmes des quotients marqués

Topologie de Scott

On définit la topologie de Scott sur le treillis des groupes k-marqués (Gk,→), où :

• Les ouverts de Scott sont les ensembles supérieurs non atteignables par unions dirigées
• Les éléments compacts sont exactement les groupes marqués finiment présentables

Points d'innovation technique

1. Cadre de numérotation unifié

Par la théorie des numérotations, on unifie différents types de descriptions de groupes dans un cadre mathématique unique, permettant une comparaison rigoureuse du pouvoir expressif de différentes méthodes de description.

2. Introduction du problème des quotients marqués

Définition : Étant donné un groupe marqué (G,S), son problème des quotients marqués est de déterminer si un groupe marqué (H,S') donné par une représentation récursive est un quotient marqué de (G,S).

L'introduction de ce concept permet de décomposer les présentations finies en information locale (problème du mot) et information globale (problème des quotients marqués).

3. Généralisation du théorème de Rice-Shapiro

Théorème 4 (Théorème de Rice-Shapiro pour les représentations récursives) : Si P est une propriété des groupes marqués semi-décidable à partir des représentations récursives, alors il existe une séquence de présentations finies énumérables calculatoirement telle qu'un groupe satisfait P si et seulement s'il est un quotient marqué d'un groupe défini par l'une de ces présentations.

Configuration expérimentale

Cet article est principalement une recherche théorique sans configuration expérimentale au sens traditionnel, mais il contient de nombreuses preuves constructives et analyses algorithmiques.

Méthodes de vérification théorique

1. Preuves constructives : Preuve des résultats d'existence par construction explicite d'algorithmes
2. Techniques de diagonalisation : Utilisation de méthodes de diagonalisation similaires au problème de l'arrêt pour prouver l'indécidabilité
3. Méthodes de réduction : Réduction des problèmes à des problèmes indécidables connus

Résultats principaux

1. Caractérisation algorithmique des groupes finiment présentables

Théorème 7 : Un groupe marqué (G,S) est finiment présentable si et seulement s'il possède un problème du mot semi-décidable et un problème des quotients marqués semi-décidable. Formalisé comme équivalence de numérotations : νFP ≡ νRP ∧ νMQA

2. Généralisation du théorème de Rice

Corollaire 5 : Pour les groupes avec représentations récursives, il n'existe pas de propriété de groupes marqués non triviale décidable. Corollaire 37 : Pour les groupes avec représentations corécursives, il n'existe pas de propriété de groupes non triviale décidable.

3. Caractérisation topologique

Corollaire 30 : La topologie générée par les ensembles semi-décidables à partir des représentations récursives est exactement la topologie de Scott sur le treillis des groupes marqués.

4. Algorithmes des quotients marqués relatifs

Proposition 54 : Le groupe phare Z/2Z≀Z possède un algorithme des quotients marqués pour la classe des groupes finis. Proposition 55 : Le groupe phare ne peut pas être finiment présenté en tant que groupe résiduellement fini.

Travaux connexes

Théorie classique des problèmes de décision

• Problèmes de Dehn : Recherche classique sur le problème du mot, le problème de conjugaison et le problème d'isomorphisme
• Théorème d'Adian-Rabin : Indécidabilité des propriétés de Markov
• Théorème d'intégration de Higman : Propriétés d'intégration des groupes récursivement présentables

Théorie de la calculabilité

• Théorie des numérotations de Malcev : Représentations calculables d'objets mathématiques
• Théorème de Rice : Indécidabilité des propriétés de programmes
• Calculabilité de Banach-Mazur : Concept de calculabilité sur les nombres réels

Théorie géométrique des groupes

• Théorie des groupes limites : Modèles universels de théories de groupes libres
• Groupes hyperboliques : Décidabilité des propriétés géométriques
• Groupes CAT(0) : Propriétés des groupes à courbure non positive

Conclusions et discussion

Conclusions principales

1. Efficacité du cadre du treillis de numérotation : Preuve que la théorie des treillis de numérotation fournit un cadre mathématique efficace pour l'étude des problèmes de décision globaux des groupes
2. Essence des présentations finies : Révélation que les présentations finies sont essentiellement une combinaison d'information locale faible (problème du mot semi-décidable) et d'information globale forte (problème des quotients marqués semi-décidable)
3. Universalité du théorème de Rice : Démonstration de l'applicabilité généralisée du théorème de Rice en théorie des groupes

Limitations

1. Théorie incomplète des représentations corécursives : Pour les représentations corécursives, manque d'un théorème complet de Rice-Shapiro
2. Classification insuffisante de la hiérarchie arithmétique supérieure : Classification incomplète des propriétés aux niveaux supérieurs de la hiérarchie arithmétique
3. Complexité des constructions : Certaines constructions nécessitent des techniques complexes, ce qui peut limiter les applications pratiques

Directions futures

1. Problème 40 : Établir un théorème complet de Rice-Shapiro pour les représentations corécursives
2. Problème 62 : Classification plus précise de davantage de propriétés de groupes dans la hiérarchie arithmétique
3. Problème 64 : Établir des conditions suffisantes d'indécidabilité dans le cas des présentations finies augmentées d'algorithmes du problème du mot

Évaluation approfondie

Points forts

1. Innovation théorique : Proposition d'un cadre entièrement nouveau du treillis de numérotation, fournissant une perspective unifiée pour les problèmes de décision en théorie des groupes
2. Profondeur technique : Combinaison ingénieuse de la théorie de la calculabilité et de la théorie des groupes, avec des techniques de preuve sophistiquées
3. Orientation vers les problèmes : Formulation explicite de plusieurs problèmes ouverts importants, indiquant les directions de recherche futures
4. Systématicité : Étude systématique des problèmes de description des groupes sous plusieurs angles (récursif, corécursif, algorithmes relatifs)

Insuffisances

1. Utilité pratique limitée : Principalement une recherche théorique avec valeur d'application directe limitée aux calculs pratiques en théorie des groupes
2. Seuil technique élevé : Nécessite une connaissance approfondie de la théorie de la calculabilité et de la théorie des groupes, ce qui peut limiter sa portée
3. Certains résultats incomplets : Par exemple, le théorème de Rice-Shapiro pour les représentations corécursives reste un problème ouvert

Impact

1. Contribution théorique : Fournit de nouveaux outils mathématiques pour la théorie des problèmes de décision en théorie des groupes
2. Disciplines interdisciplinaires : Favorise la fusion interdisciplinaire entre la théorie des groupes et la théorie de la calculabilité
3. Valeur méthodologique : La méthode des treillis de numérotation pourrait s'appliquer à l'étude d'autres structures algébriques

Domaines d'application

1. Recherche théorique en théorie des groupes : Fournit de nouveaux outils pour l'étude des propriétés algorithmiques des groupes
2. Algèbre calculable : Extension à l'étude de la calculabilité d'autres structures algébriques
3. Théorie de la complexité : Fournit une perspective de théorie des groupes pour l'analyse de la complexité algorithmique

Références bibliographiques

L'article cite 69 références importantes couvrant les problèmes de décision en théorie des groupes, la théorie de la calculabilité, la théorie géométrique des groupes et d'autres domaines, reflétant la profondeur et l'ampleur de la recherche.

Évaluation globale : Ceci est un article mathématique théorique de haute qualité ayant une valeur théorique importante dans l'étude des problèmes de décision en théorie des groupes. En introduisant le cadre du treillis de numérotation, l'auteur fournit une nouvelle perspective de recherche pour ce domaine classique et obtient une série de résultats théoriques profonds. Bien que son utilité pratique soit relativement limitée, sa contribution théorique et sa valeur méthodologique en font une référence importante dans ce domaine.