text:
\begin{document}
\title{On the quaternion $\ell$-isogeny path problem}
\author{David Kohel, Kristin Lauter, Christophe Petit\thanks{ The third author is supported by an F.R.S.-FNRS postdoctoral research fellowship at Universit\'e catholique de Louvain, Louvain-la-Neuve.}, Jean-Pierre Tignol}

\institute{Institut de Math\'ematiques de Marseille,Microsoft Research,\\ Universit\'e catholique de Louvain,Universit\'e catholique de Louvain}

\maketitle

\begin{center}
\emph{To appear in the LMS Journal of Computation and Mathematics, as a special issue for ANTS (Algorithmic Number Theory Symposium) conference.}
\end{center}

\begin{abstract}
Let $\cO$ be a maximal order in a definite quaternion algebra over $\mathbb{Q}$
of prime discriminant $p$, and $\ell$ a small prime.
We describe a probabilistic algorithm, which for a
given left $\cO$-ideal, computes a representative in
its left ideal class of $\ell$-power norm.
In practice the algorithm is efficient, and subject to heuristics on expected distributions of primes,
runs in expected polynomial time.
This breaks the underlying problem for a quaternion
analog of the Charles-Goren-Lauter hash function, and
has security implications for the original
CGL construction in terms of supersingular elliptic
curves.
\end{abstract}

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

In this paper, we provide a probabilistic algorithm to solve a
quaternion ideal analog of the path problem in supersingular
$\ell$-isogeny graphs.
The main result is an algorithm for the following.  Let $\QA$
be a quaternion algebra over $\QQ$ ramified at $p$ and $\infty$. Let $\ell$ be a ``small'' prime, typically 2 or 3, or any small constant prime.
Given a maximal quaternion order $\cO$ in $\QA$ and a left
$\cO$-ideal $I$, compute an equivalent left $\cO$-ideal
$J = I\beta$ with norm $\ell^k$ for some~$k$.
This algorithm runs in practice in probabilistic polynomial time,
and this effective runtime follows from heuristic assumptions on expected
distributions of primes.
With minimal adaptation, the algorithm also applies to output an
ideal with smooth (or power-smooth) norm.
The algorithm is described in terms of a special maximal order,
but extends to any maximal order by passing through such a
special order.

The motivation for this problem is an explicit equivalence of
categories between left $\cO$-ideals and supersingular elliptic
curves (over $\bar{\FF}_p$). The Deuring correspondence gives
a bijection between such curves, up to Galois conjugacy, and
isomorphism classes of maximal orders in $\QA$.  This bijection
can be turned into an equivalence of categories by the following
construction.  Let $E_0/K$ be a fixed elliptic curve with
endomorphism ring $\cO = \End(E_0)$ a quaternion order in
$\QA = \cO \otimes \QQ$ (we may take the base field $K = \FF_{p^2}$
and $E_0$ such that $|E_0(K)| = (p+1)^2$).  Associated to any pair
$(E_1,\varphi)$ where $\varphi: E_0 \rightarrow E_1$ is an isogeny,
we obtain a left $\cO$-ideal $I = \mathrm{Hom}(E_1,E_0) \varphi$
of norm $n = \deg(\varphi)$
and conversely every left $\cO$-ideal arises in this way
(see Kohel~\cite[Section 5.3]{Kohel1996}).
In particular, given any isogeny $\psi: E_0 \rightarrow E_1$ of
degree $m$, the left $\cO$-ideal $J = I \hat{\varphi}\psi/n$ is
an equivalent ideal of norm $m$, where $\hat\psi$ is the dual of $\psi$.

The problem we address in this work is to solve the quaternion
version of the supersingular $\ell$-isogeny path problem: given
$E_0$, $E_1$ and a small prime $\ell$, find an $\ell$-power
isogeny from $E_0$ to $E_1$.  Under this equivalence of categories,
the analogous problem is the determination of a $\ell$-power norm
left $\cO$-ideal in the class of a given left $\cO$-ideal $I$.
After introducing the necessary background on quaternion orders and ideals
in Section~\ref{sec:quaternions} and addressing some preliminary algorithmic problems in Sections~\ref{sec:prel}, we solve the $\ell$-power norm problem in Section~\ref{sec:ideals:ellpow}.  Subject to reasonable heuristics on
the probability of finding suitable primes, we obtain a probabilistic
algorithm which solves this problem in expected polynomial time.
The experimental runtime agrees with the most optimistic
predictions for the distribution of primes.

The algorithm gives a clear distinction between the efficiency
of the $\ell$-isogeny problem in the equivalent category of
quaternion ideals, whereas the analogous problem in the category
of supersingular elliptic curves, on which the security of the
Charles, Goren and Lauter hash function~\cite{Charles2009} is
based, has to date resisted attack.  This dichotomy poses
several questions on the extent to which the information from
the algebraic category can be transported to the geometric one.
In particular, one expects an algorithm for computing the
endomorphism ring of a given elliptic curve to provide an
effective reduction to the algebraic setting, making the
hardness of this problem critical to the underlying security.

\section{The quaternion $\ell$-isogeny path problem}
\label{sec:quaternions}

In this section, we first motivate and define the quaternion $\ell$-isogeny path problem.
We then recall basic facts on quaternion algebras. We introduce \emph{$p$-extremal} maximal orders, which will play an important role in our solution of the quaternion $\ell$-isogeny problem.
We finally discuss properties of reduced norms and ideal morphisms.

\subsection{``Hard'' isogeny problems}

\label{sec:intro:hard}

The motivation for studying the quaternion $\ell$-isogeny problem
is based on the analogous (indeed categorically equivalent) problem
for supersingular elliptic curves.
The difficulty of this problem for elliptic curves underlies
the security of the Charles, Goren and Lauter hash
function~\cite{Charles2009}.

As an example, finding a preimage (inverting the function) amounts
to solving the following path problem in the supersingular
$\ell$-isogeny graph:
\begin{Problem}\label{prob:preim}
Let $p$ and $\ell$ be prime numbers, $p\neq\ell$. Let $E_0$ and $E_1$
be two supersingular elliptic curves over $\FF_{p^2}$ with
$|E_0(\FF_{p^2})|=|E_1(\FF_{p^2})|=(p+1)^2$.
Find $k\in\mathbb{N}$ and an isogeny of degree $\ell^k$ from $E_0$ to $E_1$.
\end{Problem}
Similarly, finding collisions requires a solution to the following
multiple path problem in the supersingular $\ell$-isogeny graph:
\begin{Problem}\label{prob:coll}
Let $p$ and $\ell$ be prime numbers, $p\neq\ell$. Let $E_0$ be
a supersingular elliptic curve over $\FF_{p^2}$.
Find $k_1,k_2\in\mathbb{N}$, a supersingular elliptic curve
$E_1$ and two distinct isogenies (i.e.~with distinct kernels)
of degrees respectively $\ell^{k_1}$ and $\ell^{k_2}$ from $E_0$
to $E_1$.
\end{Problem}

\begin{comment}
\color{blue}
I think we can omit the remaining problems for now.
\color{red}
\begin{Problem}\label{prob:cycle}
Let $p$ and $\ell$ be prime numbers, $p\neq\ell$. Let $E_0$ be a supersingular elliptic curve over $\FF_{p^2}$. Find $k\in\mathbb{N}$ and a non trivial endomorphism of $E_0$ with degree $\ell^{k}$.
\end{Problem}

Even without the degree condition, finding non trivial endomorphisms of elliptic curves is a challenging task in general (by trivial endomorphism we mean the multiplications by constants).
\begin{Problem}\label{prob:endo}
Let $p$ be a prime number. Let $E_0$ be a supersingular elliptic curve over $\FF_{p^2}$. Find a non trivial endomorphism of $E_0$.
\end{Problem}
The endomorphism ring of an elliptic curve defined over a finite field is either an order in a  quadratic imaginary number field (in the ordinary case) or a maximal order in a quaternion algebra (in the supersingular case).
Any four linearly independent endomorphisms of a supersingular elliptic curve define a subring of its endomorphism ring. The endomorphism ring problem was first considered by Kohel in his thesis~\cite{Kohel1996}.

\begin{Problem}\label{prob:endoring}
Let $p$ be a prime number and let $E_0$ be an elliptic curve over $\FF_{p^2}$. Compute the endomorphism ring of $E_0$.
\end{Problem}

By computing the endomorphism ring, we mean finding an expression for two (in the ordinary case) or four (in the supersingular case) maps that generate it.

In the ordinary case, the endomorphism ring can be computed in subexponential time~\cite{Jao2010,Bisson2009}. In the supersingular case , Kohel's algorithm~\cite{Kohel1996} essentially finds solutions to Problem~\ref{prob:cycle} by reconstructing Mestre-Oesterl\'e's graphs.
The time complexity of this approach can be reduced to $\bigO(p^{1/2+\epsilon})$ using birthday paradox heuristics~\cite{Galbraith1999}, but it is exponential in nature.
Given a couple of solutions to Problem~\ref{prob:cycle}, a suborder of the endomorphism ring can be deduced, and this is sufficient in some cases to determine the whole endomorphism ring (see Kohel~\cite[Chapter~7]{Kohel1996}).
\color{black}
\end{comment}

Setting $\cO = \End(E_0)$, we have a category of left $\cO$-ideals,
with morphisms $I \rightarrow I\alpha \subseteq J$, for $\alpha$ in
$B = \cO \otimes \QQ$, which is equivalent to the category of
supersingular elliptic curves and isogenies.
The analog of the path problem in supersingular $\ell$-isogeny graphs
is that of finding a representative ideal $J$ for given $I$ of norm
$\ell^k$. We call this problem the \emph{quaternion $\ell$-isogeny path
problem}, and focus on
its effective solution in this article.

\subsection{Quaternion algebras\label{sec:intro:QA}}

In this work we consider the structure of left ideals of a maximal order
in the quaternion algebra $B_{p,\infty}$ ramified only at $p$ and $\infty$.
Such an algebra is isomorphic to $\End(E) \otimes \QQ$ for any supersingular
elliptic curve $E/\FF_{p^2}$. Here we denote $\End(E) = \End_{\bar{\FF}_p}(E)$
and if we assume $\#E(\FF_{p^2}) = (p+1)^2$, then the full endomorphism
ring $\End(E)$ is defined over $\FF_{p^2}$.
Any definite quaternion algebra over $\QQ$ has a presentation of the form
$\QQ\langle{i,j}\rangle$, where $i^2 = a$, $j^2 = b$, $k = ij = -ji$ for
negative integers $a,b$.  The canonical involution on $B_{p,\infty}$ is
given by
$$
\alpha = x_0 + x_1 i + x_2 j + x_3 k \longmapsto
\bar{\alpha} = x_0 - x_1 i - x_2 j - x_3 k.
$$
from which the reduced trace and norm take the form
$$
\Tr(\alpha) = \alpha + \bar{\alpha} = 2x_0
\mbox{ and }
\Nr(\alpha) = \alpha \bar{\alpha} = x_0^2 - a x_1^2 - b x_2^2 + ab x_3^2.
$$
The integral basis $\{1,i,j,k\}$ has the nice property of being
an orthogonal basis with respect to the bilinear form
$\langle{x,y}\rangle = \Nr(x + y) - \Nr(x) - \Nr(y)$
associated to the reduced norm.
Nevertheless, the order $\cO = \ZZ\langle{i,j}\rangle$
is never maximal.

\subsection{Extremal orders\label{sec:prob:extremal}}

In this work we first place the focus on the {\it $p$-extremal} maximal
orders $\cO$ containing $\pi$ such that $\pi^2 = -p$. For a general
order there exists a unique maximal $2$-sided ideal $\mathfrak{P}$
over $p$, and this ideal is principal if and only if there exists such
an element $\pi$.
The maximal ideal $\mathfrak{P}$ is a generator of the $2$-sided class
group, and $p$-extremal orders are precisely those of trivial $2$-sided
class number.  In the context of supersingular elliptic curves, these
are the maximal orders which are endomorphism rings of elliptic curves
defined over $\FF_p$ with Frobenius endomorphism~$\pi$.

Secondly, we focus on orders with distinguished quadratic subring $R$.
For a maximal order $\cO$ we define
$
d(\cO) = \min\{ \disc(R) : \ZZ \ne R \subsetneq \cO \}.
$
Among all $p$-extremal maximal quaternion orders, we define
a {\it special} $p$-extremal maximal order $\cO$ to be a
$p$-extremal maximal order such that $d(\cO)$ is minimal.

The following lemma establishes the main properties we need for such an
order, after which Lemmas~\ref{lem:disc-4}, \ref{lem:disc-8},
and~\ref{lem:disc-q} provide for their existence by explicit construction.

\begin{Lemma}
\label{lem:special-p-extremal-properties}
Let $\cO$ be a maximal order in $B_{p,\infty}$ containing a subring
$\ZZ\langle{i,j}\rangle$ with $i^2=-q$, $j^2=-p$, and $ij = -ji$,
for $q$ coprime to $p$.
Set $R = \cO \cap \QQ[i]$ and let $D$ be its discriminant.
If $R$ is the ring of integers of $\QQ[i]$, then $R^\perp = Rj$ and
$R + Rj$ is a suborder of index $|D|$ in $\cO$.
If $\omega$ is a generator of $R$, then
$$
\Nr(x_1 + y_1\omega + (x_2 + y_2\omega)j) = f(x_1,y_1) + p f(x_2,y_2),
$$
where $f(x,y)$ is a principal quadratic form of discriminant $D$.
\end{Lemma}

\begin{proof}
The triviality of the trace of $j$ and the anti-commuting relation
$ij = -ji$ imply that $\QQ(i)$ has orthogonal complement $\QQ(i)j$
in $B_{p,\infty}$. Consequently $R^\perp \subset \cO$ is a lattice
in $\QQ(i)j$ containing $Rj$, hence of the form $\mathfrak{a}j$ for
a fractional ideal $\mathfrak{a}$ of $R$ which contains $R$.
The prime $p$ is inert in $R$, since $p$ is ramified in $B_{p,\infty}$
but not in $R$.
Since the norm is integral on $\mathfrak{a}j$, and $\Nr(j) = p$,
it follows that $\mathfrak{a}$ is integral, hence equals $R$.
The orthogonality of $R$ and $Rj$ implies that
$j\beta = \bar{\beta}j$ for all $\beta$ in $R$, so $jR = Rj$
and $R + Rj$ is closed under multiplication.
The form of the norm follows from orthogonality and
multiplicativity of the norm: $\Nr(\beta_1 + \beta_2j)
= \Nr(\beta_1) + p \Nr(\beta_2)$.  Consequently the
discriminant of the norm form is $D^2 p^2$, from which
we conclude that $R + Rj$ has index $|D|$ in any
maximal order.
\end{proof}

By convention, for our special $p$-extremal order $\cO$, we
fix $\ZZ[i] \subseteq R$ with $i^2 = -q$ and $D = \disc(R)
= -d(\cO)$, and $j^2 = -p$ (i.e.~$j = \pi$ above). Being
of smallest discriminant, $R$ is necessarily a maximal order
whose discriminant is the first of the sequence
$$
-3, -4, -7, -8, -q \text{ for prime } q \equiv 3 \bmod 4,
$$
such that $p$ is ramified or inert in $R$.
The next three lemmas establish existence for $q = 1$, $q = 2$,
and $q \equiv 3 \bmod 4$ prime.
These lemmas incorporate and expand on Propositions~5.1 and~5.2
of Pizer~\cite{Pizer1980}. We recall that an order in
a quaternion algebra is {\it Eichler} if it is the intersection
of two maximal orders.

\begin{Lemma}
\label{lem:disc-4}
Let $p \equiv 3 \bmod 4$ be a prime, and let $B = \QQ\langle{i,j}\rangle$
be the quaternion algebra given by the presentation $i^2 = -1$, $j^2 = -p$,
and $k = ij = -ji$, and set $R = \ZZ[i]$. Then $B$ is ramified only at $p$
and $\infty$, and $\ZZ\langle{i,j}\rangle$ is contained in exactly two
maximal orders with index $4$, described by the inclusion chains:
$$
\ZZ\langle{i,j}\rangle
  \subsetneq \ZZ\langle{i,\frac{1+i+j+k}{2}}\rangle
  \subsetneq
  \left\{
  \begin{array}{l}
  \dsp \ZZ\langle{i,\frac{1+j}{2}}\rangle\ccomma\\[2.5mm]
  \dsp \ZZ\langle{i,\frac{1+k}{2}}\rangle\cdot
  \end{array}
  \right.
$$
In particular $\ZZ\langle{i,(1+i+j+k)/2}\rangle$ is an Eichler order, but
$\ZZ\langle{i,j}\rangle$ is not.
\end{Lemma}

\begin{Lemma}
\label{lem:disc-8}
Let $p \equiv 5 \bmod 8$ be a prime, and let $B = \QQ\langle{i,j}\rangle$
be the quaternion algebra given by the presentation $i^2 = -2$, $j^2 = -p$,
and $k = ij = -ji$, and set $R = \ZZ[i]$. Then $B$ is ramified only at $p$
and $\infty$, and $\ZZ\langle{i,j}\rangle$ is contained in exactly two
maximal orders with index $8$, described by the inclusion chains:
$$
\ZZ\langle{i,j}\rangle
  \subsetneq \ZZ\langle{i,j,\frac{i+k}{2}}\rangle
  \subsetneq \ZZ\langle{i,\frac{i+k}{2},\frac{1+j+k}{2}}\rangle
  \subsetneq
  \left\{
  \begin{array}{l}
  \dsp \ZZ\langle{i,\frac{1+j+k}{2},\frac{i+2j+k}{4}}\rangle\ccomma\\[2.5mm]
  \dsp \ZZ\langle{i,\frac{1+j+k}{2},\frac{i+2j-k}{4}}\rangle\cdot
  \end{array}
  \right.
$$
In particular $\ZZ\langle{i,j}\rangle$ is not an Eichler order.
\end{Lemma}

\begin{Lemma}
\label{lem:disc-q}
Let $p$ and $q$ be primes, with
$p \equiv 1 \bmod 4$,
$q \equiv 3 \bmod 4$, and
$$
\kro{-p}{q} = 1.
$$
Let $B = \QQ\langle{i,j}\rangle$ be the quaternion algebra given
by the relations $i^2 = -q$, $j^2 = -p$, and $k = ij = -ji$,
and set $R = \ZZ[(1+i)/2]$. Then $B$ is ramified only at $p$
and $\infty$, and $\ZZ\langle{(1+i)/2,j}\rangle = R + Rj$ is
contained in exactly two maximal orders with index $q$, described
by the inclusion chains:
$$
\ZZ\langle{(1+i)/2,j}\rangle
  \subsetneq
  \left\{
  \begin{array}{l}
  \dsp \ZZ\langle{\frac{1+i}{2}\ccomma\, j\,\ccomma\frac{ci+k}{q}}\rangle\ccomma\\[2.5mm]
  \dsp \ZZ\langle{\frac{1+i}{2}\ccomma\, j\,\ccomma\frac{ci-k}{q}}\rangle\ccomma
  \end{array}
  \right.
$$
where $c$ is any root of $x^2 + p \bmod q$. In particular $R + Rj$
is an Eichler order.
\end{Lemma}

Under the generalized Riemann hypothesis, for $p \equiv 1 \bmod 4$,
the smallest $q$ satisfying the conditions of the last lemma is
$O(\log(p)^2)$ by a result of Ankeny~\cite{Ankeny1952} (or explicitly
$q < 2\log(p)^2$ by Bach~\cite{Bach1990}).
In the remainder of this paper, we will assume that $\QA$, $\cO$,
and $R$ are suitably constructed from these
lemmas with $\disc(R)$ the minimal discriminant in which $p$ is inert
in the sequence $-3$, $-4$, $-7$, $-8$, or $-q$ for $q \equiv 3 \bmod 4$
prime.

\subsection{Reduced norms and ideal morphisms}
\label{sec:ideals:properties}

Now suppose that $\cO$ is any maximal order.
We recall that the reduced norm on $\QA$ induces a reduced norm
on left ideals defined by any of the equivalent conditions
$$
\Nr(I) :=  \sqrt{|\cO/I|}
= \gcd\left(\{\, \Nr(\alpha) \;:\; \alpha \in I \,\}\right),
$$
or by $I\bar{I} = \Nr(I)\cO$.  It follows that the
reduced norm on ideals is multiplicative
and compatible with the reduced norm on elements $\Nr(\alpha) =
\Nr(\alpha\cO) = \Nr(\cO\alpha)$.
If $I$ and $J$ are left $\cO$-ideals, a homomorphism of $I$ to $J$
is a map given by $\alpha \mapsto \alpha\gamma$ for $\gamma$ in
$\QA^*$, which is an isomorphism if $J = I\gamma$.
By the multiplicativity of the reduced norm, isomorphisms
are similitudes of quadratic modules (with respect to the
reduced norm).  In particular, an isomorphism sends a
reduced basis to a reduced basis. In fact the normalized
norm map
$$
q_I = \frac{\Nr}{\Nr(I)} : I \longrightarrow \ZZ
$$
remains invariant under this isomorphism, in the sense that $q_I(\alpha)
= q_J(\beta)$ for $\alpha$ in $I$ and $\beta = \alpha\gamma$ in $J$.
The normalized norm $q_I$ is a positive-definite integral quadratic map,
whose bilinear module given by
$
\langle{x,y}\rangle = q_I(x+y) - q_I(x) - q_I(y)
$
has determinant $p^2$. This follows from the same property for any maximal order
(see Pizer~\cite[Proposition~1.1]{Pizer1980}), since $|\cO/I| = \Nr(I)^2$,
and the fact that any submodule of index $m$ in a quadratic module $L$
has determinant $m^2\det(L)$.

The following lemma serves to replace an ideal $I$ with an isomorphic
one of different reduced norm.

\begin{Lemma}
\label{lem:ideal_norm_rep}
Let $I$ be a left $\cO$-ideal of reduced norm $N$ and $\alpha$
an element of $I$.
Then $I\gamma$, where $\gamma = \bar{\alpha}/N$, is a left
$\cO$-ideal of norm $q_I(\alpha)$.
\end{Lemma}

\begin{proof}
By the multiplicativity of the reduced norm, and $\Nr(\alpha) = \Nr(\bar{\alpha})$,
we have
$$
\Nr(I\gamma) = \Nr(I)\Nr(\gamma)
= N\frac{\Nr(\alpha)}{N^2} = \frac{\Nr(\alpha)}{N} = q_I(\alpha).
$$
Clearly $I$ is a fractional left $\cO$-ideal, so it remains
to show that $I\gamma \subseteq \cO$.
Since $\cO\alpha \subseteq I$, we have $\bar{\alpha} \subseteq \bar{I}$,
and hence $I\bar{\alpha} \subseteq I\bar{I} = N\cO$, from which
$I\gamma \subseteq \cO$ follows.
\end{proof}

\section{Preliminary algorithmic results\label{sec:prel}}

In this section, we provide two algorithmic tools that will be used to solve the quaternion $\ell$-isogeny path problem in Section~\ref{sec:ideals:ellpow}. The first algorithm computes prime norm representatives in ideal classes. The second one computes representations of integers by the norm form of a $p$-extremal order.

\subsection{Computing prime norm representatives in ideal classes}
\label{sec:ideals:prime}

Given a maximal order $\cO$ and a left $\cO$-ideal $I$, we

give a probabilistic
algorithm that computes another left $\cO$-ideal $J = I\gamma$
in the same class, but with prime norm.

Using Lemma~\ref{lem:ideal_norm_rep}, this problem reduces to the  problem of finding a prime represented by $q_I$.
\vspace{2mm}

\begin{comment}
Let $\Phi(x)$ be a monotone function.  We would like to have
sufficiently many primes in $[x,x+\Phi(x)]$, namely
$$
\frac{\pi(x+\Phi(x)) - \pi(x)}{\Phi(x)} \sim \frac{1}{\log(x)}.
$$
Unfortunately, such a hypothesis is known to be false~\cite{Maier1985}
for $\Phi(x)$ any function in $O(\log(x)^n)$.
On the other hand Selberg~\cite{Selberg1943} showed that if the Riemann
hypothesis holds, then this hypothesis is satisfied for almost all $x$
(outside some set $E$ such that $[0,x) \cap E$ is in $o(x)$) if
$$
\lim_{x \rightarrow \infty} \frac{\Phi(x)}{(\log(x))^2} = \infty.
$$
This is much better than the known worst case bounds for all $x$.
The best known bounding function is $\Phi(x) = x^{1/2 + \epsilon}$
conditional on the Riemann hypothesis and $\Phi(x) = x^{7/12 + \epsilon}$
without unproven hypotheses~\cite{Heath-Brown1989}.

In Section~\ref{sec:repns_in_orders}, we will need a stronger
hypothesis on primes in arithmetic progressions
$a \pm p\,[x,x+\Phi(a+px)]$. Since $p$ is large, a larger
$\Phi(a+px)$ is needed to prove the existence of a large density
of primes in the arithmetic progression.
Nevertheless, on average the same considerations apply, and we
adapt our algorithm to allow for $a$ to vary in order to avoid
arithmetic progressions which are potentially sparsely populated
with primes.
\end{comment}

\noindent{\bf Prime norm algorithm.}
Given a left $\cO$-ideal $I$ of norm $N$, with a Minkowski-reduced basis
$\{\alpha_1,\alpha_2,\alpha_3,\alpha_4\}$.
Generate random elements $\alpha = \sum_i x_i \alpha_i$ with
$(x_1,x_2,x_3,x_4)$ in a box $[-m,m]^4$ until finding an element $\alpha$
of $I$ with $q_I(\alpha)$ prime, and return $I(\bar{\alpha}/N)$.
\vspace{2mm}

Assuming that numbers represented by $q_I$ behave like random
numbers, it remains to ensure that $q_I([-m,m]^4)$ contains
sufficiently many primes to have a high probability of finding
one.
If $\{\alpha_1,\alpha_2,\alpha_3,\alpha_4\}$ is a Minkowski-reduced
basis, the $q_I(\alpha_i)$ attain the successive minima, and we
have the bounds
$$
p^2 \le 16 q_I(\alpha_1) q_I(\alpha_2) q_I(\alpha_3) q_I(\alpha_4) \le 4 p^2,
$$
where $q_I(\alpha_i) \le q_I(\alpha_{i+1})$. For a generic ideal
$I$ we expect $q_I(\alpha_4)$ to be in $\tilde{\bigO}(\sqrt{p})$.
In the worst case, $q_I(\alpha_4)$ is in $\tilde{\bigO}(p)$ when
$I$ equals an order $\cO$ containing a subring $R$ with $|\disc(R)|$
in $O(\log(p)^n)$.
Assuming $I$ is generic, we expect to find $\alpha$ with
$q_I(\alpha)$ in $\tilde{\bigO}(m^2 \sqrt{p})$.

In practice, we find sufficiently many primes $q_I(\alpha)$ for
$m$ which grows polynomially in $\log(p)$.
However to provably terminate, even under the GRH, it may be
necessary to allow $m$ to exceed a function in $O(\sqrt[4]{p})$, in which case the output may exceed $O(p)$.

We implemented a prime norm algorithm in Magma~\cite{Magma}.
We tested it on ideals of $\ell$-power norms generated via
a random walk from a given maximal order.
All our computations with primes of up to 200 bits and
random ideals took seconds on an Intel Xeon CPU X5500
processor with 24 GB RAM running at 2.67GHz.
The norms of the output ideals $J$ were experimentally only
slightly larger than $\sqrt{p}$.
The experimental results are given in Appendix~\ref{sec:primeres}.

\subsection{Representing integers by special orders}
\label{sec:repns_in_orders}

We also consider the problem of representing a sufficiently
large positive integer $M$ by the norm form of $\cO$.  Suppose that
$\cO$ is a $p$-extremal order, with suborder $R + Rj$, and
let $D = \disc(R)$.  We let $\Phi(x)$ be a monotone function such
that a suitable interval $[x,x+\Phi(x)]$ contains
sufficiently many primes,
and we assume that $M \ge p\,\Phi(M)$.
If $\omega$ is a reduced generator of $R$ (of trace $0$ or $\pm 1$),
then the norm form on $R + Rj$ is of the form
$$
\Nr(\alpha + \beta j) = f(x_1,y_1) + p f(x_2,y_2),
$$
where $\alpha = x_1 + y_1 \omega$ and $\beta = x_2 + y_2 \omega$, and
$f(x,y)$ is a principal form. For $(x,y)$ in $[-m,m]^2$ with
$m = \lfloor\sqrt{\Phi(M)/|D|}\rfloor$, we have $f(x,y) < \Phi(M)$
and $\Nr(\beta j) < p\,\Phi(M) < M$.

This gives the following algorithm on which we build our strong
approximation algorithm.
\vspace{2mm}

\noindent{\bf Integer representation.}
Given an integer $M \ge p\,\Phi(M)$.
Set $m = \lfloor\sqrt{\Phi(M)/|D|}\rfloor$, and choose
$(x_2,y_2)$ at random in $[-m,m]^2$ until finding a prime
$r = M - p f(x_2,y_2)$ which is split in $R$ and for which
a prime $\mathfrak{r}$ over $r$ is principal.
Let $\alpha = x_1 + y_1 \omega$ be a generator for $\mathfrak{r}$,
set $\beta = x_2 + y_2 \omega$, and return $\alpha + \beta j$.
\vspace{2mm}

Clearly the output has norm $M$. We assume that primes have density
$1/\log(M)$ in the arithmetic progression $M - p\,[0,\Phi(M)]$.
Moreover we assume that such primes are equidistributed among
primes which are non-split and split in $R$ and, in the latter
case, among each of the $h(R)$ ideal classes of $R$.
Finally, we must assume that elements $\beta = x_2 + y_2 \omega$
give rise to integers $r = M - p\,\Nr(\beta)$ with the same primality probabilities as random integers in the range
$M - p\,[0,\Phi(M)]$.
Under such heuristic assumptions, the expected number of random
$\beta$ to be tested is $2 h(R) \log(M)$.
Detecting a prime~$r$, solving for a representative prime $\mathfrak{r}$
over $r$, and determination of a principal generator can be done
in expected polynomial time by Cornaccia's algorithm~\cite{Cornacchia1903}.

Under the heuristic assumptions made above, we can appeal to average
distributions among all arithmetic progressions $a - p\,[0,\Phi(M)]$,
for representatives $a$ of $(\ZZ/p\ZZ)^*$. In the application that
follows, $M$ will be of the form $\ell^e$ or $N\ell^e$, and we can
adapt to failure to find primes in a particular arithmetic progression
sparsely populated with primes by changing~$e$.

\section{Main algorithm}
\label{sec:ideals:ellpow}

In this section, we provide an algorithm to solve the quaternion $\ell$-isogeny path problem. We also sketch a generalization of our approach to build ideal class representatives with powersmooth norms.

\subsection{Overview of the algorithm}
\label{sec:algorithm_overview}

We reduce the quaternion $\ell$-isogeny problem to a restricted version of the same problem, where we assume that $\cO$ is a special $p$-extremal maximal order
with suborder $R + Rj$  as defined in Section~\ref{sec:intro:QA}. We also assume that $I$ is a left $\cO$-ideal with reduced norm $N$, where $N$ is a (large) prime coprime to $\ell$, $|\disc(R)|$ and $p$.

 A reduction from generic left $\cO$-ideals to left $\cO$-ideals with the required norms can be effectively performed with the algorithm of Section~\ref{sec:ideals:prime}.

A reduction from general maximal orders to special $p$-extremal orders will be provided in Section~\ref{sec:ideals:gen}.

Using Lemma~\ref{lem:ideal_norm_rep}, the quaternion $\ell$-isogeny path problem is also reduced to an effective strong approximation theorem in Section~\ref{sec:ideals:strongapproximation}. In particular if the ideal is given by a pair of generators $I = \cO(N,\alpha)$, the quaternion $\ell$-isogeny path problem is reduced  to finding $\lambda \in \ZZ$ coprime to $N$ and
$$
\beta \equiv \lambda\alpha \bmod N\cO
$$
with $\Nr(\beta) = N\ell^e$ for some positive integer~$e$.

Sections~\ref{sec:ideals:ellpow:isom}, \ref{sec:ideals:ellpow:lift}, and~\ref{sec:ideals:ellpow:results} describe the core of our approach to solve this problem.

Since the index of $R + Rj$ in $\cO$ is coprime to $N$, we
have an isomorphism
$$
\frac{R + Rj}{N(R + Rj)} \cong \frac{\cO}{N\cO}\cdot
$$
We can therefore choose representative elements in $R + Rj$
as convenient to simplify the algorithm. Since the index
$[\cO:R + Rj] = |\disc(R)|$ is assumed to be small (in $O(\log(p)^2)$ under the GRH), the size of the output might be slightly
larger, but the distinction is asymptotically insignificant.

A direct approach to the strong approximation problem
to solve for $\beta$ seems daunting, so instead we reduce
to the following steps:

\begin{enumerate}
\item
Solve for a random $\gamma \in \cO$ of reduced norm $N\ell^{e_0}$.
\item
Solve for $[\mu]$ in $(\cO/N\cO)^*$ such that $(\cO\gamma/N\cO)[\mu] = I/N\cO$.
\item
Solve for the strong approximation of $[\mu]$ (modulo $N$)
by $\mu$ in $\cO$ of reduced norm $\ell^{e_1}$.
\end{enumerate}

Here we denote the element $\mu + N\cO$ of $\cO/N\cO$ by $[\mu]$
to distinguish it from the conjugate $\bar{\mu}$ of $\mu $.
The output $\beta = \gamma\mu$ is then an element of $I$ with
reduced norm $N\ell^e$ where $e = e_0+e_1$.

The element $\gamma$ can be constructed with the algorithm of
Section~\ref{sec:repns_in_orders}. We solve
for $[\mu]$ by linear algebra in Section~\ref{sec:ideals:ellpow:isom}, showing that we can take
$[\mu]$ in $(R/NR)^*[j] \subseteq (\cO/N\cO)^*$.
The core of the algorithm is the final specialized strong
approximation algorithm of Section~\ref{sec:ideals:ellpow:lift},
taking $[\mu]$ in $(R/NR)^*[j]$ and constructing the lifting
$\mu$ of norm $\ell^e$.

The whole algorithm for $p$-extremal orders is analyzed in Section~\ref{sec:ideals:ellpow:results}.

As mentioned above, we finally remove the $p$-extremal condition in Section~\ref{sec:ideals:gen} by providing a reduction from the general case to the case of $p$-extremal orders, and we generalize our approach to compute ideal representatives of smooth or powersmooth norms in Section~\ref{sec:ideals:psmooth}.

\subsection{Effective strong approximation\label{sec:ideals:strongapproximation}}

Let $B := B_{p,\infty}$ be the quaternion algebra ramified at $p$ and $\infty$.
Let $\AA_\QQ$ be the rational ad\`ele ring, defined as the restricted
product of $\QQ_v$ with respect to $\ZZ_v$, let $\ell \ne p$ be a
``small'' prime, and let $\AA_{\QQ,\ell}$ be the restricted product
over all $v \ne \ell$.
Let $\AA_B = B \otimes_\QQ \AA_\QQ$ be the ad\`ele ring of $B$,
and $\AA_{B,\ell} = B \otimes \AA_{\QQ,\ell}$.
Then $B$ embeds diagonally in $\AA_B$ and is discrete in
$\AA_B$ (see~\cite[Section 14]{Cassels1967}). The strong
approximation theorem (see~\cite[Section 15]{Cassels1967})
asserts that $B$ is dense in $\AA_{B,\ell}$ (see also
Th\'eor\`eme Fondamental 1.4, p.~61 of Vign\'eras~\cite{Vigneras1980}).

The strong approximation theorem can be viewed as a strong version
of the Chinese remainder theorem.  We apply this to find an element
of a left $\cO$-ideal $I$ which generates $I$ almost everywhere.
Each such ideal is known to be generated by two elements $N$ and
$\alpha$, where we may take $N = \Nr(I)$ for the first generator.
This follows since locally $\cO_v = \cO \otimes \ZZ_v$ is a left
principal ideal ring, hence so is the quotient $\cO/N\cO$.

If $I = \cO(N,\alpha):=\cO N+\cO\alpha$, the approximation theorem
implies that we can find $\beta$ in $I$ such that
$$
\beta \equiv \alpha \bmod N\cO
$$
and $\Nr(\beta) = N\ell^e$ for some positive integer~$e$,
from which $I = \cO(N,\alpha) = \cO(N,\beta)$.

By Lemma~\ref{lem:ideal_norm_rep}, an effective version of this strong approximation theorem is sufficient to solve the quaternion $\ell$-isogeny path problem.

In particular, since $\beta$ is in $I$, the ideal $I\bar\beta/N$ is an isomorphic ideal of norm $\ell^e$.

Similarly, solving for
$$
\beta \equiv \lambda\alpha \bmod N\cO
$$
with $\lambda \in \ZZ$ coprime to $N$ such that we still have
$I = \cO(N,\beta)$, is also sufficient to solve the quaternion $\ell$-isogeny path problem.

We will focus on this relaxed effective strong approximation theorem in the next subsections.

\subsection{Isomorphism of $\cO/N\cO$-ideals}
\label{sec:ideals:ellpow:isom}

In this section, let $I$ be a left $\cO$-ideal of prime norm $N \ne p$,
and let $\gamma$ be an arbitrary element of $\cO$ of norm $NM$, where
$\gcd(N,M) = 1$.
Since $N$ is large, we can assume that it does not divide the
index $[\cO:R+Rj]$, hence we have equalities of rings
$$
\cO/N\cO = (R+Rj)/N(R + Rj) \cong \Mat_2(\ZZ/N\ZZ).
$$
We denote by $[\alpha]$ the class of an element $\alpha$ in $\cO/N\cO$
(as distinct from its conjugate $\bar{\alpha}$).

We note that $\cO\gamma/N\cO$ and $I/N\cO$ are proper nonzero
left $\cO/N\cO$-ideals.  The following explicit classification
of such ideals, in $\Mat_2(\ZZ/N\ZZ)$, will let us construct
an explicit isomorphism between these ideals.

\begin{Lemma}
Let $N$ be a prime and $A = \Mat_2(\ZZ/N\ZZ)$. There exists a bijection
$$
S : \PP^1(\ZZ/N\ZZ) \times \PP^1(\ZZ/N\ZZ) \longrightarrow
\frac{\{\, \gamma \in A\backslash\{0\} \;:\; \det(\gamma) = 0 \,\}}{(\ZZ/N\ZZ)^*}\ccomma
$$
given by
$$
S\big((u:v),(x:y)\big) =

\left(\begin{array}{@{}cc@{}} ux & uy \\ vx & vy \end{array}\right)\cdot
$$
Under this correspondence, the set of proper nontrivial left $A$-ideals
is in bijection with the set
$$
\{\, \PP^1(\ZZ/N\ZZ) \times (x:y) : (x:y) \in \PP^1(\ZZ/N\ZZ) \,\},
$$
and the right action of $A^*/(\ZZ/N\ZZ)^* = \PGL_2(\ZZ/N\ZZ)$ on
left $A$-ideals is transitive and induced by the natural (transpose)
action on $\PP^1(\ZZ/N\ZZ)$.
\end{Lemma}

\begin{proof}
The nonzero matrices
of determinant zero, modulo $(\ZZ/N\ZZ)^*$, determine a hypersurface
$ad = bc$, which is the image of $\PP^1 \times \PP^1$ by the
Segre embedding in $\PP^3$ (= $(A\backslash\{0\})/(\ZZ/N\ZZ)^*$).
It is easily verified that left and right multiplication induce
the standard and transpose multiplication on the first and second
factors of $\PP^1 \times \PP^1$, respectively, under this isomorphism,
from which the result follows.
\end{proof}

Using an explicit isomorphism $\cO/N\cO \cong \Mat_2(\ZZ/N\ZZ)$,
by this lemma we can find $[\mu]$ in $(\cO/N\cO)^*$ such that
$
(\cO\gamma/N\cO) [\mu] = I/N\cO,
$
using linear algebra over $\ZZ/N\ZZ$.

In Section~\ref{sec:ideals:ellpow:lift} we require an input $[\mu]$
which is a unit in $Rj/N\cO$.
Observing that $[j]$ is a unit, we see that such units form
a coset of $(R/NR)^*$:
$$
(\cO/N\cO)^* \cap Rj/N\cO = (R/NR)^*[j].
$$
We note that $(R/NR)^*$ acts on the $N+1$ proper nontrivial left
$\cO$-ideals, with kernel $(\ZZ/N\ZZ)^*$.
By hypothesis, $R$ is a subring of small discriminant in which
$N$ is not ramified.
If $N$ is inert in $R$, then the $N+1$ ideals form one orbit.
Otherwise, if $N$ is split, there is one orbit of size $N-1$ and
two fixed points $\cO\pp_1/N\cO$ and $\cO\pp_2/N\cO$, where
$\pp_1$ and $\pp_2$ are the prime ideals of $R$ over $N$.
With overwhelming probability, $I/N\cO$ and $\cO\gamma/N\cO$ will
not be such fixed points, and so we can solve for $[\mu]$ in
$(R/NR)^*[j]$. In the event of failure, we can select a new
$\gamma$ or $N$.

\subsection{Approximating elements of $(R/NR)^*[j]$ by $\ell$-power norm representatives}
\label{sec:ideals:ellpow:lift}

In this section, we assume that $\ell$ is a quadratic non-residue modulo $N$.

Let also $\omega$ be a generator of $R$ of minimal norm, either $1$, $2$,
or $(1+q)/4$, for $q$ a prime congruent to $3$ modulo~$4$.

We now motivate the restriction to elements of $(R/NR)^*[j]$
in the previous section.

We suppose that we are given as input a lift
$\mu_0 = x_0 + y_0 \omega + (z_0 + w_0 \omega) j$
of an arbitrary element of $\cO/N\cO$ to $R + Rj$.
The relaxed approximation problem is to search for $\lambda$ in $\ZZ$
and $\mu_1 = x_1 + y_1 \omega + (z_1 + w_1 \omega) j$ such that
$\mu = \lambda\mu_0 + N\mu_1$ satisfies the norm equation
$$
\Nr(\mu) =
    f(\lambda x_0 + N x_1, \lambda y_0 + N y_1) +
p\, f(\lambda z_0 + N z_1, \lambda w_0 + N w_1) = \ell^e,
$$
for some $e\in\mathbb{N}$, where $f(x,y) = \Nr(x + y\omega)$
is a principal binary quadratic form of discriminant $D$ as
in Lemma~\ref{lem:special-p-extremal-properties}.
The key idea to solve this norm equation, as used in~\cite{Petit2008c}
to cryptanalyze the other hash function of Charles-Goren-Lauter,
is that it simplifies considerably when $x_0 = y_0 = 0$:
\begin{equation}
\label{eq:simplified-normequation}
\Nr(\mu) = N^2 f(x_1, y_1) + p\, f(\lambda z_0 + N z_1, \lambda w_0 + N w_1) = \ell^e.
\end{equation}
The simple algorithm we now describe to solve this equation justifies
the choice of $[\mu] \in (R/NR)^*[j]$ in Section~\ref{sec:ideals:ellpow:isom}.

To construct $\mu$, given $[\mu] \in (R/NR)^*[j]$, we consider a first
lift $\mu_0 = (z_0 + w_0 \omega) j$ to $Rj$ as above, and find
$\lambda$ in $\ZZ$ and $\mu_1  = (x_1 + y_1 \omega) + (z_1 + w_1 \omega) j$
in $R + Rj$ satisfying the simplified
equation~\eqref{eq:simplified-normequation}.
This equation modulo $N$, gives
$
\lambda^2 p\,f(z_0,w_0) = \ell^e \bmod N,
$
and since $\ell$ is a quadratic nonresidue modulo $N$,
we choose the parity of $e$ depending on whether $p\,f(z_0,w_0)$
is a quadratic residue modulo $N$ or not, and solve for a
square root modulo $N$ to find $\lambda$, in $0 < \lambda < N$.

Now for fixed $z_0$, $w_0$, and $\lambda$,
Equation~\eqref{eq:simplified-normequation} implies
a linear equation in $z_1$ and $w_1$:
\begin{equation}
\label{eq:linear-normequation}
2\lambda p L((z_0,w_0),(z_1,w_1)) = \frac{\ell^e-\lambda^2 p f(z_0,w_0)}{N}\bmod N,
\end{equation}
where $L$ is the bilinear polynomial
$$
L((z_0,w_0),(z_1,w_1)) = \langle{z_0 + w_0\omega,z_1 + w_1\omega}\rangle
                   = 2 z_0z_1 + \Tr(\omega)(z_0w_1 + w_0z_1) + 2\Nr(\omega)w_0w_1.
$$

Since $N$ is a large prime, such that $\gcd(x_0w_0|D|p,N)=1$,
there are exactly $N$ solutions $(z_1,w_1)$ to the linear
equation~\eqref{eq:linear-normequation}.
We choose a random solution satisfying
$$
|\lambda z_0 + N z_1| < N^2 \text{ and }
|\lambda w_0 + N w_1| < N^2,
$$
and equation~\eqref{eq:simplified-normequation} now leads to a problem
of representation of an integer by a binary quadratic form:
\begin{equation}
\label{eq:cornaccia-normequation}
f(x_1,y_1) = r := \frac{\ell^e- p f(\lambda z_0 + N z_1, \lambda w_0 + N w_1)}{N^2}\cdot
\end{equation}
We assume that $e$ was chosen sufficiently large so that $r$ is positive.
If $r$ (or $rq$), modulo a smooth square integer factor, is prime, splits
and is a norm in $R$, Cornaccia's algorithm~\cite{Cornacchia1903} can
efficiently solve this equation, or determine that no solution exists.
In the latter case, we repeat with a new value of $(z_1,w_1)$.
Assuming the values of $r$ behave as random values around $N^4|D|p$,
we expect to choose $\log(N^4|D|p)h(D)$ values before finding a solution.

In practice, we begin with $e$ the minimal possible value having
the correct parity, then we progressively increase it if no
solution has been found. For $N$ in the range $\tilde{O}(\sqrt{p})$,
we expect the size of $e$ to satisfy
$e \sim \log_\ell(N^4|D|p) \sim 3\log_\ell(p)$.

\subsection{Algorithm analysis and experimental results}
\label{sec:ideals:ellpow:results}

We summarize our algorithm to compute an $\ell$-power norm
representative of a left $\cO$-ideal, where $\cO$ is a special
$p$-extremal maximal order.

\begin{Theorem}
Let $\cO$ be a maximal order in a quaternion algebra $B_{p,\infty}$
and let $\ell$ be a small prime. There exists a probabilistic algorithm,

which takes as input a left $\cO$-ideal and outputs an isomorphic
left $\cO$-ideal of $\ell$-power reduced norm.
\end{Theorem}

Under the most optimistic heuristic assumptions on randomness of
representations of integers by quadratic forms and uniform
distributions of primes, this algorithm is expected to run in
polynomial time and to produce ideals of norm $\ell^{e}$, where
$$
e \sim \log_\ell(N p\,\Phi(p) |D|) + \log_\ell(N^4 |D| p) - \log_\ell N^2,
$$
where the three terms respectively account for the norms
of $\gamma$, $\mu$ and $N^{-1}$.
Assuming that $\log_\ell(N) \sim \frac{1}{2}\log_\ell(p)$
and that in practice $\Phi(p)\sim\log(p)^n$ suffices,
this leads to
$$
e \sim \frac{7}{2}\log_\ell(p).
$$

We implemented the algorithms of this article in Magma~\cite{Magma}.
We first tested the algorithm of Section~\ref{sec:repns_in_orders} to compute
$N$ times $\ell$-power norm elements in $\cO$ with $\ell\in\{2,3\}$, for random
primes $p$ of sizes up to 200 bits and  for $N$ values obtained after applying
the algorithm of Section~\ref{sec:ideals:prime} on an ideal generated via a
random walk from $\cO$. The norm of the outputs were close to the expected
values.

We then tested the algorithm of Section~\ref{sec:ideals:ellpow:lift}
for $\ell\in\{2,3\}$, for random $p$ values of sizes up to 200 bits,
for $N$ values obtained after applying the algorithm of
Section~\ref{sec:ideals:prime} on an ideal generated via a random walk
from $\cO$, and for $\mu_0 = (z_0+w_0\omega)j$ with randomly chosen
$z_0,w_0\in\ZZ/N\ZZ$ not both equal to zero.
The exponents of the norms of the quaternions computed were
close to the expected value $3\log_\ell p$.

We finally tested the overall algorithm of Section~\ref{sec:ideals:ellpow}
for $\ell\in\{2,3\}$, for random $p$ values of sizes up to 200 bits, and for
ideals $I$ generated via a random walk from $\cO$.
The $\ell$-valuation of the norm of the ideals computed were close to the
expected value $\frac{7}{2}\log_\ell p$.

All computations were carried out on an Intel Xeon CPU X5500 processor
with 24 GB RAM running at 2.67GHz. The algorithm of
Section~\ref{sec:ideals:ellpow:lift} succeeded in less than 100 seconds
for all 200 bit primes, and the overall algorithm of
Section~\ref{sec:ideals:ellpow} terminated in less than 250 seconds
for primes in this range. Additional experimental results are provided
in Appendix~\ref{sec:expres}.

\subsection{Generalization to arbitrary orders}
\label{sec:ideals:gen}

We now describe how to remove the condition that $\cO$ is one of
the special orders defined in Section~\ref{sec:intro:QA}.
First we encode the relation between two maximal orders embedded
in $\QA$ in terms of an associated ideal.

\begin{Lemma}
\label{lem:eichler-order-ideals}
Suppose that $\cO_1$ and $\cO_2$ are given maximal orders
in $\QA$.  Then the Eichler order $\cO_1 \cap \cO_2$ has the same
index in each of $\cO_1$ and $\cO_2$, which we denote $M$, and the
set:
$$
I(\cO_1,\cO_2) = \{ \alpha \in \QA \;|\; \alpha \cO_2 \bar{\alpha} \subseteq M\cO_1 \}
$$
is a left $\cO_1$-ideal and right $\cO_2$-ideal of reduced norm $M$.
Conversely, if $I$ is a left $\cO_1$-ideal with right order $\cO_2$,
such that $I \not\subseteq n\cO_1$ for any $n > 1$, then $I = I(\cO_1,\cO_2)$.
\end{Lemma}

\begin{proof}
The determinant of the norm form of any maximal order $\cO$ is $p^2$,
and for any sub-lattice $L \subset \cO$ of index $M$, the reduced norm
form on $L$ has determinant $M^2\det(\cO)$. This establishes the
well-known result that the index of an Eichler order in any maximal
order is an invariant, called its level.

It is clear by construction that $I(\cO_1,\cO_2)$ is a left
$\cO_1$-module and a right $\cO_2$-module.
Locally at any prime $q$, we may assume $\cO_1$ and $\cO_2$
are $\ZZ_q$-orders such that $\cO_2 = \alpha^{-1} \cO_1 \alpha$,
for some $\alpha$ in $\cO_1$ hence also in $\cO_2$.
It follows that we have an inclusion $\alpha \cO_2 = \cO_1 \alpha
\subseteq I(\cO_1,\cO_2)$.
However, removing any integer factors (in the center), the reduced
norm of a minimal $\alpha$ must equal the level $M\ZZ_q$, which
implies equality. The global result follows from the local-global
principle.

Conversely, since any left $\cO_1$-ideal $I$ is locally principal
at each prime $q$,
one can find locally $\alpha$ such that $I = \cO_1\alpha$; the right order of I is then

$\cO_2 = \alpha^{-1} \cO_1 \alpha$.
By hypothesis $\alpha$ is not divisible by any integer and we
conclude that the Eichler order has level $\Nr(\alpha) = \Nr(I)
= M\ZZ_q$. From the above construction in terms of a local
generator, we conclude $I = I(\cO_1,\cO_2)$.
\end{proof}

\begin{Theorem}
Let $\cO_1$ and $\cO_2$ be maximal orders in a quaternion
algebra $B_{p,\infty}$ and let $\ell$ be a small prime.
Given an algorithm which takes as input a left $\cO_1$-ideal
and outputs an equivalent left $\cO_1$-ideal of $\ell$-power
reduced norm, there exists an algorithm with the same
complexity, up to a constant of size polynomial in the input
size of $\cO_1$ and $\cO_2$, which takes as input a left
$\cO_2$-ideal and outputs an equivalent left $\cO_2$-ideal of $\ell$-power reduced norm.
\end{Theorem}

\begin{proof}
Assume we are given two orders $\cO_1$, $\cO_2$ and a left
$\cO_2$-ideal $J$, and set $I = I(\cO_1,\cO_2)$ as in
Lemma~\ref{lem:eichler-order-ideals}.
The ideal $I$ may be of arbitrarily large norm, but is bounded
by something polynomial in the specification of $\cO_1$ and
$\cO_2$ in terms of a basis for $\QA$.

Supposing that we have an algorithm for $\cO_1$, we find
representative left $\cO_1$-ideals for $I$ and $IJ$ such that
$I_1 = I\bar{\gamma}_1/\Nr(I)$ with $\gamma_1$ in $I$, and
$I_2 = IJ\bar{\gamma}_2/\Nr(IJ)$ with $\gamma_2$ in $IJ$, where
$$
\Nr(\gamma_1) = \Nr(I) \ell^{e_1} \mbox{ and }
\Nr(\gamma_2) = \Nr(IJ) \ell^{e_2}.
$$
It follows that $\gamma = \bar{\gamma}_1 \gamma_2/\Nr(I)$
is an element of $J$ with reduced norm $\Nr(\gamma) =
\Nr(J) \ell^{e_1+e_2}$, and hence $J\bar{\gamma}/\Nr(J)$
is of reduced norm $\ell^{e_1+e_2}$.
\end{proof}

This provides a reduction of the general case to the case of
special $p$-extremal orders, at the cost of two applications
of the algorithm of Section~\ref{sec:ideals:ellpow}, and
a larger power of $\ell$.

\subsection{Generalization to powersmooth norms}
\label{sec:ideals:psmooth}

We recall that a number $s=\prod\ell_i^{e_i}$ is $S$-powersmooth if $\ell_i^{e_i}<S$.
Our algorithms can be easily modified to construct ideal representatives of powersmooth
norms.
Using the approximations as before, the norm should be of size close to $p^{7/2}$.
Since the product of all maximal powers of a prime lower than $S$ can be approximated
by $S^{S/\log S}$, an adaptation of our algorithms will allow us to compute
$S$-powersmooth representatives of left ideal classes of $\cO$, with
$S\approx\frac{7}{2}\log p$.

\section{Conclusion and future work}
\label{sec:concl}

In this paper, we provided a probabilistic algorithm to solve a
quaternion ideal analog of the path problem in supersingular
$\ell$-isogeny graphs. The algorithm runs in expected polynomial
time subject to heuristics on expected distributions of primes,
and it is efficient in practice.

Following Deuring~\cite{Deuring1941}, there is a one-to-one correspondence
between supersingular elliptic curves modulo $p$, up to Galois conjugacy,
and isomorphism classes of maximal orders in the quaternion algebra $\QA$.
By identifying isogeny kernels with powersmooth ideals in the quaternion
algebra graphs, we expect our techniques to lead to both partial attacks
on Charles-Goren-Lauter's isogeny based hash function (when the initial
curve has extremal endomorphism ring), and to security reductions to the
problem of computing the endomorphism ring of a supersingular elliptic curve.
Similarly, we expect our results to lead to a constructive version of
Deuring's correspondence from maximal orders in $\QA$ to their corresponding
elements in the category of supersingular elliptic curves.

\paragraph{Acknowledgements}
The research leading to these results has received funding from the Fonds National de la Recherche - FNRS and from the European Research Council through the European ISEC action HOME/2010/ISEC/AG/INT-011 B-CCENTRE project.


TITLE: How to prove $n!>(\frac{n}{e})^{n}$
QUESTION [6 upvotes]: Prove that $n!>\left(\dfrac{n}{e}\right)^{n}$.
I used induction principle but cannot solve it for the $(m+1)$-th term after taking the $m$th term to be true.

REPLY [0 votes]: I had originally written this up for another question but it seems fitting here as well. Maybe this can help someone.
Depending on how you introduced $e$, you might be able to use the fact that there are two sequences $(a_n)_{n \in \mathbb{N}}$, $(b_n)_{n \in \mathbb{N}}$ with
$$\begin{align}
a_n ~~~&:=~~~ \left ( 1 + \frac{1}{n} \right ) ^n \\ ~ \\
b_n ~~~&:=~~~ \left ( 1 - \frac{1}{n} \right ) ^{-n}
\end{align}$$
and
$$\underset{n \rightarrow \infty}{\lim} a_n ~~~=~~~ \underset{n \rightarrow \infty}{\lim} b_n ~~~=~~~ e \\ ~ \\$$
While both sequences converge to the same limit, $a_n$ approaches from the bottom and $b_n$ approaches from the top:
import numpy as np
import matplotlib.pyplot as plt
from matplotlib import rcParams
rcParams.update({'figure.autolayout': True})

pts = np.arange(0, 20, 1)
a_n = lambda n: (1+1/n)**n
b_n = lambda n: (1-1/n)**(-n)

plt.errorbar(x = pts, xerr = None, y = a_n(pts), yerr = None, fmt = "bx", markersize = "5", markeredgewidth = "2", label = "$a_n$")
plt.errorbar(x = pts, xerr = None, y = b_n(pts), yerr = None, fmt = "rx", markersize = "5", markeredgewidth = "2", label = "$b_n$")
plt.plot(pts, [np.exp(1)]*len(pts), color = "black", linewidth = 2, label = "$e$")
plt.xlim(1.5, 14.5)
plt.ylim(2.0, 3.5)
plt.legend(loc = "best")
plt.setp(plt.gca().get_legend().get_texts(), fontsize = "22")
plt.show()

So we're going to use the following inequality:
$$\forall n \in \mathbb{N} ~ : ~~~~~ \left ( 1 + \frac{1}{n} \right ) ^n ~~~~<~~~~ e ~~~~<~~~~ \left ( 1 - \frac{1}{n} \right ) ^{-n} \tag*{$\circledast$} \\ ~ \\$$

Thesis
$$\forall n \in \mathbb{N}, ~ n \geq 2 ~ : ~~~~~ e \cdot \left ( \frac{n}{e} \right )^n ~~~~<~~~~ n! ~~~~<~~~~ n \cdot e \cdot \left ( \frac{n}{e} \right )^n \\ ~ \\$$

Proof By Induction
Base Case
We begin with $n = 2$ and get
$$\begin{align}
& ~ && e \cdot \left ( \frac{2}{e} \right )^2 ~~~~&&<~~~~ 2! ~~~~&&<~~~~ 2 \cdot e \cdot \left ( \frac{2}{e} \right )^2 \\ ~ \\
& \Leftrightarrow && e \cdot \frac{4}{e^2} ~~~~&&<~~~~ 1 \cdot 2 ~~~~&&<~~~~ 2 \cdot e \cdot \frac{4}{e^2} \\ ~ \\
& \Leftrightarrow && \frac{4}{e} ~~~~&&<~~~~ 2 ~~~~&&<~~~~ \frac{8}{e} \\ ~ \\
&\Leftrightarrow && 2 ~~~~&&<~~~~ e ~~~~&&<~~~~ 4 ~~~~ \\
\end{align}
$$
Which is a true statement.
Inductive Hypothesis
Therefore the statement holds for some $n$. $\tag*{$\text{I.H.}$}$
Inductive Step
$$\begin{align}
& ~ && e \cdot \left ( \frac{n+1}{e} \right )^{n+1} \\ ~ \\
& = && (n+1) \cdot \frac{1}{e} \cdot e \cdot \left ( \frac{n+1}{e} \right )^n\\ ~ \\
& = && (n+1) \cdot \left ( \frac{n}{e} \right )^n \cdot \left ( \frac{n+1}{n} \right )^n\\ ~ \\
& = && (n+1) \cdot \left ( \frac{n}{e} \right )^n \cdot \left ( 1 + \frac{1}{n} \right )^n\\ ~ \\
& \overset{\circledast}{<} && (n+1) \cdot \left ( \frac{n}{e} \right )^n \cdot e\\ ~ \\
& \overset{\text{I.H.}}{<} && (n+1) \cdot n!\\ ~ \\
& = && (n+1)!\\ ~ \\
& = && (n+1) \cdot n!\\ ~ \\
& \overset{\text{I.H.}}{<} && (n+1) \cdot n \cdot e \cdot \left ( \frac{n}{e} \right )^n\\ ~ \\
& = && (n+1) \cdot e \cdot \left ( \frac{n}{e} \right )^{n+1} \cdot e \\ ~ \\
& = && (n+1) \cdot e \cdot \left ( \frac{n+1}{e} \right )^{n+1} \cdot \left ( \frac{n}{n+1} \right )^{n+1} \cdot e \\ ~ \\
& = && (n+1) \cdot e \cdot \left ( \frac{n+1}{e} \right )^{n+1} \cdot \left ( 1 - \frac{1}{n+1} \right )^{n+1} \cdot e \\ ~ \\
& \overset{\circledast}{<} && (n+1) \cdot e \cdot \left ( \frac{n+1}{e} \right )^{n+1} \cdot \left ( 1 - \frac{1}{n+1} \right )^{n+1} \cdot \left ( 1 - \frac{1}{n+1} \right )^{-(n+1)} \\ ~ \\
& = && (n+1) \cdot e \cdot \left ( \frac{n+1}{e} \right )^{n+1} \\ ~ \\
\end{align}
$$
Conclusion
Therefore the statement holds $\forall n \in \mathbb{N}, ~ n \geq 2$.
$$\tag*{$\square$}$$


TITLE: Understanding the local degree for local homeomorphism
QUESTION [0 upvotes]: In Hatcher AT, we he defined the local degree of a map, as a remark he gave the case when the given map is a (local) homeomorphism. Let $f:S^n\to S^n,n>0$ and $y\in S^n$ such that $f^{-1}(y)=\{x_1,...,x_m\}$. Let $U_1,...,U_m$ be disjoint nbds of these points mapped by $f$ into a nbd $V$ of $y$.

For example, if $f$ is a homeomorphism, then $y$ can be any point and there is only one corresponding $x_i$, so all the maps in the diagram are isomorphisms and $\deg f|x_i = \deg f= \pm 1$. More generally, if $f$ maps each $U_i$ homeomorphically onto $V$, then $\deg f|x_i = \pm 1 $ for each $i$.

In this statement, the reason $\deg f|x_i =\pm 1$ is because of the (local) homeomorphism $f|_{U_i}:U_i\to V$ so $H_n(U_i,U_i-x_i)\simeq H_n(V,V-y)$ not necessary because of the above diagram. Especially, for the case of local homeomorphism case, we don't know $f_*:H_n(S^n)\to H_n(S^n)$ is an isomorphism. Am I correct?

REPLY [2 votes]: You are right, that $f_* : H_n(U_i,U_i-x_i) \to H_n(V,V-y)$ is an isomorphism is due to the fact that $f \mid_{U_i}$ is a homeomorphism. And this does definitely not imply that any other of the three maps $(p_i)_* : H_n(S^n,S^n-f^{-1}(y)) \to H_n(S^n,S^n-x_i)$, $f_* : H_n(S^n,S^n-f^{-1}(y)) \to H_n(S^n,S^n-y)$ and $f_* : H_n(S^n) \to H_n(S^n)$ is an isomorphism. See Doubt about Hatcher's proof of degree calculation.
What may be confusing in Hatcher's diagram is that one is tempted to believe that the "outer isomorphism diagram"
$\require{AMScd}$
\begin{CD}
H_n(U_i,U_i-x_i)  @>{(f_i)_*}>> H_n(V,V -y) \\
@V{\approx}VV @V{\approx}VV \\
H_n(S^n) @>{f_*}>> H_n(S^n) \end{CD}
commutes. But this is not true in general.
The local degree of $f$ at $x_i$ is defined as the degree of the map
$$\phi_{(f,x_i)} :  H_n(S^n) \stackrel{\approx}{\longrightarrow} H_n(U_i,U_i-x_i) \stackrel{(f_i)_*}{\longrightarrow}  H_n(V,V -y) \stackrel{\approx}{\longrightarrow} H_n(S^n) .$$
And in fact here you see the real purpose of the specific isomorphisms $H_n(U_i,U_i -x_i) \stackrel{\approx}{\longrightarrow} H_n(S^n)$ and $H_n(V,V -y) \stackrel{\approx}{\longrightarrow} H_n(S^n)$: We need them to get the map $\phi_{(f,x_i)}$ which has the same domain and range $H_n(S^n)$ and thus allows to speak of its degree.


TITLE: Using Leibniz Integral Rule on infinite region
QUESTION [9 upvotes]: I am trying to take the derivative with respect to $a$ of some function $I(a)=\int_{0}^{\infty}f(a,x)dx$.  I would like to make sure that I am using the Leiniz Integral Rule correctly.  Various web sources indicate a set of conditions that must hold for $f(x,a)$ and $\frac{\partial f(x,a)}{\partial a}$ when integration is done over infinite region.  From reading this source (see Theorem 10.3 on page 13) the conditions that $f(x,a)$ and $\frac{\partial f(x,a)}{\partial a}$ must obey are:

$f(x,a)$ and $\frac{\partial f(x,a)}{\partial a}$ are continuous over $x\in[0,\infty)$ and around $a$ that we are interested in.
There exists an integrable function (over $x$) $g(x)$ such that $|\frac{\partial f(x,a)}{\partial a}|\leq g(x)$.
There exists an integrable function (over $x$) $h(x)$ such that $|f(x,a)|\leq h(x)$.

Integrable here means $\int_{-\infty}^{\infty}g(x)dx<\infty$.
However, another source seems to omit condition 3 above.  I am wondering which source is correct.  If there are "both correct", when is condition 3 necessary?

REPLY [5 votes]: EDIT:
Revisiting this question, I now realize that the author of the  paper is using the uniform convergence of the integral, not the dominated convergence theorem, to justify differentiating under the integral sign.
A proof can be found in the first supplement to the textbook Introduction to Real Analysis by William F. Trench. It's Theorem 11 on page 18.
Condition 2 is the M-test for uniform convergence, which can only be used if $\int^{\infty}_{0} \frac{\partial}{\partial a} f(x,a) \, dx  $  is absolutely convergent.
The uniform converge of $\int_{0}^{\infty} f(x,a) \, dx$ is not one of the assumptions in the proof, but rather it's proven that it's a consequence of $\int^{\infty}_{0} \frac{\partial}{\partial a} f(x,a) \, dx  $ converging uniformly for values of $a$ in some closed interval.

Those are sufficient but not necessary conditions.  Basically they mimic Theorem 2 at the following link without any reference to measure theory or Lebesgue integration.  Condition 3 from your source is basically saying that $f(x,a)$ is Lebesgue integrable.
http://planetmath.org/differentiationundertheintegralsign
I prefer the related approach (when possible) of expressing the integral as an iterated integral and then switching the order of integration.  Justifying switching the order of integration is usually easier.


TITLE: Why does a real spectrum not have holes?
QUESTION [1 upvotes]: Apparently, if $A$ is a $C^\ast$-algebra and the spectrum $\sigma(a) \subseteq \mathbb R$ then $\sigma (a)$ does not have holes.
I read this in Murphy and then tried to prove it since I didn't believe it. But I can't seem to prove it (even though -- since it's mentioned without proof -- it must be trivial).
Can someone please explain to me how to prove that a real spectrum is simply connected?
Edit
This is from page 41:

REPLY [4 votes]: Your statement "a real spectrum is simply connected" is wrong. To give a concrete example, let $A = B(\mathbb C^2)$, where $\mathbb C^2$ carries the standard inner product. Let $$ a = \begin{pmatrix} 1 & 0 \\ 0 & 0 \end{pmatrix} $$
Then $\sigma(a) = \{0,1\}$, which is not connected. Note that - in general - on $B(\mathbb C^n)$, the spectrum consists of at most $n$ points and is almost never connected.

As Murphy writes on page 11, proof of Thm. 1.2.8, by $\sigma_A(b)$ "having no holes", he means that $\mathbb C \setminus \sigma_A(b)$ is connected. But this is obviously true for bounded subsets of $\mathbb R$.


TITLE: $\Vert A \Vert_{G_1} \overset{?}{\geq} \Vert A \Vert_{G_2}$, if $G_1 \succeq G_2 \succeq 0 $
QUESTION [1 upvotes]: I have a G-matrix norm which is definied as $\Vert A \Vert_G = \sqrt{\text{trace}(A^T G A )} $ with a symmetric positive semidefinite matrix $G$.
I have already found out that the relationship to the Frobenius norm is as follows:
$G = M^T M$
$\Vert A \Vert_G = \Vert MA \Vert_F $
As in the title stated, I want to know, if $\Vert A \Vert_{G_1} \geq \Vert A \Vert_{G_2}$ always hold, when $G_1 \succeq G_2 \succeq 0 $?

REPLY [2 votes]: I think, I solved the problem and the statement ist true.
$\Vert A \Vert_{G_1} \geq \Vert A \Vert_{G_2} \Leftrightarrow\, \Vert A \Vert_{G_1}^2 \geq \Vert A \Vert_{G_2}^2 \Leftrightarrow \Vert A \Vert_{G_1}^2 - \Vert A \Vert_{G_2}^2 \geq 0 \\
  \Leftrightarrow \text{trace}(A^TG_1A) - \text{trace}(A^TG_2 A) = \text{trace}(A^T(G_1 - G_2)A) = \Vert A \Vert_{G_1-G_2}^2 \geq 0$
Last inequality is true, since $G_1-G_2 \succeq 0 $ and every matrix norm is greater than or equal to zero.


TITLE: Two lines in affine space are parallel iff they have the same direction
QUESTION [0 upvotes]: Show that two lines in an affine space are parallel iff they have the same direction.
I don't know how to proceed. We know that any subspace of an affine space $A$ based on a vector space $V$ is of the form $O+W=\{\ O+w |w\in W\}\ $, for some subspace $W$ of $V$. (Here, the plus between $O$ and $w$, denotes the action of $V$ on $A$.), and $W$ is called the direction of the affine subspace. Now if $PQ$ and $RS$ are two lines, they are subspaces too, So, $PQ= O+W$ and $RS=O^{'}+W^{'}$. What I suppose is that we need to prove $W=W^{'}$ iff $PQ$ is parallel to $RS$. But I can't proceed after that
Thanks in advance!!

REPLY [1 votes]: You need to show three things, and the special case of identical lines is worth considering for each of them.

If they have the same direction, they lie in a plane. If you define a plane as $O + W_1 + W_2$, i.e. a starting point and two directions, then you can pick $W_1=W$ and $W_2=\{\lambda(O-O')\mid\lambda\in\mathbb R\}$, i.e. one direction vector equal to that of the line and the other equal to the difference between the starting points of the lines. If those two directions are the same, the lines coincide and you can either pick a second direction arbitrarily or argue that a single line is alwas coplanar with itself.
If they have the same direction they have no point in common. More precisely, if they have the same direction and one point in common, then they have all points in common. So you have $O + w = O' + w'$ for some $w,w'\in W$. How you continue from here depends a bit on how you define a one-dimensional linear subspace, but if it has a basis, you'd express $w$ and $w'$ with respect to that and then show that there is a formula for the coefficients which maps points from one line to those of the other.
If they are coplanar and have no points in common, then they have the same direction. If you know that your plane has a basis, you can express the bases of the line directions with respect to that. Then you can assume different directions and show that you can compute a point of intersection.


TITLE: In the weak formulation of the Poisson equation, why is the boundary condition included in the integration of the weighted residual?
QUESTION [3 upvotes]: In the weak formulation of the Poisson equation $\nabla^2u = g$ with boundary conditions $u = \bar{u}$ on $\Gamma_e$ and $\frac{\partial{u}}{\partial{n}} = \bar{q}$ on $\Gamma_n$, why is the integration of the weighted residual expressed as
$$I = \int_\Omega w(\nabla^2u-g) d\Omega - \int_{\Gamma_e} w\frac{\partial{u}}{\partial{n}}d\Gamma$$ and not just
$$I = \int_\Omega w(\nabla^2u-g) d\Omega$$

REPLY [2 votes]: Ignoring weights, multiply both sides of the original DE by a test function and "formally" integrate by parts. You get
$$\int_\Omega -\nabla u \cdot \nabla v dx + \int_{\Gamma_e} v \nabla u \cdot n d \Gamma + \int_{\Gamma_n} v \nabla u \cdot n d \Gamma = \int_\Omega g v dx.$$
Now we apply the boundary conditions in the weak form. On the Neumann part of the boundary $\Gamma_n$, we just replace $\nabla u \cdot n$ by what it should be. It turns out that you're stuck with this seemingly weird approach. That's because in the appropriate space of candidate solutions, restricting solution functions to the boundary makes sense but restricting their derivatives to the boundary does not.
By contrast, the approach on the Dirichlet part of the boundary is what you would expect. We restrict our solution space to functions which satisfy our Dirichlet condition. To do this without making the problem inconsistent, we must also restrict our test functions to those which vanish on $\Gamma_e$. A nice way of thinking about this is that in the associated variational problem, test functions are the directions in which we can move in the space of possible solutions. If we go in a direction which doesn't vanish on $\Gamma_e$, then our new function doesn't vanish on $\Gamma_e$, so it should not be a candidate for the minimizer in the variational problem.
Thus the weak formulation of the problem says: $u$ is a solution if $u \in H^1$, $u=\overline{u}$ on $\Gamma_e$, and
$$\int_\Omega -\nabla u \cdot \nabla v dx + \int_{\Gamma_n} v \overline{q} d \Gamma = \int_\Omega g v dx$$
for all $v \in H^1$ which vanish on $\Gamma_e$. The manipulations we did in the first place imply that a strong solution is a weak solution. Undoing the manipulations that we did shows that a smooth weak solution is a strong solution. Thus the weak formulation correctly corresponds to the strong formulation.
If you need weights, you can do it again analogously (provided the integration by parts still makes sense with the weights).


TITLE: If $\operatorname{rank}(A)=k$, can we say something about $\operatorname{rank}(AA^t)$?
QUESTION [0 upvotes]: Let $A$ a $n\times m$ matrix such that $\operatorname{rank}(A)=k$,
can we say something about  $\operatorname{rank}(AA^t)$?
It's like: If $\operatorname{rank}(A)=m$, can we say anything about $\operatorname{rank}(AA^t)$?, but $A$ is a matrix $n\times m$.

REPLY [0 votes]: Basically, what we want to prove is:
For any real-valued matrix A (with dimension $n \times m$):   $$\mbox{Rank}({\bf{A}})=\mbox{Rank}({\bf{A}}^\top)=\mbox{Rank}({\bf{A}}^\top {\bf{A}})=\mbox{Rank}({\bf{A}} {\bf{A}}^\top)$$
where ${\bf{A}}^\top$ is the transpose of $\bf{A}$.
To prove this, I'll use a few facts (consider all matrices real-valued):

If the matrices B and C are conformal for multiplication, then $\mbox{Rank}({\bf{BC}}) \leq \mbox{Rank}({\bf{B}})$ and $\mbox{Rank}({\bf{BC}}) \leq \mbox{Rank}({\bf{C}})$ (proof);
$\mbox{Rank}({\bf{A}})=\mbox{Rank}({\bf{A}}^\top)$ (proof);
If D and E are full-rank square matrices, $\mbox{Rank}({\bf{AD}})=\mbox{Rank}({\bf{EA}})=\mbox{Rank}({\bf{A}})$ (proof);
If A is $n\times m$ with $\mbox{Rank}({\bf{A}})=k<\min(n,m)$, then $\exists \,$   F with dimension ($n\times k$) and G with dimension ($k\times m$) such that A=FG, and $\mbox{Rank}({\bf{A}})=\mbox{Rank}({\bf{F}})=\mbox{Rank}({\bf{G}})=k$ (proof in page 31, Lemma 4.9)

I'll divide the proof in two parts:
i) when $\mbox{Rank}({\bf{A}})=\min(n,m)$;
ii) when $\mbox{Rank}({\bf{A}})=k<\min(n,m)$
Proof of i)
WLOG, suppose that $\min(n,m)=n$, so $\mbox{Rank}({\bf{A}})=n$. Therefore, $\bf{A} \bf{A}^\top$ if a full-rank $n \times n$ square matrix. Then we can take $\mbox{Rank}({\bf{A}}^\top)$ and use fact 3 with D=$\bf{A} \bf{A}^\top$:
$$\therefore \mbox{Rank}({\bf{A}}^\top) = \mbox{Rank}({\bf{A}}^\top {\bf{D}})=\mbox{Rank}({\bf{A}}^\top {\bf{A}} {\bf{A}^\top}) \leq \mbox{Rank}({\bf{A}}^\top {\bf{A}}) \leq  \mbox{Rank}({\bf{A}}^\top)$$
where the inequalities come from fact 1 using B=$\bf{A}^\top \bf{A}$ and C=$\bf{A}^\top$ for the first one, and B=$\bf{A}^\top$, and C=$\bf{A}$ for the second one.
From the above, $\mbox{Rank}({\bf{A}}^\top) \leq \mbox{Rank}({\bf{A}}^\top {\bf{A}}) \leq  \mbox{Rank}({\bf{A}}^\top) \implies \mbox{Rank}({\bf{A}}^\top) = \mbox{Rank}({\bf{A}}^\top {\bf{A}})$.
Using the same argument, we get that $\mbox{Rank}({\bf{A}}) \leq \mbox{Rank}({\bf{A}} {\bf{A}}^\top) \leq  \mbox{Rank}({\bf{A}}) \implies \mbox{Rank}({\bf{A}}) = \mbox{Rank}({\bf{A}} {\bf{A}}^\top )$.
From fact 2, $\mbox{Rank}({\bf{A}})=\mbox{Rank}({\bf{A}}^\top)$, so the above implies that
$$\mbox{Rank}({\bf{A}})=\mbox{Rank}({\bf{A}}^\top)=\mbox{Rank}({\bf{A}}^\top {\bf{A}})=\mbox{Rank}({\bf{A}} {\bf{A}}^\top) \quad \blacksquare$$
Proof of ii)
Now, $\mbox{Rank}({\bf{A}})=k<\min(n,m)$. From fact 4, F ($n\times k$) has rank $k$, so $\bf{F}^\top \bf{F}$ is full-rank square ($k \times k$). The same  is valid for $\bf{G} \bf{G}^\top$. Thus,
$$\begin{align}
\mbox{Rank}({\bf{A}})=\mbox{Rank}({\bf{F}})=\mbox{Rank}(\underbrace{{\bf{F}} {\bf{G}}}_{={\bf{A}}} {\bf{G}^\top}) = \mbox{Rank}(\bf{A}{\bf{G}^\top} \bf{F}^\top {\bf{F}})&=\mbox{Rank}(\bf{A}{\bf{A}^\top} {\bf{F}}) \\ &\leq \mbox{Rank}({\bf{A}}{\bf{A}^\top}) \\
&\leq \mbox{Rank}({\bf{A}})
\end{align}$$
$$\therefore \mbox{Rank}({\bf{A}}) \leq \mbox{Rank}({\bf{A}}{\bf{A}^\top}) \leq \mbox{Rank}({\bf{A}}) \implies \mbox{Rank}({\bf{A}})=\mbox{Rank}({\bf{A}}{\bf{A}^\top})$$
Using a similar argument, we can show that:
$$\mbox{Rank}({\bf{A}}^\top)=\mbox{Rank}({\bf{G}}^\top) \leq \mbox{Rank}({\bf{A}}^\top {\bf{A}}) \leq \mbox{Rank}({\bf{A}}^\top) \implies \mbox{Rank}({\bf{A}}^\top {\bf{A}}) = \mbox{Rank}({\bf{A}}^\top).$$
Hence,
$$\mbox{Rank}({\bf{A}})=\mbox{Rank}({\bf{A}}^\top)=\mbox{Rank}({\bf{A}}^\top {\bf{A}})=\mbox{Rank}({\bf{A}} {\bf{A}}^\top) \quad \blacksquare$$


TITLE: Need help understanding differential of function
QUESTION [2 upvotes]: I have encountered the term differential/pushforward many times in the literature, although I cannot seem to understand just what is meant by it. I still cannot seem to understand the definition of the differential of a multivalued multivariable function

$ f : \mathbb{R}^n \to \mathbb{R}^m $

and its generalization to differentiable manifolds. I have seen many definitions of the differential, particularly those for tangent vectors on manifolds and the definition with derivations of functions and one involving the Jacobian matrix, but I cannot understand this or any of them, thus I also cannot understand just what is meant by tangent space on manifolds. What does the differential "really mean" and how to use it? In particular, how is the differential/pushforward related to derivations of functions? Could someone please explain the differential to me and possibly using it to define tangent spaces on manifolds. I am frustrated as I have never understood the differential and lack the proper understanding in tangent spaces. All help is appreciated.

REPLY [4 votes]: Let $f\colon\mathbb{R}\to\mathbb{R}$ and $x\in\mathbb{R}$, then $f$ is differentiable at $x$ if and only if there exists $\alpha\in\mathbb{R}$ such that:
$$f(x+h)=f(x)+\alpha h+o(h),$$
when $\alpha$ exists, it is unique, denoted by $f'(x)$ and called the derivative of $f$ at $x$.
Proof. Assume that there exists $\beta\in\mathbb{R}$ such that $f(x+h)=f(x)+\beta h+o(y-x)$, then:
$$(\alpha-\beta)(y-x)=o(y-x),$$
whence $\alpha=\beta$. $\Box$
Remark. Notice that $h\mapsto\alpha h$ is a linear map.
Geometrically, $y=f(x)+f'(x)(y-x)$ is the best line approximation of the graph of $f$ around $x$.
Now, let $f\colon\mathbb{R}^m\to\mathbb{R}^n$ and $x\in\mathbb{R}^m$, generalizing the above definition, $f$ is differentiable at $x$ if and only if there exists a linear map $\ell\colon\mathbb{R}^m\to\mathbb{R}^n$ such that:
$$f(x+h)=f(x)+\ell(h)+o(h),$$
when $\ell$ exists, it is unique, denoted by $T_xf$ and called the differential of $f$ at $x$.
Proof. Assume that there exists a linear map $\ell'\colon\mathbb{R}^m\to\mathbb{R}^n$ such that $f(x+h)=f(x)+\ell'(h)+o(h)$, then:
$$(\ell-\ell')(h)=o(h).$$
Let $h\in\mathbb{R}^n\setminus\{0\}$ and $t\in\mathbb{R}^*$, then $\displaystyle\frac{(\ell-\ell')(th)}{\|th\|}=\frac{(\ell-\ell')(h)}{\|h\|}$ converges toward $0$ when $t$ goes to $0$, therefore:
$$\ell(h)=\ell'(h),$$
and this also holds for $h=0$. $\Box$
Remark. This definition can be extended to maps defined only on an open set of $\mathbb{R}^m$, as $x+h$ would fall in this open set for $h$ being sufficiently small.
I won't explain how to define the tangent space of a manifold and the tangent map of a differentiable function as it is tedious and quite long. However, the main idea is that a manifold is locally an open set of some $\mathbb{R}^m$.
I recommend you have a look at An introduction to Differential Manifolds by J. Lafontaine.


text:
\section{Introduction} \label{Sdrum1}

A fundamental problem raised in Kac's famous article \cite{Kac}
`Can one hear the shape of a drum' is whether two isospectral manifolds
are isomorphic.
The answer is negative in general.
Milnor gave a counter example for compact Riemannian manifolds~\cite{Milnor}.
In the Euclidean case the first example was given in dimension~$4$ by
Urakawa~\cite{Ura}.
Then Gordon--Webb--Wolpert
\cite{GWW2} constructed two polygons in $\Ri^2$ which are isospectral
but not isomorphic.
Moreover, \cite{GordonW} constructed two isospectral convex open sets
in $\Ri^4$ which are isospectral but not isomorphic.
Kac's question in the strict sense, namely whether two isospectral
bounded open sets in $\Ri^2$ with $C^\infty$-boundary are isometric,
is still to be open.
But there are recent positive results by Zelditch \cite{Zel}
for open sets in $\Ri^2$
with analytic boundary verifying some symmetry conditions.

To say that the two manifolds are isospectral means by definition
that the corresponding Dirichlet Laplacians have the same
eigenvalues counted with multiplicity.
This, in turn, can be reformulated by saying that  there exists a unitary
operator $U$ intertwining the two heat semigroups.
The heat semigroups are positive, i.e.\ positive initial values
lead to positive solutions.
These positive solutions describe the heat diffusion on the manifold.
Thus, if instead of a unitary operator, we consider an order isomorphism
$U$ (i.e.\ $U$ is linear, bijective and $U \varphi \geq 0$ if and only if $\varphi \geq 0$)
on $L_2$, then to say say that $U$ intertwines the heat semigroups
means that $U$ maps the positive solutions to positive solutions.
It was shown in \cite{Are3} that in the Euclidean case,
i.e.\ if we consider open connected sets in $\Ri^d$, then
these sets are necessarily congruent as soon as such an intertwining
order isomorphism exists.
This may be rephrased by saying that
diffusion determines the body.
The aim of this paper is to extend this result to manifolds.

There are several notable new features coming into play in the
non-Euclidean case.
First of all, in \cite{Are3} a precise regularity  condition has been established
under which the result is valid.
The open sets have to be regular in capacity
(this means loosely speaking that they do not have holes of
capacity~$0$).
Some effort is made in this paper to extend this notion to manifolds,
which is not possible in an immediate way.

The problem addressed in this paper is partially motivated by
work of Arveson \cite{Arv2} \cite{Arv1}, who
introduces differential structures in operator algebras.
Our results imply uniqueness of these differential structures, the case
of compact Riemannian manifolds being of particular interest.

Not all results in the Euclidean case carry over to Riemannian manifolds.
We give an example, Example~\ref{xdrum501}, of a non-zero lattice homomorphism
which intertwine the heat semigroups, but which is not an isomorphism,
in contrast to the Euclidean case \cite{Are4}, Theorem~2.1.

\smallskip

Let $(M,g)$ be a Riemannian manifold of dimension $d$.
We always assume that a Riemannian manifold is $\sigma$-compact.
Then $M$ has a natural Radon measure denoted by $|\cdot|$.
Set
\[
H^1_\loc(M)
= \{ \varphi \in L_{2,\loc}(M) : \varphi \circ x^{-1} \in H^1_\loc(x(V))
       \mbox{ for every chart } (V,x) \}
\;\;\; .  \]
If $\varphi \in H^1_\loc(M)$ and $(V,x)$ is a chart on $M$ then set
$\frac{\partial}{\partial x^i} \varphi = (D_i (\varphi \circ x^{-1})) \circ x \in L_{2,\loc}(V)$,
where $D_i$ denotes the partial derivative in $\Ri^d$.
Moreover, for all $\varphi,\psi \in H^1_\loc(M)$
there exists a unique element $\nabla \varphi \cdot \nabla \psi \in L_{1,\loc}(M)$
such that
\[
\nabla \varphi \cdot \nabla \psi \Big|_V
= \sum_{i,j=1}^d g^{ij} \Big( \frac{\partial}{\partial x^i} \varphi \Big)
                               \Big( \frac{\partial}{\partial x^j} \psi \Big)
\]
for every chart $(V,x)$ on $M$.
We let $|\nabla \varphi| = (\nabla \varphi \cdot \nabla \varphi)^{1/2}$.
Let $H^1(M)$ be the Hilbert space of all $\varphi \in H^1_\loc(M)$ such that
both $\varphi, |\nabla \varphi| \in L_2(M)$, with norm
$\varphi \mapsto ( \|\varphi\|_2^2 + \| \, |\nabla \varphi| \, \|_2^2 )^{1/2}$.
Moreover, let $H^1_0(M)$ be the closure of $C_c^\infty(M)$ in $H^1(M)$.
Define the bilinear form $a \colon H^1_0(M) \times H^1_0(M) \to \Ri$ by
$a(\psi,\varphi) = \int \nabla \psi \cdot \nabla \varphi$.
Then $a$ is  closed and positive.
The {\bf Dirichlet Laplace--Beltrami operator} $\Delta$
on $M$ is the associated self-adjoint operator.
If $(V,x)$ is a chart on $M$ then
\[
\Delta \, \varphi
= - \sum_{i,j=1}^d \frac{1}{\sqrt{g}} \, \frac{\partial}{\partial x^i} \,
           g^{ij} \, \sqrt{g} \, \frac{\partial}{\partial x^j} \, \varphi
\]
for all $\varphi \in C_c^\infty(V)$.

If $(M_1,g_1)$ and $(M_2,g_2)$ are two Riemannian manifolds
then a map $\tau \colon M_1 \to M_2$ is called an {\bf isometry}
if it is a $C^\infty$-diffeomorphism and
\[
g_2|_{\tau(p)}(\tau_*(v), \tau_*(w)) = g_1|_p(v,w)
\]
for all $p \in M_1$ and $v,w \in T_p M$.
A map $\tau \colon M_1 \to M_2$ is called a {\bf local isometry}
if for all $p \in M_1$ there exists an open neighbourhood
$V$ of $p$ such that the restriction $\tau|_V \colon V \to \tau(V)$
is an isometry.
The Riemannian manifolds $(M_1,g_1)$ and $(M_2,g_2)$
are called {\bf isomorphic} if there exists an isometry
from $M_1$ onto $M_2$.
If $\tau \colon M_1 \to M_2$ is an isometry
and $p \in [1,\infty)$ then
$\varphi \circ \tau \in L_p(M_1)$ and
\begin{equation}
\|\varphi \circ \tau\|_{L_p(M_1)} = \|\varphi\|_{L_p(M_2)}
\label{eSdrum1;1}
\end{equation}
for all $\varphi \in L_p(M_2)$.
In particular, the map $\varphi \mapsto \varphi \circ \tau$ is a
unitary map from $L_2(M_2)$ onto $L_2(M_1)$ and a unitary map
from $H^1_0(M_2)$ onto $H^1_0(M_1)$.
Moreover, if $\varphi \in L_2(M_2)$ then
$\varphi \in D(\Delta_2)$ if and only if $\varphi \circ \tau \in D(\Delta_1)$
and $\Delta_1(\varphi \circ \tau) = (\Delta_2 \varphi) \circ \tau$,
where $\Delta_j$ is the Dirichlet Laplace--Beltrami operator
on $M_j$ for all $j \in \{ 1,2 \} $.

A linear operator $U \colon E \to F$ between two Riesz spaces is said to be a
{\bf lattice homomorphism} if
\[
U (\varphi \wedge \psi) = (U \varphi) \wedge (U \psi)
\]
for all $\varphi,\psi \in E$.
For alternative equivalent definitions see \cite{AB} Theorem~7.2.
Here in this paper in most cases the spaces $E$ and $F$ will be $L_p$-spaces
and then $(\varphi \wedge \psi)(x) = \min \{ \varphi(x),\psi(x) \} $ a.e.
Each lattice homomorphism $U$ is positive, i.e.\ $\varphi \geq 0$
implies $U \varphi \geq 0$.
An {\bf order isomorphism} $U \colon E \to F$ is a bijective
mapping  such that $U \varphi \geq 0$ if and only if $\varphi \geq 0$.
Equivalently, $U$ is an order isomorphism
if and only if $U$ is a bijective lattice homomorphism.
Then also $U^{-1}$ is an order isomorphism.
Recall that also  each positive operator between $L_p$-spaces is continuous
by \cite{AB} Theorem~12.3.

The main theorem of this paper is the following.
It is valid under some regularity assumptions on the manifolds,
namely regularity in capacity, which is optimal for this purpose and
which we will explain below.

\begin{thm} \label{tdrum101}
Let $(M_1,g_1)$ and $(M_2,g_2)$ be two connected Riemannian manifolds which are both regular in capacity.
Let $p \in [1,\infty)$.
For all $j \in \{ 1,2 \} $ let $\Delta_j$ be the Dirichlet Laplace--Beltrami operator
on $M_j$ and let $S^{(j)}$ be the associated semigroup on $L_p(M_j)$.
Then the following two conditions are equivalent.
\begin{tabel}
\item \label{tdrum101-1}
$(M_1,g_1)$ and $(M_2,g_2)$ are isomorphic.
\item \label{tdrum101-3}
There exists a lattice homomorphism $U \colon L_p(M_1) \to L_p(M_2)$ such that
$U L_p(M_1)$ is dense in $L_p(M_2)$ and
\[
U S^{(1)}_t = S^{(2)}_t U
\]
for all $t > 0$.
\end{tabel}
Moreover, if $U$ is a lattice homomorphism as in Condition~{\rm \ref{tdrum101-3}} then
$U$ is an order isomorphism and
there exist $c>0$ and an isometry $\tau \colon M_2 \to M_1$ such that
$U \varphi = c \, \varphi \circ \tau$ for all $\varphi \in L_p(M_1)$.
\end{thm}

It turns out that
all complete connected Riemannian manifolds, and in particular all compact
connected Riemannian manifolds, are regular in capacity.
Therefore one immediately has the following corollary.

\begin{cor} \label{cdrum102}
Let $(M_1,g_1)$ and $(M_2,g_2)$ be two complete connected Riemannian manifolds.
Let $p \in [1,\infty)$.
For all $j \in \{ 1,2 \} $ let $\Delta_j$ be the Dirichlet Laplace--Beltrami operator
on $M_j$ and let $S^{(j)}$ be the associated semigroup on $L_p(M_j)$.
Then the following two conditions are equivalent.
\begin{tabel}
\item \label{cdrum102-1}
$(M_1,g_1)$ and $(M_2,g_2)$ are isomorphic.
\item \label{cdrum102-2}
There exists an order isomorphism $U \colon L_p(M_1) \to L_p(M_2)$ such that
\[
U S^{(1)}_t = S^{(2)}_t U
\]
for all $t > 0$.
\end{tabel}
\end{cor}

Now we explain the notion of regularity in capacity for Riemannian manifolds.
The {\bf capacity} of a subset $A$ of $M$ is given by
\[
\capp_M(A)
= \capp(A)
= \inf \{ \|\varphi\|_{H^1(M)}^2 : \varphi \in H^1(M) \mbox{ and } \varphi \geq 1
                                 \mbox{ on a neighbourhood of } A \}
\;\;\; .  \]
An open subset $\Omega$ of $\Ri^d$ is called {\bf regular in capacity}
\cite{Are3} if $\capp_{\Ri^d} (B(x\,;r) \setminus \Omega) > 0$
for all $x \in \partial \Omega$ and $r > 0$, where $B(x\,;r)$ is the
Euclidean ball.
Biegert and Warma gave several characterizations for regular in capacity.
In particular, an open subset $\Omega$ of $\Ri^d$ is regular in capacity
if and only if every $\varphi \in H^1_0(\Omega) \cap C(\overline{\Omega})$ is
zero everywhere on $\partial \Omega$ (\cite{BW} Theorem~3.2).
Since $\Ri^d$ is locally compact it then follows that
an open subset $\Omega$ of $\Ri^d$ is regular in capacity
if and only if every $\varphi \in H^1_0(\Omega) \cap C_0(\overline{\Omega})$ is
zero everywhere on $\partial \Omega$.
This characterization allows an extension to general connected Riemannian manifolds.
There is a natural distance $d_M$ on a connected Riemannian manifold~$M$.
We denote by $B_M(p\,;r) = B(p\,;r)$ the associated balls.
Let $\widetilde M$ denote the (metric) completion of $M$ with respect to this distance.
Set
\[
\partial M=\widetilde M\setminus M
\;\;\; .  \]
We say that a connected Riemannian manifold $M$ is {\bf regular in capacity} if
$\varphi(p) = 0$ for all
$\varphi \in C_0(\widetilde M) \cap H^1_0(M)
      = \{ \varphi \in C_0(\widetilde M) : \varphi|_M \in H^1_0(M) \} $ and $p \in \partial M$.
Here $C_0(\widetilde M)$ is the closure of the space $C_c(\widetilde M)$
of all continuous functions with compact support, with respect to the
supremum norm in the space of all bounded continuous functions on~$\widetilde M$.
Clearly every complete connected Riemannian manifold is regular in capacity.

In the Euclidean case regularity in capacity is a very mild  condition
on the boundary of an open subset.
If $\Omega \subset \Ri^d$ is open and bounded then it is regular in capacity
if it is Dirichlet regular.
The Lebesgue cusp is regular in capacity, but not Dirichlet regular
(see \cite{AD} Section~7).

If $M_1$ and $M_2$ are two isomorphic connected Riemannian manifolds and
$\tau \colon M_1 \to M_2$ is an isometry
then $\tau$ is {\bf distance preserving}, i.e.\
$d_{M_2}(\tau(p)\,;\tau(q)) = d_{M_1}(p\,;q)$ for all $p,q \in M_1$.
Moreover, if $M_1$ is
regular in capacity, then also $M_2$ is regular in capacity.

Now we can explain why regularity in capacity is the minimal regularity condition
in our context.
Let $M$ be a connected Riemannian manifold which is
complete (or more general, regular in capacity).
Let $\emptyset \neq N \subset M$ be a closed subset of capacity zero.
Then $\Omega := M \setminus N$ is again a connected Riemannian manifold
(see Theorem~\ref{tdrum302})
The injection $\tau \colon \Omega \to M$ defines an isometry which is not
surjective.
The unitary operator $U \colon L_2(M) \to L_2(\Omega)$ given by $U \varphi = \varphi \circ \tau$
is an order isomorphism intertwining the two heat semigroups
even though $\Omega$ and $M$ are not isomorphic.
It follows from Theorem~\ref{tdrum101} that $\Omega$ is not regular in capacity.

The paper is organized as follows.
In the next section we give a sufficient condition to ensure that the
distance on a subriemannian manifold equals the induced distance.
In Section~\ref{Sdrum5} we show that $M_1$ and $M_2$ are
isometric if they have sufficiently big isometric open subsets.
In Section~\ref{Sdrum2} we prove Theorem~\ref{tdrum101}.
Finally, in Section~\ref{Sdrum4} we give several characterizations of
regularity in capacity.

\subsection*{Acknowledgements}
The first and second named authors would like to thank for the great
hospitality and generosity
during their stay at the University of Auckland.
The third named author is most grateful for the hospitality extended
to him during a most enjoyable and fruitful stay at the University of Ulm.

config: arxiv


TITLE: Is the mass of a body the same in both material coordinate and spatial coordinate?
QUESTION [1 upvotes]: Consider the body $\mathscr{B}$ occupies volume $\mathscr{V}$ in material coordinates (where points are denoted by $\mathbf{X}=(X,Y,Z)$), and occupies region $\mathscr{R}$ with volume $v$ in spatial coordinate ($\mathbf{x}=(x,y,z)$). Assume the density could be obtained by any of the two relations below:
$$
\rho=f(\mathbf{X},t)
$$
or
$$
\rho = g(\mathbf{x},t)
$$
The question is does the equality below hold?
$$
\int_{\mathscr{V}}fd{V}=\int_vg\mathrm{dv}
$$
, where $dV=dXdYdZ$, and $\mathrm{dv}=dxdydz$.

REPLY [1 votes]: Yes, the equality holds, if you're using these two sets of coordinates to describe the same physical quantity, i.e. the mass of a physical body.
Physical quantities and equations are absolute, in the sense that they and the process they describe don't depend on the coordinates you use.
Your goal is to compute a physical quantity as the mass of the body $\mathscr B$, i.e.
$M = \displaystyle\int_{\mathscr B} \rho $
and you use 2 different sets of coordinates, X and x, as parameters to describe the physical volume $\mathscr B$, its density $\rho$ and its mass $M$.
(Notation: you should be able to avoid any differential in the physical volume integral).
To easily get a numerical value, then you introduce here two sets of coordinates to parameterize the physical space and the physical properties. If your parameterizations are consistent with the physics, the result you get is independent of the choice of the coordinates
$M = \displaystyle\int_{\mathscr B} \rho = \displaystyle\int_{\mathscr V} f(\mathbf{X}, t) dV = \displaystyle\int_{v} g(\mathbf{x}, t) dv$.
From the mathematical point of view, you're performing a change of variables, $\mathbf{x}(\mathbf{X})$, resulting in the transformation of the elementary volumes
$dv = J(\mathbf{X}) dV = \left| \dfrac{ \partial \mathbf{x}}{\partial \mathbf{X}} \right| dV$,
where $J(\mathbf{X})$ is the Jacobian of the transformation, i.e. the determinant of the gradient of the transformation $ \frac{ \partial \mathbf{x}}{\partial \mathbf{X}} (\mathbf{X})$.
Now, performing a change of variables in the last integral (using $dv = J dV$ and changing the domain of integration from $v$ to $\mathscr{V}$), and comparing with the other expression, you get the relationship between the two functions you used to parametrize the density,
$f(\mathbf{X}) = g(\mathbf{x}) J(\mathbf{X})$.
In this process we don't even need to assume that we're using Eulerian and Lageangian coordinates: it is just a parametrization and a change of variables between parametrizations to describe the same physical quantity, and thus holds for every set of arbitrary coordinates, not only for Lagrangian and Eulerian coordinates.