Dissertations, Theses, and Capstone Projects

Date of Degree

5-2019

Document Type

Dissertation

Degree Name

Ph.D.

Program

Mathematics

Advisor

Alexey Ovchinnikov

Committee Members

Richard Churchill

Vladimir Shpilrain

Subject Categories

Algebra | Algebraic Geometry | Ordinary Differential Equations and Applied Dynamics

Keywords

differential algebra, computational algebra, differential equations, Galois groups

Abstract

The differential Galois group is an analogue for a linear differential equation of the classical Galois group for a polynomial equation. An important application of the differential Galois group is that a linear differential equation can be solved by integrals, exponentials and algebraic functions if and only if the connected component of its differential Galois group is solvable. Computing the differential Galois groups would help us determine the existence of the solutions expressed in terms of elementary functions (integrals, exponentials and algebraic functions) and understand the algebraic relations among the solutions.

Hrushovski first proposed an algorithm for computing the differential Galois group of a general linear differential equation. Recently, Feng approached finding a complexity bound of the algorithm, which is the degree bound of the polynomials used in the first step of the algorithm for finding a proto-Galois group. The bound given by Feng is quintuply exponential in the order n of the differential equation. The complexity, in the worst case, of computing a Gröbner basis is doubly exponential in the number of variables. Feng chose to represent the radical of the ideal generated by the defining equations of a proto-Galois group by its Gröbner basis. Hence, a double-exponential degree bound for computing Gröbner bases was involved when Feng derived the complexity bound of computing a proto-Galois group.

Triangular decomposition provides an alternative method for representing the radical of an ideal. It represents the radical of an ideal by the triangular sets instead of its generators. The first step of Hrushovski's algorithm is to find a proto-Galois group which can be used further to find the differential Galois group. So it is important to analyze the complexity for finding a proto-Galois group. We represent the radical of the ideal generated by the defining equations of a proto-Galois group using the triangular sets instead of the generating sets. We apply Szántó's modified Wu-Ritt type decomposition algorithm and make use of the numerical bound for Szántó's algorithm to adapt to the complexity analysis of Hrushovski's algorithm. We present a triple exponential degree upper bound for finding a proto-Galois group in the first step of Hrushovski's algorithm.

Download

Share

COinS