Discrete Fourier Analysis

The finite circle

Defintion of Fourier series. The Hilbert space generated by an orthonormal basis induced by: trigonometric functions, complex exponential functions. Examples of computation of FFT by Octave. The finite circle Zn. Complex exponential functions and the finite circle. Linear congruences.

The finite torus

The chinese remainder theorem. Corollary. Isomorphism between Zn and a direct sum of rings. An application of CRT to RSA. Cartesian product of graphs and the finite torus. Cayley graphs.

Multiplicative groups and complex valued functions on Zn

Euler's function. Properties. Multiplicative group (Zn)*. (Zn)* is cyclic for n in {2, 4, p^m, 2p^m, with p odd prime}. Theorem. (Zp)* is cyclic if p is prime.

Discrete Fourier Transform on Zn

Complex valued functions on Zn. The finite dimensional C-vector space L^2(Zn). Delta functions. The convolution operator. The group of characters. Definition of discrete Fourier transform. Examples. Properties of DFT on Zn. Orthogonality relation of the characters of Zn. DFT is a 1-1 linear map on L^2(Zn) to L^2(Zn). DFT and convolution. Translation and dilatation property of DFT. DFT on even and odd functions. Examples. Inversion formula. Plancherel theorem.

Circulant graphs and the adjacency operator

Graph notation. Graph isomorphism. Cayley graph on Z_n: The circulant graphs. Shell S(r) and isomorphisms. Regularity of Cayley graphs. The adjacency operator A and its eigenvalues. The number of walks of length l joining v_i and v_j is the (i,j)-entry of A^l. A connected graph with diameter d has at least d+1 distinct eigenvalues. The diameter is the smallest d s.t. all entries in (I+A)^d are non zero.

Spectrum of a k-regular graph

In a Cayley graph the adjacency operator is a convolution operator. Regular graphs.  If a graph is k-regular: 1) The degree k is an eigenvalue of A; 2) The multiplicity of k is the number of connected components of the graph; 3) A graph is bipartite iff -k is an eigenvalue of A. Spectrum of the circulant graph. Examples: The spectra of complete graphs and cycles.

The edge expander costant

Hypercube. The edge expander costant. Examples: Complete graphs and cycles. Examples.

Four questions about Cayley graphs

Questions. Let X be a Cayley graph. Check if X is Ramanujan. Invertibility of the adjacency operator of X. Computation of diameter and girth of X. Cayley graphs on balls. Fan Chung bound for the diameter.

Finite fields and Winni Li's graphs

Basic facts about finite fields. The splitting field of x^4-x over F_2. A primitive element of F_9 and Feedback shift register. Field automorphism. Trace and norm. Definition of Winni Li's graphs by the kernel of the norm.

Questions about Winni Li's graphs

The kernel of the norm is: 1) a symmetric set of generators of the Cayley graph; 2) cyclic. They are Ramanujan. The diameter of Winnie Li graphs is <=5. The girth is 3 or 4.

Random walks on Cayley graphs

Random number generators. Definition of random walks on Zn. Definition of Markov transition matrix. Random Walks convergence to uniform distribution. Comparison between norms on R^n.Random Walks convergence to uniform distribution (II). Joint distribution on Zn. Probabilistic meaning of convolution. Upper Bound Lemma with respect to probability density, uniform distribution and DFT of the probability density.

Finite abelian groups and inversion of Lagrange theorem

Unique representation of finite abelian groups: Primary decomposition and invariant factor decomposition. Inversion of Lagrange theorem for abelian groups. Lemma. Sets of generators of finite abelian groups with the same cardinality. Examples. Fundamental theorem of finite abelian groups. Remark on the cardinality of minimal sets of generators of the group. Isomorphism between the group and its dual.

Discrete Fourier Transform on finite abelian group G

The orthogonality relations of the characters of G. DFT on a finite abelian group G. Main properties. An example. DFT over two-dimensional function.

Hadamard transform and Hamming graphs on codes

Definition. DFT on (F_2)^n. The Hadamard transform. Cayley graph defined on (F_2)^n. Hamming graph and Hamming distance. Distance comparison. Eigenvalues of the adjacency operator of the hypercubes of dimension n through discrete Fourier transform. Definition. Cayley graph X(F_2^n, S(r)). Connection with code theory. Eigenvalues of the adjacency operator of the graph defined by DFT. Description of the eigenvalues by Krawtchouk polynomials.

Perfect codes, Cyclic codes and their dual groups

Sphere packing Hamming bound. Perfect codes. Hamming codes. Examples of hypercube partitions by Hamming balls. Cyclic codes. Linear cyclic codes. Algebraic properties. Dual codes of cyclic codes are cyclic. Weight distribution. The dual group of the code.

Poisson summation formula on a finite abelian group

Dual group of ((F_2)^n/C) is the dual code of C. Poisson summation formula on a finite abelian group.

MacWilliams theorem

Corollary of Poisson Summation formula. Observation. Application to binary linear Codes. MacWilliams Theorem. Examples. Relations between weights of the code and weights of its dual code through Krawtchouk polynomials.

Strongly regular graphs and boolean functions

Theorem. Strongly regular graphs and the 3 distinct eigenvalues of the adjacency operator. Examples. Boolean function and their Cayley graphs G_f. G_f with 1 and 2 eigenvalues.

Characterization of bent functions by the spectrum of Cayley graphs

Definition of Bent function by DFT. Theorem. Bent function and strongly regular graphs G_f. Eigenvalues and multiplicities of G_f. Examples.

Material

 

Bibliography

Audrey Terras, Fourier Analysis on Finite Groups and Applications, 1999, London Mathematical Society Student Texts.

A. Bernasconi and B. Codenotti. “Spectral analysis of Boolean functions as a graph eigenvalue problem”. In: IEEE Transactions on Computers 48.3 (Mar. 1999), pp. 345–351.