Fourier Analysis: An Introduction (Princeton Lectures in ...

1 Ibookroot October 20, 2007236 Chapter 7. FINITE Fourier ANALYSIST heorem a function onG, thenkfk2=Xe2 G| f(e)| Since the characters ofGform an orthonormal basis for thevector spaceV, and (f,e)= f(e), we have thatkfk2=(f,f)=Xe2 G(f,e) f(e)=Xe2 G| f(e)| apparent di erence of this statement with that of Theorem due to the di erent normalizations of the Fourier coe cients that a function on the circle. For eachN 1 the discrete Fouriercoe cients offare defined byaN(n)=1 NNXk=1f(e2 ik/N)e 2 ikn/N, also leta(n)=Z10f(e2 ix)e 2 inxdxdenote the ordinary Fourier coe cients off.

2 (a)Show thataN(n)=aN(n+N).(b)Prove that iffis continuous, thenaN(n)!a(n) asN! aC1function on the circle, prove that|aN(n)| c/|n|whenever0<|n| N/2.[Hint: WriteaN(n)[1 e2 i`n/N]=1 NNXk=1[f(e2 ik/N) f(e2 i(k+`)/N)]e 2 ikn/N,and choose`so that`n/Nis nearly 1/2.] a similar method, show that iffis aC2function on the circle, then|aN(n)| c/|n|2,whenever 0<|n| October 20, 20073. Exercises237As a result, prove the inversion formula forf2C2,f(e2 ix)=1Xn= 1a(n)e2 inxfrom its finite version.[Hint: For the first part, use the second symmetric di erencef(e2 i(k+`)/N)+f(e2 i(k `)/N) 2f(e2 ik/N).]

3 For the second part, ifNis odd (say), write the inversion formula asf(e2 ik/N)=X|n|<N/2aN(n)e2 ikn/N.] a character onG=Z(N), the additive group of integers that there exists a unique 0 ` N 1 so thate(k)=e`(k)=e2 i`k/Nfor allk2Z(N).Conversely, every function of this type is a character onZ(N). Deduce thate`7!`defines an isomorphism from GtoG.[Hint: Show thate(1) is anNthroot of unity.] that all characters onS1are given byen(x)=e2 inxwithn2Z,and check thaten7!ndefines an isomorphism fromcS1toZ.[Hint: IfFis continuous andF(x+y)=F(x)F(y), thenFis di erentiable.

4 Tosee this, note that ifF(0)6= 0, then for appropriate ,c=R 0F(y)dy6= 0, andcF(x)=R +xxF(y)dy. Di erentiate to conclude thatF(x)=eAxfor someA.] that all characters onRtake the forme (x)=e2 i xwith 2R,and thate 7! defines an isomorphism frombRtoR. The argument in Exercise 5applies here as =e2 NmatrixM=(ajk)1 j,k Nbyajk=N 1/2 jk.(a)Show thatMis October 20, 2007238 Chapter 7. FINITE Fourier analysis (b)Interpret the identity (Mu,Mv)=(u,v) and the fact thatM =M 1interms of Fourier series onZ(N). thatP(x)=NXn=1ane2 inx.(a)Show by using the Parseval identities for the circle andZ(N), thatZ10|P(x)|2dx=1 NNXj=1|P(j/N)|2.

5 (b)Prove the reconstruction formulaP(x)=NXj=1P(j/N)K(x (j/N))whereK(x)=e2 ixN1 e2 iNx1 e2 ix=1N(e2 ix+e2 i2x+ +e2 iNx).Observe thatPis completely determined by the valuesP(j/N) for 1 j also thatK(0) = 1, andK(j/N)=0 wheneverjis not congruent to prove the following assertions, modify the argument given in the text.(a)Show that one can compute the Fourier coe cients of a function onZ(N)whenN=3nwith at most 6 Nlog3 Noperations.(b)Generalize this toN= nwhere is an integer> groupGiscyclicif there existsg2 Gthat generates all ofG, that is,if any element inGcan be written asgnfor somen2Z.

6 Prove that a finiteabelian group is cyclic if and only if it is isomorphic toZ(N) for down the multiplicative tables for the groupsZ (3),Z (4),Z (5),Z (6),Z (8), andZ (9). Which of these groups are cyclic? thatGis a finite abelian group ande:G!Cis a function thatsatisfiese(x y)=e(x)e(y) for allx,y2G. Prove that eithereis identically 0,orenever vanishes. In the second case, show that for eachx,e(x)=e2 irforsomer2 Qof the formr=p/q,whereq=|G|.Ibookroot October 20, 20074. analogy with ordinary Fourier series, one may interpret finite Fourierexpansions using convolutions as follows.

7 SupposeGis a finite abelian group,1 Gits unit, andVthe vector space of complex-valued functions onG.(a)The convolution of two functionsfandginVis defined for eacha2 Gby(f g)(a)=1|G|Xb2Gf(b)g(a b 1).Show that for alle2 Gone has\(f g)(e)= f(e) g(e).(b)Use Theorem to show that ifeis a character onG,thenXe2 Ge(c)=0 wheneverc2 Gandc6=1G.(c)As a result of (b), show that the Fourier seriesSf(a)=Pe2 G f(e)e(a) ofa functionf2 Vtakes the formSf=f D,whereDis defined by(4)D(c)=Xe2 Ge(c)= |G|ifc=1G,0 D=f, we recover the fact thatSf=f. Loosely speaking,Dcorresponds to a Dirac delta function ; it has unit mass1|G|Xc2GD(c)=1,and (4) says that this mass is concentrated at the unit element the same interpretation as the limit of a family of good kernels.

8 (See Section 4, Chapter 2.) functionDreappears in the next chapter as 1(n).4 that ifnandmare two positive integers that are relatively prime, thenZ(nm) Z(n) Z(m).