A virtually nilpotent group whose Green series is not D-finite

1. Énoncé du problème et contexte

La série de Green :
L'article étudie la série de Green (également appelée série de cogrowth), notée $\Gamma(G, S)(z)$, pour un groupe $G$ muni d'un multi-ensemble fini de générateurs $S$. Elle est définie par :
$$\Gamma(G, S)(z) = \sum_{\ell \geq 0} c_\ell z^\ell$$
où $c_\ell$ est le nombre de chemins fermés de longueur $\ell$ partant et aboutissant à l'élément neutre $e_G$ dans le graphe de Cayley de $(G, S)$.

La hiérarchie des séries :
L'auteur cherche à classer ces séries au sein d'une hiérarchie algébrique spécifique :
$$\text{Rationnelle} \subset \text{Algébrique} \subset \text{Diagonale de rationnelle} \subset \text{D-finie} \subset \text{D-algébrique}$$

• D-finie (Holonome) : Une série est D-finie si ses coefficients satisfont une relation de récurrence linéaire à coefficients polynomiaux.
• Résultats connus :
  • Rationnelle si et seulement si $G$ est fini.
  • Algébrique si $G$ est virtuellement libre.
  • Diagonale de rationnelle si $G$ est virtuellement $F_m \times \mathbb{Z}^n$.
  • Non D-finie pour les groupes moyennables à croissance super-polynomiale (Bell & Mishna).
  • Non D-finie pour des ensembles de générateurs spécifiques de $F_2 \times F_2$ et $SL_4(\mathbb{Z})$ (Garrabrant & Pak).

La question ouverte :
Pour les groupes virtuellement nilpotents, le consensus était incertain. Bien que les taux de croissance asymptotique des coefficients correspondent souvent à ceux des séries D-fines, il était inconnu si la série elle-même était toujours D-finie. Un résultat précédent de Pak et Soukup a montré que pour un groupe nilpotent spécifique $UT_m(\mathbb{Z})$ (avec $m \approx 10^8$), soit la série n'est pas une diagonale de série rationnelle, soit aucun algorithme n'existe pour la calculer. Ils n'ont pas prouvé que la série était strictement non D-finie.

Objectif :
Fournir le premier exemple d'un groupe virtuellement nilpotent avec un ensemble de générateurs spécifique dont la série de Green est non D-finie.

---

2. Le groupe et l'ensemble de générateurs

L'article se concentre sur le groupe $vH$, défini comme le produit semi-direct $H_3(\mathbb{Z}) \rtimes C_2$.

• Structure : $vH = \langle x, y, t \mid [x, [x, y]] = [y, [x, y]] = t^2 = e, txt = y \rangle$.
• Propriétés : Il est virtuellement nilpotent de classe 2. Il avait été précédemment identifié comme le premier exemple d'un groupe à croissance géodésique polynomiale qui n'est pas virtuellement abélien.
• Ensemble de générateurs : Le multi-ensemble spécifique utilisé est $S = \{x, x^{-1}, t, t, t, t, t, t, t, t\}$. Notez la multiplicité du générateur $t$ (huit copies).

Théorème principal (Théorème 1) :
La série de Green $\Gamma(vH, S)(z)$ est non D-finie.

Corollaire :
Puisque $vH$ s'injecte dans $SL_3(\mathbb{Z})$, il s'ensuit que $SL_3(\mathbb{Z})$ admet un multi-ensemble de générateurs pour lequel la série de Green est non D-finie. Cela étend les résultats précédents connus uniquement pour $SL_m(\mathbb{Z})$ avec $m \geq 4$.

---

3. Méthodologie

La stratégie de preuve adapte l'approche utilisée par Garrabrant et Pak pour $F_2 \times F_2$, en s'appuyant sur la complexité des sous-mots et les suites multiplicatives.

A. Réduction aux mots réduits

L'auteur relie d'abord la série de Green $\Gamma(z)$ à la série de croissance des mots « réduits » $R(z)$ (mots sans retournement immédiat $xx^{-1}$). En utilisant une variante de la formule de cogrowth de Bartholdi–Grigorchuk, il est démontré que $\Gamma(z)$ est D-finie si et seulement si $R(z)$ est D-finie.

B. Décomposition des chemins

L'ensemble des mots réduits $R$ est partitionné en trois sous-ensembles basés sur le nombre de générateurs $t$ :

1. $R_1$ : Mots avec peu de $t$ (au plus 4, ou 6 avec des $t$ consécutifs). Cet ensemble correspond à un langage contextuel et donne une série algébrique (donc D-finie).
2. $R_3$ : Mots avec beaucoup de $t$ (au moins 8). La contribution de ces termes est divisible par de fortes puissances de 2, les rendant négligeables modulo certaines puissances de 2.
3. $R_2$ : Mots avec exactement six $t$ et aucun $t$ consécutif. C'est l'ensemble critique.

C. Analyse combinatoire de $R_2$

Les chemins dans $R_2$ correspondent à des formes géométriques spécifiques dans le graphe de Cayley du sous-groupe de Heisenberg. Le dénombrement de ces chemins se réduit à la résolution d'un système diophantien pour les entiers $(a, b, c, d)$ :
$$a + b + c + d = n, \quad ab = cd$$
Le nombre de solutions, noté $|S_n|$, est analysé modulo des puissances de 2. L'auteur identifie des symétries (actions du groupe diédral $D_8$) pour simplifier le dénombrement.

D. Lien avec les fonctions multiplicatives

L'analyse révèle que le nombre de solutions $|S_n|$ (spécifiquement pour les indices impairs) est directement lié à une fonction $m(n)$, définie comme le plus grand entier tel que $m^2$ divise $n$.
L'auteur construit une série dérivée $S(z)$ dont les coefficients modulo 2 dépendent de la valeur d'une fonction multiplicative $f(n)$ :
$$f(n) = m\left(\frac{n}{2^{\nu_2(n)}}\right) \pmod 4$$
où $f(n) \in \{+1, -1\}$.

E. Argument de complexité des sous-mots

Le cœur de la preuve repose sur le Théorème 7 (Garrabrant–Pak) : si une série est D-finie, la complexité des sous-mots de ses coefficients modulo 2 doit être $o(2^n)$.
L'auteur prouve le Théorème 9 : pour la fonction multiplicative spécifique $f(n)$ construite ci-dessus, la complexité des sous-mots est maximale ($p_f(n) = 2^n$).

• Preuve du Théorème 9 : Utilise le théorème des restes chinois et la rareté des puissances de nombres premiers où $f(q) = -1$ pour montrer que n'importe quel motif de $\pm 1$ de longueur $n$ peut être réalisé par $f(x+i)$ pour un certain $x$.

Puisque les coefficients de la série dérivée $S(z)$ présentent une complexité de sous-mots maximale, $S(z)$ ne peut pas être D-finie. Puisque $S(z)$ est construite à partir de $R(z)$ en utilisant des opérations préservant la D-finie (extraction de termes pairs/impairs, combinaisons linéaires), la série originale $R(z)$ et par conséquent $\Gamma(z)$ ne peuvent pas être D-fines.

---

4. Contributions clés

1. Résolution du cas virtuellement nilpotent : L'article fournit le premier contre-exemple à la conjecture selon laquelle les séries de Green des groupes virtuellement nilpotents sont D-fines.
2. Raffinement de Pak-Soukup : Il renforce le résultat de Pak et Soukup en prouvant que la série est strictement non D-finie (plutôt que simplement non diagonale de série rationnelle ou non calculable) pour un groupe virtuellement nilpotent.
3. Extension à $SL_3(\mathbb{Z})$ : En injectant $vH$ dans $SL_3(\mathbb{Z})$, le résultat étend le phénomène de non-D-finitude au groupe linéaire spécial en dimension 3 (auparavant connu uniquement pour $m \geq 4$).
4. Avancement méthodologique : L'article applique avec succès la technique de la « complexité des sous-mots des suites multiplicatives » à un cadre nilpotent, surmontant la difficulté que les taux de croissance asymptotique standards dans les groupes nilpotents imitent généralement le comportement D-finie.

---

5. Importance et perspectives futures

• Impact théorique : Ce résultat remet en question l'intuition selon laquelle les groupes géométriques « bienveillants » (comme les nilpotents) produisent toujours des fonctions génératrices « bienveillantes ». Il met en évidence que les propriétés arithmétiques de la structure du groupe (spécifiquement l'interaction entre le générateur $t$ et le sous-groupe de Heisenberg) peuvent induire un comportement chaotique dans la série de cogrowth.
• Problèmes ouverts :
  • Le groupe de Heisenberg discret $H_3(\mathbb{Z})$ : L'article note que l'astuce spécifique consistant à ajouter plusieurs copies d'un générateur ($t$) utilisée ici ne s'applique pas immédiatement à $H_3(\mathbb{Z})$ lui-même. Étendre le résultat à $H_3(\mathbb{Z})$ reste un défi ouvert et significatif.
  • Fréquences asymptotiques : L'auteur mentionne qu'une preuve alternative utilisant les densités asymptotiques des nombres sans facteur carré reposerait sur la conjecture non prouvée que $\pi^2$ et la constante de Catalan $G$ sont linéairement indépendants sur $\mathbb{Q}$.
• Contexte plus large : Le résultat suggère que la frontière entre les séries D-fines et non D-fines en théorie des groupes est plus complexe qu'on ne le pensait, en particulier pour les groupes qui sont « proches » d'être abéliens ou nilpotents.

En résumé, l'article de Bodart utilise une interaction sophistiquée entre la théorie des groupes combinatoire, la théorie des nombres (fonctions multiplicatives) et la théorie des langages formels pour démontrer que même dans le monde relativement calme des groupes virtuellement nilpotents, les séries de Green peuvent présenter une complexité maximale.