3 The Geometric Lemma

Lemma 21 Moments lemma

Lemma 3.2

Let $U$ and $U'$ be i.i.d. random variables taking values in a finite set $X$, and let $\sigma _1,\ldots ,\sigma _r \colon X \rightarrow \mathbb {R}^n$ be arbitrary functions. Then

\begin{equation*} \mathbb {E}\Big[ \big\langle \sigma _1(U),\sigma _1(U’) \big\rangle ^{\ell _1} \cdots \big\langle \sigma _r(U),\sigma _r(U’) \big\rangle ^{\ell _r} \Big] \ge 0. \end{equation*}

for every $(\ell _1,\dots ,\ell _r) \in \mathbb {Z}^r$ with $\ell _1,\dots ,\ell _r \ge 0$.

Proof ▶

To simplify the notation, let us write

\begin{equation*} \big\langle \sigma _1(U),\sigma _1(U’) \big\rangle ^{\ell _1} \cdots \big\langle \sigma _r(U), \sigma _r(U’) \big\rangle ^{\ell _r} = \prod _{i = 1}^\ell \big\langle \sigma _{a_i}(U), \sigma _{a_i}(U’) \big\rangle \end{equation*}

where $\ell = \ell _1 + \cdots + \ell _r$ and $(a_1,\dots ,a_\ell )$ is such that $\big| \big\{ i \in [\ell ] : a_i = j \big\} \big| = \ell _j$ for each $j \in [r]$. Now set

\begin{equation*} Z = \sigma _{a_1}(U) \otimes \sigma _{a_2}(U) \otimes \cdots \otimes \sigma _{a_\ell }(U) \quad \text{and} \quad Z’ = \sigma _{a_1}(U’) \otimes \sigma _{a_2}(U’) \otimes \cdots \otimes \sigma _{a_\ell }(U’), \end{equation*}

and note that

\begin{equation*} \big\langle Z, Z’ \big\rangle = \prod _{i = 1}^\ell \big\langle \sigma _{a_i}(U), \sigma _{a_i}(U’) \big\rangle , \end{equation*}

since $\langle u_1 \otimes \cdots \otimes u_r, v_1 \otimes \cdots \otimes v_r \rangle = \langle u_1, v_1 \rangle \cdots \langle v_r , u_r \rangle $ for any vectors $u_i,v_i \in \mathbb {R}^n$. Finally, note that $Z$ and $Z'$ are independent and identically distributed random vectors, and therefore

\begin{equation*} \mathbb {E}\big[ \langle Z, Z’ \rangle \big] = \mathbb {E}_{Z'} \big[ \mathbb {E}_Z \big[ \langle Z, Z’ \rangle \big] \big] = \mathbb {E}_{Z'} \big[ \big\langle \mathbb {E}[Z], Z’ \big\rangle \big] = \big\langle \mathbb {E}[Z], \mathbb {E}[Z’] \big\rangle \ge 0, \end{equation*}

as required, where the final inequality holds because $\mathbb {E}[Z] = \mathbb {E}[Z']$.

Remark 22

Let $g(x):= cosh(\sqrt{x})$ where $cosh(x)$ is defined by $cosh(\sqrt{x})=\overunderset {\infty }{n=0}{\sum }\frac{x^n}{(2n)!}$, then:

For all $x\geq 0$, we have $x \leq 2+cosh(\sqrt{x}) \leq 3e^{\sqrt{x}}$.
For all $x {\lt}0$, we have $-1 \leq cosh(\sqrt{x})\leq 1$. In particular, $2+cosh(x)\geq 1$ for all $x\in \mathbb {R}$.

Proof ▶

To prove (1), let $x\geq 0$ then:

\begin{equation*} 2+cosh(\sqrt{x}) = 3 + \overunderset {\infty }{n=1}{\sum }\frac{x^n}{(2n)!}\geq 3 + \frac{x}{2}+\frac{x^2}{24}. \end{equation*}

However,

\begin{equation*} 3+\frac{x}{2}+\frac{x^2}{24}\geq x \iff \frac{1}{24}(x^2-12x+72)\geq 0 \iff \frac{1}{24}((x-6)^2+36)\geq 0,s \end{equation*}

which concludes the lower bound in the first point. To conclude (1), we note the following for $x\geq 0$:

\begin{equation*} 3e^{\sqrt{x}}= 3\overunderset {\infty }{n=0}{\sum }\frac{x^{n/2}}{n!}\geq 3\overunderset {\infty }{n=0}{\sum }\frac{x^{n}}{(2n)!} \geq 2 + \overunderset {\infty }{n=0}{\sum }\frac{x^{n}}{(2n)!}= 2 + cosh(\sqrt{x}). \end{equation*}

To prove (2), note that for $x{\lt}0$,

\begin{equation*} cosh(\sqrt{x})= \overunderset {\infty }{n=0}{\sum }\frac{x^n}{(2n)!}= \overunderset {\infty }{n=0}{\sum }\frac{(-1)^n \sqrt{-x}^{2n}}{(2n)!}= cos(\sqrt{-x}). \end{equation*}

(2) then follows by noting that $cos(\sqrt{-x}) \in [-1,1]$ for all $x{\lt}0$.

Lemma 23 Special function upper bound

Lemma 3.3

Let $r \in \mathbb {N}$. If $x_i \ge - 3r$ for all $i \in [r]$, the function $f \colon \mathbb {R}^r \rightarrow \mathbb {R}$ defined in 1 satisfies

\begin{equation*} f(x_1,\dots ,x_r) \le 3^r r \exp \bigg( \displaystyle \sum _{i = 1}^r \sqrt{ x_i + 3r } \bigg) \end{equation*}

Proof ▶

\begin{equation*} f(x_1,\dots ,x_r)= \Bigl(\overunderset {r}{i=1}{\prod }(2+cosh\sqrt{x_i})\Bigr)\overunderset {r}{j=1}{\sum }\frac{x_j}{2+cosh \sqrt{x_j}} \overset {**}{\leq }r\Bigl(\overunderset {r}{i=1}{\prod } 3e^{\sqrt{x_i+3r}}\Bigr), \end{equation*}

To see (**), we write down upper bounds for all the factors of the LHS of (**). First, for every $i \in [r]$, such that $x_i \geq 0$, we note that $cosh(\sqrt{x_i} )\leq cosh(\sqrt{x_i+3r})$ (which follows since all the coefficients in the taylor expansion of $cosh(\sqrt{y}))$ are non-negative and thus $cosh(\sqrt{y})$ is non-decreasing on the positive reals. In turn, $2+cosh(\sqrt{x_i+3r}) \leq 3e^{\sqrt{x_i+3r}}$ by point 1 of the above remark. We conculde that if $x_i \geq 0$, $2 + cosh{\sqrt{x_i}} \leq 3 e^{\sqrt{x_i+3r}}$.

Next, we condiser the indices $i \in [r]$ such that $x_i{\lt}0$. In this case

\begin{equation*} 2+cosh(\sqrt{x_i})= 2 + cos(\sqrt{-x_i}) \leq 3 \leq 3 e^{\sqrt{x_i+3r}}, \end{equation*}

since $x_i \geq -3r$. It remains to show that $\frac{x_j}{2+cosh(\sqrt{x_j})} \leq 1$ for every $j \in [r]$. If $x_j\geq 0$ this follows directly from point (1) in the above remark. If $x_j{\lt}0$, note that the numerator of the fraction is negative while the denominator is a positive number between 1 and 3 by point(2) of the remark above.

Lemma 24 Special function lower bound

Lemma 3.3

Let $r \in \mathbb {N}$. If there exists an $i \in [r]$ with $x_i \le - 3r$, the function $f \colon \mathbb {R}^r \rightarrow \mathbb {R}$ defined in 1 satisfies

\begin{equation*} f(x_1,\dots ,x_r) \le -1 \end{equation*}

Proof ▶

Let $i \in [r]$ satisfy $x_i \leq -3r$. Note that if $x\geq 0$, then $\frac{x}{2+cosh(\sqrt{x})}\leq 1$ by point (1) of the above remark. Trivially, we have $\frac{x}{2+cosh{\sqrt{x}}}{\lt}0\leq 1$ for $x{\lt}0$ (note that $2+cosh(\sqrt{x})\geq 1$.) Therefore, we have

\begin{equation*} \underset {j \in [r], j \neq i}{\sum } \frac{x_j}{2+cosh(\sqrt{x_j})} \leq r-1. \end{equation*}

On the other hand, we know that $\frac{x_i}{2+cosh(\sqrt{x_i})} \leq \frac{x_i}{3}$ by part (2) in the remark above and therefore,

\begin{equation*} \overunderset {r}{j=1}{\sum }\frac{x_j}{2+cosh(\sqrt{x_j})}\leq \frac{x_i}{3}+r-1\leq -1. \end{equation*}

Finally we write

\begin{equation*} f(x_1,\dots ,x_r) = \Bigl(\overunderset {r}{i=1}{\prod }(2+cosh\sqrt{x_i})\Bigr)\overunderset {r}{j=1}{\sum }\frac{x_j}{2+cosh \sqrt{x_j}} \leq -1, \end{equation*}

since the sum in the last term is $\leq -1$ while the product is at least $1$ (each factor in the product is at least 1).

Remark 25

The key idea in the two lemmas above was to find an entire function, $2 + \cosh \sqrt{x}$, which $(a)$ has a Taylor expansion at $x = 0$ with non-negative coefficients; $(b)$ is bounded on the negative real axis; and $(c)$ does not grow too quickly on the positive axis. The Phragmén–Lindelöf theorem implies that functions satisfying $(a)$ and $(b)$ must grow at least as fast as $\exp \big( \Omega (\sqrt{x}) \big)$ on the positive real axis. Thus the bound on the growth of $f$ given by the lemma is essentially best possible for constructions of this type.

Lemma 26 Geometric lemma

Lemma 3.1

Let $r, n\in \mathbb {N}$. Set $\beta = 3^{-4r}$ and $C = 4r^{3/2}$. Let $U$ and $U'$ be i.i.d. random variables taking values in a finite set $X$, and let $\sigma _1,\ldots ,\sigma _r \colon X \rightarrow \mathbb {R}^n$ be arbitrary functions. There exists $\lambda \ge -1$ and $i\in [r]$ such that

\begin{equation*} \mathbb {P}\Big( \big\langle \sigma _i(U),\sigma _i(U’) \big\rangle \ge \lambda \, \text{ and } \, \big\langle \sigma _j(U), \sigma _j(U’) \big\rangle \ge -1 \, \text{ for all } \, j \ne i \Big) \ge \beta e^{- C\sqrt{\lambda + 1}}. \end{equation*}

Proof ▶

For each $i \in [r]$, define $Z_i = 3r\big\langle \sigma _i(U),\sigma _i(U') \big\rangle $, and let $E$ be the event that $Z_i \ge -3r$ for every $i \in [r]$.

Consider two cases:

First assume $\mathbb {P}(E) \ge \beta $. Note that

\begin{equation*} \mathbb {P}(E) = \mathbb {P}\Big( Z_i \ge - 3r \, \text{ for all } \, i \in [r] \Big), \end{equation*}

so with $\lambda = -1$,

\begin{align*} \beta e^{-C\times 0} & = \beta \\ & \le \mathbb {P}(E)\\ & = \mathbb {P}\Big(3r\big\langle \sigma _i(U),\sigma _i(U’) \big\rangle \ge -3r \text{ for all }i\Big)\\ & = \mathbb {P}\Big( \big\langle \sigma _i(U),\sigma _i(U’) \big\rangle \ge \lambda \, \text{ and } \, \big\langle \sigma _j(U), \sigma _j(U’) \big\rangle \ge -1 \, \text{ for all } \, j \ne i \Big) \end{align*}

hence the claimed inequality holds.

Now, assume $\mathbb {P}(E) \le \beta $ and assume for the sake of a contradiction that for all $\lambda \geq -1$,

\begin{align} \label{eq:max:big:and:E:no} \mathbb {P}\left(E \cap \left( \bigcup _{i \in [r]} \left\{ \big\langle \sigma _i(U),\sigma _i(U’) \big\rangle \ge \lambda \right\} \right)\right) {\lt} \beta r e^{-C\sqrt{\lambda + 1}}. \end{align}

Observe that, since $x \le 2 + \cosh \sqrt{x}$ (Theorem 14) and using Theorem 21 and linearity of expectation,

\[ \mathbb {E}\big[ f\big( Z_1,\ldots ,Z_r \big) \big] \ge 0 \]

We hence have

\begin{align*} 0 & \le \mathbb {E}\big[ f\big( Z_1,\ldots ,Z_r \big) \big]\\ & = \mathbb {E}\big[ f\big( Z_1,\ldots ,Z_r \big) \mathbf{1}_E \big] + \mathbb {E}\big[ f\big( Z_1,\ldots ,Z_r \big) \mathbf{1}_{E^c} \big]\\ & \le \mathbb {E}\left[ 3^r r \exp \bigg( \displaystyle \sum _{i = 1}^r \sqrt{ Z_i + 3r } \bigg) \mathbf{1}_E \right] + \mathbb {E}\big[-1 \cdot \mathbf{1}_{E^c} \big] \end{align*}

where we use Theorem 23 to bound the case for $E$, and Theorem 24 for $E^c$. It follows that

\begin{equation} \label{eq:eventE:inequality} 1 - \mathbb {P}(E) \le 3^r r \cdot \mathbb {E}\bigg[ \exp \bigg( \sum _{i = 1}^r \sqrt{ Z_i + 3r } \bigg) \mathbf{1}_E \bigg]. \end{equation}

Let $M = \max \big\{ \big\langle \sigma _i(U),\sigma _i(U') \big\rangle : i \in [r] \big\} $. For any constant $c \le C - 1$, we have

\begin{align} \exp (c\sqrt{M+1})\hbox{$1\mkern -6.5mu1$}_E& = \hbox{$1\mkern -6.5mu1$}_E \Bigl(e^{c\sqrt{1-1}}+ \int _{-1}^M \frac{ce^{c\sqrt{\lambda +1}}}{2\sqrt{\lambda +1}} d\lambda \Bigr)\\ & = \hbox{$1\mkern -6.5mu1$}_E+ \int _{-1}^{\infty } \hbox{$1\mkern -6.5mu1$}_{E,\{ M\geq \lambda \} }\frac{ce^{c\sqrt{\lambda +1}}}{2\sqrt{\lambda +1}} d\lambda . \end{align}

Given any $c \leq C-1$ we take the expected value of both sides of the previous equation and apply Tonelli’s theorem to obtain:

\begin{align*} \mathbb {E}\Big[ \exp \big( c \sqrt{M + 1} \big) \mathbf{1}_E \Big] & \\ & \le \, \mathbb {P}(E) + \int _{-1}^\infty \mathbb {P}\Big( \big\{ M \ge \lambda \big\} \cap E \Big) \cdot \frac{c}{2\sqrt{\lambda + 1}} \cdot e^{c \sqrt{\lambda + 1}} \, \mathrm{d}\lambda \\ & \le \, \beta + \int _{-1}^\infty \frac{\beta r c}{2\sqrt{\lambda + 1}} \cdot e^{- C\sqrt{\lambda + 1}+c\sqrt{\lambda +1}} \, \mathrm{d}\lambda \\ & \le \, \beta + \beta r \int _{-1}^\infty \frac{c}{2\sqrt{\lambda + 1}} \cdot e^{- \sqrt{\lambda + 1}} \, \mathrm{d}\lambda \\ & \le \, \beta (cr + 1), \end{align*}

where in the second inequality we used (Equation 2) and $\mathbb {P}(E) \le \beta $; in the third we used $c \le C - 1$; and in the last inequality we used the fact that $\int _0^\infty \frac{1}{2\sqrt{x}} e^{-\sqrt{x}} \, \mathrm{d}x = 1$. Note that the second and third inequalities rely on the non-negativity of the integrand. In particular, applying this with $c = \sqrt{3}r^{3/2}$, and recalling that $C = 4r^{3/2} \ge c + 1$ and $\beta = 3^{-4r}$, it follows that

\begin{align} 1 - \mathbb {P}(E) & \le 3^r r \cdot \mathbb {E}\bigg[ \exp \bigg( \sum _{i = 1}^r \sqrt{ Z_i + 3r } \bigg) \mathbf{1}_E \bigg]\\ & \le 3^r r \cdot \mathbb {E}\bigg[ \exp \bigg( r \cdot \max _{i \in [r]} \sqrt{ Z_i + 3r } \bigg) \mathbf{1}_E \bigg]\\ & = 3^r r \cdot \mathbb {E}\bigg[ \exp \bigg( r \cdot \sqrt{ 3r} \cdot \sqrt{ (M + 1) } \bigg) \mathbf{1}_E \bigg]\\ & \le 3^r r \cdot \beta (r^{2}\sqrt{3r} + 1) \le 1/3, \end{align}

which contradicts our assumption that $\mathbb {P}(E) \le \beta $.

Hence, there exists $\lambda \ge -1$ such that

\begin{align} \label{eq:max:big:and:E} \beta r e^{-C\sqrt{\lambda + 1}} & \le \mathbb {P}\left(E \cap \left( \bigcup _{i \in [r]} \left\{ \big\langle \sigma _i(U),\sigma _i(U’) \big\rangle \ge \lambda \right\} \right) \right) \\ & \le \sum _{i \in [r]} \mathbb {P}\left(E \cap \left\{ \big\langle \sigma _i(U),\sigma _i(U’) \big\rangle \ge \lambda \right\} \right)\\ & \le r \cdot \max _{i \in [r]} \mathbb {P}\left(E \cap \left\{ \big\langle \sigma _i(U),\sigma _i(U’) \big\rangle \ge \lambda \right\} \right) , \end{align}

and therefore there exists an $i \in [r]$ as required.