Almost Optimal Pseudorandom Generators for Spherical Caps

Introduction

In this paper, we study the problem of constructing explicit pseudorandom generators (PRGs) for the class of halfspaces. Constructing PRGs for halfspaces (and more generally, polynomial threshold functions (PTFs)) has been intensively studied in the recent years . In addition to being a natural problem in derandomization, efficient PRGs for halfspaces have concrete applications such as derandomization of the Goemans Williamson algorithm for max cut and deterministic estimation of accuracy of halfspace classifiers in machine learning. Before proceeding, we define PRGs for halfspaces formallyHenceforth, for a multi-set $S$, $x\sim S$ denotes a uniformly random element of $S$.:

The parameter $r$ is called the seed-length of the PRG. $G$ is said to be explicit, if $G(y)$ can be computed in time polynomial in $n$.

Despite the long line of works, the seed-length for the best PRGs for halfspaces remains off by poly-logarithmic factors in $n$ for low error regimes (i.e. $\epsilon\approx 1/\mathsf{poly}(n)$). In this work, we resolve this question for spherical caps and give a construction with seed-length optimal up to a factor of $O(\log\log{(n)})$.

Our result extends to fool halfspaces with respect to Gaussian distributions as well.

As we describe next, our construction departs significantly from the previous work on constructing PRGs and introduces new ingredients which may be useful elsewhere. In particular, our construction uses an iterative dimension reduction approach as in the works of and makes use of explicit constructions of approximate orthogonal designs which are related to quantum analogues of classical $k$-wise independence and expanders . The analysis of the construction is motivated by the classical truncated moment problem from probability theory.

We use the above observation by iteratively projecting the vector $w$ into $\sqrt{n}$ dimensions, and then to $n^{1/4}$ dimensions and so forth until we work in a space of dimension $\Theta(\log n)$. Once we are down to vectors of dimension $\Theta(\log n)$, we use a direct approach to project down to a one-dimensional subspace. We will ensure that each one of these projections can be carried out with $O(\log(n/\epsilon))$ random bits and preserves the properties (including closeness in CDF distance) that we want. Thus, the total randomness used by our generator will be $O(\log{(n/\epsilon)}\cdot\log\log{(n)})$ random bits.

To make the above outline concrete let us introduce a central definitionThe use of $\sqrt{n}$ below is somewhat arbitrary and any $n^{c}$ for $c<1$ would suffice for us. We choose $\sqrt{n}$ to reduce the number of parameters.:

The number of random bits required to sample a $P$ distributed as $D$ is the seed-length of the PRP.

Roughly speaking, the above definition says that projecting any vector $w$ to $\sqrt{n}$ dimensions using our PRPs and then projecting to a truly random one-dimensional subspace is indistinguishable from using truly random projections.

Before describing our construction of PRPs let us note how they can be used for constructing PRGs fo spherical caps. As described above, we use our PRPs $O(\log\log n)$ times to project our vector down to $\Theta(\log^{2}{(n)})$ dimensions. At this point, we invoke the PRG of Impagliazzo et al. for space bounded machines (that has a seed-length of $O(\log{(d)}\cdot\log{(1/\epsilon)})$ for fooling halfspaces in $d$ dimensions with error $\epsilon$). To bound the error we just use a union bound to bound the errors of all projection steps and use Fact 1.1.

We next describe our construction of explicit PRPs.

2 Pseudorandom projections and the classical moment problem

There is a rich history behind these two questions (see for example, , ). Unfortunately, the results from the probability literature are quantitatively too weak for us: in most of these general results one needs to match $(1/\epsilon)^{\Omega(1)}$ moments (see and the discussion after Lemma 4.1) to get error $\epsilon$ which we cannot afford as we aim for $\epsilon$ which is polynomially small.

It is not hard to see that $Z$ has a smooth pdf and that $X^{\prime}$ has well-behaved moments (which can be controlled by hypercontractivity). We show that whenever the random variables $X^{\prime},Z$ satisfy these reasonable conditions, if, in addition, the first $k$ (even order) moments of $Y^{\prime}$ match the corresponding first $k$ moments of $X^{\prime}$, then, $X,Y$ are close within an error that is exponentially small in $k$ (the base of the exponent depending on the moments of $X^{\prime}$ and smoothness of $Z$). This result fits into the general principle where matching moments with some additional structure can be used to get much stronger quantitative guarantees on closeness of distributions; for example, show similar stronger quantitative bounds for various mixture models.

3 Orthogonal designs

We say that $\mathcal{D}$ is an explicit orthogonal design if there is a $\mathsf{poly}(n)$ time procedure to sample a matrix according to $\mathcal{D}$. The number of bits of randomness used to sample a matrix according to $\mathcal{D}$ is called its seed-length.

It is not too hard to show using the definitions and the arguments outlined from the previous section, that taking the matrix of first $\sqrt{n}$ rows of an approximate orthogonal $t$-design one gets a PRP with the same seed-length and error which is $\epsilon$. If we think of fixing the error $\epsilon$ (the dimension changes for us as we recurse), to get PRPs with an error of $\epsilon$ we need a $t$-design for $t\approx O\left(\log{(1/\epsilon)}/\log{(n)}\right)$.

In particular, to get PRPs with nearly-optimal seed-length, it suffices to get approximate $t$-designs with the near-optimal seed-length. The existence of finite orthogonal (or unitary) designs follows from the general results of Seymour and Zaslavsky . Harrow and Low observe that one can modify the argument of Ambainis et. al. to show that there exist $t$-designs with optimal (up to constants) parameters. Our application, however, requires efficient explicit constructions of these objects and we use the work of Brandao et al. who showed that a recent breakthrough result of Bourgain and Gamburd on expansion in Lie groups implies a construction of approximate orthogonal designs for $t\leq\Theta(n)$. This gives us orthogonal designs with optimal seed-length (up to constant factors).As some of the parameters important in our setting are not specified in and we work over real matrices as opposed to Hermitian ones in , we give an analysis of the construction of $t$-designs from the expansion results of Bourgain and Gamburd in Section 6.

4 Other related work

There is a vast body of work in probability on the generalized moment problems, beginning with Stieltjes with a first systematic study appearing in the work of Akhiezer under the name of classical moment problem. The ideas are extremely useful in applications in a number of different areas (see the recent textbook of Lasserre for a host of applications). For a survey of various approaches to the moment problem, see the text by Landau .

The question of distance (in various metrics) between probability distributions that have (approximately) matching low-degree moments is also well studied, see, for example , where the principle measure of distance used is the $\lambda$-metric. It is possible (see for example ) to convert these bounds into the more standard CDF (or Levy) distance bounds using known results .

The idea of using stepwise projections in order to reduce the amount of randomness required in each step was successfully employed in constructing almost optimal (with respect to randomness) explicit Johnson-Lindenstrauss (JL) embeddings by Kane et. al. . The analysis in is also based on matching the low-order moments of the lengths of the projections in each step. Their argument, though, is different and simpler as a JL family needs to satisfy only a tail bound condition and one can move from matching low-order moments to tail bounds under simple conditions on the random variables. In contrast, the connection between matching low order moments and CDF distance, as explained above, doesn’t hold in general and we crucially exploit the additional smoothening effect of mixing with an independent well behaved random variable to obtain the low errors we need.

Very recently, Gopalan, Kane and Meka gave a PRG for halfspaces whose coefficients are in $\{1,0,-1\}$ w.r.t the Boolean hypercube with a seed-length of $O((\log(n/\epsilon))\cdot\mathsf{poly}\log(\log(n/\epsilon)))$; this is incomparable to ours and their methods do not seem to apply in our setting. Their work also uses the iterative dimension reduction approach as in but the actual construction and its analysis are very different from ours.

Preliminaries

For any matrix of reals $M$, $M^{\dagger}$ denotes its transpose, $\|M\|$ its spectral norm (largest singular value) and $\|M\|_{2}=\sum_{i,j}M_{i,j}^{2}$, its Frobenius (or $2$) norm.

$\chi_{n}$ ($\chi$ random variable with $n$-degrees of freedom) denotes the positive real-valued random variable distributed as $Y=\|X\|_{2}$ where $X\sim\mathcal{N}(0,1)^{n}$.

Let $X$ and $Y$ be random variables on some domain $D$ with cumulative distribution functions (CDFs) $P_{1}$ and $P_{2}$ respectively. The CDF distance between $X$ and $Y$ is defined as $\mathsf{dcdf}(X,Y)=\sup_{z\in D}|P_{1}(z)-P_{2}(z)|.$

$\mathsf{SO}(n)$ denotes the group (under matrix multiplication) of all real orthogonal $n\times n$ matrices. There is a unique probability measure on $\mathsf{SO}(n)$ invariant under matrix multiplication (on the left or right) by matrices in $\mathsf{SO}(n)$ and is called as the Haar distribution (see Section B.1.1 for a brief overview).

PRGs for spherical caps from pseudorandom projections

We will prove the above result assuming we have constructions of appropriate PRPs as defined in Definition 1.2; we show how to construct PRPs in the subsequent sections.

When working on small dimensions ($m\sim\log{(1/\epsilon)}$), we will use the PRG for halfspaces based on the construction for small-space machines due to Nisan and Impagliazzo et. al. as observed in .

We are now ready to prove Theorem 2. As described in the introduction, the basic idea is to use the PRPs to iteratively reduce the dimension of the space and when the dimension is small enough, we can apply Fact 3.1.

Sample $P_{i}\sim\mathcal{D}_{i}$ for each $i<t$ and let $X_{t}=G_{INW}(y)$ for $y\sim\{0,1\}^{s}$, all random draws being independent of each other.

where the first $\approx$ follows from the inductive hypothesis (and the fact that $P_{j}$ is independent of $X_{j+1}$) and the second $\approx$ follows from the definition of PRP. Therefore, $\mathsf{dcdf}(\langle v,X_{j}\rangle,\langle v,Y_{j}\rangle)\leq(t-j+1)\epsilon^{\prime}$. The claim now follows by induction. ∎

Fix $\epsilon>0$. There exists a PRG for halfspaces w.r.t. the spherical Gaussian distribution with error at most $\epsilon$ and seed-length $s=O(\log n+\log\log{(1/\epsilon)}\cdot\log(1/\epsilon))$.

To prove the theorem we shall use the following simple fact.

For every $n\geq 1$, and $\delta>0$, there exists a random variable $\chi_{n,\delta}$ samplable efficiently with $O(\log n+\log(1/\delta))$ bits that approximates the random variable $\chi_{n}$:

Let $U,V_{1},V_{2}$ be independent random variables. Then, $\mathsf{dcdf}(U\cdot V_{1},U\cdot V_{2})\leq\mathsf{dcdf}(V_{1},V_{2})$.

The theorem follows from the following black box reduction and Theorem 2.

using Lemma 3.2. The theorem now follows. ∎

The objective of the following two sections is to prove Theorem 3.

From matching moments to CDF distance

In this section, we give quantitative bounds for the truncated moment problem in terms of the CDF distance: given random variables that have approximately equal low order moments, we derive strong upper bounds on the CDF distance between them. Our bounds are stronger (and crucial to obtaining near optimal seed-lengths for our generators) than those obtained from the general results in probability (see for e.g. , ) but require stronger analytic properties of the random variables. The results from this section will be used to analyze our construction of PRPs in the next section.

Random variables $X$ and $Y$ are said to be $(k,\epsilon)$-approximate moment matching if for every polynomial $p$ of degree at most $k$,

where $\|p\|_{1}$ is the sum of absolute values of the coefficients of $p$.

We are now ready to describe the main technical result of this section:

It is instructive to compare the error bounds above with the following estimate (due to Klebanov and Mkrtchyan) of CDF distance between random variables that have identical low order moments (the statement for approximately equal low order moment is similar but more cumbersome).

Let $F,f$ and $G,g$ be the CDFs and PDFs of real-valued random variables $X$ and $Y$. Suppose $f$ is bounded and that $X,Y$ have identical finite first $2m$ moments given by $\mu_{1},\mu_{2},\ldots,\mu_{2k}<\infty$ such that $\mu_{2}=1$. Let $\beta_{k}=\sum_{i=1}^{k}\mu_{2i}^{1/2i}$. Then, for a universal constant $C$,

We now move on to the proof of Lemma 4.1. We first collect a few simple facts from elementary analysis that will be useful in our proof of Lemma 4.1. We give proofs for these results in Section A of the Appendix. First we note a bound on the magnitude of derivatives of compositions of infinitely differentiable functions:

We will also need the following bound on the derivatives of $1/\sqrt{1+x}$ when $x>-1/2$:

Finally, we write the CDF of a product of two random random variables as a convenient expression:

Ideally, we’d like to show that for every $t$, $F(t/\sqrt{A})$ is well approximated by a low-degree polynomial (in $A$). We can then invoke the approximate moment matching property of the pair $X,Y$ to bound the difference in the expectations of $F(t/\sqrt{X})$ and $F(t/\sqrt{Y})$. This, however turns out to be too strong. Instead, we will show that $F$ is well approximated by low-degree polynomials whenever $X,Y$ do not deviate too far from their expectations. Towards this goal, we first set some notation:

$\hat{X}\stackrel{{\scriptstyle\textrm{def}}}{{=}}\frac{X-\mu^{2}}{\mu^{2}}$, $\hat{Y}\stackrel{{\scriptstyle\textrm{def}}}{{=}}\frac{Y-\mu^{2}}{\mu^{2}}$.

Now, $F(\frac{t}{\sqrt{X}})=F(\frac{t}{\mu\cdot\sqrt{(1+\hat{X})}})=g(\hat{X})$ and similarly, $F(\frac{t}{\sqrt{Y}})=F(\frac{t}{\mu\cdot\sqrt{(1+\hat{Y})}})=g(\hat{Y})$. Next, we describe the approximating polynomial for $g$ at , which will be obtained by truncating the Taylor expansion of $g$. To bound the error of approximation, we will need to bound the derivatives of $g$. This can be done whenever $x>-1/2$.

For every $x:|x|<1/2$, we now apply Fact 4.2 to functions $F(x)$ and $\frac{t}{\mu\sqrt{1+x}}$ and use Fact 4.3 to write:

We can now write the CDF distance between $\sqrt{X}\cdot Z$ and $\sqrt{Y}\cdot Z$ as:

We will bound each term in the right-side individually. We first use the fact that $X$ and $Y$ are $2k$ moment matching to bound the middle term:

Next, we bound the last two terms of (9). Using the bound on coefficients of $P_{k}$ and the upper bound of $1$ on the moments of $\hat{X}$:

By Markov’s inequality applied to $\hat{X}^{2k}$,

Thus, arguing as in the case of (9), we obtain:

When $t\geq 2\mu F^{-1}(1-\delta)$, it is easy to bound the CDF distance:

Thus, when $t\geq 2\mu F^{-1}(1-\delta)$,

On the other hand, when $t\leq 2\mu F^{-1}(1-\delta)$ (and $|x|\leq 1/2$) yields $\frac{t}{\mu\sqrt{1+x}}\in[2\sqrt{\frac{2}{3}},2\sqrt{2}]$ and thus: $\zeta(t)\leq\Delta_{k}$. We can now use (12) setting $\zeta(t)\leq\Delta_{k}$ to obtain the lemma. ∎

PRPs from approximate orthogonal designs

In this section, we show how to construct PRPs from approximate orthogonal designs and thus proving Theorem 3, which we first restate here.

For this, we shall assume the existence of a good explicit approximate orthogonal design, a proof of which is provided in the next section:

There exists an efficiently samplable $\epsilon$-approximate orthogonal $t$-design with seed-length $O(t\log{(n)}+\log{(1/\epsilon)})$.

Thus, if we show that a) $Z$ has an infinitely differentiable CDF with a reasonably bounded tail and derivatives b)$X$ has sufficiently slow growing moments and c) $X,Y$ are approximately moment matching, then we can apply the result from the previous section to show that the CDF distance between $\sqrt{X}\cdot Z$ and $\sqrt{Y}\cdot Z$ is small. In the following, we implement this plan and show that the $X,Y,Z$ defined above indeed satisfy the conditions required to complete the proof of Theorem 3. We first record the required properties of $Z$:

Sharp Tail: $F^{-1}(1-\delta)<1/10$ for $\delta=0.995^{\sqrt{m}}$.

Bounds on the Derivatives: For any $0<x<1:|f^{(q)}(x)|\leq c\cdot 10^{q}\cdot q!/|x|^{q}$, where $c=\frac{1}{\sqrt{\pi}}\cdot\frac{\Gamma(m/2)}{\Gamma(\frac{m-1}{2})}.$

We can now complete the proof of Theorem 3 using Lemma 4.1, Lemma 5.2 and Lemma 5.3.

We use Lemma 5.3 and Lemma 5.2 to obtain the estimates of all parameters required to apply Lemma 4.1 to $X$ and $Y$ above now. Let $F$ and $f$ be the CDF and PDF of $Z$ respectively. For $X$, $Y$ and $Z$ above, we have, $\Delta_{k}=k^{\Theta(k)}$ and $\mu_{k}/\mu^{2k}$, $\sqrt{\mu_{2k}}/\mu^{2k}\leq m^{-\Theta(k)}$. We set $\delta=0.995^{\sqrt{m}}$ and note that $F^{-1}(1-\delta)<1/10$. It is easy to verify that with this setting of the parameters, Lemma 4.1 gives an error bound of $\epsilon$ for appropriate setting of constants hidden in the $\Theta$s.

Next, we verify the seed-length used for the construction above: observe that the $k$ chosen above can be written as $\max\{\Theta(1),\Theta\left(\log{(1/\epsilon)}/\log{(m)}\right)\}$. Thus, the required seed-length is given by: $O(k\log{(m)}+\log{(1/\epsilon)})=O(\log{(m/\epsilon)})$ as promised. ∎

In the remaining part of this section, we prove Lemma 5.2 and Lemma 5.3.

To bound the derivatives of $f$, we will need the following standard theorem from complex analysis (due to Cauchy):

Before moving on to prove Lemma 5.3, we collect three facts useful in the proof:

We will need the following Marcinkiewicz-Zygmund inequality for moments and the standard gaussian concentration:

Let $S_{1},S_{2},\ldots,S_{q}$ be a sequence of independent, zero mean random variables. Then:

The following concentration bound is standard for Gaussian random vectors.

The first term is easy to estimate using Fact 5.2 (the same result can also be obtained from Bernstein-like inequalities for exponential random variables ). We have:

Constructing approximte orthogonal designs

In this section, we give a proof of a construction of approximate orthogonal designs, proving Lemma 5.1, based on a recent result of Bourgain and Gamburd . This also follows from the work Brandao et. al. (Page 17, Equation B2) except for some technicalities and concrete quantitative bounds which we need and work out next. We first provide some background before stating the result of (see the text by Bump for a detailed exposition).

Bourgain and Gamburd show that there exist Cayley graph expanders on $\mathsf{SU}(n)$. This also implies that there exist Cayley graph expanders with the same parameters on the group $\mathsf{SO}(n)$ (see Appendix B). In this section, we use the construction for $\mathsf{SO}(n)$ to obtain approximate orthogonal $t$-designs. We provide the necessary background and the deferred proofs from this section in Appendix B.

We briefly recall Cayley graphs on finite groups before working on $\mathsf{SO}(n)$. A Cayley graph on a group $G$ is defined by a set of generators (inverse closed) $g_{1},g_{2},\ldots g_{k}$. The vertex set is given by the elements of the group $G$ and there is an edge between $h,h^{\prime}$ iff $h=g_{i}h^{\prime}$ for some generator $g_{i}$.

One can define a Cayley graph on an infinite group similarly and in the following, we adopt the linear operator view.

Next, we define Hecke (or averaging) operators on $\mathcal{L}^{2}(\mathsf{SO}(n))$ that correspond to the finite dimensional normalized adjacency matrices described above. We say a set $Gen=\{g_{1},g_{2},\ldots,g_{k}\}$ is inverse closed if for every $g\in Gen$, $g^{-1}\in G$.

For some universal constant $k>0$, an averaging operator (also known as Hecke operator) with an inverse closed set of generators $g_{1},g_{2},\ldots,g_{k}\in G$ is a linear operator $\mathscr{T}:\mathcal{L}^{2}(G)\rightarrow\mathcal{L}^{2}(G)$ defined by $\mathscr{T}\stackrel{{\scriptstyle\textrm{def}}}{{=}}\frac{1}{k}\sum_{i=1}^{k}\mathscr{T}_{g_{i}}$.

It is easy to verify that a Hecke operator $\mathscr{T}$ on $\mathcal{L}^{2}(\mathsf{SO}(n))$ is bounded and compact and thus has a spectrum. Thus we can look at the gap between the first and second eigenvalues of $\mathscr{T}$ to talk of the expansion of the associated graph. This is encapsulated in the following definition:

We can now describe the (consequence of) result of Bourgain-Gamburd that we need in the language of Hecke operators:

For a universal constant $k>0$, there is an explicit Hecke operator $\mathscr{T}$ with $k$ generators on $\mathcal{L}^{2}(SO(n))$ with a spectral gap $1-\lambda$ bounded away from .

We now show how to obtain orthogonal $t$-designs using the above corollary. The idea itself is standard (see for example ) and we again use the intuition for finite graphs to motivate it: imagine running a random walk on the Cayley graph for a few ($\sim\log{(1/\epsilon)}$) steps. In the finite dimensional world, we expect that the resulting distribution on the vertices of the graph to be “close” to ($\sim\epsilon$) uniform.

In our setting, recall that our aim is to construct an object that fools the Haar (“uniform”) distribution on $\mathsf{SO}(n)$. If we start a “random walk” on a Cayley graph with generators $g_{1},g_{2},\ldots,g_{k}$ on $\mathsf{SO}(n)$ from some fixed point, we expect the resulting distribution to be close to “uniform” on $\mathsf{SO}(n)$ after a few steps. This argument can be formalized to yield $\epsilon$-approximate orthogonal $1$-designs, i.e. those that fool all linear functions in the entries of the matrices drawn according to the Haar distribution on $\mathsf{SO}(n)$. To fool higher degree polynomials, we first take the tensor powers of the generators of the “Cayley graph” on $\mathsf{SO}(n)$. The entries of $g_{i}^{\otimes t}$, the $t$-wise tensor (Kronecker) product of $g_{i}$ with itself, are all monomials of degree at most $t$ in the entries of $g_{i}$. Thus if we start with the Cayley graph with the generators given by the $t^{th}$ tensor powers of $g_{i}$, and argue similarly as above, we should hope to get approximate orthogonal $t$-designs.

has a spectrum and all its eigenvalues are at most $\lambda$.

where we use $(h\cdot g)^{\otimes t}=h^{\otimes t}\cdot g^{\otimes t}$ (which can be proven using induction and the mixed product property of the Kronecker product).

We can now use the result above to derive the main theorem of this section.

Let $g_{1},g_{2},\ldots,g_{k}$ be the generators ${\mathscr{T}}^{q}$ and let $\mathcal{D}$ be a uniform draw from $\{g_{1},g_{2},\ldots,g_{k}\}$. We will show that $\mathcal{D}$ is an $\epsilon$-approximate orthogonal $t$-design.

for some $q=t\log{(n)}+\log{(1/\epsilon)}$. Observe that it is enough to show this statement for monomials.

Thus, choosing $q=\Theta(t\log{(n)}+\log{(1/\epsilon)})$ is enough. Thus, $\mathcal{D}$ is an $\epsilon$-approximate orthogonal $t$-design.

Acknowledgment

We thank the anonymous reviewers for their suggestions on better presentation of the paper and pointing out the typos in a previous version.

References

Appendix A Deferred proofs

The result follows from using the following Faa di Bruno’s formula () for derivatives of composition of functions (whenever all the derivatives in the expression exist):

where the sum is over non-negative integers $b_{1},b_{2},\ldots,b_{m}$ such that $\sum_{i=1}^{m}ib_{i}=m$.

One can upper bound the expression on the RHS in absolute value by $k!$ for $x>-1/2$.

Let $U,V_{1},V_{2}$ be independent random variables. Then, $\mathsf{dcdf}(U\cdot V_{1},U\cdot V_{2})\leq\mathsf{dcdf}(V_{1},V_{2})$.

We can write the CDF of $U\cdot V_{1}$ as:

Similarly, the CDF of $U\cdot V_{2}$ can be written as :

Thus, $\mathsf{dcdf}(U\cdot V_{1},U\cdot V_{2})\leq\int_{0}^{\infty}\mathsf{dcdf}(V_{1},V_{2})f_{U}(u)du+\int_{-\infty}^{0}\mathsf{dcdf}(V_{1},V_{2})f_{U}(u)du=\mathsf{dcdf}(V_{1},V_{2}).$

A.2 Proofs from Section 5

Since the distribution of $x$ is invariant under any rotation of both the vectors, we can assume that $w$ has $1$ in its first coordinate and otherwise. Thus, $\langle w,v\rangle=v_{1}$. We can now calculate the CDF $F$ of $x$ by $F(x)=\Pr[v_{1}\leq x]$.

Let $t\in[-1,x]$. Then, $\{z\in L_{x}\mid z_{1}=t\}$ defines a sphere of radius $\sqrt{1-t^{2}}$ in $n-2$ dimensions. Using the Jacobian of the area measure $1/\sqrt{1-t^{2}}$, we can write $|L_{x}|$ as the integral:

Appendix B Hecke operators with spectral gap on 𝖲𝖮​(n)𝖲𝖮𝑛\mathsf{SO}(n)

In this section, we show that there exist Hecke operators on the group $\mathcal{L}^{2}(\mathsf{SO}(n))$ with a uniform spectral gap. This result follows almost immediately from the work of Bourgain and Gamburd , who show the existence of such operators on $\mathcal{L}^{2}(\mathsf{SU}(n))$. For completeness, we give a straightforward argument that uses only a few standard facts from the theory of Lie groups.

We state a few standard preliminary results (without proof) below. This material can be found in any standard textbook on Lie groups such as Bump .

B.1.2 Push forward Haar measure on coset space of closed subgroups

Let $f\in\mathcal{L}^{2}(G)$. Then, we have:

where we use $\dot{g}$ to refer to the canonical element of the coset from $G/H$ with $\dot{g}$ in it.

B.2 Existence of Hecke operators with spectral gap on 𝖲𝖮​(n)𝖲𝖮𝑛\mathsf{SO}(n)

We are now ready to describe the existence of Hecke operators with spectral gap on $\mathsf{SO}(n)$. Bourgain and Gamburd show the following:

For a universal constant $k>0$, there is a Hecke operator with a spectral gap $\mathscr{T}$ on $\mathcal{L}^{2}(\mathsf{SU}(n))$ with $k$ generators.

Using the standard machinery developed in the preliminaries above the same result can be shown to hold for $\mathsf{SO}(n)$:

For a universal constant $k>0$, there is a Hecke operator with a spectral gap $\mathscr{T}$ on $\mathcal{L}^{2}(\mathsf{SO}(n))$ with $k$ generators.