Math 202C: Lecture 20 – Uncertainty Principle

Author: Zhaolong Han

In this lecture, we will introduce the Fourier transform on finite Abelian group and a discrete version of “uncertainty principle” based on the chapter 2 of “Discrete Harmonic Analysis” by Ceccherini-Sillberstein[1]. In quantum mechanics, there is a well-known uncertainty principle saying that the more precisely the position of some particle is determined, the less precisely its momentum can be predicted from initial conditions, and vice versa.
For finite Abelian group, there is a theorem that assimilates this uncertainty principle, so people refer to this group-theoretic version as “uncertainty principle” too. However, our focus today will be Tao’s uncertainty principle for cyclic group of prime order[2], which is a refinement of the discrete uncertainty principle due to the special structure of the group.

First, let us introduce some notations and redefine the Discrete Fourier transform as Andrew did in Lecture 18. In fact, these materials already appeared in Lecture 8, where we studied the concrete example of the the rank k hypercube group B(k).

Let X be a finite set and denote by L(X)=\{f:X\to \mathbb{C}\} the vector space of all complex -valued functions defined on X. Then \mathrm{dim}\ L(X)=|X|, where |\cdot| denotes cardinality.

For x\in X we denote by \delta_x the Dirac function centered at x, that is , the element \delta_x\in L(X) defined by \delta_x(y)=1 if y=x and \delta_x(y)=0 if y\neq x for all y\in X.

The set \{\delta_x:x\in X\} is a natural basis for L(X) and if f\in L(X) then f=\sum_{x\in X}f(x)\delta_x.

The space L(X) is endowed with the scalar product defined by setting

\langle f_1,f_2\rangle=\sum_{x\in X}f_1(x)\overline{f_2(x)}

for f_1,f_2\in L(X), and we denote by ||f||=\sqrt{\langle f,f\rangle} the norm of f\in L(X). Note that {\delta_x:x\in X} is an orthonormal basis of L(X) with respect to \langle\cdot\rangle.

Let A be a finite Abelian group. A character of A is a map \chi:A\to\mathbb{T} such that


for all x,y\in A. The set \widehat{A} of all characters of A is an Abelian group with respect to the product (\chi,\psi)\mapsto \chi\cdot\psi defined by (\chi\cdot\psi)(x)=\chi(x)\psi(x) for all x\in A. \widehat{A} is called the dual of A.

For A=\mathbb{Z}_n, where \mathbb{Z}_n is the cyclic group of order n, n\ge 2, n\in \mathbb{N}. Let \omega:=e^{\frac{2\pi i}{n}}. For x\in \mathbb{Z}_n, define \chi_x\in L(\mathbb{Z}_n) by the function z\mapsto \omega^{zx}.

Exercise 1: Check that for x\in \mathbb{Z}_n, \chi_x is indeed a character of \mathbb{Z}_n, and \widehat{\mathbb{Z}_n}=\{\chi_x:x\in \mathbb{Z}_n\} is isomorphic to \mathbb{Z}_n.

Now we define the Discrete Fourier transform. Let A be a finite Abelian group. The Fourier transform of a function f\in L(A) is the function \hat{f}\in L(\widehat{A}) defined by

\widehat{f}(\chi)=\sum_{y\in A}f(y)\overline{\chi(y)}

for all \chi\in \widehat{A}. Then \widehat{f}(\chi) is called the Fourier coefficient of f with respect to \chi. When A=\mathbb{Z}_n and f\in L(\mathbb{Z}_n), we call \frac{1}{n}\hat{f} the Discrete Fourier transform (DFT) of f. Specifically, for x\in\mathbb{Z}_n and \omega=e^{\frac{2\pi i}{n}}, the DFT of f is


The uncertainty principle is the following (see Theorem 2.5.4 of [1]):
Theorem (Uncertainty principle): Let f\in L(A) and suppose that f\neq 0. Then

|\mathrm{supp}(f)|\cdot|\mathrm{supp}\hat{f}|\ge |A|.

Now we come to the main part of this lecture: Tao’s uncertainty principle for cyclic group of prime order. This improves the inequality in the above discrete uncertainty principle when the finite Abelian group A is cyclic with prime order p. To prove the theorem, we present some specific tools developed in Tao’s paper [2].

The main theorem in [2] is the following:
Theorem (Tao’s uncertainty principle): Let p be a prime number and f\in L(\mathbb{Z}_p) non-zero. Then

|\mathrm{supp}(f)|+|\mathrm{supp}(\hat{f})|\ge p+1.

Conversely, if \emptyset\neq A,A'\subset \mathbb{Z}_p are two subsets such that |A|+|A'|=p+1, then there exists f\in L(\mathbb{Z}_p) such that \mathrm{supp}(f)=A and \mathrm{supp}(\hat{f})=A'.

To prove the theorem, we present some specific tools developed in Tao’s paper [2].

Recall that \mathbb{Z}[x] denotes the ring of polynomials with integer coefficients.

Proposition 1:
Let P(x_1,x_2,\cdots,x_n) be a polynomial in the variables x_1,x_2,\cdots,x_n with integer coefficients. Suppose that for some i\neq j,

P(x_1,x_2,\cdots,x_n)|_{x_i=x_j}\equiv 0.

Then there exists a polynomial Q(x_1,x_2,\cdots,x_n) with integer coefficients such that


Remark: The proof of this proposition can be omitted for the first reading. Instead, considering P(x_1,x_2)=x_1^2+x_1x_2-2x_2^2 and trying to find corresponding Q(x_1,x_2) by using this proposition would be helpful for understanding.

For the sake of simplicity, suppose that i = 1 and j = 2 so that P(x_1,x_2,\cdots,x_n) \equiv 0. Let us denote by P_1(x_1,x_2,\cdots,x_n) (respectively P_2(x_1,x_2,\cdots,x_n)) the sum of the monomials of P(x_1,x_2,\cdots,x_n) with positive (respectively negative) coefficients so that

P(x_1,x_2,\cdots,x_n) = P_1(x_1,x_2,\cdots,x_n) + P_2(x_1,x_2,\cdots,x_n).

Note that

P_1(x_1,x_1,x_3,\cdots,x_n) =- P_2(x_1,x_1,x_3,\cdots,x_n),

since P(x_1 , x_1 ,x_3, \cdots , x_n ) \equiv 0. This implies that there exists a bijection between the monomials in P_1(x_1,x_1,x_3,\cdots,x_n) and those in P_2(x_1,x_1,x_3,\cdots,x_n). More precisely, let us fix m > 0 and k, k_3 , \cdots, k_n \ge 0; then the monomial mx_1^k x_3^{k_3}\cdots x_n^{k_n} appears in P_1(x_1,x_1,x_3,\cdots,x_n) if and only if -mx_1^k x_3^{k_3}\cdots x_n^{k_n} appears in P_2(x_1,x_1,x_3,\cdots,x_n). Suppose this is the case. Then we can find m_0 , m_1 , \cdots , m_k and n_0 , n_1 , \cdots, n_k non-negative integers such that the sum of the monomials of P(x_1,x_1,x_3,\cdots,x_n) whose variables x_i have degree k_i for i = 1, 2,\cdots , n and k_1 + k_2 = k is

\sum_{l=0}^k m_lx_1^{k-l}x_2^lx_3^{k_3}\cdots x_n^{k_n}-\sum_{l=0}^k n_lx_1^{k-l}x_2^lx_3^{k_3}\cdots x_n^{k_n}



but also such that

m_l\neq 0\implies n_l=0\quad n_l\neq 0\implies m_l\neq 0

(because otherwise there would be a cancellation). Thus, with every monomial x_1^{k-l}x_2^lx_3^{k_3}\cdots x_n^{k_n} such that m_l\neq 0 we can (arbitrarily but bijectively) associated a monomial x_1^{k-h}x_2^lx_3^{k_3}\cdots x_n^{k_n} with m_h\neq 0 and h\neq l. Now for h>l we have the identity



Exchanging h with l we get the analogous identity for h<l. This shows that

\sum_{l=0}^k m_lx_1^{k-l}x_2^lx_3^{k_3}\cdots x_n^{k_n}-\sum_{l=0}^k n_lx_1^{k-l}x_2^lx_3^{k_3}\cdots x_n^{k_n}

is divisible by x_1-x_2.

Repeating the argument for each monomial mx_1^kx_3^{k_3}\cdots x_n^{k_n} with m>0 and k,k_3,\cdots,k_n\ge 0 appearing in P_1(x_1,\cdots,x_n), we deduce that P(x_1,\cdots,x_n) is divisible by x_1-x_2.

Lemma 1: Let p be a prime, n a positive integer, and P(x_1,x_2,\cdots,x_n) a polynomial with integer coefficients. Suppose that \omega_1,\cdots,\omega_n are (not necessarily distinct) pth roots of unity such that P(\omega_1,\cdots,\omega_n)=0. Then P(1,\cdots,1)=0 is divisible by p.
Letting \omega=e^{\frac{2\pi i}{p}} we can find integers 0\le k_j\le p-1 such that \omega_j=\omega^{k_j} for j=1,2,\cdots,n.

Define the polynomials q(x),r(x)\in\mathbb{Z}[x] by settinig


where \mathrm{deg}r<p. Then r(\omega)=0 and since \mathrm{deg}r<p we deduce that r(x) is a multiple of the minimal polynomial of \omega, that is, r(x)=m(1+x+\cdots+x^{p-1}) for some m\in\mathbb{Z}, where we used a fact in undergraduate algebra that the minimal polynomial of \omega is 1+x+\cdots+x^{p-1}. It follows that P(1,\cdots,1)=r(1)=mp.

Theorem 3(Chebotarev):
Let p be a prime and 1\le n\le p. Let \eta_1,\cdots,\eta_n (respectively \xi_1,\cdots,\xi_n) be the distinct elements in \{0,1,\cdots,p-1\}. Then the matrix

A=\left(e^{\frac{2\pi i\eta_h\xi_k}{p}}\right)_{h,k=1}^n

is nonsingular.

Proof: Set \omega_h=e^{\frac{2\pi i\eta_h}{p}} for h=1,2,\cdots,n. Note that the \omega_hs are distinct pth root of unity and A=\left(\omega_h^{\xi_k}\right)_{h,k=1}^n. Define the polynomial D(x_1,\cdots,x_n) with integer coefficients by setting


As the determinant is an alternating form, we have D(x_1,\cdots,x_n)|{x_h=x_k}\equiv 0 whenever 1\le h\neq k\le n, so that, by recursively applying Proposition 1, we can find a polynomial Q(x_1,\cdots,x_n) with integer coefficients such that

D(x_1,\cdots,x_n)=Q(x_1,\cdots,x_n)\prod_{1\le h<k\le n}(x_k-x_h).

To prove the theorem, it is equivalent to show that Q(\omega_1,\cdots,\omega_n)\neq 0 (because \omega_hs are all distinct) so that, by Lemma 1 it suffices to show that p does not divide Q(1,\cdots,1). For this we need the next three lemmas to complete this proof. Let us first introduce some notations.

Given an n-tuple \mathbf{k}=(k_1,\cdots,k_n) of non-negative integers, we say that the (monomial) differential operator

L=\mathbf{L_k}=\left(x_1\frac{\partial}{\partial x_1}\right)^{k_1}\cdots\left(x_n\frac{\partial}{\partial x_n}\right)^{k_n}

is of type \mathbf{k} and order o(\mathbf{k})=k_1+\cdots+k_n.

Lemma 2:
Let L be a differential operator of type \mathbf{k} and F(x_1,\cdots,x_n) and G(x_1,\cdots,x_n) two polynomials. Then

L(FG)=\sum_{(\mathbf{i},\mathbf{j})}L_{\mathbf{i}}(F)\cdot L_{\mathbf{j}}(G)

where the sum runs over all pairs (\mathbf{i},\mathbf{j}) such that (componentwise) \mathbf{i}+\mathbf{j}=\mathbf{k} (and therefore o(\mathbf{i})+o(\mathbf{j})=o(\mathbf{k})).
Left as as exercise.

Exercise 2: Prove Lemma 2. (Hint: use induction on the order of L.)

Lemma 3:
For 1\le j\le n and 1\le h\le j-1 we have

\left(x_j\frac{\partial}{\partial x_j}\right)^{h}(x_j-x_1)(x_j-x_2)\cdots (x_j-x_{j-1})=\sum_{t=1}^ha_{h,t}x_j^t\sum_{\mathbf{i}_t}\prod_{1\le i\le j-1,i\neq i_1,\cdots,i_t}(x_j-x_i)

where \sum_{\mathbf{i}_t} runs over all \mathbf{i}_t=(i_1,\cdots,i_t) with 1\le i_1<\cdots<i_t\le j-1 and the a_{h,t}=a_{h,t}(j)s are non-negative integers such that a_{h,h}=h!. In particular,

\left(x_j\frac{\partial}{\partial x_j}\right)^{j-1}(x_j-x_1)(x_j-x_2)\cdots (x_j-x_{j-1})=(j-1)!x_j^{j-1}+\text{terms containing at least one factor } (x_j-x_i)

with 1\le i<j.
Proof by induction on h=1,\cdots,j-1. For the details see Lemma 2.6.15 of section 2.6 of [1].

Lemma 4:
Let L=L_{(0,1,\cdots,n-1)}, that is,

L=\left(x_1\frac{\partial}{\partial x_1}\right)^{0}\cdots\left(x_n\frac{\partial}{\partial x_n}\right)^{n-1}.

Then if D(x_1,\cdots,x_n) and Q(x_1,\cdots,x_n) are given by

D(x_1,\cdots,x_n)=Q(x_1,\cdots,x_n)\prod_{1\le h<k\le n}(x_k-x_h),

we have

[LD](1,\cdots,1)=\prod_{j=1}^n (j-1)!Q(1,\cdots,1).

By Lemma 2 and 3, we have

[LD](1,\cdots,1)\prod_{j=1}^n(j-1)!x_j^{j-1}Q(x_1,\cdots,x_n)+\text{terms containing at least one factor }(x_j-x_i)

with 1\le i<j\le n. Here the first term is obtained by acting the whole L on \prod_{1\le h<k\le n}(x_k-x_h) (the second term of D). In particular, taking x_i=1 for i=1,\cdots,n we complete the proof.

Now we can finish the proof of Theorem 3 with these lemmas.

Proof of Theorem 3 (continued):
For L as in Lemma 4, we have (where S_n denotes the symmetric group of degree n)

[LD](x_1,\cdots,x_n)=L\sum_{\sigma\in S_n}\epsilon(\sigma)x_1^{\xi_{\sigma(1)}}\cdots x_n^{\xi_{\sigma(n)}}

=\sum_{\sigma\in S_n}\epsilon(\sigma)\xi^0_{\sigma(1)}x_1^{\xi_{\sigma(1)}}\cdots \xi_{\sigma(n)}^{n-1}x_n^{\xi_{\sigma(n)}}


\left(x_j\frac{\partial}{\partial x_j}\right)^{j-1}x_j^{\xi_{\sigma(j)}}=\xi_{\sigma(j)}^{j-1}x_j^{\xi_{\sigma(j)}}

for all j=1,2,\cdots,n. Thus,

[LD](1,\cdots,1)=\sum_{\sigma\in S_n}\epsilon(\sigma)\xi_{\sigma(1)}^0\cdots\xi_{\sigma(n)}^{n-1}=\prod_{1\le i<j\le n}(\xi_j-\xi_i)

is the Vandermonde determinant. Since \xi_i\neq \xi_j for i<j, we deduce that [LD](1,\cdots,1) is not divisible by p because n\le p. Thus, by Lemma 4, Q(1,\cdots,1) is not divisible by p either. By Lemma 1, this completes the proof of Theorem 3.

Given a non-empty subset A\subset \mathbb{Z}_p and a function f\in L(A), we denote by \overline{f} its extension \overline{f}:\mathbb{Z}_p\to \mathbb{C} defined by setting \overline{f}(z)=0 for all z\in \mathbb{Z}_p\backslash A. For simplicity, we regard the DFT as a map L(\mathbb{Z}_p)\to L(\mathbb{Z}_p). In other words, for f\in L(\mathbb{Z}_p) and x\in \mathbb{Z}_p,


Proposition 2:
Let p be a prime. Let A,B\subset\mathbb{Z}_p such that |A|=|B|. Then the linear map T=T{A,B}:L(A)\to L(B) defined by Tf=\widehat{\overline{f}}|B is invertible.


Set A={\xi_1,\cdots,\xi_n} and B={\eta_1,\cdots,\eta_n} and consider the basis of L(A) (respectively, of L(B)) consisting of the Dirac functions \delta_{\xi_j} with j=1,\cdots,n (respectively, \delta_{\eta_k} with k=1,\cdots,n) and let \omega=e^{\frac{2\pi i}{p}}. Then we have


By virtue of Theorem 3, we have

\mathrm{det}\left([T\delta_{\xi_k}](\eta_h)\right)_{h,k=1}^n\neq 0,

showing that T is indeed invertible.

Finally, we can prove the main result, Theorem 2.

Proof of Theorem 2:
Suppose by contradiction that there exists f\in L(\mathbb{Z}_p) non-zero such that \mathrm{supp}(f)=A and \mathrm{supp}(\hat{f})=C with |A|+|C|\ge p+1. Then we can find a subset B\subset \mathbb{Z}_p such that |B|=|A| and C\cap B=\emptyset. We deduce that Tf=\widehat{\overline{f}}|_B is identicially zero. Since f\not\equiv 0, this contradicts the injectivity of T (c.f. Proposition 2).

Conversely, let \emptyset\neq A,A'\subset\mathbb{Z}p be two subsets such that |A|+|A'|=p+1. Let B\subset\mathbb{Z}_p such that |B|=|A| and B\cap A'={\xi}. Note that (\mathbb{Z}_p\backslash B)\cup{\xi}\supset A'. Taking cardinalities, |A'|=p+1-|A|=p+1-|B|=|(\mathbb{Z}_p\backslash B)\cup{\xi}|\ge |A'|, which yields

(\mathbb{Z}_p\backslash B)\cup{\xi}=A'.

Consider the map T=T_{A,B}:L(A)\to L(B). By Proposition 2, we can find g\in L(A) such that Tg=\delta_\xi|_B so that \widehat{\Bar{g}} vanishes on B\backslash{\xi} but \widehat{\Bar{g}}(\xi)\neq 0. Setting f=\Bar{g}\in L(\mathbb{Z}_p) we clearly have \mathrm{supp}(f)\subset A and \mathrm{supp}(\hat{f})\subset (\mathbb{Z}_p\backslash B)\cup{\xi}. By the first part of the theorem,

p+1\le |\mathrm{supp}(f)|+|\mathrm{supp}(\hat{f})|\le |A|+|\mathbb{Z}_p\backslash B|+1 =|A|+p-|B|+1=p+1

so that all the inequalities are in fact equalities, i.e., \mathrm{supp}(f)=A and \mathrm{supp}(\hat{f})= (\mathbb{Z}_p\backslash B)\cup{\xi}=A'. This completes the second part of the theorem.

An immediate consequence of Theorem 2 is that any sparse polynomial \sum_{j=0}^k c_jz^{n_j} with k+1 non-zero coefficients and 0<n_0<\cdots<n_k<p, when restricted to the pth roots of unity \{z:z^p=1\}, can have at most k zeroes. Indeed, such a polynomial is essentially the Fourier transform in \mathbb{Z}_p of a function whose support has cardinality k+1, and so the support of the polynomial must contain at least p-k pth roots of unity by Theorem 2, and the claim follows.


Leave a Reply