# Zeta Functions of Certain Quadratic Orders

Malors Espinosa<EMAIL_ADDRESS>Department of
Mathematics, University of Toronto Room 6290, 40 St. George Street, Toronto,
Ontario, Canada M5S 2E4

###### Abstract

In [9] Langlands provides a formula for certain product of orbital integrals
in $GL(2,\mathbb{Q})$. Its generalization has become an important question for
the strategy of Beyond Endoscopy. Arthur in [1] predicts this formula should
coincide with a product of polynomials associated to zeta functions of orders
constructed in [14] by Zhiwei Yun. In this paper we compute, for a certain
family of orders, explicit formulas for these zeta functions by a recursive
method. We use these zeta functions in [5] to prove that Arthur’s prediction
is correct.

Mathematics Subject Classification: 11S40, 11S45

††journal: ARXIV

##  1 Introduction and Results of this Article

Let $K$ be a $p-$adic field and $\mathcal{O}_{K}$ be its ring of integers. Let
$L$ be a reduced $K$-algebra of dimension $2$ over $K$ and $\mathcal{O}_{L}$
the integral closure of $\mathcal{O}_{K}$ in $L$. In [14], Yun defines for a
given order $\mathcal{O}\subseteq L$ a zeta function $\zeta_{\mathcal{O}}$. It
generalizes the classical construction of the zeta function of
$\mathcal{O}_{L}$. In [14] it is also proven that $\zeta_{\mathcal{O}}$ is a
rational function, that is

$\zeta_{\mathcal{O}}(s)=\dfrac{P(q^{-s})}{V(s)},$

where $q$ is the cardinality of the residue field of $K$. $V$ is a polynomial
in $q^{-s}$ that only depends on the extension $L/K$, while $P$ is a
polynomial that depends on $\mathcal{O}$.

The general theory of discrete valuation rings guarantees the existence of
$\Delta\in\mathcal{O}_{L}$ such that

$\mathcal{O}_{L}=\mathcal{O}_{K}[\Delta].$

Using this, we define for each integer $n\geq 0$, the order

$\mathcal{O}_{n}\mathrel{\mathop{\mathchar
58\relax}}=\mathcal{O}_{K}[p^{n}\Delta],$

where $p$ is the uniformizer of $K$. This is an order and thus has associated
a zeta function $\zeta_{n}$. The main result of this article is the explicit
computation of the polynomial $P$ for $\zeta_{n}$ (i.e. the numerator of its
rational expression). More concretely, our main theorem is:

######  Theorem 1.1.

(Theorem 5.4 in section 5) For each $n\geq 0$ define the following
polynomials:

$\displaystyle R_{n}(X)$ $\displaystyle=1+qX^{2}+q^{2}X^{4}+...+q^{n}X^{2n},$

and for $n\geq 1$ define

$\displaystyle U_{n}(X)$ $\displaystyle=(1+X)R_{n-1}(X)+q^{n}X^{2n},$
$\displaystyle S_{n}(X)$ $\displaystyle=(1-X)R_{n-1}(X)+q^{n}X^{2n}.$

Finally, also put $U_{0}(X)=S_{0}(X)=1$. Explicitly, these polynomials are

$\displaystyle R_{n}(X)$ $\displaystyle=1+qX^{2}+q^{2}X^{4}+...+q^{n}X^{2n},$
$\displaystyle U_{n}(X)$
$\displaystyle=1+X+qX^{2}+qX^{3}+...+q^{n-1}X^{2n-2}+q^{n-1}X^{2n-1}+q^{n}X^{2n},$
$\displaystyle S_{n}(X)$
$\displaystyle=1-X+qX^{2}-qX^{3}+...+q^{n-1}X^{2n-2}-q^{n-1}X^{2n-1}+q^{n}X^{2n}.$

Then the solution of the ramified, unramified and split case recurrence,
respectively, satisfy

$\displaystyle(1-q^{-s})\zeta_{n}(s)$ $\displaystyle=R_{n}(q^{-s}),$
$\displaystyle(1-q^{-2s})\zeta_{n}(s)$ $\displaystyle=U_{n}(q^{-s}),$
$\displaystyle(1-q^{-s})^{2}\zeta_{n}(s)$ $\displaystyle=S_{n}(q^{-s}).$

Notice that the assumption that $L$ has dimension $2$ over $K$ implies that
$L$ is one of three possible options: a ramified field extension of $K$, an
unramified field extension of $K$ or $L=K\times K$.

These polynomials were already computed in [7] (see the proof of Theorem 1
there). In that paper these polynomials were computed by factoring into Euler
products a global formula deduced by Zagier in [15] (see proposition 3(iii),
page 130 there) and more generally in the recent paper [8] (see their Theorem
1). In particular, it relies entirely on global methods. On the contrary, we
compute these polynomials by a recursive method that is entirely local in
nature and that does not require any global formula beforehand. Concretely,
the result is the following

######  Theorem 1.2.

(Theorem 4.2 in section 4) For $n\geq 1$, the zeta functions of the orders
$\mathcal{O}_{n}$ satisfy the recurrence relation

$\zeta_{n}(s)=\zeta_{n}^{P}(s)+q^{-s}\zeta_{n-1}(s).$

In this theorem, $\zeta_{n}^{P}(s)$ is the contribution to the zeta function
$\zeta_{n}$ from the principal ideals of $\mathcal{O}_{n}$. Explicitly it is

$\zeta_{n}^{P}(s)=\displaystyle\sum_{I\subseteq\mathcal{O}_{n}}\dfrac{1}{[\mathcal{O}_{n}\mathrel{\mathop{\mathchar
58\relax}}I]^{s}},$

where the sum runs over the principal ideals of finite index in
$\mathcal{O}_{n}$.

The recurrence relation is the same regardless of the type of extension $L/K$
is. This obfuscates an important point: when $L=K\times K$, we have that
$\mathcal{O}_{L}=\mathcal{O}_{K}\times\mathcal{O}_{K}$ is not a discrete
valuation ring nor a local ring nor an integral domain. We will be able to
overcome this in every occasion, but a significant part of the work done in
this paper is needed precisely to deal with this case.

The recurrence relation follows from a dichotomy that ideals
$I\subseteq\mathcal{O}_{n}$ of $\mathcal{O}_{K}-$rank 2 satisfy: they are
principal ideals of $\mathcal{O}_{n}$ or they are the image of an ideal of
$\mathcal{O}_{n-1}$ under multiplication by $p$. The recursive relation is the
algebraic restatement of this fact.

To prove this dichotomy we introduce the concept of representative of an ideal
$I$. It is an element which has minimal possible valuation, in each coordinate
simultaneously, among the elements of $I$. The existence of such elements is
trivial when $L/K$ is a field extension, but requires care when $L=K\times K$.
Once we know they exist, we can prove the following result, which implies the
dichotomy:

######  Proposition 1.3.

(Proposition 3.19 in section 3) Let $n\geq 0$. For every rank $2$-ideal
$I\subseteq\mathcal{O}_{n}$ and every representative $x\in I$, there exists
$0\leq i\leq n$ such that

$I=x\mathcal{O}_{i}.$

Furthermore, $i$ only depends on $I$.

This proposition follows from standard arguments when $L/K$ is a field
extension due to the existence of a valuation in $\mathcal{O}_{L}$. We
introduce the notion of representative to adapt those argument when $L=K\times
K$.

In order to solve the recurrence we need the initial condition $\zeta_{0}$ and
$\zeta_{n}^{P}(s)$ explicitly. The initial condition is straightforward
because it is the zeta function of $\mathcal{O}_{L}$. For $\zeta_{n}^{P}$ we
prove:

######  Proposition 1.4.

(Proposition 4.16 in section 4) The principal part of the zeta functions of
the orders $\mathcal{O}_{n}$ satisfies

$\zeta_{n}^{P}(s)=\displaystyle\sum_{d=0}^{n-1}\dfrac{[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{*}]}{[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n-d}^{*}]}\cdot\dfrac{1}{q^{2ds}}+\dfrac{[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{*}]}{q^{2ns}V(s)}.$

Recalll that $V(s)$ is the denominator of the rational expression of
$\zeta_{n}(s)$. It is an explicit polynomial that depends only on $L/K$.

The proof of this proposition follows from understanding how different
principal ideals contribute to $\zeta_{n}^{P}(s)$. We divide principal ideals
of $\mathcal{O}_{n}$ into two classes, according to the properties of their
representatives (vaguely, we divide them according to whether the
representative is large or small in a specific sense). Each of the classes is
responsible for one of the two terms in the expression of $\zeta_{n}^{P}(s)$.

After the expansion of $\zeta_{n}^{p}(s)$ is settled, we prove

######  Proposition 1.5.

(Proposition 5.2 in section 5) The indices of the units subgroups satisfy for
$n\geq 1$,

$[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{*}]=\left\\{\begin{array}[]{ll}q^{n}&\mbox{in the
ramified case,}\\\ (q+1)q^{n-1}&\mbox{in the unramified case,}\\\
(q-1)q^{n-1}&\mbox{in the split case.}\\\ \end{array}\right.$

And, of course, $[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{0}^{*}]=1$.

The fact that the indices and the initial condition $\zeta_{0}(s)$ vary
according to $L/K$ is the responsible of the existence of three different
families of polynomials. The recurrence is solved with this information by a
straightforward induction.

The source of motivation of the author to find these polynomials is the
Langlands Program. The central conjecture of the Langlands Program is the
Principle of Functoriality. This important conjecture remains unproven despite
it being known in several cases which have remarkable implications in number
theory, representation theory and harmonic analysis.

In [9], Langlands suggests a new approach to try to prove the principle of
Functoriality which has come to be known as Beyond Endoscopy. Vaguely
speaking, it is a strategy to construct a new trace formula which would allow
a more careful analysis of the automorphic $L-$functions.

In [9], a particular formula for the product of certain orbital integrals for
each of the local completions of $\mbox{GL}(2,\mathbb{Q})$ is used in a
prominent role for the whole analysis. It is not clear how to generalize this
formula to $\mbox{GL}(n,\mathbb{Q})$ for $n>2$.

In [1], Arthur conjectures that such a generalization might be available in
the work [14] of Zhiwei Yun. Hence, it becomes relevant to understand if the
formula used by Langlands in [9] for the product of those orbital integrals in
$\mbox{GL}(2,\mathbb{Q})$ can be deduced from the zeta functions of orders in
the way Arthur predicts. This turns out to be the case and the explanation of
this is the topic of [5]. The first step for the verification of the
conjecture of Arthur is the explicit computations of the polynomials of orders
that we have explained above.

Furthermore, [9] and [1] work over $\mathbb{Q}$. Here we work over general
$p-$adic fields and their quadratic extensions, which has as consequence that
the formula of Langlands can be generalized for general algebraic number
fields. We develop this formula in [5] based on the work of this paper.

A more careful discussion of the literature is in order now. Similar Zeta
functions associated with orders were defined and studied by Solomon in [13].
Their properties were furthermore understood and developed in the important
articles [2], [3], [4] by Bushnell and Reiner. These zeta functions differ
from those we discuss in this paper in that they count
$\mathcal{O}_{K}$-lattices of rank $2$ inside of $\mathcal{O}_{n}$, while the
ones defined by Yun in [14] count ideals (after some simplifications explained
in section 2). As we have mentioned, the interest of our investigations stems
from Beyond Endoscopy and its specific relationship with the work of Yun (see
[14], section 4). Hence, the need to study the ideal counting zeta functions
as we do in this paper.

In [11] a recurrence relation for the zeta functions of lattices of the same
sequence of orders is deduced (see equation (32) in [11]). That recurrence
relation is similar to the one we obtain but not the same. They deduce their
recurrence relation by integral methods while we do it by isolating the
principal ideals and organizing them by their type. This allows to construct
explicitly all ideals of one of the given orders $\mathcal{O}_{n}$ by
following the recursive method. At the moment of writing, whether one
recurrence can be deduced from the other is unclear to the author and remains
an interesting question. Finally, similar manipulations as the ones we do to
count ideals of each type appear in [6].

Let us now conclude with a short overview of the organization of this paper.
In section 2 we review the results of [14] that we will need. In section 3 we
prove the dichotomy mentioned above that ideals satisfy. In section 4 we prove
the expansion of the principal part $\zeta_{n}^{P}(s)$. Finally, in section 5
we compute the indices of the unit subgroups and solve the recurrence.

##  2 Zeta Functions of Orders

In this article, $K$ will always be a $p-$adic field with uniformizer $p$. We
let $q$ be the cardinality of its residue field. $\mathcal{O}_{K}$ will denote
its ring of integers, $\mbox{val}_{p}$ its $p$-adic valuation.

In [14], Yun defines zeta functions associated to orders within finite
dimensional reduced $K$-algebras. In this section we will discuss the results
of [14] that we need suited out for our purposes.

Let $L$ be a finite dimensional reduced $K-$algebra and $\mathcal{O}_{L}$ the
integral closure of $\mathcal{O}_{K}$ in $L$. We now define the orders
associated to the extension $L/K$.

######  Definition 2.1.

An order $\mathcal{O}\subseteq L$ is a finitely generated
$\mathcal{O}_{K}$-module such that

$\mathcal{O}\otimes_{\mathcal{O}_{K}}K=L.$

An order $\mathcal{O}$ is monogenic if there exists an element $\Delta\in L$
such that

$\mathcal{O}=\mathcal{O}_{K}[\Delta].$

######  Remark 2.2.

Classically, orders are only defined for the case when $L/K$ is a field
extension. This definition extends the standard one, but several results of
the classical theory have to be shown in a different way because
$\mathcal{O}_{L}$ is no longer a discrete valuation ring nor a local ring.
Monogenicity will allow us to recover many of these results.

######  Definition 2.3.

Let $\mathcal{O}\subseteq\mathcal{O}_{L}$ be a monogenic order. We define its
zeta function as

$\zeta_{\mathcal{O}}(s)=\displaystyle\sum_{I\subseteq\mathcal{O}}\dfrac{1}{[\mathcal{O}\mathrel{\mathop{\mathchar
58\relax}}I]^{s}},$

where the sum runs over all ideals $I\subseteq\mathcal{O}$ of finite index.

######  Remark 2.4.

Let $\mathcal{O}\subseteq\mathcal{O}_{L}$ be a general order, not necessarily
monogenic. Its dual order is defined as

$\check{\mathcal{O}}=\left\\{x\in L\mid\langle
x,y\rangle\in\mathcal{O}_{K}\mbox{ for all }y\in\mathcal{O}\right\\},$

where $\langle\cdot,\cdot\rangle$ is a pairing that makes $\mathcal{O}_{L}$
self dual. In this context, Yun defines the zeta function as

$\zeta_{\mathcal{O}}(s)=\displaystyle\sum_{I\subseteq\check{\mathcal{O}}}\dfrac{1}{[\mathcal{O}\mathrel{\mathop{\mathchar
58\relax}}I]^{s}},$

where the sum runs over all $\mathcal{O}-$submodules of $\check{\mathcal{O}}$
of finite index. When $\mathcal{O}$ and $\check{\mathcal{O}}$ are isomorphic
as $\mathcal{O}-$modules both definitions of the zeta functions coincide.
Monogenic orders satisfy this, which explains why we work with definition 2.3.
We refer the reader to [14] for a more detailed discussion.

It is well known that $L$ can be written as a product of $g$ fields

$L=L_{1}\times...\times L_{g},$

for some positive integer $g$. For each $i=1,...,g$, the residue field of
$L_{i}$ has cardinality $Q_{i}=q^{f_{i}}$ and the prime ideal
$\pi_{i}\mathcal{O}_{L_{i}}$ of $\mathcal{O}_{L_{i}}$ satisfies

$(\pi_{i}\mathcal{O}_{L_{i}})^{e_{i}}=p\mathcal{O}_{L_{i}},$

where $\pi_{i}$ is a uniformizer of $\mathcal{O}_{L_{i}}$. We define a
function of a complex parameter $s$ as

$\displaystyle V(s)$
$\displaystyle=\displaystyle\prod_{i=1}^{g}(1-q^{-f_{i}s}),$

Let $\mathcal{O}\subseteq\mathcal{O}_{L}$ be a monogenic order. Define

$n\mathrel{\mathop{\mathchar
58\relax}}=\mbox{length}_{\mathcal{O}_{K}}(\mathcal{O}_{L}/\mathcal{O})=\log_{q}([\mathcal{O}_{L}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}]).$

Notice that $V(s)$ does not depend on the order $\mathcal{O}$ selected. Now we
can state the following

######  Proposition 2.5.

In the context of the previous discussion, define the function

$\tilde{J}(s)=q^{ns}V(s)\zeta_{\mathcal{O}}(s).$

Then there exists a polynomial $P(x)\in 1+x\mathbb{Z}[x]$ of degree $2n$ such
that

$V(s)\zeta_{\mathcal{O}}(s)=P(q^{-s}).$

Furthermore, $\tilde{J}$ satisfies the functional equation

$\tilde{J}(s)=\tilde{J}(1-s),$

or equivalently, the polynomial $P$ satisfies

$(qx^{2})^{n}P\left(\dfrac{1}{qx}\right)=P(x).$

This is proved in [14] as theorem 2.5.

The polynomials of this proposition are the ones we will find, for a
particular set of orders, in subsequent sections of this paper.

##  3 Arithmetic of the Orders $\mathcal{O}_{n}$

From now on we suppose $L$ is a reduced $K-$algebra of dimension $2$ over $K$.
This implies $L$ is a quadratic extension of $K$ or $L=K\times K$. In the
latter case, we always consider $K$ embedded diagonally in $L$.

######  Definition 3.1.

In the context of the above discussion, we refer to the case $L=K\times K$ as
the split case. On the other hand, when $L$ is a quadratic field extension of
$K$ we refer to the case as the nonsplit case.

When we do not distinguish between the split and nonsplit cases it is because
the definitions or arguments make sense for both cases.

Recall that $\mathcal{O}_{L}$ is the integral closure of $\mathcal{O}_{K}$ in
$L$. In the nonsplit case this is the ring of integers of $L$, while in the
split case it coincides with $\mathcal{O}_{K}\times\mathcal{O}_{K}$.
Furthermore, since $\mathcal{O}_{K}$ a discrete valuation ring, every
$\mathcal{O}_{K}-$algebra of finite dimension is generated by a single
element. We denote by $\Delta\in\mathcal{O}_{L}$ an element such that

$\mathcal{O}_{L}=\mathcal{O}_{K}[\Delta].$

In the split case, we put $\Delta=(\Delta_{1},\Delta_{2})$. Since
$\mathcal{O}_{L}$ is the integral closure within $L$ of $\mathcal{O}_{K}$,
$\Delta$ satisfies a quadratic equation. We suppose it is

$\Delta^{2}=\tau_{\Delta}\Delta-\delta_{\Delta},$

with $\tau_{\Delta},\delta_{\Delta}\in\mathcal{O}_{K}$.

In the nonsplit case we denote by $\pi$ a uniformizer of $\mathcal{O}_{L}$ and
by $\mbox{val}_{\pi}$ the corresponding valuation of $L$. We write $Q$ for the
cardinality of the residue field and $N_{L/K}$ for the norm of the extension
$L/K$. We let $e$ and $f$ be the ramification and inertia degrees of the
extension $L/K$. By definition, they satisfy

$\displaystyle Q$ $\displaystyle=q^{f},$ $\displaystyle p\mathcal{O}_{L}$
$\displaystyle=(\pi\mathcal{O}_{L})^{e}.$

We also have $ef=2$. It will be important to distinguish between the two
possible nonsplit cases. We give the following

######  Definition 3.2.

Let $L$ be a quadratic field extension of $K$. We refer to the case $e=2$ as
the ramified case. When $e=1$ we refer to it as the unramified case.

In the split case, we also denote by $N_{L/K}$ the norm of $L/K$. It is given
by

$N_{L/K}(x_{1},x_{2})=(x_{1},x_{2})(x_{2},x_{1})=x_{1}x_{2}\cdot(1,1)\in K.$

We will occasionally use the notation $\mathbf{1}=(1,1)$ to distinguish
between the unit of $\mathcal{O}_{K}$ and that of $\mathcal{O}_{L}$. We do
this when the arguments require the use of the coordinates of $K\times K$.
Otherwise, we use $1$ as the unit of $\mathcal{O}_{L}$ regardless of the case.

With these conventions at hand we can define the sequence of orders we will be
interested in:

######  Definition 3.3.

We define the main sequence of orders by

$\mathcal{O}_{n}\mathrel{\mathop{\mathchar
58\relax}}=\mathcal{O}_{K}[p^{n}\Delta],\;n\geq 0.$

More specifically, $\mathcal{O}_{n}\subseteq\mathcal{O}_{L}$ consists of the
elements of $\mathcal{O}_{L}$ that can be written as

$x+yp^{n}\Delta,$

for some unique $x,y\in\mathcal{O}_{K}$. Notice that the main sequence of
orders is independent of the choice of $\Delta$.

######  Remark 3.4.

The orders $\mathcal{O}_{0},\mathcal{O}_{1},...$ are monogenic and thus
satisfy $\mathcal{O}_{n}=\check{\mathcal{O}_{n}}$, as explained in remark 2.4
in page 2.4. For the nonsplit case, $\mathcal{O}_{L}$ is a discrete valuation
ring and the isomorphism follows from the general theory of orders inside
discrete valuation rings.

In the split case, $\mathcal{O}_{L}=\mathcal{O}_{K}\times\mathcal{O}_{K}$ is
not a discrete valuation ring. The isomorphism nevertheless holds by a
standard explicit computation of the isomorphism. Indeed, it can be easily
computed that

$\check{\mathcal{O}_{n}}=\mathcal{O}_{K}\cdot v+\mathcal{O}_{K}\cdot w,$

where

$v=\dfrac{1}{\Delta_{2}-\Delta_{1}}(\Delta_{2},-\Delta_{1}),\;w=\dfrac{p^{-n}}{\Delta_{2}-\Delta_{1}}(1,-1).$

The $\mathcal{O}_{n}-$module isomorphism $R\mathrel{\mathop{\mathchar
58\relax}}\check{\mathcal{O}_{n}}\longrightarrow\mathcal{O}_{n}$ is the one
characterized by

$\displaystyle R(v)$ $\displaystyle=p^{2n}\delta_{\Delta,}$ $\displaystyle
R(w)$ $\displaystyle=p^{n}\Delta.$

We leave the details to the reader.

We aim at finding the explicit polynomials related to the zeta functions of
$\mathcal{O}_{n}$ by proposition 2.5. Let $n\geq 0$ be an integer. By
definition, $\mathcal{O}_{n}$ is a free $\mathcal{O}_{K}-$module of rank $2$.
We get immediately

######  Proposition 3.5.

Let $I\subseteq\mathcal{O}_{n}$ be an ideal of $\mathcal{O}_{n}$. We then have
$I$ is a free $\mathcal{O}_{K}$-module of rank at most $2$. Its
$\mathcal{O}_{K}-$rank is $2$ if and only if
$[\mathcal{O}_{n}\mathrel{\mathop{\mathchar 58\relax}}I]$ is finite.

We use the above proposition to give the following

######  Definition 3.6.

Let $I\subseteq\mathcal{O}_{n}$ be an ideal. We say $I$ is a rank 2 ideal if
its $\mathcal{O}_{K}-$rank is exactly $2$. We denote by $\mathcal{I}_{n}$ the
set of rank 2 ideals of $\mathcal{O}_{n}$.

Notice that the rank $2$ ideals of $\mathcal{O}_{n}$ are precisely the ones
that contribute to the zeta function of $\mathcal{O}_{n}$. We now give the
following

######  Definition 3.7.

For each integer $n\geq 0$, define the map

$T_{n}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{I}_{n}\longrightarrow\mathcal{I}_{n+1},$

by

$T_{n}(J)=pJ.$

We call $T_{n}$ the traveling map.

Due to the facts that $p\mathcal{O}_{n}\subseteq\mathcal{O}_{n+1}$ and that
multiplication by $p$ does not change the $\mathcal{O}_{K}-$rank, we deduce
that the image of $T_{n}$ indeed lies in $\mathcal{I}_{n+1}$. The goal of this
section is to prove that this image consists exactly of the nonprincipal
ideals in $\mathcal{I}_{n+1}$.

The following is straightforward:

######  Proposition 3.8.

For each $n\geq 1$ define $\psi_{n}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}\longrightarrow\mathcal{O}_{K}/p^{n}\mathcal{O}_{K}$
by

$\psi_{n}(x+yp^{n}\Delta)=x\pmod{p^{n}\mathcal{O}_{K}}.$

Then $\psi_{n}$ is a surjective ring homomorphism with kernel
$p^{n}\mathcal{O}_{0}$ which induces an $\mathcal{O}_{n}-$module structure on
$\mathcal{O}_{K}/p^{n}\mathcal{O}_{K}$ given by

$(x+yp^{n}\Delta)\cdot\overline{b}=\psi_{n}(x+yp^{n}\Delta)\overline{b}=\overline{xb},$

where the overline means class in $\mathcal{O}_{K}/p^{n}\mathcal{O}_{K}$.

The first isomorphism theorem now implies

######  Corollary 3.9.

In the context of the previous discussion,

$\dfrac{\mathcal{O}_{n}}{p^{n}\mathcal{O}_{0}}\cong\dfrac{\mathcal{O}_{K}}{p^{n}\mathcal{O}_{K}}.$

Notice the right hand side depends only on $K$ and not on the extension $L$.

Observe that $\mathcal{O}_{i}$ is an $\mathcal{O}_{n}-$module for $0\leq i\leq
n$ with $\mathcal{O}_{n}\subseteq\mathcal{O}_{i}\subseteq\mathcal{O}_{0}$. In
fact there are no others, as we now show.

######  Proposition 3.10.

For $n\geq 0$, the only $\mathcal{O}_{n}-$modules $M$ with

$\mathcal{O}_{n}\subseteq M\subseteq\mathcal{O}_{0}$

are precisely $\mathcal{O}_{0},\mathcal{O}_{1},....,\mathcal{O}_{n}$.

###### Proof.

Let $\varepsilon_{1},\varepsilon_{2}$ be an $\mathcal{O}_{K}$ basis of $M$. We
must have that one of $\\{1,\varepsilon_{1}\\}$ or $\\{1,\varepsilon_{2}\\}$
is also an $\mathcal{O}_{K}$ basis of $M$, because
$1\in\mathcal{O}_{n}\subseteq M$. Say it is $\\{1,\epsilon_{1}\\}$.

Write $\varepsilon_{1}=x+y\Delta$, for some $x,y\in\mathcal{O}_{K}$. Such $x$
and $y$ exist since $M\subseteq\mathcal{O}_{0}=\mathcal{O}_{L}$. It follows
easily that

$M=\mathcal{O}_{K}[p^{k}\Delta],$

where $k=\mbox{val}_{p}(y)$. Furthermore, $0\leq k\leq n$, for otherwise
$p^{n}\Delta\in M$ would not be possible. ∎

We get the following important consequence from the previous proposition.

######  Corollary 3.11.

Let $n\geq 0$ and $\mathcal{O}_{n}\subseteq M\subseteq\mathcal{O}_{0}$ be an
$\mathcal{O}_{n}-$module. Then $M$ is a $\mathcal{O}_{n}-$algebra.

Another easy fact states what the conductor between different orders is. More
concretely, we have the following

######  Proposition 3.12.

The conductor ideal

$(\mathcal{O}_{n+m}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n})\mathrel{\mathop{\mathchar
58\relax}}=\\{z\in\mathcal{O}_{n+m}\;\mid\;z\mathcal{O}_{n}\subseteq\mathcal{O}_{n+m}\\},$

is given by

$(\mathcal{O}_{n+m}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n})=p^{m}\mathcal{O}_{n}.$

In particular, $(\mathcal{O}_{n}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{0})=p^{n}\mathcal{O}_{0}$.

###### Proof.

For $a+bp^{n+m}\Delta$ to satisfy

$(a+bp^{n+m}\Delta)(x+yp^{n}\Delta)\in\mathcal{O}_{n+m},$

for all $x,y\in\mathcal{O}_{K}$, it is enough that it does it for $x=0$ and
$y=1$. In this case we have

$(a+bp^{n+m}\Delta)(p^{n}\Delta)=-bp^{2n+m}\delta_{\Delta}+(ap^{n}+bp^{n+m}\tau_{\Delta})p^{n}\Delta.$

This implies $p^{n+m}|ap^{n}$, which is equivalent to $p^{m}|a$. Writing
$a=p^{m}a_{0}$, we get

$a+bp^{n+m}\Delta=p^{m}(a_{0}+bp^{n}\Delta)\in p^{m}\mathcal{O}_{n},$

as desired. Because all the steps are reversible, the double inclusion holds.
This concludes the proof. ∎

We now study the units of $\mathcal{O}_{n}$. Our aim is to give a
characterization of them that is easy to use and verify.

######  Proposition 3.13.

Let $n\geq 1$. Then $a+bp^{n}\Delta\in\mathcal{O}_{n}$ is a unit of
$\mathcal{O}_{L}$ if and only if $a$ is a unit of $\mathcal{O}_{K}$.

###### Proof.

For $x\in\mathcal{O}_{L}$, we know $x\in\mathcal{O}_{L}^{*}$ if and only if
$N_{L/K}(x)\in\mathcal{O}_{K}^{*}$. From

$N_{L/K}(a+bp^{n}\Delta)=a^{2}+p^{n}ab\tau_{\Delta}+b^{2}p^{2n}\delta_{\Delta},$

we deduce $N_{L/K}(a+bp^{n}\Delta)$ is a unit if and only if $a$ is a unit.
This concludes the proof. ∎

######  Proposition 3.14.

We have $\mathcal{O}_{n}^{*}=\mathcal{O}_{L}^{*}\cap\mathcal{O}_{n}$.

###### Proof.

For $n=0$ this is true because $\mathcal{O}_{0}=\mathcal{O}_{L}$.

For $n\geq 1$, we clearly have
$\mathcal{O}_{n}^{*}\subseteq\mathcal{O}_{L}^{*}\cap\mathcal{O}_{n}$. We need
to prove that if $a+bp^{n}\Delta$ is a unit of $\mathcal{O}_{L}$, then its
inverse also lies in $\mathcal{O}_{n}$. The previous proposition implies $a$
is a unit of $\mathcal{O}_{K}$. If $x+y\Delta$ is the inverse, then from the
product equation

$1=(a+bp^{n}\Delta)(x+y\Delta)=(ax-
bp^{n}y\delta_{\Delta})+(ay+bp^{n}x+bp^{n}y\tau_{\Delta})\Delta,$ (1)

we deduce

$ay+bp^{n}x+bp^{n}y\tau_{\Delta}=0.$

Hence $p^{n}|ay$. We deduce that $p^{n}|y$, because $a$ is a unit. That is,
$x+y\Delta\in\mathcal{O}_{n}$, as desired. ∎

Using the previous result we immediately get the following criterion, which we
will use repeatedly:

######  Theorem 3.15.

Let $n\geq 1$. Then $a+bp^{n}\Delta\in\mathcal{O}_{n}$ is a unit if and only
if $a$ is a unit of $\mathcal{O}_{K}$.

The following definition will become useful later.

######  Definition 3.16.

Let $x\in\mathcal{O}_{0}=\mathcal{O}_{L}$ be any element. We define its type
by

$\varepsilon(x)=\left\\{\begin{array}[]{ll}\mbox{val}_{\pi}(x)&\mbox{in the
nonsplit case }\\\ (\mbox{val}_{p}(x_{1}),\mbox{val}_{p}(x_{2}))&\mbox{in the
split case }\end{array}\right.$

where in the split case we have $x=(x_{1},x_{2})$. We define a possible type
as an element of the image of $\varepsilon$.

We will consider $\varepsilon(x)$ as a vector of one coordinate in the
nonsplit case and of two coordinates in the split case. We now use the
previous definition to give the following

######  Definition 3.17.

Let $I\subseteq\mathcal{O}_{n}$ be an ideal. We say $x\in I$ is a
representative of $I$ if $\varepsilon(x)=\mbox{val}_{\pi}(x)$ is minimal among
$x\in I$ in the nonsplit case, and if

$\displaystyle x_{1}$ $\displaystyle=\min_{(x,y)\in I}(\mbox{val}_{p}(x))$
$\displaystyle x_{2}$ $\displaystyle=\min_{(x,y)\in I}(\mbox{val}_{p}(y))$

in the split case.

The type is registering the valuation at each coordinate of the elements of
$\mathcal{O}_{L}$ as elements of $K$ or $K\times K$. A representative of an
ideal is just an element of the ideal that has minimum possible valuation at
each coordinate simultaneously.

######  Proposition 3.18.

Let $n\geq 0$ and $I\subseteq\mathcal{O}_{n}$ a rank $2$ ideal, then $I$ has a
representative. Furthermore, all its representatives are nonzero divisors of
$\mathcal{O}_{L}$.

###### Proof.

This is obvious in the nonsplit case because
$\varepsilon(x)=\mbox{val}_{\pi}(x)$ takes values in the nonnegative integers.
We now address the split case.

Define $(x_{1},y_{1})\in I$ as one element such that

$x_{1}=\min_{(x,y)\in I}(\mbox{val}_{p}(x)),$

and $(x_{2},y_{2})\in I$ as one element such that

$y_{2}=\min_{(x,y)\in I}(\mbox{val}_{p}(y)).$

Both of these elements exists since, along a single coordinate, minimums of
the valuations exist.

If either of these elements has the other coordinate also a minimum then we
are done. Otherwise we must have

$\mbox{val}_{p}(x_{2})>\mbox{val}_{p}(x_{1}),\mbox{val}_{p}(y_{1})>\mbox{val}_{p}(y_{2}).$

In this situation, define $(x_{0},y_{0})=(x_{1}+x_{2},y_{1}+y_{2})$. Since $I$
is closed under addition, we have $(x_{0},y_{0})\in I$. Furthermore,

$\mbox{val}_{p}(x_{0})=\mbox{val}_{p}(x_{1}+x_{2})=\min(\mbox{val}_{p}(x_{1}),\mbox{val}_{p}(x_{2}))=\mbox{val}_{p}(x_{1})=\min_{(x,y)\in
I}(\mbox{val}_{p}(x)).$

Notice we have used that the equality of the triangle inequality for
valuations happens if the terms involved have different valuations, as is our
case. Analogously,

$\mbox{val}_{p}(y_{0})=\min_{(x,y)\in I}(\mbox{val}_{p}(y)),$

and this proves $(x_{0},y_{0})$ satisfies what we are looking for.

Furthermore, these valuations are nonnegative integers (as opposed to
$\infty$) since otherwise the ideal would have all of its elements with $0$’s
in the same coordinate. This would imply it does not have rank $2$, which
contradicts our choice of $I$. ∎

Now we justify the name representative:

######  Proposition 3.19.

Let $n\geq 0$. For every rank $2$-ideal $I\subseteq\mathcal{O}_{n}$ and every
representative $x\in I$, there exists $0\leq i\leq n$ such that

$I=x\mathcal{O}_{i}.$

Furthermore, $i$ only depends on $I$.

###### Proof.

The argument is the same for both split and nonsplit cases but we only write
it for the split case.

Let $I\in\mathcal{I}_{n}$. The previous proposition implies there is a
representative element $(x_{0},y_{0})\in I$ with

$\displaystyle x_{0}$ $\displaystyle=\min_{(x,y)\in I}(\mbox{val}_{p}(x)),$
$\displaystyle y_{0}$ $\displaystyle=\min_{(x,y)\in I}(\mbox{val}_{p}(y)).$

For any element $(x,y)\in I$ consider

$(z_{1},z_{2})=(xx^{-1}_{0},yy^{-1}_{0}).$

Taking valuations we get

$\displaystyle\mbox{val}_{p}(z_{1})$
$\displaystyle=\mbox{val}_{p}(x)-\mbox{val}_{p}(x_{0})\geq 0,$
$\displaystyle\mbox{val}_{p}(z_{2})$
$\displaystyle=\mbox{val}_{p}(y)-\mbox{val}_{p}(y_{0})\geq 0,$

by definition of $(x_{0},y_{0})$. This implies

$(z_{1},z_{2})\in\mathcal{O}_{0},$

which is the same as saying

$I\subseteq(x_{0},y_{0})\mathcal{O}_{0}.$

Because $I$ is an ideal, we also have

$(x_{0},y_{0})\mathcal{O}_{n}\subseteq I.$

Hence,

$\mathcal{O}_{n}\subseteq(x_{0}^{-1},y_{0}^{-1})I\subseteq\mathcal{O}_{0}.$

Notice we can take the inverses since the entries are nonzero. By proposition
3.10, we deduce there exists a unique $i$, with respect to $(x_{0},y_{0})$,
such that

$(x_{0}^{-1},y_{0}^{-1})I=\mathcal{O}_{i},$

that is, $I=(x_{0},y_{0})\mathcal{O}_{i}$.

If $(x_{1},y_{1})$ and $(x_{2},y_{2})$ are two representatives for the same
ideal with

$I=(x_{1},y_{1})\mathcal{O}_{i}=(x_{2},y_{2})\mathcal{O}_{j}.$

Without loss of generality suppose $i\leq j$. There exists
$o_{i}\in\mathcal{O}_{i}$ and $o_{j}\in\mathcal{O}_{j}$ with

$\displaystyle(x_{1},y_{1})$ $\displaystyle=(x_{2},y_{2})o_{j},$
$\displaystyle(x_{2},y_{2})$ $\displaystyle=(x_{1},y_{1})o_{i}.$

This implies $o_{i}o_{j}=\mathbf{1}$. Since
$\mathcal{O}_{j}\subseteq\mathcal{O}_{i}$ we have $o_{j}\in\mathcal{O}_{i}$,
which means that $o_{j}$ and $o_{i}$ are units of $\mathcal{O}_{i}$. Hence

$I=(x_{1},y_{1})\mathcal{O}_{i}=(x_{2},y_{2})o_{j}\mathcal{O}_{i}=(x_{2},y_{2})\mathcal{O}_{i}.$

This implies $i=j$ for otherwise it contradicts the unicity of the index for
the representative $(x_{2},y_{2})$. ∎

######  Remark 3.20.

The previous proof is classical in the theory of orders within discrete
valuation rings. In the split case, $\mathcal{O}_{L}$ is not a discrete
valuation ring. In order to be able to carry out the argument, we needed to be
able to minimize the valuation entrywise simultaneously. This is why we need
the existence of representatives, guaranteed by proposition 3.18 above.

We are now in position to prove the main structural result of the ideals in
the main sequence of orders.

######  Proposition 3.21.

Let $n\geq 1$ and $I\in\mathcal{I}_{n}$ be a nonprincipal ideal. Then there
exists a unique ideal $J\in\mathcal{I}_{n-1}$ such that $I=pJ$.

###### Proof.

Let $I\in\mathcal{I}_{n}$ be a nonprincipal ideal. By proposition 3.19, we
have $I=x\mathcal{O}_{i}$ for some representative $x\in I$ and a unique $0\leq
i\leq n$. We know $i<n$, because $I$ is nonprincipal. In particular, since

$x\mathcal{O}_{i}\subseteq\mathcal{O}_{n},$

$x$ lies in the conductor $(\mathcal{O}_{n}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{i})$. By proposition 3.12, we know
$(\mathcal{O}_{n}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{i})=p^{n-i}O_{i}$. Write $x=p^{n-i}y$, for some
$y\in\mathcal{O}_{i}$. Substituting this in the expression of $I$, we get

$I=x\mathcal{O}_{i}=p(p^{n-i-1}y\mathcal{O}_{i}).$

Let $J\mathrel{\mathop{\mathchar 58\relax}}=(p^{n-i-1}y\mathcal{O}_{i})$.
Every ideal of $\mathcal{O}_{i}$ that lies in $\mathcal{O}_{n-1}$ is also an
ideal of $\mathcal{O}_{n-1}$. This implies $J$ is an
$\mathcal{O}_{n-1}$-ideal. This concludes the proof of the existence. To
notice it is unique, realize that $J=p^{-1}I$, which as a set is uniquely
determined by $I$. ∎

From all above we immediately deduce

######  Theorem 3.22.

The traveling map $T_{n}$ is a bijection onto its image, which consists
exactly of the nonprincipal rank $2$ ideals in $\mathcal{I}_{n+1}$.

##  4 Study of the Principal Part

We begin by giving the following

######  Definition 4.1.

For $n\geq 0$ we define the zeta function of the order $\mathcal{O}_{n}$,
following definition 2.3 in page 2.3, by

$\zeta_{n}(s)\mathrel{\mathop{\mathchar
58\relax}}=\displaystyle\sum_{I\subseteq\mathcal{O}_{n}}\dfrac{1}{[\mathcal{O}_{n}\mathrel{\mathop{\mathchar
58\relax}}I]^{s}},$

where the sum runs over all ideals $I\subseteq\mathcal{O}_{n}$ of finite
index, that is, over the ideals in $\mathcal{I}_{n}$.

Furthermore, we denote by $\mathfrak{P}_{n}$ the set of principal ideals in
$\mathcal{I}_{n}$ and define

$\zeta_{n}^{P}(s)\mathrel{\mathop{\mathchar
58\relax}}=\displaystyle\sum_{I\in\mathfrak{P}_{n}}\dfrac{1}{[\mathcal{O}_{n}\mathrel{\mathop{\mathchar
58\relax}}I]^{s}},$

which we call the principal part of $\zeta_{n}(s)$.

The purpose of the traveling map is to isolate the principal part of
$\zeta_{n}$ away from the zeta function $\zeta_{n-1}$. More precisely, we have

######  Theorem 4.2.

For $n\geq 1$, the zeta functions of the orders $\mathcal{O}_{n}$ satisfy the
recurrence relation

$\zeta_{n}(s)=\zeta_{n}^{P}(s)+q^{-s}\zeta_{n-1}(s).$

###### Proof.

It is clear that

$\zeta_{n}(s)=\zeta_{n}^{P}(s)+\zeta^{i}_{n}(s),$

where we define

$\zeta^{i}_{n}(s)\mathrel{\mathop{\mathchar
58\relax}}=\displaystyle\sum_{I\notin\mathfrak{P}_{n}}\dfrac{1}{[\mathcal{O}_{n}\mathrel{\mathop{\mathchar
58\relax}}I]^{s}}.$

If $J\subseteq\mathcal{O}_{n-1}$ then
$pJ\subseteq\mathcal{O}_{n}\subseteq\mathcal{O}_{n-1}$ and $pJ\subseteq
J\subseteq\mathcal{O}_{n-1}$. Using the tower theorem for indices we get

$[\mathcal{O}_{n}\mathrel{\mathop{\mathchar
58\relax}}pJ]=\dfrac{[\mathcal{O}_{n-1}\mathrel{\mathop{\mathchar
58\relax}}pJ]}{[\mathcal{O}_{n-1}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}]}=\dfrac{[\mathcal{O}_{n-1}\mathrel{\mathop{\mathchar
58\relax}}J][J\mathrel{\mathop{\mathchar
58\relax}}pJ]}{[\mathcal{O}_{n-1}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}]}$

We know that $[J\mathrel{\mathop{\mathchar 58\relax}}pJ]=q^{2}$ and
$[\mathcal{O}_{n-1}\mathrel{\mathop{\mathchar 58\relax}}\mathcal{O}_{n}]=q$.
Both of these equalities follow from elementary divisor theory. We then deduce

$\zeta^{i}_{n}(s)=\displaystyle\sum_{I\notin\mathfrak{P}_{n}}\dfrac{1}{[\mathcal{O}_{n}\mathrel{\mathop{\mathchar
58\relax}}I]^{s}}=\displaystyle\sum_{J\subseteq\mathcal{O}_{n-1}}\dfrac{1}{q^{s}[\mathcal{O}_{n-1}\mathrel{\mathop{\mathchar
58\relax}}J]^{s}}=q^{-s}\zeta_{n-1}(s),$

where we used the traveling map in the second equality. ∎

With this at hand the challenge becomes to find a usable expression for the
principal part. In this direction we introduce the following

######  Definition 4.3.

For $I\in\mathfrak{P}_{n}$ we denote by

$R(I)\mathrel{\mathop{\mathchar
58\relax}}=\\{\alpha\in\mathcal{O}_{n}\;\mid\;\alpha\mathcal{O}_{n}=I\\},$

its set of representatives.

We will organize ideals by the type their representatives have. Because
different representatives of an ideal differ by a unit, we immediately get

######  Proposition 4.4.

For $I\in\mathfrak{P}_{n}$ and $\alpha\in R(I)$, the type of
$\varepsilon(\alpha)$ is independent of $\alpha$.

We now enhance the definition 3.16 of type, given in page 3.16 above, to also
apply for ideals in $\mathfrak{P}_{n}$. We have

######  Definition 4.5.

Let $I\in\mathfrak{P}_{n}$. We define the type of $I$ by

$\varepsilon(I)\mathrel{\mathop{\mathchar 58\relax}}=\varepsilon(x),$

for any $x\in R(I)$. We also define for every $x\in\mathcal{O}_{L}$

$\eta(x)=\min\\{\mbox{val}_{p}(a)\mid a\mbox{ is a coordinate of
}\varepsilon(x)\\},$

and write $\eta(I)=\eta(x)$ for any $x\in R(I)$. Notice that proposition 4.4
implies these definitions are well defined.

We now divide principal ideals into two different classes, in which the
contribution to the zeta function is similar but not quite the same. We have

######  Definition 4.6.

Let $\omega$ be a possible type. In the nonsplit case, we say $\omega$ is a
low type if $\omega<ne$. In the split case, we say
$\omega=(\omega_{1},\omega_{2})$ is a low type if $\omega_{1}<n$ or
$\omega_{2}<n$. Otherwise, we say $\omega$ is a high type.

######  Definition 4.7.

Let $I\in\mathfrak{P}_{n}$. We say $I$ is a low ideal if $\varepsilon(I)$ is a
low type. That is, if

$\eta(I)<\left\\{\begin{array}[]{ll}ne&\mbox{in the nonsplit case, }\\\
n&\mbox{in the split case. }\end{array}\right.$

Otherwise, we say $I$ is a high ideal. We will refer to $ne$ and $n$,
respectively in the nonsplit and split cases, as the ideal threshold and
denote if uniformly by $t_{n}$.

The role of low and high ideals will become clearer as we move forward. For
the moment, let us only say that high ideals contribute in all possible ways
available, while low ideals have a more restricted contribution to the
principal part of the zeta function.

We begin by showing what is the contribution of each ideal in
$\mathfrak{P}_{n}$. We have the following

######  Definition 4.8.

Let $\omega$ be a possible type of an ideal in $\mathfrak{P}_{n}$. We define
its  type contribution as

$c(\omega)\mathrel{\mathop{\mathchar
58\relax}}=\left\\{\begin{array}[]{ll}f\omega&\mbox{in the nonsplit case, }\\\
\omega_{1}+\omega_{2}&\mbox{in the split case. }\end{array}\right.$

In here we are denoting $\omega=(\omega_{1},\omega_{2})$ in the split case,
where the possible types are pairs of nonnegative integers.

With this definition, the following becomes a straightforward application of
the tower theorem for indices. We leave the details to the reader.

######  Proposition 4.9.

Let $I\in\mathfrak{P}_{n}$. The index
$[\mathcal{O}_{n}\mathrel{\mathop{\mathchar 58\relax}}I]$ is given by

$[\mathcal{O}_{n}\mathrel{\mathop{\mathchar
58\relax}}I]=q^{-c(\varepsilon(I))}.$

Let $\omega$ be a possible type. In the nonsplit case $\omega$ is a
nonnegative integer, while in the split case it is a pair of nonnegative
integers. We define

$X_{\omega}\mathrel{\mathop{\mathchar
58\relax}}=\\{I\in\mathfrak{P}_{n}\mid\;\varepsilon(I)=\omega\\}.$

Each ideal in $X_{\omega}$ contributes the same to the zeta function and
grouping these terms together we deduce the principal part of the zeta
function is

$\zeta_{n}^{P}(s)=\displaystyle\sum_{\omega}\dfrac{|X_{\omega}|}{q^{c(\omega)}}.$

The success of our analysis depends on whether we are able to compute the
$|X_{\omega}|$ or not.

The first step is to deal with the high types. The following proposition
explains why this distinction is important.

######  Proposition 4.10.

Let $x\in\mathcal{O}_{0}=\mathcal{O}_{L}$ be any element with $\eta(x)\geq
t_{n}$, then $x\in\mathcal{O}_{n}$.

###### Proof.

Let $x\in\mathcal{O}_{0}$ with $\eta(x)\geq t_{n}$. We claim $x$ is a multiple
of $p^{n}$ in $\mathcal{O}_{0}$.

In the nonsplit case, $\mbox{val}_{\pi}(x)=\eta(x)\geq ne$. This implies

$x=\pi^{\mbox{val}_{\pi}(x)}u=\pi^{ne}\pi^{\mbox{val}_{\pi}(x)-ne}u=p^{n}\left(\pi^{\mbox{val}_{\pi}(x)-ne}u\right),$

for some unit $u\in\mathcal{O}_{L}$. On the other hand, for the split case

$x=(x_{1},x_{2})=(p^{\mbox{val}_{p}(x_{1})}u_{1},p^{\mbox{val}_{p}(x_{2})}u_{2})=p^{n}(p^{\mbox{val}_{p}(x_{1})-n}u_{1},p^{\mbox{val}_{p}(x_{2})-n}u_{2}).$

for some unit $u_{1},u_{2}\in\mathcal{O}_{K}$. In any case, we conclude

$x\in p^{n}\mathcal{O}_{0}=(\mathcal{O}_{0}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n})\subseteq\mathcal{O}_{n},$

proving that $x\in\mathcal{O}_{n}$. ∎

We now define, for every possible type $\omega$,

$\mathcal{O}_{n}^{[\omega]}\mathrel{\mathop{\mathchar
58\relax}}=\displaystyle\bigsqcup_{\varepsilon(I)=\omega}R(I),$

that is, the set of all representatives of principal ideals in
$\mathfrak{P}_{n}$ that contribute $q^{-c(\omega)}$ to the principal part of
the zeta function. The previous proposition implies that if $\omega$ is a high
type, then

$\mathcal{O}_{n}^{[\omega]}=\left\\{x\in\mathcal{O}_{0}\;|\;\varepsilon(x)=\omega\right\\}.$

In particular, $\mathcal{O}_{n}^{[\omega]}\neq\emptyset$, that is, for high
types there must be high ideals of type $\omega$. This is what we meant when
we said above that high ideals contribute in all possible ways available. The
next proposition is now evident and states explicitly how many such ideals
there are:

######  Proposition 4.11.

Let $\omega$ be a high type. Define the map
$\Psi_{\omega}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{[\omega]}\longrightarrow\mathcal{O}_{L}^{*}$ given
by

$\Psi_{\omega}(x)=\pi^{-\omega}x$

in the nonsplit case and by

$\Psi_{\omega}(x_{1},x_{2})=(p^{-\omega_{1}}x_{1},p^{-\omega_{2}}x_{2})$

in the split case. Then $\Psi_{\omega}$ is an
$\mathcal{O}_{n}^{*}$-equivariant isomorphism.

In here, $\mathcal{O}_{n}^{[\omega]}$ and $\mathcal{O}_{L}^{*}$ are equipped
with the natural actions of $\mathcal{O}_{n}^{*}$ by left multiplication. As a
consequence, the orbits of one are in correspondence with the orbits of the
other, and so

$|X_{\omega}|=[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{*}].$

This puts in solid ground the contribution of the high ideals. We now have to
deal with the low ideals, which is a similar analysis, but we have to find how
to deal with the fact that proposition 4.10 is no longer true. The first step
to do this is the following

######  Proposition 4.12.

Let $I\in\mathfrak{P}_{n}$ be a low ideal and $x+yp^{n}\Delta\in R(I)$ a
representative. Then $\mbox{val}_{p}(x)$ is independent of the representative
of $I$ chosen and, furthermore, its value is smaller than $n$ and is equal to
$\mbox{val}_{p}(a)$ for every coordinate of $\varepsilon(I)$.

###### Proof.

We will only do the computations for the split case as the nonsplit case is
analogous. Realize there are no low ideals for $n=0$, so we may assume $n\geq
1$.

For the split case pick $\alpha\in R(I)$, say
$\alpha=(\alpha_{1},\alpha_{2})$, and put $\varepsilon(I)=(l,m)$. Since $I$ is
low one of $l$ or $m$ is smaller than $n$. Without loss of generality suppose
$l<n$.

Write $\alpha=a\cdot\mathbf{1}+b\cdot(p^{n}\Delta)$, for some
$a,b\in\mathcal{O}_{K}$ which in coordinates becomes

$\alpha_{1}=a+bp^{n}\Delta_{1},\alpha_{2}=a+bp^{n}\Delta_{2}.$

Suppose $\mbox{val}_{p}(a)\geq n$. Then

$l=\mbox{val}_{p}(a+bp^{n}\Delta_{1})\geq\min(\mbox{val}_{p}(a),n+\mbox{val}_{p}(b\Delta_{1}))\geq
n,$

which is a contradiction. We conclude $t\mathrel{\mathop{\mathchar
58\relax}}=\mbox{val}_{p}(a)<n$, say $a=p^{t}u$ for some unit
$u\in\mathcal{O}_{K}$. Then, for $i=1,2$,

$\alpha_{i}=p^{t}u+bp^{n}\Delta_{i}=p^{t}(u+bp^{n-t}\Delta_{i}),$

and because $n-t>0$ we have $bp^{n-t}\Delta_{i}$ is not a unit of
$\mathcal{O}_{K}$, and since $u$ is, then $u+bp^{n-t}\Delta_{i}$ is also a
unit. We conclude, $\mbox{val}_{p}(\alpha_{i})=t=\mbox{val}_{p}(a)$, which
proves independence, equality of entries and its value smaller than $n$, as
desired.

∎

Due to this proposition we can make the following

######  Definition 4.13.

Let $I\in\mathfrak{P}_{n}$ a low ideal. The common value of
$\mbox{val}_{p}(x)$ for all the $x+yp^{n}\Delta\in R(I)$ is denoted by
$\eta_{p}(I)$.

As a consequence, contrary to the high types, we have that not all low types
contribute to the zeta function. More precisely, we have

######  Proposition 4.14.

Let $I\in\mathfrak{P}_{n}$ be a low ideal. Then, in the nonsplit case, we have

$\eta(I)=e\eta_{p}(I),$

and so the only possible types for low ideals are $0,e,2e,...,(n-1)e$. On the
other hand, for the split case

$\varepsilon(I)=(\eta_{p}(I),\eta_{p}(I)),$

and so the only possible types for low ideals are $(0,0),(1,1),...,(n-1,n-1)$.

###### Proof.

For the split case we have for $x+yp^{n}\Delta\in R(I)$ with $x=p^{t}u$ and
$u\in\mathcal{O}_{K}^{*}$ that

$\eta(I)=\mbox{val}_{\pi}(x+yp^{n}\Delta)=\mbox{val}_{\pi}(p^{t}(u+yp^{n-t}\Delta))=t\mbox{val}_{\pi}(p)=te,$

as desired. Notice that for the last equality we have used that $t<n$, by the
previous proposition, and hence that $u+yp^{n-t}\Delta$ is a unit of
$\mathcal{O}_{L}$. This implies that the possible types of low ideals, which
are precisely the values of $\varepsilon(I)=\eta(I)$, can only be the
multiples of $e$ from $0$ to $(n-1)e$.

For the split case, the previous proposition implies the entries of
$\varepsilon(I)$ are equal and smaller than $n$. Hence, the possible types are
$(0,0),...,(n-1,n-1)$, as claimed.

∎

Notice in both cases we have a linear behaviour for the types of low ideals,
which is a remarkable fact for the split case since, a priori, there are
several other possible low types that end up never appearing. Similar to
proposition 4.11, we now have a group action for the low types:

######  Proposition 4.15.

Let $\omega$ be one of the types of the previous proposition (i.e. the
possible ones for low ideals). Define $\Psi_{\omega}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{[\omega]}\longrightarrow\mathcal{O}_{n-d}^{*}$ by

$\Psi_{\omega}(x)=p^{-d}x.$

where $d=\eta(\omega)/e$ in the nonsplit case and $d=\eta(\omega)$ in the
split case. Then $\Psi$ is a $\mathcal{O}_{n}^{*}$-equivariant isomorphism
between the $\mathcal{O}_{n}^{*}$-spaces $\mathcal{O}_{n}^{[\omega]}$ and
$\mathcal{O}_{n-d}^{*}$, where in both spaces the action is by left
multiplication. As a consequence, we have

$|X_{\omega}|=[\mathcal{O}_{n-d}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{*}]=\dfrac{[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{*}]}{[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n-d}^{*}]}$

###### Proof.

For the nonsplit case, an ideal $I$ whose representatives have
$\eta(I)=\omega$ satisfies

$\eta(I)=de,\eta_{p}(I)=d.$

On the other hand, for the split case we have $\varepsilon(x)=(d,d)$. Hence,
in both cases, we can write any representative as

$p^{d}u+yp^{n}\Delta,$

for some unit $u\in\mathcal{O}_{K}^{*}$. Since $d<n$ we can factor the $p^{d}$
and get

$p^{d}(u+yp^{n-d}\Delta),$

and since $u$ is a unit of $\mathcal{O}_{K}$, then $u+yp^{n-d}$ is a unit of
$\mathcal{O}_{n-d}$. Since all of these steps are reversible, we get that
$\Psi_{d}(\mathcal{O}_{n}^{[\omega]})=\mathcal{O}_{n-d}^{*}$.

That it is equivariant is immediate and that all orbits count follows from the
fact that the representatives are nondivisors of $0$ and we can appeal to
proposition 4.9.

∎

Now we are ready to prove the main result of this section, which is the
following

######  Proposition 4.16.

The principal part of the zeta functions of the orders $\mathcal{O}_{n}$
satisfies

$\zeta_{n}^{P}(s)=\displaystyle\sum_{d=0}^{n-1}\dfrac{[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{*}]}{[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n-d}^{*}]}\cdot\dfrac{1}{q^{2ds}}+\dfrac{[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{*}]}{q^{2ns}V(s)}.$

In here $V(s)$ is the factor appearing in proposition 2.5 on page 2.5.

###### Proof.

Collecting the contributions of both high and low ideals we will obtain this
result. For the nonsplit case the high ideals contribute

$\displaystyle\sum_{j\geq
0}\dfrac{|X_{ne+j}|}{q^{f(ne+j)s}}=\displaystyle\sum_{j\geq
0}\dfrac{[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{*}]}{q^{2ns+fjs}}=\dfrac{[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{*}]}{q^{2ns}(1-q^{-fs})}.$

For the low ideals we only get contributions for $0,e,...,(n-1)e$, and for
each one of them we have $|X_{de}|$ such terms. Hence, we obtain the low
ideals contribute

$\displaystyle\sum_{d=0}^{n-1}\dfrac{|X_{de}|}{q^{f(de)s}}=\displaystyle\sum_{d=0}^{n-1}\dfrac{|X_{de}|}{q^{2ds}}=\displaystyle\sum_{d=0}^{n-1}\dfrac{[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{*}]}{[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n-d}^{*}]}\cdot\dfrac{1}{q^{2ds}}$

Notice that we have used $fe=2$. On the other hand, for the high ideals in the
split case, we get

$\displaystyle\sum_{\eta(I)\geq
n}\dfrac{1}{[\mathcal{O}_{n}\mathrel{\mathop{\mathchar
58\relax}}I]^{s}}=\displaystyle\sum_{l,m\geq
n}\displaystyle\sum_{\varepsilon(I)=(l,m)}\dfrac{1}{[\mathcal{O}_{n}\mathrel{\mathop{\mathchar
58\relax}}I]^{s}}=\dfrac{[\mathcal{O}_{L}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{*}]}{q^{2ns}}\displaystyle\sum_{i,j\geq
0}\dfrac{1}{q^{(i+j)s}}=\dfrac{[\mathcal{O}_{L}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{*}]}{q^{2ns}(1-q^{-s})^{2}}.$

For the low ideals we have the possible types are only $(0,0),...,(n-1,n-1)$.
Hence, the contribution is

$\displaystyle\sum_{d=0}^{n-1}\dfrac{|X_{(d,d)}|}{q^{(d+d)s}}=\displaystyle\sum_{d=0}^{n-1}\dfrac{|X_{(d,d)}|}{q^{2ds}}=\displaystyle\sum_{d=0}^{n-1}\dfrac{[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{*}]}{[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n-d}^{*}]}\cdot\dfrac{1}{q^{2ds}}.$

Finally, by inspection of the two cases, we see $V(s)$ coincides with
$(1-q^{-fs})$ in the nonsplit case and with $(1-q^{-s})^{2}$ in the split one.
∎

##  5 Solution of the Recurrence

We have seen that the principal part depends on the indices
$[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{*}]$. We now compute the values of these indices.

The following formula is classical in the general theory of orders but in the
case we are is particularly simple, since we do not have to deal with class
numbers. We refer the reader to [10] (see theorems 11 and 12 in chapter 1,
section 12) or [12] to see a proof of the general case which implies our case
(the proof also works in the split case).

######  Proposition 5.1.

The following formula holds

$[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{*}]=\dfrac{\mathinner{\\!\left\lvert\left(\nicefrac{{\mathcal{O}_{0}}}{{p^{n}\mathcal{O}_{0}}}\right)^{*}\right\rvert}}{\mathinner{\\!\left\lvert\left(\nicefrac{{\mathcal{O}_{n}}}{{p^{n}\mathcal{O}_{0}}}\right)^{*}\right\rvert}}$

We have now reached the point where it is desirable to make the distinction
between the two possible nonsplit cases.

######  Proposition 5.2.

The indices of the units subgroups satisfy for $n\geq 1$,

$[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{*}]=\left\\{\begin{array}[]{ll}q^{n}&\mbox{in the
ramified case,}\\\ (q+1)q^{n-1}&\mbox{in the unramified case,}\\\
(q-1)q^{n-1}&\mbox{in the split case.}\\\ \end{array}\right.$

And, of course, $[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{0}^{*}]=1$.

###### Proof.

All the computations are analogous so we only show the nonsplit case so that
we can notice clearly how the ramification $e$ and intertia $f$ play a role.

We have that
$\nicefrac{{\mathcal{O}_{0}}}{{p^{n}\mathcal{O}_{0}}}=\nicefrac{{\mathcal{O}_{L}}}{{\pi^{ne}\mathcal{O}_{L}}}$,
and we have the well known isomorphisms

$\displaystyle\left(\nicefrac{{\mathcal{O}_{L}}}{{\pi^{ne}\mathcal{O}_{L}}}\right)^{*}$
$\displaystyle\cong\nicefrac{{\mathcal{O}_{L}^{*}}}{{U^{(ne)}_{L}}},$
/UL(m)U(m + 1)L
$\displaystyle\cong\nicefrac{{\mathcal{O}_{L}}}{{\pi\mathcal{O}_{L}}},m\geq
1,$

where $U_{L}^{(m)}$ are the higher unit groups. Furthermore, we also know that
$O_{L}^{*}=\mu_{Q-1}\times U^{(1)}_{L}$, where $\mu_{Q-1}$ is the group of
$(Q-1)$ roots of unity. From this we get

$\nicefrac{{\mathcal{O}_{L}^{*}}}{{U_{L}^{(1)}}}\cong\mu_{Q-1}.$

Now we can iterate and obtain

$\mathinner{\\!\left\lvert\left(\nicefrac{{\mathcal{O}_{L}}}{{\pi^{ne}\mathcal{O}_{L}}}\right)^{*}\right\rvert}=\mathinner{\\!\left\lvert\nicefrac{{\mathcal{O}_{L}^{*}}}{{U^{(ne)}_{L}}}\right\rvert}=\mathinner{\\!\left\lvert\nicefrac{{\mathcal{O}_{L}^{*}}}{{U^{(1)}_{L}}}\right\rvert}\mathinner{\\!\left\lvert\nicefrac{{U_{L}^{(1)}}}{{U^{(2)}_{L}}}\right\rvert}\cdots\mathinner{\\!\left\lvert\nicefrac{{U_{L}^{(ne-1)}}}{{U^{(ne)}_{L}}}\right\rvert}=(Q-1)Q^{ne-1}.$

Corollary 3.9 on page 3.9 states

$\nicefrac{{\mathcal{O}_{n}}}{{p^{n}\mathcal{O}_{0}}}\cong\nicefrac{{\mathcal{O}_{K}}}{{p^{n}\mathcal{O}_{K}}}.$

Hence,

$\left(\nicefrac{{\mathcal{O}_{n}}}{{p^{n}\mathcal{O}_{0}}}\right)^{*}\cong\left(\nicefrac{{\mathcal{O}_{K}}}{{p^{n}\mathcal{O}_{K}}}\right)^{*}.$

By the same iterative argument we thus conclude

$\mathinner{\\!\left\lvert\left(\nicefrac{{\mathcal{O}_{n}}}{{p^{n}\mathcal{O}_{n}}}\right)^{*}\right\rvert}=(q-1)q^{n-1}.$

Now we specialize in each of the cases we have:

Ramified, $f=1$:

Then $e=2$ and, using the previous proposition result, and recalling
$Q=q^{f}=q$, we get

$[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{*}]=\dfrac{(Q-1)Q^{2n-1}}{(q-1)q^{n-1}}=\dfrac{(q-1)q^{2n-1}}{(q-1)q^{n-1}}=q^{n},$

and notice that this same formula works if $n=0$.

Unamified, $f=2$:

In this situation $Q=q^{2}$ and $e=1$, then

$[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{*}]=\dfrac{(Q-1)Q^{n-1}}{(q-1)q^{n-1}}=\dfrac{(q^{2}-1)q^{2(n-1)}}{(q-1)q^{n-1}}=(q+1)q^{n-1}.$

This concludes the proof. ∎

We have found before that the recurrence relation in each case is

$\zeta_{n}(s)=\zeta_{n}^{P}(s)+q^{-s}\zeta_{n-1}(s).$

We are now ready to solve this equations explicitly. We begin by finding the
initial condition:

######  Proposition 5.3.

The zeta function of the order $\mathcal{O}_{0}=\mathcal{O}_{L}$ is in the
nonsplit case

$\zeta_{0}(s)=\dfrac{1}{1-q^{-fs}},$

and

$\zeta_{0}(s)=\dfrac{1}{(1-q^{-s})^{2}}.$

in the split case. In particular, in each case, $\zeta_{0}(s)=V(s)^{-1}$,
where $V(s)$ is the factor appearing in proposition 2.5 at page 2.5.

###### Proof.

We know that for $n=0$ all ideals are high. We have computed before, in the
proof of proposition 4.16 on page 4.16, that the high ideals contribute
$\dfrac{[\mathcal{O}_{0}^{*}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{O}_{n}^{*}]}{q^{2ns}V(s)}$. In our present case this means

$\zeta_{0}(s)=\zeta_{0}^{P}(s)=\dfrac{1}{V(s)},$

and $V(s)$ is $1-q^{-fs}$ for the nonsplit case and $(1-q^{-s})^{2}$ for the
split one. ∎

We finally get

######  Theorem 5.4.

For each $n\geq 0$ define the following polynomials:

$\displaystyle R_{n}(X)$ $\displaystyle=1+qX^{2}+q^{2}X^{4}+...+q^{n}X^{2n},$

and for $n\geq 1$ define

$\displaystyle U_{n}(X)$ $\displaystyle=(1+X)R_{n-1}(X)+q^{n}X^{2n},$
$\displaystyle S_{n}(X)$ $\displaystyle=(1-X)R_{n-1}(X)+q^{n}X^{2n}.$

Finally, also put $U_{0}(X)=S_{0}(X)=1$. Explicitly, these polynomials are

$\displaystyle R_{n}(X)$ $\displaystyle=1+qX^{2}+q^{2}X^{4}+...+q^{n}X^{2n},$
$\displaystyle U_{n}(X)$
$\displaystyle=1+X+qX^{2}+qX^{3}+...+q^{n-1}X^{2n-2}+q^{n-1}X^{2n-1}+q^{n}X^{2n},$
$\displaystyle S_{n}(X)$
$\displaystyle=1-X+qX^{2}-qX^{3}+...+q^{n-1}X^{2n-2}-q^{n-1}X^{2n-1}+q^{n}X^{2n}.$

Then the solution of the ramified, unramified and split case recurrence,
respectively, satisfy

$\displaystyle(1-q^{-s})\zeta_{n}(s)$ $\displaystyle=R_{n}(q^{-s}),$
$\displaystyle(1-q^{-2s})\zeta_{n}(s)$ $\displaystyle=U_{n}(q^{-s}),$
$\displaystyle(1-q^{-s})^{2}\zeta_{n}(s)$ $\displaystyle=S_{n}(q^{-s}).$

###### Proof.

The three cases are solved by induction using as base case the initial
condition given in the previous proposition. We omit the details as they are
straightforward. ∎

## References

  * [1] Arthur, J. A stratification related to characteristic polynomials.  Advances in Mathematics 327 (2018), 425–469.
  * [2] Bushnell, C. J., and Reiner, I. Zeta functions of arithmetic orders and solomon’s conjecture.  Mathematische Zeitschrift 173 (1980), 135–162.
  * [3] Bushnell, C. J., and Reiner, I. Functional equations for l-functions of arithmetic orders.  88–124.
  * [4] Bushnell, C. J., and Reiner, I. L-functions of arithmetic orders and asymptotic distribution of ideals.  156–183.
  * [5] Espinosa, M. Multiplicative formula of Langlands for orbital integrals in ${GL}(2)$.  submitted (2022).
  * [6] Ibukiyama, T. Genus character $l$-functions of quadratic orders in an adelic way and maximal orders of matrix algebras, 2023.
  * [7] Kaneko, M. On the local factor of the zeta function of quadratic orders.  In Zeta Functions, Topology and Quantum Physics (Boston, MA, 2005), T. Aoki, S. Kanemitsu, M. Nakahara, and Y. Ohno, Eds., Springer US, pp. 75–79.
  * [8] Kaneko, M., and Mizuno, Y. Genus character l-functions of quadratic orders and class numbers.  Journal of the London Mathematical Society 102, 1 (2020), 69–98.
  * [9] Langlands, R. P. Beyond endoscopy.  In Contributions to automorphic forms, geometry, and number theory. Johns Hopkins Univ. Press, Baltimore, MD, 2004, pp. 611–697.
  * [10] Neukirch, J. Algebraic number theory, vol. 322 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences].  Springer-Verlag, Berlin, 1999.
  * [11] Saikia, P. K. Zeta functions of orders on quadratic fields.  Proceedings of the Indian Academy of Sciences - Mathematical Sciences 98 1 (1988), 31–42.
  * [12] Sands, J. Generalization of a theorem of siegel.  Acta Arithmetica 58, 1 (1991), 47–57.
  * [13] Solomon, L. Zeta functions and integral representation theory.  Advances in Mathematics 26 (1977), 306–326.
  * [14] Yun, Z. Orbital integrals and dedekind zeta functions.  Ramanujan Mathematical Society Lecture Notes 20 (2013), 399 – 420.
  * [15] Zagier, D. Modular forms whose fourier coefficients involve zeta-functions of quadratic fields.  In Modular Functions of One Variable VI (Berlin, Heidelberg, 1977), J.-P. Serre and D. B. Zagier, Eds., Springer Berlin Heidelberg, pp. 105–169.


# dAIrector: Automatic Story Beat Generation
through Knowledge Synthesis

Markus Eger1 and Kory W. Mathewson2,3
1NC State University, Raleigh, NC, USA
2University of Alberta, Edmonton, Alberta, Canada
3HumanMachine, London, United Kingdom
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

dAIrector is an automated director which collaborates with humans storytellers
for live improvisational performances and writing assistance. dAIrector can be
used to create short narrative arcs through contextual plot generation. In
this work, we present the system architecture, a quantitative evaluation of
design choices, and a case-study usage of the system which provides
qualitative feedback from a professional improvisational performer. We present
relevant metrics for the understudied domain of human-machine creative
generation, specifically long-form narrative creation. We include, alongside
publication, open-source code so that others may test, evaluate, and run the
dAIrector.

##  1 Introduction

Improvisational theatre (improv) is an art form in which narratives are
developed ad-hoc in front of a live audience [Joh79]. Performers are prompted
with a concise, ambiguous suggestion (e.g. a location or character
relationship) and then share narrative development through action and
dialogue. Often these prompts are provided by the audience throughout a
performance. The most interesting challenge of improvisation is incorporating
new suggestions, seemingly unrelated to the narrative. Improvisation’s live
justification has been proposed as a model for real-time dynamic problem
solving [M+09, Ste11]. Improv has been proposed as a grand challenge for
machine learning systems [MHR16] potentially as an extension to the Turing
Test [Tur50, MM17a]. The dAIrector collaborates with human improvisors for
semi-automated story beat generation, suitable for improvisation performance,
through knowledge graph synthesis. First, we describe some background on story
generation, improvisational theatre, and plot graphs (from Plotto and TV
Tropes). Then, we describe our approach and present quantitative and
qualitative evaluation. We conclude with discussion of limitations and future
work.

##  2 Background and Related Work

###  2.1 Automated Story Generation

The research problem of automated story generation (ASG) is concerned with
generating a sequence which collectively form a narrative [Mee76, Coo28]. The
sequence can be composed of abstract concepts such as events or actions, or
concrete text-based elements such as paragraphs, sentences, words, or
characters. Different levels of abstraction and concreteness are accompanied
by different challenges. For instance, stories defined at high levels of
abstraction maintain step-to-step coherence easier but are simplified and lack
unique, specific details.

Previous ASG systems have used symbolic planning and extensive hand-
engineering [RY10]. Open story generation systems use machine learning
techniques to learn representations of the domain from the training data and
incorporate knowledge from an external corpus [LLUJR13]. Martin et al.
[MAW+17] address the abstraction level challenges by using recurrent neural
networks (RNNs) and an event representation to provide a level of abstraction
between words and sentences capable of modelling narrative over hundreds of
steps. They provide a method of pre-processing textual data into event
sequences and then evaluate their event-to-event and event-to-sentence models.
Our methods are distinct from this technique as we do not focus on the problem
of sentence generation from words or characters. The dAIrector embraces human
co-creators to provide dialog for given plot point descriptions and context.

Narrative generation approaches, such as TALESPIN [Mee77], focus on actions,
their effects, and element relationships to delineate character intentions
[RY10] and conflict [WY11] which ultimately leads to satisfying an author
defined goal. Alternatively, there may be no predefined goal, and systems may
discover actions autonomously [TFNH03], ideally resulting in an interesting
story. To produce an interesting story in the context of improv theater,
however, the prescription of actions (e.g. lines of dialog, character choices,
stage directions) is less desirable. A description of a situation suffices to
inspire actors who can then translate the prompt into actions, with vague and
ambiguous prompts giving the actors freedom to explore the scene [Saw03].

###  2.2 Digital Storytelling

The ad-hoc storytelling experience present in improv theater has been used for
research into digital storytelling for more than two decades. Perlin and
Goldberg [PG96] use concepts from improvisational theater to populate virtual
worlds, while Hayes-Roth and van Gent [HRVG96] describe virtual agents that
perform improvisational theater, modifying their appearance to convey
simulated emotional state. Several knowledge-based approaches have been
proposed for various problems in the space of acting in the improv theater,
such as scene introduction [OPFM11], fuzzy reasoning [MDD11], affect detection
[ZGB+07], and robotic actors [MM17b].

Through collaboration between human and machine, complex stories can be
constructed. Generative plot systems have been developed for nearly 100 years
[Coo28]. These systems aim to aid human creators with algorithmically
generated prompts to explore diverse plots. Through interaction with
generative systems, users are inspired to engage with topics they would not
have otherwise. The excitement of exploring unknown spaces and engaging with
novel topics defines the artform of theatrical improvisation [Joh79].

###  2.3 Improvised Theatre

In improvised theatre (improv) there is no script and no rehearsal; the show
is written and performed at the same time. It is an art derived from the
spontaneous justification of pseudo-randomness. Improvised theatre has been
described as a suitable test bed for human-machine co-creation systems [M+09,
MM17b, MHR16]. In improv, performers must attend to, and remember, details in
the story and must synthesize previous information with novel dialogue and
actions to progress a narrative. Often, the use of external prompts (or
suggestions) are utilized to add entropy to the performance [Joh79]. This
motivates the actors to justify this information within the context of the
current scene [Saw03].

Improvised scenes can be summarized in three stages: platform, tilt, finding a
new normal [Joh79]. The _platform_ of the scene defines what is normal in the
universe (i.e. who, what, when, where). The _tilt_ provides
flavour111According to www.thewayofimprovisation.com/glossary.php: _A tilt re-
frames the scene with a different context._. It is what makes this particular
performance unique from others with a similar platform. Finally, _finding a
new normal_ is how the scene justifies the tilt towards resolution. These
three stages enable investigation of the ability of the dAIrector to generate
cohesive plots and develop context-rich narrative. Our work addresses the
specific aspect of generating prompts for the actors on stage during an
improvised theater performance. These prompts constitute the beats of the
story in form of a platform, as well as tilts for the actors. It is then up to
the actors to act out the scene to find a new normal.

##  3 Approach

We present an improvised narrative co-creation system called dAIrector which
acts as an automated director to collaborate with humans storytellers for live
improvisational performances and writing assistance. The generated stories are
represented as linked clauses taken from William Wallace Cook’s “Plotto: The
Master Book of All Plots” [Coo28] augmented with related information from TV
Tropes222http://tvtropes.org/—a wiki-style database that contains narrative
tropes occurring in a wide range of different narratives. Human artists can
rapidly link the provided prompts to collaboratively evolve a narrative
through dialogue and actions. In this way, the dAIrector augments human
creativity. We discuss the challenges of evaluating a tool that, by design,
provides ambiguous guidance. We conclude by presenting several directions for
future research.

###  3.1 Plotto

Our work builds on the narrative development book “Plotto: The Master Book of
All Plots” by William Wallace Cook [Coo28], which contains a large variety of
plots. What makes it suitable for a computational application is the graph
structure. Rather than enumerating plots, Cook split them into fragments with
instructions on how to combine them.

The plot fragments constitute nodes and edges between them describe which
fragments can be connected to obtain a story. Edges can have labels, which
contain instructions for changing character symbols in subsequent plot
fragments (e.g. changing character $A$ to character $B$). Figure 1 shows a
subgraph from Plotto, each node a plot point and each edge a modification.
Fragment $746$ is defined in Plotto as: _B, who was thought by the people of
her community to have supernatural powers, is discovered to have been insane -
a condition caused by a great sorrow_. This fragment can be followed by either
fragment $1441a$: _A seeks to discover the secret of Life_ , or fragment
$1373$: _A sells his shadow for an inexhaustible purse_. Both of these
fragments make no mention of $B$, who is the main character of fragment $746$.
Therefore, the modifying edge instructs us to change $A$ to $B$, ensuring
consistency of the characters used. These three nodes represent just a small
fraction of the entire $3000$ notes contained in Plotto. We automatically
parse the nodes and edges into a JSON-based representation of the graph. Thus,
generating a story is done by performing a walk through the graph starting at
any random node.

Eger et al. used a similar method to build a plot generator utilizing the plot
fragments [EPBY15]. Since the plot fragments in Plotto are abstract
descriptions of plot points, ambiguous, and contain symbolic names for the
characters, the generated plots are less than suitable for presentation to an
audience. The ambiguity and openness make them ideal for interpretation in
improvised theatre. These plot points represent platforms for scenes
additional related details are needed to tilt the scene.

7461441a1373ch $A$ to $B$ch $A$ to $B$ch $B$ to $A$ Figure 1: A sub-graph from
Plotto. Nodes are plot fragments with corresponding numbers from Plotto, edges
are connections between plot points and edge labels correspond to instructions
for character modifications in subsequent fragments.

###  3.2 TV Tropes

TV Tropes is a wiki-style website that contains narrative tropes, i.e.
patterns or situations that occur across a variety of different narratives. As
a wiki, tropes often contain references to other, related tropes. Of
particular interest for our work are TV Tropes’s plot tropes which describe
high level plots abstractions. While related to those plots in Plotto, this TV
Tropes graph contains unlinked semantically related, complimentary
information.

The story beat is an identifiable moment of change in a narrative [McK97,
MS03], either in the form of a new platform or as a tilt. By connecting the
Plotto graph plot points as platforms and the TV Tropes plot tropes as tilts,
the dAIrector creates complete abstract narrative descriptions.

As described above, story generation using Plotto can be thought of as a walk
through the graph of plot fragments. For a performance, dAIrector starts at a
random node in the graph by presenting it to the actors on stage. We call the
plot fragment presented to the actors by the system the _platform_. The actors
can prompt the system for 1) the next platform in form of a new plot fragment
or 2) for a tilt to refine the current scene, and the system will use the
platform to determine which plot fragment or tilt to present next.

###  3.3 Paragraph Vectors

Our system utilizes paragraph vectors to provide information dependent on the
current platform. Paragraph Vector is an unsupervised machine learning method
to represent variable-length input text in a dense, fixed-length feature
vector [LM14]. Paragraph vectors overcome limitations of ignoring word order
and semantics of naive bag-of-word methods. To train the paragraph vector
model, we use the full text of the plot fragments, as well as the descriptions
of the tropes. We follow the training as described by Le and Mikolov and use
the Doc2Vec method from Gensim 333https://pypi.org/project/gensim/,
https://radimrehurek.com/gensim/models/doc2vec.html. Training parameters are
as follows:

  * •

Dimensionality of feature vector: $410$

  * •

Initial learning rate: $0.03$

  * •

Maximum distance between the current and predicted word within a sentence
(window): $4$

  * •

Ignore all words with fewer than two occurrences

  * •

Negative sampling is used with $4$ noise words

All other parameters are defaults as defined in Gensim.

During a performance, the current platform is used as to find the next
platform or a tilt. Alternatively, instead of using the current plot fragment,
actors may also provide a custom prompt to the system to steer the plot in a
certain direction. When queried, the dAIrector returns $5$ tilt options with
minimum cosine distances in vector space from the entire space of candidate
options [MSC+13, CYK+18]. For vectors $\mathbf{A}$ and $\mathbf{B}$ the cosine
distance, or angle distance between two vectors, is defined as
$d(\mathbf{A},\mathbf{B})=1-\frac{\mathbf{A}\cdot\mathbf{B}}{\left\|\mathbf{A}\right\|\left\|\mathbf{B}\right\|}$.

As noted above, we use the full text of the plot fragments, as well as the
descriptions of the tropes to train the paragraph vector model. However, since
these descriptions are typically several paragraphs long, we only communicate
the trope names to the actors. While we perform all comparisons against the
full textual description of the tropes, this description is never displayed to
the actors. This allows us to keep the instructions from the dAIrector concise
open ended while providing additional, related information [Saw03].

###  3.4 Plot Tree Generation

Rather than generating a single plot from the Plotto graph we generate a tree,
with one start node chosen randomly and all successors as children. Each of
these children has its successors as children up to a configurable depth. By
default, the platform used to determine the next scene is the current plot
fragment, but actors may prompt the system for a plot fragment that aligns
more closely with their interpretation of a scene or details which arose from
the scene improvisation. A performance of such a plot tree starts at the root
node, and proceeds down the tree, where child nodes are chosen depending on
the prompts given by the actors.

For example, the plot fragment _Carl’s friends, Doug and Fred, believe that
Lisa, whom Carl is about to marry, is a woman of immoral character_ , has two
successors: _Carl seeks to free himself from certain meddlesome influences_
and _Lisa, harassed by gossip that reflects on her integrity, seeks
deliverance from false suspicion_. Depending on which aspect of the original
plot the actors decide to focus on, the interference of Doug and Fred in
Carl’s affairs or the rumors that Lisa is of immoral characters, one or the
other successor is better suited. Note that neither successor is completely
unsuitable in any case, meaning that the platform can provide guidance for the
system, but that guidance does not necessarily have to be followed.

###  3.5 Contextual Tilts

In addition to simply traversing the plot tree, the system can also provide
_tilts_ in the form of plot tropes obtained from TV Tropes. In this case, the
platform is used to find a selection of tropes that fit best with the current
plot fragment. Tilts provide additional information. Thus, rather than
returning the single trope is closest to the platform, our system computes the
$5$ most semantically similar tropes and then returns a random sample from the
related set.

Prior to sampling, plot fragments are filtered and excluded if they only
provide redundant information. For example, if the platform is _Albert, an
inefficient, futile sort of person, comes to believe that he is the
reincarnation of Nicola Tesla_ , the best fitting trope according to our
system is _Reincarnation_ , which does not provide any additional information.
However, the trope that has the second lowest distance is _Deal With The
Devil_ , which provides additional guidance for the actors. In a performance,
the actors can utilize this, for example, to narrow down how Albert came to
his belief, by making a deal with the devil. This provide the scene additional
directions to explore, but it is up to the actors to decide when they would
prefer a tilt for additional guidance and when they want to follow their own
impulse for where the scene should go.

To eliminate redundant tropes, we compute the word intersection of words with
more than $3$ letters (to exclude articles, pronouns, etc.) with the platform
and discard any tropes for which this intersection is non-zero. In the example
above, because the word _reincarnation_ is also part of the platform this
particular tilt would not be provided by the system.

###  3.6 Stage Presence

For a performance, the system provides output in the form of platform beats
and tilts, according to prompts given by the actors. The basic outline of this
process is as follows:

    platform = root(plot_tree)
    present(platform)
    while platform != Null:
        request, prompt = get_input()
        context = platform
        if prompt != Null:
            context = prompt
        if request == "platform":
            platform = best_match(context, children(platform))
            present(platform)
        if request == "tilt":
            tilt = random(best_n_match(context, tvtropes, 5))
            present(tilt)

When the actors request either a platform beat or a tilt, the system uses the
paragraph vector model to find the best match among all candidates for the
given prompt, which defaults to the last presented platform beat. For the next
platform the candidates are the Plotto plot fragments that are children in the
provided plot tree, while for tilts the candidates are all TVTropes plot
tropes.

The basic mode of interaction with our system is through a console-based
application. This application will present the plot fragments in order, and
can be prompted for the next platform or a tilt. For a live performance, this
mode is less convenient and therefore we also provide the capabilities for
speech input and output, realized through speech-to-text using _pocketsphinx_
[HDKC+06] and text-to-speech using the built-in say operating system command.
Using this interaction mode, the system reads plot fragments and tilts out
loud, and the next platform beat or tilt can be obtained by the actors saying
the corresponding keywords.

Plot fragments, as contained in Plotto refer to characters in the story using
codes, including $A$ for the main male character, $B$ for the main female
character, but also very specific codes such as $AUX$ for a fictitious aunt.
As part of presenting the plot fragments to the actors and audience, our
system replaces these codes with consistent character names. This is
controlled via a configuration file, with default names provided by the
system. For clarity, we present all plot fragments in this paper with names
replaced. Note that at this point we do not change pronouns if character
symbols are replaced since that would require automatic identification of the
referent of each pronoun, which is outside the scope of this work.

##  4 Evaluation

Given the unique environment of an improv theater performance, evaluating the
quality of output is challenging; there is often no catastrophically “wrong”
output [MM17b]. That said, given the platform some tilts will require
significantly more justification to produce a satisfying narrative [Saw03].
For our work, the main challenge lies with evaluating the platforms and tilts
of story fragments.

Having humans annotate multiple story fragments with the best fitting trope is
a challenging multi-class classification problem. For example, the plot
fragment _Joe, becoming aware of an old prophecy, unconsciously seeks to
become like the exalted protagonist of the prophecy_ could be seen as having
any of the tropes _Prophecy Twist_ , _Self Fulfilling Prophecy_ , _The
Unchosen One_ , or _Because Destiny Says So_ (among others) as the “correct”
fit. For this task, we report how well our system reproduces human-assigned
tilts on our test set.

###  4.1 Evaluation of Tilts

To test the key functionality of dAIrector, that of selecting a best-fitting
tilt given a plot fragment, we design a simple task. First, we generated a
dataset of $100$ clean, labelled tilt – plot fragment pairs. We split this
dataset into training and testing sets. For evaluation, we sample a random
plot fragment from the test set and the task for the system is to correctly
predict the associated tilt. Given a plot fragment our model returns the 5
candidate tilts with the minimum cosine distance. We evaluate the system based
on top-5 accuracy. Clearly stated for explicitness, given a plot fragment, how
likely is it that the associated tilt is in the $5$ results returned by the
system? This number is reported over the entire $20$ examples in the test set.

One insight gained from this approach was that while the tropes produced by
the system are usually related to the text fragment, there are several tropes
that are vague and apply to many scenarios, while others, which are often more
closely related to the story fragment at hand are more specific. For example,
in our test set, the trope “Much Ado about Nothing”, which is a generic trope
about love, applies to a wide variety of plot fragments. The trope that was
selected the second most often for our test set was, “Road Trip”, which
applies to a wide variety of travel-related scenarios.

The dAIrectory returns a random sample from the five most closely related
tilts to a given plot point. It is therefore also reasonable to use the top-5
error as a measure of quality rather than the top-1 error. Top-N error is a
common error metric for classification tasks and measures how often the target
class does not show up in the top-N classes assigned to a test example.

Even so, the top-5 error on our test set is $40\%$, while the top-1 error rate
is $66\%$. While high, the trope annotation task resulted in many arbitrary
choices by human annotators. Most likely this is due to there not being a
clear best trope, and human annotators being overwhelmed by the number of
possible, subtly different, tropes.

Our plot trope set contained about $700$ tropes from the total trope set of
about $4300$444These are the $700$ tropes listed as _plot tropes_ by TV
Tropes: https://tvtropes.org/pmwiki/pmwiki.php/Main/Plots . For example, the
story fragment _Alfred is thrown into prison through false evidence in a
political conspiracy_ was assigned the trope _Get Into Jail Free_ by a human
annotator, but our system returned _Clear Their Name_ , _Mystery Literature_ ,
_No Mere Windmill_ , _Lipstick Mark_ 555as in evidence of a cheating spouse.,
_Prison Riot_ as the top five tropes, all of which could also be deemed
applicable.

Note the difference in specificity between _Mystery Literature_ and _Lipstick
Mark_ , where the latter provides a lot more detail to the actors of how to
proceed with the scene. At present, our system treats all tropes as equally
applicable, but, as noted above, some tropes are more general and thus related
to the story being presented while actually adding less detail than others.
While very specific, the definition of the trope _Get Into Jail Free_ actually
refers to a character that wants to get arrested intentionally, which is
arguably less fitting with the given sentence, but demonstrates the challenges
faced by the human annotators.

As a way to quantify this discrepancy we used information contained within the
TV Tropes graph. Tropes linked from one another if they shared some
commonality. We used these links to calculate a distance between tilts our
system generated and the humans annotated, equal to the number of links
between two tropes.

For example, _Get Into Jail Free_ links to _Can’t Get in Trouble for Nuthin’_
, which links to _FrameUp_ as a reason for the arrest. That trope links to
_Clear Their Name_ as a way to resolve the situation, resulting in a distance
of $3$ between _Get Into Jail Free_ and _Clear Their Name_.

Over the entire TV Tropes set, the median distance between two tropes is $3$
(mean: $3.1$, stddev: $0.6$). This is not unexpected, since tropes often refer
to “supertropes”, which refer to other “supertropes”, from which the target
trope can be reached. However, the median distance for tropes given as tilts
by our system, excluding those that exactly matched the human annotation was
$2$ (mean: $2.5$, stddev: $0.7$), which is typically a connection via the
“supertrope” common to the two tropes.

###  4.2 Sample Stories

To better illustrate the output from our system, we present sample stories
produced by the system along with tilts the actors might be given. These
stories demonstrate how the produced outputs are coherent stories. The
coherency is a product of the structure employed by Plotto. Additionally, we
show examples of stories to illustrate that the tilts the system selects can
be used to refine, provide background information, or drive the story in
different directions. To demonstrate our system, we set the maximum length of
each story to $5$. Shorter stories tend not to have enough happening in them
to qualify them as stories, while longer stories, owing to the structure of
the book, start to meander to different, somewhat unrelated story lines.

The first example is a well structured narrative with a beginning, middle, and
end, consisting of the following platform beats:

  1. 1.

Lana, a person influenced by obligation, falls into misfortune through
mistaken judgment.

  2. 2.

Lana, in order to be revenged upon her enemy, Mr. Kyle, manufactures an
infernal machine, BLOB.

  3. 3.

Lana, influenced by a compelling idea of responsibility, finds it necessary to
protect her friend, Tynan, from a secret danger.

  4. 4.

Lana, suspected of treachery by her friend, Tynan, in a daring rescue, saves
the property and perhaps the life of Tynan, and proves her faithfulness by a
revelation of the danger to which Tynan, unknown to himself, was exposed.

  5. 5.

Lana seeks to correct a character weakness in her friend, Tynan.

  6. 6.

Lana achieves success and happiness in a hard undertaking.

In each scene, the platform is clear and evident. In addition to the platform
of the scene and the dialog from the improvisors, the actors might desire a
plot device to instigate or inspire the action. For instance, the ”secret
danger” referenced in Scene 3 is vague, and the actors might ask the system
for a tilt. One such applicable tilt returned by our system, _It Belongs in a
Museum_ , provides context to further refine the “secret danger”.

Plot fragments present in Plotto rarely mention time passing, and it is often
up to the actors to explain jumps in time. Consider this example of a sequence
of platform beats from our system:

  1. 1.

Alfred, in order to restore to Beatrice, without a confession of culpability,
wealth of which he has secretly defrauded her, marries her.

  2. 2.

Alfred seeks to escape difficulties, restore property and be free of an
unloved wife, Beatrice, all by secret enterprise.

  3. 3.

Alfred leaves his coat on a cliff at the seaside, drops his hat in a stunted
tree below the brink, and vanishes from the scenes that know him.

  4. 4.

Alfred, under a fictitious name, returns to his native place, where he had
committed a youthful transgression, and, as an Unknown, seeks to discover
whether his youthful escapades have been forgotten and forgiven. Also, he
wishes to make reparation in an assumed character for wrong done in his true
character.

  5. 5.

Alfred, returning as an Unknown to his native place, discovers no one
recognizes him.

Alfred disappears in scene 3, and then reappears what is apparently much later
in scene 4 to wrap up his transgressions from the earlier scenes. We highlight
this story, because when the system was asked for a tilt on scene 3, it
responded with the tilt _Tailor Made Prison_ , which seemed unfitting at
first. However, upon reflection the references to the coat and hat link it to
the concept of a tailor. This is remarkable for two reasons: 1) it is probably
not a connection that would arise immediately to a human, and 2) this can be
seen as a pun that works well within the context of our domain.

###  4.3 Qualitative Evaluation by Professional Improvisor

To investigate the quality of the system we instructed a professional
improvisor (fluent, native English speaker, improvisor with 10+ years
performance experience) to interact with the dAIrector. The performer was
given an introduction to the system, and then explored the interaction over
the course of several scenes. The performer discussed their impressions during
the interaction. We summarize the interaction feedback below by including
_quotes from the performer_. For several points, we directly address the
quotes.

  * •

_There is a real fun in getting yourself into trouble and then putting your
faith in the dAIrector to do something to help._ In improvisation these are
described as What Should I Do? moments, when the improvisor decided to prompt
the system for the next plot point or tilt.

  * •

_It doesn’t know what I want the scene to be about or what decisions I make_.
This is an area for future work focused on how the actor’s dialogue and
actions are incorporated as prompts for the system.

  * •

_Justification is natural, and it is natural to make leaping assumptions to
connect actions/intentions to characters as the plot generation system did not
inherently make those assignments._

  * •

_Tilts don’t over-complicate the narrative, it expands the story rather than
advancing the plot, it adds flavour. The tilt is not always necessary, and
making it optional is suitable in improvisation. That said, I prefer to use
the system with the contextual tilts. They run the risk of throwing a
curveball that is very difficult, but they are often the sort of thing that
would be very fun to play. Tilts are a fun expansion._

  * •

_I prefer being able to choose when the plot points and hints come_

##  5 Discussion and Conclusions

One of the limitations of our approach is that in our graph representation of
domains all nodes are created equal, even when the underlying data sets might
have additional information attached to them. For example, the tropes in the
TV Tropes data set actually frequently refer to “subtropes”, “supertropes” or
even state “contrast with” or “opposite of” in relation to another trope. Our
system often returns very broad tilts such as _Mystery Literature_ , or overly
specific tilts such as _Lipstick Mark_ , without any means to control which
one to get. However, we believe that utilizing the structural information
contained within the data set could lead to tilts that are better suited for
any application. Extracting this structural information is non-trivial as it
is not structured meta-data. Additionally, while TV Tropes is a useful
resource, it is a large dataset that suffers from common dataset quality and
inconsistency issues. One way to address these limitations would be to use a
subset of tropes that are particularly narrative building. This would require
filtering based on a heuristic (learned or pre-defined) which can classify and
rank tropes based on narrative building qualities. Some of these qualities
could be information about the universe gained through introduction of the
trope, or dynamic shifts between characters

We used Plotto and TV Tropes as our data sources because they cover a wide
range of different narratives. It would also be possible to expand the
dAIrector to use more specialized databases such as DramaBank [Els12]. By
designing a structured graph of information, textual plots of TV show episodes
could constitute an interesting data source as well. This could allow for
plots which extend over seasons, character arcs, individual episode, or scenes
within an episode.

Treating the plot fragments as a graph allows us to use the story-generating
walk for other data sources which can be represented as graphs. We are also
considering a possible application outside of narratives: the directed
exploration of large graphs, such as Wikipedia for knowledge synthesis. In
this scenario we could target users browsing a certain topic, starting an
article of interest. The user could then request linked articles, constrained
to articles semantically related to a query from a different data source.

##  6 Acknowledgements

We would like to thank the anonymous reviewers for their insightful feedback
and suggestions toward improving this research. Additionally, we would like to
thank several individuals for their invaluable discussion in the preparation
of this work, they include: Piotr Mirowski, Stuart Hoye, and Gary Kac̆marc̆ík.
Finally, we are indebted to the talented perfomers at Rapid Fire Theatre who
provided expert opinions on the system, including: Paul Blinov and Julian
Faid.

## References

  * [Coo28] William Wallace Cook.  Plotto: The Master Book of All Plots.  Ellis, first edition, 1928.
  * [CYK+18] Daniel Cer, Yinfei Yang, Sheng-yi Kong, Nan Hua, Nicole Limtiaco, Rhomni St John, Noah Constant, Mario Guajardo-Cespedes, Steve Yuan, Chris Tar, et al.  Universal sentence encoder.  arXiv preprint arXiv:1803.11175, 2018.
  * [Els12] David Elson.  Dramabank: Annotating agency in narrative discourse.  In LREC, 2012.
  * [EPBY15] Markus Eger, Colin M Potts, Camille Barot, and R Michael Young.  Plotter: operationalizing the master book of all plots.  Proceedings of the Intelligent Narrative Technologies and Social Believability in Games, pages 30–33, 2015.
  * [HDKC+06] David Huggins-Daines, Mohit Kumar, Arthur Chan, Alan W Black, Mosur Ravishankar, and Alexander I Rudnicky.  Pocketsphinx: A free, real-time continuous speech recognition system for hand-held devices.  In Acoustics, Speech and Signal Processing, 2006. ICASSP 2006 Proceedings. 2006 IEEE International Conference on, volume 1, pages I–I. IEEE, 2006.
  * [HRVG96] Barbara Hayes-Roth and Robert Van Gent.  Improvisational puppets, actors, and avatars.  In Proc Computer Game Developers’ Conf, 1996.
  * [Joh79] Keith Johnstone.  Impro. Improvisation and the theatre. Faber and Faber Ltd, 1979.
  * [LLUJR13] Boyang Li, Stephen Lee-Urban, George Johnston, and Mark O. Riedl.  Story generation with crowdsourced plot graphs.  In Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, AAAI’13, pages 598–604. AAAI Press, 2013.
  * [LM14] Quoc Le and Tomas Mikolov.  Distributed representations of sentences and documents.  In International Conference on Machine Learning, pages 1188–1196, 2014.
  * [M+09] Brian Magerko et al.  An empirical study of cognition and theatrical improvisation.  In Creativity and Cognition, 2009.
  * [MAW+17] Lara J Martin, Prithviraj Ammanabrolu, Xinyu Wang, William Hancock, Shruti Singh, Brent Harrison, and Mark O Riedl.  Event representations for automated story generation with deep neural nets.  arXiv preprint arXiv:1706.01331, 2017.
  * [McK97] Robert McKee.  Substance, structure, style, and the principles of screenwriting.  New York: HarperCollins, 1997.
  * [MDD11] Brian Magerko, Peter Dohogne, and Chris DeLeon.  Employing fuzzy concept for digital improvisational theatre.  In Proceedings of the Seventh AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, AIIDE’11, pages 53–60. AAAI Press, 2011.
  * [Mee76] James Richard Meehan.  The metanovel: writing stories by computer.  Technical report, Yale Univ, New Haven Conn, Dept of Comp Sci, 1976.
  * [Mee77] James R Meehan.  Tale-spin, an interactive program that writes stories.  In IJCAI, volume 77, pages 91–98, 1977.
  * [MHR16] Lara J Martin, Brent Harrison, and Mark O Riedl.  Improvisational computational storytelling in open worlds.  In Interactive Storytelling: 9th Intl Conf on Interactive Digital Storytelling, Los Angeles, USA, November 15–18, 2016, Proc 9, pages 73–84. Springer, 2016.
  * [MM17a] Kory Wallace Mathewson and Piotr Mirowski.  Improvised comedy as a turing test.  arXiv preprint arXiv:1711.08819, 2017.
  * [MM17b] Kory Wallace Mathewson and Piotr Mirowski.  Improvised theatre alongside artificial intelligences.  In AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, 2017.
  * [MS03] Michael Mateas and Andrew Stern.  Façade: An experiment in building a fully-realized interactive drama.  In Game developers conference, volume 2, pages 4–8, 2003.
  * [MSC+13] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean.  Distributed representations of words and phrases and their compositionality.  In Advances in neural information processing systems, pages 3111–3119, 2013.
  * [OPFM11] Brian O’Neill, Andreya Piplica, Daniel Fuller, and Brian Magerko.  A knowledge-based framework for the collaborative improvisation of scene introductions.  In ICIDS, pages 85–96. Springer, 2011.
  * [PG96] Ken Perlin and Athomas Goldberg.  Improv: A system for scripting interactive actors in virtual worlds.  In Proc. Conf. on Computer Graphics and Interactive Techniques, pages 205–216. ACM, 1996.
  * [RY10] Mark O Riedl and Robert Michael Young.  Narrative planning: Balancing plot and character.  Journal of Artificial Intelligence Research, 39:217–268, 2010.
  * [Saw03] Robert Keith Sawyer.  Improvised dialogues: Emergence and creativity in conversation.  Greenwood Publishing Group, 2003.
  * [Ste11] Eric W Stein.  Improvisation as model for real-time decision making.  In Supporting real time decision-making, pages 13–32. Springer, 2011.
  * [TFNH03] Mariët Theune, Sander Faas, Anton Nijholt, and Dirk Heylen.  The virtual storyteller: Story creation by intelligent agents.  In Proceedings of the Technologies for Interactive Digital Storytelling and Entertainment (TIDSE) Conference, volume 204215, 2003.
  * [Tur50] Alan M Turing.  Computing machinery and intelligence.  Mind, 59(236):433–460, 1950.
  * [WY11] Stephen G Ware and Robert Michael Young.  Cpocl: A narrative planner supporting conflict.  In AIIDE, 2011.
  * [ZGB+07] Li Zhang, Marco Gillies, John A Barnden, Robert J Hendley, Mark G Lee, and Alan M Wallington.  Affect detection and an automated improvisational ai actor in e-drama.  In Artifical Intelligence for Human Computing, pages 339–358. Springer, 2007.