# A new blocks estimator for the extremal index

Helena Ferreira  Department of Mathematics of University of Beira Interior,
Portugal
<EMAIL_ADDRESS>Marta Ferreira  Center of Mathematics of Minho
University
Center for Computational and Stochastic Mathematics of University of Lisbon
Center of Statistics and Applications of University of Lisbon, Portugal
<EMAIL_ADDRESS>
###### Abstract

The occurrence of successive extreme observations can have an impact on
society. In extreme value theory there are parameters to evaluate the effect
of clustering of high values, such as the extremal index. The estimation of
the extremal index is a recurrent theme in the literature and there are
several methodologies for this purpose. The majority of existing methods
depend on two parameters whose choice affects the performance of the
estimators. Here we consider a new estimator depending only on one of the
parameters, thus contributing to a decrease in the degree of uncertainty. A
simulation study presents motivating results. An application to financial data
will also be presented.

keywords: extreme value theory, stationary sequences, dependence conditions,
extremal index

AMS 2000 Subject Classification Primary: 60G70; Secondary: 62G32

##  1 Introduction

Serial extremal dependence leads to the occurrence of clusters of high values.
This is an issue of major concern if associated to damaging phenomena, as for
example, heatwaves whose duration in time can cause drought and wildfires. On
the other hand, it may indicate a desirable situation, like successive high
stock returns attracting possible profits.

The extremal index, often denoted $\theta$, is a key parameter in assessing
the extremal clustering degree. It ranges between $0$ and $1$, where smaller
values mean stronger extremal dependence. Independent sequences have
$\theta=1$ and no clustering of extremes takes place. A broad overview about
the extremal index and, in particular, its applications in several areas can
be seen in Moloney _et al._ ([14] 2019) and references therein.

One interpretation of $\theta$ is that it corresponds to the reciprocal
limiting mean cluster size (Hsing et al. [13] 1988). The blocks and the runs
estimators were developed upon this idea (Smith and Weissman [17] 1994,
Weissman and Novak [18] 1998). Both estimators depend on the specification of
two unknown parameters: a high threshold above which observations are
considered extreme values and a cluster identifier. These are crucial since
the methods show sensitiveness on their specification. In order to overcome
the arbitrariness of these choices, alternative methods were proposed, such as
the estimator of Ferro and Segers ([11] 2003) which only needs the threshold
specification or the estimator of Northrop ([15] 2015) solely requiring the
choice of the blocks length. Other estimation procedures can also be found in
literature, such as the $K$-gaps estimator of Süveges and Davidson (2010)
involving the choice of $K$ and of the threshold ($K=0$ leads to the estimator
of Ferro and Segers [11] 2003), estimators holding under a local dependence
condition $D^{(s)}$ and thus requiring the indication of $s$ besides the
threshold (Ferreira and Ferreira [10] 2018, Cai [1] 2019), among others.

In this work we present a new estimator for the extremal index which only
requires a block length parameter. Therefore, it intends to contribute to a
decrease in the degree of uncertainty associated to the choice of parameters
involving inference on $\theta$. The direct competitors are Ferro and Segers
([11] 2003) and Northrop ([15] 2015) estimators, although our methodology
based on choosing a block size is closer to the second one. In Section 2 we
introduce the new proposal. Section 3 addresses a simulation study in order to
evaluate the performance of our estimator. In Section 4 we present an
application to a financial time series. Final remarks and future work are
pointed in Section 5.

##  2 Methodology

Let $\\{X_{n}\\}_{n}$ be a stationary sequence with extremal index $\theta$
having, without loss of generality, standard Fréchet marginals,
$F_{X}(x)=\exp(-1/x)$, $x>0$, and $\\{\widehat{X}_{n}\\}_{n}$ an associated
iid sequence, i.e., an independent sequence having marginals also standard
Fréchet, $F_{\widehat{X}}(x)=\exp(-1/x)$, $x>0$. Consider the bivariate
sequence

$\\{(Y_{n,1}=\widehat{X}_{n},Y_{n,2}=(1/2)\widehat{X}_{n}\vee(1/2)X_{n})\\}_{n}\,.$

We have that

$\displaystyle\begin{array}[]{rl}&\displaystyle\lim_{n\to\infty}P\left(\bigvee_{i=1}^{n}Y_{i,1}\leq
n/\tau_{1},\bigvee_{i=1}^{n}Y_{i,2}\leq n/\tau_{2}\right)\\\
=&\displaystyle\lim_{n\to\infty}P\left(\bigvee_{i=1}^{n}\widehat{X}_{i}\leq
n/(\tau_{1}\vee(\tau_{2}/2))\right)P\left(\bigvee_{i=1}^{n}{X}_{i}\leq
2n/\tau_{2}\right)\vspace{0.25cm}\\\
=&\exp\left(-\tau_{1}\vee(\tau_{2}/2)\right)\exp\left(-\theta\tau_{2}/2\right)\vspace{0.25cm}\\\
=&\displaystyle(\exp(-\tau_{1})\exp(-\theta\tau_{2}/2))\wedge\exp\left(-(1+\theta)\tau_{2}/2\right)\,.\end{array}$
(5)

Thus the limiting bivariate extreme value (BEV) copula is
$C(u,v)=uv^{\frac{\theta}{1+\theta}}\wedge v$, which has tail dependence
coefficient $\lambda_{C}$, given by

$\displaystyle\lambda_{C}=2-\displaystyle\lim_{u\to
1^{-1}}\frac{1-u^{1+\frac{\theta}{1+\theta}}\wedge
u}{1-u}=1-\frac{\theta}{1+\theta}\,.$ (6)

Our estimator is based on relation

$\displaystyle\theta=\frac{1}{\lambda_{C}}-1$ (7)

derived from (6). Since $\theta\in[0,1]$, then we must have
$\lambda_{C}\in[1/2,1]$.

Estimators of the tail dependence coefficient of a random pair $(Z_{1},Z_{2})$
having a BEV df $G(x_{1},x_{2})=C_{G}(G_{1}(x_{1}),G_{2}(x_{2}))$ are
addressed in literature with a threshold-free formulation. BEV copula $C_{G}$
can be stated as $C_{G}(G_{1}(x_{1}),G_{2}(x_{2}))=\exp(-l(-\log x_{1},-\log
x_{2}))$, where $l$ is the so called stable tail dependence function (Huang,
[12] 1992).

Consider $(Z_{1,1},Z_{1,2}),...,(Z_{n,1},Z_{n,2})$ a random sample of
$(Z_{1},Z_{2})$ with BEV copula $C_{G}$ and stable tail dependence function
$l$. We are going to use estimator

$\displaystyle\widetilde{\lambda}=2-\widetilde{l}(1,1),$ (8)

where

$\displaystyle\widetilde{l}(1,1)=\frac{1}{1-\frac{1}{n}\sum_{i=1}^{n}\left(\widetilde{G}_{1}(Z_{i,1})\vee\widetilde{G}_{2}(Z_{i,2})\right)}-1$
(9)

and
$\widetilde{G}_{j}(x)=\frac{1}{n+1}\sum_{l=1}^{n}\mathds{1}_{\\{Z_{l,j}\leq
x\\}}$, $j=1,2$, is the respective (modified) empirical df. Thus we have

$\displaystyle\widetilde{\lambda}=3-\frac{1}{1-\frac{1}{n}\sum_{i=1}^{n}\left(\widetilde{G}_{1}(Z_{i,1})\vee\widetilde{G}_{2}(Z_{i,2})\right)},$
(10)

and by (7) we obtain estimator

$\displaystyle\widetilde{\theta}=\frac{1}{\widetilde{\lambda}\vee 1/2}-1\,.$
(11)

For more details on formulas (8) and (9) see Ferreira and Ferreira ([7],
2012a) and references therein. See also Ferreira and Ferreira ([8] 2012b; [10]
2018).

The following algorithm describes our estimation proposal of the extremal
index of a stationary sequence $X_{1},...,X_{n}$.

  * Step 1.

In order to have standard Fréchet marginals, consider the marginal
transformation $-\frac{1}{\log\widetilde{F}_{X}(X_{i})}$, where
$\widetilde{F}_{X}$ is the (modified) empirical df as defined above.

  * Step 2.

Generate an iid sequence with standard Fréchet marginals,
$\widehat{X}_{1},...,\widehat{X}_{n}$, and consider random pairs,
$(\widehat{X}_{i},(1/2)\widehat{X}_{i}\vee(1/2)X_{i})$, $i=1,...,n$.

  * Step 3.

Since we are going to first estimate $\lambda$ on the limiting BEV model of
the component-wise maximum, we choose the blocks length $r$ where to take the
component-wise maxima, in order to obtain a sample of maximums

$\left(\bigvee_{i=(j-1)r+1}^{j\times
r}\widehat{X}_{i},\bigvee_{i=(j-1)r+1}^{j\times
r}(1/2)\widehat{X}_{i}\vee(1/2)X_{i}\right),\,1\leq j\leq n/r.$

  * Step 4.

Apply estimator $\widetilde{\lambda}$ given in (10) on the random pairs of the
previous step and calculate $\widetilde{\theta}$ in (11).

  * Step 5.

Repeat steps 2-5 a large number $M$ of times, obtain estimates
$\widetilde{\theta}_{1},...,\widetilde{\theta}_{M}$ and take the mean,
$\widetilde{\widetilde{\theta}}=\frac{1}{n}\sum_{s=1}^{M}\widetilde{\theta}_{s}$
in order to achieve robustness given the existence of arbitrariness in the
generation of a random sample (step 2) in each estimate. Here we consider
$M=10000$.

##  3 Simulations

Our simulations are based on $100$ replicates of samples of size $1000$ and
$5000$, of each of the following models: a first order autoregressive process
with Cauchy marginals and autoregressive parameter $\rho=-0.6$ (Chernick [2],
1978), a negatively correlated uniform AR(1) process with $r=2$ (Chernick _et
al._ [3], 1991), respectively denoted ARCau and ARUnif, a moving maxima (MM)
process with coefficients $\alpha_{0}=2/6,\,\alpha_{1}=1/6,\,\alpha_{2}=3/6$
(Deheuvels [5], 1983), a first order MAR process with standard Fréchet
marginals and autoregressive parameter $\phi=0.5$ (Davis and Resnick [4],
1989), a Markov chain (MC) with standard Gumbel marginals and logistic joint
distribution with dependence parameter $\alpha=0.5$ (Smith [16], 1992), an
ARCH(1) process with Gaussian innovations, autoregressive parameter
$\lambda=0.5$ and variance parameter $\beta=1.9\cdot 10^{-5}$ (Embrechts et
al., [6] 1997). The theoretical extremal index values of the processes ARCau,
ARUnif, MM, MAR, MC and ARCH are, respectively, $0.64$, $0.75$, $0.5$, $0.5$,
$0.328$ and $0.835$.

The root mean squared errors (rmse) and the absolute mean biases (abias) are
given in Table 1 for $n=1000$ and Table 2 for $n=5000$.

For comparison, we consider two direct competitors of our estimator, as
already mentioned in the Introduction, also requiring only one tuning
parameter: the sliding blocks estimator of Northrop ([15], 2015) based on a
block length choice and the estimator of Ferro and Segers ([11], 2003) which
depends on the choice of the high threshold. The first is denoted
$\widetilde{\theta}^{N}$ and is computed for the same block lengths
$r=10,20,30,40,50,70$ used in our proposal $\widetilde{\widetilde{\theta}}$.
Ferro and Segers estimator is denoted $\widetilde{\theta}^{FS}$ and obtained
for levels $u_{n}$ corresponding to the empirical quantiles $0.9$, $0.95$ and
$0.99$, with respective notation, $q_{0.90}$, $q_{0.95}$ and $q_{0.99}$.

Estimator $\widetilde{\widetilde{\theta}}$ seems to be competitive,
particularly in models ARUnif, ARCau and ARCH.

##  4 Application to financial data

The data consists of the log-returns of the exchange rate US dollar versus UK
pound, from January 2 of 1980 to May 21 of 1996 (Figure 1). An ARCH(1) fit was
performed in Embrechts et al., [6] (1997) leading to the theoretical
$\theta=0.835$.

Figure 2 presents estimates from $\widetilde{\theta}^{FS}$ computed for
thresholds corresponding to sample percentiles ranging from $40\%$ to $99\%$.
The estimated values tend to decrease as the threshold increases falling below
the theoretical one (horizontal line) from approximately quantile $86\%$.

Estimates obtained from $\widetilde{\widetilde{\theta}}$ and
$\widetilde{\theta}^{N}$, for $r=10,20,30,40,50,70$, can be seen in Table 3.
The results of $\widetilde{\widetilde{\theta}}$ are overall closer to the
theoretical $\theta=0.835$.

Figure 1: Log-returns of the exchange rate US dollar versus UK pound, from
January 2 of 1980 to May 21 of 1996. Figure 2: Plot of the
$\widetilde{\theta}^{FS}$ estimates for thresholds corresponding to sample
quantiles ranging from $40\%$ to $99\%$. The horizontal line corresponds to
theoretical $\theta=0.835$. Table 3: Extremal index estimates of the log-
returns of the exchange rate US dollar versus UK pound, from January 2 of 1980
to May 21 of 1996, obtained for estimators $\widetilde{\widetilde{\theta}}$
and $\widetilde{\theta}^{N}$, with block lengths $r=10,20,30,40,50,70$.

=2ex  $r=10$ $r=20$ $r=30$ $r=40$ $r=50$ $r=70$
$\widetilde{\widetilde{\theta}}$ 0.861 0.762 0.695 0.669 0.662 0.607
$\widetilde{\theta}^{N}$ 0.891 0.760 0.695 0.647 0.608 0.561

##  5 Conclusion

The idea of relating the extremal index with the tail dependence coefficient
is not new. For instance, in Ferreira and Ferreira ([9], 2012c), $\theta$ was
derived as a linear combination of lag-$m$ serial tail dependence
coefficients, under some local dependence conditions.

The new proposed estimator of the extremal index is based on a relation
between $\theta$ and the tail dependence coefficient $\lambda$ of a BEV
copula, without any assumptions on the dependence between the variables of the
sequence that has extremal index. This work shows that once we find a relation
between the extremal index and the tail dependence coefficient of some BEV
copula, we can always explore it to obtain other estimators of $\theta$ from
$\lambda$ estimation. Depending on the bivariate sequences we use to explore
that relation, we may find estimators that will work better for some class of
models than others. This approach opens up new avenues of investigation for
the estimation of the extremal index.

## References

  * [1] Cai, J.J. (2019). A nonparametric estimator of the extremal index, arXiv 1911.06674
  * [2] Chernick M.R. (1978). Mixing conditions and limit theorems for maxima of some stationary sequences. PhD dissertation, Stanford University.
  * [3] Chernick M.R., Hsing T., McCormick W.P. (1991). Calculating the extremal index for a class of stationary sequences. Advances in Applied Probability 23, 835–850.
  * [4] Davis R., Resnick S. (1989). Basic properties and prediction of max-ARMA processes. Advances in Applied Probability 21, 781–803.
  * [5] Deheuvels P. (1983). Point processes and multivariate extreme values. Journal of Multivariate Analysis 13, 257–272.
  * [6] Embrechts, P., Klüppelberg, C., Mikosch, T. (1997). Modelling Extremal Events. Springer, Berlin.
  * [7] Ferreira, H., Ferreira, M. (2012a). On extremal dependence of block vectors. Kybernetika 48(5), 988–1006.
  * [8] Ferreira, H., Ferreira, M. (2012b). Fragility Index of block tailed vectors. J. Statist. Plann. Inference 142(7), 1837–1848.
  * [9] Ferreira M., Ferreira H. (2012c). On extremal dependence: some contributions. TEST 21(3), 566–583.
  * [10] Ferreira, H., Ferreira, M. (2018). Estimating the extremal index through local dependence. Annales de l?Institut Henri Poincaré - Probabilités et Statistiques, 54(2), 587–605.
  * [11] Ferro C.A.T., Segers J. (2003). Inference for clusters of extreme values. Journal of the Royal Statistical Society: Series B 65, 545–556.
  * [12] Huang, X. (1992). Statistics of bivariate extreme values. PhD thesis, Erasmus University Rotterdam, Tinbergen, Institute Research Series 22.
  * [13] Hsing T., Hüsler J., Leadbetter M.R. (1988). On the exceedance point process for a stationary sequence. Probability Theory and Related Fields 78, 97–112.
  * [14] Moloney, N.R., Faranda, D., Sato, Y. (2019). An overview of the extremal index. Chaos 29, 022101.
  * [15] Northrop, P.J. (2015). An efficient semiparametric maxima estimator of the extremal index. Extremes 18(4), 585–603.
  * [16] Smith, R. (1992). The Extremal Index for a Markov Chain. Journal of Applied Probability 29(1), 37-45.
  * [17] Smith R.L., Weissman I. (1996). Characterization and estimation of the multivariate extremal index. Technical report, University of North Carolina at Chapel Hill, NC.
  * [18] Weissman I., Novak S.Y. (1998). On blocks and runs estimators of the extremal index. Journal of Statistical Planning and Inference 66(2), 281–288.

Table 1: The root mean squared error (rmse) and the absolute mean bias (abias)
obtained for estimator $\widetilde{\widetilde{\theta}}$ (with block lengths
$r=10,20,30,40,50,70$ and $n=1000$) and estimator $\widetilde{\theta}^{FS}$
(with levels $u_{n}$ corresponding to the empirical quantiles $0.9$, $0.95$
and $0.99$, respectively denoted, $q_{0.90}$, $q_{0.95}$ and $q_{0.99}$). The
results in bold correspond to the best performance and the italic denotes the
second best performance within each model.

=2ex  rmse MAR MM ARUnif ARCau ARCH MC $\widetilde{\widetilde{\theta}}$
($r=10$) 0.097 0.082 0.105 0.101 0.058 0.140 $\widetilde{\widetilde{\theta}}$
($r=20$) 0.093 0.069 0.068 0.078 0.090 0.142 $\widetilde{\widetilde{\theta}}$
($r=30$) 0.106 0.072 0.071 0.078 0.122 0.122 $\widetilde{\widetilde{\theta}}$
($r=40$) 0.107 0.066 0.068 0.075 0.145 0.159 $\widetilde{\widetilde{\theta}}$
($r=50$) 0.112 0.072 0.091 0.080 0.161 0.164 $\widetilde{\widetilde{\theta}}$
($r=70$) 0.107 0.084 0.129 0.090 0.195 0.172 $\widetilde{\theta}^{N}$ ($r=10$)
0.060 0.069 0.250 0.195 0.083 0.108 $\widetilde{\theta}^{N}$ ($r=20$) 0.054
0.048 0.219 0.111 0.079 0.081 $\widetilde{\theta}^{N}$ ($r=30$) 0.064 0.051
0.186 0.099 0.092 0.083 $\widetilde{\theta}^{N}$ ($r=40$) 0.070 0.061 0.168
0.100 0.100 0.087 $\widetilde{\theta}^{N}$ ($r=50$) 0.074 0.075 0.157 0.107
0.108 0.091 $\widetilde{\theta}^{N}$ ($r=70$) 0.090 0.091 0.146 0.128 0.125
0.108 $\widetilde{\theta}^{FS}$ ($q_{0.90}$) 0.080 0.075 0.239 0.125 0.119
0.088 $\widetilde{\theta}^{FS}$ ($q_{0.95}$) 0.100 0.111 0.201 0.151 0.122
0.165 $\widetilde{\theta}^{FS}$ ($q_{0.99}$) 0.250 0.201 0.208 0.231 0.165
0.323 abias MAR MM ARUnif ARCau ARCH MC $\widetilde{\widetilde{\theta}}$
($r=10$) 0.066 0.070 0.097 0.085 0.024 0.119 $\widetilde{\widetilde{\theta}}$
($r=20$) 0.046 0.041 0.040 0.036 0.061 0.098 $\widetilde{\widetilde{\theta}}$
($r=30$) 0.041 0.033 0.006 0.013 0.096 0.096 $\widetilde{\widetilde{\theta}}$
($r=40$) 0.037 0.029 0.019 0.000 0.120 0.096 $\widetilde{\widetilde{\theta}}$
($r=50$) 0.033 0.025 0.049 0.009 0.140 0.103 $\widetilde{\widetilde{\theta}}$
($r=70$) 0.024 0.013 0.101 0.039 0.180 0.110 $\widetilde{\theta}^{N}$ ($r=10$)
0.052 0.062 0.250 0.191 0.068 0.102 $\widetilde{\theta}^{N}$ ($r=20$) 0.027
0.024 0.215 0.094 0.032 0.063 $\widetilde{\theta}^{N}$ ($r=30$) 0.019 0.012
0.173 0.064 0.015 0.051 $\widetilde{\theta}^{N}$ ($r=40$) 0.013 0.008 0.143
0.048 0.006 0.045 $\widetilde{\theta}^{N}$ ($r=50$) 0.007 0.006 0.122 0.040
0.003 0.040 $\widetilde{\theta}^{N}$ ($r=70$) 0.011 0.001 0.093 0.035 0.018
0.039 $\widetilde{\theta}^{FS}$ ($q_{0.90}$) 0.014 0.010 0.232 0.079 0.031
0.036 $\widetilde{\theta}^{FS}$ ($q_{0.95}$) 0.019 0.015 0.178 0.056 0.024
0.068 $\widetilde{\theta}^{FS}$ ($q_{0.99}$) 0.124 0.103 0.133 0.130 0.030
0.219

Table 2: The root mean squared error (rmse) and the absolute mean bias (abias)
obtained for estimator $\widetilde{\widetilde{\theta}}$ (with block lengths
$r=10,20,30,40,50,70$ and $n=5000$) and estimator $\widetilde{\theta}^{FS}$
(with levels $u_{n}$ corresponding to the empirical quantiles $0.9$, $0.95$
and $0.99$, respectively denoted, $q_{0.90}$, $q_{0.95}$ and $q_{0.99}$). The
results in bold correspond to the best performance and the italic denotes the
second best performance within each model.

=2ex  rmse MAR MM ARUnif ARCau ARCH MC $\widetilde{\widetilde{\theta}}$
($r=10$) 0.055 0.071 0.136 0.092 0.033 0.100 $\widetilde{\widetilde{\theta}}$
($r=20$) 0.053 0.045 0.088 0.064 0.043 0.077 $\widetilde{\widetilde{\theta}}$
($r=30$) 0.061 0.038 0.072 0.062 0.053 0.077 $\widetilde{\widetilde{\theta}}$
($r=40$) 0.069 0.040 0.061 0.067 0.066 0.081 $\widetilde{\widetilde{\theta}}$
($r=50$) 0.074 0.045 0.055 0.072 0.076 0.086 $\widetilde{\widetilde{\theta}}$
($r=70$) 0.089 0.051 0.055 0.072 0.090 0.099 $\widetilde{\theta}^{N}$ ($r=10$)
0.050 0.068 0.250 0.188 0.074 0.105 $\widetilde{\theta}^{N}$ ($r=20$) 0.031
0.038 0.223 0.093 0.045 0.063 $\widetilde{\theta}^{N}$ ($r=30$) 0.030 0.030
0.177 0.066 0.044 0.055 $\widetilde{\theta}^{N}$ ($r=40$) 0.032 0.029 0.153
0.054 0.046 0.045 $\widetilde{\theta}^{N}$ ($r=50$) 0.034 0.031 0.136 0.050
0.050 0.043 $\widetilde{\theta}^{N}$ ($r=70$) 0.040 0.034 0.116 0.054 0.059
0.045 $\widetilde{\theta}^{FS}$ ($q_{0.90}$) 0.041 0.035 0.247 0.077 0.057
0.032 $\widetilde{\theta}^{FS}$ ($q_{0.95}$) 0.047 0.049 0.170 0.057 0.065
0.045 $\widetilde{\theta}^{FS}$ ($q_{0.99}$) 0.119 0.083 0.145 0.131 0.115
0.118 abias MAR MM ARUnif ARCau ARCH MC $\widetilde{\widetilde{\theta}}$
($r=10$) 0.047 0.068 0.133 0.088 0.017 0.045 $\widetilde{\widetilde{\theta}}$
($r=20$) 0.027 0.035 0.078 0.046 0.008 0.056 $\widetilde{\widetilde{\theta}}$
($r=30$) 0.022 0.024 0.057 0.034 0.021 0.095 $\widetilde{\widetilde{\theta}}$
($r=40$) 0.023 0.020 0.042 0.031 0.037 0.041 $\widetilde{\widetilde{\theta}}$
($r=50$) 0.024 0.023 0.027 0.027 0.045 0.040 $\widetilde{\widetilde{\theta}}$
($r=70$) 0.021 0.021 0.014 0.018 0.060 0.046 $\widetilde{\theta}^{N}$ ($r=10$)
0.048 0.067 0.250 0.187 0.071 0.018 $\widetilde{\theta}^{N}$ ($r=20$) 0.024
0.034 0.222 0.088 0.033 0.024 $\widetilde{\theta}^{N}$ ($r=30$) 0.015 0.021
0.174 0.055 0.018 0.040 $\widetilde{\theta}^{N}$ ($r=40$) 0.010 0.016 0.148
0.038 0.010 0.049 $\widetilde{\theta}^{N}$ ($r=50$) 0.006 0.013 0.128 0.027
0.004 0.054 $\widetilde{\theta}^{N}$ ($r=70$) 0.000 0.008 0.103 0.018 0.005
0.063 $\widetilde{\theta}^{FS}$ ($q_{0.90}$) 0.015 0.000 0.245 0.057 0.024
0.014 $\widetilde{\theta}^{FS}$ ($q_{0.95}$) 0.007 0.005 0.156 0.021 0.011
0.011 $\widetilde{\theta}^{FS}$ ($q_{0.99}$) 0.044 0.005 0.087 0.053 0.016
0.048


# Bounding Lifts of Markoff Triples $\text{mod}\,p$

Elisa Bellah  (Bellah) Department of Mathematics, Carnegie Mellon University
,  Siran Chen  (Chen) Department of Mathematics, Carnegie Mellon University  ,
Elena Fuchs  (Fuchs) Department of Mathematics, University of California,
Davis  and  Lynnelle Ye

###### Abstract.

In 2016, Bourgain, Gamburd, and Sarnak proved that Strong Approximation holds
for the Markoff surface in most cases. That is, the modulo $p$ solutions to
the equation $X_{1}^{2}+X_{2}^{2}+X_{3}^{2}=3X_{1}X_{2}X_{3}$ are covered by
the integer solutions for most primes $p$. In this paper, we provide upper
bounds on lifts of $\text{mod}\,p$ points of the Markoff surface by analyzing
the growth along paths in the Markoff $\text{mod}\,p$ graphs. Our first upper
bound follows the algorithm given in the paper of Bourgain, Gamburd, and
Sarnak, which constructs a path of possibly long length but where points grow
relatively slowly. Our second bound considers paths in these graphs of short
length but possibly large growth. We then provide numerical evidence and
heuristic arguments for how these bounds might be improved.

##  1\. Introduction

The Markoff surface $\mathbb{X}$ is the affine surface in $\mathbb{A}^{3}$
given by

$\mathbb{X}:X_{1}^{2}+X_{2}^{2}+X_{3}^{2}=3X_{1}X_{2}X_{3},$

and the integer points $\mathbb{X}(\mathbb{Z})$ are called Markoff Triples.
Markoff first studied these triples in the context of Diophantine
approximation and the theory of quadratic forms (see [12] or Chapter 2 of [3],
for example). Markoff triples have since found application in other areas. For
example, Cohn used these triples to study free groups on two generators (see
Theorem 2 of [6]), and in [10] Hirzebruch and Zagier used Markoff triples to
study the signature of certain 4-dimensional manifolds. More recently, work
has been done to study Markoff surface modulo $p$.

Define the Vieta group $\Gamma$ to be the group of affine integral morphisms
on $\mathbb{A}^{3}$ generated by permutations $\sigma_{ij}$ and the Vieta
involutions $R_{i}$; that is

$\sigma_{12}(x_{1},x_{2},x_{3})=(x_{2},x_{1},x_{3}),$
$R_{1}(x_{1},x_{2},x_{3})=(3x_{2}x_{3}-x_{1},x_{2},x_{3}),$

and the remaining $\sigma_{ij}$ and $R_{2},R_{3}$ are defined similarly. It is
well-known that the orbit of $(1,1,1)$ under $\Gamma$ gives all the nonzero
Markoff triples (see [1], for example). It is expected that the same holds
modulo $p$. More precisely, we have the following conjecture.

######  Conjecture 1.1 (Strong Approximation).

For any prime $p$,

$\Gamma\cdot(1,1,1)=\mathbb{X}(\mathbb{Z}/p\mathbb{Z})-\\{(0,0,0)\\}.$

In Theorem 1 of [2], Bourgain, Gamburd and Sarnak show that Strong
Approximation holds for primes $p$ where $p^{2}-1$ does not have too many
divisors. The authors prove this theorem by showing algorithmically that the
Markoff mod $p$ graphs, defined in Section 2, are connected.

It is conjectured that the Markoff $\text{mod}\,p$ graphs in fact form an
expander family, and so in light of [4] these graphs have been proposed as a
means to produce cryptographic hash functions. In [9], it is noted that one
avenue of attack depends on the difficulty of finding lifts of Markoff triples
modulo $p$.

Throughout this paper, we assume that $p>3$ is prime. For convenience, we set
the following notation and terminology. We denote the nonzero $\text{mod}\,p$
points $\mathbb{X}(\mathbb{Z}/p\mathbb{Z})-\\{(0,0,0)\\}$ by
$\mathbb{X}^{*}(p)$ and call elements in $\mathbf{x}\in\mathbb{X}^{*}(p)$
Markoff $\text{mod}\,p$ points. We refer to the algorithm given by Bourgain,
Gamburd, and Sarnak in [2] to BGS algorithm.

Define the size of a Markoff triple $\mathbf{x}=(x_{1},x_{2},x_{3})$ by

$\operatorname{size}(\mathbf{x}):=\max\\{x_{1},x_{2},x_{3}\\}.$

Furthermore, for a Markoff $\text{mod}\,p$ point
$\mathbf{x}\in\mathbb{X}^{*}(p)$ we call a Markoff triple $\tilde{\mathbf{x}}$
a lift of $\mathbf{x}$ if we have
$\tilde{\mathbf{x}}\equiv\mathbf{x}(\text{mod}\,p)$. The main results of this
paper give bounds on the size of minimal lifts by considering “optimal” paths
in the Markoff $\text{mod}\,p$ graphs, which are defined in Section 2 along
with relevant definitions. We show the following.

######  Theorem 1.2.

Let $p$ be a prime so that
$\operatorname{ord}_{p}(\operatorname{rot}_{1}^{n}(1,1,1))\geq p-1$ for $0\leq
n\leq 5$ and suppose that $\mathbf{x}\in\mathbb{X}^{*}(p)$ with
$\operatorname{ord}_{p}(\mathbf{x})>p^{1/2}$. Let $\tilde{\mathbf{x}}$ be a
lift of $\mathbf{x}$ of minimal size. Then,

$\operatorname{size}(\tilde{\mathbf{x}})<(3\varepsilon)^{96(2p+1)^{4}},$

where $\varepsilon=(3+\sqrt{5})/{2}$.

In Section 4, we give numerical evidence to show that the conditions in
Theorem 1.2 appear to be satisfied for many primes $p$ and approximately 80%
of Markoff $\text{mod}\,p$ points. Furthermore, we provide direction for how
these results might be obtained theoretically, and for obtaining upper bounds
on the sizes of smallest lifts for the remaining points $\mathbf{x}$ in
$\mathbb{X}^{*}(p)$ with $\operatorname{ord}_{p}(\mathbf{x})\leq p^{1/2}$.

Our second upper bound is conditional on Strong Approximation, and depends on
the expansion constant $h(p)$ of the Markoff $\text{mod}\,p$ graph
$\mathcal{G}_{p}$, but holds for all points $\mathbf{x}$ in
$\mathbb{X}^{*}(p)$. It is expected that the family of Markoff $\text{mod}\,p$
graphs $(\mathcal{G}_{p})_{p}$ forms an expander family, and so this bound is
expected to be uniform (see the discussion on Super Strong Approximation in
Section 5). We show the following.

######  Theorem 1.3.

Let $p$ be any prime where Strong Approximation holds, and let $h(p)$ be the
expansion constant of the Markoff graph $\mathcal{G}_{p}$. For
$\mathbf{x}\in\mathbb{X}^{*}(p)$, let $\tilde{\mathbf{x}}$ be a lift of
$\mathbf{x}$ of minimal size. Then,

$\operatorname{size}(\tilde{\mathbf{x}})<(3\varepsilon)^{\alpha},$

where $\varepsilon=(3+\sqrt{5})/{2}$ and

$\alpha=\left(\frac{p^{3}+3}{2}\right)^{20/\log\left(1+\frac{h(p)}{3}\right)}.$

This paper is organized as follows. In Section 2 we introduce special elements
of the Vieta group, called rotations, and give an explicit upper bound for the
growth of Markoff triples under the action of the group of rotations. In
Sections 2 and 3 we give the necessary background and an explicit description
of the algorithm given in the paper [2] of Bourgain, Gamburd, and Sarnak for
which Theorem 1.2 rests, and provide several alternate proofs to those given
in [2] using the language of linear recurrence sequences. In Section 4 we
prove Theorem 1.2 and give numerical evidence and a heuristic argument for how
one might relax the conditions of this Theorem. In Section 5 we prove Theorem
1.3 and give evidence for how this bound might be improved on average.
Finally, in Section 6 we discuss an alternate approach to finding paths in the
Markoff $\text{mod}\,p$ graphs which could be used for further improvements to
the bounds given in Theorems 1.2 and 1.3.

##  2\. Rotations and The Markoff $\text{mod}\,p$ Graphs

To analyze lifts, we consider the following special elements in the Vieta
group $\Gamma$ as introduced in [2].

######  Definition 2.1.

The rotations of $\Gamma$ are the elements $\operatorname{rot}_{i}$ given by

$\operatorname{rot}_{1}=\sigma_{23}R_{2},\operatorname{rot}_{2}=\sigma_{13}R_{1},\text{
and }\operatorname{rot}_{3}=\sigma_{12}R_{1}.$

Explicitly, we have

$\operatorname{rot}_{1}(x_{1},x_{2},x_{3})=(x_{1},x_{3},3x_{1}x_{3}-x_{2})$
$\operatorname{rot}_{2}(x_{1},x_{2},x_{3})=(x_{3},x_{2},3x_{2}x_{3}-x_{1})$
$\operatorname{rot}_{3}(x_{1},x_{2},x_{3})=(x_{2},3x_{2}x_{3}-x_{1},x_{3}).$

For a prime $p$, the Markoff $\text{mod}\,p$ graph $\mathcal{G}_{p}$ is
defined to be the graph with vertex set $\mathbb{X}^{*}(p)$ and edges
$(\mathbf{x},\operatorname{rot}_{i}\mathbf{x})$ for $i\in\\{1,2,3\\}$.

In Figure 1 we give an example of the Markoff mod $p$ graph $\mathcal{G}_{p}$
when $p=31$ to demonstrate the complexity of the path structure for these
graphs. In this figure, nodes are colored depending on their rotation order,
with blue nodes corresponding to points in the cage (defined in Section 3.1).

Figure 1. The Markoff $\text{mod}\,p$ graph $\mathcal{G}_{p}$ when $p=31$

###  2.1. Sizes under action of rotations

It’s known that in most cases, the Markoff $\text{mod}\,p$ graph
$\mathcal{G}_{p}$ is connected (see [2] and [5]). Observe that when
$\mathcal{G}_{p}$ is connected, we can construct lifts of points in
$\mathbb{X}^{*}(p)$ by finding paths between $(1,1,1)$ and points
$\mathbf{x}\in\mathcal{G}_{p}$. Proposition 2.3 will tell us that finding
small lifts modulo $p$ can then be done by finding “optimal” paths in
$\mathcal{G}_{p}$. Observe that we have the following.

######  Lemma 2.2.

Given $(x_{1},x_{2},x_{3})\in\mathbb{X}^{*}(p)$ we have

$\operatorname{rot}_{1}^{n}(x_{1},x_{2},x_{3})=(x_{1},a_{n},a_{n+1}),$

where $a_{n}$ is the linear recurrence sequence with initial conditions
$a_{0}=x_{2},a_{1}=x_{3}$ and recurrence

$a_{n+2}=3x_{i}a_{n+1}-a_{n}.$

Similarly,
$\operatorname{rot}_{i}^{n}(x_{1},x_{2},x_{3})=\sigma(x_{i},a_{n},a_{n+1})$
where the sequence $a_{n}$ has initial conditions given by the other two
coordinates $x_{i},x_{j}$ and recurrence as above, and $\sigma$ is a suitable
permutation.

This observation allows us to analyze the growth of points obtained from
$(1,1,1)$ by the action of
$\langle\operatorname{rot}_{1},\operatorname{rot}_{2},\operatorname{rot}_{3}\rangle$.
We have the following.

######  Proposition 2.3.

Let $n_{i}\in\mathbb{Z}_{\geq 1}$ and $i_{j}\in\\{1,2,3\\}$. Then we have

$\operatorname{size}(\operatorname{rot}_{i_{s}}^{n_{s}}\cdots\operatorname{rot}_{i_{1}}^{n_{1}}(1,1,1))\leq(3\varepsilon)^{2^{s-1}(n_{1}+1)\cdots(n_{s}+1)},$

where $\varepsilon=\frac{3+\sqrt{5}}{2}$.

Note that an exponential lower bound can be derived using a similar method to
that outlined below, and so we obtain a result similar to that of Zagier in
[13], which bounds the growth of sizes in the Markoff tree. Furthermore, we
see that switching between rotations contributes doubly exponentially in
growth, while traveling along a single rotation only contributes
exponentially. Theorem 1.2 follows the path constructed by Bourgain, Gamburd
and Sarnak in [2] which has a relatively small number of switches between
different rotations, but possibly long path lengths along each orbit. Theorem
1.3 instead considers paths of shortest possible length, but possibly many
switches between distinct rotations.

###### Proof of Proposition 2.3.

Let $\mathbf{x}=(x_{1},x_{2},x_{3})$ be a Markoff triple, and without loss of
generality set $x=x_{1}$ and suppose that $x>0$. Let $a_{n}$ denote the linear
recurrence sequence defined in Lemma 2.2, and
$\varepsilon_{x},\bar{\varepsilon}_{x}$ denote the characteristic roots of
$a_{n}$. That is, $\varepsilon_{x},\bar{\varepsilon}_{x}$ are the roots of the
minimal polynomial of the sequence $a_{n}$, which is given by

$f_{x}(T)=T^{2}-3xT+1.$

Note that $f_{x}$ has distinct positive real roots, so we can set
$\varepsilon_{x}>\bar{\varepsilon}_{x}$. Since $a_{n}$ is a linear recurrence
sequence we can write

$a_{n}=A\varepsilon_{x}^{n}+B\bar{\varepsilon}_{x}^{n}$

for some $A,B\in\mathbb{Q}(\varepsilon)$. Using our initial conditions we have

$x_{2}=A+B\text{ and }x_{3}=A\varepsilon_{x}+B\bar{\varepsilon}_{x},$

and so solving for $A$ and $B$ gives

$a_{n+1}=\frac{(x_{3}-x_{2}\bar{\varepsilon}_{x})\varepsilon_{x}^{n+1}+(\varepsilon_{x}x_{2}-x_{3})\bar{\varepsilon}_{x}^{n+1}}{\varepsilon_{x}-\bar{\varepsilon}_{x}}$
(2.1)
$=x_{3}\cdot\frac{\varepsilon_{x}^{n+1}-\bar{\varepsilon}_{x}^{n+1}}{\varepsilon_{x}-\bar{\varepsilon}_{x}}-x_{2}\cdot\frac{\varepsilon_{x}^{n}-\bar{\varepsilon}_{x}^{n}}{\varepsilon_{x}-\bar{\varepsilon}_{x}},$

where the second equality uses that $\varepsilon_{x}\bar{\varepsilon}_{x}=1$.

We induct on $s\in\mathbb{Z}_{\geq 1}$. When $s=1$, Equation (2.1) gives

$\displaystyle\operatorname{size}(\operatorname{rot}_{i_{1}}^{n_{1}}(1,1,1))$
$\displaystyle<\frac{\varepsilon^{n+1}-\bar{\varepsilon}^{n+1}}{\varepsilon-\bar{\varepsilon}}$
$\displaystyle<\frac{\varepsilon^{n+1}}{\varepsilon-\bar{\varepsilon}}$
$\displaystyle<\varepsilon^{n+1},$

where $\varepsilon=(3+\sqrt{5})/2$, as desired.

Next, suppose that

$\mathbf{x}=\operatorname{rot}_{i_{s-1}}^{n_{s-1}}\cdots\operatorname{rot}_{i_{1}}^{n_{1}}(1,1,1)$

and let $x$ denote the $i_{s}$th coordinate of $\mathbf{x}$. We have

$\displaystyle\operatorname{size}(\operatorname{rot}_{i_{s}}^{n_{s}}(\mathbf{x}))$
$\displaystyle<\operatorname{size}(\mathbf{x})\,\varepsilon_{x}^{n_{s}+1},\text{
by Equation (\ref{eq0})}$
$\displaystyle=\operatorname{size}(\mathbf{x})\cdot\left(\frac{3x+\sqrt{(3x)^{2}-4}}{2}\right)^{n_{s}+1}$
$\displaystyle<\operatorname{size}(\mathbf{x})\cdot\left(\frac{3x+\sqrt{(3x)^{2}}}{2}\right)^{n_{s}+1}$
$\displaystyle=\operatorname{size}(\mathbf{x})\cdot(3\operatorname{size}(\mathbf{x}))^{n_{s}+1},$

and so the result follows by induction. ∎

######  Remark 2.4.

In Figure 2, the sizes of points

$\operatorname{rot}_{i_{s}}\cdots\operatorname{rot}_{i_{1}}(1,1,1)$

are graphed with the number of rotations $s$ on the horizontal axis. Observe
that our upper bound in Proposition 2.3 overshoots the growth of these sizes.
However, through our experimentation is appears that a tight upper bound will
still depend doubly exponentially on $s$ and exponentially on the $n_{i}$.
Improvements to this upper bound or derivation of such an asymptotic would
improve the results of this paper, but we expect the true upper bound to still
depend on a balance of finding paths in $\mathcal{G}_{p}$ which are short
(i.e. minimizes the $n_{i}$, which we expect contributes exponentially to the
asymptotic growth as in Proposition 2.3) but switch between distinct rotations
minimally (i.e. minimizes $s$, which we contribute doubly exponentially to the
asmptotic growth as in Proposition 2.3).

Figure 2. Size of
$\operatorname{rot}_{i_{s}}\cdots\operatorname{rot}_{i_{1}}(1,1,1)$

###  2.2. Rotation Orders and Conic Sections

The BGS algorithm constructs paths in the Markoff mod $p$ graph by analyzing
the orbits under the rotations, defined in 2.1. We present the analysis of
these orbits as in [2], giving alternate proofs of several results.

######  Definition 2.5.

For $\mathbf{x}=(x_{1},x_{2},x_{3})\in\mathbb{X}^{*}(p)$, we define the
following.

  1. (1)

The $i$th rotation order of $\mathbf{x}$ is given by

$\operatorname{ord}_{p,i}(\mathbf{x}):=\min\\{n\in\mathbb{Z}_{>0}\mid\operatorname{rot}_{i}^{n}(X)\equiv
X(\text{mod}\,p)\\}.$

  2. (2)

The rotation order of $\mathbf{x}$ is given by

$\operatorname{ord}_{p}(\mathbf{x}):=\max\\{\operatorname{ord}_{p,i}(x)\mid
i=1,2,3\\}.$

If $\operatorname{ord}_{p}(\mathbf{x})=\operatorname{ord}_{p,i}(\mathbf{x})$,
then we call $i$ the maximal index of $\mathbf{x}$.

Observe that for distinct $i,j,k$, $\operatorname{rot}_{i}$ acts on
$(x_{j},x_{k})$, and we can write

$\operatorname{rot}_{i}(x_{i})\begin{pmatrix}x_{j}\\\
x_{k}\end{pmatrix}=\begin{pmatrix}0&1\\\
-1&3x_{i}\end{pmatrix}\begin{pmatrix}x_{k}\\\ x_{j}\end{pmatrix}.$

So, the $i$th rotation order of $\mathbf{x}$ is equal to the order of

$\begin{pmatrix}0&1\\\ -1&3x_{i}\end{pmatrix}$

in $\operatorname{SL}_{2}(\mathbb{F}_{p})$. Note in particular that
$\operatorname{rot}_{p,i}(\mathbf{x})$ only depends on the $i$th coordinate of
$\mathbf{x}$.

######  Definition 2.6.

We set the following notation. For
$\mathbf{x}=(x_{1},x_{2},x_{3})\in\mathbb{X}^{*}(p)$, let
$M_{\mathbf{x},i}:=\\{\operatorname{rot}_{i}^{n}(\mathbf{x})\mid
n\in\mathbb{Z}\\}$ be the orbit of $\mathbf{x}$ under
$\operatorname{rot}_{i}$. Furthermore, let

$A_{\mathbf{x},i}:=\begin{pmatrix}0&1\\\ -1&3x_{i}\end{pmatrix}$

be the matrix discussed above, and denote the characteristic polynomial of
$A_{\mathbf{x},i}$ by $f_{\mathbf{x},i}$ and the discriminant of
$f_{\mathbf{x},i}$ by $\Delta_{\mathbf{x},i}$. In our analysis below, we will
sometimes only be concerned with a single coordinate $x$ of a Markoff
$\text{mod}\,p$ point. In this case, we will instead use the notation
$M_{x},A_{x},f_{x}$ and $\Delta_{x}$, respectively.

Note that the action of $\operatorname{rot}_{i}$ on a Markoff triple
$\mathbf{x}$ leaves the $i$th coordinate of $\mathbf{x}$ fixed, and so the
orbits $M_{\mathbf{x},i}$ correspond to points inside of some conic section
with discriminant $\Delta_{\mathbf{x},i}$. Given $a\in\mathbb{Z}/p\mathbb{Z}$
we use the notation

$C_{i}(a):=\\{(x_{1},x_{2},x_{3})\in\mathbb{X}^{*}(p)\mid x_{i}=a\\}$

to denote the conic section consisting of Markoff $\text{mod}\,p$ points with
$i$th coordinate equal to $a$. Note that we may also use the notation
$C_{i}(\mathbf{x})$ to indicate the conic section cut out by fixing the $i$th
coordinate of $\mathbf{x}$. Accordingly, we have the following definition.

######  Definition 2.7.

Let $\mathbf{x}=(x_{1},x_{2},x_{3})\in\mathbb{X}^{*}(p)$ be a Markoff
$\text{mod}\,p$ point with $i$th coordinate equal to $x$. We say that $x$ is

  1. (1)

parabolic if $\Delta_{x}\equiv 0(\text{mod}\,p)$,

  2. (2)

hyperbolic if $\Delta_{x}$ is a nonzero square modulo $p$, and

  3. (3)

elliptic if $\Delta_{x}$ is not a square modulo $p$.

We have the following observation.

######  Lemma 2.8.

Let $\mathbf{x}=(x_{1},x_{2},x_{3})$ be a Markoff $\text{mod}\,p$, and set
$x=x_{i}$. Let $\varepsilon_{x}$ a root of $f_{x}$. If $x$ is not parabolic,
then $\operatorname{ord}_{p,i}(\mathbf{x})$ is equal to the order of
$\varepsilon_{x}$ in $\mathbb{F}^{\times}$, where

$\mathbb{F}=\begin{cases}\mathbb{F}_{p}&\text{ when $x$ is hyperbolic}\\\
\mathbb{F}_{p^{2}}&\text{ when $x$ is elliptic}\end{cases}$

under the identification
$\mathbb{F}_{p^{2}}\cong\mathbb{F}_{p}[T]/(T^{2}-\Delta_{x}).$

###### Proof.

When $x$ is hyperbolic or elliptic, $A_{x}$ is diagonalizable over
$\mathbb{F}$ with eigenvalues given by $\varepsilon_{x}$ and its conjugate
$\bar{\varepsilon}_{x}$. Since $\varepsilon_{x},\bar{\varepsilon}_{x}$ are
roots of

$f_{x}(T)=T^{2}-3xT+1$

then we have $\bar{\varepsilon}_{x}=\varepsilon_{x}^{-1}$. This gives

$A_{x}^{n}=P^{n}\begin{pmatrix}\varepsilon_{x}^{n}&0\\\
0&\varepsilon_{x}^{-n}\end{pmatrix}P^{-n}$

where $P\in\operatorname{SL}_{n}(\mathbb{F})$. So, the order of $A_{x}$ is
equal to the order of $\varepsilon$ in $\mathbb{F}$. ∎

The following Proposition can be found in Lemma 3 of [2]. We present an
alternate proof of this result here.

######  Proposition 2.9.

Let $\mathbf{x}=(x_{1},x_{2},x_{3})\in\mathbb{X}^{*}(p)$. For a prime $p>3$.
We have

$\operatorname{ord}_{p,i}(\mathbf{x})\text{ divides }\begin{cases}p-1&\text{
if $x_{i}$ is hyperbolic}\\\ p+1&\text{ if $x_{i}$ is elliptic}.\end{cases}$

If $x_{i}$ is parabolic, then $x_{i}=\pm 2/3$ and we have

$\operatorname{ord}_{p,i}(\mathbf{x})=\begin{cases}2p&\text{ if }x_{i}=-2/3\\\
p&\text{ if }x_{i}=2/3.\end{cases}$

###### Proof.

For convenience, set $x=x_{i}$ and $\varepsilon=\varepsilon_{x}$. If $x$ is
hyperbolic, then the result follows directly from Lemma 2.8. So suppose that
$x_{i}$ is elliptic. Since

$\varepsilon+\bar{\varepsilon}=3x_{i}\in\mathbb{F}_{p}^{\times}$

then we get

$(\varepsilon+\bar{\varepsilon})^{p}=\varepsilon+\bar{\varepsilon},$

and since $\bar{\varepsilon}=\varepsilon^{-1}$ then

$\varepsilon^{p}+\varepsilon^{-p}=\varepsilon+\varepsilon^{-1}.$

So, by Lemma 2.10 below, we have $\varepsilon=\varepsilon^{p}$ or
$\varepsilon=\varepsilon^{-p}$. But if $\varepsilon=\varepsilon^{p}$ then
$\varepsilon^{p-1}=1$ which implies $\varepsilon\in\mathbb{F}_{p}^{\times}$,
contradicting $x_{i}$ being elliptic. So we must have
$\varepsilon=\varepsilon^{-p}$ which gives $\varepsilon^{p+1}=1$. Hence, the
order of $\varepsilon$ divides $p+1$ and the result follows from Lemma 2.8.

Finally, suppose that $x$ is parabolic. Then $\Delta_{x}\equiv
0(\text{mod}\,p)$ which gives

$(3x)^{2}-4\equiv 0(\text{mod}\,p)\Rightarrow x\equiv\pm 2/3(\text{mod}\,p).$

Note that in the parabolic case $A_{x}$ has Jordan normal form

$A_{x}=P\begin{pmatrix}\varepsilon&1\\\ 0&\varepsilon\end{pmatrix}P^{-1},$

for some $P\in\operatorname{GL}_{2}(\mathbb{Z}/p\mathbb{Z})$ and so

(2.2) $A_{x}^{n}=P\begin{pmatrix}\varepsilon^{n}&n\varepsilon\\\
0&\varepsilon^{n}\end{pmatrix}P^{-1}.$

Recalling that $\varepsilon_{x}$ denotes a root of the characteristic
polynomial of $A_{x}$, we can compute

$\varepsilon_{x}=\begin{cases}1&\text{ if }x=2/3\\\ -1&\text{ if
}x=-2/3.\end{cases}.$

So, the result for the order of parabolic points follows from Equation (2.2)
and Lemma 2.8. ∎

######  Lemma 2.10.

If $a+a^{-1}=b+b^{-1}$ for nonzero elements $a,b$ in a field $\mathbb{F}$ with
$\text{char}(\mathbb{F})\not=2$ then we have $a=b$ or $a=b^{-1}$.

###### Proof.

If $a+a^{-1}=b+b^{-1}$ then multiplying both sides by $ab$ gives

$a^{2}b+b=ab^{2}+a\Rightarrow a^{2}b-a(b^{2}+1)+b=0.$

Since $\text{char}(\mathbb{F})\not=2$ the quadratic formula gives the desired
result. ∎

######  Definition 2.11.

Let $\mathbf{x}\in\mathbb{X}^{*}(p)$.

  1. (1)

If $\operatorname{ord}_{p,i}(\mathbf{x})=p-1$ then we say $x_{i}$ is maximal
hyperbolic.

  2. (2)

If $\operatorname{ord}_{p,i}(\mathbf{x})=p+1$ then we’ll call $x_{i}$ is
maximal elliptic, and

  3. (3)

If $\operatorname{ord}_{p,i}(\mathbf{x})=2p$ we say $x_{i}$ is maximal
parabolic.

A triple $\mathbf{x}\in\mathbb{X}^{*}(p)$ will be called maximal (hyperbolic,
elliptic, or parabolic) if one of its coordinates is either maximal
hyperbolic, elliptic, or parabolic.

###  2.3. Connection to Lucas Sequences

In Equation (2.1), we saw that the orbit of points $\mathbf{x}$ in
$\mathbb{X}^{*}(p)$ under a single rotation can be described in terms of a
corresponding Lucas sequence. We prove the following identity giving this
relation explicitly for any Markoff $\text{mod}\,p$ points, which may be
useful for future study, and is referenced in Section 3.5 as a possible
direction to relax the conditions of Theorem 1.2.

######  Lemma 2.12.

Let $\mathbf{x}\in\mathbb{X}^{*}(p)$ have $i$th coordinate $x$. Then,

$A_{x}^{n}=\begin{pmatrix}-u_{n-1}&u_{n}\\\ -u_{n}&u_{n+1}\end{pmatrix},$

where $A_{x}$ is the matrix defined in 2.6 and $u_{n}$ is the Lucas sequence
with integer parameters $(3x,1)$. That is, $u_{n}$ is the linear recurrence
sequence with initial conditions $u_{0}=0,u_{1}=1$ and recurrence
$u_{n+2}=3xu_{n+1}-u_{n}.$

###### Proof.

For convenience, set $x=x_{i}$. Observe that

$A_{x}=\begin{pmatrix}0&1\\\ -1&3x\end{pmatrix}=\begin{pmatrix}3x&-1\\\
1&0\end{pmatrix}^{-1}.$

The matrix on the right-hand side gives a familiar Lucas sequence identity. We
have

$\displaystyle\begin{pmatrix}0&1\\\ -1&3x\end{pmatrix}^{n}$
$\displaystyle=\begin{pmatrix}u_{n+1}&-u_{n}\\\
u_{n}&-u_{n-1}\end{pmatrix}^{-1}$
$\displaystyle=\frac{1}{u_{n}^{2}-u_{n+1}u_{n-1}}\begin{pmatrix}-u_{n-1}&u_{n}\\\
-u_{n}&u_{n+1}\end{pmatrix}.$

Now, let $\varepsilon,\bar{\varepsilon}$ be the roots of

$f(T)=T^{2}-3xT+1.$

Then, we can write

$u_{n}=\frac{\varepsilon^{n}-\bar{\varepsilon}^{n}}{\varepsilon-\bar{\varepsilon}}$

and we note that $\varepsilon\bar{\varepsilon}=1$. So we have

$\displaystyle u_{n}^{2}-u_{n+1}u_{n-1}$
$\displaystyle=\left(\frac{\varepsilon^{n}-\bar{\varepsilon}^{n}}{\varepsilon-\bar{\varepsilon}}\right)^{2}-\left(\frac{\varepsilon^{n+1}-\bar{\varepsilon}^{n+1}}{\varepsilon-\bar{\varepsilon}}\right)\left(\frac{\varepsilon^{n-1}-\bar{\varepsilon}^{n-1}}{\varepsilon-\bar{\varepsilon}}\right)$
$\displaystyle=\frac{1}{(\varepsilon-\bar{\varepsilon})^{2}}\left((\varepsilon^{2n}+\bar{\varepsilon}^{2n}-2)-(\varepsilon^{2n}+\bar{\varepsilon}^{2n}-(\varepsilon^{2}+\bar{\varepsilon}^{2}))\right)$
$\displaystyle=1,$

as required. ∎

##  3\. The BGS Algorithm

The algorithm outlined in [2] constructs a path between any two points in the
Markoff $\text{mod}\,p$ graph by connecting them through the cage, which we
discuss below. The BGS algorithm then guarantees a path between any two points
in the cage which contains at most two distinct rotations. In light of
Proposition 2.3, the paths constructed in the BGS algorithm are a good
candidate for small lifts, particularly when one or both of our points are in
the cage. In this section, we give an outline of the key components of the BGS
algorithm from [2], extracting explicit information when possible. An explicit
description of the path constructed by the BGS algorithm is then outlined in
Algorithm 3.6.

###  3.1. The Cage

Define the cage to be the subgraph $\mathcal{C}(p)$ of the Markoff
$\text{mod}\,p$ graph $\mathcal{G}_{p}$ containing all vertices that are
maximal points in $\mathbb{X}^{*}(p)$, as defined in 2.11. The convenience of
the cage is that the orbits with respect to the maximal index are precisely
equal to the conic sections at that index. More precisely, we have the
following.

######  Proposition 3.1.

If $\mathbf{x}=(x_{1},x_{2},x_{3})$ is in the cage $\mathcal{C}(p)$ with
maximal index $i$ then $M_{\mathbf{x},i}=C_{i}(x_{i})$. That is, if
$\mathbf{x}$ is a maximal triple with maximal index $i$, then the orbit of
$\mathbf{x}$ under $\operatorname{rot}_{i}$ contains all Markoff
$\text{mod}\,p$ points with $i$th coordinate equal to $x_{i}$.

This Proposition follows from our definition of maximal points along with the
following lemma which can be found in [2].

######  Lemma 3.2.

If $x$ is parabolic, then

$|C_{i}(x)|=\begin{cases}0&\text{ if }p\equiv-1(\text{mod}\,4)\\\ 2p&\text{ if
}p\equiv 1(\text{mod}\,4)\end{cases}.$

Otherwise, we have

$|C_{i}(x)|=\begin{cases}p+1&\text{ if $x$ is elliptic}\\\ p-1&\text{ if $x$
is hyperbolic}.\end{cases}$

The connectedness of the cage will then follow from the following result. For
completeness of our analysis and implementation of the BGS algorithm, we
outline the proof given in [2].

######  Lemma 3.3 (Section 3.2 of [2]).

Let $\mathbf{x},\mathbf{y}\in\mathcal{C}(p)$ with maximal indices
$i,j\in\\{1,2,3\\}$, respectively. Then there is a point
$\mathbf{z}\in\mathcal{C}(p)$ and $k\in\\{1,2,3\\}$ so that

$C_{i}(\mathbf{x})\cap C_{k}(\mathbf{z})\not=\varnothing\text{ and
}C_{j}(\mathbf{y})\cap C_{k}(\mathbf{z})\not=\varnothing.$

###### Proof.

Let $\mathbf{x}=(x_{1},x_{2},x_{3})$ and $\mathbf{y}=(y_{1},y_{2},y_{3})$.
Suppose first that the maximal indices of $\mathbf{x}$ and $\mathbf{y}$ are
distinct. Without loss of generality, say $\mathbf{x}$ has maximal index $i=1$
and $\mathbf{y}$ has maximal index $j=2$. We claim that there are elements
$\zeta,\gamma,z$ in $\mathbb{F}_{p}$ so that

$(x_{1},\zeta,z),(\gamma,y_{2},z)\in\mathbb{X}^{*}(p).$

Considering the Markoff equation as a quadratic in $\zeta$, for
$(x_{1},\zeta,z)$ to be in $\mathbb{X}^{*}(p)$ we must have

$(3x_{1}z)^{2}-4(x_{1}^{2}+z^{2})=\alpha^{2}$

for some $\alpha\in\mathbb{F}_{p}$. Similarly, considering the Markoff
equation as a quadratic in $\gamma$, for $(\gamma,y_{2},z)$ to be in
$\mathbb{X}^{*}(p)$ we must have

$(3y_{2}z)^{2}-4(y_{2}^{2}+z^{2})=\beta^{2}$

for some $\beta\in\mathbb{F}_{p}$. Rearranging, this gives the system of
equations

$(9x_{1}^{2}-4)z^{2}-\alpha^{2}=4x_{1}^{2}$
$(9y_{2}^{2}-4)z^{2}-\beta^{2}=4y_{2}^{2}$

with unknowns $z,\alpha,\beta$.

When $x_{1}^{2}\not=y_{2}^{2}$, this system of equations defines an
irreducible curve in $\mathbb{A}^{3}$, which has solutions modulo any prime.
If $x_{1}^{2}=y_{2}^{2}$ then this reduces to finding solutions $z,\alpha$ to

(3.1) $(9x_{1}^{2}-4)z^{2}-\alpha^{2}=4x_{1}^{2}.$

If $x_{1}$ is parabolic, then $9x_{1}^{2}-4\equiv 0(\text{mod}\,p)$. Since
we’ve assumed that $C_{1}(\mathbf{x})$ is nonempty, then by Lemma 3.2 we must
have $p\equiv 1(\text{mod}\,4)$ an so $-1$ is a square modulo $p$, which gives
a solution to equation (3.1). If $x_{1}$ is not parabolic, then equation (3.1)
is a conic section, which has a solution modulo any prime. Using an
inclusion/exclusion argument, the authors of [2] show that such a solution can
be found so that $z$ has maximal order. Hence, if we let
$\mathbf{z}=(x_{1},\zeta,z)$ then $\mathbf{z}\in\mathcal{C}(p)$ and
$C_{3}(\mathbf{z})$ intersects $C_{1}(\mathbf{x})$ and $C_{2}(\mathbf{y})$
nontrivially. Note that if $\mathbf{x}$ and $\mathbf{y}$ have the same maximal
index, then we can find points
$(x_{1},\zeta,z),(y_{1},\gamma,z)\in\mathbb{X}^{*}(p)$ by solving the Equation
(3.1) as above. This gives triple
$\mathbf{z}=(x_{1},\zeta,z)\in\mathbb{X}^{*}(p)$ with $z$ maximal and
$(y_{1},\gamma,z)\in C_{3}(\mathbf{z})$. ∎

###  3.2. Connecting points to the cage

The following two Propositions from [2] describe how to connect points of
large enough order to the cage. We give a brief outline of the proofs given in
[2], both to gather explicit information and to highlight the nonexplicit
steps in this construction which require we assume long path lengths in the
proof of Theorem 1.2. Note that these Propositions do not cover the case when
$\mathbf{x}=(x_{1},x_{2},x_{3})$ has maximal index $i$ and $x_{i}$ is
parabolic of order $p$. We will instead deal with this separately in
Proposition 3.3.

######  Proposition 3.4 (The Endgame from Section 4 of [2]).

Let $\mathbf{x}$ be in $\mathbb{X}^{*}(p)$ with
$\operatorname{ord}_{p}(\mathbf{x})>p^{1/2}$, and suppose that
$\mathbf{x}=(x_{1},x_{2},x_{3})$ has maximal index $i$ with $x_{i}$ not
parabolic. Then, there exists a positive integer $n$ and $i\in\\{1,2,3\\}$ so
that $\operatorname{rot}_{i}^{n}(\mathbf{x})$ is a maximal triple.

###### Proof.

Let $\mathbb{F}$ denote $\mathbb{F}_{p}$ when $x_{i}$ is hyperbolic and
$\mathbb{F}_{p^{2}}$ if $x_{i}$ is elliptic, under the identification
$\mathbb{F}_{p^{2}}\cong\mathbb{F}_{p}[T]/(T^{2}-\Delta_{x_{i}})$, as in the
proof of Lemma 2.8. Without loss of generality, let $i=1$. By Lemma 2.2 we can
write

$\operatorname{rot}_{1}^{n}(\mathbf{x})=(x_{1},C_{1}\varepsilon^{n}+C_{2}\bar{\varepsilon}^{n},C_{1}\varepsilon^{n+1}+C_{2}\bar{\varepsilon}^{n+1}),$

where $\varepsilon,\bar{\varepsilon}$ are roots of $f(T)=T^{2}-3x_{i}T+1$ and
$C_{1},C_{2}$ are constants in $\mathbb{F}$. The proof given in [2] uses the
Weil bound along with an inclusion/exclusion argument to show that there
exists a positive integer solution $n$ to

$C_{1}\varepsilon^{n}+C_{2}\bar{\varepsilon}^{n}=\rho+\rho^{-1}$

where $\rho$ is defined as follows: in the hyperbolic case, $\rho$ is any
generator of $\mathbb{F}_{p}^{\times}$, and in the elliptic case we take
$\rho=u^{p-1}$ where $u$ generates $\mathbb{F}_{p^{2}}^{\times}$. Then
$\operatorname{rot}_{i}^{n}(\mathbf{x})$ has second coordinate equal to
$\rho+\rho^{-1}$, and since $\rho,\rho^{-1}$ are the roots of

$f(T)=T^{2}-(\rho+\rho^{-1})T+1$

then by Lemma 2.8 $\operatorname{ord}_{p,2}(\mathbf{y})$ is equal to the order
of $\rho$, which is maximal by construction. ∎

######  Proposition 3.5 (The Middlegame from Section 4 of [2]).

Let $\mathbf{x}$ be in $\mathbb{X}^{*}(p)$ with
$c<\operatorname{ord}_{p}(\mathbf{x})\leq p^{1/2},$ where $c$ is a fixed
constant independent of $p$, which is described in [2]. Then, there exist
$i_{1},\dots,i_{t}\in\\{1,2,3\\}$ and positive integers $m_{1},\dots,m_{t}$ so
that the rotation order of

$\operatorname{rot}_{i_{t}}^{m_{t}}\cdots\operatorname{rot}_{i_{1}}^{m_{1}}(\mathbf{x})$

is larger than $p^{1/2}$, where $t\leq\tau(p^{2}-1)$.

###### Proof.

Since the rotation order of a parabolic triple is lower bounded by $p$, we
know that $\mathbf{x}$ is hyperbolic or elliptic. So, by Proposition 2.9, we
have $\operatorname{ord}_{p}(X)\mid p^{2}-1$. Suppose that $\mathbf{x}$ has
maximal index $i$ and let $M_{\mathbf{x},i}$ be the orbit of $\mathbf{x}$
under $\operatorname{rot}_{i}$, as defined in 2.6. Let
$\mathbf{y}=(y_{1},y_{2},y_{3})$ be in $M_{\mathbf{x},i}$ with maximal index
$j$. If $y_{j}$ is parabolic, then $\operatorname{ord}_{p}(\mathbf{y})\geq p$
and we’re done. Otherwise, $y_{j}$ is hyperbolic or elliptic, and so
$\operatorname{ord}_{p}(\mathbf{y})$ divides $p^{2}-1$ as well. If
$\operatorname{ord}_{p}(\mathbf{y})>\operatorname{ord}_{p}(\mathbf{x})$ then
$i\not=j$ and we repeat the process above by considering the orbit
$M_{\mathbf{y},j}$. If
$\operatorname{ord}_{p}(\mathbf{y})\leq\operatorname{ord}_{p}(\mathbf{x})$,
then we consider the sum

$N_{\mathbf{x}}:=\sum_{\ell\leq|M_{\mathbf{x},i}|}\\#\\{\mathbf{y}\in
M_{\mathbf{x},i}:|M_{\mathbf{y},j}|=\ell^{\prime}\\}.$

The authors of [2] use estimates on the gcd of elements of the form $u-1,v-1$
from Corvaja and Zannier in [7] to show that if $p^{2}-1$ does not have too
many prime divisors, then $N_{\mathbf{x}}<|M_{\mathbf{x},i}|$. So, by
definition of $N_{\mathbf{x}}$ there must be a point in the orbit of
$\mathbf{x}$ with larger rotation order, and we proceed as above. That is,
given our point $\mathbf{x}$, we can find $\mathbf{z}_{1}\in M_{\mathbf{x},i}$
with
$\operatorname{ord}_{p}(\mathbf{z}_{1})>\operatorname{ord}_{p}(\mathbf{z})$.
If $\mathbf{z}_{1}$ has maximal coordinate $z_{1}$ parabolic, then we’re done.
Otherwise, $\operatorname{ord}_{p}(\mathbf{y})\mid p^{2}-1$. Iterating in this
way, we obtain $\mathbf{z}_{1},\mathbf{z}_{2},\dots\in\mathbb{X}^{*}(p)$ with

$\operatorname{ord}_{p}(\mathbf{x})<\operatorname{ord}_{p}(\mathbf{z}_{1})<\operatorname{ord}_{p}(\mathbf{z}_{2})<\cdots$

and since $\operatorname{ord}_{p}(\mathbf{z}_{i})\mid(p^{2}-1)$ for every $i$,
this process will stop after at most $\tau(p^{2}-1)$ steps, where $\tau(n)$
denotes the number of positive divisors of an integer $n$. ∎

###  3.3. Connecting Parabolic Points to the Cage

Suppose $\mathbf{x}=(x_{1},x_{2},x_{3})$ is in $\mathbb{X}^{*}(p)$ with
$x_{i}$ parabolic. For convenience, suppose that $i=1$ and set $x=x_{1}$. From
Proposition 2.9 and Lemma 3.2, we know that $p\equiv 1(\text{mod}\,4)$ and if
$x=2/3$ then $C_{1}(x)$ consists of two disjoint orbits. Here, we describe the
conic section in terms of these orbits, and use this to show how to connect
parabolic points of order $p$ to any point in the cage.

The Jordan normal decomposition of $A_{2/3}$ is given by

$A_{2/3}=\begin{pmatrix}1&-1\\\ 1&0\end{pmatrix}\begin{pmatrix}1&1\\\
0&1\end{pmatrix}\begin{pmatrix}0&1\\\ -1&1\end{pmatrix}$

and so we get

$A_{2/3}^{n}=\begin{pmatrix}1&-1\\\ 1&0\end{pmatrix}\begin{pmatrix}1&n\\\
0&1\end{pmatrix}\begin{pmatrix}0&1\\\ -1&1\end{pmatrix}.$

Let

$\mathbf{x}^{(+)}=\left(\frac{2}{3},1,1+\frac{2}{3}i\right)\text{ and
}\mathbf{x}^{(-)}=\left(\frac{2}{3},1,1-\frac{2}{3}i\right)$

where $i$ is the square root of $-1$ modulo $p$, noting again that the
assumption of a parabolic point implies that $p\equiv 1(\text{mod}\,4)$. From
above we get

(3.2)
$M_{\mathbf{x}^{(+)}}=\left\\{\left(\frac{2}{3},1+\frac{2}{3}in,1+\frac{2}{3}i(n+1)\right)\mid
n\in\mathbb{Z}\right\\}$ (3.3)
$M_{\mathbf{x}^{(-)}}=\left\\{\left(\frac{2}{3},1-\frac{2}{3}in,1-\frac{2}{3}i(n+1)\right)\mid
n\in\mathbb{Z}\right\\}.$

Observe that these orbits are disjoint and each contain $p$ elements, so we
have

$C_{i}(\mathbf{x})=M_{\mathbf{x}^{(+)}}\cup M_{\mathbf{x}^{(-)}}.$

Now, let $\mathbf{y}=(y_{1},y_{2},y_{3})$ be any point in the cage with
maximal index $j\in\\{2,3\\}$ with and $y_{j}\not=0$. Since
$M_{\mathbf{x}^{(+)}}$ contains $p-1$ points with distinct $j$th coordinates
and $y_{j}\in\mathbb{F}_{p}^{\times}$ then we must have $C_{j}(y)\cap
M_{\mathbf{x}^{(+)}}\not=\varnothing$ and similarly we have $C_{j}(y)\cap
M_{\mathbf{x}^{(-)}}\not=\varnothing$. Hence, we can connect $\mathbf{x}$ to
the cage by $\operatorname{rot}_{1}$.

###  3.4. Points of small order

The authors of [2] show that points $\mathbf{x}$ with order bounded from above
by a constant not depending on $p$ are connected to the cage. This proof is
nonconstructive, and so we do not include such points in Theorem 1.2. We refer
the reader to Section 5 of [2] on “The Opening” for this analysis.

###  3.5. Connecting $(1,1,1)$ to the cage

In the tables below, we demonstrate that $\operatorname{rot}_{1}^{n}(1,1,1)$
is in the cage for all primes $p\leq 199$ where $0\leq n\leq 5$. If we can
show that $(1,1,1)$ is always “close” to the cage, or find a large family of
primes where this holds, we could then relax the conditions of Theorem 1.2.
One direction to do this might be to note the following connection to the
Fibonacci sequence. Observe that the Lucas sequence $u_{n}$ defined in Lemma
2.12 when $\mathbf{x}=(1,1,1)$ is equal to $f_{2n}$. This gives

$A_{1}^{n}=\begin{pmatrix}-f_{2n-2}&f_{2n}\\\ -f_{2n}&f_{2n+2}\end{pmatrix}$

and so

$\displaystyle\operatorname{rot}_{1}^{n}(1,1,1)$
$\displaystyle=(1,f_{2n}-f_{2n-2},f_{2n+2}-f_{2n})$
$\displaystyle=(1,f_{2n-1},f_{2n+1}).$

So, one approach would be to investigate the orders of $A_{x}$ where $x$ is an
odd term in the Fibonacci sequence.

Prime |  Path | Points
---|---|---
2 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,0)$
3 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
5 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
7 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
11 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
13 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
17 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
19 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
23 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
29 | $\operatorname{rot}_{1}^{2}$ |  $(1,1,1)$, $(1,1,2)$, $(1,2,5)$
31 | $\operatorname{rot}_{1}^{2}$ |  $(1,1,1)$, $(1,1,2)$, $(1,2,5)$
37 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
41 | $\operatorname{rot}_{1}^{2}$ |  $(1,1,1)$, $(1,1,2)$, $(1,2,5)$
43 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
47 | $\operatorname{rot}_{1}^{3}$ |  $(1,1,1)$, $(1,1,2)$, $(1,2,5)$, $(1,5,13)$
53 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
59 | $\operatorname{rot}_{1}^{5}$ |  $(1,1,1)$, $(1,1,2)$, $(1,2,5)$, $(1,5,13)$, $(1,13,34)$, $(1,34,30)$
61 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
67 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
71 | $\operatorname{rot}_{1}^{2}$ |  $(1,1,1)$, $(1,1,2)$, $(1,2,5)$
Table 1. Paths from $(1,1,1)$ to $\mathcal{C}(p)$ Prime |  Path | Points
---|---|---
73 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
79 | $\operatorname{rot}_{1}^{2}$ |  $(1,1,1)$, $(1,1,2)$, $(1,2,5)$
83 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
89 | $\operatorname{rot}_{1}^{3}$ |  $(1,1,1)$, $(1,1,2)$, $(1,2,5)$, $(1,5,13)$
97 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
101 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
103 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
107 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
109 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
113 | $\operatorname{rot}_{1}^{5}$ |  $(1,1,1)$, $(1,1,2)$, $(1,2,5)$, $(1,5,13)$, $(1,13,34)$, $(1,34,89)$
127 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
131 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
137 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
139 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
149 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
151 | $\operatorname{rot}_{1}^{3}$ |  $(1,1,1)$, $(1,1,2)$, $(1,2,5)$, $(1,5,13)$
157 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
163 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
167 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
173 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
179 | $\operatorname{rot}_{1}^{3}$ |  $(1,1,1)$, $(1,1,2)$, $(1,2,5)$, $(1,5,13)$
181 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
191 | $\operatorname{rot}_{1}^{3}$ |  $(1,1,1)$, $(1,1,2)$, $(1,2,5)$, $(1,5,13)$
193 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
197 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
199 | $\operatorname{rot}_{1}^{1}$ |  $(1,1,1)$, $(1,1,2)$
Table 2. Paths from $(1,1,1)$ to $\mathcal{C}(p)$ continued

###  3.6. Path Construction

We are now prepared to give an explicit description of the path from $(1,1,1)$
to points $\mathbf{x}\in\mathcal{G}_{p}$ constructed in the BGS algorithm.

######  Algorithm 3.6.

Let $p$ be prime and let $\mathbf{x}\in\mathbb{X}^{*}(p)$ with
$\operatorname{ord}_{p}(X)>c$, where $c$ is defined in the Middlegame of [2].
Then, we can connect $(1,1,1)$ to $X$ in $\mathcal{G}_{p}$ as follows.

  1. I.

We assume that $\operatorname{rot}_{1}^{n}(1,1,1)$ is connected to the cage
for $0\leq n\leq 5$, which appears numerically to hold for many primes $p$ as
discussed in Section 3.5.

  2. II.

If $\mathbf{x}\in\mathcal{C}(p)$ then we can connect $\mathbf{y}$ to
$\mathbf{x}$ as follows. Suppose that $\mathbf{x}$ has maximal index $i_{1}$
and $\mathbf{y}$ has maximal index $i_{2}$. By Lemma 3.3 there exists a point
$\mathbf{z}\in\mathcal{C}(p)$ with maximal index $i_{1}\in\\{1,2,3\\}$ so that

$C_{i_{3}}(\mathbf{x})\cap C_{i_{2}}(\mathbf{z})\not=\varnothing\text{ and
}C_{i_{1}}(\mathbf{y})\cap C_{i_{2}}(\mathbf{z})\not=\varnothing.$

Furthermore, by Proposition 3.1 we have that

$C_{i_{3}}(\mathbf{x})=M_{i_{3}}(\mathbf{x}),C_{i_{2}}(\mathbf{z})=M_{i_{2}}(\mathbf{z})\text{
and }C_{i_{1}}(\mathbf{y})=M_{i_{1}}(\mathbf{y}).$

So, the orbit of $\mathbf{z}$ under $\operatorname{rot}_{i_{2}}$ intersects
the orbits of $\mathbf{x}$ under $\operatorname{rot}_{i_{3}}$ and the orbit of
$\mathbf{y}$ under $\operatorname{rot}_{i_{1}}$. That is, there are points
$\mathbf{z}_{x},\mathbf{z}_{y}\in\mathcal{C}(p)$ with

$\mathbf{x}=\operatorname{rot}_{i_{3}}^{n_{3}}(\mathbf{z}_{x})\text{ and
}\mathbf{z}_{y}=\operatorname{rot}_{i_{1}}^{n_{1}}(\mathbf{y})$

for integers $n_{1},n_{3}$. As in Figure 3, this gives the following path from
$(1,1,1)$ to our point $\mathbf{x}\in\mathcal{C}(p)$

$\mathbf{x}=\operatorname{rot}_{i_{3}}^{n_{3}}\operatorname{rot}_{i_{2}}^{n_{2}}\operatorname{rot}_{i_{1}}^{n_{1}}\operatorname{rot}_{j}^{n}(1,1,1).$

$\mathbf{x}$$\operatorname{rot}_{i_{3}}$$\operatorname{rot}_{i_{1}}$$\operatorname{rot}_{i_{2}}$$\mathbf{y}$$\operatorname{rot}_{i_{3}}$$\operatorname{rot}_{i_{1}}$$\operatorname{rot}_{i_{2}}$$\mathbf{z}$$\mathbf{z}_{x}$$\mathbf{z}_{y}$$\operatorname{rot}_{i_{2}}$$(1,1,1)$$\operatorname{rot}_{j}$
Figure 3. Existence of $\mathbf{z}$ intersecting the orbits of $\mathbf{x}$
and $\mathbf{y}$

  3. III.

If $\operatorname{ord}_{p}(\mathbf{x})>p^{1/2}$ then by Proposition 3.4 there
exists a point $\mathbf{x}_{C}$ so that $\mathbf{x}_{C}$ is in the orbit of
$\mathbf{x}$ under the rotation $\operatorname{rot}_{i_{4}}$ for some
$i_{4}\in\\{1,2,3\\}$. This implies that $\mathbf{x}$ is also in the orbit of
$\mathbf{x}_{C}$ under the rotation $\operatorname{rot}_{i_{4}}$ and so we can
write

$\mathbf{x}=\operatorname{rot}_{i_{4}}^{n_{4}}(\mathbf{x}_{C}).$

Then, we can connect $(1,1,1)$ to $\mathbf{x}_{C}$ as in Step II to get

$\mathbf{x}=\operatorname{rot}_{i_{4}}^{n_{4}}\cdots\operatorname{rot}_{i_{1}}^{n_{1}}\operatorname{rot}_{j}^{n}(1,1,1).$

  4. IV.

If $c<\operatorname{ord}_{p}(\mathbf{x})\leq p^{1/2}$ then by Proposition 3.5
there exists a point $\mathbf{x}_{M}$ with
$\operatorname{ord}_{p}(\mathbf{x}_{M})>p^{1/2}$ where

$\mathbf{x}_{M}=\operatorname{rot}_{i_{5}}^{m_{5}}\cdots\operatorname{rot}_{i_{t+4}}^{m_{t+4}}\mathbf{x},$

and $t<\tau(p^{2}-1)$. Note that if
$\mathbf{x}_{i}=\operatorname{rot}_{i}^{m}\mathbf{x}_{j}$ then this means that
$\mathbf{x}_{i}$ is in the orbit of $\mathbf{x}_{j}$ under
$\operatorname{rot}_{i}$. So as discussed in Step III, $\mathbf{x}_{j}$ is
also in the orbit of $\mathbf{x}_{i}$ and we can write
$\mathbf{x}_{j}=\operatorname{rot}_{i}^{n}\mathbf{x}_{i}$ for some integer
$n$. Repeating this process gives us the following path from $\mathbf{x}_{M}$
to $\mathbf{x}$

$\mathbf{x}=\operatorname{rot}_{i_{t+4}}^{n_{t+4}}\cdots\operatorname{rot}_{i_{5}}^{n_{5}}\mathbf{x}_{M}.$

Since $\operatorname{rot}_{p}(\mathbf{x}_{M})>p^{1/2}$ then we can connect
$(1,1,1)$ to $\mathbf{x}_{M}$ as in Step III to get
$\mathbf{x}=\operatorname{rot}_{i_{t+4}}^{n_{t+4}}\cdots\operatorname{rot}_{i_{1}}^{n_{1}}\operatorname{rot}_{j}^{n}(1,1,1).$

##  4\. Proof of Theorem 1.2

We are now prepared to prove our first main result.

###### Proof of Theorem 1.2.

Take $\mathbf{x}\in\mathbb{X}^{*}(p)$. If
$\operatorname{ord}_{p}(\mathbf{x})>p^{1/2}$ given our assumptions and by Step
III of Algorithm 3.6 we can write

$\mathbf{x}=\operatorname{rot}_{i_{4}}^{n_{4}}\cdots\operatorname{rot}_{i_{1}}^{n_{1}}\operatorname{rot}_{1}^{n}(1,1,1).$

where $n_{i}\geq 0$, $0\leq n\leq 5$ and the $i_{j}$ are not necessarily
distinct. So, by Proposition 2.3 we have

$\operatorname{size}(\mathbf{x})<(3\varepsilon)^{2^{4}(n+1)(n_{1}+1)(n_{2}+1)(n_{3}+1)(n_{4}+1)},$

where $\varepsilon=(3+\sqrt{5})/2$. Note that the $n_{i}$ correspond to path
lengths from steps of the BGS algorithm. Since the proofs given in [2] are
nonconstructive, we upper bound each $n_{i}$ by the corresponding rotation
order. By assumption we have $n\geq 5$ and by Lemma 2.9 we have $n_{i}\leq 2p$
for each $i\in\\{1,2,3,4\\}$, and so the result follows. ∎

Observe that, using Step IV of Algorithm 3.6 and Proposition 2.3, we can
obtain the following upper bound for minimal lifts of points
$\mathbf{x}\in\mathbb{X}^{*}(p)$ in the middlegame.

######  Proposition 4.1.

Let $p$ be a prime so that
$\operatorname{ord}_{p}(\operatorname{rot}_{1}^{n}(1,1,1))>p$ for $0\leq n\leq
5$ and suppose that $\mathbf{x}\in\mathbb{X}^{*}(p)$ with
$\operatorname{ord}_{p}(\mathbf{x})>c$, where $c$ is the absolute constant
introduced in the Middlegame of [2]. Let $\tilde{\mathbf{x}}$ be a lift of
$\mathbf{x}$ of minimal size. Then,

$\operatorname{size}(\tilde{\mathbf{x}})<(3\varepsilon)^{96(2p+1)^{4+t/2}},$

where $t=\tau(p^{2}-1)$ denotes the number of positive divisors of $p^{2}-1$.

The proof of Proposition 4.1 follows identically to the proof of Theorem 1.2
above, where we additionally note that in the Middlegame our points have order
upper bounded by $p^{1/2}$. A natural next step would be to explicitly compute
the absolute constant $c$ references in [2] in order to extend Theorem 1.2 to
a larger family of points in $\mathbb{X}^{*}(p)$

###  4.1. Percentage of points in the cage

In Figure 4, the percentage of total points in $\mathbb{X}^{*}(p)$ which
satisfy the conditions of Theorem 1.2 is plotted for primes $p<300$. Observe
that this percentage appears to hover around 80%. Note here that this
percentage also includes parabolic points of order $p$, since they are a
similar distance from $(1,1,1)$ as points in the cage.

Figure 4. Percentage of points from $\mathbb{X}^{*}(p)$ in $\mathcal{C}(p)$

As shown in the proof of Proposition 2.9, note that a triple $\mathbf{x}$ is
in the cage $\mathcal{C}(p)$ if and only if one of its coordinates $x$
satisfies any of the following

  1. (1)

$x=-2/3$ if $x$ is parabolic.

  2. (2)

$\varepsilon_{x}$ generates $\mathbb{F}_{p}^{\times}$ if $x$ is hyperbolic, or

  3. (3)

$\varepsilon_{x}=\rho_{x}^{p-1}$ where $\rho_{x}$ generates
$\mathbb{F}_{p^{2}}^{\times}$ if $x$ is elliptic.

Suppose that $x$ is a randomly chosen element in $\mathbb{F}_{p}$. If we
assume the $\varepsilon_{x}$ are equally likely to take the form in (2) or (3)
as a randomly chosen element of $\mathbb{F}^{\times}$ and that generators are
equally distributed in $\mathbb{F}^{\times}$, then the probability that $x$
satisfies conditions (1), (2) or (3) is given by

$\frac{1}{p}+\frac{\varphi(p-1)}{p-1}+\frac{\varphi(p^{2}-1)}{(p-1)(p^{2}-1)}.$

Since the probability that a Markoff $\text{mod}\,p$ point
$\mathbf{x}=(x_{1},x_{2},x_{3})$ is in the cage is lower bounded by the
probability that $x=x_{1}$ satisfies one of $(1)$, $(2)$ or $(3)$, an
interesting future direction would be to use the argument above to derive a
heuristic lower bound on the percentage of points in the cage for primes $p$
where $\varphi(p-1)/p$ has a known asymptotic formula.

##  5\. Shortest Paths and Proof of Theorem 1.3

In Proposition 2.3 we saw that the size of our lift grows much faster when the
corresponding path contains many switches between different rotations. By
following the BGS algorithm we were able to make a small number of these
switches, but had to compromise by assuming long paths as we traveled along
the orbit of a single rotation due to the non explicit methods used in [2]. In
this section, we study lifts obtained from paths of shortest possible length
with possibly many switches between rotations. The bound in Theorem 1.3 are
uniform if the following conjecture holds, which is expected to be true (see
[8], for example).

######  Conjecture 5.1 (Super Strong Approximation).

For any prime $p$, the collection of Markoff mod $p$ graphs
$(\mathcal{G}_{p})_{p}$ forms an expander family.

An expander family is a collection of graphs $(G_{i})_{i}$ that is “highly
connected but relatively sparse”. We refer to [11] for the formal definition.
To obtain a uniform bound, we will only need to know that the expansion
constant of any expander family is bounded. As a Corollary to the following
Proposition, we obtain a bound on the diameter of any Markoff $\text{mod}\,p$
graph.

######  Proposition 5.2 (Proposition 3.1.5 of [11]).

Let $G$ be any finite non-empty connected graph. We have

$\operatorname{diam}(G)\leq
2\frac{\log\frac{|G|}{2}}{\log\left(1+\frac{h(G)}{v}\right)}+3,$

where $v$ is the maximum number of edges at each vertex and $h(G)$ is the
expansion constant of $G$.

Note that $|\mathbb{X}^{*}(p)|=p^{2}\pm 3n$, depending on whether $p\equiv
1(\text{mod}\,4)$. Since the $v=3$ in $\mathcal{G}_{p}$ for any prime $p$ we
have the following Corollary.

######  Corollary 5.3.

If Conjecture 5.1 holds, then

$\operatorname{diam}(\mathcal{G}_{p})\leq
C\log\left(\frac{p^{2}+3}{2}\right).$

where $\mathcal{G}_{p}$ is the Markoff $\text{mod}\,p$ graph and $C$ is a
constant given by

$C=\frac{5}{\log\left(1+\frac{h}{3}\right)},$

where $h$ is an upper bound for the expansion constant of $(G_{p})_{p}$.

We our now prepared to prove our second main result.

###### Proof of Theorem 1.3.

Let $\mathbf{x}\in\mathbb{X}^{*}(p)$ and suppose that the shortest path from
$(1,1,1)$ to $\mathbf{x}$ in $\mathcal{G}_{p}$ has length $\ell$. Then
$\mathbf{x}$ is of the form

$\mathbf{x}=\operatorname{rot}_{i_{s}}^{n_{s}}\cdots\operatorname{rot}_{i_{1}}^{n_{1}}(1,1,1),$

where $1\leq s\leq\ell$ and $n_{1}+\cdots+n_{s}=\ell$. So by Proposition 2.3,
if $\tilde{\mathbf{x}}$ is a lift of minimal size of $\mathbf{x}$ we have
$\operatorname{size}(\tilde{\mathbf{x}})<(3\varepsilon)^{\alpha}$ where

$\displaystyle\alpha$ $\displaystyle=2^{s-1}(n_{1}+1)\cdots(n_{s}+1)$
$\displaystyle<2^{s-1}5^{\ell}$ $\displaystyle<2^{4\ell}$

where the second to last inequality follows from Lemma 5.4 below. By Corollary
5.3 we have

$\alpha<2^{4C\log((p^{3}+3)/2)}<\left(\frac{p^{3}+3}{2}\right)^{4C},$

where

$C=\frac{5}{\log(1+\frac{h}{3})}$

as in Lemma 5.4. ∎

######  Lemma 5.4.

For any positive integer $\ell$ we have

$\max\\{(n_{1}+1)\cdots(n_{s}+1)\mid(n_{1},\dots,n_{s})\text{ partitions
}\ell\text{ and }1\leq s\leq n\\}\leq 5^{\ell}.$

###### Proof.

Suppose that $(n_{1},\dots,n_{s})$ partition $\ell$, and that one of our parts
is larger than 4, say $n_{1}>4$. Then $n_{1}<3(n_{1}-3)$ and we get

$(n_{1}+1)(n_{2}+1)\cdots(n_{s}+1)<(3(n_{1}-3)+1)(n_{2}+1)\cdots(n_{s}+1).$

Since $(3,n_{1}-3,n_{2},\dots,n_{s})$ is also a partition $\ell$ then
$(n_{1}+1)\cdots(n_{\ell}+1)$ is not maximal. So, any partition
$(n_{1},\dots,n_{s})$ maximizing $(m_{1}+1)\cdots(n_{s}+1)$ must have
$n_{i}\leq 4$ for every $i=1,\dots,s$. ∎

###  5.1. Data to support improvements on average

Note that the bound in Theorem 1.3 assumed our shortest path from $\mathbf{x}$
in $\mathcal{G}_{p}$ to $(1,1,1)$ switches between distinct rotations
maximally. By Proposition 2.3, this contributes doubly exponentially to the
growth of the corresponding lift. From numerical experimentation, we expect
that this bound can be improved if we consider lifts on average.

The histogram in Figure 5 plots the frequency of the logarithmic size of
Markoff triples of fixed length $\ell=14$ from $(1,1,1)$ in the Markoff tree
defined by the rotations $\operatorname{rot}_{i}$; that is, the tree with root
node $(1,1,1)$ and edges defined by
$\\{\operatorname{rot}_{1},\operatorname{rot}_{2},\operatorname{rot}_{3}\\}$.

Figure 5. Distribution of logarithmic sizes at level 14

This data suggests that sizes are distributed in such a way that favor smaller
lifts, and so we expect that the largest sizes used in our upper bound occur
infrequently enough to allow for improvement to this bound on average. An
interesting future direction would be an explicit calculation of this
distribution in order to obtain an improved upper bound on the size of lifts
on average using the methods in Theorem 1.3.

##  6\. Short Paths Along Parabolic Orbits

Suppose $\mathbf{x}=(x_{1},x_{2},x_{3})$ is in $\mathbb{X}^{*}(p)$ with
$x_{i}$ parabolic. For convenience, suppose that $i=1$ and set $x=x_{1}$. In
Section 3.3 we showed that when $p\equiv 1(\text{mod}\,4)$ and $x=2/3$ the
conic section consists of the disjoint orbits

$C_{i}(\mathbf{x})=M_{\mathbf{x}^{(+)}}\cup M_{\mathbf{x}^{(-)}}$

where $M_{\mathbf{x}^{(+)}}$ and $M_{\mathbf{x}^{(-)}}$ are defined in
Equations (3.2) and (3.3). By Proposition 2.9 and Lemma 3.2, when $x=-2/3$ we
have $C_{i}(\mathbf{x})=M_{\mathbf{x},i}$ and using a similar analysis to that
in Section 3.3 we get

$M_{\mathbf{x},i}=\left\\{\left(\frac{-2}{3},-1\pm\frac{2}{3}in,1\mp\frac{2}{3}i(n+1)\right)\right\\}.$

Now, let $p$ be a prime so that there exists a point
$\mathbf{y}=(y_{1},y_{2},y_{3})$ in the cage with

$\operatorname{rot}_{1}^{n}(1,1,1)=\mathbf{y}$

for $0\leq n\leq 5$. If it’s the case that the maximal index of $\mathbf{y}$
is not equal to one, then we can connect any parabolic point directly to
$\mathbf{y}$ as discussed in Section 3.3 by a path of the form

$\mathbf{x}=\operatorname{rot}_{i}^{n_{i}}\operatorname{rot}_{j}^{n_{j}}\operatorname{rot}_{1}^{n}(1,1,1).$

As in the proof of Theorem 1.2 we can take $n_{i},n_{j}$ smaller than the
largest rotation order, using Proposition 2.3 gives the following.

######  Proposition 6.1.

Let $\mathbf{x}\in\mathbb{X}^{*}(p)$ be of the form $\mathbf{x}=(\pm
2/3,x_{2},x_{3})$. Suppose that the point $\mathbf{y}$ above has maximal index
$i\in\\{2,3\\}$ and let $\tilde{\mathbf{x}}$ be a lift of $\mathbf{x}$ of
minimal size. Then

$\operatorname{size}(\tilde{x})\leq(3\varepsilon)^{20(2p+1)^{2}}.$

Since parabolic points have large orbits, it’s expected that many points are
“close” to parabolic orbits. Because the bound in Proposition 6.1 is better
than our previously obtained bounds, a natural next direction would be to
investigate points that have short paths to nearby parabolic orbits.

## References

  * [1] Martin Aigner.  Markov’s theorem and 100 years of the uniqueness conjecture.  Springer, Cham, 2013.  A mathematical journey from irrational numbers to perfect matchings.
  * [2] Jean Bourgain, Alexander Gamburd, and Peter Sarnak.  Markoff triples and strong approximation.  Comptes Rendus Mathematique, 354(2):131–135, 2016.
  * [3] John William Scott Cassels.  An introduction to the geometry of numbers.  Springer Science & Business Media, 2012.
  * [4] Denis X. Charles, Kristin E. Lauter, and Eyal Z. Goren.  Cryptographic hash functions from expander graphs.  J. Cryptology, 22(1):93–113, 2009.
  * [5] William Chen.  Strong approximation for the markoff equation.  arXiv: Number Theory, 2020.
  * [6] Harvey Cohn.  Markoff forms and primitive words.  Math. Ann., 196:8–22, 1972.
  * [7] Pietro Corvaja and Umberto Zannier.  Greatest common divisors of $u-1,\ v-1$ in positive characteristic and rational points on curves over finite fields.  J. Eur. Math. Soc. (JEMS), 15(5):1927–1942, 2013.
  * [8] Matthew De Courcy-Ireland and Seungjae Lee.  Experiments with the Markoff surface.  arXiv preprint arXiv: 1812.07275v1, 2018.
  * [9] Elena Fuchs, Kristin Lauter, and Austin Tran.  A cryptographic hash function from Markoff triples.  arXiv preprint arXiv:2107.10906, 2021.
  * [10] Friedrich Hirzebruch and Don Zagier.  The Atiyah-Singer theorem and elementary number theory.  Mathematics Lecture Series, No. 3. Publish or Perish, Inc., Boston, Mass., 1974.
  * [11] Emmanuel Kowalski.  An introduction to expander graphs, volume 26 of Cours Spécialisés [Specialized Courses].  Société Mathématique de France, Paris, 2019.
  * [12] Andrey Markoff.  Sur les formes quadratiques binaires indéfinies.  Math. Ann., 17(3):379–399, 1880.
  * [13] Don Zagier.  On the number of Markoff numbers below a given bound.  Math. Comp., 39(160):709–723, 1982.


$\cdot;u_{f}:\mathcal{U}_{f},u_{t}:\mathcal{U}_{t};\cdot\vdash\tau_{1}::\mathsf{Ty}$
and
$\cdot;u_{f}:\mathcal{U}_{f},u_{t}:\mathcal{U}_{t};\cdot\vdash\tau_{2}::\mathsf{Ty}$
and $\cdot;\cdot;\cdot\vdash
G:\Pi[u_{f}\\!:\\!\mathcal{U}_{f};u_{t}\\!:\\!\mathcal{U}_{t}].*$. Therefore
$\tau_{1}$, $\tau_{2}$, and $G$ contain no instances of $u$ or $\alpha$, so we
have $\sigma[\mu\alpha.\sigma^{\prime}/\alpha]=\tau[U^{\prime}/u][\lambda
u^{\prime}\\!:\\!\nu t.\mathcal{U}.\mu(\alpha;u\\!:\\!\nu
t.\mathcal{U}.\tau^{\prime};u^{\prime})/\alpha]=\Pi[u_{t}\\!:\\!\mathcal{U}_{t};u_{f}\\!:\\!\mathcal{U}_{f}].\tau_{1}\xrightarrow{G}\tau_{2}$.
Apply F:Fun. By K:Fun and CE:Reflexive and weakening,
$\cdot;\Psi;\Upsilon\vdash\Pi[u_{t}\\!:\\!\mathcal{U}_{t};u_{f}\\!:\\!\mathcal{U}_{f}].\tau_{1}\xrightarrow{G}\tau_{2}\equiv\Pi[u_{t}\\!:\\!\mathcal{U}_{t};u_{f}\\!:\\!\mathcal{U}_{f}].\tau_{1}\xrightarrow{G}\tau_{2}::\mathsf{Ty}$
for all $\Psi$.

  * •

F:Prod. Then $\sigma=\sigma_{1}\times\sigma_{2}$ and
$\tau=\tau_{1}\times\tau_{2}$ and
$\mathcal{U}^{\prime}=\mathcal{U}_{1}^{\blacksquare}\times\mathcal{U}_{2}^{\blacksquare}$
and $\Upsilon,\alpha::\nu
t.\mathcal{U}\rightarrow\mathsf{Ty}\vdash_{\mathsf{fst}~{}U}\sigma_{1}\leadsto\tau_{1};\mathcal{U}_{1}$
and $\Upsilon,\alpha::\nu
t.\mathcal{U}\rightarrow\mathsf{Ty}\vdash_{\mathsf{snd}~{}U}\sigma_{2}\leadsto\tau_{2};\mathcal{U}_{2}$.
By inversion on KU:Prod,
$\mathsf{Unann}(\Upsilon),\alpha::\mathsf{Ty}\vdash\sigma_{1}::\mathsf{Ty}$
and
$\mathsf{Unann}(\Upsilon),\alpha::\mathsf{Ty}\vdash\sigma_{2}::\mathsf{Ty}$.
By induction,
$\Upsilon\vdash_{\mathsf{fst}~{}U[U^{\prime}/u]}\sigma_{1}[\mu\alpha.\sigma^{\prime}/\alpha]\leadsto\tau_{1}^{\prime\prime};\mathcal{U}_{1}$
and
$\Upsilon\vdash_{\mathsf{snd}~{}U[U^{\prime}/u]}\sigma_{2}[\mu\alpha.\sigma^{\prime}/\alpha]\leadsto\tau_{2}^{\prime\prime};\mathcal{U}_{2}$,
and for any $\Psi_{1}$ such that
$\cdot;\Psi_{1}\vdash\mathsf{fst}~{}U[U^{\prime}/u]:\mathcal{U}_{1}$ and
$\cdot;\Psi_{1},u:\nu t.\mathcal{U};\Upsilon,\alpha::\nu
t.\mathcal{U}\rightarrow\mathsf{Ty}\vdash\tau^{\prime}::\mathsf{Ty}$,
$\cdot;\Psi_{1};\Upsilon\vdash\tau_{1}^{\prime\prime}\equiv\tau_{1}[U^{\prime}/u][\lambda
u^{\prime}\\!:\\!\nu t.\mathcal{U}.\mu(\alpha;u\\!:\\!\nu
t.\mathcal{U}.\tau^{\prime};u^{\prime})/\alpha]::\mathsf{Ty}$, and for any
$\Psi_{2}$ such that
$\cdot;\Psi_{2}\vdash\mathsf{snd}~{}U[U^{\prime}/u]:\mathcal{U}_{2}$ and
$\cdot;\Psi_{2},u:\nu t.\mathcal{U};\Upsilon,\alpha::\nu
t.\mathcal{U}\rightarrow\mathsf{Ty}\vdash\tau^{\prime}::\mathsf{Ty}$,
$\cdot;\Psi_{1};\Upsilon\vdash\tau_{2}^{\prime\prime}\equiv\tau_{2}[U^{\prime}/u][\lambda
u^{\prime}\\!:\\!\nu t.\mathcal{U}.\mu(\alpha;u\\!:\\!\nu
t.\mathcal{U}.\tau^{\prime};u^{\prime})/\alpha]::\mathsf{Ty}$. By F:Prod,
$\Upsilon\vdash_{U[U^{\prime}/u]}\sigma[\mu\alpha.\sigma^{\prime}/\alpha]\leadsto\tau_{1}^{\prime\prime}\times\tau_{2}^{\prime\prime};\mathcal{U}^{\prime}$.
By U:Fst and U:Snd,
$\cdot;\Psi\vdash\mathsf{fst}~{}U[U^{\prime}/u]:\mathcal{U}_{1}$ and
$\cdot;\Psi\vdash\mathsf{snd}~{}U[U^{\prime}/u]:\mathcal{U}_{2}$ for all
$\Psi$ such that $\cdot;\Psi\vdash U[U^{\prime}/u]:\mathcal{U}^{\prime}$ and
$\cdot;\Psi,u:\nu t.\mathcal{U};\Upsilon,\alpha::\nu
t.\mathcal{U}\rightarrow\mathsf{Ty}\vdash\tau^{\prime}::\mathsf{Ty}$. Apply
CE:Prod.

  * •

F:Sum. By symmetry with the previous case.

  * •

F:Fut. Then $\sigma=\sigma_{0}~{}\mathsf{future}$ and
$\tau=\tau_{0}~{}\mathsf{future}[\mathsf{snd}~{}U]$ and
$\mathcal{U}^{\prime}=\mathcal{U}_{0}^{\blacksquare}\times\blacklozenge^{\blacksquare}$
and $\Upsilon,\alpha::\nu
t.\mathcal{U}\rightarrow\mathsf{Ty}\vdash_{\mathsf{fst}~{}U}\sigma_{0}\leadsto\tau_{0};\mathcal{U}_{0}$.
By inversion on KU:Fut,
$\mathsf{Unann}(\Upsilon),\alpha::\mathsf{Ty}\vdash\sigma_{0}::\mathsf{Ty}$.
By induction,
$\Upsilon\vdash_{\mathsf{fst}~{}U[U^{\prime}/u]}\sigma_{0}[\mu\alpha.\sigma^{\prime}/\alpha]\leadsto\tau_{0}^{\prime\prime};\mathcal{U}_{0}$,
and for any $\Psi_{0}$ such that
$\cdot;\Psi_{0}\vdash\mathsf{fst}~{}U[U^{\prime}/u]:\mathcal{U}_{0}$ and
$\cdot;\Psi_{0},u:\nu t.\mathcal{U};\Upsilon,\alpha::\nu
t.\mathcal{U}\rightarrow\mathsf{Ty}\vdash\tau^{\prime}::\mathsf{Ty}$,
$\cdot;\Psi_{0};\Upsilon\vdash\tau_{0}^{\prime\prime}\equiv\tau_{0}[U^{\prime}/u][\lambda
u^{\prime}\\!:\\!\nu t.\mathcal{U}.\mu(\alpha;u\\!:\\!\nu
t.\mathcal{U}.\tau^{\prime};u^{\prime})/\alpha]::\mathsf{Ty}$. By F:Fut,
$\Upsilon\vdash_{U[U^{\prime}/u]}\sigma[\mu\alpha.\sigma^{\prime}/\alpha]\leadsto\tau_{0}^{\prime\prime}~{}\mathsf{future}[\mathsf{snd}~{}U[U^{\prime}/u]];\mathcal{U}^{\prime}$.
By U:Fst and U:Snd,
$\cdot;\Psi\vdash\mathsf{fst}~{}U[U^{\prime}/u]:\mathcal{U}_{0}$ and
$\cdot;\Psi\vdash\mathsf{snd}~{}U[U^{\prime}/u]:\blacklozenge$ for all $\Psi$
such that $\cdot;\Psi\vdash U[U^{\prime}/u]:\mathcal{U}^{\prime}$ and
$\cdot;\Psi,u:\nu t.\mathcal{U};\Upsilon,\alpha::\nu
t.\mathcal{U}\rightarrow\mathsf{Ty}\vdash\tau^{\prime}::\mathsf{Ty}$. Apply
UE:Reflexive and CE:Fut.

  * •

F:Rec. Then $\sigma=\mu\alpha^{\prime}.\sigma_{0}$ and
$\tau=\mu(\alpha^{\prime};u_{0}:\mathcal{U}^{\prime}.\tau_{0};U)$ and
$\mathcal{U}^{\prime}=\nu t^{\prime}.\mathcal{U}_{0}$ and
$\Upsilon,\alpha^{\prime}::\mathcal{U}^{\prime}\rightarrow\mathsf{Ty},\alpha::\nu
t.\mathcal{U}\rightarrow\mathsf{Ty}\vdash_{u_{0}}\sigma_{0}\leadsto\tau_{0};\mathcal{U}_{0}[\mathcal{U}^{\prime}/t^{\prime}]$.
By inversion on KU:Rec,
$\mathsf{Unann}(\Upsilon),\alpha^{\prime}::\mathsf{Ty},\alpha::\mathsf{Ty}\vdash\sigma_{0}::\mathsf{Ty}$.
By induction,
$\Upsilon,\alpha^{\prime}::\mathcal{U}^{\prime}\rightarrow\mathsf{Ty}\vdash_{u_{0}}\sigma_{0}[\mu\alpha.\sigma^{\prime}/\alpha]\leadsto\tau_{0}^{\prime\prime};\mathcal{U}_{0}[\mathcal{U}^{\prime}/t^{\prime}]$,
and for any $\Psi_{0}$ such that $\cdot;\Psi_{0}\vdash
u_{0}:\mathcal{U}_{0}[\mathcal{U}^{\prime}/t^{\prime}]$ and
$\cdot;\Psi_{0},u:\nu
t.\mathcal{U};\Upsilon,\alpha^{\prime}::\mathcal{U}^{\prime}\rightarrow\mathsf{Ty},\alpha::\nu
t.\mathcal{U}\rightarrow\mathsf{Ty}\vdash\tau^{\prime}::\mathsf{Ty}$,
$\cdot;\Psi_{0};\Upsilon,\alpha^{\prime}::\mathcal{U}^{\prime}\rightarrow\mathsf{Ty}\vdash\tau_{0}^{\prime\prime}\equiv\tau_{0}[U^{\prime}/u][\lambda
u^{\prime}\\!:\\!\nu t.\mathcal{U}.\mu(\alpha;u\\!:\\!\nu
t.\mathcal{U}.\tau^{\prime};u^{\prime})/\alpha]::\mathsf{Ty}$. By F:Rec,
$\Upsilon\vdash_{U[U^{\prime}/u]}\sigma[\mu\alpha.\sigma^{\prime}/\alpha]\leadsto\mu(\alpha^{\prime};u_{0}:\mathcal{U}^{\prime}.\tau_{0}^{\prime\prime};U[U^{\prime}/u]);\mathcal{U}^{\prime}$.
By U:PsiVar and UT:Corec1 and U:Subtype and weakening,
$\cdot;\Psi,u_{0}:\mathcal{U}^{\prime}\vdash
u_{0}:\mathcal{U}_{0}[\mathcal{U}^{\prime}/t^{\prime}]$ and
$\cdot;\Psi,u_{0}:\mathcal{U}^{\prime},u:\nu
t.\mathcal{U};\Upsilon,\alpha^{\prime}::\mathcal{U}^{\prime}\rightarrow\mathsf{Ty},\alpha::\nu
t.\mathcal{U}\rightarrow\mathsf{Ty}\vdash\tau^{\prime}::\mathsf{Ty}$ for all
$\Psi$ such that $\cdot;\Psi\vdash U[U^{\prime}/u]:\mathcal{U}^{\prime}$ and
$\cdot;\Psi,u:\nu
t.\mathcal{U};\Upsilon,\alpha^{\prime}::\mathcal{U}^{\prime}\rightarrow\mathsf{Ty},\alpha::\nu
t.\mathcal{U}\rightarrow\mathsf{Ty}\vdash\tau^{\prime}::\mathsf{Ty}$. Apply
UE:Reflexive and CE:Rec.

∎

Proof of Theorem 1.

###### Proof.

  1. (1)

By induction on the derivation of $\Upsilon\vdash\sigma::\mathsf{Ty}$.

     * •

KU:Unit. Then $\sigma=\mathsf{unit}$. By F:Unit,
$\mathsf{Ann}(\Upsilon)\vdash_{U}\sigma\leadsto\mathsf{unit};\blacklozenge$
for all $U$.

     * •

KU:Var. Then $\sigma=\alpha$. and
$\Upsilon=\Upsilon^{\prime},\alpha::\mathsf{Ty}$. Thus
$\mathsf{Ann}(\Upsilon)=\mathsf{Ann}(\Upsilon^{\prime}),\alpha::t\rightarrow\mathsf{Ty}$
where $t~{}\mathsf{fresh}$. By F:TyVar,
$\mathsf{Ann}(\Upsilon)\vdash_{U}\sigma\leadsto\alpha~{}U;t$ for all $U$.

     * •

KU:Fun. Then
$\sigma=\Pi[u_{f}\\!:\\!\mathcal{U}_{f};u_{t}\\!:\\!\mathcal{U}_{t}].c_{1}\xrightarrow{G[u_{f};u_{t}]}c_{2}$.
By F:Fun,
$\mathsf{Ann}(\Upsilon)\vdash_{U}\sigma\leadsto\Pi[u_{f}\\!:\\!\mathcal{U}_{f};u_{t}\\!:\\!\mathcal{U}_{t}].c_{1}\xrightarrow{G[u_{f};u_{t}]}c_{2};\blacklozenge$
for all $U$.

     * •

KU:Prod. Then $\sigma=\sigma_{1}\times\sigma_{2}$ and
$\Upsilon\vdash\sigma_{1}::\mathsf{Ty}$ and
$\Upsilon\vdash\sigma_{2}::\mathsf{Ty}$. By induction, for all $U$ there
exists $\tau_{1}$, $\tau_{2}$, $\mathcal{U}_{1}$, and $\mathcal{U}_{2}$ such
that
$\mathsf{Ann}(\Upsilon)\vdash_{\mathsf{fst}~{}U}\sigma_{1}\leadsto\tau_{1};\mathcal{U}_{1}$
and
$\mathsf{Ann}(\Upsilon)\vdash_{\mathsf{snd}~{}U}\sigma_{2}\leadsto\tau_{2};\mathcal{U}_{2}$.
Apply F:Prod.

     * •

KU:Sum. By symmetry with the previous case.

     * •

KU:Fut. Then $\sigma=\sigma^{\prime}~{}\mathsf{future}$ and
$\Upsilon\vdash\sigma^{\prime}::\mathsf{Ty}$. By induction, for all $U$ there
exists $\tau^{\prime}$ and $\mathcal{U}^{\prime}$ such that
$\mathsf{Ann}(\Upsilon)\vdash_{\mathsf{fst}~{}U}\sigma^{\prime}\leadsto\tau^{\prime};\mathcal{U}^{\prime}$.
Apply F:Fut.

     * •

KU:Rec. Then $\sigma=\mu\alpha.\sigma^{\prime}$ and
$\Upsilon,\alpha::\mathsf{Ty}\vdash\sigma^{\prime}::\mathsf{Ty}$. Thus
$\mathsf{Ann}(\Upsilon,\alpha::\mathsf{Ty})=\mathsf{Ann}(\Upsilon),\alpha::t\rightarrow\mathsf{Ty}$
where $t~{}\mathsf{fresh}$. By induction, there exists $\tau^{\prime}$ and
$\mathcal{U}^{\prime}$ such that
$\mathsf{Ann}(\Upsilon),\alpha::t\rightarrow\mathsf{Ty}\vdash_{u}\sigma^{\prime}\leadsto\tau^{\prime};\mathcal{U}^{\prime}$.
By Lemma 1, $\mathsf{Ann}(\Upsilon),\alpha::\nu
t.\mathcal{U}^{\prime}\rightarrow\mathsf{Ty}\vdash_{u}\sigma^{\prime}\leadsto\tau^{\prime}[\nu
t.\mathcal{U}^{\prime}/t];\mathcal{U}^{\prime}[\nu t.\mathcal{U}^{\prime}/t]$
(since $t~{}\mathsf{fresh}$, $\mathsf{Ann}(\Upsilon)[\nu
t.\mathcal{U}^{\prime}/t]=\mathsf{Ann}(\Upsilon)$ and $\sigma^{\prime}[\nu
t.\mathcal{U}^{\prime}/t]\\\ =\sigma^{\prime}$). By F:Rec,
$\mathsf{Ann}(\Upsilon)\vdash_{U}\sigma\leadsto\mu(\alpha;u:\nu
t.\mathcal{U}^{\prime}.\tau^{\prime}[\nu t.\mathcal{U}^{\prime}/t];U);\nu
t.\mathcal{U}^{\prime}$ for all $U$.

  2. (2)

By induction on the derivation of
$\Upsilon\vdash_{U}\sigma\leadsto\tau;\mathcal{U}$.

     * •

F:TyVar. Then $\tau=\alpha~{}U$ and
$\Upsilon=\Upsilon^{\prime},\alpha::\mathcal{U}\rightarrow\mathsf{Ty}$. Apply
K:Var and K:App.

     * •

F:Unit. Then $\tau=\mathsf{unit}$. Apply K:Unit.

     * •

F:Fun. Then
$\sigma=\tau=\Pi[u_{f}\\!:\\!\mathcal{U}_{f};u_{t}\\!:\\!\mathcal{U}_{t}].c_{1}\xrightarrow{G}c_{2}$.
By inversion on KU:Fun,
$\cdot;u_{f}:\mathcal{U}_{f},u_{t}:\mathcal{U}_{t};\cdot\vdash
c_{1}::\mathsf{Ty}$ and
$\cdot;u_{f}:\mathcal{U}_{f},u_{t}:\mathcal{U}_{t};\cdot\vdash
c_{2}::\mathsf{Ty}$ and $\cdot;\cdot;\cdot\vdash
G:\Pi[u_{f}\\!:\\!\mathcal{U}_{f};u_{t}\\!:\\!\mathcal{U}_{t}].*$. Apply K:Fun
and weakening.

     * •

F:Prod. Then $\sigma=\sigma_{1}\times\sigma_{2}$ and
$\tau=\tau_{1}\times\tau_{2}$ and
$\mathcal{U}=\mathcal{U}_{1}^{\blacksquare}\times\mathcal{U}_{2}^{\blacksquare}$
and
$\Upsilon\vdash_{\mathsf{fst}~{}U}\sigma_{1}\leadsto\tau_{1};\mathcal{U}_{1}$
and
$\Upsilon\vdash_{\mathsf{snd}~{}U}\sigma_{2}\leadsto\tau_{2};\mathcal{U}_{2}$.
By inversion on KU:Prod,
$\mathsf{Unann}(\Upsilon)\vdash\sigma_{1}::\mathsf{Ty}$ and
$\mathsf{Unann}(\Upsilon)\vdash\sigma_{2}::\mathsf{Ty}$. By U:Fst and U:Snd,
$\cdot;\Psi\vdash\mathsf{fst}~{}U:\mathcal{U}_{1}$ and
$\cdot;\Psi\vdash\mathsf{snd}~{}U:\mathcal{U}_{2}$. By induction,
$\cdot;\Psi;\Upsilon\vdash\tau_{1}::\mathsf{Ty}$ and
$\cdot;\Psi;\Upsilon\vdash\tau_{2}::\mathsf{Ty}$. Apply K:Prod.

     * •

F:Sum. By symmetry with the previous case.

     * •

F:Future. Then $\sigma=\sigma^{\prime}~{}\mathsf{future}$ and
$\tau=\tau^{\prime}~{}\mathsf{future}[\mathsf{snd}~{}U]$ and
$\mathcal{U}=\mathcal{U}^{\prime\blacksquare}\times\blacklozenge^{\blacksquare}$
and
$\Upsilon\vdash_{\mathsf{fst}~{}U}\sigma^{\prime}\leadsto\tau^{\prime};\mathcal{U}^{\prime}$.
By inversion on KU:Fut,
$\mathsf{Unann}(\Upsilon)\vdash\sigma^{\prime}::\mathsf{Ty}$. By U:Fst and
U:Snd, $\cdot;\Psi\vdash\mathsf{fst}~{}U:\mathcal{U}^{\prime}$ and
$\cdot;\Psi\vdash\mathsf{snd}~{}U:\blacklozenge$. By induction,
$\cdot;\Psi;\Upsilon\vdash\tau^{\prime}::\mathsf{Ty}$. Apply K:Fut.

     * •

F:Rec. Then $\sigma=\mu\alpha.\sigma^{\prime}$ and $\tau=\mu(\alpha;u:\nu
t.\mathcal{U}^{\prime}.\tau^{\prime};U)$ and $\mathcal{U}=\nu
t.\mathcal{U}^{\prime}$ and
$\Upsilon,\alpha::\mathcal{U}\rightarrow\mathsf{Ty}\vdash_{u}\sigma^{\prime}\leadsto\tau^{\prime};\mathcal{U}^{\prime}[\nu
t.\mathcal{U}^{\prime}/t]$. By inversion on KU:Rec,
$\mathsf{Unann}(\Upsilon),\alpha::\mathsf{Ty}\vdash\sigma^{\prime}::\mathsf{Ty}$.
By U:PsiVar, $\cdot;\Psi,u:\mathcal{U}\vdash u:\mathcal{U}$. By UT:Corec1 and
U:Subtype, $\cdot;\Psi,u:\mathcal{U}\vdash u:\mathcal{U}^{\prime}[\nu
t.\mathcal{U}^{\prime}/t]$. By induction,
$\cdot;\Psi,u:\mathcal{U};\Upsilon,\alpha::\mathcal{U}\rightarrow\mathsf{Ty}\vdash\tau^{\prime}::\mathsf{Ty}$.
Apply K:Rec.

  3. (3)

By induction on the derivation of
$\cdot\vdash_{\mathit{VP}}\sigma\leadsto\tau;\mathcal{U}$.

     * •

F:Unit. Then $\sigma=\tau=\mathsf{unit}$. By inversion on SU:Unit,
$\epsilon=\langle\rangle$. By FE:Unit,
$\vdash_{\mathit{VP}}\epsilon\leadsto\langle\rangle$. Apply SV:Unit for all
$\Omega$.

     * •

F:Fun. Then
$\sigma=\tau=\Pi[u_{f}\\!:\\!\mathcal{U}_{f};u_{t}\\!:\\!\mathcal{U}_{t}].\tau_{1}\xrightarrow{G}\tau_{2}$.
By inversion on SU:Fun, $\epsilon=\mathsf{fun}[u_{f};u_{t}]~{}f~{}x=e$ and
$G=(\mu\gamma.\Pi[u_{f}:\mathcal{U}_{f};u_{t}:\mathcal{U}_{t}].G^{\prime})[u_{f};u_{t}]$
and $\gamma~{}\mathsf{fresh}$ and
$\gamma:\Pi[u_{f}\\!:\\!\mathcal{U}_{f};u_{t}\\!:\\!\mathcal{U}_{t}].*;u_{f}:\mathcal{U}_{f};u_{f}:\mathcal{U}_{f},u_{t}:\mathcal{U}_{t};f:\Pi[u_{f}\\!:\\!\mathcal{U}_{f};u_{t}\\!:\\!\mathcal{U}_{t}].\tau_{1}\xrightarrow{\gamma[u_{f};u_{t}]}\tau_{2},x:\tau_{1}\vdash
e:\tau_{2}\mid G^{\prime}$ and
$\cdot;u_{f}:\mathcal{U}_{f},u_{t}:\mathcal{U}_{t};\cdot\vdash\tau_{1}::\mathsf{Ty}$
and
$\cdot;u_{f}:\mathcal{U}_{f},u_{t}:\mathcal{U}_{t};\cdot\vdash\tau_{2}::\mathsf{Ty}$.
By FE:Fun,
$\vdash_{\mathit{VP}}\epsilon\leadsto\mathsf{fun}[u_{f};u_{t}]~{}f~{}x=e$.
Apply SV:Fun for all $\Omega$.

     * •

F:Prod. Then $\sigma=\sigma_{1}\times\sigma_{2}$ and
$\tau=\tau_{1}\times\tau_{2}$ and
$\mathcal{U}=\mathcal{U}_{1}^{\blacksquare}\times\mathcal{U}_{2}^{\blacksquare}$
and
$\cdot\vdash_{\mathsf{fst}~{}\mathit{VP}}\sigma_{1}\leadsto\tau_{1};\mathcal{U}_{1}$
and
$\cdot\vdash_{\mathsf{snd}~{}\mathit{VP}}\sigma_{2}\leadsto\tau_{2};\mathcal{U}_{2}$.
By inversion on SU:Pair, $\epsilon=(\epsilon_{1},\epsilon_{2})$ and
$\vdash\epsilon_{1}:\sigma_{1}$ and $\vdash\epsilon_{2}:\sigma_{2}$. By
inversion on KU:Prod, $\cdot\vdash\sigma_{1}::\mathsf{Ty}$ and
$\cdot\vdash\sigma_{2}::\mathsf{Ty}$. By induction, there exist $v_{1}$ and
$v_{2}$ such that $\vdash_{\mathsf{fst}~{}\mathit{VP}}\epsilon_{1}\leadsto
v_{1}$ and $\vdash_{\mathsf{snd}~{}\mathit{VP}}\epsilon_{2}\leadsto v_{2}$,
and for all $\Omega_{1}$ such that
$\Omega_{1};\cdot\vdash\mathsf{fst}~{}\mathit{VP}:\mathcal{U}_{1}$, we have
$\Omega_{1}\vdash_{A}v_{1}:\tau_{1}$, and for all $\Omega_{2}$ such that
$\Omega_{2};\cdot\vdash\mathsf{snd}~{}\mathit{VP}:\mathcal{U}_{2}$, we have
$\Omega_{2}\vdash_{A}v_{2}:\tau_{2}$. By FE:Pair,
$\vdash_{\mathit{VP}}\epsilon\leadsto(v_{1},v_{2})$. By US:Prod,
$\mathcal{U}\rightsquigarrow\mathcal{U}_{1}^{\blacksquare}\times\mathcal{U}_{2}^{\square}\boxplus\mathcal{U}_{1}^{\square}\times\mathcal{U}_{2}^{\blacksquare}$.
By Lemma 7, there exists $\Omega_{1}$ and $\Omega_{2}$ such that
$\Omega\rightsquigarrow\Omega_{1}\boxplus\Omega_{2}$ and
$\Omega_{1};\cdot\vdash\mathit{VP}:\mathcal{U}_{1}^{\blacksquare}\times\mathcal{U}_{2}^{\square}$
and
$\Omega_{2};\cdot\vdash\mathit{VP}:\mathcal{U}_{1}^{\square}\times\mathcal{U}_{2}^{\blacksquare}$
for all $\Omega$ such that $\Omega;\cdot\vdash\mathit{VP}:\mathcal{U}$. By
U:Fst and U:Snd,
$\Omega_{1};\cdot\vdash\mathsf{fst}~{}\mathit{VP}:\mathcal{U}_{1}$ and
$\Omega_{2};\cdot\vdash\mathsf{snd}~{}\mathit{VP}:\mathcal{U}_{2}$. Apply
SV:Pair.

     * •

F:Sum. Then $\sigma=\sigma_{1}+\sigma_{2}$ and $\tau=\tau_{1}+\tau_{2}$ and
$\mathcal{U}=\mathcal{U}_{1}^{\blacksquare}\times\mathcal{U}_{2}^{\blacksquare}$
and
$\cdot\vdash_{\mathsf{fst}~{}\mathit{VP}}\sigma_{1}\leadsto\tau_{1};\mathcal{U}_{1}$
and
$\cdot\vdash_{\mathsf{snd}~{}\mathit{VP}}\sigma_{2}\leadsto\tau_{2};\mathcal{U}_{2}$.
By inversion on either SU:InL or SU:InR, either
$\epsilon=\mathsf{inl}~{}\epsilon^{\prime}$ and
$\vdash\epsilon^{\prime}:\sigma_{1}$ or
$\epsilon=\mathsf{inr}~{}\epsilon^{\prime}$ and
$\vdash\epsilon^{\prime}:\sigma_{2}$. We take the former case, the other is
similar. By inversion on KU:Sum, $\cdot\vdash\sigma_{1}::\mathsf{Ty}$. By
induction, there exists $v^{\prime}$ such that
$\vdash_{\mathsf{fst}~{}\mathit{VP}}\epsilon^{\prime}\leadsto v^{\prime}$, and
for all $\Omega^{\prime}$ such that
$\Omega^{\prime};\cdot\vdash\mathsf{fst}~{}\mathit{VP}:\mathcal{U}_{1}$, we
have $\Omega^{\prime}\vdash_{A}v^{\prime}:\tau_{1}$. By FE:InL,
$\vdash_{\mathit{VP}}\epsilon\leadsto\mathsf{inl}~{}v^{\prime}$. By U:Fst,
$\Omega;\cdot\vdash\mathsf{fst}~{}\mathit{VP}:\mathcal{U}_{1}$ for all
$\Omega$ such that $\Omega;\cdot\vdash\mathit{VP}:\mathcal{U}$. Apply SV:InL.

     * •

F:Future. Then $\sigma=\sigma^{\prime}~{}\mathsf{future}$ and
$\tau=\tau^{\prime}~{}\mathsf{future}[\mathsf{snd}~{}\mathit{VP}]$ and
$\mathcal{U}=\mathcal{U}^{\prime\blacksquare}\times\blacklozenge^{\blacksquare}$
and
$\cdot\vdash_{\mathsf{fst}~{}\mathit{VP}}\sigma^{\prime}\leadsto\tau^{\prime};\mathcal{U}^{\prime}$.
By inversion on SU:Handle, $\epsilon=\mathsf{handle}~{}\epsilon^{\prime}$ and
$\vdash\epsilon^{\prime}:\sigma^{\prime}$. By inversion on KU:Fut,
$\cdot\vdash\sigma^{\prime}::\mathsf{Ty}$. By induction, there exists
$v^{\prime}$ such that
$\vdash_{\mathsf{fst}~{}\mathit{VP}}\epsilon^{\prime}\leadsto v^{\prime}$, and
for all $\Omega^{\prime}$ such that
$\Omega^{\prime};\cdot\vdash\mathsf{fst}~{}\mathit{VP}:\mathcal{U}^{\prime}$,
we have $\Omega^{\prime}\vdash_{A}v^{\prime}:\tau^{\prime}$. By FE:Handle,
$\vdash_{\mathit{VP}}\epsilon\leadsto\mathsf{handle}[\mathsf{snd}~{}\mathit{VP}]~{}v^{\prime}$.
By US:Prod,
$\mathcal{U}\rightsquigarrow\mathcal{U}^{\prime\blacksquare}\times\blacklozenge^{\square}\boxplus\mathcal{U}^{\prime\square}\times\blacklozenge^{\blacksquare}$.
By Lemma 7, for all $\Omega$ such that
$\Omega;\cdot\vdash\mathit{VP}:\mathcal{U}$, there exists $\Omega_{1}$ and
$\Omega_{2}$ such that $\Omega\rightsquigarrow\Omega_{1}\boxplus\Omega_{2}$
and
$\Omega_{1};\cdot\vdash\mathit{VP}:\mathcal{U}^{\prime\blacksquare}\times\blacklozenge^{\square}$
and
$\Omega_{2};\cdot\vdash\mathit{VP}:\mathcal{U}^{\prime\square}\times\blacklozenge^{\blacksquare}$.
By U:Fst and U:Snd,
$\Omega_{1};\cdot\vdash\mathsf{fst}~{}\mathit{VP}:\mathcal{U}^{\prime}$ and
$\Omega_{2};\cdot\vdash\mathsf{snd}~{}\mathit{VP}:\blacklozenge$. Apply
SV:Handle.

     * •

F:Rec. Then $\sigma=\mu\alpha.\sigma^{\prime}$ and $\tau=\mu(\alpha;u:\nu
t.\mathcal{U}^{\prime}.\tau^{\prime};\mathit{VP})$ and $\mathcal{U}=\nu
t.\mathcal{U}^{\prime}$ and $\alpha::\nu
t.\mathcal{U}^{\prime}\rightarrow\mathsf{Ty}\vdash_{u}\sigma^{\prime}\leadsto\tau^{\prime};\mathcal{U}^{\prime}[\nu
t.\mathcal{U}^{\prime}/t]$. By inversion on SU:Roll,
$\epsilon=\mathsf{roll}~{}\epsilon^{\prime}$ and
$\vdash\epsilon^{\prime}:\sigma^{\prime}[\mu\alpha.\sigma^{\prime}/\alpha]$.
By inversion on KU:Rec,
$\alpha::\mathsf{Ty}\vdash\sigma^{\prime}::\mathsf{Ty}$. By Lemma 2,
$\cdot\vdash\sigma^{\prime}[\mu\alpha.\sigma^{\prime}/\alpha]::\mathsf{Ty}$.
By Lemma 3,
$\cdot\vdash_{\mathit{VP}}\sigma^{\prime}[\mu\alpha.\sigma^{\prime}/\alpha]\leadsto\tau^{\prime\prime};\mathcal{U}^{\prime}[\nu
t.\mathcal{U}^{\prime}/t]$, and for all $\Psi$ such that
$\cdot;\Psi\vdash\mathit{VP}:\mathcal{U}^{\prime}[\nu
t.\mathcal{U}^{\prime}/t]$ and $\cdot;\Psi,u:\nu
t.\mathcal{U}^{\prime};\alpha::\nu
t.\mathcal{U}^{\prime}\rightarrow\mathsf{Ty}\vdash\tau^{\prime}::\mathsf{Ty}$,
$\cdot;\Psi;\cdot\vdash\tau^{\prime\prime}\equiv\tau^{\prime}[\mathit{VP}/u][\lambda
u^{\prime}\\!:\\!\nu t.\mathcal{U}^{\prime}.\mu(\alpha;u\\!:\\!\nu
t.\mathcal{U}^{\prime}.\tau^{\prime};u^{\prime})/\alpha]::\mathsf{Ty}$. By
induction, there exists $v^{\prime}$ such that
$\vdash_{\mathit{VP}}\epsilon^{\prime}\leadsto v^{\prime}$, and for all
$\Omega^{\prime}$ such that
$\Omega^{\prime};\cdot\vdash\mathit{VP}:\mathcal{U}^{\prime}[\nu
t.\mathcal{U}^{\prime}/t]$, we have
$\Omega\vdash_{A}v^{\prime}:\tau^{\prime\prime}$. By FE:Roll,
$\vdash_{\mathit{VP}}\epsilon\leadsto\mathsf{roll}~{}v^{\prime}$. By UT:Corec1
and U:Subtype, $\Omega;\cdot\vdash\mathit{VP}:\mathcal{U}^{\prime}[\nu
t.\mathcal{U}^{\prime}/t]$ for all $\Omega$ such that
$\Omega;\cdot\vdash\mathit{VP}:\mathcal{U}$. By Lemma 8,
$\cdot;\Omega\vdash\mathit{VP}:\mathcal{U}^{\prime}[\nu
t.\mathcal{U}^{\prime}/t]$ and $\cdot;\Omega\vdash\mathit{VP}:\mathcal{U}$. By
part 2, $\cdot;\Omega;\Upsilon\vdash\tau::\mathsf{Ty}$. By inversion on K:Rec,
$\cdot;\Omega,u:\nu t.\mathcal{U}^{\prime};\alpha::\nu
t.\mathcal{U}^{\prime}\vdash\tau^{\prime}::\mathsf{Ty}$. Thus
$\cdot;\Omega;\cdot\vdash\tau^{\prime\prime}\equiv\tau^{\prime}[\mathit{VP}/u][\lambda
u^{\prime}\\!:\\!\nu t.\mathcal{U}^{\prime}.\mu(\alpha;u\\!:\\!\nu
t.\mathcal{U}^{\prime}.\tau^{\prime};u^{\prime})/\alpha]::\mathsf{Ty}$. Apply
SV:Type-Eq and SV:Roll.

∎