Langages de conjugaison et croissance de conjugaison relative aux sous-ensembles de groupes

Informations fondamentales

• ID de l'article : 2510.20923
• Titre : Conjugacy languages and conjugacy growth relative to subsets of groups
• Auteurs : André Carvalho (Université de Porto), Ana-Catarina C. Monteiro (NOVA FCT)
• Classification : math.GR (Théorie des groupes)
• Date de soumission : 23 octobre 2025
• Lien de l'article : https://arxiv.org/abs/2510.20923

Résumé

Cet article étudie la problématique des langages de conjugaison (conjugacy languages) en théorie des groupes, en particulier pour le problème de conjugaison généralisé (generalized conjugacy problem). La question centrale est : étant donné un élément de groupe $g \in G$ et un sous-ensemble $U \subset G$, déterminer si $g$ possède un élément conjugué dans $U$ (possiblement avec des contraintes sur le conjugué). Les auteurs définissent les langages correspondants $\text{ConjGeo}(U,V)$, $\text{CycGeo}(U)$, $\text{ConjSL}(U)$ et $\text{ConjMinLenSL}(U,V)$, et prouvent plusieurs résultats de régularité pour des classes de groupes : pour les groupes libres, ces langages sont réguliers lorsque $U, V$ sont des sous-ensembles rationnels ; pour les groupes hyperboliques, les résultats valent lorsque $U$ peut être représenté par un langage géodésique régulier ; des résultats correspondants sont obtenus pour les groupes virtuellement cycliques et virtuellement abéliens. De plus, les auteurs définissent des fonctions de croissance de conjugaison relative et montrent que leur comportement dépend fortement du choix du sous-ensemble.

Contexte et motivation de la recherche

Contexte du problème

1. Problème de conjugaison classique : L'un des problèmes fondamentaux en théorie des groupes est le problème de conjugaison (CP), c'est-à-dire déterminer si deux éléments d'un groupe sont conjugués. Ceci peut être généralisé en problème de conjugaison généralisé (GCP) : étant donné un élément $g$ et un sous-ensemble $U$, déterminer si $g$ possède un élément conjugué dans $U$.
2. Intersection des langages formels et de la théorie des groupes : La théorie des langages formels fournit des outils puissants pour étudier les problèmes de théorie des groupes. Par exemple, le théorème d'Anisimov établit que les groupes finis sont exactement les groupes dont le problème des mots est un langage régulier ; le théorème de Muller-Schupp caractérise les groupes virtuellement libres comme les groupes dont le problème des mots est sans contexte.
3. Limitations des travaux antérieurs :
   • Ciobanu et al. 12 ont étudié les langages de conjugaison dans le cas $U = V = G$
   • Ladra et Silva 23 ont prouvé que le problème de conjugaison généralisé pour les groupes virtuellement libres est décidable
   • Carvalho et Silva 10 ont étudié le problème de conjugaison généralisé double pour les sous-ensembles rationnels
   • Cependant, les propriétés des langages de conjugaison pour des sous-ensembles généraux $U \subset G$ n'ont pas été systématiquement étudiées

Motivation de la recherche

1. Complétude théorique : Généraliser le cas $U = G$ à des sous-ensembles généraux $U$, établissant un cadre théorique plus complet
2. Problèmes de décidabilité : Établir des résultats de décidabilité via les propriétés des langages (comme la régularité)
3. Comportement des fonctions de croissance : Les fonctions de croissance de conjugaison relative peuvent exhiber un comportement complètement différent de la croissance de conjugaison classique
4. Traitement unifié de différentes classes de groupes : Fournir un cadre théorique unifié en langage pour les groupes libres, hyperboliques, virtuellement cycliques, virtuellement abéliens, etc.

Contributions principales

1. Définition des langages de conjugaison relatifs : Pour les sous-ensembles $U, V \subseteq G$, définition systématique des langages :
   • $\text{ConjGeo}(U,V)$ : langage des représentants de conjugaison les plus courts (avec contraintes)
   • $\text{CycGeo}(U)$ : langage des mots géodésiques cycliques
   • $\text{ConjSL}(U)$ : langage de forme standard en ordre lexicographique court de conjugaison
   • $\text{ConjMinLenSL}(U,V)$ : langage en ordre lexicographique court de longueur minimale
2. Résultats de régularité pour les groupes libres (Théorème 4.5) : Pour le groupe libre $F_X$ et les sous-ensembles rationnels $U, V$, on prouve que $\text{ConjGeo}(U,V)$ et $\text{ConjMinLenSL}(U,V)$ sont des langages réguliers
3. Résultats de régularité pour les groupes hyperboliques (Théorème 5.8) : Pour un groupe $\delta$-hyperbolique, si $L$ est un langage géodésique régulier, alors $\text{ConjGeo}(L\pi)$ et $\text{ConjMinLenSL}(L\pi)$ sont réguliers
4. Caractérisation complète pour les groupes virtuellement cycliques (Théorème 6.1) : Pour un groupe virtuellement cyclique et tout sous-ensemble rationnel $U$, $\text{ConjSL}(U)$ est régulier
5. Préservation de la classe de langage pour les groupes virtuellement abéliens (Théorèmes 7.3, 7.4) : Sous les conditions appropriées, $\text{ConjGeo}(U)$ préserve les propriétés de la classe de langage originale
6. Diversité de la croissance de conjugaison relative (Théorème 3.1) : Construction de sous-ensembles rationnels $U_d$ tels que la croissance de conjugaison cumulative relative $cc_{F_2,X,U_d}(n)$ soit polynomiale d'ordre $n^{d-1}$ à $n^d$, montrant une différence remarquable avec la croissance exponentielle classique
7. Connexion avec la décidabilité (Proposition 3.2) : Établissement du lien entre la régularité des langages de conjugaison et la décidabilité du problème de conjugaison généralisé

Explication détaillée des méthodes

Définition des tâches

Problème central : Problème de conjugaison généralisé (avec contraintes)

• Entrée : Élément de groupe $g \in G$, sous-ensembles $U, V \subseteq G$
• Problème : Existe-t-il $u \in U$ et $v \in V$ tels que $g = v^{-1}uv$ ?
• Cas particulier : Lorsque $V = G$, cela se réduit au problème de conjugaison généralisé standard

Définition clé : $\alpha(K,L) = \bigcup_{u \in L} u^{-1}Ku$

Ceci représente l'union des éléments de $K$ conjugués par les éléments de $L$.

Définitions des langages centraux

Pour les sous-ensembles $U, V \subseteq G$ et l'ensemble générateur $X$ :

1. $\text{ConjGeo}_X(U,V)$ : $\text{ConjGeo}_X(U,V) = \text{ConjGeo}_X(G) \cap \alpha(U,V)\pi^{-1}$ représente les mots les plus courts pour chaque classe de conjugaison dans $\alpha(U,V)$
2. $\text{CycGeo}_X(U)$ : $\text{CycGeo}_X(U) = \{w \in \text{Geo}_X(U) \mid w \text{ est un mot géodésique cyclique}\}$
3. $\text{ConjMinLenSL}_X(U,V)$ : $\text{ConjMinLenSL}_X(U,V) = \{w_g \in \text{Geo}_X(\alpha(U,V)) \mid |g| = |g|_c\}$ où $w_g$ est la forme standard en ordre lexicographique court de $g$, et $|g|_c$ est la longueur minimale dans la classe de conjugaison
4. $\text{ConjSL}_X(U)$ : $\text{ConjSL}_X(U) = \{z_c \in \text{Geo}_X(\alpha(U)) \mid c \text{ est une classe de conjugaison}\}$ forme standard en ordre lexicographique court pour chaque classe de conjugaison intersectant $U$

Points d'innovation technique

1. Technique du langage de permutation pour les groupes libres

Définition 4.2 : Pour les langages réguliers $K, L$, définition du langage de permutation $P_{K,L} = \{u\ell \mid \ell \in L, \ell u \in K\}$

Lemme clé (Proposition 4.3) : Lorsque $UV$ est réduit (reduced), c'est-à-dire $|k\ell| \geq |k|$ pour tous $k \in U, \ell \in V$, alors $\text{ConjGeo}(U,V) = \text{ConjGeo}(F_X) \cap P_{U,V}$

Esquisse de la preuve :

• Utilisation de l'automate minimal $A = (Q, q_0, T, E)$ reconnaissant $U$
• Preuve que $P_{U,V} = \bigcup_{p \in Q, t \in T} L_{p,t}(L_{q_0,p} \cap V)$
• Observation clé : dans les groupes libres, $UV$ réduit signifie que $\ell$ est un préfixe de $k$ si et seulement si $|k\ell| = |k|$

2. Technique quasi-géodésique pour les groupes hyperboliques

Lemmes 5.1-5.3 : Utilisation de la propriété de minceur des triangles des groupes hyperboliques :

• Lemme 5.1 : La relation de conjugaison pour les mots complètement réduits peut être réalisée via des conjugués courts (longueur $\leq 2\delta + 1$)
• Lemme 5.2 : Version généralisée des mots quasi-géodésiques
• Lemme 5.3 : Construction de langages de représentants quasi-réduits à partir de langages géodésiques réguliers

Proposition 5.5 : Les mots $(1,r)$-quasi-géodésiques et $(1,s)$-quasi-géodésiques satisfont une propriété de compagnonnage asynchrone bornée (boundedly asynchronous fellow travel property), avec constante de distance $N$ dépendant de $r, s, \delta$

Corollaire 5.6 : Les langages $(1,\epsilon)$-quasi-géodésiques forment une structure bi-automatique

Technique centrale (Lemme 5.7) : Pour un langage géodésique régulier $K$, $\text{CycGeo}(\alpha(K\pi)) = S \cup \left[\text{CycGeo}(G) \cap \bigcup_{|z| \leq 2(\delta+\gamma)} \text{Cyc}(L_2(z))\right]$ où $S$ est un langage fini et $L_2(z)$ est défini par l'automate de relation de conjugaison

3. Technique d'automorphisme pour les groupes virtuellement abéliens

Observation clé (Lemme 7.2) : Pour un groupe abélien $G$ et un automorphisme $\phi$, $\phi(\text{Geo}_X(U)) = \text{Geo}_{\phi(X)}(\phi(U))$

Stratégie de preuve du Théorème 7.4 :

• Soit $N$ un sous-groupe normal abélien d'indice fini, $T = \{b_1, \ldots, b_n\}$ un ensemble de représentants de classes latérales
• Chaque $t \in T$ définit un automorphisme de conjugaison $\alpha_t: n \mapsto t^{-1}nt$
• Pour $U = \bigcup_{i=1}^n U_i b_i$ (avec $U_i \in C_\bullet(N)$), calcul de $\alpha(U_i b_i) = \bigcup_{s \in T} [U_i N(Q_{b_i}^{-1} - I)]^{Q_s} \cdot s^{-1}b_i s$ où $Q_t$ est la représentation matricielle de $\alpha_t$
• Utilisation de la fermeture du semi-AFL complet pour prouver $\alpha(U_i b_i) \in C_\bullet(G)$

Configuration expérimentale

Remarque : Cet article est un travail de mathématiques pures théoriques et ne contient pas de partie expérimentale. Tous les résultats sont des preuves mathématiques rigoureuses.

Exemples constructifs

Construction du Théorème 3.1 :

• Utilisation de la construction de Rigo 26 : pour chaque $d \in \mathbb{N}$, il existe un langage régulier $L_d$ tel que le nombre de mots de longueur $n$ soit $n^d$
• Alphabet $\Sigma_d = \{a_1, \ldots, a_{u_d}\}$, remplacement de chaque $a_i$ par $a^i b^i$
• Obtention du langage $K_d \subseteq \{a,b\}^*$, dont les éléments sont librement indépendants dans le groupe libre
• Analyse : $\frac{\sum_{i=0}^{\lfloor n/(2u_d) \rfloor} 2i^d}{i-2} < cc_{F_2,X,U_d}(n) < \sum_{i=0}^{\lfloor n/2 \rfloor} i^d$ donnant $n^{d-1} \lesssim cc_{F_2,X,U_d}(n) \lesssim n^d$

Résultats expérimentaux

Résultats théoriques principaux

1. Groupes libres (Théorème 4.5)

Résultat : Pour le groupe libre $F_X$ et les sous-ensembles rationnels $U, V$,

• $\text{ConjGeo}(U,V)$ est un langage régulier
• $\text{ConjMinLenSL}(U,V)$ est un langage régulier

Points clés de la preuve :

• Utilisation de la décomposition de Carvalho-Silva 10 : $\alpha(U,V) = \bigcup_{a \in \tilde{X}} (Y_a \cup Z_a)$
• Application de la technique du langage de permutation à chaque composante
• Utilisation de la régularité de $\text{ConjGeo}(F_X)$

Signification : Amélioration du résultat sans contexte de 10 en langage régulier

2. Groupes hyperboliques (Théorème 5.8)

Résultat : Pour un groupe $\delta$-hyperbolique $G$ et un langage géodésique régulier $L$,

• $\text{ConjGeo}(L\pi)$ est régulier
• $\text{ConjMinLenSL}(L\pi)$ est régulier

Structure de la preuve : $\text{ConjGeo}(L\pi) = S \cup \left[\left(\text{CycGeo}(\alpha(L\pi)) \cap \bigcup_{k \geq 8\delta+1} X^k\right) \setminus \text{Cyc}\left(\bigcup_{|\alpha| \leq 2\delta+1} L(\alpha)\right)\right]$

Corollaire 5.9 : Le problème de conjugaison généralisé pour les groupes virtuellement libres est décidable (fournissant une nouvelle preuve basée sur la théorie des langages)

3. Groupes virtuellement cycliques (Théorème 6.1)

Résultat : Pour un groupe virtuellement cyclique $G$ et un sous-ensemble rationnel $U$, $\text{ConjSL}(U)$ est régulier

Points essentiels de la preuve :

• Décomposition $\text{ConjSL}(U) = (\text{ConjSL}(U) \cap C\pi^{-1}) \cup (\text{ConjSL}(U) \cap (G \setminus C)\pi^{-1})$
• où $C$ est le centralisateur de $H \cong \mathbb{Z}$
• Le second terme est fini (car $G \setminus C$ n'a qu'un nombre fini de classes de conjugaison)
• Le premier terme est obtenu via la régularité de $\text{CycGeo}(\alpha(U))$ et les opérations sur les ensembles

4. Groupes virtuellement abéliens (Théorèmes 7.3, 7.4)

Théorème 7.3 : Soit $G$ un groupe virtuellement abélien, $N$ un sous-groupe normal abélien d'indice fini, $U \subseteq N$. Si $C$ est fermé par unions finies et intersections régulières, et $\text{Geo}_Z(U) \in C$, alors il existe un ensemble générateur $Z$ tel que

• $\text{ConjGeo}_Z(U) \in C$
• $\text{ConjMinLenSL}_Z(U) \in C$

Théorème 7.4 : Si $C$ est un semi-AFL complet et $U \in C_\bullet(G)$, alors $\alpha(U) \in C_\bullet(G)$

Corollaire 7.5 : Si $K \in C_\forall(G)$, alors $\text{ConjGeo}(K) \in C$

Résultats de fonction de croissance (Théorème 3.1)

Construction : Pour chaque $d \in \mathbb{N}$, il existe un sous-ensemble rationnel $U_d \in \text{Rat}(F_2)$ tel que $n^{d-1} \lesssim cc_{F_2,X,U_d}(n) \lesssim n^d$

Contraste : La croissance de conjugaison cumulative classique $cc_{F_2,X}(n)$ est exponentielle

Signification :

1. Montre que la croissance relative peut être un polynôme de degré arbitraire
2. Indique que le choix du sous-ensemble a un effet fondamental sur le comportement de croissance
3. Fournit une perspective quantifiée sur la complexité du problème de conjugaison généralisé

Résultats de décidabilité (Proposition 3.2)

Théorème : Soit $C$ une classe de sous-ensembles et $L$ une classe de langages. Si les conditions suivantes sont satisfaites :

1. $U, V \in C \Rightarrow \text{ConjGeo}(U,V) \in L$ est calculable
2. $U \in C, g \in G \Rightarrow U^g \in C$ est calculable
3. $G$ a un problème de conjugaison décidable
4. $L$ a un problème d'appartenance décidable

alors $G$ a un problème de conjugaison généralisé $C$-décidable (avec contraintes $C$)

Application : Combinaison avec les résultats de régularité pour chaque classe de groupes, donnant directement la décidabilité

Travaux connexes

Recherche en théorie des langages sur le problème de conjugaison

1. Holt-Rees-Röver 22 :
   • Définition du problème de conjugaison comme ensemble de paires $(u,v)$
   • Preuve que le problème de conjugaison pour les groupes virtuellement libres est asynchrone indexé
   • Les groupes virtuellement cycliques sont exactement les groupes dont le problème de conjugaison est sans contexte asynchrone
2. Levine 24 :
   • Les groupes virtuellement libres sont exactement les groupes où chaque classe de conjugaison est un sous-ensemble sans contexte
   • Généralisation du théorème de Muller-Schupp
3. Ciobanu-Hermiller-Holt-Rees 12 :
   • Définition de $\text{ConjGeo}(G)$, $\text{ConjMinLenSL}(G)$, $\text{ConjSL}(G)$ et autres langages
   • Preuve que $\text{ConjGeo}(G)$ et $\text{ConjMinLenSL}(G)$ sont réguliers pour les groupes hyperboliques
   • $\text{ConjGeo}(G)$ pour les groupes virtuellement abéliens est mesurable par segments
   • $\text{ConjSL}(G)$ pour les groupes virtuellement cycliques est régulier

Recherche sur le problème de conjugaison généralisé

4. Ladra-Silva 23 :
   • Preuve que le problème de conjugaison généralisé avec contraintes rationnelles pour les groupes virtuellement libres est décidable
   • Méthode : construction du langage de conjugué et preuve de sa régularité
5. Carvalho-Silva 10 :
   • Étude du problème de conjugaison généralisé double
   • Preuve que pour les groupes virtuellement libres et les sous-ensembles rationnels $U, V$, $\alpha(U,V)\pi^{-1}$ est sans contexte
   • Introduction du concept de représentation par langage géodésique
6. Diekert-Gutiérrez-Hagenah 16 :
   • La théorie existentielle avec contraintes rationnelles dans les groupes libres est PSPACE-complète

Théorie des groupes automatiques

7. Epstein et al. 17 :
   • Théorie fondamentale des groupes automatiques et bi-automatiques
   • Régularité des formes standard en ordre lexicographique court
8. Herbst 19, Carvalho-Nyberg-Brodda 9 :
   • Étude systématique des sous-ensembles de langages
   • Propriétés de la notation $C_\bullet(G)$ et des cônes, semi-AFL complets

Avancement apporté par cet article

• De $U = G$ à des sous-ensembles généraux : Généralisation systématique des résultats existants
• Cadre unifié : Traitement unifié en théorie des langages pour plusieurs classes de groupes
• Résultats plus forts : Amélioration du résultat sans contexte pour les groupes libres en langage régulier
• Nouvelle perspective : Les fonctions de croissance relative révèlent l'importance du choix du sous-ensemble

Conclusion et discussion

Conclusions principales

1. Caractérisation par théorie des langages :
   • Groupes libres : les langages de conjugaison relatifs pour les sous-ensembles rationnels sont réguliers
   • Groupes hyperboliques : les langages de conjugaison relatifs pour les sous-ensembles représentables géodésiquement sont réguliers
   • Groupes virtuellement cycliques : les langages en ordre lexicographique court pour les sous-ensembles rationnels sont réguliers
   • Groupes virtuellement abéliens : préservation des propriétés de classe de langage
2. Diversité des fonctions de croissance : La croissance de conjugaison relative peut être un polynôme de degré arbitraire, contrastant fortement avec la croissance exponentielle classique
3. Décidabilité : Établissement du lien entre la régularité des langages de conjugaison et la décidabilité du problème de conjugaison généralisé

Limitations

1. Restrictions pour les groupes virtuellement abéliens :
   • Le Théorème 7.3 requiert $U \subseteq N$ (à l'intérieur du sous-groupe abélien)
   • Le cas général (où $U$ n'est pas dans $N$) reste ouvert
2. Exigences de classe de langage :
   • Les groupes hyperboliques nécessitent une représentation géodésique régulière
   • Les groupes virtuellement abéliens nécessitent $\text{Geo}(U) \in C$
   • Tous les sous-ensembles rationnels ne satisfont pas ces conditions (comme l'exemple 7.1)
3. Constructivité :
   • Les bornes du degré de croissance du Théorème 3.1 ne sont pas précises (entre $n^{d-1}$ et $n^d$)
   • L'existence d'exemples avec degré exactement $d$ reste inconnue
4. Complexité computationnelle :
   • Preuve de décidabilité mais pas d'analyse de complexité
   • Efficacité de la construction d'automates non discutée

Directions futures

L'article énonce explicitement deux problèmes ouverts :

1. Degré de croissance précis (Problème 1) :
   • Peut-on construire un sous-ensemble rationnel $U_d$ tel que $cc_{F_2,X,U_d}(n) \sim n^d$ exactement ?
   • Actuellement seulement $n^{d-1} \lesssim cc_{F_2,X,U_d}(n) \lesssim n^d$
2. Cas général pour les groupes virtuellement abéliens (Problème 2) :
   • Quelles sont les propriétés de $\text{ConjGeo}(U)$ lorsque $U \not\subseteq N$ ?
   • Question technique clé : les éléments de $\text{ConjGeo}(U)$ peuvent-ils contenir des sous-mots de segments appartenant à $\text{ConjGeo}(G \setminus \alpha(U))$ ?
   • Suggestion de commencer par des classes de langages spécifiques (réguliers, mesurables par segments, segments exclus)
3. Autres directions potentielles :
   • Analyse de complexité computationnelle
   • Généralisation à d'autres classes de groupes (groupes CAT(0), groupes relativement hyperboliques)
   • Problème de conjugaison généralisé avec contraintes multiples
   • Propriétés asymptotiques des fonctions de croissance relative

Évaluation approfondie

Points forts

1. Profondeur théorique :
   • Généralisation systématique des résultats classiques de Ciobanu et al. 12
   • Caractérisation complète en théorie des langages pour plusieurs classes de groupes importantes
   • Techniques de preuve sophistiquées, particulièrement la méthode du langage de permutation et l'approche par automorphisme
2. Cadre unifié :
   • Notation $\alpha(U,V)$ unifiant le traitement de différents cas
   • Notation $C_\bullet(G)$ fournissant une approche flexible des classes de langages
   • Proposition 3.2 établissant un lien général entre théorie des langages et décidabilité
3. Innovation technique :
   • Langage de permutation $P_{K,L}$ comme nouvel outil pour les groupes libres
   • Technique quasi-géodésique pour les groupes hyperboliques généralisant les méthodes existantes
   • Méthode de matrice d'automorphisme pour les groupes virtuellement abéliens, nouvelle et élégante
4. Insight sur les fonctions de croissance :
   • Le Théorème 3.1 montre la richesse de la croissance relative
   • Fournit une perspective quantifiée pour comprendre la complexité du problème de conjugaison généralisé
   • Méthode de construction de portée générale
5. Qualité de rédaction :
   • Structure claire, progression du général au particulier
   • Connaissances préalables complètes, définitions précises
   • Détails de preuve suffisants, logique rigoureuse

Insuffisances

1. Limitation de couverture :
   • Les résultats pour les groupes virtuellement abéliens nécessitent $U \subseteq N$ ou $\text{Geo}(U) \in C$
   • Traitement insuffisant des sous-ensembles rationnels généraux (comme l'exemple 7.1)
   • Autres classes de groupes importantes (groupes d'angles droits, groupes de graphes) non abordées
2. Précision de la fonction de croissance :
   • Les bornes du Théorème 3.1 ne sont pas serrées (différence d'un degré)
   • Pas de construction atteignant un degré précis
   • Croissance relative pour d'autres classes de groupes non explorée
3. Aspects computationnels :
   • Pas d'analyse de complexité algorithmique
   • Efficacité de la construction d'automates non discutée
   • Calculabilité pratique non vérifiée
4. Contexte d'application :
   • Applications pratiques non discutées (cryptographie, théorie algorithmique des groupes)
   • Connexions avec d'autres problèmes de théorie des groupes insuffisantes
   • Manque d'exemples concrets et d'illustrations computationnelles
5. Problèmes ouverts :
   • Le cas général des groupes virtuellement abéliens est une lacune importante
   • Les difficultés techniques du Problème 2 ne sont pas suffisamment analysées
   • Manque de directions claires pour résoudre ces problèmes

Impact

1. Contribution théorique :
   • Généralisation importante de la théorie des langages de conjugaison
   • Établissement d'un lien profond entre le choix du sous-ensemble et les propriétés des langages
   • Fourniture d'un cadre systématique pour les recherches ultérieures
2. Valeur méthodologique :
   • La technique du langage de permutation peut s'appliquer à d'autres problèmes
   • La méthode d'automorphisme fournit un nouvel outil pour l'étude des groupes virtuellement abéliens
   • Le théorème de préservation de classe de langage a une portée générale
3. Reproductibilité :
   • Preuves détaillées, forte vérifiabilité
   • Méthodes de construction explicites
   • Mais manque d'implémentation computationnelle
4. Recherches ultérieures :
   • Problèmes ouverts clairement énoncés, directions de recherche explicites
   • Fourniture d'un modèle pour l'étude d'autres classes de groupes
   • Potentiel d'inspiration pour l'étude de problèmes connexes

Domaines d'application

1. Recherche théorique :
   • Problèmes de décision en théorie combinatoire des groupes
   • Intersection de la théorie des langages formels et de l'algèbre
   • Étude des fonctions de croissance et des propriétés asymptotiques
2. Théorie algorithmique des groupes :
   • Conception d'algorithmes de décision pour le problème de conjugaison généralisé
   • Optimisation du calcul des représentants de classes de conjugaison
   • Calcul symbolique pour les sous-ensembles rationnels
3. Domaines connexes :
   • Théorie des groupes automatiques
   • Théorie géométrique des groupes (groupes hyperboliques, groupes CAT(0))
   • Théorie de la complexité computationnelle
4. Applications potentielles :
   • Protocoles basés sur les groupes en cryptographie
   • Calcul du groupe fondamental en topologie
   • Théorie des automates

Références (Références clés)

12 L. Ciobanu, S. Hermiller, D. Holt, S. Rees. Conjugacy languages in groups. Israel J. Math., 211:311–347, 2016.

• Base directe de cet article, définissant les langages de conjugaison pour le cas $U = G$

10 A. Carvalho, P. V. Silva. Geodesic languages for rational subsets and conjugates in virtually free groups. arXiv:2410.20412v2, 2024.

• Preuve de la nature sans contexte de $\alpha(U,V)\pi^{-1}$, améliorée en régularité dans cet article

23 M. Ladra, P. V. Silva. The generalized conjugacy problem for virtually free groups. Forum Math., 23:447–482, 2011.

• Résultat classique de décidabilité du problème de conjugaison généralisé pour les groupes virtuellement libres

25 D. E. Muller, P. E. Schupp. Groups, the theory of ends, and context-free languages. J. Comput. System Sci., 26(3):295–310, 1983.

• Théorème de Muller-Schupp : le problème des mots pour les groupes virtuellement libres est sans contexte

19 T. Herbst. On a subclass of context-free groups. RAIRO Inform. Théor. Appl., 25:255–272, 1991.

• Le problème des mots pour les groupes virtuellement cycliques est one-counter, introduction de la notation $C_\bullet$

9 A. Carvalho, C. F. Nyberg-Brodda. On linguistic subsets of groups and monoids. arXiv:2502.14329, 2025.

• Théorie systématique des sous-ensembles de langages, source des Théorèmes 2.2 et 2.3

Évaluation globale : Ceci est un article mathématique théorique de haute qualité qui généralise systématiquement la théorie des langages de conjugaison au cas des sous-ensembles, fournissant une caractérisation complète en théorie des langages pour plusieurs classes de groupes importantes. Sur le plan technique, il présente des innovations (langage de permutation, méthode d'automorphisme), et sur le plan théorique, il offre une profondeur (diversité des fonctions de croissance, préservation de classe de langage). Les principales insuffisances sont le cas général non résolu pour les groupes virtuellement abéliens et l'absence d'analyse de complexité computationnelle. L'article fournit des directions claires pour les recherches ultérieures et devrait avoir un impact durable sur la théorie combinatoire des groupes et la théorie des langages formels.