Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


Degree bound for toric envelope of a linear algebraic group
HTML articles powered by AMS MathViewer

by Eli Amzallag, Andrei Minchenko and Gleb Pogudin HTML | PDF
Math. Comp. 91 (2022), 1501-1519 Request permission


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 degree at most the degree of the group as an algebraic variety. However, the degree of a linear algebraic group $G \subset \operatorname {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 $\operatorname {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 a toric envelope), which is qualitatively optimal. As an application, we improve the quintuply exponential bound due to Feng for the first step of Hrushovski’s algorithm to a single-exponential bound. For the cases $n = 2, 3$ often arising in practice, we further refine our general bound.

Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC (2020): 14Q20, 34M15, 14L17
  • Retrieve articles in all journals with MSC (2020): 14Q20, 34M15, 14L17
Additional Information
  • Eli Amzallag
  • Affiliation: Department of Mathematics, CUNY Graduate Center, 365 Fifth Avenue, New York 10016
  • Address at time of publication: Department of Mathematics, The City College of New York, New York 10031
  • MR Author ID: 1319513
  • Email:
  • Andrei Minchenko
  • Affiliation: Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz 1, 1019 Wein, Vienna, Austria
  • MR Author ID: 807995
  • Email:
  • Gleb Pogudin
  • Affiliation: Courant Institute of Mathematical Sciences, New York University, 251 Mercer St., New York 10012
  • Address at time of publication: LIX, CNRS, École Polytechnique, Institute Polytechnique de Paris, 91120 Palaiseau, France
  • MR Author ID: 948033
  • ORCID: 0000-0002-5731-8242
  • Email:
  • Received by editor(s): April 17, 2019
  • Received by editor(s) in revised form: August 19, 2021
  • Published electronically: October 28, 2021
  • Additional Notes: This work was partially supported by the NSF grants CCF-095259, CCF-1564132, CCF-1563942, DMS-1606334, DMS-1760448 by the NSA grant #H98230-15-1-0245, by CUNY CIRG #2248, by PSC-CUNY grants #69827-00 47, #60098-00 48, by the Austrian Science Fund FWF grants Y464-N18, P28079-N35
  • © Copyright 2021 American Mathematical Society
  • Journal: Math. Comp. 91 (2022), 1501-1519
  • MSC (2020): Primary 14Q20, 34M15, 14L17
  • DOI:
  • MathSciNet review: 4405504