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. 

 

Applied Macaulay2 tutorials

Preceding SIAM AG 2017 are 3-day tutorials on Macaulay2, a computer (nonlinear) algebra system.

image from Berlin poster“These tutorials are intended to appeal to participants with any level of prior M2 experience. The topics will range from the basic functionality of M2 to modeling problems in the M2 language to more specialized tutorials on algebraic statistics and numerical algebraic geometry. We will also reserve ample time for practice and Q&A sessions.”

Go here for more information.