Applications of Computer Algebra 2014

  Computational Differential and Difference Algebra

Fordham Universty, Bronx, NY, July 9-12, 2014



  • Differential and difference Galois theories of linear differential and difference equations with parameters
  • Applications to differential and difference algebraic dependencies among solutions of differential and difference equations
  • Differential and difference elimination
  • Interactions with computational aspects of differential and difference equations
  • Interactions with traditional areas of symbolic computation
  • Related events

  • July 7, 8, and 14, 2014: lectures at the Kolchin Seminar in Differential Algebra
  • Financial support

  • Supported in part by the National Science Foundation grant DMS-1413859
  • Talks

    Videos of the talks

    1. Carlos Arreche

      Title: Computing differential Galois groups of parameterized second-order linear differential equations

      Abstract: We describe recent algorithms to compute the differential Galois group G associated to a parameterized second-order homogeneous linear differential equation with respect to d/dx, with coefficients lie in the field F(x) of rational functions in x with coefficients in a partial differential field F of characteristic zero. As an application of these algorithms, we present a set of criteria to decide the differential transcendence of the solutions with respect to the parametric derivations on F.


    2. Moulay Barkatou

      Title: A direct algorithm for computing k-simple forms of first-order linear differential systems

      Abstract: Most algorithms for computing solutions of linear ordinary differential equations proceed by investigating the singularities of the coefficients to obtain information on the singularities of the solutions. For systems, this is more difficult than for scalar equations and a main tool for computing the local exponents and the non-ramified local exponential parts in this case is Moser- and super-reduction. From super-reduced forms, one can compute all the integer slopes of the Newton-polygon and determine the corresponding Newton polynomials. Moser- and super-reduced forms are also used in the computation of the formal solutions of the system around a singularity and in the computation of the global solutions such as the rational solutions and the exponential solutions. However, solving some of these problems requires only weaker forms called k-simple forms. In this talk, we present a direct (i.e., without computing first a super-reduced form) algorithm for computing k-simple forms of first-order differential systems at x=0 with coefficients from C((x)), where C is a field of constants. We give the arithmetic complexity of our algorithm which has been implemented in Maple and we illustrate it with some examples. Finally, we show how using this algorithm one can find the formal invariants of the system at x=0.


    3. James Freitag

      Title: Bounding the size of a finite differential algebraic variety

      Abstract: Given a collection of differential polynomials, f_1,.., f_n, suppose that their common solution set is finite. In the ordinary case, Hrushovski and Pillay showed how to get effective bounds for the size of this finite solution set in terms of the orders and degrees of the differential polynomials. This result is at the differential algebraic heart of various applications of differential algebra to problems in diophantine geometry (due to Hrushovski, Pillay and recent results of Freitag and Scanlon). The proof of the upper bound is algorithmic, and reveals how the problem is related to so-called geometric axioms for differentially closed fields. The upper bound eventually comes from intersection theory in arc spaces. We will explain how to extend this work to the partial case, which is more involved, essentially due to the coherence condition for differential polynomials. If time permits, recent diophantine applications related to the the Andre-Oort conjecture will be given. This is joint work with Omar Leon Sanchez.


    4. Xiao-Shan Gao

      Title: Binomial difference ideal and toric difference variety

      Abstract: The concepts of binomial difference ideals and toric difference varieties are defined and their properties are proved. Two canonical representations for Laurent binomial difference ideals are given using the reduced Groebner basis of Z[x] lattices and regular and coherent difference ascending chains, respectively. Criteria for a Laurent binomial difference ideal to be reflexive, prime, perfect, and toric are given in terms of their support lattices which are Z[x] lattices. The reflexive and perfect closures of a Laurent binomial difference ideal are shown to be binomial. Four equivalent definitions for toric difference varieties are presented. Finally, algorithms are given to check whether a given Laurent binomial difference ideal I is reflexive, prime, perfect, or toric, and in the negative case, to compute the reflexive and perfect closures of I. An algorithm is given to decompose a finitely generated perfect binomial difference ideal as the intersection of reflexive prime binomial difference ideals.


    5. Florian Heiderich

      Title: Towards a non-commutative Picard-Vessiot theory

      Abstract: André unified the Galois theories of linear differential equations and of linear difference equations. This talk aims to explain a more general approach to a Galois theory of linear functional equations involving a wide class of operators not only containing derivations and automorphisms, but also skew-derivations.


    6. Maximilian Jaroschek

      Title: Radicals of Ore polynomials

      Abstract: We give a comprehensible algorithm to compute the radical of an Ore operator. Given an operator P, we find another operator L and a positive integer k such that P is the kth power of L and k is maximal among all integers for which such an operator L exists. Furthermore we discuss possible extensions of this procedure to identify operators of the form A*P where P is the k-th power of some operator L and to derive a reduced operator A*L.


    7. Gabriela Jeronimo

      Title: Effective differential Lüroth theorem

      Abstract: Let F be a differential field of characteristic 0 and L the field of differential rational functions in a single indeterminate u. The differential Lüroth theorem proved by Ritt and extended by Kolchin states that for any differential subfield G of L there exists v in G such that G is the field of differential rational functions in v. The talk will focus on effectivity aspects of this result. More precisely: given non-constant rational functions v_1 ,..., v_n in L such that G is the field of differential rantional functions in v_1,...,v_n, we will give upper bounds for the total order and degree of a Luroth generator v of the extension G/F in terms of the number and the maximum order and degree of the given generators of G. Our approach combines elements of Ritt's and Kolchin's proofs with estimations concerning the order and the differentiation index of differential ideals. As a byproduct, we will show that our techniques enable the computation of a Lüroth generator by dealing with a polynomial ideal in a polynomial ring in finitely many variables. This is joint work with Lisi D'Alfonso and Pablo Solerno.


    8. Lourdes Juan

      On the integration of algebraic functions: computing the logarithmic part

      Bronstein developed a complete algorithm to compute the logarithmic part of an integral of a function that lies in a tower of transcendental elementary extensions. However, computing the logarithmic part in an algebraic extension has remained difficult and challenging. In his PhD dissertation, Brian Miller, building on the work of Manuel Kauers, developed a method to compute the logarithmic part when the function lies in a tower of transcendental elementary extensions followed by an algebraic extension. The method uses Grobner bases and primary decomposition. In this talk we will discuss Miller’s work and work in progress to produce a complete algorithm for some particular cases of algebraic functions.


    9. Irina Kogan

      Title: Differential algebra of invariants and invariant variational calculus

      Abstract: Systems of differential equations and variational problems arising in geometry and physics often admit a group of symmetries. As was first recognized by S. Lie, these problems can be rewritten in terms of group-invariant objects: differential invariants, invariant differential forms, and invariant differential operators. Differential invariants and invariant differential operators constitute a differential algebra with often non-trivial but computable structure. It is desirable from both computational and theoretical points of view to study invariant problems in terms of invariant differential algebra. In this talk, we will describe how differential algebra of invariants can be constructed and show applications to variational calculus.


    10. George Labahn

      Title: Convolution integrals of holonomic functions

      Abstract: In this talk we describe a procedure for determining closed form solutions of convolution integrals of holonomic functions. Because such integrals require knowing strips of convergence in the complex plane determining closed form solutions requires a mix of both algebra and analysis. We describe the tools used from complex analysis, particularly Mellin transforms, analytic continuations and distributions which all play vital roles in the analysis. This is joint work with Jason Peasgood (Waterloo) and Bruno Salvy (France).

      Updated video

    11. Markus Lange-Hegermann

      Title: Counting solutions of differential equations

      Abstract: The aim of this talk is a quantitative analysis of the solution set of a system of differential equations. We generalize Kolchin's differential dimension polynomial and its properties from prime differential ideals to characterizable differential ideals. This makes the dimension polynomial more accessible for algorithms. In certain applications, an even more detailed quantitative description of differential equations is needed. Therefore, we introduce the differential counting polynomial, a generalization of the differential dimension polynomial. The tools used in this talk are the decomposition algorithms by J.M. Thomas.


    12. Francois Lemaire

      Title : New development and application of integration of differential fractions

      Abstract : The publication "On the Integration of Differential Fractions" published at ISSAC'13 (Boulier, Lemaire, Regensburger, Rosenkranz) introduces the differential fractions (which are quotients of differential polynomials) and presents algorithms for representing such fractions. In particular, a differential fraction F can be decomposed into F = G + dH/dx (where G and H are differential fractions and d/dx designates the total derivative w.r.t. x). I will present recent developments concerning the canonicity of such a decomposition, as well as numerical applications of the decomposition in the context of parameters estimation.


    13. Omar Leon Sanchez

      Title: Parametrized logarithmic equations and their Galois theory

      Abstract: I will talk about (parametrized) differential D-groups which are not necessarily defined over a field of constants. Then, I will present the foundational results on the Galois theory of logarithmic differential equations in such groups. I will also discuss two natural non-linear examples of such equations which are not defined over the constants.


    14. Alexander Levin

      Title: Generalized Groebner bases and dimension polynomials of modules over some finitely generated noncommutative algebras

      Abstract: I will present a generalized Groebner basis method in free modules over finitely generated noncommutative algebras of a certain class that includes, in particular, algebras of difference-differential operators, Ore algebras, quantized (and classical) Weyl algebras. I will show the existence and give methods of computation of univariate and multivariate dimension polynomials associated with systems of generators of finitely generated modules over such algebras. I will also determine invariants of the dimension polynomials, that is, numerical characteristics carried by these polynomials that do not depend on the choice of the corresponding systems of module generators.


    15. Suzy S. Maddah

      Title: Formal Solutions of Completely Integrable Pfaffian Systems with Normal Crossings

      Abstract: Abstract: In this talk, we are interested in the formal reduction of the so-called completely integrable Pfaffian systems with normal crossings, i.e. the class of linear systems of partial differential equations.  Pfaffian systems arise in many applications including the studies of aerospace and celestial mechanics (see, e.g., Awane et al.' 2000 and Broucke' 1978). By far the most important for applications are those with normal crossings (Novikov et al.' 2004).  The theoretical results by Charrière et al.'1980-1981 and van den Essen et al.' 1982,  give the existence and properties of a fundamental matrix of formal solutons. However, the formal reduction, i.e. the algorithmic procedure that computes the transformation which takes the system into its canonical form so that formal solutions can be constructed, is a question of another nature.  Clearly, the particular univariate case corresponds to singular linear systems of ordinary differential equations which have been studied extensively (see, e.g., Balser' 2000, Wasow' 1965, and references therein). Moreover, unlike the multivariate case, algorithms to related problems leading to the construction of the formal solutions have been developed by various authors (see, e.g., Barkatou et al.' 1997-2009, and references therein).
      We present an algorithm to construct  a fundamental matrix of formal solutions of completely integrable Pfaffian systems with normal crossings in two variables. Our algorithm is based on associating to the Pfaffian system a singular linear system of ordinary differential equations from which its formal invariants can be efficiently derived. We then discuss the extension of this algorithm to the multivariate case. Our algorithm builds upon the package ISOLDE and is implemented in the computer algebra system Maple.


    16. Annette Maier

      Title: Parameterized differential equations and patching

      Abstract: We consider linear parameterized differential equations over k((t))(x) with parameter t such as d_x(y)=ty/x. The parameterized Galois group of such an equation is a linear differential algebraic group over k((t)), i.e., a subgroup of GL_n given by differential d_t-algebraic equations. In the example above, the parameterized Galois group equals G={c non-zero | d_t^2(c)c-d_t(c)^2=0}. The inverse problem asks which linear differential algebraic groups occur as parameterized Galois groups. In the talk, I will explain how algebraic patching methods can be applied to realize a certain class of groups as parameterized Galois groups over k((t))(x).


    17. Alice Medvedev

      Title: Dimensions of difference-algebraic groups

      Abstract: Model-theoretic dimensions (Lascar rank, Morley rank) of groups defined by difference equations of the form x in G and sigma^m(x) = f(x) for some algebraic group G and some algebraic group morphism f : G-> sigma^m(G) are relatively easy to compute. I will discuss two interesting and useful notions of the limit of these dimensions as m tends to infinity.


    18. Sergey Paramonov

      Title: Undecidability of the uniqueness testing problem for analytic solutions of PLDE with boundary conditions

      Abstract: We consider linear partial differential equations with polynomial coefficients and prove algorithmic undecidability of the following problem: to test whether a given equation of considered form has no more than one solution that is analytic on an open region and that satisfies some fixed boundary conditions. It is assumed that a polynomial which vanishes at each of points of the region bound is known.

    19. Julien Roques

      Title: Galois groups of difference equations on elliptic curves

      Abstract: The main purpose of this talk is to compute the Galois groups of some difference equations of order two on elliptic curves, such as discrete Lamé equations.

    20. Michael Wibmer

      Title: A Jordan-Hölder theorem for difference algebraic groups

      Abstract: Difference algebraic groups, i.e., groups defined by algebraic difference equations occur as the Galois groups of linear differential and difference equations depending on a discrete parameter. In this talk I will introduce difference algebraic groups and explain some of their basic properties. In particular, I will present an analog of the Jordan-Hölder theorem for difference algebraic groups.


    21. Meng Zhou

      Title: On the termination of algorithm for computing relative Gröbner bases and difference-differential dimension polynomials

      Abstract: Relative Gröbner bases were introduced by Zhou and Winkler(2008) in order to compute bivariate dimension polynomials in difference-differential modules. The algorithm for computing relative Gröbner bases and bivariate dimension polynomials also were presented in Zhou and Winkler(2008). Christian Dönch (2010) gave a Maple software of the algorithm. By now it is used as the main tool for the algorithmic computation of bivariate dimension polynomials in difference-differential modules.
      Recently Christian Dönch(2013) presented an example pointing out the algorithm does not terminate in some case. From the counterexample Dönch pointed out that it is questionable whether a relative Gröbner basis always exists. Also it is uncertain whether the algorithm for computing bivariate dimension polynomials in difference-differential modules terminates.
      In this paper we improve the results of Zhou and Winkler(2008) about relative Gröbner bases. We introduce the concept of difference-differential degree compatibility on generalized term orders. Then we prove that in the process of the algorithm the polynomials with higher and higher degree wouldn't be produced, if the term orders "<" and "<'" are difference-differential degree compatibility. So we present a condition on the generalized orders and prove that under the condition the algorithm for computing relative Gröbner bases will terminate. Also the relative Gröbner bases exist under the condition. Finally we prove the algorithm for computation of the bivariate dimension polynomials in difference-differential modules terminates.