The shift bound for abelian codes and generalizations of the Donoho-Stark uncertainty principle

Abstract

Let $G$ be a finite abelian group. If $f: G\rightarrow \bC$ is a nonzero function with Fourier transform $\hf$, the Donoho-Stark uncertainty principle states that $|\supp(f)||\supp(\hf)|\geq |G|$. The purpose of this paper is twofold. First, we present the shift bound for abelian codes with a streamlined proof. Second, we use the shifting technique to prove a generalization and a sharpening of the Donoho-Stark uncertainty principle. In particular, the sharpened uncertainty principle states, with notation above, that $|\supp(f)||\supp(\hf)|\geq |G|+|\supp(f)|-|H(\supp(f))|$, where $H(\supp(f))$ is the stabilizer of $\supp(f)$ in $G$.

14 pages, submitted