Soit :
\[ F = \left ( \begin{array}{ccc} 2 & -1 \\ 1 & 0 \\ \end{array} \right ) \] \[ G = \left ( \begin{array}{ccc} -1 & -1 \\ 1 & 0 \\ \end{array} \right ) \]Mon but est de "dénombrer" le groupe \( \langle F, G \rangle \) engendré par \( \{ F, G \} \), dans le sens exploratoire du mot "dénombrer".
Il suffit de montrer qu'il contient un sous-groupe isomorphe à \( \mathbb{Z} \).
Soit :
\[ I = \left ( \begin{array}{ccc} 1 & 0 \\ 0 & 1 \\ \end{array} \right ) \] \[ J = \left ( \begin{array}{ccc} 1 & -1 \\ 1 & -1 \\ \end{array} \right ) \]Montrons par récurrence que \( \forall n \in \mathbb{N}, F^n = I + n J\), autrement dit, que
\[ \forall n \in \mathbb{N}, F^n = \left ( \begin{array}{ccc} 1 + n & -n \\ n & 1 - n \\ \end{array} \right ) \]L'égalité se prolonge pour les \( n \lt 0 \) (même raisonnement, en itérant \( F^{-1} \) à la place de \( F \), je ne détaille pas). Tant et si bien que
\[ \forall n \in \mathbb{Z}, F^n = I + n J \] \[ \forall n \in \mathbb{Z}, F^n = \left ( \begin{array}{ccc} 1 + n & -n \\ n & 1 - n \\ \end{array} \right ) \]Tous les \( F^n \) sont distincts ; donc \( \langle F \rangle \) est isomorphe à \( \mathbb{Z} \) ; donc \( \langle F, G \rangle \) est infini.
Au sens mathématique du terme, nous avons dénombré \( \langle F,G \rangle \), et le résultat est \( \mbox{Card}(\langle F,G \rangle ) = \aleph_0 \), mais ce n'est pas ce qui nous intéresse.
Il suffit de calculer :
\[ G^2 = \left ( \begin{array}{ccc} -1 & -1 \\ 1 & 0 \\ \end{array} \right ) \left ( \begin{array}{ccc} -1 & -1 \\ 1 & 0 \\ \end{array} \right ) = \left ( \begin{array}{ccc} 0 & 1 \\ -1 & -1 \\ \end{array} \right ) \] \[ G^3 = \left ( \begin{array}{ccc} -1 & -1 \\ 1 & 0 \\ \end{array} \right ) \left ( \begin{array}{ccc} 0 & 1 \\ -1 & -1 \\ \end{array} \right ) = \left ( \begin{array}{ccc} 1 & 0 \\ 0 & 1 \\ \end{array} \right ) = I \]Il en ressort que
\[ G^{-1} = G^2 \]Pour ce qui est des notations, nous préférons utiliser \( G^{-1} \).
Fait remarquable, l'une des formules vues plus haut pour \( F \) est valide pour \( G \) aussi, mais à condition de la considérer modulo 3 :
\[ \forall n \in \mathbb{Z}, G^n = G^{n \% 3} = \left ( \begin{array}{ccc} (1 + n) \% 3 & (-n) \% 3 \\ n \% 3 & (1 - n) \% 3 \\ \end{array} \right ) \]où la fonction \( n \mapsto n \% 3 \) prend ses valeurs dans \( \{-1, 0, +1\} \) (et en particulier, \( 2 \% 3 = -1 \)).
Il est aisé de démontrer que \( F \) et \( G \) ont pour déterminant 1. Donc, toutes les matrices du groupe engendré par elles ont aussi pour déterminant 1.
On a vu que \( F \), \( G \), ainsi que leurs inverses, sont à coefficients entiers. Donc, toutes les matrices du groupe engendré par elles ont aussi des coefficients entiers.
Enfin, en termes imagés, le groupe étudié possède un élément (F) qui "avance en ligne droite" et un élément (G) qui "boucle" avec une période 3. Comment ces deux ingrédients antagonistes intéragissent-ils ?
Le programme PARI/GP que voici
\\ default(parisizemax,14G) i=Mat([1,0;0,1]) F=Mat([2,-1;1,0]) G=Mat([-1,-1;1,0]) Generators=[F,G,F^(-1),G^(-1)]; Fr=Set(i); V=Set(i) n=0 while(n<15,n++;N=List();foreach(Generators,X,foreach(Fr,Y,M=X*Y;listput(N,M)));listsort(~N);N=Set(N);Fr=setminus(N,V);V=setunion(V,N);print(#Fr))
(que l'on peut tester en ligne sur la page Try GP in your browser) implémente une exploration du groupe \( \langle F, G \rangle \).
Le principe est celui d'un parcours de graphe en largeur d'abord. La matrice \( I \) est le "germe", i.e. est la frontière initiale avec l'inconnu.
En itérant la multiplication d'éléments de la frontière par \( F \), \( F^{-1} \), \( G \), ou \( G^{-1} \), on génère des éléments dont certains sont nouveaux, d'autres pas.
On fait évoluer les connaissances en tenant à jour les ensembles de matrices "visitées" et "frontière" en conséquence.
Le résultat concret fourni par ce programme est le nombre \( a(n) \) d'éléments de \( \langle F, G \rangle \) situés à distance \( n \) dans ce graphe d'exploration, pour \( n \leq 15 \) :
\[ \begin{array}{rcr} a(0) & = & 1 \\ a(1) & = & 4 \\ a(2) & = & 10 \\ a(3) & = & 26 \\ a(4) & = & 66 \\ a(5) & = & 170 \\ a(6) & = & 434 \\ a(7) & = & 1114 \\ a(8) & = & 2850 \\ a(9) & = & 7306 \\ a(10) & = & 18706 \\ a(11) & = & 47930 \\ a(12) & = & 122754 \\ a(13) & = & 314474 \\ a(14) & = & 805490 \\ a(15) & = & 2063386 \\ \end{array} \]Comment prouver qu'il s'agit de la suite OEIS A277236 ?
Par rapport à la définition de A277236 donnée sur le site web OEIS, on voit des correspondances évidentes avec notre problème,
Prouver \( a(n) = \mbox{A277236}(n) \) revient à prouver qu'il n'existe pas fondamentalement d'autre égalité que \( G^3 = I \), autrement dit que les matrices que l'on obtient par un produit matriciel de la forme
\[ G^{\epsilon_0} F^{z_1} G^{\epsilon_1} F^{z_2} \dots F^{z_n} G^{\epsilon_n} \]sont distinctes, dès lors que les tuples
\[ \left ( \begin{array}{l} \epsilon_0 \in \{ -1, 0, 1 \} \\ z_1 \in \mathbb{Z}^* \\ \epsilon_1 \in \{ -1, 1 \} \\ z_2 \in \mathbb{Z}^* \\ \epsilon_2 \in \{ -1, 1 \} \\ \cdots \\ \epsilon_{n-1} \in \{ -1, 1 \} \\ z_n \in \mathbb{Z}^* \\ \epsilon_n \in \{ -1, 0, 1 \} \end{array} \right ) \]sont eux-mêmes distincts. Comment prouver cela ?
Pour continuer d'expérimenter, dans la même veine que le programme PARI/GP ci-dessus, on peut utiliser ce programme AWK. Il génère les données mettant en regard :
=1,0,0,1 G=-1,-1,1,0 F=2,-1,1,0 f=0,1,-1,2 g=0,1,-1,-1 GF=-3,1,2,-1 Gf=1,-3,0,1 fg=-1,-1,-2,-3 gf=-1,2,1,-3 fG=1,0,3,1 FG=-3,-2,-1,-1 ff=-1,2,-2,3 Fg=1,3,0,1 gF=1,0,-3,1 FF=3,-2,2,-1
Voici un listing plus long de ces données.
Un exemple frappant de données produites :
gfgFFFGFGFGF=1057,-387,-1494,547 fgfgfgfffGFG=547,387,1494,1057 GFGfffgfgfgf=547,-1494,-387,1057 FGFGFGFFFgfg=1057,1494,387,547
Mis en forme :
| \[ gfgFFFGFGFGF = \left ( \begin{array}{ccc} 1057 & -387 \\ -1494 & 547 \\ \end{array} \right ) \] | \[ GFGfffgfgfgf = \left ( \begin{array}{ccc} 547 & -1494 \\ -387 & 1057 \\ \end{array} \right ) \] |
| \[ FGFGFGFFFgfg = \left ( \begin{array}{ccc} 1057 & 1494 \\ 387 & 547 \\ \end{array} \right ) \] | \[ fgfgfgfffGFG = \left ( \begin{array}{ccc} 547 & 387 \\ 1494 & 1057 \\ \end{array} \right ) \] |
Y aurait-il donc des correspondances entre les transformations sur les mots et les transformations sur les matrices ? Tentons de démontrer cela.
Notons les mots comme des chaînes de caractères informatiques, avec des guillemets. Exemple : "FgfffG".
Notons la concaténation de mots comme celle de chaînes de caractères dans certains langages informatiques, avec le symbole +. Exemple : "Fgf" + "ffG" = "FgfffG".
Soit \( \lambda \) la fonction qui prend un mot en entrée et rend en sortie ce mot mais avec chaque lettre inversée (en casse) (\( F \leftrightarrow f, G \leftrightarrow g \)). Par exemple,
\[ \lambda(\mbox{"FffFg"}) = \mbox{"fFFfG"} \]Soit \( \omega \) la fonction qui prend un mot en entrée et rend en sortie ce mot mais dans l'ordre inverse des lettres. Par exemple,
\[ \omega(\mbox{"ffffGffgfGF"}) = \mbox{"FGfgffGffff"} \]Soit \( L \) la transformation matricielle :
\[ L\left( \left ( \begin{array}{ccc} a & b \\ c & d \\ \end{array} \right ) \right ) = \left ( \begin{array}{ccc} d & c \\ b & a \\ \end{array} \right ) \]Soit \( O \) la transformation matricielle :
\[ O\left( \left ( \begin{array}{ccc} a & b \\ c & d \\ \end{array} \right ) \right ) = \left ( \begin{array}{ccc} a & -c \\ -b & d \\ \end{array} \right ) \]Soit \( E \) l'évaluation d'un mot en son résultat matriciel (en quelque sorte, c'est l'opération qui enlève les guillemets, pour passer par exemple de "FG" à FG).
Soit \( \mathcal{L} \) l'ensemble des mots \( m \) tels que \( E(\lambda(m)) = L(E(m)) \)
Soit \( \mathcal{O} \) l'ensemble des mots \( m \) tels que \( E(\omega(m)) = O(E(m)) \)
Le mot vide "" est dans \( \mathcal{L} \), car trivialement, il correspond par \( E \) à la matrice identité \( I \), et \( L(I) = I \).
Le mot "F" est dans \( \mathcal{L} \). Preuve :
\[ E(\lambda(\mbox{"}F\mbox{"})) = E(\mbox{"}f\mbox{"}) = f = F^{-1} = \left ( \begin{array}{ccc} 0 & 1 \\ -1 & 2 \\ \end{array} \right ) \] \[ L(E(\mbox{"}F\mbox{"})) = L(F) = L \left ( \left ( \begin{array}{ccc} 2 & -1 \\ 1 & 0 \\ \end{array} \right ) \right ) = \left ( \begin{array}{ccc} 0 & 1 \\ -1 & 2 \\ \end{array} \right ) \]De même, les mots "f", "G", "g" sont dans dans \( \mathcal{L} \).
(i) La multiplication matricielle étant associative, l'ordre dans lequel on multiplie les matrices n'a pas d'importance.
Ainsi, quels que soient les mots \( m_1 \) et \( m_2 \), le produit de leurs évaluations, \( E(m_1) E(m_2) \) est égal à l'évaluation de leur concaténation \( E(m_1 + m_2) \).
(ii) L'inversion des lettres commute trivialement avec la concaténation : \( \lambda(m_1 + m_2) = \lambda(m_1) + \lambda(m_2) \).
Soient \( m_1 \) et \( m_2 \) deux éléments de \( \mathcal{L} \). On a :
\[ E(\lambda(m_1 + m_2)) = E(\lambda(m_1) + \lambda(m_2)) = E(\lambda(m_1)) E(\lambda(m_2)) = L(E(m_1)) L(E(m_2)) \] \[ L(E(m_1 + m_2)) = L(E(m_1) E(m_2)) \]Posons :
\[ E(m_1) = \left ( \begin{array}{ccc} a & b \\ c & d \\ \end{array} \right ) \] \[ E(m_2) = \left ( \begin{array}{ccc} s & t \\ u & v \\ \end{array} \right ) \]Il vient, d'une part :
\[ L(E(m_1)) = \left ( \begin{array}{ccc} d & c \\ b & a \\ \end{array} \right ) \] \[ L(E(m_2)) = \left ( \begin{array}{ccc} v & u \\ t & s \\ \end{array} \right ) \] \[ L(E(m_1)) L(E(m_2)) = \left ( \begin{array}{ccc} d & c \\ b & a \\ \end{array} \right ) \left ( \begin{array}{ccc} v & u \\ t & s \\ \end{array} \right ) = \left ( \begin{array}{ccc} ct + dv & cs + du \\ at + bv & as + bu \\ \end{array} \right ) \]Et d'autre part :
\[ E(m_1) E(m_2) = \left ( \begin{array}{ccc} a & b \\ c & d \\ \end{array} \right ) \left ( \begin{array}{ccc} s & t \\ u & v \\ \end{array} \right ) = \left ( \begin{array}{ccc} as + bu & at + bv \\ cs + du & ct + dv \\ \end{array} \right ) \] \[ L(E(m_1) E(m_2)) = \left ( \begin{array}{ccc} ct + dv & cs + du \\ at + bv & as + bu \\ \end{array} \right ) \]Donc
\[ L(E(m_1)) L(E(m_2)) = L(E(m_1) E(m_2)) \]Donc
\[ E(\lambda(m_1 + m_2)) = L(E(m_1 + m_2)) \]Donc : \( m_1 + m_2 \) est dans \( \mathcal{L} \).
Nous venons de démontrer : \( \forall (m_1, m_2) \in \mathcal{L} ^2, (m_1 + m_2) \in \mathcal{L} \). Autrement dit que \( \mathcal{L} \) est stable par concaténation.
La conclusion qui s'impose après les 2 § précédents est que oui, l'inversion de la casse des lettres dans un mot à base de F, G, f, g revient bien à procéder à une symétrie centrale des coefficients dans la matrice correspondante.
Le mot vide "" est dans \( \mathcal{O} \), car trivialement, il correspond par \( E \) à la matrice identité \( I \), et \( O(I) = I \).
Le mot "F" est dans \( \mathcal{O} \). Preuve :
\[ E(\omega(\mbox{"}F\mbox{"})) = E(\mbox{"}F\mbox{"}) = F = \left ( \begin{array}{ccc} 2 & -1 \\ 1 & 0 \\ \end{array} \right ) \] \[ O(E(\mbox{"}F\mbox{"})) = O(F) = O \left ( \left ( \begin{array}{ccc} 2 & -1 \\ 1 & 0 \\ \end{array} \right ) \right ) = \left ( \begin{array}{ccc} 2 & -1 \\ 1 & 0 \\ \end{array} \right ) \]TODO
On a les égalités suivantes (démontrable par récurrence) :
\[ \forall n \in \mathbb{N}, (fG)^n = \left ( \begin{array}{ccc} 1 & 0 \\ 3n & 1 \\ \end{array} \right ) \] \[ \forall n \in \mathbb{N}, (Gf)^n = \left ( \begin{array}{ccc} 1 & -3n \\ 0 & 1 \\ \end{array} \right ) \] \[ \forall n \in \mathbb{N}, (gF)^n = \left ( \begin{array}{ccc} 1 & 0 \\ -3n & 1 \\ \end{array} \right ) \] \[ \forall n \in \mathbb{N}, (Fg)^n = \left ( \begin{array}{ccc} 1 & 3n \\ 0 & 1 \\ \end{array} \right ) \] \[ \forall n \in \mathbb{N}, G(fG)^n = (Gf)^n G = \left ( \begin{array}{ccc} -(3n+1) & -1 \\ 1 & 0 \\ \end{array} \right ) \] \[ \forall n \in \mathbb{N}, g(Fg)^n = (gF)^n g = \left ( \begin{array}{ccc} 0 & 1 \\ -1 & -(3n+1) \\ \end{array} \right ) \] \[ \forall n \in \mathbb{N}, F(gF)^n = (Fg)^n F = \left ( \begin{array}{ccc} (3n+2) & -1 \\ 1 & 0 \\ \end{array} \right ) \] \[ \forall n \in \mathbb{N}, f(Gf)^n = (fG)^n f = \left ( \begin{array}{ccc} 0 & 1 \\ -1 & (3n+2) \\ \end{array} \right ) \]Conjecture : les seules matrices pouvant contenir un coefficient nul sont ces matrices.
A POURSUIVRE...
LR, 18/04/2025