Constructor theory is a meta-theoretic approach that seeks to characterise concrete theories of physics in terms of the (im)possibility to implement certain abstract “tasks” by means of physical processes. Process theory, on the other hand, pursues analogous characterisation goals in terms of the compositional structure of said processes, concretely presented through the lens of (symmetric monoidal) category theory. In this work, we show how to formulate fundamental notions of constructor theory within the canvas of process theory. Specifically, we exploit the functorial interplay between the symmetric monoidal structure of the category of sets and relations, where the abstract tasks live, and that of symmetric monoidal categories from physics, where concrete processes can be found to implement said tasks. Through this, we answer the question of how constructor theory relates to the broader body of process-theoretic literature, and provide the impetus for future collaborative work between the fields.

§ INTRODUCTION

Constructor theory [17, 18, 30] is a metatheoretic approach that seeks to characterise concrete theories of physics and information in terms of the possibility and impossibility of tasks, which are transformations between systems.
Transformations may require auxiliary inputs other than the system to be transformed: the task of turning black shoes into white shoes may require a stock of white paint as an auxiliary input in addition to the black shoes themselves.
Tasks transform states of systems into other states, and attributes of systems—such as the blackness of a shoe—into other attributes.
In our universe, we will eventually run out of white paint for this task, but if we had a mathematically ideal paintbrush with infinite white paint, we could reuse it for as many instances of the task as we'd like; such non-exhaustible auxiliary catalysts for tasks are called constructors.
A task is possible when it is partnered with a constructor that allows the task to be performed arbitrarily many times, and the task is impossible otherwise.
Though constructors and tasks are abstract, they provide explanatory value; constructor theory seeks to characterise physical theories in terms of what tasks are possible.
As a metatheory, constructor theory is implementation-agnostic, and one can choose whatever formal system of mathematics they like as a concrete language to interpret the italic terms above.

Process theories provide one such mathematically formal language, one particularly well-suited to describe the composition of processes in space-time.
Moreover, process theories are expressed in terms of string diagrams, which are an aesthetic, intuitive, flexible, and rigorous metalinguistic syntax, empowering the modeller by allowing them to operate at a level of abstraction of their choice.
This means that the same abstract diagrams provide a common syntactic foundation for fields as disparate as linear and affine algebra [6, 5], first order logic [24], electrical circuits [4], digital circuits [21], database operations [26, 35], spatial relations [34], game theory [25], petri nets [3], hypergraphs [2], probability theory [8, 20], causal reasoning [28], machine learning [16], and quantum theory [15, 14], to name just a few.

In this short paper, we provide a formal interpretation of constructor-theoretic terminology and ideas within the string-diagrammatic setting of process theories, with the intent to build a bridge between the two communities.
We caution against the view that constructor theory is “just” a class of process theories, in the same sense as it would be misguided to claim that prime numbers are “just” integers.
Process theory merely provides a rigorous mathematical language for constructor theorists to tell their stories.

For the process theorists in our audience, we wish to stress that the pedagogical mathematical presentation of this paper is for the sake of constructor theorists who might be approaching our field for the first time.
Regardless, we offer you a Rosetta stone for constructor theory within what we understand to be the de rigueur mathematics of the field, transliterated into diagrams with as few embellishments and interpretational choices as possible.
For the constructor theorists in our audience, we extend a warm invitation to join the process-theoretic community: to the best of our knowledge, this is the most attractive and general formal arena available within which to explore the ramifications of constructor theory.

§ CONCEIVABLE TASKS

Constructor theory is concerned with the study of physical theories in terms of the question “which tasks are performable within this physical theory?": there is an abstract notion of conceivable tasks and a concrete notion of possible tasks.
In seminal work by Deutsch [17], it was remarked that, in full generality, the only real requirement on conceivable tasks is arbitrary composability in sequence and in parallel, i.e. that they form a symmetric monoidal category (SMC).
[It is possible that Deutsch meant for substrates to have an individual identity as physical systems, rather than just a “type”: that is, it is possible that Deutsch would prefer for “this qubit” and “that qubit” to be modelled by different—albeit isomorphic—objects in a process theory. In this case, it would make no sense to consider parallel compositions of tasks involving the “same” physical system, and partially-monoidal categories as defined in [22] would be preferable as a process-theoretical universe.]
Back then, however, the same author made a specific choice to model tasks as relations between sets: constructor theory literature has stuck by this choice ever since, and so will we.

In this work, we take all monoidal categories to be strict, and in particular we assume that objects $\obj{\smc{D}}$ in a monoidal category $\smc{D}$ form a strict monoid. In the case of the SMCs $\Rel$ and $\Set$, considered in Definition 2.2 below, this implies a choice of singleton set $1 := \{*\}$ to act as a strict unit for the Cartesian product:

\[
X \times 1 = X = 1 \times X
\]

This also affords us the freedom to write triples (and other tuples) without having to care about nesting:

\[
X \times Y \times Z
= \suchthat{(x,y,z)}{x \in X, y \in Y, z \in Z}
\]

Note that strictness does not extend to symmetry isomorphisms: we have that $X \times Y \cong Y \times X$, but this doesn't mean that $X \times Y = Y \times X$. As a consequence, the monoid formed by objects in a strict SMC is not generally commutative.

We take the theory of conceivable tasks to be $\Rel$, the $\dagger$-SMC of sets and relations. We write $\task{A}: X \rightarrow Y$ for a task/relation $\task{A} \subseteq X \times Y$, where the set $X$ labels legitimate input states for the task and the set $Y$ labels legitimate output states. To help distinguish between pairs/tuples of elements in a Cartesian product and pairs of domain/codomain elements in a relation, we reserve pair/tuple notation for the former and adopt maplet notation for the latter:

\[
x \mapsto y \;\;:\equiv\;\; (x,y)
\hspace{2.5cm}
x \tmapsto{A} y \;\;:\equiv\;\; (x,y) \in \task{A}
\]

We omit $\task{A}$ from $\stackrel{\task{A}}{\mapsto}$ when clear from context. The sequential composition $\task{B} \circ \task{A}: X \rightarrow Z$ of task $\task{B}: Y \rightarrow Z$ after $\task{A}: X \rightarrow Y$ is defined as follows:

\[
\task{B} \circ \task{A}
:= \suchthat{x\mapsto z}{\exists y \in Y.\, x \stackrel{\task{A}}{\mapsto} y \text{ and } y \stackrel{\task{B}}{\mapsto} z}
\]

Sequential composition in diagrammatic language:

\[
\tikzfig{seqcomp}
\]

Composite sets of states are obtained by Cartesian product $X \times Y$:

\[
X \times Y
:= \suchthat{(x,y)}{x \in X \text{ and }y \in Y}
\]

The parallel composition $\task{A} \times \task{B}: X \times Z \rightarrow Y \times W$ of tasks $\task{A}: X \rightarrow Y$ and $\task{B}: Z \rightarrow W$ is defined as follows:

\[
\task{A} \times \task{B}
:= \suchthat{ (x,z) \mapsto (y,w) }{ x \tmapsto{A} y \text{ and } z \tmapsto{B} w }
\]

Parallel composition in diagrammatic language:

\[
\tikzfig{parcomp}
\]

The transpose $\task{A}^\dagger: Y \rightarrow X$ of a task $\task{A}: X \rightarrow Y$ is defined as follows:

\[
\task{A}^\dagger
:= \suchthat{ y \mapsto x}{x \tmapsto{A} y }
\]

Transposition in diagrammatic language:

\[
\tikzfig{transpose}
\]

Finally, there are symmetry isomorphisms (aka swaps) $\sigma_{X,Y}: X \times Y \stackrel{\cong}{\rightarrow} Y \times X$:

\[
\sigma_{X,Y} := \suchthat{ (x,y) \mapsto (y,x) }{ x \in X \text{ and } y \in Y }
\]

Symmetry isomorphisms in diagrammatic language:

\[
\tikzfig{syms}
\]

The symmetry isomorphisms are a structural feature of the category, making it possible to compose relations into acyclic networks, where outputs of relations can be connected to inputs of other relations. This is made possible by the following properties of the symmetry isomorphisms:

\[
\tikzfig{symeqs}
\]

The sets $X$ and $Y$ are allowed to be distinct, for sake of generality. Asking that they are always equal is equivalent to restricting the theory of conceivable tasks to be the $\dagger$-SMC $\EndoRel$ of sets and endo-relations $R: X \rightarrow X$, which is a sub-$\dagger$-SMC of $\Rel$.

If we restrict our attention to the total deterministic relations in $\Rel$, we obtain the sub-SMC $\Set$ of sets and functions between them. Functions are closed under acyclic network composition (sequential and parallel, including the usage of symmetry isomorphisms), but not under transpose. Important examples of functions are the copy map $\delta_X: X \rightarrow X \times X$ and discarding map $\epsilon_X: X \mapsto 1$ on a set $X$:

\begin{align*}
\delta_X &:= \suchthat{x \mapsto (x,x)}{ x \in X}\\
\epsilon_X &:= \suchthat{x \mapsto *}{ x \in X}
\end{align*}

Copy and delete maps in diagrammatic language:

\[
\tikzfig{copydel}
\]

Copies are indistinguishable under swaps and repeated copies, and deleting a copy results in the identity:

\[
\scalebox{0.8}{$
\tikzfig{copydeleqs}
\]

The transposes of the copy and discarding map are not functions. The transpose $\delta_X^\dagger: X \times X \rightarrow X$ is the match map, a partial function which returns the common value of its inputs when they're equal and is otherwise undefined:

\[
\delta_X^\dagger := \suchthat{(x,x) \mapsto x}{ x \in X}
\]

Match map in diagrammatic language:

\[
\tikzfig{match}
\]

Relations $S: 1 \rightarrow X$, such as the transpose $\epsilon_X^\dagger: 1 \rightarrow X$ of the discarding map, can be identified with all possible attributes of states in $X$, i.e. with all possible subsets $S \subseteq X$:

\[
S \cong \suchthat{* \mapsto x}{ x \in S}
\]

States and attributes have the same notation in diagrammatic language, since states $x \in X$ can be identified with singleton subsets $\{x\} \subseteq X$:

\[
\tikzfig{attr}
\]

The transpose $\epsilon_X^\dagger: 1 \rightarrow X$ of the discarding map is the trivial attribute, corresponding to subset $X \subseteq X$:

\[
\eta_X := \epsilon_X^\dagger = \suchthat{* \mapsto x}{ x \in X}
\]

Trivial attribute in diagrammatic language:

\[
\tikzfig{unit}
\]

Attributes can be used to condition tasks to specific input states.

Let $\task{A}: X \times Z \rightarrow Y$ be a task and let $S \subseteq Z$ be an attribute on states in $Z$. The pre-conditioned task is defined to be the task obtained by forgetting all information about the $Z$ input of $\task{A}$ other than the fact that the input state has attribute $S$:

\[
\substack{
\tikzfig{preconditioned}\\
\task{A} \circ (\id{X} \times S)
= \suchthat{x \mapsto y}{\exists z \in S.\, (x,z) \tmapsto{A} y}
\]

As a special case, we can discard the $Z$ input entirely, by pre-conditioning against the trivial attribute $\eta_Z$:

\[
\substack{
\tikzfig{prediscard}\\
\task{A} \circ (\id{X} \times \eta_Z)
= \suchthat{x \mapsto y}{\exists z \in Z.\, (x,z) \tmapsto{A} y}
\]

The object $1$ is terminal in $\Set$: there is a unique function $\epsilon_X: X \rightarrow 1$ for any set $X$. However, it is not terminal in $\Rel$: the relations $X \rightarrow 1$ are exactly the transposes $S^\dagger: X \rightarrow 1$ of the attributes $S: 1 \rightarrow X$. Explicitly, they are the constant partial functions with the attribute $S$ as their domain:

\[
S^\dagger := \suchthat{ x \mapsto * }{ x \in S }
\]

The transposes of attributes are tests, which can be used to condition tasks to specific output states.

Let $\task{A}: X \rightarrow Y \times Z$ be a task and let $S \subseteq Z$ be an attribute on states in $Z$. The post-conditioned task is defined to be the task obtained by forgetting all information about the $Z$ output of $\task{A}$ other than the fact that the output state has attribute $S$:

\[
\substack{
\tikzfig{postconditioned}\\
(\id{X} \times S^\dagger) \circ \task{A}
= \suchthat{x \mapsto y}{\exists z \in S.\, x \tmapsto{A} (y, z)}
\]

As a special case, we can discard the $Z$ output of the task entirely, by post-conditioning against the trivial attribute on $Z$:

\[
\substack{
\tikzfig{postdiscard}\\
(\id{X} \times \epsilon_Z) \circ \task{A}
= \suchthat{x \mapsto y}{\exists z \in Z.\, x \tmapsto{A} (y, z)}
\]

We can simultaneously pre-condition a task $\task{A}: X \times Z \rightarrow Y \times W$ against an attribute $P \subseteq Z$ and post-condition it against an attribute $Q \subseteq W$:

\[
\substack{
\tikzfig{prepost}\\
(\id{X} \times Q^\dagger) \circ \task{A} \circ (\id{X} \times P)
= \suchthat{x \mapsto y}{\exists p \in P, q \in Q.\, (x, p) \tmapsto{A} (y, q)}
\]

§ POSSIBLE TASKS

Conceivable tasks are a theory-independent concept: they provide a formal universe within which to formulate principles and derive constraints. On the other hand, possible tasks are theory-dependent, induced by the constructors physically available to implement them. In order to determine which tasks are possible, we need to make a choice of substrates within a theory of processes.

A choice of substrates $\left( \smc{C}, \Sigma, \Gamma \right)$ comprises:

* A reference theory of processes, in the form of a strict SMC $\smc{C} = \left(\obj{\smc{C}}, \otimes, I\right)$. For example, this could be the theory of finite-dimensional quantum systems and unitary transformations.

* A choice of substrates, in the form of a subset $\Sigma \subseteq \obj{\smc{C}}$ of systems in the theory of processes.

* A choice of sets of substrate states, in the form of a family $\Gamma = \left( \Gamma_{\substr{H}} \right)_{\substr{H} \in \Sigma}$ where $\Gamma_\substr{H} \subseteq \states{\smc{C}}{\substr{H}}$ is a set of states in $\smc{C}$ for each substrate $\substr{H} \in \Sigma$.

We require that the choice of substrates be closed under parallel composition: $I \in \Sigma$ and $\substr{H} \otimes \substr{K} \in \Sigma$ for all $\substr{H}, \substr{K} \in \Sigma$. We further require that the set of substrate states respects parallel composition of substrates: $\Gamma_I = 1$ and $\Gamma_{\substr{H}\otimes\substr{K}} = \Gamma_\substr{H} \times \Gamma_\substr{K}$ for all $\substr{H}, \substr{K} \in \Sigma$.

Given two substrates $\substr{H}, \substr{K} \in \Sigma$, we consider tasks $\Gamma_\substr{H} \rightarrow \Gamma_\substr{K}$ and ask which ones are possible within the given theory of processes: in short, a task is possible when there is a constructor which acting as a catalyst enables the task to be performed. Expanding on this, we come to the following definitions.

Let $\left( \smc{C}, \Sigma, \Gamma \right)$ be a choice of substrates and consider two substrates $\substr{H}, \substr{K} \in \Sigma$. A process $f: \substr{H} \rightarrow \substr{K}$ is task-inducing if it maps states in $\Gamma_\substr{H}$ to states in $\Gamma_\substr{K}$:

\[
\forall \rho \in \Gamma_\substr{H}.\;
f(\rho) \in \Gamma_\substr{K}
\]

We write $\indtask{f}$ for the task induced by $f$:

\[
\indtask{f} := \suchthat{\rho \mapsto f(\rho)}{\rho \in \Gamma_\substr{H}}
\]

Let $\left( \smc{C}, \Sigma, \Gamma \right)$ be a choice of substrates and consider a task $\task{A}: \Gamma_\substr{H} \rightarrow \Gamma_\substr{K}$. We say that $\task{A}$ is possible if there are:

(i) a substrate C (acting as a constructor for the task)

(ii) an attribute $P \subseteq \Gamma_\substr{C}$ (singling out the relevant constructor states)

(iii) a task-inducing process $f: \substr{H} \otimes \substr{C} \rightarrow \substr{K} \otimes \substr{C}$ (actually performing the task)

such that the following two conditions are satisfied:

* Task $\task{A}$ is obtained from the induced task $\indtask{f}$ by requiring that the input constructor state has attribute $P$ and discarding the constructor output:

\begin{align*}
\task{A} &=
\substack{
\tikzfig{def28}\\
(\id{\Gamma_\substr{K}} \times \epsilon_{\Gamma_{\substr{C}}})
\circ \indtask{f}
\circ (\id{\Gamma_\substr{H}} \times P)
&= \suchthat{
\rho \mapsto \rho'
\exists \gamma \in P, \gamma' \in \Gamma_\substr{C}.\,
f(\rho \otimes \gamma) = \rho' \otimes \gamma'
\end{align*}

* The attribute $P$ is preserved by the induced task $\indtask{f}$. While a particular constructor state $\gamma \in P$ may be modified to become $\gamma'$ by the underlying process of the induced task $\indtask{f}$, $\gamma'$ remains a constructor state for the same induced task $\indtask{f}$, i.e. $\gamma' \in P$. In $\Rel$, this constraint is equivalently expressed as the induced task $\indtask{f}$ sending the set of constructors $P$ to a subset of itself, regardless of the input and output on the substrates $\substr{H},\substr{K}$:

\[
%\forall \gamma \in P.\hspace{5mm}
\substack{
\tikzfig{def282}\\
(\epsilon_{\Gamma_\substr{K}} \times \id{\Gamma_{\substr{C}}})
\circ \indtask{f}
\circ (\eta_{\Gamma_\substr{H}} \times P) \subseteq P
\]

We write $\possibletasks{\left( \smc{C}, \Sigma, \Gamma \right)}$ for the set of possible tasks under the given choice of substrates.

The main result of this section is that possible tasks for a choice of substrate form a sub-SMC of $\Rel$, i.e. that they are closed under composition in arbitrary (acyclic) networks.

The possible tasks $\possibletasks{\left( \smc{C}, \Sigma, \Gamma \right)}$ for a given choice of substrates form a sub-SMC of $\Rel$.

Write $\smc{C} = \left(\obj{\smc{C}}, \otimes, I\right)$.
The identity tasks and swap tasks for all systems are made possible by the identity and symmetry isomorphisms of $\smc{C}$, with trivial constructor $\substr{C} := I$:

\[
\tikzfig{idtask}
\hspace{2cm}
\tikzfig{swaptask}
\]

The sequential composition $\task{B} \circ \task{A}$ of possible tasks $\task{A}$ and $\task{B}$, with constructors $C$ and $D$ respectively, is possible with constructor $C \otimes D$:
[This step of the proof becomes more complicated if constructors are forced to have individual identities (i.e. in a partially monoidal category) and the same constructor must be reused by task $\task{B}$ after being used by task $\task{A}$. We leave the handling of this more sophisticated process-theoretic interpretation of constructor theory to future work.]

\[\tikzfig{seqtaskcomp}\]

The parallel composition $\task{B} \times \task{A}$ of possible tasks $\task{A}$ and $\task{B}$, with constructors $C$ and $D$ respectively, is possible with constructor $C \otimes D$:
[This step of the proof becomes more complicated if constructors are forced to have individual identities and the same constructor must be simultaneously used by task $\task{B}$ and task $\task{A}$. We leave the handling of this more sophisticated process-theoretic interpretation of constructor theory to future work.]

\[\tikzfig{partaskcomp}\]

This completes our proof.

§ ATTRIBUTES AS STATES

More modern perspectives in constructor theory argue that tasks should be defined on the attributes of a substrate, rather than on the underlying states.
This captures the idea that the abstract specification of (possible) tasks—the basis upon which constructor theorists judge other theories of physics—should be based on the observable “macrostates” of a physical system (attributes/subsets of a set), rather than on the unobserved “microstates” which constitute them (states/elements of a set).
In this section, we show how the attribute-based perspective can be derived from the state-based perspective, in a compositionally sound way, by performing a suitable coarse-graining.

To start with, we define a notion of “coarse-graining” for tasks, moving from tasks defined on states (the “microstates”, to stick to the thermodynamical metaphor) to tasks defined on attributes (the “macrostates”, using the same metaphor).
We allow for the attributes involved to have non-trivial overlap—that is, we don't ask for them to form a partition—but we disallow nesting $S \subset T$ of different attributes; formally, we require for the set of attributes involved to form an “antichain” in the inclusion order $\subseteq$.

Let $X$ be a set. A set $\bar{X} \subseteq \mathcal{P}(X)$ of attributes on $X$ is an antichain if no two attributes are nested into each other:

\[
\forall S, T \in \bar{X}.\, S \subseteq T \Rightarrow S = T
\]

Having fixed a choice of attributes $\bar{X}$ on $X$ and $\bar{Y}$ on $Y$, any task $\task{A}: X \rightarrow Y$ induces a “coarse-grained task” on the sets of attributes, as follows: for attributes $S \in \bar{X}$ and $T \in \bar{Y}$, we say that $S \mapsto T$ in the coarse-grained task if whenever an input state $x \in X$ has attribute $S$, i.e. whenever $x \in S$, then at least one of the possible outputs states $\suchthat{y \in Y}{x \tmapsto{A} y}$ has attribute $T$, i.e. $\exists y \in T.\, x \tmapsto{A} y$.
Put it another way, $S \mapsto T$ in the coarse-grained task means that the output of task $\task{A}$ can have attribute $T$ whenever the input has attribute $S$.

Let $\task{A}: X \rightarrow Y$ be a task.
Let $\bar{X} \subseteq \mathcal{P}(X)$ and $\bar{Y} \subseteq \mathcal{P}(Y)$ be sets of attributes of $X$ and $Y$ respectively.
Then the coarse-grained task $\quotask{\task{A}}{\bar{X}}{\bar{Y}}: \bar{X} \rightarrow \bar{Y}$ is defined as follows:

\[
\quotask{\task{A}}{\bar{X}}{\bar{Y}} :=
\left\{
S \mapsto T
\;\middle|\;
S \in \bar{X},\, T \in \bar{Y},\, S \subseteq \task{A}^\dagger \circ T
\right\}
\]

We conclude this section with three results, piecing the coarse-graining story together.
Firstly, we prove that given any process theory of tasks—including, amongst many others, the theory of all conceivable tasks and all theories of possible tasks—the coarse-grainings of the tasks can themselves be arranged into a process theory.
This shows that tasks defined on attributes are just as compositionally sound as those defined on states.
Secondly, we remark how the original ordinary tasks, defined on states, can be compositionally embedded into the universe of coarse-grained tasks, proving that the latter are a sound generalisation of the former.
Finally, we remark that coarse-grained tasks can be embedded back into the universe of ordinary tasks, proving that ordinary tasks are as expressive as coarse-grained ones.

Let $\mathcal{C}$ be a sub-SMC of $\Rel$, i.e. a collection of systems and tasks closed under parallel and sequential composition.
The following defines a SMC $\overline{\mathcal{C}}$, which we refer to as the theory of coarse-grained tasks associated to $\mathcal{C}$:

* objects are all possible antichains of attributes for all possible sets of states:

\[
\obj{\overline{\mathcal{C}}} :=
\bigcup_{X \in \obj{\mathcal{C}}} \left\{
\bar{X} \subseteq \mathcal{P}(X)
\;\middle|\;
\bar{X} \text{ antichain}
\right\}
\]

* morphisms $\bar{X} \rightarrow \bar{Y}$ in $\bar{\mathcal{C}}$ are coarse-grained tasks corresponding to tasks $X \rightarrow Y$:

\[
\overline{\mathcal{C}}\left(\bar{X}, \bar{Y}\right)
:= \left\{
\quotask{\task{A}}{\bar{X}}{\bar{Y}}
\;\middle|\;
\task{A}: X \stackrel{\mathcal{C}}{\longrightarrow} Y
\right\}
\]

* sequential composition $\circ$ is inherited from $\mathcal{C}$

* parallel composition $\boxtimes$ on objects is defined as:

\[
\bar{X} \boxtimes \bar{Y} := \suchthat{S \times T}{S \in \bar{X},\, T \in \bar{Y}}
\]

* parallel composition $\boxtimes$ on morphisms arises by coarse-graining from that of $\mathcal{C}$:

\[
\quotask{\task{A}}{\bar{X}}{\bar{Y}}
\boxtimes \quotask{\task{B}}{\bar{Z}}{\bar{W}}
:= \quotask{\left(\task{A} \times \task{B}\right)}{\bar{X}\boxtimes\bar{Z}}{\bar{Y}\boxtimes\bar{W}}
\]

* identity and symmetry isomorphisms arise by coarse-graining from those of $\mathcal{C}$:

\[
\quotask{\id{X}}{\bar{X}}{\bar{X}} = \id{\bar{X}}
\hspace{2cm}
\quotask{\sigma_{X,Y}}{\bar{X}\boxtimes\bar{Y}}{\bar{Y}\boxtimes\bar{X}} = \sigma_{\bar{X}, \bar{Y}}
\]

In particular, morphisms are well-defined, i.e. whenever $\bar{X} = \bar{X'}$ and $\bar{Y} = \bar{Y'}$ we have:

\[
\suchthat{\bar{\task{A}}}{\task{A}: X \rightarrow Y}
= \suchthat{\bar{\task{A}}}{\task{A}: X' \rightarrow Y'}
\]

Objects are clearly well-defined, but well-definition of morphisms requires proof.
Let $X$ and $Y$ be sets, let $\bar{X} \subseteq \mathcal{P}(X)$ and $\bar{Y} \subseteq \mathcal{P}(Y)$ be antichains.
It suffices to show the following for $X' := \bigcup \bar{X} \subseteq X$ and $Y' := \bigcup \bar{Y} \subseteq Y$:

\[
\left\{
\quotask{\task{A}}{\bar{X}}{\bar{Y}}
\;\middle|\;
\task{A}: X \rightarrow Y
\right\}
= \left\{
\quotask{\task{A}}{\bar{X}}{\bar{Y}}
\;\middle|\;
\task{A}: X' \rightarrow Y'
\right\}
\]

Write $\pi_{X'}:= \{x \mapsto x | x \in X'\}: X \rightarrow X$ and $\pi_{Y'}:= \{y \mapsto y | y \in Y'\}: Y \rightarrow Y$.
If $S \in \bar{X}$ and $T \in \bar{Y}$, then $S \subseteq X'$ and $T \subseteq Y'$, and hence:

\[
S \subseteq \task{A}^\dagger \circ T
\;\Leftrightarrow\; S \subseteq \pi_{X'} \circ \task{A}^\dagger \circ T
\;\Leftrightarrow\; S \subseteq \pi_{X'} \circ \task{A}^\dagger \circ \pi_{Y'} \circ T
\]

Observing that $\pi_{Y'} \circ \task{A} \circ \pi_{X'}$ is a task $X' \rightarrow Y'$ completes the proof that morphisms are well-defined.
For identities, we want to show that $\quotask{\id{X}}{\bar{X}}{\bar{X}} = \id{\bar{X}}$, and this is exactly the definition of $\bar{X}$ being an antichain:

\[
\quotask{\id{X}}{\bar{X}}{\bar{X}} = \id{\bar{X}}
\Leftrightarrow \left[
S \subseteq T \Rightarrow S = T
\right]
\]

For symmetry isomorphisms, we want to show that $\quotask{\sigma_{X,Y}}{\bar{X}\times\bar{Y}}{\bar{X}\times\bar{Y}} = \sigma_{\bar{X}, \bar{Y}}$, and this again follows from the antichain requirement:

\begin{align*}
\quotask{\sigma_{X,Y}}{\bar{X}\boxtimes\bar{Y}}{\bar{X}\boxtimes\bar{Y}} = \sigma_{\bar{X}, \bar{Y}}
\left(S \times T \subseteq \sigma_{X,Y}^\dagger \circ (T' \times S')\right)
\Rightarrow \left(S = S' \text{ and } T = T'\right)
\right]
\\
\left(S \subseteq S' \text{ and } T \subseteq T'\right)
\Rightarrow \left(S = S' \text{ and } T = T'\right)
\right]
\end{align*}

For sequential composition to be well-defined, we need to show that $S \subseteq \task{A}^\dagger \circ T$ and $T \subseteq \task{B}^\dagger \circ U$ imply $S \subseteq (\task{B}\circ \task{A})^\dagger \circ U$:

\[\tikzfig{seqcompcheck}\]

For parallel composition to be well-defined, we need to show that $S \subseteq \task{A}^\dagger \circ U$ and $T \subseteq \task{B}^\dagger \circ V$ imply $S \times T \subseteq (\task{A}\boxtimes \task{B})^\dagger \circ (U \times V)$:

\[\tikzfig{parcompcheck}\]

The remaining checks are all straightforward, on similar lines.

Any sub-SMC $\mathcal{C}$ of $\Rel$ embeds into the associated theory of coarse-grained tasks $\overline{\mathcal{C}}$.
The embedding is the functor—faithful and injective on objects—defined by sending each set to the set of its singleton subsets:

\begin{align*}
F(X) &:= \suchthat{\{x\}}{x \in X}\\
F\left(\task{A}: X \rightarrow Y\right) &:= \quotask{\task{A}}{\bar{X}}{\bar{Y}} = \suchthat{
\{x\} \mapsto \{y\}
x \tmapsto{\task{A}} y
\end{align*}

It is straightforward to check that the mapping defined above is a strict monoidal functor, i.e. that it preserves both sequential and parallel composition exactly (as well as identities, and symmetry isomorphisms, in this case).

Let $\mathcal{C}$ be a sub-SMC of $\Rel$.
The associated theory of coarse-grained tasks $\overline{\mathcal{C}}$ embeds back into $\Rel$, via the identity functor:

\[
F(\bar{X}) := \bar{X}
\hspace{2cm}
F\left(\quotask{\task{A}}{\bar{X}}{\bar{Y}}\right) := \quotask{\task{A}}{\bar{X}}{\bar{Y}}
\]

The functor is strict monoidal when restricted to (the embedding of) $\mathcal{C}$ (into $\overline{\mathcal{C}}$).
It is not strict (or strong) monoidal in general, because the tensor product on sets of attributes is not the same as the tensor product on sets of states:

\[
\bar{X} \boxtimes \bar{Y} := \suchthat{S \times T}{S \in \bar{X},\, T \in \bar{Y}}
\neq \suchthat{(S, T)}{S \in \bar{X},\, T \in \bar{Y}} = \bar{X} \times \bar{Y}
\]

It is, however, lax monoidal, with the following structure morphisms:

\[
\left[(S, T) \mapsto S \times T\right]: \bar{X} \times \bar{Y} \rightarrow \bar{X} \boxtimes \bar{Y}
\hspace{2cm}
\left[\{*\} \mapsto *\right]: \bar{1} \rightarrow 1
\]

To see this, it suffices to observe that not only do $S \subseteq \task{A}^\dagger \circ U$ and $T \subseteq \task{B}^\dagger \circ V$ imply $S \times T \subseteq (\task{A}\boxtimes \task{B})^\dagger \circ (U \times V)$, but also $S \times T \subseteq (\task{A}\boxtimes \task{B})^\dagger \circ (U \times V)$ implies both $S \subseteq \task{A}^\dagger \circ U$ and $T \subseteq \task{B}^\dagger \circ V$.

§ CONCLUSION AND HISTORICAL REMARKS

We have given categorical semantics for constructor theory in its most general form, interpreting to the best of our ability the desired mathematical foundations both set out in Deutsch's original paper [17] and expressed to us by current practitioners.
We remark, without further comment, that the diagrammatic syntax we have used to formally incarnate constructor theory is also interpretable in other symmetric monoidal categories.
A long form presentation of the same content with worked examples from the constructor theory literature is in preparation.

We close with two historical case studies intended to inform constructor theorists of the topically-relevant history of process theories as applied to quantum theory, and to encourage the pursuit of the possible-impossible dichotomy by illustrating some of the fruitful outcomes that may result.

Process theories arose from counterfactual reasoning.

Possibility, read as what could happen, is at the heart of constructor theory: here, constructor theory and process theories share a lineage of counterfactual reasoning, tracing back to Aristotle's distinction between “actual” and “potential”.
One ancestor of process theories along this lineage is the Geneva school of quantum logic [32, 29], which defined the properties of physical systems in terms of experiments that could be performed [31], resulting in the linearity of physical processes [19] due to an adjunction between cause and consequence (cf. weakest precondition semantics in computer science [27]).
This led to the development of a process-theoretic framework for quantum theory, which encoded the structural consequences of an adjunction between causes and consequences in terms of a quantaloid [11].
The underlying structure of spaces (= quantum logics) was induced at the level of processes, and efforts were made to cast the composition of systems in those terms through process-state duality [9].
However, the current success of process theories relies on dumping quantum logics and replacing them with specially chosen processes (cf. cups and caps [1]).
A process theory, when formulated as a concrete symmetric monoidal category, is about possible and impossible processes that obey the axioms of the corresponding category.
Reconstructions of quantum theory in terms of process theories turn these categorical axioms into physical postulates that are considered more reasonable by some [23, 33].

Quantum from no-cloning.

In constructor theory, the cut between possible and impossible tasks is used to define theories, and it has been suggested that the impossibility to clone should yield quantum theory, at least in a broad sense.
In categorical quantum mechanics [1, 15, 14], dating back to at least 2006, classicality was indeed defined by the ability to clone [13]: this has resulted in the development of spiders [12] and the ZX-calculus [10], now a prominent formalism in quantum foundations, quantum computation, and general education on quantum theory.

§ ACKNOWLEDGEMENTS

With many thanks to Maria Violaris and Anicet Tibau Vidal for their clarity and patience when presenting constructor theory at the Wolfson quantum foundations discussion, and to Nicola Pinzani for his insights in conversation with one of the authors.

[1]
authorS. Abramsky &
authorB. Coecke (year2004):
titleA categorical semantics of quantum protocols.
In: booktitleProceedings of the 19th Annual IEEE
Symposium on Logic in Computer Science (LICS), pp.
pages415–425, 10.5555/1018438.1021878.

[2]
authorMario Alvarez-Picallo,
authorDan Ghica, authorDavid
Sprunger & authorFabio Zanasi (year2022): titleRewriting
for Monoidal Closed Categories: 7th International Conference on
Formal Structures for Computation and Deduction, FSCD 2022.
journal7th International Conference on Formal
Structures for Computation and Deduction (FSCD 2022),
<http://www.scopus.com/inward/record.url?scp=85133671634   partnerID=8YFLogxK>.
notePublisher: Schloss Dagstuhl.

[3]
authorJohn C. Baez &
authorJade Master
(year2020): titleOpen Petri Nets.
journalMathematical Structures in Computer
Science volume30(number3), pp.
pages314–341, 10.1017/S0960129520000043.
noteArXiv:1808.05415 [cs, math].

[4]
authorGuillaume Boisseau &
authorPaweł Sobociński
(year2022): titleString Diagrammatic
Electrical Circuit Theory.
journalElectronic Proceedings in Theoretical
Computer Science volume372, pp. pages178–191,
noteArXiv:2106.07763 [cs].

[5]
authorFilippo Bonchi,
authorRobin Piedeleu,
authorPawel Sobociński &
authorFabio Zanasi
(year2019): titleGraphical Affine Algebra.
In: booktitle2019 34th Annual ACM/IEEE
Symposium on Logic in Computer Science (LICS), pp.
pages1–12, 10.1109/LICS.2019.8785877.

[6]
authorFilippo Bonchi,
authorPawel Sobocinski &
authorFabio Zanasi
(year2017): titleInteracting Hopf
journalJournal of Pure and Applied Algebra
volume221(number1), pp. pages144–184,
noteArXiv:1403.7048 [cs, math].

[7]
authorFilippo Bonchi,
authorPawel Sobociński &
authorFabio Zanasi
(year2014): titleA Categorical Semantics of
Signal Flow Graphs.
volumeCONCUR 2014 - Concurrency Theory - 25th
International Conference, 10.1007/978-3-662-44584-6_30.

[8]
authorKenta Cho & authorBart
Jacobs (year2019):
titleDisintegration and Bayesian Inversion via String
journalMathematical Structures in Computer
Science volume29(number7), pp.
pages938–971, 10.1017/S0960129518000488.
noteArXiv:1709.00322 [cs].

[9]
authorB. Coecke (year2000):
titleStructural characterization of compoundness.
journalInternational Journal of Theoretical
Physics volume39, pp. pages585–594,

[10]
authorB. Coecke &
authorR. Duncan (year2011):
titleInteracting quantum observables: categorical algebra
and diagrammatics.
journalNew Journal of Physics
volume13, p. pages043016,

[11]
authorB. Coecke, authorD.J.
Moore & authorI. Stubbe (year2001): titleQuantaloids
describing causation and propagation of physical properties.
journalFoundations of Physics Letters
volume14, pp. pages133–146,

[12]
authorB. Coecke,
authorÉ. O. Paquette &
authorD. Pavlović
(year2010): titleClassical and quantum
In editorS. Gay &
editorI. Mackie, editors: booktitleSemantic Techniques in Quantum Computation,
publisherCambridge University Press, pp. pages29–69,

[13]
authorB. Coecke &
authorD. Pavlovic
(year2007): titleQuantum measurements without
In editorG. Chen,
editorL. Kauffman &
editorS. Lamonaco, editors: booktitleMathematics of Quantum Computing and Technology,
publisherTaylor and Francis, pp. pages567–604,

[14]
authorBob Coecke &
authorStefano Gogioso
(year2023): titleQuantum in Pictures: A
New Way to Understand the Quantum World.
publisherCambridge Quantum.

[15]
authorBob Coecke & authorAleks
Kissinger (year2017):
titlePicturing Quantum Processes: A First Course
in Quantum Theory and Diagrammatic Reasoning.
publisherCambridge University Press,
addressCambridge, 10.1017/9781316219317.

[16]
authorGeoffrey SH Cruttwell,
authorBruno Gavranović,
authorNeil Ghani, authorPaul
Wilson & authorFabio Zanasi (year2022): titleCategorical
foundations of gradient-based learning.
In: booktitleProgramming Languages and
Systems: 31st European Symposium on Programming, ESOP 2022, Held
as Part of the European Joint Conferences on Theory and Practice
of Software, ETAPS 2022, Munich, Germany, April 2–7, 2022,
Proceedings, publisherSpringer International Publishing Cham,
pp. pages1–28, 10.1007/978-3-030-99336-8_1.

[17]
authorDavid Deutsch
(year2013): titleConstructor theory.
volume190(number18), pp. pages4331–4359,

[18]
authorDavid Deutsch &
authorChiara Marletto
(year2015): titleConstructor theory of
journalProceedings of the Royal Society A:
Mathematical, Physical and Engineering Sciences volume471, p.
pages20140540, 10.1098/rspa.2014.0540.

[19]
authorC.-A. Faure, authorD. J.
Moore & authorC. Piron (year1995): titleDeterministic
evolutions and Schrödinger flows.
journalHelvetica Physica Acta
volume68(number2), pp. pages150–157.

[20]
authorTobias Fritz,
authorTomáš Gonda &
authorPaolo Perrone
(year2021): titleDe Finetti's Theorem in
Categorical Probability.
journalJournal of Stochastic Analysis
volume2(number4), 10.31390/josa.2.4.06.
noteArXiv:2105.02639 [cs, math, stat].

[21]
authorDan R. Ghica &
authorAchim Jung (year2016):
titleCategorical semantics of digital circuits.
In: booktitleProceedings of the 16th
Conference on Formal Methods in Computer-Aided Design,
seriesFMCAD '16, publisherFMCAD Inc,
addressAustin, Texas, pp. pages41–48,

[22]
authorStefano Gogioso
(year2019): titleA process-theoretic church of
the larger hilbert space.
journalarXiv preprint arXiv:1905.13117,

[23]
authorL. Hardy (year2011):
titleFoliable operational structures for general
probabilistic theories.
In editorH. Halvorson, editor:
booktitleDeep Beauty: Understanding the Quantum World
through Mathematical Innovation, publisherCambridge University
Press, pp. pages409–442, 10.1017/CBO9780511976971.013.

[24]
authorNathan Haydon &
authorPaweł Sobociński
(year2020): titleCompositional Diagrammatic
First-Order Logic.
In editorAhti-Veikko Pietarinen,
editorPeter Chapman,
editorLeonie Bosveld-de Smet,
editorValeria Giardino,
editorJames Corter &
editorSven Linker, editors: booktitleDiagrammatic Representation and Inference,
seriesLecture Notes in Computer Science,
publisherSpringer International Publishing,
addressCham, pp. pages402–418,

[25]
authorJules Hedges (year2015):
titleString diagrams for game theory,
noteArXiv:1503.06072 [cs, math].

[26]
authorJames Hefford,
authorVincent Wang &
authorMatthew Wilson
(year2020): titleCategories of Semantic
Concepts, 10.48550/arXiv.2004.10741.
noteArXiv:2004.10741 [quant-ph].

[27]
authorC. A. R. Hoare &
authorJ. He (year1987):
titleThe weakest prespecification.
journalInformation Processing Letters
volume24, pp. pages127–132,

[28]
authorBart Jacobs, authorAleks
Kissinger & authorFabio Zanasi (year2019): titleCausal
Inference by String Diagram Surgery,
noteArXiv:1811.08338 [cs, math].

[29]
authorJ. M. Jauch (year1968):
titleMathematical Foundations of Quantum Mechanics.

[30]
authorChiara Marletto
(year2021): titleThe Science of Can and
Can't: A Physicist's Journey Through the Land of
publisherAllen Lane, 10.1016/S0262-4079(21)00658-8.

[31]
authorD. J. Moore (year1999):
titleOn state spaces and property lattices.
journalStudies in History and Philosophy of
Modern Physics volume30(number1), pp.
pages61–83, 10.1016/S1355-2198(98)00033-1.

[32]
authorC. Piron (year1976):
titleFoundations of quantum physics.
publisherW. A. Benjamin.

[33]
authorJ. H. Selby, authorC. M.
Scandolo & authorB. Coecke (year2018):
titleReconstructing quantum theory from diagrammatic
journalarXiv preprint arXiv:1802.00367,

[34]
authorVincent Wang-Mascianica &
authorBob Coecke (year2021):
titleTalking Space: inference from spatial linguistic
meanings, 10.48550/arXiv.2109.06554.
noteArXiv:2109.06554 [cs].

[35]
authorMatthew Wilson,
authorJames Hefford,
authorGuillaume Boisseau &
authorVincent Wang
(year2021): titleThe Safari of Update
Structures: Visiting the Lens and Quantum Enclosures.
journalElectronic Proceedings in Theoretical
Computer Science volume333, pp. pages1–18,
noteArXiv:2005.05293 [quant-ph].


# Stability Problems on D-finite Functions

Shaoshi Chen, Ruyong Feng, Zewang Guo and Wei Lu  KLMM, Academy of Mathematics
and Systems Science
University of Chinese Academy of SciencesChinese Academy of Sciences, Beijing
100190, China schen, ryfeng<EMAIL_ADDRESS><EMAIL_ADDRESS>
(2023)

###### Abstract.

This paper continues the studies of symbolic integration by focusing on the
stability problems on D-finite functions. We introduce the notion of stability
index in order to investigate the order growth of the differential operators
satisfied by iterated integrals of D-finite functions and determine bounds and
exact formula for stability indices of several special classes of differential
operators. With the basic properties of stability index, we completely solve
the stability problem on general hyperexponential functions.

D-finite functions; stable Sets; symbolic integration

S. Chen was partially supported by the NSFC grants (No. 12271511 and No.
11688101), CAS Project for Young Scientists in Basic Research (Grant No.
YSBR-034), the Fund of the Youth Innovation Promotion Association (Grant No.
Y2022001), CAS, and the National Key Research and Development Project
2020YFA0712300. R. Feng, Z. Guo, W. Lu were partially supported by the NSFC
grants 11771433, 11688101, Beijing Natural Science Foundation under Grant
Z190004 and National Key Research and Development Project 2020YFA0712300.

††copyright: acmcopyright††journalyear: 2023††conference: ; ; ††ccs: Computing
methodologies Algebraic algorithms

##  1\. Introduction

New functions were introduced when certain integrals could not be evaluated in
term of a specific class of functions. We need to introduce the logarithmic
function $\log(x)$ since $1/x$ has no primitive in the field of rational
functions. The special functions, such as $\int\exp(x^{2})\,dx,\int
1/\log(x)\,dx$ etc., are introduced likewise since they are not elementary. We
can continue to study the integrals of the newly introduced functions, e.g.,
the indefinite integral of $\log(x)$ is $x\log(x)-x$. A natural question is
whether we need keep introducing new functions in order to integrate a given
function iteratively.

Motivated by irrationality proofs in number theory and the above question,
Chen initialized the dynamical aspect of symbolic integration by studying some
stability problems in differential fields in (chen2022ISSAC, ). For a given
special function $f$ in certain differential ring $(R,D)$, the stability
problem is deciding whether there exists a sequence $\\{g_{i}\\}_{i\geq 0}$ in
$R$ such that $f=D^{i}(g_{i})$ for all $i\in{\mathbb{N}}$. Such stable special
functions appear in any integro-differential algebra, which is an algebra
equipped with derivation and integration operators. The theory of integro-
differential algebras has been developed in (Guo2014, ). Two basic examples of
integro-differential algebras are the ring of polynomials ${\mathbb{C}}[x]$
and the ring $C^{\infty}({\mathbb{R}})$ of smooth functions on ${\mathbb{R}}$.
From the algorithmic point of view, the algebra $C^{\infty}({\mathbb{R}})$ is
too big and we are more interested in some subalgebra whose elements are
computable, such as the subalgebras ${\mathbb{C}}[x,\log(x)]$ and
${\mathbb{C}}[x,\exp(x)]$. To find more rich examples, it is necessary to
classify certain class of functions that are iteratively integrable in this
class.

Focusing on elementary functions, Chen in (chen2022ISSAC, ) had solved the
stability problems on three families of special functions including rational
functions, logarithmic functions, and exponential functions. The main goal of
this paper is to continue the work (chen2022ISSAC, ) by focusing on D-finite
functions using the language of differential operators.

The notion of D-finite power series was first introduced by Stanley
(Stanley1980, ) in 1980 in the univariate case and later studied by Lipshitz
in the multivariate case (Lipshitz1989, ). D-finite functions are also called
holonomic functions that had played a significant role in Zeilberger’s method
of creative telescoping (Zeilberger1990, ; Wilf1992, ). These series, like
algebraic numbers, can be algorithmically manipulated via its defining linear
differential equations (AbramovLeLi2005, ; Salvy2019, ). For a comprehensive
introduction to theory and algorithms for D-finite functions, one can see the
coming monograph by Kauers (DfiniteBook, ). The indefinite integration problem
on D-finite functions was studied by Abramov and van Hoeij in
(AbramovHoeij1997, ). The main goal of this paper is to investigate Abramov-
van Hoeij’s algorithm iteratively.

The remainder of this paper is organized as follows. We recall some basic
terminologies in differential algebra and then define the notion of principal
integrals related to iterated integration in Section 2. We will focus on
studying the order of the differential operators satisfied by principal
integrals in Section 3, which inspires us to introduce the notion of stability
index. In Section 4, we will determine the stability indices of two special
classes of differential operators including Katz’s operators and first-order
operators. With the help of stability index, we will completely solve the
stability problem for general hyperexponential functions in Section 5 which
generalizes the results in (chen2022ISSAC, ). As an application, we present an
exact formula for the stability index of a special class of rational functions
in Section 6.

##  2\. Principal integrals

Throughout this paper, let $C$ be any algebraically closed field of
characteristic zero and $k=C(x)$ be the differential field with the usual
derivation ′ such that $x^{\prime}=1$ and $c^{\prime}=0$ for all $c\in C$. Let
$\mathcal{K}$ be a differential closure of $C(x)$ (see Kolchin’s book
(kolchin, ) for the existence of such closures). Any system of algebraic
differential equations with coefficients from $k$ has solutions in
$\mathcal{K}$ if it has any solution in some differential extension of $k$.
Let $k\langle D\rangle$ be the ring of linear differential operators with
coefficients in $k$ in which we have

$D\cdot f=f\cdot D+f^{\prime},\quad\text{for any $f\in k$}.$

The ring $k\langle D\rangle$ is a left Euclidean domain in which any left
ideal is principal (Ore1933, ). For an $m\in\mathbb{Z}$, $\mathbb{Z}_{\leq m}$
(resp., we let $\mathbb{Z}_{\geq m}$) stand for the set of all integers not
greater than $m$ (resp., not less than $m$).

Let $L$ be a nonzero operator in $k\langle D\rangle$. Write

$L=\sum_{i=0}^{n}a_{i}D^{i},\quad\text{where $a_{i}\in k$ and $a_{n}\neq 0$}.$

The integer $n$ is called the order of $L$, denoted by
$\operatorname{ord}(L)$, and $a_{n}$ is called the leading coefficient of $L$,
denoted by $\operatorname{lc}(L)$. If $a_{n}=1$, then $L$ is called a monic
operator. The adjoint operator of $L$, denoted by $L^{*}$, is defined to be

$L^{*}:=\sum_{i=0}^{n}(-D)^{i}a_{i}.$

The field $\mathcal{K}$ can be equipped with a left ${k\langle
D\rangle}$-module structure with the action $L(f)=\sum_{i=0}^{n}a_{i}f^{(i)}$
for any $L=\sum_{i=0}^{n}a_{i}D^{i}\in{k\langle D\rangle}$ and
$f\in\mathcal{K}$. The annihilating ideal

$\text{Ann}_{k\langle D\rangle}(f):=\\{P\in{k\langle D\rangle}\mid P(f)=0\\}$

is a left ideal of ${k\langle D\rangle}$. Since ${k\langle D\rangle}$ is a
left Euclidean domain, we have $\text{Ann}_{k\langle D\rangle}(f)=\langle
L\rangle$ for some monic operator $L\in{k\langle D\rangle}$.

###### Definition 2.1.

An element $f\in\mathcal{K}$ is said to be  _D-finite_ over $k$ if
$\text{Ann}_{k\langle D\rangle}(f)=\langle L\rangle$ for some nonzero and
monic operator $L\in{k\langle D\rangle}$. We call $L$ the defining operator
for $f$, denoted by $L_{f}$, whose order is called the order of $f$, denoted
by $\operatorname{ord}(f)$. For convenience, we set
$\operatorname{ord}(f)=\infty$ if $f$ is not D-finite.

Lipshitz (Lipshitz1989, ) showed that the set of all D-finite elements over
$k$ forms a subalgebra of $\mathcal{K}$, which is also closed under taking
derivatives and integrals. We will investigate how the order changes when
integrating a D-finite function.

###### Definition 2.2.

For $f\in\mathcal{K}$ and $i\in\mathbb{Z}_{>0}$, $g\in\mathcal{K}$ is called
an $i$-th primitive or an $i$-th integral of $f$ if $f=D^{i}(g)$. When $i=1$,
we simply call $g$ an integral of $f$.

Suppose $f$ is a D-finite function and $g_{i}$ is an $i$-th integral of $f$.
Then $g_{i}$ is also D-finite and
$\operatorname{ord}(g_{i})\leq\operatorname{ord}(f)+i$. Set

$\mathcal{N}_{i}(f)=\min\\{\operatorname{ord}(g)\mid\mbox{$g$ is an $i$-th
integral of $f$}\\}.$

The following example shows that different i-th integrals of a given function
may have different orders.

###### Example 2.3.

Let $f=\exp(x)$. Then $f$ itself is a second integral of $f$ and
$\operatorname{ord}(f)=1$. Since every second integral of $f$ must be of order
not less than 1, $\mathcal{N}_{2}(f)=1$. On the other hand, there exist second
integrals of $f$ that are of order greater than 1. In fact, each second
integral of $f$ is of the form $\exp(x)+\alpha x+\beta$ with $\alpha,\beta\in
C$. Assume that not all $\alpha,\beta$ are zero. We claim that
$\operatorname{ord}(\exp(x)+\alpha x+\beta)=2$. First, as $\exp(x)+\alpha
x+\beta$ is not hyperexponential, $\exp(x)+\alpha x+\beta$ can not be
annihilated by any first-oder operator. Second, if $\alpha\neq 0$ then
$\exp(x)+\alpha x+\beta$ is annihilated by

$\left(x+\frac{\beta}{\alpha}+1\right)D^{2}-\left(x+\frac{\beta}{\alpha}\right)D-1,$

and if $\alpha=0$ and $\beta\neq 0$ then $\exp(x)+\beta$ is annihilated by
$D^{2}-D$. So $\operatorname{ord}(\exp(x)+\alpha x+\beta)=2$ and the claim is
shown.

The example above motivates the following notion of principal integrals.

###### Definition 2.4.

The $i$-th integrals of order $\mathcal{N}_{i}(f)$ are called the principal
$i$-th integrals of $f$.

It can happen that all integrals are principal as shown in the following
example.

###### Example 2.5.

Let $f=\frac{1}{x}$. Then each principal second integral of $f$ is of the form
$x\ln(x)+\alpha x+\beta$ with $\alpha,\beta\in C$. It is easy to check that
$x\ln(x)+\alpha x+\beta$ is annihilated by

$(x-\beta)D^{2}-D+\frac{1}{x}.$

A similar argument as in Example 2.3 implies that
$\operatorname{ord}(x\ln(x)+\alpha x+\beta)=2$ for all $\alpha,\beta\in C$.

It was proved in (AbramovHoeij1997, ; AbramovHoeij1999, ) that
$\mathcal{N}_{1}(f)=\operatorname{ord}(f)$ if and only if $L_{f}^{*}(y)=1$ has
a solution in $k$. If $L_{f}^{*}(y)=1$ has no solution in $k$ then
$\mathcal{N}_{1}(f)=\operatorname{ord}(f)+1$ and moreover $L_{g}=L_{f}D$ for
any integrals $g$ of $f$. Suppose that $L_{f}^{*}(y)=1$ has a solution $l$ in
$k$. Then $(1-lL_{f})^{*}(1)=0$ and so there is a unique $H_{l}\in{k\langle
D\rangle}$ of order $n-1$ such that

$1-lL_{f}=DH_{l}$

where $n=\operatorname{ord}(f)$. Note that $-l$ is the leading coefficient of
$H_{l}$. Set $g=H_{l}(f)$. Then $g$ is an integral of $f$ and

$L_{g}=\frac{1}{l}(1-H_{l}D).$

For a nonzero operator $P\in{k\langle D\rangle}$ and $q\in C[x]$, define

$\delta(P,q)=\begin{cases}1&\mbox{$P^{*}(y)=q$ has a solution in $C(x)$}\\\
0&\mbox{otherwise}\end{cases}.$

When $q=1$, we abbreviate $\delta(P,q)$ to $\delta(P)$. The above discussions
motivate the definition below.

###### Definition 2.6.

Suppose that $L$ is a nonzero monic operator in ${k\langle D\rangle}$. A
principal integral of $L$ is defined to be

$\begin{cases}LD&\delta(L)=0\\\ \frac{1}{l}(1-H_{l}D)&\delta(L)=1\end{cases}$

where $l\in k$ is a solution of $L^{*}(y)=1$ and $H_{l}$ is the unique
operator in ${k\langle D\rangle}$ of order $\operatorname{ord}(L)-1$ such that
$lL+DH_{l}=1$. We also call $\frac{1}{l}(1-H_{l}D)$ the principal integral of
$L$ with respect to $l$. An $i$-th principal integral of $L$ is defined
iteratively.

###### Remark 2.7.

Notice that in the case $\delta(L)=1$ principal integrals of $L$ depend on the
rational solutions of $L^{*}(y)=1$ and thus they are generally not unique. For
example, let $L=D$. The adjoint $L^{*}$ of $L$ is $-D$. For every $c\in C$,
$-x+c$ is a rational solution of $L^{*}(y)=1$. One sees that $x-c$ satisfies
that $(-x+c)D+D(x-c)=1$. Since

$\frac{1}{-x+c}(1-(x-c)D)=D-\frac{1}{x-c},$

by definition, $D-\frac{1}{x-c}$ is a principal integral of $L$ for any $c\in
C$. Therefore the principal integrals of $L$ are not unique. However they have
the same order.

###### Lemma 2.8.

Suppose that $f\in\mathcal{K}$ and $L_{i}$ is an $i$-th principal integral of
$L_{f}$. Then there is an $i$-th integral of $f$, say $g_{i}$, such that
$L_{i}=L_{g_{i}}$.

###### Proof.

We shall show the lemma by induction on $i$. The case $i=1$ follows from
Definition 2.6 and the discussions before Definition 2.6. Suppose that $i>1$
and the assertion holds for the case $i-1$. Let $L_{i-1}$ be an $(i-1)$-th
principal integral of $L_{f}$ and $L_{i}$ is a principal integral of
$L_{i-1}$. By induction hypothesis, there is an $(i-1)$-th integral $g_{i-1}$
of $f$ such that $L_{i-1}=L_{g_{i-1}}$. Since $L_{i}$ is a principal integral
of $L_{i-1}=L_{g_{i-1}}$, by induction hypothesis again, there is an integral
$g_{i}$ of $g_{i-1}$ such that $L_{i}=L_{g_{i}}$. The lemma then follows from
the fact that $g_{i}$ is an $i$-th integral of $f$.

In next section, we shall show that the $g_{i}$ in Lemma 2.8 is actually an
$i$-th principal integral of $f$. Furthermore, we shall show that
$\operatorname{ord}(L_{i})=\mathcal{N}_{i}(f)$, and Definition 2.4 and
Definition 2.6 are consistent in some sense.

##  3\. Orders of principal integrals

Throughout this section, $L$ is always a monic operator in ${k\langle
D\rangle}$. Suppose that $L_{i}$ is a principal $i$-th integral of $L$ for any
positive integer $i$. We are going to prove that
$\operatorname{ord}(L_{i+1})=\operatorname{ord}(L_{i})$ if and only if there
is a polynomial $p\in C[x]$ of degree $i$ such that $L_{i}^{*}(y)=p$ has a
solution in $k$. This generalizes the results in (AbramovHoeij1997, ;
AbramovHoeij1999, ) for the case when $i=1$. For a rational function $l\in k$,
$l$ is said to be rationally integrable if $l=D(h)$ for some $h\in k$.

###### Lemma 3.1.

Suppose that $P=1+MD$ and $l$ is a rational solution of $P^{*}(y)=p$, where
$M\in{k\langle D\rangle}$ and $p\in C[x]$. Then $l$ is rationally integrable.

###### Proof.

Note that $P^{*}=1-DM^{*}$. Since $l$ is a solution of $P^{*}(y)=p$ in $k$, we
have $l-D(M^{*}(l))=p$. Let $q\in C[x]$ be such that $p=q^{\prime}$. Then
$l=D(q+M^{*}(l))$. The lemma then follows from the fact that $q+M^{*}(l)\in
k$.

###### Proposition 3.2.

Suppose that $L_{0}=L$ and $L_{i+1}$ is a principal integral of $L_{i}$ for
any $i\geq 0$. Set $I_{-1}=1$ and for each $i\geq 0$ set

$I_{i}=\begin{cases}1&\delta(L_{i})=0\\\
D+\frac{D(l_{i})}{l_{i}}&\delta(L_{i})=1\end{cases}$

where $l_{i}\in k$ is a solution of $L_{i}^{*}(y)=1$ such that $L_{i+1}$ is
the principal integral of $L_{i}$ with respect to $l_{i}$. Then for each
$n\geq 0$,

(1) $LD^{n}=\left(\prod_{i=-1}^{n-1}I_{i}\right)L_{n}.$

###### Proof.

We shall prove the proposition by induction on $n$. The case $n=0$ is clear.
Assume that $n>0$ and the assertion holds for $n-1$. By induction hypothesis,

$LD^{n-1}=\left(\prod_{i=-1}^{n-2}I_{i}\right)L_{n-1}.$

If $\delta(L_{n-1})=0$ then $L_{n}=L_{n-1}D$ and $I_{n-1}=1$. Thus

$LD^{n}=LD^{n-1}D=\left(\prod_{i=-1}^{n-2}I_{i}\right)L_{n-1}D=\left(\prod_{i=-1}^{n-1}I_{i}\right)L_{n}.$

If $\delta(L_{n-1})=1$ then $l_{n-1}L_{n-1}+DH_{l_{n-1}}=1$ and
$L_{n}=\frac{1}{l_{n-1}}(1-H_{l_{n-1}}D)$. These imply that

$\displaystyle L_{n-1}D$
$\displaystyle=\frac{1}{l_{n-1}}(1-DH_{l_{n-1}})D=\frac{1}{l_{n-1}}D(1-H_{l_{n-1}}D)$
$\displaystyle=\frac{1}{l_{n-1}}Dl_{n-1}L_{n}=\left(D+\frac{D(l_{n-1})}{l_{n-1}}\right)L_{n}=I_{n-1}L_{n}.$

Therefore

$LD^{n}=LD^{n-1}D=\left(\prod_{i=-1}^{n-2}I_{i}\right)L_{n-1}D=\left(\prod_{i=-1}^{n-1}I_{i}\right)L_{n}.$

The assertion holds for all nonnegative integers $n$.

###### Lemma 3.3.

Suppose that $L_{n}$ is a principal integral of $L_{n-1}$. Then for every
$p\in C[x]$, $\delta(L_{n},p)=\delta(L_{n-1},q)$ for some $q\in C[x]$ with
$p=q^{\prime}$. In other words, $L_{n}^{*}(y)=p$ has a solution in $k$ if and
only if $L_{n-1}^{*}(y)=q$ has a solution in $k$.

###### Proof.

Assume that $\delta(L_{n-1})=0$. Then $L_{n}=L_{n-1}D$ and thus
$L_{n}^{*}=-DL_{n-1}^{*}$. One can verify that for each $h\in k$,
$L_{n}^{*}(h)=p$ if and only if $L_{n-1}^{*}(-h)=q$ for some $q\in C[x]$ with
$p=q^{\prime}$. Now suppose that $\delta(L_{n-1})=1$ and $L_{n}$ is the
principal integral of $L_{n-1}$ with respect to $l_{n-1}$. Then
$L_{n}=1/l_{n-1}(1-H_{l_{n-1}}D)$, where $H_{l_{n-1}}\in{k\langle D\rangle}$
satisfies that $l_{n-1}L_{n-1}+DH_{l_{n-1}}=1$. Suppose that $h\in k$ is a
solution of $L_{n}^{*}(y)=p$. Then $h/l_{n-1}$ is a solution of
$(1-H_{l_{n-1}}D)^{*}(y)=p$ in $k$. Due to Lemma 3.1, there is a $g\in k$ such
that $D(g)=h/l_{n-1}$. Since
$l_{n-1}L_{n-1}D=D-DH_{l_{n-1}}D=D(1-H_{l_{n-1}}D)$, one has that

$\displaystyle DL_{n-1}^{*}(l_{n-1}g)$
$\displaystyle=DL_{n-1}^{*}l_{n-1}(g)=(1-H_{l_{n-1}}D)^{*}D(g)$
$\displaystyle=(1-H_{l_{n-1}}D)^{*}(h/l_{n-1})=p.$

Let $\tilde{q}\in C[x]$ be such that $D(\tilde{q})=p$. Then
$D(L_{n-1}^{*}(l_{n-1}g)-\tilde{q})=0$ and thus
$L_{n-1}^{*}(l_{n-1}g)-\tilde{q}=c\in C$. Set $q=\tilde{q}+c$. Then
$L_{n-1}^{*}(l_{n-1}g)=q$. Conversely, assume that $h$ is a solution of
$L_{n-1}^{*}(y)=q$ for some $q\in C[x]$ with $p=q^{\prime}$. Then
$DL_{n-1}^{*}(h)=p$. Set $\tilde{h}=l_{n-1}D(h/l_{n-1})$. One then has that

$\displaystyle L_{n}^{*}(\tilde{h})$
$\displaystyle=(1-H_{l_{n-1}}D)^{*}(\tilde{h}/l_{n-1})=(1-H_{l_{n-1}}D)^{*}D(h/l_{n-1})$
$\displaystyle=(1+DH_{l_{n-1}}^{*})D\frac{1}{l_{n-1}}(h)=D(1+H_{l_{n-1}}^{*}D)\frac{1}{l_{n-1}}(h)$
$\displaystyle=D\left(\frac{1}{l_{n-1}}(1-DH_{l_{n-1}})\right)^{*}(h)=DL_{n-1}^{*}(h)=p.$

In other words, $L_{n}^{*}(y)=p$ has a solution in $k$.

###### Proposition 3.4.

Let $L_{i}$ be as in Proposition 3.2. Then

$\delta(L_{n},p)=\delta(LD^{n},p)$

for any $p\in C[x]\setminus\\{0\\}$ and nonnegative integer $n$.

###### Proof.

We shall prove the assertion by induction on $n$. The case $n=0$ is clear,
because $L_{0}=L=LD^{0}$ in this case. Suppose that $n>0$ and the assertion
holds for the case $n-1$. Consider the case $n$. It suffices to show that
$\delta(L_{n},p)=1$ if and only if $\delta(LD^{n},p)=1$. Assume that
$\delta(L_{n},p)=1$. Lemma 3.3 implies that $\delta(L_{n-1},q)=1$ for some
$q\in C[x]$ with $p=q^{\prime}$. By induction hypothesis,
$\delta(LD^{n-1},q)=1$, i.e. there is an $r\in k$ such that
$(LD^{n-1})^{*}(r)=q$. Since $(LD^{n})^{*}=-D(LD^{n-1})^{*}$, one sees that
$(LD^{n})^{*}(-r)=D((LD^{n-1})^{*}(r))=q^{\prime}=p$, i.e.
$\delta(LD^{n},p)=1$. Conversely, assume that $\delta(LD^{n},p)=1$. Then
$\delta(LD^{n-1},\tilde{q})=1$ for some $\tilde{q}\in C[x]$ with
$D(\tilde{q})=p$. By induction hypothesis again,
$\delta(L_{n-1},\tilde{q})=1$. By Lemma 3.3 again, $\delta(L_{n},p)=1$. Hence
the assertion holds for the case $n$.

###### Corollary 3.5.

Let $L_{i}$ be as in Proposition 3.2. Then
$\operatorname{ord}(L_{i+1})=\operatorname{ord}(L_{i})$ if and only if
$\delta(L,q)=1$ for some $q\in C[x]$ of degree $i$.

###### Proof.

From Definition 2.6, $\operatorname{ord}(L_{i+1})=\operatorname{ord}(L_{i})$
if and only if $\delta(L_{i})=\delta(L_{i},1)=1$. Note that
$\delta(L_{i})=\delta(L_{i},c)$ for any nonzero $c\in C$. Using Lemma 3.3
repeatedly, there is a $q\in C[x]$ of degree $i$ such that

$\delta(L,q)=\delta(L_{1},q^{\prime})=\dots=\delta(L_{i},i!\operatorname{lc}(q))=\delta(L_{i}).$

In other words, for such $q$, $\delta(L_{i})=1$ if and only if
$\delta(L,q)=1$. Hence $\operatorname{ord}(L_{i+1})=\operatorname{ord}(L_{i})$
if and only if $\delta(L,q)=1$ for some $q\in C[x]$ of degree $i$.

###### Lemma 3.6.

Let $f\in\mathcal{K}$ and $L_{i}$ as in Proposition 3.2 with $L=L_{f}$. Then
$\operatorname{ord}(L_{i})=\mathcal{N}_{i}(f)$.

###### Proof.

Set

$S_{i}(f)=\\{0\leq j\leq i-1\mid\delta(L_{f}D^{j})=1\\}.$

Then by Proposition 3.4,
$\operatorname{ord}(L_{i})=i+\operatorname{ord}(f)-|S_{i}(f)|$. Therefore, it
suffices to show that $|S_{i}(f)|=i-\mathcal{N}_{i}(f)+\operatorname{ord}(f)$.
We shall prove this by induction on $i$. The case $i=1$ follows from the fact
that $\mathcal{N}_{1}(f)=\operatorname{ord}(f)$ if and only if
$\delta(L_{f})=1$. Suppose that $i>1$ and the assertion holds true for the
case $i-1$. Let $g$ be an $i$-th principal integral of $f$. Then any
$(i-1)$-th integral $h$ of $D^{i-1}(g)$ is an $i$-th integral of $f$. Hence
$\operatorname{ord}(h)\geq\operatorname{ord}(g)$ and so $g$ is an $(i-1)$-th
principal integer of $D^{i-1}(g)$. In other words,
$\mathcal{N}_{i-1}(D^{i-1}(g))=\mathcal{N}_{i}(f)$. By induction hypothesis,

$S_{i-1}(D^{i-1}(g))=i-1-\mathcal{N}_{i}(f)+\operatorname{ord}(D^{i-1}(g)).$

Assume that $D^{i-1}(g)$ is a principal integral of $f$. Set
$\tilde{L}_{1}=L_{D^{i-1}(g)}$. Let $\tilde{L}_{j+1}$ be a principal integral
of $\tilde{L}_{j}$ for $1\leq j\leq i-1$. As $\tilde{L}_{1}$ is a principal
integral of $L_{f}$, $\tilde{L}_{j}$ is a $j$-th principal integral of
$L_{f}$. By Proposition 3.4 $\delta(\tilde{L}_{1}D^{j})=1$ if and only if
$\delta(\tilde{L}_{j+1})=1$, and so if and only if $\delta(L_{f}D^{j+1})=1$.
Thus $\\{s+1\mid s\in S_{i-1}(D^{i-1}(g))\\}\subset S_{i}(f).$ On the other
hand, one has that $0\in S_{i}(f)$ if and only if
$\operatorname{ord}(D^{i-1}(g))=\operatorname{ord}(f)$. Hence $|S_{i}(f)|$ is
not less than

$\displaystyle|\\{s+1\mid s\in
S_{i-1}(D^{i-1}(g))\\}|+1+\operatorname{ord}(f)-\operatorname{ord}(D^{i-1}(g))$
$\displaystyle\geq
i-1-\mathcal{N}_{i}(f)+\operatorname{ord}(D^{i-1}(g))+1+\operatorname{ord}(f)-\operatorname{ord}(D^{i-1}(g))$
$\displaystyle=i-\mathcal{N}_{i}(f)+\operatorname{ord}(f).$

If $|S_{i}(f)|>i-\mathcal{N}_{i}(f)+\operatorname{ord}(f)$ then
$\operatorname{ord}(L_{i})<\mathcal{N}_{i}(f)$. By Lemma 2.8 there is an
$i$-th integral $\tilde{g}$ of $f$ such that $L_{\tilde{g}}=L_{i}$. So
$\operatorname{ord}(\tilde{g})<\mathcal{N}_{i}(f)$, a contradiction. Hence
$|S_{i}(f)|=i-\mathcal{N}_{i}(f)+\operatorname{ord}(f)$. It remains to show
that $D^{i-1}(g)$ is a principal integral of $f$. Assume on the contrary that
$D^{i-1}(g)$ is not a principal integral of $f$. Then $L_{D^{i-1}(g)}=L_{f}D$
and $\mathcal{N}_{1}(f)=\operatorname{ord}(f)$. These imply that
$\delta(L_{f}D^{s+1})=1$ for all $s\in S_{i-1}(D^{i-1}(g))$ and
$\delta(L_{f})=1$. These imply that

$\displaystyle\operatorname{ord}(L_{i})$ $\displaystyle\leq
i+\operatorname{ord}(f)-|S_{i-1}(D^{i-1}(g))|-1$
$\displaystyle\leq\mathcal{N}_{i}(f)-\operatorname{ord}(D^{i-1}(g))+\operatorname{ord}(f)=\mathcal{N}_{i}(f)-1.$

Using a similar argument as before, one will obtain a contradiction. Thus
$D^{i-1}(g)$ must be a principal integral of $f$.

The following proposition shows that Definition 2.4 and Definition 2.6 are
consistent.

###### Proposition 3.7.

Suppose that $f\in\mathcal{K}$ and $L_{i}$ is an $i$-th principal integral of
$L_{f}$.

  1. (1)

Suppose that $g$ is an $i$-th integral of $f$ annihilated by $L_{i}$. Then $g$
is an $i$-th principal integral of $f$.

  2. (2)

Suppose that $g$ is an $i$-th principal integral of $f$. Then $L_{g}$ is an
$i$-th principal integral of $L_{f}$.

###### Proof.

(1). By Lemma 2.8,
$\operatorname{ord}(g)\leq\operatorname{ord}(L_{i})=\mathcal{N}_{i}(f)$. So
$g$ must be an $i$-th principal integral of $f$.

(2). We shall show the assertion by induction on $i$. The case $i=1$ follows
from the discussion after Proposition 4 of (AbramovHoeij1999, ). Suppose that
$i>1$ and the assertion holds true for the case $i-1$. The proof of Lemma 2.8
implies that $g$ is an $(i-1)$-th principal integral of $D^{i-1}(g)$ and
$D^{i-1}(g)$ is a principal integral of $f$. By induction hypothesis, $L_{g}$
is an $(i-1)$-th principal integral of $L_{D^{i-1}(g)}$ and $L_{D^{i-1}(g)}$
is a principal integral of $L_{f}$. Hence $L_{g}$ is an $i$-th principal
integral of $L_{f}$.

Given a nonzero $P\in{k\langle D\rangle}$, there exist a nonzero polynomial
${\rm ind}^{P}(s)\in C[s]$ and an integer $\sigma^{P}$ such that for any
$s\in\mathbb{Z}$,

$P(x^{s})={\rm ind}^{P}(s)x^{s+\sigma^{P}}(1+c_{1}x^{-1}+c_{2}x^{-2}+\dots)$

where $c_{i}\in C$ (see (vanderput-singer, , p. 102)). The polynomial ${\rm
ind}^{P}$ is usually called the indicial polynomial of $P$ at $\infty$. Remark
that $Pd$ and $P$ have the same indicial polynomial and
$\sigma^{Pd}=\sigma^{P}+\deg(d)$, where $d$ is a nonzero monic polynomial. In
the following, $V_{\mathbb{Z}_{\geq 0}}({\rm ind}^{P})$ stands for the set of
nonnegative integer solutions of ${\rm ind}^{P}(s)=0$ and we agree that
$\max\emptyset=-1$.

###### Theorem 3.8.

Let $d$ be a nonzero monic polynomial of minimal degree such that $dL$ is an
operator of polynomial coefficients. Set

(2) $\mathcal{B}(L)=\max\\{0,\max V_{\mathbb{Z}_{\geq 0}}({\rm
ind}^{L^{*}})+1+\sigma^{L^{*}}+\deg(d)\\}.$

Then for all $i\geq\mathcal{B}(L)$, there exists a polynomial $p$ of degree
$i$ such that $\delta(L,p)=1$.

###### Proof.

It is clear that $\delta(dL,p)=\delta(L,p)$ for any nonzero polynomial $p$. So
it suffices to consider $dL$. Note that ${\rm ind}^{(dL)^{*}}={\rm
ind}^{L^{*}}$ and $\sigma^{(dL)^{*}}=\sigma^{L^{*}}+\deg(d)$. Suppose that
$i\geq\mathcal{B}(L)$. Set $\ell=i-\sigma^{(dL)^{*}}$. Then $\ell\geq 0$ and
$(dL)^{*}(x^{\ell})$ is a polynomial. Furthermore,

$\displaystyle(dL)^{*}(x^{\ell})$ $\displaystyle={\rm
ind}^{P}(\ell)x^{\ell+\sigma^{(dL)^{*}}}+\mbox{lower terms}$
$\displaystyle={\rm ind}^{P}(\ell)x^{i}+\mbox{lower terms}.$

Since $\ell\geq\mathcal{B}(L)-\sigma^{(dL)^{*}}\geq\max V_{\mathbb{Z}_{\geq
0}}({\rm ind}^{P})+1$, ${\rm ind}^{(dL)^{*}}(\ell)\neq 0$ and thus
$\deg((dL)^{*}(x^{\ell}))=i$. Set $p=(dL)^{*}(x^{\ell})$. Then $p$ is a
polynomial as required.

In the case of D-finite power series, it has been proved in (chen2022ISSAC, ,
Theorem 4.5) that the order of $i$-th principal integrals of a given D-finite
function is uniformly bounded. We now provide a more explicit order bound in
terms of the information of indicial polynomials.

###### Definition 3.9.

The stability index of $L$, denoted by ${\rm Sind}(L)$, is defined to be the
minimal nonnegative integer $m$ satisfying that for each $i\geq m$ there
exists a polynomial $p_{i}$ of degree $i$ such that $\delta(L,p_{i})=1$. For
an $f\in\mathcal{K}$, the stability index of $f$ is defined to be the
stability index of $L_{f}$, also denoted by ${\rm Sind}(f)$.

###### Remark 3.10.

It is clear that ${\rm Sind}(L)\leq\mathcal{B}(L)$.

###### Example 3.11.

Let $L=D^{3}-xD$ which is the defining operator of a principal integral of
Airy function. One has that $\mathcal{B}(L)=1$. However $L$ is stable, i.e.
${\rm Sind}(L)=0$. In fact, one has that for every $i\geq 1$,

$L_{i}=D^{3}-xD+i$

is an $i$-th principal integral of $L$. Hence the bound in Remark 3.10 is not
tight.

###### Definition 3.12.

A nonzero operator $L\in{k\langle D\rangle}$ is said to be stable under
integration, or simply stable, if ${\rm Sind}(L)=0$. An $f\in\mathcal{K}$ is
said to be stable if ${\rm Sind}(f)=0$.

###### Remark 3.13.

$L$ is a nonzero operator and $L_{i}$ is an $i$-th principal integral of $L$
for all $i\geq 0$. Then Corollary 3.5 implies that
$\operatorname{ord}(L_{i})=\operatorname{ord}(L_{{\rm Sind}(L)})$ for all
$i\geq{\rm Sind}(L)$.

Below are several examples of stable operators.

###### Example 3.14.

Suppose that $\beta\in C$ is not a positive integer and $L=D+\beta/(x-c)$ for
some $c\in C$. Then for each $s\geq 1$,

$L^{*}((x-c)^{s})=-s(x-c)^{s-1}+\beta(x-c)^{s-1}=(\beta-s)x^{s-1}.$

Since $\beta$ is not a positive integer, $\beta-s\neq 0$ for any $s\geq 1$.
Hence $\deg(L^{*}((x-c)^{s}))=s-1$ for all $s\geq 1$ and then
$\delta(L,(\beta-s)(x-c)^{s-1})=1$ for all $s\geq 1$. So ${\rm Sind}(L)=0$,
i.e. $L$ is stable.

###### Example 3.15.

Suppose that $L=p(D)$, where $p\in C[z]$ is a polynomial of positive degree.
Let $s$ be the maximal integer such that $z^{s}$ divides $p$. Then for each
$i\geq s$,

$L^{*}(x^{s})=(-1)^{s}c_{s}{i\choose s}x^{i-s}+\mbox{lower terms}$

where $c_{s}$ is the trailing coefficient of $p$. Thus ${\rm Sind}(L)=0$, i.e.
$L$ is stable.

###### Example 3.16.

Suppose $\alpha,\beta,\gamma\in C$. Consider the hypergeometric differential
operator

$L=D^{2}+\frac{(\alpha+\beta+1)x-\gamma}{x(x-1)}D+\frac{\alpha\beta}{x(x-1)}.$

For each $s\geq 0$, an easy calculation yields that

$L^{*}(x^{s+1}(x-1))=(s+1-\alpha)(s+1-\beta)x^{s}-s(s+1-\gamma)x^{s-1}.$

Suppose that $\alpha-1\notin\mathbb{Z}_{\geq 0}$ and
$\beta-1\notin\mathbb{Z}_{\geq 0}$. Then $\deg((L^{*}(x^{s+1}(x-1)))=s$. Hence
$L$ is stable if neither $\alpha-1$ nor $\beta-1$ is a nonnegative integer.

##  4\. Stability Indices of special operators

For a general operator , even for a first order operator, it is difficult to
compute its stability index. In this section, we shall study the stability
indices of some special operators.

###### Proposition 4.1.

The set $P_{L}=\\{p\in C[x]|\delta(L,p)=1\\}$ is a $C$-vector space for
arbitrary nonzero operator $L$. Further if $L$ is stable, then $P_{L}=C[x]$.

###### Proof.

Suppose that $p_{1},p_{2}\in P_{L}$ and $a_{1},a_{2}\in C$. Then there are
$l_{1},l_{2}\in C(x)$ such that $L^{*}(l_{1})=p_{1}$ and $L^{*}(l_{2})=p_{2}$.
Then $L^{*}(a_{1}l_{1}+a_{2}l_{2})=a_{1}p_{1}+a_{2}p_{2}$. Hence
$a_{1}p_{1}+a_{2}p_{2}\in P_{L}$ and so $P_{L}$ is a $C$-vector space.

Suppose that $L$ is stable. Then for each $i\geq 0$, there is a nonzero
$h_{i}\in C[x]$ of degree $i$ such that $\delta(L,h_{i})=1$. Let $r_{i}\in
C(x)$ be a solution of $L^{*}(y)=h_{i}$. Note that $\\{h_{i}\mid i\geq 0\\}$
is a basis of $C[x]$ as a vector space over $C$. Assume that $p\in C[x]$.
Write $p=\sum_{i=0}^{\ell}c_{i}h_{i}$ where $\ell=\deg(p)$. Then
$\sum_{i=0}^{\ell}c_{i}r_{i}$ is a solution of $L^{*}(y)=p$ in $C(x)$.

###  4.1. Stability indices of Katz’s operators

In (Katz1987, ), Katz introduced a class of operators of the following form:

(3) $p(D)+q$

where $p,q\in C[z]\setminus C,p(0)=0$ and $\gcd(\deg(p),\deg(q))=1$. He proved
that differential Galois groups of the operators of the above form are large.
In this subsection, let us compute the stability indices of Katz’s operators.

###### Lemma 4.2.

Suppose that $L$ is of the form

$D^{n}+\frac{a_{n-1}}{a_{n}}D^{n-1}+\dots+\frac{a_{0}}{a_{n}},\,\,a_{i}\in
C[x],\,\,a_{n}\neq 0.$

Suppose further that $\gcd(a_{0}\ ,a_{1}\ ,\dots\ ,a_{n})=1$ and
$\deg(a_{0})>\deg(a_{i})-i$ for all $i=1,2,\dots,n$. Then ${\rm
Sind}(L)\leq\deg(a_{0})$.

###### Proof.

For each $s\geq 0$, a simple calculation yields that $L^{*}(a_{n}x^{s})$ is a
polynomial of degree $\deg(a_{0})+s$. Thus ${\rm Sind}(L)\leq\deg(a_{0})$.

###### Remark 4.3.

The bound given in 4.2 is better than the bound given in Theorem 3.8. In fact,
one has that ${\rm ind}^{L^{*}}(s)$ is a nonzero constant and
$\sigma^{L^{*}}=\deg(a_{0})$. Thus $\mathcal{B}(L)>\deg(a_{0})$.

###### Proposition 4.4.

Suppose that $L=p(D)+q(x)$, where $p,q\in C[z]$ and $p(0)=0$. Then ${\rm
Sind}(L)=\max\\{\deg(q),0\\}$.

###### Proof.

If $q(x)=0$ then from Example 3.15 one sees that

${\rm Sind}(L)=0=\max\\{\deg(q),0\\}.$

Assume that $q(x)\neq 0$. By Lemma 4.2, ${\rm Sind}(L)\leq\deg(q)$. It remains
to show that $\delta(L,d)=0$ for any polynomial $d$ of degree $\deg(q)-1$.
Suppose on the contrary that there is an $l\in k$ such that $L^{*}(l)$ is a
polynomial of degree $\deg(q)-1$. Suppose that $l$ is not a polynomial and
$c\in C$ is a pole of $l$. Then $c$ must be a pole of $L^{*}(l)$ and so
$L^{*}(l)$ can not be a polynomial. However, this implies that
$\deg(L^{*}(l))=\deg(q)+\deg(l)>\deg(q)-1$, a contradiction. Hence
$\delta(L,d)=0$ for any polynomial $d$ of degree $\deg(q)-1$.

###  4.2. Stability indices of first-order operators

In this subsection, we shall focus on studying the stability indices of first-
order operators. Suppose that $f\in k$ and $c\in C$. Let

$f=\sum_{i\geq\ell}a_{i}(x-c)^{i}\quad\text{with $a_{i}\in C$ and
$a_{\ell}\neq 0$}$

be the power series expansion of $f$ at $c$. Then $\ell$ is called the order
of $f$ at $c$, denoted by $\operatorname{ord}_{c}(f)$, and $a_{-1}$ is called
the residue of $f$ at $c$, denoted by $\operatorname{res}_{c}(f)$. Similarly,
we can define the order and residue of $f$ at $\infty$. Let

$f=\sum_{i\geq\ell}a_{i}\left(\frac{1}{x}\right)^{i},a_{i}\in C,a_{\ell}\neq
0$

be the power series expansion of $f$ at $\infty$. Then $\ell$ is called the
order of $f$ at $\infty$, denoted by $\operatorname{ord}_{\infty}(f)$, and
$a_{1}$ (not $a_{-1}$ in this case) is called the residue of $f$ at $\infty$,
denoted by $\operatorname{res}_{\infty}(f)$. Later one will see that the
residues of $f$ play an important role in estimating the stability index of
$D+f$. We shall use $\mathcal{S}(f)$ to denote the set of $c\in C$ such that
$c$ is a simple pole of $f$ and $\operatorname{res}_{c}(f)$ is a negative
integer. As usual, we use ${\rm den}(f)$ to denote the denominator of $f$.

###### Notation 4.5.

For a rational function $f\in k$, set

$\Delta(f)={\prod\limits_{c\in\mathcal{S}}(x-c)^{-\operatorname{res}_{c}(f)}}$

###### Lemma 4.6.

Suppose that $L=D+f$ and $r\in k$. If $L^{*}(r)$ is a nonzero polynomial then
the denominator of $r$ divides $\Delta(f)$. Furthermore, the zeros of the
denominator of $r$ has the same multiplicity as $\Delta(f)$.

###### Proof.

Set $r_{2}={\rm den}(r)$. If $r_{2}\in C$ then there is nothing to prove.
Suppose that $r_{2}\notin C$. Let $c\in C$ be a zero of $r_{2}$ with
multiplicity $m$. It suffices to show that $(x-c)^{m}$ divides $\Delta(f)$.
One has that $\operatorname{ord}_{c}(r)=-m$ and
$\operatorname{ord}_{c}(r^{\prime})=-m-1$. Write $r=r_{0}(x-c)^{-m}+\cdots$
and $f=f_{0}(x-c)^{\mu}+\cdots$, where $r_{0},f_{0}\in C$ and
$\mu=\operatorname{ord}_{c}(f)$. From $-r^{\prime}+fr=d$, one sees that
$-m-1=-m+\mu$ and $mr_{0}+f_{0}r_{0}=0$. These imply that $\mu=-1$ and
$f_{0}=-m$. Consequently, $c$ is a simple pole of $f$ and
$\operatorname{res}_{c}(f)=f_{0}=-m$. So $(x-c)^{m}$ divides $\Delta(f)$ and
the multiplicity of $c$ in $\Delta(f)$ is equal to $m$.

The following result reduces the stability problem on first order operators
into that on operators of special form.

###### Proposition 4.7.

Suppose that $L=D+f$ and $h\in C[x]$ is a non zero polynomial. If $L$ is
stable then $L-\frac{h^{\prime}}{h}$ is stable.

###### Proof.

For each $i\geq 0$, let $r_{i}$ be a solution of $L^{*}(y)=x^{i}h$ in $k$.
Such $r_{i}$ exists because of Proposition 4.1. A simple calculation yields
that

$\left(L-\frac{h^{\prime}}{h}\right)^{*}\left(\frac{r_{i}}{h}\right)=-\left(\frac{r_{i}}{h}\right)^{\prime}+\frac{fr_{i}}{h}-\frac{r_{i}h^{\prime}}{h}=\frac{-r_{i}^{\prime}+fr_{i}}{h}=x^{i}$

i.e. $\delta(L-h^{\prime}/h,x^{i})=1$ for all $i\geq 0$. So $L-h^{\prime}/h$
is stable.

The converse of Proposition 4.7 sometimes is not true. For example, $D$ is
stable but $D+1/x$ is not (see Corollary 6.4 for a proof). However, if $h$ is
a special divisor of the denominator of $f$ then the converse is still true.

###### Lemma 4.8.

Suppose that $L=D+f$ and $c\in C$ is a pole of $f$.

  1. (1)

For each $i\geq{\rm Sind}(L)+1$, there is a polynomial $p_{i}\in C[x]$ of
degree $i$ such that $L^{*}(y)=p_{i}/(x-c)$ has a solution in $k$.

  2. (2)

If $L$ is stable then for each $i\geq 0$, $L^{*}(y)=x^{i}/(x-c)$ has a
solution in $k$.

###### Proof.

(1). Write ${\rm den}(f)=(x-c)M$. One has that

$L^{*}(M)=-M^{\prime}+fM=-M^{\prime}+f_{1}/(x-c)=\tilde{M}+\alpha/(x-c)$

where $f_{1}$ is the numerator of $f$, $\tilde{M}\in C[x]$ and $\alpha\in C$.
For each $j\geq{\rm Sind}(L)$, let $d_{j}\in C[x]$ be a polynomial of degree
$j$ such that $L^{*}(y)=d_{j}$ has a solution $r_{j}\in k$. Fix an $i\geq{\rm
Sind}(L)+1$. It is easy to see that there are
$\ell>0,\beta_{1},\dots,\beta_{\ell}\in C$ such that $h=\tilde{M}+\sum_{j={\rm
Sind}(L)}^{\ell}{\beta}_{j}d_{j}$ is of degree $i-1$. Then

$L^{*}\left(M+\sum_{j={\rm
Sind}(L)}^{\ell}\beta_{j}r_{j}\right)=h+\frac{\alpha}{x-c}=\frac{(x-c)h+\alpha}{x-c}.$

Since $\deg((x-c)h+\alpha)=i$, $(x-c)h+\alpha$ is a polynomial as required.

(2). As in (1), one has that $L^{*}(M)=\tilde{M}+\alpha/(x-c)$. As
$\gcd(f_{1},x-c)=1$, $\alpha\neq 0$. If $\tilde{M}=0$ then $M/\alpha$ is a
solution of $L^{*}(y)=1/(x-c)$. Otherwise, let $r$ be a solution of
$L^{*}(y)=\tilde{M}$. Such $r$ exists due to Proposition 4.1. Then
$(M-r)/\alpha$ is a solution of $L^{*}(y)=1/(x-c)$. This proves the case
$i=0$. For the case $i>0$, write $x^{i}/(x-c)=p+\beta/(x-c)$ where $p\in C[x]$
and $\beta\in C$. Let $r_{1}$ be a solution of $L^{*}(y)=p$ in $k$ and $r_{2}$
a solution of $L^{*}(y)=\beta/(x-c)$. Then $r_{1}+r_{2}$ is a solution of
$L^{*}(y)=x^{i}/(x-c)$ in $k$.

###### Proposition 4.9.

Suppose that $L=D+f$ and $c\in C$ is a pole of $f$. Then

  1. (1)

${\rm Sind}(L+1/(x-c))\leq{\rm Sind}(L)+1$;

  2. (2)

if $L$ is stable then $L+1/(x-c)$ is also stable.

###### Proof.

(1). For each $i\geq{\rm Sind}(L)+1$, by Lemma 4.8, there exists a polynomial
$p_{i}$ of degree $i$ such that $L^{*}(y)={\frac{p_{i}}{x-c}}$ has a solution
$r_{i}$ in $k$. Then

$\left(L+\frac{1}{x-c}\right)^{*}((x-c){r_{i}})=(x-c)(-r_{i}^{\prime}+fr_{i})=p_{i}.$

Hence ${\rm Sind}(L+1/(x-c))\leq{\rm Sind}(L)+1$.

(2). Use a similar argument as in (1).

We now apply Theorem 3.8 to the first order operators to obtain an upper bound
on the stability indices of such operators. We use ${\rm num}(f)$ to denote
the numerator of a rational function $f$.

###### Proposition 4.10.

Suppose that $L=D+f$ and $\nu=\operatorname{res}_{\infty}(f)$. Then

${\rm
Sind}(L)\leq\begin{cases}\max\\{\deg(f_{1}),\deg(f_{2})\\}&\operatorname{ord}_{\infty}(f)\neq
1\\\
\deg(f_{2})-1&\operatorname{ord}_{\infty}(f)=1\,\,\mbox{and}\,\,\nu\notin\mathbb{Z}_{\leq
0}\\\ -\nu+\deg(f_{2})&\mbox{otherwise}\end{cases}$

where $f_{1}={\rm num}(f)$ and $f_{2}={\rm den}(f)$.

###### Proof.

It suffices to show that $\mathcal{B}(L)$ equals the corresponding bounds. Let
$f=\alpha\left(\frac{1}{x}\right)^{t}+\dots$ be the power series expansion of
$f$ at $\infty$, where $t=\operatorname{ord}_{\infty}(f)$. Then for each
$s\geq 0$,

$L^{*}(x^{s})=-sx^{s-1}+\alpha x^{s-t}+\dots.$

Suppose that $t>1$. Then ${\rm ind}^{L^{*}}(s)=-s$ and $\sigma^{L^{*}}=-1$.
Thus $\mathcal{B}(L)=\deg(f_{2})=\max\\{\deg(f_{1}),\deg(f_{2})\\}$ because
$\deg(f_{1})<\deg(f_{2})$. Suppose that $t<1$. Then ${\rm
ind}^{L^{*}}(s)=\alpha$ and $\sigma^{L^{*}}=-t$. Hence
$\mathcal{B}(L)=-t+\deg(f_{2})=\deg(f_{1})=\max\\{\deg(f_{1}),\deg(f_{2})\\}$.
Now suppose that $t=1$. Then $\alpha=-\operatorname{res}_{\infty}(f)=-\nu$.
Furthermore, ${\rm ind}^{L^{*}}(s)=-(s-\alpha)$ and $\sigma^{L^{*}}=-1$. If
$\nu$ is not a nonnegative integer then $\max V_{\mathbb{Z}_{\geq 0}}({\rm
ind}^{L^{*}})=-1$ and so $\mathcal{B}(L)=\deg(f_{2})-1$. Otherwise if $\nu$ is
a nonnegative integer then $\max V_{\mathbb{Z}_{\geq 0}}({\rm
ind}^{L^{*}})=-\nu$ and thus $\mathcal{B}(L)=-\nu+\deg(f_{2})$.

In what follows, we shall present a lower bound.

###### Lemma 4.11.

Suppose that $L=D+f$ with $\mathcal{S}(f)=\emptyset$. Set $N=\deg({\rm
den}(f))$ and $\nu=\operatorname{res}_{\infty}(f)$. Then

${\rm
Sind}(L)=\begin{cases}N-\min\\{1,\operatorname{ord}_{\infty}(f)\\}&\operatorname{ord}_{\infty}(f)\neq
1\,\,\mbox{or}\,\,\nu\notin\mathbb{Z}_{\leq-N}\\\
-\nu&\mbox{otherwise}\end{cases}.$

###### Proof.

Suppose that $r\in k$ satisfies that $L^{*}(r)=d$ for some nonzero polynomial
$d$. By Corollary 3.5, $r$ must be a polynomial. Furthermore, from
$-r^{\prime}+rf=d,$ one sees that ${\rm den}(f)$ divides $r$. In particular,
$\deg(r)\geq\deg({\rm den}(f))=N$. Let

$\displaystyle r=cx^{s}+\dots,\,\,f=\alpha x^{-t}+\dots,$

be the power series expansions of $r$ and $f$ respectively, where $s=\deg(r)$
and $t=\operatorname{ord}_{\infty}(f)$. From $-r^{\prime}+rf=d$ again, one has
that

(4) $-scx^{s-1}+\dots+c\alpha x^{s-t}+\dots=d.$

Suppose that $t=\operatorname{ord}_{\infty}(f)<1$. Then $\deg(d)$ must be
equal to $s-t$ that is not less than $N-t$. In other words, if $\delta(L,d)=1$
for some nonzero polynomial $d$ then $\deg(d)\geq N-t$. So ${\rm Sind}(L)\geq
N-t$. On the other hand, for each $i\geq 0$,

$L^{*}({\rm den}(f)x^{i})=-\alpha x^{N+i-t}+\mbox{lower terms}.$

This implies that for each $s\geq N-t$, ${\rm den}(f)x^{s-N+t}$ is a solution
of $L^{*}(y)=-\alpha x^{s}+\mbox{lower terms}$, i.e. ${\rm Sind}(L)\leq N-t$.
Consequently, ${\rm Sind}(L)=N-t$. Similarly, one can prove the case $t>1$.

Now assume that $t=1$. In this case,
$\alpha=-\operatorname{res}_{\infty}(f)=-\nu$ and $s=\deg(r)\geq N>0$.
Moreover, the equality (4) becomes

(5) $-c(s+\nu)x^{s-1}+\mbox{lower terms}=d.$

Suppose that $\nu\notin\mathbb{Z}_{\leq-N}$. Then $s+\nu\neq 0$ for all $s\geq
N$. Hence $\deg(d)$ must be equal to $s-1$. Using a similar argument as in the
case $t<1$, one has that ${\rm Sind}(L)=N-1$. It remains to show the case
$\nu\in\mathbb{Z}_{\leq-N}$. We first show that $\delta(L,d)=0$ for any
polynomial $d\in C[x]$ of degree $-\nu-1$. Suppose on the contrary that there
is a polynomial $d\in C[x]$ of degree $-\nu-1$ such that $L^{*}(y)=d$ has a
solution $r\in C[x]$. If $s=\deg(r)>-\nu$ then $s+\nu=0$ by (5). This implies
that $s=-\nu$, a contradiction. So $s\leq-\nu$. From (5), it is obvious that
$s$ can not be less than $-\nu$. Thus $s=-\nu$. While, this means that the
degree of the left-hand side of (5) is less than $-\nu-1$. This contradicts
the assumption that $\deg(d)=-\nu-1$. Consequently, $\delta(L,d)=0$ for any
polynomial $d$ of degree $-\nu-1$ and so ${\rm Sind}(L)\geq-\nu$. Finally, for
each $i\geq 0$,

$L^{*}\left({\rm den}(f)x^{i+1-\nu-N}\right)=-(i+1)x^{i-\nu}+\mbox{lower
terms}.$

This implies that ${\rm Sind}(L)\leq-\nu$. Therefore ${\rm Sind}(L)=-\nu$.

###### Proposition 4.12.

Suppose that $L=D+f$. Set

$N=\deg({\rm den}(f))-|\mathcal{S}(f)|-\deg(\Delta(f))$

and $\nu=\operatorname{res}_{\infty}(f).$ Then

${\rm
Sind}(L)\geq\begin{cases}N-\min\\{1,\operatorname{ord}_{\infty}(f)\\}&\operatorname{ord}_{\infty}(f)\neq
1\,\,\mbox{or}\,\,\nu\notin\mathbb{Z}_{\leq-N}\\\
-\nu&\mbox{otherwise}\end{cases}.$

###### Proof.

Set $M_{1}=\prod_{c\in\mathcal{S}(f)}(x-c)$ and write ${\rm
den}(f)=M_{1}M_{2}$. Then $\deg(M_{2})=\deg({\rm den}(f))-|\mathcal{S}(f)|$.
Since $\gcd(M_{1},M_{2})=1$, there exist $q_{1},q_{2}\in C[x]$ such that
$f=q_{1}/M_{1}+q_{2}/M_{2}.$ Since $M_{1}$ is square-free and
$\operatorname{res}_{c}(q_{1}/M_{1})=\operatorname{res}_{c}(f)$ for each
$c\in\mathcal{S}(f)$, one has that

$\frac{q_{1}}{M_{1}}=\sum_{c\in\mathcal{S}(f)}\frac{\operatorname{res}_{c}(f)}{x-c}=-\frac{\Delta(f)^{\prime}}{\Delta(f)}.$

So $f=-\Delta(f)^{\prime}/\Delta(f)+q_{2}/M_{2}$. Set
$\tilde{L}=L+\Delta(f)^{\prime}/\Delta(f)=D+q_{2}/M_{2}$. Using Proposition
4.9 repeatedly yields that ${\rm Sind}(\tilde{L})\leq{\rm
Sind}(L)+\deg(\Delta(f))$. Since $\mathcal{S}(q_{2}/M_{2})=\emptyset$, by
Lemma 4.11, one has that if $\operatorname{ord}_{\infty}(q_{2}/M_{2})\neq 1$
or
$\operatorname{res}_{\infty}(q_{2}/M_{2})\notin\mathbb{Z}_{\leq-\deg(M_{2})}$
then ${\rm
Sind}(\tilde{L})=\deg(M_{2})-\min\\{1,\operatorname{ord}_{\infty}(q_{2}/M_{2})\\}$,
otherwise ${\rm Sind}(\tilde{L})=-\operatorname{res}_{\infty}(q_{2}/M_{2})$.

Note that $\operatorname{ord}_{\infty}(-\Delta(f)^{\prime}/\Delta(f))=1$ and
$\operatorname{res}_{\infty}(-\Delta(f)^{\prime}/\Delta(f))=\deg(\Delta(f))$.
Furthermore, one has that

$\displaystyle\operatorname{res}_{\infty}(f)$
$\displaystyle\geq\min\left\\{\operatorname{ord}_{\infty}\left(-\frac{\Delta(f)^{\prime}}{\Delta(f)}\right),\operatorname{ord}_{\infty}\left(\frac{q_{2}}{M_{2}}\right)\right\\}$
$\displaystyle=\min\left\\{1,\operatorname{ord}_{\infty}\left(\frac{q_{2}}{M_{2}}\right)\right\\}$

and the equality holds if $\operatorname{ord}_{\infty}(q_{2}/M_{2})\neq 1$. If
$\operatorname{ord}_{\infty}(f)<1$ then
$\operatorname{ord}_{\infty}(q_{2}/M_{2})=\operatorname{ord}_{\infty}(f)<1$
and so

$\displaystyle{\rm Sind}(L)$ $\displaystyle\geq{\rm
Sind}(\tilde{L})-\deg(\Delta(f))$
$\displaystyle=\deg(M_{2})-\min\\{1,\operatorname{ord}_{\infty}(q_{2}/M_{2})\\}-\deg(\Delta(f))$
$\displaystyle=N-\min\\{1,\operatorname{ord}_{\infty}(f)\\}.$

Suppose that $\operatorname{ord}_{\infty}(f)>1$. Then
$\operatorname{ord}_{\infty}(q_{2}/M_{2})=1$ and moreover
$\operatorname{res}_{\infty}(q_{2}/M_{2})=-\operatorname{res}_{\infty}(-\Delta(f)^{\prime}/\Delta(f))=-\deg(\Delta(f))$.
Assume that $\deg(\Delta(f))\geq\deg(M_{2})$. Then
$\operatorname{res}_{\infty}(q_{2}/M_{2})\in\mathbb{Z}_{\leq-\deg(M_{2})}$ and
so ${\rm
Sind}(\tilde{L})=-\operatorname{res}_{\infty}(q_{2}/M_{2})=\deg(\Delta(f)).$
Thus ${\rm Sind}(L)\geq 0$. On the other hand, in this case,

$N-\min\\{1,\operatorname{ord}_{\infty}(f)\\}=\deg(M_{2})-\deg(\Delta(f))-1<0\leq{\rm
Sind}(L).$

Assume that $\deg(\Delta(f))<\deg(M_{2})$. Then we have
$\operatorname{res}_{\infty}(q_{2}/M_{2})\notin\mathbb{Z}_{\leq-\deg(M_{2})}$.
So ${\rm Sind}(\tilde{L})=\deg(M_{2})-1$ and ${\rm Sind}(L)\geq{\rm
Sind}(\tilde{L})-\deg(\Delta(f))=N-1$. Since
$\operatorname{ord}_{\infty}(f)>1$, we have
$N-1=N-\min\\{1,\operatorname{ord}_{\infty}(f)\\}$ and then the assertion
holds.

Note that
$\nu=\operatorname{res}_{\infty}(f)=\operatorname{res}_{\infty}(-\Delta(f)^{\prime}/\Delta(f))+\operatorname{res}_{\infty}(q_{2}/M_{2})$
and
$\operatorname{res}_{\infty}(-\Delta(f)^{\prime}/\Delta(f))=\deg(\Delta(f))$.
This implies that $\nu\notin\mathbb{Z}_{\leq-N}$ if and only if
$\operatorname{res}_{\infty}(q_{2}/M_{2})\notin\mathbb{Z}_{\leq-\deg(M_{2})}$.
Suppose that $\operatorname{ord}_{\infty}(f)=1$ and
$\nu\notin\mathbb{Z}_{\leq-N}$. Then
$\operatorname{ord}_{\infty}(q_{2}/M_{2})\geq 1$ and ${\rm
Sind}(\tilde{L})=\deg(M_{2})-1$. Thus ${\rm Sind}(L)\geq{\rm
Sind}(\tilde{L})-\deg(\Delta(f))\geq N-1$. The assertion then follows from the
fact that $\min\\{1,\operatorname{ord}_{\infty}(f)\\}=1$. Finally, assume that
$\operatorname{ord}_{\infty}(f)=1$ and $\nu\in\mathbb{Z}_{\leq-N}$. Then
$\operatorname{res}_{\infty}(q_{2}/M_{2})\in\mathbb{Z}_{\leq-\deg(M_{2})}$.
Hence ${\rm Sind}(\tilde{L})=-\operatorname{res}_{\infty}(q_{2}/M_{2})$ and
then ${\rm
Sind}(L)\geq-\operatorname{res}_{\infty}(q_{2}/M_{2})-\deg(\Delta(f))=-\nu$.

##  5\. Stable first order operators

Any solution of a first order operator over $k$ is called a hyperexponential
function over $k$. A first order operator is stable if and only if its
corresponding hyperexponential solution is stable. The stability problem for
hyperexponential functions of the form $f\exp(g)$ with $f,g\in k$ has been
solved in (chen2022ISSAC, ). In this section, we shall solve the stability
problem for general hyperexponential functions by presenting a necessary and
sufficient condition on the stability of first order operators.

###### Theorem 5.1.

Suppose that $L=D+f$ where $f\in C(x)$. Then $L$ is stable if and only if $f$
admits one of the following forms:

$-\frac{h^{\prime}}{h}+\alpha\,\,\mbox{or}\,\,-\frac{h^{\prime}}{h}+\frac{\beta}{x-c},\,\,h\in
C[x]\setminus\\{0\\},\alpha,\beta,c\in C$

and $\beta$ is not a positive integer.

###### Proof.

Suppose that $f$ admits one of the above forms. By Proposition 4.7, it
suffices to show that $D+\alpha$ and $D+\beta/(x-c)$ are stable. The case
$D+\alpha$ follows from Proposition 4.4 and the case $D+\beta/(x-c)$ follows
from Example 3.14.

Now suppose that $L$ is stable. Set $h=\Delta(f)$ and
$\tilde{f}=f+h^{\prime}/h$. If $\tilde{f}=0$ then there is nothing to prove.
Suppose that $\tilde{f}\neq 0$. Then there is no simple pole of $\tilde{f}$ at
which the residue of $\tilde{f}$ is a negative integer, i.e.
$\mathcal{S}(\tilde{f})=\emptyset$ and $\Delta(\tilde{f})=1$. Using
Proposition 4.9 repeatedly, one has that $\tilde{L}=L+h^{\prime}/h$ is stable.
Note that $\tilde{L}=D+\tilde{f}$.

Set $\tilde{f}_{1}={\rm num}(\tilde{f}_{1})$ and $\tilde{f}_{2}={\rm
den}(\tilde{f})$. Note that $\mathcal{S}(\tilde{f})=\emptyset$. If
$\operatorname{ord}_{\infty}(\tilde{f})<0$ then $\deg(\tilde{f}_{1})>0$, and
by Lemma 4.11 one has that

${\rm
Sind}(\tilde{L})\geq\deg(\tilde{f}_{2})-\operatorname{ord}_{\infty}(\tilde{f})=\deg(\tilde{f}_{1})>0$

a contradiction. If $\operatorname{ord}_{\infty}(\tilde{f})>1$ then
$\deg(\tilde{f}_{2})>1$ and ${\rm Sind}(\tilde{L})\geq\deg(\tilde{f}_{2})-1>0$
by Lemma 4.11. One obtains a contradiction again. Therefore
$\operatorname{ord}_{\infty}(\tilde{f})=0$ or
$\operatorname{ord}_{\infty}(\tilde{f})=1$.

Suppose that $\operatorname{ord}_{\infty}(\tilde{f})=0$. Then by Lemma 4.11
again, $0={\rm Sind}(\tilde{L})=\deg(\tilde{f}_{1})$. This implies that
$\deg(\tilde{f}_{2})=0$ for $\operatorname{ord}_{\infty}(\tilde{f})=0$. Hence
one has that $\alpha=\tilde{f}\in C\setminus\\{0\\}$ and then
$f=-h^{\prime}/h+\alpha$. Now we consider the case
$\operatorname{ord}_{\infty}(\tilde{f})=1$. Then $\deg(\tilde{f}_{2})\geq 1$
and $\operatorname{res}_{\infty}(\tilde{f})\neq 0$. If
$\operatorname{res}_{\infty}(\tilde{f})\in\mathbb{Z}_{\leq-\deg(\tilde{f}_{2})}$
then by Lemma 4.11, ${\rm
Sind}(\tilde{L})=-\operatorname{res}_{\infty}(\tilde{f})\geq\deg(\tilde{f}_{2})\geq
1$, a contradiction. So
$\operatorname{res}_{\infty}(\tilde{f})\notin\mathbb{Z}_{\leq-\deg(\tilde{f}_{2})}.$
In this case, by Lemma 4.11 again, one sees that

$0={\rm Sind}(\tilde{L})=\deg(\tilde{f}_{2})-1.$

Therefore $\deg(\tilde{f}_{2})=1$ and $\deg(\tilde{f}_{1})=0$. Set
$\beta=\tilde{f}_{1}$ and write $\tilde{f}_{2}=x-c$ for some $c\in C$. Then
$f=-h^{\prime}/h+\beta/(x-c)$.

It remains to show that $\beta$ is not a positive integer. Assume on the
contrary that $\beta$ is a positive integer. Since $\tilde{L}$ is stable, by
Proposition 4.1, there is an $r\in k$ such that
$\tilde{L}^{*}(r)=(x-c)^{\beta-1}$. As $\Delta(\tilde{f})=1$, Lemma 4.6
implies that $r$ is a polynomial. From $\tilde{L}^{*}(r)=(x-c)^{\beta-1}$, one
has that

$-r^{\prime}(x-c)+r\beta=(x-c)^{\beta}.$

Write $r=\alpha x^{s}+\dots$, where $s=\deg(r)$. Then

$-\alpha(s-\beta)x^{s}+\mbox{lower terms}=(x-c)^{\beta}.$

Comparing the degrees of both sides of the above equality, one sees that there
does not exist any integer $s$ such that the above equality holds, a
contradiction. Therefore $\beta$ is not a positive integer.

###### Example 5.2.

Let $L=D-\frac{1}{2x}-\frac{1}{2(x+1)}$. Then $L$ is the defining operator of
$\sqrt{x(x+1)}$. By Theorem 5.1, $L$ is not stable. Notice that the method
presented in (chen2022ISSAC, ) is not valid for this example.

##  6\. Iterated integration of special rational functions

In the last section, we shall consider the iterated integrals of the rational
function $1/q$, where $q$ is a nonzero polynomial in $C[x]$. Write
$q=\operatorname{lc}(q)\prod_{i=1}^{n}(x-c_{i})^{m_{i}}$. Then the first order
operator with $1/q$ as a fundamental solution is of the form

(6) $L=D+\sum_{i=1}^{n}\frac{m_{i}}{x-c_{i}}.$

###### Lemma 6.1.

Suppose that $L=D-f^{\prime}/f$ where $f\in k\setminus\\{0\\}$. Then for a
nonzero $d\in C[x]$, $\delta(L,d)=1$ if and only if $df$ is rationally
integrable.

###### Proof.

For $r\in k\setminus\\{0\\}$, one has that

$L^{*}(r)=-r^{\prime}-\frac{f^{\prime}}{f}r=-\frac{f^{\prime}r+fr^{\prime}}{f}=-\frac{1}{f}\left(rf\right)^{\prime}.$

So $L^{*}(r)=d$ if and only if $(-fr)^{\prime}=df$. In other words,
$\delta(L,d)=1$ if and only if $df$ is rationally integrable.

The following lemma may seem folklore, but we did not find any precise
reference. So we include its full proof for the sake of completeness.

###### Lemma 6.2.

Suppose that $q=c_{0}\prod_{i=1}^{n}(x-c_{i})^{m_{i}}$ with $c_{i}\in C$,
$m_{i},n>1$ and $p\in C[x]$ is a nonzero polynomial. If either $\deg(p)<n-1$
or $\deg(p)=\deg(q)-1$, then $p/q$ is not rationally integrable.

###### Proof.

Assume that $\deg(p)<n-1$ and assume on the contrary that $p/q$ is rationally
integrable, i.e. there is an $r\in C(x)$ such that $r^{\prime}=p/q$. Set
$r_{1}={\rm num}(r)$ and $r_{2}={\rm den}(r)$. We claim that
$q=\tilde{q}r_{2}\prod_{i=1}^{n}(x-c_{i})$ for some nonzero $\tilde{q}\in
C[x]$. Note that $c\in C$ is a pole of $r_{1}/r_{2}$ if and only if $c$ is a
pole of $r$. Hence we may write $r_{2}=\prod_{i=1}^{n}(x-c_{i})^{l_{i}}$ where
$l_{i}>0$. For each $1\leq i\leq n$,
$\operatorname{ord}_{c_{i}}(r^{\prime})=\operatorname{ord}_{c_{i}}(r)-1=-l_{i}-1$
and $\operatorname{ord}_{c_{i}}(p/q)\geq-m_{i}$. These imply that $m_{i}\geq
l_{i}+1$ for all $1\leq i\leq n$. So
$q=\tilde{q}r_{2}\prod_{i=1}^{n}(x-c_{i})$ and our claim holds. Now from
$r^{\prime}=p/q$, one has that
$q(r_{1}^{\prime}r_{2}-r_{1}r_{2}^{\prime})=pr_{2}^{2}$. Cancelling $r_{2}$
from both sides yields that

(7)
$\tilde{q}(r_{1}^{\prime}r_{2}-r_{1}r_{2}^{\prime})\prod_{i=1}^{n}(x-c_{i})=pr_{2}.$

If $\deg(r_{1})\neq\deg(r_{2})$ then
$\deg(r_{1}^{\prime}r_{2}-r_{1}r_{2}^{\prime})=\deg(r_{1})+\deg(r_{2})-1$.
Suppose that $\deg(r_{1})=\deg(r_{2})$. Write $r_{1}=cr_{2}+h$ where $c\in C$
and $h\in C[x]$ with $\deg(h)<\deg(r_{2})$. Since $\gcd(r_{1},r_{2})=1$,
$h\neq 0$. One sees that
$r_{1}^{\prime}r_{2}-r_{1}r_{2}^{\prime}=h^{\prime}r_{2}-hr_{2}^{\prime}$ and
then
$\deg(r_{1}^{\prime}r_{2}-r_{1}r_{2}^{\prime})=\deg(h^{\prime}r_{2}-hr_{2}^{\prime})=\deg(h)+\deg(r_{2})-1$.
In either case, one sees that
$\deg(r_{1}^{\prime}r_{2}-r_{1}r_{2}^{\prime})\geq\deg(r_{2})-1$. Then the
degree of the left-hand side of (7) is not less than $\deg(r_{2})-1+n$.
However the degree of the right-hand side of (7) equals $\deg(p)+\deg(r_{2})$
that is less than $\deg(r_{2})+n-1$. We obtain a contradiction. Thus $p/q$ is
not rationally integrable.

Finally suppose that $\deg(p)=\deg(q)-1$. Then the residue of $p/q$ at
infinity is not zero because $\operatorname{ord}(x^{2}p/q)=-1$. It is well-
known that a rational function is rationally integrable if and only if all of
its residues vanish. So $p/q$ is not rationally integrable.

###### Proposition 6.3.

Let $L$ be of the form (6) and let $L_{j}$ be a $j$-th principal integral of
$L$. Then

$\operatorname{ord}(L_{j})=\begin{cases}\operatorname{ord}(L)+j,&0\leq j\leq
n-1\\\ \operatorname{ord}(L)+n-1,&n-1<j\leq\sum_{i=1}^{n}m_{i}-1\\\
\operatorname{ord}(L)+n,&j\geq\sum_{i=1}^{n}m_{i}\end{cases}.$

###### Proof.

Note that $\frac{q^{\prime}}{q}=\sum_{i=1}^{n}\frac{m_{i}}{x-c_{i}}$. Due to
Lemmas 6.1 and 6.2, $\delta(L,d)=0$ for any nonzero polynomial $d$ of degree
less than $n-1$. By Corollary 3.5,
$\operatorname{ord}(L_{j+1})=\operatorname{ord}(L_{j})+1$ for all $0\leq
j<n-1$. Thus $\operatorname{ord}(L_{j})=\operatorname{ord}(L)+j$ for all
$0\leq j\leq n-1$.

Set $N=\sum_{i=1}^{n}m_{i}$. Assume that $N>n$. Then there is at least one
$m_{i}$ that is greater than 1. Without loss of generality, we assume that all
of $m_{1},\dots,m_{s}$ are greater than 1 and $m_{s+1}=\dots=m_{n}=1$. Suppose
that $j$ is an integer satisfying that $n-1\leq j<N-1$. Then
$\sum_{i=1}^{s}(m_{i}-1)=\sum_{i=1}^{n}(m_{i}-1)\geq N-1-j$. Hence there exist
integers $t,l_{1},\dots,l_{t}$ satisfying that $1\leq t\leq s,0<l_{i}<m_{i}$
and $\sum_{i=1}^{t}l_{i}=N-1-j$. Set $r=1/\prod_{i=1}^{t}(x-c_{i})^{l_{i}}$.
Then

$\left(\frac{1}{r}\right)^{\prime}=\frac{h}{\prod_{i=1}^{t}(x-c_{i})^{l_{i}+1}}$

where $h$ is a nonzero polynomial of degree $t-1$. Let
$\tilde{d}=q(1/r)^{\prime}$. Then $\tilde{d}$ is a nonzero polynomial because
$l_{i}+1\leq m_{i}$, and

$\deg(\tilde{d})=\deg(h)+\deg(q)-\sum_{i=1}^{t}(l_{i}+1)=j.$

As $(1/r)^{\prime}=\tilde{d}/q$, Lemma 6.1 implies that
$\delta(L,\tilde{d})=1$. Due to Corollary 3.5 again,
$\operatorname{ord}(L_{j+1})=\operatorname{ord}(L_{j})$ for all $n-1\leq
j<N-1$. Thus
$\operatorname{ord}(L_{j})=\operatorname{ord}(L_{n-1})=\operatorname{ord}(L)+n-1$
for all $n-1<j\leq N-1$.

By Lemma 6.2, we have that $p/q$ is not rationally integrable if
$\deg(p)=\deg(q)-1$. Therefore $\delta(L,d)=0$ for any $d\in C[x]$ of degree
$N-1$. Corollary 3.5 then implies that
$\operatorname{ord}(L_{N})=\operatorname{ord}(L_{N-1})+1=\operatorname{ord}(L)+n$.
For each $j\geq N$, one has that

$L^{*}(qx^{j-N+1})=(j-N+1)qx^{j-N}.$

In other words, $L^{*}(qx^{j-N+1})$ is a polynomial of degree $j$. By
Corollary 3.5, $\operatorname{ord}(L_{j+1})=\operatorname{ord}(L_{j})$ for all
$j\geq N$. Hence $\operatorname{ord}(L_{j})=\operatorname{ord}(L)+n$ for all
$j\geq N$.

###### Corollary 6.4.

Let $L$ be of the form (6). Then ${\rm Sind}(L)=\deg(q)$.

Acknowledgement. We thank the anonymous referees for their careful reading and
their valuable suggestions.

## References

  * [1] Sergei A. Abramov and Mark Van Hoeij.  Integration of solutions of linear functional equations.  Integral Transforms and Special Functions, 8(1-2):3–12, 1999.
  * [2] Sergei A. Abramov, Ha Quang Le, and Ziming Li.  Univariate Ore polynomial rings in computer algebra.  J. of Mathematical Sci., 131(5):5885–5903, 2005.
  * [3] Sergei A. Abramov and Mark van Hoeij.  A method for the integration of solutions of ore equations.  In ISSAC ’97: Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, pages 172–175, New York, NY, USA, 1997. ACM.
  * [4] Shaoshi Chen.  Stability problems in symbolic integration.  In ISSAC’22: Proceedings of the 2022 International Symposium on Symbolic and Algebraic Computation, ISSAC ’22, pages 517–524, New York, NY, USA, 2022. ACM.
  * [5] Li Guo, Georg Regensburger, and Markus Rosenkranz.  On integro-differential algebras.  J. Pure Appl. Algebra, 218(3):456–473, 2014.
  * [6] Nicholas M. Katz.  On the calculation of some differential galois groups.  Inventiones mathematicae, 87:13–61, 1987.
  * [7] Manuel Kauers.  D-Finite Fuctions.  Springer Nature, August 26, 2022.
  * [8] E. R. Kolchin.  Differential algebra and algebraic groups.  Academic Press, New York-London, 1973.  Pure and Applied Mathematics, Vol. 54.
  * [9] Leonard M. Lipshitz.  D-finite power series.  J. Algebra, 122(2):353–373, 1989.
  * [10] Oystein Ore.  Theory of non-commutative polynomials.  Ann. of Math. (2), 34(3):480–508, 1933.
  * [11] Bruno Salvy.  Linear differential equations as a data structure.  Found. Comput. Math., 19(5):1071–1112, 2019.
  * [12] Richard P. Stanley.  Differentiably finite power series.  European J. Combin., 1(2):175–188, 1980.
  * [13] Marius van der Put and Michael F. Singer.  Galois theory of linear differential equations, volume 328 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences].  Springer-Verlag, Berlin, 2003.
  * [14] Herbert S. Wilf and Doron Zeilberger.  An algorithmic proof theory for hypergeometric (ordinary and “$q$”) multisum/integral identities.  Invent. Math., 108(3):575–633, 1992.
  * [15] Doron Zeilberger.  A holonomic systems approach to special functions identities.  J. Comput. Appl. Math., 32:321–368, 1990.