# Dimension bounds for escape on average
in homogeneous spaces

Dmitry Kleinbock  Department of Mathematics, Brandeis University, Waltham MA
<EMAIL_ADDRESS>and  Shahriar Mirzadeh  Department of Mathematical
Sciences, University of Cincinnati, Cincinnati OH<EMAIL_ADDRESS>
(Date: September 2023)

###### Abstract.

Let $X=G/\Gamma$, where $G$ is a Lie group and $\Gamma$ is a uniform lattice
in $G$, and let $O$ be an open subset of $X$. We give an upper estimate for
the Hausdorff dimension of the set of points whose trajectories escape $O$ on
average with frequency $\delta$, where $0<\delta\leq 1$.

The first named author was supported by NSF grant DMS-2155111 and by a grant
from the Simons Foundation (922989, Kleinbock).

##  1\. Introduction

Throughout the paper we let $G$ be a Lie group and $\Gamma$ a lattice in $G$,
denote by $X$ the homogeneous space $G/\Gamma$ and by $\mu$ the $G$-invariant
probability measure on $X$. Let ${F^{+}:=}{({g_{t}})_{t\geq 0}}$ be a one-
parameter subsemigroup of $G$. For a subset $O$ of $X$, define

$\widetilde{E}(F^{+},O):=\big{\\{}x\in X:\exists\ t_{0}\text{ such that
}g_{t}x\notin O\ \forall\,t\geq t_{0}\big{\\}}$

to be the set of $x\in X$ eventually escaping $O$ under the action of $F^{+}$.
If the $F^{+}$-action on $(X,\mu)$ is ergodic, then it follows from Birkhoff’s
Ergodic Theorem that $\mu\big{(}\widetilde{E}(F^{+},O)\big{)}=0$ as long as
$O$ has positive measure. Furthermore, under some additional assumptions one
can obtain upper estimates for the Hausdorff dimension of
$\widetilde{E}(F^{+},O)$. More precisely, one has the following ‘Dimension
Drop Conjecture’, originated from a question asked by Mirzakhani (private
communication): if $F\subset G$ is a subsemigroup and $O$ is an open subset of
$X$, then either $\widetilde{E}(F,O)$ has positive measure, or its Hausdorff
dimension is less than the dimension of $X$. When $X$ is compact it follows
from the variational principle for measure-theoretic entropy, as outlined in
[12, §7]; an effective argument using exponential mixing was developed in [9].
See [3] (resp., [10, 11]) for the proof of this conjecture for Lie groups of
rank one (resp., higher rank with some additional assumptions).

In this work we consider trajectories which are allowed to enter $O$, but not
as frequently as mandated by Birkhoff’s Ergodic Theorem. Namely, for
$0<\delta\leq 1$ let us say that a point $x\in X$ _$\delta$ -escapes $O$ on
average under the action of $F^{+}$_ if it belongs to the set

$E_{\delta}(F^{+},O):=\left\\{x\in
X:\limsup_{T\rightarrow\infty}\frac{1}{T}\int_{0}^{T}1_{O^{c}}(g_{t}x)dt\geq\delta\right\\}.$

Again under the assumption of ergodicity for any measurable $O\subset X$
Birkhoff’s Ergodic theorem implies that

$\lim\limits_{T\rightarrow\infty}\frac{1}{T}\int_{0}^{T}1_{O^{c}}(g_{t}x)\,dt=\mu(O^{c}).$

Hence, the set $E_{\delta}(F^{+},O)$ has full measure for any
$0<\delta\leq\mu(O^{c})$, and has measure zero for any $\delta>\mu(O^{c})$.
Clearly for any $\delta$ as above one has

$E_{\delta}(F^{+},O)\supset E_{1}(F^{+},O)\supset\widetilde{E}(F^{+},O).$

Thus one can ask the following questions: under some assumptions, can it be
shown that the set $E_{1}(F^{+},O)$ has less than full Hausdorff dimension? is
the same true for $E_{\delta}(F^{+},O)$ for some $\delta<1$?

To state our results, we need to introduce some notation. If $X$ is a metric
space with metric ‘${\operatorname{dist}}$’, $O$ is a subset of $X$ and $r>0$,
we will denote by $\sigma_{r}O$ the inner $r$-core of $O$, defined as

$\sigma_{r}O:=\\{x\in X:{\operatorname{dist}}(x,O^{c})>r\\},$

and by $O^{(r)}$ the $r$-neighborhood of $O$, that is,

$O^{(r)}:=\\{x\in X:{\operatorname{dist}}(x,O)<r\\}.$

The notation ${A\gg B}$, where $A$ and $B$ are quantities depending on certain
parameters, will mean ${A\geq CB}$, where $C$ is a constant independent on
those parameters. Hausdorff dimension (see Definition 3.1) will be denoted by
‘$\dim$’, and $\operatorname{codim}A$ will stand for the Hausdorff codimension
of a set $A$, that is, the difference between the dimension of the ambient
space and $\dim A$.

Fix a right-invariant Riemannian structure on a Lie group $G$, and denote by
‘${\operatorname{dist}}$’ the corresponding Riemannian metric, using the same
notation for the induced metric on homogeneous spaces of $G$. In what follows,
if $P$ is a subgroup of $G$, we will denote by $B^{P}(r)$ the open ball of
radius $r$ centered at the identity element with respect to the metric on $P$
corresponding to the Riemannian structure induced from $G$, and by $\nu$ the
Haar measure on $P$ induced by this metric. $B(x,\rho)$ will stand for the
open ball in $X$ centered at $x\in X$ of radius $\rho$.

Throughout this paper we shall assume that $\Gamma$ is a uniform lattice in
$G$, that is, $X$ is compact. We note that the methods and results of this
paper can be extended to the noncompact case, however this would require an
extra effort controlling the escape of mass and will be pursued in subsequent
work.

For comparison, let us first state the effective dimension estimate from [9].
There the main tool was the exponential mixing of the action. Namely, let us
say that the flow $(X,F^{+})$ is exponentially mixing if there exist
$\gamma>0$ and $\ell\in{\mathbb{Z}}_{+}$ such that for any $\varphi,\psi\in
C^{\infty}(X)$ and for any $t\geq 0$ one has

${\left|{({g_{t}}\varphi,\psi)-\int_{X}\varphi\,d\mu\int_{X}\psi\,d\mu}\right|\ll{e^{-\gamma
t}}{\left\|\varphi\right\|_{\ell}}{\left\|\psi\right\|_{\ell}}.}$ (1.1)

Here and hereafter ${\|\cdot\|_{\ell}}$ stands for the “$L^{{2}}$, order
$\ell$” Sobolev norm, see e.g. [9, §2] for a definition and basic facts.

The following is a special case of [9, Theorem 1.1]:

######  Theorem 1.1.

Let $G$ be a Lie group, $\Gamma$ a uniform111This is a simplified version of
the theorem; in [9] instead of the compactness of $X$ it was assumed that the
complement of $O$ was compact. The latter assumption has been removed in [10,
11] in many special cases. lattice in $G$, $X=G/\Gamma$, and let ${F^{+}}$ be
a one-parameter ${\operatorname{Ad}}$-diagonalizable subsemigroup of $G$ whose
action on $X$ is exponentially mixing. Then there exists $r_{1}>0$ such that
for any $O\subset X$ and any $0<r<r_{1}$ one has222The result in [9] actually
involved the slightly smaller set  $E(F^{+},O):=\\{x\in X:g_{t}x\notin O\
\forall\,t\geq 0\\}$ of points whose trajectories avoid $O$, bit it is easy to
see that $\dim E(F^{+},O)=\dim\widetilde{E}(F^{+},O)$.

${{\operatorname{codim}\widetilde{E}(F^{+},O){\,\gg}\
}\frac{{\mu({\sigma_{r}O)}}}{{\log(1/r)+\log\big{(}1/\mu({\sigma_{r}O)\big{)}}}}\,.}$
(1.2)

An interesting feature of the above estimate is that its left hand side does
not depend on $r$ while the right hand side does, and tends to $0$ when $r$
either tends to $0$ or becomes large enough. Thus for applications one is left
to seek an optimal value of $r$. For example when $O=B(x,\rho)$ one can take
$r=\rho/2$, producing the estimate

${\operatorname{codim}\widetilde{E}\big{(}F^{+},B(x,\rho)\big{)}{\,\gg}\
\frac{\rho^{\dim X}}{{\log(1/\rho)}}\,.}$ (1.3)

The main theme of the present paper is replacing the phenomenon of eventual
escape by escape on average. In order to state our main result, we need to
introduce the function $\phi:[0,1]\times[0,1]\to{\mathbb{R}}$ by

${\phi(y,s):=({1-s}){\log\frac{1}{1-\frac{y}{2}}}-{2({1-s})}\log\frac{1}{{1-s}}-s\cdot\log\frac{{{1+\frac{y}{4}}}}{s}.}$
(1.4)

We will employ the convention $0\cdot\log\frac{1}{0}=0$; this way we can see
that $\phi$ is a continuous function on ${\mathbb{R}}^{2}$, with

${\phi(y,0)={\log\frac{1}{1-\frac{y}{2}}}\text{ for all }y,}$ (1.5)

hence $\phi(y,s)>0$ for small enough positive $s$ as long as $y>0$.

The following is our first main theorem:

######  Theorem 1.2.

Let $G$, $\Gamma$, $X$ and $F^{+}$ be as in Theorem 1.1. Then there exists
positive constant $r_{1}$ such that for any $O\subset X$, any $0<r<{r_{1}}$
and any $\delta>0$ one has

${\operatorname{codim}E_{\delta}(F^{+},O)\gg\frac{{\mu(\sigma_{r}O)\cdot\phi\big{(}\mu(\sigma_{r}O),\sqrt{1-\delta}\big{)}}}{\log\frac{1}{r}}.}$
(1.6)

Thus, if given a subset $O$ of $X$ we define

${\delta_{O}:=\inf\left\\{0<\delta<1:\phi\big{(}\mu(O),\sqrt{1-\delta}\big{)}>0\right\\},}$
(1.7)

which is strictly less than $1$ whenever $\mu(O)>0$, and if in addition $O$
has non-empty interior, then for any $\delta>\delta_{O}$ one can choose $r>0$
small enough to have $\phi\big{(}\mu(\sigma_{r}O),\sqrt{1-\delta}\big{)}>0$.
This implies

${\operatorname{codim}E_{\delta}(F^{+},O)>0\text{ whenever
}\delta>\delta_{O}.}$ (1.8)

Also one can observe that

$\phi\left(y,\frac{y}{2}\right)=-{\left({1-\frac{y}{2}}\right)}\log\frac{1}{{1-\frac{y}{2}}}-\frac{y}{2}\cdot\log\frac{{{1+\frac{y}{4}}}}{{y}/{2}}<0$

for any $0<y<1$; hence $\delta_{O}>1-{{\frac{\mu(O)^{2}}{4}}}>\mu(O^{c})$.

As an example, here is a graph of the function
$\delta\mapsto\phi(0.8,\sqrt{1-\delta})$; thus for $\mu(O)=\frac{4}{5}$ we get
$\delta_{O}\approx 0.9888$.

In the special case $\delta=1$, using (1.5) we obtain the following immediate
corollary:

######  Corollary 1.3.

Let $G$, $\Gamma$, $X$, $F^{+}$ and ${r_{1}}$ be as in Theorem 1.2. Then for
any $0<r<r_{1}$ we have

$\operatorname{codim}E_{1}(F^{+},O)\gg{\frac{{\mu(\sigma_{r}O)}\cdot\log\frac{1}{1-\frac{\mu(\sigma_{r}O)}{2}}}{\log\frac{1}{r}}}\gg\frac{{\mu(\sigma_{r}O)}^{2}}{\log\frac{1}{r}}.$

One sees that the above corollary does not produce any improvement of (1.2);
on the contrary, our new dimension bound for escape on average happens to be
worse by a factor of $\mu(\sigma_{r}O)$ than the bound for the eventual
escape. In the sequel to the present paper, using some ideas from the work [1]
where a similar problem was studied for the Teichmüller geodesic flow, the
authors plan to improve the existing estimates as well as extend the methods
to treat non-compact homogeneous spaces.

We also remark that when $X$ is not compact, one can consider the set

$E^{comp}_{\delta}(F^{+}):=\bigcap_{C\subset
X\,\text{compact}}{E}_{\delta}(F^{+},C)$

of points in $X$ with trajectories $\delta$-escaping all compact subsets of
$X$. Equivalently one can define $E^{comp}_{\delta}(F^{+})$ as the set of
$x\in X$ such that there exists a sequence $T_{k}\to\infty$ and a weak-$*$
limit $\nu$ of the sequence of probability measures
$f\mapsto\frac{1}{T_{k}}\int_{0}^{T_{k}}f(g_{t}x)\,dt$ such that $\nu(X)\leq
1-\delta$. It is proved in [13, Theorem 1.3] that whenever $G$ is a connected
semisimple Lie group, $\Gamma$ a lattice in $G$ and $F^{+}$ a one-parameter
semigroup contained in one of the simple factors of $G$, one has

$\operatorname{codim}\big{(}E^{comp}_{\delta}(F^{+})\big{)}\geq c\delta\text{
for all }0<\delta<1,$

where $c$ depends only on $G$ and $\Gamma$. See also [6, Remark 2.1] for a
special case.

From now on let $G$, $\Gamma$, $X$ and $F^{+}$ be as in Theorems 1.1 and 1.2.
Similarly to the argument in [9, 10, 11], our main theorem is deduced from a
result that estimates

$\dim E_{\delta}(F^{+},O)\cap Hx,$

where $x\in X$ and $H$ is the unstable horospherical subgroup with respect to
$F^{+}$, defined as

${H:=\\{g\in G:{\operatorname{dist}}({g_{t}}g{g_{-t}},e)\to
0\,\,\,as\,\,\,t\to-\infty\\}.}$ (1.9)

More generally, in the theorem below we estimate

$\dim E_{\delta}(F^{+},O)\cap Px$

for $x\in X$ and some proper subgroups $P$ of $H$, namely those which have so-
called Effective Equidistribution Property (EEP) with respect to the flow
$(X,F^{+})$. The latter property was motivated by [8] and introduced in [9],
where it was shown to hold for $H$ as above under the assumption of
exponential mixing. Namely, we have the following

######  Definition 1.4.

Say that a subgroup $P$ of $G$ has Effective Equidistribution Property (EEP)
with respect to the flow $(X,F^{+})$ if $P$ is normalized by $F^{+}$, and
there exist $\lambda>0$, $t_{0}>0$ and $\ell\in{{\mathbb{N}}}$ such that for
any $x\in X$, $t\geq t_{0}$, $f\in C^{\infty}(P)$ with
$\operatorname{supp}f\subset B^{P}(1)$ and $\psi\in C^{\infty}(X)$ it holds
that

${\left|{\int_{P}f({{h}})\psi(g_{t}{{h}}x)\,d\nu({{h}})-\int_{P}f\,d\nu{\mkern
1.0mu}\int_{X}\psi\,d\mu{\mkern
1.0mu}}\right|\ll{\max\big{(}{\left\|\psi\right\|_{C^{1}},{\left\|\psi\right\|_{\ell}}}\big{)}}\cdot{\left\|f\right\|_{{C^{\ell}}}}\cdot{e^{-\lambda
t}}{\mkern 1.0mu}.}$ (1.10)

We remark that in [9, 10, 11] this property was defined and used in the more
general set-up of $X$ being non-compact, with additional constraints on the
injectivity radius at points $x\in X$ for which (1.10) is satisfied (see §3.2
for more detail). However when $X$ is compact the injectivity radius is
uniformly bounded from below, hence a possibility to simplify the definition.

######  Theorem 1.5.

Let $G$, $\Gamma$, $X$, $F^{+}$ be as above. Then there exists ${{r_{2}}>0}$
such that whenever a connected subgroup $P$ of $H$ has property (EEP) with
respect to the flow $(X,F^{+})$, for any non-empty open subset $O$ of $X$, any
$0<r\leq{r_{2}}$, any $0<\delta<1$ and any $x\in X$ one has

$\operatorname{codim}\big{(}E_{\delta}(F^{+},O)\cap
Px\big{)}\gg\frac{{\mu(\sigma_{r}O)\cdot\phi\big{(}\mu(\sigma_{r}O),\sqrt{1-\delta}\big{)}}}{\log\frac{1}{r}}.$

In the next section we derive Theorem 1.2 from Theorem 1.5, and the rest of
the paper is be dedicated to proving Theorem 1.5. Section 3 contains a
discussion of basic technical constructions needed for the proof, such as
Hausdorff dimension estimates for lim sup sets, tessellations of nilpotent Lie
groups and Bowen boxes. In Section 4 we use property (EEP) to, given a subset
$S$ of $X$, a large $T>0$ and $0<\delta<1$, write down a measure estimate for
the set of $h\in P$ such that the Birkhoff average
$\frac{1}{T}\int_{0}^{T}1_{S}(g_{t}hx)\,dt\geq\delta$. In the subsequent
section this estimate is used to bound the number of Bowen boxes that can
cover certain exceptional sets. Finally, Section 6 contains the conclusion of
the proof.

##  2\. Theorem 1.5 $\Rightarrow$ Theorem 1.2

The reduction of Theorem 1.2 to Theorem 1.5 is fairly standard. Let
$\mathfrak{g}$ be a Lie algebra of $G$, $\mathfrak{g}_{\mathbb{C}}$ its
complexification, and for $\lambda\in\mathbb{C}$, let $E_{\lambda}$ be the
eigenspace of ${\operatorname{Ad}}\,g_{1}$ corresponding to $\lambda$. Let
$\mathfrak{h}$, $\mathfrak{{h^{0}}}$, $\mathfrak{{h^{-}}}$ be the subalgebras
of $\mathfrak{g}$ with complexifications:

${\mathfrak{h}_{\mathbb{C}}}=\operatorname{span}({E_{\lambda}}:\left|\lambda\right|>1),\
\mathfrak{h}_{\mathbb{C}}^{0}=\operatorname{span}({E_{\lambda}}:\left|\lambda\right|=1),\
\mathfrak{h}_{\mathbb{C}}^{-}=\operatorname{span}({E_{\lambda}}:\left|\lambda\right|<1).$

Let $H$, ${H^{0}}$, ${H^{-}}$ be the corresponding subgroups of $G$. Note that
$H$ is precisely the unstable horospherical subgroup with respect to $F^{+}$
(defined in (1.9)) and $H^{-}$ is the stable horospherical subgroup defined
by:

${H^{-}}=\\{h\in G:{g_{t}}h{g_{-t}}\to e\,\,\,as\,\,t\to+\infty\\}.$

Since ${\operatorname{Ad}}\,g_{1}$ is assumed to be diagonalizable over
$\mathbb{C}$, $\mathfrak{g}$ is the direct sum of $\mathfrak{h}$,
$\mathfrak{{h^{0}}}$ and $\mathfrak{{h^{-}}}$. Therefore $G$ is locally (at a
neighborhood of identity) a direct product of the subgroups $H$, ${H^{0}}$ and
${H^{-}}$.

Denote the group ${H^{-}}{H^{0}}$ by $\tilde{H}$, and fix ${0<\rho<1}$ with
the following properties:

$\text{the multiplication map }\tilde{H}\times H\to G\text{ is one to one on
}B^{{\tilde{H}}}(\rho)\times{B^{H}}(\rho),$ (2.1)

and

${g_{t}B^{\tilde{H}}(r)g_{-t}\subset B^{\tilde{H}}(2r)\text{ for any
$0<r\leq\rho$ and }t\geq 0}$ (2.2)

(the latter can be done since $F$ is ${\operatorname{Ad}}$-diagonalizable and
the restriction of the map $g\to g_{t}gg_{-t}$, $t>0$, to the subgroup
$\tilde{P}$ is non-expanding).

###### Proof of Theorem 1.2 assuming Theorem 1.5.

Let $\rho$ be as in (2.1), (2.2) and define

$r_{1}:=\min(\rho,{r_{2}}).$

For any $0<r<r_{1}$ choose $s$ such that

${{B^{G}}(s)\subset B^{{\tilde{H}}}(r/4){B^{H}}(r/4).}$ (2.3)

Now take $O\subset X$, and for $x\in X$ denote

${{{E_{\delta,x,s}}:=}\,\left\\{g\in{B^{G}}(s):gx\in
E_{\delta}(F^{+},O)\right\\}.}$ (2.4)

In view of the countable stability of Hausdorff dimension, in order to prove
the theorem it suffices to show that for any $x\in X$,

${\operatorname{codim}E_{\delta,x,s}\gg\frac{{\mu(\sigma_{r}O)\cdot\phi\big{(}\mu(\sigma_{r}O),\sqrt{1-\delta}\big{)}}}{\log\frac{1}{r}}}$
(2.5)

Indeed, $E_{\delta}(F^{+},O)$ can be covered by countably many sets
$\\{gx:g\in E_{\delta,x,s}\\}$, with the quotient maps $\pi_{x}:B^{G}(s)\to X$
being Lipschitz and one-to-one. Since every ${g\in B(s)}$ can be written as
$g={\tilde{h}}h$, where ${\tilde{h}}\in{B^{\tilde{H}}}(r/4)$ and
$h\in{B^{H}}(r/4)$, for any $y\in X$ we can write

$\displaystyle{\operatorname{dist}}({g_{t}}gx,y)$
$\displaystyle\leq{\operatorname{dist}}({g_{t}}{\tilde{h}}hx,{g_{t}}hx)+{\operatorname{dist}}({g_{t}}hx,y)$
(2.6)
$\displaystyle={\operatorname{dist}}\big{(}g_{t}{\tilde{h}}g_{-t}{g_{t}}hx,{g_{t}}hx\big{)}+{\operatorname{dist}}({g_{t}}hx,y).$

Hence in view of (2.2) and (2.3), $g\in{E_{\delta,x,s}}$ implies that $h{x}$
belongs to $E_{\delta}({F^{+}},{\sigma_{{r/2}}}O)$, and by using Wegmann’s
Product Theorem [15] we conclude that:

${\begin{split}\dim{E_{\delta,x,s}}&\leq{\dim}\left(\\{h\in{B^{H}}(r/4):hx\in
E_{\delta}({F^{+}},{\sigma_{r/2}}O)\\}\times{B^{\tilde{H}}(r/4)}\right)\\\
&\leq{\dim}\big{(}\\{h\in{B^{H}}(r/4):hx\in
E_{\delta}({F^{+}},{\sigma_{r/2}}O)\\}\big{)}+\dim{\tilde{H}}.\end{split}}$
(2.7)

Since $(X,F^{+})$ is exponentially mixing, by [9, Theorem 2.6] $H$ has (EEP)
with respect to $(X,F^{+})$. Therefore, by Theorem 1.5 applied to $O$ replaced
by $\sigma_{r/2}O$ and $r$ replaced with $r/4$ we have for any $0<r<r_{1}$

${\begin{split}&\operatorname{codim}\\{h\in{B^{H}}(r/4):hx\in
E_{\delta}({F^{+}},{\sigma_{r/2}}O)\\}\\\
&\gg\frac{{\mu(\sigma_{r/4}\sigma_{r/2}O)\cdot\phi\big{(}\mu(\sigma_{r/4}\sigma_{r/2}O),\sqrt{1-\delta}\big{)}}}{\log\frac{4}{r}}\\\
&\gg\frac{{\mu(\sigma_{r}O)\cdot\phi\big{(}\mu(\sigma_{r}O),\sqrt{1-\delta}\big{)}}}{\log\frac{4}{r}}\gg\frac{{\mu(\sigma_{r}O)\cdot\phi\big{(}\mu(\sigma_{r}O),\sqrt{1-\delta}\big{)}}}{\log\frac{1}{r}}.\end{split}}$
(2.8)

Now from (2.7) and (2.8) we conclude that (2.5) is satisfied, which finishes
the proof. ∎

##  3\. Auxillary facts

###  3.1. Hausdorff dimension of limsup sets

The exceptional sets we study in this paper are of the form
$A=\limsup\limits_{N\rightarrow\infty}A_{N}$, that is

$A=\bigcap\limits_{N\geq 1}\bigcup\limits_{n\geq N}A_{n}$

for a sequence of subsets $A_{N}$.

First, we recall the definition of the Hausdorff dimension. Let $A$ be a
subset of a metric space $Y$. For any $\rho,\beta>0$, we define

${\mathcal{H}}_{\rho}^{\beta}(A)=\inf\left\\{\sum_{I\in\mathcal{U}}\operatorname{diam}(I)^{\beta}:\mathcal{U}\text{
is a cover of A by balls of diameter }<\rho\right\\}.$

Then, the $\beta$-dimensional Hausdorff measure of $A$ is defined to be

${\mathcal{H}}^{\beta}(A)=\lim_{\rho\rightarrow
0}{\mathcal{H}}_{\rho}^{\beta}(A).$

######  Definition 3.1.

The Hausdorff dimension of a subset $A$ of a metric space $Y$ is equal to

$\dim(A)=\inf\left\\{\beta\geq
0:{\mathcal{H}}^{\beta}(A)=0\right\\}=\sup\left\\{\beta\geq
0:{\mathcal{H}}^{\beta}(A)=\infty\right\\}.$

######  Lemma 3.2.

Let $\left\\{A_{N}\right\\}_{N\geq 1}$ be a collection of subsets of $Y$.
Suppose there exist constants $C>0$, $0<\rho<1$, $N_{0}\in{\mathbb{N}}$, and a
sequence $\\{\alpha_{N}\\}_{N\geq 1}$ such that for each $N\geq N_{0}$, the
set $A_{N}$ can be covered with at most $\rho^{-\alpha_{N}N}$ balls of radius
$C\rho^{N}$. Then

$\dim\left(\limsup\limits_{N\rightarrow\infty}A_{N}\right)\leq\liminf\limits_{N\rightarrow\infty}\alpha_{N}.$

###### Proof.

Let $A:=\limsup\limits_{N\to\infty}A_{N}$ and
$\alpha:=\liminf\limits_{N\to\infty}\alpha_{N}$; without loss of generality we
can assume that $\alpha<\infty$ and $\alpha_{N}\to\alpha$ as $N\to\infty$.
Take $\beta>\alpha$; we will show that ${\mathcal{H}}^{\beta}(A)=0$, which
will imply the lemma. For any ${{\xi}}\in(0,1)$, let ${N_{\xi}\geq{N_{0}}}$ be
a natural number such that $\rho^{-N}<{{\xi}}$ and
$|\alpha_{N}-\alpha|<\frac{\beta-\alpha}{2}$ for all $N\geq{N_{\xi}}$. Notice
that ${N_{\xi}}$ tends to infinity as ${{\xi}}$ goes to $0$. Take $N\geq
N_{\xi}$ and denote by $\mathcal{O}_{N}$ a cover of the set $A_{N}$ by balls
of radius ${C}\rho^{N}$ such that $\\#\mathcal{O}_{N}$, the number of balls in
the cover $\mathcal{O}_{N}$, is at most ${\rho^{-{\alpha_{N}}N}}$. Then
$\mathcal{O}=\bigcup_{N\geq{N_{\xi}}}\mathcal{O}_{N}$ is a cover of $A$ for
which the following holds:

$\displaystyle\sum_{B\in\mathcal{O}}\operatorname{diam}(B)^{\beta}$
$\displaystyle=\sum_{N\geq{N_{\xi}}}\sum_{B\in\mathcal{O}_{N}}\operatorname{diam}(B)^{\beta}\leq(2C)^{\beta}\sum_{N\geq{N_{\xi}}}\\#\mathcal{O}_{N}\cdot\rho^{\beta
N}$
$\displaystyle\leq(2C)^{\beta}\sum_{N\geq{N_{\xi}}}\rho^{\left(\beta-\alpha_{N}\right)N}\leq(2C)^{\beta}\sum_{N\geq{N_{\xi}}}\rho^{\frac{\beta-\alpha}{2}N}$
$\displaystyle\leq(2C)^{\beta}\frac{\rho^{\frac{\beta-\alpha}{2}{N_{\xi}}}}{1-\rho^{\frac{\beta-\alpha}{2}}}\xrightarrow{{{\xi}}\rightarrow
0}0.$

This implies that ${\mathcal{H}}^{\beta}(A)=0$, and the conclusion of the
lemma follows. ∎

###  3.2. Choosing $r_{2}$

Recall that as part of the proof of Theorem 1.5 we need to define a bound
$r_{2}$ for possible values of $r$. This bound will come from two ingredients.
Namely, we define

${r_{2}:=\frac{1}{2}\min(r_{0},r^{\prime}),}$ (3.1)

where

  * •

$0<r^{\prime}<1/4$ is chosen so that for any Lie subalgebra $\mathfrak{p}$ of
$\mathfrak{g}$ the exponential map from $\mathfrak{p}$ to
$P=\exp(\mathfrak{p})$ is $2$-bi-Lipischitz on $B^{\mathfrak{p}}(r^{\prime})$;
in particular, we will have

${B^{P}(2r)\supset\exp\big{(}B^{\mathfrak{p}}(r)\big{)}\supset
B^{P}(r/2)\text{ for any }0<r\leq r^{\prime}.}$ (3.2)

  * •

${r_{0}:=r_{0}(X)=\inf\\{r_{0}(x):x\in X\\}>0,}$ where

${r_{0}(x):=}\,\sup\\{r>0:\text{the map }\pi_{x}:g\mapsto gx\text{ is
injective on }B(r)\\}.$

(the injectivity radius at $x_{0}$).

###  3.3. Tessellations of $P$

Now let $P$ be a connected subgroup of $H$ normalized by $F^{+}$. Following
[7], say that an open subset $V$ of $P$ is a tessellation domain for $P$
relative to a countable subset $\Lambda$ of $P$ if

  * •

$\nu(\partial V)=0$;

  * •

$V\gamma_{1}\cap V\gamma_{2}=\varnothing$ for different
$\gamma_{1},\gamma_{2}\in\Lambda$;

  * •

$P=\bigcup\limits_{\gamma\in\Lambda}{\overline{V}\gamma}.$

Note that $P$ is a connected simply connected nilpotent Lie group. Denote
$\mathfrak{p}:=\operatorname{Lie}(P)$ and $L:=\dim P$, and fix a Haar measure
$\nu$ on $P$. As shown in [7, Proposition 3.3], one can choose a basis of
$\mathfrak{p}$ such that for any $r>0$, $\exp\left(rI_{\mathfrak{p}}\right)$,
where $I_{\mathfrak{p}}\subset\mathfrak{p}$ is the cube centered at $0$ with
side length $1$ with respect to that basis, is a tessellation domain. Let us
denote

${V_{r}:=\exp\left({{\frac{r}{4\sqrt{L}}}}{I_{\mathfrak{p}}}\right)}$ (3.3)

and choose a countable $\Lambda_{r}\subset P$ such that $V_{r}$ is a
tessellation domain relative to $\Lambda_{r}$. Then it follows from (3.2) that
for any $0<r\leq r^{\prime}$ one has

${{B^{P}}\Big{(}\frac{r}{{16\sqrt{L}}}\Big{)}\subset{V_{r}}\subset{B^{P}}\left(\frac{r}{4}\right).}$
(3.4)

###  3.4. Bowen boxes

Note that the measure $\nu$ and the pushforward of the Lebesgue measure
$\operatorname{Leb}$ on $\mathfrak{p}$ by the exponential map are absolutely
continuous with respect to each other with locally bounded Radon–Nikodym
derivative. This implies that there exists $0<c_{1}<c_{2}$ such that

${c_{1}\operatorname{Leb}(A)\leq\nu\big{(}\exp(A)\big{)}\leq
c_{2}\operatorname{Leb}(A)\quad\forall\,\text{measurable }A\subset
B^{\mathfrak{p}}(1).}$ (3.5)

Define

${{{\lambda_{\min}}}:=\min\\{|\lambda|:\,\lambda\text{ is an eigenvalue of
}{\operatorname{ad}}_{{g_{1}}}|_{\mathfrak{p}}\\}}$ (3.6)

and

${{{\lambda_{\max}}}:=\max\\{|\lambda|:\,\lambda\text{ is an eigenvalue of
}{\operatorname{ad}}_{{g_{1}}}|_{\mathfrak{p}}\\}.}$ (3.7)

Using the bi-Lipschitz property of $\exp$, we can conclude that for any
$0<r\leq r^{\prime}$ and any $t>0$ one has

${\operatorname{diam}(g_{-t}V_{r}g_{t})<2re^{-{{\lambda_{\min}}}t}.}$ (3.8)

Also let
$\eta:=\operatorname{Tr}{\operatorname{ad}}_{{g_{1}}}|_{\mathfrak{p}}$;
clearly one then has

${{\nu(g_{-t}Ag_{t})=e^{-\eta t}\nu(A)\text{ for any measurable }A\subset
P.}}$ (3.9)

Let us now define a Bowen $(t,r)$-box in $P$ to be a set of the form
$g_{-t}V_{r}\gamma g_{t}$ for some $\gamma\in P$ and $t>0$. Our approach to
estimating Hausdorff dimension of various subsets of $P$ will be through
covering them by Bowen boxes. We are going to need three results proved in
[11]. The first one, a slight modification of [7, Proposition 3.4], gives an
upper bound for the number of $\gamma\in\Lambda_{r}$ such that the Bowen box
$g_{-t}V_{r}\gamma g_{t}$ has non-empty intersection with $V_{r}$:

######  Lemma 3.3.

[11, Lemma 4.1]There exists $c_{0}>0$ such that for any $0<r\leq r^{\prime}$
and for any $t>\frac{\log 8}{{{\lambda_{\min}}}}$

$\\#\\{\gamma\in\Lambda_{r}:{g_{-t}}{\overline{V_{r}}\gamma}{g_{t}}\cap{V_{r}}\neq\varnothing\\}\leq
e^{\eta t}\left(1+c_{0}e^{-{{\lambda_{\min}}}t}\right).$

The second one gives us an upper bound for the number of balls of radius
$re^{-{{\lambda_{\max}}}t}$ needed to cover a Bowen box.

######  Lemma 3.4.

[11, Lemma 7.4] There exists $C_{1}>0$ such that for any $0<r<1$ and any
$t>0$, any Bowen $(t,r)$-box in $P$ can be covered with at most
$C_{1}e^{({{\lambda_{\max}}}L-\eta)t}$ balls in $P$ of radius
$re^{-{{\lambda_{\max}}}t}$.

The third result is a direct consequence of property (EEP); it is a simplified
version of [11, Proposition 4.4].

######  Proposition 3.5.

Let ${F^{+}}$ be a one-parameter subsemigroup of $G$ and $P$ a subgroup of $G$
with property (EEP) with respect to $F^{+}$. Then there exist $t_{1}\geq 1$
and ${\lambda^{\prime}>0}$ such that for any open $O\subset X$, any $x\in X$,
any $r\leq r_{2}$ and any $t\geq t_{1}$ one has

${{\mathop{\nu}\big{(}\\{h\in V_{r}:g_{t}hx\in
O\\}\big{)}\geq\nu\left(V_{r}\right)\mu({\sigma_{e^{-{\lambda^{\prime}}t}}}O)-{e^{-{{\lambda^{\prime}}t}}}.}}$

##  4\. Effective equidistribution of translates and a measure estimate

From now on we will work with $F^{+}$ and $P$ as in Theorem 1.5, and for the
rest of the paper fix a positive $r\leq r_{2}$, where $r_{2}$ is as in (3.1).
Note that by the countable stability of Hausdorff dimension, in order to prove
Theorem 1.5 it suffices, for a subset $O$ of $X$ and $0<\delta<1$, to get a
uniform (in $x\in X$) upper bound for the Hausdorff dimension of the set

$\displaystyle{S_{x,\delta}(O)}$ $\displaystyle:=\\{h\in V_{r}:hx\in
E_{\delta}(F^{+},O)\\}$ (4.1)
$\displaystyle=\left\\{h\in{V_{r}}:\limsup_{T\rightarrow\infty}\frac{1}{T}\int_{0}^{T}1_{O^{c}}(g_{t}hx)\,dt\geq\delta\right\\}.$

For this it will be convenient to discretize the above definition. Namely let
us introduce the following notation: given $T>0$, a subset $S$ of $X$, $x\in
X$ and $0<\delta<1$, let us define

${A_{x,\delta}(T,S):=\left\\{h\in
V_{r}:\frac{1}{T}\int_{0}^{T}1_{S}(g_{t}hx)\,dt\geq\delta\right\\}.}$ (4.2)

In the following proposition we find the relation between the set
$S_{x,\delta}(O)$ and the family of sets
$\\{A_{x,\delta}(NT,O^{c})\\}_{N\in{\mathbb{N}}}$.

######  Proposition 4.1.

For any $T>0$ and any $x\in X$ and we have

${S_{x,\delta}(O)=\limsup_{N\in{\mathbb{N}},\,N\rightarrow\infty}A_{x,\delta}(NT,O^{c})}$

###### Proof.

In view of definition of $S_{x,\delta}(O)$, it suffices, for a fixed $T>0$, to
prove that

$\displaystyle\limsup_{R\rightarrow\infty}\frac{1}{R}\int_{0}^{R}1_{O^{c}}(g_{t}hx)\,dt$
$\displaystyle=\limsup_{N\in{\mathbb{N}},\,N\rightarrow\infty}\frac{1}{NT}\int_{0}^{NT}1_{O^{c}}(g_{t}hx)\,dt$
$\displaystyle=\lim_{N_{0}\rightarrow\infty}\sup_{N\geq
N_{0}}\frac{1}{NT}\int_{0}^{NT}1_{O^{c}}(g_{t}hx)\,dt.$

Let $N_{0}\in{\mathbb{N}}$, and let $R\geq N_{0}T$. Then one can find $N\geq
N_{0}$ and $0\leq R^{\prime}<T$ such that $R=NT+R^{\prime}$. Hence

$\displaystyle\frac{1}{R}\int_{0}^{R}1_{O^{c}}(g_{t}hx)\,dt=$
$\displaystyle\frac{1}{NT+R^{\prime}}\int_{0}^{NT+R^{\prime}}1_{O^{c}}(g_{t}hx)\,dt$
$\displaystyle\leq$
$\displaystyle\frac{1}{NT}\int_{0}^{NT+R^{\prime}}1_{O^{c}}(g_{t}hx)\,dt$
$\displaystyle=$
$\displaystyle\frac{1}{NT}\left(\int_{0}^{NT}1_{O^{c}}(g_{t}hx)\,dt+\int_{NT}^{NT+R^{\prime}}1_{O^{c}}(g_{t}hx)\,dt\right)$
$\displaystyle\underset{(1_{O^{c}}\leq 1,\,R^{\prime}\leq T)}{\leq}$
$\displaystyle\frac{1}{NT}\int_{0}^{NT}1_{O^{c}}(g_{t}hx)\,dt+\frac{1}{N}$
$\displaystyle\underset{(N\geq N_{0})}{\leq}$
$\displaystyle\frac{1}{NT}\int_{0}^{NT}1_{O^{c}}(g_{t}hx)\,dt+\frac{1}{N_{0}}.$

Therefore, we get

$\limsup_{R\rightarrow\infty}\frac{1}{R}\int_{0}^{R}1_{O^{c}}(g_{t}hx)\,dt\leq\lim_{N_{0}\rightarrow\infty}\underset{N\geq
N_{0}}{\sup}\frac{1}{NT}\int_{0}^{NT}1_{O^{c}}(g_{t}hx)\,dt.$

The reverse inequality is obvious. ∎

The next proposition gives an upper estimate for the measure of
$A_{x,{\delta}}(T,O^{c})$. We will use it in §5 to obtain an upper bound for
the number of Bowen $(r,T)$-boxes in $P$ needed to cover this set (see
Corollary 5.2).

######  Proposition 4.2.

For all $x\in X$, $0<\varepsilon<1$, for any open $O\subset X$ and for all

${T>T_{r}:=\max\left(t_{1},\,\frac{1}{\lambda^{\prime}}\log\frac{2}{r},\,\frac{1}{\lambda^{\prime}}\log\frac{(4\sqrt{L})^{L}}{c_{1}\lambda^{\prime}r^{L}}{,\frac{\log
8}{{{\lambda_{\min}}}}}\right),}$ (4.3)

where $c_{1}$ is as in (3.5) and $t_{1},\lambda^{\prime}$ are as in
Proposition 3.5, one has

$\displaystyle\nu\big{(}A_{x,1-\varepsilon}(T,O)\big{)}\geq\nu\left(V_{r}\right)\left(1-{\frac{1}{\varepsilon}}\Big{(}1-\mu({\sigma_{r/2}}O)+\frac{{T_{r}+1}}{T}\Big{)}\right).$
(4.4)

###### Proof.

Let $x,\varepsilon,O$ and $T$ be as above. Then by definition we have:

$\displaystyle\nu\big{(}A_{x,\,1-\varepsilon}(T,O)\big{)}$
$\displaystyle=\nu\left(\left\\{h\in
V_{r}:\frac{1}{T}\int_{0}^{T}1_{{O}}(g_{t}hx)\,dt\geq
1-\varepsilon\right\\}\right)$ (4.5)
$\displaystyle=\nu\left(V_{r}\right)-\nu\left(\left\\{h\in
V_{r}:\frac{1}{T}\int_{0}^{T}1_{{O^{c}}}(g_{t}hx)\,dt\,{>}\,\varepsilon\right\\}\right)$
$\displaystyle{\geq\nu\left(V_{r}\right)-\nu\big{(}A_{x,{\varepsilon}}(T,O^{c})\big{)}}.$

Our goal is to estimate the right-hand side of (4.5) from below. We have:

$\displaystyle\nu\big{(}A_{x,\varepsilon}(T,O^{c})\big{)}=$
$\displaystyle\nu\left(\left\\{h\in
V_{r}:\frac{1}{T}\int_{0}^{T}1_{{O^{c}}}(g_{t}hx)\,dt\geq\varepsilon\right\\}\right)$
(4.6) $\displaystyle\underset{\text{(Markov's inequality) }}{\leq}$
$\displaystyle{\frac{1}{\varepsilon
T}}\int_{0}^{T}\int_{V_{r}}1_{O^{c}}(g_{t}hx)\,d\nu(h)\,dt$ $\displaystyle=$
$\displaystyle{\frac{1}{\varepsilon T}}\int_{0}^{T}\nu\left(\left\\{h\in
V_{r}:g_{t}hx\in O^{c}\right\\}\right)dt$ $\displaystyle=$
$\displaystyle{\frac{1}{\varepsilon
T}}\left(\int_{0}^{T_{r}}\nu\left(\left\\{h\in V_{r}:g_{t}hx\in
O^{c}\right\\}\right)dt\right.$
$\displaystyle\qquad\qquad+\left.\int_{T_{r}}^{T}\nu\left(\left\\{h\in
V_{r}:g_{t}hx\in O^{c}\right\\}\right)dt\right).$

Note that

${{\int_{0}^{T_{r}}\nu\left(\left\\{h\in V_{r}:g_{t}hx\in
O^{c}\right\\}\right)dt\leq T_{r}\cdot\nu\left(V_{r}\right),}}$ (4.7)

and, since $T_{r}\geq t_{1}$, by applying Proposition 3.5 we get

$\displaystyle\int_{T_{r}}^{T}\nu\left(\left\\{h\in V_{r}:g_{t}hx\in
O^{c}\right\\}\right)\,dt$ (4.8) $\displaystyle=$
$\displaystyle\int_{T_{r}}^{T}\big{(}\nu(V)-\nu\left(\left\\{h\in
V_{r}:g_{t}hx\in O\right\\}\right)\big{)}\,dt$ $\displaystyle\leq$
$\displaystyle\int_{T_{r}}^{T}\left(\nu\left({V_{r}}\right)\left(1-\mu({\sigma_{e^{-\lambda^{\prime}T_{r}}}}O)\right)+{e^{-\lambda^{\prime}t}}\right)\,dt$
$\displaystyle\leq$ $\displaystyle\
T\cdot\nu\left(V_{r}\right)\left(1-\mu({\sigma_{e^{-\lambda^{\prime}T_{r}}}}O)\right)+\frac{e^{-\lambda^{\prime}T_{r}}}{\lambda^{\prime}}$
$\displaystyle\underset{\eqref{eq:Tr}}{\leq}$ $\displaystyle\
{T\cdot\nu\left(V_{r}\right)\left(1-\mu({\sigma_{r/2}}O)\right)+\frac{e^{-\lambda^{\prime}T_{r}}}{\lambda^{\prime}}}.$

It remains to observe that $\eqref{eq:Tr}$, in combination with (3.3) and
(3.5), also implies that
$\frac{e^{-\lambda^{\prime}T_{r}}}{\lambda^{\prime}}\leq\nu(V_{r})$. Hence
(4.4) follows from (4.5), (4.6), (4.7) and (4.8). ∎

##  5\. A covering result

In this section we will prove a covering result for the sets of the form
$A_{x,\delta}(NT,O^{c})$. Then, by using Proposition 4.1 and Lemma 3.2, in the
next section we will obtain an upper estimate for the Hausdorff dimension of
${S_{x,\delta}(O)}$.

We start with the following lemma:

######  Lemma 5.1.

Let $O$ be an open subset of $X$, and let $0<\varepsilon<1$. Then for any
${T>0}$, $\gamma\in\Lambda_{r}$, $x\in X$, any $0<\alpha<\varepsilon$ and for
any Bowen $(r,T)$-box $B={g_{-T}}{V_{r}\gamma}{g_{T}}$ which has non-empty
intersection with the set $A_{x,1-\alpha}(T,\sigma_{4r}O)$, we have

$B\cap\,A_{x,\varepsilon}(T,O^{c})=\varnothing.$

###### Proof.

Let $O$ be an open subset of $X$ and let $\gamma\in\Lambda_{r}$. Consider the
Bowen $(r,T)$-box $B={g_{-T}}{V_{r}\gamma}{g_{T}}$. Let $x\in X$, take $p\in
B$, and assume that $g_{t}px\in\sigma_{4r}O$ for some $0\leq t\leq T$. Any
$p^{\prime}\in B$ is of the form $p^{\prime}=hp$ where
$h\in{g_{-T}}({V_{r}\cdot V_{r}}){g_{T}}$. Thus we have

$\displaystyle g_{t}p^{\prime}x=g_{t}hg_{-t}g_{t}px$ $\displaystyle\in
g_{-(T-t)}({V_{r}\cdot V_{r}})g_{(T-t)}g_{t}px$
$\displaystyle{\underset{\eqref{eq:diam}}{\in}B^{G}(2re^{-{{\lambda_{\min}}}(T-t)})\cdot
B^{G}(2re^{-{{\lambda_{\min}}}(T-t)})g_{t}px}$ $\displaystyle{\,\,\in
B^{G}(4r)g_{t}px}$

which, in view of (3.4), implies that
$\operatorname{dist}(g_{t}p^{\prime}x,g_{t}px)\leq{4r}$. Hence
$g_{t}p^{\prime}x\in O$. Now assume in addition that $0<\alpha<\varepsilon<1$
and $p\in A_{x,1-\alpha}(T,\sigma_{4r}O)$; then

$\displaystyle\frac{1}{T}\int_{0}^{T}1_{O^{c}}(g_{t}p^{\prime}x)\,dt$
$\displaystyle=1-\frac{1}{T}\int_{0}^{T}1_{O}(g_{t}p^{\prime}x)\,dt$
$\displaystyle\leq
1-\frac{1}{T}\int_{0}^{T}{1_{\sigma_{4r}O}(g_{t}px)}\,dt\leq
1-(1-\alpha)=\alpha<\varepsilon.$

Therefore, if $B$ has non-empty intersection with
$A_{x,1-\alpha}(T,\sigma_{4r}O)$, then for any $p^{\prime}\in B$ we have
$p^{\prime}\notin A_{x,\varepsilon}(T,O^{c})$. This ends the proof. ∎

Now, by combining the previous lemma with Lemma 3.3 and Proposition 4.2 we
obtain the following corollary which is a covering result for the sets of type
$A_{x,\varepsilon}(T,O^{c})$:

######  Corollary 5.2.

Let $T_{r}$ be as in (4.3). Then for any $0<\varepsilon<1$, any $T>T_{r}$, any
$x\in X$, and for any open subset $O$ of $X$, the set
$A_{x,\varepsilon}(T,O^{c})$ can be covered with at most ${\frac{e^{\eta
T}}{\varepsilon}C(T,O)}$ Bowen $(T,r)$-boxes in $P$, where

${{C(T,O):=1-{\mu({\sigma_{5r}}O)}+\frac{T_{r}+1}{T}+c_{0}e^{-{{\lambda_{\min}}}T}.}}$
(5.1)

###### Proof.

Let $0<\varepsilon<1$, $0<\alpha<\varepsilon$, $T>T_{r}$, $x\in X$, and let
$O$ be an open subset of $X$. Then we have:

$\displaystyle\ \\#\\{\gamma\in\Lambda_{r}:g_{-T}V_{r}\gamma
g_{T}\,\cap\,A_{x,\varepsilon}(T,O^{c})\neq\varnothing\\}$
$\displaystyle\underset{\text{Lemma }\ref{covering of A^P}}{\leq}$
$\displaystyle\ \\#\\{\gamma\in\Lambda_{r}:g_{-T}V_{r}\gamma
g_{T}\,\cap\,V_{r}\neq\varnothing\\}-\\#\\{\gamma\in\Lambda_{r}:g_{-T}V_{r}\gamma
g_{T}\,\subset\,A_{x,1-\alpha}(T,\sigma_{4r}O)\\}$
$\displaystyle\underset{\text{Lemma }\ref{covering}}{\leq}$ $\displaystyle\
e^{\eta
T}\left(1+c_{0}e^{-{{\lambda_{\min}}}T}\right)-\\#\\{\gamma\in\Lambda_{r}:g_{-T}V_{r}\gamma
g_{T}\,\subset\,A_{x,1-\alpha}(T,\sigma_{4r}O)\\}$ $\displaystyle{\leq}$
$\displaystyle\ e^{\eta
T}\left(1+c_{0}e^{-{{\lambda_{\min}}}T}\right)-\frac{\nu\left(A_{x,1-\alpha}(T,\sigma_{4r}O)\right)}{\nu({g_{-T}}V_{r}{g_{T}})}$
$\displaystyle\underset{\text{Proposition }\ref{exponential mixing1}}{\leq}$
$\displaystyle\ e^{\eta T}\left(1+c_{0}e^{-{{\lambda_{\min}}}T}\right)-e^{\eta
t}\left(1-\alpha^{-1}\cdot\left(1-\mu(\sigma_{r/2}{\sigma_{4r}}O)+{\frac{T_{r}+1}{T}}\right)\right)$
$\displaystyle\underset{\eqref{eq:ctoe}}{<}$ $\displaystyle\ {\frac{e^{\eta
T}}{\alpha}C(T,O)}.$

Now since $0<\alpha<\varepsilon$ was arbitrary, by letting $\alpha$ approach
$\varepsilon$, we get that $A_{x,\varepsilon}(T,O^{c})$ can be covered with at
most ${\frac{e^{\eta T}}{\varepsilon}C(T,O)}$ Bowen $(T,r)$-boxes in $P$, as
desired. ∎

Next we will need a generalized version of the definition (4.2) of sets
$A_{x,\delta}(T,S)$. Namely, given $S\subset X$, $x\in X$, $T>0$, $0<\delta<1$
and $J\subset{\mathbb{N}}$, let us define

${A_{x,\,\delta}(T,S,J):=\left\\{h\in
V_{r}:\frac{1}{T}\int_{(i-1)T}^{iT}1_{S}(g_{t}hx)\,dt\geq\delta\,\,\,\,\,\forall\,i\in
J\right\\}.}$ (5.2)

Clearly $A_{x,\delta}(T,S)=A_{x,\,\delta}(T,S,\\{1\\})$. Using the above
corollary inductively, in the following proposition we obtain a covering
result for the sets of the form (5.2).

######  Proposition 5.3.

Let $O$ be a non-empty open subset of $X$, and let $T_{r}$ be as in (4.3).
Then for all $0<\varepsilon<1$, $T>T_{r}$, $N\in{\mathbb{Z}}_{+}$,
$J\subset\\{1,\dots,N\\}$, and for all $x\in X$, the set
$A_{x,\varepsilon}(T,O^{c},J)$ can be covered with at most

${e^{\eta
NT}{{{\left(\frac{C(T,O)}{\varepsilon}\right)^{|J|}}}\left(1+c_{0}e^{-{{\lambda_{\min}}}t}\right)^{N-|J|}}}$
(5.3)

Bowen $(NT,r)$-boxes in $P$.

###### Proof.

Let $0<\varepsilon<1$, let $T>T_{r}$, and let $x\in X$. We argue by induction
on $N$; the basis is given by $N=0$ and $J=\varnothing$, which makes the
quantity (5.3) equal to $1$. This makes sense, since
$A_{x,\varepsilon}(T,O^{c},J)=V_{r}$, which is precisely a $(0,r)$-box.

Now take an arbitrary $N\in{\mathbb{N}}$ and let
$J^{\prime}:=J\smallsetminus\\{N\\}$. By the induction assumption, the set
$A_{x,\varepsilon}\big{(}(N-1)T,O^{c},J^{\prime}\big{)}$ can be covered with
at most

${e^{\eta(N-1)T}\cdot{\left(\frac{C(T,O)}{\varepsilon}\right)^{|J^{\prime}|}}\left(1+c_{0}e^{-{{\lambda_{\min}}}t}\right)^{N-1-|J^{\prime}|}}$
(5.4)

Bowen $\big{(}(N-1)T,r\big{)}$-boxes in $P$. Now let $g_{-(N-1)T}V_{r}\gamma
g_{(N-1)T}$ be one of the Bowen $\big{(}(N-1)T,r\big{)}$-boxes in the above
cover which has non-empty intersection with
$A_{x,\varepsilon}\big{(}(N-1)T,O^{c},J^{\prime}\big{)}$. Take any
$q={g_{-(N-1)T}}{h}\gamma{g_{(N-1)T}}\in g_{-(N-1)T}V_{r}\gamma g_{(N-1)T}$,
and consider two cases.

  * •

If $N\in J$, so that $|J^{\prime}|=|J|-1$ and $N-1-|J^{\prime}|=N-|J|$, write

$\displaystyle\frac{1}{T}\int_{(N-1)T}^{NT}1_{O^{c}}(g_{t}qx)\,dt$
$\displaystyle=\frac{1}{T}\int_{(N-1)T}^{NT}1_{O^{c}}\big{(}g_{t}({g_{-(N-1)T}}{h}\gamma{g_{(N-1)T}})x\big{)}\,dt$
$\displaystyle=\frac{1}{T}\int_{0}^{T}1_{O^{c}}\big{(}g_{t}h(\gamma
g_{(N-1)T}x)\big{)}\,dt.$

Consequently,

$\displaystyle\left\\{q\in g_{-(N-1)T}V_{r}\gamma
g_{(N-1)T}:\frac{1}{T}\int_{(N-1)T}^{NT}1_{O^{c}}(g_{t}qx)\,dt\geq\varepsilon\right\\}$
(5.5) $\displaystyle=g_{(N-1)T}\left\\{h\in
V_{r}:\frac{1}{T}\int_{0}^{T}1_{O^{c}}\big{(}g_{t}h(\gamma
g_{(N-1)T}x)\big{)}\,dt\geq\varepsilon\right\\}\gamma g_{(N-1)T}$
$\displaystyle=g_{(N-1)T}A_{\gamma g_{(N-1)T}x,\varepsilon}(T,r,O^{c})\gamma
g_{(N-1)T}.$

Hence, by applying Corollary 5.2 with $\gamma g_{(N-1)T}x$ in place of $x$, we
can cover the set in the left hand side of (5.5) with at most $e^{\eta
T}{\left(\frac{C(T,O)}{\varepsilon}\right)^{|J|}}$ Bowen $(NT,r)$-boxes in
$P$. Therefore the number of Bowen $(NT,r)$-boxes needed to cover
$A_{x,\varepsilon}(T,O^{c},J)$ is at most $e^{\eta
T}{\left(\frac{C(T,O)}{\varepsilon}\right)^{|J|}}$ times the quantity in
(5.3), which is precisely (5.4).

  * •

If $N\notin J$, so that $|J^{\prime}|=|J|$ and $N-1-|J^{\prime}|=N-1-|J|$, the
argument is even clearer. By Lemma  3.3, $g_{-(N-1)T}V_{r}\gamma g_{(N-1)T}$
can be covered by at most $e^{\eta
T}\left(1+c_{0}e^{-{{\lambda_{\min}}}t}\right)$ Bowen $(NT,r)$-boxes. Hence
the number of Bowen $(NT,r)$-boxes needed to cover
$A_{x,\varepsilon}(T,O^{c},J)$ is at most $e^{\eta
T}\left(1+c_{0}e^{-{{\lambda_{\min}}}t}\right)$ times the quantity in (5.3),
which again is precisely (5.4).

∎

Recall that our goal in this section is to find a covering result for the sets
of the form $A_{x,\delta}(NT,O^{c})$. The following lemma reduces this task to
a covering result for the sets of the form $A_{x,\varepsilon}(T,O^{c},J)$ for
$0<\varepsilon<\delta$ and $J\subset\\{1,\dots,N\\}$.

######  Lemma 5.4.

For any $S\subset X$, $N\in{\mathbb{N}}$, $T>0$, $x\in X$, $0<\delta<1$, and
for any $0<\varepsilon<\delta$

$A_{x,\delta}(NT,S)\subset\bigcup_{J\subset\\{1,\dots,N\\}:|J|\geq\lceil\left(1-\frac{1-\delta}{1-\varepsilon}\right)N\rceil}A_{x,\varepsilon}(T,S,J)$

.

###### Proof.

Let $N\in{\mathbb{N}}$, $r>0$, $T>0$, $x\in X$ and $0<\varepsilon<\delta<1$.
Also let $h\in A_{x,\delta}(NT,S)$, and define

$E:=\big{\\{}j\in\\{1,\dots,N\\}:h\notin
A_{x,\varepsilon}(T,S,\\{j\\})\big{\\}}.$

Then

$\displaystyle\delta$
$\displaystyle{\leq}\frac{1}{NT}\int_{0}^{NT}1_{S}(g_{t}hx)\,dt$
$\displaystyle=\frac{1}{N}\sum_{j\in
E}\frac{1}{T}\int_{(j-1)T}^{jT}1_{S}(g_{t}hx)\,dt+\frac{1}{N}\sum_{j\in\\{1,\dots,N\\}\smallsetminus
E}\frac{1}{T}\int_{(j-1)T}^{jT}1_{S}(g_{t}hx)\,dt$
$\displaystyle\leq\frac{1}{N}\cdot|E|\cdot\varepsilon+\frac{1}{N}\cdot|\\{1,\dots,N\\}\smallsetminus
E|=\frac{1}{N}\left(|E|\cdot\varepsilon+N-|E|\right).$

This implies

$|E|\leq\frac{1-\delta}{1-\varepsilon}N.$

Note that it follows immediately from the definition of $E$ that $h$ is an
element of $A_{x,\varepsilon}(T,S,\\{1,\dots,N\\}\smallsetminus E)$. Hence, in
view of the above inequality we conclude that

$h\in\bigcup_{J\subset\\{1,\dots,N\\}:|J|\geq\lceil\left(1-\frac{1-\delta}{1-\varepsilon}\right)N\rceil}A_{x,\varepsilon}(T,S,J),$

finishing the proof of the lemma. ∎

From the above lemma combined with Proposition 5.3 we get the following
crucial covering result:

######  Corollary 5.5.

Let $C_{1}$ be as in Lemma 3.4, $0<\delta<1$, $0<r\leq r_{2}$, and let $T_{r}$
be as in (4.3). Then for any $x\in X$, any $N\in{\mathbb{N}}$, any $T>T_{r}$,
and for any $0<\varepsilon<\delta$ the set $A_{x,\delta}(NT,O^{c})$ can be
covered with at most

$\displaystyle
C_{1}{e^{{{\lambda_{\max}}}LNT}}{N\choose{\lceil\left(1-\frac{1-\delta}{1-\varepsilon}\right)N}\rceil}\cdot{{\left(\frac{C(T,O)}{\varepsilon}\right)^{\lceil\left(1-\frac{1-\delta}{1-\varepsilon}\right)N\rceil}}\cdot\left(1+c_{0}e^{-{{\lambda_{\min}}}T}\right)^{{N-\lceil\left(1-\frac{1-\delta}{1-\varepsilon}\right)N}\rceil}}$
(5.6)

balls in $P$ of radius $re^{-{{\lambda_{\max}}}NT}$.

###### Proof.

Let $x\in X$, $N\in{\mathbb{N}}$, $T>T_{r}$, and let $0<\varepsilon<\delta$.
By the above lemma we have:

$A_{x,\delta}(NT,O^{c})\subset\bigcup_{J\subset\\{1,\dots,N\\}:|J|\geq\lceil\left(1-\frac{1-\delta}{1-\varepsilon}\right)N\rceil}A_{x,\varepsilon}(T,O^{c},J).$

Now note that for any $J\subset\\{1,\dots,N\\}$, if we take any subset
$J^{\prime}$ of $J$, then it follows immediately that
$A_{x,\varepsilon}(T,O^{c},J)\subset A_{x,\varepsilon}(T,O^{c},J^{\prime})$.
Therefore, the above inclusion yields the following inclusion:

$A_{x,\delta}(NT,O^{c})\subset\bigcup_{J\subset\\{1,\dots,N\\}:|J|=\lceil\left(1-\frac{1-\delta}{1-\varepsilon}\right)N\rceil}A_{x,\varepsilon}(T,O^{c},J).$

Also, by Lemma 3.4, every Bowen $(NT,r)$-boxes in $P$ can be covered with at
most $C_{1}e^{({{\lambda_{\max}}}L-\eta)NT}$ balls in $P$ of radius
$re^{-{{\lambda_{\max}}}NT}$. From this, combined with Proposition 5.3 and the
above inclusion we can conclude the proof. ∎

##  6\. Proof of Theorem 1.5

###### Proof of Theorem 1.5.

Let $O$ be an open subset of $X$, $x\in X$, and let $\delta>0$. In view of
countable stability of Hausdorff dimension, it suffices to show that for any
$0<r\leq r_{2}$, we have

$\operatorname{codim}S_{x,\delta}(O)\gg\frac{\mu({\sigma_{r}}O)\cdot{\phi\left(\mu({\sigma_{r}}O),\sqrt{1-\delta}\right)}}{\log\frac{1}{r}}$

where $S_{x,\delta}(O)$ is as in (4.1) and $\phi$ is as in (1.4). In order to
prove the above statement, it is evident that it suffices to demonstrate that
for any $0<r\leq r_{2}/5$ we have

${\operatorname{codim}S_{x,\delta}(O)\gg\frac{\mu({\sigma_{5r}}O)\cdot{\phi\left(\mu({\sigma_{5r}}O),\sqrt{1-\delta}\right)}}{\log\frac{1}{5r}}.}$
(6.1)

If $\mu({\sigma_{5r}}O)=0$, then the above statement follows immediately. So
in this proof we assume always that $\mu({\sigma_{5r}}O)>0$. We start with the
following combinatorial lemma:

######  Lemma 6.1.

Let $m={m}(n)\leq n$ be a function of $n$ such that
$\lim_{n\rightarrow\infty}\frac{m}{n}=z$ for some fixed constant $0<z<1$. Then

${n\choose m}=o(1){B\big{(}\tfrac{m}{n}\big{)}}^{n},$

where

${B(z):=\left(\frac{1}{z}\right)^{z}\left(\frac{1}{1-z}\right)^{1-z}.}$ (6.2)

###### Proof.

Note that $\lim_{n\rightarrow\infty}\frac{m}{n}=z<1$ implies that both $m$ and
$n-m$ tend to infinity as $n$ goes to infinity; moreover,
$\lim_{n\rightarrow\infty}\frac{n-m}{n}=1-z$. Hence, by using Stirling’s
approximation we have:

$\displaystyle{n\choose m}=\frac{n!}{m!(n-m)!}$
$\displaystyle=(1+o(1))\frac{\sqrt{2\pi n}(\frac{n}{e})^{n}}{\sqrt{2\pi
m}(\frac{m}{e})^{m}+\sqrt{2\pi(n-m)}(\frac{n-m}{e})^{n-m}}$
$\displaystyle=(1+o(1))\sqrt{\frac{n}{2\pi
m(n-m)}}\left(\frac{n}{m}\right)^{m}\left(\frac{n}{n-m}\right)^{n-m}$
$\displaystyle=o(1)\left(\frac{n}{m}\right)^{m}\left(\frac{n}{n-m}\right)^{n-m}$
$\displaystyle=o(1){B\big{(}\tfrac{m}{n}\big{)}}^{n},$

where the third equality above follows from the fact that

$\lim_{n\rightarrow\infty}\frac{n}{2\pi
m(n-m)}=\lim_{n\rightarrow\infty}\frac{1}{2\pi
n}\cdot\lim_{n\rightarrow\infty}\frac{n}{m}\cdot\lim_{n\rightarrow\infty}\frac{n}{n-m}=0\cdot\frac{1}{z}\cdot\frac{1}{1-z}=0.$

∎

Now given $0<\varepsilon<\delta$ set

${z:=1-\frac{1-\delta}{1-\varepsilon}\quad\Longleftrightarrow\quad\varepsilon=1-\frac{1-\delta}{1-z}=\frac{\delta-z}{1-z}.}$
(6.3)

Lemma 6.1, applied with $n$ replaced with $N$ and $m$ replaced with
$\left\lceil zN\right\rceil$, then implies that there exists
$N_{0}=N_{0}(z)\in{\mathbb{N}}$ such that

${{N\choose\left\lceil zN\right\rceil}\leq B\left(\frac{\lceil
zN\rceil}{N}\right)^{N}\quad\text{ for all }N\geq N_{0}.}$ (6.4)

Take $0<r\leq r_{2}/5$ and $T_{r}$ as in (4.3), and let $T>T_{r}$. By
combining Corollary 5.5 with (6.4) we get that for any $N\geq N_{0}$ and any
$0<\varepsilon<\delta$,

$\displaystyle A_{x,\delta}(NT,O^{c})\text{ can be covered with at most }$
(6.5) $\displaystyle C_{1}e^{LN{{\lambda_{\max}}}T}\cdot\beta_{N}^{N}\text{
balls in $P$ of radius }re^{-{{\lambda_{\max}}}NT},$

where

$\beta_{N}:={B\left(\frac{\lceil
zN\rceil}{N}\right)}\cdot\left(\frac{C(T,O)}{\varepsilon}\right)^{\frac{\lceil
zN\rceil}{N}}\left(1+c_{0}e^{-{{\lambda_{\min}}}T}\right)^{1-\frac{\lceil
zN\rceil}{N}}.$

Note that we have

${\lim_{N\rightarrow\infty}\beta_{N}=B(z)\cdot\left(\frac{C(T,O)}{\varepsilon}\right)^{z}\left(1+c_{0}e^{-{{\lambda_{\min}}}T}\right)^{1-z}}$
(6.6)

In view of (6.3), (6.5), (6.6) and Proposition 4.1, by applying Lemma 3.2 with
$e^{-{{\lambda_{\max}}}T}$ in place of $\rho$,
$L+\frac{\log\beta_{N}}{{{\lambda_{\max}}}T}$ in place of $\alpha_{N}$ and $r$
in place of $C$, we conclude that for any $0<z<\delta$ the Hausdorff dimension
of the set $S_{x,\delta}(O)$ is bounded from above by

$\displaystyle
L+\frac{1}{{{{\lambda_{\max}}}T}}{\log\left({B(z)}\biggl{(}\frac{C(T,O)(1-z)}{\delta-z}\biggr{)}^{z}\left(1+c_{0}e^{-{{\lambda_{\min}}}T}\right)^{1-z}\right)}$
$\displaystyle\underset{\eqref{eq:bx}}{=}L+\frac{1}{{{{\lambda_{\max}}}T}}{\log\left(\biggl{(}\frac{C(T,O)(1-z)}{z(\delta-z)}\biggr{)}^{z}\left(\frac{1+c_{0}e^{-{{\lambda_{\min}}}T}}{1-z}\right)^{1-z}\right).}$

This shows that our objective should be to find $z\in(0,\delta)$ and $T>T_{r}$
such that the value of

$\frac{1}{T}\left(z\log\Big{(}\frac{z(\delta-z)}{C(T,O)(1-z)}\Big{)}+(1-z)\log\Big{(}\frac{1-z}{1+c_{0}e^{-{{\lambda_{\min}}}T}}\Big{)}\right)$

is the largest possible. We are going to approximate the maximum by first
choosing $T$ in a convenient way. Take $T_{0}\geq 1$ sufficiently large so
that for any $T\geq T_{0}$ one has

${c_{0}e^{-\lambda_{\min}T}<\frac{1}{T}}$ (6.7)

(note that $T_{0}$ depends only on $G$, $F_{+}$ and $P$), and set

${T:=\max\left(\frac{8T_{r}}{\mu({\sigma_{5r}}O)},T_{0}\right).}$ (6.8)

Then

${\frac{1}{T}<\frac{1+T_{r}}{T}\leq\frac{2T_{r}}{T}\leq\frac{\mu({\sigma_{5r}}O)}{4},}$

which, in combination with (6.7), yields

${1+c_{0}e^{-{{\lambda_{\min}}}T}\leq
1+\frac{1}{T}<1+\frac{\mu({\sigma_{5r}}O)}{4}}$

and

$\displaystyle C(T,O)$
$\displaystyle=1-\mu({\sigma_{5r}}O)+\frac{T_{r}+1}{T}+c_{0}e^{-{{\lambda_{\min}}}T}$
$\displaystyle\leq
1-\mu({\sigma_{5r}}O)+\frac{\mu({\sigma_{5r}}O)}{4}+\frac{\mu({\sigma_{5r}}O)}{4}=1-\frac{\mu({\sigma_{5r}}O)}{2}.$

Therefore for $T$ as in (6.8) the codimension of $S_{x,\delta}(O)$ is for any
$0<z<\delta$ bounded from below by

$\frac{1}{{{{\lambda_{\max}}}T}}\left(z\log\Biggl{(}\frac{z(\delta-z)}{\left(1-\frac{\mu({\sigma_{5r}}O)}{2}\right)(1-z)}\Biggr{)}+(1-z)\log\left(\frac{1-z}{1+\frac{\mu({\sigma_{5r}}O)}{4}}\right)\right).$

Note that the second summand in the above expression is always negative; thus
it makes sense to try choosing $0<z<\delta$ in a way that ensures that the
first summand is maximized and is positive if possible (this condition could
prove to be unsuccessful for any $0<z<\delta$, contingent upon
$\mu({\sigma_{5r}}O)$ and $\delta$; in this case we will not achieve a
dimension drop).

We will solve the latter problem approximately by finding $0<z<\delta$ which
maximizes the ratio $\frac{z(\delta-z)}{1-z}$. An elementary calculus exercise
shows that for that one should take $z=1-\sqrt{1-\delta}$, so that
$\frac{z(\delta-z)}{1-z}=(1-\sqrt{1-\delta})^{2}$. Denoting
$s=\sqrt{1-\delta}$ and $y=\mu({\sigma_{5r}}O)$, we get an estimate

$\begin{aligned} \operatorname{codim}S_{x,\delta}(O)\geq\ \
&\frac{1}{{{{\lambda_{\max}}}T}}\left((1-s)\log\biggl{(}\frac{(1-s)^{2}}{1-\frac{y}{2}}\biggr{)}+s\log\left(\frac{s}{1+\frac{y}{4}}\right)\right)\\\
\underset{\eqref{eq:defphi}}{=}\
&\frac{1}{{{{\lambda_{\max}}}T}}\phi(y,s).\end{aligned}.$

It remains to observe that

$T\ \underset{\eqref{eq:Tfinal}}{\ll}\ \frac{8T_{r}}{\mu({\sigma_{5r}}O)}\
\underset{\eqref{eq:Tr}}{\ll}\ \frac{\log\frac{1}{r}}{\mu({\sigma_{5r}}O)}\
\underset{r\leq\frac{r_{2}}{5}<1/40}{\ll}\
\frac{\log\frac{1}{5r}}{\mu({\sigma_{5r}}O)};$

thus (6.1) follows, which ends the proof of Theorem 1.5.∎

## References

  * [1] H. al Saqban, P. Apisa, A. Erchenko, O. Khalil, S. Mirzadeh and C. Uyanik, Exceptional directions for the Teichmüller geodesic flow and Hausdorff dimension, J. Eur. Math. Soc. 23 (2021), 1423–1476.
  * [2] J. An, L. Guan and D. Kleinbock, Nondense orbits on homogeneous spaces and applications to geometry and number theory, Ergodic Theory Dynam. Systems 42 (2022), no. 4, 1327–1372.
  * [3] M. Einsiedler, S. Kadyrov and A. Pohl, Escape of mass and entropy for diagonal flows in real rank one situations, Israel J. Math. 210 (2015), no. 1, 245–295.
  * [4] S. Kadyrov, Exceptional sets in homogeneous spaces and Hausdorff dimension, Dyn. Syst. 30 (2015), no. 2, 149–157.
  * [5] D. Kleinbock, Nondense orbits of flows on homogeneous spaces, Ergodic Theory Dynam. Systems 18 (1998), 373–396.
  * [6] S. Kadyrov, D. Kleinbock, E. Lindenstrauss and G. A. Margulis, Entropy in the cusp and singular systems of linear forms, J. Anal. Math. 133 (2017), 253–277.
  * [7] D. Kleinbock and G. A. Margulis, Bounded orbits of nonquasiunipotent flows on homogeneous spaces, Sinaí’s Moscow Seminar on Dynamical Systems, 141–172, Amer. Math. Soc. Trans. Ser. 2, Amer. Math. Soc. Providence, RI, 1996.
  * [8] by same author, On effective equidistribution of expanding translates of certain orbits in the space of lattices, in: Number Theory, Analysis and Geometry, Springer, New York, 2012, pp. 385–396.
  * [9] D. Kleinbock and S. Mirzadeh, Dimension estimates for the set of points with non-dense orbit in homogeneous spaces, Math. Z. 295 (2020), 1355–1383.
  * [10] by same author, On the dimension drop conjecture for diagonal flows on the space of lattices, Adv. Math. 425 (2023), Paper No. 109058.
  * [11] by same author, Dimension drop for diagonalizable flows on homogeneous spaces, preprint (2022), arXiv:2207.13155.
  * [12] D. Kleinbock and B. Weiss, Modified Schmidt games and a conjecture of Margulis, J. Mod. Dyn. 7, no. 3 (2013), 429–460.
  * [13] F. Rodriguez Hertz and Z. Wang, On $\varepsilon$-escaping trajectories in homogeneous spaces, Discrete Contin. Dyn. Syst. 41 (2021), no. 1, 329–357.
  * [14] M. Urbański, The Hausdorff dimension of the set of points with nondense orbit under a hyperbolic dynamical system, Nonlinearity 4 (1991), 385–397.
  * [15] H. Wegmann, Die Hausdorff-Dimension von kartesischen Produktmengen in metrischen Räumen, J. Reine Angew. Math. 234 (1969), 163–171.


# Garland’s method for token graphs

Alan Lew111e-mail<EMAIL_ADDRESS>Dept. Math. Sciences, Carnegie
Mellon University, Pittsburgh, PA 15213, USA

###### Abstract

The $k$-th token graph of a graph $G=(V,E)$ is the graph $F_{k}(G)$ whose
vertices are the $k$-subsets of $V$ and whose edges are all pairs of
$k$-subsets $A,B$ such that the symmetric difference of $A$ and $B$ forms an
edge in $G$. Let $L(G)$ be the Laplacian matrix of $G$, and $L_{k}(G)$ be the
Laplacian matrix of $F_{k}(G)$. It was shown by Dalfó et al. that for any
graph $G$ on $n$ vertices and any $0\leq\ell\leq k\leq\left\lfloor
n/2\right\rfloor$, the spectrum of $L_{\ell}(G)$ is contained in that of
$L_{k}(G)$.

Here, we continue to study the relation between the spectrum of $L_{k}(G)$ and
that of $L_{k-1}(G)$. In particular, we show that, for $1\leq
k\leq\left\lfloor n/2\right\rfloor$, any eigenvalue $\lambda$ of $L_{k}(G)$
that is not contained in the spectrum of $L_{k-1}(G)$ satisfies

$k(\lambda_{2}(L(G))-k+1)\leq\lambda\leq k\lambda_{n}(L(G)),$

where $\lambda_{2}(L(G))$ is the second smallest eigenvalue of $L(G)$ (a.k.a.
the algebraic connectivity of $G$), and $\lambda_{n}(L(G))$ is its largest
eigenvalue. Our proof relies on an adaptation of Garland’s method, originally
developed for the study of high-dimensional Laplacians of simplicial
complexes.

##  1 Introduction

Let $G=(V,E)$ be a graph. The _$k$ -th token graph_ of $G$, denoted by
$F_{k}(G)$, is the graph on vertex set $\binom{V}{k}$ whose edges are the
pairs $\\{A,B\\}$ with $|A\cap B|=k-1$ and $A\triangle B=(A\setminus
B)\cup(B\setminus A)\in E$. Token graphs were originally defined by Johns in
[15] under the name of _$k$ -tuple vertex graphs_ (see also e.g. [2, 21, 3]).
In [4], they were reintroduced under the name of _$k$ -th symmetric powers_.
Finally, in [9], they were introduced once again under their current name.
Token graphs also appear implicitly in the study of the “symmetric exclusion
process” on graphs, introduced by Spitzer in [19] (see also e.g. [6]). Note
that for $k=0$ the graph $F_{0}(G)$ is just the graph with one vertex
(corresponding to the empty set) and no edges, for $k=1$ we have
$F_{1}(G)\cong G$, and, if $|V|=n$, then $F_{k}(G)\cong F_{n-k}(G)$ for all
$0\leq k\leq n$ (see e.g. [9]).

For a symmetric matrix $M\in{\mathbb{R}}^{m\times m}$, we denote by
$\lambda_{i}(M)$ its $i$-th smallest eigenvalue. Let $L(G)$ be the Laplacian
matrix of $G$, and let $L_{k}(G)=L(F_{k}(G))$ be the Laplacian of its $k$-th
token graph. The Laplacian spectrum of token graphs was studied by Dalfó,
Duque, Fabila-Monroy, Fiol, Huemer, Trujillo-Negrete and Martínez in [7]. In
particular, in was shown in [7] that for any $0\leq\ell\leq k\leq\lfloor
n/2\rfloor$ the spectrum of $L_{\ell}(G)$ is contained in the spectrum of
$L_{k}(G)$.

Let $1\leq k\leq\lfloor n/2\rfloor$, and let $\lambda$ be an eigenvalue of
$L_{k}(G)$. We say that $\lambda$ is _non-trivial_ if the multiplicity of
$\lambda$ as an eigenvalue of $L_{k}(G)$ is larger than its multiplicity as an
eigenvalue of $L_{k-1}(G)$. In particular, any eigenvalue of $L_{k}(G)$ that
is not contained in the spectrum of $L_{k-1}(G)$ is non-trivial. We denote the
maximal eigenvalue of $L_{k}(G)$ by $\lambda_{\text{max}}^{(k)}(G)$, and its
minimal non-trivial eigenvalue by $\lambda_{\text{min}}^{(k)}(G)$. For
example, for $k=1$, we have $\lambda_{\text{max}}^{(1)}(G)=\lambda_{n}(L(G))$
and $\lambda_{\text{min}}^{(1)}(G)=\lambda_{2}(L(G))$. Our main result
consists of the following bounds on $\lambda_{\text{max}}^{(k)}(G)$ and
$\lambda_{\text{min}}^{(k)}(G)$.

######  Theorem 1.1.

Let $G=(V,E)$ be a graph with $|V|=n$, and let $2\leq k\leq\lfloor
n/2\rfloor$. Then

$\lambda_{\text{max}}^{(k)}(G)\leq\frac{k}{k-1}\lambda_{\text{max}}^{(k-1)}(G)$

and

$\lambda_{\text{min}}^{(k)}(G)\geq\frac{k}{k-1}\lambda_{\text{min}}^{(k-1)}(G)-k.$

As a consequence, we obtain the following bounds on the non-trivial spectrum
of $L_{k}(G)$.

######  Theorem 1.2.

Let $G=(V,E)$ be a graph with $|V|=n$, and let $1\leq k\leq\lfloor
n/2\rfloor$. Let $\lambda$ be a non-trivial eigenvalue of $L_{k}(G)$. Then,

$k(\lambda_{2}(L(G))-k+1)\leq\lambda\leq k\lambda_{n}(L(G)).$

Both inequalities in Theorem 1.2 are tight: the lower bound is attained when
$G$ is a complete balanced multi-partite graph with at least $k$ parts, and
the upper bound is attained when $G$ is the union of at least $k$ disjoint
cliques, all of the same size (see Section 4).

It was conjectured in [7] (see also [8, 18]) that for any graph $G$ on $n$
vertices and any $1\leq k\leq n-1$, $\lambda_{2}(L(G))=\lambda_{2}(L_{k}(G))$.
In fact, as mentioned in [17], this follows as a special case of Aldous’
spectral gap conjecture, proved by Caputo, Liggett and Richthammer (see [6,
Section 4.1.1]). Note that, in the special case when $\lambda_{2}(G)\geq k$,
the equality $\lambda_{2}(L(G))=\lambda_{2}(L_{k}(G))$ follows immediately
from the lower bound in Theorem 1.2.

Our proof of Theorem 1.1 relies on an adaptation of Garland’s “local to
global” method ([11], see also [5, 22]). In its original form, Garland’s
method relates between the spectrum of a high-dimensional Laplacian matrix on
a simplicial complex to the Laplacian spectra of certain subgraphs of the
complex. In [1], Aharoni, Berger and Meshulam developed a “global version” of
Garland’s argument, relating the spectrum of a high-dimensional Laplacian
matrix on the clique complex of a graph $G$ to the Laplacian spectrum of $G$.
This relation was later extended in [16] to more general classes of simplicial
complexes. Our argument here can be seen as an analogue of the argument in
[1], and is motivated by the similarity between the Laplacian of the $k$-th
token graph of a graph $G$ and the $(k-1)$-dimensional Laplacian of the clique
complex of $G$.

The paper is organized as follows. In Section 2 we present some background
material on Laplacian matrices and on the Laplacian spectrum of token graphs.
In Section 3 we prove our main results, Theorems 1.1 and 1.2. In Section 4 we
present extremal examples showing the sharpness of Theorem 1.2.

##  2 Preliminaries

Let $G=(V,E)$ be a graph with $|V|=n$. For convenience, we will assume
$V=[n]$. For a vertex $v\in V$, let $d_{G}(v)=|\\{e\in E:\,v\in e\\}|$ be the
_degree_ of $v$ in $G$. The _Laplacian matrix_ $L(G)\in{\mathbb{R}}^{n\times
n}$ is defined as

$L(G)_{u,v}=\begin{cases}d_{G}(v)&\text{ if }u=v,\\\ -1&\text{ if
}\\{u,v\\}\in E,\\\ 0&\text{ otherwise.}\end{cases}$

For $0\leq\ell\leq k\leq n$, let
$B_{n,k,\ell}\in{\mathbb{R}}^{\binom{n}{k}\times\binom{n}{\ell}}$ be a matrix
with rows indexed by the $k$-subsets of $[n]$ and columns indexed by its
$\ell$-subsets, with elements

$(B_{n,k,\ell})_{\sigma,\eta}=\begin{cases}1&\text{ if }\eta\subset\sigma,\\\
0&\text{ otherwise,}\end{cases}$

for $\sigma\in\binom{[n]}{k}$ and $\eta\in\binom{[n]}{\ell}$. It is well known
(see e.g. [13, 14, 20]) that for $k\leq\lfloor n/2\rfloor$, $B_{n,k,\ell}$ has
rank $\binom{n}{\ell}$. In [7, Theorem 4.3], it was shown that for any $1\leq
k\leq n$,

$B_{n,k,k-1}L_{k-1}(G)=L_{k}(G)B_{n,k,k-1}.$ (2.1)

Equation (2.1) implies that both $\text{Im}(B_{n,k,k-1})$ and
$\text{Im}(B_{n,k,k-1})^{\perp}=\text{Ker}(B_{n,k,k-1}^{T})$ are invariant
subspaces of $L_{k}(G)$. Moreover, for $1\leq k\leq\lfloor n/2\rfloor$, using
(2.1) and the fact that $B_{n,k,k-1}$ has full column rank, we obtain that if
$\phi_{1},\ldots,\phi_{\binom{n}{k-1}}$ form a basis of
${\mathbb{R}}^{\binom{n}{k-1}}$ consisting of eigenvectors of $L_{k-1}(G)$,
with eigenvalues $\lambda_{1},\ldots,\lambda_{\binom{n}{k-1}}$ respectively,
then $B_{n,k,k-1}\phi_{1},\ldots,B_{n,k,k-1}\phi_{\binom{n}{k-1}}$ form a
basis of $\text{Im}(B_{n,k,k-1})$ consisting of eigenvectors of $L_{k}(G)$,
with the same eigenvalues $\lambda_{1},\ldots,\lambda_{\binom{n}{k-1}}$ (see
[7, Corollary 4.5]). In particular, the spectrum of $L_{k-1}(G)$ is contained
(including multiplicities) in the spectrum of $L_{k}(G)$. As immediate
consequences, we obtain the following useful results:

######  Lemma 2.1.

Let $1\leq k\leq\lfloor n/2\rfloor$, and let $\lambda$ be an eigenvalue of
$L_{k}(G)$. Then, $\lambda$ is non-trivial if and only if there exists an
eigenvector $\phi$ of $L_{k}(G)$ with eigenvalue $\lambda$ satisfying
$B^{T}_{n,k,k-1}\phi=0$.

######  Lemma 2.2.

Let $1\leq k\leq\lfloor n/2\rfloor$. Then

$\lambda_{\text{min}}^{(k)}(G)=\min\left\\{\frac{\phi^{T}L_{k}(G)\phi}{\|\phi\|^{2}}\,:\,0\neq\phi\in{\mathbb{R}}^{\binom{n}{k}},\,B^{T}_{n,k,k-1}\phi=0\right\\}.$

##  3 A Garland-type argument

In this section we prove our main results, Theorems 1.1 and 1.2. Let
$G=([n],E)$ be a graph, and let $2\leq k\leq\lfloor n/2\rfloor$. Let $L=L(G)$
and $L_{k}=L_{k}(G)=L(F_{k}(G))$. We will denote the edge set of $F_{k}(G)$ by
$E_{k}$. Moreover, for $\sigma\in\binom{[n]}{k}$, let
$d_{k}(\sigma)=d_{F_{k}(G)}(\sigma)$ be the degree of $\sigma$ in $F_{k}(G)$.

Let $\phi\in{\mathbb{R}}^{\binom{n}{k}}$. For any $u\in[n]$, we define
$\phi_{u}\in{\mathbb{R}}^{\binom{n}{k-1}}$ by

$\phi_{u}(\tau)=\begin{cases}\phi(\tau\cup\\{u\\})&\text{ if }u\notin\tau,\\\
0&\text{ if }u\in\tau,\end{cases}$

for any $\tau\in\binom{[n]}{k-1}$. For a set $\sigma\in\binom{[n]}{k}$, denote
$E_{\sigma}=\\{e\in E:\,e\subset\sigma\\}.$ We define a diagonal matrix
$D_{k}\in{\mathbb{R}}^{\binom{n}{k}\times\binom{n}{k}}$ by

$(D_{k})_{\sigma,\tau}=\begin{cases}|E_{\sigma}|&\text{ if }\sigma=\tau,\\\
0&\text{ otherwise,}\end{cases}$ (3.1)

for all $\sigma,\tau\in\binom{[n]}{k}$. Theorem 1.1 will follow from the
following identity:

######  Proposition 3.1.

Let $\phi\in{\mathbb{R}}^{\binom{n}{k}}$. Then

$(k-1)\phi^{T}L_{k}\phi=\left(\sum_{u=1}^{n}\phi_{u}^{T}L_{k-1}\phi_{u}\right)-2\phi^{T}D_{k}\phi.$

For the proof of Proposition 3.1, we will need the following result about sums
of degrees in $F_{k}(G)$.

######  Lemma 3.2.

Let $\sigma\in\binom{[n]}{k}$. Then,

$\sum_{u\in\sigma}d_{k-1}(\sigma\setminus\\{u\\})=(k-1)d_{k}(\sigma)+2|E_{\sigma}|.$

###### Proof.

Note that, for any $0\leq j\leq n$ and any $\eta\in\binom{[n]}{j}$,
$d_{j}(\eta)=|\\{e\in E:\,|e\cap\eta|=1\\}|$. Therefore,

$\displaystyle\sum_{u\in\sigma}d_{k-1}(\sigma\setminus\\{u\\})$
$\displaystyle=\sum_{u\in\sigma}\sum_{v\in\sigma\setminus\\{u\\}}\sum_{\begin{subarray}{c}w\in([n]\setminus\sigma)\cup\\{u\\},\\\
\\{v,w\\}\in
E\end{subarray}}1=\sum_{u\in\sigma}\sum_{v\in\sigma\setminus\\{u\\}}\sum_{\begin{subarray}{c}w\in[n]\setminus\sigma,\\\
\\{v,w\\}\in
E\end{subarray}}1+\sum_{u\in\sigma}\sum_{\begin{subarray}{c}v\in\sigma\setminus\\{u\\},\\\
\\{u,v\\}\in E\end{subarray}}1$
$\displaystyle=(k-1)\sum_{v\in\sigma}\sum_{\begin{subarray}{c}w\in[n]\setminus\sigma,\\\
\\{v,w\\}\in
E\end{subarray}}1+\sum_{u\in\sigma}\sum_{\begin{subarray}{c}v\in\sigma\setminus\\{u\\},\\\
\\{u,v\\}\in E\end{subarray}}1=(k-1)d_{k}(\sigma)+2|E_{\sigma}|.$

∎

###### Proof of Proposition 3.1.

We have

$\displaystyle\phi^{T}L_{k}\phi$ $\displaystyle=\sum_{\\{\sigma,\tau\\}\in
E_{k}}(\phi(\sigma)-\phi(\tau))^{2}=\sum_{\sigma\in\binom{[n]}{k}}d_{k}(\sigma)\phi(\sigma)^{2}-2\sum_{\\{\sigma,\tau\\}\in
E_{k}}\phi(\sigma)\phi(\tau)$
$\displaystyle=\sum_{\sigma\in\binom{[n]}{k}}d_{k}(\sigma)\phi(\sigma)^{2}-2\sum_{\eta\in\binom{[n]}{k-1}}\sum_{\begin{subarray}{c}\\{v,w\\}\in
E,\\\ v,w\notin\eta\end{subarray}}\phi(\eta\cup\\{v\\})\phi(\eta\cup\\{w\\}).$
(3.2)

Similarly,

$\displaystyle\sum_{u=1}^{n}$
$\displaystyle\phi_{u}^{T}L_{k-1}\phi_{u}=\sum_{u=1}^{n}\sum_{\tau\in\binom{[n]}{k-1}}d_{k-1}(\tau)\phi_{u}(\tau)^{2}-2\sum_{u=1}^{n}\sum_{\eta\in\binom{[n]}{k-2}}\sum_{\begin{subarray}{c}\\{v,w\\}\in
E,\\\
v,w\notin\eta\end{subarray}}\phi_{u}(\eta\cup\\{v\\})\phi_{u}(\eta\cup\\{w\\})$
$\displaystyle=\sum_{\tau\in\binom{[n]}{k-1}}\sum_{u\in[n]\setminus\tau}d_{k-1}(\tau)\phi(\tau\cup\\{u\\})^{2}-2\sum_{\eta\in\binom{[n]}{k-2}}\sum_{u\in[n]\setminus\eta}\sum_{\begin{subarray}{c}\\{v,w\\}\in
E,\\\
v,w\notin\eta\cup\\{u\\}\end{subarray}}\phi(\eta\cup\\{u,v\\})\phi(\eta\cup\\{u,w\\})$
$\displaystyle=\sum_{\sigma\in\binom{[n]}{k}}\left(\sum_{u\in\sigma}d_{k-1}(\sigma\setminus\\{u\\})\right)\phi(\sigma)^{2}-2(k-1)\sum_{\tau\in\binom{[n]}{k-1}}\sum_{\begin{subarray}{c}\\{v,w\\}\in
E,\\\ v,w\notin\tau\end{subarray}}\phi(\tau\cup\\{v\\})\phi(\tau\cup\\{w\\}).$
(3.3)

By Lemma 3.2 we have, for all $\sigma\in\binom{[n]}{k}$,

$\sum_{u\in\sigma}d_{k-1}(\sigma\setminus\\{u\\})=(k-1)d_{k}(\sigma)+2|E_{\sigma}|.$

Therefore, by (3) and (3), we obtain

$(k-1)\phi^{T}L_{k}\phi=\sum_{u=1}^{n}\phi_{u}^{T}L_{k-1}\phi_{u}-2\sum_{\sigma\in\binom{[n]}{k}}|E_{\sigma}|\phi(\sigma)^{2}=\sum_{u=1}^{n}\phi_{u}^{T}L_{k-1}\phi_{u}-2\phi^{T}D_{k}\phi.$

∎

We will also need the following lemma.

######  Lemma 3.3.

Let $\phi\in{\mathbb{R}}^{\binom{n}{k}}$. Then

$\sum_{u=1}^{n}\|\phi_{u}\|^{2}=k\|\phi\|^{2}.$

###### Proof.

$\sum_{u=1}^{n}\|\phi_{u}\|^{2}=\sum_{u=1}^{n}\sum_{\tau\in\binom{[n]}{k-1}}\phi_{u}(\tau)^{2}=\sum_{\tau\in\binom{[n]}{k-1}}\sum_{u\in[n]\setminus\tau}\phi(\tau\cup\\{u\\})^{2}=\sum_{\sigma\in\binom{[n]}{k}}\sum_{u\in\sigma}\phi(\sigma)^{2}=k\sum_{\sigma\in\binom{[n]}{k}}\phi(\sigma)^{2}=k\|\phi\|^{2}.$

∎

We can now prove Theorem 1.1:

###### Proof of Theorem 1.1.

Let $\lambda=\lambda_{\text{max}}^{(k)}(G)$, and let
$\phi\in{\mathbb{R}}^{\binom{n}{k}}$ be an eigenvector of $L_{k}$ with
eigenvalue $\lambda$. By Proposition 3.1, we have

$(k-1)\lambda\|\phi\|^{2}=(k-1)\phi^{T}L_{k}\phi=\sum_{u=1}^{n}\phi_{u}^{T}L_{k-1}\phi_{u}-2\phi^{T}D_{k}\phi.$

Since $|E_{\sigma}|\geq 0$ for all $\sigma\in\binom{[n]}{k}$, we have
$\phi^{T}D_{k}\phi\geq 0$, and therefore

$(k-1)\lambda\|\phi\|^{2}\leq\sum_{u=1}^{n}\phi_{u}^{T}L_{k-1}\phi_{u}\leq\sum_{u=1}^{n}\lambda_{\text{max}}^{(k-1)}(G)\|\phi_{u}\|^{2}=k\lambda_{\text{max}}^{(k-1)}(G)\|\phi\|^{2},$

where the last equality follows from Lemma 3.3. Hence, we obtain $\lambda\leq
k\lambda_{\text{max}}^{(k-1)}(G)/(k-1)$, as wanted.

Now, let $\lambda=\lambda_{\text{min}}^{(k)}(G)$. By Lemma 2.1, since
$\lambda$ is non-trivial, there is an eigenvector $\phi$ of $L_{k}$ with
eigenvalue $\lambda$ such that $B^{T}_{n,k,k-1}\phi=0$. We will show that, for
any $u\in[n]$, $B^{T}_{n,k-1,k-2}\phi_{u}=0$. Let $u\in[n]$ and
$\eta\in\binom{[n]}{k-2}$. If $u\in\eta$, we have

$B^{T}_{n,k-1,k-2}\phi_{u}(\eta)=\sum_{\begin{subarray}{c}\tau\in\binom{[n]}{k-1},\\\
\eta\subset\tau\end{subarray}}\phi_{u}(\tau)=0,$

by the definition of $\phi_{u}$. If $u\notin\eta$, then

$B^{T}_{n,k-1,k-2}\phi_{u}(\eta)=\sum_{\begin{subarray}{c}\tau\in\binom{[n]}{k-1},\\\
\eta\subset\tau\end{subarray}}\phi_{u}(\tau)=\sum_{\begin{subarray}{c}\tau\in\binom{[n]}{k-1},\\\
\eta\subset\tau,\,u\notin\tau\end{subarray}}\phi(\tau\cup\\{u\\})=\sum_{\begin{subarray}{c}\sigma\in\binom{[n]}{k},\\\
\eta\cup\\{u\\}\subset\sigma\end{subarray}}\phi(\sigma)=B^{T}_{n,k,k-1}\phi(\eta\cup\\{u\\})=0.$

Therefore, by Lemma 2.2,
$\phi_{u}^{T}L_{k-1}\phi_{u}\geq\lambda_{\text{min}}^{(k-1)}(G)\|\phi_{u}\|^{2}$
for all $u\in[n]$. Moreover, since $|E_{\sigma}|\leq\binom{k}{2}$ for all
$\sigma\in\binom{[n]}{k}$, we have
$\phi^{T}D_{k}\phi\leq\binom{k}{2}\|\phi\|^{2}$, and thus, by Proposition 3.1,
we obtain

$\displaystyle(k-1)\lambda\|\phi\|^{2}$
$\displaystyle=(k-1)\phi^{T}L_{k}\phi=\sum_{u=1}^{n}\phi_{u}^{T}L_{k-1}\phi_{u}-2\phi^{T}D_{k}\phi$
$\displaystyle\geq\sum_{u=1}^{n}\lambda_{\text{min}}^{(k-1)}(G)\|\phi_{u}\|^{2}-k(k-1)\|\phi\|^{2}=\left(k\lambda_{\text{min}}^{(k-1)}(G)-k(k-1)\right)\|\phi\|^{2},$

where the last equality follows from Lemma 3.3. Hence, $\lambda\geq
k\lambda_{\text{min}}^{(k-1)}(G)/(k-1)-k$. ∎

Finally, we obtain Theorem 1.2 by an inductive application of Theorem 1.1.

###### Proof of Theorem 1.2.

We will show that

$\lambda_{\text{max}}^{(k)}(G)\leq k\lambda_{n}(L)$

and

$\lambda_{\text{min}}^{(k)}(G)\geq k(\lambda_{2}(L)-k+1).$

We argue by induction on $k$. For $k=1$ the claim is trivial. Let $k\geq 2$,
and assume that

$\lambda_{\text{max}}^{(k-1)}(G)\leq(k-1)\lambda_{n}(L)$

and

$\lambda_{\text{min}}^{(k-1)}(G)\geq(k-1)(\lambda_{2}(L)-(k-1)+1).$

Then, by Theorem 1.1, we obtain

$\lambda_{\text{max}}^{(k)}(G)\leq\frac{k}{k-1}\lambda_{\text{max}}^{(k-1)}(G)\leq
k\lambda_{n}(L),$

and

$\lambda_{\text{min}}^{(k)}(G)\geq\frac{k}{k-1}\lambda_{\text{min}}^{(k-1)}(G)-k\geq
k(\lambda_{2}(L)-k+1).$

∎

##  4 Extremal examples

The next result shows that the upper and lower bounds in Theorem 1.2 are
sharp.

######  Proposition 4.1.

Let $m\geq k$, and let $n$ be divisible by $m$. Let $G$ be the union of $m$
disjoint cliques, each of size $n/m$. Then, the maximal eigenvalue of
$L_{k}(G)$ is exactly $kn/m=k\lambda_{n}(L(G))$.

Let $\bar{G}$ be the complement graph of $G$, namely the complete balanced
$m$-partite graph with sides of size $n/m$. Then, the minimal non-trivial
eigenvalue of $L_{k}(\bar{G})$ is exactly
$k((m-1)n/m-k+1)=k(\lambda_{2}(L(\bar{G}))-k+1)$.

Proposition 4.1 follows from an argument similar to the one in [7, Theorem
7.2(iv)]. For completeness, we include a proof. We will need the following
result due to Fiedler. Recall that, given graphs $G=(V,E)$ and
$G^{\prime}=(V^{\prime},E^{\prime})$, the Cartesian product $G\square
G^{\prime}$ is the graph on vertex set $V\times V^{\prime}$ with edges of the
form $\\{(u,u^{\prime}),(v,v^{\prime})\\}$, where either $u=v$ and
$u^{\prime}$ is adjacent to $v^{\prime}$ in $G^{\prime}$, or
$u^{\prime}=v^{\prime}$ and $u$ is adjacent to $v$ in $G$.

######  Lemma 4.2 (Fiedler [10, 3.4]).

For $1\leq i\leq m$, let $H_{i}$ be a graph on $n_{i}$ vertices, and let
$\lambda_{1}^{i}\leq\cdots\leq\lambda_{n_{i}}^{i}$ be its Laplacian
eigenvalues. Then, the Laplacian eigenvalues of the Cartesian product
$H_{1}\square\cdots\square H_{m}$ are

$\left\\{\sum_{i=1}^{m}\lambda_{t_{i}}^{i}:\,1\leq t_{i}\leq n_{i}\,\,\forall
i\in[m]\right\\}.$

We will also need the following result, describing the Laplacian spectra of
token graphs of a complete graph (also known as Johnson graphs).

######  Lemma 4.3 (See [12, Thm. 6.3.2, Thm. 6.3.3], [7, Eq. 19]).

Let $K_{n}$ be the complete graph on $n$ vertices. Then, the eigenvalues of
$L_{k}(K_{n})$ are

$\\{j(n-j+1):\,0\leq j\leq k\\}.$

Moreover, for every $0\leq j\leq k$, the eigenspace corresponding to the
eigenvalue $j(n-j+1)$ is the orthogonal complement of $\text{Im}(B_{n,k,j-1})$
in $\text{Im}(B_{n,k,j})$, and therefore the eigenvalue $j(n-j+1)$ has
multiplicity $\binom{n}{j}-\binom{n}{j-1}$. In particular, the eigenvectors
corresponding to the eigenvalue $k(n-k+1)$ are exactly the vectors
$\phi\in{\mathbb{R}}^{\binom{n}{k}}$ satisfying $B^{T}_{n,k,k-1}\phi=0$.

Finally, we will need the following result relating the spectrum of $L_{k}(G)$
and that of $L_{k}(\bar{G})$, which follows from the proof of [7, Theorem
6.2]:

######  Lemma 4.4.

Let $G$ be a graph on $n$ vertices, and let $\lambda$ be a non-trivial
eigenvalue of $L_{k}(G)$. Then $\lambda=k(n-k+1)-\mu$, where $\mu$ is some
non-trivial eigenvalue of $L_{k}(\bar{G})$.

###### Proof.

Let $\phi$ be an eigenvector of $L_{k}(G)$ with eigenvalue $\lambda$. By Lemma
2.1, we can assume $B_{n,k,k-1}^{T}\phi=0$. It was shown in [7, Theorem 6.2]
that $\phi$ is also an eigenvector of $L_{k}(\bar{G})$ with eigenvalue $\mu$,
and an eigenvector of $L_{k}(K_{n})$ with eigenvalue $\xi$, for some $\mu$ and
$\xi$ such that $\lambda+\mu=\xi$. Since $B_{n,k,k-1}^{T}\phi=0$, by Lemma 4.3
we have $\xi=k(n-k+1)$. We obtain $\lambda=k(n-k+1)-\mu$. Furthermore, since
$\phi$ is an eigenvector of $L_{k}(\bar{G})$ with eigenvalue $\mu$ satisfying
$B_{n,k,k-1}^{T}\phi=0$, by Lemma 2.1 $\mu$ is a non-trivial eigenvalue of
$L_{k}(\bar{G})$. ∎

###### Proof of Proposition 4.1.

Let $G_{1},\ldots,G_{m}$ be the connected components of $G$, each isomorphic
to the complete graph on $n/m$ vertices. Let

$\mathcal{I}=\left\\{(k_{1},\ldots,k_{m}):\,0\leq k_{i}\leq
n/m,\,\sum_{i=1}^{m}k_{i}=k\right\\}.$

Then, for each $(k_{1},\ldots,k_{m})\in\mathcal{I}$, $F_{k}(G)$ has a
connected component isomorphic to $F_{k_{1}}(G_{1})\square\cdots\square
F_{k_{m}}(G_{m})$ (see proof of Corollary 6.4 in [7]). By Lemma 4.2 and Lemma
4.3, every eigenvalue of $L_{k}(G)$ is of the form

$\sum_{i=1}^{m}j_{i}(n/m-j_{i}+1)=\left(\sum_{i=1}^{m}j_{i}\right)n/m-\sum_{i=1}^{m}j_{i}(j_{i}-1),$

for $(k_{1},\ldots,k_{m})\in\mathcal{I}$ and $0\leq j_{i}\leq k_{i}$ for all
$1\leq i\leq m$.

Since $m\geq k$, we can choose each $k_{i}$ to be either $0$ or $1$, and
$j_{i}=k_{i}$ for all $i$, to obtain an eigenvalue

$\lambda=\left(\sum_{i=1}^{m}k_{i}\right)n/m-\sum_{i=1}^{m}k_{i}(k_{i}-1)=kn/m=k\lambda_{n}(L(G)).$
(4.1)

By Theorem 1.2, this is the maximal eigenvalue of $L_{k}(G)$. Furthermore,
note that, by Theorem 1.2, this is a non-trivial eigenvalue of $L_{k}(G)$
(otherwise, it is an eigenvalue of $L_{k-1}(G)$ larger than
$(k-1)\lambda_{n}(L(G))$, a contradiction).

Now, let $\bar{G}$ be the complement of $G$. Then
$\lambda_{2}(L(\bar{G}))=n-\lambda_{n}(L(G))=(m-1)n/m$. By Lemma 4.4,
$\lambda=k(n-k+1)-\mu$, where $\mu$ is some non-trivial eigenvalue of
$L_{k}(G)$. By (4.1), we have

$\displaystyle\mu$ $\displaystyle=k(n-k+1)-\lambda=k(n-k+1)-kn/m$
$\displaystyle=k((m-1)n/m-k+1)=k(\lambda_{2}(L(\bar{G}))-k+1).$

By Theorem 1.2, this is the minimal non-trivial eigenvalue of
$L_{k}(\bar{G})$. ∎

## References

  * [1] R. Aharoni, E. Berger, and R. Meshulam.  Eigenvalues and homology of flag complexes and vector representations of graphs.  Geometric and Functional Analysis, 15(3):555–566, 2005.
  * [2] Y. Alavi, M. Behzad, P. Erdős, and D. R. Lick.  Double vertex graphs.  J. Combin. Inform. System Sci, 16(1):37–50, 1991.
  * [3] Y. Alavi, D. R. Lick, and J. Liu.  Survey of double vertex graphs.  Graphs and Combinatorics, 18:709–715, 2002.
  * [4] K. Audenaert, C. Godsil, G. Royle, and T. Rudolph.  Symmetric squares of graphs.  Journal of Combinatorial Theory, Series B, 97(1):74–90, 2007.
  * [5] W. Ballmann and J. Światkowski.  On $L^{2}$-cohomology and property (T) for automorphism groups of polyhedral cell complexes.  Geometric and Functional Analysis, 7(4):615–645, 1997.
  * [6] P. Caputo, T. Liggett, and T. Richthammer.  Proof of Aldous’ spectral gap conjecture.  Journal of the American Mathematical Society, 23(3):831–851, 2010\.
  * [7] C. Dalfó, F. Duque, R. Fabila-Monroy, M. A. Fiol, C. Huemer, A. L. Trujillo-Negrete, and F. Z. Martínez.  On the Laplacian spectra of token graphs.  Linear Algebra and its Applications, 625:322–348, 2021.
  * [8] C. Dalfó and M. A. Fiol.  On the algebraic connectivity of token graphs.  arXiv preprint arXiv:2209.01030, 2022.
  * [9] R. Fabila-Monroy, D. Flores-Peñaloza, C. Huemer, F. Hurtado, J. Urrutia, and D. R. Wood.  Token graphs.  Graphs and Combinatorics, 28:365–380, 2012.
  * [10] M. Fiedler.  Algebraic connectivity of graphs.  Czechoslovak Mathematical Journal, 23(2):298–305, 1973.
  * [11] H. Garland.  $p$-adic curvature and the cohomology of discrete subgroups of $p$-adic groups.  Annals of Mathematics, pages 375–423, 1973.
  * [12] C. Godsil and K. Meagher.  Erdős-Ko-Rado theorems: algebraic approaches.  Cambridge University Press, 2016.
  * [13] D. H. Gottlieb.  A certain class of incidence matrices.  Proceedings of the American Mathematical Society, 17(6):1233–1237, 1966.
  * [14] J. E. Graver and W. Jurkat.  The module structure of integral designs.  Journal of Combinatorial Theory, Series A, 15(1):75–90, 1973.
  * [15] G. L. Johns.  Generalized distance in graphs.  PhD thesis, Western Michigan University, 1988.
  * [16] A. Lew.  The spectral gaps of generalized flag complexes and a geometric Hall-type theorem.  International Mathematics Research Notices, 2020(11):3364–3395, 2020.
  * [17] Y. Ouyang.  Computing spectral bounds of the Heisenberg ferromagnet from geometric considerations.  Journal of Mathematical Physics, 60(7):071901, 2019.
  * [18] M. Reyes, C. Dalfó, M. A. Fiol, and A. Messegué.  On the algebraic connectivity of token graphs of a cycle.  Proceedings of the 39th European Workshop on Computational Geometry, 2023.
  * [19] F. Spitzer.  Interaction of Markov processes.  Advances in Mathematics, 5(2):246–290, 1970.
  * [20] R. M. Wilson.  The necessary conditions for $t$-designs are sufficient for something.  Utilitas Math, 4:207–215, 1973.
  * [21] V. Wright.  $n$-tuple vertex graphs.  Master’s thesis, Emory University, Atlanta, 1992.
  * [22] A. Żuk.  Property (T) and Kazhdan constants for discrete groups.  Geometric & Functional Analysis GAFA, 13(3):643–670, 2003.