Réseau (géométrie)
86398
27993131
2008-03-31T10:15:22Z
Jean-Luc W
53231
/* Volume fondamental du réseau */Refonte du paragraphe
{{Voir homonymes|Réseau}}
En [[mathématiques]], et tout spécialement en [[géométrie]] et en théorie des [[groupe (mathématiques)|groupe]]s, un '''réseau''' de <math>\mathbb{R}^n</math> est un sous-groupe additif [[espace discret|discret]] de <math>\mathbb{R}^n</math> qui engendre <math>\mathbb{R}^n</math>. Tout réseau de <math>\mathbb{R}^n</math> peut être engendré en formant les combinaisons linéaires à coefficients [[entier relatif|entiers]] d'une base de <math>\mathbb{R}^n</math>.
Les réseaux ont de nombreuses application en mathématiques pures, tout particulièrement dans les [[algèbre de Lie|algèbres de Lie]] et en [[théorie des nombres]]. Ils apparaissent également en mathématiques appliquées et dans la résolution de problèmes informatiques, en cryptographie notamment. Leur structure discrète en fait un outil informatique et un objet d'études algorithmiques à part entière. Ils sont utilisés dans différents domaines de la physique : par exemple en [[cristallographie]], où les réseaux de dimension 3 permettent de modéliser la répartition d'atomes ou de molécules dans un [[cristal]].
== Exemples ==
Dans cet article les lettres ''R'' et ''Z'' désigne respectivement le [[corps (mathématiques)|corps]] des [[nombre réel|nombres réels]] et l'[[anneau (mathématiques)|anneau]] des [[entier relatif|nombres entiers]] et ''n'' un entier strictement positif. L'[[espace vectoriel]] ''R''<sup>n</sup> est munis d'une [[norme (mathématiques)|norme]], nommée ici ||.|| qui à un vecteur, associe la [[valeur absolue]] de sa plus grande coordonnée dans la [[base canonique]].
Un premier exemple simple de réseau de ''R''<sup>n</sup> est le sous-groupe ''Z''<sup>n</sup>.
Un exemple un peu plus compliqué est le [[réseau de Leech]] qui est un réseau de ''R''<sup>24</sup>. L'étude des réseaux de ''R''<sup>2</sup> est centrale dans l'étude des [[courbe elliptique|courbes elliptiques]] développée au XIXe siècle ; cette étude se généralise en dimension supérieure par la théorie des [[fonction abélienne|fonctions abéliennes]].
== Définitions ==
Une première définition est utile :
:* Un sous-ensemble ''E'' de ''R''<sup>n</sup> est dit '''discret''' si et seulement si l'intersection de ''E'' avec un [[espace compact]] est de cardinal fini.
:* Un '''Réseau''' Λ de ''R''<sup>n</sup> est un [[sous-groupe]] discret de ''R''<sup>n</sup> pour l'addition tel que le sous-espace vectoriel engendré par Λ soit égal à ''R''<sup>n</sup>.
La définition d'un réseau se généralise à tout espace vectoriel réel de dimension finie. Un réseau désigne dans ce cas un sous-groupe discret qui engendre l'espace entier.
== Propriétés ==
=== Structure ===
:* ''Un réseau de ''R''<sup>n</sup> est un [[groupe abélien de type fini|groupe abélien libre de type fini]] et de dimension ''n'' en tant que ''Z'' [[module sur un anneau|module]].''
Une autre manière d'exprimer cette propriété est la suivante :
:* ''Soit Λ un réseau de ''R''<sup>n</sup>, il existe une base (''b''<sub>i</sub>), pour ''i'' variant de 1 à ''n'' de ''R''<sup>n</sup> qui soit aussi une base de Λ en tant que ''Z'' module.''
Dans cette base, tout élément du réseau s'exprime de manière unique comme [[combinaison linéaire]] d'éléments de la base avec des coordonnées entières. Réciproquement, toute combinaison linéaire à coefficients entiers de la base est un élément du réseau. Soit Λ un réseau de ''R''<sup>n</sup> de base (''b''<sub>i</sub>). Le réseau s'exprime de la manière suivante :
<center><math>\Lambda = \left\{ \sum_{i=1}^n \lambda_i b_i \; | \; \lambda_i \in\Bbb{Z} \right\}</math></center>
Il est important que la famille (''b''<sub>i</sub>) soit libre dans ''R''<sup>n</sup> sans quoi on n'obtient pas nécessairement un réseau. Par exemple l'ensemble des combinaisons ''Z''-linéaires de 1 et de √2 ne forme pas un réseau car il s'agit d'un groupe dense dans ''R''.
{{boîte déroulante début|align=left|titre=Démonstration}}
:* '''Un réseau de ''R''<sup>n</sup> est un groupe abélien libre de type fini et de dimension ''n'' en tant que ''Z'' module :'''
Démontrons ce résultat par récurrence sur ''n''.
Si ''n'' est égal à ''un'', le réseau est non réduit au vecteur nul car il engendre ''R'' et il existe un vecteur ''c'' du réseau non nul. L'intersection du réseau moins le vecteur nul et de la boule de centre le vecteur nul et de rayon la norme de ''c'' est un ensemble fini non vide, il contient un élément de plus petite norme. Soit ''b'' un tel vecteur, par définition ''b'' est élément du réseau. Montrons que ''b'' engendre le réseau. Soit ''g'' un élément non nul du réseau et ''a'' le plus grand élément de ''Z'' en valeur absolue tel que la norme de ''a.b''<sub>i</sub> soit inférieure ou égale à celle de ''g''. La norme de l'élément du groupe ''a.b'' - ''g'' est strictement inférieure à celle de ''b'', la définition de ''b'' montre que ce vecteur est nul. On en déduit que ''g'' est égal à ''a.b'', ce qui termine la démonstration pour le cas où ''n'' est égal à ''un''.
Supposons la propriété démontrée à l'ordre ''n'' - 1 et démontrons là à l'ordre ''n''. Le réseau forme une famille génératrice de ''R''<sup>n</sup>, de toute famille génératrice, il est possible d'extraire une base, il existe donc une sous-famille du réseau de cardinal ''n'' qui engendre l'espace entier. Soit (''f''<sub>i</sub>), pour ''i'' variant de 1 à ''n'' une telle base. Soit ''S'' l'espace vectoriel engendré par (''f''<sub>i</sub>), pour ''i'' variant de 1 à ''n'' - 1. L'intersection du réseau et de ''S'' est un groupe discret engendrant ''S'', il existe une base (''b''<sub>i</sub>), pour ''i'' variant de 1 à ''n'' - 1 de ''S'' et de l'intersection du réseau et de ''S'', par hypothèse de récurrence.
Soit φ une [[forme linéaire]] nulle sur ''S'' tel que l'image du réseau par φ n'est pas réduite à ''zéro''. Une telle forme existe sinon le réseau n'engendrerait que l'espace ''S'' et pas l'espace entier. L'image par φ du réseau est un sous-groupe discret de ''R''. En effet, si cette image n'est pas discrète, il existe un nombre réel ''a'', point d'accumulation de l'image et une suite (''a''<sub>n</sub>) convergeante vers ''a'', composées de valeurs réelles distinctes deux à deux. Soit <math>\Delta</math> une droite vectoriel supplémentaire de ''S'', la restriction de la forme φ à Δ est un homéomorphisme bicontinu sur ''R'' , il existe ainsi une suite (''v''<sub>n</sub>) d'éléments du réseau et antécédents de (''a''<sub>n</sub>) par φ qui est bornée car la suite (''a''<sub>n</sub>) l'est. Les valeurs de la suite (''v''<sub>n</sub>) sont toutes distinctes car les élément de la suite (''a''<sub>n</sub>) le sont et il existe donc un compact contenant toutes tous les vecteurs ''v''<sub>n</sub> et en conséquence de cardinal infini, ce qui montre que le réseau n'est pas discret. Cette contradiction montre que l'image par φ du réseau est discrète. Puisque l'image par φ du réseau est un sous-groupe discret de ''R'' il existe un élément ''a'' de ''R'' tel que cette image soit égale à ''a.R'', ce résultat est en effet une conséquence de l'analyse pour ''n'' égal à ''un''. Soit ''b''<sub>n</sub> un vecteur du réseau tel que φ(''b''<sub>n</sub>) soit égal à ''a''. Par construction (''b''<sub>i</sub>), pour ''i'' variant de 1 à ''n'' forme une base de ''R''<sup>n</sup>, en effet, ''b''<sub>n</sub> est un vecteur qui n'est pas élément de ''S''.
Soit enfin un élément λ quelconque du réseau, l'élément λ s'exprime comme une combinaison linéaire de (''b''<sub>i</sub>).
<center><math>\lambda = \sum_{i=1}^{n-1} \lambda_i b_i + \lambda_n b_n\;</math></center>
L'image par φ de λ est égal à ''a''λ<sub>n</sub>, qui est un élément de ''a.R'', l'image du réseau par φ. on en déduit que λ<sub>n</sub> est entier. Le vecteur λ- λ<sub>n</sub>''b''<sub>n</sub> est élément du réseau et de ''S'', ce qui montre que les coordonnées λ<sub>i</sub> sont toutes entières. La base (''b''<sub>i</sub>), pour ''i'' variant de 1 à ''n'' de ''R''<sup>n</sup> est une famille génératrice du réseau. Comme elle est libre dans ''R''<sup>n</sup>, elle est aussi libre comme famille du réseau, ce qui termine la démonstration.
{{Boîte déroulante fin}}
=== Volume fondamental du réseau ===
Soit ''B''<sub>1</sub> et ''B''<sub>2</sub> deux bases distinctes d'un même réseau Λ un réseau de ''R''<sup>n</sup>. La [[matrice de passage]] d'une base dans l'autre est inversible dans ''Z''<sup>n</sup>. La formule des [[comatrice]]s montre que le [[déterminant (mathématiques)|déterminant]] de la matrice est un élément inversible de ''Z'', il est donc égal à +/- 1.
Réciproquement, soit ''M'' une [[matrice carrée]] ''n''x''n'' de déterminant égal à +/- 1, l'image d'une base par une telle matrice est encore une base du réseau. Une conséquence est que tout réseau de dimension strictement supérieure à ''un'' admet une infinité de bases. Cette propriété donne lieu à deux définitions :
:* Le '''[[domaine fondamental]] par rapport à une base ''B'' ''', si ''B'' est une base (''b''<sub>i</sub>) du réseau est l'ensemble des points ''P'' :
<center><math>P = \left\{ \sum_{i=1}^n \lambda_i b_i \; | \; \lambda_i \in [0,1[ \right\}</math></center>
On remarque de les ensemble ''v'' + ''P'', si ''v'' décrit l'ensemble du réseau est une [[partition (mathématiques)|partition]] de l'espace ''R''<sup>n</sup>. La mesure du volume d'un domaine fondamental est la valeur absolue du déterminant de l'application linéaire dont l'image de la base canonique est égal à ''B''. Comme la matrice de passage d'une base ''B''<sub>1</sub> vers une base ''B''<sub>2</sub> du réseau est de déterminant égal à ''un'' en valeur absolue, ces différents domaines ont même volume :
:* Le '''volume fondamental d'un réseau''' est le volume d'un [[parallélépipède]] formé par un domaine fondamental.
Ce qui permet d'exprimer la proposition suivante :
:* ''le volume fondamental d'un réseau est égal à la valeur absolue du déterminant de l'application linéaire dont l'image de la base canonique est égal à une base du réseau.''
Il existe une manière intrinsèque de définir le volume fondamental, le [[groupe de Lie]] ''R''<sup>n</sup> / Λ dispose d'une [[Mesure (mathématiques)|mesure]] canonique. Pour tout point ''p'' de ''R''<sup>n</sup> / Λ, il existe un ouvert de ''p'' tel que la projection canonique de ''R''<sup>n</sup> dans ''R''<sup>n</sup> / Λ est un difféomorphisme, ces [[difféomorphisme]]s permettent de définir la mesure. Le groupe de Lie est compact, sa mesure totale est égale au volume fondamental du réseau.
== Réseaux et ensembles convexes ==
Le [[théorème de Minkowski]] relie le nombre de points d'un réseau contenu dans une partie S [[ensemble convexe|convexe]] et symétrique par rapport à 0, au volume du réseau et de S. Le nombre de points du réseau contenu dans un [[polytope]] P dont les sommets sont des éléments du réseau est décrit par le [[polynôme d'Ehrhart]] de P. L'expression de certains des coefficients de ce polynôme font intervenir le volume du réseau. En dimension 2, l'expression précise est donnée par le [[théorème de Pick]].
== Problèmes algorithmiques dans les réseaux ==
Un réseau formant un ensemble discret, il existe dans tout réseau un plus court vecteur non nul. Ce vecteur dépend bien évidemment de la [[norme]] dont on munit l'espace. Ce problème (souvent nommé SVP, de l'anglais ''Shortest Vector Problem'') est connu pour être [[NP-difficile]] dans le cas de la [[norme euclidienne]]. Pour d'autres normes usuelles, rien n'est connu, mais on conjecture que le problème est au moins aussi difficile à résoudre.
Le problème non homogène associé est celui de trouver le vecteur d'un réseau le plus proche d'un vecteur donné dans <math>\mathbb{R}^n</math>. Il est souvent nommé CVP (de l'anglais ''Closest Vector Problem'') et est lui aussi NP-difficile pour la norme euclidienne.
Certaines bases sont mieux adaptées que d'autres pour travailler dans un réseau car elles sont formées de vecteurs courts et permettent donc de se promener localement aux alentours d'un point donné du réseau. On les appelle bases réduites et ces méthodes, [[réduction de réseau|réductions de réseau]]. Il existe plusieurs notions différentes de réductions mais la réduction LLL inventée par Lenstra, Lenstra et Lovász présente l'avantage d'être calculable en temps polynomial par l'[[algorithme LLL]]. Cet algorithme qui fournit une base de vecteurs ''assez'' courts a de multiples applications, notamment en [[cryptographie à clé publique]].
== Réseaux de dimension 2 ==
Il y a cinq type de réseaux en deux dimensions.
== Réseaux de dimension 3 ==
Les 14 types de réseaux de dimension 3 sont appelés les [[réseau de Bravais|réseaux de Bravais]]. Ils sont caractérisés par leurs [[groupe d'espace|groupes d'espaces]].
== Réseaux d'un espace vectoriel complexe ==
Un réseau de <math>\mathbb{C}^n</math> est un sous-groupe additif discret de <math>\mathbb{C}^n</math> qui engendre l'espace vectoriel réel de dimension 2n associé. Par exemple, les [[entier de Gauss|entiers de Gauss]] forment un réseau de <math>\mathbb{C}</math>.
Tout réseau de <math>\mathbb{R}^n</math> est un groupe abélien libre de [[rang d'un groupe abélien|rang]] n. Tout réseau de <math>\mathbb{C}^n</math> est un groupe abélien libre de rang 2n.
{{portail mathématiques}}
[[Catégorie:Réseau (mathématiques)|*]]
[[de:Gitter (Mathematik)]]
[[en:Lattice (group)]]
[[fa:توری (گروه)]]
[[ja:格子]]
[[nl:Tralie (wiskunde)]]
[[pl:Krata (algebra)]]