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

I — Quand une somme s'annule

Par définition,

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

En utilisant $\left(e^{i\theta}\right)^n=e^{in\theta}$,

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

De plus, tout nombre complexe de la forme $e^{i\theta}$ a pour module $1$, donc $|\omega|=1$. Pour tout entier $m$,

$$|\omega^m|=|\omega|^{|m|}=1$$

si $m\ge0$ ; pour $m<0$, $\omega^m=1/\omega^{-m}$ et son module vaut encore $1$. Ainsi $|\omega^m|=1$ pour tout entier $m$.

On rappelle

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

(a) Si $n$ divise $m$, il existe un entier $q$ tel que $m=nq$. Alors

$$\omega^m=\omega^{nq}=(\omega^n)^q=1.$$

Tous les termes de $S_m$ valent donc $1$ :

$$S_m=\underbrace{1+\cdots+1}_{n\text{ termes}}=n.$$

(b) Supposons que $n$ ne divise pas $m$. Si $\omega^m=1$, alors

$$e^{2i\pi m/n}=1=e^{2i\pi q}$$

pour un entier $q$, ce qui imposerait $m/n\in\mathbb Z$, donc $n\mid m$, contradiction. Ainsi $\omega^m\ne1$.

Posons $q=\omega^m$. Alors $q\ne1$ et $q^n=\omega^{mn}=(\omega^n)^m=1$. En multipliant la somme géométrique par $1-q$,

$$(1-q)(1+q+\cdots+q^{n-1})=1-q^n=0.$$

Comme $1-q\ne0$, on obtient

$$S_m=0.$$

Finalement,

$$\boxed{S_m= \begin{cases} n,&n\mid m,\\ 0,&n\nmid m. \end{cases}}$$

(c) On applique le résultat précédent à l'entier $m=r-s$. Comme $r$ et $s$ appartiennent à $\{0,\ldots,n-1\}$, on a

$$-(n-1)\le r-s\le n-1.$$

Dans cet intervalle, le seul multiple de $n$ est $0$. Ainsi $n\mid(r-s)$ équivaut à $r=s$. Donc

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

IDÉELe point essentiel est l'annulation exacte lorsque les deux indices sont différents. Cette seule identité fera disparaître, à plusieurs reprises, tous les « termes croisés » qui ne nous intéressent pas.

II — Reconnaître une oscillation

On a

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

Les entiers $m$ et $k$ appartiennent à $\{0,\ldots,n-1\}$. D'après (1),

$$\boxed{D_k= \begin{cases} n,&k=m,\\ 0,&k\ne m. \end{cases}}$$

On lit donc directement l'indice $m$ dans la liste $(D_0,\ldots,D_{n-1})$ : c'est l'unique indice pour lequel la valeur vaut $n$ au lieu de $0$. Autrement dit, la liste permet de retrouver sans ambiguïté quelle oscillation $p^{(m)}$ a été utilisée.

Pour une suite quelconque,

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

(a) Si $x=p^{(m)}$, alors $x_j=\omega^{jm}$ et

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

La question 3 donne donc immédiatement

$$\boxed{X_k=\begin{cases}n,&k=m,\\0,&k\ne m.\end{cases}}$$

Ainsi, parmi $X_0,\ldots,X_{n-1}$, un seul coefficient est non nul : celui dont l'indice est précisément $m$.

(b) On appelle fréquence d'indice $k$ l'oscillation $p^{(k)}$. Si $x$ est une fréquence pure $p^{(m)}$, la liste $X_0,\ldots,X_{n-1}$ la reconnaît donc sans ambiguïté : le seul coefficient non nul est $X_m$.

À ce stade, cette interprétation n'est démontrée que pour une oscillation pure. Les questions suivantes vont justifier le rôle beaucoup plus fort des $X_k$ pour une suite quelconque : les nombres $X_k/n$ seront exactement les coefficients qui permettent de reconstruire $x$.

III — Retrouver la suite

On suppose

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

Soit $r\in\{0,\ldots,n-1\}$. Le but est d'isoler $a_r$ et de faire disparaître tous les autres coefficients. C'est précisément ce que permet l'identité (1) si nous faisons apparaître des puissances $\omega^{j(k-r)}$.

Multiplions donc l'égalité (3) par $\omega^{-jr}$ puis sommons pour $j=0,\ldots,n-1$ :

$$\sum_{j=0}^{n-1}x_j\omega^{-jr} = \sum_{j=0}^{n-1}\left(\sum_{k=0}^{n-1}a_k\omega^{jk}\right)\omega^{-jr}.$$

La somme de gauche est précisément $X_r$. Les sommes étant finies, on peut changer leur ordre à droite :

$$X_r = \sum_{k=0}^{n-1}a_k\sum_{j=0}^{n-1}\omega^{j(k-r)}.$$

D'après (1), la somme intérieure vaut $0$ si $k\ne r$ et $n$ si $k=r$. Tous les termes disparaissent donc sauf un :

$$X_r=na_r.$$

Ainsi

$$\boxed{a_r=\frac{X_r}{n}.}$$

Cette relation montre que si une décomposition de la forme demandée existe, ses coefficients sont entièrement déterminés.

Il reste à montrer que les coefficients $X_k/n$ reconstruisent effectivement la suite, sans supposer à l'avance qu'une décomposition existe.

Fixons $r\in\{0,\ldots,n-1\}$. À partir de la définition de $X_k$,

$$\frac1n\sum_{k=0}^{n-1}X_k\omega^{rk} = \frac1n\sum_{k=0}^{n-1} \left(\sum_{j=0}^{n-1}x_j\omega^{-jk}\right)\omega^{rk}.$$

On regroupe les puissances de $\omega$ puis on échange les deux sommes finies :

$$\frac1n\sum_{k=0}^{n-1}X_k\omega^{rk} = \frac1n\sum_{j=0}^{n-1}x_j \sum_{k=0}^{n-1}\omega^{k(r-j)}.$$

D'après (1), la somme intérieure vaut $n$ lorsque $j=r$ et $0$ sinon. Il ne reste donc que le terme d'indice $j=r$ :

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

Ainsi, pour tout $r$,

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

La transformée de Fourier discrète contient donc exactement l'information de la suite de départ : aucune information n'est perdue.

(a) Pour $x=(1,0,\ldots,0)$, seul $x_0$ est non nul. Pour tout $k$,

$$X_k=1\cdot\omega^{0}=1.$$

Donc

$$\boxed{X=(1,1,\ldots,1).}$$

(b) Pour $x=(1,1,\ldots,1)$,

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

Pour $k=0$, on obtient $X_0=n$. Pour $k\in\{1,\ldots,n-1\}$, l'entier $-k$ n'est pas divisible par $n$, donc la somme vaut $0$. Ainsi

$$\boxed{X=(n,0,\ldots,0).}$$

(c) Dans le premier exemple, $x$ possède un seul terme non nul, tandis que $X$ en possède $n$. Dans le second, c'est l'inverse : $x$ possède $n$ termes non nuls et $X$ un seul. Ces deux cas suggèrent qu'une forte concentration d'un côté s'accompagne d'un étalement de l'autre. Ce n'est encore qu'une observation sur deux exemples ; la fin du problème va établir une contrainte valable pour toute suite non nulle.

IV — Une quantité qui traverse la transformation

On part de

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

Le conjugué d'une somme est la somme des conjugués, donc

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

Comme $|\omega|=1$, on a $\overline\omega=\omega^{-1}$, donc

$$\overline{\omega^{-rk}}=\omega^{rk}.$$

Ainsi

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

On multiplie maintenant les deux sommes :

$$|X_k|^2=X_k\overline{X_k} = \left(\sum_{j=0}^{n-1}x_j\omega^{-jk}\right) \left(\sum_{r=0}^{n-1}\overline{x_r}\omega^{rk}\right).$$

En développant,

$$\boxed{|X_k|^2= \sum_{j=0}^{n-1}\sum_{r=0}^{n-1} x_j\overline{x_r}\,\omega^{k(r-j)}.} \tag{12}$$

Sommons (12) sur $k$ :

$$\sum_{k=0}^{n-1}|X_k|^2 = \sum_{k=0}^{n-1} \sum_{j=0}^{n-1}\sum_{r=0}^{n-1} x_j\overline{x_r}\,\omega^{k(r-j)}.$$

Toutes les sommes sont finies, donc nous pouvons les réordonner :

$$\sum_{k=0}^{n-1}|X_k|^2 = \sum_{j=0}^{n-1}\sum_{r=0}^{n-1} x_j\overline{x_r} \left(\sum_{k=0}^{n-1}\omega^{k(r-j)}\right).$$

L'identité (1) intervient exactement ici. Si $r\ne j$, la parenthèse vaut $0$ ; si $r=j$, elle vaut $n$. Il ne reste donc que les termes diagonaux :

$$\sum_{k=0}^{n-1}|X_k|^2 = \sum_{j=0}^{n-1}x_j\overline{x_j}\,n.$$

Or $x_j\overline{x_j}=|x_j|^2$, d'où

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

IDÉELe même mécanisme est à l'oeuvre que dans la reconstruction : une somme sur les racines de l'unité élimine tous les couples d'indices différents et ne conserve que les indices égaux. L'identité (7) fixe ainsi une quantité globale. Pour obtenir ensuite une information sur le nombre de coefficients non nuls, il faudra la combiner avec une estimation de chaque coefficient $X_k$.

V — Une inégalité pour les sommes complexes

Pour deux nombres complexes $u$ et $v$,

$$|u-v|^2=(u-v)\overline{(u-v)}=(u-v)(\overline u-\overline v).$$

En développant,

$$\boxed{|u-v|^2=|u|^2+|v|^2-u\overline v-\overline u\,v.} \tag{13}$$

Cette quantité est réelle et positive ou nulle, puisqu'il s'agit du carré d'un module.

Appliquons (13) à chaque couple $(u_r,u_t)$ avec $1\le r<t\le s$ :

$$\sum_{r<t}|u_r-u_t|^2 = \sum_{r<t}\bigl(|u_r|^2+|u_t|^2\bigr) - \sum_{r<t}\bigl(u_r\overline{u_t}+\overline{u_r}u_t\bigr). \tag{14}$$

Dans la première somme, chaque $|u_q|^2$ apparaît exactement $s-1$ fois : il est associé à chacun des $s-1$ autres indices. Ainsi

$$\sum_{r<t}\bigl(|u_r|^2+|u_t|^2\bigr) =(s-1)\sum_{q=1}^s|u_q|^2. \tag{15}$$

D'autre part,

$$\left|\sum_{q=1}^s u_q\right|^2 = \left(\sum_{q=1}^s u_q\right) \left(\sum_{q=1}^s\overline{u_q}\right).$$

En développant et en séparant les termes de même indice des termes d'indices différents,

$$\left|\sum_{q=1}^s u_q\right|^2 = \sum_{q=1}^s|u_q|^2 + \sum_{r<t}\bigl(u_r\overline{u_t}+\overline{u_r}u_t\bigr). \tag{16}$$

En utilisant (15) et (16) dans (14),

$$\sum_{r<t}|u_r-u_t|^2 =(s-1)\sum_q|u_q|^2 - \left(\left|\sum_q u_q\right|^2-\sum_q|u_q|^2\right).$$

Donc

$$\boxed{ s\sum_{q=1}^{s}|u_q|^2- \left|\sum_{q=1}^{s}u_q\right|^2 = \sum_{r<t}|u_r-u_t|^2.}$$

Le membre de droite est une somme de carrés de modules, donc il est positif ou nul. Par conséquent,

$$\left|\sum_{q=1}^{s}u_q\right|^2 \le s\sum_{q=1}^{s}|u_q|^2.$$

Ainsi

$$\boxed{\left|\sum_{q=1}^{s}u_q\right|^2 \le s\sum_{q=1}^{s}|u_q|^2.}$$

IDÉECette inégalité est exactement la quantité dont nous avons besoin : elle contrôle le module d'une somme de $s$ nombres complexes uniquement à partir de la somme des carrés de leurs modules.

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

Nous combinons maintenant les deux ingrédients préparés séparément : Parseval fixe la somme totale des $|X_k|^2$, tandis que (9) va fournir une borne pour chacun d'eux lorsque $x$ n'est non nulle que sur $s$ indices.

Soit $k\in\{0,\ldots,n-1\}$. Par définition de $S=\operatorname{supp}(x)$, les termes $x_j$ sont nuls lorsque $j\notin S$. La formule de $X_k$ peut donc s'écrire

$$X_k=\sum_{j\in S}x_j\omega^{-jk}.$$

Il y a exactement $s=\#S$ termes dans cette somme. Appliquons l'inégalité (9) aux nombres

$$u_j=x_j\omega^{-jk},\qquad j\in S.$$

On obtient

$$|X_k|^2 \le s\sum_{j\in S}|x_j\omega^{-jk}|^2.$$

Or $|\omega^{-jk}|=1$, donc

$$|x_j\omega^{-jk}|^2=|x_j|^2.$$

Ainsi

$$|X_k|^2 \le s\sum_{j\in S}|x_j|^2.$$

Les termes avec $j\notin S$ étant nuls, on peut réintroduire tous les indices :

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

D'après l'identité (7),

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

Par définition de $T=\operatorname{supp}(X)$, on a $X_k=0$ pour $k\notin T$. Donc

$$\sum_{k=0}^{n-1}|X_k|^2 = \sum_{k\in T}|X_k|^2.$$

Pour chacun des $t=\#T$ indices de $T$, la question 12 donne

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

En sommant ces $t$ inégalités,

$$\sum_{k\in T}|X_k|^2 \le st\sum_{j=0}^{n-1}|x_j|^2.$$

En combinant les deux relations,

$$n\sum_{j=0}^{n-1}|x_j|^2 \le st\sum_{j=0}^{n-1}|x_j|^2.$$

La suite $x$ n'est pas nulle. Il existe donc au moins un indice $j$ tel que $x_j\ne0$, et par conséquent

$$\sum_{j=0}^{n-1}|x_j|^2>0.$$

Nous pouvons diviser par cette quantité strictement positive :

$$\boxed{st\ge n.}$$

Autrement dit,

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

Comme $s>0$, l'inégalité $st\ge n$ peut aussi s'écrire

$$t\ge \frac{n}{s}.$$

Cette forme rend le sens du résultat immédiat : si $x$ n'est non nulle que sur peu d'indices, c'est-à-dire si $s$ est petit, alors $t$ ne peut pas l'être lui aussi. La transformée $X$ doit être non nulle sur suffisamment d'indices de fréquence. Comme l'inégalité $st\ge n$ est symétrique en $s$ et $t$, on obtient de même $s\ge n/t$ : une transformée très concentrée force la suite de départ à être plus étalée.

Principe d'incertitude discret. Pour toute suite complexe non nulle de longueur $n$, le produit du nombre de positions non nulles de la suite par le nombre de fréquences non nulles de sa transformée est au moins égal à $n$.

VII — La borne peut-elle être atteinte ?

On prend $n=6$ et

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

Ainsi seuls les indices $j=0,2,4$ contribuent à la somme définissant $X_k$.

(a) Pour tout $k\in\{0,\ldots,5\}$,

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

Donc

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

(b) Posons

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

Alors $\zeta^3=1$ et

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

Si $k$ est divisible par $3$, alors $\zeta^{-k}=1$ et

$$X_k=3.$$

Parmi $0,1,2,3,4,5$, cela se produit pour $k=0$ et $k=3$.

Si $k$ n'est pas divisible par $3$, le nombre $q=\zeta^{-k}$ est une racine cubique de l'unité différente de $1$. On a donc

$$1+q+q^2=0.$$

Ainsi $X_k=0$ pour $k=1,2,4,5$. Finalement,

$$\boxed{X=(3,0,0,3,0,0).}$$

(c) La suite $x$ est non nulle exactement aux indices $0,2,4$, donc

$$\#\operatorname{supp}(x)=3.$$

La transformée $X$ est non nulle exactement aux indices $0,3$, donc

$$\#\operatorname{supp}(X)=2.$$

Par conséquent,

$$\#\operatorname{supp}(x)\;\#\operatorname{supp}(X)=3\times2=6=n.$$

La borne du principe d'incertitude est donc effectivement atteinte dans cet exemple non trivial.

Ouverture — de Fourier au principe d'incertitude en physique

Le résultat démontré ici est une version finie et discrète d'un phénomène beaucoup plus général. En analyse de Fourier, il existe de nombreux théorèmes disant qu'un objet et sa transformée de Fourier ne peuvent pas être simultanément trop concentrés. La notion de « concentration » dépend du cadre : elle peut être mesurée par la taille du support, comme ici, mais aussi par une largeur, une variance ou encore la proportion d'énergie contenue dans une région.

Dans notre situation,

$$s=\#\operatorname{supp}(x),\qquad t=\#\operatorname{supp}(X),$$

et l'inégalité

$$st\ge n$$

interdit que les deux supports soient simultanément petits. Si $s$ diminue, la borne $t\ge n/s$ force la transformée à occuper davantage d'indices de fréquence ; inversement, si $t$ diminue, alors $s\ge n/t$.

En mécanique quantique, une idée apparentée apparaît pour la position et l'impulsion. Une fonction d'onde peut être décrite en fonction de la position ; sa description en fonction de l'impulsion s'obtient, à des constantes de normalisation près, par une transformation de Fourier. Les dispersions correspondantes, notées usuellement $\Delta x$ et $\Delta p$, vérifient la relation de Heisenberg

$$\Delta x\,\Delta p\ge \frac{\hbar}{2}.$$

Autrement dit, un état très localisé en position doit nécessairement être plus étalé en impulsion, et réciproquement.

Il faut cependant distinguer nettement les deux énoncés. L'inégalité $st\ge n$ porte sur le nombre exact de coefficients non nuls d'une suite finie et de sa transformée discrète ; la relation de Heisenberg porte sur des dispersions de distributions continues associées à un état quantique. Notre résultat n'est donc pas une démonstration de la relation physique. Il en constitue un modèle mathématique fini particulièrement lisible : dans les deux cas, la transformation de Fourier rend impossible une localisation arbitrairement forte dans les deux descriptions à la fois.

Pour fixer précisément l'analogie :

• Objet étudié — ici : une suite finie $x$ ; en mécanique quantique : une fonction d'onde décrite en position.
• Description de Fourier — ici : les coefficients $X_k$ ; en mécanique quantique : la description en impulsion.
• Mesure de concentration — ici : le nombre de coefficients non nuls ; en mécanique quantique : une dispersion, mesurée par un écart-type.
• Contrainte — ici : $st\ge n$ ; en mécanique quantique : $\Delta x\,\Delta p\ge\hbar/2$.

Cette comparaison doit être lue comme une analogie de structure, et non comme une identification des grandeurs : les indices $j$ et $k$ de notre suite ne sont pas, à eux seuls, une position et une impulsion physiques.

Au terme de cette étude, une identité d'annulation sur les racines de l'unité permet d'abord de distinguer les oscillations élémentaires, puis de reconstruire exactement la suite à partir de ses coefficients de Fourier. L'identité de Parseval fixe ensuite une quantité globale, tandis que l'inégalité (9) contrôle chaque coefficient séparément. Leur combinaison impose une limite quantitative à la concentration simultanée de la suite et de sa transformée. Le cas $n=6$ montre enfin que cette limite peut être atteinte exactement.

Sources

[SOURCE] David L. Donoho et Philip B. Stark — Uncertainty Principles and Signal Recovery, SIAM Journal on Applied Mathematics, 49(3), 1989, p. 906–931. Lien direct [SOURCE] OpenStax — University Physics, Volume 3, § 7.2, The Heisenberg Uncertainty Principle. Lien direct