Petite activité en théorie des groupes

L'auteur de ce sujet a trouvé une solution à son problème.
Staff
Auteur du sujet

Bonjour !

J'ai sous la main un exercice (dont l'énoncé est simple mais la preuve et la recherche difficiles) en théorie des groupes. Je n'ai pas de correction, c'est donc un peu l'occasion de travailler ça ensemble.

En pré-requis, j'imagine qu'il est difficile de résoudre l'exercice sans un niveau L3 mais l'énoncé ne demande qu'à connaitre la notion de groupe et d'ordre d'un élément.


L'énoncé :

On rappelle que ${\rm GL}_n(\mathbf{Z})$ est l'ensemble des matrices de déterminant égal à $\pm 1$ et à coefficients entiers. On le voit comme un groupe en munissant cet ensemble de la multiplication matricielle (celle qu'on voit en algèbre linéaire).

Déterminer une borne (dépendante de $n$) de l'ordre d'une matrice d'ordre fini.


On pourra commencer par étudier le cas $n=2$. On peut montrer que les seuls ordres (finis) possibles sont $1,2,3,4$ ou $6$. En indication, on pourra s'intéresser aux valeurs propres de telles matrices.

J'espère que ça va intéresser. Si vous n'avez pas le niveau mais que vous avez tout de même envie de vous y pencher vous pouvez :

  • étudier uniquement le cas $n=2$ ;
  • essayer d'établir des modèles de matrices pour des dimensions supérieures ;
  • faire n'importe quoi d'autre en relation avec ce groupe !

Correction pour le cas $n=2$ (c'est ce que j'ai trouvé, il y a peut-être des détails à discuter) :

En fait ça marche pas :)

Correction (peut-être juste cette fois-ci) du cas $n=2$ :

On note $\nu_1,\nu_2$ les deux valeurs propres de $A$, une matrice d'ordre $\omega$ ($\omega$ est minimal).

Comme ${\rm Tr}(A) = \nu_1+\nu_2$ est entier, on en déduit qu'ils sont conjugués. Par définition, $\nu_1$ et $\nu_2$ sont des $\omega$-racine de l'unité. Donc $\nu_1$ est de la forme $\exp(i\pi 2k/\omega)$ et $\nu_2 = \bar{\nu_1}$.

Par minimalité de $\omega$, $k$ et $\omega/2$ sont premiers entre eux. En effet, un simple calcul montre sur la matrice triangulaire supérieure semblable (de diagonale égale à $\nu_1,\nu_2$) que si les éléments diagonaux sont égaux à $1$ (après mise à la puissance $p<\omega$) alors le triangle supérieur doit être égal à $0$ (sinon l'ordre ne peut être fini) et alors $p\geq\omega$.

Comme $|\nu_1|\leq 1$ on en déduit que $\nu_1+\nu_2\in \{-2,-1,0,1,2\}$ et donc $\omega$ est au plus égal à $6$ par la remarque précédente.

Édité par Holosmos

Ce n’est pas en répétant « Hom, Hom », qu’on démontre des théorèmes sérieux - Siegel Mon Twitter

+2 -0

Le polynôme caractéristique doit être à coefficients entiers, on le factorise et les valeurs propres doivent être racines de l'unité, et leur produit doit valoir ±1. On doit donc avoir un polynôme de cette forme avec des coefficients entiers (edit : donc le dernier coef = ±1). Réciproquement, un polynôme de cette forme à coefficients entiers produit une matrice compagnon par exemple qui va bien.

Il doit y avoir un lien avec les polynômes cyclotomiques. On peut peut-être conjecturer que les valeurs possibles sont $\varphi^{-1}([1,n])$ avec $\varphi$ l'indicatrice d'euler ? Enfin, je sais pas, il faut que j'étudie les polynômes cyclotomiques, je ne connais pas.

Merci de l'exo.

Édité par Couard anonyme

+1 -0

On rappelle que ${\rm GL}_n(\mathbf{Z})$ est l'ensemble des matrices de déterminant égal à $\pm 1$ et à coefficients entiers. On le voit comme un groupe en munissant cet ensemble de la multiplication matricielle (celle qu'on voit en algèbre linéaire).

Holosmos

J'ai été quelque peu étonné lorsque j'ai lu ceci ! Premièrement, on appelle ${\rm SL}_n$ l'ensemble des matrices de déterminant 1. ${\rm GL}_n$ étant défini comme étant l'ensemble des matrices dont le déterminant est différent de 0. Deuxièmement, ${\rm GL}_n(\mathbf{Z})$ n'est pas un groupe (à cause de l'inverse).

+0 -0
Staff
Auteur du sujet

Il me semble qu'avec cette définition on a bien des inverses, non ? En tout cas j'ai pas inventé l'énoncé et j'ai confiance en l'auteur (ce que je devrais pas dire si je veux paraître sérieux).

Ce n’est pas en répétant « Hom, Hom », qu’on démontre des théorèmes sérieux - Siegel Mon Twitter

+0 -0

${\rm SL}_n(\mathbf{Z})$ m'a l'air d'être un groupe. En effet, la méthode d'inversion de matrice par cofacteur demande de diviser les coefficients par le déterminant (qui est 1), donc on reste bien dans $\mathbf{Z}$.

+0 -0
Staff
Auteur du sujet

Il ne me paraît pas dingue de limiter ${\rm GL}_n(\mathbf{Z})$ aux éléments de déterminant $\pm 1$. L'intérêt premier de cet ensemble est d'être un groupe. Et puis ${\rm SL}$ limite un peu plus puisqu'on ne prend que du déterminant égal à $1$.

Plus généralement, j'ai l'habitude de noter ${\rm GL}_n(A)$ l'ensemble (qui est un groupe ici) des matrices de taille $n\times n$ à coefficients dans un anneau $A$ et dont le déterminant est inversible dans $A$.

Ce n’est pas en répétant « Hom, Hom », qu’on démontre des théorèmes sérieux - Siegel Mon Twitter

+0 -0

Pour moi la notation est standard.

Ma conjecture est fausse mais mon intuition avec les polynômes cyclotomiques était bonne. Si on note $O_n$ les ordres finis possibles pour $\mathrm{GL}_n(\mathbb Z)$, on a $\varphi^{-1}([1,n]) \subset O_n$. Comme il y a égalité dans le cas $n=2$, j'ai dit trop vite que peut-être c'était vrai pour tout $n$, mais on voit qu'avec $n=6$ cela devient faux (cf. plus loin).

Si un polynôme est à coefficients entiers et admet une racine primitive $n$ième de l'unité, alors le $n$ième polynôme cyclotomique divise ce polynôme (il est irréductible : il est le plus petit polynôme à coefficients entiers ayant cette racine). Comme on cherche des polynômes n'ayant que des racines de l'unité comme racines, on cherche un polynôme produit de polynômes cyclotomiques.

Réciproquement, tout produit de polynômes cyclotomiques fournit une matrice de $\mathrm{GL}_n(\mathbb Z)$ dont l'ordre est le lcm des « ordres » des polynômes cyclotomiques : on prend par exemple la matrice compagnon.

Par exemple, pour $n=6$, on peut obtenir une matrice d'ordre $\mathrm{lmc}(3,10) = 30$ car $\varphi(3) + \varphi(10) = 2+4 = 6$, alors que $\varphi(30) = 8 > 6$. On prend $(X^2 + X + 1) (X^4 - X^3 + X^2 - X + 1) = X^6 + X^4 - X^3 + X^2 + 1$. Sa matrice compagnon est

$$\begin{bmatrix} 0 & 0 & 0 & 0 & 0 & -1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & -1 \\ 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & -1 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ \end{bmatrix}$$

et elle est d'ordre 30. Ma conjecture est donc bien fausse, mais tous les ordres « atteignables » s'écrivent comme $\mathrm{lcm}(a_1,\dots,a_k)$ avec $\sum \varphi(a_i) = n$.

Reste à avoir le max. Mais l'exo demande juste une borne quelconque ? La borne est large ?

Si on se restreint aux déterminants 1, on trouve que l'on doit prendre un nombre pair de fois le facteur $X-1$.

edit bis : on peut être bourrin et prendre comme borne la suivante. On prend, pour chaque nombre premier $p \leq n+1$, le plus grand $\alpha$ tel que $\varphi(p^\alpha) = p^{\alpha-1} (p-1) \leq n$, et on prend le produit des $p^\alpha$. Voici ce que l'on trouve pour n=2,3,4,5 : borne=12,12,120,120.

[edit]

@Couard : le problème est qu'avec n=2 je n'ai pas l'impression que ta borne soit bonne. Si ?

Je ne vois pas… Pour $n=2$, ce que j'avais dit est juste il me semble. On obtient bien les ordres atteignables qu'il faut…

Édité par Couard anonyme

+1 -0
Staff
Auteur du sujet

Je ne vois pas… Pour n=2, ce que j'avais dit est juste il me semble. On obtient bien les ordres atteignables qu'il faut…

Ah j'avais mal lu, my bad.

J'ai pas examiné ta preuve en détails, je le ferai plus tard :)

Ce n’est pas en répétant « Hom, Hom », qu’on démontre des théorèmes sérieux - Siegel Mon Twitter

+0 -0

Pourrais-tu me dire si la borne que l'on est censé trouver grandit beaucoup plus vite que la borne minimale ou pas ? J'ai un truc qui commence par 12,12,120,120,2520 (pour 2,3,4,5,6).

edit : enfin, ça dépend de ce que l'on entend par « trouver une borne ». J'ai une expression avec une somme si on veut un truc calculable pas trop difficilement.

Édité par Couard anonyme

+0 -0
Staff
Auteur du sujet

Je n'en sais rien :-).

edit : j'ai pas regardé ta preuve, juste regardé les polynômes que tu utilises. Chu bien d'accord sur l'idée que tu as eu mais je pense que la borne est très grande, je m'attendais à moins honnêtement. Mais peut-être qu'elle est juste, je n'en sais rien.

Je travaillais sur une autre observation (dans la continuité de ce que je propose pour $n=2$) mais j'y arrive pas au bout. Si j'y arrive je devrais avoir un truc polynomial …

Édité par Holosmos

Ce n’est pas en répétant « Hom, Hom », qu’on démontre des théorèmes sérieux - Siegel Mon Twitter

+0 -0

J'ai vraiment pris le plus bourrin de ce que l'on peut faire avec ce à quoi j'étais arrivé (avec le lcm et $\varphi$). C'est sûrement pas optimal comme borne. Je trouve ce qui suit, mais c'est juste la continuité de ce que j'ai fait, je n'ai rien d'intéressant à ajouter.

Premièrement, il faut que chaque polynôme cyclotomique ne se retrouve qu'une fois dans le produit, sinon la matrice n'est pas forcément diagonalisable, mais ça ne change rien puisqu'on s'intéresse au max de l'ordre atteignable. Ça ne change même pas les ordres atteignables. On peut penser au produit de polynômes cyclotomiques différents comme la matrice qui contient autant de blocs « diagonaux » que de polynômes, et chaque bloc est la matrice compagnon d'un polynôme (avec des 0 autre part).

Il s'agit de maximiser, avec $p$ parcourant les nombres premiers inférieurs ou égaux à $n+1$, le produit $\prod_p p^{\alpha_p}$, sous contrainte $\sum_p p^{\alpha_p} \left( 1 - p^{-1} \right) \leq n$, en faisant varier les α sur ℕ. La somme-contrainte correspond au fait que le polynôme doit être de degré inférieur ou égal à $n$, et ce que l'on cherche à maximiser est le lcm des $p^\alpha$ : l'ordre de la matrice. Il faut cependant ajouter deux exceptions : si un α vaut 0, il faut en fait retirer complètement le nombre premier $p$ (i.e. ne pas laisser le $1 - p^{-1}$ tout seul dans la somme). De plus, si on ne « fusionne » jamais deux nombres premiers dans la somme, c'est parce que ce n'est jamais avantageux, mais ce n'est pas vrai dans le cas p=2 si α vaut 1 (auquel cas on le fusionne avec un autre nombre premier dans la somme).

Avec l'approche ci-dessus, on peut faire comme si les α étaient réels : ça devient facile de maximiser le produit et on obtient une borne inf en arrondissant les α à l'inférieur. En la calculant, la borne inf trouvée semble polynômiale, assymptotiquement, et même linéaire, mais la borne sup explose. On obtient comme borne sup $\frac{\left( \frac{n}{k} \right)^k}{(1-{p_1}^{-1})(1-{p_2}^{-1})\cdots(1-{p_k}^{-1})}$ (avec $k$ le nombre de nombres premiers inférieurs ou égaux à $n+1$ et $p_i$ le $i$ème de ces nombres). Et encore, cela en supposant que l'on utilise tous les nombres premiers à notre disposition, alors qu'il est souvent avantageux de ne pas prendre le dernier nombre premier (pour le cas continu, on cherche juste une borne sup). Edit : ça ne fonctionne pas pour $n=2$ puisque dans ce cas particulier, on fusionne le 2 avec le 3 dans la somme, comme dit plus haut. Avec $n=4$ ou $5$ par exemple, il ne faut pas compter le nombre premier $5$. Par contre, avec $n$ assez grand (par exemple ≥23 mais on peut améliorer), ça fonctionne toujours (le $p_k$ max tel que l'on obtienne le meilleur produit sous contrainte grandit plus vite que $n$, et comme on veut majorer le cas discret, on ne prend pas plus loin que $p_k=n+1$).

Je n'ai pas vérifié les détails mais l'idée générale devrait être bonne.

-

Si j'y arrive je devrais avoir un truc polynomial …

On voit que l'on ne pourra pas trouver de borne sup polynômiale, puisque par exemple dans les cas $n = 2^\alpha \times 1 + 3^\beta \times 2$, on peut avoir un élément d'ordre $2^{\alpha + 1} \times 3^{\beta + 1}$, et on peut réitérer la construction en incluant autant de nombres premiers que l'on veut : tout polynôme, quel que soit son degré, sera dépassé (ici on dépasse le degré 1 puisqu'on obtient un minorant de degré 2 edit : en fait non, on n'obtient pas un truc de degré 2, mais on dépasse quand même le degré 1). Attention cependant, on ne dépasse pas le degré $n$ juste en prenant $n$ nombres premiers.

Après, je ne vois pas trop comment généraliser ce que tu as fait sans tomber dans de gros calculs.

PS : je crois qu'il y a un bug avec les balises secret…

Édité par Couard anonyme

+1 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte