text:
\begin{document}

\title[Isomorphisms of Higman-Thompson groups]{The Isomorphism Problem for Higman-Thompson groups}
\author{Enrique Pardo}
\address{Departamento de Matem\'aticas, Facultad de Ciencias\\ Universidad de C\'adiz, Campus de
Puerto Real\\ 11510 Puerto Real (C\'adiz)\\ Spain.}
\email{enrique.pardo@uca.es}\urladdr{https://sites.google.com/a/gm.uca.es/enrique-pardo-s-home-page/}
\thanks{The author was partially supported by the DGI and European Regional Development Fund, jointly, through Project MTM2008-06201-C02-02, by the Consolider Ingenio ``Mathematica" project CSD2006-32 of the MEC, by PAI III grants FQM-298 and P07-FQM-02467 of the Junta de Andaluc\'{\i}a and by 2009 SGR 1389 grant of the Comissionat per Universitats i Recerca de la Generalitat de Catalunya.} \subjclass[2010]{Primary 20E32; Secondary
20E36, 20F05, 16D70} \keywords{Higman-Thompson group, Leavitt algebra, Isomorphism.}
\date{\today}
\dedicatory{To Anna}

\begin{abstract}
We prove that the Higman-Thompson groups $G_{n,r}^+$ and $G_{m,s}^+$ are isomorphic if and only if $m=n$ and $\mbox{gcd}(n-1,r)=\mbox{gcd}(n-1,s)$.
\end{abstract}

\maketitle

\section*{Introduction}

Finitely presented groups are one of the most important classes of infinite groups, both by its ubiquity (e.g. they are fundamental groups of compact manifolds) and by the number of interesting subclasses it contains (hyperbolic groups and automatic groups, among others). Also they have interest in connection with algorithmic properties, as showed by Higman \cite{HigmanRec}, who stated that a finitely generated group is embeddable in a finitely presented group if and only if is recursively presented. As simple groups are one of the milestones in the development of Group Theory, a fundamental topic in the study of groups is that of finitely presented simple groups.

The study of finitely presented simple groups began with Thompson's discovering in 1965 of the firsts two infinite examples in this class \cite{Thompson}, now known as $G_{2,1}$ and $T_{2,1}$. In 1974 Higman \cite{Higman} constructed a countably infinite family of finitely presented simple groups generalizing Thompson's group $G_{2,1}$. These are the commutator subgroups $G_{n,r}^+$ of the groups $G_{n,r}$ introduced in the same paper. There are various ways of describing these groups: automorphism groups of $r$-generated free algebras in the variety of algebras of sets that are in bijection with its own $n$-th direct power \cite{Higman}, groups of piecewise linear homeomorphisms of the unit interval with prescribed slopes and limited sets of non-differenciable points \cite{Stein}, groups of tree diagrams of finite $n$-ary $r$-forests \cite{CFP}, or groups of maximal inescapable (cofinite) isomorphisms \cite{Scott}.

Unfortunately, these groups are still not fully understood. For example, the isomorphism problem is not completely solved in this class, even if Higman \cite{Higman} highlighted a great part of it. Higman showed that showed that this family contains infinitely many isomorphism types.  Also he showed that $G_{n,r}^+\cong G_{m,s}^+$ implies that $m=n$ and $\mbox{gcd}(r,n-1)=\mbox{gcd}(s,n-1)$ \cite[Theorem 6.4]{Higman}, while the converse is known only for some particular cases (e.g. when $r\equiv s$ (mod $n-1$) \cite[Section 3]{Higman}, or when $s=rc$ with $c$ a divisor of $n$ \cite[Theorem 7.3]{Higman}).

In this paper we prove that the converse of \cite[Theorem 6.4]{Higman} holds: $G_{n,r}^+$ and $G_{m,s}^+$ are isomorphic if and only if $m=n$ and $\mbox{gcd}(n-1,r)=\mbox{gcd}(n-1,s)$. Hence, we close the isomorphism problem for this class. The key point for proving this result relies in the connection of this problem with a longstanding problem about isomorphisms of finitely presented algebras stated by Leavitt \cite{L1,L2}, and recently solved by Abrams, \'Anh and the author \cite{AbAnhP}.

Now we summarize the contents of this paper. In Section 1 we recall the definition of $G_{n,r}$ following the lines of \cite{Scott}, and we list some properties enjoyed by these groups. In Section 2 we recall the definition of Leavitt algebras, and we quote  \cite[Theorem 4.14]{AbAnhP}:
\begin{quotation}
Let $d,n$ be positive integers, and $K$ any field.  Let $L_{K,n} = L_n$ denote the Leavitt algebra of type $(1,n-1)$
with coefficients in $K$. Then $L_n\cong M_d(L_n)$ if and only if $\mbox{gcd}(d,n-1)=1$.
\end{quotation}
Since the isomorphism is explicitly given in terms of the generators of the algebra, we use it in Section 3, where we relate $G_{n,r}$ with a group of invertible matrices in $M_r(L_n)$, and as a byproduct we give a proof of the converse of \cite[Theorem 6.4]{Higman}.

\section{Basics on Higman-Thompson groups}

We will fix the essential definitions and results about Higman-Thompson groups that we will need in the sequel. Our sources are \cite{CFP, Higman, Rover, Scott}.

Let $n, r \in \N$, $n\geq 2$ and $r\geq 1$, let $\mathcal{A}_n=\{ a_1, \dots ,a_n\}$ be an alphabet (through the rest of the paper we will assume $\mathcal{A}_n=\{ 1, \dots ,n\}$  by defect), let $X_r=\{ x_1, \dots ,x_r\}$ a set of $r$ elements disjoint of $\mathcal{A}_n$, and let $W_n$ be the free monoid generated by $\mathcal{A}_n$ and the empty word. Denote by $X_rW_n$ the set of finite words of the form $x_i\alpha$, where $\alpha\in W_n$.

Given $u,v\in X_rW_n$, we will denote $u\leq v$ if there exists $\alpha \in W_n$ such that $v=u\alpha$; notice that $\leq$ is a partial order, and so $u<v$ means $u\leq v$ and $u\ne v$ with no ambiguity. We will say that a subset $B$ of $X_rW_n$ is independent if its elements are pairwise $\leq$-incomparable.

A nonempty subset $V$ of $X_rW_n$ is said to be a subspace if it is closed under right multiplication by elements of $W_n$. A subset $B$ of a subspace $V$ is a basis if it is independent and $V=BW_n$; a subset $B$ of $X_rW_n$ is a basis if there exists a subspace $V$ for which $B$ is a basis. Notice that the set $B_V=\{ y\in V\mid \mbox{ no proper initial segment of  }y \mbox{ belongs to } V\}$ is a basis for $V$, so that every subspace has a basis. In particular, $X_r$ is a basis for $X_rW_n$.

A subspace $V$ is cofinite if $\vert X_rW_n\setminus V\vert<\infty$. A basis $B$ is cofinite if $V=BW_n$ is a cofinite subspace. Notice that then $V$ is cofinite if it has a maximal finite basis. In particular, any finite basis is contained in a cofinite basis. Also it is clear that any finite intersection of cofinite subspaces is a cofinite subspace (this is \cite[Corollary 1 to Lemma 2.4]{Higman} stated in a different language).

If $u$ is an element of $X_rW_n$, we will say that $\{ua_1, \dots ,ua_n\}$ is a simple expansion of $u$. Given a basis $B$ and $u\in B$ any element, $B'=(B\setminus \{ u\})\cup \{ua_1, \dots ,ua_n\}$ is again a basis, that we call a simple expansion of $B$. Given $B,C$ basis, we say that $C$ is an expansion of $B$ if there is a finite chain $B_0, \dots ,B_k$ of basis such that $B_0=B$, $B_k=C$ and $B_{i+1}$ is a simple expansion of  $B_i$ for every $0\leq i\leq k-1$. Of course, any expansion of a cofinite basis is a cofinite basis as well.

An homomorphism $\theta$ between subspaces of $X_rW_n$ is a map satisfying $(uw)\theta=(u\theta)w$ for all $w\in W_n$, whenever $u\theta$ is defined. An isomorphism is a bijective homomorphism, and if the domain and the range of an isomorphism is cofinite, we say that it is a cofinite isomorphism. An extension of a cofinite isomorphism $\theta$ is a cofinite isomorphism $\theta'$ such that $u\theta'=u\theta$, whenever $u\theta$ is defined. A cofinite isomorphism is maximal if it has no nontrivial extensions.

Now, we quote two fundamental facts:

\begin{lem}\label{L:Scott1} {\rm (c.f. \cite[Lemma 1]{Scott})} Every cofinal isomorphism $\theta$ has a unique maximal extension $\theta^*$.
\end{lem}

Let $\phi_i: U_i\rightarrow V_i$ be cofinite isomorphisms for $i=\{ 1,2\}$. Now fix $S=V_1\cap U_2$, $R=S\phi_1^{-1}$, $T=S\phi_2$, which are cofinite subspaces, and notice that $({\phi_1}_{\vert R})\circ ({\phi_2}_{\vert S})$ is a cofinal isomorphism from $R$ to $S$. So, we define $\phi_1\phi_2:=(({\phi_1}_{\vert R})\circ ({\phi_2}_{\vert S}))^*$. With this definition we have

\begin{lem}\label{L:Scott2} {\rm (c.f. \cite[Lemma 2]{Scott})} The set of maximal cofinite isomorphisms is a group under the above defined operation.
\end{lem}

The group defined in Lemma \ref{L:Scott2} is the Higman-Thompson group $G_{n,r}$ defined originally in \cite{Higman}. We introduce a the representation of the elements of $G_{n,r}$ which turns out to be a useful instrument to deal with the group.

Whenever $B=\{ y_1, \dots ,y_N\}$ and  $C=\{ z_1, \dots ,z_N\}$ are expansions of $X_r$ (and thus cofinite basis), the bijection
$$
\begin{array}{cccc}
 \theta &B  & \rightarrow  & C  \\
 & y_i & \mapsto  & z_i
\end{array}
$$
extends naturally to a cofinite isomorphism $\theta: BW_n\rightarrow CW_n$, so that $\theta \in G_{n,r}$. Thus, we can represent $\theta$ by the symbol
$$\theta =\left(
\begin{array}{ccc}
 y_1 & \dots  & y_N  \\
 z_1 & \dots  & z_N
\end{array}
\right).
$$
Conversely, every element $\theta\in G_{n,r}$ admits such a representation \cite[Lemma 4.1]{Higman}.

Whenever
$$\varphi =\left(
\begin{array}{ccc}
 x_1 & \dots  & x_M  \\
 t_1 & \dots  & t_M
\end{array}
\right)
$$
is a symbol for any other element in $G_{n,r}$, \cite[Corollary 1 to Lemma 2.4]{Higman} guarantees that there exists a common expansion $\{ s_1 , \dots  ,s_P\} $ of $\{ z_1 , \dots  ,z_N\} $ and $\{ x_1 , \dots  , x_M\} $ so that
$$\theta =\left(
\begin{array}{ccc}
 y'_1 & \dots  & y'_P  \\
 s_1 & \dots  & s_P
\end{array}
\right)
\mbox{ and }
\varphi =\left(
\begin{array}{ccc}
 s_1 & \dots  & s_P  \\
 t'_1 & \dots  & t'_P
\end{array}
\right)
$$
and thus
$$\theta \varphi=\left(
\begin{array}{ccc}
 y'_1 & \dots  & y'_P  \\
  t'_1 & \dots  & t'_P
\end{array}
\right).
$$

A relevant subgroup of $G_{n,r}$ is the commutator subgroup, usually denoted by $G_{n,r}^+$. At it was shown in \cite{Higman} (c.f. \cite[Lemma 2.1]{Rover}), the index of $G_{n,r}^+$ in $G_{n,r}$ is $\mbox{gcd}(n-1, 2)$, so that $G_{n,r}^+$ coincides with $G_{n,r}$ whenever $n$ is even. For the sake of uniform notation (c.f. \cite[Section 5]{Higman}), we write $G_{n,r}^+=G_{n,r}$ when $n$ is even.

For any $n\geq 2, r\geq 1$, some interesting features enjoyed by these groups are the following:
\begin{enumerate}
\item The group $G_{n,r}$ is finitely presented \cite[Theorem 4.6]{Higman}.
\item The group $G_{n,r}^+$ is simple \cite[Theorem 5.4]{Higman}.
\item The group $G_{n,r}^+$ contains an isomorphic copy of every countable locally finite group \cite[Theorem 6.6]{Higman}.
\item The defining relations of the group $G_{n,r}$ are recursively enumerable, so that $G_{n,r}$ has soluble word problem, and thus conjugacy and order soluble problems \cite[Section 9]{Higman}.
\end{enumerate}

\section{Isomorphisms of Leavitt algebras}

We begin by defining the Leavitt algebras $L_{K}(1,n)$, which was investigated originally by Leavitt in his seminal paper \cite{L1}.
For any positive integer $n\geq 2$, and field $K$, we denote
$L_K(1,n)$ by $L_{K,n}$, and call it the Leavitt algebra of
type (1,n-1) with coefficients in $K$. (When $K$ is understood,
we denote this algebra simply by $L_n$).  Precisely, $L_{K,n}$ is
the quotient of the free associative $K$-algebra in $2n$
variables:
$$L_{K,n}=K<X_1,...,X_n,Y_1,...,Y_n>/T,$$
where $T$ is the ideal generated by the relations $ X_iY_j - \delta_{ij}1_K$ (for $1\leq i,j \leq n$) and
$\sum_{j=1}^{n} Y_jX_j - 1_K$. The images of $X_i,Y_i$ in $L_{K,n}$ are denoted respectively by $x_i,y_i$. In
particular, we have the equalities $x_iy_j = \delta_{ij}1_K$ and $\sum_{j=1}^{n} y_jx_j = 1_K$ in $L_n$. A multiindex will be a sequence $I=\{ i_1\dots, i_k\}$ with $i_j\in\{ 1, 2, \dots ,n\}$ for all $1\leq j\leq k$. We will then denote $y_I=y_{i_1}y_{i_2}\cdots y_{i_k}$ and $x_I=x_{i_k}x_{i_{k-1}}\cdots x_{i_1}$.

We now fix a fundamental property of $L_n$ that is basic for our purposes.

\begin{lem}\label{Basicprops}  {\rm (\cite[Theorem 8]{L1})} Let $K$ be any field, let $n\geq 2$ be a natural number. Then, $L_n$ has module type $(1,n-1)$.  In particular, if $r\equiv s$ (mod $n-1$) then $L_n^r \cong
L_n^s$ as free left $L_n$-modules.  Consequently, if $r\equiv s$ (mod $n-1$), then there is an isomorphism of matrix
rings $M_r(L_n)\cong M_s(L_n)$.
\end{lem}

\begin{rema}\label{R:special iso}
{\rm Suppose that $s=r+(n-1)$, and denote $\widehat{x}=(x_1,\dots ,x_n)$ and $\widehat{y}=(y_1, \dots ,y_n)$. Then, abovementioned isomorphism is given by the rule
$$
\begin{array}{cccc}
 \varphi: & M_r(L_n)  & \rightarrow  & M_s(L_n)  \\
 & A & \mapsto  &   \mbox{diag}(I_{r-1}, \widehat{x}^t)\cdot A\cdot \mbox{diag}(I_{r-1}, \widehat{y})
\end{array}.
$$
In particular, whenever the entries of $A$ has the form $\sum\limits_{i=1}^{k}y_{I_i}x_{J_i}$ (for $\{ I_i, J_i\}_{1\leq i\leq k}$ sets of multiindices), then so are the entries of $\varphi (A)$.
By recurrence on this argument, the same consequence holds for any pair of natural numbers $r,s$ such that  $r\equiv s$ (mod $n-1$). }
\end{rema}

\begin{defi}\label{involutiondef}  {\rm For any field $K$, the extension of the assignments $x_i \mapsto y_i=x_i^*$ and $y_i \mapsto x_i=y_i^*$
 for $1\leq i \leq n$ yields an involution $*$ on $L_K(1,n)$. This involution on $L_K(1,n)$ produces an involution
 on any sized matrix ring $M_m(L_K(1,n))$ over $L_K(1,n)$ by setting $X^* =
(x_{j,i}^*)$  for each $X=(x_{i,j})\in M_m(L_K(1,n))$. We note that if $K$ is a field with involution (which we also denote by $*$), then a second involution on $L_K(1,n)$
may be defined by extending the assignments $k\mapsto k^*$ for all $k\in K$,  $x_i \mapsto y_i=x_i^*$ and $y_i \mapsto
x_i=y_i^*$ for $1\leq i\leq n$. We will say that $X\in M_d(L_n)$ is a unitary provided that $XX^*=X^*X=I_d$, and we will denote by $U(M_d(L_n))$ the group of unitaries of $M_d(L_n)$.}
\end{defi}

Now, we will quote the essential result of this section

\begin{theor}\label{Th:IsoLeavitt} {\rm (\cite[Theorem 4.14]{AbAnhP})}
Let $d,n$ be positive integers, and $K$ any field.  Let $L_{K,n} = L_n$ denote the Leavitt algebra of type $(1,n-1)$
with coefficients in $K$. Then $L_n\cong M_d(L_n)$ if and only if $\mbox{gcd}(d,n-1)=1$.
\end{theor}

Let us fix the details needed to prove Theorem \ref{Th:IsoLeavitt}, in order to explain why it is so important in the proof of our main result. Essentially, we need to construct a $K$-algebra isomorphism
$$
\begin{array}{cccc}
 \varphi: &  L_n & \rightarrow & M_d(L_n)   \\
 & x_i & \mapsto  &   X_i\\
 & y_j & \mapsto  &   Y_j
\end{array}.
$$
Since $L_n$ is a simple algebra, it is enough to fix a set $\{ X_1, \dots, X_n,Y_1,\dots ,Y_n\}\subset M_d(L_n)$ satisfying the definitory relations of the generators of $L_n$, and generating $M_d(L_n)$. Now, we present the appropriate $2n$ matrices. For any unital ring $R$ and $i\in\{1,2,...,d\}$ we denote the
idempotent $e_{i,i}$  of the matrix ring $M_d(R)$ simply by
$e_i$. We write
$n=qd+r$ with $2\leq r \leq d$.  We assume $d<n$, so that $q\geq 1$. The matrices $X_1, X_2, ..., X_q$ are given as
follows. For $1\leq i \leq q$ we define
$$X_i=
\begin{pmatrix}x_{(i-1)d+1}&0& &0 \\
        x_{(i-1)d+2}&0& &0 \\
        \vdots&0&...&0 \\
        x_{id}&0& &0
        \end{pmatrix}
= \sum_{j=1}^{d}x_{(i-1)d+j}e_{j,1} $$ The two matrices $X_{q+1}$
and $X_{q+2}$ play a pivotal role here.  They are defined as
follows.
$$X_{q+1}=
\begin{pmatrix}x_{qd+1}&0&0& &0&0& &0& \\
        x_{qd+2}&0&0& &0&0& &0& \\
        \vdots&0&0& &0&0& &0& \\
        x_n&0&0&...&0&0&...&0&\\
        0&1&0& &0&0& &0& \\
        0&0&1& &0&0& &0& \\
        & & &\vdots& & & & & \\
        0&0&0& ...&1&0& &0& \end{pmatrix}$$
$$ = \sum_{i=1}^{d-r}e_{i+r,i+1} + \sum_{t=1}^{r}x_{qd+t}e_{t,1}$$
and
$$X_{q+2}=
\begin{pmatrix}0& &0&1&0&0& &0&0 \\
        0& &0&0&1&0& &0&0 \\
         & & & & &\vdots& & &\\
        0& &0&0&0&0& &1&0 \\
        0&...&0&0&0&0& &0&a_{q+2,r-1} \\
        0& &0&0&0&0& &0&a_{q+2,r} \\
         & & &\vdots& & & & &\vdots \\
        0& &0&0&0&0& &0&a_{q+2,d}\end{pmatrix}$$
$$ = \sum_{j=1}^{r-2}e_{j,j+s} + \sum_{t=1}^{d-(r-2)}a_{q+2,(r-2)+t}e_{(r-2)+t,d}$$
(where the elements $a_{q+2,r-1}, a_{q+2,r},..., a_{q+2,d} \in
L_n$ are monomials in $x$-variables).  In case $d-r=0$ or $r-2=0$ we interpret the appropriate
sums as zero.

The remaining matrices $X_{q+3},...,X_n$ will have the same general
form. In particular, for $q+3 \leq i \leq n$,
$$X_i=
\begin{pmatrix}0& &0&a_{i,1} \\
        0& &0&a_{i,2} \\
         0&...&\vdots&\\
        0& &0&a_{i,d}
        \end{pmatrix}
= \sum_{j=1}^{d}a_{i,j}e_{j,d} $$ (where the elements $a_{i,1},
a_{i,2}, ... ,a_{i,d} \in L_n$ are monomials in the $x$-variables).  In case $q+3 > n$ then we
understand that there are no matrices of this latter form in our
set of $2n$ matrices.  We note that we always have the matrices
$X_{q+1}$ and $X_{q+2}$, since $n=qd+r\geq q\cdot 1 + 2$. We define the matrices $Y_i$ for $1\leq i \leq n$ by setting $Y_i
= X_i^*$.

Now consider this set, which we will call ``The List":

$$x_1^{d-1}$$
$$x_2x_1^{d-2}, x_3x_1^{d-2}, ... , x_nx_1^{d-2}$$
$$x_2x_1^{d-3}, x_3x_1^{d-3}, ... , x_nx_1^{d-3}$$
$$\vdots$$
$$x_2x_1, x_3x_1, ... , x_nx_1$$
$$x_2, x_3, ... , x_n$$

The key of the proof of Theorem \ref{Th:IsoLeavitt} is that, whenever $\mbox{gcd}(d,n-1)=1$, there is a rule to assign an element in The List to each $a_{i,j}$ in the above set of matrices, in such a way that the resulting set $\{ X_1, \dots, X_n,Y_1,\dots ,Y_n\}$ satisfies the definitory relations of the generators of $L_n$, and generates $M_d(L_n)$. Thus, under such a choice, the above defined map $\varphi$ is a $K$-algebra isomorphism.

\begin{rema}\label{R:special iso2}
{\rm Because of the definition of the above mentioned isomorphism, it is clear that whenever $a\in L_n$ has the form $\sum\limits_{i=1}^{k}y_{I_i}x_{J_i}$ (for $\{ I_i, J_i\}_{1\leq i\leq k}$ sets of multiindices), then the entries of $\varphi (a)$ have the same form. }
\end{rema}

We will prove an easy consequence of Theorem \ref{Th:IsoLeavitt} that will be useful in the sequel. For, we quote the following fact

\begin{lem}\label{L:AbGroups} {\rm (\cite[Lemma 1]{AbSmith})} Let $G$ be a finitely generated abelian group (written additively). Let $x\in G$ be an element of finite order $n$, and let $c,d\in \N$. There exists an automorphism $\varphi: G\rightarrow G$ with $\varphi (cx)=dx$ if and only if $\mbox{gcd}(c,n)=\mbox{gcd}(d,n)$.
\end{lem}

\begin{corol}\label{Corol:IsoLeavitt}
Let $n, r, s$ be positive integers, and $K$ any field.  Let $L_{K,n} = L_n$ denote the Leavitt algebra of type $(1,n-1)$
with coefficients in $K$. If $\mbox{gcd}(r,n-1)=\mbox{gcd}(s,n-1)$, then $M_r(L_n)\cong M_s(L_n)$.
\end{corol}
\begin{proof}
By Lemma \ref{L:AbGroups}, applied to $G=\Z/(n-1)\Z$, $x=[1]\in \Z/(n-1)\Z$, $c=r$ and $d=s$, there exists a group automorphism $\varphi: \Z/(n-1)\Z\rightarrow \Z/(n-1)\Z$ such that $\varphi ([r])=[s]$. Thus, there exists $l\in \N$ with $\mbox{gcd}(l,n-1)=1$ such that $[lr]=[s]$. Since $lr\equiv s$ (mod $n-1$), we have $M_s(L_n)\cong M_r(M_l(L_n))$ by Lemma \ref{Basicprops}. Now, $L_n\cong M_l(L_n)$ by Theorem \ref{Th:IsoLeavitt}, so that $M_r(M_l(L_n))\cong M_r(L_n)$, which completes the proof.
\end{proof}

\begin{rema}\label{R:special iso3}
{\rm Because of Remarks \ref{R:special iso} and \ref{R:special iso2}, the isomorphism given by Corollary \ref{Corol:IsoLeavitt} has the property that, whenever the entries of $A$ has the form $\sum\limits_{i=1}^{k}y_{I_i}x_{J_i}$ (for $\{ I_i, J_i\}_{1\leq i\leq k}$ sets of multiindices), then so are the entries of $\varphi (A)$. This fact play a role in the proof of the main result of this paper.}
\end{rema}

\section{The main result}

In this section, we will prove the main result of the paper.

\begin{defi}\label{D:grupunitaris}
{\rm Let $n\geq 2, r\geq 1$ be natural numbers. We denote by $\mathcal{P}_{n,r}$ the subset of the group $U(M_r(L_n))$ of unitaries of $M_r(L_n)$ composed by matrices in which all the entries are either $0$ or have the form
$$\sum\limits_{i=1}^{m}y_{I_i}x_{J_i},$$
where the $I_i, J_i$ are multiindices.}
\end{defi}

\begin{lem}\label{L:grupunitaris}
For any $n\geq 2, r\geq 1$ natural numbers, $\mathcal{P}_{n,r}$ is a subgroup of $U(M_r(L_n))$.
\end{lem}
\begin{proof}
Since $1=\sum\limits_{i=1}^{n}y_ix_i$, it is clear that the identity matrix $I_r$ belongs to $\mathcal{P}_{n,r}$, whence it is a nonempty set.

Fix $X,Y\in \mathcal{P}_{n,r}$ two elements. Since $Y$ is an unitary, $Y^{-1}$ is the conjugated transpose of $Y$ (so it lies in $\mathcal{P}_{n,r}$ too), and hence the entries in $XY^{-1}$ are of the form $\sum\limits_{k=1}^{r}a_{i,k}b_{k,j}$, where
$$a_{i,k}b_{k,j}=\left( \sum\limits_{i=1}^{m}y_{I_i}x_{J_i}\right)\cdot \left( \sum\limits_{i=1}^{m'}y_{I'_i}x_{J'_i}\right).$$
As
$$(\ast )\hspace{.2truecm} x_{J_r}y_{I'_s}=\left\{\begin{array}{lll}  y_{\widehat{I}_s} & \mbox{if} &
I'_s=J_r\widehat{I}_s\\
 x_{\widehat{J}_r} & \mbox{if} &
J_r=\widehat{J}_rI'_s\\
 0 &  & \mbox{otherwise}\\
\end{array}
\right.
$$
we conclude that $XY^{-1}\in \mathcal{P}_{n,r}$, as desired.
\end{proof}

Notice that, if we fix the alphabet $\mathcal{A}_n=\{ 1, \dots ,n\}$, then each multiindex is an element of $W_n$, and the identity $(\ast )$ in Lemma \ref{L:grupunitaris} says that $x_{J_r}y_{I'_s}=0$ if and only if $x_1I'_s$ and $x_1J_r$ are independent elements of $X_1W_n$. The key for connecting the isomorphism problem of Higman-Thompson groups with Leavitt algebras lies precisely in this fact, that we will exploit.

Now, we will prove a technical results that will be needed later.

\begin{lem}\label{L:InverseMap}
Let $n\geq 2$ be a natural number. If $\alpha =\sum\limits_{i=1}^{m}y_{I_i}x_{J_i}\in \mathcal{P}_{n,1}$, then both $\{ I_1, \dots , I_m\}$ and $\{ J_1, \dots , J_m\}$ are expansions of the basis $\{ x_1\}$ of $X_1W_{n}$ (and thus basis).
\end{lem}
\begin{proof}
As the argument is symmetric, we will proof it only for $\{ I_1, \dots , I_m\}$.

First, suppose that $\{ I_1, \dots , I_m\}$ do not contain a complete expansion of $\{ x_1\}$. Then, two different cases could happen:
\begin{enumerate}
\item The set $\{ I_1, \dots , I_m\}$ is independent, and thus can be completed to a basis $$\{ I_1, \dots , I_l, \widehat{I}_{l+1}, \dots ,\widehat{I}_{r}\}.$$
\item The set $\{ I_1, \dots , I_m\}$ is not independent. So, we can chose a maximal independent subset $\{ I_1, \dots , I_l\}\subsetneq\{ I_1, \dots , I_m\}$.
\end{enumerate}
Hence, in any of both cases, for $l\leq m$ there exist a maximal independent subset $\{ I_1, \dots , I_l\}\subseteq\{ I_1, \dots , I_m\}$ and a multiindex $Z$ such that $\{ I_1, \dots , I_l, Z\}$ can be expanded to a basis. But then, as $Z$ is independent of the $I_j$s,
$$0\ne x_Z=x_Z\cdot 1=x_Z(\alpha \alpha^*)=(x_Z\alpha )\alpha^*=0\alpha ^*=0$$
which is impossible.

Now suppose that $\{ I_1, \dots , I_m\}$ contains an expansion (i.e. a basis) but it is not a basis, i.e it is not an independent set. Fix $\{ I_1, \dots , I_l\}\subsetneq\{ I_1, \dots , I_m\}$ a basis, and notice that
$$
1=\left( \sum\limits_{i=1}^{l}y_{I_i}x_{J_i}\right)\cdot \left( \sum\limits_{j=1}^{l}y_{J_j}x_{I_j}\right).
$$
Hence,
\begin{align*}
1= &\alpha\alpha^*=  \left( \sum\limits_{i=1}^{m}y_{I_i}x_{J_i}\right)\cdot \left( \sum\limits_{j=1}^{m}y_{J_j}x_{I_j}\right)\\& =\left( \sum\limits_{i=1}^{l}y_{I_i}x_{J_i}+\sum\limits_{i=l+1}^{m}y_{I_i}x_{J_i}\right)\cdot \left( \sum\limits_{j=1}^{l}y_{J_j}x_{I_j}+\sum\limits_{j=l+1}^{m}y_{J_j}x_{I_j}\right)\\& = 1+ \sum\limits_{i=1}^{l}\sum\limits_{j=l+1}^{m}y_{I_i}x_{J_i}y_{J_j}x_{I_j} + \sum\limits_{i=l+1}^{m}\sum\limits_{j=1}^{l}y_{I_i}x_{J_i}y_{J_j}x_{I_j} + \sum\limits_{i=l+1}^{m}\sum\limits_{j=l+1}^{m}y_{I_i}x_{J_i}y_{J_j}x_{I_j}.
\end{align*}
Thus, the last 3 summands equal zero, and in particular for any $l+1\leq i\leq m$ we have $0=y_{I_i}x_{J_i}y_{J_i}x_{I_i}=y_{I_i}x_{I_i}$, which is impossible. So, we are done.
\end{proof}

The goal is to prove that for any $n\geq 2, r\geq 1$, $\mathcal{P}_{n,r}\cong G_{n,r}$. In order to do more comprehensible the argument, first we will prove the result in the particular case $r=1$. This result is analogous to \cite[Proposition 9.6]{N}, but the proof is different.

\begin{prop}\label{P:IsoFor r=1}
If $n\geq 2$ is a natural number, then $\mathcal{P}_{n,1}\cong G_{n,1}$.
\end{prop}
\begin{proof}
By \cite[Lemma 4.1]{Higman}, given an element $x\in G_{n,1}$, we can express it by using a symbol
$$x=
\left(
\begin{array}{ccc}
I_1  &  \dots  & I_m  \\
 J_1 & \dots   & J_m
\end{array}
\right)
$$
where both $\{ I_1, \dots , I_m\}$ and $\{ J_1, \dots , J_m\}$ are expansions of the basis $\{ x_1\}$ of $X_1W_{n}$ (and thus basis). Now define
$$\alpha_x=\sum\limits_{i=1}^{m}y_{I_i}x_{J_i}\in L_n.$$
Notice that
$$
\alpha_x\alpha_x^*=\left( \sum\limits_{i=1}^{m}y_{I_i}x_{J_i}\right)\cdot \left( \sum\limits_{j=1}^{m}y_{J_j}x_{I_j}\right)= \sum\limits_{i=1}^{m}y_{I_i}x_{I_i}=1,
$$
where the last two equalities are due to the fact that both $\{ I_1, \dots , I_m\}$ and $\{ J_1, \dots , J_m\}$ are expansions of the basis $\{ x_1\}$ of $W_{n,1}$. Similarly, $\alpha_x^*\alpha_x=1$, so that $\alpha_x\in \mathcal{P}_{n,1}$. Define a map
$$\begin{array}{cccc}
 \varphi: &  G_{n,1} & \rightarrow & \mathcal{P}_{n,1}   \\
  &  x & \mapsto  & \alpha_x
\end{array},
$$
and notice that $\varphi$ send symbols equivalent by elementary expansions to the same element in $L_n$. Thus, if
$$x=
\left(
\begin{array}{ccc}
I_1  &  \dots  & I_m  \\
 J_1 & \dots   & J_m
\end{array}
\right)
\mbox{ and }
y=
\left(
\begin{array}{ccc}
R_1  &  \dots  & R_k  \\
 S_1 & \dots   & S_k
\end{array}
\right),
$$
again by \cite[Corollary 1 to Lemma 2.4]{Higman} there exists a common expansion $\{ J'_1 , \dots  , J'_t\}$ of both $\{  J_1, \dots   , J_m  \}$ and $\{ R_1  ,  \dots  , R_k\}$ such that
$$x=
\left(
\begin{array}{ccc}
I'_1  &  \dots  & I'_t  \\
 J'_1 & \dots   & J'_t
\end{array}
\right)
\mbox{ and }
y=
\left(
\begin{array}{ccc}
J'_1 & \dots   & J'_t  \\
 S'_1 & \dots   & S'_t
\end{array}
\right),
$$
whence
$$xy=
\left(
\begin{array}{ccc}
I'_1  &  \dots  & I'_t  \\
  S'_1 & \dots   & S'_t
\end{array}
\right).
$$
By the above remark, we get $\varphi (xy)=\varphi (x)\varphi (y)$, so that $\varphi$ is a group morphism.

Now, if $\alpha =\sum\limits_{i=1}^{m}y_{I_i}x_{J_i}\in \mathcal{P}_{n,1}$, then the element
$$x_{\alpha}=
\left(
\begin{array}{ccc}
I_1  &  \dots  & I_m  \\
 J_1 & \dots   & J_m
\end{array}
\right)
$$
belong to $G_{n,1}$ by Lemma \ref{L:InverseMap}, so that
$$\begin{array}{cccc}
 \psi: &  \mathcal{P}_{n,1} & \rightarrow & G_{n,1}   \\
  &  \alpha & \mapsto  & x_{\alpha  }
\end{array}
$$
is a well-defined map. Moreover, $\varphi(x_{\alpha})=\alpha$, so that $\varphi $ is an onto map. As $\psi$ is clearly compatible with the equivalence of symbols by elementary expansions, in turns out that $\psi$ is a group morphism. A simple inspection shows that $\varphi$ and $\psi$ are mutually inverses, so we are done.
\end{proof}

Now, we prove the general version.

\begin{prop}\label{Prop:IsoGroups}
If $n\geq 2$ and $r\geq 1$ are natural numbers, then $\mathcal{P}_{n,r}\cong G_{n,r}$.
\end{prop}
\begin{proof}
Consider $X_r=\{ x_1, \dots ,x_r\}$ as basis of $X_rW_{n}$, and take
$$x=
\left(
\begin{array}{ccc}
I_1  &  \dots  & I_k  \\
 J_1 & \dots   & J_k
\end{array}
\right)\in G_{n,r}.
$$
For any $1\leq i,j\leq r$, consider the strictly ascending finite sequence
$$1\leq l(i,j)_1<\cdots < l(i,j)_{s(i,j)}\leq k$$
such that $I_{l(i,j)_t}$ starts in $x_i$ and $J_{l(i,j)_t}$ starts in $x_j$ for every $1\leq t\leq s(i,j)$ (Notice that it can happens for some sequences in this list to be empty). Consider now the multiindices $I'_{l(i,j)_t}$ and $J'_{l(i,j)_t}$ obtained from $I_{l(i,j)_t}$ and $J_{l(i,j)_t}$ (respectively) by erasing the initial $x_i$ (resp. $x_j$). Now we define the matrix $X\in M_r(L_n)$ whose $(i,j)$-entry is
$$X_{i,j}=\sum\limits_{p=1}^{s(i,j)}y_{I'_{l(i,j)_p}}x_{J'_{l(i,j)_p}}.$$
Notice that $x_{J'_{l(i,k)_p}}y_{J'_{l(j,k)_q}}=\delta_{i,j}\cdot\delta_{p,q}$; indeed, if $x_{J'_{l(i,k)_p}}y_{J'_{l(j,k)_q}}=1$ for $i\ne j$ or $p\ne q$, then the symbol of $x$ shall contain entries
$$
x=
\left(
\begin{array}{ccccc}
\dots & x_iI'_{l(i,k)_p}  &  \dots  & x_jI'_{l(j,k)_q} &\dots \\
 \dots & x_kJ'_{l(i,k)_p} & \dots   & x_kJ'_{l(j,k)_q}  & \dots
\end{array}
\right)
$$
with $x_kJ'_{l(i,k)_p}=x_kJ'_{l(j,k)_q}$, which is impossible by definition of symbol. Also, since $\{ I_1  ,  \dots  , I_k \}$ is an expansion of $X_r$,
$$\{ I_{l(i,1)_1}, \dots, I_{l(i,1)_{s(i,1)}},\dots ,I_{l(i,r)_1}, \dots, I_{l(i,r)_{s(i,r)}}\}$$
is an expansion of the element $x_i\in X_r$.

We then have
\begin{align*}
(XX^*)_{i,j}= &\sum\limits_{k=1}^{r}\left( \sum\limits_{p=1}^{s(i,k)} y_{I'_{l(i,k)_p}}x_{J'_{l(i,k)_p}}\right)\cdot \left( \sum\limits_{q=1}^{s(j,k)} y_{J'_{l(j,k)_q}}x_{I'_{l(j,k)_q}}\right)\\ & = \delta_{i,j} \cdot\sum\limits_{k=1}^{r} \sum\limits_{p=1}^{s(i,k)} y_{I'_{l(i,k)_p}}x_{I'_{l(i,k)_p}}=\delta _{i,j},
\end{align*}
and similarly $(X^*X)_{i,j}=\delta _{i,j}$. Hence, $X\in \mathcal{P}_{n,r}$. Thus,
$$\begin{array}{cccc}
 \varphi: &  G_{n,r} & \rightarrow & \mathcal{P}_{n,r}   \\
  &  x & \mapsto  & X
\end{array}
$$
is a well-defined map. Clearly $\varphi$ respects the equivalence of symbols by elementary expansions in $G_{n,r}$, so that it is straightforward but tedious to prove that in fact it is a group morphism.

Now, take $X\in \mathcal{P}_{n,r}$. For any $1\leq i,j\leq r$,
$$X_{i,j}=\sum\limits_{p=1}^{s(i,j)}y_{I_{l(i,j)_p}}x_{J_{l(i,j)_p}}$$
for suitable sets of multiindices. We will show that both $W_I=\left\{ \left\{ x_i{I_{l(i,j)_p}}\right\}_{1\leq p\leq s(i,j)} \right\}_{1\leq i,j\leq r}$ and $W_J=\left\{ \left\{ x_j{J_{l(i,j)_p}}\right\}_{1\leq p\leq s(i,j)} \right\}_{1\leq i,j\leq r}$ are expansions of the basis $X_r$. Notice that for any $1\leq i\leq r$,
$$(\ast) \hspace{.2truecm} 1=\sum\limits_{k=1}^{r}X_{i,k}X_{i,k}^*=\sum\limits_{k=1}^{r}\left( \sum\limits_{p,q=1}^{s(i,k)}y_{I_{l(i,k)_p}}x_{J_{l(i,k)_p}}y_{J_{l(i,k)_q}}x_{I_{l(i,k)_q}}\right).$$
Fix any $1\leq i\leq r$, and let $W_I(i)=\left\{ \left\{ x_i{I_{l(i,j)_p}}\right\}_{1\leq p\leq s(i,j)} \right\}_{1\leq j\leq r}$. If it do not contain a complete expansion of $x_i$, then the same argument as in Lemma \ref{L:InverseMap} shows that there exist a maximal independent subset $W'$ of $W_I(i)$ and a multiindex $Z$ such that $W'\cup \{Z\}$ is a part of a basis for $x_i$. Hence,
$$0\ne x_Z\cdot e_{i,i}=(x_Z\cdot e_{i,i})(XX^*)=((x_Z\cdot e_{i,i}X)X^*$$
has $(k,j)$-entry equal to zero for any $k\ne i$ and any $j$, while
$$(x_Z\cdot e_{i,i}X)_{i,k}=\sum\limits_{p=1}^{s(i,k)}x_Zy_{I_{l(i,k)_p}}x_{J_{l(i,k)_p}}=0,$$
which is impossible. On the other side, if $W_I(i)$ contains an expansion of $\{ x_i\}$ but it is not a basis, again the argument in Lemma \ref{L:InverseMap} and the identity $(\ast)$ give us a contradiction. Thus, $W_I(i)$ is an expansion of $x_i$, and thus so is $W_I$ of $X_r$. Similarly we get that $W_J$ is an expansion of $X_r$. Since both sets has the same cardinality,
$$x_X=
\left(
\begin{array}{ccccc}
 x_1I_{l(1,1)_1} &\dots &x_iI_{l(i,j)_p}& \dots& x_rI_{l(r,r)_{s(r,r)}}  \\
  x_1J_{l(1,1)_1} &\dots  &x_jJ_{l(i,j)_p}& \dots& x_rJ_{l(r,r)_{s(r,r)}}
\end{array}
\right)
$$
is a symbol of an element of $G_{n,r}$, so that
$$\begin{array}{cccc}
 \psi: &  \mathcal{P}_{n,r} & \rightarrow & G_{n,r}   \\
  &  X & \mapsto  & x_X
\end{array}
$$
is a well-defined map. Moreover, $\varphi (x_X)=X$, so that $\varphi$ is an onto map. As $\psi$ clearly respects the equivalence of symbols by elementary expansions, $\psi$ is a group morphism, and $\varphi$ and $\psi$ are mutually inverses, so we are done.
\end{proof}

Now, we are ready to prove the main result in the paper.

\begin{theor}\label{Th:Main}
Let $n, m\geq 2$ and $r, s\geq 1$ be natural numbers. Then, $G_{m,r}^+\cong G_{n,s}^+$ if and only if $m=n$ and $\mbox{gcd}(n-1,r)=\mbox{gcd}(n-1,s)$.
\end{theor}
\begin{proof}
The ``only if'' part is \cite[Theorem 6.4]{Higman}.

Now, assume that $\mbox{gcd}(n-1,r)=\mbox{gcd}(n-1,s)$. Then, by Corollary \ref{Corol:IsoLeavitt}, there exists a $K$-algebra isomorphism $\varphi: M_r(L_n)\rightarrow M_s(L_n)$ that, by Remark \ref{R:special iso3}, restricts to a group isomorphism $\phi: \mathcal{P}_{n,r}\rightarrow \mathcal{P}_{n,s}$. As $G_{n,r}\cong \mathcal{P}_{n,r}$ and $G_{n,s}\cong \mathcal{P}_{n,s}$ by Proposition \ref{Prop:IsoGroups}, we conclude that $G_{n,r}\cong G_{n,s}$, and thus $G_{n,r}^+\cong G_{n,s}^+$, as desired.
\end{proof}

config: arxiv


TITLE: can local maximums and minimums be on endpoints?
QUESTION [3 upvotes]: My textbook has these passages written and I'm a bit confused as to whether local maximums and minimums can be on endpoints. why or why not?

Apparently x=4 is not a local maximum. But why?
Other passages:

REPLY [2 votes]: can local maximums and minimums be on endpoints?

Not according to the definition in your second scanned image.

Apparently $x=4$ is not a local maximum. But why?

Short answer: because the "near $c$" language in the definition means "near $c$" on both sides of $c$.
Longer answer: According to the definition in the red box of your second scanned image,

the number $f(c)$ is a local maximum value of $f$ if $f(c) \geq f(x)$ when $x$ is near $c$

where "near $c$" means

on some open interval containing $c$.

However, for the function $f$ whose graph is plotted in Figure 7, every open interval containing $4$ will contain some values $x > 4$, for which $f(x)$ is not defined. (The domain of $f$ was given to be the closed interval $[-1, 4]$.)  So, it's not possible to have $f(4) \geq f(x)$ for every $x$ in some open interval containing $4$.
The discussion above addresses the definition of local maximum, but the definition for local minimum is analogous and has the same issue.


TITLE: How do I show that $x+(1-\alpha)y < 0$ for all $0<\alpha < 1$?
QUESTION [2 upvotes]: Suppose that $x\in\mathbb{R}^{-}$, $y\in\mathbb{R}^{+}$, and $0<\alpha <1$. I would like to construct an argument to show that the expression $x+(1-\alpha)y$ is negative. My take on it is as follows:
$$
x+(1-\alpha)y\leq x-|\alpha-1|y<0.
$$
I think that this does it. However, I'm worried about what I did with $(1-\alpha)$, knowing that $0<\alpha<1$. Am I thinking correctly, or is there something I'm missing here?

REPLY [1 votes]: This result is not true for all $x \in \mathbb{R}^-$, $y \in \mathbb{R}^+$ and $\alpha < 1$. For example, take $\alpha = 1/2 < 1$. Then you would like for $x + (1-\alpha)y = x + y/2$ to be always negative. However, it cannot be true for any $x > 0$ and $y < 0$ since you can take $y > -2x$, and hence $x + y/2 > x - 2x/2 = 0$.
To see what's wrong in your proof, remember that by the definition of the absolute value, for all $x \in \mathbb{R}$ we have $-|x| \leq x \leq |x|$, so it is certain that $\alpha - 1 \leq |\alpha - 1|$. However, since $y$ is positive, the inequality you used here is true if $(1-\alpha) \leq -|\alpha - 1|$, which is equivalent to $|\alpha - 1| \leq \alpha - 1$. So this can be true only if $|\alpha - 1| = \alpha - 1$, that is if $\alpha - 1 > 0$, or $\alpha > 1$. It obviously contradicts your hypothesis.


TITLE: Quadratic Inequality in terms of variable $x$
QUESTION [4 upvotes]: Find the values of $a$ for which the inequality $x^2+ax+a^2+6a<0\;\forall x \in (1,2)$

$\bf{My\; Try::}$ We can Write Equation as $$x^2+ax+\frac{a^2}{4}+\frac{3a^2}{4}+6a<0$$
So $$\left(x+\frac{a}{2}\right)^2+\frac{3a^2+24a}{4}<0$$
Now how can i solve after that, Help required, Thanks

REPLY [1 votes]: Rewrite the inequality as $$(2a+x+6)^2< (6-x)(3x+6)$$
The right hand side is positive for $1<x<2$, so we get
$$-\sqrt{(6-x)(3x+6)}<2a+x+6<\sqrt{(6-x)(3x+6)}$$
and
$$-x-6-\sqrt{(6-x)(3x+6)}<2a<-x-6+\sqrt{(6-x)(3x+6)}$$
$$\frac{-x-6-\sqrt{(6-x)(3x+6)}}{2}<a<\frac{-x-6+\sqrt{(6-x)(3x+6)}}{2}$$
The maximum of the right hand side is $-4+2 \sqrt{3}$ (let $x=2$) and the minimum of the left side is $-\frac{7}{2}-\frac{3 \sqrt{5}}{2}$ (let $x=1$)
so $$-\frac{7}{2}-\frac{3 \sqrt{5}}{2}<a<-4+2 \sqrt{3}$$


TITLE: Picking a point on a sphere uniformly at random
QUESTION [0 upvotes]: I wanted to read a bit about the Borel-Kolmogorov paradox on Wikipedia, but I don't understand the following: to me it seems that picking a point uniformly at random on the sphere amounts to pick a longitude $\lambda$ uniformly at random from $[-\pi,\pi]$ and picking a latitude $\phi$ uniformly at random from $[-\pi/2,\pi/2]$. However, on Wikipedia it's written we pick the latitude $\phi$ from $[-\pi/2,\pi/2]$ with density $\frac 1 2 \cos(\phi)$. Why is that?

REPLY [1 votes]: We have this density on the latitude essentially because there is more land near the equator, and thus we want to give the latitudes near the equator more weight.
To find the density yourself, I like to use $[0,\pi]$ for the latitude coordinate, where $\phi = 0$ or $\phi = \pi$ corresponds to the $z$-axis, since it corresponds with the polar coordinate system I was taught in multivariable calculus. Then you'll recall from multivariable calculus that $\rho^2\sin\phi\,d\rho\,d\phi\,d\lambda$ is the volume element of $\mathbb R^3$, written in these coordinates, where $(\rho,\phi,\lambda)\in (0,\infty)\times[0,\pi]\times [-\frac\pi2,\frac\pi2]$.
Evaluating at $\rho = 1$ gives us $\sin\phi\,d\phi\,d\lambda$. Dividing this by $4\pi$, which is the area of the sphere, we get the uniform distribution on the sphere: $\frac{1}{4\pi}\sin\phi\,d\phi\,d\lambda = (\frac{1}{2}\sin\phi\,d\phi)(\frac{1}{2\pi}\,d\lambda)$. Or in other words, to sample a point $(\phi,\lambda)$ uniformly at random from the sphere, we sample the latitude $\phi$ from $[0,\pi]$ from a distribution with density $\frac{1}{2}\sin\phi$ and we sample the longitude $\lambda$ from $[-\pi,\pi]$ uniformly, i.e., from a distribution with density $\frac{1}{2\pi}$.

When $\phi \approx \pi/2$, which corresponds to points near the equator, $\sin\phi\approx 1$, so these points have the most weight.
When $\phi\approx 0$, or $\phi\approx \pi$, $\sin\phi\approx 0$, so these points have much less weight.

Both of the last two bullet points make sense if you think about how there is so much more land in a latitudinal strip of width $d\phi$ near the equator, versus near the poles.


TITLE: limits of sequences such as $\lim_{n \rightarrow \infty}\sqrt[n]{n!}$
QUESTION [2 upvotes]: I have a problem figuring out the limit: $\lim_{n \rightarrow \infty}\sqrt[n]{n!}$.
And other similar limits such as:

$\lim_{n \rightarrow \infty} \frac{n}{\sqrt[n]{n!}}$
$\lim_{n \rightarrow \infty}\sqrt[n]{kn \choose n}$
$\lim_{n \rightarrow \infty}\frac{n!}{(n+1)(n+1)...(2n)}$

I also have difficulties proving that if $\lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n}=l>1$, then, $\lim_{n \rightarrow \infty}a_n = \infty$
Can anyone help?
Thanj you, Tali

REPLY [0 votes]: For 1. note the reciprocal is $(n!/n^n)^{1/n}.$ Apply $\ln $ to that to get
$$\frac{1}{n}\sum_{k=0}^{n-1}\ln (1-k/n) \to \int_0^1\ln (1-x)\, dx = -1.$$
Thus the reciprocal $\to e^{-1},$ which gives $e$ for the limit of the original expression.


text:
\begin{document}
\makeatletter

\title{Classification of one dimensional dynamical systems by countable structures}

\author{Henk Bruin\\ \\
Faculty of Mathematics \\
University of Vienna \\
Oskar Morgensternplatz 1 \\
1090 Vienna, Austria
\\
\texttt{henk.bruin@univie.ac.at}
\and
Benjamin Vejnar\footnote{This work has been supported by Charles University Research Centre program No.UNCE/SCI/022.}
\\ \\
Faculty of Mathematics and Physics \\
Charles University \\
Prague, Czechia\\ \\
\texttt{vejnar@karlin.mff.cuni.cz}}

\maketitle

\begin{abstract}
We study the complexity of the classification problem of conjugacy on dynamical systems on some compact metrizable spaces.
Especially we prove that the conjugacy equivalence relation of interval dynamical systems is Borel bireducible to
isomorphism  equivalence relation of countable graphs. This solves a special case of the Hjorth's conjecture which states that every orbit equivalence relation induced by a continuous action of the group of all homeomorphisms of the closed unit interval is classifiable by countable structures.
We also prove that conjugacy equivalence relation of Hilbert cube homeomorphisms is Borel bireducible to the universal orbit equivalence relation.
\end{abstract}

\subjclass{Primary: 54H20 Secondary: 03E15, }
\keywords{Conjugacy, classification, Borel reduction, countable structures, universal orbit equivalence relation}

\section{Introduction}

 Measuring the complexity of relations on structures is a very general task.
 In this paper we use the notion of \emph{Borel reducibility} (see Definition~\ref{def:Borel_red})
 and the results of Invariant descriptive set theory to compare the complexities of classification problems. For more details on Invariant descriptive set theory we refer to the book by Gao \cite{Gao}. For a short and nice introduction to the theory of Borel reductions we refer to a paper by Foreman \cite{ForemanIntroduction}.

 Several equivalence relations  became milestones in this theory. Let us mention four of those, which describe an increasing chain of complexities:
\begin{itemize}[noitemsep]
\item the equality on an uncountable Polish space,
\item the equality of countable sets,
\item the $S_\infty$-universal orbit equivalence relation ($S_\infty$ is the group of permutations on $\N$),
\item the universal orbit equivalence relation,
\end{itemize}

Let us give several \emph{examples} to make the reader more familiar with the above relations.
A classical example is a result of Gromov (see e.g. \cite[Theorem~14.2.1]{Gao}) who proved that the isometry equivalence relation of compact metric spaces is a \emph{smooth} equivalence relation, which means that it is Borel reducible to the equality of real numbers (or equivalently of an uncountable Polish space).
The isomorphism relation of countable graphs or the isomorphism relation of countable linear orders are Borel bireducible to the $S_\infty$-universal orbit equivalence.
The homeomorphism equivalence relation of compact metrizable spaces and the isometry relation of separable complete metric spaces were proved by Zielinski in \cite{Zielinski} and by Melleray in \cite{Melleray}, respectively, to be Borel bireducible to the universal orbit equivalence relation
(see the survey paper by Motto Ros~\cite{MottoRos}).

In order to capture all the structures in one space we need some sort of \emph{coding}. This can be done by considering some universal space (e.g. the Hilbert cube or the Urysohn space)

and all its subspaces with some natural Polish topology or Borel structure (e.g the hyperspace topology or the Effros Borel structure).
Sometimes there are other natural ways to encode a given structure. For example the class of separable complete metric spaces can be coded by the set of all metrics on $\N$ where two metrics are defined to be equivalent if the completions of the respective spaces are isometric. Fortunately in this case, by \cite[Theorem 14.1.3]{Gao} it does not matter which coding we choose.
It is generally believed that this independence on a natural coding is common to other structures and thus the statements are usually formulated for all structures without mentioning the current coding. Nevertheless, for the formal treatment some coding is always necessary.

The aim of this paper is to determine the complexity of some classification problems of dynamical systems up to conjugacy. Dynamical systems of a fixed compact metrizable space $X$ can be naturally coded as a space of continuous functions mapping $X$ into itself, with the uniform topology. This one as well as the subspace of all self-homeomorphisms is well known to be a Polish space.

Let us mention several results which are dealing with the complexity of conjugacy equivalence relation.
It was proved by Hjorth that conjugacy equivalence relation of homeomorphisms of [0,1] is classifiable by countable structures \cite[Section 4.2]{Hjorth} (in fact Borel bireducible to the universal $S_\infty$-orbit equivalence relation) but conjugacy of homeomorphisms of $[0,1]^2$ is not \cite[Section 4.3]{Hjorth}.
By a result of Camerlo and Gao, conjugacy equivalence relation of both selfmaps and homeomorphisms of the Cantor set are Borel bireducible to the $S_\infty$-universal orbit equivalence relation  \cite[Theorem~5]{CamerloGao}.
Kaya proved that conjugacy of pointed minimal Cantor dynamical systems is Borel bireducible to the equality of countable subsets of reals \cite{Kaya}.
Conjugacy of odometers is smooth due to Buescu and Stewart \cite{BuescuStewart}.
The complexity of conjugacy of Toepliz subshifts was treated several times -- by Thomas, Sabok and Tsankov,
and by Kaya \cite{Thomas, SabokTsankov, KayaSubshift}.
Conjugacy of two-sided subshifts is Borel bireducible to the universal countable Borel equivalence relation
due to Clemens \cite{Clemens}. There is an extensive exposition of results on the complexity of conjugacy equivalence relation on subshifts of $2^G$ for a countable group $G$ in the book by Gao, Jackson and Seward \cite[Chapter 9]{GaoJacksonSeward}.
Recently, during the 8th Visegrad Conference on Dynamical Systems in 2019 it was announced by Dominik Kwietniak that conjugacy of shifts with specification is Borel bireducible to the universal countable Borel equivalence relation.

In this paper, we deal with some of the missing parts.
By mainly elementary and standard tools, we prove that conjugacy of interval maps is Borel bireducible to the $S_\infty$-universal orbit equivalence relation.
Conjugacy of homeomorphisms as well as of selfmaps of the Hilbert cube is proved to be Borel bireducible to the universal orbit equivalence relation. To this end we use some tools of infinite dimensional topology and a result of Zielinski on the complexity of homeomorphism equivalence relation of metrizable compacta \cite{Zielinski} combining with some ideas of P. Krupski and the second author \cite{KrupskiVejnar}.
Finally we make a small overview on the complexity of conjugacy equivalence relation of dynamical systems on the Cantor set, on the arc, on the circle and on the Hilbert cube.

\section{Definitions and notations}

A \emph{Polish space} is a separable completely metrizable topological space.
Recall that a  \emph{standard Borel space} is a measurable space $(X, \mathcal S)$ such that there is a
Polish topology $\tau$ on $X$ for which the family $(X,\tau)$ of Borel subsets  is equal to $\mathcal S$. In order to compare the complexities of equivalence relations we use the notion of Borel reducibility.

\begin{definition}\label{def:Borel_red}
Suppose that $X$ and $Y$ are sets and let $E$, $F$ are equivalence relations on $X$ and $Y$ respectively.
We say that $E$ is \emph{reducible} to $F$, and we denote this by $E\leq F$, if there exists a mapping $f\colon X\to Y$ such that
\[x E x' \iff f(x) F f(x'),\]
for every $x, x'\in X$.
The function $f$ is called a \emph{reduction} of $E$ into $F$.
If the sets $X$ and $Y$ are endowed with Polish topologies (or standard Borel structures), we say that $E$ is \emph{Borel reducible} to $F$, and we write $E\leq_B F$, if there is a reduction $f\colon X\to Y$ of $E$ into $F$ which is Borel measurable.
We say that $E$ is \emph{Borel bireducible} to $F$, and we write $E \sim_B F$, if $E$ is Borel reducible to $F$ and $F$ is Borel reducible to $E$.
\end{definition}
In a similar fashion we  define being \emph{continuously reducible} if in addition $X$ and $Y$ are Polish spaces and $f$ is continuous.

In the whole paper we set $I=[0,1]$ and denote the closure operator by $\Cl$.
For a separable metric space $X$ we denote by $\mathcal K(X)$ the hyperspace of all compacta in $X$ with the
Hausdorff distance $d_H$ and the corresponding Vietoris topology. The space $C(X)$ is the space of all continuous functions of $X$ into itself.

The equality equivalence relation of real numbers is denoted as $E_=$. We denote by $E_{=^+}$ the equivalence relation on $\R^{\N}$ defined by $(a_n)E_{=^+} (b_n)$ if and only if $\{a_n\colon n\in\N\}=\{b_n\colon n\in\N\}$. The last equivalence relations is called the \emph{equality of countable sets}.

We say, that an equivalence relation $E$ defined on a standard Borel space $X$ is \emph{classifiable by countable structures} if there is a countable relation language $\mathcal L$ such that $E$ is Borel reducible to the isomorphism relation of $\mathcal L$-structures whose underlying set is $\N$.

An equivalence relation $E$ on a standard Borel space $X$ is said to be an \emph{orbit equivalence relation} if there is a Borel action of a Polish group $G$ on $X$ such that $xEx'$ if and only if  there is some $g\in G$ for which $gx=x'$.

Let $\mathcal C$ be a class of equivalence relations on standard Borel spaces. An element $E\in\mathcal C$ is called \emph{universal} for $\mathcal C$ if $F\leq_B E$ for every $F\in\mathcal C$.
It is known that for every Polish group $G$ there is an equivalence relation (denoted by $E_G$) on a standard Borel space that is universal for all orbit equivalence relations given by continuous $G$-actions.
We are particularly interested in the \emph{universal $S_\infty$-equivalence relation} $E_{S_\infty}$, where $S_\infty$ is the group of all permutations of $\N$.
It is known that an equivalence relation is classifiable by countable structures if and only if it is Borel reducible to $E_{S_\infty}$. Moreover $E_{S_\infty}$ is known to be Borel bireducible to isomorphism equivalence relation of countable graphs.
Also there exists a \emph{universal orbit equivalence relation} which is denoted by $E_{G_\infty}$. We should also note that all the mentioned equivalence relations are analytic sets, i.e. images of standard Borel spaces with respect to a Borel measurable map.
We have a chain of complexities
\[E_=\b E_{=^+}\b E_{S_\infty}\b E_{G_\infty}\]
and it is known that none of these Borel reductions can be reversed.

\section{Interval dynamical systems}

 In this section we prove that conjugacy of interval dynamical systems is classifiable by countable structures.

The strategy of our proof

is as follows. In the first part we describe a natural reduction of interval dynamical systems to some kind of countable structures.
We assign to every $f\in C(I)$ a countable invariant set $C_f\subseteq I$ of some dynamically exceptional points for $f$. Since the set $C_f$ does not need to be dense in $I$ we do not have enough information to capture the dynamics of $f$ by restricting to $C_f$. On the other hand the dynamics on the maximal open intervals of $I\setminus C_f$ is quite simple. Hence it will be enough to define an invariant countable dense subset $D_f$ in $I\setminus\Cl(C_f)$ arbitrarily. Consequently, we get that for $f$ conjugate to $g$ there exists a conjugacy of $f$ to $g$ which sends the set $C_f\cup D_f$ onto $C_g\cup D_g$.
Finally it is enough to assign to every $f\in C(I)$ a countable structure $\Psi(f)$ whose underlying set is $C_f\cup D_f$ and which is equipped with one binary relation $\leq\restriction_{C_f\cup D_f}$ and one function $f\restriction_{C_f\cup D_f}$ (which can be as usual considered as a binary relation).
We will prove then that if two such structures $\Psi(f)$ and $\Psi(g)$ are isomorphic then $f$ and $g$ are conjugate.

In the second part we prove that this reduction can be modified using some sort of coding so that the assigned countable structures share the same support and so that the new reduction is Borel. To this end we use Lusin-Novikov selection theorem \cite[Theorem 18.10]{Kechris} several times.

For $g\in C(I)$ we denote by $\Fix(g)$ the set of fixed points of $g$, i.e. those points for which $g(x)=x$.
We omit the proof of the following ``folklore'' lemma. The key idea of the proof is the back and forth argument.

\begin{lemma}\label{folk}
Let $f, g\in C(I)$ be increasing homeomorphisms such that $\Fix(f)=\Fix(g)=\{0,1\}$ and let $A, B\subseteq (0,1)$ be countable dense sets that are invariant in both directions for $f$ and $g$ respectively.
Then there is a conjugacy $h$ of $f$ and $g$ satisfying $h(A)=B$.
\end{lemma}

\begin{definition}
For $f\in C(I)$ let us say that a point $z\in I$ is a \emph{left sharp local maximum} of $f$ if there is some $\delta>0$ such that $f(x)<f(z)$ for $x\in (z-\delta, z)$ and $f(x)\leq f(z)$ for $x\in (z, z+\delta)$. In a similar fashion we define \emph{left sharp local minimum}, \emph{right sharp local minimum} and \emph{right sharp local maximum}.
\end{definition}

\begin{notation}\label{conditions}
Let $M_f$ be the union of ${0,1}$ and the set of all left and right sharp local maxima and minima. It is easily shown that the set $M_f$ is countable.
For a closed set $F\subseteq I$ denote by $\Acc(F)$ the set of all accessible points of $F$ in $\mathbb R$, i.e. those points $x\in I$ for which there exists an open interval $(a,b)\subseteq \mathbb R\setminus F$ for which $x=a$ or $x=b$.

For every $f\in C(I)$ let us denote by $C_f$ the smallest set such that
\begin{itemize}
\item[a)] $M_f\subseteq C_f$,
\item[b)] if $f^{-1}(y)$ contains an interval then $y\in C_f$,
\item[c)] if $n\in\mathbb N$ then $\Acc(\Fix(f^n))\subseteq C_f$,
\item[d)] $f(C_f)\subseteq C_f$,
\item[e)] if $y\in C_f$ then $\Acc(f^{-1}(y))\subseteq C_f$.
\end{itemize}
\end{notation}

\begin{lemma}
The set $C_f$ is countable for every $f\in C(I)$.
\end{lemma}

\begin{proof}
Let $S_1$ be the union of $M_f$, all the values of $f$ at locally constant points and all the sets $\Acc(\Fix(f^n))$ for $n\in\mathbb N$.
Clearly $S_1$ is countable.
Let $S_{i+1}=S_i\cup f(S_i)\cup \bigcup\{\Acc(f^{-1}(y))\colon y \in S_i\}$.
Clearly $C_f=\bigcup\{S_i\colon i\in\N\}$ and thus it is countable.
\end{proof}

Note that $C_f$ depends only on the topological properties of $I$ and the dynamics of $f$. That is if $f$ and $g$ are conjugate by some homeomorphism $h$, then $h(C_f)=C_g$.
This is clear because $h$ maps $M_f$ onto $M_g$, locally constant intervals of $f$ to locally constant intervals of $g$ and periodic points of $f$ to periodic points of $g$.

Let us denote by $\mathcal J_f$ be the collection of all maximal open subintervals of $I\setminus C_f$.

\begin{lemma}\label{complementaryintervals}
Let $J\in \mathcal J_f$. Then either $f\restriction_J$ is constant or $f\restriction_J$ is one to one and in this case $f(J)\in \mathcal J_f$. Also $f^{-1}(J)$ is the finite union (possibly the empty union) of elements of $\mathcal J_f$.
\end{lemma}

\begin{proof}
Let us prove first that $f\restriction_J$ is either constant or one-to-one. Suppose that the contrary holds. Then there are points $x, y, z\in J$ such that $f(x)=f(y)\neq f(z)$ and $x\neq y$. Let us suppose without loss of generality that $x<y<z$ and $f(x)<f(z)$. Let $u=\min f\restriction_{[x,z]}$ and let $v=\max (f^{-1}(u)\cap [x, z])$.
It follows that $v\in (x,z)$ is a right sharp local minimum. By Notation~\ref{conditions} a) it follows that $v\in C_f$ which is a contradiction since $J$ is disjoint from $C_f$.

Suppose now that $f\restriction_J$ is one-to-one and let us prove that $f(J)\in\mathcal J_f$.
Observe first that $f(J)$ is disjoint from $C_f$, otherwise there would be a point $y\in f(J)\cap C_f$ and since
$f^{-1}(y)$ is a closed set not containing the whole set $J$ there will be a point in $\Acc f^{-1}(y)\cap J$ which is a contradiction with Notation~\ref{conditions} e).
We need to prove that $f(J)$ is a maximal interval disjoint from $C_f$. Suppose that $J=(a,b)$. Then there are $a_n, b_n\in C_f$ such that $a_n\to a, b_n\to b$. By continuity of $f$ it follows that $f(a_n)\to f(a)$ and $f(b_n)\to f(b)$. Also $f(a_n), f(b_n)\in C_f$ by Notation~\ref{conditions} d). Thus the maximality follows.

Observe first that $f^{-1}(J)$ is a countable union of disjoint collection of open intervals and if we prove that each of the intervals is mapped by $f$ onto $J$ it will follow by continuity that such a collection is in fact finite.
Denote $(a,b)=J$ and let $(c,d)$ by a maximal interval in $f^{-1}(J)$. Clearly $(c,d)\cap C_f=\emptyset$ by Notation~\ref{conditions}, so it is enough to prove that it is maximal with this property.
Note that $f(c), f(d)\in \{a, b\}$ otherwise we get a contradiction with $(c,d)$ being maximal interval in $f^{-1}(J)$. Also it can not happen that $f(c)=f(d)$ otherwise there will be a point of left local maximum or minimum in $(c,d)$ which would produce a point in $M_f\cap J$.
Hence $f(c,d)=J$. Moreover, by the first part of this proof we get that $f\restriction_{(c,d)}$ is one-to-one and thus it is either increasing or decreasing. Without loss of generality suppose the first case. Let us distinguish several possibilities
If $f\geq f(c)$ on a left neighborhood of $c$ then $c$ is a point of right sharp local minimum and thus $c\in C_f$. Otherwise choose a sequence $a_n\in C_f$ such that $a_n\to a$. We define points $c_n=\max([0,c]\cap f^{-1}(a_n))$. These are eventually well defined, $c_n\to c$ and $c_n\in\Acc f^{-1}(a_n)$. Hence by d) $c_n\in C_f$. We can proceed in a similar way with the point $d$ and thus the interval $(c,d)$ is maximal subinterval of $I\setminus C_f$.
\end{proof}

\begin{example}
For the tent map $f(x) =\min\{ 2x, 2(1-x)\}$, the set  $C_f$ contains all the dyadic numbers in $I$,
thus $C_f$ is a dense subset of $I$ and hence $\mathcal J_f=\emptyset$.
For the map $g=\frac14 f$ we have
\begin{align*}
C_g&=\{2^{-n}, 1-2^{-n}\colon n\in\mathbb N\}\cup\{0,1\}, \\
\mathcal J_f&=\{(2^{-n-1}, 2^{-n}), (1-2^{-n}, 1-2^{-n-1})\colon n\in\mathbb N\}.
\end{align*}
\end{example}

\begin{notation}
Let $G_f$ be a directed graph on $\mathcal J_f$ where $(J,K)$ forms an oriented edge if and only if $f(J)=K$.
Let $E_f=\mathbb Q\cap I\setminus \Cl(C_f)$ and let
\[D_f=\bigcup_{n\in\mathbb Z} f^n(E_f).\]
Note that the union is taken over all integers. In spite of that it follows by Lemma~\ref{complementaryintervals} that $D_f$ is countable.
Let us define
\[\Psi(f)=(C_f\cup D_f, \leq\restriction_{C_f\cup D_f}, f\restriction_{C_f\cup D_f}).\]
\end{notation}

\begin{theorem}\label{conjugacy}
The mapping $\Psi$ is a reduction of orientation preserving conjugacy of interval dynamical systems to the isomorphism relation of countable structures.
\end{theorem}

\begin{proof}
Suppose first that $f$ is conjugate to $g$ via some increasing homeomorphism $h$, that is $f=h^{-1}gh$. We want to find an isomorphism $\varphi\colon \Psi(f) \to \Psi(g)$. Since $h$ does not need to map $D_f$ to $D_g$ so we need to do some more work.
In fact we find a conjugacy $\bar h$ of $f$ and $g$ such that $\bar h(C_f\cup D_f)=C_g\cup D_g$. Then it will be enough to define a mapping $\varphi\colon C_f\cup D_f\to C_g\cup D_g$ as the restriction of $\bar h$. We will define $\bar h$ by parts.
First of all we define $\bar h$ on the set $\Cl(C_f)$ in the same way as $h$.

Clearly $h$ induces an isomorphism of the graphs $(\mathcal J_f, G_f)$ and $(\mathcal J_g, G_g)$.
We will consider the components of the symmetrized graphs $G_f$ and $G_g$.
Note that $J, K\in\mathcal J_f$ are in the same component of $G_f$ if there are $m, n\geq 0$ such that $f^m(J)=f^n(K)$.

Let us distinguish two cases for the components of $G_f$.
If a component of $G_f$ contains an oriented cycle, choose an element $J$ in there (note that the cycle is unique).
Hence there is $n\in\mathbb N$ such that $f^n(J)=J$.
By using Notation~\ref{conditions} c) it follows that either all the points of $J$ are fixed points for $f_n$ or there are no fixed points of $f^n$ in $J$ and the same has to be true for $g^n$.
Hence by using Lemma~\ref{folk} there is a conjugacy $\bar h\restriction_J$ of $f^n\restriction_{\Cl(J)}$ and $g^n\restriction_{\Cl(J)}$ sending $D_f\cap J$ onto $D_g\cap h(J)$.
In components which do not contain an oriented cycle we choose $J$ arbitrarily, and let $\bar h\restriction_J$ be an arbitrary increasing homeomorphism $J\to h(J)$ which maps $J\cap D_f$ onto $h(J)\cap D_g$.

 For any $K$ that is in the same component as $J$ find
 $m, n\geq 0$ such that $f^m(J)=f^n(K)\in\mathcal J_f$ and define $\bar h$ on $K$ using the definition of $\bar h$ on $J$ as
\[(g^{-n}\restriction_K)g^m\bar h (f^{-m}\restriction_J)f^n.\]

On the other hand suppose that $\varphi$ is an isomorphism of the countable structure $\Psi(f)$ to $\Psi(g)$.
Hence $\varphi\colon C_f\cup D_f\to C_f\cup D_g$ is a bijection preserving the order. Thus it can be extended to an increasing homeomorphism $\tilde{\varphi}\colon I\to I$. We claim that $\tilde\varphi$ conjugates $f$ and $g$.
Consider any point $x\in C_f\cup D_f$ and compute  \[g(\tilde\varphi(x))=g(\varphi(x))=\varphi(f(x))=\tilde\varphi(f(x)).\]
Since the set $C_f\cup D_f$ is dense it follows by continuity that $g(\tilde\varphi(x))= \tilde\varphi(f(x))$ for every $x\in I$. Hence $f$ and $g$ are conjugate.
\end{proof}

\subsection{Borel coding}
We need to verify that the mapping $\Psi$ that was proved in Theorem \ref{conjugacy} to be a reduction
can be coded in a Borel way. We use standard notation for the Borel hierarchy, especially $\Sigma^0_1$ is used for the collection of all open sets, $\Sigma^0_2$ is used for the collection of  countable unions of closed sets etc. For a set $B\subseteq X\times Y$ and $x\in X$ let us denote by $B_x$ the set $\{y\in Y\colon (x,y)\in B\}$ and call it \emph{vertical section} of $B$.

The following seems to be folklore in descriptive set theory, but for the sake of completeness we include a
proof.

\begin{proposition}\label{borelclosure}
Let $X, Y$ be Polish spaces and $B\subseteq X\times Y$ be a Borel set with countable vertical sections. Then the set $\bigcup_{x\in X} \{x\}\times \Cl(B_x)$ is Borel as well.
\end{proposition}

\begin{proof}
Let $\mathcal B$ be a countable base for the topology of $Y$. By the Lusin-Novikov selection theorem, we can assume that $B=\bigcup f_n$ for some Borel maps $f_n$.
It follows that
\[(X\times Y)\setminus \left(\bigcup_{x\in X} \{x\}\times \Cl(B_x)\right)=\bigcup_{U\in \mathcal B}\bigcap_{n\in\mathbb N}((X\setminus f_n^{-1}(U))\times U).\]
Hence the set under discussion is Borel.
\end{proof}

Let us denote $\Gamma=\{(K, a)\in\mathcal K(I)\times I\colon a\in \Acc(K)\}$.

\begin{lemma}\label{AccPointsBorel}
The set $\Gamma$ is a $\Sigma^0_2$-set.
\end{lemma}

\begin{proof}
The sets
\[L_n=\{(K, a)\in \mathcal K(I)\times I\colon a\in K, K\cap (a-2^{-n}, a)=\emptyset\},\]
\[R_n=\{(K, a)\in \mathcal K(I)\times I\colon a\in K, K\cap (a, a+2^{-n})=\emptyset\}\]
are closed for every $n\in\mathbb N$. Hence the set $\bigcup (L_n\cup R_n)$ is a $\Sigma^0_2$-set.
\end{proof}

\begin{notation}
For a set $B\subseteq C(I)\times I$ let us define
\begin{align*}
B^\rightarrow&=\{(f, f(x))\colon (f, x)\in B\}, \\
B^\leftarrow&=\{(f, x)\colon (f,f(x))\in B\}, \\
B^\Leftarrow&=\{(f, x)\colon x\in Acc(f^{-1}(y)), (f,y)\in B\}.
\end{align*}
\end{notation}

\begin{lemma}\label{Borelimage}
Let $B\subseteq C(I)\times I$ be a Borel set with countable vertical sections. Then the sets
$B^\rightarrow, B^\leftarrow$ and $B^\Leftarrow$
are Borel as well.
\end{lemma}

\begin{proof}
The evaluation mapping $e\colon C(I)\times I\to I$, $e(f, x)=f(x)$ is continuous. Hence the mapping $\Phi\colon (f,x)\mapsto (f, e(f,x))$ is continuous as well. Especially, the restriction of $\Phi$ to $B$ is Borel and also countable-to-1.
Since by \cite[18.14]{Kechris} countable-to-1 image of a Borel set is Borel we conclude that $\Phi(B)=B^\rightarrow$ is Borel.

By the Lusin-Novikov selection theorem we can write $B=\bigcup F_n$ for some Borel maps $F_n$. It follows then that
\[B^\leftarrow=\bigcup_{n\in\mathbb N}\{(f, x)\colon e(f,x)=F_n(f)\}\] and thus it is a Borel set.

The mapping $p\colon C(I)\times I\to \mathcal K(I)$, $p(f, y)=f^{-1}(y)$ is upper semicontinuous and hence it is Borel by \cite[25.14]{Kechris}.
The set $\Gamma$ is Borel by Lemma~\ref{AccPointsBorel} and it has nonempty and countable vertical sections. Hence $\Gamma=\bigcup b_n$ for some Borel mappings $b_n\colon \mathcal K(I)\to I$, by the Lusin-Novikov selection theorem.
The mapping $\Psi\colon (f,y)\mapsto (f, b_n(f^{-1}(y)))=(f, b_n(p(f, y)))$ is a Borel mapping and its restriction to $B$ is countable-to-1. Hence by \cite[18.14]{Kechris} the set $\Psi(B)=B^{\Leftarrow}$ is Borel.
\end{proof}

\begin{lemma}\label{Borel}
The set
$$
A=\{(f, x)\in C(I)\times I\colon x\in C_f\cup D_f\}
$$
is a Borel subset of $C(I)\times I$.
\end{lemma}

\begin{proof}
Let us prove first that the set $B_a:=\{(f,x)\colon x\in M_f\}$ is Borel.
As the set $\{(f, x)\colon x \text{ is a left sharp local maximum}\}$ can be written in the form
\[\bigcup_{\varepsilon>0}\bigcap_{\eta>0}\bigcup_{\delta>0}\{(f,x)\colon \forall z\in [x-\varepsilon, x-\eta]: f(z)\leq f(x)-\delta \And \forall z\in [x,x+\varepsilon]: f(z)\leq f(x)\}\]
it follows that it is a $\Sigma^0_3$ set. By symmetry it follows that $B_a$ is the union of four $\Sigma^0_3$-sets and thus it is Borel.
The set $B_b:=\{(f, y)\colon f^{-1}(y) \text{ contains an interval} \}$ is a $\Sigma^0_2$-set.
Let $B_c:=\{(f, x)\in C(I)\times I\colon f(x)=x\}$.
The function $F_n\colon C(I)\to K(I)$, $F_n(f)=\Fix(f^n)$ is upper semicontinuous and thus Borel. Since $\Gamma$ is a Borel set by Lemma~\ref{AccPointsBorel} we conclude that the composition $\Gamma\circ F_n$ is Borel because the composition of a Borel binary relation and a Borel function (in that order) is a Borel relation. Hence $B_c=\bigcup_{n\in\mathbb N} \Gamma\circ F_n$ is Borel.
Hence the set $B=B_a\cup B_b\cup B_c$ is Borel.
Define recursively $B_1=B$, $B_{n+1}=B_n \cup B_n^\rightarrow \cup B_n^\Leftarrow$ for $n\in\mathbb N$. All these sets are Borel by Lemma~\ref{Borelimage}.
It follows that $A_1=\bigcup B_n=\{(f, x)\colon x\in C_f\}$ is Borel.

Since $A_1$ has countable vertical sections and it is Borel we conclude using Proposition~\ref{borelclosure} that $A_2=\bigcup_{f\in C(I)}(\{f\}\times \Cl(A_{1,f})) $ is Borel as well. Consequently $A_3=\{(f, x)\colon x\in E_f\}= (C(I)\times \mathbb Q)\setminus A_2$ is Borel. By Lemma~\ref{Borelimage} we conclude that all the sets $A_{n+1}=A_n\cup A_n^\rightarrow\cup A_n^\leftarrow$, $n\geq 3$ are Borel.
Finally $A=A_1\cup \bigcup_{n\geq 3} A_n$ is a Borel set.
\end{proof}

\begin{theorem}\label{bireducible}
The orientation preserving conjugacy of interval dynamical systems is Borel bireducible to the $S_\infty$-universal orbit equivalence relation.
\end{theorem}

\begin{proof}
By the result of \cite[Section 4.2]{Hjorth} conjugacy of interval homeomophisms is Borel bireducible to the $S_\infty$-universal orbit equivalence relation. Hence especially the $S_\infty$-universal orbit equivalence relation is Borel reducible to conjugacy of interval dynamical systems.

Let us argue for the converse.
The set $A$ from Lemma~\ref{Borel} is Borel and it has nonempty and countable vertical sections. Hence by the Lusin-Novikov selection theorem we can find Borel functions $F_n\colon C(I)\to I$ such that $\bigcup F_n=A$.
Since all the vertical sections are infinite we can additionally suppose that for every pair $(f,x)\in A$ there is exactly one $n\in\mathbb N$
satisfying $F_n(f)=x$. Let
\[\Phi(f)=(\mathbb N, R, m),\]
where $R$ is a binary relation and $m$ is a unary function
such that $aRb$ iff $F_a(f)\leq F_b(f)$ and $m(a)=b$ iff $f(F_a(f))=F_b(f)$ for $a, b\in\mathbb N$. There is a natural isomorphism $\Phi(f)\to\Psi(f)$, $a\mapsto F_a(f)$.
Hence clearly $\Phi$ is a reduction.
It is routine to verify that $\Phi$ is Borel by the fact that the functions $F_n$ are Borel.
\end{proof}

Let us note that the same conclusion as in the previous theorem can be proved without assuming orientation preserving conjugacy but with just conjugacy. The reason is that in the proofs of Theorem \ref{bireducible} and Theorem \ref{conjugacy} we can simply consider a ternary betweenness relation $T$ instead of the binary relation of linear order $\leq$, i.e. $(x,y,z)\in T$ if and only if $y$ is an element of the smallest interval containing $x$ and $z$. This ternary relation is clearly forgetting the order of $I$. Also by \cite[Exercise 4.14]{Hjorth} $E_{S_\infty}$ is Borel reducible to conjugacy of interval homeomorphisms. Thus we get the following result.

\begin{theorem}\label{bireducible2}
The conjugacy of interval dynamical systems is Borel bireducible to the $S_\infty$-universal orbit equivalence relation.
\end{theorem}

We note that Theorem~\ref{bireducible2} is a special case of
Hjorth's conjecture \cite[Conjecture 10.6]{Hjorth} stating that every equivalence relation induced by a continuous
action of the group $\mathcal H(I)$ of all interval homeomorphisms on a Polish space is classifiable by countable structures. In this case the homeomorphism group acts on the space of continuous selfmaps by conjugacy. Similarly one can prove that the orbit equivalence relations induced by natural left or right composition actions of the homeomorphism group on the space of continuous selfmaps is Borel reducible to the $S_\infty$-universal equivalence relation.
Also it is known that the orbit equivalence induced by the homeomorphism group action $\mathcal H(I)$ on the hyperspace $\mathcal K(I)$ is Borel bireducible to the $S_\infty$-universal orbit equivalence relation (see \cite[Exercise~4.13]{Hjorth} or \cite{ChangGao2019} for a proof). All these are special cases of Hjorth's conjecture.

\section{Hilbert cube dynamical systems}
Since the homeomorphism equivalence relation of metrizable compacta is known to be Borel bireducible to the universal orbit equivalence relation,
it is not surprising that conjugacy of dynamical systems on the Hilbert cube is of the same complexity, which is the main result of this section.
In a dynamical system $(X, f)$, a point $x$ is called a \emph{locally attracting fixed point} if $f(x)=x$ and there is a neighborhood $U$ of $x$ such that for every $z\in U$ the trajectory $(f^n(z))_{n\in\mathbb N}$ converges to $x$.
The notion of a $Z$-set in the Hilbert cube $Q$ plays an important role and it describes a kind of relative homotopical smallness. In fact, we do not need to recall the definition of a $Z$-set since only few properties on $Z$-sets are necessary. First, every homeomorphism of $Z$-sets can be extended to a homeomorphism of the Hilbert cube. Second, the Hilbert cube $Q\times I$ contains a topological copy of itself $Q\times \{0\}$ as a $Z$-set. Third, every closed subset of a $Z$-set in $Q$ is a $Z$-set in $Q$.

The following proposition is a special case of \cite[Proposition~1]{Zielinski} and it can be proved using the back and forth argument.

\begin{proposition}\label{extension}
Let $K\subseteq A, L\subseteq B$ be four nonempty compact metrizable spaces such that $A\setminus K$ and $B\setminus L$ are dense sets of isolated points in $A$ and $B$ respectively. Then every homeomorphism of $K$ onto $L$ can be extended to a homeomorphism of $A$ onto $B$.
\end{proposition}

The following will be useful in the proof of Theorem~\ref{Hilbert}.

\begin{proposition}[{\cite[Theorem~2.6]{GladdinesvanMill}}]\label{homotopy}
If $X$ is a nondegenerate Peano continuum then there exists a homotopy $H\colon  \mathcal K(X)\times I\to \mathcal K(X)$ for which
\begin{itemize}[noitemsep]
\item $H(A, 0)=A$ for every $A\in 2^X$,
\item $H(A, t)$ is finite for every $t>0$ and $A\in 2^X$.
\end{itemize}
\end{proposition}

Recall that if $Y\subseteq X$ and $\varepsilon>0$ we say that $X$ is $\varepsilon$-deformable into $Y$ if there exists a continuous mapping $\varphi\colon X\times [0,1]\to X$ such that $\varphi(x,0)=x$, $\varphi(x,1)\in Y$ and the diameter of $\varphi(\{x\}\times[0,1])$ is at most $\varepsilon$ for every $x\in X$.
The following proposition was proved in \cite[1.1 and 1.3]{Krasinkiewicz}.

\begin{proposition}\label{AR}
Let $X$ be a compact space such that for every $\varepsilon>0$ there exists an absolute neighborhood retract (absolute retract) $Y\subseteq X$ for which $X$ is $\varepsilon$-deformable into $Y$. Then $X$ is an absolute neighborhood retract (absolute retract, resp.).
\end{proposition}

Some of the ideas for the proof of the following comes from the paper \cite{KrupskiVejnar}.

\begin{theorem}\label{Hilbert}
The conjugacy of Hilbert cube homeomorphisms (or selfmaps) is Borel bireducible to $E_{G_\infty}$.
\end{theorem}

\begin{figure}
\begin{tikzpicture}[line cap=round,line join=round,>=triangle 45,x=2.0cm,y=2.0cm]
\clip(-0.8870230685673408,-1.0495897586754248) rectangle (6.689259282742075,2.8063219870557705);
\fill[line width=0.4pt,fill=black,fill opacity=0.10000000149011612] (1.5,1.) -- (1.7,1.) -- (1.6,1.4) -- cycle;
\fill[line width=0.4pt,fill=black,fill opacity=0.10000000149011612] (2.2,1.) -- (2.4,1.) -- (2.3,1.4) -- cycle;
\fill[line width=0.4pt,fill=black,fill opacity=0.1] (1.1,0.6) -- (1.2,0.6) -- (1.1516705507080174,0.7973955765263389) -- cycle;
\fill[line width=0.4pt,fill=black,fill opacity=0.1] (1.4015873351160641,0.6) -- (1.501587335116064,0.6034837273061294) -- (1.4532578858240814,0.8008793038324683) -- cycle;
\fill[line width=0.4pt,fill=black,fill opacity=0.1] (1.7055408494552977,0.6034837273061294) -- (1.8055408494552976,0.6034837273061294) -- (1.757211400163315,0.8008793038324683) -- cycle;
\fill[line width=0.4pt,fill=black,fill opacity=0.1] (0.702161987805911,0.20130445208116723) -- (0.8021619878059107,0.20130445208116723) -- (0.752959293246011,0.30131164716636394) -- cycle;
\fill[line width=0.4pt,fill=black,fill opacity=0.1] (0.9021763779763046,0.19971703628616413) -- (1.0021763779763042,0.19971703628616413) -- (0.9497988518263981,0.2997242313713608) -- cycle;
\fill[line width=0.4pt,fill=black,fill opacity=0.1] (1.1053655997367042,0.20289186787617036) -- (1.205365599736704,0.20289186787617036) -- (1.1514006577917946,0.2981368155763577) -- cycle;
\fill[line width=0.4pt,fill=black,fill opacity=0.1] (1.3037925741120944,0.20130445208116723) -- (1.4037925741120942,0.20130445208116723) -- (1.349827632167185,0.2981368155763577) -- cycle;
\draw [line width=0.4pt] (0.,0.)-- (2.,0.);
\draw [line width=0.4pt] (0.,-1.)-- (2.,-1.);
\draw [line width=0.4pt] (0.,0.)-- (0.,-1.);
\draw [line width=0.4pt] (2.,0.)-- (2.,-1.);
\draw [line width=0.4pt] (2.,2.)-- (4.,2.);
\draw [line width=0.4pt] (2.,2.)-- (0.,0.);
\draw [line width=0.4pt] (4.,2.)-- (2.,0.);
\draw [line width=0.4pt] (4.,2.)-- (4.,1.);
\draw [line width=0.4pt] (4.,1.)-- (2.,-1);
\draw [line width=1.2pt] (0.5,0.)-- (1.5,0.);
\draw [line width=0.4pt] (1.5,1.)-- (1.7,1.);
\draw [line width=0.4pt] (1.7,1.)-- (1.6,1.4);
\draw [line width=0.4pt] (1.6,1.4)-- (1.5,1.);
\draw [line width=0.4pt] (2.2,1.)-- (2.4,1.);
\draw [line width=0.4pt] (2.4,1.)-- (2.3,1.4);
\draw [line width=0.4pt] (2.3,1.4)-- (2.2,1.);
\draw [line width=0.4pt] (1.1,0.6)-- (1.2,0.6);
\draw [line width=0.4pt] (1.2,0.6)-- (1.1516705507080174,0.7973955765263389);
\draw [line width=0.4pt] (1.1516705507080174,0.7973955765263389)-- (1.1,0.6);
\draw [line width=0.4pt] (1.4015873351160641,0.6034837273061294)-- (1.501587335116064,0.6034837273061294);
\draw [line width=0.4pt] (1.501587335116064,0.6034837273061294)-- (1.4532578858240814,0.8008793038324683);
\draw [line width=0.4pt] (1.4532578858240814,0.8008793038324683)-- (1.4015873351160641,0.6034837273061294);
\draw [line width=0.4pt] (1.7055408494552977,0.6034837273061294)-- (1.8055408494552976,0.6034837273061294);
\draw [line width=0.4pt] (1.8055408494552976,0.6034837273061294)-- (1.757211400163315,0.8008793038324683);
\draw [line width=0.4pt] (1.757211400163315,0.8008793038324683)-- (1.7055408494552977,0.6034837273061294);
\draw [line width=0.4pt] (0.702161987805911,0.20130445208116723)-- (0.8021619878059107,0.20130445208116723);
\draw [line width=0.4pt] (0.8021619878059107,0.20130445208116723)-- (0.752959293246011,0.30131164716636394);
\draw [line width=0.4pt] (0.752959293246011,0.30131164716636394)-- (0.702161987805911,0.20130445208116723);
\draw [line width=0.4pt] (0.9021763779763046,0.19971703628616413)-- (1.0021763779763042,0.19971703628616413);
\draw [line width=0.4pt] (1.0021763779763042,0.19971703628616413)-- (0.9497988518263981,0.2997242313713608);
\draw [line width=0.4pt] (0.9497988518263981,0.2997242313713608)-- (0.9021763779763046,0.19971703628616413);
\draw [line width=0.4pt] (1.1053655997367042,0.20289186787617036)-- (1.205365599736704,0.20289186787617036);
\draw [line width=0.4pt] (1.205365599736704,0.20289186787617036)-- (1.1514006577917946,0.2981368155763577);
\draw [line width=0.4pt] (1.1514006577917946,0.2981368155763577)-- (1.1053655997367042,0.20289186787617036);
\draw [line width=0.4pt] (1.3037925741120944,0.20130445208116723)-- (1.4037925741120942,0.20130445208116723);
\draw [line width=0.4pt] (1.4037925741120942,0.20130445208116723)-- (1.349827632167185,0.2981368155763577);
\draw [line width=0.4pt] (1.349827632167185,0.2981368155763577)-- (1.3037925741120944,0.20130445208116723);
\draw[color=black] (-0.15,-0.15) node {$Q$};
\draw[color=black] (2.8,1.5) node {$Q{'}$};
\draw[color=black] (3.4,1.0750956992997227) node {$Q{'}^-$};
\draw[color=black] (1.0339220556696547,-0.15) node {$K$};
\draw[color=black] (2,0.7077712308941867) node {$C^d_n$};
\end{tikzpicture}
\caption{The compactum $Q_K$}
\end{figure}

\begin{proof}
For one direction it is enough to prove that the homeomorphism equivalence relation of metrizable compacta is Borel reducible to conjugacy of Hilbert cube homeomorphisms because the first relation is Borel bireducible to $E_{G_\infty}$ by the main result of \cite{Zielinski}.
To this end let
\begin{align*}
Q&=\{x\in\ell_2\colon 0\leq x_n\leq 1/n\}, \\
Q'&=Q\times I, \\
Q''&=Q\times I\times [-1,1],\\
Q'^-&=Q\times I\times [-1,0]
\end{align*}
and let $\|\cdot\|$ be the usual norm on $\ell_2$.

Let us fix a homotopy $H\colon \mathcal K(Q)\times I\to \mathcal K(Q)$ given by Proposition~\ref{homotopy} for the case $X=Q$.
Let us fix $K\in \mathcal K(Q)$. We want to find a homeomorphism $f_K$ of a Hilbert cube $Q_K\subseteq Q''$ such that the topological information about $K$ is somehow encoded in the dynamics of $f_K$. Let $D_n^K=H(K, 2^{-n})$, $n\in\mathbb N$.
Let $\varepsilon_n$ be the minimum of $1/n$ and the smallest distance of different points in $D_n^K$. For every $d\in D_n^K$
fix a set
\[
B^d_n=\{(x, 2^{-n},0)\in Q''\colon \|d- x\|\leq\varepsilon_n/3\}.
\]
It follows that $B^d_n$ is always homeomorphic to the Hilbert cube since it is affinely homeomorphic to an infinite dimensional compact convex subset of a Hilbert space \cite{Keller}.
Let $C^d_n$ be the cone in $Q''$ with base $B^d_n$ and with the vertex $(d, 2^{-n}, 2^{-n})$, $d\in D_n^K$, $n\in\mathbb N$,
i.e., the union of all segments with end points $(d, 2^{-n}, 2^{-n})$ and $p$, $p\in B^d_n$.
The cone over the Hilbert cube is homeomorphic to the Hilbert cube \cite[Theorem 1.7.5]{vanMill}, which applies to $C^d_n$.
Let $Q_K^m=Q'^-\cup\bigcup\{ C^d_n\colon n\in\mathbb N, n\leq m, d\in D_n^K\}$ and $Q_K=\bigcup\{Q_K^m\colon m\in\mathbb N\}$ (see Figure 1).
By the result of \cite{Anderson} the union of two  Hilbert cubes, whose intersection is a Z-set homeomorphic to the Hilbert cube, is the Hilbert cube again. Hence we inductively obtain that all the spaces $Q_K^m$ are homeomorphic to the Hilbert cube. Moreover, for every $\varepsilon>0$, $Q_K$ is $\varepsilon$-deformable onto $Q^m_K$ for some $m$ and hence $Q_K$ is an AR by Proposition \ref{AR}. Moreover $Q_K$ has the disjoint cell property (see \cite[p. 294]{vanMill}) and thus $Q_K$ is homeomorphic to the Hilbert cube by the famous Toru\'nczyk's theorem \cite[Theorem 4.2.25]{vanMill}.

Let $h(x)=\sqrt{x}, x\in I$ or any fixed homeomorphism of $I$ with two fixed points $0,1$; and $1$
being a locally attracting fixed point. We define
\[f_K(x)=\begin{cases}x, &x\in Q',
\\
((1-h(t))a+h(t)d, 2^{-n}, 2^{-n} h(t)), &
\begin{matrix}
x=((1-t)a+td, 2^{-n}, 2^{-n}t)\in C^d_n,\\
d\in D_n^K,t\in I, n\in\N.
\end{matrix}
\end{cases}\]

All the points in $Q'$ are fixed points for $f_K$ and these are clearly not attracting.
All the points in $\bigcup D_n^K$ are fixed points of $f_K$ and these are attracting. There are no other fixed points of $f_K$.
It follows that $K$ is homeomorphic (or even equal) to the set of fixed points that are limits of attracting points but not attracting by itself (and thus defined only by dynamical notions). Hence if $f_K$ and $f_L$ are conjugate then $K$ and $L$ are homeomorphic, $K, L\in \mathcal K(Q)$.

On the other hand if $K, L$ are homeomorphic compacta in $Q$ then the sets $K\cup \bigcup_{n\in\mathbb N}D_n^K\times \{2^{-n}\}$ and $L\cup\bigcup_{n\in\mathbb N}D_n^L\times \{2^{-n}\}$ are homeomorphic by Lemma~\ref{extension}. This homeomorphism can be simply extended to a homeomorphism
\[\varphi\colon (K\times \{0\})\cup \bigcup\{B^d_n(K)\colon d\in D_n^K, n\in\mathbb N\} \to (L\times\{0\})\cup \bigcup \{B^d_n(L)\colon d\in D_n^L, n\in\mathbb N\}.\]
Both the sets in the domain and range of $\varphi$ are $Z$-sets in $Q'^-$ since these are closed subsets of the $Z$-set $Q'\times\{0\}$ \cite[Lemma 5.1.2, Corollary 5.1.5]{vanMill}. Hence $\varphi$ can be extended to a homeomorphism $\varphi'\colon Q'\to Q'$ \cite[Theorem 5.3.7]{vanMill}.
It remains to extend $\varphi'$
linearly on the cones to obtain a homeomorphism $\varphi''$.
It follows that $\varphi''$ conjugates $f_K$ and $f_L$.
To verify that the mapping $\mathcal K(Q)\to \mathcal K(Q''\times Q'')$, $K\mapsto f_K$ is Borel
is straightforward and it is left to the reader.

To conlude the proof it is enough to Borel reduce conjugacy of Hilbert cube maps to $E_{G_\infty}$. Consider structures of the form $(Q, R)$ where $R$ is a closed binary relation on $Q$. Two such structures $(Q, R)$ and $(Q, S)$ are said to be isomorphic if there is a homeomorphisms $\psi\colon Q\to Q$ for which $(\psi\times\psi)(R)=S$.
By a fairly more general result \cite{RosendalZielinski} it follows that such isomorphism equivalence relation is Borel reducible to $E_{G_\infty}$.
There is a Borel (even continuous) reduction which takes a continuous map $f\colon Q\to Q$ and assigns $(Q, \text{graph}(f))$ to it. Combining the two reductions we get the desired one.
\end{proof}

\section{Concluding remarks and questions}

Let us summarize some of the results on the complexity of conjugacy equivalence relation in Table~1 in which we consider conjugacy equivalence relation of
maps, homeomorphisms, and pointed transitive homeomorphisms of the
arc,  circle,  Cantor set and Hilbert cube, respectively.
Let us recall that a \emph{pointed dynamical system} is a triple $(X, f, x)$, where $(X, f)$ is a dynamical system and $x\in X$. We say, that a pointed dynamical system $(X, f, x)$ is \emph{transitive} if the forward orbit of $x$ in $(X, f)$ is dense.
Two pointed dynamical systems $(X, f, x)$ and $(Y, g, y)$ are called \emph{conjugate} if there is a conjugacy of $(X,f)$ and $(Y, g)$ mapping $x$ to $y$.
We proceed by a series of simple notes as comments on Table~\ref{table}.

\begin{table}[h]
\centerline{
\begin{tabular}{ r  l  l }
\hline
& Homeomorphisms/maps & Pointed transitive homeomorphisms
\\
\hline
Arc  & $E_{S_\infty}$ \cite{Hjorth}, Theorem \ref{bireducible}  & $\emptyset$ Note \ref{arc}     \\
Circle   & $E_{S_\infty}$ Note \ref{circle} & $E_=$ Note \ref{circlepointed}  \\
Cantor set  & $E_{S_\infty}$ \cite{CamerloGao} & $E_{=^+}$ \cite{Kaya}, Note \ref{Cantor}  \\
Hilbert cube  & $E_{G_\infty}$ Theorem \ref{Hilbert} & ? Question \ref{question} \\
\hline
\end{tabular}
}
\caption{The complexity of conjugacy equivalence relation.}
\label{table}
\end{table}

\begin{note}
Conjugacy of pointed transitive maps of the interval is smooth; indeed it is enough to assign to every pointed transitive dynamical system $(I, f, x)$ the $\N\times\N$ matrix of true and false: $(f^m(x)<f^n(x))_{m, n\in\mathbb N}$ which determines $f$ uniquely up to increasing conjugacy.
\end{note}

\begin{note}\label{arc}
There are no transitive homeomorphisms on the arc.
\end{note}

\begin{note}\label{circle}
The complexity result by Hjorth \cite[Section 4.2]{Hjorth} that conjugacy of interval homeomorphisms is Borel bireducible to $E_{S_\infty}$, remains true for circle homeomorphisms simply by a modification of the original proof. A modification of the proof of Theorem \ref{bireducible2} for circle maps is also possible and thus conjugacy of circle  homeomorphisms is Borel bireducible to the $S_\infty$-universal orbit equivalence relation.
\end{note}

\begin{note}\label{circlepointed}
Transitive homeomorphisms of the circle are well known to be conjugate to irrational rotations. Hence the rotation number is a complete invariant and hence conjugacy of (pointed) transitive homeomorphisms of the circle is Borel bireducible to the equality on irrationals (or on an uncountable Polish space).
\end{note}

\begin{note}\label{Cantor}

By a result of Kaya \cite{Kaya}, conjugacy of pointed minimal homeomorphisms of the Cantor set is Borel bireducible to the equality of countable sets $E_{=^+}$. Note that his proof works in the same vein for pointed transitive homeomorphisms of the Cantor set.
Let us recall the main part of his construction in this case. Let $X$ be the Cantor set and $\mathcal B$ the collection of all clopen sets in $X$.  To a pointed transitive system $(X, f, x)$ we assign the collection
\[\mathsf{Ret}(f, x)=\{\mathsf{Ret_B}(f, x)\colon B\in\mathcal B\},\]
where $\mathsf{Ret_B}(f, x)=\{n\in\Z\colon f^n(x)\in B\}$.
It can be verified that the mapping $\Phi$ defined as
\[\Phi(f, x)=(\mathsf{Ret_B}(f, x)\colon B\in\mathcal B)\in \mathcal P(\Z)^{\mathcal B}\]
is a reduction of pointed transitive Cantor maps to the equality of countable sets in $\mathcal P(\Z)^{\mathcal B}$,
i.e., $(f,x)$ is conjugate to $(g, y)$ if and only if $\mathsf{Ret}(f,x)=\mathsf{Ret}(g,y)$.
\end{note}

The following question is the missing part to complete Table~\ref{table}.

\begin{question}\label{question}
What is the complexity of conjugacy of transitive pointed Hilbert cube homeomorphisms (or maps)?
\end{question}

The most natural candidate for the complexity of conjugacy of transitive pointed Hilbert cube homeomorphisms (or maps) is the universal orbit equivalence relation.

Since triangular maps i.e., maps $f\colon I^2\to I^2$ of the form $f(x,y)=(g(x), h(x,y))$ for continuous
maps $g\colon I\to I$ and $h\colon I^2\to I$,
lie in between one-dimensional and two dimensional and there is a gap in the complexity of the last
two mentioned equivalence relations, the following question is natural.

\begin{question}
What is the complexity of conjugacy of triangular maps?
Is it Borel bireducible to $E_{S_\infty}$ or to $E_{G_\infty}$?
\end{question}

Positive answer to the next question would provide a strengthening of Theorem~\ref{bireducible2}.

\begin{question}
Is conjugacy of closed binary relations on the closed interval Borel reducible to the $S_\infty$-universal orbit equivalence relation?
\end{question}

The answer to the preceding question is affirmative if Hjorth's conjecture is true.

\bibliography{citace}
\end{document}


TITLE: Poisson distribution formula
QUESTION [0 upvotes]: The formula $\frac{\lambda^x\cdot e^{-\lambda}}{x!}$ represents a probability, so it is clearly less than or equal to 1. But this is not immediately clear from the formula itself. Is there an easy way of proving this fact?
Thnx

REPLY [0 votes]: Sum over $k$ ($x$ in your case) and obtain $1$. Clearly each term $\frac{e^{-\lambda} \lambda^k}{k!}>0$. If at most one out of infinite set of terms was greater than 1, the sum would be greater that 1. From this it follows that $0<\frac{e^{-\lambda} \lambda^k}{k!}<1$.


TITLE: a function with infinity L^p norm
QUESTION [3 upvotes]: Let $1\leq p<\infty$, $1/p+1/q=1$. For a function $f$ with $||f||_q=\infty$, can we write
$$
||f||_q=\sup_{g\in L^p(\Omega),||g||_p\neq 0}\frac{\int_\Omega |fg|}{||g||_p}?
$$
or
$$
||f||_q=\sup_{||g||_p\leq 1}{\int_\Omega |fg|}?
$$
In the case $||f||_q<\infty$, since $L^q(\Omega)$ is the dual space of $L^p(\Omega)$, with the $L^q$ norm equal to the norm of the bounded linear functional on $L^p$,  we have
$$
||f||_q=\sup_{||g||_p=1}{\int_\Omega |fg|}=\sup_{||g||_p\leq 1}{\int_\Omega |fg|}=\sup_{g\in L^p(\Omega),||g||_p\neq 0}\frac{\int_\Omega |fg|}{||g||_p}.
$$
Thanks.

REPLY [2 votes]: This is only true if you assume that $f$ vanishes outside a $\sigma$-finite set. For a counterexample, consider the measure space $X = \{1, 2\}$ with the measure $\mu$ defined on the power set of $X$ by $\mu(\emptyset) = 0$ and $\mu(\{1\}) = 1$ and $\mu(\{2\}) = \mu(X) = \infty$.
Then for any $g \in L^p (\Omega)$, we see that $g(2) = 0$. If we thus take $f$ defined by $f(2) = 1$ and $f(1) = 0$, then the right-hand side of your equality vanishes, but $\Vert f \Vert_p = \infty$.
So let us assume that $f \equiv 0$ on $\left(\bigcup_n M_n\right)^c$, where the $M_n$ have finite measure. By taking $M_n ' := \bigcup_{j=1}^n M_n$, we can assume w.l.o.g. that $M_n \subset M_{n+1}$ for all $n$.
Let us assume that the right-hand side is finite, i.e.
$$
C := \sup_{\Vert g \Vert_p \neq 0} \frac{\int_\Omega |f \cdot g|}{\Vert g \Vert_p} < \infty.
$$
We will show that in this case also $\Vert f \Vert_q$ is finite. By contraposition, this proves your claim.
Now set $$K_n := \{x \mid |f(x)| \leq n\} \cap M_n.$$
Note that $K_n \subset K_{n+1}$ for all $n$ and $\bigcup_n K_n = \bigcup_n M_n$, so that $f$ vanishes on the complement of $\bigcup_n K_n$.
If we set $f_n := f \cdot \chi_{K_n}$, where $\chi_M$ denotes the indicator function of the set $M$, we get $f_n \rightarrow f$ pointwise as $n \rightarrow \infty$. It thus suffices (by Fatou's Lemma) to show that $\Vert f_n \Vert_q \leq C$ for all $n$.
To prove this, note that $f_n$ is bounded (by $n$) and vanishes outside a set of finite measure, so that $f_n \in L^q$. We can thus apply your characterization to conclude
$$
\Vert f_n \Vert_q = \sup_{\Vert g \Vert_p \neq 0} \frac{\int_\Omega |f_n \cdot g|}{\Vert g \Vert_p} = \sup_{\Vert g \Vert_p \neq 0} \frac{\int_\Omega |f \cdot (g \cdot \chi_{K_n})|}{\Vert g \Vert_p} \leq \sup_{\Vert g \Vert_p \neq 0} \frac{C \cdot \Vert g \cdot \chi_{K_n}\Vert_p}{\Vert g \Vert_p} \leq C.
$$
Here, I used $\Vert g \cdot \chi_{K_n} \Vert_p \leq \Vert g \Vert_p$ in the last step and the definition of $C$ in the step before that.


TITLE: Closed form for $\sum_{n=0}^\infty\frac{\operatorname{Li}_{1/2}\left(-2^{-2^{-n}}\right)}{\sqrt{2^n}}$
QUESTION [23 upvotes]: Let
$$S=\sum_{n=0}^\infty\frac{\operatorname{Li}_{1/2}\left(-2^{-2^{-n}}\right)}{\sqrt{2^n}},\tag1$$
where $\operatorname{Li}_a(z)$ is the polylogarithm. For $a=1/2$ it can be represented as
$$\begin{align}\operatorname{Li}_{1/2}(z)&=\sum_{k=1}^\infty\frac{z^k}{\sqrt k}\tag2\\&=\int_0^\infty\frac z{\sqrt{\pi\,x}\ \left(e^x-z\right)}\,dx.\tag3\end{align}$$

How to find a closed-form expression for $S$?

REPLY [30 votes]: Result:
$$\boxed{\; S=\sqrt{2}\,\operatorname{Li}_{1/2}\left(\frac14\right)-\sqrt{\displaystyle\frac{\pi}{\ln 2}}\;}\tag{1}$$

Derivation:

Let us denote
$$a_n=\frac{\operatorname{Li}_{1/2}\left(-2^{-2^{-n}}\right)}{2^{n/2}},
\qquad
b_n=\frac{\operatorname{Li}_{1/2}\left(2^{-2^{-n}}\right)}{2^{n/2}}.$$
These quantities satisfy the recurrence relation
$$a_n+b_n=b_{n-1},\tag{2}$$
which follows from the identity
$$\sqrt{2}\,\operatorname{Li}_{1/2}\left(z^2\right)=
\operatorname{Li}_{1/2}\left(z\right)+\operatorname{Li}_{1/2}\left(-z\right).$$
The relation (2) implies that
$$b_N+\sum_{n=0}^Na_n=b_{-1},$$
and therefore our series telescopes:
$$S=\sum_{n=0}^{\infty}a_n=b_{-1}-b_{\infty}.\tag{3}$$
The polylogarithm asymptotics
$$\operatorname{Li}_{1/2}(x)\sim\frac{\sqrt{\pi}}{\sqrt{1-x}}\quad \text{as}\;\;
x\rightarrow 1^-,$$
implies that $\displaystyle b_{\infty}=\sqrt{\frac{\pi}{\ln 2}}$. Being combined with (3), this finally gives the above answer (which is further confirmed numerically).


TITLE: Why does a system try to minimize its total energy?
QUESTION [66 upvotes]: Why does a system like to minimize its total energy? For example, the total energy of a $H_2$ molecule is smaller than the that of two two isolated hydrogen atoms and that is why two $H$ atoms try to form a covalent bond. According to the classical mechanics, it is the potential energy of a conservative system that is minimum in equilibrium, not the total energy.

REPLY [1 votes]: Energy is a secondary concept, at least in Newtownian mechanics, so let's start with the fundamentals.
There exists a force field. A gravitational one, say. An object in this field feels a force. This force "wants" to make the object accelerate.
From forces, define work as $force \times distance$ and now we can give precise mathematical meaning to the intuitive concept that "it takes work to lift this ball from the floor to the table".
From work, define energy. Energy is how we keep track of all the work that we did. When we say "the ball has $x$ Joules of kinetic energy" that's a way of saying "some force acted upon the ball, doing $x$ much work, and now because of that force the ball has accelerated to the given velocity".
So let's answer the question: "why does a system like to minimize its total energy?" First we have to clarify the question, we have to nitpick about what "the system" is because when lifting a ball from the floor to the table I have apparently increased its energy, contradicting the premise. I think you mean "why does a system like to minimise its potential energy?" Potential energy exists because the force exists -- the ball potentially will fall back to the floor, if it is allowed to; gravity will do work on the ball as it falls and this will manifest as kinetic energy. So saying "the ball wants to minimise its potential energy" is basically saying "the force of gravity exists".
But if the ball actually is allowed to fall, we're trading potential energy for kinetic energy, and the total energy of the system is constant. If it bounces with perfect elasticity and there is no air resistance etc, it will return to its initial configuration: no energy change. In practice, the bounce will be slightly elastic, work will be done agitating the molecules into motion (heat, sound, etc) and so not all the energy will be returned to the ball in the bounce, so the energy of the (no longer closed) system will tend to decrease.