There is a common theme to research questions in additive combinatorics and noise stability.
Both study the following basic question:
Let $\mathcal{P}$ be a probability distribution
over a space $\Omega^\ell$ with all $\ell$ marginals equal. Let
$\underline{X}^{(1)}, \ldots, \underline{X}^{(\ell)}, \allowbreak
\underline{X}^{(j)} = (X_1^{(j)}, \ldots, X_n^{(j)})$ be random vectors such
that for every coordinate $i \in [n]$ the tuples $(X_i^{(1)}, \ldots, X_i^{(\ell)})$
are i.i.d. according to $\cP$.

A central question that is addressed in both areas is:

* Does there exist a function $c_\cP()$ independent
of $n$ such that
for every $f: \Omega^n \to [0, 1]$ with
$\EE[f(\underline{X}^{(1)})] = \mu > 0$:

\begin{align*}
\EE \left[ \prod_{j=1}^\ell f(\underline{X}^{(j)}) \right]
\ge c_\cP(\mu) > 0 \; ?
\end{align*}

Instances of this question include the Finite Field Model version of Roth's and
Szemerédi's theorems as well as Borell's result about the optimality of noise stability
of half-spaces.

Our goal in this paper is to interpolate between the noise stability theory and the finite field additive combinatorics theory and address the question above in further generality than considered before.
In particular, we settle the question for $\ell = 2$ and when $\ell > 2$ and $\cP$
has bounded correlation $\rho(\cP) < 1$. Under the same conditions we also characterize the obstructions for a similar lower bounds in the case of $k$ different functions.
Part of the novelty in our proof is the combination of analytic arguments from the theories of influences and hyper-contraction with arguments from additive combinatorics.

§ INTRODUCTION

§.§ Setup and same set hitting

In this paper we analyze a general framework which includes many fundamental questions in both
the theory of noise stability and in finite field models of additive combinatorics.
We begin with formally defining this general setting.
Let $\Omega$ be a finite set
and assume we are given a probability distribution $\mathcal{P}$
over $\Omega^\ell$
for some $\ell \ge 2$ – we will call it an
$\ell$-step probability distribution over $\Omega$.

Furthermore, assume we are given $n \in \bbN$.
We consider $\ell$ vectors $\underline{X}^{(1)}, \allowbreak \ldots,
\allowbreak \underline{X}^{(\ell)}$,
$\underline{X}^{(j)} = (X_1^{(j)},\allowbreak \ldots, X_n^{(j)})$ such that
for every $i \in [n]$, the $\ell$-tuple $(X_i^{(1)}, \ldots, \allowbreak  X_i^{(\ell)})$
is sampled according to $\mathcal{P}$, independently of the other
coordinates $i' \neq i$
(see Figure <ref> for an overview of the notation).

Let $\mu, \delta \in (0, 1]$. We say that a distribution
$\mathcal{P}$ is $(\mu, \delta)$-same-set hitting,
if, for all $n \geq 1$, whenever a function $f: \Omega^n \to [0, 1]$ satisfies
$\EE[f(\underline{X}^{(j)})] \ge \mu$
for every $j \in [\ell] := \{1, \ldots, \ell\}$,
we have

\begin{align*}
\EE \left[ \prod_{j=1}^\ell f(\underline{X}^{(j)})\right]
\ge \delta \; .
\end{align*}

We call $\mathcal{P}$ same-set hitting if for every
$\mu \in (0, 1]$ there exists $\delta \in (0, 1]$ such that
$\mathcal{P}$ is $(\mu, \delta)$-same-set hitting.

In this paper we address the question: which distributions $\mathcal{P}$
are same-set hitting? We achieve full characterization for $\ell = 2$
and answer the question affirmatively for a large class of distributions
with $\ell > 2$.

The question of set hitting was studied extensively in additive combinatorics and in the theory of influences and noise stability. Perhaps the most well-studied case is that of random arithmetic progressions. Let $Z$ be a finite additive group
and $\ell \in \mathbb{N}$.
Then, we can define a distribution $\mathcal{P}_{Z,\ell}$
of random $\ell$-step arithmetic progressions in $Z$.
Specifically, for every $x, r \in Z$ we set:

\begin{align*}
\cP_{Z,\ell}(x, x+r, x+2r, \ldots, x+(\ell-1)r) := 1/|Z|^2 \; .
\end{align*}

Some of the distributions $\cP_{Z,\ell}$ can be shown to be
same-set hitting using the hypergraph regularity lemma:

If $|Z|$ is coprime to $(\ell-1)!$, then $\cP_{Z,\ell}$ is same-set hitting.

As is well known, the case $\ell=3$ follows from the arguments of Roth [24] applied to the finite field setup, while the general case follows a long line of work, starting by Szemerédi lemma [28],
its proof by Furstenberg using the ergodic theorem [9]
as well as the finite group and multi-dimensional versions, see, e.g.,
[24, 8, 11, 13].

It is natural to consider a generalization of the question where different functions are applied to different $X^{(i)}$. This question was studied in the theories of Gaussian noise stability and hyper-contraction as we explain next.

§.§ Set hitting

The generalization to multiple sets is defined as follows.

Let $\mu, \delta \in (0, 1]$. We say that a distribution
$\mathcal{P}$ is $(\mu, \delta)$-set hitting,
if, whenever functions $f^{(1)}, \ldots, f^{(\ell)}: \Omega^n \to [0, 1]$ satisfy
$\EE[f^{(j)}(\underline{X}^{(j)})] \allowbreak \ge \mu$
for every $j \in [\ell]$,
we have

\begin{align}
\label{eq:85a}
\EE \left[ \prod_{j=1}^\ell f^{(j)}(\underline{X}^{(j)})\right]
\ge \delta \; .
\end{align}

We call $\mathcal{P}$ set hitting if for every
$\mu \in (0, 1]$ there exists $\delta \in (0, 1]$ such that
$\mathcal{P}$ is $(\mu, \delta)$-set hitting.

Borell [5] established the set hitting property in the Gaussian case where
$(X_i,Y_i) \sim N(0,\left( \begin{matrix} 1 & \rho \\ \rho & 1 \end{matrix} \right))$ are i.i.d and
$\rho \in (0,1)$.
In fact [5] does much more: it finds the optimal $\delta$ in terms of $\mu$ and $\rho$ in this case.
(Note that in this case $\Omega$ is infinite).

In earlier work, [4] Borell also proved some of the first reverse-hyper contractive inequalities.
These give a different proof that the Gaussian example above is set hitting but also imply
the same for the binary analog where
$(X_i,Y_i) \in \{-1,1\}^2$ satisfy $E[X_i] = E[Y_i] = 0$ and $E[X_i Y_i] = \rho$.
See [19] for a discussion of this result and some of its implications.

The full classification of set hitting distributions can be deduced from
a paper on reverse hypercontractivity[
That $\mathcal{P}$ is set hitting if (<ref>) holds is a consequence
of Lemma 8.3 in [21]. If (<ref>) does not hold,
an appropriate combination of dictators establishes a counterexample.
by Mossel, Oleszkiewicz and Sen

A finite probability space $\mathcal{P}$ is set hitting if and only if:

\begin{align}
\label{eq:84a}
\beta(\cP) :=
\min_{\substack{x^{(1)} \in \supp(X_i^{(1)}),\\
\ldots,\\
x^{(\ell)} \in \supp(X_i^{(\ell)})}}
\mathcal{P}(x^{(1)}, \ldots, x^{(\ell)}) > 0 \; .
\end{align}

In many interesting settings, include the finite field models in additive combinatorics, the distribution $\mathcal{P}$ does not have full support. In these settings, the goal is to understand sufficient conditions on the functions which imply that (<ref>) does hold as we discuss next.

§.§ Obstructions in additive combinatorics

In general much of the interest in additive combinatorics is in understanding what conditions on functions $f$ imply (<ref>). In the setup of Roth's Theorem [24], i.e., arithmetic progressions of length $3$, it is known that if the functions $f_1,f_2,f_3$ all satisfy that
$\| \widehat{f_i - E[f]}  \|_{\infty}$ is small then (<ref>) holds. More recently, Gowers showed that for longer terms arithmetic progression if the functions $f_i$ have low Gowers norm then
(<ref>) holds, see e.g. [13].

In one of our main results (see Section <ref> below)
we show that in a pretty general setup (which does not include the additive combinatorics setup), the only obstruction for $(\ref{eq:85a})$ to hold is for it to have
large Fourier coefficients.

§.§ Basic example

At this point we would like to introduce the simplest example that is not covered by either the theory of influences or techniques from additive combinatorics.
Let $S \subseteq \{0,1,2\}^n$ be a non-empty set of density
$\mu = \frac{|S|}{3^n}$.  We pick a random vector
$\underline{X} = (X_1, \ldots, X_n)$ uniformly from $\{0,1,2\}^n$, and then
sample another vector $\underline{Y} = (Y_1,\ldots,Y_n)$ such that for each
$i$ independently, coordinate $Y_i$ is picked uniformly in
$\{X_i, X_i+1 \bmod{3}\}$.  Our goal is to show that:

\begin{align*}
\Pr[\underline{X} \in S \land \underline{Y} \in S] \ge c(\mu) > 0 \; .
\end{align*}

In other words, we want to bound away the probability from $0$
by an expression which only depends on $\mu$ and not on $n$.
Similarly given sets $S$ and $T$ of density at least $\mu$, we want to find under what conditions does it holds that the probability $\Pr[\underline{X} \in S \land \underline{Y} \in S]$ can be lower bounded effectively. We note that the support of the distribution on $\{0,1,2\}^2$ is not full and that
the distribution is not of arithmetic nature.

§.§ Our results

§.§.§ Same set hitting for two steps

In case of $\ell = 2$ we establish the following theorem:

A two-step probability distribution with equal marginals $\mathcal{P}$
is same-set hitting if and only if
$\alpha(\mathcal{P}) := \min_{x \in \Omega} \cP(x, x)
> 0$.

Of course, if $\beta(\cP) > 0$, then Theorem <ref>
follows from Theorem <ref>. However,
we are not aware of any previous work in case $\beta(\mathcal{P}) = 0$,
i.e., when the distribution is same-set hitting but not set hitting,
in particular for the probability space from Section <ref>.

§.§.§ Same set hitting for more than two steps

In a general case of an $\ell$-step distribution with equal marginals, it
is still clear that $\alpha(\mathcal{P}) > 0$ is necessary. However, it remains
open if it is sufficient.

We provide the following partial results. Firstly, by a simple inductive argument
based on Theorem <ref>, we show that multi-step
probability  spaces induced by Markov chains are same-set hitting
(cf. Section <ref>).

Secondly, we show that $\mathcal{P}$ is same-set hitting
if $\alpha(\mathcal{P}) > 0$ and its
correlation $\rho(\mathcal{P})$ is smaller than $1$.
The opposite condition $\rho(\mathcal{P}) = 1$ is equivalent
to the following:
There exist $j \in [\ell]$, $S \subseteq \Omega$,
$T \subseteq \Omega^{\ell-1}$ such that
$0 < |S| < |\Omega|$ and:

\begin{align*}
X_i^{(j)} \in S \iff
\left(X_i^{(1)}, \ldots, X_i^{(j-1)}, X_i^{(j+1)}, \ldots, X_i^{(\ell)}\right)
\in T \; .
\end{align*}

For the full definition of $\rho(\mathcal{P})$, cf. Definition <ref>.

Let $\mathcal{P}$ be a probability distribution with equal marginals.
If $\alpha(\mathcal{P}) > 0$ and $\rho(\mathcal{P}) < 1$, then $\mathcal{P}$
is same-set hitting.

We are not aware of any general results in case $\rho(\mathcal{P}) = 1$.
In particular, let $\mathcal{P}$ be a three-step distribution over
$\Omega = \{0, 1, 2\}$ such that $X_i^{(1)},X_i^{(2)},X_i^{(3)}$ is uniform
over $\{000,111,222,012,120,201\}$. To the best of our knowledge,
it is an open question whether this distribution $\mathcal{P}$ is same-set

One might conjecture that $\alpha(\cP) > 0$ is the sole sufficient
condition for same-set hitting.
Unfortunately, the techniques used to prove Theorem <ref>
do not seem to extend easily to less symmetric spaces. This suggests that
proving the conjecture fully in $\rho=1$ case might be a difficult undertaking.

§.§.§ Set hitting for functions  with no large Fourier coefficients

The methods developed here also allow to obtain lower bounds on the
probability of hitting multiple sets. In fact, we show that if $\rho(\cP) < 1$,
then such lower bounds exist in terms of $\rho$,
the measures of the sets and the largest non-empty Fourier coefficient.

Let $\cP$ be a probability distribution with $\rho(\cP) < 1$. Then, $\cP$
is set-hitting for functions $f^{(1)}, \ldots, f^{(\ell)}:
\underline{\Omega} \to [0, 1]$ that have both:

* Noticeable expectations, i.e.,
$\EE[f^{(j)}(\underline{X}^{(j)})] \ge \Omega(1)$.

* No large Fourier coefficients, i.e.,
$\max_{\sigma} \left| \hat{f}^{(j)}(\sigma) \right| \le o(1)$.

§.§ Other related work

The question of understanding which sets are hit often by dynamical systems is
central to ergodic theory and additive combinatorics.

The Poincaré recurrence theorem states that measure preserving maps  satisfy the
property that for each set $U$ of positive measure, and for almost every point
$x$ of $U$, the dynamical system started at $x$ will hit $U$ infinitely often,
see, e.g., <cit.>.

Much of the ergodic theory deals with quantifying this phenomena of repeatedly
hitting the set $U$. The ergodic theorem, for example, implies that ergodic
measure preserving dynamical systems satisfy that for almost all starting
points $x$, the set $U$ will be hit in limiting frequency which is equal to its

Understanding set hitting by a number of consecutive steps of
a process has been of intense study in additive combinatorics
(where almost always $\rho=1$).

For example, a well-studied case are random arithmetic progressions.
Let $Z$ be a finite additive group
and $\ell \in \mathbb{N}$.
Then, we can define a distribution $\mathcal{P}_{Z,\ell}$
of random $\ell$-step arithmetic progressions in $Z$.
Specifically, for every $x, r \in Z$ we set:

\begin{align*}
\cP_{Z,\ell}(x, x+r, x+2r, \ldots, x+(\ell-1)r) := 1/|Z|^2 \; .
\end{align*}

Some of the distributions $\cP_{Z,\ell}$ can be shown to be
same-set hitting using the hypergraph regularity lemma:

If $|Z|$ is coprime to $(\ell-1)!$, then $\cP_{Z,\ell}$ is same-set hitting.

This follows a long line of work, starting by Szemerédi lemma [28],
its proof by Furstenberg using the ergodic theorem [9]
as well as the finite group and multi-dimensional versions, see, e.g.,
[24, 8, 11].

One might conjecture that $\alpha(\cP) > 0$ is the sole sufficient
condition for same-set hitting.
Unfortunately, the techniques used to prove Theorem <ref>
do not seem to extend easily to less symmetric spaces. This suggests that
proving the conjecture fully in $\rho=1$ case might be a difficult undertaking.

The case of $\rho < 1$ has also been studied in the context of extremal
combinatorics and hardness of approximation.
In particular, Mossel [20] uses the
invariance principle to prove that if $\rho(\mathcal{P}) < 1$, then $\mathcal{P}$ is
set hitting for low-influence functions. We use this result to establish
Theorem <ref>. Additionally, Theorem
<ref> can be seen as a strengthening of

Furthermore, Austrin and Mossel [1] establish the result equivalent to
Theorem <ref> assuming in addition to $\rho(\cP) < 1$
also that $\cP$ is pairwise independent (they also prove results for the case
$\rho(\cP)=1$ with pairwise independence but these involve only bounded degree

Finally we note that another relevant paper in the case of $\ell = 2$ and
symmetric $\cP$ is by Dinur, Friedgut and Regev [7], who give a
characterization of non-hitting sets. However, due to a different framework,
their results are not directly comparable to ours.

Our work is related to problems and results in inapproximability in theoretical computer science.
For example, our theorem is related to the proof of hardness
for rainbow colorings of hypergraphs by Guruswami and Lee
[10]. In particular, it is connected to their Theorem 4.3
and partially answers their Questions C.4 and C.6.

§.§ Proof combining ideas from additive combinatorics and the theory of influences

Interestingly, the proof of our results interpolates between additive combinatorics and the theory of influences. Results of [20] imply that if a collection of functions have low influences then they are same-set hitting. In the proof of Theorem <ref> we apply a variant of a density increase argument to reduce to this case. First we apply the standard density increase argument to assume WLOG of generality that conditioning on a small number of coordinates does not change the measure of the set by much. Then we show, under this assumption, by applying a variant of the density increase argument that we can additionally assume WLOG that all influences are small.

§.§ Outline of the paper

The rest of the paper is organised as follows: the notation is introduced
in Section <ref>, Section <ref> contains full
statements of our theorems and Section <ref> sketches
the proof of our main theorem.

The full proof of the multi-step theorem follows in
Section <ref>. The proof of the two-step theorem is in
Section <ref> and the proof for functions with
small Fourier coefficients in Section <ref>.
A theorem for Markov chains is introduced in Section <ref>
and better bounds for symmetric spaces in Section <ref>.
Finally, the modified proof of the low-influence theorem from
[20] is presented in the appendix.
We note that an extended abstract with preliminary version of our results appeared
in [15].

§ NOTATION AND PRELIMINARIES

§.§ Notation

We will now introduce our setting and notation.
We refer the reader to Figure <ref> for an overview.

We always assume that we have $n$ independent coordinates.
In each coordinate $i$
we pick $\ell$ values $X_{i}^{(j)}$ for $j \in [\ell] = \{1,\ldots,\ell\}$
at random using some distribution.
Each value $X_{i}^{(j)}$ is chosen from the same fixed set $\Omega$, and
the distribution
of the tuple $\overline{X}_i = (X_{i}^{(1)},\ldots,X_{i}^{(\ell)})$ of
values from $\Omega^{\ell}$ is given by a distribution $\mathcal{P}$.

This gives us values $X_{i}^{(j)}$ for $i \in \{1,\ldots,n\}$ and
$j \in \{1,\ldots,\ell\}$.
Thus, we have $\ell$ vectors
where $\underline{X}^{(j)} = (X_1^{(j)},\ldots,X_n^{(j)})$
represents the $j$-th step of the random process. In case $\ell = 2$,
we might call our two vectors $\underline{X}$ and $\underline{Y}$ instead.

For reasons outlined in Section <ref> we assume that
all of $X_i^{(1)}, \ldots, X_i^{(\ell)}$ have the same marginal distribution,
which we call $\pi$. We assume that $\Omega$ is the support of $\pi$.

Even though it is not necessary,
for clarity of the presentation
we assume that each coordinate $\overline{X}_i =
(X_i^{(1)},\ldots,X_i^{(j)},\ldots,X_i^{(\ell)})$ has the
same distribution $\mathcal{P}$.

We consistently use index $i$ to index over the coordinates
(from $[n]$)
and $j$ to index over the steps (from $[\ell]$).

As visible in Figure <ref>,
we denote the aggregation across the coordinates by the underline
and the aggregation across the steps by the overline.
For example, we write $\underline{\Omega} = \Omega^n$,
$\overline{\Omega} = \Omega^\ell$,
$\underline{\mathcal{P}} = \mathcal{P}^n$
and $\overline{\underline{X}} =
(\overline{X}_1, \ldots, \overline{X}_n)
\allowbreak = (\underline{X}^{(1)}, \ldots, \underline{X}^{(\ell)})$.

We sometimes call $\underline{\mathcal{P}}$ a tensorized,
multi-step probability distribution
as opposed to a tensorized, single-step distribution
$\underline{\mathcal{\pi}}$ and single-coordinate, multi-step distribution

Furthermore, we extend the index notation to subsets of indices or steps.
For example, for $S \subseteq [\ell]$ we define $X^{(S)}$ to be the
collection of random variables $\left\{ X^{(j)}: j \in S  \right\}$.

We also use the set difference symbol to mark vectors with one element missing,
e.g., $\overline{X}^{\setminus j} := (X^{(1)}, \ldots, X^{(j-1)}, X^{(j+1)}, \ldots,

One should think of $\ell$ and $|\Omega|$ as constants and of $n$ as large.
We aim to get bounds which are independent of $n$.

§.§ Correlation

In case $\ell > 2$, the bound we obtain will depend on the
correlation of the distribution $\mathcal{P}$.
This concept was used before in [20].

Let $\mathcal{P}$ be a single-coordinate distribution
and let $S, T \subseteq [\ell]$. We define the correlation:

\begin{align*}
\rho(\mathcal{P}, S, T) &:=
\sup \Bigl\{ \Cov[f(X^{(S)}), g(X^{(T)})] \Bigm|
f: \Omega^{(S)} \to \mathbb{R},
g: \Omega^{(T)} \to \mathbb{R}, \\
\Var[f(X^{(S)})] = \Var[g(X^{(T)})] = 1
\Bigr\} \; .
\end{align*}

The correlation of $\mathcal{P}$ is
$\rho(\mathcal{P}) := \max_{j \in [\ell]}
\rho\left(\mathcal{P}, \{j\}, [\ell]\setminus\{j\}\right)$.

§.§ Influence

A crucial notion in the proof of Theorem <ref> is
the influence of a function. It expresses the average variance of a
given that all but one of its $n$ inputs have been fixed to random values:

Let $\underline{X}$ be a random vector over alphabet $\underline{\Omega}$
and $f: \underline{\Omega} \to \mathbb{R}$ be a function
and $i \in [n]$. The influence of $f$ on the $i$-th coordinate is:

\begin{align*}
\Inf_i(f(\underline{X})) := \EE \left[ \Var\left[ f(\underline{X})
\mid \underline{X}_{\setminus i} \right] \right]
\; .
\end{align*}

The (total) influence of $f$ is
$\Inf(f(\underline{X})) := \sum_{i=1}^n \Inf_i(f(\underline{X}))$.

Note that the influence depends both on the function $f$ and
the distribution of the vector $\underline{X}$.

§ OUR RESULTS

Here we give precise statements of our results presented in the introduction.

§.§ The case of
l = 2

Let $\Omega$ be a finite set and
$\mathcal{P}$ a probability distribution over $\Omega^2$
with equal marginals $\pi$.
Let pairs $(X_i, Y_i)$
be i.i.d. according to $\mathcal{P}$ for
$i \in \{1,\ldots,n\}$.

Then, for every $f: \Omega^n \to [0,1]$ with
$\EE[f(\underline{X})] = \mu > 0$:

\begin{align}
\EE [f(\underline{X})f(\underline{Y})]
\geq c\left (\alpha(\mathcal{P}), \mu \right) \; ,
\end{align}

where the function $c()$ is positive whenever
$\alpha(\mathcal{P})> 0$.

We remark that Theorem <ref> does not depend
on $\rho(\mathcal{P})$ in any way.
This is in contrast to the case $\ell > 2$.
It is possible to obtain a polynomially large explicit bound $c()$
for symmetric two-step spaces (see Section <ref>).

To prove Theorem <ref> we make
a convex decomposition argument and then apply
the multi-step Theorem <ref>
(see Section <ref>).
For completeness, we provide a proof of
Theorem <ref> assuming Theorem

The “if” part follows from Theorem <ref>.
The “only if” can be seen by taking $f$ to be an appropriate dictator.

§.§ The general case

Let $\Omega$ be a finite set and $\cP$ a distribution over $\Omega^{\ell}$ in
which all marginals are equal.  Let tuples
$\overline{X}_i = (X_i^{(1)}, \ldots, X_i^{(\ell)})$ be i.i.d. according to
$\mathcal{P}$ for $i \in \{1,\ldots,n\}$.

Then, for every function $f: \Omega^n \to [0,1]$
with $\EE[f(\underline{X}^{(j)})] = \mu > 0$:

\begin{align}
\EE \left[ \prod_{j=1}^\ell f(\underline{X}^{(j)}) \right]
\geq c\left(\alpha(\mathcal{P}), \rho(\mathcal{P}), \ell, \mu \right) \; ,
\end{align}

where the function $c()$ is positive whenever $\alpha(\mathcal{P})>0$
and $\rho(\mathcal{P}) < 1$.

Furthermore, there exists some $D(\mathcal{P}) > 0$
(more precisely, $D$ depends on
$\alpha$, $\rho$ and $\ell$) such that
if $\mu \in (0, 0.99]$, one can take:

\begin{align}
\label{eq:76a}
c(\alpha, \rho, \ell, \mu) := 1 / \exp\left(\exp\left(\exp\left(
\left(1/\mu\right)^D
\right)\right)\right) \; .
\end{align}

Note that this bound does depend on $\rho(\mathcal{P})$.
We also obtain a bound that does not depend on $\rho(\mathcal{P})$
for multi-step probability spaces generated by Markov chains
(see Section <ref>).

§.§ Hitting of different sets by uniform functions

Finally, we state the generalization of low-influence theorem from
[20]. We assume that the reader is familiar with
Fourier coefficients $\hat{f}(\sigma)$ and the basics of discrete function
analysis, for details see, e.g., Chapter 8 of [23].
For the proof see Section <ref>.

Let $\overline{\underline{X}}$ be a random vector distributed according
to an $\ell$-step distribution $\cP$ with $\rho(\cP) \le \rho < 1$ and
let $\mu^{(1)}, \ldots, \mu^{(\ell)} \in (0, 1]$.

There exist
$k \in \mathbb{N}$ and $\gamma > 0$ (both depending only
on $\cP$ and $\mu^{(1)}, \ldots, \mu^{(\ell)}$) such that for all functions
$f^{(1)}, \ldots, f^{(\ell)}: \underline{\Omega} \to [0, 1]$,
if $\EE[f^{(j)}(\underline{X}^{(j)})] = \mu^{(j)}$ and
$\max_{\sigma: 0 < |\sigma| \le k}
|\hat{f}^{(j)}(\sigma)| \le \gamma$, then

\begin{align}
\label{eq:89a}
\EE\left[\prod_{j=1}^{\ell} f^{(j)}(\underline{X}^{(j)}) \right]
\geq c(\cP, \mu^{(1)}, \ldots, \mu^{(\ell)}) > 0 \; .
\end{align}

§.§ Assumptions of the theorems

§.§.§ Equal distributions: unnecessary

In Theorems <ref>, <ref>
and <ref>  we assumed that the tuples
$(X_i^{(1)},\ldots,X_i^{(\ell)})$ are distributed
identically for each $i$.
It is natural to ask if it is indeed necessary.

This is not the case.
Instead, we made this assumption for simplicity of notation and presentation.
If one is interested in statements which are valid where coordinate
$i$ is distributed according to $\mathcal{P}_i$, one simply needs
to assume that there are  $\alpha > 0$ and $\rho < 1$ such
$\alpha(\mathcal{P}_i) \geq \alpha$ and $\rho(\mathcal{P}_i) \leq \rho$.

§.§.§ Equal marginals: necessary

We quickly discuss the case when $\cP$ does not have equal marginals.
Recall that $\beta(\cP) = \min_{x^{(1)}, \ldots, x^{(\ell)} \in \Omega}
\cP(x^{(1)}, \ldots, x^{(\ell)})$. If $\beta(\cP) > 0$, then,
by Theorem <ref>, $\cP$ is set hitting,
and therefore also same-set hitting.

In case $\beta(\cP) = 0$, we demonstrate an example which shows that
$\EE\left[\prod_{j=1}^\ell f(\underline{X}^{(j)}) \right]$
can be exponentially small in $n$.
For concreteness, we set $\ell := 2$ and $\Omega := \{0,1\}$
and consider $\mathcal{P}$ which picks uniformly
among $\{00, 01, 11\}$.
We then set

\begin{align}
S_1 &:= \{(x_1,\ldots,x_n) \mid x_1 = 1 \land
|\wt(x) - n/3| \leq 0.01n\}\\
S_2 &:= \{(x_1,\ldots,x_n) \mid x_1 = 0 \land
|\wt(x) - 2n/3| \leq 0.01n\}
\end{align}

where $\wt(x)$ is the Hamming-weight of $x$, i.e., the number of ones
in $x$.

For large enough $n$, a concentration bound
implies that $\Pr[\underline{X}^{(1)} \in S_1] > \frac{1}{3}-0.01$
and $\Pr[\underline{X}^{(2)} \in S_2] > \frac{1}{3}-0.01$.
Hence, if we set $f$ to be the indicator function of $S := S_1 \cup S_2$,
the assumption of Theorem <ref> holds.
However, because of the first coordinate we have
$\Pr[\underline{X}^{(1)} \in S \land \underline{X}^{(2)} \in S]
\leq \Pr[\underline{X}^{(1)} \in S_2 \lor \underline{X}^{(2)} \in S_1]$,
and the right hand side is easily seen to be exponentially

It is not difficult to extend this example to any distribution
with $\beta(\cP) = 0$ that does not
have equal marginals.

§ PROOF SKETCH

In this section we briefly outline the proof of Theorem <ref>.
For simplicity, we assume that the probability space is the one from
Section <ref>, i.e.,
$(X_i, Y_i)$ are distributed uniformly in $\{00, 11, 22, 01, 12, 20\}$.
Additionally, we assume that we are given a set $S \subseteq \{0,1,2\}^n$
with $\mu(S) = |S|/3^n > 0$, so that we want a bound of the form

\begin{align*}
\Pr\left[ \underline{X} \in S \land \underline{Y} \in S \right] \ge c(\mu) > 0 \; .
\end{align*}

The proof consists of three steps.
Intuitively, in the first step we deal with dictator sets, e.g.,
$S_{\mathrm{dict}} = \{ \underline{x}: x_1 = 0\}$,
in the second step with linear sets, e.g.,
$S_{\mathrm{lin}} = \{ \underline{x}: \sum_{i=1}^n x_i \pmod 3 = 0 \}$
and in the third step with threshold sets, e.g.,
$S_{\mathrm{thr}} = \{ \underline{x}: |\{i: x_i = 0\}| \ge n/3 \}$.

§.§ Step 1 — making a set resilient

We call a set resilient if $\Pr[\underline{X} \in S]$ does not change by more
than a (small) multiplicative constant factor whenever conditioned on
$(X_{i_1} = x_{i_1}, \ldots, X_{i_s} = x_{i_s})$ on a constant number $s$ of

In particular, $S_{\mathrm{dict}}$ is not resilient (because
conditioning on $x_1 = 0$ increases the measure of the set to $1$),
while $S_{\mathrm{lin}}$ and $S_{\mathrm{thr}}$ are.

If a set is not resilient, using $\mathcal{P}(x, x) = 1/6$ for every
$x \in \Omega$,
one can find an event $\cE :\equiv X_{i_1}=Y_{i_1}=x_{i_1} \land \ldots \land X_{i_s}=Y_{i_s}=x_{i_s}$
such that for some constant $\epsilon > 0$ we have
$\Pr[ \cE ] \ge \epsilon$ and, at the same time,
$\Pr[\underline{X} \in S \mid \cE] \ge (1+\epsilon)\Pr[\underline{X} \in S]$.

Since each such conditioning increases the measure of the set $S$ by a constant
factor, $S$ must become resilient after a constant number of its iterations. Furthermore,
each conditioning induces only a constant factor loss in
$\Pr[\underline{X} \in S \land \underline{Y} \in S]$.

§.§ Step 2 — eliminating high influences

In this step, assuming that $S$ is resilient, we condition on a constant
number of coordinates to transform it into two
sets $S'$ and $T'$ such that:

* Both of them have low influences on all coordinates.

* Both of them are supersets of $S$ (after the conditioning).

The first property allows us to apply low-influence set hitting
from $[20]$ to
$S'$ and $T'$. The second one, together with the resilience of $S$,
ensures that $\mu(S'), \mu(T') \ge (1-\epsilon)\mu(S)$.

In fact, it is more convenient to assume that we are initially
given two resilient sets $S$ and $T$.

Assume w.l.o.g. that $\Inf_i(T) \ge \tau$ for some $i \in [n]$.
Given $z \in \{0, 1, 2\}$, let
$T_z := \{\underline{x}: \underline{x} \in T \land x_i = z\}$.
Furthermore, let $T^*_z := T_z \cup T_{z+1 \pmod 3}$.

Since $\Inf_i(T) \ge \tau$, we can show that
there exists $z \in \{0,1,2\}$ such that, after conditioning on
$X_i = Y_i = z$,
the sum $\mu(S_z)+ \mu(T^*_z)$ is strictly greater than
the sum $\mu(S) + \mu(T)$:

\begin{align}
\label{eq:83a}
\Pr[\underline{X} \in S_z \mid X_i = z] +
\Pr[\underline{Y} \in T^*_z \mid Y_i = z]
\ge \Pr[\underline{X} \in S] + \Pr[\underline{Y} \in T] + c(\tau) \; .
\end{align}

We choose to delete the coordinate $i$ and replace
$S$ with $S' := S_z$ and $T$ with $T' := T^*_{z}$.
Equation (<ref>) implies that after a constant number of such
operations, neither $S$ nor $T$ has any remaining high-influence coordinates.

Crucially, with respect to same-set hitting our set replacement
is essentially equivalent to conditioning on
$X_i = z$ and $Y_i = z \lor Y_i = z + 1 \pmod 3$.
Therefore, each operation induces only a constant factor loss in
$\Pr[\underline{X} \in S \land \underline{Y} \in T]$.

§.§ Step 3 – applying low-influence theorem from

Once we are left with two low-influence, somewhat-large sets $S$
and $T$, we
$\Pr[\underline{X} \in S \land \underline{Y} \in T] \ge c(\mu) > 0$
by a straightforward application of a slightly
modified version of Theorem 1.14 from [20].
The theorem gives that $\rho(\mathcal{P}) < 1$ implies that
the distribution $\mathcal{P}$ is set hitting for low-influence functions:

Let $\overline{\underline{X}}$ be a random vector distributed
according to $(\overline{\underline{\Omega}}, \underline{\mathcal{P}})$
such that $\cP$ has equal marginals, $\rho(\mathcal{P}) \le \rho < 1$
and $\min_{x \in \Omega} \pi(x) \ge \alpha > 0$.

Then, for all $\epsilon > 0$, there exists
$\tau := \tau(\epsilon, \rho, \alpha, \ell) > 0$
such that if functions
$f^{(1)}, \ldots, f^{(\ell)}: \underline{\Omega} \to [0, 1]$ satisfy

\begin{align}
\max_{i \in [n], j \in [\ell]} \Inf_i(f^{(j)}(\underline{X}^{(j)})) \le \tau\;,
\end{align}

then, for $\mu^{(j)} := \EE[f^{(j)}(\underline{X}^{(j)})]$:

\begin{align}
\EE \left[ \prod_{j=1}^{\ell} f^{(j)}(\underline{X}^{(j)}) \right]
\ge \left( \prod_{j=1}^\ell \mu^{(j)} \right)^{\ell / (1-\rho^2)} - \epsilon \; .
\end{align}

Furthermore, there exists an absolute constant $C \ge 0$ such that
for $\epsilon \in (0, 1/2]$ one can take

\begin{align}\label{eq:38a}
\tau := \left(\frac{(1-\rho^2)\epsilon}{\ell^{5/2}}
\right)^{C \frac{\ell \ln(\ell/\epsilon)\ln(1/\alpha)}{(1-\rho)\epsilon}}
\; .
\end{align}

The proof of Theorem <ref> can be found in
Appendix <ref>.
The first part of the appendix contains a short
explanation of differences
between [20] and our version.

(X__) at (0,0) $\underline{\overline{X}}$;
(X1_) at (1,0) $\overline{X}_1$;
(X2_) at (2,0) $\overline{X}_2$;
(X3_) at (3,0) $\dots$;
(X4_) at (4,0) $\overline{X}_i$;
(X5_) at (5,0) $\dots$;
(X6_) at (6,0) $\overline{X}_n$;

(X_1) at (0,1) $\underline{X}^{(1)}$;
(X11) at (1,1) $X_1^{(1)}$;
(X21) at (2,1) $X_2^{(1)}$;
(X31) at (3,1) $\cdots$;
(X41) at (4,1) $X_i^{(1)}$;
(X51) at (5,1) $\cdots$;
(X51) at (6,1) $X_n^{(1)}$;

(X_2) at (0,2) $\underline{X}^{(2)}$;
(X12) at (1,2) $X_1^{(2)}$;
(X22) at (2,2) $X_2^{(2)}$;
(X32) at (3,2) $\cdots$;
(X42) at (4,2) $X_i^{(2)}$;
(X52) at (5,2) $\cdots$;
(X52) at (6,2) $X_n^{(2)}$;

(X_3) at (0,3) $\vdots$;
(X13) at (1,3) $\vdots$;
(X23) at (2,3) $\vdots$;
(X43) at (4,3) $\vdots$;
(X63) at (6,3) $\vdots$;

(X_4) at (0,4) $\underline{X}^{(j)}$;
(X14) at (1,4) $X_1^{(j)}$;
(X24) at (2,4) $X_2^{(j)}$;
(X34) at (3,4) $\cdots$;
(X44) at (4,4) $X_i^{(j)}$;
(X54) at (5,4) $\cdots$;
(X64) at (6,4) $X_n^{(j)}$;

(X_5) at (0,5) $\vdots$;
(X15) at (1,5) $\vdots$;
(X25) at (2,5) $\vdots$;
(X45) at (4,5) $\vdots$;
(X65) at (6,5) $\vdots$;

(X_6) at (0,6) $\underline{X}^{(\ell)}$;
(X16) at (1,6) $X_1^{(\ell)}$;
(X26) at (2,6) $X_2^{(\ell)}$;
(X36) at (3,6) $\cdots$;
(X46) at (4,6) $X_i^{(\ell)}$;
(X56) at (5,6) $\cdots$;
(X66) at (6,6) $X_n^{(\ell)}$;

[-] (0.5,-.5) to (0.5,6.5);
[-] (-.5,0.5) to (6.5,0.5);

(iid) at (4,-3) 4.2cmTuples $\overline{X}_{i}$ are
i.i.d. according to $\mathcal{P}$.
Each of the $\ell$ marginals of $\mathcal{P}$ is $\pi$.;

[->] (iid) to (X1_.north);
[->] (iid) to (X2_.north);
[->] (iid) to (X4_.north);
[->] (iid) to (X6_.north);

[rotate=0](rowdistr) at (-2.5, 4)
3cmVectors $\underline{X}^{(j)}$
are distributed (dependently) according to $\underline{\pi} := \pi^n$.
[->] (rowdistr) to (X_1.west);
[->] (rowdistr) to (X_2.west);
[->] (rowdistr) to (X_4.west);
[->] (rowdistr) to (X_6.west);

(commonDist) at (-1, -3)
3.2cmDistributed according to
[->] (commonDist) to (X__.north west);

(propertiesofP) at (0,9) 5cm
\begin{align*}
\alpha(\mathcal{P}) &:= \min_{x \in \Omega} \mathcal{P}(x,x,\ldots,x)\\
\rho(\mathcal{P}) &: \text{See Definition~\ref{def:correlation}}
\end{align*}

(domainsofxij) at (6,10) 4cm
\begin{align*}
X_{i}^{(j)} &\in \Omega\\
\underline{X}^{(j)} &\in \underline{\Omega} := \Omega^{n}\\
\overline{X}_{i} & \in \overline{\Omega} := \Omega^{\ell}\\
\underline{\overline{X}} & \in \underline{\overline{\Omega}}
:= \Omega^{n\cdot \ell}\\
S &\subseteq \underline{\Omega}
\end{align*}

Naming of the random variables in the general case.
The columns $\overline{X}_i$ are distributed $i.i.d$ according to
Each $X_{i}^{(j)}$ is distributed according to $\pi$.
The overall distribution of $\overline{\underline{X}}$ is

§.§ The case
rho = 1
: open question

Theorem <ref> requires that $\rho < 1$ in order to give a
meaningful bound.  It is unclear whether this is an artifact of our proof or if
it is necessary.  In particular, consider the three step distribution $\mathcal{P}$
picks a uniform triple from
$\{000, 111, 222, 012, 120, 201\}$.  One easily
checks that $\rho(\mathcal{P})=1$ and that all marginals are uniform.

We do not know if this distribution is same-set hitting.

However, the method of our proof breaks down.
We illustrate the reason in the following lemma.

For every $n > n_0$ there exist three sets $S^{(1)}$, $S^{(2)}$, and $S^{(3)}$ such
that for
the distribution $\mathcal{P}$ as described above we have

* $\forall j: \Pr[ \underline{X}^{(j)} \in S^{(j)} ] \geq 0.49$.

* $\Pr[\forall j: \underline{X}^{(j)} \in S^{(j)}] = 0$.

* The characteristic functions $\1_{S^{(j)}}$ of the three sets all

\begin{align*}
\max_{i \in [n]} \Inf_{i}(\1_{S^{(j)}}(\underline{X}^{(j)})) \to 0
\text{ as } n \to \infty \; .
\end{align*}

While the lemma does not give information about whether $\mathcal{P}$ is
same-set hitting, it shows that
our proof fails (since the analogue of Theorem <ref>

We let

\begin{align*}
S^{(1)} &:= \{\underline{x}^{(1)} : \text{$\underline{x}^{(1)}$ has
less than $n/3$ twos}\}\;,\\
S^{(2)} &:= \{\underline{x}^{(2)} : \text{$\underline{x}^{(2)}$ has
less than $n/3$ ones}\}\;,\\
S^{(3)} &:= \{\underline{x}^{(3)} : \text{$\underline{x}^{(3)}$ has
less than $n/3$ zeros}\}\;.
\end{align*}

Whenever we pick
$\underline{X}^{(1)}, \underline{X}^{(2)}, \underline{X}^{(3)}$, the number of
twos in $\underline{X}^{(1)}$ plus the number of ones in $\underline{X}^{(2)}$
plus the number of zeros in $\underline{X}^{(3)}$ always equals $n$ (there is a
contribution of one from each coordinate).  All three properties are now easy to

§ PROOF FOR GENERAL
RHO(K) < 1

The goal of this section is to prove our second main result, which we
restate here for convenience.

§.§ Properties of the correlation

Recall Definition <ref>.
We now give an alternative characterization of $\rho(\mathcal{P}, \{j\},
\allowbreak [\ell]\setminus \{j\})$ which will be useful later.
For this, we first define certain random process and an associated Markov chain.

Let $\mathcal{P}$ be a single-coordinate distribution
and let $j \in [\ell]$.
We call a collection of random variables
$(\overline{X}^{\setminus j}
= (X^{(1)}, \ldots, \allowbreak X^{(j-1)}, \allowbreak X^{(j+1)}, \ldots, X^{(\ell)}),
\allowbreak Y, Z)$
a double sample on step $j$ from $\mathcal{P}$ if:

* $\overline{X}$ is first sampled according to $\mathcal{P}$, ignoring step $j$.

* Assuming that $\overline{X}^{\setminus j} = \overline{x}^{\setminus j}$,
the random variables $Y$ and $Z$ are then sampled independently of each other
according to the
$j$-th step of $\cP$ conditioned on
$\overline{X}^{\setminus j} = \overline{x}^{\setminus j}$.

Sometimes we will omit $\overline{X}^{\setminus j}$ from the notation
and refer as double sample to $(Y, Z)$ alone.

An equivalent interpretation of a double sample
is that after sampling $(\overline{X}^{\setminus j}, Y)$ according to
$\cP$ we “forget” about $Y$ and sample $Z$ again from the same distribution
(keeping the same value of $\overline{X}^{\setminus j}$).
Therefore, both
$(\overline{X}^{\setminus j}, Y)$ and $(\overline{X}^{\setminus j}, Z)$
are distributed
according to $\mathcal{P}$.

If we let

\[
K(y,z) := \Pr[Z=z | Y=y] = \EE\left[\Pr\left[Z = z | Y = y, \overline{X}^{\setminus j}
\right]\right],
\]

we see that

\begin{align}
\pi(y)K(y,z) = \Pr[Y = y \land Z = z] = \Pr[Y = z \land Z = y]
= \pi(z)K(z,y) \;,
\end{align}

which means that $K$ is the kernel of a Markov chain that is reversible with
respect to $\pi$ (see e.g., <cit.>).  Thus, $K$ has an
orthonormal eigenbasis with eigenvalues
$1=\lambda_1(K) \geq \lambda_2(K) \geq \dots \geq \lambda_{|\Omega|}(K)\geq -1$,
(e.g., <cit.>).
We will say that $K$ is the Markov kernel induced by the double sample
$(Y, Z)$.

A standard fact from the Markov chain theory
expresses $\lambda_2(K)$ in terms of covariance of functions
$f \in L^2(\Omega, \pi)$:

Let $Y, Z$ be two consecutive steps of a reversible Markov chain with kernel
$K$ such that both $Y$ and $Z$ are distributed according to a stationary
distribution of $K$. Then,

\begin{align}
\label{eq:72a}
\lambda_2(K) = \max_{\substack{f: \Omega \to \mathbb{R} \\\EE[f(Y)] = 0\\\Var[f(Y)]=1}}
\EE\left[ f(Y) f(Z) \right] \; .
\end{align}

Let $\cP$ be a single-coordinate distribution and let
$(\overline{X}^{\setminus j}, Y, Z)$ be a double sample from $\cP$
that induces a Markov kernel $K$.

\begin{align*}
\lambda_2(K) = \rho(\mathcal{P},\{j\},[\ell]\setminus\{j\})^2 \; .
\end{align*}

For readability, let us write $\overline{X}$ instead of
$\overline{X}^{\setminus j}$.

Consider first two functions $f$ and $g$ as in
Definition <ref> and assume without loss of generality that
$\EE[f(Y)] = \EE[g(\overline{X})] = 0$.
Of course, we also assume that
$\Var[f(Y)]=\Var[g(\overline{X})]=1$ as specified by
Definition <ref>. We will show that

\begin{align}
\label{eq:73a}
\Cov\left[f(Y), g(\overline{X})\right]^2 \le \lambda_2(K) \; ,
\end{align}

and that there exists a choice of $f$ and $g$ that achieves equality
in (<ref>).

Let $h(\overline{x}) := \EE[f(Y) | \overline{X} = \overline{x}]$ and observe
[f(Y)f(Z)]    =    ∑_x,y,z [X=x]
[h(X)^2]   .

Now, by Cauchy-Schwarz, (<ref>) and Lemma <ref>
we see that
[f(Y),g(X)]^2    =    [f(Y)g(X)]^2 =
≤[h(X)^2] [g(X)^2]

=    [h(X)^2]
= [f(Y)f(Z)] ≤λ_2(K)   .

The equality is obtained for $f$ that maximizes the right-hand side of
(<ref>) and $g := c\cdot h$ for some $c > 0$.

For later use, we make the following implication of Lemma <ref>.

Let $(Y, Z)$ be a double sample on step $j$ from a single-coordinate
distribution $(\Omega, \mathcal{P})$ with $\rho(\cP) = \rho$.
Then, for every function $f: \Omega \to \mathbb{R}$,

\begin{align}
\EE[(f(Y)-f(Z))^2] \geq 2(1-\rho^2) \Var[f(Y)].
\end{align}

Assume w.l.o.g. that $\EE[f(Y)]=0$.
By Lemmas <ref> and <ref>,

\begin{align*}
\EE\left[ \left( f(Y)-f(Z) \right)^2 \right]
= 2\left( \Var[f(Y)] - \EE[f(Y)f(Z)] \right)
\ge 2(1-\rho^2)\Var[f(Y)] \; .
\end{align*}

§.§ Reduction to the resilient case

In this section, we will prove that we can assume that
the function $f$ is resilient in the following sense:
whenever we fix a constant number of inputs to some
value, the expected value of $f$ remains roughly the same.

The intuitive reason for this is simple: if there is some way to fix
the coordinates which changes the expected value of $f$, we
can fix these coordinates such that the expected value increases,
which only makes our task easier
(and can be done only a constant number of times).

We first make the concept of “fixing” a subset of the coordinates formal.

Let $f: \underline{\Omega} \to [0,1]$ be a function.
A restriction $\cR$ is a sequence $\cR = (r_1,\ldots,r_n)$
where each $r_i$ is either an element $r_i \in \Omega$,
or the special symbol $r_i = \star$.

The coordinates with $r_i = \star$ are unrestricted, the coordinates
where $r_i \in \Omega$ are restricted.
The size of a restriction is the number of restricted coordinates.

A restriction $\cR$ operates on a function $f$ as

\begin{align}
(\cR f) (x_1,\ldots,x_n) := f(y_1,\ldots,y_n) \;
\end{align}

where $y_i = r_i$ if $r_i \neq \star$ and $y_i = x_i$ otherwise.

Next, we define what it means for a function to be resilient:
restrictions do not change the expectation too much.

Let $\underline{X}$ be a random vector distributed according
to a (single-step) distribution $(\underline{\Omega}, \underline{\pi})$.
A function $f: \underline{\Omega} \to [0,1]$ is $\epsilon$-resilient up to
size $k$ if for every restriction $\cR$ of size at most $k$ we have that
$(1-\epsilon)\EE[f(\underline{X})] \leq \EE[\cR f(\underline{X})]
\leq (1+\epsilon)\EE[f(\underline{X})]$.

The function is upper resilient if the expectation cannot increase too much.

Let $\underline{X}$ be a random vector distributed according
to a distribution $(\underline{\Omega}, \underline{\pi})$.
A function $f: \underline{\Omega} \to [0,1]$ is $\epsilon$-upper resilient
up to size $k$ if for every
restriction $\cR$ of size at most $k$ we have that
$\EE[\cR f(\underline{X})] \leq (1+\epsilon) \EE[f(\underline{X})]$.

Resilience and upper resilience are equivalent up to a multiplicative
factor which depends only on $k$ and the smallest probability in the
marginal distribution  $\alpha(\pi)$.
Intuitively the reason is that if there is some restriction which
decreases the $1$-norm, then some other restriction on the same
coordinates must increase the $1$-norm somewhat.

Suppose that a function $f$ is $\epsilon$-upper resilient up to size $k$.
Then, $f$ is $\epsilon'$-resilient up to size $k$, where
$\epsilon' = \epsilon/(\alpha(\pi))^k$.

Fix a subset $S \subseteq [n]$ of the coordinates of size $|S| \le k$.
We consider a random variable $\cR$ whose values are
restrictions with restricted coordinates being exactly $S$.
The elements $r_i \in \Omega$ for $i \in S$ are picked according to the
distribution $\pi$.
We let $p(\cR')$ be the probability a certain restriction $\cR'$ is picked, and

\begin{align}
\EE[f(\underline{X})] =
\sum_{{\cR}'} p({\cR}') \cdot \EE \left[ \cR' f(\underline{X}) \right]
\; ,
\end{align}

where we sum over all restrictions $\cR'$ that restrict exactly the coordinates
in $S$.

Let now $\cR^*$ be one of the possible choices for $\cR$.

\begin{align*}
p(\cR^*) \cdot \EE[\cR^* f(\underline{X})]
&= \EE[f(\underline{X})] - \sum_{\cR' \neq \cR^*}p(\cR')\cdot
\EE[\cR' f(\underline{X})]
\\
\EE[f(\underline{X})] - (1+\epsilon)
\sum_{\cR' \neq \cR^*}p(\cR')\cdot \EE[f(\underline{X})]
\\
\left(1 - (1+\epsilon)(1-p(\cR^*))\right) \cdot \EE[f(\underline{X})]
\\
&\geq \left(p(\cR^*) -\epsilon\right) \cdot \EE[f(\underline{X})] \; ,
\end{align*}

and hence:

\begin{align*}
\EE[ \cR^* f(\underline{X}) ]
&\geq \left(1 - \frac{\epsilon}{p(\cR^*)}\right) \cdot \EE[f(\underline{X})]\;.
\end{align*}

Since $p(\cR^*)  \geq \alpha(\pi)^k$ we get the bound
for the restriction $\cR^*$, which was chosen arbitrarily.

Let $\overline{\underline{X}}$ be a random vector distributed according to
a distribution with equal marginals
$(\underline{\Omega}, \underline{\mathcal{P}})$
and $f: \underline{\Omega} \to [0, 1]$ be a function
with $\EE[f(\underline{X}^{(1)})] = \mu > 0$.

Let $\epsilon \in (0,1], k \in \mathbb{N}$. Then, there exists
a restriction $\cR$ such that $g := (\cR f)$ is $\epsilon$-resilient
up to size $k$ and

\begin{align}
\EE[g(\underline{X}^{(1)})] &\geq \mu
\label{eq:241a}\;,\\
\EE \left[ \prod_{j=1}^{\ell} f(\underline{X}^{(j)}) \right] &\ge
c \cdot \EE \left[ \prod_{j=1}^{\ell} g(\underline{X}^{(j)}) \right] \; ,
\label{eq:3a}
\end{align}

where $c := \exp\left(-\frac{2 \ln 1/\mu}{\alpha^{2k} \cdot \epsilon} \right)$
with $\alpha := \alpha(\mathcal{P}) > 0$.

In particular, $c$ depends only on $\epsilon, k, \alpha(\mathcal{P})$ and $\mu$
(requiring $\epsilon, \alpha(\mathcal{P}), \mu > 0$).

Let $\epsilon' := \alpha^k\cdot\epsilon$ and
choose a restriction $\cR$ such that
$\EE[\cR f(\underline{X}^{(1)})] \geq \EE[f(\underline{X}^{(1)})]
\cdot (1+\epsilon')$.
We repeat this, replacing $f$ with $(\cR f)$, until there is no such

Since the expectation of $f$ only increases, we get (<ref>).
Finally, once the process stops, the resulting function is $\epsilon$-resilient
due to Lemma <ref>
(note that $\alpha(\pi) \ge \alpha$).

It remains to argue that (<ref>) holds for the resulting function.
Note first that the expectation cannot exceed $1$, and
hence the process will be repeated at
most $p := \ln(1/\mu)/\ln(1+\epsilon') \le \frac{2\ln(1/\mu)}{\epsilon'}$ times.
Therefore, the final restriction $\cR$ obtained after at most $p$ iterations
of the process above is of size at most $pk$.

Define $g := (\cR f)$ and
let $\mathcal{E}$ be the event that all
strings $\underline{X}^{(1)},\ldots,\underline{X}^{(\ell)}$
agree with the restriction $\cR$ in its restricted coordinates.
We will use $\1(\cE)$ to denote the function which is
$1$ if event $\cE$ happens and $0$ otherwise.
We see that

\begin{align*}
\EE \left[ \prod_{j=1}^{\ell} f(X^{(j)}) \right] &\ge
\EE\left[ \prod_{j=1}^{\ell} f(X^{(j)}) \cdot \1(\mathcal{E}) \right]
\EE\left[ \prod_{j=1}^{\ell} g(X^{(j)}) \cdot \1(\mathcal{E}) \right]\\
\alpha^{pk}
\cdot \EE \left[ \prod_{j=1}^{\ell} g(X^{(j)}) \right] \; .
\end{align*}

\begin{align*}
\alpha^{pk} \ge
\exp\left(-\frac{2 k \ln (1/\alpha) \ln (1/\mu)}{\alpha^k \cdot \epsilon}\right)
\ge \exp \left( - \frac{2 \ln 1/\mu}{\alpha^{2k} \cdot \epsilon}  \right)
\; .
\end{align*}

§.§ Reduction to the low-influence case

We next show that if $f$ is resilient, we can also assume that it has
only low influences.
However, this part of the proof actually produces a collection of functions
$g^{(1)},\ldots, g^{(\ell)}$ such that each of them
has small influences: it operates differently on each function.
In turn, it is more convenient to do this part of the proof also starting
from a collection $f^{(1)},\ldots,f^{(\ell)}$, as long as all of
them are sufficiently resilient.

As in the previous section, we use restrictions.
Here, however, we are only interested in restrictions of size one.
Consequently, we write $\cR[i,a]$ to denote
the restriction $\cR = (r_1,\ldots,r_n)$
with $r_i = a$ and $r_{i'} = \star$ for $i' \neq i$.

Furthermore, we require a new operator.

Let $f: \underline{\Omega} \to [0, 1]$, $i \in [n]$,
and fix values $y, z \in \Omega$.

We define the operator $\mathcal{M}[i,y,z]$ as

\begin{align*}
(\mathcal{M}[i,y,z]f)(x_1, \ldots, x_n) :=
\max \bigl( f(&x_1, \ldots, x_{i-1}, y, x_{i+1},\ldots, x_n), \\
f(&x_1, \ldots, x_{i-1}, z, x_{i+1}, \ldots, x_n) \bigr) \; .
\end{align*}

The operator $\mathcal{M}[i,y,z]$ is useful for two reasons.
First, if $\Inf_i(f^{(j)})$ is “large”, then
$\EE\left[\mathcal{M}[i,y,z]f^{(j)}(\underline{X}^{(j)})\right] \geq
\EE[f^{(j)}(\underline{X}^{(j)})]+c$
for some $y,z \in \Omega$ and $c > 0$.  This implies that we can use this
operator to increase the expectation of a function unless all of its
influences are small. We will prove this property later.

Second, fix a step $j^* \in [\ell]$ and assume that for some values
$\overline{x}^{\setminus j^*} = (x^{(1)}, \ldots, x^{(j^*-1)}, \allowbreak
x^{(j^*+1)}, \ldots,
x^{(\ell)}), y, z \in \Omega$
both conditional probabilities
$\Pr[X_i^{(j^*)} = y \mid \overline{X}_i^{\setminus j^*} = \overline{x}^{\setminus
$\Pr[X_i^{(j^*)} = z \mid \overline{X}_i^{\setminus j^*} = \overline{x}^{\setminus
j^*}]$ are “somewhat large” (larger than some constant).
We imagine now that
$\overline{X}_i^{(\setminus j^*)} = \overline{x}^{\setminus j^*}$
and that we have also picked all values
$\underline{X}^{(j^*)}_{\setminus i} = (X_{1}^{(j^*)},\ldots,X_{i-1}^{(j^*)},
We then hope that $X^{(j^*)}_i$ is picked among $y$ and $z$ such that it
maximizes $f^{(j^*)}$.  Since this happens with constant probability, we
conclude the following: Suppose we replace $f^{(j^*)}$ with
$\mathcal{M}[i,y,z]f^{(j^*)}$ and then prove that afterwards
$\EE[\prod f^{(j)}(\underline{X}^{(j)})]$ is large.  Then,
$\EE[\prod f^{(j)}(\underline{X}^{(j)})]$ was large before.

This second point is formalized in the following lemma:

Let $\overline{\underline{X}}$ be a random vector distributed according to
$(\overline{\underline{\Omega}}, \underline{\mathcal{P}})$.  Fix $i \in [n]$,
$j^* \in [\ell]$
$\overline{x}^{\setminus j^*} = (x^{(1)},\ldots,x^{(j^*-1)},
x^{(j^*+1)},\ldots,x^{(\ell)}), y, z \in \Omega$.  Suppose that:

\begin{align}
\cP(\overline{x}^{\setminus j^*},y) &\ge \beta \;,
\label{eq:845a}\\
\cP(\overline{x}^{\setminus j^*},z) &\ge \beta
\label{eq:846a}\;.
\end{align}

Let $f^{(1)},\ldots,f^{(\ell)}: \underline{\Omega} \to [0,1]$, and
for $j \in [\ell]$ define:

\begin{align}
g^{(j)} :=
\begin{cases}
\cR[i,x^{(j)}]f^{(j)} & \text{if $j \neq j^*$,}\\
\cM[i,y,z]f^{(j)} & \text{if $j = j^*$.}
\end{cases}
\end{align}

\begin{align}\label{eq:6a}
\EE\left[\prod_{j=1}^{\ell} f^{(j)}(\underline{X}^{(j)})\right]
\geq
\beta \cdot \EE\left[\prod_{j=1}^{\ell} g^{(j)}(\underline{X}^{(j)})\right]\;.
\end{align}

We first define a random variable $A$,
which is the value among $y$ and $z$ which $X_{i}^{(j^*)}$ needs to take
in order to maximize $f^{(j^*)}$.

\begin{align}
A = \begin{cases}
y & \text{if
$f\left(\underline{X}^{(j^*)}_{\setminus i}, y\right)
> f\left(\underline{X}^{(j^*)}_{\setminus i}, z\right)$,} \\
z & \text{otherwise.}
\end{cases}
\end{align}

Consider now the event $\cE$ which occurs if
$\overline{X}_i = (\overline{x}^{\setminus j}, A)$.
We get

\begin{align*}
\EE\left[\prod_{j=1}^{\ell} f^{(j)}(\underline{X}^{(j)})\right]
\EE\left[
\prod_{j=1}^{\ell} f^{(j)}(\underline{X}^{(j)}) \cdot \1(\mathcal{E})
\right]
\\
\EE\left[
\prod_{j=1}^{\ell} g^{(j)}(\underline{X}^{(j)}) \cdot \1(\mathcal{E})
\right]\\
\EE\left[
\EE\left[
\prod_{j=1}^{\ell} g^{(j)}(\underline{X}^{(j)}) \cdot \1(\mathcal{E})
\middle |
\overline{\underline{X}}_{\setminus i}
\right]
\right]\\
\EE\left[
\prod_{j=1}^{\ell} g^{(j)}(\underline{X}^{(j)}) \cdot
\EE\left[
\1(\mathcal{E})
\middle |
\overline{\underline{X}}_{\setminus i}
\right]
\right]\\
\beta \cdot
\EE\left[
\prod_{j=1}^{\ell} g^{(j)}(\underline{X}^{(j)})
\right] \; .
\end{align*}

The equality from the first to the second line follows because
if the event $\cE$ happens, then the functions
and $g^{(j)}(\underline{X}^{(j)})$ are equal.
From the third to the fourth line we use that conditioned on
$\underline{\overline{X}}_{\setminus i}$ the
functions $g^{(j)}(\underline{X}^{(j)})$ are constant.
Finally, the last inequality follows because by (<ref>)
and (<ref>), for every choice of
$\underline{\overline{X}}_{\setminus i} =
\overline{X}_{i+1},\ldots,\overline{X}_{n})$ event $\mathcal{E}$
has probability at least $\beta$.

The obvious idea for the next step would be to
find values $\overline{x}^{\setminus j}, y, z$
such that

\begin{align*}
\EE\left[\cM[i,y,z]f^{(j^*)}(\underline{X}^{(j^*)})\right] \geq
\EE\left[f^{(j^*)}(\underline{X}^{(j^*)})\right]+c
\end{align*}

and fix them.

Unfortunately, there is a problem with this strategy.  To replace
the function $f^{(j^*)}$ with
$\cM[i,y,z] f^{(j^*)}$, Lemma <ref> also
replaces $f^{(j)}$ with $\cR[i,x^{(j)}]f^{(j)}$ for $j \ne j^*$ (and this is
required for the proof to work).  Unfortunately, it is possible that
$\EE\Big[\cR[i,x^{(j)}]f^{(j)}(\underline{X}^{(j)})\Big] \ll
\EE\Big[f^{(j)}(\underline{X}^{(j)})\Big]$.
We remark that we cannot use that $f^{(j)}$ is resilient here: while
$f^{(j)}$ is resilient the first time we condition, the functions
$\cM[i,y,z] f^{(j)}$ obtained in the subsequent steps are not resilient in general,
so later steps will not have the guarantee.

Our solution is to pick the values $(\overline{X}^{\setminus j^*}, Y, Z)$ at
random, as a double sample on coordinate $j^*$
(cf. Definition <ref>).

\begin{align*}
G^{(j)} := \begin{cases}
\cR[i,X^{(j)}]f^{(j)} &\text{if $j \ne j^*$,}\\
\cM[i, Y, Z]f^{(j)}  &\text{if $j = j^*$.}
\end{cases}
\end{align*}

We prove that (in expectation over
$\overline{X}^{(\setminus j)},Y,Z$) the sum of expectations
$\sum_{j=1}^\ell \EE[G^{(j)}(\underline{X}^{(j)})]$ is greater by a constant than
the sum $\sum_{j=1}^\ell \EE[f^{(j)}(\underline{X}^{(j)})]$.
To argue that the sum of expectations increases, the key part is to show that
$\EE\left[ G^{(j^*)}(\underline{X}^{(j^*)}) \right]$ increases by a constant.

Let $(\overline{X}^{\setminus j^*}, Y, Z)$ be a double sample from a
single-coordinate distribution $\mathcal{P}$.

Let $\underline{X}$ be a random vector, independent of this double sample
and distributed according to a single-step
distribution $(\underline{\Omega}, \underline{\pi})$ such that
$\pi$ is the $j^*$-th marginal distribution of $\mathcal{P}$.

Then, for every $i \in [n]$ and every function
$f: \underline{\Omega} \to [0,1]$ we have

\begin{align}
\EE\left[
\mathcal{M}[i,Y,Z]f(\underline{X}) \right]
\geq
\EE[f(\underline{X})] + \tau (1-\rho^2(\mathcal{P})) \; ,
\end{align}

where $\tau = \Inf_{i}(f(\underline{X}))$.

Recall that the distribution of $(Y,Z)$ depends on $j^*$.
We do not need to
consider the full multi-step process in this lemma, but when applying it later
we will set $\underline{X} = \underline{X}^{(j^*)}$ and $f = f^{(j^*)}$.

Fix a vector $\underline{x}_{\setminus i}$ for
$\underline{X}_{\setminus i}$,
and define the function $h: \Omega \to [0,1]$ as
$h(x) := f(\underline{x}_{\setminus i}, x)$.
By Corollary <ref>,

\begin{align*}
\EE[|h(Y) - h(Z)|]
\geq
\EE[(h(Y) - h(Z))^2]
\geq
2(1-\rho^2) \Var[h(Y)] \; ,
\end{align*}

and hence, averaging over $\underline{X}_{\setminus i}$,

\begin{align}\label{eq:19a}
\EE\Bigl[\Bigl|f(\underline{X}_{\setminus i}, Y) -
f(\underline{X}_{\setminus i}, Z) \Bigr|\Bigr]
\geq 2(1-\rho^2) \Inf_i(f(\underline{X}_{\setminus i}, Y))
= 2\tau(1-\rho^2) \; .
\end{align}

Since $Y$ and $Z$ are symmetric (i.e., they define a reversible Markov chain,
cf. remarks after Definition <ref>) and by (<ref>),

\begin{align*}
\EE \left[ \left(\cM[i, Y, Z]f-f\right)(\underline{X}) \right]
\EE \left[ \max(f(\underline{X}_{\setminus i}, Y), f(\underline{X}_{\setminus i}, Z))
- f(\underline{X}_{\setminus i}, Y) \right]
\\&=
\frac12 \EE \left[ \left| f(\underline{X}_{\setminus i}, Y) -
f(\underline{X}_{\setminus i}, Z) \right| \right]
\ge
\tau(1-\rho^2) \; ,
\end{align*}

as claimed.

Let a random vector $\overline{\underline{X}}$ be distributed according to
$(\overline{\underline{\Omega}}, \underline{\mathcal{P}})$ and functions
$f^{(1)}, \ldots, f^{(\ell)}: \underline{\Omega} \to [0, 1]$.
Let $i$, $j^*$ and $\tau$ be such that
$\Inf_{i}(f^{(j^*)}) \ge \tau \ge 0$ and let $\rho(\mathcal{P}) \le \rho \le 1$.

Pick a double sample $(\overline{X}^{(j^*)}, Y, Z)$ from $\mathcal{P}$ and let:

\begin{align}\label{eq:9a}
G^{(j)} :=
\begin{cases}
\cR[i,X^{(j)}]f^{(j)} & \text{if $j \neq j^*$}\\
\cM[i,Y,Z]f^{(j^*)} & \text{if $j = j^*$}.
\end{cases}
\end{align}

\begin{align}
\EE\left[\sum_{j=1}^{\ell} \EE[G^{(j)}(\underline{X}^{(j)}) \mid G^{(j)}] \right]
\geq
\sum_{j=1}^{\ell} \EE\left[ f^{(j)}(\underline{X}^{(j)})\right] + \tau \cdot (1-\rho^2)
\; .
\end{align}

Note that (<ref>) defines the functions $G^{(j)}$ as random variables
which is why we use capital letters.

If $j \neq j^*$ we have

\begin{align}
\EE \left[ \EE[G^{(j)}(\underline{X}^{(j)}) \mid G^{(j)}] \right]  =
\EE[f^{(j)}(\underline{X}^{(j)})]\;,
\end{align}

since the marginal distribution of $\underline{X}^{(j)}$ is exactly as in the
marginal $\pi$ of $\mathcal{P}$.
Hence, it suffices to show that

\begin{align*}
\EE\left[ \EE[G^{(j^*)}(\underline{X}^{(j^*)})
\mid G^{(j^*)} ] \right]
\EE\left[ \cM[i,Y,Z]f^{(j^*)}(\underline{X}^{(j^*)})
\right]
\\&\geq
\EE[f^{(j^*)}(\underline{X}^{(j^*)})] + \tau(1-\rho^2)\;,
\end{align*}

but this is exactly Lemma <ref>.

Let $\overline{\underline{X}}$ be a random vector distributed according to
$(\overline{\underline{\Omega}}, \underline{\mathcal{P}})$ and also let
$f^{(1)},\ldots,f^{(\ell)}: \underline{\Omega} \to [0,1]$,
$i \in [n]$, $j^* \in [\ell]$, $\Inf_{i}(f^{(j^*)}) \geq \tau \ge 0$,
$\rho(\mathcal{P}) \le \rho \le 1$.

Then, there exist values
$\overline{x}^{\setminus j^*} = (x^{(1)}, \ldots, x^{(j^*-1)}, x^{(j^*+1)}, \ldots,
x^{(\ell)}), y, z$
such that the functions

\begin{align}\label{eq:17a}
g^{(j)} := \begin{cases}
\cR[i,x^{(j)}]f^{(j)} & \text{if $j \neq j^*$}\\
\cM[i,y,z]f^{(j)} & \text{if $j = j^*$}
\end{cases}
\end{align}

\begin{align}
\sum_{j=1}^{\ell} \EE[ g^{(j)}(\underline{X}^{(j)})]
\sum_{j=1}^{\ell} \EE[f^{(j)}(\underline{X}^{(j)})] +
\tau(1-\rho^2)/2
\; , \label{eq:15a}\\
\EE\left[\prod_{j=1}^{\ell} f^{(j)}(\underline{X}^{(j)})\right]
\frac{\tau(1-\rho^2)}{2\ell|\Omega|^{\ell+1}}
\cdot \EE\left[\prod_{j=1}^{\ell} g^{(j)}(\underline{X}^{(j)})\right]\label{eq:16a}
\; .
\end{align}

While (<ref>) is immediate from
Lemma <ref>, we have to do a little bit of work
to guarantee (<ref>).

Choose $(\overline{X}^{\setminus j^*}, Y, Z)$ as a double sample
from $\mathcal{P}$ and let $G^{(j)}$ be defined as in

$p(\overline{x}^{\setminus j^*}, y, z) :=
\Pr[\overline{X}^{\setminus j^*} = \overline{x}^{\setminus j^*} \land
Y = y \land Z = z]$,
$\beta := \frac{\tau(1-\rho^2)}{2\ell|\Omega|^{\ell+1}}$,
an event $\cE :\equiv p(\overline{X}^{\setminus j^*}, Y, Z) < \beta$
and a random variable

\begin{align*}
A := \sum_{j=1}^\ell \EE[ G^{(j)}(\underline{X}^{(j)}) \mid G^{(j)} ] -
\EE[ f^{(j)}(\underline{X}^{(j)})] \; .
\end{align*}

By Lemma <ref>, we have $\EE[A] \ge \tau(1-\rho^2)$.

Since there are $|\Omega|^{\ell+1}$ possible tuples
$(\overline{x}^{\setminus j}, y, z)$, by union bound we have
$\Pr[\cE] \le |\Omega|^{\ell+1}\beta \le \tau(1-\rho^2)/2\ell < 1$ and hence it makes sense to consider
$\EE[A \mid \lnot \cE]$.  Bearing in mind the above and that
$A \in [-\ell, \ell]$,

\begin{align*}
\EE[A \mid \lnot \cE]
\ge
\EE[A \cdot \1(\lnot \cE)]
\ge
\EE[A] - \ell\Pr[\cE]
\ge
\tau (1-\rho^2)/2 \; .
\end{align*}

As a consequence, let us choose $(\overline{x}^{\setminus j^*}, y ,z)$
such that $A \ge \tau(1-\rho^2)/2$ and
$\cE$ does not happen. (<ref>) is now immediate, while for
(<ref>) observe that $\lnot \cE$ implies
$\mathcal{P}(\overline{X}^{\setminus j^*}, Y) \ge \beta$
and $\mathcal{P}(\overline{X}^{\setminus j^*}, Z) \ge \beta$
and apply Lemma

We can now repeat the process from Lemma <ref>
multiple times to get the result of this section.

Let $\overline{\underline{X}}$ be a random vector distributed according
to $(\overline{\underline{\Omega}}, \underline{\mathcal{P}})$ with
$\rho(\mathcal{P}) \le \rho < 1$.
Then, for every $\tau > 0$ there exist $k \in \mathbb{N}$ and
$\beta > 0$ such that:

For every $\epsilon \in [0, 1]$ and functions
$f^{(1)}, \ldots, f^{(\ell)}: \underline{\Omega} \to [0, 1]$ such that each
$f^{(j)}$ is $\epsilon$-resilient up to size $k$, there exist
$g^{(1)}, \ldots, g^{(\ell)}: \underline{\Omega} \to [0, 1]$
with the following properties:

* $\max_{j \in [\ell]} \max_{i \in [n]} \Inf_i(g^{(j)}(\underline{X}^{(j)}))
\leq \tau$.

* $\EE \left[ \prod_{j=1}^{\ell} f^{(j)}(\underline{X}^{(j)}) \right] \ge
\beta \cdot
\EE \left[ \prod_{j=1}^{\ell} g^{(j)}(\underline{X}^{(j)}) \right]$.

* For all $j \in [\ell]$:
$\EE[g^{(j)}(\underline{X}^{(j)})] \geq

Furthermore, one can take $k := \lfloor \frac{2\ell}{\tau(1-\rho^2)} \rfloor$
and $\beta := \left(\frac{\tau(1-\rho^2)}{2\ell|\Omega|^{\ell+1}}\right)^k$.

In particular, both $k$ and $\beta$ depend only on $\tau$ and $\mathcal{P}$
(requiring $\tau > 0$ and $\rho(\mathcal{P}) < 1$).

We repeat the process from Lemma <ref>,
always replacing the collection of functions $f^{(1)},\ldots,f^{(\ell)}$
with $g^{(1)},\ldots,g^{(\ell)}$ until condition $1$ is satisfied.
Since $\sum_{j=1}^{\ell} \EE[f^{(j)}(\underline{X}^{(j)})]$ cannot exceed $\ell$
and every time it increases by $\tau(1-\rho^2)/2$, we have to do this at most
$\frac{2 \ell}{ \tau (1-\rho^2)}$ times.

The first point is then obvious, and the second point follows
from Lemma <ref>.

Finally, the third point follows
because the functions $f^{(j)}$ are all $\epsilon$-resilient up to size
$k$, and each of the functions $g^{(j)}$ can be written as
a maximum of restrictions
of size at most $k$ of $f^{(j)}$. Since the maximum only increases expectations, the proof follows.

§.§ Finishing the proof

Let us assume that $\mu \in (0, 0.99]$, the computations being only easier if
this is not the case. To establish (<ref>), whenever we say
“constant”, in the $O()$ notation or otherwise, we mean “depending only on
$\mathcal{P}$ (in particular, on $\alpha$, $\rho$, $|\Omega|$ and $\ell$),
but not on $\mu$”.

The proof consecutively applies Lemma <ref>,
Corollary <ref> and
Theorem <ref>.

Given $f: \underline{\Omega} \to [0, 1]$ with
$\EE[f(\underline{X}^{(1)})] = \mu$, first apply Lemma
<ref> to $f$ with $\epsilon := 1/2$ and
$k := \exp\left(\left(1/\mu\right)^D\right)$ for a constant $D$ large enough
(where “large enough” will depend on another constant $D'$ to be defined
This gives us a function $g: \underline{\Omega} \to [0, 1]$ such that:

* $g$ is $\epsilon$-resilient up to size $k$.

* $\EE[g(\underline{X}^{(1)})] \ge \mu$.

\begin{align}
\label{eq:77a}
\EE\left[ \prod_{j=1}^\ell f(\underline{X}^{(j)}) \right]
\ge
c \cdot \EE \left[ \prod_{j=1}^\ell g(\underline{X}^{(j)}) \right] \; ,
\end{align}

c    =    1/exp( (1/α)^2k ·4ln1/μ) ≥1/exp( exp(O(k)) ·4ln1/μ)

1/exp(exp(exp((1/μ)^O(1))) ·4ln1/μ)

1/exp(exp(exp((1/μ)^O(1))))   .

Next, apply Corollary <ref>.
Set $g^{(1)} := \ldots := g^{(\ell)} := g$ and
$\tau := 1/\exp\left( \left(1/\mu\right)^{D'}\right)$ for a constant $D'$ large
We need to check if $k$ we have chosen satisfies the assumption
of Corollary <ref>:

\begin{align*}
\frac{2\ell}{\tau(1-\rho^2)}
\le
O\left(\exp\left( \left(1/\mu\right)^{D'}\right)\right)
\le
\exp\left( \left(1/\mu\right)^{O(1)}\right) \le k \; .
\end{align*}

Therefore, Corollary <ref> is applicable
and yields $h^{(1)}, \ldots, h^{(\ell)}: \underline{\Omega} \to [0, 1]$
such that:

* $\max_{j \in [\ell]} \max_{i \in [n]} \Inf_i(h^{(j)}(\underline{X}^{(j)})) \le
\tau$.

* $\forall j \in [\ell]: \EE[h^{(j)}(\underline{X}^{(j)})] \ge \mu/2$.

\begin{align}
\label{eq:78a}
\EE\left[ \prod_{j=1}^\ell g(\underline{X}^{(j)}) \right] \ge \beta \cdot \EE
\left[ \prod_{j=1}^\ell h^{(j)}(\underline{X}^{(j)}) \right] \; ,
\end{align}

β   =

1/exp((1/μ)^O(1) ·k)
≥1/exp(exp((1/μ)^O(1)))   .

Finally, we need to apply Theorem <ref>. To this end, set:

\begin{align*}
\epsilon := \left(\mu/2\right)^{\ell^2/(1-\rho^2)}/2 \ge \mu^{O(1)}
\end{align*}

and verify (<ref>):
)^O(ln(ℓ/ϵ) ln(1/α)/(1-ρ)ϵ)
Ω(ϵ)^(O(1) + ln1/ϵ)

1/exp( (O(1) + ln1/ϵ)^2 ·O(1/ϵ)  )

1/exp( (1/ϵ)^O(1) )
≥1/exp((1/μ)^O(1))   .

Hence, from Theorem <ref>:

\begin{align}
\label{eq:79a}
\EE\left[ \prod_{j=1}^\ell h^{(j)}(\underline{X}^{(j)}) \right]
\ge \epsilon / 2 \ge \mu^{O(1)} \; .
\end{align}

(<ref>), (<ref>) and (<ref>) put together give:

\begin{align*}
\EE \left[ \prod_{j=1}^\ell f(\underline{X}^{(j)}) \right]
\ge c \cdot \beta \cdot \mu^{O(1)}
\ge 1/\exp\left(\exp\left(\exp\left(\left(\left(1/\mu\right)^{O(1)}
\right)\right)\right)\right)
\; ,
\end{align*}

as claimed.

§ PROOF FOR TWO STEPS

Our goal in this section is to prove Theorem <ref>
assuming Theorem <ref>.

In the following  we will sometimes drop the assumption that $\Omega$ is
necessarily the support of a probability distribution $\mathcal{P}$.
One can check that this will not cause problems.

§.§ Correlation of a cycle

Assume we are given a support set $\Omega$ of size
$|\Omega| = k$. Let $s \ge 2, p \in (0, 1)$ and let $(x_0, \ldots, x_{s-1})$
be a pairwise disjoint sequence of $x_i \in \Omega$.

We call a probability distribution $\mathcal{C}$ over $\Omega$
an $(s, p)$-cycle if

\begin{align*}
\mathcal{C}(x, y) = \begin{cases}
p / s & \text{if } x=y=x_i \text{ for } i \in \{1, \ldots, s\} \; , \\
(1-p) / s &\text{if } x=x_i \land y=x_{(i+1) \bmod s} \text{ for } i \in \{1, \ldots, s\} \; ,\\
0 & \text{otherwise.}
\end{cases}
\end{align*}

Let $\mathcal{C}$ be an $(s, p)$-cycle. Then

\begin{align*}
\rho(\mathcal{C}) \le 1-\frac{7p(1-p)}{s^2} \; .
\end{align*}

Let $K$ be the Markov kernel induced by a double sample on $\mathcal{C}$
($K$ is the same whether a sample is on the first or the second step,
cf. Section <ref>). Observe that

\begin{align*}
K(y, z) := \begin{cases}
p^2 + (1-p)^2 & \text{if $y=z=x_i$,}\\
p(1-p) & \text{if $y=x_i$ and $z=x_{(i\pm 1) \bmod s}$.}
\end{cases}
\end{align*}

Let $\alpha_k := \frac{2\pi k}{s}$.
One can check that the eigenvalues
of $K$ are $\lambda_0, \ldots, \lambda_{s-1}$
with $\lambda_k := 1-2p(1-p)(1-\cos \alpha_k)$.
This is easiest if one knows the respective (complex) eigenvectors
$v_k := (1, \exp(\alpha_k \imath), \ldots, \exp((s-1)\alpha_k \imath))$
(where $\imath$ is the imaginary unit).

Using $\cos x \le 1-x^2/5$ for $x \in [0, \pi]$
and $\sqrt{1-x} \le 1-x/2$ for $x \in [0, 1]$ we obtain that if $k > 0$,

\begin{align*}
\sqrt{\lambda_k} \le \sqrt{1-2p(1-p)(1-\cos \alpha_1)}
\le
\sqrt{1-2p(1-p)\frac{4\pi^2}{5s^2}}
\le 1 - \frac{7p(1-p)}{s^2} \; .
\end{align*}

The bound on $\rho(\mathcal{C})$ now follows from Lemma <ref>.

§.§ Convex decomposition of

In this section we show that if a distribution $\mathcal{P}$
can be decomposed into a convex combination
of distributions $\mathcal{P} = \sum_{k=1}^{r} \alpha_k \cP_k$ and each
distribution $\cP_k$ is same-set hitting,
then also $\mathcal{P}$ is same-set hitting.

We say that a probability distribution with equal marginals $\cP$ has an
$(\alpha, \rho)$-convex decomposition if there exist
$\beta_1, \ldots, \beta_r > 0$ with $\sum_{k=1}^r \beta_k = 1$
and distributions with equal marginals
$\cP_1, \ldots, \cP_r$ such that

\begin{align*}
\cP = \sum_{k=1}^r \beta_k \cdot \cP_k \; .
\end{align*}

and $\alpha(\cP_k) \ge \alpha$ and $\rho(\cP_k) \le \rho$ for every $k \in [r]$.

Let an $\ell$-step distribution $\mathcal{P}$ with equal marginals have an
$(\alpha, \rho)$-convex decomposition
for some $\alpha > 0$ and $\rho < 1$.

Then, for every function $f: \underline{\Omega} \to [0, 1]$ with
$\EE[f(\underline{X}^{(1)})] = \mu > 0$:

\begin{align*}
\EE \left[ \prod_{j=1}^\ell f(\underline{X}^{(j)}) \right] \ge
c(\alpha, \rho, \ell, \mu) > 0 \; .
\end{align*}

Let us write the relevant decomposition as $\cP = \sum_{k=1}^r \beta_k \cP_k$.
The existence of this decomposition implies that there exists a random vector
$\underline{Z} = (Z_1, \ldots, Z_n)$ such that:

* The variables $Z_i \in [r]$ are i.i.d. with $\Pr[Z_i = k] = \beta_k$.

* For every $i \in [n]$ and $k \in [r]$, conditioned on $Z_i = k$,
the tuple $\overline{X}_i$ is distributed according to $\cP_k$.

Let $\underline{z}$ be an arbitrary assignment to $\underline{Z}$ and let
$\mu_{\underline{z}} := \EE[f(\underline{X}^{(1)}) \mid \underline{Z}=\underline{z}]$.
If $\mu_{\underline{z}} \ge \mu / 2$, by Theorem <ref>[
Technically, Theorem <ref> requires the distributions to
be the same for each coordinate, which is not the case in our setting. However,
this is not a problem, cf. Section <ref>.

\begin{align}
\label{eq:86a}
\EE \left[ \prod_{j=1}^\ell f(\underline{X}^{(j)}) \mid
\underline{Z}=\underline{z} \right] \ge
c(\alpha, \rho, \ell, \mu) > 0 \; .
\end{align}

Since $\EE[\mu_{\underline{Z}}] =
\EE[\EE[f(\underline{X}^{(1)}) \mid \underline{Z}]] =
\EE[f(\underline{X}^{(1)})] = \mu$, by Markov

\begin{align}
\label{eq:87a}
\Pr \left[ \mu_{\underline{Z}} \ge \mu / 2 \right] \ge \mu/2 \; .
\end{align}

(<ref>) and (<ref>) together give

\begin{align*}
\EE \left[ \prod_{j=1}^\ell f(\underline{X}^{(j)}) \right]
\ge \mu/2 \cdot c(\alpha, \rho, \ell, \mu) > 0 \; .
\end{align*}

§.§ Decomposition of
into cycles

Let us consider weighted directed graphs with non-negative weights
over a vertex set $\Omega$. We will identify such a digraph $G$
with its weight matrix.

We say that such a weighted digraph is regular, if for every vertex
the total weight of the incoming edges is equal to the total weight of
the outgoing edges.

We call a weighted digraph a weighted cycle, if it is a directed cycle
over a subset of $\Omega$ with all edges of the same weight $w > 0$.
We call $w$ the weight of the cycle and number of its edges $s$
the size of the cycle.

We say that a weighted digraph $G$ can be
decomposed into $r$ weighted cycles
if there exist weighted cycles $C_1, \ldots, C_r$  such that
$G = \sum_{k=1}^r C_k$.

Every regular weighted digraph $G$ over a set $\Omega$ of size $k$
can be decomposed into at most $k^2$ weighted cycles.

Since the digraph is regular, it must have a cycle. Remove it from the graph
(taking as weight $w$ the minimum weight of the edge on this cycle).

Since the resulting graph is still regular,
proceed by induction until the graph is empty.

At each step at least one edge is completely removed from the graph,
therefore there will be at most $k^2$ steps.

To see that a two-step distribution $\cP$ can be decomposed into cycles,
it will be useful to take $\cP' := \cP - \alpha \cdot \Id$ and
look at it as a weighted directed graph $(\Omega, \cP')$,
where $\cP'$ is interpreted as a weight function
$\cP': \Omega \times \Omega \to \mathbb{R}_{\ge 0}$.

Let $\cP$ be a two-step distribution
with equal marginals
over an alphabet $\Omega$ with size $t$.

Then, $\cP$ has a convex decomposition
$\cP = \sum_{k=1}^r \beta_k \cP_k$ such that each $\cP_k$ either
has support of size $1$ or is
an $(s, p)$-cycle with $2 \le s \le t$ and $p \in [\alpha(\cP)^3, 1/2]$.

Consequently, $\cP$ has an $(\alpha, \rho)$-convex decomposition with
$\alpha := \alpha(\cP)^4$ and $\rho := 1-3\alpha(\cP)^5$.

Throughout this proof we will treat $\mathcal{P}$ as a weight matrix of
a digraph. Since $\cP$ has equal marginals, this weighted digraph is regular.
Use Lemma <ref> to decompose
$\cP - \alpha(\cP) \cdot \Id$ into weighted cycles, which allows us to write

\begin{align*}
\cP = \alpha(\cP) \cdot \Id + \sum_{k=1}^{r} C_k \; ,
\end{align*}

where $C_k$ is a weighted cycle with weight $w_k$ and size $s_k$
and $r \le t^2$.
Take $\beta_k := \min(w_k, \alpha(\cP) / t^2)$ and let
$\Id_k$ be the identity matrix restricted to the support of $C_k$. Now we
can write $\cP$ as

\begin{align*}
\cP = \left( \alpha(\cP) \cdot \Id - \sum_{k=1}^{r} \beta_k \Id_k \right) +
\left( \sum_{k=1}^{r} s_k (w_k + \beta_k) \cdot
\frac{\beta_k \Id_k + C_k}{s_k(w_k + \beta_k)} \right) \; .
\end{align*}

Firstly, $\left( \alpha(\cP) \cdot \Id - \sum_{k=1}^{r} \beta_k \Id_k \right)$
can be decomposed into distributions with support size $1$.

As for the other term, note that
$\mathcal{C}_k := \frac{\beta_k \Id_k + C_k}{s_k(w_k + \beta_k)}$ is a probability
distribution that
either has support of size $1$ (iff $C_k$ has
support of size $1$) or is an $(s, p)$-cycle with
$2 \le s \le t$ and $p = \beta_k/(\beta_k+w_k)$.

If $\beta_k = w_k$, then $p  = 1/2$. If $\beta_k < w_k$, then
$1/2 \ge p = \beta_k / (\beta_k+w_k) \ge \beta_k = \alpha(\cP) / t^2 \ge
\alpha(\cP)^3$.
Therefore, $p \in [\alpha(\cP)^3, 1/2]$, as stated.

Consequently, $\alpha(\mathcal{C}_k) = p/s_k \ge \alpha(\cP)^4$
and, by Lemma <ref>,
$\rho(\mathcal{C}_k) \ge 1-3\alpha(\cP)^5$ and, since
every $(s,p)$-cycle has equal marginals,
we obtained
an $(\alpha, \rho)$-convex decomposition of $\cP$.

§.§ Putting things together

From Lemmas <ref> and

One can see that see that, as in Theorem <ref>, we obtain
a triply exponential explicit bound, i.e, there exists
$D(\alpha(\cP)) > 0$ such that if $\mu \in (0, 0.99]$, then

\begin{align*}
\EE\left[ f(\underline{X})f(\underline{Y}) \right]
\ge 1/\exp\left(\exp\left(\exp\left( \left(1/\mu\right)^D\right) \right)\right)\;.
\end{align*}

§ LOCAL VARIANCE

In this section we state and prove a generalization of the low-influence theorem
from [20]. We assume that the reader is familiar with
Fourier coefficients $\hat{f}(\sigma)$ and the basics of discrete function
analysis, for details see, e.g., Chapter 8 of [23].

[20] shows that $\rho(\cP) < 1$ implies that $\cP$ is set hitting
for low-influence functions. We extend this result to
a weaker notion of influence. In particular, we show that $\cP$ is set hitting
for functions with $\Omega(1)$ measure and $o(1)$ largest Fourier coefficient.
The main result of this section is Theorem <ref>.

We remark that Theorem <ref>
does not require equal marginals.
The rest of this section contains the proof of Theorem <ref>.
First, from Corollary <ref> and
Theorem <ref> it is easy to establish[
One needs to check that the assumption about equal marginals is not necessary,
but that turns out to be the case (the bound in Theorem <ref>
then depends on $\min_{j \in [\ell], x \in \supp(X^{(j)})} \pi^{(j)}(x)$).
] the following:

Let $\overline{\underline{X}}$ be a random vector distributed according to
an $\ell$-step distribution $\cP$ with $\rho(\cP) \le \rho < 1$ and
let $\epsilon \in [0, 1)$.

Then, for
all $\mu^{(1)}, \ldots, \mu^{(\ell)} \in (0, 1]$ there exists
$k(\cP, \epsilon, \mu^{(1)}, \ldots, \mu^{(\ell)}) \in \mathbb{N}$
such that for all functions
$f^{(1)}, \ldots, f^{(\ell)}: \underline{\Omega} \to [0, 1]$,
if $\EE[f^{(j)}(\underline{X}^{(j)})] = \mu^{(j)}$ and
if $f^{(1)}, \ldots, f^{(\ell)}$ are all $\epsilon$-resilient up to size
$k$, then

\begin{align}
\EE\left[\prod_{j=1}^{\ell} f^{(j)}(\underline{X}^{(j)}) \right]
\geq c(\cP, \epsilon, \mu^{(1)}, \ldots, \mu^{(\ell)}) > 0 \; .
\end{align}

Let $\pi$ be a single-step distribution and let
$f: \underline{\Omega} \to \bbR$ be a
function. Let $S \subseteq [n]$ with $|S| = k$.
We define $f^{\subseteq S}: \underline{\Omega} \to \bbR$ as

\begin{align}
f^{\subseteq S}(\underline{x}) :=
\EE[f(\underline{x}_S,\underline{X}_{\overline S})] \; ,
\end{align}

where $\overline S := [n] \setminus S$, $\underline{x}_{S}$
is the vector $\underline{x}$ restricted to coordinates in $S$,
and $\underline{X}_{\overline{S}}$ is a random vector of
$n-k$ elements with each coordinate distributed i.i.d. in $\pi$.

A proof of the following claim can be found, e.g., in [23]:

Let $\pi$ be a single-step distribution and let
$f: \underline{\Omega} \to \bbR$, $S \subseteq [n]$.
If a random vector $\underline{X}$
is distributed according to $\underline{\pi}$
and $\phi_0, \ldots, \phi_{m-1}$ form a Fourier basis for $\pi$ and
$f = \sum_{\sigma \in \mathbb{N}^n_{< m}}
\hat{f}(\sigma) \phi_{\sigma}$, then
$f^{\subseteq S} = \sum_{\sigma: \supp(\sigma) \subseteq S}
\hat{f}(\sigma) \phi_{\sigma}$.
In particular,

\begin{align*}
\Var\left[f^{\subseteq S}(\underline{X})\right] =
\sum_{\substack{\sigma: \supp(\sigma) \subseteq S,\\
\sigma \ne 0^n}}
\left|\hat{f}(\sigma)\right|^2 \; .
\end{align*}

Let a random vector $\underline{X}$ be distributed according to a single-step
distribution $\underline{\pi}$ with
$\min_{x \in \Omega} \pi(x) \ge \alpha$ and
let $\epsilon \in [0, 1]$, $k \in \mathbb{N}$.

Then, for every $f: \underline{\Omega} \to \mathbb{R}_{\ge 0}$
with $\EE[f(\underline{X})] = \mu$, if for every
$S \subseteq[n]$ with $|S| = k$ it holds that

\begin{align*}
\Var\left[f^{\subseteq S}(\underline{X})\right] \le \alpha^{k}(\epsilon\mu)^2 \; ,
\end{align*}

then $f$ is $\epsilon$-resilient up to size $k$.

We prove the contraposition.

If $f$ is not $\epsilon$-resilient up to size $k$, by definition
of $f^{\subseteq S}$ it implies that there exist $S \subseteq [n]$ with
$|S| = k$ and $\underline{x}$ such that

\begin{align*}
\left| f^{\subseteq S}(\underline{x}) -
\EE[f^{\subseteq S}(\underline{X})] \right| >
\epsilon \EE[f^{\subseteq S}(\underline{X})]
= \epsilon\mu \; .
\end{align*}

But this gives

\begin{align*}
\Var\left[ f^{\subseteq S}(\underline{X}) \right]
\ge \alpha^k
\left(f^{\subseteq S}(\underline{x}) - \EE[f^{\subseteq S}(\underline{X})]
\right)^2
> \alpha^{k} (\epsilon\mu)^2 \; ,
\end{align*}

as required.

Using Lemma <ref> we can weaken
the assumption in Theorem <ref>
such that it only requires that all Fourier coefficients of degree at most $k$
are small:

From Theorem <ref>, there exists
$k := k(\cP, \mu^{(1)}, \ldots, \mu^{(\ell)})$ such that if
$f^{(1)}, \ldots, f^{(\ell)}$ are all $1/2$-resilient up to size $k$,
then (<ref>) holds. Therefore, it is sufficient to show that
the functions $f^{(j)}$ are indeed $1/2$-resilient up to size $k$
if the parameter $\gamma$ is chosen small enough.

By Claim <ref>, if $\max_{\sigma: 0<| \sigma|\le k}
|\hat{f}^{(j)}(\sigma)| \le \gamma$, then for any
$S \subseteq [n]$ with $|S| = k$ we have
$\Var\left[ (f^{(j)})^{\subseteq S}(\underline{X}^{(j)})\right]
\le 2^k \gamma^2$. With that in mind it is easy to choose $\gamma$
such that Lemma
can be applied to each $f^{(j)}$.

§ MULTIPLE STEPS OF A MARKOV CHAIN

Next, we consider the case where the distribution $\cP$
is such that the random variables
$X^{(1)},X^{(2)},\ldots,X^{(\ell)}$ form a Markov chain.

Let $\cP$ be a an $\ell$-step distribution with equal marginals and let
$\overline{X} = (X^{(1)}, \ldots, X^{(\ell)})$ be a random variable distributed
according to $\cP$. We say that
$\mathcal{P}$ is generated by Markov chains[
Note that our definition allows for different Markov chains
in different steps.
] if for every $j \in \{2, \ldots, \ell\}$ and
$x^{(1)}, \ldots, x^{(j)} \in \Omega$ we have
[X^(j) = x^(j)  |  X^(1) = x^(1) …X^(j-1) = x^(j-1)]

[X^(j) = x^(j) | X^(j-1) = x^(j-1)]   .

Observe that since we still require $\mathcal{P}$ to have equal marginals,
the marginal $\pi$ is then simply a stationary distribution of the chain.

In this case, we give a reduction to Theorem <ref>
to prove a bound that does not depend on $\rho(\cP)$:

Let $\Omega$ be a finite set and $\cP$ a probability distribution over
$\Omega^{\ell}$ with equal marginals
generated by Markov chains.
Let tuples $\overline{X}_i = (X_i^{(1)}, \ldots, X_i^{(\ell)})$ be
i.i.d. according to $\mathcal{P}$ for $i \in \{1,\ldots,n\}$.

Then, for every $f: \Omega^n \to [0,1]$ with
$\EE[f(\underline{X}^{(1)})] = \mu > 0$:

\begin{align}
\EE \left[ \prod_{j=1}^\ell f(\underline{X}^{(j)}) \right]
\geq c \left( \alpha(\mathcal{P}), \ell, \mu \right)
\; ,
\end{align}

where the function $c()$ is positive whenever
$\alpha(\mathcal{P})> 0$.

Let $\cP$ be a distribution generated by Markov chains
with $\alpha := \alpha(\cP) > 0$ and let $f: \underline{\Omega} \to [0, 1]$
with $\EE[f(\underline{X}^{(1)})] = \mu > 0$.

The proof is by induction on $\ell$. For $\ell = 2$, apply
Theorem <ref> directly. For $\ell > 2$, define
the function $g: \underline{\Omega} \to [0, 1]$ as

\begin{align*}
g(\underline{x}) :=
\EE \left[ f(\underline{X}^{(\ell-1)})f(\underline{X}^{(\ell)}) \mid
\underline{X}^{(\ell-1)} = \underline{x} \right]
= f(\underline{x}) \cdot \EE \left[ f(\underline{X}^{(\ell)}) \mid
\underline{X}^{(\ell-1)} = \underline{x} \right] \; .
\end{align*}

Applying Theorem <ref> for the distribution
of the last two steps,

\begin{align}
\label{eq:88a}
\EE[g(\underline{X}^{(1)})] =
\EE[g(\underline{X}^{(\ell-1)})] =
\EE[ f(\underline{X}^{(\ell-1)}) f(\underline{X}^{(\ell)}) ] \ge
c(\alpha, \mu) > 0 \; .
\end{align}

Now we have
[ ∏_j=1^ℓ f(X^(j)) ]
[ ( ∏_j=1^ℓ-2 f(X^(j)) )
g(X^(ℓ-1)) ]

[ ∏_j=1^ℓ-1 g(X^(j)) ]

c(α, ℓ-1, c(α, μ) ) = c(α, ℓ, μ) > 0,

where (<ref>) holds since $\cP$ is generated by Markov chains,
(<ref>) is due to $f \ge g$ pointwise and
(<ref>) is an application of the induction and (<ref>).

Unfortunately, this proof worsens the explicit bound. One can check that
for a Markov-generated distribution with $\ell$ steps the dependence on $\mu$
is a tower of exponentials of height $3(\ell-1)$.

§ POLYNOMIAL SAME-SET HITTING

The property of set hitting establishes a lower bound on
$\EE\left[ \prod_{j=1}^\ell f^{(j)}(\underline{X}^{(j)})\right]$ that is
independent of $n$. However, it might be the case that this bound is very
small, perhaps far from the best possible one. In particular, our bound
from Theorem <ref> is triply exponentially small, and
the bound from Theorem <ref> is not even primitive recursive.

A distribution $\mathcal{P}$ is polynomially set hitting
(resp. polynomially same-set hitting) if there exists $C \ge 0$
such that $\mathcal{P}$ is $(\mu, \mu^C)$-set hitting (resp. same-set hitting)
for every $\mu \in (0, 1]$.

As a matter of fact, [21]
(cf. Theorem <ref>) establishes that
all distributions that are set hitting are also polynomially set hitting.
We suspect that this is also the case for two-step same-set hitting,
but this remains an open problem.

However, it is possible to harness reverse hypercontractivity to show
that all symmetric two-step distributions are polynomially same-set

Let a two-step probability distribution with equal marginals
$\mathcal{P}$ be symmetric, i.e.,
$\mathcal{P}(x, y) = \mathcal{P}(y, x)$ for all $x, y \in \Omega$.
If $\alpha(\mathcal{P}) > 0$, then $\mathcal{P}$ is polynomially same-set

We omit the proof of Theorem <ref>,
noting that the idea is similar as in Section <ref>:
one performs an obvious convex decomposition of $\mathcal{P}$ into cycles
of length two and applies
the result of [21] to each term of this decomposition.

[1]
Per Austrin and Elchanan Mossel.
Noise correlation bounds for uniform low degree functions.
Arkiv för Matematik, 51(1):29–52, 2013.

[2]
William Beckner.
Inequalities in Fourier analysis.
Annals of Mathematics, 102(1):159–182, 1975.

[3]
Aline Bonami.
Étude des coefficients de Fourier des fonctions de $L^p(G)$.
Annales de l'institut Fourier, 20(2):335–402, 1970.

[4]
Christer Borell.
Positivity improving operators and hypercontractivity.
Mathematische Zeitschrift, 180(3):225–234, 1982.

[5]
Christer Borell.
Geometric bounds on the Ornstein–Uhlenbeck velocity process.
Zeitschrift für Wahrscheinlichkeitstheorie und verwandte
Gebiete, 70(1):1–13, 1985.

[6]
Wei-Kuo Chen, Nikos Dafnis, and Grigoris Paouris.
Improved Hölder and reverse Hölder inequalities for Gaussian
random vectors.
Advances in Mathematics, 280:643–689, 2015.

[7]
Irit Dinur, Ehud Friedgut, and Oded Regev.
Independent sets in graph powers are almost contained in juntas.
Geometric and Functional Analysis, 18(1):77–97, 2008.

[8]
Harry Furstenberg and Yitzhak Katznelson.
A density version of the Hales-Jewett theorem.
Journal d’Analyse Mathématique, 57(1):64–119, 1991.

[9]
Harry Furstenberg.
Ergodic behavior of diagonal measures and a theorem of Szemerédi
on arithmetic progressions.
Journal d'Analyse Mathématique, 31(1):204–256, 1977.

[10]
Venkatesan Guruswami and Euiwoong Lee.
Strong inapproximability results on balanced rainbow-colorable
In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium
on Discrete Algorithms, pages 822–836, 2015.

[11]
W. T. Gowers.
A new proof of Szemerédi's theorem.
Geometric & Functional Analysis GAFA, 11(3):465–588, 2001.

[12]
W. T. Gowers.
Hypergraph regularity and the multidimensional Szemerédi theorem.
Annals of Mathematics, 166(3):897–946, 2007.

[13]
Ben Green.
Finite field models in additive combinatorics.
In Bridget S Webb, editor, Surveys in Combinatorics, pages
1–27. 2005.

[14]
Leonard Gross.
Logarithmic Sobolev inequalities.
American Journal of Mathematics, 97(4):1061–1083, 1975.

[15]
Jan Hązła, T. Holenstein, and E. Mossel.
Lower Bounds on Same-Set Inner Product in Correlated Spaces.
In APROX/RANDOM, volume 34, pages 1–11, 2016.

[16]
Michel Ledoux.
Remarks on Gaussian noise stability, Brascamp-Lieb and
Slepian inequalities.
In Geometric Aspects of Functional Analysis: Israel Seminar
(GAFA) 2011–2013, pages 309–333, 2014.

[17]
David A. Levin, Yuval Peres, and Elizabeth L. Wilmer.
Markov Chains and Mixing Times.
American Mathematical Society, 2008.

[18]
Elchanan Mossel, Ryan O'Donnell, and Krzysztof Oleszkiewicz.
Noise stability of functions with low influences: Invariance and
Annals of Mathematics, 171(1):295–341, 2010.

[19]
Elchanan Mossel, Ryan O'Donnell, Oded Regev, Jeffrey E. Steif, and Benny
Non-interactive correlation distillation, inhomogeneous Markov
chains, and the reverse Bonami-Beckner inequality.
Israel Journal of Mathematics, 154(1):299–336, 2006.

[20]
Elchanan Mossel.
Gaussian bounds for noise correlation of functions.
Geometric and Functional Analysis, 19(6):1713–1756, 2010.

[21]
Elchanan Mossel, Krzysztof Oleszkiewicz, and Arnab Sen.
On reverse hypercontractivity.
Geometric and Functional Analysis, 23(3):1062–1097, 2013.

[22]
Edward Nelson.
The free Markoff field.
Journal of Functional Analysis, 12(2):211–227, 1973.

[23]
Ryan O'Donnell.
Analysis of Boolean Functions.
Cambridge University Press, 2014.

[24]
Klaus F. Roth.
On certain sets of integers.
Journal of the London Mathematical Society, s1-28(1):104–109,

[25]
Vojtěch Rödl and Jozef Skokan.
Regularity lemma for k-uniform hypergraphs.
Random Structures & Algorithms, 25(1):1–42, 2004.

[26]
Vojtěch Rödl and Jozef Skokan.
Applications of the regularity lemma for uniform hypergraphs.
Random Structures & Algorithms, 28(2):180–194, 2006.

[27]
Walter Rudin.
Real and Complex Analysis.
McGraw-Hill, Inc., 3rd edition, 1987.

[28]
Endre Szemerédi.
On sets of integers containing no k elements in arithmetic
Acta Arithmetica, 27(1):199–245, 1975.

[29]
Terence Tao and Van H. Vu.
Additive Combinatorics.
Cambridge University Press, 2006.

[30]
Paweł Wolff.
Hypercontractivity of simple random variables.
Studia Mathematica, 180:219–236, 2007.

§ PROOF OF THEOREM <REF>

Our proof of Theorem <ref> follows in this appendix.
It is only a slight adaptation of the argument from [20], but
we include it in full for the sake of completeness.

We first restate the theorem and discuss the differences between
our proof and the one in [20]:

Theorem <ref> is very similar to a subcase of Theorem 1.14
from [20].  We make a stronger claim with one respect: in
[20] the influence threshold $\tau$ depends among others on:

\begin{align}
\label{eq:74a}
\alpha^* := \min_{(x^{(1)}, \ldots, x^{(\ell)}) \in \supp(\mathcal{P})}
\mathcal{P}(x^{(1)}, \ldots, x^{(\ell)}) \; ,
\end{align}

while our bound depends only on the smallest marginal probability:

\begin{align}
\label{eq:75a}
\alpha = \min_{x \in \Omega} \pi(x) \; .
\end{align}

The main differences to the proof in [20] are:

20 proves the base case $\ell=2$ and then obtains the result
for general $\ell$ by an inductive argument
(cf., Theorem 6.3 and Proposition 6.4 in [20]). Since the induction
is applied to functions $f^{(1)}$ and $g := \prod_{j=2}^{\ell} f^{(j)}$,
where $g$ is viewed as a function on a single-step space, the information
on the smallest marginal is lost in the case of $g$. To avoid this, our proof
proceeds directly for general $\ell$. However, the structure
and the main ideas are really the same as in [20].

* In hypercontractivity bounds for Gaussian and discrete spaces
(Theorem <ref> and
Lemma <ref>) we are slightly more careful
to obtain bounds which depend on $\alpha$ rather than $\alpha^*$
(as defined in (<ref>) and (<ref>)). This better
bound is then propagated in the proof of the invariance principle.

* Another change is not related to the dependency on the smallest
marginal. For the Gaussian reverse hypercontractivity bound
(Theorem <ref>) instead of
using the result of Borell ([5], Theorem 5.1 in [20])
for a bound expressed in terms of the cdf
of bivariate Gaussians, we utilize the results of [6] and [16]
for a more convenient bound
of the form $\left(\prod_{j=1}^\ell \mu^{(j)}\right)^{c(\rho, \ell)}$.

The proof can be generalized in several directions, but for the sake
of clarity we present the simplest version sufficient for our purposes.

§.§ Preliminaries — the general framework

We start with explaining the notation of random variables and $L^2$ spaces
that we will use throughout the proof.

Let $(\Omega, \mathcal{F}, \mathcal{P})$ be a probability space.
We define the real inner product space $L^2(\Omega, \mathcal{P})$
as the set of all square-integrable functions
$f: \Omega \to \mathbb{R}$, i.e., the functions that satisfy

\begin{align}
\int_{\Omega} f^2 \, \mathrm{d}\mathcal{P} < +\infty \; ,
\label{eq:44a}
\end{align}

with inner product defined as

\begin{align}
\langle f, g \rangle := \int_{\Omega} fg \, \mathrm{d}\mathcal{P} \; .
\label{eq:45a}
\end{align}

As we will see shortly,
if $X$ is a random variable sampled from $\Omega$ according to
the equations (<ref>) and (<ref>) can be written as
[f^2(X)]     <     +∞  ,

⟨f, g ⟩    =     [f(X) g(X)]   .

We omitted the event space $\mathcal{F}$ in the definition
of $L^2(\Omega, \mathcal{P})$. This is because $\mathcal{F}$ is always
implicit in the choice of the measure $\mathcal{P}$.

In particular,  when $\mathcal{P}$ is discrete,
of course we choose $\mathcal{F}$ to be the powerset
of $\Omega$.
When $\mathcal{P}$ is continuous over $\mathbb{R}^n$,
we use the “standard” real event space, i.e., the
completion of the Borel algebra.

While this will not be our usual way of thinking,
at this point it makes sense to introduce the formal
definition of a random variable: a function from a probability
space to some set.

Let $(\Sigma, \mathcal{F}, \mathcal{P})$ be a probability space.
We say that $X$ is a random variable over
a set  $\Sigma'$
if it is a measurable function $X: \Sigma \to \Sigma'$.

As usual, we will assume throughout the
proof that all random variables are induced by some underlying probability
space $(\Sigma,\mathcal{F},\mathcal{P})$.

Using this,
a random variable induces some distribution, which we can study.

We say that a random variable $X$ over a set $\Omega$ is distributed
according to a probability space $(\Omega, \mathcal{P})$
if for every event $A \in \mathcal{F}$:

\begin{align*}
\Pr[X \in A] = \mathcal{P}(A) \; .
\end{align*}

Let $X$ be a random variable distributed over $\Omega$.
By $L^2(X)$ we denote the inner product space of random variables that
correspond to square-integrable functions $f: \Omega \to \mathbb{R}$:

\begin{align*}
L^2(X) := \{ Z \mid Z = f \circ X \text{ for some } f:\Omega \to \mathbb{R}
\text{ with } \EE[f(X)^2] < +\infty  \} \; ,
\end{align*}

with the inner product given as

\begin{align*}
\langle Z_1, Z_2 \rangle := \EE[ Z_1 \cdot Z_2 ] \; .
\end{align*}

We consider the formal setting again, i.e.,
suppose $(\Sigma, \mathcal{F}, \mathcal{P})$ is the underlying probability
space, and $X: \Sigma \to \Omega$ a random variable.
Then, $L^{2}(X)$ is a subspace of $L^2(\Sigma,\mathcal{P})$.
Intuitively, it contains all real valued functions
which “depend only on $X$”.

Fix $(\Omega, \mathcal{P})$ to be the uniform distribution on
$\Omega := \{0, 1, 2\}$ and let $X$ be distributed according
to $(\Omega, \mathcal{P})$. Then $L^2(X)$ has dimension three
and one of its orthonormal bases is
Z_0     :≡    1

Z_1    :=
√(6)/2     if $X=0$,

-√(6)/2     if $X=1$,

0     if $X=2$.

Z_2    :=
√(2)/2     if $X \in \{0,1\}$,

-√(2)     if $X=2$.

After this point, we will have no need to refer explicitly
to the underlying probability space $(\Sigma,\mathcal{F},\mathcal{P})$ anymore.
Nevertheless, it will be useful to remember that random variables are
functions of this underlying space.

It immediately follows from the definitions that:

Let $X$ be a random variable distributed according to $(\Omega, \mathcal{P})$.
Then $L^2(X)$ is isomorphic to $L^2(\Omega, \mathcal{P})$.

§.§ Preliminaries — orthonormal ensembles and multilinear polynomials

In this section we introduce orthonormal ensembles
and multilinear polynomials over them.

We call a finite family $(\mathcal{X}_0, \ldots, \mathcal{X}_p)$
of random variables orthonormal
if they satisfy $\EE[\mathcal{X}_k^2] = 1$ for every $k$
and $\EE[\mathcal{X}_j \mathcal{X}_k ] = 0$ for every $j \ne k$.

We call a finite family of orthonormal random variables
$\mathcal{X} = (\mathcal{X}_{\star,0} = 1, \mathcal{X}_{\star,1},
\ldots, \mathcal{X}_{\star,p})$
an $\emph{orthonormal ensemble}$.
We call $p$ the size of the ensemble.

An $\emph{ensemble sequence}$ is a sequence of independent families of
random variables
$\underline{\mathcal{X}} = (\mathcal{X}_1, \ldots, \mathcal{X}_n)$
such that each $\mathcal{X}_i$ is an orthonormal ensemble
$\mathcal{X}_i = (\mathcal{X}_{i,0} = 1, \mathcal{X}_{i,1},
\ldots, \mathcal{X}_{i,p})$ of the same size $p$.
We call $n$ the size of the sequence.

The notation $\mathcal{X}_{\star, k}$ is a little awkward, but we do not
need to use it often.
The reason for it is that we want to to make sure that one cannot confuse
one of the random variables $\mathcal{X}_{\star,k}$ within an orthonormal
ensemble with the orthonormal ensemble $\mathcal{X}_i$ itself.
Whenever a random variable $\mathcal{X}_{i,k}$ is part of an ensemble
there is no reason to use the $\star$-symbol.
Instead we use the index of the ensemble.

Note that in an orthonormal ensemble for $k>0$ we have $\EE[\mathcal{X}_{\star,k}]
= \EE[\mathcal{X}_{\star,k}\mathcal{X}_{\star,0}] = 0$.

We call two ensemble sequences
$\underline{\mathcal{X}} = (\mathcal{X}_1, \ldots, \mathcal{X}_n)$
and $\underline{\mathcal{Y}} = (\mathcal{Y}_1, \ldots, \mathcal{Y}_m)$
compatible if $n = m$ and the sizes of the individual ensembles
$\mathcal{X}_i$ and $\mathcal{Y}_i$ are the same.

Let $\underline{\mathcal{X}} = (\mathcal{X}_1, \ldots, \mathcal{X}_n)$
be an ensemble sequence such that each ensemble $\mathcal{X}_i$ is of size $p$.

A monomial compatible with $\underline{\mathcal{X}}$ is a term

\begin{align*}
x_\sigma := \prod_{i=1}^n x_{i,\sigma_i} \; ,
\end{align*}

where $\sigma = (\sigma_1, \ldots, \sigma_n)$ with
$\sigma_i \in \{0, \ldots, p\}$.

A (formal) multilinear polynomial
compatible with $\underline{\mathcal{X}}$ is
a sum of compatible monomials, i.e., a polynomial $P$ of the form

\begin{align*}
P(\underline{x}) =
\sum_{\sigma \in \{0,\ldots,p\}^n} \alpha(\sigma) x_{\sigma} =
\sum_{\sigma \in \{0,\ldots,p\}^n}
\alpha(\sigma) \prod_{i=1}^n x_{i, \sigma_i} \; ,
\end{align*}

where the sum goes over all tuples $\sigma = (\sigma_1,\ldots,\sigma_n)$
as above, and  $\alpha(\sigma) \in \mathbb{R}$.

For a tuple $\sigma$ we define its support
as $\supp(\sigma) := \{ i \in [n]: \sigma_i \ne 0 \}$
and its
degree as the size of its support:
$|\sigma| := |\supp(\sigma)|$.
Also, we will write the tuple $(0, \ldots, 0)$ as $0^n$.

Let a multilinear polynomial $P$ compatible with $\underline{\mathcal{X}}$
be given. Then, $P(\underline{\mathcal{X}})$ is what one expects:
the random variable obtained by evaluating the polynomial on the given input.
Analogously, if $\sigma$ is a tuple as above we write $\mathcal{X}_\sigma$ for
the random variable corresponding to the evaluation of the monomial $x_{\sigma}$.

Let $\underline{\mathcal{X}}$ be an ensemble sequence and $\sigma$, $\tau$
two tuples whose monomials $x_{\sigma}$, $x_{\tau}$ are compatible with

\begin{align}\label{eq:68a}
\EE[{\mathcal{X}}_{\sigma}{\mathcal{X}}_\tau]
= \begin{cases}
1 & \text{if $\sigma = \tau$}\\
0 & \text{otherwise}
\end{cases}
\end{align}

\begin{align}\label{eq:69a}
\EE[{\mathcal{X}}_{\sigma}]
= \begin{cases}
1 & \text{if $\sigma = 0^n$}\\
0 & \text{otherwise.}
\end{cases}
\end{align}

By independence of the coordinates we have
$\EE[{\mathcal{X}}_{\sigma}{\mathcal{X}}_\tau] =
\prod_{i=1}^n \EE [\mathcal{X}_{i,\sigma_i} \cdot \mathcal{X}_{i, \tau_i}]$
and now we can use the orthonomality of each ensemble $\mathcal{X}_i$.
For the second part, we apply the first on $\tau=0^n$.

Given a multilinear polynomial
$P(\underline{x}) = \sum_{\sigma}\alpha(\sigma)x_{\sigma}$
we define its following properties:
(P)     :=
max_σ: α_σ0 |σ|      if $P$ is non-zero

-∞    if $P$ is the zero polynomial

[P]     :=     α(0^n)

[P^2]     :=     ∑_σ α(σ)^2

[P]     :=     [P^2] - ^2[P]

_i(P)     :=     ∑_σ: σ_i 0 α(σ)^2

(P)     :=     ∑_i=1^n _i(P)

The next lemma states that the formal expressions defined above
are consistent with the corresponding probabilistic interpretations
for every ensemble sequence.

For an ensemble sequence $\underline{\mathcal{X}}$
and a multilinear polynomial $P$ compatible with it we have
[P]     =     [P(𝒳)]

[P^2]     =     [(P(𝒳))^2]

[P]     =     [P(𝒳)]    .

Furthermore, if all random variables in $\underline{\mathcal{X}}$
are discrete, then

\begin{align}
\Inf_i(P)  =  \EE \left[ \Var\left[ P(\underline{\mathcal{X}})  \mid
\mathcal{X}_1, \ldots, \mathcal{X}_{i-1},
\mathcal{X}_{i+1}, \ldots, \mathcal{X}_n \right] \right] \; .
\label{eq:35a}
\end{align}

Linearity of expectation
and (<ref>) yield
$\EE[P(\underline{\mathcal{X}})] =
\sum_{\sigma} \alpha(\sigma) \EE[\mathcal{X}_{\sigma}] = \alpha(0^n)$, which
is (<ref>).
Next, (<ref>) gives
$\EE[P^2(\underline{\mathcal{X}})] =
\sum_{\sigma,\tau} \alpha(\sigma)\alpha(\tau) \mathcal{X}_\sigma\mathcal{X}_\tau
= \sum_{\sigma} \alpha(\sigma)^2$,
i.e. (<ref>), and hence
(<ref>) by the definition of the variance.

As for (<ref>), fix an assignment
$\underline{x}_{\setminus i} = (x_1, \ldots, x_{i-1}, x_{i+1}, \ldots, x_n)$
to the ensemble sequence
$\underline{\mathcal{X}}_{\setminus i} =
(\mathcal{X}_1, \ldots, \mathcal{X}_{i-1}, \mathcal{X}_{i+1}, \ldots,
\mathcal{X}_n)$.[
Note that each entry in this tuple is itself a tuple:
$x_{i} = (x_{i,0} = 1, x_{i,1}, \ldots, x_{i,p})$,
where $p$ is the size of the ensemble.
We suppose that this tuple has a non-zero probability of occurence.
Since $\mathcal{X}_i$ is an orthornormal ensemble,
[P(𝒳) |𝒳_∖i = x_∖i ]
=     ∑_k = 1^p ( ∑_σ: σ_i = k
α(σ) ·∏_j i x_j, σ_j

From Lemma <ref>, for a fixed $k \in \{1, \ldots, p\}$,

\begin{align*}
\EE \left[ \left(
\sum_{\sigma: \sigma_i = k} \alpha(\sigma) \cdot \prod_{j \ne i}
\mathcal{X}_{j,\sigma_j}
\right)^2 \right] = \sum_{\sigma: \sigma_i = k} \alpha(\sigma)^2 \; .
\end{align*}

Together this gives

\begin{align*}
\EE\left[ \Var\left[ P(\underline{\mathcal{X}}) \mid
\underline{\mathcal{X}}_{\setminus i} \right] \right]
= \sum_{\sigma: \sigma_i \ne 0} \alpha(\sigma)^2 \; ,
\end{align*}

as claimed.

For a multilinear polynomial $P(\underline{x}) =
\sum_{\sigma} \alpha(\sigma)x_\sigma$ and
$S \subseteq [n]$ we let $P_S$ be $P$
restricted to tuples $\sigma$ with $\supp(\sigma) = S$,
i.e., $P_S := \sum_{\sigma:\supp(\sigma)=S} \alpha(\sigma)x_\sigma$.

Then, let $P^{>d} := \sum_{S: |S| > d} P_S$ be $P$
restricted to tuples with the degree greater than $d$.
We also define $P^{=d}$, $P^{\le d}$ etc. in the analogous way.

Let $P$ and $Q$ be multilinear polynomials compatible with an ensemble
sequence $\underline{\mathcal{X}}$. Then,

\begin{align*}
\EE\left[ P(\underline{\mathcal{X}}) Q(\underline{\mathcal{X}}) \right]
= \sum_{S \subseteq [n]} \EE\left[ P_S(\underline{\mathcal{X}})
Q_S(\underline{\mathcal{X}}) \right] \; .
\end{align*}

It is enough to show that for $S \ne T$

\begin{align*}
\EE\left[ P_S(\underline{\mathcal{X}})
Q_T(\underline{\mathcal{X}}) \right] = 0 \;.
\end{align*}

Let $P(\underline{\mathcal{X}}) =
\sum_\sigma \alpha(\sigma) \cdot \mathcal{X}_\sigma$
and $Q(\underline{\mathcal{X}}) = \sum_\sigma \beta(\sigma) \cdot
\mathcal{X}_\sigma$.
Assume w.l.o.g. that there exists $i^* \in S\setminus T$.
[ P_S(𝒳) Q_T(𝒳) ] =

= ∑_σ: (σ) = S
σ': (σ') = T
α(σ) β(σ') [ 𝒳_i^*, σ_i^* ]
[ ∏_i i^* 𝒳_i,σ_i 𝒳_i,σ'_i
] = 0   .

Let $P$ be a multilinear polynomial.
Then, $\EE[P^2] \allowbreak = \allowbreak \sum_{S \subseteq [n]}
\allowbreak \EE[P_S^2]$.

Taking any ensemble sequence $\underline{\mathcal{X}}$ compatible with $P$,

\begin{align*}
\EE[P^2] = \EE[P(\underline{\mathcal{X}})^2] = \sum_{S\subseteq[n]}
\EE[P_S(\underline{\mathcal{X}})^2] = \sum_{S\subseteq [n]} \EE[P_S^2] \; .
& \qedhere
\end{align*}

Let $P$ be a multilinear polynomial. Then,
$\Var[P] = \sum_{S \subseteq[n]} \Var[P_S]$.

Observing that $\Var[P_\emptyset] = 0$, $\EE[P_\emptyset^2] = \alpha(0^n)^2$
and $\Var[P_S] = \EE[P_S^2]$ for $S \ne \emptyset$, by Corollary

\begin{align*}
\Var[P] = \EE[P^2] - \alpha(0^n)^2 = \sum_{S\subseteq[n], S \ne \emptyset}
\EE[P_S^2] = \sum_{S\subseteq[n]} \Var[P_S] \; . & \qedhere
\end{align*}

Let $P$ be a multilinear polynomial with $\deg(P) \le d$. Then,

\begin{align*}
\Inf(P) \le d \cdot \Var[P] \; .
\end{align*}

\begin{align*}
\Inf(P) &= \sum_{\sigma} |\sigma| \cdot \alpha(\sigma)^2
\le d \cdot \sum_{\sigma \ne 0^n} \alpha(\sigma)^2 = d \cdot \Var[P] \; .
\qedhere
\end{align*}

Let $\rho \in \mathbb{R}$. We define the operator $T_\rho$ as follows:
let $P(\underline{x}) = \sum_{\sigma} \alpha(\sigma) x_\sigma$ be a multilinear
polynomial. Then,

\begin{align*}
(T_\rho P)(\underline{x}) :=
\sum_{\sigma} \rho^{|\sigma|} \alpha(\sigma) x_\sigma \; .
\end{align*}

We will mostly use the operator $T_\rho$ with $\rho \in [0, 1]$.

We call an orthonormal ensemble $\mathcal{G}_\star$ of size $p$
Gaussian if random variables
$\mathcal{G}_{\star,1}, \ldots, \mathcal{G}_{\star, p}$
are independent $\mathcal{N}(0, 1)$ Gaussians.

We say that an ensemble sequence
$\underline{\mathcal{G}} = (\mathcal{G}_1, \ldots, \mathcal{G}_n)$
is Gaussian if for each $i \in [n]$ the ensemble $\mathcal{G}_i$
is Gaussian.

We remark than as in all ensemble sequences, in a Gaussian ensemble sequence
we have $\mathcal{G}_{i,0} \equiv 1$ for all $i$.

For tuples of multilinear polynomials $\overline{P} = (P^{(1)}, \ldots, \allowbreak P^{(\ell)})$
such that each polynomial $P^{(j)}$ is
compatible with an ensemble sequence $\underline{\mathcal{X}}$ we write
$\overline{P}(\underline{\mathcal{X}})$ for the tuple
$(P^{(1)}(\underline{\mathcal{X}}), \ldots, P^{(\ell)}(\underline{\mathcal{X}}))$.

Similarly, given multilinear polynomials
$\overline{P} = (P^{(1)}, \ldots, P^{(\ell)})$ and a collection of ensemble
$\overline{\underline{\mathcal{X}}} = (\underline{\mathcal{X}}^{(1)}, \ldots
\underline{\mathcal{X}}^{(\ell)})$ such that
$P^{(j)}$ is compatible with $\underline{\mathcal{X}}^{(j)}$ we write
$\overline{P}(\overline{\underline{\mathcal{X}}})$ for
$(P^{(1)}(\underline{\mathcal{X}}^{(1)}), \ldots,

§.§ Preliminaries — ensemble collections

In this section we recall the setting of Theorem <ref>
and introduce some other concepts we will need throughout the proof.

From now on we will always implicitly assume that all multi-step distributions
$\cP$ have equal marginals (denoted as $\pi$).
This assumption is not necessary, but sufficient for our main purpose,
while making the notation easier.

Let $X$ be a random variable distributed according to a
single-step, single-coordinate distribution $(\Omega, \pi)$.
We say that an orthonormal ensemble $\mathcal{X}_\star$ is
constructed from $X$ if the elements
of $\mathcal{X}_\star$ form an orthonormal basis of $L^2(X)$.

Similarly, let $\underline{X}$ be a random vector distributed
according to $(\underline{\Omega}, \underline{\pi})$.
We say that an ensemble sequence $\underline{\mathcal{X}} =
(\mathcal{X}_1, \ldots, \mathcal{X}_n)$ is constructed
from $\underline{X}$ if for each $i \in [n]$
the ensemble $\mathcal{X}_i$ is constructed from $X_i$.

The definition of ensemble sequences requires that $\mathcal{X}_{i,0}
\equiv 1$ for every $i$; of course we can find a basis
of $L^2({X}_i)$ which satisfies this requirement, so that
ensemble sequences constructed from $\underline{X}$ indeed exist.

Let $\underline{\mathcal{X}}$ be an ensemble sequence constructed
from a random vector
${\underline{X}}$ distributed according to
$({\underline{\Omega}}, \underline{\pi})$.
Assume that the size of each ensemble $\mathcal{X}_i$ is $p$.
Then the set of monomials

\begin{align*}
\underline{\mathcal{B}} :=
\left\{ \mathcal{X}_\sigma \mid \sigma = (\sigma_1, \ldots, \sigma_n),
\sigma_i \in \{0, \ldots, p\} \right\}
\end{align*}

is an orthonormal basis of $L^2({\underline{X}})$.

Observe that the dimension of $L^2({X}_i)$ is $p+1$, (note that
it is the support size of the single-coordinate distribution
$(\Omega, \pi)$).
Hence, the dimension of $L^2(\underline{X})$ is $(p+1)^n$,
which equals the size of $\underline{\mathcal{B}}$.
Therefore, it is enough to check that $\underline{\mathcal{B}}$ is
orthonormal, which is done in Lemma <ref>.

Let $\underline{\mathcal{X}}$ be an ensemble sequence constructed from a
random vector $\underline{X}$ distributed according to
$(\underline{\Omega}, \underline{\pi})$.

For a function $f: \underline{\Omega} \to \mathbb{R}$
and a multilinear polynomial $P$ compatible with
we say that $f(\underline{X})$
is equivalent to $P$ if it always holds that

\begin{align*}
f(\underline{X}) = P(\underline{\mathcal{X}}) \; .
\end{align*}

Recall the operator $T_\rho$ from Definition <ref>.
We show that it has a natural counterpart in
$L^2({\underline{\Omega}}, \underline{\pi})$.

Let $\rho \in [0, 1]$ and let
$({\underline{\Omega}}, \underline{\pi})$
be a single-step probability space (with
$({\Omega}, \pi)$ a corresponding
single-coordinate probability space).

We define a linear operator
$T_\rho:  L^2({\underline{\Omega}}, \underline{\pi}) \to
L^2({\underline{\Omega}}, \underline{\pi})$ as

\begin{align*}
T_\rho f({\underline{x}}) := \EE \left[ f\left(
{\underline{Y}}^{\rho, {\underline{x}}} \right) \right] \; ,
\end{align*}

where ${\underline{Y}}^{\rho, {\underline{x}}} =
({Y}^{\rho, {\underline{x}}}_1, \ldots,
{Y}^{\rho, {\underline{x}}}_n)$
is a random vector with independent coordinates
distributed such that ${Y}^{\rho, {\underline{x}}}_i =
with probability $\rho$
and ${Y}^{\rho, {\underline{x}}}_i$ is
distributed according to $({\Omega}, \pi)$ with probability

The next lemma states that taking operator $T_\rho$ preserves
the equivalence of functions and polynomials:

Let $\underline{\mathcal{X}}$ be an ensemble sequence constructed from
a random vector ${\underline{X}}$ distributed according
to $({\underline{\Omega}}, \underline{\pi})$.

Let $\rho \in [0, 1]$, $f: {\underline{\Omega}} \to \mathbb{R}$
and $P$ be a multilinear polynomial equivalent to $f$.
Then, $T_\rho P$ and $T_\rho f$ are equivalent, i.e.,

\begin{align*}
T_\rho f ({\underline{X}})
= T_\rho P (\underline{\mathcal{X}}) \; .
\end{align*}

Fix an input ${\underline{x}} \in {\underline{\Omega}}$
in the support of $\underline{\mathcal{P}}$.
$\underline{\mathcal{Y}}^{\rho, {\underline{x}}} =
(\mathcal{Y}_1^{\rho, {\underline{x}}}, \ldots,
\mathcal{Y}_n^{\rho, {\underline{x}}})$
be the random sequence where for each coordinate $i \in [n]$, independently

\begin{align*}
\mathcal{Y}_i^{\rho, {\underline{x}}} := \begin{cases}
\mathcal{X}_i({x_i}) & \text{with probability $\rho$,}\\
\text{a random ensemble distributed as $\mathcal{X}_i$}
& \text{with probability $1-\rho$.}
\end{cases}
\end{align*}

Note that $\underline{\mathcal{Y}}^{\rho, {\underline{x}}}$ is not an
ensemble sequence, but this will not cause problems.

Writing $P(\underline{x}) =
\sum_\sigma \alpha(\sigma) \cdot x_\sigma$ we can calculate
T_ρf (x)     =     [
f(Y^ρ, x) ]
= [ P(𝒴^ρ, x)]
= ∑_σα(σ)
[ 𝒴_σ^ρ, x ]

=     ∑_σρ^|σ| α(σ) ·𝒳_σ(x)
= T_ρP (x)   .

Since ${\underline{x}}$ was arbitrary, the claim is proved.

Recall Definition <ref>.
In the proof we will construct a tuple of ensemble sequences
$\overline{\underline{\mathcal{X}}} =
(\underline{\mathcal{X}}^{(1)}, \ldots, \underline{\mathcal{X}}^{(\ell)})$
from a random vector $\overline{\underline{X}}$
and consider relations between those sequences
and compatible Gaussian ensemble sequences.
To this end, we need to introduce the Gaussian equivalent of
marginal ensemble sequences $\underline{\mathcal{X}}^{(j)}$.

Let $\mathcal{G_\star} = (\mathcal{G}_{\star,0}, \ldots, \mathcal{G}_{\star, p})$ be a Gaussian
orthonormal ensemble of size $p$. We define
an inner product space $V(\mathcal{G})$ as

\begin{align*}
V({\mathcal{G}}) := \left\{
\sum_{k=0}^p \alpha_k \cdot \mathcal{G}_k \mid
\alpha_0, \ldots, \alpha_k \in \mathbb{R}
\right\}
\end{align*}

with the inner product of $A, B \in V(\mathcal{G})$ given by
$\langle A, B \rangle := \EE[ A \cdot B ]$.

Similarly, given a Gaussian ensemble sequence
$\underline{\mathcal{G}}$ such that each of its ensembles is of size $p$
we let

\begin{align*}
V(\underline{\mathcal{G}}) := \left\{
\sum_{\sigma} \alpha(\sigma) \cdot \mathcal{G}_\sigma
\mid \sigma = (\sigma_1, \ldots, \sigma_n) \in \{0, \ldots, p\},
\alpha(\sigma) \in \mathbb{R}
\right\} \; ,
\end{align*}

with the inner product $\langle A, B \rangle := \EE[ A \cdot B ]$.

Let a random tuple $\overline{X} =
(X^{(1)},\ldots,X^{(\ell)})$ be distributed according
to a single-coordinate distribution
$(\overline{\Omega}, \mathcal{P})$.
Let $\overline{\mathcal{X}}_\star =
(\mathcal{X}_\star^{(1)},\ldots,\mathcal{X}_\star^{(\ell)})$ be such
that $\mathcal{X}_\star^{(j)}$ is an orthonormal ensemble constructed
from $X^{(j)}$.

Then, there exist Gaussian orthonormal ensembles
$\overline{\mathcal{G}}_\star =
compatible with $\overline{\mathcal{X}}_\star$ such
that for all $j_1,j_2 \in [\ell]$, and all $k_1,k_2 \geq 0$ we have

\begin{align}\label{eq:70a}
\Cov\left[ \mathcal{X}_{\star, k_1}^{(j_1)}, \mathcal{X}_{\star, k_2}^{(j_2)}
\right]
= \Cov\left[
\mathcal{G}_{\star, k_1}^{(j_1)}, \mathcal{G}_{\star, k_2}^{(j_2)} \right] \; .
\end{align}

$(\overline{\Omega}, \mathcal{P})$
as a single-step probability space, and let $\overline{X}$
be the corresponding random variable.
Let now $\mathcal{Z}_\star$ be an orthonormal ensemble constructed
from $\overline{X}$. Recall that this means that
the elements of $\mathcal{Z}_\star$ form an orthonormal basis
of $L^2(\overline{X})$.

Let $\mathcal{H}_\star$ be a Gaussian ensemble sequence compatible
with $\mathcal{Z}_\star$.
Define the map
$\Psi: L^2(\overline{X}) \to V(\mathcal{H}_\star)$ by linearly extending
$\Psi(\mathcal{Z}_{\star,k}) := \mathcal{H}_{\star,k}$.
In this way $\Psi$ becomes an isomorphism between $L^2(\overline{X})$
and $V(\mathcal{H}_\star)$ (and as such it preserves inner products).

Since $L^2(X^{(j)})$ is a subspace of $L^2(\overline{X})$, we can define
$\mathcal{G}_{\star,k}^{(j)}$ as $\mathcal{G}_{\star,k}^{(j)} :=
\Psi(\mathcal{X}_{\star,k}^{(j)})$.
Since $\Psi$ preserves inner products we get (<ref>).

We still need to argue that for each $j \in [\ell]$ the
orthonormal ensemble $\mathcal{G}_\star^{(j)}$ is Gaussian.
The fact that $\mathcal{G}_\star^{(j)}$ is an ensemble sequence
follows from (<ref>) for $j_1 = j_2 = j$ (note that $\Psi(1) = 1$).

The variables $\mathcal{G}_{\star,k}^{(j)}$ are clearly jointly Gaussian,
since they can be written as sums of independent Gaussians.
By (<ref>), their covariance matrix is identity.
This finishes the proof, since joint Gaussians with
the identity covariance matrix must be independent.

Since the proof of Lemma <ref> is somewhat abstract,
we illustrate the construction of $\overline{\mathcal{G}}_\star$
with an example.

Consider $(X^{(1)}, X^{(2)})$ distributed according to $\cP$
over $\Omega = \{0,1\}$ with
$\cP(0, 0) = \cP(1, 1) = 1/8$ and $\cP(0, 1) = \cP(1, 0) = 3/8$. We can take
the following for the ensemble $\mathcal{Z}_\star$:

$(X^{(1)}, X^{(2)}) :=$     (0,0)     (0, 1)     (1, 0)     (1, 1)

$\mathcal{Z}_{\star, 0}$     1     1     1     1

$\mathcal{Z}_{\star, 1}$     2     0     0     -2

$\mathcal{Z}_{\star, 2}$     0     $2\sqrt{3}/3$     $-2\sqrt{3}/3$     0

$\mathcal{Z}_{\star, 3}$     $\sqrt{3}$     $-\sqrt{3}/3$     $-\sqrt{3}/3$

For the marginal ensemble $\mathcal{X}_\star^{(1)}$ we can take

$X^{(1)} :=$     0     1

$\mathcal{X}_{\star, 0}^{(1)}$     1     1

$\mathcal{X}_{\star, 1}^{(1)}$     $1$     $-1$

Now one can check that $\mathcal{X}^{(1)}_{\star, 0} = \mathcal{Z}_{\star, 0}$
$\mathcal{X}^{(1)}_{\star, 1} = 1/2 \cdot \mathcal{Z}_{\star, 1}
+\sqrt{3}/2 \cdot \mathcal{Z}_{\star,2}$.
Defining the ensemble $\mathcal{X}_{\star}^{(2)}$ in the same way we get
$\mathcal{X}^{(2)}_{\star,0} = \mathcal{Z}_{\star,0}$ and
$\mathcal{X}^{(2)}_{\star,1} = 1/2 \cdot \mathcal{Z}_{\star, 1} -\sqrt{3}/2 \cdot
\mathcal{Z}_{\star, 2}$.

Let $\mathcal{H}_{\star} =
(\mathcal{H}_{\star, 0}\equiv 1, \mathcal{H}_{\star, 1}, \mathcal{H}_{\star, 2},
\mathcal{H}_{\star, 3})$ be a Gaussian ensemble sequence compatible with
$\mathcal{Z}$. One easily checks that our construction gives

\begin{align*}
\mathcal{G}_{\star, 0}^{(1)} = \mathcal{G}_{\star, 0}^{(2)} & =  \mathcal{H}_{\star, 0}
\\
\mathcal{G}^{(1)}_{\star, 1} & =
1/2 \cdot \mathcal{H}_{\star, 1} +\sqrt{3}/2 \cdot \mathcal{H}_{\star,2}
\\
\mathcal{G}^{(2)}_{\star,1} & =
1/2 \cdot \mathcal{H}_{\star, 1} -\sqrt{3}/2 \cdot \mathcal{H}_{\star, 2} \; .
\end{align*}

Since the covariances between independent coordinates are always zero,
Lemma <ref> applied to each coordinate separately gives:

Let a random vector $\overline{\underline{X}} =
(\underline{X}^{(1)},\ldots,\underline{X}^{(\ell)})$ be distributed according
to a distribution
$(\underline{\overline{\Omega}}, \underline{\mathcal{P}})$.
Let $\underline{\overline{\mathcal{X}}} =
(\underline{\mathcal{X}}^{(1)},\ldots,\underline{\mathcal{X}}^{(\ell)})$ be such
that $\underline{\mathcal{X}}^{(j)}$ is an ensemble sequence constructed
from $\underline{X}^{(j)}$.

Then, there exist Gaussian ensemble sequences
$\underline{\overline{\mathcal{G}}} =
compatible with $\overline{\underline{\mathcal{X}}}$ such
that for all $i_1, i_2 \in [n]$, $j_1,j_2 \in [\ell]$, and all $k_1,k_2 \geq 0$ we have

\begin{align}\label{eq:70aa}
\Cov\left[ \mathcal{X}_{i_1, k_1}^{(j_1)}, \mathcal{X}_{i_2, k_2}^{(j_2)}
\right]
= \Cov\left[
\mathcal{G}_{i_1, k_1}^{(j_1)}, \mathcal{G}_{i_2, k_2}^{(j_2)} \right] \; .
\end{align}

An ensemble collection for
$(\overline{\underline{\Omega}}, \underline{\mathcal{P}})$
is a tuple
\begin{align*}
\left(\overline{\underline{X}},
\underline{\overline{\mathcal{X}}} = (\underline{\mathcal{X}}^{(1)}, \ldots,
\underline{\mathcal{X}}^{(\ell)}),
\underline{\overline{\mathcal{G}}} = (\underline{\mathcal{G}}^{(1)}, \ldots,
\underline{\mathcal{G}}^{(\ell)})\right)
\end{align*}

* $\overline{\underline{X}}$ is a random vector
distributed according to $(\overline{\underline{\Omega}},
\underline{\mathcal{P}})$,

* $\underline{\mathcal{X}}^{(1)}, \ldots, \underline{\mathcal{X}}^{(\ell)}$
are ensemble sequences constructed from
$\underline{X}^{(1)}, \ldots, \underline{X}^{(\ell)}$, respectively,

* and
$\underline{\mathcal{G}}^{(1)}, \ldots, \underline{\mathcal{G}}^{(\ell)}$
are obtained from Corollary <ref>.

§.§ Hypercontractivity

In this section we develop a version of hypercontractivity for products
of multilinear polynomials. Our goal is to prove Lemma

Recall the operator $T_\rho$ from Definition <ref>.

Let $\underline{\mathcal{X}}$ be an ensemble sequence
and let $1 \le p \le q < \infty$ and $\rho \in [0, 1]$.
We say that the sequence $\underline{\mathcal{X}}$ is
$(p, q, \rho)$-hypercontractive if for
every multilinear polynomial $P$ compatible with $\underline{\mathcal{X}}$
we have

\begin{align*}
\EE\left[ \left| T_\rho P (\underline{\mathcal{X}}) \right|^q \right]^{1/q}
\le
\EE\left[ \left| P (\underline{\mathcal{X}}) \right|^p \right]^{1/p}
\end{align*}

Let $\mathcal{X}$ be an orthonormal ensemble
and let $1 \le p \le q < \infty$ and $\rho \in [0, 1]$.
We say that the ensemble $\mathcal{X}$ is
$(p, q, \rho)$-hypercontractive if
the one-element ensemble sequence
$\underline{\mathcal{X}} := (\mathcal{X})$ is
$(p, q, \rho)$-hypercontractive.

We start with stating without proofs the hypercontractivity of
orthonormal ensembles that we use in
the invariance principle:

Let $\mathcal{G}$ be a Gaussian orthonormal
ensemble and $\rho \in \allowbreak
[0, \sqrt{2}/2]$. Then,
$\mathcal{G}$ is $(2, 3, \rho)$-hypercontractive.

Let $\mathcal{X}$ be an orthonormal ensemble constructed from a random variable
$X$ distributed according to a
(single-coordinate, single-step) probability space
$(\Omega, \pi)$ with
$\min_{x \in \Omega} \pi(x) \ge \alpha \ge 0$.

Then, $\mathcal{X}$ is $(2, 3, \alpha^{1/6}/2)$-hypercontractive.

Subsequently, we observe that
an ensemble sequence constructed from
hypercontractive ensembles is itself hypercontractive:

Let $1 \le p \le q < \infty$, $\rho \in [0, 1]$ and let
$\underline{\mathcal{X}} := (\mathcal{X}_1, \ldots, \mathcal{X}_n)$
be an ensemble sequence such that
for every $i \in [n]$, the ensemble $\mathcal{X}_i$
is $(p, q, \rho)$-hypercontractive. Then,
the sequence $\underline{\mathcal{X}}$ is also
$(p, q, \rho)$-hypercontractive.

Yet again, we omit the proof of Theorem <ref>.
We remark that it is well-known as the tensorization argument.
The argument can be found, e.g., in the proof of Proposition 3.11
in [18].

Let $\underline{X}$ be a random vector distributed
according to a (single-step, tensorized) probability space
$(\underline{\Omega}, \underline{\pi})$.
We say that an ensemble sequence
$\underline{\mathcal{X}} = (\mathcal{X}_1, \ldots, \mathcal{X}_n)$
is $\underline{X}$-Gaussian-mixed if
for each $i \in[n]$:

* Either $\mathcal{X}_i$ is constructed
from the random variable $X_i$,

* or $\mathcal{X}_i$ is a Gaussian ensemble.

Theorems <ref>,
<ref> and
<ref> immediately imply:

Let $\underline{X}$ be a random vector distributed according to
a probability space
$(\underline{\Omega}, \underline{\pi})$ with
$\min_{x \in \Omega} \pi(x) \ge \alpha \ge 0$
and let $\underline{\mathcal{X}}$ be an
ensemble sequence.

Then, $\underline{\mathcal{X}}$ is $(2, 3, \alpha^{1/6}/2)$-hypercontractive.

Let $\underline{X}$ be a random vector distributed according to a
probability space $(\underline{\Omega}, \underline{\pi})$
with $\min_{x \in \Omega} \pi(x) \ge \alpha > 0$
and let $\underline{\mathcal{X}}$ be an $\underline{X}$-Gaussian-mixed
ensemble sequence.
Let $P$ be a multilinear
polynomial compatible with $\underline{\mathcal{X}}$ of degree at most $d$.Then,

\begin{align*}
\EE\left[ \left| P(\underline{\mathcal{X}})  \right|^3  \right]^{1/3}
\le \left(\frac{2}{\alpha^{1/6}}\right)^d
\sqrt{\EE\left[ P^2 \right]} \; .
\end{align*}

Let $\rho := \alpha^{1/6}/2$ and write
$P(\underline{\mathcal{X}}) = \sum_{\sigma} \beta(\sigma) \mathcal{X}_{\sigma}$.
By Corollary <ref>, definitions of $T_\rho$ and
$E[P^2]$, and the degree bound on $P$,
[ | P(𝒳) |^3 ]^1/3
= [ | T_ρT_1/ρ P(𝒳)
|^3 ]^1/3
≤√( [ (T_1/ρ P)^2 ] )

= √( ∑_σ ρ^-2|σ| β(σ)^2)
≤√( ∑_σ ρ^-2d β(σ)^2)
= ρ^-d √( [P^2] )   .

Let $\overline{\underline{X}}$ be a random vector distributed according to
a (multi-step)  probability space with equal marginals
$(\overline{\underline{\Omega}}, \underline{\mathcal{P}})$
with $\min_{x \in \Omega} \pi(x) \ge \alpha > 0$.

$\underline{\mathcal{S}}^{(1)}, \ldots, \underline{\mathcal{S}}^{(\ell)}$
be ensemble sequences such that $\underline{\mathcal{S}}^{(j)}$ is
Let $P^{(1)}, \ldots, P^{(\ell)}$ be multilinear polynomials
such that $P^{(j)}$ is
compatible with $\underline{\mathcal{S}}^{(j)}$
and also $\deg(P^{(j)}) \le d$.

Then, for every triple $j_1, j_2, j_3 \in [\ell]$:

\begin{align*}
\EE \left[ \left| \prod_{k=1}^3 P^{(j_k)}(\underline{\mathcal{S}}^{(j_k)})
\right| \right]
\le \left( \frac{8}{\sqrt{\alpha}} \right)^d \cdot
\sqrt{ \prod_{k=1}^3 \EE \left[ (P^{(j_k)})^2\right]}
\; .
\end{align*}

Let $\rho := \alpha^{1/6}/2$. By Hölder's inequality
and  Theorem
[ | ∏_k=1^3 P^(j_k)(𝒮^(j_k))
| ]
∏_k=1^3 [ | P^(j_k)(𝒮^(j_k))
|^3 ]^1/3

≤    ρ^-3d ·√( ∏_k=1^3 [ (P^(j_k))^2] )   .

§.§ Invariance principle

In this section we prove a basic version of invariance principle for multiple

We say that a function is $B$-smooth if all of its third-order partial
derivatives are uniformly bounded by $B$:

For $B \ge 0$ we say that a function $\Psi: \mathbb{R}^\ell \to \mathbb{R}$ is
$B$-smooth if $\Psi \in \mathcal{C}^3$ and
for every $j_1, j_2, j_3 \in [\ell]$ and every
$\overline{x} = (x^{(1)}, \ldots, x^{(\ell)}) \in \mathbb{R}^\ell$ we have

\begin{align*}
\left| \frac{\partial^3}
{\partial x^{(j_1)} \partial x^{(j_2)} \partial x^{(j_3)}}
\Psi(\overline{x}) \right| \le B \; .
\end{align*}

Let $(\overline{\underline{X}},
\overline{\underline{\mathcal{X}}},
\overline{\underline{\mathcal{G}}})$ be an ensemble collection
for a probability space
$(\overline{\underline{\Omega}}, \underline{\mathcal{P}})$
with $\min_{x \in \Omega} \pi(x) \ge \alpha > 0$.

Let $\overline{P} = (P^{(1)}, \ldots, P^{(\ell)})$ be
such that $P^{(j)}$ is a multilinear polynomial compatible with
the ensemble sequence $\underline{\mathcal{X}}^{(j)}$.

Let $d \in \mathbb{N}$ and $\tau \in [0, 1]$ and assume that
$\deg(P^{(j)}) \le d$ and $\Var[P^{(j)}] \le 1$ for each $j \in [\ell]$,
and that $\sum_{j=1}^\ell \Inf_i(P^{(j)}) \le \tau$ for each $i \in [n]$.

Finally, let $\Psi: \mathbb{R}^\ell \to \mathbb{R}$
be a $B$-smooth function. Then,

\begin{align*}
\left| \EE \left[
\Psi(\overline{P}(\overline{\underline{\mathcal{X}}}))
- \Psi(\overline{P}(\overline{\underline{\mathcal{G}}}))
\right] \right|
\le
\frac{\ell^{5/2}d B}{3} \left( \frac{8}{\sqrt{\alpha}} \right)^d
\sqrt{\tau} \; .
\end{align*}

A typical setting of parameters for which Theorem <ref>
might be successfully applied is constant $\ell$, $d$, $B$, and $\alpha$,
while $\tau = o(1)$ (as $n \to \infty$).

The rest of this section is concerned with proving Theorem

For $i \in \{0, \ldots, n\}$ and $j \in [\ell]$ let the ensemble sequence
$\underline{\mathcal{U}}_{(i)}^{(j)}$ be
defined as $\underline{\mathcal{U}}_{(i)}^{(j)} :=
(\mathcal{G}_1^{(j)}, \ldots, \mathcal{G}_i^{(j)},
\mathcal{X}_{i+1}^{(j)}, \ldots, \mathcal{X}_n^{(j)})$.

\begin{align*}
\left| \EE \left[
\Psi(\overline{P}(\overline{\underline{\mathcal{X}}}))
- \Psi(\overline{P}(\overline{\underline{\mathcal{G}}}))
\right] \right|
\le
\sum_{i=1}^n \left| \EE \left[
\Psi(\overline{P}(\overline{\underline{\mathcal{U}}}_{(i-1)}))
- \Psi(\overline{P}(\overline{\underline{\mathcal{U}}}_{(i)}))
\right] \right| \; .
\end{align*}

By the triangle inequality.

Due to Claim
<ref>, we will estimate

\begin{align*}
\left| \EE \left[
\Psi(\overline{P}(\overline{\underline{\mathcal{U}}}_{(i-1)}))
- \Psi(\overline{P}(\overline{\underline{\mathcal{U}}}_{(i)}))
\right] \right|
\end{align*}

for every $i \in [n]$. Fix $i \in [n]$ and write
$\underline{\mathcal{T}}^{(j)} := \underline{\mathcal{U}}_{(i-1)}^{(j)}$ and
$\underline{\mathcal{U}}^{(j)} := \underline{\mathcal{U}}_{(i)}^{(j)}$ for
For $j \in [\ell]$ we can write

\begin{align}
\label{eq:62a}
P^{(j)}(\underline{\mathcal{T}}^{(j)}) =
A^{(j)} + \sum_{k>0} \mathcal{X}_{i,k}^{(j)} \cdot B^{(j)}_k =
A^{(j)} + P_i^{(j)}(\underline{\mathcal{T}}^{(j)}) \; ,
\end{align}

where $A^{(j)}$ and $B^{(j)}_k$ do not depend on the coordinate $i$
and, if $P^{(j)}(\underline{\mathcal{T}}^{(j)}) =
\sum_\sigma \alpha(\sigma) \mathcal{T}_\sigma^{(j)}$,
then $P_i^{(j)}(\underline{\mathcal{T}}^{(j)}) = \sum_{\sigma: i \in \supp(\sigma)}
\alpha(\sigma) \mathcal{T}_\sigma^{(j)}$.
At the same time, since $A^{(j)}$ and $B_k^{(j)}$ do not depend on the
$i$-th coordinate,

\begin{align*}
P^{(j)}(\underline{\mathcal{U}}^{(j)}) =
A^{(j)} + \sum_{k>0} \mathcal{G}_{i,k}^{(j)} \cdot B^{(j)}_k =
A^{(j)} + P_i^{(j)}(\underline{\mathcal{U}}^{(j)})
\; .
\end{align*}

We note for later use that the construction gives us

\begin{align}\label{eq:36a}
\deg(P_i^{(j)}) &\le d\\
\EE\left[ \left( P_i^{(j)}\right)^2\right] &= \Inf_i\left(P^{(j)}\right)\;.
\label{eq:37a}
\end{align}

The rest of the proof proceeds as follows:
we calculate the multivariate second order Taylor expansion (i.e., with
the third-degree rest) of the expression, getting
- Ψ(P(𝒰)) =

Ψ(A^(1) + ∑_k>0 𝒳_i,k^(1) B_k^(1), …,
A^(ℓ) + ∑_k>0 𝒳_i,k^(ℓ) B_k^(ℓ))

-   Ψ(A^(1) + ∑_k>0
𝒢_i,k^(1) B_k^(1), …,
A^(ℓ) + ∑_k>0 𝒢_i,k^(ℓ) B_k^(ℓ))

around the point $\overline{A} := (A^{(1)}, \ldots, A^{(\ell)})$.
We will see that:

* All the terms up to the second degree cancel in expectation
due to the properties of ensemble sequences.

* The remainder, which is of the third degree,
can be bounded using that $\Psi$ is $B$-smooth,
properties of $P_{i}^{(j)}$, and
hypercontractivity, in particular
Lemma <ref>.

We proceed with a detailed description.
The first result we will need is multivariate Taylor's theorem
for $B$-smooth functions:

Let $\Psi: \mathbb{R}^\ell \to \mathbb{R}$ be a $B$-smooth function
and let
$\overline{x} = (x^{(1)}, \ldots, x^{(\ell)}),
\overline{\epsilon} = (\epsilon^{(1)}, \ldots, \epsilon^{(\ell)})
\in \mathbb{R}^\ell$.
Ψ( x^(1)+ϵ^(1), …, x^(ℓ)+ϵ^(ℓ) )

( Ψ(x) +
∑_j ∈[ℓ] ϵ^(j)
+ 1/2 ∑_j_1,j_2 ∈[ℓ] ϵ^(j_1) ϵ^(j_2)
∂^2/∂x^(j_1) ∂x^(j_2) Ψ(x)
) |

≤B/6 ∑_j_1, j_2, j_3 ∈[ℓ] |
ϵ^(j_1) ϵ^(j_2) ϵ^(j_3) |   .

We omit the proof of Theorem <ref>.

Fix $i \in [n]$ and write
$\underline{\mathcal{T}}^{(j)} := \underline{\mathcal{U}}^{(j)}_{(i-1)}$
and $\underline{\mathcal{U}}^{(j)} := \underline{\mathcal{U}}^{(j)}_{(i)}$.
[ Ψ(P(𝒯)) ]

= [
Ψ(A) + 1/2 ∑_j_1, j_2 ∈[ℓ] (
∑_k_1, k_2 > 0 𝒳_i,k_1^(j_1) 𝒳_i,k_2^(j_2)
B_k_1^(j_1) B_k_2^(j_2)
∂^2/∂A^(j_1) ∂A^(j_2) Ψ(A)
+ R_𝒯 ]
[ Ψ(P(𝒰)) ]

= [
Ψ(A) + 1/2 ∑_j_1, j_2 ∈[ℓ] (
∑_k_1, k_2 > 0 𝒢_i,k_1^(j_1) 𝒢_i,k_2^(j_2)
B_k_1^(j_1) B_k_2^(j_2)
∂^2/∂A^(j_1) ∂A^(j_2) Ψ(A)
+ R_𝒰 ]
where random variables $R_{\underline{\mathcal{T}}}$ and $R_{\underline{\mathcal{U}}}$
are such that
| R_𝒯 |
| R_𝒰 |
≤ℓ^3/2 B/6 (8/√(α))^d
( ∑_j=1^ℓ_i(P^(j)) )^3/2   .

We show only (<ref>) and the bound on $\EE[|R_{\underline{\mathcal{T}}}|]$,
the proofs for the ensemble sequence $\underline{\mathcal{U}}$ being

As a preliminary remark,
note that since all the random ensembles we are dealing with are hypercontractive,
and since $\Psi$ is $B$-smooth,
all the terms in the expressions above have finite expectations.

Keeping in mind both decompositions from (<ref>),
by Theorem <ref>
Ψ(A) +
∑_j ∈[ℓ] (
∑_k>0 𝒳_i,k^(j) B_k^(j)
∂/∂A^(j) Ψ(A)
) +

+   1/2 ∑_j_1, j_2 ∈[ℓ] (
∑_k_1,k_2>0 𝒳_i,k_1^(j_1) 𝒳_i,k_2^(j_2)
B_k_1^(j_1) B_k_2^(j_2)
∂^2/∂A^(j_1) ∂A^(j_2) Ψ(A)
+ R_𝒯   ,

[ | R_𝒯 | ] ≤B/6
∑_j_1, j_2, j_3 ∈[ℓ] [ |
∏_k=1^3 P_i^(j_k)(𝒯^(j_k))
| ]   .

Since $\EE[\mathcal{X}_{i,k}^{(j)}] = 0$, and all other terms
are independent of coordinate $i$, we have

\begin{align*}
\EE \left[ \sum_{j \in [\ell]}
\sum_{k>0} \mathcal{X}_{i,k}^{(j)} B_k^{(j)}
\frac{\partial}{\partial A^{(j)}} \Psi(\overline{A})
\right] = 0 \; ,
\end{align*}

which together with (<ref>) yields (<ref>).

As for the bound on $\EE[|R_{\underline{\mathcal{T}}}|]$, since
$T^{(j)}$ is $\underline{X}^{(j)}$-Gaussian-mixed ensemble sequence,
due to (<ref>), Lemma <ref>
(note that the degree is bounded due to (<ref>)), and (<ref>),
B/6 (8/√(α))^d
∑_j_1,j_2,j_3 ∈[ℓ] √(
∏_k=1^3 [(P_i^(j_k))^2])

B/6 (8/√(α))^d
∑_j_1,j_2,j_3 ∈[ℓ] √(
∏_k=1^3 _i(P^(j_k)))

ℓ^3/2 B/6 (8/√(α))^d
( ∑_j=1^ℓ_i(P^(j)) )^3/2   ,

where the last inequality uses
$\sum_{j_1,j_2,j_3} \nu(j_1,j_2,j_3) \leq\allowbreak
\sqrt{\ell^3} \sqrt{\sum \nu^2(j_1,j_2,j_3)}$
for the vector $\nu$ with entries
$\nu(j_1,j_2,j_3) = \sqrt{\prod_{k=1}^3 \Inf_i(P^{(j_k)})}$.

Fix $i \in [n]$ and write
$\underline{\mathcal{T}}^{(j)} := \underline{\mathcal{U}}^{(j)}_{(i-1)}$
and $\underline{\mathcal{U}}^{(j)} := \underline{\mathcal{U}}^{(j)}_{(i)}$.

\begin{align*}
\left| \EE\left[
\Psi(\overline{P}(\overline{\underline{\mathcal{T}}}))
- \Psi(\overline{P}(\overline{\underline{\mathcal{U}}}))