On bounds for the effective differential Nullstellensatz
Omar León Sánchez
Department of Mathematics and Statistics, McMaster University, 1280 Main St W, Hamilton, ON L8S 4L8, Canada

Alexey Ovchinnikov1

arXiv:1508.07508v1 [math.AC] 29 Aug 2015

Department of Mathematics, CUNY Queens College, 65-30 Kissena Blvd, Queens, NY 11367, USA
Ph.D. Program in Mathematics, CUNY Graduate Center, 365 Fifth Avenue, New York, New York 10016, USA

Abstract
Understanding bounds for the effective differential Nullstellensatz is a central problem in differential algebraic geometry. Recently, several bounds have been obtained using Dicksonian and antichains sequences (with a given growth
rate). In the present paper, we make these bounds more explicit and, therefore, more applicable to understanding the
computational complexity of the problem, which is essential to designing more efficient algorithms.
Keywords: Effective differential Nullstellensatz, antichain sequences
2010 MSC: primary 12H05, secondary 14Q20

1. Introduction
The effective differential Nullstellensatz problem can be stated as follows: Given a system of algebraic partial
differential equations F = 0 where F = f1 , . . . , fs , can one effectively determine if the system is consistent? In
other words, is there an effective procedure to determine if 1 belongs or not to the differential ideal generated by F in
the ring of differential polynomials? To determine if 1 belongs to an ideal in a polynomial ring, one can use algebraic
effective methods (for instance, [1, 6]). Thus, the problem reduces to finding an effective bound B such that 1 is in
the differential ideal generated by F if and only if 1 is in the ideal generated by F and its derivatives of order at most
B.
Let us rephrase the above problem in more technical terms. Let m, n, ℓ, D be positive integers. An upper bound for
the effective differential Nullstellensatz is an effectively determined function B = B(m, n, ℓ, D) that is minimal with
respect to the following property: For any differential field (K, ∂1 , . . . , ∂m ) of characteristic zero with m commuting
derivations, and any finite set F ⊂ K{x1 , . . . , xn } of differential polynomials over K in n differential indeterminates
of order and degree bounded by ℓ and D, we have
1 ∈ [F ] ⇐⇒ 1 ∈ (F )(B) .
Here, [F ] denotes the differential ideal generated by F , and (F )(B) the ideal generated by F together with its derivatives up to order B.
In order to determine the bound B using a differential elimination algorithm, one needs to determine how many
differentiation steps the algorithm makes. Determining this number of steps is the main difficulty of the problem.
The first attempt to a solution was given by Seidenberg [11] in 1956, where it was suggested how this bound could
be obtained. In [4, Theorem 1], using bounds on the length of Dicksonian sequences, an explicit bound was found

Email addresses: oleonsan@math.mcmaster.ca (Omar León Sánchez), aovchinnikov@qc.cuny.edu (Alexey Ovchinnikov)
Ovchinnikov was partially supported by the NSF grants CCF-0952591 and DMS-1413859.

1 A.

Preprint submitted to Elsevier

October 23, 2017

in terms of the Ackermann function (see Section 2 for the recursive definition of this function). More precisely, they
proved that
B ≤ A(m + 8, n + max(n, ℓ, D)).
(1.1)
Recently, in [5, Theorem 3.4], a better bound was found. More explicitly,

O n 3 α3
T

B ≤ (nαT −1 D)2

,

(1.2)


T +m

where αT = m and T = T (m, n, ℓ) is defined below.
In order to say what the value of T = T (m, n, ℓ) is, we need the following terminology. Consider the order ≤ on
m
Zm
>0 × n defined as (τ, i) ≤ (η, j) iff i = j and τ is less than or equal to η in the product order of Z>0 . To be clear
m
m
m
n = {0, 1, . . . , n − 1}, and so (τ, i) ∈ Z>0 × n means that τ ∈ Z>0 and 0 ≤ i ≤ n − 1. If a ∈ Z>0 × n, we let the
degree of a be deg a = deg τ := τ1 + · · · + τm where a = (τ, i) and τ = (τ1 , . . . , τm ). A sequence a1 , a2 , . . . of
Zm
>0 × n is called Dicksonian if for all i < j we have ai  aj . By Dickson’s lemma, every Dicksonian sequence is
finite. On the other hand, an antichain sequence is a Dicksonian sequence with the additional property that ai  aj
for i < j; in particular, an antichain sequence, as a set, is an antichain of Zm
>0 × n with respect to the order ≤. In
m
the case n = 1, we simply write Zm
instead
of
Z
×
1,
so
it
is
clear
what
is
meant by a Dicksonian (or antichain)
>0
>0
sequence of Zm
.
>0
Given a function f : Z>0 → Z>0 , we say that the degree growth of a sequence a1 , a2 , . . . of Zm
>0 × n is bounded
by f if deg ai ≤ f (i) for all i. Let Lnf,m be the maximal length of an antichain sequence of Zm
>0 × n with degree
growth bounded by f . We then have
n

T (m, n, ℓ) = 2Lf,m +1 ℓ,

where f (i) = 2i ℓ.

The number T first appeared in [10, Theorems 4.3 and 4.10] and is related to the axiomatization of the class of
differentially closed fields with several commuting derivations (in arbitrary characteristic). Theorem 4.10 of [10] is
one of the main tools used to prove the upper bound (1.2). However, [10] only dealt with the existence of such a
number, and no algorithm to compute it was considered. It is worth mentioning at this point that, in [3], the number
T together with [10, Theorem 4.10] have also been used to compute Bezout-type estimates for systems of algebraic
partial differential equations. There, [3, §3], an algorithm to compute T was presented for m = 1, 2.
The goal of this paper is to build an effective algorithm to determine the value of T (we also prove an upper bound
in closed form in terms of the Ackermann function, see Example 3.2). In Section 2, we obtain explicit upper bounds
for lengths of Dicksonian sequences whose degree growth is bounded by a given function f . The proofs of our bounds
for Dicksonian sequences are based on the ideas of [4, Lemma 8]. However, the proof of the latter contains an error
in the way it refers to [9, Proposition 1.1]. Here, we correct this error and improve the statements. In Section 3, upper
bounds for the length of antichain sequences are obtained. Furthermore, we provide an explicit recursive algorithm
which computes the exact value of the maximal length of antichain sequences; more precisely, of Lnf,m . Note that
our results provide explicit bounds for any number m of derivations, while currently explicit bounds are only known
for m = 1, 2. Due to the discussion above, having these explicit bounds is crucial for the effective differential
Nullstellensatz (1.2) (and for Bezout-type estimates of algebraic PDE’s). Of course, it is still desirable to determine
how sharp the bound in (1.2) is, or how much it can be improved. These are interesting and difficult questions, which
we leave for future research,
The type of bounds discussed in this paper have been studied in combinatorics using general versions of Dickson’s
lemma. Their existence, together with constructive recursive algorithms, appear in [2, 7, 8, 10, 11]. For instance, in
[8], it is shown that the maximal possible length of Dicksonian sequences (and antichains) is primitive recursive in
the bounding function and recursive, but not primitive recursive (if the function increases at least linearly), in m. The
motivation of our statements is the need to find explicit expressions of such bounds to make them more applicable to
designing efficient algorithms, and thus to have a better understanding of the complexity of the differential effective
Nullstellensatz (and, consequently, of differential elimination).
2. Bounds for Dicksonian sequences
This section contains explicit upper bounds for lengths of Dicksonian sequences with growth rate bounded by a
given function. We provide several versions of the bounds so that more cases are covered. We start by introducing
2

some terminology. Let


k
1
, . . . , τk = τ1k , . . . , τm
τ1 = τ11 , . . . , τm

be a sequence of m-tuples of nonnegative integers and f : Z>0 → Z>0 be an arbitrary function.
Definition 2.1. We say that the max growth of this sequence is bounded by the function f if, for all i, 1 ≤ i ≤ k,

i
≤ f (i).
max τ1i , . . . , τm

We also say that the degree growth of this sequence is bounded by the function f if, for all i, 1 ≤ i ≤ k,
i
deg τi := τ1i + . . . + τm
≤ f (i).

Remark 2.2. The sequences with bounded max growth are used in the bounds for the effective differential Nullstellensatz found in [4], see (1.1); while sequences with bounded degree growth are used for the improved bounds found
in [5], see (1.2).
The Ackermann function, which is used in our bound estimates, is defined as follows (see [9, §2], for instance):


n ≥ 0,
A(0, n) = n + 1
A(m, n) = A(m + 1, 0) = A(m, 1)
m ≥ 0,


A(m + 1, n + 1) = A(m, A(m + 1, n)) m, n ≥ 0.

Proposition 2.3. [8, Proposition 1.1] For all m, h, k ≥ 1, if τ1 , . . . , τk is a Dicksonian sequence of m-tuples, such
that
deg τi = h + i − 1, 1 ≤ i ≤ k,
then
k ≤ A(m, h − 1) − h,
and there exists such a Dicksonian sequence for which this bound is reached.
We will use the following notation:
• Let Lf,m denote the maximal length of a Dicksonian sequence of m-tuples with max growth is bounded by f .
• Let lf,m denote the maximal length of a Dicksonian sequence of m-tuples with degree growth is bounded by f .
• For an increasing function f : Z>0 → Z>0 , let ⌈f −1 (x)⌉ be the least number k such that f (k) ≥ x.
Under certain assumptions on the growth of the function f , the following lemmas yield upper bounds for Lf,m
and lf,m in closed form in terms of the Ackermann function. The idea of the proofs is that if the function f does
not grow “too fast”, one can reduce the problem to the one treated in Proposition 2.3. This kind of statements has
already been considered in [4, Lemma 8]; however, the proof of that lemma contains an error in the way it refers to
[8, Proposition 1.1]. Our lemmas below can be considered as a correction and/or improvement of that lemma. The
general case (arbitrary function f ) has been considered in [9]; an algorithm to compute the value of lf,m is provided
there. However, in general, a closed form of this bound is not available. Also, [11, Theorem 10] can be viewed
as being more general than Lemma 2.4, but, again, the bounds are not given explicitly there. Our results below are
justified by the convenience of having explicit expressions of the bounds; moreover, such expressions will be used in
Section 3.1.
Lemma 2.4. For every increasing function f : Z>0 → Z>0 and d ∈ Z>0 such that
d · f (i + 1) ≥ (m + d)f (i),

i > 0,

if
(m + d)f (i + 1) ≤ A(d, d · f (i) − 1),

i > 0,

then


Lf,m < f −1 A(m + d, (d + m)f (1) − 1)/d
3

(2.1)

Proof. Let


k
1
, . . . , τk = τ1k , . . . , τm
τ1 = τ11 , . . . , τm

(2.2)

be a Dicksonian sequence whose max growth is bounded by f . We now construct, from (2.2), a new sequence
satisfying the conditions of Proposition 2.3. We will use the fact that deg τi > 0 for 1 ≤ i < k. Append to the first
tuple d new coordinates, each equal to f (1), obtaining the following (m + d)-tuple:

1
τ11 , . . . , τm
, f (1), . . . , f (1) ,
whose degree is

deg τ1 + d · f (1) ≤ (m + d)f (1).
Let α1 := deg τ2 + d · f (2) − deg τ1 − d · f (1) − 1. Note that
0 ≤ α ≤ (m + d)f (2) − d · f (1) − 1.
1
Now, add α many new (m + d)-tuples as follows: The first m coordinates of these tuples are (τ11 , . . . , τm
), and the
last d coordinates form a Dicksonian sequence of d-tuples, starting with (f (1), . . . , f (1)), with the degree growing
exactly by 1 at each step. From Proposition 2.3 and the condition

(m + d)f (2) − d · f (1) ≤ A(d, d · f (1) − 1) − d · f (1),
such a sequence exists. The last tuple will have degree equal to
deg τ2 + d · f (2) − 1.
Next, add the tuple

2
τ12 , . . . , τm
, f (2), . . . , f (2) .

i
Continue by adding new (m + d)-tuples, whose first m coordinates are (τ1i , . . . , τm
) and last d coordinates form a
Dicksonian sequence with the degree growing by 1 at each step. When the tuple

k−1
τ1k−1 , . . . , τm
, f (k − 1), . . . , f (k − 1)

is reached, consider two cases: (1) if deg τk + d · f (k) = deg τk−1 + d · f (k − 1) then stop
 this construction;
k
(2) otherwise, repeat the construction one more time and stop at τ1k , . . . , τm
, f (k), . . . , f (k) . In both cases, we
obtain a sequence of (m + d)-tuples in which the degree grows by 1 at each step. We will show that this sequence is
Dicksonian. Suppose that it is not. Let τj , τl , j < l, be two (m + d)-tuples from this sequence for which there exists
an (m + d)-tuple τ of nonnegative integers such that
τl = τj + τ.
For an (m + d)-tuple γ, let γ ′ and γ ′′ denote the first m coordinates and the last d coordinates of it, respectively. Then
we have
τl′ = τj′ + τ ′ and τl′′ = τj′′ + τ ′′ .
If τj and τl have been added after the same tuple of the form

i
pi = τ1i , . . . , τm
, f (i), . . . , f (i) ,

or if τj coincides with such a tuple pi and τl has been added after pi , the equality
τl′′ = τj′′ + τ ′′
contradicts the fact that the last d coordinates of the tuples between pi and pi+1 , including pi and excluding pi+1 ,
form a Dicksonian sequence. If τj and τl have been added after different tuples pi and pi′ , the equality
τl′ = τj′ + τ ′
4

contradicts the fact that sequence (2.2) is Dicksonian. Therefore, our assumption was false and the constructed
sequence is Dicksonian.
By Proposition 2.3, the degree of its last element does not exceed
A(m + d, deg ā1 + d · f (1) − 1) − 1 < A(m + d, (m + d)f (1) − 1),
and, moreover, this degree equals deg τk + d · f (k). Hence,
d · f (k) < A(m + d, (d + m)f (1) − 1),
and


k < f −1 A(m + d, (d + m)f (1) − 1)/d .

Lemma 2.5. For every increasing function f : Z>0 → Z>0 and d ∈ Z>0 such that
f (i + 1) ≥ (m + 1)f (i),

i > 0,

if
(m + 1)f (i + 1) ≤ A(d, f (i) − 1),

i > 0,

then


Lf,m < f −1 A(m + d, (m + 1)f (1) − 1)

(2.3)

Proof. The proof follows as in Lemma 2.4 where the appended d-tuples begin with the form
i
(τ1i , . . . , τm
, f (i), 0, . . . , 0).

Lemma 2.6 (cf. Proposition 3.1). For every increasing function f : Z>0 → Z>0 and a, d ∈ Z>0 such that
a · f (i + 1) ≥ (a + 1)f (i),

i > 0,

if
(a + 1)f (i + 1) ≤ A(d, a · f (i) − 1),

i > 0,

then


lf,m < f −1 A(m + d, (a + 1)f (1) − 1)/a

(2.4)

Proof. The proof follows as in Lemma 2.4 where the appended d-tuples begin with the form
i
(τ1i , . . . , τm
, a · f (i), 0, . . . , 0).

Example 2.7. Let d = 2, b > 1, and ℓ > 0. Also, let f (i) = bi ℓ. Consider the following question: For which values
of b is there a ∈ Z>0 satisfying the hypothesis of Lemma 2.6? We first have the inequality
abi+1 ℓ ≥ (a + 1)bi ℓ,
which is the same as ab ≥ a + 1. We also have
(a + 1)bi+1 ≤ A(2, abi − 1) = 2abi + 1,
This is equivalent to (a + 1)b ≤ 2a. From this inequality, we see that
b≤

2a
< 2.
a+1
5

for all i ≥ 0.

Moreover, from the above inequalities, we see that for any 1 < b < 2, if a ∈ Z>0 is such that
a≥

1
b−1

and

a≥

b
,
2−b

then the hypothesis of Lemma 2.6 are satisfied. Thus, for such values of a and b, we have


lf,m < logb (A(m + 2, (a + 1)bℓ − 1)/aℓ) .

In particular, if b = 3/2 and ℓ = 2/3, we can choose a = 3. In case m = 2, we get

 


65536
− 3)/2) .
lf,2 < log 32 (A(4, 3)/2) = log 32 ((22
Remark 2.8. In the previous example we saw that 1 < b < 2. Thus, Lemma 2.6 can only deal with the case f (i) = 2i ℓ
when d ≥ 3 (see Example 3.2). As we saw in the introduction, the increasing function f (i) = 2i ℓ plays an important
role in the applications of our bounds to the effective differential Nullstellensatz, and so better bounds are desirable.
We deal with these issues in the next section.
3. Bounds for antichains
In this section, we establish explicit bounds for lengths of antichain sequences of tuples of nonnegative integers,
which can be used for computations of the bound (1.2) obtained in [5, Theorem 3.4] (see Example 3.15). Clearly,
every such sequence is a Dicksonian sequence, and so the bounds obtained in the previous section can be applied;
however, the goal of this section is to show that in general the maximal length of an antichain sequence is much
smaller, and so better bounds can be obtained for the differential Nullstellensatz computations.
Let us recall some of the notation used in the introduction. Let m and n be positive integers2 . Consider the order
m
≤ on Zm
>0 × n defined as (τ, i) ≤ (η, j) iff i = j and τ is less than or equal to η in the product order of Z>0 . Recall
that an antichain sequence of Z>0 × n is a sequence a1 , . . . , ak such that for all i 6= j we have that ai  aj . If
a ∈ Zm
>0 × n, we let the degree of a be deg a = deg τ where a = (τ, i).
Given f : Z>0 → Z>0 , we let Lnf,m be the maximal length of an antichain sequence of Zm
>0 × n with degree
growth bounded by f . In the following sections we find an upper bound of Lnf,m in terms of the Ackermann function
and, more importantly, we find a recursive algorithm which yields its exact value. Recall that, for a nonnegative
integer ℓ, the number T = T (m, n, ℓ) that appears in the bound (1.2) is given by
n

T = 2Lf,m +1 ℓ,

where f (i) = 2i ℓ.

3.1. Using Dicksonian sequences
Using the results of Section 2, we provide an upper bound for Lnf,m (for a certain family of functions) in terms of
the Ackermann function.
Proposition 3.1. Let f : Z>0 → Z>0 be an increasing function such that f (i + 1) ≥ 2f (i). If d ∈ Z>0 is such that
2f (i + 1) ≤ A(d, f (i) − 1),
then


L1f,m < f −1 (A(m + d, 2f (1) − 1)) .

(3.1)



Lnf,m < f −1 (A(m + d + 2, 2f (1)n − 1)/n) .

(3.2)

Moreover, if d ≥ 3, then, for n > 1,

2 In

this section, we consider m-tuples and n copies of Zm
>0 .

6

Proof. Inequality (3.1) follows immediately from Lemma 2.6 taking a = 1 and noting that L1f,m ≤ lf,m . For (3.2),
m+2
assume n > 1. We can embed Zm
>0 × n into Z>0 by
(ξ, i) 7→ (ξ, i, n − 1 − i).

(3.3)

Note that, given an increasing function f : Z>0 → Z>0 and a sequence (a1 , . . . , ak ) of elements in Zm
>0 × n, if
deg ai ≤ f (i), then
deg ai + n − 1 ≤ f (i) + n − 1 ≤ F (i) := f (i) · n.
Since d ≥ 3, we have
2F (i + 1) = 2nf (i + 1) ≤ nA(d, f (i) − 1) ≤ A(d, F (i) − 1).
Thus, we get that
F (L1F,m+2 ) < A(m + d + 2, 2F (1) − 1),
and so


L1F,m+2 < f −1 (A(m + d + 2, 2f (1)n − 1)/n) .

Furthermore, any antichain sequence of Zm
>0 × n whose degree growth is bounded by f yields, by means of the
n
1
embedding (3.3), an antichain sequence of Zm+2
>0 whose degree growth is bounded by F . Therefore, Lf,m ≤ LF,m+2 ,
and the result follows.
Example 3.2. In our case of interest for the applications to the effective differential Nullstellensatz, we have f (i) = 2i ℓ
and, in this case, we write Lnℓ,m instead of Lnf,m . In this case, we see that f (i + 1) ≥ 2f (i) and, if we let d = 3, we
see that
2f (i + 1) ≤ 2f (i)+2 − 3 = A(3, f (i) − 1).
Thus, we can apply Proposition 3.1 to get that
1

2Lℓ,m ℓ < A(m + 3, 4ℓ − 1),
and, if n > 1, then

n

2Lℓ,m ℓ < A(m + 5, 4nℓ − 1)/n.
We conclude that the value of T in (1.2) satisfies
T < 2 A(m + 3, 4ℓ − 1) when n = 1
and
T <

2
A(m + 5, 4nℓ − 1) when n > 1.
n

3.2. Sequence giving the exact bound
We now provide a recursive algorithm that yields the exact value of Lnf,m . The techniques we use are motivated
by the arguments for Dicksonian sequences from [9, §4].
Clearly, Lnf,1 = n. For m = 2, we have (see [3, Lemma 3.8])
Lnf,2 = bn ,

where b0 := 0 and bi+1 := f (bi + 1) + bi + 1, i ≥ 0.

(3.4)

However, for m > 2, the arguments in [3, Section 3] do not yield the value of Lnf,m .
For the rest of this section we assume that
(†) the bound function f is increasing.
Remark 3.3. If f grows at least linearly, Proposition 2.3 yields a Dicksonian sequence of Zm
>0 of length A(m, 0) − 1
such that the degree grows (by one) at each step. Hence, this Dicksonian sequence is in fact an antichain sequence
with degree growth bounded by f , and so
A(m, 0) − 1 ≤ Lnf,m .
7

Let us now recall the notions of compressed sets and binomial representations (see [9, §1] for more details).
Consider the degree-lexicographic order in Zm
>0 , τ ≺ η iff deg τ < deg η or deg τ = deg η and τ is less than η in the
m
m
lexicographic order of Zm
>0 . A subset M of Z>0 is said to be compressed if whenever τ, η ∈ Z>0 and deg τ = deg η
we have
(τ ∈ M and τ ≺ η) =⇒ η ∈ M.
For γ > 0, k < γ, and a0 ≥ a1 ≥ · · · ≥ ak ≥ 0 we define




a0 + γ
ak + γ − k
ha0 , . . . , ak iγ =
+ ···+
.
γ
γ−k
For each γ > 0, the map (a0 , . . . , ak ) 7→ ha0 , . . . , ak iγ is an order-preserving bijection between decreasing sequences
of Z>0 of length at most γ (with the lexicographic order) and the positive integers (with the usual order). Thus, for
every positive integer the inverse of this map yields a unique decreasing sequence which we call its γ-binomial
representation. For every positive integer a, we define
ahγi = ha0 , . . . , ak iγ+1 ,
where (a0 , . . . , ak ) is the γ-binomial representation of a. We set 0hγi = 0. We have the following, if a1 , a2 , b1 , b2 are
nonnegative integers such that b1 ≥ a1 , a2 ,
hγi

hγi

a1 + a2 ≤ b1 + b2 =⇒ a1 + a2

hγi

hγi

≤ b1 + b2 .

(3.5)

m
We now consider the analogue of the Hilbert-Samuel function for Zm
>0 . Given a sequence τ = (τ1 . . . , τk ) of Z>0 ,
i
for each i = 0, 1, . . . , k we let Hτ : Z>0 → Z>0 be

Hτi (d) = {ξ ∈ Zm
>0 : deg ξ = d and ξ  τ1 , . . . , τi } .
Recall that ξ  τj means that ξ − τj has at least one negative entry. Now, Macaulay’s theorem on the Hilbert-Samuel
function (cf. [9, §1]) states that
Hτi (d + 1) ≤ Hτi (d)hdi , for all i = 0, 1, . . . , k and d ≥ 1.

(3.6)

Moreover, if for some i ≤ k the sequence (τ1 , . . . , τi ) is compressed and deg τj ≤ d for all j ≤ i, then
Hτi (d + 1) = Hτi (d)hdi .

(3.7)

Let us now construct an algorithm that yields the values of Lnf,m . We first consider the case n = 1. Our strategy is
to build an appropriate antichain sequence and show that it has maximal length. The algorithm to compute its length
will follow from the construction of such a sequence. We construct an antichain sequence as follows:
µ1 = max{ξ ∈ Zm
>0 : deg ξ = f (1)},
≺

and, as long as it is possible, choose
µi = max{ξ ∈ Zm
>0 : deg ξ = f (i) and ξ  µ1 , . . . , µi−1 }.
≺

(3.8)

Since f is increasing, µ̄ := (µ1 , . . . , µL ) is indeed an antichain sequence, and f bounds its degree growth (in fact,
deg µi = f (i)). We will show that L = L1f,m . It is worth mentioning at this point that in [9, §4] the value of L is
denoted by Ω(m, f ) and is called the frontier of f in Zm
>0 .
Let us give a more explicit construction of µ̄. By the definition of ≺, the first element of µ̄ is
µ1 = (f (1), 0, . . . , 0),
if f (1) > 0 (which we might as well assume), the second element is
µ2 = (f (1) − 1, f (2) − f (1) + 1, 0, . . . , 0),
8

the third element is
µ3 = (f (1) − 1, f (2) − f (1), f (3) − f (2) + 1, 0, . . . , 0),
and so on. The penultimate element is
µL−1 = (0, . . . , 0, 1, f (L − 1) − 1),
and the last element is
µL = (0, . . . , 0, f (L)).
More generally, a recursive construction of the sequence µ̄ is given as follows:
(i) if µi−1 = (u1 , . . . , ur , 0, . . . , 0, um ) with r < m − 1 and ur > 0, then
µi = (u1 , . . . , ur − 1, f (i) − f (i − 1) + um + 1, 0, . . . , 0)

(3.9)

(ii) if µi−1 = (u1 , . . . , um−1 , um ) with um−1 > 0, then
µi = (u1 , . . . , um−1 − 1, f (i) − f (i − 1) + um + 1).

(3.10)

Remark 3.4. From the recursive construction of µ̄, one sees that, for each i ≤ L, the sequence (µ1 , . . . , µi ) is
compressed and that Hµ̄L (deg µL ) = 0.
We now aim to show that L = L1f,m . Let τ = (τ1 , . . . , τν ) be an antichain sequence of Zm
>0 with degree growth
bounded by f . Suppose ν ≥ L, we must show that then ν ≤ L. The first step is to replace τ with a more adequate
antichain sequence of the same length.
Lemma 3.5. There is an antichain sequence η = (η1 , . . . , ην ) with degree growth bounded by f , such that deg ηi ≤
deg ηi+1 for i = 1, . . . , ν. In fact, one such a sequence can be obtained by reordering τ .
Remark 3.6. The above lemma does not hold for Dicksonian sequences. This is an important difference between
Dicksonian and antichain sequences.
Proof. Let η1 = min≺ {τ1 , . . . , τν } and ηi = min≺ {(τ1 , . . . , τν ) \ (η1 , . . . , ηi−1 )} for i = 2, . . . , ν. Clearly, η =
(η1 , . . . , ην ) is an antichain sequence (as τ is). Also, by construction,
deg ηi ≤ deg ηi+1 .
Thus, all that is left to show is that f bounds the degree of η. To see this, note that, by the definition of ηi , there must
be 1 ≤ j ≤ i such that deg ηi ≤ deg τj . But since f is assumed to be increasing and it bounds the degree growth of
τ , we get
deg ηi ≤ f (j) ≤ f (i),
as desired.
Now, let
g(i) =



deg ηi , for i ≤ ν
deg ην , for i > ν

Clearly, g is an increasing function such that g(i) ≤ f (i). Let ζ = (ζ1 , . . . , ζM ) be the antichain sequence with degree
growth bounded by g constructed as in (3.8).
Lemma 3.7. With µ̄ = (µ1 , · · · , µL ) and ζ = (ζ1 , . . . , ζM ) as above, we have M ≤ L.
Proof. By the construction of µ̄ (see (3.9) and (3.10)), we have that if (u1 , . . . , um ) ∈ µ̄ and 0 ≤ v1 ≤ u1 , . . . , 0 ≤
vm−1 ≤ um−1 , then
there exists vm ≥ um such that (v1 , . . . , vm ) ∈ µ̄.
(3.11)
We now prove
Claim. For every (u1 , . . . , um−1 , um ) ∈ ζ, there is (u1 , . . . , um−1 , vm ) ∈ µ̄ with vm ≥ um .
9

Proof of Claim. We proceed by induction on i = 1, . . . , M . The first element of ζ is (g(1), 0 . . . , 0), but the first
element of µ̄ is (f (1), 0 . . . , 0) and g(1) ≤ f (1), thus, by (3.11), we can find the desired tuple in µ̄. Now suppose
ζi−1 = (u1 , . . . , ur , 0, . . . , 0, um ),

r < m − 1, ur > 0.

By induction, there is vm ≥ um such that (u1 , . . . , ur , 0, . . . , 0, vm ) ∈ µ̄. By (3.9), ζi is of the form
(u1 , . . . , ur − 1, α, 0, . . . , 0),

α := g(i) − u1 − · · · − ur + 1.

Also, by (3.9),
(u1 , . . . , ur − 1, β, 0 . . . , 0) ∈ µ̄,

β := f (i) − u1 − · · · − ur + 1.

Since g(i) ≤ f (i), we have that α ≤ β, and so, by (3.11), we can find the desired tuple in µ̄. Finally, suppose
ζi−1 = (u1 , . . . , um−1 , um ),

um−1 > 0.

By induction, there is vm ≥ um such that (u1 , . . . , um−1 , vm ) ∈ µ̄. By (3.10), ζi is of the form
(u1 , . . . , um−1 − 1, α′ ),

α′ := g(i) − u1 − · · · − um−1 + 1.

Also, by (3.10),
(u1 , . . . , um−1 − 1, β ′ ) ∈ µ̄,

β ′ = f (i) − u1 − · · · − um−1 + 1.

Again, since g(i) ≤ f (i), we have α′ ≤ β ′ , and so, once again, by ((3.11)) we can find the desired tuple in µ̄. This
proves the claim.
The claim implies that every element of ζ will be accounted for in µ̄, and so M ≤ L.
By the above lemma, M ≤ L ≤ ν. Thus, it suffices to show that ν ≤ M . Note that deg ζi = deg ηi for all i ≤ M .
We now establish how Hηi is related to Hζi .
Proposition 3.8. For each i = 0, 1, . . . , M and d ≥ 0, we have Hηi (d) ≤ Hζi (d).
Proof. We proceed by induction on i. For the base case i = 0, we have


m−1+d
0
Hη (d) =
= Hζ0 (d),
d
which is the number of m-tuples of degree d. We now proceed with the induction step i + 1. We have that for
d < g(i + 1) = deg ηi+1 = deg ζi+1 ,
Hηi+1 (d) = Hηi (d) ≤ Hζi (d) = Hζi+1 (d).
For d = g(i + 1), we have
Hηi+1 (d) = Hηi (d) − 1 ≤ Hζi (d) − 1 = Hζi+1 (d).
Now let d ≥ g(i + 1). For this case we follow the strategy of the last part of the proof of [9, Proposition 4.3]. By
Macaulay’s theorem on the Hilbert-Samuel function (see (3.6)),
Hηi+1 (d + 1) ≤ Hηi+1 (d)hdi ,

(3.12)

As we pointed out in Remark 3.4, the sequence (ζ1 , . . . , ζi ) is compressed for all i, and so the theorem of Macaulay
also yields (see (3.7))
Hζi+1 (d + 1) = Hζi+1 (d)hdi .
(3.13)
It then follows, by induction on d ≥ g(i + 1) and the fact that if a ≤ b then ahdi ≤ bhdi (which follows from (3.5)),
that
Hηi+1 (d)hdi ≤ Hζi+1 (d)hdi .
(3.14)
Thus, putting (3.12), (3.13), and (3.14) together, we get
Hηi+1 (d + 1) ≤ Hζi+1 (d + 1),
and the result follows.
10

By the above proposition, we have that
HηM (deg ηM ) ≤ HζM (deg ζM ).
As we pointed out in Remark 3.4, we have that HζM (deg ζM ) = 0. Thus, HηM (d) = 0 for all d ≥ deg ηM . Now, if
ν > M , then deg ηM+1 ≥ deg ηM , and this would imply that
HηM (deg ηM+1 ) > 0,
which contradicts the previous sentence, and so we get ν ≤ M . Thus, we have shown the following
Theorem 3.9. If f is an increasing function, then the antichain sequence µ̄ = (µ1 , . . . , µL ) built above has the
1
maximal length among antichain sequences of Zm
>0 with degree growth bounded by f , and so L = Lf,m .
3.3. Recursive construction for the length
We can now give a recursive expression for L1f,m by giving such an expression for L. We remind the reader that
we are working under the assumption that f is increasing. From the recursive construction of µ̄, we observe that, to
find its length L, we simply need to keep track of the number of steps in the above construction (cf. (3.9) and (3.10)),
and note that we stop once we reach the tuple (0, . . . , 0, f (L)). To do this, we let i denote our counter. Consider
Ψf,m = Ψ : Z>0 × Zm
>0 → Z>0 given by
Ψ(i, (0, . . . , 0, un )) = i
with
Ψ(i − 1, (u1 , . . . , ur , 0, . . . , 0, um ))
= Ψ(i, (u1 , . . . , ur − 1, f (i) − f (i − 1) + um + 1, 0, . . . , 0)),

r < m − 1, ur > 0

and
Ψ(i − 1, (u1 , . . . , um−1 , um )) = Ψ(i, (u1 , . . . , um−1 − 1, f (i) − f (i − 1) + um + 1)),

um−1 > 0.

Theorem 3.9 yields that
Corollary 3.10. If f is an increasing function, then
L1f,m = Ψm,f (1, (f (1), 0, . . . , 0)).
Remark 3.11. A straightforward computation shows that, if m = 2, then
L1f,2 = Ψ(1, (f (1), 0)) = f (1) + 1,
which is what one expects.
We now extend this recursive expression to n > 1. As in the case n = 1, we recursively build an antichain
(1)
sequence of Zm
be the antichain sequence
>0 × n of maximal length. Again, we assume that f is increasing. Let µ̄
m
with degree growth bounded by f0 (x) := f (x) constructed in (3.8) inside of Z>0 × {0}. Let L1 denote the length of
µ̄(1) ; thus, µ̄(1) is of the form
(1)
(1)
((µ1 , 0), . . . , (µL1 , 0)).
Similarly, let µ̄(2) be the antichain sequence with degree growth bounded by f1 (x) := f (x + L1 ) constructed in (3.8)
(2)
inside of Zm
. Then,
>0 × {1}, and let L2 be the length of µ̄
(2)

(2)

µ̄(2) = ((µ1 , 1), . . . , (µL2 , 1)).
Continuing in this fashion, we build µ̄(i) for i = 3, . . . n as the antichain sequence with degree bounded growth
bounded by
fi−1 (x) = f (x + L1 + · · · + Li−1 )
(1)
constructed in (3.8) inside of Zm
, . . . , µ̄(n) , then
>0 × {i − 1}. It is easy to check that if µ̄ is the concatenation of µ̄
m
µ̄ is an antichain sequence of Z>0 × n with degree growth bounded by f .
To prove that Lnf,m = L1 + · · · + Ln , we will need the following technical lemma.

11

Lemma 3.12. Suppose a1 , . . . , ar and b1 , . . . , bs are sequences of nonnegative integers such that b1 = · · · = bs−1 ≥
bs and b1 ≥ ai for all i ≤ r. If a1 + · · · + ar ≤ b1 + · · · + bs , then, for every γ > 0, we have that
hγi

hγi

a1 + · · · + ahγi
≤ b1 + · · · + bhγi
r
s .
Proof. We may assume that a1 ≥ · · · ≥ ar . We proceed by induction on (r, s) using the lexicographic order. By
(3.5), if a ≤ b then ahγi ≤ bhγi . The case r = 1 follows from this observation. It also follows from (3.5) that
ahγi + bhγi ≤ (a + b)hγi , and the case s = 1 follows from this. Thus, we assume that r, s > 1. We now consider two
cases:
Case 1. Suppose bs ≥ ar . Then the sequences a1 , . . . , ar−1 and b1 , . . . , bs−1 , bs − ar satisfy our hypothesis. By
induction,
hγi
hγi
hγi
hγi
a1 + · · · + ar−1 ≤ b1 + · · · + bs−1 + (bs − ar )hγi .
hγi

hγi

Using that ar + (bs − ar )hγi ≤ bs (which follows from (3.5)), we get the desired inequality for the original
sequences.
Case 2. Suppose bs < ar . When s = 2, we must have that a1 + · · · + ar−1 ≤ b1 , and so
hγi

hγi

hγi

a1 + · · · + ahγi
≤ (a1 + · · · + ar−1 )hγi + ahγi
≤ b1 + b2 ,
r
r
where the latter inequality follows from (3.5). So we assume that s > 2. If it happens that a1 + · · · + ar ≤
b1 + · · · + bs−1 , then we are done by induction. So we can assume that
a1 + · · · + ar−1 > b1 + · · · + bs−2 .

(3.15)

We have that
bs−1 + bs ≥ ar + (a1 + · · · + ar−1 − b1 − · · · − bs−2 ) .
It follows from (3.5), and using (3.15), that
hγi

hγi

bs−1 + bhγi
≥ ahγi
s
r + (a1 + · · · + ar−1 − b1 − · · · − bs−2 )

.

Thus, it suffices to see that
hγi

hγi

hγi

b1 + · · · + bs−2 + (a1 + · · · + ar−1 − b1 − · · · − bs−2 )

hγi

hγi

≥ a1 + · · · + ar−1 ,

but this follows by induction.
Proposition 3.13. If f is an increasing function, then the above antichain sequence µ̄ of Zm
>0 × n has the maximal
length among the antichain sequences of Zm
×
n
with
degree
growth
bounded
by
f
.
In
particular,
Lnf,m = L1 +
>0
· · · + Ln .
Proof. First enumerate µ̄ = (µ1 , . . . , µL ), where L = L1 + · · · + Ln . Let ā = (a1 , . . . , aν ) be an antichain sequence
of Zm
>0 × n of degree growth bounded by f . Suppose ν ≥ L, we must show that ν ≤ L. We assume, by reordering ā
if necessary (as in Lemma 3.5), that
deg ai ≤ deg ai+1 , i = 1, . . . , ν.
We also assume, by replacing f and µ̄ if necessary (as in the discussion after Lemma 3.5 and prior to Proposition 3.8),
that deg ai = deg µi = f (i) for all i = 1, . . . , L.
i
Given a sequence b̄ = (b1 , . . . , bk ) of Zm
>0 × n, for each i = 0, 1, . . . , k we let Hb̄ : Z>0 → Z>0 be
Hb̄i (d) = {c ∈ Zm
>0 × n : deg c = d and c  b1 , . . . , bi } .
If, for each 1 ≤ j ≤ n, we let Hb̄i,j be the Hilbert-Samuel function of the subsequence of b̄ consisting of its elements
m
in the j-copy of Zm
>0 (i.e., inside of Z>0 × {j − 1}), then clearly
Hb̄i (d) = Hb̄i,1 (d) + · · · + Hb̄i,n (d).
12

(3.16)

As in Remark 3.4, by the construction of µ̄, we have that Hµ̄L (deg µL ) = 0. Moreover, when L0 + · · · + Lj−1 ≤ i ≤
L0 + · · · + Lj (where L0 = 0), by the construction of µ̄, we have that, for all d ≥ 0,


m−1+d
i,1
i,j−1
i,j
i,j+1
i,n
0 = Hµ̄ (d) = · · · = Hµ̄
(d) ≤ Hµ̄ (d) ≤ Hµ̄
(d) = · · · = Hµ̄ (d) =
,
d
where the latter is the number of m-tuples of degree d. We now claim that, for all i = 1, . . . , L and d ≥ 0, we have
Hāi (d) ≤ Hµ̄i (d). When i = 0, we have
Hā0 (d)



m−1+d
=n·
= Hµ̄0 (d).
d

Now, when d < f (i + 1) = deg ai+1 = deg µi+1 , we have
Hāi+1 (d) = Hāi (d) ≤ Hµ̄i (d) = Hµ̄i+1 (d).
For d = f (i + 1), we have
Hāi+1 (d) = Hāi (d) − 1 ≤ Hµ̄i (d) − 1 = Hµ̄i+1 (d).
Now let d ≥ f (i + 1). By Macaulay’s theorem on the Hilbert-Samuel function (see (3.6)), we have that
Hāi+1,j (d + 1) ≤ Hāi+1,j (d)hdi ,
(j)

(3.17)

(j)

Since for each j = 1, . . . , n and i = 1, . . . , Lj , the sequence (µ1 , . . . , µi ) is compressed, the theorem of Macaulay
also yields (see (3.7))
Hµ̄i+1,j (d + 1) = Hµ̄i+1,j (d)hdi .
(3.18)
It then follows, by induction on d ≥ f (i + 1) and using Lemma 3.12, that
Hāi+1,1 (d)hdi + · · · + Hāi+1,n (d)hdi ≤ Hµ̄i+1,1 (d)hdi + · · · + Hµ̄i+1,n (d)hdi .

(3.19)

Thus, putting (3.16), (3.17), (3.18), and (3.19) together, we get
Hāi+1 (d + 1) ≤ Hµ̄i+1 (d + 1).
This proves our claim. The result now follows as in the discussion prior to Theorem 3.9.
By Proposition 3.13 and the recursive construction of µ̄, we obtain
Corollary 3.14. If f is an increasing function, then
Lnf,m = ψn
where ψ0 = 0 and ψi+1 = Ψfi ,m (1, (fi (1), 0, . . . , 0)) + ψi , for i ≥ 0 . We recall that fi (x) = f (x + ψi ).
By Remark 3.11, when m = 2, we get precisely (3.4), as expected.
Example 3.15. Again, for the applications to the effective differential Nullstellensatz we consider f (i) = 2i ℓ and, in
this case, we write Lnℓ,m instead of Lnf,m .
1. When m = 2 and n = 1, we get L1ℓ,2 = 2ℓ + 1. So, in this case, the value of T is
T = 22ℓ+2 ℓ.
2. More generally, when m = 2, we get Lnℓ,2 = bn where b0 = 0 and bi+1 = 2bi +1 ℓ + bi + 1. For instance,
2ℓ+2

L2ℓ,2 = 22ℓ+2 ℓ + 2ℓ + 2 and L3ℓ,2 = 22
13

+2ℓ+3

ℓ + 22ℓ+2 + 2ℓ + 3.

3. For m = 3, up until now no explicit values of T were known. Let n = 1 and ℓ = 1, then
L11,3 = Ψf,3 (1, (2, 0, 0)) = 70,
and so, in this case, T = 271 . Note that the antichain sequence of maximal length built in (3.8) takes the form
(2, 0, 0)
(1, 3, 0), (1, 2, 5), (1, 1, 14), (1, 0, 31)
(0, 64, 0), (0, 63, 27 − 63), (0, 62, 28 − 62), . . . , (0, 1, 269 − 1), (0, 0, 270)
520

4. For m = 3, n = 1 and ℓ = 2, we get L12,3 = 22

+520

+ 2520 + 519. So the value of T is

2520 +520

T = 22

+2520 +521

.

In this case, the antichain of maximal length takes the form
(4, 0, 0)
(3, 5, 0), (3, 4, 9), . . . , (3, 0, 28 − 3)
9

(2, 29 − 2, 0), (2, 29 − 3, 210 − 29 + 1), . . . , (2, 0, 22
9

(1, 22

+8

29 +8

(0, 22

9

− 1, 0), (1, 22
9

+2 +8

+8

− 2, 22

29 +8

, 0), (0, 22

9

9

+9

+2 +8

9

− 22

+8

29 +8

− 1, 22

+7

− 2)
29 +8

+ 1), . . . , (1, 0, 22
9

+2 +9

29 +8

− 22

9

+2 +8

+29 +7

− 1)
9
22 +8 29 +8

+ 1), . . . , (0, 0, 22

9 +8

+22

+29 +8

)

References
[1] W.D. Brownawell, Bounds for the degrees in the Nullstellensatz,
http://dx.doi.org/10.2307/1971361.

Annals of Mathematics 126 (1987) 577–591. URL:

[2] D. Figueira, S. Figueira, S. Schmitz, P. Schnoebelen, Ackermannian and primitive-recursive bounds with Dickson’s lemma, in: 26th Annual
IEEE Symposium on Logic in Computer Science, pp. 269–278. URL: http://dx.doi.org/10.1109/LICS.2011.39.
[3] J. Freitag, O. León Sánchez, Effective uniform bounds in partial differential fields, 2014. URL: http://arxiv.org/abs/1411.0029.
[4] O. Golubitsky, M. Kondratieva, A. Ovchinnikov, A. Szanto, A bound for orders in differential Nullstellensatz, Journal of Algebra 322 (2009)
3852–3877. URL: http://dx.doi.org/10.1016/j.jalgebra.2009.05.032.
[5] R.
Gustavson,
M.
Kondratieva,
A.
http://arxiv.org/abs/1411.1000.

Ovchinnikov,

New

effective

[6] J. Kollár, Sharp effective Nullstellensatz, Journal of the Americal
http://dx.doi.org/10.1090/S0894-0347-1988-0944576-7.
[7] K. McAloon,
Petri nets and large finite sets,
Theoretical
http://dx.doi.org/10.1016/0304-3975(84)90029-X.

differential

Mathematical
Computer

Nullstellensatz,

Society

Science

32

1

(1988)
(1984)

2014.

URL:

963–975.

URL:

173–183.

URL:

[8] G. Moreno Socı́as, An Ackermannian polynomial ideal, An Ackermannian polynomial ideal, volume 539 of Lecture Notes in Computer
Science, Springer, 1991, pp. 269–280. URL: http://dx.doi.org/10.1007/3-540-54522-0_116.
[9] G. Moreno Socı́as, Length of polynomial ascending chains and primitive recursiveness, Mathematica Scandinavica 71 (1992) 181–205. URL:
http://www.mscand.dk/article/download/12421/10437.
[10] D. Pierce,
Fields with several commuting derivations,
http://dx.doi.org/10.1017/jsl.2013.19.

Journal

of

Symbolic

Logic

79

(2014)

1–19.

[11] A. Seidenberg, An elimination theory for differential algebra, University of California publications in Mathematics III (1956) 31–66.

14

URL:

