# Computing superspecial hyperelliptic curves of genus 4 with automorphism
group properly containing the Klein 4-group

Ryo Ohashi Graduate School of Information Science and Technology, The
University of Tokyo, E-mail<EMAIL_ADDRESS>Momonari Kudo
Fukuoka Institute of Technology, E-mail<EMAIL_ADDRESS>
###### Abstract

In algebraic geometry, enumerating or finding superspecial curves in positive
characteristic $p$ is important both in theory and in computation. In this
paper, we propose feasible algorithms to enumerate or find superspecial
hyperelliptic curves of genus $4$ with automorphism group properly containing
the Klein $4$-group. Executing the algorithms on Magma, we succeeded in
enumerating such superspecial curves for every $p$ with $19\leq p<500$, and in
finding a single one for every $p$ with $19\leq p<7000$.

##  1 Introduction

Throughout this paper, a curve means a non-singular projective variety of
dimension one, and isomorphisms are ones over an algebraically closed field.
The complexity is measured by the number of (arithmetic) operations in a
field, and the soft-O notation $\tilde{O}$ is used for ignoring logarithmic
factors. Let $p$ be a prime, and $k$ an algebraically closed field of
characteristic $p$. A curve $C$ is said to be superspecial if its Jacobian
variety is isomorphic to a product of supersingular elliptic curves. This is
well-known to be equivalent to that the Cartier operator on the regular
differential forms on $C$ acts as zero, where a matrix representing the
operator with respect to a suitable basis is called a Cartier-Manin matrix of
$C$. For a given pair $(g,p)$, the number of isomorphism classes of
superspecial genus-$g$ curves in characteristic $p$ is finite (possibly zero),
and it is important to determine the (non-)existence of such a curve; if
exists, the next problem is to enumerate all isomorphism classes. For $g\leq
3$, these problems were both solved in arbitrary $p$, but for $g\geq 4$ (even
when $g=4$), they are still open in general $p$, see [8] for a survey.

The case on which we focus in this paper is $g=4$, and we here review known
results in the case briefly; we refer to [8] for details. In this case, there
does not exist any superspecial curve when $p\in\\{2,3\\}$ by Ekedahl’s bound
[3], while it follows from [4, Theorem 3.1] that such a curve uniquely (up to
isomorphism) exists in $p=5$. To investigate the case where $p\geq 7$, Kudo-
Harashita developed computational approaches for enumeration and search of
superspecial genus-4 curves, see [9] and [11] for algorithms in the non-
hyperelliptic case, and [10] and [12] for ones in the hyperelliptic case. The
former (resp. latter) two algorithms can enumerate all superspecial non-
hyperelliptic (resp. hyperelliptic) curves of genus $4$ for a given $p$, and
its computational cost heavily depends on the Gröbner basis computation.
Although the complexity of each algorithm is considered to be exponential with
respect to $p$, their efficient implementations on Magma [1] established
enumeration results for some small $p\leq 23$; a particular but the most
surprising result is [9, Theorem B], which says that there is no superspecial
curve of genus $4$ in characteristic $p=7$.

On the other hand, some polynomial-time algorithms have been proposed in
recent years, for restricted cases where curves have non-trivial automorphism
groups: the paper [13] for the non-hyperelliptic case where ${\rm
Aut}\supset\mathbf{V}_{4}$, and [22] (resp. [15]) for the hyperelliptic case
where ${\rm Aut}\supset\mathbf{V}_{4}$ (resp. ${\rm
Aut}\supset\mathbf{C}_{6}$), where $\mathbf{V}_{4}$ and $\mathbf{C}_{n}$
respectively denote the Klein $4$-group and the cyclic group of order $n$. In
particular, Ohashi-Kudo-Harashita [22] proposed an algorithm to enumerate
superspecial hyperelliptic curves $H$ of genus 4 such that ${\rm
Aut}(H)\supset\mathbf{V}_{4}$, and its complexity is estimated as $O(p^{4})$
operations in $\mathbb{F}_{p^{4}}$. If we restrict ourselves to the case where
$\mathrm{Aut}(H)\cong\mathbf{V}_{4}$, the algorithm is expected to terminate
in $O(p^{3})$.

In this paper, we explore the hyperelliptic case where $\mathrm{Aut}(H)$
properly contains $\mathbf{V}_{4}$, namely
$\mathrm{Aut}(H)\supsetneq\mathbf{V}_{4}$. In this case, it is known that
$\mathrm{Aut}(H)$ is isomorphic to $\mathbf{D}_{4}$, $\mathbf{D}_{8}$,
$\mathbf{D}_{10}$, $\mathbf{C}_{16}\rtimes\mathbf{C}_{2}$, or
$\mathbf{C}_{5}\rtimes\mathbf{D}_{4}$, where $\mathbf{D}_{n}$ denotes the
dihedral group of order $2n$. Our contributions are summarized as follows:

  * •

In Section 3.1, we propose an algorithm (Algorithm 3.1.3 below) to enumerate
superspecial hyperelliptic curves $H$ of genus $4$ with
$\mathrm{Aut}(H)\supset\mathbf{D}_{4}$ in characteristic $p$, as a simpler
version of Ohashi-Kudo-Harashita’s algorithm [22]. Thanks to our criterion
(Lemma 3.1.1 below) to detect $H$’s satisfying
$\mathrm{Aut}(H)\supset\mathbf{D}_{4}$ together with Proposition 3.1.5, the
complexity of the proposed algorithm is estimated as $O(p^{3})$ operations in
$\mathbb{F}_{p^{4}}$, which is more efficient than directly applying Ohashi-
Kudo-Harashita’s one.

  * •

In Sections 3.2 and 3.3, we also propose efficient algorithms specific to the
case where $\mathrm{Aut}(H)\supset\mathbf{D}_{8}$ or
$\mathrm{Aut}(H)\supset\mathbf{D}_{10}$, by using Cartier-Manin matrices
together with Gauss’ hypergeometric series. For each case, we explicitly
determine the Cartier-Manin matrix of $H$, and prove that counting all
superspecial $H$’s is just done by computing the gcd of only one pair of
univariate polynomials. With this fact together with our isomorphy criteria,
the complexity of enumerating superspecial curves by this algorithm is
$\tilde{O}(p^{2})$ operations in $\mathbb{F}_{p^{4}}$, and it is expected to
be $\tilde{O}(p)$ in practice.

  * •

Implementing and executing the proposed algorithms on Magma, we obtain the
following computational results:

######  Theorem 1.

For each type of automorphism group properly containing $\mathbf{V}_{4}$, the
number of superspecial hyperelliptic curves of genus $4$ in characteristic $p$
with $19\leq p<500$ are summarized in Table 2 below. Moreover, such a
superspecial curve exists for every prime $p$ with $19\leq p<7000$.

As in [22], the upper bounds on $p$ in Theorem 1 can be also updated easily,
see Section 4 for details. From our computational results, we conjecture (cf.
Conjecture 1 below) that there exists a superspecial hyperelliptic curve $H$
of genus $4$ with $\mathrm{Aut}(H)\supset\mathbf{D}_{4}$ in arbitrary
characteristic $p$ with $p\geq 19$.

##  2 Preliminaries

In this section, let $k$ be an algebraically closed field of characteristic
$p\geq 3$.

###  2.1 Cartier-Manin matrix of a certain hyperelliptic curve

Let $g\geq 2$ be an integer. Any hyperelliptic curve $H$ over $k$ of genus $g$
is isomorphic to

$H:y^{2}=f(x),\quad\deg{f(x)}=2g+1\ {\rm or}\ 2g+2$

where $f(x)\in k[x]$ is a square-free polynomial. Then, the Cartier-Manin
matrix  of $H$ is defined to be the $(g\times g)$-matrix

$M=\begin{pmatrix}\gamma_{p-1}&\gamma_{p-2}&\cdots&\gamma_{p-g}\\\
\gamma_{2p-1}&\gamma_{2p-2}&\cdots&\gamma_{2p-g}\\\
\vdots&\vdots&\ddots&\vdots\\\
\gamma_{gp-1}&\gamma_{gp-2}&\cdots&\gamma_{gp-g}\end{pmatrix},$

where we write

$f(x)^{(p-1)/2}=\sum_{i=0}^{n}\gamma_{i}x^{i},\quad\
n:=\frac{p-1}{2}\cdot\,\deg{f(x)}$

with $\gamma_{i}\in k$. The Cartier-Manin matrix $M$ enables us to determine
whether $H$ is superspecial or not by the following result:

######  Theorem 2.1.1 ([19, Theorem 4.1]).

With notation as above, $H$ is superspecial if and only if $M$ is zero.

In the following, we consider the hyperelliptic curves

$C:y^{2}=(x^{r}-1)(x^{r}-\lambda)=:f(x),\quad
D:y^{2}=x(x^{r}-1)(x^{r}-\lambda)=:g(x),$

where $\lambda\in k$. We denote respectively by $\alpha_{d}$ and $\beta_{d}$
the $x^{d}$-coefficients of $f(x)^{e}$ and $g(x)^{e}$ with $e:=(p-1)/2$. We
also use the following notation:

######  Definition 2.1.2.

A truncation of Gauss’ hypergeometric series is defined as

$G^{(d)}(a,b,c\,;z):=\sum_{n=0}^{d}\frac{(a\,;n)(b\,;n)}{(c\,;n)(1\,;n)}z^{n},$

where $(x\,;n):=x(x+1)\cdots(x+n-1)$.

We can show that each entry of the Cartier-Manin matrices of $C$ and $D$ is
written as a truncation of Gauss’ hypergeometric series:

######  Proposition 2.1.3.

For all integers $d$ with $0\leq d\leq r(p-1)$, we obtain the following
statements:

  1. (1)

If $d\not\equiv 0\pmod{r}$, then we have $\alpha_{d}=\beta_{d+e}=0$.

  2. (2)

If $d=kr$ with $0\leq k\leq e$, then we have

$\alpha_{d}=\beta_{d+e}\equiv\lambda^{e-k}\cdot(-1)^{k}\binom{e}{k}G^{(k)}(1/2,-k,1/2-k\,;\lambda)\pmod{p}.$

  3. (3)

If $d=kr$ with $e\leq k\leq p-1$, then we have

$\alpha_{d}=\beta_{d+e}\equiv(-1)^{k}\binom{e}{p-1-k}G^{(k)}(1/2,1+k,3/2+k\,;\lambda)\pmod{p}.$

###### Proof.

Letting $\gamma_{k}$ be the $x^{k}$-coefficient of
$\\{(x-1)(x-\lambda)\\}^{(p-1)/2}$, we have that $\alpha_{d}=\beta_{d+e}$ is
equal to $\gamma_{k}$. The assertions follow from Proposition A.3 below. ∎

######  Corollary 2.1.4.

For all integers $k$ with $0\leq k\leq e$, we have

$\alpha_{(e-k)r}\equiv\alpha_{(e+k)r}\lambda^{k}\ \,{\rm and}\
\,\beta_{(e-k)r+e}\equiv\beta_{(e+k)r+e}\lambda^{k}.$

###### Proof.

It follows from Proposition 2.1.3 and Corollary A.4. ∎

###  2.2 Hyperelliptic curves of genus 4

We recall a classification by Kudo-Nakagawa-Takagi [14] (a preliminary version
of [15]) of hyperelliptic curves of genus $4$ by means of their automorphism
groups. For a hyperelliptic curve $H$ over $k$, we denote by $\iota_{H}$ its
hyperelliptic involution. The quotient group $\overline{\rm
Aut}(H):=\mathrm{Aut}(H)/\langle\iota_{H}\rangle$ is called the reduced
automorphism group of $H$. For $n\geq 2$, we also denote respectively by
$\mathbf{C}_{n}$, $\mathbf{D}_{n}$, $\mathbf{A}_{n}$, $\mathbf{V}_{4}$, and
$\mathbf{Q}_{8}$ the cyclic group of order $n$, the dihedral group of order
$2n$, the alternating group of order $n!/2$, the Klein $4$-group
$\mathbf{C}_{2}\times\mathbf{C}_{2}$, and the quaternion group.

######  Theorem 2.2.1 ([14, Theorem C]).

Assume that $p\geq 7$. The reduced automorphism group
$\overline{\mathrm{Aut}}(H)$ of a hyperelliptic curve $H$ of genus $4$ over an
algebraically closed field $k$ of characteristic $p$ is isomorphic to either
of the $10$ finite groups listed in Table 1. In each type of
$\overline{\mathrm{Aut}}(H)$, the finite group isomorphic to $\mathrm{Aut}(H)$
is provided in the third column of Table 1, and the hyperelliptic curve $H$ is
isomorphic to $y^{2}=f(x)$ given in the fourth column of the table.

Table 1: Classification of hyperelliptic curves $H$ of genus $4$ over an
algebraically closed field $k$ of characteristic $p\geq 7$ according to their
reduced and full automorphism groups, with their defining equations
$y^{2}=f(x)$, where $A,B,C,D\in k$.

Type | $\overline{\mathrm{Aut}}(H)$ | ${\mathrm{Aut}}(H)$ | Defining equation $y^{2}=f(x)$ for $H$ (in normal form)
---|---|---|---
1 | $\\{0\\}$ | $\mathbf{C}_{2}$ | $y^{2}=(\mbox{square-free polynomial in $x$ of degree 9 or 10})$
2-1 | $\mathbf{C}_{2}$ | $\mathbf{V}_{4}$ | $y^{2}=x^{10}+Ax^{8}+Bx^{6}+Cx^{4}+Dx^{2}+1$
2-2 | $\mathbf{C}_{2}$ | $\mathbf{C}_{4}$ | $y^{2}=x^{9}+Ax^{7}+Bx^{5}+Cx^{3}+x$
3 | $\mathbf{C}_{3}$ | $\mathbf{C}_{6}$ | $y^{2}=x^{10}+Ax^{7}+Bx^{4}+x$
4-1 | $\mathbf{V}_{4}$ | $\mathbf{D}_{4}$ |  $y^{2}=x^{10}+Ax^{8}+Bx^{6}+Bx^{4}+Ax^{2}+1$, or
$y^{2}=x^{9}+Ax^{7}+Bx^{5}+Ax^{3}+x$
4-2 | $\mathbf{V}_{4}$ | $\mathbf{Q}_{8}$ | $y^{2}=x(x^{4}-1)(x^{4}+Ax^{2}+1)$
5 | $\mathbf{D}_{4}$ | $\mathbf{D}_{8}$ | $y^{2}=x^{9}+Ax^{5}+x$
6 | $\mathbf{D}_{5}$ | $\mathbf{D}_{10}$ | $y^{2}=x^{10}+Ax^{5}+1$
7 | $\mathbf{A}_{4}$ | $\mathrm{SL}_{2}(\mathbb{F}_{3})$ | $y^{2}=x(x^{4}-1)(x^{4}+2\sqrt{-3}x^{2}+1)$
8 | $\mathbf{D}_{8}$ | $\mathbf{C}_{16}\rtimes\mathbf{C}_{2}$ | $y^{2}=x^{9}+x$
9 | $\mathbf{C}_{9}$ | $\mathbf{C}_{18}$ | $y^{2}=x^{10}+x$
10 | $\mathbf{D}_{10}$ | $\mathbf{C}_{5}\rtimes\mathbf{D}_{4}$ | $y^{2}=x^{10}+1$

Figure 1: Containment relationships among the families of genus-$4$
hyperelliptic curves $H$ with given automorphism groups ${\rm Aut}(H)$, and
the number of parameters representing each family.
$\textstyle{\mathbf{C}_{2}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$7-parameters$\textstyle{\mathbf{V}_{4}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$4-parameters$\textstyle{{\mathbf{C}_{4}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$3-parameters$\textstyle{\mathbf{C}_{6}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\mathbf{D}_{4}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$2-parameters$\textstyle{{\mathbf{Q}_{8}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\mathbf{D}_{8}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\mathbf{D}_{10}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$1-parameter$\textstyle{\mathbf{C}_{18}}$$\textstyle{{\mathrm{SL}_{2}(\mathbb{F}_{3})}}$$\textstyle{\mathbf{C}_{16}\rtimes\mathbf{C}_{2}}$$\textstyle{\mathbf{C}_{5}\rtimes\mathbf{D}_{4}}$No
parameter

Note that the superspeciality of the curves of Types 8, 9, and 10 can be
described as follows:

######  Corollary 2.2.2.

Assume that $p\geq 7$. Then, we have the following statements:

  1. (1)

The genus-4 hyperelliptic curve $H$ whose automorphism group ${\rm Aut}(H)$ is
isomorphic to $\mathbf{C}_{16}\rtimes\mathbf{C}_{2}$ is superspecial if and
only if $p\equiv-1,9\pmod{16}$.

  2. (2)

The genus-4 hyperelliptic curve $H$ whose automorphism group ${\rm Aut}(H)$ is
isomorphic to $\mathbf{C}_{18}$ is superspecial if and only if $p\equiv
8\pmod{9}$.

  3. (3)

The genus-4 hyperelliptic curve $H$ whose automorphism group ${\rm Aut}(H)$ is
isomorphic to $\mathbf{C}_{5}\rtimes\mathbf{D}_{4}$ is superspecial if and
only if $p\equiv 9\pmod{10}$.

###### Proof.

The curves in the cases (1) and (2) are isomorphic to

$y^{2}=x^{9}-x\quad{\rm and}\quad y^{2}=x^{9}-1$

respectively, and hence the assertions for these cases are shown by [25,
Theorem 2]. Moreover, the curve in the case (3) is isomorphic to
$H:y^{2}=x^{10}-1$, which has two involutions

$\sigma:(x,y)\mapsto(-x,y),\quad{\rm and}\quad\tau:(x,y)\mapsto(-x,-y).$

Then, the quotient curves $C_{1}:=H/\langle\sigma\rangle$ and
$C_{2}:=H/\langle\tau\rangle$ are given by

$C_{1}:y_{1}^{2}=x^{5}-1\quad{\rm and}\quad C_{2}:y_{2}^{2}=x(x^{5}-1)$

respectively, and these curves are both superspecial if and only if $p\equiv
9\pmod{10}$ by [6]. Since the Jacobian of $H$ is $(2,2,2,2)$-isogenous to
$J(C_{1})\times J(C_{2})$, we have that $H$ is superspecial if and only if
$p\equiv 9\pmod{10}$. ∎

###  2.3 Review on results by Ohashi-Kudo-Harashita

As noted in Section 1, the computational enumeration of superspecial curves is
an important problem, and Ohashi-Kudo-Harashita [22] proposed an algorithm
specific to the case of genus-$4$ hyperelliptic curves $H$ with
$\mathrm{Aut}(H)\supset\mathbf{V}_{4}$, i.e., types 2-1, 4-1, 5, 6, 8, and 10
in Table 1. Their idea is to reduce the enumeration of superspecial $H$’s into
that of special pairs of superspecial genus-$2$ curves obtained as the
quotients of $H$ by non-hyperelliptic involutions.

In the following, we briefly review the idea and their enumeration algorithm.
The target curves are of the form $y^{2}=f(x^{2})$ for some square-free
polynomial $f(x)\in k[x]$ of degree $5$, as in type 2-1 of Table 1. Each $H$
of the target curves has non-hyperelliptic involutions $(x,y)\mapsto(-x,y)$
and $(x,y)\mapsto(-x,-y)$, whence the quotients of $H$ by them are given by
$y_{1}^{2}=f(x)$ and $y_{2}^{2}=xf(x)$ respectively. This implies that any
genus-$4$ hyperelliptic curve with automorphism group containing
$\mathbf{V}_{4}$ is realized as the normalization of the fiber product over
$\mathbb{P}^{1}$ of two genus-$2$ curves sharing exactly $5$ ramification
points, and it is straightforward that the converse also holds. Moreover,
transforming $2$ among ramification points of $H$ into $\\{\pm 1\\}$, we may
assume that $H$ is of the following normal form

$H:y^{2}=f(x^{2})=(x^{2}-1)(x^{2}-c_{2})(x^{2}-c_{3})(x^{2}-c_{4})(x^{2}-c_{5})$
(2.1)

with $f(x)=(x-1)(x-c_{2})(x-c_{3})(x-c_{4})(x-c_{5})$ for some $c_{i}\in
k\\!\smallsetminus\\!\\{0,1\\}$. Moreover, we can transform the two quotient
curves into the following Rosenhain forms:

$\displaystyle C_{1}$
$\displaystyle:y_{1}^{2}=f_{1}(x)=x(x-1)(x-\lambda_{1})(x-\lambda_{2})(x-\lambda_{3}),$
(2.2) $\displaystyle C_{2}$
$\displaystyle:y_{2}^{2}=f_{2}(x)=x(x-1)(x-\lambda_{1})(x-\lambda_{2})(x-\lambda_{3}^{\prime}),$
(2.3)

via $x\mapsto\frac{(x-c_{2})(c_{3}-1)}{(x-1)(c_{3}-c_{2})}$, where
$\lambda_{1}$, $\lambda_{2}$, $\lambda_{3}$, and $\lambda_{3}^{\prime}$ are
mutually distinct elements in $k\\!\smallsetminus\\!\\{0,1\\}$ given by

$\begin{split}\lambda_{1}\\!=\\!\frac{(c_{4}-c_{2})(c_{3}-1)}{(c_{4}-1)(c_{3}-c_{2})},\
\lambda_{2}\\!=\\!\frac{(c_{5}-c_{2})(c_{3}-1)}{(c_{5}-1)(c_{3}-c_{2})},\
\lambda_{3}\\!=\\!\frac{c_{2}(c_{3}-1)}{c_{3}-c_{2}},\
\lambda_{3}^{\prime}\\!=\\!\frac{c_{3}-1}{c_{3}-c_{2}}.\end{split}$ (2.4)

Namely, $1$, $c_{2}$, $c_{3}$, $c_{4}$, $c_{5}$, $0$, and $\infty$ are mapped
into $\infty$, $0$, $1$, $\lambda_{1}$, $\lambda_{2}$, $\lambda_{3}$, and
$\lambda_{3}^{\prime}$ respectively. Note that, given $\lambda_{1}$,
$\lambda_{2}$, $\lambda_{3}$, and $\lambda_{3}^{\prime}$, we can reconstruct
$c_{2}$, $c_{3}$, $c_{4}$, and $c_{5}$ through the map
$x\mapsto\frac{x-\lambda_{3}^{\prime}}{x-\lambda_{3}}$, explicitly

$c_{2}=\frac{\lambda_{3}^{\prime}}{\lambda_{3}},\quad
c_{3}=\frac{1-\lambda_{3}^{\prime}}{1-\lambda_{3}},\quad
c_{4}=\frac{\lambda_{1}-\lambda_{3}^{\prime}}{\lambda_{1}-\lambda_{3}},\quad
c_{5}=\frac{\lambda_{2}-\lambda_{3}^{\prime}}{\lambda_{2}-\lambda_{3}}.$ (2.5)

Note that exchanging $\lambda_{1}$ and $\lambda_{2}$ produces the same
equation (2.1). Exchanging $\lambda_{3}$ and $\lambda_{3}^{\prime}$, we have
$y^{2}=(x^{2}-1)(x^{2}-c_{2}^{-1})(x^{2}-c_{3}^{-1})(x^{2}-c_{4}^{-1})(x^{2}-c_{5}^{-1})$,
which is isomorphic to (2.1) via
$(x,y)\mapsto(1/x,\sqrt{-c_{2}c_{3}c_{4}c_{5}}y/x^{5})$. Namely, $H$ is
specified by a pair
$(\\{\lambda_{1},\lambda_{2}\\},\\{\lambda_{3},\lambda_{3}^{\prime}\\})$ of
the sets $\\{\lambda_{1},\lambda_{2}\\}$ and
$\\{\lambda_{3},\lambda_{3}^{\prime}\\}$.

Recall from [22, Lemma 2] that $H$ is superspecial if and only if $C_{1}$ and
$C_{2}$ are both superspecial. Based on the above discussion, Ohashi-Kudo-
Harashita [22] presented the following algorithm to enumerate superspecial
$H$’s:

######  Algorithm 2.3.1 ([22, Algorithm 1]).

Input:

A rational prime $p\geq 7$.

Output:

A list of representatives for the isomorphism classes of superspecial
genus-$4$ hyperelliptic curves $H$ over $\overline{\mathbb{F}_{p}}$ with
$\mathrm{Aut}(H)\supset\mathbf{V}_{4}$.

Step 1.

Enumerate all isomorphism classes of superspecial curves of genus $2$ in
characteristic $p$, and let $\mathsf{SSp}_{2}(p)$ be a list of the enumerated
superspecial genus-$2$ curves.

Step 2.

For each superspecial genus-$2$ curve $C$ in $\mathsf{SSp}_{2}(p)$, compute
all $C_{\lambda,\mu,\nu}$ in Rosenhain form with $C_{\lambda,\mu,\nu}\cong C$,
by translating $3$ among $6$ ramified points of $C\to{\mathbb{P}}^{1}$ to
$\\{0,1,\infty\\}$. Sorting the list of all genus-$2$ curves in Rosenhain form
generated as above, detect all pairs
$(C_{\lambda,\mu,\nu},C_{\lambda^{\prime},\mu^{\prime},\nu^{\prime}})$ with
$\\#(\\{\lambda,\mu,\nu\\}\cap\\{\lambda^{\prime},\mu^{\prime},\nu^{\prime}\\})=2$.
Let $\mathsf{HowePairsList}$ be a list of the computed pairs.

Step 3.

Classify isomorphism classes of $H$’s as in (2.1) corresponding via (2.5) to
the pairs $(C_{1},C_{2})$ in $\mathsf{HowePairsList}$. Finally, output a list
of the computed isomorphism classes.

Ohashi-Kudo-Harashita estimated in [22] that the complexity of Algorithm 2.3.1
is ${O}(p^{4})$ operations in $\mathbb{F}_{p^{4}}$. More precisely, the
complexities of Steps 1, 2, and 3 are estimated as $O(p^{3})$, $O(p^{3})$, and
$O(p^{4})$ respectively. We can estimate in fact that the complexity of Step 3
is $O(p^{4})$ operations in $\mathbb{F}_{p^{2}}$ as follows: Ohashi’s recent
result [20, Main Theorem A] implies that
$\lambda,\mu,\nu\in\mathbb{F}_{p^{2}}$ for any superspecial
$C_{\lambda,\mu,\nu}$ computed in Step 2. In Step 3, we need to test whether
two hyperelliptic curves of genus $4$ are isomorphic or not in many times, and
it would be expected from [22, Remark 4] that the number of required isomorphy
tests is $O(p^{4})$. In general, testing isomorphy of two hyperelliptic curves
of genus $4$ is done by computing a Gröbner basis (with respect to a fast
monomial ordering) for a polynomial system with $5$ variables and maximal
total degree $10$, and its complexity is $O(1)$ operations in any common base
field of the two curves, see [22, Section 2.1] for details. Therefore, the
complexity of Step 3 is $O(p^{4})$ operations in $\mathbb{F}_{p^{2}}$. If we
restrict ourselves to the case where $\mathrm{Aut}(H)\cong\mathbf{V}_{4}$ in
Step 3, the complexity of Step 3 is $O(p^{3})$ operations in
$\mathbb{F}_{p^{2}}$, so that the total complexity is $O(p^{3})$ operations in
$\mathbb{F}_{p^{2}}$.

Ohashi-Kudo-Harashita implemented Algorithm 2.3.1 on Magma, and succeeded in
enumerating superspecial $H$’s with $\mathrm{Aut}(H)\cong\mathbf{V}_{4}$ for
$p$ up to $200$.

##  3 Main results

In this section, we first construct a feasible algorithm for enumerating
superspecial genus-$4$ hyperelliptic curves $H$ with
$\mathrm{Aut}(H)\supset\mathbf{D}_{4}$, as a simpler version of Algorithm
2.3.1. We also present more efficient algorithms specific to the cases where
$\mathrm{Aut}(H)\supset\mathbf{D}_{8}$ and
$\mathrm{Aut}(H)\supset\mathbf{D}_{10}$, by using Cartier-Manin matrices
together with the theory of Gauss’ hypergeometric series.

###  3.1 The case where ${\rm Aut}\cong{\mathbf{D}}_{4}$

Let $H$ be a hyperelliptic curve of genus $4$ over $k$ with
$\mathrm{Aut}(H)\supset\mathbf{D}_{4}$. A naive way to enumerate superspecial
$H$’s is to proceed with the following: Apply Steps 1 and 2 of Algorithm
2.3.1, detect $H$ with $\mathrm{Aut}(H)\supset\mathbf{D}_{4}$ from the list
$\mathsf{HowePairsList}$ by computing the automorphism group of each curve,
and then classify the isomorphism classes of detected ones as in the original
Step 3 in $O(p^{4})$ operations in $\mathbb{F}_{p^{4}}$. However, in fact, we
can simplify Step 2 (e.g., we need not compute any automorphism group), and
moreover the complexity of the isomorphism classification can be estimated as
$O(p^{2})$. A key lemma for simplifying Step 2 is the following:

######  Lemma 3.1.1.

With notation as above, $H$ is birational to
$C_{1}\times_{\mathbb{P}^{1}}C_{2}$ for some genus-$2$ curves $C_{1}$ and
$C_{2}$ over $k$ with $C_{1}\cong C_{2}$ that share exactly $5$ ramification
points. In fact, we can take equations for $C_{1}$ and $C_{2}$ to be ones in
Rosenhain form $C_{\lambda_{1},\lambda_{2},\lambda_{3}}$ and
$C_{\lambda_{1},\lambda_{2},\lambda_{3}^{\prime}}$ with
$\lambda_{3}\neq\lambda_{3}^{\prime}$ satisfying $c_{2}c_{3}=c_{4}c_{5}=1$,
where $c_{2}$, $c_{3}$, $c_{4}$, and $c_{5}$ are given in (2.5).

Conversely, if $C_{\lambda_{1},\lambda_{2},\lambda_{3}}$ and
$C_{\lambda_{1},\lambda_{2},\lambda_{3}^{\prime}}$ with
$\lambda_{3}\neq\lambda_{3}^{\prime}$ satisfy $c_{2}c_{3}=c_{4}c_{5}=1$, then
they are isomorphic to each other, and
$C_{\lambda_{1},\lambda_{2},\lambda_{3}}\times_{\mathbb{P}^{1}}C_{\lambda_{1},\lambda_{2},\lambda_{3}^{\prime}}$
is birational to a hyperelliptic curve of genus $4$ whose automorphism group
contains $\mathbf{D}_{4}$.

###### Proof.

Recall from Theorem 2.2.1 that $H$ is isomorphic to

$\displaystyle y^{2}$ $\displaystyle=x^{10}+Ax^{8}+Bx^{6}+Bx^{4}+Ax^{2}+1,\
\mbox{or}$ (3.6) $\displaystyle y^{2}$
$\displaystyle=x^{9}+Ax^{7}+Bx^{5}+Ax^{3}+x$ (3.7)

for some $A,B\in k$. By Lemma 3.1.2 below, it suffices to consider the first
equation (3.6) only, which is transformed into

$\displaystyle y^{2}$ $\displaystyle=x^{10}-Ax^{8}+Bx^{6}-Bx^{4}+Ax^{2}-1$
$\displaystyle=(x^{2}-1)(x^{8}+(1-A)x^{6}+(-A+B+1)x^{4}+(1-A)x^{2}+1)$

by $(x,y)\to(\sqrt{-1}x,\sqrt{-1}y/x^{5})$. Putting $1-A=a+b$ and $-A+B-1=ab$,
we can write the right hand side as

$(x^{2}-1)(x^{4}+ax^{2}+1)(x^{4}+bx^{2}+1)=(x^{2}-1)(x^{2}-c_{2})(x^{2}-c_{3})(x^{2}-c_{4})(x^{2}-c_{5})$

for some $c_{2},c_{3},c_{4},c_{5}\in k\\!\smallsetminus\\!\\{0,1\\}$ with
$c_{2}c_{3}=c_{4}c_{5}=1$. As in Subsection 2.3, $H$ is birational to the
fiber product $C_{1}\times_{\mathbb{P}^{1}}C_{2}$ of the two genus-$2$ curves
$C_{1}:y_{1}^{2}=f(x)=(x-1)(x-c_{2})(x-c_{3})(x-c_{4})(x-c_{5})$ and
$C_{2}:y_{2}^{2}=xf(x)$, which share $5$ ramification points precisely. By
$c_{2}c_{3}=c_{4}c_{5}=1$, these $C_{1}$ and $C_{2}$ are isomorphic to each
other via the map $(x,y)\mapsto(1/x,\sqrt{-c_{2}c_{3}c_{4}c_{5}}y/x^{3})$.
Moreover, they are isomorphic to (2.2) and (2.3) respectively, via (2.4) and
(2.5). We have proved the first assertion, and it is straightforward that the
second assertion (the converse of the first assertion) holds. ∎

######  Lemma 3.1.2.

Any genus-$4$ hyperelliptic curve given by (3.7) is isomorphic to one given by
(3.6).

###### Proof.

As in (3.6), the right hand side of (3.7) is factored into

$x(x^{4}-ax^{2}+1)(x^{4}-bx^{2}+1)=x(x^{2}-c^{2})(x^{2}-c^{-2})(x^{2}-d^{2})(x^{2}-d^{-2})$

for some $a,b\in k\\!\smallsetminus\\!\\{\pm 2\\}$ with $a\neq b$ and some
$c,d\in k\\!\smallsetminus\\!\\{0,\pm 1\\}$ with $c\neq d$. Since the Möbius
transformation $\phi:x\to\frac{1+x}{1-x}$ maps $\\{\infty,0,\pm c,\pm
c^{-1},\pm d,\pm d^{-1}\\}$ to $\\{\pm
1,\pm\xi,\pm\xi^{-1},\pm\eta,\pm\eta^{-1}\\}$ with $\xi:=\phi(c)$ and
$\eta:=\phi(d)$, the genus-$4$ hyperelliptic curve given by (3.7) is
isomorphic to

$y^{2}=(x^{2}-1)(x^{2}-\xi^{2})(x^{2}-\xi^{-2})(x^{2}-\eta^{2})(x^{2}-\eta^{-2}).$

Expanding the right hand side, we obtain an equation of the form (3.6), as
required. ∎

From Lemma 3.1.1, we not necessarily consider all genus-$2$ curves in
Rosenhain form constructed in Step 2 of Algorithm 2.3.1: It suffices to
consider only Rosenhain forms $C_{\lambda_{1},\lambda_{2},\lambda_{3}}$
constructed from the same $C_{\lambda,\mu,\nu}$. In addition, we may discard
any pair of $C_{\lambda_{1},\lambda_{2},\lambda_{3}}$ and
$C_{\lambda_{1},\lambda_{2},\lambda_{3}^{\prime}}$ with
$\lambda_{3}\neq\lambda_{3}^{\prime}$ if $(c_{2},c_{3},c_{4},c_{5})$ given in
(2.5) does not satisfy $c_{2}c_{3}=c_{4}c_{5}=1$. This also means that we can
detect pairs $(C_{1},C_{2})$ such that associated $H$ satisfies
$\mathrm{Aut}(H)\supset\mathbf{D}_{4}$ without computing $\mathrm{Aut}(H)$.
Here, we write down an algorithm to enumerate superspecial $H$’s with
$\mathrm{Aut}(H)\supset\mathbf{D}_{4}$, as a simpler version of Algorithm
2.3.1.

######  Algorithm 3.1.3.

Input:

A rational prime $p\geq 7$.

Output:

A list of representatives for the isomorphism classes of superspecial
genus-$4$ hyperelliptic curves $H$ over $\overline{\mathbb{F}_{p}}$ with
$\mathrm{Aut}(H)\supset\mathbf{D}_{4}$.

Step 1.

Proceed with the same as in Step 1 of Algorithm 2.3.1, but we give a
representative of each isomorphism class in Rosenhain form. Let
$\mathsf{SSp}_{2}(p)$ be a list of enumerated superspecial genus-$2$ curves in
Rosenhain form.

Step 2.

For each superspecial genus-$2$ curve $C_{\lambda,\mu,\nu}$, generate all
$C_{\lambda^{\prime},\mu^{\prime},\nu^{\prime}}$ with
$\lambda^{\prime},\mu^{\prime},\nu^{\prime}\in k\smallsetminus\\{0,1\\}$ such
that $C_{\lambda,\mu,\nu}\cong
C_{\lambda^{\prime},\mu^{\prime},\nu^{\prime}}$, by translating $3$ among the
$6$ ramified points of $C_{\lambda,\mu,\nu}\to{\mathbb{P}}^{1}$ to
$\\{0,1,\infty\\}$. Among $C_{\lambda^{\prime},\mu^{\prime},\nu^{\prime}}$’s
produced as above, detect ones satisfying
$\\#(\\{\lambda,\mu,\nu\\}\cap\\{\lambda^{\prime},\mu^{\prime},\nu^{\prime}\\})=2$.
For each detected one, when we write $C_{\lambda,\mu,\nu}$ and
$C_{\lambda^{\prime},\mu^{\prime},\nu^{\prime}}$ as
$C_{\lambda_{1},\lambda_{2},\lambda_{3}}$ and
$C_{\lambda_{1},\lambda_{2},\lambda_{3}^{\prime}}$ respectively, compute an
equation (2.1) defining a hyperelliptic curve $H$ birational to
$C_{\lambda_{1},\lambda_{2},\lambda_{3}}\times_{\mathbb{P}^{1}}C_{\lambda_{1},\lambda_{2},\lambda_{3}^{\prime}}$
by (2.5), and store it if $c_{2}c_{3}=c_{4}c_{5}=1$. Let
$\mathsf{ListSSpHypCurvesD4}$ be a list of $H$’s computed as above.

Step 3.

Classify isomorphism classes of $H$’s in $\mathsf{ListSSpHypCurvesD4}$.
Finally, output a list of the computed isomorphism classes.

######  Remark 3.1.4.

In our implementation, we realize Step 1 by generating the superspecial
Richelot isogeny graph, which can be computed with arithmetic of theta
functions [2]. Since this is not the main topic of this paper, we omit to
write its concrete procedures, and some details will be explained in [23].

We also remark that our implementation conducts each isomorphism test in Step
3 with Magma’s built-in function IsIsomorphicHyperellipticCurves, which was
implemented by Lercier-Sijsling-Ritzenthaler [16].

The correctness of Algorithm 3.1.3 follows from Lemma 3.1.1. The complexity of
Step 1 is the same as that of Algorithm 2.3.1, i.e., $O(p^{3})$ operations in
$\mathbb{F}_{p^{4}}$. Note that, for each $C_{\lambda,\mu,\nu}$ computed in
Step 1, we have
$\lambda,\mu,\nu\in\mathbb{F}_{p^{2}}\\!\smallsetminus\\!\\{0,1\\}$ by [20,
Main Theorem A]. Therefore, the complexity of Step 2 is $O(p^{3})$ operations
in $\mathbb{F}_{p^{2}}$. To estimate the complexity of Step 3, we use the
following lemma:

######  Proposition 3.1.5.

In Step 2 of Algorithm 3.1.3, if $\lambda_{1}$, $\lambda_{2}$, and
$\lambda_{3}$ are chosen uniformly at random from
$\mathbb{F}_{p^{2}}\\!\smallsetminus\\!\\{0,1\\}$, then the probability that
$C_{\lambda_{1},\lambda_{2},\lambda_{3}}\cong
C_{\lambda_{1},\lambda_{2},\lambda_{3}^{\prime}}$ for some
$\lambda_{3}^{\prime}\in\mathbb{F}_{p^{2}}$ with
$\lambda_{3}\neq\lambda_{3}^{\prime}$ is $O(1/p^{2})$.

###### Proof.

As in [20, Section 2.1], we have that
$C_{\lambda_{1},\lambda_{2},\lambda_{3}}\cong C_{\lambda,\mu,\nu}$ if and only
if

$\lambda=\frac{(a_{4}-a_{1})(a_{2}-a_{3})}{(a_{4}-a_{3})(a_{2}-a_{1})},\
\mu=\frac{(a_{5}-a_{1})(a_{2}-a_{3})}{(a_{5}-a_{3})(a_{2}-a_{1})},\
\nu=\frac{(a_{6}-a_{1})(a_{2}-a_{3})}{(a_{6}-a_{3})(a_{2}-a_{1})},$

where
$\\{a_{1},\ldots,a_{6}\\}=\\{0,1,\infty,\lambda_{1},\lambda_{2},\lambda_{3}\\}$.
Here, if $a_{i}=\infty$, we mean that all the factors $(a_{i}-a_{j})$ or
$(a_{j}-a_{i})$ are excluded from each of $\lambda$, $\mu$, and $\nu$. Then,
we see that

$\lambda=\lambda_{1},\quad\mu=\frac{\lambda_{1}}{\lambda_{2}},\quad\nu=\frac{\lambda_{1}}{\lambda_{3}}$

in the case where
$(a_{1},\ldots,a_{6})=(\infty,\lambda_{1},0,1,\lambda_{2},\lambda_{3})$. Let
us compute the probability that

$\\#(\\{\lambda_{2},\lambda_{3}\\}\cap\\{\mu,\nu\\})=1.$

Then, we have that $\mu=\lambda_{2}$ or $\nu=\lambda_{3}$ (indeed, if
$\mu=\lambda_{3}$, then we also obtain $\nu=\lambda_{2}$, which contradicts
the above condition). Therefore, we need only consider the case that
$\lambda_{1}=\lambda_{2}^{2}$ or $\lambda_{1}=\lambda_{3}^{2}$, and we see
that this probability is $O(1/p^{2})$ since all
$\lambda_{1},\lambda_{2},\lambda_{3}$ belong to
$\mathbb{F}_{p^{2}}\\!\smallsetminus\\!\\{0,1\\}$.

There exist two other transformations

$\displaystyle\lambda$
$\displaystyle=\lambda_{1},\quad\mu=\frac{\lambda_{2}-\lambda_{1}}{\lambda_{2}-1},\quad\nu=\frac{\lambda_{3}-\lambda_{1}}{\lambda_{3}-1},$
$\displaystyle\lambda$
$\displaystyle=\lambda_{1},\quad\mu=\lambda_{1}\cdot\frac{\lambda_{2}-1}{\lambda_{2}-\lambda_{1}},\quad\nu=\lambda_{1}\cdot\frac{\lambda_{3}-1}{\lambda_{3}-\lambda_{1}}$

satisfying $\lambda=\lambda_{1}$ except for the trivial transformation. In
these cases, the probability that
$\\#(\\{\lambda_{2},\lambda_{3}\\}\cap\\{\mu,\nu\\})=1$ is also $O(1/p^{2})$
as similar discussions. ∎

######  Remark 3.1.6.

For a fixed $3$-tuple $(\lambda_{1},\lambda_{2},\lambda_{3})$, the number of
$\lambda^{\prime}_{3}$ such that $C_{\lambda_{1},\lambda_{2},\lambda_{3}}\cong
C_{\lambda_{1},\lambda_{2},\lambda_{3}^{\prime}}$ is $O(1)$ since the number
of transformations is $O(1)$.

Since the number of superspecial genus-$2$ curves is $O(p^{3})$ by [6, Theorem
3.3], we obtain the following expectation from Proposition 3.1.5:

######  Expectation 3.1.7.

The number of pairs
$(C_{\lambda_{1},\lambda_{2},\lambda_{3}},C_{\lambda_{1},\lambda_{2},\lambda_{3}^{\prime}})$
of superspecial $C_{\lambda_{1},\lambda_{2},\lambda_{3}}$ and
$C_{\lambda_{1},\lambda_{2},\lambda_{3}^{\prime}}$ with
$\lambda_{3}\neq\lambda_{3}^{\prime}$ is $O(p)$.

Assuming Expectation 3.1.7, we can estimate the complexity of Step 3 in
Algorithm 3.1.3 is $O(p^{2})$ operations in $\mathbb{F}_{p^{2}}$ similarly to
the case of Algorithm 2.3.1, so that the total complexity becomes $O(p^{3})$
operations in $\mathbb{F}_{p^{4}}$.

###  3.2 The case where ${\rm Aut}\cong{\mathbf{D}}_{8}$

In this subsection, we shall present an algorithm specific to the case where
$\mathrm{Aut}(H)\supset\mathbf{D}_{8}$. For this, we start with proving the
following lemma:

######  Lemma 3.2.1.

Any genus-4 hyperelliptic curve $H$ such that ${\rm
Aut}(H)\supset\mathbf{D}_{8}$ can be written as

$H_{\lambda}:y^{2}=x(x^{4}-1)(x^{4}-\lambda)$

for some $\lambda\neq 0,1$.

###### Proof.

Recall from Table 1 that $H$ is written as

$H:y^{2}=x^{9}+Ax^{5}+x=x(x^{4}-\alpha^{4})(x^{4}-\alpha^{-4}),$

where $\alpha^{4}+\alpha^{-4}=-A$ with $\alpha^{4}\neq 0,\pm 1$. Setting
$\lambda:=\alpha^{8}$, we obtain an isomorphism

$H\rightarrow H_{\lambda}\ ;\,(x,y)\mapsto(\alpha x,\alpha^{9/2}y),$

where $\alpha^{8}\neq 0,1$ implies $\lambda\neq 0,1$, as desired. ∎

######  Remark 3.2.2.

In the proof of Lemma 3.2.1, the genus-$4$ hyperelliptic curve
$H:y^{2}=x^{9}+Ax^{5}+x$ is isomorphic to $H_{\lambda}$ for some $\lambda\in
k\\!\smallsetminus\\!\\{0,1\\}$ and vice versa, via the relation
$\lambda+\frac{1}{\lambda}=A^{2}-2$.

We shall use the above $H_{\lambda}$ for our purpose that we enumerate or find
superspecial curves. Next, we investigate the Cartier-Manin matrix of
$H_{\lambda}$. Write

$\bigl{\\{}\hskip
0.56905ptx(x^{4}-1)(x^{4}-\lambda)\bigr{\\}}^{e}=\sum_{i=e}^{9e}\beta_{i}x^{i},\quad
e:=\frac{p-1}{2},$

where $\beta_{i}\in k$, and then we obtain that $\beta_{i}=0$ unless $i-e$ is
multiple of 4. By a straightforward computation, we can determine possibly
non-zero entries in the Cartier-Manin matrix $M$ of $H_{\lambda}$, dividing
the case into the following four cases, by the value of $p\bmod 8$:

  * •

If $p\equiv 1\pmod{8}$, then $e\equiv 0\pmod{4}$, and we have

$M=\begin{pmatrix}\beta_{p-1}&0&0&0\\\ 0&\beta_{2p-2}&0&0\\\
0&0&\beta_{3p-3}&0\\\ 0&0&0&\beta_{4p-4}\end{pmatrix}.$

  * •

If $p\equiv 3\pmod{8}$, then $e\equiv 1\pmod{4}$, and we have

$M=\begin{pmatrix}0&\beta_{p-2}&0&0\\\ \beta_{2p-1}&0&0&0\\\
0&0&0&\beta_{3p-4}\\\ 0&0&\beta_{4p-3}&0\end{pmatrix}.$

  * •

If $p\equiv 5\pmod{8}$, then $e\equiv 2\pmod{4}$, and we have

$M=\begin{pmatrix}0&0&\beta_{p-3}&0\\\ 0&0&0&\beta_{2p-4}\\\
\beta_{3p-1}&0&0&0\\\ 0&\beta_{4p-2}&0&0\end{pmatrix}.$

  * •

If $p\equiv 7\pmod{8}$, then $e\equiv 3\pmod{4}$, and we have

$M=\begin{pmatrix}0&0&0&\beta_{p-4}\\\ 0&0&\beta_{2p-3}&0\\\
0&\beta_{3p-2}&0&0\\\ \beta_{4p-1}&0&0&0\end{pmatrix}.$

Here, recall from Theorem 2.1.1 that $H$ is superspecial if and only if $M=0$,
which can be determined by computing the gcd of four possible non-zero entries
(as univariate polynomials in $\lambda$) given as above. In fact, it suffices
to consider only two among the four entries in each case:

######  Proposition 3.2.3.

With notation as above, we have the following statements:

  * •

If $p\equiv 1\pmod{8}$, then $H_{\lambda}$ is superspecial if and only if
$\beta_{3p-3}=\beta_{4p-4}=0$.

  * •

If $p\equiv 3\pmod{8}$, then $H_{\lambda}$ is superspecial if and only if
$\beta_{3p-4}=\beta_{4p-3}=0$.

  * •

If $p\equiv 5\pmod{8}$, then $H_{\lambda}$ is superspecial if and only if
$\beta_{3p-1}=\beta_{4p-2}=0$.

  * •

If $p\equiv 7\pmod{8}$, then $H_{\lambda}$ is superspecial if and only if
$\beta_{3p-2}=\beta_{4p-1}=0$.

###### Proof.

It follows from Corollary 2.1.4 that

$\beta_{5e-4i}\equiv\beta_{5e+4i}\lambda^{i}\pmod{p}$

for all $i\in\\{0,\ldots,e\\}$. In the case where $p\equiv 1\pmod{8}$, we see
that

$\beta_{p-1}\equiv\beta_{4p-4}\lambda^{3e/4}\ \ {\rm and}\ \
\beta_{2p-2}\equiv\beta_{3p-3}\lambda^{e/4}.$

By the condition that $\lambda\neq 0$, we have

$\beta_{p-1}=\beta_{2p-2}=\beta_{3p-3}=\beta_{4p-4}=0\
\Longleftrightarrow\,\beta_{3p-3}=\beta_{4p-4}=0.$

The other three cases can be shown in a way similar to this. ∎

Putting $F:={\rm gcd}(\beta_{3p-i},\beta_{4p-j})$ for

$(i,j):=\left\\{\begin{array}[]{l}(3,4)\quad{\rm if}\ p\equiv
1\pmod{8},\\\\[1.42262pt] (4,3)\quad{\rm if}\ p\equiv
3\pmod{8},\\\\[1.42262pt] (1,2)\quad{\rm if}\ p\equiv
5\pmod{8},\\\\[1.42262pt] (2,1)\quad{\rm if}\ p\equiv
7\pmod{8},\end{array}\right.$ (3.8)

we have that $H_{\lambda}$ is superspecial if and only if $F(\lambda)=0$.

Here, we have shown that a list of all superspecial $H_{\lambda}$ can be
generated by computing the gcd $F(\lambda)$ and by seeking its roots, all of
which are contained in $\mathbb{F}_{p^{4}}$ (see Proposition 3.2.7 below).
Note that the number of listed superspecial curves $H_{\lambda}$ is $O(p)$
since $\deg{F}=O(p)$. In fact, we can expect from our computational results
that this degree (and thus the number of listed curves) is bounded by a
constant not depending on $p$, see Table 2 below.

Once the list is obtained, we execute the isomorphism classification to count
the number of isomorphism classes of listed superspecial curves. As we
described in Subsection 2.3, testing isomorphy of two hyperelliptic curves of
genus $4$ is done in a constant number of operations (with respect to $p$) in
their common base field. Hence, the complexity of the isomorphism
classification is $O(p^{2})$ operations in $\mathbb{F}_{p^{4}}$ naively. To
make this more efficient, we prove the following criteria (Proposition 3.2.4
below), and then obtain a formula (Theorem 3.2.6 below) on the number of
isomorphism classes:

######  Proposition 3.2.4.

For $\lambda_{1},\lambda_{2}\in k\\!\smallsetminus\\!\\{0,1\\}$, the curve
$H_{\lambda_{1}}$ is isomorphic to the curve $H_{\lambda_{2}}$ if and only if
$\lambda_{1}=\lambda_{2}$ of $\lambda_{1}=1/\lambda_{2}$.

###### Proof.

Write the two hyperelliptic curves $H_{\lambda_{1}}$ and $H_{\lambda_{2}}$ as
follows:

$\displaystyle H_{\lambda_{1}}$
$\displaystyle:y^{2}=x(x^{4}-\alpha^{4})(x^{4}-\alpha^{-4}),\quad{\rm with}\
\alpha^{8}=\lambda_{1},$ $\displaystyle H_{\lambda_{2}}$
$\displaystyle:y^{2}=x(x^{4}-\beta^{4})(x^{4}-\beta^{-4}),\quad\hskip
0.28453pt{\rm with}\ \beta^{8}=\lambda_{2}.$

Then, one can show that $H_{\lambda_{1}}\cong H_{\lambda_{2}}$ if and only if

$\lambda_{1}+\frac{1}{\lambda_{1}}=\alpha^{8}+\frac{1}{\alpha^{8}}=\beta^{8}+\frac{1}{\beta^{8}}=\lambda_{2}+\frac{1}{\lambda_{2}}$

by a way similar to the proof of [7, Theorem 2.1]. It is straightforward that
this is equivalent to $\lambda_{1}=\lambda_{2}$ or
$\lambda_{1}=1/\lambda_{2}$, as desired. ∎

Recall from Theorem 2.2.1 (especially Figure 1) that
$\mathrm{Aut}(H_{\lambda})$ is isomorphic to $\mathbf{D}_{8}$ or
$\mathbf{C}_{16}\rtimes\mathbf{C}_{2}$; the latter case is easily detected as
follows:

######  Corollary 3.2.5.

The following statements are true:

  1. (1)

If $\lambda=-1$, then we have ${\rm
Aut}(H_{\lambda})\cong\mathbf{C}_{16}\rtimes\mathbf{C}_{2}$.

  2. (2)

Otherwise, we have ${\rm Aut}(H_{\lambda})\cong\mathbf{D}_{8}$.

###### Proof.

The assertion (1) follows from Remark 3.2.2 and the case 8 of Table 1. For any
$\lambda\neq-1$, it follows from Proposition 3.2.4 that $H_{\lambda}$ is not
isomorphic to $H_{-1}$, as desired. ∎

Thanks to the following theorem, we can compute the number of isomorphism
classes of superspecial hyperelliptic genus-4 curves such that ${\rm
Aut}\cong{\mathbf{D}}_{8}$.

######  Theorem 3.2.6.

With notation as above, the degree of $F$ is odd if and only if
$p\equiv-1,9\pmod{16}$, and the number of superspecial hyperelliptic curves
$H$ of genus 4 such that ${\rm Aut}(H)\cong{\mathbf{D}}_{8}$ is given as

$\left\\{\begin{array}[]{l}\frac{1}{2}(\deg{F}-1)\quad{\rm if}\
p\equiv-1,9\pmod{16},\\\\[2.84526pt] \frac{1}{2}\deg{F}\hskip
13.37277pt\qquad{\rm otherwise.}\end{array}\right.$

###### Proof.

We first claim that $F$ is separable as a univariate polynomial in $\lambda$.
Indeed, each entry $\beta_{k}$ in the Cartier-Manin matrix for $H_{\lambda}$
is written as a Gauss’ hypergeometric series by Corollary 2.1.3. Then, one can
show that all $\beta_{i}$’s (as univariate polynomials in $\lambda$) are
separable and have no root $\lambda=0$ nor $\lambda=1$, by a way similar to
the proof of [5], [6, $\S 1.4$], or [21, Lemma 3.1.3]. Therefore, $F$ is also
separable.

Next, we prove the assertions. For any $\lambda_{0}\in
k\\!\smallsetminus\\!\\{0,1\\}$, it follows from Proposition 3.2.4 that
$F(\lambda_{0})=0$ is equivalent to $F(\frac{1}{\lambda_{0}})=0$. Here,
$\lambda_{0}=\frac{1}{\lambda_{0}}$ implies $\lambda_{0}=\pm 1$ and vice
versa, and $F(-1)=0$ holds if and only if $p\equiv-1,9\pmod{16}$ by Corollary
2.2.2 (1) and Corollary 3.2.5. From these together with the separability of
$F$, we can write

$F=\left\\{\begin{array}[]{ll}c(\lambda+1)^{i}\prod_{\lambda_{0}}(\lambda-\lambda_{0})(\lambda-\frac{1}{\lambda_{0}})&\quad{\rm
if}\ p\equiv-1,9\pmod{16},\\\\[1.42262pt]
c\prod_{\lambda_{0}}(\lambda-\lambda_{0})(\lambda-\frac{1}{\lambda_{0}})&\quad\mbox{otherwise}\end{array}\right.$

for a constant $c\in k\smallsetminus\\{0\\}$ and some mutually different
$\lambda_{0}$’s with $\lambda_{0}\in k\smallsetminus\\{0,\pm 1\\}$, which
implies the assertion on the degree of $F$. With the above factorization of
$F$, we obtain the second assertion from Proposition 3.2.4 and Corollary
3.2.5. ∎

Moreover, we obtain the following proposition, which is used for determining
the complexity of computing the list of superspecial curves $H_{\lambda}$ with
exact $\lambda$:

######  Proposition 3.2.7.

All roots of the polynomial $F$ belong to $\mathbb{F}_{p^{4}}$.

###### Proof.

It is known that any superspecial curve is defined over $\mathbb{F}_{p^{2}}$.
Hence, if $H_{\lambda}$ is superspecial, then there exists a curve $H$ defined
over $\mathbb{F}_{p^{2}}$ such that $H_{\lambda}\cong H$. Let
${H_{\lambda}}^{\\!(\sigma)}$ be the fiber product
$H_{\lambda}\otimes_{k,\sigma}k$, where $\sigma:k\rightarrow k$ is the
$p^{2}$-power map, so that we have ${H_{\lambda}}^{\\!(\sigma)}\cong H$. Since
$H_{\sigma(\lambda)}\cong{H_{\lambda}}^{\\!(\sigma)}$, we obtain that
${H_{\lambda}}\cong H_{\sigma(\lambda)}$. It follows from Proposition 3.2.4
that

$\lambda+\frac{1}{\lambda}=\sigma(\lambda)+\frac{1}{\sigma(\lambda)}=\sigma\biggl{(}\lambda+\frac{1}{\lambda}\biggr{)},$

and hence $\lambda+1/\lambda$ belongs to $\mathbb{F}_{p^{2}}$. This implies
that $\lambda$ and $1/\lambda$ are the roots of a quadratic polynomial over
$\mathbb{F}_{p^{2}}$, so that $\lambda\in\mathbb{F}_{p^{4}}$, as desired. ∎

Putting the results obtained in this subsection together, we obtain the
following algorithm:

######  Algorithm 3.2.8.

Input:

A rational prime $p\geq 7$.

Output:

A list $\mathcal{L}$ of representatives for the isomorphism classes of
superspecial genus-$4$ hyperelliptic curves $H$ over
$\overline{\mathbb{F}_{p}}$ with $\mathrm{Aut}(H)\cong\mathbf{D}_{8}$.

Step 1.

Compute $\beta_{3p-i}$ and $\beta_{4p-j}$ by using Proposition 2.1.3 (details
will be explained in the proof of Theorem 3.2.9 below), where $(i,j)$ denotes
a pair of integers defined in (3.8).

Step 2.

Compute the polynomial $F:={\rm gcd}(\beta_{3p-i},\beta_{4p-j})$ and its roots
$\lambda\in\mathbb{F}_{p^{4}}$.

Step 3.

For each $\lambda\neq-1$ obtained in Step 2, if not $H_{1/\lambda}$ already
belongs to $\mathcal{L}$, then set $\mathcal{L}\leftarrow\mathcal{L}\hskip
1.42262pt\cup\\{H_{\lambda}\\}$. Finally, output a list $\mathcal{L}$.

We finally determine the complexity of Algorithm 3.2.8 in the following:

######  Theorem 3.2.9.

We can compute the number of superspecial genus-$4$ hyperelliptic curves $H$
with $\mathrm{Aut}(H)\cong\mathbf{D}_{8}$ in $\tilde{O}(p)$ operations in
$\mathbb{F}_{p}$. Moreover, the complexity of listing up all of their
isomorphism classes is bounded by $\tilde{O}(p+d^{2})$ operations in
$\mathbb{F}_{p^{4}}$ with $d:=\deg{F}=O(p)$, and it becomes $\tilde{O}(p)$
operations in $\mathbb{F}_{p^{4}}$ assuming that $\deg{F}$ is bounded by a
constant not depending on $p$.

###### Proof.

By definition of $\beta_{i}$, we see that the degrees of $\beta_{3p-i}$ and
$\beta_{4p-j}$ are both $O(p)$. These are computed in $\tilde{O}(p)$
operations in $\mathbb{F}_{p}$. Indeed, we can write

$\displaystyle\beta_{3p-i}$
$\displaystyle=(-1)^{k_{1}}\binom{e}{p-1-k_{1}}G^{(k_{1})}(1/2,1+k_{1},3/2+k_{1}\,;\lambda),\
\ k_{1}=\frac{3p-i-e}{4},$ $\displaystyle\beta_{4p-j}$
$\displaystyle=(-1)^{k_{2}}\binom{e}{p-1-k_{2}}G^{(k_{2})}(1/2,1+k_{2},3/2+k_{2}\,;\lambda),\
\ k_{2}=\frac{4p-j-e}{4}$

by Proposition 2.1.3. Here, Gauss’ hypergeometric series
$G^{(d)}(a,b,c\,;\lambda)$ can be computed as follows: We set $g_{0}:=1$ and
compute

$g_{n}:=\frac{(a+n-1)(b+n-1)}{(c+n-1)n}\cdot g_{n-1}$

for each $n$ from $1$ to $d$. Then, the sum
$g_{0}+g_{1}\lambda+\cdots+g_{d}\lambda^{d}$ is equal to
$G^{(d)}(a,b,c\,;\lambda)$. Hence, the computation of Step 1 can be done in
${O}(p)$ operations in $\mathbb{F}_{p}$.

In Step 2, the polynomial $F$ can be also computed in $\tilde{O}(p)$
operations in $\mathbb{F}_{p}$ with the fast gcd algorithm, since the degrees
of $\beta_{3p-i}$ and $\beta_{4p-j}$ as univariate polynomials in $\lambda$
are both $O(p)$. Hence, the first assertion is shown by Theorem 3.2.6. If one
computes a list of representatives of all isomorphism classes, it is required
to compute all the roots in $\mathbb{F}_{p^{4}}$ of $F$. By the separability
of the polynomial $F$, we can compute the roots only by equal-degree
factorization, e.g., the Cantor-Zassenhaus algorithm, whose complexity is
${O}(d^{2}\log{d}\log{p^{4}})$ (and thus $\tilde{O}(d^{2})$) operations in
$\mathbb{F}_{p^{4}}$ in this case.

It follows from Proposition 3.2.4 that computations in Step 3 can be done in
$O(d\log{d})$ operations in $\mathbb{F}_{p^{4}}$. Considering the complexity
of each step together, we obtain the second assertion. When we suppose
$d=O(1)$, it is clear that the complexity of Step 2 (resp. Step 3) is
$\tilde{O}(p)$ (resp. $O(1)$) operations in $\mathbb{F}_{p^{4}}$, which
deduces the last assertion. ∎

###  3.3 The case where ${\rm Aut}\cong{\mathbf{D}}_{10}$

Similarly to the previous subsection, we shall present an algorithm specific
to the case where $\mathrm{Aut}(H)\supset\mathbf{D}_{10}$. We first prove the
following lemma:

######  Lemma 3.3.1.

Any genus-4 hyperelliptic curve $H$ such that ${\rm
Aut}(H)\supset\mathbf{D}_{10}$ can be written as

${H^{\prime}}_{\\!\\!\lambda}:y^{2}=(x^{5}-1)(x^{5}-\lambda)$

for some $\lambda\neq 0,1$.

###### Proof.

From Table 1, we can write $H$ as

$H:y^{2}=x^{10}+Ax^{5}+1=(x^{5}-\alpha^{5})(x^{5}-\alpha^{-5})$

where $\alpha^{5}+\alpha^{-5}=-A$ with $\alpha^{5}\neq 0,\pm 1$. Setting
$\lambda:=\alpha^{10}$, there exists an isomorphism

$H\rightarrow{H^{\prime}}_{\\!\\!\lambda}\ ;\,(x,y)\mapsto(\alpha
x,\alpha^{5}y),$

where $\lambda\neq 0,1$ by $\lambda=\alpha^{10}\neq 0,1$, as desired. ∎

######  Remark 3.3.2.

In the proof of Lemma 3.3.1, the genus-$4$ hyperelliptic curve
$H:y^{2}=x^{10}+Ax^{5}+1$ is isomorphic to $H_{\lambda}$ for some $\lambda\in
k\\!\smallsetminus\\!\\{0,1\\}$ and vice versa, via the relation
$\lambda+\frac{1}{\lambda}=A^{2}-2$.

As for the Cartier-Manin matrix $M$ of ${H^{\prime}}_{\\!\\!\lambda}$, one has

$\bigl{\\{}\hskip
0.56905pt(x^{5}-1)(x^{5}-\lambda)\bigr{\\}}^{e}=\sum_{i=0}^{10e}\alpha_{i}x^{i},$

where $e:=(p-1)/2$. We see that $\alpha_{i}=0$ unless $i$ is multiple of 5. A
straightforward computation determines possibly non-zero entries in $M$,
dividing the case into the following four cases, by the value of $p\bmod 10$:

  * •

If $p\equiv 1\pmod{10}$, then $e\equiv 0\pmod{5}$, and we have

$M=\begin{pmatrix}\alpha_{p-1}&0&0&0\\\ 0&\alpha_{2p-2}&0&0\\\
0&0&\alpha_{3p-3}&0\\\ 0&0&0&\alpha_{4p-4}\end{pmatrix}.$

  * •

If $p\equiv 3\pmod{10}$, then $e\equiv 1\pmod{5}$, and we have

$M=\begin{pmatrix}0&0&\alpha_{p-3}&0\\\ \alpha_{2p-1}&0&0&0\\\
0&0&0&\alpha_{3p-4}\\\ 0&\alpha_{4p-2}&0&0\end{pmatrix}.$

  * •

If $p\equiv 7\pmod{10}$, then $e\equiv 3\pmod{5}$, and we have

$M=\begin{pmatrix}0&\alpha_{p-2}&0&0\\\ 0&0&0&\alpha_{2p-4}\\\
\alpha_{3p-1}&0&0&0\\\ 0&0&\alpha_{4p-3}&0\end{pmatrix}.$

  * •

If $p\equiv 9\pmod{10}$, then $e\equiv 4\pmod{5}$, and we have

$M=\begin{pmatrix}0&0&0&\alpha_{p-4}\\\ 0&0&\alpha_{2p-3}&0\\\
0&\alpha_{3p-2}&0&0\\\ \alpha_{4p-1}&0&0&0\end{pmatrix}.$

As in Proposition 3.2.3, we obtain the following proposition:

######  Proposition 3.3.3.

With notation as above, we have the following:

  * •

If $p\equiv 1\pmod{10}$, then ${H^{\prime}}_{\\!\\!\lambda}$ is superspecial
if and only if $\alpha_{3p-3}\\!=\\!\alpha_{4p-4}\\!=\\!0$.

  * •

If $p\equiv 3\pmod{10}$, then ${H^{\prime}}_{\\!\\!\lambda}$ is superspecial
if and only if $\alpha_{3p-4}\\!=\\!\alpha_{4p-2}\\!=\\!0$.

  * •

If $p\equiv 7\pmod{10}$, then ${H^{\prime}}_{\\!\\!\lambda}$ is superspecial
if and only if $\alpha_{3p-1}\\!=\\!\alpha_{4p-3}\\!=\\!0$.

  * •

If $p\equiv 9\pmod{10}$, then ${H^{\prime}}_{\\!\\!\lambda}$ is superspecial
if and only if $\alpha_{3p-2}\\!=\\!\alpha_{4p-1}\\!=\\!0$.

###### Proof.

This can be shown similarly to the proof of Proposition 3.2.3, and so let us
omit to write a proof here. ∎

We define $G:={\rm gcd}(\alpha_{3p-i},\alpha_{4p-j})$, where a pair $(i,j)$ is
given as

$(i,j):=\left\\{\begin{array}[]{l}(3,4)\quad{\rm if}\ p\equiv 1\pmod{10},\\\
(4,2)\quad{\rm if}\ p\equiv 3\pmod{10},\\\ (1,3)\quad{\rm if}\ p\equiv
7\pmod{10},\\\ (2,1)\quad{\rm if}\ p\equiv 9\pmod{10}.\end{array}\right.$
(3.9)

Hence, the curve ${H^{\prime}}_{\\!\\!\lambda}$ is superspecial if and only if
$G(\lambda)=0$. As in Proposition 3.2.4, we prove the following criteria to
make the isomorphism classification of listed superspecial
${H^{\prime}}_{\\!\\!\lambda}$’s efficient:

######  Proposition 3.3.4.

For $\lambda_{1},\lambda_{2}\in k\smallsetminus\\{0,1\\}$, the curve
${H^{\prime}}_{\\!\\!\lambda_{1}}$ is isomorphic to the curve
${H^{\prime}}_{\\!\\!\lambda_{2}}$ if and only if $\lambda_{1}=\lambda_{2}$ of
$\lambda_{1}=1/\lambda_{2}$.

###### Proof.

Write the two hyperelliptic curves ${H^{\prime}}_{\\!\\!\lambda_{1}}$ and
${H^{\prime}}_{\\!\\!\lambda_{2}}$ as

$\displaystyle{H^{\prime}}_{\\!\\!\lambda_{1}}$
$\displaystyle:y^{2}=(x^{5}-\alpha^{5})(x^{5}-\alpha^{-5}),\quad{\rm with}\
\alpha^{10}=\lambda_{1},$ $\displaystyle{H^{\prime}}_{\\!\\!\lambda_{2}}$
$\displaystyle:y^{2}=(x^{5}-\beta^{5})(x^{5}-\beta^{-5}),\quad\hskip
0.28453pt{\rm with}\ \beta^{10}=\lambda_{2}.$

Similarly to the proof of [7, Theorem 2.2], one can show that
${H^{\prime}}_{\\!\\!\lambda_{1}}\cong{H^{\prime}}_{\\!\\!\lambda_{2}}$ if and
only if

$\lambda_{1}+\frac{1}{\lambda_{1}}=\alpha^{10}+\frac{1}{\alpha^{10}}=\beta^{10}+\frac{1}{\beta^{10}}=\lambda_{2}+\frac{1}{\lambda_{2}},$

which is equivalent to $\lambda_{1}=\lambda_{2}$ or
$\lambda_{1}=1/\lambda_{2}$, as desired. ∎

Recall from Theorem 2.2.1 (especially Figure 1) that
$\mathrm{Aut}(H_{\lambda}^{\prime})$ is isomorphic to $\mathbf{D}_{10}$ or
$\mathbf{C}_{5}\rtimes\mathbf{D}_{4}$; we can easily decide which is the case
as follows:

######  Corollary 3.3.5.

The following statements are true:

  1. (1)

If $\lambda=-1$, then we have that ${\rm
Aut}({H^{\prime}}_{\\!\\!\lambda})\cong\mathbf{C}_{5}\rtimes\mathbf{D}_{4}$.

  2. (2)

Otherwise, we have that ${\rm
Aut}({H^{\prime}}_{\\!\\!\lambda})\cong\mathbf{D}_{10}$.

###### Proof.

The assertion (1) follows from Remark 3.3.2 and the case 10 of Table 1. For
any $\lambda\neq-1$, it follows from Proposition 3.3.4 that
${H^{\prime}}_{\\!\\!\lambda}$ is not isomorphic to ${H^{\prime}}_{\\!\\!-1}$,
as desired. ∎

Moreover, we can show the following results similarly to Theorem 3.2.6 and
Proposition 3.2.7.

######  Theorem 3.3.6.

With notation as above, the degree of $G$ is odd if and only if $p\equiv
9\pmod{10}$, and the number of superspecial hyperelliptic curves $H$ of genus
4 such that ${\rm Aut}(H)\cong{\mathbf{D}}_{10}$ is equal to

$\left\\{\begin{array}[]{l}\frac{1}{2}(\deg{G}-1)\quad{\rm if}\ p\equiv
9\pmod{10},\\\\[2.84526pt] \frac{1}{2}\deg{G}\hskip 13.37277pt\qquad{\rm
otherwise.}\end{array}\right.$

######  Proposition 3.3.7.

All roots of the polynomial $G$ belong to $\mathbb{F}_{p^{4}}$.

As in the case treated in Subsection 3.2, we expect from our computational
results that $\deg{G}$ (and thus the number of listed superspecial curves) is
bounded by a constant not depending on $p$, see Table 2 below. As a result of
the above discussion, we obtain the following algorithm:

######  Algorithm 3.3.8.

Input:

A rational prime $p\geq 7$.

Output:

A list $\mathcal{L}$ of representatives for the isomorphism classes of
superspecial genus-$4$ hyperelliptic curves $H$ over
$\overline{\mathbb{F}_{p}}$ with $\mathrm{Aut}(H)\cong\mathbf{D}_{10}$.

Step 1.

Compute $\beta_{3p-i}$ and $\beta_{4p-j}$ by using Proposition 2.1.3 (see also
the first paragraph in the proof of Theorem 3.2.9), where $(i,j)$ denotes a
pair of integers defined in (3.9).

Step 2.

Compute the polynomial $G:={\rm gcd}(\beta_{3p-i},\beta_{4p-j})$ and its roots
$\lambda\in\mathbb{F}_{p^{4}}$.

Step 3.

For each $\lambda\neq-1$ obtained in Step 2, if not $H_{1/\lambda}^{\prime}$
already belongs to $\mathcal{L}$, then set
$\mathcal{L}\leftarrow\mathcal{L}\hskip
1.42262pt\cup\\{H_{\lambda}^{\prime}\\}$. Finally, output a list
$\mathcal{L}$.

The complexity of this algorithm can be estimated as follows:

######  Theorem 3.3.9.

We can compute the number of superspecial genus-$4$ hyperelliptic curves $H$
with $\mathrm{Aut}(H)\cong\mathbf{D}_{10}$ in $\tilde{O}(p)$ operations in
$\mathbb{F}_{p}$, and we can list all of their isomorphism classes in
$\tilde{O}(p+d^{2})$ operations in $\mathbb{F}_{p^{4}}$ with
$d:=\deg{G}=O(p)$. Moreover, the complexity of listing up the isomorphism
classes becomes $\tilde{O}(p)$ operations in $\mathbb{F}_{p^{4}}$, if
$\deg{G}$ is bounded by a constant not depending on $p$.

###### Proof.

This can be shown similarly to the proof of Theorem 3.2.9. ∎

##  4 Computational results

We implemented Algorithms 3.1.3, 3.2.8, and 3.3.8 on Magma V2.26-10 on a
computer with Intel(R) Xeon(R) Gold 6130 CPU at 2.10GHz with 16 cores (32
threads) and 768GB memory. Executing the implemented algorithm, we obtain
Theorem 1 in Section 1. We here explain details dividing into enumeration
results and search ones.

Table 2: The total number of isomorphism classes of superspecial hyperelliptic
curves $H$ of genus $4$ with $\mathrm{Aut}(H)\supset\mathbf{D}_{4}$ for each
$p$ with $19\leq p<500$, and their classification by types of automorphism
groups. We denote $\mathbf{C}_{16}\rtimes\mathbf{C}_{2}$ and
$\mathbf{C}_{5}\rtimes\mathbf{D}_{4}$ by $\mathbf{G}_{32}$ and
$\mathbf{G}_{40}$ respectively.

$p$ | All | $\mathbf{D}_{4}$ | $\mathbf{D}_{8}$ | $\mathbf{D}_{10}$ | $\mathbf{G}_{32}$ | $\mathbf{G}_{40}$
---|---|---|---|---|---|---
19 | 2 | 1 | 0 | 0 | 0 | 1
23 | 1 | 1 | 0 | 0 | 0 | 0
29 | 2 | 1 | 0 | 0 | 0 | 1
31 | 3 | 1 | 1 | 0 | 1 | 0
37 | 4 | 3 | 1 | 0 | 0 | 0
41 | 2 | 0 | 0 | 1 | 1 | 0
43 | 2 | 2 | 0 | 0 | 0 | 0
47 | 5 | 4 | 0 | 0 | 1 | 0
53 | 6 | 6 | 0 | 0 | 0 | 0
59 | 4 | 2 | 0 | 1 | 0 | 1
61 | 4 | 2 | 0 | 1 | 0 | 0
67 | 4 | 4 | 0 | 0 | 0 | 0
71 | 6 | 4 | 1 | 1 | 0 | 0
73 | 6 | 5 | 0 | 0 | 1 | 0
79 | 9 | 7 | 0 | 0 | 1 | 1
83 | 10 | 10 | 0 | 0 | 0 | 0
89 | 7 | 4 | 0 | 1 | 1 | 1
97 | 4 | 4 | 0 | 0 | 0 | 0
101 | 7 | 4 | 2 | 1 | 0 | 0
103 | 10 | 9 | 1 | 0 | 0 | 0
107 | 11 | 11 | 0 | 0 | 0 | 0
109 | 7 | 5 | 0 | 1 | 0 | 1
113 | 13 | 13 | 0 | 0 | 0 | 0
127 | 14 | 13 | 0 | 0 | 1 | 0
131 | 12 | 12 | 0 | 0 | 0 | 0
137 | 11 | 9 | 1 | 0 | 1 | 0
139 | 19 | 16 | 0 | 2 | 0 | 1
149 | 15 | 13 | 0 | 1 | 0 | 1
151 | 10 | 10 | 0 | 0 | 0 | 0
157 | 16 | 13 | 3 | 0 | 0 | 0
163 | 8 | 8 | 0 | 0 | 0 | 0
167 | 19 | 17 | 2 | 0 | 0 | 0
173 | 11 | 11 | 0 | 0 | 0 | 0
179 | 23 | 19 | 0 | 3 | 0 | 1
181 | 14 | 10 | 3 | 1 | 0 | 0
191 | 37 | 31 | 3 | 2 | 1 | 0
193 | 18 | 18 | 0 | 0 | 0 | 0
197 | 12 | 9 | 3 | 0 | 0 | 0
199 | 26 | 22 | 2 | 1 | 0 | 1
211 | 22 | 20 | 0 | 2 | 0 | 0
223 | 37 | 35 | 1 | 0 | 1 | 0
227 | 15 | 15 | 0 | 0 | 0 | 0
229 | 13 | 10 | 0 | 2 | 0 | 1
233 | 13 | 11 | 1 | 0 | 1 | 0

$p$ | All | $\mathbf{D}_{4}$ | $\mathbf{D}_{8}$ | $\mathbf{D}_{10}$ | $\mathbf{G}_{32}$ | $\mathbf{G}_{40}$
---|---|---|---|---|---|---
239 | 33 | 30 | 0 | 1 | 1 | 1
241 | 20 | 17 | 1 | 2 | 0 | 0
251 | 27 | 27 | 0 | 0 | 0 | 0
257 | 17 | 16 | 1 | 0 | 0 | 0
263 | 35 | 34 | 1 | 0 | 0 | 0
269 | 39 | 32 | 3 | 3 | 0 | 1
271 | 48 | 40 | 5 | 2 | 1 | 0
277 | 28 | 28 | 0 | 0 | 0 | 0
281 | 14 | 11 | 1 | 1 | 1 | 0
283 | 24 | 24 | 0 | 0 | 0 | 0
293 | 19 | 19 | 0 | 0 | 0 | 0
307 | 22 | 22 | 0 | 0 | 0 | 0
311 | 44 | 42 | 1 | 1 | 0 | 0
313 | 30 | 28 | 1 | 0 | 1 | 0
317 | 26 | 26 | 0 | 0 | 0 | 0
331 | 36 | 36 | 0 | 1 | 0 | 0
337 | 22 | 22 | 0 | 0 | 0 | 0
347 | 16 | 16 | 0 | 0 | 0 | 0
349 | 35 | 32 | 0 | 2 | 0 | 1
353 | 30 | 29 | 1 | 0 | 0 | 0
359 | 56 | 53 | 0 | 2 | 0 | 1
367 | 45 | 43 | 1 | 0 | 1 | 0
373 | 28 | 28 | 0 | 0 | 0 | 0
379 | 36 | 33 | 0 | 2 | 0 | 1
383 | 58 | 56 | 1 | 0 | 1 | 0
389 | 39 | 36 | 0 | 2 | 0 | 1
397 | 27 | 27 | 0 | 0 | 0 | 0
401 | 41 | 39 | 1 | 1 | 0 | 0
409 | 35 | 30 | 1 | 2 | 1 | 1
419 | 45 | 39 | 0 | 5 | 0 | 1
421 | 36 | 32 | 4 | 0 | 0 | 0
431 | 64 | 61 | 0 | 2 | 1 | 0
433 | 41 | 40 | 1 | 0 | 0 | 0
439 | 64 | 56 | 2 | 5 | 0 | 1
443 | 37 | 37 | 0 | 0 | 0 | 0
449 | 28 | 27 | 0 | 0 | 0 | 1
457 | 43 | 42 | 0 | 0 | 1 | 0
461 | 33 | 29 | 0 | 4 | 0 | 0
463 | 47 | 44 | 2 | 0 | 1 | 0
467 | 36 | 36 | 0 | 0 | 0 | 0
479 | 73 | 68 | 1 | 2 | 1 | 1
487 | 40 | 38 | 1 | 0 | 0 | 0
491 | 43 | 42 | 0 | 1 | 0 | 0
499 | 49 | 47 | 0 | 1 | 0 | 1

#### Enumeration results.

As indicated in Theorem 1, our enumeration results involve the number of
isomorphism classes of superspecial hyperelliptic curves $H$ of genus $4$ in
each type of automorphism group containing $\mathbf{D}_{4}$ for $19\leq
p<500$, and they are summarized in Table 2. Note that there is no such a curve
in characteristic $p\leq 17$. We see from Table 2 that the number of
superspecial $H$’s with $\mathrm{Aut}(H)\cong\mathbf{D}_{4}$ would follow
$O(p)$, as estimated in Section 3.1. On the other hand, the number of
superspecial $H$’s with automorphism group of other type might be bounded by a
constant not depending on $p$.

We can easily increase the upper bound on $p$ in Table 2: We have succeeded in
finishing the computation of $\overline{\mathbb{F}_{p}}$-isomorphism classes
for all $19\leq p<500$ within a few day in total, on the computer described
above. For example, the execution for $p=499$ took only 1,441 seconds. More
specifically, the time taken for Step 1 was 971 seconds, while that for Steps
2–3 was 470 seconds.

#### Search results.

Search here means that we find a single superspecial hyperelliptic curve $H$
of genus $4$ with $\mathrm{Aut}(H)\supset\mathbf{D}_{4}$. For this, we
construct and implement an algorithm based on the following strategy:

  1. (1)

It follows from Corollary 2.2.2 that there does exist a superspecial $H$ with
$\mathrm{Aut}(H)\cong\mathbf{C}_{16}\rtimes\mathbf{C}_{2}$ (resp.
$\mathrm{Aut}(H)\cong\mathbf{C}_{5}\rtimes\mathbf{D}_{4}$) if
$p\equiv-1,9\pmod{16}$ (resp. $p\equiv 9\pmod{10}$). In these cases, we need
not to execute any of Algorithms 3.1.3, 3.2.8, nor 3.3.8. Otherwise, we
proceed with (2) and (3) in order.

  2. (2)

We try to find a superspecial $H$ with $\mathrm{Aut}(H)\cong\mathbf{D}_{8}$ or
$\mathrm{Aut}(H)\cong\mathbf{D}_{10}$ by Algorithms 3.2.8 and 3.3.8. For our
purpose, it suffices to compute one root of $F$ (resp. $G$) in Step 2 of
Algorithm 3.2.8 (resp. Algorithm 3.3.8).

  3. (3)

When we fail to produce a superspecial $H$ by (2), we next execute Algorithm
3.1.3. For the efficiency of the search, we modify Algorithm 3.1.3 as follows:
Once a single genus-$2$ superspecial curve $C$ is generated in Step 1 of
Algorithm 3.1.3, we check whether there exists $C^{\prime}$ with $C\cong
C^{\prime}$ such that the normalization $H$ of
$C\times_{\mathbb{P}^{1}}C^{\prime}$ is a genus-$4$ superspecial hyperelliptic
curve with $\mathrm{Aut}(H)\cong\mathbf{D}_{4}$, by using Lemma 3.1.1.

Executing the search algorithm on Magma, we succeeded in finding a
superspecial hyperelliptic curve $H$ of genus $4$ with
$\mathrm{Aut}(H)\supset\mathbf{D}_{4}$ for every $p$ with $19\leq p<7000$, as
in [22]. We have succeeded in finishing the search for all $p$ in the interval
within a week in total, on the same computer used for the enumeration. This
upper bound can be also updated easily:

  * •

Among $19\leq p<7000$, the maximal time for finding a single superspecial
curve was 19,144 seconds ($\approx$ 5.4 hours) for $p=6763$. In this case, we
failed to find such a curve by (2) of the above strategy, and most of the time
was spent for (3) (the time spent for (3) was 19,119 seconds), whose
complexity is bounded by that of Algorithm 3.1.3 (i.e., ${O}(p^{3})$ as
estimated in Section 3.1).

  * •

Even in the case where we fail to find any superspecial curve in (2), there
are many large $p$ for which such a curve was found in shorter time (e.g.,
only 6.8 seconds spent for proceeding with (3) when $p=6373$).

  * •

Fortunately if we can find a single superspecial curve only by (2) (not
proceeding with (3)), the time spent for (2) is expected to follow
$\tilde{O}(p)$ (cf. Theorems 3.2.9 and 3.3.9), and thus in most cases it would
be quite shorter than that for (3). For example, we found such a curve by (2)
in 27.6 seconds for $p=6997$.

From our search results, we obtain the following conjecture:

######  Conjecture 1.

  1. (1)

There exists a superspecial hyperelliptic curve $H$ of genus $4$ with
$\mathrm{Aut}(H)\cong\mathbf{D}_{4}$ in arbitrary characteristic $p$ with
$p\geq 19$ and $p\neq 41$.

  2. (2)

There does not exist any superspecial hyperelliptic curve $H$ of genus $4$
with $\mathrm{Aut}(H)\supset\mathbf{D}_{8}$ if $p\equiv 3\pmod{8}$.

  3. (3)

There does not exist any superspecial hyperelliptic curve $H$ of genus $4$
with $\mathrm{Aut}(H)\supset\mathbf{D}_{10}$ if $p\equiv 3,7\pmod{10}$.

##  5 Concluding remarks

We proposed an algorithm (Algorithm 3.1.3) to enumerate superspecial
hyperelliptic curves $H$ of genus $4$ with
$\mathrm{Aut}(H)\supset\mathbf{D}_{4}$, as a simpler version of the algorithm
provided in [22]. All the computations of the algorithm are done in
$\mathbb{F}_{p^{4}}$, and the total complexity is expected to be $O(p^{3})$
operations in $\mathbb{F}_{p^{4}}$. More efficient algorithms (Algorithms
3.2.8 and 3.3.8) specific to the case where
$\mathrm{Aut}(H)\supset\mathbf{D}_{8}$ or
$\mathrm{Aut}(H)\supset\mathbf{D}_{10}$ were also constructed by utilizing
Cartier-Manin matrices and Gauss’ hypergeometric series. Their complexities
are both $\tilde{O}(p^{2})$ (in practice $\tilde{O}(p)$) operations in
$\mathbb{F}_{p^{4}}$, which would become $\tilde{O}(p)$ operations in
$\mathbb{F}_{p}$ when one computes only the number of isomorphism classes. By
executing the algorithms on Magma, we succeeded in enumerating all the
isomorphism classes of superspecial hyperelliptic curves $H$ of genus $4$ with
$\mathrm{Aut}(H)\supset\mathbf{D}_{4}$ for every $p$ from $19$ to $500$. We
also succeeded in finding such a curve for every $p$ from $19$ to $7000$. From
our computational results, we obtain a conjecture (Conjecture 1) that there
exists a superspecial hyperelliptic curve $H$ of genus $4$ with
$\mathrm{Aut}(H)\supset\mathbf{D}_{4}$ in arbitrary characteristic $p$ with
$p\geq 19$.

A future work is to theoretically prove Conjecture 1. Constructing an
efficient algorithm in the case where $\mathrm{Aut}(H)\cong\mathbf{C}_{4}$ or
$\mathrm{Aut}(H)\cong\mathbf{Q}_{8}$ would be also an interesting problem.

### Acknowledgments

This research was conducted under a contract of “Research and development on
new generation cryptography for secure wireless communication services” among
“Research and Development for Expansion of Radio Wave Resources (JPJ000254)”,
which was supported by the Ministry of Internal Affairs and Communications,
Japan. This work was supported by JSPS Grant-in-Aid for Young Scientists
20K14301 and 23K12949.

## References

  * [1] W. Bosma, J. Cannon, and C. Playoust: The Magma algebra system. I. The user language, Journal of Symbolic Computation 24 (1997), 235–265.
  * [2] P. Dartois, L. Maino, G. Pope, and D. Robert: An algorithmic approach to $(2,2)$-isogenies in the theta model and applications to isogeny-based cryptography, preprint, https://ia.cr/2023/1747.
  * [3] T. Ekedahl: On supersingular curves and abelian varieties, Math. Scand., 60 (1987), 151–-178.
  * [4] R. Fuhrmann, A. Garcia, and F. Torres: On maximal curves, J. Number Theory, 67 (1997), 29–51.
  * [5] J. Igusa: Class number of a definite quaternion with prime discriminant, Proc. Nat. Acad. Sci. U.S.A., 44 (1958), 312–314.
  * [6] T. Ibukiyama, T. Katsura, and F. Oort: Supersingular curves of genus two and class numbers, Compositio Math., 57 (1986), no. 2, 127–152.
  * [7] N. Ishii: The automorphism group and invariants of a curve of genus 2, J. Res. Inst. Sci. Tech., Nihon Univ. 126 (2011), 6–11.
  * [8] M. Kudo: Counting isomorphism classes of superspecial curves, Theory and Applications of Supersingular Curves and Supersingular Abelian Varieties, RIMS Kôkyûroku Bessatsu, B90 (2022), 77–95, Research Institute for Mathematical Sciences, Kyoto University.
  * [9] M. Kudo and S. Harashita: Superspecial curves of genus 4 in small characteristic, Finite Fields and Their Applications, 45, 131–169 (2017).
  * [10] M. Kudo and S. Harashita: Superspecial Hyperelliptic Curves of Genus 4 over Small Finite Fields, In: L. Budaghyan and F. Rodriguez-Henriquez (eds), Arithmetic of Finite Fields, WAIFI 2018, LNCS, 11321, pp. 58–73, Springer, Cham, 2018, (DOI) 10.1007/978-3-030-05153-2_3
  * [11] M. Kudo and S. Harashita: Computational approach to enumerate non-hyperelliptic superspecial curves of genus 4, Tokyo Journal of Mathematics, 43, Number 1, 259–278, 2020, (DOI) doi:10.3836/tjm/1502179310
  * [12] M. Kudo and S. Harashita: Algorithmic study of superspecial hyperelliptic curves over finite fields, Commentarii Mathematici Universitatis Sancti Pauli, 70, 49–64, 2022, (DOI) doi/10.14992/00022411
  * [13] M. Kudo, S. Harashita, and E. W. Howe: Algorithms to enumerate superspecial Howe curves of genus $4$, Proceedings of Fourteenth Algorithmic Number Theory Symposium (ANTS-XIV), Open Book Series, Vol. 4 (1), 301–316, 2020.
  * [14] M. Kudo, T. Nakagawa, and T. Takagi: Efficient search for superspecial hyperelliptic curves of genus four with automorphism group containing $\mathbb{Z}_{6}$, preprint, arXiv: 2210.14822.
  * [15] M. Kudo, T. Nakagawa, and T. Takagi: Efficient search for superspecial hyperelliptic curves of genus four with automorphism group containing ${\mathrm{C}}_{6}$, Math. Comput. Sci. 17 (2023), Article number: 21.
  * [16] R. Lercier, J. Sijsling, and C. Ritzenthaler: Functionalities for genus 2 and 3 curves, arXiv:2102.04372.
  * [17] T. Moriya and M. Kudo: Some Explicit arithmetics on curves of genus three and their applications, arxiv: 2209.02926.
  * [18] S. A. Novoselov: Counting points on hyperelliptic curves of type $y^{2}=x^{2g+1}+ax^{g+1}+bx$, Finite Fields Appl. 68 (2020), 101757.
  * [19] N.O.Nygaard: Slopes of powers of Frobenius on crystalline cohomology, Ann. Sci. Éc. Norm. Supér 14.4 (1981), 369–401.
  * [20] R. Ohashi: On the Rosenhain forms of superspecial curves of genus two, preprint, arXiv: 2308.11963.
  * [21] R. Ohashi, M. Kudo, and S. Harashita: The $a$-numbers of non-hyperelliptic curves of genus three with cyclic automorphism group of order 6 and 9, preprint, arxiv: 2111.09777.
  * [22] R. Ohashi, M. Kudo, and S. Harashita: Fast enumeration of superspecial hyperelliptic curves of genus $4$ with automorphism group $V_{4}$, Arithmetic of finite fields. 9th international workshop, WAIFI 2022, LNCS, 13638, 107–124 (2023).
  * [23] R. Ohashi, H. Onuki, M. Kudo, R. Yoshizumi, and K. Nuida: Computing Richelot isogeny graph of superspecial abelian threefolds, in preparation.
  * [24] J. Paulhus: Decomposing Jacobians of curves with extra automorphisms, Acta Arith., 132 (2008), No. 3, 231–244.
  * [25] Robert C. Valentini: Hyperelliptic curves with zero Hasse-Witt matrix, Manuscripta Math., 86 (1995), 185–194.

##  A Some facts on Gauss’ hypergeometric series

In this appendix, we correct some facts related to Gauss’ hypergeometric
series, which are used in the main contents of this paper. Let $K$ be an
arbitrary field of characteristic $p\geq 5$.

######  Lemma A.1.

For an integer $d>0$, the following statements are true:

  1. (1)

If $0\leq b\leq a$, then we have

$\sum_{n=0}^{d}\binom{a}{n}\binom{a}{b-n}z^{n}=\binom{a}{b}G^{(d)}(-a,-b,1+a-b\,;z).$

  2. (2)

If $a\leq b\leq 2a$, then we have

$\sum_{n=0}^{d}\binom{a}{n}\binom{a}{b-n}z^{n}=z^{b-a}\cdot\binom{a}{2a-b}G^{(d)}(-a,b-2a,1+b-a\,;z).$

###### Proof.

This follows from a simple computation. ∎

We consider an element $\lambda\neq 0,1$ of the field $K$. Let $\gamma_{k}$ be
the $x^{k}$-coefficient of the polynomial $\\{(x-1)(x-\lambda)\\}^{e}$ with
$e:=(p-1)/2$.

######  Lemma A.2.

For an integer $0\leq k\leq e$, we have

$\gamma_{k}=(-1)^{p-1-k}\sum_{n=0}^{k}\binom{(p-1)/2}{n}\binom{(p-1)/2}{k-n}\lambda^{e-k+n}.$

###### Proof.

Let $e:=(p-1)/2$, then we can compute

$(x-1)^{e}=\sum_{i=0}^{e}\\!\binom{e}{i}(-1)^{e-i}x^{i},\quad(x-\lambda)^{e}=\sum_{j=0}^{e}\\!\binom{e}{j}(-\lambda)^{e-j}x^{j},$

and hence we obtain

$\\{(x-1)(x-\lambda)\\}^{(p-1)/2}=\sum_{k=0}^{p-1}\Biggl{(}\,\sum_{i+j=k}\\!\binom{e}{i}\\!\binom{e}{j}(-1)^{e-i}(-\lambda)^{e-j}\\!\Biggr{)}x^{k}.$

Comparing the $x^{k}$-coefficients of both sides, we have this lemma. ∎

Combining the above two lemmas together, we can write $\gamma_{k}$ as a
truncation of Gauss’ hypergeometric series:

######  Proposition A.3.

The following statements are true:

  1. (1)

If $0\leq k\leq e$, then we have

$\gamma_{k}\equiv\lambda^{e-k}\cdot(-1)^{k}\binom{e}{k}G^{(k)}(1/2,-k,1/2-k\,;\lambda)\pmod{p}.$

  2. (2)

If $e\leq k\leq p-1$, then we have

$\gamma_{k}\equiv(-1)^{k}\binom{e}{p-1-k}G^{(k)}(1/2,1+k,3/2+k\,;\lambda)\pmod{p}.$

###### Proof.

It follows from the previous lemmas. ∎

######  Corollary A.4.

For all $0\leq k\leq e$, we have that
$\gamma_{e-k}\equiv\gamma_{e+k}\lambda^{k}\pmod{p}$.

###### Proof.

It follows from Corollary A.3 that

$\displaystyle\gamma_{e-k}$
$\displaystyle\equiv\lambda^{k}\cdot(-1)^{e-k}\binom{e}{e-k}G^{(e-k)}(1/2,-e+k,1/2-e+k\,;\lambda)$
$\displaystyle\equiv\lambda^{k}\cdot(-1)^{e+k}\binom{e}{e-k}G^{(e+k)}(1/2,1+e+k,3/2+e+k\,;\lambda)$
$\displaystyle\equiv\gamma_{e+k}\lambda^{k}\pmod{p}.$

Here, we use the fact that

$G^{(e+k)}(1/2,-e+k,1/2-e+k\,;\lambda)=G^{(e-k)}(1/2,-e+k,1/2-e+k\,;\lambda)$

since $\lambda^{n}$-terms are vanished $\pmod{p}$ for all $e-k<n\leq e+k$. ∎