\section{Introduction}

There are several computational problems in braid groups that have been proposed for their potential applications to cryptography \cite{DehornoySurvey}. Initially, the conjugacy problem in the braid group~$\mathbb B_n$ was proposed as a non-commutative alternative to the discrete logarithm problem \cite{AnshelAnshelGoldfeld, Coreanos}. Later, some other problems were proposed, including the $k$-th root extraction problem: given $x\in \mathbb B_n$ and an integer $k>1$, find $a\in \mathbb B_n$ such that $a^k=x$.

The interest of braid groups for cryptography has decreased considerably, mainly due to the appearance of algorithms which solve the conjugacy problem extremely fast in the generic case \cite{Gebhardt, GebhardtGM-Sliding1, GebhardtGM-Sliding2}. The main problem with the proposed cryptographic protocols turns out to be the key generation. Public and secret keys are chosen `at random', and this implies that the protocols are insecure against algorithms which have a fast generic-case complexity.

While the future of braid-cryptography depends on finding a good key-generation procedure, there are some other problems in braid groups whose generic-case complexity is still to be studied. This is the case of the $k$-th root (extraction) problem.

A priori, the study of the generic case for the $k$-th root problem could be though to be nonsense as, generically, the $k$-th root of a braid~$x$ does not exist. But we should think of the braid~$x$ as the $k$-th power of a generic braid: in protocols based on this problem, a secret braid~$a$ is chosen at random, and the braid $x=a^k$ is made public. Hence we are dealing with braids for which a $k$-th root is known to exist. In any case, the algorithm in this paper not only shows that root extraction in braid groups is generically very fast, but can also be used by those mathematicians needing a simple algorithm for finding a $k$-th root of a braid (or proving that it does not exist), which works in most cases.

There are already known algorithms to solve the $k$-th root problem in braid groups and, more generally, in Garside groups \cite{Sibert, Lee}. But these algorithms can be simplified a lot in the generic case, as we will show in this paper.

The plan of this paper is as follows. In \autoref{preliminaries} we provide the necessary tools to describe the situation and attack the problem. Then in \autoref{section_root}, we prove the theoretical results needed for our proposed algorithm, which is given in \autoref{section_algorithm}, together with the study of its generic-case complexity.

This generic-case complexity turns out to be quadratic on the canonical length~$l$ of the braid, if the number~$n$ of strands is fixed. More precisely, the generic-case complexity is $O(l(l+n)n^3\log n)$ (\autoref{maintheorem}).

\section{Preliminaries}\label{preliminaries}

\subsection{Garside structure of $\mathbb B_n$}
A group $G$ is said to be a \textit{Garside group} \cite{DehornoyLibro} if it admits a submonoid~$\mathcal{P}$ (whose elements are called {\it positive}) such that $\mathcal{P}\cap \mathcal{P}^{-1}=\{1\}$, and a special element $\Delta \in \mathcal{P}$, called {\it Garside element}, satisfying the following properties:

\begin{itemize}
 \item The partial order~$\preccurlyeq$ in~$G$ defined by $a \preccurlyeq b$ if $a^{-1}b \in \mathcal{P}$ is a lattice order. If $a\preccurlyeq b$ we say that~$a$ is a {\it prefix} of~$b$. The lattice structure implies that for all $a,b\in G$ there exists a unique meet $a \wedge b$ and a unique join $a \vee b$ with respect to~$\preccurlyeq$.  Notice that this partial order is invariant under left-multiplication.

\item The set of simple elements $\mathcal{S}\coloneqq\{s\in G\,|\, 1\preccurlyeq s \preccurlyeq \Delta  \}$ is finite and generates~$G$.

\item Conjugation by $\Delta$ preserves $\mathcal{P}$, that is, $\Delta^{-1}\mathcal{P} \Delta = \mathcal{P}$.

\item $\mathcal{P}$ is atomic: the atoms are the indivisible elements of~$\mathcal P$ (elements $a\in \mathcal{P}$ for which there is no decomposition $a=bc$ with non-trivial elements $b,c\in\mathcal{P}$). Then, for every $x\in\mathcal{P}$ there is an upper bound on the number of atoms in a decomposition of the form $x=a_1a_2\cdots a_n$, where each~$a_i$ is an atom.
\end{itemize}

One of the main examples of Garside groups is the braid group on $n$~strands, denoted by~$\mathbb{B}_n$. This group has a standard presentation due to Artin \cite{Artin}:
$$
\mathbb{B}_n = \left< \sigma_1, \sigma_2, ... , \sigma_{n-1} \left|\begin{array}{cccc}
\sigma_i\sigma_j\sigma_i = \sigma_j\sigma_i\sigma_j & & &  \mbox{if }  |i-j| = 1 \\
\sigma_i\sigma_j = \sigma_j\sigma_i & & &  \mbox{if }  |i-j| > 1
\end{array}
\right.
\right>.
$$

Attending to the above presentation, a braid is said to be positive if it can be written as a product of positive powers of the generators~$\{\sigma_i\}_{i=1}^n$. The set of positive braids forms the monoid~$\mathcal{P}$ corresponding to the classical Garside structure of~$\mathbb{B}_n$. We will denote this monoid by~$\mathbb{B}_n^+$.

The usual Garside element in~$\mathbb{B}_n^+$, which we denote~$\Delta_n$, is defined recursively setting $\Delta_2=\sigma_1$ and
$$\Delta_n = \Delta_{n-1} \sigma_{n-1}\sigma_{n-2} \cdots \sigma_1,$$
for all $n>2$. We will often write~$\Delta$ and omit the subindex~$n$ when there is no ambiguity.

Consider now the inner automorphism $\tau: \mathbb{B}_n \to \mathbb{B}_n$ determined by~$\Delta$. That is, $\tau(x) = \Delta^{-1}x\Delta$. One can easily show from the presentation of~$\mathbb B_n$ that $\tau(\sigma_i) = \sigma_{n-i}$ for $1 \leq i \leq n-1$. Hence~$\tau$ has order~2 and~$\Delta^2$ is central. In fact, the center of~$\mathbb B_n$ is cyclic, generated by~$\Delta^2$ \cite{Chow}.

The set~$\mathcal S$ of simple elements and the automorphism~$\tau$ will be very important in the sequel.

\subsection{Normal forms, cyclings and decyclings}

It is well-known that Garside groups have solvable word problem, as one can compute a normal form for each element.

Let us first define the \textit{right complement} of a simple element $s\in \mathcal S$ as $\partial(s) = s^{-1} \Delta$. That is, $\partial(s)$~is the only element $t\in \mathcal P$ such that $st=\Delta$. Let us see that $\partial(s)=t$ is also a simple element. Recall that the simple elements are the positive prefixes of~$\Delta$. Since~$\tau$ preserves~$\mathcal P$ (by definition of Garside group), we have that~$\tau(s)$ is positive. Now
$$
  st\tau(s)=\Delta \tau(s) = s \Delta,
$$
hence $t\tau(s)=\Delta$, which implies that~$t$ is a positive prefix of~$\Delta$, that is, $t\in \mathcal S$. It follows that we have a map $\partial:\: \mathcal S \to \mathcal S$. Notice that, by definition, $\partial^2\equiv \tau$.

Given two simple elements $s, t \in \mathcal S$, we say that the decomposition~$st$ is \textit{left weighted} if~$s$ is the biggest possible simple element (with respect to~$\preccurlyeq$) in any decomposition of the element~$st$ as a product of two simple elements. This condition can be restated as $\partial(s) \wedge t = 1$, i.e., $\partial(s)$ and~$t$ have no non-trivial prefixes in common.

\begin{definition}{\rm \cite{ElrifaiMorton, Epsteinetal}}
The \emph{left normal form} of an element $x \in \mathbb{B}_n$ is the unique decomposition $x = \Delta^p x_1 \cdots x_l$ so that $p \in \mathbb{Z}$, $l \geq 0$, $x_i \in \mathcal S\setminus\{1, \Delta\}$ for $i = 1, \ldots, l$, and $x_i x_{i+1}$ is a left weighted decomposition, for $i = 1, \ldots, l-1$.
\end{definition}

Given such a decomposition, we define the \textit{infimum, supremum} and \textit{canonical length} of~$x$ as $\inf(x) = p$, $\sup(x) = p+l$ and $\ell(x) = l$, respectively. Equivalently, the infimum and supremum of~$x$ can be defined as the maximum and minimum integers~$p$ and~$s$ so that $\Delta^p \preccurlyeq x \preccurlyeq \Delta^s$ (see \cite{ElrifaiMorton}).

It is important to notice that conjugation by~$\Delta$ preserves the Garside structure of~$\mathbb B_n$. Hence, if the left normal form of a braid~$x$ is $\Delta^p x_1\cdots x_l$, then the left normal form of~$\tau(x)$ is $\Delta^p \tau(x_1)\cdots \tau(x_l)$. We will make use of this property later.

Garside groups also have solvable conjugacy problem. One of the main tools to solve problems related to conjugacy in braid groups are the summit sets, which are subsets of the conjugacy class of a braid. Throughout this article we are going to use two of them: the {\it super summit set} \cite{ElrifaiMorton} and the {\it ultra summit set} \cite{Gebhardt}. Let us first introduce some concepts:

\begin{definition}
Let $x = \Delta^p x_1 \cdots x_l$ be in left normal form, with $l>0$. Notice that we can write:
$$
 x= \tau^{-p}(x_1) \Delta^p x_2\cdots x_l.
$$
We define the {\it initial factor} of $x$ as $\iota(x) =\tau^{-p}(x_1)$, and the {\it final factor} of $x$ as  $\varphi(x) = x_l$. We can then write:
$$
 x = \iota(x)\Delta^p x_2 \cdots x_l  \, \quad \mbox{ and } \quad \, x =  \Delta^p x_1 \cdots x_{l-1}\varphi(x).
$$
If $l=0$, we set $\iota(x) = 1$ and $\varphi(x) = \Delta$.
\end{definition}

Notice that, as~$\tau^2$ is the identity, we actually have either $\iota(x)=x_1$ if~$p$ is even, or $\iota(x)=\tau(x_1)$ if~$p$ is odd. This happens in braid groups, but not in other Garside groups in which the order of~$\tau$ is bigger.

\begin{definition} {\rm{\cite{ElrifaiMorton}}}
Let $x = \Delta^p x_1 \cdots x_l$ be in left normal form, with $l>0$. The \textit{cycling} and \textit{decycling} of~$x$ are the conjugates of~$x$ defined, respectively, as
$$
 \boldsymbol{\mathrm c}(x) = \Delta^p x_2 \cdots x_l \iota(x) \, \quad \mbox{ and } \quad \, \boldsymbol{\mathrm d}(x) = \varphi(x) \Delta^p x_1 \cdots x_{l-1}.
$$
\end{definition}

Thus~$\boldsymbol{\mathrm c}(x)$ is the conjugate of~$x$ by~$\iota(x)$, and that~$\boldsymbol{\mathrm d}(x)$ is the conjugate of~$x$ by~$\varphi(x)^{-1}$.

Cyclings and decyclings were defined in \cite{ElrifaiMorton} in order to try to simplify the braid~$x$ by conjugations. Usually, if $l\geq 2$, the decomposition $\Delta^p x_2 \cdots x_l \iota(x)$ is {\bf not} the left normal form of~$\boldsymbol{\mathrm c}(x)$. So~$\boldsymbol{\mathrm c}(x)$ could a priori have a shorter normal form (with less factors). A similar situation happens for~$\boldsymbol{\mathrm d}(x)$.

If $\Delta^p x_2 \cdots x_l \iota(x)$ is actually the left normal form of~$\boldsymbol{\mathrm c}(x)$ (when $l\geq 2$), we say that the braid~$x$ is {\it rigid}. This happens if and only if $x_l\iota(x)$ (that is, $\varphi(x)\iota(x)$) is a left weighted decomposition. We can extend this definition to every case, when $l\geq 0$:

\begin{definition}
We say that $x\in \mathbb B_n$ is {\it rigid} if $\varphi(x)\iota(x)$ is a left weighted decomposition.
\end{definition}

If~$x$ is rigid, neither cycling nor decycling can simplify its normal form $x=\Delta^p x_1 \cdots x_l$. Actually, the normal forms of the iterated cyclings of~$x$ are, if~$p$ is even:
$$
    \boldsymbol{\mathrm c}(x)=\Delta^p x_2\cdots x_l x_1, \qquad \boldsymbol{\mathrm c}^2(x)=\Delta^p x_3\cdots x_lx_1x_2, \qquad \ldots
$$
so $\boldsymbol{\mathrm c}^l(x)=x$ in this case. In the case when~$p$ is odd we have:
$$
    \boldsymbol{\mathrm c}(x)=\Delta^p x_2\cdots x_l \tau(x_1), \qquad \boldsymbol{\mathrm c}^2(x)=\Delta^p x_3\cdots x_l\tau(x_1)\tau(x_2), \qquad \ldots
$$
so $\boldsymbol{\mathrm c}^{2l}(x)=x$ in this case.

In the same way, if~$x$ is rigid we have, for~$p$ even:
$$
    \boldsymbol{\mathrm d}(x)=\Delta^p x_l x_1\cdots x_{l-1}, \qquad \boldsymbol{\mathrm d}^2(x)=\Delta^p x_{l-1} x_{l} x_1\cdots x_{l-2}, \qquad \ldots
$$
so $\boldsymbol{\mathrm d}^l(x)=x$ in this case. If~$p$ is odd we get:
$$
   \boldsymbol{\mathrm d}(x)=\Delta^p \tau(x_l) x_1\cdots x_{l-1}, \qquad \boldsymbol{\mathrm d}^2(x)=\Delta^p \tau(x_{l-1}) \tau(x_{l}) x_1\cdots x_{l-2}, \qquad \ldots
$$
so $\boldsymbol{\mathrm d}^{2l}(x)=x$ in this case. We then see that, if~$x$ is rigid, iterated cyclings and decyclings correspond to cyclic permutations of the factors in the normal form of~$x$ (possibly conjugated by~$\Delta$, if~$p$ is odd); moreover, when applied to rigid braids, $\boldsymbol{\mathrm c}$ and~$\boldsymbol{\mathrm d}$ are inverses of each other.

\subsection{Summit sets}

Let now $x\in \mathbb B_n$ be an arbitrary braid (not necessarily rigid). Consider the conjugacy class of~$x$, denoted~$x^{\mathbb{B}_n}$, and write~${\inf}_s(x)$ (resp.~${\sup}_s(x)$) for the maximal infimum (resp. the minimal supremum) of an element in~$x^{\mathbb{B}_n}$. These numbers are known to exist \cite{ElrifaiMorton}, and are called the {\it summit infimum} and the {\it summit supremum} of~$x$, respectively. Set $\ell_s(x)=\sup_s(x)-\inf_s(x)$, the {\it summit length} of~$x$. It is shown in \cite{ElrifaiMorton} that the elements in~$x^{\mathbb B_n}$ having the shortest possible normal form are those whose canonical length is precisely~$\ell_s(x)$, and they coincide with the elements whose infimum and supremum are equal to~$\inf_s(x)$ and~$\sup_s(x)$, respectively. The set formed by these elements is called the \textit{supper summit set} of the braid~$x$:
$$
  SSS(x) = \left\{y \in x^{\mathbb{B}_n} \, | \, \ell(y) = {\ell}_s(x)\right\}= \left\{y \in x^{\mathbb{B}_n} \, | \, \inf(y) = {\inf}_s(x), \, \, \sup(y) = {\sup}_s(x)\right\}.
$$

Starting from~$x$, it is possible to obtain an element in~$SSS(x)$ by applying cyclings and decyclings iteratively. It is known \cite{ElrifaiMorton} that if $\inf(x)<\inf_s(x)$ then the infimum of~$x$ can be increased by iterated cycling. Actually, in this case $\inf(x)<\inf(\boldsymbol{\mathrm c}^k(x))$ for some $k<\frac{n(n-1)}{2}$ (see \cite{BirmanKoLee2}). Hence, every $\frac{n(n-1)}{2}$ iterations either the infimum has increased, or one is sure to have an element whose infimum is the summit infimum.

In the same way, if $\sup(x)>\sup_s(x)$, then the supremum of~$x$ can be decreased by iterated decycling \cite{ElrifaiMorton}, and in that case $\sup(x)>\sup(\boldsymbol{\mathrm d}^k(x))$ for some $k<\frac{n(n-1)}{2}$ \cite{BirmanKoLee2}. Hence, every $\frac{n(n-1)}{2}$ iterations either the supremum has decreased, or we are sure to have an element whose supremum is the summit supremum. Since decycling can never decrease the infimum of an element, it follows that starting with any $x\in \mathbb B_n$ and applying iterated cycling (until summit infimum is obtained) followed by iterated decycling (until summit supremum is obtained) yields an element $y\in SSS(x)$.

The super summit set~$SSS(x)$ is a finite set, but it is usually huge, so smaller subsets of the conjugacy class of~$x$ were defined in order to solve the conjugacy problem of~$x$ more efficiently. Namely, the \emph{ultra summit set} of~$x$, denoted by~$USS(x)$, is a subset of~$SSS(x)$ defined as follows \cite{Gebhardt}:
$$
   USS(x)=\{y\in SSS(x)\,|\,  \boldsymbol{\mathrm c}^m(y)=y \text{ for some } m>0\}.
$$
Since~$SSS(x)$ is finite, the subset~$USS(x)$ is also finite. It is then clear that one obtains an element is~$USS(x)$ by iterated application of cycling, starting from an element in~$SSS(x)$, when a repeated element is obtained. Actually, the whole orbit under cycling of an element in~$USS(x)$ belongs to~$USS(x)$. So~$USS(x)$ is a finite set of orbits under cycling.

Notice that every rigid braid belongs to its ultra summit set, as cylings and decyclings are basically cyclic permutations of its factors. It is shown in \cite{BirmanGebhardtGM1} that, if~$x$ is conjugate to a rigid braid and $\ell_s(x)>1$, then~$USS(x)$ coincides with the set of rigid conjugates of~$x$.

There is actually a simpler way, in the general case, to obtain an element in~$USS(x)$ starting from~$x$. Instead of using cyclings and decyclings, one can use the following single type of conjugation:

\begin{definition}\rm{\cite{GebhardtGM-Sliding1}}
Given $x\in \mathbb B_n$, the {\it cyclic sliding} of~$x$ is defined as $\mathfrak s(x)=\mathfrak p(x)^{-1} x \: \mathfrak p(x)$, where $\mathfrak p(x)=\iota(x)\wedge \partial(\varphi(x))$.
\end{definition}

\begin{theorem}\rm{\cite{GebhardtGM-Sliding1}}
Given $x\in \mathbb B_n$, there are integers $0\leq k<t$ such that $\mathfrak s^k(x)=\mathfrak s^t(x)$. For every such pair of integers, one has $\mathfrak s^k(x)\in USS(x)$.
\end{theorem}

By the above result, one can obtain an element in~$USS(x)$ by iterated cyclic sliding starting form~$x$. Furthermore, if~$x$ is conjugate to a rigid element (this will be the generic situation, as we will see in \autoref{subsection_generic}), iterated cyclic sliding yields the {\it shortest} positive conjugating element from~$x$ to a rigid element.

\begin{theorem}\label{Cyclic_Sliding_fastest_conjugation}\rm{\cite{GebhardtGM-Sliding1}}
Let $x\in \mathbb B_n$ and suppose that~$x$ is conjugate to a rigid braid. Then there is an integer $k>0$ such that~$\mathfrak s^k(x)$ is rigid. Moreover, the conjugating element~$\alpha$ from~$x$ to~$\mathfrak s^k(x)$, that is,
$$
   \alpha = \mathfrak p(x) \: \mathfrak p(\mathfrak s(x))\: \mathfrak p(\mathfrak s^2(x))\cdots \mathfrak p(\mathfrak s^{k-1}(x))
$$
is the smallest positive element (with respect to~$\preccurlyeq$) conjugating~$x$ to a rigid element, meaning that for every positive element~$\beta$ such that $\beta^{-1}x\beta$ is rigid, one has $\alpha\preccurlyeq \beta$.
\end{theorem}

After obtaining one element in~$USS(x)$, it is possible to compute all elements in~$USS(x)$ together with conjugating elements connecting them. In this way, one solves the conjugacy problem in~$\mathbb B_n$, as two elements~$x$ and~$y$ are conjugate if and only if $USS(x)=USS(y)$ or, equivalently, if $USS(x)\cap USS(y)\neq \emptyset$. Then, in order to check whether~$x$ and~$y$ are conjugate, one can compute the whole set~$USS(x)$, and one element $\widetilde y\in USS(y)$. Then, $x$ and~$y$ are conjugate if and only if $\widetilde y\in USS(x)$. By construction, one can even compute a conjugating element from~$x$ to~$y$.

In order to understand the forthcoming proofs in this paper, we will need to describe some conjugating elements connecting the elements of~$USS(x)$.

\begin{definition}\rm{\cite{Gebhardt}}
Let $x \in \mathbb{B}_n$ and $y \in USS(x)$. A simple non-trivial element $s \in \mathcal S$ is said to be a \emph{minimal simple element} for~$y$ if $y^s \in USS(x)$ and $y^t \notin USS(x)$, for every $1 \prec t \prec s$.
\end{definition}

In \cite{Gebhardt}, Gebhardt showed that for any two elements $y,z\in USS(x)$ there exists a sequence
$$
    y=y_1 \stackrel{c_1}{\longrightarrow} y_2 \stackrel{c_2}{\longrightarrow} \cdots \rightarrow y_t \stackrel{c_t}{\longrightarrow} y_{t+1} =z,
$$
where~$c_i$ is a minimal simple element for~$y_i$, and $y_{i+1}=c_i^{-1}y_ic_i$, for $i=1,\ldots,t$. Moreover, he introduced an algorithm to compute all minimal simple elements for a given $y \in USS(x)$. This allows to construct a directed graph~$\Gamma_x$, whose vertices correspond to elements of~$USS(x)$, and whose arrows correspond to minimal simple elements, in such a way that for every minimal simple element~$s$ for~$y$, there is an edge with label~$s$ from~$y$ to $y^s = s^{-1}ys$. By the above discussion, it follows that~$\Gamma_x$ is a connected graph, and this is why~$USS(x)$ can be computed starting with a single vertex, iteratively computing the minimal simple elements corresponding to each known vertex, until all vertices are obtained.

We will later see that, generically, ultra summit sets are really small. Actually, they usually have a very simple structure, that we explain now.

\begin{lemma} \rm{\cite{BirmanGebhardtGM2}}
Let $y \in USS(x)$ with $\ell(y) >0$ and let~$s$ be a minimal simple element for~$y$. Then, $s$~is a prefix of either~$\iota(y)$ or~$\partial(\varphi(y))$, or both.
\end{lemma}

The above lemma allows us to classify the arrows in~$\Gamma_x$ into two groups: a directed edge labelled by~$s$ starting at $y \in USS(x)$ is black (resp. grey), if~$s$ is a prefix of~$\iota(x)$ (resp. of~$\partial(\varphi(y))$). In principle, an edge could be of both colors at the same time (a bi-colored arrow, whose label is a prefix of both~$\iota(x)$ and~$\partial(\varphi(x))$), but not in the case of rigid braids, as $\iota(x)\wedge \partial(\varphi(x))=1$ if~$x$ is rigid. Actually, this is a necessary and sufficient condition:

\begin{lemma}\rm{\cite{BirmanGebhardtGM2}}\label{lemma_rigid_iff}
A braid $y \in USS(x)$ with $\ell(y) >0$ is rigid if and only if none of the edges starting at~$y$ is bi-colored.
\end{lemma}

\begin{definition}\label{def_USSminimal}
Given a braid $x\in \mathbb{B}_n$, its associated~$USS(x)$ is \emph{minimal} if $\ell_s(x)>1$ and, for every vertex~$y$ in the graph~$\Gamma_x$, there are exactly two directed edges starting at~$y$, a black one labeled~$\iota(y)$ and a grey one labeled~$\partial(\varphi(y))$. \end{definition}

Notice that, as a consequence of \autoref{lemma_rigid_iff}, if~$USS(x)$ is minimal then all elements in $USS(x)$ are rigid. Moreover, the arrow labeled~$\iota(y)$ corresponds to a cycling of~$y$, and the arrow labeled~$\partial(\varphi(y))$ corresponds to a {\it twisted decycling} of~$y$, meaning a decycling followed by the automorphism~$\tau$. This implies that, if~$USS(x)$ is minimal, the elements of~$USS(x)$ are obtained from~$y$ by applying~$\boldsymbol{\mathrm c}$ and~$\tau\circ \boldsymbol{\mathrm d}$ in every possible way. Since~$y$ is rigid, cyclings and decyclings basically correspond to cyclic permutations of the factors. Therefore, if~$USS(x)$ is minimal, it consists of either two orbits under cycling (conjugate to each other by~$\Delta$), or one orbit under cycling (conjugate to itself by~$\Delta$). If the infimum of~$y$ is even, the orbit of~$y$ has at most $\ell (y) = \ell_s(x)\leq \ell(x)$ elements, so the size of~$USS(x)$ is at most~$2\ell(x)$. If the infimum of~$y$ is odd, the orbit of~$y$ has at most $2\ell(y)\leq 2\ell(x)$ elements, and it is conjugate to itself by~$\Delta$, so it is the only orbit. Therefore, in any case, if~$USS(x)$ is minimal it has at most~$2\ell(x)$ elements.
\\

\begin{remark}\label{checking_minimal} In order to see whether $USS(x)$ is minimal, one should a priori check the condition in \autoref{def_USSminimal} for every element in $USS(x)$. But it is actually shown in \cite[Theorem~4.6]{GMValladares} that, given $y\in USS(x)$, the set~$USS(x)$ is minimal if and only if $\ell(y)>1$ and the minimal simple elements for~$y$ are precisely~$\iota(y)$ and~$\partial(\varphi(y))$. Hence, one just needs to compute the minimal elements for a single arbitrary element $y \in USS(x)$.
\end{remark}

Let us see that this case, in which $USS(x)$ is so small and has such a simple structure, is generic.

\subsection{Generic braids}\label{subsection_generic}

Since~$\mathbb B_n$ is an infinite set, it is necessary to explain what we mean by `picking a random braid' or by saying that a braid is `generic'. Even if we fix the subset of braids of a given length, we must specify if we choose braids from the subset with a uniform distribution, or if we pick braids by choosing a random walk in the Cayley graph, which are the two usual situations.

We will consider the Cayley graph of the braid group~$\mathbb{B}_n$, taking as generators the simple braids, and assume that each edge of the Cayley graph has length~1, so it becomes a metric space. Let us point out that left normal forms of braids are closely related to geodesics in this Cayley graph \cite{Charney}.

Now let~$B(r)$ denote the ball of radius~$r$ centered at the trivial braid~$1$. As the number of simple braids is finite, the set~$B(r)$ is a finite subset of~$\mathbb B_n$. We will consider the uniform distribution within this set. It turns out that `most' elements in~$B(r)$ have a very simple ultra summit set:

\begin{theorem}\rm{\cite{GMValladares}}
The proportion of braids in~$B(r)$ whose ultra summit set is minimal tends to~$1$ exponentially fast, as~$r$ tends to infinity.
\end{theorem}

This is why we can say that the ultra summit set of a `generic braid' is minimal. Moreover, the above result was obtained by refining the following theorem, which gives some important information concerning the elements in~$B(r)$. We have simplified the statement to adapt it to our situation:

\begin{theorem}\rm{\cite{CarusoWiest}}\label{teoCarusoWiest}
The proportion of braids~$x$ in~$B(r)$ which are conjugate to a rigid braid $y=\alpha^{-1} x \alpha$, in such a way that~$\alpha$ is a positive braid with $\ell(\alpha)<\ell(x)$, tends to~$1$ exponentially fast, as~$r$ tends to infinity.
\end{theorem}

Therefore, not only generic braids have minimal ultra summit sets (made of rigid braids), but one can also obtain a rigid conjugate of a generic braid~$x$ very fast, applying iterated cyclic sliding to~$x$. By \autoref{Cyclic_Sliding_fastest_conjugation}, the obtained conjugating element will be the smallest possible positive conjugator, so its canonical length will be smaller than~$\ell(x)$. Once that a rigid conjugate~$y$ (which belongs to~$USS(x)$) is obtained, one can compute the whole~$USS(x)$ very fast, as it consists of at most~$2\ell(x)$ elements, connected by cyclings and twisted decyclings. This is why solving the conjugacy problem in braid groups is generically very fast.

We will also be interested in the centralizer~$Z(x)$ of a braid~$x$. Notice that if $y=\alpha^{-1}x\alpha$, then $Z(y)=\alpha^{-1} Z(x)\alpha$. Therefore, knowing~$Z(y)$ is equivalent to knowing~$Z(x)$, via~$\alpha$. We will then be interested in~$Z(y)$ for $y\in USS(x)$.

\begin{definition}\label{defPC}
Let $x \in \mathbb B_n$ and $y\in USS(x)$, and let~$t$ be the smallest positive integer such that $\boldsymbol{\mathrm c}^t(y) = y$. Denote $p_i:=\iota(\boldsymbol{\mathrm c}^{i-1}(y))$ the positive element conjugating~$\boldsymbol{\mathrm c}^{i-1}(y)$ to~$\boldsymbol{\mathrm c}^{i}(y)$, for $i=1,\ldots,t$. Then the \textit{preferred cycling conjugator} of~$y$ is defined as
\[
  PC(y) = p_1 p_2 \cdots p_t.
\]
In other words, $PC(y)$~corresponds to the conjugating element along the whole cycling orbit of~$y$. By construction, $PC(y)$ commutes with~$y$.
\end{definition}

In the generic case (when~$USS(x)$ is minimal), it turns out that~$Z(x)$ is isomorphic to~$\mathbb Z^2$, and one can describe the generators of~$Z(y)$ for any $y\in USS(x)$ (and thus of~$Z(x)$) in a very explicit way:

\begin{theorem}\rm{\cite{GMValladares}}\label{teoJuanLoles}
Let $x\in \mathbb{B}_n$ and $y\in USS(x)$. Let $PC(y)=p_1\cdots p_t$ as above. If~$USS(x)$ is minimal, then all elements in~$USS(x)$ are rigid, $Z(x)\simeq Z(y) \simeq \mathbb Z^2$, and one of the following conditions holds:
\begin{itemize}
\item[(i)] $USS(x)$ has two orbits under cycling, conjugate to each other by~$\Delta$, and $Z(y) = \langle \Delta^2, PC(y)\rangle$.
\item[(ii)] $USS(x)$ has one orbit under cycling, conjugate to itself by~$\Delta$, and:
	\begin{itemize}
		\item If $\tau(y) = y$, then $Z(y) = \langle \Delta, PC(y) \rangle$.
		\item If $\tau(y) \neq y$, then~$t$ is even and $Z(y) = \langle \Delta^2, \: p_1 \cdots p_{\frac{t}{2}}\Delta^{-1} \rangle$.
	\end{itemize}
\end{itemize}
\end{theorem}

\section{$k$-th root problem}\label{section_root}

Now we come to the central problem in this paper: given $x\in \mathbb B_n$ and an integer $k>1$, find a $k$-th root of~$x$. In other words, we want to either find $a\in \mathbb B_n$ such that $a^k=x$, or show that such a braid does not exist.

Notice that if $a^k=x$ then~$a$ belongs to~$Z(x)$, the centralizer of~$x$. It is interesting to know that finding a single solution~$a$ to the $k$-th root equation is basically the same as finding all possible solutions, as the complete set of solutions coincides with the conjugacy class of~$a$ in~$Z(x)$:

\begin{proposition}\label{roots_are_conjugate_in_Z(x)}
Let $a,x\in \mathbb B_n$ be such that $a^k=x$ for some integer $k>1$. Then the set $\sqrt[k]{x}$ of $k$-th roots of $x$ is precisely
$$
    \sqrt[k]{x}= a^{Z(x)}=\left\{b\in \mathbb B_n \, | \, \ b=u^{-1}au,\ u\in Z(x) \right\}.
$$
\end{proposition}

\begin{proof}
In \cite{GM-roots}, the second author proved that the $k$-th root of a braid is unique, up to conjugacy. That is, if $a,b\in \mathbb B_n$ satisfy $a^k=b^k=x$, then $a=u^{-1}bu$ for some $u\in \mathbb B_n$. Then one has $x= b^k = u^{-1} a^k u =u^{-1} x u$, and hence $u\in Z(x)$. This proves that $\sqrt[k]{x}\subset a^{Z(x)}$.

On the other hand, if $b=a^{Z(x)}$ and we write $b=u^{-1}au$ for some $u\in Z(x)$, we have $b^k=u^{-1}a^k u = u^{-1} x u = x$, so $b\in \sqrt[k]{x}$.
\end{proof}

Observe that $a^k=x$ if and only if  $(\alpha^{-1}a\alpha)^k=\alpha^{-1}x\alpha$ for any $\alpha\in \mathbb B_n$. Hence, given~$x$, it suffices to solve the $k$-th root problem for any conjugate of~$x$, for instance for some $y \in USS(x)$.

We will focus our attention in the generic case in which $USS(x)$ is minimal. Recall from \autoref{teoJuanLoles} that in this case $Z(x)\simeq Z(y)\simeq \mathbb Z^2$. If we express the centralizer of~$y$ as $Z(y)=\langle v,w\rangle$, where~$v$ and~$w$ commute, we know that $y$ has the form $y=v^c w^d$, for some $c,d\in \mathbb Z$ (and that this expression is unique, as any other expression would yield a different element of~$Z(y)$). If we are able to express $y$ in this way, then the $k$-th root problem is trivially solved:

\begin{proposition}\label{prop_raiz}
Let $x\in \mathbb B_n$. Let $y\in USS(x)$ and suppose that $USS(x)$ is minimal. Let $Z(y)=\langle v,w\rangle$ and let $c,d\in \mathbb Z$ be such that $y=v^c w^d$. Then~$y$ admits a $k$-th root if and only if both $c$ and $d$ are multiples of $k$, and in this case the only $k$-th root of~$y$ is:
\[
     a= v^{\frac{c}{k}} w^{\frac{d}{k}}.
\]
\end{proposition}

\begin{proof}
We know from \autoref{teoJuanLoles} that $Z(y)\simeq \mathbb Z^2$, so it is abelian. Hence, by \autoref{roots_are_conjugate_in_Z(x)}, if a $k$-th root~$a$ of~$y$ exists then $\sqrt[k]{y} = a^{Z(y)} = \{a\}$. Therefore, if a $k$-th root exists, it is unique.

Suppose that the $k$-th root problem for~$y$ has a solution $a\in \mathbb B_n$. Then $a\in Z(y)$, and hence $a=v^r w^s$ for some $r,s\in \mathbb Z$. But since~$v$ and~$w$ commute, we have:
\[
   v^c w^d = y = a^k = (v^r w^s)^k = v^{rk} w^{sk}.
\]
This implies that~$c$ and~$d$ are multiples of~$k$, and that $a= v^r w^s= v^{\frac{c}{k}} w^{\frac{d}{k}}.$

Conversely, if~$c$ and~$d$ are multiples of~$k$, we write $c=rk$ and $d=sk$ for some integers $r, s$, and we consider the element $a=v^r w^s$. Since~$v$ and~$w$ commute, it follows that $a^k=y$.
\end{proof}

By the above result, it follows that the only difficulty in solving the $k$-th root problem, in the generic case in which $USS(x)$ is minimal, is to express some $y\in USS(x)$ in terms of the generators of~$Z(y)$. We know from \autoref{teoJuanLoles} that there are three possible cases, depending on whether~$USS(x)$ has two orbits under cycling, or has one orbit with $\tau(y)=y$, or has one orbit with $\tau(y)\neq y$. The three following results address each case:

\begin{proposition}\label{case1}
Let $x\in \mathbb B_n$, and let $y=\Delta^p y_1\cdots y_l\in USS(x)$, written in left normal form. Suppose that $USS(x)$ is minimal. Suppose also that $USS(x)$ has two orbits under cycling, conjugate to each other by~$\Delta$. Let $v=\Delta^2$ and $w=PC(y)=p_1\cdots p_t$, so:
$$
    Z(y) = \langle v, w\rangle = \langle \Delta^2, PC(y)\rangle.
$$
If we write $c=p/2$ and $d=l/t$, then~$c$ and~$d$ are integers and we have: $y=v^c w^d$.
\end{proposition}

\begin{proof}
We know that, since $USS(x)$ is minimal, it consists of rigid elements. Hence iterated cycling corresponds to a cyclic permutation of the factors in the normal form of~$y$ (with possible conjugations by~$\Delta$, if~$p$ is odd).

Suppose that~$p$ is odd. Then~$\boldsymbol{\mathrm c}^l(y)$ is obtained from~$y$ by cyclically permuting all its~$l$ factors, conjugating all of them by $\Delta$. Hence $\boldsymbol{\mathrm c}^l(y)=\tau(y)$. This implies that $\tau(y)=\Delta^{-1}y\Delta$ is in the same orbit of~$y$ under cycling, but this is a contradiction with the hypotheses, as $USS(x)$ has two distinct orbits (the one containing~$y$ and the one containing~$\tau(y)$). Therefore~$p$ is even.

Since~$p$ is even, iterated cyclings of~$y$ correspond exactly to cyclic permutations of the factors of~$y$. By definition, $t$~is the smallest positive integer such that $\boldsymbol{\mathrm c}^t(y)=y$, and it is then clear that $\boldsymbol{\mathrm c}^m(y)=y$ for some positive integer~$m$ if and only if~$m$ is a multiple of~$t$. Since $\boldsymbol{\mathrm c}^l(y)=y$, we finally obtain that~$l$ is a multiple of~$t$. Then the normal form of~$y$ is as follows:
\[
    y= \Delta^p y_1\cdots y_l = \Delta^p (y_1\cdots y_t)(y_1\cdots y_t)\cdots (y_1\cdots y_t),
\]
where $PC(y)=y_1\cdots y_t$, and there are~$l/t$ parenthesized factors.

Now, if we write $c=p/2$ and $d=l/t$, these numbers are integers and we have:
\[
  v^c w^d = (\Delta^2)^c (PC(y))^d = \Delta^{2c} (y_1\cdots y_t)^d = \Delta^p y_1\cdots y_l = y.
\]
\end{proof}

\begin{proposition}\label{case2}
Let $x\in \mathbb B_n$, and let $y=\Delta^p y_1\cdots y_l\in USS(x)$, written in left normal form. Suppose that $USS(x)$ is minimal. Suppose also that $USS(x)$ has one orbit under cycling, conjugate to itself by~$\Delta$, and that $\tau(y)=y$. Let $v=\Delta$ and $w=PC(y)=p_1\cdots p_t$, so:
$$
    Z(y) = \langle v, w\rangle = \langle \Delta, PC(y)\rangle.
$$
If we write $c=p$ and $d=l/t$, then~$c$ and~$d$ are integers and we have: $y=v^c w^d$.
\end{proposition}

\begin{proof}
We know that the left normal form of $\tau(y)$ is $\Delta^p \tau(y_1)\cdots \tau(y_l)$. Since $\tau(y)=y$, the normal forms of~$y$ and~$\tau(y)$ must coincide, hence $\tau(y_i)=y_i$ for $i=1,\ldots,l$.

This implies that iterated cyclings correspond to cyclic permutations of the factors of~$y$. We do not care about the parity of~$p$, as every factor of~$y$ is invariant under $\tau$. It then follows that $PC(y)=y_1\cdots y_t$, that $t$ divides $l$ and that the normal form of $y$ is:
$$
   y = \Delta^p y_1\cdots y_l = \Delta^p (y_1\cdots y_t)(y_1\cdots y_t)\cdots (y_1\cdots y_t),
$$
where there are $l/t$ parenthesized factors.

Now, if we write $c=p$ and $d=l/t$, these numbers are integers and we have:
$$
   v^c w^d = \Delta^c (PC(y))^d = \Delta^{c} (y_1\cdots y_t)^d = \Delta^p y_1\cdots y_l = y.
$$
\end{proof}

\begin{proposition}\label{case3}
Let $x\in \mathbb B_n$, and let $y=\Delta^p y_1\cdots y_l\in USS(x)$, written in left normal form. Suppose that $USS(x)$ is minimal. Suppose also that $USS(x)$ has one orbit under cycling, conjugate to itself by $\Delta$, and that $\tau(y)\neq y$. Let $v=\Delta^2$, $PC(y) = p_1 \cdots p_t$ and $w=p_1\cdots p_{\frac{t}{2}}\Delta^{-1}$ (recall from \autoref{teoJuanLoles} that $t$ is even), so:
$$
    Z(y) = \langle v, w\rangle = \langle \Delta, \: p_1\cdots p_{\frac{t}{2}}\Delta^{-1}\rangle.
$$
If we write $c=\frac{pt+2l}{2t}$ and $d=\frac{2l}{t}$, then $c$ and $d$ are integers and we have: $y=v^c w^d$.
\end{proposition}

\begin{proof}
We know from \autoref{teoJuanLoles} that~$t$ is even, but let us see why this holds. We know that there exists some $m>0$ so that $\tau(y)=\boldsymbol{\mathrm c}^m(y)$; we take $m$ as small as possible, and this implies that $\boldsymbol{\mathrm c}^r(y)\neq y$ for $0<r<m$. Now, it follows from their own definitions that~$\tau$ and~$\boldsymbol{\mathrm c}$ commute, and therefore $y = \tau^2(y) = \tau(\boldsymbol{\mathrm c}^m(y)) = \boldsymbol{\mathrm c}^m(\tau(y))= \boldsymbol{\mathrm c}^{2m}(y)$. This implies that the length of the cycling orbit of~$y$ is a divisor of~$2m$. It cannot be~$m$ (as $\boldsymbol{\mathrm c}^m(y)=\tau(y)\neq y$), and it cannot be smaller than~$m$ (as $\boldsymbol{\mathrm c}^r(y)\neq y$ for every $r<m$). Therefore, the length of the orbit is precisely $t=2m$.  The generators of~$Z(y)$ are then $v=\Delta^2$ and $w=p_1\cdots p_m \Delta^{-1}$.

We consider now two cases, depending on the parity of~$p$. If~$p$ is even, since the first $m$~cyclings transform~$y$ into~$\tau(y)$, it follows that the left normal form of~$y$ is:
$$
    y= \Delta^p \ \left(y_1\cdots y_{m}\right)\  \left(\tau(y_1)\cdots \tau(y_{m})\right)\ \cdots \  \left(y_1\cdots y_{m}\right)\ \left(\tau(y_1)\cdots \tau(y_{m})\right).
$$
Then $l=2rm$ for some positive integer~$r$.

Recall that~$PC(y)$ is the product of the first $t=2m$ conjugating elements for cycling. The first $m$~conjugating elements are $y_1,\ldots, y_m$, so $p_i=y_i$ for $i=1,\ldots,m$. The following $m$~conjugating elements are~$\tau(y_1),\ldots, \tau(y_m)$. Hence, we have that
\begin{eqnarray*}
 PC(y) & = & p_1\cdots p_t
 \\ & = & y_1\cdots y_{m} \tau(y_1)\cdots \tau(y_{m})
 \\ & = & y_1\cdots y_{m} \;\tau(y_1\cdots y_{m})
 \\ & = & p_1\cdots p_{m} \Delta^{-1} p_1\cdots p_{m} \Delta
 \\ & = & \left(p_1\cdots p_{m} \Delta^{-1}\right) \left(p_1\cdots p_{m} \Delta^{-1}\right) \Delta^2
 \\ & = &  w^2 v.
\end{eqnarray*}

Therefore, if~$p$ is even:
$$
  y= \Delta^p PC(y)^{r} = v^{\frac{p}{2}} \left(w^2v\right)^{r} = v^{\frac{p}{2}+r} w^{2r} = v^c w^d,
$$
where $c=\frac{pt+2l}{2t}$ and $d=\frac{2l}{t}$ (recall that $l=2rm=rt$).

Consider now the case when~$p$ is odd. In this case, the left normal form of~$y$ is:
$$
    y= \Delta^p \ \left(y_1\cdots y_{m}\right)\  \left(\tau(y_1)\cdots \tau(y_{m})\right)\ \cdots \  \left(y_1\cdots y_{m}\right)\ \left(\tau(y_1)\cdots \tau(y_{m})\right)\ \left(y_1\cdots y_{m}\right).
$$
Then $l=(2r+1)m$ for some positive integer $r$.

As before, $PC(y)$ is the product of the first $t=2m$ conjugating elements for cycling, but this time the first $m$ conjugating elements for cycling are $\tau(y_1),\ldots,\tau(y_m)$, and therefore $p_i=\tau(y_i)$ for $i=1,\ldots,m$. The following $m$ conjugating elements are $y_1,\ldots,y_m$, so we have:
\begin{eqnarray*}
 PC(y) & = & p_1\cdots p_t
 \\ & = & \tau(y_1)\cdots \tau(y_{m}) y_1\cdots y_{m}
 \\ & = & p_1\cdots p_{m} \;\tau(p_1\cdots p_{m})
 \\ & = & p_1\cdots p_{m} \Delta^{-1} p_1\cdots p_{m} \Delta
 \\ & = & \left(p_1\cdots p_{m} \Delta^{-1}\right) \left(p_1\cdots p_{m} \Delta^{-1}\right) \Delta^2
 \\ & = &  w^2 v.
\end{eqnarray*}

Hence $PC(y)=w^2v$ also when $p$ is odd. Finally, we have:
\begin{eqnarray*}
  y & = & \Delta^p (y_1\cdots y_{m}) (\tau(y_1)\cdots \tau(y_{m}))\cdots (y_1\cdots y_{m}) (\tau(y_1)\cdots \tau(y_{m}))(y_1\cdots y_{m})
\\ & = & (\tau(y_1)\cdots \tau(y_{m})) (y_1\cdots y_{m})\cdots (\tau(y_1)\cdots \tau(y_{m})) (y_1\cdots y_{m}) \Delta^p (y_1\cdots y_{m})
\\ & = & PC(y)^r \Delta^p (y_1\cdots y_{m})
\\ & = & PC(y)^r \Delta^{p+1} \Delta^{-1}(y_1\cdots y_{m})
\\ & = & PC(y)^r \Delta^{p+1} (p_1\cdots p_{m}) \Delta^{-1}
\\ & = & (w^2v)^r v^{\frac{p+1}{2}}w
\\ & = & v^{\frac{2r+1+p}{2}}w^{2r+1}
\\ & = & v^{c}w^{d},
\end{eqnarray*}
where $c=\frac{pt+2l}{2t}$ and $d=\frac{2l}{t}$ (recall that $2l=2(2r+1)m=(2r+1)t$ in this case).
\end{proof}

\section{An algorithm to find the $k$-th root of a braid}\label{section_algorithm}

We end this paper by providing a detailed algorithm that summarizes the results from the previous section, together with a study of its complexity.

The results of the previous section are valid when $USS(x)$ is minimal (which is the generic case). In order to have an algorithm which always succeeds in finding the $k$-th root of a braid~$x$, we need to include instructions on what to do if $USS(x)$ is not minimal. In those cases, one can use the algorithm in \cite{Lee}, which finds the $k$-th root of~$x$ in any case, considering the Garside group $G=\mathbb Z\ltimes \left(\mathbb B_n\right)^k$, where $\mathbb Z=\langle \delta\rangle $ acts on~$\left(\mathbb B_n\right)^k$ by cyclic permutation of the coordinates. S. J. Lee shows that the braid~$x$ has a $k$-th root if and only if the ultra summit set of $\delta (x,1,\ldots,1)$ in~$G$ has an element of the form $\delta (h,\ldots,h)$. Hence, computing an ultra summit set in such a group also solves the root extraction problem in~$\mathbb B_n$. It is not clear to us how big these ultra summit sets are in generic cases, while the algorithm presented in this paper is very simple, and generically very fast.

If one is not interested in programming the algorithm in~\cite{Lee}, one could tell our algorithm to return `fail' when $USS(x)$ is not minimal, obtaining an algorithm which will succeed only in the generic case. In any case, we present now the main result:

\begin{theorem}\label{maintheorem}
There is an algorithm that takes as input a braid $x=\Delta^p x_1\ldots,x_l \in \mathbb B_n$ written in left normal form, and a positive integer $k>1$, and finds a braid $a\in \mathbb B_n$ such that $a^k=x$, or guarantees that such a braid does not exist, whose generic-case complexity is $O(l(l+n)n^3\log n)$.
\end{theorem}

\begin{proof}
\autoref{algo}, which uses the results from the previous section, constitutes a proof of the theorem. Let us describe it in detail.

 The input is a braid $x=\Delta^p x_1\cdots x_l\in \mathbb B_n$ in left normal form and an integer $k>1$. First (lines 2-5), the algorithm applies iterated cyclic sliding to~$x$, checking at each iteration whether the resulting braid~$y$ is rigid. As we will now see, if the algorithm applies cyclic sliding $l\left(\frac{n(n-1)}{2}-1\right)$ times and no rigid braid is obtained, then we are not in the generic case stated in \autoref{teoCarusoWiest}, hence the algorithm in~\cite{Lee} is applied. The number $l\left(\frac{n(n-1)}{2}-1\right)$ is precisely $l$~times the length of~$\Delta$ minus one. Recall from \autoref{teoCarusoWiest} that in the generic case there is a positive element~$\alpha$ conjugating~$x$ to a rigid braid, such that $\ell(\alpha)< \ell(x)=l$. If~$\alpha$ is the smallest possible one, there is no~$\Delta$ in its normal form. Hence, the length of~$\alpha$ in terms of atoms ($\sigma_i$'s) is at most $l\left(\frac{n(n-1)}{2}-1\right)$. Now, from \autoref{Cyclic_Sliding_fastest_conjugation} we know that the smallest positive conjugator to a rigid braid is obtained by iterated cyclic sliding. Since at every iteration the conjugating element gets bigger, if we are in the generic case we must obtain a rigid element in at most $l\left(\frac{n(n-1)}{2}-1\right)$ iterations, as we claimed.

 If the braid~$y$ obtained after the loop in lines 2-5 is rigid, as the algorithms stores the conjugating elements for cyclic sliding at each iteration, we will have a braid~$\alpha$ such that $\alpha^{-1}x\alpha=y$.

 Now the algorithm checks whether $USS(y)$ is minimal (the generic case we are interested in), as explained in \autoref{checking_minimal}, checking whether the minimal simple elements for~$y$ are precisely~$\iota(y)$ and~$\partial(\varphi(y))$.

 In general, it is not known how fast it is to compute the minimal simple elements for a given arbitrary braid~$y$. But if~$y$ is rigid, one can easily find the minimal simple elements for~$y$. We know that every such element must be a prefix of either~$\iota(y)$ or~$\partial(\varphi(y))$. For every generator~$\sigma_i$, one can consider $\sigma_i^{-1}y\sigma_i$ and apply iterated cyclic sliding to it, until it becomes rigid. The obtained conjugating element is the smallest conjugating element from $y$ to a rigid braid, having~$\sigma_i$ as a prefix. We do this for all~$\sigma_i$ which are prefixes of~$\iota(y)$, and either we find a conjugating element which is a proper prefix of~$\iota(y)$ (in which case~$\iota(y)$ is not minimal), or we have shown that~$\iota(y)$ is minimal. Then we do the same for all generators which are prefixes of~$\partial(\varphi(y))$. The number of iterations in each case is bounded by the length  of~$\iota(y)$ (resp.~$\partial(\varphi(y))$), which are simple elements, while the total number of generators is~$n-1$. So the total number of cyclic slidings used to check whether~$\iota(y)$ and~$\partial(\varphi(y))$ are minimal (and hence whether $USS(y)$ is minimal) is~$O(n^3)$.

 If $USS(y)$ is not minimal, we are not in the generic case stated in \autoref{teoCarusoWiest}, hence the algorithm in \cite{Lee} is applied. Otherwise, we are in one of the situations described in \autoref{case1}, \autoref{case2} and \autoref{case3}. The rest of the algorithm just applies these propositions together with \autoref{prop_raiz}: after decomposing~$y$ in the form $y=v^cw^d$, it checks whether both~$c$ and~$d$ are multiples of~$k$. If this is the case, then $v^{\frac{c}{k}}w^{\frac{d}{k}}$ is the (unique) $k$-th root of~$y$, and since $x=\alpha y \alpha^{-1}$, it follows that $\alpha v^{\frac{c}{k}}w^{\frac{d}{k}}\alpha^{-1}$ is the desired $k$-th root of~$x$; otherwise, the algorithm returns the sentence ``A $k$-th root does not exist".

We study now the complexity of our algorithm, assuming that we are in the generic case in which $USS(x)$ is minimal, and we can quickly conjugate~$x$ to a rigid braid. Computing the complement or applying~$\tau$ to a simple element is~$O(n)$, and computing $s\wedge t$ for two simple elements~$s$ and~$t$ is~$O(n\log n)$ \cite[Proposition~9.5.1]{Epsteinetal}. Starting with an element~$y$ in left normal form, computing~$\mathfrak s(y)$ consists of computing a complement ($\partial(\varphi(y))$), a meet ($\iota(x)\wedge \partial(\varphi(x))$) and the normal form of the conjugate of~$y$ by a simple element of length at most~$l$ (which is $O(ln\log n)$). Hence the total complexity of applying a cyclic sliding is $O(ln\log n)$.

 The first loop (lines 2-5) is repeated~$O(ln^2)$ times, checking the condition takes $O(n\log n)$ and the body of the loop takes $O(ln\log n)$. Hence the total complexity of the loop in lines 2-5 is $O(l^2n^3\log n)$.

 The ``If" statement in lines 6-7 is negligible compared with the previous ``while" loop.

 Next, in lines 8-9 the algorithm checks whether~$\iota(y)$ and~$\partial(\varphi(y))$ are minimal, for the rigid element~$y$. By the arguments above, this applies~$O(n^3)$ cyclic slidings, hence the total complexity of this step is $O(ln^4\log n)$.

 In line 11 and in the loop in lines 12-15, some cyclings are applied. Since the involved braids are rigid of canonical length at most~$l$, and cycling is just a cyclic permutation of the factors with a possible application of~$\tau$ to a simple element, this final part of the algorithm is negligible with respect to the previous one.

 Therefore, the generic-case complexity of \autoref{algo} is $O(l(l+n)n^3\log n)$.
\end{proof}

\begin{algorithm}[ht]
\small
\SetKwData{Self}{selfConjugateOrbit}
\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{A braid $x\in \mathbb B_n$ given in left normal form, and an integer $k>1$.}
\Output{A braid $a\in \mathbb B_n$ such that $a^k=x$, or the message ``{\it A $k$-th root does not exist.}".}

$y:=x$;\quad $l=\ell(x)$;\quad $\alpha=1\in \mathbb B_n$;\quad $r=0\in \mathbb Z$\;
\While{$\iota(y)\wedge \partial(\varphi(y))\neq 1$ {\bf and} $r< l\left(\frac{n(n-1)}{2}-1\right)$}{
 $\alpha:=\alpha\: \mathfrak p(y)$\;
 $y:=\mathfrak s(y)$\;
 $r:=r+1$\;
}
\If{$\iota(y)\wedge \partial(\varphi(y))\neq 1$}{
  $y$ is not rigid. Apply the algorithm in \cite{Lee}\;
}
\ElseIf{$\{\mbox{Minimal simple elements for }y\}\neq \{\iota(y),\: \partial(\varphi(y))\}$}{
  $USS(y)$ is not minimal. Apply the algorithm in \cite{Lee}\;
}
\Else{

$y':=\tau(y)$; \quad $z:=\boldsymbol{\mathrm c}(y)$;\quad $PC:=\iota(y)\in \mathbb B_n$; \quad $t:=1\in \mathbb Z$;   \quad $p:=\inf(y)$; \quad $l:=\ell(y)$; \quad $\Self:=0$\;
\While{$z\neq y$ {\bf and} $z\neq y'$}
{
 $PC:=PC\: \iota(z)$\;
 $z:=\boldsymbol{\mathrm c}(z)$\;
 $t:=t+1$\;
}
\If{$z=y'$}{
   $\Self := 1$\;
 }

\If{$\Self=0$}{
 $c:= p/2$\;
 $d:= l/t$\;
 \If{$k|c$ {\bf and} $k|d$}{
  $v:=\Delta^2$\;
  $w:=PC$\;
  \Return{$\alpha v^{\frac{c}{k}}w^{\frac{d}{k}}\alpha^{-1}$\;}
 }
 \Else{
  \Return{``A $k$-th root does not exist.'';}
 }
}
\ElseIf{$\Self=1$ {\bf and} $y=y'$}{
 $c:= p$\;
 $d:= l/t$\;
 \If{$k|c$ {\bf and} $k|d$}{
  $v:=\Delta$\;
  $w:=PC$\;
  \Return{$\alpha v^{\frac{c}{k}}w^{\frac{d}{k}}\alpha^{-1}$\;}
 }
 \Else{
  \Return{``A $k$-th root does not exist.'';}
 }
}
\ElseIf{$\Self=1$ {\bf and} $y\neq y'$}{
 $t:=2t$\;
 $c:= \frac{pt+2l}{2t}$\;
 $d:= \frac{2l}{t}$\;
 \If{$k|c$ {\bf and} $k|d$}{
  $v:=\Delta$\;
  $w:=PC\: \Delta^{-1}$\;
  \Return{$\alpha v^{\frac{c}{k}}w^{\frac{d}{k}}\alpha^{-1}$\;}
 }
 \Else{
  \Return{``A $k$-th root does not exist.'';}
 }
}
}

\caption{Find a $k$-th root of a braid $x$. }\label{algo}
\end{algorithm}

\begin{remark}
Although the integers~$p$ and~$k$ are part of the input, the computed complexity does not involve them, as treating with these integers is usually negligible, in reasonable examples, with respect to the calculated complexity. If~$p$ is really big, one should take into account the number~$\log p$. The case of~$k$ is somehow different, as one would have a positive answer only if~$k$ is a divisor of the integers~$c$ and~$d$ (with $d\neq 0$), which are~$O(p+l)$, so it makes no sense to ask for a $k$-th root of~$x$, in the generic case, if~$k$ is too big compared with~$p$ and~$l$.
\end{remark}

\bibliographystyle{plain}


\section{Introduction}
Pulsating stars such as classical Cepheids enable precise measurements of the local expansion rate of the Universe, $H_0$, thanks to the existence of period-luminosity relations (PLRs), or Leavitt laws \citep[henceforth: LLs]{Leavitt1908,Leavitt1912}. Using a Cepheids-based distance ladder, the {\it SH0ES} team \citep[henceforth: R+16]{Riess2016} recently established a systematic difference between the present-day value of $H_0$ and the value inferred based on Cosmic Microwave Background observations by the \citet{Planck2018H0} assuming the concordance cosmological model (flat $\Lambda$CDM). Following further improvements to the distance ladder \citep[e.g.][]{Riess2018,Riess2019}, and considering Cepheid-independent routes to measure $H_0$ \citep[e.g.][]{Wong2019,Freedman2019,Yuan2019}, the so-called Hubble tension now figures at a significance of $4-6\sigma$, sparking an increasing number of suggested modifications to $\Lambda$CDM \citep[for a detailed overview, see][and references therein]{Verde2019}.

The {\it SH0ES} distance ladder consists of three rungs that are fitted globally (cf. Appendix in R+16). The first rung involves the calibration of the Cepheid LL in relatively nearby, so-called ``anchor'' galaxies whose distances are known. The second rung consists of so-called ``SN-host'' galaxies, where both Cepheids and type-Ia supernovae (SNe\,Ia) have been observed: SN-host galaxies thus set the luminosity zero-point for SNe\,Ia. The third, final rung consists of the Hubble diagram of SNe\,Ia. The intercept of this Hubble diagram provides the measurement of $H_0$. Almost all SN-host galaxies are more distant than the anchor galaxies, with the exception of M\,101, which is approximately $0.9$\,Mpc closer than the anchor galaxy NGC\,4258. Following an improvement of the distance to NGC\,4258, the latest $H_0 = 73.5 \pm 1.4$$\rm{km\,s^{-1}\,Mpc^{-1}}$\ \citep{Reid2019}.

Following impressive gains in $H_0$ precision and the importance of $H_0$ for informing modifications to $\Lambda$CDM, the identification and mitigation of previously overlooked $H_0$ uncertainties and biases is rapidly gaining  importance. Notably, the effects of stellar association bias \citep{AndersonRiess2018} are now taken into account in the $H_0$ measurement \citep{Riess2019}.

A key bottleneck for increasing $H_0$ precision is the number of SN-host galaxies. At present,  Cepheids can be measured with good precision in galaxies up to $\sim 40$\,Mpc distant (R+16), and large efforts are in progress to increase the number of SN-host galaxies from currently 19 to 38 \citep{Riess2019}. However, the rather low volumetric rate of SNe\,Ia explosions requires exploring alternative primary distance indicators capable of probing greater distances, such as Mira-variable stars \citep[e.g.][]{Whitelock2008,Yuan2017,Huang2018,Huang2019,Bhardwaj2019}, especially considering the short mission duration of the James Webb Space Telescope ({\it JWST}). Adding new SN-host galaxies to the distance ladder will therefore tend to include more distant galaxies and increase average SN-host galaxy redshift due to the Hubble-Lema\^itre law \citep{Wirtz1924,Lemaitre1927,Hubble1929}.

The longitudinal Doppler effect shifts the oscillation frequency emitted by a source as a function of its radial (line-of-sight) velocity, $v_r$. Time dilation due to cosmological redshift $\bar{z}$ slows down clocks in a mathematically approximately identical way in the case of small $\bar{z}$ and non-relativistic velocities ($v_r \ll c$). Thus, time dilation of the type Ia supernova SN\,1995K enabled observational proof of the Universe's expansion \citep{Leibundgut1996}.
Several studies have considered the impact of inaccuracies related to redshift measurements of SNe\,Ia \citep[e.g.][]{Hui2006,Davis2011,Davis2019} on $H_0$ and the dark energy equation of state. Additionally, the impact of Doppler frequency shifts for asteroseismic inferences was studied by \citet{Davies2014} and is gaining importance for measuring orbital motion in pulsating stars \citep{Murphy2014}.
However, the impact of systematic differences in (observed heliocentric) redshift between anchor and SN-host galaxies on variable-star periods and the $H_0$ measurement has hitherto remained unexplored.

This \emph{article} investigates the relevance and impact of dilated variable-star periods on the measurement of $H_0$. Specifically, \S\ref{sec:RLB} explains the distance bias arising from cosmic expansion, the Doppler effect, and the Leavitt law in the case of Cepheids and Mira stars. \S\ref{sec:H0} estimates the impact on the latest $H_0$ measurement involving Cepheids and SNe\,Ia. \S\ref{sec:discussion} discusses these findings in the context of future distance ladders based on Mira-variable stars in the era of the {\it JWST}. Finally, \S\ref{sec:conclusions} summarises this work and presents its conclusions.

\section{Redshift-Leavitt Bias (RLB)}\label{sec:RLB}
\begin{figure}
    \centering
    \includegraphics{RLBcartoon}
    \caption{Not-to-scale visual representation of Redshift-Leavitt Bias. SN-hosts are redshifted relative to anchor galaxies. Observed oscillation frequencies of Cepheids, Miras, and other variable stars, are subject to time dilation, i.e., observed periods are longer than emitted periods. This translates to a distance modulus bias due to the slope of Leavitt laws.\label{fig:cartoon}}
\end{figure}

The observed total redshift of an extragalactic source relative to the observer is a combination of cosmological redshift ($\bar{z}$), peculiar motion of the galaxy ($z_{\rm{pec}}^{\rm{gal}}$), peculiar motion of the observer ($z_{\rm{pec}}$), and gravitational redshift of the galaxy ($z_{\rm{\phi}}^{\rm{gal}}$) and the observer ($z_{\rm{\phi}}$). Once corrected to the heliocentric reference frame, the observed redshift $z_{\rm{obs}}$ is \citep[their Eq.\,2.2]{Calcino2017}:
\begin{equation}
1 + z_{\rm{obs}} = (1 + \bar{z})(1 + z_{\rm{pec}}^{\rm{gal}})(1 + z_{\rm{pec}})(1 + z_{\rm{\phi}}^{\rm{gal}})(1+ z_{\rm{\phi}}) \ .
\label{eq:redshift}
\end{equation}

Variability periods of extragalactic variable stars such as classical Cepheids are subject to both time dilation due to cosmological redshift (mostly relevant for Cepheids outside the Local Group), and the Doppler effect due to line-of-sight motions such as peculiar velocities, velocity dispersions, partial sampling of a galaxy's rotation curve, orbital motion, etc. Since the latter velocities are usually $\lesssim 1000$\,$\rm{km\,s}^{-1}$, such Doppler shifts can be treated non-relativistically to very good approximation. The observed redshift of an individual variable star in another galaxy is thus:
\begin{equation}
1 + z_{i,\rm{obs}} \approx (1 + z_{\rm{obs}})\left(1 + \frac{v_{r,i}}{c}\right)\ ,
\label{eq:redshiftdoppler}
\end{equation}
where $v_{r,i}$ is the line-of-sight component of the star's motion relative to the heliocentric reference frame, not counting peculiar motion, which is already included as part of Eq.\,\ref{eq:redshift}. Of course, $v_{r,i}$ of individual Cepheids is currently measurable only in the Milky Way and Magellanic Clouds, where cosmological redshift is negligible. For individual variable stars in other galaxies, internal motions due to velocity dispersion and partially sampled rotation curves can lead to $v_{r,i}/c \lesssim 10^{-3}$. However, most observed populations of Cepheids in SN-host galaxies sample all parts of their host galaxy disks, which furthermore tend to be oriented relatively face-on. Hence, no significant net effect is to be expected for a typical SN-host galaxy's Cepheid population as a whole, meaning, $\langle v_{r} \rangle \approx 0$. For partially sampled galaxies \citep[e.g. the PHAT footprint of M31, cf.][]{Dalcanton2012}, disk or halo rotation could lead to a net $\langle v_r \rangle \lesssim \pm 300$\,$\rm{km\,s}^{-1}$, which would be comparable to the effect of $\bar{z}$ at distances $\lesssim 4$\,Mpc.

Galaxy catalogs list redshifts ($z_{\rm{obs}}$) measured as the displacement of spectral lines relative to their rest-wavelength $\lambda_0$, corrected to the heliocentric reference frame \citep[e.g.][]{Huchra1992}:
\begin{equation}
z_{\rm{obs}} = \frac{\lambda - \lambda_0}{\lambda_0} \ .
\label{eq:redshiftmeasured}
\end{equation}
$z_{\rm{obs}}$ does not distinguish between the physical origin of redshift, and includes all terms listed in Eq.\,\ref{eq:redshift}. However, it does not account for motions of individual stars ($v_{r,i}$) or velocity differences across a galaxy. In the following, we neglect these latter two contributions since Cepheid populations are usually distributed across the full disks of SN-host galaxies, which are usually oriented face-on (R+16). However, observers may consider accounting for net effects, due to galaxy rotation at distances $\lesssim 40$\,Mpc, if these conditions are not fulfilled.

Using $z_{\rm{obs}}$, we calculated the effect of time dilation on variable-star periods (cf. Fig.\,\ref{fig:timedilation}) as
\begin{equation}
P_{\rm{obs}} = (1 + z_{\rm{obs}})P_{0} \ ,\ \mathrm{so\ that}
\label{eq:TimeDilation}
\end{equation}
\vspace{-0.5cm}
\begin{equation}
\Delta \log{P} = \log{P_{\rm{obs}}} - \log{P_0} = \log{(1 + z_{\rm{obs}})} = \log{B}\ ,
\label{eq:deltalogP}
\end{equation}
where we use $\log{B} = \log{(1 + z_{\rm{obs}})}$ for brevity.

\begin{figure}
    \centering
    \includegraphics{DeltaLogP}
    \caption{\label{fig:timedilation} Dilation of logarithmic oscillation period as a function of redshift, cf. Eq.\,\ref{eq:deltalogP}.}
    \vspace{0.2cm}
    \includegraphics{DeltaMuZ}
    \caption{\label{fig:distmod} Redshift-Leavitt Bias for Cepheids and Miras with $\langle \log{P_{\rm{obs}}} \rangle = 2.4$ whose LL is calibrated at $\log{P_{\rm{ref}}}=2.3$, cf. Eqs.\,\ref{eq:leavitt}, and \ref{eq:leavittMira}.}
\end{figure}

Leavitt Laws relate oscillation periods of certain pulsating star types to  absolute magnitudes $M$. The most common functional form is linear in $\log{P}$ and is used, for example, for classical Cepheid variables:
\begin{equation}
M = a + b\cdot\log{P} \ ,
\label{eq:leavitt}
\end{equation}
where $a$ and $b$ are calibrated using objects at known distances (ideally from geometry), for example, via {\it Gaia} parallaxes \citep{GaiaDR2Brown,Lindegren2018}, detached eclipsing binaries in the LMC \citep{Pietrzynski2019}, or the parallax of the mega-maser in NGC\,4258 \citep{Humphreys2013}.

Non-linear LLs have also been considered, for example, broken PLRs for Cepheids \citep[e.g.][]{Bhardwaj2016}, PLRs affected by metallicity \citep[e.g.][especially for RR Lyrae stars observed in the infrared]{Sesar2017,Gieren2018,Delgado2019}. LLs are noticeably non-linear for Mira stars, where quadratic LLs  have been used \citep[e.g.][]{Yuan2017,Huang2018}:
\begin{equation}
M = a + b_1 \cdot (\log{P_{\mathrm{obs}}} - 2.3) + b_2 \cdot (\log{P_{\mathrm{obs}}} - 2.3)^2 \ .
\label{eq:leavittMira}
\end{equation}

In the following, we adopt $b=-3.26$ for a linear LL appropriate for Cepheids ($H-$band Wesenheit PL-slope from R+16) and $b_1 = -3.59$, $b_2 = -3.40$, and $\log{P_{\rm{ref}}} = 2.3$ \citep{Huang2018} for quadratic LLs.

Absolute magnitudes inferred using LLs, $M_{\rm{LL}}$, are biased by the effect of time dilation on oscillation periods, cf. Fig.\,\ref{fig:cartoon}. With Eq.\,\ref{eq:deltalogP} and Eqs.\,\ref{eq:leavitt} \& \ref{eq:leavittMira}, we obtain
\begin{equation}
\begin{split}
\Delta M & = M_{\rm{LL}} - M_0 \\
 & = b\Delta\log{P} = b\log{B} & \small{[\rm{lin\, LL}]}\\
 & = b_1  \log{B} + b_2  \log{B}  \left( 2 \log{P_{\rm{obs}}^{'}}  - \log{B} \right) & \small{[\rm{quad\, LL}]} & \ ,
\end{split}
\label{eq:MLL}
\end{equation}
where the second line applies to linear LLs and the third line to quadratic LLs. For linear LLs, the bias depends only on $b$ and the observed heliocentric redshift. For quadratic LLs, RLB depends on $z_{\rm{obs}}$, $b_1$, and $b_2$, as well as the pivot period $P_{\rm{ref}}$, since $\log{P_{\rm{obs}}^{'}} = \log{P_{\rm{obs}}} - \log{P_{\rm{ref}}}$.

The resulting bias in distance modulus is therefore:
\begin{equation}
\Delta \mu = \mu_{\rm{LL}} - \mu_0 = m - M_0 - \Delta M - m + M_0 = -\Delta M \ .
\label{eq:deltamu}
\end{equation}
Inserting Eq.\,\ref{eq:MLL} in Eq.\,\ref{eq:deltamu} we obtain:
\begin{equation}
\begin{split}
\Delta \mu = & - b\log{B} & \small{\rm{[lin\, LL]}} \\
\Delta \mu = & - b_1  \log{B} - b_2  \log{B}  \left( 2 \log{P_{\rm{obs}}^{'}}  - \log{B} \right) & \small{\rm{[quad\, LL]}} &\ .
\end{split}
\label{eq:deltamuLL}
\end{equation}
Figure\,\ref{fig:distmod} illustrates $\Delta\mu$ for a wide range of $z_{\rm{obs}}$. We notice that a) $(\log{B})^2 \sim 10^{-4}$ is negligible at distances $< 100$Mpc, and b) $\log{P_{\rm{obs}}^{'}}$ can be minimized by using a pivot $\log{P_{\rm{ref}}}$ close to the sample average. However, any galaxy is expected to show a distribution of Mira periods, so that time dilation could lead to a small apparent LL slope change in a given galaxy if redshift is not accounted for.

With $\mu = 5\log{d} + 25$ ($d$ in Mpc), the ratio of the true distance $d_0$ to the biased distance $d_{\rm{LL}}$ is:
\begin{equation}
\frac{d_0}{d_{\rm{LL}}} = 10^{-0.2\cdot\Delta \mu} = 10^{0.2\cdot\Delta M} \ .
\label{eq:drelbias}
\end{equation}
With Eq.\,\ref{eq:deltamuLL}, Eq.\,\ref{eq:drelbias} becomes:
\begin{equation}
\begin{split}
d_0 &= d_{\rm{LL,lin}} \cdot 10^{0.2 b\log{B} } \\
d_0 &= d_{\rm{LL,quad}} \cdot 10^{0.2 \left[  b_1 \log{B} + b_2  \log{B}  \left( 2 \log{P_{\rm{obs}}^{'}}  - \log{B} \right) \right] }
\end{split}
\label{eq:drelbiasLL}
\end{equation}
for linear and quadratic LLs, respectively. Since $b$, $b_1$, and $b_2$ are all negative, and $\log{B} \ge 1$, this typically means that $d_0 < d_{\rm{LL}}$. We notice that the term $\log{P_{\rm{obs}}^{'}}$ can be negative or positive, depending on pivot period and average $\log{P_{\rm{obs}}}$. In the following, we consider the small difference between $\log{P_{\rm{ref}}}=2.3$ and $\langle \log{P_{\rm{obs}}} \rangle = 2.4$, which corresponds to the case of Miras in NGC\,4258 \citep[`Gold' sample in their Tab.\,6]{Huang2018}.

Figure\,\ref{fig:reldisterr} illustrates RLB as a function of distance assuming $H_0 = 74$\,$\rm{km\,s^{-1}\,Mpc^{-1}}$\ and redshift caused by cosmic expansion only. The slightly steeper slopes of Mira LLs imply a slightly stronger susceptibility to RLB compared to Cepheids. For quadratic LLs, more significant differences  result from possible differences among the average observed and pivot period (if $\log{P_{\rm{obs}}^{'}} \ne 0$).

\begin{figure}
    \centering
    \includegraphics{relDistErr_vs_d_sim}
    \caption{\label{fig:reldisterr} Relative distance error as function of distance in case of  cosmological redshift (considers only expansion). Relative distance errors of $1$, $2$, and $3\%$ are shown by horizontal dotted lines. For Cepheids, we adopt $b = -3.26$ (corresponds to the $H$-band Period-Wesenheit relation using F160W, F555W, and F814W in R+16), for Miras $b_1 = -3.59$, $b_2 = -3.40$, and $\log{P_{\rm{ref}}}=2.3$ from \citet{Huang2018}. If left uncorrected, RLB affects Cepheids at the $1\%$ ($2\%$) level for $d > 62$\,Mpc ($d > 123$\,Mpc). For Miras of mean $\log{P_{\rm{obs}}}=2.4$, the $1\%$ ($2\%$) bias level is reached sooner, at $d > 47.5$\,Mpc ($d > 95$\,Mpc).}
\end{figure}

$H_0$ is measured as the intercept of the Hubble diagram, $a_x$ (cf. Eqs.\,5 and 9 in R+16, subscript $x$ denotes photometric band) via
\begin{equation}
\log{H_0} = \frac{M_x^0 + 5a_x + 25}{5} \ ,\ \mathrm{which\ yields}
\label{eq:H0meas}
\end{equation}
With Eq.\,\ref{eq:H0meas} and $\Delta M = M_{x,\rm{obs}}^0 - M_{x,\rm{true}}^0$, we obtain:
\begin{equation}
\begin{split}
H_{0,\rm{true}} &= H_{0,\rm{LL,lin}} \cdot 10^{-0.2 b\log{B} } \\
H_{0,\rm{true}} &= H_{0,\rm{LL,quad}} \cdot 10^{-0.2 \left[  b_1 \log{B} + b_2  \log{B}  \left( 2 \log{P_{\rm{obs}}^{'}}  - \log{B} \right) \right] }
\end{split}
\label{eq:corrH0}
\end{equation}
for linear and quadratic LLs, respectively, where $H_{0,\rm{true}} > H_{0,\rm{LL}}$ since $b$, $b_1$, $b_2$ all $< 0,$ and $\log{B} = \log{(1 + z_{\rm{obs}})} > 0$. Hence, the Universe is expanding slightly faster than previously reported based on the Cepheid-based distance ladder \citep[R+16,][]{Riess2018,Riess2019,Reid2019}. In \S\ref{sec:H0}, we estimate this effect and the correction for $H_0$, and underline the importance of correcting variability periods for time dilation when measuring distances exceeding $40$\,Mpc using Mira stars with {\it JWST}.

\section{Correcting $H_0$ for RLB}\label{sec:H0}

We now estimate RLB as it applies to the {\it SH0ES} Cepheids-based distance ladder (R+16) and the corresponding $H_0$ measurement. To this end, we compiled measured heliocentric redshifts from NED\footnote{\url{https://ned.ipac.caltech.edu}} as well as other relevant information for the anchor and SN-host galaxies. Table~\ref{tab:table} provides this information for convenience.

\begin{table*}
\centering
\caption{\label{tab:table} Information used to estimate redshift-Leavitt bias for anchor and SN-host galaxies in SH0ES Cepheids-based distance ladder (R+16). The number of Cepheids in each galaxy, $N_{\rm{Cep}}$, approximate distance modulus $\mu$, and PL-relation dispersion $\sigma_{\rm{PL}}$ are all taken from R+16. Heliocentric  redshifts $z_{\rm{obs}}$ are compiled from NED, with original references $\rm{Ref}_{z}$ as follows:
a: \citet{Vaucouleurs1991},
b: \citet{Meyer2004,Wong2006},
c: \citet{Koribalski2004},
d: \citet{Bureau1996},
e: \citet{Krumm1980},
f: \citet{Guthrie1996},
g: \citet{Verheijen2001},
h: \citet{Lauberts1989},
i: \citet{Kent2008},
j: \citet{Grogin1998},
k: \citet{Strauss1992},
l: \citet{Schneider1992},
m: \citet{Richter1987}.
The redshift for the anchor galaxies and SN-host galaxies, weighted by $\sigma_{\rm{PL}}$, are shown above each group. $\Delta z_{\rm{obs,RF}} = z_{\rm{obs}} - z_{\rm{obs,cal}}$ is the redshift difference between each SN-host galaxy and the anchor reference frame. The shift in logarithmic oscillation period, $\Delta \log{P}$ (cf. Eq.\,\ref{eq:deltalogP}), the overestimate of distance modulus $\Delta \mu$ (cf. Eq.\,\ref{eq:deltamuLL}), and the distance bias $\Delta d$ (cf. Eq.\,\ref{eq:drelbias}) are computed using $\Delta z_{\rm{obs,RF}}$.
}
\begin{tabular}{lrrrrrrrrr}
\hline
Galaxy & $N_{\rm{Cep}}$  & $\mu$ & $\langle \sigma_{\rm{PL}} \rangle$ & $z_{\rm{obs}}$ & Ref$_{z}$ & $\Delta z_{\rm{obs,RF}}$ & $\Delta \log{P}$ & $\Delta \mu$ & $\Delta d = d_{0} - d_{\rm{LL}}$ \\
 & & [mag] & [mag] & [$10^{-3}$] & & [$10^{-3}$] & [d] & [mmag] & [Mpc] \vspace{3mm}\\
\hline
\multicolumn{10}{c}{Anchor galaxies, $\langle z_{\rm{obs,cal}} \rangle = 0.48\times 10^{-3}$} \\
\hline
Milky Way & 50  &  $-$    & 0.08 & $0$    &   & $-$ & $-$ & $-$ & $-$ \\
LMC       & 785 &  18.477 & 0.12 & $0.92$ & m & $-$ & $-$ & $-$ & $-$ \\
NGC\,4258 & 139 &  29.397 & 0.15 & $1.49$ & a & $-$ & $-$ & $-$ & $-$ \\
\hline
\multicolumn{10}{c}{SN-host galaxies, $\langle z_{\rm{obs,LL}} \rangle = 4.76\times 10^{-3}$} \\
\hline
M\,101     & 251  &  29.135  & 0.32  & $0.80$ &  a & $0.32$  & 0.007 & 0.2  & -0.001 \\
NGC\,1015  & 14   &  32.497  & 0.36  & $8.77$ &  b & $8.29$  & 0.353 & 11.5 & -0.168 \\
NGC\,1309  & 44   &  32.523  & 0.36  & $7.12$ &  c & $6.64$  & 0.281 & 9.2  & -0.135 \\
NGC\,1365  & 32   &  31.307  & 0.32  & $5.45$ &  d & $4.97$  & 0.209 & 6.8  & -0.057 \\
NGC\,1448  & 54   &  31.311  & 0.36  & $3.90$ &  c & $3.41$  & 0.141 & 4.6  & -0.039 \\
NGC\,2442  & 141  &  31.511  & 0.38  & $4.89$ &  b & $4.41$  & 0.184 & 6.0  & -0.056 \\
NGC\,3021  & 18   &  32.498  & 0.51  & $5.14$ &  a & $4.66$  & 0.195 & 6.4  & -0.093 \\
NGC\,3370  & 63   &  32.072  & 0.33  & $4.27$ &  e & $3.78$  & 0.157 & 5.1  & -0.061 \\
NGC\,3447  & 80   &  31.908  & 0.34  & $3.56$ &  f & $3.07$  & 0.127 & 4.1  & -0.046 \\
NGC\,3972  & 42   &  31.587  & 0.38  & $2.84$ &  g & $2.36$  & 0.095 & 3.1  & -0.030 \\
NGC\,3982  & 16   &  31.737  & 0.32  & $3.70$ &  a & $3.21$  & 0.133 & 4.3  & -0.044 \\
NGC\,4038  & 13   &  31.290  & 0.33  & $5.48$ &  h & $4.99$  & 0.210 & 6.8  & -0.057 \\
NGC\,4424  & 3    &  31.080  & 0.56  & $1.46$ &  i & $0.97$  & 0.035 & 1.2  & -0.009 \\
NGC\,4536  & 33   &  30.906  & 0.29  & $6.03$ &  j & $5.55$  & 0.234 & 7.6  & -0.053 \\
NGC\,4639  & 25   &  31.532  & 0.45  & $3.40$ &  b & $2.91$  & 0.120 & 3.9  & -0.036 \\
NGC\,5584  & 83   &  31.786  & 0.33  & $5.46$ &  c & $4.98$  & 0.209 & 6.8  & -0.072 \\
NGC\,5917  & 13   &  32.263  & 0.38  & $6.35$ &  k & $5.87$  & 0.248 & 8.1  & -0.106 \\
NGC\,7250  & 22   &  31.499  & 0.43  & $3.89$ &  l & $3.41$  & 0.141 & 4.6  & -0.042 \\
UGC\,9391  & 28   &  32.919  & 0.43  & $6.38$ &  l & $5.90$  & 0.249 & 8.1  & -0.144 \\
\hline
\end{tabular}
\end{table*}

We first determine the difference between the mean redshift of LL anchor galaxies and the mean redshift of SN-host galaxies used for measuring $H_0$. The $\sigma_{\rm{PL}}$-weighted average observed redshift of anchor galaxies is $\langle z_{\rm{obs,cal}} \rangle \approx 0.48 \times 10^{-3}$. For Milky Way Cepheids, we adopt $v_r = 0$\,$\rm{km\,s}^{-1}$,\ as expected for a random distribution of radial velocities. Any deviations from null velocity are on the order of $10$\,$\rm{km\,s}^{-1}$\ and can be comfortably neglected.
For SN-host galaxies, the $\sigma_{\rm{PL}}$-weighted average redshift is $\langle z_{\rm{obs,LL}} \rangle \approx 4.76 \times 10^{-3},$ and the average redshift difference between anchor and SN-host galaxies is $\Delta z_{\rm{obs}} = 4.28 \times 10^{-3}$. In the following, we use $\log{B} = \log{(1 + \Delta z_{\rm{obs}})}$ to calculate RLB and the bias of $H_0$.

Figure\,\ref{fig:measuredRLB} shows  $d_0 / d_{\rm{LL}}$ for all 19 {\it SH0ES} SN-host galaxies individually, as well as sample averages including the $\sigma_{\rm{PL}}$-weighted average (dark red solid lines), the average weighted by number of Cepheids, $N_{\rm{cep}}$ (dashed), and the un-weighted average (dotted). For the $\sigma_{\rm{PL}}$-weighted average, we find $\langle d_0/d_{\rm{LL}} \rangle_{\sigma_{\rm{PL}}} \approx 0.99721$. Using the $N_{\rm{Cep}}$-weighted average, we find $\langle d_0/d_{\rm{LL}} \rangle_{N_{\rm{Cep}}} \approx 0.99748$. Any uncertainty contribution due to redshift uncertainties is minimal, since $\langle \sigma_{z}/z \rangle = 0.004$ restricts variations in $\Delta \log{P}$ to $\lesssim 10^{-5}$.

For $H_0 = 73.50 \pm 1.40$\,$\rm{km\,s^{-1}\,Mpc^{-1}}$\ \citep{Reid2019} and $\Delta z_{\rm{obs}}=4.28\times10^{-3}$, Eq.\,\ref{eq:corrH0} yields $H_{0,\rm{true}} = 73.70 \pm 1.40$\,$\rm{km\,s^{-1}\,Mpc^{-1}}$, i.e., an increase of $\Delta H_{0} = 0.20 \pm 0.01$\,$\rm{km\,s^{-1}\,Mpc^{-1}}$. Thus, RLB amounts to $14\%$ of the reported total uncertainty on $H_0$ of $1.90\%$. The small shift in $H_0$ slightly increases the significance of the tension between {\it Planck} and the {\it SH0ES} distance ladder from $4.1\sigma$ to $4.2\sigma$.

Analogously, we estimate biases of $0.19\%$ and $0.20\%$ for recent Mira-based $H_{0}$\ measurements by \citet{Huang2019} that used linear Mira LL slopes of $b =-3.64$ and $-3.35$. In this case, NGC4258 was the sole anchor, and NGC1559 \citep[$z_{\rm{obs,N1559}}=4.35 \times 10^{-3}$]{Koribalski2004} the sole SN-host galaxy.

Of course, the above is a somewhat crude, first-order estimation of the degree by which previous $H_0$ measurements are affected by RLB. Future $H_0$ measurements should take into account the dilation of observed oscillation periods using Eq.\,\ref{eq:deltalogP} to avoid RLB. \S\ref{sec:discussion} highlights why this correction is required to elucidate Hubble tension using a future distance ladder based on more distant Mira stars.

\begin{figure}
    \centering
    \includegraphics{relDistErr_vs_d_yinverted}
    \caption{\label{fig:measuredRLB}Relative distance error incurred due to RLB, cf. Eq.\,\ref{eq:drelbias}. $z_{\rm{obs}}$ was translated to distance assuming $H_0=74$\,$\rm{km\,s^{-1}\,Mpc^{-1}}$; scatter in the relation arises from peculiar velocities. The dark red solid, dashed, and dotted crosses indicate the average values obtained for different weightings. Solid lines: weighted according to $\sigma_{\rm{PL}}$ in Tab.\,\ref{tab:table}, $\langle d_0 / d_{\rm{LL}} \rangle = 0.9972$. Dashed lines: weighted according to $N_{\rm{cep}}$ in Tab.\,\ref{tab:table}. Dotted lines: unweighted mean distance and bias, $\langle d_0 / d_{\rm{LL}} \rangle = 0.9975$.}
\end{figure}

\section{Discussion}\label{sec:discussion}
Time dilation can affect any oscillating star's variability period and lead to distance bias whenever there is a net redshift difference among the LL calibration set and the population where LLs are being applied. Besides the aforementioned Cepheid, RR Lyr, and Mira stars, many other classes of pulsating stars, including $\delta$~Scuti stars,
type-II Cepheids,
and long-period oscillating red giants obey PLRs that render them potentially useful as standard candles \citep[e.g.][]{Ziaali2019,Matsunaga2011,Kiss2003}.

Mira stars are of particular importance due to their high luminosity and large amplitudes for future distance ladder calibration using {\it JWST}. Mira stars observed with {\it JWST} should significantly extend the distance $d$ within which SNe\,Ia luminosity be cross-calibrated. Since volume increases as $d^3,$ and the probability of a SN\,Ia exploding depends on volume, it follows that most new SN-host galaxies observed with {\it JWST} should reside at significantly greater distance than the current {\it SH0ES} SN-host galaxies. Due to the Hubble-Lema\^itre law, the redshift difference among anchor and SN-host galaxies should therefore be enhanced in the era of the Mira-{\it JWST} distance ladder.

Fig.\,\ref{fig:reldisterr} illustrates this effect, and shows that RLB of a sample of Miras with $\langle \log{P_{\mathrm{obs}}} \rangle = 2.5\ (316\,\rm{d})$  exceeds $2\%$ at Coma cluster distances of $100$\,Mpc. Moreover, the intra-cluster velocity dispersion $\sigma_{v_{\rm{pec}},\rm{Coma}} \approx 1000$\,$\rm{km\,s}^{-1}$\ \citep[and references therein]{Sohn2017} could differentially bias distances of Coma cluster galaxies by $1-2\%$,
potentially affecting the interpretation of galaxy cluster scales.

According to Eq.\,\ref{eq:drelbiasLL}, a mismatch between the average period of a sample of Miras and the pivot period of quadratic LLs can further increase RLB.
Assuming $\log{P_{\rm{ref}}}=2.3$, a bias of $1\%$ is reached at $37$, $42$, $48$, $57$, $71$, and $93$\,Mpc for locally calibrated Miras of $\log{P} = 2.6$, $2.5$, $2.4$, $2.3$, $2.2$, and $2.1$, respectively. Alternatively expressed, at $60$\,Mpc, individual Mira stars would be biased by between $0.7\%$ and $1.7\%$, depending on their period.

RLB depends on LL slopes, which depend on photometric passbands. For example, the $H-$band LL in R+16 has slightly shallower slope ($b_H = -3.06$) than the near-IR Wesenheit LL ($b_W = -3.26$). Hence, the $H-$band Cepheid LL is less affected by RLB than the near-IR Wesenheit-LL. Analogously, different kinds of oscillating stars exhibiting shallower LL slopes are also less strongly affected by RLB. For example, the slope of the period term in the $K-$band RR Lyrae PL-metallicity relation has slope of approximately $-2.4$ \citep[e.g.][]{Barth2002,Minniti2003}, reducing the effect compared to Cepheids or Miras.

Thankfully, RLB is easily avoided by correcting observed oscillation periods for time dilation effects. In the continued pursuit of measuring $H_0$ with $1\%$ accuracy, this effect can and must be accounted for.

\section{Conclusions}\label{sec:conclusions}
The Universe's expansion leads to a subtle, distance-dependent dilation of variability periods in oscillating stars. If left uncorrected, this systematic change in variability period biases distance estimates based on Leavitt laws along the distance ladder, because more distant stars are assumed to be more luminous than they truly are. Due to the interplay between redshift and Leavitt law slopes, we term this effect Redshift-Leavitt Bias (RLB).

RLB results in overestimated distances and thus leads to an underestimated value of the Universe's local expansion rate $H_0$. Emulating the {\it SH0ES} distance ladder \citep{Riess2016,Riess2018,Riess2019,Reid2019}, we estimate a bias of $\Delta H_0 / H_0 = 0.27 \pm 0.01\%$. Applying this first-order correction to the  $H_0$ reported by \citet{Reid2019}, we obtain $\Delta H_0 = 0.20 \pm 0.01$\,$\rm{km\,s^{-1}\,Mpc^{-1}}$\ and a de-biased $H_0 = 73.70 \pm 1.40$\,$\rm{km\,s^{-1}\,Mpc^{-1}}$. The slight increase of $H_0$ increases the significance of the Hubble tension between the ``early-universe'' value by the \citet[$H_0 = 67.4 \pm 0.5$\,$\rm{km\,s^{-1}\,Mpc^{-1}}$]{Planck2018H0} and the Cepheids-based distance ladder to $4.2\sigma$.

With oscillating stars being observed at increasing distances, correcting variable-star oscillation periods for time dilation due to redshift becomes increasingly important. For the highly promising Mira stars, we estimate $H_0$ bias of order $2-3\%$ if this effect is not accounted for. Hence, a future Mira-based distance ladder requires correcting variability periods for time dilation.

\begin{acknowledgements}
The author is pleased to thank the anonymous referee for a timely and constructive report, Adam G. Riess and Stefano Casertano for useful comments on an earlier draft, as well as Bruno Leibundgut, Jason Spyromilio, and Steven Kawaler for useful discussions.
This research has made use of NASA's Astrophysics Data System.
\end{acknowledgements}

\bibliographystyle{aa}


\section{Introduction}
In a dynamic stochastic general equilibrium (DSGE) model, satisfaction of time consistency \citep{kydland77} is crucial, especially for a rational expectation equilibrium (REE).

Without stochastic shocks, DSGE models are equivalent to multi-period static models, except for the question of time consistency, which prohibits some of possible equilibria in dual multi-period static models.

This paper intends to demonstrate that under some initial conditions, there is no time-consistent REE in an unexpected way. There is surprise in that conventional dynamic model analysis \citep{slp89} suggests there should be no equilibrium existence issue. The resolution to this `paradox' is easily found: for an economy $E_0$, if we instead take limit $E \rightarrow E_0$, then there exists the limit of model-corresponding equilibria. There is no problem utilizing this limit equilibrium instead. This limit strategy evades the time consistency issue by taking the limit of economies that do not have time consistency issues.

\section{Time consistency issue}
In fashion of a New Keynesian model \citep{woodford03,gali15}, assume that a central bank controls issuance of $B_{it}$, where $i$ refers to each consumer. When $B_{it}>0$, consumer has government bonds, when $B_{it} <0$, consumer is indebted to the central bank. $B_{it}$ is the only way consumers can build up wealth or be indebted. As standard with many DSGE models, an infinite-horizon economy is assumed.

Suppose that the central bank, for whatever reasons, decides to impose $B_{it} = 0$, along with a right interest rate path for the implementation. That is, central bank decides to run an economy as if there is no finance. While the assumption is quite toxic, this is not expected to produce no equilibrium by itself.

Now the specification of consumer $i$ follows.
\begin{equation}
\label{eqn:girutilitymax}
\max_{\{C_{it}, B_{it},..\}}U_i = \max_{\{C_{it}, B_{it},..\}} \sum_{t=0}^{\infty} (\beta_i)^t u_i(C_{it},..)
\end{equation}
where $C_{it}$ refers to consumption good, $\beta_i$ refers to time discount factor and $u_i$ refers to a single-period utility function with $U$ being time-discounted utility function. It is assumed that generally, $\beta_i \neq \beta_j$. Let the budget constraint of each consumer be:
\begin{equation}
\label{eqn:girbudget}
P_t C_{it} + (1+i_t)^{-1} B_{it} +.. \leq  B_{i(t-1)}+..
\end{equation}
where $..$ terms do not contain any of $C_{it}$ and $B_{it}$. $P_t$ refers to price level and $i_t$ is nominal interest rate set by central bank.

The following main equation may be derived from consumer optimization, with the derivation provided in the appendix:
\begin{equation}
\label{eqn:girmain}
\frac{u_j'(C_{jt})}{u_k'(C_{kt})} = \frac{(1-\gamma_{jk})}{\gamma_{jk}}\left(\frac{\beta_k}{\beta_j}\right)^t
\end{equation}
Note that Equation \eqref{eqn:girmain} can be derived even when $B_{it}$ and central bank do not exist - see the appendix.

Suppose that economic conditions remain time-invariant. For example, there is zero technology factor growth, there is no capital accumulation in an economy as standard in a basic New Keynesian model \citep{woodford03,gali15} and so on. As aforementioned, $B_{it} = 0$, and there are infinitely many time periods. Then Equation \eqref{eqn:girmain} creates the time inconsistency issue not found in a dual multi-period static model.

Since economic conditions remain same across periods and there is no `end' in time, the left-hand side of Equation \eqref{eqn:girmain} should remain constant across time. This is impossible when $\beta_k \neq \beta_j$.

\subsection{Limit economy}
Note that the `initial condition' requirement for the time inconsistency result is relatively strong. First, $B_{it} = 0$ was required. Second, other economic conditions also are assumed to remain same across periods. An infinite horizon also plays a role - however, technically, the time inconsistency result itself can be created even in a finite horizon circumstance.

If any of these conditions is not satisfied, then Equation \eqref{eqn:girmain} cannot be asserted to generate the time consistency issue.

We may then choose to approach an economy with the time consistency issue as a limit of neighboring economies that do have time-consistent equilibria. A limit of equilibria then can be asserted to be an equilibrium for a limit economy (the economy with the time consistency issue) as well.

Therefore, in practical sense, an economy with the time consistency issue may safely be treated as if it has an equilibrium. In case of the example economy, even if fiscal authority does not actually exercise its power, its potential power to reallocate $B_{it}$ helps to entirely avoid theoretical issues.

\section{Conclusion}
The lesson is that there must be significant care that must be taken of when dealing with rational expectation equilibria (REE). It is well-known that not all REE are meaningful or learnable. \citep{evans01,evans18} The direction also goes from non-existence as well - non-existence of REE has to be carefully considered.

For REE non-existence driven by a time consistency issue induced from consumer heterogeneity, it is easy to construct nearby economies that do not have time consistency issues, thereby evading the issue. In such a case, it is not economics-wise meaningful to declare that there exists no REE.

\bibliographystyle{aea}