The discrete Fourier transform of distributions

Abstract

This article (being the first chapter of the book Music Through Fourier Space published by Springer International Publishing Switzerland in 2016 and reprinted here in the Journal of Mathematics and Music with the kind permission of Springer International Publishing Switzerland) gives the basic definitions and tools for the discrete Fourier transform (DFT) of subsets of a cyclic group, which can model for instance pitch-class sets or periodic rhythms. I introduce the ambient space of distributions, where pc-sets (or periodic rhythms) are the elements whose values are only zeros and ones, and several important operations, most notably convolution, which leads to “multiplication d'accords” (transpositional combination), algebraic combinations of chords/scales, tiling, intervallic functions, and many musical concepts. Everything is defined and the article is hopefully self-contained, except perhaps for the section on circulant matrices, which uses some notions from linear algebra: eigenvalues of matrices and diagonalisation. Indeed, it is hoped that the material in this article will be used for pedagogical purposes, as a motivation for studying complex numbers and exponentials, modular arithmetic, algebraic structures, and so forth. The proof of an important theorem demonstrates that the DFT is the only transform that simplifies the convolution product into the ordinary, termwise product.

Keywords:

• discrete Fourier transform
• music theory
• Fourier coefficients
• polynomials
• matrices

2010 Mathematics Subject Classification:

• 00A65
• 13A99
• 42A16
• 42A85

Acknowledgments

For the idea and opportunity of reprinting this article in the Journal of Mathematics and Music, I am very grateful to Thomas Fiore, Co-Editor-in-Chief of the journal, and to Ronan Nugent from Springer Nature, who gave permission.

For the book (Amiot 2016) I am indebted first and foremost to Ian Quinn, who revived interest in DFT and invented the saliency quality.

I owe much to Jason Yust, who made tremendous progress in the field over the last two years and generously gave me permission to cite all of his results and analyses, even those not yet published.

Jack Douthett is also father to a prolific notion, the maximally even sets, which are a foundation to many further developments, including the book containing this article. His support and encouragement were always a great help in my research.

I am grateful to Moreno Andreatta and Guerino Mazzola, editors of the CMS series, who incited me to write this book and provided pointed and vital advice.

In addition to several memorable research collaborators and co-authors, including Carlos Agon, Moreno Andreatta, Daniel Ghisi, John Mandereau, and Thomas Noll, I would like to single out for the present opus William Sethares, since our joint work on matricial shortcuts through music-theoretical notions provided some major insights on the usefulness of DFT.

Cliff Callender allowed me to borrow from the well-chosen examples of his paper on Fourier; his openness and helpfulness are as usual greatly appreciated.

I thank Co-Editor-in-Chief Thomas Fiore for his eagle-eye corrections to the galley proof, and occasional clarifications in the text.

Notes

1 This article has been slightly copy-edited to conform to journal style.

2 https://www.springer.com/series/8349

3 Loudness of a pitch, say, or “velocity” in MIDI format, or probabilities of occurrence in a score, to name a few possible meanings.

4 This is known in the USA as “transpositional combination,” see Cohn (1991).

5 For a very pedagogical explanation of the Fourier transform by and for music theorists, see Callender (2007). This article aims at a higher mathematical level and is of necessity more terse in the basic definitions.

6 Though this article focuses on the discrete Fourier transform, some attention is devoted in Amiot (2016, Chapter 5) to continuous versions that have appeared in the context of music theory. The continuous/integral Fourier transform (and Fourier series expansions) is of course well known in the theory of sound, but our topic is altogether different.

7 This is easily understood as computing the DFT of the map induced by f by its restriction to $\mathbb{Z}/\frac{n}{p}\mathbb{Z}$. This again follows from Lemma 1.6, see the exercises at the end of this article.

8 Modern harmonic analysis (in mathematics) uses many different orthogonal bases for decomposition of a signal, for instance wavelets; exponentials are only the seminal case. In calculus, the exponentials are privileged in being the eigenvectors of the differential operator, i.e. the simplest maps under differentiation.

9 $({\mathbb{C}}^n,\times )$ is not a group because many elements are not invertible. See Amiot (2016, Chapter 3).

10 Generated in ${\mathbb{Z}}_n$ by n/p. Proof in exercises.

11 This is a vector, listing the magnitudes of all coefficients.

12 T/I is made of translations (“transpositions” for musicians) $x\mapsto x+\tau$ and central symmetries (“inversions”) $x\mapsto c-x$.

13 Quantitative correlations could be computed, of course, with any reasonable estimator.

14 The DFT of a real-valued function is non-real in general, it only satisfies $\hat{f}(-t)=\overline{\hat{f}\left(t\right)}$.

15 This traditional position is not tenable; another argument against it is that some classes of “Z-related” chords are indeed exchanged through action of a larger group than T/I, like the two famous all-intervals $\{0,1,4,6\}$ and $\{0,1,3,6\}$ in ${\mathbb{Z}}_{12}$ (Figure 8.13 in Amiot [2016]), which are affine-related – and this can be generalised, since any affine transform of an all-interval set will be Z-related. Jon Wild pointed out to us that the reverse is false, and John Mandereau proved that the classes of homometric subsets are not orbits of any (point-wise) group action (Amiot 2016, Chapter 2, Theorem 2.25), see Agon and Andreatta (2009) and (Amiot 2016, Chapter 2).

16 An algebra is a vector space, with an internal multiplication. Common examples of algebras are square matrices and polynomials. In this section we put forth several algebra isomorphisms, i.e. maps between algebras that preserve all three operations: addition, multiplication by numbers, and internal multiplication.

17 Meaning that any operation in one structure is echoed by a similar operation in the other structure. The advantage is that matrix multiplication for diagonal matrices is trivial, though it is not for ordinary matrices, nor is the convolution product of distributions. This is another expression of the simplification of convolution product to termwise multiplication, cf. Theorem 1.10.

18 Because the algebra of circulant matrices is stable under “×” and also under transposition of matrices, since its generating element J satisfies $J^{\mathrm{T}}=J^{-1}=J^{n-1}$.

19 We have thus retrieved the left hand (D♭E♭G♭) of Le vent dans la plaine from its interaction with the right hand. Notice that the computation of the first column of the matrix is enough. The bulk of the effort consists in inverting matrix $\mathcal{A}$, which can be done using techniques specific to ${\mathcal{C}}_n\left(k\right)$, though many pocket calculators have no trouble inverting $12\times 12$ matrices.

20 See however the section on algorithms in Chapter 3 of Amiot (2016), retrieving B even when one Fourier coefficient of A is nil.

21 I feel certain that some readers will prefer the shortcut of a short exact sequence $(X^n-1)\hookrightarrow \mathbb{C}\left[X\right]\to \mathbb{C}\left[J\right].$

22 Meaning that $X^n$ can be replaced by 1, and hence $X^{n+1}$ is replaced by X, $X^{5n+3}$ by $X^3$, etc.

23 The exponents are defined modulo n since the polynomials are taken modulo $X^n-1$.

24 Here $\mathbf{S}\left(X\right)$ is actually equal to one lone cyclotomic polynomial, ${\mathrm{\Phi }}_{49}\left(X\right)$.