\section{Introduction}
		In this article we consider the pricing of American and European options paying
		the \emph{complexity deficiency}, or intuitively the lack of complexity, of a sequence of up and down ticks for a financial security.
		The complexity notions we consider are
		plain and prefix-free Kolmogorov complexity, nondeterministic automatic complexity, and run complexity.
		\subsection{Motivation}

			We believe it may be of value in finance to have
			some notions of the complexity of a price path.
			Agents may want to insure against too complex or too simple price paths for a stock, for example.
			A very simple or complex path may be a sign that something is going on that the agent is not aware of.

			Weather is somewhat periodic, and automatic complexity measures
			periodicity, to some extent. Hence a complexity option may be used as a weather derivative.

			Casino owners may want to ensure that their casinos are truly random, so as to avoid unexpected losses.
			In general, anyone who makes an assumption of randomness may want to hedge that,
			as true randomness is not easy to guarantee, or even completely well-defined.

			\paragraph{Automatic complexity: between two extremes.} Of course, we can insure against certain types of non-randomness in simple ways.
			We can insure against a dramatic fall of a stock price by selling the stock short.
			This corresponds to \emph{run complexity} (Section \ref{Malihe}).
			At the other end, one cannot use \emph{Kolmogorov complexity} (Section \ref{sec:KC}) as a basis for the security,
			because Kolmogorov complexity is not computable.
			The \emph{nondeterministic automatic complexity},
			being both
			\begin{itemize}
				\item powerful enough to discern a variety of patterns, and at the same time
				\item single-exponential time computable,
			\end{itemize}
			may be a promising middle ground.
		\subsection{Automatic complexity and the idea of complexity deficiency}
			Kolmogorov complexity is an important notion that in a way is to complexity
			as Turing computability is to computability.
			It is computably approximable, but unfortunately not computable.
	 		As a remedy, \cite{MR1897300} defined the \emph{automatic complexity}
			of a finite binary string \(x=x_1\ldots x_n\) to be
			the least number \(A_D(x)\) of states of a {deterministic finite automaton} \(M\) such that
			\(x\) is the only string of length \(n\) in the language accepted by \(M\).

			Automatic complexity is computable, but it does have a couple of awkward properties that make us want to tweak its definition.
			First, many of the automata used to witness the complexity have
			a \emph{dead state} whose sole purpose is to absorb any irrelevant or
			unacceptable transitions. Second, some strings $x=x_1\dots x_n$ have a different complexity from their reverse $x_n\dots x_1$.
			For instance \cite{COCOON:14,Kjos-EJC},
			\[
				A_D(011100) = 4 < 5 = A_D(001110).
			\]
			We tweak the definition of automatic complexity by introducing nondeterminism.
			\begin{df}[\cite{Kjos-EJC}]\label{precise}
				The nondeterministic automatic complexity $A_N(w)$ of a word $w$ is
				the minimum number of states of an NFA $M$
				(having no $\epsilon$-transitions) accepting $w$
				such that there is only one accepting path in $M$ of length $\abs{w}$.
			\end{df}
			\begin{figure}[h]
				\begin{tikzpicture}[shorten >=1pt,node distance=1.5cm,on grid,auto]
					\node[state,initial, accepting] (q_1)  {$q_1$};
					\node[state] (q_2)   [right=of q_1  ] {$q_2$};
					\node[state] (q_3)   [right=of q_2  ] {$q_3$};
					\node[state] (q_4)   [right=of q_3  ] {$q_4$};
					\node    (q_dots) [right=of q_4  ] {$\ldots$};
					\node[state] (q_m)   [right=of q_dots] {$q_m$};
					\node[state] (q_{m+1}) [right=of q_m  ] {$q_{m+1}$};
					\path[->]
						(q_1)   edge [bend left] node      {$x_1$}   (q_2)
						(q_2)   edge [bend left] node      {$x_2$}   (q_3)
						(q_3)   edge [bend left] node      {$x_3$}   (q_4)
						(q_4)   edge [bend left] node [pos=.45] {$x_4$}   (q_dots)
						(q_dots) edge [bend left] node [pos=.6] {$x_{m-1}$} (q_m)
						(q_m)   edge [bend left] node [pos=.56] {$x_m$}   (q_{m+1})
						(q_{m+1}) edge [loop above] node      {$x_{m+1}$} ()
						(q_{m+1}) edge [bend left] node [pos=.45] {$x_{m+2}$} (q_m)
						(q_m)   edge [bend left] node [pos=.4] {$x_{m+3}$} (q_dots)
						(q_dots) edge [bend left] node [pos=.6] {$x_{n-3}$} (q_4)
						(q_4)   edge [bend left] node      {$x_{n-2}$} (q_3)
						(q_3)   edge [bend left] node      {$x_{n-1}$} (q_2)
						(q_2)   edge [bend left] node      {$x_n$}   (q_1);
				\end{tikzpicture}
				\caption{
					A nondeterministic finite automata that only accepts one string
					$x= x_1x_2x_3x_4 \ldots x_n$ of length $n = 2m + 1$.
				}
				\label{fig1}
			\end{figure}
			Moreover, and most importantly for the present paper, $A_N$ gives rise to a striking instance of the idea of \emph{complexity deficiency}:
			\begin{thm}[\cite{Hyde,Kjos-EJC}]\label{Kayleigh}
				The nondeterministic automatic complexity $A_N(x)$ of a string $x$ of length $n$ satisfies
				\[
					A_N(x) \le b(n):={\lfloor} n/2 {\rfloor} + 1\text{.}
				\]
			\end{thm}
			\begin{proof}[Proof sketch]
				The proof is essentially contained in Figure \ref{fig1},
				although we must modify the picture slightly if $x$ has even length.
			\end{proof}
			\begin{df}
				The \emph{nondeterministic automatic complexity deficiency} of a string $x$ is defined by
				\[
					D_n(x) = b(n) - A_N(x),
				\]
				with $b(n)$ as in Theorem \ref{Kayleigh}. Sometimes we write $D(x)$ for $D_n(x)$.
			\end{df}
			Experimentally we have found that about half of all strings have $D_n(x)=0$ \cite{Kjos-EJC}.
			We call such strings \emph{complex}, and other strings \emph{simple}, herein.

		\subsection{Option types: perpetual, American, European}
			We shall consider the following types of options and their prices.
			\begin{itemize}
				\item[$V$.] This is the price of the perpetual option that pays out the deficiency $D_n(x)$ when
					we exercise the option at a time $n$.
					(\emph{Perpetual} here means that
					we can exercise the option at any time step labeled by a nonnegative integer.)
					The price of a perpetual option is the supremum, over all exercise policies ${\tau}$,
					of the expected payoff when using ${\tau}$. There is no restriction that ${\tau}$ be computable
					(in particular, there is no restriction that there be enough time to compute it before the next market time step occurs),
					but if that were to become an issue one would presumably change the definition accordingly.
				\item[$V_n$.] This is the price of an \emph{American} option that we can exercise at any time step
					labeled by an integer between $0$ and $n$.
				\item[$W_n$.] This is the price of the \emph{European} option with expiry $n$.
					In this case we must exercise the option at time $n$, if at all. So
					$W_n=\mathbb E(\max\{D_n, 0\})$.
					Here, and in the rest of this article, we assume the underlying probability distribution is given by the fair-coin measure.
					In a finance setting it could more generally be given by
					the risk-neutral measure determined from a stock price process.
			\end{itemize}
			We have
			\[
				\mathbb E D_n \le W_n \le V_n \le V,
			\]
			and
			\begin{thm}\label{three}
				\[
					\sup_n \mathbb E D_n \le \sup_n V_n \le V \le \mathbb E \sup_n D_n.
				\]
			\end{thm}
			\begin{proof}
				For the first inequality, it suffices to show
				\[
					\mathbb E D_n \le V
				\]
				for each $n$. This holds because one possible exercise policy is
				the static strategy of exercising at time $n$ no matter what.

				For the third inequality, there are two cases.

				Case 1: $\sup_n D_n$ is almost surely finite.
				Note that $D_n$ is integer-valued, so $\sup_n D_n$ will be realized at some finite stage $n_0$.
				Let us call \emph{magically prescient} the strategy which waits for
				$\sup_n D_n$ to be realized and then exercises the option.
				By contrast, an \emph{exercise policy} should be a stopping time, i.e.,
				it should not depend on future outcomes.
				We see that the payoff from the magically prescient strategy has
				a higher price than any exercise policy.
				It follows that $V\le\mathbb E\sup_n D_n$ in this case.

				Case 2: $\mathbb P(\sup_n D_n=\infty)>0$. Then $\mathbb E\sup_n D_n=\infty$ and so we are done.
			\end{proof}
			\begin{rem}
				In Case 2 of Theorem \ref{three}, if $\mathbb P(\sup_n D_n=\infty) = \varepsilon > 0$ then we can even assert that $V=\infty$.
				Indeed if $V<\infty$ then we can buy the option, and wait for $D_n > V/\varepsilon + 1$.
				The expected payoff is at least
				\[
					(\varepsilon)(V/\varepsilon + 1) = V + \varepsilon > V,
				\]
				which would create an arbitrage.
			\end{rem}
			In Sections \ref{sec:KC} and \ref{sec:CFC} we shall consider several complexity notions, including
			\begin{itemize}
				\item prefix-free Kolmogorov complexity $K$,
				\item plain Kolmogorov complexity $C$, and
				\item nondeterministic automatic complexity $A_N$.
			\end{itemize}
			For each notion we first define one or more suitable deficiency notions $D_n(x)$:
			for instance, $D_n(x) = n + c_C - C(x)$ for a suitable constant $c_C$ for $C$, and
			$D_n(x) = \lfloor n/2\rfloor + 1 - A_N(x)$ for $A_N$.
			The following questions are natural for each of these deficiency notions:
			\begin{itemize}
				\item Does the price of the European option tend to $\infty$?
				\item Does the price of the American option tend to $\infty$?
				\item Does the American option have an efficiently computable exercise policy?
			\end{itemize}

	\section{Kolmogorov complexity}\label{sec:KC}
		\subsection{Plain complexity \texorpdfstring{$C$}{C}}
			Let $c_C$ be the least constant $c_C$ such that
			$C(x\mid n)\le n+c_C$ for all strings $x$ of any length $n$.
			If we define $D_n(x) = n + c_C - C(x\mid n)$ for $x$ of length $n$, then $D_n(x)\ge 0$ for all $x$,
			and $D_n(x)=0$ does occur. This is theoretically pleasant. Deficiencies are nonnegative and can
			be zero.
			Of course, $c_C$ depends on the version of the plain length-conditional Kolmogorov complexity $C(\cdot\mid\cdot)$ that we use.
			In this setting, we have
			\begin{thm}\label{plainFinite}
				$\sup_n\mathbb E D_n<\infty$.
			\end{thm}
			\begin{proof}
				Fix $n$. For any $a$, there are only $2^{a+1} - 1$ binary strings of length at most $a$.
				All descriptions witnessing complexity (given $n$) being at most $a$ must be among them, so
				at most $2^{a + 1} - 1$ many strings have complexity (given $n$) of at most $a$.
				(This is a standard argument, see \cite[Proposition 3.1.3]{MR2732288}.)
				Applying this to $a = n + c_C - k$,
				at most $2^{n + c_C - k + 1} - 1$ strings $x$
				(in particular, at most that many strings of length $n$) satisfy
				$D_n(x) \ge k$. That is,
				\[
					\mathbb P(D_n(x)\ge k) \le 2^{c_C - k + 1}.
				\]
				Then we have
				\[
					\mathbb E D_n = \sum_{k = 0}^\infty k \,\mathbb P(D_n = k)
					= \sum_{k = 1}^\infty \mathbb P(D_n \ge k)
					\le \sum_{k = 1}^\infty 2^{c_C - k + 1} = 2^{c_C + 1}.\qedhere
				\]
			\end{proof}
			It turns out that for options expiring at time $n$, there is a significantly better exercise policy than
			the static strategy of waiting until the very end:
			\begin{thm}\label{MLstrategy}
				For plain Kolmogorov complexity, $\sup_n V_n=\infty$,
				even if we require efficient computation of the exercise policy.
			\end{thm}
			The idea of the proof is to use complexity oscillations, first observed by \cite{MR0451322}:
			when the initial part of a string $x$ is a binary encoding of the length of $x$,
			the plain Kolmogorov complexity of $x$ will be low.
			\begin{proof}
					\cite{MR0451322} showed that deficiency is unbounded for all reals:
					for each $X$ and $b$ there is an $n$ with ${D({X \upharpoonright n}) > b}$.
					We can computably identify such an $n$.
					The well known idea is that we take a prefix $X\upharpoonright m$;
					consider it as a binary representation of a length $\ell < 2^m$;
					and then consider $\sigma=X\upharpoonright\ell$.
					Since the beginning of $\sigma$ is known just from the length of $\sigma$,
					$\sigma$ is compressible.
					This translates into an exercise policy for our option:
					at the \emph{grant date} $m$ we decide on the date $\ell$ at which we are going to exercise.
Thus at the grant date our option style is transformed from American to European.
			\end{proof}

			\begin{rem}
				Since $C(x\mid n)\le^+ C(x)$, Theorem \ref{MLstrategy} holds equally for
				length-conditional plain Kolmogorov complexity, and
				Theorem \ref{plainFinite} also holds if we consider
				plain Kolmogorov complexity that is not length-conditional.
			\end{rem}
		\subsection{Prefix-free complexity \texorpdfstring{$K$}{K} with \texorpdfstring{$C$}{C}-style deficiency}
			Let $K$ denote prefix-free Kolmogorov complexity.
			With $D_n(x) = n - K(x)$, there is no limiting deficiency distribution in this case (or one could say the deficiency is in the limit $-\infty$ almost surely).
			That is, $K(w)\ge \abs{w}-c$ for almost all $w$, for any $c$.
			Indeed, for each $c\in\mathbb Z$,
			\[
				\lim_{n\rightarrow\infty}\frac{\left| \sigma\in 2^n: K(\sigma)\ge n-c\right|}{2^n} = 1,
			\]
			as is easily shown using $\sum_\sigma 2^{-K(\sigma)}<1$.
			If the $\limsup$ of the complement is $\delta>0$, then for each $\varepsilon>0$ there exist $N_k$ with
			\[
				1\ge \sum_\sigma 2^{-K(\sigma)} = \sum_n \sum_{\abs{\sigma}=n}2^{-K(\sigma)}
			\]
			\[	> \sum_k \delta(1-\varepsilon) 2^{N_k}2^{-(N_k-c)}
				= (1-\varepsilon)\delta \sum_k^\infty 2^c = \infty.
			\]
			\begin{thm}\label{prefixFinite}
				Let $K$ denote prefix-free Kolmogorov complexity $K$ and define the deficiency $D_n(x)=n-K(x)$
for a string $x$ of length $n$.
				The price of the perpetual option that pays $D_n - a$ is at most $2^{1 - a}$.
			\end{thm}
			\begin{proof}
				By \cite[Lemma 6.2.2]{MR2732288},
				\[
					\mathbb P(\sup_n D_n - a > c) = \mathbb P(\exists n\, K(X\upharpoonright n) < n - c - a) \le 2^{-c - a}.
				\]
				Let ${D_n^+ = \max \{D_n - a, 0\}}$.
				Since we would not exercise an option giving negative payoff, it follows that
				\begin{eqnarray*}
					V \le \mathbb E(\sup_n D_n^+) &=& \sum_{c=0}^\infty c\, \mathbb P\left(\sup_n D_n^+ = c\right)
				\\
					= \sum_{c=1}^\infty c\, \mathbb P\left(\sup_n D_n^+ = c\right)
					&=& \sum_{c=1}^\infty \mathbb P\left(\sup_n D_n^+ \ge c\right)
				\\
					= \sum_{c=1}^\infty \mathbb P\left(\sup_n D_n - a > c-1\right) &\le& \sum_{c=1}^\infty 2^{-(c-1)-a} = 2^{1 - a}.\qedhere
				\end{eqnarray*}

			\end{proof}

		\subsection{Prefix-free complexity \texorpdfstring{$K$}{K} with its natural notion of deficiency}
			\begin{thm}[Deficiency based on an upper bound for \texorpdfstring{$K$}{K}]\label{Kbound}
				If we fix a constant $c_K$ such that for prefix-free Kolmogorov complexity $K$,
				\[
					K(x)\le n + K(n) + c_K
				\]
				for all $x$ of any length $n$,
				and let
				\[
					D_n(x) = n + K(n) + c_K - K(x)\ge 0,
				\]
				then
				$\mathbb E D_n$ is bounded, but $V_n\rightarrow\infty$.
			\end{thm}
			\begin{proof}
				The same proof as for Theorem \ref{plainFinite} but using an analogous property
				shows that $\mathbb E D_n$ is bounded. In this case, however,
				$\sup D_n(X\upharpoonright n)$ will be $\infty$ for almost all $X\in 2^\omega$.
				In fact Li and Vit\'anyi showed
				$D_n(X\upharpoonright n) > \log n$ for infinitely many $n$ for almost all $X$.

				Solovay showed that	$\liminf D_n(X\upharpoonright n)$ will be finite \cite{MillerYu}.

				$V = \infty$ in this case since we can simply wait for a sufficiently high $D_n$ value.
				What about $V_n$? Consider an arbitrary constant,
				which for expository vividness we will take to equal 17.
				Almost surely there will be an $n$ with $D_n(X\upharpoonright n)\ge 17$. Therefore for each $\varepsilon$
				there is an $n_0$ such that
				\[
					\mathbb P \bigcup_{n\le n_0} \{ D_n(X\upharpoonright n)\ge 17 \} \ge 1 - \varepsilon
				\]
				and so $V_{n_0}\ge 17(1 - \varepsilon)$. Moreover $V_n\le V_{n + 1}$ for American options.
				So $V_n\rightarrow\infty$ in this case.
				The exercise policy would be to wait for $D_n=17$ to occur and then exercise.
			\end{proof}

		\begin{sidewaystable}
			\centering
			\begin{tabular}{|c|c|c|c|c|}
				\hline
				$D_n$&
				$\sup_n \mathbb E D_n$&
				$\sup_n V_n$&
				$\mathbb E \sup_n D_n$\\
				\hline
				$n + c_K - K(x)$&
				$\therefore<\infty$&
				$\therefore<\infty$&
				$<\infty$ (Theorem\ \ref{prefixFinite})\\
				$n + K(n) + c_K - K(x)$&
				$<\infty$ (Theorem\ \ref{Kbound})&
				$\infty$ (Theorem\ \ref{Kbound})&
				$\therefore\infty$
				\\
				$n + c_C - C(x)$&
				$<\infty$ (Theorem\ \ref{plainFinite})&
				$\infty$ (Theorem\ \ref{MLstrategy})&
				$\therefore\infty$
				\\
				$n + c_C - C(x\mid n)$&
				$<\infty$ (Theorem\ \ref{plainFinite})&
				$\infty$ (Theorem\ \ref{MLstrategy})&
				$\therefore\infty$
				\\
				\hline
				$\lceil n/2\rceil + 1 - A_N(x)$&
				$<\infty$? (Conjecture \ref{oslo}) &
				$\infty$? (Conjecture \ref{oslo}) &
				$\therefore\infty$?
				\\
				\hline
			\end{tabular}
			\caption{Infinity and finiteness of option prices for various complexity deficiencies $D_n(x)$, for strings $x$ of length $n$.
			The conclusions labeled by $\therefore$ (``therefore'') follow from the inequalities
			$\sup_n \mathbb E D_n \le \sup_n V_n\le \mathbb E \sup_n D_n$
			(Theorem \ref{three}).
			}
			\label{priceOverview}
		\end{sidewaystable}

		An overview of the deficiency option prices is given in Table \ref{priceOverview}.
		\begin{rem}
			Of course, one does not need to only consider deficiencies.
			One could consider an option paying out $K(x) - n$.
			This value will go to infinity, but how fast?
			What is our exercise policy if we are not given access to $K$?
			Another possibility is to consider dips in complexity associated with the Kolmogorov structure function
			\cite{MR2103496}
			and its automatic complexity variant \cite{Kjos-TCS}.
		\end{rem}

		\subsection{Using runs}
			\begin{rem}\label{referee6}
				An anonymous referee suggested the following approach to obtaining results of the form $V_n\rightarrow\infty$.
				Let $R_n$ be the longest run of 0s in a string of length $n$ and let $\mathbb E$ and $\operatorname{Var}$ denote expectation and variance with respect
				to the uniform distribution on $\{0,1\}^n$.
				Now, if $U$ is a universal prefix-free machine,
				we can define another machine $M$ by the following algorithm: on input $x^*$, simulate $U$, and if $U(x^*)=x$, then
				\[
					M(x^*)=f(x):=x\,0^{\lfloor\log_2 \abs{x}\rfloor-c}
				\]
				for a fixed constant $c$.
				The domain of $M$ equals the domain of $U$, hence $M$ is also a prefix-free machine.
				Thus
				\[
					K(x\,0^{\lfloor\log_2 \abs{x}\rfloor-c})\le^+ K(x).
				\]
				Let now $m = \abs{f(x)} = \abs{x} + \lfloor\log_2 \abs{x}\rfloor - c$ and $y=f(x)$.
				Since $K(n)\le ^+ K(m)$ by the choice of $m$, we have
				\[
					K(y)\le n + K(n) + c_K \le^+ n + K(m) + c_K = (m + K(m) + c_K) - (m-n)
				\]
				and
				\[
					C(y)\le^+ n + c_C = m + c_C - (m - n).
				\]
				Now we employ the trading strategy whereby we wait until our input is of the form $x\,0^{\log_2 \abs{x}-c}$, and then exercise.
				By Theorem \ref{BoydThm} below, $\abs{\mathbb E(R_n)-\log_2 n}$ and $\operatorname{Var}(R_n)$ are both bounded by a constant $c$.
				By the argument in Section \ref{Malihe} below, with high probability we will be able to exercise.
				Thus for American options, with payoff $D_n(x)$ either $n + K(n) + c_K - K(x)$ or $c_C - C(x)$, we obtain $V_n\rightarrow\infty$.
			\end{rem}
			\begin{thm}[\cite{Boyd}]\label{BoydThm}
				Let $R_n$ be the longest run of heads in
				a binary sequence of length $n$
				distributed according to the Bernoulli distribution with parameter $1/2$. Let $\log=\ln$. Then
				\[
					\mathbb E(R_n)
					= \log_2 n + \frac{\gamma}{\ln 2} - \frac32 + \varepsilon_1(\log n/\log 2) + r_1(n),
				\]
				where $\varepsilon_1(\alpha)$ is a function of period 1 which satisfies
				$\abs{\varepsilon_1(\alpha)} < 2\times 10^{-6}$ for all $\alpha$, and
				$r_1(n) = O(n^{-1}(\log n)^4) \rightarrow 0$.
				Moreover,
				\[
					\operatorname{Var}(R_n) = \frac1{12}+\frac{\pi^2}{6(\log 2)^2} + \varepsilon_2\left(\frac{\log n}{\log 2}\right) + O(n^{-1}(\log n)^5),
				\]
				where $\varepsilon_2(\alpha)$ has period 1, and $\abs{\varepsilon_2(\alpha)}<10^{-4}$ for all $\alpha$.
			\end{thm}

	\section{Computable forms of complexity}\label{sec:CFC}
		\subsection{Automatic complexity}
			Now the goal is to price the European/American option that pays the
			nondeterministic automatic complexity deficiency $D_n$ of the movements of a stock
			from time 0 to the time $n$ when the option is exercised.
			We suspect that finding the exact price is a computationally intractable problem, both because of
			the conjectured intractability of computing automatic complexity \cite{Kjos-EJC}, and
			because of the exponential number of price paths to consider.

			The interest rate $r$ can be set to 0 or to a positive value.
			For pedagogical reasons, \cite{Shreve}
			uses $r=1/4$ for his main recurring example, and we sometimes adopt that value as well.
			\begin{itemize}
				\item For $n=0$ the option would pay 0 as there are no simple strings,
					and moreover the situation is anyway already known at time $0$.
				\item For $n=1$ the actual string (0 or 1) is not known at time 0 but
					it does not affect the payoff,
					which is 0 either way as there are no simple strings of length 1.
				\item For $n=2$, with up-factor $u=2$, down-factor $d=\frac12$, and $r=1/4$,
					there is a risk-neutral probability of $1/2$ of one of the strings $00$, $11$,
					both of which pay \$1. So the value is
					\[
						(1+r)^{-2}\cdot \frac12\cdot 1 = \frac{16}{50}.
					\]
			\end{itemize}
			In general when the risk-neutral probabilities are $1/2$ each for up and down,
			then the value of the option is directly related to the distribution of the deficiency $D_n$:
			\[
				\sum_{d=0}^{n/2} d \cdot \mathbb P(D_n=d) \cdot (1+r)^{-n} = \mathbb E(D_n)\cdot (1+r)^{-n}.
			\]
			If $D_n$ happened to be Poisson for large $n$, this is approximately $\lambda (1+r)^{-n}$,
			which is decreasing in $n$. However, we have just seen that
			the value for $n=2$ is higher than for $n=0$ and $n=1$.

			\begin{rem}\label{amirQ}
				For an American version, one question is
				whether to exercise the option at time $n=2$ after having seen $00$.
				If we exercise we get \$1. Otherwise the deficiency can at most go up by 1 each time step,
				whereas the interest factor with $r=1/4>0$ is exponential,
				so an upper bound for our payoff is
				\[
					(n/2)(1+r)^{-n} = \frac{n}{2}e^{-n\ln(5/4)}.
				\]
				This expression is maximized at $n=4$ and at $n=5$. Both places it takes the value $.8192$.
			\end{rem}

			\begin{figure}
				\begin{tikzpicture}[>=stealth,sloped]
					\matrix (tree) [%
						matrix of nodes,
						column sep=1.5cm,
						row sep=0cm,
					]
					{
								&   	&		&   	& (1111):2\\
								&   	&		&(111):1&         \\
								&   	&		&   	& (1110):1\\
								&   	& (11):1&   	&         \\
								&   	&		&   	& (1101):0\\
								&   	&		&(110):0&         \\
								&   	&		&   	& (1100):0\\
								& (1):0 &		&   	&         \\
								&   	&		&   	& (1011):0\\
								&   	&		&(101):0&         \\
								&   	&		&   	& (1010):1\\
								&   	& (10):0&   	&         \\
								&   	&		&   	& (1001):0\\
								&   	&		&(100):0&         \\
								&   	&		&   	& (1000):1\\
						():0    &   	&		&   	&         \\
								&   	&		&   	& (0111):1\\
								&   	&		&(011):0&         \\
								&   	&		&   	& (0110):0\\
								&   	& (01):0&   	&         \\
								&   	&		&   	& (0101):1\\
								&   	&		&(010):0&         \\
								&   	&		&   	& (0100):0\\
								& (0):0 &		&   	&         \\
								&   	&		&   	& (0011):0\\
								&   	&		&(001):0&         \\
								&   	&		&   	& (0010):0\\
								&   	& (00):1&   	&         \\
								&   	&		&   	& (0001):1\\
								&   	&		&(000):1&         \\
								&   	&		&   	& (0000):2\\
					};
					\draw[->] (tree-2-4)  -- (tree-1-5)  node [midway,above] {$H$};
					\draw[->] (tree-2-4)  -- (tree-3-5)  node [midway,below] {$T$};
					\draw[->] (tree-4-3)  -- (tree-2-4)  node [midway,above] {$H$};
					\draw[->] (tree-4-3)  -- (tree-6-4)  node [midway,below] {$T$};
					\draw[->] (tree-6-4)  -- (tree-5-5)  node [midway,above] {$H$};
					\draw[->] (tree-6-4)  -- (tree-7-5)  node [midway,below] {$T$};
					\draw[->] (tree-8-2)  -- (tree-4-3)  node [midway,above] {$H$};
					\draw[->] (tree-8-2)  -- (tree-12-3) node [midway,below] {$T$};
					\draw[->] (tree-10-4) -- (tree-9-5)  node [midway,above] {$H$};
					\draw[->] (tree-10-4) -- (tree-11-5) node [midway,below] {$T$};
					\draw[->] (tree-12-3) -- (tree-10-4) node [midway,above] {$H$};
					\draw[->] (tree-12-3) -- (tree-14-4) node [midway,below] {$T$};
					\draw[->] (tree-14-4) -- (tree-13-5) node [midway,above] {$H$};
					\draw[->] (tree-14-4) -- (tree-15-5) node [midway,below] {$T$};
					\draw[->] (tree-16-1) -- (tree-8-2)  node [midway,below] {$H$};
					\draw[->] (tree-16-1) -- (tree-24-2) node [midway,below] {$T$};
					\draw[->] (tree-18-4) -- (tree-17-5) node [midway,above] {$H$};
					\draw[->] (tree-18-4) -- (tree-19-5) node [midway,below] {$T$};
					\draw[->] (tree-20-3) -- (tree-18-4) node [midway,above] {$H$};
					\draw[->] (tree-20-3) -- (tree-22-4) node [midway,below] {$T$};
					\draw[->] (tree-22-4) -- (tree-21-5) node [midway,above] {$H$};
					\draw[->] (tree-22-4) -- (tree-23-5) node [midway,below] {$T$};
					\draw[->] (tree-24-2) -- (tree-20-3) node [midway,above] {$H$};
					\draw[->] (tree-24-2) -- (tree-28-3) node [midway,below] {$T$};
					\draw[->] (tree-26-4) -- (tree-25-5) node [midway,above] {$H$};
					\draw[->] (tree-26-4) -- (tree-27-5) node [midway,below] {$T$};
					\draw[->] (tree-28-3) -- (tree-26-4) node [midway,above] {$H$};
					\draw[->] (tree-28-3) -- (tree-30-4) node [midway,below] {$T$};
					\draw[->] (tree-30-4) -- (tree-29-5) node [midway,above] {$H$};
					\draw[->] (tree-30-4) -- (tree-31-5) node [midway,below] {$T$};
				\end{tikzpicture}
				\caption{
					Deficiency tree for $n=4$, see Remark \ref{MFE-remark}.
				}\label{deficiency-tree}
			\end{figure}
			\begin{figure}
				\begin{tikzpicture}[>=stealth,sloped]
					\matrix (tree) [%
						matrix of nodes,
						minimum size=0.4cm,
						column sep=2.0cm,
						row sep=0.12cm,
						style={nodes={draw,rounded corners}},
					]
					{
								&   	&		&   & 2 \\
								&   	&		&1.2&   \\
								&   	&		&   & 1 \\
								&   	& 1     &   &   \\
								&   	&		&   & 0 \\
								&   	&		& 0 &   \\
								&   	&		&   & 0 \\
								& 0.528 &		&   &   \\
								&   	&		&   & 0 \\
								&   	&		&0.4&   \\
								&   	&		&   & 1 \\
								&   	& 0.32  &   &   \\
								&   	&		&   & 0 \\
								&   	&		&0.4&   \\
								&   	&		&   & 1 \\
						0.4224  &   	&		&   &   \\
								&   	&		&   & 1 \\
								&   	&		&0.4&   \\
								&   	&		&   & 0 \\
								&   	& 0.32  &   &   \\
								&   	&		&   & 1 \\
								&   	&		&0.4&   \\
								&   	&		&   & 0 \\
								& 0.528 &		&   &   \\
								&   	&		&   & 0 \\
								&   	&		& 0 &   \\
								&   	&		&   & 0 \\
								&   	& 1     &   &   \\
								&   	&		&   & 1 \\
								&   	&		&1.2&   \\
								&   	&		&   & 2 \\
					};
					\draw[->] (tree-2-4)  -- (tree-1-5)  node [midway,above] {$H$};
					\draw[->] (tree-2-4)  -- (tree-3-5)  node [midway,below] {$T$};
					\draw[->] (tree-4-3)  -- (tree-2-4)  node [midway,above] {$H$};
					\draw[->] (tree-4-3)  -- (tree-6-4)  node [midway,below] {$T$};
					\draw[->] (tree-6-4)  -- (tree-5-5)  node [midway,above] {$H$};
					\draw[->] (tree-6-4)  -- (tree-7-5)  node [midway,below] {$T$};
					\draw[->] (tree-8-2)  -- (tree-4-3)  node [midway,above] {$H$};
					\draw[->] (tree-8-2)  -- (tree-12-3) node [midway,below] {$T$};
					\draw[->] (tree-10-4) -- (tree-9-5)  node [midway,above] {$H$};
					\draw[->] (tree-10-4) -- (tree-11-5) node [midway,below] {$T$};
					\draw[->] (tree-12-3) -- (tree-10-4) node [midway,above] {$H$};
					\draw[->] (tree-12-3) -- (tree-14-4) node [midway,below] {$T$};
					\draw[->] (tree-14-4) -- (tree-13-5) node [midway,above] {$H$};
					\draw[->] (tree-14-4) -- (tree-15-5) node [midway,below] {$T$};
					\draw[->] (tree-16-1) -- (tree-8-2)  node [midway,below] {$H$};
					\draw[->] (tree-16-1) -- (tree-24-2) node [midway,below] {$T$};
					\draw[->] (tree-18-4) -- (tree-17-5) node [midway,above] {$H$};
					\draw[->] (tree-18-4) -- (tree-19-5) node [midway,below] {$T$};
					\draw[->] (tree-20-3) -- (tree-18-4) node [midway,above] {$H$};
					\draw[->] (tree-20-3) -- (tree-22-4) node [midway,below] {$T$};
					\draw[->] (tree-22-4) -- (tree-21-5) node [midway,above] {$H$};
					\draw[->] (tree-22-4) -- (tree-23-5) node [midway,below] {$T$};
					\draw[->] (tree-24-2) -- (tree-20-3) node [midway,above] {$H$};
					\draw[->] (tree-24-2) -- (tree-28-3) node [midway,below] {$T$};
					\draw[->] (tree-26-4) -- (tree-25-5) node [midway,above] {$H$};
					\draw[->] (tree-26-4) -- (tree-27-5) node [midway,below] {$T$};
					\draw[->] (tree-28-3) -- (tree-26-4) node [midway,above] {$H$};
					\draw[->] (tree-28-3) -- (tree-30-4) node [midway,below] {$T$};
					\draw[->] (tree-30-4) -- (tree-29-5) node [midway,above] {$H$};
					\draw[->] (tree-30-4) -- (tree-31-5) node [midway,below] {$T$};
				\end{tikzpicture}
				\caption{
					Option prices corresponding to Figure \ref{deficiency-tree}.
				}\label{option-price-tree}
			\end{figure}

			\begin{table}
				\begin{center}
				\begin{tabular}{|r|l|c|l|}
					\hline
					Length&$\mathbb E D_n$& $\le$ & $V_n$\\
					\hline
					 0	&	$0$    	& $=$ &  	$0$\\
					 2	&	$0.5$  	& $=$ &  	$0.5$\\
					 4	&	$0.625$	& $<$ &  	$0.75$\\
					 6	&	$0.687$	& $<$ &  	$0.875$\\
					 8	&	$0.765$	& $<$ &  	$1.070$\\
					10	&	$0.791$	& $<$ &  	$1.191$\\
					12	&	$0.720$	& $<$ &  	$1.236$\\
					\hline
				\end{tabular}
			\end{center}
				\caption{
					Static versus dynamic exercise policies for nondeterministic automatic complexity.
				}
				\label{static}
			\end{table}

			To obtain a reasonable level of abstraction
			it is valuable to consider infinite price paths
			and associate a finite complexity deficiency with them. We can do so if
			the nondeterministic automatic complexity deficiencies of prefixes of an infinite binary sequence
			are almost surely bounded (Conjecture \ref{oslo}; see also Table \ref{priceOverview}).

			\begin{con}\label{oslo}
				For nondeterministic automatic complexity $A_N$,
				\[
					\mathbb P(\sup_n D_n<\infty) = 1,
				\text{ and yet}\quad
					\sup_n V_n = \infty.
				\]
			\end{con}

			\begin{rem}\label{MFE-remark}
				\cite{MFE} studied
				a perpetual American option that pays the complexity deficiency of the sequence of up and down ticks
				(considered as 1s and 0s) upon exercise.
				With interest rate set to zero ($r=0$) the price of this security may be infinity, based on tentative numerical evidence.
				That is, for $A_N$,
				\[
					\sup_n V_n = \infty,
				\]
				although $\mathbb E D_n$ seems to approach a finite limit (see Table \ref{static}).
				For positive interest rates the price is finite (see Remark \ref{amirQ}).
				They found numerical evidence that for $r=1/4$ the price is $0.47$.
				See Figure \ref{deficiency-tree} for the deficiencies of strings of length at most 4,
				and Figure \ref{option-price-tree} for corresponding calculated option prices.
				The price of the American option with expiry $2k$ and expiry $2k+1$ are the same,
				as is easy to prove.
			\end{rem}

			\begin{df}
				Let $W_n$ be the price of the European option paying the
				nondeterministic automatic complexity deficiency $D(x)$ for the price path $x$ of length $n$.

				\noindent\emph{Decision problem:} $\mathrm{PRICE}$.

				\noindent\emph{Instance:} A pair of nonnegative integers $n$ and $k$ with
				\[
					0\le \frac{k}{2^n}\le\lfloor n/2\rfloor +1.
				\]

				\noindent\emph{Question:} Is $W_n\ge k/2^n$?
			\end{df}
			Recall that $\mathrm{E}$ is the class of single-exponential time decidable decision problems.
			\begin{thm}\label{referee}
				$\mathrm{PRICE}$ is in $\mathrm{E}$.
			\end{thm}
			\begin{proof}
				\cite{Kjos-EJC} considered the problem $\mathrm{DEFICIENCY}$ of deciding whether,
				given an integer $k$ and a sequence $x$,
				the nondeterministic automatic complexity deficiency $D(x)$ satisfies $D(x)\ge k$.
				They showed that $\mathrm{DEFICIENCY}$ is in $\mathrm{E}$.
				Since there are only single-exponentially many price paths of length $n$,
				the usual backwards recursive algorithm for
				option pricing in the binomial model \cite{Shreve} gives the theorem.
			\end{proof}
			The same proof shows that
			the analogous statement to Theorem \ref{referee} for American options holds as well.

		\subsection{Run complexity}\label{Malihe}
			If the payoff of our option is just the longest run of heads then \cite{Alikhani} showed that
			the price of the option is $\Theta(\log_2 n)$.
			This corresponds to automata that always proceed to a fresh state,
			except that one state may be repeated (namely, the state of the longest run).

			\begin{df}\label{df:runComplexity}
				The \emph{run complexity} $C_R$ of a binary sequence $x$ is defined by $C_R(x)=n+1-r$,
				where $n$ is the length of $x$ and $r$ is the length of the longest run of 0s or 1s in $x$.
			\end{df}
			This complexity notion has the advantage that it is efficiently computable.
			\cite{Kjos-COCOA} studied it in more detail
			and also considered multiple runs, as in the Wald--Wolfowitz runs test.

			In the rest of this subsection we give the argument of \cite{Alikhani}.
			We assume familiarity with basic discrete options \cite{Shreve}.
			A coin tossing sequence is $\omega_1\dots\omega_N$ where each $\omega_i\in\{H,T\}$.
			(Read $H$ as ``heads'' and $T$ as ``tails''.)
			\begin{df}
				For each $0\le n\le N$, the \emph{current run of heads} in the coin tossing sequence $\omega_1\dots\omega_n$ is defined by
				\[
					G_n(\omega)=\max \{r: \omega_{n-r+1} = \dots = \omega_n = H\}.
				\]
				The \emph{run option} is the American option where the payoff when exercised at time $n\le N$ is
				$G_n(\omega)$.
				Let $V^A $ be the price of the run option.
				Define a stopping time $\tau_t$ by
				\[
					\tau_t(\omega_1 \dots \omega_N)=\min\{s: G_s=[\mathbb E(R_N)] - t\},
				\]
				where $R_N$ is the longest run of heads in a coin tossing sequence of length $N$.
			\end{df}
			Thus, the trading strategy corresponding to $\tau_t$ is to wait for a run of heads
			that is almost as long as we ever expect to see before time $N$,
			with ``almost'' being qualified and measured by the parameter $t$.
			\begin{df}
				Let $[x]$ denote the nearest integer of $x$. In particular,
				$[x]$ is an integer $k$ with $k-1\le x\le k+1$.
			\end{df}

			\begin{thm}\label{bumblebee}
				Given $N$ there is a deterministic choice of $t=t_N$ such that
				there is a sequence of numbers $\varepsilon_N$ with
				$\lim_{N \to +\infty} \varepsilon_N=0$, and
				constants $c_2$ and $c$, such that for large $N$,
				\[
					\mathbb E(G_{\tau_{t_{N}}})\geq (\log_2N-c_2- c \sqrt[3] {\ln N})(1-\varepsilon_N).
				\]
			\end{thm}
			\begin{proof}
				Let $S_n$ be the set of stopping times taking values in $\{n, n+1,\dots,\infty\}$
				\cite[Section 4.4]{Shreve}.
				The price process $V_n^A$ for the run option satisfies the American risk-neutral formula
				\[
					V_n^A=\max_{\tau \in S_n} {\mathbb E_n}[\mathbb{I}_{\tau \leq N} G_{\tau}],
					\quad \text{for } n=0,1,\dots,N.
				\]
				So for each $t$,
				\[
					V_n^A \geq {\mathbb E_n}[(\mathbb{I}_{\tau_t \leq N}) G_{\tau_t}].
				\]
				Now we find a lower bound on $\mathbb E(G_{\tau_t})$.
				\begin{align*}
					\mathbb E(G_{\tau_{t}})
					&=  \mathbb E(G_{\tau_{t}}| G_{\tau_{t}} > 0) \Pr(G_{\tau_{t}} > 0)\\
					&=  ([\mathbb E(R_N)] - t)(\Pr\{R_N \ge [\mathbb E(R_N)] - t  \})\\
					&\ge ([\mathbb E(R_N)] - t)(\Pr\{R_N \ge \mathbb E(R_N) - t + 1 \})\\
					&\ge ([\mathbb E(R_N)] - t)(\Pr\{|R_N- \mathbb E(R_N)| \leq (t-1)\})\\
					&\ge ([\mathbb E(R_N)] - t)  \left(1-\frac{\operatorname{Var}(R_N)}{(t-1)^2}\right)
					\qquad\text{(by Chebyshev's Inequality)}\\
					&\ge (\mathbb E(R_N) - 1 - t)\left(1-\frac{\operatorname{Var}(R_N)}{(t-1)^2}\right).
				\end{align*}
				By Theorem \ref{BoydThm},
				\[
					\operatorname{Var}(R_N) = \pi ^2/6\ln^2(2)+1/12+r_2(N)+\varepsilon_2(N) \leq 4
				\]
				for large $N$.
				Let $\mathbb E(R_N)=a$; then we get
				\begin{equation}\label{star}
					\mathbb E(G_{\tau_t})\ge (a-t-1)\left(1-\frac4{(t-1)^2}\right).
				\end{equation}
				Now we find the $t=t_N$ such that
				the right-hand side of (\ref{star}) is maximized.
				The corresponding third degree polynomial has negative discriminant.
				Therefore it has one real root, which was calculated by $\mathrm{Mathematica}$:
				\[
					t=\frac{
						\left(\frac{2}{3}\right)^{2/3}\sqrt[3]{
							9\ln^2(2)\ln (N)+\sqrt{3} \sqrt{27 \ln^4(2) \ln^2(N)+4 \ln^6(2)}
						}
					}{\ln (2)}
				\]
				\[
					-\frac{2\sqrt[3]{\frac{2}{3}} \ln(2)}{
						\sqrt[3]{9 \ln^2(2) \ln(N)+\sqrt{3} \sqrt{27 \ln ^4(2) \log^2(N)+4 \ln ^6(2)}}
					}.
				\]
				By the second derivative test, since
				\[
					\frac{d^2}{dt^2} (a-t)(1-4/t^2) = -3t^2-4 \leq 0,
				\]
				we see that $t$ maximizes the right-hand side of ($*$).
				We have
				\[
					\lim_{n\to\infty}-\frac{2\sqrt[3]{\frac{2}{3}} \ln (2)}
					{\sqrt[3]{9 \ln ^2(2) \ln (n)+\sqrt{3} \sqrt{27 \ln ^4(2) \ln ^2(N)+4 \ln ^6(2)}}} = 0
				\]
				and hence
				\[
					\frac{t}{(4/\ln 2)^{1/3}( \sqrt[3] {\ln N})}\rightarrow 1.
				\]
				Therefore, $t = t_N \in \Theta ( \sqrt[3] {\ln N})$ and so
				\[
					\mathbb E(G_{\tau_{t_{N}}}) \geq (\log_2N-c_2- c\sqrt[3] {\ln N})(1-\varepsilon_N).
				\]
			\end{proof}
			\begin{cor}\label{th1}
				$V^{A} \sim \log_2N$.
			\end{cor}
			\begin{proof}
				$V^{A} $ is bounded below by the expected payoff of the strategy that
				waits for $\mathbb [E(R_N)]-t_N$ heads, with $t_N$ as in Theorem \ref{bumblebee}, and then exercises.
				On the other hand, $V^{A} $ is bounded above $\mathbb E(R_N)$.
				Therefore
				\[
					\mathbb E(R_N)-t_N\leq V^{A} \leq \mathbb E(R_N).
				\]
				By Theorem \ref{BoydThm},
				\[
					\mathbb E(R_N)=\log_2(N/2)+ \gamma /\ln2-1/2=\log_2N+O(1),
				\]
				and so by Theorem \ref{bumblebee},
				\[
					\log_2N -c_2 -\sqrt[3] {\ln N} \leq V^{A} \leq \log_2N+O(1).
				\]
				Dividing by $\log_2 N$ we get
				\[
					1- o(1) \leq \frac{V^{A}}{\log_2 N} \leq 1+ o(1).\qedhere
				\]
			\end{proof}
	\section{Robustness}
		We now consider whether, in the phrase of an anonymous referee,
		\begin{quote}
			small perturbations on input sequences can have drastic effects on
			our studied measurements of complexity.
		\end{quote}
		In other words, whether errors in the measurement of a sequence
		will lead to large errors in the calculated complexity.
		Let $d(x,y)$ denote the Hamming distance between two sequences of the same length $x$ and $y$.
		Let us consider our three types of complexity in turn.
		\paragraph{Run complexity.}
			Here a change in a single bit sometimes cuts the longest run in half.
			That is,
			if $d(x,y)=1$ then $C_R(x)=n-r_x$ and $C_R(y)=n-r_y$ where $r_x\le 2 r_y + 1$.

			On the other hand, since
			the longest run will only be about $\log_2 n$ \cite{Boyd},
			a random change in a single random bit will tend to leave the complexity unchanged.
		\paragraph{Automatic complexity.}
			Here we have numerical evidence that a change in a single bit sometimes has large effects.
			For instance, consider the string $0^n$ which becomes $0^a10^{n-a-1}$. See Table \ref{perturbing}.
		\paragraph{Kolmogorov complexity.}
			A change in a single bit will affect the complexity only logarithmically
			(by at most about $2\log n$)
			since a description of the sequence can include
			hard-coded information about where the changed bit is.
			\cite{FLV} studied Kolmogorov complexity with error in detail.
			\begin{table}
				\centering
				\begin{tabular}{|c|c|}
					\hline
					$w$&$A_N(w)$\\
					\hline
					$0^{23}$   & 1\\
					$0^{22} 1$  & 2\\
					$0^{21} 1 0$ & 3\\
					$0^{20} 1 0^2$& 4\\
					$0^{19} 1 0^3$& 5\\
					$0^{18} 1 0^4$& 6\\
					$0^{17} 1 0^5$& 7\\
					$0^{16} 1 0^6$& 8\\
					$0^{15} 1 0^7$& 9\\
					$0^{14} 1 0^8$& 8\\
					$0^{13} 1 0^9$& 8\\
					$0^{12} 1 0^{10}$&8\\
					$0^{11} 1 0^{11}$&7\\
					\hline
				\end{tabular}
				\caption{
					Nondeterministic automatic complexity in the Hamming ball of radius 1 around $0^{n}$, $n=23$.
				}\label{perturbing}
			\end{table}
	\section{Enhanced Content}
		\paragraph{AutoComplex.} This app for Android devices \cite{links/AC}
		lets you look up nondeterministic automatic complexity values of particular strings.
		The app tells you the complexity of a given string and also provides a ``proof'' or ``witness''.

		This witness is a uniquely accepting state sequence,
		i.e., a sequence of states visited during a run of a witnessing automaton.
		It is analogous to a shortest description $x^*$ of a string $x$,
		familiar from the study of Kolmogorov complexity.

		The app also provides some extensions of the string suggested by
		the familiar autocompletion feature used in search engines.

		\paragraph{The Complexity Guessing Game and the Complexity Option Game.} These two online games \cite{links/CGG,links/COG} invite the player to guess complexities,
		or implement an exercise policy for a complexity-based financial option, respectively.
		The games include graphical displays of millions of the relevant automata.
	\section*{Acknowledgments}
		This work was partially supported by
		a grant from the Simons Foundation
		(\#315188 to Bj\o rn Kjos-Hanssen).

		This material is based upon work supported by the National Science Foundation under Grant No.\ 0901020.
	\bibliographystyle{alpha}


\section{Introduction}

One of the central challenges faced by the field of spintronics, as an alternate to conventional charge-based information processing, is to encode information in a magnetic configuration (i.e. a collection of spins) which is both stable against thermal fluctuations and electrically manipulated with minimal energy budget. Recently, magnetic skyrmions have emerged as one such candidate configuration, opening a new sub-field of information processing with skyrmions, dubbed as \textit{skyrmionics}.\cite{Nagaosa2013} Skyrmions are topologically nontrivial magnetic textures characterized by a non-zero integer-valued skyrmion number $\mathcal{N}$, which counts the number of times the texture wraps a sphere in the spin-space\cite{rajaraman1982solitons}. Much recent interest has been fuelled by observation of the skyrmion crystal phase\cite{muhlbauer2009skyrmion,*Yu2010,*Heinze2011}, its emergent electrodynamic properties\cite{Schulz2012} and manipulation by currents at low temperatures.\cite{Jonietz2010,*Romming2013}

Meanwhile, motivated by room temperature applications, thin films with perpendicular anisotropy have been proposed as hosts for controlled nucleation and manipulation of individual skyrmions \cite{Sampaio2013}. Single skyrmions in such films can be stabilized by either Dzyaloshinskii-Moriya interaction(DMI)\cite{Dzioloshinskii, *Moriya} or dipole-dipole interaction(DDI) \footnote{In the case of DDI, more generic cylindrical magnetic domains, known as bubbles \cite{malozemoff1979magnetic}, can be stabilized, which may or may not have a non-zero skyrmion number \cite{Yu2012}. Here we focus only on textures which are topologically non-trivial and hence refer to them as skyrmions following Ref. \cite{Nagaosa2013}}competing against Zeeman and exchange energies.
Additionally, these films can be typically sandwiched between a dielectric and a high spin-orbit coupling material resulting in broken inversion symmetry along the growth direction. Such film structures, apart from allowing for a finite DMI, have recently been shown to exhibit current-induced spin-orbit torques(SOT) \cite{MihaiMiron2010,*Liu2012}, which, in turn, result in efficient current-induced motion of chiral magnetic textures. \cite{emorinm13, *ryunnt13} These attractive properties have made such films  an ideal candidate for skyrmion-based race-track-like memory applications.\cite{Sampaio2013, *Iwasaki2013} In fact more recently, experimental evidence for skyrmionic configurations stabilized at room temperature in thin films \cite{wanjun_skyrmion, *beach_skyrmion} and multilayers \cite{fert_skyrmion} in proximity with heavy metals have been presented. In Ref. \onlinecite{wanjun_skyrmion, *beach_skyrmion}, current-induced motion has also been observed.

In this article, we propose and show|via a combination of symmetry based  phenomenology and micromagnetic simulations|that an electric-field applied across such film structures can dramatically influence current-induced skyrmion motion. In particular, we find that for a fixed current, the electric-field can control both the speed and the direction of skyrmion motion. More importantly, we show that by applying electric-fields in a certain pattern, defined via gated structures, skyrmions can be guided along desired trajectories. We also identify the mechanism for this electric-field control of skyrmion motion, which can be explained in terms of the change in the static properties of skyrmions, brought about by the electric-field induced modification of the micromagnetic free energy. Finally, utilizing this additional electrical knob we show that the realm of \textit{skyrmionics} can be extended  beyond the race-track-like memory applications, to possibly realize logic and computing functionalities.

\begin{figure}[h]
\centering
\includegraphics[width=0.5\textwidth]{schematic_fig1_new.pdf}
\caption{Schematic of the system: A ferromagnet(FM) layer with a skyrmion, sandwiched between a heavy metal(HM) and a dielectric, breaking the symmetry along the $z$ axis. A current through HM with density $J$ drives skyrmion via SOT, while simultaneously local electric fields (oriented along $z$) can be applied at a gate region by an external voltage $V$.}
\label{schematic}
\end{figure}

\section{Electric-field coupling: Phenomenology}
We begin by constructing a general phenomenological model describing electric-field coupling to the magnetization dynamics based on the symmetries of the structure. We are interested here in two dimensional ferromagnetic films considered to have the following symmetry properties (see Fig.~\ref{schematic}): broken inversion symmetry along the growth axis (oriented along $z$), by interfacing it with different materials on both sides and application of an electric field, which is assumed to be applied along the $z$ axis via gates. While for simplicity, the structure is considered isotropic about the $z$ axis \footnote{As drawn, the isotropicity about the $z$ axis is broken \textit{globally} by the gates, however, here we are interested in electric-field coupling terms which result in local modification of magnetization dynamics.}. In addition, we are interested in the temperature regime well below the Curie temperature of the ferromagnet, where, suppressing the magnitude fluctuations of magnetization, the magnetization dynamics can be expressed within the Landau-Lifshitz-Gilbert framework as\cite{landauBK80} :
\begin{equation}
\partial_t{\bf m}=-\gamma {\bf m \times H_*}+\alpha{\bf m \times \partial_t m}.
\label{LLG2}
\end{equation}
Here ${\bf m}$ is a unit vector along the magnetization ${\bf M}$ (with magnitude $M_s$), i.e. ${\bf M} \equiv M_s{\bf m}$, while $\gamma$ and $\alpha$ label gyromagnetic ratio and Gilbert damping parameters, respectively. Moreover, we have defined ${\bf H_*}\equiv {\bf -\delta_M\mathcal{F}+H}(J,E)$, with ${\bf -\delta_M\mathcal{F}}$ representing the effective field contribution derivable from a micromagnetic free energy $\mathcal{F}$, and $H(J,E)$ denoting the contribution due to application of current(having a current density, $J$) and electric-field($E$). In its minimalistic form, the micromagnetic free energy is comprised of  the classical dipole-dipole interaction $\mathcal{F}_d$, the exchange interaction parameterized by an exchange constant $A$, and the Zeeman energy due to an applied magnetic field ${\bf H_a}$. In addition, the breaking of inversion symmetry about the $z$ axis in the presence of spin-orbit interaction gives rise to interfacial perpendicular anisotropy and DMI\cite{Dzioloshinskii, *Moriya}, whose strengths are parameterized by $K$ and $D$, respectively, resulting in:

\begin{align}
\mathcal{F}=\mathcal{F}_d +A[(\partial_x {\bf m})^2 + (\partial_y {\bf m})^2]- {\bf M\cdot H_a} \\ \nonumber - Km_z^2 + Dm_z{\bf \nabla \cdot m}.
\label{free}
\end{align}
Here, ${\bf \nabla}\equiv \partial_x{\bf x}+\partial_y{\bf y}$. Similarly, the current and electric field-induced spin-orbit fields, obtained upon imposing the above mentioned structural symmetries on Eq.~\ref{LLG2} (noting  $J$ and $m_z$ are even, while $E$, $m_x$ and $m_y$ are odd under inversion about $z$ axis) and, in the spirit of linear response, retaining terms linear in $E$ and $J$, are given by:

\begin{align}
{\bf H}(J,E)=\eta_D J{\bf m \times y} +  \zeta_D Em_z{\bf m \times z} \\ \nonumber +\eta_F J{\bf y} + \zeta_F Em_z{\bf z}  .
\label{field}
\end{align}
The terms proportional to $\eta_D$ and $\zeta_D$ represent the dissipative components, i.e. which cannot be derived from a free energy, while terms proportional to $\eta_F$ and $\zeta_F$ represent current and electric-field-induced modification of $\mathcal{F}$. In particular, the terms proportional to current density represent the field-like and anti-damping like components of spin-orbit fields, microscopically derived from spin-Hall and Rashba/Edelstein effects\cite{PhysRevLett.83.1834, *rashba, *Edelstein}. Additional current-dependent terms representing corrections due to angle-dependence of spin-orbit field and symmetry-allowed dissipative torques inexpressible in the simple anti-damping like form \cite{Garello2013, *Yu2014} are not included for simplicity. On the other hand, the parameter describing coupling of electric-field to magnetization, denoted by $\zeta_F$, can be identified as electric-field dependent perpendicular magnetic anisotropy. Microscopically, electric-charge- \cite{Duan2008,*Nakamura2008, *maruyamaNATNANO09}, strain- \cite{Eerenstein2006} and ionic movement-induced \cite{Bauer2014} anisotropy modification are few examples  which are gaining increased attention in the spintronics community for exploring, both, fundamental physics and potential low-power technological applications \cite{amiri2012voltage}. Particularly for domain-wall based devices, the electric-field dependent anisotropy has been shown to trap domain walls\cite{Bauer2013} and proposed to induce domain-wall motion\cite{PhysRevB.88.224422}. Finally, the dissipative coupling of electric-field should become relevant for very thin dielectrics \cite{Silas} which, to the best of our knowledge, has not yet been measured experimentally.

At this point we mention for completeness that terms, allowed by symmetry, where electric-field and current couple to gradients of magnetization,  which could themselves be interesting to explore in proposed experimental structures, have been omitted from Eq.~\ref{free}. For example, the electric-field could generate a term of the form $\sim Em_z{\bf \nabla \cdot M}$, describing microscopic electric-field dependence of DMI. Such electric-field-induced DMI has been proposed to induce a transverse ME effect in spiral spin magnets \cite{electricDMI}. Motivated by including minimal ingredients to stabilize skyrmions and study non-trivial effects of electric-field on their dynamics based on the available experimental data, we set $D=\eta_F=\zeta_D=0$ in the following sections. However, the qualitative features of electric-field control and its mechanism are expected to be extended for the case when some of these parameters are included as well.

\begin{figure}[h]
\centering
\includegraphics[width=0.5\textwidth]{static_fig2_new2.pdf}
\caption{Static properties of skyrmion as a function of perpendicular anisotropy $K$: broken vertical line marks approximate boundary between two regions. For $K>4.25\times 10^6$~erg/cm$^3$, skyrmion is stable, with its micromagnetic configuration for $K=4.5\times 10^6$~erg/cm$^3$ shown at top right corner. Here $m_z$ denotes the out of plane component of the magnetization vector, while the in-plane components are shown with an arrow. The diameter and domain-wall width surrounding the skyrmion in this region is represented by triangle and square markers, respectively. For $K<4.25\times 10^6$~erg/cm$^3$ the skyrmion is unstable, instead a multi-domain/ in-plane state is favored.}
\label{static_prop}
\end{figure}

\section{Electric-field effect: statics}
The dynamic control of skyrmions, as will be explained later, can be understood in terms of the modification of their static properties. To this end,  we discuss first the electric-field effect on the static properties of a skyrmion. In general, two separate regimes can be defined based on the stability of the skyrmion. In the first regime, the skyrmion remains stable with a smooth change in its diameter $D_s$, and the domain-wall width $\Delta_w$, surrounding the skyrmion. This change occurs in order to minimize the micromagnetic energy corresponding to the electric-field induced modification of perpendicular anisotropy: the energy cost, due to deviation of magnetization from the easy axis in the wall region, increases with increasing $K$. In an attempt to reduce this energy cost, the domain wall area ($\sim 2\pi D_s \Delta_w$) is reduced resulting in decrease of both diameter of skyrmion and the wall-width. In the second regime, on the other hand, the skyrmion itself becomes unstable. This instability occurs close to the out-of-plane to in-plane transition of magnetization when the perpendicular anisotropy is lowered to a value, such that, the perpendicular anisotropy energy is overwhelmed by the dipole-dipole interaction, due to the out of plane component of the magnetization \cite{malozemoff1979magnetic}.

To demonstrate the qualitative picture presented above in a specific numerical model, we perform micromagnetic simulations for a DDI-stabilized skyrmion(i.e. with DMI strength set to zero) with saturation magnetization, $M_s=920$~emu/cm$^3$ and exchange stiffness $A=1$~$\mu$erg/cm. In order to take electric-field-induced modification of perpendicular anisotropy into account, the strength of perpendicular anisotropy was varied in the range $K=[2$-$5.5]\times 10^6$~erg/cm$^3$. This range corresponds to films with $K=4.25\times 10^6$~erg/cm$^3$, \cite{CoPd} in the absence of electric-field, and a maximum value of electric-field being $\sim 0.1$~MV/cm, for a coupling constant $\zeta=20$~erg/(V$\cdot$cm$^2$) \cite{Carman}. These material parameters are typical for strain-based ferromagnet/dielectric heterostructures such as CoPd(alloys)/PMN-PT, which are chosen as they exhibit one of the largest values of magneto-electric coupling (i.e. $\zeta$) at room temperature \cite{Carman}. In addition, a DDI skyrmion state has been found to be stable in finite-sized nanodisks of cobalt- and iron-based ferromagnets with similar material parameters \cite{Hehn1996,*Moutafis2007}. The simulated magnetic films are assumed to be two-dimensional with periodic boundary conditions in the film plane and a thickness of $t=32$ nm. Additionally, an external magnetic field of strength $H_{a}/H_d=0.3$ with $H_d=4\pi M_s$, is applied along the $z$ axis, which is needed to stabilize a DDI skyrmion for films of infinite extent \cite{malozemoff1979magnetic}. All micromagnetic simulations are performed using LLG Micromagnetic Simulator \cite{LLG} with temperature set to zero.

To study the static properties of a skyrmion, the initial magnetization was set close to a film with a single skyrmion state, i.e. with a central region of sufficiently large diameter pointing along $-z$ and the rest of the film oriented along $+z$. This initial configuration was then allowed to relax to equilibrium for each value of perpendicular anisotropy. The result of such a procedure is summarized in Fig.~\ref{static_prop}. For anisotropy strength $K<K_c=4.25\times 10^6$~erg/cm$^3$, the single skyrmion state is unstable, favoring a multi-domain (for relatively strong $K$, i.e $3<K<4.25\times 10^6$~erg/cm$^3$) or in-plane magnetization (for still weaker anisotropies, i.e. $K<3\times 10^6$~erg/cm$^3$). Such a behavior is typical for films, where the out-of-plane magnetization-induced dipole energy ($\sim M_s^2$) starts dominating the perpendicular anisotropy energy ($\sim K$). This picture can be further confirmed by calculating the so-called quality factor $Q\equiv K/2\pi M_s^2$ which has a value of $Q_c\sim 0.8$, i.e. close to one, at the critical anisotropy, $K_c$. On the other hand, for $K>K_c$ in the simulations, the resulting equilibrium configuration is that of a single skyrmion (shown in the inset of Fig.~\ref{static_prop})\footnote{A second transition corresponding to the collapse of skyrmion is expected to occur on reaching a critical radius for higher anisotropies as observed for bubbles \citep{malozemoff1979magnetic}. To see that transition in micromagnetic simulations finer grid and higher anisotropy values need to be explored }. As expected, in order to minimize the dipole-dipole interaction energy in the wall, the DDI skyrmion is ``Bloch-like" with skyrmion number $\mathcal{N}=1$. Moreover, increasing anisotropy results in decreasing diameter and wall-width surrounding the skyrmion, supporting the qualitative argument presented above.

\iffalse
We remark here that although the simulations are performed for a DDI skyrmion, turning on a small but finite interfacial DMI is expected to result in same regimes as a function of perpendicular anisotropy. As DMI will dominantly affect only the wall energy and structure, by trying to favor a ``N\'{e}el" skyrmion \cite{Nagaosa2013}. It is thus expected that the qualitative feature of decrease in domain wall area with increasing anisotropy and the occurrence of instability of perpendicular magnetization should also occur for a range of non-zero DMI values. However, effect of large DMI on the phase diagram and skyrmion structure, presented in Fig.~\ref{static_prop}, could be an interesting problem to study in the future.
\fi

\section{Electric-field effect: dynamics}
In this section we show how the modification of static properties of the skyrmion results in the electric-field control of current-induced skyrmion motion. Corresponding to the two regimes, defined for modification of static properties, there exist two qualitatively different regimes for the dynamic control.(i) When a uniform electric field with a magnitude below a critical value is applied, such that the skyrmion remains stable, the change in $D_s$ and $\Delta_w$ results in change in the magnitude and the direction of skyrmion motion. (ii) On the other hand, defining unstable regions for skyrmions by application of a non-uniform electric-field above the critical value, results in constraining skyrmion motion along desired paths (which we refer to as the ``guiding regime" below). To gain more insight into this connection between electric-field-induced static and dynamic control, we begin with an analytical model of current-induced skyrmion motion based on Thiele's collective coordinate approach \cite{Thiele}.

\begin{figure}[h]
\centering
\includegraphics[width=0.5\textwidth]{velocity_angle_fig3_new.pdf}
\caption{Velocity modulation for uniform electric-field: the schematic in the bottom shows the steady-state of skyrmion moving with velocity ${\bf v}$ and the corresponding forces acting on it. ${\bf F^s}$ represents current-induced spin-orbit force, while $\mathcal{G}{\bf v}$ and $\Gamma {\bf v}$ represent the Lorentz and damping force, respectively. Open square and triangle markers represent speed and the angle $\psi$ (between current and {\bf v} as shown in the schematic) as obtained from analytical model. The corresponding speed and angle from micromagnetic simulations are represented by the closed square and triangle markers.  }
\label{vel_comp}
\end{figure}

\textit{Analytical model}|
In the collective coordinate approach, the relevant degrees of freedom, describing the equation of motion of a magnetic-texture, are given by the so- called soft modes \cite{Bazaliy2008}. The most relevant soft modes for a skyrmion in an infinite film are its rigid translations in the film plane. Consequently, the collective coordinates included for describing the motion of a skyrmion are $(X,Y)$, which label the position of the skyrmion's center along the $x$ and $y$ axis, respectively. Within this approximation, LLG Eq.~\ref{LLG2} can be reduced to the following equation of motion \cite{Thiele,*Bazaliy2008,*Sampaio2013}:
\begin{equation}
{\bf G \times v}- \Gamma {\bf v}+{\bf F^s}-{\bf F^u}=0,
\label{EOM2}
\end{equation}
where ${\bf v}\equiv(\dot{X},\dot{Y})$ is the velocity vector, while ${\bf G}\equiv (0,0,\mathcal{G})$ with $\mathcal{G}=\int {\bf m} \cdot(\partial_x {\bf m} \times \partial_y{\bf m})$. Inclusion of other modes, such as wall fluctuations, results in deviations from the rigid motion approximation and endows Eq.~\ref{EOM2} with a ``mass term" \cite{makhfudz2012inertia}, which is not the focus of the current study. The first term describes the ``Lorentz force" \footnote{strictly speaking the dimension of each term in Eq.~\ref{EOM2} is that of a velocity but for the ease of discussion they are referred here as forces}due to the skyrmion's non-trivial topology induced fictitious magnetic field \cite{volovik1987linear}. Furthermore, the integrand in $\mathcal{G}$ is the local solid angle, making $\mathcal{G}$ independent of the exact magnetization texture and  simply proportional to the skyrmion number, i.e. $\mathcal{G}=4\pi \mathcal{N}$. The second and third terms originate from the Gilbert damping and current-induced spin-orbit field term in LLG Eq.~\ref{LLG2}, respectively, with $\Gamma=\alpha \int \partial_{x} {\bf m} \cdot \partial_{x}{\bf m} $ and $F_i^s=\gamma \eta J\int \partial_i{\bf m}\cdot({\bf m \times y})$, where $i$ labels the cartesian coordinates. Finally, the fourth term represents the force due to variation of the skyrmion's ``potential energy" $U$, i.e. ${\bf F^u}= -{\bf \nabla}{U}$. The skyrmion's potential energy is, in turn, defined as $U(X,Y)\equiv\int \mathcal{F}+\zeta_F Em_z^2/2$, where the integral is performed for the magnetic configuration of a skyrmion with its center located at $(X,Y)$. In contrast to $\mathcal{G}$; $\Gamma$, ${\bf F^s}$ and ${\bf F^u}$ depend on the exact functional form of the magnetization.

In general, the functional form of ${\bf F^u}$ will depend on the interaction of the skyrmion with its ``environment" and will be discussed for the two regimes below, while analytical expressions are obtained for the dissipative and spin-orbit forces using Thiele's ansatz \cite{Thiele70} for a skyrmion's magnetic configuration as $\Gamma=\alpha \pi^2D_s/\Delta_w$ and ${\bf F^s}=(0,\gamma\eta J\pi^2D_s/2)$. Within this Thiele's ansatz, the integrand for $\Gamma$ and ${\bf F^s}$ is assumed to be non-zero near the wall region, where the magnetization profile, parameterized by the polar($\theta$) and azimuthal($\phi$) angles as ${\bf m}\equiv (\sin \theta\cos \phi, \sin \theta\sin \phi, \cos \theta)$, is given by $\cos \theta(r)=\tanh(\pi r/\Delta_w)$. Additionally, in order to compare to micromagnetics, the Bloch-like DDI skyrmion configuration with $\mathcal{N}=1$ is used, i.e. $\phi(\varphi)=\varphi + \pi/2$ with $(r,\varphi)$ representing the two-dimensional film plane in cylindrical coordinates.

\begin{figure*}
\centering
\includegraphics[width=\textwidth]{velocity_guiding_fig4_new3.pdf}
\caption{Skyrmion guiding regime: (a) the bottom schematic shows the steady-state of a skyrmion moving along the boundary between stable and unstable regions (marked by a horizontal broken line) and corresponding forces. The angle between current and the normal to this boundary is represented by $\beta$. In addition to current-induced force, the damping force and the Lorentz force (as also shown in Fig. ~\ref{vel_comp}), there exist a dipolar force between the skyrmion and in-plane magnetization in the unstable region, denoted by ${\bf F^u}$. The skyrmion's speed along the boundary as a function of $\beta$ as obtained from the micromgnetic simulations is shown by the square marker. While the broken curve shows the result from the analytical model, i.e. Eq.~\ref{guiding_eq}, for same current density. The origin of the dipolar force is illustrated in (b), which compares the interaction of a skyrmion with the environment in the presence (top schematic) and the absence (bottom schematic) of an unstable region. The red circular region represents the core of the skyrmion, with the magnetization inside and outside the skyrmion pointing along - and + $z$, respectively, while the lines emanating from the cylinder represent the dipolar field due to the core region. The magnetization in the unstable region for the top schematic points in the plane as shown by the arrows.}
\label{guiding_comp}
\end{figure*}

We begin by looking at the regime when a uniform electric-field, having a magnitude below the critical value required to make the skyrmion unstable, is applied to the infinite film. In this case, the skyrmion's potential energy is independent of its location and hence ${\bf F^u}=0$. Consequently, solving Eq.~\ref{EOM2} for velocity, we obtain:
\begin{equation}
v=\frac {\gamma \eta JD_s}{8\sqrt{1+(\alpha\pi D_s/4\Delta_w)^2}} ;  \psi=\tan^{-1}(\alpha \pi D_s/4\Delta_w),
\label{vel}
\end{equation}
where $v$ is the skyrmion's speed and $\psi$ is the angle between the skyrmion's motion and the current (see inset of Fig.~\ref{vel_comp} for a  schematic). This constitutes one of the main results of the analytical model, relating the skyrmion's static and dynamic properties. The electric-field control of skyrmion's motion in this regime is thus expected to enter via modification of $D_s$ and $\Delta_w$, as discussed in section III, and is shown in Fig.~\ref{vel_comp} for the diameter and domain wall width extracted from static micromagnetic simulations. These analytical results are compared later against the velocities and angles extracted directly from dynamic micromagnetic simulations.

The dependence of $U$ on electric-field suggests another qualitatively different route to control the skyrmion's dynamics via application of non-uniform electric-field and consequently ``engineering" desired forces ${\bf F^u}$. Interestingly in multiferroics, electric-field gradient-induced forces have been theoretically shown to induce Hall-like skyrmion motion\cite{PhysRevB.87.100402}. Here, we propose the scenario where unstable regions [such as the one shown in the inset of Fig.~\ref{guiding_comp}(a)] can be defined for skyrmions, where magnetization deviates from the out-of-plane direction,  due to the application of an electric field above the critical value. In this case, ${\bf F^u}$ becomes non-zero as the skyrmion approaches the boundary between the stable and unstable regions due to dipolar interaction, as explained next. The dipolar fields originating from the ``core" (i.e. the region inside the skyrmion's diameter) point in a direction opposite to the core's magnetization in the region outside the skyrmion's core. Deviation of magnetization from this dipolar field direction in the unstable region will thus result in a higher dipolar energy when compared with skyrmions interacting with the film in the absence of unstable regions [as illustrated in Fig.~\ref{guiding_comp}(b)]. Consequently, as the skyrmion moves closer to the boundary between the stable and unstable regions, the dipolar energy increases and results in ${\bf F^u}$ preventing the skyrmion to enter the unstable region. Due to this additional ${\bf F^u}$ a new steady state is expected. This situation is very similar to the case of a skyrmion driven in nanowires, where in steady state the skyrmion is driven along the nanowire, with the dipolar forces from the boundary of the nanowire balancing the Lorentz force\cite{Sampaio2013}. Thus generically it is expected that, for a range of drive currents, the skyrmion can be guided along the boundary between the stable and unstable regions, as depicted schematically in Fig.~\ref{guiding_comp}. The advantage here, as compared to the nanowire case, is that this boundary is defined by application of the electric-field and hence can be constructed on the fly, providing a controllable method to ``rewire skyrmion current". A general analytical expression for the velocity depends on the details of ${\bf F^u}$, however a simple expression can be derived for the case when the magnetization configuration in the unstable region has translational symmetry along the boundary [such as the one shown in the schematic of Fig.~\ref{guiding_comp}(a)]. This translational symmetry demands that ${\bf F^u}$ is oriented perpendicular to the boundary, whose magnitude is denoted by $F_u$. Solving for a steady state with the skyrmion moving along the boundary, taking the angle between the current and the normal to the boundary to be $\beta$, and balancing the forces along and transverse to the boundary [as depicted in the inset of Fig.~\ref{guiding_comp}(a)], we obtain for the guiding regime:
\begin{equation}
v=\frac{\gamma \eta J \Delta_w}{2\alpha}\cos \beta ; F_u=4\pi v.
\label{guiding_eq}
\end{equation}
We can see from the above expression that by orienting the electric field gate boundary with respect to the current, i.e. changing $\beta$, the skyrmion's speed can be controlled dramatically. The position of the skyrmion with respect to the boundary, on the other hand, is given by the balance of Lorentz and dipolar forces, with the skyrmion pushed closer to the boundary for larger currents.
We will now compare these analytical insights to the micromagnetic simulations and, in particular, prove the existence of the electric-field-controlled skyrmion guiding regime.

\textit{Micromagnetics}|
The micromagnetic simulations were performed for a DDI skyrmion with the same material parameters as used in the case for static simulations. In addition a current-induced spin-orbit torque, with $\eta_d=\hbar J \theta_{s}/2eM_st$ and $\theta_{s}=0.2$ \cite{Liu2012}, was turned on as the driving force for all the simulations presented in this section.\footnote{In general the effective spin-orbit field also includes a contribution of form $\sim I{\bf y}$, which cannot drive domain-walls in perpendicular magnets \cite{emorinm13, *ryunnt13} and is thus not considered here} Here $\hbar$, $e$ and $J$ are the reduced Planck's constant, charge of an electron and current density respectively. Experimentally, this can be achieved, for example, by interfacing the ferromagnet in the ferromagnet/dielectric heterostructure with a heavy metal like Ta, Pt, W etc. \footnote{In practice additional spin-torque-induced driving forces will act on skyrmion due to current flowing through the ferromagnet itself, which are neglected here for simplicity} The dynamics were calculated by integrating Eq.~\ref{LLG2} with a damping parameter $\alpha=0.05$. In Fig.~\ref{vel_comp} we first compare the results for a uniform electric-field with a magnitude below the critical field. These results are obtained for a single skyrmion moving in a film, with periodic boundary conditions along the film plane, and a fixed current density of $J=10^8$~A/cm$^2$, while simultaneously varying the anisotropy throughout the film in the stable range (as obtained in the static simulations, i.e. for $K=[4.25-5.5]\times 10^6$~erg/cm$^3$ in Fig.\ref{static_prop}). As can be seen, both the speed and the angle of the skyrmion with respect to the current direction are modulated by application of the electric-field. Moreover for the range of electric-field magnitudes studied here, the trend predicted by the analytical model fits the obtained $v$ and $\psi$ well, both qualitatively and quantitatively, substantiating the analytical picture presented above. For the material parameters used, the electric-field modulation shown in this regime is, however, relatively weak. For a much stronger control of skyrmion dynamics, we next turn towards the other regime, i.e application of a non-uniform electric-field.

To demonstrate the skyrmion guiding regime by defining unstable regions for skyrmions, micromagnetic simulations were performed with the value of $K=4.25 (2)\times 10^6$~erg/cm$^3$ in the stable(unstable) regions marked in Fig.~\ref{guiding}. The dynamics was then simulated for a skyrmion driven by current, with the initial state of a single skyrmion in the stable region. In Fig.~\ref{guiding} we show various snapshots of the results of these simulations. First note that, as was discussed in the section III, the magnetization in the unstable region goes to an in-plane state. In the initial stage of the simulation, i.e. when the skyrmion is relatively far from the the unstable region [Fig ~\ref{guiding}(b)], the skyrmion behaves very similar to ${\bf F^u}=0$ case moving at an angle with respect to the current. However, as the skyrmion approaches the boundary between the stable and unstable region [Fig.~\ref{guiding}(c)] a non-zero ${\bf F^u}$ deflects the skyrmion, preventing it from entering the unstable region. After $t\sim 40$ns a new steady state is reached with the skyrmion moving along the boundary between the stable and unstable region [Fig.~\ref{guiding}(d)] and hence proving the existence of the guiding regime. The robustness of this steady state was checked by varying the magnitude of drive current density. For this example, the skyrmion is still driven along the boundary for current density below $J\sim 5 \times 10^8$~A/cm$^2$. As the drive force increases, with increasing current density, the skyrmion is pushed closer to the boundary according to Eq.~\ref{guiding_eq}. However, above $J\sim 5 \times 10^8$~A/cm$^2$ the drive force overcomes ${\bf F^u}$, resulting in the skyrmion entering the unstable region where it is annihilated. Motivated by applications, we next discuss how this regime of skyrmion guiding could provide new opportunities for constructing possible spintronic devices.

\begin{figure}[h]
\centering
\includegraphics[width=0.5\textwidth]{guiding_fig4_new.pdf}
\caption{Micromagnetic simulations showing the guiding by electric field: (a) Initial state showing a stable skyrmion with $K=4.25\times 10^6$~erg/cm$^3$ in the region above the horizontal dashed line and in-plane magnetization below it, where $K=2\times 10^6$~erg/cm$^3$. A current, with density $J$, and making an angle $\beta$ with the normal to the boundary between stable and unstable regions, provides the driving force for the skyrmion. The inset shows the color code for out of plane magnetization, while the in-plane components are shown by arrows. The snapshot of simulation after (b) 5 ns, (c) 10 ns and (d) 20 ns, are shown with the arrows alongside the skyrmion representing the instantaneous direction of the skyrmion's motion.}
\label{guiding}
\end{figure}

\section{Skyrmionics beyond race-tracks}
Nanosized skyrmions can be used as non-volatile information carriers in a spintronic device owing to their stability against thermal fluctuations. The information stored in the skyrmion can, in turn, be read both optically or electrically (by utilizing various magneto-resistance effects such as topological Hall effect \cite{PhysRevLett.102.186601}, tunneling- \cite{jullierePLA75} or giant- \cite{PhysRevLett.61.2472, *PhysRevB.39.4828} magnetoresistance). One such proposed example of a spintronic device is a race-track memory, where information stored in a magnetic texture is moved by current to a desired location where it can be read or written\cite{Parkin11042008}. With the discovery of current-induced skyrmion motion, skyrmions in a nanowire are considered as a promising alternate to ``conventional" domains in a race-track memory as they show very weak pinning by external impurities requiring orders of magnitude lower critical depinning currents \cite{Jonietz2010}. The new possibility of controlling ``skyrmion current" by the electrical-field presented here is thus expected to open up novel avenues of information processing with skyrmions. We demonstrate this by specifically showing via micromagnetic simulations that electric-field gates can be used to turn ``skyrmion currents" off, i.e. providing a transistor-like operation, and deflect information carried by skyrmions in specific parts of the spintronic circuit, i.e. a multiplexer-like operation.

\begin{figure}[h]
\centering
\includegraphics[width=0.5\textwidth]{transistor_3d_new2.pdf}
\caption{Micromagnetic simulations showing the transistor-like function: top schematic shows the initial state with a skyrmion located on the right end of the nanowire, along with a current pulse of 10 ns passed through the heavy metal underlayer. An external electric-field can be applied locally via a voltage over a gate region indicated in the figure. The resulting location of the skyrmion at the end of the pulse when the gate is in OFF (bottom left) and ON (bottom right) state.}
\label{transistor}
\end{figure}

To demonstrate the transistor-like operation, a nanowire geometry is adopted in the simulations with width of the nanowires set at 200 nm. The anisotropy strength was $K=4.25\times 10^6$~erg/cm$^3$ throughout the simulations everywhere in the nanowire except in a region of width $50$ nm defined as the gate. To simulate the effect of electric-field applied on the gated region, the anisotropy value was dropped to $K=2\times 10^6$~erg/cm$^3$ when the gate is in the ``ON" state and kept at $K=4.25\times 10^6$~erg/cm$^3$ in the ``OFF" state. The rest of the parameters are same as for the dynamical simulations presented above. The result of the application of a drive current pulse along the $x$ axis of duration $t_p=10$~ns is shown in Fig.~\ref{transistor}. When the gate is in the OFF state, the skyrmion is driven past the gate region along the nanowire (Fig.~\ref{transistor} bottom left). On the other hand, when the same current pulse is applied in the presence of a gate voltage, the skyrmion is blocked by the gate (Fig.~\ref{transistor} bottom right), due to the repulsive dipolar forces from the unstable gated region, thus exhibiting a transistor-like function. This situation is the special case of the guiding regime, i.e. Eq.~\ref{guiding_eq}, with $\beta =90$.

\begin{figure}[h]
\centering
\includegraphics[width=0.5\textwidth]{multiplexer_3d_new2.pdf}
\caption{Micromagnetic simulations showing the multiplexer-like function: top schematic shows the initial state for two magnetic nanowires coming together at the ``wing-shaped" junction with a skyrmion located at the right end of the upper arm. A local external field can be applied at the shown gate region. The result of the simulation at the end of a current pulse of 10ns passed through the heavy metal underlayer when the gate is OFF (bottom left schematic) and ON (bottom right schematic).  }
\label{multiplex}
\end{figure}

Next we simulate a ``wing-shaped" nanowire junction, with two nanowires, each of width 200 nm, meeting at an angle representing two different arms of a spintronic circuit. A gate in this case is defined on one of the arms as shown in Fig.~\ref{multiplex}, which also shows snapshots of the simulations. When the gate is OFF, a current pulse along the $x$ axis in this case drives the skyrmion to the lower arm (Fig.~\ref{multiplex} bottom left). This motion is similar to a skyrmion moving at an angle with the current due to the Lorentz force, as seen for a skyrmion moving in an infinite film. However, when the gate voltage is turned on, the skyrmion driven by the same current pulse is deflected off the gate region into the upper arm (Fig.~\ref{multiplex} bottom right). Such structures can thus be used to rewire the skyrmion current into specific parts of the circuit.

\section{Summary}

It is shown that an electric-field provides an additional degree of freedom for effective control of current-driven skyrmion motion. By using a symmetry-based phenomenology we find the general form of spin-orbit-induced electric-field coupling for thin films with broken inversion symmetry about the film plane. In general, this coupling can be classified as dissipative, i.e. not derivable from a free energy,  and conservative, i.e. terms which can be understood as electric-field- induced modification of the free energy. The conservative terms can further be identified as electric-field dependent perpendicular anisotropy (when electric field does not couple to gradients of magnetization) and electric-field dependent exchange and Dzyaloshinskii-Moriya interaction (when electric-field couples to gradient in magnetization). Motivated by applications and available experimental data, we  specifically studied effects of the electric-field dependent perpendicular ansisotropy in thin films, which also harbor a nanosized skyrmion state stabilized by dipolar interaction.  We find that there exist two regimes for controlling the static and hence the dynamical properties of skyrmions: (a) below a critical value, such that the corresponding perpendicular ansitoropy is still strong enough to overcome the out-of-plane dipolar interaction, skyrmions are a stable configuration showing a decrease in diameter and domain wall width surrounding the skyrmion with increasing anisotropy, and (b) above the critical value, the skyrmion itself becomes unstable due to formation of multi-domain/ in-plane magnetized state. The decrease in diameter and domain wall width with increasing anisotropy in regime (a) is, in turn, driven by an attempt to reduce the wall energy. This change of static properties modulates both the speed and the angle of skyrmion motion driven by a current induced spin-orbit force. This modulation can be understood within Thiele's analytical model of rigid skyrmion motion, where, the static properties enter the velocity via $D_s$ and $\Delta_w$ dependence of spin-orbit and damping forces acting on the skyrmion. On the other hand, corresponding to regime (b), desired unstable regions can be defined for skyrmions using gate voltages, which are observed in micromagnetic simulations to guide skyrmions along the boundary between stable and unstable regions.This regime of skyrmion guiding is established by appearance of additional forces due to variation of skyrmion's potential energy, caused by the dipolar interactions, as the skyrmion approaches the unstable region. Using this ability to electrically design potential energy landscapes, we demonstrate transistor-like and multiplexer-like spintronic devices controlling skyrmion current by defining electric-field  gates. The proposed electric-field control is thus expected to extend the reach of \textit{skyrmionics} into logic and computing devices.

\begin{acknowledgements}
This work was partially supported by the National Science Foundation Nanosystems Engineering Research Center for Translational Applications of Nanoscale Multiferroic Systems (TANMS), and in part by the FAME Center, one of six centers of the Semiconductor Technology Advanced Research network (STARnet), a Semiconductor Research Corporation (SRC) program sponsored by the Microelectronics advanced Research Corporation (MARCO) and the Defense Advanced Research Projects Agency (DARPA). P.U. also acknowledges partial support from the Spins and Heat in Nanoscale Electronic Systems (SHINES), an Energy Frontier Research Center funded by the U.S. Department of Energy (DOE), Office of Science, Basic Energy Sciences (BES), under Award \# DE-SC0012670. We would like to thank Yaroslav Tserkovnyak, Greg Carman, Axel Hoffman, Wanjun Jiang, and Kin Wong for useful discussions.
\end{acknowledgements}