#  Hypercontractivity on high dimensional expanders:
Approximate Efron-Stein Decompositions for $\varepsilon$-product spaces

Tom Gur, Noam Lifshitz, Siqi Liu

###### Abstract.

We prove hypercontractive inequalities on high dimensional expanders. As in
the settings of the $p$-biased hypercube, the symmetric group, and the
Grassmann scheme, our inequalities are effective for global functions, which
are functions that are not significantly affected by a restriction of a small
set of coordinates. As applications, we obtain Fourier concentration, small-
set expansion, and Kruskal–Katona theorems for high dimensional expanders. Our
techniques rely on a new approximate Efron–Stein decomposition for high
dimensional link expanders.

Tom Gur, University of Warwick<EMAIL_ADDRESS>supported by the UKRI
Future Leaders Fellowship MR/S031545/1.

Noam Lifshitz, Hebrew University of Jerusalem<EMAIL_ADDRESS>supported in part by ERC advanced grant 834735.

Siqi Liu, UC Berkeley<EMAIL_ADDRESS>
##  1\. Introduction

High-dimensional expanders (HDX) are sparse simplicial complexes with strong
structural properties. More accurately, a simplicial complex $X$ is a
$\epsilon$-HDX (or an $\epsilon$-link expander) if the $1$-skeleton of each
link of the complex $X$ is a spectral expander graph whose second-largest
eigenvalue is bounded by $\epsilon$. In recent years, HDX have received much
attention in theoretical computer science [33, 45, 34, 42, 41, 35, 27],
finding applications in property testing [32, 14, 28], coding theory [13, 10],
statistical physics [3, 7, 2], complexity theory [1, 4, 12, 29], and beyond.
Notably, very recently the study of HDX led to a breakthrough in quantum
computing, breaking the $\sqrt{n}$ distance in quantum LDPC [19], as well as
to a resolution of one of the most important questions in coding theory,
namely, the first construction of $O(1)$-query asymptotically good locally
testable codes [11].

In this work, we focus on analysis of Boolean functions on high dimensional
expanders, whose systematic study was recently initiated by Dikstein et al.
[9]. This continues a long line of investigation of Fourier analysis of
Boolean functions on extended domains beyond the Boolean hypercube, such as
the Boolean slice [44, 20, 25, 24], the Grassmann scheme [15, 39, 18], the
symmetric group [23, 21, 8], the $p$-biased cube [17, 40, 22], and the multi-
slice [26, 6]. The foregoing extended domains arise naturally throughout
theoretical computer science, and indeed, the study of analysis of Boolean
functions on extended domains has recently led to a breakthrough regarding the
unique games conjecture [38, 16, 15, 39].

Hypercontractive inequalities are amongst the most powerful technical tools in
Fourier analysis, yielding a plethora of applications in algorithms,
complexity, learning theory, statistical physics, social choice, and beyond
(see [43] and references therein). Loosely speaking, such statements assert
that functions of low Fourier degree are “well behaved” in terms of their
distribution around their mean. Concretely, in the Boolean hypercube, the
simplest example of a hypercontractive inequality is Bonami’s lemma, which
states that for every function $f\colon\\{0,1\\}^{n}\to\mathbb{{R}}$ of
Fourier degree at most $d$, it holds that
$\|f\|_{4}\leq\sqrt{{3}^{d}}\|f\|_{2}$.

Alas, in the setting of high dimensional expanders, where the domain is not a
product space and the induced measure is biased, general strong
hypercontractivity cannot hold. The heart of the problem is that some highly
local functions, such as dictators (i.e., $f(x)=x_{i}$), provide strong
counterexamples to hypercontractivity. A similar phenomenon also occurs in
several prominent extended domains, such as the $p$-biased cube and the
Grassmann scheme.

Fortunately, as observed in the setting of the $p$-biased cube [36], all of
the aforementioned examples are local, in the sense that a small number of
coordinates can significantly influence the output of the function. This led
to the definition of ‘global’ functions. For Boolean valued functions, these
are functions wherein a small number of coordinates can change the output of
the function only with a negligible probability. For real valued functions,
this is captured by the $2$-norm remaining roughly the same when restricting
O(1) coordinates of the input. More precisely, consider the setting of a
general product measure. Let $\left(V_{i},\mu_{i}\right)$ be probability
spaces, let $V_{S}=\prod_{i\in S}V_{i}$ and equip $V_{S}$ with the product
measure, which we denote by $\mu_{S}.$ Every function $f\in
L^{2}\left(V_{\left[k\right]},\mu\right)$ is equipped with an orthogonal
decomposition $\sum_{S\subseteq\left[n\right]}f^{=S}$ known as the Efron–Stein
decomposition. The function $f^{=S}$ in the Efron–Stein decomposition plays a
similar role to the function $\hat{f}\left(S\right)\chi_{S}$ in the Boolean
cube. Using that analogy we write

$f^{\leq d}=\sum_{\left|S\right|\leq d}f^{=S},$

and $f$ is said to be of degree $d$ if $f=f^{\leq d}$. Keevash et al. [37]
introduced the following notions. The _Laplacians of $f$_ are given by

$L_{S}\left[f\right]=\sum_{T\supseteq
S}\left(-1\right)^{\left|T\right|}f^{=T}.$

For $x\in V_{S}$ the _derivatives_ are given by restricting the laplacians

$D_{S,x}f=L_{S}\left[f\right]\left(x,\cdot\right),$

and the $\left(S,x\right)$_-influence_ of $f$ is defined as

$I_{S,x}\left[f\right]=\|D_{S,x}\left[f\right]\|_{2}^{2}.$

In this setting, a function $f$ is $\left(r,\delta\right)$_-global_ if
$\|f\left(x,\cdot\right)\|_{2,\mu_{\left[n\right]\setminus S}}^{2}\leq\delta$
for each $\left|S\right|\leq r.$ We remark that here, being
$\left(r,\delta\right)$-global for a small $\delta>0$ is, in a sense,
equivalent to having $I_{S,x}\left[f\right]\leq\delta^{\prime}$ for a small
$\delta^{\prime}$ for all $\left|S\right|\leq r$ and all $x$. In fact,
$\delta,\delta^{\prime}$ can be taken to be within a factor of $2^{r}$ of one
another.

In [37], it was shown that if $f\in L^{2}\left(V,\mu\right)$ is of degree $d$,
then the following hypercontractive inequality holds:

(1.1) $\|f\|_{4}^{4}\leq
1000^{d}\sum_{S}\mathbb{E}_{x\sim\mu_{S}}I_{S,x}\left[f\right]^{2}.$

This allowed them to deduce if a function $f$ of degree $d$ is
$\left(d,\delta\right)$_-global_ , then

$\|f\|_{4}^{4}\leq\delta 8000^{d}\|f\|_{2}^{2}.$

Here when setting $\delta=100\|f^{\leq d}\|_{2}^{2}$ one gets the statement
$\|f\|_{4}\leq C^{d}\|f\|_{2},$ which replicates the behavior in the Boolean
cube. Moreover, the statement is useful even for larger values of $\delta$.

In this work, we raise the following question.

> _Does hypercontractivity hold for high dimensional expanders?_

###  1.1. Main results

We answer the question above in the affirmative. Namely, our main contribution
is a hypercontractive inequality for functions on the $k$-faces of an
$\epsilon$-HDX. We denote by $X(k)$ the $k$-faces of a simplicial complex $X$,
and denote by $\mu$ the uniform measure on its $k$-faces. We define the
influences $I_{S,x}^{\leq d}$ and the degree restriction operator
$(\cdot)^{\leq d}$ analogously to their definition on the $p$-biased cube (see
Section 4 for precise definition). We then prove the following
hypercontractive statement for high dimensional expanders in the spirit of
(1.1).

######  Theorem 1.1.

Let $X$ be an $\epsilon$-HDX, and let $f\in L^{2}\left(X(k),\mu\right)$. We
have

$\|f^{\leq d}\|_{4}^{4}\leq 20^{d}\sum_{\left|S\right|\leq
d}\left(4d\right)^{\left|S\right|}\mathbb{E}_{x\sim\mu_{S}}I_{S,x}^{\leq
d}\left[f\right]^{2}+O_{k}\left(\epsilon^{2}\right)\|f\|_{2}^{2}\|f\|_{\infty}^{2}.$

In the setting of $\epsilon$-HDX, we say that a function $f$ is
$\left(d,\delta\right)$-global if for each $\left|S\right|\leq d$, we have
$\|f\left(x,\cdot\right)\|_{L^{2}\left(V_{x},\mu_{x}\right)}\leq\delta.$ We
show that we can bound the infinity norm of global functions and obtain the
following strong hypercontractive inequality for global functions on
$\epsilon$-HDX.

######  Corollary 1.2.

For each $\zeta,d,k>0,$ there exists
$\epsilon_{0}=\epsilon_{0}\left(\zeta,k,d\right),\delta_{0}=\delta_{0}\left(\zeta,d\right)$,
such that the following holds. Let
$\epsilon\leq\epsilon_{0},\delta\leq\delta_{0}$, let $X$ be an $\epsilon$-HDX,
and let $f\in L^{2}\left(X(k),\mu\right)$. If $f$ is
$\left(d,\delta\right)$-global, then we have

$\|f^{\leq d}\|_{4}^{4}\leq\zeta\|f\|_{2}^{2}.$

We remark that, in fact, we prove our results in a slightly more general
setting, to which we refer as $\epsilon$-product measures. See Section 7 for
details.

###  1.2. Applications

As corollaries of our hypercontractive inequality for high dimensional
expanders, we obtain several applications, which we discuss below. See Section
8 for more details.

####  1.2.1. Fourier spectrum concentration theorem

Fourier concentration results are widely useful in complexity theory and
learning theory. Our first application is a Fourier concentration theorem for
HDX. Namely, the following theorem shows that global Boolean functions on
$\epsilon$-HDX are concentrated on the high degrees, in the sense that the
$2$-norm of the restriction of a function to its low-degree coefficients only
constitutes a tiny fraction of its total $2$-norm.

######  Theorem 1.3.

For each $\zeta,d,k>0,$ there exists
$\epsilon_{0}=\epsilon_{0}\left(\zeta,k,d\right),\delta_{0}=\delta_{0}\left(\zeta,d\right)$,
such that the following holds. Let
$\epsilon\leq\epsilon_{0},\delta\leq\delta_{0}$, let $X$ be an $\epsilon$-HDX,
and let $f\colon X(k)\to\left\\{0,1\right\\}$ be
$\left(d,\delta\right)$-global. Then

$\|f^{\leq d}\|_{2}^{2}\leq\zeta\|f\|_{2}^{2}.$

####  1.2.2. Small set expansion theorem

Small set expansion is a fundamental property that is prevalent in
combinatorics and complexity theory. In the setting of the $\rho$-noisy
Boolean hypercube, the small set expansion theorem of Kahn, Kalai, and Linial
[31] gives an upper bound on $\mathrm{{Stab}_{\rho}}(1_{A})=\langle
1_{A},T_{\rho}1_{A}\rangle$ for indicators $1_{A}$ of small sets $A$. The
noise stability $\mathrm{{Stab}_{\rho}}(1_{A})$ captures the probability that
a random edge $\left(x,y\right)$ of the $\rho$-noisy hypercube has both its
endpoints in $A$. Hence, an inequality of the form
$\mathrm{{Stab}_{\rho}}(1_{A})\leq\zeta\|1_{A}\|_{2}^{2}$ for an arbitrarily
small $\zeta$ and sufficiently small $A$ implies that that small sets are
expanding in the sense that the random walk makes you leave them with
probability $\geq 1-\zeta$. Our second application is a small set expansion
theorem for global functions on $\epsilon$-HDX, captured via bounding the
natural noise operator in this setting. Let $\rho\in\left(0,1\right)$ be a
noise-rate parameter. The noise operator is given by

$\mathrm{T}_{\rho}f\left(x\right):=\sum_{S\subseteq\left[k\right]}\rho^{\left|S\right|}\left(1-\rho\right)^{k-\left|S\right|}\mathbb{E}_{y\sim\mu}\left[f\left(y\right)|y_{S}=x_{S}\right].$

In other words, $\mathrm{T}_{\rho}$ corresponds to the random walk that starts
with $x$ chooses a $\rho$-biased random $S\subseteq\left[k\right]$, keeps
$x_{S}$, and re-randomises $x$ given $x_{S}$. Our small set expansion theorem
tells us that if we start with a small subset $A\subseteq X\left(k\right)$ and
we apply one step of the random walk, then we leave $A$ with probability
$0.99$.

######  Theorem 1.4.

For each $\zeta,d,k>0,$ there exists
$\epsilon_{0}=\epsilon_{0}\left(\zeta,k,d\right),\delta_{0}=\delta_{0}\left(\zeta,d\right)$,
such that the following holds. Let
$\epsilon\leq\epsilon_{0},\delta\leq\delta_{0}$, and let $X$ be an
$\epsilon$-HDX. If $f\colon V_{\left[k\right]}\to\left\\{0,1\right\\}$ is
$\left(d,\delta\right)$-global, then

$\|\mathrm{T}_{\rho}f\|_{2}^{2}\leq\zeta\|f\|_{2}^{2}.$

####  1.2.3. Kruskal–Katona theorem

Our last application is an analogue of the Kruskal–Katona theorem in the
setting of high dimensional expanders. The Kruskal-Katona theorem is a
fundamental and widely-applied result in extremal combinatorics, which gives a
lower bound on the size of the lower shadow $\partial\left(A\right)$ of a
$k$-uniform hypergraph $A$ on $n$ vertices. The _lower shadow_ is defined to
be the family of all $(k-1)$-sets that are contained in an edge of $A$. More
generally, if $A\subseteq X\left(k\right)$, then we similarly let
$\partial\left(A\right)$ be the family of all $k-1$-faces that are contained
in a $k$-face of $A$.

Filmus et al. [23] used their hypercontractivity theorem to prove a stability
result for the Kruskal–Katona theorem. We prove a similar stability result for
$\epsilon$-HDX.

######  Theorem 1.5.

Let $X$ be an $\epsilon$-HDX, for a sufficiently small $\epsilon>0$. Let
$\delta\leq\left(200d\right)^{-d},$ and let $A\subseteq X\left(k-1\right)$ be
$\left(d,\delta\right)$-global. Then

$\mu\left(\partial\left(A\right)\right)\geq\mu\left(A\right)\left(1+\frac{d}{2k}\right).$

###  1.3. Techniques

Conceptually, one can view the theory of expanders and pseudorandom graphs in
the following perspective: Given a pseudorandom regular graph
$G=\left(V,E\right)$ and $\left(x,y\right)\sim E$, the goal is to show that
$x,y$ behave similarly to independent random variables $x,y\sim V$, i.e., as
an approximation of a product space.

In the theory of high dimensional expanders, we are given a distribution $\mu$
on $(k+1)$-tuples by choosing a random $k$-face
$\left(x_{1},\ldots,x_{k+1}\right)$ of a sparse simplicial complex, and the
goal is again to show that the variables $\\{x_{i}\\}$ approximately behave as
though they were independent. Thus, our main objective is to generalise
results from the product space setting, where the $x_{i}$’s are independent,
to the setting of HDX, where we only have local spectral information about the
links. However, such a generalisation yields significant challenges.

One of the fundamental tools for studying the product space setting is the
aforementioned Efron–Stein decomposition. Its role in the analysis of product
spaces is that it allows us to easily generalise techniques from the Boolean
cube by replacing the Fourier expression $\hat{f}\left(S\right)\chi_{S}$ with
the function $f^{=S}.$

Our high-level proof strategy is to develop new Efron–Stein decompositions for
HDX. We show that despite the more involved setting, and despite the fact that
we only have mere local spectral information, we can still obtain similar
structural properties as in product spaces. We now list a few of the
challenges that we are facing, which require fundamentally new ideas and
techniques.

Dikstein et al. [9] gave a decomposition of the form $f=\sum_{d=0}^{k}f^{=d}$.
We provide a new decomposition
$\left\\{f^{=S}\right\\}_{S\subseteq\left[k\right]}$ such that
$f=\sum_{S\subseteq\left[k\right]}f^{=S},$ and despite not having
orthogonality, we can still show that the inner product $\left\langle
f^{=S},f^{=T}\right\rangle$ is negligible compared to $\|f\|_{2}^{2}.$ This
allows us to generalise the Laplacians, derivatives and influences, but we
have to deal with the following problems:

  * •

Let $\mathcal{F}\subseteq\left[k\right]$ be a small set. We would like to say
that $g=\sum_{S\in\mathcal{F}}f^{=S}$ is supported on $\mathcal{F},$ but we
have no way of knowing that looking at
$\left\\{g^{=S}\right\\}_{S\subseteq\left[k\right]},$ as $g^{=S}$ may be
nonzero even for $S\notin\mathcal{F}.$ This leads to the problem of how to
even define the degree of a function. We would like to say that $f^{\leq
d}:=\sum_{\left|S\right|\leq d}f^{=S}$ is of degree at most $d$, and that $f$
is of degree $d$ if $f=f^{\leq d}$. Alas, according to this definition the
function $f^{\leq d}$ is not of degree $d$.

  * •

We can and do define the derivatives $D_{S,x}$ to be the restrictions of the
Laplacians. In the product case the derivatives decrease the degree by
$\left|S\right|$, and this is a very desirable property as our proof goes by
induction on $d$. However, this is no longer true in the HDX setting.

  * •

We may define the influences by taking $2$-norms of the derivatives. However,
now it is no longer true that having small influences is equivalent to being
global. This leads us to the following problem which is the source for all of
the difficulty.

  * •

The spectral information tells us that HDX should behave similarly to product
spaces with respect to the $L^{2}$-norm. However, we care about $L_{4}$
information when bounding $\|f\|_{4}$, and we deal with
$L_{\infty}$-hypothesis as the globalness notion is about all the
restrictions. There is no reason for HDX to behave well with respect to
$L_{4}$ and even more so for $L_{\infty}.$

At first, the above, and especially the last point, seem as fundamental
barriers to this approach.

Nevertheless, we overcome this barrier by developing an alternative notion,
which we call the _approximate Efron–Stein decomposition_. Our new notion has
the following properties that fix all of the above problems.

  * •

If $\left\\{f_{S}\right\\}_{S\subseteq\left[k\right]}$ is an approximate
Efron–Stein decomposition, then crucially,
$\left\\{f_{S}\right\\}_{S\in\mathcal{F}}$ is an approximate Efron–Stein
decomposition for $\sum_{S\in\mathcal{F}}f^{=S}$.

  * •

If $f$ is approximately of degree $d$, in the sense that
$\left\\{f_{S}\right\\}$ is an approximate Efron-Stein decomposition for $f$,
then the derivative $D_{S,x}\left[f\right]$ may be $L_{4}$-approximated by
$D_{S,x}\left[f\right]^{\leq d-\left|S\right|}$ .

  * •

We find a way of proving an inequality of the form

$\mathbb{E}_{x\sim\mu_{S}}I_{S,x}^{2}\left[f\right]\leq\delta\mathbb{E}_{x\sim\mu_{S}}\left[I_{S,x}\right],$

without having the traditional hypothesis
$\max_{x}I_{S,x}\left[f\right]\leq\delta$ at our disposal.

  * •

We show that we may move freely between different approximate Efron–Stein
decomposition up to a small $L_{4}$-norm error term.

We believe that our approximate Efron–Stein decomposition provides the desired
comfortable platform for analysing functions on HDX in the same way one would
analyze a product space.

See Section 4 for a detailed exposition of our approximate Efron–Stein
decomposition, and see Section 5 for a more detailed proof overview of our
main hypercontractivity results, which build on the aforementioned
decomposition.

###  1.4. Related work

Simultaneously and independently to this work, Bafna, Hopkins, Kaufman, and
Lovett [5] also obtained hypercontractive inequalities for high dimensional
expanders. We remark that while the main hypercontractive inequalities in both
papers achieve essentially the same parameters, the techniques are completely
different. Namely, in [5] the proof strategy follows the approach of analogous
results in the setting of the Grassmann graph, whereas our approach
generalises Efron–Stein decompositions and hypercontractivity for general
product spaces. We further note that our approximate Efron–Stein decomposition
extends approximate Fourier decompositions that appeared in several recent
works [34, 35, 9, 1, 30].

###  1.5. Organisation

The rest of the paper is organised as follows. We start in Section 2, where we
recall the notions of hypercontractivity and globalness in general product
spaces, as well as provide an alternative proof of a slightly weaker
hypercontractive inequality that is more amenable for generalisation to non-
product spaces. In Section 3, we present the framework of $\epsilon$-product
spaces, of which high dimensional expanders are a special case, and we also
define key operators in this setting and show some basic properties they
satisfy. Next, in Section 4, which is introducing a new approximate
Efron–Stein decomposition and developing a framework for proving
hypercontractivity results using this decomposition. Then, in Section 5, we
give a detailed proof overview of our hypercontractive inequalities for high
dimensional expanders, which build on the foregoing framework. In Section 6,
we define the notions of laplacians, derivatives and influences in the setting
of $\epsilon$-measures, give bounded approximated Efron–Stein decompositions
related to the Laplacians, define globalness, and show that it implies small
influences.. Then, we provide the full proof of our main hypercontractivity
results in Section 7. Finally, in Section 8, we show how to derive the
applications from our hypercontractive inequalities.

### Acknowledgments

We are grateful to Alessandro Chiesa for participating in early stages of this
research. We thank Yuval Filmus and Dor Minzer for insightful discussions. We
further thank Yuval Filmus for insightful comments on a previous version of
this work.

##  2\. Recalling globalness and hypercontractivity in the product space
setting

We begin by recalling the Efron–Stein decomposition, as well as derivatives
and Laplacians in the setting of general product spaces, and state the
hypercontractivity inequalities for product spaces that were shown in [37]. We
then give a proof, inspired by [18], of a slightly weaker hypercontractivity
inequality that we will later generalise to approximate product spaces.

###  2.1. Efron-Stein decomposition

Let $\left(V_{1},\mu_{1}\right),\ldots,\left(V_{k},\mu_{k}\right)$ be a
probability space. Let $\mu$ be the corresponding product measure
$\mu_{1}\otimes\cdots\otimes\mu_{k}$. For a set $S\subseteq\left[k\right]$, we
write $V_{S}=\prod_{i\in S}V_{i},$ and we write $\text{$\mu_{S}$ for the
product measure }\,\mu_{S}=\bigotimes_{i\in S}\mu_{i}.$ The _Efron–Stein
decomposition_ is a decomposition of
$L^{2}\left(V_{\left[k\right]},\mu\right)$ into $2^{k}$ orthogonal spaces
$\left\\{W_{S}\right\\}_{S\subseteq\left[k\right]}.$ Every function $f\in
L^{2}\left(V_{\left[k\right]},\mu\right)$ can then be decomposed as
$f=\sum_{S\subseteq\left[k\right]}f^{=S},$ where $f^{=S}$ is the projection of
$f$ to $W_{S}.$ The Efron–Stein decomposition is characterised by the
orthogonality of $\left\\{W_{S}\right\\}$, the fact that
$\sum_{S}W_{S}=L^{2}\left(V,\mu\right)$, and the fact that the space $W_{S}$
is composed of functions depending only on $S.$

The functions $f^{=S}$ also have an explicit formula for $x\in V_{S}$, where
we denote

$A_{S}f\left(x\right)=\mathbb{E}_{y\sim\left(V_{\overline{S}},\mu_{\overline{S}}\right)}\left[f\left(x,y\right)\right],$

where $\bar{{S}}=[k]\setminus S$. We then write

$f^{=S}=\sum_{T\subseteq S}\left(-1\right)^{\left|S\setminus T\right|}A_{T}f.$

The function $A_{S}\left[f\right]$ then has the following neat Efron–Stein
decomposition

$A_{S}\left[f\right]=\sum_{T\subseteq S}f^{=T}.$

See [43, Chapter 8] for more details.

###  2.2. Notations

We write $a=b\pm\epsilon$ to indicate that
$a\in\left(b-\epsilon,b+\epsilon\right).$ We use $a\leq O\left(b\right)$ to
denote that the inequality holds up to an absolute constant, and $a\leq
O_{k}\left(b\right)$ to denote that the inequality holds up to a constant only
depending on $k$.

###  2.3. Derivatives and Laplacians

Let $\mu=\mu_{1}\otimes\cdots\otimes\mu_{k}$ be a product measure. Let $f\in
L^{2}\left(V_{\left[k\right]},\mu\right),$ $S\subseteq\left[n\right]$. The
_Laplacian_ is given by the formula

$L_{S}\left[f\right]=\sum_{T\supseteq S}f^{=T}=\sum_{T\subseteq
S}\left(-1\right)^{\left|T\right|}A_{\left[k\right]\setminus T}f.$

For $S\subseteq\left[n\right]$ and $x\in V_{S}$ the _derivative_ $D_{S,x}\in
L^{2}\left(V_{\overline{S}},\mu_{\overline{S}}\right)$ is defined by

$D_{S,x}f=L_{S}\left[f\right]\left(x,\cdot\right).$

For convenience, we also write $D_{\varnothing}f=f.$ The
$\left(S,x\right)$_-influence_ of $f$ is defined as

$I_{S,x}\left[f\right]=\|D_{S,x}\left[f\right]\|_{2}^{2}.$

This includes the case $S=\varnothing$, where we have
$I_{\varnothing}\left[f\right]:=\|f\|_{2}^{2}.$

We now state a few facts from [37] that we generalise. The following lemma,
which appears in [37], shows that the notion of small influences corresponds
to small $2$-norms of the restriction of $f$.

######  Lemma 2.1.

Suppose that $I_{S,x}\left[f\right]\leq\delta$ for each set $S$ of size at
most $r.$ Then $\|f\left(x,\cdot\right)\|_{2,\mu_{\left[n\right]\setminus
S}}^{2}\leq\delta 4^{r}$ for each $S$ and $x\in V_{S}$. Conversely, if
$\|f\left(x,\cdot\right)\|_{2,\mu_{\left[n\right]\setminus S}}^{2}\leq\delta$
for each $\left|S\right|\leq r$ and $x\in V_{S}$, then
$I_{S,x}\left[f\right]\leq\delta 4^{r}$ for each $S$ of size at most $r$ and
$x\in V_{S}.$

For the above reason they gave the following definition.

######  Definition 2.2.

A function $f$ is said to be $\left(r,\delta\right)$_-global_ if
$I_{S,x}\left[f\right]\leq\delta$ for each $\left|S\right|\leq r.$

The _degree_ of a function is the largest $S$, such that $f^{=S}\neq 0$. The
derivatives decrease the degrees for the following reason.

######  Lemma 2.3.

$D_{S,x}\left[f^{=T}\right]$ is $0$ unless $S\subseteq T$, and if $S\subseteq
T$, then

$D_{S,x}\left[f^{=T}\right]\in W^{T\setminus S}.$

Consequently, if $f=\sum_{\left|S\right|\leq d}f^{=S}$ is of degree $d$, then
$D_{S,x}\left[f\right]$ is of degree $d-\left|S\right|.$

###  2.4. Hypercontractivity

The following result is by [37].

######  Theorem 2.4.

If $f\in L^{2}\left(V,\mu\right)$ is of degree $d$, then

$\|f\|_{4}^{4}\leq 1000^{d}\sum_{S}\mathbb{E}_{x}I_{S,x}\left[f\right]^{2}.$

To show the implication of the theorem for global functions they use the
following inequality.

######  Lemma 2.5.

$\sum_{S}\mathbb{E}_{x}I_{S,x}\left[f\right]\leq 2^{d}\|f\|_{2}^{2}.$

###### Proof.

The right hand side is equal to

$\sum_{S}\|L_{S}\left[f\right]\|_{2}^{2}=\sum_{S}\sum_{T\supseteq
S,\left|T\right|\leq d}\|f^{=T}\|_{2}^{2}\leq
2^{d}\sum_{T}\|f^{=T}\|_{2}^{2}=2^{d}\|f\|_{2}^{2}.$

∎

Combining Theorem 2.4 and Lemma 2.5, we obtain the following corollary.

######  Corollary 2.6.

If $f$ of degree $d$ is $\left(d,\delta\right)$-global. Then $\|f^{\leq
d}\|_{4}^{4}\leq\delta 2000^{d}\|f\|_{2}^{2}.$

###### Proof.

We have

$\displaystyle\|f^{\leq d}\|_{4}^{4}$ $\displaystyle\leq
1000^{d}\sum_{S\subseteq\left[n\right]}\mathbb{E}_{x\sim\mu_{S}}\|I_{S,x}\left[f\right]\|_{2}^{4}$
$\displaystyle\leq\delta
1000^{d}\sum_{S}\mathbb{E}_{x\sim\mu_{S}}\|I_{S,x}\left[f\right]\|_{2}^{2}$
$\displaystyle\leq\delta 2000^{d}\|f\|_{2}^{2}.$

∎

###  2.5. An alternative proof of hypercontractivity on product spaces

We give an alternative proof of the following slightly weaker version of
Theorem 2.4. The proof is inspired by a future work by Ellis, Kindler, and the
second author [18], who show that the same idea works in the Grassmann
setting. In this paper we show that it generalises to HDX as well.

######  Theorem 2.7.

Let $f\in L^{2}\left(V,\mu\right)$ be of degree $d.$ Then

$\|f\|_{4}^{4}\leq 2\cdot 9^{d}\sum_{\left|T\right|\leq
d}\left(9d\right)^{\left|T\right|}\mathbb{E}_{x}\left[I_{S,x}\left[f\right]^{2}\right].$

####  2.5.1. Proof overview.

Before providing the full proof, we first describe the high-level approach for
proving Theorem 2.7. The strategy is to first show a lemma that gives the
following bound

(2.1) $\|f\|_{4}^{4}\leq
C^{d}\|f\|_{2}^{4}+\sum_{S\subseteq\left[n\right]}\left(4d\right)^{\left|S\right|}\|L_{S}\left[f\right]\|_{4}^{4},$

for a constant $C$. Using this lemma, we can give an inductive proof by first
noting that
$\|L_{S}\left[f\right]\|_{4}^{4}=\mathbb{E}_{x}\|D_{S,x}\|_{4}^{4}$, and then
applying induction using the fact that $D_{S,x}$ is of degree
$d-\left|S\right|$. Finally, using the fact that $D_{S,x}D_{T,y}=D_{S\cup
T,\left(x,y\right)}$, we can get our desired hypercontractive statement.

Hence, the key step is to prove the aforementioned lemma. To this end, we
first use the fact that

$\mathbb{E}\left[f^{4}\right]=\sum_{S}\|\left(f^{2}\right)^{=S}\|_{2}^{2}.$

We then expand the summands of $\left(f^{2}\right)^{=S}$ as sums of terms of
the form $\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}.$ Next, we note that the
nonzero terms either satisfy $T_{1}\cap T_{2}\cap S\neq\varnothing$ or satisfy
$T_{1}\Delta T_{2}=S$. Terms of the first kind are cancelled out by
$L_{i}\left[f\right]^{4}$ for an $i\in T_{1}\cap T_{2}\cap S$ on the right
hand side of (2.1). (The terms $\|L_{S}\left[f\right]\|_{4}^{4}$ appear
because of over counting, which we resolve by inclusion exclusion.) Terms of
the latter kind correspond to the situation in the Boolean cube where
$f^{=T}=\hat{f}\left(T\right)\chi_{T}$ and $\chi_{T}\chi_{S}=\chi_{T\Delta
S}.$ We then upper bound $\|\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}\|_{2}$ by
$\|f^{=T_{1}}\|_{2}\|f^{=T_{2}}\|_{2}$. This allows us to translate the
problem of upper bounding the terms of the first kind to the problem of upper
bounding the $4$-norm of a low degree function on the Boolean cube. Namely,
the function

$\sum_{\left|T\right|\leq d}\|f^{=T}\|_{2}\chi_{T}.$

Finally, we use hypercontractivity to upper bound the $4$-norm by its
$2$-norm, which is equal to the $2$-norm of $f$. This concludes the proof
overview.

####  2.5.2. Proof of hypercontractivity on product spaces

We now give a formal proof of Theorem 2.7. We shall first need the following
key lemma, which admits the inductive approach.

######  Lemma 2.8.

Let $f\in L^{2}\left(V,\mu\right)$ be of degree $d.$ Then

$\frac{1}{2}\|f\|_{4}^{4}\leq
9{}^{d}\|f\|_{2}^{4}+\sum_{T\neq\varnothing}\left(4d\right)^{\left|T\right|}\|L_{T}\left[f\right]\|_{4}^{4}.$

We are now ready to prove the lemma.

###### Proof of Lemma 2.8.

By Parseval we have

$\|f\|_{4}^{4}=\sum\|\left(f^{2}\right)^{=S}\|_{2}^{2}.$

We bound each term $\|\left(f^{2}\right)^{=S}\|_{2}^{2}$ individually. By
expanding and using the linearity of the $\cdot^{=S}$ operator we have

$\left(f^{2}\right)^{=S}=\sum_{T_{1},T_{2}}\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}.$

We now divide the pairs $\left(T_{1},T_{2}\right)$ into three sums.

  1. (1)

We let $I_{1}$ be the set of pairs $\left(T_{1},T_{2}\right)$ such that
$T_{1}\cap T_{2}\cap S\neq\varnothing.$ If $i$ is in $T_{1}\cap T_{2}\cap S$,
then the summand $\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}$ appears as a summand
when expanding $\left(L_{i}\left[f\right]^{2}\right)^{=S}.$ This explains the
role of the Laplacians in the right hand side.

  2. (2)

We let $I_{2}$ be the set of pairs such that $T_{1}\Delta T_{2}=S.$ These kind
of pairs have a similar behavior to the one in the Boolean cube. There
$f^{=S}=\hat{f}\left(S\right)\chi_{S}$ and

$f^{=S}f^{=T}=\hat{f}\left(S\right)\hat{f}\left(T\right)\chi_{S\Delta T}.$

We show that the contribution from the pairs in $I_{2}$ is $\leq
C^{d}\|f\|_{2}^{2}.$

  3. (3)

We let $I_{3}=\left(T_{1},T_{2}\right)$ such that either $\left(T_{1}\Delta
T_{2}\right)\setminus S\neq\varnothing$ or $S\setminus\left(T_{1}\cup
T_{2}\right)\neq\varnothing$. We show that in this case
$\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}=0.$

It is easy to verify that each pair $\left(T_{1},T_{2}\right)$ belongs to at
least one of the sets $I_{1},I_{2},I_{3}$. We additionally have $I_{1}\cap
I_{2}=\varnothing.$

### Upper bounding the contribution from $I_{1}$

Let us start by upper bounding the contribution from pairs corresponding to
$I_{1}$. For a nonempty $T\subseteq S$ write $I_{1}\left(T\right)$ for the
pairs $\left(T_{1},T_{2}\right)$, such that $T_{1}\cap T_{2}\supseteq T.$ Then

$\left(L_{T}\left[f\right]^{2}\right)^{=S}=\sum_{\left(T_{1},T_{2}\right)\in
I_{1}\left(T\right)}\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}.$

Now $I_{1}=\bigcup_{i\in S}I_{1}\left(i\right),$ so as a multiset inclusion-
exclusion shows that we have

$I_{1}=\sum_{T\subseteq S}\left(-1\right)^{\left|T\right|-1}\bigcap_{i\in
T}I_{1}\left(i\right)=\sum_{T\subseteq
S}\left(-1\right)^{\left|T\right|-1}I_{1}\left(T\right).$

We therefore have the equality:

$\sum_{\left(T_{1},T_{2}\right)\in
I_{1}}\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}=\sum_{T\subseteq
S,T\neq\varnothing}\left(-1\right)^{\left|T\right|-1}\left(L_{T}\left[f\right]^{2}\right)^{=S}.$

By the triangle inequality and Cauchy–Schwarz, we obtain that

$\displaystyle\|\sum_{\left(T_{1},T_{2}\right)\in
I_{1}}\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}\|_{2}^{2}$
$\displaystyle\leq\left(\sum_{i=1}^{\left|S\right|}\binom{\left|S\right|}{i}\left(4\left|S\right|\right)^{-i}\right)\left(\sum_{T\subseteq
S}\left(4\left|S\right|\right)^{\left|T\right|}\|\left(L_{T}\left[f\right]^{2}\right)^{=S}\|_{2}^{2}\right)$
$\displaystyle\leq\sum_{T\subseteq
S}\left(4\left|S\right|\right)^{\left|T\right|}\|\left(L_{T}\left[f\right]^{2}\right)^{=S}\|_{2}^{2}.$

Summing over all $S$ we have

$\sum_{S}\|\sum_{\left(T_{1},T_{2}\right)\in
I_{1}}\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}\|_{2}^{2}\leq\sum_{T}\left(4d\right)^{\left|T\right|}\|L_{T}\left[f\right]\|_{4}^{4}.$

### Upper bounding the contribution from $I_{2}$

We now upper bound the contribution from $I_{2}.$ Let $T_{1}\Delta T_{2}=S.$
Then for each $S^{\prime}\subsetneq S$, we assert that
$A_{S^{\prime}}\left(f^{=T_{1}}f^{=T_{2}}\right)=0$. Let $i\in S\setminus
S^{\prime}$. Then $i\in T_{1}\Delta T_{2}.$ Assume without loss of generality
that $i\in T_{1}$. Then

$A_{S^{\prime}\cup
T_{2}}\left(f^{=T_{1}}f^{=T_{2}}\right)=f^{=T_{2}}A_{S^{\prime}\cup
T_{2}}f^{=T_{1}}=0.$

This shows that $A_{S^{\prime}}\left[f^{=T_{1}}f^{=T_{2}}\right]=0.$ Hence,

$\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}=A_{S}\left(f^{=T_{1}}f^{=T_{2}}\right)=\left\langle
f^{=T_{1}}\left(x,\cdot\right),f^{=T_{2}}\left(x,\cdot\right)\right\rangle_{L^{2}\left(\mu_{\overline{S}}\right)}.$

By Cauchy–Schwarz we have

$\displaystyle\|\sum_{\left(T_{1},T_{2}\right)\in
I_{2}}\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}\|_{2}^{2}$
$\displaystyle=\sum_{T_{1}\Delta T_{2}=T_{3}\Delta
T_{4}=S}\left\langle\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S},\left(f^{=T_{3}}f^{=T_{4}}\right)^{=S}\right\rangle$
$\displaystyle\leq\sum_{T_{1}\Delta T_{2}=T_{3}\Delta
T_{4}=S}\left\|\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}\right\|_{2}\left\|\left(f^{=T_{3}}f^{=T_{4}}\right)^{=S}\right\|_{2}.$

Now, for each $\left(T_{1},T_{2}\right)\in I_{2}$ we have

$\displaystyle\left\|\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}\right\|_{2}^{2}$
$\displaystyle=\mathbb{E}_{x\sim\mu_{S}}\left\langle
f^{=T_{1}}\left(x,\cdot\right),f^{=T_{2}}\left(x,\cdot\right)\right\rangle_{L^{2}\left(\mu_{\overline{S}}\right)}^{2}$
$\displaystyle\leq\mathbb{E}_{x\sim\mu_{S}}\left[\|f^{=T_{1}}\left(x,\cdot\right)\|_{L^{2}\left(\mu_{\overline{S}}\right)}^{2}\|f_{x}^{=T_{2}}\|_{L^{2}\left(\mu_{\overline{S}}\right)}^{2}\right]$
$\displaystyle=\mathbb{E}_{x\sim\mu_{S}}\|f_{x}^{=T_{1}}\|_{2}^{2}\mathbb{E}_{x\sim\mu_{S}}\|f_{x}^{=T_{2}}\|_{2}^{2}$
$\displaystyle=\|f^{=T_{1}}\|_{2}^{2}\|f^{=T_{2}}\|_{2}^{2},$

where in the second equality we used the fact that
$\|f^{=T}\left(x,\cdot\right)\|_{L^{2}\left(\mu_{\overline{S}}\right)}^{2}$
depends only on $x_{T\cap S}$, so these are independent for $T=T_{1}$ and
$T=T_{2}.$ This establishes

$\mathbb{E}\left[\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}\left(f^{=T_{3}}f^{=T_{4}}\right)^{=S}\right]\leq\|f^{=T_{1}}\|_{2}\|f^{=T_{2}}\|_{2}\|f^{=T_{3}}\|_{2}\|f^{=T_{4}}\|_{2}$

Summing over all $S$, we obtain

$\displaystyle\sum_{S}\|\sum_{\left(T_{1},T_{2}\right)\in
I_{2}}\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}\|_{2}^{2}$
$\displaystyle\leq\mathbb{E}_{\left(\left\\{0,1\right\\}^{n},\mu_{\frac{1}{2}}\right)}\left(\sum_{S\subseteq\left[n\right]}\|f^{=S}\|_{2}\chi_{S}\right)^{4}$
$\displaystyle\leq
9^{d}\mathbb{E}\left[(\sum\|f^{=S}\|_{2}\chi_{S})^{2}\right]^{2}$
$\displaystyle=9^{d}\|f\|_{2}^{4}.$

Here the first inequality follows by expanding both terms and the second is a
well known consequence of hypercontractivity in the uniform cube.

### Showing that there is no contribution from $I_{3}$

We recall that $I_{3}$ consist of the pairs with either $\left(T_{1}\Delta
T_{2}\right)\setminus S\neq\varnothing$ or $S\setminus\left(T_{1}\cup
T_{2}\right).$ Then we claim that $\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}=0$.
If $T_{1}\cup T_{2}$ does not contain $S$, then

$f^{=T_{1}}f^{=T_{2}}=A_{T_{1}\cup
T_{2}}\left(f^{=T_{1}}f^{=T_{2}}\right)=\sum_{S^{\prime}\subseteq
S}\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S^{\prime}}.$

The uniqueness of the Efron–Stein decomposition shows that
$\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}=0$. Suppose now that there exists
$i\in\left(T_{1}\Delta T_{2}\right)\setminus S.$ Without loss of generality
$i\in T_{1}.$ We then have

$A_{\left[k\right]\setminus\left\\{i\right\\}}\left(f^{=T_{1}}f^{=T_{2}}\right)=f^{=T_{2}}\cdot
A_{\left[k\right]\setminus\left\\{i\right\\}}f^{=T_{1}}=0.$

In particular, $\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}=0$ as for each
$S\subseteq\left[k\right]\setminus\left\\{i\right\\}$ we have

$\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}\left[A_{\left[k\right]\setminus\left\\{i\right\\}}\left(f^{=T_{1}}f^{=T_{2}}\right)\right]^{=S}=0$

### Combining the contributions from $I_{1}$ and $I_{2}$.

The lemma now follows by Cauchy–Schwarz. We have

$\displaystyle\|f\|_{4}^{4}$
$\displaystyle\leq\sum_{S}\|\left(f^{2}\right)^{=S}\|_{2}^{2}$
$\displaystyle\leq\sum_{S}\left(2\sum_{\left(T_{1},T_{2}\right)\in
I_{1}}\|\left(f^{2}\right)^{=S}\|_{2}^{2}+2\sum_{\left(T_{1},T_{2}\right)\in
I_{2}}\|\left(f^{2}\right)^{=S}\|_{2}^{2}\right)$ $\displaystyle\leq
2\sum_{T}\left(4d\right)^{\left|T\right|}\|L_{T}\left[f\right]\|_{4}^{4}+2\cdot
9^{d}\|f\|_{2}^{4}.$

∎ Finally, using Lemma 2.8, we can derive Theorem 2.7 as follows.

###### Proof of Theorem 2.7.

The proof is by induction on $d$. Since $D_{T,x}\left[f\right]$ is of degree
$d-\left|T\right|$, we have

$\displaystyle\frac{1}{2}\|f\|_{4}^{4}$ $\displaystyle\leq
9{}^{d}\|f\|_{2}^{4}+\sum_{T\neq\varnothing}\left(4d\right)^{\left|T\right|}\|L_{T}\left[f\right]\|_{4}^{4}$
$\displaystyle=9^{d}\|f\|_{2}^{4}+\sum_{T\neq\varnothing}\left(4d\right)^{\left|T\right|}\mathbb{E}_{x\sim\mu_{T}}\|D_{T,x}\left[f\right]\|_{4}^{4}$
$\displaystyle\leq 9^{d}\|f\|_{2}^{4}+\sum_{T\neq\varnothing}2\cdot
9^{d-\left|T\right|}\left(4d\right)^{\left|T\right|}\sum_{T^{\prime}\subseteq\left[n\right]\setminus
T}\left(8d\right)^{T^{\prime}}\mathbb{E}_{x\sim\mu_{T\cup T^{\prime}}}I_{T\cup
T^{\prime},x}^{2}$ $\displaystyle=9^{d}\|f\|_{2}^{4}+\sum_{T\cap
T^{\prime}=\varnothing}2^{\left|T^{\prime}\right|+1}9^{d-\left|T\right|}\left(4d\right)^{\left|T\cup
T^{\prime}\right|}\mathbb{E}_{x\sim\mu_{T\cup T^{\prime}}}\|D_{T^{\prime}\cup
T,x}\left[f\right]\|_{2}^{4}$ $\displaystyle\leq 9^{d}\sum_{T\subseteq
S}\left(9d\right)^{\left|T\right|}\mathbb{E}_{x\sim\mu_{T}}I_{T,x}^{2}.$

∎

##  3\. $\epsilon$-product spaces and the operators $A_{S,T}$

In this section, we present the framework of $\epsilon$-product spaces, of
which high dimensional expanders are a special case. We also define key
operators in this setting and show some basic properties that they satisfy.

###  3.1. Complexes having $\epsilon$-pseudorandom links.

It is useful for us to consider measures on $V_{1}\times\cdots\times V_{k}$
rather than pure $(k-1)$-dimensional complexes, which can be identified with
subsets $S\subseteq V^{k}.$ Instead we identify a set with the uniform measure
over it.

### Projected complexes

Let $\mu$ be a probability measure on $V_{1}\times\cdots\times V_{k}.$ We say
that $\mu$ is a, weighted $k$-partite, $(k-1)$-dimensional complex. Let
$S\subseteq\left[k\right]$ we write $\mu_{S}$ for the projection of $\mu$ on
$S$. We write $\mu_{i}$ rather than $\mu_{\left\\{i\right\\}}.$ We write
$V_{S}$ for the support of $\mu_{S}$ inside $\prod_{i\in S}V_{i}.$ We write
$\overline{S}$ for the complement of $S$.

### Restricted complexes

Let $x\in V_{S}.$ We write $\mu_{x}$ for the measure on $V_{\overline{S}}$
given by

$\mu_{x}\left(y\right)=\frac{\mu\left(x,y\right)}{\mu_{S}\left(x\right)}.$

We write $V_{x}$ for the support of $\mu_{x}.$ We refer to
$\left(V_{x},\mu_{x}\right)$ as the _link_ of $\mu$ on $x$.

###  $\epsilon$-pseudorandom weighted graphs

Let $V_{1},V_{2}$ be finite sets. A measure $\mu$ on $V_{1}\times V_{2}$ can
be thought of as a weighted bipartite graph. We say that $\mu$ is
$\epsilon$-pseudorandom if for each $f_{1}\colon V_{1}\to\mathbb{R},$
$f_{2}\colon V_{2}\to\mathbb{R}$ we have

$\displaystyle\left|\mathbb{E}_{\left(x_{1},x_{2}\right)\sim\mu}\left[f_{1}\left(x_{1}\right)f_{2}\left(x_{2}\right)\right]-\mathbb{E}_{x_{1}\sim\mu_{1}}\left[f_{1}\left(x_{1}\right)\right]\mathbb{E}_{x_{2}\sim\mu_{2}}\left[f_{2}\left(x_{2}\right)\right]\right|$
$\displaystyle\leq$
$\displaystyle\epsilon\sqrt{\mathrm{Var}_{x_{1}\sim\mu_{1}}\left[f_{1}\left(x_{1}\right)\right]\mathrm{Var}_{x_{2}\sim\mu_{2}}\left[f_{2}\left(x_{2}\right)\right]}.$

We let $A_{12}$ be the operator from $L^{2}\left(V_{1},\mu_{1}\right)$ to
$L^{2}\left(V_{2},\mu_{2}\right)$ given by

$A_{12}f\left(x\right)=\mathbb{E}_{y\sim\mu_{x}}\left[f\left(y\right)\right].$

We have the following standard lemma.

######  Lemma 3.1.

The following are equivalent.

  1. (1)

$\mu$ is $\epsilon$-pseudorandom

  2. (2)

$\|A_{12}-\mathbb{E}\|_{2\to 2}\leq\epsilon.$

  3. (3)

The second eigenvalue of $\mathrm{A}_{12}^{*}\mathrm{A}_{12}$ is
$\leq\epsilon^{2}.$

###  $\epsilon$-pseudorandom links

Now let $\mu$ on $V_{1}\times\cdots\times V_{k}.$ We say that $\mu$ has _
$\epsilon$-pseudorandom skeletons_ if for each $S$ of size $2$ the measure
$\mu_{S}$ is $\epsilon$-pseudorandom.

We say that $\mu$ is _$\epsilon$ -product _if for each
$S\subseteq\left[k\right]$ of size $\leq k-2$ and each $x\in V_{S}$ the link
$\mu_{x}$ has $\epsilon$-pseudorandom skeletons.

In all that follows we assume that $\mu$ is an $\epsilon$-product measure on
$V_{1}\times\cdots\times V_{k}.$

### Inheritance

The definition of $\epsilon$-product makes it easy for inductive type argument
for the following reason.

######  Lemma 3.2.

Let $\mu$ on $\prod_{i=1}^{k}V_{i}$ be $\epsilon$-product. Let
$S,T\subseteq\left[k\right]$ be disjoint. Then for each $x\in V_{S}$, the
probability measure $\left(\mu_{x}\right)_{T}=\left(\mu_{S\cup T}\right)_{x}$
is $\epsilon$-product.

###### Proof.

All the skeletons of links of $\left(\mu_{S\to x}\right)_{T}$ are also
skeletons of links of $\mu.$ ∎

### Pseudorandomness as a measure of independence

Let $S,T\subseteq\left[n\right]$. Then we have an operator
$A_{S,T}:L^{2}\left(V_{S},\mu_{S}\right)\to L^{2}\left(V_{T},\mu_{T}\right).$
The operator is given by

$A_{S,T}f\left(y\right)=\mathbb{E}_{x\sim\mu}\left[f\left(x_{S}\right)|x_{T}=y\right].$

We write $A_{S,T}^{\mu}$ to stress that the operator is taken with respect to
$\mu.$ We write $A_{S}$ for $A_{\left[k\right],S},$ the operator given by
restricting $S$ and taking expectation.

When $S,T$ are disjoint we expect $A_{S,T}f$ to be close to
$\mathbb{E}\left[f\right],$ as in the product case $A_{S,T}$ is equal to the
expectation. In fact, we do have the following.

######  Lemma 3.3.

Let $\mu$ be $\epsilon$-product. Let $S,T\subseteq\left[k\right]$ be disjoint,
and let $f\in L^{2}\left(V_{S},\mu_{S}\right)$. We have

$\|A_{S,T}f-\mathbb{E}\left[f\right]\|_{2}^{2}\leq\left|S\right|\left|T\right|\epsilon^{2}\|f\|_{2}^{2}$

###### Proof.

We prove it by induction on $k$. The case where $k=2$ is Lemma 3.1, so we
assume $k>2$. Given a probability space $\left(\Omega,\mu\right)$ we write
$1^{\bot}$ for the subspace of $L^{2}\left(\Omega,\mu\right)$ consisting of
functions that are orthogonal to the constant function $1.$ We write
$\tilde{\|}A_{S,T}\tilde{\|}$ for the $L^{2}$ operator norm of $A_{S,T}$ as an
operator from $1^{\bot}$ to $1^{\bot}$. I.e.

$\tilde{\|}A_{S,T}\tilde{\|}=\max_{f\in
1^{\bot}}\frac{\|A_{S,T}f\|_{2}}{\|f\|_{2}}.$

Our goal is to show that

$\tilde{\|}A_{S,T}\tilde{\|}\leq\sqrt{\left|S\right|\left|T\right|}\epsilon.$

### Discarding the trivial cases

If $T=\varnothing$, then $A_{S,T}=\mathbb{E}$ and the result is trivial. If
$S\cup T\neq\left[k\right]$ the result follows by working with the space
$\left(V_{S\cup T},\mu_{S\cup T}\right)$ rather then
$\left(V_{\left[k\right]},\mu_{\left[k\right]}\right).$ We also have
$\tilde{\|}A_{S,T}\tilde{\|}=\tilde{\|}A_{S,T}^{*}\tilde{\|}$ as $A_{S,T}1=1.$
As $A_{S,T}^{*}=A_{T,S}$ we may assume that
$\left|T\right|\leq\left|S\right|.$ As $k>2$ we may therefore assume that
$\left|T\right|\geq 2.$

### Completing the proof in the case where $\left|T\right|>1$

Assume without loss of generality that $1\in T$.

Let $f\in 1^{\bot}$. Using the fact that the equality

$\|X\|_{2}^{2}=\mathbb{E}\left[X\right]^{2}+\|X-\mathbb{E}\left[X\right]\|_{2}^{2}$

holds for every random variable $X$ we have

$\displaystyle\|A_{S,T}f\|_{2}^{2}$
$\displaystyle=\mathbb{E}_{y\sim\mu_{T}}\mathbb{E}_{x\sim\mu_{y}}^{2}\left[f\left(x_{S}\right)\right]$
$\displaystyle=\mathbb{E}_{a\sim\mu_{1}}\|A_{S,T\setminus\left\\{1\right\\}}^{\mu_{a}}f\|_{2}^{2}$
$\displaystyle=\mathbb{E}_{a\sim\mu_{1}}\left[\mathbb{E}_{\mu_{a}}^{2}f+\|A_{S,T\setminus\left\\{1\right\\}}^{\mu_{a}}f-\mathbb{E}_{\mu_{a}}f\|_{2}^{2}\right].$
$\displaystyle=\mathbb{E}_{a\sim\mu_{1}}\left[A_{S,1}f^{2}\left(a\right)+\|A_{S,T\setminus\left\\{1\right\\}}^{\mu_{a}}f-\mathbb{E}_{\mu_{a}}f\|_{2}^{2}\right]$

By induction we may upper bound the right hand side we have

$\displaystyle RHS$
$\displaystyle\leq\mathbb{E}_{a\sim\mu_{1}}\left[A_{S,1}f^{2}\left(a\right)+\left|S\right|\left|T-1\right|\epsilon^{2}\|f\|_{L^{2}\left(\mu_{a}\right)}^{2}\right].$
$\displaystyle=\|A_{S,1}f\|_{2}^{2}+\left|S\right|\left|T-1\right|\epsilon^{2}\|f\|_{2}^{2}.$
$\displaystyle\leq\left|S\right|+\left|S\right|\left|T-1\right|\epsilon^{2}\|f\|_{2}^{2}$
$\displaystyle=\left|S\right|\left|T\right|\epsilon^{2}\|f\|_{2}^{2}$

∎

### Understanding the operators $A_{S,T}$ and their compositions

We now deduce that we have a similar upper bound of the form

$\|A_{S,T}-A_{S,S\cap T}\|_{2\to
2}\leq\sqrt{\left|S\right|\left|T\right|}\epsilon.$

######  Corollary 3.4.

Let $S,T\subseteq\left[k\right]$, and let $f\in L^{2}\left(\mu_{S}\right)$.
Then

$\|A_{S,T}f-A_{S,S\cap
T}f\|_{2}^{2}\leq\left|S\right|\left|T\right|\epsilon^{2}\|f\|_{2}^{2}.$

###### Proof.

Lemma 3.3 covers the case $S\cap T=\varnothing.$ This shows that the corollary
is true in $\mu_{x}$ for each $x\in V_{S\cap T}.$ Therefore

$\displaystyle\|A_{S,T}f-A_{S,S\cap T}f\|_{2}^{2}$
$\displaystyle=\mathbb{E}_{x\sim\mu_{S\cap T}}\|A_{S\setminus T,T\setminus
S}^{\mu_{x}}f-A_{S\setminus
T,\mathrm{\varnothing}}^{\mu_{x}}f\|_{L^{2}\left(\mu_{x}\right)}^{2}$
$\displaystyle\leq\left|S\right|\left|T\right|\epsilon^{2}\mathbb{E}_{x}\|f\|_{L^{2}\left(\mu_{x}\right)}^{2}$
$\displaystyle=\left|S\right|\left|T\right|\epsilon^{2}\|f\|_{2}^{2}.$

∎

We now show that compositions behave similarly to the product space setting.

######  Lemma 3.5.

We have

$\|A_{T_{2}}A_{T_{1}}-A_{T_{1}\cap T_{2}}\|_{2\to
2}\leq\left|T_{1}\right|\left|T_{2}\right|\epsilon.$

###### Proof.

We may assume that $T_{1}\cap T_{2}=\varnothing$. Indeed, if the lemma holds
for $T_{1}\cap T_{2}=\varnothing$ then it holds in general. Indeed, write

$\tilde{T_{1}}=T_{1}\setminus T_{2},\tilde{T_{2}}=T_{2}\setminus
T_{1},A=\left[k\right]\setminus\left(T_{1}\cap T_{2}\right).$

Let $x\in V_{T_{1}\cap T_{2}}$. Then we have

$\left(A_{T_{2}}A_{T_{1}}f\right)\left(x,\cdot\right)=\left(A_{\tilde{T}_{2}}^{\mu_{x}}A_{\tilde{T_{1}}}^{\mu_{x}}\right)\left(f\left(x,\cdot\right)\right)$

and

$A_{T_{1}\cap
T_{2}}f\left(x,\cdot\right)=\mathbb{E}_{y\sim\mu_{x}}\left[f\left(x,y\right)\right].$

Therefore once we prove the case $T_{1}\cap T_{2}=\varnothing$ it would imply
that for each $x$

$\mathbb{E}_{y\sim\mu_{x}}\left(A_{T_{2}}A_{T_{1}}f\left(x,y\right)-A_{T_{1}\cap
T_{2}}f\left(x,y\right)\right)^{2}\leq\left|T_{1}\right|\left|T_{2}\right|\epsilon^{2}\mathbb{E}_{y\sim\mu_{x}}f\left(x,y\right)^{2}.$

The lemma will then follow by taking expectations over $x$.

Let us now settle the case $T_{1}\cap T_{2}=\varnothing$. Write
$\mathrm{T}=A_{T_{2}}A_{T_{1}}.$ Then

$\mathrm{T}=A_{T_{1},T_{2}}A_{T_{1}}.$

Write $g=A_{T_{1}}f$. We have $\|g\|_{2}\leq\|f\|_{2}$ by Cauchy–Schwarz. By
Lemma 3.3 we have

$\displaystyle\|\mathrm{T}f-\mathbb{E}\left[f\right]\|_{2}^{2}$
$\displaystyle=\|A_{T_{1},T_{2}}g-\mathbb{E}g\|_{2}^{2}$
$\displaystyle\leq\left|T_{1}\right|\left|T_{2}\right|\epsilon^{2}\|g\|_{2}^{2}$
$\displaystyle\leq\left|T_{1}\right|\left|T_{2}\right|\epsilon^{2}\|f\|_{2}^{2}.$

∎

##  4\.  Efron–Stein decompositions for link expanders

In this section, we introduce a new approximate Efron–Stein decomposition for
high dimensional expanders. In fact, it is more convenient to state and prove
our results in the more general setting of $\epsilon$-product spaces, of which
high dimensional expanders are a special case. We proceed to discuss this
setting below.

We first define the Efron–Stein decomposition via the usual formula for it.

######  Definition 4.1.

Let $f\in L^{2}\left(V,\mu\right)$ and $S\subseteq\left[n\right].$ We write

$f^{=S}=\sum_{T\subseteq\left[S\right]}\left(-1\right)^{\left|S\setminus
T\right|}A_{T}f.$

The functions $f^{=S}$ are defined in terms of the operators $A_{T}$.
$L^{2}$-wise the composition of the operators
$\left\\{A_{T}\right\\}_{T\subseteq\left[k\right]}$ behave similarly to the
compositions in the product case setting. We satrt this section by making use
of that and showing that many known facts from the product setting generalize
to the $\epsilon$-product setting up to a small error.

###  4.1. $L^{2}$-approximations for the Efron–Stein decomposition

Thinking of $\epsilon$ as tending to $0$ in a much quicker pace than
$\frac{1}{k}$. Our goal is now to show that if $\mu$ is $\epsilon$-product,
then we have:

  1. (1)

$\left|\|f\|_{2}^{2}-\sum_{S\subseteq\left[k\right]}\|f^{=S}\|_{2}^{2}\right|=o\left(\|f\|_{2}^{2}\right),$

  2. (2)

and more generally

$\left|\left\langle f,g\right\rangle-\sum_{S}\left\langle
f^{=S},g^{=S}\right\rangle\right|=o\left(\|f\|_{2}\|g\|_{2}\right).$

One main tool involves the notion of a junta. We say that $g\colon
V\to\mathbb{R}$ is a _$T$ -junta_ if $g\left(x\right)$ depends only on
$x_{T}.$ Equivalently, $g$ is a $T$-junta if $A_{T}g=g.$

Our first step towards the proof is a near orthogonality result between
$f^{=T}$ and $g^{=S}$ for $T\neq S.$

We start by a Fourier formula that holds exactly, this is unlike most of the
results in this section that only generalize the situation from the product
space setting up to a small error term.

######  Lemma 4.2.

We have

$A_{S}\left[f\right]=\sum_{T\subseteq S}f^{=T}\left(x\right).$

In particular $f=\sum_{S\subseteq\left[k\right]}f^{=S}.$

###### Proof.

We have

$\displaystyle\sum_{T\subseteq S}f^{=T}$ $\displaystyle=\sum_{T\subseteq
S}\sum_{T^{\prime}\subseteq T}\left(-1\right)^{\left|T\setminus
T^{\prime}\right|}A_{T^{\prime}}f$ $\displaystyle=\sum_{T^{\prime}\subseteq
S}A_{T^{\prime}}f\sum_{T^{\prime}\subseteq T\subseteq
S}\left(-1\right)^{\left|T\setminus T^{\prime}\right|}$
$\displaystyle=A_{S}f,$

where the last equality follows from the fact that whenever $T^{\prime}\neq S$
and $i\in S\setminus T^{\prime}$ the pairs

$\left(T,T\Delta\left\\{i\right\\}\right)$

contribute opposing signs to the sum $\sum_{T^{\prime}\subseteq T\subseteq
S}\left(-1\right)^{\left|T\setminus T^{\prime}\right|}.$ The ‘in particular’
part follows by taking $S=\left[k\right].$ ∎

The following lemma holds even without assuming that $\mu$ is
$\epsilon$-product.

######  Lemma 4.3.

We have $\|A_{S,T}\|_{2\to 2}\leq 1$ and

$\|f^{=S}\|_{2}\leq 2^{\left|S\right|}\|f\|_{2}.$

###### Proof.

The triangle inequality implies that it suffices to prove the former claim.
Now by Cauchy–Schwarz we have

$\displaystyle\|A_{S,T}f\|_{2}^{2}$
$\displaystyle=\mathbb{E}_{x\sim\mu_{T}}A_{S,T}f\left(x\right)^{2}$
$\displaystyle=\mathbb{E}_{x\sim\mu_{T}}\left(\mathbb{E}_{y\sim\left(\mu_{x}\right)_{T}}f\left(y\right)\right)^{2}$
$\displaystyle\leq\mathbb{E}_{x\sim\mu_{T}}\mathbb{E}_{y\sim\left(\mu_{x}\right)_{T}}f\left(y\right)^{2}$
$\displaystyle=\|f\|_{2}^{2}.$

∎

######  Lemma 4.4.

Let $f\colon V\to\mathbb{R}$, $T$ be a set not containing $S$, and $g$ be a
$T$-junta. Then

$\left\langle
f^{=S},g\right\rangle\leq\epsilon\sqrt{\left|S\right|\left|T\right|}2^{\left|S\right|}\|f\|_{2}\|g\|_{2}.$

###### Proof.

As $A_{T}$ is the dual to the inclusion operator $L^{2}\left(V_{T}\right)\to
L^{2}\left(V_{\left[k\right]}\right)$ we have

$\left\langle f^{=S},g\right\rangle=\left\langle A_{T}f^{=S},g\right\rangle.$

By Cauchy–Schwarz it is sufficient to show that

$\|A_{T}f^{=S}\|_{2}\leq\epsilon\left|S\right|\left|T\right|2^{\left|S\right|}\|f\|_{2}.$

Now

$A_{T}f^{=S}=\sum_{S^{\prime}\subseteq S}\left(-1\right)^{\left|S\setminus
S^{\prime}\right|}A_{T}A_{S^{\prime}}f.$

Roughly speaking, we rely on Lemma 4.2, which says that
$\|A_{T}A_{S^{\prime}}-A_{T\cap S^{\prime}}\|_{2\to 2}$ is small together with
the fact that

(4.1) $\sum_{S^{\prime}\subseteq S}\left(-1\right)^{\left|S\setminus
S^{\prime}\right|}A_{T\cap S^{\prime}}f=0.$

The equality follows by choosing an arbitrary $i\in S\setminus T$ and noting
that the sets
$\left(S^{\prime},S^{\prime}\Delta\left\\{i\right\\}\right)_{S^{\prime}\subseteq
S}$ correspond to the same term $A_{\left[k\right],T\cap S^{\prime}}$, while
appearing with opposite signs. This shows that we have

$A_{T}f^{=S}=\sum_{S^{\prime}\subseteq S}\left(-1\right)^{\left|S\setminus
S^{\prime}\right|}\left(A_{T}A_{S^{\prime}}f-A_{T\cap S^{\prime}}f\right).$

By Lemma 3.5 we have

$\displaystyle\|A_{T}A_{S^{\prime}}f-A_{T\cap
S^{\prime}}f\|_{2}\leq\sqrt{\left|T\right|\left|S\right|}\epsilon\|f\|_{2}\leq\sqrt{\left|S\right|\left|T\right|}\epsilon\|f\|_{2}.$

Hence,

$\|A_{T}f^{=S}\|_{2}\leq\sqrt{\left|S\right|\left|T\right|}2^{\left|S\right|}\epsilon.$

∎

### Proof of our near orhogonality result

######  Corollary 4.5.

Let $T\neq S.$ Then $\left\langle f^{=S},g^{=T}\right\rangle\leq
2^{2\left|S\right|+2\left|T\right|}\epsilon\|f\|_{2}\|g\|_{2}.$

###### Proof.

The function $g^{=T}$ is a $T$-junta. By Lemmas 4.4 and 4.3 we therefore have
the following chain of inequalities if $T$ does not contain $S$.

$\left\langle
f^{=S},g^{=T}\right\rangle\leq\epsilon\sqrt{\left|S\right|\left|T\right|}2^{\left|S\right|}\|f\|_{2}\|g^{=T}\|_{2}\leq\epsilon
2^{2\left|S\right|+2\left|T\right|}\|f\|_{2}\|g\|_{2}.$

A similar chain of inequalities holds when $S$ does not contain $T.$ ∎

### Parseval holds approximately for the Efron–Stein decomposition

######  Lemma 4.6.

We have

$\left|\left\langle
f,g\right\rangle-\sum_{S\subseteq\left[k\right]}\left\langle
f^{=S},g^{=S}\right\rangle\right|\leq 2^{4k}\epsilon\|f\|_{2}\|g\|_{2}.$

Moreover, if $f$ is a $T$-junta, then

$\left|\left\langle f,g\right\rangle-\sum_{S\subseteq T}\left\langle
f^{=S},g^{=S}\right\rangle\right|=2^{4\left|T\right|}\epsilon\|f\|_{2}\|g\|_{2}.$

###### Proof.

We have $\left\langle
f,g\right\rangle=\sum_{S\subseteq\left[k\right]}\left\langle
f^{=S},g^{=S}\right\rangle+\sum_{S\neq T}\left\langle
f^{=S},g^{=T}\right\rangle.$ By corollary 4.5 we have

$\sum_{S\neq T}\left\langle f^{=S},g^{=T}\right\rangle\leq
2^{4k}\epsilon\|f\|_{2}\|g\|_{2}.$

For the ‘moreover’ part note that if $f$ is a $T$-junta, then

$\left\langle f,g\right\rangle=\left\langle
f,A_{T}g\right\rangle_{L^{2}\left(\mu_{T}\right)}.$

We may then apply the first part of the lemma in $\mu_{T}$ noting that
$\left(A_{T}g\right)^{=T^{\prime}}=g^{=T^{\prime}}$ for each
$T^{\prime}\subseteq T$. ∎

###  $\left(f^{=S}\right)^{=S}$ is $L^{2}$-close to $f^{=S}.$

In the product space setting we have
$\left(f^{=S}\right)^{=T}=\begin{cases}f^{=S}&T=S\\\ 0&T\neq S\end{cases}.$
Here we have the following instead:

######  Lemma 4.7.

Let $g=f^{=S}.$ Then:

  1. (1)

If $S\neq T$, then

$\|g^{=T}\|_{2}^{2}\leq 2^{8k}\epsilon^{2}\|f\|_{2}^{2}$

  2. (2)

$\|g^{=S}-g\|_{2}^{2}\leq 2^{10k}\epsilon^{2}\|f\|_{2}^{2}.$

###### Proof.

We have

$g^{=T}=\sum_{T^{\prime}\subseteq T,S^{\prime}\subseteq
S}\left(-1\right)^{\left|S\setminus S^{\prime}\right|+\left|T\setminus
T^{\prime}\right|}A_{T^{\prime}}A_{S^{\prime}}f.$

Write

$h=\sum_{T^{\prime}\subseteq T,S^{\prime}\subseteq
S}\left(-1\right)^{\left|S\setminus S^{\prime}\right|+\left|T\setminus
T^{\prime}\right|}A_{T^{\prime}\cap S^{\prime}}f.$

By Lemma 3.4 we therefore have

$\|h-g^{=T}\|_{2}\leq
2^{2k}\max_{T^{\prime},S^{\prime}}\|A_{T^{\prime}}A_{S^{\prime}}-A_{T^{\prime}\cap
S^{\prime}}\|_{2\to 2}\|f\|_{2}\leq 2^{4k}\epsilon\|f\|_{2}.$

Now we claim that $h=0.$ Indeed, assume without loss of generality that $T$ is
not contained in $S$ and let $i\in T\setminus S.$ Then the terms
$A_{T^{\prime}\cap S^{\prime}}$ appears with opposing sums for the pairs
$T^{\prime}$ and $T^{\prime}\Delta\left\\{i\right\\}$.

(2)-follows by the fact that

$\|g^{=S}-g\|_{2}=\left\|\sum_{T\neq S}g^{=T}\right\|_{2}\leq\sum_{T\neq
S}\|g^{=T}\|_{2}\leq 2^{5k}\epsilon\|f\|_{2}.$

∎

###  4.2. Approximate Efron-Stein decomposition

Again think of $\epsilon$ as tending to 0 much more quickly than
$\frac{1}{k}$. We now define a notion of
$\left(\alpha,\epsilon^{\prime}\right)$-approximate Efron–Stein decomposition.
We show that a version of Lemma 4.6 still holds for these approximate
Efron–Stein decompositions.

### Motivation

One reason that demonstrates our need for an approximate Efron–Stein
decomposition is as follows. Let $f^{\leq d}=\sum_{\left|S\right|<d}f^{=S}$.
Then we do not have

$\displaystyle\left(f^{\leq d}\right)^{=S}$
$\displaystyle=\begin{cases}f^{=S}&\left|S\right|\leq d\\\
0&\left|S\right|>d\end{cases},$

but we would nevertheless like to work with the decomposition
$\left\\{f^{=S}\right\\}_{\left|S\right|\leq d}$ as an approximate Efron–Stein
decomposition for $f$. We capture that notion as follows.

### Defining the $\left(\alpha,\epsilon^{\prime}\right)$-approximate
Efron–Stein decomposition

######  Definition 4.8.

We say that $\left\\{f_{S}\right\\}_{S\subseteq\left[k\right]}$ is an
$\left(\alpha,\epsilon^{\prime}\right)$-approximate Efron–Stein decomposition
if

  1. (1)

$\|f\|_{2}\leq\alpha.$

  2. (2)

$\|f-\sum_{S}f_{S}\|_{2}<\epsilon^{\prime},$

  3. (3)

For each $S$ there exists $h_{S}$ with $\|h_{S}\|_{2}\leq\alpha$ and

$\|h_{S}^{=S}-f_{S}\|_{2}\leq\epsilon^{\prime}.$

It turns out that we have an approximate Parseval theorem for every
approximate Efron–Stein decomposition.

######  Lemma 4.9.

Let $\alpha_{1},\alpha_{2},\epsilon_{1},\epsilon_{2}>0$. Suppose that $f$ has
an $\left(\alpha_{1},\epsilon_{1}\right)$-bounded approximate Efron–Stein
decomposition $\left\\{f_{S}\right\\}$ and $g$ has an
$\left(\alpha_{2},\epsilon_{2}\right)$-bounded Efron–Stein decomposition
$\left\\{g_{S}\right\\}.$ Then

$\left|\left\langle f,g\right\rangle-\sum_{S}\left\langle
f_{S},g_{S}\right\rangle\right|\leq
2^{6k}\left(\epsilon_{1}\alpha_{2}+\epsilon_{2}\alpha_{1}+\epsilon\alpha_{1}\alpha_{2}\right).$

###### Proof.

For each $S\subseteq\left[k\right]$ let $\tilde{f}_{S},\tilde{g}_{S}$ be with
$\|\tilde{f}_{S}\|_{2}\leq\alpha_{1},\|\tilde{g}_{S}\|_{2}\leq\alpha_{2}$

$\|\tilde{f}{}_{S}^{=S}-f_{S}\|_{2}\leq\epsilon_{1},$

and

$\|\tilde{g}_{S}^{=S}-g_{S}\|_{2}\leq\epsilon_{2}.$

Let

$f^{\prime}_{S}=\tilde{f}_{S}^{=S},g^{\prime}_{S}=\tilde{g}_{S}^{=S},$

$f^{\prime}=\sum_{S\subseteq\left[k\right]}f^{\prime}_{S}$

and

$g^{\prime}=\sum_{S\subseteq\left[k\right]}g^{\prime}_{S}.$

By Lemma 4.5 we have

$\displaystyle\left\langle f^{\prime},g^{\prime}\right\rangle$
$\displaystyle=\sum_{S}\left\langle
f^{\prime}_{S},g^{\prime}_{S}\right\rangle+\sum_{S\neq
T\subseteq\left[k\right]}\left\langle
f_{S}^{\prime},g_{T}^{\prime}\right\rangle$
$\displaystyle=\sum_{S}\left\langle
f_{S}^{\prime},g_{S}^{\prime}\right\rangle\pm
2^{6k}\epsilon\alpha_{1}\alpha_{2}.$

Now by Cauchy–Schwarz

$\displaystyle\left\langle f,g\right\rangle$ $\displaystyle=\left\langle
f^{\prime},g^{\prime}\right\rangle+\left\langle
f^{\prime},g-g^{\prime}\right\rangle+\left\langle f-f^{\prime},g\right\rangle$
$\displaystyle=\sum_{S}\left\langle
f^{\prime}_{S},g^{\prime}_{S}\right\rangle\pm\left(2^{6k}\epsilon\alpha_{1}\alpha_{2}+\|f^{\prime}\|_{2}\|g-g^{\prime}\|_{2}+\|f-f^{\prime}\|_{2}\|g\|_{2}\right)$
$\displaystyle=\sum_{S}\left\langle
f^{\prime}_{S},g^{\prime}_{S}\right\rangle\pm\left(2^{6k}\epsilon\alpha_{1}\alpha_{2}+2^{2k}\alpha_{1}\epsilon_{2}+\epsilon_{1}\alpha_{2}\right),$

where the last equality used

$\|f^{\prime}\|_{2}\leq\sum\|f^{\prime}_{S}\|_{2}\leq
2^{k+\left|S\right|}\alpha_{1}\leq 2^{2k}\alpha_{1},$

which follows from Lemma 4.3.

To complete the proof we note that we similarly have

$\displaystyle\left\langle f^{\prime}_{S},g^{\prime}_{S}\right\rangle$
$\displaystyle=\left\langle
f_{S},g_{S}\right\rangle\pm\|f_{S}\|_{2}\|g_{S}-g_{S}^{\prime}\|_{2}+\|f_{S}^{\prime}-f_{S}\|_{2}\|g_{S}^{\prime}\|_{2}$
$\displaystyle=\left\langle
f_{S},g_{S}\right\rangle\pm\alpha\epsilon_{2}+2^{k}\epsilon_{1}\alpha_{2}.$

∎

The above approximate Efron–Stein decomposition works well when we care about
$L_{2}$-norms. We actually care about closeness in higher norms specifically
$4$-norms. Our strategy when wishing to upper bound $\|f-f^{\prime}\|_{4}$ is
to use the inequality

$\|f-f^{\prime}\|_{4}^{4}\leq\|f-f^{\prime}\|_{2}^{2}\left(\|f\|_{\infty}+\|f^{\prime}\|_{\infty}\right).$

Where we hope that the $L^{2}$-closeness is sufficient to overcome the loss of
using infinity norms. We would therefore like everything to have a relatively
small infinity norm.

######  Definition 4.10.

We say that $\left\\{f_{S}\right\\}$ is a
$\left(\beta,\alpha,\epsilon^{\prime}\right)$-_bounded approximate Efron-
Stein_ decomposition if it is an
$\left(\alpha,\epsilon^{\prime}\right)$-approximate Efron–Stein decomposition
and moreover for each $S$:

$\|h_{S}^{=S}\|_{\infty},\|f_{S}\|_{\infty},\|f\|_{\infty}$

are all $\leq\beta.$ Here $h_{S}^{=S}$ is as in Definition 4.8.

We now show that the different Efron–Stein decompositions of a function $f$
are all close in $L_{4}.$

######  Lemma 4.11.

Suppose that $\left\\{f_{S}\right\\},\left\\{f^{\prime}_{S}\right\\}$ are
$\left(\beta,\alpha,\epsilon^{\prime}\right)$-bounded approximate Efron–Stein
decompositions for $f.$ Then

  1. (1)

$\|f_{S}-f^{\prime}_{S}\|_{2}^{2}\leq
O_{k}\left(\epsilon^{\prime}\right)^{2}+O_{k}\left(\epsilon\alpha^{2}\right),$

  2. (2)

$\|f_{S}-f_{S}^{\prime}\|_{4}^{4}\leq O_{k}\left(\epsilon^{\prime
2}\beta^{2}\right)+O_{k}\left(\epsilon\alpha^{2}\beta^{2}\right),$

  3. (3)

$\|\sum_{S}\left(f_{S}-f^{\prime}_{S}\right)\|_{4}^{4}\leq
O_{k}\left(\epsilon^{\prime
2}\beta^{2}\right)+O_{k}\left(\epsilon^{2}\alpha^{2}\beta^{2}\right),$

  4. (4)

and

$\|f-\sum_{S\subseteq\left[k\right]}f_{S}\|_{4}^{4}\leq
O_{k}\left(\epsilon^{2}\beta^{2}\right)\left(\alpha^{2}+\|f\|_{2}^{2}\right).$

###### Proof.

(3) is an immediate corollary of (2). (4) also follows immediately from (3) by
setting $f^{\prime}_{S}=f^{=S}$ while applying it with $2^{k}\beta$ rather
than $\beta$. Indeed, $\|f^{=S}\|_{\infty}\leq 2^{k}\|f\|_{\infty}\leq
2^{k}\beta$. Therefore $\left\\{f^{=S}\right\\}_{S\subseteq\left[k\right]}$ is
a $\left(2^{k}\beta,\alpha,0\right)$-approximate Efron–Stein decomposition for
$f$. (2) follows immediately from (1) as we have

$\|f_{S}-f^{\prime}_{S}\|_{4}^{4}\leq\|f_{S}-f^{\prime}_{S}\|_{2}^{2}\|f_{S}-f^{\prime}_{S}\|_{\infty}^{2}$

and $\|f_{S}-f^{\prime}_{S}\|_{\infty}^{2}\leq 4\beta^{2}.$

We now prove (1).

### Reducing to the case that $f^{\prime}_{S}=f^{=S}$

First we assert that we may assume that $f^{\prime}_{S}=f^{=S}$ for each $S.$
Indeed, $\left\\{f^{=S}\right\\}$ is a
$\left(\beta,\alpha,0\right)$-Efron–Stein decomposition. By the triangle
inequality we have

$\|f_{S}-f^{\prime}_{S}\|_{2}\leq\|f_{S}-f^{=S}\|_{2}+\|f^{=S}-f^{\prime}_{S}\|_{2},$

which implies (by Hólder) that

$\|f_{S}-f^{\prime}_{S}\|_{2}^{2}\leq
2\|f_{S}-f^{=S}\|_{2}^{2}+2\|f^{=S}-f^{\prime}_{S}\|_{2}^{2}.$

This shows that it is sufficient to prove the theorem when
$\left\\{f_{S}\right\\}=\left\\{f^{=S}\right\\}$ and when
$\left\\{f^{\prime}_{S}\right\\}=\left\\{f^{=S}\right\\}.$ Without loss of
generality we may assume that $f^{\prime}_{S}=f^{=S}.$

### Reducing to the case that $f_{S}=h_{S}^{=S}$

Let $h_{S}$ be with $\|h_{S}\|_{2}\leq\alpha$ and
$\|f_{S}-h_{S}^{=S}\|_{2}<\epsilon^{\prime}.$ Setting
$\tilde{f}_{S}=h_{S}^{=S}$ we obtain by the triangle inequality that
$\left\\{\tilde{f}_{S}\right\\}_{S\subseteq\left[k\right]}$ is a
$\left(\beta,\alpha,\left(2^{k}+1\right)\epsilon^{\prime}\right)$-bounded
approximate Efron–Stein decomposition for $f$. We have

$\|f_{S}-f^{=S}\|_{2}^{2}\leq
2\|\tilde{f_{S}}-f_{S}\|_{2}^{2}+2\|\tilde{f}_{S}-f^{=S}\|_{2}\leq
2\epsilon^{\prime}+2\|\tilde{f}_{S}-f^{=S}\|_{2}.$

Therefore it is sufficient to prove (1) when $f_{S}$ is replaced by
$\tilde{f}_{S}$.

### Proving the lemma when $f_{S}=h_{S}^{=S}$ and $f^{\prime}_{S}=f^{=S}$

By Cauchy–Schwarz and Corollary 4.5 we have:

$\displaystyle\left\langle f_{S}-f^{=S},f\right\rangle$
$\displaystyle=\sum_{T\subseteq\left[k\right]}\left\langle
f_{S}-f^{=S},f^{=T}\right\rangle$ $\displaystyle=\left\langle
f_{S}-f^{=S},f^{=S}\right\rangle+\sum_{T\neq S}\left\langle
f^{=S}-h_{S}^{=S},f^{=T}\right\rangle$ $\displaystyle=\left\langle
f_{S}-f^{=S},f^{=S}\right\rangle+O_{k}\left(\epsilon\alpha^{2}\right).$

Again by Corollary 4.5 and Cauchy–Schwarz we have:

$\displaystyle\left\langle f_{S}-f^{=S},f\right\rangle$
$\displaystyle=\left\langle
f_{S}-f^{=S},\sum_{T}f_{T}\right\rangle+\left\langle
f_{S}-f^{=S},f-\sum_{T}f_{T}\right\rangle$ $\displaystyle=\left\langle
f_{S}-f^{=S},f_{S}\right\rangle+O_{k}\left(\epsilon\alpha^{2}\right)+\|f_{S}-f^{=S}\|_{2}\epsilon^{\prime}.$

Rearranging we obtain,

$\displaystyle\|f_{S}-f^{=S}\|_{2}^{2}$ $\displaystyle\leq
O_{k}\left(\epsilon^{\prime}\right)\left(\|f^{=S}-f_{S}\|_{2}\right)+O_{k}\left(\epsilon\alpha^{2}\right).$

This shows that

$\|f_{S}-f^{=S}\|_{2}^{2}\leq
O_{k}\left(\epsilon^{\prime}\right)^{2}+O_{k}\left(\epsilon\alpha^{2}\right).$

∎

##  5\. Proof overview

Building on the framework we established in Section 4, we can now give a proof
overview for our hypercontactive inequality on high dimensional expanders.
Recall that in the setting of direct products, we first prove a key lemma,
(Lemma 2.8) and then use it to derive the theorem via an inductive argument.
We now give a sketch of how to generalise this approach to the
$\epsilon$-product setting.

###  5.1. Generalising Lemma 2.8

Recall that we would like to show a lemma of the form

$\|f\|_{4}^{4}\leq
C^{d}\|f\|_{2}^{4}+\sum_{S}\left(4d\right)^{\left|S\right|}\|L_{S}\left[f\right]\|_{4}^{4}.$

We instead show a similar lemma that holds up to a small error term of
$O_{k}\left(\epsilon\|f\|_{2}^{2}\|f\|_{\infty}^{2}\right)$:

(5.1) $\frac{1}{2}\|f^{\leq d}\|_{4}^{4}\leq 9^{d}\|f^{\leq
d}\|_{2}^{4}+4\sum_{0<\left|T\right|\leq
d}\left(4d\right)^{\left|T\right|}\|L_{T}^{\leq
d}\left[f\right]\|_{4}^{4}+O_{k}\left(\epsilon\right)\|f\|_{2}^{2}\|f\|_{\infty}^{2}.$

However, first note that we do not have a useful notion of a low degree
function. Instead we work with

$f^{\leq d}=\sum_{\left|S\right|\leq d}f^{=S}.$

In turn, instead of $L_{S}\left[f\right]$ we have

$L_{S}^{\leq d}\left[f\right]=\sum_{T\supseteq S,\left|T\right|\leq d}f^{=T}.$

We show that when expanding

$\left(\left(f^{\leq
d}\right)^{2}\right)^{=S}=\sum_{T_{1},T_{2}}\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S},$

there are three kinds of terms: (1) terms that vanish in the product space
setting, but here they do not; (2) terms with $T_{1}\cap T_{2}\cap
S\neq\varnothing$; and (3) terms with $T_{1}\Delta T_{2}=S.$

Our high-level approach is to show that the same proof as in the setting of
product spaces works up to an error term. We accomplish that by expressing
everything in terms of our operators $\left\\{A_{S}\right\\}$, and we then
replace equalities that hold in the product space by $L_{2}$-approximation of
the form

$\|A_{S}A_{T}-A_{S\cap T}\|_{2\to 2}\leq O_{k}\left(\epsilon\right).$

At first glance, it might appear that this approach would not suffice, as we
eventually would like to upper bound $4$-norms of terms, or $2$-norms of
expressions involving the product of two functions such as
$\left(f^{=T_{1}}f^{=T_{2}}\right)^{S}.$ Nevertheless, we are able to
accomplish that via inequalities of the form

$\|f\|_{4}^{4}\leq\|f\|_{2}^{2}\|f\|_{\infty}^{2}.$

We then use the fact that all our terms are bounded by
$O_{k}\left(\|f\|_{\infty}\right)$, and our $L_{2}$-approximations involve
$\epsilon$, and therefore beat the $O_{k}\left(1\right)$-terms. This allows us
to generalise Lemma 2.8 and prove (5.1).

###  5.2. Applying induction

After having an inequality of the form

$\|f^{\leq d}\|_{4}^{4}\leq C^{d}\|f^{\leq
d}\|_{2}^{2}+\sum_{S}\left(4d\right)^{\left|S\right|}\|L_{S}^{\leq
d}\left[f\right]\|_{4}^{4},$

we would like to use a similar idea to the one we used in the product space
setting; that is, restrict $S$ to some $x\in V_{S}$, and then apply induction
for the function $L_{S}^{\leq d}\left[f\right]\left(x,\cdot\right).$ The
problem is that the restricted function $L_{S}^{\leq
d}\left[f\right]\left(x,\cdot\right)$ is no longer of degree
$d-\left|S\right|$, and hence we can no longer use induction.

We overcome this problem by using the notion of our approximate Efron–Stein
decompositions. Namely, we show that $L_{S}^{\leq d}$ has two different
approximate Efron–Stein decomposition. The first one is

$\left\\{f^{=T}\right\\}_{T\supseteq S,\left|T\right|\leq d},$

and the other one replaces $f^{=T}$ by the function $f_{T}$

$\left(x,y\right)\mapsto\left(L_{S}\left[f\right]\left(x,\cdot\right)\right)^{=T\setminus
S}\left(y\right).$

We then obtain that $\sum_{\left|T\right|\supseteq S,\left|T\right|\leq
d}f_{T}\left(x,\cdot\right)$ is of the form $D_{S,x}^{\leq d-\left|S\right|}$,
which allows us to use induction similarly as in the product space setting.

After applying induction we get the compositions of two derivatives, and we
are again able to translate them back to expressions of the form
$\mathbb{E}_{x\sim\mu_{S}}I_{S,x}^{2}$ by showing that $D_{S,x}D_{T,y}$ and
$D_{S\cup T,\left(x,y\right)}$ are both approximate Efron–Stein decompositions
of the same expression.

The remaining step is to upper bound the influences. We achieve that by
generalising the inequality

$\mathbb{E}_{x\sim\mu_{S}}\left[I_{S,x}^{2}\right]\leq\delta\|L_{S}\left[f\right]\|_{2}^{2}$

from the product space setting, where crucially, we obtain that without upper
bounding $\|I_{S,x}\|_{\infty}$.

##  6\. Laplacians, influences, and globalness on $\epsilon$-measures

In this section, we define the notions of laplacians, derivatives and
influences in the setting of $\epsilon$-measures, give bounded approximated
Efron–Stein decompositions related to the Laplacians, define globalness, and
show that it implies small influences.

###  6.1. Defining the Laplacians, derivatives and influences

######  Definition 6.1.

We define the Laplacians via the formula

$L_{i}\left[f\right]=f-A_{\left[k\right]\setminus\left\\{i\right\\}}f.$

######  Lemma 6.2.

We have

$L_{i}\left[f\right]=\sum_{S\ni i}f^{=S}.$

###### Proof.

This follows immediately from Lemma 4.2, which shows that

$A_{\left[k\right]\setminus\left\\{i\right\\}}\left[f\right]=\sum_{S\subseteq\left[k\right]\setminus\left\\{i\right\\}}f^{=S}.$

∎

######  Definition 6.3.

We define $L_{S}\left[f\right]=\sum_{T\supseteq S}f^{=T}.$ Alternatively,

$L_{S}\left[f\right]=\sum_{T\subseteq
S}\left(-1\right)^{\left|T\right|}A_{\left[k\right]\setminus T}f.$

Let $x\in V_{S}.$ We let $D_{S,x}=L_{S}\left[f\right]\left(x,\cdot\right)$,
i.e. the function in $L^{2}\left(V_{x},\mu_{x}\right)$ obtained by plugging in
$x$ in the $S$ coordinates. We let

$I_{S,x}\left[f\right]=\|D_{S,x}\left[f\right]\|_{L^{2}\left(V_{x},\mu_{x}\right)}.$

###  6.2. Bounded approximated Efron–Stein decompositions related to the
Laplacians

######  Lemma 6.4.

. There exists $C=O_{k}\left(1\right)$, such that
$\left\\{f^{=T}\right\\}_{T\supseteq S}$ is a
$\left(C\|f\|_{\infty},C\|f\|_{2},0\right)$-bounded approximate Efron–Stein
decomposition for $L_{S}\left[f\right].$

###### Proof.

We have

$\|f^{=S}\|_{\infty}\leq\sum_{T\subseteq S}\|A_{T}f\|_{\infty}\leq
2^{\left|S\right|}\|f\|_{\infty}$

and

$\|L_{S}\left[f\right]\|_{\infty}\leq\sum_{T\subseteq
S}\|A_{\overline{T}}f\|_{\infty}\leq 2^{\left|S\right|}\|f\|_{\infty}.$

The other properties are easy to verify. ∎

Let $f\in L^{2}\left(V_{\left[k\right]},\mu_{\left[k\right]}\right)$ and let
$g_{T}\in L^{2}\left(V_{T},\mu_{T}\right)$ be given by

$g_{T}\left(x\right)=I_{T,x}\left[f\right].$

Then $g_{T}$ can be interpreted interms of the Laplacians and the averaging
operators as

$g_{T}=A_{T}\left(L_{T}\left[f\right]^{2}\right).$

Suppose that $\left\\{f_{S}\right\\}_{S\subseteq\left[k\right]}$ is a
$\left(\beta,\alpha,\epsilon^{\prime}\right)$-bounded approximate Efron–Stein
decompositions for $f$ and set
$\widetilde{L_{T}\left[f\right]}=\sum_{S\supseteq T}f_{S}$. The following
lemma essentially shows that the function
$A_{T}\left(\widetilde{L_{T}\left[f\right]}^{2}\right)$ is a good
$L_{2}$-approximation for the function $g_{T}$. This can be interpreted by
saying that the generalised influences could be computed via any
$\left(\beta,\alpha,\epsilon^{\prime}\right)$-bounded approximate Efron–Stein
decomposition for $f$.

######  Lemma 6.5.

Let $\left\\{f_{S}\right\\}$ and $\left\\{f_{S}^{\prime}\right\\}$ be
$\left(\beta,\alpha,\epsilon^{\prime}\right)$-bounded Efron-Stein
decompositions for $f.$ Then

$\|A_{T}\left(\sum_{S\supseteq T}f_{S}\right)^{2}\|_{2}^{2}\leq
2\|A_{T}\left(\sum_{S^{\prime}\supseteq
T}f^{\prime}_{S}\right)^{2}\|_{2}^{2}+O_{k}\left(\epsilon^{\prime
2}\beta^{2}\right)+O_{k}\left(\epsilon\alpha^{2}\beta^{2}\right).$

###### Proof.

By Cauchy–Schwarz we have

$\left(\sum_{S\supseteq T}f_{S}\right)^{2}\leq 2\left(\sum_{S\supseteq
T}f_{S}^{\prime}\right)^{2}+2\left(\sum_{S\supseteq
T}f_{S}^{\prime}-f_{S}\right)^{2}.$

Therefore

$\|A_{T}\left(\sum_{S\supseteq T}f_{S}\right)^{2}\|_{2}^{2}\leq
2\|A_{T}\left(\sum_{S^{\prime}\supseteq
T}f^{\prime}_{S}\right)^{2}\|_{2}^{2}+2\|A_{T}\left(\sum_{S\supseteq
T}f^{\prime}_{S}-f_{S}\right)^{2}\|_{2}^{2}.$

Now since $A_{T}$ contracts 2-norms (Lemma 4.3). We have

$2\|A_{T}\left(\sum_{S\supseteq
T}f^{\prime}_{S}-f_{S}\right)^{2}\|_{2}^{2}\leq 2\|\sum_{S\supseteq
T}f_{S}^{\prime}-f_{S}\|_{4}^{4}.$

Lemma 4.11 now completes the proof. ∎

We now show that Lemma 6.4 is a special case of a more general phenomenon.
Whenever $\left\\{f_{S}\right\\}_{S\subseteq\left[k\right]}$ is a
$\left(\beta,\alpha,\epsilon^{\prime}\right)$-bounded approximate Efron–Stein
decomposition for $f$, we obtain that $\left\\{f_{T}\right\\}_{T\supseteq S}$
is a $\left(\tilde{\beta},\tilde{\alpha},\tilde{\epsilon}\right)$-bounded
approximate Efron–Stein decomposition for suitable values of
$\tilde{\beta},\tilde{\alpha},\tilde{\epsilon}$. We show the following.

######  Lemma 6.6.

There exists $C=O_{k}\left(1\right)$, such that the following holds. Suppose
that $\left\\{f_{T}\right\\}_{T\subseteq\left[k\right]}$ is a
$\left(\beta,\alpha,\epsilon^{\prime}\right)$-Approximate Efron–Stein
decomposition for $f$. Then $\left\\{f_{T}\right\\}_{T\supseteq S}$ is a
$\left(C\beta,\alpha,C\left(\epsilon^{\prime}+\alpha\sqrt{\epsilon}\right)\right)$-Approximate
Efron–Stein decomposition for $L_{S}\left[f\right].$

###### Proof.

The only requirements that are not automatically inherited from $f$ are the
upper bounds on $\|L_{S}\left[f\right]\|_{\infty}$, and on
$\|L_{S}f-\sum_{T\supseteq S}f_{T}\|_{2}.$ The former inequality follows from
the inequality

$\|L_{S}\left[f\right]\|_{\infty}\leq 2^{\left|S\right|}\|f\|_{\infty}\leq
2^{k}\beta.$

While the latter follows from Lemma 4.11 and the triangle inequality:

$\displaystyle\|L_{S}f-\sum_{T\supseteq S}f_{T}\|_{2}$
$\displaystyle=\|\sum_{T\supseteq S}\left(f^{=T}-f_{T}\right)\|_{2}.$
$\displaystyle\leq\sum_{T\supseteq S}\|f^{=T}-f_{T}\|_{2}$ $\displaystyle\leq
O_{k}\left(\epsilon^{\prime}\right)+O_{k}\left(\alpha\sqrt{\epsilon}\right).$

∎

###  6.3. Low degree functions and truncations

######  Definition 6.7.

We define the _low degree part_ of $f$ by setting

$f^{\leq d}=\sum_{\left|S\right|\leq d}f^{=S}$

we define the _low degree Laplacians_ of $f$ by setting

$L_{T}^{\leq d}\left[f\right]=\sum_{S\supseteq T,\left|S\right|\leq d}f^{=T}.$

We now show that if $\left\\{f_{T}\right\\}_{T\subseteq\left[k\right]}$ is a
$\left(\beta,\alpha,\epsilon^{\prime}\right)$bounded approxiate Efron–Stein
decomposition for $f$, then we may turn it into an Efron–Stein decomposition
for $f^{\leq d}$ and $L_{S}^{\leq d}\left[f\right]$ in the obvious way.

######  Lemma 6.8.

There exists $C=O_{k}\left(1\right)$, such that the following holds. Suppose
that $\left\\{f_{T}\right\\}_{T\subseteq\left[k\right]}$ is a
$\left(\beta,\alpha,\epsilon^{\prime}\right)$-Approximate Efron–Stein
decomposition for $f$. Then

  1. (1)

The functions $\left\\{f_{T}\right\\}_{\left|T\right|\leq d}$ are a
$\left(C\beta,\alpha,C\epsilon+C\epsilon^{\prime}\right)$-approximate
Efron–Stein decomposition for $f^{\leq d}.$

  2. (2)

the functions $\left\\{f_{T}\right\\}_{\left|T\right|\supseteq
S,\left|T\right|\leq d}$ are a
$\left(C\beta,\alpha,C\epsilon+C\epsilon^{\prime}\right)$-approximate
Efron–Stein decomposition for $L_{S}^{\leq d}\left[f\right].$

###### Proof.

It is sufficient to prove (2) as (1) is the special case where
$S=\varnothing.$ By Lemma 4.11, we have

$\|f_{T}-f^{=T}\|_{2}\leq
O_{k}\left(\epsilon^{\prime}\right)+O_{k}\left(\sqrt{\epsilon}\alpha\right).$

Hence, by the triangle inequality we have

$\displaystyle\|L_{S}^{\leq d}\left[f\right]-\sum_{T\supseteq
S,\left|T\right|\leq d}f_{T}\|_{2}$ $\displaystyle\leq\sum_{T\supseteq
S,\left|T\right|\leq d}\|f^{=T}-f_{T}\|_{2}$
$\displaystyle=O_{k}\left(\epsilon^{\prime}\right)+O_{k}\left(\sqrt{\epsilon}\alpha\right).$

Moreover,

$\displaystyle\|L_{S}^{\leq d}\left[f\right]\|_{\infty}$
$\displaystyle=\left\|\sum_{T\supseteq S,\left|T\right|\leq
d}f^{=T}\right\|_{\infty}$ $\displaystyle\leq
2^{k}\max_{S}\|f^{=S}\|_{\infty}$ $\displaystyle\leq 4^{k}\|f\|_{\infty}\leq
4^{k}\beta.$

∎

###  6.4. Globalness

Unlike the product space setting the two possible definitions of globalness
are not equivalent. It turns out to be more convenient to work with the notion
concerning the restrictions.

######  Definition 6.9.

We say that $f$ is $\left(d,\delta\right)$-global if for each
$\left|S\right|\leq d$ and each $x\in V_{S}$ we have

$\|f\left(x,\cdot\right)\|_{L^{2}\left(V_{x},\mu_{x}\right)}\leq\delta.$

######  Claim 6.10.

If $f$ is $\left(d,\delta\right)$-global and $\epsilon$ is sufficiently small,
then for each $T$ of size $\leq d$ we have

$\|f^{=T}\|_{\infty}\leq 2^{\left|T\right|}\delta.$

###### Proof.

This follows from the triangle inequality once we show that
$\|A_{T^{\prime}}f\|_{\infty}\leq\delta$ for each $T^{\prime}\subseteq T$.
Indeed, for each $x$ we have

$A_{T^{\prime}}f\left(x\right)=\mathbb{E}_{\left(V_{x},\mu_{x}\right)}f\left(x,\cdot\right)\leq\|f\left(x,\cdot\right)\|_{L^{2}\left(V_{x},\mu_{x}\right)}\leq\delta.$

∎

######  Lemma 6.11.

Suppose that $f$ is $\left(d,\delta\right)$-global. Then
$\left\\{f^{=S}\right\\}_{\left|S\right|\leq d}$ is a
$\left(k^{d}\delta,\|f\|_{2},0\right)$-bounded Efron–Stein decomposition for
$f^{\leq d}.$

###### Proof.

We have $\|f^{=S}\|_{\infty}\leq 2^{d}\delta$ by Claim 6.10. We also have

$\|f\|_{\infty}\leq\sum\|f^{=S}\|_{\infty}\leq k^{d}\delta.$

The rest of the conditions hold automatically. ∎

######  Definition 6.12.

We say that $f$ is of $\left(\beta,\alpha\right)$-degree $d$ if
$f=\sum_{\left|S\right|\leq d}f_{S}$ and $f_{S}=h_{S}^{=S}$ where
$\|h_{S}\|_{2}\leq\alpha$, $\|h_{S}^{=S}\|_{\infty}\leq\beta$ and
$\|f\|_{2}\leq\alpha,\|f\|_{\infty}\leq\beta.$

If $f=\sum_{\left|S\right|\leq d}f_{S}$ is of
$\left(\beta,\alpha\right)$-degree $d$ as above, then $\left\\{f_{S}\right\\}$
is one $\left(\beta,\alpha,0\right)$-bounded Efron–Stein decomposition for
$f.$ We now show that in this case the canonical
$\left\\{f^{=S}\right\\}_{\left|S\right|\leq d}$ is also
$\left(\beta^{\prime},\alpha^{\prime},\epsilon^{\prime}\right)$-bounded
Efron–Stein decomposition for the right parameters.

###  6.5. Other approximate Efron-Stein decompositions for
$L_{T}\left[f\right],L_{T}^{\leq d}\left[f\right]$

######  Definition 6.13.

We define the low degree derivatives for $T\subseteq\left[k\right]$ and $x\in
V_{T}$

$D_{T,x}^{\leq d}\colon L^{2}\left(\mu\right)\to
L^{2}\left(V_{x},\mu_{x}\right)$

via

$D_{T,x}^{\leq d}\left[f\right]=L_{T}^{\leq
d}\left[f\right]\left(x,\cdot\right)$

The low degree influences for $T\subseteq\left[n\right]$ and $x\in V_{T}$ are
defined by

$I_{T,x}^{\leq d}\left[f\right]=\|L_{T}^{\leq
d}\left[f\right]\left(x,\cdot\right)\|_{L^{2}\left(V_{x},\mu_{x}\right)}^{2}.$

We now move on to the critical lemma for our inductive approach. In the
product space setting our inductive approach relied on the fact that
$D_{T,x}f$ is of degree $\leq d-\left|T\right|$ whenever $f$ is of degree $d.$
Here we show that $L_{T}\left[f\right]$ has an alternative
$\left(\beta,\alpha,\epsilon\right)$-bounded approximate Efron–Stein
decompositions $\left\\{f_{S}\right\\}_{S\supseteq T}$ that gives rise to a
function

$\widetilde{L_{T}^{\leq d}\left[f\right]}=\sum_{S\supseteq
T,\left|S\right|\leq d}f^{=S}$

with the property that for each $x$ $\widetilde{L_{T}^{\leq
d}\left[f\right]}\left(x,\cdot\right)$ is of degree $d-\left|T\right|$.

######  Lemma 6.14.

Let $f_{S}\left(x,y\right)=D_{T,x}^{=S\setminus T}[f](y).$ Then for each $f$:

  1. (1)

The set $\left\\{f_{S}\right\\}_{S\supseteq T}$ is a
$\left(C\|f\|_{\infty},C\|f\|_{2},C\epsilon\|f\|_{2}\right)$-bounded
approximate Efron–Stein decomposition for $L_{T}\left[f\right].$

  2. (2)

The set $\left\\{f_{S}\right\\}_{S\supseteq T,\left|S\right|\leq d}$ is a
$\left(C\|f\|_{\infty},C\|f\|_{2},C\epsilon\|f\|_{2}\right)$-bounded
approximate Efron–Stein decomposition for $L_{T}^{\leq d}\left[f\right].$

  3. (3)

If $T^{\prime}\supseteq T$, then the set $\left\\{f_{S}\right\\}_{S\supseteq
T^{\prime}}$ is a
$\left(C\|f\|_{\infty},C\|f\|_{2},C\epsilon\|f\|_{2}\right)$-bounded
approximate Efron Stein decomposition for $L_{T^{\prime}}\left[f\right].$

  4. (4)

The set $\left\\{f_{S}\right\\}_{S\supseteq T^{\prime},\left|S\right|\leq d}$
is a $\left(C\|f\|_{\infty},C\|f\|_{2},C\epsilon\|f\|_{2}\right)$-bounded
approximate Efron–Stein decomposition for $L_{T^{\prime}}^{\leq
d}\left[f\right].$

  5. (5)

If $f$ is $\left(d,\delta\right)$-global. Then
$\left\\{f_{S}\right\\}_{S\supseteq T^{\prime},\left|S\right|\leq d}$ is a
$\left(C\delta,C\|f\|_{2},C\epsilon\|f\|_{2}\right)$-bounded approximate
Efron–Stein decomposition for $L_{T^{\prime}}^{\leq d}\left[f\right].$

###### Proof.

Due to Lemma 6.8 (1) implies (2)-(4). By Lemma 4.3 all the operators $A_{I}$
contract $\infty$-norms. We therefore have

$\|f_{S}\|_{\infty}\leq\max_{x}2^{\left|S\setminus
T\right|}\|D_{T,x}f\|_{\infty}=2^{\left|S\setminus
T\right|}\|L_{T}f\|_{\infty}\leq 2^{\left|S\right|}\|f\|_{\infty}.$

To complete the proof it is sufficient to show that

$\|f_{S}-f^{=S}\|_{2}\leq O_{k}\left(\epsilon\|f\|_{2}\right)$

as this will also imply that

$\displaystyle\|\sum_{S\supseteq T}f_{S}-L_{T}\left[f\right]\|_{2}$
$\displaystyle=\|\sum_{S\supseteq T}f_{S}-\sum_{S\supseteq T}f^{=S}\|_{2}$
$\displaystyle=O_{k}\left(\epsilon\|f\|_{2}\right).$

We have

$\displaystyle f_{S}$ $\displaystyle=\sum_{S^{\prime}\subseteq
S}\left(-1\right)^{\left|S\setminus S^{\prime}\right|}A_{S^{\prime}}L_{T}f.$
$\displaystyle=\sum_{S^{\prime}\subseteq S}\sum_{T^{\prime}\subseteq
T}\left(-1\right)^{\left|S\setminus
S^{\prime}\right|+\left|T^{\prime}\right|}A_{S^{\prime}}A_{[k]\setminus
T^{\prime}}f.$

Write

$\displaystyle h$ $\displaystyle=\sum_{S^{\prime}\subseteq
S}\sum_{T^{\prime}\subseteq T}\left(-1\right)^{\left|S\setminus
S^{\prime}\right|+\left|T^{\prime}\right|}A_{S^{\prime}\setminus T^{\prime}}f$

Then by Lemma 3.4 we have

$\|f_{S}-h\|_{2}\leq O_{k}\left(\epsilon\right)\|f\|_{2}.$

We then observe that whenever $S^{\prime}\not\supseteq T$ the inner sum
corresponding to it is $0.$ In this case there is some $i\in T\setminus
S^{\prime}$ and $T^{\prime},T^{\prime}\cup\left\\{i\right\\}$ appear with
alternating signs and correspond to the same term $A_{S^{\prime}\setminus
T^{\prime}}.$ Therefore we have

$\displaystyle h$ $\displaystyle=\sum_{T\subseteq S^{\prime}\subseteq
S}\sum_{T^{\prime}\subseteq T}\left(-1\right)^{\left|S\setminus
S^{\prime}\right|+\left|T^{\prime}\right|}A_{S^{\prime}\setminus
T^{\prime}}f=\sum_{S^{\prime\prime}\subseteq
S}\left(-1\right)^{\left|S\setminus
S^{\prime\prime}\right|}A_{S^{\prime\prime}}f=f^{=S}.$

This shows that $\|f_{S}-f^{=S}\|_{2}\leq
O_{k}\left(\epsilon\right)\|f\|_{2},$ which completes the proof. ∎

###  6.6. Globalness implies small influences

In the product space setting we had $\|I_{T,x}\|_{\infty}\leq 4^{d}\delta^{2}$
and we used it via the inequality

(6.1)
$\mathbb{E}_{x\sim\mu_{T}}\left[I_{T,x}^{2}\right]\leq\mathbb{E}_{x\sim\mu_{T}}\left[I_{T,x}\right]4^{d}\delta^{2}=4^{d}\delta^{2}\|L_{T}\left[f\right]\|_{2}^{2}.$

See the proof of Corollary 2.6. Here we find a convoluted way of proving an
analogue of (6.1) without having any upper bound on $\|I_{T,x}\|_{\infty}$ at
our disposal.

######  Lemma 6.15.

Suppose that $f\colon V_{\left[k\right]}\to\mathbb{R}$ is
$\left(d,\delta\right)$-global, and let $\left|T\right|\leq d$. Then

$\mathbb{E}_{x\sim\mu_{T}}\left[\left(I_{T,x}\left[f\right]\right)^{2}\right]\leq
2^{d+1}\delta^{2}\mathbb{E}_{x\sim\mu_{T}}I_{T,x}+O_{k}\left(\epsilon^{2}\|f\|_{4}^{4}\right).$

###### Proof.

Write $g\left(x\right)=I_{T,x}\left[f\right].$ Then
$g=A_{T}\left[\left(L_{T}\left[f\right]\right)^{2}\right].$ We would like to
upper bound $\|g\|_{2}^{2}.$ We accomplish that by upper bounding
$\|g\|_{2}^{2}$ by $\mathbb{E}\left[gg^{\prime\prime}\right]$ for a function
$g^{\prime\prime}$ with a small $\infty$-norm.

By Cauchy–Schwarz we have

$L_{T}\left[f\right]^{2}\leq
2^{\left|T\right|}\sum_{T^{\prime}\supseteq\overline{T}}A_{T^{\prime}}\left[f\right]^{2}.$

This shows that

(6.2) $g\leq 2^{\left|T\right|}\sum_{T^{\prime}\subseteq
T}A_{T}\left[\left(A_{T^{\prime}}f\right)^{2}\right],$

on all $x$. Let us denote by $g^{\prime}$ the right hand side of 6.2. Also let

$g^{\prime\prime}=2^{\left|T\right|}\sum_{T^{\prime}\subseteq T}A_{T\cap
T^{\prime}}\left[\left(A_{T^{\prime}}f\right)^{2}\right].$

Then in the product space setting the functions $g^{\prime},g^{\prime\prime}$
would have been equal. Here we have an $L^{2}-$approximation between them.

######  Claim 6.16.

$\|g^{\prime}-g^{\prime\prime}\|_{2}\leq
O_{k}\left(\epsilon\right)\|f\|_{4}^{2}.$

###### Proof.

As $\left(A_{T^{\prime}}f\right)^{2}$ is a $T^{\prime}$-junta we have

$\left(A_{T^{\prime}}f\right)^{2}=A_{T^{\prime}}\left[\left(A_{T^{\prime}}f\right)^{2}\right].$

By Lemma 3.4 we have

$\|A_{T}A_{T^{\prime}}-A_{T\cap T^{\prime}}\|_{2\to 2}\leq
O_{k}\left(\epsilon\right).$

We therefore have

$\displaystyle\|A_{T}\left[\left(A_{T^{\prime}}f\right)^{2}\right]-A_{T\cap
T^{\prime}}\left[\left(A_{T^{\prime}}f\right)^{2}\right]\|_{2}^{2}$
$\displaystyle\leq
O_{k}\left(\epsilon^{2}\right)\|\left(A_{T^{\prime}}f\right)^{2}\|_{2}^{2}$
$\displaystyle\leq O_{k}\left(\epsilon^{2}\right)\|f\|_{4}^{4},$

as $A_{T^{\prime}}$ contracts $4$-norms. Therefore,

$\|g^{\prime}-g^{\prime\prime}\|_{2}\leq
O_{k}\left(\epsilon\right)\|f\|_{4}^{2}.$

∎

As $0\leq g\leq g^{\prime}$ we have

$\mathbb{E}\left[g^{2}\right]\leq\mathbb{E}\left[g^{\prime}g\right]\leq\mathbb{E}\left[g^{\prime\prime}g\right]+\mathbb{E}\left[\left(g^{\prime}-g^{\prime\prime}\right)g\right].$

By Cauchy–Schwarz we have

$\mathbb{E}\left[\left(g^{\prime}-g^{\prime\prime}\right)g\right]\leq\|g^{\prime}-g^{\prime\prime}\|_{2}\|g\|_{2}\leq
O_{k}\left(\epsilon\right)\|f\|_{4}^{2}\|g\|_{2}.$

Now either

(6.3) $\mathbb{E}\left[g^{2}\right]\leq
2\mathbb{E}\left[g^{\prime\prime}g\right]$

or

$\mathbb{E}\left[g^{2}\right]\leq
2\mathbb{E}\left[\left(g^{\prime}-g^{\prime\prime}\right)g\right]\leq
O_{k}\left(\epsilon\right)\|f\|_{4}^{2}\|g\|_{2}.$

In the latter case we have

(6.4) $\|g\|_{2}^{2}\leq O_{k}\left(\epsilon^{2}\right)\|f\|_{4}^{4}.$

after rearranging. We can now sum the upper bounds of (6.3) and (6.4)
corresponding to each of the cases to obtain the upper bound

$\mathbb{E}\left[g^{2}\right]\leq
2\mathbb{E}\left[g^{\prime\prime}g\right]+O_{k}\left(\epsilon^{2}\right)\|f\|_{4}^{4}.$

that is true in both cases. The following claim completes the proof.

######  Claim 6.17.

$\|g^{\prime\prime}\|_{\infty}\leq 2^{d}\delta^{2}.$

###### Proof.

By Cauchy–Schwarz we point-wise have $\left(A_{T^{\prime}}f\right)^{2}\leq
A_{T^{\prime}}\left(f^{2}\right).$ We therefore have

$A_{T\cap T^{\prime}}\left[\left(A_{T^{\prime}}f\right)^{2}\right]\leq
A_{T\cap T^{\prime}}A_{T^{\prime}}\left(f^{2}\right)=A_{T\cap
T^{\prime}}\left(f^{2}\right)\leq\delta^{2}.$

This shows that $\|g^{\prime\prime}\|_{\infty}\leq 2^{d}\delta^{2}.$ ∎

∎

The same proof works for the truncated influences.

######  Lemma 6.18.

Suppose that $f\colon V_{\left[k\right]}\to\mathbb{R}$ is
$\left(d,\delta\right)$-global. Suppose additionally that
$\epsilon\leq\epsilon_{0}\left(k\right)$. Then we have

$\mathbb{E}_{x\sim\mu_{T}}\left[\left(I_{T,x}^{\leq
d}\left[f\right]\right)^{2}\right]\leq
2^{d+4}\delta^{2}\mathbb{E}_{x\sim\mu_{T}}\left[I_{T,x}^{\leq
d}\right]+O_{k}\left(\epsilon^{2}\|f\|_{\infty}^{2}\|f\|_{2}^{2}\right).$

###### Proof.

Write

$g_{1}\left(x\right)=\|\left(D_{T,x}\left[f\right]\right)^{\leq
d-\left|T\right|}\|_{2}^{2}.$

We now proceed with the following steps.

### Upper bounding $\mathbb{E}_{x\sim\mu_{T}}\left[\left(I_{T,x}^{\leq
d}\left[f\right]\right)^{2}\right]$ in terms of $g_{1}$

By Lemma 6.14 the functions

$\left\\{D_{T,x}\left[f\right]^{=S}\right\\}_{\left|S\right|\leq
d-\left|T\right|},$

is an alternative
($O_{k}\|f\|_{\infty},O_{k}\|f\|_{2},O_{k}\left(\epsilon\|f\|_{2}\right)$)-bounded
approximate Efron–Stein decomposition for $L_{T}^{\leq d}\left[f\right]$.
Therefore by Lemma 6.5 we have

(6.5) $\displaystyle\mathbb{E}_{x\sim\mu_{T}}\left[I_{T,x}^{\leq
d}\left[f\right]^{2}\right]$ $\displaystyle\leq
2\mathbb{E}_{x\sim\mu_{T}}\left[g_{1}\left(x\right)^{2}\right]+O_{k}\left(\epsilon\|f\|_{2}^{2}\|f\|_{\infty}^{2}\right).$

### Repeating the proof of Lemma 6.18

Now by Lemma 4.9 we have $g_{1}\left(x\right)\leq 2I_{T,x}$ for each $x$,
provided that $\epsilon$ is sufficiently small. Write
$g_{2}\left(x\right)=I_{T,x}\left[f\right].$ Similarly to the proof of Lemma
6.18 we let

$g_{2}^{\prime}=2^{\left|T\right|}\sum_{T^{\prime}\subseteq
T}A_{T}\left[\left(A_{T^{\prime}}f\right)^{2}\right]$

and let

$g_{2}^{\prime\prime}=2^{\left|T\right|}\sum_{T^{\prime}\subseteq T}A_{T\cap
T^{\prime}}\left[\left(A_{T^{\prime}}f\right)^{2}\right].$

By Cauchy–Schwarz we have

$\displaystyle\|g_{1}\|_{2}^{2}\leq 2\mathbb{E}\left[g_{1}g_{2}\right]$
$\displaystyle\leq 2\mathbb{E}\left[g_{1}g_{2}^{\prime}\right]\leq
2\mathbb{E}\left[g_{1}g_{2}^{\prime\prime}\right]+2\mathbb{E}\left[g_{1}\left(g_{2}^{\prime}-g_{2}^{\prime\prime}\right)\right].$

Now either

$\|g_{1}\|_{2}^{2}\leq 4\mathbb{E}\left[g_{2}^{\prime\prime}g_{1}\right],$

which would imply

$\|g_{1}\|_{2}^{2}\leq 4\mathbb{E}\left[g_{2}^{\prime\prime}g_{1}\right]\leq
2^{d+2}\delta\mathbb{E}\left[g_{1}\right]$

by Claim 6.17, or

$\displaystyle\|g_{1}\|_{2}^{2}$ $\displaystyle\leq
4\mathbb{E}\left[g_{1}\left(g_{2}^{\prime}-g_{2}^{\prime\prime}\right)\right]\leq
4\|g_{1}\|_{2}\|g_{2}^{\prime}-g_{2}^{\prime\prime}\|_{2}$

and rearranging, we obtain

$\|g_{1}\|_{2}^{2}\leq 16\|g_{2}^{\prime}-g_{2}^{\prime\prime}\|_{2}^{2}\leq
O_{k}\left(\epsilon^{2}\|f\|_{4}^{4}\right)$

by Claim 6.16. This shows that

(6.6) $\|g_{1}\|_{2}^{2}\leq
2^{d+2}\delta\mathbb{E}\left[g_{1}\right]+O_{k}\left(\epsilon^{2}\|f\|_{4}^{4}\right).$

### Moving back from $g_{1}$ to $I_{T,x}^{\leq d}$

By Lemmas 6.14 we have

$\|\left(D_{T,x}\left[f\right]\right)^{\leq d-\left|T\right|}-D_{T,x}^{\leq
d}\left[f\right]\|_{2}^{2}\leq O_{k}\left(\epsilon^{2}\|f\|_{2}^{2}\right)$

yielding

(6.7) $\displaystyle\mathbb{E}\left[g_{1}\right]$ $\displaystyle\leq
2\|D_{T,x}^{\leq
d}\left[f\right]\|_{2}^{2}+O_{k}\left(\epsilon^{2}\|f\|_{2}^{2}\right)$
$\displaystyle=2\mathbb{E}_{x\sim\mu_{T}}I_{T,x}^{\leq
d}\left[f\right]+O_{k}\left(\epsilon^{2}\right)\|f\|_{2}^{2}$

by the triangle inequality and Cauchy–Schwarz. By combining (6.5), (6.6) with
(6.7) we obtain

$\displaystyle\mathbb{E}_{x\sim\mu_{T}}\left[I_{T,x}^{\leq
d}\left[f\right]^{2}\right]$ $\displaystyle\leq
2\|g_{1}\|_{2}^{2}+O_{k}\left(\epsilon\|f\|_{2}^{2}\|f\|_{\infty}^{2}\right).$
$\displaystyle\leq
2^{d+3}\delta^{2}\mathbb{E}\left[g_{1}\right]+O_{k}\left(\epsilon^{2}\|f\|_{2}^{2}\|f\|_{\infty}^{2}\right)+O_{k}\left(\epsilon^{2}\|f\|_{4}^{4}\right)$
$\displaystyle\leq
2^{d+3}\delta^{2}\mathbb{E}\left[g_{1}\right]+O_{k}\left(\epsilon^{2}\|f\|_{2}^{2}\|f\|_{\infty}^{2}\right).$

The lemma now follows by putting everything together. ∎

##  7\. Proving hypercontractivity for $\epsilon$-product measures

We suggest revisiting Section 2 before reading this section. Our strategy is
the same as in the product case, and we deal with the differences by appealing
to the tools developed in Sections 3-6.

###  7.1. Upper bounding $\|f^{\leq d}\|_{4}^{4}$ by $4$-norms of non-trivial
Laplacians and $\|f^{\leq d}\|_{2}^{4}$

We now move on to preparing the ground for the proof of our hypercontractive
inequality.

######  Lemma 7.1.

Let $f$ be $\left(d,\delta\right)$-global. Suppose that
$\epsilon\leq\epsilon_{0}\left(k\right)$. Then we have

$\frac{1}{2}\|f^{\leq d}\|_{4}^{4}\leq 9^{d}\|f^{\leq
d}\|_{2}^{4}+4\sum_{0<\left|T\right|\leq
d}\left(4d\right)^{\left|T\right|}\|L_{T}^{\leq
d}\left[f\right]\|_{4}^{4}+O_{k}\left(\epsilon\right)\|f\|_{2}^{2}\|f\|_{\infty}^{2}.$

###### Proof.

Let $g=f^{\leq d}.$ By Lemma 4.9 we have

$\|g\|_{4}^{4}\leq 2\sum_{S}\|\left(g^{2}\right)^{=S}\|_{2}^{2}.$

We now upper bound $\|\left(g^{2}\right)^{=S}\|_{2}^{2}.$ We have

$\left(g^{2}\right)^{=S}=\sum_{\left|T_{1}\right|\leq d,\left|T_{2}\right|\leq
d}\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}.$

Let

  1. (1)

$I_{1}=\left\\{\left(T_{1},T_{2}\right):T_{1}\cap T_{2}\cap
S\neq\varnothing\right\\}.$

  2. (2)

$I_{2}=\left(\left(T_{1},T_{2}\right):T_{1}\Delta T_{2}=S\right)$

  3. (3)

$I_{3}=\left(T_{1}\Delta T_{2}\right)\setminus S\neq\varnothing$ or
$S\setminus\left(T_{1}\cup T_{2}\right)\neq\varnothing$.

Our first step is to show that the contribution from $I_{3}$ is negligible.
This is to be expected as in the product space setting we were able to show
that the contribution from $I_{3}$ is 0.

######  Claim 7.2.

Let $\left(T_{1},T_{2}\right)\in I_{3}$. Then

$\|\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}\|_{2}^{2}\leq
O_{k}\left(\epsilon^{2}\right)\|f\|_{2}^{2}\|f\|_{\infty}^{2}.$

###### Proof.

Suppose first that $\left(T_{1}\Delta T_{2}\right)\setminus S\neq\varnothing.$
Then without loss of generality we may assume that there is some $i\in
T_{1}\setminus\left(T_{2}\cup S\right).$ By Lemma 4.9 we have

$\|\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}\|_{2}^{2}\leq
2\|A_{\left[k\right]\setminus\left\\{i\right\\}}\left(f^{=T_{1}}f^{=T_{2}}\right)\|_{2}^{2}.$

Now

$A_{\left[k\right]\setminus\left\\{i\right\\}}\left(f^{=T_{1}}f^{=T_{2}}\right)=\left(A_{\left[k\right]\setminus\left\\{i\right\\}}\left(f^{=T_{1}}\right)\right)f^{=T_{2}}.$

By Lemma 4.7 we have

$\|A_{\left[k\right]\setminus\left\\{i\right\\}}f^{=T_{1}}\|_{2}\leq\sum_{T^{\prime}\not\ni
i}\|\left(f^{=T_{1}}\right)^{=T^{\prime}}\|_{2}\leq
O_{k}\left(\epsilon\right)\|f\|_{2}.$

This shows that

$\displaystyle\|A_{\left[k\right]\setminus\left\\{i\right\\}}\left(f^{=T_{1}}f^{=T_{2}}\right)\|_{2}^{2}$
$\displaystyle\leq\|A_{\left[k\right]\setminus\left\\{i\right\\}}f^{=T_{1}}\|_{2}^{2}\|f^{=T_{2}}\|_{\infty}^{2}$
$\displaystyle\leq
O_{k}\left(\epsilon^{2}\right)\|f\|_{\infty}^{2}\|f\|_{2}^{2}.$

Suppose now that $S\setminus\left(T_{1}\cup T_{2}\right)\neq\varnothing.$ Let
$i\in S\setminus\left(T_{1}\cup T_{2}\right).$ Then the function
$g=f^{=T_{1}}f^{=T_{2}}$ is a $T_{1}\cup T_{2}$-junta. This shows that
$g=A_{T_{1}\cup T_{2}}g.$

Hence by Lemma 4.7 and the triangle inequality we have

$\displaystyle\|g^{=S}\|_{2}$ $\displaystyle=\|\left(A_{T_{1}\cup
T_{2}}g\right)^{=S}\|_{2}$ $\displaystyle\leq\|\sum_{T\subseteq T_{1}\cup
T_{2}}\left(g^{=T}\right)^{=S}\|_{2}$ $\displaystyle\leq
O_{k}\left(\epsilon\right)\|g\|_{2}.$

It now remains to note that
$\|g\|_{2}^{2}\leq\|f^{=T_{1}}\|_{2}\|f^{=T_{2}}\|_{\infty}\leq
2^{2k}\|f\|_{2}\|f\|_{\infty}.$ ∎

We now move on to our next step of upper bounding the contribution from the
pairs in $I_{1}.$

######  Claim 7.3.

$\sum_{\left(T_{1},T_{2}\right)\in
I_{1}}\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}=\sum_{T\subseteq
S}\left(-1\right)^{\left|T\right|+1}\|\left(L_{T}^{\leq
d}\left[f\right]^{2}\right)^{=S}\|_{2}^{2}.$

###### Proof.

The proof is exactly the same as in the product case so we omit it. ∎

It now remains to consider the contribution from $I_{2}$, i.e. the case
$T_{1}\Delta T_{2}=S$ . Here just like the product case it is sufficient to
show the following claim

######  Claim 7.4.

Let $T_{1}\Delta T_{2}=S$. Then we have

$\|\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}\|_{2}\leq
2\|f^{=T_{1}}\|_{2}\|f^{=T_{2}}\|_{2}+O_{k}\left(\epsilon\right)\|f\|_{2}\|f\|_{\infty},$

provided that $\epsilon$ is sufficiently small.

###### Proof.

First let $S^{\prime}\subsetneq S.$ As $T_{1}\Delta T_{2}=S$, there exists
$i\in\left(T_{1}\Delta T_{2}\right)\setminus S^{\prime}.$ Without loss of
generality $i\in T_{1}.$ By Lemmas 4.9, 4.7, and 4.2 we have

$\displaystyle\|A_{S^{\prime}}\left(f^{=T_{1}}f^{=T_{2}}\right)\|_{2}$
$\displaystyle\leq 2\|A_{S^{\prime}\cup
T_{2}}\left(f^{=T_{1}}f^{=T_{2}}\right)\|_{2}$ $\displaystyle\leq
2\|A_{S^{\prime}\cup T_{2}}f^{=T_{1}}\|_{2}\|f^{=T_{2}}\|_{\infty}$
$\displaystyle\leq O_{k}\left(\epsilon\right)\|f\|_{2}\|f\|_{\infty}.$

By the triangle inequality this shows that

$\displaystyle\|\left(f^{=T_{1}}f^{=T_{2}}\right)^{=S}\|_{2}$
$\displaystyle\leq\sum_{S^{\prime}}\left(-1\right)^{\left|S\setminus
S^{\prime}\right|}A_{S^{\prime}}\left(f^{=T_{1}}f^{=T_{2}}\right).$
$\displaystyle\leq\|A_{S}\left(f^{=T_{1}}f^{=T_{2}}\right)\|_{2}+O_{k}\left(\epsilon\right)\|f\|_{2}\|f\|_{\infty}$

We now upper bound $\|A_{S}\left(f^{=T_{1}}f^{=T_{2}}\right)\|_{2}.$

By Cauchy–Schwarz for $x\in V_{S}$ we have

$\displaystyle A_{S}\left(f^{=T_{1}}f^{=T_{2}}\right)\left(x\right)$
$\displaystyle=\left\langle
f^{=T_{1}}\left(x,\cdot\right),f^{=T_{2}}\left(x,\cdot\right)\right\rangle_{L^{2}\left(V_{x},\mu_{x}\right)}$
$\displaystyle\leq\|f^{=T_{1}}\left(x,\cdot\right)\|_{L^{2}\left(V_{x},\mu_{x}\right)}\|f^{=T_{2}}\left(x,\cdot\right)\|_{L^{2}\left(V_{x},\mu_{x}\right)}.$

This shows that

(7.1) $\displaystyle\|A_{S}\left(f^{=T_{1}}f^{=T_{2}}\right)\|_{2}^{2}$
$\displaystyle\leq\mathbb{E}_{x\sim\mu_{S}}\left[\|f^{=T_{1}}\left(x,\cdot\right)\|_{L^{2}\left(V_{x},\mu_{x}\right)}^{2}\|f^{=T_{2}}\left(x,\cdot\right)\|_{L^{2}\left(V_{x},\mu_{x}\right)}^{2}\right].$

We have

$\|f^{=T_{1}}\left(x,\cdot\right)\|_{L^{2}\left(V_{x},\mu_{x}\right)}^{2}=A_{S}\left[\left(f^{=T_{1}}\right)^{2}\right]=A_{S}A_{T_{1}}\left(f^{=T_{1}}\right)^{2}$

By Lemma 3.4

$\|A_{S}A_{T_{1}}-A_{S\cap T_{1}}\|_{2\to 2}\leq O_{k}\left(\epsilon\right).$

Hence,

$\displaystyle\|A_{S}A_{T_{1}}\left(f^{=T_{1}}\right)^{2}-A_{S\cap
T_{1}}\left[\left(f^{=T_{1}}\right)^{2}\right]\|_{2}^{2}$ $\displaystyle\leq
O_{k}\left(\epsilon^{2}\|f^{=T_{1}}\|_{4}^{4}\right)$ $\displaystyle\leq
O_{k}\left(\epsilon^{2}\|f\|_{2}^{2}\|f\|_{\infty}^{2}\right).$

By Cauchy–Schwarz this shows that

RHS of (7.1) $\displaystyle=\left\langle
A_{S}A_{T_{1}}\left(f^{=T_{1}}\right)^{2},A_{S}\left(f^{=T_{2}}\right)^{2}\right\rangle_{L^{2}\left(V_{S},\mu_{S}\right)}$
$\displaystyle=\left\langle A_{S\cap
T_{1}}\left(f^{=T_{1}}\right)^{2},A_{S}\left(f^{=T_{2}}\right)^{2}\right\rangle_{L^{2}\left(V_{S},\mu_{S}\right)}$
$\displaystyle+O_{k}\left(\epsilon\|f\|_{2}\|f\|_{\infty}\right)\|A_{S}\left(f^{=T_{2}}\right)^{2}\|_{2}.$

As we have

$\|A_{S}\left(f^{=T_{2}}\right)^{2}\|_{2}^{2}\leq
O_{k}\left(\|f\|_{4}^{4}\right)\leq
O_{k}\left(\|f\|_{2}^{2}\|f\|_{\infty}^{2}\right).$

Therefore,

$\displaystyle\|A_{S}\left(f^{=T_{1}}f^{=T_{2}}\right)\|_{2}^{2}$
$\displaystyle\leq\left\langle A_{S\cap
T_{1}}\left(f^{=T_{1}}\right)^{2},A_{S}\left(f^{=T_{2}}\right)^{2}\right\rangle_{L^{2}\left(V_{S},\mu_{S}\right)}+O_{k}\left(\epsilon\|f\|_{2}^{2}\|f\|_{\infty}^{2}\right)$
$\displaystyle=\left\langle A_{S\cap
T_{1}}\left(f^{=T_{1}}\right)^{2},A_{S\cap
T_{1}}\left(f^{=T_{2}}\right)^{2}\right\rangle_{L^{2}\left(\mu\right)}+O_{k}\left(\epsilon\|f\|_{2}^{2}\|f\|_{\infty}^{2}\right).$

Now

$A_{S\cap T_{1}}\left(f^{=T_{2}}\right)^{2}=A_{S\cap
T_{1}}A_{T_{2}}\left(f^{=T_{2}}\right)^{2}$

and $\|A_{S\cap T_{1}}A_{T_{2}}-\mathbb{E}\|_{2\to 2}\leq\epsilon$ by Lemma
3.4. Therefore we similarly have

$\displaystyle\left\langle A_{S\cap T_{1}}\left(f^{=T_{1}}\right)^{2},A_{S\cap
T_{1}}\left(f^{=T_{2}}\right)^{2}\right\rangle_{L^{2}\left(\mu\right)}$
$\displaystyle=\left\langle A_{S\cap
T_{1}}\left(f^{=T_{1}}\right)^{2},\|f^{=T_{2}}\|_{2}^{2}\right\rangle+O_{k}\left(\epsilon\|f\|_{2}^{2}\|f\|_{\infty}^{2}\right).$
$\displaystyle=\|f^{=T_{1}}\|_{2}^{2}\|f^{=T_{2}}\|_{2}^{2}+O_{k}\left(\epsilon\|f\|_{2}^{2}\|f\|_{\infty}^{2}\right).$

This completes the proof of the claim. ∎

The rest of the proof is the exactly the same as in the product case setting.
∎

Now the only thing to remains is to apply the inductive hypothesis.

######  Theorem 7.5.

We have $\|f^{\leq d}\|_{4}^{4}\leq 20^{d}\sum_{\left|S\right|\leq
d}\left(4d\right)^{\left|S\right|}\mathbb{E}_{x\sim\mu_{S}}I_{S,x}^{\leq
d}\left[f\right]^{2}+O_{k}\left(\epsilon^{2}\right)\|f\|_{2}^{2}\|f\|_{\infty}^{2}.$

###### Proof.

The proof is by induction on $d$. By Lemma 7.1 we have

(7.2) $\|f{}^{\leq d}\|_{4}^{4}\leq 2\cdot 9^{d}\|f^{\leq
d}\|_{2}^{4}+2\cdot\sum_{S\neq\varnothing}\left(4d\right)^{\left|S\right|}\|L_{S}^{\leq
d}\left[f\right]\|_{4}^{4}+O_{k}\left(\epsilon\right)\|f\|_{2}^{2}\|f\|_{\infty}^{2}.$

Write $g_{S,x}\left(y\right)=\left(D_{S,x}\left[f\right]\right)^{\leq
d-\left|T\right|}\left(y\right).$ Then by Lemma 6.14 and Lemma 4.11 we have:

$\mathbb{E}_{x}\|D_{S,x}^{\leq d}\left[f\right]\|_{4}^{4}\leq
2\mathbb{E}_{x}\|g_{S,x}\|_{4}^{4}+O_{k}\left(\epsilon^{2}\right)\|f\|_{2}^{2}\|f\|_{\infty}^{2}.$

By induction, we have

(7.3) $\displaystyle\|g_{S,x}\|_{4}^{4}$ $\displaystyle\leq
20^{d-\left|S\right|}\sum_{T\cap S=\varnothing,\left|T\right|\leq
d-\left|S\right|}\left(4d\right)^{\left|T\right|}\mathbb{E}_{y\sim\mu_{T}}I_{T,y}^{2}\left[g_{S,x}\right]+O_{k}\left(\epsilon\right)\|g_{S,x}\|_{2}^{2}\|g_{S,x}\|_{\infty}^{2}.$

By Lemma 6.14 we have $\|g_{S,x}\|_{\infty}=O_{k}\left(\|f\|_{\infty}\right)$.
By Lemmas 6.14, 4.11, and 4.9 we have

(7.4) $\displaystyle\mathbb{E}_{x\sim\mu_{S}}\|g_{S,x}\|_{2}^{2}$
$\displaystyle\leq 2\mathbb{E}_{x\sim\mu_{S}}\|D_{S,x}^{\leq
d}f\|_{2}^{2}+O_{k}\left(\epsilon^{2}\right)\|f\|_{2}^{2}$ $\displaystyle\leq
O_{k}\left(\|f\|_{2}^{2}\right)$

Taking expectations over (7.3), and plugging in (7.4) we obtain:

$\mathbb{E}_{x}\|g_{S,x}\|_{4}^{4}\leq 2\sum_{T\cap
S=\varnothing,\left|T\right|\leq
d-\left|S\right|}\left(4d\right)^{\left|T\right|}\mathbb{E}_{\left(x,y\right)\sim\mu_{S\cup
T}}I_{T,y}^{2}\left[g_{S,x}\right]+O_{k}\left(\epsilon\right)\|f\|_{2}^{2}\|f\|_{\infty}^{2}.$

By Lemmas 6.14 and 4.11 we have

$\mathbb{E}_{\left(x,y\right)\sim\mu_{S\cup
T}}I_{T,y}^{2}\left[g_{S,x}\right]=\mathbb{E}_{z\sim\mu_{T\cup S}}I_{T\cup
S,z}^{2}\left[g\right]+O_{k}\left(\epsilon^{2}\right)\|f\|_{2}^{2}\|f\|_{\infty}^{2}.$

Hence,

$\mathbb{E}_{x}\|g_{S,x}\|_{4}^{4}\leq
20^{d-\left|S\right|}\sum_{S^{\prime}\supseteq S\left|S^{\prime}\right|\leq
d}\left(4d\right)^{\left|S^{\prime}\setminus
S\right|}\mathbb{E}_{z\sim\mu_{S^{\prime}}}\left(I_{S^{\prime},z}^{\leq
d}\left[f\right]\right)^{2}+O_{k}\left(\epsilon\right)\|f\|_{2}^{2}\|f\|_{\infty}^{2}.$

This gives

$\mathbb{E}_{x}\|D_{S,x}^{\leq d}\left[f\right]\|_{4}^{4}\leq 2\cdot
20^{d-\left|S\right|}\sum_{S^{\prime}\supseteq S\left|S^{\prime}\right|\leq
d}\left(4d\right)^{\left|S^{\prime}\setminus
S\right|}\mathbb{E}_{z\sim\mu_{S^{\prime}}}\left(I_{S^{\prime},z}^{\leq
d}\left[f\right]\right)^{2}+O_{k}\left(\epsilon\right)\|f\|_{2}^{2}\|f\|_{\infty}^{2}$

The proof is now completed by plugging this inequality in (7.2). Indeed, we
have

$\displaystyle\|f^{\leq d}\|_{4}^{4}$ $\displaystyle\leq 2\cdot
9^{d}\|f\|_{2}^{4}+O_{k}\left(\epsilon\|f\|_{2}^{2}\|f\|_{\infty}^{2}\right)$
$\displaystyle+\sum_{0<\left|S\right|\leq
d}\left(4d\right)^{\left|S\right|}\cdot 2\cdot
20^{d-\left|S\right|}\sum_{S^{\prime}\supseteq S\left|S^{\prime}\right|\leq
d}\left(4d\right)^{\left|S^{\prime}\setminus
S\right|}\mathbb{E}_{z\sim\mu_{S^{\prime}}}\left(I_{S^{\prime},z}^{\leq
d}\left[f\right]\right)^{2}$ $\displaystyle\leq
20^{d}\sum_{\left|S^{\prime}\right|\leq
d}\left(4d\right)^{\left|S\right|}\mathbb{E}_{z\sim\mu_{S^{\prime}}}\left(I_{S^{\prime},z}^{\leq
d}\left[f\right]\right)^{2}+O_{k}\left(\epsilon\|f\|_{2}^{2}\|f\|_{\infty}^{2}\right).$

∎

###  7.2. The case where $\|f\|_{\infty}$ is large

Here we show a hypercontractive inequality whose error term does not include
the factor $\|f\|_{\infty}.$ This may be useful when $\|f\|_{\infty}$ is
significantly larger than $\delta.$

######  Theorem 7.6.

Suppose that $f$ is $\left(d,\delta\right)$-global, then

$\|f^{\leq d}\|_{4}^{4}\leq 20^{d+1}\sum_{\left|S\right|\leq
d}\left(4d\right)^{\left|S\right|}\mathbb{E}_{x\sim\mu_{S}}I_{S,x}^{\leq
d}\left[f\right]^{2}+O_{k}\left(\epsilon^{2}\delta^{2}\right)\|f\|_{2}^{2}.$

###### Proof.

By applying Theorem 7.7 with $f^{\leq d}$ rather then $f$ and using $\|f^{\leq
d}\|_{\infty}\leq\delta$ we obtain

$\|\left(f^{\leq d}\right)^{\leq d}\|_{4}^{4}\leq
20^{d}\sum_{\left|S\right|\leq
d}\left(4d\right)^{\left|S\right|}\mathbb{E}_{x\sim\mu_{S}}I_{S,x}^{\leq
d}\left[f^{\leq
d}\right]^{2}+O_{k}\left(\epsilon\delta^{2}\right)\|f\|_{2}^{2}.$

The theorem now follows from Lemmas 6.11, 4.11 and 6.5. ∎

######  Theorem 7.7.

Let $\epsilon\leq\epsilon_{0}\left(k\right)$ be sufficiently small. Suppose
that $f$ is $\left(d,\delta\right)$-global. Then we have

$\|f^{\leq d}\|_{4}^{4}\leq\left(100d\right)^{d}\delta^{2}\|f^{\leq
d}\|_{2}^{2}+O_{k}\left(\delta^{2}\epsilon^{2}\|f\|_{2}^{2}\right).$

###### Proof.

By Theorem 7.6, Lemma 6.18, and 4.9 we have

$\displaystyle\|f^{\leq d}\|_{4}^{4}$ $\displaystyle\leq
20^{d}\sum_{\left|S\right|\leq
d}\left(4d\right)^{d}\mathbb{E}_{x\sim\mu_{S}}\left(I_{S,x}^{\leq
d}\left[f\right]\right)^{2}+O_{k}\left(\epsilon^{2}\|f\|_{2}^{2}\|f\|_{\infty}^{2}\right)$
$\displaystyle\leq 20^{d}\sum_{\left|S\right|\leq
d}\left(8d\right)^{d+2}\delta^{2}\mathbb{E}_{x}\left[I_{S,x}^{\leq
d}\left[f\right]\right]+O_{k}\left(\epsilon\|f\|_{2}^{2}\|f\|_{\infty}^{2}\right)$
$\displaystyle\leq 20^{d}\sum_{\left|S\right|\leq
d}\left(8d\right)^{d+2}\delta^{2}\sum_{T\supseteq S,\left|T\right|\leq
d}\|f^{=T}\|_{2}^{2}+O_{k}\left(\epsilon\|f\|_{2}^{2}\|f\|_{\infty}^{2}\right)$
$\displaystyle\leq\left(40d\right)^{d}\delta^{2}\sum_{\left|T\right|\leq
d}\|f^{=T}\|_{2}^{2}+O_{k}\left(\epsilon\|f\|_{2}^{2}\|f\|_{\infty}^{2}\right)$
$\displaystyle\leq 2\left(40d\right)^{d}\delta^{2}\|f^{\leq
d}\|_{2}^{2}+O_{k}\left(\epsilon\|f\|_{2}^{2}\|f\|_{\infty}^{2}\right).$

∎

##  8\. Applications

In this section, we show our applications of the hypercontractive inequality
on high dimensional expanders, which we have shown in the previous section.
The applications follow in a fairly straightforward way, and hence we present
them with brevity.

###  8.1. Global Boolean functions are concentrated on the high degrees.

Fourier concentration results are widely useful in complexity theory and
learning theory. Our first application is a Fourier concentration theorem for
HDX. Namely, the following theorem shows that global Boolean functions on
$\epsilon$-HDX are concentrated on the high degrees, in the sense that the
$2$-norm of the restriction of a function to its low-degree coefficients only
constitutes a tiny fraction of its total $2$-norm.

######  Corollary 8.1.

If $f\colon V_{\left[k\right]}\to\left\\{0,1\right\\}$ is
$\left(d,\delta\right)$-global and $\epsilon$ is sufficiently small. Then

$\|f^{\leq
d}\|_{2}^{2}\leq\left(O_{k}\left(\sqrt{\epsilon}\right)+\left(200d\right)^{d}\delta^{\frac{1}{2}}\right)\|f\|_{2}^{2}.$

###### Proof.

By Lemma 4.9 we have

$\|f^{\leq d}\|_{2}^{2}=\left\langle f^{\leq d},f\right\rangle-
O_{k}\left(\epsilon\right)\|f\|_{2}^{2}.$

We also have by Theorem 7.7

$\displaystyle\left\langle f^{\leq d},f\right\rangle$
$\displaystyle\leq\|f^{\leq d}\|_{4}\|f\|_{\frac{4}{3}}$
$\displaystyle\leq\left(100d\right)^{d}\delta^{\frac{1}{2}}\sqrt{\|f^{\leq
d}\|_{2}}\|f\|_{\frac{4}{3}}+O_{k}\left(\sqrt{\epsilon}\|f\|_{2}^{\frac{1}{2}}\|f\|_{\infty}^{\frac{1}{2}}\|f\|_{\frac{4}{3}}\right).$
$\displaystyle\leq
2\left(100d\right)^{d}\delta^{\frac{1}{2}}\sqrt{\|f\|_{2}}\|f\|_{\frac{4}{3}}+O_{k}\left(\sqrt{\epsilon}\|f\|_{2}^{2}\right)$
$\displaystyle\leq\left(200d\right)^{d}\delta^{\frac{1}{2}}\|f\|_{2}^{2}+O_{k}\left(\sqrt{\epsilon}\|f\|_{2}^{2}\right)$

∎

The Corollary completes the proof of Theorem 1.3.

###  8.2. Small-set expansion theorem

Small set expansion is a fundamental property that is prevalent in
combinatorics and complexity theory. In the setting of the $\rho$-noisy
Boolean hypercube, the small set expansion theorem gives an upper bound on
$\mathrm{{Stab}_{\rho}}(1_{A})=\langle
1_{A},T_{\rho}1_{A}\rangle=E[1_{A}(x)1_{A}(y)]$ for indicators $1_{A}$ of
small sets $A$, which captures the probability that a random walk starting at
a point $x\in A$ remains in $A$, hence showing that small sets are expanding.
Our second application is a small set expansion theorem for global functions
on $\epsilon$-HDX, captured via bounding the natural noise operator in this
setting.

######  Definition 8.2.

Let $\rho\in\left(0,1\right).$ Given $x\in V_{\left[k\right]}$ we let
$N_{\rho}\left(x\right)$ be the distribution where $y\sim
N_{\rho}\left(x\right)$ is chosen by choosing a random set $S$ where each $i$
is in $S$ independently with probability $\rho,$ then choosing
$z\sim\mu_{x_{S}}$ and setting $y=\left(x_{S},z\right).$ We then set

$\mathrm{T}_{\rho}f\left(x\right)=\mathbb{E}_{y\sim N_{\rho}\left(x\right)}f.$

Alternatively we can use the averaging operators to give the following
equivalent definition:

$\mathrm{T}_{\rho}:=\sum_{S\subseteq\left[k\right]}\rho^{\left|S\right|}\left(1-\rho\right)^{k-\left|S\right|}A_{S}\left[f\right].$

We have the following formula for the noise operator, which is similar to the
one in the product space setting.

######  Claim 8.3.

We have $\mathrm{T}_{\rho}f=\sum_{S}\rho^{\left|S\right|}f^{=S}.$

###### Proof.

We have

$\displaystyle\mathrm{T}_{\rho}f$
$\displaystyle=\sum_{S\subseteq\left[k\right]}\rho^{\left|S\right|}\left(1-\rho\right)^{k-\left|S\right|}A_{S}\left[f\right]$
$\displaystyle=\sum_{S\subseteq\left[k\right]}\rho^{\left|S\right|}\left(1-\rho\right)^{k-\left|S\right|}\sum_{T\subseteq
S}f^{=T}$ $\displaystyle=\sum_{T\subseteq\left[k\right]}\sum_{S\supseteq
T}\rho^{\left|S\right|}\left(1-\rho\right)^{k-\left|S\right|}$
$\displaystyle=\sum_{T\subseteq\left[k\right]}\rho^{\left|T\right|}f^{=T}.$

∎

Via a standard argument we have the following bound on the noise operator.

######  Lemma 8.4.

We have

$\|\mathrm{T}_{\rho}f\|_{2}^{2}\leq\|f^{\leq
d}\|_{2}^{2}+\left(\rho^{d}+O_{k}\left(\epsilon\right)\right)\|f\|_{2}^{2}.$

###### Proof.

This is immediate from Lemmas 8.3 and 4.9. ∎

Our small set expansion applications are as follows.

######  Corollary 8.5 (Small set expansion theorem).

If $f\colon V_{\left[k\right]}\to\left\\{0,1\right\\}$ is
$\left(d,\delta\right)$-global. Then

$\|\mathrm{T}_{\rho}f\|_{2}^{2}\leq\left(\rho^{d}+\left(100d\right)^{d}\delta^{2}+O_{k}\left(\sqrt{\epsilon}\right)\right)\|f\|_{2}^{2}.$

###### Proof.

This follows immediately from Lemma 8.4 and Corollary 8.1. ∎

###  8.3. Kruskal–Katona theorem

Our last application is an analogue of the Kruskal–Katona theorem in the
setting of high dimensional expanders. The Kruskal-Katona theorem is a
fundamental and widely-applied result in algebraic combinatorics, which gives
a lower bound on the size of the lower shadow of a set $A$, denoted
$\partial(A)=\\{x\colon y\prec x,\;\text{for some}\;y\in A\\}$.

We first consider the natural up-down walk in our setting.

######  Definition 8.6.

The operator corresponding to up-down random walk is

$\mathrm{T}=\frac{1}{k}\sum_{i=1}^{k}A_{\left[k\right]\setminus\left\\{i\right\\}}\left[f\right]=\sum_{S}\frac{k-\left|S\right|}{k}f^{=S}.$

By applying the approximate Parseval inequality (Lemma 4.9), we obtain the
following claim.

######  Claim 8.7.

We have

$\left\langle f-\mathrm{T}f,f\right\rangle\geq\frac{d}{k}\|f^{\geq
d}\|_{2}^{2}-O_{k}\left(\epsilon\right)\|f\|_{2}^{2}.$

By our Fourier concentration theorem, (Corollary 8.1), we have the following
lower bound on the $2$-norm of the high degree part of $f$.

######  Claim 8.8.

Let $\delta\leq\left(200d\right)^{-2d},$ and
$\epsilon\leq\epsilon_{0}\left(k\right)$ be sufficiently small. If $f\colon
V_{\left[k\right]}\to\left\\{0,1\right\\}$ is $\left(d,\delta\right)$-global.
Then

$\|f^{\geq d}\|_{2}^{2}\geq\frac{1}{2}\|f\|_{2}^{2}.$

Combining the above claims we get the following.

######  Claim 8.9.

Let $\delta\leq\left(200d\right)^{-2d}.$ We have

$\left\langle f-\mathrm{T}f,f\right\rangle\geq\frac{d}{2k}\|f\|_{2}^{2}$

We are now ready to prove the Kruskal–Katona theorem in the setting of high
dimensional expanders.

######  Corollary 8.10.

Let $X$ be an $\epsilon$-HDX, for a sufficiently small $\epsilon>0$. Let
$\delta\leq\left(200d\right)^{-d},$ and let $A\subseteq X\left(k-1\right)$ be
$\left(d,\delta\right)$-global. Then

$\mu\left(\partial(A)\right)\geq\mu\left(A\right)\left(1+\frac{d}{2k}\right).$

###### Proof.

Let $f=1_{A}.$ We have

$\displaystyle\left\langle f-\mathrm{T}f,f\right\rangle$
$\displaystyle=\Pr_{\sigma\sim
X\left(k-1\right)}\Pr_{\tau_{1},\tau_{2}\supset\sigma}\left[\tau_{1}\in
A,\tau_{2}\notin A\right].$
$\displaystyle\leq\Pr\left[\sigma\in\partial(A),f\left(\tau_{2}\right)\notin
A\right]$ $\displaystyle=\mu\left(\partial(A)\right)-\mu\left(A\right).$

∎

## References

  * [1] Vedat Levi Alev, Fernando Granha Jeronimo, and Madhur Tulsiani.  Approximating constraint satisfaction problems on high-dimensional expanders.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 180–201. IEEE, 2019.
  * [2] Nima Anari, Vishesh Jain, Frederic Koehler, Huy Tuan Pham, and Thuy-Duong Vuong.  Entropic independence in high-dimensional expanders: Modified log-sobolev inequalities for fractionally log-concave polynomials and the ising model.  arXiv preprint arXiv:2106.04105, 2021.
  * [3] Nima Anari, Kuikui Liu, and Shayan Oveis Gharan.  Spectral independence in high-dimensional expanders and applications to the hardcore model.  SIAM Journal on Computing, (0):FOCS20–1, 2021.
  * [4] Nima Anari, Kuikui Liu, Shayan Oveis Gharan, and Cynthia Vinzant.  Log-concave polynomials ii: high-dimensional walks and an fpras for counting bases of a matroid.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 1–12, 2019.
  * [5] Mitali Bafna, Max Hopkins, Tali Kaufman, and Schahar Lovett.  Hypercontractivity on high dimensional expanders.  (personal communication), 2021.
  * [6] Mark Braverman, Subhash Khot, Noam Lifshitz, and Dor Minzer.  An invariance principle for the multi-slice, with applications.  arXiv preprint arXiv:2110.10725, 2021.
  * [7] Zongchen Chen, Kuikui Liu, and Eric Vigoda.  Optimal mixing of glauber dynamics: Entropy factorization via high-dimensional expansion.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1537–1550, 2021.
  * [8] Neta Dafni, Yuval Filmus, Noam Lifshitz, Nathan Lindzey, and Marc Vinyals.  Complexity measures on symmetric group and beyond.  In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021), 2021.
  * [9] Yotam Dikstein, Irit Dinur, Yuval Filmus, and Prahladh Harsha.  Boolean Function Analysis on High-Dimensional Expanders.  In LIPIcs-Leibniz International Proceedings in Informatics, volume 116. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.
  * [10] Yotam Dikstein, Irit Dinur, Prahladh Harsha, and Noga Ron-Zewi.  Locally testable codes via high-dimensional expanders.  arXiv preprint arXiv:2005.01045, 2020.
  * [11] Irit Dinur, Shai Evra, Ron Livne, Alex Lubotzky, and Shahar Mozes.  Locally testable codes with constant rate, distance, and locality.  In (to appear), 2021.
  * [12] Irit Dinur, Yuval Filmus, Prahladh Harsha, and Madhur Tulsiani.  Explicit sos lower bounds from high-dimensional expanders.  arXiv preprint arXiv:2009.05218, 2020.
  * [13] Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, and Amnon Ta-Shma.  List Decoding with Double Samplers.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 2134–2153, 2019.
  * [14] Irit Dinur and Tali Kaufman.  High Dimensional Expanders Imply Agreement Expanders.  In Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on, pages 974–985. IEEE, 2017.
  * [15] Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra.  On Non-Optimally Expanding Sets in Grassmann Graphs.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 940–951, 2018.
  * [16] Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, and Muli Safra.  Towards a Proof of the 2-to-1 Games Conjecture?  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 376–389, 2018.
  * [17] David Ellis, Nathan Keller, and Noam Lifshitz.  On a biased edge isoperimetric inequality for the discrete cube.  Journal of Combinatorial Theory, Series A, 163:118–162, 2019.
  * [18] David Ellis, Guy Kindler, and Noam Lifshitz.  Hypercontractivity for global functions in the bilinear scheme.  In preparation, 2021.
  * [19] Shai Evra, Tali Kaufman, and Gilles Zémor.  Decodable quantum ldpc codes beyond the square root distance barrier using high dimensional expanders.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 218–227. IEEE, 2020.
  * [20] Yuval Filmus.  Friedgut-Kalai-Naor Theorem for Slices of the Boolean Cube.  Chicago J. Theor. Comput. Sci., 2016, 2016.
  * [21] Yuval Filmus.  Almost linear boolean functions on S n are almost unions of cosets.  Manuscript, 2021.
  * [22] Yuval Filmus.  FKN theorems for the biased cube and the slice.  Manuscript, 2021.
  * [23] Yuval Filmus, Guy Kindler, Noam Lifshitz, and Dor Minzer.  Hypercontractivity on the symmetric group.  arXiv preprint arXiv:2009.05503, 2020.
  * [24] Yuval Filmus, Guy Kindler, Elchanan Mossel, and Karl Wimmer.  Invariance Principle on the Slice.  TOCT, 10(3):11:1–11:37, 2018.
  * [25] Yuval Filmus and Elchanan Mossel.  Harmonicity and Invariance on Slices of the Boolean Cube.  In 31st Conference on Computational Complexity, CCC 2016, May 29 to June 1, 2016, Tokyo, Japan, pages 16:1–16:13, 2016.
  * [26] Yuval Filmus, Ryan O’Donnell, and Xinyu Wu.  A log-Sobolev inequality for the multislice, with applications.  In Proceedings of the 10th Innovations in Theoretical Computer Science conference (ITCS’19), 2019.
  * [27] Louis Golowich.  Improved product-based high-dimensional expanders.  arXiv preprint arXiv:2105.09358, 2021.
  * [28] Roy Gotlib and Tali Kaufman.  Testing odd direct sums using high dimensional expanders.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
  * [29] Max Hopkins, Tali Kaufman, and Shachar Lovett.  High dimensional expanders: Random walks, pseudorandomness, and unique games.  arXiv preprint arXiv:2011.04658, 2020.
  * [30] Fernando Granha Jeronimo, Shashank Srivastava, and Madhur Tulsiani.  Near-linear time decoding of ta-shma’s codes via splittable regularity.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 1527–1536, 2021.
  * [31] Jeff Kahn, Gil Kalai, and Nathan Linial.  The Influence of Variables on Boolean Functions.  IEEE, 1988.
  * [32] Tali Kaufman and Alexander Lubotzky.  High Dimensional Expanders and Property Testing.  In Innovations in Theoretical Computer Science, ITCS’14, Princeton, NJ, USA, January 12-14, 2014, pages 501–506, 2014.
  * [33] Tali Kaufman and David Mass.  High Dimensional Random Walks and Colorful Expansion.  In LIPIcs-Leibniz International Proceedings in Informatics, volume 67. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.
  * [34] Tali Kaufman and Izhar Oppenheim.  Construction of New Local Spectral High Dimensional Expanders.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 773–786, 2018.
  * [35] Tali Kaufman and Izhar Oppenheim.  High Order Random Walks: Beyond Spectral Gap.  Combinatorica, pages 1–37, 2020.
  * [36] Peter Keevash, Noam Lifshitz, Eoin Long, and Dor Minzer.  Hypercontractivity for global functions and sharp thresholds.  arXiv preprint arXiv:1906.05568, 2019.
  * [37] Peter Keevash, Noam Lifshitz, Eoin Long, and Dor Minzer.  Forbidden intersections for codes.  arXiv preprint arXiv:2103.05050, 2021.
  * [38] Subhash Khot, Dor Minzer, and Muli Safra.  On Independent Sets, 2-to-2 Games, and Grassmann Graphs.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 576–589, 2017.
  * [39] Subhash Khot, Dor Minzer, and Muli Safra.  Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion.  In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 592–601, 2018\.
  * [40] Noam Lifshitz and Dor Minzer.  Noise sensitivity on the p-biased hypercube.  In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pages 1205–1226. IEEE, 2019.
  * [41] Siqi Liu, Sidhanth Mohanty, and Elizabeth Yang.  High-dimensional expanders from expanders.  arXiv preprint arXiv:1907.10771, 2019.
  * [42] Alexander Lubotzky.  High dimensional expanders.  In Proceedings of the International Congress of Mathematicians: Rio de Janeiro 2018, pages 705–730. World Scientific, 2018.
  * [43] Ryan O’Donnell.  Analysis of boolean functions.  Cambridge University Press, 2014.
  * [44] Ryan O’Donnell and Karl Wimmer.  KKL, Kruskal–Katona, and Monotone Nets.  SIAM Journal on Computing, 42(6):2375–2399, 2013.
  * [45] Ori Parzanchevski.  Mixing in high-dimensional expanders.  Combinatorics, Probability and Computing, 26(5):746–761, 2017.