Des rotations aux fréquences : Fourier sur un groupe cyclique

Le but du problème est de comprendre pourquoi une transformée de Fourier apparaît naturellement lorsqu'on étudie les rotations d'un polygone régulier. On attachera un nombre complexe à chaque sommet : une rotation déplacera alors ces valeurs d'un sommet à l'autre. On cherchera d'abord les fonctions non nulles pour lesquelles ce déplacement a un effet particulièrement simple : toutes les valeurs sont seulement multipliées par un même nombre complexe. On montrera que ces fonctions sont exactement, à une constante près, les fonctions $z\mapsto z^k$. Elles deviendront ensuite les briques élémentaires permettant de reconstruire une fonction quelconque ; les coefficients de cette reconstruction formeront sa transformée de Fourier discrète. Enfin, on comparera le nombre de sommets où la fonction est non nulle au nombre de coefficients de Fourier non nuls.

Dans tout le problème, on fixe un entier $n\geq 2$ et

$$\omega=e^{2i\pi/n},\qquad \mathbb U_n=\{1,\omega,\omega^2,\ldots,\omega^{n-1}\}.$$

On considère des fonctions $f:\mathbb U_n\to\mathbb C$.

I — Un polygone qui est aussi un groupe

1. On commence par préciser la structure de l'ensemble $\mathbb U_n$.

(a) Montrer que les éléments $1,\omega,\ldots,\omega^{n-1}$ sont deux à deux distincts et qu'ils sont exactement les racines $n$-ièmes de l'unité.

(b) Vérifier que $\mathbb U_n$ est stable par produit et par passage à l'inverse. En déduire que $(\mathbb U_n,\times)$ est un groupe fini. Montrer enfin que tout élément de $\mathbb U_n$ est une puissance de $\omega$. On dira que $\mathbb U_n$ est un groupe cyclique et que $\omega$ en est un générateur.

Éclairage. Multiplier un sommet $z$ par $\omega$ le fait passer au sommet suivant du polygone régulier. Comme toute rotation par un angle multiple de $2\pi/n$ s'écrit $z\mapsto\omega^jz$, la structure de groupe encode ici exactement les rotations du polygone.

II — Translater une fonction, c'est faire tourner son motif

Pour $a\in\mathbb U_n$, la multiplication $z\mapsto az$ fait tourner les sommets. Pour transporter avec eux les valeurs d'une fonction $f$, on définit

$$(\tau_af)(z)=f(a^{-1}z),\qquad z\in\mathbb U_n.$$

Ainsi, la valeur qui se trouvait au sommet $y$ se retrouve au sommet $ay$.

2. Soient $a,b\in\mathbb U_n$.

(a) Montrer que $\tau_a\tau_b=\tau_{ab}$, que $\tau_1$ est l'identité et que chaque $\tau_a$ est bijective.

(b) Montrer que, pour tout $j\in\{0,\ldots,n-1\}$,

$$\tau_{\omega^j}=(\tau_\omega)^j.$$

Vérifier également que $(\tau_\omega f)(\omega z)=f(z)$. Expliquer alors en quoi $\tau_\omega$ correspond à une rotation du motif d'un sommet vers le suivant et pourquoi l'étude de cette seule translation suffit pour retrouver toutes les autres rotations.

III — Les fonctions les plus simples sous rotation

On cherche maintenant une fonction non nulle $f$ pour laquelle la rotation d'un cran ne change pas la forme du motif, mais multiplie toutes ses valeurs par un même facteur complexe. On suppose donc qu'il existe $\lambda\in\mathbb C$ tel que

$$\tau_\omega f=\lambda f.$$

3. Sous cette hypothèse :

(a) Montrer que $\lambda\neq0$, que $f(1)\neq0$ et que, pour tout $j\in\{0,\ldots,n-1\}$,

$$f(\omega^j)=\lambda^{-j}f(1).$$

(b) En utilisant la question 2, montrer que $\lambda^n=1$. En déduire qu'il existe un unique $k\in\{0,\ldots,n-1\}$ et une constante $c\neq0$ tels que

$$f(z)=cz^k\qquad\text{pour tout }z\in\mathbb U_n.$$

Pour $k\in\{0,\ldots,n-1\}$, on note désormais

$$m_k(z)=z^k.$$

Ces fonctions seront appelées les modes du groupe cyclique.

(c) Montrer que, pour tout $a\in\mathbb U_n$,

$$\tau_am_k=a^{-k}m_k.$$

En déduire que la droite de fonctions $\{cm_k\,;\,c\in\mathbb C\}$ est stable par toutes les translations $\tau_a$ et que l'action de $\tau_a$ sur cette droite est entièrement décrite par le seul facteur $a^{-k}$.

Éclairage. C'est en ce sens précis que les modes $m_k$ sont adaptés aux translations : une opération qui permute en général toutes les valeurs d'une fonction devient, sur un mode, une simple multiplication par un nombre complexe.

IV — Séparer les modes par une somme géométrique

4. Pour $r\in\mathbb Z$, calculer

$$S_r=\sum_{j=0}^{n-1}\omega^{jr}.$$

On distinguera les cas $n\mid r$ et $n\nmid r$.

5. La somme précédente permet de séparer deux modes.

(a) Pour $k,\ell\in\{0,\ldots,n-1\}$, montrer que

$$\sum_{z\in\mathbb U_n}m_k(z)\,\overline{m_\ell(z)} =\begin{cases} n,&k=\ell,\\ 0,&k\neq\ell. \end{cases}$$

(b) En déduire que si

$$\sum_{k=0}^{n-1}c_km_k(z)=0\qquad\text{pour tout }z\in\mathbb U_n,$$

alors $c_0=\cdots=c_{n-1}=0$.

Éclairage. La relation de la question 5(a) est l'analogue complexe d'une relation d'orthogonalité. Plus tard, le produit scalaire permettra d'organiser ce type de calcul : des directions orthogonales se séparent sans interférer. Ici, tout est obtenu directement avec la conjugaison et une somme géométrique.

V — Faire apparaître la transformée de Fourier

La question 5 suggère un moyen d'extraire la contribution du mode $m_k$ dans une fonction quelconque : on multiplie par $\overline{m_k(z)}=z^{-k}$ puis on somme. On définit donc, pour $k\in\{0,\ldots,n-1\}$,

$$\widehat f(k)=\sum_{z\in\mathbb U_n}f(z)z^{-k}.$$

Le nombre $\widehat f(k)$ est le $k$-ième coefficient de Fourier discret. L'entier $k$ sera désormais appelé indice de fréquence.

6. Comprendre puis inverser cette transformation.

(a) Calculer $\widehat{m_r}(k)$ pour $r,k\in\{0,\ldots,n-1\}$.

(b) Montrer que, pour tout $z\in\mathbb U_n$,

$$f(z)=\frac1n\sum_{k=0}^{n-1}\widehat f(k)z^k.$$

Indication : utiliser la question 4.

(c) En déduire que toute fonction sur $\mathbb U_n$ se décompose de manière unique comme combinaison des modes $m_0,\ldots,m_{n-1}$, et préciser le coefficient de $m_k$ dans cette décomposition.

VI — Les translations après transformée de Fourier

7. Pour $a\in\mathbb U_n$, exprimer $\widehat{\tau_af}(k)$ en fonction de $\widehat f(k)$. Comparer ce qui se passe avant et après transformée de Fourier : que devient une translation du motif lorsqu'on regarde les coefficients de Fourier ?

Éclairage. Le gain est désormais visible : dans les valeurs $f(z)$, une translation déplace les données d'un sommet à l'autre ; dans les coefficients $\widehat f(k)$, elle agit séparément sur chaque fréquence par une simple multiplication. C'est exactement la simplification que les questions 2 et 3 cherchaient à faire apparaître.

VII — Une identité de conservation

8. Établir l'identité

$$\sum_{k=0}^{n-1}|\widehat f(k)|^2 =n\sum_{z\in\mathbb U_n}|f(z)|^2.$$

On pourra s'appuyer sur la question 4.

Éclairage. Cette formule est une forme discrète de l'identité de Parseval. Avec la normalisation choisie ici, elle dit que l'énergie totale de la fonction est conservée, à un facteur $n$ près, lorsqu'on passe des sommets aux fréquences. Dans le langage du produit scalaire, on l'interprétera comme une égalité de normes entre deux représentations d'un même objet.

VIII — Peut-on être concentré des deux côtés ?

On suppose désormais $f\not\equiv0$ et on pose

$$S=\operatorname{supp}f=\{z\in\mathbb U_n\,;\,f(z)\neq0\}, \qquad T=\operatorname{supp}\widehat f=\{k\in\{0,\ldots,n-1\}\,;\,\widehat f(k)\neq0\}.$$

9. On va comparer la taille de ces deux supports.

(a) Soient $x_1,\ldots,x_m$ des réels positifs. Montrer que

$$\left(\sum_{j=1}^m x_j\right)^2\leq m\sum_{j=1}^m x_j^2.$$

On peut reconnaître une forme de l'inégalité de Cauchy-Schwarz ; une preuve élémentaire à partir de $\sum_{i,j}(x_i-x_j)^2\geq0$ est également possible.

(b) Montrer que, pour tout $k\in\{0,\ldots,n-1\}$,

$$|\widehat f(k)|^2\leq |S|\sum_{z\in\mathbb U_n}|f(z)|^2.$$

(c) Démontrer le principe d'incertitude discret

$$|\operatorname{supp}f|\,|\operatorname{supp}\widehat f|\geq n.$$

Indication : utiliser la question 8.

(d) Supposons que $f$ soit non nulle sur exactement $p$ sommets. Quel nombre minimal de coefficients de Fourier non nuls l'inégalité impose-t-elle ? Donner l'énoncé symétrique si $\widehat f$ est non nulle sur exactement $q$ fréquences. Expliquer alors, en termes précis, l'impossibilité d'une localisation simultanée exacte sur très peu de sommets et très peu de fréquences.

10. Vérifier que l'inégalité de la question 9(c) est une égalité pour une fonction non nulle en un seul sommet et nulle ailleurs, puis pour une fonction constante non nulle.

On cherche enfin des cas d'égalité moins extrêmes. On suppose que $n=ab$ avec $a,b\geq2$ et on pose

$$H=\{1,\omega^a,\omega^{2a},\ldots,\omega^{(b-1)a}\},\qquad f=\mathbf 1_H.$$

11. Étudier cette fonction.

(a) Montrer que $H$ possède exactement $b$ éléments.

(b) Calculer $\widehat f(k)$ et montrer que

$$\widehat f(k)=\begin{cases} b,&b\mid k,\\ 0,&b\nmid k, \end{cases} \qquad 0\leq k\leq n-1.$$

(c) Déterminer $|\operatorname{supp}f|$ et $|\operatorname{supp}\widehat f|$. Que montre cet exemple sur l'optimalité de l'inégalité de la question 9(c) ?

Ouverture. Les résultats s'enchaînent maintenant ainsi : symétrie de rotation, fonctions adaptées aux translations, orthogonalité, coefficients de Fourier, reconstruction, conservation, puis incertitude. Joseph Fourier a développé au début du XIXe siècle des décompositions trigonométriques dans l'étude de la chaleur ; le cadre fini construit ici en est un modèle discret. En mécanique quantique, les descriptions en position et en impulsion sont liées par une transformée de Fourier et le principe d'incertitude de Heisenberg exprime lui aussi une incompatibilité de localisation. Il ne s'agit toutefois pas de la même inégalité : notre résultat porte sur les tailles exactes des supports, alors que l'inégalité physique usuelle porte notamment sur des dispersions.