Date of Degree


Document Type


Degree Name





Alexey Ovchinnikov

Committee Members

Vladimir Shpilrain

Benjamin Steinberg

Subject Categories

Algebra | Algebraic Geometry | Ordinary Differential Equations and Applied Dynamics


algebraic groups, Galois groups, differential equations, differential algebra, algebraic groups, computational algebra


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 radical 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 radical ideal in terms of the size of the coefficient matrix. We first discuss an improvement of this bound achieved 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 results on the complexity of triangular representations of algebraic sets, results that we shall present and that more generally suggest using triangular sets in place of Groebner bases to potentially reduce complexity.


A revised version was uploaded on November 5, 2018 with the approval of the dissertation committee chair and the Graduate Center.