Research

Preprints

Solving the area-length systems in discrete gravity using homotopy continuation

(S. K. Asante, B.)

Area variables are intrinsic to connection formulations of general relativity, in contrast to the fun- damental length variables prevalent in metric formulations. Within 4D discrete gravity, particularly based on triangulations, the area-length system establishes a relationship between area variables associated with triangles and the edge length variables. This system is comprised of polynomial equations derived from Heron’s formula, which relates the area of a triangle to its edge lengths. 
Using tools from numerical algebraic geometry, we study the area-length systems. In particular, we show that given the ten triangular areas of a single 4-simplex, there could be up to 64 compatible sets of edge lengths. Moreover, we show that these 64 solutions do not, in general, admit formulae in terms of the areas by analyzing the Galois group, or monodromy group, of the problem. We show that by introducing additional symmetry constraints, it is possible to obtain such formulae for the edge lengths. We take the first steps toward applying our results within discrete quantum gravity, specifically for effective spin foam models. 

Lawrence Lifts, Matroids, and Maximum Likelihood Degrees

(B., A. Maraj)

We express the maximum likelihood (ML) degrees of a family toric varieties in termsof M¨obius invariants of matroids. The family of interest are those parametrized by monomial mapsgiven by Lawrence lifts of totally unimodular matrices with even circuits. Specifying these matricesto be vertex-edge incidence matrices of bipartite graphs gives the ML degrees of some hierarchicalmodels and three dimensional quasi-independence models. Included in this list are the no-three-wayinteraction models with one binary random variable, for which, we give closed formulae.

Quatroids and Rational Plane Cubics

(B., F. Gesmundo, A. Steiner)

It is a classical result that there are 12 (irreducible) rational cubic curves through 8 generic points in ℙ2ℂ, but little is known about the non-generic cases. The space of 8-point configurations is partitioned into strata depending on combinatorial objects we call quatroids, a higher-order version of representable matroids. We compute all 779777 quatroids on eight distinct points in the plane, which produces a full description of the stratification. For each stratum, we generate several invariants, including the number of rational cubics through a generic configuration. As a byproduct of our investigation, we obtain a collection of results regarding the base loci of pencils of cubics and positive certificates for non-rationality. 

Accepted/Published

Monodromy Coordinates

We introduce the concept of monodromy coordinates for representing solutions to large polynomial systems. Representing solutions this way provides a time-memory trade-off in a monodromy solving algorithm. We describe an algorithm, which interpolates the usual monodromy solving algorithm, for computing such a representation and analyze its space and time complexity.  

Max-Convolution through numerics and tropical geometry

(B., J. Hauenstein and C. Hills)
Numerical Algorithms

The maximum function, on vectors of real numbers, is not differentiable. Consequently, several differentiable approximations of this function are popular substitutes. We survey three smooth functions which approximate the maximum function and analyze their convergence rates. We interpret these functions through the lens of tropical geometry, where their performance differences are geometrically salient. As an application, we provide an algorithm which computes the max-convolution of two integer vectors in quasi-linear time. We show this algorithm's power in computing adjacent sums within a vector as well as computing service curves in a network analysis application.

The algebraic matroid of the Heron variety

(S. K. Asante, B., M. Hatzel)


We introduce the n-th Heron variety as the realization space of the (squared) volumes of faces of an n-simplex. Our primary goal is to understand the extent to which Heron's formula, which expresses the area of a triangle as a function of its three edge lengths, can be generalized. Such a formula for one face volume of an n-simplex in terms of other face volumes expresses a dependence in the algebraic matroid of the Heron variety. Whether the volume is expressible in terms of radicals is controlled by the monodromy groups of the coordinate projections of the Heron variety onto coordinates of bases. We discuss a suite of algorithms, some new, for determining these matroids and monodromy groups. We apply these algorithms toward the smaller Heron varieties, organize our findings, and interpret the results in the context of our original motivation. 

Polyhedral Geometry in OSCAR

(B., M. Joswig)

To appear as a chapter in the OSCAR book

OSCAR is an innovative new computer algebra system which combines and extends the power of its four cornerstone systems - GAP (group theory), Singular (algebra and algebraic geometry), Polymake (polyhedral geometry), and Antic (number theory). Here, we give an introduction to polyhedral geometry computations in OSCAR, as a chapter of the upcoming OSCAR book. In particular, we define polytopes, polyhedra, and polyhedral fans, and we give a brief overview about computing convex hulls and solving linear programs. Three detailed case studies are concerned with face numbers of random polytopes, constructions and properties of Gelfand-Tsetlin polytopes, and secondary polytopes. 

Enumerating chambers of hyperplane arrangements with symmetry

(B., H. Eble, L. Kuhne)

Discrete & Computational Geometry

We introduce a new algorithm for enumerating chambers of hyperplane arrangements which exploits their underlying symmetry groups. Our algorithm counts the chambers of an arrangement as a byproduct of computing its characteristic polynomial. We showcase ourjulia implementation, based on OSCAR, on examples coming from hyperplane arrangements with applications to physics and computer science.

Sparse trace tests

(T. Brysiewicz, M. Burr)

Mathematics of Computation (Accepted)

We establish how the coefficients of a sparse polynomial system influence the sum (or the trace) of its zeros. As an application, we develop numerical tests for verifying whether a set of solutions to a sparse system is complete. These algorithms extend the classical trace test in numerical algebraic geometry. Our results rely on both the analysis of the structure of sparse resultants as well as an extension of Esterov's results on monodromy groups of sparse systems. 

Likelihood degenerations

(D. Agostini, T. Brysiewicz, C. Fevola, L. Kuhne, B. Sturmfels, S. Telen)

Advances in Mathematics 451 (2022) 108863

Computing all critical points of a monomial on a very affine variety is a fundamental task in algebraic statistics, particle physics and other fields. The number of critical points is known as the maximum likelihood (ML) degree. When the variety is smooth, it coincides with the Euler characteristic. We introduce degeneration techniques that are inspired by the soft limits in CEGM theory, and we answer several questions raised in the physics literature. These pertain to bounded regions in discriminantal arrangements and to moduli spaces of point configurations. We present theory and practise, connecting complex geometry, tropical combinatorics, and numerical nonlinear algebra. 

Tangent Quadrics in Real 3-Space

(B., C. Fevola, B. Sturmfels)

Le Matematiche 76 (2021) 355-367

We examine quadratic surfaces in 3-space that are tangent to nine given figures. These figures can be points, lines, planes or quadrics. The numbers of tangent quadrics were determined by Hermann Schubert in 1879. We study the associated systems of polynomial equations, also in the space of complete quadrics, and we solve them using certified numerical methods. Our aim is to show that Schubert’s problems are fully real

Nodes on quintic spectrahedra

(B., K. Kozhasov, M. Kummer)

Le Matematiche 76 (2021) 415-430

We classify transversal quintic spectrahedra by the location of 20 nodes on the respective real determinantal surface of degree 5. We identify 65 classes of such surfaces and find an explicit representative in each of them.

Solving decomposable sparse systems

(B.,  J. Rodriguez, F. Sottile, and T. Yahl)

Brysiewicz, Taylor & Rodriguez, Jose & Sottile, Frank & Yahl, Thomas. (2021). Solving decomposable sparse systems. Numerical Algorithms. 10.1007/s11075-020-01045-x.

We present a recursive algorithm to solve decomposable sparse systems.

The degree of the Stiefel manifold

(B., F. Gesmundo)

The degree of Stiefel manifolds, ECA 1:3 (2021) Article S2R20.
We compute the degree of Stiefel manifolds, that is, the variety of orthonormal frames in a finite dimensional vector space. Our approach employs techniques from classical algebraic geometry, algebraic combinatorics, and classical invariant theory.

(B.)

Mathematics in Computer Science (2020)
We present an implementation in Macaulay2 of numerical software which computes the Newton polytope of a hypersurface given as the image of a map.We also describe how one can use this as a tropical membership test.

(B.)

J. Symb. Comput. (2019) https://doi.org/10.1016/j.jsc.2019.11.002
We count the number of polynomial parametrized osculants to a general analytic curve in the plane: as combinatorial necklaces. 

Supplementary Materials

(Brandt, Bruce, B., Krone, Robeva)

Combinatorial Algebraic Geometry, 207-224, Fields Inst. Commun. 80, Fields Inst. Res. Math. Sci., 2017.
We compute the degree of SO(n) as an algebraic variety in C^(n^2). We give a combinatorial description of this number as a non-intersecting lattice path count and we relate this degree with the complexity of a low-rank relaxation of semi-definite programming. 

Supplementary Materials

(Balay-Wilson, B.)

Rose-Hulman Undergraduate Mathematics Journal. Volume 15, No. 1, Spring 2014.
We give an explicit geometric condition for when, for a point on a cubic, there exists another cubic intersecting it exactly at that point (with multiplicity 9). 

Supplementary Materials

Dissertation

Newton polytopes and numerical algebraic geometry

We develop a collection of numerical algorithms which connect ideas from polyhedral geometry and algebraic geometry. The first algorithm we develop functions as a numerical oracle for the Newton polytope of a hypersurface and is based on ideas of Hauenstein and Sottile. Additionally, we construct a numerical tropical membership algorithm which uses the former algorithm as a subroutine. Based on recent results of Esterov, we give an algorithm which recursively solves a sparse polynomial system when the support of that system is either lacunary or triangular. Prior to explaining these results, we give necessary background on polytopes, algebraic geometry, monodromy groups of branched covers, and numerical algebraic geometry. 

Supplementary Materials