On Sets of Large Fourier Transform Under Changes in Domain

Joel Laity, Barak Shani

Published 2016-10-14Version 1

A function $f:\mathbb{Z}_n \to \mathbb{C}$ can be represented as a linear combination $f(x)=\sum_{\alpha \in \mathbb{Z}_n}\widehat{f}(\alpha) \chi_{\alpha,n}(x)$ where $\widehat{f}$ is the (discrete) Fourier transform of $f$. Clearly, the basis $\{\chi_{\alpha,n}(x):=\exp(2\pi i \alpha x/n)\}$ depends on the value $n$. We show that if $f$ has "large" Fourier coefficients, then the function $\widetilde{f}:\mathbb{Z}_m \to \mathbb{C}$, given by \[ \widetilde{f}(x) = \begin{cases} f(x) & \text{when } 0\leq x < \min(n, m), \newline 0 & \text{otherwise}, \end{cases} \] also has "large" coefficients. Moreover, they are all contained in a "small" interval around $\lfloor \frac{m}{n}\alpha \rceil$ for each $\alpha \in \mathbb{Z}_n$ such that $\widehat{f}(\alpha)$ is large. One can use this result to recover the large Fourier coefficients of a function $f$ by redefining it on a convenient domain. One can also use this result to reprove a result by Morillo and R{\`a}fols: \emph{single-bit} functions, defined over any domain, have a small set of large coefficients.