An uncertainty principle for cyclic groups of prime order

By Terence Tao. 2003

253 citations recorded by the source corpus.

Let $G$ be a finite abelian group, and let $f: G \to \C$ be a complex function on $G$. The uncertainty principle asserts that the support $\supp(f) := \{x \in G: f(x) \neq 0\}$ is related to the support of the Fourier transform $\hat f: G \to \C$ by the formula $$ |\supp(f)| |\supp(\hat f)| \geq |G|$$ where $|X|$ denotes the cardinality of $X$. In this note we show that when $G$ is the cyclic group $\Z/p\Z$ of prime order $p$, then we may improve this to $$ |\supp(f)| + |\supp(\hat f)| \geq p+1$$ and show that this is absolutely sharp. As one consequence, we see that a sparse polynomial in $\Z/p\Z$ consisting of $k+1$ monomials can have at most $k$ zeroes. Another consequence is a short proof of the well-known Cauchy-Davenport inequality.

Subfields: Applied Mathematics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/9825949e5e1baeed93aac18aa4e0dc81498de93c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Discrete Mathematics and Combinatorics

Citations in the corpus

The Faber–Krahn inequality for the short-time Fourier transform (2021, background): “For interesting applications to signal recovery we refer to [5, 44, 45, 49] and the references therein.”
Blind Multiband Signal Reconstruction: Compressed Sensing for Analog Signals (2007, background): “Several specific constructions of sampling patterns are proved to be universal [11], [26].”
Hardy and uncertainty inequalities on stratified Lie groups (2013, background): “More recent work on the general topic of uncertainty principles on groups and manifolds includes [10, 37, 38].”
Discrete Fourier analysis (2013, unknown): “Below we see one of the oldest theorems in the subject known as the Cauchy (1813)- Davenport (1935) Theorem reproved recently using uncertainty [7].”
Open problems in additive combinatorics (2007, unknown): “…F p -version of the problem is considerably more diﬃcult, and all presently known proofs of the Cauchy-Davenport theorem incorporate a non-trivial idea, such as the transform method (sometimes called the “intersection-union trick”), the polynomial method (as in [1]), or Fourier analysis (see [96]).”