On Sets of Large Fourier Transform Under Changes in Domain

Abstract

A function $f:{\mathbb{Z}}_n\to \mathbb{C}$ can be represented as a linear combination $f(x)={\sum }_{\alpha \in {\mathbb{Z}}_n}\hat{f}(\alpha ){\chi }_{\alpha ,n}(x)$ where $\hat{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 $\tilde{f}:{\mathbb{Z}}_m\to \mathbb{C}$, given by \[ \widetilde{f}(x) = \begin{cases} f(x) & \text{when } 0\leq x < \min(n, m), 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 $\hat{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{à}fols: \emph{single-bit} functions, defined over any domain, have a small set of large coefficients.

References in corpus (1)

• On sets of large exponential sums