The Fourier Transform of Restrictions of Functions on the Slice

Boolean functions, or functions over $\{0,1\}^{n}$, are central to computer science. One tool that has found many uses is Fourier analysis, which involves defining an orthonormal basis separate from the standard basis, but with many useful properties. One such property is that this basis consists of eigenvectors of the Boolean hypercube, the graph whose vertices are $\{0,1\}^{n}$ with an edge between two vectors $u$ and $v$ if they differ in exactly one coordinate. Fourier analysis over the Boolean hypercube has led to many applications, including in learning theory, property testing, pseudorandomness, voting theory, and more. For a more complete treatment, see [O’D14].

In recent years, much attention has been drawn to functions on the slice, $\binom{[n]}{k}=\{v\mid v\in\{0,1\}^{n},\sum_{i=1}^{n}v_{i}=k\}$ or the subset of $\{0,1\}^{n}$ that consists of vectors with exactly $k$ $1$’s for some fixed $k$. Like in the case of the Boolean hypercube, one can also define an orthonormal basis separate from the standard basis, over functions on the slice. In particular, one can consider the eigenvectors of the Johnson graph, the graph whose vertices are elements of the slice, with an edge between two vectors $u$ and $v$ if they differ in exactly two coordinates. Thus, this basis can be seen as an analogue of the Fourier transform, but for the slice.

Such a basis was given explicitly in [Fil16] and [Sri11], and this basis has subsequently found many applications in analogues of major theorems for the Boolean hypercube, but now for the slice. These include Friedgut’s theorem [Fil16], various versions of the invariance principle [FM19, FKMW18], the Kindler-Safra theorem [KK20], and a theorem due to Nisan and Szegedy regarding juntas [FI19]. In this paper, we continue this line of work of proving analogues for the slice.

Fourier analysis on the hypercube has been particularly useful when considering restrictions of functions. In particular, if $f:\{0,1\}^{n}\rightarrow\mathbb{R}$ is a function, and $z\in\{0,1\}^{t}$ for $t\leqslant n$, we let its restriction, $f_{z}:\{0,1\}^{n-t}\rightarrow\mathbb{R}$, be the function defined by $f_{z}(x)=f(x\circ z)$ where $\circ$ denotes concatenation. In particular, one can relate the Fourier coefficients of $f$ with the Fourier coefficients of $f_{z}$.

Recall that the orthonormal basis for the Fourier transform can be indexed by subsets of the set $[n]$. Then for any $t$ and any $S\subseteq[n-t]$,

where $\widehat{f}(S)$ denotes the projection onto the vector indexed by $S$ (see Corollary 3.22 in [O’D14]).

In the case of the slice, one can also define a restriction, where given $f:\binom{[n]}{k}\rightarrow\mathbb{R}$ and $z\in\{0,1\}^{t}$ for $t\leqslant n$, we let $f_{z}:\binom{n-t}{k-|z|}\rightarrow\mathbb{R}$ be defined by $f_{z}(x)=f(x\circ z)$, where $|z|=|\{i:\,z_{i}=1\}|$ denotes the Hamming weight of $z$. If $z$ contains more than $k$ $1$’s, then $f_{z}$ is an empty function. In this work, we show that an identity similar to Eq. (1) holds for the slice.

In the slice, the orthonormal basis for the Fourier transform is now indexed by subsets of $[n]$ with a certain property. Let $\mathcal{H}_{n,\min\{k,n-k\}}$ be the collection of subsets $S=\{s_{1},s_{2},\ldots,s_{i}\}$ of $[n]$ of size at most $k$ such that $s_{j}\geqslant 2j$ for all $j$, when the elements of $S$ are listed in sorted order. Then the vectors in the orthogonal basis from [Fil16] and [Sri11] can be indexed by elements of $\mathcal{H}_{n,\min\{k,n-k\}}$. We note that a vector indexed by the set $S$ in the orthogonal basis for the slice differs significantly from the vector indexed by the same set in the orthogonal basis for the Boolean hypercube.

The main result of this paper is the following theorem, which generalizes Eq. (1) to the slice.

Again, $\widehat{f}(S)$ denotes the projection onto the vector indexed by $S$. For convenience, we will let $\widehat{f}(S)=0$ if $S$ is not a subset in $\mathcal{H}_{n,\min\{k,n-k\}}$ or $f$ is an empty function.

Eq. (1) has many applications, one of which includes the Goldreich-Levin theorem [GL89, KM93]. Informally, this theorem says that if the Fourier coefficients of a function are concentrated on just a few vectors, then the function can be learned efficiently. As an application of Theorem 1.1, we show that a similar theorem applies in the case of the slice, following the Kushilevitz-Mansour algorithm.

Denote by $[n]$ the set $\{1,2,\ldots,n\}$ and by $\binom{[n]}{k}$ the set $\{v\mid v\in\{0,1\}^{n},\sum_{i=1}^{n}v_{i}=k\}$ or the subset of $\{0,1\}^{n}$ that consists of vertices with exactly $k$ $1$’s for some fixed $k$.

Given a string $x\in\{0,1\}^{n}$, denote by $|x|$ the Hamming weight of $x$, that is, $|x|=\sum_{i=1}^{n}x_{i}$.

As stated in the introduction, we denote by $\mathcal{H}_{n,k}$ the set of subsets $S=\{s_{1},s_{2},\ldots,s_{i}\}$ of $[n]$ of size at most $k$ such that $s_{j}\geqslant 2j$ for all $j$, when the elements of $S$ are listed in sorted order. Note that by Bertrand’s ballot problem, there are $\binom{n}{|S|}-\binom{n}{|S|-1}$ sets in $\mathcal{H}_{n,k}$ of size $|S|$, and thus $|\mathcal{H}_{n,k}|=\binom{n}{k}$.

Given a vector $v\in\mathbb{R}^{N}$ we define the $\ell_{p}$-norm by

We define the inner product for two vectors $u,v\in\mathbb{R}^{N}$ to be

It will often be convenient to index vectors by vectors rather than integers, that is, to let $v$ be a vector in $\mathbb{R}^{\binom{[n]}{k}}$ for some $n$ and $k$. It will often be convenient to identify vectors as functions, that is, to represent $v\in\mathbb{R}^{n}$ as $f_{v}:[n]\rightarrow\mathbb{R}$, or $v\in\mathbb{R}^{\binom{[n]}{k}}$ as $f_{v}:{\binom{[n]}{k}}\rightarrow\mathbb{R}$ where in both cases, one obtains $f_{v}$ from $v$ via $f_{v}(x)=v_{x}$.

By the Cauchy-Schwarz inequality, one can relate the $\ell_{1}$-norm of a vector with its $\ell_{2}$-norm as follows.

We denote by $I_{N}$ the $\mathbb{R}^{N\times N}$ identity matrix.

Recall that the Johnson graph is defined by $G=(V,E)$ where $V=\binom{[n]}{k}$ and $E=\left\{(v,u)\mid\sum_{i=1}^{n}|v_{i}-u_{i}|=2\right\}$. Let $A_{n,k}$ be the corresponding adjacency matrix.

In this section we give with proof an orthonormal basis of eigenvectors for the Johnson graph. The claims and theorems in this section will be used in Section 4 to prove Theorem 1.1. We stress that all of the results in this section are known, and can be found in the works of Stanley [Sta88, Sta90], Filmus [Fil16], Srinivasan [Sri11], and Filmus and Lindzey [FL20]. When illustrative, however, we give the proofs of the various statements.

We start by defining a collection of matrices that will help yield the eigenvectors of $A_{n,k}$.

Let $P^{\uparrow}_{n,k}\in\mathbb{R}^{\binom{[n]}{k+1}\times\binom{[n]}{k}}$ be the matrix defined by

Let $P^{\downarrow}_{n,k+1}=(P^{\uparrow}_{n,k})^{*}$.

Let

and

For simplicity, we let $P^{\uparrow}_{n,k,k}=P^{\downarrow}_{n,k,k}=I_{\binom{n}{k}}$.

Let $P^{\vee}_{n,k}=P^{\uparrow}_{n,k-1}P^{\downarrow}_{n,k}$ and $P^{\wedge}=P^{\downarrow}_{n,k+1}P^{\uparrow}_{n,k}$. The following fact shows that $P^{\vee}_{n,k}$ and $P^{\wedge}_{n,k}$ differ only by a multiple of the identity matrix.

Similarly, one can show that $A_{n,k}$ differs from $P^{\vee}_{n,k}$ and $P^{\wedge}_{n,k}$ by a multiple of the identity matrix. Thus, for the rest of this paper, we focus on determining an orthonormal basis of eigenvectors for $P^{\vee}_{n,k}$ and $P^{\wedge}_{n,k}$.

The following claim shows that to determine the eigenvectors of $P^{\vee}_{n,k}$ and $P^{\wedge}_{n,k}$, it is enough to determine the nullspace of $P^{\downarrow}_{n,i}$ for all $i\leqslant k$. This will be under the assumption that $P^{\downarrow}_{n,i}$ has full rank when $i\leqslant n/2$, which we will prove in Claims 3.5 and 3.6.

The following claim shows that if $P^{\downarrow}_{n,i}v=0$, then $P^{\uparrow}_{n,i,k}v=0$ if $k>n-i$. Thus, in the case that $k>n/2$, one only needs to consider the nullspace of $P^{\downarrow}_{n,i}$ for $i\leqslant n-k$. In fact, we will compute $\displaystyle\frac{\left\|P^{\uparrow}_{n,|S|,k}v\right\|_{2}^{2}}{\left\|v\right\|_{2}^{2}}$ when $P^{\downarrow}_{n,i}v=0$, which will be useful in Section 3.2

Note that the assumption that $P^{\downarrow}_{n,i}$ has full-rank when $i\leqslant n/2$ combined with Claims 3.2 and 3.3 yields a subspace of eigenvectors with equal eigenvalue of dimension $\binom{n}{i}-\binom{n}{i-1}$. For a fixed $k$ and summing over all $i$ from $0$ to $\min\{k,n-k\}$, this is $\binom{n}{\min\{k,n-k\}}$ eigenvectors, and thus, this gives a complete basis of eigenvectors.

The following claim shows that to determine an orthogonal basis of eigenvectors of $P^{\vee}_{n,k}$ and $P^{\wedge}_{n,k}$ it is enough to determine an orthogonal basis for the nullspace of $P^{\downarrow}_{n,i}$ for all $i\leqslant\min\{k,n-k\}$. That is, applying $P^{\uparrow}_{n,i^{\prime}}$ to two orthogonal vectors preserves orthogonality. Recall that the eigenvectors of a symmetric matrix with different eigenvalues are orthogonal, and thus it is sufficient to determine an orthogonal basis for the nullspace of $P^{\downarrow}_{n,i}$ for each $i$.

We note that Claims 3.1, 3.2 3.3, and 3.4 can be generalized to sequentially differential posets (of which, the collection of subsets of $[n]$ is an example), as is done in the work of Stanley [Sta88, Sta90].

In this section, we state and prove our main theorem regarding a relationship between the Fourier coefficients of a function on the slice, and the Fourier coefficients of its restrictions.

We start with the following theorem.