Density Frankl–Rödl on the Sphere

Guruswami, Venkatesan; Li, Shilun

doi:10.4230/LIPIcs.APPROX/RANDOM.2025.44

Density Frankl–Rödl on the Sphere

Venkatesan Guruswami

Department of EECS, University of California, Berkeley, CA, USA Shilun Li

Department of Mathematics, University of California, Berkeley, CA, USA

Abstract

We establish a density variant of the Frankl–Rödl theorem on the sphere $\mathbb{S}^{n-1}$ , which concerns avoiding pairs of vectors with a specific distance, or equivalently, a prescribed inner product. In particular, we establish lower bounds on the probability that a randomly chosen pair of such vectors lies entirely within a measurable subset $A\subseteq\mathbb{S}^{n-1}$ of sufficiently large measure. Additionally, we prove a density version of spherical avoidance problems, which generalize from pairwise avoidance to broader configurations with prescribed pairwise inner products. Our framework encompasses a class of configurations we call inductive configurations, which include simplices with any prescribed inner product $-1<r<1$ . As a consequence of our density statement, we show that all inductive configurations are sphere Ramsey.

Keywords and phrases:

Frankl–Rödl, Sphere Ramsey, Sphere Avoidance, Reverse Hypercontractivity, Forbidden Angles

Category:

RANDOM

Funding:

Venkatesan Guruswami: Research supported by a Simons Investigator Award and NSF grants CCF-2210823 and CCF-2228287.

Shilun Li: Research supported by University of California, Berkeley under McBeth Family Fellowship and Berkeley Fellowship.

Copyright and License:

2012 ACM Subject Classification:

Mathematics of computing

\rightarrow

Probability and statistics ; Mathematics of computing

\rightarrow

Functional analysis ; Theory of computation

\rightarrow

Randomness, geometry and discrete structures ; Theory of computation

\rightarrow

Computational complexity and cryptography

Editors:

Alina Ene and Eshan Chattopadhyay

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The Frankl–Rödl theorem [14] is a foundational result in extremal combinatorics and theoretical computer science. It states that for any fixed $0<\gamma<1$ , assuming $(1-\gamma)n$ is even, if a set $A\subseteq\{-1,1\}^{n}$ contains no pair of distinct points at Hamming distance exactly $(1-\gamma)n$ , then the fractional size of $A$ must be exponentially small. That is, there exists a constant $\epsilon=\epsilon(\gamma)<1$ such that

|A|/2^{n}\leq\epsilon^{n}.

The corresponding Frankl–Rödl graph ${\mathrm{FR}_{\gamma}^{n}}$ is defined on vertex set $\{-1,1\}^{n}$ with edges between points at Hamming distance $(1-\gamma)n$ , with the Frankl-Rödl theorem bounding the independence number of this graph. This theorem has found broad applications in theoretical computer science, particularly in the analysis of hardness of approximation. The graph ${\mathrm{FR}_{\gamma}^{n}}$ has been used to construct integrality gap instances for problems such as 3-Coloring [25, 22, 12, 3, 23] and Vertex-Cover [25, 12, 2, 18, 17, 23].

The Frankl–Rödl theorem extends naturally from pairs of points to general forbidden configurations. A configuration of $k$ vertices is specified by a set of pairwise distances (or equivalently, inner products). Frankl and Rödl [14] showed that for any fixed $k$ , any subset $A\subseteq\{-1,1\}^{4n}$ that avoids $r$ pairwise orthogonal vectors must also have exponentially small fractional size. This result has been applied to show an $\Omega(\log n)$ integrality gap for the SDP relaxation of Min-Multicut [1].

While the original theorem asserts that for any $A\subseteq\{-1,1\}^{n}$ of size $|A|/2^{n}\geq\epsilon(\gamma)^{n}$ ,

\mathop{\bf Pr\/}_{\begin{subarray}{c}x,y\in\{-1,1\}^{n}\\ x\cdot y=(2\gamma-1)n\end{subarray}}(x\in A,y\in A)>0,

it is natural to ask whether one can give a quantitative lower bound on this probability in terms of the density $|A|/2^{n}$ . Benabbas, Hatami, and Magen [7] answered this by proving a density version of the Frankl–Rödl theorem: for any $0<\alpha<1$ , if $|A|/2^{n}\geq\alpha$ , then

\mathop{\bf Pr\/}_{\begin{subarray}{c}x,y\in\{-1,1\}^{n}\\ x\cdot y=(2\gamma-1)n\end{subarray}}(x\in A,y\in A)\geq 2\left(\alpha/2\right)% ^{\frac{2}{1-|2\gamma-1|}}-o(1).

This result is based on the reverse hypercontractivity of the Bonami–Beckner semigroup [30], and was used to prove integrality gaps for Vertex-Cover. Later Kauers et. al [23] showed that the proof can be conducted in the sum-of-squares (SOS) proof system. In particular, they showed that for any $0<\gamma\leq 1/4$ , the SOS/Lasserre SDP hierarchy at degree $4\left\lceil\frac{1}{4\gamma}\right\rceil$ certifies that the maximum independent set in ${\mathrm{FR}_{\gamma}^{n}}$ has fractional size $o(1)$ . This implies that a degree-4 algorithm from the SOS hierarchy can certify that the ${\mathrm{FR}_{\gamma}^{n}}$ SDP integrality gap instances for 3-Coloring have chromatic number $\omega(1)$ , and that a degree- $\left\lceil 1/\gamma\right\rceil$ SOS algorithm can certify the ${\mathrm{FR}_{\gamma}^{n}}$ SDP integrality gap instances for Min-Vertex-Cover has minimum vertex cover $>1-o(1)$ .

In the continuous setting, the sphere $\mathbb{S}^{n-1}$ provides a natural high-dimensional geometric analogue. This motivates the study of spherical avoidance problems: how dense can a subset $A\subseteq\mathbb{S}^{n-1}$ be while avoiding a fixed configuration of pairwise inner products? Let $\Delta_{k}(n,r)$ denote the $k$ -simplex in $\mathbb{S}^{n-1}$ with pairwise inner product $r$ . Witsenhausen’s problem [39] asks for the maximum density of a measurable set $A\subseteq\mathbb{S}^{n-1}$ avoiding orthogonal pairs, i.e., $\Delta_{2}(n,0)$ . Frankl and Wilson [15] gave the first exponentially decreasing upper bound $\sigma(A)\leq(1+o(1))(1.13)^{-n}$ , where $\sigma$ denotes the uniform surface measure on $\mathbb{S}^{n-1}$ . Kalai [21] conjectured that the extremal set consists of two opposite caps of geodesic radius $\pi/4$ ; this Double Cap Conjecture implies new lower bounds for the measurable chromatic number of $\mathbb{R}^{n}$ [13].

Regev and Klartag [36] established a density version of the Frankl–Rödl theorem on the sphere for pairs of orthogonal vectors:

\mathop{\bf Pr\/}_{\begin{subarray}{c}x,y\in{\mathbb{S}^{n-1}}\\ x\cdot y=0\end{subarray}}(x\in A,\ y\in A)\geq 0.9\,\sigma(A)^{2},

valid for any measurable set $A\subseteq{\mathbb{S}^{n-1}}$ with $\sigma(A)\geq C\exp(-cn^{1/3})$ , where $C$ and $c$ are universal constants. This result was a key component in their proof of an $\Omega(n^{1/3})$ lower bound on the classical communication complexity of the Vector in Subspace Problem (VSP). As a major consequence, they resolved a long-standing open question posed by Raz [35], demonstrating that quantum one-way communication is indeed exponentially stronger than classical two-way communication.

For configurations $\Delta_{k}(n,r)$ with $r>0$ , Castro-Silva et al. [11] proved that for any $k\geq 2$ , there exists $c=c(k,r)<1$ such that any $A\subseteq\mathbb{S}^{n-1}$ avoiding $\Delta_{k}(n,r)$ satisfies $\sigma(A)\leq(c+o(1))^{n}$ . A configuration is sphere Ramsey if any $c$ -coloring of of the sphere, there exists a monochromatic congruent copy of the configuration. Castro-Silva et al.’s result implied that all simplectic configurations $\Delta_{k}(n,r)$ with $r>0,\ k\geq 2$ are sphere Ramsey. On the other hand, Matoušek and Rödl [26] showed that any configuration $P$ with circumradius less than 1 is sphere Ramsey.

This sphere Ramsey theorem was recently used by Brakensiek, Guruswami, and Sandeep [10] to demonstrate integrality gaps for the basic SDP relaxation of certain promise CSPs: namely Boolean symmetric promise CSPs defined by a single predicate pair that lack Majority or Alternate-Threshold (AT) polymorphisms of all odd arities. Via Raghavendra’s general connection tightly linking SDP integrality gaps to Unique-Games hardness [34], this enabled BGS to conclude that such promise CSPs do not admit a robust satisfiability algorithm (in the sense of Zwick [40]) under the Unique Games conjecture. Complemeting this hardness result, BGS gave a robust satisfiability algorithm for Boolean promise CSPs that admit Majority polymorphisms of all odd arities or AT polymorphisms of all odd arities – the algorithm applied in the general promise CSP setting that could have multiple predicate pairs. Together these results led to a dichotomy theorem with respect to robust satisfiability for Boolean symmetric promise CSPs defined by a single predicate. Towards extending their hardness result to Boolean symmetric PCSPs that could include multiple predicate pairs, BGS posed the following problem: can one show a density version of spherical avoidance problems for the configuration $(x_{1},\cdots,x_{b},-x_{b+1},\cdots,-x_{k})$ where $(x_{1},\cdots,x_{b},x_{b+1},\cdots,x_{k})\in\Delta_{k}(n,r)$ . Namely, obtain a non-trivial lower bound on the quantity

\mathop{\bf Pr\/}_{(x_{1},\cdots,x_{b},x_{b+1},x_{k})\in\Delta_{k}(n,r)}\left(% x_{1}\in A,\cdots,x_{b}\in A,-x_{b+1}\in A,\cdots,-x_{k}\in A\right).

in terms of $\sigma(A)$ . While we do not directly resolve the exact configuration posed by BGS, our result applies to a broad class of configurations that includes closely related structures.

In this paper, we show the following result:

Theorem 1.

Fix $k, r$ such that $-\frac{1}{k-1}<r<1$ , there exists constant $C=C(k,r),\ \epsilon=\epsilon(k,r)$ such that

\mathop{\bf Pr\/}_{x_{1},\dots,x_{k}\in\Delta_{k}(n,r)}(x_{i}\in A\ \forall i)% \geq\Omega_{k,r}\left(\sigma(A)^{C}\right)

for all measurable $A\subseteq\mathbb{S}^{n-1}$ with $\sigma(A)\geq\omega_{k,r}(n^{-\epsilon})$ .

Our result generalizes the work of Castro-Silva et al. to simplices with any $-\frac{1}{k-1}<r<1$ , and more broadly, to a class of inductive configurations defined in Section 4 (see Theorem 14). In particular, we show that all inductive configurations are sphere Ramsey.

Inspired by the techniques of Benabbas et al. [7], who used reverse hypercontractivity of the Bonami–Beckner semigroup to show the density variant of Frankl–Rödl on $\{-1,1\}^{n}$ , we develop analogous tools on the sphere. Specifically, we prove reverse hypercontractivity of the operator

A_{t}f(x):=\mathop{\mathbb{E}\/}_{\begin{subarray}{c}y\in\mathbb{S}^{n-1}\\ x\cdot y=e^{-t}\end{subarray}}[f(y)],

which enables us to derive density versions of spherical avoidance for inductive configurations. In Section 2, we analyze the eigen-decomposition of $A_{t}$ ; in Section 3, we relate $A_{t}$ to the Poisson Markov semigroup $P_{t}$ and establish reverse hypercontractive inequalities. Finally, in Section 4, we prove our main results on density versions of the Frankl–Rödl theorem on the sphere and density spherical Ramsey statements for inductive configurations.

2 Eigen-decomposition via Spherical Harmonics

In order to analyze the eigen-decomposition of $A_{t}$ , we first introduce some fundamental notions from the theory of spherical harmonics. This decomposition of $A_{t}$ plays a central role in our analysis of reverse-hypercontractive. For a comprehensive background, we refer to the standard references [32, 38] and notes such as [16].

2.1 Spherical Harmonics

For each integer $n\geq 2$ , let $\mathbb{S}^{n-1}\subseteq\mathbb{R}^{n}$ denote the unit $n$ -sphere, defined by

\mathbb{S}^{n-1}=\{x\in\mathbb{R}^{n}:x\cdot x=1\}.

Given $p>0$ and a measurable function $f:\mathbb{S}^{n-1}\to\mathbb{R}$ , we define its $L^{p}$ norm by

\|f\|_{L^{p}(\mathbb{S}^{n-1})}:=\left(\int_{\mathbb{S}^{n-1}}|f(x)|^{p}\,d% \sigma(x)\right)^{1/p},

where $\sigma$ denotes the uniform surface measure on $\mathbb{S}^{n-1}$ , normalized such that $\int_{\mathbb{S}^{n-1}}d\sigma(x)=1$ . It follows that for $p\geq q>0$ , we have $L^{p}(\mathbb{S}^{n-1})\subseteq L^{q}(\mathbb{S}^{n-1})$ .

We focus in particular on $L^{2}(\mathbb{S}^{n-1})$ , the space of square-integrable functions. It admits an orthonormal basis consisting of spherical harmonics $\{Y_{k,\ell}\}$ , indexed by integers $k\geq 0$ (the degree) and $1\leq\ell\leq c_{k,n}$ , where

c_{k,n}=\binom{k+n-2}{k}+\binom{k+n-3}{k-1}.

Each $Y_{k,\ell}$ is the restriction to $\mathbb{S}^{n-1}$ of a harmonic, homogeneous polynomial of degree $k$ on $\mathbb{R}^{n}$ . We denote by $\mathcal{S}_{k}\subseteq L^{2}(\mathbb{S}^{n-1})$ the finite-dimensional subspace spanned by spherical harmonics of degree $k$ :

\mathcal{S}_{k}:=\operatorname{span}\{Y_{k,1},\dotsc,Y_{k,c_{k,n}}\}.

Notably, $\mathcal{S}_{0}$ consists of the constant functions. Rotations $U\in\mathrm{SO}(n)$ act on $f\in L^{2}(\mathbb{S}^{n-1})$ via

(Uf)(x):=f(U^{-1}x).

Each space $\mathcal{S}_{k}$ is invariant under the action of $\mathrm{SO}(n)$ , and furnishes an irreducible representation, i.e. any subspace $V\subseteq{\mathcal{S}_{k}}$ that is invariant under rotations must either be $\{0\}$ or ${\mathcal{S}_{k}}$ . Moreover, for $n\geq 3$ , the spaces $\mathcal{S}_{k}$ for different $k$ have different dimensions therefore are inequivalent as representations. Throughout the remainder of this paper, we assume $n\geq 3$ .

For $t\geq 0$ , define an operator $A_{t}:L^{2}(\mathbb{S}^{n-1})\to L^{2}(\mathbb{S}^{n-1})$ by

(A_{t}f)(x):=\int_{\mathbb{S}^{n-1}}f(y)\,d\sigma_{x,e^{-t}}(y)=\mathop{% \mathbb{E}\/}_{\begin{subarray}{c}y\in{\mathbb{S}^{n-1}}\\ \ x\cdot y=e^{-t}\end{subarray}}[f(y)],

where $\sigma_{x,r}$ is the uniform probability measure on the $(n-2)$ -subsphere $S_{x,r}:=\{y\in\mathbb{S}^{n-1}:x\cdot y=r\}$ .

The operator $A_{t}$ is easily seen to commute with rotations via

(A_{t}Uf)(x)=\mathop{\mathbb{E}\/}_{\begin{subarray}{c}y\in{\mathbb{S}^{n-1}}% \\ \ x\cdot y=e^{-t}\end{subarray}}[f(U^{-1}y)]=\mathop{\mathbb{E}\/}_{\begin{% subarray}{c}z\in{\mathbb{S}^{n-1}}\\ \ x\cdot Uz=e^{-t}\end{subarray}}[f(z)]=\mathop{\mathbb{E}\/}_{\begin{subarray% }{c}z\in{\mathbb{S}^{n-1}}\\ \ U^{-1}x\cdot z=e^{-t}\end{subarray}}[f(z)]=(UA_{t}f)(x)

for any $U\in\mathrm{SO}(n)$ . It is also self-adjoint by

	$\displaystyle\left\langle{A_{t}f,g}\right\rangle=\mathop{\mathbb{E}\/}_{x\in{% \mathbb{S}^{n-1}}}[g(x)A_{t}f(x)]$	$\displaystyle=\mathop{\mathbb{E}\/}_{x\in{\mathbb{S}^{n-1}}}\left[\mathop{% \mathbb{E}\/}_{y:x\cdot y=e^{-t}}[g(x)f(y)]\right]$
		$\displaystyle=\mathop{\mathbb{E}\/}_{y\in{\mathbb{S}^{n-1}}}\left[\mathop{% \mathbb{E}\/}_{x:x\cdot y=e^{-t}}[g(x)f(y)]\right]=\left\langle{f,A_{t}g}% \right\rangle.$

for all $f,g\in L^{2}(\mathbb{S}^{n-1})$ .

Using standard techniques from representation theory, we establish that the spaces $\mathcal{S}_{k}$ are eigenspaces of $A_{t}$ :

Lemma 2.

For any $k\geq 0$ and $Y_{k}\in\mathcal{S}_{k}$ , we have

A_{t}(Y_{k})=\mu_{k,t}Y_{k},

where $\mu_{k,t}=G_{k}(e^{-t})$ , with $G_{k}:[-1,1]\to\mathbb{R}$ denoting the degree- $k$ Gegenbauer polynomial (see,e.g., [32]), given by

G_{k}(r)=\mathbb{E}\left[\left(r+iX_{1}\sqrt{1-r^{2}}\right)^{k}\right],

where $X=(X_{1},\dotsc,X_{n-1})$ is uniformly distributed on $\mathbb{S}^{n-2}$ and $X_{1}$ denotes any fixed coordinate.

Proof.

By Schur’s Lemma (see e.g. [37]), any linear operator commuting with the group action must act as a scalar on each irreducible representation. Since $A_{t}$ commutes with rotations and $\mathcal{S}_{k}$ are inequivalent irreducible representations for different $k$ , the restriction of $A_{t}$ to $\mathcal{S}_{k}$ must be a scalar multiple of the identity.

To identify the eigenvalue, consider the function $f_{k}(x):=G_{k}(x\cdot v)$ for some fixed $v\in\mathbb{S}^{n-1}$ . It is known that $f_{k}\in\mathcal{S}_{k}$ [32]. Then

(A_{t}f_{k})(v)=G_{k}(e^{-t}),\quad\text{and}\quad f_{k}(v)=G_{k}(1)=1,

showing that $\mu_{k,t}=G_{k}(e^{-t})$ . $\hfill\blacktriangleleft$

2.2 Eigenvalue Estimates

We now estimate the eigenvalues $\mu_{k,t}$ .

Lemma 3.

The eigenvalues $\mu_{k,t}$ satisfy

|\mu_{k,t}-e^{-kt}|=O_{t}\left(\frac{1}{n}\right),

as $n\to\infty$ , where the implicit constant depends only on $t$ but is independent of $k$ .

Proof.

Let us first analyze the $k$ -th moments of $X_{1}$ . Notice that the density of $X_{1}$ is supported in $[-1,1]$ and proportional to $(1-x^{2})^{(n-4)/2}$ . Since the density $X_{1}$ is an odd function, the odd moments vanishes, $\mathop{\mathbb{E}\/}[X_{1}^{k}]=0$ for odd $k$ . For even $k$ , there is an estimate

\mathop{\mathbb{E}\/}[X_{1}^{k}]\leq\left(\frac{k}{n-4}\right)^{k/2}

given by [36] Lemma 5.5. We will estimate the eigenvalues $\mu_{k,t}$ for different regimes of $k$ .

When $k\leq\frac{n}{10}$ , a direct computation gives

	$\displaystyle\mu_{k,t}$	$\displaystyle=G_{k}(e^{-t})$
		$\displaystyle=\ \mathop{\mathbb{E}\/}\left[\left(e^{-t}+iX_{1}\sqrt{1-e^{-2t}}% \right)^{k}\right]$
		$\displaystyle=\ \sum_{a=0}^{k}\left(i\sqrt{1-e^{-2t}}\right)^{a}e^{-t(k-a)}E[X% _{1}^{a}]$
		$\displaystyle=\ \sum_{a=0}^{\left\lfloor k/2\right\rfloor}(-1)^{a}(1-e^{-2t})^% {a}e^{-t(k-2a)}E[X_{1}^{2a}]$
		$\displaystyle=\ e^{-kt}+\sum_{a=1}^{\left\lfloor k/2\right\rfloor}(-1)^{a}(1-e% ^{-2t})^{a}e^{-t(k-2a)}E[X_{1}^{2a}]\ .$

Therefore

	$\displaystyle\|\mu_{k,t}-e^{-kt}\|\leq{}$	$\displaystyle\sum_{a=1}^{\left\lfloor k/2\right\rfloor}(1-e^{-2t})^{a}e^{-t(k-% 2a)}\left(\frac{2a}{n-4}\right)^{a}$
	$\displaystyle\leq{}$	$\displaystyle\frac{2}{n-4}+\sum_{a=2}^{\left\lfloor k/2\right\rfloor}(1-e^{-2t% })^{a}e^{-t(k-2a)}\left(\frac{2a}{n-4}\right)^{a}$
	$\displaystyle\leq{}$	$\displaystyle\frac{2}{n-4}+\sum_{a=2}^{\left\lfloor k/2\right\rfloor}\left(% \frac{2a}{n-4}\right)^{a}$

Since $\left(\frac{2a}{n-4}\right)^{a}$ is decreasing with $a$ when $2\leq a\leq\left\lfloor k/2\right\rfloor\leq\frac{n}{20}$ , we can bound

|\mu_{k,t}-e^{-kt}|\leq\frac{2}{n-4}+(\left\lfloor k/2\right\rfloor-2)\left(% \frac{4}{n-4}\right)^{2}\leq\frac{2}{n-4}+\frac{n}{20}\left(\frac{4}{n-4}% \right)^{2}\leq O\left(\frac{1}{n}\right).

For the case where $k\geq\frac{n}{10}$ , by Markov’s inequality

\mathop{\bf Pr\/}(|X_{1}|\geq\frac{1}{2})\leq\frac{\mathop{\mathbb{E}\/}\left[% |X_{1}|^{2\left\lceil n/20\right\rceil}\right]}{(1/2)^{2\left\lceil n/20\right% \rceil}}\leq\left(\frac{4\left\lceil n/20\right\rceil}{n-4}\right)^{n/20}\leq O% \left(\frac{1}{n}\right)

which leads us to

		$\displaystyle\|\mu_{k,t}-e^{-kt}\|$
	$\displaystyle\leq{}$	$\displaystyle\|G_{k}(e^{-t})\|+\|e^{-kt}\|$
	$\displaystyle\leq{}$	$\displaystyle\mathop{\mathbb{E}\/}\left[\left\|e^{-t}+iX_{1}\sqrt{1-e^{-2t}}% \right\|^{k}\right]+\|e^{-kt}\|$
	$\displaystyle\leq{}$	$\displaystyle\mathop{\mathbb{E}\/}\left[\left(e^{-2t}+(1-e^{-2t})\|X_{1}\|\right% )^{k}\right]+\|e^{-kt}\|$
	$\displaystyle\leq{}$	$\displaystyle\mathop{\bf Pr\/}(\|X_{1}\|<\frac{1}{2})\left(e^{-2t}+\frac{1}{2}(1% -e^{-2t})\right)^{k}+\mathop{\bf Pr\/}(\|X_{1}\|\geq\frac{1}{2})+\|e^{-\frac{n}{1% 0}t}\|$
	$\displaystyle\leq{}$	$\displaystyle\ O\left(\left(\frac{1+e^{-2t}}{2}\right)^{n/10}\right)+O(\frac{1% }{n})+O_{t}(\frac{1}{n})$
	$\displaystyle\leq{}$	$\displaystyle O_{t}(\frac{1}{n})$

as $n\rightarrow\infty$ . $\hfill\blacktriangleleft$

3 Reverse Hypercontractivity of $A_{t}$

Hypercontractive inequalities play a central role in modern analysis, probability, and theoretical computer science, quantifying how semigroups “smooth out” irregularities over time by contracting $L^{q}$ norms to $L^{p}$ norms. A semigroup $(T_{t})_{t\geq 0}$ is hypercontractive if for all real-valued functions $f$ ,

\|T_{t}f\|_{p}\leq\|f\|_{q},

for $1<q<p<\infty$ , whenever $t\geq\tau(p,q)$ . These inequalities are deeply connected to logarithmic Sobolev inequalities [19] and underlie results on quantum information theory [27], diffusion processes [4], and mixing times [8].

On the Boolean hypercube $\{0,1\}^{n}$ , a canonical example is the Bonami–Beckner semigroup $T_{\rho}$ , where $0\leq\rho\leq 1$ , defined as

T_{\rho}f(x)=\mathbb{E}[f(y)],\quad\text{where }y\sim_{\rho}x,

and $y$ is obtained by flipping each bit of $x$ independently with probability $\frac{1-\rho}{2}$ . The operator satisfies the sharp hypercontractive inequality [9, 33, 5, 19]:

\|T_{\rho}f\|_{p}\leq\|f\|_{q}\quad\text{if }\rho\leq\sqrt{\frac{q-1}{p-1}}

for $1<q<p<\infty$ . This inequality underpins many foundational results in the analysis of Boolean functions, such as the KKL theorem [31], the invariance principle [31].

In contrast, reverse hypercontractivity, introduced by Mossel, Oleszkiewicz, and Sen [31], captures a complementary “anti-smoothing” phenomenon. A semigroup $(T_{t})_{t\geq 0}$ is reverse hypercontractive if for all non-negative functions $f$ ,

\|T_{t}f\|_{q}\geq\|f\|_{p},

for $0<q<p<1$ , whenever $t\geq\tau(p,q)$ . This inequality lower-bounds the dispersion of mass under the semigroup and connects to reverse log-Sobolev inequalities [31], Gaussian isoperimetry [28], and tail bounds in correlated settings.

On the Boolean hypercube, the Bonami–Beckner semigroup $T_{\rho}$ also satisfies reverse hypercontractive inequalities [31]: for all non-negative $f:\{0,1\}^{n}\to\mathbb{R}_{\geq 0}$ ,

\|T_{\rho}f\|_{q}\geq\|f\|_{p}\quad\text{if }\rho<\sqrt{\frac{1-p}{1-q}}

for all $0<q<p<1$ .

Reverse hypercontractivity has enabled several significant applications on the hypercube. It was used to prove the “It Ain’t Over Till It’s Over” conjecture [24] from social choice theory [29], and dimension-free Gaussian isoperimetric inequalities [28].

The operator $A_{t}$ serves as the analogue of the Bonami–Beckner operator on the sphere. In this section, we demonstrate that $A_{t}$ is close to the Poisson Markov semigroup $P_{t}$ in the $L^{2}$ norm. Using the logarithmic Sobolev inequality for $P_{t}$ , we then establish that $P_{t}$ satisfies reverse hypercontractivity inequalities, which in turn imply reverse hypercontractivity inequalities for $A_{t}$ .

3.1 Poisson Markov Semigroup

Definition 4.

A family $(P_{t})_{t\geq 0}$ of operators on real-valued measurable functions on ${\mathbb{S}^{n-1}}$ is called a Markov semigroup if it satisfies the following properties:

(i)

For each $t\geq 0$ , $P_{t}$ is a linear operator mapping bounded measurable functions to bounded measurable functions.
(ii)

$P_{t}(1)=1$ , where $1$ denotes the constant function on ${\mathbb{S}^{n-1}}$ (mass conservation).
(iii)

If $f\geq 0$ , then $P_{t}f\geq 0$ (positivity preservation).
(iv)

$P_{0}=\mathrm{Id}$ , the identity operator.
(v)

For any $s,t\geq 0$ , $P_{s+t}=P_{s}\circ P_{t}$ (semigroup property).
(vi)

For each $f$ , the map $t\mapsto P_{t}f$ is continuous.

Operators satisfying properties (i)–(iii) are called Markov operators. For any function $f\in L^{2}({\mathbb{S}^{n-1}})$ , we can express it in terms of the spherical harmonic basis as

f(x)=\sum_{k,l}\widehat{f_{k,l}}Y_{k,l}(x),

where $\widehat{f_{k,l}}=\langle f,Y_{k,l}\rangle$ . Define the Poisson semigroup¹¹1In the literature, e.g., [6], the Poisson semigroup is typically defined by $P_{r}f(x)=\sum_{k,l}r^{k}\widehat{f_{k,l}}Y_{k,l}(x)$ with multiplicative semigroup property $P_{rs}=P_{r}\circ P_{s}$ . We adopt a slightly modified definition here to match the additive semigroup convention of Markov semigroups. $(P_{t})_{t\geq 0}:L^{2}({\mathbb{S}^{n-1}})\to L^{2}({\mathbb{S}^{n-1}})$ by

P_{t}f(x)=\sum_{k,l}e^{-kt}\widehat{f_{k,l}}Y_{k,l}(x).

As shown in [6], this can equivalently be written in terms of the Poisson kernel

K_{r}(x,y)=\frac{1-r^{2}}{|x-ry|^{n}},\quad(-1\leq r\leq 1),

so that

P_{t}f(x)=\int_{{\mathbb{S}^{n-1}}}K_{e^{-t}}(x,y)f(y)\,d\sigma(y).

It is straightforward to verify that $P_{t}$ satisfies the Markov semigroup properties.

We now show that $A_{t}$ is close to $P_{t}$ in the $L^{2}$ -norm.

Lemma 5.

For any $f\in L^{2}({\mathbb{S}^{n-1}})$ ,

\|A_{t}f-P_{t}f\|_{2}=O_{t}(n^{-2})\|f\|_{2}

as $n\to\infty$ .

Proof.

Expressing $f$ in the spherical harmonic basis as $f(x)=\sum_{k,l}\widehat{f_{k,l}}Y_{k,l}(x)$ , we have

\|A_{t}f-P_{t}f\|_{2}=\left\|\sum_{k,l}(\mu_{k,t}-e^{-kt})\widehat{f_{k,l}}Y_{% k,l}\right\|_{2}=\sum_{k,l}(\mu_{k,t}-e^{-kt})^{2}\left(\widehat{f_{k,l}}% \right)^{2}.

By Lemma 3,

(\mu_{k,t}-e^{-kt})^{2}\leq O_{t}(n^{-2})

where we can conclude

\|A_{t}f-P_{t}f\|_{2}^{2}\leq O_{t}(n^{-2})\sum_{k,l}\left(\widehat{f_{k,l}}% \right)^{2}=O_{t}(n^{-2})\|f\|_{2}^{2}\ .\

$\hfill\blacktriangleleft$

3.2 Reverse Hypercontractivity

Mossel, Oleszkiewicz, and Sen [31] showed that for Markov semigroups, reverse hypercontractivity inequalities follow from log-Sobolev inequalities. We will use this fact to establish reverse hypercontractivity for the Poisson semigroup $P_{t}$ . For any positive function $f>0$ , define its entropy by

\mathop{\bf Ent\/}(f)=\mathop{\mathbb{E}\/}[f\log f]-\mathop{\mathbb{E}\/}[f]% \cdot\log\mathop{\mathbb{E}\/}[f].

For a Markov semigroup $(P_{t})_{t\geq 0}$ with generator $L$ , the Dirichlet form is defined as

\mathcal{E}(f,g)=\mathop{\mathbb{E}\/}[fLg]=\mathop{\mathbb{E}\/}[gLf]=% \mathcal{E}(g,f)=-\left.\frac{d}{dt}\mathop{\mathbb{E}\/}[fP_{t}g]\right|_{t=0}.

Lemma 6 ([6], Theorem 1).

The Poisson semigroup $(P_{t})_{t\geq 0}$ satisfies the log-Sobolev inequality:

\mathop{\bf Ent\/}(f^{2})\leq C\mathcal{E}(f,f),

for some constant $C\leq\frac{1}{2}$ .

Lemma 7 ([31], Theorem 1.10).

If a Markov semigroup $(P_{t})_{t\geq 0}$ satisfies the log-Sobolev inequality with constant $C$ , then for all $q<p<1$ and every positive function $f:{\mathbb{S}^{n-1}}\to\mathbb{R}$ , the following inequality holds for all $t\geq\frac{C}{4}\log\frac{1-q}{1-p}$ :

\|P_{t}f\|_{q}\geq\|f\|_{p}.

We now deduce a reverse hypercontractivity inequality for the operator $A_{t}$ , leveraging its proximity to $P_{t}$ in the $L^{2}$ norm.

Theorem 8.

For any positive functions $f,g\in L^{2}({\mathbb{S}^{n-1}})$ , the following reverse hypercontractivity inequality holds:

\mathop{\mathbb{E}\/}_{x\cdot y=e^{-t}}[f(x)g(y)]=\langle f,A_{t}g\rangle\geq% \|f\|_{p}\|g\|_{p}-O_{t}(n^{-2})\|f\|_{2}\|g\|_{2},

as $n\to\infty$ , for all $0<p\leq 1-e^{-4t}$ .

Proof.

By Lemma 5, we have

\mathop{\mathbb{E}\/}_{x\cdot y=e^{-t}}[f(x)g(x)]=\langle f,A_{t}g\rangle\geq% \langle f,P_{t}g\rangle-O_{t}(n^{-2})\|f\|_{2}\|g\|_{2}.

Let $p^{\prime}=\frac{p}{p-1}$ be the Hölder conjugate of $p$ , so that $1/p+1/p^{\prime}=1$ . Applying the reverse Hölder inequality (see [20], Theorem 13), we obtain

\langle f,P_{t}g\rangle=\|fP_{t}g\|_{1}\geq\|f\|_{p}\|P_{t}g\|_{p^{\prime}}.

From Lemma 6, the semigroup $(P_{t})_{t\geq 0}$ satisfies a log-Sobolev inequality with constant $C\leq\frac{1}{2}$ . Thus, by Lemma 7,

\|P_{t}g\|_{p^{\prime}}\geq\|g\|_{p}

provided that $t\geq\frac{1}{8}\log\frac{1-p^{\prime}}{1-p}=-\frac{1}{4}\log(1-p)$ . Therefore, the inequality holds for all $p\leq 1-e^{-4t}$ , completing the proof. $\hfill\blacktriangleleft$

4 Density Sphere Avoidance

In this section, we present our main results: the density version of the Frankl–Rödl theorem on the sphere (Theorem 11) and the density sphere avoidance result for inductive configurations (Theorem 14).

4.1 Inductive Configurations

Let $(v_{1},\cdots,v_{k})$ be a configuration on ${\mathbb{S}^{n-1}}$ , where $v_{i}\in{\mathbb{S}^{n-1}}$ are distinct vectors satisfying $\left\langle{v_{i},v_{j}}\right\rangle=r_{i}$ for $i<j$ . Specifically, writing $v_{i}$ as column vectors, we consider configurations whose covariance matrix has the form

R(r_{1},\cdots,r_{k-1}):=(v_{1},\cdots,v_{k})^{T}(v_{1},\cdots,v_{k})=\begin{% pmatrix}1&r_{1}&r_{1}&\cdots&r_{1}&r_{1}\\ r_{1}&1&r_{2}&\cdots&r_{2}&r_{2}\\ r_{1}&r_{2}&1&\cdots&r_{3}&r_{3}\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ r_{1}&r_{2}&r_{3}&\cdots&1&r_{k-1}\\ r_{1}&r_{2}&r_{3}&\cdots&r_{k-1}&1\end{pmatrix}.

Let $\Delta(n,R)=\{(x_{1},\cdots,x_{k}):(x_{1},\cdots,x_{k})^{T}(x_{1},\cdots,x_{k}% )=R\}\subseteq({\mathbb{S}^{n-1}})^{k}$ denote the set of tuples that are congruent to the configuration $(v_{1},\cdots,v_{k})$ defined by $R$ . We refer to such configurations as inductive configurations, as they can be constructed recursively as follows:

Start with any vector $v_{1}$ and a choice of $-1<r_{1}<1$ . Choose $v_{2}$ on the $(n-2)$ -dimensional subsphere $S_{v_{1},r_{1}}=\{x\in{\mathbb{S}^{n-1}}:\left\langle{x,v_{1}}\right\rangle=r_% {1}\}$ . Next, select $r_{2}$ such that the intersection $S_{v_{1},r_{1}}\cap S_{v_{2},r_{2}}$ is nonempty, and choose $v_{3}$ on this $(n-3)$ -dimensional subsphere. Proceed inductively: for each $v_{i}$ , choose it on the $(n-i)$ -dimensional subsphere $\bigcap_{j<i}S_{v_{j},r_{j}}$ .

Throughout the paper, we exclude a special case of inductive configuration–configurations where the length of $v_{k}-v_{k-1}$ is the diameter of $\bigcap_{j<k-1}S_{v_{j},r_{j}}$ – for reasons that will become clear in the later proof. Notably, both the length of $v_{k}-v_{k-1}$ and the diameter of $\bigcap_{j<k-1}S_{v_{j},r_{j}}$ are independent of the ambient dimension $n$ , so this is a constraint on the configuration $R$ itself.

We will show that, fixing any inductive configuration $R$ (excluding the special case), any set $A\subseteq{\mathbb{S}^{n-1}}$ of constant spherical measure will, as $n\to\infty$ , contain many congruent copies of $R$ . Moreover, we provide an explicit lower bound on the probability that a randomly chosen congruent copy of $R$ lies entirely within $A$ .

4.2 Configuration with Pairwise Orthogonal Vectors

Let $\Delta_{k}(n,0):=\Delta(n,I_{k})=\{(x_{1},\cdots,x_{k})\in({\mathbb{S}^{n-1}})% ^{k}:\left\langle{x_{i},x_{j}}\right\rangle=0,\ \forall i\neq j\}$ denote the set of all $k$ -tuples of pairwise orthogonal vectors in ${\mathbb{S}^{n-1}}$ . Recall that $S_{x,r}$ denotes the $(n-2)$ -subsphere $\{y\in\mathbb{S}^{n-1}:x\cdot y=r\}$ and $\sigma_{x,r}$ is the uniform probability measure on $S_{x,r}$ .

Lemma 9 ([36], Theorem 2.2).

For any measurable set $A\subseteq{\mathbb{S}^{n-1}}$ , the condition

\left|\frac{\sigma_{x,0}(A\cap S_{x,0})}{\sigma(A)}\right|\leq 0.1

holds for all $x\in{\mathbb{S}^{n-1}}$ , except on a subset of measure at most $C\exp(-cn^{1/3})$ , where $C,c>0$ are universal constants.

Theorem 10.

Fix an integer $k\geq 2$ . For any measurable set $A\subseteq{\mathbb{S}^{n-1}}$ , the probability that a tuple $(v_{1},\cdots,v_{k})$ drawn uniformly at random from $\Delta_{k}(n,0)$ lies entirely in $A$ is at least

\mathop{\bf Pr\/}_{(x_{1},\cdots,x_{k})\in\Delta_{k}(n,0)}(x_{1}\in A,\cdots,x% _{k}\in A)\geq\Omega_{k}\left(\sigma(A)^{k}-C_{k}\exp(-cn^{1/3})\sigma(A)^{k-1% }\right),

where $c>0$ is a universal constant and $C_{k}$ is a constant depending only on $k$ .

Proof.

We proceed by induction on $k$ . Let $B\subseteq{\mathbb{S}^{n-1}}$ denote the set of all $x_{1}$ for which

\left|\frac{\sigma_{x_{1},0}(A\cap S_{x_{1},0})}{\sigma(A)}\right|\leq 0.1.

By Lemma 9, we have $\sigma(B)\geq 1-C\exp(-cn^{1/3})$ , where $C,c>0$ are universal constants.

When $k=2$ ,

		$\displaystyle\mathop{\bf Pr\/}_{(x_{1},x_{2})\in\Delta_{2}(n,0)}(x_{1}\in A,x_% {2}\in A)$
	$\displaystyle\geq{}$	$\displaystyle\mathop{\bf Pr\/}_{(x_{1},x_{2})\in\Delta_{2}(n,0)}(x_{1}\in A% \cap B,x_{2}\in A)$
	$\displaystyle={}$	$\displaystyle\mathop{\bf Pr\/}(x_{1}\in A\cap B)\cdot\mathop{\bf Pr\/}(x_{2}% \in A\mid x_{1}\in A\cap B)$
	$\displaystyle={}$	$\displaystyle\mathop{\bf Pr\/}(x_{1}\in A\cap B)\cdot\mathop{\mathbb{E}\/}[% \sigma_{x_{1},0}(A\cap S_{x_{1},0})\mid x_{1}\in A\cap B]$
	$\displaystyle\geq{}$	$\displaystyle\left(\sigma(A)-C\exp(-cn^{1/3})\right)\cdot 0.9\sigma(A)$
	$\displaystyle\geq{}$	$\displaystyle\Omega\left(\sigma(A)^{2}-C\exp(-cn^{1/3})\sigma(A)\right)$

When $k>2$ , assume the claim holds for $k-1$ . Then:

		$\displaystyle\mathop{\bf Pr\/}_{(x_{1},\cdots,x_{k})\in\Delta_{k}(n,0)}(x_{1}% \in A,\cdots,x_{k}\in A)$
	$\displaystyle\geq{}$	$\displaystyle\mathop{\bf Pr\/}(x_{1}\in A\cap B)\cdot\mathop{\bf Pr\/}(x_{2},% \cdots,x_{k}\in A\mid x_{1}\in A\cap B)$
	$\displaystyle={}$	$\displaystyle\mathop{\bf Pr\/}(x_{1}\in A\cap B)\cdot\mathop{\bf Pr\/}(x_{2},% \cdots,x_{k}\in A\cap S_{x_{1},0}\mid x_{1}\in A\cap B).$

By the inductive hypothesis applied within the subsphere $S_{x_{1},0}$ , we have:

		$\displaystyle\mathop{\bf Pr\/}(x_{2},\cdots,x_{k}\in A\cap S_{x_{1},0}\mid x_{% 1}\in A\cap B)$
	$\displaystyle\geq{}$	$\displaystyle\Omega_{k}\left((0.9\sigma(A))^{k-1}-C_{k}\exp(-cn^{1/3})(0.9% \sigma(A))^{k-2}\right)$
	$\displaystyle\geq{}$	$\displaystyle\Omega_{k}\left(\sigma(A)^{k-1}-C_{k}\exp(-cn^{1/3})\sigma(A)^{k-% 2}\right).$

Multiplying with $\mathop{\bf Pr\/}(x_{1}\in A\cap B)\geq\sigma(A)-C\exp(-cn^{1/3})$ , we obtain:

		$\displaystyle\mathop{\bf Pr\/}(x_{1},\cdots,x_{k}\in A)$
	$\displaystyle\geq{}$	$\displaystyle\Omega_{k}\left(\sigma(A)^{k-1}-C_{k}\exp(-cn^{1/3})\sigma(A)^{k-% 2}\right)\cdot\left(\sigma(A)-C\exp(-cn^{1/3})\right)$
	$\displaystyle\geq{}$	$\displaystyle\Omega_{k}\left(\sigma(A)^{k}-C^{\prime}_{k}\exp(-cn^{1/3})\sigma% (A)^{k-1}\right),$

completing the induction. $\hfill\blacktriangleleft$

4.3 Main Results

We first prove a two-set version of the density sphere Frankl-Rödl theorem which will be later used for induction on inductive configurations.

Theorem 11 (Density Sphere Frankl-Rödl).

For any measurable sets $A,B\subseteq{\mathbb{S}^{n-1}}$ and any $r\in(-1,1)$ , we have

\mathop{\bf Pr\/}_{x\cdot y=r}(x\in A,\ y\in B)\geq(\sigma(A)\sigma(B))^{1/(1-% r^{4})}-O_{r}(n^{-2})\sqrt{\sigma(A)\sigma(B)}.

Proof.

The case $r=0$ follows from a stronger version of Lemma 9, given by [36, Theorem 5.1]. Now consider $r\neq 0$ . Let

f=\mathbf{1}_{A},\quad\text{and}\quad g(x)=\begin{cases}\mathbf{1}_{B}(x)&% \text{if }r>0,\\ \mathbf{1}_{B}(-x)&\text{if }r<0.\end{cases}

Applying Theorem 8 with $p=1-r^{4}$ , we obtain

	$\displaystyle\mathop{\bf Pr\/}_{x\cdot y=r}(x\in A,\ y\in B)$	$\displaystyle=\mathop{\mathbb{E}\/}_{x\cdot y=\|r\|}[f(x)g(y)]$
		$\displaystyle\geq\\|f\\|_{p}\\|g\\|_{p}-O_{r}(n^{-2})\\|f\\|_{2}\\|g\\|_{2}$
		$\displaystyle=(\sigma(A)\sigma(B))^{1/(1-r^{4})}-O_{r}(n^{-2})\sqrt{\sigma(A)% \sigma(B)}\ .\$

$\hfill\blacktriangleleft$

Fix an inductive configuration $R$ and let $A\subseteq{\mathbb{S}^{n-1}}$ be measurable. For any $x\in{\mathbb{S}^{n-1}}$ , recall that $\sigma_{x,r}$ denotes the uniform measure on $S_{x,r}$ . We say that a vector $x\in A$ is good if

\sigma_{x,r}(A\cap S_{x,r})\geq\frac{1}{2}\sigma(A)^{(1+r^{4})/(1-r^{4})}.

Define the set of good vectors:

A_{\mathrm{good}}=\left\{x\in{\mathbb{S}^{n-1}}:\sigma_{x,r}(A\cap S_{x,r})% \geq\frac{1}{2}\sigma(A)^{(1+r^{4})/(1-r^{4})}\right\}.

Using Theorem 11, we can show that many such good vectors must exist.

Proposition 12.

The set of good vectors satisfies

\sigma(A_{\mathrm{good}})\geq\frac{1}{2}\sigma(A)^{2/(1-r^{4})}-O_{r}(n^{-2})% \sigma(A).

Proof.

By Theorem 11, we have

\mathop{\mathbb{E}\/}_{x}[\sigma_{x,r}(A\cap S_{x,r})\mid x\in A]=\mathop{\bf Pr% \/}_{x\cdot y=r}(y\in A\mid x\in A)\geq\sigma(A)^{(1+r^{4})/(1-r^{4})}-O_{r}(n% ^{-2}).

Split the expectation by conditioning on $A_{\mathrm{good}}$ and its complement:

	$\displaystyle\mathop{\mathbb{E}\/}_{x}[\sigma_{x,r}(A\cap S_{x,r})\mid x\in A]$	$\displaystyle=\mathop{\mathbb{E}\/}[\sigma_{x,r}(A\cap S_{x,r})\mid x\in A_{% \mathrm{good}}]\mathop{\bf Pr\/}(x\in A_{\mathrm{good}}\mid x\in A)$
		$\displaystyle\quad+\mathop{\mathbb{E}\/}[\sigma_{x,r}(A\cap S_{x,r})\mid x% \notin A_{\mathrm{good}}]\mathop{\bf Pr\/}(x\notin A_{\mathrm{good}}\mid x\in A)$
		$\displaystyle\leq 1\cdot\mathop{\bf Pr\/}(x\in A_{\mathrm{good}}\mid x\in A)+% \frac{1}{2}\sigma(A)^{(1+r^{4})/(1-r^{4})}.$

Rearranging yields

\mathop{\bf Pr\/}(x\in A_{\mathrm{good}}\mid x\in A)\geq\mathop{\mathbb{E}\/}_% {x}[\sigma_{x,r}(A\cap S_{x,r})\mid x\in A]-\frac{1}{2}\sigma(A)^{(1+r^{4})/(1% -r^{4})},

and thus

\sigma(A_{\mathrm{good}})=\mathop{\bf Pr\/}(x\in A_{\mathrm{good}}\mid x\in A)% \cdot\sigma(A)\geq\frac{1}{2}\sigma(A)^{2/(1-r^{4})}-O_{r}(n^{-2})\sigma(A)\ .\

$\hfill\blacktriangleleft$ The following proposition shows the relation between inner product on ${\mathbb{S}^{n-1}}$ and the normalized inner product on $S_{x,c}$ :

Proposition 13.

Let $x_{1},x_{2},x_{3}\in{\mathbb{S}^{n-1}}$ be such that $\left\langle{x_{1},x_{2}}\right\rangle=\left\langle{x_{1},x_{3}}\right\rangle=c$ and $\left\langle{x_{2},x_{3}}\right\rangle=r$ . For $i=2,3$ , we can write

x_{i}=cx_{1}+\sqrt{1-c^{2}}y_{i},

where $y_{i}=\frac{x_{i}-cx_{1}}{\|x_{i}-cx_{1}\|_{2}}$ satisfies $\left\langle{y_{i},x_{1}}\right\rangle=0$ and

\left\langle{y_{2},y_{3}}\right\rangle=f_{c}(r),

with $f_{c}(r)=\frac{r-c^{2}}{1-c^{2}}$ .

Proof.

A direct computation shows that $y_{i}$ is orthogonal to $x_{1}$ and that $\|x_{i}-cx_{1}\|_{2}=\sqrt{1-c^{2}}$ . Thus,

	$\displaystyle\left\langle{y_{2},y_{3}}\right\rangle$	$\displaystyle=\frac{\left\langle{x_{2}-cx_{1},x_{3}-cx_{1}}\right\rangle}{1-c^% {2}}$
		$\displaystyle=\frac{\left\langle{x_{2},x_{3}}\right\rangle-c\left\langle{x_{1}% ,x_{3}}\right\rangle-c\left\langle{x_{1},x_{2}}\right\rangle+c^{2}\\|x_{1}\\|_{2% }^{2}}{1-c^{2}}$
		$\displaystyle=\frac{r-c^{2}}{1-c^{2}}\ .\$

$\hfill\blacktriangleleft$

We now apply the above propositions to prove our main result using induction.

Theorem 14.

Let $(v_{1},\dots,v_{k})$ be an inductive configuration with covariance matrix $R$ , and assume that

\left\lVert v_{k}-v_{k-1}\right\rVert_{2}\neq\operatorname{diam}\left(\bigcap_% {j<k-1}S_{v_{j},r_{j}}\right).

Then for any measurable set $A\subseteq\mathbb{S}^{n-1}$ with $\sigma(A)\geq\omega_{R}(n^{-\epsilon_{R}})$ , the probability that a uniformly random tuple $(x_{1},\dots,x_{k})\in\Delta(n,R)$ lies entirely in $A$ satisfies

\mathop{\bf Pr\/}_{(x_{1},\dots,x_{k})\in\Delta(n,R)}(x_{1}\in A,\dots,x_{k}% \in A)\geq\Omega_{R}(\sigma(A)^{C_{R}}),

as $n\to\infty$ . The constant $C_{R}$ is given by

C_{R}=\sum_{i=1}^{k-1}\frac{2}{1-c_{i}^{4}}\prod_{j=1}^{i-1}\frac{1+c_{j}^{4}}% {1-c_{j}^{4}},

with

c_{1}=r_{1},\quad c_{i}=(f_{c_{i-1}}\circ\cdots\circ f_{c_{1}})(r_{i}),\quad i% =2,\dots,k-1,

and $f_{c}(r)=\frac{r-c^{2}}{1-c^{2}}$ . The constant $\epsilon_{R}$ is given by

\epsilon_{R}=2\prod_{i=1}^{k-1}\frac{1-c_{i}^{4}}{1+c_{i}^{4}}.

Proof.

We proceed by induction on $k$ . The base case $k=2$ follows directly from Theorem 11. The condition $v_{2}-v_{1}\neq\operatorname{diam}({\mathbb{S}^{n-1}})$ ensures $r=\left\langle{v_{1},v_{2}}\right\rangle>-1$ and the condition $\sigma(A)\geq\omega_{R}(n^{-\epsilon_{R}})$ ensures that the error term goes to $0$ .

Assume the result holds for all configurations of size $<k$ , and let $c_{1}=r_{1}$ . Define

A_{\mathrm{good}}=\left\{x\in{\mathbb{S}^{n-1}}:\sigma_{x,c_{1}}(A\cap S_{x,c_% {1}})\geq\frac{1}{2}\sigma(A)^{(1+c_{1}^{4})/(1-c_{1}^{4})}\right\}.

Then,

	$\displaystyle\mathop{\bf Pr\/}_{(x_{1},\dots,x_{k})\in\Delta(n,R)}(x_{1},\dots% ,x_{k}\in A)$	$\displaystyle=\mathop{\bf Pr\/}(x_{1}\in A)\cdot\mathop{\bf Pr\/}(x_{2},\dots,% x_{k}\in A\mid x_{1}\in A)$
		$\displaystyle\geq\mathop{\bf Pr\/}(x_{1}\in A_{\mathrm{good}})\cdot\mathop{\bf Pr% \/}(x_{2},\dots,x_{k}\in A\mid x_{1}\in A_{\mathrm{good}}).$

Given $x_{1}$ , we write $x_{i}=c_{1}x_{1}+\sqrt{1-c_{1}^{2}}y_{i}$ for $i\geq 2$ , where $y_{i}=\frac{x_{i}-r_{1}x_{1}}{\left\lVert x_{i}-r_{1}x_{1}\right\rVert_{2}}$ . Conditioned on $x_{1}$ , according to Proposition 13, the induced configuration $(y_{2},\dots,y_{k})$ follows from a uniform distribution over $\Delta(n-1,R^{\prime})$ , where

R^{\prime}=R(f_{c_{1}}(r_{2}),\dots,f_{c_{1}}(r_{k})).

Given $x_{1}$ , the event $x_{2}\in A,\cdots,x_{k}\in A$ is equal to $y_{2}\in A\cap S_{x_{1},c_{1}},\cdots,y_{k}\in A\cap S_{x_{1},c_{1}}$ . Conditioned on $x_{1}\in A_{\mathrm{good}}$ , we have $\sigma_{x_{1},c_{1}}(A\cap S_{x_{1},c_{1}})\geq\frac{1}{2}\sigma(A)^{(1+c_{1}^% {4})/(1-c_{1}^{4})}\geq\omega_{R^{\prime}}(n^{-\epsilon_{R^{\prime}}})$ , so by the inductive hypothesis:

\mathop{\bf Pr\/}(y_{2},\dots,y_{k}\in A\cap S_{x_{1},c_{1}})\geq\Omega_{R}% \left(\sigma(A)^{C_{R^{\prime}}(1+c_{1}^{4})/(1-c_{1}^{4})}\right).

with

C_{R^{\prime}}=\sum_{i=2}^{k-1}\frac{2}{1-c_{i}^{4}}\prod_{j=2}^{i-1}{\frac{1+% c_{j}^{4}}{1-c_{j}^{4}}}

where $c_{2}=f_{c_{1}}(r_{2})$ and

c_{i}=(f_{c_{i-1}}\circ\cdots\circ f_{c_{2}})(f_{c_{1}}(r_{i}))=(f_{c_{i-1}}% \circ\cdots\circ f_{c_{1}})(r_{i}),\ i=3,\cdots,k-1

By Proposition 12, we also have

\mathop{\bf Pr\/}(x_{1}\in A_{\mathrm{good}})\geq\Omega_{R}(\sigma(A)^{2/(1-c_% {1}^{4})}).

Multiplying the two bounds give

\mathop{\bf Pr\/}(x_{1},\dots,x_{k}\in A)\geq\Omega_{R}\left(\sigma(A)^{C_{R}}% \right),

where

C_{R}=\frac{2}{1-c_{1}^{4}}+\frac{1+c_{1}^{4}}{1-c_{1}^{4}}C_{R^{\prime}}=\sum% _{i=1}^{k-1}\frac{2}{1-c_{i}^{4}}\prod_{j=1}^{i-1}\frac{1+c_{j}^{4}}{1-c_{j}^{% 4}}\ .\

$\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 15.

The condition

\left\lVert v_{k}-v_{k-1}\right\rVert_{2}\neq\operatorname{diam}\left(\bigcap_% {j<k-1}S_{v_{j},r_{j}}\right)

is equivalent to $c_{k-1}\neq-1$ , which is necessary for applying Theorem 11. For a given configuration $(v_{1},\dots,v_{k})$ , the quantity $c_{i}$ corresponds to the inner product between $v_{i}$ and later vectors $v_{j}$ , after projecting to the $(n-i)$ -subsphere $\bigcap_{l<i}S_{v_{l},r_{l}}$ and normalizing. Since $v_{1},\dots,v_{k}$ are distinct, we have $-1<c_{i}<1$ for all $i\leq k-2$ and $c_{k-1}<1$ . The only forbidden case is $c_{k-1}=-1$ , which occurs precisely when $v_{k}-v_{k-1}$ equals the diameter of the intersection $\bigcap_{j<k-1}S_{v_{j},r_{j}}$ .

A configuration is sphere Ramsey if for any $c>0$ , any $c$ -coloring of the sphere contains a monochromatic congruent copy of the configuration,. Since any $c$ -coloring must contain a monochromatic set $A$ with $\sigma(A)\geq 1/c$ , an immediate corollary to Theorem 14 is that all inductive configurations (excluding the special case) are sphere Ramsey.

Corollary 16.

Let $(v_{1},\dots,v_{k})$ be an inductive configuration with covariance matrix $R$ , and assume that

v_{k}-v_{k-1}\neq\operatorname{diam}\left(\bigcap_{j<k-1}S_{v_{j},r_{j}}\right).

Then $R$ is sphere Ramsey.

A particularly important class of inductive configurations are $k$ -simplices:

\Delta_{k}(n,r):=\Delta(n,R(r,\dots,r))=\{(x_{1},\dots,x_{k})\in({\mathbb{S}^{% n-1}})^{k}:\left\langle{x_{i},x_{j}}\right\rangle=r,\ \forall i\neq j\}.

In this case, the coefficients $c_{i}$ admit the closed-form expression $c_{i}=\frac{r}{1+(i-1)r}$ . The condition $c_{k-1}>-1$ is equivalent to $r>-\frac{1}{k-1}$ . We thus obtain the following corollary:

Corollary 17.

Fix any $r\in\left(-\frac{1}{k-1},1\right)$ . For any measurable set $A\subseteq\mathbb{S}^{n-1}$ with $\sigma(A)\geq\omega_{k,r}(n^{-\epsilon_{k,r}})$ , the probability that a uniformly random tuple $(x_{1},\dots,x_{k})\in\Delta_{k}(n,r)$ lies entirely in $A$ satisfies

\mathop{\bf Pr\/}_{(x_{1},\dots,x_{k})\in\Delta_{k}(n,r)}(x_{1}\in A,\dots,x_{% k}\in A)\geq\Omega_{k,r}(\sigma(A)^{C_{k,r}}),

as $n\to\infty$ . The constants $C_{k,r},\ \epsilon_{k,r}$ are given by

C_{k,r}=\sum_{i=1}^{k-1}\frac{2}{1-c_{i}^{4}}\prod_{j=1}^{i-1}\frac{1+c_{j}^{4% }}{1-c_{j}^{4}}\qquad\epsilon_{k,r}=2\prod_{i=1}^{k-1}\frac{1-c_{i}^{4}}{1+c_{% i}^{4}},

where

c_{i}=\frac{r}{1+(i-1)r},\quad\text{for }i=1,\dots,k-1.

5 Open Problems

Our density version of the Frankl–Rödl theorem on the sphere (Theorem 11) requires the set $A\subseteq\mathbb{S}^{n-1}$ to have spherical measure $\sigma(A)>\omega(n^{-2})$ in order to guarantee a non-trivial lower bound. In contrast, the classical Frankl–Rödl theorem asserts that for any $-1<r<1$ , there exists a constant $\epsilon=\epsilon(r)>0$ such that

\mathop{\bf Pr\/}_{x\cdot y=r}(x\in A,y\in A)>0

holds for all sets $A$ with $\sigma(A)>\Omega(\epsilon^{n})$ . Notably, when $r=0$ , our result in Theorem 10 recovers the classical theorem for exponentially small sets. A natural open problem is to extend our techniques and obtain explicit lower bounds on

\mathop{\bf Pr\/}_{x\cdot y=r}(x\in A,y\in A)

for all $-1<r<1$ , even when $\sigma(A)$ is exponentially small in $n$ .

Another direction concerns the class of configurations we consider. Our density result applies to inductive configurations, but Matoušek and Rödl [26] showed that fix constant $c$ and for any configuration $P$ with circumradius less than 1, any $c$ coloring of ${\mathbb{S}^{n-1}}$ contains a monochromatic copy of $P$ . It remains open whether one can establish a density version of this theorem – that is, to show

\mathop{\bf Pr\/}_{(x_{1},\ldots,x_{k})\in P}(x_{i}\in A\ \forall i)>\epsilon(% \sigma(A))

for any set $A\subseteq\mathbb{S}^{n-1}$ with constant density $\sigma(A)>\epsilon(P)$ where $\epsilon(\sigma(A))$ is a lower bound on the probability in terms of $\sigma(A)$ .

Finally, our current results can be almost extended to 3-point configurations. For example, using Theorem 11, we can obtain bounds on

\mathop{\bf Pr\/}_{\begin{subarray}{c}x\cdot y=r_{1}\\ x\cdot z=r_{2}\end{subarray}}(x\in A,y\in A,z\in A),

but this does not yet yield control over 3-point configurations, which require bounding

\mathop{\bf Pr\/}_{\begin{subarray}{c}x\cdot y=r_{1}\\ x\cdot z=r_{2}\\ y\cdot z=r_{3}\end{subarray}}(x\in A,y\in A,z\in A).

It is an open question whether a density theorem can be proved for general 3-point configurations on the sphere.

References

[1] Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev. $O(\sqrt{\log n})$ approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems. In Proceedings of the 37th ACM symposium on Theory of computing, pages 573–581, 2005.
[2] Sanjeev Arora, Béla Bollobás, László Lovász, and Iannis Tourlakis. Proving integrality gaps without knowing the linear program. Theory of Computing, 2:19–51, 2006. doi:10.4086/TOC.2006.V002A002.
[3] Sanjeev Arora and Rong Ge. New tools for graph coloring. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 1–12. Springer, 2011. doi:10.1007/978-3-642-22935-0_1.
[4] Dominique Bakry and Michel Émery. Diffusions hypercontractives. In Séminaire de Probabilités XIX 1983/84: Proceedings, pages 177–206. Springer, 2006.
[5] William Beckner. Inequalities in Fourier analysis. Annals of Mathematics, 102(1):159–182, 1975.
[6] William Beckner. Sobolev inequalities, the Poisson semigroup, and analysis on the sphere Sn. Proceedings of the National Academy of Sciences, 89(11):4816–4819, 1992.
[7] Siavosh Benabbas, Hamed Hatami, and Avner Magen. An isoperimetric inequality for the Hamming cube with applications for integrality gaps in degree-bounded graphs. Unpublished, 1(1.2):1, 2012.
[8] Sergey Bobkov and Prasad Tetali. Modified log-sobolev inequalities, mixing and hypercontractivity. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 287–296, 2003. doi:10.1145/780542.780586.
[9] Aline Bonami. Étude des coefficients de fourier des fonctions de lp(g). In Annales de l’institut Fourier, volume 20, pages 335–402, 1970.
[10] Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep. SDPs and robust satisfiability of promise CSP. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 609–622, 2023. doi:10.1145/3564246.3585180.
[11] Davi Castro-Silva, Fernando de Oliveira Filho, Lucas Slot, and Frank Vallentin. A recursive Lovász theta number for simplex-avoiding sets. Proceedings of the American Mathematical Society, 150(8):3307–3322, 2022.
[12] Moses Charikar. On semidefinite programming relaxations for graph coloring and vertex cover. In Proceedings of the 13th annual ACM-SIAM symposium on Discrete algorithms, pages 616–620, 2002. URL: http://dl.acm.org/citation.cfm?id=545381.545462.
[13] Evan DeCorte and Oleg Pikhurko. Spherical sets avoiding a prescribed set of angles. International Mathematics Research Notices, 2016(20):6095–6117, 2016.
[14] Peter Frankl and Vojtěch Rödl. Forbidden intersections. Transactions of the American Mathematical Society, 300(1):259–286, 1987.
[15] Peter Frankl and Richard M. Wilson. Intersection theorems with geometric consequences. Combinatorica, 1:357–368, 1981. doi:10.1007/BF02579457.
[16] Jean Gallier. Notes on spherical harmonics and linear representations of Lie groups. preprint, 2009.
[17] Konstantinos Georgiou, Avner Magen, Toniann Pitassi, and Iannis Tourlakis. Integrality gaps of 2-o(1) for vertex cover SDPs in the Lovász–Schrijver hierarchy. SIAM Journal on Computing, 39(8):3553–3570, 2010.
[18] Konstantinos Georgiou, Avner Magen, and Iannis Tourlakis. Vertex cover resists SDPs tightened by local hypermetric inequalities. In International Conference on Integer Programming and Combinatorial Optimization, pages 140–153. Springer, 2008. doi:10.1007/978-3-540-68891-4_10.
[19] Leonard Gross. Logarithmic Sobolev inequalities. American Journal of Mathematics, 97(4):1061–1083, 1975.
[20] Godfrey Harold Hardy, John Edensor Littlewood, and George Pólya. Inequalities. Cambridge university press, 1952.
[21] Gil Kalai and R Wilson. How large can a spherical set without two orthogonal vectors be? Combinatorics and more (weblog), 2009.
[22] David Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite programming. Journal of the ACM (JACM), 45(2):246–265, 1998. doi:10.1145/274787.274791.
[23] Manuel Kauers, Ryan O’Donnell, Li-Yang Tan, and Yuan Zhou. Hypercontractive inequalities via SOS, and the Frankl–Rödl graph. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1644–1658. SIAM, 2014. doi:10.1137/1.9781611973402.119.
[24] Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 767–775, 2002. doi:10.1145/509907.510017.
[25] Jon Kleinberg and Michel X Goemans. The Lovász theta function and a semidefinite programming relaxation of vertex cover. SIAM Journal on Discrete Mathematics, 11(2):196–204, 1998. doi:10.1137/S0895480195287541.
[26] Jiří Matoušek and Vojtěch Rödl. On Ramsey sets in spheres. Journal of Combinatorial Theory, Series A, 70(1):30–44, 1995.
[27] Ashley Montanaro. Some applications of hypercontractive inequalities in quantum information theory. Journal of Mathematical Physics, 53(12), 2012.
[28] Elchanan Mossel and Joe Neeman. Robust dimension free isoperimetry in Gaussian space. The Annals of Probability, 43(3), May 2015. doi:10.1214/13-aop860.
[29] Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pages 21–30. IEEE, 2005. doi:10.1109/SFCS.2005.53.
[30] Elchanan Mossel, Ryan O’Donnell, Oded Regev, Jeffrey E Steif, and Benny Sudakov. Non-interactive correlation distillation, inhomogeneous markov chains, and the reverse bonami-beckner inequality. Israel Journal of Mathematics, 154(1):299–336, 2006.
[31] Elchanan Mossel, Krzysztof Oleszkiewicz, and Arnab Sen. On reverse hypercontractivity. Geometric and Functional Analysis, 23(3):1062–1097, 2013.
[32] Claus Müller. Spherical harmonics, volume 17. Springer, 2006.
[33] Edward Nelson. The free Markoff field. Journal of Functional Analysis, 12(2):211–227, 1973.
[34] Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 245–254, 2008. doi:10.1145/1374376.1374414.
[35] Ran Raz. Exponential separation of quantum and classical communication complexity. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 358–367, 1999. doi:10.1145/301250.301343.
[36] Oded Regev and Bo’az Klartag. Quantum one-way communication can be exponentially stronger than classical communication. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 31–40, 2011. doi:10.1145/1993636.1993642.
[37] Jean-Pierre Serre et al. Linear representations of finite groups, volume 42. Springer, 1977.
[38] Elias M Stein and Guido Weiss. Introduction to Fourier Analysis on Euclidean Spaces, volume 1. Princeton university press, 1971.
[39] Hans S Witsenhausen. Spherical sets without orthogonal point pairs. The American Mathematical Monthly, 81(10):1101–1102, 1974.
[40] Uri Zwick. Finding almost-satisfying assignments. In Proceedings of the 30th annual ACM symposium on Theory of computing, pages 551–560, 1998. doi:10.1145/276698.276869.

[bib.bib1] [1] Amit Agarwal, Moses Charikar, Konstantin Makarychev, and Yury Makarychev. $O(\sqrt{\log n})$ approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems. In Proceedings of the 37th ACM symposium on Theory of computing, pages 573–581, 2005.

[bib.bib2] [2] Sanjeev Arora, Béla Bollobás, László Lovász, and Iannis Tourlakis. Proving integrality gaps without knowing the linear program. Theory of Computing, 2:19–51, 2006. doi:10.4086/TOC.2006.V002A002.

[bib.bib3] [3] Sanjeev Arora and Rong Ge. New tools for graph coloring. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 1–12. Springer, 2011. doi:10.1007/978-3-642-22935-0_1.

[bib.bib4] [4] Dominique Bakry and Michel Émery. Diffusions hypercontractives. In Séminaire de Probabilités XIX 1983/84: Proceedings, pages 177–206. Springer, 2006.

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

[bib.bib6] [6] William Beckner. Sobolev inequalities, the Poisson semigroup, and analysis on the sphere Sn. Proceedings of the National Academy of Sciences, 89(11):4816–4819, 1992.

[bib.bib7] [7] Siavosh Benabbas, Hamed Hatami, and Avner Magen. An isoperimetric inequality for the Hamming cube with applications for integrality gaps in degree-bounded graphs. Unpublished, 1(1.2):1, 2012.

[bib.bib8] [8] Sergey Bobkov and Prasad Tetali. Modified log-sobolev inequalities, mixing and hypercontractivity. In Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, pages 287–296, 2003. doi:10.1145/780542.780586.

[bib.bib9] [9] Aline Bonami. Étude des coefficients de fourier des fonctions de lp(g). In Annales de l’institut Fourier, volume 20, pages 335–402, 1970.

[bib.bib10] [10] Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep. SDPs and robust satisfiability of promise CSP. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 609–622, 2023. doi:10.1145/3564246.3585180.

[bib.bib11] [11] Davi Castro-Silva, Fernando de Oliveira Filho, Lucas Slot, and Frank Vallentin. A recursive Lovász theta number for simplex-avoiding sets. Proceedings of the American Mathematical Society, 150(8):3307–3322, 2022.

[bib.bib12] [12] Moses Charikar. On semidefinite programming relaxations for graph coloring and vertex cover. In Proceedings of the 13th annual ACM-SIAM symposium on Discrete algorithms, pages 616–620, 2002. URL: http://dl.acm.org/citation.cfm?id=545381.545462.

[bib.bib13] [13] Evan DeCorte and Oleg Pikhurko. Spherical sets avoiding a prescribed set of angles. International Mathematics Research Notices, 2016(20):6095–6117, 2016.

[bib.bib14] [14] Peter Frankl and Vojtěch Rödl. Forbidden intersections. Transactions of the American Mathematical Society, 300(1):259–286, 1987.

[bib.bib15] [15] Peter Frankl and Richard M. Wilson. Intersection theorems with geometric consequences. Combinatorica, 1:357–368, 1981. doi:10.1007/BF02579457.

[bib.bib16] [16] Jean Gallier. Notes on spherical harmonics and linear representations of Lie groups. preprint, 2009.

[bib.bib17] [17] Konstantinos Georgiou, Avner Magen, Toniann Pitassi, and Iannis Tourlakis. Integrality gaps of 2-o(1) for vertex cover SDPs in the Lovász–Schrijver hierarchy. SIAM Journal on Computing, 39(8):3553–3570, 2010.

[bib.bib18] [18] Konstantinos Georgiou, Avner Magen, and Iannis Tourlakis. Vertex cover resists SDPs tightened by local hypermetric inequalities. In International Conference on Integer Programming and Combinatorial Optimization, pages 140–153. Springer, 2008. doi:10.1007/978-3-540-68891-4_10.

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

[bib.bib20] [20] Godfrey Harold Hardy, John Edensor Littlewood, and George Pólya. Inequalities. Cambridge university press, 1952.

[bib.bib21] [21] Gil Kalai and R Wilson. How large can a spherical set without two orthogonal vectors be? Combinatorics and more (weblog), 2009.

[bib.bib22] [22] David Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite programming. Journal of the ACM (JACM), 45(2):246–265, 1998. doi:10.1145/274787.274791.

[bib.bib23] [23] Manuel Kauers, Ryan O’Donnell, Li-Yang Tan, and Yuan Zhou. Hypercontractive inequalities via SOS, and the Frankl–Rödl graph. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1644–1658. SIAM, 2014. doi:10.1137/1.9781611973402.119.

[bib.bib24] [24] Subhash Khot. On the power of unique 2-prover 1-round games. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 767–775, 2002. doi:10.1145/509907.510017.

[bib.bib25] [25] Jon Kleinberg and Michel X Goemans. The Lovász theta function and a semidefinite programming relaxation of vertex cover. SIAM Journal on Discrete Mathematics, 11(2):196–204, 1998. doi:10.1137/S0895480195287541.

[bib.bib26] [26] Jiří Matoušek and Vojtěch Rödl. On Ramsey sets in spheres. Journal of Combinatorial Theory, Series A, 70(1):30–44, 1995.

[bib.bib27] [27] Ashley Montanaro. Some applications of hypercontractive inequalities in quantum information theory. Journal of Mathematical Physics, 53(12), 2012.

[bib.bib28] [28] Elchanan Mossel and Joe Neeman. Robust dimension free isoperimetry in Gaussian space. The Annals of Probability, 43(3), May 2015. doi:10.1214/13-aop860.

[bib.bib29] [29] Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS’05), pages 21–30. IEEE, 2005. doi:10.1109/SFCS.2005.53.

[bib.bib30] [30] Elchanan Mossel, Ryan O’Donnell, Oded Regev, Jeffrey E Steif, and Benny Sudakov. Non-interactive correlation distillation, inhomogeneous markov chains, and the reverse bonami-beckner inequality. Israel Journal of Mathematics, 154(1):299–336, 2006.

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

[bib.bib32] [32] Claus Müller. Spherical harmonics, volume 17. Springer, 2006.

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

[bib.bib34] [34] Prasad Raghavendra. Optimal algorithms and inapproximability results for every CSP? In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 245–254, 2008. doi:10.1145/1374376.1374414.

[bib.bib35] [35] Ran Raz. Exponential separation of quantum and classical communication complexity. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 358–367, 1999. doi:10.1145/301250.301343.

[bib.bib36] [36] Oded Regev and Bo’az Klartag. Quantum one-way communication can be exponentially stronger than classical communication. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 31–40, 2011. doi:10.1145/1993636.1993642.

[bib.bib37] [37] Jean-Pierre Serre et al. Linear representations of finite groups, volume 42. Springer, 1977.

[bib.bib38] [38] Elias M Stein and Guido Weiss. Introduction to Fourier Analysis on Euclidean Spaces, volume 1. Princeton university press, 1971.

[bib.bib39] [39] Hans S Witsenhausen. Spherical sets without orthogonal point pairs. The American Mathematical Monthly, 81(10):1101–1102, 1974.

[bib.bib40] [40] Uri Zwick. Finding almost-satisfying assignments. In Proceedings of the 30th annual ACM symposium on Theory of computing, pages 551–560, 1998. doi:10.1145/276698.276869.

Density Frankl–Rödl on the Sphere

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Theorem 1.

2 Eigen-decomposition via Spherical Harmonics

2.1 Spherical Harmonics

Lemma 2.

Proof.

2.2 Eigenvalue Estimates

Lemma 3.

Proof.

3 Reverse Hypercontractivity of 𝑨𝒕

3.1 Poisson Markov Semigroup

Definition 4.

Lemma 5.

Proof.

3.2 Reverse Hypercontractivity

Lemma 6 ([6], Theorem 1).

Lemma 7 ([31], Theorem 1.10).

Theorem 8.

Proof.

4 Density Sphere Avoidance

4.1 Inductive Configurations

4.2 Configuration with Pairwise Orthogonal Vectors

Lemma 9 ([36], Theorem 2.2).

Theorem 10.

Proof.

4.3 Main Results

Theorem 11 (Density Sphere Frankl-Rödl).

Proof.

Proposition 12.

Proof.

Proposition 13.

Proof.

Theorem 14.

Proof.

▶ Remark 15.

Corollary 16.

Corollary 17.

5 Open Problems

References

3 Reverse Hypercontractivity of $A_{t}$

$\blacktriangleright$ Remark 15.