text:
\begin{document}

\title[Genus bounds for curves]
{Genus bounds for curves \\ with fixed Frobenius eigenvalues}

\author[Elkies]{Noam D. Elkies}
\address{
  Department of Mathematics,
  Harvard University,
  Cambridge, MA 02138--2901
}
\email{elkies@math.harvard.edu}
\urladdr{\href{http://www.math.harvard.edu/~elkies/}
              {http://www.math.harvard.edu/\lowtilde{}elkies/}}

\author[Howe]{\hbox{Everett W. Howe}}
\address{Center for Communications Research,
         4320 Westerra Court,
         San Diego, CA 92121-1967, USA.}
\email{however@alumni.caltech.edu}
\urladdr{\href{http://www.alumni.caltech.edu/~however/}
              {http://www.alumni.caltech.edu/\lowtilde{}however/}}

\author[Ritzenthaler]{\hbox{Christophe Ritzenthaler}}
\address{Institut de Math\'ematiques de Luminy,
         UMR 6206 du CNRS,
         Luminy, Case 907, 13288 Marseille, France.}
\email{ritzenth@iml.univ-mrs.fr}
\urladdr{\href{http://iml.univ-mrs.fr/~ritzenth/}
              {http://iml.univ-mrs.fr/\lowtilde{}ritzenth/}}
\thanks{The third author is partially supported by grant MTM2006-11391
        from the Spanish MEC and by grant ANR-09-BLAN-0020-01 from the
        French ANR}

\date{14 December 2011}
\keywords{Curve, Jacobian, Weil polynomial, Frobenius eigenvalue, genus,
          linear programming}

\subjclass[2010]{Primary 14G10; Secondary 11G20, 14G15, 14H25}

\begin{abstract}
For every finite collection $\calC$ of abelian varieties over~$\FF_q$,
we produce an explicit upper bound on the genus of curves over $\FF_q$
whose Jacobians are isogenous to a product of powers of elements
of~$\calC$.

Our explicit bound is expressed in terms of the Frobenius angles of
the elements of $\calC$.  In general, suppose that $S$ is a finite
collection of $s$ real numbers in the interval $[0,\pi]$.  If
$S = \{0\}$ set $r = 1/2$; otherwise, let
\[
r = \#(S\cap\{\pi\}) + 2 \! \sum_{\theta\in S\setminus\{0,\pi\}}
      \left\lceil \frac{\pi}{2\theta}\right\rceil.
\]
We show that if $C$ is a curve over $\FF_q$ whose genus is greater
than
\[
\min\left(
  23\, s^2  q^{2s} \log q,
  \
  (\sqrt{q}+1)^{2r} \left(\frac{ 1 + q^{-r}}{2} \right)
\right),
\]
then $C$ has a Frobenius angle $\theta$ such that neither $\theta$
nor $-\theta$ lies in $S$.

We do not claim that this genus bound is best possible.  For any
particular set $S$ we can usually obtain a better bound by solving a
linear programming problem.  For example, we use linear programming to
give a new proof of a result of Duursma and Enjalbert:  If the Jacobian
of a curve $C$ over $\FF_2$ is isogenous to a product of elliptic curves
over $\FF_2$ then the genus of $C$ is at most~$26$.  As Duursma and
Enjalbert note, this bound is sharp, because there is an $\FF_2$-rational
model of the genus-$26$ modular curve $X(11)$ whose Jacobian splits
completely into elliptic curves.

As an application of our results, we reprove (and correct a small error
in) a result of Yamauchi, which provides the complete list of positive
integers $N$ such that the modular Jacobian $J_0(N)$ is isogenous
over $\QQ$ to a product of elliptic curves.
\end{abstract}

\maketitle

\section{Introduction}
\label{S:intro}

Let $(C_n)$ be a sequence of curves over a finite field $k$ such that
the genus of $C_n$ tends to infinity with $n$.
Serre~\cite{serre}*{Cor.~2, p.~93} applies a result of Tsfasman and
\Vladut~\cites{tsfasman,TV} to show that the dimension of the largest
$k$-simple isogeny factor of the Jacobian of $C_n$ tends to infinity
with~$n$.  In this article we give an explicit bound for this
asymptotic result.

The \emph{Weil polynomial} of a $d$-dimensional abelian variety $A$
over a finite field $\FF_q$ is the characteristic polynomial of the
$q$-th power Frobenius endomorphism of $A$ (acting, for instance, on
the $\ell$-adic Tate module of $A$).  The Weil polynomial is a monic
polynomial in $\ZZ[x]$ of degree $2d$, and its complex roots
$\alpha_1,\ldots,\alpha_{2d}$ all have magnitude~$\sqrt{q}$.  The roots
can be written $\alpha_j = \sqrt{q} \exp(i \theta_j)$ for real numbers
$\theta_j$ in the half-open interval $(-\pi, \pi]$, and the roots can
be ordered so that $\alpha_j\alpha_{j+d} = q$ and
\[
0 \le \theta_1 \le \theta_2 \le \cdots \le \theta_d \le \pi.
\]
The $\theta_j$ are called the \emph{Frobenius angles} of $A$, and the
$\theta_j$ that are nonnegative are the \emph{nonnegative Frobenius
angles} of $A$.  If $C$ is a curve over $\FF_q$, we define the
Frobenius angles of $C$ to be the Frobenius angles of its Jacobian.

We show that for any finite set $S$ of real numbers in the interval
$[0,\pi]$, every curve over $\FF_q$ of sufficiently large genus has
a nonnegative Frobenius angle that does not lie in $S$.

\begin{theorem}
\label{T:angles}
Let $S$ be a finite set of $s$ real numbers $\theta$ with
$0\le\theta\le\pi$.  If $S = \{0\}$ set $r = 1/2$; otherwise,
take
\[
r = \#(S\cap\{\pi\}) + 2 \! \sum_{\theta\in S\setminus\{0,\pi\}}
       \left\lceil \frac{\pi}{2\theta}\right\rceil,
\]
where $\lceil x\rceil$ denotes the least integer greater than or equal
to the real number $x$.  Let
\[
B_1 = 23\, s^2 q^{2s}\log q
\text{\quad and \quad}
B_2 =(\sqrt{q}+1)^{2r} \left(\frac{ 1 + q^{-r}}{2}\right).
\]
If $C$ is a curve over~$\FF_q$ whose nonnegative Frobenius angles all
lie in $S$, then the genus $g$ of $C$ satisfies $g \le B_1$ and
$g < B_2$.
\end{theorem}

\begin{remark}
Elementary calculations show that if $s > 7\sqrt{q}\log q$
then the bound $B_1$ from Theorem~\ref{T:angles}
is smaller than the bound $B_2$.
\end{remark}

Theorem~\ref{T:angles}
allows us to derive an explicit version of Serre's result.

\begin{corollary}
\label{C:Serre}
If $C$ is a curve of genus $g > 2$ over a finite field $\FF_q$, then
the Jacobian of $C$ has a simple isogeny factor of dimension greater
than
\[
\sqrt{\frac{\log\log g}{6\log q}}.
\]
\end{corollary}

The first genus bound from Theorem~\ref{T:angles} leads to a corollary
that does not mention Frobenius angles.

\begin{corollary}
\label{C:varieties}
Let $A$ be a $d$-dimensional abelian variety over~$\FF_q$.  If $C$ is a
curve over $\FF_q$ of genus greater than $23\, d^2 q^{2d}\log q$ then
the Jacobian of $C$ has a simple isogeny factor $B$ that is not an
isogeny factor of $A$.
\end{corollary}

One natural choice for the set $S$ in Theorem~\ref{T:angles} is the
set of all nonnegative Frobenius angles for elliptic curves over a
given finite field.  Applying the theorem to this set leads to the
following corollary:

\begin{corollary}
\label{C:split}
Suppose $C$ is a curve over $\FF_q$ whose Jacobian is isogenous over
$\FF_q$ to a product of elliptic curves.  Then the genus of $C$ is at
most $510\, q^{8\sqrt{q} + 3} \log q$.
\end{corollary}

We prove Theorem~\ref{T:angles} and its corollaries in
Section~\ref{S:proof}.  As we will show in Remark~\ref{R:B1},
for every prime power $q$ there is a family of sets $S$ for which
(in the notation of Theorem~\ref{T:angles}) the ratio $B_1/g$ is
less than $47 s^2 \log q$; similarly, in Remark~\ref{R:B2}
we show that there is a family of examples with $s=1$ and
$q\to\infty$ for which the ratio $B_2/g$ approaches $1$.
For many sets~$S$, however, we expect that the bounds given by
Theorem~\ref{T:angles} are likely to be far from optimal;
in Section~\ref{S:LP} we show how tighter bounds can sometimes
be obtained by solving an integer linear programming problem.
As a concrete example, we take $S$ to be the set of nonnegative
Frobenius angles of the elliptic  curves over $\FF_2$, and use the
linear programming method to show that the genus of a curve over
$\FF_2$ whose Jacobian splits up to isogeny into elliptic curves
is at most~$26$, a result proved earlier by Duursma and
Enjalbert~\cite{DE} by a different (but related) method.
In Section~\ref{S:X11} we show that for this particular set $S$
the genus bound of $26$ is sharp, because the genus-$26$ modular
curve $X(11)$ has a model over $\FF_2$ whose Jacobian is isogenous
over $\FF_2$ to a product of elliptic curves.
(We find sharp upper bounds in other cases as well; see
Remark~\ref{R:ordinary}.)
In Section~\ref{S:X0} we use this genus bound to give a simple proof
of a result of Yamauchi~\cite{yamauchi} on the values of $N$ for which
the Jacobian of the modular curve $X_0(N)$ is isogenous over $\QQ$ to a
product of elliptic curves.

\subsubsection*{Conventions and notation.}
Operators such as $\Hom$, $\End$ or $\Aut$ applied to varieties over a
field $k$ will always refer to $k$-rational homomorphisms and
endomorphisms. Similarly, when we say that an abelian variety over $k$
is `decomposable', `split', or `simple', these words should be
interpreted with respect to isogenies over~$k$. In the sequel, we use
$e(x)$ to denote $\exp(i x)$, where $i = \sqrt{-1}$, and we use $\re(x)$
to denote the real part of a complex number $x$.

\subsubsection*{Acknowledgments.}
After an initial version of this work was posted on the arXiv, Mike
Zieve alerted us to the paper of Duursma and Enjalbert~\cite{DE}
mentioned above, which contains a result that implies our
Lemma~\ref{L:key-lemma} (see~\S2.4 of the arXiv version of~\cite{DE})
and which proves that a curve over $\FF_2$ whose Jacobian is isogenous
to a product of elliptic curves has genus at most~$26$.  The print
version of their paper also states that there is a model of $X(11)$
over $\FF_2$ whose Jacobian is isogenous over $\FF_2$ to a produce
of elliptic curves; this is proved in an addendum added to the arXiv
version.  We are grateful to Mike Zieve for telling us about~\cite{DE},
and to Iwan Duursma for discussions about these results.

We are grateful to Armand Brumer for informing us of Yamauchi's
paper~\cite{yamauchi}.

In the initial version of this paper, the bound $B_1$ in
Theorem~\ref{T:angles} was a doubly-exponential expression in~$s$ that
we obtained via an argument using our Lemma~\ref{L:key-lemma}.  We are
extremely grateful to Zeev Rudnick and Sergei Konyagin for pointing out
to us that the work of Smyth~\cite{smyth} could be used to get a bound
that is singly-exponential in~$s$.  Our proof that $B_1$ gives an upper
bound for the genus is due almost entirely to them.

The work in this paper was begun at the GeoCrypt 2009 conference in
Pointe-\`a-Pitre.  We would like to thank the organizers of the
conference for providing a stimulating environment for collaboration.

\section{Proof of Theorem~\ref{T:angles} and its corollaries}
\label{S:proof}

In this section we prove Theorem~\ref{T:angles} and
Corollaries~\ref{C:varieties} and~\ref{C:split}.  The arguments that
show that $B_1$ and $B_2$ give upper bounds on the genus are
independent of one another, so we break the proof of
Theorem~\ref{T:angles} into two parts.

\begin{proof}[Proof of Theorem~\textup{\ref{T:angles}},
              part \textup{1:} $g\le B_1$]
The bound $g\le B_1$ holds trivially when $S$ is empty, so we may
assume that $s > 0$.  First we consider the case where $s>1$.

Suppose $C$ is a curve over $\FF_q$ all of whose Frobenius angles lie
in~$S$.  Let the elements of $S$ be $\theta_1,\ldots,\theta_s$, and
for each index $j$ let $b_j$ denote the multiplicity of $\theta_j$ as
a Frobenius angle for $C$ (unless $\theta_j = 0$ or $\theta_j = \pi$,
in which case we let $b_j$ denote half of this multiplicity), so that
we have
\[
b_1 + \ldots + b_s = g.
\]
Reindex the $\theta_j$ and the corresponding $b_j$ so that
$b_1\ge b_2 \ge \cdots \ge b_s$, and note that this implies that
$b_1 \ge g / s$. Finally, for every $j$ let $z_j = e(\theta_j)$, and
for every integer $k > 0$ let $G(k)$ denote the weighted power sum
\[
G(k) = b_1 z_1^k + \cdots + b_s z_s^k.
\]
Weil's `Riemann Hypothesis' for curves over finite fields says that
\[
\#C(\FF_{q^k}) = q^k + 1 - \sum_{j=1}^{2g} \alpha_j^k
              = q^k + 1 - 2 q^{k/2} \re G(k),
\]
so we find that
\[
2 \re G(k) = q^{k/2} + q^{-k/2} - \#C(\FF_{q^k}) / q^{k/2}.
\]

Now we apply a result of Smyth~\cite{smyth}. Let
\[
\beta := (b_2 + \cdots + b_s)/b_1,
\]
let $\lambda$ be an arbitrary real number with $0 < \lambda \le 1$,
and let
\[
K := 1 + \lfloor(4\beta+3)/\lambda\rfloor.
\]
Smyth shows that then
\[
(b_1/4)(1-\lambda) < \max_{1\le k \le K} \re G(k).
\]
In our case, we have $\beta = g/b_1 - 1 \le s - 1$, so
$K \le 1 + (4\beta+3)/\lambda  \le L$, where we set
\[
L:= 1 + (4s - 1)/\lambda.
\]
Also, for each $k$ we have $\re G(k) \le (1/2)(q^{k/2} + q^{-k/2})$.
Since $q^x + q^{-x}$ is an increasing function of $x$ for $x>0$,
Smyth's result shows that
\[
(b_1/4)(1-\lambda) < (1/2)(q^{L/2} + q^{-L/2}).
\]
As we noted earlier, we have $b_1\ge g/s$, so for every $\lambda$
with $0<\lambda<1$ we have
\begin{equation}
\label{EQ:Smyth}
\frac{g}{s} < \frac{2}{1-\lambda}\left(q^{L/2} + q^{-L/2}\right).
\end{equation}

We will apply this inequality with $\lambda = 1 - 1/a$, where
\[
a = \left(\frac{4s-1}{2}\right)\log q.
\]
(This choice of $\lambda$ was obtained by taking the first two terms of
the power series expansion (in $1/a$) of the value of $\lambda$ that
minimizes $q^{L/2}/(1-\lambda)$.)  Note that $L > 4s \ge 8$, so that
\[
q^{L/2} + q^{-L/2} = q^{L/2}(1 + q^{-L}) < \frac{257}{256}q^{L/2}.
\]
Combining this with~\eqref{EQ:Smyth}, we find
\begin{align*}
\frac{g}{s} &< \left(\frac{257}{256}\right)
               \left(\frac{2}{1-\lambda}\right) q^{L/2} \\
            &= \left(\frac{257}{256}\right)
               (4s-1)(\log q) \, \exp((L/2)\log q).
\end{align*}
Using the equality $L = 1 + (4s - 1)/\lambda$, we find that
\begin{align*}
(L/2) \log q    &= (\log q)/2 + \left(\frac{4s - 1}{2}\right)
                                      \frac{\log q}{\lambda} \\
                &= (\log q)/2 + a/\lambda \\
                &= (\log q)/2 + a^2/(a-1) \\
                &= (\log q)/2 + a + a/(a-1)\\
                &= 2 s \log q + a/(a-1).
\end{align*}
Since $s\ge 2$ and $q\ge 2$ we have $a\ge (7/2)\log 2$ and
$\exp(a/(a-1)) < 5.5$.  Thus
\[
\exp((L/2)\log q) < 5.5\, \exp(2s\log q) = 5.5 \,q^{2s},
\]
so
\[
\frac{g}{s} < \left(\frac{257}{256}\right)
              (4s)(\log q) (5.5\, q^{2s})
            < 23\, s q^{2s} \log q.
\]
This shows that $g < B_1$ when $s > 1$.

Now suppose $s = 1$.  Let $\theta$ be the unique element of $S$.
If $\theta \ge \pi/2$ then the quantity $r$ defined in the statement
of the theorem is equal to $2$.  It is easy to show that then
$B_2 < B_1$, so the bound $g < B_2$, proved below, shows that
$g < B_1$.

The final case to consider is when $s = 1$ and $\theta < \pi/2$.
If $C$ has only one nonnegative Frobenius angle $\theta$, then
$e(\theta)\sqrt{q}$ must be an algebraic integer of degree at most
$2$ over the rationals, so the quantity
$t =  e(\theta)\sqrt{q} +  e(-\theta)\sqrt{q}$ is an integer.
Furthermore, since $\theta$ is less than $\pi/2$ the integer $t$
is positive.  Then Weil's theorem shows that
\[
0 \le \#C(\FF_q) = q + 1 - gt \le q + 1 - g,
\]
so that $g \le q + 1.$  Again, it follows easily that $g < B_1$.
\end{proof}

Our proof that $B_2$ gives an upper bound for the genus relies upon
the following lemma.

\begin{lemma}
\label{L:key-lemma}
Let $S$ be a set of real numbers in $[0,\pi]$ and let $T \in \RR[X]$ be
a polynomial with nonnegative coefficients such that $T(0)=0$ and
$\re(T(e(\theta))) \geq 1$ for all $\theta \in S$.  If $C$ is a curve
over $\FF_q$ whose nonnegative Frobenius angles all lie in~$S$, then
the genus of $C$ is at most $(T(q^{1/2}) + T(q^{-1/2})) / 2$.
\end{lemma}

\begin{proof}
Let $\alpha_1,\ldots,\alpha_{2g}$ be the complex roots of the Weil
polynomial of~$C$, listed with appropriate multiplicities, so that
from Weil's theorem we have
\[
\#C(\FF_{q^m}) = q^m + 1 - \sum_{j=1}^{2g} \alpha_j^m
\]
for all integers $m>0$.  Write
\[
T = a_1 x + \cdots + a_n x^n, \quad a_j \geq 0.
\]
Then
\begin{align*}
0 &\le \sum_{m=1}^n a_m \frac{\#C(\FF_{q^m}) }{q^{m/2}}\\
   & =  \sum_{m=1}^n a_m \left(
         q^{m/2} + q^{-m/2} - \sum_{j=1}^{2g} \alpha_j^m/q^{m/2}
         \right)\\
   &= T(q^{1/2}) + T(q^{-1/2}) - \sum_{j=1}^{2g} T(\alpha_j/\sqrt{q}).
\end{align*}
By hypothesis, each summand $T(\alpha_j/\sqrt{q})$ has real part at
least $1$, so
\[
0 \le T(q^{1/2}) + T(q^{-1/2}) - 2g,
\]
and hence
\[
g \le \frac{T(q^{1/2}) + T(q^{-1/2}) }{2}.
\]
\end{proof}

\begin{remark}
This lemma could also be proved by using the results in~\S2.4 of the
arXiv version of~\cite{DE}.
\end{remark}

\begin{remark}
Lemma~\ref{L:key-lemma} is stated for polynomials $T$ with nonnegative
coefficients, but an analogous statement holds when $T$ is a power
series in $\RR[[x]]$ with nonnegative coefficients, so long as its
radius of convergence exceeds $\sqrt{q}$.
\end{remark}

With this lemma in hand, we complete the proof of
Theorem~\ref{T:angles}.  Our proof will depend on a careful choice of
the polynomial $T$.

\begin{proof}[Proof of Theorem~\textup{\ref{T:angles}},
              part \textup{2:} $g < B_2$]
It is easy to check that $g < B_2$ when $S$ is empty, so we may assume
that $S$ is nonempty. If $S = \{0\}$ then the quantity $r$ from the
theorem is equal to $1/2$. In this case we can take $T = x$, and we find
that $(T(q^{1/2}) + T(q^{-1/2}))/2$ is less than $B_2$. Then
Lemma~\ref{L:key-lemma} shows that $g < B_2$.  So
let us assume that $S$ contains a nonzero element.

Given a nonzero $\theta\in S$, let
$m = \left\lceil \frac{\pi}{2\theta}\right\rceil,$  so that
$\cos(m\theta)\le 0$.  If $\theta = \pi$ let $P_\theta$ be the
polynomial $1+x$; otherwise, set
$P_\theta = 1 - 2\cos(m\theta)x^m + x^{2m}$. In both cases we have
$P_\theta(e(\theta)) = 0.$  Let
\[
P = \prod_{\theta\in S\setminus\{0\}} P_\theta.
\]
Then $P$ is a polynomial with constant term $1$, with nonnegative
coefficients, and with degree equal to $r$, where
\[
r = \#(S\cap\{\pi\}) + 2\sum_{\theta\in S\setminus\{0,\pi\}}
      \left\lceil \frac{\pi}{2\theta}\right\rceil
\]
is as in the statement of the theorem.  Let $T = (P-1)^2$.  Then
$T(0) = 0$, the coefficients of $T$ are nonnegative, and for every
$\theta \in S\setminus\{0\}$ we have $T(e(\theta)) = 1.$  Also, for
each $\theta$ we have $P_{\theta}(1)\ge 2$, so $P(1)\ge 2$ and
$T(1)\ge 1$.  Lemma~\ref{L:key-lemma} shows that any curve whose
nonnegative Frobenius angles all lie in $S$ must have genus no larger
than $(T(q^{1/2}) + T(q^{-1/2}))/2$.  Now, for positive real numbers
$z$ we have $1\le P(z) \le (1 + z)^r$, so that $T(z) < (1+z)^{2r}.$
Thus we have
\begin{align*}
T(q^{1/2}) + T(q^{-1/2}) &< (\sqrt{q} + 1)^{2r} + (1/\sqrt{q} + 1)^{2r}\\
                         &= (\sqrt{q} + 1)^{2r }(1 + q^{-r}),
\end{align*}
which gives the inequality $g < B_2$.
\end{proof}

\begin{remark}
\label{R:B2}
In Section~\ref{S:LP} we will see that our bounds can sometimes be bad.
However, the following easy example shows that at least in one case our
second bound is asymptotically exact as $q \rightarrow \infty$.  For
any prime power~$q$ let $E$ be a supersingular elliptic over $\FF_q$
with Weil polynomial $x^2+q$, corresponding to the set $S=\{\pi/2\}$.
Applying Theorem~\ref{T:angles}, we see that the genus of a curve
$C / \FF_q$ with Jacobian isogenous to a power of~$E$ is bounded above
by
\[
(\sqrt{q}+1)^4 \cdot \left(\frac{1+q^{-2}}{2}\right) \sim q^2/2
                  \text{\qquad as $q\to\infty$}.
\]
On the other hand, $\Jac(C)$ is isogenous to a power of~$E$ if and only
if $C$ is optimal over $\FF_{q^2}$, in the sense that its number of
points attains the Weil upper bound.  But the maximal genus of such a
curve is $q(q-1)/2 \sim q^2/2$ (see \cite{ihara}), attained by the
Hermitian curve $H_q$ defined by $x^{q+1}+y^{q+1}+z^{q+1}=0$ (see for
instance~\cite{RS}).
\end{remark}

\begin{remark}
\label{R:moreB2}
The Hermitian curve $H_q$, viewed as a curve over $\FF_{q^2}$, again
gives an example of a curve whose genus comes close to the upper
bound $B_2$.  If we take $S = \{\pi\}$ then the bound $B_2$ for the
field $\FF_{q^2}$ is
\[
(q+1)^2 \cdot \left(\frac{1+q^{-2}}{2}\right) \sim q^2/2
                  \text{\qquad as $q\to\infty$},
\]
while $H_q$ has genus $q(q-1)/2$.
\end{remark}

\begin{remark}
\label{R:B1}
Hermitian curves can also be used to give examples that limit the
extent to which we might hope to improve the bound~$B_1$.  For any
integer $s>0$, let $S$ be the $s$-element set
\[
S = \left\{\frac{\pi}{2s}, \frac{3\pi}{2s}, \ldots, \frac{(2s-1)\pi}{2s} \right\}.
\]
Let $q$ be any prime power and set $Q=q^s$.
Note that the nonnegative Frobenius angles
of a curve $C$ over $\FF_q$ are contained in $S$ if and only if the
only nonnegative Frobenius angle of the base extension of $C$ to
$\FF_Q$ is $\pi/2$.  Let $C$ be the curve
$x^{Q+1}+y^{Q+1}+z^{Q+1}=0$ over $\FF_q$.  As noted in
Remark~\ref{R:B2}, the base extension of $C$ to $\FF_Q$ has $\pi/2$
as its unique Frobenius angle, so all of the Frobenius angles of $C$
itself are contained in $S$.  Since the genus of $C$ is
$(q^{2s}-q^s)/2$, we see that Theorem~\ref{T:angles} would be false if
we replaced $B_1$ with any expression of the form
\[
(\text{polynomial in $s$ and $\log q$}) \, q^{2s-\eps}
\]
for a positive constant~$\eps$.
\end{remark}

We end this section by proving the corollaries from the introduction.

\begin{proof}[Proof of Corollary~\textup{\ref{C:Serre}}]
We begin by noting that for every integer $n>0$,
the number of isogeny classes of $n$-dimensional
abelian varieties over~$\FF_q$ is less than $6^{n^2}q^{n(n+1)/4}$.
This is easy to check for $n=1$ (see the proof of
Corollary~\ref{C:split} below) and for $n=2$, while for $n > 2$ it
follows from the results in~\cite{DH1} (as corrected in~\cite{DH2}).
We leave the details of the argument to the reader, but we do at least
note that it is helpful to observe that for every $n$, the quantity
$v_n$ in~\cite{DH1}*{Thm.~1.2} is bounded above by $264$.
It follows that the number of isogeny classes of \emph{simple} abelian
varieties over $\FF_q$ of dimension \emph{at most} $n$ is also less than
$6^{n^2}q^{n(n+1)/4}$, and that the number of nonnegative Frobenius
angles of abelian varieties over $\FF_q$ of dimension at most $n$ is
less than $n 6^{n^2}q^{n(n+1)/4}$.

Suppose, to obtain a contradiction, that the corollary is false, and
let $C$ be a curve of genus $g$ over $\FF_q$ that provides a
counterexample.  Take
\[
n = \left\lfloor\sqrt{\frac{\log \log g}{6 \log q}}\right\rfloor.
\]
For $C$ to provide a counterexample we must have~$n\ge 1$.
We will apply Theorem~\ref{T:angles} to the set of nonnegative
Frobenius angles of abelian varieties over $\FF_q$ of dimension at
most~$n$; as we have just noted, this means that
in Theorem~\ref{T:angles} we have $s < n 6^{n^2} q^{n(n+1)/4}$.
Simple estimates for the terms
in the right-hand side of this inequality show that
\begin{equation}
\label{EQ:s}
s < q^{4n^2}.
\end{equation}
Note that there are at least $5$ isogeny classes of elliptic curves
over any field, so $s\ge 5$; using this fact it is easy to show
that the bound $B_1 = 23 s^2 q^{2s}\log q$ from the theorem satisfies
\begin{equation}
\label{EQ:B1}
B_1 < q^{4s}.
\end{equation}

The definition of $n$ tells us that
\[
\log\log g \ge 6 n^2 \log q,
\]
so exponentiating gives us
\[
\log g \ge q^{6n^2} > 4 q^{4n^2} \log q > 4 s \log q,
\]
where the third inequality follows from~\eqref{EQ:s}.  Exponentiating
again, we find that
\[
g > q^{4s} > B_1,
\]
by~\eqref{EQ:B1}.  Theorem~\ref{T:angles} then shows that $\Jac C$ has
a simple isogeny factor of dimension greater than $n$, contradicting
our assumption that $C$ was a counterexample to the corollary.  This
contradiction completes the proof.
\end{proof}

\begin{proof}[Proof of Corollary~\textup{\ref{C:varieties}}]
Let $S$ be the set of nonnegative Frobenius angles of the abelian
variety $A$ over $\FF_q$, so that $\#S\le d$.  If $C$ is a curve over
$\FF_q$ with genus greater than $23\, d^2 q^{2d}\log q$ then $C$ has
a nonnegative Frobenius angle $\theta$ not in $S$.  Let $B$ be any
element of the unique isogeny class of simple abelian varieties over
$\FF_q$ that have $\theta$ as one of their Frobenius angles.  Then
$B$ is an isogeny factor of $\Jac C$.  On the other hand, $A$ and
$B$ have coprime Weil polynomials, so by the Honda--Tate theorem $B$
is not an isogeny factor of~$A$.
\end{proof}

\begin{proof}[Proof of Corollary~\textup{\ref{C:split}}]
Let $m$ be the largest integer with $m^2 \le 4q$.  The Weil polynomial
of an elliptic curve over $\FF_q$ is of the form $x^2 - tx + q$, where
$t$ is an integer with $-m\le t\le m$.  (Not every $t$ in this range
need come from an elliptic curve.)  The nonnegative Frobenius angle
$\theta_t$ corresponding to a given $t$ is
$\theta_t = \cos^{-1} (t / (2 \sqrt{q} )).$  We take $S$ to be the
set $\{\theta_t \col -m \le t\le m\}$.

Clearly $\#S \le 4\sqrt{q} + 1$.  The bound $B_1$ from
Theorem~\ref{T:angles} is then
\begin{align*}
23\, s^2 q^{2s} \log q &\le 23\, (4\sqrt{q} + 1)^2 q^{8\sqrt{q} + 2} \log q\\
                       &\le 23\, \left(\frac{4\sqrt{2} + 1}{\sqrt{2}}\right)^2
                          q^{8\sqrt{q} + 3} \log q \\
                       &< 510\, q^{8\sqrt{q} + 3} \log q.
\end{align*}
\end{proof}

\section{Linear programming}
\label{S:LP}

The arguments we used to prove Theorem~\ref{T:angles} used no special
properties of the set $S$ and give a bound that is almost certainly
far from optimal when applied to most~$S$.  For example, suppose we
take $S$ to be the set of nonnegative Frobenius angles coming from
the elliptic curves over~$\FF_2$.  There are five isogeny classes of
elliptic curves over~$\FF_2$ (each containing a single curve),
corresponding to the five possible traces
of Frobenius $-2,-1,0,1,2$ (see \cite{deuring},
\cite{waterhouse}*{Theorem 4.1}). For each of these traces~$t$, let
$\alpha_t = (-t + \sqrt{t^2-8})/2$, let $\theta_t$ be the argument of
$\alpha_t$, and let $E_t$ be an elliptic curve over $\FF_2$ with
trace~$t$.  Let us apply Theorem~\ref{T:angles} to the set
$S =\{\theta_t\}$.  We find that $B_1 \approx 408125$ and
$B_2 \approx 2.6\times10^{10}$.  However, the best upper bound on the
genus is much smaller than these numbers.

\begin{theorem}[Duursma and Enjalbert~\cite{DE}]
\label{T:F2}
Suppose $C$ is a curve over $\FF_2$ whose Jacobian is isogenous to a
product of powers of the $E_t$.  Then the genus of $C$ is at most~$26$.
\end{theorem}

\begin{remark}
Duursma and Enjalbert prove this result by using a stronger version of
our Lemma~\ref{L:key-lemma}.  We give the proof presented here as an
example of our general technique of using linear programming to get
genus bounds.
\end{remark}

\begin{remark}
We will see in Section~\ref{S:X11} that the bound in Theorem~\ref{T:F2}
is sharp.
\end{remark}

\begin{proof}[Proof of Theorem~\textup{\ref{T:F2}}]
Our bounds in Theorem~\ref{T:angles} were obtained from the fact that
the number of points on a curve over a finite field is always
nonnegative.  We actually know a somewhat stronger constraint:  For
every $n>0$, the number of degree-$n$ places on a curve is
nonnegative.  If the size of the base field is large compared to the
genus of the curve in question, the bounds we get from using place
counts are not much better than the one we get from point counts.
However, Theorem~\ref{T:F2} involves a very small field indeed.

Let $C$ be a curve as in the statement of the theorem.  In particular,
suppose there are integers $e_t \ge 0$ such that the Jacobian of $C$
is isogenous to
\[
E_{-2}^{e_{-2}} \times
E_{-1}^{e_{-1}} \times
E_{ 0}^{e_{ 0}} \times
E_{ 1}^{e_{ 1}} \times
E_{ 2}^{e_{ 2}}.
\]
Then for every $n>0$ the number of points on $C$ over $\FF_{2^n}$ is
given by
\[
\#C(\FF_{2^n}) = 2^n + 1 - \sum_{-2\le t\le 2} e_t\Tr(\alpha_t^n),
\]
and the number $N_n$ of degree-$n$ places on $C$ is given by
\[
N_n = \frac{1}{n}\sum_{d|n} \mu(n/d)\#C(\FF_{2^d}),
\]
where $\mu$ is the M\"obius function.

The nonnegativity of the number of degree-$n$ places, for
$n=1,\ldots,8$, is expressed by the following inequalities:
\begin{equation}
\label{EQ:places8}
\begin{array}{rrrrrl}
- 2 e_{-2} & -   e_{-1} &          & +   e_1 & + 2 e_2 & \le  3  \\
    e_{-2} & -   e_{-1} & - 2 e_0  & - 2 e_1 & -   e_2 & \le  1  \\
  2 e_{-2} & + 2 e_{-1} &          & - 2 e_1 & - 2 e_2 & \le  2  \\
- 2 e_{-2} & +   e_{-1} & + 3 e_0  & +   e_1 & - 2 e_2 & \le  3  \\
  2 e_{-2} & - 2 e_{-1} &          & + 2 e_1 & - 2 e_2 & \le  6  \\
-   e_{-2} & +   e_{-1} & - 2 e_0  & + 3 e_1 & +   e_2 & \le  9  \\
- 2 e_{-2} & + 2 e_{-1} &          & - 2 e_1 & + 2 e_2 & \le 18  \\
  5 e_{-2} & - 4 e_{-1} & + 3 e_0  & - 4 e_1 & + 5 e_2 & \le 30  \\
\end{array}
\end{equation}
We claim that $\sum_{t=-2}^2 e_t \leq 26$ for any nonnegative integers
$e_t$ satisfying the inequalities above.  Indeed we show this even if
the $e_t$ are allowed to be nonnegative real numbers.  Maximizing their
sum is then a linear programming problem.  Solving the dual problem, we
find that if we take $39$ times the third inequality
of~\eqref{EQ:places8}, plus $44$ times the fourth inequality, plus $78$
times the sixth inequality, plus $32$ times the eighth inequality, we
obtain
\[
 72 e_{-2}  + 72 e_{-1}  + 72 e_0   + 72 e_1  + 72 e_2  \le 1872,
\]
so that $e_{-2}+e_{-1}+e_0+e_1+e_2\le 1872/72 = 26$, as claimed.
\end{proof}

\begin{remark}
\label{R:genus26}
By enumerating $5$-tuples of nonnegative integers
$(e_{-2},e_{-1},e_0,e_1,e_2)$ that sum to $26$ and checking whether
they satisfy the inequalities~\eqref{EQ:places8}, one finds that if a
genus-$26$ curve over $\FF_2$ has a completely split Jacobian, then
the Jacobian is isogenous to one of the varieties
\begin{align*}
&E_{-2}^4 \times E_{-1}^7 \times E_0^5 \times E_1^3 \times E_2^7,\\
&E_{-2}^5 \times E_{-1}^6 \times E_0^5 \times E_1^4 \times E_2^6,
\text{\ or}\\
&E_{-2}^6 \times E_{-1}^5 \times E_0^5 \times E_1^5 \times E_2^5.
\end{align*}
\end{remark}

\begin{remark}
We would not get a genus bound if we looked only at the inequalities
coming from counting the places of degree strictly less than $8$.  The
reader can check that for any even $g$, the values $e_{-2} = e_2 = g/2$
and $e_{-1}=e_0=e_1=0$ satisfy the first seven inequalities in the
system~\eqref{EQ:places8}. On the other hand, \emph{a priori} there is
no reason to think that the bound we get from looking at the counts of
places of degree $8$ and less will be the best possible; perhaps by
using the nonnegativity of several more place counts, we would get a
better bound.  In this particular instance, results of
Section~\ref{S:X11} show that the bound we obtain is in fact sharp.
\end{remark}

\begin{remark}
A similar argument, using places of degree at most $12$, shows that a
curve over $\FF_3$ whose Jacobian is isogenous to a product of elliptic
curves must have genus less than or equal to $2091$.   By extending the
argument slightly (or by using an integer linear programming package,
such as the one in Magma~\cite{magma}) one can improve this upper bound
to $2085$.  We suspect that this bound is not sharp!
\end{remark}

\begin{remark}
\label{R:ordinary}
If one restricts to curves whose Jacobians are isogenous to a product
of powers of ordinary elliptic curves, one finds a genus bound of
$3$ over $\FF_2$ and $26$ over $\FF_3$. The first bound is
reached by the the curve
\[
x^4 + y^4 + z^4 + x^2 y^2 + x^2 z^2 + y^2 z^2 + x^2 y z + x y^2 z + x y z^2 = 0
\]
which is a twist of the Klein quartic;  the second bound is reached as
well, as we show in Section~\ref{S:X11}.
\end{remark}

\section{The modular curve $X(11)$}
\label{S:X11}

In this section we show that the modular curve $X(11)$ has a model
defined over~$\FF_2$ whose Jacobian is isogenous over $\FF_2$ to
a product of elliptic curves. Since $X(11)$ has
genus~$26$, this example shows that the bound of Theorem~\ref{T:F2} is
sharp.  Duursma and Enjalbert~\cite{DE} provide a different proof
that $X(11)$ has a model over $\FF_2$ with completely split Jacobian;
their argument, found in the addendum to the arXiv version of their
paper, relies on working with Klein's explicit model of $X(11)$ in~$\PP^4$.

Let $G$ be the twist of the finite group scheme $\ZZ/11\ZZ$ over
$\FF_2$ on which the $\FF_2$-Frobenius acts as multiplication by~$3$,
and let $G'$ be the Cartier dual of $G$, so that $G'$ is the twist of
$\ZZ/11\ZZ$ on which the $\FF_2$-Frobenius acts as multiplication
by~$2/3=-3 \bmod 11$.  Let $e\col G\times G'\to\GG_m$ be the natural
pairing from $G\times G'$ to the multiplicative group.

Let $X$ be the modular curve over $\FF_2$ whose non-cuspidal
$K$-rational points, for every extension $K$ of $\FF_2$, parametrize
pairs $(E, \varphi)$, where $E$ is an elliptic curve over $K$ and
$\varphi$ is an isomorphism from the group scheme $E[11]$ to the group
scheme $(G\times G')\otimes_{\FF_2} K$ that takes the Weil pairing on
$E[11]$ to the pairing~$e$.

\begin{theorem}
\label{T:modular}
The genus of $X$ is $26$, and the Jacobian of $X$ is isogenous to
\[
E_{-2}^6 \times E_{-1}^5 \times E_0^5 \times E_1^5 \times E_2^5,
\]
where each $E_t$ is an elliptic curve over $\FF_2$ with trace $t$.
\end{theorem}

\begin{proof}
The curve $X$ is geometrically isomorphic to $X(11)$, so it has
genus~$26$ and geometric automorphism group isomorphic to~$\PSL_2(11)$
(see \cite{ritzenthaler}*{Th\'eor\`eme~5} and~\cite{BCG}).  Consider
the group scheme $(G\times G')\otimes_{\FF_2}\FF_4$; it is simply
$(\ZZ/11\ZZ)^2$, with the $\FF_4$-Frobenius acting as multiplication
by~$-2$.  The automorphism group of this $\FF_4$-scheme is $\GL_2(11)$,
and the subgroup of automorphisms that respect the pairing $e$ is
isomorphic to $\SL_2(11)$.  There is a surjective map
\[
\Aut \left( (G\times G')\otimes_{\FF_2}\FF_4, e\right)
\to \Aut (X\otimes_{\FF_2}{\FF_4})
\]
that sends an automorphism $\alpha$ of the finite group-scheme to the
automorphism $\beta$ of $X\otimes_{\FF_2}\FF_4$ that takes a pair
$(E,\varphi)$ to $(E,\alpha\varphi)$, and the kernel of this map is the
group $\{\pm1\}$.  Therefore all of the geometric automorphisms of $X$
are already defined over~$\FF_4$.

Using~\cite{GGHZ}*{Lemma~2.1} we see that the twists of the curve
$X\otimes_{\FF_2}\FF_4$ correspond to the conjugacy classes of
$\Aut (X\otimes_{\FF_2}\FF_4)$; also, the automorphism group of the
twist corresponding to the conjugacy class of an element $\alpha$ is
isomorphic to the commutator of $\alpha$.  Since $\PSL_2(11)$ has
trivial center, we see that every nontrivial twist of
$X\otimes_{\FF_2}\FF_4$ has automorphism group strictly smaller
than $\PSL_2(11)$.

Now take the $\QQ(\sqrt{-11})$-rational model $Y$ of $X(11)$ considered
by Ligozat~\cite{ligozat}*{Example~3.7.3, pp.~199--200}; Ligozat calls
this curve $X(11)_{K_{11}}$.  Let $\gothp$ be the prime of
$\QQ(\sqrt{-11})$ over~$2$, with residue field $\FF_4$.  The
automorphism group of $Y$ is $\PSL_2(11)$, so the reduction of $Y$
modulo $\gothp$ also has automorphism group $\PSL_2(11)$.  Therefore,
the reduction of $Y$ must be $X\otimes_{\FF_2}\FF_4$.  Applying a
result of Ligozat~\cite{ligozat}*{Prop 3.6.1, p.~223}, we find that the
Jacobian of $X$ is isogenous to
$E_{-2}^{11}\times E_0^5 \times E_1^{10}$.  (To see this, we must take
the elliptic curves mentioned in Ligozat's proposition and compute
their reductions modulo $\gothp$.)

It follows that over $\FF_2$, the Jacobian of $X$ is isogenous to
\[
E_{-2}^a E_{-1}^b E_0^5 E_1^{10-b} E_2^{11-a}
\]
for some choice of $a$ and $b$, and by Remark~\ref{R:genus26}, we know
that $(a,b)$ is one of $(4,7)$, $(5,6)$, and~$(6,5)$.

For each of the three possible isogeny classes we can compute the
associated zeta function and the number of $\FF_2$-rational points on
a curve with that zeta function.   We find that if the number of
$\FF_2$-rational points on $X$ is $1$, then $(a,b)=(4,7)$; if
$\#X(\FF_2)=3$ then $(a,b) = (5,6)$; and if $\#X(\FF_2) = 5$ then
$(a,b) = (6,5)$.

Consider $E_0$, the unique elliptic curve over $\FF_2$ with trace~$0$.
The characteristic polynomial of Frobenius on $E_0[11]$ is $x^2 + 2$,
so the action of Frobenius on $E_0[11]$ has two eigenspaces, one with
eigenvalue $3$ and one with eigenvalue $-3$.  One finds that there are
$10$ pairing-respecting isomorphisms $\varphi:E_0[11]\to G\times G'$,
and since $(E_0,\varphi)$ and $(E_0,-\varphi)$ are represented by the
same point on $X$, we have found $5$ $\FF_2$-rational points on $X$.
Therefore the Jacobian of $X$ decomposes as claimed in the statement
of the theorem.
\end{proof}

\begin{remark}
One can show that the curve $X$ has $60$ cusps (that is, points that
lie over the point at infinity on the the $j$-line).  The field of
definition of $10$ of the cusps is $\FF_{2^5}$; the field of definition
of the other $50$ is $\FF_{2^{10}}$.  Using these facts, together with
the modular interpretation of the non-cuspidal points on $X$, we can
compute the number of points on $X$ over any (reasonably small)
extension of~$\FF_2$. This gives another method of computing the
decomposition of the Jacobian of~$X$.
\end{remark}

\begin{remark}
Applying Ligozat's Proposition~3.6.1, we see that the Jacobian of
$X(11)_{K_{11}} \otimes \FF_3$ splits into a product of ordinary
elliptic curves. Hence the bound $26$ for ordinary elliptic curves over
$\FF_3$ from Remark~\ref{R:ordinary} is reached as well.
\end{remark}

\section{Application: Modular curves with split Jacobians}
\label{S:X0}

Let $J_0(N)$ denote the Jacobian of the modular curve $X_0(N)$
over~$\QQ$.  Cohen~\cite{cohen} (mentioned
in~\cite{serre}*{Remarque~2, p.~90} with the value $N=27$ omitted)
has computed a list of the odd integers $N$ for which $J_0(N)$ is
isogenous to a product of elliptic curves, and
Yamauchi~\cite{yamauchi}*{Thm.~1.1}
extended this list to include even values of $N$ as well.  In this section we use
Theorem~\ref{T:F2} and the mathematical software package
Sage~\cite{sage} to recompute Yamauchi's list; we note that the list
in Yamauchi's theorem mistakenly includes $N=672$ and omits $N=28$.

\begin{theorem}
\label{T:X0}
Let $N = 2^e n$ with $n$ odd.  Then $J_0(N)$ is isogenous over~$\QQ$
to a product of elliptic curves if and only if $n$ appears in the
following table and $e \leq \emax(n)$ with $\emax(n)$ as
tabulated\textup{:}
\[
\begin{array}{r|ccr|ccr|c}
 n & \emax(n) &\qquad &  n & \emax(n) &\qquad &   n & \emax(n) \\
\cline{1-2}\cline{4-5}\cline{7-8}
 1 & 7    & & 15 & 4    & &  37 & 0    \\
 3 & 7    & & 17 & 1    & &  45 & 4    \\
 5 & 4    & & 19 & 2    & &  49 & 0    \\
 7 & 4    & & 21 & 4    & &  57 & 1    \\
 9 & 7    & & 25 & 4    & &  75 & 4    \\
11 & 2    & & 27 & 4    & &  99 & 2    \\
13 & 2    & & 33 & 2    & & 121 & 0    \\
\end{array}
\]
\end{theorem}

\begin{proof}
Suppose $N$ is an odd integer such that $J_0(N)$ splits into elliptic
curves.  Since $N$ is odd the modular curve $X_0(N)$ has good reduction
modulo~$2$, and the reduced curve over $\FF_2$ has split Jacobian.  By
Theorem~\ref{T:F2}, the genus of $X_0(N)$ is at most $26$.  Using the
fact~\cite{CWZ} that the genus of $X_0(N)$ is greater than or equal to
$(N-5\sqrt{N}-8)/12$, we find that $N$ is at most~$422$.

Using the command \verb|J0(N).decomposition()| of the mathematics
package Sage for all \verb|N| less than $423$, we find that the odd
values of~$N$ with $J_0(N)$ split are the twenty-one odd integers that
appear as $n$ in the table.

To complete the proof, we note that if $J_0(N)$ is split then so is
$J_0(n)$ for every divisor $n$ of $N$.  Therefore the integers we are
searching for can be written $2^e n$ for some exponent $e$ and for some
$n$ among the odd values that we have just computed.  For each of the
possible odd parts $n$, we use Sage to compute the decomposition of
$J_0(2^e n)$ for increasing values of $e$ until we reach a Jacobian
that does not split.  (In practice, we do not have to compute the
decomposition of $J_0(2^e n)$ if we already know that $J_0(2^e m)$
does not split for some divisor $m$ of~$n$.  For example, since
$J_0(2^8)$ does not split we must have $\emax(n)<8$ for each $n$.)
The largest value of~$e$ for which $J_0(2^e n)$ splits is recorded
in the table as $\emax(n)$.
\end{proof}

\begin{remark}
Ekedahl and Serre~\cite{ES} give a list of various values of $g$ such
that there exists a curve of genus $g$ over $\QQ$ with a completely
split Jacobian.  Many of their values of $g$ come from modular
curves~$X_0(N)$.  The tables of modular forms that they had access to
did not include values of $N$ greater than $1000$, so they missed a few
of the values from Theorem~\ref{T:X0}.  The modular curves $X_0(1152)$
and $X_0(1200)$, of genus $161$ and $205$, respectively, allow us to
add two more values of $g$ to their
list~\cite{ES}*{Th\'eor\`eme, p.~509}.

Ekedahl and Serre also seem to have missed the curve $X_0(396)$ of
genus $61$, but they obtain a curve of genus $61$ with split Jacobian
by considering a quotient of $X_0(720)$ by an involution.
\end{remark}

\end{document}

config: arxiv


text:
\begin{figure}[!t]
\centering\hspace*{-1em}
\includegraphics[clip, trim=0 0 0 0, width=.96\textwidth]{figs/exp1_dim_k.png}
\caption{Computation of $\PCal_k^2(\hat{\mu},\hat{\nu})$ depending on the dimension $k \in [d]$ and $k^* \in \{2, 4, 7, 10\}$, where $\hat{\mu}$ and $\hat{\nu}$ stand for the empirical measures of $\mu$ and $\nu$ with 100 points. The solid and dash curves are the computation of $\PCal_k^2(\hat{\mu},\hat{\nu})$ with the RGAS and RAGAS algorithms, respectively. Each curve is the mean over 100 samples with shaded area covering the min and max values.}\label{fig:exp1_dim_k}
\end{figure}

\section{Experiments}\label{sec:experiment}
We conduct numerical experiments to evaluate the computation of the PRW distance by the RGAS and RAGAS algorithms. The baseline approaches include the computation of SRW distance with the Frank-Wolfe algorithm\footnote{Available in https://github.com/francoispierrepaty/SubspaceRobustWasserstein.}~\citep{Paty-2019-Subspace} and the computation of Wasserstein distance with the POT software package\footnote{Available in https://github.com/PythonOT/POT}~\citep{Flamary-2017-Pot}. For the RGAS and RAGAS algorithms, we set $\gamma = 0.01$ unless stated otherwise, $\beta = 0.8$ and $\alpha=10^{-6}$. For the experiments on the MNIST digits, we run the feature extractor pretrained in PyTorch 1.5. All the experiments are implemented in Python 3.7 with Numpy 1.18 on a ThinkPad X1 with an Intel Core i7-10710U (6 cores and 12 threads) and 16GB memory, equipped with Ubuntu 20.04.
\begin{figure}[!t]
\centering
\includegraphics[width=0.45\textwidth]{figs/exp1_hypercube_value_1.png}
\includegraphics[width=0.45\textwidth]{figs/exp1_hypercube_value_2.png}
\caption{Mean estimation error (left) and mean subspace estimation error (right), with varying number of points $n$. The shaded areas represent the 10\%-90\% and 25\%-75\% quantiles over 100 samples.}\label{fig:exp_cube_1}
\end{figure}
\begin{figure}[!t]
\centering
\includegraphics[clip, trim=10 10 10 10, width=0.32\textwidth]{figs/exp1_plan_W_100.png}
\includegraphics[clip, trim=10 10 10 10, width=0.32\textwidth]{figs/exp1_plan_SRW_100.png}
\includegraphics[clip, trim=10 10 10 10, width=0.32\textwidth]{figs/exp1_plan_PRW_100.png}
\includegraphics[clip, trim=10 10 10 10, width=0.32\textwidth]{figs/exp1_plan_W_250.png}
\includegraphics[clip, trim=10 10 10 10, width=0.32\textwidth]{figs/exp1_plan_SRW_250.png}
\includegraphics[clip, trim=10 10 10 10, width=0.32\textwidth]{figs/exp1_plan_PRW_250.png}
\caption{Fragmented hypercube with $(n, d) = (100, 30)$ (above) and $(n, d) = (250, 30)$ (bottom). Optimal mappings in the Wasserstein space (left), in the SRW space (middle) and the PRW space (right). Geodesics in the PRW space are robust to statistical noise.}
\label{fig:exp_cube_2}
\end{figure}
\paragraph{Fragmented hypercube.} We conduct our first experiment on the fragmented hypercube which is also used to evaluate the SRW distance~\citep{Paty-2019-Subspace} and FactoredOT~\citep{Forrow-2019-Statistical}. In particular, we consider $\mu = \UCal([-1,1]^d)$ which is an uniform distribution over an hypercube and $\nu = T_{\#} \mu$ which is the push-forward of $\mu$ under the map $T(x) = x + 2\sign(x)\odot(\sum_{k=1}^{k^*} e_k)$. Note that $\sign(\cdot)$ is taken element-wise, $k^* \in [d]$ and $(e_1, \ldots, e_d)$ is the canonical basis of $\br^d$. By the definition, $T$ divides $[-1,1]^d$ into four different hyper-rectangles, as well as serves as a subgradient of convex function. This together with Brenier's theorem (cf.\ \citet[Theorem~2.12]{Villani-2003-Topics}) implies that $T$ is an optimal transport map between $\mu$ and $\nu = T_{\#}\mu$ with $\WCal_2^2(\mu, \nu) = 4k^*$. Notice that the displacement vector $T(x) - x$ is optimal for any $x \in \br^d$ and always belongs to the $k^*$-dimensional subspace spanned by $\{e_j\}_{j \in [k^*]}$. Putting these pieces together yields that $\PCal_k^2(\mu, \nu) = 4k^*$ for any $k \geq k^*$.

Figure~\ref{fig:exp1_dim_k} presents the behavior of $\PCal_k^2(\widehat{\mu}, \widehat{\nu})$ as a function of $k^* \in \{2, 4, 7, 10\}$, where $\widehat{\mu}$ and $\widehat{\nu}$ are empirical distributions corresponding to $\mu$ and $\nu$, respectively. The sequence is concave and increases slowly after $k = k^*$, which makes sense since the last $d - k^*$ dimensions only represent noise. The rigorious argument for the SRW distance is presented in~\citet[Proposition~3]{Paty-2019-Subspace} but hard to be extended here since the PRW distance can not be characterized as a sum of eigenvalues.

Figure~\ref{fig:exp_cube_1} presents mean estimation error and mean subspace estimation error with varying number of points $n \in \{25, 50, 100, 250, 500, 1000\}$. In particular, $\widehat{U}$ is an approximate optimal subspace projection achieved by computing $\PCal_k^2(\widehat{\mu}, \widehat{\nu})$ with our algorithms and $\Omega^*$ is the optimal projection matrix onto the $k^*$-dimensional subspace spanned by $\{e_j\}_{j \in [k^*]}$. We set $k^*=2$ here and $\widehat{\mu}$ and $\hat{\nu}$ are constructed from $\mu$ and $\nu$ respectively with $n$ points each. The quality of solutions obtained by the RGAS and RAGAS algorithms are roughly the same.

Figure~\ref{fig:exp_cube_2} presents the optimal transport plan in the Wasserstein space (left), the optimal transport plan in the SRW space (middle), and the optimal transport plan in the PRW space (right) between $\widehat{\mu}$ and $\widehat{\nu}$. We consider two cases: $n = 100$ and $n = 250$, in our experiment and observe that our results are consistent with~\citet[Figure~5]{Paty-2019-Subspace}, showing that both PRW and SRW distances share important properties with the Wasserstein distance.

\paragraph{Robustness of $\PCal_k$ to noise.} We conduct our second experiment on the Gaussian distribution\footnote{~\citet{Paty-2019-Subspace} conducted this experiment with their projected supergradient ascent algorithm (cf.\ ~\citet[Algorithm 1]{Paty-2019-Subspace}) with the \textsc{emd} solver from the POT software package. For a fair comparison, we use Riemannian supergradient ascent algorithm (cf.\ Algorithm~\ref{alg:supergrad-simplex}) with the \textsc{emd} solver here; see Appendix for the details.}. In particular, we consider $\mu = \NCal(0, \Sigma_1)$ and $\nu = \NCal(0, \Sigma_2)$ where $\Sigma_1, \Sigma_2 \in \br^{d \times d}$ are positive semidefinite  matrices of rank $k^*$. This implies that either of the support of $\mu$ and $\nu$ is the $k^*$-dimensional subspace of $\br^d$. Even though the supports of $\mu$ and $\nu$ can be different, their union is included in a $2k^*$-dimensional subspace. Putting these pieces together yields that $\PCal_k^2(\mu, \nu) = \WCal_2^2(\mu, \nu)$ for any $k \geq 2k^*$. In our experiment, we set $d = 20$ and sample 100 independent couples of covariance matrices $(\Sigma_1, \Sigma_2)$, where each has independently a Wishart distribution with $k^* = 5$ degrees of freedom. Then we construct the empirical measures $\widehat{\mu}$ and $\widehat{\nu}$ by drawing $n = 100$ points from $\NCal(0, \Sigma_1)$ and $\NCal(0, \Sigma_2)$.

Figure~\ref{fig:exp_noise_1} presents the mean value of $\SCal_k^2(\widehat{\mu},\widehat{\nu})/\WCal_2^2(\widehat{\mu}, \widehat{\nu})$ (left) and $\PCal_k^2(\widehat{\mu},\widehat{\nu})/\WCal_2^2(\widehat{\mu}, \widehat{\nu})$ (right) over 100 samples with varying $k$. We plot the curves for both noise-free and noisy data, where white noise ($\NCal(0, I_d)$) was added to each data point. With moderate noise, the data is approximately on two $5$-dimensional subspaces and both the SRW and PRW distances do not vary too much. Our results are consistent with the SRW distance presented in~\citet[Figure~6]{Paty-2019-Subspace}, showing that the PRW distance is also robust to random perturbation of the data.
\begin{figure}[!t]
\centering
\includegraphics[clip, trim=0 0 20 0, width=0.45\textwidth]{figs/exp2_noise_srw.png}
\includegraphics[clip, trim=20 0 0 0, width=0.45\textwidth]{figs/exp2_noise_0.png}
\caption{Mean normalized SRW distance (left) and mean normalized PRW distance (right) as a function of dimension. The shaded area shows the 10\%-90\% and 25\%-75\% quantiles over the 100 samples.}\label{fig:exp_noise_1}
\end{figure}
\begin{figure}[!t]
\centering
\includegraphics[width=0.45\textwidth]{figs/exp2_noise_level.png}
\includegraphics[width=0.45\textwidth]{figs/exp4_computation_time.png}
\caption{(Left) Comparison of mean relative errors over 100 samples, depending on the noise level. The shaded areas show the min-max values and the 10\%-90\% quantiles; (Right) Comparisons of mean computation times on CPU. The shaded areas show the minimum and maximum values over 50 runs.}\label{fig:exp_noise_2}
\end{figure}

Figure~\ref{fig:exp_noise_2} (left) presents the comparison of mean relative errors over 100 samples as the noise level varies. In particular, we construct the empirical measures $\widehat{\mu}_\sigma$ and $\hat{\nu}_\sigma$ by gradually adding Gaussian noise $\sigma\NCal(0, I_d)$ to the points. The relative errors of the Wasserstein, SRW and PRW distances are defined the same as in~\citet[Section~6.3]{Paty-2019-Subspace}. For small noise level, the imprecision in the computation of the SRW distance adds to the error caused by the added noise, while the computation of the PRW distance with our algorithms is less sensitive to such noise. When the noise has the moderate to high variance, the PRW distance is the most robust to noise, followed by the SRW distance, both of which outperform the Wasserstein distance.

\begin{wrapfigure}{r}{0.5\textwidth}
\vspace*{-.5em}\includegraphics[width=0.45\textwidth]{figs/exp4_computation_time_lr.png}
\caption{Comparisons of mean computation time of the RGAS and RAGAS algorithms on CPU (log-log scale) for different learning rates. The shaded areas show the max-min values over 50 runs.}\label{fig:exp4_computation_time_lr_above}
\end{wrapfigure}

\paragraph{Computation time of algorithms.} We conduct our third experiment on the fragmented hypercube with dimension $d \in \{25, 50, 100, 250, 500\}$, subspace dimension $k=2$, number of points $n=100$ and threshold $\epsilon=0.001$. For the SRW and the PRW distances, the regularization parameter is set as $\eta = 0.2$ for $n < 250$ and $\eta = 0.5$ otherwise\footnote{Available in https://github.com/francoispierrepaty/SubspaceRobustWasserstein}, as well as the scaling for the matrix $C$ (cf. Definition~\ref{def:C}) is applied for stabilizing the algorithms. We stop the RGAS and RAGAS algorithms when $\|U_{t+1} - U_t\|_F/\|U_t\|_F \leq \epsilon$.

Figure~\ref{fig:exp_noise_2} (right) presents the mean computation time of the SRW distance with the Frank-Wolfe algorithm~\citep{Paty-2019-Subspace} and the PRW distance with our RGAS and RAGAS algorithms. Our approach is significantly faster since the complexity bound of their approach is quadratic in dimension $d$ while our methods are linear in dimension $d$.

\begin{figure}[!t]
\centering
\includegraphics[clip, trim=10 20 10 20, width=0.45\textwidth]{figs/exp4_computation_time_lr_0.png}
\includegraphics[clip, trim=20 10 10 20, width=0.45\textwidth]{figs/exp4_computation_time_lr_1.png}
\caption{Comparisons of mean computation time of the RGAS and RAGAS algorithms on CPU (log-log scale) for different learning rates. The shaded areas show the max-min values over 50 runs.}\label{fig:exp4_computation_time_lr_bottom}
\end{figure}
\paragraph{Robustness of algorithms to learning rate.} We conduct our fourth experiment on the fragmented hypercube to evaluate the robustness of our RGAS and RAGAGS algorithms by choosing the learning rate $\gamma \in \{0.01, 0.1\}$. The parameter setting is the same as that in the third experiment.

Figure~\ref{fig:exp4_computation_time_lr_above} indicates that the RAGAS algorithm is more robust than the RGAS algorithm as the learning rates varies, with smaller variance in computation time (seconds). This is the case especially when the dimension is large, showing the advantage of the adaptive strategies in practice.

To demonstrate the advantage of the adaptive strategies in practice, we initialize the learning rate using four options $\gamma \in \{0.005, 0.01, 0.05, 0.1\}$ and present the results for the RGAS and RAGAS algorithms separately in Figure~\ref{fig:exp4_computation_time_lr_bottom}. This is consistent with the results in Figure~\ref{fig:exp4_computation_time_lr_above} and supports that the RAGAS algorithm is more robust than the RGAS algorithm to the learning rate.
\begin{table}[!t]\small
\centering\hspace*{-3.5em}
\begin{tabular}{|c|ccccccc|} \hline
& D & G & I & KB1 & KB2 & TM & T \\ \hline
D & 0/0 & 0.184/0.126 & 0.185/0.135 & 0.195/0.153 & 0.202/0.162 & 0.186/0.134 & \textbf{0.170}/\textbf{0.105} \\ \hline
G & 0.184/0.126 & 0/0 & \textbf{0.172}/0.101 & 0.196/0.146 & 0.203/0.158 & 0.175/\textbf{0.095} & 0.184/0.128 \\ \hline
I & 0.185/0.135 & 0.172/0.101 & 0/0 & 0.195/0.155 & 0.203/0.166 & \textbf{0.169}/\textbf{0.099} & 0.180/0.134 \\ \hline
KB1 & 0.195/0.153 & 0.196/0.146 & 0.195/0.155 & 0/0 & \textbf{0.164}/\textbf{0.089} & 0.190/0.146 & 0.179/0.132 \\ \hline
KB2 & 0.202/0.162 & 0.203/0.158 & 0.203/0.166 & \textbf{0.164}/\textbf{0.089} & 0/0 & 0.193/0.155 & 0.180/0.138 \\ \hline
TM & 0.186/0.134 & 0.175/\textbf{0.095} & \textbf{0.169}/0.099 & 0.190/0.146 & 0.193/0.155 & 0/0 & 0.182/0.136 \\ \hline
T & \textbf{0.170}/\textbf{0.105} & 0.184/0.128 & 0.180/0.134 & 0.179/0.132 & 0.180/0.138 & 0.182/0.136 & 0/0 \\ \hline
\end{tabular}
\caption{Each entry is $\SCal_k^2/\PCal_k^2$ distance between different movie scripts. D = Dunkirk, G = Gravity, I = Interstellar, KB1 = Kill Bill Vol.1, KB2 = Kill Bill Vol.2, TM = The Martian, T = Titanic.}\label{tab:exp_cinema}
\end{table}
\begin{table}[!t]\small
\centering
\begin{tabular}{|c|cccccc|}\hline
& H5 & H & JC  & TMV & O & RJ \\ \hline
H5 & 0/0 & \textbf{0.222}/\textbf{0.155} & 0.230/0.163 & 0.228/0.166 & 0.227/0.170 & 0.311/0.272 \\ \hline
H & 0.222/0.155 & 0/0 & 0.224/0.163 & 0.221/0.159 & \textbf{0.220}/\textbf{0.153} & 0.323/0.264 \\ \hline
JC & 0.230/0.163 & 0.224/0.163 & 0/0 & 0.221/\textbf{0.156} & \textbf{0.219}/0.157 & 0.246/0.191 \\ \hline
TMV & 0.228/0.166 & 0.221/0.159 & \textbf{0.221}/0.156 & 0/0 & 0.222/\textbf{0.154} & 0.292/0.230 \\ \hline
O & 0.227/0.170 & 0.220/\textbf{0.153} & \textbf{0.219}/0.157 & 0.222/0.154 & 0/0 & 0.264/0.215 \\ \hline
RJ & 0.311/0.272 & 0.323/0.264 & \textbf{0.246}/\textbf{0.191} & 0.292/0.230 & 0.264/0.215 & 0/0 \\ \hline
\end{tabular}
\caption{Each entry is $\SCal_k^2/\PCal_k^2$ distance between different \sk plays. H5 = Henry V, H = Hamlet, JC = Julius Caesar, TMV = The Merchant of Venice, O = Othello, RJ = Romeo and Juliet.}\label{tab:exp_shakespeare}
\end{table}

\paragraph{Experiments on real data.} We compute the PRW and SRW distances between all pairs of items in a corpus of seven \textit{movie scripts}. Each script is tokenized to a list of words, which is transformed to a measure over $\br^{300}$ using \textsc{word2vec}~\citep{Mikolov-2018-Advances} where each weight is word frequency. The SRW and PRW distances between all pairs of movies are in Table~\ref{tab:exp_cinema}, which is consistent with the SRW distance in~\citet[Figure~9]{Paty-2019-Subspace} and demonstrate that the PRW distance is smaller than SRW distance. We also compute the SRW and PRW for a preprocessed corpus of eight Shakespeare operas. The PRW distance is consistently smaller than the corresponding SRW distance; see Table~\ref{tab:exp_shakespeare}. Figure~\ref{fig:exp_word_cloud} displays the projection of two measures associated with \textit{Dunkirk} versus \textit{Interstellar} (left) and \textit{Julius Caesar} versus \textit{The Merchant of Venice} (right) onto their optimal 2-dimensional projection.

To further show the versatility of SRW and PRW distances, we extract the features of different MNIST digits using a convolutional neural network (CNN) and compute the scaled SRW and PRW distances between all pairs of MNIST digits. In particular, we use an off-the-shelf PyTorch implementation\footnote{https://github.com/pytorch/examples/blob/master/mnist/main.py} and pretrain on MNIST with 98.6\% classification accuracy on the test set. We extract the 128-dimensional features of each digit from the penultimate layer of the CNN. Since the MNIST test set contains 1000 images per digit, each digit is associated with a measure over $\br^{128000}$. Then we compute the optimal 2-dimensional projection distance of measures associated with each pair of two digital classes and divide each distance by 1000; see Table~\ref{tab:MNIST} for the details. The minimum SRW and PRW distances in each row is highlighted to indicate its most similar digital class of that row, which coincides with our intuitions. For example, D1 is sometimes confused with D7 (0.58/0.47), while D4 is often confused with D9 (0.49/0.38) in scribbles.

\paragraph{Summary.} The PRW distance has less discriminative power than the SRW distance which is equivalent to the Wasserstein distance~\citep[Proposition~2]{Paty-2019-Subspace}. Such equivalence implies that the SRW distance suffers from the curse of dimensionality in theory. In contrast, the PRW distance has much better sample complexity than the SRW distance if the distributions satisfy the mild condition~\citep{Niles-2019-Estimation, Lin-2020-Projection}. Our empirical evaluation shows that the PRW distance is computationally favorable and more robust than the SRW and Wasserstein distance, when the noise has the moderate to high variance.
\begin{table}[!t]\small
\centering\hspace*{-6em}
\begin{tabular}{|c|cccccccccc|}
\hline
& D0 & D1 & D2 & D3 & D4 & D5 & D6 & D7 & D8 & D9 \\ \hline
D0 & 0/0 & 0.97/0.79 & \textbf{0.80}/\textbf{0.59} & 1.20/0.92 & 1.23/0.90 & 1.03/0.71 & 0.81/0.59 & 0.86/0.66 & 1.06/0.79 & 1.09/0.81 \\ \hline
D1 & 0.97/0.79 & 0/0 & 0.66/0.51 & 0.86/0.72 & 0.68/0.54 & 0.84/0.70 & 0.80/0.66 & \textbf{0.58}/\textbf{0.47} & 0.88/0.71 & 0.85/0.72 \\ \hline
D2 & 0.80/0.59 & \textbf{0.66}/\textbf{0.51} & 0/0 & 0.73/0.54 & 1.08/0.79 & 1.08/0.83 & 0.90/0.70 & 0.70/0.53 & 0.68/0.52 & 1.07/0.81 \\ \hline
D3 & 1.20/0.92 & 0.86/0.72 & 0.73/0.54 & 0/0 & 1.20/0.87 & \textbf{0.58}/\textbf{0.43} & 1.23/0.91 & 0.72/0.55 & 0.88/0.64 & 0.83/0.65 \\ \hline
D4 & 1.23/0.90 & 0.68/0.54 & 1.08/0.79 & 1.20/0.87 & 0/0 & 1.00/0.75 & 0.85/0.62 & 0.79/0.61 & 1.09/0.78 & \textbf{0.49}/\textbf{0.38} \\ \hline
D5 & 1.03/0.71 & 0.84/0.70 & 1.08/0.83 & \textbf{0.58}/\textbf{0.43} & 1.00/0.75 & 0/0 & 0.72/0.51 & 0.91/0.68 & 0.72/0.53 & 0.78/0.59 \\ \hline
D6 & 0.81/0.59 & 0.80/0.66 & 0.90/0.70 & 1.23/0.91 & 0.85/0.62 & \textbf{0.72}/\textbf{0.51} & 0/0 & 1.11/0.83 & 0.92/0.66 & 1.22/0.83 \\ \hline
D7 & 0.86/0.66 & \textbf{0.58}/0.47 & 0.70/0.53 & 0.72/0.55 & 0.79/0.61 & 0.91/0.68 & 1.11/0.83 & 0/0 & 1.07/0.78 & 0.62/\textbf{0.46} \\ \hline
D8 & 1.06/0.79 & 0.88/0.71 & \textbf{0.68}/\textbf{0.52} & 0.88/0.64 & 1.09/0.78 & 0.72/0.53 & 0.92/0.66 & 1.07/0.78 & 0/0 & 0.87/0.63 \\ \hline
D9 & 1.09/0.81 & 0.85/0.72 & 1.07/0.81 & 0.83/0.65 & \textbf{0.49}/\textbf{0.38} & 0.78/0.59 & 1.22/0.83 & 0.62/0.46 & 0.87/0.63 & 0/0 \\ \hline
\end{tabular}
\caption{Each entry is scaled $\SCal_k^2/\PCal_k^2$ distance between different hand-written digits.}\label{tab:MNIST}
\end{table}
\begin{figure}[!t]
\centering
\includegraphics[clip, trim=0 0 0 0, width=1\textwidth]{figs/word_clouds.pdf}
\caption{Optimal 2-dimensional projections between ``Dunkirk" and ``Interstellar" (left) and optimal 2-dimensional projections between ``Julius Caesar" and ``The Merchant of Venice" (right). Common words of two items are displayed in violet and the 30 most frequent words of each item are displayed.}\label{fig:exp_word_cloud}\vspace*{-.5em}
\end{figure}