\section{Introduction}

The goal of this note is to give estimates from below for the bottom of the combinatorial spectrum $\mu_0(G,S)$, for $G={\PSL(2,\Z)}$ associated to the system of generators $S = \{r,u\}$, where $r=\begin{psmallmatrix} 0 & 1 \\ -1 & 0 \end{psmallmatrix}$ and $u=\begin{psmallmatrix} 1 & 1 \\ 0 & 1 \end{psmallmatrix}$. By combinatorial spectrum, we refer to the spectrum of the combinatorial Laplace operator on the Cayley graph.

The main motivation for writing this note is that, even if it is likely that in the present case, estimates (or even the exact value) of $\mu_0(G,S)$ are known by the experts, we could not find any clue of this.
The problem of computing $\mu_0(G,S)$ arose in a previous version of \cite{Pa}, but some adjustments on the arguments changed the objects of study, so there is no longer record of the estimates on the present work (however, the same techniques are used in \cite[Appendix~B]{Pa}).

As suggested by S.~Gou\"ezel~\cite{Go} (cf.~\cite{Go2}), we estimate $\mu_0(G,S)$ from below following ideas of T.~Nagnibeda~\cite{Na} and prove the following.

\begin{theo} \label{theo:combinatorial spectrum}
Let $G={\PSL(2,\Z)}$ and $S = \{r,u\}$. Then, the bottom of the combinatorial spectrum associated to $S$ satisfies \[\mu_0(G,S) > 0.07.\]
\end{theo}

\begin{rema}
The bottom of the combinatorial spectrum associated to a symmetric finite system of $k>1$ generators, is bounded from above by $k-2\sqrt{k-1}$ (which corresponds to the bottom of the combinatorial spectrum of a regular tree of degree $k$).
In our case, this means that $\mu_0(G,S) < 3-2\sqrt{2} \approx 0.1716$.
\end{rema}

\section{Combinatorial group theory}

In this section, we recall some aspects of combinatorial group theory we need and, in particular, we recall the definition of the bottom of the combinatorial spectrum $\mu_0(G,S)$. The following discussion is completely general.

Let $G$ be any group, and let $S$ be a subset of $G$. A \emph{word} in $S$ is any expression of the form
\[ w=s_{1}^{\sigma _{1}}s_{2}^{\sigma _{2}}\cdots s_{n}^{\sigma _{n}}\]
where $s_1,\dots,s_n\in S$ and $\sigma_i \in \{+1,-1\}$, $i=1,\dots,n$. The number $l(w)=n$ is the \emph{length} of the word.

Each word in $S$ represents an element of $G$, namely the product of the expression.
The identity element can be represented by the empty word, which is the unique word of length zero.

\subsection*{Notation}
We use an overline to denote inverses, thus $\bar s$ stands for $s^{-1}$.

In these terms, a subset $S$ of a group $G$ is a system of generators if and only if every element of $G$ can be represented by a word in $S$. Henceforth, let $S$ be a fixed system of generators of $G$ and a word is assumed to be a word in $S$. A \emph{relator} is a non-empty word that represent the identity element of $G$.

Any word in which a generator appears next to its own inverse ($s\bar s$ or $\bar ss$) can be simplified by omitting the redundant pair. We say that a word is \emph{reduced} if it contains no such redundant pairs.

Let $v,w$ be two words. We say that $v$ is a \emph{subword} of $w$ if $w=v'vv''$, for some words $v',v''$. If $v'$ is the empty word we say that $v$ is a \emph{prefix} of $w$. If $v''$ is the empty word we say that $v$ is a \emph{suffix} of $w$.

We say that a word is \emph{reduced in $G$} if it has no non-empty relators as subword.
In particular, if a word is reduced in $G$, any of its subwords is also reduced in $G$.

For an element $g\in G$, we consider the \emph{word norm} $|g|$ to be the least length of a word which is equals to $g$ when considered as a product in $G$, and every such word is called a \emph{path}, that is, if its length coincides with its word norm when considered as a product in $G$. In particular, a path is always reduced in $G$. Moreover, a subword of a path is also a path. We say that two words are \emph{equivalent} if they represent the same element in $G$.

For a relator, we call a subword that is a relator, a \emph{subrelator}. We say that a relator is \emph{primitive} if every proper subword is reduced in $G$, that is, if it does not contain proper subrelators. In particular, a word is reduced in $G$ if and only if it contains no primitive relators as subword.
Note that, if $P$ is the set of all primitive relators, then $\langle S \mid P \rangle$ is a presentation of $G$.

The following elementary results (see Figure~\ref{figu:decomposition}) will be useful in \S\ref{sect:compatible type function}.

\begin{lemm}
Let $v,w$ be two different equivalent paths. Then, there are paths $v_0,v_1$, $w_0,w_1$ and $x$ such that $v = v_0v_1x$ and $w = w_0w_1x$, and $v_1\bar w_1$ is a primitive relator (of even length).
\end{lemm}

\begin{figure}[ht]
\centering\includegraphics[height=.26\textheight]{word-decomposition.pdf}
\caption{Decomposition of two equivalent paths}
\label{figu:decomposition}
\end{figure}

\begin{proof}

Let $x$ be the largest common suffix of $v$ and $w$ (possibly $x$ is empty). Write $v=v'x$ and $w = w'x$.
Let $w_1$ and $v_1$ be the smallest non-empty suffixes of $w'$ and $v'$ respectively such that $v_1$ and $w_1$ are equivalent. Such $v_1$ and $w_1$ exist since $v$ and $w$ are different words. Moreover, they have the same length since they are equivalent, that is, they are paths that evaluate to the same element in $G$. Write $v'=v_0v_1$ and $w'=w_0w_1$ (possibly $v_0$ and $w_0$ are empty). In particular $v_0$ and $w_0$ are equivalent, since the same holds for $v',w'$ and $v_1,w_1$.

It remains to prove that $v_1\bar w_1$ is primitive.
Suppose $z$ is a subrelator of $v_1\bar w_1$.
Since $v_1$ and $w_1$ are paths, they are in particular reduced in $G$ and also their subwords. Then $z = v_2\bar w_2$ for some non-empty suffixes $v_2$ and $w_2$ of $v_1$ and $w_1$ respectively. In particular, $v_2$ and $w_2$ are non-empty suffixes of $w'$ and $v'$ respectively and $v_2,w_2$ are equivalent. But, by definition, $v_1$ and $w_1$ are the smallest such suffixes and therefore $v_2=v_1$ and $w_2=w_1$. Thus, $v_1\bar w_1$ has no proper subrelators and therefore, $v_1\bar w_1$ is primitive.
\end{proof}

As a direct consequence of the previous lemma, we have the following.

\begin{coro} \label{coro:primitive relator subword}
Let $v=v'yx$ and $w=w'zx$ be two equivalent paths such that $y\bar z$ is reduced in $G$. Then, $y\bar z$ is a subword of some primitive relator (of even length).
\end{coro}

\begin{proof}
Consider the decomposition given by the previous lemma. It is clear that $y$ is a subword of $v_1$ and $z$, of $w_1$. Then $y\bar z$ is a subword of the primitive relator $v_1\bar w_1$.
\end{proof}





\subsection{Combinatorial spectrum}
Let $G$ be a finitely generated group and $S\subset G$ be a finite system of generators of $G$.
Let $\ell^2(G)$ be the space of square-summable sequences on $G$ with the inner product \[\langle h,h' \rangle \coloneqq \sum_{g\in G} h_g {h\mathrlap{'}}_g,\] for $h,h'\in\ell^2(G)$, and define $\Delta_S:\ell^2(G)\to\ell^2(G)$, the combinatorial Laplace operator on $G$ associated to $S$, by \[(\Delta_S h)_g \coloneqq \sum_{s\in S\cup\bar S} (h_g - h_{gs}),\] for $h\in\ell^2(G)$.
Then, we define $\mu_0(G,S)$, \emph{the bottom of the combinatorial spectrum of $G$ associated to $S$} to be the bottom of the spectrum of $\Delta_S$, that is, \[\mu_0(G,S)\coloneqq \inf \left\{\frac{\langle \Delta_S h, h \rangle}{\langle h, h \rangle},\; h\in \ell^2(G)\right\}.\]

\begin{rema} The subjacent object in this discussion is the Laplace operator on the Cayley graph of $G$ associated to $S$. However we do not explain this here.
\end{rema}

\subsection{Nagnibeda's ideas}

In order to give estimates from below to the combinatorial spectrum we follow ideas of Nagnibeda~\cite{Na}, which are based in the following result, whose proof is elementary (see, for example,~\cite[\S7.1]{Co}).

\begin{prop}[Gabber--Galil's lemma] \label{prop:GG}
Let $G$ be a finitely generated group and $S$ a finite symmetric system of generators of $G$. Suppose there exists a function $L:G\times S\to \mathbb{R}_+$ such that, for every $g\in G$ and $s\in S$,
\[L(g,s) = \frac{1}{L(gs,s^{-1})} \qquad \text{ and } \qquad \sum_{s\in S} L(g,s) \leq k,\] for some $k>0$.
Then, \[\mu_0(G,S) \geq \# S - k.\]
\end{prop}

Let $S$ be a symmetric finite system of generators of $G$. For $g\in G$, denote by $|g|$ the word norm with respect to $S$ and define $S^\pm(g)\coloneqq \{s\in S :\; |gs| = |g| \pm 1\}$. For $g\in G$ and $s\in S$, we say that $gs$ is a \emph{successor} of $g$ if $s\in S^+(g)$ and that $gs$ is a \emph{predecessor} of $g$ if $s\in S^-(g)$. Henceforth we assume $S^{+}(g)\cup S^{-}(g)=S$, for every $g\in G$. Note that this is equivalent to say that every relator has even length.

A function $t:G \to \mathbb{N}$ is called a \emph{type function on $G$} and its value $t(g)$ at $g\in G$ is called the \emph{type of $g$}. We say that a type function $t$ is \emph{compatible with $S$}, or simply that $t$ is a \emph{compatible type function}, if the following two conditions are equivalent:
\begin{enumerate}
\item $t(g) = t(g')$;
\item $\#\{s\in S^+(g) :\; t(gs)=k\} = \#\{s'\in S^+(g') :\; t(g's')=k\}$, for every $k\in \mathbb{N}$.
\end{enumerate}
Equivalently, $t$ is a compatible type function if the (multiset of) types of successors of an element $g\in G$ (is/)are completely defined by its type $t(g)$.

For any type function $t:G \to \mathbb{N}$ and positive valuation $c: \mathbb{N}\to \mathbb{R}_+$, we can consider a function $L_c:G\times S\to \mathbb{R}_+$ defined by
\[L_c(g,s) = \begin{cases} c_k, & \text{if } s \in S^+(g),\;k = t(gs), \\ 1/c_k, & \text{if } s\in S^-(g),\;k = t(g). \end{cases}\]
It is clear then, by the definition, that any $L_c:G\times S\to \mathbb{R}_+$ defined as above satisfies $L_c(g,s) = 1/L_c(gs,s^{-1})$, since $s\in S^+(g)$ if and only if $s^{-1}\in S^-(gs)$, and $S=S^+(g)\cup S^-(g)$, for every $g\in G$.

Moreover, for a compatible type function $t$, we define for $k=t(g)\in \mathbb{N}$, $g\in G$,
\[
f_k(c) \coloneqq \sum_{s\in S} L_c(g,s) = \sum_{s\in S^+(g)} c_{t(gs)} + \frac{\# S^-(g)}{c_k}.
\]
Note that this is well defined since $t$ is compatible with $S$ and therefore the sum depends only on $k$, the type of $g$.

As a direct consequence of Gabber--Galil's lemma (Proposition~\ref{prop:GG}), we get the following.

\begin{coro} \label{coro:GG} Let $t:G\to \{0,\dots, K\}$ be a compatible type function. Then, \[\mu_0(G,S) \geq \# S - \max_{k=0,\dots,K} f_k(c),\] for every $c:\{0,\dots, K\} \to\mathbb{R}_+$, where $f_k$ is defined as above.
\end{coro}

Then, every compatible (finite) type function gives lower bounds for the combinatorial spectrum.



\section{Compatible type functions for $G={\PSL(2,\Z)}$, $S=\{r,u\}$}
\label{sect:compatible type function}

Until now, the discussion is completely general. We now specialize to the case of $G={\PSL(2,\Z)}$ with generators $r=\begin{psmallmatrix} 0 & 1 \\ -1 & 0 \end{psmallmatrix}$ and $u=\begin{psmallmatrix} 1 & 1 \\ 0 & 1 \end{psmallmatrix}$.
The aim in the following is to give a compatible finite type function in this case, in order to give estimates for the bottom of the combinatorial spectrum with the aid of Corollary~\ref{coro:GG}.
For this, we define a \emph{suffix type function} and prove that it is compatible with $S=\{r,u\}$.

It is classical that $\langle r,u \mid r^2,(ru)^3\rangle$ is a presentation of $G$. Since we have the relator $r^2$, for the sake of simplicity, we omit henceforth $\bar r$, since as element in $G$ it coincides with $r$.
The set of primitive relators is then (up to include the variants with $\bar r$ instead of $r$) given by
\[\{ r^2, (r u)^3, (r \bar u)^3, (ur)^3, (\bar ur)^3\}.\]
In particular, every relator has even length and we can apply previous discussion.

Let $\mbf S(g)$ be the set of all suffixes of paths for $g\in G$. Then, by the description of the primitive relators, as a direct consequence of Corollary~\ref{coro:primitive relator subword}, we have the following.

\begin{coro}
The following cases cannot happen:
\begin{itemize}
\item $u,\bar u \in \mbf S(g)$;
\item $ur,\bar ur \in \mbf S(g)$;
\item $ar,\bar a^2 \in \mbf S(g)$, for $a=u$ or $\bar u$; or
\item $ar,a \in \mbf S(g)$, for $a=u$ or $\bar u$.
\end{itemize}
\end{coro}

\begin{proof}
Neither $u^2$, $ur\bar u$ nor $\bar uru$ are subwords of a primitive relator.
\end{proof}

Let $\mbf S_n(g)$ be the set of all suffixes of length $n\in \mathbb{N}$ of paths for $g\in G$ and define, by recurrence, $\mbf S_1^*(g) = \mbf S_1(g)$ and
\[\mbf S_{n+1}^*(g) = \begin{cases} \mbf S_{n+1}(g) & \text{if } S_{n+1}(g) \neq \emptyset, \\ \mbf S_n^*(g) & \text{if } S_{n+1}(g) = \emptyset. \end{cases}\]
Note that any injective function $j:\mbf S_n^*(G) \to \mathbb{N}$ defines a (finite) type function $t=j\circ \mbf S_n^*:G\to\mathbb{N}$, which we call \emph{suffix type function of level~$n$}.


\begin{lemm} Let $t:G\to \mathbb{N}$ be a suffix type function of level~$2$. Then, it is compatible with $S$.
\end{lemm}

\begin{proof}
Being compatible with $S$ means that the type $t(g)$ of $g\in G$ completely defines the types of its successors. Then, it is enough to show that $\mbf S_2^*(g)$ defines completely the multiset $\{\mbf S_2^*(gs): s\in S^+(g)\}$.

By the previous corollary, we have that it cannot happen that $u,\bar u \in\mbf S_1(g)$, that $\#\mbf S_2(g)\leq 2$ and that $\mbf S_2(g)= 2$ if and only if $\mbf S_2(g) = \{ra,a^2\}$ or $\{ra,\bar ar\}$, for $a=u$ or $\bar u$.
It follows then, that $\mbf S_1^*(g) \in \{\emptyset,\{r\},\{u\},\{\bar u\},\{u,r\},\{\bar ur\}\}$ and
\[\mbf S_2^*(g) \in \{\emptyset,\{r\},\{ar\},\{a\},\{ra\},\{a^2\},\{ra,a^2\},\{ra,\bar ar\}\}_{a=u,\bar u}.\]
Moreover, it is clear that $s\in S^+(g)$ if and only if $\bar s\notin \mbf S_1(g)$.

Let $a=u$ or $\bar u$.
\begin{itemize}
\item If $\mbf S_2^*(g) = \emptyset$, $g=1$ and evidently $\mbf S_2^*(gs) = \{s\}$, for $s\in S=S^+(g)$.
\item If $\mbf S_2^*(g) = \{r\}$, $g=r$ and $\mbf S_2^*(gb) = \{rb\}$, for $b\in\{u,\bar u\} = S^+(r)$.
\item If $\mbf S_2^*(g) = \{ar\}$, $S^+(g)=\{u,\bar u\}$, $\mbf S_2^*(ga) = \{ra,\bar ar\}$ and $\mbf S_2^*(g\bar a) = \{r\bar a\}$.
\item If $\mbf S_2^*(g) = \{a\}$, $g=a$ and $S^+(g)=\{r,a\}$. Moreover, $\mbf S_2^*(gr) = \{ar\}$ and $\mbf S_2^*(ga) = \{a^2\}$.
\item If $\mbf S_2^*(g) = \{ra\}$, then $S^+(g)=\{r,a\}$, $\mbf S_2^*(gr) = \{ar,r\bar a\}$ and $\mbf S_2^*(ga) = \{a^2\}$.
\item If $\mbf S_2^*(g) = \{a^2\}$, then $S^+(g)=\{r,a\}$, $\mbf S_2^*(gr) = \{ar\}$ and $\mbf S_2^*(ga) = \{a^2\}$.
\item If $\mbf S_2^*(g) = \{ra,a^2\}$, $S^+(g)=\{r,a\}$, $\mbf S_2^*(gr) = \{ar,r\bar a\}$ and $\mbf S_2^*(ga) = \{a^2\}$.
\item If $\mbf S_2^*(g) = \{ra,\bar ar\}$, then $S^+(g)=\{a\}$ and $\mbf S_2^*(ga) = \{ra,a^2\}$.
\end{itemize}
Thus, given only the value of $\mbf S_2^*(g)$ we can tell $\mbf S_2^*(gs)$, $s\in S^+(g)$ and therefore, suffix type functions are compatible with $S$.
\end{proof}

We summarize the proof of the previous lemma by the following diagram which shows each possible $\mbf S_2^*(g)$, $g\in G$ with its respective multiset of $\mbf S_2^*(gs)$, $s\in S^+(g)$:
\begin{align*}
\mbf S_2^*(g) & \to \mbf S_2^*(gs), s\in S^+(g) \\
\\
\emptyset & \to \{r\}, \{u\}, \{\bar u\} \\
\{r\} & \to \{ru\}, \{r\bar u\} \\
\{ar\} & \to \{ra,\bar ar\}, \{r\bar a\} \\
\{a\} & \to \{ar\}, \{a^2\} \\
\{ra\} & \to \{ar,r\bar a\}, \{a^2\} \\
\{a^2\} & \to \{ar\}, \{a^2\} \\
\{ra,a^2\} & \to \{ar,r\bar a\}, \{a^2\} \\
\{ra,\bar ar\} & \to \{ra,a^2\},
\end{align*}
where $a=u$ or $\bar u$.

It is not difficult to see in the previous diagram that there are different suffix types which share the types of the successors. Namely $\{a\},\{a^2\}$ and $\{ra\},\{ra,a^2\}$. This allows us to reduce the number of types. Furthermore, it is clear that distinguishing $u$ and $\bar u$ in the previous description has no major benefit.
This motivates the definition of the following type function. Let $T:G\to\{0,\dots,5\}$ be the type function defined as follows:
\[
T(g) =
\begin{cases}
0 & \text{if } \mbf S_2^*(g) = \emptyset, \\
1 & \text{if } \mbf S_2^*(g) = \{r\}, \\
2 & \text{if } \mbf S_2^*(g) = \{ar\},\; a=u \text{ or } \bar u, \\
3 & \text{if } \mbf S_2^*(g) = \{a\} \text{ or } \{a^2\},\; a=u \text{ or } \bar u, \\
4 & \text{if } \mbf S_2^*(g) = \{ra\} \text{ or } \{ra,a^2\},\; a=u \text{ or } \bar u, \\
5 & \text{if } \mbf S_2^*(g) = \{ar,r\bar a\},\; a=u \text{ or } \bar u.
\end{cases}
\]

From the previous discussion, we deduce the following.
\begin{theo} \label{theo:cone types} The type function $T:G\to \{0,\dots,5\}$ is compatible with $S$.
Moreover,
\begin{itemize}
\item Type $0$ elements have one type $1$ and two type $3$ successors;
\item Type $1$ elements have two type $4$ successors;
\item Type $2$ elements have one type $4$ and one type $5$ successor;
\item Type $3$ elements have one type $2$ and one type $3$ successor;
\item Type $4$ elements have one type $3$ and one type $5$ successor; and
\item Type $5$ elements have one type $4$ successor;
\end{itemize}
\end{theo}

Thus, we have a compatible type function with a full description of the types of the successors for each type. We can then finally apply Nagnibeda's ideas (Corollary~\ref{coro:GG}) to give estimates for the bottom of the combinatorial spectrum.

\section{Estimates for the bottom of the combinatorial spectrum} By Theorem~\ref{theo:cone types}, the $f_k$ of Corollary~\ref{coro:GG} are given by:
\begin{itemize}
\item $f_0(c) = c_1 + 2 c_3$;
\item $f_1(c) = 2 c_4 + 1/c_1$;
\item $f_2(c) = c_4 + c_5 + 1/c_2$;
\item $f_3(c) = c_2 + c_3 + 1/c_3$;
\item $f_4(c) = c_3 + c_5 + 1/c_4$; and
\item $f_5(c) = c_4 + 2/c_5$.
\end{itemize}
It follows that $\mu_0(G,S) \geq \# S - \max_{k} f_k(c)$, for every $c=(c_1,\dots,c_5)\in \mathbb{R}_+^{5}$.
Thus, the problem can be reduced to find the optimal such bound.
This can be solved numerically: we get that $\bar c\in\mathbb{R}_+^5$ with
\[\bar c_1= 1;\; \bar c_2 \approx 0.8323;\; \bar c_3 \approx 0.7326;\; \bar c_4 \approx 0.7927;\; \bar c_5 \approx 0.9358;\]
is a (local) minimun for $\max_{k} f_k(c)$, and $\max_{k} f_k(\bar c) \approx 2.9299 < 2.93$.

Finally, since $\# S=3$, it follows that \[\mu_0(G,S) > 0.07.\]
This concludes the proof of Theorem~\ref{theo:combinatorial spectrum}\qed


