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!



Choice of normalization of the finite Fourier transform
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).


