# Symbolic Summation/Integration and Algebraic Relations [SSIAR]

### Project Description

Budget EUR 113547,-

### Project Duration

01/04/2007 - 30/03/2009

## Publications

### The Complete Generating Function for Gessel Walks is Algebraic

#### Alin Bostan, Manuel Kauers

Proceedings of the AMS 138(9), pp. 3063-3078. September 2010. ISSN 0002-9939. [pdf] [ps]
@article{RISC3945,
author = {Alin Bostan and Manuel Kauers},
title = {{The Complete Generating Function for Gessel Walks is Algebraic}},
language = {english},
abstract = { Gessel walks are lattice walks in the quarter plane $\set N^2$ which start at the origin~$(0,0)\in\set N^2$ and consist only of steps chosen from the set $\{\leftarrow,\penalty0\swarrow,\penalty0\nearrow,\penalty0\rightarrow\}$. We prove that if $g(n;i,j)$ denotes the number of Gessel walks of length~$n$ which end at the point~$(i,j)\in\set N^2$, then the trivariate generating series $\displaystyle\smash{ G(t;x,y)=\sum_{n,i,j\geq 0} g(n;i,j)x^i y^j t^n }$ is an algebraic function.},
journal = {Proceedings of the AMS},
volume = {138},
number = {9},
pages = {3063--3078},
isbn_issn = {ISSN 0002-9939},
year = {2010},
month = {September},
refereed = {yes},
length = {16}
}

### When can we detect that a P-finite sequence is positive?

#### Manuel Kauers, Veronika Pillwein

In: Proceedings of ISSAC'10, , pp. 195-202. 2010. 978-1-4503-0150-3. [pdf] [ps]
@inproceedings{RISC4022,
author = {Manuel Kauers and Veronika Pillwein},
title = {{When can we detect that a P-finite sequence is positive?}},
booktitle = {{Proceedings of ISSAC'10}},
language = {english},
abstract = {We consider two algorithms which can be used for proving positivity ofsequences that are defined by a linear recurrence equation with polynomial coefficients (P-finite sequences). Both algorithms have in common that while they do succeed on a greatmany examples, there is no guarantee for them to terminate, and theydo in fact not terminate for every input.For some restricted classes of P-finite recurrence equations of order up to three we provide a priori criteria that assert the termination of the algorithms.},
pages = {195--202},
isbn_issn = {978-1-4503-0150-3},
year = {2010},
editor = {Stephen Watt},
refereed = {yes},
length = {7}
}

### Algorithms in Symbolic Computation

#### Peter Paule, Bruno Buchberger, Lena Kartashova, Manuel Kauers, Carsten Schneider, Franz Winkler

In: Hagenberg Research, , Chapter 1, pp. 5-62. 2009. Springer, 978-3-642-02126-8. [pdf]
@incollection{RISC3845,
author = {Peter Paule and Bruno Buchberger and Lena Kartashova and Manuel Kauers and Carsten Schneider and Franz Winkler},
title = {{Algorithms in Symbolic Computation}},
booktitle = {{Hagenberg Research}},
language = {english},
chapter = {1},
pages = {5--62},
publisher = {Springer},
isbn_issn = {978-3-642-02126-8},
year = {2009},
annote = {2009-00-00-C},
editor = {Bruno Buchberger et al.},
refereed = {no},
length = {58}
}

### A Non-Holonomic Systems Approach to Special Function Identities

#### Frederic Chyzak, Manuel Kauers, Bruno Salvy

In: Proceedings of ISSAC'09, , pp. 111-118. 2009. 978-1-60558-609-0. [pdf] [ps]
@inproceedings{RISC3815,
author = {Frederic Chyzak and Manuel Kauers and Bruno Salvy},
title = {{A Non-Holonomic Systems Approach to Special Function Identities}},
booktitle = {{Proceedings of ISSAC'09}},
language = {english},
abstract = {We extend Zeilberger's approach to special function identities to cases that are notholonomic. The method of creative telescoping is thus applied to definite sums orintegrals involving Stirling or Bernoulli numbers, incomplete Gamma function orpolylogarithms, which are not covered by the holonomic framework. The basic idea is to takeinto account the dimension of appropriate ideals in Ore algebras. This unifies severalearlier extensions and provides algorithms for summation andintegration in classes that had not been accessible to computer algebra before.},
pages = {111--118},
isbn_issn = {978-1-60558-609-0},
year = {2009},
editor = {John May},
refereed = {yes},
length = {8}
}

### Automatic Classification of Restricted Lattice Walks

#### Alin Bostan, Manuel Kauers

In: Proceedings of FPSAC'09, , pp. 201-215. 2009. [ps] [pdf]
@inproceedings{RISC3838,
author = {Alin Bostan and Manuel Kauers},
title = {{Automatic Classification of Restricted Lattice Walks}},
booktitle = {{Proceedings of FPSAC'09}},
language = {english},
abstract = {We propose an experimental mathematics approach leading to the computer-driven discovery of various conjectures aboutstructural properties of generating functions coming from enumeration of restricted lattice walks in 2D and in 3D.},
pages = {201--215},
isbn_issn = { },
year = {2009},
editor = {Christian Krattenthaler and Volker Strehl and and Manuel Kauers},
refereed = {yes},
length = {14}
}

### A Mathematica Package for q-Holonomic Sequences and Power Series

#### Manuel Kauers, Christoph Koutschan

The Ramanujan Journal 19(2), pp. 137-150. 2009. Springer, ISSN 1382-4090. [pdf] [ps]
@article{RISC3437,
author = {Manuel Kauers and Christoph Koutschan},
title = {{A Mathematica Package for q-Holonomic Sequences and Power Series}},
language = {english},
abstract = { We describe a Mathematica package for dealing with $q$-holonomic sequences and power series. The package is intended as a $q$-analogue of the Maple package gfun and the Mathematica package GeneratingFunctions. It provides commands for addition, multiplication, and substitution of these objects, for converting between various representations ($q$-differential equations, $q$-recurrence equations, $q$-shift equations), for computing sequence terms and power series coefficients, and for guessing recurrence equations given initial terms of a sequence.},
journal = {The Ramanujan Journal},
volume = {19},
number = {2},
pages = {137--150},
publisher = {Springer},
isbn_issn = {ISSN 1382-4090},
year = {2009},
refereed = {yes},
length = {14}
}

### A Proof of George Andrews' and Dave Robbins' q-TSPP-Conjecture (modulo a finite amount of routine calculations)

#### Manuel Kauers, Christoph Koutschan, Doron Zeilberger

The personal Journal of Ekhad and Zeilberger, pp. 1-8. January 2009. [url] [pdf] [ps]
@article{RISC3801,
author = {Manuel Kauers and Christoph Koutschan and Doron Zeilberger},
title = {{A Proof of George Andrews' and Dave Robbins' q-TSPP-Conjecture (modulo a finite amount of routine calculations)}},
language = {english},
journal = {The personal Journal of Ekhad and Zeilberger},
pages = {1--8},
isbn_issn = { },
year = {2009},
month = {January},
refereed = {no},
length = {8},
url = {http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/qtspp.html}
}

### Proof of Ira Gessel's Lattice Path Conjecture

#### Manuel Kauers, Christoph Koutschan, Doron Zeilberger

Proceedings of the National Academy of Sciences 106(28), pp. 11502-11505. July 2009. ISSN 0027-8424. [ps] [pdf]
@article{RISC3837,
author = {Manuel Kauers and Christoph Koutschan and Doron Zeilberger},
title = {{Proof of Ira Gessel's Lattice Path Conjecture}},
language = {english},
abstract = { We present a computer-aided, yet fully rigorous, proof of Ira Gessel's tantalizingly simply-stated conjecture that the number of ways of walking $2n$ steps in the region $x+y \geq 0, y \geq 0$ of the square-lattice with unit steps in the east, west, north, and south directions, that start and end at the origin, equals $16^n\frac{(5/6)_n(1/2)_n}{(5/3)_n(2)_n}$ .},
journal = {Proceedings of the National Academy of Sciences},
volume = {106},
number = {28},
pages = {11502--11505},
isbn_issn = {ISSN 0027-8424},
year = {2009},
month = {July},
refereed = {yes},
length = {4}
}

### Determining the closed forms of the {$O(a_s^3)$} anomalous dimensions and {W}ilson coefficients from {M}ellin moments by means of computer algebra

#### J. Bluemlein, M. Kauers, S. Klein, C. Schneider

Comput. Phys. Comm. 180, pp. 2143-2165. 2009. ISSN 0010-4655. [pdf]
@article{RISC3846,
author = {J. Bluemlein and M. Kauers and S. Klein and C. Schneider},
title = {{Determining the closed forms of the {$O(a_s^3)$} anomalous dimensions and {W}ilson coefficients from {M}ellin moments by means of computer algebra}},
language = {english},
journal = {Comput. Phys. Comm. },
volume = {180},
pages = {2143--2165},
isbn_issn = {ISSN 0010-4655},
year = {2009},
refereed = {yes},
length = {23}
}

### Solving Difference Equations whose Coefficients are not Transcendental

#### Manuel Kauers

Theoretical Computer Science 401(1-3), pp. 217-227. July 2008. ISSN 0304-3975. [pdf] [ps]
@article{RISC3368,
author = {Manuel Kauers},
title = {{Solving Difference Equations whose Coefficients are not Transcendental}},
language = {english},
abstract = {We consider a large class of sequences which are defined by systems of (possibly nonlinear) difference equations. A procedure for recursively enumerating the algebraic dependencies of such sequences is presented. Also a procedure for solving linear difference equations with such sequences as coefficients is proposed. The methods are illustrated on some problems arising in the literature on special functions and combinatorial sequences.},
journal = {Theoretical Computer Science},
volume = {401},
number = {1-3},
pages = {217--227},
isbn_issn = {ISSN 0304-3975},
year = {2008},
month = {July},
refereed = {yes},
length = {11}
}

### The Quasi-Holonomic Ansatz and Restricted Lattice Walks

#### Manuel Kauers, Doron Zeilberger

Journal of Difference Equations and Applications 14(10-11), pp. 1119-1126. 2008. ISSN 1023-6198. to appear. [pdf] [ps]
@article{RISC3370,
author = {Manuel Kauers and Doron Zeilberger},
title = {{The Quasi-Holonomic Ansatz and Restricted Lattice Walks}},
language = {english},
journal = {Journal of Difference Equations and Applications},
volume = {14},
number = {10--11},
pages = {1119--1126},
isbn_issn = {ISSN 1023-6198},
year = {2008},
note = {to appear},
refereed = {yes},
length = {10}
}

### Experiments with a Positivity Preserving Operator

#### Manuel Kauers, Doron Zeilberger

Experimental Mathematics 17(3), pp. 341-345. 2008. ISSN 1058-6458. [pdf] [ps]
@article{RISC3394,
author = {Manuel Kauers and Doron Zeilberger},
title = {{Experiments with a Positivity Preserving Operator}},
language = {english},
abstract = { We consider some multivariate rational functions which have (or are conjectured to have) only positive coefficients in their series expansion. We consider an operator that preserves positivity of series coefficients, and apply the inverse of this operator to the rational functions. We obtain new rational functions which seem to have only positive coefficients, whose positivity would imply positivity of the original series, and which, in a certain sense, cannot be improved any further.},
journal = {Experimental Mathematics},
volume = {17},
number = {3},
pages = {341--345},
isbn_issn = {ISSN 1058-6458},
year = {2008},
refereed = {yes},
length = {5}
}

### Integration of Algebraic Functions: A Simple Heuristic for Finding the Logarithmic Part

#### Manuel Kauers

In: Proceedings of ISSAC'08, , Proceedings of ISSAC'08, pp. 133-140. 2008. 978-1-59593-904-3. [ps] [pdf]
@inproceedings{RISC3427,
author = {Manuel Kauers},
title = {{Integration of Algebraic Functions: A Simple Heuristic for Finding the Logarithmic Part}},
booktitle = {{Proceedings of ISSAC'08}},
language = {english},
abstract = { A new method is proposed for finding the logarithmic part of an integral over an algebraic function. The method uses Gr\"obner bases and is easy to implement. It does not have the feature of finding a closed form of an integral whenever there is one. But it very often does, as we will show by a comparison with the built-in integrators of some computer algebra systems.},
pages = {133--140},
isbn_issn = {978-1-59593-904-3},
year = {2008},
editor = {David Jeffrey},
refereed = {yes},
length = {8},
conferencename = {ISSAC'08}
}

### Computer Algebra for Special Function Inequalities

#### Manuel Kauers

In: Tapas in Experimental Mathematics, , Contemporary Mathematics 457, pp. 215-235. 2008. AMS, ISBN 978-0-8218-4317-8. [pdf] [ps]
@incollection{RISC3443,
author = {Manuel Kauers},
title = {{Computer Algebra for Special Function Inequalities}},
booktitle = {{Tapas in Experimental Mathematics}},
language = {english},
abstract = {Recent computer proofs for some special function inequalities are presented. Thealgorithmic ideas underlying these computer proofs are described, and the conceptualdifference to existing algorithms for proving special function identities is discussed.},
series = {Contemporary Mathematics},
volume = {457},
pages = {215--235},
publisher = {AMS},
isbn_issn = {ISBN 978-0-8218-4317-8},
year = {2008},
editor = {Tewodros Amdeberhan and Victor Moll},
refereed = {yes},
length = {21}
}

### Fast Solvers for Dense Linear Systems

#### Manuel Kauers

Nuclear Physics B (Proc. Suppl.) 183, pp. 245-250. 2008. ISSN 0550-3213. [ps] [pdf]
@article{RISC3778,
author = {Manuel Kauers},
title = {{Fast Solvers for Dense Linear Systems}},
language = {english},
abstract = {It appears that large scale calculations in particle physicsoften require to solve systems of linear equations with rational numbercoefficients exactly. If classical Gaussian elimination is applied to a\emph{dense} system, the time needed to solve such a system grows exponentiallyin the size of the system. In this tutorial paper, we present a standardtechnique from computer algebra that avoids this exponential growth:homomorphic images. Using this technique, big dense linear systemscan be solved in a much more reasonable time than using Gaussianelimination over the rationals.},
journal = {Nuclear Physics B (Proc. Suppl.)},
volume = {183},
pages = {245--250},
isbn_issn = {ISSN 0550-3213},
year = {2008},
refereed = {yes},
length = {6}
}

### Automated Proofs for Some Stirling Number Identities

#### Manuel Kauers , Carsten Schneider

The Electronic Journal of Combinatorics 15(1), pp. 1-7. 2008. ISSN 1077-8926. R2. [pdf] [ps]
@article{RISC3366,
author = {Manuel Kauers and Carsten Schneider},
title = {{Automated Proofs for Some Stirling Number Identities}},
language = {english},
abstract = {We present computer-generated proofs for some summation identities for($q$-)Stir\-ling and ($q$-)Eulerian numbers that were obtained by combining arecent summation algorithm for Stirling number identities with arecurrence solver for difference fields.},
journal = {The Electronic Journal of Combinatorics},
volume = {15},
number = {1},
pages = {1--7},
isbn_issn = {ISSN 1077-8926},
year = {2008},
note = {R2},
refereed = {yes},
length = {7}
}

### From moments to functions in higher order QCD

#### J. Bluemlein, M. Kauers, S. Klein, C. Schneider

In: Proc. of Science, , Proceedings of XII Advanced Computing and Analysis Techniques in Physics Research PoS(ACAT08)106, pp. 1-7. 2008. ISSN 1824-8039. [pdf]
@inproceedings{RISC3835,
author = {J. Bluemlein and M. Kauers and S. Klein and C. Schneider},
title = {{From moments to functions in higher order QCD }},
booktitle = {{Proc. of Science}},
language = {english},
volume = { PoS(ACAT08)106},
pages = {1--7},
isbn_issn = {ISSN 1824-8039},
year = {2008},
editor = {-},
refereed = {yes},
length = {7},
conferencename = {XII Advanced Computing and Analysis Techniques in Physics Research}
}

### Computing the Algebraic Relations of C-finite Sequences and Multisequences

#### Manuel Kauers, Burkhard Zimmermann

Journal of Symbolic Computation 43(11), pp. 787-803. 2008. ISSN 0747-7171.. [pdf] [ps]
@article{RISC3341,
author = {Manuel Kauers and Burkhard Zimmermann},
title = {{Computing the Algebraic Relations of C-finite Sequences and Multisequences}},
language = {english},
abstract = {We present an algorithm for computing generators for the ideal of algebraic relations among sequences which are given by homogeneous linear recurrence equations with constant coefficients. Knowing these generators makes it possible to use Groebner bases methods for carrying out certain basic operations in the ring of such sequences effectively. In particular, one can answer the question whether a given sequence can be represented in terms of other given sequences. },
journal = {Journal of Symbolic Computation},
volume = {43},
number = {11},
pages = {787--803},
isbn_issn = {ISSN 0747-7171.},
year = {2008},
refereed = {yes},
length = {25}
}

### Computer Algebra and Power Series with Positive Coefficients

#### Manuel Kauers

In: Proceedings of FPSAC'07, , pp. 1-7. 2007. [pdf] [ps]
@inproceedings{RISC3059,
author = {Manuel Kauers},
title = {{Computer Algebra and Power Series with Positive Coefficients}},
booktitle = {{Proceedings of FPSAC'07}},
language = {english},
abstract = {We consider the question whether all the coefficients in the series expansions of some specific rational functions are positive, and we demonstrate how computer algebra can help answering questions arising in this context. By giving partial computer proofs, we provide new evidence in support of some longstanding open conjectures. Also two new conjectures are made.},
pages = {1--7},
isbn_issn = {?},
year = {2007},
editor = {?},
refereed = {yes},
length = {7}
}

### Summation Algorithms for Stirling Number Identities

#### Manuel Kauers

Journal of Symbolic Computation 42(10), pp. 948-970. October 2007. ISSN 0747-7171. [pdf] [ps]
@article{RISC3240,
author = {Manuel Kauers},
title = {{Summation Algorithms for Stirling Number Identities}},
language = {english},
abstract = {We consider a class of sequences defined by triangular recurrence equations. This class contains Stirling numbers and Eulerian numbers of both kinds, and hypergeometric multiples of those. We give a sufficient criterion for sums over such sequences to obey a recurrence equation, and present algorithms for computing such recurrence equations efficiently.Our algorithms can be used for verifying many known summation identities about Stirling numbers instantly, and also fordiscovering new identities. },
journal = {Journal of Symbolic Computation},
volume = {42},
number = {10},
pages = {948--970},
isbn_issn = {ISSN 0747-7171},
year = {2007},
month = {October},
refereed = {yes},
length = {23}
}