On Sets of Large Fourier Transform Under Changes in Domain

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}$isthe(discrete)Fouriertransformof$f$\mathrm{.}Clearly,thebasis${\chi_{\alpha,n}(x):=\exp(2\pi i \alpha x/n)}$dependsonthevalue$n$. We show that if $f$ has “large” Fourier coefficients, then the function $\tilde{f}:{\mathbb{Z}}_m\to \mathbb{C}$, given by $$\tilde{f}(x)=\{\begin{array}{lll}f(x)& \text{when }0\le x<\min (n,m),0& \text{otherwise},\end{array}$$ 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.