text:
\begin{document}
\maketitle

\begin{abstract}
Let $G$ be a group. The orbits of the natural action of $\Aut(G)$ on $G$ are called ``automorphism orbits'' of $G$, and the number of automorphism orbits of $G$ is denoted by $\omega(G)$. In this paper we prove that if $G$ is an $\FC$-group  with finitely many automorphism orbits, then the derived subgroup $G'$ is finite and $G$ admits a decomposition $G = \Tor(G) \times D$, where $\Tor(G)$ is the torsion subgroup of $G$ and $D$ is a divisible characteristic subgroup of $\cent(G)$. We also show that if $G$ is an infinite $\FC$-group with $\omega(G) \leqslant 8$, then either $G$ is soluble or $G \cong \Alt_5 \times H$, where $H$ is an infinite abelian group with $\omega(H)=2$. Moreover, we describe the structure of the infinite non-soluble $\FC$-groups with at most eleven automorphism orbits.
\end{abstract}

\maketitle

\section{Introduction}
An element $g$ of a group $G$ is called an $\FC$-element if it has a finite number of conjugates in $G$, that is, if the index $[G : \centralizer(g)]$ is finite, where $\centralizer(g) = \{h \in G \mid  g^{h} = g\}$.  The set $\centhat(G)$ of all $\FC$-elements of $G$ is a characteristic subgroup (see \cite[14.5.5]{Rob}). If each element of $G$ is an $\FC$-element, then $G$ is called an $\FC$-group. In particular, $G = \centhat(G)$. If there exists a positive integer $d$ such that $[G : \centralizer(g)] \leq d$ for all $g \in G$, then the group $G$ is called a $\BFC$-group, that is, there is a common bound for the size of conjugacy classes in $G$. The class of $\FC$-groups contains all abelian and all finite groups.

Let $G$ be a group. The orbits of the natural action of $\Aut(G)$ on $G$ are called ``automorphism orbits'' of $G$, and the number of automorphism orbits of $G$ is denoted by $\omega(G)$.  It is interesting to ask what can we
say about ``$G$'' only knowing $\omega(G)$. It is obvious that $\omega(G)=1$ if and only if $G=\{1\}$, and it is well known that if $G$ is a finite group then $\omega(G) = 2$ if and only if $G$ is elementary abelian. In \cite{LD}, Laffey and MacHale proved that if $G$ is a finite non-soluble group with $\omega(G) \leqslant 4$, then $G$ is isomorphic to $\PSL(2,\mathbb{F}_4)$. Stroppel in \cite{S1} has shown that the only finite non-abelian simple groups $G$ with $\omega(G) \leq 5$ are the groups $\PSL(2,\mathbb{F}_q)$ with $q \in \{4,7,8,9\}$. In \cite{BD,BDG}, the authors prove that if $G$ is a finite non-soluble group with $\omega(G) \leq 6$, then $G$ is isomorphic to one of $\PSL(2,\mathbb{F}_q)$ with $q \in \{4,7,8,9\}$, $\PSL(3,\mathbb{F}_4)$ or $\ASL(2,\mathbb{F}_4)$ (answering a question of Stroppel, cf. \cite[Problem 2.5]{S1}). Here $\ASL(2,\mathbb{F}_4)$ is the affine group $\SL(2,\mathbb{F}_4) \ltimes \mathbb{F}_4^2$ where $\SL(2,\mathbb{F}_4)$ acts naturally on $\mathbb{F}_4^2$. For more details concerning automorphism orbits of finite groups see \cite{K02,K04,S99,Z}.

Some aspects of automorphism orbits are also investigated for infinite groups. In \cite{MS1}, M\"aurer and Stroppel classified the groups with a nontrivial characteristic subgroup and with three orbits by automorphisms (see Section 5, below). Schwachh\"ofer and Stroppel in \cite{S2}, have shown that if $G$ is an abelian group with finitely many automorphism orbits, then $G = \Tor(G) \oplus D$, where $D$ is a characteristic torsion free divisible subgroup of $G$ and $\Tor(G)$ is the set of all torsion elements in $G$. Stroppel also investigated properties of topological groups with finitely many automorphism orbits (see \cite{S1} for more details).

In the present article we consider infinite $\FC$-groups with finitely many automorphism orbits. Our results can be viewed as extensions of the above results.

\begin{thmA}
Let $G$ be an infinite $\FC$-group with finitely many automorphism orbits. Then the derived subgroup $G'$ is finite. Moreover, $G$ admits a decomposition $\Tor(G) \times D$, where $D$ is a divisible characteristic subgroup of $\cent(G)$.
\end{thmA}

In general, infinite groups with small number of automorphism orbits need not be soluble. For instance, Higman, Neumann and Neumann have constructed a torsion free non-abelian simple group $S$ with $\omega(S) = 2$ (cf.  \cite[6.4.6]{Rob}). However, we prove the following solubility criterion for infinite $\FC$-groups in terms of the number of automorphism orbits.

\begin{thmB} \label{thm.soluble}
Let $G$ be an infinite $\FC$-group.
\begin{itemize}
\item[$(a)$] If $\omega(G) \leqslant 4$, then $G$ is nilpotent;
\item[$(b)$] If $\omega(G) \leqslant 7$, then $G$ is soluble;
\item[$(c)$] If $G$ is a non-soluble group with $\omega(G) = 8$, then there exists an infinite abelian group $H$ with $\omega(H)=2$ such that $G$ is isomorphic to $\Alt_5 \times H$.
\end{itemize}
\end{thmB}

Note that the group $\Sym_3 \times H_2$ is an infinite non-nilpotent $\FC$-group with $\omega(\Sym_3 \times H_2)=5$, where $\Sym_3$ is the symmetric group and $H_2$ is an infinite elementary abelian $2$-group (see Example \ref{ex.5}, below). Consequently, the bound on the number of orbits in Theorem B (a) is sharp. It should be noted that $\omega(\Alt_5 \times \mathbb{Q})=8$, where $\Alt_5$ is the alternating group and $\mathbb{Q}$ is the additive group of the field of rational numbers. In particular, the bound obtained in Theorem B (b) cannot be improved (see Example \ref{ex.5}, below).

The famous Schur Theorem says that if $G$ is central-by-finite, then the order of the derived subgroup $G'$ is finite (cf. \cite[10.1.4]{Rob}). In particular, $G$ is a $\BFC$-group. Later, Neumann proved that the group $G$ is a $\BFC$-group if and only if the derived subgroup $G'$ is finite (cf. \cite[14.5.11]{Rob}). It is well known that $\BFC$-groups need not be central-by-finite (cf. \cite{N}). By Theorem B, every infinite non-soluble $\FC$-group with at most eight automorphism orbits is central-by-finite. We obtain the following related result.

\begin{thmC}
Let $G$ be an infinite non-soluble $\FC$-group with at most eleven automorphism orbits. Then $G$ is central-by-finite.
\end{thmC}

The above theorem is no longer valid if the assumption of non-solubility of $G$ is dropped (see Example \ref{ex.H}, below). Moreover, the bound obtained in the above result cannot be improved (see Example \ref{ex.12}, below).

\section{Proof of Theorem A}

Let $G$ be a group and $g$ an element in $G$. The {\it automorphism orbit} of $g$ in the group $G$ is denoted by $g^{\Aut(G)} =\{g^{\alpha} \mid  \alpha \in \Aut(G)\}$. If $K$ is a subgroup of $G$, the notation $K = \uplus_{i=1}^{n} g_{i}^{\Aut(G)}$ means that $$K = \displaystyle \bigcup_{i=1}^{n} g_{i}^{\Aut(G)}$$ and $g_i^{\Aut(G)} \cap g_j^{\Aut(G)} = \emptyset$ if $i \neq j$.

\begin{lem} \label{lemma2}
(Stroppel, \cite[Lemma 3.1]{S}) Let $G$ be a nontrivial group with finitely many automorphism orbits. Suppose that there exist nontrivial characteristic subgroups $M$ and $N$ such that $M \cap N = 1$. Then
$$\omega(G) \geqslant \omega(M)\omega(N) \geqslant 2 \cdot \omega(N).$$
Moreover, if $G = M \times N$, then $\omega(G) = \omega(M) \cdot \omega(N)$.
\end{lem}

\begin{lem} (Stroppel, \cite[Lemma 1.1]{S2} \label{Stroppel1})
If $G$ is an abelian group with finitely many automorphism orbits, then $G = \Tor(G) \oplus D$, where $D$ is a characteristic torsion free divisible subgroup of $G$. In particular, $D$ is the additive group of a vector space over $\mathbb{Q}$.
\end{lem}

Schur \cite[10.1.4]{Rob} has shown that if $G$ is a central-by-finite group then the derived subgroup $G'$ is finite. In particular, $G$ is a $\BFC$-group. It is well known that the converse of Schur's Theorem does not hold (see \cite{N}). However, Hall \cite[14.5.3]{Rob} has shown that if $G$ is a group whose the $k$-th term of the lower central series $\gamma_{k+1}(G)$ is finite, then $\cent_{2k}(G)$. The next result is an immediate consequence of Hall's result  in the context of infinite BFC-groups. We supply the proof for the reader's convenience.

\begin{lem} \label{lem.center}
Let $G$ be an infinite $\FC$-group with finitely many automorphism orbits. Then the center $\cent(G)$ is non-trivial.
\end{lem}

\begin{proof}
By Theorem A, the derived subgroup $G'$ is finite. By Hall's theorem \cite[14.5.3]{Rob}, the second center $\cent_2(G)$ has finite index in $G$. Since $G$ is infinite, it follows that the center $\cent(G)$ is non-trivial. The proof is complete.
\end{proof}

\begin{lem} \label{lem.abelian}
Let $G$ be an infinite $\FC$-group with $\omega(G) = 2$. Then $G$ is the additive group of a vector space, that is, either a torsion free divisible abelian group or an elementary abelian $p$-group for some prime $p$.
\end{lem}

\begin{proof}
By Lemma \ref{lem.center}, the center $\cent(G)$ is nontrivial. It follows that $G = \cent(G)$. In particular, $G$ is the additive group of a vector space over some field $\mathbb{F}$. The result follows.
\end{proof}

\begin{lem} \label{lemma1}
Let $G$ be an $\FC$-group with finitely many automorphism orbits. Then $G$ is a $\BFC$-group.
\end{lem}

\begin{proof}
The size of the conjugacy class $g^G$ is constant on each orbit under $\Aut(G)$. If $\omega(G)$ is finite then there is a finite bound for those sizes.
\end{proof}

We are now in a position to prove Theorem A.

\begin{proof}[Proof of Theorem A] Assume that $G$ is an $\FC$-group with finitely many automorphism orbits. We claim that $G$ is a $\BFC$-group and admits a decomposition $D \times \Tor(G)$, where $D$ is a divisible characteristic subgroup of $\cent(G)$.

By Lemma \ref{lemma1}, $G$ is a BFC-group. By Neumann's result \cite[14.5.11]{Rob}, the derived subgroup $G'$ is finite. It remains to prove the decomposition $G = \Tor(G) \times D$. By Lemma \ref{Stroppel1}, $\cent(G) = (\Tor(G) \cap \cent(G)) \oplus D$, where $D$ is a characteristic subgroup of $\cent(G)$. By Baer's result \cite[14.5.6]{Rob}, $G/\cent(G)$ is a torsion group. Since $\omega(G)$ is finite, we conclude that $G / \cent(G)$ has finite exponent. Set $m= \exp(G/\cent(G))$. Since $G$ is an $\FC$-group, it follows that $\Tor(G)$ is a subgroup of $G$ (cf. \cite[14.5.9]{Rob}).  By Lemma \ref{Stroppel1}, $G/\Tor(G)$ is a divisible group. Let $g \in G \setminus \Tor(G)$. Hence there exists $h \in G$ such that $g = h^{m}k$, where $k \in \Tor(G)$ and thus $G = \Tor(G)\cent(G) = \Tor(G)D$. On the other hand, $G = \Tor(G) \times D$, because $D$ is torsion free. The proof is complete.
\end{proof}

\begin{cor} \label{cor.odd}
Let $G$ be an infinite $\FC$-group in which $\omega(G)$ is an odd number. Then $G$ has finite exponent.
\end{cor}

\begin{proof}
According to Theorem A, $G = \Tor(G) \times D$, where $D$ is a divisible characteristic subgroup of $G$. Suppose that $D$ is non-trivial. By Lemma \ref{Stroppel1}, $\omega(D) = 2$. By Lemma \ref{lemma2},   $$\omega(G) = \omega(\Tor(G))\omega(D) = 2 \omega(\Tor(G)),$$ a contradiction. The proof is complete.
\end{proof}

\begin{cor} \label{Cor.na.5}
Let $G$ be a non-abelian $\FC$-group with $\omega(G) \leq 5$. Then $G$ has finite exponent.
\end{cor}

\begin{proof}
By Corollary \ref{cor.odd}, we can assume that $G$ has exactly four automorphism orbits. Suppose that $G$ is not a torsion group. By Theorem A, $G = D \times \Tor(G)$, where $D$ is a torsion free divisible group and so, $G$ is abelian.
\end{proof}

\begin{ex}
Note that the group $\Sym_3 \times \mathbb{Q}$ is an infinite non-periodic $\FC$-group with $\omega(\Sym_3 \times \mathbb{Q}) = 6$ (Lemma \ref{lemma2}). Thus, the bound on the number of orbits in the above result cannot be improved.
\end{ex}

\section{Proof of Theorem B}

Let $H$ be a periodic group and $S$ a subset of $H$. The {\it spectrum} of $S$, denoted by $\spec(S)$, is defined to be the set of all orders of elements in $S$. A crucial observation that we will use many times is that two elements that lie in the same automorphism orbit have the same order. In particular, it is clear that if $G$ is a $p$-group with finitely many automorphism orbits, then $p^{\omega(G)} \geqslant \exp(G)$. The following result is a key argument to obtain bounds for the exponent $\exp(G)$, when $G$ is an infinite non-abelian $\BFC$-group.

\begin{lem} \label{Lemma 4.2}
Let $G$ be an infinite $\FC$-group with finitely many automorphism orbits. Assume that $G$ is a non-abelian $p$-group. Then there exists $h \in G'$ and $g \in G \setminus G'$ such that $|h| = |g|$.
\end{lem}

\begin{proof}
Since $G$ is a $p$-group with finitely many automorphism orbits, we conclude that the exponent $\exp(G)$ is finite. Suppose for contradiction that $\spec(G') \cap \spec(G\setminus G') = \emptyset$. Let $p^{s} = \exp(G')$ and let $A_{i} = \{g \in G \mid |g| = p^{s+i}\}$. Since $G$ is non-abelian, it follows that $s \geqslant 1$, so  $\spec(G') = \{1,p,\ldots,p^s\}$. It suffices to obtain an element $g \in G \setminus G'$ with $|g|=p$. If $a_{1} \in A_{1}$, then the subgroup $\langle a_{1}, G' \rangle$ is finite \cite[14.5.8]{Rob}. Thus there exists $a_{2} \in C_{G}(a_1)$ such that
$$a_{2} \notin \langle a_{1}, G' \rangle.$$
Since $\langle a_{2}, a_{1}, G' \rangle$ is finite, there exists $a_{3} \in \centralizer(a_{2}) \cap \centralizer(a_{1})$ such that
$$a_{3} \notin \langle a_{2}, a_{1}, G' \rangle.$$
Repeating this process, we get $a_{1}, a_{2}, a_{3}, ..., a_{n}, ... \in G \setminus G'$ such that $a_{i} \in \centralizer(a_{i-1}) \cap ... \cap \centralizer(a_{1})$ and
$$a_{i} \notin \langle a_{i-1}, ..., a_{1}, G' \rangle$$
for any $i \in \mathbb{N}$. Thus $C:= \langle a_{1}, a_{2}, a_{3}, ..., a_{n}, ...\rangle$ is an infinite abelian group.

Since $G$ has finite exponent, it follows that $C \cap A_{i}$ is infinite for some positive integer $i$. Set $t=\min \{i \in \mathbb{N} \mid C \cap A_i \ \text{is infinite}\}$. Then the set
$$\{a \in C \cap A_{t} \mid \, a^{p} = b \}$$
is infinite for some $b$ with order $p^{s+t-1}$. Choose
$$a_{i_{1}}, ..., a_{i_{|b|}} \in \{a \in C \cap A_{t} \mid \, a^{p} = b \}.$$
Then
$$(a_{i_{1}} ... a_{i_{|b|}})^{p} = a_{i_{1}}^{p} ... a_{i_{|b|}}^{p} = b^{|b|} = 1$$
and
$$a_{i_{1}} ... a_{i_{|b|}} \notin G',$$
a contradiction. Now, it remains to exclude the case when $\exp(G') > \max \{\spec(G \setminus G')\}$. In particular, there are an element $x \in G'$ and a $p$-power $t$ such that $|x^t| \in \spec(G \setminus G')$. Set $h = x^t$. Consequently, there exists an element $g \in G \setminus G'$ such that $|h| = |g|$, which completes the proof.
\end{proof}

We obtain a bound of the exponent of certain infinite non-abelian $\FC$-group in terms of the number of automorphism orbits (see Examples \ref{ex.H} and \ref{ex.n(2)}, below).

\begin{cor} \label{Cor3.3}
Let $G$ be an infinite non-abelian $\FC$-group with finitely many automorphism orbits. Suppose that $G$ is a $p$-group. Then $\exp(G)$ divides $p^{\omega(G) - 2}$.
\end{cor}

\begin{proof}
Suppose that $\exp(G) \geq p^{\omega(G) - 1}$. Set $g \in G$ such that $|g| = p^{\omega(G) - 1}$. We can deduce that
\begin{equation} \label{eq:cor.p}
G = \{1\} \uplus g^{\Aut(G)} \uplus (g^{p})^{\Aut(G)} \uplus ... \uplus (g^{p^{\omega(G) - 2}})^{\Aut(G)}.
\end{equation}
By Theorem A, the derived subgroup $G'$ is finite. By Lemma \ref{Lemma 4.2}, there exists an element $h$ of $G \setminus G'$ such that $|h| \in \spec(G')$. In particular, we present two elements of the same order which are in different automorphism orbits, contrary to (\ref{eq:cor.p}). The result follows.
\end{proof}

\begin{lem} \label{lem.2-groups}
Let $G$ be an infinite non-abelian $\FC$-group. Assume that $G$ is a $2$-group. Then $\omega(G) \geqslant 4$.
\end{lem}

\begin{proof}
If $\omega(G)=2$, then $G$ is abelian (by Lemma \ref{lem.abelian}). There is no loss of generality in assuming that $\omega(G)=3$. By Corollary \ref{Cor3.3}, $\exp(G)$ divides $4$. Since $G$ is non-abelian, we conclude that $G'$ is non-trivial, so there are elements $h \in G'$ and $g \in G \setminus G'$ such that $|h|=|g|=2$ (by Lemma \ref{Lemma 4.2}). As $\omega(G)=3$, we have $\exp(G)=2$, which is impossible. The proof is complete.
\end{proof}

The bound on the number of orbits in the above result cannot be improved (see Example \ref{ex.n(2)}, below).

\begin{lem} \label{lem.3.4}
Let $G$ be an infinite non-abelian $\FC$-group.
\begin{itemize}
\item[(a)] If $\omega(G) = 3$, then $G$ is nilpotent of class $2$ and its exponent $\exp(G)$ is $p$, for some odd prime $p$;
\item[(b)] If $\omega(G) = 4$, then $G$ is nilpotent of class $2$ and the exponent $\exp(G)$ divides $p^2$, for some prime $p$.
\end{itemize}
\end{lem}
\begin{proof}
$(a).$ By Theorem A, $G'$ is finite. By Lemma \ref{lem.center}, the center $\cent(G)$ is nontrivial. Consequently, $G' = \cent(G)$ and $\omega(\cent(G))=2$, so $\cent(G)$ is a finite elementary abelian $p$-group, for some prime $p$. Since $G$ is nilpotent of class at most $2$ and $\cent(G)$ has exponent $p$, it follows that $G$ is a $p$-group (cf. \cite[5.2.22]{Rob}). Combining Corollary \ref{Cor3.3} and Lemma \ref{lem.2-groups} we deduce that the exponent $\exp(G) = p$ for some odd prime $p$. \\

\noindent $(b).$ We first prove that $G$ is nilpotent of class $2$.

By Theorem A, $G'$ is finite. We have $1 < \omega(G') < 4$. Suppose that $\omega(G') = 3$. Since $\cent_{2}(G)$ is an infinite subgroup, we deduce that there is an element $g \in \cent_{2}(G) \setminus G'$. Thus $G = G' \cent_{2}(G)$ because that characteristic subset meets each orbit under $\Aut(G)$. Moreover, if $\cent_{2}(G) < G$, then there exists $h \in G' \setminus \cent_{2}(G)$. Hence $(hg)^{\Aut(G)}$ does not belong to $G'$ and is not in $\cent_{2}(G)$; which is impossible, because $\omega(G) = 4$. Thus $\cent_2(G) = G$ if $\omega(G')=3$. Now we can assume that $\omega(G') = 2$. Consequently, the derived subgroup $G'$ is a finite elementary abelian $p$-group, for some prime $p$. If $G' \cap \cent(G) = \{ 1 \}$, then $G = G' \cent(G)$ and $G$ is abelian, a contradiction. So $G' \cap \cent(G)$ meets the unique nontrivial orbit of $\Aut(G)$ in $G'$, and $G' \leqslant \cent(G)$ follows.

Since $2 \leq \omega(\cent(G)) \leq 3$, we conclude that $\cent(G)$ is a $p$-group. It follows that $G$ is a $p$-group (\cite[5.2.22]{Rob}). By Corollary \ref{Cor3.3}, $\exp(G) \leq p^{2}$.
\end{proof}

The following lemma is a straightforward consequence of \cite[2.1]{BDG}.

\begin{lem} \label{lem.Z}
Let $G$ be a finite non-soluble group with $\omega(G) \leqslant 6$. Then the center $\cent(G)$ is trivial.
\end{lem}

We are now in a position to prove Theorem B.

\begin{proof}[Proof of Theorem B]
$(a)$ By Lemmas \ref{lem.abelian} and \ref{lem.3.4}, $G$ is nilpotent. \\

\noindent $(b)$ Assume that $G$ is an infinite $\FC$-group with $\omega(G) \leqslant 7$. We claim that $G$ is soluble.

Assume that $G$ is non-soluble. Then, $G'$ is also non-soluble. By Theorem A, $G'$ is finite. By  \cite[Theorem 1]{LD}, $\omega(G') \geqslant 4$. Since $G'$ is a proper characteristic subgroup, we deduce that $\omega(G') \leqslant 6$ under the action of $\Aut(G)$ and so, $G' \cap \cent(G) = 1$ (Lemma \ref{lem.Z}). By Lemma \ref{lem.center}, the center $\cent(G)$ is nontrivial. It follows that $\omega(G) \geqslant \omega(G' \cent(G)) \geqslant 8$ (Lemma \ref{lemma2}), which contradicts $\omega(G)\leqslant 7$. \\

\noindent $(c)$ Now assume that $G$ is an infinite non-soluble $\FC$-group with $\omega(G)=8$. Then $G'$ is not soluble, and $\cent(G)$ is not trivial (by Lemma \ref{lem.center}). Suppose that $G' \cap \cent(G) \neq 1$. It follows that $G/(G' \cap \cent(G))$ is a $\BFC$-group with $\omega(G/(G' \cap \cent(G))) \leqslant 7$. We reach the contradiction that $G$ is soluble. So $G' \cap \cent(G)$ is trivial, and the characteristic subgroup $G'\cent(G)$ of $G$ is a direct product $G' \times \cent(G)$. Now $\omega(G') \geqslant 4$ (cf. \cite[Theorem 1]{LD}) yields $8 \leqslant \omega(G' \times \cent(G)) = \omega(G') \cdot \omega(\cent(G)) \leqslant \omega(G)$ (by Lemma \ref{lemma2}). Thus $\omega(G)=8$ enforces $G = G' \times \cent(G)$ and $\omega(\cent(G))=2$. Then $\omega(G')=4$ gives $G' \cong \Alt_5$ (cf. \cite[Theorem 1]{LD}), completing the proof.
\end{proof}

\begin{ex} \label{ex.5}
In a certain sense the above result cannot be improved. \\

\noindent {\bf (i)} The infinite $\FC$-group $\Sym_{3} \times H_{2}$, where $H_{2}$ is an infinite elementary abelian $2$-group, has five orbits under the action of $\Aut(G)$. For each $h \in H_2$, there exists a homomorphism $\varphi_h$ from $\Sym_3$ to $H_2$ mapping $(12)$ to $h$. Putting $\alpha_h(sv):=s(v\varphi_h(s))$ for $s \in \Sym_3$ and $v \in H_2$ defines an automorphism of $\Sym_{3} \times H_2$ mapping $(12)$ to $(12)h$. Therefore the elements $(1 \, 2)$, $(1 \, 2 \, 3)$, $h$, $(1 \, 2 \, 3)h$ are the representatives of nontrivial orbits of $G$. \\

\noindent {\bf (ii)} The infinite non-soluble $\FC$-group $\Alt_5 \times \mathbb{Q}$ has exactly eight automorphism orbits (by Lemma \ref{lemma2}).

\end{ex}

In \cite{S1} Stroppel proposed the following problem (Problem 2.5): classify all the finite non-solvable groups $G$ with $\omega(G) \leq 6$. We answered Stroppel's question by the following result:

\begin{thm} (\cite[Theorem 1]{BDG})  \label{thm.nsoluble}
Let $G$ be a finite non-soluble group with $\omega(G) \leqslant 6$. Then $G$ is isomorphic to one of $\PSL(2,\mathbb{F}_4)$, $\PSL(2,\mathbb{F}_7)$, $\PSL(2,\mathbb{F}_9)$, $\PSL(3,\mathbb{F}_4)$, $\ASL(2,\mathbb{F}_4)$.
\end{thm}

Now, we extend Theorem \ref{thm.nsoluble} to the class of infinite $\FC$-groups.

\begin{cor}
Let $G$ be a non-soluble $\FC$-group with $\omega(G) \leqslant 6$. Then $G$ is finite. Moreover, $G$ is isomorphic to one of $\PSL(2,\mathbb{F}_4)$, $\PSL(2,\mathbb{F}_7)$, $\PSL(2,\mathbb{F}_9)$, $\PSL(3,\mathbb{F}_4)$, $\ASL(2,\mathbb{F}_4)$.
\end{cor}
\begin{proof}
By Theorem B, all infinite $\FC$-group with at most six automorphism orbits are soluble. Since $G$ is non-soluble, it follows that $G$ is finite. Consequently, $G$ is isomorphic to one of the groups indicated in Theorem \ref{thm.nsoluble}. The proof is complete.
\end{proof}

\section{Proof of Theorem C}
Recall that a finite group $K$ is said to be quasisimple if $K = K'$ and $K/\cent(K)$ is simple.

\begin{thmC}
Let $G$ be an infinite non-soluble $\FC$-group with at most eleven automorphism orbits. Then $G$ is central-by-finite.
\end{thmC}

\begin{proof}
Since $G$ is non-soluble, it follows that the derived subgroup $G'$ is non-soluble. By Theorem A, the derived subgroup $G'$ is finite. Thus $\omega(G') \geqslant 4$ (cf. \cite[Theorem 1]{LD}).

Consider $\omega(G') \in \{4,5,6\}$. It follows that $G' \cap \cent_{2}(G) = 1$ (Theorem \ref{thm.nsoluble}). By Hall's result \cite[14.5.3]{Rob}, the second center has finite index in $G$. If $G$ is not central-by-finite, then $\cent(G)$ is a proper subgroup of $\cent_2(G)$ and  $\omega(\cent_{2}(G)) \geq 3$. Hence, $$\omega(G) \geq \omega(G')\omega(\cent_{2}(G)) \geq 12,$$
a contradiction.

Assume that $\omega(G') \in \{7,8,9,10\}$. Set $N = G' \cap \cent_{2}(G)$. Since the derived subgroup  $G'$ is non-soluble, it follows that $\omega (G'/N) \geq 4.$ Consider representatives $g_1N$, $g_2N$ and $g_3N$ for three different non-trivial orbits under $\Aut(G)$ in $G'/N$. Since $[G : \cent_{2}(G)]$ is finite, we can choose $z \in \cent_{2}(G) \setminus G'$. If $zg_{i} \in (zg_{j})^{\Aut(G)}$ for some $1 \leq i \neq j \leq 3$, then there exists $\alpha \in \Aut(G)$ such that
$$zg_{i} = z^{\alpha}g_{j}^{\alpha},$$
that is,
$$g_{i}g_{j}^{-\alpha} = z^{-1}z^{\alpha} \in N.$$
So $g_{i}N \in (g_{j}N)^{\Aut(G)}$, contradicting the choice of representatives. Thus we can conclude that the number of nontrivial orbits of $\Aut(G)$ on $G'/N$ is bonded by $4 - 1 = 3$, because $\omega(G') + |\{z, zg_{1}, zg_{2}, zg_{3}\}| = 11$. It remains to exclude the case when $\omega(G) = 11$,  $G'/N \cong \Alt_{5}$, the derived subgroup $G'$ has seven orbits under the action of $\Aut(G)$, and $\cent_{2}(G) \setminus G'$ is just an orbit. If $\cent(G) \setminus G'$ is a non-empty set, then $G = G' \cent(G)$ and $G$ is central-by-finite. Thus $\cent(G)$ is a subgroup of $G'$ and $N = \cent(G) = \cent(G')$. Since $|G'/N| = 60$, we can deduce that $\omega(\cent(G)) = 2$ under the action of $\Aut(G)$, so $\cent(G)$ is a finite elementary abelian $p$-group for some prime $p$. Since the second center $\cent_{2}(G)$ is infinite and $\cent_2(G) \setminus \cent(G)$ contains just an orbit under the action of $\Aut(G)$, it follows that $\omega(\cent_2(G))=3$ is a $p$-group for some odd prime $p$ (by Lemma \ref{lem.3.4}). Note that $G' = [G', G']$ and $G'/\cent(G') = \Alt_{5}$, then $G'$ is a quasisimple group. Hence the center $\cent(G) = \cent(G')$ is isomorphic to a subgroup of the Schur Multiplier $M(\Alt_5) = C_2$ (cf. \cite[Proposition 2.1.7 and Theorem 2.12.5]{Kar}), which is impossible. The proof is complete.
\end{proof}

Summarizing, we have the following classification of infinite non-soluble $\FC$-groups with at most eleven automorphism orbits.

\begin{cor}
Let $G$ be an infinite non-soluble $\FC$-group with $\omega(G) \leqslant 11$. Then $G$ is isomorphic to one of the groups in the set
$$\{\PSL(2, \mathbb{F}_{q}) \times \cent(G), \, \SL(2, \mathbb{F}_5) \times H_2 \mid q \in \{4, 7, 8, 9\} \},$$
where $\omega(\cent(G)) = 2$ and $H_{2}$ is an infinite elementary abelian $2$-group.
\end{cor}

\begin{proof}
Since the derived subgroup $G'$ is non-soluble, it follows that $\omega(G') \in \{4, 5, 6, 7, 8, 9, 10\}$ (under action of $\Aut(G)$).

Assume that $\omega(G') \in \{4, 5, 6 \}$. Arguing as in the proof of Theorem B (c), we deduce that  $G$ is isomorphic to one of the following groups: $$\PSL(2, \mathbb{F}_{q}) \times \cent(G),$$ where $q \in \{4, 7, 8, 9\}$ and $\omega(\cent(G)) = 2$.

Now assume that $\omega(G') \in \{7, 8, 9, 10 \}$.  Arguing as in the proof of Theorem C, we can conclude that the Schur multiplier $M(\Alt_5) = C_2$ and $|\cent(G)| \leqslant 2$. In particular,  $G'$ is isomorphic to one of $\SL(2, \mathbb{F}_5)$ or $\Alt_5$, so $G \cong \SL(2,\mathbb{F}_5)\cent(G)$. In particular, $G \cong \SL(2,\mathbb{F}_5) \times H_2$, where $H_2$ is an infinite elementary abelian $2$-group. The result follows.
\end{proof}

\section{Neumann's groups}

Groups with three automorphism orbits are called almost homogeneous groups. In \cite{MS1}, M\"aurer and Stroppel prove that the nilpotent almost homogeneous groups with exponent $p$ are generalized Heisenberg group (see also Example \ref{ex.H}, below). In the same article, M\"aurer and Stroppel show that a soluble almost homogeneous group with non-trivial center is nilpotent of class $2$. By Lemma \ref{lem.3.4}, all non-abelian infinite $\FC$-groups $G$ with three automorphism orbits are nilpotent and $\exp(G)=p$ for some odd prime $p$. We present some examples of infinite FC-groups now, we determine the number of orbits under their respective automorphism orbits. The following construction of $\BFC$-groups is due to Neumann \cite{N}.

\begin{ex} (Almost homogeneous $p$-groups) \label{ex.H}
Let $p$ a prime and $\N(p)$ be the group generated by
$$a_{i}, b_{i}, \, i = 1, 2, ..., n, ...$$
with the relations
$$[a_{i}, b_{j}] = [a_{i}, a_{j}] = 1, \, i \neq j,$$
$$[a_{i}, b_{i}] =c, \, c^{p} = [a_{i}, c] = [b_{i}, c] = 1.$$

If $p$ is odd, then $\N(p)$ is isomorphic to the generalized Heisenberg group $\GH(\V, \mathbb{F}_{p}, \beta)$, where $\V$ is a vector space of countably infinite dimension over the field $\mathbb{F}_{p}$ with $p$ elements (see \cite[page 235]{MS1} for more details). Moreover, $\omega(\GH(\V,\mathbb{F}_{p},\beta))=3$. Its center and derived subgroups are $\langle c \rangle$, thus it is nilpotent of class $2$ and each nontrivial normal subgroup of $\N(p)$ contains the subgroup $\langle c \rangle$. Hence $\{\N(p) \mid \, p \text{ odd prime}\}$ is an infinite family of almost homogeneous $\BFC$-group which are not central-by-finite.
\end{ex}

It is well known that every group of exponent $2$ is abelian. By Lemma \ref{lem.2-groups}, an infinite non-abelian $2$-group and $\BFC$-group has at least four automorphism orbits. We obtain the following related result.

\begin{ex} \label{ex.n(2)}
The $\BFC$-group $\N(2)$ has exactly four automorphism orbits.
\end{ex}

\begin{proof}
It is clear that $\N(2)$ is hopfian and every surjective endomorphism is an automorphism.

Let $I$ and $J$ be subsets of the set of positive integers, with $|I| = |J|$, and $\sigma: I \rightarrow J$ a bijection. We collect some facts:

\noindent i) The homomorphism $\alpha_{I}: \N(2) \rightarrow \N(2)$ that extends the map
$$a_{i} \mapsto b_{i}, b_{i} \mapsto a_{i}$$
if $i \in I$ and
$$a_{i} \mapsto a_{i}, b_{i} \mapsto b_{i}$$
if $i \in \mathbb{N} \setminus I$, is an automorphism.

\noindent ii) The homomorphism $\beta_{IJ}: \N(2) \rightarrow \N(2)$ that extends the map
$$a_{i} \mapsto a_{i^{\sigma}}, \, b_{i} \mapsto b_{i^{\sigma}}, \, a_{i^{\sigma}} \mapsto a_{i}, \, b_{i^{\sigma}} \mapsto b_{i}$$
if $i \in I$ and
$$a_{i} \mapsto a_{i}, b_{i} \mapsto b_{i}$$
if $i \in \mathbb{N} \setminus I$, is an automorphism.

\noindent iii) Any element $g \in \N(2)$ can be written in the form
$$g = (a_{i_{1}}b_{i_{1}} ... a_{i_{l}}b_{i_{l}})(a_{j_{1}} ... a_{j_{k}})(b_{t_{1}} ... b_{t_{m}})c^{\delta},$$
where $\delta = 0, 1$ and the set $\{i_{1}, ..., i_{l}, j_{1}, ..., j_{k}, t_{1}, ..., t_{m}\}$ has $l + k + m$ elements. If $l$ is even then $g$ has order $2$ and if $l$ is odd then $g$ have order $4$.

Given $g$ of order $2$, consider $I_{1} = \{i_{1}, ..., i_{l}\}$, $I_{2} = \{j_{1}, ..., j_{k}\}$, $I_{3} = \{t_{1}, ..., t_{m}\}$, $J_{1} = \{1, ..., l\}$, $J_{2} = \{l+1, ..., l+k\}$, $J_{2} = \{l+k+1, ..., l+k+m\}$, and $\sigma_{1} : I_{1} \rightarrow J_{1}$, $\sigma_{2} : I_{2} \rightarrow J_{2}$, $\sigma_{3} : I_{3} \rightarrow J_{3}$ the canonical bijection maps from $I_{r}$ to $J_{r}$, with $r = 1, 2, 3$. Hence
$$h = g^{\alpha_{I_{3}} \beta_{I_{1}J_{1}} \beta_{I_{2}J_{2}} \beta_{I_{3}J_{3}}} = (a_{1}b_{1} ... a_{l}b_{l})(a_{l+1} ... a_{l+k})(a_{l+k+1} ... a_{l+k+m})c^{\delta} =$$
$$= (a_{1}b_{1} ... a_{l}b_{l}) a_{l+1}...a_{s}c^{\delta}$$
with $s = l+k+m$. Now, define the sequences
$$x_{1} = a_{1}b_{1} ... a_{l}b_{l}, x_{2} = b_{1}a_{2}, ..., x_{l} = b_{1}a_{l}, x_{l+1} = a_{l+1}, ...,$$
$$y_{1} = b_{1}, y_{2} = b_{1}b_{2}, ..., y_{l} = b_{1}b_{l}, y_{l+1} = b_{l+1}, ...$$
and
$$u_{1} = a_{1}, ..., u_{l} = a_{l}, u_{l+1} = a_{l+1}...a_{s}c^{\delta}, u_{l+2} = a_{l+2}, ...,$$
$$ v_{1} = b_{1}, ..., v_{l} = b_{l}, v_{l+1} = b_{l+1}, v_{l+2} = b_{l+1}b_{l+2}...,$$
$$v_{s} = b_{l+1}b_{s}, v_{s+1} = b_{s+1}, ....$$
Note that $\{x_{i}, y_{i}; i = 1, 2, 3, ...\}$ and $\{u_{i}, v_{i}; i = 1, 2, 3, ...\}$ are generating sets of $G$ and satisfy its  relations. It follows that the homomorphisms $\alpha: \N(2) \rightarrow \N(2)$ and $\beta: \N(2) \rightarrow \N(2)$ that extend, respectively, the maps
$$x_{i} \mapsto a_{i}, \, y_{i} \mapsto b_{i}$$
and
$$u_{i} \mapsto a_{i}, \, v_{i} \mapsto b_{i}$$
are automorphisms. Therefore
$$h^{\alpha \beta} = a_{1}a_{l+1}.$$
Since there exists $\gamma \in \Aut(\N(2))$ such that $(a_{1}a_{l+1})^{\gamma} = a_{1}$, we conclude that $g$ and $a_{1}$ are in the same orbit.

If $l$ is odd, there exists an automorphism $\mu \in \Aut(\N(2))$ such that $$[(a_{2}b_{2} ... a_{l}b_{l}) a_{l+1}...a_{s}c^{\delta}]^{\mu} = a_{2}$$ and $a_{1}^{\mu} = a_{1}, b_{1}^{\mu} = b_{1}$, that is,
$$h^{\mu} = a_{1}b_{1}a_{2} = (a_{1}a_{2})b_{1}.$$
Note that there exists $\eta \in \Aut(\N(2))$ such that $(a_{1}a_{2})^{\eta} = a_{1}$, $b_{1}^{\eta} = b_{1}$. Thus $h^{\mu\eta} = a_{1}b_{1}$ and $g$ and $a_{1}b_{1}$ are in the same orbit. Therefore,
$$\N(2) = \{1\} \uplus \{c\} \uplus a_{1}^{\Aut(\N(2))} \uplus (a_{1}b_{1})^{\Aut(\N(2))}.$$
\end{proof}

\begin{ex} \label{ex.12}
Let $p$ be an odd prime. Then $\N(p) \times \Alt_5$ is an infinite non-soluble $\BFC$-group with $\omega(\N(p) \times \Alt_5)=12$ (by Lemma \ref{lemma2}). This group is not central-by-finite, so the bound on the number of orbits in Theorem C is a sharp one.
\end{ex}


TITLE: Almost Trivial $\sigma-$fields
QUESTION [2 upvotes]: I am trying to understand the proof of the following Lemma form the book A probability path by sidney Resnick.
Lemma: Let $\mathcal{G}$ be an almost trivial $\sigma-\text{field}$ and let $X$ be a random variable measurable with respect to $\mathcal{G}$. Then there exists $c$ such that $P[X=c]=1$.
Let $F(x)=P[X\leq x]$. Then $F$ is non-decreasing and since $[X \leq x] \in \sigma(X)\subset \mathcal{G}$, $F(x)=0$ or $1$ for each $x \in \mathbb{R}$. Let
$c=\sup\{x: F(x)=0\}$.
The distribution must have a jump of size $1$ at $c$ and thus $P[X=c]=1$. Why $\sup\{x: F(x)=0\}$  can't be $\infty$?

REPLY [1 votes]: Because $F$ is a distribution function, it must satisfy
$$
\lim\limits_{x\to\infty}F(x)=1
$$
This implies that there exist a $N$ such that  $F(x)>1/2$ for every $x\geq N$ (since $F$ is nondecreasing). This means that $N$ is an upper bound for the set $\{x:F(x)=0\}$ and so $\sup\{x:F(x)=0\}<\infty$.


TITLE: Taylor Expansion of Normal CDF
QUESTION [2 upvotes]: I read the following paragraph which claims to be the Taylor expansion of standard normal CDF for positive $x$.
$1 - \frac{1}{\sqrt{2\pi}}e^{-\frac{x^2}{2}}  (a_1k + a_2k^2 + a_3k^3 + a_4k^4 + a_5k^5)$,
where $k:=\frac{1}{1+0.2316419x}, a_1=0.319381530, a_2=-0.356563782, a_3=1.781477937, a_4=-1.821255978, a_5=1.330274429.$
I do not get how this is derived even though I am numerically convinced of its truth. Could anyone explain this to me, please?

REPLY [3 votes]: This is no Taylor expansion. It is a rational approximation listed as
formula 26.2.17 in Abramowitz / Stegun (see http://people.math.sfu.ca/~cbm/aands/page_932.htm)  and attributed to Hastings (1955), Approximations for Digital Computers.


TITLE: How many cells will be born before it dies?
QUESTION [3 upvotes]: A given cell can replicate at rate $\lambda$ and die at rate $\mu$. Upon replication, the cell divides into 2.

The question asks: how many cells will be produced by this cell before it dies?

My interpretation:
Case 1) I only count the cells which are born directly by this cell, e.g. if it replicates, I don't count the replications of the 2nd cell.
Case 2) I consider the total number of cells generated.

Case 1: With probability $\lambda / \mu$ the cell will replicate before it dies, with probability $(\lambda / \mu)^2$ it will replicate twice and so on using the memoryless property of the exponential. Each time we get an extra cell, hence we have $E(X)=\sum_1^\infty (\lambda /\mu)^i \times i$
Case 2: I don't know how to include all possible divisions of daughter cells. Maybe it's not required?

REPLY [1 votes]: For your case 1, your calculation is not quite correct. The probability of no offspring is $\dfrac{\mu}{\lambda+\mu}$, of exactly one offspring $\dfrac{\lambda\mu}{(\lambda+\mu)^2}$, of two $\dfrac{\lambda^2\mu}{(\lambda+\mu)^3}$ etc. giving the expectation  $$\sum_{i=0}^\infty i\dfrac{\lambda^i\mu}{(\lambda+\mu)^{i+1}} = \sum_{i=1}^\infty  \dfrac{\lambda^i}{(\lambda+\mu)^{i}} = \dfrac{\lambda}{\mu}$$
An alternative way would be to assume the expectation was $x$ and then using memorylessness to solve $x=\dfrac{\lambda}{\lambda+\mu}(1+x)$ to give $x=\dfrac{\lambda}{\mu}$ again
The latter approach works for case 2 too.  Suppose its expectation is $y$.  You would then want to use memorylessness to solve $y=\dfrac{\lambda}{\lambda+\mu}(1+2y)$ to give $y=\dfrac{\lambda}{\mu-\lambda}$, at least when $\mu \gt \lambda$


TITLE: Proof of infinitude of primes whose reversal in base 10 is also prime
QUESTION [3 upvotes]: Is there any proof of infinitude of A007500 primes?
If you want to generate them here is trivial and naive python program.
def is_prime(n):
    i = 2
    while i*i <= n:
        if n%i == 0:
            return False
        i = i + 1
    else:
        return True

print [x for x in range(1,200) if is_prime(x) and is_prime(int(str(x)[::-1]))]

REPLY [1 votes]: Now, thinking about this a bit, let's say $f$ is the function that reverses the digits, so that $f(n)$ is the number that has the digits of $n$ in base 10 reversed. I think that when estimating $$|\{n \leq x: n,f(n) \mbox{ simultaneously prime}\}|,$$
then for each prime $p$, maybe you'll have to estimate the number of solutions to
$$
nf(n) \equiv 0 \bmod p,
$$
where $n \in \mathbb{Z}/p\mathbb{Z}$. This is similar to like when estimating the twin prime constant (but I'm not claiming that the whole thing goes through the same way). The problem is that $f(n)$ is not so straightforward like $n+2$ is.
For $p=3$, at least $f(n) \equiv n \bmod 3$, so that is ok. $p=11$ is also not too bad. For other $p$, it doesn't seem so straightforward.
In fact, it's not even as straightforward as this, because for $n,f(n)\in \mathbb{Z}$, when one fixes $n \bmod p$, $f(n) \bmod p$ is not fixed in general. The point is just that I think one might have to estimate the probability that $p\nmid f(n)\in \mathbb{Z}$, given that $p\nmid n\in \mathbb{Z}$.


TITLE: How to determine splitting field on $\mathbb{Q}$ of $f(X)= x^{15}-x^8-x^7+1$ and determine the degree over $\mathbb{Q}$
QUESTION [0 upvotes]: Let $$f(X) \in \mathbb{Q} $$ such that $$f(X)= X^{15}-X^8-X^7+1=0$$
       Determine splitting field over $\mathbb{Q}$ of $f(X)$
I know that i have to find roots of f but I have trouble.
$$\small f(X)=(x^{8}-1)(x^7-1)
=(x^4-1)(x^4+1)(x^7-1)
=(x^2-1)(x^2+1)(x^4+1)(x^6+x^5+x^4+x^3+x^2+x+1)(x-1)
=(x-1)^2(x+1)(x^2+1)(x^4+1)(x^6+x^5+x^4+x^3+x^2+x+1)$$
So root are $\pm i, \pm 1, \pm \sqrt[4]{-1}$ and  $\sqrt[7]{-1} $
So now
the splitting field over $\mathbb {Q}$ is  $\mathbb {Q}(i,\sqrt[4]{-1},\sqrt[7]{-1})$ ?

REPLY [1 votes]: Hint.- A useful factorization of your polynomial is $$f(x)=(x^8-1)(x^7-1)$$
$$x^8-1=(x^2-1)(x^2+1)(x^2-\sqrt2 x+1)(x^2+\sqrt2 x+1)$$ $$x^7-1=(x-1)(x^6+x^5+x^4+x^3+x^2+x+1)$$
so the corresponding roots are
$$\pm1,\pm i,\frac{\sqrt2(1\pm\sqrt i)}{2},\frac{\sqrt2(-1\pm\sqrt i)}{2}$$ and
 $$1,\cos\frac{2k\pi}{7}+i\sin\frac{2k\pi}{7}; k=1,2,3,4,5,6$$
from which your splitting field $K|\mathbb Q$ simplifying carefully, when elements are not $\mathbb Q$-linearly independent (for example i and -i and remember that $x^7-1$ defines an easy cyclotomic field of degree $6$ over $\mathbb Q$).


TITLE: The modulus of smoothness of $c_0$ by an equivalent norm
QUESTION [0 upvotes]: Let $(X,\|\cdot\|)$ be a Banach space. For $t>0$, the modulus of smoothness of $\|\cdot\|$ is defined by
$\rho_X(t)=\sup\left\{\dfrac{\|x+ty\|+\|x−ty\|}{2}−1:x,y\in S_X\right\}$. We define an equivalent norm $\|\cdot\|$ on $c_0$ by setting$$\|x\|=\sup_{n\in N}|x_n|+\sum_{n=1}^\infty2^{-n}|x_n|, \text{ for all }  x=(x_n)_{n=1}^\infty \in c_0$$. I want to find the modulus of smoothness of $(c_0, \|\cdot\|)$.
 Thanks you help

REPLY [1 votes]: By the triangle inequality, the modulus of smoothness satisfies $\rho_X(t)\le t$. I claim that in fact $\rho_X(t)=t$ for all $t$.
Consider the two-dimensional space $V_n = \{ \alpha e_{n} +\beta e_{n+1}: \alpha,\beta\in\mathbb R\}$. Observe that
$$ \max(|\alpha|,|\beta|) \le  \|x \| \le (1+2^{1-n})\max(|\alpha|,|\beta|)$$
Therefore, as $n\to\infty$, the modulus of smoothness of $V_n$ tends to  the modulus of smoothness of two-dimensional $\ell_\infty$ space, $\ell_\infty^2$. For the latter the modulus is $\rho(t)=t$, as is shown by $x=e_{n}+e_{n+1}$ and $y = t(e_n-e_{n-1} )$.


TITLE: Prove a convergent sequence has either a minimum, a maximum or both.
QUESTION [6 upvotes]: Let $a_n$ be a convergent sequence. Prove $a_n$ has a minimum, a maximum or both.
I am being prepared for a final exam, which is why it is important to me to know that $I$ am correct in $my$ attempt. Of course if I am completely wrong, hints or solution are welcome. Thanks.
$Attempt$: $a_n$ converges to a limit $L\in \Bbb{R}$ as $n\to \infty$. Therefore, for $\epsilon=1$ we get, for large enough $N$ that $\forall n\ge N,$ $|a_n-L|<1$ $\Rightarrow$ $L-1 \le a_n\le L+1$, in particular $a_n\le L+1$. Therefore, for $M=max(a_1,a_2,...,a_N,L+1)$, $a_n\le M$ necessarily. i.e, $a_n$ is upper bounded. The same can be shown with lower bound. If $a_n$ is constant, we are done. Otherwise, the lower and the upper bounds are different. Suppose $a_n$ has no minimum nor maximum, then both lower and upper bound are accumulation point, a contradiction. Therefore $a_n$ has a maximum or a minimum in that case.

REPLY [3 votes]: We use the notation of the OP. The result is clear if all the $a_k$ are equal to the limit $L$. Thus we can assume that for some $k_0$ we have $a_{k_0}\ne L$. For simplicity let $a_{k_0}=c$. By symmetry we can suppose that $c\gt L$.
By the definition of limit, there is an index $N$ such that $|a_n-L|\lt c-L$ if $n\gt N$. In particular,  $a_n\lt c$ for $n\gt N$.
The (multi)set $\{a_1,a_2,\dots,a_N\}$ has a maximum $b$, and $b\ge a_k$ for all $k$.


text:
\section{Notation} \label{s:Setup}

We now present some notation that will be used in the main theorems and throughout the paper. \ri{Notation used throughout this paper is tabulated in Tables \ref{t:Table1}-\ref{t:Table2}.}

\input{diffmaps_symbols_v6}

\subsection{Operators}\label{ss:Operators}

\ri{Recall that our domain is $\domain = (\mathbb{R} / L\mathbb{Z})^d$.}
We will use as our kernel function the periodic Gaussian kernel $k_\eps(x,y) = g_{\eps,L}(y-x)$:
\begin{align} g_{\eps,L}(x) &= \sum_{\mathbf{j} \in \mathbb{Z}^d} g_\eps(x + L\mathbf{j}), \label{eq:GaussianKernelL}\end{align}
where the standard Gaussian kernel is
\begin{align} g_\eps(x) &= (2\pi \eps)^{-d/2} e^{-\|x\|^2/2\eps}. \label{eq:GaussianKernel}\end{align}
Note that if, as is typical, the bandwidth $\sqrt{\eps} \ll L$, all but one summand in \R{eq:GaussianKernelL} will be superexponentially small.

We define convolution by the periodic Gaussian kernel \R{eq:GaussianKernelL} as an operator
\begin{equation} (\C_\eps\phi)(x) = \int_\domain g_{\eps,L}(y-x) \phi(y)\, \dd x, \label{eq:Convolution}\end{equation}
which has the semigroup property $\C_s \C_t = \C_{s+t}$.

In this paper we will interpolate the vectors and matrices introduced in the introduction by functions defined on the continuous domain $\domain$. Our interpolation arises very naturally: the kernel matrix $\Km$ defined in \R{eq:KernelMatrix} acting on vectors $(\phi(x^i))_{i = 1,\ldots,M}$ extends to the following operator
\begin{equation} (\D^M_\eps \phi)(x) := \frac{1}{M} \sum_{i=1}^M g_{\eps,L}(x-x^i) \phi(x^i) = (\C_\eps \rho^M \phi)(x), \label{eq:DMeps} \end{equation}
where $\rho^M$ is the empirical measure of the sample. In particular, if we define the restriction to sample points $\varpi(\phi) = (\phi(x_i))_{i = 1,\ldots, M}$, then $\varpi \circ \D^M_\eps = \Km \circ \varpi$.

For Sinkhorn weights our weight vector $u$, defined in \R{eq:SinkhornWeightsDiscrete}, then extends to the function $U^M_\eps$ given as the unique solution of
\begin{equation} U^M_\eps(x)\, (\D^M_\eps U^M_\eps)(x) \equiv 1, \label{eq:SinkhornDiscretisation} \end{equation}
so $\varpi(U^M_\eps) = u$.

Our normalised matrix then extends to the operator
\begin{align}
(\P^M_\eps \phi)(x) &= U^M_\eps(x) (\D^M_{\eps}U^M_\eps\phi)(x). \label{eq:SemigroupDiscrete}
\end{align}
Since $P \circ \varpi = \varpi \circ \P^M_\eps$, $P$ and $\P^M_\eps$ will have identical (non-zero) spectra and identical eigenvectors (up to $\varpi$).

We will study a range of weighted operators of a form similar to \R{eq:SemigroupDiscrete} and we will write them for short in the following manner:
\begin{align*}
\P^M_\eps &= U^M_\eps \D^M_{\eps}U^M_\eps.
\end{align*}

In this paper we are required to consider two limits and their associated errors: the stochastic, so-called ``variance'' error as the finite sample size $M\to\infty$ for fixed timestep $\eps$, and the deterministic, so-called ``bias'' error, in the spatial continuum limit as the timestep $\eps \to 0$. We will show in Section \ref{s:Particle} that the discrete kernel operator $\D^M_\eps$ converges in the $M\to\infty$ data limit to a continuum kernel operator
\begin{equation} (\D_\eps\phi)(x) = \int g_\eps(x-y) \phi(y) \rho(y) \,\dd y = (\C_\eps\rho\phi)(x) \label{eq:Deps}. \end{equation}

In the infinite data limit we will show in Section \ref{s:ParticleSinkhorn} that the $U^M_\eps$ converge to functions $U_\eps$ that satisfy a continuum version of the Sinkhorn problem
\begin{equation} U_\eps(x)\, (\D_\eps U_\eps)(x) \equiv 1. \label{eq:SinkhornProblem} \end{equation}

From this we have a deterministic approximation to the semigroup $e^{\eps \calL}$
\begin{align}

\P_\eps &= U_\eps \D_{\eps} U_\eps, \label{eq:SemigroupDeterministic}
\end{align}
to which we expect the normalised discrete operator $\P^M_\eps$ to converge.

Because the two limits require the use of different function spaces to attain the appropriate convergence rates we will consider semi-conjugacies of our operators $\P^M_\eps$ and $\P_\eps$ that will be bounded on the space of continuous functions $C^0$. For concision, in this discussion we will take ``$\mathcal{A}^{(M)}_\eps$'' to mean ``$\mathcal{A}_\eps$ (resp. $\mathcal{A}^M_\eps$)''.

Using that $\D^{(M)}_{\eps} = \C_{\eps/2} \D^{(M)}_{\eps/2}$ we will define the half-step weight functions
\begin{align}
Y^{(M)}_\eps(x) = (\D^{(M)}_{\eps/2} U^{(M)}_\eps)(x) \label{eq:Y}
\end{align}
and the half-step operators
\begin{align}
\J^{(M)}_\eps &= U^{(M)}_\eps \C_{\eps/2} Y^{(M)}_\eps \label{eq:J} \\
\K^{(M)}_\eps &= (Y^{(M)}_\eps)^{-1} \D^{(M)}_{\eps/2} U^{(M)}_\eps. \label{eq:K}
\end{align}
These operators $\J^{(M)}_\eps, \K^{(M)}_\eps$ are positive, preserve constant functions and have
\[ \P^{(M)}_\eps = \J^{(M)}_\eps \K^{(M)}_\eps. \]
We then define the following operators that are semi-conjugate to $(\P^M_\eps)^n$
\begin{align}
\M^{(M)}_{n,\eps} &= (\K^{(M)}_\eps \J^{(M)}_\eps)^n \label{eq:M}.
\end{align}

\\

To study the situation for the standard weights, we will define the kernel density estimate of the distribution using the sample:
\begin{equation} \rho^{(M)}_\eps = \D^{(M)}_\eps 1 \label{eq:RhoEpsDef} \end{equation}
The weight vectors $\check u_\alpha := (\Km 1)^{-\alpha}$ and $1/(\Km \check u_\alpha)$ then extend respectively to the functions
\begin{align}
\check{U}^{(M)}_{\eps,\alpha}(x) &= (\rho^{(M)}_\eps(x))^{-\alpha}. \label{eq:StandardDiscretisationU} \\
\check{V}^{(M)}_{\eps,\alpha}(x) &= 1/(\D^{(M)}_\eps\check{U}^{(M)}_{\eps,\alpha})(x). \label{eq:StandardDiscretisationV}
\end{align}
We then have the approximations to the semigroup $e^{\eps \check{\calL}_\alpha}$
\begin{equation} \check{\P}^{(M)}_{\eps,\alpha} = \check{V}^{(M)}_{\eps,\alpha} \D^{(M)}_{\eps,\alpha} \check{U}^{(M)}_{\eps,\alpha}, \label{eq:StandardDiscretisationP}
\end{equation}
We then define operators $\check{\J}^{(M)}_{\eps,\alpha}, \check{\K}^{(M)}_{\eps,\alpha}, \check{\M}^{(M)}_{\eps,\alpha}$ analogously to the Sinkhorn weight case (see \RR{eq:YStandard}{eq:MStandard}).

\subsection{Function spaces}\label{ss:FunctionDef}

We will use two different classes of function spaces to study the bias and variance error. To study the variance error, we will need spaces with very strongly compact embeddings into $C^0$, specifically Hardy spaces of analytic functions. On the other hand, when considering the bias error we are comparing against the semigroup $e^{\eps \calL}$, and because of our relaxed conditions on the regularity of $\rho$, we can only expect the image of the semigroup to be contained in spaces of low differentiability.

To study the bias error, we will therefore make use of the scales of Sobolev spaces $\W[p]{s} \subseteq L^p(\domain,\dd x)$ for $s \geq 0, p \in (1,\infty]$, which each consist of function classes $[\phi]$ for which the norm
\[ \| \phi \|_{\W[p]{s}} := \| J^{s/2} \phi \|_{L^p},\]
is finite and well-defined, where the operator $J = I - \Delta$. For some operator $\mathcal{A}$ that is sectorial (see Section \ref{s:FunctionResults}) and thus for which a semigroup $e^{-\mathcal{A}t}, t\geq 0$ is defined, we define fractional powers as inverses of the injections \citep{Henry06}
\begin{equation} \mathcal{A}^{-s/2} := \Gamma(s/2)^{-1} \int_0^\infty t^{-s/2-1} e^{-t\mathcal{A}}\,\dd t,\, s>0.
\label{eq:FractionalPower} \end{equation}
The operator $J$ is sectorial on all $\W[p]{s}$ \citep{Haase06}.

For integer $k\geq 0$ the space of $k$-times continuously differentiable functions $C^k$ is a subset of $\W{k}$ with equivalent norms. Furthermore, for all $s' < s$, the H\"older space $C^{s'} \subseteq \W{s}$, and each $[\phi] \in \W{s}$ has an element $\phi \in C^{s}$: the inclusion maps between these function spaces are continuous.
\\

On the other hand, to study the convergence of the particle discretisation (i.e.~the variance error), we will use spaces of bounded analytic functions on narrow strips around the domain $\domain$. We therefore define for $\zeta \geq 0$ the complex domains
\[ \domain_\zeta = \{ x + iz \mid x \in \domain, z \in [-\zeta,\zeta]^d \}, \]
and the corresponding Hardy space
\[ H^\infty(\domain_\zeta) = \{ \phi \in C^0(\domain_\zeta) : \phi \textrm{ analytic on }\intr \domain_\zeta\} \]
with norm
\begin{equation} \| \phi \|_{\zeta} = \sup_{z \in \domain_\zeta} | \phi(z)|. \label{eq:HardyNormDefinition}\end{equation}
Note that the Hardy space norm $\| \cdot\|_{\zeta}$ is always equal to or greater than $\|\cdot\|_0$, the $C^0$ norm on the real domain $\domain$.

These Hardy spaces encode the smoothness of the Gaussian kernel: \rii{unlike if we used a $C^k$ space, this allows for very good local compact embedding results into $C^0$. On the other hand, our choice of thin strips $\domain_\zeta$ as our complex domain allows the kernel to have $\bigO(1)$ norm as an operator $C^0 \to H^\infty(\domain_\zeta)$, if we take $\zeta$ to scale with the $\bigO(\eps^{1/2})$ kernel bandwidth}.
\\

In this paper we will assume that our measure density $\rho$ is strictly bounded away from zero, and that it lies in the Sobolev space $\W{s}$, where $s > 3/2$ for the standard normalisation and $s>2$ for the Sinkhorn normalisation: it is equivalent to assume that $\rho \in C^{3/2+\beta}$ (resp. $\rho \in C^{2+\beta}$) for some $\beta > 0$.

\subsection{Eigendata}\label{ss:Eigenspaces}

The generator $\calL$ has eigenvalues $0 = -\lambda_0 > -\lambda_1 \geq -\lambda_2 \geq \cdots$, and the semigroup approximations $\P^{(M)}_\eps$ have respective eigenvalues $1 = e^{-\eps\lambda_{0,\eps}^{(M)}} > e^{-\eps\lambda_{1,\eps}^{(M)}} \geq e^{-\eps\lambda_{2,\eps}^{(M)}} \geq \cdots \geq 0$. That is, $-\lambda_{0,\eps}^{(M)},-\lambda_{1,\eps}^{(M)},\ldots$ are the estimates of the Laplacian eigenvalues obtained from the semigroup approximations.

Note that the non-negativity of these eigenvalues is guaranteed via positive semi-definiteness of $\P^{(M)}_\eps$ in $L^2(\rho^{(M)})$. We denote the corresponding eigenspaces $E_k, E_{k,\eps}^{(M)}$, and merge discretised eigenspaces whose eigenvalues will converge in the limit:
\[ \bar E_{k,\eps}^{(M)} := \bigoplus_{\lambda_j = \lambda_k} E_{k,\eps}^{(M)}. \]

For the standard weights we define equivalent quantities: \ri{$\check \lambda_{k,\alpha}$ the eigenvalues of $\check \calL_{\alpha}$ with eigenspaces $\check E_{k,\alpha}$, and $e^{-\eps \check\lambda^{(M)}_{k,\eps,\alpha}}$ the eigenvalues of $\check\P^{(M)}_{\eps,\alpha}$ with eigenspaces $\check{\bar{E}}^{(M)}_{k,\eps,\alpha}$ (merged appropriately for degenerate eigenvalues of the limiting generator $\check{\calL}_\alpha$).}
Note that we have positive semi-definiteness of $\check\P^{(M)}_{\eps,\alpha}$ in $L^2(\rho^{(M)}(\check U^{(M)}_{\eps,\alpha}/\check V^{(M)}_{\eps,\alpha})^{1/2})$).

Finally, to quantify the convergence of eigenspaces, we define the distance between vector subspaces:
\begin{equation} d_{C^0}(E,F) = \max\left\{\sup_{\phi \in B_{C^0}(1) \cap E} \inf_{\psi \in F} d_{C^0}(\phi,\psi), \sup_{\phi \in B_{C^0}(1) \cap F} \inf_{\psi \in E} d_{C^0}(\psi,\phi)\right\}. \label{eq:dCO} \end{equation}
This distance $d_{C^0}$ therefore quantifies the distance between subspaces in the $L^\infty$ norm.

	\subsection{Dependency of constants}

All constants in our paper depend only on: the dimension of the manifold $d$, the side-length of the domain $L$, the Sobolev differentiability parameter of the density $s$, the Sobolev norm of the log-density $\| \log \rho \|_{\W{s}}$, and the upper limit on the timestep $\eps_0$.

Constants specifically pertaining to eigendata (i.e. those in Section \ref{s:Spectral}, Theorems \ref{t:EigendataStandard}-\ref{t:Eigendata}, and Corollary \ref{c:GraphLaplacian}) also depend on the eigendata of the generator $\mathcal{L}$ or $\check{\mathcal{L}}_\alpha$, specifically the lower bound  $-\lambda_*$ on the eigenvalues under consideration, and the minimum separation between points in $(\sigma(\mathcal{L}) \cap (-\lambda_*,0]) \cup \{-\lambda_*\} $ (respectively for $\check{\mathcal{L}}_\alpha$).

\section{Main results}\label{s:Theorems}

In this paper we will deterministically bound the ``variance'' errors, which depend on the empirical measure $\rho^M$, exclusively via an operator error $\delta$:
	\begin{equation}
\delta := \left\| \D^M_{\eps/2} - \D_{\eps/2}\right\|_{H^\infty(\domain_\zeta) \to C^0}, \label{eq:DeltaDef}
\end{equation}
where $\zeta = Z_0 \eps^{1/2}$ for some constant $Z_0$, and $H^\infty(\domain_\zeta)$ is defined in \R{eq:HardyNormDefinition}. Thus, results in terms of $\delta$ can be applied to any point sample, including weighted, dependent and deterministic samples.

When the empirical measure is an {\em i.i.d.} sample from the true density $\rho$, we have the following probabilistic bound on $\delta$:
\begin{theorem}\label{t:Delta}
	Suppose $\rho \in L^\infty$. There exist constants ${{C}}_1, {{C}}_{2}$ depending only on $L$, $d$, $\rhonm$, $\eps_0$, $Z_0$ such that for all $\eps < \eps_0$ and $c < \tfrac{3}{4} \rhonm$,
	\begin{equation*} \Pr\left(\delta > c\right) \leq \exp\left\{{{C}}_1 (\log c + \log\eps^{-1})^{2d+1} - {{C}}_{2} M  \eps^{d/2} c^2 \right\}. \label{eq:DeltaBound} \end{equation*}

\end{theorem}

In other words, with very high probability
\[ \delta = \bigO\left(M^{-1/2} \eps^{-d/4} (\log M + \log \eps^{-1})^{d-1/2}\right).\]
\\

We can now state the main theorems, on convergence of spectral data for the diffusion maps approximations:

\begin{theorem}[Spectral convergence for standard weights]\label{t:EigendataStandard}

	Suppose $\rho \in \W{s},\, s > 3/2$.
	For all $\alpha \in [0,1]$ and $\lambda_* > 0$ there exist constants $\check {{C}}_{3}, \check {{C}}_{4}, \check {{C}}_{5}$ such that if $\eps+  \eps^{-1} \delta < \check {{C}}_{3}$, then for $-\lambda_{k,\alpha} \geq -\lambda_*$ we have
	\begin{enumerate}[(a)]
		\item Convergence of eigenvalues of $\check\P_{\eps,\alpha}$ and $\check\P^M_{\eps,\alpha}$:
		\begin{align*} | \check\lambda_{k,\eps,\alpha} - \check\lambda_{k,\alpha} | &\leq \check {{C}}_{4} \eps \\
		| \check\lambda_{k,\eps,\alpha}^M - \check\lambda_{k,\alpha}| &\leq \check {{C}}_{4} (\eps + \eps^{-1} \delta).
		\end{align*}
		\item Sup-norm convergence of the respective eigenspaces:
		\begin{align*} d_{C^0}(\check{\bar E}_{k,\eps,\alpha}, \check E_{k,\alpha}) &\leq \check {{C}}_{5} \eps \\
		d_{C^0}(\check{\bar E}_{k,\eps,\alpha}^M, \check E_{k,\alpha}) &\leq \check {{C}}_{5} (\eps + \eps^{-1} \delta).
		\end{align*}
	\end{enumerate}
\end{theorem}
(Recall that checked quantities $\check \lambda_{k,\alpha}$, etc. are defined analogously to their unchecked weights $\lambda_k$, etc. using standard rather than Sinkhorn normalisations.)
\begin{theorem}[Spectral convergence for Sinkhorn weights]\label{t:Eigendata}

	Suppose $\rho \in \W{s},\, s > 2$.
	For all $\lambda_* > 0$ there exist constants ${{C}}_{3}, {{C}}_{4}, {{C}}_{5}$ such that if $\eps^2 +  \eps^{-1} \delta < {{C}}_{3}$, then for $-\lambda_k \geq -\lambda_*$ we have
	\begin{enumerate}[(a)]
		\item Convergence of eigenvalues of $\P_{\eps}$ and $\P^M_{\eps}$:
		\begin{align*}
		| \lambda_{k,\eps} - \lambda_k | &\leq {{C}}_{4} \eps^2 \\
		| \lambda_{k,\eps}^M - \lambda_k| &\leq {{C}}_{4} (\eps^2 + \eps^{-1} \delta).
		\end{align*}
		\item Sup-norm convergence of the respective eigenspaces:
		\begin{align*}
		d_{C^0}(\bar E_{k,\eps}, E_k) &\leq {{C}}_{5} \eps^2 \\
		d_{C^0}(\bar E_{k,\eps}^M, E_k) &\leq {{C}}_{5} (\eps^2 + \eps^{-1} \delta).
 		\end{align*}
	\end{enumerate}
\end{theorem}

An empirical comparison of the bias errors for the standard and Sinkhorn normalisations on a $C^{2+\beta}$ sampling distribution is given in Figure \ref{fig:biaserror}, demonstrating the optimality of the bias error bounds, and the better convergence of the Sinkhorn normalisation for $\alpha = \half$.

The empirical behaviour of variance errors for a three-dimensional example is given in Figure \ref{fig:varianceerror}. Here the variance error in the spectral data appears to have the central limit theorem convergence in the sample size $M$ that we have shown. However, this convergence occurs in the regime $\Meff = M \eps^{d/2} \gg 1$, i.e.~up to log terms that $\delta \ll 1$: this regime is larger than that covered by our results, $\eps^{-1} \delta \ll 1$. Furthermore, the dependence on the timestep $\eps$ appears to be more gentle than our results would suggest: as $\eps$ is decreased with $\Meff$ fixed, the variance error in fact appears to decrease rather than increasing as $\bigO(\eps^{-1})$. This is in accordance with previous observations that spectral estimates have better convergence than the pointwise estimates that our results match up to \citep{Trillos19, Calder19}.
\\

\begin{figure}
	\centering
	\includegraphics[width=0.6\linewidth]{Fig-BiasError}
	\caption{Bias error in eigenvalues for $C^{2.2^-}$ function density $\rho(x) = 1 + \tfrac{1-3^{-2.2}}{2} \sum_{j=1}^\infty 3^{-2.2j} \cos (3^j\cdot 2\pi x)$ on $\domain = \mathbb{R}/\mathbb{Z}$ using a Sinkhorn normalisation (solid lines) and $\alpha = \half$ standard normalisation (dashed lines). A Fourier operator discretisation with $2001$ modes was used to compute the spectrum of the generator $\calL$ and discrete-time approximations $\P_\eps, \check \P_{\eps,1/2}$.}
	\label{fig:biaserror}
\end{figure}

\begin{figure}
	\centering
	\includegraphics[width=0.6\linewidth]{Fig-VarianceError2a}
		\includegraphics[width=0.6\linewidth]{Fig-VarianceError2b}
	\caption[Error in variance estimates]{$L^2(\rho^M)$ error in diffusion maps estimates of eigenspace $E_1$ for function density $\rho(x,y,z) \propto e^{\cos 4\pi x + f(y)+f(z)}$ where $f(x) = 0.4 \cos 2 \pi x+ 0.12 \sin 4 \pi x$ on $\domain = (\mathbb{R}/\mathbb{Z})^3$.

	Sinkhorn normalisation (solid lines) and $\alpha = \half$ standard normalisation (dashed lines) are compared. At top, the variance error plotted against local sample size $\Meff$ for different $\eps$; at bottom the combined bias and variance error are plotted against timestep $\eps$ for different sample sizes $M$.

	Expectations were computed using $30$ samples each. An adaptive Fourier discretisation \citep{ApproxFun} was used to approximate the eigenfunctions of the generator $\calL$ and of the continuum semigroup approximations $\P_\eps, \check \P_{\eps,1/2}$.}
	\label{fig:varianceerror}
\end{figure}

Rather than the semigroup, one is often interested in approximating the Laplace-Beltrami operator $\calL$ itself via the (possibly weighted) graph Laplacian $\eps^{-1}(\Pm -I)$: as an operator, we are thus interested in
\[ \calL^{(M)}_\eps := \eps^{-1}(\P^{(M)}_\eps-I),\]

and similarly for the standard weights. The eigenfunctions of these operators are the same as that of the respective $\P^{(M)}_\eps$, thus with the same convergence. On the other hand, if we let the eigenvalues of the generator $\calL^{(M)}_\eps$ be
\begin{equation} -\tilde \lambda_{k,\eps}^{(M)} = \eps^{-1}(e^{-\lambda_{k,\eps}^{(M)}}-1), \label{eq:GraphLaplacianEigenvalues}\end{equation}
and similarly for standard weights
\begin{equation} -\check{\tilde \lambda}_{k,\alpha,\eps}^{(M)} = \eps^{-1}(e^{-\check{\lambda}_{k,\alpha,\eps}^{(M)}}-1), \label{eq:GraphLaplacianEigenvaluesStandard}\end{equation}
 then we also have convergence of eigenvalues.
\begin{corollary}[Eigendata of the graph Laplacian]\label{c:GraphLaplacian}
	For all $\alpha \in [0,1]$ and $\lambda_* > 0$ there exist constants ${{C}}_{3}, {{C}}_{6}, \check {{C}}_{3}, \check {{C}}_{6}$ such that
	\begin{enumerate}[(a)]
		\item The eigenspaces of the graph Laplacians $\calL^{(M)}_\eps$ are those of the respective semigroup approximations $\P^{(M)}_\eps$ given in Theorems \ref{t:EigendataStandard} and \ref{t:Eigendata}.
		\item If $\rho \in C^{3/2+\beta}$ and $\eps +  \eps^{-1} \delta < \check {{C}}_{3}$, then for $-\check \lambda_{k,\alpha} \geq -\lambda_*$ we have convergence of eigenvalues for the standard weights
			 \begin{align*} | \tilde{\check \lambda}_{k,\eps,\alpha} - \check \lambda_{k,\alpha} | &\leq \check {{C}}_{6} \eps, \\
			 | \tilde{\check \lambda}_{k,\eps,\alpha}^{M} - \check  \lambda_{k,\alpha}| &\leq \check {{C}}_{6} (\eps + \eps^{-1} \delta).
			 \end{align*}
 		\item  If $\rho \in C^{2+\beta}$ and $\eps^2 +  \eps^{-1} \delta < {{C}}_{3}$, then for $-\lambda_k \geq -\lambda_*$ we have convergence of eigenvalues for the Sinkhorn weights
			 \begin{align*} | \tilde \lambda_{k,\eps} - \lambda_k | &\leq {{C}}_{6} \eps, \\
			 | \tilde \lambda_{k,\eps}^{M} - \lambda_k| &\leq {{C}}_{6} (\eps + \eps^{-1} \delta).
			 \end{align*}
	 \end{enumerate}
\end{corollary}
Note however that for purely linear-algebraic reasons the improvement in the bias error to $\bigO(\eps^2)$ for Sinkhorn weights is lost.
\\

Our proof of the main results rely on bounds of the deviations of (powers of) our discretised half-step operators $\J^{(M)}_\eps, \K^{(M)}_\eps$ from their respective limits.

Thus for the Sinkhorn weights, the bias error is bounded according to the following theorem:
\begin{theorem}\label{t:DeterministicOperator}
	Suppose $\rho \in \W{s},\, s > 2$, and let $S_\eps(t_1,t_0)$ be the solution operator of the PDE
	\begin{equation} \partial_t \phi^t = \calL \phi^t + \nabla \hat w^t_\eps \cdot \nabla \phi^t, \label{eq:SDMPDE}\end{equation}

	where we define $\hat w^t_\eps := \log (\D_t U_\eps) - \half \log \rho$ for $t \in [0,\eps)$ and extend $\eps$-periodically.

	Then
	\begin{align*}
	 	\J_\eps &= S_\eps(\eps,\half\eps)\\
		\K_\eps &= S_\eps(\half\eps,0)\\
		\P_\eps &= S_\eps(\eps,0)\\
		\M_{\eps,n} &= S_\eps((n+\half)\eps,\half\eps).
	\end{align*}
	Furthermore, for all $T>0$ and $\beta \in (0,\min\{s-2,1\})$ there exists a constant ${{C}}_{7,T,\beta}$ such that for all $0 \leq t_1-t_0 \leq T$ and $\eps \leq \eps_0$,
	\begin{align} \|S_\eps(t_1,t_0) - e^{(t_1-t_0) \calL}\|_{C^{3+\beta}\to C^0} \leq {{C}}_{7,T,\beta} \eps^2. \label{eq:GeneratorBound} \end{align}
\end{theorem}

If the sampling density $\rho$ has higher regularity, we have the stronger result, which follows from a simplification of the proof of Theorem \ref{t:DeterministicOperator} and implies an $\bigO(\eps^2)$ pointwise bias error of the Sinkhorn-weighted graph Laplacian:
\begin{proposition}\label{p:DeterministicOperatorS4}
	Suppose $\rho \in \W{s}$ for $s >4$. Then for all $\beta \in (0,1)$ there exists a constant ${{C}}_{8,\beta}$ such that for all $t \in \mathbb{R}$, $\eps \leq \eps_0$,
	\[\| S_\eps(t+\eps,t) - e^{\eps \calL}\|_{C^{3+\beta} \to C^0} \leq {{C}}_{8,\beta}\eps^3. \]
\end{proposition}

This is the best possible asymptotic rate of convergence to the semigroup for operators of the form $V_\eps \D_{\eps} U_\eps$ for all non-uniform distributions $\rho$ (see Remark \ref{r:SinkhornIsBest}).

Bounds on the variance error proceed from Theorem \ref{t:Delta}. In particular, we have the following result on the convergence of the operator $\D^M_\eps$ (an interpolation of the kernel matrix $\Km$) to its continuum limit:
\begin{theorem}\label{t:Operator}
Let $\zeta = Z_0 \eps^{1/2}$. Then
\[ \left\| \D^M_\eps - \D_\eps \right\|_{H^\infty(\domain_\zeta)} \leq e^{2 d Z_0^2} \delta. \]
\end{theorem}
Note here that the imaginary-direction thickness $\zeta$ of the domain of the Hardy space $H^\infty(\domain_\zeta)$ scales proportionally with the $\bigO(\eps^{1/2})$ bandwidth of the kernel. A useful consequence of this is that it is also possible to bound the error of the $k$th derivative of the spatial discretisation, with a penalty in the error of $\bigO(\eps^{-k/2})$.

As a consequence of Theorem \ref{t:Operator}, we also have operator convergence of the normalised operator $\P^M_\eps$, which interpolates the matrix $\Pm$, as well as the various auxiliary operators:
\begin{theorem}\label{t:WeightedOperatorConvergence}
	There exist constants $Z_0, {{C}}_{9}, {{C}}_{10}$ such that if $\zeta = Z_0 \eps^{1/2}$ and $\delta \leq {{C}}_{9}$
	then for all $\eps \leq \eps_0$ and $n \in \mathbb{N}$,
	\[ \| \P^M_\eps - \P_\eps \|_\zeta,\, \| \J^M_\eps - \J_\eps \|_{0\to\zeta},\, \| \K^M_\eps - \K_\eps \|_{\zeta\to 0} \leq {{C}}_{10}\delta, \]
	and
	\[ \| \M^M_{\eps,n} - \M_{\eps,n} \|_{0} \leq {{C}}_{10} \delta n. \]
\end{theorem}

config: arxiv


TITLE: Coloring edges of $K_n$ so each vertex has $l$ edges of each color.
QUESTION [0 upvotes]: Given $n$ for what values of $l$ can we color the edges so that each vertex $l$ edges of each color adjacent to it.
The number of colors used is clearly $\frac{n-1}{l}$
Thank you in advance.

REPLY [1 votes]: I found the answer a couple of hours after posting the question:
For starters we shall need an algorithm that in mexico we call the tortilla algorithm. It does the following: Given $n$ odd vertices place them as if they where the vertices of a convex $n$-gon and give a different color to each of the edges. color a  diagonal color in the color of the side that is paralel to the diagonal. This way every vertex will have exactly one edge of each of the $n$ colors, except for the color of the edge oposite to it, it shall have zero edges of this color. To fix this we can add a new vertex and join it to all of the old ones, the edge going from this new vertex to a given old vertex is going to be colored with the color that the old vertex lacked before the addition of the new vertex.
With this algorithm we can paint the edges of a complete even graph $K_n$ with $n-1$ colors  so that each of its vertices has exactly one edge of each color. Now suppose we are given $k|n-1$. We can color the graph with $\frac{n-1}{k}$ colors so that each vertex has $k$ edges how? First use the previous algorithm to color it with $n-1$ colors and then partition the set of $n-1$ colors into $\frac{n-1}{k}$ sets of $k$ colors each. For each of those sets paint the edges that where in any of those colors with a new color, so that the graph now has $\frac{n-1}{k}$ different colors. Clearly this coloring satisfies the requirement since a given vertex had exactly one edge o each of the new colors. But in the new coloring what where before $k$ colors are now one. So for any given new color there are exactly $k$ edges of that color adjacent to any particular vertex. So when the graph is even $k$ can be any divisor of $n-1$.
If $n=2m+1$ is odd we first prove when $k=2$ we can do it: Place the vertices as if they where the vertices of a regular $n$-gon and label the colors $0,1,2,3\dots m-1$. For any given diagonal of the n-gon consider the two sides in which the n-gon is divided. Then consider the side which has less points, we color the diagonal with the color that corresponds to the number of points left in that side, so for example the sides are colored with color zero. It is easy to see when we do this every vertex has two edges of each color since the two diagonals of color $s$ oming out of edge $v$ can be found by going around the vertex starting from $v$ and counting $s+1$ vertices (there are two because we can go clock or counter-clock wise). Using a method similar to the even case we can use this to prove we can always do it if $k$ is a multiple of $2$.
We now prove if $n$ is odd and $k$ is odd we cannot do it by contradiction. Suppose it is possible, pick one of the colors. Then the graph which has only edges of that color has an odd amount of vertices odd degree, a contradiction.
Thus the answer is as Casteels said, if $n$ is even any divisor of $n-1$ works and if $n$ is odd any even divisor of $n-1$ works, and these are the only values for which it works.


TITLE: Necessary and sufficient condition for quadratic forms
QUESTION [0 upvotes]: Consider the quadratic form $Q(u,v)=au^2 + 2buv +cv^2$. Upon completing the square we will obtain $$Q(u,v)=a\left(u+\frac{bv}{a}\right)^2+\left(c-\frac{b^2}{a}\right)v^2,$$
we assume that $a\ne 0$.
There is a theorem which says that

A set of necessary and sufficient conditions that $Q(u,v)$ be positive for all nontrivial $u$ and $v$ is that
  $$a>0, \text{ } \left|\begin{matrix}
a & b\\
b & c
\end{matrix}\right|>0$$

However, what if $a>0$ but $\left(c-\frac{b^2}{a}\right)<0$? Then either $c$ is negative or $c<\frac{b^2}{a}$. Why wouldn't this satisfy $Q(u,v)$ as being positive?
This is also equivalent to
$$ac-b^2>0 \text{ (1)}$$
$$ac-b^2<0 \text{ (2)}$$
with (1) implying that $c>0$ whenever $a>0$ but $ac$ can also be positive when $a<0$ and $c<0$ and $ac>b^2$. Likewise, (2) can also be negative when $a,c>0$ and $ac<b^2$.
What is it that I'm missing here?

REPLY [1 votes]: when $a > 0$ but $c - \frac {b^2}{a} < 0,$ test with pair
$$  u = -b, \; \; v = a .  $$
Then
$$ a u^2 + 2 b u v + c v^2 = a b^2 - 2 b b a + c a^2 = ca^2 - a b^2 = a(ca-b^2) < 0 $$


TITLE: proof $f(\overline{A})\subseteq \overline{f(A)} \Leftrightarrow f$ continuous
QUESTION [1 upvotes]: It'd be great if someone checked the proof I did for the following problem:
$f:X\longrightarrow Y$,
$f(\overline{A})\subseteq \overline{f(A)},\forall A\subseteq X \Leftrightarrow f$ continuous
proof:
Suppose $f(\overline{A})\subseteq \overline{f(A)}$ for any $A\subseteq X$ .
Let $C\subseteq Y$ be closed and define $A=f^{-1}(C)$.
$f(\overline{A})\subseteq \overline{f(A)}\subseteq\overline{C}=C$, therefore $\overline{A}\subseteq f^{-1}(C)=A$,  so $A$ is closed.
*Conversely, suppose $f$ is continuous.
Let $p\in\overline{A}$ and let $V$ be an open neighborhood of $f(p)$. Since $f$ is continuous,  $f^{-1}(V)$ is open. On the other hand $p\in f^{-1}(V)$, but since $p\in\overline{A}$ we have that $f^{-1}(V)$ contains points of  $A$. Therefore $V$ contains points of $f(A)$. Since $V$ is an arbitrary neighborhood of $f(p)$, we have $f(p)\in \overline{f(A)}$. So finally, $f(\overline{A})\subseteq\overline{f(A)}$.
Thank you very much!

REPLY [0 votes]: I found this proof very awkward when I first came across it so for everyone else like me I'm going to explain everything slowly. $$$$
 "$\Rightarrow$" let $f:X->Y$ be continuous $\Rightarrow\forall F\subset Y $ such that $y$ is closed in $Y$ $f^{-1} (F)$ is closed in X. Pick any $A\in X$. It is "obvious" $f(A)= f(A) \Rightarrow f(A)\subset\overline {f(A)}$ hence $A\subset f^{-1}\left( \overline {f(A)}\right)$ $ \Rightarrow \bar A\subset \overline{ f^{-1}\left( \overline {f(A)}\right)}$. Here it is important to note that $\overline{f(A)}$ is closed in Y hence it's inverse image is closed in X. Thus$\overline{ f^{-1}\left( \overline {f(A)}\right)}= f^{-1}\left( \overline {f(A)}\right)$ hence subbing this back into the original formula we see that $\bar A \subset f^{-1}\left( \overline {f(A)}\right)$ and the result follows. $$$$ "$\Leftarrow$" Now suppose $f(\bar A)\subset \overline {f(A)}$  pick any $C_Y\subset Y$ such that $C_Y$ is closed in Y. Let $A=f^{-1}(C_Y)$, $f(\bar A)\subset \overline{f(A)}\subset \overline{C_Y}\subset C_Y$. Taking the first and last parts of that working gives: $f(\bar A) \subset C_Y$. Finally, taking inverse images gives $\bar A \subset f^{-1}(C_Y)$ using our definition at the start we see $\bar A\subset A$. This show us $A$ is closed and hence the pre-image of a closed set is closed and thus our function is continuous.


TITLE: Rotation matrix formula derivation?
QUESTION [0 upvotes]: I would like to understand where to following formula for a 2-D rotation matrix is derived from:
$R =\frac{1}{a^2+b^2} \left(\begin{array}{cc} a^2-b^2 & 2ab\\ -2ab & a^2-b^2 \end{array}\right)$
I believe the answer is geometric and if it is, a picture would be nice.

REPLY [1 votes]: Consider the unit vector
$$\vec u=\left(\frac a{\sqrt{a^2+b^2}},\frac b{\sqrt{a^2+b^2}}\right).$$
The rotation that applies $(1,0)$ to $\vec u$ and $(0,1)$ to a unit vector orthogonal to $\vec u$ is described by the matrix
$$R=\frac1{\sqrt{a^2+b^2}}\begin{bmatrix}a&b\\-b&a\end{bmatrix}.$$
Applying the rotation twice, i.e. squaring the matrix gives
$$R^2=\frac1{a^2+b^2}\begin{bmatrix}a^2-b^2&2ab\\-2ab&a^2-b^2\end{bmatrix}.$$


TITLE: Two solutions, A+ and A-, for masses connected via springs
QUESTION [3 upvotes]: My prof gives an example of trying to solve the equations of motion for a series of gliders each connected by springs, with the same spring constant. From looking at the $j-1$ through $j+1$ glider, he got the following:
\begin{equation}mx^{\prime\prime}_j = \omega_0^2 (x_{j+1} - 2x_j + x_{j-1}).\end{equation} This I understand.
Solving $x'' = \omega_0 ^2 (A_{j+1} -2A_j + A_{j-1})$ using $x=A_je^{-\imath \omega t}$ gives the solution \begin{equation}\left[2-\left(\frac{\omega}{\omega_0}\right)^2\right]A_j = A_{j+1} + A_{j-1}.\end{equation} I can follow this step.
Why does this mean it has solutions, $A_j = A_+ e^{\imath\, \theta j}$ and $A_- e^{-\imath\,\theta j}$? This is what my lecture notes say.
I thought $A_+$ might be $A_{j+1}$ divided by $\left[2-\left(\frac{\omega}{\omega_0}\right)^2\right]$, but then why did the exponent on the $e$ change?

REPLY [1 votes]: Basically this is just the solution to the recurrence formula, look here.  They show how to solve recurrence relation using difference equation.


TITLE: Help with differential equation of unknown order
QUESTION [1 upvotes]: I was working with a problem and this differential equation came up.
$$1+\frac {dx}{x}=e^{mx \, dy}$$
I don't think this has any closed form solution. Can anyone solve this if possible?

REPLY [0 votes]: $\because dy$ is a very small change in $y$ so we consider $mxdy$ as negligible. And we know that when $x$ is too small then $e^x$ can be written as $(1+x)$ .So in above differential equation, $e^{mxdy}$ can  be written as $(1+mxdy)$ and the solution for given problem is as follows-
$1+\frac{dx}{x}=e^{mxdy}$
$\Rightarrow1+\frac{dx}{x}=1+mxdy$
$\Rightarrow\frac{dy}{dx}=\frac{1}
{mx^2}$
$\Rightarrow y=-\frac{1}{mx}+c$