# Elliptic curves over Hasse pairs

Eleni Agathocleous  Max-Planck-Institut für Mathematik, Vivatsgasse 7, D-53111
Bonn, Germany<EMAIL_ADDRESS>,  Antoine Joux  CISPA Helmholtz
Center for Information Security, Stuhlsatzenhaus 5, 66123 Saarbrücken,
Germany<EMAIL_ADDRESS>and  Daniele Taufer  KU Leuven, Celestijnenlaan 200A -
box 2402, 3001 Leuven, Belgium<EMAIL_ADDRESS>
###### Abstract.

We call a pair of distinct prime powers
$(q_{1},q_{2})=(p_{1}^{a_{1}},p_{2}^{a_{2}})$ a Hasse pair if
$|\sqrt{q_{1}}-\sqrt{q_{2}}|\leq 1$. For such pairs, we study the relation
between the set $\mathcal{E}_{1}$ of isomorphism classes of elliptic curves
defined over $\mathbb{F}_{q_{1}}$ with $q_{2}$ points, and the set
$\mathcal{E}_{2}$ of isomorphism classes of elliptic curves over
$\mathbb{F}_{q_{2}}$ with $q_{1}$ points. When both families $\mathcal{E}_{i}$
contain only ordinary elliptic curves, we prove that their isogeny graphs are
isomorphic. When supersingular curves are involved, we describe which curves
might belong to these sets. We also show that if both the $q_{i}$’s are odd
and $\mathcal{E}_{1}\cup\mathcal{E}_{2}\neq\emptyset$, then
$\mathcal{E}_{1}\cup\mathcal{E}_{2}$ always contains an ordinary elliptic
curve. Conversely, if $q_{1}$ is even, then
$\mathcal{E}_{1}\cup\mathcal{E}_{2}$ may contain only supersingular curves
precisely when $q_{2}$ is a given power of a Fermat or a Mersenne prime. In
the case of odd Hasse pairs, we could not rule out the possibility of an empty
union $\mathcal{E}_{1}\cup\mathcal{E}_{2}$, but we give necessary conditions
for such a case to exist. In an appendix, Moree and Sofos consider how
frequently Hasse pairs occur using analytic number theory, making a connection
with Andrica’s conjecture on the difference between consecutive primes.

###### 2020 Mathematics Subject Classification:

11G07, 11G15, 14K02

with an appendix by

PIETER MOREE AND EFTHYMIOS SOFOS

##  1\. Introduction

Given an elliptic curve $E$ over a finite field $\mathbb{F}_{q}$ of
characteristic $p$, its number of points $|E(\mathbb{F}_{q})|$ is directly
related with a number $t$, called the trace of $E/\mathbb{F}_{q}$, which is
defined as

$t=q+1-|E(\mathbb{F}_{q})|.$

All elliptic curves over $\mathbb{F}_{q}$ with the same number of rational
points have the same trace, which we will denote by $t$. We can then consider
the set $\mathcal{E}(t)$ of $\mathbb{F}_{q}$-isomorphism classes of elliptic
curves $E/\mathbb{F}_{q}$ with trace $t$:

$\mathcal{E}(t)=\\{E/\mathbb{F}_{q}\ :\
|E(\mathbb{F}_{q})|=q+1-t\\}/\\{\mathbb{F}_{q}\textnormal{-isomorphisms}\\}.$

It is of both mathematical and cryptographic interest, to study such families
$\mathcal{E}(t)$ over some finite field $\mathbb{F}_{q}$, when the number of
points, and therefore the trace $t$, is given. In this paper, we are
interested in a ‘dual formulation’ of this problem: given two prime powers
$q_{1},q_{2}$, we investigate the two sets

$\mathcal{E}_{1}=\\{E_{1}/\mathbb{F}_{q_{1}}\ :\
|E_{1}(\mathbb{F}_{q_{1}})|=q_{2}\\}/\\{\mathbb{F}_{q_{1}}\textnormal{-isomorphisms}\\},$

and

$\mathcal{E}_{2}=\\{E_{2}/\mathbb{F}_{q_{2}}\ :\
|E_{2}(\mathbb{F}_{q_{2}})|=q_{1}\\}/\\{\mathbb{F}_{q_{2}}\textnormal{-isomorphisms}\\}.$

To exclude trivial cases, we further ask that the two prime powers
$q_{1},q_{2}$ be different and satisfy the relation

$|\sqrt{q_{1}}-\sqrt{q_{2}}|\leq 1.$

When this relation holds true, we call such a pair $(q_{1},q_{2})$ a _Hasse
pair_. We remark that the case $|\sqrt{q_{1}}-\sqrt{q_{2}}|>1$ is degenerate:
when $q_{1},q_{2}$ do not belong to the Hasse interval of each other, then
both sets $\mathcal{E}_{i}$ are necessarily empty.

The integer $t_{1}=q_{1}+1-q_{2}$ (resp. $t_{2}=q_{2}+1-q_{1}$) will be
referred to as the trace of $\mathcal{E}_{1}$ (resp. $\mathcal{E}_{2}$), as it
equals the trace of every curve (if any) in the corresponding set.

When $E_{1}\in\mathcal{E}_{1}$ and $E_{2}\in\mathcal{E}_{2}$ both arise as
good reductions of a global curve $E$, the pair $(q_{1},q_{2})$ was called
_amicable_ or $2$-_aliquot cycle_ for $E$ [7, 31], and the distribution of
amicable primes for a given $E$ was notably shown to depend on whether $E$ has
complex multiplication [16, 25, 31]. If the $E_{i}$’s share the same
endomorphism ring $\mathcal{O}$, the pair $(q_{1},q_{2})$ has been referred to
as _dual elliptic_ associated to $\mathcal{O}$ [21]. In cryptography, such
pairs of curves $(E_{1},E_{2})$ are called _2-cycles_ , and may be employed to
design recursive zk-SNARK protocols [5]. Those are particularly efficient when
the considered curves are pairing-friendly, which poses strong constraints on
the feasible curves [4, 9]. Examples of such applications appeared, among
others, in [6, 14, 15, 20], and we refer the interested reader to [2] for an
extensive survey on this topic.

###  1.1. Novel contributions

Unlike previous related works, in this paper we do not start from a global
curve. We observe instead that for a given Hasse pair, the associated traces
$t_{i}$ are linearly dependent (Remark 3.2) and they have the same
discriminant $\Delta$ (Lemma 3.5), which prescribes whether the corresponding
elliptic curves are ordinary or supersingular (Lemma 3.10). Furthermore, even
though the set $\mathcal{E}_{i}$ may occasionally be empty, even when
$(q_{1},q_{2})$ is a Hasse pair, this never occurs when the $q_{i}$’s are pure
primes (Lemma 3.11); and in this case, both sets $\mathcal{E}_{i}$ consist of
ordinary elliptic curves, except for a few small exceptions (Remark 3.12).

For every choice of odd Hasse pair $(p_{1}^{a_{1}},p_{2}^{a_{2}})$, at least
one of the $p_{i}$’s is proved to split completely in
$\mathbb{Q}(\sqrt{\Delta})$ (Proposition 5.6).

For any Hasse pair $(q_{1},q_{2})$, both the sets $\mathcal{E}_{i}$ are likely
to consist of ordinary elliptic curves, and in this case, the directed
multigraphs of their prime degree $\mathbb{F}_{q_{i}}$-isogenies are
isomorphic (Theorem 6.9). However, special choices of the $q_{i}$’s may lead
to different configurations. When both the $q_{i}$’s are odd, at most one of
the sets $\mathcal{E}_{i}$ may contain supersingular elliptic curves
(Proposition 4.2), while this fails with even characteristic in a specific
list of cases involving Fermat and Mersenne primes (Theorem 4.6). Moreover, if
$q_{1}$ is even, then the existence of a curve in $\mathcal{E}_{1}$ is
sufficient to guarantee that $\mathcal{E}_{2}$ is also non-empty (Lemma 4.4
and Theorem 4.6).

The only open case left is $\mathcal{E}_{1}\cup\mathcal{E}_{2}=\emptyset$. In
even characteristic this can happen, but we found only one such instance,
namely $(q_{1},q_{2})=(2^{8},3^{5})$. We did not find any such a pair when
both the $q_{i}$’s are odd, and we proved that such an example (if existent)
should satisfy strict numerical conditions (Proposition 5.11).

######  Problem 1.1.

Characterizing Hasse pairs $(q_{1},q_{2})$ such that $\mathcal{E}_{1}$ and
$\mathcal{E}_{2}$ are both empty. In particular, deciding if the set of such
pairs is finite (or even empty, in odd characteristics).

To the best of our knowledge, Problem 1.1 is open, except for cases of very
small exponents ruled out by Corollary 5.12. The possible configurations of
sets $\mathcal{E}_{i}$ discussed in the present paper are displayed by Tables
1 and 2.

Finally, given the interesting properties that these sets of elliptic curves
and their graphs exhibit, it is natural to ask, not only out of mathematical
curiosity but also from a cryptographic perspective, whether there are many
Hasse pairs. This question is directly related to a long-standing conjecture
known as Andrica’s conjecture, which states that the difference of the square
roots of any two consecutive primes is always less than one. In Appendix A,
Moree and Sofos discuss this conjecture in the context of prime powers, and
they prove an asymptotic result regarding the number of Hasse pairs in which a
given prime $p$ can be a member.

###  1.2. Notation

We denote the set of natural numbers by $\mathbb{N}=\\{0,1,\dots\\}$, and its
positive subset by $\mathbb{Z}_{>0}=\\{1,2,\dots\\}$. We write $p^{a}||N$ when
$p^{a}|N$ but $p^{a+1}\nmid N$. When the order of the elements of a pair is
irrelevant, we denote it by $((q_{1},q_{2}))$ to indicate $(q_{1},q_{2})$ or
$(q_{2},q_{1})$.

###  1.3. Paper organization

In Section 2 we recall a theorem of Waterhouse on valid traces, and we prove a
corollary of this result regarding elliptic curves of $j$-invariant zero. In
Section 3, we define Hasse pairs and we establish several properties of its
associated discriminant $\Delta$ and traces $t_{1}$ and $t_{2}$. In Section 4
we focus on the non-ordinary cases, i.e. when at least one of the sets
$\mathcal{E}_{1}$ or $\mathcal{E}_{2}$ is empty or is comprised of
supersingular elliptic curves. Section 5 is devoted to the splitting behavior
of the base primes of a given Hasse pair in the corresponding imaginary
quadratic field $\mathbb{Q}(\sqrt{\Delta})$. In Section 6, we deal with the
ordinary case and we establish the correspondence between the isogeny graphs
of the elliptic curves in $\mathcal{E}_{1}$ and of those in $\mathcal{E}_{2}$.
Some numerical and visual examples of such graphs are presented in Section 7.
Finally, in Section 8, we summarise the results of the current paper, and we
draw our conclusions.

##  2\. Valid Traces

Let $q\in\mathbb{Z}_{>0}$ be a prime power. We consider all elliptic curves
over $\mathbb{F}_{q}$ with the same number of points or, equivalently, with
the same trace $t\in\mathbb{Z}$. We denote the set of
$\mathbb{F}_{q}$-isomorphism classes of such curves by $\mathcal{E}(t)$. The
following theorem of Waterhouse determines when $\mathcal{E}(t)$ is not empty
and the type of elliptic curves it contains.

######  Theorem 2.1 ([35, Theorem 4.1]).

Let $\mathcal{E}(t)$ be the set of elliptic curves of trace $t$ over
$\mathbb{F}_{q}=\mathbb{F}_{p^{a}}$. Then $\mathcal{E}(t)$ is non-empty
precisely in the following cases.

  1. $(a)$

$|t|\leq 2\sqrt{q}$, with $\gcd(t,q)=1$.

  2. $(b)$

$t=\pm 2\sqrt{q}$, and $a$ is even.

  3. $(c)$

$t=\pm\sqrt{q}$, with $p\not\equiv 1\bmod 3$ and $a$ is even.

  4. $(d)$

$t=\pm\sqrt{p^{a+1}}$, with $p\in\\{2,3\\}$ and $a$ is odd.

  5. $(e)$

$t=0$, and $(\textnormal{I})$ $a$ is odd or $(\textnormal{II})$ $a$ is even,
and $p\not\equiv 1\bmod 4$.

The elliptic curves of case (a) are ordinary. The curves of case (b) are
supersingular and have all their endomorphisms defined over
${\mathbb{F}_{q}}$, while the rest are supersingular but do not have all their
endomorphisms defined over ${\mathbb{F}_{q}}$.

By [35, Theorems 4.1 and 4.2], one can deduce the values of the $j$-invariants
for some of the cases of Theorem 2.1. Since we have not found this result in
the literature, we state and prove it here, for completeness.

######  Proposition 2.2.

The elliptic curves corresponding to cases (c) and (d) in Theorem 2.1 have
$j$-invariant $0$.

###### Proof.

Since the CM-discriminant is $\Delta=t^{2}-4q$, we have

$t=\begin{cases}\pm p^{\frac{a}{2}}&\textnormal{ with }a\textnormal{ even,}\\\
\pm p^{\frac{a+1}{2}}&\textnormal{ with }p\in\\{2,3\\},a\textnormal{ odd.}\\\
\end{cases}\implies\Delta=\begin{cases}-3q&\textnormal{ in case
}\eqref{W:odd1},\\\ (p-4)q&\textnormal{ in case }\eqref{W:odd2}.\\\
\end{cases}$

The elliptic curves corresponding to the above cases, do not have all their
endomorphisms defined over $\mathbb{F}_{q}$, hence by [35, Theorem 4.2-(3)]
the possible endomorphism rings arising from the elliptic curves in
$\mathcal{E}(t)$ have conductor coprime to $q$.

In case (c) the possible conductors are those dividing $\sqrt{q}$, therefore
the unique possible order is the maximal one, i.e. the ring of integers of
$\mathbb{Q}(\sqrt{-3})$, which is the endomorphism ring of curves with
$j$-invariant $0$.

Similarly, in case (d), if $p=2$ the possible conductors are those dividing
$2^{(a+1)/2}$, therefore the unique possible order is the ring of integers of
$\mathbb{Q}(i)$, which is defined by curves with $j$-invariant
$1728=0\in\mathbb{F}_{q}$. If $p=3$ the conductors need to divide
$3^{(a-1)/2}$, therefore the unique endomorphism order is the ring of integers
of $\mathbb{Q}(\sqrt{-3})$, which is again defined by curves with
$j$-invariant $0$. ∎

##  3\. Hasse pairs

Throughout the paper, $q_{1}=p_{1}^{a_{1}}$ and $q_{2}=p_{2}^{a_{2}}$ will
denote arbitrary prime powers. Given such a pair $(q_{1},q_{2})$, we consider
the (possibly empty) set of elliptic curves defined over $\mathbb{F}_{q_{1}}$
with $q_{2}$ rational points, and respectively the set of elliptic curves over
$\mathbb{F}_{q_{2}}$ with $q_{1}$ points. To avoid trivial repetitions, we
consider these curves up to $\mathbb{F}_{q_{i}}$-isomorphism.

######  Definition 3.1.

Let $(q_{1},q_{2})$ be a pair of distinct prime powers. For $(i,j)=((1,2))$,
we define

$\mathcal{E}_{i}=\\{E_{i}/\mathbb{F}_{q_{i}}\ :\
|E_{i}(\mathbb{F}_{q_{i}})|=q_{j}\\}/\\{\mathbb{F}_{q_{i}}\textnormal{-isomorphisms}\\}.$

We also define the _trace_ $t_{i}$ corresponding to such a pair as

$t_{i}=q_{i}+1-q_{j}.$

######  Remark 3.2.

The integers $t_{i}$ are the traces of the Frobenius morphism for every
elliptic curve (if any) in $\mathcal{E}_{i}$ [30, Remark V.2.6]. Moreover, by
adding their defining equations, we immediately see that

$t_{1}+t_{2}=2.$

######  Remark 3.3.

The results of the present paper would hold even when $q_{1}=q_{2}$. We have
excluded this case from Definition 3.1, since it leads to the trivial
relations $\mathcal{E}_{1}=\mathcal{E}_{2}$ and $t_{1}=t_{2}=1$. These curves
of trace $1$ are often called _anomalous_ curves, and are all ordinary by
Theorem 2.1 (a).

######  Definition 3.4.

We define the _discriminant_ associated with the pair $(q_{1},q_{2})$ as

$\Delta=(q_{1}-q_{2})^{2}-2(q_{1}+q_{2})+1.$

As we prove below, this is the maximal CM-discriminant of the curves in the
sets $\mathcal{E}_{i}$, when they are not empty. An analogous result for
amicable curves was already observed in [31, Proposition 3.4].

######  Lemma 3.5.

Let $t_{1},t_{2}$ and $\Delta$ be defined as above. Then

$t_{1}^{2}-4q_{1}=\Delta=t_{2}^{2}-4q_{2}.$

###### Proof.

By the definition of $t_{1}$ we have

$t_{1}^{2}-4q_{1}=(q_{1}-q_{2})^{2}+2(q_{1}-q_{2})+1-4q_{1}=\Delta,$

which is symmetric in $q_{1}$ and $q_{2}$, thus it also equals
$t_{2}^{2}-4q_{2}$. ∎

Hasse’s Theorem [30, Theorem V.1.1] implies that the sets $\mathcal{E}_{i}$
can be non-empty if the considered $q_{i}$’s are close enough. This motivates
the following definition.

######  Definition 3.6 (Hasse pair).

Let $q_{1},q_{2}$ be distinct prime powers. We call the pair $(q_{1},q_{2})$ a
_Hasse pair_ iff

$|\sqrt{q_{1}}-\sqrt{q_{2}}|\leq 1.$

When both $q_{1}$ and $q_{2}$ are odd, we will refer to it as an _odd Hasse
pair_.

The following lemma links the above definition to Hasse’s theorem.

######  Lemma 3.7.

Let $t_{1},t_{2}$ be defined as above. The following are equivalent:

  1. (1)

$(q_{1},q_{2})$ is a Hasse pair,

  2. (2)

$|t_{1}|\leq 2\sqrt{q_{1}}$,

  3. (3)

$|t_{2}|\leq 2\sqrt{q_{2}}$.

###### Proof.

Condition (1) is equivalent to

$\sqrt{q_{2}}-1\leq\sqrt{q_{1}}\leq\sqrt{q_{2}}+1.$

Since all the quantities are positive, this is equivalent to its squared
version, namely

$q_{2}-2\sqrt{q_{2}}+1\leq q_{1}\leq q_{2}+2\sqrt{q_{2}}+1.$

This can be written as

$-2\sqrt{q_{2}}\leq-(q_{2}-q_{1}+1)\leq 2\sqrt{q_{2}},$

which is condition (3). Since condition (1) is symmetric, the equivalence
between (1) and (2) follows in the same way, by reversing the roles of $q_{1}$
and $q_{2}$. ∎

An elliptic curve over $\mathbb{F}_{q_{i}}$ is called _supersingular_ if its
trace is divisible by $p_{i}$, and _ordinary_ otherwise. Since all the curves
in $\mathcal{E}_{i}$ (if any) have the same trace $t_{i}$, then the set
$\mathcal{E}_{i}$ is either empty or contains curves that have the same type
(i.e. they are all ordinary or all supersingular). This motivates the
following definition.

######  Definition 3.8.

We call the set $\mathcal{E}_{i}$ _ordinary_ (resp. _supersingular_) if it is
non-empty and contains ordinary (resp. supersingular) elliptic curves.

######  Remark 3.9.

We recall that two ordinary curves are isomorphic over $\mathbb{F}_{q}$ if and
only if they have the same size and the same $j$-invariant [10, Proposition
14.19]. Hence, when the set $\mathcal{E}_{i}$ is ordinary, it can be
identified with the set containing the $j$-invariants of all elliptic curves
that belong to $\mathcal{E}_{i}$.

######  Lemma 3.10.

Let $(q_{1},q_{2})$ be a Hasse pair. For both $i\in\\{1,2\\}$, the following
hold.

  * •

If $\gcd(\Delta,q_{i})=1$, then $\mathcal{E}_{i}$ is ordinary.

  * •

If $\gcd(\Delta,q_{i})\neq 1$, then $\mathcal{E}_{i}$ is either supersingular
or empty.

###### Proof.

We notice that

$\gcd(t_{i},q_{i})=1\iff\gcd(t_{i}^{2}-4q_{i},q_{i})=1\iff\gcd(\Delta,q_{i})=1.$

All the curves of $\mathcal{E}_{i}$ (if any) have trace $t_{i}$ (Remark 3.2),
hence they are ordinary when $\gcd(\Delta,q_{i})=1$, and supersingular when
$\gcd(\Delta,q_{i})\neq 1$. Since $|t_{i}|\leq 2\sqrt{q_{i}}$ by Lemma 3.7, in
the ordinary case the set $\mathcal{E}_{i}$ is always non-empty (see Theorem
2.1, case (a)). ∎

When dealing with pure primes, the sets $\mathcal{E}_{i}$ are almost always
comprised of ordinary curves, as shown by the next lemma.

######  Lemma 3.11.

If $(p_{1},q_{2})$ is a Hasse pair, with $p_{1}$ prime, then $\mathcal{E}_{1}$
is non-empty. Moreover, if $\mathcal{E}_{1}$ is supersingular then
$q_{2}=p_{1}+1$ or $p_{1}\in\\{2,3\\}$.

###### Proof.

Since $(q_{1},q_{2})$ is Hasse, by Lemma 3.7 we have $|t_{1}|\leq
2\sqrt{p_{1}}<2p_{1}.$ If $p_{1}\in\\{2,3\\}$, the integer values lying
between $-2p_{1}$ and $2p_{1}$ are either coprime to $p_{1}$ (a), or equal to
$\pm p_{1}$ (d), or equal to $0$ (e).

When $p_{1}>3$, we have the tighter bound $|t_{1}|\leq 2\sqrt{p_{1}}<p_{1}$.
In this case, the integers between $-p_{1}$ and $p_{1}$ are either coprime to
$p_{1}$ (a) or equal to $0$ (e). In all such cases, $\mathcal{E}_{1}$ is non-
empty by Theorem 2.1. Furthermore, if $p_{1}>3$ the only supersingular case
has $t_{1}=0$ which implies $q_{2}=p_{1}+1$. ∎

######  Remark 3.12.

As a consequence of Lemma 3.11, whenever $(p_{1},p_{2})$ is a Hasse pair
consisting of pure primes (i.e. $a_{1}=a_{2}=1$), in all but a few small
cases, both sets $\mathcal{E}_{i}$ are ordinary. A straightforward
verification of those cases shows that $\mathcal{E}_{1}$ is actually
supersingular precisely when $(p_{1},p_{2})\in\\{(2,3),(2,5),(3,7)\\}$.

######  Example 3.13.

Since $\sqrt{7}-\sqrt{3}=0.913\dots$, then $(p_{1},p_{2})=(3,7)$ is an odd
Hasse pair. Up to isomorphism, there is only one elliptic curve in
$\mathcal{E}_{1}$, defined by $y^{2}=x^{3}+2x+1.$ As $t_{1}=3+1-7=-3$, this
curve is supersingular. Similarly, there is only one curve in
$\mathcal{E}_{2}$, defined by $y^{2}=x^{3}+4.$ It has trace $t_{2}=2-t_{1}=5$,
hence it is ordinary. Finally, we notice that the $j$-invariant of both curves
is $0$, and this is not a coincidence as we show in Proposition 4.3.

##  4\. Non-ordinary cases

In this section, we discuss the relation between $\mathcal{E}_{1}$ and
$\mathcal{E}_{2}$ when $\gcd(\Delta,q_{1}q_{2})\neq 1$, namely when at least
one of these sets is either supersingular or empty.

We begin by noticing that non-ordinary cases may occur only in different
characteristics.

######  Lemma 4.1.

If $p_{1}=p_{2}$, then $\gcd(\Delta,q_{1}q_{2})=1$.

###### Proof.

If $p_{1}=p_{2}$, then $q_{i}=p_{1}^{e_{i}}$. Therefore

$\Delta=(q_{1}-q_{2})^{2}-2(q_{1}+q_{2})+1\equiv 1\bmod p_{1},$

which implies $\gcd(\Delta,q_{1}q_{2})=1$. ∎

###  4.1. Odd characteristics

When $q_{1}$ and $q_{2}$ are both odd, then so are $t_{1}$ and $t_{2}$.

######  Proposition 4.2.

Let $(q_{1},q_{2})$ be an odd Hasse pair. If $\mathcal{E}_{1}$ is
supersingular, then $\mathcal{E}_{2}$ is ordinary. Thus, if
$\mathcal{E}_{1}\cup\mathcal{E}_{2}$ is non-empty, then it always contains an
ordinary elliptic curve.

###### Proof.

Let $E_{1}\in\mathcal{E}_{1}$ be a supersingular curve. We first consider the
case $p_{1}\neq 3$. Since $t_{1}$ is odd, only case (c) of Theorem 2.1 can
apply. Thus, $a_{1}$ needs to be even and $t_{1}=\pm\sqrt{q_{1}}$, hence
$\Delta=t_{1}^{2}-4q_{1}=-3q_{1}.$ Since $\gcd(q_{1},q_{2})=1$ by Lemma 4.1,
then $\gcd(\Delta,q_{2})\in\\{1,3\\}$.

Let us assume by contradiction that $p_{2}=3$, then by Remark 3.2 we get

$2-t_{1}=t_{2}=3^{a_{2}}+1-p_{1}^{a_{1}},\quad\mbox{which implies}\quad
p_{1}^{a_{1}}\mp p_{1}^{\frac{a_{1}}{2}}+1=3^{a_{2}}.$

If $a_{2}=1$, then $q_{2}=3$ and the only odd prime powers inside its Hasse
interval are $5$ and $7$, both with odd exponents, contradicting the parity of
$a_{1}$. If $a_{2}>1$, then $x=-p_{1}^{\frac{a_{1}}{2}}$ should be a root of
one of the polynomials

$x^{2}\pm x+1\in\mathbb{Z}/9\mathbb{Z}[x],$

which is impossible since those polynomials are both irreducible. Hence, we
conclude that $p_{2}\neq 3$, which implies $\gcd(\Delta,q_{2})=1$, then
$\mathcal{E}_{2}$ is ordinary by Lemma 3.10.

Let us now consider the case $p_{1}=3$. Since $t_{1}$ is odd, by Theorem 2.1
we have

$t_{1}=\begin{cases}\pm 3^{\frac{a_{1}}{2}}&\textnormal{if }a_{1}\textnormal{
is even, \quad case~{}\eqref{W:odd1}},\\\ \pm
3^{\frac{a_{1}+1}{2}}&\textnormal{if }a_{1}\textnormal{ is odd, \ \quad
case~{}\eqref{W:odd2}},\end{cases}$

which leads us to

$\Delta=\begin{cases}(3^{\frac{a_{1}}{2}})^{2}-4\cdot
3^{a_{1}}=-3^{a_{1}+1}&\textnormal{if }a_{1}\textnormal{ is even,}\\\
(3^{\frac{a_{1}+1}{2}})^{2}-4\cdot 3^{a_{1}}=-3^{a_{1}}&\textnormal{if
}a_{1}\textnormal{ is odd.}\end{cases}$

By Lemma 4.1 we have $\gcd(q_{1},q_{2})=1$, therefore $3\nmid q_{2}$. Hence,
$\Delta$ and $q_{2}$ cannot have common factors and we conclude that
$\mathcal{E}_{2}$ is ordinary by Lemma 3.10.

Thus, for odd Hasse pairs the sets $\mathcal{E}_{i}$ cannot be both
supersingular, then if $\mathcal{E}_{1}\cup\mathcal{E}_{2}$ is not empty, then
it contains an ordinary elliptic curve. ∎

Next, we show that in odd characteristics, establishing the existence of
supersingular curves in $\mathcal{E}_{1}\cup\mathcal{E}_{2}$ only requires
testing curves with $j$-invariant $0$.

######  Proposition 4.3.

Let $(q_{1},q_{2})$ be an odd Hasse pair. If $E_{1}\in\mathcal{E}_{1}$ is
supersingular, then $j(E_{1})=0$. Furthermore, in this case $\mathcal{E}_{2}$
is ordinary and it also contains an elliptic curve with $j$-invariant $0$.

###### Proof.

Since $t_{1}$ is odd, we are in cases (c) or (d) of Theorem 2.1, thus by
Proposition 2.2 we have $j(E_{1})=0$. Moreover, by Proposition 4.2,
$\mathcal{E}_{2}$ is ordinary and, by [35, Theorem 4.2 (2)], the maximal order
always arises as the endomorphism ring of some curve in $\mathcal{E}_{2}$. We
have

$t_{1}=\begin{cases}\pm p_{1}^{\frac{a_{1}}{2}}&\textnormal{if
}a_{1}\textnormal{ is even,}\\\ \pm 3^{\frac{a_{1}+1}{2}}&\textnormal{if
}a_{1}\textnormal{ is
odd,}\end{cases}\implies\Delta=\begin{cases}-3p_{1}^{a_{1}}&\textnormal{if
}a_{1}\textnormal{ is even,}\\\ -3^{a_{1}}&\textnormal{if }a_{1}\textnormal{
is odd.}\end{cases}$

We observe that the maximal order in both cases is the ring of integers of
$\mathbb{Q}(\sqrt{-3})$, which is always isomorphic to the endomorphism ring
of elliptic curves of $j$-invariant $0$. ∎

###  4.2. Even characteristics

In this section, we discuss Hasse pairs involving even prime powers, so we
will assume $p_{1}=2$.

######  Lemma 4.4.

Let $(2^{a_{1}},q_{2})$ be a Hasse pair. The following are equivalent:

  1. (1)

$\mathcal{E}_{1}$ is ordinary,

  2. (2)

$q_{2}$ is even,

  3. (3)

$(2^{a_{1}},q_{2})\in\\{((2,4)),((4,8))\\}$.

###### Proof.

(1) $\Rightarrow$ (2): Since $\mathcal{E}_{1}$ is ordinary, then $t_{1}$ is
odd, so is $t_{2}$ (Remark 3.2). Therefore $q_{2}=t_{2}-1+2^{a_{1}}$ is even.

$\eqref{lem:ord-ord2-ii}\Rightarrow\eqref{lem:ord-ord2-iii}$: A
straightforward check shows that there are only two powers of $2$ lying in the
Hasse bound of each other, namely $\\{2,4\\}$ and $\\{4,8\\}$.

$\eqref{lem:ord-ord2-iii}\Rightarrow\eqref{lem:ord-ord2-i}$: Every
$(2^{a_{1}},q_{2})\in\\{((2,4)),((4,8))\\}$ has discriminant $\Delta=-7$,
which is coprime to $2^{a_{1}}$. Thus, $\mathcal{E}_{1}$ is ordinary by Lemma
3.10. ∎

The ordinary cases of Lemma 4.4 are detailed in Examples 7.2 and 7.3. Except
for such cases, if $\gcd(\Delta,q_{1}q_{2})\neq 1$ we can assume that $q_{2}$
is odd and $\mathcal{E}_{1}$ is supersingular or empty. In the supersingular
case, we know from Deuring [12, §8.2] that the only possible curves in
$\mathcal{E}_{1}$ have $j$-invariant $0$, similarly to the odd case
(Proposition 4.3).

However, with an even characteristic one may simultaneously find supersingular
curves in both $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$. To determine when this
is the case we need the following lemma. It is an easy instance of the theorem
of Mihăilescu [22], which proved the famous Catalan’s conjecture, but the
version we need can be proved with elementary techniques.

######  Lemma 4.5 ([28, pp. 201-203]).

Let $\alpha,\beta\geq 2$ be integers and let $p\in\mathbb{N}$ be a prime. If
$2^{\alpha}$ and $p^{\beta}$ are consecutive integers, then $\alpha=3,\beta=2$
and $p=3$.

######  Theorem 4.6.

Let $(q_{1},q_{2})=(2^{a_{1}},p_{2}^{a_{2}})$ be a Hasse pair. If
$\mathcal{E}_{1}$ is supersingular of trace $t_{1}$, then precisely one of the
following holds.

  1. (1)

$t_{1}=\pm 2^{\frac{a_{1}+2}{2}}$ and

$(q_{1},q_{2})=\begin{cases}(2^{6},3^{4}),&\textnormal{ or }\\\
\big{(}2^{2^{n+1}},(2^{2^{n}}+1)^{2}\big{)},&\textnormal{ with
}p_{2}=2^{2^{n}}+1\textnormal{ a Fermat prime, or }\\\
\big{(}2^{2m},(2^{m}-1)^{2}\big{)},&\textnormal{ with
}p_{2}=2^{m}-1\textnormal{ a Mersenne prime. }\end{cases}$

  2. (2)

$t_{1}=2$ and $(q_{1},q_{2})=(2^{2},3)$.

  3. (3)

$t_{1}=0$, or $a_{1}$ is odd and $t_{1}=\pm 2^{\frac{a_{1}+1}{2}}$, or $a_{1}$
is even, $t_{1}=\pm 2^{\frac{a_{1}}{2}}$ and $p_{2}\neq 3$.

In cases (1) and (2), $\mathcal{E}_{2}$ is supersingular, while in case (3),
$\mathcal{E}_{2}$ is ordinary.

###### Proof.

Since $\mathcal{E}_{1}$ is supersingular, then $p_{2}$ is odd by Lemma 4.4 and
$t_{1}$ is given by one of the cases (b)-(e) of Theorem 2.1. We examine such
cases separately.

Case (b): $a_{1}$ is even and $t_{1}=\pm 2^{\frac{a_{1}+2}{2}}$, thus
$\Delta=t_{1}^{2}-4q_{1}=2^{a_{1}+2}-4\cdot 2^{a_{1}}=0$. Since
$\Delta=t_{2}^{2}-4p_{2}^{a_{2}}$ by Lemma 3.5, then $a_{2}$ is also even. As
$(q_{1},q_{2})$ is Hasse, this implies that $2^{\frac{a_{1}}{2}}$ and
$p_{2}^{\frac{a_{2}}{2}}$ are consecutive integers. By Lemma 4.5 if
$\frac{a_{1}}{2},\frac{a_{2}}{2}\geq 2$ there is a unique possibility, namely
$(q_{1},q_{2})=(2^{6},3^{4})$, corresponding to the consecutive integers $8$
and $9$. Now consider the case where $a_{1}$ or $a_{2}$ is $2$. If $a_{1}=2$,
we straightforwardly verify that there are no Hasse pairs $(4,p_{2}^{a_{2}})$
with $a_{2}$ even. If $a_{2}=2$, then $2^{\frac{a_{1}}{2}}$ and $p_{2}$ are
consecutive integers, therefore $p_{2}$ is either a Fermat or a Mersenne
prime. It is easy to check that the corresponding traces $t_{2}$ fit into case
(b) of Theorem 2.1, hence in such cases $\mathcal{E}_{2}$ is supersingular.

Case (c): $a_{1}$ is even and $t_{1}=\pm 2^{\frac{a_{1}}{2}}$, then
$\Delta=-3\cdot 2^{a_{1}}$. If $p_{2}>3$ then $\mathcal{E}_{2}$ is ordinary by
Lemma 3.10. Let us consider $p_{2}=3$. By Lemma 3.5 we have

$-3\cdot 2^{a_{1}}=t_{2}^{2}-4\cdot 3^{a_{2}}.$

Since $-3$ is not a quadratic residue modulo $9$, the above equation may have
integer solutions only if $a_{2}=1$, hence $q_{2}=3$. We straightforwardly
check that the unique Hasse pair $(2^{a_{1}},3)$ with $a_{1}$ even is
$(2^{2},3)$, which gives $t_{1}=2,t_{2}=0$ and therefore $\mathcal{E}_{2}$
supersingular.

Cases (d) and (e): If $a_{1}$ is odd and $t_{1}=\pm 2^{\frac{a_{1}+1}{2}}$, or
if $t_{1}=0$, then $\Delta$ is a power of $2$, hence $\mathcal{E}_{2}$ is
ordinary by Lemma 3.10. ∎

######  Remark 4.7.

By Proposition 4.3 and Theorem 4.6, both sets $\mathcal{E}_{i}$ can be
simultaneously supersingular only if one of the considered prime powers is
even, and the other one involves primes of Fermat or Mersenne. On the other
side, if the Lenstra-Pomerance-Wagstaff conjecture [34] holds true, this would
imply the existence of infinitely many Mersenne primes, hence by Theorem 4.6
both sets $\mathcal{E}_{i}$ are supersingular infinitely many times.

######  Remark 4.8.

When both sets $\mathcal{E}_{i}$ are supersingular, they are often unrelated.
For instance, for $(q_{1},q_{2})=(2^{10},31^{2})$ the set $\mathcal{E}_{1}$
contains one curve of $j$-invariant $0\in\mathbb{F}_{2^{10}}$, while
$\mathcal{E}_{2}$ contains three curves of $j$-invariants
$2,4,23\in\mathbb{F}_{31^{2}}$. Instead, in the next sections we will prove
that this is never the case when both sets $\mathcal{E}_{i}$ are ordinary.

##  5\. The splitting behavior of the primes in odd Hasse pairs

In this section, we consider odd Hasse pairs $(q_{1},q_{2})$, and therefore
the traces $t_{i}$ are both odd integers.

######  Lemma 5.1.

Let $(q_{1},q_{2})$ be an odd Hasse pair. Then $\Delta<0$, $\Delta\equiv
1\bmod 4$ and $|\Delta|$ is not a perfect square.

###### Proof.

Since $(q_{1},q_{2})$ is Hasse and $t_{1}$ is odd, by Lemma 3.7 we have
$t_{1}<2\sqrt{q_{1}}$, hence by Lemma 3.5 we conclude

$\Delta=t_{1}^{2}-4q_{1}<0.$

Since $t_{1}^{2}\equiv 1\bmod 4$, the above equation implies $\Delta\equiv
1\bmod 4$, so $|\Delta|=-\Delta\equiv-1\bmod 4$. Therefore $|\Delta|$ cannot
be a square, as it is not a quadratic residue modulo $4$. ∎

We can write the discriminant $\Delta$ associated with $(q_{1},q_{2})$ as

$\Delta=f^{2}D,$

where $f$ is called the _conductor_ , and $D$ is the squarefree part of
$\Delta$. By Lemma 5.1, we have $D\equiv 1\bmod 4$ as well, hence $D$ is a
fundamental discriminant. We denote by $K$ the imaginary quadratic field

$K=\mathbb{Q}\big{(}\sqrt{\Delta}\big{)}=\mathbb{Q}\big{(}\sqrt{D}\big{)},$

and by $\mathcal{O}_{K}$ the maximal order of $K$.

######  Remark 5.2.

When $(q_{1},q_{2})$ is an odd Hasse pair, we observe that we never have
$K=\mathbb{Q}(i)$, since $\Delta\equiv 1\bmod 4$. Therefore, in this case, the
$j$-invariant $1728$ cannot correspond to an elliptic curve in either set
$\mathcal{E}_{i}$.

######  Remark 5.3.

By Lemma 3.5 we have $\Delta=t_{i}^{2}-4q_{i}$, from which we have

$q_{i}=\frac{{t_{i}}^{2}-\Delta}{4}=\textnormal{Norm}_{K/\mathbb{Q}}\left(\frac{t_{i}+\sqrt{\Delta}}{2}\right).$

It shows that $q_{i}$ is the norm from $K$ down to $\mathbb{Q}$, of the
integral element

$\pi_{i}=\frac{t_{i}+\sqrt{\Delta}}{2}\in\mathcal{O}_{K}.$

Furthermore, by Remark 3.2, we obtain the relation

$\pi_{i}=1-\overline{\pi_{j}},\qquad i\neq j.$ (1)

######  Remark 5.4.

Since $\Delta$ is not a square, the polynomial
$f_{i}(x)=x^{2}-t_{i}x+q_{i}\in\mathbb{Z}[x]$ is irreducible for
$i\in\\{1,2\\}$, and it is the minimal polynomial of the element
$\pi_{i}\in\mathcal{O}_{K}$. In particular, $\mathbb{Z}[\pi_{i}]$ are both
suborders of $\mathcal{O}_{K}$.

######  Remark 5.5.

The discriminant $\delta_{i}$ of each order $\mathbb{Z}[\pi_{i}]$ can be
easily computed as

$\delta_{i}=\left(\det\begin{pmatrix}1&\pi_{i}\\\
1&\overline{\pi}_{i}\end{pmatrix}\right)^{2}=\Delta=f^{2}D.$

Since $\pi_{1}-\pi_{2}=1-t_{2}$ by Remark 3.2, we also have
$\mathbb{Z}[\pi_{1}]=\mathcal{O}_{\Delta}=\mathbb{Z}[\pi_{2}]$.

######  Proposition 5.6.

Let $(q_{1},q_{2})$ be an odd Hasse pair. Then at least one of the base primes
$p_{i}$ splits completely in $K$.

###### Proof.

We equivalently show that in $\mathcal{O}_{K}$: (a) the $p_{i}$’s cannot be
both inert, and (b) if $p_{i}$ ramifies, then $p_{j}$ splits for $j\neq i$.

Case (a): The fact that
$\textnormal{Norm}_{K/\mathbb{Q}}(\pi_{i})=q_{i}=p_{i}^{a_{i}}$ implies that
$p_{i}$ is the unique prime of $\mathcal{O}_{K}$ that divides $\pi_{i}$, since
$\mathcal{O}_{K}$ is Dedekind and we have unique factorization of ideals.
Thus, for both $i\in\\{1,2\\}$ there are positive integer
$b_{i}\in\mathbb{Z}_{>0}$ such that

$(\pi_{i})=(p_{i}^{b_{i}}).$

If both primes $p_{i}$ were inert in $K$, by taking norms in the above
equation, we would have
$p_{i}^{a_{i}}=q_{i}=\textnormal{Norm}_{K/\mathbb{Q}}(\pi_{i})=p_{i}^{2b_{i}}$.
This in turn gives us that $a_{i}=2b_{i}$ should be both even. Since
$q_{1}\neq q_{2}$, it would imply that

$|\sqrt{q_{1}}-\sqrt{q_{2}}|=|p_{1}^{b_{1}}-p_{2}^{b_{2}}|>1,$

contradicting the fact that $(q_{1},q_{2})$ is Hasse.

Case (b): Assume without loss of generality that $p_{1}$ ramifies in $K$. From
Case (a) we know that only one of the exponents $a_{i}$ can be even.

(i) Let us first assume that $a_{1}$ is odd. Since $p_{1}$ ramifies in
$\mathcal{O}_{K}$, this implies that $p_{1}$ should divide the fundamental
discriminant $D$ of $K$, and therefore the power of $p_{1}$ dividing $\Delta$
must be odd. We recall that in the case of odd Hasse pairs, the fundamental
discriminant is not divisible by $4$ and is therefore squarefree. From the
following relation

$t_{1}^{2}-4q_{1}=\Delta=f^{2}D,$

it follows that $p_{1}|t_{1}$. Therefore, there exist $k_{1}\in\mathbb{Z}$ and
$b_{1}\in\mathbb{Z}_{>0}$ such that $t_{1}=k_{1}p_{1}^{b_{1}}$, with
$\gcd(k_{1},p_{1})=1$. By considering the parity of the exponents of $p_{i}$
in the above equation, we have that $2b_{1}>a_{1}$. However, since $\Delta<0$
and $p_{1}$ is odd, this case can only happen when $p_{1}=3$ and
$|t_{1}|=3^{\frac{a_{1}+1}{2}}$. This is case (d) of Theorem 2.1, which
implies that $\mathcal{E}_{1}$ is supersingular. Proposition 4.2 now implies
that $\text{gcd}(\Delta,p_{2})=1$, from which we conclude that
$\Delta=t_{2}^{2}-4q_{2}$ is a non-zero quadratic residue modulo $p_{2}$, and
so is $D$ since $D\equiv(\frac{t_{2}}{f})^{2}\bmod p_{2}$. Therefore $p_{2}$
must split in $K$ by [10, Proposition 5.16].

(ii) Assume now that $a_{1}$ is even, so $a_{2}$ is odd. Then, by Case (a)
$p_{2}$ cannot be inert. From Case (b-i) above, we see that $p_{2}$ cannot
ramify either, because this would imply that $p_{1}$ splits, contradicting our
assumption that $p_{1}$ ramifies. Hence, $p_{2}$ must split in $K$. ∎

######  Remark 5.7.

We note that if $\mathcal{E}_{i}$ is ordinary, then $p_{i}$ splits because
$\Delta\equiv t_{i}^{2}\bmod p_{i}$. The opposite, however, might not hold,
since $p_{i}$ may split and divide the conductor $f$ of $\Delta$. In
particular, Proposition 5.6 alone does not guarantee the existence of an
ordinary elliptic curve in $\mathcal{E}_{1}\cup\mathcal{E}_{2}$.

In the case of odd Hasse pairs $(p_{1},p_{2})$ with $p_{1},p_{2}$ pure primes,
one can conclude that both of them split completely in $K$ unless
$(p_{1},p_{2})=((3,7))$ (Example 5.8). However, this does not have to be true
for prime powers with exponent $>1$ (Example 5.9). Thus, the splitting of one
$p_{i}$ given by Proposition 5.6 is the best one can guarantee for Hasse pairs
in general.

######  Example 5.8.

Let us consider the Hasse pair $(3,7)$ as in Example 3.13, whose discriminant
is $\Delta=-3$. By Remarks 3.12 and 5.7, this is the unique odd Hasse pair
consisting of pure primes that are not both guaranteed to split completely. In
fact, $(3)=(\sqrt{-3})^{2}\subset\mathcal{O}_{K}$ is ramified, while $(7)$
splits because $\mathcal{E}_{2}$ is ordinary (Remark 5.7).

######  Example 5.9.

Since $\sqrt{307}=17.521\dots$, then $(17^{2},307)$ is an odd Hasse pair,
whose discriminant is $\Delta=-3\cdot 17^{2}$. As $\mathcal{E}_{2}$ is
ordinary by Lemma 3.10, then $(307)$ splits completely in $K$ (Remark 5.7). On
the other hand, $(17)$ is prime (inert) in $K$.

For the remainder of this section, we study under which conditions
$\mathcal{E}_{1}\cup\mathcal{E}_{2}$ may be empty.

######  Definition 5.10.

Let $\mathcal{O}$ be an order with fraction field $K$. We say that an ideal
$\mathfrak{a}\subset\mathcal{O}$ is _proper_ whenever $\mathcal{O}=\\{b\in K\
|\ b\mathfrak{a}=\mathfrak{a}\\}$. We recall that principal ideals are always
proper [10, p. 135]. A proper $\mathcal{O}$-ideal is called _primitive_ if it
is not of the form $d\mathfrak{a}$ for some proper ideal $\mathfrak{a}$ and
$d\in\mathbb{Z}_{>0}$. We will call an element $\lambda\in\mathcal{O}$
primitive if $(\lambda)$ is a primitive ideal.

######  Proposition 5.11.

Let $(q_{1},q_{2})$ be an odd Hasse pair with corresponding traces
$t_{i}=k_{i}p_{i}^{b_{i}}$, where $b_{i}\in\mathbb{N}$ and
$\gcd(k_{i},p_{i})=1$. Then one of the sets $\mathcal{E}_{i}$ is ordinary,
except possibly when $b_{i}\geq 1$, $a_{i}>2b_{i}$ and
$p_{i}^{2b_{i}}||\Delta$ for both $i\in\\{1,2\\}$.

###### Proof.

By Proposition 4.2 it is sufficient to show that if the above conditions are
not satisfied, then $\mathcal{E}_{1}\cup\mathcal{E}_{2}$ is non-empty. We show
the result in steps.

Step 1: If either one of the $\pi_{i}$’s is primitive, then $\mathcal{E}_{i}$
is non-empty:

(i): If $\gcd(t_{i},\Delta)=1$, then $\mathcal{E}_{i}$ is ordinary by Lemma
3.10.

(ii): If $\gcd(t_{i},\Delta)>1$, since $\pi_{i}$ is primitive then in
particular $p_{i}$ cannot divide the conductor. This implies that $p_{i}$ must
divide $D$ and hence ramifies. From Case(b-i) of Proposition 5.6, this can
only happen when $p_{i}=3$ and $|t_{i}|=3^{\frac{a_{i}+1}{2}}$, which implies
that $\mathcal{E}_{i}$ is supersingular.

Step 2: If $2b_{i}\geq a_{i}$, then $\mathcal{E}_{1}\cup\mathcal{E}_{2}$ is
non-empty:

We rewrite the norm equation

$t_{i}^{2}-4q_{i}=p_{i}^{a_{i}}(k_{i}^{2}p_{i}^{2b_{i}-a_{i}}-4)=\Delta<0\
\Rightarrow\ k_{i}^{2}p_{i}^{2b_{i}-a_{i}}<4.$

Then we must have $k_{i}=\pm 1$, and either

(i) $2b_{i}>a_{i}$, in which case we should have $p_{i}=3$ and
$\mathcal{E}_{i}$ is supersingular by case (d) of Theorem 2.1, or

(ii) $2b_{i}=a_{i}$, which implies that $2b_{j}>a_{j}$ and this is case (i)
right above.

Step 3: Given Steps 1 and 2, $\mathcal{E}_{1}\cup\mathcal{E}_{2}$ may be empty
only if neither $\pi_{i}$ is primitive and $2b_{i}<a_{i}$ for both
$i\in\\{1,2\\}$. Given the norm equation, this again implies that
$p_{i}^{2b_{i}}||\Delta$ for both $i\in\\{1,2\\}$. ∎

######  Corollary 5.12.

If $a_{i}\leq 2$ for some $i\in\\{1,2\\}$, then at least one of the sets
$\mathcal{E}_{i}$ is ordinary.

###### Proof.

If for some $i\in\\{1,2\\}$ we have $a_{i}\leq 2$, then we cannot have
$a_{i}>2b_{i}$ and $b_{i}\geq 1$, hence we are not in the exceptional case of
Proposition 5.11. ∎

A necessary condition for an odd Hasse pair to satisfy the exceptional
conditions of Proposition 5.11 is having positive integers $a_{i}>2b_{i}$ and
odd integer primes $p_{i}$ such that

$\begin{cases}p_{1}^{a_{1}}\equiv 1\bmod p_{2}^{b_{2}},\\\ p_{2}^{a_{2}}\equiv
1\bmod p_{1}^{b_{1}},\\\
\left|\sqrt{p_{1}^{a_{1}}}-\sqrt{p_{2}^{a_{2}}}\right|\leq 1.\\\ \end{cases}$

Even for $b_{i}=1$, we have found no evidence of such values for moderately
small prime powers ($p_{i}\leq 10^{5}$ and $a_{i}\leq 10^{3}$). Moreover,
large prime powers are expected to be asymptotically “very far apart” [26,
27], therefore finding large solutions to the above inequality seems hard.

##  6\. The isogeny graphs of ordinary Hasse pairs

###  6.1. The graph vertices: Sets of $j$-invariants

In this section, we consider the case where both sets $\mathcal{E}_{i}$ are
ordinary and we will refer to the pair $(q_{1},q_{2})$ as an _ordinary Hasse
pair_. In such cases, $\gcd(\Delta,q_{1}q_{2})=1$ and $\Delta$ is odd,
therefore the fundamental discriminant $D$ is squarefree.

By Lemma 4.4 there are only two non-odd ordinary Hasse pairs, up to
permutation, and it may be directly verified that their isogeny graphs (as
will be defined in Section 6.2) are isomorphic (see Examples 7.2 and 7.3).
Therefore, we can restrict to odd ordinary Hasse pairs and use our definitions
and results from Section 5.

We recall from Remark 5.5 that the order
$\mathbb{Z}[\pi_{1}]=\mathcal{O}_{\Delta}=\mathbb{Z}[\pi_{2}]$ is of
discriminant $\Delta=f^{2}D$. For any positive divisor $g$ of $f$, there
corresponds an order $\mathcal{O}_{g^{2}D}$, with discriminant $g^{2}D|\Delta$
and ideal class group $\textnormal{Cl}(\mathcal{O}_{g^{2}D})$ [10, Lemma 7.2].
The cardinality $h_{g^{2}D}=|\textnormal{Cl}(\mathcal{O}_{g^{2}D})|$ of the
ideal class group is known as the class number of $\mathcal{O}_{g^{2}D}$. We
denote by $H_{g^{2}D}(x)$ the Hilbert class polynomial of
$\mathcal{O}_{g^{2}D}$ and by $L_{g^{2}D}$ the splitting field of
$H_{g^{2}D}(x)$, also known as the ring class field of $\mathcal{O}_{g^{2}D}$.
Given any set of representatives $\\{\mathfrak{a}_{s}\\}_{1\leq s\leq
h_{g^{2}D}}$ for $\textnormal{Cl}(\mathcal{O}_{g^{2}D})$, the Hilbert class
polynomial $H_{g^{2}D}(x)$ is given by

$H_{g^{2}D}(x)=\prod_{1\leq s\leq
h_{g^{2}D}}\big{(}x-j(\mathfrak{a}_{s})\big{)}\in\mathbb{Z}[x].$

We also have a group isomorphism
$\textnormal{Cl}(\mathcal{O}_{g^{2}D})\simeq\textnormal{Gal}(L_{g^{2}D}/K)$,
which can be explicitly described as follows [19, Theorem 5, Chapt. 10, §3]:

$\mathfrak{b}\mapsto\sigma_{\mathfrak{b}},\quad\textnormal{where}\quad\sigma_{\mathfrak{b}}j(\mathfrak{a})=j(\mathfrak{b}^{-1}\mathfrak{a}).$

In particular, the ideal class group $\textnormal{Cl}(\mathcal{O}_{g^{2}D})$
acts on the set $\\{j(\mathfrak{a}_{s})\\}_{1\leq s\leq h_{g^{2}D}}$ freely
and transitively, and therefore $L_{g^{2}D}=K\big{(}j(\mathfrak{a})\big{)}$
for any $\mathfrak{a}\in\textnormal{Cl}(\mathcal{O}_{g^{2}D})$.

######  Lemma 6.1.

Let $(q_{1},q_{2})$ be an ordinary Hasse pair. The ideals
$(\pi_{i})\subset\mathcal{O}_{K}$ are proper, primitive, and
$(\pi_{i})=\mathfrak{p}_{i}^{a_{i}}$, where the $\mathfrak{p}_{i}$’s are prime
ideals such that $\mathfrak{p}_{i}\overline{\mathfrak{p}}_{i}=(p_{i})$ and
$\mathfrak{p}_{i}\neq\overline{\mathfrak{p}}_{i}$.

###### Proof.

Since we are in the ordinary case we must have that $\gcd(t_{i},\Delta)=1$,
which implies that $p_{i}\nmid t_{i}$ and $p_{i}\nmid f$ for both
$i\in\\{1,2\\}$. As a consequence [35, Lemma, §4, p. 537] both primes $p_{i}$
must split in $K$ as $p_{i}=\mathfrak{p}_{i}\overline{\mathfrak{p}}_{i}$,
$\mathfrak{p}_{i}\neq\overline{\mathfrak{p}}_{i}$. Let us consider the norm
equation

$(q_{i})=(\pi_{i})(\overline{\pi}_{i})=\mathfrak{p}_{i}^{a_{i}}\overline{\mathfrak{p}}_{i}^{a_{i}}.$

Since the norms of $\mathfrak{p}_{i}^{a_{i}}$ and $(\pi_{i})$ are prime to the
conductor, these ideals are therefore primitive and they belong to the group
of ideals with unique factorization in the order
$\mathcal{O}_{\Delta}\subseteq\mathcal{O}_{K}$. We conclude that
$(\pi_{i})=\mathfrak{p}_{i}^{m_{i}}\overline{\mathfrak{p}}_{i}^{n_{i}}$, for
some $m_{i},n_{i}\in\mathbb{N}$ such that $m_{i}+n_{i}=a_{i}$. Assume by way
of contradiction that both $m_{i},n_{i}$ are not zero. Then $p_{i}|\pi_{i}$
and therefore $p_{i}|t_{i}=\pi_{i}+\overline{\pi}_{i}$, contradiction.
Therefore we have that either $m_{i}=0$ or $n_{i}=0$, so up to conjugation we
have $(\pi_{i})=\mathfrak{p}_{i}^{a_{i}}\ \text{in}\
\mathcal{O}_{\Delta}\subseteq\mathcal{O}_{K}$. ∎

######  Lemma 6.2.

Let $(q_{1},q_{2})$ be an ordinary Hasse pair. For every $g\in\mathbb{Z}_{>0}$
with $g|f$, $H_{g^{2}D}$ splits completely with distinct roots in both
$\mathbb{F}_{q_{i}}[x]$. In particular, $H_{\Delta}$ splits completely with
distinct roots in both $\mathbb{F}_{q_{i}}[x]$.

###### Proof.

Let us fix primes $\mathfrak{B}_{i}$ of $\mathcal{O}_{L}$ above
$\mathfrak{p}_{i}$. Since our primes $p_{i}$ neither ramify nor divide the
conductor, then by [24, Proposition I.8.3], the Hilbert class polynomial
$H_{\Delta}$ splits completely with distinct roots in both finite fields
$\mathbb{F}_{p_{i}^{\iota_{i}}}$, where $\iota_{i}$ is called the inertia
degree and it is the degree of the residue field extension

$\iota_{i}=[\mathcal{O}_{L_{\Delta}}/\mathfrak{B}_{i}:\mathcal{O}_{\Delta}/\mathfrak{p}_{i}].$
(2)

Since the inertia degree is the smallest power to which the base ideal,
$\mathfrak{p}_{i}$ in this case, becomes principal in
$\textnormal{Cl}(\mathcal{O}_{\Delta})$, and since
$\mathfrak{p}_{i}^{a_{i}}=(\pi_{i})$ by Lemma 6.1, then $\iota_{i}|a_{i}$.
From the fact that $h_{g^{2}D}|h_{\Delta}$, we have that the primes
$\mathfrak{p}_{i}\mathcal{O}_{g^{2}D}$ must also become principal when raised
to $a_{i}$, for both $i\in\\{1,2\\}$. Hence, by the same [24, Proposition
I.8.3], $H_{g^{2}D}$ must also split completely with distinct roots over both
$\mathbb{F}_{q_{i}}[x]$. ∎

For each $g|f$, we denote by $J_{g^{2}D}$ the set of complex roots of the
corresponding Hilbert Class Polynomial $H_{g^{2}D}$. We note that two
different $H_{g^{2}D}$ cannot have common roots, and we denote by $J$ the
(disjoint) union of all these sets. We similarly denote by
$J_{{(g^{2}D)}_{i}}$ and $J_{i}$ the sets of roots of the same polynomials in
$\mathbb{F}_{q_{i}}$.

######  Remark 6.3.

Since $H_{g^{2}D}$ splits completely by Lemma 6.2, the cardinality of each
$J_{g^{2}D}$ is $h_{g^{2}D}$, i.e.

$|J_{g^{2}D}|=|J_{{(g^{2}D)}_{1}}|=|J_{{(g^{2}D)}_{2}}|.$

Therefore, we also have

$|J|=|J_{1}|=|J_{2}|.$

We also remark that, given Lemma 6.2, the sets $J_{{(g^{2}D)}_{i}}$ are
already defined in
$\mathbb{F}_{p_{i}^{\iota_{i}}}\hookrightarrow\mathbb{F}_{q_{i}}$.

Since we are in the ordinary case, by Remark 3.9 each set $\mathcal{E}_{i}$
can be identified with the set of $j$-invariants of their elliptic curves. We
note that this cannot be done in the supersingular case (Example 7.1). Remark
6.3 now implies that we can identify the sets $\mathcal{E}_{i}$ with $J_{i}$.

######  Lemma 6.4.

Let $j^{(0)}\in L$ be a root of $H_{\Delta}$ and $r$ be a fixed square root of
$\Delta$. Let also $D_{0}=\textnormal{Disc}(H_{\Delta})\in\mathbb{Z}$. For
every $j\in J$, there exists $h_{j}(x,y)\in\mathbb{Z}[x,y]$ such that

$j=\frac{h_{j}(j^{(0)},r)}{2\,D_{0}}.$

Moreover, if $p$ is an odd prime such that $H_{\Delta}$ does not have repeated
roots over $\bar{\mathbb{F}}_{p}$, then $\gcd(2\,D_{0},p)=1$.

###### Proof.

For every order
$\mathcal{O}_{\Delta}\subseteq\mathcal{O}\subseteq\mathcal{O}_{K}$ and every
$j\in J$, we have $j\in L_{g^{2}D}\subseteq L=K(j^{(0)})$ [19, Theorem 10.6]
and $H_{\mathcal{O}}(j)=0$. Since $H_{\mathcal{O}}$ is a monic integral
polynomial, then $j\in\mathcal{O}_{L}$. By classical properties of simple
separable extensions [24, Lemma I.2.9], we have

$\mathcal{O}_{L}\subseteq
D_{0}^{-1}\mathcal{O}_{K}[j^{(0)}]\subseteq(2D_{0})^{-1}\mathbb{Z}[j^{(0)},r].$

Thus, every $j\in\mathcal{O}_{L}$ can be written as
$\frac{h_{j}(j^{(0)},r)}{2D_{0}}$ for some $h_{j}(x)\in\mathbb{Z}[x,y]$.
Moreover, since $H_{\Delta}$ is the minimal polynomial of $j^{(0)}\in L$ over
$\mathbb{Q}$ [29, Theorem II.4.3], we have

$D_{0}=\pm\textnormal{Disc}(H_{\Delta})=\pm\textnormal{Res}_{x}\big{(}H_{\Delta}(x),H_{\Delta}^{\prime}(x)\big{)}\in\mathbb{Z}.$

Then $H_{\Delta}$ has no repeated roots in $\bar{\mathbb{F}}_{p}$ precisely
when
$D_{0}=\pm\textnormal{Res}_{x}\big{(}H_{\Delta}(x),H_{\Delta}^{\prime}(x)\big{)}\in\bar{\mathbb{F}}_{p}^{*}$,
i.e. when $D_{0}$ is coprime to $p$. ∎

######  Remark 6.5.

We fix once and for all a square root $r$ of $\Delta\in\mathbb{C}$, and an
element $j^{(0)}\in J_{\Delta}$, which generates $L_{\Delta}$ over $K$. Now,
given Remark 6.3 and Lemma 6.4, any fixed choice of a square root $r_{i}$ of
$\Delta\in\mathbb{F}_{p_{i}^{\iota_{i}}}$ and $j^{(0)}_{i}\in
J_{(\Delta)_{i}}$, induces an explicit bijection

$\Pi_{i}:J\to
J_{i}\subseteq\mathbb{F}_{p_{i}^{\iota_{i}}},\quad\frac{h_{j}(j^{(0)},r)}{2D_{0}}\mapsto\frac{h_{j}(j^{(0)}_{i},r_{i})}{2D_{0}}.$

By embedding $\mathbb{F}_{p_{i}^{\iota_{i}}}$ into $\mathbb{F}_{q_{i}}$, this
extends to a bijection $\Pi_{i}:J\to J_{i}\subseteq\mathbb{F}_{q_{i}}$, which
we denote in the same way. We notice that the above choices of $r_{i}$ and
$j^{(0)}_{i}$ are associated with a fixed choice of primes
$\mathfrak{P}_{i}\subset\mathcal{O}_{L}$ and
$\mathfrak{p}_{i}\subset\mathcal{O}_{K}$ such that
$\mathfrak{P}_{i}|\mathfrak{p}_{i}|p_{i}$, for both $i\in\\{1,2\\}$.

###  6.2. The Isogeny Graphs

######  Definition 6.6.

Let $\textnormal{B}\subset\mathbb{N}$ be a finite set of integer primes, and
$\mathcal{E}$ be a set of elliptic curves defined over a finite field $\Bbbk$,
up to $\Bbbk$-isomorphism. We define the _B -isogeny graph_ of $\mathcal{E}$,
denoted by $G_{\textnormal{B}}(\mathcal{E})$, as the directed colored
multigraph, whose vertices are the elements in $\mathcal{E}$, and the edges
are cyclic $\Bbbk$-isogenies between them. The color of any edge corresponds
to the degree of the isogeny, which is some prime in $B$.

######  Remark 6.7.

When drawing isogeny graphs we use the convention that an undirected edge
corresponds to one edge in each direction. We recall that $j=1728$ can appear
in an ordinary $G_{\textnormal{B}}(\mathcal{E})$ only in even characteristic
(so it equals $j=0$) by Remark 5.2. Since every isogeny has a dual isogeny
[30, Section III.6], and $\textnormal{Aut}(E)=\\{\pm\textnormal{id}\\}$ for
every elliptic curve $E$ with $j(E)\neq 0,1728$ [30, Section III.10], our
graphs may be thought of as undirected, with the only possible exception of
isogenies from $j=0$.

######  Lemma 6.8.

Let $(q_{1},q_{2})$ be an ordinary Hasse pair. For both $i\in\\{1,2\\}$, the
graphs $G_{\\{p_{i}\\}}(\mathcal{E}_{1})$ and
$G_{\\{p_{i}\\}}(\mathcal{E}_{2})$ are isomorphic and consist of
$h_{\Delta}/\iota_{i}$ cycles of length $\iota_{i}$ (as defined in (2)).

###### Proof.

Since the relation is symmetric, we can assume without loss of generality that
$i=2$. We can also restrict to vertices contained in $J_{(\Delta)_{1}}$ and
$J_{(\Delta)_{2}}$, because all the $p_{2}$-isogenies are horizontal since
$(q_{1},q_{2})$ is ordinary. We compute the eigenvalues of the $\pi_{i}$’s by
examining the splitting of their minimal polynomials $f_{i}(x)\bmod p_{2}$.
Given Remark 5.4, a simple computation shows that

$f_{1}(x)=f_{2}(-x+1).$

We compute the eigenvalues $\\{\mu_{i},\nu_{i}\\}$ of each $\pi_{i}$ as the
roots of

$\displaystyle f_{2}(x)$ $\displaystyle\equiv x(x-t_{2})\bmod p_{2},$
$\displaystyle f_{1}(x)=f_{2}(-x+1)$
$\displaystyle\equiv(x-1)\big{(}x-(1-t_{2})\big{)}\bmod p_{2}.$

For ordinary elliptic curves in characteristic $p_{2}$, there are only two
isogenies of degree $p_{2}$: the Frobenius isogeny, which is inseparable, and
its dual, called the _Verschiebung_ , which is separable. The Frobenius
isogeny creates cycles of length equal to the degree of the minimal extension
field where the elliptic curve is defined, which in this case is $\iota_{2}$
as in (2). Therefore, the number of cycles in this case is
$h_{\Delta}/\iota_{2}$.

We now look at the eigenvalues $\lambda_{1}=1$ and $\mu_{1}=1-t_{2}$ of
$f_{1}$. We see that $\mu_{1}\not\equiv 0\bmod p_{2}$ since otherwise, from
the equation $q_{1}=q_{2}+1-t_{2}$, we would have that $p_{2}|q_{1}$, which is
not possible for odd Hasse pairs. Furthermore,
$\lambda_{1}\not\equiv\mu_{1}\bmod p_{2}$, as $t_{2}\equiv 0\bmod p_{2}$ would
lead to supersingular curves. Since we have two distinct eigenvalues, this
implies that $p_{2}$ is an Elkies prime and we have $h_{\Delta}/\iota_{2}$
cycles of degree-$p_{2}$ isogenies in this case as well ([32, Theorem 7]).
Thus, $G_{\\{p_{2}\\}}(\mathcal{E}_{1})$ and
$G_{\\{p_{2}\\}}(\mathcal{E}_{2})$ have the same structure. ∎

######  Theorem 6.9.

Let $(q_{1},q_{2})$ be an ordinary Hasse pair and $B\subset\mathbb{N}$ be a
finite set of primes. Then $G_{\textnormal{B}}(\mathcal{E}_{1})$ is isomorphic
to $G_{\textnormal{B}}(\mathcal{E}_{2})$.

###### Proof.

Let $G_{\textnormal{B}}(\Delta)$ be the directed colored multigraph (in
characteristic zero) whose vertices are the elements of $J$ and whose edges
$\phi:j_{1}\to j_{2}$ represent isogenies of prime color $\deg\phi=\ell$
between curves with $j$-invariants $j_{1}$ and $j_{2}$, for any $\ell\in B$.

By adapting [29, Proposition II.4.4] to the context of Remark 6.5, for both
$i\in\\{1,2\\}$ we have an injection

$\textnormal{Hom}(j_{1},j_{2})\to\textnormal{Hom}\big{(}\Pi_{i}(j_{1}),\Pi_{i}(j_{2})\big{)},$

which preserves the degree of the isogenies. Therefore, there is an isomorphic
copy of $G_{\textnormal{B}}(\Delta)$ over both the
$\mathbb{F}_{p_{i}^{\iota_{i}}}$’s. Since the isogenies, as well as the
$j$-invariants involved, are defined over $\mathbb{F}_{p_{i}^{\iota_{i}}}$,
they are also defined over $\mathbb{F}_{q_{i}}$, therefore the maps $\Pi_{i}$
are isomorphic graph embeddings of $G_{\textnormal{B}}(\Delta)$ into the
$G_{\textnormal{B}}(\mathcal{E}_{i})$’s.

Since all the considered curves are ordinary, the structure of the isogeny
graphs $G_{\textnormal{B}}(\Delta)$, $G_{\textnormal{B}}(\mathcal{E}_{1})$,
and $G_{\textnormal{B}}(\mathcal{E}_{2})$ only depends on $\Delta$. Therefore,
the number and type of isogenies (horizontal or vertical) from curves with
$j$-invariant different from $0$ are the same in both characteristics (by [32,
Theorem 7] and [17, Proposition 23]) for isogenies of degree
$l\not\in\\{p_{1},p_{2}\\}$. By Lemma 6.8, the same holds for isogenies of
degree $p_{1}$ and $p_{2}$.

Finally, either none or both sets $\mathcal{E}_{i}$ contain a curve
$E^{0}_{i}$ with $j(E^{0}_{i})=0$, as this occurs if and only if the
squarefree part of $\Delta$ is $D=-3$. If such curves exist, then we have

$\textnormal{End}_{\mathbb{F}_{p_{1}}}(E^{0}_{1})\simeq\textnormal{End}_{\mathbb{F}_{p_{2}}}(E^{0}_{2})\simeq\mathbb{Z}\left[\frac{1+\sqrt{-3}}{2}\right].$

Since a $j$-invariant zero curve over $\mathbb{F}_{p_{i}^{a_{i}}}$ is ordinary
if and only if $p_{i}\equiv 1\bmod 3$, then $\sqrt{-3}$ is defined over both
the $\mathbb{F}_{p_{i}}$’s (and consequently over the $\mathbb{F}_{q_{i}}$’s).
Thus, in both the $G_{\textnormal{B}}(\mathcal{E}_{i})$’s, if we have any
descending $l$-isogenies $0\to j\neq 0$, then there are precisely three
distinct $l$-isogenies from $0$ to $j$. Moreover, in this case, both the
isogeny graphs have exactly $(\frac{\Delta}{l})+1$ isogenies of degree $l$
from $0$ to itself. ∎

##  7\. Examples of isogeny graphs

######  Example 7.1.

The discriminant of the Hasse pair $(q_{1},q_{2})=(4,7)$ is $\Delta=-12$.
Given
$\mathbb{F}_{4}=\mathbb{F}_{2}(\gamma)\simeq\mathbb{F}_{2}[x]/(x^{2}+x+1)$,
one can directly verify that $\mathcal{E}_{1}$ contains only the following two
elliptic curves

$0_{A}\ :\ y^{2}+\gamma y=x^{3}+1,\quad\quad 0_{B}\ :\
y^{2}+\gamma^{2}y=x^{3}+\gamma^{2},$ (3)

which are both supersingular and their $j$-invariant is $0\in\mathbb{F}_{4}$.
On the other hand, $\mathcal{E}_{2}$ is ordinary and contains the curves of
$j$-invariant $0$ and $2\in\mathbb{F}_{7}$. The $2$-Frobenius map $\pi_{2}$
connects the curves $0_{A}$ and $0_{B}$ in
$\textnormal{G}_{\\{2\\}}(\mathcal{E}_{1})$, while there are three descending
and one ascending $2$-isogenies in
$\textnormal{G}_{\\{2\\}}(\mathcal{E}_{2})$. Thus, the isogeny graphs are not
isomorphic as shown in Figure 1.

$0_{A}$$0_{B}$$\pi_{2}$

$0$$2$

Figure 1.
$\\{{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}2}\\}$-isogeny
graphs for the Hasse pair $(4,7)$. The curves $0_{A}$ and $0_{B}$ are defined
as in (3).

######  Example 7.2.

The pair $(q_{1},q_{2})=(2,4)$ is an ordinary Hasse pair with associated
discriminant $\Delta=-7$. Given
$\mathbb{F}_{4}=\mathbb{F}_{2}(\gamma)\simeq\mathbb{F}_{2}[x]/(x^{2}+x+1)$,
one can directly verify that $\mathcal{E}_{1}$ only contains the curve $E_{1}$
defined by $y^{2}+xy=x^{3}+1$ over $\mathbb{F}_{2}$, while $\mathcal{E}_{2}$
only contains the curve $E_{2}$ defined by $y^{2}+xy=x^{3}+\gamma^{2}x^{2}+1$
over $\mathbb{F}_{4}$, both of $j$-invariant $1$. If $\pi_{2}$ is the
$2$-Frobenius map, one can also check that

$\textnormal{End}_{\mathbb{F}_{2}}(E_{1})=\mathbb{Z}[\pi_{2}]=\textnormal{End}_{\mathbb{F}_{4}}(E_{2}),$

so the isogeny graphs are isomorphic and given in Figure 2.

$1$$\pi_{2}$

$1$$\pi_{2}$

Figure 2. B-isogeny graphs $G_{\textnormal{B}}(\mathcal{E}_{1})$ (on the left)
and of $G_{\textnormal{B}}(\mathcal{E}_{2})$ (on the right) for
$(q_{1},q_{2})\in\\{((2,4)),((4,8))\\}$ for any
$2\in\textnormal{B}\subseteq\mathbb{N}$.

######  Example 7.3.

The pair $(q_{1},q_{2})=(4,8)$ is the second of the two ordinary non-odd Hasse
pair of Lemma 4.4, the other one being Example 7.2. The associated
discriminant is again $\Delta=-7$. One can directly verify that both sets
$\mathcal{E}_{i}$ contain only the curve defined by the model
$y^{2}+xy=x^{3}+1$, of $j$-invariant $1$. Notice that in $\mathcal{E}_{1}$ we
have the (unique) twist of $E_{2}$ from Example 7.2. Therefore the
endomorphism ring for both curves is $\mathbb{Z}[\pi_{2}]$, and so the isogeny
graphs are isomorphic and are shown again in Figure 2.

######  Example 7.4.

Since $\sqrt{587}=24.228\dots$, then $(q_{1},q_{2})=(5^{4},587)$ is an odd
Hasse pair, which is ordinary since its associated discriminant
$\Delta=-979=-11\cdot 89$ is coprime with both the $q_{i}$’s (Lemma 3.10).
Thus, the isogeny graphs of $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ are the
same by Theorem 6.9. This correspondence is portrayed for isogenies of prime
degree up to $11$ by Figure 3.

$\gamma^{582}$$\gamma^{354}$$\gamma^{366}$$\gamma^{570}$$\gamma^{198}$$\gamma^{114}$$\gamma^{414}$$\gamma^{522}$

$415$$203$$22$$427$$477$$576$$279$$354$

Figure 3. $\\{$2,3,5,7,11$\\}$-isogeny graphs for the Hasse pair
$(5^{4},587)$. The vertices are $j$-invariants over
$\mathbb{F}_{5^{4}}=\mathbb{F}_{5}[\gamma]\simeq\mathbb{F}_{5}[x]/(x^{4}+4x^{2}+4x+2)$
(left) and over $\mathbb{F}_{587}$ (right).

######  Example 7.5.

Since $\sqrt{1069}-\sqrt{1021}=0.742\dots$, then $(q_{1},q_{2})=(1021,1069)$
is an odd Hasse pair. Its associated discriminant is $\Delta=-1875=-3\cdot
5^{4}$, so both sets $\mathcal{E}_{i}$ are ordinary by Lemma 3.10, and their
isogeny graphs are the same by Theorem 6.9. This correspondence is portrayed
for isogenies of certain degrees by Figures 4 and 5.

$0$$89$$277$$33$$109$$462$$730$$894$$931$$782$$912$$143$$439$

$0$$643$$855$$1025$$883$$364$$266$$79$$212$$537$$195$$707$$352$

Figure 4. {3,5}-isogeny graph for the ordinary Hasse pair $(1021,1069)$. The
vertices are $j$-invariants over $\mathbb{F}_{1021}$ (left) and
$\mathbb{F}_{1069}$ (right).

$0$$89$$277$$143$$462$$782$$894$$439$$109$$912$$730$$931$$33$

$0$$643$$855$$537$$364$$707$$79$$352$$266$$195$$883$$212$$1025$

Figure 5. {7,19}-isogeny graph for the ordinary Hasse pair $(1021,1069)$. The
vertices are $j$-invariants over $\mathbb{F}_{1021}$ (left) and
$\mathbb{F}_{1069}$ (right).

######  Example 7.6.

Since $\sqrt{22501}=150.003\dots$, then $(q_{1},q_{2})=(151^{2},22501)$ is an
odd Hasse pair. Since $\Delta=-507=-3^{2}\cdot 67$, all the curves are
ordinary and the isogeny graphs are isomorphic by Theorem 6.9. Those graphs
are shown for isogenies of certain degrees by Figure 6. We observe that all
the $j$-invariants of $\mathcal{E}_{1}$ are already defined over
$\mathbb{F}_{151}$, since $\iota_{1}=1$ (as defined in (2)). In fact, one can
verify that the resulting isogeny graph equals the isogeny graph of (isogeny
classes of) anomalous curves over $\mathbb{F}_{151}$.

$125$$40$$75$$99$$96$

$12341$$337$$620$$4861$$6330$

Figure 6. {3,17,19}-isogeny graph for the ordinary Hasse pair
$(151^{2},22501)$. The vertices are $j$-invariants over
$\mathbb{F}_{151}\hookrightarrow\mathbb{F}_{151^{2}}$ (left) and
$\mathbb{F}_{22501}$ (right).

##  8\. Conclusions

In the present paper, for a given Hasse pair $(q_{1},q_{2})$ we investigated
the properties of the sets $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$.

When the pair is odd, the results we obtained are summarized in Table 1. In
this case, we proved that $\mathcal{E}_{1}\cup\mathcal{E}_{2}$ always contains
an ordinary curve when it is non-empty, but we could not prove nor disprove
whether such a union could be empty. This remains an open problem for us
(Problem 1.1), and we believe that its difficulty lies in the fact that the
prime powers involved should be very close, as well as meeting further modular
conditions.

$(q_{1},q_{2})$ | $\mathcal{E}_{1}$
---|---
odd Hasse pair |  ordinary |  supersingular |  empty
| ordinary |  Same isogeny graphs |  Occurs with $j=0$ |  May occur
|  |  Theorem 6.9 |  Proposition 4.3 |  E.g. $(7^{2},43)$
$\mathcal{E}_{2}$ | supersingular |  | Never occurs
|  |  Symmetric | Proposition 4.2
| empty | see $(q_{2},q_{1})$ . |  Open,
|  |  |  Problem 1.1
Table 1. Possible configuration arising from odd Hasse pairs.

When the considered Hasse pair involves even entries, different cases may
occur, as portrayed in Table 2. In this setting, it is possible to find only
supersingular curves in $\mathcal{E}_{1}\cup\mathcal{E}_{2}$. These cases
arise precisely when we have Fermat and Mersenne primes, therefore counting
such cases is equivalent to the well-known open problem of deciding the
finiteness of these families of primes (Remark 4.7). Furthermore, the set
$\mathcal{E}_{i}$ defined in even characteristic may be empty only if the
other one (defined in odd characteristic) is also empty, but we have found
only one instance of such a case. Again, the empty cases look special, and
establishing a complete classification of them seems challenging.

$(2^{a_{1}},q_{2})$ | $\mathcal{E}_{1}$
---|---
Hasse pair |  ordinary |  supersingular |  empty
| ordinary |  $q_{2}$ even, classified |  May occur |  May occur
|  |  Lemma 4.4 |  Example 7.1 |  E.g. $(2^{4},11)$
$\mathcal{E}_{2}$ | supersingular |  |  Classified |  May occur
|  |  Never occurs |  Theorem 4.6 |  E.g. $(2^{3},7)$
| empty |  Lemma 4.4 |  Never occurs |  May occur
|  |  |  Theorem 4.6 |  E.g. $(2^{8},3^{5})$
Table 2. Possible configuration arising from non-odd Hasse pairs.

Furthermore, in the last section we observed that, regardless of the
characteristic, when $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ are both
ordinary, we have a perfect correspondence between their isogeny graphs. This
relation is effective only on paper at the moment, as we lack an efficient way
of passing from one isogeny graph to the other. Performing such correspondence
efficiently, i.e. without passing through the construction of huge Hilbert
class polynomials in characteristic zero, is regarded as an ambitious task,
which could lead to interesting cryptographic applications.

Finally, similarly to how aliquot cycles extend the idea of amicable primes
[31], one may aim at extending the ideas of the current paper by considering
the tuples $(p_{1}^{a_{1}},\dots,p_{r}^{a_{r}})$ of prime powers and elliptic
curves $E_{1},\dots,E_{r}$, such that for every $1\leq i\leq r$, the curve
$E_{i}$ is defined over $\mathbb{F}_{q_{i}}$ and

$\forall\,1\leq i\leq r-1\ :\ |E_{i}|=q_{i+1},\quad|E_{r}|=q_{1}.$

When ordinary, all these curves should have the same isogeny graphs.

## Acknowledgements

This work was partially supported by the European Union’s H2020 Programme
under grant agreement number ERC-669891. D.T. was also supported by the
Research Foundation - Flanders (FWO mandate: 12ZZC23N). E.A. would like to
thank the CISPA Helmholtz Center for Information Security, and the Max Planck
Institute for Mathematics in Bonn, for their hospitality and support during
the writing of this paper. The authors are grateful to Pieter Moree for
helpful discussions, insightful comments, and careful proof-reading of the
paper.

##  Appendix A Hasse pairs and Andrica’s conjecture
by Pieter Moree and Efthymios Sofos

Recall that a pair of prime powers $(q_{1},q_{2})$ is called a _Hasse pair_ if

$\mid\sqrt{q_{1}}-\sqrt{q_{2}}\mid\leq 1.$ (4)

If both $q_{1}$ and $q_{2}$ are odd, then the pair is called an _odd Hasse
pair_. Using Lemma 4.5 it is easy to see that if
$\sqrt{q_{1}}-\sqrt{q_{2}}=1$, then necessarily $q_{1}=81$ and $q_{2}=64$,
thus replacing $\leq 1$ by $<1$ is almost equivalent.

It is natural to ask if there are many Hasse pairs. In this direction we
contribute the following result.

######  Theorem A.1.

Fix any $\epsilon>0$. There exists a constant $c(\epsilon)$ such that for
every prime $p<x$ and real number $x\geq 2$, with at most
$c(\epsilon)\,x^{3/5+\epsilon}$ exceptions, there are at least
$\frac{1}{2}\sqrt{p}\,(\log p)^{-1}$ Hasse pairs $(p,\ell)$ with $\ell$ a
prime.

We will apply some ideas from analytic number theory to this question. Since
the number of primes up to $x$ grows asymptotically as $x/\log x$ and the
number of prime powers $p^{m}$ with $m\geq 2$ only as $\sqrt{x}$, which is
$\leq c(\epsilon)\,x^{3/5+\epsilon}$ for every $x$ sufficiently large, we see
that Theorem A.1 implies the following corollary.

######  Corollary A.2.

Theorem A.1 also holds true if instead of primes we consider prime powers.

Thus typically a large prime (power) occurs as member of a _large number_ of
Hasse pairs. However, we cannot exclude the existence of a prime power that
_never_ occurs as a member of a Hasse pair.

######  Conjecture 1.

Every prime power is member of some Hasse pair.
Every odd prime power is member of some odd Hasse pair.

In Section A.2 we show that this conjecture is intimately connected with
Andrica’s conjecture. Research on that conjecture then shows that Conjecture 1
is certainly true for all prime powers $<10^{19}$. Let
$p_{1}=2,p_{2}=3,\ldots$ be the sequence of consecutive primes.

######  Proposition A.3.

If Andrica’s conjecture that $(p_{j},p_{j+1})$ is always a Hasse pair is true,
then so is Conjecture 1.

###### Proof.

If $q$ is a prime power, we let $p_{j}$ be the largest prime $\leq q$. Then
$(q,p_{j+1})$ is a Hasse pair by Andrica’s conjecture. If $q$ is odd, then
$(q,p_{j+1})$ is an odd Hasse pair. ∎

###  A.1. Proof of Theorem A.1

Theorem A.1 is in essence a corollary of the following deep result due to
Heath-Brown [13].

######  Theorem A.4 (Heath-Brown [13]).

For any fixed $\epsilon>0$ the measure of the set of $y\in[0,x]$ such that

$\max_{0\leq
h\leq\sqrt{y}}\left|\pi(y+h)-\pi(y)-\int_{y}^{y+h}\frac{\mathrm{d}t}{\log
t}\right|\geq\frac{\sqrt{y}}{(\log y)(\log\log y)}$

is $O_{\epsilon}(x^{3/5+\epsilon})$.

Proof of Theorem A.1: Let $B_{x}$ be the set of primes $p\in[2,x]$ such that
the interval $(p,p+\sqrt{p})$ contains $\leq\sqrt{p}/(2\log p)$ primes. Our
plan is to show that for any $p\in B_{x}\cap[2,x-1]$ the interval $(p,p+1)$
contributes towards the measure in Theorem A.4, from which we can directly
deduce that the number of elements in $B_{x}$ is
$c(\epsilon)\,x^{3/5+\epsilon}$.

For any $p\in B_{x}$ and $y\in(p,p+1)$ we have that the number of primes in
the interval $(y,y+\sqrt{p})$ is at most 2 plus the number of primes in the
interval $(p,p+\sqrt{p})$, which by assumption is $\leq 2+\sqrt{p}/(2\log p)$.
Now for all sufficiently large $p$ by trivial calculus this is
$\leq\sqrt{p}/(\log 2p)-\sqrt{p+1}/(\log{(p+1)\log\log(p+1)})$ and by the
monotonicity of the log function this is

$\leq\int_{y}^{y+\sqrt{p}}\frac{\mathrm{d}t}{\log
t}-\frac{\sqrt{p+1}}{\log(p+1)\log\log(p+1)},$

but since $y<p+1$, this is

$\leq\int_{y}^{y+\sqrt{p}}\frac{\mathrm{d}t}{\log t}-\frac{\sqrt{y}}{\log
y\log\log y}.$

Now taking $h=\sqrt{p}$ we note that $h\leq\sqrt{y}$ and hence we have shown
that if $p\in B_{x}$, then every $y$ in the interval $(p,p+1)$ violates the
inequality in Theorem A.4. $\square$

###  A.2. Andrica’s conjecture

Let $d_{n}:=p_{n+1}-p_{n}$ be the $n$th prime gap. Over the centuries many
conjectures involving $d_{n}$ have been made. Here we are interested in a
conjecture made in 1986 by Dorin Andrica [1].

######  Conjecture 2 (Andrica [1]).

The inequality

$\sqrt{p_{n+1}}-\sqrt{p_{n}}<1$ (5)

holds for all $n$.

A lot of numerical work on large gaps has been done. This can be used to infer
that Andrica’s conjecture holds for $p_{n}\leq 2\cdot 2^{63}\approx 1.8\cdot
10^{19}$; see Visser [33].

An equivalent formulation of Andrica’s conjecture is that

$d_{n}<2\sqrt{p_{n}}+1$ (6)

holds for all $n$. It seems to be far out of reach, as under RH the best
result is due to Cramér [11] who showed in already 1920 that
$d_{n}=O(\sqrt{p_{n}}\log p_{n})$. More explicitly, Carneiro et al. [8] showed
under RH that $d_{n}\leq\frac{22}{25}\sqrt{p_{n}}\log p_{n}$ for every
$p_{n}>3$. Unconditionally Baker et al. [3] showed that $d_{n}<p_{n}^{0.525}$
for all $n$ sufficiently large.

Heath-Brown used Theorem A.4 to obtain the following result on large gaps
between consecutive primes, which is a culmination of an enormous amount of
research done over many years.

######  Theorem A.5 (Heath-Brown [13]).

We have

$\sum_{\begin{subarray}{c}p_{n}\leq x\\\
p_{n+1}-p_{n}\geq\sqrt{p_{n}}\end{subarray}}(p_{n+1}-p_{n})\ll_{\epsilon}x^{3/5+\epsilon}.$

For a table of earlier (larger) exponents than $3/5$ achieved and their
authors, see Moree [23].

The authors (with Kosyak and Zhang) [18] came across the quantity on the left
hand side in Theorem A.5 as essentially being the number of failures up to $x$
for a method of construction they have for producing cyclotomic polynomials
$\Phi_{n}(x)$ having maximum coefficient $h$, with $h\leq x$. If a slightly
stronger variant of Andrica’s conjecture holds true, then they showed that
_every_ natural number occurs as maximum coefficient of some cyclotomic
polynomial. For a more leisurely account, see Moree [23].

###  A.3. Andrica’s conjecture for denser sequences

In our context a slightly weaker version of Andrica’s conjecture comes up,
namely:

######  Conjecture 3 (Andrica for prime powers).

Let $q_{1},q_{2},\ldots$ be the consecutive prime powers. The inequality

$\sqrt{q_{n+1}}-\sqrt{q_{n}}<1$ (7)

holds for all $n$.

Since the number of primes up to $x$ grows asymptotically as $x/\log x$ and
the number of prime powers $p^{m}$ with $m\geq 2$ as $\sqrt{x}$, this modified
version is, unfortunately, not that much weaker. One could hope that if one
replaces the sequence of prime numbers by a substantially ‘fatter’ sequence,
one might be able to prove the analogue of Andrica’s conjecture. Finally, we
present an example showing that this hope is not unjustified.

A positive integer $n$ is said to be _practical_ if every positive integer
$\leq n$ is a subset-sum of the positive divisors of $n$. Weingartner [36]
showed that there is a constant $c=1.33607\ldots$ such that the number of
practical numbers $\leq x$ grows as $cx/\log x$. The analogue of Andrica’s
conjecture for the practical numbers is known to be true, see Wu [37].

Max-Planck-Institut für Mathematik,
Vivatsgasse 7, D-53111 Bonn, Germany.
E-mail<EMAIL_ADDRESS>

School of Mathematics and Statistics,
University of Glasgow,
University Place, Glasgow, G12 8SQ, United Kingdom.
E-mail<EMAIL_ADDRESS>

## References

  * [1] D. Andrica, Note on a conjecture in prime number theory, _Studia Univ. Babeş-Bolyai Math. 31_ , 1986, pp. 44–48.
  * [2] D. F. Aranha, Y. El Housni, A. Guillevic, A survey of elliptic curves for proof systems, _Des. Codes Cryptogr. 91_ , 2023, pp. 3333–3378.
  * [3] R. C. Baker, G. Harman, J. Pintz, The difference between consecutive primes, II, _Proc. London Math. Soc. 83_ , 2001, pp. 532–562.
  * [4] M. Bellés-Muñoz, J. J. Urroz, J. Silva, _Revisiting Cycles of Pairing-Friendly Elliptic Curves_ , In CRYPTO 2023, Springer Cham, pp. 3–37.
  * [5] E. Ben-Sasson, A. Chiesa, E. Tromer, M. Virza, _Scalable Zero Knowledge via Cycles of Elliptic Curves_ , In CRYPTO 2014, Springer Berlin Heidelberg, pp. 276–294.
  * [6] S. Bowe, J. Grigg, D. Hopwood, _Halo: Recursive proof composition without a trusted setup_ , Cryptology ePrint Archive, Paper 2019/1021.
  * [7] J. Brown, D. Heras, K. James, R. Keaton, A. Qian, Amicable pairs and aliquot cycles for elliptic curves over number fields, _Rocky Mt. J. Math. 46_ , 2016, pp. 1853–1866.
  * [8] E. Carneiro, M. B. Milinovich, K. Soundararajan, Fourier optimization and prime gaps, _Comment. Math. Helv. 94_ , 2019, pp. 533–568.
  * [9] A. Chiesa, L. Chua, M. Weidner, On Cycles of Pairing-Friendly Elliptic Curves, _SIAM J. Appl. Algebra Geom. 3_ , 2019, pp. 175–192.
  * [10] D. A. Cox, _Primes of the form $x^{2}+ny^{2}$: Fermat, Class Field Theory and Complex Multiplication_, Wiley, 1989.
  * [11] H. Cramér, Some theorems concerning prime numbers, _Arkiv f. Math. Astr. Fys. 15_ , 1920, pp. 1–33. [Collected Works 1, 85–91, Springer, Berlin-Heidelberg, 1994.]
  * [12] M. Deuring, Die Typen der Multiplikatorenringe elliptischer Funktionenkörper, _Abh. Math. Semin. Hansische Univ. 14_ , 1941, pp. 197–272.
  * [13] D. R. Heath-Brown, The differences between consecutive primes, V, _Int. Math. Res. Not. IMRN 22_ , 2021, pp. 17514–17562.
  * [14] D. Hopwood, _Pluto-eris hybrid cycle of elliptic curves_ , 2021, available at https://github.com/daira/pluto-eris.
  * [15] D. Hopwood, _The pasta curves for halo 2 and beyond_ , 2020, available at https://electriccoin.co/blog/the-pasta-curves-for-halo-2-and-beyond/.
  * [16] N. Jones, Elliptic aliquot cycles of fixed length, _Pac. J. Math. 263_ , 2013, pp. 353–371.
  * [17] D. Kohel, _Endomorphism rings of elliptic curves over finite fields_ , PhD thesis, University of California, Berkeley, 1996.
  * [18] A. Kosyak, P. Moree, E. Sofos, B. Zhang, Cyclotomic polynomials with prescribed height and prime number theory, _Mathematika 67_ , 2021, pp. 214–234.
  * [19] S. Lang, _Elliptic functions_ , Springer, 1987.
  * [20] I. Meckler, _O(1) labs fork of zexe: implementation of bn382-plain_ , 2020, available at https://github.com/o1-labs/zexe/tree/master/algebra/src/bn_382.
  * [21] P. Mihăilescu, _Dual Elliptic Primes and Applications to Cyclotomy Primality Proving_ , ArXiv: 0709.4113.
  * [22] P. Mihăilescu, Primary Cyclotomic Units and a Proof of Catalan’s Conjecture, _J. Reine Angew. Math. 572_ , 2004, pp. 167–195.
  * [23] P. Moree, Prime gaps and cyclotomic polynomials, _Nieuw Arch. Wisk. 5/22_ , 2021, pp. 219–225.
  * [24] J. Neukirch, _Algebraic Number Theory, Translated from the German by Norbert Schappacher_ , Springer-Verlag, Berlin Heidenberg New York, 1999.
  * [25] J. Parks, An asymptotic for the average number of amicable pairs for elliptic curves, _Math. Proc. Camb. Philos. Soc. 166_ , 2019, pp. 33–59.
  * [26] S. S. Pillai, On $a^{x}-b^{y}=c$, _J. Indian Math. Soc. 2_ , 1936, pp. 119–122.
  * [27] S. S. Pillai, A correction to the paper “On $a^{x}-b^{y}=c$”, _J. Indian Math. Soc. 2_ , 1937, p. 215.
  * [28] P. Ribenboim, _Catalan’s Conjecture: Are $8$ and $9$ the only Consecutive Powers?_, Academic Press, Inc. 1994.
  * [29] J. H. Silverman, _Advanced Topics in the Arithmetic of Elliptic Curves_ , Springer, 1994.
  * [30] J. H. Silverman, _The Arithmetic of Elliptic Curves_ , 2nd edition, Springer, 2008.
  * [31] J. H. Silverman, K. E. Stange, Amicable Pairs and Aliquot Cycles for Elliptic Curves, _Exp. Math. 20_ , 2011, pp. 329–357.
  * [32] A. V. Sutherland, _Isogeny volcanoes_ , In ANTS X. Open Book Series 1, 2012, pp. 507–530.
  * [33] M. Visser, Strong version of Andrica’s conjecture, _Int. Math. Forum 14_ , 2019, pp. 181–188.
  * [34] S. S. Wagstaff, Divisors of Mersenne numbers, _Math. Comp. 40_ , 1983, pp. 385–397.
  * [35] W. Waterhouse, Abelian varieties over finite fields, _Ann. Sci. Ècole Norm. Sup. 2_ , 1969, pp. 521–560.
  * [36] A. Weingartner, The constant factor in the asymptotic for practical numbers, _Int. J. Number Theory 16_ , 2020, pp. 629–638.
  * [37] X.-H. Wu, Special forms and the distribution of practical numbers, _Acta Math. Hungar. 160_ , 2020, pp. 405–411.