Title: Degree bound for toric envelope of a linear algebraic group,
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.