NONSTANDARD METHODS FOR BOUNDS IN DIFFERENTIAL POLYNOMIAL RINGS

MATTHEW HARRISON-TRAINOR, JACK KLYS, AND RAHIM MOOSA

Abstract. Motivated by the problem of the existence of bounds on degrees and orders in checking primality of radical (partial) differential ideals, the nonstandard methods of van den Dries and Schmidt [“Bounds in the theory of polynomial rings over fields. A nonstandard approach.”, Inventionnes Mathematicae, 76:77–91, 1984] are here extended to differential polynomial rings over differential fields. Among the standard consequences of this work are: a partial answer to the primality problem, the equivalence of this problem with several others related to the Ritt problem, and the existence of bounds for characteristic sets of minimal prime differential ideals and for the differential Nullstellensatz.

1. Introduction

This paper is concerned with existence proofs of bounds in the theory of differential polynomial rings over differential fields. We are motivated by the following open question in differential-algebraic geometry: Given a differential-algebraic family of Kolchin-closed sets {V_{a} ⊆ L^{n} : a ∈ L^{m}}, where L is a differentially closed field of characteristic zero in several commuting derivations, is the set

D := {a ∈ L^{m} : V_{a} is irreducible}

Kolchin-constructible? Because of quantifier-elimination for differentially closed fields, this is equivalent to asking whether D can be defined by a first-order formula in the language of differential rings. Now if V_{a} is defined by the vanishing of the finite system S_{a} of differential polynomials over L, then V_{a} is irreducible if and only if the radical differential ideal generated by S_{a}, denoted by {S_{a}}, is prime. Membership of f_{b} in {S_{a}}, for a given differential polynomial with coefficients b, is a first-order property of (a, b) because it is equivalent to the vanishing of f_{b} on V_{a}. Primality of {S_{a}}, on the other hand, is not on the face of it first-order in a because it requires quantification over all (coefficients of) differential polynomials f and g such that fg ∈ {S_{a}}. If, however, we could restrict these quantifications to differential polynomials of bounded degree and order – bounded independently of a – then we would have a first-order definition for D. In fact, one expects to have bounds that are also independent of the base differential field.

Date: May 2nd, 2011.

2000 Mathematics Subject Classification. Primary 12H05. Secondary 03H05.

Matthew Harrison-Trainor and Jack Klys were partially supported by an NSERC USRA..

Rahim Moosa was partially supported by an NSERC Discovery Grant.

Conjecture 1.1 (Definability of primality). For every d there exists r = r(d, n, m) such that for every field of characteristic zero equipped with m commuting derivations Δ = {δ_{1}, …, δ_{m}} and every finite set S of Δ-polynomials in n indeterminates X = (X_{1} …, X_{n}) over k of degree and order ≤ d, the following are equivalent:

(i) {S}, the radical Δ-ideal generated by S, is prime, (ii) {S} is proper and for all Δ-polynomials f and g in X over k of degree and

order ≤ r, if fg ∈ {S} then f ∈ {S} or g ∈ {S}.

The purely algebraic analogue of Conjecture 1.1, which asks for a bound on degrees for checking the primality of radical ideals in polynomial rings over fields, has an affirmative solution, and this is why irreducibility in algebraic families of Zariskiclosed sets is definable (in the language of rings). Constructive proofs go back to the work of Hermann [4] and later Seidenberg [6]. Clearer and more efficient proofs of the existence of bounds were given by van den Dries and Schmidt in [7] using a nonstandard approach; that is, by studying ultraproducts of polynomial rings over fields. Our goal here is to extend the methods of van den Dries and Schmidt to the differential setting; to study the ultraproducts of differential polynomial rings over differential fields and to bring that to bear on Conjecture 1.1.

We obtain a partial solution whereby we are able to bound one of the two quantifiers in the definition of primality; see Theorem 5.4 below. We are also able to prove the equivalence of Conjecture 1.1 with four other natural existence-of-bounds conjectures in differential algebra; see Theorem 5.7. Here we are motivated by [2] where a related series of problems around the existence of algorithms in computational differential algebra are shown to be equivalent. As a byproduct of our analysis we also obtain quick existence proofs of bounds in two other areas where bounds have been obtained by (or are deducible from) constructive methods; namely for characteristic sets of minimal prime differential ideals (Theorem 6.1) and for the differential Nullstellensatz (Theorem 6.3).

The results described above are proved in the final two sections of the paper, based on the study of internal differential polynomials carried out in Section 4. In Sections 2 and 3 below we review the relevant notions from differential algebra and introduce the corresponding nonstandard setting.

We are grateful to Alexey Ovchinnikov for his explanations regarding several points of constructive differential algebra.

2. Differential-algebraic preliminaries

We begin with a quick review of differential polynomial rings, primarily to set notation. See [5] for details.

Suppose m, n < ω, (k, Δ = {δ_{1}, …, δ_{m}}) is a differential field of characteristic zero in m commuting derivations, and X = (X_{1}, …, X_{n}) is an n-tuple of indeterminates. Let Θ = {δ_{1}^{e_{1}} ⋯ δ_{m}^{e_{m}} : e_{i} ≥ 0} be the set of Δ-operators and set ΘX := {θX_{i} : θ ∈ Θ, 1 ≤ i ≤ n}. The ring of Δ-polynomials in X over k, denoted by k{X}, is the ring of (commutative) polynomials in ΘX over k equipped with the natural structure of a Δ-ring. For this reason the X_{i} are called differential indeterminates while the elements of ΘX are the algebraic indeterminates. For a subset S ⊂ k {X}, we use (S), [S], and {S} to denote, respectively, the ideal, Δ-ideal, and radical Δ-ideal generated by S. By the degree of a Δ-polynomial f ∈ k{X} we will mean the total degree of f as an element of k[ΘX], and by its order we mean the maximum order of the Δ-operators that appear in f. (The order of a Δ-operator δ_{1}^{e_{1}} ⋯ δ_{m}^{e_{m}} is e_{1} + ⋯ + e_{m}.)

We rank the algebraic indeterminates by δ_{1}^{e_{1}} ⋯ δ_{m}^{e_{m}}X_{i} < δ_{1}^{f_{1}} ⋯ δ_{m}^{f_{m}}X_{j} if and only

if (∑_{l=1}^{m} e_{l}, i, e_{1}, …, e_{m}) < (∑_{l=1}^{m} f_{l}, j, f_{1}, …, f_{m}) in the lexicographic ordering.

According to this ranking we enumerate ΘX as (Z_{h} : h < ω), and define the height of an algebraic indeterminate v to be the h such that v = Z_{h}. Given f ∈ k{X}\k, the leader of f, denoted by v_{f}, is the highest ranking algebraic indeterminate appearing in f, and the height of f is by definition the height of its leader. The leading coefficient when f is written as a polynomial in v_{f} is called the initial of f and is denoted by I_{f}. Note that the leader of I_{f} is strictly less than v_{f} in rank. The derivative of f with respect to v_{f} is called the separant of f and will be denoted by S_{f}. A consequence of these definitions is that for any θ ∈ Θ \ {1}, the initial of θf is S_{f}.

The ranking of the algebraic indeterminates extends to Δ-polynomials by the lexicographic ordering on the pair (v_{f}, deg_{v_{f}} (f)). So for example both rank(I_{f}) < rank(f) and rank(S_{f}) < rank(f). This ranking extends also to finite sequences of Δ-polynomials by the following lexicographic-like ranking: rank(f_{1}, …, f_{r}) < rank(g_{1}, …, g_{s}) if either there is k ≤ min(r, s) with rank(f_{i}) = rank(g_{i}) for all i < k and rank(f_{k}) < rank(g_{k}), or r > s and rank(f_{i}) = rank(g_{i}) for all i ≤ s.

Suppose f, g ∈ k{X}. Recall that f is reduced with respect to g if θv_{g} does not appear in f for any θ ∈ Θ \ {1} and the degree of v_{g} in f is strictly less than its degree in g. In particular, if rank(f) < rank(g) then f is reduced with respect to g, but the converse need not hold; even when f is reduced with respect to g higher ranking algebraic indeterminates than v_{g} may appear in f, just not any that can be obtained from v_{g} by applying the derivations. A set of Δ-polynomials is called autoreduced if every element is reduced with respect to all the others. Autoreduced sets are always finite, and we canonically view them as finite sequences by ordering the elements of an autoreduced set according to increasing height. This induces a ranking on the autoreduced subsets of k {X}.

Given a subset S ⊆ k{X}, a characteristic set for S is a lowest ranking autoreduced subset of S. It is a basic fact that every Δ-ideal has a characteristic set. Moreover, prime Δ-ideals are determined by their characteristic sets in the following sense: if P is a prime Δ-ideal and Λ is a characteristic set for P then

P = I[Λ] := {g ∈ k{X} : H_{Λ}^{t}g ∈ [Λ], for some t ∈ ℕ}

where by definition H_{Λ} := ∏_{f∈Λ} S_{f}I_{f}. For notational reasons specific to this paper

we are here denoting by I[Λ] what is usually denoted in the literature by [Λ] : H_{Λ}^{∞}.

Finally let us recall the characterisation of characteristic sets of prime Δ-ideals. First, given a finite set Λ ⊂ {X} and h < ω, (Λ)_{h} denotes the ideal generated by Λ together with all the derivatives of Λ that are of height at most h. An autoreduced set Λ is coherent if whenever f ≠ g in Λ are such that θ_{f}v_{f} = θ_{g}v_{g} = Z_{h} for some θ_{f}, θ_{g} ∈ Θ, and if θ_{f}, θ_{g} are such that the height h is minimal possible, then S_{g}θ_{f}f − S_{f}θ_{g}g ∈ (Λ)_{h−1}.

Fact 2.1 (Lemma 2 of §IV.9 of Kolchin [5]). Let Λ be a finite subset of k {X}. Then Λ is a characteristic set of a prime Δ-ideal if and only if (1) Λ is coherent, and

(2) I(Λ) := {g ∈ k {X} : H_{Λ}^{t}g ∈ (Λ), for some t ∈ ℕ} is a prime ideal containing no nonzero elements that are reduced with respect to Λ.

The main usefulness of this criterion rests in the fact that it makes reference only to the ideal (Λ) and not the Δ-ideal [Λ].

3. Internal Δ-polynomials

We will be using nonstandard methods just as they were used in [7], a gentle introduction to which can be found in Section 3 of [8]. Fix once and for all an index set 𝕀 and a nonprincipal ultrafilter U on 𝕀. We work in the ultrapoduct with respect to U of whatever universe of algebraic objects we are interested in. For any set A we denote by A^{∗} its nonstandard interpretation, namely ∏_{U} A. Given an

element a of the ultraproduct we will usually fix an 𝕀-indexed sequence representing that element and use a(r) to denote the rth co-ordinate of that representative. We say that a condition P is true of a “co-ordinatewise almost everywhere” if the set of indices r ∈ 𝕀 for which P is true of a(r) is a member of the ultrafilter. This does not depend on the choice of representative for a. Recall that a subset S of an ultraproduct is internal if there exists a sequence of subsets (S_{r} : r ∈ 𝕀), called the family of components of S, such that a ∈ S if and only if a(r) ∈ S_{r} almost everywhere. Note that every finite set is internal with components the set of coordinates, that is, S_{r} = {a(r) : a ∈ S} for all r ∈ 𝕀. We say that a condition P is true of an internal set S “componentwise almost everywhere” if the set of indices r ∈ 𝕀 for which P is true of S_{r} is a member of the ultrafilter. This too does not depend on the choice of family of components for S.

Suppose {K_{r} : r ∈ 𝕀} is a sequence of Δ-fields of characteristic zero. Fixing differential indeterminates X = (X_{1}, …, X_{n}), we have the Δ-ring of internal Δpolynomials over K, namely ∏_{U} (K_{r}{X}), which, following [7] in the algebraic case,

we denote by K{X}_{int} where K := ∏_{U} K_{r}. Almost every differential algebraic no-

tion has an internal analogue in K{X}_{int}. For example, given f, g ∈ K{X}_{int}, we say that f is of lower internal rank than g if it is of lower rank co-ordinatewise almost everywhere, that is, if {r ∈ 𝕀 : f(r) is of lower rank than g(r)} ∈ U. Similarly, f is internally reduced with respect to g if it is reduced with respect to g co-ordinatewise almost everywhere. An internal subset Λ ⊂ K{X}_{int} is internally autoreduced if it is componentwise autoreduced almost everywhere. Note that unlike for standard autoreduced sets, internally autoreduced subsets of K{X}_{int} need not be finite (though they will be componentwise finite almost everywhere). Nevertheless we can rank the internally autoreduced sets by declaring that rank (Λ) < rank (Γ) if this is the case componentwise almost everywhere. Similarly, an internally characteristic set for an internal set S, is an internal subset Λ ⊂ S such that Λ_{r} is characteristic for S_{r} for almost all r. As an illustration of how these definitions play out, we prove the following straightforward equivalences.

Lemma 3.1. Suppose S, Λ ⊂ K{X}_{int} are internal sets.

(i) Λ is internally autoreduced if and only if every element of Λ is internally reduced with respect to every other element of Λ.

(ii) Λ is an internally characteristic set for S if and only if Λ is a minimally ranked internally autoreduced subset of S.

Proof. For the left-to-right direction of (i), suppose V ∈ U is such that Λ_{r} is autoreduced in K_{r} {X} for all r ∈ V. Given f ≠ g in Λ, shrinking V if necessary, we have that f(r) ≠ g(r) are in Λ_{r} and hence are reduced with respect to each other. It follows that f and g are internally reduced with respect to each other. For the converse, suppose W := {r ∈ 𝕀 : Λ_{r} is autoreduced} ∉ U. Then V := 𝕀 \ W ∈ U. For each r ∈ V, let f_{r} ≠ g_{r} in Λ_{r} be such that f_{r} is not reduced with respect to g_{r}. Let f, g ∈ K{X}_{int} be such that f(r) = f_{r} and g(r) = g_{r} for almost all r. Then f ≠ g are in Λ and f is not internally reduced with respect to g.

Now suppose that Λ is internally characteristic for S, and let V ∈ U be coordinates where Λ_{r} is a characteristic subset of S_{r}. In particular, Λ is internally autoreduced. Now if Σ ⊂ S is any other internally autoreduced set, after possibly shrinking V, we have that Σ_{r} ⊂ S_{r} is autoreduced and hence rank (Λ_{r}) ≤ rank (Σ_{r}), for all r ∈ V. So rank (Λ) ≤ rank (Σ). This proves that Λ is minimally ranked among the internally autoreduced subset of S. For the converse, suppose that Λ ⊂ S is internally autoreduced but W := {r ∈ 𝕀 : Λ_{r} is characteristic for S_{r}} ∉ U. Then V := 𝕀 \ W ∈ U. Shrinking V we may assume that Λ_{r} is autoreduced for each r ∈ V. Hence, for each r ∈ V there must exist an autoreduced subset Σ_{r} ⊂ S_{r} with rank (Σ_{r}) < rank (Λ_{r}). The sequence (Σ_{r} : r ∈ V) extends to the family of components of an internal set Σ ⊂ K{X}_{int}. It follows that Σ ⊂ S is internally autoreduced and rank (Σ) < rank (Λ). That is, Λ is not minimally ranked among the internally autoreduced subsets of S. This proves (ii). □

By an internal Δ-ideal of K{X}_{int} we mean an internal subset of K{X}_{int} almost all of whose components are Δ-ideals. Note that an internal Δ-ideal is a Δ-ideal of K{X}_{int}. Given an internal set S ⊂ K{X}_{int}, we use (S)_{int}, [S]_{int}, and {S}_{int} to denote the internal ideal whose rth component is, respectively, the ideal, Δ-ideal, and radical Δ-ideal generated by S_{r}. On the other hand, it is not hard to check that (S)_{int} is contained in every ideal of K{X}_{int} containing S, [S]_{int} is contained in every internal Δ-ideal of K{X}_{int} containing S, and {S}_{int} is contained in every radical internal Δ-ideal of K{X}_{int} containing S.

It follows immediately from the definitions that since every Δ-ideal has a characteristic subset, every internal Δ-ideal has an internally characteristic subset. Moreover, a prime internal Δ-ideal is determined by an internally characteristic set in the following sense: if P is a prime internal Δ-ideal and Λ ⊂ P is an internally characteristic set for P then

P = I_{int}[Λ] := {g ∈ K{X}_{int} : (H_{Λ}^{int})^{N}g ∈ [Λ]_{int}, for some N ∈ ℕ^{∗}}

where by definition H_{Λ}^{int} ∈ K{X}_{int} is determined by the sequence (H_{Λ_{r}} : r ∈ 𝕀). Indeed, this is just by transfer from the corresponding fact about standard prime Δ-ideals. Moreover, the characterisation of characteristic sets of prime Δ-ideals (Fact 2.1) tranfers easily:

Fact 3.2. An internal set Λ ⊂ K{X}_{int} is internally characteristic for a prime internal Δ-ideal if and only if Λ is internally coherent and

I_{int}(Λ) := {g ∈ K{X}_{int} : (H_{Λ}^{int})^{N} g ∈ (Λ)_{int}, for some N ∈ ℕ^{∗}}

is a prime internal ideal containing no nonzero elements that are internally reduced with respect to Λ.

Of course, here internally coherent means coherent in almost all components.

4. Comparing K{X}_{int} and K{X}

Since K = ∏_{U} K_{r} is equipped with the natural (co-ordinatewise) Δ-field structure we also have the Δ-polynomial ring K{X}. There is a natural embedding of K{X} into K{X}_{int} over K which essentially “unpacks” the coefficients of the polynomial. More precisely, if we list all of the monomials in ΘX as M_{1}, M_{2}, …, then we can write an element of K{X} as ∑_{i=1}^{∞} a_{i}M_{i} with the a_{i} ∈ K, all but finitely many of which are zero. Then we can define ϕ : K{X} → K{X}_{int} by

[ϕ (∑_{i=1}^{∞} a_{i}M_{i})] (r) = ∑_{i=1}^{∞} a_{i}(r)M_{i}

It is easy to check that ϕ is an embedding of Δ-rings that is the identity on K. This allows us to view K{X}_{int} as a Δ-ring extension of K{X}. Following the approach of [7], we study the extent to which the properties of K{X} are reflected in this extension.

We have the following intrinsic characterisation of K{X}: it is the subring of elements f ∈ K{X}_{int} for which for some V ∈ U there is a bound on the degree and order of f(r) independently of r ∈ V. Indeed, if f has this property then there are finitely many monomials M_{1}, …, M_{N} such that for all r ∈ V there are a_{i,r} ∈ K_{r} such that f(r) = ∑_{i=1}^{N} a_{i,r}M_{i}, and so f is ϕ (∑_{i=1}^{N} a_{i}M_{i}) where a_{i} ∈ K is such that a_{i}(r) = a_{i,r} for all r ∈ V. Conversely, from the definition of ϕ it follows that if f ∈ K{X} then there is a set V ∈ U such that for all r ∈ V, ϕ(f)(r) has the same “shape” as f, ie. a monomial M appears with a nonzero coefficient in f if and only if it does in ϕ(f)(r) as well.

Let us first consider K{X}_{int} purely as a ring extension of K{X}. Recall that Z = (Z_{i} : i < ω) is an enumeration of the algebraic indeterminates according to height. The underlying ring structure of K{X} is simply the pure polynomial ring K [Z], while that of K{X}_{int} is the ring of internal polynomials K [Z]_{int} := ∏_{U} K_{r} [Z]. In the following proposition we extend some of the results of van den Dries and Schmidt – which were proved in [7] for finitely generated polynomial rings – to this infinitary setting.

Proposition 4.1. The ring K{X}_{int} is a faithfully flat K{X}-module. Moreover, for any ideal I of K{X},

(a) I is prime in K{X} if and only if IK{X}_{int} is prime in K{X}_{int}, and

(b) \{g ∈ K\{X\} : g^{N} ∈ IK\{X\}_{int} for some N ∈ ℕ^{∗}\} = \sqrt{I}

Proof. As above, K{X} = K[Z] and K{X}_{int} = K[Z]_{int}, where Z = (Z_{i} : i < ω) is an enumeration of the algebraic indeterminates according to height.

For flatness consider a homogeneous linear equation

f_{1}Y_{1} + ⋯ f_{ℓ}Y_{ℓ} = 0

where f_{1}, …, f_{ℓ} ∈ K[Z]. We denote this equation by F Y = 0. Suppose g ∈ K[Z]_{int}^{ℓ} is a solution. We need to show that g is a K[Z]_{int}-linear combination of solutions in K[Z]^{ℓ}. We do this by passing first to K [Z_{i} : i < h]_{int}, where h is such that f_{1}, …, f_{ℓ} ∈ K [Z_{i} : i < h], and then to K [Z_{i} : i < h] by the finite variable case. For each r ∈ 𝕀, let h_{r} ≥ h be such that g(r) ∈ K_{r} [Z_{i} : i < h_{r}]^{ℓ}. Since, for almost all r, g(r) is a solution to F (r)Y = 0, and since K_{r} [Z_{i} : i < h_{r}] is flat over K_{r} [Z_{i} : i < h], we have that g(r) is a K_{r} [Z_{i} : i < h_{r}]-linear combination of solutions to F (r)Y = 0 in K_{r} [Z_{i} : i < h]^{ℓ}. Now, as the coefficients of the equation are of bounded degree independently of r, Theorem 1.4 of [7] gives us a bound α, independent of r, such that all solutions in K_{r} [Z_{i} : i < h]^{ℓ} are K_{r} [Z_{i} : i < h]-linear combinations of solutions with degree bounded by α. Let N be the K_{r}-dimension of the subspace of K_{r} [Z_{i} : i < h]^{ℓ} made up of tuples of polynomials with degree bounded by α. Then N depends only on α and h, and hence not on r. Moreover, for each r, there exist solutions e_{1,r}, …, e_{N,r} ∈ K_{r} [Z_{i} : i < h]^{ℓ} such that g(r) is a K_{r} [Z_{i} : i < h_{r}]-linear combination of {e_{1,r}, …, e_{N,r}}. Setting e_{j} ∈ K [Z_{i} : i < h]_{int}^{ℓ} to be such that e_{j}(r) = e_{j,r} almost everywhere, we have that g is a K[Z]_{int}-linear combination of {e_{1}, …, e_{N}}. Theorem 1.1 of [7] tells us that K [Z_{i} : i < h]_{int} is a flat extension of K [Z_{i} : i < h], and so each e_{j} is a K [Z_{i} : i < h]_{int}-linear combination of solutions in K [Z_{i} : i < h]^{ℓ}. Hence g is a K[Z]_{int}-linear combination of solutions in K [Z_{i} : i < h]^{ℓ} ⊂ K[Z]^{ℓ}, as desired.

For faithful flatness, suppose AY = B is a system of k linear equations in ℓ unknowns over K [Z] with a solution in K [Z]_{int}^{ℓ}. Let h be a bound on the heights of the entries of A and B. Then working co-ordinatewise, and using the fact that K_{r} [Z] is faithfully flat over K_{r}[Z_{i} : i < h], we have that AY = B has a solution in K [Z_{i} : i < h]_{int}. But the latter is faithfully flat over K [Z_{i} : i < h] by Theorem 1.8 of [7]. Hence we get a solution in K [Z]^{ℓ}, as desired.

The right-to-left direction of part (a) of the “moreover” clause is an immediate consequences of the fact that by faithfull flatness IK{X}_{int} ∩ K{X} = I. For the converse, note first of all that since checking any instance of primeness of IK{X}_{int} involves only finitely many elements from I, it would suffice to prove the result with I ∩ K [Z_{i} : i < h], which is still prime, in place of I, for each h < ω. But I ∩ K [Z_{i} : i < h] is finitely generated, and hence it will suffice to prove the result for finitely generated I. That is, we assume (Λ)K{X} is prime for some finite subset Λ ⊂ K{X}, and prove that (Λ)K{X}_{int} is prime. Let h be such that Λ ⊂ K [Z_{i} : i < h]. Since K[Z] is faithfully flat over K [Z_{i} : i < h], (Λ)K[Z] ∩ K [Z_{i} : i < h] = (Λ)K [Z_{i} : i < h] and hence the latter is prime. By Theorem 2.5 of [7], (Λ)K [Z_{i} : i < h]_{int} is prime. Note that (Λ)K [Z_{i} : i < h]_{int}, being finitely generated, is an internal ideal with family of components ((Λ_{r})K_{r} [Z_{i} : i < h] : r ∈ 𝕀) where Λ_{r} := {f(r) : f ∈ Λ}. Hence, for almost all r, (Λ_{r})K_{r} [Z_{i} : i < h] is prime. But then, passing to a polynomial ring extension over the same field, we have that (Λ_{r})K_{r}[Z] is prime for almost all r. It follows that the corresponding internal ideal (Λ)K[Z]_{int} is prime, as desired.

Finally, for (b), suppose g ∈ K{X} and N ∈ ℕ^{∗} are such that g^{N} ∈ IK{X}_{int}. Let Λ be a finite subset of I such that g^{N} ∈ (Λ)K\{X\}_{int}. We show that g ∈ \sqrt{(Λ)}. Let h be such that Λ ⊂ K [Z_{i} : i < h] and g ∈ K [Z_{i} : i < h]. Then, for almost all r, g(r)^{N(r)} ∈ (Λ_{r})K_{r}[Z] ∩ K_{r} [Z_{i} : i < h] = (Λ_{r})K_{r} [Z_{i} : i < h]. That is, g ∈ \sqrt[int]{(Λ)K [Z_{i} : i < h]_{int}}. Corollary 2.7 of [7] says that \sqrt[int]{(Λ)K [Z_{i} : i < h]_{int}} = \sqrt{(Λ)}·K [Z_{i} : i < h]_{int}. By the faithful flatness of K [Z_{i} : i < h]_{int} over K [Z_{i} : i < h], we get g ∈ \sqrt{(Λ)}, as desired. The reverse containment of part (b) is clear. □

Now let us consider K{X}_{int} as a Δ-ring extension of K{X}. Note that many of the internal notions discussed in the last section restrict to the usual ones on K{X}. For example, suppose f, g ∈ K{X}. Then f is internally of lower rank than g in K{X}_{int} (respectively internally reduced with respect to g) if and only if it is of lower rank than g in K{X} (respectively reduced with respect to g). This is because rank and reducedness depend only on the shape of Δ-polynomials, and elements of K{X} have the same shape as their co-ordinates almost everywhere. Similarly, a finite subset of K{X} is autoreduced in K{X} if and only if, as an internal subset of K{X}_{int}, it is internally autoreduced. Also, the ranking of internally autoreduced subsets of K{X}_{int} restricts to the usual ranking of autoreduced (finite) subsets of K{X}. In particular, if Λ ⊂ K{X} is an internally characteristic set of a prime internal Δ-ideal of K{X}_{int}, then Λ is a characteristic set of a prime Δideal of K{X}. Indeed, if P ⊂ K{X}_{int} is a prime internal Δ-ideal witnessing the truth of the antecedent of the above statement, then P ∩ K{X} witnesses the consequent. The converse, however, is not so straightforward, and constitutes the main goal of this section (cf. Theorem 4.3 below). We will use the characterisation of characteristic subsets of prime Δ-ideals given by Fact 2.1 (and its nonstandard analogue Fact 3.2). The following lemma is the main technical result that will allow us to do so.

Lemma 4.2. Let Λ ⊂ K {X} be a finite set. Then

(a) Λ is coherent in K{X} if and only if Λ is internally coherent in K{X}_{int}.

(b) If I(Λ) is prime in K{X} then I_{int}(Λ) = I(Λ)K{X}_{int}, and hence I_{int}(Λ) is prime in K{X}_{int}.

(c) Suppose Λ is autoreduced and I(Λ) is prime in K{X}. Then I(Λ) contains a nonzero element that is reduced with respect to Λ if and only if I_{int}(Λ) contains a nonzero element that is internally reduced with respect to Λ.

Proof. Toward a proof of part (a), let F be the set of pairs (f, g) of distinct elements from Λ such that there exists θ_{1}, θ_{2} ∈ Θ with θ_{1}v_{f} = θ_{2}v_{g}. If (f, g) ∈ F, let θ_{f} and θ_{g} be such that θ_{f}v_{f} = θ_{g}v_{g} is of minimal height, say h(f, g). Note that despite the notation both operators θ_{f} and θ_{g} depend on the pairt (f, g).

Suppose that Λ is coherent. By the coherence of Λ, if (f, g) ∈ F then S_{g} (θ_{f}f) − S_{f} (θ_{g}g) ∈ (Λ)_{h(f,g)−1}. It follows that for some V_{f,g} ∈ U and all r ∈ V_{f,g}, S_{g(r)} (θ_{f}f (r))−S_{f(r)} (θ_{g}g (r)) ∈ (Λ_{r})_{h(f,g)−1} in K_{r} {X}. We are using here also the fact that the separant of a Δ-polynomial can be computed co-ordinatewise almost everwhere.

Let V = ⋂_{(f,g)∈F} V_{f,g}. We have already pointed out that internal autoreducedness

extends autoreducedness, so, shrinking V if necessary, we may assume that Λ_{r} is autoreduced for all r ∈ V. Shrinking V further, we may also assume that f and f(r) have the same shape for all f ∈ Λ, and that if f ≠ g in Λ then f(r) ≠ g(r) in Λ_{r}. We now show that for each r ∈ V, Λ_{r} is coherent in K_{r} {X}. Suppose f(r), g(r) ∈ Λ_{r} are distinct and there are θ_{1}, θ_{2} ∈ Θ such that θ_{1}v_{f(r)} = θ_{2}v_{g(r)} is of height h, and that h is minimal such. Since this is a fact just about the shape of f(r) and g(r), it follows that (f, g) ∈ F, θ_{1} = θ_{f}, θ_{2} = θ_{g}, and h = h(f, g). Hence, as r ∈ V_{f,g} we have that S_{g(r)} (θ_{1}f (r)) − S_{f(r)} (θ_{2}g (r)) ∈ (Λ_{r})_{h−1}. This proves that Λ_{r} is coherent. Hence Λ is internally coherent.

For the converse, suppose that Λ is internally coherent. Then Λ is internally autoreduced and hence autoreduced. Suppose (f, g) ∈ F and set P := S_{g} (θ_{f}f) − S_{f} (θ_{g}g). Let {Q_{1}, …, Q_{ℓ}} be Λ together with its derivatives up to height h(f, g)−1. We need to show that P ∈ (Q_{1}, …, Q_{ℓ})K{X}. Let V ∈ U be such that for all r ∈ V, Λ_{r} is coherent, θ_{f}v_{f(r)} = θ_{g}v_{g(r)} with height h(f, g), and this height is minimal such. Shrinking V further we may also assume that {Q_{1}(r), …, Q_{ℓ}(r)} is Λ_{r} together with all its derivatives up to height h(f, g) − 1. By coherence,

P (r) ∈ (Λ_{r})_{h(f,g)−1} = (Q_{1}(r), …, Q_{ℓ}(r)) K_{r} {X}

Hence P ∈ (Q_{1}, …, Q_{ℓ}) K{X}_{int}. But P and the Q_{j}’s are in K{X}, and, by Proposition 4.1, K{X}_{int} is faithfully flat over K{X}. Hence P ∈ (Q_{1}, …, Q_{ℓ})K{X}, as desired.

For part (b), recall first of all that by definition

I(Λ) = {g ∈ K {X} : H_{Λ}^{t}g ∈ (Λ)K{X}, for some t ∈ ℕ}

and

I_{int}(Λ) = {g ∈ K{X}_{int} : (H_{Λ}^{int})^{N} g ∈ (Λ)_{int}, for some N ∈ ℕ^{∗}}

But H_{Λ}^{int} = H_{Λ} since separants and initials of elements in K{X} can be computed co-ordinatewise almost everywhere. Similarly, (Λ)_{int} = (Λ) K{X}_{int} because Λ is finite and hence (Λ) K{X}_{int} is internal with components (Λ_{r})K_{r}{X} where Λ_{r} := {f(r) : f ∈ Λ}. So in fact,

I_{int}(Λ) = {g ∈ K{X}_{int} : H_{Λ}^{N}g ∈ (Λ)K{X}_{int}, for some N ∈ ℕ^{∗}}

It follows that I(Λ) ⊂ I_{int}(Λ), and so I(Λ)K{X}_{int} ⊆ I_{int}(Λ)

For the reverse containment, suppose toward a contradiction that g ∈ I_{int}(Λ) and g ∉ I(Λ)K{X}_{int}. Then H_{Λ}^{N}g ∈ (Λ)K{X}_{int} ⊂ I(Λ)K{X}_{int} for some N ∈ ℕ^{∗}. Since I(Λ) is prime by assumption, Proposition 4.1(a) tells us that I(Λ)K{X}_{int} is also prime. Hence H_{Λ}^{N} ∈ I(Λ)K{X}_{int}. By Proposition 4.1(b), H_{Λ}^{t} ∈ I(Λ) for some t ∈ ℕ. Increasing t if necessary, H_{Λ}^{t} ∈ (Λ). But this means that 1 ∈ I(Λ), contradicting the primality of that ideal. We have shown that I_{int}(Λ) = I(Λ)K{X}_{int}. In particular, by Proposition 4.1(a), I_{int}(Λ) is prime.

We now turn to part (c); Λ is autoreduced and I(Λ) is prime. One direction is straightforward: a nonzero element of I(Λ) reduced with respect to Λ is itself a nonzero element of I_{int}(Λ) internally reduced with respect to Λ. For the converse, let Z = (Z_{i} : i < ω) again enumerate the algebraic indeterminates according to height. Consider the leaders T := {v_{f} : f ∈ Λ} and let Y := {Z_{i} : Z_{i} is not a derivative of any v_{f} ∈ T }. Since Λ is autoreduced, all the algebraic indeterminates appearing in Λ come from Y ∪T. It follows, as is remarked after Lemma 2 of Chapter 4 of [5], that I(Λ) is generated by I := I(Λ) ∩ K[Y, T]. Hence, I_{int}(Λ), which by part (b) is equal to I(Λ)K[Z]_{int}, is in fact equal to IK[Z]_{int}.

Now suppose g ∈ I_{int}(Λ) = IK[Z]_{int} is nonzero and internally reduced with respect to Λ. Let V ∈ U be such that g(r) is reduced with respect to Λ_{r} := {f(r) : f ∈ Λ} for all r ∈ V. In particular, g(r) ∈ K_{r}[Y, T], and so g ∈ K[Y, T]_{int}∩IK[Z]_{int}. But K[Z]_{int} is faithfully flat over K[Y, T]_{int} since, for all r, K_{r}[Z] is faithfully flat over K_{r}[Y, T]. So g ∈ IK[Y, T]_{int}.

For each r ∈ 𝕀, set L_{r} to be the field K_{r}(Y) and let L be the corresponding internal field. Note that L is the fraction field of R := K[Y]_{int} The ultraproduct of the polynomial rings L_{r}[T] gives rise to the ring of internal polynomails L[T]_{int}, which extends L[T] via the usual embedding. Since deg_{v_{f}} (g(r)) < deg_{v_{f}} (f), for all r ∈ V and f ∈ Λ, we have that g ∈ L[T]. But we saw above that g ∈ IK[Y, T]_{int} ⊂ IL[T]_{int}. By the faithful flatness of L[T]_{int} over L[T], IL[T]_{int} ∩ L[T] = IL[T]. So g ∈ IL[T]. Now we can clear denominators: there is h ∈ R = K[Y]_{int} such that f := hg ∈ IR[T]. Note that f is still internally reduced with respect to Λ as we have only multiplied by an internal polynomial in which no derivatives of T appear, co-ordinatewise almost everywhere.

Write f = h_{1}g_{1} +⋯+h_{ℓ}g_{ℓ} where g_{1}, …, g_{ℓ} ∈ I ⊂ K[Y, T] and h_{1}, …, h_{ℓ} ∈ R[T]. Letting (M_{j} : j ∈ J) be the monomials in T that appear in f, the h_{i}’s, g_{i}’s, and h_{i}g_{i}’s, we can write

f = ∑_{j∈J} f_{j}M_{j}
h_{i} = ∑_{j∈J} h_{i,j}M_{j}
g_{i} = ∑_{j∈J} g_{i,j}M_{j}

where f_{j}, h_{i,j} ∈ K[Y]_{int} and g_{i,j} ∈ K[Y]. Let J′ ⊂ J be those indices j such that f_{j} ≠ 0. Then for each j ∈ J′,

f_{j} = ∑_{i=1}^{ℓ} ∑_{M_{j_{1}} M_{j_{2}} =M_{j}} h_{i,j_{1}}g_{i,j_{2}}

and for each j ∈ J \ J′,

0 = ∑_{i=1}^{ℓ} ∑_{M_{j_{1}} M_{j_{2}} =M_{j}} h_{i,j_{1}}g_{i,j_{2}}

That is, the f_{j}’s and h_{i,j}’s are a solution in K[Y]_{int} to the system of linear equations over K[Y] given by

0 = −S_{j} + ∑_{i=1}^{ℓ} ∑_{M_{j_{1}} M_{j_{2}} =M_{j}} g_{i,j_{2}}S_{i,j_{1}}

for j ∈ J′, and

0 = ∑_{i=1}^{ℓ} ∑_{M_{j_{1}} M_{j_{2}} =M_{j}} g_{i,j_{2}}S_{i,j_{1}}

for j ∈ J \ J′. Note that J′ ≠ ∅ as f ≠ 0. By the flatness of K[Y]_{int} over K[Y], our solution is a K[Y]_{int}-linear combination of solutions in K[Y]. In particular, there must exist a solution (f′_{j}, h′_{i,j}) in K[Y]. In fact, we can find such a solution such that for some j ∈ J′, f′_{j} ≠ 0. Hence f′ := ∑_{j∈J′} f′_{j}M_{j} ≠ 0. Moreover, setting h′_{i} := ∑_{j∈J} h′_{i,j}M_{j} ∈ K[Y, T], we get that f′ = h′_{1}g_{1} + ⋯ + h′_{ℓ}g_{ℓ} ∈ I ⊂ I(Λ). Note that as f′ ∈ K[Y, T] and in each T -variable the degree of f′ is no greater than it was in f, f′ is reduced with respect to Λ. We have found a nonzero element of I(Λ) that is reduced with respect to Λ, as desired. □

We can now apply Facts 2.1 and 3.2 to see that characteristic sets for prime Δ-ideals in K{X} can be recognised in K{X}_{int}.

Theorem 4.3. Suppose Λ ⊂ K{X} is finite. Then Λ is a characteristic set for a prime Δ-ideal of K{X} if and only if it is an internally characteristic set for a prime internal Δ-ideal of K{X}_{int}.

Proof. The right-to-left direction we have already mentioned: If Λ is internally characteristic for P ⊂ K{X}_{int} then it is characteristic for P ∩ K{X}. This is because internal autoreducedness and rank in K{X}_{int} restrict to autoreducedness and rank in K{X}. (See the discussion on page 8.)

For the converse, suppose Λ is characteristic for a prime Δ-ideal P ⊂ K{X}. By Fact 2.1, Λ is coherent and I(Λ) is a prime ideal of K{X} containing no nonzero elements reduced with respect to Λ. By Lemma 4.2, Λ is internally coherent in K{X}_{int}, I_{int}(Λ) is prime, and I_{int}(Λ) contains no nonzero element internally reduced with respect to Λ. Hence, by Fact 3.2, Λ is an internally charcateristic set for a prime internal Δ-ideal. □

Recall that for Λ ⊂ K{X}, I[Λ] = {g ∈ K{X} : H_{Λ}^{n}g ∈ [Λ], for some n ∈ ℕ} and I_{int}[Λ] = {g ∈ K{X}_{int} : H_{Λ}^{N}g ∈ [Λ]_{int}, for some N ∈ ℕ^{∗}}. (We are using here again the fact that, since Λ ⊂ K{X}, H_{Λ} = H_{Λ}^{int}.) One would like to prove, analogously to Lemma 4.2(b), that if I[Λ] is prime and Λ is its characteristic set, then I_{int}[Λ] = {I[Λ]}_{int}. But we are not able to do so. In fact, as we will see in the next section (see statement (B) of Proposition 5.5), this would imply the definability of primality conjecture discussed in the introduction. Nevertheless, we can use Theorem 4.3 to show that I_{int}[Λ] is least among the prime internal Δ-ideals that lie above I[Λ].

Corollary 4.4. Suppose Λ ⊂ K{X} is a characteristic set for a prime Δ-ideal. Then I_{int}[Λ] is a prime internal Δ-ideal, I_{int}[Λ] ∩ K{X} = I[Λ], and if P is any prime internal Δ-ideal of K{X}_{int} with P ∩ K{X} = I[Λ] then I_{int}[Λ] ⊂ P.

Proof. By Theorem 4.3, Λ is internally characteristic for a prime internal Δ-ideal of K{X}_{int}, which must therefore be I_{int}[Λ]. It follows that I_{int}[Λ]∩K{X} is prime and that Λ, being minimally ranked among the autoreduced subsets of this ideal, is characteristic for I_{int}[Λ] ∩ K{X}. But then I_{int}[Λ] ∩ K{X} = I[Λ].

Suppose P is a prime internal Δ-ideal of K{X}_{int} with P ∩ K{X} = I[Λ]. Note that H_{Λ} ∉ P else it would be in P ∩ K{X} = I[Λ] forcing the latter to be all of K{X}. Suppose g ∈ I_{int}[Λ] so that H_{Λ}^{N}g ∈ [Λ]_{int} ⊂ P, for some N ∈ ℕ^{∗}. Since H_{Λ} ∉ P, H_{Λ}(r) ∉ P_{r} for almost all r, and so by primality g(r) ∈ P_{r} for almost all r. Hence g ∈ P. So I_{int}[Λ] ⊂ P, as desired. □

Corollary 4.5. Suppose S ⊂ K{X}. Then {S}_{int} ∩ K{X} = {S}.

Proof. If {S} = K{X} then {S}_{int} = K{X}_{int} and we are done. Otherwise {S} is a proper radical Δ-ideal and by the differential prime decomposition theorem there must exist finitely many prime Δ-ideals, P_{1}, …, P_{ℓ} ⊂ K{X}, such that {S} = P_{1} ∩ ⋯ ∩ P_{ℓ}. For each i = 1, …, ℓ, let P_{i} = I[Λ_{i}] where Λ_{i} is characteristic for P_{i}. By Corollary 4.4, each I_{int}[Λ_{i}] is a prime internal Δ-ideal and I_{int}[Λ_{i}]∩K{X} = P_{i}. In particular, I_{int}[Λ_{1}] ∩ ⋯ ∩ I_{int}[Λ_{ℓ}] is a radical internal Δ-ideal of K{X}_{int} that contains S. It follows that {S}_{int} ⊂ I_{int}[Λ_{1}] ∩ ⋯ ∩ I_{int}[Λ_{ℓ}]. So, working in K{X},

{S} ⊂ {S}_{int} ∩ K{X}
⊂ (I_{int}[Λ_{1}] ∩ ⋯ ∩ I_{int}[Λ_{ℓ}]) ∩ K{X}
= (I_{int}[Λ_{1}] ∩ K{X}) ∩ ⋯ ∩ (I_{int}[Λ_{ℓ}] ∩ K{X})
= P_{1} ∩ ⋯ ∩ P_{ℓ}
= {S}

which proves that {S}_{int} ∩ K{X} = {S}. □

Remark 4.6. We do not know if [S]_{int} ∩ K{X} = [S] for all finite sets S ⊂ K{X}. Since our proof of Corollary 4.5 goes via prime Δ-ideals it does not help. One might hope to imitate what happens in the algebraic setting, where (S)_{int} ∩ K{X} = (S) follows by faithful flatness from the fact that (S)_{int} = (S)K{X}_{int}. The latter holds because if g ∈ (S)_{int} then for almost all r we have g(r) = ∑_{f∈S} g_{f,r}f(r) where the g_{f,r} are in K_{r}{X}, and hence g = ∑_{f∈S} g_{f}f where g_{f} is chosen so that g_{f}(r) = g_{f,r} almost everywhere. But this argument cannot be extended to Δ-ideals; it is not necessarily the case that [S]_{int} is the Δ-ideal of K{X}_{int} generated by S. For a counterexample consider the case when Δ is a single derivation δ, X is a single variable, and 𝕀 = ω. The internal δ-ideal generated by the variable X in K{X}_{int} clearly contains the internal δ-polynomial δ^{ω}X whose rth co-ordinate is δ^{r}X. But δ^{ω}X is not in the δ-ideal generated by X in K{X}_{int} since the latter is the ideal generated by the set {δ^{m}X : m < ω}. Note that this counterexample is radical (indeed prime), so that even passing to radicals does not avoid the problem.

5. Definability of primality and related problems

Throughout this section all nonstandard notions are with respect to a fixed nonprincipal ultrafilter U on ω. Also, we continue to work with m commuting derivations Δ = {δ_{1}, …, δ_{m}} in n differential indeterminates X = (X_{1}, …, X_{n}).

The original motivation for this work was to apply nonstandard methods to the problem of the existence of uniform bounds in checking if the radical Δ-ideal generated by a given finite set of Δ-polynomials is prime. This is the definability of primality problem discussed in the introduction (Conjecture 1.1). The algebraic analogue of Conjecture 1.1 was proved using nonstandard methods by van den Dries and Schmidt [7], and we have tried here to extend their approach to the differential setting. The following translates definability of primality into a statement about rings of internal Δ-polynomials.

Proposition 5.1 (Nonstandard formulation of definability of primality). Conjecture 1.1 of the introduction is equivalent to the following statement:

(A) For any internal Δ-field K and internal S ⊂ K{X}, if {S}_{int} ∩ K{X} is prime in K{X} then {S}_{int} is prime in K{X}_{int}.

Proof. If the conjecture fails then there exists a d < ω, and for every r < ω a Δ-field K_{r} with a finite set S_{r} ⊂ K_{r}{X} of order and degree ≤ d such that {S_{r}} is not prime, but it is proper and for all f, g ∈ K_{r}{X} of degree and order ≤ r, if fg ∈ {S_{r}} then either f or g is in {S}. Passing to the ultraproduct we obtain an internal Δ-field K whose components are K_{r} and an internal set S ⊂ K{X}_{int} whose components are S_{r}. Since the degrees and orders of the elements of S_{r} were bounded independently of r, S is in fact a subset of K{X}. Since the {S_{r}} were not prime, {S}_{int} is not prime. On the other hand, {S}_{int} ∩ K{X} is prime. Indeed, it is proper since each {S_{r}} was proper and hence {S}_{int} omits 1 ∈ K{X}. Moreover, if f, g ∈ K{X} with fg ∈ {S}_{int}, then for almost all r, f(r), g(r) ∈ K_{r}{X} are of degree and order ≤ r (as they are almost everywhere equal to that of f and g), and f(r)g(r) ∈ {S_{r}}, and hence one of f(r) and g(r) is in {S_{r}}. Depending on which of these is favoured by the ultrafilter, we get that either f or g is in {S}_{int}. We have shown that {S}_{int} ∩ K{X} is prime but {S}_{int} is not. That is, statement (A) is false.

Conversely, suppose Conjecture 1.1 holds, K is an internal Δ-field, and S ⊂ K{X} is an internal set. Let (S_{r} : r < ω) be a family of components for S. The fact that S ⊂ K{X} means that for some V ∈ U there is a bound on the orders and degrees of the elements of S_{r} for all r ∈ V, that is independent of r. Let d be this bound and let N = r(d, n, m) be given by Conjecture 1.1. Now suppose that {S}_{int} is not prime. We show that {S}_{int} ∩ K{X} cannot be prime, thereby verifying the contrapositive of (A). Shrinking V if necessary, {S_{r}} is not prime for all r ∈ V. Hence there is f_{r}, g_{r} ∈ K_{r}{X} of degree and order ≤ N witnessing the nonprimality of {S_{r}}. (Note that while S_{r} need not be finite, there exists finite T_{r} ⊂ S_{r} with {S_{r}} = {T_{r}} by the Ritt-Raudenbush basis theorem, and hence Conjecture 1.1 applies.) Let f, g ∈ K{X}_{int} be such that f(r) = f_{r} and g(r) = g_{r} almost everywhere. Then, as the degrees and orders are bounded, we have that f, g ∈ K{X}. Moreover, f, g witness the nonprimality of {S}_{int}. That is, {S}_{int} ∩ K{X} is not prime. □

Remark 5.2. The above proposition remains true even if we change statement (A) to consider only finite subsets S ⊂ K{X}. Indeed, when we were proving above that a counterexample to Conjecture 1.1 leads to a counterexample to (A), we could have taken the S_{r} to be of bounded size independently of r without changing {S_{r}}. This is because the Δ-polynomials in K_{r}{X} of order and degree bounded by d form a K_{r}-vector space whose (finite) dimension depends only on d (not on r). Choosing the S_{r} to be of uniformly bounded size would then have lead to a finite counterexample S.

Unfortunately, the results we obtained in the last section only go part way toward proving statement (A). The proof of the following weak form of (A) illustrates what goes wrong.

Proposition 5.3. Suppose K is an internal Δ-field and S ⊂ K{X} is such that {S}_{int} ⊊ K{X}_{int} satisfies: for all f ∈ K{X} and g ∈ K{X}_{int}, if fg ∈ {S}_{int} then f ∈ {S}_{int} or g ∈ {S}_{int}. Then {S}_{int} is prime.

Proof. Note that our assumption on {S}_{int} implies that {S}_{int} ∩ K{X} is prime.^{1} Theorem 4.3 tells us that if Λ is a characteristic for {S}_{int} ∩ K{X} then I_{int}[Λ] is prime. We will show that {S}_{int} = I_{int}[Λ]. Since I_{int}[Λ] contains I[Λ] = {S}_{int} ∩ K{X} ⊃ S, we have {S}_{int} ⊂ I_{int}[Λ]. For the reverse containment, suppose g ∈ I_{int}[Λ]. Then H_{Λ}^{N}g ∈ [Λ]_{int} ⊂ {S}_{int} for some N ∈ ℕ^{∗}. It follows that (H_{Λ}g)^{N} ∈ {S}_{int}. Since {S}_{int} is componentwise radical almost everywhere, H_{Λ}g ∈ {S}_{int}. Now H_{Λ} ∉ {S}_{int}, else it would be in I[Λ] and the latter would then not be proper.

1We know by Corollary 4.5 that {S}_{int} ∩ K{X} = {S}, but we don’t use this fact here.

Since H_{Λ} ∈ K{X}, our assumption on {S}_{int} implies that g ∈ {S}_{int}, as desired. □

We leave it to the reader to deduce from the above proposition the following standard consequence which bounds one of the two universal quantifiers in the definition of primality.

Theorem 5.4. For every d there exists r = r(d, n, m) such that for every Δ-field k and and every finite set of Δ-polynomials S ⊂ k{X} of degree and order ≤ d, the following are equivalent:

(i) {S} is prime (ii) {S} is proper and for all f, g ∈ k{X} with f of degree and order ≤ r, if

fg ∈ {S} then either f or g is in {S}.

Now we turn our attention away from trying to prove definability of primality, and instead toward proving that it is equivalent to other existence-of-bounds problems in differential algebra. In this we are informed by [2] where Golubitsky, Kondratieva, and Ovchinnikov show, under some natural computability-theoretic assumptions on the base Δ-field^{2}, the equivalence of several computational problems in differential algebra. We are interested in the existence-of-bounds analogues of some of their existence-of-algorithm problems.

Proposition 5.5. Statement (A) of Proposition 5.1 is equivalent to each of the following statements: For any internal Δ-field K,

(B) If P ⊂ K{X}_{int} is a prime internal Δ-ideal with an internally characteristic

set from K{X} then P = {S}_{int} for some internal S ⊂ K{X}. (C) Suppose P, Q ⊂ K{X}_{int} are prime internal Δ-ideals with internally char-

acteristic sets from K{X}. If P ∩ K{X} ⊂ Q then P ⊂ Q. (D) Suppose S ⊂ K{X} is internal and P, Q ⊂ K{X}_{int} are minimal prime

internal Δ-ideals containing S. If P ∩ K{X} ⊂ Q then P = Q. (E) If S ⊂ K{X} is internal and f ∈ K{X} is not a zero divisor in K{X}/{S}

then f is not a zero divisor in K{X}_{int}/{S}_{int}.

Proof. Suppose (A) holds and let Λ ⊂ K{X} be internally characteristic for a prime internal Δ-ideal P. Then P = I_{int}[Λ], and by Theorem 4.3, Λ is characteristic for the prime Δ-ideal I[Λ] of K{X}. Let S ⊂ K{X} be finite so that I[Λ] = {S}. By Corollary 4.4, P is least among the prime internal Δ-ideals that lie above {S}. By Corollary 4.5, {S}_{int} ∩ K{X} = {S}, and by (A), {S}_{int} is prime. Hence P ⊂ {S}_{int}. The reverse containment is clear. This proves (B).

That (B) implies (C) is immediate.

Note that (D) does not follow tautologically from (C), because the prime internal Δ-ideals P and Q appearing in (D) are not assumed to have internally characteristic sets from K{X}. However, by the following lemma, P and Q do in fact have internally characteristic sets from K{X}, and so (C) does imply (D).

Lemma 5.6. If S ⊂ K{X} and P ⊂ K{X}_{int} is a minimal prime internal Δ-ideal containing S, then P has an internally characteristic set from K{X}.

2Namely that k is a computable Δ-field and that there is an algorithm for determining if a univariate polynomial over k is irreducible.

Proof of Lemma 5.6. Consider the prime Δ-ideal Q := P ∩ K{X}, and let Λ ⊂ K{X} be a characteristic set for Q. By Theorem 4.3, Λ is internally characteristic for the prime internal Δ-ideal I_{int}[Λ]. We show that P = I_{int}[Λ]. By Corollary 4.4, I_{int}[Λ] is least among the prime internal Δ-ideals of K{X}_{int} whose intersection with K{X} is Q. Hence I_{int}[Λ] ⊂ P. On the other hand, S ⊂ P ∩ K{X} = Q ⊂ I_{int}[Λ]. So by the minimality of P, P = I_{int}[Λ], as desired. □

In order to prove that (D) implies (E), we first show, unconditionally, that if S ⊂ K{X} is internal and Λ ⊂ K{X} is characteristic for a minimal prime Δ-ideal containing S, then I_{int}[Λ] is a minimal prime internal Δ-ideal of K{X}_{int} containing S. Indeed, by Theorem 4.3, I_{int}[Λ] is a prime internal Δ-ideal containing S, and hence by transfer from the standard setting, there exists P ⊂ I_{int}[Λ] minimal such. But then, by Lemma 5.6, P = I_{int}[Σ] where Σ ⊂ K{X} is internally characteristic for P. Intersecting with K{X}, we get S ⊂ I[Σ] ⊂ I[Λ], and hence I[Σ] = I[Λ] by minimality. Therefore P = I_{int}[Σ] = I_{int}[Λ], as desired.

Now we show that (D) implies:

(D′) If Q ⊂ K{X}_{int} is a minimal prime internal Δ-ideal containing S, then Q ∩ K{X} is a minimal prime Δ-ideal of K{X} containing S.

Indeed, let Q′ ⊂ Q ∩ K{X} be a minimal prime Δ-ideal containing S. Let Λ ⊂ K{X} be characteristic for Q′, so that Q′ = I[Λ]. Then, by the previous paragraph, P := I_{int}[Λ] is another minimal prime internal Δ-ideal of K{X}_{int} containing S. As P ∩ K{X} = I[Λ] ⊂ Q, (D) implies that P = Q. So, Q ∩ K{X} = I[Λ] = Q′

We are ready to prove that (D) implies (E). We use the following characterisation of zero divisors that comes from the prime decomposition theorem (see, for example, Lemma 1 of [2]): f ∈ K{X} is a zero divisor modulo {S} if an only if f belongs to one of, but not all of, the minimal prime Δ-ideals of K{X} that contain S. Working componentwise almost everywhere we also have: f ∈ K{X}_{int} is a zero divisor in K{X}_{int}/{S}_{int} if an only if f belongs to one of, but not all of, the minimal prime internal Δ-ideals of K{X}_{int} that contain S. Now, toward a proof of the contrapositive of (E), suppose that f ∈ K{X} is a zero divisor in K{X}_{int}/{S}_{int}, and let P and Q be minimal prime internal Δ-ideals containing S such that f ∈ P \ Q. But then f ∈ (P ∩ K{X}) \ (Q ∩ K{X}). As P ∩ K{X} and Q ∩ K{X} are minimal prime internal Δ-ideals containing S by (D′), it follows that f is a zero divisor of K{X}/{S}.

Finally, we show that (E) implies (A). Assuming (E), suppose that S ⊂ K{X} is an internal set such that {S}_{int} is not prime in K{X}_{int}. We need to prove that {S}_{int}∩K{X} is not prime in K{X}. By Corollary 4.5, {S}_{int}∩K{X} = {S}. Now by Proposition 5.3, the fact that {S}_{int} is not prime is witnessed by some f ∈ K{X} and g ∈ K{X}_{int} neither of which are in {S}_{int} but such that fg ∈ {S}_{int}. That is, f is a zero divisor in K{X}_{int}/{S}_{int}. As f ∈ K{X}, (E) implies that f is a zero divisor in K{X}/{S}. Hence {S} is not prime in K{X}, as desired. □

Theorem 5.7. The following statements in differential algebra are equivalent:

(1) Definability of primality. Conjecture 1.1.

(2) Bounds for generators of a prime Δ-ideal given a characteristic set. For every d there exists r = r(d, n, m) such that for every Δ-field k, if P is a prime Δ-ideal of k{X} with a characteristic set whose elements are of degree and order ≤ d, then P is radically differentially generated by Δ-polynomials of order and degree ≤ r.

(3) Bounds for checking ⊂ among prime Δ-ideals given characteristic sets. For every d there exists r = r(d, n, m) such that for every Δ-field k and all prime Δ-ideals P, Q ⊂ k{X} with characteristic sets whose elements are of degree and order ≤ d, if every Δ-polynomial in P of degree and order ≤ r is in Q then P ⊂ Q.

(4) Bounds for distinguishing minimal prime Δ-ideals.

For every d there exists r = r(d, n, m) such that for every Δ-field k, every set S ⊂ k{X} of Δ-polynomials of degree and order ≤ d, and every pair P and Q of minimal prime Δ-ideals containing S, if every Δ-polynomial in P of degree and order ≤ r is in Q then P = Q.

(5) Definability of zero-divisibility.

For every d there exists r = r(d, n, m) such that for every Δ-field k, every set S ⊂ k{X} of Δ-polynomials of degree and order ≤ d, and every g ∈ k{X} of degree and order ≤ d, if gf ∉ {S} for all f ∉ {S} of degree and order ≤ r, then g is not a zero divisor modulo {S}.

Proof. These statements are just standard formulations of the corresponding statements (A) through (E) of Proposition 5.5. The equivalence of (A) and (1) is Proposition 5.1, and very similar arguments yield the equivalence of (B) to (2), (C) to (3), (D) to (4), and (E) to (5). The theorem then follows immediately from Proposition 5.5. □

Remark 5.8. The existence-of-algorithms analogue of (3) would say that there is an algorithm for deciding whether one prime Δ-ideal is contained in another given their characteristic sets. This is Kolchin’s Problem 3 of §IV.9 of [5], a solution to which would solve the Ritt problem of computing the prime components of the radical Δ-ideal generated by a given finite set of Δ-polynomials.

6. Two standard consequences

We conclude by extracting the existence of some bounds in the theory of Δpolynomial rings from our understanding of the ring of internal Δ-polynomials.

Throughout Δ = {δ_{1}, …, δ_{m}} and X = (X_{1}, …, X_{n}).

6.1. Characteristic sets for minimal prime Δ-ideals. Given a finite set of Δpolynomials S, consider the problem of finding the minimal prime Δ-ideals that contain S. In constructive differential algebra there has been significant work on bounds in differential elimination algorithms from which it seems that explicit bounds on characteristic sets for the minimal prime Δ-ideals containing S should be deducible. We have in mind [1] and [3]. Here we show the existence of such bounds as an immediate consequence of our study of K{X}_{int}.

Theorem 6.1. Suppose d ∈ ℕ. There is r = r(d, n, m) ∈ ℕ such that for every Δ-field k and every finite set of Δ-polynomials S ⊂ k{X} of degree and order ≤ d, each minimal prime Δ-ideal containing S has a characteristic set of Δ-polynomials of degree and order ≤ r.

Proof. Suppose not. Then for each r ∈ ℕ there is a Δ-field K_{r}, a finite set S_{r} ⊂ K_{r}{X} of Δ-polynomials of degree and order bounded by d, and a minimal prime Δ-ideal P_{r} ⊂ K_{r}{X} containing S_{r} all of whose characteristic sets contain at least one element of either degree or order strictly bigger than r.

Fix a non-principal ultrafilter U on ω, and work in the ultraproduct K{X}_{int}. Let S ⊂ K{X}_{int} be the internal set with components S_{r}, and let P ⊂ K{X}_{int} be the prime internal Δ-ideal with components P_{r}. Then P is a minimal prime internal Δ-ideal containing S. As the degrees and orders of the elements of S_{r} were bounded independently of r, we actually have that S ⊂ K{X}. By Lemma 5.6, P has an internally characteristic set from K{X}, say Λ ⊂ K{X}. It follows that for almost all r, Λ_{r} := {f(r) : f ∈ Λ} is characteristic for P_{r}. Since for f ∈ K{X}, f and f(r) have the same shape, if t is the maximum of the degrees and orders of the elements of Λ, then t is also the maximum of the degrees and orders of the elements of Λ_{r}. Letting r ≥ t, this contradicts the fact that P_{r} has no characteristic set bounded by r in this way. □

When {S} itself is prime we get from the above theorem the existence of a bound for a characteristic set of {S}. In this case an explicit bound (at least for orders) is given by Lemma 14 of [3].

Corollary 6.2. There is r = r(d, n, m) ∈ ℕ such that for every Δ-field k and every prime Δ-ideal P = {S}, where S is a finite set of Δ-polynomials of degree and order ≤ d, P has a characteristic set of Δ-polynomials of degree and order ≤ r.

6.2. Differential Nullstellensatz. Consider finally the problem of determining if a Δ-polynomial g is in the radical Δ-ideal generated by a finite set of Δpolynomials S. An explicit bound on how many derivatives one has to apply to S to witness this membership, depending only on the orders and degrees of the elements of S ∪ {g}, was found in [3]. Again, the mere existence of such a bound can be seen as an immediate corollary of our study of K{X}_{int}, as we now point out. Another proof of the existence of a bound, also using ultraproducts (though of differentially closed fields), was given by Singer (cf. §6 of [3]). However Singer’s bound depends also on the size of S.

Theorem 6.3. Suppose d ∈ ℕ. There is r = r(d, n, m) ∈ ℕ such that for every Δ-field k and every finite set of Δ-polynomials S ⊂ k{X} of degree and order ≤ d, the following holds:

if g ∈ {S} is of order and degree ≤ d then g^{r} ∈ (θf | f ∈ S, θ ∈ Θ, ord θ ≤ r).

Proof. Suppose not. Then for each r ∈ ℕ there is a Δ-field K_{r}, a finite set S_{r} ⊂ K_{r}{X}, and g_{r} ∈ {S_{r}}, such that every element of S_{r} ∪ {g_{r}} is of degree and order bounded by d, and g_{r}^{r} ∉ (θf | f ∈ S_{r}, θ ∈ Θ, ord θ ≤ r). Let S ⊂ K{X}_{int} be the internal set with components S_{r}, and g ∈ K{X}_{int} the internal Δ-polynomial with co-ordinates g_{r}. Then g ∈ {S}_{int}. Since the order and degrees of the components were bounded, we have S ⊂ K{X} and g ∈ K{X}. Hence g ∈ {S}_{int} ∩ K{X} = {S} by Corollary 4.5. It follows that for some f_{1}, …, f_{ℓ} ∈ S and some t ∈ ℕ, g^{t} ∈ (θf_{i} | 1 ≤ i ≤ ℓ, θ ∈ Θ, ord(θ) ≤ t)K{X}. So for almost all r ∈ ℕ, g_{r}^{t} ∈ (θf_{i}(r) | 1 ≤ i ≤ ℓ, θ ∈ Θ, ord(θ) ≤ t)K_{r}{X}. Since f_{i}(r) ∈ S_{r}, we have g_{r}^{t} ∈ (θf | f ∈ S_{r}, θ ∈ Θ, ord θ ≤ t), for almost all r. But taking r ≥ t, this contradicts the fact that g_{r}^{r} ∉ (θf | f ∈ S_{r}, θ ∈ Θ, ord θ ≤ r)K_{r}{X}. □

References

[1] O. Golubitsky, M. Kondratieva, M. Moreno Maza, and A. Ovchinnikov. A bound for Rosenfeld-Groebner algorithm. Journal of Symbolic Computation, 43(8):582–610, 2008.

[2] O. Golubitsky, M. Kondratieva, and A. Ovchinnikov. On the generalized Ritt problem as a computational problem. Fundamental′naya i Prikladnaya Matematika, 14(4):109–120, 2008.

[3] O. Golubitsky, M. Kondratieva, A. Ovchinnikov, and A. Szanto. A bound for orders in differential Nullstellensatz. Journal of Algebra, 322(11):3852–3877, 2009.

[4] G. Hermann. Die Frage der endlich vielen Schritte in der Theorie der Polynomideale. Mathematische Annalen, 95(1):736–788, 1926.

[5] E. R. Kolchin. Differential algebra and algebraic groups. Academic Press, New York, 1973. Pure and Applied Mathematics, Vol. 54.

[6] A. Seidenberg. Constructions in algebra. Transactions of the American Mathematical Society, 197:273–313, 1974.

[7] L. van den Dries and K. Schmidt. Bounds in the theory of polynomial rings over fields. A nonstandard approach. Inventiones Mathematicae, 76:77–91, 1984.

[8] L. van den Dries and A. J. Wilkie. Gromov’s theorem on groups of polynomial growth and elementary logic. Journal of Algebra, 89(2):349–374, 1984.

Department of Pure Mathematics, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1