Degree bound for toric envelope of a linear algebraic group
Preprint
Abstract
Algorithms working with linear algebraic groups often represent them via defining polynomial equations. One can always choose defining equations for an algebraic group to be of the degree at most the degree of the group as an algebraic variety. However, the degree of a linear algebraic group $G \subset \mathrm{GL}_n(C)$ can be arbitrarily large even for $n = 1$. One of the key ingredients of Hrushovski's algorithm for computing the Galois group of a linear differential equation was an idea to `approximate' every algebraic subgroup of $\mathrm{GL}_n(C)$ by a `similar' group so that the degree of the latter is bounded uniformly in $n$. Making this uniform bound computationally feasible is crucial for making the algorithm practical. In this paper, we derive a single-exponential degree bound for such an approximation (we call it toric envelope), which is qualitatively optimal. As an application, we improve the quintuply exponential bound for the first step of the Hrushovski's algorithm due to Feng to a single-exponential bound. For the cases $n = 2, 3$ often arising in practice, we further refine our general bound.
Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Hrushovski's algorithm for computing the Galois group of a linear differential equationAdvances in Applied Mathematics, 2015
- Around the numeric–symbolic computation of differential Galois groupsJournal of Symbolic Computation, 2007
- Galois Theory of Linear Differential Equations2003
- Effective equidimensional decomposition of affine varietiesJournal of Pure and Applied Algebra, 2002
- Computing Galois Groups of Completely Reducible Differential EquationsJournal of Symbolic Computation, 1999
- Computation of Invariants for Reductive GroupsAdvances in Mathematics, 1999
- Connected Linear Groups as Differential Galois GroupsJournal of Algebra, 1996
- Definability and fast quantifier elimination in algebraically closed fieldsTheoretical Computer Science, 1983
- Basic Theory of Algebraic Groups and Lie Algebras1981
- Representation theory of finite groups and associative algebrasUSSR Computational Mathematics and Mathematical Physics, 1964