\input fontmac
\input mathmac
\def\FF{{\bf F}}
\def\TT{{\bf T}}
\def\bar{\overline}
\def\hat{\widehat}
\def\norm#1{|\!|#1|\!|}
\def\bignorm#1{\big|\!\big|#1\big|\!\big|}
\def\Norm#1{\Big|\!\Big|#1\Big|\!\Big|}
\def\normm#1{\bigg|\!\bigg|#1\bigg|\!\bigg|}
\def\supp{\op{{\rm supp}}}
\def\sgn{\op{{\rm sgn}}}
\def\smallsupp{\op{{\sevenrm supp}}}
\def\divides{\backslash}
\def\del{\partial}
\widemargins
\bookheader{THE DISCRETE FOURIER UNCERTAINTY PRINCIPLE}{MARCEL K. GOH}
\maketitle{The discrete Fourier uncertainty principle}{by}{Marcel K. Goh}{6 October 2022}
\bigskip
\advsect Introduction
Let $Z$ be a finite abelian group. A {\it character} on $Z$ is a homomorphism from $Z$ to the multiplicative
group $\CC\setminus \{0\}$. It is easily seen that $|\chi(x)|$ must equal $1$ for all $x\in Z$.
The set of characters forms a group, which we shall denote by $\hat Z$. This is the Pontryagin dual of $Z$.
Letting $\ZZ_n$ be the $n$-element cyclic group,
if $Z = \ZZ_{n_1}\times \ZZ_{n_2} \times\cdots\times \ZZ_{n_r}$, then for every $u = (u_1,\ldots,u_r)\in Z$
the function $\chi_u : Z\to \CC$ given by
$$\chi_u(x_1,\ldots,x_r) = \prod_{i=1}^r \exp\biggl( {2\pi i u_i x_i\over n_i} \biggr)$$
is a character, and in fact the map $u\mapsto \chi_u$ gives an isomorphism of groups from $Z$ to $\hat Z$.
The space of functions from $Z$ to $\CC$ can be made into an inner product space by setting
$$\langle f,g\rangle = \ex_{x\in Z} f(x)\bar{g(x)},$$
where $\ex_{x\in Z} F(x) = |Z|^{-1} \sum_{x\in Z} F(x)$, and likewise we define an inner product on
the space of functions from $\hat Z$ to $\CC$ by putting
$$\langle \hat f, \hat g\rangle = \sum_{\chi \in \hat Z} \hat f(\chi) \bar{\hat g(\chi)}.$$
For $f:Z\to \CC$, the {\it Fourier transform} of $f$ is the function $\hat f : \hat Z\to \CC$ given by
$$ \hat f(\chi) = \langle f,\chi\rangle
= \ex_{x\in Z} f(x) \bar{\chi(x)}.$$
Of course, we can associate to any $\alpha\in Z$ the character $\chi_\alpha\in \hat Z$, so we may write
$\hat f(\alpha)$ to mean $\hat f(\chi_\alpha)$, and this is called the {\it Fourier coefficient
of $f$ at $\alpha$}.
It is not difficult to prove that any two distinct characters are orthogonal in the space
of functions from $Z$ to $\CC$. Furthermore, for any $x\in Z$ we can define a function $F_x : \hat Z\to \CC$
by $F_x(\chi) = \chi(x)$, and one can similarly show that if $x\ne y$, then $\langle F_x, F_y\rangle = 0$.
So since both of the vector spaces $\CC^Z$ and $\CC^{\hat Z}$ have dimension $n$, we have found orthogonal
bases for these spaces, namely $\{\chi_u : u\in Z\}$ and $\{F_x : x\in Z\}$ respectively.
We have the following important formulas, whose proofs
can be found in any book on Fourier analysis.
\parenproclaim Theorem P (Parseval--Plancherel identity). Let $Z$ be a finite abelian group and
let $f,g : Z\to \CC$. If $\hat f$ and $\hat g$ are the Fourier transforms of $f$ and $g$ respectively,
then $\langle f,g \rangle = \langle \hat f, \hat g\rangle$.\slug
\parenproclaim Theorem I (Fourier inversion formula). Let $Z$ be a finite abelian group and let $f:Z\to \CC$.
Then
$$f(x) = \sum_{\chi\in \hat Z} \hat f(\chi) \chi(x).\noskipslug$$
Recall also the {\it Cauchy--Schwarz inequality}, which wears many disguises but in our context says that
$$ \Bigl( \sum_{x\in Z} |f(x)|\cdot |g(x)| \Bigr)^2
\le \Bigl(\sum_{x\in Z} |f(x)|^2\Bigr)\Bigl( \sum_{x\in Z} |g(x)|^2\Bigr)$$
for all $f,g : Z\to \CC$.
\advsect The uncertainty principle
The {\it support} of a function $f:Z\to \CC$ is the set $\{x\in Z : f(x)\ne 0\}$. We will write
$\norm{f}_0$ for the size $|\supp(f)|$ of the support, and it is also convenient to write
$\norm{f}_\infty$ for the quantity $\max_{x\in Z} |f(x)|$. (These are defined analogously for
functions on $\hat Z$.) The uncertainty principle states that
the support of $f:Z\to \CC$ and the support of its Fourier transform $\hat f:\hat Z\to \CC$ cannot both
be small. We will make this fact quantitative very soon. First off, let us prove a lemma.
\proclaim Lemma \advthm. Let $f$ be a function from an abelian group $Z$ to $\CC$ and let $\hat f$
be its Fourier transform. Then
$$\norm{\hat f}_\infty \le \ex_{x\in Z} |f(x)|.$$
\proof Let $\chi\in \hat Z$ be given. We have, by the definition of Fourier transform
and the triangle inequality,
$$|\hat f(\chi)| = \Bigl| \ex_{x\in Z} f(x) \bar{\chi(x)} \Bigr|
\le \ex_{x\in Z} \bigl| f(x) \bar{\chi(x)} \bigr|,$$
but since $|\chi(x)| = 1$ for all $x$, this is exactly the right-hand side of the lemma statement
and we are done since $\chi$ was arbitrary.\slug
We now state and prove the Fourier uncertainty principle.
\parenproclaim Theorem~{\advthm} (Fourier uncertainty principle).
Let $Z$ be a finite abelian group and $\hat Z$ be its dual. If $f : Z\to \CC$ is not identically zero
and $\hat f: \hat Z\to \CC$ is its Fourier transform, then
$$\norm{f}_0 \cdot \norm{\hat f}_0 \ge |Z|.$$
\proof By the previous lemma and the definition of the support,
$$\norm{\hat f}_\infty \le \ex_{x\in Z} |f(x)| = {1\over |Z|} \sum_{x\in Z} |f(x)|
= {1\over |Z|} \sum_{x\in \smallsupp(f)} |f(x)|.$$
We then use the Cauchy--Schwarz inequality to obtain
$$\sum_{x\in \smallsupp(f)} |f(x)| \le \sqrt{\sum_{x\in \smallsupp(f)} |f(x)|}\sqrt{\sum_{x\in \smallsupp(f)} 1^2}
= \sqrt{\norm{f}_0 \sum_{x\in Z} |f(x)|^2},$$
and so far we have shown that
$$\norm{\hat f}_\infty \le {1\over |Z|} \sqrt{\norm{f}_0 \sum_{x\in Z} |f(x)|^2}.$$
But by the Parseval--Plancherel identity, we have
$$\sum_{x\in Z} |f(x)|^2 = |Z| \sum_{\chi\in \hat Z} |\hat f(\chi)|^2
\le |Z|\cdot \norm{\hat f}_0 \cdot \norm{\hat f}_\infty^2, $$
and plugging this in above, we have
$$\norm{\hat f}_\infty \le \norm{\hat f}_\infty \sqrt{ \norm{f}_0\cdot \norm{\hat f}_0 \over |Z|}.$$
Since $f$ is not the zero function, we can divide both sides by $\norm{\hat f}_\infty$, square the
inequality, then rearrange to get the theorem statement.\slug
It can be shown that we have equality above if and only if $f$ is (some multiple of) the characteristic
function of a coset of a subgroup of $Z$.
So far so good, but for $Z = \ZZ_p$ a much stronger uncertainty principle holds, and the rest of these notes
will be dedicated to establishing the algebraic machinery needed to prove it.
\advsect Cyclotomic polynomials
Let $n$ be a positve integer. An {\it $n$th root of unity} is any complex number $\omega$ such
that $\omega^n = 1$. Note that if $d$ divides $n$, then any $\omega$ with $\omega^d = 1$
also satisfies $\omega^n = 1$, so in some sense this number should be associated to $d$ and not
$n$. An $n$th root
of unity is called {\it primitive} if it is not an $m$th root of unity for any $1\le m1$,
$${z^n-1\over \Phi_1(z)} = \lim_{z\to 1} {z^n-1 \over z-1} = \lim_{z\to 1} {nz^{n-1} \over 1} = n,$$
giving us the formula
$$ n = \prod_{d\divides n,\,d>1} \Phi_d(1) .$$
Taking logarithms of both sides, we have
$$\log n = \sum_{d\divides n,\,d>1} \log \Phi_d(1),$$
and by the formula above for the von Mangoldt function $\Lambda$, as well as the fact that $\Lambda(1) = 0$,
we have
$$\sum_{d\divides n,\,d>1} \Lambda(d) = \sum_{d\divides n,\,d>1} \log \Phi_d(1).$$
The claim is that these two sums are actually equal term-by-term. When $n$ is prime, the statement above
already shows that $\log \Phi_p(1) = \Lambda(p) = \log p$,
and supposing the claim proven for all $m1$ such
that $\omega^m \in B$. Factor $m$ into primes $m = p_1p_1\cdots p_k$. Let $\omega_0 = \omega$ and
for $1\le i\le k$ let $\omega_i = \omega^{p_1p_2\cdots p_i}$. Let $j$ be the
smallest integer such that $\omega_j\in B$. (Since $\omega_0\in A$ and $\omega_k = \omega^m\in B$, such
a $j$ must exist.) Now letting $\omega' = \omega^{p_1\cdots p_{j-1}}$ and setting $p=p_j$,
we have found some $\omega'\in A$ and some prime $p$ such that $\omega^p\in B$.
This means that $\omega'$ is a root of both $f(z)$ and $g(z^p)$. Let $h(z)$ be the greatest common divisor
of $f(z)$ and $g(z^p)$. By the Euclidean algorithm there exist polynomials $r(z)$ and $s(z)$
such that
$$ h(z) = f(z)r(z) + g(z^p)s(z),$$
showing that $h(z)$ has $\omega'$ as a root and, in particular, is not constant.
Now we consider everything as polynomials in $\FF_p[z]$, which is a unique factorisation domain.
Applying the previous lemma twice, we have
$h(z^p) = h(z)^p$ and $z^{np}-1 = (z^n-1)^p$ in this ring.
Now since $\Phi_n(z^p) = f(z^p)g(z^p) = f(z)^pg(z^p)$, we find that in $\FF_p[z]$,
the polynomial $h(z)^{p+1}$ divides $\Phi_n(z^p)$, and because $\Phi_n(z^p)$ divides $z^{np}-1 = (z^n -1)^p$,
we see that $h(z)^{p+1}$ divides $(z^n-1)^p$ as well. This means that $h(z)^2$ divides $z^n-1$.
Putting $p(z) = z^n-1$, this means that there is some polynomial $q$ such that $p = h^2q$. Then we
find that $nz^{n-1} = p' = 2h h'q + h^2 q'$ is divisible by $h$, and thus $z^n-1$ and $nz^{n-1}$
have a nonconstant common factor.
On the other hand, letting $n^{-1}$ be the multiplicative inverse of $n$ in $\FF_p$, we can
run the Euclidean algorithm on $z^n-1$ and $nz^{n-1}$:
$$\eqalign{
z^n - 1 &= (n^{-1} z) (nz^{n-1}) + (-1) \cr
nz^{n-1} &= (-1)(-nz^{n-1}) + 0,\cr
}$$
discovering that the greatest common divisor of these two polynomials is $1$.
This contradiction shows that $\Phi_n(z)$ is irreducible over $\ZZ$.\slug
\advsect Vandermonde determinants
In our journey towards proving a stronger uncertainty principle over $\FF_p$, we will require special
polynomials called
{\it Vandermonde determinants}. These are indexed by $n\ge 1$ and defined by
$$\Delta_n(z_1,\ldots,z_n) = \prod_{i=1}^n \prod_{j=i+1}^n (z_j-z_i).$$
The next lemma justifies the name ``determinant''.
\proclaim Lemma \advthm. Let $z_1,\ldots,z_n$ be indeterminates.
Letting
$$V = \pmatrix{
1 & z_1 & {z_1}^2 & \cdots & {z_1}^{n-1} \cr
1 & z_2 & {z_2}^2 & \cdots & {z_2}^{n-1} \cr
\vdots & \vdots & \vdots & \ddots & \vdots \cr
1 & z_n & {z_n}^2 & \cdots & {z_n}^{n-1} \cr
},$$
we have $\Delta_n(z_1,\ldots,z_n) = \det V$.
\proof By the Leibniz formula for determinants, we have
$$\det V = \sum_{\pi\in {\frak S}_n} \sgn(\pi) \prod_{i=1}^n {z_i}^{\pi(i) - 1},$$
where ${\frak S}_n$ is the symmetric group of all permutations on $n$ letters. (The factor $\sgn(\pi)$ is
$1$ if the permutation $\pi$ factors as a product of an even number of transpositions,
and $-1$ if it factors as an odd number of transpositions.) Since the $i$th column of $V$
contains only monomials of degree $i-1$, every term of $\det V$ is a monomial in which the sum
of the degrees over all coefficients is $0 + 1 + \cdots n-1 = n(n-1)/2$.
In the formula
$$\Delta_n(z_1,\ldots,z_n) = \prod_{i=1}^n \prod_{j=i+1}^n (z_j-z_i),$$
note that since the product runs over ${n\choose 2} = n(n-1)/2$ linear factors, every term in this sum
is a monomial of total degree $n(n-1)/2$ as well. Because $\det V$ is equal to zero if any two
of the $z_i$ are equal, $\det V$ is divisible by
the linear polynomial $z_j-z_i$ for all $i < j$. Repeating this for all such $i$ and $j$, we
conclude that $\Delta_n(z_1,\ldots,z_n)$ divides $\det V$; that is,
$\det V = \Delta_n f$ for some polynomial $f$. But since both of them consist purely of
monomials of total degree $n$, $f$ must be a constant polynomial. To find out what this
constant factor is, note that the term corresponding to the identity permutation in the Leibniz formula
is $z_2{z_3}^2{z_4}^3\cdots {z_n}^{n-1}$, and expanding
$$\Delta_n(z_1,\ldots,z_n) = (z_2-z_1)(z_3-z_2)(z_3-z_1)(z_4-z_3)\cdots(z_n-z_{1}),$$
a moment's scrutiny reveals that this term is also $z_2{z_3}^2{z_4}^3\cdots {z_n}^{n-1}$, and hence
$f$ must equal $1$, which is what we needed.\slug
\newcount\vandermonde
\vandermonde=\thmcount
\proclaim Lemma \advthm. Let $n_1,\ldots, n_k$ be positive integers and let $P\in \ZZ[z_1,\ldots,z_k]$
be the polynomial given by
$$ P(z_1,\ldots,z_n) = \sum_{\pi\in {\frak S}_k} \sgn(\pi) \prod_{i=1}^k {z_i}^{n_{\pi(i)}}.$$
Then we may factor $P = \Delta_k Q$, where $Q\in \ZZ[z_1,\ldots,z_k]$ is such that
$$Q(1,1,\ldots,1) = \Delta_k(n_1, \ldots, n_k) / \Delta_k(1,\ldots,k).$$
\proof By the Leibniz formula, $P(z_1,\ldots,z_n)$ is the determinant of
the $k\times k$ matrix whose entry in the $i$th row and $j$th column is $z_j^{n_i}$. As in the previous
proof, $P$ is divisible by $z_j-z_i$ for all $ip+1$. Consider the set
$$S = \{(A', B') : A'\subseteq A, B'\subseteq B, |A|+|B| = p+1\}.$$
This set is finite, so let us index its elements $(A_1,B_1),\ldots, (A_s, B_s)$. From
the previous paragraph, there exist functions $f_1,\ldots,f_s$ such that for all $1\le i\le s$,
$\supp(f_i) = A_i$ and $\supp(\hat{f_i}) = B_i$. Now let
$$f = \lambda_1 f_1 + \cdots \lambda_s f_s$$
for some scalars $\lambda_i\in \CC$ to be chosen later. It is clear that $\supp(f) \subseteq A$
and, since the Fourier transform is linear, we also have
$\supp(\hat f) \subseteq B$. This is true regardless of our choices for the $\lambda_i$. Now we must prove
that we can pick the $\lambda_i$ so that $A\subseteq \supp(f)$ and $B\subseteq \supp(\hat f)$. For
$x\in A$, let
$$ V_x = \Bigl\{ (\lambda_1,\ldots,\lambda_s) \in \CC^s : \sum_{i=1}^s \lambda_i f_i(x) = 0 \Bigr\}.$$
This is a subspace of codimension $1$ in $\CC^s$, since we have $s$ degrees of freedom and one nontrivial
linear constraint. Similarly, for all $x\in B$, let
$$ W_x = \Bigl\{ (\lambda_1,\ldots,\lambda_s) \in \CC^s : \sum_{i=1}^s \lambda_i \hat{f_i}(x) = 0 \Bigr\}.$$
Now
$$\bigcup_{x\in A} V_x \cup \bigcup_{x\in B} W_x$$
is a finite union of subspaces of codimension $1$. Thus its complement is nonempty and we can choose
$\lambda_1,\ldots,\lambda_s$ such that the resulting $f$ has $f(x) \ne 0$ for all $x\in A$
and ${\hat f}(x)\ne 0$ for all $x\in B$. This completes the proof.\slug
\advsect The Cauchy--Davenport theorem
We now use Tao's uncertainty principle for cyclic groups of prime order to prove the Cauchy--Davenport theorem.
First, we need to define the {\it convolution} of two functions $f,g:Z \to \CC$. This is denoted $f * g$
and given by
$$ (f*g)(x) = \ex_{y+z = x} f(y)g(z).$$
The following easy theorem describes the nice behaviour of convolutions under Fourier transform.
\parenproclaim Theorem C (Convolution law). Let $Z$ be a finite abelian group and $f,g: Z\to \CC$.
For all $\chi\in \hat Z$, we have $\hat{f * g} (\chi) = \hat f(\chi)\hat g(\chi)$.
\proof We expand
$$\hat{f*g}(\chi) = \ex_{x\in Z} (f*g)(x)\bar{\chi(x)} = \ex_{x\in Z} \ex_{y+z=x} f(y)g(z)\bar{\chi(y)\chi(z)}.$$
But note that $x$ does not appear anywhere in the summand, so we can rewrite this as an expectation over
{\it all} $y$ and $z$ (their sum must equal $x$ for some $x\in Z$). So
$$\hat{f*g}(\chi) = \ex_{y\in Z}\ex_{z\in Z} f(y)\bar{\chi(y)} g(z)\bar{\chi(z)}
=\hat f(\chi)\hat g(\chi),$$
which is what we wanted.\slug
Now let $Z$ be a finite abelian group and let $A$ and $B$ be subsets of $Z$. We define the {\it sumset}
$A+B$ to be the set of all sums $a+b$ where $a\in A$ and $b\in B$. This is related to the
convolution operation above, since if $\supp (f) = A$
and $\supp (g) = B$, then $\supp(f*g)\subseteq A+B$. Also notice that the convolution law gives
$\supp\bigl(\hat{f*g}\bigr) = \supp(\hat f)\cap \supp(\hat g)$.
\parenproclaim Theorem {\advthm} (Cauchy--Davenport theorem). Let $A$ and $B$ be nonempty subsets of
$\ZZ_p$. Then we have
$$|A+B| \ge \min\bigl( |A|+|B| - 1, p\bigr).$$
\proof Since $A$ is nonempty, we can build a nonempty set $X\subseteq \ZZ_p$ with $p+1-|A|$ elements, so that
$\ZZ_p \setminus X$ has $|A|-1$ elements. Then since $B$ is nonempty, if $|X|+1 > |B|$, then
we can pick $Y'\subseteq X$ with $|X|+1-|B|$ elements, and let $Y = Y' \cup (\ZZ_p \setminus X)$, so that
$$|Y| = p+1 - |A| +1 -|B| + |A|-1 = p+1-|B|.$$
If instead $|X| + 1 \le |B|$, then we let $Y'$ be any singleton subset of $X$ and
since $p-|X| \ge p+1-|B|$ we can find a subset $Y''$ of
$\ZZ_p\setminus X$ of size $p-|B|$. Letting $Y = Y' \cup Y''$, we also have $|Y| = p+1-|B|$ in this case,
and in both cases we have
$$|X\cap Y| = \max\bigl(|X|+1-|B|, 1\bigr) = \max\bigl( |X|+|Y|-p, 1\bigr).$$
Now since $|A|+|X| = |B|+|Y| = p+1$, by Tao's uncertainty principle we can find $f : \ZZ_p\to \CC$ with
$\supp(f) = A$ and $\supp(\hat f) = X$, as well as $g:\ZZ_p\to \CC$ with
$\supp(g) = B$ and $\supp(\hat g) = Y$. As we saw before, the convolution $f*g$ has support contained in $A+B$ and
the support of its Fourier transform equals $X\cap Y$. By the other direction of Tao's uncertainty principle,
we must have
$$|A+B|+|X\cap Y| \ge |\supp(f*g)| + \bigl|\supp\bigl( \hat{f*g}\bigr)\bigr| \ge p+1.$$
But since $|X|+|Y|-p = p+2-|A|-|B|$,
$$|A+B| \ge p+1 - \max\bigl( |X|+|Y|-1, 1\bigr) = \min(|A|+|B|-1, p),$$
exactly what we wanted to show.\slug
\section References
\bye