Réseau (géométrie)

Un article de Wikipédia, l'encyclopédie libre.

Pour les articles homonymes, voir Réseau.

En mathématiques, et tout spécialement en géométrie et en théorie des groupes, un réseau de \mathbb{R}^n est un sous-groupe additif discret de \mathbb{R}^n qui engendre \mathbb{R}^n. Tout réseau de \mathbb{R}^n peut être engendré en formant les combinaisons linéaires à coefficients entiers d'une base de \mathbb{R}^n.

Les réseaux ont de nombreuses application en mathématiques pures, tout particulièrement dans les 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.

Sommaire

[modifier] Exemples

Dans cet article les lettres R et Z désigne respectivement le corps des nombres réels et l'anneau des nombres entiers et n un entier strictement positif. L'espace vectoriel Rn est munis d'une 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 Rn est le sous-groupe Zn.

Un exemple un peu plus compliqué est le réseau de Leech qui est un réseau de R24. L'étude des réseaux de R2 est centrale dans l'étude des courbes elliptiques développée au XIXe siècle ; cette étude se généralise en dimension supérieure par la théorie des fonctions abéliennes.

[modifier] Définitions

Une première définition est utile :

  • Un sous-ensemble E de Rn est dit discret si et seulement si l'intersection de E avec un espace compact est de cardinal fini.
  • Un Réseau Λ de Rn est un sous-groupe discret de Rn pour l'addition tel que le sous-espace vectoriel engendré par Λ soit égal à Rn.

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.

[modifier] Propriétés

[modifier] Structure

Une autre manière d'exprimer cette propriété est la suivante :

  • Soit Λ un réseau de Rn, il existe une base (bi), pour i variant de 1 à n de Rn 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 Rn de base (bi). Le réseau s'exprime de la manière suivante :

\Lambda = \left\{ \sum_{i=1}^n \lambda_i b_i \; | \; \lambda_i \in\Bbb{Z} \right\}

Il est important que la famille (bi) soit libre dans Rn 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.

Démonstration
  • Un réseau de Rn 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.bi 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 Rn, 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 (fi), pour i variant de 1 à n une telle base. Soit S l'espace vectoriel engendré par (fi), 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 (bi), 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 (an) convergeante vers a, composées de valeurs réelles distinctes deux à deux. Soit Δ une droite vectoriel supplémentaire de S, la restriction de la forme φ à Δ est un homéomorphisme bicontinu sur R , il existe ainsi une suite (vn) d'éléments du réseau et antécédents de (an) par φ qui est bornée car la suite (an) l'est. Les valeurs de la suite (vn) sont toutes distinctes car les élément de la suite (an) le sont et il existe donc un compact contenant toutes tous les vecteurs vn 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 bn un vecteur du réseau tel que φ(bn) soit égal à a. Par construction (bi), pour i variant de 1 à n forme une base de Rn, en effet, bn 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 (bi).

\lambda = \sum_{i=1}^{n-1} \lambda_i b_i + \lambda_n b_n\;

L'image par φ de λ est égal à aλn, qui est un élément de a.R, l'image du réseau par φ. on en déduit que λn est entier. Le vecteur λ- λnbn est élément du réseau et de S, ce qui montre que les coordonnées λi sont toutes entières. La base (bi), pour i variant de 1 à n de Rn est une famille génératrice du réseau. Comme elle est libre dans Rn, elle est aussi libre comme famille du réseau, ce qui termine la démonstration.

 

[modifier] Volume fondamental du réseau

Soit B1 et B2 deux bases distinctes d'un même réseau Λ un réseau de Rn. La matrice de passage d'une base dans l'autre est inversible dans Zn. La formule des comatrices montre que le 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 nxn 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 (bi) du réseau est l'ensemble des points P :
P = \left\{ \sum_{i=1}^n \lambda_i b_i \; | \; \lambda_i \in [0,1[ \right\}

On remarque de les ensemble v + P, si v décrit l'ensemble du réseau est une partition de l'espace Rn. 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 B1 vers une base B2 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 Rn / Λ dispose d'une mesure canonique. Pour tout point p de Rn / Λ, il existe un ouvert de p tel que la projection canonique de Rn dans Rn / Λ est un difféomorphisme, ces difféomorphismes permettent de définir la mesure. Le groupe de Lie est compact, sa mesure totale est égale au volume fondamental du réseau.

[modifier] 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 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.

[modifier] 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 \mathbb{R}^n. 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é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.

[modifier] Réseaux de dimension 2

Il y a cinq type de réseaux en deux dimensions.

[modifier] Réseaux de dimension 3

Les 14 types de réseaux de dimension 3 sont appelés les réseaux de Bravais. Ils sont caractérisés par leurs groupes d'espaces.

[modifier] Réseaux d'un espace vectoriel complexe

Un réseau de \mathbb{C}^n est un sous-groupe additif discret de \mathbb{C}^n qui engendre l'espace vectoriel réel de dimension 2n associé. Par exemple, les entiers de Gauss forment un réseau de \mathbb{C}.

Tout réseau de \mathbb{R}^n est un groupe abélien libre de rang n. Tout réseau de \mathbb{C}^n est un groupe abélien libre de rang 2n.