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 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 [1]):
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 [2].
The main theorem in [2] 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 [2].
Recall that denotes the ring of polynomials with integer coefficients.
Proposition 1:
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.
Proof:
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
Note 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
and
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
.
Proof:
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
.
Theorem 3(Chebotarev):
Let be a prime and
. Let
(respectively
) be the distinct elements in
. Then the matrix
is nonsingular.
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
.
Lemma 2:
Let be a differential operator of type
and
and
two polynomials. Then
where the sum runs over all pairs such that (componentwise)
(and therefore
).
Proof:
Left as as exercise.
Exercise 2: Prove Lemma 2. (Hint: use induction on the order of .)
Lemma 3:
For and
we have
where runs over all
with
and the
s are non-negative integers such that
. In particular,
with .
Proof:
Proof by induction on . For the details see Lemma 2.6.15 of section 2.6 of [1].
Lemma 4:
Let , that is,
Then if and
are given by
we have
Proof:
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
)
since
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
,
Proposition 2:
Let be a prime. Let
such that
. Then the linear map
defined by
is invertible.
Proof:
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.
References:
- [1] 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
- [2] Terence Tao. An uncertainty principle for cyclic groups of prime order.