text:
\section{Background}

If $A$ is a basis of a free group $F$, we often write $F = F(A)$ and
we represent the elements of $F$ as reduced words over the alphabet
$A$.  More precisely, we consider the set of all words on the
symmetrized alphabet $\tilde A = A \cup A^{-1}$, where $A^{-1} = \{a^{-1}
\mid a\in A\}$ is a set that is disjoint from $A$, equipped with an
explicit bijection with $A$, namely $a\mapsto a^{-1}$.  It is customary
to extend the mapping $u \mapsto u^{-1}$ to all words $u\in \tilde
A^{*}$ by letting $(a^{-1})^{-1} = a$ for each $a\in A$, $1^{-1} = 1$
(where 1 denotes the empty word) and $(a_{1}a_{2}\cdots a_{n})^{-1} =
a_{n}^{-1} \cdots a_{2}^{-1} a_{1}^{-1}$ for all $a_{1},\ldots,a_{n}\in
\tilde A$.  A word in $\tilde A^{*}$ is \textit{reduced} if it
contains no factor of the form $aa^{-1}$ or $a^{-1} a$ with $a\in A$,
and it is well known that $F$ can be identified with the set of
reduced words over $A$.  We denote by $\rho$ the map that assigns to
each word $u$ the corresponding reduced word $u\rho \in F(A)$,
obtained by iteratively deleting all factors of the form $aa^{-1}$ or
$a^{-1} a$ ($a\in A$).

\subsection{On inverse automata}

We describe the main tool for the representation of subgroups of free
groups in terms of automata (see \cite{PerrinHB}). Readers less
familiar with this terminology may think of automata as edge-labeled
directed graphs.

An \textit{automaton} on alphabet $A$ is a triple of the form $\mathcal{A} =
(Q, q_{0}, E)$ where $Q$ is a finite set called the \textit{state}
set, $q_{0}\in Q$ is the \textit{initial state}, and $E \subseteq Q
\times A \times Q$ is the set of \textit{edges}, or
\textit{transitions}.  A transition $(p,a,q)$ is said to be from state
$p$, to state $q$, with label $a$.  The \textit{label of a path} in
$\mathcal{A}$ (a finite sequence of consecutive transitions) is the sequence
of the labels of its transitions, a word on alphabet $A$, that is, an
element of the free monoid $A^*$.  We write $p \mapright u q$ if there
is a path from state $p$ to state $q$ with label $u$.  The language
accepted by $\mathcal{A}$ is the set $L(\mathcal{A})$ of all words in $A^*$ which
label a path in $\mathcal{A}$ from $q_{0}$ to $q_{0}$.

This definition of automata leads naturally to the definition of a
\textit{homomorphism} $\phi$ from an automaton $\mathcal{A} = (Q,q_{0},E)$
to an automaton $\mathcal{A}' = (Q',q'_{0},E')$ (over the same alphabet
$A$): $\phi$ is a mapping from $Q$ to $Q'$ such that $\phi(q_{0}) =
q'_{0}$, and such that whenever $(p,a,q)\in E$, we also have
$(\phi(p),a,\phi(q)) \in E'$.  The homomorphism $\phi$ is an
\textit{isomorphism} if it is a bijection and if $\phi^{-1}$ is also a
homomorphism.

The automaton $\mathcal{A}$ is called \textit{deterministic} if no two
distinct edges with the same initial state bear the same label, that
is,
$$(p,a,q), (p,a,q') \in E \Longrightarrow q = q'.$$
The automaton is called \textit{trim} if every state $q\in Q$ lies in
some path from $q_{0}$ to $q_{0}$.

In the sequel, we consider automata where the alphabet is symmetrized,
that is, the alphabet is of the form $\tilde A = A \cup A^{-1}$.  We
say that $\mathcal{A}$ is \textit{dual} if for each $a\in A$, there is an
$a$-labeled edge from state $p$ to state $q$ if and only if there is
an $a^{-1}$-labeled edge from $q$ to $p$,
$$(p,a,q) \in E \Longleftrightarrow (q,a^{-1},p)\in E.$$
Let us immediately record the following fact.

\begin{fact}\label{fact 11}
    Let $\mathcal{A}$ be a deterministic dual automaton.  If a word $u$
    labels a path in $\mathcal{A}$ from state $p$ to state $q$, then so does
    the corresponding reduced word $u\rho$.
    Moreover $L(\mathcal{A})$ is a submonoid of $\tilde A^*$ and
    $L(\mathcal{A})\rho$ is a subgroup of $F(A)$.
\end{fact}

Now let $\mathcal{A} = (Q,q_{0},E)$ be a trim dual automaton and let $p,q\in
Q$ be states of $\mathcal{A}$. If $w = a_{1}\cdots a_{n}\in \tilde A^*$
is a non-empty word, the expansion of $\mathcal{A}$ by $(p,w,q)$ is the
automaton obtained from $\mathcal{A}$ by adding $n - 1$ vertices
$q_{1},\ldots,q_{n-1}$ and $2n$ edges
$$p \mapright{a_1} q_1 \mapright{a_2} \ldots \mapright{a_{n-1}}
q_{n-1} \mapright{a_{n}} q$$
and
$$q \mapright{a_{n}^{-1}} q_{n-1} \mapright{a_{n-1}^{-1}} \ldots
\mapright{a_2^{-1}}
q_{1} \mapright{a_1^{-1}} p.$$
Note that this automaton is still trim and dual. Moreover, if $p = q
= q_{0}$, then we observe the following.

\begin{prpstn}\label{H(A)}
    Let $\mathcal{A} = (Q,q_{0},E)$ be a trim dual automaton, let $H =
    L(\mathcal{A})\rho$ and let $w$ be a non-empty word. If $\mathcal{B}$ is the
    expansion of $\mathcal{A}$ by $(q_{0},w,q_{0})$, then $L(\mathcal{B})\rho$ is
    the subgroup generated by $H$ and $w\rho$, that is, $L(\mathcal{B})\rho =
    \langle H, w\rangle$.
\end{prpstn}

\begin{proof}
Let $\mathcal{C}$ be the dual automaton consisting of the state $q_{0}$ and
the states and edges added to $\mathcal{A}$ in the expansion. It is
immediate that $L(\mathcal{C})\rho$ is the subgroup of $F(A)$ generated by
$w\rho$.

If $u\in L(\mathcal{B})$, we can factor a path $q_{0} \mapright u q_{0}$
according to the successive visits of state $q_{0}$. The resulting
factorization of $u$ makes it clear that $u$ is a product of elements
of $L(\mathcal{A})$ and $L(\mathcal{C})$. Thus, $L(\mathcal{B})$ is the submonoid
generated by $L(\mathcal{A}) \cup L(\mathcal{C})$, and $L(\mathcal{B})\rho$ is the
subgroup generated by $L(\mathcal{A})\rho$ and $w\rho$. This concludes the
proof.
\end{proof}

\subsection{Reduced inverse automata}\label{representation}

The automaton $\mathcal{A}$ is called \textit{inverse} if it is
deterministic, trim and dual.  It is \textit{reduced} if every state
$q\in Q$ lies in some path from $q_{0}$ to $q_{0}$, labeled by a
(possibly empty) reduced word.  We note the following result, a cousin
of \cite[Thm 1.16]{Stephen}.

\begin{prpstn}\label{prop unique}
    If $\mathcal{A}$ and $\mathcal{B}$ are reduced inverse automata such that
    $L(\mathcal{A})\rho = L(\mathcal{B})\rho$, then $\mathcal{A}$ and $\mathcal{B}$ are
    isomorphic.
\end{prpstn}

\begin{proof}
Let $\mathcal{A} = (Q,q_{0},E)$ and $\mathcal{B} = (P,p_{0},D)$ be reduced
inverse automata such that $L(\mathcal{A})\rho = L(\mathcal{B})\rho$. We
construct an isomorphism $\phi$ between $\mathcal{A}$ and $\mathcal{B}$ as follows.
We first let $\phi(q_{0}) = p_{0}$.

Let $q\in Q$.  Since $\mathcal{A}$ is reduced, there exist reduced words $u$
and $v$ such that the word $uv$ is reduced, $q_{0} \mapright{u} q$ and
$q\mapright{v} q_{0}$.  Then $uv\in L(\mathcal{A})\rho$, so $uv \in
L(\mathcal{B})\rho$, and hence $uv\in L(\mathcal{B})$ by Fact~\ref{fact 11}.  Thus
$uv$ labels a path in $\mathcal{B}$ from $p_{0}$ to $p_{0}$, and we let
$\phi(q)$ be the unique state in $P$ such that $p_{0} \mapright{u}
\phi(q) \mapright{v} p_{0}$.

We first verify that $\phi$ is well defined.  Suppose that $uv$ and
$u'v'$ are reduced words such that $q_{0} \mapright{u} q \mapright{v}
q_{0}$ and $q_{0} \mapright{u'} q \mapright{v'} q_{0}$ in $\mathcal{A}$.  We
want to show that if $p_{0} \mapright{u} p \mapright v p_{0}$ and
$p_{0} \mapright{u'} p' \mapright{v'} p_{0}$ in $\mathcal{B}$, then $p =
p'$.  We note that $u'v$ labels a path from $q_{0}$ to $q_{0}$ in
$\mathcal{A}$.  If $u'v$ is a reduced word, then by the same reasoning as
above, $u'v$ labels a path in $\mathcal{B}$ from $p_{0}$ to $p_{0}$, say,
$p_{0} \mapright{u'} p'' \mapright v p_{0}$ and the deterministic
property of $\mathcal{B}$ implies that $p' = p'' = p$.

If $u'v$ is not reduced, and $a$ is the first letter of $v$, then the
last letter of $u'$ is $a^{-1}$ while the last letter of $u$ is not
$a^{-1}$. Therefore $u'u^{-1}$ is reduced, $u'u^{-1} \in L(\mathcal{A})$ and
again, there is a path in $\mathcal{B}$ of the form $p_{0} \mapright{u'} p''
\mapright{u^{-1}} p_{0}$. By determinism, it follows that $p' = p'' =
p$.

This shows that $\phi$ is well defined.  A dual construction yields a
well-defined mapping $\psi$ from $P$ to $Q$ such that, whenever $p_{0}
\mapright u p \mapright v p_{0}$ in $\mathcal{B}$ and $uv$ is a reduced
word, then $q_{0} \mapright u \psi(p) \mapright v q_{0}$ in $\mathcal{A}$.
Using the determinism of $\mathcal{A}$ and $\mathcal{B}$, it is now immediate that
$\psi\circ \phi$ is the identity on $Q$ and $\phi\circ \psi$ is the
identity on $P$.

There remains to verify that $\phi$ and $\phi^{-1}$ are homomorphisms.
The case of $\phi^{-1}$ is dual of that of $\phi$ and we treat only the
latter.  That is, we want to show that if $(q,a,q')$ is a transition
in $\mathcal{A}$, then $(\phi(q),a,\phi(q'))$ is a transition in $\mathcal{B}$.
Let $uv$ and $u'v'$ be reduced words such that $q_{0} \mapright u q
\mapright v q_{0}$ and $q_{0} \mapright{u'} q' \mapright{v'} q_{0}$.
In particular, we have $p_{0} \mapright u
\phi(q) \mapright v p_{0}$ and $p_{0} \mapright{u'} \phi(q')
\mapright{v'} p_{0}$ in $\mathcal{B}$.

\begin{center}
    \begin{picture}(60,38)(0,-34)

	\node[NLangle=0.0,Nmr=2.0](n0)(0.0,-15.0){$q_0$}

\node[NLangle=0.0,Nmr=2.0](n3)(30.0,0.0){$q$}

\node[NLangle=0.0,Nmr=2.0](n4)(30.0,-30.0){$q'$}

\node[NLangle=0.0,Nmr=2.0](n5)(60.0,-15.0){$q_0$}

\drawedge[ELdist=3.0](n0,n3){$u$}

\drawedge[ELdist=3.0](n3,n5){$v$}

\drawedge[ELdist=3.5](n3,n4){$a$}

\drawedge[ELside=r,ELdist=4.0](n0,n4){$u'$}

\drawedge[ELside=r,ELdist=4.0](n4,n5){$v'$}

\end{picture}
\end{center}

If $uav'$ is reduced, then in $\mathcal{B}$, there is a path from $p_{0}$ to
$p_{0}$ labeled $uav'$, and by determinism, there is a transition
$(\phi(q),a,\phi(q'))$. If $uav'$ is not reduced, then either $ua$ is
not reduced or $av'$ is not reduced. If $ua$ is not reduced, then $u =
u_{1}a^{-1}$ and by determinism, $q_{0} \mapright{u_{1}} q'$. As in the
first part of the proof, it follows that at least one of $u_{1}v'$ and
$u_{1}{u'}^{-1}$ is reduced, so $p_{0} \mapright{u_{1}} \phi(q')$ in
$\mathcal{B}$ and hence there is a transition $(\phi(q),a,\phi(q'))$.
The case where $av'$ is not reduced is handled symmetrically, and
this concludes the proof.
\end{proof}

Let $H$ be a subgroup of $F(A)$.  Say that an automaton $\mathcal{A}$
\textit{on alphabet $A$ represents $H$} if $\mathcal{A}$ is reduced and
inverse and if $L(\mathcal{A})\rho = H$.  Proposition~\ref{prop unique}
shows that there exists at most one such automaton, and we denote it
by $\Gamma_{A}(H)$ if it exists.  We now discuss the existence and the
construction of $\Gamma_{A}(H)$ when $H$ is finitely generated.  (As
it turns out, $\Gamma_{A}(H)$ always exists, but our interest in this
paper is restricted to the finite rank case.)

Let $\mathcal{A}$ be an automaton and let $p, q$ be distinct states of
$\mathcal{A}$. The automaton obtained from $\mathcal{A}$ by identifying states $p$
and $q$ is constructed as follows: its state set is
$Q\setminus\{p,q\}\cup \{n\}$, where $n$ is a new state; its initial
state is $q_{0}$ (or $n$ if $p$ or $q$ is equal to $q_{0}$); and its
set of transitions is obtained from $E$ by replacing everywhere $p$ and
$q$ by $n$. If $\mathcal{A}$ is trim or dual, then so is the automaton
obtained from $\mathcal{A}$ by identifying a pair of states.

Now let $\mathcal{A}$ be a dual automaton.  If $\mathcal{A}$ is not deterministic,
there exist transitions $(r,a,p)$ and $(r,a,q)$ with $p\ne q$ and
$a\in \tilde A$.  Identifying $p$ and $q$ yields a new dual automaton
$\mathcal{B}$, and we say that $\mathcal{B}$ is obtained from $\mathcal{A}$ by an
\textit{elementary reduction of type 1}.

\begin{fact}\label{reduction1}
    Let $\mathcal{A}$ be a dual automaton and let $\mathcal{B}$ be obtained from
    $\mathcal{A}$ by an elementary reduction of type 1. Then $L(\mathcal{A})\rho =
    L(\mathcal{B})\rho$.
\end{fact}

\begin{proof}
It is easily seen that $L(\mathcal{A}) \subseteq L(\mathcal{B})$. For the converse,
we use the notation given above: in $\mathcal{B}$, the states $p$ and $q$ of
$\mathcal{A}$ are replaced with a new state $n$. Let $u\in L(\mathcal{B})$. Then
there exists a path labeled $u$ from the initial state of $\mathcal{B}$ (say,
$q_{0}$) to itself. If that path does not visit state $n$, then $u$
also labels a path from $q_{0}$ to itself in $\mathcal{A}$ and hence $u\in
L(\mathcal{A})$.

If that path does visit state $n$, we consider the
factorization of $u$ given by the passage of that path through $n$: we
have $u = u_{0}u_{1}\cdots u_{r}$, $r\ge 1$ and
$$q_{0} \mapright{u_{0}} n \mapright{u_{1}} n \cdots n \mapright{u_{r}}
q_{0}.$$
It follows that in $\mathcal{A}$, $u_{i}$-labelled paths exist, with end
states $p$ or $q$ (or $q_{0}$).  Then one of $u_{0}$ and $u_{0}a^{-1}
a$ labels a path in $\mathcal{A}$ from $q_{0}$ to $q$.  Similarly, one of
$u_{r}$ and $a^{-1} au_{r}$ labels a path from $q$ to $q_{0}$ (making
due allowance if $p$ or $q$ is equal to $q_{0}$).  And for each $1\le
i \le r$, one of $u_{i}$, $a^{-1} au_{i}$, $u_{i}a^{-1} a$ and $a^{-1}
au_{i}a^{-1} a$ labels a path in $\mathcal{A}$ from $q$ to $q$.  Therefore,
there exists a path in $\mathcal{A}$ of the form $q_{0} \mapright v q_{0}$
such that $u\rho = v\rho$, which concludes the proof.
\end{proof}

Now assume that $\mathcal{A}$ is a deterministic dual automaton.

\begin{fact}\label{reduction11}
    Let $\mathcal{A}$ be an inverse automaton.  Then $\mathcal{A}$ is non-reduced
    if and only if there exist states $q\ne q_{0}$ and $p$, and a
    letter $a\in \tilde A$ such that the only transitions of $\mathcal{A}$
    involving $q$ are $(p,a,q)$ and $(q,a^{-1},p)$.

    In graph-theoretic terms, this means that $\mathcal{A}$ is reduced if
    and only if no vertex of $\mathcal{A}$ has degree one (more precisely:
    no vertex is adjacent to a single $A$-labeled edge), except possibly
    $q_{0}$.
\end{fact}

\begin{proof}
By definition, $\mathcal{A}$ is not reduced if and only if there exists a
state $q$ that does not lie on any path from $q_{0}$ to itself,
labeled by a reduced word.  We first observe that the state $q$ cannot
be equal to $q_{0}$ since the empty word is reduced, and labels a path
from $q_{0}$ to itself.  Suppose now that there exist reduced words
$u,v$ with distinct last letters, labeling paths from $q_{0}$ to $q$:
then $uv^{-1}$ is a reduced word, labeling a path from $q_{0}$ to
itself and visiting $q$.  On the other hand, if every reduced word
labeling a path from $q_{0}$ to $q$ ends with, say, letter $a\in
\tilde A$, then every path from $q_{0}$ to itself visiting $q$ has a
non-reduced label.  Thus $\mathcal{A}$ is not reduced if and only if there
exists a state $q\ne q_{0}$ and every reduced word labeling a path
from $q_{0}$ to $q$ ends with the same letter.  By determinism, this
is equivalent to the existence of another state $p$ such that the
transitions involving $q$ are $(p,a,q)$ and $(q,a^{-1},p)$.
\end{proof}

Let $\mathcal{A}$ be inverse and not reduced, and let $a,p,q$ be as in
Fact~\ref{reduction11}.  If $\mathcal{B}$ is obtained from $\mathcal{A}$ by
omitting state $q$ and the transitions involving it, we observe that
$\mathcal{B}$ is again an inverse automaton, and we say that $\mathcal{B}$ is
obtained from $\mathcal{A}$ by an \textit{elementary reduction of type 2}.

\begin{fact}\label{reduction2}
    Let $\mathcal{A}$ be an inverse automaton and let $\mathcal{B}$ be obtained
    from $\mathcal{A}$ by an elementary reduction of type 2.  Then
    $L(\mathcal{A})\rho = L(\mathcal{B})\rho$.
\end{fact}

\begin{proof}
Let $a$ be a letter and let $p,q$ be states of $\mathcal{A}$ as in
Fact~\ref{reduction11}, and let us assume that $\mathcal{B}$ is obtained
from $\mathcal{A}$ by omitting state $q$ and the transitions involving it.
It is easily seen that $L(\mathcal{B}) \subseteq L(\mathcal{A})$.  Conversely, let
$u\in L(\mathcal{A})$.  By Fact~\ref{fact 11}, $u\rho\in L(\mathcal{A})$.  Now
Fact~\ref{reduction11} shows that the path $q_{0} \mapright u\rho
q_{0}$ in $\mathcal{A}$ cannot visit state $q$, since $u\rho$ is a reduced
word.  It follows that this path is also a path in $\mathcal{B}$, $u\rho\in
L(\mathcal{B})$ and hence $u\rho\in L(\mathcal{B})\rho$.
\end{proof}

Let $\mathcal{A}$ be a trim, dual automaton, and let $\mathcal{B}$ be an automaton
obtained by iteratively performing elementary reductions, first of
type 1 until the automaton is inverse, and then of type 2 until none
is possible.  Then $\mathcal{B}$ is a reduced inverse automaton, we write
$\mathcal{B} = \mathcal{A}\rho$ and we say that $\mathcal{B}$ is obtained from $\mathcal{A}$
by reduction.  Moreover, Facts~\ref{reduction1} and \ref{reduction2}
show that $L(\mathcal{A})\rho = L(\mathcal{B})\rho$.

This leads directly to the well-known algorithm to construct a reduced
inverse automaton representing a given finitely generated subgroup
$H$.  Let $h_{1},\ldots,h_{n}$ be generators of $H$, and let us
consider the automaton obtained from the trivial automaton (one vertex
$q_{0}$, no transitions) by performing successively expansions by
$(q_{0}, h_{i}, q_{0})$ ($1\le i\le n$) and then reducing the
automaton.  It follows from Propositions~\ref{H(A)} and~\ref{prop
unique} that the resulting automaton is $\Gamma_{A}(H)$.  Note that it
does not matter which set of generators of $H$ was used, nor in which
order the elementary reductions were performed.

\begin{rmrk}
    This construction of $\Gamma_{A}(H)$ is well known, and can be
    described in many different ways, notably in terms of immersions
    over the bouquet of circles (Stallings \cite{Stallings}) or of
    closed inverse submonoids of a free inverse monoid (Margolis and
    Meakin \cite{MargolisMeakin}).
\end{rmrk}

\begin{fact}\label{end of sec 12}
    There is a well-known converse to the above construction: if
    $\mathcal{A}$ is a reduced inverse automaton and $H = L(\mathcal{A})\rho$,
    then $H$ has finite rank and a basis for $H$ can be computed as
    follows (see Stallings \cite{Stallings}).  Given a spanning tree
    $T$ of the (graph underlying the) automaton $\mathcal{A}$, for each
    state $p$, let $u_{p}$ be the reduced word labeling a path from
    $q_{0}$ to $p$ inside the tree $T$.  For each transition $e =
    (p,a,q)$, let $b_{e} = u_{p}au_{q}^{-1}$: then a basis of $H$
    consists of the elements $b_{e}$, where $e$ runs over the
    transitions $e = (p,a,q)$ not in $T$ and such that $a\in A$.

    We note that, given a finite set $h_{1},\ldots,h_{n}$ of elements
    of $F(A)$ with total length $\ell = \sum_{i}|h_{i}|$, one can
    construct $\Gamma_{A}(H)$ in time at most $O(\ell^2)$ and
    $\Gamma_{A}(H)$ has $v \le \ell - n + 1$ states.  Moreover,
    finding a basis of $H$ can be done in time at most $O(v^2)$ ($O(v
    \log^*v)$ according to Touikan's announcement~\cite{Touikan}), and
    the rank of $H$ is equal to $e-v+1$, where $e$ is the number of
    edges in $\Gamma_{A}(H)$.
\end{fact}

\subsection{On the complexity of Whitehead and other
algorithms}\label{whitehead}

It is well known that one can decide, given a subgroup $H$ of a finite
rank free group $F$, whether $H$ is a free factor of $F$. We briefly
describe here the main known algorithms and discuss their complexity.

Let $H$ be a finitely generated subgroup of a free group $F$ of rank
$r$, with basis $A$. Let $h_{1},\ldots,h_{n}$ be a generating set of
$H$. By the results summarized in Fact~\ref{end of sec 12}, up to a
quadratic time computation, we may assume that $h_{1},\ldots,h_{n}$ is
a basis of $H$. Let $\ell = |h_{1}| + \cdots + |h_{n}|$ be the total
length of the tuple $(h_{i})_{i}$, and let $d = r - n$ be the rank
difference between $F$ and $H$ -- which we assume to be positive, since
$H$ can be a proper free factor of $F$ only if $n < r$.

Federer and J\'onsson (see \cite[Prop. I.2.26]{LS}) gave the following
observation and decision procedure: $H$ is a free factor of $F$ if and
only if there exist $d$ words $h_{n+1},\ldots,h_{r}$, each of length at
most $\max\{|h_{i}| \mid 1\le i\le n\}$, such that $h_{1},\ldots,h_{r}$
generate the whole of $F$. The resulting algorithm requires testing
every suitable $d$-tuple of reduced words on alphabet $A$. Each of
these tests (does a certain $r$-tuple of words generate $F$?) takes
time polynomial in the total length of the $r$-tuple, and hence in
$d\ell$. However, the number of tests is $O(r^{d\ell})$, which is
exponential in $\ell$ and $d$.

This approach leads to the following.

\begin{fact}
    Deciding whether $H\le_{\sf ff} K$ is in $NP$, with respect to $d\ell$.
\end{fact}

\begin{proof}
To verify that $H\le_{\sf ff} K$, we need to guess $d$ words of length at most
$\ell$, and verify that together with $H$, they generate $F$, which can
be done in $O((d\ell)^2)$.
\end{proof}

Another approach is based on the use of Whitehead automorphisms.  We
refer the readers to \cite[Sec.  I.4]{LS} for the definition of these
automorphisms, it suffices to note here that the set $W$ of Whitehead
automorphisms of $F$ which do not preserve length, has exponential
cardinality (in terms of $r$).  A result of Whitehead \cite[Prop.
I.4.24]{LS} shows the following: if there exists an automorphism
$\phi$ of $F$ such that the total length of $(\phi(h_{i}))_{i}$ is
strictly less than $\ell$, then there exists such an automorphism in
$W$.  In particular, an algorithm to compute the minimum total length
of an automorphic image of the tuple $(h_{i})_{i}$ consists in
repeatedly applying the following step: try every automorphism
$\psi\in W$ until the total length of $(\psi(h_{i}))_{i}$ is strictly
less than the total length of $(h_{i})_{i}$; if such a $\psi$ exists,
replace $(h_{i})_{i}$ by $(\psi(h_{i}))_{i}$; otherwise, stop and
output the total length of $(h_{i})_{i}$.

This applies to the decision of the free factor relation since $H\le_{\sf ff}
F$ if and only if there exists an automorphism $\phi$ mapping a basis
of $H$ to a subset of $A$.  Thus an algorithm consists in first
computing a basis of $H$, and assuming that $h_{1},\ldots,h_{n}$ is a
basis, verifying whether the minimum total length of
$(\phi(h_{i}))_{i}$ when $\phi$ runs over the automorphisms of $F$, is
exactly $n$.  This algorithm may require $O((\ell-n)\form{card}(W))$ steps,
each of which consists in computing the image of a tuple of length at
most $\ell$ under an automorphism, and hence has complexity $O(\ell)$.
Thus the time complexity of this algorithm is $O(\ell^2\ \form{card}(W))$,
which is quadratic in $\ell$ and exponential in $r$.

A variant of this algorithm was established by Gersten \cite{Gersten},
who showed that a similar method applies to find the minimum size
(number of vertices) of $\Gamma_{A}(\phi(H))$, when $\phi$ runs over
the automorphisms of $F(A)$. It is clear that $H$ is a free factor of
$F(A)$ if and only if there exists an automorphism $\phi$ such that
$\Gamma_{A}(\phi(H))$ has a single vertex. The time complexity is
computed as above, where the number of vertices of $\Gamma_{A}(H)$ is
substituted for the total length of a basis for $H$. As noted earlier,
this number of vertices is usually substantially smaller than the total
length of a basis, but the two values are linearly dependent, so the
order of magnitude of the time complexity is not modified, notably the
exponential dependence in $r$.

\begin{rmrk}
    The discussion of Whitehead's algorithm above concerns only the
    so-called \textit{easy part} of the algorithm (see for instance
    Kapovich, Miasnikov and Shpilrain \cite{KSS}).  Results by
    Miasnikov and Shpilrain \cite{MS}, Khan \cite{Kh}, and most
    recently by Donghi Lee \cite{DL} on the possible polynomial
    complexity of the \textit{hard part} of the algorithm also
    consider the rank of the ambient free group as a constant, and do
    not question the actual exponential dependence in that parameter.
\end{rmrk}

\section{A careful look at the expansions and reductions of inverse
automata}\label{careful}

Let $\mathcal{A}$ be a reduced inverse automaton.

Let $\mathcal{B}$ be obtained from $\mathcal{A}$ by performing an expansion, say by
$(p,w,q)$, and then reducing the resulting automaton. In this
situation, we write $\mathcal{A} \longrightarrow_{{\sf exp}}^{(p,w,q)} \mathcal{B}$, or simply $\mathcal{A}
\longrightarrow_{{\sf exp}} \mathcal{B}$. We distinguish two special cases.

$\bullet$ If the reduction following the expansion does not involve
identifying or omitting states of $\mathcal{A}$, or equivalently if $\mathcal{A}$
embeds in $\mathcal{B}$, we say that $\mathcal{B}$ is obtained from $\mathcal{A}$ by a
\textit{reduced expansion} and we write $\mathcal{A} \longrightarrow_{{\sf re}}^{(p,w,q)} \mathcal{B}$
or $\mathcal{A} \longrightarrow_{{\sf re}} \mathcal{B}$.

$\bullet$ If the states $p$ and $q$ are equal to the distinguished
state $q_{0}$ of $\mathcal{A}$, we say that $\mathcal{B}$ is obtained from $\mathcal{A}$
by an \textit{e-step} and we write $\mathcal{A} \longrightarrow_{{\sf e}}^{w} \mathcal{B}$, or simply
$\mathcal{A} \longrightarrow_{{\sf e}} \mathcal{B}$.

Finally, let $\mathcal{B}$ be obtained from $\mathcal{A}$ by identifying two
distinct vertices $p$ and $q$, and then reducing the resulting
automaton. Then we say that $\mathcal{B}$ is obtained from $\mathcal{A}$ by an
\textit{i-step} and we write $\mathcal{A} \longrightarrow_{{\sf i}}^{p = q} \mathcal{B}$, or simply
$\mathcal{A} \longrightarrow_{{\sf i}} \mathcal{B}$.

Note that if $\mathcal{A} \longrightarrow_{{\sf exp}}
\mathcal{B}$, $\mathcal{A} \longrightarrow_{{\sf re}} \mathcal{B}$, $\mathcal{A} \longrightarrow_{{\sf e}} \mathcal{B}$ or $\mathcal{A} \longrightarrow_{{\sf i}}
\mathcal{B}$, then $\mathcal{B}$ is a reduced inverse automaton.

We first record a few facts.

\begin{fact}\label{fact1}
    Let $u$ be a reduced word labeling a path in $\mathcal{A}$ from a state
    $p$ to a state $p'$, and from a state $q$ to a state $q'$,

    $$p \mapright{u} p', \quad q \mapright{u} q'.$$

    By definition of the reduction of dual automata, the identification
    of $p$ and $q$ implies that of $p'$ and $q'$, and the converse
    holds as well. Thus $\mathcal{A} \longrightarrow_{{\sf i}}^{p = q} \mathcal{B}$ if and only if
    $\mathcal{A} \longrightarrow_{{\sf i}}^{p' = q'} \mathcal{B}$.
\end{fact}

Let us now examine in detail the effect of an operation of the form
$\longrightarrow_{{\sf exp}}$.

\begin{fact}\label{fact2}
    Let $p, q$ be states of $\mathcal{A}$ and let $w$ be a non-empty reduced
    word. Let $u$ be the longest prefix of $w$ that can be read in
    $\mathcal{A}$ from state $p$, and let $v$ be the longest suffix of $w$
    that can be read in $\mathcal{A}$ to state $q$ (that is, $v^{-1}$ is the
    longest prefix of $w^{-1}$ that can be read in $\mathcal{A}$ from state
    $q$). We distinguish two cases:

    \begin{itemize}
	\item[(1)] If $|u| + |v| < |w|$, then $w = uw'v$ for some
	non-empty reduced word $w'$. If we let $p'$ (resp. $q'$) be the
	end (resp. start) state of the path labeled $u$ (resp. $v$) and
	starting in $p$ (resp. ending in $q$),

	$$p \mapright{u} p' \mapright{w'} q' \mapright{v} q,$$

	then the reduction process on the result of the expansion of
	$\mathcal{A}$ by $(p,w,q)$ identifies the $|u|$ first edges and the
	$|v|$ last edges of the added path with existing edges of
	$\mathcal{A}$, so that $\mathcal{A} \longrightarrow_{{\sf exp}}^{(p,w,q)} \mathcal{B}$ if and only
	if $\mathcal{A} \longrightarrow_{{\sf exp}}^{(p',w',q')} \mathcal{B}$ and the latter is a
	reduced expansion.

	\item[(2)] If $|u| + |v| \ge |w|$, then there exist words
	$x,y,z$, possibly empty, such that $u = xy$, $v = yz$ and $w =
	xyz$.  Let $p', p'', q', q''$ be the states of $\mathcal{A}$ defined
	by the following paths

	$$p \mapright{x} p' \mapright{y} p'', \quad q' \mapright{y} q''
	\mapright{z} q.$$

	Then $\mathcal{A} \longrightarrow_{{\sf exp}}^{(p,w,q)} \mathcal{B}$ if and only if $\mathcal{A}
	\longrightarrow_{{\sf i}}^{p' = q'} \mathcal{B}$, if and only if $\mathcal{A} \longrightarrow_{{\sf i}}^{p'' =
	q''} \mathcal{B}$.
    \end{itemize}
\end{fact}

We derive from Fact~\ref{fact2} the following statement.

\begin{prpstn}\label{L04}
    Let $\mathcal{A}$ and $\mathcal{B}$ be inverse automata. If $\mathcal{A} \longrightarrow_{{\sf e}}^{w}
    \mathcal{B}$, then $\mathcal{A} \longrightarrow_{{\sf i}} \mathcal{B}$ or $\mathcal{A} \longrightarrow_{{\sf re}}^{(p,u,q)}
    \mathcal{B}$ for some states $p$ and $q$ and a reduced word $u$ such
    that $|u| \le |w|$.
\end{prpstn}

The following converse statements are derived from Facts~\ref{fact1}
and~\ref{fact2}.

\begin{prpstn}\label{H istep}
    Let $\mathcal{A}$ be a reduced inverse automaton, let $H =
    L(\mathcal{A})\rho$, let $u$ and $v$ be reduced words labeling paths $q
    \mapright v q_{0} \mapright u p$ in $\mathcal{A}$, and suppose that
    $\mathcal{A} \longrightarrow_{{\sf i}}^{p=q} \mathcal{B}$.  Then $\mathcal{A} \longrightarrow_{{\sf e}}^{uv} \mathcal{B}$ and
    $L(\mathcal{B})\rho = \langle H, uv\rangle$.

    In particular, $\form{rank}(L(\mathcal{B})\rho) \le 1 + \form{rank}(H)$.  If
    $\form{rank}(L(\mathcal{B})\rho) = 1 + \form{rank}(H)$, then $H \le_{\sf ff} L(\mathcal{B})\rho$
    and if $C$ is a basis of $H$, then $C\cup\{uv\}$ is a basis of
    $L(\mathcal{B})\rho$.
\end{prpstn}

\begin{proof}
Let $\mathcal{A}'$ be the expansion of $\mathcal{A}$ by $(q_{0},uv,q_{0})$.  The
analysis in Fact~\ref{fact2} (2) shows that a step in the reduction of
$\mathcal{A}'$ is provided by the automaton obtained in identifying $p$ and
$q$.  By Proposition~\ref{H(A)} we have $L(\mathcal{B})\rho = \langle H,
uv\rangle$ (hence the rank inequality), and the uniqueness statement
in Proposition~\ref{prop unique} then shows that $\mathcal{A} \longrightarrow_{{\sf e}}^{uv}
\mathcal{B}$.

Let us now assume that $\form{rank}(L(\mathcal{B})\rho) = 1 + \form{rank}(H)$, and that
$C$ is a basis of $H$.  Then $C \cup \{uv\}$ is a generating set of
$L(\mathcal{B})\rho$ with cardinality equal to the rank of $L(\mathcal{B})\rho$,
so $C \cup \{uv\}$ is a basis of that subgroup by \cite[Prop.
I.3.5]{LS}.
\end{proof}

\begin{prpstn}\label{H restep}
    Let $\mathcal{A}$ and $\mathcal{B}$ be reduced inverse automata, let $w$ be a
    reduced word such that $\mathcal{A} \longrightarrow_{{\sf re}}^{(p,w,q)} \mathcal{B}$, let $H =
    L(\mathcal{A})\rho$, and let $u$ and $v$ be reduced words labeling paths
    $q \mapright v q_{0} \mapright u p$ in $\mathcal{A}$.  Then $\mathcal{A}
    \longrightarrow_{{\sf e}}^{uwv} \mathcal{B}$ and $L(\mathcal{B})\rho = \langle H, uwv\rangle$.

    Moreover, $H \le_{\sf ff} L(\mathcal{B})\rho$, $\form{rank}(L(\mathcal{B})\rho) = 1 +
    \form{rank}(H)$ and if $C$ is a basis of $H$, then $C \cup \{uwv\}$ is a
    basis of $L(\mathcal{B})\rho$.
\end{prpstn}

\begin{proof}
Since the expansion of $\mathcal{A}$ by $(p,w,q)$ is a reduced expansion,
the word $uwv$ is reduced and the expansion by $(q_{0},uwv,q_{0})$
falls in the situation described in Fact~\ref{fact2}~(1).  Together
with Proposition~\ref{H(A)}, it follows that $\mathcal{A} \longrightarrow_{{\sf e}}^{uwv}
\mathcal{B}$, which concludes the verification that of the first part of
the proposition.

The free factor and the rank statements follow from the statement on
a basis for $L(\mathcal{B})\rho$, which is a direct consequence of the
definition of a reduced expansion and of the discussion on bases and
spanning trees in Fact~\ref{end of sec 12}.
\end{proof}

We now introduce a measure of the \textit{cost} of a reduced
expansion or an i-step $\sigma$, written $\lambda(\sigma)$: if $\sigma$
is an i-step, then $\lambda(\sigma) = 0$; if $\sigma$ is a reduced
expansion, $\sigma = \longrightarrow_{{\sf re}}^{(p,w,q)}$, its cost is the length of
$w$, $\lambda(\sigma) = |w|$. We extend this notion of cost to finite
sequences of i-steps and reduced expansions: if $\bar\sigma =
(\sigma_{1},\ldots,\sigma_{n})$ is such a sequence, we let
$$\lambda(\bar\sigma) =
(\lambda(\sigma_{1}),\ldots,\lambda(\sigma_{n})).$$
Finally, we introduce an order relation on the set of finite sequences
of non-negative integers. Let $\bar k = (k_{1},\ldots,k_{n})$ and
$\bar\ell = (\ell_{1},\ldots,\ell_{m})$ be such sequences. We say that
$\bar k \preceq \bar\ell$ if
\begin{itemize}
    \item[either] $n < m$,

    \item[or] $n = m$ and $\sum_{i=1}^n k_{i} < \sum_{i=1}^m
    \ell_{i}$,

    \item[or] $n = m$, $\sum_{i=1}^n k_{i} = \sum_{i=1}^m \ell_{i}$
    and $\bar k$ precedes $\bar\ell$ in the lexicographic order.
\end{itemize}

It is routine to check that $\preceq$ is a well-order on the set of
finite sequences of non-negative integers, which is stable under the
concatenation of sequences. We write $\bar k\prec\bar\ell$ if $\bar
k\preceq\bar\ell$ and $\bar k\ne\bar\ell$.

\begin{prpstn}\label{L06}
    Let $\mathcal{A}$, $\mathcal{A}'$ and $\mathcal{B}$ be inverse automata such that
    $\mathcal{A}'$ is obtained from $\mathcal{A}$ by a reduced expansion
    $\sigma_{1}$ and $\mathcal{B}$ is obtained from $\mathcal{A}'$ by an i-step
    $\sigma_{2}$,
    $$\mathcal{A} \longrightarrow_{{\sf re}} \mathcal{A}' \longrightarrow_{{\sf i}} \mathcal{B}.$$
    Then there exist a sequence of reduced expansions or i-steps
    $\bar\sigma'$ of length 1 or 2 such that $\mathcal{B}$ is obtained from
    $\mathcal{A}$ by applying the steps in $\bar\sigma'$ and
    $\lambda(\bar\sigma') \prec \lambda(\sigma_{1},\sigma_{2})$.
\end{prpstn}

\begin{proof}
Suppose that $\mathcal{A} \longrightarrow_{{\sf re}}^{(p,w,q)} \mathcal{A}' \longrightarrow_{{\sf i}}^{r = s} \mathcal{B}$
with $r\ne s$.  The cost of this sequence of transformations is
$(|w|,0)$.

Let $Q$ be the state set of $\mathcal{A}$ and let $u$ and $v$ be reduced
paths,
$$q \mapright{v} q_0 \mapright{u} p.$$
Then $uwv$ is a reduced word and $L(\mathcal{A}')\rho = \langle
L(\mathcal{A})\rho,uwv\rangle$ by Proposition~\ref{H restep}. We distinguish
three cases, depending whether or not $r$ and $s$ lie in $Q$.

\paragraph{Case 1: Both $r$ and $s$ are in $Q$.}
Let $x$ and $y$ be reduced words labeling paths in $\mathcal{A}$ $s
\mapright{y} q_0 \mapright{x} r$.  Then the same words label similar
paths in $\mathcal{A}'$ and it follows from Proposition~\ref{H istep} that
$$L(\mathcal{B})\rho = \langle L(\mathcal{A}')\rho, xy\rangle = \langle
L(\mathcal{A})\rho, uwv, xy \rangle.$$

Let also $\mathcal{A}''$ and $\mathcal{B}'$ be determined by $\mathcal{A} \longrightarrow_{{\sf i}}^{r = s}
\mathcal{A}'' \longrightarrow_{{\sf e}}^{uwv} \mathcal{B}'$. Then $L(\mathcal{B}')\rho$ is also equal to
$\langle L(\mathcal{A})\rho, xy, uwv \rangle$, so that $\mathcal{B} = \mathcal{B}'$
by Proposition~\ref{prop unique}.

Note that the words $u$ and $v$ label paths from and into state $q_{0}$ in
$\mathcal{A}''$ as well. It follows from Proposition~\ref{L04} that, if
$uwv \not\in L(\mathcal{A}'')$, then $\mathcal{B}$ can be obtained from
$\mathcal{A}''$ by an i-step or by a reduced expansion of the form
$\longrightarrow_{{\sf re}}^{(t,z,t')}$ with $|z|\le |w|$.

Thus $\mathcal{B}$ is obtained from $\mathcal{A}$ either by a sequence of 1 or 2
transformations, of cost $0$ or $(0,k)$ with $0\le k\le |w|$. This
is $\prec$-less than $(|w|,0)$, as expected.

\paragraph{Case 2: Exactly one of $r$ and $s$ is in $Q$.}
Without loss of generality, we may assume that $r\in Q$ and $s\not\in
Q$.  Let $z$ be a reduced word labeling a path from $q_{0}$ to $r$ in
$\mathcal{A}$, and hence also in $\mathcal{A}'$.  Let $g$ be the unique reduced
word labeling a path from $p$ to $s$ in $\mathcal{A}'$, using only edges
that were not in $\mathcal{A}$.  By assumption, $g$ is a proper, non-empty
prefix of $w$.  Moreover, by Propositions~\ref{H(A)} and~\ref{H
istep},
$$L(\mathcal{B})\rho = \langle L(\mathcal{A}')\rho, ugz^{-1}\rangle = \langle
L(\mathcal{A})\rho, uwv, ugz^{-1} \rangle.$$

Let $h$ be the longest common suffix of $g$ and $z$, so that $g = g'h$,
$z = z'h$, $g'{z'}^{-1}$ is reduced and we have the following paths in
$\mathcal{A}'$,
$$q_0 \mapright{z'} r' \mapright{h} r, \quad p \mapright{g'} s'
\mapright{h} s.$$
Fact~\ref{fact1} shows that $\mathcal{A}'\longrightarrow_{{\sf i}}^{r' = s'} \mathcal{B}$, so
we may assume that $h = 1$, $g = g'$ and $z = z'$. There is a
possibility that the word $g$ is now empty (if $h$ was in fact equal to
$g$), but in that case, we are returned to the situation of Case 1,
with $s' = p$. Thus we may still assume that $g\ne 1$. In particular,
the word $ugz^{-1}$ is reduced.

Then let $\mathcal{A}''$ and $\mathcal{B}'$ be defined by $\mathcal{A} \longrightarrow_{{\sf e}}^{ugz^{-1}}
\mathcal{A}'' \longrightarrow_{{\sf e}}^{uwv} \mathcal{B}'$. Again $L(\mathcal{B}')\rho = \langle
L(\mathcal{A})\rho, uwv, ugz^{-1} \rangle$, so $\mathcal{B} = \mathcal{B}'$ by
Proposition~\ref{prop unique}.

Proposition~\ref{L04} states that each e-step can be replaced by an
i-step or by a reduced expansion of cost bounded above by the cost of
the e-step.  Going back to Fact~\ref{fact2}, we see that the e-step
$\mathcal{A} \longrightarrow_{{\sf e}}^{ugz^{-1}} \mathcal{A}''$ can be replaced by a transformation
of cost $k\le |g|$ since both $u$ and $z$ can be read from state
$q_{0}$ in $\mathcal{A}$ (in fact, of cost exactly $|g|$ by definition of
$g$).  As for the e-step $\mathcal{A}'' \longrightarrow_{{\sf e}}^{uwv} \mathcal{B}$, it can be
replaced by a transformation of cost $\ell \le |w|-|g|$ since $ug$ (a
prefix of $uw$) and $v$ can be read to state $q_{0}$ in $\mathcal{A}''$.

Now, it suffices to verify that $(k,\ell) \prec (|w|,0)$, which is
easily done if we observe that $k + \ell \le |w|$ and $k < |w|$.

\paragraph{Case 3: Neither $r$ nor $s$ is in $Q$.}
Without loss of generality, we may assume that $r$ occurs before $s$
along the $w$-labeled path from $p$ to $q$. Thus, the word
$w$ factors as $w = w_{1}w_{2}w_{3}$ and the path in $\mathcal{A}'$ made of
edges added to $\mathcal{A}$ factors as
$$p \mapright{w_{1}} r \mapright{w_{2}} s \mapright{w_{3}} q.$$
Since $r\ne s$ and these vertices are not in $Q$, each of the three
factors $w_{1}, w_{2}, w_{3}$ is non-empty. Moreover,
$$L(\mathcal{B})\rho = \langle L(\mathcal{A}')\rho, uw_{1}w_{3} v\rangle = \langle
L(\mathcal{A})\rho, uwv, uw_{1}w_{3} v \rangle.$$

Let $h$ be the longest common suffix of $w_{1}$ and $w_{3}^{-1}$, so
that $w_{1} = w'_{1}h$, $w_{3} = h^{-1} w'_{3}$, $w'_{1}w'_{3}$ is
reduced and we have the following paths in $\mathcal{A}'$,
$$p \mapright{w'_{1}} r' \mapright{h} r \mapright{w_{2}} s
\mapleft{h} s' \mapright{w'_{3}} q.$$
Proposition~\ref{fact1} shows that $\mathcal{A}'\longrightarrow_{{\sf i}}^{r' = s'} \mathcal{B}$, so
we may assume that $h = 1$, $w_{1} = w'_{1}$ and $w_{3} = w'_{3}$.
There is a possibility that the words $w_{1}$ or $w_{3}$ be now empty
(if $h$ was in fact equal to $w_{1}$ or $w_{3}$), but in that case, we
are returned to the situation of Cases 1 or 2, with $r' = p$ or $s' =
q$. Thus we may still assume that $w_{1}\ne 1$ and $w_{3}\ne 1$. In
particular, the word $uw_{1}w_{3}v$ is reduced.

Then let $\mathcal{A}''$ and $\mathcal{B}'$ be defined by $\mathcal{A}
\longrightarrow_{{\sf e}}^{uw_{1}w_{3}v} \mathcal{A}'' \longrightarrow_{{\sf e}}^{uwv} \mathcal{B}'$. Then
$L(\mathcal{B}')\rho = \langle L(\mathcal{A})\rho, uwv, uw_{1}w_{3}v \rangle$, so
$\mathcal{B} = \mathcal{B}'$ by Proposition~\ref{prop unique}.

As in Case 2, we use Fact~\ref{fact2} to verify that the e-step $\mathcal{A}
\longrightarrow_{{\sf e}}^{uw_{1}w_{3}v} \mathcal{A}''$ can be replaced by a reduced expansion
of cost $k = |w_{1}w_{3}|$ since $u$ and $v$ are the maximal prefix
and suffix of $uw_{1}w_{3}v$ that can be read from and to state
$q_{0}$ in $\mathcal{A}$.  As for the e-step $\mathcal{A}'' \longrightarrow_{{\sf e}}^{uwv} \mathcal{B}$,
it can be replaced by a reduced expansion of cost $\ell = |w_{2}|$
since $uw_{1}$ and $w_{3}v$ are the maximal prefix and suffix of $uwv$
that can be read from and to state $q_{0}$ in $\mathcal{A}''$.

Now, it suffices to verify that $(k,\ell) \prec (|w|,0)$, which is
easily done if we observe that $k + \ell = |w|$ and $k < |w|$.
\end{proof}

\section{Deciding the free factor relation}\label{sec deciding}

\subsection{A geometric characterization of free factors}

We put together the technical results from Section~\ref{careful} to
prove the following characterization of free factors.

\begin{thrm}\label{charact ff}
    Let $H, K$ be finitely generated subgroups of $F = F(A)$ and assume
    that $d = \form{rank}(K) - \form{rank}(H) > 0$. Then $H$ is a free factor of
    $K$ if and only if the inverse automaton $\Gamma_{A}(H)$ can be
    transformed in $\Gamma_{A}(K)$ by a sequence of $d'\le d$ i-steps
    followed by $d - d'$ reduced expansions.
\end{thrm}

\begin{proof}
We first observe that $H$ is a free factor of $K$ if and only if there
exist $d$ elements $k_{1},\ldots,k_{d}$ of $F(A)$ such that $\langle
H\cup\{k_{1},\ldots,k_{d}\}\rangle = K$. This follows from the fact
that an $r$-element generating set in a rank $r$ free group, is a basis
\cite[Prop. I.3.5]{LS}.

By definition of e-steps, this means that $H\le_{\sf ff} K$ if and only if
$\Gamma_{A}(H)$ yields $\Gamma_{A}(K)$ by a sequence of $d$ e-steps.

Now Propositions~\ref{L04}, \ref{H istep} and~\ref{H restep} show that
this is equivalent to the fact that $\Gamma_{A}(H)$ yields
$\Gamma_{A}(K)$ by a sequence of $d$ i-steps or reduced expansions.

Since $\preceq$ is a well-order on the set of finite sequences of
non-negative integers, we may consider a sequence $\bar\sigma$ of $d$
i-steps and reduced expansions leading from $\Gamma_{A}(H)$ to
$\Gamma_{A}(K)$, which is $\preceq$-minimal.  Proposition~\ref{L06},
together with the stability of $\preceq$ under concatenation, then
shows that the i-steps in $\bar\sigma$ come before the reduced
expansions.  Thus, $H\le_{\sf ff} K$ if and only if $\Gamma_{A}(H)$ yields
$\Gamma_{A}(K)$ by a sequence of $d'$ i-steps followed by $d - d'$
reduced expansions.
\end{proof}

It follows from the discussion on bases and spanning trees in
Fact~\ref{end of sec 12} that if $\Gamma_{A}(H)$ embeds in
$\Gamma_{A}(K)$, then $H$ is a free factor of $K$.  Not every free
factor of $K$ occurs that way, and those that do are called the
\textit{graphical free factors of $K$} (\textit{with respect to $A$}).
It is easily verified that $H$ is a graphical free factor of $K$ if
and only if $\Gamma_{A}(H)$ yields $\Gamma_{A}(K)$ by a sequence of
reduced expansions.

\begin{crllr}\label{coroll HffK}
    Let $H, K$ be finitely generated subgroups of $F = F(A)$ and assume
    that $d = \form{rank}(K) - \form{rank}(H) > 0$. Then $H$ is a free factor of
    $K$ if and only if the inverse automaton $\Gamma_{A}(H)$ can be
    transformed by a sequence of $d'\le d$ i-steps into some
    $\Gamma_{A}(L)$ such that $\form{rank}(L) = \form{rank}(H) + d'$ and $L$ is a
    graphical free factor of $K$ with respect to $A$.
\end{crllr}

\begin{proof}
Let us first assume that $H\le_{\sf ff} K$.  By Theorem~\ref{charact ff}, for
some $d'\le d$, $\Gamma_{A}(H)$ can be taken to some $\Gamma_{A}(L)$
by a sequence of $d'$ i-steps, and $\Gamma_{A}(L)$ can be taken to
$\Gamma_{A}(K)$ by a sequence of $d - d'$ re-steps.  Since $\form{rank}(K) =
\form{rank}(H) + d$ and an i-step or an re-step can increment the rank by at
most one (Propositions~\ref{H istep} and~\ref{H restep}), $L$ must have
rank exactly $\form{rank}(H) + d'$.

Conversely, suppose that a sequence of $d' \le d$ i-steps takes
$\Gamma_{A}(H)$ to $\Gamma_{A}(L)$ in such a way that $\form{rank}(L) =
\form{rank}(H) + d'$ and $\Gamma_{A}(L)$ embeds in $\Gamma_{A}(K)$.  By
Propositions~\ref{H istep} and~\ref{H restep} again, we have $H \le_{\sf ff}
L \le_{\sf ff} K$, and hence $H\le_{\sf ff} K$.
\end{proof}

\begin{rmrk}\label{rank incrementing}
    We observe the following by-product of the proof of
    Corollary~\ref{coroll HffK}: if $\Gamma_{A}(H)$ can be transformed
    into $\Gamma_{A}(L)$ by a sequence of $d'$ i-steps such that
    $\form{rank}(L) = d' + \form{rank}(H)$, then for every i-step $\mathcal{A} \longrightarrow_{{\sf i}}
    \mathcal{B}$ occurring in that sequence, we have $\form{rank}(L(\mathcal{B})\rho) =
    1 + \form{rank}(L(\mathcal{A})\rho)$.  We say that such an i-step is
    \textit{rank-incrementing}.
\end{rmrk}

In the special case where $K = F$, we have the following statement.

\begin{crllr}\label{coroll HffF}
    Let $H$ be a finitely generated subgroup of $F = F(A)$, let
    $A_{0}$ be the set of letters in $A$ that occur in $\Gamma_{A}(H)$
    and let $d = |A_{0}| - \form{rank}(H) = \form{rank}(F(A_{0})) - \form{rank}(H)$.
    Then $H$ is a free factor of $F$ if and only if $d \ge 0$ and
    $\Gamma_{A}(H)$ can be transformed into a one-vertex automaton by
    a sequence of $d$ i-steps.
\end{crllr}

\begin{proof}
By Corollary~\ref{coroll HffK}, $H$ is a free factor of $F(A)$ if and
only if $\Gamma_{A}(H)$ yields a one-vertex automaton $\mathcal{B}$ by a
sequence of $d' \le |A| - \form{rank}(H)$ i-steps, in such a way that
$L(\mathcal{B})\rho$ has rank $d' + \form{rank}(H)$.  Now the set of letters
occurring in such an automaton $\mathcal{B}$ must be exactly $A_{0}$, so
$L(\mathcal{B})\rho = F(A_{0})$ and $d' = d$.
\end{proof}

\subsection{Deciding whether $H\le_{\sf ff} F$}\label{sec algorithm}

We first consider the problem of deciding whether a given finitely
generated subgroup $H$ of $F = F(A)$ is a free factor of $F$.  With
the notation of Corollary~\ref{coroll HffF} and Remark~\ref{rank
incrementing}, the algorithm to decide whether $H\le_{\sf ff} F$ consists of
the following.  We need to explore the sequences of rank-incrementing
i-steps, starting from $\Gamma_{A}(H)$ and of length $d = |A_{0}| -
\form{rank}(H)$.  Then $H\le_{\sf ff} F$ if and only if one of the automata
occurring at the end of one of these sequences has a single vertex.
Note that no automaton obtained after less than $d$ i-steps could be
a single-vertex automaton.

These automata can be viewed as nodes of a tree, rooted at
$\Gamma_{A}(H)$, in which the children of a node are the automata
produced by a rank-incrementing i-step.  Let $n$ be the number of
states of $\Gamma_{A}(H)$.  Then every automaton occurring along this
tree has at most $n$ states.

If $\mathcal{A}$ is such an automaton, then $\mathcal{A}$ has at most
$\frac12(n^2-n)$ pairs of distinct vertices, and hence at most
$\frac12(n^2-n)$ children, each of which has at most $n - 1$ states.
The computation of the children of $\mathcal{A}$ is done by computing all
the (at most $\frac12(n^2-n)$) possible i-steps, computing
the ranks of the corresponding subgroups and retaining only those of
rank $1 + \form{rank}(L(\mathcal{A})\rho)$.  It follows from Fact~\ref{end of sec
12} that the cost of the computation of the children of $\mathcal{A}$ is
$O(n^{4})$.

Moreover, there are at most $O(n^{2d-2})$ nodes of the tree at depth
at most $d-1$, and the computation of these nodes and their children
requires time $O(n^{2d+2})$.  For each of the $O(n^{2d})$ automata at
depth $d$, the verification whether the automaton has a single node
takes constant time, so the total cost of the algorithm is
$O(n^{2d+2})$.

Finally, if $H$ is given by a finite set of generators, of total
length $\ell$, we recall that computing $\Gamma_A(H)$ takes time
$O(\ell^2)$ and that $\Gamma_A(H)$ has at most $\ell$ states and
$\ell$ edges.  This discussion justifies the following statement.

\begin{thrm}\label{thm35}
    Let $A$ be a fixed alphabet.  Then there is an algorithm which,
    given reduced words $h_{1},\ldots,h_{n}$ in $F(A)$ with total
    length $\ell$, decides whether the subgroup $H$ generated by the
    $h_{i}$ is a free factor of $F(A)$ in time $O(\ell^{2d+2})$, where
    $d = |A_{0}| - \form{rank}(H)$ and $A_{0}$ is the set of letters in $A$
    that occur in the $h_{i}$.
\end{thrm}

\begin{rmrk}
    The tree exploration described above can be speeded up by the
    following observation.  If the automaton $\mathcal{A}$ occurs in a
    sequence of rank-incre\-menting i-steps from $\Gamma_{A}(H)$ to the
    one-vertex automaton $\Gamma_{A}(F(A_{0}))$ (a \textit{winning
    sequence}), then $L(\mathcal{A})\rho \le_{\sf ff} F(A_{0})$, which implies that
    $L(\mathcal{A})\rho$ is a free factor of every subgroup of $F(A_{0})$
    containing it.  It follows that, if some i-step $\mathcal{A} \longrightarrow_{{\sf i}}
    \mathcal{B}$ does not increment the rank, then $\mathcal{A}$ does not occur in
    a winning sequence, that is, we may ignore the subtree below
    $\mathcal{A}$.

    There are undoubtedly other implementation tricks and ideas that
    can reduce the decision process, however without changing the
    worst-case complexity.
\end{rmrk}

\begin{rmrk}
    In view of Touikan's announcement (see Fact~\ref{end of sec 12}),
    the time complexity in the above theorem can be lowered to
    $O(\ell^{2d+1}\log^*\ell)$.
\end{rmrk}

The above discussion of complexity depends on a \textit{uniform cost
assumption}, by which we assume that the elementary operations on $A$
(reading or writing a letter, comparing two letters) require unit
time.  In other words, we have been assuming that $A$ is fixed, and
not part of the input.  We will shortly consider the problem of
deciding whether $H \le_{\sf ff} K$ where both $H$ and $K$ are part of the
input, and for the purpose of that discussion, we reconsider the
algorithm and the complexity established above under the \textit{bit
cost assumption}: we let $r$ be the cardinality of $A$, and we
consider that each letter is identified by a bit string of length at
most $\log r$, so that the elementary operations on $A$ require
$O(\log r)$ units of time.

Let $f(\ell,r)$ be the complexity of reducing a dual automaton on
$\tilde A$ with at most $\ell$ vertices and $\ell$ edges.  The
computation of the automaton obtained by an i-step from an
$\ell$-vertex automaton takes time at most $f(\ell,r)$.  To compute
the tree of rank-incrementing i-steps rooted at $\Gamma_A(H)$, we need
to compute the at most $O(\ell^2)$ children of at most $\ell^{2d-2}$
nodes, which requires time $O(\ell^{2d}f(\ell,r))$.  Finally, deciding
whether an automaton has a single vertex takes constant time, so the
total complexity of the algorithm is $O(\ell^{2d}f(\ell,r))$.

We now give an upper bound of $f(\ell,r)$.  Let $\mathcal{A}$ be an
$A$-automaton with at most $\ell$ states and $\ell$ edges.  The
identifiers of states require space $O(\log\ell)$ and the identifiers
of letters require space $O(\log r)$.  Moreover, we assume that the
set of states and the set $\tilde A$ are linearly ordered, and
equipped with a constant time \textsf{next} function.

The automaton can be viewed as the lexicographically ordered list of
all triples $(u,a,v)$ such that either $a\in A$ and there is an
$a$-labeled edge from state $u$ to state $v$, or $\bar a\in A$ and
there is a $\bar a$-labeled edge from state $v$ to state $u$.  Each
entry of this list requires space $O(\log\ell + \log r) = O(\log(\ell
r))$, and the list contains at most $\ell$ entries.  In particular, a
complete scan of the list takes time $O(\ell \log(\ell r))$.

The reduction of $\mathcal{A}$ consists in performing elementary reductions
of type 1 as long as it is possible, and then elementary reductions of
type 2.  To find out whether a type 1 reduction is possible, one needs
to scan the list to find two (consecutive) cells of the form $(u,a,v)$
and $(u,a,v')$, requiring $O(\ell \log(\ell r))$.  Performing the
identification consists in reading through the list, replacing every
occurrence of $v'$ by $v$, and reordering the list: this takes time
$O(\ell \log(\ell r))$.  To find out whether an elementary reduction
of type 2 is possible, one scans the list to find a vertex $u$ such
that there is a unique triple of the form $(u,a,v)$ in the list:
again, this takes time $O(\ell \log(\ell r))$.  Finally, performing
the reduction consists simply in deleting the entries $(u,a,v)$ and
$(v,\bar a,u)$ in the list.

Summarizing, since we will perform at most $\ell$ reductions, we can
take the function $f(\ell,r)$ to be equal to $\ell^2\log(\ell r)$.
This yields the following statement.

\begin{thrm}\label{thm-generalized35}
    There is an algorithm which, given an alphabet $A$ of size $r$ and
    reduced words $h_{1},\ldots,h_{n} \in F(A)$ with total length
    $\ell$, decides whether the subgroup $H$ generated by the $h_{i}$
    is a free factor of $F(A)$ in time $O(\ell^{2d+2} \log(\ell r))$,
    where $d = |A_{0}| - \form{rank}(H)$ and $A_{0}$ is the set of letters
    in $A$ that occur in the $h_{i}$.
\end{thrm}

\subsection{Deciding whether $H \le_{\sf ff} K$}\label{sec algorithm HK}

We now suppose that $H$ and $K$ are subgroups of $F(A)$, given by sets
of generators with total length $\ell$, and we consider the problem of
deciding whether $H\le_{\sf ff} K$.  The algorithm is the following: we first
compute $\Gamma_{A}(K)$ and we verify whether each generator of $H$
can be read as a loop at $q_0$, the designated vertex of
$\Gamma_A(K)$. If not, then $H$ is not contained in $K$, and cannot
be a free factor.

We now assume that $H \le K$ and we compute a spanning tree $T$ of the
graph $\Gamma_{A}(K)$.  This spanning tree determines a basis $B$ of
$K$, indexed by the edges of $\Gamma_{A}(K)$ that are not in $T$ (see
Fact~\ref{end of sec 12}), and we express the given generators of $H$
in terms of this basis: it suffices to read the generators of $H$ as
loops at the designated vertex in $\Gamma_{A}(K)$, and to record the
sequence of edges traversed and not in $T$.  In particular, each
generator of $H$ is expressed as a reduced word in $\tilde B^*$, that
is no longer than its expression as a reduced word in $\tilde A^{*}$.
We then use this expression of the generators of $H$ to construct
$\Gamma_{B}(H)$, and the algorithm in Section~\ref{sec algorithm} to
decide whether $H$ is a free factor of the ambient free group, namely
$K$.

Let us now discuss the complexity of this algorithm, assuming that
$H$ and $K$ are given by tuples of generators of total length $\ell$
and that $F$ has rank $r$. As discussed in the previous section,
computing $\Gamma_A(K)$ takes time $O(\ell^2\log(\ell r))$. Running
a word $w \in F(A)$ in the automaton $\Gamma_A(K)$ requires reading
sequentially each letter of $w$ (time $O(\log r)$) and looking for
the corresponding transition in the table representing the automaton
(time $O(\ell\log(\ell r))$). If $w$ has length  $\ell'$, this takes time
$O(\ell'\ell\log(\ell r))$. In order to decide whether $H$ is contained
in $K$, this must be done for every generator of $H$, and since the
total length of these generators is at most $\ell$, this requires
time $O(\ell^2\log(\ell r))$.

Assuming that $H$ is indeed contained in $K$, the next step is to
construct a spanning tree $T$ of $\Gamma_A(H)$, for instance by
marking certain edges in the list representing $\Gamma_A(K)$.  Again,
this can be done in time $O(\ell^2\log(\ell r))$.  The positively
labeled edges of $\Gamma_A(K)$ not in $T$ are in bijection with a
basis $B$ of $K$.  In particular, the rank of $K$ is at most $\ell$,
an upper bound of the number of edges in $\Gamma_A(K)$.  The elements
of $B$, seen as words in $F(A)$, consist of the label of a path in
$T$, followed by the label of an edge not in $T$, followed by the
label of a path in $T$.  In particular, their length is at most twice
the number of vertices of $\Gamma_A(K)$ plus one, that is $O(\ell)$.
But we do not need to compute these words: it suffices to number (from
$1$ to $\form{rank}(K) \le \ell$) the positively labeled edges not in $T$.
Then, for each generator $h$ of $H$, reading $h$ in $\Gamma_A(K)$ from
state $q_0$ and keeping track of the (identifier of the) edges
traversed that are not in $T$, provides an expression of $h$ in $B$.
Moreover, the total length of the expression of the generators of
$H$ in this basis of $K$ is at most $\ell$.

We now simply apply Theorem~\ref{thm-generalized35} to a length $\ell$
set of generators of a subgroup of a free group of rank at most
$\ell$, to justify the following corollary.

\begin{crllr}
    Given tuples of generators for subgroups $H$ and $K$ of $F(A)$,
    with total length $\ell$, one can decide whether the subgroup $H$
    is a free factor of $K$ in time
    $O(\ell^{2d+2}\log(\ell r))$, where $d = \form{rank}(K) - \form{rank}(H)$.
\end{crllr}

\begin{rmrk}\label{alternative algo H leff K}
    Corollary~\ref{coroll HffK} suggests an alternative algorithm to
    decide whether $H\le_{\sf ff} K$: one may explore the sequences of
    rank-incrementing i-steps of length at most $d = \form{rank}(K) -
    \form{rank}(H)$, starting from $\Gamma_{A}(H)$ and producing only
    representations of subgroups contained in $K$.  Each
    $\Gamma_{A}(L)$ occurring in such a sequence must be checked to
    verify whether it can be embedded in $\Gamma_{A}(K)$: if it can,
    then $H\le_{\sf ff} K$, and if it cannot, then the automata produced by a
    rank-incrementing i-step from it must be computed and checked in
    their turn.
\end{rmrk}

\subsection{Complement of a free factor}

By definition of a free factor (see the introduction), $H\le_{\sf ff} K$ if
there exists a basis $C$ of $H$ and a disjoint set $D\subseteq K$ such
that $C \cup D$ is a basis of $K$.  In that case, the subgroup
generated by $D$ is called a \textit{complement of $H$ in $K$}.  It is
easy to see that this complement is not uniquely defined.

If $H$ is indeed a free factor of the free group $F$, the algorithm
described in Section~\ref{sec algorithm} also provides a sequence of
rank-incrementing i-steps taking $\Gamma_{A}(H)$ to
$\Gamma_{A}(F(A_{0}))$, where $A_{0}$ is the set of letters of $A$
that occur in the generators of $H$.  Repeated applications of
Proposition~\ref{H istep} then yield a basis of $F(A_{0})$ containing
a basis of $H$, and hence a complement of $H$ in $F(A_{0})$.

We can be a little more precise.  If $\mathcal{A}$ is a reduced inverse
automaton, let $\form{diam}_{q_{0}}(\mathcal{A})$, the \textit{$q_{0}$-diameter}
of $\mathcal{A}$, be the longest shortest path in $\mathcal{A}$ from $q_{0}$ to
a state, that is
$$\form{diam}_{q_{0}}(\mathcal{A}) = \max_{q}\Big(\min\{|u| \mid \textrm{$u$ is a
reduced word and $q_{0} \mapright u q$ in $\mathcal{A}$}\}\Big).$$
Then Proposition~\ref{H istep} shows that if $\mathcal{A} \longrightarrow_{{\sf i}} \mathcal{B}$ and
$L(\mathcal{A})\rho \le_{\sf ff} L(\mathcal{B})\rho$, then a complement of
$L(\mathcal{A})\rho$ is generated by a word of length at most
$2\ \form{diam}_{q_{0}}(\mathcal{A})$.

This justifies the following statement.

\begin{prpstn}
    Let $H$ be a free factor of $F(A)$.  Then one can construct
    effectively a basis for a complement of $H$ in $F(A)$, consisting
    of words of length at most $2\ \form{diam}_{q_{0}} (\Gamma_{A}(H))$.
\end{prpstn}

It is interesting to observe that this is a graphical analogue -- and
a minor improvement -- of Federer and J\'onsson's result (see
\cite[Prop.  I.2.26]{LS}) mentioned in Section~\ref{whitehead}.
Indeed, if $h_{1},\ldots, h_{n}$ are a set of generators of $H$, then
every edge of $\Gamma_{A}(H)$ is on a loop at $q_{0}$ labeled by some
$h_{i}$, and hence $\max_{i}|h_{i}| \ge 2\
\form{diam}_{q_{0}}(\Gamma_{A}(H))$.

Let us now consider the problem of constructing a basis of a
complement of $H$ in $K$, where $H$ and $K$ are given finitely
generated subgroups of $F(A)$ and $H\le_{\sf ff} K$.  The algorithm described
in Remark~\ref{alternative algo H leff K} (based on
Corollary~\ref{coroll HffK}) shows that one can construct effectively
a graphical free factor $L$ of $K$ such that $H \le_{\sf ff} L$.  As above,
in view of Proposition~\ref{H istep}, the same algorithm can produce a
basis of a complement of $H$ in $L$ consisting of words of length at
most $2\ \form{diam}_{q_{0}}(\Gamma_{A}(H))$.  There remains to construct a
basis for a complement of $L$ in $K$.

In view of Fact~\ref{end of sec 12} (and using the notation therein),
one can find a (basis of a) complement of $L$ in $K$ by considering a
spanning tree of $\Gamma_{A}(L)$, extending it to a spanning tree $T$
of $\Gamma_{A}(K)$, and considering the elements $b_{e}$ associated
with edges of $\Gamma_{A}(K)$ that are neither in $\Gamma_{A}(L)$ nor
in $T$. In particular, the words $b_{e}$ have length at most $1 + 2\
\form{diam}_{q_{0}}(\Gamma(K))$. Thus we have the following statement.

\begin{prpstn}
    Let $H, K$ be finitely generated subgroups of $F(A)$.  If $H\le_{\sf ff}
    K$, then one can construct effectively a basis for a complement of
    $H$ in $K$, consisting of words of length at most $\max(2\
    \form{diam}_{q_{0}}(\Gamma_{A}(H)), 1 + 2\
    \form{diam}_{q_{0}}(\Gamma_{A}(K)))$.
\end{prpstn}

\begin{acknowledgement}
The authors wish to thank both anonymous referees for their many
helpful comments, which have substantially contributed to the
improvement of the paper.  All remaining shortcomings are naturally
ours.
\end{acknowledgement}

redpajama_set_name: RedPajamaArXiv


text:
\section{methods}

\subsection{Free energy and work.}

Each potential well separated by peaks was defined as a state (Fig. S5).
The free energy of the state $k$ was caluclated as $F_\mathrm{k}=-k_\mathrm{B} T\ln\left[\int\mathrm{d}x\,e^{-U(x)/k_\mathrm{B} T}\right]$, where the integration was performed in the angular region corresponding to the state $k$.
Since the shapes of all the wells are almost the same, the free energy difference between states is nearly equal to the difference of the potential energy of their local minima.
The work performed on the particle $W$ was calculated as the potential-energy change associated with the switching; the potential energy after the switching minus that before the switching.
In cycles without switching, $W=0$.

\subsection{Information content.}

For an event $k$ with a probability of occurrence $p(k)$, the Shannon information content associated with this event is defined as $-\ln p(k)$.
This definition leads to well-defined properties that the information content should satisfy\cite{Shannon1948}.
The average Shannon information content becomes $I\equiv -\sum_k p(k)\ln p(k)$.
Measurements usually accompany errors, which reduce the amount of information that can be utilized.
Although $I$ denotes the amount of the information embedded in the system, the mutual information content, $I'$, denotes the amount of information that is obtained by the measurement \cite{Cover1991, Sagawa2010}: $I'\equiv \sum_{k,m} p(m|k)p(k)\ln\frac{p(m|k)}{p(k)}$, where $p(m|k)$ is the conditional probability that the outcome of the measurement is the $m$-th event when the $k$-th event occurs actually.
If the measurement is free from error, $p(m|k)=\delta_\mathrm{k, m}$ ($\delta_{k, m}=1$ if $k=m$, and otherwise 0).
In such case, $I'=I$.
In the present experiment, we distinguished two events; the particle is observed in the region S or not with negligible measurement errors.
Then, the (average) Shannon information content per cycle becomes the so-called binary entropy function: $I= -p\ln p-(1-p)\ln(1-p)$, where $p$ is the probability that the particle is observed in the region S.

\subsection{Feedback efficacy.}

The feedback efficacy $\gamma$ is defined as the sum of the probabilities that the time-reversed trajectories are observed under time-reversed protocols for all possible protocols (Fig. S7).
In the forward feedback cycle, we measure the particle's angular position at $t=0$ and (i) switched or (ii) did not switch the potential at $t=\varepsilon$ depending on the angular position.
Corresponding time-reversed trajectories are that the particle is observed in the region (i) S at $t=\tau$ after the switching at $t=\tau-\varepsilon$ or (ii) outside S without switching.
Let the occurrence probabilities of time-reversed trajectories under timer-reversed protocolos be $p_\mathrm{sw}$ and $p_\mathrm{ns}$, respectively.
Then, $\gamma$ is $\gamma=p_\mathrm{sw}+p_\mathrm{ns}$.
From its definition, if there are $m$ states to be distinguished ($m=2$ in our experiment: whether the particle is in the region S or not), $0\le\gamma\le m$.
We repeated time reversed cycles with/without switchings to obtain $\gamma$ with a period of 220 ms, which is sufficiently long to ensure that the initial state of the cycle is relaxed to equilibrium.

\section{Schematic of experiment and the consistency with the second law of thermodynamics.}

We demonstrated that free energy is obtained by a feedback control using the information about the system; information is converted to free energy, as the first realization of Szilard-type Maxwell's demon\cite{Szilard1929}.

Since the obtained free energy or work is compensated for by the demon's energy cost to manipulate information, it does not violate the second law of thermodynamics when the total system including both the particle and demon is considered.
The demon consists of macroscopic devices in practice such as computers in our system; the microscopic device gains energy at the expense of the energy consumption of a macroscopic device (Fig. S\ref{fig:Second Law}).
In other words, by using information as the energy-transferring ``medium'', this information-energy conversion can be utilized to transport energy to nanomachines even if it is not possible to drive them directly.

\begin{figure}[htb]
\centering{\includegraphics[scale=0.6]{SecondLaw.eps}}
\caption{Schematic of the information-energy conversion with a macroscopic demon and a microscopic system (Szilard engine\cite{Szilard1929} as an example).
The Szilard-engine can achieve the 100\% conversion rate from information to energy; 1 bit ($\ln 2$ nat in the natural logarithm) of information is converted to free energy or work of $k_\mathrm{B}T\ln 2$ in the microscopic system at the expense of an energy consumption of $k_\mathrm{B}T\ln 2$ in the macroscopic demon.
}
\label{fig:Second Law}
\end{figure}

\section{Preparation of chamber.}

Brownian particles in a buffer solution were prepared for the experiment by the following procedure.
The cover slip (Matsunami, Japan) that served as the ceiling of the observation chamber was washed three times with distilled water.
The bottom glass coated with chromium electrodes (Matsunami, Japan) was soaked in 10 N KOH over night and then washed with distilled water.
The top and bottom glasses were separated by a plastic film with a thickness of about 12 $\mu$m (Saran wrap, Asahi Kasei, Japan) and silicone grease.
6 $\mu$l of A buffer (50 mM MOPS-K, 50 mM KCl, 2 mM MgCl$_2$, 2 mg/ml heat-shocked Bovine serum albumin (Sigma-Aldrich, USA), pH6.9) was applied to the chamber to suppress the binding of particles to the glass surface.
Then, 10 $\mu$l of streptavidin-coated polystyrene beads with a diameter of 287 nm (Seradyn, USA) in A buffer was applied to the chamber.
Some particles bound to the top glass surface.
About 50 $\mu$l of B buffer (5 mM MOPS-K, 1 mM MgCl$_2$, 1 mM KP$_\mathrm{i}$, pH6.9) was applied to wash out unbound particles in the chamber.
All the experiments were performed in B buffer at a room temperature.

\section{Microscopy and image analysis.}

The incidentally-dimeric particle pinned at the top glass surface was observed on a phase-contrast microscope (BX-51WI, Olympus, Japan) equipped with a high speed camera (IPX-210L, Imperx, USA) at a period of 1.1 ms with an exposure time of 0.3 ms.
Real-time feedback system was constructed on the PXI (PCI eXtensions for Instrumentation) system implementing a computing module (PXI-8108, National Instruments, USA), a video capturing board (PXI-1428, National Instruments), and a digital-to-analog conversion board for the control of the electric potential across the electrodes patterned on the bottom glass plate (PXI-6221, National Instruments).
The minimum delay in this feedback control is thus 1.1 ms  which is much shorter than the time for the particle to perform rotational diffusion up to 90 degrees.
The angle of the dimeric probe particle was estimated using an algorithm based on the principal component analysis.

\section{Elliptically-rotating electric field.}

\begin{figure}[htb]
\centering{\includegraphics[scale=1.0]{System.eps}}
\caption{(a) Quadrant electrodes. Not to scale. (b) Sinusoidal voltages applied on the electrodes.}
\label{fig:System}
\end{figure}

To provide a periodic potential and adverse torque to the Brownian particle, we utilized the induced polarization effect of the dielectric material subjected to an AC external electric field\cite{Watanabe-Nakayama2008, Washizu1993, Toyabe2010a}.
Four chromium electrodes on the bottom glass surface were connected to four power amplifiers (HSA4101, NF, Japan) that amplify AC (Alternative Current) voltages generated by function generators (WF1974, NF, Japan).
We applied 1-MHz AC voltages with some phase shifts on the electrodes (Fig. S\ref{fig:System}).
Let the phases on the electrodes to be 0, $\delta$, 180, and $180+\delta$ degrees.
Three different types of potentials are imposed on the particle according to the value of $\delta$ (Fig. S\ref{fig:EREF}).
\begin{itemize}
\item If $\delta=\pm 90$ degrees, a rotating electric field is applied at the center of the electrodes (Fig. S\ref{fig:EREF}a), where a dipole moment rotating at the same rate with some time delay appears on dielectric particles.
The length of the time delay is determined by the complex dielectric constants of the particle and the solution.
Due to the time delay, the particle experiences a torque from the electric field \cite{Watanabe-Nakayama2008, Washizu1993, Toyabe2010a}.
The torque is constant; it does not depend on the particle's motions but depends only on the time delay.
Its magnitude is proportional to the particles's volume and the square of the amplitude of the applied AC voltages.
Also, it nonlinearly depends on the frequency of the applied AC voltages.
According to the sign of $\delta$, the direction of the torque is changed.
\item If $\delta=0$ or $180$ degrees, the electric field does not rotate but oscillates along an axis (Fig. S\ref{fig:EREF}b).
In this case, the particle feels a periodic potential with a period of 180 degrees along the direction of rotation.
The oscillating direction of the electric field corresponds to the angle of the potential's local minima.
\item Otherwise, an elliptically rotating electric field is applied (Fig. S\ref{fig:EREF}c); it corresponds to the superposition of the above two cases ($\delta=0$ and 90 degrees).
In such case, the particle feels a tilted periodic potential.
The gradient of the potential depends on the value of $\delta$.
According to the sign of $\delta$, the direction of the torque is changed.
\end{itemize}

We set $\delta$ to be about 5 degrees ($\delta$ was tuned for each particle) to apply the elliptically rotating electric field.
For feedback control, the potential was switched by modulating the phases of applied voltages from 0, $\delta$, 180, and 180+$\delta$ degrees to 0, 180-$\delta$, 180, and -$\delta$ degrees, respectively for four electrodes.

\begin{figure}[htb]%
\centering{\includegraphics[scale=1.0]{ElectricField.eps}}%
\caption{
Three different types of the potential imposed on the particle according to the phase shift $\delta$.
(a) Rotating electric field.
(b) Oscillating electric field.
(c) Elliptically rotating electric field.
}
\label{fig:EREF}%
\end{figure}%

\section{Estimation of potential energy.}

The potential profiles were estimated by a method similar to Ref. \cite{Errington2004} (Fig. S\ref{fig:PotentialEstimation}a).
We switched two potentials with opposite phases periodically with a period of 220 ms to sample data around not only the local minima but also the peaks.
We divided the whole video frames to two sets according to the potential at each frame.
For each set of frames, we performed the following procedures to estimate the potential profile.
\begin{figure}[htb]%
\centering{\includegraphics{PotentialEstimation.eps}}%
\caption{
(a) Potential estimation.
(b) Estimation of the potential energy for a simulated trajectory.
Solid lines indicate the theoretical curves.
Markers correspond to estimated values (bin width = 3 degrees).
The slope is 1 $k_\mathrm{B}T/360^\circ$, the activation energy (peak-to-peak amplitude) 3 $k_\mathrm{B}T$, the rotational friction coefficient 0.3 pN$\cdot$nm$\cdot$s/rad$^2$, the framerate 1000 Hz, and temperature 300 K.
Number of frames is 1,000,000.
The potentials were switched every 200 frames.
}
\label{fig:PotentialEstimation}%
\end{figure}%
360 degrees are divided to equally-spaced bins with a bin width of 3 degrees.
We counted the number of video frames $m_\mathrm{i}$ where the particle is in the $i$\,th bin.
We also counted the number of transitions $n_\mathrm{i\to j}$, or the number of two-successive-frame where the particle in the $i$\,th bin moves to the $j$\,th bin at the next frame.
The transition probabilities $w_\mathrm{i\to j}\equiv n_\mathrm{i\to j}/m_\mathrm{i}$ satisfy the detailed balance condition:
\begin{equation}\label{eq:Detailed Balance Condition}
\frac{w_\mathrm{i\to j}}{w_\mathrm{j\to i}}=e^{-\Delta U_\mathrm{i\to j}/k_\mathrm{B} T},
\end{equation}
where $\Delta U_{i\to j}\equiv U_\mathrm{j}-U_\mathrm{i}$ is the difference of the potential energies between $i$\,th and $j$\,th bins.
We searched the set $\{U^*_i\}$ which minimizes a score function as follows:
\[
\varepsilon^2(\{U_i\})\equiv \sum_{i<j}\sqrt{n_\mathrm{i\to j}n_\mathrm{j\to i}}\left[\Delta U_\mathrm{i\to j}-\Delta U'_\mathrm{i\to j}\right]^2,
\]
where $\Delta U'_\mathrm{i\to j}\equivk_\mathrm{B} T \left[\ln{w_\mathrm{j\to i}}-\ln{w_\mathrm{i\to j}}\right]$, using the Powell's method \cite{NumericalRecipes3}.

The validity of this method was verified for numerically-simulated trajectories based on a Langevin dynamics.
Figure S\ref{fig:PotentialEstimation}b shows that this algorithm estimates the potential energy for the trajectory generated by a Langevin simulation to a good extent.

A typical number of video frames used for the potential estimation was about 1,000,000.

\section{State and free energy.}

Figure S\ref{fig:FreeEnergy} is the schematic to illustrate the definition of the state and how to calculate the free energy.

\begin{figure}[htb]
\centering{\includegraphics[scale=1.0]{FreeEnergy.eps}}
\caption{Definitions of the states and free energies. The well separated by peaks is regarded as a state. A free energy is assigned to each state.}
\label{fig:FreeEnergy}
\end{figure}

\section{Schematic of Energetics.}

Schematic to illustrate the energetics in a cycle with a switching is shown in Fig. S\ref{fig:Energetics}.

\begin{figure}[htb]%
\centering{\includegraphics[scale=1.0]{Energetics.eps}}%
\caption{
Schematic to illustrate the energetics in a cycle with a switching.
For small $\varepsilon$, switchings occur mostly when the particle is in the region S.
In this case, the particle absorbs heat from an isothermal environment to reach the region S before measurements at $t=0$, performs extractable work to the electric field at the switching, and finally jumps to the rightward well after the switching.
On the other hand, for large $\varepsilon$, most of the energy at $t=0$ dissipates to the heat bath before switching.
Then, the switching performs external work on the particle with lifting up the potential, which then dissipates as it falls down in the well.
}
\label{fig:Energetics}%
\end{figure}%

\section{Feedback efficacy.}

Figure S\ref{fig:Reverse} is the schematic to illustrate the feedback efficacy.

\begin{figure}[htb]%
\centering{\includegraphics[scale=0.7]{reverse.eps}}%
\caption{Forward and reversed cycle.
(A) Forward feedback cycle. ``S'' and ``N'' indicate that the particle is observed in the region S or not, respectively.
(B) Reversed cycle. Feedback control is not performed.}
\label{fig:Reverse}%
\end{figure}%

\section{Efficiency.}

Figure S\ref{fig:Efficiency} shows (a) the probability that the particle is observed in the region S, (b) the (average) Shannon information content, and (c) the efficiency to convert information to energy.

\begin{figure}[htb]
\centering{\includegraphics[scale=1.0]{efficiency.eps}}
\caption{Efficiency of information-energy conversion.
(a) The probability $p$ that the particle is observed in the region S.
(b) Shannon information content $I\equiv -p\ln p-(1-p)\ln(1-p)$.
(c) Efficiency of the information-energy conversion calculated as $\langle\Delta F-W\rangle/k_\mathrm{B}TI$.
Error bars indicate standard deviations.
}
\label{fig:Efficiency}
\end{figure}

\bibliographystyle{prsty}