\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