Fourier Analysis on abelian groups; theory and applications by Tommy Odland Master of Science Thesis in Applied and Computational Mathematics Department of Mathematics University of Bergen November 2017 i ii Abstract Fourier analysis expresses a function as a weighted sum of complex exponen- tials. The Fourier machinery can be applied when a function is defined on a locally compact abelian group (LCA). The groups R, T = R/Z, Z and Zn are all LCAs of great interest, but numerical computations are almost always done on the finite group Zn using the Fast Fourier Transform. To reduce a general problem to a numerical computation, sampling and pe- riodization is necessary. In this thesis we present a new software library which facilitates Fourier analysis on elementary LCAs. The software al- lows the user to work directly with abstract mathematical objects, perform numerical computations and handle the relationship between discrete and continuous domains in a natural way. Thespecificcombinationofmathematicalobjectsandoperationsavailablein thesoftwaredevelopedistoourknowledgenotfoundelsewhere. Effortshave been made to efficiently open-source, document and distribute the software library, which is now available to every user of the Python programming language. Acknowledgements First and foremost I would like to thank my advisor, professor Hans Z. Munthe-Kaas, for suggesting this interesting project and for all of his help following it through. The versatility of this project has made it delightful to work with: there are undoubtedly abstract components to Fourier analysis and group theory, but at the same time it’s an applicable and concrete field of mathematics. Building a relatively large software library has been an exciting learning experience. I would also like to thank Amir M. Hashemi, Erlend R. V˚agset, Gunvor Lemvik and Simen Midtbø for reading through a draft of the thesis and providing comments. iii Contents Contents 1 Introduction 2 1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Chapter overview . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Preview 6 2.1 Sampling on a lattice . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Fourier series approximation . . . . . . . . . . . . . . . . . . . 8 2.3 Hexagonal sampling and periodization . . . . . . . . . . . . . 9 3 Preliminaries 12 3.1 Properties of integers and set functions . . . . . . . . . . . . . 12 3.2 Group theory . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.3 Category theory . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.4 Fourier analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4 Integer linear algebra 28 4.1 Unimodular matrices . . . . . . . . . . . . . . . . . . . . . . . 28 4.2 The Hermite normal form . . . . . . . . . . . . . . . . . . . . 30 4.3 The Smith normal form . . . . . . . . . . . . . . . . . . . . . 31 4.4 Algorithms and computational issues . . . . . . . . . . . . . . 32 5 Computing factorizations in FinAb 37 5.1 Factorizations in abelian categories . . . . . . . . . . . . . . . 37 5.2 Factorizations in VectR . . . . . . . . . . . . . . . . . . . . . . 40 5.3 Factoring free-to-free morphisms in FinAb . . . . . . . . . . . 42 5.4 Solving equations in FinAb . . . . . . . . . . . . . . . . . . . . 44 5.5 Factoring left-free morphisms in FinAb . . . . . . . . . . . . . 46 5.6 Morphisms in Ab . . . . . . . . . . . . . . . . . . . . . . . . . 53 6 Fourier analysis on locally compact abelian groups 55 6.1 Locally compact abelian groups . . . . . . . . . . . . . . . . . 55 6.2 Characters and the dual group . . . . . . . . . . . . . . . . . 56 6.3 The invariant integral . . . . . . . . . . . . . . . . . . . . . . 57 Contents iv 6.4 The Fourier transform . . . . . . . . . . . . . . . . . . . . . . 58 6.5 Pullbacks and pushforwards on groups . . . . . . . . . . . . . 59 6.6 Computing pushforwards . . . . . . . . . . . . . . . . . . . . 61 6.7 Dual homomorphisms . . . . . . . . . . . . . . . . . . . . . . 62 6.8 Sampling and periodization . . . . . . . . . . . . . . . . . . . 65 6.9 Hexagonal Fourier analysis in R2 . . . . . . . . . . . . . . . . 69 7 The abelian software library 74 7.1 Scientific programming and Python . . . . . . . . . . . . . . . 74 7.2 Principles of software development . . . . . . . . . . . . . . . 75 7.3 Introducing abelian . . . . . . . . . . . . . . . . . . . . . . . 76 7.4 Example 1: Factoring a homomorphism . . . . . . . . . . . . 79 7.5 Example 2: Fourier series approximation . . . . . . . . . . . . 80 7.6 Example 3: Hexagonal Fourier analysis . . . . . . . . . . . . . 81 8 Conclusion and further work 84 8.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 8.2 Further work . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 Appendices 90 A Source code 91 B Software documentation 99 1 Contents Notation Groups Binary operators • • Z : Additive integers (, ) : Dual pairing · · Zn : Additive integers mod n : Convolution ∗ R : Additive reals : Direct sum ⊕ T =R/Z : Additive reals mod 1 Relations • T : Complex numbers z with z =1 = : Isomorphic | | ∼ GL(n,Z) : Invertible matrices over Z Arrows • Categories φ • H G : epimorphism Set : Category of sets φ H G : monomorphism VectR : Vector spaces over R ModZ : Modules over Z • Other FinAb : FGAs : Big O notation O Ab : Abelian groups φ⊥ : Annihilator of φ Objects G : Dual group of G • G,H : Abelian groups (f),f : Fourier transform of f F(cid:98) U,V : Unimodular matrices hom(, ) : Set of homomorphisms · ·(cid:98) I : Identity matrix of size n BA : Functions f :A B n → Abbreviations DFT - Discrete Fourier Transform FFT - Fast Fourier Transform FGA - Finitely Generated Abelian group LCA - Locally Compact Abelian group HNF - Hermite Normal Form SNF - Smith Normal Form Chapter 1. Introduction 2 Chapter 1 Introduction 1.1 Introduction Fourier analysis expresses a function as a weighted sum of trigonometric functions, or equivalently complex exponentials. Fourier synthesis recovers the original function from the frequency representation. These ideas are remarkably powerful, and are widely used in applied and theoretical science. The general setting for Fourier analysis are the locally compact abelian groups (LCAs). The four common Fourier transforms are defined for func- tions on R, T = R/Z, Z and Zn, and these groups are called elementary LCAs. The goal of this master project is to create software which allows for general computations and Fourier analysis on the group G, which is an elementary LCA. To do this, the software must handle periodization, dis- cretization and interpretation of functions f : G C. Ideas for such a → software package were sketched in [Munthe-Kaas, 2016]. The majority of the thesis is devoted to the theory required to understand the general framework we will work in. We will make use of group theory, linear algebra, category theory and abstract Fourier analysis. To unify the reading experience, the thesis includes theoretical preliminaries and some historicalremarks. Afterintroducingthemathematicsneededtounderstand theobjects,operationsandalgorithmsinthesoftware,theabelianlibraryis introducedinChapter7. Ageneralintroductionisgivenalongwithexample code, and further details about the software is found in the appendices. Some of the underlying algorithms used in the software are known, see for instance [Charles C. Sims, 1994] for algorithms which compute the Hermite and Smith normal forms. Several algorithms are the result of my own work: Algorithm3inSection5.4forthesolutionofaparticularequationismyown, andsoisAlgorithm5inSection6.5usedtogenerategroupelementsordered 3 1.2. Chapter overview by norm. The theorems presented in Section 5.5 for the computation of the kernel, cokernel, image and coimage were developed in discussions with my advisor Hans Z. Munthe-Kaas. The abelian software library is the main contribution of this project. It’s open sourced, well-documented, has a modern test-suite and is distributed on the official Python package index. As far as I am aware, no similar soft- ware package exists. The combination of objects and operations is unique, and implementations of the underlying algorithms are relatively rare. For instance, MATLAB currently implements a Smith normal form algorithm onlyforsquarematrices,whileageneralimplementationisfoundinabelian. Among the popular scientific Python libraries, no implementations were found. Now, Python users will have access to this algorithm and many others, as well as objects and methods for Fourier analysis and general com- putations on elementary LCAs. 1.1.1 Software used in this project This document was typeset using LATEX2ε. The plots were produced using the matplotlib library for Python, and the remaining figures were created using the extensible drawing editor ipe. The abelian library was written in Python 3.6. The following web services were used for software distribution. Source code: github.com/tommyod/abelian/ • Documentation: abelian.readthedocs.io/ • Python package index: pypi.org/project/abelian/ • 1.2 Chapter overview Chapter 1 – Introduction The introduction provides an overview of the thesis. It gives a brief introduction to Fourier analysis, states the goal of the project and details what is new. A brief comparison is made with existing software. This chapter overview is a quick account of the content and purpose of each chapter. Chapter 2 – Preview To entice the reader, the preview chapter shows some example usage of the abelian software library. Three examples are presented in increasing order of complexity. Real Python code snippets are included, along with figures explaining the problems. Chapter 1. Introduction 4 Chapter 3 – Preliminaries The purpose of this chapter is to serve as a reference for the later chapters. It has been divided into four parts: integers and set functions, group theory, category theory and Fourier analysis. Each section briefly summarizes some material which the reader ideally has some existing knowledge of, while also establishing the notation. Depending on the background of the reader, this chapter may be skimmed or perhaps skipped altogether. Chapter 4 – Integer linear algebra Tostudyfinitelygeneratedabelian groups (FGAs), we will require knowledge of the the Hermite normal form (HNF) and the Smith normal form (SNF), which are introduced as factor- izations of a linear map A : Zn Zm. Unimodular matrices are defined, → andalgorithmsforcomputingtheHNFandSNFarepresented. Whilethese algorithms are discussed in the literature, implementations are rare. Chapter 5 – Computing factorizations in FinAb In an abelian cate- gory, a morphism has a kernel, cokernel, image and coimage. The goal of this chapter is to develop algorithms for computing these four important morphisms in FinAb, the category of FGAs. Working our way up to this goal, we consider how to compute the morphisms in several categories. We start with the relatively well known case of the category of vector spaces over R, denoted VectR, and work towards the goal of developing algorithms for the category FinAb. Chapter 6 – Fourier analysis on locally compact abelian groups We examine Fourier analysis from the perspective of LCAs. From this view Fourier series, the Fourier transform and the discrete Fourier transform are the same thing. Dual groups, the dual pairing and dual homomorphisms are introduced. Pullbacks and pushforwards are discussed both in theory and practical computations. An algorithm for practical computations of push- forwards is developed. Finally we discuss computational Fourier analysis on Td as well as Rd, and study Fourier analysis on a hexagonal lattice in detail. We briefly compare our approach to methods used in several recent research papers on Fourier analysis on lattices. Chapter. 7 – The abelian software library This chapter introduces abelian, a software library for computations on elementary LCAs. We start by briefly discussing the state of open-source scientific software and the Python programming language. We mention some good practices for developing a modern software library, and finally introduce abelian. The abelian software library is then used to compute several concrete examples. 5 1.2. Chapter overview A selection of the most important algorithms from the source code is found in Appendix A. An excerpt of the full software documentation is found in Appendix B. Chapter 8 – Conclusions and further work The work is concluded and some suggestions for further work are presented. Appendices There are two appendices: Appendix A contains some of the source code for abelian. Only the most important algorithms are included. Appendix B contains parts of the full documentation. The general introduc- tionandtutorialsareincluded,whiledetaileddocumentationofthemethods with examples are omitted due to space considerations.