# An averaging formula for Nielsen numbers of affine $n$ -valued maps on
infra-nilmanifolds

Karel Dekimpe and Lore De Weerdt  KU Leuven Campus Kulak Kortrijk, 8500
Kortrijk, Belgium<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

In [8, 9], the authors developed a nice formula to compute the Nielsen number
of a self-map on an infra-nilmanifold. For the case of nilmanifolds this
formula was extended to $n$-valued maps in [4]. In this paper, we extend these
results further and establish the averaging formula to compute the Nielsen
number of any $n$-valued affine map on an infra-nilmanifold.

Research supported by Methusalem grant METH/21/03 – long term structural
funding of the Flemish Government.

## Introduction

Let $M$ be a closed manifold (or more generally a compact polyhedron) and let
$f:M\to M$ be a self-map of $M$. In Nielsen-Reidemeister fixed point theory
one attaches to each such map $f$ a number $N(f)$, the Nielsen number of $f$,
which is a (sharp) lower bound for the number of fixed points of any map $g$
which is homotopic to $f$. In this paper we are concerned with infra-
nilmanifolds. It is known that any self-map on an infra-nilmanifold is
homotopic to a so-called affine map ([10]). These maps are rather algebraic in
nature and one has developed an averaging formula for computing their Nielsen
number ([8, 9]). Since the Nielsen number of a map is invariant under a
homotopy, this formula allows us to compute the Nielsen number of any self-map
on an infra-nilmanifold. For $n$-valued maps the situation is more
complicated. It is no longer true that any $n$-valued map on an infra-
nilmanifold is homotopic to an affine $n$-valued map ([6]), but nevertheless,
these affine $n$-valued maps still form a large and interesting class of
$n$-valued maps on infra-nilmanifolds. In this paper, we obtain a natural
generalisation of the formula from [9] for computing the Nielsen number of any
affine $n$-valued map on an infra-nilmanifold.

In the first section we recall the basic Nielsen theory for $n$-valued maps
and describe a general averaging formula (1.1) for computing the Nielsen
number of an $n$-valued map. In the second section, we recall the necessary
concepts concerning infra-nilmanifolds and affine $n$-valued maps. In the
third section we establish a decomposition of the fixed point set of an
$n$-valued map on an infra-nilmanifold, which allows us to rewrite the general
averaging formula into a more algebraic one (3.1). In the fourth section we
further examine this formula in the case of affine $n$-valued maps, to finally
arrive at the main result of this paper (Theorem 4.9), which is an averaging
formula generalising in a natural way the formula from [9].

##  1\. Nielsen theory of $n$-valued maps

Let $X$ be a connected compact manifold with fundamental group $\pi$ and
universal cover $p:\tilde{X}\to X$. We will view $\pi$ as being the group of
covering transformations of $p$.

An _n-valued map_ $f:X\multimap X$ is a continuous (i.e. upper and lower semi-
continuous) set-valued function, sending each point of $X$ to a set of $n$
distinct points in $X$. Equivalently, by the work of Brown and Gonçalves [2],
the map $f$ can be viewed as a continuous single-valued function from $X$ to
the _unordered configuration space_

$D_{n}(X)=\\{\\{x_{1},\ldots,x_{n}\\}\subseteq X\mid x_{i}\neq x_{j}\text{ if
}i\neq j\\},$

i.e. the quotient of the space $F_{n}(X)=\\{(x_{1},\ldots,x_{n})\in X^{n}\mid
x_{i}\neq x_{j}\text{ if }i\neq j\\}$ under the action of the permutation
group $\Sigma_{n}$. The fixed point set of an $n$-valued map $f$ is
$\mathrm{Fix}(f)=\\{x\in X\mid x\in f(x)\\}$.

In what follows we recall some of the results of Brown et al. [1], where the
study of fixed points of $f$ was done by considering fixed points of _lifts_
of $f$ to the _orbit configuration space_

$F_{n}(\tilde{X},\pi)=\\{(\tilde{x}_{1},\ldots,\tilde{x}_{n})\in\tilde{X}^{n}\mid
p(\tilde{x}_{i})\neq p(\tilde{x}_{j})\text{ if }i\neq j\\},$

which is a covering space of $D_{n}(X)$ with covering map

$p^{n}:F_{n}(\tilde{X},\pi)\to
D_{n}(X):(\tilde{x}_{1},\ldots,\tilde{x}_{n})\mapsto\\{p(\tilde{x}_{1}),\ldots,p(\tilde{x}_{n})\\}.$

The corresponding covering group is $\pi^{n}\rtimes\Sigma_{n}$, which acts on
$F_{n}(\tilde{X},\pi)$ by

$(\gamma_{1},\ldots,\gamma_{n};\sigma)(\tilde{x}_{1},\ldots,\tilde{x}_{n})=(\gamma_{1}\tilde{x}_{\sigma^{-1}(1)},\ldots,\gamma_{n}\tilde{x}_{\sigma^{-1}(n)}).$

A lift of $f$ can then be defined as a map $\tilde{f}:\tilde{X}\to
F_{n}(\tilde{X},\pi)$ such that

${\tilde{X}}$${F_{n}(\tilde{X},\pi)}$${X}$${D_{n}(X)}$$\scriptstyle{\tilde{f}}$$\scriptstyle{p}$$\scriptstyle{p^{n}}$$\scriptstyle{f}$

commutes. As $F_{n}(\tilde{X},\pi)$ is a subspace of $\tilde{X}^{n}$, such a
lift $\tilde{f}:\tilde{X}\to F_{n}(\tilde{X},\pi)$ splits into $n$ maps
$\tilde{f}_{1},\ldots,\tilde{f}_{n}:\tilde{X}\to\tilde{X}$, called the _lift-
factors_ of $\tilde{f}$.

A lift $\tilde{f}=(\tilde{f}_{1},\ldots,\tilde{f}_{n})$ induces a morphism
$(\phi_{1},\ldots,\phi_{n};\sigma):\pi\to\pi^{n}\rtimes\Sigma_{n}$ of the
covering groups so that for all $\gamma\in\pi$,

$(\tilde{f}_{1}\gamma,\ldots,\tilde{f}_{n}\gamma)=(\phi_{1}(\gamma)\tilde{f}_{\sigma_{\gamma}^{-1}(1)},\ldots,\phi_{n}(\gamma)\tilde{f}_{\sigma_{\gamma}^{-1}(n)}).$

Using this morphism, one can first subdivide $\\{1,\ldots,n\\}$ into _$\sigma$
-classes_, the equivalence classes for the relation given by

$i\sim
j\enskip\Leftrightarrow\enskip\exists\gamma\in\pi:\sigma_{\gamma}(i)=j.$

For all $i$, denote by $S_{i}=\\{\gamma\in\pi\mid\sigma_{\gamma}(i)=i\\}$ the
stabilizer of $i$ for this relation, which is a finite index subgroup of
$\pi$. The restrictions of the maps $\phi_{i}$ to $S_{i}$ are group morphisms,
using which one can define an equivalence relation on $\pi$ by

$\alpha\sim\beta\enskip\Leftrightarrow\enskip\exists\gamma\in
S_{i}:\alpha=\gamma\beta\phi_{i}(\gamma)^{-1}.$

The set of equivalence classes for this relation is denoted
$\mathcal{R}[\phi_{i}]$, and its number of elements is the _Reidemeister
number_ $R(\phi_{i})$.

######  Remark 1.1.

In general, given two group morphisms $\varphi,\psi:\Pi_{1}\to\Pi_{2}$, one
can consider the equivalence relation on $\Pi_{2}$ given by

$\alpha\sim\beta\enskip\Leftrightarrow\enskip\exists\gamma\in\Pi_{1}:\alpha=\psi(\gamma)\beta\varphi(\gamma)^{-1}.$

The equivalence classes are called the _Reidemeister coincidence classes_ of
$\varphi$ and $\psi$, and denoted $\mathcal{R}[\varphi,\psi]$. In case
$\Pi_{1}$ is a subgroup of $\Pi_{2}$ and $\psi$ is the inclusion
$\iota:\Pi_{1}\to\Pi_{2}$, we abbreviate
$\mathcal{R}[\varphi,\iota]=\mathcal{R}[\varphi]$.

The $\sigma$-classes and Reidemeister classes of $\phi_{i}$ partition the
fixed point set of $f$ into a disjoint union of _fixed point classes_ : if
$i_{1},\ldots,i_{r}$ are representatives of the $\sigma$-classes, then

$\mathrm{Fix}(f)=\bigsqcup_{\ell=1}^{r}\bigsqcup_{[\alpha]\in\mathcal{R}[\phi_{i_{\ell}}]}p(\mathrm{Fix}(\alpha\tilde{f}_{i_{\ell}})).$

To each fixed point class one can associate an _index_ , and the fixed point
classes with non-zero index are called _essential_. The number of essential
fixed point classes is the _Nielsen number_ of $f$, which is a lower bound for
the number of fixed points among all maps homotopic to $f$:

$N(f)\leq\text{min}\\{\\#\mathrm{Fix}(g)\mid g\sim f\\}.$

By the above, the Nielsen number can be written as

$N(f)=\sum_{\ell=1}^{r}\sum_{[\alpha]\in\mathcal{R}[\phi_{i_{\ell}}]}\varepsilon_{\alpha,i_{\ell}}$

where

$\varepsilon_{\alpha,i}=\left\\{\begin{array}[]{ll}1&\text{if
$p(\mathrm{Fix}(\alpha\tilde{f}_{i}))$ is an essential fixed point class of
$f$,}\\\ 0&\text{otherwise.}\end{array}\right.$

Since the representatives for the $\sigma$-classes were chosen arbitrarily,
and choosing another representative $i_{\ell}$ for some $\ell$ must give the
same result for $N(f)$, the number

$\sum_{[\alpha]\in\mathcal{R}[\phi_{i_{\ell}}]}\varepsilon_{\alpha,i_{\ell}}$

does not depend on the chosen representative $i_{\ell}$. Therefore the formula
above can also be written as

(1.1)
$N(f)=\sum_{i=1}^{n}\frac{1}{[\pi:S_{i}]}\sum_{[\alpha]\in\mathcal{R}[\phi_{i}]}\varepsilon_{\alpha,i}.$

##  2\. Infra-nilmanifolds and affine maps

The maps we consider in this paper are _affine_ $n$-valued maps on _infra-
nilmanifolds_. An infra-nilmanifold, as defined e.g. in [5], is the quotient
of a connected and simply connected nilpotent Lie group $G$ under the action
of an almost-Bieberbach group $\pi\subseteq G\rtimes\mathrm{Aut}(G)$, i.e. a
torsion free cocompact discrete subgroup of $G\rtimes C$, with $C$ a maximal
compact subgroup of $\mathrm{Aut}(G)$. Such an almost-Bieberbach group acts
properly discontinuously on $G$ and hence $\pi$ is (isomorphic to) the
fundamental group of the infra-nilmanifold $\pi\backslash G$. As before, we
will view $\pi$ as the covering group of the universal covering
$G\to\pi\backslash G$.

In the special case where this group $\pi$ is entirely contained in $G$, the
quotient space is called a nilmanifold. Every infra-nilmanifold $\pi\backslash
G$ is finitely covered by a nilmanifold $N\backslash G$: it follows from the
generalised Bieberbach Theorems that $\pi\cap G$ is of finite index in $\pi$,
so one can take $N=\pi\cap G$ or any other subgroup $N\subseteq\pi\cap G$
which is of finite index in $\pi$. Such a group $N$ is a finitely generated
torsion free nilpotent group and is a lattice of the Lie group $G$.

Nilmanifolds have been studied in detail by Mal’cev; see [11]. We briefly
recall some of his results.

For a nilpotent group $G$ of class $c$, we denote the lower central series by

$G=\gamma_{1}(G)\geq\ldots\geq\gamma_{c}(G)\geq\gamma_{c+1}(G)=1.$

For a finitely generated torsion free nilpotent group $N$ of class $c$ we
consider another central series whose terms are the _isolators_ of the lower
central series,

$N_{i}=\sqrt[N]{\gamma_{i}(N)}=\\{g\in N\mid\exists
k>0:g^{k}\in\gamma_{i}(N)\\}.$

This series has the useful property that for all $i$, the quotient
$N_{i}/N_{i+1}$ is free abelian of finite rank, say
$N_{i}/N_{i+1}\cong\mathbb{Z}^{k_{i}}$. Moreover, for these numbers $k_{i}$,
the factors of the lower central series of $G$ satisfy
$\gamma_{i}(G)/\gamma_{i+1}(G)\cong\mathbb{R}^{k_{i}}$. Morphisms of (lattices
in) $G$ induce morphisms on these quotients, which can be represented by
$k_{i}\times k_{i}$ real (or integer) matrices.

If $N,N^{\prime}$ are lattices in $G$, any morphism $\phi:N\to N^{\prime}$
extends uniquely to a Lie group morphism $G\to G$. The latter induces a
morphism on the Lie algebra $\mathfrak{g}$ of $G$. From now on we will refer
to this as the Lie algebra morphism induced by $\phi:N\to N^{\prime}$, and
write $\phi_{*}:\mathfrak{g}\to\mathfrak{g}$, without explicitly mentioning
the extension of $\phi$ to $G$.

Another useful property of connected and simply connected nilpotent Lie groups
$G$ is that the exponential map $\exp:\mathfrak{g}\to G$ is a diffeomorphism
[3, Theorem 1.2.1]. In particular, it is invertible, and we denote the inverse
map by $\log:G\to\mathfrak{g}$. This allows us to define the continuous
function

$G\times\mathbb{R}\to G:(g,t)\mapsto g^{t}=\exp(t\log(g))$

which we will use later on.

On an infra-nilmanifold we can define the notion of an _affine_ $n$-valued
map. A map $f:\pi\backslash G\to D_{n}(\pi\backslash G)$ is affine if it lifts
to a map of the form

$\tilde{f}:G\to
F_{n}(G,\pi):x\mapsto(g_{1}\varphi_{1}(x),\ldots,g_{n}\varphi_{n}(x))$

with $g_{1},\ldots,g_{n}\in G$ and
$\varphi_{1},\ldots,\varphi_{n}\in\mathrm{End}(G)$. We remark that this
condition is independent of the chosen lift $\tilde{f}$. The corresponding
maps $\phi_{i}$ and $\sigma$ from section 1 satisfy

(2.1) $g_{i}\varphi_{i}(\gamma
x)=\phi_{i}(\gamma)g_{\sigma_{\gamma}^{-1}(i)}\varphi_{\sigma_{\gamma}^{-1}(i)}(x)$

for all $\gamma\in\pi$, $x\in G$ and $i\in\\{1,\ldots,n\\}$.

Nielsen numbers of affine $n$-valued maps on nilmanifolds have been studied in
[4], where the following formula is proven:

######  Theorem 2.1 ([4, Theorem 6.13]).

Let $N\backslash G$ be a nilmanifold. The Nielsen number of an affine map
$f:N\backslash G\to D_{n}(N\backslash G)$ with lift $\tilde{f}:G\to
F_{n}(G,N):x\mapsto(g_{1}\varphi_{1}(x),\ldots,g_{n}\varphi_{n}(x))$ is given
by

$N(f)=\sum_{i=1}^{n}|\det(I-(\varphi_{i})_{*})|.$

The goal of this paper is to generalise this formula to infra-nilmanifolds. In
the single-valued case, this extension from nilmanifolds to infra-nilmanifolds
was done by Kim, Lee and Lee in [8]. They proved that any map $f$ on an infra-
nilmanifold $\pi\backslash G$ can be lifted to a nilmanifold $N\backslash G$
that finitely covers $\pi\backslash G$, and they expressed the Nielsen number
of $f$ as the average of the Nielsen numbers of these lifts.

We cannot follow the same approach in the $n$-valued case, since $n$-valued
maps in general no longer admit lifts to a nilmanifold. However, we can
decompose the formula for the Nielsen number in a similar way as in [8], and
then plug in the knowledge about affine maps on nilmanifolds established in
[4] to obtain the desired averaging formula without involving actual lifts to
the nilmanifold.

##  3\. Decomposition of the fixed point set

Let $\pi\backslash G$ be an infra-nilmanifold, finitely covered by a
nilmanifold $N\backslash G$. For a general map $f:\pi\backslash G\to
D_{n}(\pi\backslash G)$, we will decompose the sum (1.1) into a sum over
Reidemeister classes in $N$ and in $\pi/N$, generalising the approach in [8].

For all $i$, consider the group $S^{\prime}_{i}$ generated by
$\\{\gamma^{[\pi:N]}\mid\gamma\in S_{i}\\}$. This is a normal subgroup of
$S_{i}$, and the quotient group $S_{i}/S^{\prime}_{i}$ is periodic, since the
order of every element divides $[\pi:N]$. Also note that $\pi$ (and therefore
also $S_{i}/S^{\prime}_{i}$) is polycyclic-by-finite, since its finite index
normal subgroup $N$ is finitely generated and nilpotent. Since periodic
polycyclic-by-finite groups are automatically finite, it follows that
$[S_{i}:S^{\prime}_{i}]$ is finite. Consequently, also

$[N:S^{\prime}_{i}]=\frac{[\pi:S_{i}][S_{i}:S^{\prime}_{i}]}{[\pi:N]}$

is finite. Thus, $S_{i}^{\prime}$ is a finite index normal subgroup of $S_{i}$
and a finite index subgroup of $N$.

Furthermore, note that the image of $S^{\prime}_{i}$ under any morphism
$S_{i}\to\pi$ is contained in $N$. Hence the inclusion map $\iota:S_{i}\to\pi$
and the morphism $\phi_{i}:S_{i}\to\pi$ induce morphisms

$\displaystyle\iota^{\prime}:S_{i}^{\prime}\to N$
$\displaystyle:\gamma\mapsto\gamma$
$\displaystyle\bar{\iota}:S_{i}/S_{i}^{\prime}\to\pi/N$ $\displaystyle:\gamma
S_{i}^{\prime}\mapsto\gamma N$
$\displaystyle\phi^{\prime}_{i}:S_{i}^{\prime}\to N$
$\displaystyle:\gamma\mapsto\phi_{i}(\gamma)$
$\displaystyle\bar{\phi}_{i}:S_{i}/S_{i}^{\prime}\to\pi/N$
$\displaystyle:\gamma S_{i}^{\prime}\mapsto\phi_{i}(\gamma)N.$

We will decompose the set of Reidemeister classes of $\phi_{i}$ using
Reidemeister classes associated to $\bar{\phi}_{i}$ and $\phi_{i}^{\prime}$.

First, note that

$\mathcal{R}[\phi_{i}]=\bigcup_{\bar{\alpha}\in\pi/N}\,\bigcup_{g\in
N}\,[g\alpha].$

If $[g\alpha]=[g^{\prime}\alpha^{\prime}]$ in $\mathcal{R}[\phi_{i}]$, then
certainly $[\bar{\alpha}]=[\bar{\alpha}^{\prime}]$ in
$\mathcal{R}[\bar{\phi}_{i},\bar{\iota}]$, i.e.

$\exists\bar{\gamma}\in
S_{i}/S^{\prime}_{i}:\bar{\alpha}=\bar{\iota}(\bar{\gamma})\bar{\alpha}^{\prime}\bar{\phi}_{i}(\bar{\gamma})^{-1}.$

Conversely, note that if $[\bar{\alpha}]=[\bar{\alpha}^{\prime}]$ in
$\mathcal{R}[\bar{\phi}_{i},\bar{\iota}]$, then there is a $g\in N$ so that
$[g\alpha]=[\alpha^{\prime}]$ in $\mathcal{R}[\phi_{i}]$.

For fixed $\alpha$, we have $[g\alpha]=[g^{\prime}\alpha]$ in
$\mathcal{R}[\phi_{i}]$ if and only if $[g]=[g^{\prime}]$ in
$\mathcal{R}[\tau_{\alpha}\phi_{i}]$, with
$\tau_{\alpha}:\pi\to\pi:\beta\mapsto\alpha\beta\alpha^{-1}$; i.e.

$\exists\gamma\in S_{i}:g=\gamma
g^{\prime}\alpha\phi_{i}(\gamma)^{-1}\alpha^{-1}.$

Thus, the above are disjoint unions when taken over these respective
Reidemeister classes:

$\mathcal{R}[\phi_{i}]=\bigsqcup_{[\bar{\alpha}]\in\mathcal{R}[\bar{\phi}_{i},\bar{\iota}]}\bigsqcup_{[g]\in\mathcal{R}[\tau_{\alpha}\phi_{i}]}\,[g\alpha].$

Rather than in $\mathcal{R}[\tau_{\alpha}\phi_{i}]$, we would like to view the
classes $[g]$ with $g\in N$ as elements of
$\mathcal{R}[\tau_{\alpha}\phi^{\prime}_{i}]$, where

$g\sim g^{\prime}\enskip\Leftrightarrow\enskip\exists\gamma\in
S^{\prime}_{i}:g=\gamma
g^{\prime}\alpha\phi^{\prime}_{i}(\gamma)^{-1}\alpha^{-1}.$

Since $S_{i}^{\prime}\subseteq S_{i}$, it is clear that $[g]=[g^{\prime}]$ in
$\mathcal{R}[\tau_{\alpha}\phi^{\prime}_{i}]$ implies $[g]=[g^{\prime}]$ in
$\mathcal{R}[\tau_{\alpha}\phi_{i}]$, but conversely there can be distinct
elements in $\mathcal{R}[\tau_{\alpha}\phi^{\prime}_{i}]$ that are equivalent
in $\mathcal{R}[\tau_{\alpha}\phi_{i}]$. The following lemma allows us to
describe how many different classes in
$\mathcal{R}[\tau_{\alpha}\phi^{\prime}_{i}]$ give rise to the same class in
$\mathcal{R}[\tau_{\alpha}\phi_{i}]$. In this lemma, we use
$\mathrm{coin}(\varphi,\psi)=\\{\gamma\in\Pi_{1}\mid\varphi(\gamma)=\psi(\gamma)\\}$
to denote the group of coincidence points of two morphisms
$\varphi,\psi:\Pi_{1}\to\Pi_{2}$.

######  Lemma 3.1 ([7, Lemma 3.1.4]).

Given a commutative diagram of groups with exact rows

${1}$${\Gamma_{1}}$${\Pi_{1}}$${\Pi_{1}/\Gamma_{1}}$${1}$${1}$${\Gamma_{2}}$${\Pi_{2}}$${\Pi_{2}/\Gamma_{2}}$${1}$$\scriptstyle{\varphi^{\prime}}$$\scriptstyle{\psi^{\prime}}$$\scriptstyle{\varphi}$$\scriptstyle{\psi}$$\scriptstyle{\bar{\varphi}}$$\scriptstyle{\bar{\psi}}$

such that the quotient groups $\Pi_{i}/\Gamma_{i}$ are finite. For all
$\alpha\in\Pi_{2}$ and $g\in\Gamma_{2}$, the number of Reidemeister
coincidence classes
$[g^{\prime}]\in\mathcal{R}[\tau_{\alpha}\varphi^{\prime},\psi^{\prime}]$ such
that $[g]=[g^{\prime}]$ in $\mathcal{R}[\tau_{\alpha}\varphi,\psi]$ is equal
to

$[\mathrm{coin}(\tau_{\bar{\alpha}}\bar{\varphi},\bar{\psi}):\overline{\mathrm{coin}(\tau_{g\alpha}\varphi,\psi)}]$

where $\overline{\mathrm{coin}(\tau_{g\alpha}\varphi,\psi)}$ denotes the image
of $\mathrm{coin}(\tau_{g\alpha}\varphi,\psi)$ in $\Pi_{1}/\Gamma_{1}$.

Applying this to the diagram

${1}$${S^{\prime}_{i}}$${S_{i}}$${S_{i}/S^{\prime}_{i}}$${1}$${1}$${N}$${\pi}$${\pi/N}$${1}$$\scriptstyle{\phi^{\prime}_{i}}$$\scriptstyle{\iota^{\prime}}$$\scriptstyle{\phi_{i}}$$\scriptstyle{\iota}$$\scriptstyle{\bar{\phi}_{i}}$$\scriptstyle{\bar{\iota}}$

learns that for a given $g\in N$, the number of classes
$[g^{\prime}]\in\mathcal{R}[\tau_{\alpha}\phi^{\prime}_{i}]$ such that
$[g]=[g^{\prime}]$ in $\mathcal{R}[\tau_{\alpha}\phi_{i}]$ is equal to

$[\mathrm{coin}(\tau_{\bar{\alpha}}\bar{\phi}_{i},\bar{\iota}):\overline{\mathrm{fix}(\tau_{g\alpha}\phi_{i})}]=\frac{|\mathrm{coin}(\tau_{\bar{\alpha}}\bar{\phi}_{i},\bar{\iota})|}{|\overline{\mathrm{fix}(\tau_{g\alpha}\phi_{i})}|},$

where $\overline{\mathrm{fix}(\tau_{g\alpha}\phi_{i})}$ denotes the image of
$\mathrm{fix}(\tau_{g\alpha}\phi_{i})=\mathrm{coin}(\tau_{g\alpha}\phi_{i},\iota)$
in $S_{i}/S_{i}^{\prime}$. Therefore the sum (1.1) decomposes as

$N(f)=\sum_{i=1}^{n}\frac{1}{[\pi:S_{i}]}\sum_{[\bar{\alpha}]\in\mathcal{R}[\bar{\phi}_{i},\bar{\iota}]}\sum_{[g]\in\mathcal{R}[\tau_{\alpha}\phi^{\prime}_{i}]}\frac{|\overline{\mathrm{fix}(\tau_{g\alpha}\phi_{i})}|}{|\mathrm{coin}(\tau_{\bar{\alpha}}\bar{\phi}_{i},\bar{\iota})|}\,\varepsilon_{g\alpha,i}.$

To further simplify this formula, consider the action of
$S_{i}/S^{\prime}_{i}$ on $\pi/N$ given by

$\bar{\gamma}\cdot\bar{\alpha}=\bar{\iota}(\bar{\gamma})\bar{\alpha}\bar{\phi}_{i}(\bar{\gamma})^{-1}.$

The orbit of an element $\bar{\alpha}$ for this action is its Reidemeister
class $[\bar{\alpha}]\in\mathcal{R}[\bar{\phi}_{i},\bar{\iota}]$. The
stabilizer of $\bar{\alpha}$ is the set

$\\{\bar{\gamma}\in
S_{i}/S^{\prime}_{i}\mid\bar{\iota}(\bar{\gamma})\bar{\alpha}\bar{\phi}_{i}(\bar{\gamma})^{-1}=\bar{\alpha}\\}=\mathrm{coin}(\tau_{\bar{\alpha}}\bar{\phi}_{i},\bar{\iota}).$

Therefore we have

$|[\bar{\alpha}]|\cdot|\mathrm{coin}(\tau_{\bar{\alpha}}\bar{\phi}_{i},\bar{\iota})|=|S_{i}/S^{\prime}_{i}|=[S_{i}:S^{\prime}_{i}].$

This reduces the expression for $N(f)$ to

$\displaystyle N(f)$
$\displaystyle=\sum_{i=1}^{n}\frac{1}{[\pi:S_{i}]}\sum_{\bar{\alpha}\in\pi/N}\frac{1}{|[\bar{\alpha}]|}\sum_{[g]\in\mathcal{R}[\tau_{\alpha}\phi^{\prime}_{i}]}\frac{|\overline{\mathrm{fix}(\tau_{g\alpha}\phi_{i})}|}{|\mathrm{coin}(\tau_{\bar{\alpha}}\bar{\phi}_{i},\bar{\iota})|}\,\varepsilon_{g\alpha,i}$
(3.1)
$\displaystyle=\sum_{i=1}^{n}\frac{1}{[\pi:S^{\prime}_{i}]}\sum_{\bar{\alpha}\in\pi/N}\sum_{[g]\in\mathcal{R}[\tau_{\alpha}\phi^{\prime}_{i}]}|\overline{\mathrm{fix}(\tau_{g\alpha}\phi_{i})}|\,\varepsilon_{g\alpha,i}.$

##  4\. Averaging formula for affine maps

Now we apply this to the special case where $f$ is an affine map with lift
$\tilde{f}:G\to
F_{n}(G,\pi):x\mapsto(g_{1}\varphi_{1}(x),\ldots,g_{n}\varphi_{n}(x))$. In
this case, the formula above can be reduced to an expression purely in terms
of the morphisms $\varphi_{i}$.

Recall that, for a morphism $\phi^{\prime}:S^{\prime}\to N$ between lattices
in a connected and simply connected nilpotent Lie group $G$, we use
$(\phi^{\prime})_{*}:\mathfrak{g}\to\mathfrak{g}$ to denote the Lie algebra
morphism induced by the unique extension of $\phi^{\prime}$ to $G\to G$.

######  Lemma 4.1.

Suppose $\pi\backslash G$ is an infra-nilmanifold finitely covered by a
nilmanifold $N\backslash G$, and $S$ is a finite index subgroup of $\pi$. Let
$S^{\prime}$ be the subgroup generated by $\\{\gamma^{[\pi:N]}\mid\gamma\in
S\\}$. Let $\phi:S\to\pi$ be a morphism and $\phi^{\prime}:S^{\prime}\to N$
its restriction to $S^{\prime}$. If $\det(I-(\phi^{\prime})_{*})\neq 0$, then
$\mathrm{fix}(\phi)=1$.

###### Proof.

We first prove that $\mathrm{fix}(\phi^{\prime})=1$. To this end, let
$\exp:\mathfrak{g}\to G$ denote the exponential map of $G$, and
$\log:G\to\mathfrak{g}$ its inverse.

Suppose $\gamma\in S^{\prime}$ is a fixed point of $\phi^{\prime}$. Then
$X=\log(\gamma)$ is a fixed point of $(\phi^{\prime})_{*}$, i.e.
$(I-(\phi^{\prime})_{*})(X)=0$. Since $\det(I-(\phi^{\prime})_{*})\neq 0$, the
only element $X$ satisfying this equation is $0$. It follows that
$\gamma=\exp(0)=1$.

Now, suppose $\gamma\in S$ is a fixed point of $\phi$, and denote $k=[\pi:N]$.
Then $\phi(\gamma^{k})=\phi(\gamma)^{k}=\gamma^{k}$, so $\gamma^{k}\in
S^{\prime}$ is a fixed point of $\phi^{\prime}$. By the above, we have
$\gamma^{k}=1$. Since $S$ is torsion free, it follows that $\gamma=1$. ∎

We will now show that for an affine map, the number $\varepsilon_{g\alpha,i}$
in (3.1) is independent of $g\in N$, using the results from [4]. We
distinguish two cases. In both cases we will need the following lemma.

######  Lemma 4.2 ([4, Lemma 6.4]).

Let $G$ be a connected and simply connected nilpotent Lie group, and
$\varphi\in\mathrm{End}(G)$. If $\varphi_{*}$ has no eigenvalue $1$, the map
$G\to G:x\mapsto\varphi(x)x^{-1}$ is bijective.

The first case is the following.

######  Notation 4.3.

For $\alpha\in\pi\subseteq G\rtimes\mathrm{Aut}(G)$ we will write
$\alpha=(a_{\alpha},A_{\alpha})$ with $a_{\alpha}\in G$ and
$A_{\alpha}\in\mathrm{Aut}(G)$.

######  Corollary 4.4.

Let $f:\pi\backslash G\to D_{n}(\pi\backslash G)$ be an affine $n$-valued map
with lift $\tilde{f}:x\mapsto(g_{1}\varphi_{1}(x),\ldots,g_{n}\varphi_{n}(x))$
and corresponding numbers $\varepsilon_{g\alpha,i}$. Fix $i$ and
$\alpha\in\pi$. If $\det(I-(A_{\alpha}\varphi_{i})_{*})\neq 0$, then
$\varepsilon_{g\alpha,i}=1$ for all $g\in N$.

###### Proof.

Pick $g\in N$. Note that for all $x\in G$,

$g\alpha\tilde{f}_{i}(x)=g\alpha
g_{i}\varphi_{i}(x)=ga_{\alpha}A_{\alpha}(g_{i})A_{\alpha}\varphi_{i}(x).$

So if we denote $ga_{\alpha}A_{\alpha}(g_{i})=g^{\prime}$, then
$g\alpha\tilde{f}_{i}=g^{\prime}A_{\alpha}\varphi_{i}$.

By Lemma 4.2, the map $G\to G:x\mapsto A_{\alpha}\varphi_{i}(x)x^{-1}$ is a
bijection. Hence there is a unique $x\in G$ such that
$A_{\alpha}\varphi_{i}(x)x^{-1}=(g^{\prime})^{-1}$, i.e. such that
$g^{\prime}A_{\alpha}\varphi_{i}(x)=x$. That is, the map
$g\alpha\tilde{f}_{i}=g^{\prime}A_{\alpha}\varphi_{i}$ has a unique fixed
point. The index of the fixed point class
$p(\mathrm{Fix}(g\alpha\tilde{f}_{i}))$ is then equal to the index of this
unique fixed point of $g^{\prime}A_{\alpha}\varphi_{i}$.

In [4, Lemma 6.10] it is proven that, if $\varphi:G\to G$ is a morphism so
that $G\to G:x\mapsto\varphi(x)x^{-1}$ is a bijection, then for any $h\in G$,
the index of $G\to G:x\mapsto h\varphi(x)$ at its unique fixed point is $\pm
1$. Applying this to $\varphi=A_{\alpha}\varphi_{i}$ and $h=g^{\prime}$ gives
the desired result. ∎

For the second case, we can use the following lemma, which is a special case
of [4, Lemma 6.6]. We give a more polished version of the proof adapted to our
specific needs.

######  Lemma 4.5.

Let $G$ be a connected and simply connected nilpotent Lie group, and
$\varphi\in\mathrm{End}(G)$. If $\varphi_{*}$ has eigenvalue $1$, then for all
$g\in G$ there is a $g_{0}\in G$ such that $g\varphi(x)g_{0}\neq x$ for all
$x\in G$.

###### Proof.

We prove the claim by induction on the nilpotency class $c$ of $G$.

If $c=1$, then $G=\mathbb{R}^{k}$ for some $k$ and $\varphi=\varphi_{*}$ is a
linear map represented by a matrix which has eigenvalue $1$. We can choose a
basis $\\{v_{1},\ldots,v_{k}\\}$ of $\mathbb{R}^{k}$ with respect to which the
matrix of $\varphi$ is of the form

$\begin{bmatrix}1&0&\cdots&0\\\ *&*&\cdots&*\\\ \vdots&\vdots&\ddots&\vdots\\\
*&*&\cdots&*\end{bmatrix}.$

That is, if we write $V=\langle v_{2},\ldots,v_{k}\rangle$, then $\varphi(\mu
v_{1}+v)\equiv\mu v_{1}\;\mathrm{mod}\,V$ for all $\mu\in\mathbb{R}$ and $v\in
V$.

Take $\lambda\in\mathbb{R}$ such that $g\equiv\lambda v_{1}\;\mathrm{mod}\,V$.
We claim that $g_{0}=(1-\lambda)v_{1}$ does the job. Indeed, suppose
$x\in\mathbb{R}^{k}$ satisfies $g+\varphi(x)+g_{0}=x$. If we write $x=\mu
v_{1}+v$ with $v\in V$, this reduces to

$\lambda v_{1}+\mu v_{1}+(1-\lambda)v_{1}=\mu v_{1}\;\mathrm{mod}\,V,$

or equivalentely, $v_{1}\in V$, which is a contradiction.

Now suppose $c>1$ and the result holds for all groups of smaller nilpotency
class. For all $i=1,\ldots,c$, let $M_{i}$ be the matrix of the morphism
induced by $\varphi$ on $\gamma_{i}(G)/\gamma_{i+1}(G)$. We distinguish two
cases: either one of the matrices $M_{1},\ldots,M_{c-1}$ has eigenvalue $1$,
or $M_{c}$ is the only matrix with eigenvalue $1$.

In the first case, we can apply the induction hypothesis to the map
$G/\gamma_{c}(G)\to G/\gamma_{c}(G):\bar{x}\mapsto\overline{\varphi(x)}$ (and
the element $\bar{g}$ for $g$) to obtain a $g_{0}\in G$ such that
$\overline{g\varphi(x)g_{0}}\neq\bar{x}$ in $G/\gamma_{c}(G)$, so in
particular $g\varphi(x)g_{0}\neq x$ in $G$, for all $x\in G$.

In the second case, we can apply the induction hypothesis to the restriction
of $\varphi$ to $\gamma_{c}(G)$ (and the identity element for $g$) to obtain a
$g_{0}\in\gamma_{c}(G)$ such that $\varphi(x)g_{0}\neq x$ for all
$x\in\gamma_{c}(G)$. On the other hand, we can apply Lemma 4.2 to the map
$G/\gamma_{c}(G)\to G/\gamma_{c}(G):\bar{x}\mapsto\overline{\varphi(x)}$,
which has no eigenvalue $1$. It follows that there is a unique $\bar{x}_{0}\in
G/\gamma_{c}(G)$ such that $\overline{x_{0}\varphi(x_{0})^{-1}}=\bar{g}$.
Choose a representative $x_{0}\in G$ for $\bar{x}_{0}$, and take
$z\in\gamma_{c}(G)$ such that $g\varphi(x_{0})=x_{0}z$. We claim that the
element $g_{0}z^{-1}$ does the job. Indeed, suppose $x\in G$ satisfies
$g\varphi(x)g_{0}z^{-1}=x$. By uniqueness of $\bar{x}_{0}$, this element $x$
must be of the form $x_{0}z^{\prime}$ for some $z^{\prime}\in\gamma_{c}(G)$.
Then we have

$\displaystyle g\varphi(x_{0}z^{\prime})g_{0}z^{-1}=x_{0}z^{\prime}$
$\displaystyle\enskip\Leftrightarrow\enskip
g\varphi(x_{0})\varphi(z^{\prime})g_{0}z^{-1}=x_{0}z^{\prime}$
$\displaystyle\enskip\Leftrightarrow\enskip
x_{0}z\varphi(z^{\prime})g_{0}z^{-1}=x_{0}z^{\prime}$
$\displaystyle\enskip\Leftrightarrow\enskip\varphi(z^{\prime})g_{0}=z^{\prime},$

which is impossible for $z^{\prime}\in\gamma_{c}(G)$, by definition of
$g_{0}$. ∎

######  Corollary 4.6.

Let $f:\pi\backslash G\to D_{n}(\pi\backslash G)$ be an affine $n$-valued map
with lift $\tilde{f}:x\mapsto(g_{1}\varphi_{1}(x),\ldots,g_{n}\varphi_{n}(x))$
and corresponding numbers $\varepsilon_{g\alpha,i}$. Fix $i$ and
$\alpha\in\pi$. If $\det(I-(A_{\alpha}\varphi_{i})_{*})=0$, then
$\varepsilon_{g\alpha,i}=0$ for all $g\in N$.

###### Proof.

Pick $g\in N$ and define $g^{\prime}$ as in Corollary 4.4. By Lemma 4.5, there
exits a $g_{0}\in G$ such that $g^{\prime}A_{\alpha}\varphi_{i}(x)g_{0}\neq x$
for all $x\in G$. Then we have a homotopy

$\pi\backslash G\times[0,1]\to D_{n}(\pi\backslash
G):(p(x),t)\mapsto\\{p(\tilde{f}_{1}(x)g_{0}^{t}),\ldots,p(\tilde{f}_{n}(x)g_{0}^{t})\\}.$

Under this homotopy, the fixed point class
$p(\mathrm{Fix}(g\alpha\tilde{f}_{i}))$ of $f$ corresponds to the fixed point
class $p(\mathrm{Fix}(g\alpha\tilde{f}_{i}g_{0}))$. Since
$g\alpha\tilde{f}_{i}g_{0}$ has no fixed points by definition of $g_{0}$, the
index of this fixed point class is $0$. As indices are preserved under
homotopies, the index of $p(\mathrm{Fix}(g\alpha\tilde{f}_{i}))$ is also $0$.
∎

On the other hand, the results in [4] give an expression for the number of
terms in the second sum in (3.1):

######  Lemma 4.7.

For a morphism $\phi^{\prime}:S^{\prime}\to N$, with $N$ finitely generated,
torsion free and nilpotent, and $S^{\prime}$ a finite index subgroup of $N$,
one has

$R(\phi^{\prime})=[N:S^{\prime}]|\det(I-(\phi^{\prime})_{*})|_{\infty},$

where $|a|_{\infty}$ is defined as $|a|$ if $a\neq 0$, and $\infty$ if $a=0$.

###### Proof.

Let $c$ be the nilpotency class of $N$. For $i=1,\ldots,c$, write
$N_{i}=\sqrt[N]{\gamma_{i}(N)}$ and
$S^{\prime}_{i}=\sqrt[S^{\prime}]{\gamma_{i}(S^{\prime})}$. If $M_{i}$ denotes
the matrix of the morphism $S^{\prime}_{i}N_{i+1}/N_{i+1}\to N_{i}/N_{i+1}$
induced by $\phi^{\prime}$, it is proven in [4, Theorem 4.14] that

$R(\phi^{\prime})=[N:S^{\prime}]|\det(I-M)|_{\infty},$

where

$M=\begin{bmatrix}M_{1}&0&\cdots&0\\\ 0&M_{2}&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&M_{c}\end{bmatrix}.$

On the other hand, it is proven in [4, Theorem 5.4] that the matrix of
$(\phi^{\prime})_{*}$ with respect to a well-chosen basis for $\mathfrak{g}$
is of the form

$\begin{bmatrix}M_{1}&0&\cdots&0\\\ *&M_{2}&\cdots&0\\\
\vdots&\vdots&\ddots&\vdots\\\ *&*&\cdots&M_{c}\end{bmatrix}.$

Thus, we can replace $\det(I-M)$ by $\det(I-(\phi^{\prime})_{*})$, which gives
the desired formula. ∎

Lastly, we observe:

######  Lemma 4.8.

Let $f:\pi\backslash G\to D_{n}(\pi\backslash G)$ be an affine $n$-valued map
with lift $\tilde{f}:x\mapsto(g_{1}\varphi_{1}(x),\ldots,g_{n}\varphi_{n}(x))$
and corresponding morphisms $\phi_{i}^{\prime}:S_{i}^{\prime}\to N$. For all
$i$ and $\alpha\in\pi$, for all $g\in N$,

$\det(I-(\tau_{g\alpha}\phi^{\prime}_{i})_{*})=\det(I-(A_{\alpha}\varphi_{i})_{*}).$

###### Proof.

We may choose a basis
$v_{1,1},v_{1,2},\ldots,v_{1,k_{1}},v_{2,1},\ldots,v_{c,k_{c}}$ for
$\mathfrak{g}$ in such a way that the vectors
$v_{i,1},v_{i,2},\ldots,v_{i,k_{i}},v_{i+1,1},\ldots,v_{c,k_{c}}$ form a basis
of $\gamma_{i}(\mathfrak{g})$, the $i$-th term in the lower central series of
the Lie algebra $\mathfrak{g}$. With respect to this basis, all morphisms
$\mathfrak{g}\to\mathfrak{g}$ are represented by blocked lower triangular
matrices (with blocks of size $k_{i}\times k_{i}$ on the diagonal).

Now note that for the morphisms
$\tau_{g\alpha},\,\phi_{i}^{\prime}:S_{i}^{\prime}\to N$, and therefore also
for their extensions $G\to G$,

$\tau_{g\alpha}=c_{ga_{\alpha}}A_{\alpha}\qquad\text{and}\qquad\phi_{i}^{\prime}=c_{g_{i}}\varphi_{i}$

where $c_{g}:G\to G$ denotes conjugation with $g\in G$. (The equality for
$\phi_{i}$ follows by evaluating (2.1) at $x=1$ and $\gamma\in
S_{i}^{\prime}$.)

For all $g\in G$, the map $c_{g}:G\to G$ induces the identity on
$\gamma_{i}(G)/\gamma_{i+1}(G)$, so the maps $(c_{g})_{\ast}$ induce the
identity on $\gamma_{i}(\mathfrak{g})/\gamma_{i+1}(\mathfrak{g})$ and the
matrix representation of $(c_{g})_{\ast}$ has identity blocks on the diagonal.
It follows that the matrices of $(\tau_{g\alpha})_{*}$ and
$(\phi^{\prime}_{i})_{*}$ have the same blocks on the diagonal as those of
$(A_{\alpha})_{*}$ and $(\varphi_{i})_{*}$, respectively; therefore

$\det(I-(\tau_{g\alpha}\phi^{\prime}_{i})_{*})=\det(I-(A_{\alpha}\varphi_{i})_{*}).\qed$

Putting all these results together gives the averaging formula:

######  Theorem 4.9.

The Nielsen number of an affine map $f:\pi\backslash G\to D_{n}(\pi\backslash
G)$ with lift
$\tilde{f}:x\mapsto(g_{1}\varphi_{1}(x),\ldots,g_{n}\varphi_{n}(x))$ is given
by

$N(f)=\frac{1}{[\pi:N]}\sum_{\bar{\alpha}\in\pi/N}\sum_{i=1}^{n}|\det(I-(A_{\alpha}\varphi_{i})_{*})|.$

###### Proof.

Recall from section 3 that

$N(f)=\sum_{i=1}^{n}\frac{1}{[\pi:S^{\prime}_{i}]}\sum_{\bar{\alpha}\in\pi/N}\sum_{[g]\in\mathcal{R}[\tau_{\alpha}\phi^{\prime}_{i}]}|\overline{\mathrm{fix}(\tau_{g\alpha}\phi_{i})}|\,\varepsilon_{g\alpha,i}.$

In case $\det(I-(A_{\alpha}\varphi_{i})_{*})\neq 0$, Lemma 4.1 implies
$\mathrm{fix}(\tau_{g\alpha}\phi_{i})=1$, so in particular
$|\overline{\mathrm{fix}(\tau_{g\alpha}\phi_{i})}|=1$; Corollary 4.4 implies
$\varepsilon_{g\alpha,i}=1$ for all $g$; and Lemmas 4.7 and 4.8 imply

$R(\tau_{\alpha}\phi^{\prime}_{i})=[N:S^{\prime}_{i}]|\det(I-(A_{\alpha}\varphi_{i})_{*})|.$

Thus, in this case,

$\sum_{[g]\in\mathcal{R}[\tau_{\alpha}\phi^{\prime}_{i}]}|\overline{\mathrm{fix}(\tau_{g\alpha}\phi_{i})}|\,\varepsilon_{g\alpha,i}=[N:S^{\prime}_{i}]|\det(I-(A_{\alpha}\varphi_{i})_{*})|.$

In case $\det(I-(A_{\alpha}\varphi_{i})_{*})=0$, Corollary 4.6 implies
$\varepsilon_{g\alpha,i}=0$ for all $g$, so

$\sum_{[g]\in\mathcal{R}[\tau_{\alpha}\phi^{\prime}_{i}]}|\overline{\mathrm{fix}(\tau_{g\alpha}\phi_{i})}|\,\varepsilon_{g\alpha,i}=0=[N:S^{\prime}_{i}]|\det(I-(A_{\alpha}\varphi_{i})_{*})|.$

It follows that

$\displaystyle N(f)$
$\displaystyle=\sum_{i=1}^{n}\frac{1}{[\pi:S^{\prime}_{i}]}\sum_{\bar{\alpha}\in\pi/N}[N:S^{\prime}_{i}]|\det(I-(A_{\alpha}\varphi_{i})_{*})|$
$\displaystyle=\frac{1}{[\pi:N]}\sum_{\bar{\alpha}\in\pi/N}\sum_{i=1}^{n}\,|\det(I-(A_{\alpha}\varphi_{i})_{*})|.\qed$

##  5\. Example

To illustrate the formula, consider the following example. Take
$G=\mathbb{R}^{2}$ and let
$\pi\subseteq\mathbb{R}^{2}\rtimes\mathrm{GL}_{2}(\mathbb{R})$ be the group
generated by

$a=\left(\begin{bmatrix}1\\\ 0\end{bmatrix},\begin{bmatrix}1&0\\\
0&1\end{bmatrix}\right),\quad b=\left(\begin{bmatrix}0\\\
\frac{1}{2}\end{bmatrix},\begin{bmatrix}-1&0\\\ 0&1\end{bmatrix}\right).$

Then $\pi\backslash\mathbb{R}^{2}$ is an infra-nilmanifold isomorphic to the
Klein bottle. Consider the map given by

$\tilde{f}:\mathbb{R}^{2}\to
F_{2}(\mathbb{R}^{2},\pi):(t_{1},t_{2})\mapsto((0,\textstyle\frac{t_{2}}{2}),(0,\textstyle\frac{t_{2}}{2}-\frac{1}{4})).$

This map induces a well-defined $2$-valued map
$f:\pi\backslash\mathbb{R}^{2}\to D_{2}(\pi\backslash\mathbb{R}^{2})$ on the
Klein bottle, since for all $(t_{1},t_{2})\in\mathbb{R}^{2}$

$\displaystyle\tilde{f}(a(t_{1},t_{2}))$
$\displaystyle=((0,\textstyle\frac{t_{2}}{2}),(0,\textstyle\frac{t_{2}}{2}-\frac{1}{4}))=(1,1;1)\tilde{f}(t_{1},t_{2})$
$\displaystyle\tilde{f}(b(t_{1},t_{2}))$
$\displaystyle=(b(0,\textstyle\frac{t_{2}}{2}-\frac{1}{4}),(0,\textstyle\frac{t_{2}}{2}))=(b,1;\sigma)\tilde{f}(t_{1},t_{2})$

with $\sigma\in\Sigma_{2}$ the permutation that interchanges $1$ and $2$.

Note that $f$ is an affine map, with

$g_{1}=\begin{bmatrix}0\\\ 0\end{bmatrix},\quad g_{2}=\begin{bmatrix}0\\\
-\frac{1}{4}\end{bmatrix},\quad\varphi_{1}=\varphi_{2}=\begin{bmatrix}0&0\\\
0&\frac{1}{2}\end{bmatrix}.$

To compute the Nielsen number of $f$, we consider the nilmanifold
$Z\backslash\mathbb{R}^{2}$ where $Z=\pi\cap\mathbb{R}^{2}=\langle
a,b^{2}\rangle\cong\mathbb{Z}^{2}$, i.e. the $2$-torus. The group $\pi/Z$ has
two elements, represented by

$\left(\begin{bmatrix}0\\\ 0\end{bmatrix},\begin{bmatrix}1&0\\\
0&1\end{bmatrix}\right)\quad\text{and}\quad\left(\begin{bmatrix}0\\\
0\end{bmatrix},\begin{bmatrix}-1&0\\\ 0&1\end{bmatrix}\right).$

Thus, by Theorem 4.9

$\displaystyle N(f)$
$\displaystyle=\frac{1}{2}\sum_{\bar{\alpha}\in\pi/Z}\sum_{i=1}^{2}\left|\,\det\left(I-A_{\alpha}\begin{bmatrix}0&0\\\
0&\frac{1}{2}\end{bmatrix}\right)\right|$
$\displaystyle=\sum_{\bar{\alpha}\in\pi/Z}\left|\,\det\left(I-A_{\alpha}\begin{bmatrix}0&0\\\
0&\frac{1}{2}\end{bmatrix}\right)\right|$
$\displaystyle=\left|\,\det\left(I-\begin{bmatrix}1&0\\\
0&1\end{bmatrix}\begin{bmatrix}0&0\\\
0&\frac{1}{2}\end{bmatrix}\right)\right|+\left|\,\det\left(I-\begin{bmatrix}-1&0\\\
0&1\end{bmatrix}\begin{bmatrix}0&0\\\
0&\frac{1}{2}\end{bmatrix}\right)\right|$
$\displaystyle=\left|\,\det\begin{bmatrix}1&0\\\
0&\frac{1}{2}\end{bmatrix}\right|+\left|\,\det\begin{bmatrix}1&0\\\
0&\frac{1}{2}\end{bmatrix}\right|=1.$

A direct calculation shows that the map $f$ has one isolated fixed point:
indeed, for all $k,\ell\in\mathbb{Z}$ we have

$\displaystyle(t_{1},t_{2})=a^{k}b^{\ell}(0,\textstyle\frac{t_{2}}{2})$
$\displaystyle\enskip\Leftrightarrow\enskip(t_{1},t_{2})=(k,\textstyle\frac{t_{2}}{2}+\frac{\ell}{2})$
$\displaystyle\enskip\Leftrightarrow\enskip(t_{1},t_{2})=(k,\ell)$

and

$\displaystyle(t_{1},t_{2})=a^{k}b^{\ell}(0,\textstyle\frac{t_{2}}{2}-\frac{1}{4})$
$\displaystyle\enskip\Leftrightarrow\enskip(t_{1},t_{2})=(k,\textstyle\frac{t_{2}}{2}-\frac{1}{4}+\frac{\ell}{2})$
$\displaystyle\enskip\Leftrightarrow\enskip(t_{1},t_{2})=(k,\textstyle-\frac{1}{2}+\ell);$

and all these points $(k,\ell)$ and $(k,-\frac{1}{2}+\ell)$ in
$\mathbb{R}^{2}$ project to the same point on the Klein bottle. Thus, the
minimal number of fixed points is actually attained in this case.

######  Remark 5.1.

This map $f$ is an example of a map on the Klein bottle that does not lift to
the torus $Z\backslash\mathbb{R}^{2}$. In fact, there is no nilmanifold
(torus) $N\backslash\mathbb{R}^{2}$ that finitely covers
$\pi\backslash\mathbb{R}^{2}$ so that $f$ lifts to
$N\backslash\mathbb{R}^{2}$: in order for such a lift to exist, the induced
morphism of covering groups
$f_{*}=(\phi_{1},\phi_{2};\sigma):\pi\to\pi^{2}\rtimes\Sigma_{2}$ defined in
section 1 must satisfy $f_{*}(N)\subseteq N^{2}\rtimes\Sigma_{2}$. However,
note that $f_{*}(b^{2})=(b,b;1)$. If $N\backslash\mathbb{R}^{2}$ is a
nilmanifold that finitely covers $\pi\backslash\mathbb{R}^{2}$, then $N$ must
be a finite index subgroup of $Z$. Hence there is a smallest
$\ell\in\mathbb{Z}_{>0}$ so that $(b^{2})^{\ell}\in N$. But then
$f_{*}((b^{2})^{\ell})=(b^{\ell},b^{\ell};1)$ is not an element of
$N^{2}\rtimes\Sigma_{2}$, by minimality of $\ell$.

This illustrates the fact that a classical averaging formula in terms of lifts
as in [8] is not feasible in the $n$-valued case.

## References

  * [1] R. F. Brown, C. Deconinck, K. Dekimpe, and P. C. Staecker.  Lifting Classes for the Fixed Point Theory of _n_ -Valued Maps.  Topology and its Applications, 274:107–125, 2020.
  * [2] R. F. Brown and D. L. Gonçalves.  On the topology of _n_ -valued maps.  Advanced Fixed Point Theory, 8(2):205–220, 2018.
  * [3] L. Corwin and F. P. Greenleaf.  Representations of nilpotent Lie groups and their applications: Volume 1, Part 1, Basic theory and examples, volume 18.  Cambridge University Press, 1990.
  * [4] C. Deconinck and K. Dekimpe.  Nielsen numbers of affine $n$-valued maps on nilmanifolds.  Journal of Fixed Point Theory and Applications, 25(4):Paper No. 84, 29, 2023.
  * [5] K. Dekimpe.  A users’ guide to infra-nilmanifolds and almost-Bieberbach groups, volume 40 of Adv. Lect. Math. (ALM), Handbook of group actions. Vol. III, pages 215–262.  Int. Press, Somerville, MA, 2018.
  * [6] K. Dekimpe and L. D. Weerdt.  Non-affine $n$-valued maps on tori.  arXiv:2401.05053 (to appear in Topology and its Applications), 2024\.
  * [7] K. Y. Ha, J. B. Lee, and P. Penninckx.  Formulas for the Reidemeister, Lefschetz and Nielsen coincidence number of maps between infra-nilmanifolds.  Journal of Fixed Point Theory and Applications, 2012(39):1–23, 2012\.
  * [8] S. W. Kim, J. B. Lee, and K. B. Lee.  Averaging formula for Nielsen numbers.  Nagoya Mathematical Journal, 178:37–53, 2005.
  * [9] J. B. Lee and K. B. Lee.  Lefschetz numbers for continuous maps, and periods for expanding maps on infra-nilmanifolds.  Journal of Geometry and Physics, 56(10):2011–2023, 2006.
  * [10] K. B. Lee.  Maps on infra-nilmanifolds.  Pacific Journal of Mathematics, 168(1):157–166, 1995.
  * [11] A. I. Mal’cev.  On a class of homogeneous spaces.  Izvestiya Akademii Nauk SSSR. Seriya Matematicheskaya, 13:9–32, 1949.


# Pricing of European Calls
with the
Quantum Fourier Transform

Tom Ewen  Department of Financial Mathematics
Fraunhofer ITWM
Kaiserslautern, Germany
<EMAIL_ADDRESS>
0009-0007-4028-6698

###### Abstract

The accurate valuation of financial derivatives plays a pivotal role in the
finance industry. Although closed formulas for pricing are available for
certain models and option types, exemplified by the European Call and Put
options in the Black-Scholes Model, the use of either more complex models or
more sophisticated options precludes the existence of such formulas, thereby
requiring alternative approaches. The Monte Carlo simulation, an alternative
approach effective in nearly all scenarios, has already been challenged by
quantum computing techniques that leverage Amplitude Estimation. Despite its
theoretical promise, this approach currently faces limitations due to the
constraints of hardware in the Noisy Intermediate-Scale Quantum (NISQ) era.

In this study, we introduce and analyze a quantum algorithm for pricing
European call options across a broad spectrum of asset models. This method
transforms a classical approach, which utilizes the Fast Fourier Transform
(FFT), into a quantum algorithm, leveraging the efficiency of the Quantum
Fourier Transform (QFT). Furthermore, we compare this novel algorithm with
existing quantum algorithms for option pricing.

###### Index Terms:

quantum computing, quantum finance, option pricing, quantum fourier transform,
fourier transform, discrete fourier transform

##  I Introduction

In the finance sector the pricing of derivatives is an important task.
Derivatives are contracts that promise the buyer a payoff depending on an
underlying asset, a simple example is the European Call which pays the buyer
the difference between a predefined strike, $K$, and the value of the
underlying at its maturity $S_{T}$, if that difference is positive, i.e.,
$\max\\{S_{T}-K,0\\}$. Since the underlying is modeled as a stochastic
process, the payoff of this derivative is also stochastic. Pricing this
derivative involves finding the expectation of the payoff under the risk-free
measure. Speeding up this task would be a huge impact quantum computers could
bring. In the literature there are presented different approaches on how to
achieve this using a Quantum Computer [1, 2]. Both approaches have in common
that they mimic classical Monte-Carlo methods, where the potential for
improvement comes from the Amplitude Estimation algorithm [3]. In this work we
will present a different approach that is based on numerically approximating
the option price and calculating this approximation via the Discrete Fourier
Transform (DFT). Here the potential speedup stems from the efficiency of the
Quantum Fourier Transform (QFT). This classical part of this method was
introduced to price European calls for models where the characteristic
function of the log-price is known [4].

The remainder of the paper is structured as follows, we will introduce the
numerical approximation of the option price in Section II, and we will see how
to perform this approximation on a quantum computer in Section III. In Section
IV we will compare the result with other approaches from the literature and
give an intuition on error rates in Section V. Finally, we conclude with a
short summary and a brief outlook in Section VI.

##  II Numerical Approximation

This section follows the ideas of [4] to find a numerical approximation of the
price of a European Call that can be calculated with the DFT. The goal is to
calculate the fair price of a European call with strike $K\in\mathbb{R}_{>0}$
and maturity $T\in\mathbb{R}_{>0}$ which is based on an underlying
$\left(S_{t}\right)_{0\leq t\leq T}$. The fair price is then given as the
discounted expected payout under the risk-free measure

$C=\mathrm{e}^{-rT}\mathbb{E}[\max\left\\{S_{T}-K,0\right\\}].$ (1)

See for example [5] for a more detailed argumentation.

To be able to calculate this expectation we need to assume a model for the
underlying. For this approach we will assume that the characteristic function
of the logarithm of the underlying’s price is known. This is the case in many
models, the Black-Scholes Model or the Heston Model being two prominent
examples or the Variance Gamma model [6] being a more complex example.

We will calculate the expectation in Equation 1 by expressing it as an
integral and approximating this integral numerically. Note that we replace the
underlying’s price and the strike with their logarithms and write a lowercase
letter instead of a capital one to denote the logarithm. The Option Price is
then given as

$C=\mathrm{e}^{-rT}\int_{k}^{\infty}(\mathrm{e}^{s}-\mathrm{e}^{k})f_{s_{T}}(s)\mathrm{d}s.$
(2)

The maximum from Equation 1 is taken care of by starting the integral only
from $k$ instead of $-\infty$. If the density $f_{s_{T}}$ was known
analytically, we could stop here, discretize the integral and approximate, but
this is not the case for all models we are interested in.

###  II-A Analytic transformation

First we will transform Equation 2 into an expression that no longer depends
on the density, but the characteristic function instead. As a first step we
will express the price in terms of the log-strike and introduce a dampening
factor $\alpha\in\mathbb{R}_{>0}$ to make the expression square integrable
with respect to $k$.

$\widetilde{C}(k)\coloneqq\mathrm{e}^{\alpha
k}C(k)\overset{\lx@cref{creftype~refnum}{eq:option_price_integral}}{=}\mathrm{e}^{\alpha
k}\mathrm{e}^{-rT}\int_{k}^{\infty}(\mathrm{e}^{s}-\mathrm{e}^{k})f_{s_{T}}(s)\mathrm{d}s.$
(3)

Now we take the Fourier Transform (FT) of $\widetilde{C}(k)$

$\psi(v)=\int_{-\infty}^{\infty}\mathrm{e}^{\boldsymbol{\mathrm{i}}vk}\widetilde{C}(k)\mathrm{d}k.$
(4)

Next, we plug in Equation 3 and applying Fubini’s Theorem, which we are
allowed to do, since the dampening factor guarantees the square integrability.
This leads us to

$\psi(v)=\int_{-\infty}^{\infty}\mathrm{e}^{-rT}f_{s_{T}}(s)\int_{-\infty}^{s}\left(\mathrm{e}^{s}\mathrm{e}^{k(\alpha+\boldsymbol{\mathrm{i}}v)}-\mathrm{e}^{k(1+\alpha+\boldsymbol{\mathrm{i}}v)}\right)\mathrm{d}k\mathrm{d}s.$

The change of order of the integration allows us to explicitly calculate the
inner integral

$\int_{-\infty}^{s}\left(\mathrm{e}^{s}\mathrm{e}^{k(\alpha+\boldsymbol{\mathrm{i}}v)}-\mathrm{e}^{k(1+\alpha+\boldsymbol{\mathrm{i}}v)}\right)=\frac{\mathrm{e}^{s}\mathrm{e}^{s(\alpha+\boldsymbol{\mathrm{i}}v)}}{\alpha+\boldsymbol{\mathrm{i}}v}-\frac{\mathrm{e}^{s(1+\alpha+\boldsymbol{\mathrm{i}}v)}}{1+\alpha+\boldsymbol{\mathrm{i}}v}.$

Together with the definition of the characteristic function

$\Phi(v)\coloneq\int_{-\infty}^{\infty}\mathrm{e}^{\boldsymbol{\mathrm{i}}vs}f_{s_{T}}(s)\mathrm{d}s$

we can simplify eq. 4 to

$\psi(v)=\frac{\mathrm{e}^{-rT}\Phi\left(\frac{1+\alpha+\boldsymbol{\mathrm{i}}v}{\boldsymbol{\mathrm{i}}}\right)}{(\alpha+\boldsymbol{\mathrm{i}}v)(1+\alpha+\boldsymbol{\mathrm{i}}v)}.$

As we require for this approach the characteristic function to be known
analytically, we know $\psi(v)$ analytically as well.

In a last step we apply the inverse FT and reverse the dampening to get an
expression for the Option Price

$C(k)=\mathrm{e}^{-\alpha k}\widetilde{C}(k)=\frac{\mathrm{e}^{-\alpha
k}}{2\pi}\int_{-\infty}^{\infty}\mathrm{e}^{-\boldsymbol{\mathrm{i}}vk}\psi(v)\mathrm{d}v.$
(5)

###  II-B Numerical Approximation

Now that we have an expression for the Price the next step is actually
calculating it. As eq. 5 contains an improper integral, that we cannot
calculate directly, we need to find an approximation, i.e., compute the price
numerically. At this point this work deviates from [4] to make the
approximation more suitable for a quantum computer. We will have to make two
approximations in the process of numerically calculating $C(k)$. Firstly we
have to cut off the integral at some finite point, and secondly we will
introduce a discretization error. The second source of approximation error can
be mitigated by employing more involved discretization schemes, like the
Simpson Rule, but this is not the focus of this work and when looking at the
results later on, not really necessary.

We fix a step size $\Delta_{v}\in\mathbb{R}_{>0}$ and the number of
discretization steps $N\in\mathbb{N}$ for the positive and negative part of
the integration range each and discretize Equation 5 as

$C(k)\approx\frac{\mathrm{e}^{-\alpha
k}}{2\pi}\sum_{j=-N}^{N-1}\mathrm{e}^{-\boldsymbol{\mathrm{i}}\Delta_{v}jk}\psi_{T}(\Delta_{v}j)\Delta_{v}.$

Now we specify a discretization for the log-strike $k_{l}\coloneqq
k_{0}+\Delta_{k}l$ for $0\leq l<2N$ while we fix the relation between the
discretizations of $v$ and $k$ to $\Delta_{k}\Delta_{v}=\frac{\pi}{N}$. With
an additional shift of the index this will give us a discretization that fits
into the structure needed for the DFT

$\begin{split}C(k_{l})&\approx\frac{\mathrm{e}^{-\alpha(k_{0}+\Delta_{k}l)}}{2\pi}\Delta_{v}\mathrm{e}^{\boldsymbol{\mathrm{i}}\pi
l}\sum_{j=0}^{2N-1}\mathrm{e}^{-\boldsymbol{\mathrm{i}}\frac{2\pi}{2N}jl}x_{j}\\\
x_{j}&=\mathrm{e}^{-\boldsymbol{\mathrm{i}}\Delta_{v}jk_{0}}\mathrm{e}^{\boldsymbol{\mathrm{i}}\Delta_{v}Nk_{0}}\psi(\Delta_{v}(j-N)).\end{split}$
(6)

As seen in Figures 1 and 2 when choosing a good value for the dampening factor
$\alpha$, even for moderate number of discretization steps the approximation
is very accurate.

Figure 1: Prices of a European Call in a Black Scholes model with parameters
$S_{0}=100$, $r=0.05$, $\sigma=0.3$, $T=0.5$. The prices are calculated with
the discretization from Equation 6 where $\alpha=2.5$, $N=2^{10}$,
$\Delta_{k}=\frac{1}{\sqrt{N}}$ and $k_{0}=\ln 100-\frac{N\Delta_{k}}{2}$. We
see that the approximation that could be realized with ten qubits is already
very Figure 2:  Mean squared error between true prices of a European Call and
their approximation by Equation 6 for varying strikes and increasing number of
discretization steps in a Black Scholes model with parameters $S_{0}=100$,
$r=0.05$, $\sigma=0.3$, $T=0.5$. For all discretizations we fix
$\Delta_{k}=\frac{1}{\sqrt{N}}$ and $k_{0}=\ln 100-\frac{N\Delta_{k}}{2}$. We
see that the speed of convergence heavily depends on the choice of $alpha$.

##  III Pricing with the Quantum Fourier Transform

In this section we will see the necessary steps to evaluate the approximation
from Section II on a quantum computer. The idea is to calculate the sum from
Equation 6 with the QFT and thus achieving a benefit compared to the classical
approach.

The QFT is a unitary operation $QFT_{n}\in\mathbb{C}^{2^{n}\times 2^{n}}$,
operating on an $n$-qubit system, that transforms a given state
$\Ket{x}=\sum_{j=0}^{2^{n}-1}x_{j}\Ket{j}$ into
$\Ket{y}=\sum_{l=0}^{2^{n}-1}y_{l}\Ket{l}$ where

$y_{l}=\frac{1}{2^{\frac{n}{2}}}\sum_{j=0}^{2^{n}-1}x_{j}\mathrm{e}^{\boldsymbol{\mathrm{i}}\frac{2\pi}{2^{n}}jl}.$

The inverse QFT is a unitary operation $QFT_{n}^{-1}\in\mathbb{C}^{2^{n}\times
2^{n}}$, which maps a state $\Ket{x}=\sum_{j=0}^{2^{n}-1}x_{j}\Ket{j}$ to
$\Ket{y}=\sum_{l=0}^{2^{n}-1}y_{l}\Ket{l}$ where

$y_{l}=\frac{1}{2^{\frac{n}{2}}}\sum_{j=0}^{2^{n}-1}x_{j}\mathrm{e}^{-\boldsymbol{\mathrm{i}}\frac{2\pi}{2^{n}}lj}.$

Note that the conventions for the QFT differ slightly from the classical
version, for once the QFT corresponds to the inverse DFT. Further the factor
before the sum is in the QFT setting distributed between the two directions,
whereas for the DFT only one direction of the transform has that factor.

Before we can apply the QFT, or to be precise the inverse QFT, we need to
prepare the correct state. As an $n$-qubit system allows for $2^{n}$
amplitudes we will limit ourselves to discretizations $N=2^{n}$ for some
$n\in\mathbb{N}$. The positive and negative part of the integral will be
discretized individually, so in total we need $n+1$ qubits. We further have to
make sure that the state we want to prepare is actually a valid state. Thus,
we normalize first

$\widetilde{x}_{j}=\frac{x_{j}}{\sqrt{\sum\limits_{l=0}^{2^{n+1}-1}\left\lvert
x_{l}\right\rvert^{2}}}.$

We will call the unitary that prepares this state E

$E\Ket{0}=\sum_{j=0}^{2^{n+1}-1}\widetilde{x}_{j}\Ket{j}.$

On that state we apply the inverse QFT

$\Ket{y}=QFT^{-1}E\Ket{0}$

where

$\displaystyle y_{l}$
$\displaystyle=\frac{1}{2^{\frac{n+1}{2}}}\sum_{j=0}^{2^{n+1}-1}\mathrm{e}^{\boldsymbol{\mathrm{i}}\frac{2\pi}{2^{n+1}}lj}\widetilde{x}_{j}$
$\displaystyle=\frac{1}{2^{\frac{n+1}{2}}}\frac{1}{\sqrt{\sum\limits_{j=0}^{2^{n+1}-1}\left\lvert
x_{j}\right\rvert^{2}}}\sum_{j=0}^{2^{n+1}-1}\mathrm{e}^{\boldsymbol{\mathrm{i}}\frac{2\pi}{2^{n+1}}lj}x_{j}.$

Now we can plug this into Equation 6 to get

$C(k_{l})\approx\frac{\mathrm{e}^{-\alpha(k_{0}+\Delta_{k}l)}}{2\pi}\Delta_{v}\mathrm{e}^{\boldsymbol{\mathrm{i}}\pi
l}\sqrt{\sum_{j=0}^{2^{n+1}-1}\left\lvert
x_{j}\right\rvert^{2}}2^{\frac{n+1}{2}}y_{l}.$ (7)

Unfortunately the values $y_{l}$ we need are encoded in the amplitude of a
quantum state, and we do not have direct access to it. This could be achieved
by state tomography, but that is a very inefficient procedure, taking
exponentially many measurements in the number of qubits [7]. Alternatively we
can retrieve the absolute values $\lvert y_{l}\rvert$ by either Amplitude
Estimation or by simply executing many shots. While the latter is less
efficient it estimates all amplitudes in one go and not only the one of a
single state.

Knowing that the true price is real and positive and looking at Equation 7 we
see that $\mathrm{e}^{\boldsymbol{\mathrm{i}}\pi l}y_{l}$ needs to be positive
and real if the approximation would be without error. But the approximation is
not perfect, thus we introduce another approximation error replacing
$\mathrm{e}^{\boldsymbol{\mathrm{i}}\pi l}y_{l}$ by the square root of the
observed probability of state $\Ket{l}$. We will call the observed
probabilities $p_{l}$. The final approximation is given as

$C(k_{l})\approx\frac{\mathrm{e}^{-\alpha(k_{0}+\Delta_{k}l)}}{2\pi}\Delta_{v}\sqrt{\sum_{j=0}^{2^{n+1}-1}\left\lvert
x_{j}\right\rvert^{2}}2^{\frac{n+1}{2}}\sqrt{p_{l}}.$ (8)

The quality of the approximation strongly depends on how well the amplitudes
are estimated, in Figure 3 we can see that this again depends strongly the
number of shots used for the approximation, even if the quantum computer is
noise free, depicted here by the use of a simulator.

Figure 3: Prices of a European Call for different number of shots on a noise
free simulator in a Black Scholes model with parameters $S_{0}=100$, $r=0.05$,
$\sigma=0.3$, $T=0.5$. The prices are calculated with the discretization from
Equation 6 where $\alpha=2.5$, $N=2^{10}$, $\Delta_{k}=\frac{1}{\sqrt{N}}$ and
$k_{0}=\ln 100-\frac{N\Delta_{k}}{2}$. We see that even for an error free
device the error introduced by estimating the probabilities from finite many
realizations introduces an error.

##  IV Comparison

In this section we will see how this novel approach compares to existing
quantum algorithms for pricing options. The approaches introduced in [1, 2]
all have in common, that they start with loading a distribution into a quantum
register. On this distribution they apply a quantum algorithm to encode the
options payoff in the amplitude of one target qubit. This amplitude can then
be retrieved either by repeated measurement or amplitude estimation.

For the approach introduced in [1] we will rely on the implementation done by
the qiskit-finance [8] python library, while for our novel QFT approach and
the Conditional Parameterized Quantum Circuits (CPQC) [2] we will rely on our
own implementation.

We will not look at results on actual hardware, as we are interested in
comparing the algorithms in general and not how well they cope with current
hardware restrictions.

A common way to analyze quantum algorithms is to look at the scaling of the
circuit depth or the number of two qubit gates for an increasing number of
qubits. We see in Figure 4 that this novel approach does not compare well in
this metric.

Figure 4:  The circuit depth for different algorithms depending on the number
of used qubits. For calculating the depth every circuit is transpiled to
consist only of CNOT and U3 gates. Note that the circuit depth comes mainly
from the state preparation necessary for all algorithms. The implementation
provided by qiskit-finance and the implementation using CPQCs both use
ancillary qubits that make them look better in this comparison, as they do not
need to be initialized.

That only tells us, that this new approach scales worse for an increasing
number of qubits. But in our setting increasing the number of qubits is solely
done to improve the approximation, we don’t need a specific number of qubits
to be able to calculate real world examples. This means we should look at the
relation between the achieved approximation quality and the quantum resources
needed. As seen in Figure 5 in this comparison the QFT based option pricing
outperforms the other approaches notably. This is possible, as the QFT based
approach needs fewer qubits for getting good approximations.

(a) Circuit Depth against Option Price.

(b) Circuit Depth against Error.

(c) Used Number of Qubits against Error.

Figure 5:  Comparison of different quantum algorithms to compute option
prices. The priced option is a European Call with strike 100 in a Black
Scholes model with parameters $S_{0}=100$, $r=0.05$, $\sigma=0.3$, $T=0.5$. We
compare the novel QFT approach with two Monte-Carlo inspired approaches. We
see in Figure 5a that the qiskit-finance [8]implementation is biased, while
the other two seem to converge to the true price. For finance applications a
high precision is important thus we look at that in Figure 5b. When comparing
the approaches regarding the number of used qubits Figure 5c, the results look
similar.

A further advantage of the QFT based approach is, that the prices for many
strikes can be computed with only one circuit. The downside is, that it only
works for European Calls, and, in extension by the Put Call parity, for
European Puts [9].

##  V Error Propagation

Until now we only looked at idealized error free quantum devices. In this
section we will get an Idea how good a quantum computer would need to perform
to get practical results. To do so we compare Equation 7 and Equation 8 the
first one being the theoretical approximation making use of the amplitude and
the latter being the observable approximation making use of the observed
probability. Let us call the error the quantum computer does
$\epsilon_{l}=\lvert y_{l}-\sqrt{p_{l}}\rvert$ then the absolute difference
between the theoretical approximation and the observed approximation is

$\mathcal{E}_{l}=\frac{\mathrm{e}^{-\alpha(k_{0}+\Delta_{k}l)}}{2\pi}\Delta_{v}\sqrt{\sum_{j=0}^{2^{n+1}-1}\left\lvert
x_{j}\right\rvert^{2}}2^{\frac{n+1}{2}}\epsilon_{l}.$ (9)

This expression depends on the strike for which we want to calculate the
option price, but also on the parameter $\alpha$, which we can choose freely.
Note that the $x_{j}$ also depend on $\alpha$, and thus it is not straight
forward, how exactly the $\mathcal{E}_{l}$ depend on $\alpha$.

(a)  (b)

Figure 6:  The factor from Equation 9 for different strikes and dampening
factors $\alpha$ for a Black Scholes Model with parameters $S_{0}=100$,
$r=0.05$, $\sigma=0.3$, $T=0.5$. We can see that there is no one value for
$\alpha$ that fits for all strikes, especially if that strike is far away from
the start value of the underlying.

In Figure 6 we can see that the behavior of this error propagation heavily
depends on the strike, especially if the strike is far away from the starting
value of the underlying. This means that the choice of $\alpha$ could be
different, depending on the strike we are interested in. But as long the
strike is not too far from the start value there is a sweet spot for $\alpha$
around $2.5$. There the factor $\mathcal{E}$ from eq. 9 is below $50$ which
tells us, that if we, for example, want an approximation precision up to the
second digit, the quantum computer needs to approximate the amplitude with an
error below $\frac{0.01}{50}=0.0002$. Unfortunately for devices in the NISQ
era, this is not achievable.

##  VI Conclusion

We have seen a novel approach in using quantum computers for pricing Options
that makes use of the QFT. This new approach performs better than previously
introduced algorithms for a wide class of models, but only for European Calls
and Puts. The QFT promises a significant speedup compared to the classical
FFT, which is unfortunately in parts counteracted by the expensive state
preparation.

As no efficient procedure is currently known for preparing general states,
further research could investigate whether there is an inherent structure in
the states, needed for this novel approach, that permits more efficient
preparation.

## References

  * [1] N. Stamatopoulos, D. J. Egger, Y. Sun, C. Zoufal, R. Iten, N. Shen, and S. Woerner, “Option Pricing using Quantum Computers.” [Online]. Available: http://arxiv.org/abs/1905.02666
  * [2] M.-O. Wolf, T. Ewen, and I. Turkalj. Quantum Architecture Search for Quantum Monte Carlo Integration via Conditional Parameterized Circuits with Application to Finance. [Online]. Available: http://arxiv.org/abs/2304.08793
  * [3] G. Brassard, P. Hoyer, M. Mosca, and A. Tapp, “Quantum Amplitude Amplification and Estimation.” [Online]. Available: http://arxiv.org/abs/quant-ph/0005055
  * [4] P. Carr and D. Madan, “Option valuation using the fast Fourier transform,” vol. 2, no. 4, pp. 61–73. [Online]. Available: http://www.risk.net/journal-of-computational-finance/technical-paper/2160495/option-valuation-fast-fourier-transform
  * [5] R. Korn and E. Korn, _Option Pricing and Portfolio Optimization: Modern Methods of Financial Mathematics_ , ser. Graduate Studies in Mathematics. American Mathematical Society, no. 31.
  * [6] D. B. Madan and E. Seneta, “The Variance Gamma (V.G.) Model for Share Market Returns,” vol. 63, no. 4, pp. 511–524. [Online]. Available: https://www.jstor.org/stable/2353303
  * [7] D. F. V. James, P. G. Kwiat, W. J. Munro, and A. G. White, “Measurement of qubits,” vol. 64, no. 5, p. 052312. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.64.052312
  * [8] Qiskit contributors, “Qiskit: An open-source framework for quantum computing.”
  * [9] J. Hull, _Options, Futures, and Other Derivatives_ , ninth edition ed. Pearson.