Lecture 29: Results on Fourier coefficients of two functions

IIT Kanpur July 201
20 followers
Sep 6, 2024
[Music]
welcome uh in the last lecture we posed
ourself a question if n is factorized
with M and M Prime and if my f is
defined in terms of uh f is defined from
ZM Prime
to Z so this is what we have
said uh and uh we would like to compute
the forar coefficient of this G in terms
of the capital F so now this I can put
it as a
theorem
so
let capital N isal M into M Prime
and F is from z n by m to
C
Define
G of n is equal to F of n by m uh
n by
m uh for n isal to 0 Plus or - M plus or
- 2 m and like this and Z
otherwise
then G of
K is equal to 1 by m f of K
second also if I Define G of
n
if G of n is equal to F of
n remember that so up to M Prime minus
one there is no problem so if n is
greater than so which means if we're
taking suppose say n is = to 4 m Prime
is equal to 2 then so G of 0 this is
equal to F of 0 g of 1 this is equal to
F of 1 now G of 2 now 2 is going to
corresponds in Z2 as zero so I will
Define this as F of 0 and G of3 is f of
one so this is what is the meaning of f
g of n is equal to F of n
then G of
K this is equal to F of K by
m if K is = to 0 Plus or Min - M plus or
- 2 m and so on and so forth and zero
otherwise okay
so this so let's prove
this G of K if I take then this is equal
to by definition 1 by n summation / n is
equal
to 0 to n minus of 1 G of n e to the
power - 2 pi i k n by n
now G of n is defined like this so this
we can write is that summation / 1 by
n then this is when n is divisible by m
g is taking nonzero value otherwise it
is taking the zero value so now this is
equal to I'll write it at n Prime is
equal to 0 to n by m minus of 1 F of n
Prime then e to the
power - 2 pi
i
k this n is equal
to
uh uh M uh MN Prime so therefore this is
MN Prime ided by n
and uh this one is uh going to
be now n is = to m m Prime so now this
is 1 by m into 1 by n by m summation
Over N Prime is = 0 to n by n
-1 i k
and this is n Prime / n by
m so this is nothing but the forar
coefficient
of
f so just writing it down one can easily
get this now for the proof of
uh
two so this is uh
this is summation Over N = 0 to n minus
of 1 let's let me try g k e to the power
2 pi i k n by n this by forer inversion
formula this is GN now in our definition
it is FN now if I want to put the forer
inversion formula over here so this is
going to be some
over K isal 0
to uh n by m minus of
1 F capital F of
K and e to the power 2 pi i
k
uh n n is here divided
by uh n by m
so now equating the coefficient of this
now what do we get we get that g of K is
equal to let me denote
uh this to be K Prime K Prime K Prime is
equal to F of K
Prime
if K Prime of M into m n this is equal
to K N that means this is equal
to uh what does that mean that means K
Prime is equal to K by
m and that's what we would like to get K
Prime so hence G of K is equal to and
otherwise this is zero g of K is going
to be zero if it is not of this form
because they linearly
independent so so therefore what we get
is that this is f of K by m if K is
equal to whenever K is divisible by
m and zero otherwise just with the
comparing the
coefficient okay
so now let's uh let's see some
interesting
uh example based on this observation so
which is
uh going to be very useful in certain
aspects of mathematics and its
application so this is uh let's say look
at a concrete
example let f is from
Z4 to C
now G I am taking from
Z8 to
C now what I
Define uh let's say G of n this is equal
to F of n by 2 if n is
even and zero otherwise
because 8 is 2 * 4 so our M Prime is 4
and M is
2 so then how does this map is going to
look like if I have f of0 is some a uh F
of one is b f of 2 is c f of 3 is D then
G is going to be defined as G of 0 is
equal to
a g of 1 this is equal to0 G of 2 this
is equal to F of 1 which is equal to b g
of 3 is equal to 0 g of 4 which is equal
to C G5 0
G6 D G7
is equal to
Z so this I can write this as if
f a b c d then what we get our G is
equal to
a0
b0
c0
d0 is if now
let X F of a is equal to a uh capital F
at for your
coefficient because this is going to be
again in j4 D then now if I write the
forer coefficient of G this is going to
be this is going to be 1/2 1 by m m is 2
and then
the 1 by two and then this is
a
b c
D again now G of five what we are going
to look at so this is going to be a b c
d because as you can see what we have
derived is uh here here this is defined
in this way so now this is G of K = to 1
by m f of K there in that case m is 2 so
therefore now five will correspond to
Z4 4 is going to correspond to uh 0 and
uh 5 will be correspond to 1 0o 5 is
correspond to 1 6 is correspond to three
and 7 is will correspond uh
uh two and then this D is going to
correspond to three so similarly if I
Define my uh uh
f a g to
be let's say I will add two more
zeros B 0 0 C 0 0 and D 0 0 that means I
am looking at z12 now here m is three
therefore now this G is going to be 1x3
then a b c
d AB b c
d a b c
d so now for the other part if we would
like to Define our G to
be a b c d a b c d that means G of n is
equal to F of n this is what corresponds
to G of n isal to F of
n now in this case if I
by what we have derived in the theorem
let's write down the g g is going to be
if it is K by m if K is of the form plus
or minus M and zero or the wise it is
zero that is what the G of K would be so
the first one is
a then I have one is zero because it is
not divisible by three so now this is uh
going to be
B
0
C there here m is 2 so 0 and D 0
so six I will get D that is uh F of 3
here four F of
2 uh in the case of two F of one that is
B and zero case f of 0 capital F of 0
that is a and the rest of the things are
zero so now this is you can see that I
mean if I am going to put certain just
if I want to extend my function from one
uh finite group to another multiple of n
then essentially when I am Computing the
forer transform so on the places I am
going to uh fill up the places either by
zero or repeating the forar
coefficients
so so another interesting observation
one can also get I will write it in the
form of the proposition
so
let F from Zed M into
n to
C
and G I am defining from
ZN to C the other other side so here F I
have been given with a some let's say 2
N and G is a function uh
uh uh from n to C then uh what is going
to be the for transform of G Vis is the
given foror transform of f so one if
suppose G of
n so what I am doing is some sort of the
periodization so that I will get into M
into n
so now this function if I am
defining to be L is equal to 0
to M minus of
1 F of n minus
Ln this is a periodization so now
then
then G of
K this is going to be M * F of M
K and then the second one is that if G
of n this is equal to F of
MN
then G of K this is equal to summation
over L is = 0 to M minus of 1 F
of K -
Ln okay
so what is the proof of uh this
so now I write 1 G of K this is is equal
to 1 by n summation Over N is = to 0 to
uh n minus of
1 uh this is G of n e power - 2 pi i k n
by
n and we know the formula from 1 by n
and this if I put the value this is L =
to 0 to M minus of 1 F of n-
Ln that is the definition of g e to the
power - 2 pi i k n by
n
now recall that e^ 2 pi I any integer
that is going to be
one so therefore this I can write this
as 1 by
n summation / n is from 0 to nus of 1
summation over L from 0 to n -1 F of N -
Ln into E power - 2 <
i k *
L
minus
uh uh
nus
Ln ided by n because Ln by n is L and e^
2 pi i k l this is nothing but 1 so
therefore I can write this now these two
sums if I am writing then this is going
to be 1 by n combining this two terms is
some n Prime this is equal to 0
to MN minus of 1 F of n Prime e^ - 2 pi
i k n Prime by
n
so this I can do this as
uh uh I will multiply M by m uh so so
this I can now again I can write this as
MN Prime
by MN mm gets cancelled so this is 1 by
n so I want a factor of so this I can
write M into n m so this is nothing but
the foure coefficient of
f uh that is what we want to prove F of
MK
because this is the MK is coming okay so
exactly in the similar fashion one can
get that uh um the second part of this
so which uh if you
uh uh do the break of this breaking of
the sum like this you will get the
second part proof
is
similar now so it will be
interesting the interesting question is
going to be that uh how
efficiently we can
compute the forer coefficient in a
finite group group in Jen that is what
uh how many that's what it says that
finally if we ask the computer to
compute the forer coefficient then how
many steps it requires now let us uh try
to understand this problem so now what
we want to get is that we have a
function f
from J N to
C and we are denoting the for year
coefficient of f is this is again a
function from z n to
C so we
can that means we are
defining F isal 4er coefficient just I'm
changing the symbol this is what so now
let's look at my f
this is equal
to the column Vector F of 0 f
of1 and f of
nus1 and uh capital F this is going to
be equal to F of 0 f of
1 F of n minus of 1
now I need to find a matrix script F
which is going to give me that if I act
on this F column Vector I am going to
get uh capital F the for your
coefficient again the column Vector so
I'm looking for a n cross n Matrix which
is going to give me
um the foror coefficient let's take
let Omega isal E power - 2 pi
i n by
n
so now now let's look at so what is our
forer coefficient forer coefficient
let's 1 by n summation Over N is equal =
to 0 to n -1 F of n e the power - 2 piun
i
n uh K by n this is what we would like
to uh see so
now this
is no n
now consider the Matrix f is 1 /
n
1 1
1 1
1
1 1 this is Omega this is omega squ
omega to the^ nus of 1 this is omega squ
omega to the^
4 and Omega 2 into n minus of 1 and this
is Omega N - of 1 Omega 2 * N - of 1 and
Omega N - of 1 n minus of
one this is what we have defined now if
I compute
F acting on F then this is going to be
F0 to FN minus F1 now this is now this
is summation
over F of n n is = 0 to n minus of 1 so
now if K is equal to 0 then this is what
exactly what we have
got so so this is nothing but F
of0 now in the second row if I am
multiplying it then what I am going to
get I am going to get F0
plus uh F of 1 into e the
power uh 2
pi uh K is 1 I divided by n
plus F of
2 and this goes on up to F of n minus of
1
then this one is Omega e the power 2 pi
I uh n uh n minus of 1 by n and this is
nothing but F of
one and so
if you do the last one so this is f of 0
+ Omega to^ n minus of 1 means e^ - 2 pi
i n minus of
1 by n so now that will corresponds to F
of n minus of1 so now this is equal to F
just by the matrix
multiplication now this is that uh so
how many arithmetic operation we are now
doing to compute all the forer
coefficient given a function f so what
we are doing is that's now
multiplication of the N cross n Matrix
is going to give uh give all our uh
foror coefficients which means on on
each of the thing I am multiplying n
times and adding n times and uh so there
are n such columns so it is a think
something of the order of n Square so
now if I am going for a large ZN for n
large then the computation is going to
be n Square kind of order of n Square
which is pretty big now the question is
that can we
reduce this n
Square uh to a lesser quantity can we
calculate the for transform more smartly
so that we will require less number of
steps so that we are going to see it in
the next lecture thank you
[Music]
[Music]
[Music]
