Heisenberg's inequality for the Fourier transform on finite fields Fix a prime power $q$, let $F$ be the finite field with $q$ elements, let $N \mid (q-1)$ and let $\zeta_N$ be a primitive $N$-th root of unity in $F$. The DFT on the $F$-vector space of functions $f : \mathbb{Z}/N\mathbb{Z} \to F$ is given by $\hat{f}(m) = \sum_{j \in \mathbb{Z}/N\mathbb{Z}} f(j) \zeta_N^{mj}$. 
Question: Is it true that $\#\text{supp}(f)\#\text{supp}(\hat{f}) \geq N$?
Note this inequality holds when $F$ is replaced with $\mathbb{C}$ (or even perhaps any ring containing $N$-th roots and a non-trivial norm?). It is sometimes called the Heisenberg uncertainty principle inequality for finite abelian groups (see for instance page 15 here: http://www.ms.uky.edu/~pkoester/research/finiteabeliananalysis.pdf). I wonder if this also holds when the codomain $\mathbb{C}$ is replaced with $F$? Note the proof in the case of $\mathbb{C}$ relies mainly on the norm for $\mathbb{C}$, being non-trivial and satisfying a triangle inequality. However as far as I know the only norm in $F$ is the trivial one. Perhaps one could work in $p$-adic fields instead, use the norm there, and translate a result for finite fields via the Teichmuller points? Thanks a lot.
 A: Let $G$ be a locally compact Abelian group. Denote the Pontryagin dual group of $G$ by $\widehat{G}$. Then the Fourier transform $\mathcal{F}$ on $G$ is the isometric isomorphism $\mathcal{F} : L^2 (G) \to L^2 (\widehat{G})$ given by
$$ \mathcal{F} f(\omega) = \int_{G} f(x) \overline{\omega(x)} d\mu_G (x) $$
whenever $f \in L^1 (G) \cap L^2 (G)$. For a function $f \in L^2 (G)$ and its Fourier transform $\hat{f} := \mathcal{F} f$, the Weyl-Heisenberg inequality is given by
$$ \mu_G (\text{supp} \;f) \mu(\text{supp}\;\hat{f}) \geq 1. $$
The proof is rather straightforward and uses essentially the same arguments as the one in the paper you referred to.
Consider now the special case $G = \mathbb{Z} / N \mathbb{Z}$. Then the Pontryagin dual of $G$ is $\widehat{G} = \mathbb{Z} / N \mathbb{Z}$, that is, $\mathbb{Z} / N \mathbb{Z}$ is self-dual. Furthermore, there is the identification $L^2 (\mathbb{Z} / N \mathbb{Z}) \cong \mathbb{C}^N$, which yields the inequality
$$ \#(\text{supp} \;f) \#(\text{supp} \;\hat{f}) \geq N$$
for Haar measures given by $\mu_G = \frac{1}{\sqrt{N}} \#$ and $\mu_{\widehat{G}} = \frac{1}{\sqrt{N}} \#$, where $\#$ denotes the counting measure.
Regarding the finite field, whenever you take a prime $p \in \mathbb{N}$, then there is the identification $\mathbb{F}_p \cong \mathbb{Z} / p \mathbb{Z}$, where $\mathbb{F}_p$ denotes the Galois field of order $p$. Therefore, the Fourier transform at $x \in \mathbb{F}_p$ is the map $\hat{f}_x : \mathbb{F}_p \to \mathbb{C}$, and hence is a functional on a finite field, but it is not necessarily $\mathbb{F}_p$-valued. 
As you notice, all of the above is based on the $L^2$ space, which is a $\mathbb{C}$-valued linear space. To my knowledge, most properties of $L^p$ spaces do not extend to other fields than $\mathbb{R}$ or $\mathbb{C}$, so I am not sure if it is possible to derive similar inequalities for $\mathbb{F}_p$-valued linear spaces. At least it is not possible to do this in the "classical" way.
Another point is the characters $\omega \in \widehat{G}$, which are, by definition, homomorphisms from $G$ into $\mathbb{T} \subset \mathbb{C}$, which are thus not necessarily $\mathbb{F}_p$-valued either. I am not entirely sure how this relates to your "characters" $\zeta_N$ though.
