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

Dans 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 ℂ

L'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 f_s ;
• cet espace vectoriel est canoniquement muni d'un produit hermitien $\langle \cdot |\cdot \rangle$ défini par :$\forall f,h\in \mathbb {C} ^{G},\quad \langle f|h\rangle ={\frac {1}{g}}\sum _{s\in G}{\overline {f(s)}}h(s).$Ce produit hermitien confère à ℂ^G une structure d'espace hermitien, noté ℓ²(G) ;
• cet espace vectoriel est aussi muni du produit de convolution ∗, défini par :$\forall (a_{s})_{s\in G},(b_{t})_{t\in G}\in \mathbb {C} ^{G}\quad \left(\sum _{s\in G}a_{s}\delta _{s}\right)*\left(\sum _{t\in G}b_{t}\delta _{t}\right)=\sum _{s,t\in G}a_{s}b_{t}\delta _{s+t}$.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

Le 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 ℓ²(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

Égalité de Bessel-Parseval

Le cas d'égalité de l'inégalité de Bessel dans un espace hermitien montre que tout élément

$a=\sum _{s\in G}a_{s}\delta _{s}\in \ell ^{2}(G)$

se décompose sur la base orthonormée Ĝ sous la forme suivante :

${\text{en notant}}\quad a_{\chi }=\langle \chi \mid a\rangle ={\frac {1}{g}}\sum _{s\in G}{\overline {\chi (s)}}~a_{s},\quad {\text{on a}}\quad a=\sum _{\chi \in {\widehat {G}}}a_{\chi }\chi \quad {\text{donc}}\quad \|a\|^{2}=\sum _{\chi \in {\widehat {G}}}|a_{\chi }|^{2}$.

Transformée de Fourier

La transformée de Fourier de cet élément $a$ de ℓ²(G) est l'application

${\widehat {a}}:{\widehat {G}}\to \mathbb {C}$

définie par :

${\widehat {a}}(\chi )=ga_{\chi }=\sum _{s\in G}{\overline {\chi (s)}}a_{s}$.

Ceci définit une application linéaire, la transformation de Fourier ⌃ : ℓ²(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é :

$\forall a\in \ell ^{2}(G)\quad a={\frac {1}{g}}\sum _{\chi \in {\widehat {G}}}{\widehat {a}}(\chi )\chi$.

Produit de convolution

Le choix ci-dessus de multiplier $a_{\chi }$ par $g$ 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 :

$\forall a,b\in \mathbb {C} [G]\quad {\widehat {a*b}}={\hat {a}}\,{\hat {b}}$.

Démonstration

${\begin{aligned}\forall \chi \in {\widehat {G}}\qquad {\widehat {a*b}}(\chi )&=\sum _{u\in G}{\overline {\chi (u)}}(a*b)(u)\\&=\sum _{u\in G}{\overline {\chi (u)}}\left(\sum _{s,t\in G,s+t=u}a_{s}b_{t}\right)\\&=\sum _{s,t\in G}{\overline {\chi (s+t)}}a_{s}b_{t}\\&=\left(\sum _{s\in G}{\overline {\chi (s)}}a_{s}\right)\left(\sum _{t\in G}{\overline {\chi (t)}}b_{t}\right)\\&={\hat {a}}(\chi ){\hat {b}}(\chi ).\end{aligned}}$

Égalité de Parseval

Faire de la bijection linéaire ⌃ : ℓ²(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 :

$\forall f,h\in \mathbb {C} ^{\widehat {G}}\quad \langle f\mid h\rangle ={\frac {1}{g^{2}}}\sum _{\chi \in {\widehat {G}}}{\overline {f(\chi )}}h(\chi )$.

On remarquera que ce produit hermitien correspond à la mesure de Haar sur Ĝ de masse ¹⁄_g, alors que celui introduit pour définir ℓ²(G) correspondait à la mesure de Haar sur G de masse 1. On notera cependant ℓ²(Ĝ) l'espace ℂ^Ĝ muni du produit hermitien ci-dessus. On obtient ainsi :

Avec la définition ci-dessus de ℓ²(Ĝ), la transformation de Fourier

${\widehat {}}:\ell ^{2}(G)\to \ell ^{2}({\widehat {G}})$

est un isomorphisme d'espaces hermitiens. En particulier elle vérifie l'égalité suivante, dite de Parseval :

$\forall a,b\in \ell ^{2}(G)\quad \langle {\hat {a}}|{\hat {b}}\rangle _{\ell ^{2}({\hat {G}})}=\langle a|b\rangle _{\ell ^{2}(G)}$.

Orthogonal d'un sous-groupe

Soit 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 $0\to {\widehat {G/H}}\to {\widehat {G}}\to {\widehat {H}}\to 0$, due à l'injectivité du groupe divisible ℂ*.

Formule sommatoire de Poisson

Soit H un sous-groupe d'ordre h de G. Tout élément $a$ de ℓ²(G) vérifie la formule sommatoire de Poisson suivante :

$g\sum _{t\in H}a_{t}=h\sum _{\chi \in H^{\perp }}{\hat {a}}(\chi )$.

Démonstration

$g\sum _{t\in H}a_{t}=g^{2}\langle \sum _{t\in H}\delta _{t}\mid a\rangle _{\ell ^{2}(G)}=\sum _{t\in H}g^{2}\langle {\widehat {\delta _{t}}}\mid {\hat {a}}\rangle _{\ell ^{2}({\hat {G}})}=\sum _{t\in H,\chi \in {\widehat {G}}}{\overline {{\widehat {\delta _{t}}}(\chi )}}{\hat {a}}(\chi )=\sum _{\chi \in {\widehat {G}}}c_{\chi }{\hat {a}}(\chi )$

avec

$c_{\chi }=\sum _{t\in H}\chi (t)=h\langle 1\mid \chi _{|H}\rangle _{\ell ^{2}(H)}={\begin{cases}h\quad {\text{si}}\quad \chi _{|H}=1\\0\quad {\text{sinon.}}\end{cases}}$

Or la restriction de χ à H est égale au caractère 1 sur H si et seulement si χ appartient à l'orthogonal de H, ce qui termine la démonstration.

Applications

Arithmétique modulaire

Les 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 F_p = ℤ/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

Dans 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 F_p est un carré non nul, et associe -1 sinon.

L'image de la fonction symbole de Legendre sur le groupe multiplicatif de F_p 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 F_p. 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

Dans le reste de l'article p est un nombre premier impair.

Soit ψ un caractère du groupe additif (F_p, +) et χ un caractère du groupe multiplicatif (F_p*, .), alors la somme de Gauss associée à χ et ψ est le nombre complexe, ici noté G(χ, ψ) et défini par :

$G(\chi ,\psi )=\sum _{x\in F_{p}^{*}}\chi (x)\psi (x)$.

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 χ à F_p 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 ψ à F_p* 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

Les 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

$\left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{\frac {(p-1)(q-1)}{4}}$.

Ce théorème est démontré dans l'article Somme de Gauss.

Caractère de Dirichlet

Pour 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

Un 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

Pour 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

Sur 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 F_q de cardinal q. Le symbole ${\hat {V}}$ désigne le groupe dual de V, χ₀ un caractère non trivial du groupe additif de F_q 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 $V^{*}\to {\hat {V}},f\mapsto \chi _{0}\circ f$ 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 χ₀∘f est, comme χ₀, non trivial. Les deux groupes ayant même ordre qⁿ, ce morphisme injectif est bijectif.

Par composition, on en déduit :

Le morphisme de groupes $U:V\to {\hat {V}}$ défini par

$\forall x,y\in V\quad U_{x}(y)=\chi _{0}(\langle x\mid y\rangle )$

est un isomorphisme.

Orthogonalité relativement à la dualité de Pontryagin

Soit 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 ${\hat {V}}$ 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 à (χ₀, < | >)^[Quoi ?] comme le sous-groupe S° := U⁻¹(S^⊥) de V :

$S^{\circ }=\{x\in V\mid \forall y\in S\quad \chi _{0}(\langle x\mid y\rangle )=1\}$.

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 χ₀ 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

L'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 : ${\widehat {a}}(\chi ):=\sum _{y\in G}{\overline {\chi (y)}}a(y)$. La formule de Plancherel est $a={\frac {1}{g}}\sum _{\chi \in {\widehat {G}}}{\widehat {a}}(\chi )\chi$ et si ( , )_G désigne le produit hermitien canonique de l'espace vectoriel complexe ℂ[G], l'égalité de Parseval s'écrit : $({\hat {a}}|{\hat {b}})_{\widehat {G}}=|G|~(a|b)_{G}$.

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]} :

$\forall a\in \mathbb {C} [V]\quad \forall x\in V\quad {\hat {a}}(x):={\hat {a}}(U(x))=\sum _{y\in V}a(y)\chi _{0}(-\langle x\mid y\rangle )$.

L'égalité de Parseval se réécrit alors :

$\forall a,b\in \mathbb {C} [V]\quad ({\hat {a}}\mid {\hat {b}})=q^{n}(a\mid b)$

et la formule de Plancherel :

$\forall a\in \mathbb {C} [V]\quad \forall y\in V\quad a(y)={\frac {1}{q^{n}}}\sum _{x\in V}{\widehat {a}}(x)\chi _{0}(\langle x\mid y\rangle )$.

Formule sommatoire de Poisson

Si W est un sous-groupe de V et $a$ un élément de ℂ[V], alors la formule sommatoire de Poisson prend la forme suivante :

$\sum _{w\in W}a(w)={\frac {1}{|W^{\circ }|}}\sum _{w^{\circ }\in W^{\circ }}{\hat {a}}(w^{\circ })$.

Applications

Fonction booléenne

Il existe un cas particulier, celui où l'espace vectoriel est binaire, c'est-à-dire sur le corps à deux éléments F₂. 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

L'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

• 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

• Transformée de Fourier discrète
• Analyse harmonique non commutative

Lien externe

• 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

• 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