zhan101

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

$\chi(x+y)=\chi(x)\chi(y)$

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

$\hat{f}(x)=\frac{1}{n}\sum_{y\in\mathbb{Z}_n}f(y)\omega^{-xy}.$

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

$P(x_1,x_2,\cdots,x_n)=(x_i-x_j)Q(x_1,x_2,\cdots,x_n)$ .

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.

Proof:
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}$

and

$m_0+m_1+\cdots+m_k=n_0+n_1+\cdots+n_k=m$

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

$x_1^{k-l}x_2^l-x_1^{k-h}x_2^h=x_2^lx_1^{k-h}(x_1^{h-l}-x_2^{h-l})$

$=x_2^lx_1^{k-h}(x_1-x_2)(x_1^{h-l-1}+x_1^{h-l-2}x_2+\cdots+x_2^{h-l-1}).$

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) $p$ th roots of unity such that $P(\omega_1,\cdots,\omega_n)=0$ . Then $P(1,\cdots,1)=0$ is divisible by $p$ .
Proof:
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

$P(x^{k_1},\cdots,x^{k_n})=(x^p-1)q(x)+r(x)$

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_h$ s are distinct $p$ th 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

$D(x_1,\cdots,x_n)=\mathrm{det}\left(x_h^{\xi_k}\right)_{h,k=1}^n.$

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_h$ s 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})$ ).
Proof:
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:
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).$

Proof:
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)}}$

since

$\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$ ,

$\hat{f}(x)=\frac{1}{p}\sum_{y\in\mathbb{Z}_p}f(y)\omega^{-xy}.$

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.

Proof:

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

$[T\delta_{\xi_k}](\eta_h)=\widehat{\delta_{\xi_k}}(\eta_h)=\sum_{x\in\mathbb{Z}p}\delta_{\xi_k}(x)\omega^{-x\eta_h}=\omega^{-\eta_h\xi_k}.$

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 $p$ th 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$ $p$ th roots of unity by Theorem 2, and the claim follows.

References:

Author Archives: zhan101

Math 202C: Lecture 20 – Uncertainty Principle