320
10 Pourquoi 44 100 nombres ` a la seconde ?
Est-ce que l’ensemble des d k peut ˆ etre d´ eduit univoquement de l’ensemble des f l , l =
0, 1, . . . , 2N − 1 ? Ou, en d’autres mots, est-ce que la matrice
e
2πikl/2N
−N ≤k≤N −1,0≤l≤2N −1
(10.12)
peut ˆ etre invers´ ee ?
La r´ eponse d´ epend de l’observation simple suivante. Soient p un nombre rationnel
et n un entier tels que e
2πipn = 1. Alors,
n−1
l=0
e
2πipl =
0, si e
2πip
= 1,
n, si e
2πip = 1.
(10.13)
Pour le prouver, utilisons l’expression des sommes partielles de la somme g´ eom´ etrique
n−1
l=0
e
2πipl =
1 − e
2πipn
1 − e 2πip
si e
2πip
= 1
=
1 − 1
1 − e 2πip = 0.
Si e
2πip = 1, alors
n−1
l=0
e
2πipl =
n−1
l=0
(1)
l = n.
La relation (10.13) sugg` ere de faire des combinaisons lin´ eaires des ´ equations (10.11)
comme suit. Multiplions les membres de gauche et de droite de l’´ equation (10.11) par
e
−2πiml/2N et sommons sur l = 0, 1, . . . , 2N − 1. Le membre de gauche devient
A m =
2N −1
l=0
e
−2πiml/2N f l ,
et le membre de droite peut ˆ etre simplifi´ e comme suit
A m =
2N −1
l=0
N −1
k=−N
d k e
−2πiml/2N e
2πikl/2N
=
N −1
k=−N
d k
2N −1
l=0
e
2πil(k−m)/2N .
L’indice k des d k est un entier dans l’intervalle [−N, N − 1]. Si on limite l’entier m ` a ce
mˆ eme intervalle, la diff´ erence k − m est un entier dans l’intervalle [−(2N − 1), 2N − 1],
et le nombre e
2πip , o` u p = (k − m)/2N , ne sera pas ´ egal `
a 1 `
a moins que k = m. Ainsi,
la relation (10.13) permet d’obtenir