Preface |
|
xi | |
|
Part I Finite Abelian groups and the DFT |
|
|
|
|
3 | (43) |
|
1.1 Preliminaries in number theory |
|
|
3 | (7) |
|
1.2 Structure theory of finite Abelian groups: preliminary results |
|
|
10 | (8) |
|
1.3 Structure theory of finite Abelian groups: the theorems |
|
|
18 | (8) |
|
1.4 Generalities on endomorphisms and automorphisms of finite Abelian groups |
|
|
26 | (4) |
|
1.5 Endomorphisms and automorphisms of finite cyclic groups |
|
|
30 | (5) |
|
1.6 The endomorphism ring of a finite Abelian p-group |
|
|
35 | (5) |
|
1.7 The automorphisms of a finite Abelian p-group |
|
|
40 | (2) |
|
1.8 The cardinality of Aut(A) |
|
|
42 | (4) |
|
2 The Fourier transform on finite Abelian groups |
|
|
46 | (28) |
|
|
46 | (2) |
|
2.2 Characters of finite cyclic groups |
|
|
48 | (2) |
|
2.3 Characters of finite Abelian groups |
|
|
50 | (3) |
|
2.4 The Fourier transform |
|
|
53 | (6) |
|
2.5 Poisson's formulas and the uncertainty principle |
|
|
59 | (3) |
|
2.6 Tao's uncertainty principle for cyclic groups |
|
|
62 | (12) |
|
3 Dirichlet's theorem on primes in arithmetic progressions |
|
|
74 | (27) |
|
3.1 Analytic preliminaries |
|
|
74 | (10) |
|
3.2 Preliminaries on multiplicative characters |
|
|
84 | (5) |
|
3.3 Dirichlet L-functions |
|
|
89 | (7) |
|
|
96 | (3) |
|
|
99 | (2) |
|
4 Spectral analysis of the DFT and number theory |
|
|
101 | (28) |
|
|
101 | (6) |
|
4.2 The decomposition into eigenspaces |
|
|
107 | (8) |
|
4.3 Applications: some classical results by Gauss and Schur |
|
|
115 | (1) |
|
4.4 Quadratic reciprocity and Gauss sums |
|
|
116 | (13) |
|
5 The Fast Fourier Transform |
|
|
129 | (38) |
|
5.1 A preliminary example |
|
|
129 | (2) |
|
|
131 | (8) |
|
5.3 Permutation matrices and Kronecker products |
|
|
139 | (12) |
|
5.4 The matrix form of the FFT |
|
|
151 | (10) |
|
5.5 Algorithmic aspects of the FFT |
|
|
161 | (6) |
|
Part II Finite fields and their characters |
|
|
|
|
167 | (30) |
|
6.1 Preliminaries on ring theory |
|
|
167 | (4) |
|
6.2 Finite algebraic extensions |
|
|
171 | (5) |
|
6.3 The structure of finite fields |
|
|
176 | (1) |
|
6.4 The Frobenius automorphism |
|
|
177 | (1) |
|
6.5 Existence and uniqueness of Galois fields |
|
|
178 | (5) |
|
6.6 Subfields and irreducible polynomials |
|
|
183 | (4) |
|
|
187 | (5) |
|
|
192 | (5) |
|
7 Character theory of finite fields |
|
|
197 | (38) |
|
7.1 Generalities on additive and multiplicative characters |
|
|
197 | (4) |
|
7.2 Decomposable characters |
|
|
201 | (2) |
|
7.3 Generalized Kloosterman sums |
|
|
203 | (7) |
|
|
210 | (3) |
|
7.5 The Hasse-Davenport identity |
|
|
213 | (4) |
|
|
217 | (5) |
|
7.7 On the number of solutions of equations |
|
|
222 | (5) |
|
7.8 The FFT over a finite field |
|
|
227 | (8) |
|
Part III Graphs and expanders |
|
|
|
8 Graphs and their products |
|
|
235 | (48) |
|
8.1 Graphs and their adjacency matrix |
|
|
235 | (6) |
|
8.2 Strongly regular graphs |
|
|
241 | (4) |
|
|
245 | (2) |
|
|
247 | (1) |
|
|
248 | (2) |
|
|
250 | (2) |
|
|
252 | (6) |
|
8.8 Cartesian, tensor, and lexicographic products of graphs |
|
|
258 | (7) |
|
8.9 Wreath product of finite graphs |
|
|
265 | (3) |
|
8.10 Lamplighter graphs and their spectral analysis |
|
|
268 | (2) |
|
8.11 The lamplighter on the complete graph |
|
|
270 | (3) |
|
8.12 The replacement product |
|
|
273 | (4) |
|
|
277 | (2) |
|
8.14 Cayley graphs, semidirect products, replacement products, and zig-zag products |
|
|
279 | (4) |
|
9 Expanders and Ramanujan graphs |
|
|
283 | (60) |
|
9.1 The Alon-Milman-Dodziuk theorem |
|
|
284 | (11) |
|
9.2 The Alon-Boppana-Serre theorem |
|
|
295 | (5) |
|
9.3 Nilli's proof of the Alon-Boppana-Serre theorem |
|
|
300 | (7) |
|
|
307 | (2) |
|
|
309 | (2) |
|
|
311 | (9) |
|
9.7 The Alon-Schwartz-Shapira estimate |
|
|
320 | (7) |
|
9.8 Estimates of the first nontrivial eigenvalue for the Zig-Zag product |
|
|
327 | (11) |
|
9.9 Explicit construction of expanders via the Zig-Zag product |
|
|
338 | (5) |
|
Part IV Harmonic analysis on finite linear groups |
|
|
|
10 Representation theory of finite groups |
|
|
343 | (56) |
|
10.1 Representations, irreducibility, and equivalence |
|
|
343 | (6) |
|
10.2 Schur's lemma and the orthogonality relations |
|
|
349 | (12) |
|
10.3 The group algebra and the Fourier transform |
|
|
361 | (11) |
|
10.4 Group actions and permutation characters |
|
|
372 | (8) |
|
10.5 Conjugate representations and tensor products |
|
|
380 | (10) |
|
10.6 The commutant of a representation |
|
|
390 | (7) |
|
10.7 A noncommutative FFT |
|
|
397 | (2) |
|
11 Induced representations and Mackey theory |
|
|
399 | (27) |
|
11.1 Induced representations |
|
|
399 | (10) |
|
11.2 Frobenius reciprocity |
|
|
409 | (4) |
|
11.3 Preliminaries on Mackey's theory |
|
|
413 | (1) |
|
11.4 Mackey's formula for invariants |
|
|
414 | (5) |
|
|
419 | (2) |
|
11.6 The Mackey-Wigner little group method |
|
|
421 | (3) |
|
11.7 Semidirect products with an Abelian group |
|
|
424 | (2) |
|
12 Fourier analysis on finite affine groups and finite Heisenberg groups |
|
|
426 | (34) |
|
12.1 Representation theory of the affine group Aff(Fq) |
|
|
426 | (6) |
|
12.2 Representation theory of the affine group Aff(Z/nZ) |
|
|
432 | (5) |
|
12.3 Representation theory of the Heisenberg group H3(Z/nZ) |
|
|
437 | (6) |
|
|
443 | (4) |
|
|
447 | (10) |
|
12.6 Representation theory of the Heisenberg group H3(Fq) |
|
|
457 | (3) |
|
13 Hecke algebras and multiplicity-free triples |
|
|
460 | (22) |
|
13.1 Preliminaries and notation |
|
|
460 | (2) |
|
|
462 | (4) |
|
13.3 Commutative Hecke algebras |
|
|
466 | (3) |
|
13.4 Spherical functions: intrinsic theory |
|
|
469 | (5) |
|
13.5 Harmonic analysis on the Hecke algebra H(G, K, Χ) |
|
|
474 | (8) |
|
14 Representation theory of GL(2, Fq) |
|
|
482 | (61) |
|
14.1 Matrices associated with linear operators |
|
|
482 | (2) |
|
14.2 Canonical forms for m2(F) |
|
|
484 | (4) |
|
|
488 | (4) |
|
14.4 Representation theory of the Borel subgroup |
|
|
492 | (2) |
|
|
494 | (7) |
|
14.6 Cuspidal representations |
|
|
501 | (11) |
|
14.7 Whittaker models and Bessel functions |
|
|
512 | (10) |
|
|
522 | (5) |
|
14.9 Character theory of GL(2, Fq) |
|
|
527 | (6) |
|
14.10 Induced representations from GL(2, Fq) to GL(2, Fqm) |
|
|
533 | (7) |
|
14.11 Decomposition of tensor products |
|
|
540 | (3) |
Appendix Chebyshev polynomials |
|
543 | (12) |
Bibliography |
|
555 | (8) |
Index |
|
563 | |