Algebraic and Geometric Computations in OSCAR

OSCAR (Open Source Computer Algebra Research) is a new open-source computer algebra system that is written in the Julia programming language [6]. Wolfram Decker, Claus Fieker, Max Horn, and Michael Joswig currently lead this collaborative project, which has many contributors; its ongoing development can be monitored on GitHub. OSCAR is funded by the German Research Foundation within the collaborative research center on “Symbolic Tools in Mathematics and their Application.”

One of OSCAR’s most important features is its ease of installation, which is a direct consequence of its inclusion within the rapidly growing Julia ecosystem as a registered package. On the Julia interactive command line, users can simply type

import Pkg; Pkg.add(“Oscar”); using Oscar

to download the relevant data from the internet and print a banner; OSCAR is then ready for action. This works on every operating system (Linux, macOS, and Windows), though one should nevertheless budget sufficient time for the initial installation.

OSCAR rests on the combined functionality of the GAP (group and representation theory), Nemo/Hecke (number theory), polymake (polyhedral and tropical geometry), and Singular (commutative algebra and algebraic geometry) packages but extends them considerably. The user interface is inspired by Donald Knuth’s “literate programming” paradigm [10]; it should be as close to standard textbooks as possible. In contrast to Magma, OSCAR is an accessible platform for interoperable and reproducible computations due to its open-source nature. And compared to SageMath, it is smaller but more tightly knit. As a result, some computations that are possible in OSCAR are not currently achievable elsewhere — at least not in other open-source software; the computation of Galois groups of arbitrarily high degree is one such example [7]. To provide a more precise idea of OSCAR’s present capabilities, we will discuss specific computations that have arisen in four Ph.D. projects. The associated code examples are available as Jupyter notebooks that require OSCAR v0.12.0 or a later version.

Parametric Volume of Polytope Slices

Polytopes and convex bodies are geometric objects that occur naturally as feasible domains in linear and convex programming, and volume computations have been the subject of wide interest and application since the early days of mathematics in ancient Egypt. These two distinct concepts converge in the study of intersection bodies, which arose in convex geometry settings to help solve the famous Busemann-Petty problem [8]. This question investigated whether a symmetric convex body with larger central hyperplane sections must similarly have a larger volume. Intersection bodies also appear in open problems such as Bourgain’s slicing conjecture [9]. Our example Jupyter notebook presents an experimental approach to these problems by computing explicit instances of intersection bodies. The methods exploit the fact that intersection bodies of polytopes are semi-algebraic — i.e., describable in terms of polynomial inequalities.

The crucial step is a parametric volume computation [4] that requires methods from polyhedral geometry and commutative algebra, all of which exist in OSCAR. The algorithm in our notebook takes a polytope \(P\) as input; we are interested in slicing \(P\) with arbitrary central hyperplanes. The slice volume function is actually a piecewise quotient of two polynomials, and the algorithm’s output is its explicit computation. Our method involves triangulating \(P\)—a standard task in polyhedral geometry—and subsequently adding determinants of matrices whose entries are multivariate rational functions; doing so requires basic linear algebra and an efficient implementation of arithmetic operations in polynomial rings. For conciseness, the notebook demonstrates the computation for one specific polytope: the truncated tetrahedron, which is an Archimedean solid (see Figure 1).

Combinatorics of Hurwitz Numbers

In this project, we tackle a problem from enumerative algebraic geometry in both a combinatorial and algorithmic manner. Hurwitz numbers of degree \(d\) and genus \(g\) count the number of degree \(d\) covers of the complex projective line by algebraic curves of genus \(g\). This tally does not distinguish isomorphic covers, which can be described combinatorially in terms of behavior around the branch points. Such a monodromy representation is encoded as a list of permutations, with one permutation for each branch point. Plane Hurwitz numbers only count covers that arise via projections. For example, we have explicitly computed the Hurwitz and plane Hurwitz numbers of degree 3 and genus 1, as well as degree 4 and genus 3 (with simple ramification), then analyzed their structures [1].

We constructed the 7,528,620 (representatives of) monodromy representations (out of a total of 2,176,782,336 candidate lists of permutations) that exist for degree 4. This part of the computation is purely topological and only exploits the structure of the Riemann surface that underlies a complex algebraic curve. Furthermore, all of the computed monodromy representations can be combinatorially analyzed for the geometric and algebraic properties of the covers that they symbolize. While each individual computation is neither hard nor time-consuming, their sheer collective volume makes analysis impossible without the aid of a computer algebra system. Fortunately, the fact that OSCAR is written in Julia simplifies the processing of the output of HomotopyContinuation.jl [5]: a system that solves polynomial equations via analytic methods that can compute the monodromy representation of a given cover.

Cox Rings of Point Blow-ups

To fully understand the geometry of varieties, one must describe their algebraic invariants. An example of this concept is the Cox ring of a projective algebraic variety. This universal homogeneous coordinate ring algebraically encodes all possible embeddings of the given variety into projective space. We recently solved a formerly open question by demonstrating that quadrics generate the ideal \(I\) of relations of the Cox ring of the blow-up of seven points in three-dimensional complex projective space [3]. The primary result relies on an OSCAR computation in an essential way. This scenario is interesting because only a few Cox rings of such blow-ups are finitely generated, and the scenario in question had been one of only two remaining cases that researchers did not completely comprehend.

One can compute a Gröbner basis to show that quadrics generate the relevant ideal \(I\). Yet \(I\) is given indirectly as the radical of another ideal \(J\), which has 4,220 quadric generators in 129 variables. Since this problem is far too large for a direct computation with current methods, we seek to study the Cox ring as a subalgebra that is spanned by 129 generators in a polynomial ring with only 14 variables. Our proof computes a Khovanskii basis of the Cox ring, which is an analog of a Gröbner basis for a subalgebra (rather than an ideal). Because Khovanskii bases are generally not finite, this task is more subtle. Luckily, OSCAR was able to find a finite Khovanskii basis. Our example Jupyter notebook illustrates the analogous computation for the blow-up of six points.

Cox Rings of Linear Quotients

A linear quotient is the orbit space of a finite group that acts linearly on a finite-dimensional complex vector space. Such objects are the subject of invariant theory — a field of mathematics that dates back at least 150 years and lies at the intersection of group theory, representation theory, and algebraic geometry. Invariant theory in particular pertains to the study of polynomials that remain invariant under the linear action of a group on a polynomial ring; the set of these invariant polynomials forms its own invariant ring.

Classical results of David Hilbert and Emmy Noether imply that a linear quotient is an affine algebraic variety. Our example notebook for this project again relates to the Cox ring of this variety. Here, we must compute a certain invariant ring and endow it with a nonstandard grading by a theorem of Ivan Arzhantsev and Sergey Gaĭfullin [2]. Computation of this ring facilitates the study of the birational geometry of a linear quotient [11]. OSCAR provides all of the necessary tools for the effective management of matrix groups and their invariant theory.

References

[1] Agostini, A., Markwig, H., Nollau, C., Schleis, V., Sendra-Arranz, J., & Sturmfels, B. (2022). Recovery of plane curves from branch points. Preprint, arXiv:2205.11287.
[2] Arzhantsev, I.V., & Gaĭfullin, S.A. (2010). Cox rings, semigroups and automorphisms of affine varieties. Math. Sbornik, 201(1), 3-24.
[3] Belotti, M., & Panizzut, M. (2022). Discrete geometry of Cox rings of blow-ups of \(\mathbb{P}^3\). Preprint, arXiv:2208.05258.
[4] Berlow, K., Brandenburg, M.-C., Meroni, C., & Shankar, I. (2022). Intersection bodies of polytopes. Beitr. Algebra Geom., 63, 419-439.
[5] Breiding, P., & Timme, S. (2018). HomotopyContinuation.jl: A package for homotopy continuation in Julia. In Mathematical software – ICMS 2018 (pp. 458-465). South Bend, IN: Springer International Publishing.
[6] Decker, W., Eder, C., Fieker, C., Horn, M., & Joswig, M. (Eds.). (2024). The OSCAR book. To be published.
[7] Fieker, C., Hofmann, T., & Joswig, M. (2022). Computing Galois groups of Ehrhart polynomials in OSCAR. Sém. Lothar. Combin., 86B, 87.
[8] Gardner, R.J., Koldobsky, A., & Schlumprecht, T. (1999). An analytic solution to the Busemann-Petty problem on sections of convex bodies. Ann. Math., 149(2), 691-703.
[9] Klartag, B., & Milman, V. (2022). The slicing problem by Bourgain. In A. Avila, M.T. Rassias, & Y. Sinai (Eds.), Analysis at large: Dedicated to the life and work of Jean Bourgain (pp. 203-231). Cham, Switzerland: Springer Cham.
[10] Knuth, D.E. (1984). Literate programming. Comp. J., 27(2), 97-111.
[11] Schmitt, J. (2023). On \(\mathbb{Q}\)-factorial terminalizations of symplectic linear quotient singularities [Doctoral thesis, Department of Mathematics, University of Kaiserslautern-Landau].