Stillman’s conjecture and Gröbner bases

Start with linear forms f_1,\dots,f_k in infinitely many variables \{x_i\mid i>0\}. Fix the monomial order to be the graded reverse lexicographic (with x_1>x_2>\cdots). Then the reduced Gröbner basis (GB) for the input sequence f is equivalent to the row-reduced echelon form (RREF) of the k \times \infty matrix of the coefficients of f.

Suppose one makes a generic linear change of variables prior to computing GB (RREF). Then the dimension r of the subspace spanned by f determines the leading monomials of the GB (pivots in the RREF): \{x_1,\dots,x_r\}. Note that there is a finite number of outcomes as r  is at most k.

In full analogy to the above, stepping into the nonlinear land, [DLL] establishes that there is a finite number of generic initial ideals (gins) for the ideal \langle f_1,\dots,f_k \rangle for the homogeneous generators of fixed arbitrary degrees d_1,\dots,d_k (the linear case is d_1=\dots=d_k=1). Moreover, this remains true beyond polynomials: f may come from a big ring of formal power series of bounded degree.

The finiteness of the set of gins implies yet another proof of Stillman’s conjecture:

The projective dimension of an ideal generated by homogeneous forms of fixed degrees but in an arbitrary number of variables and in arbitrary characteristic is uniformly bounded.

Notably, unlike in the linear case, the characteristic of the field of coefficients may make a difference for the outcome (i.e., the set of possible gins). However, the union of these over all characteristics is still finite!

The following articles (listed chronologically) contain proofs of Stillman’s conjecture.

[AH]  Ananyan, Hochster. “Small subalgebras of polynomial rings and Stillman’s conjecture.”

[ESS]  Erman, Snowden, Sam. “Big polynomial rings and Stillman’s conjecture.”

[DLL]  Draisma, Lasoń, Leykin. “Stillman’s conjecture via generic initial ideals.”

IMG_20180328_075335-EFFECTS
Spring at Institut Mittag-Leffler

In principle, it is possible to use the bounds on the projective dimension given in [AH] for an effective approach to find all gins. One can also implement the algorithm of [DLL] on a computer. While the latter may seem more efficient than the former, neither approach may lead to computational results that surpass those obtained in special cases by humans.

(Disclaimer: the last statement represents the author’s opinion of the capabilities of humans and machines at the moment of writing.)

 

Advertisements

Littlewood-Richardson Homotopy

This work took (from the original idea to an implemented algorithm) about 20 years to complete!

22b-eps-converted-to-1

Start by playing Ravi Vakil’s checkerboard games to understand the geometric Littlewood-Richardson rule. Track involved cascades of homotopies on checkerboard varieties corresponding to one of the 10 moves like the one depicted and find solutions (i.e, find approximate numerical solutions explicitly!) to any instance of any Schubert problem on any Grassmannian.

 

 

Beyond polyhedral homotopies

We forgot to post this here in the beginning of the summer… The paper outlines a very general framework for (an) algorithm(s) waiting to be implemented.

trop-two-circles

Beyond polyhedral homotopies
(Anton Leykin and  Josephine Yu)

Abstract: We present a new algorithmic framework which utilizes tropical geometry and homotopy continuation for solving systems of polynomial equations where some of the polynomials are generic elements in linear subspaces of the polynomial ring. This approach generalizes the polyhedral homotopies by Huber and Sturmfels. 

 

MonodromySolver

Last month the latest stable version (1.10) of Macaulay2 was released. This includes the first stable version of the package MonodromySolver, developed by some of us at Georgia Tech (Anton, Cvetelina, Kisun, Tim), as well as our collaborators Jeff Sommars and Anders Jensen. The corresponding paper has been on the arXiv for about a year.

People in algebraic geometry have used monodromy groups for a long time—in particular, use of monodromy group to solve polynomial systems has appeared elsewhere recently (see here, and here) and is certainly implicit in earlier algorithms. In fact, the possible variations on this idea seem limitless. Our implementation allows one to compare various approaches and unifies them in a general framework.

The package currently works best for the following problem: we are given a family of square polynomial systems (F_p )_{p \in B} in n variables over the complex numbers, where the parameter space B is a finite-dimensional affine space, such that, for a Zariski open subset of z \in \mathbb{C}^n, there exists p \in B such that F_p(z) =0. However, the various methods are modular enough to incorporate them into solving more general systems—see here for a great example. Understanding what users want in more general settings will help us improve the package in the future, so try it out and let us know what you think!

New paper: Toric h-vectors and Chow Betti Numbers of Dual Hypersimplices

Toric h-vectors and Chow Betti Numbers of Dual Hypersimplices
by Charles Wang and Josephine Yu

Abstract: The toric h-numbers of a dual hypersimplex and the Chow Betti numbers of the normal fan of a hypersimplex are the ranks of intersection cohomology and Chow cohomology respectively of the torus orbit closure of a generic point in the Grassmannian. We give explicit formulas for these numbers. We also show that similar formulas hold for the coordinator numbers of type A^* lattices.

http://front.math.ucdavis.edu/1707.04581