An uncertainty principle for cyclic groups of prime order

2003/08/29 by Terence Tao, Tao, Terence · 3 citations
Mathematics · #Algebraic and Geometric Analysis #Mathematical Analysis and Transform Methods #Mathematical and Theoretical Analysis #math.CA #math.NT #msc:42A99

paper · pdf · doi:10.48550/arxiv.math/0308286

7 pages, no figures, submitted, Math Research Letters. More references added

arxiv created 2004/07/22 · arxiv updated 2009/12/01

Abstract

Let G be a finite abelian group, and let f: G → \C be a complex function on G. The uncertainty principle asserts that the support \supp(f) := \x ∈ G: f(x) ≠ 0\ is related to the support of the Fourier transform f: G → \C by the formula |\supp(f)| |\supp( f)| ≥ |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( f)| ≥ 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.

Cited by

• Fourier Sparsity of Delta Functions and Matching Vector PIRs
• Recovery of Integer Images from Limited DFT Measurements with Lattice Methods
• On Closure Properties of Read-Once Oblivious Algebraic Branching Programs

Related

• An uncertainty inequality for finite abelian groups
• The uncertainty principle for the short-time Fourier transform on finite cyclic groups: cases of equality
• Good cyclic codes and the uncertainty principle
• Uncertainty Principles on Finite Abelian Groups, Restriction Theory, and Applications to Sparse Signal Recovery
• Uncertainty Principle, annihilating pairs and Fourier restriction