# Choice of normalization of the finite Fourier transform

Let $f : \mathbb{Z}/N\mathbb{Z} \rightarrow \mathbb{C}$ be a function. Is its Fourier transform typically defined by

$$\widehat{f}(\xi) = \sum_{x \in \mathbb{Z}/N \mathbb{Z}} f(x) e^{- 2 \pi i x \xi /N},$$

or the same expression with $\frac{1}{N}$ in front?

I recently encountered both in material on additive combinatorics. This is just a choice of normalization; if the factor of $1/N$ is not included, then it appears in the Fourier inversion formula instead.

Is one of these substantially more common than the other (perhaps just in additive combinatorics), or does the choice of normalization tell me something implicit about the author's approach? (The source including $1/N$ in front is using the language of probability theory; perhaps this has something to do with it.)

Thank you!

-
The 1/N factor appears to be better suited to taking the limit as N goes to infinity, so I would guess it is more sensible for that kind of application. (In other words it naturally occurs if you give Z/NZ total measure 1 instead of the counting measure.) – Qiaochu Yuan Feb 17 '11 at 21:35
You could always (multiplicatively) split the difference and use $1/\sqrt{N}$. Then Fourier inversion looks nicer. Also, the $f$ is missing in the right side of your definition. – Ramsey Feb 17 '11 at 21:48
Ramsey -- thank you, fixed the mistake. – Frank Thorne Feb 17 '11 at 22:10
I can't imagine either is overwhelmingly preferred to the other. Just make it clear what your definition is when you use it. – KConrad Feb 17 '11 at 22:55
@Qiaochu: Very helpful, thank you! (Indeed, that is pretty close to a 3-line summary of Terry Tao's answer below). @KConrad: I certainly see your point, but I see that my "something implicit" is a choice of measure on $\mathbb{Z}/N\mathbb{Z}$, and my unhappiness has completely gone away. – Frank Thorne Feb 17 '11 at 23:50

The "right" category in which to define the Fourier transform in general is that of a locally compact abelian (LCA) group $G$, equipped with a Haar measure $\mu_G$. Once one fixes the Haar measure $\mu_G$, there is a natural dual measure $\mu_{\hat G}$ on the Pontryagin dual group $\hat G$, such that all the usual Fourier identities hold with these two measures (and no further need of normalisation).

For many standard LCA groups (e.g. ${\bf R}^n$, ${\bf Z}^n$, $({\bf R}/{\bf Z})^n$) there is a natural choice of Haar measure, namely Lebesgue measure or counting measure, and so there is a fairly universal choice of convention for the Fourier transform (although there are sometimes some minor advantages to moving the $2\pi$ factor around a bit, or replacing $i$ with $-i$). A bit more generally, with discrete abelian groups one always has counting measure as a canonical choice, and for compact abelian groups one always has normalised Haar measure (in which the total mass is one) as a canonical choice.

However, finite groups such as ${\bf Z}/N{\bf Z}$ are both discrete and compact, and so there are two canonical choices of Haar measure available, namely counting measure and normalised counting measure. Such groups are isomorphic to their Pontryagin dual (though not always canonically); but the nature of Fourier duality is such that if one gives the group counting measure, its dual group will naturally come equipped with normalised measure, and conversely. So one has to pick whether it is the group or the dual group that is going to "look discrete" or "look compact", and the other group will then take the opposite normalisation.

In additive combinatorics, one is often working with dense subsets of the ambient group ${\bf Z}/N{\bf Z}$, which makes the "compact" normalisation (dividing counting measure by N) natural for the spatial variable $x$. As a consequence, the frequency variable $\xi$ (which lives in the dual group $\widehat{{\bf Z}/N{\bf Z}} \equiv {\bf Z}/N{\bf Z}$) is most naturally given the "discrete" normalisation. But this is ultimately just a convention, and one can certainly imagine other applications in which the other normalisation is desirable.

The compromise normalisation (dividing counting measure by $\sqrt{N}$ on both sides) is occasionally convenient when one is working primarily at the $L^2$ level (or with half-densities rather than with functions or measures), and in situations in which one really wants to treat the spatial variable $x$ and frequency variable $\xi$ on the same footing, for instance if one is trying to perform time-frequency analysis in the phase plane

$$\{ (x,\xi): x,\xi \in {\bf Z}/N{\bf Z}\}.$$

However, this type of analysis is not particularly common in the context of finite abelian groups (EDIT: with the notable exception of quantum computation, see comments).

-
NB. The compromise choice enforces unitarity (which you of course alluded to by mentioning $L^2$) and for that reason is ubiquitous in quantum computation. – Steve Huntsman Feb 17 '11 at 23:15
This is extremely helpful. Thank you very much! – Frank Thorne Feb 17 '11 at 23:38
I have been fascinated for decades by the fact that whatever choice of the Fourier transform you make, you encounter $\pi$ somewhere. It is unavoidable. This reminds me a joke where a PhD student is mocked by a friend of him because his thesis (on probability, say) involves $\pi$ at every page, and ''of course, probability has nothing to do with the ratio between the perimeter of the circle and its diameter''. – Denis Serre Feb 18 '11 at 7:10
@Steve: one always has unitarity from $L^2(G,\mu_G)$ to $L^2(\hat G,\mu_{\hat G})$. But, yes, you have a point, quantum computation is certainly one place where one wants to place the spatial and frequency variables on the same footing. @Denis: It's not helpful, but one can eliminate all the special constants ($e$, $2$, $\pi$, $i$) from the Fourier transform by using the obfuscated conventions $\hat f(\xi) = \int 1^{-x \cdot \xi} f(x)\ dx$ and $f(x) = \int 1^{x \cdot \xi} \hat f(\xi)\ d\xi$. (In particular, one has the amusingly compact $\hat 1_E(\xi) = \int 1_E^{x \cdot \xi}(x)\ dx$.) – Terry Tao Feb 18 '11 at 11:53
@TT. Nice, but you cheat a little bit, hidding God's existence (dixit Euler), I mean $e^{i\pi}=-1$. – Denis Serre Feb 18 '11 at 12:56

Wolfram's website

http://reference.wolfram.com/mathematica/tutorial/FourierTransforms.html

discusses the different conventions in different disciplines (data analysis, signal processing,...) and how to set them in Mathematica.

-