Fourier Transform
EXERCISES
HIGHER ALGEBRA, MATH 571, WINTER 2024
(1) Let G be a finite abelian group and H < G a subgroup. Let f = 1H be the characteristic function of H (it is 1 on H and 0 outside H). Study its Fourier transform and the implication for the Plancherel formula for ∑g∈G f(g−1)h(g), for this particular f and arbitrary h.
(2) Let G be the cyclic group Z/NZ. Let a ∈ Z/NZ and χa(t) = ζat, ζN = e2πi/N.
N
χa is a function on G (in fact, a multiplicative character), calculate its Fourier transform χˆa (viewed
as a function on G).
(3) Let G be a finite group. In general it doesn’t make sense to talk about f because f is not a function on a group, but rather on representations of a group. However, if G is abelian, fˆ is a function on
∗× ∗∗ ˆ
G = Hom(G, C ), and we have (canonically) G = G, and so one can talk about f that will be a
function on G again.
ˆ ˆ
Relate f to f when G is abelian. (The previous exercise, and our calculation of δg, should allow you to test your answer.)
(4) For g ∈ G, we can define a translation operator Tg on C(G, C). Viewing C(G, C) as the group ring C[G], Tg is just multiplication by g from the left. In terms of functions
Tg(f)(x) = f(g−1x).
Relate \Tg(f) to fˆ. What does your formula give when G = Z/NZ and g = 1?
(5) Prove that if f is a class function on G then fˆ(ρ) is a scalar for every irreducible representation ρ. In this case, show that fˆ(ρ) is the scalar operator |G| · ⟨ f , χ ̄⟩, where χ = χρ and the inner product
χ(1)
is the one we defined on class functions.
(6) Let p be an odd prime. Define the Legendre symbol ? · ? as a function on Z/pZ by
(ii) h(−1) = (−1)(p−1)/2.
p
1 x ̸= 0 is a square modulo p,
?x?=−1 x̸=0isnotasquaremodulop, p
0 x=0. For ease of notation, we put
h(x) := ? x ? . p
(a) Check the following properties of the Legendre symbol:
(i) h(xy) = h(x)h(y) for all x, y ∈ Z/pZ (in particular, h is a homomorphism Z/pZ× → {±1}).
ˆ ˆ
EXERCISES HIGHER ALGEBRA, MATH 571, WINTER 2024
(7)
(8)
Thus, η(x) considers also 0 as a quadratic residue.
Calculate the Fourier transform of the function
φ(x) = η(x) − η(x − 1).
(You will find the questions above useful for this calculation.)
(e) We say that [x,...,x+r] is a block of quadratic residues if η(x) = ··· = η(x+r) = 1 but
η(x−1) ̸= 1 and also η(x+r+1) ̸= 1. Find the number of zeros of φ(x) in terms of the number of blocks of quadratic non-residues.
Here is an example: let p equal to 7.
0123456 η 111-11-1-1
η(x)−η(x−1) 2 0 0 -2 2 -2 0
(The blocks of quadratic residues are [0, 2] and [4]. For p = 5, [4, 1] = {4, 0, 1} is a block of
quadratic residues. That is, everywhere above we read x, x − 1, x + r, etc., modulo p.)
Find an analogue for Corollary 22.3.2. when f is not necessarily a real-valued function. Use this to
derive a formula for
∑ | f (s)|2 s∈G
in terms of its Fourier transform.
Let P, Q be probability distributions on a finite set S (thus, P(s) ≥ 0 for all s ∈ S and ∑s∈S P(s) = 1,
etc. ). For a subset A ⊂ S we write P(A) for ∑s∈A P(s). Recall that we defined ∥P − Q∥max := max |P(A) − Q(A)|.
(iii) ∑x∈Z/pZ h(x) = 0.
(Hint: prove that there is a y such that h(y) = −1. Multiply the sum by h(y).)
(b) Let hˆ(x) be the Fourier transform of h(x). Prove that hˆ ( x ) = hˆ ( 1 ) · h ( x ) .
Note that hˆ(1) = ∑p−1 h(s)e2πis/p. This value hˆ(1) is an example of a Gauss sum and so we s=0
will also denote it by G. Thus, h is “essentially equal” to its Fourier transform: hˆ ( x ) = G · h ( x ) .
(To prove this identity, distinguish between the case x = 0 and x ̸= 0. In the latter case, proceed by the definition of hˆ(x) and in the sum ∑s h(s)e2πisx/p form the change of variable t = sx.)
(c) By applying the Fourier transform again, prove that
(d) Let
G2 = (−1)(p−1)/2 · p. η(x) = δ0(x) + h(x).
Prove that
A⊆S
∥ P − Q ∥ m a x = 21 ∑ | P ( s ) − Q ( s ) | .
s∈S
(The latter can also be written, per definition, as 21 ∥P − Q∥L1 .)
EXERCISES HIGHER ALGEBRA, MATH 571, WINTER 2024 3
(9) Let G be the group S3 with the probability distribution P given by P(σ) = 1/6 for all transpositions σ, P(1) = 1/2 and P((123)) = P((132)) = 0. Calculate the Fourier transform of P∗n. Using the Diaconis-Shahshahani Lemma, estimate ∥P∗n − U∥max.
(10) Consider the group Sn and let S be the set of transpositions in it. S has k := n(n − 1)/2 elements.
Define
f (σ) =
Calculate the Fourier transform of f and the Fourier transform of the probability distribution P =
f + 12 δId (note that both f and P are class functions).
What can you say about ∥P∗n − U∥max? (This is a bit of an open ended question.)
(11) Let G = D6 be the dihedral group with 12 elements, G = ⟨x,y|x6 = y2 = yxyx = 1⟩ and let S = {x, x−1, y}. For each irreducible representation ρi of G (there are four 1 dimensional represen- tations and two 2-dimensional representations – refer to the notes for a discussion of the irreducible representations of Dn) find the operators A(ρi) defined in the lectures and their eigenvalues. Find the eigenvalues of the normalized adjacency matrix of the Cayley graph of G relative to S.
Projective, injective and flat modules
(12) Let R be a ring, M, N left R-modules such that M ⊕ N is a projective module. Can we conclude that M is projective? What if M ⊕ N is an injective module – can we conclude that M is injective? What if M⊕N is a flat module – can we conclude that M is flat?
(13) Let R be a ring and P a projective R module. Prove that there is a free module Q such that P ⊕ Q is free. (Hint: rearrange an infinite sum.)
(14) Let R be a ring and A a right R module. Prove that A is flat if and only if for every exact sequence of left R-modules
· · · GG B GG B GG B GG 0 210
the sequence of abelian groups
··· GGA⊗ B GGA⊗ B GGA⊗ B GG0 R2R1R0
is also exact.
(Tryitfirstforasequenceoftheform0→B3 →B2 →B1 →B0 →0,byreplacingitbytwoSES.)
(15) Let f : A → B be a ring homomorphism and let M ∈A Mod be a flat A-module. Prove that B⊗A M is a flat B-module.
(16) Let A be a commutative ring and M, N flat A-modules. M ⊗A N is also an A-module. Prove that it is flat.1
(17) Prove that if R is a commutative PID then an R-module is injective if and only if it is divisible. Here iswesaythatanR-moduleMisdivisibleifforeverym∈M,r∈R,r̸=0,thereism′ ∈Msuch that rm′ = m. The proof is an adaptation of the result for Z-modules.2
1So the tensor product of projective, resp. flat, modules is projective, resp. flat. This is not true in general for injective modules. 2In general, a divisible module need not be injective. An example, apparently, is Q(x)/Z[x] considered as a Z[x]-module.
(1/2k σ a transposition 0 else
EXERCISES HIGHER ALGEBRA, MATH 571, WINTER 2024
(18) (19)
(20)
Prove that if R is a PID the tensor product of two injective R-modules is injective.
Prove that Q/Z has the following property. Given a non-zero abelian group C and an element
0 ̸= c ∈ C, there is a homomorphism
f:C→Q/Z, f(c)̸=0.
Let B ∈ ModR and define its character module B∗ to be the left R-module B∗ = HomZ(B, Q/Z).
(a) Prove that B → B∗ is an exact additive contravariant functor ModR → RMod.
(b) Let 0 GG A α GG B β GG C GG 0 be a sequence of R-modules and homomorphisms.
We do not assume it is a complex necessarily. Prove that the sequence
0 GGA α GGB β GGC GG0 of R-modules is exact if and only if the sequence
0 GG C∗ β∗ GGGG B∗ α∗ GG A∗ GG 0,
of abelian groups is exact.
(One direction you already proved in (a). For the other direction, for the first half, assume that there is a a ∈ A such that α(a) ̸∈ Ker(β) and let c = β(α(a)). Use the previous question. The other half also uses the previous question but now for a suitable element in B/Im(α).)
Prove that
B ∈ ModR is flat ⇐⇒ B∗ ∈ RMod is injective.
Follow the following steps:
(a) For flat implies injective, one uses in the argument the adjoint property of ⊗ and Hom.
(b) For the injective implies flat, one wants to prove that if A1 → A2 is an injective homomorphism
of R-modules then A1 ⊗ B → A2 ⊗ B is an injective homomorphism of groups. One way to show that pass is to the character groups.
Let R be a commutative integral domain and assume that I is a non-zero injective and projective R-module. Prove that R is a field.
Prove that HomR(P, R) ̸= {0} if P is a nonzero projective left R-module.
Let 0 → A → B →f C → 0 be a SES of R-modules such that C is projective. Prove that this sequence splits. Namely, that there is a homomorphism g : C → B such that f ◦ g = Id. Show further that B ∼= A ⊕ g(C) and the map f becomes the homomorphism (a, b) 7→ f (b).
Let R be a commutative integral domain and M a cyclic R module. Prove that M is free if and only if M is flat. (Hint: for any r ∈ R, r ̸= 0 multiplication by r provides an injection R → R.)
(21)
(22)
(23) (24)
(25)
Homological algebra
EXERCISES
HIGHER ALGEBRA, MATH 571, WINTER 2024 5
(26) (The Snake Lemma). Let
be a commutative diagram of modules with exact rows. The Snake Lemma states that the sequence
0 GG Ker( f ) GG Ker(g) GG Ker(h) δ GG Coker( f ) GG Coker(g) GG Coker(h) GG 0
is exact, where δ (the connecting homomorphism) was defined in the lecture and the rest of the maps are naturally induced from the α’s and β’s. Prove here that Ker(δ) is equal to the image of the preceding map.
(27) (The 9 Lemma). Consider a commutative diagram of modules:
0 GGAα1GGBβ1GGC GG0 111
fgh
?? ?? ??
0 GGAα2GGBβ2GGC GG0
?? 0 GGA
?? 0 GGA
?? ?? GG B GG C
GG 0 GG 0 GG 0
?? ?? GG B GG C
??
0 GG A GG B GG C
?? ?? ?? 000
?? ??
Assume that the columns are exact and all the rows are complexes. Prove that if the last (resp., first) two rows are exact, then so is the remaining row. (Hint: use the Snake Lemma.)
(28) (The comparison lemma for injective modules). Consider a ladder of R-modules 0 G G A ε ′ G G Q d 0′ G G Q d 1′ G G Q d 2′ G G . . .
f f0 f1
?? ?? ?? ??
f2
0 GGB ε GGI d0 GGI d1 GGI d2 GG...
where the rows are complexes, the Ij are injective modules and the top row is exact. Prove that the ladder can be completed to a commutative diagram as is indicated by the dotted arrows.
Two comments:
(a) It is in fact true that any two extensions are homotopic, just like we had in the comparison
lemma for projective modules. You are not required to prove that.
(b) The definition of f0 would probably be not too hard to figure out. Suppose that f0 was defined.
For the next step you would want to consider Q0/Ker(d0′ ) and the map on it induced from d0 ◦ f0. Why is it well-defined?? If you figure out this case, you will understand how to approach the general case.
(29) Use Tor to prove that following statement: Let
0→A′ →A→A′′ →0
EXERCISES HIGHER ALGEBRA, MATH 571, WINTER 2024
(30)
(31)
(32)
(33)
be an exact sequence of R-modules. If A′ and A′′ are flat, so is A.
Since Ext1(Z/3Z,Z/3Z) ∼= Z/3Z, the theorem about Ext1 and extensions implies that there are three equivalence classes of extensions of Z/3Z by Z/3Z. Write three such extensions and prove that none is equivalent to the other.
Let a be a positive integer. Apply Hom(−, Z) to the exact sequence 0 GGZ [a] GGZ GGZ/aZ GG0,
and use the resulting long exact sequence to calculate Extn(Z/aZ,Z).
(Another method is to note that this is a projective resolution of Z/aZ and so one can apply the recipe for Extn(Z/aZ,Z) using the resolution, but in this exercise do not use this point of view.)
By tracing through the proof of the theorem e(C, A) ∼= Ext1(C, A), prove the following:
• The zero element of Ext1(C, A) corresponds to the split extension of A by C.
• Recall that Ext1(Z/aZ,Z) ∼= Z/aZ. Find a ”push-out” model for each of the extensions.
Which of them is torsion-free?
Givenanextensionξ: 0→A→E→C→0ofR-modulesandahomomorphismh:A→A′ show that there is a diagram
ξ 0 GGA GGE GGC GG0
h
?? ??
h∗(ξ) 0 GG A′ GG E′ GG C GG 0,
where one first constructs E′ as a push-out and argues that there is a natural map E′ → C making the diagram commutative and E′ an extension of A′ by C. This is in fact the functorial map
h∗ : Ext1(C, A) → Ext1(C, A′),
coming from the formalism of derived functors, but you are not required to prove that.
Similarly,givenanextensionξ: 0→A→E→C→0andahomomorphismk:C′→Cshow that there is a diagram
k∗(ξ) 0 GG A GG E′ GG C′ GG 0 k
?? ??
ξ 0 GGA GGE GGC GG0,
where one first constructs E′ as a pull-back and argues that there is a natural map A → E′ making the diagram commutative and E′ an extension of A by C′. This is in fact the functorial map
k∗ : Ext1(C, A) → Ext1(C′, A),
coming from the formalism of derived functors, but you are not required to prove that.
For solving this exercise you should find it useful to have the concrete description we gave for pull- back and push-out. There is no homological algebra involved in this exercise, except for the context in which it is given.
Let
EXERCISES HIGHER ALGEBRA, MATH 571, WINTER 2024 7
(34) The cohomology of a cyclic group. Let G = {1, g, . . . , gn−1} be a cyclic group.
• Here you are asked to show that the following is a projective resolution of Z by Z[G]-modules.
ε : Z[G] → Z, ε(∑agg) = ∑ag. gg
Letη=1+g+···+gn−1 and
N:Z[G]→Z[G], N(x)=xη
(multiplying by the element η). Let δ = g − 1 and let D:Z[G]→Z[G], D(x)=xδ
(multiplying by the element δ). Prove that
· · · GG Z[G] N GG Z[G] D GG Z[G] N GG Z[G]
is a projective resolution.
• Deduce the following:
H0(G, A) = AG, H2n−1(G, A) = A[η]/δA,
D GG Z[G] ε
GG Z
GG 0
H2n(G, A) = AG/ηA,
• Let L/K be a cyclic Galois extension of fields with Galois group G = ⟨g⟩ of order n. Let λ ∈ L×
where A[η] = {a ∈ A : ηa = 0}.
be an element whose norm to K× is equal to 1: ∏n−1 gi(λ) = 1. Prove that there is an element
Do the same for the group C4 = Z/4Z and the matrix M = ? 0 −1 ?. 10
(36) Let B be any abelian group, N ≥ 1 an integer. Prove that Ext1(Z/NZ, B) ∼= B/NB.
What can you conclude of an exact sequence of abelian groups of the form
0→Z[1/N]→E→Z/NZ→0 ?
(37) Let G be a finite group of order N acting trivially on a finite group A, such that (|A|, N) = 1. Let 0→A→B→C→0
be a short exact sequence of abelian groups with G action (or Z[G]-modules, if you prefer). Prove that the sequence of invariants
0→AG →BG →CG →0
is exact too.
(38) Let G be a group and let A2 be an abelian group sitting in an exact sequence of groups 0→A1 →A2 →A3 →0.
Suppose that any extension of A1 by G is a semi-direct product, and that any extension of A3 by G is a semi-direct product. Prove that any extension of A2 by G is a semi-direct product.
× i=0 such that λ = g(μ)/μ. (Use also Hilbert’s 90.)
μ ∈ L
(35) The matrix M = ? 0 −1 ? has order 3. Let the group C3 = Z/3Z act on Z2 by letting a act by the
1 −1
matrix Ma. Calculate Hi(G,Z2).
EXERCISES HIGHER ALGEBRA, MATH 571, WINTER 2024
(39)
The following exercises are in the context of wallpaper groups.
The orthogonal group O2(R) consists of all 2×2 matrices A with real entries such that tAA = I2
and SO2(R) is its subgroup of matrices with determinant 1.
(a) Prove that every matrix in SO2(R) is a rotation and every matrix in O2(R) \ SO2(R) has determinant -1 and is a reflection.
(b) Let G be a finite subgroup of O2(R). Conclude that either G is contained in SO2(R) and is a cyclic group, or G ∩ SO2(R) is a subgroup of index 2 in G and G is a dihedral group.
(c) Assume further that G is a subgroup of O2(Q). That is, assume that all the entries of all the matrices in G are rational numbers. Prove then that G ∩ SO2(R) is a cyclic group of order 1,2,3,4 or 6. (This is the so-called “crystallographic restriction”. To prove it, consider eigenvalues.) Thus, the finite subgroups of O2(Q) are isomorphic to one of the cyclic groups C1, C2, C3, C4, C6, or the dihedral groups D1, D2, D3, D4, D6 3
The rigid transformations of R2 are defined to be the bijective maps T of R2 such that ∥x − y∥ = ∥Tx − Ty∥ for all x, y ∈ R2. These form the group Aff(R2). The subgroup of Aff(R2) consisting of transformations T such that T(0) = 0 is precisely O2(R) (in particular, they are automatically linear maps). One can prove that there is an exact sequence
1→R2 →Aff(R2)→O2(R)→1,
where we identify a vector v ∈ R2 with the transformation Tv (x) := x + v. This sequence splits and Aff(R2) = R2 o O2(R) and that implies that every element of Aff(R2) is a transformation of the form
x 7→ Mx + v,
where M ∈ O2(R) and v ∈ R2.
(d) Prove that the induced conjugation action of O2(R) on R2 ⊂ Aff(R2) is precisely the action of O2(R) on R2 by matrix multiplication of vectors. Write set-theoretically the elements of Aff(R2) as pairs {(v, M) : v ∈ R2, M ∈ O2(R)} and describe the group law this way.
Let G be a finite group of order m and let A be a G-module such that multiplication by m is an isomorphism of A.
(e) Prove that for all n ≥ 1, Hn(G, A) = 0. In particular, conclude that if G is a subgroup of O2(R), whose action on R2 preserves Z2, and ζ ∈ H2(G, Z2), then there are vectors {vg ∈ R2 : g ∈ G} such that
ζ(g, h) = gvh − vgh + vg.
Assume ζ is a normalized cocycle,4 namely, that it satisfies ζ(1, g) = ζ(g, 1) = 0 for all g ∈ G.
In that case it follows that v1 = 0 (so g 7→ vg is a normalized coboundary). Prove that Γ := {(x + vg, g) : x ∈ Z2, g ∈ G}
is a subgroup of Aff(R2) such that (i) Γ ∩ R2 = Z2 and (ii) the image of Γ under the group
homomorphism Aff(R2) → O2(R) is G.
(f) Prove, moreover, that the extension class of Γ is ζ. (Take the section (tg, g) for calculating the
extension class.). Conclude that if G ⊂ O2(Q) and its action on R2 preserves Z2, then any “abstract” extension of Z2 by G can be realized as a wallpaper group. 5
3Note that in this list C2 ∼= D1, but they are realized in a different fashion inside O2(R).
4Those are also called “factor sets”. The fact that one can work with “normailized” representatives for the cocycles and coboundaries is not that easy. It is proven in Rotman using the “bar resolution” (Theorem 10.24).
5To derive this conclusion one needs that every class in H2(G,Z2) is represented by a normalized cocycle. This is true, in fact in much greater generality, and we will discuss that in the context of central simple algebras. Assume that for now.
