Kolchin Seminar in Differential Algebra

Spring 2018

The schedule for the Fall 2018 semester is available here. For earlier seminars, see the old webpage. The seminar activities are partially supported by the National Science Foundation.

February 9, Erdal Imamoglu, North Carolina State University
Algorithms for Solving Linear Differential Equations with Rational Function Coefficients

Special time: 2:45-3:45pm
We present two algorithms for computing hypergeometric solutions of a second order linear differential equation with rational function coefficients. Our first algorithm uses quotients of formal solutions, modular reduction, Hensel lifting, and rational reconstruction. Our second algorithm first tries to simplify the input differential equation using integral bases for differential operators and then uses quotients of formal solutions.
Video

February 16, Michael Wibmer, University of Pennsylvania
Algebraic theory of difference equations

Special time: 10:30am-12:15pm
Difference equations are a discrete analog of differential equations. This talk will explain how the algebraic theory of difference equations provides a way to tackle problems in number theory, discrete dynamical systems and the theory of differential equations. For example, I have used the Galois theory of difference equations to prove a special case of the dynamical Mordell-Lang conjecture. Finiteness results will be a guiding theme for this talk. In particular, we will show that the ideal of all difference algebraic relations among the solutions of a linear differential equation is finitely generated.

February 23, Peter Olver, University of Minnesota
Algebras of Differential Invariants

Special time: 2:30-3:30 pm
A classical theorem of Lie and Tresse states that the algebra of differential invariants of a Lie group or (suitable) Lie pseudo-group action is finitely generated. I will present a fully constructive algorithm, based on the equivariant method of moving frames, that reveals the full structure of such non-commutative differential algebras, and, in particular, pinpoints generating sets of differential invariants as well as their differential syzygies. A variety of applications and outstanding issues will be discussed, including recent applications to classical invariant theory, equivalence and symmetry detection in image processing, and some surprising results in classical surface geometries.
Slides
Video

March 2, Anne Shiu, Texas A&M University
Identifiability of Linear Compartment Models: The Singular Locus

Special time: 2:15-3:30 pm
This talk addresses the problem of parameter identifiability—that is, the question of whether parameters can be recovered from data—or linear compartment models. Using standard differential algebraic techniques, the question of whether such a model is (generically, locally) identifiable is equivalent to asking whether the Jacobian matrix of a certain coefficient map, arising from input-output equations, is generically full rank. A formula for these input-output equations was given recently by Meshkat, Sullivant, and Eisenberg. Here we build on their results by giving a formula for the resulting coefficient maps. This formula is in terms of acyclic subgraphs of the directed graph underlying the linear compartment model. As an application, we prove that two families of linear compartment models—cycle and mammillary (star) models—are identifiable. We accomplish this by determining the defining equation for the singular locus of non-identifiable parameters. Our work helps to shed light on the open question of which linear compartment models are identifiable. This is joint work with Elizabeth Gross and Nicolette Meshkat.
Slides
Video

March 9, Gleb Pogudin, New York University
Analyticity of power series solutions of algebraic ODEs

One natural approach to solving a system of algebraic differential equations is to find a formal power series satisfying the system. It has been known for years that such a formal power series might diverge in any neightborhood, so might not result in an analytic solution. Thus, the question is how to check whether all formal the power series solutions of a given system do converge. Surprisingly, there exists a purely algebraic sufficient criteria for that, which was obtained recently by O. Gerasimova and Yu.P. Razmyslov. It is based on the transcendence degree of the corresponding differential algebra and its homomorphic images. In the talk I will describe these results and explain how these results explain the fact that many power series solutions of equations arising in practice actually define analytic functions.
Video

March 16, William Sit, City College, CUNY
What Initial Values Guarantee Existence and Uniqueness in Algebraic Differential Systems?

This talk is complementary to the talk given last week by Gleb Pogudin on the convergence of power series solutions to systems of ODEs. The main result reported by Pogudin is that under certain conditions, for any prescribed initial values, the formal power series solution, if it exists, will be convergent. Pritchard and Sit studied initial value problems for differential algebraic ODES in relation to the question of existence and uniqueness of solutions. In this talk, we describe a theoretical as well as computational approach to obtain algebraic constraints on initial values that would guarantee existence and uniqueness of solutions. Our method works directly for a wide class of linear or non-linear systems of first order ordinary differential equations and in addition to obtaining the constraints, the algorithm (implemented in Axiom) will also provide equivalent systems where the first derivatives of the dependent variables are explicitly given in terms of rational functions. These rational vector fields can be integrated in a numerically stable way. Higher order systems can be dealt with by the usual reduction to first order systems. Singularities are exposed by the algorithm in some simple examples.
Reference: F. L. Pritchard and W. Sit, On Initial Value Problems for Ordinary Differential-Algebraic Equations, in Grobner Bases in Symbolic Analysis, M. Rosenkranz and D. Wang eds., Radon Series Comp. Appl. Math 2, 283-340, Walter de Gruyter, 2007.
Slides

March 23, Francis Valiquette, SUNY at New Paltz
Group Foliation of Finite Difference Equations Using Equivariant Moving Frames

Given a finite difference equation with continuous symmetry group G, I will explain how to solve such an equation using the method of equivariant moving frames.
Video
Slides

March 23, Eli Amzallag, City University of New York
Galois Groups of Differential Equations and Representing Algebraic Sets

Special time: 2:00-3:15 pm
The algebraic framework for capturing properties of solution sets of differential equations was formally introduced by Ritt and Kolchin. As a parallel to the classical Galois groups of polynomial equations, they devised the notion of a differential Galois group for a linear differential equation. Just as solvability of a polynomial equation by radicals is linked to the equation’s Galois group, so too is the ability to express the solution to a linear differential equation in ``closed form” linked to the equation’s differential Galois group. It is thus useful even outside of mathematics to be able to compute and represent these differential Galois groups, which can be realized as linear algebraic groups; indeed, many algorithms have been written for this purpose. The most general of these is Hrushovski’s algorithm and so its complexity is of great interest. A key step of the algorithm is the computation of a group called a proto-Galois group, which contains the differential Galois group. As a proto-Galois group is an algebraic set and there are various ways to represent an algebraic set, a natural matter to investigate in this regard is which representation(s) are expected to be the "smallest".
Some typical representations of algebraic sets are equations (that have the given algebraic set as their common solutions) and, for the corresponding ideal, Groebner bases or triangular sets. In computing any of these representations, it can be helpful to have a degree bound on the polynomials they will feature based on the given differential equation. Feng gave such a bound for a Groebner basis for a proto-Galois group’s ideal in terms of the size of the coefficient matrix. I will discuss how my joint work with Andrei Minchenko and Gleb Pogudin improved this bound by focusing on equations that define such a group instead of its corresponding ideal. This bound also produces a smaller degree bound for Groebner bases than the one Feng obtained. Recent work by M. Sun shows that Feng’s bound can also be improved by replacing Feng's uses of Groebner bases by triangular sets. Sun’s bound relies on my joint work with Pogudin, Sun, and Ngoc Thieu Vo on the complexity of triangular representations of algebraic sets, work that more generally suggests using triangular sets in place of Groebner bases to potentially reduce complexity. I will explain why this is the case.

April 20, André Platzer, Carnegie Mellon University
Differential Equation Axiomatization

Special time: 10:00-11:15am
We prove the completeness of an axiomatization for differential equation invariants, so all true invariants are provable. First, we show that the differential equation axioms in differential dynamic logic are complete for all algebraic invariants. Our proof exploits differential ghosts, which introduce additional variables that can be chosen to evolve freely along new differential equations. Cleverly chosen differential ghosts are the proof-theoretical counterpart of dark matter. They create new hypothetical state, whose relationship to the original state variables satisfies invariants that did not exist before. The reflection of these new invariants in the original system enables its analysis.
We then show that extending the axiomatization with existence and uniqueness axioms makes it complete for all local progress properties, and further extension with a real induction axiom makes it complete for all real arithmetic invariants. This yields a parsimonious axiomatization, which serves as the logical foundation for reasoning about invariants of differential equations. Moreover, our approach is purely axiomatic, and so the axiomatization is suitable for sound implementation in foundational theorem provers.
This talk is based on joint work with Yong Kiam Tan at LICS 2018.
Video
Slides

April 27, Boris Adamczewski, Université Lyon I
Mahler's method: old and new

Any algebraic (resp. linear) relation over the field of rational functions with algebraic coefficients between given analytic functions leads by specialization to an algebraic (resp. linear) relation over the field of algebraic numbers between the values of these functions at any algebraic point (where of course the functions are well-defined). Number theorists have long been interested in proving results going in the other direction. Though the converse result is known to be false in general, there are few known instances where it essentially holds true. In each case, an additional structure is required: the analytic functions under consideration do satisfy some kind of differential/difference equation. Mahler's method, which was initiated by Mahler at the end of 1920s, provides an instance of such a situation.
In this talk, I will discuss recent results by Philippon on the one hand, and by Faverjon and the speaker on the other hand which solve, partly or completely, some old problems of this theory. The discussion will include the case of Mahler's method in several variables, as well as applications related to automata theory.
Video

May 4, Dmitry A. Lyakhov, KAUST
Algorithmic Lie Symmetry Analysis and Group Classification for Ordinary Differential Equations

Sophus Lie proposed systematic method for solving nonlinear differential equations. Typically it leads to large system of overdetermined partial differential equations and relies on tools of differential algebra. We will show some recent advances in this field and raise open questions on algorithmic group classification.
Video
Slides

May 11, Amaury Pouly, Max Planck Institute, Saarbrücken
A truly universal polynomial differential equation

Lee A. Rubel proved in 1981 that there exists a universal fourth-order algebraic differential equation

P(y,y',y'',y''')=0 (1)

and provided an explicit example. It is universal in the sense that for any continuous function f from R to R and any continuous positive function ε from R to (0, +∞), there exists an infinitely smooth solution y to (1) such that |f(t)−y(t)|≤ε(t) for all real t. In other words, there is always a solution of (1) that is ε-close to f everywhere. However this result suffers from a big shortcoming, identified as an open question by Rubel in his paper: ``It is open whether we can require that the solution that approximates f be the unique solution for its initial data.'' Indeed, the solution to (1) is not unique when ones adds the condition that y(0)=y0 for example. In fact, one can add a finite number of such conditions and still not get uniqueness of the solution. This is not surprising because the construction of Rubel fundamentally relies on the non-uniqueness of the solution to work.
Our main result is to answer Rubel's question positively. More precisely, we show that there a polynomial P of degree k such that for any continuous function f from R to R and any continuous positive function ε from R to (0, +∞), there exist real y0, y'0, ..., y(k - 1)0 such that the unique analytic solution y to P(y,y',...,y(k))=0 and y(0)=y0, y'(0)=y'0,..., y(k−1)(0)=y(k−1)0 is such that |f(t)−y(t)|≤ε(t) for all real t. The major difference with Rubel's result is that we get unicity by requiring that the solution be analytic. This requires a completely different and more involved construction. A by-product of the proof is that y0 is constructive and in fact computable from f and ε.
Slides
Video

May 11, Julio R. Banga, Marine Research Institute, Vigo
Optimality principles and identification of dynamic models of biosystems

Special time: 2-3pm
Deterministic nonlinear ODEs are widely used in computational systems biology. The inverse problem of parameter estimation can be very challenging and has received great attention. Here, we will discuss a generalization of this problem which addresses the following question: given a dynamic model and observed time-series data, estimate the time-invariant model parameters, the unmeasured time-dependent inputs and the underlying optimality principle that is consistent with the measurements.
We will justify the use of optimality principles in this context, and we will present an inverse optimal control formulation that can be used to solve the above problem under some assumptions. We will also discuss associated identifiability issues, and how to surmount them in special cases. We will illustrate these ideas with examples of increasing complexity involving metabolic and signaling pathways.
Slides
Video

May 11, Hoon Hong, North Carolina State University
Deciding consistency of real polynomial constraints by prolongation and relaxation

Special time: 3-4pm
The combination of prolongation and relaxation is a fundamental technique for reducing a difficult problem to a larger but easier problem.
It has been successfully applied to checking the consistency of polynomial equations over complex numbers by Sylvester and Macaulay, reducing it to that of linear equations. It has been also successfully applied to differential equations by Kolchin, reducing it to that of polynomial equations.
In this talk, we share our on-going effort on applying the technique to polynomial equations/inequalities over real numbers, reducing it to that of linear equations/inequalities.
This is a joint work with Brittany Riggs.
Video