# Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems

Noam Lifshitz

###### Abstract.

The classical sharp threshold theorem of Friedgut and Kalai (1996) asserts
that any symmetric monotone function
$f\colon\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$ exhibits a sharp
threshold phenomenon. This means that the expectation of $f$ with respect to
the biased measure $\mu_{p}$ increases rapidly from 0 to 1 as $p$ increases.

In this paper we present ‘robust’ versions of the theorem, which assert that
it holds also if the function is ‘almost’ monotone, and admits a much weaker
notion of symmetry. Unlike the original proof of the theorem which relies on
hypercontractivity, our proof relies on a ‘regularity’ lemma (of the class of
Szemerédi’s regularity lemma and its generalizations) and on the ‘invariance
principle’ of Mossel, O’Donnell, and Oleszkiewicz which allows (under certain
conditions) replacing functions on the cube $\\{0,1\\}^{n}$ with functions on
Gaussian random variables.

The hypergraph removal lemma of Gowers (2007) and independently of Nagle,
Rödl, Schacht, and Skokan (2006) says that if a $k$-uniform hypergraph on $n$
vertices contains few copies of a fixed hypergraph $H$, then it can be made
$H$-free by removing few of its edges. While this settles the ‘hypergraph
removal problem’ in the case where $k$ and $H$ are fixed, the result is
meaningless when $k$ is large (e.g. $k>\log\log\log n$).

Using our robust version of the Friedgut–Kalai Theorem, we obtain a hypergraph
removal lemma that holds for $k$ up to linear in $n$ for a large class of
hypergraphs. These contain all the hypergraphs such that both their number of
edges and the sizes of the intersections of pairs of their edges are upper
bounded by some constant.

##  1\. Introduction

###  1.1. Problems on $\mathcal{H}$-free families

For any set $V$ we use $\binom{V}{k}$ to denote the family of all subsets of
$V$ of size $k$. Any $\mathcal{H}\subseteq\binom{V}{k}$ is called a _$k$
-uniform hypergraph _or a $k$_-uniform family_ on the _vertex set_ $V$, and
the elements of $\mathcal{H}$ are its _edges_. We write $\left[n\right]$ for
the set $\left\\{1,\ldots,n\right\\}.$

The celebrated Mantel’s Theorem [47] from 1907 says that the largest triangle
free graph $G\subseteq\binom{\left[n\right]}{2}$ is the balanced complete
bipartite graph. In 1941, Turán [62] generalized Mantel’s Theorem from
triangles to cliques. He raised the following problem known as the Turán
problem for hypergraphs.

######  Problem 1.1.

Given a hypergraph $\mathcal{H}\subseteq\binom{V}{k},$ determine the value
$\mathrm{ex}\left(n,\mathcal{H}\right)$ of the largest $\mathcal{H}$-free
family in $\binom{\left[n\right]}{k}.$

An $\mathcal{H}$-free family of size $\mathrm{ex}\left(n,\mathcal{H}\right)$
is called an _extremal $\mathcal{H}$-free family_. The Turán problem is one of
the most prominent problems in extremal combinatorics, and it includes many of
the well studied problems in this area. (See the excellent survey of Keevash
[41], and the more recent survey of Mubayi and Verstraëte [51].) One example,
is the classical Erdős-Ko-Rado Theorem (EKR Theorem) [21] from 1961, which
determines the largest size of a family
$\mathcal{F}\subseteq\binom{\left[n\right]}{k}$ such that each two of its
edges have nonempty intersection. It can be rephrased by saying that
$\mathrm{ex}\left(n,\mathcal{M}_{2}\right)=\binom{n-1}{k-1}$ for any $n\geq
2k$, where $\mathcal{M}_{2}$ is the $k$-uniform hypergraph that consists of
two disjoint edges.

Another well-studied set of Turán problems is the Forbidden intersection
problem of Erdős and Sós [20] from 1975. It concerns determining
$\mathrm{ex}\left(n,\mathcal{H}\right)$ in the case where the forbidden
hypergraph $\mathcal{H}$ consists of two edges with a given intersection, (see
[18, 25, 28, 30, 42]).

Besides the Turán problem for hypergraphs of determining
$\mathrm{ex}\left(n,\mathcal{H}\right)$ for various hypergraphs $\mathcal{H}$,
the research of $\mathcal{H}$-free families in recent years concentrated on
the following types of problems.

  1. (1)

$0.99$-type stability results. Suppose that $\mathcal{F}$ is a nearly extremal
$\mathcal{H}$-free family in the sense that its size is close to
$\mathrm{ex}\left(n,\mathcal{H}\right)$. Can we say that $\mathcal{F}$ is
close to an $\mathcal{H}$-free family? (See e.g. [26, 60]).

  2. (2)

$0.01$-type stability results. What is the structure of an $\mathcal{H}$-free
family whose size is within a constant of
$\mathrm{ex}\left(n,\mathcal{H}\right)$? (See [15, 34]).

  3. (3)

The removal problem. Suppose that $\mathcal{F}$ is a family that is almost
$\mathcal{H}$-free, in the sense that it contains few copies of $\mathcal{H}$.
Is it true that $\mathcal{F}$ is close to an $\mathcal{H}$-free family? (See
e.g. [37, 52, 54, 56]).

  4. (4)

The counting problem. How many $\mathcal{H}$-free families are there?
Particularly, is it true that almost all of them are contained in an extremal
$\mathcal{H}$-free family? (See e.g. [57, 58].

  5. (5)

The random problem. Let $p\in\left(0,1\right)$, and let
$\binom{\left[n\right]}{k}_{p}$ be the random family that contains each set in
$\binom{\left[n\right]}{k}$ independently with probability $p$. What is the
size of the largest $\mathcal{H}$-free subfamily of
$\binom{\left[n\right]}{k}_{p}$? (See e.g. [12, 59]).

In this paper our main focus will be on solving the 0.01-type stability
problem and the removal problem for a large class of hypergraphs called
_expanded hypergraphs_. These are the hypergraphs in which both the number of
edges and the intersections of pairs of the edges are bounded by a constant.
While we shall not address the counting problem and the random problem in this
paper, we would like to note that the container method of Balogh, Morris, and
Samotij [4], and independently of Saxton and Thomason [58], essentially
reduces the solutions of the counting problem and the random problem to the
solutions of the 0.99-type stability problem and the removal problem.
Therefore, our work should be viewed as progress towards all of the above
problems.

Our results are based on a novel theorem about the sharp threshold of ‘almost
monotone’ Boolean functions in the discrete cube, whose proof uses the
invariance principle of Mossel, O’Donnell, and Oleszkiewicz [50]. We believe
that the connection we establish between sharp threshold phenomena of Boolean
functions and the removal problem is the main contribution of this paper.

###  1.2. The structure of large families that are free from an expanded
hypergraphs

######  Definition 1.2.

A hypergraph is said to be _$\left(h,d\right)$ -expanded_ if it has at most
$h$ edges and the intersection of each two of its edges is of size at most
$d$.

The hypergraph $\mathcal{M}_{2}$ is an example of a
$\left(2,0\right)$-expanded hypergraph, and hypergraphs that are
$\left(h,1\right)$-expanded for some $h$ are known as _linear hypergraph_ s.
Generally speaking, we shall be concerned with $k$-uniform
$\left(h,d\right)$-expanded hypergraphs, where $h$ and $d$ are fixed, and
where $k$ is significantly larger.

Our terminology stems from the following standard definition, (see Mubayi and
Verstraëte [51]).

######  Definition 1.3.

Let $\mathcal{H}$ be a hypergraph. The $k$-expansion of $\mathcal{H}$ is the
$k$-uniform hypergraph $\mathcal{H}^{+}$ obtained from $\mathcal{H}$ by
enlarging each of its edges with distinct new vertices. We denote by
$\mathrm{ex}_{k}\left(n,\mathcal{H}^{+}\right)$ the problem of determining the
largest size of a family $\mathcal{F}\subseteq\binom{\left[n\right]}{k}$ free
of the $k$-expansion of $\mathcal{H}.$

Note that the $k$-expansion of a $d$-uniform hypergraph with $h$ edges is
$\left(h,d\right)$-expanded. Conversely, any $\left(h,d\right)$-expanded
hypergraph can be easily seen to be the $k$-expansion of some
$d\left(h-1\right)$-uniform hypergraph.

Many problems in extremal combinatorics can be expressed as determining
$\mathrm{ex}_{k}\left(n,\mathcal{H}^{+}\right)$ for a fixed hypergraph
$\mathcal{H}$ (see e.g. [29, 35, 44, 27], and the survey of Mubayi and
Verstraëte [51] for the case where $\mathcal{H}$ is a graph). The methods used
for attacking such problems are varied. One of the most successful methods is
the delta-system method of Erdős, Deza, and Frankl [14]. This method was
applied by Frankl and Füredi [25, 28, 29] to solve various Turán problems for
expanded hypergraphs (including the case where $\mathcal{H}$ is a special
simplex, a sunflower, or the hypergraph that consist of two edges with some
intersection of a fixed size). This allowed them to make significant progress
on several longstanding open problems in extremal combinatorics.

Another notable technique is the shifting technique of Erdős, Ko, and Rado
[21]. This technique was applied, e.g., in a recent breakthrough of Frankl
[27]. He gave the best bound for the Erdős Matching Conjecture [19], which
asks to determine $\mathrm{ex}_{k}\left(n,M_{s}^{+}\right),$ where
$M_{s}\subseteq\binom{\left[n\right]}{2}$ is a matching of size $s$. Other
methods include the Erdős-Simonovits stability method [60], and the random
sampling from the shadow method of Kostochka, Mubayi, and Verstraëte (see [44,
45, 46]).

Recently, a new approach towards the Turán problem for expansion was initiated
be Keller and the author [43] and further developed by Ellis, Keller, and the
author [18].

######  Definition 1.4.

A family $\mathcal{F}\subseteq\binom{\left[n\right]}{k}$ is said to depend on
the set of coordinates $J$ if for each sets $A,B\in\binom{\left[n\right]}{k}$
that satisfy $A\cap J=B\cap J$ we have $A\in\mathcal{F}\iff B\in\mathcal{F}.$
A family $\mathcal{F}$ is said to be a $j$-junta if it depends on a set $J$ of
size at most $j$. We say that a family $\mathcal{F}_{1}$ is _$\epsilon$
-essentially contained_ in $\mathcal{F}_{2}$ if

$\left|\mathcal{F}_{1}\backslash\mathcal{F}_{2}\right|\leq\epsilon\binom{n}{k}.$

The notion junta was introduced by Friedgut [31] while studying the
isoperimetric problem in discrete cube. Dinur and Friedgut [15] were the first
to use this notion in the study of $k$-uniform set-systems. They showed the
following.

######  Theorem 1.5 (Dinur–Friedgut [15]).

For each $r\in\mathbb{N},$ there exist $C>0,j\in\mathbb{N},$ such that any
intersecting family $\mathcal{F}\subseteq\binom{\left[n\right]}{k}$ is
$C\left(\frac{k}{n}\right)^{r}$-essentially contained in an intersecting
$j$-junta.

Note that the theorem is trivial for $\frac{k}{n}=\Theta\left(1\right),$ while
it is meaningful once $\frac{k}{n}$ is sufficiently small.

Inspired by [15], Keller and the author [43] extended Theorem 1.5 to show that
for each $h,r$ there exist $C>0,j\in\mathbb{N}$, such that any
$M_{h}^{+}$-free family $\mathcal{F}\subseteq\binom{\left[n\right]}{k}$ is
$C\left(\frac{k}{n}\right)^{r}$-essentially contained in an $M_{h}^{+}$-free
$j$-junta, and obtained the following result for general expanded hypergraphs.

######  Theorem 1.6 ([43]).

For each $\epsilon>0,h,d\in\mathbb{N},$ there exist $C>0,j\in\mathbb{N}$, such
that the following holds. Let $C<k<\frac{n}{C}$, and let $\mathcal{H}$ be a
$k$-uniform $\left(h,d\right)$-expanded hypergraph. Then any
$\mathcal{H}$-free family $\mathcal{F}\subseteq\binom{\left[n\right]}{k}$ is
$\epsilon$-essentially contained in an $\mathcal{H}$-free $j$-junta.

Theorem 1.6 serves as the first step in the following strategy for determining
$\mathrm{ex}\left(n,\mathcal{H}\right).$

  1. (1)

Show that any $\mathcal{H}$-free family is essentially contained in an
$\mathcal{H}$-free junta $\mathcal{J}$.

  2. (2)

Find the extremal junta $\mathcal{J}_{\mathrm{ex}}$ that is free of
$\mathcal{H}.$

  3. (3)

Show that if an $\mathcal{H}$-free junta has size that is close to
$\left|\mathcal{J}_{\mathrm{ex}}\right|$, then it must be a small perturbation
of $\mathcal{J}_{\mathrm{ex}}.$

  4. (4)

Show that any $\mathcal{H}$-free small perturbation of
$\mathcal{J}_{\mathrm{ex}}$ must have smaller size than it.

These four steps together suffice in order to show that the extremal junta is
the family $\mathcal{J}_{\mathrm{ex}}.$ Indeed, if $\mathcal{F}$ is the
extremal $\mathcal{H}$-free family, then Step 1 implies that $\mathcal{F}$ is
essentially contained in an $\mathcal{H}$-free junta $\mathcal{J}$. The fact
that $\mathcal{F}$ is of the extremal size implies that the size of
$\mathcal{J}$ cannot be much smaller than the size of
$\mathcal{J}_{\mathrm{ex}}.$ Step 3 implies that $\mathcal{F}$ is essentially
contained in $\mathcal{J}_{\mathrm{ex}},$ and Step 4 implies that
$\mathcal{F}$ is actually equal to $\mathcal{J}_{\mathrm{ex}}.$

This strategy was successfully carried out in [43] to solve the Turán problem
for various $\left(h,d\right)$-expanded hypergraphs, in the regime where
$C<k<\frac{n}{C}$ for some $C=C\left(h,d\right).$

Later, [18] showed that this strategy can be carried out also for some
hypergraphs in the regime where $\epsilon
n<k<\left(\frac{1}{2}-\epsilon\right)n$ for an arbitrarily small constant
$\epsilon,$ and a sufficiently large $n$. Specifically, they considered the
case where the forbidden hypergraph $\mathcal{H}$ is $\mathcal{I}_{2,d}$ that
consists of two edges that intersect in $d$ elements.

Their basic observation was that any junta that does not contain a copy of
$\mathcal{I}_{2,d}$ must be free of $\mathcal{I}_{2,d^{\prime}}$ for any
$d^{\prime}<d$ as well. In other words, any two sets in an
$\mathcal{I}_{2,d}$-free junta have intersection of size at least $d+1$. This
essentially reduces the problem to the well known problem on the size of
$\left(d+1\right)$-wise intersecting families, which was solved decades ago
using the shifting technique (see Ahlswede–Khachatrian [3], Filmus [22], and
Frankl [24]).

It is our belief that this strategy may be carried out for various other
$\left(h,d\right)$-expanded hypergraphs, and that the following result we
prove in this paper will serve as the first step in the solution of the Turán
problem for various other hypergraphs in the regime where $\epsilon
n<k\leq\left(\frac{1}{h}-\epsilon\right)n.$

######  Theorem 1.7.

For each $\epsilon>0,d,h\in\mathbb{N},$ there exists $j>0,$ such that the
following holds. Let $\epsilon n\leq k\leq\left(\frac{1}{h}-\epsilon\right)n$,
and let $\mathcal{H}$ be an $\left(h,d\right)$-expanded hypergraph. Then any
$\mathcal{H}$-free $\mathcal{F\subseteq}\binom{\left[n\right]}{k}$ is
$\epsilon$-essentially contained in an $\mathcal{H}$-free $j$-junta.

The special case of Theorem 1.7 where $\mathcal{H}=M_{2}^{+}=\mathcal{M}_{2}$
was already proved recently by Friedgut and Regev [34] who built upon the work
of Dinur and Friedgut [15]. Other special cases of Theorem 1.7 were proved in
[18], which settles the case $h=2$ of the theorem.

Theorem 1.7 is actually a special case of our main Theorem 1.13 below, which
deals also with families that contain few copies of $\mathcal{H}$, rather than
dealing only with $\mathcal{H}$-free families.

Similarly to the case where $\mathcal{H}=\mathcal{I}_{2,d}$, it turns out that
it is a general phenomenon that $\mathcal{H}$-free juntas are automatically
free of some other hypergraphs.

######  Definition 1.8.

Let $\mathcal{H}$ be a hypergraph and let $v$ be a vertex of $\mathcal{H}$.
The _resolution of $\mathcal{H}$ at $v$, _denoted by
$\mathrm{res}\left(\mathcal{H},v\right)$, is the hypergraph obtained from
$\mathcal{H}$ by taking $v$ out of each edge of $\mathcal{H}$ that contains
$v$, and by replacing it with a new vertex that belongs only to this edge. The
resolution of $\mathcal{H}$ at a set of vertices $S$, denoted by
$\mathrm{res}\left(\mathcal{H},S\right)$, is the hypergraph obtained by
resolving $\mathcal{H}$ at the vertices of $S$ one after the other. Any
hypergraph of the form $\mathrm{res}\left(\mathcal{H},S\right)$ will be called
a _resolution_ of _ $\mathcal{H}$_.

######  Example 1.9.

Any hypergraph $\mathcal{H}$ is a resolution of itself since
$\mathrm{res}\left(\mathcal{H},\varnothing\right)=\mathcal{H}$. Defining the
_center_ of a hypergraph $\mathcal{H}$ to be the set of its vertices that
belong to at least two of its edges, the $k$-uniform $h$-matching
$\mathcal{M}_{h}:=M_{h}^{+}$ is the resolution of any $k$-uniform hypergraph
with $h$ edges at its center. Another simple example is the hypergraph
$\mathcal{I}_{2,d}$: its resolutions are the hypergraphs of the form
$\mathcal{I}_{2,d^{\prime}}$ for $d^{\prime}\leq d.$

It is easy to show that any $j$-junta
$\mathcal{G}\subseteq\binom{\left[n\right]}{k}$ that is free of a hypergraph
$\mathcal{H}$ with $h$ edges is also free of every resolution of
$\mathcal{H}$, provided that $C<k\leq\left(\frac{1}{h}-\epsilon\right)n$ and
$n$ is large enough. Hence, in order to show that a given junta $\mathcal{J}$
is an extremal $\mathcal{H}$-free family, it would essentially be enough to
show that it is the extremal family that is free of a copy of $\mathcal{H}$ as
well as of all of its resolutions.

###  1.3. Removal lemma for expanded hypergraphs

While Theorem 1.7 tells us the structure of $\mathcal{H}$-free families it
tells us nothing on families that are ‘almost $\mathcal{H}$-free’, a notion
that may be defined more precisely as follows.

######  Definition 1.10.

Let $\delta>0$ and let $\mathcal{H}$ be a $k$-uniform hypergraph. We say that
a family $\mathcal{F}\subseteq\binom{\left[n\right]}{k}$ is _$\delta$ -almost
$\mathcal{H}$-free_ if a random copy of $\mathcal{H}$ in
$\binom{\left[n\right]}{k}$ lies within $\mathcal{F}$ with probability at most
$\delta.$

The celebrated triangle removal lemma says that for any $\epsilon>0$, there
exists $\delta>0$, such that any $\delta$-almost triangle-free graph is
$\epsilon$-essentially contained in a triangle-free graph. This was
generalized by Gowers [36, 37], and independently by Nagle, Rödl, Schacht, and
Skokan [52, 54] to show that for each fixed $k$-uniform hypergraph
$\mathcal{H}$, there exists $\epsilon>0$, such that if a family
$\mathcal{F}\subseteq\binom{\left[n\right]}{k}$ is $\delta$-almost
$\mathcal{H}$-free, then $\mathcal{F}$ is $\epsilon$-essentially contained in
an $\mathcal{H}$-free family. This result is known as the _hypergraph removal
lemma._(See the survey of Conlon and Fox [11] for a more thorough history, and
for quantitative aspects of removal lemmas.)

While the hypergraph removal lemma settles the case where $k,$ $\mathcal{H}$,
and $\epsilon$ are fixed, it becomes quite useless for $k$ that tends to
infinity with $n$. Indeed, the initial dependence of $\delta$ on $\epsilon$ in
the graph case where $k=2$ was

$\delta=\left(\mathrm{tower}\left(\epsilon^{-O_{\mathcal{H}}\left(1\right)}\right)\right)^{-1}=\underset{\epsilon^{-O_{\mathcal{H}}\left(1\right)}\text{
times}}{\underbrace{2^{2^{\iddots^{2}}}}},$

and this was improved by Fox [23] to
$\mathrm{tower}\left(O_{\mathcal{H}}\left(\log\frac{1}{\epsilon}\right)\right)^{-1}.$
For $k=3$ the best known bound is
$\delta=\underset{\epsilon^{-O_{\mathcal{H}}\left(1\right)}\text{
times}}{\underbrace{\mathrm{tower}\left(\mathrm{tower}\cdots\left(2\right)\right)^{-1}}}$,
and the bounds similarly worsen as $k$ increases (see [61, Remark 2.11]).

Friedgut and Regev [34] were the first to prove a removal lemma in the case
where $k$ is linear in $n$. They showed that for each $\epsilon>0$ there
exists $\delta>0$, such that if $\epsilon n\leq
k\leq\left(\frac{1}{2}-\epsilon\right)n,$ and if
$\mathcal{F}\subseteq\binom{\left[n\right]}{k}$ is a $\delta$-almost
$\mathcal{M}_{2}$-free family, then $\mathcal{F}$ is $\epsilon$-essentially
cxontained in an $\mathcal{M}_{2}$-free family. Later, Das and Tran [13]
proved a quantitatively stronger removal result for $\delta$-almost
$M_{2}^{+}$-free families whose size is close to $\binom{n-1}{k-1}.$

At first glance it may seem that the Friedgut–Regev Theorem follows from the
hypergraph removal lemma, but it actually does not. While the hypergraph
removal lemma deals with the case where $k$ and the hypergraph $\mathcal{H}$
are fixed, the Friedgut–Regev theorem deals with the case where $k$ is linear
in $n$. Our goal in this paper it to prove removal lemmas for other expanded
hypergraphs in the regime where $k$ is up to linear in $n$.

In light of Theorem 1.7, it may seem the Friedgut–Regev Theorem can be
generalized to all $\left(h,d\right)$-expanded hypergraphs. However, we show
that the following surprising statement holds.

######  Theorem 1.11.

For each $h,d\in\mathbb{N},\epsilon>0$ there exists $C,\delta>0$ such that the
following holds. Let $C\leq k\leq\left(\frac{1}{h}-\epsilon\right)n$, and let
$\mathcal{H}$ be a $k$-uniform $\left(h,d\right)$-expanded hypergraph, then we
have the following.

  1. (1)

If the family $\mathcal{F}$ is $\delta$-almost $\mathcal{H}$-free, then
$\mathcal{F}$ is $\epsilon$-essentially contained in an $\mathcal{M}_{h}$-free
family.

  2. (2)

Conversely, if the family $\mathcal{F}$ is $\delta$-essentially contained in
an $\mathcal{M}_{h}$-free family, then $\mathcal{F}$ is $\epsilon$-almost
$\mathcal{H}$-free.

So suppose that $\mathcal{F}$ is a family that we want to check whether it is
$\mathcal{H}$-free or not. One natural way to check if $\mathcal{F}$ is
$\mathcal{H}$-free is to choose uniformly at random copies of $\mathcal{H},$
and to check that none of them are contained in $\mathcal{F}$. While we could
expect that this would tell us that $\mathcal{F}$ is close to some
$\mathcal{H}$-free family, we instead obtain from Theorem 1.11 that this
implies that $\mathcal{F}$ is close to a family that is free of the hypergraph
$\mathcal{M}_{h}.$ Even more surprisingly, also the converse holds. Any family
that is close to an $\mathcal{M}_{h}$-free family contains few copies of
$\mathcal{H}.$ This phenomenon becomes clearer by inspecting the following
example.

######  Example 1.12.

The _star_ $\left\\{A\in\binom{\left[n\right]}{n/3}:\,1\in A\right\\}$ is
$o\left(1\right)$-almost free of the hypergraph $\mathcal{I}_{2,1}$, which
consists of two edges that intersect in a singleton $\left\\{i\right\\}$.
Indeed, the probability that a random copy of this hypergraph lies in the star
is $\frac{1}{n}$, as it is the probability that a random injection from the
vertices of $\mathcal{I}_{2,1}$ to $\left[n\right]$ sends the vertex $i$ to
$1$. As Theorem 1.11 guarantees, the star is $o\left(1\right)$-essentially
contained in an $\mathcal{M}_{2}$-free family as it is in itself
$\mathcal{M}_{2}$-free. However, the star is not $o\left(1\right)$-essentially
contained in any family free of the hypergraph $\mathcal{I}_{2,1}$.

More generally, suppose that $\mathcal{\mathcal{G}}$ is a $j$-junta depending
on a set $J$ and that $\mathcal{H}$ is an $\left(h,d\right)$-expanded
hypergraph. Then the center of a random copy of $\mathcal{H}$ most likely does
not intersect $J$. So from the ‘point of view’ of the junta $\mathcal{G}$, a
random copy of $\mathcal{H}$ and a random copy of $\mathcal{M}_{h}$ look the
same. It is therefore easy to see that

$\Pr\left[\text{a random copy of $\mathcal{H}$}\text{ lies in
}\mathcal{G}\right]=\Pr\left[\text{a random copy of $\mathcal{M}_{h}$}\text{
lies in }\mathcal{G}\right]+o\left(1\right).$

Let $\mathcal{F}\subseteq\binom{\left[n\right]}{k}$, and let $\mathcal{H}$ be
a hypergraph. We say that $\mathcal{F}$ is _$\left(\mathcal{H},s\right)$
-free_ if it is free of any resolution of $\mathcal{H}$ whose center is of
size at most $s.$ While Example 1.12 shows that being $o\left(1\right)$-almost
free of $\mathcal{H}$ is not sufficient for guaranteeing closeness to an
$\mathcal{H}$-free family, the following theorem shows that a stronger
assumption is sufficient.

######  Theorem 1.13.

For each $h,d,s\in\mathbb{N},\epsilon>0$ there exist
$\delta>0,j\in\mathbb{N}$, such that the following holds. Let $\mathcal{H}$ be
an $\left(h,d\right)$-expanded hypergraph. Let $\frac{1}{\delta}\leq
k\leq\left(\frac{1}{h}-\epsilon\right)n,$ and let $\mathcal{F}$ be a
$\frac{\delta}{n^{s}}$-almost $\mathcal{H}$-free family. Then $\mathcal{F}$ is
$\epsilon$-essentially contained in an $\left(\mathcal{H},s\right)$-free
$j$-junta.

Note that Theorem 1.7 is a special case of Theorem 1.13. Indeed, Theorem 1.13
implies that if $\mathcal{H}$ is a hypergraph whose center is of size $c$,
then any $\frac{\delta}{n^{c}}$-almost $\mathcal{H}$-free family is
$\epsilon$-essentially contained in an $\left(\mathcal{H},c\right)$-free
family, i.e. to a family free of $\mathcal{H}$ and of any resolution of it. On
the other hand, Theorem 1.7 yields the same conclusion under the stronger
hypothesis that $\mathcal{F}$ is $\mathcal{H}$-free.

The following proposition is a converse to Theorem 1.13. It shows that any
$\left(\mathcal{H},s\right)$-free $j$-juntas is
$O\left(\frac{1}{n^{s+1}}\right)$-almost $\mathcal{H}$-free. So in particular,
$j$-juntas are $\frac{\delta}{n^{s}}$-almost $\mathcal{H}$-free, provided that
$n$ is sufficiently large as a function of $\delta$.

######  Proposition 1.14.

For each $h,c,j,s\in\mathbb{N},$ there exists a constant $C>0$, such that the
following holds. Let $\mathcal{H}$ be a hypergraph with $h$ edges whose center
is of size $c$. Let $C\leq k\leq\left(\frac{1}{h}-\epsilon\right)n,$ and let
$\mathcal{J}$ be an $\left(\mathcal{H},s\right)$-free $j$-junta. Then
$\mathcal{J}$ is $\frac{C}{n^{s+1}}$-almost $\mathcal{H}$-free.

###  1.4. Sketch of Proof of Theorem 1.13 for matching

We shall now sketch the proof of Theorem 1.13 in the case where the forbidden
hypergraph is $\mathcal{M}_{h}.$ The proof relies on the regularity method and
on a novel sharp threshold result for ‘almost monotone’ Boolean functions that
will be presented in Section 2.

Let $\epsilon>0,h\in\mathbb{N}$ be fixed constants, and let $\mathcal{F}$ be a
family which is not $\epsilon$-contained in any family free of the matching
$\mathcal{M}_{h}$. Our goal is to show that a random matching lies in
$\mathcal{F}$ with probability $\Theta\left(1\right)$.

Note that any set $J$ decomposes the sets in $\mathcal{F}$ into
$2^{\left|J\right|}$ parts according to their intersection with $J$. Following
Friedgut and Regev [34] and [18] we apply a regularity lemma which says that
we may find a set $J$, such that in the decomposition of $\mathcal{F}$ induced
by $J$, almost all of the parts are either ‘random-like’ or sufficiently small
that we can ignore them. We may then take as our approximating junta, the
family

$\mathcal{G}=\left\\{A\in\binom{\left[n\right]}{k}:\,A\cap J\text{ corresponds
to a random part of }\mathcal{F}\right\\}.$

The fact that $\mathcal{F}$ is not $\epsilon$-essentially contained in an
$\mathcal{M}_{h}$-free family will allow us to show that $\mathcal{G}$ is not
$\mathcal{M}_{h}$-free. This in turn will imply that there exist pairwise
disjoints sets $A_{1},\ldots,A_{h}\subseteq J$ that correspond to random parts
of $\mathcal{F}.$ Now note that a random matching
$\left\\{\boldsymbol{B}_{1},\ldots,\boldsymbol{B}_{h}\right\\}$ intersects the
set $J$ in the sets $A_{1},\ldots,A_{h}$ with probability
$\Theta\left(1\right)$. So the remaining task is to show that if
$\mathcal{F}_{1},\ldots,\mathcal{F}_{h}$ are ‘random-like’ parts, then a
random matching $\boldsymbol{A}_{1},\ldots,\boldsymbol{A}_{h}$ satisfies
$\boldsymbol{A}_{i}\in\mathcal{F}_{i}$ with probability
$\Theta\left(1\right)$. We will accomplish this task using an enhancement of
the ‘sharp threshold technology’ presented by Dinur and Friedgut [15]. Let us
recall first the method in [15]. We say that families
$\mathcal{F}_{1},\ldots,\mathcal{F}_{h}$ are cross free of a matching if there
exist no pairwise disjoint sets $A_{1},\ldots,A_{h}$ such that
$A_{i}\in\mathcal{F}_{i}$ for each $i$, otherwise they cross-contain a
matching.

The _$p$ -biased distribution_ on $\mathcal{P}\left(\left[n\right]\right)$ is
a probability distribution on sets $\boldsymbol{A}\subseteq\left[n\right]$,
where each element is chosen to be in $\boldsymbol{A}$ independently with
probability $p.$ For a family $\mathcal{G}$, write
$\mu_{p}\left(\mathcal{G}\right)$ for
$\Pr_{\boldsymbol{A}\sim\mu_{p}}\left[\boldsymbol{A}\in\mathcal{G}\right].$ A
family $\mathcal{F}\subseteq\mathcal{P}\left(\left[n\right]\right)$ is
monotone if $B\in\mathcal{F}$ whenever $B\supseteq A$ for some
$A\in\mathcal{F}.$ The ‘sharp threshold principle’ essentially says that for a
random-like monotone family $\mathcal{F}$ the $p$-biased measure of
$\mathcal{F}$ jumps from being near $0$ to being near $1$ in a short interval.

Roughly speaking, the analogue of the strategy in [18] for the hypergraph
$\mathcal{M}_{h}$ goes as follows.

  1. (1)

Observe that if $\left\\{\mathcal{F}_{i}\right\\}_{i=1}^{h}$ are cross-free of
a matching, then their up-closures

$\left\\{\mathcal{F}_{i}^{\uparrow}:=\left\\{B:\,\exists A\subseteq B\text{
such that $A\in\mathcal{F}$}\right\\}\right\\}_{i=1}^{h}$

are also cross-free of a matching (in the sense that there are no pairwise
disjoint sets $A_{1},\ldots,A_{h}$ with $A_{i}\in\mathcal{F}_{i}^{\uparrow}$).

  2. (2)

Use a simple coupling argument to show that if
$\mu_{\frac{1}{h}}\left(\mathcal{F}_{i}^{\uparrow}\right)>1-\frac{1}{h}$ for
each $i$, then the families
$\mathcal{F}_{1}^{\uparrow},\ldots,\mathcal{F}_{h}^{\uparrow}$ cross-contain a
matching. So in particular, the families
$\mathcal{F}_{1},\ldots,\mathcal{F}_{h}$ cross contain a matching.

  3. (3)

Show that the families $\mathcal{F}_{i}^{\uparrow}$ are random-like monotone
families whose $\mu_{\frac{k}{n}}$ measure is bounded away from 0. The sharp
threshold principle will allow us to deduce that
$\text{$\mu$}_{\frac{1}{h}}\left(\mathcal{F}_{i}^{\uparrow}\right)$ is close
to 1, so by Step 2 the families $\left\\{\mathcal{F}_{i}\right\\}_{i=1}^{h}$
cannot be cross free of a matching.

This plan fails completely when we try to show the desired statement that
random-like families contain _many_ matchings. The step which stops to work is
the first one. While it is true that if $\left\\{\mathcal{F}_{i}\right\\}$ are
cross free of a matching, then their up closures
$\left\\{\mathcal{F}_{i}^{\uparrow}\right\\}$ are cross-free of a matching, it
is not true that if $\left\\{\mathcal{F}_{i}\right\\}$-are almost cross free
of a matching (in the sense that they cross contain few matchings), then the
families $\mathcal{F}_{i}^{\uparrow}$ are also almost cross free of a
matching. We resolve this issue by replacing the up-closure of $\mathcal{F}$
by the family

$\left\\{A\in\mathcal{P}\left(\left[n\right]\right):\,\left|A\right|\geq
k\text{ and a random }k\text{-}\text{subset of }A\text{ lies in
}\mathcal{F}\text{ with probability }\Theta\left(1\right)\right\\}.$

However, this new family is not monotone, and instead it satisfies a weaker
hypothesis that may be called ‘almost monotonicity’.

So to make the above plan work, we shall need to generalize the sharp
threshold principle from monotone families to ‘almost monotone’ families. This
statement is made more precise in Section 2. It is accomplished with the help
of the invariance principle of Mossel, O’Donnell, and Oleszkiewicz [50].

In our view, the main contribution of this paper comes from the fact that we
relate between sharp threshold results and hypergraph removal problems. We
believe that further exploration of the relation between these two well
studied problems will improve the understanding of each of them.

In the following section we give a more thorough introduction of the sharp
threshold principle of monotone Boolean functions, and state our sharp
threshold result for almost monotone Boolean functions. (Note that Boolean
functions $f\colon\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$, and
families $\mathcal{F}\subseteq\mathcal{P}\left(\left[n\right]\right)$ can be
identified).

##  2\. Sharp threshold theorems for almost monotone functions

We use bold letters to denote random variables, and we write $\left[n\right]$
for the set $\left\\{1,\ldots,n\right\\}.$ We shall use the convention that
the $i$th coordinate of an $x\in\left\\{0,1\right\\}^{n}$ is denoted by
$x_{i}$. A function $f\colon\left\\{0,1\right\\}^{n}\to\mathbb{R}$ is said to
be _monotone_ if $f\left(x\right)\leq f\left(y\right)$ whenever $x,y$ are
elements of $\left\\{0,1\right\\}^{n}$ that satisfy $\forall
i\in\left[n\right]:\,x_{i}\leq y_{i}$. The $p$-biased distribution $\mu_{p}$
is the distribution on the set $\left\\{0,1\right\\}^{n},$ where a random
element $\boldsymbol{x}\sim\mu_{p}$ is chosen by letting its coordinates
$\mathbf{x}_{i}$ to be independent random variables that take the value $1$
with probability $p$. For a function
$f\colon\left\\{0,1\right\\}^{n}\to\mathbb{R}$, we write
$\mu_{p}\left(f\right)$ for
$\mathbb{E}_{\mathbf{x}\sim\mu_{p}}\left[f\left(\mathbf{x}\right)\right].$

It is easy to see that for any monotone function
$f\colon\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$, the function
$p\mapsto\mu_{p}\left(f\right)$ is a monotone increasing function of $p$.
Roughly speaking, a Boolean function
$f\colon\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$ is said to have a
_sharp threshold_ if there exists a ‘short’ interval $\left[q,p\right]$, such
that $\mu_{q}\left(f\right)$ is ‘close’ to 0, and $\mu_{p}\left(f\right)$ is
‘close’ to 1. Otherwise, it is said to have a _coarse threshold_.

A central problem in the area of analysis of Boolean functions is the
following (see e.g. [10, 32, 33, 39]).

######  Problem 2.1.

Which monotone Boolean functions
$f\colon\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$ exhibit a coarse
threshold?

We shall now make the above discussion more formal. For a non-constant
monotone $f\colon\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$, the
_critical probability_ of $f$ (denoted by $p_{c}\left(f\right)$) is the unique
number in the interval $\left(0,1\right)$_, such that
$\mu_{p_{c}}\left(f\right)=\frac{1}{2}.$ _Bollobás and Thomason [7] showed
that for any fixed $\epsilon>0,$ and each Boolean function $f$ there exists an
interval $\left[q,p\right]$ with $q,p=\Theta\left(p_{c}\left(f\right)\right),$
such that $\mu_{q}\left(f\right)<\epsilon,$ and
$\mu_{p}\left(f\right)>1-\epsilon$. Therefore, $f$ should be considered to
have a sharp threshold if there exists an interval $\left[q,p\right]$ of
length significantly smaller than $p_{c}\left(f\right)$, such that
$\mu_{q}\left(f\right)<\epsilon$ and $\mu_{p}\left(f\right)>1-\epsilon$.

Formally, we say that a Boolean function
$f\colon\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$ exhibits an
$\epsilon$_-sharp threshold_ if there exists an interval $\left[q,p\right]$ of
length $\epsilon p_{c}\left(f_{n}\right)$, such that
$\mu_{q}\left(f\right)<\epsilon$ and $\mu_{p}\left(f\right)>1-\epsilon$. We
say that $f$ exhibits an $\epsilon$_-coarse threshold_ if there exist an
$\epsilon>0,$ and an interval $\left[q,p\right]$ of length at least $\epsilon
p_{c}\left(f\right),$ such that $\mu_{q}\left(f_{n}\right)>\epsilon,$ and
$\mu_{p}\left(f_{n}\right)<1-\epsilon.$

A function $f\colon\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$ is said to
be _transitive symmetric_ if the group of all permutations $\sigma\in S_{n},$
such that

$\forall
x\in\left\\{0,1\right\\}^{n}:\,f\left(x_{\sigma\left(1\right)},\ldots,x_{\sigma\left(n\right)}\right)\equiv
f\left(x_{1},\ldots,x_{n}\right)$

acts transitively on $\left\\{1,\ldots,n\right\\}.$

The Friedgut–Kalai Theorem [33] says that if $f$ is transitive symmetric and
$p_{c}\left(f\right)$ is bounded away from 0 and 1, then $f$ exhibits a sharp
threshold.

######  Theorem 2.2 (Friedgut–Kalai).

For each $\epsilon>0$ there exists $n_{0}=n_{0}\left(\epsilon\right)$ such
that the following holds. Let $n>n_{0}$ and let
$f\colon\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$ be a monotone
transitive symmetric function satisfying
$\epsilon<p_{c}\left(f\right)<1-\epsilon$. Then $f$ exhibits an
$\epsilon$-sharp threshold.

On the other hand, $f$ need not exhibit a coarse threshold if $f$ is no longer
assumed to be transitive symmetric. Let $j$ be a constant. A function $f$ is
said to be a _$j$ -junta_ if it depends on at most $j$ coordinates. It is easy
to see that any non-constant monotone $j$-junta exhibits an $\epsilon$-coarse
threshold for some constant $\epsilon=\epsilon\left(j\right)>0$. A well known
corollary of the celebrated Friedgut’s Junta Theorem [31] is a partial
converse to this statement. We shall say that $f$ is
_$\left(\mu_{r},\epsilon\right)$ -close_ to $g$ if

$\Pr_{\mathbf{x}\sim\mu_{r}}\left[f\left(\mathbf{x}\right)\neq
g\left(\mathbf{x}\right)\right]<\epsilon.$

######  Theorem 2.3 (Corollary of Friedgut’s Junta Theorem).

For each $\epsilon>0$, there exists $j\in\mathbb{N}$, such that the following
holds. Let $f\colon\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$ be a
Boolean function, and let $q,p$ be numbers in the interval $\left(0,1\right)$
that satisfy $p>q+\epsilon.$ Then there exists some $r$ in the interval
$\left[q,p\right],$ such that $f$ is $\left(\mu_{r},\epsilon\right)$-close to
a $j$-junta.

Note that Friedgut’s Junta Theorem becomes trivial if
$\mu_{q}\left(f\right)<\epsilon$ or if $\mu_{p}\left(f\right)>1-\epsilon$ as
in which case we may take the junta to be the corresponding constant function.
For that reason, Friedgut’s Junta Theorem can be interpreted by saying that
non-junta like functions exhibit a sharp threshold behavior.

###  2.1. Structural results on monotone families

We extend Theorems 2.2 and 2.3 in the following directions.

  * •

We replace the condition that $f$ is monotone with the weaker condition that
$f$ satisfies a notion we call _$\left(q,p,\delta\right)$ -almost
monotonicity._

  * •

We strengthen the Friedgut–Kalai theorem by relaxing the condition that $f$ is
transitive symmetric to the weaker condition that $f$ satisfies a notion
called _$\left(r,\delta,\mu_{q}\right)$ -regularity_.

  * •

Bearing in mind our applications to the removal problem, we modify Theorem 2.3
by replacing the condition that $f$ is ‘close’ to a junta with respect to the
$\mu_{r}$ measure with a condition that says that $f$ is ‘close’ to a junta in
a sense that involves only the measures $\mu_{p}$ and $\mu_{q}$, i.e. the
measures at the ends of the interval.

We shall now define the above notions more precisely, starting with
$\left(q,p,\delta\right)$-almost monotonicity. Intuitively, a function $f$
should be called ‘almost monotone’ if $f\left(x\right)\leq f\left(y\right)$
for almost all values of $x$ and $y$ that satisfy $\forall
i\in\left[n\right]:\,x_{i}\leq y_{i}.$ However, there are many ways to
interpret the notion ‘almost all values of $x$ and $y$’. For instance, the
following definitions all seem to fit equally well.

  * •

Choose $\mathbf{x}$ uniformly out of $\left\\{0,1\right\\}^{n}$ and then
choose $\mathbf{y}$ uniformly among the set of all the elements
$y\in\left\\{0,1\right\\}^{n}$ that satisfy $\forall
i:\,y_{i}\geq\mathbf{x}_{i}$. Say that $f$ is ‘almost monotone’ if
$\Pr\left[f\left(\mathbf{x}\right)>f\left(\mathbf{y}\right)\right]$ is
‘small’.

  * •

First choose $\mathbf{y}$ uniformly out of $\left\\{0,1\right\\}^{n}$, then
choose $\mathbf{x}$ among the set of all $x\in\left\\{0,1\right\\}^{n}$ that
satisfy $\forall i:\,x_{i}\leq\mathbf{y}_{i},$ and say that $f$ is ‘almost
monotone’ if
$\Pr\left[f\left(\mathbf{x}\right)>f\left(\mathbf{y}\right)\right]$ is
‘small’.

  * •

Choose a uniformly random pair of elements
$\mathbf{x},\mathbf{y}\in\left\\{0,1\right\\}^{n}$ among the
$x,y\in\left\\{0,1\right\\}^{n}$ that satisfy $\forall i:\,x_{i}\leq y_{i},$
and say that $f$ is ‘almost monotone’ if
$\Pr\left[f\left(\mathbf{x}\right)>f\left(\mathbf{y}\right)\right]$ is
‘small’.

Note that these notions are different. In the first we have

$\Pr\left[\mathbf{x}_{i}=1\right]=\frac{1}{2}\text{ and
}\Pr\left[\mathbf{y}_{i}=1\right]=\frac{3}{4},$

in the second we have

$\Pr\left[\mathbf{x}_{i}=1\right]=\frac{1}{4}\text{ and
}\Pr\left[\mathbf{y}_{i}=1\right]=\frac{1}{2},$

and in the last we have

$\Pr\left[\mathbf{x}_{i}=1\right]=\frac{1}{3}\text{ and
}\Pr\left[\mathbf{y}_{i}=1\right]=\frac{2}{3}.$

All these notions are captured by the following framework.

######  Definition 2.4.

Let $q<p.$ The $\left(q,p\right)$-biased distribution, denoted by
$D\left(q,p\right)$, is the unique probability distribution on elements
$\left(\mathbf{x},\mathbf{y}\right)\in\left\\{0,1\right\\}^{n}\times\left\\{0,1\right\\}^{n}$
that satisfies the following.

  1. (1)

The pairs $\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)$ are independent random
variables.

  2. (2)

We have $\mathbf{x}_{i}\leq\mathbf{y}_{i}$ with probability 1.

  3. (3)

We have $\Pr\left[\mathbf{x}_{i}=1\right]=q$ and
$\Pr\left[\mathbf{y}_{i}=1\right]=p.$

We write $\mathbf{x,y}\sim D\left(q,p\right)$ to denote that they are chosen
according to this distribution. We say that
$f\colon\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$ is
$\left(q,p,\delta\right)$-almost monotone if

$\Pr_{\mathbf{x,y}\sim
D\left(q,p\right)}\left[f\left(\mathbf{x}\right)>f\left(\mathbf{y}\right)\right]<\delta.$

It will be convenient for us to define the following notion of ‘closeness’
between a function $f$ and a function $g$ that takes into considerations both
the $p$-biased measure and the $q$-biased one. We say that functions
$f,g\colon\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$ are
_$\left(\mu_{q},\mu_{p},\epsilon\right)$ -close_ if the set of all
$x\in\left\\{0,1\right\\}^{n}$ such that $f\left(x\right)\neq g\left(x\right)$
can be partitioned into the union of two sets $S_{p}$ and $S_{q}$, such that
$\mu_{p}\left(S_{p}\right)<\epsilon$ and $\mu_{q}\left(S_{q}\right)<\epsilon.$

We give the following variant of Friedgut’s junta theorem, which implies that
if $\epsilon,q<p$ are fixed numbers in the interval $\left(0,1\right)$, if
$\delta>0$ is small enough, and if $j\in\mathbb{N}$ is sufficiently large,
then any $\left(q,p,\delta\right)$-almost monotone function $f$ is
$\left(\mu_{q},\mu_{p},\epsilon\right)$-close to a monotone $j$-junta.

######  Theorem 2.5.

For each $\epsilon>0$, there exists $j\in\mathbb{N},\delta>0$, such that the
following holds. Let $p,q$ be numbers in the interval
$\left(\epsilon,1-\epsilon\right)$ that satisfy $p-q>\epsilon$ and let
$f\colon\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$ be a
$\left(q,p,\delta\right)$-almost monotone function. Then there exists a
monotone $j$-junta $g$, such that

$\Pr_{\mathbf{x}\sim\mu_{q}}\left[f\left(\mathbf{x}\right)>g\left(\mathbf{x}\right)\right]<\epsilon\text{
and
}\Pr_{\mathbf{x}\sim\mu_{p}}\left[f\left(\mathbf{x}\right)<g\left(\mathbf{x}\right)\right]<\epsilon.$

Note that Theorem 2.5 is really a theorem about functions that have a coarse
threshold. Indeed, if we have either $\mu_{p}\left(f\right)>1-\epsilon$ or
$\mu_{q}\left(f\right)<\epsilon$, then the theorem becomes trivial by taking
$g$ to be a suitable constant function.

The conclusion of Theorem 2.5 says that $f$ can be ‘approximated’ by the junta
$g$, where our approximation notion is the ‘two-sided’ notion of
$\left(q,p,\epsilon\right)$-closeness. It is natural to ask whether $f$ can
also be approximated by a junta according to a ‘one-sided’ notion, such as the
notions of $\left(\mu_{p},\epsilon\right)$-closeness and
$\left(\mu_{q},\epsilon\right)$-closeness. The following example demonstrates
that the two-sided approximation is actually necessary.

######  Example 2.6.

Fix some numbers $q,p$ in the interval $\left(0,1\right)$ that satisfy $q<p$.
Let $f_{n}\colon\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$ be the
function defined by

$f\left(x\right)=\begin{cases}1&x_{1}=1,\mbox{ and }\sum_{i=2}^{n}x_{i}>qn\\\
1&x_{1}=0,\mbox{ and }\sum_{i=2}^{n}x_{i}>pn\\\
0&\mbox{Otherwise}\end{cases}.$

The Central Limit Theorem implies that

$\mu_{q}\left(f\right)=\frac{q}{2}+o\left(1\right)\text{ and
}\mu_{p}\left(f\right)=\frac{\left(1+p\right)}{2}+o\left(1\right).$

Since both $\mu_{q}\left(f\right)$ and $\mu_{p}\left(f\right)$ are bounded
away from 0 and 1, we obtain that $f$ has an $\epsilon$-coarse threshold for
some constant $\epsilon$ independent of $n$. On the other hand, it is easy to
see that $f$ is not $\left(\mu_{p},\frac{\left(1-p\right)}{4}\right)$-close to
an $O\left(1\right)$-junta and is not
$\left(\mu_{q},q\left(1-q\right)\right)$-close to an $O\left(1\right)$-junta,
provided that $n$ is sufficiently large. However, if we take $g$ to be the
_dictator_ function defined by $g\left(x\right)=x_{1},$ then we have

$\Pr_{\mathbf{x}\sim\mu_{q}}\left[f\left(\mathbf{x}\right)>g\left(\mathbf{x}\right)\right]=o\left(1\right)\text{
and
}\Pr_{\mathbf{x}\sim\mu_{p}}\left[f\left(\mathbf{x}\right)<g\left(\mathbf{x}\right)\right]=o\left(1\right),$

as Theorem 2.5 guarantees.

The proof of Theorem 2.5 is based on the invariance principle of Mossel,
O’Donnell, and Oleszkiewicz [50] and on a recent unpublished regularity lemma
of O’Donnell, Servedio, Tan, and Wan. A presentation of their proof was
recently given by Jones [40].

For our next extension of the Friedgut–Kalai Theorem, we need the notion of
$\left(r,\epsilon,\mu_{p}\right)$_-regularity_ , (see O’Donnell [53, Chapter
7] for more about this notion). Let $R$ be a subset of $\left[n\right],$ and
let $y\in\left\\{0,1\right\\}^{R}$. We write $f_{R\to y}$ for the Boolean
function on the domain $\left\\{0,1\right\\}^{\left[n\right]\backslash R}$
defined by $f_{R\to y}\left(x\right)=f\left(z\right),$ where $z$ is the vector
whose projection to $\left\\{0,1\right\\}^{R}$ is $y$ and whose projection to
$\left\\{0,1\right\\}^{\left[n\right]\backslash R}$ is $x.$

Note that a function $f$ is a $j$-junta if there exists a set $J$ of size $j$,
such that all the restrictions $f_{J\to x}$ are constant functions. On the
other extreme, we have the following notion of regularity which could be
thought of as the complete opposite of being a junta. It says that for each
set $J$ of constant size $r$, the $\mu_{p}$ measures of $f$ and of $f_{J\to
y}$ are not far apart.

######  Definition 2.7.

A function $f\colon\left\\{0,1\right\\}^{n}\to\left[0,1\right]$ is said to be
$\left(r,\epsilon,\mu_{p}\right)$-regular if

$\left|\mu_{p}\left(f_{J\to y}\right)-\mu_{p}\left(f\right)\right|<\epsilon$

for each set $J\subseteq\left[n\right]$ of size at most $r$ and each
$y\in\left\\{0,1\right\\}^{J}$.

As we explain below the following is a robust version of the Friedgut–Kalai
Theorem.

######  Theorem 2.8.

For each $\epsilon>0$, there exists $\delta>0$, such that the following holds.
Let $q,p\in\left(\epsilon,1-\epsilon\right)$ and suppose that $p>q+\epsilon$.
Let $f,g\colon\left\\{0,1\right\\}^{n}\to\left[0,1\right]$. Suppose that

$\mathbb{E}_{\left(\mathbf{x},\mathbf{y}\right)\sim
D\left(q,p\right)}\left[\left(1-g\left(\mathbf{y}\right)\right)f\left(\mathbf{x}\right)\right]<\delta,$

and that the function $f$ is
$\left(\left\lceil\frac{1}{\delta}\right\rceil,\delta,\mu_{q}\right)$-regular.
Then either $\mu_{q}\left(f\right)<\epsilon$, or
$\mu_{p}\left(g\right)>1-\epsilon.$

Theorem 2.8 is a robust version of Theorem 2.2. Indeed, note that one can
equivalently restate Theorem 2.2 as follows. Let $q$ and $p$ be numbers in the
interval $\left(\epsilon,1-\epsilon\right)$, and suppose that $p>q+\epsilon$.
Let $f\colon\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$ be a monotone
transitive symmetric Boolean function. Then we either have
$\mu_{q}\left(f\right)<\epsilon$, or we have
$\mu_{p}\left(g\right)>1-\epsilon$, provided that $n$ is sufficiently large.

Applying Theorem 2.8 (with $f=g$), we see that it strengthens Theorem 2.2 in
the following ways. It shows that we may replace the hypothesis that $f$ is
monotone by the weaker hypothesis that $f$ is $\left(q,p,\delta\right)$-almost
monotone, and that we may replace the hypothesis that $f$ is transitive
symmetric, with the weaker hypothesis that the $f$ is
$\left(\left\lceil\frac{1}{\delta}\right\rceil,\delta,\mu_{q}\right)$-regular
for some $\delta=\delta\left(n\right),$ where
$\lim_{n\to\infty}\delta\left(n\right)=0.$ Example 3.8 below shows that the
latter hypothesis is indeed weaker.

######  Remark 2.9.

While Theorem 2.8 is more general than the Friedgut–Kalai Theorem, we remark
that the Friedgut–Kalai Theorem is better in the quantitative aspects that we
have not addressed. We would also like to remark that the proof of Theorem 2.5
is very different than the standard proofs of Theorems 2.2 and 2.3. While the
traditional proofs are based on the hypercontractivity theorem of Bonami,
Gross, and Beckner [8, 38, 5] and on Russo’s Lemma [55], our proof of Theorem
2.8 is based instead on the invariance principle of O’Donnell, Mossel, and
Oleszkiewicz [50].

###  2.2. Sketch of the proof of Theorems 2.5 and 2.8

Our proof of Theorem 2.5 is based on the _regularity method_. In the setting
of the regularity method we are given a space $\mathcal{S}$, and our goal is
to show a ‘removal lemma’ asserting that any subset $A\subseteq\mathcal{S}$
that contain few copies of a given ‘forbidden’ configuration may be
approximated by a family that contains no copies of that configuration. The
proof contains two ingredients.

  1. (1)

A _regularity lemma_ showing that for any set $A$, we may decompose $B$ into
some parts, such that the intersections of $A$ with ‘almost all’ of the parts
are either ‘quasirandom’ or ‘small’.

  2. (2)

A _counting lemma_ showing that if we take the quasirandom parts, then
together they contain many forbidden configurations.

These two ingredients are put together by approximating $A$ by the set $J$
defined to be the union of all the quasirandom parts of $B$. The task is then
to use the counting lemma to show that any forbidden configuration that
appears in $J$ results in many forbidden configurations back in $A.$

The invariance principle of Mossel O’Donnell and Oleszkiewicz [50] considers a
notion of smoothness called _small noisy influences_. It roughly says that we
may replace the variables of a smooth function
$f\colon\left\\{0,1\right\\}^{n}\to\left[0,1\right]$ by Gaussian random
variables and obtain a function that behaves similarly. We call this function
the Gaussian analogue of $f$. The proof of Theorem 2.5 goes through the
following steps.

  1. (1)

We apply a regularity lemma presented by Jones [40], which shows that we may
find a set $J$ of constant size that decomposes $f$ into the parts
$\left\\{f_{J\to y}\right\\}_{y\in\left\\{0,1\right\\}^{J}}$, such that almost
all of the parts either have expectation very close to 0, or have small noisy
influences.

  2. (2)

We give a counting lemma that shows that if two functions
$f_{1},f_{2}\colon\left\\{0,1\right\\}^{n}\to\left[0,1\right]$ have small
noisy influences and satisfy
$\mathbb{E}_{\mathbf{x}\sim\mu_{q}}\left[f_{1}\left(\mathbf{x}\right)\right],\mathbb{E}_{\boldsymbol{y}\sim\mu_{p}}\left(1-f_{2}\left(\mathbf{y}\right)\right)=\Theta\left(1\right)$,
then

$\mathbb{E}_{\mathbf{x},\mathbf{y}\sim
D\left(q,p\right)}\left[f_{1}\left(\mathbf{x}\right)\left(1-f_{2}\left(\mathbf{y}\right)\right)\right]=\Theta\left(1\right).$

The proof of the second part follows [50]. We express
$\mathbb{E}_{\mathbf{x},\mathbf{y}\sim
D\left(q,p\right)}\left[f_{1}\left(\mathbf{x}\right)\left(1-f_{2}\left(\mathbf{y}\right)\right)\right]$
in terms of the Fourier expansions of $f_{1}$ and $f_{2}$, and we show that
this expression can be approximated by a similar expression involving the
Gaussian analogues of $f_{1}$ and $f_{2}$. We then apply a classical theorem
by Borell [9] to lower bound the value of the corresponding expression.

The proof of Theorem 2.8 is similar. Suppose that $f$ is a
$\left(\left\lceil\frac{1}{\delta}\right\rceil,\delta,\mu_{q}\right)$-regular
function with $\mu_{q}\left(f\right)>\epsilon$.

  1. (1)

We apply the regularity lemma of [40] to find a set $J$ of constant size that
decomposes $f$ into the parts $\left\\{f_{J\to
y}\right\\}_{y\in\left\\{0,1\right\\}^{J}}$, such that most of the parts
either have expectations very close to 0, or have small noisy influences. The
$\left(\left\lceil\frac{1}{\delta}\right\rceil,\delta,\mu_{q}\right)$-regularity
of $f$ implies that there are no parts with expectations close to 0, so only
the latter option is available.

  2. (2)

We note that the term

$\mathbb{E}_{\mathbf{z},\boldsymbol{w}\sim\left(\left\\{0,1\right\\}^{n-\left|J\right|},D\left(q,p\right)\right)}\left[f_{J\to
x}\left(\boldsymbol{\mathbf{z}}\right)\left(1-g_{J\to
y}\left(\boldsymbol{w}\right)\right)\right]$

is small for each $x,y\in\left\\{0,1\right\\}^{J},$ such that $x_{i}\leq
y_{i}$ for each $i$.

  3. (3)

We deduce from the above counting lemma (applied with $f_{1}=f_{J\to
x},f_{2}=g_{J\to y}$) that for such $x,y$, if $f_{J\to x}$ has small noisy
influences, then the function $g_{J\to y}$ has expectation close to 1.

  4. (4)

It is easy that for ‘almost all’ $y\in\left\\{0,1\right\\}^{J}$ we may find
$x\in\left\\{0,1\right\\}^{J}$ with $x_{i}\leq y_{i}$ for each $i$, such that
$f_{J\to x}$ has small noisy influences. So Step 3 implies that for almost all
$y$ the expectation of $g_{J\to y}$ is close to $1$. Therefore, the
expectation of $g$ is close to $1$.

##  3\. Prior results and notions that we make use of

In this section we review some facts on the Fourier analysis of the $p$-biased
cube. Many of them are standard results that can be found e.g. in O’Donnell
[53, Chapters 2,8, and 11].

###  3.1. Fourier analysis on the $p$-biased cube

Given a distribution $D$ on a space $\Omega$, we write
$\boldsymbol{x}\sim\left(\Omega,D\right)$ or $\boldsymbol{x}\sim D$ to denote
that$\boldsymbol{x}$ is chosen out of $\Omega$ according to the distribution
$D$. We shall use bold letters to denote random variables.

We denote by $L^{2}\left(\left\\{0,1\right\\}^{n},\mu_{p}\right)$ the Hilbert
space of function $f\colon\left\\{0,1\right\\}^{n}\to\mathbb{R}$ equipped with
the $p$-biased inner product

$\left\langle
f,g\right\rangle=\mathbb{E}_{\mathbf{x}\sim\left(\left\\{0,1\right\\}^{n},\mu_{p}\right)}\left[f\left(\mathbf{x}\right)g\left(\mathbf{x}\right)\right].$

The _$p$ -biased norm_ is defined by setting $\|f\|=\sqrt{\left\langle
f,f\right\rangle}$. In any time that we write that $f$ is an element of the
space $L^{2}\left(\left\\{0,1\right\\}^{n},\mu_{p}\right),$ we shall use the
shorthand $\mathbb{E}\left[f\right]$ for
$\mathbb{E}_{\mathbf{x}\sim\left(\left\\{0,1\right\\}^{n},\mu_{p}\right)}\left[f\right]$.

The $p$-biased Fourier characters are an orthonormal basis of
$L^{2}\left(\left\\{0,1\right\\}^{n},\mu_{p}\right)$ defined as follows.

######  Definition 3.1.

Let $i\in\left[n\right]$. The _Fourier character_ corresponding to the
singleton $\left\\{i\right\\}$ is the function $\chi_{i}^{p}\in
L^{2}\left(\left\\{0,1\right\\}^{n},\mu_{p}\right)$ defined by the formula

$\chi_{i}^{p}\left(x\right):=\begin{cases}-\sqrt{\frac{1-p}{p}}&x_{i}=1\\\
\sqrt{\frac{p}{1-p}}&x_{i}=0\end{cases}.$

More generally, let $S$ be a subset of $\left[n\right]$. The _Fourier
character_ corresponding to the set $S\subseteq\left[n\right]$ is the function
$\chi_{S}^{p}:=\prod_{i\in S}\chi_{i}^{p}.$

The Fourier characters are known to be an orthonormal basis for
$L^{2}\left(\left\\{0,1\right\\}^{n},\mu_{p}\right)$. Thus, each function has
a unique expansion of the form
$f=\sum_{S\subseteq\left[n\right]}\hat{f}\left(S\right)\chi_{S}^{p},$ where
$\hat{f}\left(S\right)=\left\langle f,\chi_{S}^{p}\right\rangle.$ This
expansion is called the _$p$ -biased Fourier expansion_ of $f$, or just the
Fourier expansion of $f$, where $p$ is clear from context. We also have the
following identities known as the _Parseval identities_.

$\mathbb{E}\left[f^{2}\right]=\left\langle
f,f\right\rangle=\sum_{S\subseteq\left[n\right]}\hat{f}\left(S\right)^{2}$
$\mathbb{E}\left[fg\right]=\left\langle
f,g\right\rangle=\sum_{S\subseteq\left[n\right]}\hat{f}\left(S\right)\hat{g}\left(S\right).$

For any $T\subseteq\left[n\right]$, the _averaging_ operator

$\mathsf{A}_{T}\colon L^{2}\left(\left\\{0,1\right\\}^{n},\mu_{p}\right)\to
L^{2}\left(\left\\{0,1\right\\}^{n-\left|T\right|},\mu_{p}\right)$

is defined by setting

$\mathsf{A}_{T}\left[f\right]\left(x\right)=\mathbb{E}\left[f_{\left[n\right]\backslash
T\to x}\right].$

The operator $\mathsf{A}_{T}\left[f\right]$ has the following nice Fourier
analytical interpretation. It is the operator that annihilates all the Fourier
coefficients that correspond to sets that have nonempty intersection with $T$.

######  Fact 3.2.

Let $f\in L^{2}\left(\left\\{0,1\right\\}^{n},\mu_{p}\right)$ be a function
that has the Fourier expansion

$f=\sum_{S\subseteq\left[n\right]}\hat{f}\left(S\right)\chi_{S}^{p}.$

Then

$\mathsf{A}_{T}\left[f\right]=\sum_{S\subseteq\left[n\right]\backslash
T}\hat{f}\left(S\right)\chi_{S}^{p}$

Another notion of importance for us is the notion of _influence_ by Ben-Or and
Linial [6].

######  Definition 3.3.

The _$p$ -biased $i$th influence_ of a function
$f\colon\left\\{0,1\right\\}^{n}\to\mathbb{R}$ whose Fourier expansion is
$\sum_{S\subseteq\left[n\right]}\hat{f}\left(S\right)\chi_{S}^{p}$ is defined
by setting

(3.1)
$\mathrm{Inf}_{i}^{p}\left[f\right]=\mathbb{E}\left[\left(f-A_{\left\\{i\right\\}}\left[f\right]\right)^{2}\right]=\sum_{S\ni
i}\hat{f}\left(S\right)^{2}.$

We shall also need to introduce the noise operator.

######  Definition 3.4.

Given $x\in\left\\{0,1\right\\}^{n}$ the $\left(\rho,p\right)$_-noisy
distribution_ of $x$ denoted by $N_{\rho,p}\left(x\right)$ is a probability
distribution on elements $\mathbf{y}\in\left\\{0,1\right\\}^{n}$, where we set
each coordinate $\mathbf{y}_{i}$ independently to be $x_{i}$ with probability
$\rho$, and to a new $p$-biased element of $\left\\{0,1\right\\}$ with
probability $1-\rho.$

The _noise operator_ $\mathsf{T}_{\rho,p}$ on the space
$L^{2}\left(\left\\{0,1\right\\}^{n},\mu_{p}\right)$ is the operator that
associates to each $f\in L^{2}\left(\left\\{0,1\right\\}^{n},\mu_{p}\right)$
the function

$\mathsf{T}_{\rho,p}\left[f\right]:=\underset{\mathbf{y}\sim
N_{\rho,p}\left(x\right)}{\mathbb{E}}\left[f\left(\mathbf{y}\right)\right].$

We have the following Fourier formula for $\mathsf{T}_{\rho,p}\left[f\right].$

######  Fact 3.5.

Let $\rho,p\in\left(0,1\right)$, and let

$f=\sum_{S\subseteq\left[n\right]}\hat{f}\left(S\right)\chi_{S}^{p}$

be a function in $L^{2}\left(\left\\{0,1\right\\}^{n},\mu_{p}\right)$. Then

$\mathsf{T}_{\rho,p}\left[f\right]=\sum_{S\subseteq\left[n\right]}\rho^{\left|S\right|}\hat{f}\left(S\right)\chi_{S}^{p}.$

###  3.2. The directed noise operators

We shall now introduce a directed analogue of the noise operator. Recall that
$D\left(q,p\right)$ is the joint distribution on elements
$\left(\mathbf{x},\mathbf{y}\right)\in\left\\{0,1\right\\}^{n}\times\left\\{0,1\right\\}^{n},$
such that

$\mathbf{x}\sim\mu_{q},\mathbf{y}\sim\mu_{p},\,\,\,\forall
i:\,\mathbf{y}_{i}\geq\mathbf{x}_{i}.$

We define an operator

$\mathsf{T}_{p\to q}\colon
L^{2}\left(\left\\{0,1\right\\}^{n},\mu_{p}\right)\to
L^{2}\left(\left\\{0,1\right\\}^{n},\mu_{q}\right),$

and its adjoint

$\mathsf{T}^{q\to p}\colon
L^{2}\left(\left\\{0,1\right\\}^{n},\mu_{q}\right)\to
L^{2}\left(\left\\{0,1\right\\}^{n},\mu_{p}\right),$

by setting

$\mathsf{T}_{p\to
q}\left(f\right)\left(x\right)=\mathbb{E}_{\mathbf{x},\mathbf{y}\sim
D\left(q,p\right)}\left[f\left(\mathbf{y}\right)\,|\,\mathbf{x}=x\right],$

and

$\mathsf{T}^{q\to
p}\left(f\right)\left(y\right)=\mathbb{E}_{\mathbf{x},\mathbf{y}\sim
D\left(q,p\right)}\left[f\left(\mathbf{x}\right)\,|\,\mathbf{y}=y\right].$

These operators were first studied by Ahlberg, Broman, Griffiths, and Morris
[2], and then again by Abdullah and Venkatasubramania [1]. The one sided noise
operator has the following Fourier formulas:

######  Lemma 3.6.

Let $p>q$, and set $\rho=\sqrt{\frac{q\left(1-p\right)}{p\left(1-q\right)}}.$
Let $f=\sum_{S\subseteq\left[n\right]}\hat{f}\left(S\right)\chi_{S}^{q}$ be a
function in $L^{2}\left(\left\\{0,1\right\\}^{n},\mu_{q}\right)$. Then
$\mathsf{T}^{q\to p}\left(f\right)$ has the $p$-biased Fourier expansion:

$\mathsf{T}^{q\to
p}\left(f\right)=\sum_{S\subseteq\left[n\right]}\rho^{\left|S\right|}\hat{f}\left(S\right)\chi_{S}^{p}.$

Similarly, if
$g=\sum_{S\subseteq\left[n\right]}\hat{g}\left(S\right)\chi_{S}^{p}$ is a
function in $L^{2}\left(\left\\{0,1\right\\}^{n},\mu_{p}\right)$, then the
function $\mathsf{T}_{p\to q}\left(g\right)$ has the $q$-biased Fourier
expansion

$\mathsf{T}_{p\to
q}\left(g\right)=\sum_{S\subseteq\left[n\right]}\rho^{\left|S\right|}\hat{g}\left(S\right)\chi_{S}^{q}.$

###### Proof.

We shall prove it for the operator $\mathsf{T}^{q\to p},$ as the proof for the
other operator $\mathsf{T}_{p\to q}$ will be similar. By linearity, it is
enough to prove the lemma in the case where $f=\chi_{S}^{q}$ for some
$S\subseteq\left[n\right].$ Let $y\in\left\\{0,1\right\\}^{n}.$ Note that

(3.2) $\displaystyle\mathsf{T}^{q\to
p}\left[\chi_{S}^{q}\right]\left(y\right)$
$\displaystyle=\mathbb{E}_{\mathbf{x},\mathbf{y}\sim
D\left(q,p\right)|\,\mathbf{y}=y}\left[\chi_{S}^{q}\left(\mathbf{x}\right)\right]=\mathbb{E}_{\mathbf{x},\mathbf{y}\sim
D\left(q,p\right)|\,\mathbf{y}=y}\left[\prod_{i\in
S}\chi_{i}^{q}\left(\mathbf{x}_{i}\right)\right].$

Claim 3.7 below shows that

$\mathbb{E}_{\mathbf{x},\mathbf{y}\sim
D\left(q,p\right)|\,\mathbf{y}=y}\left[\chi_{i}^{q}\left(\mathbf{x}_{i}\right)\right]=\rho\chi_{i}^{p}\left(y_{i}\right).$

By the independence of the random variables
$\chi_{i}^{q}\left(\mathbf{x}_{i}\right)$ for any $\mathbf{x},\mathbf{y}\sim
D\left(q,p\right)|\,\mathbf{y}=y$ we obtain:

(3.3) $\displaystyle\mathbb{E}_{\mathbf{x},\mathbf{y}\sim
D\left(q,p\right)|\,\mathbf{y}=y}\left[\prod_{i\in
S}\chi_{\left\\{i\right\\}}^{q}\left(\mathbf{x}_{i}\right)\right]$
$\displaystyle=\prod_{i\in S}\mathbb{E}_{\mathbf{x},\mathbf{y}\sim
D\left(q,p\right)|\,\mathbf{y}=y}\left[\chi_{i}^{q}\left(\mathbf{x}_{i}\right)\right]$
$\displaystyle=\rho^{\left|S\right|}\prod_{i\in
S}\chi_{i}^{p}\left(y_{i}\right)=\rho^{\left|S\right|}\chi_{S}\left(y\right).$

Combining (3.2) with (3.3), we complete the proof. ∎

######  Claim 3.7.

Let $x,y$ be elements of $\left\\{0,1\right\\}^{n},$ let
$p>q\in\left(0,1\right),$ and let
$\rho=\sqrt{\frac{q\left(1-p\right)}{p\left(1-q\right)}}.$ Then

(3.4) $\mathbb{E}_{\mathbf{x},\mathbf{y}\sim
D\left(q,p\right)|\,\mathbf{y}=y}\left[\chi_{i}^{q}\left(\mathbf{x}_{i}\right)\right]=\rho\chi_{i}^{p}\left(y_{i}\right),$

and

(3.5) $\mathbb{E}_{\mathbf{x},\mathbf{y}\sim
D\left(q,p\right)|\,\mathbf{x}=x}\left[\chi_{i}^{p}\left(\mathbf{y}_{i}\right)\right]=\rho\chi_{i}^{q}\left(x_{i}\right).$

###### Proof.

Since the functions $\chi_{i}^{q},\chi_{i}^{p}$ depend only on the $i$th
coordinate we may assume that $n=1$, and we shall write
$\chi^{p}=\chi_{1}^{p}$ as well as $\chi^{q}=\chi_{1}^{q}$ for brevity. We
shall start by showing (3.4), and the proof of (3.5) will be similar. Let
$h\in L^{2}\left(\left\\{0,1\right\\}^{n},\mu_{p}\right)$ be the map

$y\mapsto\mathbb{E}_{\mathbf{x},\mathbf{y}\sim
D\left(q,p\right)|\,\mathbf{y=}y}\left[\chi^{q}\left(\mathbf{x}\right)\right].$

Note the space $L^{2}\left(\left\\{0,1\right\\},\mu_{p}\right)$ is a linear
space of dimension $2$. We shall show that $h=\rho\chi^{p}$ by showing that
there are two independent linear functionals on the space
$L^{2}\left(\left\\{0,1\right\\},\mu_{p}\right)$ that agree on the functions
$h$ and $\rho\chi_{p}$. Namely, the first functional is the functional of
evaluating at $0$, and the second functional is the expectation according to
the $p$-biased distribution. Indeed, we may use the fact that elements
$\boldsymbol{x,y}\sim D\left(q,p\right)$ satisfy
$\boldsymbol{x}_{i}\leq\boldsymbol{y}_{i}$ with probability $1$ to obtain:

$\mathbb{E}_{\mathbf{x},\mathbf{y}\sim\left(\left\\{0,1\right\\},D\left(q,p\right)\right)|\,\mathbf{y}=0}\left[\chi^{q}\left(\mathbf{x}\right)\right]=\chi^{q}\left(0\right)=\sqrt{\frac{q}{1-q}}=\rho\sqrt{\frac{p}{1-p}}=\rho\chi^{p}\left(0\right).$

On the other hand,

$\displaystyle\mathbb{E}_{\mathbf{z}\sim\mu_{p}}\left[h\left(\mathbf{z}\right)\right]$
$\displaystyle=\mathbb{E}_{\mathbf{z}\sim\mu_{p}}\left[\mathbb{E}_{\mathbf{x},\mathbf{y}\sim
D\left(q,p\right)|\,\mathbf{y=\mathbf{z}}}\left[\chi^{q}\left(\mathbf{x}\right)\right]\right]$
$\displaystyle=\mathbb{E}_{\mathbf{x},\mathbf{y}\sim
D\left(q,p\right)}\left[\chi^{q}\left(\mathbf{x}\right)\right]=\mathbb{E}_{\mathbf{x}\sim\mu_{q}}\left[\chi_{q}\left(\mathbf{x}\right)\right]=0$
$\displaystyle=\mathbb{E}_{\mathbf{z}\sim\mu_{p}}\left[\rho\chi_{p}\left(\boldsymbol{\boldsymbol{z}}\right)\right].$

Since the expectation functional and the evaluating by 0 functionals are
independent, and since the space
$L^{2}\left(\left\\{0,1\right\\},\mu_{p}\right)$ is of dimension 2, we obtain
$h=\rho\chi_{p}$. This completes the proof of (3.4).

We prove (3.5) in a similar fashion. Define $h\in
L^{2}\left(\left\\{0,1\right\\},\mu_{q}\right)$ by

$x\mapsto\mathbb{E}_{\mathbf{x},\mathbf{y}\sim
D\left(q,p\right)|\,\mathbf{x}=x}\left[\chi^{p}\left(\mathbf{y}\right)\right].$

Similarly to the proof of (3.4), it is enough to prove the identities

$\mathbb{E}_{\mathbf{z}\sim\mu_{q}}\left(h\right)=0,h\left(1\right)=\rho\chi_{q}\left(1\right).$

To prove the former, note that

$\mathbb{E}_{\mathbf{z}\sim\mu_{q}}\left(h\left(\mathbf{z}\right)\right)=\mathbb{E}_{\mathbf{z}\sim\mu_{q}}\left[\mathbb{E}_{\mathbf{x},\mathbf{y}\sim
D\left(q,p\right)|\,\mathbf{x}=\mathbf{z}}\left[\chi^{p}\left(\mathbf{y}\right)\right]\right]=\mathbb{E}_{\mathbf{x},\mathbf{y}\sim
D\left(q,p\right)}\left[\chi^{p}\left(\mathbf{y}\right)\right]=0.$

To prove the latter, note that

$h\left(1\right)=\mathbb{E}_{\mathbf{x},\mathbf{y}\sim
D\left(q,p\right)|\,\mathbf{x}=1}\left[\chi^{p}\left(\mathbf{y}\right)\right]=\chi_{p}\left(1\right)=\rho\chi_{q}\left(1\right).$

∎

###  3.3. Fourier regularity

We shall say that a function $f\colon\left\\{0,1\right\\}^{n}\to\mathbb{R}$ is
$\left(r,\delta,\mu_{p}\right)$-_Fourier regular_ if
$\left|\hat{f}\left(S\right)\right|<\delta$ for each $0<\left|S\right|\leq r$.
It is easy to see (see O’Donnell [53, Chapter 7]) that any
$\left(r,\delta,\mu_{p}\right)$-regular function is
$\left(r,\delta,\mu_{p}\right)$-Fourier regular, and on the converse any
$\left(r,\delta,\mu_{p}\right)$-Fourier regular function is
$\left(r,2^{r}\delta,\mu_{p}\right)$-regular. So in a sense these notions are
equivalent.

######  Example 3.8.

Let $f\colon\left\\{0,1\right\\}^{n}\to\left[0,1\right]$ be a transitive
symmetric function. Then $f$ is
$\left(r,\sqrt{\frac{r}{n}},\mu_{p}\right)$-Fourier regular for any $r$ and
$p$. Indeed, let $S\in\binom{\left[n\right]}{r},$ then the fact that $f$ is
transitive symmetric implies that there exist distinct $r$-subsets of
$\left[n\right]$, $S_{1},\ldots,S_{\left\lceil\frac{n}{r}\right\rceil}$, such
that $\hat{f}\left(S_{i}\right)=\hat{f}\left(S\right)$ for each $i$. By
Parseval’s identity, we have

$1\geq\|f\|_{\mu_{p}}^{2}\geq\sum_{i=1}^{\left\lceil\frac{n}{r}\right\rceil}\hat{f}\left(S_{i}\right)^{2}=\left\lceil\frac{n}{r}\right\rceil\hat{f}\left(S\right)^{2}.$

After rearranging, we obtain that $f$ is
$\left(r,2^{r}\sqrt{\frac{r}{n}},\mu_{p}\right)$-Fourier regular, so it is in
fact $\left(r,\delta,\mu_{p}\right)$-Fourier regular, provided that
$n>\frac{4^{r}}{\delta^{2}}$.

###  3.4. The noisy influences

Let $f\in L^{2}\left(\left\\{0,1\right\\}^{n},\mu_{p}\right)$ be a function.
The noise stability of $f$ is defined by

$\mathrm{Stab}_{\rho,p}\left(f\right):=\left\langle
T_{\rho}\left(f\right),f\right\rangle_{\mu_{p}}=\underset{\mathbf{x}\sim\mu_{p},\mathbf{y}\sim
N_{\rho,p}\left(x\right)}{\mathbb{E}}\left[f\left(\mathbf{x}\right)f\left(\mathbf{y}\right)\right].$

By Fact 3.5, and by Parseval’s identity, we have

(3.6)
$\mathrm{Stab}_{\rho,p}\left(f\right)=\sum_{S\subseteq\left[n\right]}\rho^{\left|S\right|}\hat{f}\left(S\right)^{2},$

where $\hat{f}\left(S\right)$ are the Fourier coefficients of $f$ with respect
to the $p$-biased distribution.

The $\left(\rho,\mu_{p}\right)$-noisy influences of $f$ are defined by

$\mathrm{Inf}_{i}^{\left(\rho,p\right)}\left[f\right]:=\mathrm{Stab}_{\rho,p}\left[\left(f-A_{\left\\{i\right\\}}\left[f\right]\right)\right].$

By Fact 3.2 and by (3.6) we have

(3.7) $\mathrm{Inf}_{i}^{\left(\rho,p\right)}\left[f\right]=\sum_{S\ni
i}\rho^{\left|S\right|}\hat{f}\left(S\right)^{2}.$

######  Definition 3.9.

Let $\delta>0,\rho,p\in\left[0,1\right].$ A function
$f\colon\left\\{0,1\right\\}^{n}\to\mathbb{R}$ is said to have
$\left(\rho,\delta,\mu_{p}\right)$-small noisy influences if
$\mathrm{Inf}_{i}^{\left(\rho,p\right)}\left[f\right]<\delta$ for every
$i\in\left[n\right].$

###  3.5. Regularity lemmas we use

We shall make use of the following regularity lemma presented by Jones [40].

######  Theorem 3.10.

For each $\epsilon>0$ there exists $j\in\mathbb{N}$ such that the following
holds. Let $p\in\left(\epsilon,1-\epsilon\right)$ and let $f\in
L^{2}\left(\left\\{0,1\right\\},\mu_{p}\right)$ be a function. Then there
exists a set $J$ of size at most $j$, such that if we choose
$\mathbf{x}\sim\left(\left\\{0,1\right\\}^{J},\mu_{p}\right)$, then the
functions $f_{J\to\mathbf{x}}$ has
$\left(1-\epsilon,\epsilon,\mu_{p}\right)$-small noisy influences with
probability at least $1-\epsilon.$

######  Remark 3.11.

Jones [40] proved Theorem 3.10 only for the case where $p=\frac{1}{2}.$
However, as in most of the results in the area, their proof can be extended
verbatim to the $p$-biased distribution, for any $p$ bounded away from 0 and
1.

We also make use of the following regularity lemma of [17].

######  Theorem 3.12 ( [17, Theorem 1.7]).

For each $\delta,\epsilon>0$, there exists $j\in\mathbb{N}$, such that the
following holds. Let $\delta<\frac{k}{n}<1-\delta,$ and let
$\mathcal{F}\subseteq\binom{\left[n\right]}{k}$ be a family. Then there exists
a set $J$ of size at most $j$ and a family
$\mathcal{G}\subseteq\mathcal{P}\left(J\right)$, such that:

  1. (1)

We have
$\mu\left(\mathcal{F}\setminus\left\langle\mathcal{G}\right\rangle\right)<\epsilon.$

  2. (2)

For each $B\in\mathcal{G}$ the family $\mathcal{F}_{J}^{B}$ is
$\left(\left\lceil\frac{1}{\delta}\right\rceil,\delta\right)$-regular and
$\mu\left(\mathcal{F}_{J}^{B}\right)>\frac{\epsilon}{2}$.

###  3.6. Functions on Gaussian spaces

Let $\gamma$ be the standard normal probability distribution
$N\left(0,1\right)$ on $\mathbb{R}$. Abusing notation, we will also use
$\gamma$ to denote the product normal probability distribution
$N\left(0,1\right)^{n}$ on $\mathbb{R}^{n}.$ We shall denote by
$L^{2}\left(\mathbb{R}^{n},\gamma\right)$ the space of functions
$f\colon\mathbb{R}^{n}\to\mathbb{R}$, such that
$\|f\|_{\gamma}:=\mathbb{E}_{\gamma}\left[f^{2}\right]<\infty$. This space is
equipped with the inner product

$\left\langle
f,g\right\rangle=\mathbb{E}_{\gamma}\left[fg\right]=\int_{\mathbb{R}^{n}}f\left(x\right)g\left(x\right)\gamma\left(x\right)dx.$

The operator $\mathsf{T}_{\rho}$ on the space
$\left(\mathbb{R}^{n},N\left(0,1\right)\right)$, also known as the _Ornstein-
Uhlenbeck_ _operator_ , is defined as follows.

######  Definition 3.13.

Let $\rho\in\left(0,1\right)$, and let $x\in\mathbb{R}^{n}$, the $\rho$_-noisy
distribution_ of $x$ is the distribution $N_{\rho,\gamma}\left(x\right)$,
where we choose $\mathbf{y}$ by setting each coordinate $\mathbf{y}_{i}$
independently to be $\rho x_{i}+\sqrt{1-\rho^{2}}\mathbf{z}_{i}$, where
$\mathbf{z}$ is a new independent $\gamma$-distributed element of
$\mathbb{R}$. The _noise operator_ $\mathsf{T}_{\rho}$ on the space
$L^{2}\left(\mathbb{R}^{n},\gamma\right)$ is the operator that associates to
each $f\in L^{2}\left(\mathbb{R}^{n},\gamma\right)$ the function

$\mathsf{T}_{\rho}\left[f\right]\left(x\right):=\underset{\mathbf{y}\sim
N_{\rho,\gamma}\left(x\right)}{\mathbb{E}}\left[f\left(\mathbf{y}\right)\right].$

######  Remark 3.14.

The analogy between the distribution $N_{\rho,p}$, and $N_{\rho,\gamma}$ stems
from the fact if we choose $\mathbf{x}\sim\gamma,$ and $\mathbf{y}\sim
N_{\rho,\gamma}\left(\mathbf{x}\right),$ then we have the following
properties.

  * •

$\mathbf{x},\mathbf{y}\sim\gamma.$

  * •

$\forall i\,:\mathbb{E}\left[\mathbf{x}_{i}\mathbf{y}_{i}\right]=\rho.$

  * •

The $\mathbb{R}^{2}$-valued random
variables$\left(\mathbf{x}_{i},\mathbf{y}_{i}\right)$ are independent of each
other.

These properties are similarly satisfied when we choose
$\mathbf{x\sim}\mu_{p}$ and then choose $\mathbf{y}\sim
N_{\rho,p}\left(\mathbf{x}\right).$

For $\mu\in\left(0,1\right)$, we let
$F_{\mu}\colon\mathbb{R}\to\left[0,1\right]$ denote the function
$\mathbf{1}_{x<t}$, where $t$ is the only real number for which
$\mathbb{E}_{\boldsymbol{x}\sim\gamma}\left[F_{\mu}\left(\boldsymbol{x}\right)\right]=\mu$.
The following theorem was proved by Borell [9]. It says that if $f,g\in
L^{2}\left(\mathbb{R}^{n},\gamma\right)$ are functions that take their value
in the interval $\left[0,1\right]$ that satisfy
$\mathbb{E}\left[f\right]=\mu,\mathbb{E}\left[g\right]=\nu$, then the maximal
possible value of the quantity
$\left\langle\mathsf{T}_{\rho}\left[f\right],g\right\rangle$ is obtained when
$f=F_{\mu}$ and $g=F_{\nu}.$

######  Theorem 3.15 (Borell 1985).

Let $f,g\in L^{2}\left(\mathbb{R}^{n},\gamma\right)$ be two
$\left[0,1\right]$-valued functions. Then

$\left\langle\mathsf{T}_{\rho}\left[f\right],g\right\rangle\leq\left\langle\mathsf{T}_{\rho}\left[F_{\mathbb{E}\left[f\right]}\right],F_{\mathbb{E}\left[g\right]}\right\rangle.$

We denote
$\left\langle\mathsf{T}_{\rho}\left[F_{\mu}\right],F_{\nu}\right\rangle$ by
$\Lambda_{\rho}\left(\mu,\nu\right).$ Note that we trivially have

$\Lambda_{\rho}\left(\mu,\nu\right):=\left\langle\mathsf{T}_{\rho}\left[F_{\mu}\right],F_{\nu}\right\rangle\leq\left\langle\mathsf{T}_{\rho}\left[F_{\mu}\right],1\right\rangle=\mu.$

We will be interested in the case where $\mu$ is bounded away from $0$ and
$\nu,\rho$ are bounded away from 1. For such parameters,
$\Lambda_{\rho}\left(\mu,\nu\right)$ admits a slightly stronger upper bound.

######  Lemma 3.16.

For each $\epsilon>0$, there exists $\delta>0$, such that the following holds.
Let $\mu\in\left(\epsilon,1\right)$ and let
$\rho,\nu\in\left(0,1-\epsilon\right)$. Then

$\Lambda_{\rho}\left(\mu,\nu\right)\leq\mu-\delta.$

###### Proof.

Let
$\delta=\left\langle\mathsf{T}_{1-\epsilon}\left[F_{\epsilon}\right],1-F_{1-\epsilon}\right\rangle>0$.
We have

$\displaystyle\Lambda_{\rho}\left(\mu,\nu\right)$
$\displaystyle=\left\langle\mathsf{T}_{\rho}\left[F_{\mu}\right],F_{\nu}\right\rangle=\left\langle\mathsf{T}_{\rho}\left[F_{\mu}\right],1\right\rangle+\left\langle\mathsf{T}_{\rho}\left[F_{\mu}\right],F_{\nu}-1\right\rangle$
$\displaystyle=\mu-\left\langle\mathsf{T}_{\rho}\left[F_{\mu}\right],1-F_{\nu}\right\rangle\leq\mu-\left\langle\mathsf{T}_{1-\epsilon}\left[F_{\epsilon}\right],1-F_{1-\epsilon}\right\rangle$
$\displaystyle=\mu-\delta.$

∎

We shall also use the following estimate on $\Lambda_{\rho}.$

######  Lemma 3.17 ([49, Lemma 2.5]).

Let $\rho_{1}<\rho_{2}.$ Then

$\left|\Lambda_{\rho_{1}}\left(\mu,\nu\right)-\Lambda_{\rho_{2}}\left(\mu,\nu\right)\right|\leq\frac{10\left(\rho_{2}-\rho_{1}\right)}{1-\rho_{2}}.$

We would also like to remark that we have the following Fourier formula for
$\mathsf{T}_{\rho}\left[f\right]$, in the case where $f$ is a multilinear
polynomial:

######  Fact 3.18.

Let $f=\sum_{S\subseteq\left[n\right]}a_{i}\prod_{i\in S}z_{i}$ be a
multilinear polynomial. Then

$\mathsf{T}_{\rho}\left[f\right]=\sum_{S\subseteq\left[n\right]}a_{i}\rho^{\left|S\right|}\prod_{i\in
S}z_{i}.$

###  3.7. The invariance principle

The invariance principle is a powerful theorem due to Mossel, O’Donnell, and
Oleszkiewicz [50] that relates the distribution of a ‘smooth’ function
$f\colon\left\\{0,1\right\\}^{n}\to\mathbb{R}$ with the distribution of
functions on Gaussian spaces. To state a corollary of it that we shall apply,
we need to introduce some terminology.

Let $f\colon\mathbb{R}^{n}\to\mathbb{R}$ be a function. Following [16], we
define the function $\mathrm{Chop}\left(f\right)$ by setting

$\mathrm{Chop}\left(f\right)\left(x\right)=\begin{cases}f\left(x\right)&\mbox{if
}f\left(x\right)\in\left[0,1\right]\\\ 0&\mbox{if }f\left(x\right)\leq 0\\\
1&\mbox{if }f\left(x\right)\geq 1\end{cases}.$

We shall also need the following definition.

######  Definition 3.19.

Let $f\in L^{2}\left(\left\\{0,1\right\\}^{n},\mu_{p}\right)$ be some function
with Fourier expansion

$f=\sum_{S\subseteq\left[n\right]}\hat{f}\left(S\right)\chi_{S}^{p}.$

We let the Gaussian analogue of it be the multilinear polynomial $\tilde{f}\in
L^{2}\left(\mathbb{R}^{n},\gamma\right)$ defined by

$\tilde{f}\left(z\right)=\sum_{S\subseteq\left[n\right]}\hat{f}\left(S\right)\prod_{i\in
S}z_{i}.$

Roughly speaking, the invariance principle says that if the function $f$ is
sufficiently ‘smooth’, then the distribution of $f\left(\mathbf{x}\right)$,
where $\mathbf{x}\sim\left(\left\\{0,1\right\\}^{n},\mu_{p}\right)$ is
somewhat similar to the distribution of $\tilde{f}\left(\mathbf{y}\right)$,
where $\mathbf{y}\sim\left(\mathbb{R}^{n},\gamma\right)$ is a Gaussian random
variable. The smoothness requirement that we need is the following. Let
$\delta,\epsilon>0$, we shall say that a function $f\in
L^{2}\left(\left\\{0,1\right\\}^{n},\mu_{p}\right)$ is
$\left(\delta,1-\epsilon,\mu_{p}\right)$-smooth if
$\mathrm{Inf}_{i}^{p}\left[f\right]<\delta$ for each $i\in\left[n\right],$ and
$\left|\hat{f}\left(S\right)\right|\leq\left(1-\epsilon\right)^{\left|S\right|}$
for each $S\subseteq\left[n\right].$

As a corollary of the invariance principle, one can show (see [16, Theorem
3.8] or [50, Theorem 3.18]) the following corollary of it. It says that if $f$
is a ‘sufficiently smooth’ function that takes its value in the interval
$\left[0,1\right]$, then $\tilde{f}$ is concentrated on $\left[0,1\right]$ as
well, in the sense that $\|\tilde{f}-\mathrm{Chop}\left(\tilde{f}\right)\|$ is
small.

######  Corollary 3.20 (Corollary of the invariance principle).

For each $\epsilon,\eta>0$, there exists $\delta>0$, such that the following
holds. Let $p\in\left(\epsilon,1-\epsilon\right)$, let
$f\colon\left\\{0,1\right\\}^{n}\to\left[0,1\right]$ be a function, and
suppose that $f$ is $\left(\delta,1-\eta,\mu_{p}\right)$-smooth. Then

$\|\tilde{f}-\mathrm{Chop}\left(\tilde{f}\right)\|<\epsilon.$

##  4\. Counting lemma for the $\rho$-noisy influence regularity lemma

In this section we prove our version of the majority is stablest theorem that
would serve as a counting lemma in the proof of Theorem 1.7. The proof is a
straightforward adaptation of the proof by Mossel, O’Donnell, and Oleszkiewicz
[50] of the Majority is Stablest Theorem, and its generalizations by Mossel
[48].

######  Proposition 4.1.

For each $\epsilon>0,$ there exists $\delta>0,$ such that the following holds.
Let $\rho\in\left(0,1-\epsilon\right),$ and suppose that $p-q>\epsilon.$ Let
$f,g\colon\left\\{0,1\right\\}^{n}\to\left[0,1\right]$ be some functions, and
suppose that

$\max_{i\in\left[n\right]}\min\left\\{\mathrm{Inf}_{i}^{\left(1-\delta,q\right)}\left[f\right],\mathrm{Inf}_{i}^{\left(1-\delta,q\right)}\left[g\right]\right\\}<\delta.$

Then

(4.1)
$\sum_{S\subseteq\left[n\right]}\rho^{\left|S\right|}\hat{f}\left(S\right)\hat{g}\left(S\right)<\Lambda_{\rho}\left(\mu_{q}\left(f\right),\mu_{p}\left(g\right)\right)+\epsilon.$

We divide the proof into three parts. In each of these parts we prove that if
$f,g$ satisfy certain requirement then (4.1) holds. The hypothesis will be the
strongest in the first part, weaker on the second part, and the weakest on the
third part. The parts are as follows.

  1. (1)

We start by showing that (4.1) holds if $f$ is assumed to be
$\left(\delta,1-\epsilon,\mu_{q}\right)$-smooth, and $g$ is assumed to be
$\left(\delta,1-\epsilon,\mu_{p}\right)$-smooth.

  2. (2)

We then prove (4.1) in the case where $f$ and $g$ are assumed to satisfy

$\max_{i\in\left[n\right]}\max\left\\{\mathrm{Inf}_{i}^{\left(1-\delta,q\right)}\left[f\right],\mathrm{Inf}_{i}^{\left(1-\delta,q\right)}\left[g\right]\right\\}<\delta.$

  3. (3)

Finally, we shall complete the proof of the proposition by proving (4.1) in
the case where $f$ and $g$ are assumed to satisfy

$\max_{i\in\left[n\right]}\min\left\\{\mathrm{Inf}_{i}^{\left(1-\delta,q\right)}\left[f\right],\mathrm{Inf}_{i}^{\left(1-\delta,q\right)}\left[g\right]\right\\}<\delta.$

###  4.1. Proof of the proposition in the case where $f$ is
$\left(\delta,1-\epsilon,\mu_{q}\right)$-smooth and $g$ is
$\left(\delta,1-\epsilon,\mu_{p}\right)$-smooth.

The idea of the proof is to convert the statement on $f$ and $g$ to a
corresponding statement about their Gaussian analogues $\tilde{f}$ and
$\tilde{g}$, and then to prove the corresponding statement by applying
Borrel’s Theorem. A difficulty that arises in this approach is the fact that
Borrel’s Theorem may be applied only on functions that take their values in
the interval $\left[0,1\right],$ while the functions $\tilde{f}$ and
$\tilde{g}$ may take their values outside of this interval. However, we
overcome this difficulty by noting that Borrel’s theorem may be applied on the
functions $\mathrm{Chop}\left(\tilde{f}\right)$ and
$\mathrm{Chop}\left(\tilde{g}\right),$ and by observing that Corollary 3.20
shows that $\tilde{f}$ and $\tilde{g}$ are approximated by the functions
$\mathrm{Chop}\left(\tilde{f}\right)$ and
$\mathrm{Chop}\left(\tilde{g}\right).$ The technical details are below.

######  Lemma 4.2.

For each $\epsilon>0,$ there exists $\delta>0$ such that the following holds.
Let $q,p\in\left(\epsilon,1-\epsilon\right)$, let $\rho\in\left(0,1\right),$
let $f=\sum\hat{f}\left(S\right)\chi_{S}^{q}$ be a
$\left(\delta,1-\epsilon,\mu_{q}\right)$-smooth function, and let
$g=\sum\hat{g}\left(S\right)\chi_{S}^{p}$ be a
$\left(\delta,1-\epsilon,\mu_{p}\right)$-smooth function. Then

$\sum_{S\subseteq\left[n\right]}\rho^{\left|S\right|}\hat{f}\left(S\right)\hat{g}\left(S\right)<\Lambda_{\rho}\left(\mu_{q}\left(f\right),\mu_{p}\left(g\right)\right)+\epsilon.$

###### Proof.

Let $\epsilon>0$ and suppose that $\delta=\delta\left(\epsilon\right)$ is
sufficiently small. Let $\tilde{f}$ be the Gaussian analogue of $f$ and let
$\tilde{g}$ be the Gaussian analogue of $g.$ By Fact 3.18 we have

$\sum_{S\subseteq\left[n\right]}\rho^{\left|S\right|}\hat{f}\left(S\right)\hat{g}\left(S\right)=\left\langle\mathsf{T}_{\rho}\tilde{f},\tilde{g}\right\rangle.$

So our goal is to show that

(4.2)
$\left\langle\mathsf{T}_{\rho}\tilde{f},\tilde{g}\right\rangle-\Lambda_{\rho}\left(\mu_{q}\left(f\right),\mu_{p}\left(g\right)\right)<\epsilon,$

provided that $\delta$ is sufficiently small. Let

$\epsilon_{1}:=\left|\left\langle\mathsf{T}_{\rho}\tilde{f},\tilde{g}\right\rangle-\left\langle\mathsf{T}_{\rho}\left(\mathrm{Chop}\left(\tilde{f}\right)\right),\mathrm{Chop}\left(\tilde{g}\right)\right\rangle\right|,$

and let

$\displaystyle\epsilon_{2}$
$\displaystyle=\left|\Lambda_{\rho}\left(\mathbb{E}\left(\mathrm{Chop}\left(\tilde{f}\right)\right),\mathbb{E}\left(\mathrm{Chop}\left(\tilde{g}\right)\right)\right)-\Lambda_{\rho}\left(\mathbb{E}\left[\tilde{f}\right],\mathbb{E}\left[\tilde{g}\right]\right)\right|$
$\displaystyle=\left|\Lambda_{\rho}\left(\mathbb{E}\left(\mathrm{Chop}\left(\tilde{f}\right)\right),\mathbb{E}\left(\mathrm{Chop}\left(\tilde{g}\right)\right)\right)-\Lambda_{\rho}\left(\mu_{q}\left(f\right),\mu_{p}\left(g\right)\right)\right|.$

Applying Borrel’s Theorem on the functions
$\mathrm{Chop}\left(\tilde{f}\right),\mathrm{Chop}\left(\tilde{g}\right),$ we
obtain

(4.3)
$\left\langle\mathsf{T}_{\rho}\mathrm{Chop}\left(\tilde{f}\right),\mathrm{Chop}\left(\tilde{g}\right)\right\rangle\leq\Lambda_{\rho}\left(\mathbb{E}\left(\mathrm{Chop}\left(\tilde{f}\right)\right),\mathbb{E}\left(\mathrm{Chop}\left(\tilde{g}\right)\right)\right),$

and hence

$\left\langle\mathsf{T}_{\rho}\tilde{f},\tilde{g}\right\rangle\leq\Lambda_{\rho}\left(\mu_{q}\left(f\right),\mu_{p}\left(g\right)\right)+\epsilon_{1}+\epsilon_{2}.$

So to complete the proof we need to show that
$\epsilon_{1}+\epsilon_{2}<\epsilon$ provided that $\delta$ is sufficiently
small.

######  Claim 4.3.

Provided that $\delta$ is sufficiently small we have
$\epsilon_{1}<\epsilon/2$.

###### Proof.

Note that it follows from Jensen’s inequality that the operator
$\mathsf{T}_{\rho}$ on the space $L^{2}\left(\mathbb{R}^{n},\gamma\right)$ is
a contraction. Indeed, for each function $h\in
L^{2}\left(\mathbb{R}^{n},\gamma\right)$ we have

$\displaystyle\left\|\mathsf{T}_{\rho}\left(h\right)\right\|^{2}$
$\displaystyle=\mathbb{E}_{\boldsymbol{x}\sim\left(\mathbb{R}^{n},\gamma\right)}\left[\left(\mathbb{E}_{\boldsymbol{y}\sim
N_{\rho}\left(x\right)}\left[h\left(\boldsymbol{y}\right)\right]\right)^{2}\right]$
$\displaystyle\leq\left(\mathbb{E}_{\boldsymbol{x}\sim\left(\mathbb{R}^{n},\gamma\right)}\left[\mathbb{E}_{\boldsymbol{y}\sim
N_{\rho}\left(x\right)}\left[h\left(\boldsymbol{y}\right)\right]\right]\right)^{2}$
$\displaystyle=\left(\mathbb{E}_{\boldsymbol{y}\sim\left(\mathbb{R}^{n},\gamma\right)}\left[h\left(\boldsymbol{y}\right)\right]\right)^{2}$
$\displaystyle=\|h\|^{2}.$

Moreover, we note that by Parseval
$\|\tilde{g}\|=\sum\hat{g}\left(S\right)^{2}=\sqrt{\mathbb{E}_{\mathbf{y\sim\mu}_{p}}\left[g\left(\boldsymbol{y}\right)^{2}\right]}\leq
1.$ Therefore,

$\displaystyle\epsilon_{1}$
$\displaystyle=\left|\left\langle\mathsf{T}_{\rho}\tilde{f},\tilde{g}\right\rangle-\left\langle\mathsf{T}_{\rho}\left(\mathrm{Chop}\left(\tilde{f}\right)\right),\mathrm{Chop}\left(\tilde{g}\right)\right\rangle\right|$
$\displaystyle\leq\left|\left\langle\mathsf{T}_{\rho}\tilde{f},\tilde{g}\right\rangle-\left\langle\mathsf{T}_{\rho}\left(\mathrm{Chop}\left(\tilde{f}\right)\right),\tilde{g}\right\rangle\right|$
$\displaystyle+\left|\left\langle\mathsf{T}_{\rho}\left(\mathrm{Chop}\left(\tilde{f}\right)\right),\tilde{g}\right\rangle-\left\langle\mathsf{T}_{\rho}\left(\mathrm{Chop}\left(\tilde{f}\right)\right),\mathrm{Chop}\left(\tilde{g}\right)\right\rangle\right|$
$\displaystyle(\text{By Cauchy-Schwarz})$
$\displaystyle\leq\left\|\mathsf{T}_{\rho}\left(\tilde{f}-\mathrm{Chop}\left(\tilde{f}\right)\right)\right\|\left\|\tilde{g}\right\|+\left\|\mathsf{T}_{\rho}\left(\mathrm{Chop}\left(\tilde{f}\right)\right)\right\|\left\|\tilde{g}-\mathrm{Chop}\left(\tilde{g}\right)\right\|$
$\displaystyle(\text{Since }\mathsf{T}_{\rho}\text{ is a contraction)}$
$\displaystyle\leq\left\|\tilde{f}-\mathrm{Chop}\left(\tilde{f}\right)\right\|\left\|\tilde{g}\right\|+\left\|\mathrm{Chop}\left(\tilde{f}\right)\right\|\left\|\tilde{g}-\mathrm{Chop}\left(\tilde{g}\right)\right\|$
$\displaystyle\leq\left\|\tilde{f}-\mathrm{Chop}\left(\tilde{f}\right)\right\|+\left\|\tilde{g}-\mathrm{Chop}\left(\tilde{g}\right)\right\|.$

We may now apply Corollary 3.20 with $\epsilon$ replacing $\eta$ and
$\frac{\epsilon}{4}$ replacing $\epsilon$, to obtain that

(4.4)
$\left\|\tilde{f}-\mathrm{Chop}\left(\tilde{f}\right)\right\|+\left\|\tilde{g}-\mathrm{Chop}\left(\tilde{g}\right)\right\|<\frac{\epsilon}{2},$

provided that $\delta$ is sufficiently small. This completes the proof of the
claim. ∎

To finish the proof of the lemma it remains to prove the following claim.

######  Claim 4.4.

Provided that $\delta$ is sufficiently small, we have
$\epsilon_{2}<\epsilon/2.$

Choose $X\sim\left(\mathbb{R},\gamma\right),Y\sim N_{\rho}\left(X\right).$
Then
$\Lambda_{\rho}\left(\mathbb{E}\left[\tilde{f}\right],\mathbb{E}\left[\tilde{g}\right]\right)$
is the probability of the event $X<t_{1},Y<t_{2}$ for the proper values of
$t_{1},t_{2}.$ Similarly,
$\Lambda_{\rho}\left(\mathbb{E}\left[\mathrm{Chop}\left(\tilde{f}\right)\right],\mathbb{E}\left[\mathrm{Chop}\left(\tilde{g}\right)\right]\right)$
is the probability of the event $X<t_{3},Y<t_{4}$ for the proper values of
$t_{3},t_{4}.$ These events differ either if $X$ is in the interval whose
endpoints are $t_{1},t_{3}$ or if $Y$ is in the interval whose endpoints are
$t_{2},t_{4}.$ The Probability of the former event is
$\left|\mathbb{E}\left[\mathrm{Chop}\left(\tilde{f}\right)\right]-\mathbb{E}\left[\tilde{f}\right]\right|$,
and the probability of the latter event is
$|\mathbb{E}\left[\mathrm{Chop}\left(\tilde{g}\right)\right]-\mathbb{E}\left[\tilde{g}\right]|.$
Therefore, a union bound implies that:

$\displaystyle\epsilon_{2}$
$\displaystyle=\left|\Lambda_{\rho}\left(\mathbb{E}\left[\tilde{f}\right],\mathbb{E}\left[\tilde{g}\right]\right)-\Lambda_{\rho}\left(\mathbb{E}\left[\mathrm{Chop}\left(\tilde{f}\right)\right],\mathbb{E}\left[\mathrm{Chop}\left(\tilde{g}\right)\right]\right)\right|$
$\displaystyle\leq\left|\mathbb{E}\left[\mathrm{Chop}\left(\tilde{f}\right)\right]-\mathbb{E}\left[\tilde{f}\right]\right|+|\mathbb{E}\left[\mathrm{Chop}\left(\tilde{g}\right)\right]-\mathbb{E}\left[\tilde{g}\right]|$
$\displaystyle(\text{By Cauchy-Schwarz and \eqref{eq:chops are small}})$
$\displaystyle\leq\|\mathrm{Chop}\left(\tilde{f}\right)-\tilde{f}\|+\|\mathrm{Chop}\left(\tilde{g}\right)-\tilde{g}\|<\frac{\epsilon}{2}.$

∎

###  4.2. The case where $f,g$ have small noisy influences

We shall now prove a stronger version of Lemma 4.2, where we impose on $f,g$
the hypothesis

$\max_{i\in\left[n\right]}\max\left\\{\mathrm{Inf}_{i}^{\left(1-\delta,q\right)}\left[f\right],\mathrm{Inf}_{i}^{\left(1-\delta,p\right)}\left[g\right]\right\\}<\delta.$

######  Lemma 4.5.

For each $\epsilon>0,$ there exists $\delta>0$ such that the following holds.
Let $q,p\in\left(\epsilon,1-\epsilon\right)$, let $\rho\in\left(0,1\right)$,
let $f=\sum\hat{f}\left(S\right)\chi_{S}^{q}$ be a function and suppose that

$\max_{i\in\left[n\right]}\max\left\\{\mathrm{Inf}_{i}^{\left(1-\delta,q\right)}\left[f\right],\mathrm{Inf}_{i}^{\left(1-\delta,p\right)}\left[g\right]\right\\}<\delta.$

Then

$\sum_{S\subseteq\left[n\right]}\rho^{\left|S\right|}\hat{f}\left(S\right)\hat{g}\left(S\right)<\Lambda_{\rho}\left(\mu_{q}\left(f\right),\mu_{p}\left(g\right)\right)+\epsilon.$

###### Proof.

Let $\epsilon>0$, let $\delta_{1}=\delta_{1}\left(\epsilon\right)$ be
sufficiently small, and let $\delta=\delta\left(\delta_{1}\right)$ be
sufficiently small. Let
$f^{\prime}=\mathsf{T}_{q,1-\delta_{1}}\left(f\right),g^{\prime}=\mathsf{T}_{p,1-\delta_{1}}\left(g\right),$
$\rho^{\prime}=\frac{\rho}{\left(1-\delta_{1}\right)^{2}}.$

We assert that the functions $f^{\prime}$ is
$\left(\delta,1-\delta_{1},\mu_{q}\right)$-smooth and the function
$g^{\prime}$ is $\left(\delta,1-\delta_{1},\mu_{p}\right)$-smooth, provided
that $\delta$ is small enough. Indeed, the functions $f^{\prime}$ is
$\left(\delta,1-\delta_{1},\mu_{q}\right)$-smooth since:

$\mathrm{Inf}_{i}\left[f^{\prime}\right]=\mathrm{Inf}_{i}^{\left(1-\delta_{1},q\right)}\left[f\right]\leq\mathrm{Inf}_{i}^{\left(1-\delta,q\right)}\left[f\right]<\delta,$

provided that $\delta\leq\delta_{1},$ and

$\left|\hat{f^{\prime}}\left(S\right)\right|=\left|\left(1-\delta_{1}\right)^{\left|S\right|}\hat{f}\left(S\right)\right|\leq\left(1-\delta_{1}\right)^{\left|S\right|}.$

The function $g$ is $\left(\delta,1-\delta_{1},\mu_{p}\right)$-smooth for
similar reasons. Provided that $\delta$ is small enough, Lemma 4.2 implies
that

$\left\langle\mathsf{T}_{\rho}f,g\right\rangle=\left\langle\mathsf{T}_{\rho^{\prime}}f^{\prime},g^{\prime}\right\rangle\leq\Lambda_{\rho^{\prime}}\left(\mu_{q}\left(f^{\prime}\right),\mu_{p}\left(g^{\prime}\right)\right)+\delta_{1}=\Lambda_{\rho^{\prime}}\left(\mu_{q}\left(f\right),\mu_{p}\left(g\right)\right)+\delta_{1}.$

By Lemma 3.17 we have

$\Lambda_{\rho^{\prime}}\left(\mu_{q}\left(f\right),\mu_{p}\left(g\right)\right)<\Lambda_{\rho}\left(\mu_{q}\left(f\right),\mu_{p}\left(g\right)\right)+\epsilon-\delta_{1},$

provided that $\delta_{1}$ is sufficiently small. Hence

$\left\langle\mathsf{T}_{\rho}f,g\right\rangle\leq\Lambda_{\rho}\left(\mu_{q}\left(f\right),\mu_{p}\left(g\right)\right)+\epsilon.$

∎

###  4.3. Proof of Proposition 4.1

Finally, we shall replace the hypothesis

$\max_{i\in\left[n\right]}\max\left\\{\mathrm{Inf}_{i}^{\left(1-\delta,q\right)}\left[f\right],\mathrm{Inf}_{i}^{\left(1-\delta,p\right)}\left[g\right]\right\\}<\delta$

by the weaker hypothesis

$\max_{i\in\left[n\right]}\min\left\\{\mathrm{Inf}_{i}^{\left(1-\delta,q\right)}\left[f\right],\mathrm{Inf}_{i}^{\left(1-\delta,p\right)}\left[g\right]\right\\}<\delta.$

###### Proof.

Let $\epsilon>0$, let $\delta_{1}=\delta_{1}\left(\epsilon\right)$ be
sufficiently small, and let $\delta=\delta\left(\delta_{1}\right)$ be
sufficiently small. Let

$A_{1}=\left\\{i\in\left[n\right]:\,\mathrm{Inf}_{i}^{\left(1-\delta_{1},q\right)}\left[f\right]>\delta_{1}\right\\},\,\,\,A_{2}=\left\\{i\in\left[n\right]:\,\mathrm{Inf}_{i}^{\left(1-\delta_{1},q\right)}\left[g\right]>\delta_{1}\right\\},$

let $A=A_{1}\cup A_{2},$ and set $B=\left[n\right]\backslash A.$ Write
$f^{\prime}=\mathsf{A}_{A}\left(f\right),g^{\prime}=\mathsf{A}_{A}\left(g\right).$
We have

$\sum_{S\subseteq\left[n\right]}\rho^{\left|S\right|}\hat{f}\left(S\right)\hat{g}\left(S\right)=\sum_{S\subseteq
B}\rho^{\left|S\right|}\hat{f}\left(S\right)\hat{g}\left(S\right)+\sum_{S\cap
A\neq\varnothing}\rho^{\left|S\right|}\hat{f}\left(S\right)\hat{g}\left(S\right).$

We shall now bound
$\sum_{S\subseteq\left[n\right]}\rho^{\left|S\right|}\hat{f}\left(S\right)\hat{g}\left(S\right)$
by bounding each of the terms in the right hand side.

Upper bounding $\sum_{S\subseteq
B}\rho^{\left|S\right|}\hat{f}\left(S\right)\hat{g}\left(S\right)$

Since $f^{\prime},g^{\prime}$ satisfy the hypothesis of Lemma 4.5 (with
$\delta_{1}$ replacing $\delta$), we have

$\sum_{S\subseteq
B}\rho^{\left|S\right|}\hat{f}\left(S\right)\hat{g}\left(S\right)=\sum_{S\subseteq\left[n\right]}\rho^{\left|S\right|}\hat{f}^{\prime}\left(S\right)\hat{g^{\prime}}\left(S\right)\leq\Lambda_{\rho}\left(\mu_{q}\left(f^{\prime}\right),\mu_{p}\left(g^{\prime}\right)\right)+\frac{\epsilon}{2}=\Lambda_{\rho}\left(\mu_{q}\left(f\right),\mu_{p}\left(g\right)\right)+\frac{\epsilon}{2},$

provided that $\delta_{1}$ is small enough.

Upper bounding $\sum_{S\cap
A\neq\varnothing}\rho^{\left|S\right|}\hat{f}\left(S\right)\hat{g}\left(S\right).$

By Cauchy Schwarz, we have

$\displaystyle\sum_{S\cap
A\neq\varnothing}\rho^{\left|S\right|}\hat{f}\left(S\right)\hat{g}\left(S\right)$
$\displaystyle\leq\sum_{i\in A}\sum_{S\ni
i}\rho^{\left|S\right|}\left|\hat{f}\left(S\right)\hat{g}\left(S\right)\right|\leq\sum_{i\in
A}\sqrt{\sum_{S\ni
i}\rho^{\left|S\right|}\hat{f}\left(S\right)^{2}}\sqrt{\sum_{S\ni
i}\rho^{\left|S\right|}\hat{g}\left(S\right)^{2}}.$ $\displaystyle=\sum_{i\in
A}\sqrt{\mathrm{Inf}_{i}^{\left(\rho,q\right)}\left(f\right)}\sqrt{\mathrm{Inf}_{i}^{\left(\rho,p\right)}\left(g\right)}.$

Now note that

$\max\left\\{\mathrm{Inf}_{i}^{\left(\rho,q\right)}\left(f\right),\mathrm{Inf}_{i}^{\left(\rho,p\right)}\left(g\right)\right\\}\leq
1$

for any $i\in\left[n\right].$ Moreover, we have
$\mathrm{Inf}_{i}^{\left(\rho,q\right)}\left(f\right)\leq\mathrm{Inf}_{i}^{\left(1-\delta,q\right)}\left(f\right)$
and
$\mathrm{Inf}_{i}^{\left(\rho,p\right)}\left(f\right)\leq\mathrm{Inf}_{i}^{\left(1-\delta,p\right)}\left(f\right),$
provided that $\delta<1-\rho.$ The hypothesis implies that

$\max_{i\in\left[n\right]}\min\left\\{\mathrm{Inf}_{i}^{\left(1-\delta,q\right)}\left(f\right),\mathrm{Inf}_{i}^{\left(1-\delta,p\right)}\left(f\right)\right\\}\leq\delta.$

Therefore,

$\sum_{i\in
A}\sqrt{\mathrm{Inf}_{i}^{\left(\rho,q\right)}\left(f\right)}\sqrt{\mathrm{Inf}_{i}^{\left(\rho,p\right)}\left(g\right)}\leq\left|A\right|\sqrt{\delta}.$

So this completes the proof provided that
$\delta\leq\frac{\epsilon^{2}}{4\left|A\right|^{2}}$. We shall now complete
the proof by showing that $\left|A\right|=O_{\delta_{1}}\left(1\right).$

Upper bounding $\left|A\right|$

We show that $\left|A_{1}\right|=O_{\delta_{1}}\left(1\right),$ as the proof
that $\left|A_{2}\right|=O_{\delta_{1}}\left(1\right)$ is similar. Note that
the quantity
$\sum_{i=1}^{n}\mathrm{Inf}_{i}^{\left(1-\delta_{1},q\right)}\left(f\right)$
is on the one hand bounded from below by $\left|A_{1}\right|\delta_{1},$ and
on the other hand we have the following upper bound on it.

$\sum_{i=1}^{n}\mathrm{Inf}_{i}^{\left(q,1-\delta_{1}\right)}\left(f\right)=\sum_{S\subseteq\left[n\right]}\left(1-\delta_{1}\right)^{\left|S\right|}\left|S\right|\hat{f}\left(S\right)^{2}\leq\sum_{s=1}^{\infty}s\left(1-\delta_{1}\right)^{s}=O_{\delta_{1}}\left(1\right).$

Hence $\left|A_{1}\right|=O_{\delta_{1}}\left(1\right).$ This completes the
proof of the proposition. ∎

##  5\. Proof of the structural result on almost monotone functions

In this section we prove Theorem 2.5. We restate it for the convenience of the
reader.

######  Theorem.

For each $\epsilon>0$, there exists $j\in\mathbb{N},\delta>0$, such that the
following holds. Let $p,q$ be numbers in the interval
$\left(\epsilon,1-\epsilon\right)$ that satisfy $p-q>\epsilon$ and let
$f\colon\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$ be a
$\left(q,p,\delta\right)$-almost monotone function. Then there exists a
monotone $j$-junta $g$, such that

$\Pr_{\mathbf{x}\sim\mu_{q}}\left[f\left(\mathbf{x}\right)>g\left(\mathbf{x}\right)\right]<\epsilon\text{
and
}\Pr_{\mathbf{x}\sim\mu_{p}}\left[f\left(\mathbf{x}\right)<g\left(\mathbf{x}\right)\right]<\epsilon.$

We recall that the proof relies on the regularity method, with the regularity
lemma being Theorem 3.10 of [40], and with the corresponding counting lemma
being Proposition 4.1.

The regularity lemma allows us to decompose $f$ into functions
$\left\\{f_{J\to\mathbf{x}}\right\\}_{\mathbf{x}\in\left\\{0,1\right\\}^{J}}$,
such that for most of the parts the function $f_{J\to x}$ has small noisy
influences and a $q$-biased measure that is bounded away from $0$. We shall
then approximate $f$ by the ‘least’ monotone junta
$g\colon\left\\{0,1\right\\}^{J}\to\left\\{0,1\right\\}$ that takes the value
1 on all the the $x$, such that the function $f_{J\to x}$ has small noisy
influences. Here, by least we mean smallest with respect to the partial order:
$g\leq h$ if and only if $g\left(x\right)\leq h\left(x\right)$ for each $x$.

###### Proof.

Let $\delta_{1}=\delta_{1}\left(\epsilon\right)$ be sufficiently small, let
$\delta_{2}=\delta_{2}\left(\delta_{1}\right)$ be sufficiently small, let
$j=j\left(\delta_{2}\right)$ be sufficiently large, and let
$\delta=\delta\left(j,\delta_{1},\epsilon\right)$ be sufficiently small. By
Theorem 3.10, there exists a set $J$ of size at most $j$, such that the for a
random $\mathbf{x}\sim\left(\left\\{0,1\right\\}^{J},\mu_{q}\right)$ the
function $f_{J\to\mathbf{x}}$ does not have
$\left(1-\delta_{2},\delta_{2},\mu_{q}\right)$-small noisy influences with
probability at most $\delta_{2}$.

Let $Q\subseteq\left\\{0,1\right\\}^{J}$ be the set of ‘quasirandom parts’
consisting of all $x\in\left\\{0,1\right\\}^{J},$ such that $f_{J\to x}$ has
$\left(1-\delta_{2},\delta_{2},\mu_{q}\right)$-small noisy influences. So
$\Pr_{\boldsymbol{x}\sim\left\\{0,1\right\\}^{J}}\left[\mathbf{x}\in
Q\right]>1-\delta_{2}.$

Let $N\subseteq\left\\{0,1\right\\}^{J}$ be the set of ‘negligible parts’
consisting of all $x\in\left\\{0,1\right\\}^{J},$ such that
$\mu_{q}\left(f_{J\to x}\right)<\epsilon/2.$ Note that

$\displaystyle\Pr_{\mathbf{x}\sim\mu_{q}}\left[f\left(\mathbf{x}\right)=1\,|\,\mathbf{x}_{J}\in
N\right]$ $\displaystyle\leq\max_{y\in
N}\Pr_{\mathbf{x}\sim\mu_{q}}\left[f\left(\mathbf{x}\right)=1\,|\,\mathbf{x}_{J}=y\right]\leq\frac{\epsilon}{2}.$

Let $A$ be the up-closure of $Q/N$, i.e. the set of all
$x\in\left\\{0,1\right\\}^{J},$ such that there exists some $y\in Q\backslash
N$ that satisfies $\forall i:\,y_{i}\leq x_{i}$. Finally, we let
$g\colon\left\\{0,1\right\\}^{J}\to\left\\{0,1\right\\}$ be the indicator
function of $A.$

Showing that
$\Pr_{\mathbf{x}\sim\mu_{q}}\left[f\left(\mathbf{x}\right)>g\left(\mathbf{x}\right)\right]<\epsilon$.

For each $\mathbf{x}\in\left\\{0,1\right\\}^{n}$ with
$f\left(\mathbf{x}\right)>g\left(\mathbf{x}\right)$ we have
$g\left(x\right)=0$, and particularly $x\notin Q\backslash N.$ So we either
have $\mathbf{x}\notin Q$ or we have the unlikely event that
$f\left(\mathbf{x}\right)=1$ although $\mathbf{x}_{J}\in N.$ The former event
occurs with probability at most $\delta_{2},$ and the latter event occurs with
probability at most $\frac{\epsilon}{2}$ so

$\Pr_{\mathbf{x}\sim\mu_{q}}\left[f\left(\mathbf{x}\right)>g\left(\mathbf{x}\right)\right]<\frac{\epsilon}{2}+\delta_{2}<\epsilon,$

provided that $\delta_{2}$ is sufficiently small.

Showing that
$\Pr_{\mathbf{x}\sim\mu_{p}}\left[f\left(\mathbf{x}\right)<g\left(\mathbf{x}\right)\right]<\epsilon$.

Let $y\in A,$ let $x\in Q\backslash N$ be with $\forall i:\,x_{i}\leq y_{i}$,
and let $\rho=\sqrt{\frac{q\left(1-p\right)}{p\left(1-q\right)}}$. Since $x$
is in $Q$, we may apply Proposition 4.1 to obtain that

(5.1) $\left\langle\mathsf{T}^{q\to p}f_{J\to x},f_{J\to
y}\right\rangle\leq\Lambda_{\rho}\left(\mu_{q}\left(f_{J\to
x}\right),\mu_{p}\left(f_{J\to y}\right)\right)+\delta_{1},$

provided that $\delta_{2}$ is sufficiently small.

This gives us an upper bound on $\left\langle\mathsf{T}^{q\to p}f_{J\to
x},f_{J\to y}\right\rangle.$ On the other hand we may use the fact that $f$ is
almost monotone to obtain a lower bound on $\left\langle\mathsf{T}^{q\to
p}f_{J\to x},f_{J\to y}\right\rangle$ as follows. Note that we have

$\displaystyle\delta$ $\displaystyle\geq\left\langle\mathsf{T}^{q\to
p}f,1-f\right\rangle=\Pr_{\mathbf{z,}\mathbf{w}\sim
D\left(q,p\right)}\left[f\left(\mathbf{z}\right)=1,f\left(\mathbf{w}\right)=0\right]$
(5.2) $\displaystyle\geq\Pr_{\mathbf{z,}\mathbf{w}\sim
D\left(q,p\right)}\left[\mathbf{z}_{J}=x,\mathbf{w}_{J}=y\right]\Pr_{\mathbf{z,}\mathbf{w}\sim
D\left(q,p\right)}\left[f_{J\to x}\left(\mathbf{z}_{\left[n\right]\backslash
J}\right)=1,f_{J\to y}\left(\mathbf{w}_{\left[n\right]\backslash
J}\right)=0\right]$
$\displaystyle=\Pr_{\mathbf{x},\mathbf{y}\sim\left(\left\\{0,1\right\\}^{J},D\left(q,p\right)\right)}\left[\mathbf{x}=x,\mathbf{y}=y\right]\left\langle\mathsf{T}^{q\to
p}f_{J\to x},1-f_{J\to y}\right\rangle.$

Thus,

$\displaystyle\left\langle\mathsf{T}^{q\to p}f_{J\to x},f_{J\to
y}\right\rangle$ $\displaystyle=\left\langle\mathsf{T}^{q\to p}f_{J\to
x},1\right\rangle-\left\langle\mathsf{T}^{q\to p}f_{J\to x},1-f_{J\to
y}\right\rangle$ (5.3) $\displaystyle\geq\mu_{q}\left(f_{J\to
x}\right)-\frac{\delta}{\Pr_{\mathbf{x},\mathbf{y}\sim\left(\left\\{0,1\right\\}^{J},D\left(q,p\right)\right)}\left[\mathbf{x}=x,\mathbf{y}=y\right]}$
$\displaystyle\geq\mu_{q}\left(f_{J\to x}\right)-\delta_{1},$

provided that $\delta=\delta\left(\delta_{1},j,\epsilon\right)$ is small
enough. Combining (5.1) and (5.3) we obtain

$\Lambda_{\rho}\left(\mu_{q}\left(f_{J\to x}\right),\mu_{p}\left(f_{J\to
y}\right)\right)\geq\mu_{q}\left(f_{J\to x}\right)-2\delta_{1}.$

By Lemma 3.16 we have $\mu_{p}\left(f_{J\to y}\right)>1-\frac{\epsilon}{2}$
provided that $\delta_{1}$ is small enough (note that $\mu_{q}\left(f_{J\to
x}\right)>\epsilon/2,$ since $x\notin N$).

This shows that any $y$ with $g\left(y\right)=1,f\left(y\right)=0$ satisfies
the unlikely event that $f\left(y\right)=0$ while $\mu_{p}\left(f_{J\to
y_{J}}\right)>1-\epsilon/2.$ Since a random $\mathbf{y}\sim\mu_{p}$ satisfies
this event with probability at most $\epsilon$, we obtain
$\Pr_{\boldsymbol{y}\sim\mu_{p}}\left[f\left(\boldsymbol{y}\right)<g\left(\boldsymbol{y}\right)\right]<\epsilon$.
This completes the proof of the theorem. ∎

We may repeat the proof of Theorem 2.5 to obtain the following lemma that we
use in the proof of Theorem 2.8.

######  Lemma 5.1.

For each $\epsilon>0,j\in\mathbb{N}$ there exists $\delta>0,$ such that the
following holds. Let $f,g\colon\left\\{0,1\right\\}^{n}\to\left[0,1\right]$ be
functions, let $J$ be a set of size at most $j,$ and let
$p,q\in\left(\epsilon,1-\epsilon\right)$, be with $p-q>\epsilon.$ Suppose that
$\left\langle\mathsf{T}_{q\to p}f,1-g\right\rangle<\delta,$ and let
$x,y\in\left\\{0,1\right\\}^{J}$ be with $\forall i:\,x_{i}\leq y_{i}.$
Suppose additionally that $f_{J\to x}$ has
$\left(1-\epsilon,\epsilon,\mu_{q}\right)$-small noisy influences. Then we
either have $\mu_{q}\left(f_{J\to x}\right)<\epsilon$ or we have
$\mu_{p}\left(g_{J\to y}\right)>1-\epsilon.$

###### Proof.

Let $\delta_{1}=\delta_{1}\left(\epsilon\right)$ be sufficiently small, and
let $\delta=\delta\left(\delta_{1},j\right)$ be sufficiently small. Similarly
to (5.2) we have

$\displaystyle\delta$ $\displaystyle\geq\left\langle\mathsf{T}^{q\to
p}f,1-g\right\rangle\geq\left\langle\mathsf{T}^{q\to p}f_{J\to x},1-g_{J\to
y}\right\rangle\Pr_{\mathbf{x},\mathbf{y}\sim\left(\left\\{0,1\right\\}^{J},D\left(q,p\right)\right)}\left[\mathbf{x}=x,\mathbf{y}=y\right].$

Similarly to (5.3) we have

$\left\langle\mathsf{T}^{q\to p}f_{J\to x},g_{J\to
y}\right\rangle\geq\mu_{q}\left(f_{J\to x}\right)-\delta_{1},$

provided that $\delta_{1}$ is small enough. Similarly to (5.1), we have

$\left\langle\mathsf{T}^{q\to p}f_{J\to x},g_{J\to
y}\right\rangle\leq\Lambda_{\rho}\left(\mu_{q}\left(f_{J\to
x}\right),\mu_{p}\left(g_{J\to y}\right)\right)+\delta_{1}.$

Hence,

$\Lambda_{\rho}\left(\mu_{q}\left(f_{J\to x}\right),\mu_{p}\left(g_{J\to
y}\right)\right)\geq\mu_{q}\left(f_{J\to x}\right)-2\delta_{1}.$

As in the proof of Theorem (2.5), we may now apply Lemma 3.16 to complete the
proof. ∎

We shall now prove Theorem 2.8. We restate it for the convenience of the
reader.

######  Theorem.

For each $\epsilon>0$, there exists $\delta>0$, such that the following holds.
Let $q,p\in\left(\epsilon,1-\epsilon\right)$ and suppose that $p>q+\epsilon$.
Let $f,g\colon\left\\{0,1\right\\}^{n}\to\left[0,1\right]$, and suppose that

$\mathbb{E}_{\mathbf{x},\mathbf{y}\sim
D\left(q,p\right)}\left[\left(1-g\left(\mathbf{y}\right)\right)f\left(\mathbf{x}\right)\right]<\delta,$

and that the function $f$ is
$\left(\left\lceil\frac{1}{\delta}\right\rceil,\delta,\mu_{q}\right)$-regular.
Then either $\mu_{q}\left(f\right)<\epsilon$, or
$\mu_{p}\left(g\right)>1-\epsilon.$

###### Proof.

Let $\delta_{1}=\delta_{1}\left(\epsilon\right)$ be sufficiently small, let
$j=j\left(\delta_{1},\epsilon\right)$ be sufficiently large, and let
$\delta=\delta\left(j,\delta_{1},\epsilon\right)$ be sufficiently small. By
Theorem 3.10, there exists a set $J$ of size at most $j$, such that for a
random $\mathbf{x}\sim\left(\left\\{0,1\right\\}^{J},\mu_{q}\right)$ the
function $f_{J\to x}$ does not have
$\left(1-\delta_{1},\delta_{1},\mu_{q}\right)$-small noisy influences with
probability at most $\delta_{1}$. Let $Q\subseteq\left\\{0,1\right\\}^{J}$ be
the set of ‘quasirandom elements’ consisting of all
$x\in\left\\{0,1\right\\}^{J},$ such that $f_{J\to x}$ has
$\left(1-\delta_{1},\delta_{1},\mu_{q}\right)$-small noisy influences. Let $A$
be the up-closure of $Q$. Since $A$ is monotone, we have

$\mu_{p}\left(A\right)\geq\mu_{q}\left(A\right)\geq 1-\delta_{2}.$

Moreover, the fact that $f$ is
$\left(\left\lceil\frac{1}{\delta}\right\rceil,\delta,\mu_{q}\right)$-regular
implies that

$\mu_{q}\left(f_{J\to x}\right)\geq\epsilon-\delta>\epsilon/2$

for each $x\in\left\\{0,1\right\\}^{J},$ provided that
$\delta<\min\left\\{\frac{\epsilon}{2},\frac{1}{j}\right\\}.$ By Lemma 5.1
(applied with $\epsilon/2$ rather than $\epsilon$), we obtain that
$\mu_{p}\left(g_{J\to x}\right)>1-\epsilon/2$ for all $x\in A.$ So this
implies that

$\mu_{p}\left(g\right)\geq\left(1-\epsilon/2\right)\mu_{p}\left(A\right)\geq\left(1-\epsilon/2\right)\left(1-\delta/2\right)>1-\epsilon.$

This completes the proof of the theorem. ∎

##  6\.  Counting matchings

In this section we prove Theorem 7.1 in the case where $\mathcal{H}$ is a
matching.

######  Theorem 6.1.

For each $h\in\mathbb{N},\epsilon>0,$ there exists $\delta>0$, such that the
following holds. Let
$k_{1},\ldots,k_{h}\leq\left(\frac{1}{s}-\epsilon\right)n$, and let
$\mathcal{F}_{1}\subseteq\binom{\left[n\right]}{k_{1}},\ldots,\mathcal{F}_{h}\subseteq\binom{\left[n\right]}{k_{h}}$
be families whose measure is at least $\epsilon$. Suppose that for each
$i\in\left[n\right]$, such that $k_{i}\geq\delta n$ the family
$\mathcal{F}_{i}$ is
$\left(\left\lceil\frac{1}{\delta}\right\rceil,\delta\right)$-regular, and
choose uniformly at random a matching
$\left\\{\boldsymbol{A}_{1},\ldots,\boldsymbol{A}_{h}\right\\},$ such that

$\mathbf{A}_{1}\in\binom{\left[n\right]}{k_{1}},\ldots,\mathbf{A}_{h}\in\binom{\left[n\right]}{k_{h}}.$

Then

$\Pr\left[\mathbf{A}_{1}\in\mathcal{F}_{1},\ldots,\mathbf{A}_{h}\in\mathcal{F}_{h}\right]>\delta.$

We start by stating some constructions that we shall use throughout the proof.

###  6.1. Basic constructions and overview of the proof

We completely identify between an element $x\in\left\\{0,1\right\\}^{n}$ with
the set of $i\in\left[n\right],$ such that $x_{i}=1$. Thus, we shall use the
notations $\mathcal{F}_{J}^{B},$ $\mathcal{F}_{J}^{1_{B}}$ interchangeably, we
write $\mathcal{P}\left(x\right)$ for the family of all subsets of
$\left\\{i:\,x_{i}=1\right\\},$ we shall write $\binom{x}{k}$ for the family
of all subsets in $\mathcal{P}\left(x\right)$ whose size is $k$, and we write
$\left|x\right|$ for $\\#\left\\{i:\,x_{i}=1\right\\}.$

The first construction that we need associates to each family
$\mathcal{F}\subseteq\binom{\left[n\right]}{k}$ a function
$f_{\mathcal{F}}\colon\left\\{0,1\right\\}^{n}\to\left[0,1\right].$ This
construction is originated in the work of Friedgut and Regev [34].

######  Definition 6.2.

Let $\mathcal{F}\subseteq\binom{\left[n\right]}{k}$, we associate to
$\mathcal{F}$ the function $f_{\mathcal{F}}$ defined by

$f_{\mathcal{F}}\left(x\right)=\begin{cases}0&\left|x\right|<k\\\
\Pr_{A\sim\binom{x}{k}}\left[A\in\mathcal{F}\right]&\left|x\right|\geq
k\end{cases}.$

Another construction we need turns a function
$f\colon\left\\{0,1\right\\}^{n}\to\mathbb{R}$ into a Boolean function
$\mathrm{Cut}_{\delta}\left(f\right).$

######  Definition 6.3.

Given a function $f\colon\left\\{0,1\right\\}^{n}\to\mathbb{R}$, and a
$\delta\in\mathbb{R}$, we define the function
$\mathrm{Cut}_{\delta}\left(f\right)$ by setting:

$\mathrm{Cut}_{\delta}\left(f\right)\left(\mathbf{x}\right)=\begin{cases}1&\mbox{
if }f\left(\mathbf{x}\right)\geq\delta\\\ 0&\mbox{ if
}f\left(\mathbf{x}\right)<\delta\end{cases}.$

We shall also need to introduce the following distributions.

######  Definition 6.4.

Let $p\in\left(0,1\right),$ and let $k\in\left[n\right].$

  * •

We write $\mu_{p}^{\geq k}$ for the conditional probability distribution on
$\mathbf{x}\sim\left(\left\\{0,1\right\\}^{n},\mu_{p}\right)$ given that
$\left|\mathbf{x}\right|\geq k.$ (The distributions
$\mu_{p}^{>k},\mu_{p}^{<k},\mu_{p}^{\leq k}$ are defined accordingly.)

  * •

We write $\left(\mu_{p}^{\geq k},J\to B\right)$ for the conditional
distribution on sets $\mathbf{A}\sim\mu_{p}^{\geq k}$ given that
$\mathbf{A}\cap J=B.$ The distributions $\left(\mu_{p},J\to
B\right),\left(\binom{\left[n\right]}{k},J\to B\right)$ are defined
accordingly.

Another construction we need is the construction of a random matchings

$\mathbf{B}_{1},\ldots,\mathbf{B}_{h}\in\mathcal{P}\left(\left[n\right]\right),$

such that each of the sets $\mathbf{B}_{i}$ is distributed according to the
$\frac{1}{h}$-biased distribution.

######  Definition 6.5.

Choose uniformly and independently $\left[0,1\right]$-valued random variables
$X_{1},\ldots,X_{n}$. For each $i\in\left\\{1,\ldots,h\right\\}$ we let
$\mathbf{B}_{i}$ be the set of all $j\in\left[n\right],$ such that $X_{j}$ is
in the interval $\left[\frac{j-1}{h},\frac{j}{h}\right]$. We call the sets
$\left(\mathbf{B}_{1},\ldots,\mathbf{B}_{h}\right)$ a random _$\frac{1}{h}$
-biased matching_. Let $k\leq\frac{n}{h}$ we call the conditional distribution
on a random $\frac{1}{h}$-biased matching
$\left(\mathbf{B}_{1},\ldots,\mathbf{B}_{h}\right)$ given that
$\left|\mathbf{B}_{i}\right|\geq k$ for each $i$ a
_$\left(\frac{1}{h},k\right)$ -biased matching._ Given a
$\left(\frac{1}{h},k\right)$-biased matching
$\left(\mathbf{B}_{1},\ldots,\mathbf{B}_{h}\right)$, we obtain that
$\mathbf{B}_{1}$ is distributed according to some distribution that we denote
by $\mu_{\frac{1}{h},k}^{\mbox{matching}}.$

Note that if $\left(\mathbf{B}_{1},\ldots,\mathbf{B}_{h}\right)$ a random
_$\frac{1}{h}$_ -biased matching, then each $\mathbf{B}_{i}$ is indeed chosen
according to the $\frac{1}{h}$-biased distribution, and moreover the sets
$\mathbf{B}_{1},\ldots,\mathbf{B}_{h}$ are pairwise disjoint with probability
1.

We will be concerned with the case where
$k\leq\frac{n}{h}-\Theta\left(n\right)$. This would yield that
$\left|\mathbf{B}_{i}\right|\geq k$ asymptotically almost surely for all $i$.
So intuitively, the distribution of a $\frac{1}{h}$-biased matching is not
much different than the distribution of a $\left(\frac{1}{h},k\right)$-biased
matching.

The proof of Theorem 6.1 consists of three steps:

(In the following $\epsilon_{1}$ is sufficiently small and
$\epsilon_{2}=\epsilon_{2}\left(\epsilon_{1}\right)$ is sufficiently small)

  1. (1)

We set $q$ to be slightly larger than $\frac{k}{n}$. The first step is to show
that for each of the families $\mathcal{F}_{i}$ of Theorem 6.1, the function
$f_{\mathcal{F}_{i}}$ is
$\left(\left\lceil\frac{1}{\epsilon_{1}}\right\rceil,\epsilon_{1},\mu_{q}\right)$-regular.

  2. (2)

The second step is to show that the measure
$\mu_{\frac{1}{h},k}^{\mbox{matching}}\left(\mathrm{Cut}_{\epsilon_{2}}\left(f_{\mathcal{F}_{i}}\right)\right)$
is very close to 1.

This step is based on Theorem 2.8, and the proof roughly goes as follows.

     * •

We show that the term $\mathbb{E}_{\mathbf{x},\mathbf{y}\sim
D\left(q,\frac{1}{h}\right)}\left[f_{\mathcal{F}_{i}}\left(\mathbf{x}\right)\left(1-\mathrm{Cut}_{\epsilon_{2}}\left(f_{\mathcal{F}_{i}}\left(\mathbf{y}\right)\right)\right)\right]$
is always smaller than $\epsilon_{2}$.

     * •

We shall apply Theorem 2.8 to deduce that
$\mu_{\frac{1}{h}}\left(\mathrm{Cut}_{\epsilon_{2}}\left(f_{\mathcal{F}_{i}}\right)\right)$
is large.

     * •

We shall use the similarity between $\mu_{\frac{1}{s}}$ and
$\mu_{\frac{1}{h},k}^{\mathrm{matching}}$ to deduce that
$\mu_{\frac{1}{h},k}^{\mbox{matching}}\left(\mathrm{Cut}_{\epsilon_{2}}\left(f_{\mathcal{F}_{i}}\right)\right)$
is large.

  3. (3)

We then finish the proof by observing that if we choose a
$\left(\frac{1}{h},k\right)$-biased matching
$\mathbf{B}_{1},\ldots,\mathbf{B}_{h},$ and then choose sets
$\mathbf{M}_{1}\sim\binom{\mathbf{B}_{1}}{k_{1}},\ldots,\mathbf{M}_{s}\sim\binom{\mathbf{B}_{h}}{k_{h}}.$
Then $\mathbf{M}_{1},\ldots,\mathbf{M}_{h}$ is a uniformly random matching. By
Step 2 and a union bound we would have
$\mathrm{Cut}_{\epsilon_{2}}\left(f_{\mathcal{F}_{i}}\right)\left(\mathbf{B}_{i}\right)=1$
with high probability. On the other hand for each $B_{i}$ with
$\mathrm{Cut}_{\epsilon_{2}}\left(f_{\mathcal{F}_{i}}\right)\left(B_{i}\right)=1$,
we have
$\Pr_{\mathbf{M_{i}\sim}\binom{B_{i}}{k_{i}}}\left[\mathbf{M}_{i}\in\mathcal{F}\right]\geq\epsilon_{2}$,
and for each choice of disjoint $B_{1},\ldots,B_{h}$ these events are
independent. Therefore, the probability that $\mathbf{M}_{i}$ is in
$\mathcal{F}$ for each $i$ cannot be much smaller than $\epsilon_{2}^{h}.$

We shall start with the proof of the first step.

###  6.2. Showing that if $\mathcal{F}$ is regular, then the function
$f_{\mathcal{F}}$ is
$\left(\left\lceil\frac{1}{\epsilon}\right\rceil,\epsilon,\mu_{q}\right)$-regular

In order to show that the function $f_{\mathcal{F}}$ is regular, we will need
to show that $\mu_{q}\left(f_{\mathcal{F}}\right)$ is approximately
$\mu_{q}\left(\left(f_{\mathcal{F}}\right)_{J\to x}\right)$ for each
$\left|J\right|\leq\left\lceil\frac{1}{\epsilon}\right\rceil,$ and each
$x\in\left\\{0,1\right\\}^{J}$. In order to accomplish this we would need to
write both of the quantities
$\mu_{q}\left(f_{\mathcal{F}}\right),\mu_{q}\left(\left(f_{\mathcal{F}}\right)_{J\to
x}\right)$ in terms of $\mathcal{F}$. We shall start by showing that
$\mu_{q}\left(f_{\mathcal{F}}\right)$ is approximately equal to
$\mu\left(\mathcal{F}\right).$

######  Lemma 6.6.

For each $\epsilon>0,$ there exists $n_{0}>0$, such that the following holds.
Let $n>n_{0}$, let $q\in\left(0,1\right),k\leq n$ satisfy
$q\geq\frac{k}{n}+\epsilon,$ and let
$\mathcal{F}\subseteq\binom{\left[n\right]}{k}$ be some family. Then

(6.1)
$\mu_{q}\left(f_{\mathcal{F}}\right)\leq\mu\left(\mathcal{F}\right)\leq\mu_{q}\left(f_{\mathcal{F}}\right)\left(1+\epsilon\right).$

###### Proof.

We have

$\displaystyle\mu_{q}\left(f_{\mathcal{F}}\right)$
$\displaystyle=\mathbb{E}_{\mathbf{x}\sim\mu_{q}}\left[f_{\mathcal{F}}\left(\mathbf{x}\right)\right]=\Pr\left[\mathbf{x}\geq
k\right]\mathbb{E}_{\mathbf{x}\sim\mu_{q}^{\geq
k}}\left[f_{\mathcal{F}}\left(\mathbf{x}\right)\right]+\Pr\left[\mathbf{x}<k\right]\mathbb{E}_{\mathbf{x}\sim\mu_{q}^{<k}}\left[f_{\mathcal{F}}\left(\mathbf{x}\right)\right].$
$\displaystyle=\Pr_{\mathbf{x}\sim\mu_{q}}\left[\left|\mathbf{x}\right|\geq
k\right]\mathbb{E}_{\mathbf{x}\sim\mu_{q}^{\geq
k}}\left[\Pr_{\mathbf{A}\sim\binom{\mathbf{x}}{k}}\left[\mathbf{A}\in\mathcal{F}\right]\right].$

However, whenever we choose $\mathbf{x}\sim\mu_{q}^{\geq k}$, and an
$\mathbf{A}\sim\binom{\mathbf{x}}{k}$, we obtain a set $\mathbf{A}$ that is
distributed uniformly in $\binom{\left[n\right]}{k}$. Thus,

(6.2)
$\mu_{q}\left(f_{\mathcal{F}}\right)=\Pr_{\mathbf{x}\sim\mu_{q}}\left[\left|\mathbf{x}\right|\geq
k\right]\mu\left(\mathcal{F}\right).$

The lemma follows by combining (6.2) with the fact that
$\Pr_{\mathbf{x}\sim\mu_{q}}\left[\left|\mathbf{x}\right|\geq k\right]$ tends
to 1 as $n$ tends to infinity. ∎

We now turn to the task of approximating
$\mu_{q}\left(\left(f_{\mathcal{F}}\right)_{J\to x}\right)$ in terms of
$\mathcal{F}$. We show that for some $\lambda>0$ the term
$\mu_{q}\left(\left(f_{\mathcal{F}}\right)_{J\to x}\right)$ can be
approximated by

$\underset{\mathbf{C}\sim\left(\mathcal{P}\left(x\right),\mu_{\lambda}\right)}{\mathbb{E}}\left[\mu\left(\mathcal{F}_{J\to\mathbf{C}}\right)\right].$

######  Lemma 6.7.

For each $\epsilon>0$ there exists $n_{0},$ such that the following holds. Let
$n>n_{0},$ let $k\leq n$ and let $q$ be a number in the interval
$\left(\frac{k}{n}+\epsilon,1\right)$, and set $\lambda=\frac{k}{qn}.$ Then

$\mu_{q}\left(\left(f_{\mathcal{F}}\right)_{J\to
x}\right)\left(1-\epsilon\right)\leq\underset{\mathbf{C}\sim\left(\mathcal{P}\left(x\right),\mu_{\lambda}\right)}{\mathbb{E}}\left[\mu\left(\mathcal{F}_{J\to\mathbf{C}}\right)\right]\leq\mu_{q}\left(\left(f_{\mathcal{F}}\right)_{J\to
x}\right)\left(1+\epsilon\right).$

###### Proof.

As in Lemma 6.6, we have

(6.3) $\mu_{q}\left(\left(f_{\mathcal{F}}\right)_{J\to
x}\right)=\Pr_{\mathbf{y}\sim\left(\mu_{q},J\to
x\right)}\left[\left|\mathbf{y}\right|\geq
k\right]\underset{\mathbf{y}\sim\left(\mu_{q}^{\geq k},J\to
x\right)}{\mathbb{E}}\left[f_{\mathcal{F}}\left(\mathbf{y}\right)\right].$

Note that

$\Pr_{\mathbf{y}\sim\left(\mu_{q},J\to
x\right)}\left[\left|\mathbf{y}\right|\geq k\right]=1-o\left(1\right),$

where the $o\left(1\right)$ is with respect to $n$ tending to infinity. So to
complete the proof it remains show that

$\underset{\mathbf{y}\sim\left(\mu_{q}^{\geq k},J\to
x\right)}{\mathbb{E}}\left[f_{\mathcal{F}}\left(\mathbf{y}\right)\right]=\left(1+o\left(1\right)\right)\underset{\mathbf{C}\sim\left(\mathcal{P}\left(x\right),\mu_{\lambda}\right)}{\mathbb{E}}\left[\mu\left(\mathcal{F}_{J\to\mathbf{C}}\right)\right].$

Choose $\mathbf{y}\sim\left(\mu_{q}^{\geq k},J\to
x\right),$$\mathbf{A\sim}\binom{\mathbf{y}}{k},$ then $\mathbf{A}\cap J$ is
equal to some subset $\mathbf{C}$ of $\mathbf{x}.$ Note also that the
conditional distribution of $\mathbf{A}$ given that $\mathbf{C=}C$ is the
distribution of a uniformly random element of $\binom{\left[n\right]}{k}$ that
intersects $J$ at the set $C.$ Therefore,

$\displaystyle\underset{\mathbf{y}\sim\left(\mu_{q}^{\geq k},J\to
x\right)}{\mathbb{E}}\left[f_{\mathcal{F}}\left(\mathbf{y}\right)\right]$
$\displaystyle=\Pr_{\mathbf{y}\sim\left(\mu_{q}^{\geq k},J\to
x\right),\mathbf{A}\sim\binom{\mathbf{y}}{k}}\left[A\in\mathcal{F}\right]$
$\displaystyle\sum_{C\subseteq
x}\Pr\left[\mathbf{C}=C\right]\Pr\left[\mathbf{A\in\mathcal{F}\,|\,}\mathbf{C}=C\right]$
(6.4) $\displaystyle=\sum_{C\subseteq
x}\Pr\left[\mathbf{C}=C\right]\mu\left(\mathcal{F}_{J}^{C}\right).$

So to complete the proof it remains to show that

(6.5)
$\Pr\left[\mathbf{C}=C\right]=\lambda^{\left|C\right|}\left(1-\lambda\right)^{\left|x\right|\backslash\left|C\right|}\left(1+o\left(1\right)\right).$

Indeed, with high probability
$\left|\mathbf{y}\right|=qn\left(1+o\left(1\right)\right),$ and the
conditional probability that $\mathbf{C}=C$ given that
$\left|\mathbf{y}\right|=s$ is

$\frac{\left|\left\\{S\in\binom{\mathbf{y}}{k}\mbox{ that satisfy }\left|S\cap
x\right|=C\right\\}\right|}{\left|\binom{\mathbf{y}}{k}\right|}=\frac{\binom{s-\left|x\right|}{k-\left|C\right|}}{\binom{s}{k}}=\left(\frac{k}{s}\right)^{\left|C\right|}\left(1-\frac{k}{s}\right)^{\left|x\right|\backslash\left|C\right|}\left(1+o\left(1\right)\right).$

Let $\mathbf{s}=\left|\mathbf{y}\right|.$ Thus,

$\displaystyle\Pr\left[\mathbf{C}=C\right]$
$\displaystyle=\mathbb{E}_{\mathbf{s}}\left[\Pr\left[\mathbf{C}=C\,|\,\mathbf{s}\right]\right]=\mathbb{E}_{\mathbf{s}}\left[\left(\frac{k}{\mathbf{s}}\right)^{\left|C\right|}\left(1-\frac{k}{\mathbf{s}}\right)^{\left|x\right|\backslash\left|C\right|}\left(1+o\left(1\right)\right)\right]$
$\displaystyle=\lambda^{\left|C\right|}\left(1-\lambda\right)^{\left|x\right|\backslash\left|C\right|}\left(1+o\left(1\right)\right),$

where the last equality follows from the fact that
$\frac{k}{\mathbf{s}}=\lambda\left(1+o\left(1\right)\right)$ with high
probability. This completes the proof of the lemma. ∎

We are now ready to show that if
$\mathcal{F}\subseteq\binom{\left[n\right]}{k}$ is a
$\left(\left\lceil\frac{1}{\epsilon}\right\rceil,\epsilon\right)$-regular
family, and if we choose $q$ that is bounded from below away of $\frac{k}{n}$,
then the function $f_{\mathcal{F}}$ is
$\left(\left\lceil\frac{1}{2\epsilon}\right\rceil,2\epsilon,\mu_{q}\right)$-regular,
provided that $n$ is sufficiently large.

######  Lemma 6.8.

For each $\epsilon<0$, there exists $n_{0},$ such that the following holds.
Let $n>n_{0}$, let $\mathcal{F}\subseteq\binom{\left[n\right]}{k}$ be a
$\left(\left\lceil\frac{1}{2\epsilon}\right\rceil,2\epsilon\right)$-regular
family, and let $q\geq\frac{k}{n}+\epsilon.$ Then the function
$f_{\mathcal{F}}$ is
$\left(\left\lceil\frac{1}{\epsilon}\right\rceil,\epsilon,\mu_{q}\right)$-regular.

###### Proof.

Fix $\epsilon>0,$ let $n_{0}$ be sufficiently large, and let
$\mathcal{F}\subseteq\binom{\left[n\right]}{k},$ be as in the hypothesis of
the lemma. Let $B\subseteq J\subseteq\left[n\right]$ be sets, such that
$\left|J\right|\leq\left\lceil\frac{1}{\epsilon}\right\rceil$. By Lemma 6.6

(6.6)
$\left|\mu\left(\mathcal{F}\right)-\mu_{q}\left(f_{\mathcal{F}}\right)\right|<\frac{\epsilon}{4},$

provided that $n_{0}$ is large enough. By Lemma 6.7

(6.7) $\left|\mu_{q}\left(\left(f_{\mathcal{F}}\right)_{J\to
B}\right)-\mathbb{E}_{\mathbf{C}\sim\left(\mathcal{P}\left(x\right),\mu_{\frac{k}{qn}}\right)}\mu\left(\mathcal{F}_{J}^{C}\right)\right|<\frac{\epsilon}{4},$

provided that $n_{0}$ is large enough.

By hypothesis

(6.8)
$\displaystyle\left|\mu\left(\mathcal{F}\right)-\mathbb{E}_{\mathbf{C}\sim\left(\mathcal{P}\left(x\right),\mu_{\frac{k}{qn}}\right)}\mu\left(\mathcal{F}_{J}^{C}\right)\right|$
$\displaystyle=\left|\mathbb{E}_{\mathbf{C}\sim\left(\mathcal{P}\left(x\right),\mu_{\frac{k}{qn}}\right)}\left(\mu\left(\mathcal{F}_{J}^{C}\right)-\mu\left(\mathcal{F}\right)\right)\right|$
$\displaystyle\leq\mathbb{E}_{\mathbf{C}\sim\left(\mathcal{P}\left(x\right),\mu_{\frac{k}{qn}}\right)}\frac{\epsilon}{2}=\frac{\epsilon}{2}.$

Thus,

$\displaystyle\left|\mu_{q}\left(\left(f_{\mathcal{F}}\right)_{J\to
B}\right)-\mu_{q}\left(f_{\mathcal{F}}\right)\right|$
$\displaystyle\leq\left|\mu_{q}\left(\left(f_{\mathcal{F}}\right)_{J\to
B}\right)-\mathbb{E}_{\mathbf{C}\sim\left(\mathcal{P}\left(x\right),\mu_{\frac{k}{qn}}\right)}\mu\left(\mathcal{F}_{J}^{C}\right)\right|$
$\displaystyle+\left|\mathbb{E}_{\mathbf{C}\sim\left(\mathcal{P}\left(x\right),\mu_{\frac{k}{qn}}\right)}\mu\left(\mathcal{F}_{J}^{C}\right)-\mu\left(\mathcal{F}\right)\right|+\left|\mu\left(\mathcal{F}\right)-\mu_{q}\left(f_{\mathcal{F}}\right)\right|$
$\displaystyle<\frac{\epsilon}{4}+\frac{\epsilon}{4}+\frac{\epsilon}{2}=\epsilon.$

This completes the proof that $f_{\mathcal{F}}$ is
$\left(\left\lceil\frac{1}{\epsilon}\right\rceil,\epsilon,\mu_{q}\right)$-regular.
∎

###  6.3. Showing that if $\frac{k}{n}$ is small, then $f_{\mathcal{F}}$ is
$\left(\left\lceil\frac{1}{\epsilon}\right\rceil,\epsilon,\mu_{q}\right)$-regular

######  Lemma 6.9.

For each $\epsilon>0,$ there exists $\delta>0$ such that the following holds.
Let $\frac{k}{n}<\delta$, let $q\geq\epsilon$, and let
$\mathcal{F}\subseteq\binom{\left[n\right]}{k}$ be some family. Then the
function $f_{\mathcal{F}}$ is
$\left(\left\lceil\frac{1}{\epsilon}\right\rceil,\epsilon,\mu_{q}\right)$-regular.

###### Proof.

Let $J$ be of size at most $\left\lceil\frac{1}{\epsilon}\right\rceil,$ and
let $B\subseteq J.$ We have

(6.9) $\left|\mu_{q}\left(\left(f_{\mathcal{F}}\right)_{J\to
B}\right)-\mu_{q}\left(f_{\mathcal{F}}\right)\right|\leq\left|\mu\left(\mathcal{F}_{J}^{\varnothing}\right)-\mu_{q}\left(f_{\mathcal{F}}\right)\right|+\left|\mu\left(\mathcal{F}_{J}^{\varnothing}\right)-\mu_{q}\left(\left(f_{\mathcal{F}}\right)_{J\to
B}\right)\right|.$

We shall complete the proof by giving an upper bound of $\frac{\epsilon}{2}$
for each of the summands in the right hand side of (6.9).

Showing that
$\left|\mu\left(\mathcal{F}_{J}^{\varnothing}\right)-\mu_{q}\left(f_{\mathcal{F}}\right)\right|\leq\frac{\epsilon}{2}.$

By decreasing $\delta$ if necessary we may assume that $n$ is as large as we
wish. Therefore Lemma 6.6 implies that

$\left|\mu_{q}\left(f_{\mathcal{F}}\right)-\mu\left(\mathcal{F}\right)\right|<\frac{\epsilon}{4},$

provided that $\delta$ is small enough. Now note that

(6.10) $\displaystyle\mu\left(\mathcal{F}\right)$
$\displaystyle=\sum_{B\subseteq
J}\Pr_{\mathbf{A}\sim\binom{\left[n\right]}{k}}\left[\mathbf{A}\cap
J=B\right]\mu\left(\mathcal{F}_{J}^{B}\right)$
$\displaystyle=\left(1-O\left(\frac{k}{n}\right)\right)\mu\left(\mathcal{F}_{J}^{\varnothing}\right)+\sum_{\varnothing\neq
B\subseteq
J}O\left(\left(\frac{k}{n}\right)^{\left|B\right|}\right)\mu\left(\mathcal{F}_{J}^{B}\right).$

So provided that $\delta$ is small enough, we have

$\left|\mu_{q}\left(f_{\mathcal{F}}\right)-\mu\left(\mathcal{F}_{J}^{\varnothing}\right)\right|\leq\left|\mu_{q}\left(f_{\mathcal{F}}\right)-\mu\left(\mathcal{F}\right)\right|+\left|\mu\left(\mathcal{F}\right)-\mu\left(\mathcal{F}_{J}^{\varnothing}\right)\right|\leq\frac{\epsilon}{4}+O_{\epsilon}\left(\frac{k}{n}\right)<\epsilon/2.$

Showing that
$\left|\mu\left(\mathcal{F}_{J}^{\varnothing}\right)-\mu_{q}\left(\left(f_{\mathcal{F}}\right)_{J\to
B}\right)\right|<\frac{\epsilon}{2}.$

By Lemma 6.9

$\left|\mu_{q}\left(\left(f_{\mathcal{F}}\right)_{J\to
B}\right)-\sum_{C\subseteq
B}\left(\frac{k}{qn}\right)^{\left|C\right|}\left(1-\frac{k}{qn}\right)^{\left|B\right|\backslash\left|C\right|}\mu\left(\mathcal{F}_{J}^{C}\right)\right|\leq\frac{\epsilon}{4},$

provided that $n$ is large enough. Now note that similarly to (6.10) we have

$\sum_{C\subseteq
B}\left(\frac{k}{qn}\right)^{\left|C\right|}\left(1-\frac{k}{qn}\right)^{\left|B\right|\backslash\left|C\right|}\mu\left(\mathcal{F}_{J}^{C}\right)=\mu\left(\mathcal{F}_{J}^{\varnothing}\right)+O_{\epsilon}\left(\frac{k}{n}\right).$

Thus,