An uncertainty principle for cyclic groups of prime order (Q1774282): Difference between revisions

If \(G\) is a finite abelian group with Haar measure \(| \cdot| \), and \(f:G\to \mathbb{C}\) is not identically zero then \[ | {\text{supp}}(f)| | {\text{supp}}(\hat f)| \geq | G| \leqno{\text{(G)}} \] where \(\hat{f}\) is the discrete Fourier transform of \(f\). If \(G=\mathbb{Z}_N\) where \(N\) is composite, the sharpness of this inequality is seen by taking \(f\) to be the characteristic function of a proper, nontrivial subgroup. In general, its arithmetic analog \[ | {\text{supp}}(f)| +| {\text{supp}}(\hat f)| \geq 2\sqrt{| G| } \] is not sharp. However, when \(N=P\) is prime the author proves the sharp result \[ | {\text{supp}}(f)| +| {\text{supp}}(\hat f)| \geq | P| +1.\leqno{\text{(P)}} \] Inequality (P) does not follow simply from Cauchy-Schwarz as (G) does. Rather, it uses the fact that if \(P\) is prime then all of the minors of the discrete Fourier matrix are nonzero. The author mentions several proofs of this fact in the literature, and provides a new ``analytic'' proof. It is also shown that the Cauchy-Davenport inequality \[ | A+B| \geq \min\,(| A| +B| -1,P) \] for subsets \(A\) and \(B\) of \(\mathbb{Z}_P\) follows in a simple way from (P).