Hilbert-type dimension polynomials of difference field extensions, difference modules and prime difference ideals play the same role in difference algebra as Hilbert and Hilbert-Samuel polynomials play in commutative algebra and algebraic geometry. In particular, a system of algebraic difference equations can be characterized by its associated difference dimension polynomials; these polynomials are of primary 1 3 importance for the problem of equivalence of such systems and for the comparative analysis of systems of algebraic difference equations arisen from systems of PDEs. Univariate difference dimension polynomials introduced in [6] and [7] characterize difference modules and difference field extensions in the same way as Hilbert polynomials characterize the corresponding structures in commutative algebra and algebraic geometry. A similar concept of differential dimension polynomial introduced in [3] plays an important role in the study of finitely generated differential field extensions, differential modules and algebras. An important property of dimension polynomials is the fact that they carry certain invariants of the corresponding difference or differential algebraic structure, that is, elements which do not depend on the choice of the system of its generators. The above mentioned results were generalized to the case of an arbitrary partition of the basic set of operators (derivations or/and translations) and the corresponding multivariate filtrations of difference (as well as differential) modules and field extensions, see [10,11], and [12]. It was shown that multivariate dimension polynomials whose existence was proved in these papers carry more invariants of the corresponding difference or differential algebraic structures than their univariate counterparts. The following theorem proved in [9, Section 4.2] presents a multivariate dimension polynomial of a finitely generated difference field extension associated with a partition of the basic set of translations.
Theorem 1.1 Let K be a difference field of characteristic zero with a basic set = { 1 , … , m } , that is, a field considered together with the action of elements as mutually commuting endomorphisms of the field (they are called translations). Let T be the free commutative semigroup generated by and let a partition of the set into a disjoint union of its subsets be fixed:
where p ∈ ℕ . Let Card i = m i and for any =
Furthermore, let T(r 1 , … , r p ) = { ∈ T | ord 1 ≤ r 1 , … , ord p ≤ r p } for any r 1 , … , r p ∈ ℕ.
Let L = K⟨ 1 , … , s ⟩ be a difference (with respect to ) field extension of K gen- erated by a finite set = { 1 , … , n } . (As a field, L = K({ ( i ) | ∈ T, 1 ≤ i ≤ n}) .) Then there exists a polynomial |K (t 1 , … , t p ) in p variables with rational coeffi- cients such that (i) |K (r 1 , … , r p ) = trdeg K K({ j | ∈ T(r 1 , … , r p ), 1 ≤ j ≤ n}) for all suf- ficiently large (r 1 , … , r p ) ∈ ℕ p (that is, there exist r (0) 1 , … , r (0) p ∈ ℕ such that the equality holds for all (r 1 , … , r p ) with r i ≥ r (0) i , 1 ≤ i ≤ p).
(1.1)
Generalized characteristic sets and new multivariate… (ii) deg t i |K ≤ m i and the polynomial |K (t 1 , … , t p ) can be represented as where a i 1 …i p ∈ ℤ for all i 1 , … , i p .
(iii) For any permutation (j 1 , … , j p ) of the set {1, … , p} , let < j 1 ,…,j p denote the lexicographic order on ℕ p such that (r 1 , … , r p ) < j 1 ,…,j p (s 1 , … , s p ) if and only if either r j 1 < s j 1 or there exists k ∈ ℕ , 1 < k ≤ p , such that r j = s j for = 1, … , k -1 and r j k < s j k . Let E |K = {(i 1 , … , i p ) ∈ ℕ p | 0 ≤ i k ≤ m k for k = 1, … , p and a i 1 …i p ≠ 0} and let E � |K denote the set of all e ∈ E |K that are maximal elements of E |K with respect to one of the p! orders < j 1 ,…,j p . Then d = deg |K , a m 1 …m p , p-tuples (j 1 , … , j p ) ∈ E � |K , the corresponding coefficients a j 1 …j p , and the coefficients of the terms of total degree d do not depend on the choice of the system of -generators of L over K. Furthermore, a m 1 …m p = -tr.deg K L where -tr.deg K L denoted the maximal number of elements 1 , … , k ∈ L such that the set { i | ∈ T, 1 ≤ i ≤ k} is algebraically independent over K.
The polynomial |K is called the -dimension polynomial of L/K associated with the set of -generators = { 1 , … , n } and partition (1.1). (If p = 1 , the last theorem gives a "standard" univariate difference dimension polynomial introduced in [6].) Theorem 1.1 allows one to assign dimension polynomials to prime difference ideals of finitely generated difference algebras over difference fields (these are dimension polynomials of the quotient fields of the corresponding factor rings). Using properties of difference dimension polynomials, one can efficiently study Krull-type dimension of difference rings, local difference algebras, and extensions of difference fields (see, for example, [5,Chapter 7], [9,Chapter 4], and [15]). Furthermore, as it is shown in [16] and [9,Chapter 7], the dimension polynomial of a differential or difference polynomial ideal generated by a system of partial differential or, respectively, difference equations expresses Einstein's strength of the system, its important qualitative characteristic introduced in [2]. (See [9,Section 7.7] for the description of the relationship between difference dimension polynomials and Einstein's strength of systems of equations in finite differences. The discussion of this relationship in the multivariate case associated with a fixed partition of the set of translations can be found in [8].)
In this paper we introduce a reduction of difference polynomials associated with a fixed partition of the set of basic translations. This reduction takes into account the effective orders of difference polynomials with respect to the elements of the partition (we generalize the concept of the effective order of an ordinary difference polynomial defined in [1, Chapter 2, Section 4]). We consider a new type of characteristic sets that are associated with this reduction and use their properties to prove the existence of a multivariate dimension polynomial of a finitely generated difference field extension that describes the transcendence degrees of intermediate fields
obtained by adjoining transforms of the generators whose orders with respect to the elements of the given partitions lie between two given natural numbers. This dimension polynomial is a polynomial in 2p variables where p is the number of subsets in the partition of the basic set of translations. We determine invariants of such polynomials, that is, numerical characteristics of the extension that are carried by any its dimension polynomial and that do not depend on the system of difference generators the polynomial is associated with. Furthermore, we show (see Examples 2 and 3 in section 4) that the introduced multivariate difference dimension polynomials carry essentially more invariants of the corresponding difference field extensions than any previously known difference dimension polynomials, including such polynomials defined in Theorem 1.1 and bivariate difference dimension polynomials introduced in [13] (the corresponding bivariate difference dimension polynomials for finitely generated difference modules are defined in [14]). Given a finitely generated difference field extension, the latter dimension polynomial describes the transcendence degrees of intermediate fields obtained by adjoining transforms of the generators whose (total) orders lie between two natural numbers. By considering a partition of the basic set of translations, generalizing the concept of effective order of a difference polynomial and developing the corresponding method of characteristic sets, we obtain much stronger results than those of [13]. The fact that the multivariate difference dimension polynomial introduced in this paper carries extra invariants of the corresponding difference field extension allows one to apply our results to the equivalence problem for systems of algebraic difference equations. At the end of section 4, we give an example where we use the introduced dimension polynomials to show that two algebraic difference equations are not equivalent even though their invariants carried by the associated univariate and bivariate dimension polynomials defined in [13] coincide.
Throughout the paper, ℕ , ℤ , and ℚ denote the sets of all non-negative integers, integers, and rational numbers, respectively. For any positive integer m, ≤ P will denote the product order on ℕ m , that is, a partial order such that
By a ring we always mean an associative ring with unity. Every ring homomorphism is unitary (maps unity to unity), every subring of a ring contains the unity of the ring, and every algebra over a commutative ring is unitary. Every field considered in this paper is supposed to have zero characteristic. ℚ[t 1 , … , t p ] will denote the ring of polynomials in variables t 1 , … , t p over ℚ.
By a difference ring we mean a commutative ring R considered together with a finite set = { 1 , … , m } of mutually commuting injective endomorphisms of R called translations. The set is called the basic set of the difference ring R, which is also called a -ring. If R is a field, it is called a difference field or a -field. (We will often use prefix -instead of the adjective "difference".) 1 3
In what follows T denotes the free commutative semigroup generated by the set , that is, the semigroup of all power products =
. Furthermore, we fix representation (1.1) of the set as the union of p disjoint subsets 1 , … , p ( p ≥ 1 ): where
A subring (ideal) R 0 of a -ring R is said to be a difference (or -) subring of R (respectively, a difference (or -) ideal of R) if R 0 is closed with respect to the action of any operator in . In this case the restriction of a mapping i ∈ to R 0 is denoted by the same symbol i . If a prime ideal P of R is closed with respect to the action of , it is called a prime difference (or -) ideal of R.
If L is a -field and K a subfield of L which is also a -subring of L, then K is said to be a -subfield of L; L, in turn, is called a difference (or -) field extension or a -overfield of K (we also say that we have a -field extension L/K). In this case, if S ⊆ L , then the intersection of all -subfields of L containing K and S is the unique -subfield of L containing K and S and contained in every -subfield of L containing K and S. It is denoted by K⟨S⟩ . If S is finite, S = { 1 , … , n } , then we say that L is a finitely generated -field extension of K with the set of -generators { 1 , … , n } and write L = K⟨ 1 , … , n ⟩ . Clearly, this field coincides with the field K({ i | ∈ T, 1 ≤ i ≤ n} ). (Here and below we often write for ( ) where ∈ T , ∈ R.)
If R is a -ring and F ⊆ R , then the intersection of all -ideals of R containing F is, obviously, the smallest -ideal of R containing F. This ideal is denoted by [F]; as an ideal, it is generated by all elements f where ∈ T , f ∈ F . If the set F is finite, F = {f 1 , … , f k } , we say that the -ideal I = [F] is finitely generated, write I = [f 1 , … , f k ] and call elements of F difference (or -) generators of I. A -ideal I of R is said to be reflexive if for any ∈ , the inclusion (a) ∈ I implies a ∈ I (there- fore, for any ∈ T , the inclusion (a) ∈ I implies a ∈ I).
If R is a -ring, then an expression of the form ∑ ∈T a , where a ∈ R for any ∈ T and only finitely many elements a are different from 0, is called a -opera- tor over R. It is an endomorphism of the additive group of R
∑ ∈T b are con- sidered to be equal if and only if a = b for any ∈ T . The set of all -operators over R will be denoted by R . This set, which has a natural structure of an R-module generated by T, becomes a ring if one sets a = (a) for any a ∈ R , ∈ T and extends this rule to the multiplication of any two -operators by distributivity. The resulting ring R is called the ring of -operators over R.
Let R and S be two difference rings with the same basic set , so that elements of act on each of the rings as pairwise commuting endomorphisms. (More rigorously, we assume that there exist injective mappings of into the sets of endomorphisms of the rings R and S such that the images of any two elements of commute. For convenience we will denote these images by the same symbols). A ring homomorphism ∶ R ⟶ S is called a difference (or -) homomorphism if ( a) = (a) for any ∈ , a ∈ R . The notions of -epimorphism, -monomor- phism and -isomorphism are defined accordingly.
If K is a difference ( -) field and Y = {y 1 , … , y n } is a finite set of symbols, then one can consider a countable set of symbols TY = { y j | ∈ T, 1 ≤ j ≤ n} and the polynomial ring R = K[{ y j | ∈ T, 1 ≤ j ≤ n}] in the set of indeterminates TY over K. This polynomial ring is naturally viewed as a -ring where ( � y j ) = ( � )y j for any , � ∈ T , 1 ≤ j ≤ n , and the elements of act on the coefficients of the polyno- mials of R as they act in the field K. The ring R is called the ring of difference (or -) polynomials in the set of difference ( -) indeterminates y 1 , … , y n over K. This ring is denoted by K{y 1 , … , y n } and its elements are called difference (or -) polynomi- als. A -polynomial is called linear if it is linear as a polynomial in the variables y i
a for any a ∈ K and y i ↦ i ), then P = Ker is a prime reflexive -ideal of R called the defining ideal of the extension L/K. In this case, L is isomorphic to the -field qf (R∕P) , the quotient field of R/P ( i ↔ y i + P).
Let K be a -field and U a family of elements of some -overfield of K. We say that the family U is -algebraically dependent over K, if the family TU = { u | ∈ T, u ∈ U} is algebraically dependent over K (that is, there exist ele- ments u 1 , … , u k ∈ TU and a nonzero polynomial f in k variables with coefficients in K such that f (u 1 , … , u k ) = 0 ). Otherwise, the family U is said to be -algebraically independent over K.
If L is a -overfield of a -field K, then a set B ⊆ L is said to be a -transcendence basis of L over K if B is -algebraically independent over K and every element a ∈ L is -algebraic over K⟨B⟩ (it means that the set { a | ∈ T} is algebraically depend- ent over the field K⟨B⟩ ). If L is a finitely generated -field extension of K, then all -transcendence bases of L over K are finite and have the same number of elements (see [9,Proposition 4.1.6]). This number is called the -transcendence degree of L over K (or the -transcendence degree of the extension L/K); it is denoted by -tr.deg K L.
It is clear that every polynomial with integer coefficients is numerical. As an example of a numerical polynomial in p variables with non-integer coefficients ( p ∈ ℕ, p ≥ 1 ) one can consider a polynomial ∏ p i=1
The following theorem proved in [5, Chapter 2] gives the "canonical" representation of a numerical polynomial in several variables. In what follows (until the end of the section), we deal with subsets of the set ℕ m (m is a positive integer). Furthermore, we fix a partition of the set ℕ m = {1, … , m} into p disjoint subsets ( p ≥ 1):
where
The following theorem proved in [5, Chapter 2] generalizes the well-known Kolchin's result on the univariate numerical polynomial associated with a subset of ℕ m (see [4, Chapter 0, Lemma 17]).
Let A be a subset of ℕ m and let partition (2.2) of ℕ m be fixed ( m = m 1 + ⋯ + m p for some nonnegative integers m 1 , … , m p , p ≥ 1 ). Then there exists a numerical polynomial A (t 1 , … , t p ) with the following properties:
(iv) A is a zero polynomial if and only if (0, … , 0) ∈ A.
The polynomial A (t 1 , … , t p ) is called the dimension polynomial of the set A ⊆ ℕ m associated with the given partition of ℕ m . If p = 1 , the corresponding uni- variate numerical polynomial A (t) is called the Kolchin polynomial of A.
Note that if A ⊆ ℕ m and A * is the set of all minimal elements of A with respect to the product order on ℕ m , then the set A * is finite (it follows from [4, Ch. 0, Lemma 15] that states that for any infinite set A ⊆ ℕ m , there exists an infinite sequence of elements of A, strictly increasing relative to the product order). The following theorem proved in [5, Chapter 2] gives an explicit formula for the dimension polynomial of a finite subset of ℕ m associated with a partition of ℕ m into the union of p disjoint subsets.
where n is a positive inte- ger, and let partition (2.2) of ℕ m be fixed
(as before we consider partition (2.2) of ℕ m ). We will use this observation in the proof of Theorem 4.1.
(2.3)
Generalized characteristic sets and new multivariate…
Let K be a difference field with a basic set = { 1 , … , m } and R = K{y 1 , … , y n } the algebra of difference polynomials in -indeterminates y 1 , … , y n over K. Then R can be viewed as a polynomial ring in the set of indeterminates TY = { y i | ∈ T, 1 ≤ i ≤ n} whose elements are called terms. As before, we fix partition (1.1) of the set and for every j = 1, … , p , define the order of a term u = y i with respect to j (denoted by ord j u ) as the corresponding order of (that is, ord j ( y i ) = ord j for any i = 1, … , n, ∈ T ). As usual, if , � ∈ T , we say that divides ′ (and write | � ) if � = �� for some element �� ∈ T denoted by ′ . If u = y i and v = � y j are two terms in TY, we say that u divides v (and write u | v ) if i = j and | � . In this case we also say that v is a transform of u and define the ratio
If ≤ is a ranking on R and f ∈ R , then the greatest and smallest (with respect to <) terms in f are called the leader and coleader of f with respect to the ranking ≤.
Let us consider p total orderings < 1 , … , < p of the set of power products
) is less than the corresponding (m + p) -tuple for ′ with respect to the lexicographic order on ℕ m+p . Furthermore, we consider p orders < 1 , … , < p on the set of terms TY that correspond to the intro- duced orders on T. They are defined as follows:
Clearly, these orders are rankings on K{y 1 , … , y n }.
If f ∈ K{y 1 , … , y n }⧵K and 1 ≤ k ≤ p , then the greatest with respect to < k term that appears in f is called the k-leader of the -polynomial f; it is denoted by u (k) f . The smallest with respect to < k term in f is called the k-coleader of f and is denoted by
f is called the k th effective order of f; it is denoted by Eord k f . It follows from the last definition that for any f ∈ K{y 1 , … , y n } and for any ∈ T , Eord k ( f ) = Eord k (f ) for k = 1, … , p. Definition 3.2 Let f and g be two -polynomials in the ring K{y 1 , … , y n } . We say that f has lower rank than g and write rk f < rk g if either f ∈ K , g ∉ K , or (the comparison of u (1) f and u (1) g in this lexicographic order is made with respect to the order < 1 on the set of terms TY). If the last two (p + 2)-tuples are equal (or f , g ∈ K ) we say that f and g are of the same rank and write rk f = rk g.
g g . We say that f is E-reduced with respect to g if one of the following two conditions holds.
(i) f does not contain any ( u (1) g ) e ( ∈ T ) such that e ≥ d;
g ) e with e ≥ d for some ∈ T , but in this case either there exists k ∈ ℕ p , k ≥ 2 , such that ord k (𝜏u (k) g ) > ord k (u (k) f ) or there exists j ∈ ℕ p such that ord j (𝜏v
f ) . (The "or" here is inclusive, that is, the case when both conditions hold is included.) Thus, f is not E-reduced with respect to g if f contains some ( u (1) g ) e ( ∈ T ) with e ≥ d = deg u (1) g g and also ord k (
Proof Suppose that f is not E-reduced with respect to g. Then f contains some
Therefore, rk f ≥ rk g according to Definition 3.2, so we have arrived at a contradic- tion. ◻ Proposition 3.2 Let A = {g 1 , … , g t } be a finite set of -polynomials in the ring R = K{y 1 , … , y n } , let u (i) k and v (i) k denote the i-leader and i-coleader of g k , respec- tively
Generalized characteristic sets and new multivariate… when g k is written as a polynomial in u (1)
Then for any h ∈ R , there exist -polynomials J ∈ I(A) and h * ∈ R such that h * is E-reduced with respect to A and
Proof If h is E-reduced with respect to A , the statement is obvious (one can set h * = h ). Suppose that h is not E-reduced with respect to A . In what follows, if a -polynomial f ∈ R is not E-reduced with respect to A , then a term w f that appears in f will be called the A-leader of f if w f is the greatest (with respect to < 1 ) term among all terms of the form u (1)
f for j = 1, … , p . Let w h be the A-leader of the element h, d = deg w h h , and c h the coefficient of w d h when h is written as a polynomial in w h . Then w h = u (1) k for some ∈ T and for some k
Let us choose such k that corresponds to the maxi- mum (with respect to < 1 ) 1-leader u (1) k in the set of all 1-leaders of elements of A , and let us consider the -polynomial
that is greater than w h with respect to < 1 (such a term cannot appear in (I k )h or g k ).
Applying the same procedure to h ′ and continuing in the same way, we will arrive at a -polynomial h * ∈ R such that h * is E-reduced with respect to A and Jhh * ∈ [A] for some J ∈ I(A) . ◻
The process of reduction described in the proof of the last proposition can be realized by the following algorithm. (Recall that R denotes the ring of -operators over the -ring R = K{y 1 , … , y n }.)
While there exist k, 1 ≤ k ≤ t , and a term w that appears in h * with a (nonzero) coefficient c w , such that u (1)
h * for j = 1, … , p , do z:= the greatest of the terms w that satisfy the above conditions. l:= the smallest number k for which u (1) g k is the greatest (with respect to < 1 ) 1-leader of an element of A such that u (1)
g l g l , and c z is the coefficient of z d when h * is written as a polynomial in z h * ∶= (I l )h *c z z d-d l ( g l ) End Definition 3.4 A set A ⊆ K{y 1 , … , y n } is said to be E-autoreduced if either it is empty or A ⋂ K = � and every element of A is E-reduced with respect to all other elements of the set A.
We are going to show that every E-autoreduced sets is finite. The proof of the following lemma can be found in [4, Chapter 0, Section 17].
Then there exists an infinite sequence of elements of A, strictly increasing relative to the product order, in which every element has the same projection on ℕ n . This lemma immediately implies the following statement that will be used below. Lemma 3.2 Let S be any infinite set of terms y j ( ∈ T, 1 ≤ j ≤ n ) in the ring K{y 1 , … , y n } . Then there exists an index j ( 1 ≤ j ≤ n ) and an infinite sequence of terms 1 y j , 2 y j , … , k y j , … such that k | k+1 for every k = 1, 2, ….
Proof Suppose that there is an infinite E-autoreduced set follows from Lemma 3.2 that A contains a sequence of -polynomials {f 1 , f 2 , … } such that u (1)
not have an infinite decreasing subsequence, without loss of generality we can assume that deg u (1)
Generalized characteristic sets and new multivariate… Then for any j = 2, … , p , we have
, so that f i 2 contains a term u (1)
such that ≠ 1 and ord j ( u
Similar arguments with the use of (3.2) show that ord j ( v
for j = 2, … , p . Thus, the -polynomial f i 2 is not reduced with respect to f i 1 that contradicts the fact that A is an E-autoreduced set. ◻
Example 1 Let K be a difference field with a basic set = { 1 considered with a partition = 1 ∪ 2 where 1 = { 1 } and 2 = { 2 } . Let A = {g 1 , g 2 } ⊆ K{y} (the ring of -polynomials in one -indeterminate y) where
Then ( Eord 1 (g 1 ), … , Eord p (g 1 ), u (1)
g 2 g 2 ) , so rk g 1 < rk g 2 . By Proposition 3.1, g 1 is E-reduced with respect to g 2 . Since g 2 contains no transform of u (1)
1 2 y , g 2 is reduced with respect to g 1 , so the set A is E-autoreduced. How- ever, since the degree of g 1 with respect to 1 u (1) g 2 is equal to the degree of g 2 with respect to u (1) g 2 , the set A is not autoreduced in the usual sense (where one considers an orderly ranking of terms in K{y} and f is said to be reduced with respect to g if f does not contain any ( u g ) e ( ∈ T , u g is the leader of g with respect to the given ranking) such that e ≥ d = deg u g g , see [5,Section 3.3]) or [9,Section 2.4]).
In what follows, while considering E-autoreduced sets we always assume that their elements are arranged in order of increasing rank. Definition 3.5 Let A = {g 1 , … , g s } and B = {h 1 , … , h t } be two E-autoreduced sets in the ring K{y 1 , … , y n } . Then A is said to have lower rank than B , written as rk A < rk B , if one of the following two cases holds:
(1) rk g 1 < rk h 1 or there exists k ∈ ℕ such that 1 < k ≤ min{s, t} , rk g i = rk h i for i = 1, … , k -1 and rk g k < rk h k .
(2) s > t and rk g i = rk h i for i = 1, … , t.
If s = t and rk g i = rk h i for i = 1, … , s , then A is said to have the same rank as B ; in this case we write rk A = rk B (3.2)
Proof Let M be a nonempty family of E-autoreduced sets in the ring K{y 1 , … , y n } .
Let us inductively define an infinite descending chain of subsets of M as follows: Let J be any ideal of the ring K{y 1 , … , y n } . Since the set of all E-autoreduced subsets of J is not empty (if f ∈ J , then {f } is an E-autoreduced subset of J), the last statement shows that J contains an E-autoreduced subset of lowest rank. Such an E-autoreduced set is called an E-characteristic set of the ideal J.
Then an element g ∈ J is E-reduced with respect to the set A if and only if g = 0.
Proof First of all, note that if g ≠ 0 and rk g < rk f 1 , then rk {g} < rk A that con- tradicts the fact that A is a E-characteristic set of the ideal J. Let rk g > rk f 1 (if rk g = rk f 1 , then g is not reduces with respect to f 1 , contrary to the assumption that g is E-reduced with respect to A ). Let f 1 , … , f j ( 1 ≤ j ≤ d ) be all elements of A whose rank is lower than the rank of g. Then the set A � = {f 1 , … , f j , g} is E-autore- duced. Indeed, by the conditions of the theorem, -polynomials f 1 , … , f j are reduced with respect to each other and g is reduced with respect to the set {f 1 , … , f j } . Fur- thermore, each f i ( 1 ≤ i ≤ j ) is reduced with respect to g because rk f i < rk g . Since rk A ′ < rk A , A is not an E-characteristic set of J that contradicts the conditions of the proposition. Thus, g = 0 . ◻ Proposition 3.6 Let ≤ be a ranking on the ring R = K{y 1 , … , y n } and let f 1 , … , f s ( s ≥ 2 ) be linear -polynomials in R. For every i = 1, … , s , let u i and v i denote, respectively, the leader and coleader of f i with respect to ≤ , and let
) and that g cannot be represented as a linear combina- tion of any proper subset of {f 1 , … , f s } with coefficients in R. Then g contains u 1 and v s .
Generalized characteristic sets and new multivariate… Proof Without loss of generality we can assume that the coefficient of u 1 in f 1 is 1. Dividing each h i ( 2 ≤ i ≤ s ) by f 1 with respect to u 1 , we obtain that h i = h � i f 1 + h �� i where the -polynomial h ′′ i does not contain u 1 . Thus,
Similarly, writing each h j with 1 ≤ j ≤ s -1 as h j = h * j f s + h * * j where h * * j does not contain v s , we obtain (using the fact that g cannot be written as a linear combination of elements of any proper subset of {f 1 , … , f s } ) that g contains v s . ◻
Then one can represent g in the form where 0 ≠ h i ∈ R , i ∈ T ( 1 ≤ i ≤ s ), i ≠ j whenever i ≠ j , and s is the smallest positive integer for which such a representation of g exists. (In particular, g cannot be written as a linear combination with coefficients in R of elements of any proper subset of { 1 f , … , s f } .) Since the elements 1 , … , s are all distinct, for every k = 1, … , p , there exists a permutation k of the set {1, … , s} such that
. By Proposition 3.6, g contains the k-leader of k (1) f and the k-coleader of k (s) f (clearly, the latter term cannot be smaller than v (k) g with respect to < k ). Therefore, g is not E-reduced with respect to {f } and rk g ≥ rk f . Thus, no element of [f] is E-reduced with respect to {f } and f has the smallest rank among all -polynomials in [f]. It follows that {f } is an E-characteristic set of the -ideal [f]. ◻
In this section we use properties of E-characteristic sets to obtain the following result that generalizes Theorem 1.1 and introduces a new type of multivariate dimension polynomials of difference field extensions that carry more invariants than any previously known difference dimension polynomials. (By an invariant of a finitely generated difference field extension we mean a numerical characteristic that is carried by a difference dimension polynomial of such an extension and that does not depend on the choice of the finite set of its difference generators.) As before, K denotes a difference ( -) field with a basic set = { 1 , … , m } considered together with its parti- tion (1.1) into the union of p disjoint subsets i , Card i = m i ( 1 ≤ i ≤ p ). Further- more, for any two p-tuples (r 1 , … , r p ), (s 1 , … , s p ) ∈ ℕ p with s i ≤ r i for i = 1, … , p , we set
Then there exists a polynomial |K (t 1 , … , t 2p ) in 2p variables with rational coefficients and numbers r (0) i ,
Proof Let P ⊆ R = K{y 1 , … , y n } be the defining -ideal of the extension L/K and let A = {f 1 , … , f q } be an E-characteristic set of P. Let u (i) j and v (i) j denote the i-leader and i-coleader of f j , respectively ( 1
u is divisible by the 1-leader of some f j ( 1 ≤ j ≤ q ) and whenever u = u (1) j for some ∈ T, 1 ≤ j ≤ q , either ord 1 (𝜏v (1) j ) < s 1 or there exist k ∈ {2, … , p} , i ∈ {1, … , p} such that ord k (𝜏u (k) j ) > r k or ord i (𝜏v (i) j ) < s i ("or" is inclusive)},
We are going to prove that for every r, s ∈ ℕ p with s < P r , the set U (r, s) is a tran- scendence basis of the field K(W (r, s)) over K. First, one can see that this set is algebraically independent over K. Indeed, if f (w 1 ( ), … , w k ( )) = 0 for some ele- ments w 1 , … , w k ∈ U(r, s) , then the -polynomial f (w 1 , … , w k ) lies in P and it is
and
1 3
Generalized characteristic sets and new multivariate…
f ("or" is inclusive). It follows that f is E-reduced with respect to A .) By Proposition 3.5, f = 0 , so the set U (r, s) is algebraically inde- pendent over K. Now let us prove that if 0 ≤ s i ≤ r is (0) i , where s (0) i = max{ Eord i f j | 1 ≤ j ≤ q} ( 1 ≤ i ≤ p ), then every element k ∈ W (r, s)⧵U (r, s) ( ∈ T , 1 ≤ k ≤ n ) is alge- braic over the field K(U (r, s)) . In this case y k ∉ U(r, s) , therefore y k is equal to some term of the form � u (1) j ( 1 ≤ j ≤ q ) where � ∈ T , ord 1 ( � u (i) j ) ≤ r i for i = 2, … , p , and ord l ( � v (l) j ) ≥ s l for l = 1, … , p. Let us represent f j as a polynomial in u (1) j :
where
do not contain u (1) j (therefore, all terms in these -polynomials are lower than u (1) j with respect to < 1 ). Since f j ∈ P , f j ( ) = 0 , that is, Note that I This contradicts the fact that A is an E-characteristic set of P. Since the -ideal P is reflexive, (i) q ) ∉ P for any ∈ T . Therefore, if we apply ′ to both sides of (4.1), the resulting equality will show that the element � u (1) j ( ) = k is algebraic over the field K({ τ 𝜂 l | s i ≤ ord i τ ≤ r i (1 ≤ i ≤ p), τ y l < 1 𝜏 � u (1) j }) . Now, the induction on the well-ordered (with respect to < 1 ) set of terms TY completes the proof of the fact that the set U (r, s) is a transcendence basis of the field K(W (r, s)) over K.
In order to evaluate the size of U (r, s) we are going to evaluate the sizes of the sets U � (r, s) and U �� (r, s) , that is, the sizes of the sets U � (r, s) and U �� (r, s) . For every k = 1, … , n , let Applying Theorem 2.1, we obtain that there exists a numerical polynomial k (t 1 , … , t p ) in p variables with rational coefficients such that k (r 1 , … , r p ) = Card V A k (r 1 , … , r p ) for all sufficiently large (r 1 , … , r p ) ∈ ℕ p . It follows that if we set
L/K associated with the set of -generators and partition (1.1) of , as it is shown in the proof of Theorem 1.1 given in [9,Section 4.2].
In order to evaluate Card U �� (r, s) , note that this set consists of all terms u (1) j ( ∈ T, 1 ≤ j ≤ q ) such that s i ≤ ord i ( u j ) ≤ r i and either ord 1 (𝜏v (1) j ) < s 1 or there exist k ∈ {2, … , p} , i ∈ {1, … , p} such that ord k (𝜏u (k) j ) > r k or ord i (𝜏v (i) j ) < s i ("or" is inclusive). It follows from Remark 2.1 that for every fixed j, the number N j of such terms satisfying the conditions ord i (𝜏v (i)
By Remark 2.1, a similar formula holds for the number of terms satisfying the con-
Applying the principle of inclusion and exclusion (taking into account terms that are multiples of more than one 1-leaders), we obtain that Card U �� (r, s) is an alternat- ing sum of polynomials in r 1 , … , r p , s 1 , … , s p that are products of k terms of the form r i -a i +m i m The following theorem describes some invariants of a 2p-variate -dimension polynomial of a finitely generated -field extension L/K with partition (1.1) of ,
Generalized characteristic sets and new multivariate… that is, characteristics of the extension that do not depend on the set of -generators of L over K. The formulation of the theorem uses the following notation. For any permutation (j 1 , … , j 2p ) of the set {1, … , 2p} , let < j 1 ,…,j 2p denote the lexicographic order on ℕ p such that (k 1 , … , k 2p ) < j 1 ,…,j 2p (l 1 , … , l 2p ) if and only if either k j 1 < l j 1 or there exists q ∈ ℕ , 2 ≤ q ≤ 2p , such that k j = l j for 𝜈 < q and k j q < l j q .
Theorem 4.2 With the notation of Theorem 4.1, let |K (t 1 , … , t 2p ) be the 2p-variate -dimension polynomial of the -field extension L = K⟨ 1 , … , n ⟩ . Since the degrees of |K with respect to t i and t p+i ( 1 ≤ i ≤ p ) do not exceed m i = Card i (see parti- tion (1.1)), Theorem 2.1 shows that this polynomial can be written as
Then the total degree d of |K with respect to t 1 , … , t p and the coefficients of the terms of total degree d in not depend on the choice of the set of -generators . Furthermore, if ( 1 , … , p ) is any permutation of {1, … , p} and ( 1 , … , p ) is any permutation of {p + 1, … , 2p} , then the maximal element of E with respect to the lexicographic order < 𝜇 1 ,…,𝜇 p ,𝜈 1 ,…,𝜈 p and the corresponding coefficient a 1 ,…, p , 1 ,…, p do not depend on the choice of a finite set of -generators of L/K either. Finally, a m 1 …m p 0…0 = a 0…0m 1 …m p = -tr.deg K L.
Proof Suppose that = { 1 , … , l } is another system of -generators of L/K, that is, L = K⟨ 1 , … , n ⟩ = K⟨ 1 , … , l ⟩ . Let be the 2p-variate dimension polynomial of L/K associated with the system of generators . Then there exist h In order to prove the last part of the theorem, note that the expression (4.3) and a similar expression corresponding to the condition with ord i (𝜏u (i) j ) > r i for i ∈ {l 1 , … , l e } ⊆ {2, … , p} (see the proof of Theorem 2.3) have the property that there total degrees with respect to r 1 , … , r p and s 1 , … , s p are less than m. It follows that the coefficients of the terms of total degree m in t 1 , … , t p and terms of total degree m in t p+1 , … , t 2p in the polynomial |K are equal to the corresponding coeffi- cients in the polynomials |K (t 1 , … , t p ) and |K (t p+1 , … , t 2p ) , respectively (see (4.2)). It follows from Theorem 1.1 that a m 1 …m p 0…0 = a 0…0m 1 …m p = -tr. .
Therefore, the dimension polynomial of the -field extension of L/K defined by the equation (4.4) on its -generator , which expresses Card U � (r, s) + Card U �� (r, s) , is of the form Note that the standard (univariate) -dimension polynomial |K (t) of the extension L/K associated with the -generator (see [6] or [5,Theorem 6.4.1]), which is equal to the Kolchin polynomial of the set {(a, b)} ⊂ ℕ 2 , is as follows. This polynomial carries two invariants of the extension L/K, deg |K = 2 and the leading coefficient a + b . At the same time, according to Theorem 4.1, the num- bers c, 2bc and 2ac are invariants of the dimension polynomial (4.5). Thus, the dimension polynomial (4.5) gives all three parameters a, b and c of the defining equation (4.4) while |K (t) gives just the sum a + b.
In [13], the author introduced a bivariate dimension polynomial |K (t 1 , t 2 ) that describes the transcendence degrees of intermediate fields
of the extension K⟨ 1 , … , n ⟩∕K for all sufficiently large r, s ∈ ℕ with s < r . The computation of this polynomial in the case of the -field extension L = K⟨ ⟩ with the defining equation (4.4) gives the fol- lowing result (we use Theorem 4.1 of [13]):
By [13,Theorem 4.1], the polynomial |K (t 1 , t 2 ) carries three invariants of the extension L/K, deg |K = 2 , a + b , and c. We see that this polynomial does not give all the parameters a, b, c of the equation (4.4) while the polynomial |K (t 1 , … , t 6 ) carries all these parameters. The univariate difference dimension polynomial and the bivariate difference dimension polynomial introduced in [13] are defined without using partitions of the basic sets of translations. The multivariate -dimension polynomial given by Theorem 1.1 is associated with such a partition. The following example illustrates that in this case our 2p-dimension polynomial carries more invariants of the corresponding -field extension than the p-variate -dimension polynomial introduced by Theorem 1.1.
Let K be a difference ( -) field with a basic set of endomorphisms = { 1 , 2 } considered together with its partition = { 1 } ∪ { 2 } . Let L = K⟨ ⟩ be a -field extension with the defining equation where a, b, c ∈ ℕ , a > b > c > 0 . Then the computation of the bivariate -dimension polynomial |K (t 1 , t 2 ) (see Theorem 1.1) using the method of [13] and the computa- tion of the 4-variate -dimension polynomial |K (t 1 , t2, t 3 , t 4 ) (using the evaluation of the set Card U (r, s) , as it is done in the proof of Theorem 2.