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

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.

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

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

Video

Reference: F. L. Pritchard and W. Sit,

Slides

Video

Slides

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.

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

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

Video

Slides

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 y

Slides

Video

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

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