## §8.5: Abelian groups

The previous section covered the case of $f \in L^2(\Omega^n, \pi^{\otimes n})$ with $|\Omega| = 2$; there, we saw it could be helpful to look at explicit Fourier bases. When $|\Omega| \geq 3$ this is often not helpful, especially if the only “operation” on the domain is equality. For example, if $f : \{\mathsf{Red}, \mathsf{Green}, \mathsf{Blue}\}^n \to {\mathbb R}$ then it’s best to just work abstractly with the orthogonal decomposition. However if there is a notion of, say, “addition” in $\Omega$ then there is a natural, canonical Fourier basis for $L^2(\Omega, \pi)$ when $\pi$ is the uniform distribution.

More precisely, suppose the domain $\Omega$ is a finite abelian group $G$, with operation $+$ and identity $0$. We will consider the domain $G$ under the uniform probability distribution $\pi$; this is quite natural because $\pi$ is translation-invariant: $\pi(X) = \pi(t + X)$ for any $X \subseteq G$, $t \in G$. In this setting it is more convenient to allow functions with range the complex numbers; thus we come to the following definition:

Definition 50 Let $G$ be a finite abelian group with operation $+$ and identity $0$. For $n \in {\mathbb N}^+$ we write $L^2(G^n)$ for the complex inner product space of functions $f : G^n \to {\mathbb C}$, with inner product $\langle f, g \rangle = \mathop{\bf E}_{{\boldsymbol{x}} \sim G^n}[f({\boldsymbol{x}})\overline{g({\boldsymbol{x}})}].$ Here and throughout this section ${\boldsymbol{x}} \sim G^n$ denotes that ${\boldsymbol{x}}$ is drawn from the uniform distribution on $G^n$.

Everything we have done in this chapter for the real inner product space $L^2(\Omega^n, \pi^{\otimes n})$ generalizes easily to the case of a complex inner product; the main difference is that Plancherel’s Theorem becomes $\langle f, g \rangle = \sum_{\alpha \in {\mathbb N}^n_{< m}} \widehat{f}(\alpha) \overline{\widehat{g}(\alpha)} = \sum_{S \subseteq [n]} \langle f^{=S}, g^{=S} \rangle.$ See the exercises for more.

A natural Fourier basis for $L^2(G)$ comes from a natural family of functions $G \to {\mathbb C}$, namely the characters. These are defined to be the group homomorphisms from $G$ to ${\mathbb C}^\times$, where ${\mathbb C}^\times$ is the abelian group of nonzero complex numbers under multiplication.

Definition 51 A character of the (finite) group $G$ is a function $\chi : G \to {\mathbb C}^\times$ which is a homomorphism; i.e., satisfies $\chi(x + y) = \chi(x) \chi(y)$. Since $G$ is finite there is some $m \in {\mathbb N}^+$ such that $0 = x + x + \cdots + x$ ($m$ times) for each $x \in G$. Thus $1 = \chi(0) = \chi(x)^m$, meaning the range of $\chi$ is in fact contained in the $m$th roots of unity. In particular, $|\chi(x)| = 1$ for all $x \in G$.

We have the following easy facts:

Fact 52 If $\chi$ and $\phi$ are characters of $G$ then so are $\overline{\chi}$ and $\phi \cdot \chi$.

Proposition 53 Let $\chi$ be a character of $G$. Then either $\chi \equiv 1$ or $\mathop{\bf E}[\chi] = 0$.

Proof: If $\chi \not \equiv 1$, pick some $y \in G$ such that $\chi(y) \neq 1$. Since ${\boldsymbol{x}} + y$ is uniformly distributed on $G$ when ${\boldsymbol{x}} \sim G$, $\mathop{\bf E}_{{\boldsymbol{x}} \sim G}[\chi({\boldsymbol{x}})] = \mathop{\bf E}_{{\boldsymbol{x}} \sim G}[\chi({\boldsymbol{x}}+y)] = \mathop{\bf E}_{{\boldsymbol{x}} \sim G}[\chi({\boldsymbol{x}})\chi(y)] = \chi(y)\mathop{\bf E}_{{\boldsymbol{x}} \sim G}[\chi({\boldsymbol{x}})].$ Since $\chi(y) \neq 1$ it follow that $\mathop{\bf E}[\chi({\boldsymbol{x}})]$ must be $0$. $\Box$

Proposition 54 The set of all characters of $G$ is orthonormal. (As a consequence, $G$ has at most $\dim(L^2(G)) = |G|$ characters.)

Proof: First, if $\chi$ is a character then $\langle \chi, \chi \rangle = \mathop{\bf E}[|\chi|^2] = 1$ because $|\chi| \equiv 1$. Next, if $\phi$ is another character distinct from $\chi$ then $\langle \phi, \chi \rangle = \mathop{\bf E}[\phi \cdot \overline{\chi}]$. But $\phi \cdot \overline{\chi}$ is a character by Fact 52, and $\phi \cdot \overline{\chi} = \phi/\chi \not \equiv 1$ because $\phi$ and $\chi$ are distinct; here we used $\overline{\chi} = 1/\chi$ because $|\chi| \equiv 1$. Thus $\langle \phi, \chi \rangle = 0$ by Proposition 53. $\Box$

As we will see next, $G$ in fact has exactly $|G|$ characters. It thus follows from Proposition 54 that the set of all characters (which includes the constant $1$ function) constitutes a Fourier basis for $L^2(G)$.

To check that each finite abelian group $G$ has $|G|$ distinct characters, we begin with the case of a cyclic group, ${\mathbb Z}_m$ for some $m$. In this case we know that every character’s range will be contained in the $m$th roots of unity.

Definition 55 Fix an integer $m \geq 2$ and write $\omega$ for the $m$th root of unity $\exp(2\pi i/m)$. For $0 \leq j < m$, we define $\chi_j : {\mathbb Z}_m \to {\mathbb C}$ by $\chi_j(x) = \omega^{jx}$. It is easy to see that these are distinct characters of ${\mathbb Z}_m$.

Thus the functions $\chi_0 \equiv 1, \chi_1, \dots, \chi_{m-1}$ form a Fourier basis for $L^2({\mathbb Z}_m)$. Furthermore, Proposition 13 tells us that we can get a Fourier basis for $L^2({\mathbb Z}_m^n)$ by taking all products of these functions.

Definition 56 Continuing Definition 55, let $n \in {\mathbb N}^+$. For $\alpha \in {\mathbb N}_{< m}^n$ we define $\chi_\alpha : {\mathbb Z}_m^n \to {\mathbb C}$ by $\chi_{\alpha}(x) = \prod_{j =1}^n \chi_{\alpha_j}(x_j).$ These functions are easily seen to be (all of the) characters of the group ${\mathbb Z}_m^n$, and they constitute a Fourier basis of $L^2({\mathbb Z}_m^n)$.

Most generally, by the Fundamental Theorem of Finitely Generated Abelian Groups we know that any finite abelian $G$ is a direct product of cyclic groups of prime-power order. In the exercises you are asked to check that you get all of the characters of $G$ — and hence a Fourier basis for $L^2(G)$ — by taking all products of the associated cyclic groups’ characters. In the remainder of the section we mostly stick to groups of the form ${\mathbb Z}_m^n$ for simplicity.

Returning to the characters $\chi_0, \dots, \chi_{m-1}$ from Definition 55, it is easy to see (using $\omega^m = 1$) that they satisfy $\chi_{j} \cdot \chi_{j’} = \chi_{j + j’ \pmod m}$ and also $1/\chi_{j} = \overline{\chi_j} = \chi_{-j \pmod m}$. Thus the characters themselves form a group under multiplication, isomorphic to ${\mathbb Z}_m$. As in Chapter 3.2, we index them using the notation $\widehat{{\mathbb Z}_m}$. More generally, indexing the Fourier basis/characters of $L^2({\mathbb Z}_m^n)$ by $\widehat{{\mathbb Z}_m^n}$ instead of multi-indices, we have:

Fact 57 The characters $(\chi_{\alpha})_{\alpha \in \widehat{{\mathbb Z}_m^n}}$ of ${\mathbb Z}_m^n$ form a group under multiplication:

• $\chi_{\alpha} \cdot \chi_{\beta} = \chi_{\alpha + \beta}$,
• $1/\chi_{\alpha} = \overline{\chi_{\alpha}} = \chi_{-\alpha}$.

As mentioned, the salient feature of $L^2(G)$ distinguishing it from other spaces $L^2(\Omega, \pi)$ is that there is a notion of addition on the domain. This means that convolution plays a major role in its analysis. We generalize the definition from the setting of ${\mathbb F}_2^n$:

Definition 58 Let $f, g \in L^2(G)$. Their convolution is the function $f * g \in L^2(G)$ defined by \begin{equation*} (f * g)(x) = \mathop{\bf E}_{\boldsymbol{y} \sim G}[f(\boldsymbol{y}) g(x - \boldsymbol{y})] = \mathop{\bf E}_{\boldsymbol{y} \sim G}[f(x-\boldsymbol{y})g(\boldsymbol{y})]. \end{equation*}

In the exercises you are asked to check that convolution is associative and commutative, and that the following generalization of Theorem 1.28 holds:

Theorem 59 Let $f, g \in L^2(G)$. Then $\widehat{f * g}(\alpha) = \widehat{f}(\alpha) \widehat{g}(\alpha)$.

We conclude this section by mentioning vector space domains. When doing Fourier analysis over the group ${\mathbb Z}_m^n$, it is natural for subgroups to arise. Things are simplest when the only subgroups of ${\mathbb Z}_m$ are the trivial ones, $\{0\}$ and ${\mathbb Z}_m$; in this case, all subgroups will be isomorphic to ${\mathbb Z}_m^{n’}$ for some $n’ \leq n$. Of course, this simple situation occurs if and only if $m$ is equal to some prime $p$. In that case, ${\mathbb Z}_p$ can be thought of as a field, ${\mathbb Z}_p^n$ as an $n$-dimensional vector space over this field, and its subgroups as subspaces. We use the notation ${\mathbb F}_p^n$ in this setting and write $\widehat{{\mathbb F}_p^n}$ to index the Fourier basis/characters; this generalizes the notation introduced for $p = 2$ in Chapter 3.2. Indeed, all of the notions from Chapters 3.2 and 3.3 regarding affine subspaces and restrictions thereto generalize easily to $L^2({\mathbb F}_p^n)$.

## §8.4: $p$-biased analysis

Perhaps the most common generalized domain in analysis of boolean functions is the case of the hypercube with “biased” bits.
Continue reading §8.4: $p$-biased analysis

## §8.3: Orthogonal decomposition

In this section we describe a basis-free kind of “Fourier expansion” for functions on general product domains. We will refer to it as the orthogonal decomposition of $f \in L^2(\Omega^n, \pi^{\otimes n})$ though it goes by several other names in the literature: e.g., Hoeffding, Efron–Stein, or ANOVA decomposition.
Continue reading §8.3: Orthogonal decomposition

## §8.2: Generalized Fourier formulas

In this section we will revisit a number of combinatorial/probabilistic notions and show that for functions $f \in L^2(\Omega^n, \pi^{\otimes n})$, these notions have familiar Fourier formulas which don’t depend on the Fourier basis.
Continue reading §8.2: Generalized Fourier formulas

## §8.1: Fourier bases for product spaces

We will now begin to discuss functions on (finite) product probability spaces.
Continue reading §8.1: Fourier bases for product spaces

## Chapter 8: Generalized domains

So far we have studied functions $f : \{0,1\}^n \to {\mathbb R}$. What about, say, $f : \{0,1,2\}^n \to {\mathbb R}$? In fact, very little of what we’ve done so far depends on the domain being $\{0,1\}^n$; what it has mostly depended on is our viewing the domain as a product probability distribution. Indeed, much of analysis of boolean functions carries over to the case of functions $f : \Omega_1 \times \cdots \times \Omega_n \to {\mathbb R}$ where the domain has a product probability distribution $\pi_1 \otimes \cdots \otimes \pi_n$. There are two main exceptions: the “derivative” operator $\mathrm{D}_i$ does not generalize to the case when $|\Omega_i| > 2$ (though the Laplacian operator $\mathrm{L}_i$ does); and, the important notion of hypercontractivity (introduced in the next chapter) depends strongly on the probability distributions $\pi_i$.

In this chapter we focus on the case where all the $\Omega_i$’s are the same, as are the $\pi_i$’s. (This is just to save on notation; it will be clear that everything we do holds in the more general setting.) Important classic cases include functions on the $p$-biased hypercube (Section 4) and functions on abelian groups (Section 5). For the issue of generalizing the range of functions — e.g., studying functions $f : \{0,1,2\}^n \to \{0,1,2\}$ — see the exercises.

## Hiatus

The last video lecture for my CMU course on Analysis of Boolean Functions has just been posted. Except for responding to comments, the blog will be going on hiatus for a little while. Next semester I’ll post the final chapters of the book; there will be between 4 and 7 of them, depending on how much energy I have.

Happy holidays……..

## CMU online course: Lecture 23 published

The video for Lecture 23 of the online course is available on the course web page.

## CMU online course: Lecture 22 published

The video for Lecture 22 of the online course is available on the course web page.

## Chapter 7 notes

The study of property testing was initiated by Rubinfeld and Sudan [RS96] and significantly expanded by Goldreich, Goldwasser, and Ron [GGR98]; the stricter notion of local testability was introduced (in the context of error-correcting codes) by Friedl and Sudan [FS95]. The first local tester for dictatorship was given by Bellare, Goldreich, and Sudan [BGS95,BGS98] (as in Exercise 8); it was later rediscovered by Parnas, Ron, and Samorodnitsky [PRS01,PRS02]. The relevance of Arrow’s Theorem to testing dictatorship was pointed out by Kalai [Kal02].
Continue reading Chapter 7 notes