\section{Transformée de Fourier}


\subsection{racine de l'unité}
Soit $n$ un entier ppositif.
Dans le corps des nombres complexes, 
l'équation $X^n=1$ possède exactement
$n$ solutions : les racines $n$-ième
de l'unité
$$
    x_k = \exp( \frac{2ik\pi}n ),\quad 0 \leq k < n,
$$
qui forment un groupe d'ordre $n$ engendré par
la racine primitive standard $\zeta_n = x_1 = \exp( \frac{2ik\pi}n )$.

\begin{fait}
Pour $n$ pair
$$
   \zeta_n^2 = \zeta_{\frac n2},
\quad
\text{en particulier}
\quad
   \zeta_n^{\frac n2} = -1.
$$
\end{fait}

\begin{fait}
Soit $x$ une racine \ieme n,
$$
1+x+x^2+\ldots+x^{n-1}=\sum_{i=0}^{n-1} x^i =
\begin{cases}
n,   &x=1;\\
0,   &x\not=1.\\
\end{cases}
$$
\end{fait}

\subsection{transformée de Fourier}

La transformation de Fourier est une 
application de $\C[X]_n$ dans lui-même:

$$
   f(X)\mapsto \tfr f(X) =\sum_{i=0}^{n-1} f(\zeta_n^k) X^k
$$

\begin{fait}
L'inverse de la tranformée de Fourier est
$$
   f(X)\mapsto \inv f(X) =\sum_{i=0}^{n-1} f(\bar\zeta_n^k) X^k
$$
\end{fait}


On décompose le polynôme $f(X) =\sum_{i=0}^{n-1} a_i X^i$ 
en regroupant la partie paire et la partie impaire :
$$
f(X) = g( X^2 ) + X h(X^2), 
\quad g(X)=\sum_{2i < n} a_{2i} X^i
\quad h(X)=\sum_{2i + 1 < n} a_{2i+1} X^i.
$$ 


\begin{fait}
On suppose $n$ pair. Pour tout entier $k$,
$$
f( \zeta_n^k ) = g(\zeta_{n/2}^k) + \zeta_n^k h(\zeta_{n/2}^k)
$$
et
$$
f( \zeta_n^{k+\frac n2} ) = g(\zeta_{n/2}^k) -  \zeta_n^k h(\zeta_{n/2}^k)
$$
\end{fait}

\subsection{transformation rapide}
