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

La construction part d'une question de symétrie. La structure de groupe organise les rotations ; les fonctions $z\mapsto z^k$ sont imposées par la recherche du comportement le plus simple possible sous translation ; la somme géométrique permet ensuite de les séparer. La formule d'inversion reconstruit toute fonction à partir des coefficients ainsi obtenus, puis l'identité de Parseval conduit à un principe d'incertitude exact sur les supports.

I — Un polygone qui est aussi un groupe

(a) Si $\omega^j=\omega^\ell$ avec $0\leq j,\ell\leq n-1$, alors $\omega^{j-\ell}=1$, donc

$$e^{2i\pi(j-\ell)/n}=1.$$

Ainsi $(j-\ell)/n\in\mathbb Z$, c'est-à-dire $n\mid(j-\ell)$. Comme $|j-\ell|<n$, on obtient $j=\ell$ : les $n$ nombres affichés sont distincts.

Réciproquement, si $z^n=1$, alors $|z|^n=1$, donc $|z|=1$ et $z=e^{i\theta}$ pour un réel $\theta$. La relation $e^{in\theta}=1$ donne $n\theta\in2\pi\mathbb Z$, d'où $z=e^{2i\pi j/n}=\omega^j$ pour un entier $j$, que l'on peut réduire modulo $n$ dans $\{0,\ldots,n-1\}$.

(b) Pour $j,\ell\in\{0,\ldots,n-1\}$,

$$\omega^j\omega^\ell=\omega^{j+\ell}\in\mathbb U_n$$

après réduction de l'exposant modulo $n$, et

$$(\omega^j)^{-1}=\omega^{-j}\in\mathbb U_n.$$

L'associativité vient de la multiplication complexe, $1\in\mathbb U_n$ est neutre, et chaque élément possède un inverse dans $\mathbb U_n$. Ainsi $(\mathbb U_n,\times)$ est un groupe fini.

Enfin, par définition,

$$\mathbb U_n=\{\omega^j\,;\,0\leq j\leq n-1\}.$$

Tous ses éléments sont donc des puissances de $\omega$ : le groupe est cyclique et $\omega$ est un générateur.

Éclairage. L'application $z\mapsto\omega z$ est la rotation d'angle $2\pi/n$. La loi de groupe ne constitue donc pas un habillage : elle encode la composition des rotations du polygone.

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

(a) Pour $z\in\mathbb U_n$,

$$(\tau_a\tau_bf)(z)=(\tau_bf)(a^{-1}z)=f(b^{-1}a^{-1}z)=f((ab)^{-1}z)=(\tau_{ab}f)(z).$$

Donc $\tau_a\tau_b=\tau_{ab}$.

De plus, $\tau_1f=f$, donc $\tau_1$ est l'identité. Enfin,

$$\tau_a\tau_{a^{-1}}=\tau_1,$$

si bien que $\tau_a$ est bijective et que son inverse est $\tau_{a^{-1}}$.

(b) Par récurrence à partir de $\tau_a\tau_b=\tau_{ab}$,

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

Par ailleurs,

$$(\tau_\omega f)(\omega z)=f(\omega^{-1}\omega z)=f(z).$$

La valeur portée par le sommet $z$ avant la translation se retrouve donc au sommet $\omega z$ après translation : le motif a été déplacé d'un cran. Comme tout $a\in\mathbb U_n$ s'écrit $a=\omega^j$, toute translation $\tau_a$ est obtenue en répétant cette translation élémentaire.

III — Les fonctions les plus simples sous rotation

(a) Si $\lambda=0$, l'égalité $\tau_\omega f=0$ et la bijectivité de $\tau_\omega$ imposeraient $f=0$, contradiction. Donc $\lambda\neq0$.

Si $f(1)=0$, alors la relation

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

propagerait la valeur nulle à tous les sommets, donc encore $f=0$. Ainsi $f(1)\neq0$.

La même relation donne

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

et une récurrence fournit

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

(b) La question 2 donne

$$\tau_\omega^n=\tau_{\omega^n}=\tau_1=\operatorname{Id}.$$

En appliquant cette identité à $f$ et en utilisant $\tau_\omega f=\lambda f$,

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

Comme $f\not\equiv0$, on obtient $\lambda^n=1$. Il existe donc un unique $k\in\{0,\ldots,n-1\}$ tel que

$$\lambda=\omega^{-k}.$$

Alors, pour $z=\omega^j$,

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

Avec $c=f(1)\neq0$,

$$\boxed{f(z)=cz^k.}$$

(c) Pour $a,z\in\mathbb U_n$,

$$(\tau_am_k)(z)=m_k(a^{-1}z)=(a^{-1}z)^k=a^{-k}z^k=a^{-k}m_k(z).$$

Ainsi,

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

Par conséquent, $\tau_a$ transforme tout multiple $cm_k$ en $ca^{-k}m_k$, qui appartient encore à la droite $\mathbb C m_k$. Sur cette droite, toute la translation est donc résumée par le seul scalaire $a^{-k}$. C'est le contenu mathématique précis de l'expression « mode adapté aux translations ».

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

4. Si $n\mid r$, alors $\omega^r=1$ et chaque terme vaut $1$, donc

$$S_r=n.$$

Si $n\nmid r$, alors $\omega^r\neq1$. La somme géométrique donne

$$S_r=\frac{1-(\omega^r)^n}{1-\omega^r} =\frac{1-(\omega^n)^r}{1-\omega^r}=0.$$

Ainsi

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

(a) Comme $|z|=1$, on a $\overline z=z^{-1}$. Ainsi

$$m_k(z)\overline{m_\ell(z)}=z^kz^{-\ell}=z^{k-\ell}.$$

En écrivant $z=\omega^j$,

$$\sum_{z\in\mathbb U_n}m_k(z)\overline{m_\ell(z)} =\sum_{j=0}^{n-1}\omega^{j(k-\ell)}.$$

La question 4 donne $n$ si $n\mid(k-\ell)$ et $0$ sinon. Comme $k,\ell\in\{0,\ldots,n-1\}$, la première condition équivaut à $k=\ell$.

(b) Supposons

$$\sum_{k=0}^{n-1}c_km_k(z)=0$$

pour tout $z\in\mathbb U_n$. Fixons $\ell$, multiplions par $\overline{m_\ell(z)}$ puis sommons sur $z$ :

$$0= \sum_{k=0}^{n-1}c_k \sum_{z\in\mathbb U_n}m_k(z)\overline{m_\ell(z)} =nc_\ell.$$

Donc $c_\ell=0$. Ceci vaut pour tout $\ell$, donc tous les coefficients sont nuls.

Éclairage. Si l'on pose $\langle f,g\rangle=\sum_{z\in\mathbb U_n}f(z)\overline{g(z)}$, la question 5(a) s'écrit $\langle m_k,m_\ell\rangle=n\delta_{k\ell}$. C'est précisément la structure que le produit scalaire permet de systématiser : les modes sont orthogonaux.

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

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

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

La question 4 donne donc

$$\boxed{\widehat{m_r}(k)=\begin{cases} n,&r=k,\\ 0,&r\neq k. \end{cases}}$$

(b) Pour $z\in\mathbb U_n$,

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

Les sommes étant finies, on peut les permuter :

$$\frac1n\sum_{y\in\mathbb U_n}f(y) \sum_{k=0}^{n-1}\left(\frac zy\right)^k.$$

Or $z/y\in\mathbb U_n$. D'après la question 4, la somme intérieure vaut $n$ si $z/y=1$, c'est-à-dire si $y=z$, et $0$ sinon. Il ne reste donc que $f(z)$ :

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

(c) La formule d'inversion s'écrit

$$f=\sum_{k=0}^{n-1}\frac{\widehat f(k)}n\,m_k.$$

Elle fournit l'existence d'une décomposition. L'unicité vient de la question 5(b). Le coefficient de $m_k$ est donc exactement $\widehat f(k)/n$.

Éclairage. La transformée n'a pas été introduite comme une formule arbitraire : elle mesure les composantes de $f$ selon les modes distingués par les translations. C'est à ce stade que l'indice $k$ prend le rôle d'un indice de fréquence.

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

7. Par définition,

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

La multiplication par $a^{-1}$ permute $\mathbb U_n$. Posons $y=a^{-1}z$, donc $z=ay$. Alors

$$\widehat{\tau_af}(k) =\sum_{y\in\mathbb U_n}f(y)(ay)^{-k} =a^{-k}\sum_{y\in\mathbb U_n}f(y)y^{-k}.$$

Ainsi

$$\boxed{\widehat{\tau_af}(k)=a^{-k}\widehat f(k).}$$

Dans les valeurs de $f$, $\tau_a$ permute les sommets ; dans les coefficients de Fourier, chaque fréquence est seulement multipliée par un facteur propre. Les fréquences ne se mélangent pas.

VII — Une identité de conservation

8. On développe

$$|\widehat f(k)|^2 =\left(\sum_{z\in\mathbb U_n}f(z)z^{-k}\right) \left(\sum_{y\in\mathbb U_n}\overline{f(y)}\,y^k\right),$$

car $\overline{y^{-k}}=y^k$ pour $|y|=1$. En sommant sur $k$ puis en permutant les sommes finies,

$$\sum_{k=0}^{n-1}|\widehat f(k)|^2 =\sum_{z,y\in\mathbb U_n}f(z)\overline{f(y)} \sum_{k=0}^{n-1}\left(\frac yz\right)^k.$$

La question 4 annule la somme intérieure lorsque $y\neq z$ et lui donne la valeur $n$ lorsque $y=z$. Donc

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

C'est l'identité de Parseval pour la normalisation choisie.

Éclairage. Avec une transformée normalisée par $1/\sqrt n$, le facteur $n$ disparaîtrait : la transformation préserverait exactement la somme des carrés des modules. Le vocabulaire de norme et de produit scalaire donnera plus tard une formulation compacte de cette conservation.

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

(a) On part de

$$\frac12\sum_{i=1}^m\sum_{j=1}^m(x_i-x_j)^2\geq0.$$

En développant,

$$\frac12\sum_{i,j}(x_i-x_j)^2 =m\sum_{j=1}^m x_j^2- \left(\sum_{j=1}^m x_j\right)^2.$$

D'où

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

Il s'agit aussi de Cauchy-Schwarz appliquée aux vecteurs $(x_1,\ldots,x_m)$ et $(1,\ldots,1)$.

(b) Comme $f$ est nulle hors de $S$,

$$|\widehat f(k)| =\left|\sum_{z\in S}f(z)z^{-k}\right| \leq\sum_{z\in S}|f(z)|.$$

La question 9(a), appliquée aux $|S|$ nombres $|f(z)|$, donne

$$\left(\sum_{z\in S}|f(z)|\right)^2 \leq |S|\sum_{z\in S}|f(z)|^2.$$

Ainsi

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

(c) Puisque $\widehat f(k)=0$ pour $k\notin T$,

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

La question 9(b), appliquée à chacun des $|T|$ indices, donne

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

Or, par la question 8,

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

Comme $f\not\equiv0$, la somme $\sum|f(z)|^2$ est strictement positive. On peut donc simplifier :

$$\boxed{|S|\,|T|\geq n.}$$

Cette inégalité appartient à une famille de principes d'incertitude de Fourier formulés en termes de concentration ; des versions continues et discrètes ont notamment été étudiées en traitement du signal.

(d) Si $|S|=p$, alors $p|T|\geq n$, donc

$$|T|\geq\left\lceil\frac np\right\rceil.$$

Symétriquement, si $|T|=q$, alors

$$|S|\geq\left\lceil\frac nq\right\rceil.$$

Ainsi une forte localisation exacte sur les sommets impose un étalement du support fréquentiel, et réciproquement. En particulier, $p=1$ force $|T|=n$, tandis que $q=1$ force $|S|=n$.

10. Soit $z_0\in\mathbb U_n$ et considérons $f=\mathbf1_{\{z_0\}}$. Alors $|\operatorname{supp}f|=1$ et

$$\widehat f(k)=z_0^{-k}\neq0$$

pour tout $k$, donc $|\operatorname{supp}\widehat f|=n$. Le produit vaut $n$.

Pour une fonction constante non nulle $f(z)=c$, le support de $f$ a taille $n$ et

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

La question 4 donne $\widehat f(0)=cn\neq0$ et $\widehat f(k)=0$ pour $k\neq0$. Le support fréquentiel a taille $1$, et le produit vaut encore $n$.

(a) Si $\omega^{aj}=\omega^{a\ell}$ avec $0\leq j,\ell\leq b-1$, alors $n=ab$ divise $a(j-\ell)$, donc $b\mid(j-\ell)$. Or $|j-\ell|<b$, donc $j=\ell$. Les $b$ éléments affichés sont distincts :

$$|H|=b.$$

(b) Comme $f=\mathbf1_H$,

$$\widehat f(k)=\sum_{j=0}^{b-1}(\omega^{aj})^{-k} =\sum_{j=0}^{b-1}(\omega^{-ak})^j.$$

Or

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

Si $b\mid k$, alors $\omega^{-ak}=1$ et la somme vaut $b$. Sinon, $\omega^{-ak}$ est une racine $b$-ième de l'unité différente de $1$, et la somme géométrique vaut $0$. Donc

$$\boxed{\widehat f(k)=\begin{cases} b,&b\mid k,\\ 0,&b\nmid k. \end{cases}}$$

(c) $|\operatorname{supp}f|=|H|=b$. Dans $\{0,\ldots,ab-1\}$, les multiples de $b$ sont

$$0,b,2b,\ldots,(a-1)b,$$

soit exactement $a$ indices. Ainsi

$$|\operatorname{supp}\widehat f|=a, \qquad |\operatorname{supp}f|\,|\operatorname{supp}\widehat f|=ab=n.$$

L'inégalité est donc optimale, y compris pour des configurations intermédiaires entre « un seul sommet / toutes les fréquences » et « tous les sommets / une seule fréquence ».

Synthèse. La transformée de Fourier discrète n'a pas été postulée : les translations du groupe cyclique ont fait apparaître les fonctions $z^k$ ; leur orthogonalité a fourni les coefficients ; l'inversion a montré qu'ils décrivent toute fonction ; Parseval a relié les deux descriptions ; le principe d'incertitude a enfin mesuré l'impossibilité de les rendre simultanément très localisées.

Ouverture. Dans la mécanique quantique continue, les représentations en position et en impulsion d'un état sont reliées par une transformée de Fourier. Le principe d'incertitude formulé par Heisenberg en 1927 exprime lui aussi une incompatibilité de localisation, mais il ne faut pas confondre les résultats : l'inégalité démontrée ici porte sur le nombre de composantes exactement non nulles dans un modèle fini ; les relations position-impulsion usuelles portent notamment sur des dispersions. Des relations d'incertitude spécifiquement adaptées à la transformée de Fourier discrète existent également en dimension finie.

Sources

[SOURCE] Joseph Fourier — Théorie analytique de la chaleur (1822). Lien direct [SOURCE] D. L. Donoho et P. B. Stark — Uncertainty Principles and Signal Recovery (1989). Lien direct [SOURCE] Werner Heisenberg — Über den anschaulichen Inhalt der quantentheoretischen Kinematik und Mechanik (1927). Lien direct [SOURCE] S. Massar et P. Spindel — Uncertainty Relation for the Discrete Fourier Transform (2008). Lien direct