Even when unable to run experiments,
practitioners can evaluate prospective policies,
using previously logged data.
However, while the bandits literature
has adopted a diverse set of objectives,
most research on off-policy evaluation
to date focuses on the expected reward.
In this paper, we introduce
Lipschitz risk functionals,
a broad class of objectives
that subsumes conditional value-at-risk (CVaR),
variance, mean-variance,
many distorted risks, and CPT risks, among others.
We propose Off-Policy Risk Assessment (OPRA),
a framework that first estimates a target policy's CDF
and then generates plugin estimates
for any collection of Lipschitz risks,
providing finite sample guarantees
that hold simultaneously
over the entire class.
We instantiate OPRA with
both importance sampling
and doubly robust estimators.
Our primary theoretical contributions are
(i) the first uniform concentration inequalities
for both CDF estimators in contextual bandits
and (ii) error bounds on our Lipschitz risk estimates,
which all converge at a rate of $O(1/\sqrt{n})$.

§ INTRODUCTION

Many practical tasks,
including medical treatment <cit.>
and content recommendation <cit.>
are commonly modeled
within the contextual bandits framework.
In the online setting, an agent
observes a context at each step
and chooses among the available actions.
The agent then receives
a context-dependent reward
corresponding to the action taken,
but cannot observe the rewards
corresponding to alternative actions.
In a healthcare setting,
the observed context might be a vector
capturing vital signs, lab tests,
and other available data,
while the action space might consist
of the available treatments.
The reward to optimize could
be a measure of patient health
or treatment response.

While contextual bandits research
has traditionally focused
on the expected reward,
stakeholders often care
about other risk functionals
(parameters of the reward distribution)
that express real-world desiderata
or have desirable statistical properties.
For example, investors assess mutual funds
via the Sharpe ratio,
which normalizes returns
by their variance <cit.>.
Related works in reinforcement learning (RL)
have sought to estimate
the variance of returns
and to optimize the mean return
under variance constraints <cit.>.
In safety-critical and financial applications,
researchers often measure
the conditional value-at-risk (CVaR),
which captures the expected return
among the lower $\alpha$ quantile of outcomes
In an emerging line of RL works,
researchers have explored
other risk functionals,
including cumulative prospect weighting <cit.>,
distortion risk measures <cit.>,
and exponential utility functions <cit.>.

In many real-world problems otherwise suited
to the contextual bandits framework,
experimentation turns out to be
prohibitively expensive or unethical.
In such settings,
we might hope
to evaluate prospective policies
using the data collected
under a previous policy.
Formally, this problem is called
off-policy evaluation,
and our goal is to evaluate
the performance of a target policy $\pi$
using data collected
under a behavior policy $\beta$.
While most existing research
focuses on estimating
the expected value of the returns
one recent paper evaluates
the variance of returns

In this paper, we propose
practical methods and
the first sample complexity guarantees
for off-policy risk evaluation,
addressing a diverse set of objectives
of interest to researchers and practitioners.
Towards this end,
we introduce Lipschitz risk functionals
which encompass all objectives
for which the risk
(i) depends only on the CDF of rewards;
and (ii) is Lipschitz with respect
to changes in the CDF
(as assessed via the sup norm).
We prove that for bounded rewards,
this class subsumes many risk functionals
of practical interest, including variance,
mean-variance, conditional value-at-risk,
and cumulative prospect weighting, among others.

Thus, given accurate estimates
of the CDF of rewards under $\pi$,
we can accurately estimate Lipschitz risks.
Moreover, (sup norm) error bounds on our CDF estimates
imply error bounds on the corresponding plugin estimates
for any Lipschitz risks.
The key remaining step is to establish
finite sample guarantees on the error
in estimating the target policy's
CDF of rewards.
Our analysis centers on
an importance sampling estimator
(Section <ref>),
and a variance-reduced
doubly robust estimator
(Section <ref>).
We derive finite sample concentrations
for both CDF estimators,
showing that they achieve
the desired $O(1/\sqrt{n})$ rates,
where $n$ is the sample size.
Moreover, the estimation error
for any Lipschitz risk
is scales with its Lipschitz constant,
and similarly converges as $O(1/\sqrt{n})$.

We assemble these results
into an algorithm called OPRA
(Algorithm <ref>)
that outputs a comprehensive risk assessment
for a target policy $\pi$,
using any set of Lipschitz risk functionals.
Notably, because all risk estimates
share the same underlying CDF estimate,
our error guarantees hold simultaneously
for all estimated risk functionals in the set,
regardless of the cardinality (Section <ref>).
we present experiments that demonstrate the practical applicability our estimators.

§ RELATED WORK

The study of risk functionals and risk-aware algorithms
is core to the decision making literature <cit.>.
In supervised learning, <cit.>
study generalization properties under the CVaR risk functional,
while <cit.> study a variety of risk functionals.
<cit.> considers
the uniform convergence of $L$ risks
that are induced by CDF-dependent weighting functions
and generalize CVaR and cumulative prospect theory (CPT)
inspired risks <cit.>.
Uniform convergence of worst-case risks
defined by $f$-divergences,
which is a generalization of CVaR,
is studied in <cit.>.
A recent line of research on developing
the pointwise concentration of CVaR
can be found in <cit.>.

In the bandit literature,
many works address regret minimization problems
using risk functionals;
popular examples include the CVaR,
value-at-risk, and mean-variance
<cit.> studies
optimistic UCB exploration for optimizing CVaR
while <cit.>
study Thompson sampling,
and <cit.>
study regret minimization for
linear combinations of the mean and CVaR.
Using the CPT risk functional,
<cit.> considers regret minimization
in both $K$-armed bandits and linear contextual bandits.
tackle the problem
of black-box function optimization
under different risk functionals.

In off-policy evaluation,
we face an additional challenge
due to the discrepancy
between the data distribution
and that induced by the target policy.
Importance sampling () estimators
are among the most prominent methods
for dealing with distribution shift <cit.>.
Doubly robust () estimators
leverage (possibly misspecified) models
to achieve lower variance
without sacrificing consistency.
These estimators have been adapted
for off-policy evaluation in multi-armed bandits <cit.>,
contextual bandits <cit.>,
and Markov decision processes

In addition, distributional reinforcement learning methods
have gained traction in recent years.
These methods, introduced by <cit.>,
work with the full distribution of returns
and were subsequently improved upon by
Notably, <cit.>
uses the learned distribution
to optimize a number of risk functionals,
including the CVaR and other distorted risk functionals.
<cit.> leverages a similar method
to learn the distribution of returns,
but uses optimistic distribution-dependent exploration
to optimize the CVaR in MDPs.
Along similar lines, <cit.>
considers CVaR regret minimization using UCB exploration
in the multi-armed bandit setting,
and uses an empirical estimate
of the reward distribution for each arm
in order to evaluate the CVaR.

For empirical CDF estimation,
the seminal work of <cit.>
provides an approximation-theoretic
concentration bound
which was later tightened by <cit.>.
<cit.> provides concentration bounds
on probability estimates of arbitrary but structured measurable sets.
Later, the works of <cit.>
systematically improved Alexander's inequality.
For more details on concentrations of probability estimates,
we refer readers to <cit.>.

After deriving our key results,
we learned of a prior independent
(but then unpublished) work
that also employs importance sampling
to estimate CDFs for the purpose
of providing off-policy estimates
for parameters of the reward distribution.
However, they do not establish uniform concentration
of their estimates or formally relate
the parameter and CDF errors,
leaving open questions concerning the convergence
(both asymptotically and in finite samples)
of the parameter estimates.
Our work formulates both importance sampling
and variance-reduced doubly robust estimators
and provides the first uniform
finite sample concentration bounds
for both types of CDF and risk estimates.

§ PROBLEM SETTING

We denote contexts by $X$
and the corresponding context space by $\X$.
Similarly, we denote actions by $A$
and the corresponding action space by $\A$.
We study the contextual bandit problem characterized
by a fixed probability measure over context space $\X$,
and a reward function that maps from tuples
of contexts and actions to rewards:
$\mathcal{R}: \X \times \A \rightarrow \Real$.
In the off-policy setting,
we have access to a dataset $\mathcal{D}$
generated using a behavior policy $\beta$
that interacts with
the environment for $n$ rounds as follows:
at each round, a new context $X$ is drawn
and then the policy $\beta$
chooses an action $A \sim \beta(\cdot|X)$.
The environment then reveals the reward
$R \sim \mathcal{R}(\cdot|X,A)$
for only the chosen action $A$.
Running this process for $n$ steps
generates a dataset
$\mathcal{D} := \lbrace x_i, a_i, r_i \rbrace_{i=1}^n$.
In the off-policy evaluation setting,
our goal is to evaluate the performance
of a target policy $\pi$,
using only a dataset $\mathcal{D}$.

Next, we can express our sample space
in terms of the contexts, actions, and rewards:
$\Omega = \left(\mathcal{X} \times \mathcal{A} \times \Real \right)$.
Let $(\Omega, \F, \Prob_\beta)$ be the probability space
induced by the behavior policy $\beta$,
and $(\Omega, \F, \Prob)$ the probability space
induced by the target policy $\pi$.
We assume that $\Prob$ is absolutely continuous
with respect to $\Prob_\beta$.
For any context $x$ and action $a$,
the importance weight expresses the ratio
between the two densities
$\weight(\omega)= \weight(a,x) = \frac{\beta(a|x)}{\pi(a|x)}$,
and the maximum weight $w_{\max} = \sup_{a,x} w(a,x)$ is simply the supremum
taken over all contexts and actions. Further, let $w_\mathbbm{2} = \E_{\Prob_\beta}\left[\weight(A,X)^2\right]$ denote the exponential
of the second order Rényi divergence.
Note that by definition,
$w_\mathbbm{2} \leq w_{\max}$,
and in practice, we often have
$w_\mathbbm{2} \ll w_{\max}$.

Finally, we introduce
some notation
for describing s:
For any $t\in\Real$,
let $F(t) = \E_{\Prob}[\Ind_{\{R \leq t\}}]$
denote the under the target policy;
further, let $G(t;X,A) = \E_{\Prob}[\Ind_{\{R \leq t\}} \vert X,A] = \E_{\Prob_\beta}[\Ind_{\{R \leq t\}} \vert X,A]$ denote the of rewards
conditioned on a context $X$ and action $A$, which is independent of the policy.
Lastly, for any $t\in\Real$,
we denote the variance by
$\varXA(t;X,A) = \Var_\Prob\left[\Ind_{\lbrace R\leq t\rbrace}\vert X,A\right] = \Var_{\Prob_\beta}\left[\Ind_{\lbrace R\leq t\rbrace}\vert X,A\right]$.

§ LIPSCHITZ RISK FUNCTIONALS

We now introduce Lipschitz risk functionals,
a novel class of objectives
for which absolute differences in the risk
are bounded by sup norm differences in the CDF of rewards.
After formally defining the class,
we provide an in-depth review
of common risk functionals
and their relationship
to the of rewards.
When possible, we derive
the associated Lipschitz constants,
when rewards are bounded on support $[0, D]$,
relegating all proofs to Appendix <ref>.

§.§ Defining the Lipschitz Risk Functionals

The Lipschitz risk functionals are a subset
of the broader family of
law-invariant risk functionals.
Formally, let $Z\in \L_\infty(\Omega, \F_Z,\Prob_Z)$
denote a real-valued random variable that admits a $F_Z\in \L_\infty(\Real, \Borel(\Real))$.
A risk functional $\rho$
is a mapping from a space of random variables to the space of real numbers
$\rho: \L_\infty(\Omega, \F_Z,\Prob_Z) \rightarrow \Real$.
Any risk functional $\rho$
is said to be law-invariant if $\rho(Z)$ depends
only on the distribution of $Z$ <cit.>.

A risk functional
$\rho:\L_\infty(\Omega, \F,\Prob)  \rightarrow \Real$,
is law-invariant
if for any pair of random variables $Z$ and $Z'$,
F_Z = F_{Z'}\;\Longrightarrow\; \rho(Z)=\rho(Z').

When clear from the context,
we sometimes abuse notation
by writing $\rho(F_Z)$
in place of $\rho(Z)$.
In general, it may not be practical
to estimate risk functionals
that are not law invariant
from data <cit.>.
Thus focusing on law-invariant risks
is only mildly restrictive.

We can now formally define
the Lipschitz risk functionals:

A law invariant risk functional $\rho$ is $L$-Lipschitz
if for any pair of s $F_Z$ and $F_{Z'}$ and some $L \in (0, \infty)$,
it satisfies

\begin{align*}
|\rho(F_Z)-\rho(F_{Z'})|\leq L \|F_Z-F_{Z'}\|_\infty.
\end{align*}

A risk functional is $L$-Lipschitz if,
for any two random variables $Z, Z'$,
its value is upper bounded
by the sup-norm of the difference between
their corresponding CDFs.
The significance of this Lipschitzness property
in the contextual bandit setting is that,
given a high confidence bound on the error
of the estimated CDF of rewards for a policy $\pi$,
we can obtain a high confidence bound on its evaluation
under any $L$-Lipschitz law-invariant risk functional
on the distribution of rewards.

§.§ Overview of Common Risk Functionals (and their Lipschitzness)

We now briefly describe some popular classes
of risk functionals and their axiomatic definitions. When possible, we
derive their associated Lipschitz constants.

First, we enumerate
a set of prominent axioms
explored in the current literature
Consider a pair of random variables $Z$ and $Z'$,
we have the following axioms:

*  Monotonicity: $\rho(Z) \leq \rho(Z')$ whenever $Z \leq Z'$.

*  Subadditivity: $\rho(Z+Z') \leq \rho(Z) + \rho(Z')$.

*  Additivity: $\rho(Z+Z') =\rho(Z) + \rho(Z')$ if $Z$ and $Z'$ are co-monotonic random variables
(i.e., there exists a random variable $Y$
and weakly increasing functions $f, g$
such that $Z = f(Y)$ and $Z' = g(Y)$).

* Translation invariance:
$\rho(Z + c) = \rho(Z) + c, \forall c \in \Real$.

* Positive homogeneity:
$\rho(tZ) = t\rho(Z)$ for $t > 0$.

*  Bounded above by the maximum cost,
i.e., $\rho(Z)\leq \max(Z)$.

*  Bounded below by the mean cost,
i.e., $\rho(Z)\geq \E[Z]$.

From this set of axioms,
one can define a class of risk functionals
by choosing the subset best suited
to the problem at hand.

Coherent Risk Functionals.
The set of risk functionals that satisfy
monotonicity (Axiom <ref>),
subadditivity (Axiom <ref>),
translation invariance (Axiom <ref>),
and positive homogeneity (Axiom <ref>), and positive homogeneity
(see Appendix <ref>),
constitute the coherent risk functionals <cit.>. Further, if a law-invariant coherent risk functional
additionally satisfies Additivity (Axiom <ref>),
it is said to be a spectral risk functional <cit.>.

While not all coherent risk functionals
are law-invariant,
nearly all of those commonly
addressed in the literature are.
Examples include expected value,
conditional value-at-risk (CVaR),
entropic value-at-risk,
and mean semideviation <cit.>.
Others include the Wang transform function <cit.>
and the proportional hazard (PH)
risk functional <cit.>.

Distorted Risk Functionals.
When the random variable $Z$
is required to be non-negative,
law-invariant coherent risk functionals
are examples of the more general class
of law-invariant distorted risk functionals
For $Z \geq 0$, a distorted risk functional has the following form

\begin{align*}
\rho(F_Z) = \int_0^\infty g(1-F_Z(t))dt,
\end{align*}

where the distortion function $g:[0,1]\rightarrow[0,1]$
is an increasing function with $g(0)=0$ and $g(1)=1$.
Distorted risk functionals are coherent
if and only if $g$ is concave <cit.>.
For example, when $g(s) = \min\{\frac{s}{1-\alpha},1\}$
for $s\in[0,1]$ and $\alpha \in (0, 1)$,
$\CVaR$ at level $\alpha$ is recovered.
When $g$ is the identity map,
the distorted risk functional
is the expected value.
The Wang risk functional at level $\alpha$ <cit.>
is recovered when $g(s)=F(F^{-1}(s)-F^{-1}(\alpha))$,
and the proportional hazard risk functional
can by obtained by setting $g(s)=s^\alpha$ for $\alpha < 1$.
Not all distorted risk functionals are coherent.
For example, setting $g(s)=\Ind_{\{s\geq 1-\alpha\}}$
recovers the value-at-risk (VaR),
which is not coherent.

Distorted risk functionals have many desirable theoretical properties.
They are translation invariant (Axiom <ref>)
and positive homogeneous (Axiom <ref>),
and are defined utilizing (Axiom <ref>)
and (Axiom <ref>) <cit.>.
They satisfy Axiom <ref>
if and only if $g(s)\geq s~\forall s\in[0,1]$ <cit.>,
and are subadditive (Axiom <ref>)
if and only if $g$ is concave,
which preserves second order stochastic dominance <cit.>.
In addition, all distorted risk functionals
preserve stochastic first order dominance <cit.>.

On the space of random variables with support in $[0,D]$,
the distorted risk functional of any $\frac{L}{D}$-Lipschitz distortion function $g:[0,1]\rightarrow[0,1]$, i.e., $|g(t)-g(t')|\leq \frac{L}{D}|t-t'|$,
is a $L$-Lipschitz risk functional.

Both expected value and CVaR are examples of distorted risk functionals.
Then using Lemma <ref>,
on the space of random variables with support in $[0,D]$,
the expected value risk functional is $D$-Lipschitz
because $g$ is the identity and thus 1-Lipschitz.
On the same space, the risk functional $\cvara$
is $\frac{D}{\alpha}$-Lipschitz
because $g$ is $\frac{1}{\alpha}$-Lipschitz.

Cumulative Prospect Theory (CPT) Risk Functionals.
CPT risks <cit.> take the form:

\begin{align*}
\rho(F_Z) = \int_0^{+\infty}g^+\left(1 - F_{u^+(Z)}(t)
\right)dt - \int_0^{+\infty}g^-\left(1 - F_{u^-(Z)}(t)\right) dt,
\end{align*}

where $g^+, g^-$: $[0, 1] \rightarrow [0, 1]$,
$g^{+/-}(0) = 0$,
and $g^{+/-}(1) = 1$.
The functions $u^+, u^-: \Real \rightarrow \Real_+$ are continuous,
with $u^+(z) = 0$ when $z \geq c$ and $u^-(z) = 0$
when $z < c$ for some constant $c \in \Real$.
Importantly, the CPT functional handles gains and losses separately.
The functions $u^+, u^-$ compare the random variable $Z$
to a baseline $c$,
and the distortion $g^+$ is applied to “gains”
(when $Z \geq c$),
while $g^-$ is applied to “losses” (when $Z < c$).

Note that the distortions $g^+, g^-$ may not necessarily be monotone functions.
As a result, the distortion functionals can be seen as
a special case of the CPT functional
when $Z$ is nonnegative,
$c = 0$,
and $g$ is an increasing function.
Appropriate choices of $g^+, g^-$
can again be used to recover risk functionals such as the CVaR and VaR.
We make note of the fact that, in the CPT literature,
$g^{+/-}$ is chosen to necessarily have a fixed point
where $g^{+/-}(s) = s$ for some $s \in (0, 1)$,
although we do not make this assumption here.

In general, due to the general form of $g^{+/-}$ and the separate consideration of losses and gains, the CPT-inspired risk functional may not satisfy any of the defined axioms. However, additional assumptions on the distortions $g^+$ and $g^-$ may allow certain axioms to be satisfied. For example, if the random variable has nonnegative support and the threshold $c$ is set to be 0 so that only gains are observed, and $g^+$ is additionally increasing, we recover the distorted risk functionals with axioms specified above. If $g^+$ is additionally concave, then we recover the coherent risk functionals.

On the space of random variables with support in $[0,D]$,
if the CPT distortion functions $g^+$ and $g^-$
are both $\frac{L}{D}$-Lipschitz,
then the CPT risk functionals is $L$-Lipschitz.

Other Risk Functionals.
The variance, mean-variance,
and many other popular risks
do not fit easily into
the aforementioned classes,
but are nevertheless law-invariant.
For example, for a nonnegative random variable $Z$,
the variance is defined as
$\rho(F_Z) = 2\int_{0}^\infty t(1-F_Z(t))dt - \left(\int_{0}^\infty (1-F_Z(t))dt \right)^2.$
Moreover, the variance and mean-variance
are both $L$-Lipschitz.

On the space of random variables with support in $[0,D]$,
variance is a $3D^2$-Lipschitz risk functional.

A number of recent papers
have addressed risk functionals
expressed as weighted combinations
of others, e.g., mean-variance <cit.>.
Other papers have optimized constrained objectives,
such as expected reward constrained by variance
or CVaR below a certain threshold
When expressed as Lagrangians,
these objectives can also be expressed
as weighted combinations
of the risk functionals involved.
We extend the Lipschitzness property
to risk functionals of this form:

Let $\rho$ be a weighted sum
of risk functionals $\rho_1,...,\rho_K$
that are $L_1,...,L_K$-Lipschitz, respectively,
with weights $\lambda_1,....,\lambda_K > 0$, i.e.,
$\rho(Z) = \sum_{k=1}^K \lambda_k \rho_k(Z)$.
Then $\rho$ is $\sum_k \lambda_k L_k $-Lipschitz.

Note that mean-variance is given
by $\rho(Z) = \E[Z] + \lambda \Var(Z)$
for some $\lambda > 0$.
Then, using Lemma <ref>,
we immediately obtain that mean-variance
is $(1 + 3\lambda D^2)$-Lipschitz
for bounded random variables.

Though we have provided many examples of Lipschitz risk functionals in this section, it is worth noting that there are a number of risk functionals that do not satisfy the Lipschitzness property, such as the value-at-risk (VaR).
For the sake of brevity, we omit consideration of such risk functionals in this paper, and outline future avenues of research on this topic in the discussion.

§ OFF-POLICY CDF ESTIMATION

This section describes our method for
high-confidence off-policy estimation of $F$,
the CDF of returns under the policy $\pi$.
The key challenge in estimating $F$
is that the reward samples are observed
only for actions taken by the behavior policy $\beta$.
To overcome this limitation,
one intuitive solution is to reweight
the observed samples according to
their importance sampling (IS) weight (Section <ref>).
However, IS estimators are known to suffer from high variance.
To mitigate this, we define the first doubly robust CDF estimator (Section <ref>).

§.§ CDF Estimation with Importance Sampling (IS)

Given an off-policy dataset $\mathcal{D} = \lbrace x_i, a_i, r_i \rbrace_{i=1}^n$,
we define the following nonparametric IS-based estimator for the empirical CDF,

\begin{equation}\label{is_estimator}
\widehat{F}_{\text{IS}}(t) := \frac{1}{n}\sum_{i=1}^n w\left(a_i, x_i\right)\mathbbm{1}_{\{r_i \leq t\}},
\end{equation}

where $w(a, x) = \frac{\pi(a|x)}{\beta(a|x)}$ are the importance weights.
The IS estimator is pointwise-unbiased,
with variance given below:

The IS estimator (<ref>) is unbiased and its variance is

\begin{align*}
\Var_{\Prob_\beta}\left[\wh{F}_{\text{IS}}(t)\right] &= \frac{1}{n}\E_{\Prob_\beta}\left[w(A,X)^2 \sigma^2(t;X,A) \right] + \frac{1}{n}\Var_{\Prob_\beta}\left[\E_{\Prob_\beta}\left[w(A,X) G(t;X,A)\vert X\right]\right] \\
&\quad\quad+ \frac{1}{n}\E_{\Prob_\beta}\left[\Var_{\Prob_\beta}\left[w(A,X) G(t;X,A)\vert X\right]\right]
\end{align*}

The expression for variance is broken down into three terms.
The first term represents randomness in the rewards.
The second term represents variance
due to the randomness over contexts $X$.
The final term is the penalty arising
from using importance sampling,
and is proportional to the importance sampling weights $\weight$
and the true CDF of conditional rewards $G$.
The variance contributed by the third term
can be large
when the weights $\weight$
have a wide range, which occurs
when $\beta$ assigns extremely small probabilities
to actions where $\pi$ assigns high probability.

Due to the use of importance sampling weights,
the estimated CDF $\widehat{F}_{\text{IS}}(t)$
may be greater than 1 for some $t$,
even though a valid must be in the interval $[0, 1]$ for all $t$.
To mitigate this problem, a weighted importance sampling () estimator can be used,
which normalizes each importance weight by the sum of importance weights:

\begin{align*}
\wh{F}_\WIS(t) = \frac{1}{\sum_{j=1}^n w(a_j, x_j) } \sum_{i=1}^n w(a_i, x_i) \mathbbm{1}_{\{r_i \leq t\}},
\end{align*}

which <cit.> shows is a biased but uniformly consistent estimator. Another option is the clipped estimator IS-Clip (<ref>), which simply limits the estimator to the unit interval:

\begin{equation}\label{is_clip_estimator}
\widehat{F}_{\ISclip}(t) := \min\{\widehat{F}_{\IS}(t), 1\}
\end{equation}

Although $\widehat{F}_{\ISclip}$
has lower variance than the IS estimator, it is potentially biased.

However, given finite samples,
we can bound with high confidence the sup-norm error between $\wh{F}_\ISclip$ and $F$,
in Theorem <ref> below (proof in Appendix <ref>):

Given $n$ samples drawn from $\Prob_\beta$,
for the estimator $\wh F_{\IS}(t)$, we have

\begin{equation}\label{eq:IS-concentration}
\Prob_\beta\left(\Vert \wh{ F}_{\ISclip} -  F\Vert_{\infty} \leq \varepsilon_{\IS_1}:= \sqrt{\frac{8\weight^2_{\max}}{n}\log(4/\delta)}\right)\geq  1-\delta.
\end{equation}

or, based on $w_{\mathbbm{2}}$, we obtain a Bernstein-style bound,

\begin{align}\label{eq:IS-concentration-Bernstein}
\Prob_\beta\left(\left\Vert\wh{ F}_{\ISclip} -  F \right\Vert_\infty  \leq \varepsilon_{\text{IS}_2}:= \frac{4\weight_{\max}\log(4/\delta)}{n}+2\sqrt{\frac{2w_{\mathbbm{2}}\log(4/\delta)}{n}}\right)\geq 1-\delta
\end{align}

When $w_{\mathbbm{2}} \ll w_{max}$, we observe that inequality (<ref>) is more favorable than  inequality (<ref>).
Theorem <ref> demonstrates that the $\wh{F}_\ISclip$ uniformly converges to the true at a rate of $O(1/\sqrt{n})$, with the uniform consistency of $\wh{F}_\ISclip$ as an immediate consequence.
To the best of our knowledge, it is the first
DKW-style concentration inequality
on the importance sampling estimator estimator
in off-policy evaluation.
The bound has explicit constants
and subsumes the classical DKW inequality.

§ OFF-POLICY RISK ASSESSMENT

Given any law-invariant risk functional $\rho$
CDF estimator $\wh{F}$,
we can estimate the value of the risk functional as $\wh\rho:=\rho(\wh F)$.
However, the estimator $\wh\rho$ may be biased
even if $\wh F$ is unbiased.
For Lipschitz risk functionals introduced in Section <ref>,
we can obtain their
finite sample error bounds,
using the error bound of the CDF estimator.
Further, a set of risk functionals of interest can be evaluated using the same estimated CDF,
which suggests that the error bound of the CDF gives error bounds on the risk estimators that hold simultaneously.

Theorem <ref>
error bound
of the estimated CDF to derive error bounds
for estimators of a set of Lipschitz risk functionals.
As we showed in Section <ref>,
most if not all commonly studied risk functionals
satisfy the property of Lipschitzness,
showing our result's wide applicability.

Given a set of Lipschitz risk functionals
$\lbrace \rho_p \rbrace_{p=1}^P$
with Lipschitz constants $\lbrace L_p\rbrace_{p=1}^P$,
and a CDF estimator $\wh{F}$,
such that $\Vert \widehat{F} - F \Vert_\infty \leq \epsilon$
with probability at least $1-\delta$,
we have with probability at least $1-\delta$ that for all $p \in \{1, \ldots P\}$,

\begin{equation*}\label{eq:confidence_general}
\left\vert \rho_p(\wh{F}) - \rho_p(F) \right\vert \leq L_p\epsilon.
\end{equation*}

one powerful property of risk estimation
using the estimated CDF approach
is that,
given a high-probability error bound on the CDF estimator,
the corresponding error bounds on estimates of all Lipschitz risk functionals of interest
hold simultaneously with the same probability.
Further, because the error of the IS
CDF estimator $\epsilon_{\text{IS}}$ (Theorem <ref>) and DR CDF estimator $\epsilon_\text{DR}$ (Theorem <ref>)
converge at a rate of $O(1/\sqrt{n})$,
Theorem <ref> shows that the error of all Lipschitz risk functional estimators
shrink at a rate of $O(1/\sqrt{n})$.
Thus, $\rho_p(\wh F)$ are consistent risk functional estimators.

Putting these results together, we now provide an algorithm,
called OPRA (Algorithm <ref>),
which given an off-policy contextual bandit dataset
and a set of Lipschitz risk functionals
of interest,
outputs for each risk functional an estimate of its value
and a confidence bound.
The algorithm first uses a valid CDF estimator,
e.g., the clipped IS estimator (<ref>) or monotonized DR estimator (<ref>),
to form $\wh{F}$ with sup-norm error $\epsilon$.
OPRA then evaluates each $L_p$-Lipschitz risk functional $\rho_p$ on $\wh{F}$ to obtain $\wh\rho_p$,
along with its upper and lower confidence bound
$\wh\rho_p \pm L_p\epsilon$.

Dataset $\mathcal{D}$, policy $\pi$, probability $\delta$, models $\overline{G}$,
Lipschitz risk functionals $\lbrace \rho_p\rbrace_{p=1}^P$ with Lipschitz constants $\lbrace L_p \rbrace_{p=1}^P$.
Estimate the CDF using a valid estimator $\wh{F}$
Compute the corresponding CDF estimation error $\epsilon$ such that $\mathbb{P}(\Vert F - \wh F\Vert_\infty < \epsilon) \geq 1-\delta$
p = 1 …P
Estimate $\wh{\rho}_p = \rho_p(\wh{F})$

Estimates with errors $\lbrace \wh{\rho}_p \pm L_p \epsilon\rbrace_{p=1}^P$.
Off-Policy Risk Assessment (OPRA)

OPRA can be used to obtain a full risk assessment of any given policy, using the input Lipschitz risk functionals of interest,
which can include the popularly used mean, variance, and CVaR.
As demonstrated in Theorem <ref>,
the error guarantee on the risk estimators
holds simultaneously for all $P$ risk functionals
with probability at least $1-\delta$.
Importantly, OPRA also demonstrates the computational efficiency
of the distribution-centric risk estimation approach proposed in this paper.
For a given $\pi$, the CDF only needs to be estimated once,
and can be used repetitively
to estimate the value of the risk functionals.
Further, the error of the risk estimators are
determined by the known error of the CDF estimator,
multiplied by the known Lipschitz constants.

We have focused our discussion on the estimation
of $L$-Lipschitz risk functionals
due their generalizability and flexibility,
and because we can characterize the rate at which the error decreases.
Any law-invariant risk functional can actually be estimated using the CDF estimate, although the error or confidence of the estimate
may have to be determined on a case-by-case basis
for each risk functional of interest.
Further, the rate at which the error converges may not necessarily be known.

Although we work with known behavioral policy $\beta$ in this paper,
previous works on off-policy evaluation have considered the case where the behavioral policy is unknown.
In such cases, an estimate or model of the policy, called $\wh\beta$, is instead used in CDF and risk estimation.
In Appendix <ref> we extend the bias, variance, error bound results to this setting.

§ EMPIRICAL STUDIES

In this section, we give empirical evidence
for the effectiveness of the doubly robust () and risk estimates,
in comparison to the importance sampling (),
weighted importance sampling (),
and direct method () estimates.
Further, we demonstrate
the convergence of the
and risk estimation error
in terms of the number of samples.

Following <cit.>,
we obtain our off-policy contextual bandit datasets
by transforming classification datasets.
The contexts are the provided features,
and the actions correspond to the possible class labels.
To obtain the evaluation policy $\pi$,
we use the output probabilities
of a trained logistic regression classifier.
The behavior policy is defined as
$\beta = \alpha \pi + (1-\alpha)\pi_{\text{UNIF}}$,
where $\pi_{\text{UNIF}}$
is a uniform policy over the actions,
for some $\alpha \in (0, 1]$.
We apply this process to the PageBlocks
and OptDigits datasets <cit.>,
which have dimensions $d$ and actions $k$
using $\alpha = 0.1$
(Figure <ref>).
When models $\overline{G}$ are used
(for DM, DR estimators),
as in <cit.>,
the dataset is divided into two splits,
with each of the two splits
used to calculate $\overline{G}$ via regression,
which is then used
with the other split
to calculate the estimator.
The two results are averaged
to produce the final estimators.
We provide further details
and extensive evaluations
in Appendix <ref>.

CDF Estimation.
We evaluate the error $\Vert F - \wh F\Vert_\infty$
of our estimators against sample size
for two UCI datasets (Figure <ref>).
The and exhibit the expected
$O\left(1/\sqrt{n}\right)$ rate of convergence
in error previously derived
in Theorems <ref>
and <ref>, respectively.
We note that the estimator, while biased,
performs as well as the estimator if not better.
In the PageBlocks dataset (Figure <ref>, left),
the regression model for $\overline{G}$
is relatively well-specified
as exemplified by the relatively low error of the $\DM$ estimator, though it has high variance for low samples sizes.
The estimator leverages this model to outperform
all other estimators for all sample sizes,
without suffering the drawbacks of the estimator.
It takes an order of magnitude less data
to reach the same error
compared to the and estimators.
In contrast, the regression model
is less well-specified in the OptDigits dataset for lower sample sizes
(Figure <ref>, right),
and consequently,
the $\DR$ estimator cannot perform as well
as the and estimators for small $n$.
This trend reverses as data increases and the model improves,
with the estimator outperforming
the estimators.

The error of the CDF estimators as a function of sample size $n$, for (left) the PageBlocks dataset and (right) the OptDigits dataset. Shaded area is the 95% quantile over 500 runs.

Estimated mean, $\text{CVaR}_{0.5}$, and variance for the OptDigits dataset, compared to their true values (black). Shaded area is the standard deviation over 500 runs.

Estimation of Risk Functionals.
Figure <ref> shows the
mean, variance, and $\text{CVaR}_{0.5}$ estimates,
which are obtained by evaluating each risk functional
on the estimators for the OptDigits dataset.
Here, the estimates are plotted against the true value (dashed line)
to make the variance reduction effect of the estimators more apparent.
The estimator, which appeared to have competitive performance in the error plot,
has relatively high risk estimate error,
which occurs because the may be poorly approximated
in areas that are important for risk functional estimation.
The , , and risk estimates
converge quickly to the true value as $n$ increases,
and as expected,
their relative behavior echoes the trends in Figure <ref> as a consequence of our distributional approach.
The estimator has slightly worse performance for small samples sizes due to the poor specification of the model, but soon exhibits
the desired variance reduction for $n > 1000$.

§ DISCUSSION

In this paper, we have developed a distribution-centric method for high confidence off-policy estimation of risk functionals.
Our method relies on first estimating the CDF and its confidence band, then estimating risk functionals by evaluating on the estimated CDF.
We have defined several estimators for the CDF, including an importance sampling and doubly robust estimator which takes advantage of side information to reduce variance.
For $L$-Lipschitz risk functionals, which we show many classes of risks fall under, the concentration of the estimated risk can be derived from the confidence band on the CDF.

From a theoretical point of view, our paper provides the first finite sample concentration inequalities for a number of different CDF and risk estimators, which are widely applicable to recent distributional reinforcement learning settings, which learn the CDF of returns and are capable of optimizing different risk functionals <cit.>.
Of these estimators, the doubly robust estimator is a novel contribution and has not yet been defined or analyzed for distributions in the literature.
From a practical standpoint, our method
can be used to comprehensively evaluate
the behavior of a target policy before deployment
using a wide range of risk functionals–a contribution that is especially important in real-world applications.

Our work also raises
several open questions and avenues of future work,
which we discuss below.

Error Bound for the Doubly Robust CDF Estimator.
Although we presented a sample-dependent bound, we believe that it can be improved because our current bound does not take into account the double robustness of the estimator.
We obtain a looser bound for the DR estimator compared to the IS estimator, even though we show the DR estimator has reduced pointwise variance.
Obtaining an improved error bound dependent on the term $G-\wb{G}$, which is the error of the given model compared to the true conditional , is one important direction of future work.

Monotone Transformation of the CDF Estimate.
As we have demonstrated for
the importance sampling and doubly robust estimators,
estimation faces a unique problem in that the
estimate may not be a valid .
Estimates of the expected value,
for example,
are not subject to any such constraints.
We have shown how methods
such as clipping and monotone transformation
can be applied to $\wh{F}_{\text{IS}}$ or $\wh{F}_{\text{DR}}$
to mitigate this problem.

However, it is important to note that
there are, in fact, several options
for how the clipping and monotone transformation is applied.
For example, instead of applying these transformations after averaging the $n$ samples to form the estimator,
another option is to apply the transformation to each individual sample,
and then average the transformed results.
Applying the monotone transformation to each sample before averaging may potentially increase bias while reducing variance, which may be desirable in certain applications.

In this paper we proposed a simple method (<ref>) for clipping and transforming the  estimate, but different forms of monotone regression <cit.>,
which may potentially provide a better monotone approximation of the CDF estimate.
As of yet, the best method of transforming estimates into valid s is not yet clear.
Extensive theoretical and empirical evaluation of such estimator options is another important avenue of future work.

CDF and Risk Estimation in MDPs. Previous work in off-policy evaluation for expected value has developed a doubly robust estimator for the MDP setting <cit.>. Following this, another avenue of future work will aim to extend our results for the contextual bandit setting to CDF and risk estimation in the Markov Decision Process (MDP) and nonstationary settings.
We believe this is especially relevant in relation to recent advances in distributional reinforcement learning, that aims to learn the distribution of returns in MDPs <cit.>.

CDF and Risk Estimation with Unknown Behavioral Policy.
Along similar lines, another direction of future work lies in in-depth analysis of the importance sampling and doubly robust estimators when the behavioral policy is unknown and must be estimated from the data. Previous works have shown that under mild consistency assumptions, using estimates of importance weight asymptotically provides a better estimator of policy evaluate <cit.>. Whether similar properties hold under CDF and risk estimation remains to be seen.

Risk Error Bounds Without Lipschitzness.Finally, though we provide concentration bounds for a large number of risk functionals under the $L$-Lipschitz property,
a number of other risk functionals, such as the inverse quantile function, do not satisfy this property.
The confidence band on the CDF can still be used to calculate a confidence interval on the risk,
but it is not clear if and how quickly the confidence interval shrinks with more samples.
This motivates the following open question, which we plan to study in future work: can concentration inequalities for risk functional estimates be derived if and only if they are Lipschitz, in a more general sense?

§ ACKNOWLEDGEMENTS

The authors thank Siva Balakrishnan for inspiring discussions,
and Roberto Imbuzeiro Oliveira for his lecture notes.
Liu Leqi is generously supported by an Open Philanthropy AI Fellowship. Zachary Lipton thanks Amazon AI, Salesforce Research, the Block Center, the PwC Center, Abridge, UPMC, the NSF, DARPA, and SEI for supporting ACMI lab’s research on robust and socially aligned machine learning.


# A doubling construction for Williamson matrices

Curtis Bright
University of Waterloo

###### Abstract

A construction that generates Williamson matrices of order $2n$ from
Williamson matrices of odd order $n$ is presented. The construction is
completely constructive and only uses three simple sequence operations.

##  1 Introduction

Four square, symmetric, and circulant matrices of order $n$ with $\pm 1$
entries are known as _Williamson matrices_ if they satisfy

$A^{2}+B^{2}+C^{2}+D^{2}=4nI_{n}$

where $I_{n}$ is the identity matrix of order $n$. Such matrices were first
introduced by Williamson (1944), who proved that such matrices can be used to
constuct a Hadamard matrix (a square matrix with $\pm 1$ entries whose rows
are pairwise orthogonal) of order $4n$. Since Williamson matrices are
circulant they are defined in terms of their first row and so it is convenient
to instead think of Williamson matrices in terms of four sequences
$(a_{0},\dotsc,a_{n-1})$, $(b_{0},\dotsc,b_{n-1})$, $(c_{0},\dotsc,c_{n-1})$,
$(d_{0},\dotsc,d_{n-1})$. Since Williamson matrices are symmetric these
sequences are also symmetric (i.e., $x_{k}=x_{n-k}$ for $k=1$, $\dotsc$,
$n-1$).

##  2 Preliminaries

A doubling construction for Hadamard matrices was originally given by
Sylvester (1867) who showed that a Hadamard matrix of order $2n$ can be
constructed from a Hadamard matrix of order $n$. Baumert and Hall (1965)
provided a doubling construction for generalizations of Williamson matrices
which are often referred to as _Williamson-type_ matrices (Seberry and Yamada,
1992, Def. 3.3). Using complex Hadamard matrices, Turyn (1970) provided a
construction which generates Williamson matrices of order $2^{k}n$ for $k=1$,
$2$, $3$, $4$ from Williamson matrices of odd order $n$. In this paper we
provide a simple doubling construction which works directly on the sequences
which define Williamson matrices.

###  2.1 Correlation

Williamson matrices can also be defined in terms of a correlation function.
The _periodic cross-correlation function_ of two sequences
$X=(x_{0},\dotsc,x_{n-1})$ and $Y=(y_{0},\dotsc,y_{n-1})$ is defined to be

$\operatorname{PCF}_{X,Y}(s)\coloneqq\sum_{k=0}^{n-1}x_{k}y_{k+s\bmod n}$

and the _periodic autocorrelation function_ of $X$ be a sequence is
$\operatorname{PAF}_{X}(s)\coloneqq\operatorname{PCF}_{X,X}(s)$. In (Bright,
2017, §3.1.1) it is shown that four symmetric sequences $A$, $B$, $C$,
$D\in\\{\pm 1\\}^{n}$ form the initial rows of a set of Williamson matrices if
and only if they satisfy

$\operatorname{PAF}_{A}(s)+\operatorname{PAF}_{B}(s)+\operatorname{PAF}_{C}(s)+\operatorname{PAF}_{D}(s)=0$

for $s=1$, $\dotsc$, $\lfloor n/2\rfloor$. We refer to such sequences as
_Williamson sequences_.

###  2.2 Sequence operations

Let $A=(a_{0},\dotsc,a_{n-1})$ and $B=(b_{0},\dotsc,b_{n-1})$ be sequences of
order $n$. Our construction uses the following 3 types of operations.

  1. 1.

Negation. Individually negate each entry of $A$, i.e.,
$-A\coloneqq(-a_{0},\dotsc,-a_{n-1})$.

  2. 2.

Shift. Cyclically shift the entries of $A$ by an offset of $k$, i.e.,
$(a_{k},a_{k+1},\dotsc,a_{k-1})$ with indices taken modulo $n$.

  3. 3.

Interleave. Interleave the entries of $A$ and $B$ in a perfect shuffle, i.e.,

$A\mathbin{\text{x}}B\coloneqq(a_{0},b_{0},a_{1},b_{1},\dotsc,a_{n-1},b_{n-1}).$

If $n$ is odd we let $A^{\prime}$ denote shifting $A$ by an offset of
$(n-1)/2$, i.e.,

$A^{\prime}\coloneqq(a_{(n-1)/2},\dotsc,a_{n-1},a_{0},a_{1},\dotsc,a_{(n-3)/2}).$

Note that we have $\operatorname{PAF}_{-A}(s)=\operatorname{PAF}_{A}(s)$,
$\operatorname{PAF}_{A^{\prime}}(s)=\operatorname{PAF}_{A}(s)$, and

$\operatorname{PAF}_{A\mathbin{\text{x}}B}(s)=\begin{cases}\operatorname{PAF}_{A}(s/2)+\operatorname{PAF}_{B}(s/2)&\text{when
$s$ is even},\\\
\operatorname{PCF}_{A,B}\big{\lparen}\frac{s-1}{2}\big{\rparen}+\operatorname{PCF}_{B,A}\big{\lparen}\frac{s+1}{2}\big{\rparen}&\text{when
$s$ is odd}.\end{cases}$

##  3 Doubling construction

Our doubling construction is captured by the following theorem.

######  Theorem 1.

Let $A$, $B$, $C$, $D$ be Williamson sequences of odd order $n$. Then

$A\mathbin{\text{x}}B^{\prime},\,(-A)\mathbin{\text{x}}B^{\prime},\,C\mathbin{\text{x}}D^{\prime},\,(-C)\mathbin{\text{x}}D^{\prime}$

are Williamson sequences of order $2n$.

###### Proof.

The fact that the constructed sequences have $\pm 1$ entries are of length
$2n$ follows directly from the properties of the three types of operations
used to generate them. The fact that they are symmetric follows from the fact
that the sequences $X$ which appear to the left of $\mathbin{\text{x}}$
satisfy $x_{k}=x_{n-k}$ for $k=1$, $\dotsc$, $n-1$ and the sequences $Y$ which
appear to the right of $\mathbin{\text{x}}$ satisfy $y_{k}=y_{n-k-1}$ for
$k=0$, $\dotsc$, $n-1$ which are exactly the necessary properties for
$X\mspace{-1.0mu}\mathbin{\text{x}}\mspace{1.0mu}Y$ to be symmetric.

Let $L$ be the list containing the constructed sequences of order $2n$. To
show these sequences are Williamson we need to show that

$\sum_{X\in L}\operatorname{PAF}_{X}(s)=0$

for $s=1$, $\dotsc$, $n$. When $s$ is even and in this range using the
properties from Section 2.2 we obtain

$\sum_{X\in
L}\operatorname{PAF}_{X}(s)=2\sum_{X=A,B,C,D}\operatorname{PAF}_{X}(s/2)=0$

since $A$, $B$, $C$, $D$ are Williamson. When $s$ is odd we have that

$\operatorname{PAF}_{(-X)\mathbin{\text{x}}Y}(s)=-\operatorname{PAF}_{X\mathbin{\text{x}}Y}(s)$

and using this for $(X,Y)=(A,B^{\prime})$ and $(C,D^{\prime})$ derives the
desired property. ∎

We remark that unlike the doubling constructions given by Sylvester and
Baumert–Hall our doubling construction cannot be applied repeatedly because it
only applies when $n$ is odd. When $n$ is even it is not possible to apply a
shift to a symmetric sequence $Y$ of order $n$ to obtain a sequence
$Y^{\prime}$ which satisfies $y^{\prime}_{k}=y^{\prime}_{n-k-1}$ for $k=0$,
$\dotsc$, $n-1$ and this property is necessary to make the constructed
sequences symmetric.

## References

  * Baumert and Hall (1965) LD Baumert and Marshall Hall.  Hadamard matrices of the Williamson type.  _Mathematics of Computation_ , 19(91):442–447, 1965.
  * Bright (2017) Curtis Bright.  _Computational Methods for Combinatorial and Number Theoretic Problems_.  PhD thesis, University of Waterloo, 2017.
  * Seberry and Yamada (1992) Jennifer Seberry and Mieko Yamada.  Hadamard matrices, sequences, and block designs.  _Contemporary design theory: a collection of surveys_ , pages 431–560, 1992.
  * Sylvester (1867) James Joseph Sylvester.  Thoughts on inverse orthogonal matrices, simultaneous signsuccessions, and tessellated pavements in two or more colours, with applications to Newton’s rule, ornamental tile-work, and the theory of numbers.  _The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science_ , 34(232):461–475, 1867.
  * Turyn (1970) Richard J. Turyn.  Complex Hadmard matrices.  In _Combinatorial structures and their applications_ , pages 435–437. Gordon and Breach, 1970.
  * Williamson (1944) John Williamson.  Hadamard’s determinant theorem and the sum of four squares.  _Duke Math. J_ , 11(1):65–81, 1944.


# Universal systole bounds
for arithmetic locally symmetric spaces

Sara Lapan  Department of Mathematics
University of California
Riverside, CA 92521<EMAIL_ADDRESS>,  Benjamin Linowitz  Department of
Mathematics
Oberlin College
Oberlin, OH 44074<EMAIL_ADDRESS>and  Jeffrey S. Meyer
Department of Mathematics
California State University
San Bernardino, CA 92407<EMAIL_ADDRESS>
###### Abstract.

The systole of a closed Riemannian manifold is the minimal length of a non-
contractible closed loop. We give a uniform lower bound for the systole for
large classes of simple arithmetic locally symmetric orbifolds. We establish
new bounds for the translation length of semisimple
$x\in\operatorname{SL}_{n}(\mathbf{R})$ in terms of its associated Mahler
measure. We use these geometric methods to prove the existence of extensions
of number fields in which fixed sets of primes have certain prescribed
splitting behavior.

##  1\. Introduction

The systole of a closed Riemannian manifold is the minimal length of a non-
contractible closed loop. In this paper, we investigate lower bounds for the
systoles of simple arithmetic locally symmetric orbifolds.

To give some history and motivation, we begin by describing the situation in
dimension 2. If $\Gamma\subset\operatorname{SL}_{2}(\mathbf{R})$ is a lattice
and $\mathbb{H}^{2}$ is the (real) hyperbolic plane, then
$S:=\mathbb{H}^{2}/\Gamma$ is a hyperbolic surface (possibly with cusps or
cone points). An element $x\in\operatorname{SL}_{2}(\mathbf{R})$ is hyperbolic
if it is diagonalizable with positive real eigenvalues. Let $\\{a,a^{-1}\\}$
(where $a>1$) denote the eigenvalues of $x$. If $x\in\Gamma$, then it
corresponds to a closed geodesic in $S$ with length

(1.1) $\ell(x):=2\log|a|.$

It is well known ([14, §12.3] or [16, §4]) that if $\Gamma$ is an arithmetic
lattice derived from a quaternion algebra, then $a$ is an algebraic integer
greater than 1 which is Galois conjugate to its inverse and for which all
other Galois conjugates have norm 1, or in other words, $a$ is a Salem number.
Conversely, Chinburg, Neumann, and Reid showed that every Salem number appears
this way for some arithmetic hyperbolic surface.

The Mahler measure of a monic polynomial
$p(X)=\prod_{i=1}^{n}(X-a_{i})\in\mathbf{C}[X]$ is the product
$M(p):=\prod_{i=1}^{n}\max\\{1,|a_{i}|\\}$. The Mahler measure is a
fascinating function on polynomials that appears throughout algebra, geometry,
and dynamics (see for example the surveys [6] and [20]). If $p_{x}(X)$ is the
characteristic polynomial of $x$, then it follows that (1.1) can be rewritten
in terms of the Mahler measure of $p_{x}$,

(1.2) $\ell(x)=2\log(M(p_{x})).$

Equation (1.2) provides a deep connection between length and the Mahler
measure. If $p$ is a cyclotomic polynomial, then $M(p)=1$. Lehmer’s Problem
asks: is the Mahler measure of irreducible non-cyclotomic monic polynomials
with integer coefficients bounded away from 1? The polynomial

(1.3) $L(X)=X^{10}+X^{9}-X^{7}-X^{6}-X^{5}-X^{4}-X^{3}+X+1$

found by Lehmer (and now called Lehmer’s polynomial) has Mahler measure
$M(L)\approx 1.1762808$. Currently $M(L)$ is the smallest known nontrivial
Mahler measure and it is still an open question if in fact this is the
smallest over all monic polynomials in $\mathbf{Z}[X]$. It follows that
Lehmer’s problem implies the open Short Geodesic Problem, which asks: is there
a universal lower bound for the systoles of arithmetic hyperbolic surfaces?

In [5], Emery, Ratcliffe, and Tschantz extended the identification (1.2) to
$n$-dimensional arithmetic hyperbolic orbifolds of simplest type. In
particular, they were able to get systole bounds in terms of Salem numbers of
bounded degree.

Our goal in this paper is to generalize these results and establish lower
bounds for broad classes of arithmetic locally symmetric spaces. In order to
achieve this goal we need a generalization of (1.2) to semisimple
$x\in\operatorname{SL}_{n}(\mathbf{R})$. In Section 2, we establish such a
generalization with our Mahler-Length Bounds Theorem A below.

######  Theorem A (Mahler-Length Bounds).

If $n\geq 2$, $x\in\operatorname{SL}_{n}(\mathbf{R})$ is semisimple, and
$p_{x}$ denotes the characteristic polynomial of $x$, then

(1.4) $2\sqrt{\frac{2}{n}}\log(M(p_{x}))\leq\ell(x)\leq 2\log(M(p_{x})).$

Let $\\{a_{1},\ldots,a_{n}\\}$ denote the eigenvalues of $x$. The lower bound
is an equality exactly when there exists an $r\in\mathbf{R}$ such that for all
$i$, either $|a_{i}|=r$ or $|a_{i}|^{-1}=r$, and the upper bound is an
equality when $\left|a_{i}\right|=1$ for all but at most two of the $i$.

######  Remark 1.1.

Let $x$ be such that in (1.4) the upper bound is an equality and at least one
of its eigenvalues has modulus not equal to 1. Since $p_{x}$ has real
coefficients, if $a_{i}$ is complex, its complex conjugate $\overline{a_{i}}$
is also an eigenvalue. By our assumption on $x$, it has precisely two
eigenvalues of modulus not equal to 1, and as the eigenvalues must multiply to
1, it follows that $x$ or $-x$ has a unique real eigenvalue greater than 1,
say $\alpha$. When $p_{x}$ has integer coefficients, then $\alpha$ is a Salem
number.

######  Remark 1.2.

Our Mahler-Length Bounds Theorem A is a generalization of (1.2) to degree
$n\geq 2$ just as our Trace-Length Bounds Theorem in [10] was a generalization
of the relationship
$\ell(x)=2\operatorname{arccosh}(\frac{\operatorname{tr}{x}}{2})$ to degree
$n\geq 2$.

In Section 3 we use our Mahler-Length Bounds Theorem A to establish lower
bounds for the systoles of simple arithmetic orbifolds.

######  Theorem B (Universal Systole Bounds).

If $N$ is a simple arithmetic orbifold with field of definition $k$ and
universal cover $\mathfrak{X}$, then

(1.5) $\operatorname{sys}(N,g)\geq\frac{2\sqrt{2}}{\sqrt{n}}f(n),$

where $\operatorname{sys}(N,g)$ denotes the systole of $N$ (as measured
relative to the subspace metric (3.1)),
$n=|k:\mathbf{Q}|\dim(\operatorname{Isom}(\mathfrak{X}))$, and

(1.6) $\displaystyle f(n)=\begin{cases}\log(M(L))>0.16235&\mbox{ if }n\leq
20,\\\ \frac{1}{4}\left(\frac{\log\log n}{\log n}\right)^{3}&\mbox{ if
}n>20,\end{cases}$

where $L(X)=X^{10}+X^{9}-X^{7}-X^{6}-X^{5}-X^{4}-X^{3}+X+1$ is Lehmer’s
polynomial.

To prove this result, we show in Proposition 3.2 that the special linear group
is “universal” in the sense that if $N\cong\mathfrak{X}/\Gamma$ where
$\Gamma\subset\operatorname{Isom}(\mathfrak{X})$ is arithmetic, then $\Gamma$
injects into a special linear group of explicitly bounded degree and each
matrix in the image of this injection has a characteristic polynomial with
integer coefficients.

######  Remark 1.3.

Fix a globally symmetric space $\mathfrak{X}$ of noncompact type. When
$N\cong\mathfrak{X}/\Gamma$ where $\Gamma$ is a principal arithmetic lattice
in the sense of [18, 3.4], then as the volume of $N$ increases, Prasad’s
volume formula [18, 3.11] implies the degree $|k:\mathbf{Q}|$ increases, and
hence $n$ in (1.5) increases, thereby decreasing the systole bound. Hence
Theorem B implies there is a fixed universal lower systole bound for orbifolds
of bounded volume, but as volume is allowed to increase, this bound goes to 0.

In [10, Theorem B] we showed that every simple arithmetic $N$ has a finite
degree cover $N^{\prime}$ such that $\operatorname{sys}(N^{\prime})\geq
c_{1}\log(\operatorname{Vol}(N^{\prime}))+c_{2}$ for certain constants $c_{1}$
and $c_{2}$. In Section 4 we prove that certain covers will always attain
systoles with order of magnitude log of volume.

######  Theorem C (Simple Arithmetic Manifolds with Large Systoles).

If $N$ is a compact simple arithmetic manifold, then $N$ has a finite sheeted
cover $N^{\prime}$ whose systole has order of magnitude
$\log(\operatorname{Vol}(N^{\prime}))$.

A particularly interesting specialization of Theorem B is to the case of
special linear orbifolds derived from central simple algebras. In Section 5 we
give the construction of special linear orbifolds derived from central simple
algebras and give an alternate proof of Theorem D below.

######  Theorem D (Standard Special Linear Short Geodesic Bounds).

If $M$ is a standard special linear orbifold of degree $n$, $n\geq 2$, which
is derived from a central simple algebra, then

(1.7) $\displaystyle\operatorname{sys}(M)\geq\frac{2\sqrt{2}}{\sqrt{n}}f(n),$

where $f(n)$ is as in Theorem B.

Interestingly, the results of this paper can be used to prove a result from
algebraic number theory: for any fixed totally real number field $k$ and
finite set $S$ of primes of $k$, there exists a prime degree field extension
of $k$ in which no prime of $S$ splits completely and whose norm of relative
discriminant may be bounded from above. Although such a result follows from
quantitative refinements of the (deep) Grunwald-Wang theorem (see [23] and
[24]), we are able to give a short, geometrically-inspired proof.

######  Theorem E (Existence of Number Fields with Prescribed Arithmetic
Properties).

Let $p>2$ be a prime number, $k$ be a totally real number field and
$\mathfrak{p}_{1},\dots,\mathfrak{p}_{s}$ be primes of $k$. There exists a
field extension $L/k$ of degree $p$ in which none of the primes
$\mathfrak{p}_{i}$ split completely and which has norm of relative
discriminant bounded above by
$cd_{k}^{c^{\prime}}\left(\prod_{i=1}^{s}N_{k/\mathbf{Q}}(\mathfrak{p}_{i})\right)^{c^{\prime\prime}}$
where $c,c^{\prime},c^{\prime\prime}$ are positive constants depending only on
$p$ and the degree over $\mathbf{Q}$ of $k$.

######  Acknowledgements.

The authors would like to thank Ralf Spatzier for his useful comments
regarding the proof of Proposition 4.1. The work of the second author is
partially supported by NSF Grant Number DMS-1905437. The third author
acknowledges support from U.S. National Science Foundation grants DMS 1107452,
1107263, 1107367 “RNMS: Geometric Structures and Representation Varieties”
(the GEAR Network).

##  2\. Mahler Measure and Translation Length Inequalities - Theorem A

Throughout this section, we will let
$p(X)=\prod_{i=1}^{n}(X-a_{i})\in\mathbf{R}[X]$ denote a monic degree $n$
polynomial. We will prove results bounding its translation length (2.6) by its
Mahler measure (Theorem 2.3), length, and discriminant (Corollary 2.5). By
specializing these results to the case when $p(X)=p_{x}(X)$ is the
characteristic polynomial for some semisimple
$x\in\operatorname{SL}_{n}(\mathbf{R})$, we obtain Theorem A.

We remind the reader that the Mahler measure of $p$ is the product

(2.1) $\displaystyle M(p):=\prod_{i=1}^{n}\max\\{1,|a_{i}|\\}.$

For a detailed survey on the Mahler measure, see [20]. While it is open as to
whether the Mahler measure is uniformly bounded away from 1 for monic,
irreducible, noncyclotomic polynomials in $\mathbf{Z}[X]$, we do have such a
result when degree is fixed.

######  Proposition 2.1.

There exists an explicit monotonically decreasing function on the domain of
integers $n\geq 2$, such that $f(n)>1$ and if $p(X)\in\mathbf{Z}[X]$ is a
degree $n$, monic polynomial for which at least one of its irreducible factors
is noncyclotomic, then $\log(M(p))\geq f(n)$. Furthermore, $f(n)$ can be taken
to be

(2.2) $f(n)=\begin{cases}\log(M(L))>0.16235&\mbox{ if }n\leq 20,\\\
\frac{1}{4}\left(\frac{\log\log n}{\log n}\right)^{3}&\mbox{ if
}n>20,\end{cases}$

where $L(X)=X^{10}+X^{9}-X^{7}-X^{6}-X^{5}-X^{4}-X^{3}+X+1$ is Lehmer’s
polynomial.

###### Proof.

Lower bounds for when $p(X)$ is irreducible are well known, such as the bounds
of Voutier [22] $f_{V}(n)=\frac{1}{4}\left(\frac{\log\log n}{\log
n}\right)^{3}$. A check via Sage verifies that $f_{V}(15)<0.01245$, and
$f_{V}(n)$ is monotonically decreasing for all $n\geq 15$. Meanwhile, Boyd [3,
4] enumerated all integer polynomials of degree $\leq 20$ of small Mahler
measure and verified that Lehmer’s polynomial $L$ attains the minimal Mahler
measure in this range. It can be computed in Sage that $\log(M(L))>0.16235$.
We may take $f(x)$ to be the maximum of the two. When $p$ is not irreducible,
the proposition follows from the fact that the log of the Mahler measure is
additive together with the monotonicity of $f(n)$. More precisely, if
$p(X)=g_{1}(X)\cdots g_{s}(X)$, where the $g_{i}$ are irreducible of degree
$n_{i}$, and without loss of generality, $g_{1}(X)$ is noncyclotomic, then

$\log(M(p))=\log(M(g_{1}))+\cdots+\log(M(g_{s}))\geq
f(n_{1})+\cdots+f(n_{s})\geq f(n_{1})\geq f(n).$

∎

We may write $p(X)$ as

(2.3) $\displaystyle p(X)$ $\displaystyle=\sum_{j=0}^{n}(-1)^{j}s_{j}X^{n-j}$

where $s_{j}$ denotes the $j^{th}$ elementary symmetric polynomial in the
roots of $p$. Let $p_{k}:=\sum_{i}a_{i}^{k}$. Newton’s identities [8] state
that for all $1\leq j\leq n$,

(2.4) $\displaystyle js_{j}=\sum_{i=1}^{j}(-1)^{i-1}s_{j-i}p_{i}.$

The following result will be used in the proof of Theorem A to bound the
Mahler measure.

######  Lemma 2.2.

Suppose the polynomial
$p(X)=\prod_{i=1}^{n}(X-c_{i})=\sum_{j=0}^{n}(-1)^{j}s_{j}X^{n-j}$ has all
real zeros. The coefficient $s_{j}$ is the $j$th elementary symmetric
polynomial in the zeros of $p$. For $k\in\mathbf{N}$, let
$p_{k}=\sum_{i=1}^{n}c_{i}^{k}$. Then:

(2.5) $\frac{2n}{n-1}s_{2}\leq s_{1}^{2}\leq np_{2}$

with equality on both sides exactly when $c_{i}=c_{j}$ for all $i,j$. If all
$c_{i}\geq 0$, then $p_{2}\leq s_{1}^{2}$ with equality exactly when $c_{i}=0$
for all $i$.

###### Proof.

By the Cauchy-Schwarz inequality:

$s_{1}^{2}=\left(\sum_{i=1}^{n}(c_{i})(1)\right)^{2}\leq\left(\sum_{i=1}^{n}c_{i}^{2}\right)\left(\sum_{i=1}^{n}1^{2}\right)=n\sum_{i=1}^{n}c_{i}^{2}=np_{2},$

with equality exactly when the sequence $\\{c_{i}\\}_{i=1}^{n}$ and
$\\{1\\}_{i=1}^{n}$ are linearly dependent. In particular, when $c_{i}=c_{j}$
for all $i,j$. Also,

$s_{1}^{2}=\left(\sum_{i=1}^{n}c_{i}\right)^{2}=\sum_{i=1}^{n}c_{i}^{2}+2\sum_{i<j}c_{i}c_{j}=p_{2}+2s_{2}.$

If all $c_{i}\geq 0$, notice that $s_{1}^{2}\geq p_{2}$ with equality
precisely when all $c_{i}=0$. Rearranging the previous equation and combining
it with the special case of the Cauchy-Schwarz inequality given above we get:

$s_{1}^{2}\leq n(s_{1}^{2}-2s_{2})\quad\Rightarrow\quad
2ns_{2}\leq(n-1)s_{1}^{2}.$

∎

Being motivated by thinking of $p$ as a characteristic polynomial of a
semisimple matrix, we define the translation length of the polynomial $p$ to
be

(2.6)
$\displaystyle\ell(p):=\sqrt{\sum_{i=1}^{n}2(\log\left|a_{i}\right|)^{2}}.$

######  Theorem 2.3.

Let $p(X)=\prod_{i=1}^{n}(X-a_{i})\in\mathbf{R}[X]$ and assume
$\prod_{i=1}^{n}a_{i}=1$. Then:

(2.7) $2\sqrt{\frac{2}{n}}\log(M(p))\leq\ell(p)\leq 2\log(M(p)).$

The lower bound is an equality exactly when there exists an $r\in\mathbf{R}$
such that for all $i$, either $|a_{i}|=r$ or $|a_{i}|^{-1}=r$. The upper bound
is an equality when $\left|a_{i}\right|=1$ for all but at most two of the $i$.

######  Remark 2.4.

When $n=2$, the upper and lower bounds in (2.7) are equal and so
$\ell(x)=2\log(M(p))$, which coincides with (1.2).

###### Proof.

Let $p_{-1}(X):=\prod_{i=1}^{n}(X-a_{i}^{-1})$. Since
$\prod_{i=1}^{n}a_{i}=1$, $M(p)=M(p_{{-1}})>0$ and so
$M(p)=\sqrt{M(p)M(p_{{-1}})}$. Then:

$\log(M(p))=\frac{1}{2}\log(M(p)M(p_{{-1}}))=\frac{1}{2}\sum_{i=1}^{n}\left(\log_{+}\left|a_{i}\right|+\log_{+}\left|a_{i}^{-1}\right|\right)=\frac{1}{2}\sum_{i=1}^{n}\left|\log\left|a_{i}\right|\right|,$

where $\log_{+}(a)=\max\\{0,\log(a)\\}$. Applying Lemma 2.2 to the sequence
with
$\\{c_{i}\\}_{i=1}^{n}=\\{\left|\log\left|a_{i}\right|\right|\\}_{i=1}^{n}$,
we get:

(2.8) $\displaystyle 2\log(M(p))=s_{1}$
$\displaystyle\leq\sqrt{np_{2}}=\sqrt{n\sum_{i=1}^{n}\left|\log\left|a_{i}\right|\right|^{2}}=\sqrt{\frac{n}{2}}\ell(p),$

with equality precisely when, for all $i$,
$\left|\log\left|a_{1}\right|\right|=\left|\log\left|a_{i}\right|\right|$ or,
equivalently, when
$\left|a_{i}\right|\in\\{\left|a_{1}\right|,\left|a_{1}\right|^{-1}\\}$.

We now find an upper bound for $\ell(p)$ by using specific information about
the relative sizes of the $a_{i}$ that comes from our setup. Assume that
$\left|a_{i}\right|>1$ for some $i$, since otherwise $\left|a_{i}\right|=1$
for all $i$ and so $\ell(p)=0=\log(M(p))$. Re-order the $\\{a_{i}\\}$ so that
$\left|a_{1}\right|\geq\ldots\geq\left|a_{k}\right|\geq
1>\left|a_{k+1}\right|\geq\ldots\geq\left|a_{n}\right|>0$ and so
$\prod_{i=1}^{k}\left|a_{i}\right|=M(p)=M(p_{{-1}})=\prod_{i=k+1}^{n}\left|a_{i}^{-1}\right|$.
Using the same notation as in Lemma 2.2, we want to find a tight upper bound
on $p_{2}$ in terms of $s_{1}$. We know that $p_{2}=s_{1}^{2}-2s_{2}\leq
s_{1}^{2}$ since $c_{i}:=\left|\log\left|a_{i}\right|\right|\geq 0$. To get a
tighter bound, we find a lower bound on $s_{2}$ specific to our setup:

$s_{2}=\sum_{i<j}c_{i}c_{j}\geq\left(\sum_{i=1}^{k}c_{i}\right)\left(\sum_{j=k+1}^{n}c_{j}\right)=\left(\log(M(p))\right)\left(\log(M(p_{{-1}}))\right)=\left(\log(M(p))\right)^{2}.$

Note that the above inequality is an equality when $c_{i}=0$ (so
$\left|a_{i}\right|=1$) for all $i\in[2,n-1]$. Therefore:

(2.9) $\displaystyle\ell(p)$
$\displaystyle=\sqrt{2(s_{1}^{2}-2s_{2})}\leq\sqrt{2\left(2\log(M(p))\right)^{2}-4\left(\log(M(p))\right)^{2}}=2\log(M(p)).$

∎

We conclude this section by observing that our results enable us to also bound
translation length in terms of two other measures of a polynomial’s
complexity: length and discriminant. For $p(X)$ as above, its length is:

(2.10) $\displaystyle L(p):=\sum_{i=0}^{n}\left|s_{i}\right|$

and its discriminant is

(2.11) $\displaystyle\mathrm{disc}(p):=(-1)^{\frac{1}{2}n(n-1)}\prod_{i\neq
j}(a_{i}-a_{j})=\prod_{i<j}(a_{i}-a_{j})^{2}.$

These quantities are related, and the following bounds are well known (see
[13])

(2.12) $\displaystyle L(p)\leq 2^{n}M(p)\leq 2^{n}L(p)$

(2.13) $\displaystyle\left|\mathrm{disc}(p)\right|\leq n^{n}M(p)^{2n-2}$

These inequalities can be combined with the inequality in Theorem 2.3 to bound
$\ell(p)$ in terms of $L(p)$ and $\mathrm{disc}(p)$ as in the following
corollary. Let $\log_{+}(a)=\max\\{0,\log(a)\\}$.

######  Corollary 2.5.

If $p(X)=\prod_{i=1}^{n}(X-a_{i})\in\mathbf{R}[X]$ and
$\prod_{i=1}^{n}a_{i}=1$, then:

$\displaystyle 2\sqrt{\frac{2}{n}}\log_{+}(2^{-n}L(p))$
$\displaystyle\leq\ell(p)\leq 2\log(L(p)),$
$\displaystyle\frac{1}{n-1}\sqrt{\frac{2}{n}}\log_{+}\left|n^{-n}\mathrm{disc}(p)\right|$
$\displaystyle\leq\ell(p).$

###### Proof.

The length inequality follows directly from replacing $M$ in Theorem 2.3 with
$L$ using (2.12). To get the discriminant inequality, first re-arrange (2.13)
and take the logarithm to get:

$\log_{+}\left|n^{-n}\mathrm{disc}(p)\right|\leq 2(n-1)\log(M(p)).$

Combine that with the lower bound in Theorem 2.3 that
$2\log(M(p))\leq\sqrt{\frac{n}{2}}\ell(p)$ to get:

$\log_{+}\left|n^{-n}\mathrm{disc}(p)\right|\leq(n-1)\sqrt{\frac{n}{2}}\ell(p).$

∎

##  3\. Characteristic Polynomials and the Proof of Theorem B

If $\mathfrak{X}$ is a globally symmetric space of noncompact type, then the
identity component of its isometry group
$\mathcal{G}:=\operatorname{Isom}_{0}(\mathfrak{X})$ is a connected, adjoint
semisimple Lie group and the stabilizer subgroup
$\mathcal{K}=\operatorname{Stab}_{\mathcal{G}}(o)$ of a point
$o\in\mathfrak{X}$ is a maximal compact subgroup [7, IV.3.3, VI.1.1, VI.2.2].
It follows that $\mathcal{K}\backslash\mathcal{G}\cong\mathfrak{X}$. We say
$\mathfrak{X}$ is simple if $\mathcal{G}$ is simple (i.e., the
complexification of its Lie algebra is simple). By a simple locally symmetric
space, we mean a space of the form $\mathfrak{X}/\Gamma$ where $\mathfrak{X}$
is simple and $\Gamma\subset\mathcal{G}$ is a lattice.

We now discuss the construction of arithmetic lattices in $\mathcal{G}$. Here
we assume some familiarity with algebraic groups and arithmetic groups. For
detailed references on algebraic and arithmetic groups, we refer the reader to
[1, 15]. For a discussion of arithmetic simple orbifolds, see [10, Section 7].

To begin, fix:

  1. (1)

a degree $d_{1}$, totally real number field $k$ with ring of integers
$\mathcal{O}_{k}$,

  2. (2)

an embedding $k\subset\mathbf{R}$,

  3. (3)

a simple, semisimple, adjoint, algebraic $k$-group $\mathrm{G}$ of dimension
$d_{2}$ such that the identity component of its real points
$(\mathrm{G}(\mathbf{R}))_{0}\cong\mathcal{G}$ as Lie groups,

  4. (4)

a choice of a $k$-rational basis for its Lie algebra $\mathfrak{g}$ and use it
to identify $\operatorname{GL}(\mathfrak{g})$ with
$\operatorname{GL}_{d_{2}}(k)$,

  5. (5)

$\mathrm{G}(\mathcal{O}_{k}):=\operatorname{Ad}^{-1}(\operatorname{Ad}(\mathrm{G}(k))\cap\operatorname{GL}_{d_{2}}(\mathcal{O}_{k}))$.

Assume $\mathrm{G}$ is $\mathbf{R}$-isotropic but $\mathrm{G}$ is anisotropic
for all non-identity embeddings $\sigma:k\to\mathbf{R}$. Then any
$\Gamma\subset\mathrm{G}(\mathbf{R})$ commensurable to
$\mathrm{G}(\mathcal{O}_{k})$ is an arithmetic lattice in
$\mathrm{G}(\mathbf{R})$.

Fix a basis for $k$ over $\mathbf{Q}$ and let
$\operatorname{reg}:k\to\operatorname{M}_{d_{1}}(\mathbf{Q})$ be the regular
representation associated to this basis. Let $L/k$ be the Galois closure of
$k$ with fixed embedding $L\subset\mathbf{C}$. We have two injective ring maps
$\iota_{1},\iota_{2}:\operatorname{M}_{d_{2}}(k)\to\operatorname{M}_{d_{1}d_{2}}(L)$
defined below. We obtain our first ring map by applying the regular
representation to each entry of the matrix.

$\iota_{1}:\operatorname{M}_{d_{2}}(k)\to\operatorname{M}_{d_{1}d_{2}}(\mathbf{Q})\subset\operatorname{M}_{d_{1}d_{2}}(L)$

$\begin{pmatrix}y_{11}&\cdots&y_{1d_{2}}\\\ &\ddots&\\\
y_{d_{2}1}&\cdots&y_{d_{2}d_{2}}\end{pmatrix}\mapsto\left(\begin{matrix}[c|c|c]\operatorname{reg}(y_{11})&\cdots&\operatorname{reg}(y_{1d_{2}})\\\
\hline\cr&\ddots&\\\
\hline\cr\operatorname{reg}(y_{d_{2}1})&\cdots&\operatorname{reg}(y_{d_{2}d_{2}})\end{matrix}\right).$

Meanwhile, we obtain our second injective ring map by looking at the diagonal
map across all real embeddings of $k$, which we denote $V_{\infty}$.

$\iota_{2}:\operatorname{M}_{d_{2}}(k)\to\prod_{\sigma\in
V_{\infty}}\operatorname{M}_{d_{2}}(L)\subset\operatorname{M}_{d_{1}d_{2}}(L)$

$\begin{pmatrix}y_{11}&\cdots&y_{1d_{2}}\\\ &\ddots&\\\
y_{d_{2}1}&\cdots&y_{d_{2}d_{2}}\end{pmatrix}\mapsto\left(\begin{array}[]{@{}c@{}cc@{}}\hskip
6.0pt\begin{array}[]{|ccc|}\hline\cr\sigma_{1}(y_{11})&\cdots&\sigma_{1}(y_{1d_{2}})\\\
&\ddots&\\\ \sigma_{1}(y_{d_{2}1})&\cdots&\sigma_{1}(y_{d_{2}d_{2}})\\\
\hline\cr\end{array}&0&0\\\ 0&\ddots&0\\\ 0&0&\hskip
6.0pt\begin{array}[]{|ccc|}\hline\cr\sigma_{d_{1}}(y_{11})&\cdots&\sigma_{d_{1}}(y_{1d_{2}})\\\
&\ddots&\\\
\sigma_{d_{1}}(y_{d_{2}1})&\cdots&\sigma_{d_{1}}(y_{d_{2}d_{2}})\\\
\hline\cr\end{array}\end{array}\right).$

######  Lemma 3.1.

The images $\iota_{1}(\operatorname{M}_{d_{2}}(k))$ and
$\iota_{2}(\operatorname{M}_{d_{2}}(k))$ are
$\operatorname{GL}_{d_{1}d_{2}}(L)$-conjugate.

###### Proof.

If $A:=L\otimes_{k}\operatorname{M}_{d_{2}}(k)$, then $A$ is a central simple
$L$-algebra [19, 7.8]. Letting $B:=\operatorname{M}_{d_{1}d_{2}}(L)$, and
letting $\iota_{1}$ and $\iota_{2}$ extend linearly to $A$, we have
$L\subset\iota_{1}(A)\subset B$ and $L\subset\iota_{2}(A)\subset B$. It then
follows from the Skolem–Noether Theorem [19, 7.21] that the images
$\iota_{1}(A)$ and $\iota_{2}(A)$ are identified by an inner automorphism of
$A$. More precisely, there exists a $g\in\operatorname{GL}_{d_{1}d_{2}}(L)$
such that if $h\in\operatorname{M}_{d_{2}}(k)$, then $\iota_{2}(1\otimes
h)=g\iota_{1}(1\otimes h)g^{-1}$. The result follows. ∎

If $\mathrm{H}$ is an algebraic $k$-group, the restriction of scalars group
$\operatorname{Res}_{k/\mathbf{Q}}(\mathrm{H})$ is a $\mathbf{Q}$-group such
that
$\mathrm{H}(k)\cong\operatorname{Res}_{k/\mathbf{Q}}(\mathrm{H})(\mathbf{Q})$
[17, 2.1.2]. Fix the $\mathbf{Q}$-rational map
$\varphi:\operatorname{Res}_{k/\mathbf{Q}}(\operatorname{SL}_{d_{2}})\to\operatorname{SL}_{d_{1}d_{2}}$
which at the level of $k$-points is $\iota_{1}$, i.e. if
$y\in\operatorname{SL}_{d_{2}}(k)\cong\operatorname{Res}_{k/\mathbf{Q}}(\operatorname{SL}_{d_{2}})(\mathbf{Q})$,
then $\varphi(y)=\iota_{1}(y)$.

As in [10, Proposition 7.2], composing the adjoint map with restriction of
scalars, we obtain an embedding of Lie groups
$\rho:\mathrm{G}(\mathbf{R})\to\operatorname{SL}_{d_{1}d_{2}}(\mathbf{R})$.
This embedding has many nice features and in Proposition 3.2 we now establish
an important one concerning characteristic polynomials: relative to this
embedding, semisimple elements of arithmetic lattices always have
characteristic polynomials with integer coefficients.

######  Proposition 3.2.

If $\Gamma\subset\mathrm{G}(\mathbf{R})$ is an arithmetic lattice and
$x\in\Gamma$ is semisimple, then
$p_{\operatorname{Ad}(x)}(X)\in\mathcal{O}_{k}[X]$ and
$p_{\rho(x)}(X)\in\mathbf{Z}[X]$.

###### Proof.

To begin, we show that if $x\in\Gamma$ is semisimple, then the characteristic
polynomial $p_{\operatorname{Ad}(x)}(X)$ of the matrix
$\operatorname{Ad}(x)\in\operatorname{SL}_{d_{2}}(k)$ lies in
$\mathcal{O}_{k}[X]$. By assumption, $\Gamma$ is commensurable with
$\mathrm{G}(\mathcal{O}_{k})$, so let
$e=[\Gamma:(\Gamma\cap\mathrm{G}(\mathcal{O}_{k}))]$. Then
$x^{e}\in\mathrm{G}(\mathcal{O}_{k})$, and thus
$p_{\operatorname{Ad}(x^{e})}(X)\in\mathcal{O}_{k}[X]$. Hence
$\operatorname{Ad}(x^{e})$ has integral eigenvalues, and thus the eigenvalues
of $\operatorname{Ad}(x)$ are algebraic integers. The coefficients of the
characteristic polynomial are symmetric polynomials on the eigenvalues (2.3),
thus the coefficients of $p_{\operatorname{Ad}(x)}(X)$ are algebraic integers.
Since $\mathrm{G}$ is adjoint, $x\in\mathrm{G}(k)$ [2, Proposition 1.2], so
$\operatorname{Ad}(x)\in\operatorname{SL}_{d_{2}}(k)$ hence
$p_{\operatorname{Ad}(x)}(X)\in k[X]$, and we conclude
$p_{\operatorname{Ad}(x)}(X)\in\mathcal{O}_{k}[X]$.

Next we show that if $y\in\operatorname{SL}_{d_{2}}(k)$ is semisimple such
that $p_{y}(X)\in\mathcal{O}_{k}[X]$, then
$p_{\iota_{1}(y)}(X)\in\mathbf{Z}[X]$. To begin, since
$y\in\operatorname{SL}_{d_{2}}(k)$, it follows that
$\iota_{1}(y)\in\operatorname{SL}_{d_{1}d_{2}}(\mathbf{Q})$ and hence
$p_{\iota_{1}(y)}(X)$ has rational coefficients. Meanwhile $\iota_{2}$,
restricted to $\operatorname{SL}_{d_{2}}(k)$, gives the diagonal embedding

$\operatorname{SL}_{d_{2}}(k)\to\prod_{\sigma\in
V_{\infty}}\operatorname{SL}_{d_{2}}(\sigma(k))\subset\operatorname{SL}_{d_{1}d_{2}}(L)$

where $V_{\infty}$ is the set of all real embeddings of $k$ and $L$ is the
Galois closure of $k$. Since $\iota_{1}(y)$ and $\iota_{2}(y)$ are
$\operatorname{GL}_{d_{1}d_{2}}(L)$-conjugate by Lemma 3.1, they have equal
characteristic polynomials. If $p_{y}(X)=\sum_{i=0}^{n}c_{i}X^{i}$ for
$c_{i}\in\mathcal{O}_{k}$, then it follows that

$p_{\iota_{2}(y)}(X)=\prod_{\sigma\in
V_{\infty}}\left(\sum_{i=0}^{n}\sigma(c_{i})X^{i}\right).$

Since each $\sigma(c_{i})$ is an algebraic integer, all of the coefficients of
$p_{\iota_{2}(y)}(X)$ are algebraic integers. We deduce that the coefficients
of $p_{\iota_{1}(y)}(X)$ are both rational and algebraic integers, thus
concluding $p_{\iota_{1}(y)}(X)\in\mathbf{Z}[X]$. ∎

While there are many reasonable Riemannian metrics to put on
$\mathfrak{X}_{n}:=\operatorname{SO}(n)\backslash\operatorname{SL}_{n}(\mathbf{R})$,
as in [10, Equation (10)], we fix once and for all the Riemannian metric on
$\mathfrak{X}_{n}$ given by

(3.1) $\langle X,Y\rangle:=2\operatorname{tr}(XY),\hskip
24.0ptX,Y\in\mathfrak{sl}_{n}(\mathbf{R}).$

This has the nice geometrical property that the inclusions of the hyperbolic
plane $\mathbb{H}^{2}\to\mathfrak{X}_{n}$ (associated to any $2\times 2$ block
along the diagonal
$\operatorname{SL}_{2}(\mathbf{R})\to\operatorname{SL}_{n}(\mathbf{R})$) are
totally geodesic, isometrical immersions (i.e., the images have constant
curvature -1).

For any inclusion of a connected semisimple lie group
$H\to\operatorname{SL}_{n}(\mathbf{R})$, this induces a subspace metric (which
we will denote $g$) on the corresponding symmetric space
$(H\cap\operatorname{SO}(n))\backslash H\subset\mathfrak{X}_{n}$.

###### Proof of Theorem B.

Let $\Gamma\subset\mathrm{G}(\mathbf{R})$ be an arithmetic subgroup and
$N:=\mathrm{K}\backslash\mathrm{G}(\mathbf{R})/\Gamma$, where $K$ is a maximal
compact subgroup of $\mathrm{G}(\mathbf{R})$. By [10, Theorem 7.2], we have an
embedding of Lie groups
$\rho:\mathrm{G}(\mathbf{R})\to\operatorname{SL}_{n}(\mathbf{R})$ where
$n=|k:\mathbf{Q}|\dim\mathrm{G}$. It follows from Proposition 3.2 that if
$x\in\Gamma$ is semisimple, then $p_{\rho(x)}(X)\in\mathbf{Z}[X]$, and hence
by our Mahler-Length Theorem A and Proposition 2.1, we have

(3.2) $\operatorname{sys}(N,g)\geq\frac{2\sqrt{2}}{\sqrt{n}}f(n),$

where $\operatorname{sys}(N,g)$ denotes the systole of $N$ relative to the
subspace metric (3.1), and $f(n)$ is as in (2.2). ∎

##  4\. Large Systoles and the Proof of Theorem C

Let $N$ be a compact, simple arithmetic manifold. In [10, Theorem B] we showed
that $N$ has a finite degree cover $N^{\prime}$ whose systole satisfies
$\operatorname{sys}(N^{\prime})\geq
c_{1}\log(\operatorname{Vol}(N^{\prime}))+c_{2}$ for certain positive
constants $c_{1}$ and $c_{2}$. In order to prove Theorem C it therefore
suffices to derive an upper bound for the systole of $N^{\prime}$ whose order
of magnitude is also $\log(\operatorname{Vol}(N^{\prime}))$. This follows from
the following proposition.

######  Proposition 4.1.

Let $\mathfrak{X}$ be a symmetric space of noncompact type and $\Gamma$ be a
discrete, cocompact subgroup of isometries of $\mathfrak{X}$ having finite
covolume. Then $\operatorname{sys}(\mathfrak{X}/\Gamma)\leq
c\log(\operatorname{Vol}(\mathfrak{X}/\Gamma))$ for some positive constant $c$
depending only on $\mathfrak{X}$.

###### Proof.

Let $B$ be a closed ball of radius $R$ in $\mathfrak{X}$ which has volume
greater than $\operatorname{Vol}(\mathfrak{X}/\Gamma)$. The projection
$\pi:B\rightarrow\mathfrak{X}/\Gamma$ cannot be one-to-one, hence there exist
distinct points $x_{1},x_{2}\in B$ such that $\pi(x_{1})=\pi(x_{2})$. Then
$x_{2}=\gamma x_{1}$ for some semisimple element $\gamma\in\Gamma$, and
consequently the translation length $\ell(\gamma)$ of $\gamma$ satisfies
$\ell(\gamma)\leq 2R$. The proposition now follows from [9, Theorem A], where
it is shown that the volume of $B$ is asymptotically equivalent to
$R^{\frac{r-1}{2}}e^{hR}$ as $R$ tends to infinity, where $r$ is the rank of
$\mathfrak{X}$ and $h>0$ denotes the volume entropy of $\mathfrak{X}$. Indeed,
the result of [9, Theorem A] shows that the volume of $B$ is greater than
$c_{1}e^{hR}$ for all $R\geq R_{0}$, where $c_{1}$ and $R_{0}$ are positive
constants. In particular the volume of $B$ is will be greater than
$\operatorname{Vol}(\mathfrak{X}/\Gamma)$ for any $R\geq R_{0}$ satisfying
$R>\frac{1}{h}\log(\operatorname{Vol}(\mathfrak{X}/\Gamma)/c_{1})$, and there
clearly exists a positive constant $c$ for which such an $R$ may be taken to
satisfy $R<c\log(\operatorname{Vol}(\mathfrak{X}/\Gamma))$.∎

##  5\. Geometry of Special Linear Orbifolds and Theorem D

For $n\geq 2$, we fix the globally symmetric space
$\mathfrak{X}_{n}:=\operatorname{SO}(n)\backslash\operatorname{SL}_{n}(\mathbf{R})$.
If $\Gamma\subset\operatorname{SL}_{n}(\mathbf{R})$ is a lattice, then
$\mathfrak{X}_{n}/\Gamma$ is a special linear orbifold. In this section, we
give a brief overview of the construction and geometry of what we call
standard special linear orbifolds. For a detailed construction, we refer the
reader to [10, Section 4]. This construction requires knowledge of the theory
of central simple algebras, for which we refer the reader to [19].

Let $A$ be a central simple algebra over $\mathbf{Q}$ of dimension $n^{2}\geq
4$. The Wedderburn Structure Theorem states that $A\cong\mathrm{M}_{m}(D)$ for
some division algebra $D$ over $\mathbf{Q}$ where $n^{2}=m^{2}(\dim D)^{2}$.

Let $\ell$ denote either $\mathbf{R}$ or the field of $p$-adic numbers for
some rational prime $p$. Then $A\otimes_{\mathbf{Q}}\ell$ is a central simple
algebra over $\ell$, and again by the Wedderburn Structure Theorem, there
exists a division algebra $D_{\ell}$ over $\ell$ such that there exists an
isomorphism
$h:A\otimes_{\mathbf{Q}}\ell\cong\mathrm{M}_{m^{\prime}}(D_{\ell})$. If $\dim
D_{\ell}>1$, we say $A$ ramifies over $\ell$, otherwise we say $A$ is
unramified over $\ell$.

A $\mathbf{Z}$-order in $A$ is a subring $\mathcal{O}$ which is also a
finitely generated $\mathbf{Z}$-module for which
$A=\mathbf{Q}\otimes_{\mathbf{Z}}\mathcal{O}$. An order is maximal if it is
maximal with respect to inclusion. Maximal orders always exist [19, 10.4]. Let
$\mathcal{O}$ be a maximal order.

To produce our standard special linear manifolds, we fix a central simple
algebra $A$ over $\mathbf{Q}$ that is unramified over $\mathbf{R}$. Fix the
isomorphism $h:A\otimes_{\mathbf{Q}}\mathbf{R}\to\mathrm{M}_{n}(\mathbf{R})$.
Via that isomorphism, we can define the norm $N(a):=\det(h(a\otimes 1))$. (It
is a fundamental result that this definition is independent of the choice of
isomorphism $h$).

Let $\mathcal{O}^{1}$ denote the set of norm one elements of $\mathcal{O}$.
Following the convention of [14, 8.3.4], if $\Gamma\subset
h(\mathcal{O}^{1})$, then we say $\Gamma$ is a standard arithmetic lattice in
$\operatorname{SL}_{n}(\mathbf{R})$ derived from a central simple algebra and
similarly $M:=\mathfrak{X}_{n}/\Gamma$ is a standard special linear orbifold
derived from a central simple algebra. Any orbifold commensurable to such an
$M$ is a standard linear orbifold.

As a locally symmetric space, $M$ has a one parameter family of Haar measures
induced from $\mathfrak{X}_{n}$. We choose the normalization (3.1) which we
called the geometric metric [10, Section 2], in which the natural embedding
$\operatorname{SL}_{2}(\mathbf{R})\to\operatorname{SL}_{n}(\mathbf{R})$ as a
$2\times 2$ block along the diagonal results in a totally geodesic, isometric
embedding $\mathbb{H}^{2}\to\mathfrak{X}_{n}$.

###### Proof of Theorem D.

Let $M$ be a special linear orbifold derived from a central simple algebra.,
i.e. $M\cong\mathfrak{X}_{n}/\Gamma$ where $\Gamma\subset\mathcal{O}^{1}$, the
norm 1 elements of a maximal order $\mathcal{O}$. Let $x\in\Gamma$ be
semisimple and let $p_{x}(X)$ denote the characteristic polynomial of
$h(x\otimes 1)$ for $h$ as above. It is a fundamental result [19, Theorem 8.6]
that $p_{x}(X)$ is a monic, degree $n$ polynomial in $\mathbf{Z}[X]$. (Note
that $p_{x}$ need not be irreducible.) By our Mahler-Length Theorem A and
Proposition 2.1, we have then
$\operatorname{sys}(M)\geq\frac{2\sqrt{2}}{\sqrt{n}}f(n),$ where $f(n)$ is as
in (2.2), and the result follows. ∎

##  6\. Proof of Theorem E

Let $p>2$ be a rational prime, $k$ be a totally real number field with ring of
integers $\mathcal{O}_{k}$ and $\mathfrak{p}_{1},\ldots\mathfrak{p}_{s}$ be
primes of $k$.

Let $B$ be the division algebra over $k$ with Hasse invariant $\frac{1}{p}$ at
each of the primes $\mathfrak{p}_{1},\dots,\mathfrak{p}_{s-1}$ and Hasse
invariant $\frac{a}{p}$ at the prime $\mathfrak{p}_{s}$ where $a$ is a
positive integer satisfying $a+(s-1)\equiv 0\pmod{p}$. Since the sum of these
Hasse invariants is an integer, it follows from the Albert-Brauer-Hasse-
Noether theorem that $B$ exists and has degree $p$ over $k$ (see [12, Theorem
2.1].

Let $\mathcal{O}$ be a maximal order of $B$ and $\mathcal{O}^{1}$ denote the
multiplicative subgroup of $\mathcal{O}^{*}$ consisting of the elements of
$\mathcal{O}^{*}$ having reduced norm one. Since
$B\otimes_{\mathbf{Q}}\mathbf{R}\cong\operatorname{M}_{p}(\mathbf{R})^{[k:\mathbf{Q}]}$
we obtain an embedding
$B\hookrightarrow\operatorname{SL}_{p}(\mathbf{R})^{[k:\mathbf{Q}]}$. Let
$\Gamma$ denote the image in
$\operatorname{SL}_{p}(\mathbf{R})^{[k:\mathbf{Q}]}$ of $\mathcal{O}^{1}$
under this embedding. Let $\mathfrak{X}$ denote the symmetric space of
$\operatorname{SL}_{p}(\mathbf{R})^{[k:\mathbf{Q}]}$ and define
$M:=\mathfrak{X}/\Gamma$ to be the arithmetic orbifold associated to $\Gamma$.

Let $\gamma\in\Gamma$ be a semisimple element whose translation length
$\ell(\gamma)$ realizes the systole of $M$. As a consequence of Proposition
4.1 we have the inequality

(6.1) $\ell(\gamma)\leq c_{1}\log(\operatorname{Vol}(\mathfrak{X}/\Gamma))$

for some positive constant $c_{1}$ depending only on $\mathfrak{X}$ (and thus
only on $p$ and the degree of $k$).

We now obtain an upper bound for $\operatorname{Vol}(\mathfrak{X}/\Gamma)$
using [11, Proposition 3.2]:

(6.2) $\operatorname{Vol}(\mathfrak{X}/\Gamma)\leq
c_{2}d_{k}^{\frac{p^{2}-1}{2}}\left(\prod_{i=1}^{s}N_{k/\mathbf{Q}}(\mathfrak{p}_{i})\right)^{\frac{p(p-1)}{2}}$

for some positive constant $c_{2}$ which is explicitly given in [11,
Proposition 3.2] and depends only on $p$ and the degree of $k$. (That the
dependence only depends on the degree of $k$ follows from the trivial bound
$\zeta_{k}(s)\leq\zeta(s)^{[k:\mathbf{Q}]}$.)

We now need a lower bound for $\ell(\gamma)$. To do so we will employ the
bound given in Theorem A. There is a potential issue however. The hypothesis
of Theorem A is that the semisimple element $\gamma$ lies in
$\operatorname{SL}_{n}(\mathbf{R})$ for some positive integer. Our element
$\gamma$, on the other hand, lies in
$\operatorname{SL}_{p}(\mathbf{R})^{[k:\mathbf{Q}]}$. To resolve this we use
the fact that $\operatorname{SL}_{p}(\mathbf{R})^{[k:\mathbf{Q}]}$ is a Lie
subgroup of $\operatorname{SL}_{p[k:\mathbf{Q}]}(\mathbf{R})$ and apply
Theorem A with $n=p[k:\mathbf{Q}]$:

(6.3) $\ell(\gamma)\geq 2\sqrt{\frac{2}{p[k:\mathbf{Q}]}}\log(M(p_{\gamma})).$

Let $L=k(\gamma)$ be the extension of $k$ generated by adjoining to $k$ a
preimage in $B$ of $\gamma$. This extension has degree $p$ and, by Theorem
32.15 of [19], for every prime $\mathfrak{P}$ of $L$ lying above a prime
$\mathfrak{p}\in\\{\mathfrak{p}_{1},\dots,\mathfrak{p}_{s}\\}$, satisfies
$[L_{\mathfrak{P}}:k_{\mathfrak{p}}]=p$. In particular none of the primes
$\mathfrak{p}_{i}$ split completely in $L/k$.

In order to relate the relative discriminant $\Delta_{L/k}$ of $L$ over $k$ we
will make use of a result of Silverman [21, Theorem 2]:

(6.4)
$\log(M(p_{\gamma}))\geq\frac{1}{2p(p-1)}\log(N_{k/\mathbf{Q}}(\Delta_{L/k}))-\frac{p\log(p)}{2(p-1)}.$

By combining (6.3) and (6.4) we obtain positive constants $c_{3},c_{4}$
depending only on $p$ and the degree of $k$ such that

(6.5) $\ell(\gamma)\geq c_{3}+c_{4}\log(N_{k/\mathbf{Q}}(\Delta_{L/k})).$

Finally, by combining (6.1), (6.2) and (6.5) we obtain positive constants
$c_{5},c_{6},c_{7}$ such that

$N_{k/\mathbf{Q}}(\Delta_{L/k})\leq
c_{5}d_{k}^{c_{6}}\left(\prod_{i=1}^{s}N_{k/\mathbf{Q}}(\mathfrak{p}_{i})\right)^{c_{7}},$

which finishes the proof of Theorem E.

## References

  * [1] A. Borel  _Linear Algebraic Groups_.  Graduate Texts in Mathematics, 126, Springer-Verlag, (1991).
  * [2] A. Borel, G. Prasad.  Finiteness theorems for discrete subgroups of bounded covolume in semi-simple groups.  Inst. Hautes Études Sci. Publ. Math. No. 69 (1989), 119–171.
  * [3] D. W. Boyd.  Reciprocal polynomials having small measure.  Math. Comp. 35 (1980), no. 152, 1361–1377.
  * [4] D. W. Boyd.  Reciprocal polynomials having small measure. II.  Math. Comp. 53 (1989), no. 187, 355–357, S1–S5.
  * [5] V. Emery, J. G. Ratcliffe, and S. T. Tschantz.  Salem numbers and arithmetic hyperbolic groups.  Trans. Amer. Math. Soc. 372 (2019), no. 1, 329–355.
  * [6] E. Ghate, E. Hironaka.  _The arithmetic and geometry of Salem numbers_. Bull. Amer. Math. Soc. (N.S.) 38 (2001), no. 3, 293–314.
  * [7] S. Helgason  _Differential Geometry, Lie Groups, and Symmetric Spaces_.  AMS, Providence, (2001).
  * [8] D. Kalman  _A Matrix Proof of Newton’s Identities_.  Math. Mag. 73 (2000), no. 4, 313–315.
  * [9] G. Knieper.  On the asymptotic geometry of nonpositively curved manifolds. Geom. Funct. Anal., 7(4):755–782, 1997.
  * [10] S. Lapan, B. Linowitz, and J. S. Meyer.  Systole inequalities up towers for arithmetic locally symmetric spaces. https://arxiv.org/abs/1710.00071 (2017).
  * [11] B. Linowitz, D. B. McReynolds, and N. Miller.  Locally equivalent correspondences. Ann. Inst. Fourier (Grenoble), 67(2):451–482, 2017.
  * [12] B. Linowitz, D. B. McReynolds, P. Pollack, and L. Thompson.  Counting and effective rigidity in algebra and geometry.  Invent. Math., 213(2):697–758, 2018.
  * [13] K. Mahler  _An application of Jensen’s formula to polynomials_.  Mathematika 7, 98-100, 1960.
  * [14] C. Maclachlan and A. W. Reid  _The Arithmetic of Hyperbolic 3–Manifolds_.  Springer-Verlag, (2003).
  * [15] D. W. Morris _Introduction to Arithmetic Groups_. Deductive Press, (2015) MR 3307755.
  * [16] W. D. Neumann and A. W. Reid  _Arithmetic of hyperbolic manifolds_.  Topology ’90 (Columbus, OH, 1990), Ohio State Univ. Math. Res. Inst. Publ., vol. 1, de Gruyter, Berlin, 1992, pp. 273–310.
  * [17] V. Platonov and A. Rapinchuk  _Algebraic groups and number theory_.  Academic Press, (1994).
  * [18] G. Prasad.  Volumes of $S$-arithmetic quotients of semi-simple groups.  Inst. Hautes Études Sci. Publ. Math., (69):91–117, 1989.  With an appendix by Moshe Jarden and the author.
  * [19] I. Reiner,  _Maximal orders_ , Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers],  London-New York, 1975, London Mathematical Society Monographs, No. 5. MR 0393100 (52 #13910)
  * [20] C. Smyth  _The Mahler measure of algebraic numbers: a survey_ ,  (English summary) Number theory and polynomials, 322–349, London Math. Soc. Lecture Note Ser., 352, Cambridge Univ. Press, Cambridge, 2008.
  * [21] J. H. Silverman,  _Lower bounds for height functions_.  Duke Math. J., 51 (1984), 395–403.
  * [22] P. Voutier.  _An effective lower bound for the height of algebraic numbers_.  Acta Arith. 74 (1996), no. 1, 81–95.
  * [23] S. Wang,  _An effective version of the Grunwald–Wang theorem_ ,  Ph.D. thesis, Caltech, 2001.
  * [24] S. Wang.  _Grunwald-Wang theorem, an effective version_ ,  Sci. China Math. 58 (2015), 1589–1606.