# Sharp Hypercontractivity for Global Functions

Nathan Keller , Noam Lifshitz , and Omri Marcus Department of Mathematics,
Bar-Ilan University<EMAIL_ADDRESS>Supported by the Israel Science
Foundation (grant no. 2669/21).Einstein institute of Mathematics, Hebrew
University<EMAIL_ADDRESS>Supported by the Israel Science Foundation
(grant no. 1980/22).Department of Mathematics, Bar-Ilan University.
<EMAIL_ADDRESS>
###### Abstract

For a function $f:\\{0,1\\}^{n}\to\mathbb{R}$ with Fourier expansion
$f=\sum_{S\subset\\{1,2,\ldots,n\\}}\hat{f}(S)\chi_{S}$, the hypercontractive
inequality for the noise operator allows bounding norms of
$T_{\rho}f=\sum_{S}\rho^{|S|}\hat{f}(S)\chi_{S}$ in terms of norms of $f$. If
$f$ is Boolean-valued, the level-$d$ inequality allows bounding the norm of
$f^{=d}=\sum_{|S|=d}\hat{f}(S)\chi_{S}$ in terms of $\mathbb{E}[f]$. These two
inequalities play a central role in analysis of Boolean functions and its
applications.

While both inequalities hold in a sharp form when the hypercube
$\\{0,1\\}^{n}$ is endowed with the uniform measure, it is easy to show that
they do not hold for more general discrete product spaces, and finding a
‘natural’ generalization was a long-standing open problem. In [P. Keevash, N.
Lifshitz, E. Long, and D. Minzer, Global hypercontractivity and its
applications, J. Amer. Math. Soc., to appear], Keevash et al. obtained a
hypercontractive inequality for general discrete product spaces, that holds
for functions which are ‘global’ – namely, are not significantly affected by a
restriction of a small set of coordinates. This hypercontractive inequality is
not sharp, which precludes applications to the symmetric group $S_{n}$ and to
other settings where sharpness of the bound is crucial. Also, no level-$d$
inequality for global functions over general discrete product spaces is known.

We obtain sharp versions of the hypercontractive inequality and of the
level-$d$ inequality for global functions over discrete product spaces. Our
inequalities open the way for diverse applications to extremal set theory and
to group theory. We demonstrate this by proving quantitative bounds on the
size of intersecting families of sets and vectors under weak symmetry
conditions and by describing numerous applications to the study of functions
on the symmetric group $S_{n}$ – including hypercontractivity and level-$d$
inequalities, character bounds, variants of Roth’s theorem and of Bogolyubov’s
lemma, and diameter bounds, that were obtained using our techniques.

##  1 Introduction

###  1.1 Background

Analysis of Boolean functions was initiated as a study of functions on the
hypercube $\\{0,1\\}^{n}$ via their discrete Fourier expansion, that is, their
unique representation as a multi-linear polynomial over the reals. The field
has expanded greatly in the last 30 years, a rich theory was developed, and
applications to a wide variety of fields – e.g., percolation theory, group
theory, hardness of approximation, machine learning, social choice, etc. –
were established (see [30, 45]).

The basic tool, which lies behind most central results in the field, is the
hypercontractive inequality for the noise operator, obtained by Bonami [5],
Gross [23], and Beckner [3]. For $0\leq\rho\leq 1$, the noise operator
$T_{\rho}:L^{2}(\\{0,1\\}^{n})\to L^{2}(\\{0,1\\}^{n})$ is defined by
$T_{\rho}f(x)=\mathbb{E}[f(y)]$, where $y$ is obtained from $x$ by leaving
each coordinate unchanged with probability $\rho$ and replacing it by a random
value with probability $1-\rho$. The basic form of the inequality asserts that
when the hypercube is endowed with the uniform measure $\mu_{1/2}$, this
operator is hypercontractive.

######  Theorem 1.1.

Let $q\geq 2$ and let $\rho\leq\frac{1}{\sqrt{q-1}}.$ For any $f\in
L^{2}(\\{0,1\\}^{n},\mu_{1/2})$, we have

$\|T_{\rho}f\|_{q}\leq\|f\|_{2}.$

An alternative approach to the noise operator is via the Fourier expansion. If
$f=\sum_{S\subset\\{1,2,\ldots,n\\}}\hat{f}(S)\chi_{S}$, where
$\chi_{S}=\prod_{i\in S}(2x_{i}-1)$, is the Fourier expansion of $f$, then
$T_{\rho}f=\sum_{S}\rho^{|S|}\hat{f}(S)\chi_{S}$. Hence, it is natural to view
the Fourier expansion of $f$ as divided into ‘levels’, where the $d$’th level
of $f$, defined as $f^{=d}=\sum_{|S|=d}\hat{f}(S)\chi_{S}$, is included in the
eigenspace that corresponds to the eigenvalue $\rho^{|S|}$ of the noise
operator. An extremely useful corollary of the hypercontractive inequality for
Boolean-valued functions is the so-called level-$d$ inequality:

######  Theorem 1.2.

For any $f:(\\{0,1\\}^{n},\mu_{1/2})\to\\{0,1\\}$, and for any $d\leq
2\log(1/\mathbb{E}[f])$, we have

$\|f^{=d}\|_{2}^{2}\leq\mathbb{E}[f]^{2}\left(2e\frac{\log(1/\mathbb{E}[f])}{d}\right)^{d}.$

Kahn, Kalai, and Linial [28] used a variant of Theorem 1.1 for
$\\{-1,0,1\\}$-valued functions to show that any function
$f:\\{0,1\\}^{n}\to\\{0,1\\}$ whose expectation is bounded away from $0$ and
$1$ has an influential variable, and Friedgut [19] used it to show that if the
sum of the influences of the variables on $f$ is small, then $f$ depends on
only a few variables.

This landscape breaks down as one moves from the uniform measure $\mu_{1/2}$
on $\\{0,1\\}^{n}$ to more general finite product spaces, and in particular,
to the biased measure $\mu_{p}$ on $\\{0,1\\}^{n}$ (defined as
$\mu_{p}(x)=p^{\sum x_{i}}(1-p)^{n-\sum x_{i}}$), which plays a central role
in applications of analysis of Boolean functions to threshold phenomena (see,
e.g., [6, 20]). In the biased measure setting, the characters $\chi_{S}$ in
the Fourier expansion have the form $\chi_{S}=\prod_{i\in
S}\frac{x_{i}-p}{\sqrt{p(1-p)}}$. Hence, the function $f(x)=x_{i}$ has the
Fourier expansion

$f(x)=p+\sqrt{p(1-p)}\frac{x_{1}-p}{\sqrt{p(1-p)}}=p+\sqrt{p(1-p)}\chi_{i}.$

Thus, $\|f\|_{2}=\sqrt{p}$ and $\|T_{\rho}f\|_{q}\geq\rho\cdot p^{1/q}$, which
means that $\rho$ must be as small as $O(p^{1/2-1/q})$, for Theorem 1.1 to
hold. Similarly, $\|f^{=1}\|_{2}^{2}=p(1-p)\approx\mathbb{E}[f]$, and thus, a
‘correction factor’ of order at least $\Omega(p\log(1/p))^{-d}$ is needed in
order to fix Theorem 1.2. (In both cases, these ‘corrections’ are sufficient;
see [34, 44]).

As a result, the Kahn-Kalai-Linial theorem and Friedgut’s theorem do not hold
for general functions with respect to $\mu_{p}$ where $p=o(1)$, and numerous
deep works obtained variants of them for restricted classes of functions,
which rule out counterexamples like the aforementioned $f(x)=x_{i}$ (e.g.,
[20, 24]).

###  1.2 The results of Keevash et al. – qualitative hypercontractivity for
global functions

In the breakthrough work [33], Keevash, Lifshitz, Long, and Minzer obtained a
generalization of the hypercontractive inequality to the biased measure on the
cube, under the additional assumption that the function $f$ is _global_ ,
i.e., is not significantly affected by a restriction of a small set of
coordinates. Formally, for each $S\subset[n]=\\{1,2,\ldots,n\\}$, define the
generalized influence $I_{S}(f)$ as

$I_{S}(f)=\mathbb{E}_{\mu_{p}}\left[\left(\sum_{x\in\\{0,1\\}^{|S|}}(-1)^{|S|-\sum
x_{i}}f_{S\to x}\right)^{2}\right],$

where the restriction $f_{S\to x}:\\{0,1\\}^{[n]\setminus S}\to\mathbb{R}$ is
defined by $f_{S\to x}(y)=f(x,y)$. The main result of [33] for
$(\\{0,1\\}^{n},\mu_{p})$ reads as follows.

######  Theorem 1.3.

Let $q>2$ and let $\rho<(2q)^{-1.5}$. Let
$f:(\\{0,1\\}^{n},\mu_{p})\to\mathbb{R}$, and assume that
$I_{S}(f)\leq\beta\|f\|_{2}^{2}$ for all $S\subset[n]$. Then
$\|T_{\rho}f\|_{q}\leq\beta^{1/2-1/q}\|f\|_{2}$.

The novel technique of Keevash et al. allowed them to prove a stronger variant
of Bourgain’s sharp threshold theorem [20, appendix], to make progress on the
inverse problem for the isoperimetric inequality on the Boolean cube [27], and
to obtain a $p$-biased analogue of the invariance principle of Mossel,
O’Donnell and Oleszkiewicz [42]. Even more recently, this technique was used
in [13] to give a much shorter proof of the breakthrough result of Khot,
Minzer and Safra on expansion of the Grassmann graph [36] which was the main
mathematical ingredient in the proof of the 2-to-2 games conjecture in
complexity theory.

However, Theorem 1.3 is not sharp in terms of the noise rate $\rho$, and this
precludes applications to settings where a sharp version is crucial, such as
various applications to the symmetric group $S_{n}$. Likewise, a sharp version
of Theorem 1.2 for the biased measure on the hypercube (without a ‘correction
factor’ that depends on $p$) is not known.

###  1.3 Our results

In this paper we present sharp versions of the hypercontractive inequality and
of the level-$d$ inequality for global functions over general finite product
spaces.

######  Theorem 1.4.

Let $q\geq 2$ and let $(\Omega,\mu)$ be a finite probability space. Let
$f\colon(\Omega^{n},\mu^{n})\to\mathbb{R}$, and assume that

$\|f_{S\to x}\|_{2}\leq r^{|S|}\|f\|_{2}$

for all $S\subset[n]$ and for all $x\in\Omega^{S}$. If $r\geq 1$ and
$\rho\leq\frac{\log q}{32rq}$, then $\|T_{\rho}f\|_{q}\leq\|f\|_{2}$.

The classical hypercontractive inequality (i.e., Theorem 1.1) implies that if
$f:(\\{0,1\\}^{n},\mu_{1/2})\to\mathbb{R}$ is a linear function, then
$\|f\|_{q}\leq\sqrt{q}\|f\|_{2}.$ This corresponds to the behaviour of
Gaussian random variables $X$, which satisfy
$\|X\|_{q}=\theta(\sqrt{q}\|X\|_{2}).$ When we switch from the uniform measure
on the Boolean cube to the general product space setting, a new phenomenon
arises, where functions behave like Poisson random random variables, which
satisfy $\|X\|_{q}=\Theta(\frac{q}{\log q}\|X\|_{2}).$ Theorem 1.4, which
demonstrates this phenomenon, is sharp for functions of general degree. This
can be observed by inspecting the function
$f:(\\{0,1\\}^{n},\mu_{p})\to\mathbb{R}$, defined by

$f=\prod_{j=0}^{d-1}\left(\sum_{i=1}^{n/d}(x_{j(n/d)+i}-p)\right),$

where $p=\frac{d}{n}$ and $d$ divides $n$, as is shown in Proposition 4.10
below.

By relying on a slightly more involved version of Theorem 1.4 (namely, Theorem
4.5 and Corollary 4.7), we prove the following.

######  Theorem 1.5.

There exists a constant $C>0$ such that the following holds. Let
$(\Omega,\mu)$ be a finite probability space, and let
$f\colon(\Omega^{n},\mu^{n})\to\\{0,1\\}$. Assume that for some $r>1$ and
$d\leq\frac{1}{4}\log(1/\mathbb{E}[f])$, we have $\mathbb{E}[f_{S\to x}]\leq
r^{|S|}\mathbb{E}[f]$ for all sets $S$ of size $\leq d$ and all
$x\in\Omega^{S}.$ Then

$\|f^{=d}\|_{2}^{2}\leq\mathbb{E}^{2}[f]\left(\frac{Cr^{2}\log(1/\mathbb{E}[f])}{d}\right)^{d}.$

For constant values of $r$, Theorem 1.5 is tight, up to the value of $C$. To
see this, consider the function
$f=\mathrm{AND}_{t}\colon\\{0,1\\}^{n}\to\\{0,1\\}$ defined by $f(x)=1$ if and
only if $x_{1}=x_{2}=\cdots=x_{t}=1.$ It is is easy to see that for all $d\leq
t$ we have

$\|f^{=d}\|_{2}^{2}\geq\mathbb{E}^{2}[f]\left(\frac{c\log(1/\mathbb{E}[f])}{d}\right)^{d},$

for an absolute constant $c$. This tightness example for the classical
level-$d$ inequality (i.e., Theorem 1.2) can be lifted to a tightness example
for Theorem 1.5 with respect to an arbitrary uniform product space
$\left(\mathbb{Z}/m\mathbb{Z}\right)^{n},$ with $m$ even, by applying $f$ to
the input modulo 2.

We remark that in order to obtain Theorem 1.5, it is crucial to use our
Theorem 1.4 in place of Theorem 1.3 of Keevash et al. Indeed, if instead we
have tried to apply Theorem 1.3, our $\log(1/\mathbb{E}[f])$ factor would have
been replaced by its cube $\log^{3}(1/\mathbb{E}[f])$. Saving on the power of
$\log(1/\mathbb{E}[f])$ is crucial in the applications of our theorem: while
Theorem 1.5 is applicable for sets of density as small as $2^{-\Omega(n)}$, a
weaker variant with a $\log^{3}(1/\mathbb{E}[f])$ factor is applicable only
when the density is at least $2^{-O(n^{1/3})}$.

##### Our techniques.

Unlike the proof of Theorem 1.3 which proceeds by replacing the coordinates of
the function one-by-one by Gaussians and tracking the ‘cumulative error’, our
proof of Theorem 1.4 follows the proof strategy of the classical
hypercontractive inequality – proving the assertion for $n=1$ and then
leveraging the result to a general $n$ by tensorization. A crucial element of
our proof is the use of several different notions of globalness – most
notably, a notion based on bounding discrete derivatives of the function
rather than its restrictions. While the notions coincide when the ‘globalness
parameter’ is larger than $1$, for smaller values of the globalness parameter
the globalness of the derivatives is not fully captured by the behavior of the
restrictions of the functions, and hence, the stronger ‘derivative-based’
notion is needed. We show that if $f$ satisfies ‘restriction-globalness’ with
respect to both the $L^{1}$ and the $L^{2}$ norms then $f^{=d}$ satisfies
‘derivative-based globalness’, and this allows us to leverage results which we
obtain in the stronger derivative-based setting to results in the restriction-
based setting of [33].

##### Applications.

The sharpness of Theorems 1.4 and 1.5 allows applying the ‘global
hypercontractivity’ technique in a wide range of settings where the
qualitative results of Theorem 1.3 are insufficient. We demonstrate this in
the two following sections, by presenting strong quantitative bounds on the
size of ‘smeared’ intersecting families of sets and vectors, and by describing
a variety of results on functions on the symmetric group – including
hypercontractivity and level-$d$ inequalities, character bounds, variants of
Roth’s theorem and of Bogolyubov’s lemma, and diameter bounds, that were
obtained using our techniques.

###  1.4 Quantitative bounds on the size of smeared intersecting families

A family $\mathcal{F}$ of sets is called _intersecting_ if for any
$A,B\in\mathcal{F}$, $A\cap B\neq\emptyset$. The classical Erdős-Ko-Rado
theorem [15] asserts that for any $k<n/2$, the maximal size of an intersecting
family of $k$-element subsets of $[n]$ is $\binom{n-1}{k-1}$. The Erdős-Ko-
Rado theorem is the cornerstone of a large field of research, which studies
extremal problems on families of sets or other objects, under various
conditions on their intersections (see the survey [18]).

A common feature of the Erdős-Ko-Rado theorem and of many other central
results in the field is that the extremal examples are obtained by ‘juntas’ –
families $\mathcal{F}$ that depend on a few variables (which formally means
that there exists a small $S\subset[n]$ and some $J\subset S$, such that
$A\in\mathcal{F}$ if and only if $A\cap S=J$). This naturally gives raise to
the question, whether a _smeared_ intersecting family – namely, an
intersecting family on which ‘many’ variables have a ‘large’ influence – must
be significantly smaller than the Erdős-Ko-Rado maximum value.

In recent years, numerous _qualitative_ results in this spirit were obtained
in various settings, asserting that if an intersecting family is ‘symmetric’
in some sense (e.g., is transitive symmetric, or is regular, which means that
any element of the ground set is included in the same number of sets of the
family), then its size is much smaller than the maximal size of an
intersecting family in the same setting [8, 9, 11, 26, 32]. However, the
bounds these results yield on the size of the family are far from optimal. The
only effective bound was obtained recently by Kupavskii and Zakharov [38], who
used the techniques developed in the breakthrough result of Alweiss et al. [1]
on the Sunflower Lemma to show that for any $k<cn/\log n$, the maximum size of
a regular intersecting family of $k$-element subsets of $[n]$ is
$\exp(-\Omega\left(\frac{n}{k}\right))\binom{n}{k}$ (which is almost tight, as
was shown in [37]).

Using our sharp hypercontractivity results, we obtain an effective bound on
the measure (or size) of intersecting families, under the weaker assumption
that the family is _smeared_ – namely, that ‘many’ variables have a non-
negligible influence on it, even if it is far from being transitive symmetric
or regular. Formally, we identify a family $\mathcal{F}\subset\\{0,1\\}^{n}$
with the Boolean-valued function $f=1_{\mathcal{F}}$. We denote
$\delta(f)=\max_{i}|\hat{f}(\\{i\\})|$, and
$m(f)=|\\{i:\hat{f}(\\{i\\})^{2}\geq\frac{\delta(f)^{2}}{2}\\}|$, where the
Fourier coefficients are taken w.r.t. the measure $\mu_{p}$. We say that $f$
is a _smeared level- $1$ function_ or is just _smeared_ if $m(f)\geq 1/p^{2}$.
We prove the following.

######  Theorem 1.6.

There exist $c_{1},c_{2}>0$ such that the following holds. Let $\mathcal{F}$
be an intersecting family, and assume that $1/\sqrt{m(1_{\mathcal{F}})}\leq
p\leq 1/2$. Then $\mu_{p}(\mathcal{F})\leq c_{1}\exp\left(-c_{2}/p\right)$.

As we show in Section 6, for any $p>1/\sqrt{n}$ the assertion of the theorem
is tight, up to a factor of $O(\log(1/p)\log n)$ in the exponent. Since a
‘regular’ family $\mathcal{F}$ is clearly smeared (having all first-level
Fourier coefficients of $1_{\mathcal{F}}$ equal), Theorem 1.6 implies the
result of Kupavskii and Zakharov [38] for any $k>\sqrt{n}$, up to the constant
factors $c_{1},c_{2}$, while being applicable for a much wider range of
functions.

We also obtain the following quantitative result for _vector-intersecting_
families – namely, for families $\mathcal{A}\subset[k]^{n}$ such that for any
$x,y\in\mathcal{A}$ there exists $i$ such that $x_{i}=y_{i}$.

######  Theorem 1.7.

There exist $c_{1},c_{2}>0$ such that the following holds. Let $n,k$ be
natural numbers such that $2\log n\leq k\leq\sqrt{n}\log n$. Let
$\mathcal{A}\subseteq[k]^{n}$ be a transitive-symmetric vector-intersecting
family. Then

$\frac{|\mathcal{A}|}{k^{n}}\leq c_{1}\exp\left(-\frac{c_{2}k}{\log
n}\right).$

For $k>\sqrt{n}\log n$, we have $\frac{|\mathcal{A}|}{k^{n}}\leq
c_{1}\exp\left(-c_{2}\sqrt{n}\right)$.

As we show in Section 6, for any $2\log n\leq k\leq\sqrt{n}\log n$, the
assertion of the theorem is tight, up to a factor of $O(\log k\log^{2}n)$ in
the exponent. Theorem 1.7 is the first quantitative upper bound in the vector-
intersecting setting, after qualitative results were obtained in [8, 9, 32].

###  1.5 Follow-up works

Since the initial version of our results was presented in [41], our Theorems
1.4 and 1.5 were used to obtain a variety of results concerning subsets of
$S_{n}$ and functions on $S_{n}$.

####  1.5.1 Intersection problems for families of permutations

A family $\mathcal{F}$ of permutations is called _$t$ -intersecting_ if for
any $\sigma,\tau\in\mathcal{F}$, there exist $i_{1},\ldots,i_{t}$ such that
$\sigma(i_{j})=\tau(i_{j})$, and is called $(t-1)$-avoiding if for any
$\sigma,\tau\in\mathcal{F}$, $|\\{i:\sigma(i)=\tau(i)\\}|\neq t-1$. Deza and
Frankl [17] conjectured that for all $n\geq n_{0}(t)$, the maximum size of a
$t$-intersecting family is $(n-t)!$. Cameron [7] conjectured that equality is
obtained only for the families of the form
$\mathcal{F}=\\{\sigma:\sigma(i_{1})=j_{1},\ldots,\sigma(i_{t})=j_{t}\\}$, for
some $i_{1},\ldots,i_{t},j_{1},\ldots,j_{t}$. Ellis, Friedgut and Pilpel [10]
conjectured that the same holds for $(t-1)$-avoiding families.

In recent years, both problems attracted significant attention. For
$t$-intersecting families, Ellis, Friedgut and Pilpel [10], Ellis and Lifshitz
[14], and Kupavskii and Zakharov [38] showed that the conjectures of Deza and
Frankl and of Cameron hold for all $k$ up to $O(\log\log n)$, $O(\log
n/\log\log n)$, and $O(n/\log^{2}n)$, respectively. For $(t-1)$-avoiding
families, Ellis and Lifshitz [14] and Kupavskii and Zakharov [38] proved the
conjectures for $k$ up to $O(\log n/\log\log n)$ and $\tilde{O}(n^{1/3})$,
respectively. Each of the works [10, 14, 38] introduced entirely new tools
into the study of these problems.

In [35], Keller, Lifshitz, Minzer and Sheinfeld used Theorem 1.5 to show that
the conjectures of Deza and Frankl and of Cameron hold for all $t\leq O(n)$ in
the $t$-intersecting setting and for all $t\leq O(\sqrt{n}/\log n)$ in the
$(t-1)$-avoiding setting, thus obtaining a significant advancement on both
problems.

####  1.5.2 Hypercontractivity and level-$d$ inequality in the symmetric group

While the symmetric group $S_{n}$ is not a product space, it behaves like the
product space $[n]^{n}$ (endowed with the uniform measure) in various aspects.
In particular, Filmus, Kindler, Lifshitz, and Minzer [16] found a way to
deduce a hypercontractive inequality for functions over $S_{n}$ from a
corresponding hypercontractive inequality for $[n]^{n}$. However, their
reduction was lossy in the parameters.

In [31], Keevash and Lifshitz found a way to make this reduction essentially
loss-less and obtained analogues of our main results (Theorems 1.4 and 1.5) to
functions over $S_{n}$, by reducing each analogue result for $S_{n}$ to the
corresponding statement that we proved for $[n]^{n}$. To present the results
of [31], a few more definitions are needed. A function on $S_{n}$ is said to
be of _degree_ $d$ if it can be written as a linear combination of products of
$d$ _dictators_ $1_{\sigma(i)=j}$. Given $m$-tuples of distinct coordinates
$I,J$ the function $f$ can be restricted to the set of permutations sending
$I$ to $J$. The restriction is denoted by $f_{I\to J}$. We say that $f$ is
$(r,\gamma)$-_global_ if for any $m$ and for all $m$-tuples $I,J$, we have
$\|f_{I\to J}\|_{2}\leq r^{m}\gamma$. The authors of [31] proved the following
analogue of Theorem 1.4.

######  Theorem 1.8 ([31]).

There exists an absolute constant $C>0$ and a family of self adjoint operators
$\mathrm{T}_{\rho}$ with the following properties.

  1. 1.

(Large degree $d$ eigenvalues) Let $d$ be an integer. If $f\colon
S_{n}\to\mathbb{R}$ is a function of degree $\leq d$, then

$\left\langle\mathrm{T}_{\rho}f,f\right\rangle\geq\left(\frac{\rho}{C}\right)^{d}\|f\|_{2}^{2}.$

  2. 2.

Let $q\geq 2$. If $f$ is $\left(r,\gamma\right)$-global, and
$\rho\leq\frac{\log q}{Crq}$, then

$\|\mathrm{T}_{\rho}f\|_{q}^{q}\leq\gamma^{q-2}\|f\|_{2}^{2}.$

  3. 3.

The operator $\mathrm{T}_{\rho}$ commutes with the action of $S_{n}$ from both
sides.

A function $f$ on $S_{n}$ is said to be $(r,\gamma_{2},\gamma_{1})$-_biglobal_
if for any $m$ and for all $m$-typles $I,J$ we have $\|f_{I\to J}\|_{2}\leq
r^{m}\gamma_{2}$ and $\|f_{I\to J}\|_{1}\leq r^{m}\gamma_{1}$. For a function
$f\colon S_{n}\to\mathbb{R}$, we write $f^{=d}$ for the projection of $f$ onto
the space of degree $\leq d$ functions that are orthogonal to all degree $\leq
d-1$ functions. Using Theorem 5.4 (which is a slightly more general version of
Theorem 1.5), the authors of [31] proved the following analogue of Theorem
1.5.

######  Theorem 1.9.

There exists $C>0$ such that the following holds. Let $r\geq 1$ and let
$f\colon S_{n}\to\left\\{0,1\right\\}$ be an $r$-biglobal function. Let
$\alpha=\mathbb{E}\left[f\right]$ and let $d\leq\log\left(1/\alpha\right).$
Then

$\|f^{=d}\|_{2}^{2}\leq\left(\frac{Cr}{d}\right)^{2d}\alpha^{2}\log^{d}\left(1/\alpha\right).$

This allowed accomplishing the following results.

####  1.5.3 An analogue of Bogolyubov’s lemma for $A_{n}$

Bogolyubov’s lemma for finite fields says (in the special case of binary
fields) that if $A\subseteq\mathbb{F}_{2}^{n}$ has density $\geq\alpha,$ then
$A+A+A+A$ contains an affine linear subspace of codimension $O(1/\alpha)$
(see, e.g., [49]). It is one of the main ingredients in the classical proof of
the Freiman-Ruzsa theorem. The main disadvantage of using Bogolyubov’s lemma
in the Abelian setting is the fact that the density of the subspace whose
existence is guaranteed is exponentially smaller than the density of the
original set. Had the dependency been polynomial, it would have implied the
polynomial Freiman–Ruzsa conjecture. Keevash and Lifshitz [31] used our
Theorem 1.5 to prove an analogue of Bogolyubov’s lemma for the alternating
group, with subspaces replaced by $m$-umvirates (that is, families of the form
$\\{\sigma\in S_{n}:\sigma(i_{1})=j_{1},\ldots,\sigma(i_{m})=j_{m}\\}$, for
some fixed $i_{1},\ldots,i_{m},j_{1},\ldots,j_{m}$). In their setting, the
measure of the $m$-umvirates is polynomial in the density, provided that the
density is at least $e^{-cn^{0.99}}$. We say that a set $A$ is _symmetric_ if
$A=A^{-1}.$ We write $AB=\\{ab:\,a\in A,B\in B\\}$, and $A^{i}$ for the
$i$-fold product of $A$ with itself.

######  Theorem 1.10 ([31]).

There exist absolute constants $C,c>0$, such that the following holds. Let
$\zeta>\frac{1}{\log n}$ and let $A\subseteq A_{n}$ be a symmetric set having
density $\geq e^{-cn^{1-\zeta}}$. For any integer $M\geq\frac{C}{\zeta^{2}}$,
the set $A^{M}$ contains an $m$-umvirate for some $m$-umvirate of density
$\geq\mu(A)^{M}.$

####  1.5.4 An analogue of Roth’s theorem for $S_{n}$

Keevash and Lifshitz [31] also considered the problem of determining the
largest set $A\subseteq S_{n}$ that does not contain a solution to the
equation $xz=y^{2}$ – that is, the problem of finding the strongest possible
analogue for $S_{n}$ of the classical theorem of Roth [47] on arithmetic
progressions. They used Theorem 1.9 to show that if $A\subseteq S_{n}$ does
not contain a solution to the equation $xz=y^{2},$ then $\mu(A)\leq n^{-c\log
n}$ for an absolute constant $c$.

Extensions of Roth’s theorem to nonabelian groups are well studied (see, e.g.,
[4], [46], and [48]). The more thoroughly studied extension of Roth’s theorem
concerns triples of the form $(x,xg,xg^{2})$. In that setting, the extremal
problem of how large can a family $A\subset S_{n}$ be, if it contains no
nontrivial triple of the form $(x,xg,xg^{2})$, is not that interesting, as
this question can be reduced to the Abelian setting by inspecting left cosets
of Abelian subgroups.

The previous works got rid of these trivialities by studying instead the
mixing variant, where one wants to show that the triple $(x,xg,xg^{2})$
behaves in some senses like an independent triple. The authors of [31] were
interested in the extremal problem, and therefore, they considered families
$A\subset S_{n}$ with no solutions of the equation $xz=y^{2}$, where the
reduction to the Abelian setting no longer exists.

####  1.5.5 Diameter bounds for $S_{n}$

The distance between two vertices in a graph is the number of edges in the
shortest path that connects them. The _diameter_ of a graph is the largest
distance between two vertices. For a group $G$ and $A\subset G$, the _covering
number_ of $A$ is the minimal $\ell$ for which $A^{\ell}=G.$ The diameter of a
Cayley graph $\mathrm{Cay}(G,A)$ is equal to the covering number of $A$.

The problem of determining covering numbers of sets $A\subseteq G$ is well
studied for finite simple groups. A striking result of Liebeck and Shalev [40]
solves this problem completely when $G$ is a finite simple group and $A$ is a
conjugacy class. They showed that the covering number of such conjugacy
classes is always $\Theta\left(\log_{|A|}{|G|}\right).$

For the groups $S_{n}$ and $A_{n}$, a well-known longstanding folklore
conjecture asserts that the diameter of any connected Cayley graph on $A_{n}$
or on $S_{n}$ is polynomial in $n$ (see [2]). A celebrated result of Helfgott
and Seress [25] shows a quasi-polynomial upper bound on the diameter, while
Nikiolov and Pyber [43] showed that Gowers’ [22] result about product mixing
implies that any set in $A_{n}$ of density $\geq(n-1)^{1/3}$ has covering
number 3.

Following Nikiolov and Pyber [43], Keevash, and Lifshitz [31] considered the
following more general problem: What is the largest possible diameter of a
connected Cayley graph $\mathrm{Cay}(A_{n},A)$ for a set $A$ of density
$\alpha$? One example to keep in mind is the union of the $t$-umvirates of all
permutations fixing $\\{1,\ldots,t\\}$ with the set of transpositions
$\\{(1,2),(2,3),\ldots,(t,t+1)\\},$ whose covering number is $\theta(t^{2}).$
The authors of [31] showed that for a fixed $\zeta$ and $\alpha\geq
e^{-n^{1-\zeta}}$, the above construction is sharp up to a constant. Namely,
they showed that if $A$ has density $\geq\max(n^{-t},e^{-n^{1-\zeta}}),$ then
the diameter of the Cayley graph $\mathrm{Cay}(A_{n},A)$ is at most
$C/\zeta^{2}t^{2},$ where $C$ is an absolute constant. This essentially solves
this problem completely for sets $A$ of density $\geq e^{-cn}.$

####  1.5.6 Character bounds in the symmetric group

Lifshitz and Marmor [12] used Theorem 1.8 to obtain the following bound on the
norms of the characters.

######  Theorem 1.11.

There exists an absolute constant $C>0$, such that the following holds. Let
$q\geq 2$ and $d<n/10$. Let $\lambda$ be a partition of $n$ and suppose that
$\lambda_{1}=n-d$. Then $\|\chi_{\lambda}\|_{q}\leq\left(\frac{Cq}{\log
q}\right)^{d}\left(\frac{\chi_{\lambda}(1)d^{d}}{n^{d}}\right)^{1-2/q}.$

They also showed that their bound is sharp, up to the value of the constant
$C$. This allowed the authors of [12] to show that there exits an absolute
constant $c>0$, such that for every conjugacy class $A$ of $S_{n}$ of density
$\frac{|A|}{n!}\geq e^{-c\sqrt{n}\log n}$, the mixing time of the Cayley graph
$\mathrm{Cay}(A_{n},A)$ is at most two. The lower bound $e^{-c\sqrt{n}\log n}$
on the density of $A$ is optimal, up to the value of the implicit constant
$c$. This allowed them to improve various results of Larsen and Shalev [39] on
character bounds, diameter bounds, and mixing of conjugacy classes.

###  1.6 Organization of the paper

In Section 2 we present basic notions and lemmas that will be used throughout
the paper. In Section 3 we show that norms of the noise operator can be
bounded using the norms of certain ‘Gaussian encodings’ of the function. The
proofs of the sharp hypercontractive inequality for global functions (namely,
Theorem 1.4) and of the sharp level-$d$ inequality (namely, Theorem 1.5) are
presented in Sections 4 and 5, respectively. Finally, we apply our results to
bound the size of smeared intersecting families of sets and vectors in Section
6.

##  2 Background

###  2.1 Functions over the hypercube

As was mentioned above, the classical results in discrete Fourier analysis
were obtained for functions $f:\\{0,1\\}^{n}\to\mathbb{R}$, where the
hypercube $\\{0,1\\}^{n}$ is endowed with the product measure
$\mu_{p}(x)=p^{|\\{i:x_{i}=1\\}|}(1-p)^{|\\{i:x_{i}=0\\}|}$. While in this
paper we consider functions over general finite product spaces, we begin with
presenting the hypercube case, and then develop the notions for the general
case as generalizations of the ‘hypercube case’ notions.

##### Fourier expansion.

Denote $[n]=\\{1,2,\ldots,n\\}$. For each $i\in[n]$, let
$\chi_{i}(x)=\frac{x_{i}-p}{\sqrt{p(1-p)}}$, and for each $S\subset[n]$, let
$\chi_{S}=\prod_{i\in S}\chi_{i}$. It can be easily verified that the set of
characters $\\{\chi_{S}\\}_{S\subset[n]}$ is an orthonormal basis for the
space of functions $\mathcal{U}_{n}=\\{f:\\{0,1\\}^{n}\to\mathbb{R}\\}$ with
respect to the standard inner product $\langle f,g\rangle=\mathbb{E}[fg]$.
Hence, each $f\in\mathcal{U}_{n}$ can be uniquely represented as
$f=\sum_{S\subset[n]}\hat{f}(S)\chi_{S}$, where $\hat{f}(S)=\langle
f,\chi_{S}\rangle$. This expansion is called the Fourier expansion of $x$.

##### Restrictions, derivatives, and influences.

For $f\in\mathcal{U}_{n}$ and $S\subset[n]$, the _restriction_ $f_{S\to
x}:\\{0,1\\}^{[n]\setminus S}\to\mathbb{R}$ is defined as $f_{S\to
x}(y)=f(x,y)$ for all $y\in\\{0,1\\}^{[n]\setminus S}$. The _discrete
derivative_ in the $i$’th direction is defined as
$D_{i}(f)=\sqrt{p(1-p)}\cdot(f_{i\to 1}-f_{i\to 0})$. The _influence_ of the
$i$’th coordinate on $f$ is $I_{i}(f)=||f_{i\to 1}-f_{i\to 0}||_{2}^{2}$. The
discrete derivative can be applied sequentially, to obtain

$D_{S}(f)=\sqrt{p(1-p)}^{|S|}\sum_{x\in\\{0,1\\}^{S}}(-1)^{|S|-|\\{i:x_{i}=1\\}|}f_{S\to
x}.$

Discrete derivatives (and subsequently, influences) have a convenient
representation in terms of the Fourier expansion:

$D_{S}(f)=\sum_{T:S\subset T}\hat{f}(T)\chi_{T\setminus
S},\qquad\mbox{and}\qquad I_{i}(f)=\frac{1}{p(1-p)}\sum_{S:i\in
S}\hat{f}(S)^{2}.$

##### The noise operator.

For $0<\rho<1$, let $N_{\rho}(x)$ be obtained from $x$ by leaving each
coordinate $x_{i}$ of $x$ unchanged with probability $\rho$ and replacing it
by a random $y_{i}\sim\mu_{p}(\\{0,1\\})$ with probability $1-\rho$. The noise
operator $T_{\rho}:\mathcal{U}_{n}\to\mathcal{U}_{n}$ is defined by
$T_{\rho}f(x)=\mathbb{E}_{y\sim N_{\rho}(x)}T(y)$. It can be easily verified
that the eigenvectors of the noise operator are precisely the characters
$\\{\chi_{S}\\}$, and that for any $f=\sum_{S}\hat{f}(S)\chi_{S}$, we have
$T_{\rho}f=\sum_{S}\rho^{|S|}\hat{f}(S)\chi_{S}$.

For more details on the above classical definitions and their properties, the
reader is referred to [44].

###  2.2 Functions over general finite product spaces

Let $(\Omega,\mu)$ be a finite probability space, and let
$(\Omega^{n},\mu^{n})$ be the product space, where $\mu^{n}$ is the product
probability measure. We will mostly omit the superscript $n$ in the expression
$\mu^{n}$, when the dimension is clear from context. For $S\subseteq[n]$ we
denote by $\Omega^{S}$ the projection of $\Omega^{n}$ that leaves only the
coordinates in $S$, and $\mu^{S}$ will be the corresponding projected measure.
We denote by $L^{2}(\Omega,\mu)$ the space of real-valued functions on
$\Omega$.

In the case of the hypercube, for $f=\sum_{S}\hat{f}(S)\chi_{S}$, the term
$\hat{f}(S)\chi_{S}$ represents the ‘part of $f$ which depends precisely on
$S$’. The Efron-Stein decomposition generalizes this property to functions
over general spaces. It will be convenient for us to introduce the Efron-Stein
decomposition using the two following operators.

##### Laplacians and averages.

In the one-dimensional case, the _Laplacian_ operator $L$ is defined using the
expectation operator $E$: For any $g:\Omega\to\mathbb{R}$,

$Eg=\mathbb{E}[g],\quad\mbox{and}\quad Lg=g-Eg.$

For functions $\\{f_{i}\colon\Omega\to\mathbb{R}\\}_{i\in[n]}$, we write
$f_{1}\otimes\cdots\otimes f_{n}$ for the function $f:\Omega^{n}\to\mathbb{R}$
defined by $x\mapsto\prod_{i=1}^{n}f_{i}(x_{i}).$ For linear operators
$T_{i}\colon L^{2}(\Omega,\mu)\to L^{2}(\Omega,\mu)$ we define
$T_{1}\otimes\cdots\otimes T_{n}:L^{2}(\Omega^{n},\mu)\to
L^{2}(\Omega^{n},\mu)$ by setting $f_{1}\otimes\cdots\otimes f_{n}\mapsto
T_{1}f_{1}\otimes\cdots\otimes T_{n}f_{n}$ and extending linearly.

We can now generalize the expectation operator and the Laplacian to the
$n$-dimensional case by taking tensors with the identity operator. For each
$i\in[n]$, we set

$E_{i}f=(I\otimes\cdots\otimes\underbrace{E}_{i}\otimes\cdots\otimes I)f,\quad
L_{i}f=(I\otimes\cdots\otimes\underbrace{L}_{i}\otimes\cdots\otimes I)f.$

More generally, for $S\subset[n]$,

$E_{S}[f](x)=\bigotimes_{i\in S}E_{i}\otimes\bigotimes_{i\notin
S}\text{id},\quad L_{S}f=\bigotimes_{i\in S}L_{i}\otimes\bigotimes_{i\in
S^{c}}\text{id}.$

Combinatorially, the operator $E_{S}$ is the expected value obtained when
resampling the coordinates in $S$ according to $\mu$. The Laplacians $L_{S}$
have a combinatorial description in terms of the averaging operators $E_{S}$:
For any $S\subset[n]$, we have $L_{S}=\sum_{T\subseteq S}(-1)^{|T|}E_{T}$.

##### The Efron-Stein decomposition.

In the one-dimensional case, the space $L^{2}(\Omega,\mu)$ can be partitioned
into two parts: $V_{=\varnothing}$, which consists of constant functions, and
$V_{=\\{1\\}}$, which consists of functions with expectation $0$. The
projection on $V_{=0}$ is the averaging operator $E$ and the projection on
$V_{=\\{1\\}}$ is the Laplacian $L=f-\mathbb{E}[f].$

To generalize this partition to the $n$-dimensional case, we may use
tensorization to obtain the operators

$\\{E_{T^{c}}L_{T}\\}_{T\subseteq[n]}=\bigotimes_{i\in
T}L_{i}\otimes\bigotimes_{i\in T^{c}}E_{i}.$

Using these operations, we may obtain an orthogonal decomposition of the space
$L^{2}(\Omega^{n},\mu)$ into the spaces $V_{=T}=\\{E_{T^{c}}L_{T}[f]:\,f\in
L^{2}(\Omega^{n},\mu)\\}$. Note that the space $V_{=T}$ consists of functions
that depend only on the coordinates in $T$, and thus, serves as a
generalization of the space $\mathrm{span}(\chi_{T})$ from the ‘hypercube’
case, in which we have $E_{T^{c}}L_{T}[f]=\hat{f}(T)\chi_{T}$.

The _Efron-Stein decomposition_ of $f\in L^{2}(\Omega^{n},\mu)$ is

$f=\sum_{T\subset[n]}f^{=T},\qquad\mbox{where}\qquad
f^{=T}=E_{T^{c}}L_{T}[f].$

We write $f^{=d}=\sum_{|S|=d}f^{=S}$.

Note that unlike the hypercube case, the spaces $V_{=T}$ are no longer
1-dimensional. However, they still convey the notion of ‘dependence on exactly
the variables in $T$’, which turns out to be sufficient for our purposes.

The following lemma summarizes basic properties of the Efron-Stein
decomposition. The simple proof is omitted.

######  Lemma 2.1.

Let $V=L^{2}(\Omega^{n},\mu)$.

  1. 1.

The spaces $V^{=T}$ are an orthogonal decomposition of
$L^{2}(\Omega^{n},\mu)$. Therefore, for every $f,g\in V$ we have $\langle
f,g\rangle=\sum_{T\subseteq[n]}\langle f^{=T},g^{=T}\rangle$.

  2. 2.

For any $f\in V$, we have

$L_{S}f=\sum_{T\supseteq S}f^{=T},\qquad\mbox{and}\qquad
E_{S}f=\sum_{T\subseteq S^{c}}f^{=T}.$

For more information on the Efron-Stein decomposition, we refer the reader to
[44, Chapter 8].

##### Restrictions and derivatives.

Like in the hypercube case, for $f\in V$, $S\subset[n]$, and $x\in\Omega^{S}$,
the restriction $f_{S\to x}:\Omega^{[n]\setminus S}\to\mathbb{R}$ is defined
as $f_{S\to x}(y)=f(x,y)$. As was suggested in [32], the discrete derivatives
can be generalized using restrictions of the Laplacians. For all
$S\subseteq[n]$, $x\in\Omega^{n}$, define

$D_{S,x}f=[L_{S}f]_{S\rightarrow x_{S}}.$

We use the same notation when $x\in\Omega^{T}$ for an arbitrary set $T$
containing $S$, and write $D_{i,x}$ instead of $D_{\\{i\\},x}$ for brevity.

##### The noise operator.

The noise operator, defined above in the ‘hypercube’ setting, can be naturally
defined over a general space $(\Omega^{n},\mu)$ as
$T_{\rho}f(x)=\mathbb{E}_{y\sim N_{\rho}(x)}T(y)$, where $N_{\rho}(x)$ be
obtained from $x$ by leaving each coordinate $x_{i}$ of $x$ unchanged with
probability $\rho$ and replacing it by a random $y_{i}\sim\mu$ with
probability $1-\rho$. It can be easily verified that like in the hypercube
case, the eigenspaces of $T_{\rho}$ are exactly the spaces $V^{=T}$, and that
for any $f\in V$, we have

$T_{\rho}f=\sum_{S\subseteq[n]}\rho^{|S|}f^{=S}.$ (2.1)

In particular, it is clear that $T_{\rho}$ is multiplicative: we have
$T_{\rho_{1}}\circ T_{\rho_{2}}=T_{\rho_{1}\cdot\rho_{2}}$.

The following relations between the Laplacian, the derivatives, and the noise
operator, can be easily verified.

######  Lemma 2.2.

Let $f\in V$. Then for any $\rho>0$, any $S\subset[n]$, and any
$x\in\Omega^{S}$, we have

$L_{S}T_{\rho}f=T_{\rho}L_{S}f,\qquad\mbox{and}\qquad
D_{S,x}T_{\rho}f=\rho^{|S|}T_{\rho}D_{S,x}f.$

##  3 Bounding Norms Using Gaussian Encodings

In this section we show that the $q$-norm of the noise operator, namely,
$\|T_{\rho}f\|_{q}$, can be bounded using the norms of certain ‘Gaussian
encodings’ of $f$. This will allow us to reduce the hypercontractive
inequalities we want to prove to the Gaussian setting in which similar
hypercontractive inequalities are known.

###  3.1 Gaussian encodings

Let $(\Omega,\mu)$ be a probability space with $k$ elements, and let
$B=\\{1,f_{1},\ldots f_{k-1}\\}$ be an orthonormal basis for
$L^{2}(\Omega,\mu)$. Let $\gamma$ be the Gaussian probability measure on
$\mathbb{R}^{k-1}$, where the coordinates are independent normal (i.e.,
$N(\mathbf{0},1)$) Gaussian random variables. We define an operator $G\colon
L^{2}(\Omega,\mu)\to L^{2}(\mathbb{R}^{k-1},\gamma)$ by setting

$G(\alpha_{0}+\sum_{i=1}^{k-1}\alpha_{i}f_{i})=\alpha_{0}+\sum_{i=1}^{k-1}\alpha_{i}z_{i}$

for all $\alpha_{0},\ldots,\alpha_{k-1}\in\mathbb{R}$, where $z_{i}$ is the
projection on the $i$’th coordinate. By tensorization, for any $S\subset[n]$
we obtain an operator

$G_{S}\colon L^{2}(\Omega^{n},\mu)\to
L^{2}(\Omega^{S^{c}}\times\left(\mathbb{R}^{k-1}\right)^{S},\mu^{S^{c}}\otimes\gamma^{S}),$

defined by

$G_{S}=\bigotimes_{i\in S}G\otimes\bigotimes_{i\in S^{c}}\text{id}.$

For the sake of convenience, we shorten $G_{\\{i\\}}$ to $G_{i}$.

###  3.2 Bounding norms using the encodings

We aim at showing that $\|T_{\rho}f\|_{q}$ can be bounded using norms of the
encodings $G_{S}(f)$. Specifically, we prove the following:

######  Proposition 3.1.

Let $\rho\leq\frac{1}{3}$, let $q\geq 2$, and let $f\in
L^{2}(\Omega^{n},\mu)$. Then

$\|T_{\rho}f\|_{q}^{q}\leq\sum_{S\subseteq[n]}\beta^{q|S|}\|(L_{S}\circ
G_{S^{c}})f\|_{q}^{q},$

where $\beta=\rho\left(1+\frac{2(q-2)}{\log(1/\rho)}\right)$.

Note that here and throughout the paper, ‘$\log$’ means the natural logarithm.

We prove the proposition in three stages. First, we prove it in the case
$(k=2,n=1)$, where each function $f$ has the form
$f=\alpha_{0}+\alpha_{1}f_{1}$ and we have
$T_{\rho}f=\alpha_{0}+\rho\alpha_{1}f_{1}$. Then, we prove it for general
linear functions, i.e., for $f=\alpha_{0}+\sum_{i=1}^{k-1}\alpha_{i}f_{i}$,
where $T_{\rho}f=\alpha_{0}+\rho\sum_{i=1}^{k-1}\alpha_{i}f_{i}$. Finally, we
deduce Proposition 3.1 from the linear case using tensorization.

####  3.2.1 Linear functions for $k=2$

In this case, we may write $f=\alpha_{0}+\alpha_{1}f_{1}$ and the assertion of
Proposition 3.1 reads

$\|T_{\rho}f\|_{q}^{q}\leq\|G(f)\|_{q}^{q}+\beta^{q}\|\alpha_{1}f_{1}\|_{q}^{q},$
(3.1)

since $L_{\\{1\\}}(\alpha_{0}+\alpha_{1}f_{1})=\alpha_{1}f_{1}$. We prove the
following slightly more general lemma:

######  Lemma 3.2.

Let $0<\rho\leq 1/3$ and $q\geq 2$ be real numbers. Let $X$ be a real random
variable with $\mathbb{E}[X]=0$ and $\mathbb{E}[X^{2}]=1$, and let $Z$ be a
normal Gaussian random variable. Then for any $d\in\mathbb{R}$ we have:

$\|1+\rho dX\|_{q}^{q}\leq\|1+dZ\|_{q}^{q}+\beta^{q}\|dX\|_{q}^{q},$

where $\beta=\rho\left(1+\frac{2(q-2)}{\log(1/\rho)}\right)$.

Lemma 3.2 clearly implies (3.1). Indeed, for $\alpha_{0}=0$ (i.e.,
$f=\alpha_{1}f_{1}$), we have $T_{\rho}f=\rho f$ and hence (3.1) follows from
the inequality $\|\rho f\|_{q}^{q}\leq\beta^{q}\|f\|_{q}^{q}$ which holds
trivially. For $\alpha_{0}\neq 0$, by dividing both sides of (3.1) by
$|\alpha_{0}|^{q}$ we obtain a special case of Lemma 3.2.

###### Proof.

We may assume $q>2$, since it is easy to check that for $q=2$ the claim holds.
Set $\omega=\frac{\log(1/\rho)}{2(q-2)}$, so that
$\beta=\rho(1+\frac{1}{\omega})$. We decompose

$1+\rho dX=\left(1+\rho dX\right)\cdot 1_{\rho|dX|\geq\omega}+\left(1+\rho
dX\right)\cdot 1_{\rho|dX|<\omega},$

to obtain

$\|1+\rho dX\|_{q}^{q}=\|\left(1+\rho
dX\right)1_{\rho|dX|\geq\omega}\|_{q}^{q}+\|\left(1+\rho
dX\right)1_{\rho|dX|<\omega}\|_{q}^{q}.$

When $\rho|dX|\geq\omega$, we have
$\omega+\omega\rho|dX|\leq(1+\omega)\rho|dX|$ and therefore

$\left|1+\rho dX\right|\leq\frac{1+\omega}{\omega}\rho|dX|.$

This allows us to upper bound

$\|1+\rho
dX\|_{q}^{q}\leq\left(\rho\left(1+\frac{1}{\omega}\right)\right)^{q}\|dX\|_{q}^{q}+\|\left(1+\rho
dX\right)1_{\rho|dX|<\omega}\|_{q}^{q}=\beta^{q}\|dX\|_{q}^{q}+\|\left(1+\rho
dX\right)1_{\rho|dX|<\omega}\|_{q}^{q}.$

Hence, it remains to upper bound the second summand by $\|1+dZ\|_{q}^{q}$. To
achieve this, we first prove the following claim:

######  Claim 3.3.

In the above notations, for any $x\in\mathbb{R}$ we have

$\left|1+\rho dx\right|^{q}\,1_{\rho|dx|<\omega}\leq 1+q\rho
dx+\frac{\rho^{-1/2}}{2}(q\rho dx)^{2}.$ (3.2)

###### Proof.

For $w\in\mathbb{R}$ and a positive integer $i$ we write $\binom{w}{i}$ for
$\frac{w(w-1)\cdots(w-i+1)}{i!}$. By taking the Taylor approximation of degree
$1$ of the function $|1+y|^{q}$ at $y=0$, we may write

$|1+y|^{q}=1+qy+\binom{q}{2}|1+y^{\prime}|^{q-2}y^{2},$

for some $y^{\prime}$ in the interval between 0 and $y$. We may upper bound

$|1+y^{\prime}|^{q-2}\leq(1+|y|)^{q-2},$

and when substituting $y=\rho dx$ we get

$(1+\rho|dx|)^{q-2}\leq(1+\omega)^{q-2}\leq e^{\omega(q-2)}=\rho^{-1/2}.$

We therefore obtain that in the domain $\rho|dx|<\omega$,

$|1+\rho dx|^{q}\leq 1+q\rho dx+\frac{\rho^{-1/2}}{2}(q\rho dx)^{2}.$

We are left with the case $\rho|dx|\geq\omega$. In this case, the left hand
side of (3.2) is equal to zero, while the right hand side $1+(q\rho
dx)+\frac{\rho^{-1/2}}{2}(q\rho dx)^{2}$ is positive since for $A>1/4$, we
have $1+x+Ax^{2}>0$ for all $x$. ∎

We now return to the proof of the lemma. Since $\mathbb{E}[X]=0$ and
$\mathbb{E}[X^{2}]=1$, Eq. (3.2) implies

$\|\left(1+\rho dX\right)1_{\rho|dX|<\omega}\|_{q}^{q}\leq
1+\frac{\rho^{1.5}}{2}q^{2}d^{2}\leq 1+\frac{1}{9}q^{2}d^{2}.$

On the other hand, as $\mathbb{E}[Z]=0$, $\mathbb{E}[Z^{2}]=1$,
$\mathbb{E}[1+dZ]=1$, and $q>2$, we may use the Binomial theorem to obtain

$\|1+dZ\|_{q}^{q}\geq\|1+dZ\|_{\lfloor q\rfloor}^{\lfloor q\rfloor}\geq
1+\binom{\lfloor q\rfloor}{2}d^{2}\geq 1+\frac{1}{9}q^{2}d^{2},$

which completes the proof. ∎

####  3.2.2 Linear functions for a general $k$

In this case, we may write $f=\alpha_{0}+\sum_{i=1}^{k-1}\alpha_{i}f_{i}$ and
hence, the assertion of Proposition 3.1 reduces to the following lemma.

######  Lemma 3.4.

Let $\rho\leq 1/3$, $q\geq 2$, and let $f\in L^{2}(\Omega,\mu)$ be a linear
function. Then

$\left\|T_{\rho}[f]\right\|_{q}^{q}\leq\left\|G[f]\right\|_{q}^{q}+\beta^{q}\left\|L[f]\right\|_{q}^{q},$

where $\beta=\rho\left(1+\frac{2(q-2)}{\log(1/\rho)}\right)$.

###### Proof.

Like in the case $k=2$, we may assume without loss of generality that
$\alpha_{0}=1$, and hence, $f=1+\sum_{i=1}^{k-1}\alpha_{i}f_{i}$. In this
case, $\|G[f]\|_{q}^{q}=\|1+\sum_{i=1}^{k-1}d_{i}Z_{i}\|_{q}^{q},$ where
$Z_{i}$ are independent normal Gaussian random variables. Denote
$X=L[f]=\sum_{i=1}^{k-1}d_{i}f_{i}$, $\sigma=\sqrt{\mathbb{E}[X^{2}]}$, and
note that $T_{\rho}[f]=1+\rho X=1+\rho\sigma\frac{X}{\sigma}$. We have
$\mathbb{E}\left[\frac{X}{\sigma}\right]=0$ and
$\mathbb{E}\left[\left(\frac{X}{\sigma}\right)^{2}\right]=1$. By Lemma 3.2
(applied with $d=\sigma$ and $\frac{X}{\sigma}$ in place of $X$), for any
normal Gaussian variable $Z$ we have,

$\left\|T_{\rho}f\right\|_{q}^{q}=\|1+\sigma\frac{X}{\sigma}\|_{q}^{q}\leq\left\|1+\sigma
Z\right\|_{q}^{q}+\beta^{q}\left\|\sigma\frac{X}{\sigma}\right\|_{q}^{q}=\left\|1+\sigma
Z\right\|_{q}^{q}+\beta^{q}\left\|L[f]\right\|_{q}^{q}.$

The assertion of the lemma follows, as $\sigma Z$ has the same distribution as
$\sum_{i=1}^{k-1}\alpha_{i}Z_{i}$, where $Z_{i}$ are independent normal
Gaussian random variables. ∎

####  3.2.3 General functions

Now we are ready to prove Proposition 3.1.

###### Proof.

Let $T_{\rho}^{(i)}$ be the operator $f\mapsto E_{i}[f]+\rho L_{i}[f]$. We may
write $T_{\rho}$ as the composition of the operators $T_{\rho}^{(i)}$, since

$T_{\rho}^{(i)}=(I\otimes\cdots\otimes\underbrace{T_{\rho}}_{i}\otimes\cdots\otimes
I).$

We claim that for any function $g$ we have

$\|T_{\rho}^{(i)}g\|_{q}^{q}\leq\|G_{i}g\|_{q}^{q}+\beta^{q}\|L_{i}f\|_{q}^{q}.$
(3.3)

We will then apply this assertion repeatedly (for $i=1,\ldots,n$) to complete
the proof.

To prove (3.3), we may assume without loss of generality that $i=1$. We may
choose a random input $x\sim\mu$ and write it as $(x_{1},y),$ where $y$
denotes the last $n-1$ coordinates of $x$. Let $\mathrm{ev}_{y}\colon
L^{2}(\Omega^{\\{2,\ldots,n\\}})\to\mathbb{R}$ be the ‘evaluation at $y$’
operator given by $g\mapsto g(y)$. Then the restriction operator $g\mapsto
g_{\\{2,\ldots,n\\}\to y}$ takes the form $I\otimes\mathrm{ev_{y}}$. This
shows that the restriction operator commutes with $T_{\rho}^{(1)},E_{1},$ and
$L_{1}$. We may now apply Lemma 3.4 to the restricted function
$g_{y}:=g_{\\{2,\ldots,n\\}\to y}$ and take expectations to obtain:

$\displaystyle\|T_{\rho}^{(i)}g\|_{q}^{q}=\mathbb{E}_{x}\left[\left|T_{\rho}^{(1)}g(x)\right|^{q}\right]=\mathbb{E}_{y}\left[\|T_{\rho}^{(1)}\left[g_{y}\right]\|_{q}^{q}\right]\leq\operatorname*{\mathbb{E}}_{y}\left[\operatorname*{\mathbb{E}}\left[|G_{\\{1\\}}(g_{y})|^{q}+\beta^{q}|L_{1}g_{y}|^{q}\right]\right]=\|G_{1}g\|_{q}^{q}+\beta^{q}\|L_{1}g\|_{q}^{q},$

where the last equality follows from Fubini’s theorem. This proves (3.3).

We now complete the proof by showing inductively that for every $m\leq n$, we
have

$\|T_{\rho}^{(m)}\circ T_{\rho}^{(m-1)}\circ\cdots\circ
T_{\rho}^{(1)}f\|_{q}^{q}\leq\sum_{S\subseteq[m]}\beta^{q|S|}\|L_{S}\circ
G_{[m]\setminus S}\|_{q}^{q}.$ (3.4)

This will complete the proof by setting $m=n$.

For $m=1$, the claim is exactly (3.3), with $g=f$ and $i=1$. Let us assume
that (3.4) holds for $m-1$ and prove it for $m$. Write

$T_{\rho}^{[m-1]}=T_{\rho}^{(m-1)}\circ\cdots\circ T_{\rho}^{(1)}.$

We may apply (3.3) and the commutation properties of tensor products to obtain
that

$\displaystyle\|T_{\rho}^{(m)}T_{\rho}^{[m-1]}f\|_{q}^{q}\leq\|G_{m}T_{\rho}^{[m-1]}f\|_{q}^{q}+\beta^{q}\|L_{m}T_{\rho}^{[m-1]}f\|_{q}^{q}=\|T_{\rho}^{[m-1]}G_{m}f\|_{q}^{q}+\beta^{q}\|T_{\rho}^{[m-1]}L_{m}f\|_{q}^{q}.$

Applying the induction hypothesis with $L_{m}[f]$ and $G_{m}[f]$ in place of
$f$ completes our inductive proof. ∎

##  4 Sharp Hypercontractive Inequalities for Global Functions on $\Omega^{n}$

In this section we prove sharp hypercontractive inequalities for functions on
$\Omega^{n}$. First, we prove a hypercontractive inequality for general
functions, and then we use it to prove a more powerful hypercontractive
inequality for global functions. Finally, we use the latter inequality to
prove Theorem 1.4.

###  4.1 Hypercontractivity for general functions

We prove the following theorem.

######  Theorem 4.1.

Let $\rho\leq 1/3$ and $q\geq 2$. Then for any $f\in L^{2}(\Omega^{n},\mu)$,

$\|T_{\rho\frac{1}{\sqrt{q}}}f\|_{q}^{q}\leq\sum_{S\subseteq[n]}\beta^{q|S|}q^{-q|S|/2}\operatorname*{\mathbb{E}}_{x\sim\Omega^{S}}\|D_{S,x}f\|_{2}^{q},$

where $\beta=\rho\left(1+\frac{2(q-2)}{\log(1/\rho)}\right)$.

In the proof we rely on the classical hypercontractive inequality in Gaussian
space proved by Bonami [5], Gross [23], and Beckner [3].

######  Theorem 4.2.

Let $q\geq p\geq 1$ and let $\rho\leq\sqrt{\frac{p-1}{q-1}}.$ For any $f\in
L^{p}(\mathbb{R}^{n},\gamma)$, we have $\|T_{\rho}f\|_{q}\leq\|f\|_{p}$.

We also use the following simple commutativity properties of the operators
$G_{S},T_{\rho},$ and $D_{S,x}$ which complement the ‘swapping rules’ of
$L_{S}$ and $D_{S,x}$ with $T_{\rho}$ that were presented in Lemma 2.2.

######  Lemma 4.3.

  1. 1.

For any $S,T\subset[n]$ we have $T_{\rho}G_{S}=G_{S}T_{\rho}$.

  2. 2.

If $S,T$ are disjoint, then $G_{T}D_{S,x}=D_{S,x}G_{T}$.

###### Proof.

We make use of the following tensor descriptions of our operators.

$D_{S,x}=\bigotimes_{i\in S}D_{i,x_{i}}\otimes\bigotimes_{i\in
S^{c}}I,\qquad\qquad T_{\rho}=\bigotimes_{i=1}^{n}T_{\rho}^{(i)},\qquad\mbox{
and }\qquad G_{S}=\bigotimes_{i\in S}G_{i}\otimes\bigotimes_{i\in S^{c}}I.$

As the composition of operators is performed coordinate-wise, (2) follows
immediately from the tensor description, and (1) reduces to the case $n=1$,
where it follows easily from the Fourier formulas for $T_{\rho}$ and $D_{S,x}$
given in Lemma 2.1 and (2.1). ∎

Now we are ready to present the proof of Theorem 4.1.

###### Proof.

By Proposition 3.1 and Lemmas 2.2, 4.3 we have

$\displaystyle\|T_{\rho\frac{1}{\sqrt{q}}}f\|_{q}^{q}$
$\displaystyle=\|T_{\rho}T_{\frac{1}{\sqrt{q}}}f\|_{q}^{q}\leq\sum_{S\subseteq[n]}\beta^{q|S|}\|(L_{S}\circ
G_{S^{c}})T_{\frac{1}{\sqrt{q}}}f\|_{q}^{q}=$
$\displaystyle=\sum_{S\subseteq[n]}\beta^{q|S|}\operatorname*{\mathbb{E}}_{x\sim\Omega^{S}}\left\|\left[L_{S}\left(G_{S^{c}}T_{\frac{1}{\sqrt{q}}}f\right)\right]_{S\rightarrow
x}\right\|_{q}^{q}=\sum_{S\subseteq[n]}\beta^{q|S|}\operatorname*{\mathbb{E}}_{x\sim\Omega^{S}}\|G_{S^{c}}D_{S,x}T_{\frac{1}{\sqrt{q}}}f\|_{q}^{q}=$
$\displaystyle=\sum_{S\subseteq[n]}\beta^{q|S|}\operatorname*{\mathbb{E}}_{x\sim\Omega^{S}}\left\|\left(\frac{1}{\sqrt{q}}\right)^{|S|}G_{S^{c}}T_{\frac{1}{\sqrt{q}}}D_{S,x}f\right\|_{q}^{q}=\sum_{S\subseteq[n]}\beta^{q|S|}q^{\frac{-q|S|}{2}}\operatorname*{\mathbb{E}}_{x\sim\Omega^{S}}\|G_{S^{c}}T_{\frac{1}{\sqrt{q}}}D_{S,x}f\|_{q}^{q}=$
$\displaystyle=\sum_{S\subseteq[n]}\beta^{q|S|}q^{-\frac{q|S|}{2}}\operatorname*{\mathbb{E}}_{x\sim\Omega^{S}}\|T_{\frac{1}{\sqrt{q}}}\left(G_{S^{c}}D_{S,x}f\right)\|_{q}^{q}.$

The function $G_{S^{c}}D_{S,x}f$ is a function on the Gaussian space
$(\mathbb{R}^{k-1})^{S^{c}}$, and hence, we may apply Theorem 4.2 to obtain

$\displaystyle\|T_{\rho\frac{1}{\sqrt{q}}}f\|_{q}^{q}$
$\displaystyle\leq\sum_{S\subseteq[n]}\beta^{q|S|}q^{-\frac{q|S|}{2}}\operatorname*{\mathbb{E}}_{x\sim\Omega^{S}}\|T_{\frac{1}{\sqrt{q}}}\left(G_{S^{c}}D_{S,x}f\right)\|_{q}^{q}\leq\sum_{S\subseteq[n]}\beta^{q|S|}q^{-\frac{q|S|}{2}}\operatorname*{\mathbb{E}}_{x\sim\Omega^{S}}\|G_{S^{c}}D_{S,x}f\|_{2}^{q}$
$\displaystyle=\sum_{S\subseteq[n]}\beta^{q|S|}q^{-\frac{q|S|}{2}}\operatorname*{\mathbb{E}}_{x\sim\Omega^{S}}\|D_{S,x}f\|_{2}^{q},$

where the last equality holds since $G_{S^{c}}$ preserves 2-norms. This
completes the proof. ∎

###  4.2 Hypercontractivity for global functions

######  Definition 4.4.

Let $r,\gamma>0$. A function $f\in L^{2}(\Omega^{n},\mu)$ is called
_$(r,\gamma)$ -$L_{2}$-global_ if $\|D_{S,x}f\|_{2}\leq r^{|S|}\gamma$ for all
$S\subseteq[n]$ and $x\in\Omega^{S}.$

Note that this notion of globalness differs from the ‘restriction-based’
notion of globalness used in [33]. We will establish a relation between these
notions in Section 4.3.

We prove the following theorem.

######  Theorem 4.5.

Let $r,\gamma>0,$ and let $q\geq 2$. Let $f\colon\Omega^{n}\to\mathbb{R}$ be
an $(r,\gamma)$-$L_{2}$-global function. Let
$\rho=\frac{1}{\sqrt{2q}}\rho^{\prime}$ and suppose that $\rho^{\prime}\leq
1/3$ and that
$\beta=\rho^{\prime}\left(1+\frac{2(q-2)}{\log(1/\rho^{\prime})}\right)$
satisfies

$\beta\leq\sqrt{q}(r/\sqrt{2})^{-\frac{q-2}{q}}.$ (4.1)

Then

$\|T_{\rho}f\|_{q}^{q}\leq\|f\|_{2}^{2}\gamma^{q-2}.$

In the proof we use the following simple lemma.

######  Lemma 4.6.

For any $f\colon\Omega^{n}\to\mathbb{R},$ we have

$\sum_{S\subseteq[n]}\|L_{S}T_{1/\sqrt{2}}[f]\|_{2}^{2}=\|f\|_{2}^{2}.$

###### Proof.

By Lemma 2.1 and (2.1), we have

$L_{S}T_{1/\sqrt{2}}[f]=\sum_{T\supseteq S}2^{-|T|/2}f^{=T}.$

Taking 2-norms, we obtain

$\sum_{S\subseteq[n]}\|L_{S}T_{1/\sqrt{2}}[f]\|_{2}^{2}=\sum_{S\subseteq[n]}\sum_{T\supseteq
S}2^{-|T|}\|f^{=T}\|_{2}^{2}=\sum_{T\subseteq[n]}\|f^{=T}\|_{2}^{2}=\|f\|_{2}^{2},$

as asserted. ∎

###### Proof of Theorem 4.5.

Write $f^{\prime}=T_{\frac{1}{\sqrt{2}}}f.$ By Theorem 4.1, we have

$\|T_{\rho}f\|_{q}^{q}=\|T_{\rho^{\prime}\frac{1}{\sqrt{q}}}f^{\prime}\|_{q}^{q}\leq\sum_{S\subseteq[n]}\left(\frac{\beta}{\sqrt{q}}\right)^{q|S|}\mathbb{E}_{x\sim\Omega^{S}}\|D_{S,x}[f^{\prime}]\|_{2}^{q}.$
(4.2)

By Lemma 2.2, for any $S\subset[n]$ and any $x\in\Omega^{S}$, we have
$D_{S,x}[f^{\prime}]=D_{S,x}T_{1/\sqrt{2}}f=\left(\frac{1}{\sqrt{2}}\right)^{|S|}T_{1/\sqrt{2}}D_{S,x}[f]$,
and hence,

$\displaystyle\begin{split}\|D_{S,x}[f^{\prime}]\|_{2}^{q-2}&=\|\left(\frac{1}{\sqrt{2}}\right)^{|S|}T_{1/\sqrt{2}}D_{S,x}[f]\|_{2}^{q-2}=\left(\frac{1}{\sqrt{2}}\right)^{|S|(q-2)}\|T_{1/\sqrt{2}}D_{S,x}f\|_{2}^{q-2}\\\
&\leq\left(\frac{1}{\sqrt{2}}\right)^{|S|(q-2)}\|D_{S,x}f\|_{2}^{q-2}\leq(r^{|S|}\gamma)^{q-2},\end{split}$
(4.3)

where the penultimate inequality holds since $T_{1/\sqrt{2}}$ is a contraction
and the last inequality holds as $f$ is $(r,\gamma)$-$L_{2}$-global. Since
$\mathbb{E}_{x\sim\Omega^{S}}\|D_{S,x}[f^{\prime}]\|_{2}^{q}\leq\max_{x\in\Omega^{S}}\|D_{S,x}[f^{\prime}]\|_{2}^{q-2}\mathbb{E}_{x\sim\Omega^{S}}\|D_{S,x}[f^{\prime}]\|_{2}^{2}$,
we may combine (4.2) and (4.3) to obtain

$\|T_{\rho}f\|_{q}^{q}\leq\sum_{S\subseteq[n]}\left(\left(\frac{\beta}{\sqrt{q}}\right)^{q}\left(\frac{r}{\sqrt{2}}\right)^{q-2}\right)^{|S|}\gamma^{q-2}\mathbb{E}_{x\sim\Omega^{S}}\|D_{S,x}T_{\frac{1}{\sqrt{2}}}f\|_{2}^{2}.$

By (4.1), we have

$\left(\frac{\beta}{\sqrt{q}}\right)^{q}\left(\frac{r}{\sqrt{2}}\right)^{q-2}\leq
1,$

and thus,

$\|T_{\rho}f\|_{q}^{q}\leq\sum_{S\subseteq[n]}\gamma^{q-2}\mathbb{E}_{x\sim\Omega^{S}}\|D_{S,x}T_{\frac{1}{\sqrt{2}}}f\|_{2}^{2}=\gamma^{q-2}\sum_{S\subseteq[n]}\|L_{S}T_{1/\sqrt{2}}f\|_{2}^{2}=\gamma^{q-2}\|f\|_{2}^{2},$

where the last equality uses Lemma 4.6. This completes the proof. ∎

As the assertion of Theorem 4.5 is somewhat cumbersome, we provide a weaker,
yet useful, corollary.

######  Corollary 4.7.

Let $r,\gamma>0,$ and let $q\geq 2$. Let $f\colon\Omega^{n}\to\mathbb{R}$ be
an $(r,\gamma)$-$L_{2}$-global function. If

  1. 1.

$\rho\leq\frac{1}{3\sqrt{2}}\min\left(\frac{1}{r^{\frac{q-2}{q}}q},\frac{1}{\sqrt{q}}\right)$,
or

  2. 2.

$r\geq 1$ and $\rho\leq\frac{\log q}{16rq}$,

then $\|T_{\rho}f\|_{q}^{q}\leq\|f\|_{2}^{2}\gamma^{q-2}$.

###### Proof.

Set $\rho^{\prime}=\sqrt{2q}\cdot\rho$ and
$\beta=\rho^{\prime}\left(1+\frac{2(q-2)}{\log(1/\rho^{\prime})}\right)$. It
is clear that if either (1) or (2) holds then $\rho^{\prime}<1/3$. Hence, in
order to prove that Corollary 4.7 follows from Theorem 4.5, it is sufficient
to show that $\beta$ satisfies (4.1).

Since for any $q,\rho^{\prime}>0$,

$\frac{1}{3}\left(1+\frac{2q}{\log(1/\rho^{\prime})}\right)\leq\frac{q}{\min\\{q,\log(1/\rho^{\prime})\\}},$

and as $q\geq 2$, $\rho^{\prime}\leq 1/3$, we have

$\beta=(3\rho^{\prime})\cdot\frac{1}{3}\left(1+\frac{2(q-2)}{\log(1/\rho^{\prime})}\right)\leq\frac{3\rho^{\prime}q}{\min\\{q,\log(1/\rho^{\prime})\\}}\leq
3\rho^{\prime}q.$

If (1) holds, then in particular,
$\rho\leq\frac{1}{3\sqrt{2}r^{\frac{q-2}{q}}q}$, and thus,

$\beta\leq 3\rho^{\prime}q\leq
3\frac{\sqrt{2q}}{3\sqrt{2}r^{\frac{q-2}{q}}q}q\leq\frac{\sqrt{q}}{r^{\frac{q-2}{q}}},$

which proves (4.1).

If (2) holds (that is, if $r>1$ and $\rho\leq\frac{\log q}{16rq}$), then we
have

$\rho^{\prime}\leq\frac{1}{8\sqrt{2}}\frac{\log
q}{r\sqrt{q}}\leq\frac{1}{q^{1/3}},$

since $q\geq 2$, and thus,
$\min\\{q,\log(1/\rho^{\prime})\\}\geq\frac{1}{3}\log q$. Hence,

$\beta\leq\frac{3\rho^{\prime}q}{\min\\{q,\log(1/\rho^{\prime})\\}}\leq\frac{3\frac{1}{8\sqrt{2}}\frac{\log
q}{r\sqrt{q}}q}{\frac{1}{3}\log q}\leq\frac{\sqrt{q}}{r},$

which implies (4.1) since $r>1$. This completes the proof. ∎

###  4.3 Proof of Theorem 1.4

We use the following ‘derivative-based’ notion of globalness, which
generalizes Definition 4.4.

######  Definition 4.8.

For $p\geq 1$, we say that $f$ is _$(r,\gamma,d)$ -$L_{p}$-global_ if
$\|D_{S,x}f\|_{p}\leq r^{|S|}\gamma$ for all $S\subseteq[n]$ of size $\leq d$
and all $x\in\Omega^{S}.$

The following easy lemma shows that the ‘restriction-based’ notion of
globalness (which is essentially the notion used in [33]) implies the
‘derivative-based’ notion, with almost the same parameters.

######  Lemma 4.9.

Let $p\geq 1$, and let $f:\Omega^{n}\to\mathbb{R}$. Suppose that for some
$r,\gamma>0$, we have $\|f_{S\to x}\|_{p}\leq r^{|S|}\gamma$ for all $S$ of
size $\leq d$ and all $x\in\Omega^{S}.$ Then $f$ is
$(2r,\gamma,d)$-$L_{p}$-global.

###### Proof.

Let $S\subset[n]$, $|S|\leq d$. As was shown in Section 2, the Laplacian
$L_{S}[f]$ satisfies

$L_{S}[f]=\sum_{T\subseteq S}(-1)^{|T|}E_{T}[f].$

By the triangle inequality, this implies $\|D_{S,x}f\|_{p}\leq\sum_{T\subseteq
S}\|[E_{T}[f]]_{S\to x}\|_{p}.$ For each $T\subset S$, we obtain by Jensen’s
inequality that

$\|[E_{T}[f]]_{S\to
x}\|_{p}^{p}=\operatorname*{\mathbb{E}}_{z\sim\Omega^{S^{c}}}\left[\left|\operatorname*{\mathbb{E}}_{y\sim\Omega^{T}}f_{S\setminus
T\to x_{S\setminus T},S^{c}\to z}\right|^{p}\right]\leq\|f_{S\setminus T\to
x_{S\setminus T}}\|_{p}^{p}\leq r^{p|S|}\gamma^{p}.$

Hence,

$\|D_{S,x}f\|_{p}\leq\sum_{T\subseteq S}\|[E_{T}[f]]_{S\to
x}\|_{p}\leq\sum_{T\subseteq S}r^{|S|}\gamma=(2r)^{|S|}\gamma,$

as asserted. ∎

This allows us to obtain our main hypercontractivity theorem (Theorem 1.4)
from Corollary 4.7. Let us recall its formulation

Theorem 1.4. Let $q\geq 2$ and let $(\Omega,\mu)$ be a finite probability
space. Let $f\colon(\Omega^{n},\mu^{n})\to\mathbb{R}$, and assume that

$\|f_{S\to x}\|_{2}\leq r^{|S|}\|f\|_{2}$

for all $S\subseteq[n]$ and for all $x\in\Omega^{S}$. If $r\geq 1$ and
$\rho\leq\frac{\log q}{32rq}$, then $\|T_{\rho}f\|_{q}\leq\|f\|_{2}$.

###### Proof.

By Lemma 4.9, $f$ is $(2r,\|f\|_{2})$-$L_{2}$-global. Hence, the assertion of
the theorem follows from Corollary 4.7. ∎

The following proposition shows that Theorem 1.4 is tight, up to the value of
the constant $C$.

######  Proposition 4.10.

There exist $r,C>1$ such that for any $q\geq 2$, there exist $n,p$ and a
function $f:(\\{0,1\\}^{n},\mu_{p})\to\mathbb{R}$, such that:

(a): $\|f_{S\to x}\|_{2}\leq r^{|S|}\|f\|_{2}$ for all $S\subset[n]$, and for
all $x\in\\{0,1\\}^{S}$, and

(b): $\|T_{\rho}f\|_{q}>\|f\|_{2}$, for all $\rho>\frac{C\log q}{rq}$.

###### Proof.

For $n,d\in\mathbb{N}$ such that $d|n$, let $p=d/n$ and consider the function
$f_{n,d}:(\\{0,1\\}^{n},\mu_{p})\to\mathbb{R}$ defined by

$f_{n,d}=\prod_{j=0}^{d-1}\left(\sum_{i=1}^{n/d}(x_{j(n/d)+i}-p)\right).$

For any $n,d$, the function $f_{n,d}$ satisfies (a) with $r=2$. Indeed, if the
set $S$ of ‘restricted’ coordinates is included in a single expression of the
form $f_{n,d,j}=\sum_{i=1}^{n/d}(x_{j(n/d)+i}-p)$, the 2-norm increases the
most when all the coordinates are fixed to $1$, and in this case we have

$\|(f_{n,d,j})_{S\rightarrow
1}\|_{2}^{2}=(|S|(1-p))^{2}+(\frac{n}{d}-|S|)(p(1-p))\leq|S|^{2}+1,$

and $\|f_{n,d,j}\|_{2}=\sqrt{1-p}$. As $\sqrt{\frac{|S|^{2}+1}{1-p}}\leq
2^{|S|}$ for all $|S|\geq 1$, condition (a) is satisfied for any such $S$. The
condition for an arbitrary set $S$ follows by multiplicativity.

When $d$ is fixed and $n$ tends to infinity, the distribution of $f_{n,d}$
converges to the distribution of $\prod_{i=1}^{d}(X_{i}-1),$ where each
$X_{i}$ is independently $\mathrm{Poi}(1)$ distributed. This easily implies
that when $q$ is large and fixed and $n\to\infty$, the $q$-norm of $f_{n,d}$
tends to $\left(\Theta(\frac{q}{\log q})\right)^{d}$, while its $2$-norm is
$(1-p)^{d/2}.$ Moreover, for any $\rho>0$, $f_{n,d}$ is an eigenfunction of
$T_{\rho}$ corresponding to the eigenvalue $\rho^{d}$. Hence, there exist
$C^{\prime}>0$ and $n_{0}=n_{0}(q,d)$, such that $\|T_{\frac{C^{\prime}\log
q}{q}}f_{n,d}\|_{q}>\|f_{n,d}\|_{2}$, for all $n>n_{0}$. In particular,
condition (b) holds for $f_{n,d}$, for all $C\geq 2C^{\prime}$. Therefore, the
function $f=f_{n,d}$ for any $n>n_{0}$ satisfies the assertion of the
proposition, with $r=2$ and $C=2C^{\prime}$. ∎

##  5 Sharp Level-$d$ Inequalities for Global Functions

In this section we prove our $d$-level inequality – namely, Theorem 1.5, which
asserts a sharp bound on the 2-norm of $f^{=d}$ for ‘global’ functions
$f:\Omega^{n}\to\\{0,1\\}$. Here, the ‘globalness’ notion concerns
_restrictions_ of $f$ – it asserts that there exist $r,\gamma$ such that for
any $S\subset[n]$ with $|S|\leq d$, $\operatorname*{\mathbb{E}}[f_{S\to
x}]\leq r^{|S|}\gamma$.

First, we prove a sharp $d$-level inequality under the assumption that
$f^{=d}$ is global. Then, we pass via a derivative-based notion of globalness
– namely, the assumption that $\|D_{S,x}f\|_{p}\leq r^{|S|}\gamma_{p}$ for
$p=1,2$, to show that globalness of $f$ can be upgraded to globalness of
$f^{=d}$, thus allowing us to prove the theorem.

Throughout this section, we use the convention $(\cdot)^{0}=1$ for any
expression $(\cdot)$, including expressions of the form $\frac{r}{0}$ and
$\log 1$.

###  5.1 A level-$d$ inequality when $f^{=d}$ is global

######  Lemma 5.1.

Let $\gamma>0,\gamma_{2}>\gamma_{1}>0,$ let $f\colon\Omega^{n}\to\mathbb{R}$
be with $\|f\|_{2}\leq\gamma_{2}$ and $\|f\|_{1}\leq\gamma_{1}$, let
$d<\frac{1}{2}\log\left(\frac{\gamma_{2}}{\gamma_{1}}\right)$, and let
$r\geq\left(\frac{d}{\log(\gamma_{2}/\gamma_{1})}\right)^{1/2}$ . If the
function $f^{=d}$ is $(r,\gamma)$-$L_{2}$-global, then

$\|f^{=d}\|_{2}^{2}\leq\left(\frac{33r}{d}\right)^{d}\gamma_{1}\cdot\gamma\log^{d}\left(\frac{\gamma_{2}}{\gamma_{1}}\right).$

###### Proof.

The assertion clearly holds for $d=0$. Hence, we may assume $d\geq 1$. Let
$q>2,q^{\prime}$ be Hölder conjugates to be chosen later. Then by Hölder’s
inequality we have

$\displaystyle\|f^{=d}\|_{2}^{2}=\langle
f,f^{=d}\rangle\leq\|f^{=d}\|_{q}\|f\|_{q^{\prime}}.$

Let
$\rho=\frac{1}{3\sqrt{2}}\min\left(\frac{1}{r^{\frac{q-2}{q}}q},\frac{1}{\sqrt{q}}\right)$.
By Corollary 4.7, we have

$\|f^{=d}\|_{q}=\rho^{-d}\|\mathrm{T}_{\rho}f^{=d}\|_{q}\leq\rho^{-d}\|f^{=d}\|_{2}^{2/q}\gamma^{1-2/q}\leq\rho^{-d}\gamma.$

Let $\theta=\frac{2}{q}$. Since
$\frac{1}{q^{\prime}}=1-\frac{1}{q}=\frac{1-\theta}{1}+\frac{\theta}{2},$ by
the log-convexity of $L_{p}$-norms we have

$\|f\|_{q^{\prime}}\leq\|f\|_{1}^{1-\theta}\|f\|_{2}^{\theta}\leq\gamma_{1}\left(\frac{\gamma_{2}}{\gamma_{1}}\right)^{\theta}.$

Combining with the above bounds, we obtain

$\|f^{=d}\|_{2}^{2}\leq\|f^{=d}\|_{q}\|f\|_{q^{\prime}}\leq\rho^{-d}\gamma\cdot\gamma_{1}\left(\frac{\gamma_{2}}{\gamma_{1}}\right)^{\theta}.$

In order to optimize the right hand side, we choose
$q=2\log(\gamma_{2}/\gamma_{1})/d$, thus obtaining
$\theta=d/\log(\gamma_{2}/\gamma_{1})$, which yields

$\|f^{=d}\|_{2}^{2}\leq\rho^{-d}\gamma\cdot\gamma_{1}\left(\frac{\gamma_{2}}{\gamma_{1}}\right)^{\theta}=(e/\rho)^{d}\gamma_{1}\cdot\gamma.$
(5.1)

Note by the assumptions on $r$ and $d$, we have $q>4$ and $r>1/\sqrt{q}$. It
follows that

$\frac{1}{3\sqrt{2}r^{\frac{q-2}{q}}q}=\frac{1}{3\sqrt{2}rq}\cdot
r^{2/q}>\frac{1}{6rq}$

(since $r^{2/q}>(1/q)^{1/q}$, and for any $x<1/4$ we have $x^{x}>1/\sqrt{2}$),
and

$\frac{1}{3\sqrt{2q}}>\frac{1}{6rq},$

and therefore, $\rho\geq\frac{1}{6rq}=\theta/(12r)$. Substituting into (5.1),
we obtain

$\|f^{=d}\|_{2}^{2}\leq\left(\frac{e\cdot
12r}{\theta}\right)^{d}\gamma_{1}\cdot\gamma\leq\left(\frac{33r}{d}\right)^{d}\gamma_{1}\cdot\gamma\cdot\log^{d}\left(\frac{\gamma_{2}}{\gamma_{1}}\right),$

as asserted. ∎

###  5.2 Obtaining globalness of $f^{=d}$

The following theorem shows that ‘derivative-based’ globalness of $f$ can be
used to obtain globalness of $f^{=d}$. In view of Lemma 4.9, it will be
sufficient for proving Theorem 1.5.

######  Theorem 5.2.

Let $r\geq 1,\gamma_{2}>\gamma_{1}>0$, and let
$d\leq\frac{1}{2}\log(\frac{\gamma_{2}}{\gamma_{1}})$ be a non-negative
integer. Let $f:\Omega^{n}\to\mathbb{R}$ be a function that is both
$(r,\gamma_{1},d)$-$L_{1}$-global and $(r,\gamma_{2},d)$-$L_{2}$-global. Let

$r^{\prime}_{d}=\frac{\sqrt{d}}{\log^{1/2}(\gamma_{2}/\gamma_{1})}\qquad\mbox{and}\qquad\gamma^{\prime}_{d}=\left(\frac{33r}{\sqrt{d}}\right)^{d}\gamma_{1}\log^{d/2}\left(\frac{\gamma_{2}}{\gamma_{1}}\right).$

Then the function $f^{=d}$ is
$(r^{\prime}_{d},\gamma^{\prime}_{d})$-$L_{2}$-global.

###### Proof.

We prove the theorem by induction on $d$. For $d=0$, the theorem asserts that
$f^{=0}$ is $(0,\gamma_{1})$-$L_{2}$-global, and this indeed holds since
$f^{=0}=\operatorname*{\mathbb{E}}[f]$.

To prove the induction step, we show that each function $D_{i,x}[f^{=d}]$ is
$(r^{\prime}_{d},r^{\prime}_{d}\gamma^{\prime}_{d})$-$L_{2}$ global and that
$\|f^{=d}\|_{2}\leq\gamma^{\prime}_{d}.$ This will complete the proof, as each
derivative $D_{S,x}[f^{=d}]$ is also a derivative of the function
$D_{i,x}[f^{=d}]$ (for any $i\in S$). We first show the former claim.

Each function $D_{i,x}[f]$ is both $(r,r\gamma_{1},d-1)$-$L_{1}$-global and
$(r,r\gamma_{2},d-1)$-$L_{2}$-global. Therefore, we may apply the induction
hypothesis to obtain that the function

$D_{i,x}[f^{=d}]=\left(D_{i,x}[f]\right)^{=d-1}$

is $(r^{\prime\prime}_{d-1},\gamma^{\prime\prime}_{d-1},d-1)$-$L_{2}$-global,
where

$r^{\prime\prime}_{d-1}:=\sqrt{\frac{d-1}{d}}r^{\prime}_{d},\qquad\mbox{and}\qquad\gamma^{\prime\prime}_{d-1}:=\left(\frac{33r}{\sqrt{d-1}}\right)^{d-1}r\gamma_{1}\log^{(d-1)/2}\left(\frac{\gamma_{2}}{\gamma_{1}}\right).$

As we clearly have $r^{\prime\prime}_{d-1}\leq r^{\prime}_{d}$, and as

$\gamma^{\prime\prime}_{d-1}\leq\left(\frac{33r}{\sqrt{d}}\right)^{d}r^{\prime}_{d}\gamma_{1}\log^{d/2}\left(\frac{\gamma_{2}}{\gamma_{1}}\right)=r^{\prime}_{d}\gamma^{\prime}_{d},$

$D_{i,x}[f^{=d}]$ is indeed
$(r^{\prime}_{d},r^{\prime}_{d}\gamma^{\prime}_{d})$-$L_{2}$ global. (In the
case $d=1$, the function
$D_{i,x}[f^{=1}]=(D_{i,x}[f])^{=0}=\mathbb{E}[D_{i,x}(f)]$ is
$(0,r\gamma_{1})$-$L_{2}$-global, and in particular, is
$(r^{\prime}_{1},r^{\prime}_{1}\gamma^{\prime}_{1})$-$L_{2}$ global.)

It now remains to show that $\|f^{=d}\|_{2}\leq\gamma^{\prime}_{d}.$ Suppose
on the contrary that $\|f^{=d}\|_{2}>\gamma^{\prime}_{d}$. By the above
paragraph, it follows that $f^{=d}$ is
$(r^{\prime}_{d},\|f^{=d}\|_{2})$-global. Therefore, by Lemma 5.1 we have

$\|f^{=d}\|_{2}^{2}\leq\left(\frac{33r^{\prime}_{d}}{d}\right)^{d}\gamma_{1}\|f^{=d}\|_{2}\log^{d}\left(\frac{\gamma_{2}}{\gamma_{1}}\right).$

By substituting the values of $r^{\prime}_{d}$ and $\gamma^{\prime}_{d}$, this
yields

$\left(\frac{33r}{\sqrt{d}}\right)^{d}\gamma_{1}\log^{d/2}\left(\frac{\gamma_{2}}{\gamma_{1}}\right)=\gamma^{\prime}_{d}<\|f^{=d}\|_{2}\leq\left(\frac{33\sqrt{d}}{d\log^{1/2}\left(\frac{\gamma_{2}}{\gamma_{1}}\right)}\right)^{d}\gamma_{1}\log^{d}\left(\frac{\gamma_{2}}{\gamma_{1}}\right),$

a contradiction. This completes the proof. ∎

###  5.3 Proof of Theorem 1.5

We prove the following concrete version of Theorem 1.5.

######  Theorem 5.3.

Let $f:\Omega^{n}\rightarrow\\{0,1\\}$. Let $r>1$, let
$d\leq\frac{1}{4}\log(1/\mathbb{E}[f])$, and suppose that

$\mathbb{E}[f_{S\to x}]\leq r^{|S|}\mathbb{E}[f],$

for all sets $S$ of size $\leq d$ and all $x\in\Omega^{S}.$ Then

$\|f^{=d}\|_{2}^{2}\leq\mathbb{E}^{2}[f]\left(\frac{2200r^{2}\log(1/\mathbb{E}[f])}{d}\right)^{d}.$

###### Proof.

Denote $\gamma=\operatorname*{\mathbb{E}}[f]$. Since the range of $f$ is
$\\{0,1\\}$, Lemma 4.9 implies that $f$ is both $(2r,\gamma,d)$-$L_{1}$-global
and $(2\sqrt{r},\sqrt{\gamma},d)$-$L_{2}$ global. By Theorem 5.2 we obtain
that the function $f^{=d}$ is $(r^{\prime},\gamma^{\prime})$-global, for

$r^{\prime}=\frac{\sqrt{d}}{\log^{1/2}(1/\sqrt{\gamma})}\qquad\mbox{and}\qquad\gamma^{\prime}=\left(\frac{33\cdot(2r)}{\sqrt{d}}\right)^{d}\gamma\log^{d/2}\left(\frac{1}{\sqrt{\gamma}}\right).$
(5.2)

The theorem now follows from the fact that
$\|f^{=d}\|_{2}\leq\gamma^{\prime}.$ ∎

More generally, we have the following.

######  Theorem 5.4.

Let $f\colon\Omega^{n}\to\mathbb{R}$. Let $\gamma_{2}>\gamma_{1}>0$, $r>1,$
and $d\leq\frac{1}{2}\log(\gamma_{2}/\gamma_{1})$, and suppose that for all
sets $S\subset[n]$ with $|S|\leq d$ and for all $x\in\Omega^{S}$, we have

$\|f_{S\to x}\|_{1}\leq r^{|S|}\gamma_{1}\qquad\mbox{and}\qquad\|f_{S\to
x}\|_{2}\leq r^{|S|}\gamma_{2}.$

Then

$\|f^{=d}\|_{2}^{2}\leq\gamma_{1}^{2}\left(\frac{2200r^{2}\log(\gamma_{2}/\gamma_{1})}{d}\right)^{d}.$

###### Proof.

By Lemma 4.9, $f$ is both $(2r,\gamma_{1},d)$-$L_{1}$-global and
$(2r,\gamma_{2},d)$-$L_{2}$ global. The assertion now follows from Theorem
5.2, just like in the proof of Theorem 5.3. ∎

###  5.4 Bounding the $q$-norm of $f^{=d}$

We conclude this section with a bound on the $q$-norm of $f^{=d}$, which we
will use in Section 6.2.

######  Proposition 5.5.

Let $r>1$ and let $f:\Omega^{n}\rightarrow\\{0,1\\}$. Suppose that
$\mathbb{E}[f_{S\to x}]\leq r^{|S|}\gamma$ for all sets $S$ of size $\leq d$
and for all $x\in\Omega^{S}.$ Then for any $q\geq 2$ and any integer $d$ we
have

$\|f^{=d}\|_{q}\leq\gamma\left(400r\sqrt{q}\sqrt{\max\\{\log(1/\gamma),\,q\\}}\right)^{d}.$

###### Proof.

The assertion clearly holds for $d=0$. Hence, we may assume $d\geq 1$. By
Lemma 4.9, $f$ is $(2r,\sqrt{\gamma},d)$-$L_{2}$-global and
$(2r,\gamma,d)$-$L_{1}$-global. We divide the proof into two cases.

_Case 1: $1\leq d\leq\frac{1}{4}\log(1/\gamma)$._ In this case, by Theorem 5.2
we obtain that $f^{=d}$ is $(r^{\prime},\gamma^{\prime})$-global, for
$(r^{\prime},\gamma^{\prime})$ defined in (5.2). Let
$\rho=\frac{1}{3\sqrt{2}}\min\left(\frac{1}{(r^{\prime})^{\frac{q-2}{q}}q},\frac{1}{\sqrt{q}}\right)$.
By Corollary 4.7(1),

$\rho^{d}\|f^{=d}\|_{q}=\|T_{\rho}f^{=d}\|_{q}\leq\gamma^{\prime\frac{q-2}{q}}\|f^{=d}\|_{2}^{2/q}\leq\gamma^{\prime}.$

If $\rho=\frac{1}{3\sqrt{2}\sqrt{q}}$, then by substituting the value of
$\gamma^{\prime}$ we obtain

$\|f^{=d}\|_{q}\leq\gamma^{\prime}\rho^{-d}=\gamma\left(99\cdot
2\,r\sqrt{q}\sqrt{\frac{\log(1/\gamma)}{d}}\right)^{d}\leq\gamma\left(200r\sqrt{q}\cdot\max\left\\{\sqrt{q},\sqrt{\log(1/\gamma)}\right\\}\right)^{d},$

and the assertion follows. If
$\rho=\frac{1}{3\sqrt{2}(r^{\prime})^{\frac{q-2}{q}}q}$, then by substituting
the values of $\gamma^{\prime}$ and $r^{\prime}$ we obtain

$\|f^{=d}\|_{q}\leq\gamma^{\prime}\rho^{-d}=\gamma\left(99\cdot
2\,r\,r^{\prime}q\,(r^{\prime})^{-2/q}\sqrt{\frac{\log(1/\gamma)}{d}}\right)^{d}=\gamma\left(99\cdot
2\cdot\sqrt{2}\,r\,q\,(r^{\prime})^{-2/q}\right)^{d}.$

Thus, in order to prove the assertion, it is sufficient to show that

$\sqrt{q}(r^{\prime})^{-2/q}\leq\sqrt{2}\max\left\\{\sqrt{q},\sqrt{\log(1/\gamma)}\right\\}.$
(5.3)

Note that $\frac{2}{(r^{\prime})^{2}}=\frac{\log(1/\gamma)}{d}$, and thus by
our assumption on $d$, we have
$4\leq\frac{2}{(r^{\prime})^{2}}\leq\log(1/\gamma)$. Now, if
$q\geq\log(1/\gamma)\geq\frac{2}{(r^{\prime})^{2}}$, then
$(r^{\prime})^{-2/q}\leq\sqrt{(q/2)^{2/q}}<\sqrt{2}$, and (5.3) follows.
Hence, we may assume $q<\log(1/\gamma)$. In this case, we may write

$\sqrt{q}(r^{\prime})^{-2/q}=(q\cdot\left(\frac{1}{(r^{\prime})^{2}}\right)^{2/q})^{1/2}\leq(q\cdot\left(\frac{\log(1/\gamma)}{2}\right)^{2/q})^{1/2}=(x_{0}\cdot
a_{0}^{2/x_{0}})^{1/2},$

where $a_{0}=\frac{\log(1/\gamma)}{2}>1$, and $x_{0}=q$ satisfies
$2<x_{0}<\log(1/\gamma)$. As for any $a>1$, the function $g_{a}:x\mapsto
xa^{2/x}$ is convex for all $x>0$, we have
$x_{0}(a_{0})^{2/x_{0}}=g_{a_{0}}(x_{0})\leq\max(g_{a_{0}}(2),g_{a_{0}}(\log(1/\gamma)))$,
and thus,

$\sqrt{q}(r^{\prime})^{-2/q}\leq\max(2\frac{\log(1/\gamma)}{2},\log(1/\gamma)\left(\frac{\log(1/\gamma)}{2}\right)^{2/\log(1/\gamma)})^{1/2}=\sqrt{\log(1/\gamma)}\sqrt{\max(1,2)}=\sqrt{2}\sqrt{\log(1/\gamma)},$

where the last inequality holds since $x^{1/x}<2$ for all $x$. Equation (5.3)
follows.

_Case 2: $d>\frac{1}{4}\log(1/\gamma)$._ To handle this case, we may use the
fact that

$\|D_{S,x}[f^{=d}]\|_{2}=\|(D_{S,x}[f])^{=d-|S|}\|_{2}\leq\|D_{S,x}[f]\|_{2},$

to obtain that $f^{=d}$ is $(2r,\sqrt{\gamma})$-$L_{2}$-global, since $f$ is
$(2r,\sqrt{\gamma},d)$-$L_{2}$-global. By Corollary 4.7(1), setting
$\rho=\frac{1}{6\sqrt{2}rq}$, we have

$\rho^{d}\|f^{=d}\|_{q}=\|T_{\rho}f^{=d}\|_{q}\leq\gamma^{\frac{q-2}{2q}}\|f^{=d}\|_{2}^{2/q}\leq\sqrt{\gamma}.$

By the assumption on $d$, this implies

$\|f^{=d}\|_{q}\leq\sqrt{\gamma}(6\sqrt{2}rq)^{d}\leq\gamma(6\sqrt{2}e^{2}rq)^{d}\leq\gamma\left(64r\sqrt{q}\sqrt{\max\\{\log(1/\gamma),\,q\\}}\right)^{d},$

as asserted. ∎

##  6 Quantitative Bounds on the Size of Intersecting Families

In this section we consider families of subsets of $[n]$, with respect to the
biased measure $\mu_{p}$. A family $\mathcal{F}\subset\mathcal{P}([n])$ is
called _intersecting_ if for any $A,B\in\mathcal{F}$, we have $A\cap
B\neq\emptyset$. Two families $\mathcal{F},\mathcal{G}\subset\mathcal{P}([n])$
are called _cross-intersecting_ if $\forall S\in\mathcal{F},T\in\mathcal{G}$,
$S\cap T\neq\emptyset$.

We identify subsets of $[n]$ with elements of $\\{0,1\\}^{n}$, and families
$\mathcal{F}$ of subsets of $[n]$ with Boolean-valued functions
$f=1_{\mathcal{F}}:(\\{0,1\\}^{n},\mu_{p})\to\\{0,1\\}$. Subsequently, we say
that Boolean-valued functions are (cross-)intersecting if the corresponding
families of subsets of $[n]$ are (cross-)intersecting. We use the notation
$\mu_{p}(f)$ for $\mu_{p}(\mathcal{F})=\mathbb{E}_{\mu_{p}}(f)$, and say that
$f$ is ‘large’ (resp., ‘small’) if $\mu_{p}(f)$ is ‘large’ (resp., ‘small’).

Throughout this section, when considering a function
$f:(\\{0,1\\}^{n},\mu_{p})\to\\{0,1\\}$, we use the notations

$\alpha=\mu_{p}(f),\qquad\sigma^{2}=\sum_{i=1}^{n}\hat{f}(\\{i\\})^{2},\qquad\delta=\max_{i}|\hat{f}(\\{i\\})|,\qquad
m=m(f)=|\\{i:\hat{f}(\\{i\\})^{2}\geq\frac{\delta^{2}}{2}\\}|,$

where the Fourier coefficients are w.r.t. the measure $\mu_{p}$. We say that
$f$ has _smeared level- $1$ coefficients_ or that $f$ is a smeared level-$1$
function if $m(f)\geq 1/p^{2}$.

The first result we prove in this section is the following concrete version of
Theorem 1.6.

######  Theorem 6.1.

Let $f:(\\{0,1\\}^{n},\mu_{p})\to\\{0,1\\}$ be intersecting, and assume that
$1/\sqrt{m(f)}\leq p\leq 1/2$. Then

$\mu_{p}(f)\leq 32\exp\left(-0.0001/p\right).$

For any $p>1/\sqrt{n}$, the assertion of the theorem is tight, up to a factor
of $O(\log(1/p)\log n)$ in the exponent. Indeed, let $T$ be the _tribes_
family with tribes of size $r\approx\frac{1}{p}\log n$ (formally, we write
$[n]=T_{1}\cup T_{2}\cup\ldots\cup T_{n/r}$, where the $T_{i}$’s are disjoint
sets of size $r$, and we set $T=\\{S\subset[n]:\exists i,T_{i}\subset S\\}$).
Let $T^{\prime}$ be the dual family (defined by $S\in T^{\prime}$ if and only
if $[n]\setminus S\not\in T$). The function $f=1_{T\cap T^{\prime}}$ is
intersecting, satisfies $m(f)=n\geq 1/p^{2}$, and computation shows that
$\mu_{p}(f)=\exp(-O(\frac{1}{p}\log\frac{1}{p}\log n))$. Another example is
the ‘longest-run-of-ones’ function, discussed in [11, 29], whose measure is of
the same order of magnitude, for all values of $p>1/\sqrt{n}$ simultaneously.

Recall that Kupavskii and Zakharov [38] showed that for any $k<cn/\log n$, the
maximum size of a regular intersecting family of $k$-element subsets of $[n]$
is $\exp(-\Omega\left(\frac{n}{k}\right))\binom{n}{k}$. As each such family
corresponds to a function on $\\{0,1\\}^{n}$ all whose $1$-level Fourier
coefficients are equal, we can apply to it Theorem 6.1. This yields a bound
with the same order of magnitude in the exponent as in Kupavskii and
Zakharov’s result, up to a polynomial factor in $n,p$ which can be absorbed in
the exponent. Hence, Theorem 6.1 implies the result of [38] for all
$k>\sqrt{n}$, up to the value of the constants. It should be mentioned though
that the constants in [38] are better than the constants we obtain.

The proof of the theorem consists of three main steps which span Sections
6.1–6.3. First, we show in Section 6.1 that a function which cross-intersects
a ‘large’ global function must be ‘small’. Then, we show in Section 6.2 that a
function with smeared level-$1$ coefficients that admits a measure-reducing
restriction by fixing to zero a small number of coordinates, must be ‘small’
as well. At the third step, presented in Section 6.3, we consider a function
$f$ that satisfies the hypothesis of the theorem and assume on the contrary
that it is ‘large’. We show that there exists a global restriction $h=f_{S\to
x}$ such that $\mu_{p}(h)\geq e^{|S|}\mu_{p}(f)$ and $|S|$ is small. As the
function $g=f_{S\to 0}$ cross-intersects the large global function $h$, the
result of Section 6.1 implies that $g$ is ‘small’. However, this means that
$f$ admits a measure-reducing restriction by fixing to zero a small number of
coordinates, which contradicts the result of Section 6.2.

The second result we prove in this section is the following concrete version
of Theorem 1.7.

######  Theorem 6.2.

Let $n,k$ be natural numbers such that $2\log n\leq k\leq\sqrt{n}\log n$. Let
$\mathcal{A}\subseteq[k]^{n}$ be a transitive-symmetric vector-intersecting
family. Then

$\frac{|\mathcal{A}|}{k^{n}}\leq 128\exp\left(-\frac{0.0001k}{\log n}\right).$

For $k>\sqrt{n}\log n$, we have $\frac{|\mathcal{A}|}{k^{n}}\leq
128\exp\left(-0.0001\sqrt{n}\right)$.

For any $2\log n\leq k\leq\sqrt{n}\log n$, the assertion of the theorem is
tight, up to a factor of $O(\log k\log^{2}n)$ in the exponent. To see this,
one may take the aforementioned family $T\cap T^{\prime}\subset\\{0,1\\}^{n}$,
and define a family $\mathcal{A}\subset[k]^{n}$ by setting $x\in A$ if and
only if there exists $y\in T\cap T^{\prime}$ such that $\forall
i:(y_{i}=1)\Rightarrow(x_{i}=1)$. The family $\mathcal{A}$ is vector-
intersecting and transitive symmetric, and computation shows that
$\frac{|\mathcal{A}|}{k^{n}}=\exp(-O(k\log k\log n))$. This construction
follows a strategy suggested in [9, Section 4].

The proof of the theorem, presented in Section 6.4, relies on an embedding of
$\mathcal{A}$ into $((\\{0,1\\}^{k})^{n},\mu_{p})$, for $p=\frac{\log n}{k}$,
and on application of Theorem 6.1.

###  6.1 A family that cross-intersects a large global family, is small

In this section we show that a Boolean-valued function which cross-intersects
a ‘large’ global Boolean-valued function, must be ‘small’.

######  Proposition 6.3.

Let $p\leq 1/2$, and let $g,h\in L_{2}(\\{0,1\\}^{n},\mu_{p})$ be cross-
intersecting Boolean-valued functions. Assume that for some $r>0$, we have
$\mu_{p}(h_{S\to x})\leq r^{|S|}\mu_{p}(h)$ for all sets $S\subset[n]$ and for
all $x\in\\{0,1\\}^{S}.$ Denote $c=\frac{1}{3200r}$. If $\mu_{p}(h)>e^{-c/p}$,
then $\mu_{p}(g)<8e^{-c/p}$.

In the proof of the proposition, we use a lemma which follows a strategy of
Friedgut [21].

######  Lemma 6.4.

Let $p\leq 1/2$, and let $g,h\in L_{2}(\\{0,1\\}^{n},\mu_{p})$ be cross-
intersecting Boolean-valued functions. Then

$\mu_{p}(h)\mu_{p}(g)\leq\sum_{d=1}^{n}\left(\frac{p}{1-p}\right)^{d}|\langle
h^{=d},g\rangle|,$

where the inner product is taken with respect to the $\mu_{p}$ measure.

###### Proof of Lemma 6.4.

Let $A^{(1)}=\begin{pmatrix}\frac{1-2p}{1-p}&\frac{p}{1-p}\\\
1&0\end{pmatrix}$, and let $A^{(n)}$ be the $n$-fold tensor product of
$A^{(1)}$ with itself. Let $A:L_{2}(\\{0,1\\}^{n},\mu_{p})\to
L_{2}(\\{0,1\\}^{n},\mu_{p})$ be the linear operator represented by the matrix
$A^{(n)}$. In [21, Lemma 2.2], it is shown that:

  1. (1)

$A^{(n)}$ is a pseudo-disjointness matrix for $\\{0,1\\}^{n}$, meaning that if
$S\cap T\neq\emptyset$ then $A^{(n)}_{S,T}=0$;

  2. (2)

The eigenfunctions of $A$ are the characters $\\{\chi_{S}\\}_{S\subset[n]}$,
and the eigenvalue that corresponds to $\chi_{S}$ is
$\left(-\frac{p}{1-p}\right)^{|S|}$.

By (1), since $g,h$ are cross-intersecting we have

$\langle Ah,g\rangle_{\mu_{p}}=0.$

By (2), we have

$Ah=A(\sum_{S\subset[n]}\hat{h}(S)\chi_{S})=\sum_{S}\left(-\frac{p}{1-p}\right)^{|S|}\hat{h}(S)\chi_{S}=\sum_{d=0}^{n}\left(-\frac{p}{1-p}\right)^{d}h^{=d}.$

Hence,

$0=\langle
Ah,g\rangle_{\mu_{p}}=\sum_{d=0}^{n}\left(-\frac{p}{1-p}\right)^{d}\langle
h^{=d},g\rangle\geq\mu_{p}(h)\mu_{p}(g)-\sum_{d=1}^{n}\left(\frac{p}{1-p}\right)^{d}|\langle
h^{=d},g\rangle|.$

Thus,
$\mu_{p}(h)\mu_{p}(g)\leq\sum_{d=1}^{n}\left(\frac{p}{1-p}\right)^{d}|\langle
h^{=d},g\rangle|$, as asserted. ∎

Now we are ready to present the proof of Proposition 6.3.

###### Proof.

Let $q=\max\\{\log(1/\mu_{p}(g)),\,2\\}$, let $q^{\prime}$ be the Hölder
conjugate of $q$, and let $A=\max\\{\log(1/\mu_{p}(h)),\,q\\}$. By Hölder’s
inequality, we have

$|\langle
h^{=d},g\rangle|\leq\|h^{=d}\|_{q}\,\|g\|_{q^{\prime}}=\|h^{=d}\|_{q}\cdot\mu_{p}(g)/\mu_{p}(g)^{1/q}$

where the equality holds since $g$ is Boolean-valued. By the definition of
$q$,

$\mu_{p}(g)^{1/q}\geq\mu_{p}(g)^{1/\log(1/\mu_{p}(g))}=e^{-1}.$

By Proposition 5.5 (since $q\geq 2$),

$\|h^{=d}\|_{q}\leq\mu_{p}(h)\left(400\,r\,\sqrt{q}\cdot\sqrt{A}\right)^{d}.$

Hence,

$|\langle h^{=d},g\rangle|\leq
e\,\mu_{p}(h)\mu_{p}(g)\left(400\,r\,\sqrt{q}\cdot\sqrt{A}\right)^{d}.$ (6.1)

Substituting (6.1) into Lemma 6.4, we obtain

$\mu_{p}(h)\mu_{p}(g)\leq
e\mu_{p}(h)\mu_{p}(g)\sum_{d=1}^{n}\left(\frac{p}{1-p}\,400\,r\,\sqrt{q\cdot
A}\right)^{d}.$ (6.2)

If $\frac{p}{1-p}\,400\,r\,\sqrt{q\cdot A}\leq 1/4$ then (6.2) yields

$1\leq e\sum_{d=1}^{n}(1/4)^{d}<\frac{e}{3}<1,$

a contradiction. Hence, we have $\frac{p}{1-p}\,400\,r\,\sqrt{q\cdot A}>1/4,$
and consequently,

$A\geq\sqrt{q\cdot
A}\geq\frac{1}{1600\,r\,\frac{1-p}{p}}\geq\frac{1}{3200rp},$ (6.3)

where the last inequality holds since $p\leq 1/2$. Denoting
$c=\frac{1}{3200r}$, we obtain $A>c/p$. By the assumption of the proposition,
$\log(1/\mu_{p}(h))<c/p$, and hence, $A=q$. Furthermore, we may assume
$c/p>2$, as otherwise, $8\,e^{-c/p}>1$ and the proposition holds trivially.
Thus, $q=A>c/p>2$, and consequently, $q=\log(1/\mu_{p}(g))$. Therefore, (6.3)
yields

$\log(1/\mu_{p}(g))=q>c/p,$

or equivalently, $\mu_{p}(g)<e^{-c/p}$, as asserted. ∎

###  6.2 A smeared level-$1$ family admitting a measure-reducing restriction,
is small

In this section we show that a smeared level-$1$ function
$f\subset(\\{0,1\\}^{n},\mu_{p})$ that admits a measure-reducing restriction
by fixing to zero a small number of coordinates, must be small.

######  Proposition 6.5.

Let $f\colon(\\{0,1\\}^{n},\mu_{p})\rightarrow\\{0,1\\}$ be a Boolean-valued
function with $m=m(f)>1/p^{2}$. If for some $S\subset[n]$ with
$|S|\leq\frac{1}{4p}$, we have $\frac{\mu_{p}(f_{S\rightarrow
0})}{\mu_{p}(f)}<\frac{1}{4}$, then $\mu_{p}(f)<\exp(-0.001\sqrt{m})$.

In the proof of the proposition, we use a ‘level-1 inequality for smeared
functions’, which may be useful on its own.

######  Proposition 6.6 (Level-$1$ inequality for smeared level-$1$
functions).

Let $f\colon(\\{0,1\\}^{n},\mu_{p})\rightarrow\\{0,1\\}$ be a Boolean-valued
function, and assume that $m(f)>1/p^{2}$. If
$\alpha=\mathbb{E}[f]>e^{-\sqrt{m(f)}}$, then

$\sum_{i=1}^{n}\hat{f}(\\{i\\})^{2}\leq 750\,\alpha^{2}\log(1/\alpha).$

###### Proof.

Consider the function $f^{=1}=\sum_{i=1}^{n}\hat{f}(\\{i\\})\chi_{\\{i\\}}$.
We have $\|f^{=1}\|_{2}=\sigma$, $D_{S,x}[f^{=1}]=0$ for any $S\subset[n]$
with $|S|>1$, and for each $1\leq i\leq n$,

$\|D_{i,x}[f^{=1}]\|_{2}=|\mathbb{E}[D_{i,x}f]|=|\hat{f}(\\{i\\})|\,|\chi_{i}(x_{i})|\leq\delta\sqrt{\frac{1-p}{p}}\leq\frac{\sqrt{2}\sigma}{\sqrt{mp}},$

where the last inequality holds since $m\frac{\delta^{2}}{2}\leq\sigma^{2}$ by
the definition of $m(f)$. Hence, $f^{=1}$ is
$\left(\sqrt{\frac{2}{mp}},\sigma\right)$-$L_{2}$-global.

Note that we may assume
$\sqrt{\frac{2}{mp}}\leq\sqrt{\frac{2}{\log(1/\alpha)}}$, as otherwise,
$\log(1/\alpha)>mp\geq\sqrt{m}$, contradicting the assumption
$\alpha>e^{-\sqrt{m}}$. Thus, $f^{=1}$ is
$\left(\sqrt{\frac{2}{\log(1/\alpha)}},\sigma\right)$-$L_{2}$-global.
Furthermore, we may assume $1<\frac{1}{4}\log(1/\alpha)$, as otherwise
$\alpha>e^{-4}$, and hence, $750\,\alpha^{2}\log(1/\alpha)>1\geq\sigma^{2}$,
proving the assertion.

Therefore, we may apply Lemma 5.1 to the function $f$, with $d=1$,
$\gamma_{1}=\|f\|_{1}=\alpha$, $\gamma_{2}=\|f\|_{2}=\sqrt{\alpha}$, and
$r=\sqrt{\frac{2}{\log(1/\alpha)}}$, to obtain

$\sigma^{2}\leq\frac{33}{\sqrt{2}}\alpha\sigma\sqrt{\log(1/\alpha)},$

and consequently, $\sigma^{2}\leq 750\alpha^{2}\log(1/\alpha)$, as asserted. ∎

Now we are ready to present the proof of Proposition 6.5.

###### Proof.

The proof of the proposition consists of three steps. We consider a function
$f$ which satisfies the hypothesis and assume on the contrary that $f$ is
‘large’ (formally, that $\mu_{p}(f)\geq\exp(-0.001\sqrt{m})$). First, we show
that $\mathbb{E}[f(x)|x_{S}\neq 0]$ is large. Then, we show that there exists
$i\in S$ such that $f_{i\to 1}$ is large, and deduce that $|\hat{f}(\\{i\\})|$
is large. Finally, we use the smearness of $f$ to infer that
$\sum_{i}\hat{f}(\\{i\\})^{2}$ is large, which yields a contradiction by
Proposition 6.6.

_Step 1: $\mathbb{E}[f(x)|x_{S}\neq 0]$ is large._ Denote $|S|=s$ and
$a=(1-p)^{s}$. We claim that

$\mathbb{E}[f(x)|x_{S}\neq 0]\geq\frac{1-a/4}{1-a}\cdot\mu_{p}(f).$ (6.4)

Indeed, by the assumption on $\mu_{p}(f_{S\to 0})$, we have

$\mu_{p}(f)=\mathbb{E}[f(x)\mid x_{S}=0]\cdot\Pr(x_{S}=0)+\mathbb{E}[f(x)\mid
x_{S}\neq 0]\cdot\Pr(x_{S}\neq 0)\leq
a\cdot\frac{\mu_{p}(f)}{4}+(1-a)\mathbb{E}[f(x)\mid x_{S}\neq 0].$

Equation (6.4) follows by rearranging.

_Step 2: There exists $i\in S$ such that $\hat{f}(\\{i\\})$ is large._ First,
we claim that there exists $i\in S$ such that

$\mu_{p}(f_{i\to 1})\geq 3\mu_{p}(f).$ (6.5)

Indeed, by a union bound, we have

$\displaystyle(1-a)\mathbb{E}[f(x)\mid x_{S}\neq 0]=\mathbb{E}[f(x)\mid
x_{S}\neq 0]\cdot\Pr(x_{S}\neq 0)\leq\sum_{i\in S}\mu_{p}(f_{i\to
1})\cdot\Pr(x_{i}=1)\leq sp\cdot\max_{i\in S}\mu_{p}(f_{i\to 1}).$

By rearranging and substituting into (6.4), we obtain $\mu_{p}(f_{i\to
1})\geq\frac{1-a/4}{sp}\mu_{p}(f)$. Equation (6.5) follows, since by
assumption, $sp\leq 1/4$ and $a\leq 1$. Now, for $i$ that satisfies (6.5), we
have

$\sqrt{\frac{1-p}{p}}\hat{f}(\\{i\\})=\mu_{p}(f_{i\to 1})-\mu_{p}(f)\geq
2\mu_{p}(f).$ (6.6)

_Step 3: $\sum_{i}\hat{f}(\\{i\\})^{2}$ is large, contradicting Proposition
6.6._ By (6.6), we have
$\delta=\max_{i}|\hat{f}(\\{i\\})|\geq\sqrt{\frac{p}{1-p}}\cdot 2\mu_{p}(f)$.
By the definition of $m(f)$, this implies

$\sum_{i=1}^{n}\hat{f}(\\{i\\})^{2}\geq m\frac{p}{1-p}\alpha^{2}.$

On the other hand, by Proposition 6.6, we have

$\sum_{i=1}^{n}\hat{f}(\\{i\\})^{2}\leq 750\,\alpha^{2}\log(1/\alpha).$

Combining these two inequalities, we obtain $m\frac{p}{1-p}\leq
750\log(1/\alpha)$, which implies

$\log(1/\alpha)\geq\frac{1}{750}mp>0.001\sqrt{m},$

contradicting the assumption $\mu_{p}(f)\geq\exp(-0.001\sqrt{m})$. This
completes the proof. ∎

###  6.3 Proof of Theorem 6.1

Let us recall the statement of the theorem.

Theorem 6.1. Let $f:(\\{0,1\\}^{n},\mu_{p})\to\\{0,1\\}$ be intersecting, and
assume that $1/\sqrt{m(f)}\leq p\leq 1/2$. Then $\mu_{p}(f)\leq
32\exp\left(-0.0001/p\right)$.

###### Proof.

Let $f$ be a function that satisfies the hypothesis, and assume on the
contrary $\mu_{p}(f)\leq 32\exp\left(-0.0001/p\right)$. Since $1/\sqrt{m}\leq
p$, this implies

$\mu_{p}(f)>\max\left\\{32\exp\left(-0.0001/p\right),\exp(-0.001\sqrt{m})\right\\}.$
(6.7)

_Step 1: Constructing a global restriction of $f$._ Fix some ‘globality
parameter’ $r>1$, say $r=e$. We want to find a subset $S\subseteq[n]$ and
$x\in\\{0,1\\}^{S}$ such that $h=f_{S\to x}$ is ‘global’ – namely, such that
for any $T\subseteq[n]\setminus S$ and for any $y\in\\{0,1\\}^{T}$, we have
$\mu_{p}(h_{T\to y})\leq\mu_{p}(h)r^{|T|}$. For this sake, we choose $S,x$
such that $\frac{\mu_{p}(f_{S\rightarrow x})}{r^{|S|}}$ is maximal (over all
choices of $S,x$), and set $h=f_{S\to x}$. By the choice of $S,x$, for any
$T\subseteq[n]\setminus S$ and for any $y\in\\{0,1\\}^{T}$, we have

$\frac{\mu_{p}(h_{T\rightarrow y})}{r^{|S|+|T|}}=\frac{\mu_{p}(f_{S\cup
T\,\rightarrow(x,y)})}{r^{|S|+|T|}}\leq\frac{\mu_{p}(f_{S\rightarrow
x})}{r^{|S|}}=\frac{\mu_{p}(h)}{r^{|S|}},$

and thus, $\mu_{p}(h_{T\rightarrow y})\leq\mu_{p}(h)\cdot r^{|T|},$ as
desired. In addition, we have

$\exp\left(-\frac{0.0001}{p}\right)\leq\mu_{p}(f)=\frac{\mu_{p}(f)}{r^{0}}\leq\frac{\mu_{p}(f_{S\rightarrow
x})}{r^{|S|}}\leq e^{-|S|},$

and consequently,

$|S|\leq\frac{0.0001}{p}.$ (6.8)

_Step 2: Finding a function which cross-intersects the global function $h$ and
applying to it Proposition 6.3._ Define $g=f_{S\rightarrow 0}$. The function
$g$ cross-intersects $h$, and we have $\mu_{p}(h_{T\rightarrow
y})\leq\mu_{p}(h)\cdot r^{|T|}$ for any $T,y$ and
$\mu_{p}(h)\geq\mu_{p}(f)>\exp\left(-0.0001/p\right)$. Hence, we may apply
Proposition 6.3 to deduce that

$\mu_{p}(g)=\mu_{p}(f_{S\to 0})\leq
8\exp\left(-\frac{0.0001}{p}\right)\leq\frac{1}{4}\mu_{p}(f).$ (6.9)

_Step 3: Obtaining a contradiction using Proposition 6.5_. By Equations (6.8)
and (6.9), the smeared level-$1$ function $f$ admits a restriction $g=f_{S\to
0}$ such that $\frac{\mu_{p}(g)}{\mu_{p}(f)}\leq\frac{1}{4}$, for
$|S|<\frac{1}{4p}$. By Proposition 6.5, this implies that
$\mu_{p}(f)<\exp(-0.001\sqrt{m})$, which contradicts (6.7). This completes the
proof. ∎

###  6.4 Intersecting transitive-symmetric families of vectors

In this section we prove Theorem 6.2. Let us recall the formulation of the
theorem.

Theorem 6.2. Let $n,k\in\mathbb{N}$ such that $2\log n\leq k\leq\sqrt{n}\log
n$. Let $\mathcal{A}\subseteq[k]^{n}$ be a transitive-symmetric vector-
intersecting family. Then

$\frac{|\mathcal{A}|}{k^{n}}\leq 128\exp\left(-\frac{0.0001k}{\log n}\right).$

For $k>\sqrt{n}\log n$, we have $\frac{|\mathcal{A}|}{k^{n}}\leq
128\exp\left(-0.0001\sqrt{n}\right)$.

To prove the theorem, we show that $\mathcal{A}$ can be embedded into
$((\\{0,1\\}^{k})^{n},\mu_{p})$, for $p=\frac{\log n}{k}$, in such a way that
the resulting family $\mathcal{B}$ is intersecting, has smeared level-$1$
coefficients, and satisfies
$\mu_{p}(\mathcal{B})\geq\frac{1}{4}\frac{|\mathcal{A}|}{k^{n}}$. The
assertion will then follow from application of Theorem 6.1 to $\mathcal{B}$.

Let us present the embedding. Denote

$\mathcal{S}_{1,n}\vcentcolon=\\{S\in(\\{0,1\\}^{k})^{n}\mid\forall
i:|S_{i}|=1\\},\qquad\mbox{and}\qquad\mathcal{S}_{\geq
1,n}\vcentcolon=\\{S\in(\\{0,1\\}^{k})^{n}\mid\forall i:|S_{i}|\geq 1\\}.$

First, we embed $\mathcal{A}$ into $\mathcal{S}_{1,n}$, to obtain

$\tilde{\mathcal{A}}\vcentcolon=\\{S=(S_{1},S_{2},\ldots,S_{n})\in(\\{0,1\\}^{k})^{n}\mid\exists
z\in\mathcal{A}\ s.t.\ \forall
i:S_{i}=\\{z_{i}\\}\\}\subseteq\mathcal{S}_{1,n}.$

Then we take $\mathcal{B}=\tilde{\mathcal{A}}^{\uparrow}$ to be the up-closure
of $\tilde{\mathcal{A}}$ in $(\\{0,1\\}^{k})^{n}$ (i.e., we have
$x\in\mathcal{B}$ if and only if $\exists y\in\tilde{\mathcal{A}}:\forall
i,y_{i}\leq x_{i}$). The following lemma shows that for an appropriate choice
of $p$, $\mu_{p}(\mathcal{B})$ is no much smaller than
$\frac{|\mathcal{A}|}{k^{n}}$.

######  Lemma 6.7.

For any $k,n\in\mathbb{N},p\in(0,1]$, and any $\mathcal{A}\subseteq[k]^{n}$,
we have

$\frac{|\mathcal{A}|}{k^{n}}\leq\frac{\mu_{p}(\mathcal{B})}{\left(1-\left(1-p\right)^{k}\right)^{n}}.$

By fixing $p=\frac{\log n}{k}$ and using the monotonicity of the function
$x\mapsto(1-1/x)^{x}$ for $x\geq 1$, Lemma 6.7 implies:

######  Corollary 6.8.

Let $2\leq k,n\in\mathbb{N}$. Set $p=\frac{\log n}{k}$. Then for any
$\mathcal{A}\subseteq[k]^{n}$, we have

$\frac{|\mathcal{A}|}{k^{n}}\leq 4\,\mu_{p}(\mathcal{B}).$

###### Proof of Lemma 6.7.

The proof uses a coupling argument. Define a distribution $\mu$ on
$\mathcal{S}_{\geq 1,n}$ by conditioning $\mu_{p}$: For all
$x\in\mathcal{S}_{\geq 1,n}$,

$\mu(x)=\frac{\mu_{p}(x)}{\mu_{p}(\mathcal{S}_{\geq
1,n})}=\frac{\mu_{p}(x)}{\left(1-\left(1-p\right)^{k}\right)^{n}}.$

Define a distribution $\nu$ on $\mathcal{S}_{1,n}$ by sampling an element $x$
from the distribution $\mu$ and sampling uniformly at random an element of
$\mathcal{S}_{1,n}$ among the elements beneath it:
$\\{y\in\mathcal{S}_{1,n}\mid y\leq x\\}$. It is clear that $\nu$ is the
uniform distribution on $\mathcal{S}_{1,n}$. Hence, the marginals of the
distribution $(\mu,\nu)$ on $\mathcal{S}_{\geq 1,n}\times\mathcal{S}_{1,n}$
satisfy

$\mu(\mathcal{B})=\frac{\mu_{p}(\mathcal{B})}{\left(1-\left(1-p\right)^{k}\right)^{n}},\qquad\mbox{and}\qquad\nu(\tilde{\mathcal{A}})=\frac{|\tilde{\mathcal{A}}|}{|\mathcal{S}_{1,n}|}=\frac{|\mathcal{A}|}{k^{n}}.$

Consider the indicator random variables

$X(x,y)=\begin{cases}1,&x\in\mathcal{B}\\\
0,&otherwise\end{cases}\qquad\mbox{and}\qquad
Y(x,y)=\begin{cases}1,&y\in\tilde{\mathcal{A}}\\\ 0,&otherwise\end{cases}.$

Note that $X\geq Y$. Indeed, by the definition of $\nu$, for any $(x,y)$ drawn
from the distribution $(\mu,\nu)$ we have $x\geq y$. Thus,

$Y(x,y)=1\quad\Rightarrow\quad y\in\tilde{\mathcal{A}}\quad\Rightarrow\quad
x\in\tilde{\mathcal{A}}^{\uparrow}=\mathcal{B}\quad\Rightarrow\quad X(x,y)=1.$

Therefore, we have

$\frac{\mu_{p}(\mathcal{B})}{\mu_{p}(\mathcal{S}_{\geq
1,n})}=\mu(\mathcal{B})=\mathbb{E}[X]\geq\mathbb{E}[Y]=\nu(\tilde{\mathcal{A}})=\frac{|\mathcal{A}|}{k^{n}},$

as asserted. ∎

Now we are ready to present the proof of Theorem 6.2.

###### Proof.

Let $2\log n\leq k\leq\sqrt{n}\log n$, and let $\mathcal{A}\subseteq[k]^{n}$
be a transitive-symmetric vector-intersecting family. Construct
$\mathcal{B}\subset((\\{0,1\\}^{k})^{n},\mu_{\log n/k})$ in the way described
above. Clearly, $\mathcal{B}$ is intersecting.

We claim that $\mathcal{B}$ has $n$-smeared level-$1$ coefficients (meaning
$m(\mathcal{B})\geq n$). Indeed, if $\sigma\in S_{n}$ is a permutation that
preserves $\mathcal{A}$, then $\sigma^{\prime}\in S_{nk}$ defined by
$\sigma^{\prime}(i+j\cdot k)=i+\sigma(j)\cdot k$ preserves $\mathcal{B}$.
Since $\mathcal{A}$ is transitive-symmetric, there exists a group of
permutations $G\leq S_{nk}$ preserving $\mathcal{B}$, which is transitive on
each of the following sets of coordinates:

$\\{1,1+k,\ldots,1+(n-1)k\\},\\{2,2+k,\ldots,2+(n-1)k\\},\ldots,\\{k,2k,\ldots,nk\\}.$

Consequently, we have
$\hat{1}_{\mathcal{B}}(\\{i\\})=\hat{1}_{\mathcal{B}}(\\{i+jk\\})$ for all
$1\leq i\leq k$ and all $1\leq j\leq n$, and thus, $1_{\mathcal{B}}$ has
$n$-smeared level-$1$ coefficients.

Hence, the function $1_{\mathcal{B}}$ satisfies the hypothesis of Theorem 6.1.
Applying the theorem to it, we obtain $\mu_{\log n/k}(\mathcal{B})\leq
32\exp(-0.0001k/\log n)$. As $\frac{|\mathcal{A}|}{k^{n}}\leq 4\mu_{\log
n/k}(\mathcal{B})$ by Corollary 6.8, the assertion follows.

To prove the assertion for $k>\sqrt{n}\log n$ and any transitive-symmetric
vector-intersecting family $\mathcal{A}\subseteq[k]^{n}$, construct
$\mathcal{B}$ as above and note that as $\mathcal{B}$ is monotone, combination
of Corollary 6.8 with an application of Theorem 6.1 for $p=\frac{1}{\sqrt{n}}$
yields

$\frac{|\mathcal{A}|}{k^{n}}\leq 4\mu_{\log n/k}(\mathcal{B})\leq
4\mu_{1/\sqrt{n}}(\mathcal{B})\leq 128\exp(-0.0001/\sqrt{n}),$

proving the assertion. ∎

## References

  * [1] Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang.  Improved bounds for the sunflower lemma.  Ann. of Math. (2), 194(3):795–815, 2021.
  * [2] László Babai and Ákos Seress.  On the diameter of permutation groups.  Eur. J. Comb., 13(4):231–243, 1992.
  * [3] W. Beckner.  Inequalities in Fourier Analysis.  Ann. Math., 102:159–182, 1975.
  * [4] Amey Bhangale, Prahladh Harsha, and Sourya Roy.  Mixing of 3-term progressions in quasirandom groups.  In ITCS 2022, volume 215 of LIPIcs, pages 20:1–20:9.
  * [5] Aline Bonami.  Étude des coefficients de Fourier des fonctions de $l^{p}(g)$.  Annales de l’Institut Fourier, 20:335–402, 1970.
  * [6] Jean Bourgain and Gil Kalai.  Influences of variables and threshold intervals under group symmetries.  Geom. Funct. Anal., 7(3):438–461, 1997.
  * [7] Peter J. Cameron.  Metric and geometric properties of sets of permutations.  In Algebraic, extremal and metric combinatorics, 1986 (Montreal, PQ, 1986), volume 131 of London Math. Soc. Lecture Note Ser., pages 39–53. Cambridge Univ. Press, Cambridge, 1988.
  * [8] Irit Dinur, Ehud Friedgut, and Oded Regev.  Independent sets in graph powers are almost contained in juntas.  Geometric and Functional Analysis, 18:77–97, 2008.
  * [9] Sean Eberhard, Jeff Kahn, Bhargav Narayanan, and Sophie Spirkl.  On symmetric intersecting families of vectors.  Combinatorics, Probability and Computing, 30(6):899–904, 2021.
  * [10] David Ellis, Ehud Friedgut, and Haran Pilpel.  Intersecting families of permutations.  J. Amer. Math. Soc., 24(3):649–682, 2011.
  * [11] David Ellis, Gil Kalai, and Bhargav Narayanan.  On symmetric intersecting families.  European Journal of Combinatorics, 86:103094, 2020.
  * [12] David Ellis, Peter Keevash, and Noam Lifshitz.  Bounds for characters of the symmetric group: A hypercontractive approach.  In preperation.
  * [13] David Ellis, Guy Kindler, and Noam Lifshitz.  An analogue of Bonami’s lemma for functions on spaces of linear maps, and 2-2 games.  Available at arXiv:2209.04243, 2022.
  * [14] David Ellis and Noam Lifshitz.  Approximation by juntas in the symmetric group, and forbidden intersection problems.  Duke Math. J., 171(7):1417–1467, 2022.
  * [15] Paul Erdős, Chao Ko, and R. Rado.  Intersection theorems for systems of finite sets.  Quart. J. Math. Oxford Ser. (2), 12:313–320, 1961.
  * [16] Yuval Filmus, Guy Kindler, Noam Lifshitz, and Dor Minzer.  Hypercontractivity on the symmetric group.  arXiv preprint arXiv:2009.05503, 2020.
  * [17] Péter Frankl and Mikhail Deza.  On the maximum number of permutations with given maximal or minimal distance.  J. Combinatorial Theory Ser. A, 22(3):352–360, 1977.
  * [18] Peter Frankl and Norihide Tokushige.  Invitation to intersection problems for finite sets.  J. Comb. Theory, Ser. A, 144:157–211, 2016.
  * [19] Ehud Friedgut.  Boolean functions with low average sensitivity depend on few coordinates.  Comb., 18(1):27–35, 1998.
  * [20] Ehud Friedgut.  Sharp thresholds of graph properties, and the $k$-sat problem.  J. Amer. Math. Soc., 12(4):1017–1054, 1999.  With an appendix by Jean Bourgain.
  * [21] Ehud Friedgut.  On the measure of intersecting families, uniqueness and stability.  Combinatorica, 28(5):503–528, 2008.
  * [22] William T Gowers.  Quasirandom groups.  Combinatorics, Probability and Computing, 17(3):363–387, 2008.
  * [23] L. Gross.  Logarithmic Sobolev inequalities.  Amer. J. Math., 97:1061–1083, 1975.
  * [24] Hamed Hatami.  A structure theorem for Boolean functions with small total influences.  Ann. of Math. (2), 176(1):509–533, 2012.
  * [25] Harald A. Helfgott and Ákos Seress.  On the diameter of permutation groups.  Ann. of Math., pages 611–658, 2014.
  * [26] Ferdinand Ihringer and Andrey Kupavskii.  Regular intersecting families.  Discret. Appl. Math., 270:142–152, 2019.
  * [27] Jeff Kahn and Gil Kalai.  Thresholds and expectation thresholds.  Combin. Probab. Comput., 16(3):495–502, 2007.
  * [28] Jeff Kahn, Gil Kalai, and Nathan Linial.  The influence of variables on Boolean functions (extended abstract).  In FOCS 1988, pages 68–80. IEEE Computer Society, 1988.
  * [29] Gil Kalai.  Mathoverflow, Kahn–Kalai–Linial for intersecting upsets, 2012\.  https://mathoverflow.net/questions/105086/kahn-kalai-linial-for-intersecting-upsets/105099#105099.
  * [30] Gil Kalai.  Three puzzles on mathematics, computation, and games.  In Proceedings of the International Congress of Mathematicians—Rio de Janeiro 2018. Vol. I. Plenary lectures, pages 551–606. World Sci. Publ., Hackensack, NJ, 2018.
  * [31] Peter Keevash and Noam Lifshitz.  The global mixing property in the alternating group.  In preperation.
  * [32] Peter Keevash, Noam Lifshitz, Eoin Long, and Dor Minzer.  Forbidden intersections for codes.  arXiv preprint arXiv:2103.05050, 2021.
  * [33] Peter Keevash, Noam Lifshitz, Eoin Long, and Dor Minzer.  Global hypercontractivity and its applications.  J. Amer. Math. Soc., to appear. Available at arXiv:2103.0460, 2021\.
  * [34] Nathan Keller.  A simple reduction from a biased measure on the discrete cube to the uniform measure.  European Journal of Combinatorics, 33(8):1943–1957, 2012.
  * [35] Nathan Keller, Noam Lifshitz, Dor Minzer, and Ohad Sheinfeld.  On $t$-intersecting families of permutations.  arXiv preprint arXiv:2303.15755, 2023.
  * [36] Subhash Khot, Dor Minzer, and Muli Safra.  Pseudorandom sets in Grassmann graph have near-perfect expansion.  Ann. of Math. (2), 198(1):1–92, 2023.
  * [37] Andrey Kupavskii and Dmitriy Zakharov.  Regular bipartite graphs and intersecting families.  Journal of Combinatorial Theory, Series A, 155:180–189, 2018.
  * [38] Andrey Kupavskii and Dmitriy Zakharov.  Spread approximations for forbidden intersections problems.  arXiv preprint arXiv:2203.13379, 2022.
  * [39] Michael Larsen and Aner Shalev.  Characters of symmetric groups: sharp bounds and applications.  Inventiones mathematicae, 174:645–687, 2008.
  * [40] Martin W Liebeck and Aner Shalev.  Diameters of finite simple groups: sharp bounds and applications.  Ann. of Math., pages 383–406, 2001.
  * [41] Noam Lifshitz.  Analysis of Boolean functions – lecture notes of summer course for excelling students.  2022\.
  * [42] Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz.  Noise stability of functions with low influences: invariance and optimality.  Ann. of Math. (2), 171(1):295–341, 2010.
  * [43] Nikolay Nikolov and László Pyber.  Product decompositions of quasirandom groups and a jordan type theorem.  Journal of the European Mathematical Society, 13(4):1063–1077, 2011\.
  * [44] Ryan O’Donnell.  Analysis of Boolean functions.  Cambridge University Press, 2014.
  * [45] Ryan O’Donnell.  Social choice, computational complexity, Gaussian geometry, and Boolean functions.  In Proceedings of the International Congress of Mathematicians—Seoul 2014. Vol. IV, pages 633–658. Kyung Moon Sa, Seoul, 2014.
  * [46] Sarah Peluse.  Mixing for three-term progressions in finite simple groups.  In Mathematical Proceedings of the Cambridge Philosophical Society, volume 165, pages 279–286. Cambridge University Press, 2018.
  * [47] Klaus Roth.  On certain sets of integers.  J. London Math. Soc., 28(1):104–109, 1953.
  * [48] Terence Tao.  Mixing for progressions in nonabelian groups.  In Forum of Mathematics, Sigma, volume 1, page e2. Cambridge University Press, 2013.
  * [49] Yufei Zhao.  Graph Theory and Additive Combinatorics: Exploring Structure and Randomness.  Cambridge University Press, 2023.