Lecture 27: Fourier transform on Z(N)

IIT Kanpur July 201
20 followers
Sep 8, 2024
[Music]
welcome in the last lecture we have
defined the forear coefficient let us
recall that this is a map we are
considering to
see uh complex function and then we
Define denote the forar efficient as the
capital F which is 1 / n summation / n =
0
to
um n -1 F of n e power - 2 pi i k by K N
by
n okay so then easily one can see that
some basic properties
if
if f and
g are four year
coefficient of functions f and
g respectively
then uh F + G
is the forer
coefficient of f + G that is uh just the
linearity of the sum is going to give us
uh this much because
suppose
h of K the for your coefficient of f + G
this is 1 by n n = 0 to n minus of 1 F +
G of n e the^ - 2 pi i k n by n then
this is if you split the sum you are
going to get F of K plus G of
K okay so in
general if
FJ from ZN to
C and J is equal to 1 to some M
then the four year coefficient
of summation over J from 1 to M FJ is
given
by summation over J from 1 to m f j that
means individual forer coefficients they
get
added then the second one is that
let G of n this is equal to F of capital
N minus of n where f is a function from
ZN to C and I Define then G becomes a
function also from ZN to
C uh therefore the forer coefficient of
this is if you do it g k the foror
coefficient of G then this is going to
be 1 by
n g of n e the power - 2 pi i k n by n
which is equal to 1 by n summation / n =
0 to n -1 F of nus of N e^ - 2 pi i k n
by n now
of course so if I make a change of
variable that capital of n minus of n is
equal to l then this L is going to vary
from 0 to n minus1
again right and so therefore this is we
can get
n l = 0 to n minus of1 F of l e the^ - 2
pi i k and this n is replaced
by this n is uh
replaced by
L uh n minus of
L by
n because I'm taking n minus
of n this is equal to l so therefore
this is 1 by n summation / L = 0 2 N -1
F of l e to the power 2 pi i k l by n
because again by the two uh by
periodicity of this so this is equal to
F the for transform at minus K so
remember that minus K in my notation is
the inverse of the K in Jen that is the
n minus K so that's what is
uh one can see and then the second is so
if we take third you take GN to
be equal to FN
bar then of course what you can get this
GK then you can take
the bar out outside the sum so e to the
power so this is summation n = 0 to n
minus of 1 FN bar E power - 2 pi i k n
by n now if I take the bar whole outside
n minus of one then this is FN e^ 2 pi i
k n by n and this so again this is is
equal to
1 F minus of K
bar
so now one of the thing what we observed
in the forer transform uh in the forer
series case is that if I translate then
I take the for transform then it was HED
by a character so similar kind of thing
is going to be true over here now you
define G of n is equal to F of n minus
of n for some fixed n then if you
compute just like that you you are going
to get G of K this is equal to uh he he
by the character it is e to^ 2 pi i
k
n by n into F of
K because you can pull out the K * n not
by n that will be independent of n in
the sum variable so we can get that
so
and the converse is also true now if you
take G of n you hit that with a
character 2 pi i k uh 2 pi i n
not by
n uh G of n is n n not by n uh and F of
n then G of K this you are going to get
that this is f of K minus n just you
take the sum inside then what you are
going to get is
this
okay so now another important uh uh
property what what we have
exploited uh in the for year series case
uh that is
uh the
convolution so now we can Define the
convolution
let f g is from J then to C
Define f convolution of
g at n this is equal to 1 by n summation
over J is = 0 to n minus of 1 F of N -
J G of J as you can see that uh I can
Define actually f for any integer
because every integer is going to have a
representative with respect to capital N
uh in among the number um uh 0 to n
minus one as a matter of fact they are
equivalence class I can Define each of
them suppose zero is going to be the
same as n 2 N 3 n 4 and 5 n 6 n minus n
like this one would be n + 1
right and then you you are going to 2 N
+ 1 3 n + 1 like
this
uh so therefore there is absolutely no
ambiguity in defining F of n minus of J
so uh
now there what we have seen when we did
the convolution there we found found
that actually that does not exist any G
such that F convolution of G is equal to
F for all
F because
uh uh if I take the the argument there
was if I take the foror transform then
what we get that g hat of n is equal to
1 and which contradicts the remma
let's see whether we have something here
similar or we have something better so
Define G of n is equal to 1 if n is
equal to 0 Z
otherwise that is again Delta 0
then now F convolution of Delta 0 at n
this is going to be 1 by n summation n =
0 to n
-1 F of
J Delta 0
of n minus of J as you can see here
because uh this is an abent group so I
can uh this I can take that this is also
equal to n summation over J from 0 to n
minus of 1 F of J G of n minus of J so
that is uh nothing to just the change of
variable is going to give me this and uh
and
if this it can also if convolution G is
equal to G convolution of f so now here
let us look at this now the sum this
this one is going to survive only when
this n is equal to
J I mean rather J is equal to n because
n is fixed uh here we have j = 0 to n
minus of
1 so whenever J is equal to n then it is
going to survive rest of the for the
rest of the J this will be zero this
Delta 0 would be zero so only term which
get survived is
uh F of
uh
n
so now if I do a little bit of this if I
Define my G to be n time Delta 0 of n
then uh that is g is taking the value n
when n is equal to 0 and taking the
value 0 when n is not equal to Z then in
that case what I get is for this G at n
this is going to be
one ah sorry this is going to be F
because any is going to get HED because
this value is going to take the value
capital N therefore what we so here in
contrast with the four year series here
what we have found is that
it has an
identity okay so now the next one of the
most important properties of the
convolution uh we have used is the forer
transform convolution we have seen uh as
a product
on the domain side and uh with the
function side then when I take the for
transform it is going to take F to F
because it is uh pointwise
multiplication in uh uh for similar kind
of thing
let
H be
the foror transform
of f convolution of
G so let me write down then this h k
this is equal to 1 by n summation / n =
0 to nus of 1 F convolution of g at N e^
- 2 pi i k n by n now I will open
up f convolution
g this is equal to 1 by n² is going to
come out which is equal to 0 to n minus
of 1 F of J G of n minus of J e^ - 2i i
k n by
n now first I will do the n
sum so this is j = 0 to n minus of 1 F
of J then 1 by n summ over j = 0 to n uh
n is = 0 to n
-1 G of N - J e^ - 2 pi i k n by n now I
make a change a variable n minus J so
now here I am going to get an extra
Factor so this is going to
get 1 by n summation /
J from 0 to n
-1 F of j e to the power minus 2 pi i k
j by n into this is G
of uh
K so now the first quantity is nothing
but F of K and G of K so exactly it
follows that uh
the foror transform of f convolution g
is going to be the foror transform of f
times the for transform of
G
okay so now and then what we must try to
get so the one of the most important
thing there was that the inversion and
the plal so now let us see that whether
we are going to get this over here or
not now you
take
consider V to be the set of all
functions
now of course uh V is going to be a
vector space because if I take two
functions then uh some pointwise sum F +
g n is equal to FN + GN this is again a
function and if I hit that with a scalar
then that is again going to give us a
function so V is a vector space
now if it is a vector space then it's
going it must have basis element so what
are the basis elements of this
uh so now
Define e0 of n this e or rather EI of n
this is equal to 1 if n = to I and Z
otherwise and this is for the function I
from
zero I varies over this for each I from
0 to n minus one I Define this function
so there are n types of n of this
function now this e
linearly
independent as if you take I from one 0
to n minus of 1 a i EI this is equal to
zero that means this is true for every n
for all n belongs to zed n then here
only n it is going to survive is that I
is equal to n therefore alpha n is equal
to Z for all
n a n is equal to zero for all n
therefore they are linearly independent
and now one can see that if you take a
function
let f is
from Jen
to C and F of n is equal to alpha n then
this F can be written as F of n this is
equal to summation over J from 0
to n minus of 1 Alpha j
e uh J of n so that's uh basically says
that this spans the whole thing
therefore the dimension of V is equal to
n okay so now once we have a vector
space then it is natural for us to
define the inner product in that Vector
space
let f and g this belongs to this Vector
space then
Define the inner product FG
this is = 1 by n summation / n = 0 to
nus of 1 F of n g of n
Bar and uh as usual I will denote Square
this is equal
to F comma F which is equal to 1 by n
summation / n = 0 to n minus of
one mod
FN
s this is the so-called Norm so now what
we need to find is uh that whether we
have
uh uh the inversion as and Par identity
in this
setting uh recall one thing that in the
forer series case we have
exploited uh that e to the power i n
Theta they are
going they orthogonal
family and
uh with a scalar multiplication they
become orthonormal and that we have
exploited heavily while doing the four
year series so now simil let's see that
the similar thing is going to be true
here or not so let me write it as a
LMA the
family e0 to e n minus of one
is an orthogonal
family the proof is uh trivial uh what
do I mean by the orthogonal family let
me uh Define it that means e
m uh e j this is equal to zero if m not
equal to J
moreover e
m e m this is equal to 1 by
n
now let's let's do the proof proof is
simple just writing down the definition
e m EJ this is equal to 1 by n summation
Over N =
to uh 0 to n minus of 1 and
uh so this is actually this is going to
be equal
to
one so this is e
m of n e j of n so this is equal to 1 by
n and if as you can see that you are
doing the pointwise evaluation of n is
not equal to M this is equal to zero and
uh if so only surviving term is going to
occur is that provided it is going to be
equal to one pro if
M = to J if m is not equal to and this
is equal to zero if m is not equal to
J uh because if m is whever e m is going
to take the value one EJ is going to
take the value zero because M and J they
are not equal therefore you are going to
get that this is but this this is an
orthogonal family but this is on the
function side which is actually not
going to give uh any kind of result uh
in the for year analysis because we want
to look at the orthogonal family in
terms of uh on the forer side that means
there we are looking at e^ 2 pi i n
Theta so similarly
Define f of n or
I uh K of n this is equal
to uh E power 2 pi i k n by n now
whether this is an orthogonal this is a
function and which is orthogonal in uh
so obviously all this uh F K this
belongs to V now if I take F K and f j
this is equal to by definition 1 by n
summation
over
uh n = 0 to
n-1 f k n and F JN bar which is equal to
1 by n summation
k n by n into e^ - 2i I JN by n this is
equal to 1 by n summation / n = 0 to nus
of 1 e^ 2 pi i k - J of n by n now if K
is not equal to K is not equal to J then
these are all the N uh root of unity so
therefore this if is equal to Z if K is
not equal to J so now this is an
orthogonal family this is and this is
what we are going to exploit to get
results in this setting thank you
[Music]
[Music]
[Music]
