\section{Introduction}
\label{sec:Introduction}

Let $\FF_q$ denote a finite field with $q$ elements, where $q$ is a power of
the prime number~$p$, and let $X$ denote an algebraic variety over~$\FF_q$.

\begin{defn}
The zeta function of $X$ is the formal power series
\[
Z(X,T) = \exp \Bigl(\sum_{i=1}^{\infty} \card{X(\FF_{q^i})} \frac{T^i}{i} \Bigr).
\]
\end{defn}

As we will see in the next section, $Z(X,T)$
is a rational function, i.e.\ it is contained in $\QQ(T)$, and
hence can be given by a finite amount of data. Therefore, it is natural
to ask whether it can be computed effectively and, in fact, it is not
hard to provide an algorithm as follows. Using well known bounds
by Bombieri~\citep{Bombieri1966} for the degrees of the numerator and
denominator of $Z(X,T)$, one can reduce the computation of $Z(X,T)$ to that
of a finite number of the $\card{X(\FF_{q^i})}$, which can be determined
by naive counting.

A more interesting problem is whether, and if so how, $Z(X,T)$ can be
computed efficiently, where `efficiently' can mean with low time complexity
or just fast in practice. When $X$ is a (hyper-)elliptic curve, this problem
is important in cryptographic applications and has been the subject of
much attention, resulting in very efficient algorithms.  For example, when
$X$ is an elliptic curve, Schoof's algorithm~\citep{Schoof1995}, which uses
$\ell$-adic \'etale cohomology, has runtime polynomial in~$\log(q)$, and is
also very fast in practice using improvements due to Atkins and Elkies.

For more general algebraic varieties~$X$, the only available option is
usually to compute the rigid cohomology spaces of~$X$, with their natural
action of the Frobenius map, and then use a Lefschetz formula to deduce the
zeta function. This method was introduced by Kedlaya in the case of
hyperelliptic curves in odd characteristic~\citep{Kedlaya2001}.  The same
idea has been shown to work in much greater generality, for example for
smooth projective hypersurfaces \citep{AbbottKedlayaRoe2006}.

Lauder \citep{Lauder2004a,Lauder2004b} showed that instead of computing the
action of the Frobenius map on the rigid cohomology spaces of a smooth
projective hypersurface~$X$ directly, it is better, at least in terms of
time complexity, to embed $X$ in a family of smooth projective hypersurfaces
containing a diagonal hypersurface.  Following his deformation method,
one first computes the action of the Frobenius map on the rigid cohomology
of the diagonal hypersurface, and then solves a $p$-adic differential equation
to obtain the Frobenius map on the rigid cohomology of the original
hypersurface.

To be more precise, in~\citep{Lauder2004a,Lauder2004b} Lauder did not directly
work with rigid cohomology but with Dwork cohomology. While the two
cohomology theories are equivalent, various comparison and finiteness results
are more easily stated and proved in the context of rigid cohomology.  In~\citep{Gerkmann2007}
Gerkmann reformulated Lauder's deformation method in terms of rigid
cohomology.  Moreover, he improved various precision bounds, making
the algorithm more practical, which he demonstrated with many examples. Kedlaya
introduced new ideas and results to further lower the precision bounds for
the deformation method in \citep{Kedlaya2012}.

The aim of this paper is to continue where Lauder, Gerkmann and Kedlaya left
off. We make improvements to almost every step of the algorithm. This results
in an algorithm with both lower time and space complexity than Lauder's
original algorithm, but perhaps more importantly, which is a lot more efficient
in practice. The first author has written a (publicly available)
implementation of our algorithm using the library FLINT~\citep{FLINT}.
This implementation lowers the runtimes of the examples in~\citep{Gerkmann2007}
by factors of $50$ to $5,000$. Moreover, it can be used to compute the zeta
function in many cases where this was not possible before, e.g.\ for generic
quartic surfaces.

We now briefly describe the contents of the remaining sections,
necessarily relying on some terminology that is introduced only
in Section~\ref{sec:Background}.  The reader who is not familiar
with this terminology might prefer to start reading there.

In Section~\ref{sec:Background}, we recall the main theoretical results that
underpin the remaining sections of the paper.  We limit ourselves to the bare
minimum as there are already good references available for the relevant theory,
see e.g.~\citep{Kedlaya2012}. We also introduce the required terminology and
notation. We conclude the section with an overview of the different steps of
the deformation method, which are then treated individually in the next four
sections.

In Section~\ref{sec:Connection}, we explain how to compute the Gauss--Manin
connection on the cohomology of a family of smooth projective hypersurfaces.
We define an explicit monomial basis for the cohomology that we will use
throughout the paper. Our most important result in this section
is Theorem~\ref{thm:Isomorphism}, which allows us to compute very efficiently
in the cohomology. We formalise the computation of the Gauss--Manin connection
matrix in Algorithm~\ref{alg:Connection}. We also prove some lower bounds for
the valuation of the matrix of Frobenius and its inverse that are essential
for controlling the $p$-adic precision loss in the algorithm.

In Section~\ref{sec:Diagonal}, we show how to compute the Frobenius matrix of
a diagonal hypersurface over a prime field. Our method is essentially based
on a computation of Dwork, but by rewriting and slightly generalising his formulas
we obtain Algorithm~\ref{alg:Diagfrob}, which is a significant improvement to the
corresponding algorithms of Lauder and Gerkmann, both in terms of time complexity
and in practice.

In Section~\ref{sec:DifferentialSystem}, we explain how to solve the
differential equation for the Frobenius matrix. We use the same method as
Lauder but incorporate improved convergence bounds for $p$-adic differential
equations by Kedlaya. We collect the precision bounds that follow from our
analysis in Theorem~\ref{thm:Ni} and formalise the computation of the power
series expansion of the Frobenius matrix in Algorithm~\ref{alg:expansion}.

In Section~\ref{sec:ZetaFunctions}, we describe how to evaluate the Frobenius
matrix at some fibre and compute its zeta function. We combine various bounds
from different sources to lower the required $p$-adic and $t$-adic precisions.
This finally results in Algorithm~\ref{alg:complete}, which combines all of
our previous algorithms, and is the main result of the paper.

In Section~\ref{sec:Complexity}, we analyse the time and space complexity of
our algorithm and compare these to Lauder's work~\citep{Lauder2004a}.
In Section~\ref{sec:Examples}, we compute various numerical examples, and
compare our runtimes to those provided by Gerkmann~\citep{Gerkmann2007}.

Both authors were supported by the European Research Council (grant 204083)
and additionally the second author was supported by FWO - Vlaanderen. We would
like to thank Alan Lauder for all his help and in particular for his comments and
suggestions on earlier versions of this paper. Finally, we thank the anonymous
referees for their comments and suggestions.

\section{Theoretical background}
\label{sec:Background}

We start by recalling the main result about the zeta function of algebraic
varieties over finite fields.

\begin{thm}[Weil conjectures] If $X/\FF_q$ is a smooth projective variety of
dimension~$m$, then \label{thm:weildeligne}
\[
Z(X,T)=\frac{p_1 p_3 \dotsm p_{2m-1}}{p_0 p_2 p_4 \dotsm p_{2m}},
\]
where for all $i$:
\begin{enumerate}
\item $p_i = \prod_j (1-\alpha_{i,j}T) \in \ZZ[T]$,
\item the transformation $t \rightarrow q^m/t$ maps the $\alpha_{i,j}$
      bijectively to the $\alpha_{2m-i,k}$, preserving multiplicities,
\item $\abs{\alpha_{i,j}} = q^{i/2}$ for all $j$, and every embedding
      $\bar{\QQ} \hookrightarrow \CC$.
\end{enumerate}
\end{thm}

\begin{proof}
The proof of this theorem was completed by Deligne in \citep{Deligne1974}.
\end{proof}

We let $\QQ_q$ denote the unique unramified extension of $\QQ_p$ with
residue field $\FF_q$ and $\ZZ_q$ its ring of integers. We denote
the $p$-adic valuation on $\QQ_q$ by $\ord_p(-)$.

\begin{defn}
Let $\Hrig^{i}(X)$ denote the rigid
cohomology spaces of $X$. These are finite dimensional vector spaces
over $\QQ_q$ that are contravariantly functorial in $X$, and they are
equipped with an action of the $p$-th and $q$-th power Frobenius map
on $X$ that we denote by $\Frob_p$ and $\Frob_q$, respectively. For the
construction and basic properties of these spaces we refer
to~\citep{Berthelot1986}.
\end{defn}

The relation between the zeta function and the rigid cohomology spaces
is given by the so called Lefschetz formula.

\begin{thm}[Lefschetz formula] \label{thm:Lefschetz}
If $X$ is a smooth proper algebraic variety over~$\FF_q$ of dimension~$m$,
then
\[
Z(X,T) = \prod_{i=0}^{2m} \det \bigl(1- T \Frob_q | \Hrig^i(X) \bigr)^{(-1)^{i+1}}.
\]
\end{thm}

\begin{proof}
See for example \citep[Theorem 6.3]{EtesseLeStum1993}.
\end{proof}

Let $\pi \colon \mathfrak{X} \rightarrow \mathfrak{S}$ be a smooth family of
algebraic varieties defined over~$\QQ_q$.

\begin{defn}
Let $\HdR^i(\mathfrak{X}/\mathfrak{S})$ denote the $i$-th relative algebraic
de Rham cohomology sheaf on $\mathfrak{S}$.
If $\mathfrak{X}/\mathfrak{S}$ admits a relative normal crossing
compactification, then the $\HdR^i(\mathfrak{X}/\mathfrak{S})$ are vector bundles.
\end{defn}

The $\HdR^i(\mathfrak{X}/\mathfrak{S})$ come equipped with an integrable
connection, which is called the Gauss--Manin connection. Let us first recall
the notion of a connection on a vector bundle.

\begin{defn}
Let $\mathfrak{E}$ be a vector bundle on $\mathfrak{S}$. A connection on
$\mathfrak{E}$ is a map of vector bundles
$\nabla \colon \mathfrak{E} \rightarrow \Omega^1_{\mathfrak{S}} \otimes \mathfrak{E}$
which satisfies the Leibniz rule
\begin{align*}
\nabla(f e)=f\nabla(e)+df \otimes e
\end{align*}
for all local sections~$f$ of $\mathcal{O}_{\mathfrak{S}}$ and $e$
of $\mathfrak{E}$.
\end{defn}

The Gauss--Manin connection on $\HdR^i(\mathfrak{X}/\mathfrak{S})$ can
be defined as follows.

\begin{defn}
The de Rham complex $\Omega^{\bullet}_{\mathfrak{X}}$ can be equipped
with the decreasing filtration
\[
F^i=\fIm(\Omega^{\bullet-i}_{\mathfrak{X}} \otimes \pi^* \Omega^i_{\mathfrak{S}} \rightarrow \Omega^{\bullet}_{\mathfrak{X}}).
\]
The spectral sequence associated to this filtration has as its first sheet
\[
E_1^{p,q}=\Omega^p_{\mathfrak{S}} \otimes \HdR^q(\mathfrak{X}/\mathfrak{S}).
\]
The Gauss--Manin connection
$\nabla:H^i(\mathfrak{X}/\mathfrak{S}) \rightarrow \Omega^1_{\mathfrak{S}} \otimes H^i(\mathfrak{X}/\mathfrak{S})$
is now defined as the differential $d_1 \colon E_1^{0,i} \rightarrow E_1^{1,i}$
in this spectral sequence.
\end{defn}

\begin{rem}
We can give a more explicit description of $\nabla$ when
$\mathfrak{X}/\mathfrak{S}$ is affine. If we lift a relative $i$-cocycle
$\omega \in \Omega^i_{\mathfrak{X}/\mathfrak{S}}$ to an absolute $i$-form
$\omega' \in \Omega^i_{\mathfrak{X}}$ and apply the absolute differential~$d$,
we get an element of
$\Omega^1_{\mathfrak{S}} \wedge \Omega^i_{\mathfrak{X}/\mathfrak{S}}$.
Projecting onto
$\Omega^1_{\mathfrak{S}} \otimes \HdR^i(\mathfrak{X}/\mathfrak{S})$,
we obtain $\nabla(\omega)$.
\end{rem}

\begin{defn} \label{defn:sigma}
We write $\sigma$ for the standard $p$-th power Frobenius lift on
$\mathbf{P}^1_{\QQ_q}$, i.e.\ the semilinear map that lifts the $p$-th power
Frobenius map on $\mathbf{P}^1_{\FF_q}$ and satisfies $\sigma(t)=t^p$.
\end{defn}

Now suppose that $\mathfrak{E}$ is a vector bundle with connection on
some Zariski open subset~$\mathfrak{S}$ of $\mathbf{P}^1_{\QQ_q}$ with
complement~$\mathfrak{Z}$. Let~$V$ denote the rigid analytic subspace
of~$\mathbf{P}^1_{\QQ_q}$ which is the complement of the union of the
open disks of radius~$1$ around the points of~$\mathfrak{Z}$.

\begin{defn}
A Frobenius structure on $\mathfrak{E}$ is an isomorphism of vector bundles
with connection $F \colon \sigma^* \mathcal{E} \rightarrow \mathcal{E}$
defined on some strict neighbourhood of $V$.
\end{defn}

\begin{thm} \label{thm:frobstruc}
Let $\mathcal{S}$ be a Zariski open subset of $\mathbf{P}^1_{\ZZ_q}$ and
suppose that $\mathcal{X}/\mathcal{S}$ is a smooth family of algebraic
varieties that admits a relative normal crossing compactification. Denote
the generic fibres of $\mathcal{S}$, $\mathcal{X}$ by
$\mathfrak{S}=\mathcal{S} \otimes \QQ_q$, $\mathfrak{X}=\mathcal{X} \otimes \QQ_q$
and the special fibres by $S=\mathcal{S} \otimes \FF_q$,
$X=\mathcal{X} \otimes \FF_q$, respectively. The vector bundle
$\HdR^i(\mathfrak{X}/\mathfrak{S})$ with the Gauss--Manin connection $\nabla$
admits a Frobenius structure $F$ with the following property.
For any finite field extension $\FF_{\mathfrak{q}}/\FF_q$ and
all $\tau \in S(\FF_{\mathfrak{q}})$,
\[
(\Hrig^i(X_{\tau}),\Frob_p) \cong (\HdR^i(\mathfrak{X}/\mathfrak{S}),F)_{\hat{\tau}}
\]
as $\QQ_{\mathfrak{q}}$-vector spaces with a $\sigma$-semilinear
endomorphism, where $\hat{\tau} \in \mathcal{S}(\ZZ_{\mathfrak{q}})$ denotes
the Teichm\"uller lift of $\tau$. We will therefore denote this Frobenius
structure on $\HdR^i(\mathfrak{X}/\mathfrak{S})$ by $\Frob_p$ as well.
\end{thm}

\begin{proof}
This result is well known, see for example \citep[Theorem 6.1.3]{Kedlaya2012}.
Although it is usually attributed to Berthelot, a complete reference
seems to be missing from the literature.
\end{proof}

\begin{defn}
Let $\Hrig^i(X/S)$ denote the vector bundle $\HdR^i(\mathfrak{X}/\mathfrak{S})$
with its Frobenius structure $\Frob_p$ from Theorem~\ref{thm:frobstruc}.
\end{defn}

\begin{rem}
One can show that $\Hrig^i(X/S)$ is again functorial in $X/S$ and so does
not depend on the lift $\mathcal{X}/\mathcal{S}$. Moreover, one can still
define $\Hrig^i(X/S)$ when $X/S$ cannot be lifted to characteristic zero,
see~\citep{Berthelot1986}.  However, for our purposes the above definition
will be sufficient.
\end{rem}

In this paper we restrict our attention to one-parameter families of smooth
projective hypersurfaces. So we let $P \in \ZZ_q[t][x_0,\dotsc,x_n]$ denote
a homogeneous polynomial of degree $d$ and let
$\mathcal{S} \subset \mathbf{P}^1_{\ZZ_q}$ be a Zariski open subset such that
$P$ defines a family $\mathcal{X}/\mathcal{S}$ of smooth hypersurfaces contained
in $\mathbf{P}^n_{\mathcal{S}}$.
We let $\mathcal{U}/\mathcal{S}$
denote the complement of $\mathcal{X}/\mathcal{S}$ in $\mathbf{P}^n_{\mathcal{S}}$,
and write $\mathfrak{X}=\mathcal{X} \otimes \QQ_q$,
$\mathfrak{U}=\mathcal{U} \otimes \QQ_q$, $\mathfrak{S}=\mathcal{S} \otimes \QQ_q$
for the generic fibres, and $X=\mathcal{X} \otimes \FF_q$,
$U=\mathcal{U} \otimes \QQ_q$, $S=\mathcal{S} \otimes \FF_q$ for the special
fibres of $\mathcal{X},\mathcal{U}$, $\mathcal{S}$, respectively. Moreover,
we let $\FF_{\mathfrak{q}}/\FF_q$ denote a finite field extension and
denote $a=\log_p(\mathfrak{q})$.

\begin{thm} \label{thm:hypersurface}
For all $\tau \in S(\FF_{\mathfrak{q}})$, we have
\begin{equation} \label{eq:formulazeta}
Z(X_{\tau},T) = \frac{\chi(T)^{(-1)^n}}{(1 - T) (1 - \mathfrak{q}T) \dotsm (1 - \mathfrak{q}^{n-1}T)},
\end{equation}
where
$\chi(T) = \det \bigl( 1 - T \mathfrak{q}^{-1} \Frob_{\mathfrak{q}} | \Hrig^n(U_{\tau}) \bigr) \in \ZZ[T]$
denotes the reverse characteristic polynomial of the action of
$\mathfrak{q}^{-1} \Frob_{\mathfrak{q}}$ on $\Hrig^n(U_{\tau})$.
Moreover, the polynomial $\chi(T)$ has degree
\begin{equation} \label{eq:formulab}
\frac{1}{d} \bigl((d-1)^{n+1} + (-1)^{n+1}(d-1) \bigr).
\end{equation}
\end{thm}

\begin{proof}
This theorem is well known, see for example~\citep{AbbottKedlayaRoe2006}.
Since we need some intermediate results from the proof later on, we will
give a brief sketch here. First, by Theorem~\ref{thm:Lefschetz}, we have
\[
Z(X_{\tau},T) = \prod_{i=0}^{2(n-1)}
    \det\bigl(1- T \Frob_{\mathfrak{q}} | \Hrig^i(X_{\tau})\bigr)^{(-1)^{i+1}}.
\]
Then, by the Lefschetz hyperplane theorem and Poincar\'e duality, we see
that $\Hrig^i(X_{\tau}) \cong \Hrig^i(\mathbf{P}^n_{\FF_{\mathfrak{q}}})$
for all $i \neq (n-1)$. Next, one shows by a computation that
\begin{equation} \label{eqn:projcoho}
\Hrig^i(\mathbf{P}^n_{\FF_{\mathfrak{q}}})
\cong
\begin{cases}
\QQ_{\mathfrak{q}}(i) &\mbox{if $i$ even,} \\
$0$ &\mbox{if $i$ odd,}
\end{cases}
\end{equation}
where $(i)$ denotes the $i$-th Tate twist, for which $\Frob_p$ is multiplied
by $p^{-i}$. It remains to determine $\Hrig^{n-1}(X_{\tau})$. One uses the
excision short exact sequence
\begin{equation} \label{eqn:excision}
\begin{CD}
0 @>>> \Hrig^{n}(U_{\tau}) @>>> \Hrig^{n-1}(X_{\tau})(-1) @>>> \Hrig^{n+1}(\mathbf{P}^n_{\FF_{\mathfrak{q}}}) @>>> 0
\end{CD}
\end{equation}
to relate $\Hrig^{n-1}(X_{\tau})$ to $\Hrig^{n}(U_{\tau})$ and complete
the proof of~\eqref{eq:formulazeta}. We will show in Proposition~\ref{prop:rankcoho}
that the dimension of $\Hrig^{n-1}(U_{\tau})$ is given by~\eqref{eq:formulab}.
\end{proof}

Let $[e_1, \dotsc, e_b]$ be some basis of sections of
$\HdR^n(\mathfrak{U}/\mathfrak{S})$, and let $M \in M_{b \times b}(\QQ_q(t))$
denote the matrix of the Gauss--Manin connection $\nabla$ with respect
to this basis, i.e.
\[
\nabla (e_j) = \sum_{i=1}^b M_{i,j} e_i.
\]
Let $r \in \ZZ_q[t]$ with $\ord_p(r)=0$ be a denominator for $M$, i.e.\ such that we can write
$M = G/r$ with $G \in M_{b \times b}(\QQ_q[t])$, and let $\Phi$ denote the
matrix of $p^{-1}\Frob_p$ with respect to the basis $[e_1, \dotsc, e_b]$, i.e.\
\[
p^{-1} \Frob_p (e_j) = \sum_{i=1}^b \Phi_{i,j} e_i.
\]

\begin{defn}
We define the ring of overconvergent functions
\begin{align*}
\QQ_q \left\langle t, 1/r \right\rangle^{\dag} =
\Biggl\{\sum_{i,j=0}^{\infty} a_{i,j} \frac{t^i}{r^j} \; : \;
a_{i,j} \in \QQ_q, \; \exists c > 0 \text{ s.t.}
\lim_{i+j \rightarrow \infty} \bigl(\ord_p(a_{i,j}) - c(i+j)\bigr) \geq 0
\Biggr\},
\end{align*}
as the $p$-adically meromorphic functions on $\mathbf{P}^1_{\QQ_q}$ that are
analytic outside of the open disks of radius $\rho$ around the zeros of $r$
and the point at infinity for some $\rho<1$.
\end{defn}

\begin{defn}
We extend the $p$-adic valuation
to $\QQ_q \langle t, 1/r \rangle^{\dag}$ in the standard way, i.e.\
$\ord_p(f)$ is defined as the maximum, over all ways of writing the element $f$ as
$\sum_{i,j=0}^{\infty} a_{i,j} t^i / r^j$,
of the minimum, over $i,j \geq 0$, of $\ord_p(a_{i,j})$. Note that the
norm on $\QQ_q \langle t, 1/r \rangle^{\dag}$ corresponding to this valuation
is the Gauss norm. We also extend $\ord_p(-)$ to polynomials and matrices over
$\QQ_q \langle t, 1/r \rangle^{\dag}$, by taking the
minimum over the coefficients and entries, respectively.
\end{defn}

\begin{assump} \label{assump:S}
From now on we will always assume that $0 \in \mathcal{S}$.
Note that if this is not the case, then it can be achieved by
applying a translation.
\end{assump}

\begin{thm} \label{thm:eqphi}
The matrix $\Phi$ is an element of
$M_{b \times b}(\QQ_q \langle t, 1/r \rangle^{\dag})$
and satisfies the differential equation
\begin{align*}
\left(\frac{d}{dt} + M\right) \Phi &= p t^{p-1} \Phi \sigma(M), &\Phi(0)& = \Phi_0,
\end{align*}
where $\Phi_0$ is the
matrix of $p^{-1}\Frob_p$ on $\Hrig^n(U_0)$ with respect to the
basis $[e_0,\dotsc,e_b]$.
\end{thm}

\begin{proof}
That the differential equation is satisfied is an immediate consequence of the
fact that $\Frob_p$ is a horizontal map of vector bundles with connection, and
that $\Phi(0)=\Phi_0$ is also clear from Theorem~\ref{thm:frobstruc}. Note that
by a residue disk on $\mathcal{S}$ we mean all points on $\mathcal{S}(\bar{\QQ}_q)$
that reduce modulo $p$ to a given point of $S(\bar{\FF}_q)$.
If $M$ does not have any poles in a given residue disk, then $\Phi$ cannot have
any poles in that residue disk either, by Theorem~\ref{thm:KedlayaTuitman}
below. Hence the entries of $\Phi$ are contained in
$\QQ_q \langle t, 1/r \rangle^{\dag}$.
\end{proof}

The deformation method can now be sketched as follows:
\begin{enumerate}[\it Step 1.]
\item Compute the matrix $M$ of the Gauss--Manin connection $\nabla$.
\item Compute the matrix $\Phi_0$ of the action of $p^{-1}\Frob_p$ on
      $\Hrig^n(U_0)$. If the family is chosen such that $X_0$ is a diagonal
      hypersurface over a prime field, this can be done as
      explained in Chapter~\ref{sec:Diagonal}.
\item Solve the differential equation from Theorem~\ref{thm:eqphi} for $\Phi$.
\item Substitute the Teichm\"uller lift $\hat{\tau}$ of an element
      $\tau \in S(\FF_{\mathfrak{q}})$ into $\Phi$ to obtain the
      matrix $\Phi_{\tau}$ of the action of $p^{-1}\Frob_p$ on
      $\Hrig^n(U_{\tau})$. Compute the matrix $\Phi_{\tau}^{(a)}$
      of the action of $\mathfrak{q}^{-1} \Frob_{\mathfrak{q}}$
      on~$\Hrig^n(U_{\tau})$, which is also equal to $(p^{-1}\Frob_p)^a$.
      Use Theorem~\ref{thm:hypersurface} to compute the zeta function
      $Z(X_{\tau},T)$ of the fibre $X_{\tau}$.
\end{enumerate}

Note that we can only carry out these computations to finite $p$-adic
precision. Therefore, we need to recall some bounds on the loss of $p$-adic
precision when multiplying $p$-adic numbers and matrices.

\begin{prop} \label{prop:productval}
Let $v_1,\dotsc,v_{\ell} \in \ZZ$ and $x_1, \dotsc, x_{\ell} \in \mathbf{Q}_q$,
$\ell \geq 2$, be such that $\ord_p(x_i) \geq v_i$ for all $i$. Suppose that
$N \in \ZZ$ satisfies $N \geq \sum_{j=1}^{\ell} v_j$. Let
$\tilde{x}_1, \dotsc, \tilde{x}_{\ell}$ denote $p$-adic approximations to
$x_1, \dotsc, x_{\ell}$ such that
\[
\ord_p\left(x_i - \tilde{x}_i\right) \geq N - \sum_{j \neq i} v_j
\]
for all $i$.  Then
\begin{equation*}
\ord_p(x_1 \dotsm x_{\ell} - \tilde{x}_1 \dotsm \tilde{x}_{\ell}) \geq N.
\end{equation*}
\end{prop}

\begin{proof}
For all $i$,
\begin{align*}
\ord_p\left(\tilde{x}_i \right)
    & \geq \min \{ \ord_p\left(x_i-\tilde{x}_i\right), \ord_p(x_i) \} \\
    & \geq \min \biggl\{ N- \sum_{j \neq i} v_j, \ord_p(x_i)\biggr\} \geq v_i.
\end{align*}
Therefore, we also have that
\begin{equation*}
\ord_p \bigl( (x_{i}-\tilde{x}_{i})
    (\tilde{x}_1 \dotsm \tilde{x}_{i-1} x_{i+1} \dotsm x_{\ell}) \bigr) \geq N,
\end{equation*}
for all $i$. The result now follows by adding these $\ell$ inequalities.
\end{proof}

\begin{prop} \label{prop:matrixproductval}
Let $v_1,\dotsc,v_{\ell} \in \ZZ$ and
$A_1, \dotsc, A_{\ell} \in M_{b \times b}(\QQ_q)$, $\ell \geq 2$, be
such that $\ord_p(A_i) \geq v_i$ for all $i$. Suppose that $N \in \ZZ$
satisfies $N \geq \sum_{j=1}^{\ell} v_j$.
Let $\tilde{A}_1, \dotsc, \tilde{A}_{\ell}$ denote $p$-adic approximations
to $A_1, \dotsc A_{\ell}$ such that
\[
\ord_p\bigl(A_i - \tilde{A}_i\bigr) \geq N - \sum_{j \neq i} v_j
\]
for all $i$.  Then
\begin{equation}
\ord_p\bigl(A_1 \dotsm A_{\ell} - \tilde{A}_1 \dotsm \tilde{A}_{\ell}\bigr) \geq N.
\end{equation}
\end{prop}

\begin{proof}
We can follow the proof of Proposition~\ref{prop:productval},
observing that for matrices $A,B \in M_{b \times b}(\QQ_q)$, we still
have that $\ord_p(A + B) \geq \min \{\ord_p(A), \ord_p(B)\}$ and
$\ord_p(AB) \geq \ord_p(A)+\ord_p(B)$.
\end{proof}

\section{Computing the connection matrix}
\label{sec:Connection}

In this section we compute the action of the Gauss--Manin connection $\nabla$
on the algebraic de~Rham cohomology $\HdR^{n}(\mathfrak{U}/\mathfrak{S})$
of the generic fiber
$\mathfrak{U}/\mathfrak{S}=\mathcal{U}/\mathcal{S} \otimes \QQ_q$ of the
complement $\mathcal{U}/\mathcal{S}$ of a family of smooth hypersurfaces
$\mathcal{X}/\mathcal{S}$ contained in $\mathbf{P}^n_{\mathcal{S}}$ over
some Zariski open subset $\mathcal{S} \subset \mathbf{P}^1_{\ZZ_q}$. Let
$\mathcal{X}/\mathcal{S}$ be defined by a homogeneous polynomial
$P \in \ZZ_q[t][x_0,\dotsc,x_n]$ of degree $d$. First we recall how to
compute in $\HdR^{n}(\mathfrak{U}/\mathfrak{S})$ following the method
of Griffiths and Dwork.

\begin{prop} \label{prop:Omega}
Let $\Omega$ denote the $n$-form on $\mathfrak{U}/\mathfrak{S}$ defined by
\begin{align*}
\Omega = \sum_{i=0}^n (-1)^i x_i d x_0 \wedge \dotsb \wedge \widehat{d x_i} \wedge \dotsb \wedge d x_n.
\end{align*}
The algebraic de~Rham cohomology space $\HdR^{n}(\mathfrak{U}/\mathfrak{S})$
is isomorphic to the quotient of the space of closed $n$-forms
$Q \Omega / P^k$ with $k \in \NN$ and
$Q \in H^0(\mathfrak{S},\mathcal{O}_{\mathfrak{S}})[x_0, x_1, \dotsc, x_n]$
homogeneous of degree $k d - (n + 1)$, by the subspace of exact $n$-forms
generated by
\begin{equation*}
\frac{(\partial_i Q) \Omega}{P^k} - k \frac{Q (\partial_i P) \Omega}{P^{k+1}},
\end{equation*}
for all $0 \leq i \leq n$ with $k \in \NN$ and
$Q \in H^0(\mathfrak{S}, \mathcal{O}_{\mathfrak{S}})[x_0, x_1, \dotsc, x_n]$
homogeneous of degree $kd-n$, where $\partial_i$ denotes the partial
derivative operator with respect to~$x_i$.
\end{prop}

\begin{proof}
The proof is straightforward, for details see \citep[\S 4]{Griffiths1969}.
\end{proof}

The cohomology space $\HdR^{n}(\mathfrak{U}/\mathfrak{S})$ is
equipped with an increasing filtration by the pole order, for which
$\mbox{Fil}^k \HdR^{n}(\mathfrak{U}/\mathfrak{S})$ consists of all elements
that can be represented by $n$-forms $Q \Omega / P^k$ with
$Q \in H^0(\mathfrak{S},\mathcal{O}_{\mathfrak{S}})[x_0, x_1, \dotsc, x_n]$
homogeneous of degree $kd - (n + 1)$.  It follows from a theorem of
Macaulay~\citep[(4.11)]{Griffiths1969} that
$\mbox{Fil}^n \HdR^{n}(\mathfrak{U}/\mathfrak{S}) = \HdR^{n}(\mathfrak{U}/\mathfrak{S})$.
Actually, the reverse filtration $H_i=\mbox{Fil}^{n-i} \HdR^{n}(\mathfrak{U}/\mathfrak{S})$
corresponds to the restriction of the Hodge filtration on
$\HdR^{n-1}(\mathfrak{X}/\mathfrak{S})$ to $\HdR^{n}(\mathfrak{U}/\mathfrak{S})$
by~\citep[(8.6.)]{Griffiths1969}.

As we prefer to perform linear
algebra operations over a field, we will actually work with the de~Rham
cohomology vector space $\HdR^{n}\bigl(\mathfrak{U}_{\QQ_q(t)}\bigr)$ of
the generic fibre
\[
\mathfrak{U}_{\QQ_q(t)} = \mathfrak{U}/\mathfrak{S} \times_{\mathfrak{S}} \Spec \QQ_q(t).
\]
We now define an explicit basis of a simple form for
$\HdR^{n}\bigl(\mathfrak{U}_{\QQ_q(t)}\bigr)$
for the families that we are interested in.

\begin{defn} \label{defn:MonBasis}
For $k \in \NN$, we define the following sets of monomials:
\begin{align*}
F_k & = \{ x^u : u \in \mathbf{N}_{0}^{n+1}, \abs{u} = k d - (n+1) \}, \\
B_k & = \{ x^u : u \in \mathbf{N}_{0}^{n+1}, \abs{u} = k d - (n+1) \text{ and $u_i < d-1$ for all $i$}\}, \\
R_k & = F_k - B_k,
\end{align*}
where $x^u = x_0^{u_0} \dotsm x_n^{u_n}$ and $\abs{u}=\sum_{i=0}^n u_i$.
We also define
\begin{equation*}
\cB_k = \{Q \Omega / P^k : Q \in B_k\},
\end{equation*}
and write $B = B_1 \cup \dotsb \cup B_n$ and $\cB = \cB_1 \cup \dotsb \cup \cB_n$.
\end{defn}

We will show below that if the family $\mathcal{X}/{\mathcal{S}}$ contains
a diagonal fibre, then the set $\cB$ forms a basis for
$\HdR^n\bigl(\mathfrak{U}_{\QQ_q(t)}\bigr)$.

\begin{defn} \label{defn:IndexSets}
For $k \in \NN$, let $C_k^{(0)}$ be the set of monomials of total
degree $(k-1)d - n$ and then inductively, for $1 \leq j \leq n$, define
$C_k^{(j)}$ to be the set of monomials in $C_k^{(j-1)}$ except for those
divisible by $x_{j-1}^{d-1}$.  Moreover, we define the multi-set $C_k$ as
the disjoint union of $C_k^{(0)}, \dotsc, C_k^{(n)}$.  We shall write an
element of this multi-set as $(j, g)$, when referring to a monomial~$g$
in~$C_k^{(j)}$.
\end{defn}

\begin{lem} \label{lem:bijection}
For all $k \in \NN$, the multi-sets $R_k$ and $C_k$
have the same cardinality.
\end{lem}

\begin{proof}
We construct a bijection $R_k \to C_k$, representing the
monomials by their exponent tuples.  Let $u = (u_0, \dotsc, u_n)$ be an
element of $R_k$.  If $u_0 \geq d-1$, we define the image as
$(u_0-d-1, u_1, \dotsc, u_n) \in C_k^{(0)}$.  More generally, if
$u_0 < d-1, \dotsc, u_{j-1} < d-1$ and $u_j \geq d-1$, we define the image as
$(u_0, \dotsc, u_{j-1}, u_j-(d-1), u_{j+1}, \dotsc, u_n) \in C_k^{(j)}$.
It is easy to verify that this map is indeed a bijection.
\end{proof}

\begin{defn} \label{defn:Deltak}
We define a square matrix $\Delta_k$ with
row and column index sets $R_k$ and $C_k$ as follows.
Given $f \in R_k$ and $(j,g) \in C_k$, we set the corresponding entry in
$\Delta_k$ to be the coefficient of the monomial $f/g$ in $\partial_j P$ if
$g$ divides $f$ and $0$ otherwise.
\end{defn}

\begin{thm} \label{thm:Isomorphism}
Suppose that the family $\mathcal{X}/\mathcal{S}$ of smooth projective
hypersurfaces given by the polynomial~$P$ in $\ZZ_q[t][x_0, \dotsc, x_n]$ contains
a diagonal fibre.  For $k \in \NN$ and $0 \leq j \leq n$, let $U_k^{(j)}$ be
the $\QQ_q(t)$-vector space of polynomials with basis $C_k^{(j)}$, and let $U_k$
denote the cartesian product $U_k = U_k^{(0)} \times \dotsb \times U_k^{(n)}$.
Moreover, let $V_k$ and $W_k$ be the $\QQ_q(t)$-vector spaces of polynomials with
bases $F_k$ and $R_k$, respectively, and let $\pi \colon V_k \rightarrow W_k$
denote the linear map that sends the elements of $B_k$ to zero and the
elements of $R_k$ to themselves.
Then the map
\begin{align}
\phi_k \colon U_k &\to W_k,
&(Q_0, \dotsc, Q_n) &\mapsto \pi \bigl( Q_0 \partial_0 P + \dotsb + Q_n \partial_n P \bigr)
\end{align}
is an isomorphism of $\QQ_q(t)$-vector spaces.
\end{thm}

\begin{proof}
Recall that $R_k$ and $C_k$ have the same cardinality by Lemma~\ref{lem:bijection}.
If $R_k$ and $C_k$ are empty, then $U_k$ and $W_k$ are the zero vector spaces,
and the theorem holds trivially. So suppose that $R_k$ and $C_k$ are nonempty.
It is immediate that $\Delta_k$ is the matrix
representing $\phi_k$ with respect to the bases $C_k$ and $R_k$ of $U_k$ and $W_k$,
respectively.

The assumption that the family~$\mathcal{X}/\mathcal{S}$ contains a diagonal
hypersurface means that for some~$t_0 \in \mathcal{S}(\ZZ_q)$,
the fibre $\mathcal{X}_{t_0}$ is defined by a polynomial of the form
\begin{equation*}
P_{t_0}(x_0, \dotsc, x_n) = a_0 x_0^d + \dotsb + a_n x_n^d
\end{equation*}
with $a_0, \dotsc, a_n \in \ZZ_q^{\times}$.

We now show that the determinant of $\Delta_k$ is nonzero.  Since
evaluation of the matrix at \mbox{$t = t_0$} commutes with computing the
determinant, it suffices to show that the determinant of
$(\Delta_k) \big |_{t=t_0}$ is nonzero. Since, for $0 \leq j \leq n$,
we have $\partial_j P_{t_0} (x_0, \dotsc, x_n) = d a_j x_j^{d-1}$, there is
precisely one nonzero entry in each column and each row of~$\Delta_k$.
Namely, in column $(j, g) \in C_k$ and row $g x_j^{d-1} \in R_k$ there is
the nonzero entry $d a_j$. Note that this also implies that
$(\Delta_k) \big |_{t=t_0} \in \ZZ_{q}^{\times}$.
\end{proof}

We can use Theorem~\ref{thm:Isomorphism} to give a routine {\sc Decompose},
formalised in Algorithm~\ref{alg:Decompose}, which given
$Q \in \QQ_q(t)[x_0, \dotsc, x_n]$ homogeneous of degree $kd - (n+1)$
returns an expression
\begin{equation*}
Q = Q_0 \partial_0 P + \dotsb + Q_n \partial_n P + \gamma_k
\end{equation*}
with $Q_0, \dotsc, Q_n \in \QQ_q(t)[x_0, \dotsc, x_n]$ homogeneous of
degree $kd-n$ and $\gamma_k$ in the $\QQ_q(t)$-span of~$B_k$. We can in turn
use {\sc Decompose} to furnish another routine {\sc Reduce}, formalised
in Algorithm~\ref{alg:PoleRed}, which given a closed $n$-form $Q\Omega/P^k$
with $Q \in \QQ_q(t)[x_0, \dotsc, x_n]$ homogeneous of degree $kd - (n+1)$ returns
an expression
\begin{equation*}
\frac{Q \Omega}{P^k} \equiv \frac{\gamma_{1} \Omega}{P^{1}}
                            + \dotsb + \frac{\gamma_n \Omega}{P^n},
\end{equation*}
with $\gamma_i$ in the $\QQ_q(t)$-span of $B_i$ for $1 \leq i \leq n$ and
where $\equiv$ denotes equality in cohomology.

\begin{algorithm}
\caption{Obtain coordinates in the Jacobian ideal modulo basis elements}
\label{alg:Decompose}
\begin{algorithmic}
\Require $P$ in $\ZZ_q[t][x_0, \dotsc, x_n]$ homogeneous of degree~$d$,
         defining a family $\mathcal{X}/\mathcal{S}$ of smooth projective
         hypersurfaces that contains a diagonal fibre,
         $Q \in \QQ_q(t)[x_0, \dotsc, x_n]$ homogeneous of degree $kd - (n+1)$.
\Ensure  $Q_0, \dotsc, Q_n \in \QQ_q(t)[x_0, \dotsc, x_n]$ homogeneous of degree
         $k(d-1)-n$, and $\gamma_k$ in the $\QQ_q(t)$-span of $B_k$, such that
         $Q = Q_0 \partial P_0 + \dotsb + Q_n \partial_n P +\gamma_k$.
\Procedure{Decompose}{$P,Q$}
\State \begin{compactenum}[{\hspace{1em}} 1.] \vspace{-1.24em}
\item Let $w$ be the vector of length $\abs{R_k}$ such that the entry
      corresponding to $x^u \in R_k$ is the coefficient of
      $x^u$ in $Q$.
\item Solve for the unique vector $v$ of length $\abs{C_k}$ satisfying
      $\Delta_k v = w$.  We write $v$
      as $\bigl(v^{(0)}, \dotsc, v^{(n)}\bigr)$, where $v^{(j)}$ is
      a vector of length $\abs{C_k^{(j)}}$ for $0 \leq j \leq n$,
      and let $v_g^{(j)}$ be the entry in $v^{(j)}$ corresponding
      to $g \in C_k^{(j)}$.
\item For $0 \leq j \leq n$, compute $Q_j \gets \sum_{g \in C_k^{(j)}} v_g^{(j)} g$.
\item Set $\gamma_k \gets Q-(Q_0 \partial P_0 + \dotsb + Q_n \partial_n P)$.
\item \textbf{return} $Q_0, \dotsc, Q_n,\gamma_k$
\EndProcedure
\end{compactenum}
\end{algorithmic}
\end{algorithm}

\begin{algorithm}
\caption{Reduce $Q \Omega / P^k$ in $\HdR^n\bigl(\mathfrak{U}_{\QQ_q(t)}\bigr)$}
\label{alg:PoleRed}
\begin{algorithmic}
\vspace{1mm}
\Require $P$ in $\ZZ_q[t][x_0, \dotsc, x_n]$ homogeneous of degree~$d$,
         defining a family $\mathcal{X}/\mathcal{S}$ of smooth projective
         hypersurfaces that contains a diagonal fibre, $Q \in \QQ_q(t)[x_0, \dotsc, x_n]$
         homogeneous of degree $kd - (n+1)$.
\Ensure  $\gamma_i$ in the $\QQ_q(t)$-span of $B_i$ for $1 \leq i \leq n$, with
         $Q \Omega / P^k \equiv \gamma_{1} \Omega / P^{1} + \dotsb + \gamma_n \Omega / P^n$.
\Procedure{Reduce}{$P,Q$}
\While{$k \geq n+1$}
\State $Q_0, \dotsc, Q_n, 0 \gets \Call{Decompose}{Q}$
\State $k \gets k-1$
\State $Q \gets k^{-1} \sum_{i=0}^n \partial_i Q_i$
\EndWhile
\While{$Q \not \in \QQ_q(t)$-span of $B_k$}
\State $Q_0, \dotsc, Q_n, \gamma_k \gets \Call{Decompose}{Q}$
\State $k \gets k-1$
\State $Q \gets k^{-1} \sum_{i=0}^n \partial_i Q_i$
\EndWhile
\If{$Q \neq 0$}
\State $\gamma_{k} \gets Q$
\State $k \gets k-1$
\EndIf
\State $\gamma_{1}, \dotsc, \gamma_{k} \gets 0$
\State \textbf{return} $\gamma_{1}, \dotsc, \gamma_n$
\EndProcedure
\end{algorithmic}
\end{algorithm}

We now establish that the set~$\cB$ indeed forms a basis for
$\HdR^n\bigl(\mathfrak{U}_{\QQ_q(t)}\bigr)$, as announced before.
We start with an auxiliary result describing the cardinality of
the set~$\cB$.

\begin{prop} \label{prop:BasisSize}
The set $\cB$ has cardinality
\begin{equation*}
\frac{1}{d} \left((d-1)^{n+1} + (-1)^{n+1}(d-1) \right).
\end{equation*}
\end{prop}

\begin{proof}
First note that if we denote
\begin{align*}
V   &= \Bigl\{(u_0,\dotsc,u_n) \in (\ZZ/d\ZZ)^{n+1} : \sum_{j=0}^n u_j = -(n+1) \Bigr\}, \\
W_j &= \Bigl\{(u_0,\dotsc,u_n) \in (\ZZ/d\ZZ)^{n+1} : u_j = -1 \Bigr\},
\end{align*}
then  $\cB$ is in one-to-one correspondence with the set $V-(W_0 \cup \dotsb \cup W_n)$.
Now by the inclusion-exclusion principle,
\begin{align*}
\abs{V \cap (W_0 \cup \dotsb \cup W_n)}
& = \sum_{j=0}^n \abs{V \cap W_j}
    - \sum_{0 \leq j < k \leq n} \abs{V \cap W_j \cap W_k} \\
& \quad + \dotsb + (-1)^{n} \abs{V \cap W_0 \cap \dotsb \cap W_n} \\
& = {n+1 \choose 1} d^{n-1} -{n+1 \choose 2} d^{n-2}
    + \dotsb + (-1)^{n-1} {n+1 \choose n} + (-1)^{n} \\
& = \frac{1}{d} \left(d^{n+1}+(-1)^{n+1} - (d-1)^{n+1}\right)+(-1)^n,
\end{align*}
so that
\begin{align*}
\abs{V-(W_0 \cup \dotsb \cup W_n)}&=\abs{V}-\abs{V \cap (W_0 \cup \dotsb \cup W_n)} \\
&= d^n - \frac{1}{d} \bigl(d^{n+1}+(-1)^{n+1} - (d-1)^{n+1}+d (-1)^n \bigr) \\
&= \frac{1}{d} \left((d-1)^{n+1} + (-1)^{n+1}(d-1) \right),
\end{align*}
and the proof is complete.
\end{proof}

\begin{prop} \label{prop:rankcoho}
The rank of $\HdR^n(\mathfrak{U}/\mathfrak{S})$ is
\[
\frac{1}{d} \left((d-1)^{n+1} + (-1)^{n+1}(d-1) \right).
\]
\end{prop}

\begin{proof}
Let $\mathfrak{U}_m/\mathfrak{S}$ denote the complement of a family
$\mathfrak{X}_m/\mathfrak{S}$ of smooth projective hypersurfaces of
degree~$d$ in $\mathbf{P}^m_{\mathfrak{S}}$ and let $b(d,m)$ denote
the rank of $\HdR^m(\mathfrak{U}_m/\mathfrak{S})$. It is known that
$b(d,m)$ only depends on $d$, $m$. Moreover, taking $x=y=z$
in~\citep[Corollaire~2.4~(i)]{sga7}, we find that
\[
\sum_{m=1}^{\infty} b(d,m) x^{m-1}
  = \frac{(d-1)}{(1+x)(1-(d-1)x)}
  = \frac{1}{xd} \left( \frac{d-1}{1-(d-1)x} - \frac{d-1}{1+x} \right)
\]
as formal power series. From this the result follows easily.
\end{proof}

\begin{thm} \label{thm:Basis}
Suppose that the family of smooth projective hypersurfaces
$\mathcal{X}/\mathcal{S}$ contains a diagonal fibre.  Then the
set~$\cB$ from Definition~\ref{defn:MonBasis} is a basis for
the $\QQ_q(t)$-vector space $\HdR^n\bigl(\mathfrak{U}_{\QQ_q(t)}\bigr)$.
\end{thm}

\begin{proof}
We already know that $\HdR^n\bigl(\mathfrak{U}_{\QQ_q(t)}\bigr)$ is
spanned by the classes of the $n$-forms $Q \Omega / P^k$ with
$Q \in \QQ_q(t)[x_0, \dotsc, x_n]$ homogeneous of degree
$kd - (n+1)$ for $k \in \NN$. Applying Algorithm~\ref{alg:PoleRed}, we
obtain an expression for the class of $Q \Omega / P^k$ as a
$\QQ_q(t)$-linear combination of elements in $\cB$.  This shows that
$\cB$ spans the vector space $\HdR^n\bigl(\mathfrak{U}_{\QQ_q(t)}\bigr)$.
However, by the two propositions above, the dimension of
$\HdR^n\bigl(\mathfrak{U}_{\QQ_q(t)}\bigr)$ is equal to the cardinality of
$\cB$, so that $\cB$ is linearly independent as well.
\end{proof}

\begin{rem} \label{rem:hnumbers}
Let $H_i$ denote the restriction of the Hodge filtration on
$\HdR^{n-1}(\mathfrak{X}/\mathfrak{S})$ to $\HdR^{n}(\mathfrak{U}/\mathfrak{S})$
and write
\[
h^{i,n-1-i}=\mbox{rank}(H_i/H_{i+1})
\]
for the corresponding Hodge numbers.
Recall that $H_i=\mbox{Fil}^{n-i} \HdR^{n}(\mathfrak{U}/\mathfrak{S})$
for the filtration by the pole order defined above. Applying
the loop in Algorithm~\ref{alg:PoleRed} just once, to lower the pole
order from $k$ to $k-1$, we see that $\cB_k$ spans
\[
\mbox{Fil}^{k} \HdR^{n}\bigl(\mathfrak{U}_{\QQ_q(t)}\bigr) / \mbox{Fil}^{k-1} \HdR^{n}\bigl(\mathfrak{U}_{\QQ_q(t)}\bigr)
\]
for all $1 \leq k \leq n$. Hence it follows that $\card{B_k} \geq h^{n-k,k-1}$ , but since
\[
\sum_{k=1}^n \card{B_k} = \dim \HdR^n\bigl(\mathfrak{U}_{\QQ_q(t)}\bigr) = \sum_{k=1}^n h^{n-k,k-1},
\]
this implies that $\card{B_k} = h^{n-k,k-1}$ for all $1 \leq k \leq n$. So the Hodge numbers
can be read off from the basis $\cB$.
\end{rem}

We now describe the action of the Gauss--Manin connection~$\nabla$ on
$\HdR^n\bigl(\mathfrak{U}_{\QQ_q(t)}\bigr)$.  Suppose that we are given a basis element
$x^u \Omega / P^k \in \cB_k$.  Following the description in
Section~\ref{sec:Background}, we compute
\begin{equation} \label{eqn:nabla}
\nabla \left(\frac{x^u \Omega}{P^k}\right) \equiv
    dt \otimes \frac{- k x^u (\partial P / \partial t) \Omega}{P^{k+1}},
\end{equation}
where $\equiv$ denotes equality in
$\Omega_{\QQ_q(t)} \otimes \HdR^n\bigl(\mathfrak{U}_{\QQ_q(t)}\bigr)$.
We apply Algorithm~\ref{alg:PoleRed} in order to write
\begin{equation}
dt \otimes \frac{- k x^u (\partial P / \partial t) \Omega}{P^{k+1}} \equiv
dt \otimes \left( \frac{\gamma_{1}}{P} + \dotsb + \frac{\gamma_n}{P^n} \right) \Omega,
\end{equation}
where $\gamma_i$ is an element in the $\QQ_q(t)$-span of~$B_i$ for $1 \leq i \leq n$.

\begin{rem} \label{rem:precgm}
For the matrix $M$ of $\nabla$ to be correct to $p$-adic precision $N_M$, we have to
carry out this computation to a somewhat higher working precision $N'_M$ due to the
precision loss in Algorithm~\ref{alg:PoleRed}.
For all $k \in \NN$, by definition $\ord_p(\Delta_k) \geq 0$, and from the proof
of Theorem~\ref{thm:Isomorphism} we know that $\ord_p(\det(\Delta_k))=0$.
Therefore, there is no precision loss
in Algorithm~\ref{alg:Decompose}, and the only precision loss in Algorithm~\ref{alg:PoleRed}
comes from dividing by $k-1$ for $k=2,\dotsc,n+1$. Hence it is sufficient to take
\begin{equation*}
N_M'=N_M + \ord_p(n!).
\end{equation*}
\end{rem}
This is formalised in Algorithm~\ref{alg:Connection}.

\begin{algorithm}
\caption{Compute the Gauss--Manin connection matrix}
\label{alg:Connection}
\begin{algorithmic}
\Require $P$ in $\ZZ_q[t][x_0, \dotsc, x_n]$ homogeneous of degree~$d$,
         defining a family $\mathfrak{X}/\mathfrak{S}$ of smooth projective
         hypersurfaces that contains a diagonal fibre, $p$-adic precision $N_M$.
\Ensure  The matrix~$M$ of $\nabla$ with respect to $\cB$ to $p$-adic precision $N_M$.
\Procedure{GMConnection}{$P,N_M$}
\State $N'_M \gets N_M + \ord_p(n!)$
\State \textit{Execute the following steps with $p$-adic working precision $N'_M$}:
\For{$g \in B$}
\State $k \gets  \bigl(\deg(g)+(n+1)\bigr)/d$
\State $Q \gets  - k g (\partial P / \partial t)$
\State $\gamma_{1}, \dotsc, \gamma_n \gets$ {\sc Reduce($P,Q$)}
\For{$f \in B$}
\State $l \gets \bigl(\deg(f)+(n+1)\bigr)/d$
\State $M_{f,g} \gets$ coefficient of $f$ in $\gamma_l$
\EndFor
\EndFor
\Return $M$
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{defn} \label{defn:resultant}
We define the polynomial $R \in \ZZ_q[t]$ by
\[
R = \prod_{k=2}^{n+1}  \det(\Delta_k).
\]
\end{defn}

\begin{prop} \label{thm:denom}
The matrix $M$ of $\nabla$ with respect to $\cB$ is of the form
$H/R$, with $H \in M_{b \times b}(\QQ_q[t])$.
\end{prop}

\begin{proof}
The only time in Algorithm~\ref{alg:Connection} that nonconstant denominators
are introduced is when the subroutine {\sc{Reduce}} calls its subroutine
{\sc{Decompose}} and a linear system $\Delta_k v = w$ is solved. Since this
happens only for $k=2, \dotsc, n+1$ and at most once for each
such~$k$, the result is clear.
\end{proof}

\begin{rem}
Recall that $\cB$ is a basis for $\HdR^n\bigl(\mathfrak{U}_{\QQ_q(t)}\bigr)$
but not necessarily for $\HdR^n(\mathfrak{U}/\mathfrak{S})$. However, if the
zero locus of $R$ in $\mathbf{P}^1_{\ZZ_q}$ does not intersect $\mathcal{S}$,
then $\cB$ is a basis for $\HdR^n(\mathfrak{U}/\mathfrak{S})$. That it
spans the cohomology can be seen by applying Algorithm~\ref{alg:PoleRed}, and that it
is linearly independent follows because it is so over $\QQ_q(t)$. Therefore, it will
be convenient to choose $\mathcal{S}$ smaller, so that this condition is satisfied.
\end{rem}

\begin{assump} \label{assump:R}
From now on we assume that the zero locus of~$R$ in~$\mathbf{P}^1_{\ZZ_q}$
does not intersect $\mathcal{S}$. In particular, this implies that $\cB$ is
a basis for $\HdR^n(\mathfrak{U}/\mathfrak{S})$.
\end{assump}

\begin{rem}
Note that in Algorithm~\ref{alg:Connection}, we solve $\BigOh(\card{\cB})$~linear
systems given by the matrices $\Delta_k$ for $k = 2, \dotsc, n+1$.  In practice,
it is important to take advantage of this, e.g.\ by computing the decomposition
$\Delta_k = LUP$, where $L$ is lower triangular, $U$ is upper triangular, and
$P$ is a permutation matrix, which is guaranteed to exist for any square matrix.
Since, moreover, the matrices~$\Delta_k$ contain many zeros, methods from sparse
linear algebra can be used to compute such a decomposition.  Then, every call to
{\sc{Decompose}} reduces to solving a lower and an upper diagonal linear system.
\end{rem}

In the rest of this section we will freely use the definitions and notation
from Section~\ref{sec:Background}. We let all of our matrices be defined with
respect to the basis $\cB$. We have seen that there exists a Frobenius
structure $\Frob_p$ on $\HdR^n(\mathfrak{U}/\mathfrak{S})$ and let
$\Phi \in M_{b \times b}(\QQ_q \langle t, 1/r \rangle^{\dag})$
denote the matrix of the action of $p^{-1}\Frob_p$, where $r$ is the
denominator of the connection matrix $M$. Recall that
$\FF_{\mathfrak{q}}/\FF_q$
denotes a finite field extension.

We need a priori lower bounds on the $p$-adic valuations of the matrices
$\Phi$ and $\Phi^{-1}$ to bound the loss of $p$-adic precision in our
computations. We will now recall how such bounds can be obtained
following~\citep{AbbottKedlayaRoe2006}.

\begin{thm} \label{thm:deltabound}
For any finite field extension $\FF_{\mathfrak{q}}/\FF_q$ and
all $\tau \in S(\FF_{\mathfrak{q}})$,
there exists a matrix $W_{\tau} \in M_{b \times b}(\QQ_{\mathfrak{q}})$ such that
\begin{align*}
\ord_p(W_{\tau}) &\geq -\sum_{i=1}^{n-1} \floor{\log_p(i)},
&\ord_p\bigl(W_{\tau} \Phi_{\tau} \sigma(W_{\tau}^{-1})\bigr) &\geq  0, \\
\ord_p(W_{\tau}^{-1}) &\geq -\ord_p \bigl((n-1)! \bigr),
&\ord_p\bigl(W_{\tau} \Phi_{\tau}^{-1} \sigma(W_{\tau}^{-1})\bigr) &\geq  -(n-1).
\end{align*}
\end{thm}

\begin{proof}
Let $\Lambda_{\tau, crys}$ be the image of the integral logarithmic de Rham
cohomology space
$\HdR^n\bigl(\mathbf{P}_{\mathbf{Z}_{\mathfrak{q}}}^n,\mathcal{X}_{\hat{\tau}}\bigr)$
in the rigid cohomology space $\Hrig^n(U_{\tau})$. It is known that
$\Lambda_{\tau, crys} \otimes \QQ_{\mathfrak{q}} \cong \Hrig^n(U_{\tau})$,
so that $\Lambda_{\tau, crys}$ is a lattice in $\Hrig^n(U_{\tau})$.  Let
$\Lambda_{\tau, mon}$ be the $\ZZ_{\mathfrak{q}}$-module in $\Hrig^n(U_{\tau})$
generated by the classes of $x^u \Omega/P^n$ with $u \in \NN_0^{n+1}$ such that
$\sum_{i=0}^n u_i = nd-(n+1)$. Since these classes generate $\Hrig^n(U_{\tau})$, we have
that $\Lambda_{\tau,mon}$ is a lattice in $\Hrig^n(U_{\tau})$ as well. We know
that
\[
\Lambda_{\tau,crys} \subset \Lambda_{\tau,mon} \subset p^{-\sum_{i=1}^{n-1} \floor{\log_p(i)}} \Lambda_{\tau,crys}.
\]
The inclusion on the left is \citep[Lemma 3.4.3]{AbbottKedlayaRoe2006}, and the
one on the right is \citep[Proposition 3.4.6]{AbbottKedlayaRoe2006}.

Let $\Lambda_{\tau,\cB}$ be the $\ZZ_{\mathfrak{q}}$-module in $\Hrig^n(U_{\tau})$
generated by the basis $\cB$. Since $\cB$ spans $\Hrig^n(U_{\tau})$, we have that
$\Lambda_{\tau,\cB}$ is also a lattice in $\Hrig^n(U_{\tau})$. Now we know that
\[
(n-1)! \Lambda_{\tau,mon} \subset \Lambda_{\tau,\cB} \subset \Lambda_{\tau,mon}.
\]
The inclusion on the left follows by explicitly reducing the generators of
$\Lambda_{\tau,mon}$ to the basis $\cB$ with Algorithm~\ref{alg:PoleRed} using
that $R(\hat{\tau}) \in \ZZ_{\mathfrak{q}}^{\times}$, and the inclusion on the right is clear.

Combining these inclusions of lattices, we find that
\begin{equation} \label{eq:lattices}
(n-1)! \Lambda_{\tau,crys} \subset \Lambda_{\tau,\cB} \subset p^{-\sum_{i=1}^{n-1} \floor{\log_p(i)}} \Lambda_{\tau,crys}.
\end{equation}
Now let $[d_1, \dotsc, d_b]$ be a $\ZZ_{\mathfrak{q}}$-basis for
$\Lambda_{\tau,crys}$ and let $W_{\tau} \in M_{b \times b}(\QQ_q)$ be
the matrix in which the $i$-th column
consists of the coordinates of $d_i$ with respect to the basis~$\cB$. From the
inclusions~\eqref{eq:lattices} it is clear that
\begin{eqnarray*}
\ord_p(W_{\tau}) &\geq& -\sum_{i=1}^{n-1} \floor{\log_p(i)}, \\
\ord_p(W_{\tau}^{-1}) &\geq& -\ord_p((n-1)!).
\end{eqnarray*}
Note that $W_{\tau} \Phi_{\tau} \sigma(W_{\tau}^{-1})$ is the matrix of
$p^{-1}\Frob_{p}$ on $\Hrig^n(U_{\tau})$ with respect to the basis
$[d_1,\dotsc,d_b]$. Now $\Lambda_{\tau,crys}$ is contained in the crystalline
cohomology space $H^{n-1}_{crys}(X_{\tau})$, which maps to itself
under~$\Frob_p$. So by the short exact sequence~\eqref{eqn:excision}, the
lattice $\Lambda_{\tau,crys}$ maps to itself under $p^{-1}\Frob_{p}$, and
\[
\ord_p(W_{\tau} \Phi_{\tau} \sigma(W_{\tau}^{-1})) \geq 0.
\]
Similarly, note that $W_{\tau} \Phi_{\tau}^{-1} \sigma(W_{\tau}^{-1})$ is
the matrix of $p\Frob_p^{-1}$ on $\Hrig^n(U_{\tau})$ with respect to the
basis $[d_1,\dotsc,d_b]$. By Poincar\'e duality, the map $p^{n-1}\Frob_p^{-1}$
maps the crystalline cohomology space $H^{n-1}_{crys}(X_{\tau})$ to itself.
So by the short exact sequence~\eqref{eqn:excision}, the lattice
$\Lambda_{\tau,crys}$ maps to itself under $p^{n-1} (p\Frob_p^{-1})$, and
\begin{equation*}
\ord_p(W_{\tau} \Phi_{\tau}^{-1} \sigma(W_{\tau}^{-1})) \geq -(n-1). \qedhere
\end{equation*}
\end{proof}

\begin{defn} \label{defn:delta}
Define the nonnegative integer
\[
\delta = \ord_p((n-1)!)+\sum_{i=1}^{n-1} \floor{\log_p(i)}.
\]
\end{defn}

\begin{cor} \label{cor:delta} We have
\begin{align*}
\ord_p(\Phi) &\geq -\delta, \\
\ord_p(\Phi^{-1}) &\geq -\delta-(n-1).
\end{align*}
\end{cor}

\begin{proof}
For every $\tau \in \mathcal{S}(\bar{\FF}_{\mathfrak{q}})$,
we can apply Theorem~\ref{thm:deltabound}
to obtain
\begin{align*}
\ord_p(\Phi_{\tau}) &\geq \ord_p(W^{-1}_{\tau}) +
                          \ord_p(W_{\tau} \Phi_{\tau} \sigma(W_{\tau}^{-1})) +
                          \ord_p(\sigma(W_{\tau})) \\
                    &\geq -\delta,
\end{align*}
and also
\begin{align*}
\ord_p(\Phi^{-1}_{\tau}) &\geq \ord_p(W^{-1}_{\tau}) +
                               \ord_p(W_{\tau} \Phi^{-1}_{\tau} \sigma(W_{\tau}^{-1})) +
                               \ord_p(\sigma(W_{\tau})) \\
                         &\geq -\delta - (n-1).
\end{align*}
As these inequalities hold for infinitely many~$\tau \in S(\bar{\FF}_q)$
we obtain the required bounds.
\end{proof}

\section{Frobenius on diagonal hypersurfaces}
\label{sec:Diagonal}

\subsection{A formula for $\Phi_0$}

We consider a single smooth
projective diagonal hypersurface~$\mathcal{X}_0$ over $\ZZ_p$ defined by
a polynomial $P_0 \in \ZZ_p[x_0, \dotsc, x_n]$ of the form
\begin{equation*}
P_0(x_0, x_1, \dotsc, x_n) =
    a_0 x_0^d + a_1 x_1^d + \dotsb + a_n x_n^d,
\end{equation*}
where $a_0, a_1, \dotsc, a_n \in \ZZ_p^{\times}$ and $p \nmid d$.
Let $\mathfrak{X}_0 = \mathcal{X}_0 \otimes_{\ZZ_p} \QQ_p$ denote the generic
fibre of $\mathcal{X}_0$ and let $\mathcal{U}_0$ and $\mathfrak{U}_0$ be the
complements of $\mathcal{X}_0$ and $\mathfrak{X}_0$, respectively.
We fix our choice of basis~$\cB$ for $\HdR^{n}(\mathfrak{U}_0)$
as in Definition~\ref{defn:MonBasis}.
Our goal is to compute
the matrix~$\Phi_0$ representing the action of $p^{-1} \Frob_p$ on
$\Hrig^n(U_0) \cong \HdR^n(\mathfrak{U}_0)$, with respect to the basis~$\cB$,
to $p$-adic precision~$N_{\Phi_0}$. It will turn out that this matrix has only one
nonzero element in every row and column.

Let $u = (u_0, \dotsc, u_n)$ and $v = (v_0, \dotsc, v_n)$ be tuples
of integers such that $x^u, x^v \in B$ and $p (u_i+1) \equiv v_i+1 \bmod{d}$,
for all $i$. Furthermore, let $k(u) \in \NN$ denote the positive integer such that
\[
k(u) d -(n+1) = \sum_{i=0}^n u_i.
\]
Finally, for all $l \in \QQ$ and integers $r \geq 0$, let the rising factorial $\prod_{j=0}^{r-1} (l + j)$ be
denoted by $(l)_r$.

\begin{defn} \label{defn:alpha}
Let $u, v \in \ZZ^{n+1}$ be such that we have
$x^u, x^v \in B$ and
$p (u_i + 1) \equiv v_i + 1 \bmod{d}$ for all~$i$.
We define
\begin{equation*}
\alpha_{u,v} = \prod_{i=0}^n a_i^{(p (u_i + 1) - (v_i + 1))/d}
    \biggl( \sum_{m,r} \left( \frac{u_i+1}{d} \right)_r
        \sum_{j=0}^{r} \frac{\bigl(p a_i^{p-1}\bigr)^{r-j}}{(m-pj)!j!} \biggr),
\end{equation*}
where the sum in the $i$-th factor of the product is over all integers $m, r \geq 0$
that satisfy $p(u_i+1)-(v_i+1)=d(m-pr)$.
\end{defn}

The following lemma will be useful in what follows.

\begin{lem} \label{lem:mpr}
Let $x^u, x^v \in B$, $0 \leq i \leq n$ and $m, r \geq 0$ integers, such that
\[
p(u_i + 1) - (v_i + 1) = d(m-pr).
\]
Then we have $r = \floor{m/p}$.
\end{lem}

\begin{proof}
Since $0 \leq u_i, v_i \leq d-2$, we obtain
\[
p-(d-1) \leq p(u_i + 1) - (v_i + 1) \leq p(d-1)-1,
\]
and from this the result follows, also using that $m - pr \in \ZZ$.
\end{proof}

The entries of $\Phi_0$ can be expressed in terms of the $\alpha_{u,v}$ in the following way.

\begin{thm} \label{thm:01-03-diagfrob}
Let $\omega_1$ denote an element of $\cB$ corresponding to a tuple
$u \in \ZZ^{n+1}$ and let $\omega_2$ denote the unique element of~$\cB$
corresponding to a tuple $v \in \ZZ^{n+1}$ such that
$p (u_i + 1) \equiv v_i + 1 \bmod{d}$ for all $i$. Then
\begin{equation} \label{eq:diagfrobformula}
p^{-1} \Frob_p (\omega_1) =
    (-1)^{k(v)} \frac{(k(v) - 1)!}{(k(u) - 1)!} p^{n-k(u)} \alpha_{u,v}^{-1} \cdot \omega_2.
\end{equation}
\end{thm}

\begin{proof} We start with some definitions.
First, let $\QQ_p(\pi)$ denote the totally ramified extension of $\QQ_p$ with $\pi^{p-1} = -p$
and extend the $p$-adic valuation such that \mbox{$\ord_p(\pi) = (p-1)^{-1}$}. For $0 \leq i \leq n$,
define sets
\begin{align*}
W^{(i)} &= \{ (w_0,\cdots,w_n) \in \NN_0^{n+1} \colon w_j \geq 1 \text{ for all } j \neq i \text{ and } \lvert w \rvert \equiv 0 \bmod{d} \},
\end{align*}
with $\lvert w \rvert=\sum_{i=0}^n w_i$. Note that $\lvert w \rvert=k(w-1)$,
where $w-1$ denotes the tuple $(w_0-1,\ldots,w_n-1)$.  Furthermore, still
for $0 \leq i \leq n$, define $\QQ_p(\pi)$-vector spaces
\begin{align*}
\mathcal{L}^{(i)} &= \Bigl\{ \sum_{w \in W^{(i)}} b_w x^{w} \; : \;
b_{w} \in \QQ_p(\pi), \; \exists c > 0 \text{ s.t.}
\lim_{\lvert w \rvert \rightarrow \infty} \bigl(\ord_p(b_w) - c \cdot \lvert w \rvert \bigr) \geq 0 \Bigr\}
\end{align*}
and let $\mathcal{L} = \cap_{i=0}^n \mathcal{L}^{(i)}$ be the intersection of the
$\mathcal{L}^{(i)}$. Moreover, let $D_i \colon \mathcal{L}^{(i)} \rightarrow \mathcal{L}$
denote the differential operator $D_i = x_i \partial_i +  \pi x_i \partial_i(P_0)$.
Finally, let $\psi_p, \alpha \colon \mathcal{L} \rightarrow \mathcal{L}$ be the
$\QQ_p(\pi)$-linear maps defined by:
\begin{align*}
\psi_p(x^w) &=
\begin{cases}
x^{w/p} &\text{ if } p \mid w_i \text{ for all } 0 \leq i \leq n \\
0                        &\text{ otherwise}
\end{cases} \\
\alpha(x^w) &= \psi_p \Bigl( \exp\Bigl(\pi \bigl(P_0(x_0,\ldots,x_n)-P_0(x_0^p,\ldots,x_n^p)\bigl) \Bigr) \cdot x^w \Bigr)
\intertext{and let $\mathcal{R} \colon \mathcal{L} \rightarrow \Hrig^n(U_0) \otimes \QQ_p(\pi)$
denote the $\QQ_p(\pi)$-linear map defined by}
\mathcal{R}(x^w) &= \frac{(\lvert w \rvert-1)!}{(-\pi)^{\lvert w \rvert-1}} \frac{x^{w-1} \Omega}{P_0^{\lvert w \rvert}},
\end{align*}
where $\Omega$ is defined as in Proposition~\ref{prop:Omega}.

Then by \citep[Theorem 2.15]{katz}, the diagram
\[
\begin{CD}
\mathcal{L} / \sum_{i=0}^n D_i \mathcal{L}^{(i)} @>  \; \; \; \; \; p^{-n} \alpha \; \; \; \;   >> \mathcal{L} / \sum_{i=0}^n D_i \mathcal{L}^{(i)}  \\
@VV \mathcal{R} V  @V \mathcal{R} VV \\
\Hrig^n(U_0) \otimes \QQ_p(\pi) @> \left(p^{-1} \Frob_p \right)^{-1}  >> \Hrig^n(U_0) \otimes \QQ_p(\pi)
\end{CD}
\]
commutes and by \citep[Corollary 1.15]{katz} the vertical maps are isomorphisms.
This implies that~\eqref{eq:diagfrobformula} is equivalent to
\[
\alpha(x^{v+1}) \equiv \pi^{pk(u)-k(v)} \alpha_{u,v} \cdot x^{u+1} \bmod{\sum_{i=0}^n D_i \mathcal{L}^{(i)}},
\]
which we will now prove.

Note that so far we have not used that $P_0$ is diagonal. Since
$P_0(x_0, x_1, \dotsc, x_n)$ is equal to $a_0 x_0^d + a_1 x_1^d + \dotsb + a_n x_n^d$,
we have
\begin{align*}
\exp \Bigl(\pi \bigl(P_0(x_0,\ldots,x_n)- P_0(x_0^p,\ldots,x_n^p)\bigl) \Bigr)
    = \prod_{i=0}^n \exp \Bigl( \pi a_i (x_i^d - x_i^{dp}) \Bigr)
\end{align*}
and also
\begin{align*}
D_i =x_i \partial_i + (\pi a_i d) x_i^d.
\end{align*}
For $0 \leq i \leq n$, we denote
\begin{align*}
\QQ_p(\pi) \left\langle x_i \right\rangle^{\dag} =  \left\{ \sum_{j=0}^{\infty} b_j x_i^{j} \; : \;
b_{j} \in \QQ_p(\pi), \; \exists c > 0 \text{ s.t.}
\lim_{j \rightarrow \infty} \left(\ord_p(b_j) - c \cdot j \right) \geq 0 \right\}
\end{align*}
and we define $\QQ_p(\pi)$-linear maps $\psi_p, D_i$ on $\QQ_p(\pi) \langle x_i \rangle^{\dag}$
by the same formulas as before. Then
\begin{align*}
\psi_p \Bigl( \exp \bigl(\pi a_i(x_i^d- x_i^{pd})\bigr) x_i^{v_i+1} \Bigr)
    & = \sum_{\substack{m \geq 0 \text{ s.t. }\\ p \mid dm+v_i+1}}
        \biggl(\sum_{j=0}^{\floor{m/p}} \frac{(-1)^j (\pi a_i)^{m-(p-1)j}}{j! (m-pj)!} \biggr) x_i^{(dm+v_i+1)/p} \\
    & = \sum_{\; \; \; \; \; \; m,r \; \; \; \; \; \;}
        \biggl(\; \sum_{j=0}^{r} \; \; \frac{(-1)^j (\pi a_i)^{m-(p-1)j}}{j! (m-pj)!} \biggr) x_i^{u_i+1+dr},
\end{align*}
where the outer sum on the last line is over all integers $m, r \geq 0$
that satisfy $p(u_i+1)-(v_i+1)=d(m-pr)$ and we have used Lemma~\ref{lem:mpr}.
It is clear that
\begin{equation*}
x_i^{u_i+1+dr} \equiv \Bigl(\frac{u_i+1}{d}\Bigr)_r (-\pi a_i)^{-r} x_i^{u_i+1} \bmod{D_i \QQ_p(\pi) \langle x_i \rangle^{\dag} }.
\end{equation*}
Hence, it follows that
\begin{align*}
&\psi_p \Bigl( \exp \bigl(\pi a_i \bigl( x_i^d- x_i^{pd} \bigr) \bigr) x_i^{v_i+1} \Bigr) \equiv \\
&(\pi a_i)^{(p (u_i + 1) - (v_i + 1))/d}
    \biggl( \sum_{m,r} \left( \frac{u_i+1}{d} \right)_r
        \sum_{j=0}^{r} \frac{(p a_i^{p-1})^{r-j}}{(m-pj)!j!} \biggr) x_i^{u_i+1} \bmod{D_i \QQ_p(\pi) \langle x_i \rangle^{\dag}},
\end{align*}
where the sum is still over all integers $m, r \geq 0$  that satisfy $p(u_i+1)-(v_i+1)=d(m-pr)$.
For $G_i \in  \QQ_p(\pi) \langle x_i \rangle^{\dag}$ with $0 \leq i \leq n$, we have
\begin{align*}
  \psi_p \biggl( \prod_{j=0}^n G_j \biggr) &= \prod_{j=0}^n \psi_p(G_j),
& D_i \biggl( \prod_{j=0}^n G_j \biggr) &= D_i(G_i) \cdot \prod_{j \neq i} G_j.
\end{align*}
Therefore, we can take the product of the congruences above to conclude that
\begin{align*}
\alpha(x^{v+1}) \equiv \pi^{pk(u)-k(v)} \alpha_{u,v} \cdot x^{u+1} \bmod{\sum_{i=0}^n D_i \QQ_p(\pi) \langle x_i \rangle^{\dag}}.
\end{align*}
Since
$\mathcal{L} \; \cap \; \sum_{i=0}^n D_i \QQ_p(\pi) \langle x_i \rangle^{\dag} =  \sum_{i=0}^n D_i \mathcal{L}^{(i)}$,
we can replace $\sum_{i=0}^n D_i \QQ_p(\pi) \langle x_i \rangle^{\dag}$
by $\sum_{i=0}^n D_i \mathcal{L}^{(i)}$ in this expression, completing the proof.
\end{proof}

\begin{rem}
The computation in the proof of Theorem~\ref{thm:01-03-diagfrob} essentially
goes back to Dwork~\citep[\S 4]{Dwork1964}.  Following Dwork's work, Lauder
obtained a formula similar to ours~\citep[Proposition 10]{Lauder2004b}, that
was used both by him~\citep{Lauder2004b} and Gerkmann~\citep{Gerkmann2007}
in their algorithms.

However, our approach is different in two ways.  Firstly, our formula
for~$\alpha_{u,v}$ is defined over~$\QQ_p$ instead of $\QQ_p(\pi)$. By
eliminating the $\pi$'s, we are able to improve the complexity of
the computation of $\Phi_0$, and even of the whole deformation algorithm,
by a factor~$p$, as we will see in Section~\ref{sec:Complexity}. Secondly,
Lauder's formula is only valid when the $a_i$ are Teichm\"uller lifts,
i.e.\ $a_i^{p-1}=1$. From a theoretical point of view, of course one can
always choose the $a_i$ to be Teichm\"uller lifts, but in computations
this is unnecessarily restrictive.
\end{rem}

\subsection{Some estimates}

There are two remaining problems for computing the matrix~$\Phi_0$. Firstly, to
compute~$\Phi_0$ to $p$-adic precision $N_{\Phi_0}$ using Theorem~\ref{thm:01-03-diagfrob},
we have to compute the elements~$\alpha_{u,v}$ to a somewhat higher precision~$N'_{\Phi_0}$
because of loss of precision in the computation. In Corollary~\ref{cor:NPhi0prime} we will
obtain a bound for~$N'_{\Phi_0}$. Secondly, the sums over $m,r$ in Definition~\ref{defn:alpha}
consist of infinitely many terms.  In Proposition~\ref{prop:MR} we will derive a finite
expression for $\alpha_{u,v}$ to precision $N'_{\Phi_0}$. We start with some estimates that
will be needed in the proofs.

\begin{prop} \label{prop:rfac}
For all integers $j, d, r \geq 1$ with $p \nmid d$,
\begin{equation*}
\ord_p\Bigl(\frac{j}{d}\Bigr)_r \geq \ord_p(r!) \geq \frac{r}{p-1} - \floor{\log_p(r) + 1}.
\end{equation*}
\end{prop}

\begin{proof}
Let $s_p(r)$ denote the sum of digits in the $p$-adic expansion of~$r$
and observe that $s_p(r) \leq (p-1)\floor{\log_p(r) + 1}$. Then
\begin{equation*}
\ord_p\left(\frac{j}{d}\right)_r \geq \ord_p(r!)
    = \frac{r - s_p(r)}{p-1} \geq \frac{r}{p-1} - \floor{\log_p(r) + 1}. \qedhere
\end{equation*}
\end{proof}

\begin{prop} \label{prop:coefbound}
For all integers $m \geq 0$ and $0 \leq i \leq n$,
\begin{align*}
\ord_p \biggl( \sum_{j=0}^{\floor{m/p}} \frac{(p a_i^{p-1})^{\floor{m/p}-j}}{(m-pj)!j!} \biggr)
    \geq \frac{p-1}{p^2}m + \floor{\frac{m}{p}}-\frac{m}{p-1}.
\end{align*}
\end{prop}
\begin{proof}
Let $\QQ_p(\pi)$ denote the totally ramified extension of $\QQ_p$ with $\pi^{p-1} = -p$ and
extend the $p$-adic valuation such that \mbox{$\ord_p(\pi) = (p-1)^{-1}$}. Expanding
\begin{align*}
\exp \bigl( \pi a_i(x-x^p) \bigr) &= \sum_{m=0}^{\infty} \lambda_m x^m,
\end{align*}
one checks easily that, for all $m \geq 0$,
\begin{align*}
\lambda_m &= \sum_{j=0}^{\floor{m/p}} \frac{(-1)^j (\pi a_i)^{m-(p-1)j}}{(m-pj)!j!} \\
          &= (-1)^{\floor{m/p}} (\pi a_i)^{m-(p-1)\floor{m/p}} \biggl( \sum_{j=0}^{\floor{m/p}} \frac{(p a_i^{p-1})^{\floor{m/p}-j}}{(m-pj)!j!} \biggr).
\end{align*}
Therefore, it suffices to show that $\ord_p(\lambda_m) \geq m (p-1)/p^2$. This is
well-known in the case $a_i=1$, but the proof from \citep[Lemma 4.1]{dwork1962}
remains valid when $a_i \in \ZZ_p^{\times}$.
\end{proof}

\begin{thm} \label{thm:alphabound}
Let $\alpha_{u,v}$ be defined as in Definition~\ref{defn:alpha}. Then
\begin{equation*}
0 \leq \ord_p(\alpha_{u,v}) \leq \ord_p\left( \frac{(k(v)-1)!}{(k(u)-1)!} \right)+(n-k(u))+\delta,
\end{equation*}
where $\delta$ is defined as in Definition~\ref{defn:delta}.
\end{thm}

\begin{proof}
First, we prove the left-hand inequality. By Lemma~\ref{lem:mpr}, Proposition~\ref{prop:rfac}
and Proposition~\ref{prop:coefbound}, it suffices to show that
\begin{align} \label{eq:mp}
\frac{p-1}{p^2}m + \floor{\frac{m}{p}}-\frac{m}{p-1} + \ord_p\left(\floor{\frac{m}{p}}!\right)>-1,
\end{align}
for all integers $m \geq p$. From Proposition~\ref{prop:rfac} and the fact that $m \geq p \floor{m/p}$, it follows that
\begin{align*}
\frac{p-1}{p^2}m + \floor{\frac{m}{p}}-\frac{m}{p-1} + \ord_p\left(\floor{\frac{m}{p}}!\right) \geq \frac{p-1}{p} \floor{\frac{m}{p}} - \floor{\log_p\left(\floor{\frac{m}{p}}\right)+1}.
\end{align*}
One checks easily that the right-hand side is greater than $-1$, unless we have $p=2$ and $m=4,5$. However, in these cases~\eqref{eq:mp} still holds, as can be seen by direct
substitution.

Next, we prove the right-hand inequality. Recall from Corollary~\ref{cor:delta} that the valuations
of the entries of the matrix~$\Phi_0$ are bounded below by $-\delta$. Thus by Theorem~\ref{thm:01-03-diagfrob},
we have
\begin{equation*}
-\delta \leq \ord_p\left(\frac{(k(v) - 1)!}{(k(u) - 1)!} \right)+ (n-k(u)) - \ord_p( \alpha_{u,v}),
\end{equation*}
from which the result follows.
\end{proof}

Using Theorem~\ref{thm:alphabound}, we can now bound the $p$-adic precision $N'_{\Phi_0}$ to which we
have to compute the $\alpha_{u,v}$.

\begin{cor} \label{cor:NPhi0prime}
In order to compute the matrix $\Phi_0$ to $p$-adic precision $N_{\Phi_0}$, it is sufficient to
compute the $\alpha_{u,v}$ to $p$-adic precision
\[
N_{\Phi_0}' = N_{\Phi_0} + (n-1) + \ord_p\left((n-1)!\right)  + 2\delta,
\]
where $\delta$ is defined as in Definition~\ref{defn:delta}.
\end{cor}

\begin{proof}
Note that the loss of precision in inverting $\alpha_{u,v}$ is at most $2\ord_p(\alpha_{u,v})$.
Therefore, it follows from Theorem~\ref{thm:01-03-diagfrob} and Theorem~\ref{thm:alphabound} that
it is sufficient to compute $\alpha_{u,v}$ to precision
\begin{align*}
N_{\Phi_0} + \ord_p\left(\frac{(k(v) - 1)!}{(k(u) - 1)!} \right) + (n-k(u)) + 2\delta \leq
N_{\Phi_0} + (n-1) + \ord_p\left((n-1)!\right)  + 2\delta,
\end{align*}
where we have used that $1 \leq k(u),k(v) \leq n$.
\end{proof}

To derive a finite expression for $\alpha_{u,v}$ to precision $N'_{\Phi_0}$,
we start with the following elementary lemma.

\begin{lem} \label{lem:log}
Given integers $\alpha, \beta \geq 2$ and defining
$x = \beta + \log_{\alpha}(\beta) + 1$, for all real numbers $y \geq x$,
we have
\begin{equation*}
y - \log_{\alpha}(y) \geq \beta.
\end{equation*}
\end{lem}

\begin{proof}
We first note that the function $y \mapsto y - \log_{\alpha}(y)$ is increasing
for $y \geq 2$ because it has derivative $1 - \log_{\alpha}(e)/y > 0$.  Thus,
it suffices to verify the result for~$x$.  Indeed, as $\beta \geq 2$ we have
that $\log_{\alpha}(\beta) + 1 \leq \beta$, hence
$\beta + \log_{\alpha}(\beta) + 1 \leq 2 \beta \leq \alpha \beta$,
which upon taking logarithms and rearranging yields the result.
\end{proof}

\begin{prop} \label{prop:MR}
In order to compute $\alpha_{u,v}$ to $p$-adic precision~$N'_{\Phi_0}$,
it suffices to restrict the sums in Theorem~\ref{defn:alpha} to pairs $m,r \geq 0$
such that $m \leq \mathcal{M}$, or equivalently $r \leq \mathcal{R}$, where
\begin{align*}
\mathcal{M} &= \ceil{\frac{p^2}{p-1}(N'_{\Phi_0}+\log_p(N'_{\Phi_0}+3)+4)} - 1,
&\mathcal{R} &= \floor{\mathcal{M}/p}.
\end{align*}
\end{prop}

\begin{proof}
By Proposition~\ref{prop:rfac} and Proposition~\ref{prop:coefbound}, we have
\begin{align*}
\ord_p \biggl( \Bigl( \frac{u_i+1}{d} \Bigr)_r \sum_{j=0}^{r} \frac{(p a_i^{p-1})^{r-j}}{(m-pj)!j!} \biggr)
    &\geq  \frac{p-1}{p^2}m + \floor{\frac{m}{p}}-\frac{m}{p-1}+\frac{r}{p-1}-\floor{\log_p(r)+1} \\
    &\geq  \frac{p-1}{p^2}m - \log_p(m)-1.
\end{align*}
Therefore, it is sufficient to restrict the sums in Definition~\ref{defn:alpha}
to $m,r \geq 0$ for which
\begin{align*}
\frac{p-1}{p^2}m - \log_p(m) -1 < N'_{\Phi_0}.
\end{align*}
We can now apply Lemma~\ref{lem:log} with $y=m(p-1)/p^2$, $\alpha=p$
and $\beta=N'_{\Phi_0}+3$ to obtain the result.
\end{proof}

Finally, we formalise the procedure for computing the entries of~$\Phi_0$ to
$p$-adic precision~$N_{\Phi_0}$ in Algorithm~\ref{alg:Diagfrob}.

\begin{algorithm}
\caption{Compute the matrix $\Phi_0$.}
\label{alg:Diagfrob}
\begin{algorithmic}
\vspace{1mm}
\Require $P_0=a_0 x_0^d + \dotsb + a_n x_n^d$
         with $a_0,\dotsc,a_n \in \ZZ_p^{\times}$,
         $p$-adic precision $N_{\Phi_0} \geq 0$.
\Ensure  The matrix $\Phi_0$ for the action of $p^{-1} \Frob_p$
         on $\Hrig^n(U_0)$ with respect to basis $\cB$ to $p$-adic
         precision $N_{\Phi_0}$.
\Procedure{DiagFrob}{$P_0,N_{\Phi_0}$}
\State \begin{compactenum}[{\hspace{1em}} 1.] \vspace{-1.24em}
\item Determine $N'_{\Phi_0}$ from Corollary~\ref{cor:NPhi0prime}.
\item Let $\Phi_0 \in M_{b \times b}(\QQ_p)$ be the zero matrix.
\item[] \textbf{for} $x^u \in B$ \textbf{do}
\item[] \begin{compactenum}[{\hspace{1em}} 1.]
        \item Determine the unique $x^v \in B$ such that $v_i = p (u_i + 1) - 1 \bmod{d}$.
        \item Compute $\alpha_{u,v}$ to $p$-adic
              precision $N'_{\Phi_0}$ using Proposition~\ref{prop:MR}.
        \item Set $(\Phi_0)_{u,v} \gets (-1)^{k(v)} \left( \frac{ (k(v)-1)!}{(k(u)-1)!} \right) p^{n-k(u)} \alpha_{u,v}^{-1} \bmod{p^{N_{\Phi_0}}}$.
      \end{compactenum}
 \item \textbf{return} $\Phi_0$
\end{compactenum}
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{assump} \label{assump:diag}
From now on we assume that our family of
hypersurfaces~$\mathcal{X}/\mathcal{S}$ is defined by a
polynomial $P \in \ZZ_q[t][x_0,\dotsc,x_n]$ for which
$P(0) \in \ZZ_q[x_0,\dotsc,x_n]$ is of the form
$P_0=a_0 x_0^d + \dotsb + a_n x_n^d$ with $a_0,\dotsc,a_n \in \ZZ_p^{\times}$,
so that we can apply Algorithm~\ref{alg:Diagfrob}.
\end{assump}

\begin{rem}
Note that Assumption~\ref{assump:diag}
also implies that $\mathcal{S}$ can be chosen to satisfy Assumption~\ref{assump:S}
and Assumption \ref{assump:R}, since $P_0$ defines a smooth hypersurface and
we have that $R(0) \in \ZZ_p^{\times}$.
\end{rem}

\section{Solving the differential equation}
\label{sec:DifferentialSystem}

In this section we explain how to solve the $p$-adic differential
equation for the horizontal sections of the Gauss--Manin
connection $\nabla$, in order to obtain a local expansion of the
matrix for the action of $p^{-1} \Frob_p$ on $\Hrig^{n}(U/S)$.

All our matrices will be defined with respect to the basis $\cB$. Recall
that $M \in M_{b \times b}(\QQ_q(t))$ denotes
the matrix for the Gauss--Manin connection $\nabla$ on
$\HdR^n(\mathfrak{U}/\mathfrak{S})$ and
$\Phi \in M_{b \times b} \bigl(\QQ_q \langle t,1/r \rangle^{\dag} \bigr)$
the matrix for the $\sigma$-semilinear action of~$p^{-1} \Frob_p$
on $\Hrig^{n}(U/S)$, where $\sigma$ is defined as
in Definition~\ref{defn:sigma}.

As we saw in Section~\ref{sec:Background}, these matrices satisfy
the differential equation
\begin{align} \label{eq:Phi}
\left(\frac{d}{dt} + M\right) \Phi &= p t^{p-1} \Phi \sigma(M), &\Phi(0)& = \Phi_0,
\end{align}
where $\Phi_0 \in M_{b \times b}(\QQ_p)$ is the matrix for the action
of $p^{-1} \Frob_p$ on $\Hrig^n(U_0)$. Our goal is the computation of
the power series expansion of~$\Phi$ at $t=0$ to $t$-adic precision~$K$
and $p$-adic precision $N_{\Phi}$, i.e.\ as an element of
$M_{b \times b}(\QQ_q[[t]])$ modulo $t^K$ and $p^{N_{\Phi}}$.

We first observe that if
$C \in M_{b \times b}(\QQ_q[[t]])$ denotes
the unique solution to the differential equation
\begin{align} \label{eq:01-GMDE-Homogenous}
\Bigl(\frac{d}{dt} + M\Bigr) C &= 0, &C(0)&=I,
\end{align}
where $I$ denotes the identity matrix,
then the matrix $\Phi = C \Phi_0 \sigma(C)^{-1}$ satisfies
Equation~\eqref{eq:Phi}. So it is sufficient to solve
Equation~\eqref{eq:01-GMDE-Homogenous}.
We now give a bound on the rate of
convergence of $C=\sum_{i=0}^{\infty} C_i t^i$ that
follows from recent work of
Kedlaya~\citep{Kedlaya2010}.
We let $\delta$ be defined as in Definition~\ref{defn:delta}.

\begin{thm} \label{thm:valC}
For all $i \geq 1$, we have
\begin{equation*}
\ord_p(C_i) \geq - \left(2 \delta + (n - 1)\right) \ceil{\log_p(i)}.
\end{equation*}
\end{thm}

\begin{proof}
It follows from~\citep[Theorem~{18.3.3}]{Kedlaya2010} that
\begin{equation*}
\ord_p(C_i) \geq \left( \ord_p(\Phi) + \ord_p(\Phi^{-1}) \right) \ceil{\log_p(i)},
\end{equation*}
but from Corollary~\ref{cor:delta} we already know that $\ord_p(\Phi) \geq -\delta$ and
$\ord_p(\Phi^{-1}) \geq -\delta-(n-1)$.
\end{proof}

\begin{rem}
In~\citep[Remark~18.3.4]{Kedlaya2010} Kedlaya also includes the bound
\begin{equation*}
\ord_p(C_i) \geq (b - 1) \ord_p(M)
            + \left( \ord_p(\Phi) + \ord_p(\Phi^{-1}) \right) \floor{\log_p(i)},
\end{equation*}
which can sometimes be used to improve Theorem \ref{thm:valC}
slightly, for example when $\ord_p(M)$ is nonnegative.
\end{rem}

\begin{rem} \label{rem:Cinv}
The bound from Theorem~\ref{thm:valC}
also applies to the inverse matrix~$C^{-1}$, as this matrix satisfies
the dual differential equation
\begin{align} \label{eq:01-GMDE-Dual}
\left(\frac{d}{dt} - M^t\right) \left(C^{-1}\right)^t &= 0, &C^{-1}(0)& = I,
\end{align}
that carries a Frobenius structure
given by the matrix~$(\Phi^{-1})^t$.
\end{rem}

We only know the matrix $M$ to some finite $p$-adic precision
$N_M$, and we need to compute $C$ to some finite $t$-adic and
$p$-adic precisions $K,N_C$, respectively. The following result gives an
expression for $N_M$ in terms of $K,N_C$. For a matrix
$A=\sum_{i=0}^{\infty} A_i t^i$ we write
$\overline{A}=\sum_{i=0}^{K-1} A_i t^i$
in what follows.

\begin{prop} \label{prop:N_M}
Let $K,N_C \in \NN$ and define
\[
N_M= N_C + (2 \delta + n) \ceil{\log_p(K-1)}+1.
\]
Let $\tilde{M} \in M_{b \times b}(\QQ_q(t))$ be
an approximation of $M$ to $p$-adic precision $N_M$, i.e.
such that $\ord_p(\tilde{M}-M) \geq N_M$, and suppose that
$\tilde{C}=\sum_{i=0}^{\infty} \tilde{C}_i t^i$ satisfies the
differential equation
\begin{align*}
\left(\frac{d}{dt}+\tilde{M} \right) \tilde{C}&=0, &\tilde{C}(0)=I&.
\end{align*}
Then $\ord_p(\tilde{C}_i-C_i) \geq N_C$ for all $i < K$.
\end{prop}

\begin{proof}
From the expressions
\begin{align*}
C(t)&=\exp\left(- \int_{0}^t M(s) ds\right), &
\tilde{C}(t)&=\exp\left(-\int_{0}^t \tilde{M}(s) ds\right),
\end{align*}
it follows that
\begin{equation} \label{eq:CtildeminusC}
\tilde{C}(t) - C(t) = C(t) \left( \exp \left( \int_{0}^t \left( \tilde{M}(s)-M(s) \right) ds \right)- I \right).
\end{equation}
Since $\ord_p(\tilde{M}-M) \geq N_M$, we obtain
\begin{equation*}
\ord_p \left( \overline{\frac{1}{i!} \left(\int_{0}^t \left( \tilde{M}(s)-M(s) \right) ds \right)^i } \right) \geq
N_C + (2 \delta + n-1) \ceil{\log_p(K-1)}
\end{equation*}
for all $1 \leq i \leq K-1$, where we have used that
$\ord_p(i!) \leq i/(p-1) \leq 1$. Moreover, from
Theorem~\ref{thm:valC}, we already know that
\[
\ord_p(\overline{C}) \geq -(2 \delta + n-1) \ceil{\log_p(K-1)}.
\]
From these two inequalities and Equation~\eqref{eq:CtildeminusC}, we
deduce $\ord_p(\overline{\tilde{C}-C}) \geq N_C$.
\end{proof}

Now we explain how to compute the solution $C$ to
Equation~\eqref{eq:01-GMDE-Homogenous} to $p$-adic precision~$N_C$ and
$t$-adic precision~$K$, assuming that the connection matrix~$M$ has been
computed to $p$-adic precision~$N_M$ as defined in Proposition~\ref{prop:N_M}.
We can write $M = G/r$, with
$G = \sum_{i=0}^{\deg(G)} G_i t^i \in M_{b \times b}(\QQ_q[t])$
and $r = \sum_{i=0}^{\deg(r)} r_i t^i \in \ZZ_q[t]$ a divisor of the
polynomial~$R$ defined in Definition~\ref{defn:resultant}.
Note that the degree of~$r$ might be smaller than the degree
of~$R$, which will speed up our computations. By Assumption~\ref{assump:diag},
we have $r(0) \neq 0 \bmod{p}$, so in particular $r(0) \neq 0$.

We can obtain a power series solution $C = \sum_{i=0}^{\infty} C_i t^i$ to
the equation
\begin{align*}
r \frac{dC}{dt} + G C &= 0, &C(0)& = I,
\end{align*}
which is clearly equivalent to
Equation~\eqref{eq:01-GMDE-Homogenous}, using the following recursion:
\begin{align} \label{eq:recursiondifeq}
C_0 &= I, \nonumber \\
C_{i+1} &= \frac{-1}{r_0 (i+1)} \left(
    \sum_{j=\max{\{0,i-\deg(G)\}}}^i G_{i-j} C_j +
    \sum_{j=\max{\{0,i-\deg(r)\}}+1}^i r_{i-j+1} (j C_j) \right).
\end{align}
Again we will only carry out this computation to some finite $p$-adic
working precision~$N'_C$, and if we want $C$ to be correct to $p$-adic
precision~$N_C$, then the precision~$N'_C$ has to be somewhat higher
because of error propagation. An expression for~$N'_C$, in terms of~$N_C$
and the desired $t$-adic precision~$K$, was given by
Lauder~\citep[Theorem~5.1]{Lauder2006}, but his result can be
significantly improved using Theorem~\ref{thm:valC}, as we will now show.

Let $\tilde{C}=\sum_{i=0}^{\infty} \tilde{C}_i t^i$ denote an
approximation to $C$ obtained using the approximate recursion:
\begin{align*}
\tilde{C}_0 &= I, \\
\tilde{C}_{i+1} &= \frac{-1}{r_0 (i+1)} \left(
    \sum_{j=\max{\{0,i-\deg({G})\}}}^i {G}_{i-j} \tilde{C}_j +
    \sum_{j=\max{\{0,i-\deg({r})\}}+1}^i {r}_{i-j+1} (j \tilde{C}_j) \right) + {E}_{i+1},
\end{align*}
where $\ord_p({E}_i) \geq N'_{C}$ for all $i \geq 1$,
so that the matrices~$\tilde{C}_i$ are computed with $p$-adic working
precision~$N'_C$.

\begin{prop} \label{thm:errorprop}
Let $K,N_{C} \in \NN$, and suppose that
\begin{align*}
N'_C          &= N_{C} + \left(2 \left(2 \delta + (n-1)\right) + 1\right) \ceil{\log_p(K-1)}.
\end{align*}
Then $\ord_p(\tilde{C}_i-C_i) \geq N_{C}$ for all $i < K$.
\end{prop}

\begin{proof}
The matrix $\tilde{C}$ satisfies the differential equation
\begin{align*}
\frac{d\tilde{C}}{dt}+M \tilde{C}&=E, &\tilde{C}(0)&=I,
\end{align*}
where we have denoted $E=\sum_{i=1}^{\infty} E_i t^i$.
One also checks that the matrix $C^{-1}\tilde{C}$ satisfies
the differential equation
\begin{align*}
\frac{d(C^{-1}\tilde{C})}{dt} &=C^{-1} E, &(C^{-1}\tilde{C})(0)&=I,
\end{align*}
from which it follows that
\begin{equation} \label{eq:integral}
\tilde{C}(t)-C(t) = C(C^{-1} \tilde{C}-I) = C(t) \left(\int_{0}^t C^{-1}(s) E(s) ds \right).
\end{equation}
We know from Theorem~\ref{thm:valC} and Remark~\ref{rem:Cinv} that
\begin{equation} \label{eq:boundCCinv}
\ord_p(\overline{C}),\ord_p(\overline{C^{-1}}) \geq
-(2 \delta + n-1) \ceil{\log_p(K-1)},
\end{equation}
and we hence obtain
\[
\ord_p \left(\overline{\int_{0}^t C^{-1}(s) E(s) ds }\right) \geq
N_{C} + \left( \bigl(2 \delta + (n-1)\bigr) \right) \ceil{\log_p(K-1)}.
\]
From the bounds~\eqref{eq:boundCCinv} and Equation~\eqref{eq:integral},
we deduce that $\ord_p\left(\overline{\tilde{C}-C}\right) \geq N_C$.
\end{proof}

\begin{rem}
A result similar to Proposition~\ref{thm:errorprop} with a larger constant in front of
the logarithm was obtained by Lauder in \citep[Theorem 5.1]{Lauder2006}. We have
not been able to find something similar to Proposition~\ref{prop:N_M} in Lauder's work.
\end{rem}

\begin{rem} \label{rem:sigmatrick}
In order to determine the power series expansion of the matrix~$\Phi$,
we also need to compute the matrix $\sigma(C)^{-1}$. We could compute
the matrix~$C^{-1}$ using matrix inversion over the ring $\mathbf{Q}_q[[t]]$.
However, solving~\eqref{eq:01-GMDE-Dual} turns
out to be more efficient.
\end{rem}

We finally give all the precisions necessary for computing the power series
expansion of $\Phi$ at $t=0$ to $t$-adic precision $K$ and $p$-adic
precision $N_{\Phi}$.

\begin{thm} \label{thm:Ni}
Let $K,N_{\Phi} \in \NN$ and define:
\begin{eqnarray*}
N_{\Phi_0}   		&=& N_{\Phi}+\left(2\delta+(n-1)\right) \left( \ceil{\log_p(K-1)} + \ceil{\log_p(\ceil{K/p}-1)}\right),\\
N_{C}				&=& N_{\Phi}+\left(2\delta+(n-1)\right) \ceil{ \log_p(\ceil{K/p}-1)} + \delta, \\
N_{C^{-1}}			&=& N_{\Phi}+\left(2\delta+(n-1)\right) \ceil{\log_p(K-1)} + \delta, \\
N_M                 &=& N_{\Phi}+\left(2\left(2 \delta + (n-1)\right) + 1\right) \ceil{\log_p(K-1)}+1, \\
N'_C			    &=& N_{\Phi}+\left(2 \left(2 \delta + (n-1)\right) + 1\right) \ceil{\log_p(K-1)}, \\
N'_{C^{-1}}	        &=& N_{\Phi}+\left(2 \left(2 \delta + (n-1)\right) + 1\right) \ceil{\log_p(\ceil{K/p}-1)}.
\end{eqnarray*}

In order to compute the power series expansion of the matrix~$\Phi$ at $t=0$
with $t$-adic precision~$K$ and $p$-adic precision~$N_{\Phi}$, it is
sufficient to compute the matrix~$\Phi_0$ to $p$-adic precision~$N_{\Phi_0}$,
the matrix~$C$ to $t$-adic precision~$K$ and $p$-adic precision~$N_{C}$,
the matrix~$C^{-1}$ to $t$-adic precision $\ceil{K/p}$ and $p$-adic
precision~$N_{C^{-1}}$, and the matrix~$M$ to $p$-adic precision~$N_M$.

Therefore, while solving Equation~\eqref{eq:01-GMDE-Homogenous} for $C$ and
Equation~\eqref{eq:01-GMDE-Dual} for $C^{-1}$, using a recursion like in
Equation~\eqref{eq:recursiondifeq}, it is sufficient to use $p$-adic
working precisions $N'_C$ and $N'_{C^{-1}}$, respectively.
\end{thm}

\begin{proof}
Recall that $\Phi = C \Phi_0 \sigma(C)^{-1}$. The sufficient $t$-adic
precisions are clear. We can apply Proposition~\ref{prop:matrixproductval},
using Theorem~\ref{thm:valC} for both $C$ and $C^{-1}$ and the fact that
$\ord_p(\Phi_0) \geq -\delta$ from Corollary~\ref{cor:delta}, to obtain
the sufficient $p$-adic precisions for the matrices $\Phi_0$, $C$ and $C^{-1}$.
The sufficient precision for the matrix $M$ follows from Proposition~\ref{prop:N_M},
and the sufficient working precisions $N'_C$ and $N'_{C^{-1}}$
follow from Proposition~\ref{thm:errorprop}.
\end{proof}

Now we have all the ingredients to compute the power series expansion of
$\Phi$ at $t=0$ to any given $p$-adic and $t$-adic precisions, as formalised
in Algorithm~\ref{alg:expansion}.

\begin{algorithm}
\caption{Compute the power series expansion of $\Phi$ at $t=0$.}
\label{alg:expansion}
\begin{algorithmic}
\vspace{1mm}
\Require $P \in \ZZ_q[t][x_0,\dotsc,x_n]$ satisfying Assumption~\ref{assump:diag}, $t$-adic precision~$K$, $p$-adic precision~$N_{\Phi}$.
\Ensure  The power series expansion of $\Phi$ at $t=0$ to $t$-adic precision $K$ and $p$-adic precision $N_{\Phi}$.
\Procedure{FrobSeriesExpansion}{$N_{\Phi},K$}
\State \begin{compactenum}[{\hspace{6pt}} 1.] \vspace{-1.24em}
\item Determine $N_M,N_{\Phi_0},N_C,N_{C^{-1}},N'_C$, and $N'_{C^{-1}}$ from Theorem~\ref{thm:Ni}.
\item $M \gets \textsc{GMConnection}(P,N_M)$
\item $\Phi_0 \gets \textsc{DiagFrob}(P_0,N_{\Phi_0})$
\item Solve Equation~\eqref{eq:01-GMDE-Homogenous} for $C$ to $t$-adic precision $K$ and $p$-adic precision $N_{C}$:
\begin{compactenum}[a.]
\item[] $C_0 \gets I$
\item[] \textbf{for} $i=0$ \textbf{to} $K-2$ \textbf{do}
\item[] \hspace{0.6em} $C_{i+1} \gets \frac{-1}{r_0 (i+1)} \Bigl(\sum_j G_{i-j} C_j + \sum_j r_{i-j+1} (j C_j) \Bigr) \bmod{p^{N'_C}}$
\item[] $C \gets \sum_{i=0}^{K-1} C_i t^i \bmod{p^{N_C}}$
\end{compactenum}
\item Solve Equation~\eqref{eq:01-GMDE-Dual} for $C^{-1}$ to $t$-adic precision $\ceil{K/p}$ and $p$-adic precision $N_{C^{-1}}$:
\begin{compactenum}[a.]
\item[] $(C^{-1})_0 \gets I$
\item[] \textbf{for} $i=0$ \textbf{to} $\ceil{K/p}-2$ \textbf{do}
\item[] \hspace{0.6em} $(C^{-1})_{i+1} \gets  \frac{-1}{r_0(i+1)} \Bigl(\sum_j -G_{i-j}^t (C^{-1})_j + \sum_j r_{i-j+1} (j (C^{-1})_j) \Bigr) \bmod{p^{N'_{C^{-1}}}}$
\item[] $C^{-1} \gets \sum_{i=0}^{\ceil{K/p}-1} (C^{-1})_i t^{i} \bmod{p^{N_{C^{-1}}}}$
\end{compactenum}
\item $\Phi \gets C \Phi_0 \sigma(C^{-1})$
\item \Return $\Phi$
\end{compactenum}
\EndProcedure
\end{algorithmic}
\end{algorithm}

\section{The zeta function of a fibre}

\label{sec:ZetaFunctions}

\subsection{Evaluating $\Phi$ at a point}

In the previous section we described how to compute the power series
expansion at $t=0$ of the matrix~$\Phi$ for the action of $p^{-1} \Frob_p$ on
$\Hrig^{n}(U/S)$. We now want to evaluate $\Phi$ at the Teichm\"uller
lift~$\hat{\tau}$ of some nonzero $\tau \in S(\FF_{\mathfrak{q}})$,
where $\FF_{\mathfrak{q}}/\FF_q$ is a finite field extension, but
the power series expansion of $\Phi$
at $t=0$ usually only converges on the open unit disc $\abs{t} < 1$
and hence cannot be evaluated at $\hat{\tau}$.

However, since $\Phi$ is a matrix of overconvergent functions, i.e.\
\[
\Phi \in M_{b \times b}\left(\QQ_q \left\langle t,1/r \right\rangle^{\dag}\right),
\]
it can be approximated to any given $p$-adic precision $N$ by a matrix
of rational functions, which can then be evaluated at $\hat{\tau}$. To
convert the power series expansion for $\Phi$ to such an approximation
by rational functions, we need a bound on the pole order of these
rational functions at their poles, as a function of~$N$.

The bounds used by Lauder~\citep[\S 8.1]{Lauder2004a} and
Gerkmann~\citep[\S 6]{Gerkmann2007} were not very sharp,
and this significantly impacted their algorithms.
Recently, under some small additional assumptions, Kedlaya and the second
author~\citep[Theorem~2.1]{KedlayaTuitman2012} obtained a sharper bound
that we state below in a simplified form. For $z \in \mathbf{P}^1(\bar{\QQ}_q)$, we
denote the valuation on $\QQ_q(t)$ corresponding to $z$ by $\ord_z(-)$, and
we extend $\ord_z(-)$ to polynomials and matrices over $\QQ_q(t)$ by
taking the minimum over the coefficients and entries, respectively.
We recall that $M$ denotes the matrix of the Gauss--Manin connection~$\nabla$
with respect to the basis~$\cB$ from Definition~\ref{defn:MonBasis}
and let $\delta$ be defined as in Definition~\ref{defn:delta}.

\begin{thm} \label{thm:KedlayaTuitman}
Let $D \subset \mathbf{P}^1(\bar{\QQ}_q)$ be a residue disk and
$z \in D$ a point such that $M$ has at most a simple pole at~$z$
and no other poles contained in $D$. Suppose that
the exponents $\lambda_1, \dotsc, \lambda_{b}$ of $M$ at $z$, which are defined
as the eigenvalues  of the matrix $(t - z) M \vert_{t=z}$ and
known to be rational numbers, are contained in $\ZZ_p \cap \QQ$.
For $i \in \NN$, let
\begin{align*}
f(i) = \max \left\{ -\left(2 \delta + (n-1) \right) \lceil \log_p(i) \rceil,
(b-1) \ord_p(M) -\left(2 \delta + (n-1) \right) \lfloor \log_p(i) \rfloor
\right\},
\end{align*}
and define
\begin{align*}
c = \begin{cases}
0 & \mbox{if $\ord_p(M) \geq 0$}, \\
\min\{0, i + f(i): i \in \NN\} & \mbox{if $\ord_p(M) < 0$}.
\end{cases}
\end{align*}
For $N \in \NN$, let
\begin{align*}
g(N) &= \max \{i \in \NN : i + f(i) - \delta + c  < N \},
\end{align*}
and define
\begin{align*}
\alpha_1    &= \lfloor -p \min_i \{ \lambda_i \} + \max_{i} \{\lambda_i\} \rfloor, \\
\alpha_2    &=  \left \{
         \begin{array}{cl}
         0  & \mbox{if $M$ does not have a pole at $z$},  \\
         0  & \mbox{if $z \in \{0,\infty \}$}, \\
         g(N) & \mbox{otherwise}.
         \end{array}
         \right.
\end{align*}
Then the matrix $\Phi$ is congruent
modulo $p^{N}$ to a matrix $\tilde{\Phi} \in M_{b \times b}(\QQ_q(t))$ for which
\begin{equation*}
\ord_z\left(\tilde{\Phi}\right) \geq -(\alpha_1+p \alpha_2)
\end{equation*}
and $\tilde{\Phi}$ has no other poles contained in $D$.
\end{thm}

\begin{proof}
Since the matrix $\Phi$ defines a Frobenius structure on the vector
bundle $\Hrig^n(U/S)$ with connection $\nabla$, we can
apply~\citep[Theorem~2.1]{KedlayaTuitman2012}. We have
replaced $\ord_p\left(\Phi\right)$ and $\ord_p\left(\Phi\right)+\ord_p\left(\Phi^{-1}\right)$
by their respective lower bounds $-\delta$ and $-2 \delta + (n-1)$, since
we might not know them exactly a priori.
\end{proof}

\begin{rem}
In practice, the constants $-(2 \delta + (n-1))$, $c$, $\alpha_1$, and $-\delta$
are very small in absolute value, so that $g(N)$ is about $N$ and
the lower bound for the order of~$\Phi$ modulo $p^N$ at the point $z$ is
roughly $-pN$.
\end{rem}

\begin{rem} \label{rem:basischange}
The condition that $M$ has a simple pole at $z$ is not a serious restriction.
By \citep[Theorem 2.1]{Lauder2011}, one can always find a matrix $W \in GL_{b}(\QQ_q[t,1/(t-z)])$
such that the connection matrix has a simple pole at $z$ with respect to the basis
$[w_1, \dotsc, w_b]$ defined by $w_j = \sum_{i=1}^b W_{ij} e_i$ for all
$1 \leq j \leq b$, where $\cB=[e_1,\dotsc,e_b]$ denotes our basis from
Definition~\ref{defn:MonBasis}. Now by \citep[Corollary 2.6]{KedlayaTuitman2012},
the matrix $\Phi$ is congruent modulo $p^{N+\ord_p(W)+\ord_p(W^{-1})}$
to a matrix $\tilde{\Phi} \in M_{b \times b}(\QQ_q(t))$ for which
\[
\ord_z\bigl(\tilde{\Phi}\bigr) \geq -(\alpha_1+p \alpha_2)+\ord_z(W)+p\ord_z\bigl(W^{-1}\bigr)
\]
and $\tilde{\Phi}$ has no other poles contained in $D$.
Here, $\alpha_1$ and $\alpha_2$ are defined as in
Theorem~\ref{thm:KedlayaTuitman}, but with $\delta$ replaced by
\begin{equation*}
\delta' = \delta-\left(\ord_p(W)+\ord_p\left(W^{-1}\right)\right),
\end{equation*}
since for the matrix $\Phi'$ of $p^{-1}\Frob_p$ with respect to the basis
$[w_1,\dotsc,w_b]$, in general we only have that $\ord_p\left(\Phi'\right) \geq -\delta'$.
\end{rem}

When one of the other conditions in Theorem~\ref{thm:KedlayaTuitman} is not satisfied,
we can use the alternative bound below. Recall that our family of
smooth projective hypersurfaces $\mathcal{X}/\mathcal{S}$ is defined by the homogeneous
polynomial $P \in \ZZ_q[t][x_0,\dotsc,x_n]$.

\begin{thm} \label{thm:Gerkmann}
Define the matrices $\Delta_k$ over $\QQ_q(t)$ as in
Definition~\ref{defn:Deltak}.
Let $D \subset \mathbf{P}^1(\bar{\QQ}_q)$ be a residue disk
and for any point $z \in D$ put
\begin{eqnarray*}
\mu_z &=& \sum_{k=2}^n \ord_z\left(\Delta_k^{-1}\right), \\
\nu_z &=& \ord_z\left(\Delta_{n+1}^{-1}\right).
\end{eqnarray*}
For $N \in \NN$, define
\begin{align*}
h(N) = \max \left\{ i \in \NN : i+(n-1)+\ord_p ((n-1)!)-n \floor{\log_p(p(n+i)-1)} < N \right\},
\end{align*}
and put
\[
\beta_z = \begin{cases}
-\mu_z -(p(n+h(N))-n) \nu_z & \mbox{if $z \neq \infty$}, \\
-\mu_z -(p(n+h(N))-n) \nu_z + p h(N) \deg_t(P) & \mbox{if $z = \infty$}.
\end{cases}
\]
Then $\Phi$ is congruent modulo $p^N$ to a matrix
$\tilde{\Phi} \in M_{b \times b}(\QQ_q(t))$ for which
\begin{equation*}
\ord_z\bigl(\tilde{\Phi}\bigr) \geq -\beta_z,
\end{equation*}
for all points $z \in D$.
\end{thm}

\begin{proof}
First we extend $\sigma$ to the ring of overconvergent functions:
\begin{align*}
A^{\dag} =
&\Bigl\{ \sum_{i_0,\dotsc,i_{n+3}=0}^{\infty} a_{i_0, \dotsc, i_{n+3}}
\frac{x_0^{i_0} \dotsm x_n^{i_{n}}t^{i_{n+1}}}{r^{i_{n+2}} P^{i_{n+3}}} \; : \;
a_{i_0, \dotsc i_{n+3}} \in \QQ_q, \; \\
&\exists c > 0 \text{ s.t.} \lim_{i_0+\dotsb+i_{n+3} \rightarrow \infty} \bigl(\ord_p(a_{i_0, \dotsc, i_{n+3}} ) -
c(i_0+\dotsb+i_{n+3})\bigr) \geq 0 \Bigr\},
\end{align*}
by putting $\sigma(x_i) = x_i^p$ for $0 \leq i \leq n$. Note that
\begin{equation*}
\sigma\left(\frac{1}{P}\right) =
    P^{-p} \left( 1-\frac{P^p-\sigma(P)}{P^p} \right)^{-1}
\end{equation*}
is an element of $A^{\dag}$ since
\begin{equation*}
\ord_p\left(P^p-\sigma(P)\right) \geq 1.
\end{equation*}
We use the notation and terminology from Section~\ref{sec:Connection}.
It is known that the de Rham cohomology of
$A^{\dag}/\QQ_q \langle t,1/r \rangle^{\dag}$
is isomorphic to the rigid cohomology of $U/S$, and that the action of
$F_p$ on the rigid cohomology of $U/S$ is induced by $\sigma$. Recall
that our basis vectors for $\Hrig(U/S)$
are of the form $x^u \Omega / P^{\ell}$ with $x^u \in B_{\ell}$ and
$\ell \leq n$.  We observe that
\begin{equation*}
p^{-1} \Frob_p \left(\frac{x^u \Omega}{P^{\ell}} \right) \equiv
\sum_{i=0}^{\infty} \eta_i p^{n-1+i} \left(\frac{P^p-\sigma(P)}{p} \right)^i
(x_0 \dotsm x_n)^{p-1} \left( \frac{x^{pu} \Omega}{P^{p(\ell+i)}} \right)
\end{equation*}
in $\Hrig^n(U/S)$, where $\eta_i \in \NN$ is defined by the equality
$(1-y)^{-\ell} = \sum_{i=0}^{\infty} \eta_i y^i$.
Using Algorithm~\ref{alg:PoleRed}, we can write
\begin{equation} \label{eqn:Froblift}
\eta_i p^{n-1+i} \left(\frac{P^p-\sigma(P)}{p} \right)^i
(x_0 \dotsm x_n)^{p-1} \left( \frac{x^{pu} \Omega}{P^{p(\ell+i)}} \right) \equiv
\frac{\gamma_{i,1} \Omega}{P^1}+\dotsb+\frac{\gamma_{i,n} \Omega}{P^n},
\end{equation}
where $\gamma_{i,j}$ is contained in the $L$-span of $B_j$ for all $i \geq 0$ and
$0 \leq j \leq n$.

Actually, we can slightly modify
Algorithm~\ref{alg:Decompose}, so that we only have to solve systems of the
form $\Delta_{n+1} v = w$ as long as the pole order is at least~$n+1$.
Indeed, we may assume, without loss of generality, that $Q=x^v$ is a monomial,
and can find some other monomial $x^w$ such that $x^{v-w}$ is of degree
$(n+1)d-(n+1)$. Now we apply Algorithm~\ref{alg:Decompose} to $x^{v-w}$,
noting that $B_{n+1}=\emptyset$, and multiply the output by~$x^w$ to obtain
the decomposition of~$x^v$.

Note that the left-hand side of Equation~\eqref{eqn:Froblift} does not have a
pole at $z \neq \infty$, and has order at least $-i p \deg_t(P)$ at $z=\infty$.
When applying Algorithm~\ref{alg:PoleRed} to this expression, as long as the
pole order is at least~$n+1$, the order at~$z$ drops by at most $\nu_z$ in every
reduction step, and it drops by at most $\mu_z$ in the remaining reduction steps.
This implies that
\begin{align} \label{al:ordz}
\ord_z(\gamma_{i,j}) &\geq
\begin{cases}
\mu_z + (p(n+i)-n) \nu_z                 &\mbox{if } z \neq \infty, \\
\mu_z + (p(n+i)-n) \nu_z - pi \deg_t(P)  &\mbox{if } z=\infty.
\end{cases}
\end{align}

For every $\tau \in S(\bar{\FF}_q)$, we
define lattices $\Lambda_{\tau,crys}$, $\Lambda_{\tau,\cB}$ in $\Hrig^n(U_{\tau})$
as in the proof of Theorem~\ref{thm:deltabound}. It follows from
\citep[Proposition 3.4.6]{AbbottKedlayaRoe2006}, Equation~\eqref{eqn:Froblift},
and the inclusion $(n-1)!\Lambda_{\tau,crys} \subset \Lambda_{\tau,\cB}$ that
\begin{equation*}
\frac{\gamma_{i,1} \Omega}{P^1}+\dotsb+\frac{\gamma_{i,n} \Omega}{P^n} \subset
p^{i+(n-1)-\ord_p((n-1)!)-n \floor{\log_p(p(n+i)-1)}} \Lambda_{\tau,\cB},
\end{equation*}
which implies that
\begin{equation*}
\ord_p(\gamma_{i,j}) \geq i+(n-1) - \ord_p((n-1)!) - n \floor{\log_p(p(n+i)-1)}.
\end{equation*}
The entries of $\Phi$ are coefficients of sums of the form
$\sum_{i=0}^{\infty} \gamma_{i,j}$. Now modulo $p^N$, we can
restrict this sum to terms for which $\ord_p(\gamma_{i,j})<N$,
and we can compute the order at $z$ of these terms using
\eqref{al:ordz}. This completes the proof.
\end{proof}

\begin{rem}
A result similar to, but weaker than, Theorem \ref{thm:Gerkmann}
was obtained by Gerkmann in \citep[Section 6]{Gerkmann2007}.
\end{rem}

\begin{thm} \label{thm:defD}
Let $N_{\Phi} \in \NN$. We can explicitly find $s \in \ZZ_q[t]$ and $K \in \NN$,
where $s$ divides some power of the polynomial $R$ from Definition~\ref{defn:resultant}, such that
$s \Phi$ is congruent modulo $p^{N_{\Phi}}$ to a matrix of polynomials of degree
less than $K$.
\end{thm}

\begin{proof}
On every residue disk $D \subset \mathbf{P}^1(\bar{\QQ}_q)$, we can
apply either Theorem~\ref{thm:KedlayaTuitman} (when it applies) or
Theorem~\ref{thm:Gerkmann} in order to find numbers $\theta_z \in \NN_0$
such that $\Phi$ is congruent modulo~$p^N$ to a matrix
$\tilde{\Phi}\in M_{b \times b}(\QQ_q(t))$ for which $\ord_z(\tilde{\Phi}) \geq -\theta_z$
for all $z \in D$.
By Theorem~\ref{thm:Gerkmann}, we can take $\theta_z=0$ for $z \neq \infty$ if
$R(z) \neq 0$, so that $\theta_z$ vanishes for all but finitely many $z \in \mathbf{P}^1(\bar{\QQ}_q)$.
Moreover, by Theorem~\ref{thm:KedlayaTuitman}, we can also take $\theta_z=0$
whenever the matrix~$M$ does not have a pole in the residue disk at~$z$.
Finally, we may assume that $\theta_z=\theta_{z'}$ if $z,z'$ are conjugates over~$\QQ_q$.
We now define
\begin{align*}
s &= \prod_{z \neq \infty, \ord_p(z) \geq 0} (t-z)^{\theta_z}
     \prod_{z \neq \infty, \ord_p(z) < 0}\left(\frac{t}{z}-1\right)^{\theta_z},
&K&= \left(\sum_{z} \theta_z \right) +1,
\end{align*}
which satisfy all the required conditions.
\end{proof}

We compute the matrix $\Phi$ to $t$-adic precision $K$ and $p$-adic
precision $N_{\Phi}$ using Algorithm~\ref{alg:expansion}. For any
$\tau \in S(\bar{\FF}_q)$, we can now compute
\begin{equation*}
\Phi_{\tau} =
  s(\hat{\tau})^{-1} \left( s \Phi \bmod{t^{K}} \right)|_{t=\hat{\tau}}
  \bmod{p^{N_{\Phi}}}.
\end{equation*}
Since $\ord_p(s(\hat{\tau}))=0$, $\ord_p(\hat{\tau}) \geq 0$ and
$\ord_p(\Phi) \geq -\delta$, by Proposition~\ref{prop:matrixproductval}
the matrix $\Phi_{\tau}$ will also be correct to precision $N_{\Phi}$
provided that $\hat{\tau}$ is computed to $p$-adic precision $N_{\Phi}+\delta$.

\subsection{Computing the zeta function}

Now we want to compute the zeta function of the fibre $X_{\tau}$ of
our family $X/S$ lying over some $\tau \in S(\FF_{\mathfrak{q}})$,
where $\FF_{\mathfrak{q}}/\FF_q$ is a finite field extension.
Recall from Theorem~\ref{thm:hypersurface}
that the zeta function of $X_{\tau}$ is of the form
\begin{equation*}
Z(X_{\tau},T) = \frac{\chi(T)^{(-1)^n}}{(1 - T) (1 - \mathfrak{q}T) \dotsm (1 - \mathfrak{q}^{n-1}T)},
\end{equation*}
where $\chi(T) = \det \bigl( 1 - T \mathfrak{q}^{-1} \Frob_{\mathfrak{q}} | \Hrig^n(U_{\tau}) \bigr) \in \ZZ[T]$
denotes the reverse characteristic polynomial of the action
of $\mathfrak{q}^{-1} \Frob_{\mathfrak{q}}$
on $\Hrig^n(U_{\tau})$.

We start by computing the matrix of the action
of $\mathfrak{q}^{-1} \Frob_{\mathfrak{q}}$ on $\Hrig^n(U_{\tau})$.
Let us still denote $a=\log_p(\mathfrak{q})$. Recall that $\Phi_{\tau}$
is the matrix of the action of $p^{-1} \Frob_p$ on~$\Hrig^{n}(U_{\tau})$
with respect to the basis $\cB$. As this action is $\sigma$-semilinear,
we have that
\begin{equation*}
\Phi_{\tau}^{(a)} =
    \Phi_{\tau} \sigma(\Phi_{\tau}) \dotsm \sigma^{a-1}(\Phi_{\tau})
\end{equation*}
is the matrix of the action of $\mathfrak{q}^{-1} \Frob_{\mathfrak{q}}$
on $\Hrig^n(U_{\tau})$.

We now analyse the loss of $p$-adic precision when computing
the reverse characteristic polynomial
$\chi(T)=1+\sum_{i=1}^b \chi_i T^i=\det\bigl( 1 - T \Phi_{\tau}^{(a)}\bigr)$.

\begin{thm} \label{thm:preccharpoly}
Let $N_{\Phi} \in \NN$ be such that $N_{\Phi} \geq \delta$,
where $\delta$ is defined as in Definition~\ref{defn:delta}.
Moreover, suppose that $\tilde{\Phi}_{\tau}$ is an approximation to $\Phi_{\tau}$ satisfying
$\ord_p (\Phi_{\tau}-\tilde{\Phi}_{\tau}) \geq N_{\Phi}$.
Let us denote
\[
\tilde{\chi}(T) = 1 + \sum_{i=1}^b \tilde{\chi}_i T^i
                = \det\left( 1 - T \tilde{\Phi}_{\tau}^{(a)}\right).
\]
Then for all $1 \leq i \leq b$, we have
\[
\ord_p \left(\chi_i - \tilde{\chi}_i \right) \geq N_{\Phi}-\delta.
\]
\end{thm}

\begin{proof}
Recall from Theorem~\ref{thm:deltabound} that there exists a matrix
$W_{\tau} \in M_{b \times b}(\QQ_q)$ satisfying
$\ord_p(W_{\tau})+\ord_p(W_{\tau}^{-1}) \geq -\delta$ such that for
$\Phi_{\tau}'=W_{\tau} \Phi_{\tau} \sigma(W)^{-1}$
we have \mbox{$\ord_p(\Phi_{\tau}') \geq 0$}.

Defining the matrix
$\tilde{\Phi}_{\tau}'=W_{\tau} \tilde{\Phi}_{\tau} \sigma(W)^{-1}$, we find that
$\ord_p(\Phi'_{\tau}-\tilde{\Phi}_{\tau}') \geq N-\delta$ and in particular
$\ord_p(\tilde{\Phi}_{\tau}') \geq 0$. Thus, we obtain
\[
\ord_p \left( \det\left(1 - T (\Phi'_{\tau})^{(a)}\right)
            - \det\left(1 - T (\tilde{\Phi}'_{\tau})^{(a)}\right) \right) \geq N-\delta.
\]
Note that $(\Phi'_{\tau})^{(a)}= W_{\tau} \Phi_{\tau}^{(a)} W_{\tau}^{-1}$
and $(\tilde{\Phi}'_{\tau})^{(a)}= W_{\tau} \tilde{\Phi}_{\tau}^{(a)} W_{\tau}^{-1}$,
so that
\begin{align*}
\chi(T) &= \det\left(1 - T (\Phi'_{\tau})^{(a)}\right),
&\tilde{\chi}(T) &= \det\left(1 - T (\tilde{\Phi}'_{\tau})^{(a)}\right).
\end{align*}
This completes the proof.
\end{proof}

\begin{rem} \label{rem:workprecchi}
If we know $\Phi_{\tau}$ to $p$-adic precision $N_{\Phi}$, then
$\chi(T)$ is determined to precision $N_{\Phi}-\delta$.
However, we cannot compute $\chi(T)$ as in the proof of
Theorem~\ref{thm:preccharpoly}, since we do not know the matrix
$W_{\tau}$ explicitly. When computing with respect to our basis~$\cB$,
there will be loss of $p$-adic precision. The loss of precision
in computing $\Phi_{\tau}^{(a)}$ from $\Phi_{\tau}$ is at most
$(a-1)\delta$, and the loss of
precision in computing $\chi(T)$ from $\Phi_{\tau}^{(a)}$
is at most $(b-1) \delta$, by Proposition~\ref{prop:productval} and
Corollary~\ref{cor:delta}. Therefore, for $\chi(T)$ to be correct
to $p$-adic precision $N_{\Phi}-\delta$, it is sufficient to compute
$\chi(T)$ from $\Phi_{\tau}$ using $p$-adic working precision
\[
(N_{\Phi}-\delta)+\bigl((a-1)+(b-1)\bigr)\delta = N_{\Phi}+(a+b-3)\delta.
\]
\end{rem}

When $p \geq n$, one can improve Theorem~\ref{thm:preccharpoly} by taking into
account the Hodge numbers $h^{i,n-1-i}$ of $\HdR^{n}(\mathfrak{U}/\mathfrak{S})$.
Recall from Remark~\ref{rem:hnumbers} that $h^{i,n-1-i}=\card{B_i}$.

\begin{defn}
Define $\Gamma \colon [0,b] \rightarrow \RR$ to be the function whose graph
is the convex polygon in the plane whose left-most point is the origin and
which has slope~$i$ over the interval of the horizontal axis
\[
\left[h^{0,n-1} + \dotsb + h^{i-1,n-i}, h^{0,n-1} + \dotsb + h^{i,n-i-1}\right].
\]
Note that $\Gamma(b)=b(n-1)/2$ since $h^{i,n-1-i}=h^{n-1-i,i}$ for all $0 \leq i \leq n-1$.
\end{defn}

\begin{thm} \label{thm:pgeqn}
We continue with the notation of Theorem~\ref{thm:preccharpoly}.
Let \mbox{$N_{\Phi} \in \NN$} and suppose that $p \geq n$. If $\tilde{\Phi}_{\tau}$
is an approximation to $\Phi_{\tau}$ such that $\ord_p (\Phi_{\tau}-\tilde{\Phi}_{\tau}) \geq N_{\Phi}$
then, for all $1 \leq i \leq b$, we have
\[
\ord_p\left(\chi_i-\tilde{\chi}_i\right) \geq N_{\Phi} + a\Gamma(i-1).
\]
\end{thm}

\begin{proof}
Note that in this case $\delta=0$ and hence that $\ord_p(\Phi_{\tau}) \geq 0$.
By a result of Mazur~\citep[p.\ 665--666]{Mazur1972}, the map $p^{-1} \Frob_p$
sends $(H_i)_{\hat{\tau}} \cap \Lambda_{\tau,crys}$ into $p^i \Lambda_{\tau,crys}$,
where $\Lambda_{\tau,crys}$ is defined as in the proof of
Theorem~\ref{thm:deltabound} and $H_i$ as in Remark~\ref{rem:hnumbers}.
This implies that the so called Hodge polygon of the
$F$-crystal $(\Lambda_{\tau,crys},p^{-1} \Frob_p)$ lies above the graph of
$\Gamma$. From this it follows that the Hodge polygon of the $F$-crystal
$(\Lambda_{\tau,crys},\mathfrak{q}^{-1} \Frob_{\mathfrak{q}})$ lies
above the graph of $a\Gamma$. Hence we can find an invertible matrix
$W_{\tau} \in M_{b \times b}(\ZZ_{\mathfrak{q}})$ such that for all
$1 \leq i \leq b$, the sum of the valuations of any~$i$ different columns
of $W_{\tau} \Phi_{\tau}^{(a)} W_{\tau}^{-1}$ is at least $a\Gamma(i)$.
Note that
\[ \ord_p(W_{\tau }\Phi_{\tau}^{(a)} W_{\tau}^{-1}-W_{\tau } \tilde{\Phi}_{\tau}^{(a)} W_{\tau}^{-1}) \geq N_{\Phi}.\]
The coefficients $\chi_i$ and $\tilde{\chi}_i$ are alternating sums
of products of $i$ elements from different columns of
$W_{\tau }\Phi_{\tau}^{(a)} W_{\tau}^{-1}$
and $W_{\tau } \tilde{\Phi}_{\tau}^{(a)} W_{\tau}^{-1}$, respectively.
Therefore, the required bound follows from Theorem~\ref{prop:productval}.
\end{proof}

\begin{rem}
For $a=1$, Theorem~\ref{thm:pgeqn} was obtained by Lauder in \citep[Proposition 9.4]{Lauder2006} and
the general idea of using the Hodge filtration to lower $p$-adic precision bounds had already been
suggested before in \citep[Remark 1.6.4]{AbbottKedlayaRoe2006}. However, we have not been able
to find Theorem~\ref{thm:pgeqn} in the literature for $a \neq 1$.
\end{rem}

Now we determine the $p$-adic precision~$N_{\chi_i}$ to which we need to compute~$\chi_i$
in order to recover the integer polynomial~$\chi(T)$ exactly.

\begin{thm} \label{thm:N0}
In order to recover the integer polynomial~$\chi(T)$ exactly,
it suffices to compute $\chi_i$ to $p$-adic precision
\begin{equation*}
N_{\chi_i} = \floorbig{\log_p \bigl( 2 \bigl( b/i \bigr) \mathfrak{q}^{i (n-1) / 2} \bigr)} + 1.
\end{equation*}
\end{thm}

\begin{proof}
By Theorem~\ref{thm:weildeligne} and the short exact
sequence~\eqref{eqn:excision}, we have
\[
\chi(T)=\prod_{i=1}^b (1-\alpha_i T),
\]
where the $\alpha_i$ are algebraic integers of absolute
value $\mathfrak{q}^{(n-1)/2}$ that are permuted under the
map $\alpha \mapsto \mathfrak{q}^{n-1}/\alpha$. If we denote
$s_j = \sum_{i=1}^{b} \alpha_i^j$, then clearly
\[
|s_j| \leq b \mathfrak{q}^{j (n-1)/2}.
\]
for all $1 \leq j \leq b$. Moreover, if we write
$\chi(T) = 1+\sum_{i=1}^{b} \chi_i T^i$, then by the Newton--Girard
identies we have
\begin{equation} \label{eq:recursion}
s_j+j \chi_j = - \sum_{i=1}^{j-1} s_{j-i} \chi_i.
\end{equation}
This means that if we are given $\chi_1,\dotsc,\chi_{j-1}$, then
we can limit $\chi_j$ to an explicit  disk in the complex plane of
radius $(b/j) \mathfrak{q}^{j (n-1) / 2}$. Therefore,
if we know each $\chi_i$ to $p$-adic precision $N_{\chi_i}$ satisfying
\[
p^{N_{\chi_i}} > \frac{2 b}{i} \mathfrak{q}^{i (n-1) / 2},
\]
we can determine $\chi(T)$ exactly using the recursion~\eqref{eq:recursion}.
\end{proof}

\begin{rem}
This bound was first obtained by Kedlaya in~\citep[]{Kedlaya2007},
although it does not appear there in exactly this form.
\end{rem}

\begin{thm} \label{thm:precPhitau}
Let $N_{\chi_i}$ be defined as in Theorem~\ref{thm:N0}.  In order to
compute $\chi(T)$ exactly, it is sufficient to compute~$\Phi_{\tau}$
with $p$-adic precision
\begin{align*}
N_{\Phi} &= \max_{1 \leq i \leq b} \left\{ N_{\chi_i} \right\} +\delta.
\intertext{If moreover $p \geq n$, then this can be improved to}
N_{\Phi} &= \max_{1 \leq i \leq b} \left\{ N_{\chi_i} -a\Gamma(i-1) \right\}.
\end{align*}
\end{thm}

\begin{proof}
This follows easily by combining Theorem~\ref{thm:N0} with
Theorem~\ref{thm:preccharpoly} and Theorem~\ref{thm:pgeqn}, respectively.
\end{proof}

\begin{rem} \label{rem:epsilon}
If the sign $\epsilon = \pm 1$ is known for which
$\det \bigl(\Phi_{\tau}^{(a)} \bigr) = \epsilon \mathfrak{q}^{b(n-1)/2}$,
then this can be improved further. Since
$\prod_{i=1}^b \alpha_i = \epsilon \mathfrak{q}^{b(n-1)/2}$, and
the $\alpha_i$ are permuted under the map
$\alpha \mapsto \mathfrak{q}^{n-1}/\alpha$, we have
\begin{equation*}
\chi_{b-i}=\epsilon (-1)^{b} \mathfrak{q}^{(n-1)(b/2-i)} \chi_b.
\end{equation*}
So $\chi(T)$ is uniquely determined already by
$\chi_1,\dotsc,\chi_{\lfloor b/2 \rfloor}$, and it is sufficient
to take the maxima in Theorem~\ref{thm:precPhitau} running only over
$1 \leq i \leq \floor{b/2}$.

It is well known that $\epsilon = 1$ when $n$ is even, but when $n$
is odd $\epsilon$ is usually not known. In practice it is then often
still possible to use a smaller precision by computing $\epsilon$ first.
Let $j$ be the smallest positive integer such that $\chi_{\ceil{b/2} - j} \neq 0$.
To recover $\chi_0, \dotsc, \chi_{\floor{b/2}+j}$, it is sufficient to take
the maxima in Theorem~\ref{thm:precPhitau} running only over
$1 \leq i \leq \floor{b/2}+j$. This allows us to determine $\epsilon$ from
the two coefficients $\chi_{\ceil{b/2}-j}$ and $\chi_{\floor{b/2}+j}$.
\end{rem}

We now formalise the complete algorithm for computing $Z(X_{\tau},T)$
in Algorithm~\ref{alg:complete}.

\begin{algorithm}
\caption{Compute $Z(X_{\tau},T)$.}
\label{alg:complete}
\begin{algorithmic}
\vspace{1mm}
\Require $P \in \ZZ_q[t][x_0,\dotsc,x_n]$ homogeneous of degree $d$ satisfying Assumption~\ref{assump:diag} and $\tau \in S(\mathbf{F}_{\mathfrak{q}})$.
\Ensure  The zeta function $Z(X_{\tau},T)$ of the fibre $X_{\tau}$ lying over $\tau$.
\Procedure{ZetaFunction}{$P,\tau$}
\State \begin{compactenum}[{\hspace{1em} } 1.] \vspace{-1.24em}
\item Determine $N_{\Phi}$ from Theorem~\ref{thm:precPhitau}.
\item $N_{\Phi}' \gets N_{\Phi}+(a+b-3) \delta$
\item Determine $K \in \NN$ and $s \in \ZZ_q[t]$ from Theorem \ref{thm:defD}.
\item Compute $\Phi \gets$ \textsc{FrobSeriesExpansion($N_{\Phi},K)$}.
\item Determine $\hat{\tau} \in \mathcal{S}(\ZZ_{\mathfrak{q}})$ to $p$-adic precision $N_{\Phi}+\delta$.
\item Compute $\Phi_{\tau} \gets s(\hat{\tau})^{-1} \bigl( a \Phi \bmod{t^{K}} \bigr)|_{t=\hat{\tau}}$
      to $p$-adic precision $N_{\Phi}$, using $p$-adic working precision $N_{\Phi}+\delta$.
\item Compute $\chi(T) \gets \det\bigl(1-T \bigl(\Phi_{\tau} \sigma(\Phi_{\tau}) \dotsm \sigma^{a-1}(\Phi_{\tau}) \bigr)  \bigr)$ to $p$-adic precision $N_{\Phi}-\delta$,
      using $p$-adic working precision $N'_{\Phi}$.
\item Round $\chi(T)$ to $\ZZ[T]$ using the recursion~\eqref{eq:recursion}.
\item Set $Z(X_{\tau},T) \gets \bigl( \chi(T)^{(-1)^n} \bigr)/\bigl((1 - T) (1 - \mathfrak{q}T) \dotsm (1 - \mathfrak{q}^{n-1}T)\bigr)$.
\item \Return $Z(X_{\tau},T)$
\end{compactenum}
\EndProcedure
\end{algorithmic}
\end{algorithm}

\begin{rem}
The output of Algorithm~\ref{alg:complete} only depends on $X_{\tau}$.
In particular, we can also take a polynomial
$\bar{P} \in \FF_q[t][x_0,\dotsc,x_n]$ as input and at the start of
the algorithm take $P$ to be an arbitrary lift of $\bar{P}$. For the
complexity analysis in the next section, we thus take the input size
to be the size of $\bar{P}$.  However, from a practical point of view,
it is convenient to keep the lift $P$ as the input, since:
\begin{enumerate}
\item the matrices $M, \Phi_0, C, \Phi, \Phi_{\tau}$ do depend on $P$,
\item Assumption~\ref{assump:diag} needs to hold for $P$,
\item the runtime and memory usage of the algorithm depend on $P$.
\end{enumerate}
\end{rem}

\section{Complexity}

\label{sec:Complexity}

In this section we determine the complexity of Algorithm~\ref{alg:complete}.
We denote $a' = \log_p(q)$, noting that $a'$ divides $a$,
and let $d_t$ denote the degree of $P$ in the variable~$t$.

We use the $\SoftOh(-)$ notation that ignores logarithmic factors,
i.e.\ $\SoftOh(f)$ denotes the class of functions
that lie in $\BigOh(f \log^k(f))$ for some $k \in \NN$.

Let us first revisit some results concerning the complexity of the,
sometimes basic, constituent operations.  We recall that two $k$-bit
integers can be multiplied in $\SoftOh(k)$ bit operations, and that
two degree-$k$ polynomials can be multiplied in $\SoftOh(k)$ ring
operations.  We let $\omega$ denote an exponent for matrix
multiplication, so that two $k \times k$ matrices can be multiplied
in $\BigOh(k^{\omega})$ ring operations. An invertible $k \times k$ matrix
can then be inverted in $\BigOh(k^{\omega})$ ring operations as well.
Moreover, it is known~\citep{Williams2012} that one can take $\omega \leq 2.3729$.
Finally, we point out that the characteristic polynomial of a matrix can be
computed in $\BigOh(b^{\omega} \log(b))$ field operations using
an algorithm of Keller-Gehrig~\citep{KellerGehrig1985}.

Next we consider specific $p$-adic operations, referring the reader to
Hubrechts~\citep{Hubrechts2010} for further details.  First, images of elements
of $\QQ_{\mathfrak{q}}$ under~$\sigma^i$, for $0 < i < a$, can be computed to
$p$-adic precision~$N$ in time $\SoftOh(a \log^2(p) + a N \log(p))$.  Second,
the Teichm\"uller lift of an element of $\FF_{\mathfrak{q}}$ can be computed
to precision~$N$ in time $\SoftOh(a N \log^2(p))$.

We start by estimating the degrees of the numerator and denominator of the
connection matrix~$M$.

\begin{prop}
The degrees of $H$, $R$ from Proposition~\ref{thm:denom}, and
$G$, $r$ from Section~\ref{sec:DifferentialSystem} are all
$\BigOh(n(de)^n d_t) \subset \SoftOh((de)^n d_t)$.
\end{prop}

\begin{proof}
Note that $\Delta_k$ in Definition~\ref{defn:resultant} is a square matrix
of degree~$d_t$, with
\[
{kd-1 \choose n} \leq \biggl( \frac{e(kd-1)}{n} \biggr)^n < (de)^n
\]
columns, where $e$ denotes the base for the natural logarithm. The result
follows easily from this. Note that the degrees of the numerators and
denominators of all intermediate results in Algorithm~\ref{alg:Connection}
are also $\SoftOh((de)^n d_t)$.
\end{proof}

Next we estimate the precisions that we require.

\begin{prop}
All $p$-adic precisions that we use lie in $\SoftOh(a d^n \log(d_t))$
and $\deg(s), K$ are both $\SoftOh(apd^n (de)^n d_t)$.
\end{prop}

\begin{proof}
Note that $b \in \BigOh(d^n)$ and $\delta \in \BigOh(n)$.
In Theorem~\ref{thm:precPhitau}, we have
\begin{align*}
\max_{1 \leq i \leq b} \{N_{\chi_i}\} \in \BigOh\bigl(a n b + \log(b) \bigr)
            &\subset \SoftOh\bigl(a d^n \bigr),
&N_{\Phi}   &\in \SoftOh(a d^n).
\end{align*}
The precisions $N'_{\Phi}$ and $N_{\Phi} \pm \delta$ in
Algorithm~\ref{alg:complete} are then $\SoftOh(ad^n)$ as well.
It follows from Theorem~\ref{thm:Gerkmann} that in
Theorem~\ref{thm:defD} we can take
\begin{align*}
\deg{s} &\leq \deg  \Bigl( \prod_{k=2}^n \det(\Delta_k) \Bigr) + (p(n+h(N_{\Phi}))-n) \deg(\det(\Delta_{n+1})), \\
K &\leq \deg(s)+ 1+\deg \Bigl(\prod_{k=2}^n \Delta_k^{-1}\Bigr) + (p(n+h(N_{\Phi}))-n) \deg(\Delta_{n+1}^{-1}) + ph(N_{\Phi}) d_t.
\end{align*}
Consequently, we obtain
\[
\deg(s), K \in \SoftOh(apd^n (de)^n d_t).
\]

The $p$-adic precisions $N_{\Phi_0}$, $N_C$, $N_M$, $N_{C^{-1}}$, $N'_{C}$,
and $N'_{C^{-1}}$ in Theorem~\ref{thm:Ni} are in $\SoftOh(ad^n \log(d_t))$,
noting that the logarithms that appear there are to base~$p$. Finally, the
remaining $p$-adic precisions $N'_M$ and $N'_{\Phi}$ are also
$\SoftOh(a d^n \log(d_t))$ by Remark~\ref{rem:precgm} and
Corollary~\ref{cor:NPhi0prime}, respectively.
\end{proof}

We now analyse the computation of the connection matrix~$M$.
\begin{prop}
The computation of the connection matrix~$M$ using
Algorithm~\ref{alg:Connection} requires
\begin{align*}
\mbox{time: }  & \SoftOh\bigl(a a' \log(p) (d^{n(\omega+2)} e^{n(\omega+1)}+ d^{5n}e^{3n} ) d_t\bigr), \\
\mbox{space: } & \SoftOh(a a' \log(p) d^{4n}e^{3n} d_t).
\end{align*}
\end{prop}

\begin{proof}
We first need to construct and invert the matrices~$\Delta_k$.  This is
dominated by the inversion, which requires $\BigOh\bigl((de)^{n \omega}\bigr)$
operations in the ring $\QQ_q[t]$ to $p$-adic
precision~$\SoftOh(a d^n \log(d_t))$. As there are $\BigOh(n)$ of
these matrices, this takes time
\[
\SoftOh\bigl((de)^{n \omega} (a' \log(p)) (a d^n \log(d_t)) ((de)^n d_t)\bigr) =
    \SoftOh\bigl(a a' \log(p) d^{n(\omega+2)} e^{n(\omega+1)} d_t\bigr).
\]
Then we multiply each of the monomials in our basis with
$-k (\partial P / \partial t)$ for some $1 \leq k \leq n$ and
reduce the product to the basis by repeatedly using
Algorithm~\ref{alg:Decompose}.  For each of these monomials this
takes time
\[
\SoftOh\bigl((de)^{2n} (a' \log(p)) (a d^n \log(d_t)) ((de)^n d_t)\bigr) =
    \SoftOh\bigl(a a' \log(p) d^{4n}e^{3n} d_t\bigr),
\]
because of the quadratic complexity of the matrix-vector product.
There are $b \in \BigOh(d^n)$ monomials in our basis and hence this
takes time $\SoftOh(a a' \log(p) d^{5n}e^{3n} d_t)$.

During this computation we have to store $\BigOh(n)$ matrices
and vectors of size
\[
\SoftOh\bigl((de)^{2n} (a' \log(p)) (a d^n \log(d_t)) ((de)^n d_t)\bigr),
\]
which completes the proof.
\end{proof}

Next we consider the computation of the matrix $\Phi_0$.

\begin{prop} \label{prop:complexityPhi0}
The computation of the matrix~$\Phi_0$ with Algorithm~\ref{alg:Diagfrob} requires
\begin{align*}
\mbox{time: }  & \SoftOh\bigl(a^3 p d^{4n} \log^3(d_t)\bigr), \\
\mbox{space: } & \SoftOh\bigl(a \log(p) d^{2n} \log(d_t)\bigr).
\end{align*}
\end{prop}

\begin{proof}
In Proposition~\ref{prop:MR}, we have $\mathcal{R} \in \SoftOh(N'_{\Phi_0})$.
In Definition~\ref{defn:alpha}, the sums
\begin{equation*} \label{eqn:ifactor}
\left(\frac{u_i+1}{d} \right)_r \sum_{j=0}^{r} \frac{\bigl(p a_i^{p-1}\bigr)^{r-j}}{(m-pj)!j!}
\end{equation*}
consist of $\BigOh(\mathcal{R})$ terms. Note that each term can be computed from the previous one in $\BigOh(p)$ operations
in $\ZZ_p$. For each $r$, the sum can therefore be computed in time $\BigOh(p \mathcal{R} N'_{\Phi_0})$. We have to consider
$\BigOh(\mathcal{R})$ values of $r$, so each $\alpha_{u,v}$ can be computed in time
\[
\SoftOh\bigl(np \mathcal{R}^2 N'_{\Phi_0}\bigr) \subset \SoftOh\bigl(a^3 p d^{3n} \log^3(d_t)\bigr).
\]
We need to compute $b \in \BigOh(d^n)$ of these $\alpha_{u,v}$, so the computation of $\Phi_0$
takes time $\SoftOh(a^3 p d^{4n} \log^3(d_t))$.

The required space is dominated by the size of the output, which is
\[
\SoftOh\bigl(b \log(p) N'_{\Phi_0}\bigr) \subset \SoftOh\bigl(a \log(p) d^{2n} \log(d_t)\bigr). \qedhere
\]
\end{proof}

\begin{rem}
Note that the time complexity in Proposition~\ref{prop:complexityPhi0}
is quasilinear in~$p$, while in the work of Lauder~\citep{Lauder2004a}
it is quasiquadratic.  The main reason for this is that Lauder computed
in the totally ramified extension~$\QQ_p(\pi)$ with $\pi^{p-1}=-p$,
where a single multiplication already takes time quasilinear in~$p$.  It will turn out
that this crucial improvement also decreases the overall time complexity
of the deformation method from being quasiquadratic to quasilinear in~$p$.

We should mention that there is a small downside to our approach.  The time
complexity in Proposition~\ref{prop:complexityPhi0} is quasicubic in~$a$,
while by using fast exponentials over $\QQ_p(\pi)[[z]]$, this can be
decreased to being quasiquadratic in~$a$, which again has an effect on the
entire deformation method.  We address this in the following proposition.
\end{rem}

\begin{prop} \label{prop:compPhi0}
Alternatively, the matrix~$\Phi_0$ can be computed in
\begin{align*}
\mbox{time: }  &\SoftOh\bigl(a^2 p d^{2n} (p + d^n) \log^2(d_t) \bigr), \\
\mbox{space: } &\SoftOh\bigl(a^2 p^2 d^{2n} \log^2(d_t)\bigr).
\end{align*}
\end{prop}

\begin{proof}
In Proposition~\ref{prop:MR}, we have $\mathcal{M} \in \SoftOh(pN'_{\Phi_0})$.
Let $\QQ_p(\pi)$ denote the totally ramified extension of $\QQ_p$ with $\pi^{p-1}=-p$.
Recall from the proof of Proposition~\ref{prop:coefbound} that in Definition~\ref{defn:alpha},
up to a factor $(-1)^r (\pi a_i)^{m-(p-1)r}$, the sum
\begin{align*}
\sum_{j=0}^{r} \frac{(p a_i^{p-1})^{r-j}}{(m-pj)!j!}
\end{align*}
is equal to the coefficient $\lambda_{m}$ of $x^m$ in the power series expansion of $\exp(\pi a_i(x-x^p))$. However,
the power series expansion of $\exp(\pi a_i(x-x^p))$ modulo $x^{\mathcal{M}+1}$ can be computed in
$\SoftOh(\mathcal{M})$ operations in $\QQ_p(\pi)$ following Brent~\citep{Brent1976}. Since
a single operation in $\QQ_p(\pi)$ takes time $\SoftOh(pN'_{\Phi})$, precomputing these
power series expansions for all $0 \leq i \leq n$ takes time
\[
\SoftOh\bigl(n p^2 (N'_{\Phi_0})^2\bigr) \subset \SoftOh\bigl(a^2 p^2 d^{2n} \log^2(d_t)\bigr).
\]
Each $\alpha_{u,v}$ can now be computed as in Proposition~\ref{prop:complexityPhi0} in time
\[
\SoftOh\bigl(p(N'_{\Phi_0})^2 \bigr) \subset \SoftOh\bigl(a^2 p d^{2n} \log^2(d_t)\bigr),
\]
so computing all $b \in \BigOh(d^n)$ of these $\alpha_{u,v}$ takes time
$\SoftOh(a^2 p^2 d^{3n} \log^2(d_t))$. Hence $\Phi_0$
can be computed in time $\SoftOh(a^2 p d^{2n} (p + d^n) \log^2(d_t))$.

The space requirement is dominated by that of the power series expansions of $\exp(\pi a_i(x-x^p))$ modulo $x^{\mathcal{M}+1}$ for $0 \leq i \leq n$
and is therefore given by
\[
\SoftOh\bigl(n \mathcal{M} p N'_{\Phi_0}\bigr) \subset \SoftOh\bigl(a^2 p^2 d^{2n} \log^2(d_t)\bigr). \qedhere
\]
\end{proof}

We now consider the computation of the power series expansion of the
matrix~$\Phi$.

\begin{prop}
Assume that the matrices $M = G/r$ and $\Phi_0$ have been computed already.
The subsequent computation of the power series expansion of the matrix~$\Phi$
in Algorithm~\ref{alg:expansion} then requires
\begin{align*}
\mbox{time: }  &\SoftOh(a^2 a' p d^{n(\omega+4)}e^{2n} d_t^2), \\
\mbox{space: } &\SoftOh(a^2 a' p d^{5n} e^n d_t).
\end{align*}
\end{prop}

\begin{proof}
The computation of the power series expansion of~$\Phi$ comprises
three steps, namely the computation of the matrices $C$, $\sigma(C)^{-1}$
and the matrix product $C \Phi_0 \sigma(C)^{-1}$.

As each of the $K$ steps in the computation of $C$ is dominated by the
computation of $\SoftOh((de)^n d_t)$ matrix products, the matrix~$C$ can be
computed in time
\begin{equation*}
\SoftOh\bigl(K ((de)^n d_t) b^{\omega} (a' \log (p)) (a d^n \log (d_t))\bigr)
    \subset \SoftOh\bigl(a^2 a' p d^{n(\omega + 4)} e^{2n} d_t^2 \bigr).
\end{equation*}
Similarly, the matrix $C^{-1}$ can be computed in time
\begin{equation*}
\SoftOh\bigl( (K/p) ((de)^n d_t) b^{\omega} (a' \log (p)) (ad^n \log (d_t)) \bigr)
    \subset \SoftOh\bigl( a^2 a' \log(p) d^{n(\omega+4)} e^{2n} d_t^2 \bigr).
\end{equation*}
Moreover, applying $\sigma$ to the matrix $C^{-1}$ takes time
\begin{equation*}
\SoftOh\bigl( (K/p) b^2 \bigl(a' \log^2(p) + a' (a d^n \log(d_t)) \log(p) \bigl) \bigr)
\subset \SoftOh\bigl( a^2 a' \log^2(p) d^{5n} e^n d_t \bigr).
\end{equation*}
Finally, the matrix product
$C \Phi_0 \sigma(C)^{-1}$ can be computed in time
\begin{equation*}
\SoftOh\bigl( b^{\omega} K (a' \log(p)) (a d^n \log(d_t)) \bigr)
    \subset \SoftOh\bigl( a^2 a' p d^{n(\omega + 3)} e^n d_t \bigr).
\end{equation*}
The result on the time complexity now follows.

The space requirement is dominated by the matrix~$C$, which has size
\begin{equation*}
\SoftOh\bigl(b^2 K (a' \log(p)) (a d^n \log(d_t))\bigr)
    \subset \SoftOh(a^2 a' p d^{5n} e^n d_t). \qedhere
\end{equation*}
\end{proof}

We now move on to the computation of the matrix~$\Phi_{\tau}$.

\begin{prop}
The computation of the matrix~$\Phi_{\tau}$ from the matrix~$\Phi$
and $\tau \in S(\FF_{\mathfrak{q}})$ requires
\begin{align*}
\mbox{time: }  &\SoftOh\bigl(a^2 a' p d^{5n} e^n d_t \bigr), \\
\mbox{space: } &\SoftOh\bigl(a^2 a' p d^{5n} e^n d_t \bigr).
\end{align*}
\end{prop}

\begin{proof}
We first recall that the Teichm\"uller lift
$\hat{\tau} \in \mathcal{S}(\ZZ_{\mathfrak{q}})$
can be computed to $p$-adic precision $N_{\Phi}+\delta \in \SoftOh(a d^n)$
in time $\SoftOh(a^2 d^n \log^2(p))$.  Next, we observe that the
scalar-matrix product $s \Phi \bmod t^K$ over~$\QQ_q[t]$
requires time
\begin{equation*}
\SoftOh\bigl( b^2 K a' (a d^n) \log(p) \bigr)
    \subset \SoftOh\bigl( a^2 a' p d^{5n} e^n d_t \bigr).
\end{equation*}
Finally, we consider the substitution of $\hat{\tau}$
into the $b^2$ entries of the matrix $s \Phi \bmod t^K$.
Each of these can be thought of as a modular composition of polynomials
over~$\QQ_{q}$, where the modulus~$m(t)$ is an irreducible polynomial defining
the extension $\QQ_{\mathfrak{q}} / \QQ_{q}$ as a quotient of $\QQ_q[t]$,
which is of degree~$a/a'$. However, care has to be taken to include the
additional reduction modulo~$m(t)$ of the polynomials of degree less than~$K$,
so that polynomials involved in the modular composition have degree less
than~$a/a'$.

Thus, the substitutions require time
\begin{equation*}
\SoftOh\Bigl( b^2 \bigl(K (a' \log(p)) (a d^n) + (a/a') (a' \log(p)) (a d^n) \bigr) \Bigr)
    \subset \SoftOh(a^2 a' p d^{5n} e^n d_t).
\end{equation*}
Clearly, evaluating and inverting $s(\hat{\tau})$ and performing the
scalar multiplication can be ignored, and the result on the time complexity now follows.

The space requirement is dominated by the matrix $s \Phi \bmod t^K$,
which has size
\begin{equation*}
\SoftOh(b^2 K (a' \log(p)) (a d^n)) \subset \SoftOh(a^2 a' p d^{5n} e^n d_t).
\qedhere
\end{equation*}
\end{proof}

Finally, we consider the computation of the polynomial $\chi(T)$.

\begin{prop}
The computation of $\chi(T)$ from $\Phi_{\tau}$ requires
\begin{align*}
\mbox{time: }  & \SoftOh(a^2  \log^2(p) d^{n(\omega+1)}), \\
\mbox{space: } & \SoftOh(a^2 \log(p) d^{3n}).
\end{align*}
\end{prop}

\begin{proof}
In order to compute $\Phi_{\tau}^{(a)}$ using fast exponentiation for
semilinear maps as in \citep[Lemma 32]{LauderWan2008}, we first need to apply powers of $\sigma$ to $\BigOh(b^2 \log(a))$
elements of $\QQ_{\mathfrak{q}}$ and then multiply $\BigOh(\log (a))$ matrices
of size $b \in \BigOh(d^n)$. This can be done in time
\begin{gather*}
\SoftOh\Bigl( b^2 \log(a) \bigl( a \log^2(p) + (a \log(p))(a d^n)  \bigr)
    + \log(a) b^{\omega} (a \log(p))(a d^n)  \Bigr)
\subset \SoftOh(a^2 \log^2(p) d^{n(\omega+1)}).
\end{gather*}
Next, we compute the reverse characteristic polynomial of matrix
$\Phi_{\tau}^{(a)} \in M_{b \times b}(\QQ_{\mathfrak{q}})$, which
can be accomplished in~$\BigOh(b^{\omega} \log(b))$ field operations.
This amounts to a time complexity of
\begin{equation*}
\SoftOh\bigl(b^{\omega} (a \log(p))(a d^n) \bigr)
    \subset \SoftOh\bigl( a^2 \log(p) d^{n(\omega+1)} \bigr).
\end{equation*}
Rounding this polynomial to $\ZZ[T]$ can be ignored.

We need to store $\BigOh(\log(a))$ matrices of size~$b$ with entries
in~$\QQ_{\mathfrak{q}}$.  This requires space
$\SoftOh(b^2 (a \log(p)) (a d^n)) \subset \SoftOh(a^2 \log(p) d^{3n})$.
\end{proof}

We can now state the total time and space requirements of
Algorithm~\ref{alg:complete}. Recall that $P \in \ZZ_q[t][x_0,\dotsc,x_n]$
denotes a homogeneous polynomial
of degree $d$ satisfying Assumption~\ref{assump:diag}
and that $\tau \in S(\mathbf{F}_{\mathfrak{q}})$, where
$\FF_{\mathfrak{q}}/\FF_q$ denotes a finite field extension
of characteristic $p$.
Moreover, we write $a=\log_p(\mathfrak{q})$, $a'=\log_p(q)$ and let
$d_t$ be the degree of $P$ in the variable $t$. Finally,
we let $e$ denote the base of the natural
logarithm and $\omega$ an exponent for matrix multiplication.

\begin{thm} \label{thm:totalcomplexity}
The computation of $Z(X_{\tau},T)$ using Algorithm~\ref{alg:complete} requires
\begin{align*}
\mbox{time: }  &\SoftOh\Bigl(
                a^3 p d^{4n} +
                a^2 a' p d^{n(\omega+4)} e^{2n} d_t^2+
                aa' \bigl(d^{n(\omega+2)} e^{n(\omega+1)}+ d^{5n} e^{3n}\bigr) d_t
                \Bigr), \\
\mbox{space: } &\SoftOh\bigl( a^2 a' p d^{5n} e^n d_t + a a' d^{4n} e^{3n} d_t \bigr).
\end{align*}
Alternatively, computing the matrix $\Phi_0$ as in the proof of Proposition~\ref{prop:compPhi0},
the computation of $Z(X_{\tau},T)$ requires
\begin{align*}
\mbox{time: }  &\SoftOh\Bigl(
                a^2 p^2 d^{2n} +
                a^2 a' p d^{n(\omega+4)} e^{2n} d_t^2+
                aa' \bigl(d^{n(\omega+2)} e^{n(\omega+1)}+ d^{5n} e^{3n}\bigr) d_t
                \Bigr), \\
\mbox{space: } &\SoftOh\bigl(
                a^2 p^2 d^{2n} +
                a^2 a' p d^{5n} e^n d_t +
                a a' d^{4n} e^{3n} d_t \bigr).
\end{align*}
\end{thm}

\begin{proof}
This follows by adding all complexities from the previous propositions and
leaving out terms that are dominated by other terms or powers of
logarithms of other terms.
\end{proof}

\begin{rem} In \citep{Lauder2004a}, Lauder took $d_t=1$ and showed that his
algorithm requires
\begin{align*}
\mbox{time: }  &\SoftOh\bigl(a^3 p^2 (d^{n(\omega+5)} e^{3n} + d^{6n} e^{5n}) \bigr), \\
\mbox{space: } &\SoftOh\bigl(a^3 p^2 d^{6n} e^{4n} \bigr).
\end{align*}
His main goal was to show that these complexities are $(pad^n)^{\BigOh(1)}$,
which was not the case for previously known algorithms such as
\citep{AbbottKedlayaRoe2006, LauderWan2008}.
Our Theorem~\ref{thm:totalcomplexity} improves Lauder's complexity bounds
by lowering the constants implicit in the exponent~$\BigOh(1)$.  To our
knowledge, the complexity bounds presented in Theorem~\ref{thm:totalcomplexity}
are therefore the best ones known.  Note that since a natural measure for the
input size is $\log(p) a d^n$, these bounds are only polynomial in the
input size provided $p$ is fixed, which is something that all $p$-adic
point counting algorithms tend to have in common.
\end{rem}

\section{Examples}
\label{sec:Examples}

In this section we apply Algorithm~\ref{alg:complete} to some examples
using our implementation\footnotemark.  This implementation
is restricted to the case $q = p$, i.e.\ to families of hypersurfaces
defined over a prime field.  In order to provide some context for the
runtimes presented below, note that all computations were carried out
on a machine with two Intel Core i7-3540M processors running at 3GHz and
with 8GB of RAM, but only used a single processor.  Moreover, timings were obtained using the C function
{\tt{clock()}} and are stated in minutes~(m) or seconds~(s).

\footnotetext{This implementation is available at
\url{https://github.com/SPancratz/deformation}.}

\subsection{Quintic curve}

We consider the family of genus six curves over $\ZZ$ given by the polynomial
\begin{equation*}
P=x_0^5 + x_1^5 + x_2^5 + t x_0 x_1 x_2^3,
\end{equation*}
which Gerkmann~\citep[\S 7.4]{Gerkmann2007} considers as an element of
$\ZZ_p[t][x_0,x_1,x_2]$ for $p=2,3,7$.  Note that these are, in fact,
three examples.  The connection matrix $M \in M_{12 \times 12}(\QQ(t))$
only has to be computed once, and turns out to have denominator $r=27t^5+3125$.
The set of exponents at each of the zeros of $r$ is $\{-1,0\}$, and
after changing basis by
\[
W=\mbox{diag}(t^{-1},t,t^{-2},t^{-1},1,1,1,1,1,t^2,t^2,1)
\]
as in Remark~\ref{rem:basischange}, the set of exponents at~$\infty$ is
$\{-2/3,2/3,1,4/3,7/3,8/3,13/3,14/3\}$.  Note that by
Remark~\ref{rem:epsilon}, we only need to determine the bottom
half of the coefficients of the polynomial $\chi(T)$ directly.

\subsubsection{Precisions}

\noindent
\textit{Prime $p=2$.}
We take $\log_p(\mathfrak{q})=50$ and let $\tau \in \FF_{\mathfrak{q}}$ be
a zero of the Conway polynomial of $\FF_{\mathfrak{q}}/\FF_p$, i.e. the
standard irreducible polynomial used to represent this extension.  We first
compute $\delta=0$ and $N_{\Phi}=N_{\Phi}'=153$.  As the roots of~$r$ are
$2$-adic integers and distinct  modulo~$2$, we can apply
Theorem~\ref{thm:KedlayaTuitman} everywhere. We find $\theta_z=320$ at all
zeros~$z$ of $r$ and $\theta_{\infty}=12$, so that we can take $s=r^{320}$
and $K=1613$. We now compute the remaining $p$-adic precisions
$N_{\Phi_0}=174$, $N_C=163$, $N_{C^{-1}}=164$, $N_M=187$,
$N_C'=184$, $N_{C^{-1}}'=183$, $N_{\Phi_0}'=176$, and $N_M'=188$. \\

\noindent
\textit{Prime $p=3$.}
We take $\log_p(\mathfrak{q})=40$ and let $\tau \in \FF_{\mathfrak{q}}$ be
a zero of the Conway polynomial of $\FF_{\mathfrak{q}}/\FF_p$.  We first
compute $\delta=0$ and $N_{\Phi}=N_{\Phi}'=122$. As the roots of~$r$ are all
contained in the residue disk at~$\infty$, we cannot apply
Theorem~\ref{thm:KedlayaTuitman} and have to apply Theorem~\ref{thm:Gerkmann}
instead. At each of the zeros $z$ of~$r$ we find $\mu_z=0$, $\nu_z=-1$, $\theta_z=397$
and at $\infty$ we find $\mu_{\infty}=-3$, $\nu_{\infty}=-2$, $\theta_{\infty}=793$, so that
we can take $s=r^{397}$ and $K=2779$. We now compute the remaining $p$-adic
precisions
$N_{\Phi_0}=137$, $N_C=129$, $N_{C^{-1}}=130$, $N_M=147$,
$N_C'=146$, $N_{C^{-1}}'=143$, $N_{\Phi_0}'=139$, and $N_M'=147$. \\

\noindent
\textit{Prime $p=7$.}
We take $\log_p(\mathfrak{q})=10$, and let $\tau \in \FF_{\mathfrak{q}}$ be
a zero of the Conway polynomial of $\FF_{\mathfrak{q}}/\FF_p$. We first
compute $\delta=0$ and $N_{\Phi}=N_{\Phi}'=31$.  As the zeros of $r$ are
$7$-adic integers and distinct modulo~$7$, we can apply
Theorem~\ref{thm:KedlayaTuitman} everywhere.  We find $\theta_z=224$ at all
zeros~$z$ of $r$ and $\theta_{\infty}=25$, so that we can take $s=r^{224}$ and
$K=1146$. We now compute the remaining $p$-adic precisions
$N_{\Phi_0}=38$, $N_C=34$, $N_{C^{-1}}=37$, $N_M=44$,
$N_C'=43$, $N_{C^{-1}}'=40$, $N_{\Phi_0}'=40$, and $N_M'=44$.

\subsubsection{Timings}

We now compare the performance of our FLINT implementation with the
timings reported by Gerkmann. To save space, we do not include the
polynomials $\chi(T)$ that we obtained from these computations.

\begin{center}
\begin{tabular}{l l l l l l l} \toprule
                & \multicolumn{2}{l}{$p = 2$}
                & \multicolumn{2}{l}{$p = 3$}
                & \multicolumn{2}{l}{$p = 7$} \\ \midrule
Computation     & P--T & G     & P--T  & G       & P--T & G     \\ \midrule
$M$             & 0.00s&       & 0.00s &         & 0.00s&       \\
$\Phi_0$        & 0.03s& 2.65m & 0.03s & 5.86m   & 0.01s& 1.31m \\
$\Phi$          & 0.67s& 1.33m & 1.28s & 1.38m   & 0.29s& 0.89m \\
$Z(X_{\tau},T)$ & 9.20s& 3.96m & 6.42s & 101.40s & 0.15s& 1.09m \\
Total           & 9.90s& 7.94m & 7.73s & 8.93m   & 0.45s& 3.29m \\ \bottomrule
\end{tabular}
\end{center}

\bigskip

Our timings in these examples are a factor of $50-500$ lower than the ones
provided by Gerkmann.

\subsection{Quartic surface}

We consider the family of quartic K3 surfaces over $\ZZ_3$ given by
\begin{equation*}
P=x_0^4 + x_1^4 + x_2^4 + x_3^4 + t x_0 x_1 x_2 x_3,
\end{equation*}
which Gerkmann considers in~\citep[\S 7.5]{Gerkmann2007}. The connection matrix
$M \in M_{21 \times 21}(\QQ(t))$ turns out to have denominator
$r=t^4-256$. The set of exponents at each of the zeros of $r$ is $\{-3/2,-1/2,0\}$,
and after changing basis by
\[
W=\mbox{diag}(t^{-2},1,1,1,1,1,1,1,1,1,t^{-1},1,1,1,1,1,1,1,1,1,1)
\]
as in Remark~\ref{rem:basischange}, the set of exponents  at $\infty$ is
$\{1,2,3\}$.

\subsubsection{Precisions}

We take $a=\log_3(\mathfrak{q})=20$, let $\alpha \in \FF_{\mathfrak{q}}$
be a zero of the Conway polynomial of $\FF_{\mathfrak{q}}/\FF_{3}$, and take
$\tau=\alpha^{2345}$.  We first compute $\delta=0$ and $N_{\Phi}=N_{\Phi}'=43$.
Since the zeros of $r$ are $3$-adic integers and different modulo $3$, we can apply
Theorem~\ref{thm:KedlayaTuitman} everywhere. We find $\theta_z=148$ at all zeros
of $r$ and $\theta_{\infty}=6$, so that we can take $s=r^{148}$
and $K=599$. We now compute the remaining $p$-adic
precisions $N_{\Phi_0}=65$, $N_C=53$, $N_{C^{-1}}=55$, $N_M=74$,
$N_C'=73$, $N_{C^{-1}}'=68$, $N_{\Phi_0}'=68$ and $N_M'=75$.

\subsubsection{Timings}

\begin{center}
\begin{tabular}{l l l} \toprule
Computation     & P--T & G      \\ \midrule
$M$             & 0.00s& 7.00s      \\
$\Phi_0$        & 0.01s& 45.26m \\
$\Phi$          & 0.22s& 19.90m \\
$Z(X_{\tau},T)$ & 0.76s& 18.66m \\
Total           & 0.99s& 83.82m \\ \bottomrule
\end{tabular}
\end{center}

\bigskip

As the final result of the computation we find that
$\mathfrak{q} \chi(T/\mathfrak{q})$ is equal to
\begin{multline*}
- 3486784401T^{21} - 39675197243T^{20} - 191506614866T^{19} - 482588946510T^{18} \\
- 552821487569T^{17} + 243001138765T^{16} + 1641410078472T^{15} + 1793016627512T^{14} \\
- 410199003010T^{13} - 2617001208822T^{12} - 1586643774924T^{11} + 1586643774924T^{10} \\
+ 2617001208822T^9 + 410199003010T^8 - 1793016627512T^7 - 1641410078472T^6 \\
- 243001138765T^5+ 552821487569T^4 + 482588946510T^3 + 191506614866T^2 \\
+ 39675197243T + 3486784401.
\end{multline*}

Our timings in this example are about $5,000$~times lower than the ones
presented by Gerkmann.

Additionally, we should mention that Gerkmann does not include timings for part
of his computations.  For example, he omits the time that is required for the
computation of the $p$-adic precision parameter that he calls $\delta$, which
involves solving $b^2$~differential equations similar to the one for the matrix~$C$.
Moreover, it appears that there are minor errors in the precision analysis, e.g.\
the final $p$-adic precision is not sufficient to recover the exact zeta function.
Finally, the polynomial~$\chi(T)$ provided by Gerkmann for this example does
not satisfy Theorem~\ref{thm:weildeligne}, so cannot be correct.

The remaining examples could not have been computed with previous implementations
of the deformation method and, to our knowledge, neither with any other point counting
method.  For example, Lauder noted that he could not compute the connection matrix
for a family of quintic curves or quartic surfaces given by a polynomial with more
than a \emph{few} nonzero terms.  Indeed, this was the main motivation for the work
in the PhD~thesis of the first author and the present paper.  We are now able to
compute the zeta function of e.g.\ quintic curves and quartic surfaces over small
finite fields given by a polynomial with \emph{all} of its coefficients nonzero.

\subsection{Generic quintic curve}

We consider the family of generic quintic curves over $\ZZ_{11}$ given by
\begin{equation*}
\begin{split}
P = x_0^5 + x_1^5 + x_2^5
+ t \bigl( & 3x_0^4 x_1-x_0^4 x_2+2 x_0 x_1^4+x_1^4 x_2+4 x_0 x_2^4+5 x_1 x_2^4 + x_0^3 x_1^2 \\
           & + x_0^3 x_2^2 + x_0^2 x_1^3+ x_1^3 x_2^2+x_0^2 x_2^3+x_1^2 x_2^3 + x_0^3 x_1 x_2 + x_0 x_1^3 x_2 \\
           & + x_0 x_1 x_2^3 + x_0^2 x_1^2 x_3 + x_0^2 x_1 x_2^2 + x_0 x_1^2 x_2^2 \bigr).
\end{split}
\end{equation*}
The connection matrix $M \in M_{12 \times 12}(\QQ(t))$ has denominator
$r = r_1 r_2$, with polynomials $r_1,r_2 \in \ZZ[t]$ that are irreducible
of degree $30$ and $48$, respectively. The set of exponents is $\{ 0,1 \}$
at the zeros of $r_1$ and $\{ -1,0 \}$ at the zeros of~$r_2$. Moreover,
the matrix $M$ has a simple pole at $\infty$ and the set of exponents
is $\{1,2\}$ there.

\subsubsection{Precisions}

We take $a=\log_{11}(\mathfrak{q})=10$ and let $\tau$ be a zero of the Conway polynomial of
$\FF_{\mathfrak{q}}/\FF_{11}$.
We first compute $\delta=0$ and $N_{\Phi}=N_{\Phi}'=31$.
Since the zeros of $r$ are $11$-adic integers and different modulo $11$, we can apply
Theorem~\ref{thm:KedlayaTuitman} everywhere. We find $\theta_z=352$ at the zeros of $r_2$
and $\theta_{\infty}=9$ at $\infty$. At the residue disk of a zero $z$ of $r_1$, noting that
$R$ has no other zeros there, we get a better bound by applying
Theorem~\ref{thm:Gerkmann} with $\mu_z=-1$, $\nu_z=0$ and find $\theta_z=1$, so that we can
take $s=r_1 r_2^{352}$ and $K=16936$. We now compute the remaining $p$-adic precisions
$N_{\Phi_0}=40$, $N_C=35$, $N_{C^{-1}}=36$, $N_M=47$, $N_C'=46$, $N_{C^{-1}}'=43$,
$N_{\Phi_0}'=42$ and $N_M'=47$.

\subsubsection{Timings}

\begin{center}
\begin{tabular}{l l} \toprule
Computation     & P--T \\ \midrule
$M$             & 4.43s     \\
$\Phi_0$        & 0.04s     \\
$\Phi$          & 3.76m     \\
$Z(X_{\tau},T)$ & 9.48s     \\
Total           & 3.99m     \\ \bottomrule
\end{tabular}
\end{center}

\bigskip

As the final result of the computation we find that~$\chi(T)$ is equal to
\begin{equation*}
\begin{split}
& 304481639541418099574449295360278774639038415066698088621947601 T^{12} \\
& \quad + 3777543732986291528931322507772938448980494046897871937792 T^{11} \\
& \quad + 23639674223084796290417361507756397439403378558130350 T^{10} \\
& \quad + 54141350391870148138663709375646947695242620108 T^9 \\
& \quad - 363231942297281636316475334779570949613459 T^8 \\
& \quad - 4138991673785569248268236480720472276 T^7 \\
& \quad - 28015243113507339254470240817992 T^6 - 159576046483273177468242676 T^5 \\
& \quad - 539921137173243550659 T^4 + 3102762464729708 T^3 \\
& \quad + 52231690350 T^2 + 321792 T + 1.
\end{split}
\end{equation*}

\subsection{Generic quartic surface}

We consider the family of generic quartic K3 surfaces over $\ZZ_{7}$ given by
\begin{equation*}
\begin{split}
P=x_0^4 + x_1^4 + x_2^4 + x_3^4
+ t \bigl( & -3 x_0^3 x_1 + 2 x_0^3 x_2 - 2 x_0 x_1 x_2 x_3 + x_0^3 x_3 - x_0 x_1^3 - 3 x_1^3 x_2 \\
           & + x_2^3 x_3 + 2 x_1^3 x_3 + x_0 x_2^3 - 2 x_1 x_2^3 - x_0 x_3^3 + x_1 x_3^3 \\
           & + 3 x_2 x_3^3 + x_0^2 x_1^2 + 3 x_0^2 x_2^2 + x_0^2 x_3^2 + 2 x_1^2 x_2^2 - 2 x_1^2 x_3^2 \\
           & + x_2^2 x_3^2 + 2 x_0^2 x_1 x_2 + x_0^2 x_1 x_3 + 3 x_0^2 x_2 x_3 - x_0 x_1^2 x_2 \\
           & + 2 x_0 x_1^2 x_3 + 3 x_1^2 x_2 x_3 - x_0 x_1 x_2^2 + 3 x_0 x_2^2 x_3 + x_1 x_2^2 x_3 \\
           & + 2 x_0 x_1 x_3^2 + 2 x_0 x_2 x_3^2 + 2 x_1 x_2 x_3^2 \bigr).
\end{split}
\end{equation*}
The connection matrix $M \in M_{21 \times 21}(\QQ(t))$ has denominator
$r = r_1 r_2 r_3$, with polynomials $r_1,r_2,r_3 \in \ZZ[t]$ that are
irreducible of degree $16$, $104$ and $108$, respectively.  The matrix~$M$
has a simple pole at $\infty$ and the set of exponents is $\{1,2,3\}$ there.

\subsubsection{Precisions}

We take $\tau$ to be  $1 \in \FF_7$. We first compute $\delta=0$ and
$N_{\Phi}=N_{\Phi}'=4$. Since we do not know the exponents of~$M$ at
its finite poles, we cannot use Theorem~\ref{thm:KedlayaTuitman} at poles
outside the residue disk at infinity. Applying Theorem~\ref{thm:Gerkmann}
at all the zeros $z$ of $R$, using the bound
$\ord_z(\Delta_k^{-1}) \geq -\ord_z(\det(\Delta_k))$, we find that we can
take $s = \det(\Delta_2)\det(\Delta_3)\det(\Delta_4)^{67}$, which has
degree~$25027$. However, most of the zeros of $R$ do not lie in the
residue disk of a pole of~$M$ and hence the corresponding factors can
be removed from~$s$, which decreases the degree of~$s$ to~$8833$.
We can apply Theorem~\ref{thm:KedlayaTuitman} at~$\infty$ to find
$\theta_{\infty}=-4$, so that we can take $K=8830$. We now compute
the remaining $p$-adic precisions $N_{\Phi_0}=22$, $N_C=12$, $N_{C^{-1}}=14$,
$N_M=30$, $N_C'=29$, $N_{C^{-1}}'=24$, $N_{\Phi_0}'=25$, and $N_M'=30$.

\subsubsection{Timings}

\begin{center}
\begin{tabular}{l l} \toprule
Computation     & P--T \\ \midrule
$M$             & 3.55m     \\
$\Phi_0$        & 0.02s     \\
$\Phi$          & 17.53m     \\
$Z(X_{\tau},T)$ & 6.7s     \\
Total           & 21.19m     \\ \bottomrule
\end{tabular}
\end{center}

\bigskip

As the final result of the computation we find that $7 \chi(T/7)$ is equal to
\begin{multline*}
7T^{21} - 5T^{20} + 6T^{19} - 6T^{18} + 4T^{17} - 11T^{16} + 5T^{15} - 9T^{14} + 4T^{13} + 3T^{12} \\
+ 4T^{11} + 4T^{10} + 3T^9 + 4T^8 - 9T^7 + 5T^6 - 11T^5 + 4T^4 - 6T^3 + 6T^2 - 5T + 7.
\end{multline*}

\subsection{Larger primes}

We consider the family of quartic surfaces over $\ZZ$ given by the polynomial
\begin{equation*}
P=x_0^4 + 2x_1^4 + 3x_2^4 + 4x_3^4 + t(x_0x_1x_2x_3 + 2 x_0^2 x_2^2 + 3x_0x_2^3)
\end{equation*}
which we consider as an element of $\ZZ_p[t][x_0,x_1,x_2,x_3]$ for various
primes $p$, most of which are much larger than those in the previous examples.
The connection matrix $M \in M_{21 \times 21}(\QQ(t))$ has denominator
$r = r_1 r_2 r_3 r_4$, with polynomials $r_1,r_2,r_3,r_4 \in \ZZ[t]$ that are
irreducible of degree $3$, $5$, $12$ and $16$, respectively. The set of
exponents at each of the zeros of $r$ is a subset of the set $\{-3/2,-1/2,0,1\}$,
and after changing basis by
\[
W=\mbox{diag}(t^{-1},1,1,1,1,1,1,1,1,1,1,1,1,1,1,t^{-1},1,1,t^{-1},1,t)
\]
as in Remark~\ref{rem:basischange}, the set of exponents  at $\infty$ is
$\{1,3/2,2,3\}$. We take $\tau$ to be $1 \in \FF_p$.

\subsubsection{Precisions}

For all primes $p$ that we consider, the zeros of $r$ are $p$-adic integers and different modulo $p$.
Therefore, we can apply Theorem~\ref{thm:KedlayaTuitman} everywhere. As an example, we determine the
precisions in the case $p=2^9+9$. We first compute $\delta=0$ and $N_{\Phi}=N'_{\Phi}=3$. We find
$\theta_z=1824$ at all zeros $z$ of $r$ and $\theta_{\infty}=4$, so that we can take $s=r^{1824}$ and $K=65668$.
We now compute the remaining $p$-adic precisions $N_{\Phi_0}=9$, $N_C=5$, $N_{C^{-1}}=7$, $N_M=14$,
$N_C'=13$, $N_{C^{-1}}'=8$, $N_{\Phi_0}'=11$ and $N_M'=14$.

\subsubsection{Timings}

\begin{center}
\begin{tabular}{l l l l l l} \toprule
$p$             & $2^2+1$ & $2^3+3$ & $2^4+1$ & $2^5+5$ & $2^6+3$ 	\\ \midrule
Computation     & 	  &         &         &         &               \\ \midrule
$M$             & 0.10s   & 0.10s   & 0.10s   & 0.10s  	& 0.10s	  	\\
$\Phi_0$        & 0.01s   & 0.00s   & 0.01s   & 0.01s 	& 0.00s	  	\\
$\Phi$          & 5.89s   & 9.19s   & 9.38s   & 20.06s 	& 42.18s       	\\
$Z(X_{\tau},T)$ & 0.07s   & 0.14s   & 0.08s   & 0.37s 	& 0.91s	  	\\
Total           & 6.07s   & 9.43s   & 9.57s   & 20.54s 	& 43.19s      	\\ \bottomrule
\end{tabular}
\end{center}

\begin{center}
\begin{tabular}{l l l l l l} \toprule
$p$             & $2^7 + 3$ & $ 2^8+1$	& $2^9+9$  	& $2^{10}+7$ 	& $2^{11}+5$	\\ \midrule
Computation     & 	    &          	&          	&            	& \\ \midrule
$M$             & 0.10s     & 0.10s	& 0.10s    	& 0.10s	 	& 0.10s \\
$\Phi_0$        & 0.00s     & 0.00s	& 0.00s       	& 0.00s	      	& 0.00s\\
$\Phi$          & 84.78s    & 166.68s	& 359.06s    	& 748.57s	& 1569.01s\\
$Z(X_{\tau},T)$ & 1.61s     & 3.62s	& 7.09s      	& 14.50s	& 32.03s\\
Total           & 86.49s    & 170.40s	& 366.25s    	& 763.18s	& 1601.15s\\ \bottomrule
\end{tabular}
\end{center}

\bigskip

Our timings in this example confirm that the running time of the algorithm is (quasi)linear in $p$
and the memory usage also turns out to be (quasi)linear in $p$ as predicted. In the case $p=2^{11}+5$, the computation
requires about 6 GB of memory. As an example, for the prime $p=2^{11}+5$ we find that $p \chi(T/p)$ is equal to
\begin{multline*}
2053 T^{21} - 4885 T^{20} + 6922 T^{19} - 7050 T^{18} + 1163 T^{17} + 7077 T^{16} - 12948 T^{15} \\
+ 12948 T^{14} - 9130 T^{13} + 3722 T^{12} + 128 T^{11} + 128 T^{10} + 3722 T^9 - 9130 T^8 \\
+ 12948 T^7 - 12948 T^6 + 7077 T^5 + 1163 T^4 - 7050 T^3 + 6922 T^2 - 4885 T + 2053.
\end{multline*}

\begin{rem}
In all of our timings, we have not included the time required to compute
the $p$-adic and $t$-adic precisions, since we used MAGMA for this. Note,
however, that we can readily determine $\det(\Delta_k)$ from the
$LUP$~decomposition of~$\Delta_k$ and that the factorisation of the
polynomials $r$, $R$ over $\QQ$ and $\FF_p$ was instantaneous in all
cases. The only step that required noticeably more time was the
computation of the exponents in the generic examples. For the family of
generic quintic curves, this required $10s$, $47s$ and $1.5s$ at the
zeros of $r_1$, the zeros of $r_2$ and at $\infty$, respectively. For the
family of generic quartic surfaces, this required $13s$ and $59s$ at the
zeros of~$r_1$ and at~$\infty$, respectively, but almost four hours for
both the zeros of~$r_2$ and $r_3$.  Note, however, that in this last case
we only use the exponents at~$\infty$ in the precision analysis and that
the other exponents are not needed for the result of the computation to
be provably correct.
\end{rem}

\phantomsection

\bibliographystyle{plainnat}