Transformation de Fourier à valeurs dans un corps fini

Soit ${\displaystyle G}$ un groupe abélien fini d'ordre ${\displaystyle \vert G\vert }$ et d'exposant une puissance ${\displaystyle n}$-ième d'un nombre premier ${\displaystyle p}$, ${\displaystyle \mathbb {F} _{p^{n}}}$ le corps fini de cardinal ${\displaystyle p^{n}}$, ${\displaystyle \chi }$ un caractère à valeur dans ${\displaystyle \mathbb {F} _{p^{n}}}$ et ${\displaystyle f}$ une fonction de ${\displaystyle G}$ dans ${\displaystyle \mathbb {F} _{p^{n}}}$. La transformée de Fourier de ${\displaystyle f}$ est une fonction, souvent notée ${\displaystyle {\widehat {f}}}$ de l'ensemble des caractères de ${\displaystyle G}$ dans le corps ${\displaystyle \mathbb {F} _{p^{n}}}$ définie par :^{[réf. nécessaire]}

${\displaystyle {\widehat {f}}(\chi )\ ={\frac {1}{\vert G\vert }}\sum _{s\in G}f(s)\chi (s)^{-1}}$.

Le contexte est identique à celui de l'analyse harmonique classique d'un groupe abélien fini. La forme bilinéaire associée à l'algèbre du groupe est alors la suivante :

${\displaystyle \forall f,h\in \mathbb {F} _{p^{n}}^{G}\quad \langle f\mid h\rangle ={\frac {1}{\vert G\vert }}\sum _{s\in G}f(s)^{-1}h(s)}$

L'ensemble des résultats de la théorie de l'analyse harmonique s'applique, on dispose ainsi de l'égalité de Parseval, du théorème de Plancherel, d'un produit de convolution, de la dualité de Pontryagin ou encore de la formule sommatoire de Poisson.

Il existe un cas particulier, celui ou le groupe G est le groupe additif d'un espace vectoriel fini. Un cas particulier est celui ou G est un corps.

La transformation discrète de Fourier est donnée par

${\displaystyle f_{j}=\sum _{k=0}^{n-1}x_{k}\left(e^{-{\frac {2\pi i}{n}}}\right)^{jk}\quad \quad j=0,\dots ,n-1}$

La transformation théorique de nombre^[Quoi ?] opère sur une suite de n nombres, modulo un nombre premier p de la forme ${\displaystyle p=\xi n+1\,}$, où ${\displaystyle \xi \,}$ peut être tout nombre entier positif.

Le nombre ${\displaystyle e^{-{\frac {2\pi i}{n}}}\,}$ est remplacé par un nombre ${\displaystyle \omega ^{\xi }\,}$ où ${\displaystyle \omega \,}$ est une racine primitive de p, un nombre où le plus petit nombre entier positif ${\displaystyle \alpha \,}$ où ${\displaystyle \omega ^{\alpha }=1\,}$ est ${\displaystyle \alpha =p-1\,}$. Il devrait y avoir une quantité d'${\displaystyle \omega \,}$ qui satisfassent à cette condition. Les deux nombres ${\displaystyle e^{-{\frac {2\pi i}{n}}}\,}$ et ${\displaystyle \omega ^{\xi }\,}$ élevés à la puissance n sont égaux à 1 (mod p), toutes les puissances inférieures différentes de 1.

La transformation théorique de nombre est donnée par

${\displaystyle f(x)_{j}=\sum _{k=0}^{n-1}x_{k}(\omega ^{\xi })^{jk}\mod p\quad \quad j=0,\dots ,n-1}$

La transformation inverse est donnée par

${\displaystyle f^{-1}(x)_{h}=n^{p-2}\sum _{j=0}^{n-1}x_{j}(\omega ^{p-1-\xi })^{hj}\mod p\quad \quad h=0,\dots ,n-1}$

${\displaystyle \omega ^{(p-1-\xi )}=\omega ^{-\xi }\,}$, l'inverse de ${\displaystyle \omega ^{\xi }\,}$, et ${\displaystyle n^{p-2}=n^{-1}\,}$, l'inverse de n. (mod p)

On vérifie que cette formule donne bien l'inverse car la somme ${\displaystyle \sum _{k=0}^{n-1}z^{k}}$ vaut ${\displaystyle n}$ pour ${\displaystyle z=1}$ et est nulle pour tous les autres valeurs de ${\displaystyle z}$ vérifiant ${\displaystyle z^{n}=1}$. En effet, on a la relation (qui est vérifiée dans tout anneau)

${\displaystyle (z-1)\left(\sum _{k=0}^{n-1}z^{k}\right)=z^{n}-1}$.

Soit, pour une racine ${\displaystyle n}$-ème de l'unité

${\displaystyle (z-1)\left(\sum _{k=0}^{n-1}z^{k}\right)=0}$.

Un corps étant intègre, un des facteurs (au moins) de ce produit est nul. Donc, soit ${\displaystyle z=1}$ et trivialement ${\displaystyle \sum _{k=0}^{n-1}z^{k}=\sum _{k=0}^{n-1}1=n}$, soit ${\displaystyle z\neq 1}$ et nécessairement ${\displaystyle \sum _{k=0}^{n-1}z^{k}=0}$.

Nous pouvons maintenant compléter la démonstration. Nous prenons la transformation inverse de la transformation.

${\displaystyle {\begin{aligned}f^{-1}(f(x))_{h}&=n^{p-2}\sum _{j=0}^{n-1}\left(\sum _{k=0}^{n-1}x_{k}\left(\omega ^{\xi }\right)^{jk}\right)(\omega ^{p-1-\xi })^{hj}\mod p\\&=n^{p-2}\sum _{j=0}^{n-1}\sum _{k=0}^{n-1}x_{k}(\omega ^{\xi })^{jk-hj}\mod p\\&=n^{p-2}\sum _{k=0}^{n-1}x_{k}\sum _{j=0}^{n-1}(\omega ^{\xi (k-h)})^{j}\mod p\\&=n^{p-2}\sum _{k=0}^{n-1}x_{k}\left\{{\begin{matrix}n,&k=h\\0,&k\neq h\end{matrix}}\right\}\mod p&{\text{puisque }}\omega ^{\xi }=1,\\&=n^{p-2}x_{h}n=x_{h}\mod p\end{aligned}}}$