%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[revision]{FPSAC2019}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

\articlenumber{101}
\addbibresource{101.bib}

%% note that the class file already loads {amsmath, amsthm, amssymb}


\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{problem}[theorem]{Problem}

\newcommand{\code}[1]{\texttt{#1}}

\newcommand{\set}[1]{\ensuremath{\mathbb{#1}}}
\newcommand{\rational}{\set{Q}}
\newcommand{\real}{\set{R}}
\newcommand{\integer}{\set{Z}}
\newcommand{\naturals}{\set{N}}
\newcommand{\complex}{\set{C}}
\newcommand{\tq}{\ensuremath{\ :\ }}
\newcommand{\si}[1][x]{\ensuremath{\sin(#1)}}
\newcommand{\co}[1][x]{\ensuremath{\cos(#1)}}
\newcommand{\ta}[1][x]{\ensuremath{\tan(#1)}}
\newcommand{\gcrd}{\operatorname{GCRD}}
\newcommand{\lclm}{\operatorname{LCLM}}
\newcommand{\trdeg}{\operatorname{tr.deg.}}

\newcommand{\falling}[2]{\ensuremath{\left(#1\right)^{\underline{#2}}}}
\newcommand{\id}{\mathcal{I}}
\newcommand{\sm}{\mathcal{S}}
\renewcommand{\vector}{\mathbf}
\newcommand{\df}{\partial}
 
\newcommand{\pr}[2][x]{\ensuremath{#2[#1]}} % Polynomial ring
\newcommand{\rf}[2][x]{\ensuremath{#2(#1)}} % Polynomial Fraction Field
\newcommand{\ff}[1]{\ensuremath{\text{Q}(#1)}} % Fraction Field
\newcommand{\dor}[2][\df]{\ensuremath{#2[#1]}} % Linear Diff. Operator ring
\newcommand{\ps}[2][x]{\ensuremath{#2[[#1]]}} % Power series ring
\newcommand{\sr}[1]{\ensuremath{#1^{\naturals}}} % Power series ring
\newcommand{\ls}[2][x]{\ensuremath{#2((#1))}} % Laurent series field
\newcommand{\seq}[1]{\ensuremath{\bold{#1}}} % notation for sequences
\newcommand{\cm}{\mathcal{C}}

\DeclareMathOperator{\GL}{GL}

\DeclareMathOperator{\dd}{D}
\newcommand{\dfinite}[1][K]{\ensuremath{\dd(\pr{#1})}} %D-Finite ring
\newcommand{\ddfinite}[1][K]{\ensuremath{\dd^2(\pr{#1})}} %DD-Finite ring
\newcommand{\dlimit}[1][K]{\ensuremath{\dd^{\infty}(\pr{#1})}} %Limit D-ring

\newcommand{\expf}[1]{\ensuremath{e_{#1}}}
\newcommand{\iexpf}[1]{\ensuremath{\hat{e}_{#1}}}

\newcommand{\ann}[1][A]{\ensuremath{\mathcal{#1}}} % annihilating operator 

\newcommand{\vecD}{\vec{\partial}}

\DeclareMathOperator{\coeff}{coeff}
\DeclareMathOperator{\rank}{rk}
\DeclareMathOperator{\len}{len}

\usepackage{listings}
\lstdefinelanguage{Sage}[]{Python}
{morekeywords={False,sage,True},sensitive=true}
\lstset{
  frame=none,
  showtabs=False,
  showspaces=False,
  showstringspaces=False,
  commentstyle={\ttfamily\color{dgreencolor}},
  keywordstyle={\ttfamily\color{dbluecolor}\bfseries},
  stringstyle={\ttfamily\color{dgraycolor}\bfseries},
  language=Sage,
  basicstyle={\fontsize{10pt}{10pt}\ttfamily},
  aboveskip=0.3em,
  belowskip=0.1em,
  numbers=left,
  numberstyle=\footnotesize
}
\definecolor{dblackcolor}{rgb}{0.0,0.0,0.0}
\definecolor{dbluecolor}{rgb}{0.01,0.02,0.7}
\definecolor{dgreencolor}{rgb}{0.2,0.4,0.0}
\definecolor{dgraycolor}{rgb}{0.30,0.3,0.30}
\newcommand{\dblue}{\color{dbluecolor}\bf}
\newcommand{\dred}{\color{dredcolor}\bf}
\newcommand{\dblack}{\color{dblackcolor}\bf}

%\usepackage{lipsum}

%% define your title in the usual way
\title[DDFunctions]{DD-finite functions in Sage}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author[A. Jim\'{e}nez-Pastor]{Antonio Jim\'{e}nez-Pastor\thanks{\href{mailto:antonio.jimenez-pastor@dk-compmath.jku.at}{antonio.jimenez-pastor@dk-compmath.jku.at}.This author was funded by the Austrian Science Fund (FWF): W1214-N15, project DK15.
}}

%% then use \addressmark to match authors to institutions here
\address{Doctoral Program Computational Mathematics, JKU, Linz}

%% put the date of submission here
\received{March 14, 2019}

%% leave this blank until submitting a revised version
\revised{April 30, 2019}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{We present here a Sage implementation for DD-finite functions, which are a natural extension of the
class of holonomic or D-finite functions. The package, focused on a functional approach, provides natural 
commands for executing closure properties among DD-finite functions, a general framework for 
extracting their coefficient sequences and allows the user to compute the composition 
(as power series) of the functions treated in the package.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{Nam dui ligula, fringilla a, euismod sodales, sollicitudin vel, wisi. Morbi
%auctor lorem non justo. Nam lacus libero, pretium at, lobortis vitae, ultricies et, tel-
%lus. Donec aliquet, tortor sed accumsan bibendum, erat ligula aliquet magna, vitae
%ornare odio metus a mi. Morbi ac orci et nisl hendrerit mollis. Suspendisse ut massa.
%Cras nec ante. Pellentesque a nulla. Cum sociis natoque penatibus et magnis dis par-
%turient montes, nascetur ridiculus mus. Aliquam tincidunt urna. Nulla ullamcorper
%vestibulum turpis. Pellentesque cursus luctus mauris.}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{holonomic, D-finite, generating functions, closure properties, formal power series}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
%\usepackage[backend=bibtex]{biblatex}
%\addbibresource{JimenezPastor_sftw_fpsac19.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}\label{sec:intro}
A formal power series $f(x) = \sum_{n\geq 0} a_nx^n$ is called D-finite, if it satisfies a linear differential
equation with polynomial coefficients~\cite{mk:pp:CT,stanley:1980,stanley:enum-comb:2}. Many generating 
functions of combinatorial sequences are of this type as well as the most commonly used special
functions~\cite{andrews,NIST:DLMF,RainvilleSF}. These objects can be represented in finite terms using
a defining differential equation and sufficiently many initial values.

We recently extended this class to a wider set of formal power series that satisfy linear differential
equations with D-finite coefficients, and call them DD-finite~\cite{ajp:vp:dd-finite}. In the same way as 
D-finite functions satisfy several closure properties that have been implemented in several computer algebra
systems~\cite{gfun,mallinger,chyzak98,koutschan,oresage}, we present here a Sage implementation for the 
closure properties and other operations on DD-finite functions.

The finiteness of the representation for D-finite functions allows to finitely represent DD-finite
functions, with a defining differential equation and initial conditions. A difference
between our packages and other implementations is that our focus is on the whole function, not only
its annihilating differential operator. This leads to two different steps while manipulating DD-finite functions:
computing the final differential equation and computing the initial data required for the specific object.
More details on the structure we used can be found in \cref{sec:theory}.

Kauer's et al. package \code{ore\_algebra}~\cite{oresage} has implemented several operations for D-finite functions. 
On this base level, the package presented here uses these structures by default.If the user desires to
avoid that package, or \code{ore\_algebra} is not installed, a different 
implementation~\cite{ajp:vp:issac18} is provided. That is used by default
with DD-finite functions.

At the time of writing, the package described in this document is still under construction and has not been
added to the official Sage distribution. Readers who want to try it are invited to download 
the current version from

\begin{center}\url{https://www.dk-compmath.jku.at/Members/antonio/sage-package-dd_functions}\end{center}
and are encouraged to send bug reports, feature requests or other comments.

Once downloaded and unpacked the file, the user should add the path to the obtained folder into the package
folders in the Sage installation or just run Sage within the directory \emph{diff\_defined\_functions}. 
Then the package is ready to be used using the following command:

\begin{lstlisting}[numbers=none]
sage: from ajpastor.dd_functions import *
\end{lstlisting}

All the features of the package (creating the appropriate objects, arithmetically manipulating them, getting 
some examples, etc.) can be used without further configuration.

\begin{lstlisting}[numbers=none]
sage: C = Catalan();   # Getting Catalan gen. function
sage: F = Fibonacci(); # Getting Fibonacci gen. function
sage: C*(1+x^2*C^2*F(x*C)) == F(x*C) # Check identity
	True
sage: T = Tan(x) # Getting the tangent function
sage: T.derivative() == T^2+1 # Derivative identity for the tangent
	True
\end{lstlisting}

The user can check that the package is ready to be used by running the included tests on the code. 
Running these tests will produce a text output that shows the timestamps of the tests that are been
executed. The code to run those tests is the following:

\begin{lstlisting}[numbers=none]
sage: from ajpastor.tests import dd_functions
sage: dd_function.run()
\end{lstlisting}

More details on how to build the structures and the examples available can be found in
\cref{sec:theory,sec:features}.

\section{The basic structures}\label{sec:theory}

Although the main motivation behind our package is manipulating DD-finite functions, the theory involved can be 
described in a more general way. We recall the main definition and the basic closure properties. For details,
see~\cite{ajp:vp:dd-finite}.
\begin{definition}\label{def:dd_ring}
	Let $R$ be a non-trivial differential subring of $\ps{K}$ and $\dor{R}$
    the ring of linear differential operators over $R$. We call $f \in
    \ps{K}$ \emph{differentially definable over $R$} if there is a non-zero operator
    $\ann \in \dor{R}$ that annihilates $f$, i.e.,~$\ann \cdot f = 0$.
    By $\dd(R)$ we denote the set of all $f \in \ps{K}$ that are
    differentially definable over~$R$.  
\end{definition}

\begin{theorem}
	\label{thm:closure}
	Let $R$ be a non-trivial differential subring of $\ps{K}$ and $f(x),g(x)
        \in \dd(R)$. Then:
	\begin{enumerate}
        \item\label{it:der} $f'(x) \in \dd(R)$.
        \item\label{it:antider} Any antiderivative of $f(x)$ is in $\dd(R)$.
        \item\label{it:add} $f(x)+g(x) \in \dd(R)$.
        \item\label{it:mult} $f(x)g(x) \in \dd(R)$.
        \item\label{it:multinv} If $r(0)\neq0$, then its multiplicative inverse $1/r(x)$ in $\ps K$
          is in $\dd(R)$.
	\end{enumerate}
	
	In particular, $\dd(R)$ is a differential subring of $\ps K$.
\end{theorem}

\subsection{DDRing}\label{subsec:ddring}

The structure \code{DDRing} describes the rings of differentially definable functions, $\dd(R)$. Thus,
they are built from any ring structure $R$ in Sage. Following the \emph{Parent-Element} model of 
Sage, \code{DDRing} is a parent class that will include as element any differentially definable 
function over $R$.

To create a \code{DDRing}, the user has to provide the base ring $R$ for the coefficients of
the differential operators. There are several optional inputs that allow more
flexibility and a wider use of the structure. For more information, the user can type
\code{DDRing?} in Sage to obtain all the information about it.

The use of a \code{DDRing} in Sage is restricted to creating elements within itself (see the description
of the method \code{element} in the \cref{subsec:ddfunction}) and to get information
about the ring $R$ over the \code{DDRing} is based on.

Two \code{DDRings} are defined by default in the system when the package is loaded: the object
\code{DFinite} that is the ring of D-finite functions, and \code{DDFinite} which represents
the ring of DD-finite functions.

\begin{lstlisting}[numbers=none]
sage: DDFinite
	DD-Ring over (DD-Ring over (Univariate Polynomial Ring in x over 
	Rational Field))
sage: Qi.<i> = NumberField(x^2+1)
sage: S = DDRing(Qi[x])
sage: S
	(DD-Ring over (Univariate Polynomial Ring in x over Number Field 
	in i with defining polynomial x^2 + 1))
\end{lstlisting}


\subsection{DDFunction}\label{subsec:ddfunction}

The class \code{DDFunction} represents differentially definable functions over any ring. It is composed
of a linear differential operator and some initial conditions. Moreover, it is the \emph{Element} class
of a \code{DDRing}, so every \code{DDFunction} must be included in a particular \code{DDRing}.

To create a \code{DDFunction}, the user must use the method \code{element} of the \code{DDRing} where
the function belongs. A function $f(x)$ satisfying a linear differential equation with coefficients
$r_i$ and initial values $a_i$ is created from two lists $[r_0,\dots,r_d]$ and $[a_0,\dots,a_n]$,
i.e.,
	\[([r_0,\dots,r_d], [a_0,\dots,a_n]) \mapsto 
	\left\{\begin{array}{c}
		r_df^{(d)}(x) + \dots + r_0f(x) = 0,\\ 
		f(0) = a_0, \dots, f^{(n)}(0) = a_n. 
	\end{array}\right.\]
	
The method \code{element} also checks that the coefficients $r_i$ are in the appropriate ring of coefficients
$R$ and that the initial conditions $a_i$ are elements of the field where the function $f(x)$
is considered.

\begin{lstlisting}[numbers=none]
sage: f = R.element([-i,1],[1]) # f == exp(i*x)
sage: g = R.element([i,1],[1]) # g == exp(-i*x)
sage: (f+g)/2 == Cos(x)
	True
\end{lstlisting}


\section{Selected methods and main features}\label{sec:features}

\subsection{The structure of \code{DDFunction}}

The package provide several methods to extract information from a \code{DDFunction}

\begin{itemize}
 \item \code{equation}: the differential operator that defines the function.
 \item \code{getInitialValue}: the value of the $n$th derivative of the function at $x=0$.
 \item \code{getSequenceElement}: the value of the $n$th coefficient of the power series.
 \item \code{getOrder}: the order of the differential operator defining the function.
 \item \code{min\_coefficient}: the first non-zero coefficient of the power series
 \item \code{zero\_extraction}: the order of the power series and the \code{DDFunction} defined after
 factoring the maximal power of $x$ possible.
\end{itemize}

\begin{lstlisting}[numbers=none]
sage: f = DFinite.element([1,0,1],[0,1]) # f == sin(x)
sage: f.equation
	Wrapped_OreOperator(D^2 + 1)
sage: [f.getInitialValue(n) for n in range(5)]
	[0, 1, 0, -1, 0]
sage: [f.getSequenceElement(n) for n in range(5)]
	[0, 1, 0, -1/6, 0]
sage: f.getOrder(), f.min_coefficient()
	(2, 1)
sage: n, g = f.zero_extraction
sage: n
	1
sage: print g
	(2:2:4)DD-Function in (DD-Ring over (Univariate Polynomial Ring 
	in x over Rational Field)):
	-------------------------------------------------
		-- Equation (self = f):
			f  * (x)
			+   D(f) * (2)
			+ D^2(f) * (x)
			= 0 
		-- Initial values:
		[1, 0, -1/3]
	-------------------------------------------------
sage: x*g == f
	True
\end{lstlisting}

\subsection{Closure properties}

All the arithmetic operations are implemented using Python magic methods. This 
enables to use also Sage coercion system for a more \emph{user friendly} use of the package.
For more details on the algorithms, see~\cite{ajp:vp:issac18}

\begin{itemize}
 \item \textbf{Addition}: \code{add} or simply \code{+}
 \item \textbf{Multiplication}: \code{mult} or simply \code{*}
 \item \textbf{Difference}: \code{sub} or simply \code{-}
 \item \textbf{Exponentiation}: \code{pow} or simply \code{\^}
 \item \textbf{Multiplicative Inverse:} \code{inverse} returns a \code{DDFunction} representing the 
 multiplicative inverse of the function.
\end{itemize}

\begin{lstlisting}[numbers=none]
sage: sin = DFinite.element([1,0,1],[0,1])
sage: cos = DFinite.element([1,0,1],[1,0])
sage: sin^2 + cos^2 == 1
	True
sage: sec = cos.inverse
sage: print sec
	(1:1:5)DD-Function in (DD-Ring over (DD-Ring over (Univariate 
	Polynomial Ring in x over Rational Field))):
	-------------------------------------------------
		-- Equation (self = f):
	(2:2:2)	f  * (DD-Function in (DD-Ring over (Univariate Polynomial 
	Ring in x over Rational Field)))
	(2:2:2)	+   D(f) * (DD-Function in (DD-Ring over (Univariate 
	Polynomial Ring in x over Rational Field)))
			= 0 
		-- Initial values:
		[1, 0]
	-------------------------------------------------
sage: cos*sec
	1
sage: sin*sec == Tan(x)
	True
\end{lstlisting}

The user can also perform differential operations over a \code{DDFunction}, like computing the 
derivative ($f'(x)$) or computing the indefinite integral ($\int f$).

\begin{itemize}
 \item \code{derivative}: returns a \code{DDFunction} with the derivative.
 \item \code{integrate}: returns a \code{DDFunction} with an indefinite integral. The value at $x=0$ 
 can be specified. By default, it is $0$.
\end{itemize}

\begin{lstlisting}[numbers=none]
sage: f = DDFinite.element([Cos(x)^3, Sin(x), Cos(x)], [0,1])
sage: df = f.derivative()
sage: f.integrate().derivative() == f
	True
sage: df.integrate(0) == f
	True
sage: all(f.getInitialValue(n+1) == df.getInitialValue(n) for n 
....: in range(10))
	True
\end{lstlisting}

As recently proven~\cite{ajp:vp:ms:structure}, the composition of differentially definable 
functions is again differentially definable and the implementation described in that report is 
included into the package. The method \code{compose} or the magic method \code{\_\_call\_\_} do the job.

\begin{lstlisting}[numbers=none]
sage: f = DDFinite.element([Cos(x)^3, Sin(x), Cos(x)], [0,1])
sage: sin = DFinite.element([1,0,1],[0,1])
sage: g = sin(f)
sage: print g
	(2:2:95)DD-Function in (DD-Ring over (DD-Ring over (DD-Ring over 
	(Univariate Polynomial Ring in x over Rational Field)))):
	-------------------------------------------------
		-- Equation (self = f):
	(4:4:37) 	f  * (((sin(sin(x)))')^3)
	(2:2:37) -	D(f) * ((sin(sin(x)))'')
	(2:2:19) +	D^2(f) * ((sin(sin(x)))')
			= 0 
		-- Initial values:
		[0, 1, 0]
	-------------------------------------------------
sage: sin(sin) == f
	True
\end{lstlisting}

\subsection{Algebraic and Differentially Algebraic properties}

Functions that are algebraic over a differential field $F$ are also
differentially definable over $F$~\cite{mk:pp:CT, ajp:vp:ms:structure}. 
Given the polynomial defining an algebraic function, the user can get a \code{DDFunction}
associated with such function using the method \code{DAlgebraic}.

\begin{lstlisting}[numbers=none]
sage: Q.<x,y> = QQ[];
sage: p = x*y^2 - y + 1 # Minimal polynomial for Catalan gen. func.
sage: f = DAlgebraic(p, [1,1])
sage: print f
	(2:2:5)DD-Function in (DD-Ring over (Univariate Polynomial Ring 
	in x over Rational Field)):
	-------------------------------------------------
		-- Equation (self = f):
				f  * (2)
			+	D(f) * (10*x - 2)
			+	D^2(f) * (4*x^2 - x)
			= 0 
		-- Initial values:
		[1, 1, 4]
-------------------------------------------------
sage: [f.getSequenceElement(n) for n in range(10)] # Catalan numbers
	[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]
\end{lstlisting}

We also proved in~\cite{ajp:vp:ms:structure} that DD-finite functions are differentially algebraic.
Using the method \code{diff\_to\_diffalg}, the user can compute from a \code{DDFunction} an associated
differentially algebraic equation with polynomial coefficients.

\begin{lstlisting}[numbers=none]
sage: cos = DFinite.element([1,0,1],[1,0])
sage: diff_to_diffalg(cos)
	y_2 + y_0
sage: f = DDFinite.element([-Exp(x), 1], [1]) # f == exp(exp(x)-1)
sage: diff_to_diffalg(f)
	y_1^2 - y_2*y_0 + y_1*y_0
\end{lstlisting}

\subsection{Built-in functions of the package}

Aiming for a more user friendly interface, we provide a set of examples of D-finite and DD-finite functions
that can be easily called and built from Sage once the package is loaded. Some of these functions
are elementary as the exponential function or trigonometric functions; some are special 
functions as the hypergeometric $_pF_q$ functions, solutions to the Riccati equation,
the Mathieu functions or some generating functions for combinatorial sequences.

All implemented functions can be checked in Sage by typing \code{ddExamples?}. This command displays the 
documentation for the \code{ddExamples} file where all these built-in functions are explained.

\section{Conclusions}

The Sage package \code{ajpastor.dd\_functions} provides a functional-focused implementation
of differentially definable functions for arbitrary differential rings. In particular,
it can be used for working with regular D-finite functions and DD-finite functions.

This package can be used to prove symbolically identities between DD-finite functions
and to obtain combinatorial sequences that are out of the D-finite scope.

Closure properties, such as addition, multiplication and exponentiation can be performed by
the package, as well as other operations such as composition or division. It also provides several methods 
to convert algebraic functions to \code{DDFunction} manipulating a defining polynomial to obtain a 
differential equation, and to compute a non-linear equation with polynomial coefficients for any 
differentially definable function.

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography
\end{document}