Editing Uncertainty principle (section)

===Discrete Fourier transform===
Let <math>\left \{ \mathbf{ x_n } \right \} := x_0, x_1, \ldots, x_{N-1}</math> be a sequence of ''N'' complex numbers and <math>\left \{ \mathbf{X_k} \right \} := X_0, X_1, \ldots, X_{N-1},</math> be its [[Discrete Fourier transform#Uncertainty principles | discrete Fourier transform]].

Denote by <math>\|x\|_0</math> the number of non-zero elements in the time sequence <math>x_0,x_1,\ldots,x_{N-1}</math> and by <math>\|X\|_0</math> the number of non-zero elements in the frequency sequence <math>X_0,X_1,\ldots,X_{N-1}</math>. Then,
<math display="block">\|x\|_0 \cdot \|X\|_0 \ge N.</math>

This inequality is [[inequality (mathematics)#Sharp inequalities|sharp]], with equality achieved when ''x'' or ''X'' is a Dirac mass, or more generally when ''x'' is a nonzero multiple of a Dirac comb supported on a subgroup of the integers modulo ''N'' (in which case ''X'' is also a Dirac comb supported on a complementary subgroup, and vice versa).

More generally, if ''T'' and ''W'' are subsets of the integers modulo ''N'', let <math>L_T,R_W : \ell^2(\mathbb Z/N\mathbb Z)\to\ell^2(\mathbb Z/N\mathbb Z)</math> denote the time-limiting operator and [[bandlimiting|band-limiting operator]]s, respectively. Then
<math display="block">\|L_TR_W\|^2 \le \frac{|T||W|}{|G|} </math>
where the norm is the [[operator norm]] of operators on the Hilbert space <math>\ell^2(\mathbb Z/N\mathbb Z)</math> of functions on the integers modulo ''N''. This inequality has implications for [[signal reconstruction]].<ref name="Donoho">{{cite journal |last1=Donoho |first1=D.L. |last2=Stark |first2=P.B |year=1989 |title=Uncertainty principles and signal recovery |journal=SIAM Journal on Applied Mathematics |volume=49 |issue=3 |pages=906–931 |doi=10.1137/0149053}}</ref>

When ''N'' is a [[prime number]], a stronger inequality holds:
<math display="block">\|x\|_0 + \|X\|_0 \ge N + 1.</math>
Discovered by [[Terence Tao]], this inequality is also sharp.<ref>{{citation|
journal=Mathematical Research Letters
|volume=12
|year=2005
|issue=1
|title=An uncertainty principle for cyclic groups of prime order
|pages=121–127
|author=[[Terence Tao]]
|doi=10.4310/MRL.2005.v12.n1.a11
|arxiv=math/0308286
|s2cid=8548232
}}</ref>