% ----------------------------------------------------------------
% AMS-LaTeX Paper ************************************************
% **** -----------------------------------------------------------
\documentclass[finalversion]{FPSAC2020}
\articlenumber{9}
\addbibresource{fpsac.bib}

%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\crefname{thm}{Theorem}{Theorems}



%% define your title in the usual way
\title[Random words in compact Lie groups]{On the distribution of random words in a compact Lie group}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[Hariharan Narayanan]{Hariharan Narayanan\thanks{\href{mailto:hariharan.narayanan@tifr.res.in}{hariharan.narayanan@tifr.res.in}.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}School of Technology and Computer Science \\Tata Institute of Fundamental Research, Mumbai, India}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)

\abstract{
Let $G$ be a compact Lie group. Suppose $g_1, \dots, g_k$ are chosen independently from the Haar measure on $G$. Let  $\mathcal A = \cup_{i \in [k]} \mathcal A_i$, where, $\mathcal A_i :=  \{g_i\} \cup \{g_i^{-1}\}$.  Let $\mu_{\mathcal A}^\ell$ be the uniform measure over all words of length $\ell$ whose alphabets belong to $\mathcal A$. We give probabilistic bounds on the nearness of a heat kernel smoothening of $\mu_{\mathcal A}^\ell$ to a constant function on $G$ in ${\mathcal L}^2(G)$. We also give probabilistic bounds on the maximum distance of a point in $G$ to the support of $\mu_{\mathcal A}^\ell$.
}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Random generation, Lie groups}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
%\usepackage[backend=bibtex]{biblatex}
%\documentclass{amsart}

\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amstext}
\usepackage{amsmath}
\usepackage{amsthm,verbatim}
\usepackage{xspace}
\usepackage{graphicx}
\usepackage{algorithm}
% ----------------------------------------------------------------
\vfuzz2pt % Don't report over-full v-boxes if over-edge is small
\hfuzz2pt % Don't report over-full h-boxes if over-edge is small
% THEOREMS -------------------------------------------------------
\newtheorem{cor}[thm]{Corollary}
\newtheorem{prop}[thm]{Proposition}

\newcommand{\abs}[1]{\left\vert#1\right\vert}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\Real}{\mathbb R}
\newcommand{\eps}{\varepsilon}
\newcommand{\To}{\longrightarrow}
\newcommand{\BX}{\mathbf{B}(X)}
\renewcommand{\a}{\alpha}
%\newcommand{\delta}{\delta}
% ----------------------------------------------------------------
\begin{document}


%\thanks{}%
%\subjclass{}%
%\keywords{}%

%\date{}%
%\dedicatory{}%
%\commby{}%
\include{Random_nets_macros}
% ----------------------------------------------------------------

\maketitle
% ----------------------------------------------------------------
\section{Introduction}
Let $G$ be a compact $n-$dimensional Lie group endowed with a left-invariant Riemannian distance function $d$.  Thus \beqs \forall g, x, y \in G,\,d(x, y) = d(gx, gy).\eeqs 
We will denote by $C_G$ a constant depending on  $(G, d)$ that is greater than $1$. Suppose $g_1, \dots, g_k$ are chosen independently from the Haar measure on $G$. Let  $\A = \cup_{i \in [k]} \A_i$, where, $\A_i :=  \{g_i\} \cup \{g_i^{-1}\}$. 
Let the Heat kernel at $x$  corresponding to Brownian motion on $G$ with respect to the distance function $d$ started at the origin $o \in G$ for time $t$ be $H_t(x)$.  Let $\mu_{\A}^\ell$ be the uniform measure over all words of length $\ell$ whose alphabets belong to $\A$. 
\begin{comment}
The overall strategy employed here is similar to that of Landau and Russell in \cite{LR}, which reproves with better constants, the result of Alon and Roichman \cite{AR} that random Cayley graphs are expanders. However, in our context of compact Lie groups, the analysis requires additional ingredients, due to the fact that $\LL^2(G)$ is infinite dimensional. We deal with this difficulty by  restricting  our attention to certain finite dimensional subspaces of $\LL^2(G)$. These subspaces are defined as the spans of eigenfunctions of the Laplacian corresponding to eigenvalues that are less than certain finite values.
\end{comment}

 For the case 
$G = SU_n$, Bourgain and Gamburd proved \cite{BG2} the existence of a spectral gap provided the entries of the generators are algebraic and the subgroup they generate is dense in $G$. There is a long line of work that this relates to, touching upon approximate subgroups and pseudorandomness, for which we direct the reader to the references in \cite{BG2}.
The question of a spectral gap when $G$ is $SU_2$ for random generators of the kind we consider was reiterated by Bourgain and Gamburd in \cite{BG1}, being first raised by Lubotzky, Philips and Sarnak \cite{Lub} in 1987 and is still open. In the setting of $SU_2$, our results can be viewed as addressing a quantitative version of a weak variant of this question.

Suppose $F_1, F_2, \dots$ are eigenspaces of the Laplacian $L_G$ on $G$ corresponding to eigenvalues $0 = \la_0 < \la_1 <  \la_2 < \dots$. Let $f_i^1, \dots, f_i^j, \dots$ be an orthonormal basis for $F_i$, for each $i \in \N$. The Laplacian $L_G$ is a second order differential operator, which for all twice differentiable functions $f$, satisfies $H_t \ast f = e^{tL_G} f.$ 
$G$ acts on  functions in $\LL^2(G)$ via $T_g$, the translation operator,
$$T_g f (x) = f(g^{-1} x).$$
Thus each $F_i$ is a representation of $G$, though not necessarily an irreducible representation.

As stated in the introduction, let the Heat kernel at $x$  corresponding to Brownian motion on $G$ with respect to the distance function $d$ started at the origin $o \in G$ for time $t$ be $H_t(x)$. When we wish to change the starting point for the diffusion, we will denote by $H(x, y, t)$ the probability density of Brownian motion started at $x$ at time zero ending at $y$ at time $t$.
Our first result, \cref{thm:main:1} relates to equidistribution and gives a lower bound on the probability that  $\|\mu_{\A}^\ell*H_t - \frac{\one}{\vol G}\|_{\LL^2(G)}$ is less than a specified quantity $2\eta$. Our second result, \cref{thm:11} provides conditions under which the set of all elements of $G$ which can be expressed as words of length less or equal to $\ell$ with alphabets in $\A$, form a $2r-$net of $G$ with probability at least $1-\delta$. For constant $\delta$, both $k$ and $\ell$ can be chosen to be less than $C n \log (1/r)$, where $C$ is a universal constant. 

Our main result on equidistribution, \cref{thm:main:1} immediately implies the following.
\begin{thm}Let $(G, d)$ be a tuple consisting of an $n$ dimensional compact Lie group $G$ and a Riemannian distance function $d$ on it under which the Riemannian volume of $G$ is $1$. There exists a constant $C_G$ depending only on on $G$ and the distance function $d$ on it such that the following is true. 
Let $ \eta := 2^{- \ell} t^{- \frac{n}{4}}$ be sufficiently small. Let $\delta:=  (C_G/\eta)\exp\left(-\frac{k}{16\ln 2}\right).$ Then, denoting by $\A^\ell$, the set of all ordered $\ell-$tuples with elements in $\A$, 

\beq \lab{eq:eta1.0} \p\left[ \left\|{1_G}- \frac{1}{(2k)^\ell} {\sum\limits_{g \in \A^\ell}   {H}_{t} \circ T_g} \right\|_{\LL^2(G)} \leq 2\eta  \right] \geq 1 - \delta.\eeq
\end{thm}

Our main result on nets, \cref{thm:11} immediately implies the following.

\begin{thm} \lab{thm:11} Let $\delta \in (0, 1]$ be a real number.  Let $\epsilon$ be a  positive real number less than a sufficiently small constant depending only on $G$.
Choose $$k \geq 12 (n\ln \frac{1}{\eps} +  \ln \frac{1}{\delta})$$ i.i.d random points $\{g_1, \dots, g_k\}$ from the Haar measure on $G$ and let $$\A = \{g_1, g_1^{-1}, \dots, g_k, g_k^{-1}\}.$$ Let $\ell =  n\log_2(\frac{1}{\eps})$. Then, with probability at least $1 - \delta$,  $\A^\ell$ is an $\eps-$net of $G$. 
\end{thm}

\begin{comment}
 Finally, the lower bounds that we prove on $k$ and $\ell$ are encapsulated in \cref{thm:13.5,thm:14}.
{\it Proposition}~\ref{thm:13.5}:
Let $G$ be a compact Lie group with a left invariant Riemannian distance function that results in $G$ having a unit Riemannian volume. 
Suppose that for some  constant $C_G$ depending only the the group $G$ and its distance function, 
$k \leq C_G \ln \frac{1}{\eps}$. Choose $k$ i.i.d random points $\{g_1, \dots, g_k\}$ from the Haar measure on $G$ and let $$\A = \{g_1, g_1^{-1}, \dots, g_k, g_k^{-1}\}.$$ Suppose $\A^\ell$ is an $\eps-$net of $G$. Then, $$\ell \geq  \frac{n\ln \left(\frac{1}{4\eps}\right)}{\ln(2C_G\ln \frac{1}{\eps})}.$$

{\it Proposition}~\ref{thm:14}:
Let $G = \R^n/\Z^n$ be the standard $n-$dimensional torus. Let $\eps$ be a positive real, bounded above by a  sufficiently small constant depending on $n$. Let $\ell \leq k \leq 2\ell.$ Choose $k$ i.i.d random points $\{g_1, \dots, g_k\}$ from the Haar measure on $G$ and let $$\A = \{g_1, g_1^{-1}, \dots, g_k, g_k^{-1}\}.$$  Suppose $\A^\ell$ is an $\eps-$net of $G$. Then, $k \geq \frac{n}{2} \ln \frac{1}{\eps},$ and $\ell \geq  \frac{n}{4} \ln \frac{1}{\eps}.$
\end{comment}

\section{Analysis on a compact Lie group}

The following is a theorem of Minakshisundaram and Pleijel \cite{Minakshisundaram1, Minakshisundaram}.
\begin{thm}\lab{Minak}
For each $x \in G$  there is an asymptotic expansion
$$ H( x, x, t) \sim t^{-n/2}(a_0(x) + a_1(x)t + a_2(x)t^2 + \dots),$$ $t \ra 0$.
The $a_j$ are smooth functions on $G$.
\end{thm}
Since $G$ is equipped with a left invariant distance function, the $a_j(x)$ are constant functions.
We will use the following theorem of Grigoryan from \cite{Grigor}, where it appears as Theorem 1.1.

\begin{thm}\lab{thm:grig}
Assume that for some points $x, y \in M$ and for all $t \in (0, T) $, 
$$p_t(x, x) \leq \frac{C_1}{\gamma_1(t)},$$ and $$p_t(y, y) \leq \frac{C_1}{\gamma_2(t)},$$ where $\gamma_1$ and $\gamma_2$ are increasing positive functions on $\mathbb{R}_+$ both satisfying
\beq \frac{\gamma_i(at)}{\gamma_i(t)} \leq A \frac{\gamma_i(as)}{\gamma_i(s)}\eeq for all $0 < t \leq s < T,$ for some constants $a, A > 1.$ Then for any $C > 4$ and all $t \in (0, T),$ 
\beq p_t(x, y) \leq \frac{C_2}{\sqrt{\gamma_1(\epsilon t)\gamma_2(\epsilon t)}}\exp\left(- \frac{d^2(x, y)}{Ct}\right)\eeq
for some $\epsilon = \epsilon(a, C) > 0.$

\end{thm}

It follows from \cref{Minak} that for some sufficiently small time $T>0$, we can choose $\gamma_1(t) = \gamma_2(t) = (\frac{1}2)t^{n/2}$ for $ t \in (0, T)$ in \cref{thm:grig}.

This gives us the following corollary.

\begin{cor}\lab{thm:CLY}
For any constant $C > 4$, there exists $T>0$ and $C_1$ depending on $G$ and  $C$ so that for all $t \in (0, T)$
 $$H(x, y, t) \leq C_1t^{-n/2} \exp (-\frac{r^2}{Ct})$$
 where $n$ is the dimension of $G$ and $r$ is the distance between $x$ and $y$.
\end{cor}


\begin{lem}\label{lem:1}Let $\eta > 0$.
We  take $ \eps  \sqrt{ 5\ln \frac{1}{\eta \eps^n}} = r$. 
If we choose $t = \eps^2$, then, 

 for all $y$ such that $$d(x, y) > r,$$ we have
$$H(x, y, t) < C_G{\eta}.$$
\end{lem}
\begin{proof}
 In \cref{thm:CLY},  we may set $C = 5$ and  $T = 1$ and ignore the dependence in $x$ since the distance function is left invariant.  For all $ t \leq \eps^2$ and all $y$ such that $$d(x, y) >  r,$$
\beq H(x, y, t) & < &  C_1 \eps^{-n}  ( \exp(- \ln \frac{1}{\eta \eps^n})) \\
& < &                 C_1 {\eta}.\eeq


\end{proof}


By Weyl's law for the eigenvalues of the Laplacian on a Riemannian manifold as proven by Duistermaat and Guillimin \cite{DG}, we have the following.
\begin{thm}\label{thm:weyl}
$$\lim_{\la \ra \infty} \frac{\la^{n/2}}{ \sum_{\la_i \leq \la}\dim F_i} = \frac{\vol(B_n)\vol(G)}{(2\pi)^n} =: C_2,$$ where $C_2$ is a constant depending only on volume and dimension $n$ of the Lie group.
\end{thm}
This has the following corollary, which is improved upon by \cref{thm:g} below.
\begin{cor}\label{cor3}
$$\sup_{i \geq 1} \frac{\dim F_i}{ \la_i^{n/2}} = C_3,$$ where $C_3$ is a finite constant depending only on the Lie group and its distance function.
\end{cor}



The following theorem is due to Donnelly (Theorem 1.2, \cite{donnelly}). 

\begin{thm}\lab{thm:g} 
Let $M$ be a compact $n-$dimensional Riemannian manifold and $\Delta$ its Laplacian acting on functions. Suppose that the injectivity radius of $\MM$ is bounded below by $c_4$ and that the absolute value of the sectional curvature is bounded above by $c_5$. If $\Delta \phi = - \la \phi$ and $\la \neq 0$, then $\|\phi\|_\infty \leq c_2 \la^{\frac{(n-1)}{4}}\|\phi\|_2.$ The constant $c_2$ depends only upon $c_4, c_5,$ and the dimension $n$ of $\MM$. Moreover the multiplicity $m_\la \leq c_3 \la^{\frac{(n-1)}{2}}$ where $c_3$ depends only on $c_2$ and an upper bound for the volume of $\MM$.
\end{thm}
H\"{o}rmander \cite{Hormander} proved this result earlier without specifying which geometric parameters the constants  depended upon. 
%We also use the following result of Yunqian Shi and Bin Xu \cite{SX}.
Then, by the Fourier expansion of the heat kernel into eigenfunctions of the Laplacian,
$$H_t = \sum_{\la_i \geq 0}\sum_{j} a_{ij}  f_{ij} .$$
where $a_{ij} = e^{- \la_i t} f_{ij}(0) \leq  e^{- \la_i t} (c_2 \la_i^{\frac{n-1}{4}}),$ where the $f_{ij}$  for $ j \in [1, \dim F_i] \cap \N $, form an orthonormal basis of $F_i$.  
Let $$\tilde{H}_{t, M}(y) = \sum_{0 < \la_i \leq M}\sum_{j} a_{ij} f_{ij},$$ and
 $${H}_{t, M}(y) = \sum_{0 \leq \la_i \leq M}\sum_{j} a_{ij} f_{ij},$$
\begin{lem}\lab{lem:6} For any $M > 0$, \beq \|\tilde{H}_{t, M}\|_{\LL^2} <  C_G t^{-n/4}\eeq
\end{lem}
\begin{proof}
We note that \beq \|\tilde{H}_{t, M}\|_{\LL^2} \leq \|H_t\|_{\LL^2},\eeq because $\tilde{H}_{t, M}$ is the image of $H_t$ under a projection (with respect to $\LL^2$) onto a  subspace spanned by the eigenfunctions of the Laplacian corresponding to eigenvalues in the range $(0, M]$. Thus it suffices to bound $\|H_t\|_{\LL^2}$ from above in the appropriate manner. Choosing $\eta = 1 $ in \cref{lem:1}, we see that if
we  take $ \eps  \sqrt{ 5 \ln (\eps^{-n})} = r$ and  $t = \eps^2$, then, 

 for all $y$ such that $$d(x, y) > r,$$ we have
$$H(x, y, t) < C_G.$$ Let $\mu_n$ denote the Lebesgue measure on $\R^n$ and $\mu$ the volume measure on $G$. We next need an upper bound on $\int_{B(o,r)} H_t(y)^2 \mu(dy).$ Note that when $\eps$ is sufficiently small, $B(o, r)$ is almost isometric via the exponential map to a Euclidean ball of radius $r$ in $\R^n$. 
Further, it is known that \beq \lab{eq:2.7} \sqrt{\det g_{ij}(\exp_x(\alpha v))} = 1 - \frac{1}{6} Ric^g(v, v) \alpha^2 + o(\alpha^2), \eeq
where $Ric$ denotes the Ricci tensor, and $\exp_x$, the exponential map at $x$. Since $Ric^g(v, v)$ is bounded above by a finite real number for $v$ on the unit sphere, 

 \beqs \int_{B(o,r)} H_t(y)^2 \mu(dy) & \leq &  C_G\left( \int_{\R^n} \eps^{-n}  ( \exp(-  \frac{|y|^2}{5t} ))\mu_n(dy)\right)\\
& \leq & C_G \left( \int_{\R} \eps^{-1}  ( \exp(-  \frac{|y|^2}{5t} ))\mu_1(dy)\right)^n\\
& \leq & C_G \eps^{-n}. \eeqs
Therefore \beq \|H_t\|_{\LL^2} \leq C_G \eps^{-n/2}. \eeq
\end{proof}


\begin{lem}\lab{lem:7} For $M = 2^{\frac{2k_0}{n}}$ where $$k_0 \geq \max\left(\log_2 \frac{ 1 }{\eta},  C_G +  (1 + o(1))\frac{n}{2} \log_2 \frac{1}{t}\right),$$
 \beq\lab{eq:byW}   \|H_t - H_{t, M}\|_{\LL^2}  \leq {\eta}.\eeq \end{lem}
\begin{proof}
It follows by the $\LL^2-$convergence of Fourier series that
\beq \|H_t - H_{t, M}\|_{\LL^2} \leq \sum_{\la_i \geq M} \dim(F_i)e^{- \la_i t} (c_2 \la_i^{\frac{n-1}{4}}) .\eeq


By Weyl's law (\cref{thm:weyl}), 
$$\lim_{\la \ra \infty} \frac{\la^{n/2}}{ \sum_{\la < \la_i \leq 2^{\frac{2}{n}}\la}\dim F_i} = \frac{\vol(B_n)\vol(G)}{(2\pi)^n} =: C_2^{-1}.$$

Let, for $k \in \N$, \beq I_k = \left(2^{\frac{2k}{n}}, 2^{\frac{2k+2}{n}}\right]. \eeq Now, for $k_0 > C_G$, 
\beq  \sum_{\la_i > 2^{\frac{2k_0}{n}}} \dim(F_i)e^{- \la_i t} (c_2 \lambda_i^{\frac{n-1}{4}}) & \leq & 
\sum_{k \geq k_0} \left(\sum_{ \la_i \in I_k} \dim(F_i) \right) \sup_{\la_i \in I_k} \left(\frac{c_2 \la_i^{ \frac{n-1}{4}}}{e^{\la_i t}}\right)\\
& \leq & C_2 \sum_{k \geq k_0}  2^{k+1} \sup_{\la_i \in I_k} \left(\frac{c_2 \la_i^{ \frac{n-1}{4}}}{e^{\la_i t}}\right)
 \eeq 

We see that \beq \sup_{\la_i \in I_k} \left(\frac{\la_i^{\frac{n-1}{4}}}{e^{\la_i t}}\right) & < & \frac{2^{\frac{(k+1)}{2}}}{\exp(2^{\frac{2k}{n}}t)}\\
& < & \exp(\frac{(k+1)}{2} - 2^\frac{2k}{n} t).\eeq
When \beq\lab{eq:1.10}  k \geq \left(\frac{n}{2}\right) \log_2 \frac{6k}{t}, \eeq  assuming $k > 5$, we have \beq \frac{k/t}{n/2t} \geq \log_2 \frac{\frac{5}{2}(k+1)}{t}, \eeq and then, we see that 
\beq \exp(\frac{(k+1)}{2} - 2^\frac{2k}{n} t) < 2^{-2( k+1)}. \eeq
In order to enforce (\ref{eq:1.10}), it suffices to have \beq \frac{k}{\log_2 \frac{6k}{t}} & \geq &  \frac{n}{2},\eeq which is implied by \beq \frac{6k}{\log_2 \frac{6k}{t}}\log_2\left( \frac{6k}{t\log_2 \frac{6k}{t}} \right) & \geq &  {3n}\log_2\left(\frac{3n}{t}\right).\eeq This is equivalent to 
\beq k\left(1 - \frac{\log_2 {\log_2 \frac{6k}{t}}}{{\log_2 \frac{6k}{t}}} \right) & \geq &  \frac{n}{2}\log_2\left(\frac{3n}{t}\right),\eeq
which is in turn implied by 
\beq k & \geq &  \frac{n}{2} \left(\log_2 \frac{3n}{t}\right)\left( 1 - \frac{\log_2 \log_2 \frac{3n}{t}}{\log_2 \frac{3n}{t}}\right)^{-1}\\ &  =  & (1 + o(1))\frac{n}{2} \log_2 \frac{3n}{t}. \eeq

Therefore, for any $$k_0 > C_G +  (1 + o(1))\frac{n}{2} \log_2 \frac{3n}{t},$$
\beq \sum_{\la_i > 2^{\frac{2k_0}{n}}} \dim(F_i)e^{- \la_i t} (c_2 \lambda_i^{\frac{n-1}{4}})  < \frac{2^{(-k_0-1)}}{1 - (1/2)} < 2^{(-k_0)}. \eeq


\end{proof}
 It follows from (\ref{eq:byW}) that for any $\eta$, by choosing $$k_0 = \max\left(\log_2 \frac{1}{\eta}, C_G +  (1 + o(1)){n} \log_2 \frac{1}{\eps}\right),$$ and \beq\lab{eq:M} M \geq  2^{2k_0/n}\eeq we have that
\beq \label{eq:one}  \|\tilde{H}_{t, M}  - {H}_t\|_{\LL^2} < \eta.\eeq

\section{Equidistribution and an upper bound on the Hausdorff distance.}
Let $A(V)$ denote the collection of self adjoint operators on the finite dimensional Hilbert space $V$. For $B \in A(V)$, we let $\|B\|$ denote the operator norm of $B$, equal to the largest absolute value attained by an eigenvalue of $A$. The cone of {\it non-negative definite} operators
$$\Lambda(V) = \{B\in A(V)|\forall v, \langle Av, v\rangle \geq 0\}$$ turns $A(V)$ into a poset by the relation $A \geq B$ if $A - B \in \Lambda(V)$.

We next state a matrix Chernoff bound due to Ahlswede and Winter from \cite{AW}.
 \begin{thm}\lab{thm:AW}
Let $V$ be a Hilbert Space of dimension $D$ and let $A_1, \dots, A_k$ be independent identically distributed random variables taking values in $\Lambda(V)$ with expected value $\E[A_i] = A\geq \mu I$ and $A_i \leq I$. Then for all $\eps \in [0, 1/2]$,
$$ \p\left[\frac{1}{k} \sum_{i=1}^k A_i \not\in [(1-\epsilon)A, (1 + \epsilon)A]\right] \leq 2D \exp\left(\frac{-\eps^2\mu k}{2\ln 2}\right).$$
\end{thm}


For any $g \in G$
\beq (Id - T_g) \tilde{H}_{t, M} \eeq lies in \beq \tilde{F}_M := \bigoplus_{ 0 < \la_i \leq M} F_i. \eeq
$\tilde{F}_M$ has, by Weyl's law, a  dimension that is bounded above by $O(M^{n/2})$.
We will study the Markov operator $P: \tilde{F}_M \To \tilde{F}_M$ given by
\beq P(f)(x) := \frac{\sum\limits_{g \in \A} (f(x) + f(gx))}{2|\A|}. \eeq

We know that  $\A = \cup_i \A_i$, where, $\A_i =  \{g_i\} \cup \{g_i^{-1}\}$.
Note that $P$ is the sum of $k$ i.i.d operators \beq P_i :=  \frac{\sum\limits_{g \in \A_i} (f(x) + f(gx))}{4}. \eeq
We see that $\forall f \in \tilde{F}_M$, and $1 \leq i \leq k$,  \beq \E P_i(f) = (1/2) f, \eeq which is equivalent to
$$\E P_i = (1/2) I. $$

By \cref{thm:AW}, 
for all $\eps \in [0, 1/2]$,
\beq \p\left[\frac{1}{k} \sum_{i=1}^k P_i \not\in [((1-\epsilon)/2)I, ((1 + \epsilon)/2) I]\right] \leq C_GM^{n/2} \exp\left(\frac{-\eps^2 k}{4\ln 2}\right).\eeq Setting $\eps = 1/2$ and substituting for $M$, we see that 

\beq \p\left[\frac{1}{k} \sum_{i=1}^k P_i \not\in [(1/4)I, (3/4) I]\right] \leq \left(C_G M^{n/2}\right) \exp\left(\frac{- k}{16\ln 2}\right).\eeq
Let the map $x \mapsto gx$ be denoted by $T_g$. 
It follows that  
\beqs \p\left[\forall f \in \tilde{F}_M, \left\|\frac{1}{2k} {\sum\limits_{g \in \A}  f \circ T_g} \right\|_{\LL^2} \leq (1/2)\|f\|_{\LL^2} \right] \geq 1 - \left(C_G M^{n/2}\right) \exp\left(\frac{- k}{16\ln 2}\right).\eeqs
Iterating the above inequality $\ell$ times, we observe that
\beqs \p\left[\forall f \in \tilde{F}_M, \left\|\frac{1}{(2k)^\ell} {\sum\limits_{g \in \A^\ell}  f \circ T_g} \right\|_{\LL^2} \leq (1/2)^\ell \|f\|_{\LL^2} \right] \geq 1 - \delta,\eeqs
where \beq\lab{eq:de} \delta:= \left(C_G M^{n/2}\right) \exp\left(\frac{- k}{16\ln 2}\right).\eeq

Choosing $f = \tilde{H}_{t, M}$, we see that
\beqs \p\left[ \left\|\frac{1}{(2k)^\ell} {\sum\limits_{g \in \A^\ell}   \tilde{H}_{t, M} \circ T_g} \right\|_{\LL^2} \leq (1/2)^\ell \| \tilde{H}_{t, M}\|_{\LL^2} \right] \geq 1 - \delta,\eeqs
By the above, and Lemmas~\ref{lem:6} and \ref{lem:7}, we see that
\beqs \p\left[ \left\|\frac{1}{(2k)^\ell} {\sum\limits_{g \in \A^\ell}   \tilde{H}_{t} \circ T_g} \right\|_{\LL^2} \leq \eta + 2^{-\ell} t^{-n/4} \right] \geq 1 - \delta.\eeqs
Thus, we see that

\beq \lab{eq:eta} \p\left[ \left\|\frac{1_G}{\vol G} - \frac{1}{(2k)^\ell} {\sum\limits_{g \in \A^\ell}   {H}_{t} \circ T_g} \right\|_{\LL^2} \leq \eta + 2^{-\ell} t^{-n/4} \right] \geq 1 - \delta.\eeq

We derive from this, the following theorem on the equidistribution of $\A^\ell$. 
\begin{thm}\lab{thm:main:1}
Let $2^{- \ell} t^{- \frac{n}{4}} \leq \eta \leq 2^{-C_G}t^{\frac{(1 + o(1))n}{2}}.$ Let $\delta=  (C_G/\eta)\exp\left(-\frac{k}{16\ln 2}\right).$ Then, 

\beq \lab{eq:eta1} \p\left[ \left\|\frac{1_G}{\vol G} - \frac{1}{(2k)^\ell} {\sum\limits_{g \in \A^\ell}   {H}_{t} \circ T_g} \right\|_{\LL^2} \leq 2\eta  \right] \geq 1 - \delta.\eeq


\end{thm}

\begin{proof}
This follows from (\ref{eq:eta}) on setting $M = \eta^{-\frac{2}{n}}$ and substituting in (\ref{eq:de}). 
\end{proof}
\begin{comment}
More precisely, with probability at least $1 - \delta$ for $\ell \geq \ln(\sqrt{\vol G} C_\eps)$, for $$f = P^{\ell}  \left( \tilde{H}_{t, M}\right),$$ we have 
$$ \|f\|_2 < \frac{1}{\sqrt{\vol G} C_\eps}.$$

But this means that the  $\LL_1$ norm should be negligible also, since
$$\|f\|_1 \leq \sqrt{\vol G} \|f\|_2 < \frac{1}{ C_\eps}.$$
\end{comment}

\begin{lem}\lab{lem:9}
Suppose $ \eps  \sqrt{ 5\ln \frac{C_G}{ \eps^n}} = r$, and $t = \eps^2$ are sufficiently small.
If $$\left\|\frac{1_G}{\vol G} - \frac{1}{(2k)^\ell} {\sum\limits_{g \in \A^\ell}   {H}_{t} \circ T_g} \right\|_{\LL^2} \leq \sqrt{\vol(B_n)r^{n}}\left(\frac{1}{2\vol(G)}\right),$$ then,  $\A^\ell$ is a $2r$-net of $G$.
\end{lem}
\begin{proof}
Suppose $\A^\ell$ is not a $2r$-net of $G$. Then, there exists an element $\tilde{g}$ such that $d(\tilde{g}, \A^\ell) > 2r$.
Let $B(r, \tilde{g})$ be the metric ball of radius $r$ centered at $\tilde{g}$. Then, for any $g \in \A^\ell$, $B(r, g) \cap B(r, \tilde{g}) = \emptyset.$ Applying  \cref{lem:1}  we see that 
${H}_{t}(g^{-1} y) < \frac{1}{3\vol G}$ for all $g \in \A^\ell$ and all $y \in B(r, \tilde{g})$. Therefore, 
$$       \frac{1}{(2k)^\ell} {\sum\limits_{g \in \A^\ell}   {H}_{t} \circ T_g(y)}             < \frac{1}{3\vol G}$$ for all all $y \in B(r, \tilde{g})$. This implies that 
\beq \left\|\frac{1_G}{\vol G} - \frac{1}{(2k)^\ell} {\sum\limits_{g \in \A^\ell}   {H}_{t} \circ T_g} \right\|_{\LL^2} & > &
\sqrt{\vol(B(0, r))}\left(\frac{2}{3\vol(G)}\right)\\ & > & \sqrt{\vol(B_n)r^{n}}\left(\frac{1}{2\vol(G)}\right),\eeq
which is a contradiction.
\end{proof}




\begin{thm} \lab{thm:11} Suppose $ \eps  \sqrt{ 5\ln \frac{C_G}{ \eps^n}} = r$.
Choose $$k \geq C_G + (16 \ln 2)((1 + o(1))n\ln \frac{1}{\eps} +  \ln \frac{1}{\delta})$$ i.i.d random points $\{g_1, \dots, g_k\}$ from the Haar measure on $G$ and let $$\A = \{g_1, g_1^{-1}, \dots, g_k, g_k^{-1}\}.$$ Let $X$ be the set of all elements of $G$ which can be expressed as words of length less or equal to $\ell$ with alphabets in $\A$, where $\ell \geq C_G+ \frac{n}{2}\log_2(\frac{1}{\eps r})$ . Then, with probability at least $1 - \delta$, for every element $g \in G$ there is $x \in X$ such that $d(g, x) < 2r$.
\end{thm}
\begin{proof}
Let $\eta = 2^{- C_G} \eps^{(1 + o(1))n}$ in \cref{lem:7}. We set $\log_2 M = C_G + \log_2 \frac{1}{t^{1 + o(1)}},$ by enforcing an equality in (\ref{eq:M}). Taking logarithms on both sides of (\ref{eq:de}), we see that 
$$- \ln \frac{1}{\delta} = C_G + \frac{n}{2} \ln t^{-(1 + o(1))} - \frac{k}{16\ln 2}.$$ This fixes the lower bound for $k$ in the statement of the corollary. 
In order to use (\ref{eq:eta}) in conjunction with \cref{lem:9}, we see that it suffices to set $2^{-\ell}t^{- \frac{n}{4}}$ to a value less than $r^{n/2}$, because for small $\eps$, the value of $\eta$ that we have chosen is significantly smaller than $r^{n/2}$. This shows that the theorem holds for any $\ell$ greater or equal to  $ \frac{n}{2} \log_2 \frac{1}{\eps r} + C_G.$
\end{proof}
\begin{comment}
\section{Lower bounds on the number of generators and  word length required for a given Hausdorff distance}\lab{sec:lower}

Let us take $\eps > 0$, $\delta> 0$. We are now interested in lower bounds on the value of $\ell$ as a function on $\eps, \delta$ and $k$. 
Let $G$ be a compact Lie group with a left invariant Riemannian distance function that results in $G$ having a unit Riemannian volume. 

The number of distinct elements that the set of all words $\A^\ell$ of length $\ell$ in $k$ alphabets (and their inverses) correspond to in a group is less or equal to   
$(2k)^\ell$. We note in passing, that equality can only hold when $\ell \leq 1$  because of the presence of inverses in $\A$.
 Therefore, the measure covered by a $r-$neighborhood  of ${(2k)^\ell}$ elements is less or equal to $(2k)^\ell \vol(B_n(r)).$  Since this has to be at least $1$ for $\A^\ell$ to be a $r-$net of $G$, we obtain 
\beq {(2k)^\ell} \vol(B_n(r)) \geq 1. \eeq
Thus, if $r$ is sufficiently small, we see from (\ref{eq:2.7}) and the remarks preceeding it that 
\beq {(2k)^\ell}  \geq \frac{1}{2\omega_n r^n}, \eeq where $\omega_n$ is the volume of the unit Euclidean ball. Since the Euclidean ball is contained in a cube of side $2$, we see that 
$${(2k)^\ell}  \geq 2^{-1}\left(\frac{1}{2r}\right)^n.$$
Suppose that for some  constant $C_G$ depending only the the group $G$ and its distance function, 
$k \leq C_G \ln \frac{1}{r}$. Then, $$\ell \geq  \frac{n\ln \left(\frac{1}{4r}\right)}{\ln(2C_G\ln \frac{1}{r})}.$$ We encapsulate this in the following proposition.
\begin{prop}\lab{thm:13.5}
Let $G$ be a compact Lie group with a left invariant Riemannian distance function that results in $G$ having a unit Riemannian volume. 
Suppose that for some  constant $C_G$ depending only the the group $G$ and its distance function, 
$k \leq C_G \ln \frac{1}{\eps}$. Choose $k$ i.i.d random points $\{g_1, \dots, g_k\}$ from the Haar measure on $G$ and let $$\A = \{g_1, g_1^{-1}, \dots, g_k, g_k^{-1}\}.$$  Suppose $\A^\ell$ is an $\eps-$net of $G$. Then, $$\ell \geq  \frac{n\ln \left(\frac{1}{4\eps}\right)}{\ln(2C_G\ln \frac{1}{\eps})}.$$
\end{prop}

In the remainder, we consider the case when $G = \R^n/\Z^n,$  the unit $n-$dimensional torus.

The number of distinct elements that the set of all words $\A^\ell$ of length $\ell$ in $k$ alphabets (and their inverses) correspond to in an abelian group is less or equal to 
${2k + \ell - 1\choose \ell}$. Therefore, the measure covered by a $2r-$neighborhood (in an $\ell_2^n$ sense) of ${2k + \ell - 1\choose \ell}$ elements is less or equal to ${m - 1\choose \ell}(2r)^n \vol(B_n),$ for $r < 1/2$. Since this has to be at least $1$ for $\A^\ell$ to be a $2r-$net of $G$, we obtain 
\beq {m - 1 \choose \ell}(2r)^n \vol(B_n) \geq 1. \eeq

We will obtain a lower bound for $k$ using the above inequality. It is clear that a lower bound that is twice as big must hold for $\ell+1$ by the identity 

$${2k + \ell - 1\choose \ell} = {2k + \ell - 1\choose 2k-1}.$$

\beq {m - 1 \choose \ell}2^n \vol(B_n) \geq \frac{1}{r^n}, \eeq

therefore, \beq \ln {m^{2k}} - \ln {(2k-1)!} + \ln\left(2^n \vol(B_n)\right) \geq n\ln \frac{1}{r}. \eeq
Therefore \beq k \geq \frac{ n \ln \frac{1}{r}}{2 \ln m}.\eeq
Let us place the further constraint that $\ell \leq k \leq 2\ell$ as was the case in our upper bound for reasonably large values of $\delta$.
We then using Stirling's approximation see that $$2 k\ln 3k - (2k -2) \ln (2k) + 2k  \geq { n \ln \frac{1}{r}} -  \ln\left(2^n \vol(B_n)\right).$$
This leads to 
$$2 \ln 2 k + 2k (1 + \ln (3/2))   \geq {  n \ln \frac{1}{r}}  - \ln\left(2^n \vol(B_n)\right).$$

Therefore, for sufficiently large $n$, $$k  \geq  (2\ln(1 + \ln (3/2)))^{-1}\left(n \ln \frac{1}{r} -  \ln\left( n \ln \frac{1}{r}\right)  - \ln\left(2^n \vol(B_n)\right) -  \ln\left(-\ln\left(2^n \vol(B_n)\right)\right)\right).$$
This can be simplified  to the following weaker inequality: 
\beq k  \geq  (2\ln(1 + \ln (3/2)))^{-1}\left(n \ln \frac{1}{r} -  \ln\left(  \ln \frac{1}{r}\right)  \right),\eeq
which is greater than $\frac{n}{2}\ln \frac{1}{r}$, when $r$ is sufficiently small. Therefore, we also have
\beq \ell + 1 \geq  (\ln(1 + \ln (3/2)))^{-1}\left(n \ln \frac{1}{r} -  \ln\left(  \ln \frac{1}{r}\right)  \right),\eeq
which is greater than $\frac{n}{4}\ln \frac{1}{r}$, when $r$ is sufficiently small.
We thus have the following proposition.

\begin{prop}\lab{thm:14}
Let $G = \R^n/\Z^n$ be the standard $n-$dimensional torus. Let $r$ be a positive real, bounded above by a  sufficiently small constant depending on $n$. Let $\ell \leq k \leq 2\ell.$ Choose $k$ i.i.d random points $\{g_1, \dots, g_k\}$ from the Haar measure on $G$ and let $$\A = \{g_1, g_1^{-1}, \dots, g_k, g_k^{-1}\}.$$ Suppose $\A^\ell$ is an $r-$net of $G$. Then, $k \geq \frac{n}{2} \ln \frac{1}{r},$ and $\ell \geq  \frac{n}{4} \ln \frac{1}{r}.$
\end{prop}
\end{comment}

\acknowledgements{
We are grateful to Charles Fefferman, Anish Ghosh, Sergei Ivanov and Matti Lassas for helpful discussions. We thank
Emmanuel Breuillard for a useful correspondence. We are grateful to Somnath Chakraborty for a careful reading. This work was supported by NSF grant  \#1620102  and a Ramanujan fellowship.
}

\printbibliography


\end{document}
% ----------------------------------------------------------------
