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. 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, 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 hypercube group .
Let be a finite set and denote by the vector space of all complex -valued functions defined on . Then , where denotes cardinality.
For we denote by the Dirac function centered at , that is , the element defined by if and if for all .
The set is a natural basis for and if then .
The space is endowed with the scalar product defined by setting
for , and we denote by the norm of . Note that is an orthonormal basis of with respect to .
Let be a finite Abelian group. A character of is a map such that
for all . The set of all characters of is an Abelian group with respect to the product defined by for all . is called the dual of .
For , where is the cyclic group of order , , . Let . For , define by the function .
Exercise 1: Check that for , is indeed a character of , and is isomorphic to .
Now we define the Discrete Fourier transform. Let be a finite Abelian group. The Fourier transform of a function is the function defined by
for all . Then is called the Fourier coefficient of with respect to . When and , we call the Discrete Fourier transform (DFT) of . Specifically, for and , the DFT of is
The uncertainty principle is the following (see Theorem 2.5.4 of ):
Theorem (Uncertainty principle): Let and suppose that . Then
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 is cyclic with prime order . To prove the theorem, we present some specific tools developed in Tao’s paper .
The main theorem in  is the following:
Theorem (Tao’s uncertainty principle): Let be a prime number and non-zero. Then
Conversely, if are two subsets such that , then there exists such that and .
To prove the theorem, we present some specific tools developed in Tao’s paper .
Recall that denotes the ring of polynomials with integer coefficients.
Let be a polynomial in the variables with integer coefficients. Suppose that for some ,
Then there exists a polynomial with integer coefficients such that
Remark: The proof of this proposition can be omitted for the first reading. Instead, considering and trying to find corresponding by using this proposition would be helpful for understanding.
For the sake of simplicity, suppose that and so that . Let us denote by (respectively ) the sum of the monomials of with positive (respectively negative) coefficients so that
since . This implies that there exists a bijection between the monomials in and those in . More precisely, let us fix and ; then the monomial appears in if and only if appears in . Suppose this is the case. Then we can find and non-negative integers such that the sum of the monomials of whose variables have degree for and is
but also such that
(because otherwise there would be a cancellation). Thus, with every monomial such that we can (arbitrarily but bijectively) associated a monomial with and . Now for we have the identity
Exchanging with we get the analogous identity for . This shows that
is divisible by .
Repeating the argument for each monomial with and appearing in , we deduce that is divisible by .
Lemma 1: Let be a prime, a positive integer, and a polynomial with integer coefficients. Suppose that are (not necessarily distinct) th roots of unity such that . Then is divisible by .
Letting we can find integers such that for .
Define the polynomials by settinig
where . Then and since we deduce that is a multiple of the minimal polynomial of , that is, for some , where we used a fact in undergraduate algebra that the minimal polynomial of is . It follows that .
Let be a prime and . Let (respectively ) be the distinct elements in . Then the matrix
Proof: Set for . Note that the s are distinct th root of unity and . Define the polynomial with integer coefficients by setting
As the determinant is an alternating form, we have whenever , so that, by recursively applying Proposition 1, we can find a polynomial with integer coefficients such that
To prove the theorem, it is equivalent to show that (because s are all distinct) so that, by Lemma 1 it suffices to show that does not divide . For this we need the next three lemmas to complete this proof. Let us first introduce some notations.
Given an -tuple of non-negative integers, we say that the (monomial) differential operator
is of type and order .
Let be a differential operator of type and and two polynomials. Then
where the sum runs over all pairs such that (componentwise) (and therefore ).
Left as as exercise.
Exercise 2: Prove Lemma 2. (Hint: use induction on the order of .)
For and we have
where runs over all with and the s are non-negative integers such that . In particular,
Proof by induction on . For the details see Lemma 2.6.15 of section 2.6 of .
Let , that is,
Then if and are given by
By Lemma 2 and 3, we have
with . Here the first term is obtained by acting the whole on (the second term of ). In particular, taking for we complete the proof.
Now we can finish the proof of Theorem 3 with these lemmas.
Proof of Theorem 3 (continued):
For as in Lemma 4, we have (where denotes the symmetric group of degree )
for all . Thus,
is the Vandermonde determinant. Since for , we deduce that is not divisible by because . Thus, by Lemma 4, is not divisible by either. By Lemma 1, this completes the proof of Theorem 3.
Given a non-empty subset and a function , we denote by its extension defined by setting for all . For simplicity, we regard the DFT as a map . In other words, for and ,
Let be a prime. Let such that . Then the linear map defined by is invertible.
Set and and consider the basis of (respectively, of ) consisting of the Dirac functions with (respectively, with ) and let . Then we have
By virtue of Theorem 3, we have
showing that is indeed invertible.
Finally, we can prove the main result, Theorem 2.
Proof of Theorem 2:
Suppose by contradiction that there exists non-zero such that and with . Then we can find a subset such that and . We deduce that is identicially zero. Since , this contradicts the injectivity of (c.f. Proposition 2).
Conversely, let be two subsets such that . Let such that and . Note that . Taking cardinalities, , which yields
Consider the map . By Proposition 2, we can find such that so that vanishes on but . Setting we clearly have and . By the first part of the theorem,
so that all the inequalities are in fact equalities, i.e., and . This completes the second part of the theorem.
An immediate consequence of Theorem 2 is that any sparse polynomial with non-zero coefficients and , when restricted to the th roots of unity , can have at most zeroes. Indeed, such a polynomial is essentially the Fourier transform in of a function whose support has cardinality , and so the support of the polynomial must contain at least th roots of unity by Theorem 2, and the claim follows.
-  Ceccherini-Silberstein, T., Scarabotti, F., & Tolli, F. (2018). Discrete Harmonic Analysis: Representations, Number Theory, Expanders, and the Fourier Transform (Cambridge Studies in Advanced Mathematics). Cambridge: Cambridge University Press. doi:10.1017/9781316856383
-  Terence Tao. An uncertainty principle for cyclic groups of prime order.