Des racines de l’unité à la transformée de Fourier discrète

Une suite de longueur $n$ peut être lue comme un motif qui se répète. Certaines suites très simples oscillent régulièrement autour du cercle unité. Peut-on utiliser ces oscillations comme des briques élémentaires pour analyser une suite quelconque, puis la reconstruire exactement ? Une même identité sur les racines de l'unité va répondre à cette question et conduire, à la fin, à une contrainte surprenante sur la concentration d'une suite et de ses fréquences.

I — Quand une somme s'annule

On fixe un entier $n\ge 2$ et on pose

$$\omega=e^{2i\pi/n}.$$

1. Vérifier que $\omega^n=1$ et que $|\omega|=1$. En déduire que $|\omega^m|=1$ pour tout entier $m$.

2. Pour tout entier $m$, on note

$$S_m=\sum_{j=0}^{n-1}\omega^{jm}=1+\omega^m+\omega^{2m}+\cdots+\omega^{(n-1)m}.$$

(a) Montrer que si $n$ divise $m$, alors $S_m=n$. (b) On suppose que $n$ ne divise pas $m$. Montrer que $\omega^m\ne1$, puis calculer $(1-\omega^m)S_m$. En déduire la valeur de $S_m$. (c) Soient $r,s\in\{0,\ldots,n-1\}$. Montrer que

$$\sum_{j=0}^{n-1}\omega^{j(r-s)}= \begin{cases} n,&\text{si }r=s,\\ 0,&\text{si }r\ne s. \end{cases} \tag{1}$$

Éclairage. En géométrie, le produit scalaire permet de reconnaître deux vecteurs orthogonaux par une égalité du type $\vec u\cdot\vec v=0$. Ici, si l'on compare les deux listes $(1,\omega^r,\ldots,\omega^{(n-1)r})$ et $(1,\omega^s,\ldots,\omega^{(n-1)s})$ à l'aide de la somme $\sum_{j=0}^{n-1}\omega^{jr}\overline{\omega^{js}}$, on retrouve exactement (1). Après le lycée, on définit de la même façon un produit scalaire adapté aux listes de nombres complexes ; lorsque $r\ne s$, ces deux oscillations sont alors dites orthogonales.

II — Reconnaître une oscillation

Pour $m\in\{0,\ldots,n-1\}$, considérons la suite

$$p^{(m)}=(1,\omega^m,\omega^{2m},\ldots,\omega^{(n-1)m}).$$

3. Pour $k\in\{0,\ldots,n-1\}$, calculer

$$D_k=\sum_{j=0}^{n-1}\omega^{jm}\omega^{-jk}.$$

Montrer en particulier que $D_m=n$ tandis que $D_k=0$ pour $k\ne m$. Expliquer comment la liste $D_0,\ldots,D_{n-1}$ permet alors de retrouver l'indice $m$ de l'oscillation $p^{(m)}$.

4. Soit désormais une suite complexe quelconque $x=(x_0,\ldots,x_{n-1})$. Pour chaque $k\in\{0,\ldots,n-1\}$, on définit

$$X_k=\sum_{j=0}^{n-1}x_j\omega^{-jk}. \tag{2}$$

(a) Supposons que $x$ soit précisément l'une des oscillations précédentes : $x=p^{(m)}$. En comparant la définition de $X_k$ avec celle de $D_k$, déterminer les valeurs de $X_0,\ldots,X_{n-1}$. (b) Nous appellerons fréquence d'indice $k$ l'oscillation $p^{(k)}$. D'après (a), comment la liste $X_0,\ldots,X_{n-1}$ permet-elle de reconnaître une suite qui est constituée d'une seule fréquence $p^{(m)}$ ?

Éclairage. La suite $X=(X_0,\ldots,X_{n-1})$ est appelée la transformée de Fourier discrète de $x$. Pour l'instant, nous savons qu'elle reconnaît parfaitement une oscillation pure. La suite du problème va montrer quelque chose de beaucoup plus fort : pour une suite quelconque, les nombres $X_k/n$ sont exactement les coefficients qui permettent de reconstruire $x$.

III — Retrouver la suite

5. Supposons qu'il existe des nombres complexes $a_0,\ldots,a_{n-1}$ tels que, pour tout $j$,

$$x_j=\sum_{k=0}^{n-1}a_k\omega^{jk}. \tag{3}$$

Pour isoler un coefficient $a_r$, l'idée est de faire apparaître les sommes d'annulation de (1). Soit donc $r\in\{0,\ldots,n-1\}$. Multiplier (3) par $\omega^{-jr}$, puis sommer les égalités obtenues pour $j=0,\ldots,n-1$. Réorganiser la double somme et utiliser (1) pour montrer que nécessairement

$$a_r=\frac{X_r}{n}. \tag{4}$$

6. Sans supposer cette fois l'existence d'une décomposition de la forme (3), montrer directement que, pour tout $r\in\{0,\ldots,n-1\}$,

$$\boxed{x_r=\frac1n\sum_{k=0}^{n-1}X_k\omega^{rk}.} \tag{5}$$

Ainsi, la transformée permet non seulement d'analyser la suite, mais aussi de la reconstruire exactement.

7. Deux cas extrêmes donnent une première idée de ce que fait la transformation. (a) Déterminer $X$ lorsque $x=(1,0,\ldots,0)$. (b) Déterminer $X$ lorsque $x=(1,1,\ldots,1)$. (c) Comparer, dans ces deux exemples, le nombre de termes non nuls de $x$ et celui de $X$.

Point d'étape. Les questions 5 et 6 ont montré que $x$ et $X$ contiennent exactement la même information : on passe de l'une à l'autre sans perte. Les deux exemples de la question 7 suggèrent toutefois un autre phénomène : lorsqu'une suite est très concentrée sur quelques indices, sa transformée semble davantage étalée. Nous allons chercher à rendre cette observation précise.

IV — Une quantité qui traverse la transformation

8. Montrer que, pour tout $k$,

$$\overline{X_k}=\sum_{r=0}^{n-1}\overline{x_r}\,\omega^{rk}. \tag{6}$$

En déduire une expression de $|X_k|^2=X_k\overline{X_k}$ sous la forme d'une somme double portant sur deux indices $j$ et $r$.

9. Sommer l'expression précédente sur $k$, puis utiliser (1) pour montrer l'identité

$$\boxed{\sum_{k=0}^{n-1}|X_k|^2=n\sum_{j=0}^{n-1}|x_j|^2.} \tag{7}$$

Point d'étape. L'identité (7) relie une quantité globale calculée à partir de $x$ à la même quantité calculée à partir de $X$. Pour transformer cette information globale en une contrainte sur le nombre de coefficients non nuls, il nous faudra aussi savoir contrôler le module d'une somme de nombres complexes. C'est l'objet de la partie suivante.

V — Une inégalité pour les sommes complexes

Soient $s\ge1$ et $u_1,\ldots,u_s$ des nombres complexes.

10. Pour deux nombres complexes $u$ et $v$, développer $|u-v|^2$ à l'aide de $u$, $v$ et de leurs conjugués.

11. En sommant convenablement le résultat précédent sur les couples $1\le r<t\le s$, montrer que

$$s\sum_{r=1}^{s}|u_r|^2- \left|\sum_{r=1}^{s}u_r\right|^2 = \sum_{1\le r<t\le s}|u_r-u_t|^2. \tag{8}$$

En déduire

$$\boxed{\left|\sum_{r=1}^{s}u_r\right|^2\le s\sum_{r=1}^{s}|u_r|^2.} \tag{9}$$

Éclairage. L'inégalité (9) est un cas particulier de l'inégalité de Cauchy-Schwarz. Vous connaissez déjà le produit scalaire en géométrie, pour lequel une inégalité analogue relie $|\vec u\cdot\vec v|$ aux longueurs de $\vec u$ et $\vec v$. Après le lycée, Cauchy-Schwarz généralise ce type de contrôle à de nombreux produits scalaires, notamment sur des listes de nombres réels ou complexes. Ici, nous n'avons utilisé que le cas exact dont nous avions besoin.

VI — Jusqu'où peut-on se concentrer ?

Nous revenons maintenant à la question suggérée par les deux exemples de la question 7 : peut-on avoir à la fois peu de termes non nuls dans $x$ et peu de termes non nuls dans $X$ ?

On suppose désormais que $x$ n'est pas la suite nulle. On appelle support de $x$ l'ensemble

$$\operatorname{supp}(x)=\{j\in\{0,\ldots,n-1\}:x_j\ne0\}.$$

On note $S=\operatorname{supp}(x)$ et $s=\#S$. De même, on note

$$T=\operatorname{supp}(X),\qquad t=\#T.$$

12. Soit $k\in\{0,\ldots,n-1\}$. Comme $x_j=0$ pour $j\notin S$, réécrire $X_k$ sous la forme d'une somme portant seulement sur les $s$ indices de $S$. Appliquer ensuite (9) aux $s$ nombres $x_j\omega^{-jk}$, $j\in S$, et utiliser $|\omega^{-jk}|=1$ pour montrer que

$$|X_k|^2\le s\sum_{j=0}^{n-1}|x_j|^2. \tag{10}$$

Point d'étape. La relation (10) borne séparément chacun des nombres $|X_k|^2$. Mais (7) impose en même temps la valeur de leur somme totale. Si chaque terme est borné et que la somme totale est fixée, il faut suffisamment de termes non nuls pour porter cette somme : la question suivante quantifie exactement cette idée.

13. À l'aide de (7), de (10) et du fait que $X_k=0$ lorsque $k\notin T$, montrer que

$$\boxed{\#\operatorname{supp}(x)\;\#\operatorname{supp}(X)\ge n.} \tag{11}$$

Éclairage. La relation (11) est appelée un principe d'incertitude discret. En notant $s=\#\operatorname{supp}(x)$ et $t=\#\operatorname{supp}(X)$, elle s'écrit $t\ge n/s$ : plus la suite de départ est concentrée sur peu d'indices, plus sa transformée est forcée d'être non nulle sur de nombreux indices de fréquence. Comme (11) est symétrique en $s$ et $t$, on a aussi $s\ge n/t$.

VII — La borne peut-elle être atteinte ?

14. On prend $n=6$ et

$$x=(1,0,1,0,1,0).$$

On pose toujours $\omega=e^{2i\pi/6}$. (a) Montrer que, pour tout $k\in\{0,\ldots,5\}$,

$$X_k=1+\omega^{-2k}+\omega^{-4k}.$$

(b) En posant $\zeta=\omega^2=e^{2i\pi/3}$, déterminer les six valeurs $X_k$. (c) Calculer $\#\operatorname{supp}(x)$ et $\#\operatorname{supp}(X)$. Que constate-t-on dans (11) ?

Ouverture. Le résultat obtenu appartient à une famille beaucoup plus large de principes d'incertitude liés à l'analyse de Fourier : un objet et sa transformée ne peuvent pas être simultanément très concentrés. Ici, la concentration est mesurée par le nombre de coefficients non nuls ; dans d'autres cadres, on utilise plutôt une largeur, une dispersion ou la part d'énergie contenue dans une zone. En mécanique quantique, la description d'un état en fonction de la position et sa description en fonction de l'impulsion sont reliées par une transformation de Fourier. La relation d'Heisenberg $\Delta x\,\Delta p\ge \hbar/2$ affirme qu'on ne peut pas rendre arbitrairement petites à la fois les dispersions de position et d'impulsion. Notre inégalité $\#\operatorname{supp}(x)\,\#\operatorname{supp}(X)\ge n$ n'est pas cette relation physique, mais un analogue discret fini fondé sur la même opposition mathématique : une forte localisation d'un côté impose un étalement de l'autre.

Nous sommes partis d'une identité d'annulation sur les racines de l'unité. Elle permet de distinguer les oscillations élémentaires, puis de reconstruire exactement une suite à partir de ses coefficients de Fourier. L'identité de Parseval montre ensuite que cette transformation conserve une quantité globale, tandis que l'inégalité (9) limite la taille de chaque coefficient. Leur combinaison conduit au principe d'incertitude discret : une suite non nulle et sa transformée ne peuvent pas être toutes deux concentrées sur trop peu d'indices. L'exemple $n=6$ montre enfin que la borne est exacte.