text:
\chapter{Factorial Elements of Puiseux Monoids} \label{conclusion}

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

The elements having exactly one factorization are crucial in the study of factorization theory of commutative cancellative monoids and integral domains. Aiming to avoid repeated long descriptions, we call such elements \emph{molecules}. Molecules were first studied in the context of algebraic number theory by W.~Narkiewicz and other authors in the 1960's. For instance, in~\cite{wN66} and~\cite{wN66a} Narkiewicz studied some distributional aspects of the molecules of quadratic number fields. In addition, he gave an asymptotic formula for the number of (non-associated) integer molecules of any algebraic number field~\cite{wN72}. In this chapter, we study the molecules of submonoids of~$(\qq_{\ge 0},+)$, including numerical monoids, and the molecules of their corresponding monoid algebras.

If a numerical monoid $N$ satisfies that $N \neq \nn_0$, then it contains only finitely many molecules. Notice, however, that every positive integer is a molecule of $(\nn_0,+)$. Figure~\ref{fig:molecule of four NS} shows the distribution of the sets of molecules of four numerical monoids. We begin Section~\ref{sec:molecules of NS} pointing out how the molecules of numerical monoids are related to the Betti elements. Then we show that each element in the set $\nn_{\ge 4} \cup \{\infty\}$ (and only such elements) can be the number of molecules of a numerical monoid. We conclude our study of molecules of numerical monoids exploring the possible cardinalities of the sets of reducible molecules (i.e., molecules that are not atoms).

The class of Puiseux monoids, on the other hand, contains members having infinitely many atoms and, consequently, infinitely many molecules. In Section~\ref{sec:molecules of PM}, we study the sets of molecules of Puiseux monoids, finding infinitely many non-isomorphic Puiseux monoids all whose molecules are atoms (in contrast to the fact that the set of molecules of a numerical monoid always differs from its set of atoms).

We conclude with Section~\ref{sec:mol prime reciprocals}, where we construct infinitely many non-isomorphic Puiseux monoids having infinitely many molecules that are not atoms (in contrast to the fact that the set of molecules of a nontrivial numerical monoid is always finite). Special attention is given in this section to prime reciprocal Puiseux monoids and a characterization of their molecules.
\begin{figure}
	\centering
	\includegraphics[width = 11cm]{images/MoleculesOfFourNS}
	\caption[Atoms, molecules, and non-molecules of the numerical monoids $N_1 = \langle 2, 21 \rangle$, $N_2 = \langle 6,9,20 \rangle$, $N_3 = \langle 5,6,7,8,9 \rangle$, and $N_4 = \langle 2,3 \rangle$.]{The dots on the horizontal line labeled by $N_i$ represent the nonzero elements of the numerical monoid $N_i$; here we are setting $N_1 = \langle 2, 21 \rangle$, $N_2 = \langle 6,9,20 \rangle$, $N_3 = \langle 5,6,7,8,9 \rangle$, and $N_4 = \langle 2,3 \rangle$.
		Atoms are represented in blue, molecules that are not atoms in red, and non-molecules in black.}
	\label{fig:molecule of four NS}
\end{figure}
\medskip

\section{Molecules of Numerical Monoids}
\label{sec:molecules of NS}

In this section we study the sets of molecules of numerical monoids, putting particular emphasis on their possible cardinalities.

\subsection{Atoms and Molecules}

As one of the main purposes of this chapter is to study elements with exactly one factorization in Puiseux monoids (in particular, numerical monoids), we introduce the following definition.

\begin{definition}
	Let $M$ be a monoid. We say that an element $x \in M \setminus U(M)$ is a \emph{molecule} provided that $|\mathsf{Z}(x)| = 1$. The set of all molecules of $M$ is denoted by $\mathcal{M}(M)$.
\end{definition}

It is clear that the set of atoms of any monoid is contained in the set of molecules. However, such an inclusion might be proper (consider, for instance, the additive monoid $\nn_0$). In addition, for any atomic monoid $M$ the set $\mathcal{M}(M)$ is \emph{divisor-closed} in the sense that if $x \in \mathcal{M}(M)$ and $x' \mid_M x$ for some $x' \in M \setminus U(M)$, then $x' \in \mathcal{M}(M)$. If the condition of atomicity is dropped, then this observation is not necessarily true (see Example~\ref{ex:PM whose set of molecules is not divisor-closed}).
\medskip

\begin{example} \label{ex:NS with embedding dimension two}
	For $k \ge 1$, consider the numerical monoid $N_1 = \langle 2, 21 \rangle$, whose molecules are depicted in Figure~\ref{fig:molecule of four NS}. It is not hard to see that $x \in N_1^\bullet$ is a molecule if and only if every factorization of $x$ contains at most one copy of $21$. Therefore
	\[
	\mathcal{M}(N_1) = \big\{2m + 21n : 0 \le m < 21, n \in \{0,1\}, \, \text{and} \, (m, n) \neq (0, 0)\big\}.
	\]
	In addition, if $2m + 21n = 2m' + 21n'$ for some $m,m' \in \{0,\dots, 20\}$ and $n,n' \in \{0,1\}$, then one can readily check that $m = m'$ and $n = n'$. Hence $|\mathcal{M}(N_1)| = 41$.
\end{example}
\smallskip

\subsection{Betti Elements} Let $N = \langle a_1, \dots, a_n \rangle$ be a minimally generated numerical monoid. We always represent an element of $\mathsf{Z}(N)$ with an $n$-tuple $z = (c_1, \dots, c_n) \in \nn^n_0$, where the entry $c_i$ specifies the number of copies of $a_i$ that appear in $z$. Clearly, $|z| = c_1 + \dots + c_n$. Given factorizations $z = (c_1, \dots, c_n)$ and $z' = (c'_1, \dots, c'_n)$, we define
\[
	\gcd(z,z') = (\min\{c_1,c'_1\}, \dots, \min\{c_n,c'_n\}).
\]
The \emph{factorization graph} of $x \in N$, denoted by $\nabla\!_x(N)$ (or just $\nabla\!_x$ when no risk of confusion exists), is the graph with vertices $\mathsf{Z}(x)$ and edges between those $z, z' \in \mathsf{Z}(x)$ satisfying that $\gcd(z,z') \neq 0$. The element $x$ is called a \emph{Betti element} of $N$ provided that $\nabla\!_x$ is disconnected. The set of Betti elements of $N$ is denoted by $\text{Betti}(N)$.

\begin{example}
	Take $N$ to be the numerical monoid $\langle 14, 16, 18, 21, 45 \rangle$. A computation in SAGE using the \texttt{numericalsgps GAP} package immediately reveals that $N$ has nine Betti elements. In particular, $90 \in \text{Betti}(N)$. In Figure~\ref{fig:factorization graphs} one can see the disconnected factorization graph of the Betti element $90$ on the left and the connected factorization graph of the non-Betti element $84$ on the right.
	\begin{figure}
		\centering
		\subfigure[\label{figa}]{\includegraphics[width = 5.4cm]{images/DiscFactGraph}}
		\hspace{10pt}
		\subfigure[]{\includegraphics[width = 5.4cm]{images/ConnFactGraph}}
		\caption[The factorization graphs of $90 \in \text{Betti}(N)$ and $84 \notin \text{Betti}(N)$, where $N$ is the numerical monoid $\langle 14,16,18,21,45 \rangle$.]{Factorization graphs of one Betti element and one non-Betti element in the numerical monoid $N = \langle 14,16,18,21,45 \rangle$: A) the element $90 \in \text{Betti}(N)$ \\and B) the element $84 \notin \text{Betti}(N)$. }
		\label{fig:factorization graphs}
	\end{figure}
\end{example}

Observe that $0 \notin \text{Betti}(N)$ since $|\mathsf{Z}(0)| = 1$. It is well-known that every numerical monoid has finitely many Betti elements. Betti elements play a fundamental role in the study of uniquely-presented numerical monoids \cite{GO10} and the study of delta sets of BFMs~\cite{CGLMS12}. In a numerical monoid, Betti elements and molecules are closely related.

\begin{remark}
	Let $N$ be a numerical monoid. An element $m \in N$ is a molecule if and only if $\beta \nmid_N m$ for any $\beta \in \text{Betti}(N)$.
\end{remark}

\begin{proof}
	For the direct implication, suppose that $m$ is a molecule of $N$ and take $\alpha \in N$ such that $\alpha \mid_N m$. As the set of molecules is closed under division, $|\mathsf{Z}(\alpha)| = 1$. This implies that $\nabla \!_\alpha$ is connected and, therefore, $\alpha$ cannot be a Betti element. The reverse implication is just a rephrasing of \cite[Lemma~1]{GO10}.
\end{proof}
\medskip

\subsection{On the Sizes of the Sets of Molecules} Obviously, for every $n \in \nn$ there exists a numerical monoid having exactly $n$ atoms. The next proposition answers the same realization question replacing the concept of an atom by that one of a molecule. Recall that $\mathcal{N}^\bullet$ denotes the class of all nontrivial numerical monoids.

\begin{proposition} \label{prop:realization for the size of the sets of molecules}
	$\{|\mathcal{M}(N)| : N \in \mathcal{N}^\bullet\} = \nn_{\ge 4}$.
\end{proposition}

\begin{proof}
	Let $N$ be a nontrivial numerical monoid. Then $N$ must contain at least two atoms. Let $a$ and $b$ denote the two smallest atoms of $N$, and assume that $a < b$. Note that $2a$ and $a+b$ are distinct molecules that are not atoms. Hence $|\mathcal{M}(N)| \ge 4$. As a result, $\{|\mathcal{M}(N)| : N \in \mathcal{N}^\bullet\} \subseteq \nn_{\ge 4} \cup \{ \infty \}$. Now take $x \in \nn$ with $x > \mathfrak{f}(N) + a b$. Since $x' := x - a b > \mathfrak{f}(N)$, we have that $x' \in N$ and, therefore, $\mathsf{Z}(x')$ contains at least one factorization, namely $z$. So we can find two distinct factorizations of $x$ by adding to $z$ either $a$ copies of $b$ or $b$ copies of $a$. Thus, $\mathfrak{f}(N) + a b$ is an upper bound for $\mathcal{M}(N)$, which means that $|\mathcal{M}(N)| \in \nn_{\ge 4}$. Thus, $\{|\mathcal{M}(N)| : N \in \mathcal{N}^\bullet\} \subseteq \nn_{\ge 4}$.

	To argue the reverse inclusion, suppose that $n \in \nn_{\ge 4}$, and let us find $N \in \mathcal{N}$ with $|\mathcal{M}(N)| = n$. For $n = 4$, we can take the numerical monoid $\langle 2, 3 \rangle$ (see Figure~\ref{fig:molecule of four NS}). For $n > 4$, consider the numerical monoid
	\[
		N = \langle n-2, n-1, \dots, 2(n-2)-1 \rangle.
	\]
	It follows immediately that $\mathcal{A}(N) = \{n-2, n-1, \dots, 2(n-2)-1\}$. In addition, it is not hard to see that $2(n-2), 2(n-2)+1 \in \mathcal{M}(N)$ while $k \notin \mathcal{M}(N)$ for any $k > 2(n-2)+1$. Consequently, $\mathcal{M}(N) = \mathcal{A}(N) \cup \{2(n-2), 2(n-2)+1\}$, which implies that $|\mathcal{M}(N)| = n$. Therefore $\{|\mathcal{M}(N)| : N \in \mathcal{N}\} \supseteq \nn_{\ge 4}$, which completes the proof.
\end{proof}

\begin{corollary}
	The monoid $(\nn_0,+)$ is the only numerical monoid having infinitely many molecules.
\end{corollary}

In Proposition~\ref{prop:realization for the size of the sets of molecules} we have fully described the set $\{|\mathcal{M}(N)| : N \in \mathcal{N} \}$. A full description of the set $\{|\mathcal{M}(N) \setminus \mathcal{A}(N)| : N \in \mathcal{N} \}$ seems to be significantly more involved. However, the next theorem offers some evidence to believe that
\[
	\{|\mathcal{M}(N) \setminus \mathcal{A}(N)| : N \in \mathcal{N} \} = \nn_{\ge 2} \cup \{\infty\}.
\]

\begin{theorem} \label{thm:more molecules than atoms in any NS}
	The following statements hold.
	\begin{enumerate}
		\item $\{|\mathcal{M}(N) \setminus \mathcal{A}(N)| : N \in \mathcal{N}^\bullet \} \subseteq \nn_{\ge 2}$.
		\vspace{3pt}
		\item $|\mathcal{M}(N) \! \setminus \! \mathcal{A}(N)| = 2$ for infinitely many numerical monoids $N$.
		\vspace{3pt}
		\item For each $k \in \nn$, there is a numerical monoid $N_k$ with $|\mathcal{M}(N) \! \setminus \! \mathcal{A}(N)| > k$.
	\end{enumerate}
\end{theorem}

\begin{proof}
	To prove~(1), take $N \in \mathcal{N}^\bullet$. Then we can assume that $N$ has embedding dimension $n$ with $n \ge 2$. Take $a_1, \dots, a_n \in \nn$ such that $a_1 < \dots < a_n$ such that $N = \langle a_1, \dots, a_n \rangle$. Since $a_1 < a_2 < a_j$ for every $j = 3, \dots,n$, the elements $2a_1$ and $a_1 + a_2$ are two distinct molecules of $N$ that are not atoms. Hence $\mathcal{M}(N) \setminus \mathcal{A}(N) \subseteq \nn_{\ge 2} \cup \{\infty\}$. On the other hand, Proposition~\ref{prop:realization for the size of the sets of molecules} guarantees that $|\mathcal{M}(N)| < \infty$, which implies that $|\mathcal{M}(N) \setminus \mathcal{A}(N)| < \infty$. As a result, the statement~(1) follows.

	To verify the statement~(2), one only needs to consider for every $n \in \nn$ the numerical monoid $N_n := \{0\} \cup \nn_{\ge n-2}$. The minimal set of generators of $N_n$ is the $(n-2)$-element set $\{n-2, n-1, \dots, 2(n-2)-1 \}$ and, as we have already argued in the proof of Proposition~\ref{prop:realization for the size of the sets of molecules}, the set $\mathcal{M}(N_n) \! \setminus \! \mathcal{A}(N_n)$ consists precisely of two elements.

	Finally, let us prove condition~(3). We first argue that for any $a,b \in ~\nn_{\ge 2}$ with $\gcd(a,b) = 1$ the numerical monoid $\langle a, b \rangle$ has exactly $ab-1$ molecules (cf. Example~\ref{ex:NS with embedding dimension two}). Assume $a < b$, take $N := \langle a, b \rangle $, and set
	\[
		\mathcal{M} = \{ma + nb : 0 \le m < b, \, 0 \le n < a, \, \text{and} \ \, (m, n) \neq (0, 0)\}.
	\]
	Now take $x \in N$ to be a molecule of $N$. As $|\mathsf{Z}(x)| = 1$, the unique factorization $z := ~(c_1, c_2) \in \mathsf{Z}(x)$ (with $c_1,c_2 \in \nn_0$) satisfies that $c_1 < b$; otherwise, we could exchange $b$ copies of the atom $a$ by $a$ copies of the atom $b$ to obtain another factorization of $x$. A similar argument ensures that $c_2 < a$. As a consequence, $\mathcal{M}(N) \subseteq \mathcal{M}$. On the other hand, if $ma + nb = m'a + n'b$ for some $m,m',n,n' \in \nn_0$, then $\gcd(a,b) = 1$ implies that $b \mid m-m'$ and $a \mid n-n'$. Because of this observation, the element $(b-1)a + (a-1)b$ has only the obvious factorization, namely $(b-1,a-1)$. Since $(b-1)a + (a-1)b$ is a molecule satisfying that $y \mid_N (b-1)a + (a-1)b$ for every $y \in \mathcal{M}$, the inclusion $\mathcal{M} \subseteq \mathcal{M}(N)$ holds. Hence $|\mathcal{M}(N)| = |\mathcal{M}| = ab-1$. To argue the statement~(3) now, it suffices to take $N_k := \langle 2, 2k+1 \rangle$.
\end{proof}
\medskip

\section{Molecules of Generic Puiseux Monoids}
\label{sec:molecules of PM}
\smallskip

 In this section we study the sets of molecules of the general class of Puiseux monoids. We will argue that there are infinitely many non-finitely generated atomic Puiseux monoids~$P$ such that $|\mathcal{M}(P) \setminus \mathcal{A}(P)| = \infty$. On the other hand, we will prove that, unlike the case of numerical monoids, there are infinitely many non-isomorphic atomic Puiseux monoids all whose molecules are, indeed, atoms.

In Section~\ref{sec:molecules of NS} we mentioned that the set of molecules of an atomic monoid is divisor-closed. The next example indicates that this property might not hold for non-atomic monoids.

\begin{example} \label{ex:PM whose set of molecules is not divisor-closed}
	Consider the Puiseux monoid
	\[
		P = \bigg\langle \frac 25, \frac 35, \frac 1{2^n} \, : \, n \in \nn \bigg\rangle.
	\]
	First, observe that $0$ is not a limit point of $P^\bullet$, and so $P$ cannot be finitely generated. After a few easy verifications, one can see that $\mathcal{A}(P) = \{2/5, 3/5\}$. On the other hand, it is clear that $1/2 \notin \langle 2/5,3/5 \rangle$, so $P$ is not atomic. Observe now that~$\mathsf{Z}(1)$ contains only one factorization, namely $2/5 + 3/5$. Therefore $1 \in \mathcal{M}(P)$. Since $\mathsf{Z}(1/2)$ is empty, $1/2$ is not a molecule of $P$. However, $1/2 \mid_P 1$. As a result, $\mathcal{M}(P)$ is not divisor-closed.
\end{example}

Although the additive monoid $\nn_0$ contains only one atom, it has infinitely many molecules. The next result implies that $\nn_0$ is basically the only atomic Puiseux monoid having finitely many atoms and infinitely many molecules.

\begin{proposition} \label{prop:atoms-molecules cardinality for PM}
	Let $P$ be a Puiseux monoid. Then $|\mathcal{M}(P)| \in \nn_{\ge 2}$ if and only if $|\mathcal{A}(P)| \in \nn_{\ge 2}$.
\end{proposition}

\begin{proof}
	Suppose first that $|\mathcal{M}(P)| \in \nn_{\ge 2}$. As every atom is a molecule, $\mathcal{A}(P)$ is finite. Furthermore, note that if $\mathcal{A}(P) = \{a\}$, then every element of the set $S = \{na : n \in \nn\}$ would be a molecule, which is not possible as $|S| = \infty$. As a result, $|\mathcal{A}(P)| \in \nn_{\ge 2}$. Conversely, suppose that $|\mathcal{A}(P)| \in \nn_{\ge 2}$. Since the elements in $P \! \setminus \! \langle \mathcal{A}(P) \rangle$ have no factorizations, $\mathcal{M}(P) = \mathcal{M}(\langle \mathcal{A}(P) \rangle)$. Therefore there is no loss in assuming that $P$ is atomic. As $1 < |\mathcal{A}(P)| < \infty$, the monoid $P$ is isomorphic to a nontrivial numerical monoid. The proposition now follows from the fact that nontrivial numerical monoids have finitely many molecules.
\end{proof}

\begin{corollary}
	If $P$ is a Puiseux monoid, then $|\mathcal{M}(P)| \neq 1$.
\end{corollary}

The set of atoms of a numerical monoid is always strictly contained in its set of molecules. However, there are many atomic Puiseux monoids which do not satisfy such a property. Before proceeding to formalize this observation, recall that if two Puiseux monoids $P$ and $P'$ are isomorphic, then there exists $q \in \qq_{>0}$ such that $P' = qP$; this is a consequence of~Proposition~\ref{chap:algebraic background}.\ref{prop:homomorphisms between PM}.

\begin{theorem}[cf. Theorem~\ref{thm:more molecules than atoms in any NS}(1)] \label{thm:F(M) equals A(M)}
	There are infinitely many non-isomorphic atomic Puiseux monoids $P$ satisfying that $\mathcal{M}(P) = \mathcal{A}(P)$.
\end{theorem}

\begin{proof}
	Let $\mathcal{S} = \{S_n : n \in \nn\}$ be a collection of infinite and pairwise-disjoint sets of primes. Now take $S = S_n$ for some arbitrary $n \in \nn$, and label the primes in $S$ strictly increasingly by $p_1, p_2, \dots$. Recall that $\mathsf{D}_S(r)$ denotes the set of primes in $S$ dividing $\mathsf{d}(r)$ and that $\mathsf{D}_S(R) = \cup_{r \in R} \mathsf{D}_S(r)$ for $R \subseteq \qq_{> 0}$. We proceed to construct a Puiseux monoid $P_S$ satisfying that $\mathsf{D}_S(P_S) = S$.

	Take $P_1 := \langle 1/p_1 \rangle$ and $P_2 := \langle P_1, 2/(p_1p_2) \rangle$. In general, suppose that $P_k$ is a finitely generated Puiseux monoid such that $\mathsf{D}_S(P_k) \subset S$, and let $r_1, \dots, r_{n_k}$ be all the elements in $P_k$ which can be written as a sum of two atoms. Clearly, $n_k \ge 1$. Because $|S| = \infty$, one can take $p'_1, \dots, p'_{n_k}$ to be primes in $S \! \setminus \! \mathsf{D}_S(P_k)$ satisfying that $p'_i \nmid \mathsf{n}(r_i)$. Now consider the following finitely generated Puiseux monoid
	\[
		P_{k+1} := \bigg\langle P_k \cup \bigg\{ \frac{r_1}{p'_1}, \dots, \frac{r_{n_k}}{p'_{n_k}} \bigg\} \bigg\rangle.
	\]
	For every $i \in \{1,\dots,n_k\}$, there is only one element in $P_k \cup \{r_1/p'_1, \dots, r_{n_k}/p'_{n_k}\}$ whose denominator is divisible by $p'_i$, namely $r_i/p'_i$. Therefore $r_i/p'_i \in \mathcal{A}(P_{k+1})$ for $i=1, \dots, n_k$. To check that $\mathcal{A}(P_k) \subset \mathcal{A}(P_{k+1})$, fix $a \in \mathcal{A}(P_k)$ and take
	\begin{equation} \label{eq:FM equals AM}
		z := \sum_{i=1}^m \alpha_i a_i + \sum_{i=1}^{n_k} \beta_i \frac{r_i}{p'_i} \in \mathsf{Z}_{P_{k+1}}(a),
	\end{equation}
	where $a_1, \dots, a_k$ are pairwise distinct atoms in $\mathcal{A}(P_{k+1}) \cap P_k$ and $\alpha_i, \beta_j$ are nonnegative coefficients for $i = 1,\dots,m$ and $j = 1,\dots, n_k$. In particular, $a_1, \dots, a_k \in \mathcal{A}(P_k)$. For each $i=1,\dots,n_k$, the fact that the $p'_i$-adic valuation of $a$ is nonnegative implies that $p'_i \mid \beta_i$. Hence
	\[
		a = \sum_{i=1}^m \alpha_i a_i + \sum_{i=1}^{n_k} \beta'_i r_i,
	\]
	where $\beta'_i = \beta_i/p'_i \in \nn_0$ for $i = 1,\dots,n_k$. Since $r_i \in \mathcal{A}(P_k) + \mathcal{A}(P_k)$ and $(\beta_i/p'_i)r_i \mid_{P_k} a$ for every $i=1,\dots,n_k$, one obtains that $\beta_1 = \dots = \beta_{n_k} = 0$. As a result, $a = \sum_{i=1}^m \alpha_i a_i$. Because $a \in \mathcal{A}(P_k)$, the factorization $\sum_{i=1}^m \alpha_i a_i$ in $\mathsf{Z}_{P_k}(a)$ must have length $1$, i.e, $\sum_{i=1}^m \alpha_i = 1$. Thus, $\sum_{i=1}^m \alpha_i + \sum_{i=1}^{n_k} \beta_i =~1$, which means that $z$ has length $1$ and so $a \in \mathcal{A}(P_{k+1})$. As a result, the inclusion $\mathcal{A}(P_k) \subseteq \mathcal{A}(P_{k+1})$ holds. Observe that because $n_k \ge 1$, the previous containment must be strict. Now set
	\[
		P_S = \bigcup_{k \in \nn} P_k.
	\]
	Let us verify that $P_S$ is an atomic monoid satisfying that $\mathcal{A}(P_S) = \cup_{k \in \nn} \mathcal{A}(P_k)$. Since $P_k$ is atomic for every $k \in \nn$, the inclusion chain $\mathcal{A}(P_1) \subset \mathcal{A}(P_2) \subset \dots$ implies that $P_1 \subset P_2 \subset \dots$. In addition, if $a_0 = a_1 + \dots + a_m$ for $m \in \nn$ and $a_0, a_1, \dots, a_m \in P_S$, then $a_0 = a_1 + \dots + a_m$ will also hold in $P_k$ for some $k \in \nn$ large enough. This immediately implies that $\cup_{k \in \nn} \mathcal{A}(P_k) \subseteq \mathcal{A}(P_S)$. Since the reverse inclusion follows trivially, $\mathcal{A}(P_S) = \cup_{k \in \nn} \mathcal{A}(P_k)$. To check that $P_S$ is atomic, take $x \in P_S^\bullet$. Then there exists $k \in \nn$ such that $x \in P_k$ and, because $P_k$ is atomic, $x \in \langle \mathcal{A}(P_k) \rangle \subseteq \langle \mathcal{A}(P_S) \rangle$. Hence $P_S$ is atomic.

	To check that $\mathcal{M}(P_S) = \mathcal{A}(P_S)$, suppose that $m$ is a molecule of $P_S$, and then take $K \in \nn$ such that $m \in P_k$ for every $k \ge K$. Since $\mathcal{A}(P_k) \subset \mathcal{A}(P_{k+1}) \subset \dots$, we have that $\mathsf{Z}_{P_k}(m) \subseteq \mathsf{Z}_{P_{k+1}}(m) \subseteq \dots$. Moreover, $\cup_{k \ge K} \mathcal{A}(P_k) = \mathcal{A}(P_S)$ implies that $\cup_{k \ge K} \mathsf{Z}_{P_k}(m) = \mathsf{Z}_{P_S}(m)$. Now suppose for a contradiction that $m = \sum_{j=1}^i a_j$ for $i \in \nn_{\ge 2}$, where $a_1, \dots, a_i \in \mathcal{A}(P_S)$. Take $j \in \nn_{\ge K}$ such that $a_1, \dots, a_i \in \mathcal{A}(P_j)$. Then the way in which $P_{j+1}$ was constructed ensures that $|\mathsf{Z}_{P_{j+1}}(a_1 + a_2)| \ge 2$ and, therefore, $|\mathsf{Z}_{P_{j+1}}(m)| \ge 2$. As $\mathsf{Z}_{P_{j+1}}(m) \subseteq \mathsf{Z}_{P_S}(m)$, it follows that $|\mathsf{Z}_{P_S}(m)| \ge 2$, which contradicts that $m$ is a molecule. Hence $\mathcal{M}(P_S) = \mathcal{A}(P_S)$.

	Finally, we argue that the monoids constructed are not isomorphic. Let $S$ and $S'$ be two distinct members of the collection $\mathcal{S}$ and suppose, by way of contradiction, that $\psi \colon P_S \to P_{S'}$ is a monoid isomorphism. Because the only homomorphisms of Puiseux monoids are given by rational multiplications, there exists $q \in \qq_{> 0}$ such that $P_{S'} = q P_S$. In this case, all but finitely many primes in $\mathsf{D}_\pp(P_S)$ belong to $\mathsf{D}_\pp(P_{S'})$. Since $\mathsf{D}_\pp(P_S) \cap \mathsf{D}_\pp(P_{S'}) = \emptyset$ when $S \neq S'$, we get a contradiction.
\end{proof}
\medskip

\section{Molecules of Prime Reciprocal Monoids} \label{sec:mol prime reciprocals}

In this section, we focus our attention on the class consisting of all prime reciprocal Puiseux monoids.

\begin{proposition}[cf. Theorem~\ref{thm:more molecules than atoms in any NS}(1)] \label{prop:PPM has infinitely many molecules that are not atoms}
	There exist infinitely many non-finitely generated atomic Puiseux monoids $P$ such that $|\mathcal{M}(P) \! \setminus \! \mathcal{A}(P)| = \infty$.
\end{proposition}

\begin{proof}
	As in the proof of Theorem~\ref{thm:F(M) equals A(M)}, let $\mathcal{S} = \{S_n : n \in \nn\}$ be a collection of infinite and pairwise-disjoint subsets of $\pp \setminus \{2\}$. For every $n \in \nn$, let $P_n$ be a prime reciprocal Puiseux monoid over $S_n$. Fix $a \in \mathcal{A}(P_n)$, and take a factorization
	\[
		z := \sum_{i=1}^k \alpha_i a_i  \in \mathsf{Z}(2a),
	\]
	for some $k \in \nn$, pairwise distinct atoms $a_1, \dots, a_k$, and $\alpha_1,\dots,\alpha_k \in \nn_0$. Since $\mathsf{d}(a) \neq 2$, after applying the $\mathsf{d}(a)$-adic valuation on both sides of the equality $2a = \sum_{i=1}^t \alpha_i a_i$, one obtains that $z = 2a$. So $2a \in \mathcal{M}(P_n) \setminus \mathcal{A}(P_n)$ and, as a result, $|\mathcal{M}(P_n) \setminus \mathcal{A}(P_n)| = \infty$. Now suppose, by way of contradiction, that $P_i \cong P_j$ for some $i,j \in \nn$ with $i \neq j$. Since the only isomorphisms of Puiseux monoids are given by rational multiplication, there exists $q \in \qq_{> 0}$ such that $P_j = q P_i$. However, this implies that only finitely many primes in $\mathsf{d}(P_i)$ are not contained in $\mathsf{d}(P_j)$, which contradicts that $S_i \cap S_j = \emptyset$. Hence no two monoids in $\{P_n : n \in \nn\}$ are isomorphic, and the proposition follows.
\end{proof}

Before characterizing the molecules of prime reciprocal monoids, let us introduce the concept of maximal multiplicity. Let $P$ be a Puiseux monoid. For $x \in P$ and $a \in \mathcal{A}(P)$ we define the \emph{maximal multiplicity} of $a$ in $x$ to be
\[
	\mathsf{m}(a,x) := \max\{n \in \nn_0 : na \mid_P x\}.
\]

\begin{proposition} \label{prop:sufficient condition for molecules in PPM}
	Let $P$ be a prime reciprocal monoid, and let $x \in P$. If $\mathsf{m}(a,x) < \mathsf{d}(a)$ for all $a \in \mathcal{A}(P)$, then $x \in \mathcal{M}(P)$.
\end{proposition}

\begin{proof}
	Suppose, by way of contradiction, that $x \notin \mathcal{M}(P)$. Then there exist $k \in \nn$, elements $\alpha_i, \beta_i \in \nn_0$ (for $i=1,\dots, k$), and pairwise distinct atoms $a_1, \dots, a_k$ such that
	\[
		z:= \sum_{i=1}^k \alpha_i a_i \ \text{ and } \ z' := \sum_{i=1}^k \beta_i a_i
	\]
	are two distinct factorizations in $\mathsf{Z}(x)$. As $z \neq z'$, there is an index $i \in \{1,\dots,k\}$ such that $\alpha_i \neq \beta_i$. Now we can apply the $\mathsf{d}(a_i)$-adic valuation to both sides of the equality
	\[
		\sum_{i=1}^k \alpha_i a_i = \sum_{i=1}^k \beta_i a_i
	\]
	to verify that $\mathsf{d}(a_i) \mid \beta_i - \alpha_i$. As $\alpha_i \neq \beta_i$, we obtain that
	\[
		\mathsf{m}(a_i, x) \ge \max\{\alpha_i, \beta_i\} \ge \mathsf{d}(a_i).
	\]
	However, this contradicts the fact that $\mathsf{m}(a,x) < \mathsf{d}(a)$ for all $a \in \mathcal{A}(P)$. As a consequence, $x \in \mathcal{M}(P)$.
\end{proof}

For $S \subseteq \pp$, we call the monoid $E_S := \langle 1/p : p \in S \rangle$ the \emph{elementary} prime reciprocal monoid over $S$; if $S = \pp$ we say that $E_S$ is \emph{the} elementary prime reciprocal monoid. It was proved in \cite[Section~5]{GG19} that every submonoid of the elementary prime reciprocal monoid is atomic. This gives a large class of non-finitely generated atomic Puiseux monoids, which contains each prime reciprocal monoid.

\begin{proposition} \label{prop:factorial equivalence for elementary primary monoids}
	Let $S$ be an infinite set of primes, and let $E_S$ be the elementary prime reciprocal monoid over $S$. For $x \in E_S$, the following conditions are equivalent:
	\begin{enumerate}
		\item $x \in \mathcal{M}(E_S)$;

		\item $1$ does not divide $x$ in $E_S$;

		\item$\mathsf{m}(a,x) < \mathsf{d}(a)$ for all $a \in \mathcal{A}(E_S)$;

		\item If $a_1, \dots, a_n \in \mathcal{A}(E_S)$ are distinct atoms and $\alpha_1, \dots, \alpha_n \in \nn_0$ satisfy that $\sum_{j=1}^n \alpha_i a_i \in \mathsf{Z}(x)$, then $\alpha_j < \mathsf{d}(a_j)$ for each $j = 1,\dots,n$.
	\end{enumerate}
\end{proposition}

\begin{proof}
	First, let us recall that since $E_S$ is atomic, $\mathcal{M}(E_S)$ is divisor-closed. On the other hand, note that for any two distinct atoms $a,a' \in \mathcal{A}(E_S)$, both factorizations $\mathsf{d}(a) \, a$ and $\mathsf{d}(a') \, a'$ are in $\mathsf{Z}(1)$. Therefore $1 \notin \mathcal{M}(E_S)$. Because the set of molecules of $E_S$ is divisor-closed, $1 \nmid_{E_S} m$ for any $m \in \mathcal{M}(E_S)$; in particular, $1 \nmid_{E_S} x$. Thus, (1) implies (2). If $\mathsf{m}(a,x) \ge \mathsf{d}(a)$ for $a \in \mathcal{A}(E_S)$, then
	\[
		x = \mathsf{m}(a,x) \, a + y = 1 + (\mathsf{m}(a,x) - \mathsf{d}(a)) \, a + y
	\]
	for some $y \in E_S$. As a result, $1 \mid_{E_S} x$, from which we can conclude that~(2) implies (3). It is obvious that (3) and (4) are equivalent conditions. Finally, the fact that (3) implies~(1) follows from Proposition~\ref{prop:sufficient condition for molecules in PPM}.
\end{proof}

\begin{corollary}
	Let $S$ be an infinite set of primes, and let $E_S$ be the elementary prime reciprocal monoid over $S$. Then $|\mathsf{Z}(x)| = \infty$ for all $x \notin \mathcal{M}(E_S)$.
\end{corollary}

In order to describe the set of molecules of an arbitrary prime reciprocal monoid, we need to cast its atoms into two categories.

\begin{definition}
	Let $P$ be a prime reciprocal monoid. We say that $a \in \mathcal{A}(P)$ is \emph{stable} if the set $\{a' \in \mathcal{A}(P) : \mathsf{n}(a') = \mathsf{n}(a)\}$ is infinite, otherwise we say that $a$ is \emph{unstable}. If every atom of $P$ is stable (resp., unstable), then we call $P$ \emph{stable} (resp., \emph{unstable}).
\end{definition}

For a prime reciprocal monoid $P$, we let $\mathcal{S}(P)$ denote the submonoid of $P$ generated by the set of stable atoms. Similarly, we let $\mathcal{U}(P)$ denote the submonoid of $P$ generated by the set of unstable atoms. Clearly, $P$ is stable (resp., unstable) if and only if $P = \mathcal{S}(P)$ (resp., $P = \mathcal{U}(P)$). In addition, $P = \mathcal{S}(P) + \mathcal{U}(P)$, and $\mathcal{S}(P) \cap \mathcal{U}(P)$ is trivial only when either $\mathcal{S}(P)$ or $\mathcal{U}(P)$ is trivial. Clearly, if $P$ is stable, then it cannot be finitely generated. Finally, we say that $u \in \mathcal{U}(P)$ is \emph{absolutely unstable} provided that $u$ is not divisible by any stable atom in $P$, and we let $\mathcal{U}^a(P)$ denote the set of all absolutely unstable elements of~$P$.

\begin{example}
	Let $(p_n)_{n \in \mathbb{N}}$ be the strictly increasing sequence with underlying set $\pp \setminus \{2\}$, and consider the prime reciprocal monoid $P$ defined as
	\[
		P := \bigg\langle \frac{3 + (-1)^n}{p_{2n-1}}, \frac{p_{2n} - 1}{p_{2n}} \ : \ n \in \nn \bigg\rangle.
	\]
	Set $a_n = \frac{3 + (-1)^n}{p_{2n-1}}$ and $b_n =  \frac{p_{2n} - 1}{p_{2n}}$. One can readily verify that $P$ is an atomic monoid with $\mathcal{A}(P) = \{a_n, b_n : n \in \nn\}$. As both sets
	\[
		\{n \in \nn : \mathsf{n}(a_n) = 2\} \quad \text{ and } \quad \{n \in \nn : \mathsf{n}(a_n) = 4\}
	\]
	have infinite cardinality, $a_n$ is a stable atom for every $n \in \nn$. In addition, since $(\mathsf{n}(b_n))_{n \in \mathbb{N}}$ is a strictly increasing sequence bounded below by $\mathsf{n}(b_1) = 4$ and $\mathsf{n}(a_n) \in \{2,4\}$, we have that $b_n$ is an unstable atom for every $n \in \nn_{\ge 2}$. Also, notice that $4/3 = 2a_1 \in \mathcal{S}(P)$, but $4/3 \notin \mathcal{U}(P)$ because $\mathsf{d}(4/3) = 3 \notin \mathsf{d}(\mathcal{U}(P))$. Furthermore, for every $n \in \nn$ the element $u_n := (p_{2n} - 1) b_n \in \mathcal{U}(P)$ is not in $\mathcal{S}(P)$ because $p_{2n} = \mathsf{d}(u_n) \notin \mathsf{d}(\mathcal{S}(P))$. However, $\mathcal{S}(P) \cap \mathcal{U}(P) \ne \emptyset$ since the element $4 = 6 a_1 = 5 b_1$ belongs to both $\mathcal{S}(P)$ and $\mathcal{U}(P)$. Finally, we claim that $2b_n$ is absolutely unstable for every $n \in \nn$. If this were not the case, then $2b_k \notin \mathcal{M}(P)$ for some $k \in \nn$. By Proposition~\ref{prop:sufficient condition for molecules in PPM} there exists $a \in \mathcal{A}(P)$ such that $\mathsf{m}(a, 2b_k) \ge \mathsf{d}(a)$. In this case, one would obtain that $2b_k \ge \mathsf{m}(a,2b_k)a \ge \mathsf{d}(a)a = \mathsf{n}(a) \ge 2$, contradicting that $b_n < 1$ for every $n \in \nn$. Thus, $2b_n \in \mathcal{U}^a(P)$ for every $n \in \nn$.
\end{example}

\begin{proposition} \label{prop: characterization of factorial elements in stable PPM}
	Let $P$ be a prime reciprocal monoid that is stable, and let $x \in P$. Then $x \in \mathcal{M}(P)$ if and only if~$\mathsf{n}(a)$ does not divide $x$ in $P$ for any $a \in \mathcal{A}(P)$.
\end{proposition}

\begin{proof}
	For the direct implication, assume that $x \in \mathcal{M}(P)$ and suppose, by way of contradiction, that $\mathsf{n}(a) \mid_P x$ for some $a \in \mathcal{A}(P)$. Since $a$ is a stable atom, there exist $p_1, p_2 \in \pp$ with $p_1 \neq p_2$ such that $\gcd(p_1 p_2, \mathsf{n}(a)) = 1$ and $\mathsf{n}(a)/p_1, \mathsf{n}(a)/p_2 \in \mathcal{A}(P)$. As $\mathsf{n}(a) \mid_P x$, we can take $a_1, \dots, a_k \in \mathcal{A}(P)$ such that $x = \mathsf{n}(a) + a_1 + \dots + a_k$. Therefore
	\[
		p_1 \frac{\mathsf{n}(a)}{p_1} + a_1 + \dots + a_k \ \text{ and } \ p_2 \frac{\mathsf{n}(a)}{p_2} + a_1 + \dots + a_k
	\]
	are two distinct factorizations in $\mathsf{Z}(x)$, contradicting that $x$ is a molecule.
	Conversely, suppose that $x$ is not a molecule. Consider two distinct factorizations $z := \sum_{i=1}^k \alpha_i a_i$ and $z' := \sum_{i=1}^k \beta_i a_i$ in $\mathsf{Z}(x)$, where $k \in \nn$, $\alpha_i, \beta_i \in \nn_0$, and $a_1, \dots, a_k \in \mathcal{A}(P)$ are pairwise distinct atoms. Pick an index $j \in \{1, \dots, k\}$ such that $\alpha_j \neq \beta_j$ and assume, without loss of generality, that $\alpha_j < \beta_j$. After applying the $\mathsf{d}(a_j)$-adic valuations on both sides of the equality
	\[
		\sum_{i=1}^k \alpha_i a_i = \sum_{i=1}^k \beta_i a_i
	\]
	one finds that the prime $\mathsf{d}(a_j)$ divides $\beta_j - \alpha_j$. Therefore $\beta_j > \mathsf{d}(a_j)$ and so
	\[
		x = \mathsf{n}(a_j) + (\beta_j - \mathsf{d}(a_j))a_j + \sum_{i \neq j} \alpha_i a_i.
	\vspace{-6pt}
	\]
	Hence $\mathsf{n}(a_j) \mid_P x$, which concludes the proof.
\end{proof}

Observe that the reverse implication of Proposition~\ref{prop: characterization of factorial elements in stable PPM} does not require $\mathcal{S}(P) = P$. However, the stability of $P$ is required for the direct implication to hold as the following example illustrates.

\begin{example}
	Let $(p_n)_{n \in \mathbb{N}}$ be the strictly increasing sequence with underlying set $\pp \setminus \{2\}$, and consider the unstable prime reciprocal monoid
	\[
		P := \bigg\langle \frac 12, \frac{p_n^2 -1}{p_n} \, : \, n \in \nn \bigg\rangle.
	\]
	Because the smallest two atoms of $P$ are $1/2$ and $8/3$, it immediately follows that $m := 2(1/2) + 8/3 \notin \langle 1/2 \rangle$ must be a molecule of $P$. In addition, notice that $1 = \mathsf{n}(1/2)$ divides $m$ in $P$.
\end{example}

We conclude this section characterizing the molecules of prime reciprocal monoids.

\begin{theorem} \label{thm:characterization of factorial elements in PPM}
	Let $P$ be a prime reciprocal monoid. Then $x \in P$ is a molecule if and only if $x = s + u$ for some $s \in \mathcal{S}(P) \cap \mathcal{M}(P)$ and $u \in \mathcal{U}^a(P) \cap \mathcal{M}(P)$.
\end{theorem}

\begin{proof}
	First, suppose that $x$ is a molecule. As $P = \mathcal{S}(P) + \mathcal{U}(P)$, there exist $s \in \mathcal{S}(P)$ and $u \in \mathcal{U}(P)$ such that $x = s + u$. The fact that $x \in \mathcal{M}(P)$ guarantees that $s,u \in \mathcal{M}(P)$. On the other hand, since $|\mathsf{Z}(u)| = 1$ and $u$ can be factored using only unstable atoms, $u$ cannot be divisible by any stable atom in $P$. Thus, $u \in \mathcal{U}^a(P)$, and the direct implication follows.

	For the reverse implication, assume that $x = s + u$, where $s \in \mathcal{S}(P) \cap \mathcal{M}(P)$ and $u \in \mathcal{U}^a(P) \cap \mathcal{M}(P)$. We first check that $x$ can be uniquely expressed as a sum of two elements $s$ and $u$ contained in the sets $\mathcal{S}(P) \cap \mathcal{M}(P)$ and $\mathcal{U}^a(P) \cap \mathcal{M}(P)$, respectively. To do this, suppose that $x = s + u = s' + u'$, where $s' \in \mathcal{S}(P) \cap \mathcal{M}(P)$ and $u' \in \mathcal{U}^a(P) \cap \mathcal{M}(P)$. Take pairwise distinct stable atoms $a_1, \dots, a_k$ of $P$ for some $k \in \nn$ such that $z = \sum_{i=1}^k \alpha_i a_i \in \mathsf{Z}_P(s)$ and $z' = \sum_{i=1}^k \alpha'_i a_i \in \mathsf{Z}_P(s')$, where $\alpha_j, \alpha'_j \in \nn_0$ for $j = 1, \dots, k$. Because $u$ and $u'$ are absolutely unstable elements, they are not divisible in $P$ by any of the atoms $a_i$'s. Thus, $\mathsf{d}(a_j) \nmid \mathsf{d}(u)$ and $\mathsf{d}(a_j) \nmid \mathsf{d}(u')$ for any $j \in \{1,\dots, k\}$. Now for each $j = 1,\dots,k$ we can apply the $\mathsf{d}(a_j)$-adic valuation in both sides of the equality
	\[
		u + \sum_{i=1}^k \alpha_i a_i  = u' + \sum_{i=1}^k \alpha'_i a_i
	\]
	to conclude that the prime $\mathsf{d}(a_j)$ must divide $\alpha_j - \alpha'_j$. Therefore either $z = z'$ or there exists $j \in \{1,\dots,k\}$ such that $|\alpha_j - \alpha'_j| > \mathsf{d}(a_j)$. Suppose that $|\alpha_j - \alpha'_j| > \mathsf{d}(a_j)$ for some $j$, and say $\alpha_j > \alpha'_j$. As $\alpha_j > \mathsf{d}(a_j)$, one can replace $\alpha_j a_j$ by $(\alpha_j - \mathsf{d}(a_j))a_j + \mathsf{n}(a_j)$ in $s = \phi(z) = \alpha_1 a_1 + \dots + \alpha_k a_k$ to find that $\mathsf{n}(a_j)$ divides $s$ in $\mathcal{S}(P)$, which contradicts Proposition~\ref{prop: characterization of factorial elements in stable PPM}. Then we have $z = z'$. Therefore $s' = s$ and $u' = u$.

	Finally, we argue that $x \in \mathcal{M}(P)$. Write $x = \sum_{i=1}^{\ell} \gamma_i a_i + \sum_{i=1}^\ell \beta_i b_i$ for $\ell \in \nn_{\ge k}$, pairwise distinct stable atoms $a_1, \dots, a_\ell$ (where $a_1, \dots, a_k$ are the atoms showing up in $z$), pairwise distinct unstable atoms $b_1, \dots, b_\ell$, and coefficients $\gamma_i, \beta_i \in \nn_0$ for every $i=1,\dots,\ell$. Set $z''' := \sum_{i=1}^{\ell} \gamma_i a_i$ and $w''' = \sum_{i=1}^\ell \beta_i b_i$. Note that, \emph{a priori}, $\phi(z''')$ and $\phi(w''')$ are not necessarily molecules.  As in the previous paragraph, we can apply $\mathsf{d}(a_j)$-adic valuation to both sides of the equality
	\[
		u + \sum_{i=1}^k \alpha_i a_i = \sum_{i=1}^{\ell} \gamma_i a_i + \sum_{i=1}^\ell \beta_i b_i
	\]
	to find that $z''' = z$. Hence $\phi(z''') = s$ and $\phi(w''') = u$ are both molecules. Therefore $z'''$ must be the unique factorization of $s$, while $w'''$ must be the unique factorization of $u$. As a result, $x \in \mathcal{M}(P)$.
\end{proof}
\medskip


TITLE: Problems in BQP but conjectured to be outside P
QUESTION [20 upvotes]: Wikipedia listed four problems that are in $BQP$ but conjectured to be outside $P$: Integer factorization; Discrete logarithm; Simulation of quantum systems; Computing the Jones polynomial at certain roots of unity.
Are there any other such problems?

REPLY [23 votes]: To have a list of such problems, you can look at the list of superpolynomial speed improvement at the quantum algorithm zoo (QAZ). The list below is based on  this (see QAZ for precise definitions and references. This is another way to say I don’t even pretend to understand many of the problems of this list!)
Algebraic and Number Theoretic Problems
If I’m not mistaken, all problems listed before the Abelian hidden subgroup problem are special cases of it.

Factorization
Discrete logarithm
Pell’s Equation. Factoring reduces to Pell’s equation.
Principal Ideal Ideal problem. Pell’s equation reduces to this problem, which therefore at least as hard as factoring.
Unit Group problem
Class Group problem
Gauß Sums estimation
Matrix Elements of Group Representations
Group Order and Membership
The Abelian hidden subgroup problem
Some (but not all) non-Abelian hidden subgroup problems
Some (but not all) problems phrased as special cases of the hidden shift problem
Some (but not all) Hidden Nonlinear Structures problems
Exploring some graphs (Welded trees)
Group Isomorphism, for Abelian and some non-Abelian groups
Find some properties of Finite Rings and Ideals

Approximation and Simulation

Quantum simulation. Obviously $BQP$-complete
Computing some knot-invariants, including HOMFLY polynomial, of which the Jones polynomial is a special case. Some of them are $BQP$-complete
Computing some Three-manifold Invariants. Some of them are $BQP$-complete.
Estimating the thermodynamic partition function of some classical systems
Computing Zeta Functions over finite fields
A string rewriting problem is  $\mathit{PromiseBQP}$-complete
approximating matrix elements of powers of exponentially large sparse matrices.

Algorithm I don’t really  get.
These are mainly algorithms where QAZ claims a superpolynomial increase, but I don’t get why the original problem is supposed to be out of $P$. That said, I’ll bet lots of my money on QAZ being right and myself being wrong on that.

Pattern matching for large enough ($>\log(n)$) patterns
Some linear system problems, in $P$ but having a $\mathrm{polylog}$ quantum algorithm if the linear system is given as an oracle.
Computing the Electrical Resistance of a graph,has a $\mathrm{polylog}$ quantum algorithm if the electric circuit is given as an oracle
Weight Enumerators problem. Something related to code and partition functions, but I don’t understand what it is about.

$P$ problems 1st proved to be in $BQP$ and then in $P$
Here are some problems where an efficient quantum algorithm has been published before a classical one. In other words, they were once conjectured to be in $BQP$ but not in $P$, but this conjecture is now invalidated.

Satisfying more than $(\tfrac12-\tfrac{\text{constant}}{D})N$ (but less than $\left(\tfrac12-\tfrac{1}{22D^{3/4}}\right)N$) constraints of the  Max E3LIN2 problem. As pointed by Juan Berego Vega in the comments : there is now a classical algorithm for $(\tfrac12-\tfrac{\text{constant}}{\sqrt{D}})N$, which was motivated by the quantum result. (Blog post on this result, paper 1, paper2)
Recommendation systems (see Scott Aaronson’s blog post  for a more detailed explanation). Recommendation system — à la Netflix/Amazon/etc.— can be seen as completing a sparse $m×n$ matrix of low rank $k$ with very incomplete data. Known classical algorithm where polynomial in $m$, $n$ ad $k$. If the matrix is given as an oracle, Iordanis Kerenidis an Anupam Prakash found a $\mathrm{poly}(k)\mathrm{polylog}(mn)$ quantum algorithm finding samples of the unknown elements of the matrix in 2016 (paper). In 2018, while trying to prove this scaling is impossible to reach with a classical machine, Ewin Tang actually found a classical algorithm achieving the same performance under the same conditions (paper available here and here).


TITLE: The parametrisation (cos(t),sin(t+a)) almost always seems to describe a rotated ellipse. How can I prove it?
QUESTION [0 upvotes]: I was wondering how a curve would look like if you have two hands of a clock moving at the same speed from different positions while you track the x of one hand and the y of the other hand over time. That's how I got (cos(t),sin(t+a)) where t is the time and a the angle between the hands.
It turned out to almost always describe an ellipse tilted by 45°. I have no idea why it is always tilted by that angle and how to show this parametrisation describes an ellipse.
My failed tries:
1. Rotating (cos(t),sin(t+a)) by 45° and showing that the rotated points suffice the $\frac{x^2}{u^2}+\frac{y^2}{v^2}=1$ equation.

Using the distance to focal points definition for (cos(t),sin(t+a))

Maybe it's not possible to show in general because of the special cases where
(cos(t),sin(t+a)) describes a line. Please help!
I also failed showing it for a special a.
Sry for my bad english. I'm no native speaker

REPLY [0 votes]: $$
(\cos(t),\sin(t+a))=(\cos(t),\sin(t)\cos(a)+\cos(t)\sin(a))
$$
$$
\big\Updownarrow
$$
$$
(y-\sin(a)x)^2+\cos^2(a)x^2=\cos^2(a)
$$
$$
\big\Updownarrow
$$
$$
\begin{align}
2\cos^2(a)
&=2\begin{bmatrix}x&y\end{bmatrix}
\begin{bmatrix}
1&-\sin(a)\\
-\sin(a)&1
\end{bmatrix}
\begin{bmatrix}x\\y\end{bmatrix}\\
&=\begin{bmatrix}x&y\end{bmatrix}
\begin{bmatrix}
1&1\\
1&-1
\end{bmatrix}
\begin{bmatrix}
1-\sin(a)&0\\
0&1+\sin(a)
\end{bmatrix}
\begin{bmatrix}
1&1\\
1&-1
\end{bmatrix}
\begin{bmatrix}x\\y\end{bmatrix}\\[6pt]
&=(1-\sin(a))(x+y)^2+(1+\sin(a))(x-y)^2
\end{align}
$$
Therefore,
$$
\frac{\left(\frac{x+y}{\sqrt2}\right)^2}{1+\sin(a)}+\frac{\left(\frac{x-y}{\sqrt2}\right)^2}{1-\sin(a)}=1
$$
which is an ellipse with semi-major and semi-minor axes of $\sqrt{1+\sin(a)}$ and $\sqrt{1-\sin(a)}$ rotated by $\frac\pi4$.


text:
\begin{document}
\title{Convergence to equilibrium in competitive Lotka-Volterra equations}

\date{}
\author{Nicolas Champagnat$^{1}$, Pierre-Emmanuel Jabin$^{1,2}$,
  Ga\"el Raoul$^{3}$}

\footnotetext[1]{TOSCA project-team, INRIA Sophia Antipolis --
  M\'editerran\'ee, 2004 rte des Lucioles, BP.\ 93, 06902 Sophia
  Antipolis Cedex, France, \\
E-mail: \texttt{Nicolas.Champagnat@sophia.inria.fr}}

\footnotetext[2]{Laboratoire J.-A. Dieudonn\'e, Universit\'e de Nice --
  Sophia Antipolis, Parc Valrose, 06108 Nice Cedex 02, France, E-mail:
  \texttt{jabin@unice.fr}}
\footnotetext[3]{DAMTP, CMS, University of Cambridge, Wilberforce Road,
Cambridge CB3 0WA, United Kingdom, Email: \texttt{g.raoul@damtp.cam.ac.uk}}
\maketitle{}
\selectlanguage{english}
\noindent{\bf Abstract.} We study a generalized system of ODE's
modeling a finite number of biological populations in a competitive
interaction. We adapt the techniques in \cite{JR} and
\cite{CJ} to prove the convergence to a unique stable equilibrium.

\selectlanguage{french}
\noindent{\bf R\'esum\'e.} Nous \'etudions un syst\`eme
g\'en\'eralis\'e d'\'equations diff\'erentielles mod\'elisant un
nombre fini de populations biologiques en interaction
{com\-p\'e\-ti\-tive}. En adaptant les techniques de \cite{JR} et \cite{CJ},
nous prouvons la convergence vers un unique \'equilibre stable.

\bigskip

\noindent{\bf Version fran\c caise abr\'eg\'ee.}

Nous \'etudions le comportement en temps grand de mod\`eles de
dynamique de populations. On consid\`ere un nombre fini de
sous-populations, correspondant chacune \`a un trait ou type diff\'erent. Ces
populations interagissent entre elles de fa\c con comp\'etitive. En
notant $n_i(t)$ l'effectif de la sous-population num\'ero $i$, un des
mod\`eles les plus classiques est le syst\`eme de Lotka-Volterra comp\'etitif
\[
\frac{d}{dt} n_i=(r_i-\sum_j b_{ij}\,n_j)\,n_i, \quad i=1\ldots N,
\]
o\`u $b_{ij}\geq 0$. On se place ici dans le cadre plus g\'en\'eral du
syst\`eme
\[
\frac{d}{dt} n_i(t)=\left[
r_i-\int_{\Omega} K_i(\alpha)\;L\left(\sum_j B_j(\alpha)\,
n_j(t)\right)\,dP(\alpha)\right]\;n_i(t),\quad i=1\ldots N
\]
avec $(\Omega,P)$ un espace  mesurable. Ce syst\`eme peut
s'interpr\^eter comme un mod\`ele avec ressources g\'en\'eralis\'ees.

En utilisant les techniques d\'evelopp\'ees dans \cite{JR} pour une
version continue du premier mod\`ele, et dans \cite{CJ}, on peut
facilement montrer
\medskip

\noindent{\bf Th\'eor\`eme} {\em
Supposons que $L$ est une fonction $C^1$ sur $\R$, positive sur $\R_+$, que
$K$ et $B$ sont des fonctions positives appartenant \`a
$L^\infty(dP(\alpha))\cap L^1(dP(\alpha))$ et que\\
\noindent $(i)$ (Comp\'etition stricte)
$L$ est strictement croissante et pour tout $1\leq i\leq n$,
$r_i<\int_\Omega K_i(\alpha)L(\infty)dP(\alpha)$
o\`u $L(\infty):=\lim_{x\rightarrow+\infty}L(x)\in(0,+\infty]$.\\
\noindent $(ii)$ (Sym\'etrie) Il existe $C_i> 0$
tq $B_i(\alpha)=C_i\,K_i(\alpha)$
\\
\noindent $(iii)$ (Non extinction)
 Pour tout $i$, $r_i>\int_{\Omega} K_i(d\alpha)L(0)\,dP(\alpha)$
\\
\noindent $(iv)$ (Non d\'eg\'en\'erescence)
Pour $I\subset \{1\ldots N\}$, soit $\R^I$ l'ensemble des $n\in\R^N$
tels que $n_i=0$ pour
tout $i\not\in I$. Pour tout $I\subset \{1\ldots N\}$ il y a au plus
un $n\in \R^{I}$ tq
\[
r_i-\int_{\Omega} K_i(\alpha)\;L\left(\sum_{j=1}^N B_j(\alpha)\,
n_j\right)\,dP(\alpha)=0,\quad \forall i\in I.
\]

Alors $\exists!\;\bar n=(\bar n_1,\ldots, \bar n_N)\in
\R_+^N\setminus \{0\}$, tel que pour toute solution $n(t)=( n_1,\ldots,
n_N)$ du mod\`ele g\'en\'eralis\'e avec une donn\'ee initiale $n_i(0)>0$
$\forall i$, on a
\[
n(t)\longrightarrow \bar n, \ quand\ t\rightarrow +\infty.
\]
}

\medskip
\noindent En particulier ce r\'esultat implique
\medskip

\noindent {\bf Proposition} {\em Supposons que $r_i>0$ pour tout $i$
  et que
la matrice $b_{ij}$ v\'erifie
\[
\exists C\in (\R_+^*)^N\ \mbox{tq}\ C_i\,
b_{ij}=b_{ji}\,C_j,\ \mbox{et}\ \sum_{ij}u_i\,u_j\,b_{ij}\,C_i>0\quad
\forall u\in\R^N\setminus \{0\},
\]
Alors $\exists!\;\bar n=(\bar n_1,\ldots, \bar n_N)\in
\R_+^N\setminus\{0\}$ tel que pour toute solution $n(t)=( n_1,\ldots,
n_N)$ du premier mod\`ele avec donn\'ee initiale $n_i(0)>0$ $\forall i$,
\[
n(t)\longrightarrow \bar n, \ quand\ t\rightarrow +\infty.
\]

}

\selectlanguage{english}

\section{Introduction}

We study the long time behaviour of models of population dynamics. We
consider a finite number of
subpopulations whose dynamics is governed by a system of competitive
ODEs (in the sense of Hirsch, see
e.g.~\cite{hirsch-88}). We denote by $n_i(t)$, $i=1\ldots N$, the
number of individuals
of the subpopulation $i$.

The most classical models are competitive Lotka-Volterra equations
\begin{equation}
\frac{d}{dt} n_i=(r_i-\sum_j b_{ij}\,n_j)\,n_i, \quad i=1\ldots N,\label{Eql}
\end{equation}
where $b_{ij}\geq 0$, and the models with a finite number of resources
\begin{equation}
\frac{d}{dt} n_i=(-d_i+\sum_{k=1}^K I_k\,\eta_{ki})\,n_i, \label{Eqr}
\end{equation}
where $\eta_{ki}\geq 0$ and the $I_k$ are given by the
Holling II functional response
\begin{equation*}
I_k=\frac{I_k^0}{1+\sum_{i=1}^N \eta_{ki}\,n_i}.
\end{equation*}

This type of system appears in biology when one studies the dynamics
of a system of interacting species (see
\cite{HS,Gop,Kri}). It also appears in Trait Substitution Sequence
models, where one considers a population
structured by a continuous phenotype (see equation \eqref{Eqlcont},
\eqref{continuous} on this matter), where
only a small number of traits are present (see
\cite{MGMJH,Cha}). These models have been used to develop the
theory of Adaptative Dynamics (see \cite{MGMJH,Cha,Di}).

Previous asymptotic studies on this type of equations concern either
very general properties (the existence of
a carrying simplex~\cite{hirsch-88}), or precise results but only for
low dimensional systems ($N\leq
3$~\cite{zeeman-93}), under strong assumptions of the coefficients
(for instance, the matrix $(b_{ij})$ is
supposed to be diagonal dominant, see \cite{HS}), or only on local
properties (the equilibrium population is
locally stable, or populations $n_i$ do not vanish).

Note that both equations \eqref{Eql} and \eqref{Eqr} may be
interpreted as discrete versions of
continuous models. To each subpopulation corresponds a phenotypic
trait $x_i\in \R^d$, and then posing
\begin{equation}
n(t,x)=\sum_{i=1}^N n_i(t) \delta_{x_i},\label{dirac}
\end{equation}
one finds that Eq. \eqref{Eql} for instance is equivalent to
\begin{equation}
\partial_t n(t,x)=(r(x)-\int_{\R^d} b(x,y)\,n(t,dy))\,n(t,x),\label{Eqlcont}
\end{equation}
with $r_i=r(x_i)$ and $b_{ij}=b(x_i,x_j)$.

The long time behaviour of the continuous model \eqref{Eqlcont}
(with bounded initial
data instead of Dirac masses) was studied in \cite{JR}. For a
symmetric $b$ defining a positive operator,
the convergence to the unique stable equilibrium was proved. For the
case with resources, the result is essentially contained in \cite{CJ},
which generalizes the derivation of \cite{DJMP}.

The study of the discrete or continuous models corresponds to slighty
different biological questions; in the
continuous case, it is for instance connected to the issue of
speciation, or how from a continuum of traits a
few well separated ones (the ``species'') are selected; in the
discrete case, one is rather concerned about
survival or extinction of each subpopulations. From a rigorous
mathematical point of view, a result in the
continuous case does not imply anything for the discrete one.  However
it is easy to apply the techniques developed in \cite{JR}
and \cite{CJ} to the discrete models;
that is our aim.

First of all,
we consider the very general equation
\begin{equation}
\frac{d}{dt} n_i(t)=\left[
r_i-\int_{\Omega} K_i(\alpha)\;L\left(\sum_j B_j(\alpha)\,
n_j(t)\right)\,dP(\alpha)\right]\;n_i(t),\quad i=1\ldots N,\label{discrete}
\end{equation}
with $(\Omega,P)$ any measurable space,  or in the continuous case
\begin{equation}
\partial_t n(t,x)=\left[
r(x)-\int_{\Omega} K(x,\alpha)\;L\left(\int_{\R^d} B(y,\alpha)\,
n(t,dy)\right)\,dP(\alpha)\right]\;n(t,x).\label{continuous}
\end{equation}
We prove the following
\begin{theorem}
  Assume that $L$ is $C^1$ on $\R$ and non negative on $\R_+$, that
  $K$ and $B$ are non negative, in $L^\infty(dP(\alpha))\cap
  L^1(dP(\alpha))$ and that\\
  \noindent $(i)$ (Strict competition) $L$ is strictly increasing and
  $r_i<\int_\Omega
  K_i(\alpha)L(\infty)\,dP(\alpha)$ for all $1\leq i\leq N$, where
  $L(\infty):=\lim_{x\rightarrow+\infty}L(x)\in(0,+\infty]$.\\
  \noindent $(ii)$ (Symmetry) There exists $C_i>0$
  s.t. $B_i(\alpha)=C_i\,K_i(\alpha)$
  \\
  \noindent $(iii)$ (Non extinction)
  For any $i$, $r_i>\int_{\Omega} K_i(\alpha)L(0)\,dP(\alpha)$
  \\
  \noindent $(iv)$ (Non degeneracy)
  For any subset $I\subset \{1\ldots N\}$, let $\R^I$ be the set of
  $n\in\R^N$ s.t.\ $n_i=0$ for all $i\not\in
  I$. For all $I\subset\{1\ldots N\}$, there exists
  at most one $n\in \R^{I}$ s.t.\
  \begin{equation}
    \label{eq:cond4}
  r_i-\int_{\Omega} K_i(\alpha)\;L\left(\sum_{j=1}^N B_j(\alpha)\,
    n_j\right)\,dP(\alpha)=0,\quad \forall i\in I.
  \end{equation}

  Then there exists a unique $\bar n=(\bar n_1,\ldots, \bar n_N)\in
  \R_+^N$ with $\bar n\neq 0$, s.t. for any solution $n(t)=( n_1,\ldots,
  n_N)$ to \eqref{discrete} with initial data $n_i(0)>0$ for any $i$,
  \[
  n(t)\longrightarrow \bar n, \ as\ t\rightarrow +\infty.
  \]
  \label{mainthm}
\end{theorem}

Note that, if one had $r_i>\int K_i(\alpha)L(\infty)\,dP(\alpha)$ for
some $i$, then $n_i(t)\rightarrow+\infty$ if
$n_i(0)>0$. Assumption~$(i)$ hence ensures the non-explosion of the system.

Eq.~\eqref{discrete} could be directly derived from simple biological
considerations. It assumes that the reproduction rate of a population
of type $i$ (or with trait $x_i$) is the difference between a fixed rate
depending only on the trait and a competitive interaction with the
other populations, resulting from the interaction with
the environment.  The state of each component of this environment
(indicated by different values of $\alpha$) is given by the sum
\[
\sum_j B_j(\alpha)\,n_j(t).
\]
Each such component has some independent effect on the reproduction.
To get the total reproduction rate
one sums over those.

Eq.~\eqref{discrete} is hence an obvious generalization, with a
possibly infinite number of resources, of the
model \eqref{Eqr}.  It also contains the Lotka-Volterra
system~\eqref{Eql}. In this case,
Theorem~\ref{mainthm} gives
\begin{prop} Assume that $r_i>0$ for all $i$ and that
the matrix $b_{ij}$ satisfies
\begin{equation}
\exists C\in (\R_+^*)^N\ \mbox{s.t.}\ C_i\,
b_{ij}=b_{ji}\,C_j,\ \mbox{and}\ \sum_{ij}u_i\,u_j\,b_{ij}\,C_i>0\quad
\forall u\in\R^N\setminus \{0\}, \label{hypb}
\end{equation}
then there exists a unique $\bar n=(\bar n_1,\ldots, \bar n_N)\in
\R_+^N$ with $\bar n\neq 0$, s.t.\ for any solution $n(t)=( n_1,\ldots,
n_N)$ to \eqref{Eql} with initial data $n_i(0)>0$ for any $i$,
\[
n(t)\longrightarrow \bar n, \ as\ t\rightarrow +\infty.
\]

\label{propb}
\end{prop}

  This result shows that, in Lotka-Volterra systems which are symmetric in the sense of~(\ref{hypb}), the
  competition between a mutant trait and a resident population leads to a unique stationary state,
  regardless of the initial population state. This is precisely the assumption needed in~\cite{Cha} to apply a
  limit of large population and rare mutations to an individual-based
  model.

  In particular, Thm.~2.7 of~\cite{Cha} applies to symmetric competitive Lotka-Volterra systems.

\bigskip
\noindent {\bf Proof of Prop.~\ref{propb}.}
Define the matrix $m_{ij}=C_i\,b_{ij}$. Note that $m$ is symmetric and
positive definite. Hence there exists an orthonormal basis of
eigenvectors $U^i$,
$i=1\dots N$, and corresponding eigenvalues $\lambda_i>0$.

Then put $L=\text{Id}$,
$\Omega=\{1,...,N\}$, $P=\frac{1}{N}\sum_{i=1}^N \delta_i$,
$B_j(\alpha)=\sqrt{\lambda_\alpha}
U^\alpha_j$, $K_i(\alpha)=C_i^{-1}\,\sqrt{\lambda_\alpha}U^\alpha_i$
and note that
\[\begin{split}
\sum_{j=1}^N b_{ij}\,n_j&=\frac{1}{C_i}\sum_{j=1}^N
m_{ij}\,n_j=\frac{1}{C_i}\left[Mn\right]_i\\
&=\frac{1}{C_i}\left[M\left(\sum_\alpha U^\alpha\langle
  U^\alpha,n\rangle\right)\right]_i=
\frac{1}{C_i}\sum_{\alpha=1}^N \lambda_\alpha\,U^\alpha_i \left(\sum_{j=1}^N
U^\alpha_j\,n_j\right)\\
&=\int_\Omega K_i(\alpha) L\left(\sum_{j=1}^N
B_j(\alpha)\,n_j\right)\,dP(\alpha).
\end{split}
\]
Therefore Eq.~\eqref{discrete} indeed yields \eqref{Eql} in that
particular case.

Conditions $(i)$ and $(ii)$ of Theorem~\ref{mainthm} are obviously
satisfied. Conditions $(iii)$ holds since $r_i>0$ for all $i$ and
$L(0)=0$. As for condition $(iv)$, assume that for a subset $I$ one
has two vectors $n_j^\gamma$, $\gamma=1,2$, s.t. $n_i^\gamma=0$ for
$i\not\in I$ and
\[
r_i=\int_\Omega K_i(\alpha) L\left(\sum_{j=1}^N
B_j(\alpha)\,n_j^\gamma\right)\,dP(\alpha)=\sum_{j=1}^N b_{ij}
n_j^\gamma\quad \forall
i\in I.
\]

Put $\delta n=n^1-n^2$ and simply note that
$\delta n_i \sum_{j=1}^N b_{ij}\delta n_j =0$ pour $ i=1\dots N$.

This means that $\delta n=0$ and proves $(iv)$ since
$\sum_{i,j=1}^N C_i b_{ij}\,\delta n_i\,\delta n_j=0$.
Hence the proposition is implied by Theorem~\ref{mainthm}.
\cqfd
\medskip

Note that the same argument works in the continuous case and
Eq.~\eqref{Eqlcont} is a particular case of~\eqref{continuous} for
$x\in O$ a bounded domain. The condition on $b$ is
\[
C(x)\,b(x,y)=C(y)\,b(y,x),\quad \int_{O^2}
C(x)\,b(x,y)\,n(x)\,n(y)\,dx\,dy>0\quad \forall n\neq 0.
\]
One still puts $L(\xi)=\xi$.

Notice that $C(x)\,b(x,y)$ defines a
 compact, selfadjoint and positive operator on $L^2(O)$.
Diagonalizing the operator,
one gets
\[
C(x)\,b(x,y)=\sum_{\alpha} \lambda_i f_\alpha(x)\,f_\alpha(y),
\]
with $\lambda_\alpha>0$ the eigenvalues, tending to $+\infty$ and
$f_\alpha$ the corresponding normalized eigenvector. It is hence enough to
take $\Omega=\N$ and
$
K(x,\alpha)=\sqrt{\lambda_\alpha}\,f_\alpha(x).
$

In the particular case where $b(x,y)=b(x-y)$ on the whole $\R^d$
and $C=1$, by Fourier transform,
the condition on $b$  means that $\hat b>0$.

One then takes $\Omega=\R^d$ and
\[
K(x,\alpha)=(\cos(\alpha\cdot x)\,\sqrt{\hat
  b(\alpha)},\ \sin(\alpha\cdot x)\,\sqrt{\hat b(\alpha)} ).
\]

\section{Proof of Theorem \ref{mainthm}}

The proof is based on the study of the following Lyapunov functional
\begin{equation}
F(n)=\int_\Omega H\left(\sum_{j=1}^N B_j(\alpha)
n_j\right)\;dP(\alpha)-\sum_{i=1}^N C_i\, r_i\, n_i,\label{F}
\end{equation}
where $H$ is an antiderivative of $L$ and hence strictly convex.

\subsection{$F$ is a strict Lyapunov functional}\label{sub1}

Let $n$ be a solution to \eqref{discrete}. Then by a direct
computation
\begin{align}
\frac{d}{dt} F(n(t))

&=-\sum_{i=1}^N C_i\, n_i\,\left[
\int_\Omega K_i(\alpha)\,L\left(\sum_{j=1}^N B_j(\alpha)
n_j\right)\;dP(\alpha)-\,r_i
\right]^2. \label{eq:F-Lyap}
\end{align}
Therefore $F(n(t))$ is non increasing and its derivative in time vanishes only on stationary solutions
to~\eqref{discrete}, i.e.\ $F$ is a strict Lyapunov functional for the system~(\ref{discrete}).

Thanks to condition~$(i)$,
\begin{align}
  \frac{\partial F}{\partial n_i} &

  \geq C_i\left(\int_\Omega K_i(\alpha)L\Big(\frac{K_i(\alpha)}{C_i}
  n_i\Big)\,dP(\alpha)-r_i\right)
  \geq a>0 \notag
\end{align}
if $n_i$ is large enough. Therefore, there is a constant $a'>0$ s.t.\ $\nabla F(n)\cdot n\geq a'\|n\|$ if $\|n\|$ is large enough. This implies that $F(n)\rightarrow+\infty$ when $\|n\|\rightarrow+\infty$, and entails that $n(t)$ is uniformly bounded.

Let $n\in\R_+^N$ be a steady-state of \eqref{discrete} and let $I$ be the set of $i$ s.t.\ $n_i>0$. Then, for
any $i\in I$ one needs to have
\[
\int_\Omega
K_i(\alpha)\,
L\left(\sum_{j=1}^N B_j(\alpha)
n_j\right)\;dP(\alpha)=r_i.
\]
By condition $(iv)$ there is at most one such solution for every $I$, and there are only a finite number of
possible $I$, $F$ has then a finite number of steady-states.

Classical Lyapunov functionnals' techniques
then entail that the solution $n(t)$ to~(\ref{discrete}) converges to a steady-state $\tilde
n$ for any initial condition $n(0)$.

\subsection{The functional $F$ is convex}

Compute
\begin{equation}
\label{eq:der2-F}
\frac{\partial^2 F}{\partial n_i\partial n_k}=\int_\Omega
B_i(\alpha)\,B_k(\alpha)
L'\left(\sum_{j=1}^N B_j(\alpha)
n_j\right)\;dP(\alpha).
\end{equation}
Hence as $L$ is increasing
\begin{equation}
\label{eq:unif-ellipt}
\sum_{i,k} \frac{\partial^2 F}{\partial n_i\partial n_k} \xi_i\,\xi_k=
\int_\Omega
(\sum_i \xi_i B_i(\alpha))^2\,
L'\left(\sum_{j=1}^N B_j(\alpha)
n_j\right)\;dP(\alpha)\geq 0.
\end{equation}
$F$ is therefore convex and any local minimum on $\R_+^N$ is global.

Since~(\ref{discrete}) has a finite number of stationary solutions, this clearly implies that $F$ admits a
unique global minimizer $\bar{n}$. Otherwise, $F$ would reach its minimum on the whole segment linking two
distinct minimizers.

The object of the next subsection is to prove that $\bar{n}$ satisfies a stronger property: this is the unique
ESS of the system.

\subsection{Uniqueness of the ESS}\label{sub2}

Any local minimizer  $n\in\mathbb R_+^N$ of the functional $F$  necessarily satisfies
\begin{equation}
\begin{split}
&\int_\Omega
K_i(\alpha)\,
L\left(\sum_{j=1}^N B_j(\alpha)
n_j\right)\;dP(\alpha)=r_i,\quad \forall i\ s.t.\ n_i>0,\\
&\int_\Omega
K_i(\alpha)\,
L\left(\sum_{j=1}^N B_j(\alpha)
n_j\right)\;dP(\alpha)\geq r_i,\quad \forall i\ s.t.\ n_i=0.
\end{split}\label{ESS}
\end{equation}
This condition corresponds to the usual definition of an Evolutionarily Stable Strategy in adaptive dynamics
(see for instance \cite{Di}).  It turns out that there exists at most one ESS, $\bar{n}$. Hence being an ESS
is a necessary and sufficient condition to be the global minimizer of $F$.

Indeed take two $n^\gamma\in \R^N_+$, $\gamma=1,2$ satisfying \eqref{ESS} and
compute
\[\begin{split}
 0&\geq \sum_i C_i\,n^1_i \left(r_i-\int_\Omega
K_i(\alpha)\,
L\left(\sum_{j=1}^N B_j(\alpha)
n_j^2\right)\;dP(\alpha)\right)\\
&\qquad+\sum_i C_i\,n^2_i \left(r_i-\int_\Omega
K_i(\alpha)\,
L\left(\sum_{j=1}^N B_j(\alpha)
n_j^1\right)\;dP(\alpha)\right). \\
\end{split}\]
This last quantity is equal to (thanks to \eqref{ESS})
\[
\begin{split}
& \sum_i C_i\,(n^1_i-n^2_i) \left(r_i-\int_\Omega
K_i(\alpha)\,
L\left(\sum_{j=1}^N B_j(\alpha)
n_j^2\right)\;dP(\alpha)\right)\\
&\qquad+\sum_i C_i\,(n^2_i-n^1_i) \left(r_i-\int_\Omega
K_i(\alpha)\,
L\left(\sum_{j=1}^N B_j(\alpha)
n_j^1\right)\;dP(\alpha)\right) \\
\end{split}\]
and to
\[\begin{split}
&+ \int_\Omega \left(\sum_j B_j(\alpha)\,n_j^1-\sum_j B_j(\alpha)
n_j^2\right)\\
&\qquad\left(L\left(\sum_{j=1}^N B_j(\alpha)
n_j^1\right)-L\left(\sum_{j=1}^N B_j(\alpha)
n_j^1\right)\right)\;dP(\alpha).
\end{split}\]
As $L$ is strictly increasing, this implies that for $P\ a.e.$
$\alpha$,
$\sum_{i=1}^N B_i(\alpha)\,(n^1_i-n^2_i)=0$ and by
$(iv)$, it means that $n^1=n^2$.

\subsection{Conclusion of the proof of Thm.~\ref{mainthm}}\label{sub3}

Assume that $n_i(0)>0$ for all $1\leq i\leq N$. We know from Subsection \ref{sub1} that $n(t)$ converges to a
steady-state $\tilde n$ when $t\to\infty$.

If $\tilde n$ does not satisfy \eqref{ESS}, there exists $i\in \{1,\dots,N\}$ such that
\[
\lambda_i:=r_i-\int_\Omega
K_i(\alpha)\,
L\left(\sum_{j=1}^N B_j(\alpha)
\tilde n_j\right)\;dP(\alpha)> 0.
\]
Since $n_i(0)>0$, $n_i>0$ at all times, and the linearized equation around $\tilde n$ shows that $n$ cannot converge to $\tilde n$:
\begin{eqnarray*}
  \label{eq:}
  \frac d{dt}(n-\tilde n)_i&=&\left(\lambda_i+O(\|n-\tilde n\|)\right)\,(n-\tilde n)_i\\
&\geq&\frac{\lambda_i}2\,(n-\tilde n)_i,
\end{eqnarray*}
provided that $\|n-\tilde n\|$ is small enough.

Therefore, $\tilde{n}=\bar{n}$, and the proof of Thm.~\ref{mainthm} is completed.

\bigskip

\noindent{\bf Acknowledgments:} The first author is grateful to Michel Bena\"im for useful discussions on the
dynamical systems context of the problem. GR has been supported by Award No. KUK-I1-007-43 of Peter A. Markowich,
made by King Abdullah University of Science and Technology (KAUST).

config: arxiv


TITLE: How many points of intersection between an ellipse and an $L_p$-circle?
QUESTION [19 upvotes]: Consider an ellipse $E$ in the plane, centered at the origin.  (In my case, the minor axis points into the nonnegative quadrant.)
Let S be an "$L_p$-circle":  $S = \{(x,y) : |x|^p + |y|^p = 1\}$, where $p > 1$, $p \neq 2$.
Is it correct that $E$ and $S$ have at most 8 intersections?
More exactly what I care about: is it true that $E$ and $S$ have at most 2 intersections in the nonnegative quadrant?
It seems relatively clear from drawing pictures, but I couldn't quite get the natural convexity argument to work.

REPLY [2 votes]: This question has been asked and answered on MathOverflow. I have replicated the accepted answer by Ilya Bogdanov below.

$\def\sign{\mathop{\rm sign}}$First of all, it is enough to prove the statement when $p=u/v$ is rational, $u$ is even and $v$ is odd (such numbers are dense on the real line). We need this to simplify the last argument.
Let the equation of the ellipse be $f(x,y)=ax^2+2bxy+cy^2=1$; one may assume that $b\neq 0$ (either by a small variation argument, or by considering it directly --- this case is easy). Let us bound the number of local extrema of $f(x,y)$ on $|x|^p+|y|^p=1$; if there are at most 8 of them, then we are done: between every two, there is at most one intersection point. Since $b\neq 0$, the points where one of the coordinates vanish are not extremal (the ellipse passing through such point has a tangent not parallel to the coordinate axes).
The extremal points satisfy the system of Lagrange equations
  $$
  2(ax+by)=p\lambda|x|^{p-1}\sign x, \quad
  2(bx+cy)=p\lambda|y|^{p-1}\sign y;
$$
  obviously, $\lambda\neq 0$, so this system yields
  $$
  \frac{at+b}{bt+c}=|t|^{p-1}\sign t,
$$
  where $t=x/y$. So, it suffices to show that there are at most four such values of $t$ (each corresponds to two symmetrical extremal points). Notice that $|t|^{p-1}\sign t=t^{(u-v)/v}$ by our assumptions on $u$ and $v$. Now, substituting $t=s^v$ we obtain
  $$
  as^v+b=bs^u+cs^{u-v}.
$$
  The last polynomial equation has at most four roots by an easy application of Descartes' rule of signs.
ADDENDUM. By the way, you have mentioned on MathSE that in your case the minor axis is in the positive quadrant, and you were interested in the intersection points lying in this quadrant as well. In this case we may assume that $a,b,c>0$, and we are interested in positive values of $t$. The rule of signs shows that there is at most one $t$ whenever $u-v>v$, that is --- if $p>2$. Otherwise it claims that there is at most one $t$ in the adjacent quadrant.
ADDENDUM2. Here is the explanation about the limiting case. Assume that you have more than 8 common pointsof an ellipse and an $\ell_p$-circle. Blowing up or away your ellipse a bit, you may reach the situation when there are more than 8 points of transversal intersection. Then you mark a point on the ellipse between every such neighboring points (or simply mark 10 of them); these marked points are alternately inside and outside the $\ell_p$-circle. Finally, if you change $p$ a bit, all these 10 points will still be alternating, guaranteeing 10 intersection points.
The same method works for $b=0$.
Finally, if it is easier for you, you may pass to rational $p$ of a desired form AFTER writing down the (almost) polynomial in $t$ --- in this case the statement is more visible...
And, even more finally, you may just repeat the proof of the Descartes' rule for an `almost polynomial' --- all you (perhaps) need is that all the powers differ by at least one, which can be reached by an appropriate substitution.
ADDENDUM3. Just to mention. The same method allows to prove that the affine images of $\ell_p$- and $\ell_q$-circles also have at most 8 common points, if they have the same center.


TITLE: Proving convergence of a sequence using the Squeeze Theorem
QUESTION [0 upvotes]: I am given a non-empty set $X$ which is a subset of $\Bbb R^k$ with a function $f:X \to X$. I am required to prove that a sequence $X_n$ in $X$ converges to $f$ given a fixed point on $X$.
Question

My Solution

From the solutions, you can see that I am attempting to use the Squeeze theorem to solve the convergence problem. However, I am not clear as to whether I am doing this correctly or whether the Squeeze theorem is the right tool to use in the first instance. Any help would be greatly appreciated.

REPLY [0 votes]: For a), there is a simpler proof, which doesn't involve the squeeze theorem.
Note $\Vert x_{n+1}-x_n\Vert=\Vert f(x_n)-f(x_{n-1})\Vert<\Vert x_n-x_{n-1}\Vert$. This shows the sequence $\Vert x_{n+1}-x_n\Vert$ is decreasing in $\mathbb{R}$, and bounded below by zero, so it has a limit $l$.
Also, if $k>1$ I'm not really sure you can manipulate expressions like $\frac{1}{x(x-1)}$ as you could if those were real numbers, or if the expression $x-1$ makes sense.

For b), you are trying to prove that the preimage of an open set is open, to conclude $f$ is continuous, right? That is a correct approach. Then again, I at least find it sligthly confusing to manipulate the pre-images of sets to prove continuity. I think it is better to prove it with the $\epsilon-\delta$ notion of continuity, or with convergent sequences, which in this case is straightforward.
A proof with pre-images of open sets is this: Let $U\subseteq\mathbb{R}^k$ an open set. Let $x\in f^{-1}(U)$ We want to show there is some $\epsilon>0$ s.t. $B(x,\epsilon)\subset U$. Since $x\in f^{-1}(U)$, $f(x)\in U$. Since $U$ is open there is some $\epsilon>0$ s.t. $B(f(x),\epsilon)\subset U$. But then
$$
y\in B(x,\epsilon)\Rightarrow \Vert f(x)-f(y) \Vert < \Vert x-y\Vert <\epsilon \Rightarrow f(y)\in B(f(x),\epsilon)\subset f^{-1}(U)
$$
This shows there is some $\epsilon>0$ s.t. $B(x,\epsilon)\subset f^{-1}(U)$


TITLE: Limit definition of Sets.
QUESTION [1 upvotes]: Proposition 1.32 $X_{n}\xrightarrow{a.s.} X$ if and only if for any $\epsilon>0$
$P( | X_{n}- X |<\epsilon, \; \forall n\geq m )\rightarrow1$ $as$ $ m\rightarrow\infty$
Proof. Suppose first that $X_{n} \xrightarrow{a.s.} X$. Fix $\epsilon>0$, and $m\geq1$ define the event
$A_m=\{| X_{n}-X |<\epsilon , \; \forall n\geq m\}$
Because $A_m,m\geq1$, is an increasing sequence of events, the continuity property of probabilities yields that
$$\lim_{m\to \infty}P(A_m)=P(\lim_{m\to \infty}A_m)=P(| X_{n}- X |<\epsilon \text { for all n sufficiently large})\geq P(\lim_{n \to \infty}X_n=X)=1$$
To go the other way, assume that for any $\epsilon>0$
$P(| X_{n}-X |<\epsilon, \; \forall n\geq m)\rightarrow1$ as $m\rightarrow\infty$
let $\epsilon_{i}, i\geq1$ be a decreasing sequence of postive numbers that converge to $0 $ and let
$A_{m,i}=\{| X_{n}-X |<\epsilon, \; \forall n\geq m\}$
Because $A_{m,i}\subset A_{m+1,i}$ and, by assumption, $\lim\limits_{m\to \infty}P(A_{m,i})=1$ ......

The parts in bold that concern increasing and decreasing events confuse me thoroughly, I do not understand them :(
What does it actually mean to have $X_{n}\xrightarrow{a.s.} X$?

REPLY [0 votes]: 1.1. Perhaps, you might better understand $A_m$'s as follows:
$$A_1 = \{\omega \in \Omega \mid |X_1(\omega) - X(\omega)| < \epsilon, |X_2(\omega) - X(\omega)| < \epsilon, |X_3(\omega) - X(\omega)| < \epsilon, \dots \}$$
$$A_2 = \{\omega \in \Omega \mid |X_2(\omega) - X(\omega)| < \epsilon, |X_3(\omega) - X(\omega)| < \epsilon, |X_4(\omega) - X(\omega)| < \epsilon, \dots \}$$
$$\vdots$$
$$A_m = \{\omega \in \Omega \mid |X_m(\omega) - X(\omega)| < \epsilon, |X_{m+1}(\omega) - X(\omega)| < \epsilon, |X_{m+2}(\omega) - X(\omega)| < \epsilon, \dots \}$$
$$\vdots$$
To be more elaborate, define:
$$B_1:= \{\omega \in \Omega \mid |X_1(\omega) - X(\omega)| < \epsilon\}$$
$$B_2:= \{\omega \in \Omega \mid |X_2(\omega) - X(\omega)| < \epsilon\}$$
$$B_3:= \{\omega \in \Omega \mid |X_3(\omega) - X(\omega)| < \epsilon\}$$
$$\vdots$$
$$B_m:= \{\omega \in \Omega \mid |X_m(\omega) - X(\omega)| < \epsilon\}$$
$$\vdots$$
Then $$A_1 = B_1 \cap B_2 \cap B_3 \cap \cdots = \bigcap_{k=1}^{\infty} B_k$$
$$A_2 = B_2 \cap B_3 \cap \cdots = \bigcap_{k=2}^{\infty} B_k$$
$$\vdots$$
$$A_m = B_m \cap B_{m+1} \cap \cdots = \bigcap_{k=m}^{\infty} B_k$$
$$\vdots$$
Hopefully, it is clear that $$A_1 \subseteq A_2 \subseteq \cdots \subseteq A_m \subseteq \cdots$$

1.2 I have a feeling you made a typo. Did you mean
$$A_{m,i} = \{\omega \in \Omega \mid |X_m(\omega) - X(\omega)| < \epsilon_i, |X_{m+1}(\omega) - X(\omega)| < \epsilon_i, |X_{m+2}(\omega) - X(\omega)| < \epsilon_i, \dots \}$$
?
If so, then $$A_{m,i} \subseteq A_{m+1,i}$$ for the same reasons that $A_{m} \subseteq A_{m+1}$.

This is almost sure convergence, the closest analogue to pointwise convergence from real analysis.

If we have random variables $X, X_1, X_2, \dots$ in $(\Omega, \mathscr F, \mathbb P)$, then $X_n$ converges almost surely to $X$ iff
$$P(\lim_{n \to \infty} X_n = X) := P(\omega \in \Omega \mid \lim_{n \to \infty} X_n(\omega) = X(\omega)) = 1$$
So if we collect all $(\omega_j)_{j \in J}$ s.t. $$\limsup X_n(\omega_j) = \liminf X_n(\omega_j) = X(\omega_j)$$, then we must have $$P(\bigcup_{j \in J} (\omega_j)) = 1$$