Analyse harmonique sur un groupe abélien fini
En mathématiques, l'analyse harmonique sur un groupe abélien fini est un cas particulier d'analyse harmonique correspondant au cas où le groupe est abélien et fini.
L'analyse harmonique permet de définir la notion de transformée de Fourier ou le produit de convolution. Elle est le cadre de nombreux théorèmes comme celui de Plancherel, l'égalité de Parseval ou la dualité de Pontryagin.
Le cas où le groupe est abélien et fini est le plus simple de la théorie, la transformée de Fourier se limite à une somme finie et le groupe dual est isomorphe au groupe d'origine.
L'analyse harmonique sur un groupe abélien fini possède de nombreuses applications, particulièrement en arithmétique modulaire et en théorie de l'information.
Contexte
modifierDans tout cet article, G désigne un groupe abélien d'ordre g, noté additivement, et ℂ le corps des nombres complexes ; si z désigne un nombre complexe, z désigne son conjugué.
Espace des applications de G dans ℂ
modifierL'ensemble ℂG des applications de G dans ℂ est muni de plusieurs structures :
- c'est un espace vectoriel complexe de dimension g, de base canonique (δs)s∈G, où δs désigne le symbole de Kronecker : δs(t) vaut 1 pour t=s et vaut 0 pour les autres t∈G. Les coordonnées dans cette base d'une application f sont les nombres complexes f(s), aussi notés fs ;
- cet espace vectoriel est canoniquement muni d'un produit hermitien défini par :
- cet espace vectoriel est aussi muni du produit de convolution ∗, défini par :
. Cette multiplication interne prolonge la loi du groupe G : δs∗δt = δs+t. Elle confère à ℂG une structure de ℂ-algèbre, appelée l'algèbre du groupe fini G et notée ℂ[G]. On démontre (mais ce ne sera pas utilisé dans cet article) que pour tout groupe fini G (abélien ou pas) ℂ[G] est un anneau semi-simple.
Groupe dual
modifierLe groupe dual de G, noté Ĝ, est constitué des caractères de G, c'est-à-dire des morphismes de G dans le groupe multiplicatif ℂ*.
Il forme un groupe multiplicatif isomorphe (non canoniquement) au groupe additif G.
Il est inclus dans ℂG et forme une base orthonormée de ℓ2(G), ce qui justifie a posteriori le choix du produit hermitien sur ℂG.
Tout groupe abélien fini est canoniquement isomorphe à son bidual (le dual de son dual). Cette propriété se généralise sous le nom de dualité de Pontryagin.
Théorie de l'analyse harmonique
modifierÉgalité de Bessel-Parseval
modifierLe cas d'égalité de l'inégalité de Bessel dans un espace hermitien montre que tout élément
se décompose sur la base orthonormée Ĝ sous la forme suivante :
Transformée de Fourier
modifierLa transformée de Fourier de cet élément de ℓ2(G) est l'application
définie par :
Ceci définit une application linéaire, la transformation de Fourier ⌃ : ℓ2(G) → ℂĜ, dont les principales propriétés sont détaillées ci-dessous, mais dont on peut déjà remarquer qu'elle est bijective, puisque les deux espaces sont de dimension g et que l'égalité de Bessel-Parseval, réécrite sous la forme suivante appelée inversion de Plancherel, assure l'injectivité :
Produit de convolution
modifierLe choix ci-dessus de multiplier par dans la définition de la transformée de Fourier assure sa compatibilité avec le produit de convolution ∗, défini dans la section « Espace des applications de G dans ℂ » (voir supra) :
Soient a et b deux éléments de l'algèbre du groupe G, la transformée de Fourier de a∗b est le produit de celles de a et b :
.
Égalité de Parseval
modifierFaire de la bijection linéaire ⌃ : ℓ2(G) → ℂĜ un isomorphisme d'espaces hermitiens revient à choisir sur ℂĜ l'unique produit hermitien pour lequel la base (gδχ)χ∈Ĝ (transformée de Fourier de la base orthonormée Ĝ) est orthonormée. On pose donc :
On remarquera que ce produit hermitien correspond à la mesure de Haar sur Ĝ de masse 1⁄g, alors que celui introduit pour définir ℓ2(G) correspondait à la mesure de Haar sur G de masse 1. On notera cependant ℓ2(Ĝ) l'espace ℂĜ muni du produit hermitien ci-dessus. On obtient ainsi :
Avec la définition ci-dessus de ℓ2(Ĝ), la transformation de Fourier
est un isomorphisme d'espaces hermitiens. En particulier elle vérifie l'égalité suivante, dite de Parseval :
.
Orthogonal d'un sous-groupe
modifierSoit H un sous-groupe de G, nous appellerons groupe orthogonal de H, et noterons H⊥, le sous-groupe de Ĝ constitué des caractères dont le noyau contient H.
D'après les théorèmes d'isomorphisme :
- H⊥ est isomorphe au dual du groupe quotient G/H.En effet, H⊥ est l'ensemble des caractères de G qui se factorisent par G/H, donc c'est l'image du plongement canonique du dual de G/H dans celui de G. Ceci fournit une première preuve du fait que H⊥ est bien un sous-groupe de Ĝ, et montre de plus que son ordre est égal au quotient de l'ordre de G par celui de H.
- Le groupe quotient Ĝ/H⊥ est isomorphe à Ĥ.En effet, H⊥ est le noyau du morphisme canonique de restriction, de Ĝ dans Ĥ, ce qui fournit un morphisme injectif de Ĝ/H⊥ dans Ĥ, et ce morphisme est aussi surjectif par un argument de cardinalité.
Les deux énoncés ci-dessus peuvent aussi se déduire de l'exactitude de la suite , due à l'injectivité du groupe divisible ℂ*.
Formule sommatoire de Poisson
modifierSoit H un sous-groupe d'ordre h de G. Tout élément de ℓ2(G) vérifie la formule sommatoire de Poisson suivante :
.
Applications
modifierArithmétique modulaire
modifierLes premières utilisations historiques des caractères ont pour objectif l'arithmétique. Le symbole de Legendre est un exemple de caractère sur le groupe multiplicatif du corps fini Fp = ℤ/pℤ où ℤ désigne l'anneau des entiers relatifs et p un nombre premier impair.
Il est utilisé pour le calcul des sommes de Gauss ou des périodes de Gauss. Ce caractère est à la base d'une démonstration de la loi de réciprocité quadratique.
Symbole de Legendre
modifierDans ce paragraphe p désigne un nombre premier impair. G est ici le groupe ℤ/pℤ. Le symbole de Legendre désigne la fonction qui, à un entier a, associe 0 si a est un multiple de p, associe 1 si la classe de a dans Fp est un carré non nul, et associe -1 sinon.
L'image de la fonction symbole de Legendre sur le groupe multiplicatif de Fp correspond au caractère à valeurs dans[pas clair] l'ensemble {-1, 1}.
En effet, le symbole de Legendre est défini sur ℤ. Cette fonction est constante sur les classes d'entiers modulo p ; elle est donc définie sur le groupe multiplicatif de Fp. Sur ce groupe, le symbole de Legendre prend ses valeurs dans l'ensemble {-1, 1} et est un morphisme de groupes, car le symbole de Legendre est un caractère de Dirichlet.
Les démonstrations sont données dans l'article associé.
Somme de Gauss
modifierDans le reste de l'article p est un nombre premier impair.
Soit ψ un caractère du groupe additif (Fp, +) et χ un caractère du groupe multiplicatif (Fp*, .), alors la somme de Gauss associée à χ et ψ est le nombre complexe, ici noté G(χ, ψ) et défini par :
En termes de transformée de Fourier, on peut considérer l'application qui à χ associe G(χ, ψ) comme la transformée de Fourier du prolongement de χ à Fp par l'égalité χ(0) = 0 dans le groupe additif du corps et l'application qui à ψ associe G(χ, ψ) comme la transformé de Fourier de la restriction de ψ à Fp* dans le groupe multiplicatif du corps.
Les sommes de Gauss sont largement utilisées en arithmétique, par exemple pour le calcul des périodes de Gauss. Elles permettent notamment de déterminer la somme des valeurs du groupe des résidus quadratiques des racines p-ièmes de l'unité, et plus généralement de déterminer les racines du polynôme cyclotomique d'indice p.
Loi de réciprocité quadratique
modifierLes sommes de Gauss ont une application historique importante : la loi de réciprocité quadratique, qui s'exprime de la manière suivante :
Si p et q sont deux nombres premiers impairs distincts, alors
.
Ce théorème est démontré dans l'article Somme de Gauss.
Caractère de Dirichlet
modifierPour démonter le théorème de la progression arithmétique, affirmant que toute classe inversible de l'anneau ℤ/nℤ contient une infinité de nombres premiers, Dirichlet généralise les travaux de Gauss et étudie systématiquement le groupe des caractères du groupe des inversibles d'un tel anneau.
L'utilisation de la transformée de Fourier est une étape clé de la démonstration. Les caractères de Dirichlet ont un rôle important dans la théorie analytique des nombres particulièrement pour analyser les racines de la fonction ζ de Rieman.
Cas particulier : espace vectoriel fini
modifierUn cas particulier est celui des espaces vectoriels sur un corps fini. Les propriétés des corps finis permettent d'établir les résultats de la théorie sous une forme légèrement différente. Ce cas est utilisé par exemple en théorie de l'information à travers l'étude des fonctions booléennes, correspondant au cas où le corps contient deux éléments. La théorie est utilisée pour résoudre des questions de cryptologie notamment pour les boîtes-S, ainsi que pour les chiffrements par flot. L'analyse harmonique sur un espace vectoriel fini intervient aussi dans le contexte de la théorie des codes et particulièrement pour les codes linéaires, par exemple pour établir l'identité de MacWilliams.
Dualité de Pontryagin
modifierPour tout groupe abélien localement compact G, le morphisme injectif canonique de G dans son bidual est bijectif. Si G est un groupe abélien fini, il existe même des isomorphismes (non canoniques) de G dans son dual. Dans le cas particulier où G est le groupe additif d'un espace vectoriel fini, c'est-à-dire un groupe abélien élémentaire (en), on peut construire comme suit certains de ces isomorphismes.
Isomorphisme fondamental
modifierSur n'importe quel espace vectoriel V de dimension finie, une forme bilinéaire〈 | 〉est non dégénérée si et seulement si l'application x ↦ 〈x〉est un isomorphisme de V dans son espace dual V*.
Dans cet article, V désigne un espace vectoriel de dimension finie n sur un corps fini Fq de cardinal q. Le symbole désigne le groupe dual de V, χ0 un caractère non trivial du groupe additif de Fq et〈 | 〉une forme bilinéaire non dégénérée sur V.
En ne considérant de l'espace vectoriel V* que son groupe additif, on a :
Le morphisme de groupes est un isomorphisme.
En effet, ce morphisme est injectif car de noyau trivial, puisque si f est une forme linéaire non nulle donc surjective, alors le caractère χ0∘f est, comme χ0, non trivial. Les deux groupes ayant même ordre qn, ce morphisme injectif est bijectif.
Par composition, on en déduit :
Le morphisme de groupes défini par
est un isomorphisme.
Orthogonalité relativement à la dualité de Pontryagin
modifierSoit S un sous-ensemble de V. Comme dans le cas général d'un groupe abélien fini, l'orthogonal de S est le sous-groupe S⊥ de constitué des caractères dont le noyau contient S. On définit de plus l'orthogonal de S relativement à[réf. nécessaire] la dualité de Pontryagin associée à (χ0, < | >)[Quoi ?] comme le sous-groupe S° := U−1(S⊥) de V :
On remarque que :
- l'orthogonal à gauche de S relativement à la forme bilinéaire est un sous-espace vectoriel de V inclus dans le sous-groupe S°. Il lui est égal dès que χ0 est injectif — c'est-à-dire dès que q est premier — mais aussi dès que S est un sous-espace vectoriel ;
- si la forme bilinéaire〈 | 〉est symétrique ou antisymétrique, S°° est le sous-groupe engendré par S ; en effet, ce sous-groupe H est inclus dans H°°, or l'ordre |H°| = |H⊥| de H° est égal à |V|/|H| et de même, |H°°| est égal à |V|/|H°| donc à |H|, si bien que H = H°° = S°°.
Transformée de Fourier
modifierL'algèbre d'un groupe fini est notée ℂ[G]. La transformation de Fourier, de ℂ[G] dans ℂ[Ĝ], est la bijection linéaire définie par : . La formule de Plancherel est et si ( , )G désigne le produit hermitien canonique de l'espace vectoriel complexe ℂ[G], l'égalité de Parseval s'écrit : .
Dans le cas G = V, l'isomorphisme U ci-dessus, de V dans son groupe dual, permet de transporter cette transformation de Fourier en une application de ℂ[V] dans ℂ[V], encore appelée transformation de Fourier et encore notée ^[réf. nécessaire] :
L'égalité de Parseval se réécrit alors :
et la formule de Plancherel :
Formule sommatoire de Poisson
modifierSi W est un sous-groupe de V et un élément de ℂ[V], alors la formule sommatoire de Poisson prend la forme suivante :
Applications
modifierFonction booléenne
modifierIl existe un cas particulier, celui où l'espace vectoriel est binaire, c'est-à-dire sur le corps à deux éléments F2. Dans ce contexte, il n'existe qu'un caractère non trivial, celui qui à l'unité associe –1. La transformée de Fourier prend alors une forme simple et porte le nom de transformée de Walsh.
Il possède de nombreuses applications en théorie des codes. Il sert par exemple en cryptographie pour assurer la sécurité d'un message à l'aide d'une boîte-S dans le cas des algorithmes à chiffrement symétrique.
Identité de MacWilliams
modifierL'analyse harmonique sur les espaces vectoriels finis est aussi utilisée pour les codes correcteurs, particulièrement dans le contexte des codes linéaires.
L'identité de MacWilliams est un exemple ; elle relie le polynôme énumérateur des poids, c'est-à-dire la distribution des poids de Hamming, d'un code linéaire et celui de son dual. Il sert pour l'étude de codes comme celui de Hamming.
Voir aussi
modifier- Cet article est partiellement ou en totalité issu de l'article intitulé « Analyse harmonique sur un espace vectoriel fini » (voir la liste des auteurs).
Articles connexes
modifierLien externe
modifier- C. Bachoc, Mathématiques discrètes de la transformée de Fourier, Université Bordeaux I
- A. Bechata, « Analyse harmonique sur les groupes finis commutatifs », p. 10-11
- Anthony Carbery, « Harmonic Analysis on Vector Spaces over Finite Fields », p. 4-5.
Ouvrages
modifier- Michel Demazure, Cours d'algèbre : primalité, divisibilité, codes [détail des éditions]
- André Warusfel, Structures algébriques finies, Hachette, 1971
- Gabriel Peyré, L'algèbre discrète de la transformée de Fourier, Ellipses, 2004