Stillman's conjecture via generic initial ideals
Jan Draisma Michal Lason Anton Leykin







[Jan Draisma]Mathematical Institute, University of
Bern,
Sidlerstrasse 5, 3012 Bern, Switzerland; and Eindhoven
University of Technology, The Netherlands
JD is partially supported by a Vici grant from the
Netherlands Organisation for Scientific Research (NWO)
jan.draisma@math.unibe.ch

[Michał Lasoń]Mathematical Institute,
University of Bern, Sidlerstrasse 5, 3012 Bern,
Switzerland; Institute of Mathematics of the Polish Academy of Sciences, ul.Śniadeckich 8, 00-656 Warszawa, Poland 
michalason@gmail.com

[Anton Leykin]School of Mathematics, 
Georgia Institute of Technology, Atlanta, GA 30332-0160,
USA
leykin@math.gatech.edu
Research of AL is supported in part by DMS-1719968 award from NSF


Using recent work by Erman-Sam-Snowden, we show that finitely generated
ideals in the ring of bounded-degree formal power series in
infinitely many variables have finitely
generated Gröbner bases relative to the graded reverse lexicographic
order. We then combine this result with the first author's work on
topological Noetherianity of polynomial functors to give an algorithmic
proof of the following statement: ideals in polynomial rings generated
by a fixed number of homogeneous polynomials of fixed degrees only
have a finite number of possible generic initial ideals, independently
of the number of variables that they involve and independently of the
characteristic of the ground field. 
Our algorithm outputs not only a finite list of possible generic initial ideals, 
but also finite descriptions of the corresponding strata in
the space of coefficients.


Stillman's conjecture via generic initial ideals
    Jan Draisma and Michał Lasoń and Anton Leykin
    December 30, 2023
=================================================





§ INTRODUCTION




 §.§ Grevlex series and Gröbner bases


Let A be a ring and let R_A be the A-algebra of formal power
series over A of bounded degree in the infinitely many variables
x_1,x_2,…. In other words, each element of R_A is a formal
infinite sum

    ∑_α∈^, |α| ≤ d c_α x^α
 
where d is some nonnegative integer and c_α∈ A for each
sequence α=(α_1,α_2,…) of nonnegative integers whose
sum |α| is (finite and) at most d. Addition and multiplication
are as usual. 

We equip the polynomial ring R_A with the graded reverse lexicographic order
grevlex, in which x^α > x^β if either |α|>|β|
or |α|=|β| and the last non-zero entry of α-β
is negative. So, for instance, the monomials of degree 3 are ordered
as follows:

    x_1^3>x_1^2x_2>x_1x_2^2>x_2^3>x_1^2x_3>x_1x_2x_3>x_2^2x_3>
    x_1x_3^2>x_2x_3^2>x_3^3>x_1^2x_4>…

To remind the reader that this is the only monomial order considered
in this paper, we call the elements of R_A grevlex series over
A. If f is a nonzero element of R, then (f) denotes the
largest monomial that has a nonzero coefficient in f,
(f) denotes that coefficient, and
(f)=(f)(f) is the leading term. The ring R_A
carries a unique topology in which a basis of open neighborhoods of
f ∈ R_A is given by all sets {g ∈ R_A |(f-g)
< x^α} as α varies.

Let L be a field. A Gröbner basis of an ideal I ⊆
R_L is a subset B ⊆ I such that for each h ∈ L there
exists an f ∈ B with (f)|(h). We do not require that B
be finite. As in the classical setting, a Gröbner basis B of I
generates I as an ideal (Lemma <ref>). Our first main
result is the following.

 
For every field L, every finitely generated homogeneous ideal in
the ring R_L has a finite Gröbner basis with respect to grevlex.


The analogous statement certainly does not hold for all monomial
orders: in <cit.> it is shown that the
ideal generated by a generic quadric and a generic cubic has a
non-finitely generated initial ideal relative to the lexicographic
order.  Theorem <ref> implies a positive answer to
<cit.>; in that paper a positive answer
is given in the case where the ideal is generated by series 
∑_|α|=d_i c_i,α x^α, i=1,…,k whose
coefficients (c_i,α)_i ∈ [k],|α|=d_i are algebraically
independent over the prime field of L.

The natural question arises whether a Gröbner basis as in the
theorem can be computed in finite time. A straightforward variant SeriesBuchberger of Buchberger's algorithm shows that this would,
indeed, be the case—if only we could work effectively with
infinite series.

Next we focus on the following setting where we can indeed work with such
series. Let =⋃_n be the union of all symmetric groups,
and let  be the subgroup of all permutations fixing 1,…,n
elementwise. Suppose that we are given an action of S_>n_0
on A by means of ring automorphisms, and let S_>n_0
act on the variables x_1,x_2,… via π x_i=x_π(i). This
action extends to an action of S_>n_0 by (continuous)
ring automorphisms on R_A via

    π(∑_α c_α x^α) = π(∑_α c_α∏_i x^α_i_i )=∑_απ(c_α) ∏_i x^α_i_π(i) = ∑_απ(c_α)
    x^α∘π^-1.

We call an f ∈ R_A eventually invariant if there exists an
n ≥ n_0 such that π(f)=f for all π∈. To specify
an eventually invariant grevlex series we need only a finite number of
coefficients: if f is invariant under  and has degree d, then
 has only finitely many orbits on monomials in x_1,x_2,…
of degree at most d—the grevlex-largest element in each orbit
is of the form x^α where α(n+1) ≥α(n+2) ≥…. Then f is uniquely determined by its coefficients on these
grevlex-largest representatives x^α_1,…,x^α_s.
We call f̂:=∑_i=1^s c_α_i x^α_i the n-representation of f=∑_α c_α x^α.
Often we will suppress n from this notation. 

 
Suppose that A=L is a field.  There exist a finite algorithm that on
input a finite list f̂_1,…,f̂_k of representations
of eventually invariant grevlex series f_1,…,f_k outputs a
finite list ĝ_1,…,ĝ_l representing an eventually
invariant Gröbner basis g_1,…,g_l of ⟨ f_1,…,f_k
⟩_R_L.




 §.§ Stillman's conjecture


The condition of eventual invariance seems rather restrictive, but it
is tailored to a proof of the following theorem.

 
There exists a finite algorithm that on input k ∈ and
d_1,…,d_k ∈ outputs a finite sequence S_1,…,S_t,
each S_i a finite set of monomials in the x_j, such that the
following holds: For every infinite field K, all n ∈, and
all homogeneous polynomials f_1,…,f_k ∈ K[x_1,…,x_n]
of degrees d_1,…,d_k, respectively, the generic grevlex initial
ideal of ⟨ f_1,…,f_k ⟩_K[x_1,…,x_n] equals
⟨ S_i ⟩_K[x_1,…,x_n] for some i.


In short: ideals in polynomial rings generated by homogeneous
polynomials of degrees d_1,…,d_k have only finitely many possible
generic grevlex initial ideals, independently of the number of variables.
Via <cit.>, which is based on <cit.>,
this implies that 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. This is Stillman's
conjecture from the title; see <cit.>.

This is the fourth proof of Stillman's conjecture, after the
first proof by Ananyan-Hochster <cit.> and two recent
proofs by Erman-Sam-Snowden <cit.>. Our proof is the same
in spirit as the second proof in the latter paper in that it uses
Draisma's theorem on topological Noetherianity of polynomial functors
<cit.>. However, unlike the second proof in <cit.>
(but like the first proof there, and like Ananyan-Hochster's proof), our
theorem yields S_1,…,S_t that are valid in all characteristics.
Also, our theorem is constructive in the sense that we give an algorithm
for computing the possible initial ideals and the corresponding strata
given by equations and disequations for field characteristics and
coefficients of the input series.  All these are represented finitely.

In <cit.> the authors raise the question whether a version over
 of Draisma's theorem holds, as this would also make their second
proof characteristic-inde­pen­dent. We do not settle this question. Instead,
the algorithm of Theorem <ref> simulates a generic ideal
computation in all characteristics, branching along constructible
subsets of  whenever necessary. We argue that, if there were
an infinite branch in this computation, then this branch would also
be infinite over some field; and that this would contradict Draisma's
theorem over that field.

In <cit.> (see also <cit.>), using
Stillman's conjecture and Draisma's theorem, the same authors establish
a generalization of Stillman's conjecture to ideal invariants that
are upper semicontinuous in flat families and preserved under adding a
variable to the polynomial ring. We have not pursued the question to
what extent (an algorithmic version of) this generalisation also follows from our
Theorem <ref>. 



 §.§ Organization


This paper is organized as follows. In Section <ref> we
prove Theorem <ref> using work from <cit.>. In
Section <ref> we use this existence result to prove
that a version of Buchberger's algorithm for eventually invariant
series terminates; this yields Theorem <ref>. In
Section <ref> we review topological Noetherianity of a
specific polynomial functor, which follows from <cit.>. Finally,
in Section <ref> we derive Theorem <ref> from
Theorem <ref> and Draisma's theorem.



§ THE EXISTENCE OF FINITE GRÖBNER BASES



We will use two results from <cit.>, the first of which is the following.

 
If L is perfect, then R_L contains an (uncountable) set of homogeneous
elements {g_j:j ∈ J} such that the unique L-algebra homomorphism
L[(x_j)_j ∈ J] → R_L sending x_j to g_j is an L-algebra
isomorphism.


For each n ∈ we write R_L^(n):=L[x_1,…,x_n]. There is
a natural L-algebra homomorphism R_L → R_L^(n), f ↦ f^(n)
that retains only the terms involving only the variables x_1,…,x_n.
We may think of a degree-at-most-d element of R_L as a sequence
(f^(0),f^(1),…) in which each f^(n) is a polynomial in
R_L^(n) of degree at most d such that f^(n) is the image of
f^(n+1) under discarding all terms divisible by x_n+1. Conversely,
R_L^(n) is an L-subalgebra of R_L.  Observe that, for any f
∈ R_L and n ∈, the image ((f))^(n) is either zero
or equal to (f^(n)) in the grevlex order on L[x_1,…,x_n].


A sequence g_1,…,g_l ∈ R_L of homogeneous elements is a
regular sequence in R_L if and only if g_1^(n),…,g_l^(n)
is a regular sequence in R_L^(n) for all n ≫ 0.


The following lemma is straightforward from <cit.>, but we
include its proof using the two results above.

 
Let f_1,…,f_k ∈ R_L. Then the natural map between
first syzygies 

    _R_L^(n+1)(f_1^(n+1),…,f_k^(n+1)) →_R_L^(n)(f_1^(n),…,f_k^(n))

is surjective for all n ≫ 0.



This surjectivity is not affected by enlarging the field, so we
may assume that L is perfect. By Theorem <ref>,
there exist homogeneous
g_1,…,g_l ∈ R_L such that f_1,…,f_k ∈ L[g_1,…,g_l]
and such that g_1,…,g_l are part of a system of variables
for the polynomial ring R_L. In particular, they are a regular
sequence in R_L, and hence by Theorem <ref> the polynomials
g_1^(n),…,g_l^(n) are a regular sequence in R_L^(n)
for n ≫ 0. We draw two conclusions from this. First, for n ≫
0, g_1^(n),…,g_l^(n) are algebraically independent over
L, f_1^(n),…,f_k^(n) are elements of the polynomial
ring A^(n):=L[g_1^(n),…,g_l^(n)], and 

    _A^(n+1)(f_1^(n+1),…,f_k^(n+1)) 
    →_A^(n)(f_1^(n),…,f_k^(n))

is a bijection. Second, still for n ≫ 0, R^(n) is a
free module over A^(n). Therefore,
_A^(n)(f_1^(n),…,f_k^(n)) ⊆
(A^(n))^k generates
_R^(n)(f_1^(n),…,f_k^(n)) ⊆
(R^(n))^k as an
R^(n)-module. Combining these two statements we find the
surjectivity claimed in the lemma.



Let f_1,…,f_k ∈ R_L be nonzero, homogeneous, and let
n ∈. Set I:=⟨ f_1,…,f_k ⟩⊆
R_L.  Consider a monomial u ∈(I) ∩ R^(n+1) divisible by
x_n+1. There exist homogeneous a_1,…,a_k ∈ R^(n) with
(a_i)=(u)-(f_i) and homogeneous b_1,…,b_k ∈
R^(n+1) with (b_i)=deg(u)-deg(f_i)-1 such that

    u = ((a_1+b_1 x_n+1)f_1^(n+1) + ⋯ + (a_k +
    b_k x_n+1)f_k^(n+1)).

Now (a_1,…,a_k)∈_R^(n)
(f_1^(n),…,f_k^(n))—otherwise, the right-hand side would equal
(∑_i a_i f_i^(n)), which is not divisible by x_n+1. By
Lemma <ref>, if n ≫ 0, the syzygy (a_1,…,a_k) can
be lifted to a syzygy (c_1,…,c_k) ∈_R^(n+1)_L(f^(n+1)_1,…,f^(n+1)_k).  Write c_i=a_i
+ x_n+1 b'_i for each i.  Then

    u = ((b_1-b'_1)x_n+1f_1^(n+1) + ⋯ +
    (b_k-b'_k)x_n+1f^(n+1)),

but then we see that u/x_n+1∈(I). Hence for n ≫ 0,
(I) does not contain minimal generators divisible by x_n+1. It
follows that for such an n, (I) is generated by any finite
generating list m_1,…,m_t of (I^(n)). Now h_1,…,h_t
∈ I such that (h_i)=m_i form a Gröbner basis of I.






§ BUCHBERGER'S ALGORITHM FOR GREVLEX SERIES


To turn Theorem <ref> into an algorithm, we
derive a version of Buchberger's algorithm.

[Division with remainder] 
Let f_1,…,f_k ∈ R_L be monic and h ∈ R_L. Then there
exist q_1,…,q_k ∈ R_L such that (q_i f_i) ≤(h)
for all i and such that no term of the remainder h-∑_i q_i f_i
is divisible by any (f_i).


In particular, if f_1,…,f_k is a Gröbner basis of the ideal
that they generate, then the remainder must be zero.


Initialize r:=h and q_i:=0 for all i. While some term of r
is divisible by some (f_i), pick the grevlex-largest such term
c x^α in r, subtract c (x^α/(f_i)) f_i from r
and add c x^α/(f_i) to q_i. This does not change terms in
q_i larger than the term just added, and hence in the product topology
on R_L^k the vector q converges a solution vector q as desired.





 
Assuming an implementation for addition, multiplication, and
division with remainder of grevlex series, SeriesBuchberger on
page alg:SeriesBuchberger terminates after a finite number of
steps and outputs a Gröbner basis of the ideal generated by the series
in the input.



Fix any natural number n.  The loops with m ranging from
1 to n really compute a Gröbner basis for I:=⟨
f_1^(n),…,f_k^(n)⟩ while dragging the tails of the
series along. In particular, these n loops terminate.  If an element
is added to the queue Q in the (n+1)st run of the loop, then this
implies that (I) ∩ R_L^(n) does not generate (I). By
Theorem <ref>, this cannot happen infinitely often, so the
algorithm terminates. That the output is, indeed, a Gröbner basis,
follows from the ordinary Buchberger criterion.




§ BUCHBERGER'S ALGORITHM FOR EVENTUALLY INVARIANT
SERIES
 

Recall that S_>n_0 acts on L, on variables, and on
R_L. Given representations f̂_1,…,f̂_k of eventually
invariant f_1,…,f_k ∈ R_L, we want to compute the representation
of an eventually invariant Gröbner basis of I:=⟨ f_1,…,f_k
⟩.

The first ingredient in our variant of Buchberger's algorithm is an
analogue of Lemma <ref>.

[Division with remainder on representations.] 
Let f_1,…,f_k ∈ R_L be monic and h ∈ R_L. Assume that
h,f_1,…,f_k,(f_1),…,(f_k) are invariant under
.  Then q_1,…,q_k and r from Lemma <ref>
can be chosen -invariant, and the representations
q̂_1,…,q̂_k,r̂ can be effectively computed from
ĥ,f̂_1,…,f̂_r.



Set r:=h. While some term of r is divisible by some (f_i),
pick the grevlex-largest such term c x^α in r, let
x^α_1,x^α_2,… be the (countably infinite) orbit of
x^α under  and for each i let c_i be the coefficient of
x^α_i in r. Since r is -invariant, so is a:=∑_i
c_i x^α_i.  Moreover, as (f_i) is -invariant,
a is divisible by (f_i). Replace r by r-(a/(f_i))f_i
and q_i by q_i+(a/(f_i)); each of these are -invariant.
This does not effect the terms of r larger than x^α and gets
rid of this particular term. In this process, r and the q_i remain
-invariant and converge to series as in Lemma <ref>.

For effectiveness, we need to be able to compute the representation
of r-(a/(f_i))f_i from r̂,â=c x^α, and
f̂_i. The representation depends linearly on the series, so
it suffices to have a procedure for computing the representation of
a product. The function Product does just that—it uses that
no monomial of degree e that is grevlex-maximal in its -orbit
contains any of the variables x_n+e+1,x_n+e+2,….







The next ingredient is S-series: if f,g are monic
-invariant series whose leading monomials are also
-invariant, and x^γ=((f),(g)), then we
set S(f,g):=(x^γ/(f))f-(x^γ/(g))g.  We note
that S(f,g) is also -invariant, and the n-representation of
S(f,g) can be computed from the n-representations f̂,ĝ,
as follows.



From the n-representation f̂=∑_i=1^s c_α_i
x^α_i of an -invariant grevlex series one can
compute the m-representation f̃ with m>n as follows. For each
i=1,…,s, the group S_>m has only finitely many
orbits on x^α_i. Let
x^β_i1,…,x^β_is_i
be the grevlex-maximal representatives of these orbits, and let
π_i1,…,π_is_i∈S_>m be such that
π_ij x^α_i=x^β_ij. Then define

    f̃:=∑_i=1^s ∑_j=1^s_iπ_ij(c_α_i) x^β_ij.

We call f̃ the m-expansion of f̂. So we may
freely increase n when desirable; we will use this to ensure that the
leading monomial of f is -invariant.





The algorithm SymmetricBuchberger above called with arguments
(n,f̂_̂1̂,…,f̂_̂k̂) performs the same operations as the
algorithm SeriesBuchberger on page alg:SeriesBuchberger on
input (f_1,…,f_k), except that it works with finite data structures
capturing the series f_i. Hence Proposition <ref>
implies both the termination and the fact that the output
of SymmetricBuchberger is the representation of a Gröbner basis of
⟨ f_1,…,f_k ⟩.



Should one consider implementing SymmetricBuchberger, it may be
practical to allow series to have m-representations with varying values
of m, as opposed to the uniform m for every iteration of the outer
loop above.

In order to perform binary operations, i.e., additions and
multiplications, representations would then need to be expanded to a
matching value of m. Furthermore, to ensure termination, the order
of S-pairs needs to ensure that each leading monomial is eventually
encountered. In SymmetricBuchberger, this is done by increasing
m only after all the leading monomials in x_1,…,x_m have been
collected.




§ A POLYNOMIAL FUNCTOR
 

Let K be an infinite field. Let _n(K) act on the space K^n
with basis x_1,…,x_n by left multiplication, and for each d ∈ on the d-th symmetric power S^d K^n in the natural manner. Fix
d_1,…,d_k ∈ and set

    P^(n)(K):= S^d_1K^n ⊕⋯⊕ S^d_kK^n,

the space of tuples of forms of degrees d_1,…,d_k in n variables. Now
define P(K):=lim_ n P^(n)(K), the projective limit along
the maps P^(n+1)(K) → P^(n)(K) coming from the projection
K^n+1→ K^n forgetting the last coordinate. The map
P^(n+1)(K) → P^(n)(K) 
is _n(K)-equivariant if we think of _n(K) as embedded in
_n+1(K) via the map g ↦(g,1), and hence P(K) is
a module for the group _∞(K):=⋃_n _n(K).
The space P(K)
is the subspace of (R_K)^k consisting of all tuples where the i-th
element is homogeneous of degree d_i for each i ∈ [k].

Dually, let V:=lim_n → (P^(n)(K))^*. Then V is a
countable-dimensional space, P(K) is canonically isomorphic to V^*,
and hence K[P]:=SV, the symmetric algebra on V, serves as a coordinate
ring of P(K) in that the set of K-algebra homomorphisms K[P] → K
is canonically identified with P(K). We equip P(K) with the Zariski
topology in which closed subsets are characterized by polynomial equations
from K[P]. Also V and K[P] are modules for _∞(K). The
following is an instance of a general result on polynomial functors
from <cit.>.

 
Let K be an infinite field, and fix integers d_1,…,d_N. Then
any chain P(K) ⊇ X_1 ⊇⋯ of
_∞(K)-stable
Zariski-closed subsets stabilizes eventually. Equivalently, any sequence
a_1,a_2,a_3,… in K[P] has the property that for t ≫ 0 we have

    a_t ∈√(⟨⋃_i=1^t-1_∞(K) a_i
    ⟩).



 
Two comments are in order. First, the implication ⇒ between
the two statements in the theorem follows from the Nullstellensatz, since
the first sentence also holds for any algebraic closure 
of K. Second, each a_i is an element of K[P^(n_i)] for some
finite n_i. If n ≥max_i∈ [t] n_i, then the property of a_t
above is equivalent to

    a_t ∈√(⟨⋃_i=1^t-1_n(K)
    a_i ⟩),

where we have replaced ∞ by n. 




§ FINITELY MANY GENERIC INITIAL IDEALS



We now prepare for the proof of Theorem <ref>. For i=1,…,k
let f_i be the homogeneous degree-d_i series

    f_i=∑_|α|=d_ic_i,α x^α

whose coefficients live in the polynomial ring

    A=[c_i,α| i ∈ [k], α∈^, |α|=d_i]

in which the c_i,α are variables. We note that if
K is a field, then K ⊗ A is the coordinate ring
K[P] of the space P(K) introduced in
Section <ref>.

On A acts  via ring automorphisms determined by π
c_i,α=c_i,α∘π^-1, and each f_i is
-invariant. In the 0-representation f̂_i of f_i, we have

    f̂_i=∑_|α|=d_i, α(1)≥α(2) ≥…
    c_i,α x^α,

a polynomial with as many terms as there are partitions of d_i.
Write A^(n) for the subring of A generated by those c_i,α
such that ∀ m > n: α(m)=0.

Let g be an n × n-matrix of variables. Replacing, in f_i,
each x_h with h ≤ n by ∑_j g_hj x_j and each x_h with
h>n by x_h yields a series gf_i in the x_h whose coefficients
are polynomials that are linear in the c_i,α and homogeneous
of degree d_i in the g_hj. We use the formal notation g^-1
c_i,α for the coefficient of x^α in gf_i. This notation
is chosen so that if we specialize g to be the matrix of a permutation
π∈, then g^-1 c_i,α specializes to π^-1
c_i,α in the -action above.  For a polynomial
r=r(c) ∈ A
(in the c_i,α with varying i and α) write g^-1
r ∈[g_hj| h,j ∈ [n]] ⊗_ A for the polynomial obtained by replacing each c_i,α
with g^-1 c_i,α. Regarding g^-1 r as a polynomial in
the entries g_hj whose coefficients are in A, we write E_n(r)
⊆ A for the set of all nonzero coefficients. It is easy to see
that if r ∈ A^(n), then also E_n(r) ⊆ A^(n).
The following easy lemma explains the significance of this construction.

 
If K is an infinite field, then the K-span of the orbit of 1 ⊗ r
∈ K ⊗_ A under _n(K) equals the K-span of 1 ⊗
E_n(r(c)). □





In the recursive variant Stillman of SymmetricBuchberger on
page alg:Stillman, we write _p, where p is either zero or
a prime, for the prime field of characteristic p.  

We prove that Stillman terminates on input

    (0,∅,{f̂_1,…,f̂_d},(),∅,∅)

and that it prints out the sets S_i as in the theorem.

First we clarify the role of the variables. The symbols
m,B̂,Q̂ carry the same meaning as in SymmetricBuchberger.  The meaning of Z and N, finite subsets of
A, is that of vanishing and nonvanishing elements, respectively, at
the current run of the algorithm.  While Z stays constant throughout
the run (Z is extended only when recursive calls are made), N is
augmented as it accumulates elements due to presumed nonvanishing of
the leading coefficients.

The current run considers only primes in the set
Y ⊆(). Furthermore, it deals with the specializations
of the truncations f_1^(m),…,f_k^(m) with coefficients in

    A̅^(m):=A^(m)[N^-1]/√(⟨⋃_r
    ∈ Z E_m(r)⟩).

We discuss the computations of Y_1,Y_2. 

For Y_1, one starts
running the ordinary Buchberger algorithm on the ideal in the localization
A^(m)[N^-1][t] generated by ⋃_r ∈ Z E_m(r) and ta-1
(Rabinowitsch' trick), where t is an auxiliary variable.  Whenever an
integer leading coefficient is divisible by a nonzero prime (p) in Y,
the algorithm branches into a branch where multiples of p are zero and a
branch where p is invertible. Assuming that Y is constructible to begin
with, each leaf of this finite tree yields a constructible set of primes
leading to that leaf, and Y_1 is the union of the primes corresponding
to leaves where the aforementioned ideal contains 1.  

A similar algorithm
is used to compute Y_2. Since we start with Y=, it follows
that in any of the further calls of Stillman the set Y
is constructible. In other words, Y is either a finite set of nonzero
primes in () or a cofinite set in () containing (0).

Furthermore, in each run of Stillman, for each (p) ∈ Y,
the algebra _p ⊗A̅^(m) has 0 ≠ 1. This is true
at the initial call, it remains true in call (I) since m,Z,N do not
change, and it remains true in call (II) since we explicitly test for
this condition. Furthermore, it remains true later in the loop, since
there we have already removed from Y the primes in Y_1, which are
those where inverting a would cause the algebra to collapse.

Let T be the rooted tree whose vertices are the runs of Stillman
and whose edges are labelled (I) or (II) according to which call in the
algorithm leads from one run to the other. We claim that every path in
T away from the root is finite. Indeed, consider an infinite
path γ in T. The argument Y remains nonempty and weakly
decreases along γ and since it is locally closed in (),
so there exists a prime (p_0) ∈ that is in the intersection
of all the arguments Y along γ.

If infinitely many edges in γ are labelled (II), then 
Z records a_1,a_2,a_3,… with a_i ∈ A^(m_i) and m_1 ≤
m_2 ≤… and

    a_i ∉√(⟨ E_n_i(a_1) ∪⋯∪ E_n_i(a_i-1) ⟩__p_0⊗ A^(m_i)) for all  i=1,2,3,…

By Lemma <ref> and Remark <ref> this contradicts
the Noetherianity of K[P] over any infinite field K of
characteristic p_0 (Theorem <ref>).

Hence only finitely many edges in γ are labelled (II). We analyse
the computation along γ beyond the last edge e labelled (II). Let
m_∞∈∪{∞} be the supremum of the values of m
along γ, let Z_0 be the (fixed) value of Z along γ
from e onwards, and let N_∞ the union of all N's seen along
γ. Define

    Ã:=_p_0⊗
    A[N_∞^-1]/√(⟨⋃_m ≤ m_∞, r ∈ Z
    E_m(r) ⟩).

By construction, 1 ≠ 0 in Ã, hence there exists an
epimorphism from Ã to some field L of characteristic p_0.
Then the call of SeriesBuchberger with input the images of the
f_i in R_L performs the same operations as the algorithm Stillman along γ. Since the former algorithm terminates by
Proposition <ref>, so does the latter.

We conclude that T is finite. Let K be an infinite field, n a
natural number, and let f'_1,…,f'_k be homogeneous polynomials
in K[x_1,…,x_n] of degrees d_1,…,d_k, respectively.
We claim that, at the leaf of some path γ in T away from
the root, generators for the generic initial ideal of ⟨
f'_1,…,f'_k ⟩ are printed. To see this, let g
be an n × n-matrix of variables, set L:=K((g_hj)_h,j),
and consider the ideal J in L[x_1,…,x_n] generated by the
polynomials gf'_1,…,gf'_k obtained by replacing x_h in each
f'_i by ∑_h g_hj x_j. Then the generic initial ideal of ⟨
f'_1,…,f'_k ⟩⊆ K[x_1,…,x_n] equals the initial
ideal of J, and the latter is computed by Buchberger (or SymmetricBuchberger) on
input (n and) gf'_1,…,gf'_k. To find γ, proceed as follows:
whenever a ∈ A is defined as the numerator of a leading
coefficient of f̂, check if under the specialization
f_i ↦ gf'_i the element a specializes in K to zero
or to a nonzero element. If a specializes to zero, then follow call
(I) or call (II) according as ( K) ∈ Y_1 or not. If a does
not specialize to zero, then follow neither of these calls and continue
with the loop.  Along this γ, Stillman performs the same
operations as SeriesBuchberger, and hence terminates with the
generic initial ideal of ⟨ f'_1,…,f'_k ⟩.



Apart from printing (B̂) at each leaf of T we may also
print Y,Z,N, which together describe a locally closed stratum 
of P(K), for any infinite K with ( K) ∈ Y, consisting of
k-tuples with generic initial ideal generated by (B̂).




Acknowledgements.
The authors thank Institut Mittag-Leffler for the hospitality during their stay in the early 2018. 

The first author thanks Diane Maclagan, who introduced
Stillman's conjecture to him many years ago and suggested
that it might be related to Noetherianity up to symmetry.

The third author thanks MSRI for the Fall of 2017 stay, during which “The Fellowship of the Ring” and Craig Huneke rekindled his interest in Stillman's conjecture. Last but the most, the thanks go to Gennady Lyubeznik and Mike Stillman. When they both were 40 years young, Gennady suggested a problem that involved a certain constructible stratification and Mike helped solving it via parametric Gröbner bases. The intuition gained 20 years ago was instrumental in the present work.




Sne98b

[AH16]Hochster16
Tigran Ananyan and Melvin Hochster.
Small subalgebras of polynomial rings and Stillman's conjecture.
2016.
Preprint, arXiv:1610.09268.

[BS87]Bayer87
David Bayer and Michael Stillman.
A theorem on refining division orders by the reverse lexicographic
  order.
Duke Math. J., 55:321–328, 1987.

[DES17]Derksen17
Harm Derksen, Rob Eggermont, and Andrew Snowden.
Topological noetherianity for cubic polynomials.
Algebra Number Theory, 11(9):2197–2212, 2017.

[Dra17]Draisma17
Jan Draisma.
Topological Noetherianity of polynomial functors.
2017.
Preprint, arXiv:1705.01419.

[Eis95]Eisenbud95
David Eisenbud.
Commutative Algebra. With a View toward Algebraic Geometry,
  volume 150 of Graduate Texts in Mathematics.
Springer-Verlag, Berlin, 1995.

[ESS17]Erman17
Daniel Erman, Steven Sam, and Andrew Snowden.
Generalizations of Stillman's conjecture via twisted commutative
  algebras.
2017.
Preprint, arXiv:1804.09807.

[ESS18]Erman18
Daniel Erman, Steven V. Sam, and Andrew Snowden.
Big polynomial rings and Stillman's conjecture.
2018.
Preprint, arXiv:1801.09852.

[PS09]Peeva09
Irena Peeva and Mike Stillman.
Open problems on syzygies and Hilbert functions.
J. Commut. Algebra, 1(1):159–195, 2009.

[Sne98a]Snellman98
Jan Snellman.
Gröbner bases and normal forms in a subring of the power series
  ring on countably many variables.
J. Symb. Comput., 25(3):315–328, 1998.

[Sne98b]Snellman98b
Jan Snellman.
Reverse lexicographic initial ideals of generic ideals are finitely
  generated.
In Gröbner bases and applications. Based on a course for
  young researchers, January 1998, and the conference “33 years of Gröbner
  bases”, Linz, Austria, February 2–4, 1998, pages 504–518. Cambridge:
  Cambridge University Press, 1998.



