On the Complexity of Computing Galois Groups of Differential Equations

<p>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.</p> <p>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.</p> <p>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.</p>

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

Doctoral

Discipline thesis:degree_discipline

Mathematics

Grantor

The Graduate School and University Center of The City University of New York

Year dc:date.available

2019

Author dc:creator

• Sun, Mengxiao

Advisor dc:contributor.advisor

• Alexey Ovchinnikov

Committee members dc:contributor.committeemember

• Richard Churchill
• Vladimir Shpilrain

• Algebra
• Algebraic Geometry
• Ordinary Differential Equations and Applied Dynamics
• differential algebra
• computational algebra
• differential equations
• Galois groups

Repository record dc:identifier

https://academicworks.cuny.edu/gc_etds/3217

OAI identifier oai:identifier

oai:academicworks.cuny.edu:gc_etds-4338