Dimension Quasi-polynomials of Inversive Difference Field Extensions with Weighted Translations

Abstract

We consider Hilbert-type functions associated with finitely generated inversive difference field extensions and systems of algebraic difference equations in the case when the translations are assigned positive integer weights. We prove that such functions are quasi-polynomials that can be represented as alternating sums of Ehrhart quasi-polynomials of rational conic polytopes. In particular, we generalize the author’s results on difference dimension polynomials and their invariants to the case of inversive difference fields with weighted basic automorphisms.

1 Introduction

The role of difference dimension polynomials in difference algebra is similar to the role of Hilbert polynomials in commutative algebra and algebraic geometry, as well as to the role of differential dimension polynomials in differential algebra. In particular, difference dimension polynomials and their invariants play the key role in the study of Krull-type dimension of difference and inversive difference modules and algebras, as well as of difference and inversive difference field extensions (see, for example, [8, 10, 11, 13], and [9, Sects. 3.6, 4.6]). Furthermore, and this is probably the most important application of difference dimension polynomials outside of difference algebra, the difference dimension polynomial of a system of algebraic difference equations expresses the A. Einstein’s strength of the system (see [9, Chap. 7] for a detailed description of this concept). In this connection, properties and methods of computation of difference dimension polynomials play a significant role in the qualitative theory of difference equations.

In this paper, we prove the existence and determine some invariants of a dimension quasi-polynomial associated with a finitely generated inversive difference field extension with weighted basic translations. We also show that such a quasi-polynomial is an alternating sum of Ehrhart quasi-polynomials associated with rational conic polytopes. Furthermore, we show that every “prime” system of algebraic difference equations with weighted translations (that is, a system of the form $f_{i}(y_{1},\dots , y_{n}) = 0$, $i\in I$, where the left-hand sides generate a prime reflexive difference ideal in the corresponding ring of inversive difference polynomials) can be assigned a quasi-polynomial, which represents the Einstein’s strength of the system. Note that systems of difference equations of these kind arise, in particular, from finite difference approximations of systems of PDEs with weighted derivatives, see, for example, [14, 15]. One should also mention that our work continues the study of dimension quasi-polynomials associated with differential and difference algebraic structures initiated by C. Dönch in his dissertation [4]. In this work C. Dönch developed a Gröbner basis method for free difference-differential modules with weighted basic derivations and translations and used the developed technique to prove the existence of dimension quasi-polynomials associated with finitely generated modules over rings of difference-differential operators.

2 Preliminaries

In what follows $\mathbb {Z}$, $\mathbb {N}$, $\mathbb {Z}_{-}$, $\mathbb {Q}$, and $\mathbb {R}$ denote the sets of all integers, non-negative integers, non-positive integers, rational numbers, and real numbers, respectively. If $m\in \mathbb {Z}$, $m\ge 1$, then by the product order on $\mathbb {N}^{m}$ we mean a partial order $<_{P}$ such that $(a_{1},\dots , a_{m})<_{P}(a'_{1},\dots , a'_{m})$ if and only if $a_{i}<_{P}a'_{i}$ for $i=1,\dots , m$.

By a ring we always mean an associative ring with unity. Every ring homomorphism is unitary (maps unity onto unity), every subring of a ring contains the unity of the ring.

A difference ring is a commutative ring R together with a finite set $\sigma = \{\alpha _{1},\dots , \alpha _{m}\}$ of mutually commuting endomorphisms of R. The set $\sigma$ is called a basic set of R and the endomorphisms $\alpha _{i}$ are called translations. We also say that R is a $\sigma$-ring.

If $\alpha _{1}, \dots , \alpha _{m}$ are automorphisms of R, we say that R is an inversive difference ring with the basic set $\sigma$. In this case the set $\{\alpha _{1}, \dots , \alpha _{m}, \alpha _{1}^{-1}, \dots , \alpha _{m}^{-1}\}$ is denoted by $\sigma ^{*}$ and R is also called a $\sigma ^{*}$-ring. If a difference ring with a basic set $\sigma$ is a field, it is called a difference (or $\sigma$-) field. If all $\alpha _{i}$ are automorphisms, it is called an inversive difference field or a $\sigma ^{*}$-field. (We always use the upper index $*$ in the notation that refers to inversive algebraic difference structures; the corresponding notation without $*$ is common in the non-inversive case.)

In what follows we deal with inversive difference ($\sigma ^{*}$-) rings and fields, where the basic set consists of m translations (automorphisms) $\alpha _{1}, \dots , \alpha _{m}$. Furthermore, we will consider the free commutative group $\varGamma$ generated by the set $\sigma$ (we use the multiplicative notation, so that elements of $\varGamma$ are power products of the form $\gamma = \alpha _{1}^{k_{1}}\dots \alpha _{m}^{k_{m}}$ where $k_{1},\dots , k_{m}\in \mathbb {Z}$).

If R is a $\sigma ^{*}$-ring and $R_{0}$ a subring of R such that $\alpha (R_{0})\subseteq R_{0}$ for any $\alpha \in \sigma ^{*}$, then $R_{0}$ is said to be an inversive difference (or $\sigma ^{*}$-) subring of R; we also say that R is a $\sigma ^{*}$-overring of $R_{0}$. In this case the restriction of $\alpha _{i}$ on $R_{0}$ ($1\le i\le m$) is denoted by the same symbol $\alpha _{i}$. If R is an inversive difference ($\sigma ^{*}$-) field and $R_{0}$ a subfield of R which is also a $\sigma ^{*}$-subring of R, then $R_{0}$ is said to be an inversive difference (or $\sigma ^{*}$-) subfield of R; R, in turn, is called an inversive difference (or $\sigma ^{*}$-) field extension (or overfield) of $R_{0}$. In this case we also say that we have a $\sigma ^{*}$-field extension $R/R_{0}$.

A subring (ideal) J of a $\sigma ^{*}$-ring R is said to be a $\sigma ^{*}$-subring of R (respectively, a $\sigma ^{*}$-ideal of R) if J is closed with respect to the action of any mapping $\alpha _{i}\in \sigma ^{*}$. If J is a $\sigma ^{*}$-ideal of R, then the factor ring R/J has a natural structure of a $\sigma ^{*}$-ring with the same basic set $\sigma$ where $\alpha (a+I) = \alpha (a) + I$ for any coset $a+I\in R/I$ and $\alpha \in \sigma ^{*}$. If a $\sigma ^{*}$-ideal is prime, it is referred to as a prime $\sigma ^{*}$ -ideal.

If R is a $\sigma ^{*}$-ring and $S\subseteq R$, then the intersection I of all $\sigma ^{*}$-ideals of R containing the set S is the smallest $\sigma ^{*}$-ideal of R containing S; it is denoted by $[S]^{*}$. Clearly, $[S]^{*}$ is generated, as an ideal, by the set $\{\gamma (a)\,|\, a\in S,\, \gamma \in \varGamma \}$). If the set S is finite, $S = \{a_{1},\dots , a_{r}\}$, we say that the $\sigma$-ideal $J = [S]^{*}$ is finitely generated (we write this as $J = [a_{1},\dots , a_{r}]^{*}$) and call $a_{1},\dots , a_{r}$ $\sigma ^{*}$-generators of J.

If $R_{0}$ is a $\sigma ^{*}$-subring of R and $S\subseteq R$, then the smallest $\sigma ^{*}$-subring of R containing $R_{0}$ and S is denoted by $R_{0}\{S\}^{*}$ (if S is finite, $S = \{\eta _{1},\dots , \eta _{n}\}$, we write $R_{0}\{\eta _{1},\dots , \eta _{n}\}^{*}$). As a ring, it is generated over $R_{0}$ by the set $\{\gamma s\,|\,\gamma \in \varGamma ,\, s\in S\}$. (Here and below we frequently write $\gamma s$ for $\gamma (s)$.)

A ring homomorphism of $\sigma$-rings $\phi : R \longrightarrow S$ is called a difference (or $\sigma$-) homomorphism if $\phi (\alpha a) = \alpha \phi (a)$ for any $\alpha \in \sigma$, $a\in R$ (of course, if R and S are inversive, the equality holds for every $\alpha \in \sigma ^{*}$). It is easy to see that the kernel of such a mapping is a $\sigma ^{*}$-ideal of R.

If K is a $\sigma ^{*}$-subfield of a $\sigma ^{*}$-field L and $S\subseteq L$, then the smallest $\sigma ^{*}$-subfield of L containing K and S is denoted by $K\langle S\rangle ^{*}$. If the set S is finite, $S = \{\eta _{1},\dots ,\eta _{n}\}$, then $K\langle S \rangle ^{*}$ is written as $K\langle \eta _{1},\dots ,\eta _{n}\rangle ^{*}$ and is said to be a finitely generated inversive difference (or $\sigma ^{*}$-) extension of K with the set of $\sigma ^{*}$-generators $\{\eta _{1},\dots ,\eta _{n}\}$. It is easy to see that the field $K\langle \eta _{1},\dots ,\eta _{n}\rangle ^{*}$ coincides with the field $K(\{\gamma \eta _{i}\,|\,\gamma \in \varGamma ,\, 1\le i\le n\}$).

If R is an inversive difference ($\sigma ^{*}$-) ring and $Y =\{y_{1},\dots , y_{n}\}$ is a finite set of symbols, then one can consider a countable set of symbols $\varGamma Y = \{\gamma y_{j}|\gamma \in \varGamma , 1\le j\le n\}$ and the polynomial ring $R[\varGamma Y]$ in the set of indeterminates $\varGamma Y$ over R (the elements of $\varGamma Y$ will be called terms). This polynomial ring is naturally viewed as a $\sigma ^{*}$-ring where the action of the translations of $\sigma ^{*}$ on R is extended to $R[\varGamma Y]$ by setting $\alpha (\gamma y_{j}) = (\alpha \gamma )y_{j}$ for any $\alpha \in \sigma ^{*}$, $\gamma \in \varGamma$, $1\le j\le n$. This $\sigma ^{*}$-ring (that contains R as its $\sigma ^{*}$-subring) is denoted by $R\{y_{1},\dots , y_{n}\}^{*}$; it is called the ring of inversive difference (or $\sigma ^{*}$-) polynomials in the set of inversive difference ($\sigma ^{*}$-) indeterminates $y_{1},\dots , y_{n}$ over R. Elements of $R\{y_{1},\dots , y_{n}\}^{*}$ are called inversive difference (or $\sigma ^{*}$-) polynomials. If R is a $\sigma ^{*}$-subring of a $\sigma ^{*}$-ring S, $f\in R\{y_{1},\dots , y_{n}\}^{*}$ and $\eta = (\eta _{1},\dots , \eta _{n})\in S^{n}$, then $f(\eta )$ denotes the result of the replacement of every entry $\gamma y_{i}$ in f by $\gamma \eta _{i}$ ($\gamma \in \varGamma$, $1\le i\le n$).

Let R be an inversive difference ($\sigma ^{*}$-) ring and $U = \big \{u^{(\lambda )} | \lambda \in \varLambda \big \}$ a family of elements of some $\sigma ^{*}$-overring of R. We say that the family U is transformally (or $\sigma$-algebraically) dependent over R, if the family

$$U_{\sigma }^{*} = \left\{ \gamma u^{(\lambda )}\,|\,\gamma \in \varGamma ,\, \lambda \in \varLambda \right\} $$

is algebraically dependent over R (that is, there exist elements $v^{(1)},\dots , v^{(k)}\in U_{\sigma }^{*}$ and a nonzero polynomial f in k variables with coefficients in R such that $f\big (v^{(1)},\dots , v^{(k)}\big ) = 0$). Otherwise, the family U is said to be transformally (or $\sigma$-algebraically) independent over R.

If K is an inversive difference ($\sigma ^{*}$-) field and L a $\sigma ^{*}$-field extension of K, then a set $B\subseteq L$ is said to be a difference (or $\sigma$-) transcendence basis of L over K if B is $\sigma$-algebraically independent over K and every element $a\in L$ is $\sigma$-algebraic over $K\langle B\rangle ^{*}$ (that is, the set $\{\gamma a\,|\,\gamma \in \varGamma \}$ is algebraically dependent over $K\langle B\rangle ^{*}$). If L is a finitely generated $\sigma ^{*}$-field extension of K, then all $\sigma$-transcendence bases of L over K are finite and have the same number of elements (see [9, Sect. 4.1]). This number is called the difference (or $\sigma$-) transcendence degree of L over K (or the $\sigma$-transcendence degree of the extension L/K); it is denoted by $\sigma$-${{\mathrm{trdeg}}}_{K}L$.

3 Dimension Quasi-polynomials of Subsets of $\mathbb {N}^{m}$ and $\mathbb {Z}^{m}$

A function $f:\mathbb {Z}\rightarrow \mathbb {Q}$ is called a quasi-polynomial of period q if there exist q polynomials $g_{i}(x)\in \mathbb {Q}[x]$   ($0\le i\le q-1$) such that $f(n) = g_{i}(n)$ whenever $n\in \mathbb {Z}$ and $n\equiv i\, (mod\, q)$.

An equivalent way of introducing quasi-polynomials is as follows.

A rational periodic number U(n) is a function $U:\mathbb {Z}\rightarrow \mathbb {Q}$ with the property that there exists (a period) $q\in \mathbb {N}$ such that

$$U(n) = U(n')\,\,\, {\text {whenever}}\,\,\, n\equiv n' \,(mod\, q).$$

A rational periodic number is represented by a list of q its possible values as follows:

$$U(n) = [a_{0},\dots , a_{q-1}]_{n}.$$

($U(n)= a_{i}$ ($0\le i\le q-1$) whenever $n\equiv i\,(mod\, q)$).

For example, $U(n) = \left[ {\displaystyle \frac{2}{3}},\, {\displaystyle \frac{1}{4}},\, 5\right] _{n}$ is a periodic number with period 3 such that $U(n) = {\displaystyle \frac{2}{3}}$ if $n\equiv 0 \,(mod\, 3)$, $U(n) = {\displaystyle \frac{1}{4}}$ if $n\equiv 1 \,(mod\, 3)$, and $U(n) = 5$ if $n\equiv 2 \,(mod\, 3)$.

With the above notation, a quasi-polynomial of degree d is defined as a function $f:\mathbb {Z}\rightarrow \mathbb {Q}$ such that

$$f(n) = c_{d}(n)n^{d} + \dots + c_{1}(n)n + c_{0}(n)\,\,\,\,\, (n\in \mathbb {Z})$$

where $c_{i}(n)$’s are rational periodic numbers and $c_{d}(n)\ne 0$ for at least one $n\in \mathbb {Z}$.

One of the main applications of quasi-polynomials is their application to the problem of counting integer points in rational polytopes. Recall that a rational polytope in $\mathbb {R}^{d}$ is the convex hull of finitely many points (vertices) in $\mathbb {Q}^{d}$ (d is a positive integer). Equivalently, a rational polytope $P\subseteq \mathbb {R}^{d}$ is the set of solutions of a finite system of linear inequalities $A\mathbf{x}\le \mathbf{b},$ where A is an $m\times d$-matrix with integer entries ($m\in \mathbb {Z},\, m\ge 1$) and $\mathbf{b}\in \mathbb {Z}^{m}$, provided that the solution set is bounded. A rational polytope is said to be a lattice one if all its vertices are integer points (that is, points with integer coordinates).

Let $P\subseteq \mathbb {R}^{d}$ be a rational polytope. (We assume that P has dimension d, that is, P is not contained in a proper affine subspace of $\mathbb {R}^{d}$.) Then a polytope

$$rP = \{r\mathbf{x}\,|\,\mathbf{x}\in P\}$$

($r\in \mathbb {N}$, $n\ge 1$) is called the rth dilate of P. Clearly, if $\mathbf{v}_{1},\dots , \mathbf{v}_{k}$ are all vertices of P, then rP is the convex hull of $r\mathbf{v}_{1},\dots , r\mathbf{v}_{k}$.

Given a rational polytope P, let L(P, r) denote the number of integer points in rP (in other words, $L(P, r) = {{\mathrm{Card}}}(rP\cap \mathbb {Z}^{d}$)). The following result is due to Ehrhart, see [5].

Theorem 1

Let $P\subseteq \mathbb {R}^{d}$ be a rational polytope of dimension d. Then there exists a quasi-polynomial $\phi _{P}(r)$ of degree d such that

 

(i) :

$\phi _{P}(r) = L(P, r)$ for all $r\in \mathbb {N}$.

(ii) :

The leading coefficient of $\phi _{P}(r)$ is a constant that is equal to the Euclidean volume of the polytope P.

(iii) :

The minimum period of $\phi _{P}(r)$ (that is, the least common multiple of the minimum periods of its coefficients) is a divisor of the number $\mathcal {D}(P)= \min \{n\in \mathbb {N}\,|\,nP$ is a lattice polytope$\}$.

(iv) :

If P is a lattice polytope, then $\phi _{P}(r)$ is a polynomial of r with rational coefficients.

 

The main tools for computation of Ehrhart quasi-polynomials are Alexander Barvinok’s polynomial time algorithm and its modifications, see [1,2,3]. In some cases, however, the Ehrhart quasi-polynomial can be found directly from the Ehrhart’s theorem by evaluating the periodic coefficients of the quasi-polynomial (by computing L(P, r) for the first several values of $r\in \mathbb {N}$ and then solving the corresponding system of linear equations, see [12, Example 1]).

Let $w_{1},\dots , w_{m}$ be fixed positive integers ($m > 0$) and $a = (a_{1},\dots , a_{m})\in \mathbb {N}^{m}$. Then the number

$${{\mathrm{ord}}}_{w}a = w_{1}a_{1} + \dots + w_{m}a_{m}$$

is called the order of a with respect to the weights $w_{1},\dots , w_{m}$. If the weights are fixed, ${{\mathrm{ord}}}_{w}a$ is simply called the order of a.

In what follows, $\lambda ^{(m)}_{w}(t)$ denotes the Ehrhart quasi-polynomial that describes the number of integer points in the conic polytope

$$P_{t} = \{(x_{1},\dots , x_{m})\in \mathbb {R}^{m}\,|\, \sum _{i=1}^{m}w_{i}x_{i}\le t,\, x_{j}\ge 0\, (1\le j\le m)\}.$$

It follows from the Ehrhart’s Theorem that $\lambda ^{(m)}_{w}(t)$ is a quasi-polynomial of degree m whose leading coefficient is $\displaystyle \frac{1}{m!w_{1}\dots w_{m}}$. A polynomial time algorithm for computing $\lambda ^{(m)}_{w}(t)$ can be found, for example, in [3]. We will illustrate the computation of such a quasi-polynomial with the use of the above-mentioned method based on the Ehrhart’s theorem.

Example 1

Consider a conic polytope

$$P = \{(x_{1}, x_{2})\in \mathbb {R}^{2}\,|\,x_{1}\ge 0,\, x_{2}\ge 0,\, 2x_{1}+3x_{2}\le 1\}$$

whose rth dilate is

$$rP = \{(x_{1}, x_{2})\in \mathbb {R}^{2}\,|\,x_{1}\ge 0,\, x_{2}\ge 0,\, 2x_{1}+3x_{2}\le r\}.$$

By the Ehrhart’s theorem,

$$\phi _{P}(r) = L(P, r) = {\frac{1}{12}}r^{2} + [a_{0}, a_{1}, a_{2}, a_{3}, a_{4}, a_{5}]_{r}r + [b_{0}, b_{1}, b_{2}, b_{3}, b_{4}, b_{5}]_{r}$$

where $a_{i}, b_{i}\in \mathbb {Q}$ ($0\le i\le 5$). The direct computation of the number of integer points in the first eleven dilated polytopes rP gives

$\phi _{P}(0) = b_{0} = 1$,  $\phi _{P}(1) = {\frac{1}{12}} + a_{1} + b_{1} = 1$,  $\phi _{P}(2) = {\frac{1}{3}} + 2a_{2} + b_{2} = 2$,

$\phi _{P}(3) = {\frac{3}{4}} + 3a_{3} + b_{3} = 3$,  $\phi _{P}(4) = {\frac{4}{3}} + 4a_{4} + b_{4} = 4$,  $\phi _{P}(5) = {\frac{25}{12}} + 5a_{5} + b_{5} = 5$,

$\phi _{P}(6) = 3 + 6a_{0} + b_{0} = 7$;  $\phi _{P}(7) = {\frac{49}{12}} + 7a_{1} + b_{1} = 8$,  $\phi _{P}(8) = {\frac{16}{3}} + 8a_{2} + b_{2} = 10$,

$\phi _{P}(9) = {\frac{27}{4}} + 9a_{3} + b_{3} = 12$,  $\phi _{P}(10) = {\frac{25}{3}} + 10a_{4} + b_{4} = 14$,

$\phi _{P}(11) = {\frac{121}{12}} + 11a_{5} + b_{5} = 16$. Solving this system we obtain that $a_{i} = {\frac{1}{2}}$

($0\le i\le 5$), $b_{0} =1$, $b_{1} = {\frac{5}{12}}$, $b_{2} = {\frac{2}{3}}$, $b_{3} = {\frac{3}{4}}$, $b_{4} = {\frac{2}{3}}$, and $b_{5} = {\frac{5}{12}}$, so that

$$\phi _{P}(r) = {\frac{1}{12}}r^{2} + {\frac{3}{4}}r + \left[ 1, {\frac{5}{12}}, {\frac{2}{3}}, {\frac{3}{4}}, {\frac{2}{3}}, {\frac{5}{12}}\right] _{r}.$$

Remark 1

In what follows we will also use Ehrhart quasi-polynomials that describe (for sufficiently large $r\in \mathbb {N}$) the numbers of integer points $(x_{1},\dots , x_{m})\in \mathbb {R}^{m}$ satisfying the inequality $|x_{1}| +\dots + |x_{m}|\le r$. It is easy to see that such a quasi-polynomial, denoted by $\mu _{w}^{(m)}(t)$, is an alternating sum of quasi-polynomials of the form $\lambda _{w}^{(k)}(t)$ that contains $2^{m}$ terms $\lambda _{w}^{(m)}(t)$ and the other quasi-polynomials $\lambda _{w}^{(k)}(t)$ in this sum have $k <m$. It follows that

$$\mu _{w}^{(m)}(t) = {\frac{2^{m}}{m!w_{1}\dots w_{m}}}t^{m} + \,\,\,\text {terms of degree less than}\,\,\, m.$$

For any $A\subseteq \mathbb {N}^{m}$, $r\in \mathbb {N}$ (and the fixed weight vector $w = (w_{1},\dots , w_{m})$), we set

$$A^{(w)}(r) = \{a = (a_{1},\dots , a_{m})\in A\,|\,{{\mathrm{ord}}}_{w}a \le r\}.$$

Furthermore, $V^{(w)}_{A}$ will denote the set of all m-tuples $v = (v_{1},\dots , v_{m})\in \mathbb {N}^{m}$ that are not greater than or equal to any m-tuple from A with respect to the product order $\le _{P}$. In other words, an element $v=(v_{1}, \dots , v_{m})\in \mathbb {N}^{m}$ lies in $V^{(w)}_{A}$ if and only if for any element $(a_{1},\dots , a_{m})\in A$ there exists $i\in \mathbb {N}, 1\le i\le m$, such that $a_{i} > v_{i}$.

The following theorem proved in [12] generalizes E. Kolchin’s result on dimension polynomials of subsets of $\mathbb {N}^{m}$ (see [6, Chap. 0, Lemma 16]).

Theorem 2

With the above conventions, for any set $A\subseteq \mathbb {N}^{m}$, there exists a quasi-polynomial $\chi ^{(w)}_{A}(t)$ in one variable t such that  

(i) :

$\chi ^{(w)}_{A}(r) = {{\mathrm{Card}}}\,V^{(w)}_{A}(r)$ for all sufficiently large $r\in \mathbb {N}$.

(ii) :

$\deg \,\chi ^{(w)}_{A}(t)\le m$.

(iii) :

$\deg \,\chi ^{(w)}_{A}(t) = m$ if and only if $A = \emptyset$. In this case $\chi ^{(w)}_{A}(t) = \lambda ^{(m)}_{w}(t)$.

(iv) :

$\chi ^{(w)}_{A}(t) = 0$ if and only if $(0,\dots , 0)\in A$.

(v) :

Let $A = \{a^{(1)}, \dots , a^{(d)}\}$ be a finite subset of $\mathbb {N}^{m}$ and let $a^{(i)} = (a_{i1},\dots , a_{im})$ for $i=1,\dots , d$. For any $l = 0,\dots , d$, let $\varDelta (l, d)$ denote the set of all l-element subsets of $\{1,\dots , d\}$ ($\varDelta (0, d) = \emptyset$) and for any set $\epsilon = \{a^{(i_{1})},\dots , a^{(i_{l})}\}\in \varDelta (l, d)$ ($1\le i_{1}<\dots < i_{l}\le d$), let $c_{\epsilon j} = \max \{a_{\nu j}\,|\,\nu = i_{1},\dots , i_{l}\}$ (the maximal jth coordinate of elements of $\epsilon$). Furthermore, let $c_{\epsilon } = (c_{\epsilon 1}, \dots , c_{\epsilon m})$. Then

$$\begin{aligned} \chi ^{(w)}_{A}(t) = \sum _{l=0}^{d}(-1)^{l}\sum _{\epsilon \in \varDelta (l, d)}\lambda ^{(m)}_{w}(t - {{\mathrm{ord}}}_{w}c_{\epsilon }). \end{aligned}$$

(1)

 

The quasi-polynomial $\chi ^{(w)}_{A}(t)$ whose existence is established by Theorem 2 is called the dimension quasi-polynomial of the set $A\subseteq \mathbb {N}^{m}$ associated with the weight vector $(w_{1},\dots , w_{m})$. An example of computation of such a quasi-polynomial can be found in [12, Example 2].

Note that if $w_{1}=\dots = w_{m}=1$, then $\chi ^{(w)}_{A}(t)$ is the dimension polynomial of the subset A of $\mathbb {N}^{m}$ introduced in [6, Chap. 0, Lemma 16]. Some properties of such polynomials and methods of their computation were obtained in [7, Chap. 2]. If $w_{1}=\dots = w_{m} = w$ and $w > 1$, then it is easy to see that $\lambda ^{(m)}_{w}(t)$ describes the number of integer points in the conic polytope $\{(x_{1},\dots , x_{m})\in \mathbb {R}^{m}\,|\,\sum _{i=1}^{m}x_{i}\le \left\lfloor {\frac{t}{w}}\right\rfloor \}$ ($\left\lfloor {a}\right\rfloor$ denotes the greatest integer not exceeding a). Therefore, $\lambda ^{(m)}_{w}(t) = \displaystyle {{\left\lfloor {\frac{t}{w}}\right\rfloor + m}\atopwithdelims (){m}}$. Clearly, w is the minimum period of this quasi-polynomial ($\lambda ^{(m)}_{w}(t) = \displaystyle {{{\frac{t-i}{w}}+m}\atopwithdelims (){m}}$ whenever $t\in \mathbb {Z}$ and $t\equiv i\, (mod\, w)$, $0\le i\le w-1$). It follows that in this case w is a period of the dimension quasi-polynomial $\chi ^{(w)}_{A}(t)$, since every term in the sum (1) is of the form $\displaystyle {{\left\lfloor {\frac{t-{{\mathrm{ord}}}_{w}c_{\epsilon }}{w}}\right\rfloor + m}\atopwithdelims (){m}}$.

Now we extend previous considerations to subsets of $\mathbb {Z}^{m}$ ($m\in \mathbb {N}$, $m\ge 1$). We fix positive integers $w_{1},\dots , w_{m}$ (“weights”) and define the order of an m-tuple $a = (a_{1},\dots , a_{m})\in \mathbb {Z}^{m}$ (with respect to the given weights) as

$${{\mathrm{ord}}}_{w}a = w_{1}|a_{1}| + \dots + w_{m}|a_{m}|.$$

If $A\subseteq \mathbb {Z}^{m}$ and $r\in \mathbb {N}$, we set $A(r) = \{a\in A\,|\,{{\mathrm{ord}}}_{w}a\le r\}$.

In what follows the set $\mathbb {Z}^{m}$ will be considered as the union

$$\begin{aligned} \mathbb {Z}^{m} = \displaystyle \bigcup _{1\le j\le 2^{m}}\mathbb {Z}_{j}^{(m)} \end{aligned}$$

(2)

where $\mathbb {Z}_{1}^{(m)}, \dots , \mathbb {Z}_{{2^{m}}}^{(m)}$ are all distinct Cartesian products of m factors each of which is either $\mathbb {Z}_{-}$ or $\mathbb {N}$. We assume that $\mathbb {Z}_{1}^{(m)} = \mathbb {N}^{m}$ and call a set $\mathbb {Z}_{j}^{(m)}$ ($1\le j\le 2^{m}$) an orthant of $\mathbb {Z}^{m}$.

The set $\mathbb {Z}^{m}$ will be treated as a partially ordered set with respect to the order $\trianglelefteq$ defined as follows: $(x_{1}, \dots , x_{m})\trianglelefteq (y_{1}, \dots , y_{m})$ if and only if $(x_{1}, \dots , x_{m})$ and $(y_{1}, \dots , y_{m})$ belong to the same orthant of $\mathbb {Z}^{m}$ and $|x_{i}|\le |y_{i}|$ for $i=1,\dots , m$. For any set $B\subseteq \mathbb {Z}^{m}$, $\mathcal{{V}}_{B}$ will denote the set of all m-tuples in $\mathbb {Z}^{m}$ that exceed no element of B with respect to $\trianglelefteq$. Furthermore, we define a mapping $\rho :\mathbb {Z}^{m}\rightarrow \mathbb {N}^{2m}$ such that

$$\rho (z_{1},\dots , z_{m}) = (\max \{z_{1}, 0\},\dots , \max \{z_{m}, 0\}, \max \{-z_{1}, 0\}, \dots , \max \{-z_{m}, 0\}).$$

The proof of the following theorem can be obtained by mimicking the proof of the first three parts of Theorem 2.5.5 of [7] (with the use of Theorem 2 instead of Theorem 2.2.5 of [7]).

Theorem 3

Let $\mathcal {A}$ be a subset of $\mathbb {Z}^{m}$. Then there exists a quasi-polynomial $\phi ^{(w)}_{\mathcal {A}}(t)$ with the following properties.  

(i) :

$\phi ^{(w)}_{A}(r) = {{\mathrm{Card}}}\,\mathcal{{V}}_{\mathcal {A}}(r)$ for all sufficiently large $r\in \mathbb {N}$;

(ii) :

$\deg \,\phi ^{(w)}_{\mathcal {A}}\le m$.

(iii) :

Let $\rho (\mathcal {A}) = A$ ($A\subseteq \mathbb {N}^{2m}$) and let $b_{i}$ ($1\le i\le m$) be a 2m-tuple in $\mathbb {N}^{2m}$ whose ith and $(m+i)$th coordinates are 1 and all other coordinates are zeros. Then for all $r\in \mathbb {N}$, $\phi ^{(w)}_{\mathcal {A}}(r) = \chi ^{(w)}_{B}(r)$ where $B = A\cup \{b_{1}\}\cup \dots \cup \{b_{m}\}$ and $\chi ^{(w)}_{B}(t)$ is the dimension quasi-polynomial of the set $B\subseteq \mathbb {N}^{2m}$ associated with the weight vector $(w_{1},\dots , w_{m}, w_{1},\dots , w_{m})$.

 

The quasi-polynomial $\phi ^{(w)}_{\mathcal {A}}(t)$ is called the dimension polynomial of the set $\mathcal {A}\subseteq \mathbb {Z}^{m}$ associated with the weight vector $(w_{1},\dots , w_{m})$.

4 The Main Theorem

Let K be an inversive difference field of characteristic zero with a basic set of translations $\sigma = \{\alpha _{1},\dots , \alpha _{m}\}$ that are assigned positive integer weights $w_{1}, \dots , w_{m}$, respectively. As before, let $\varGamma$ denote the free commutative group generated by the set $\sigma$. For any element $\gamma = \alpha _{1}^{k_{1}}\dots \alpha _{m}^{k_{m}}\in \varGamma$, the number

$${{\mathrm{ord}}}_{w}\gamma = \displaystyle \sum _{i=1}^{m}w_{i}|k_{i}|$$

will be called the order of $\gamma$. Furthermore, for any $r\in \mathbb {N}$, we set

$$\varGamma _{w}(r) = \{\gamma \in \varGamma \,|\,{{\mathrm{ord}}}_{w}\gamma \le r\}.$$

The following theorem establishes the existence of a dimension quasi-polynomial associated with a finitely generated inversive difference field extension with weighted basic translations.

Theorem 4

With the above notation, let $L = K\langle \eta _{1},\dots ,\eta _{n}\rangle ^{*}$ be a $\sigma ^{*}$-field extension of K generated by a finite set $\eta =\{\eta _{1},\dots ,\eta _{n}\}$. For any $r\in \mathbb {N}$, let $L_{r} = K(\{\gamma \eta _{i}\,|\gamma \in \varGamma _{w}(r), \, 1\le i\le n\})$. Then there exists a quasi-polynomial $\varPsi ^{(w)}_{\eta |K}(t)$ such that

 

(i) :

$\varPsi ^{(w)}_{\eta |K}(r) = {{\mathrm{trdeg}}}_{K}L_{r}$ for all sufficiently large $r\in \mathbb {N}$.

(ii) :

$\deg \varPsi ^{(w)}_{\eta |K}\le m$.

(iii) :

$\varPsi ^{(w)}_{\eta |K}$ is an alternating sum of Ehrhart quasi-polynomials associated with rational conic polytopes in $\mathbb {N}^{m}$.

(iv) :

The degree and leading coefficient of the quasi-polynomial $\varPsi ^{(w)}_{\eta |K}$ are constants that do not depend on the set of $\sigma ^{*}$-generators $\eta$ of the extension L/K. Furthermore, the coefficient of $t^{m}$ in $\varPsi ^{(w)}_{\eta |K}$ can be represented as $\displaystyle \frac{a2^{m}}{m!w_{1}\dots w_{m}}$ where a is equal to the $\sigma$-transcendence degree of L/K.

 

The quasi-polynomial $\varPsi ^{(w)}_{\eta |K}(t)$ is called the $\sigma ^{*}$ -dimension quasi-polynomial of the $\sigma ^{*}$-field extension L/K associated with the system of $\sigma ^{*}$-generators $\eta$.

In order to prove Theorem 4 we need some results on reduction and autoreduced sets in the ring of inversive difference polynomials $K\{y_{1},\dots , y_{n}\}^{*}$. In what follows we will consider $\mathbb {Z}^{m}$ as the union (2) of $2^{m}$ orthants $\mathbb {Z}_{j}^{(m)}$ ($1\le j\le 2^{m}$), and the group $\varGamma$ will be considered as a union $\varGamma = \bigcup _{j=1}^{2^{m}}\varGamma _{j}$ where $\varGamma _{j} = \{\alpha _{1}^{k_{1}}\dots \alpha _{m}^{k_{m}}\,|\,(k_{1},\dots , k_{m})\in \mathbb {Z}_{j}^{(m)}\}$ ($1\le j\le 2^{m}$).

Let $K\{y_{1},\dots , y_{n}\}^{*}$ be an algebra of $\sigma ^{*}$-polynomials in $\sigma ^{*}$-indeterminates $y_{1},\dots , y_{n}$ over K; as before, $\varGamma Y$ will denote the set of terms $\{\gamma y_{i} | \gamma \in \varGamma , 1\le i\le n \}$. By the order of a term $u = \gamma y_{j}$ we mean the order of the element $\gamma \in \varGamma$. Setting $(\varGamma Y)_{j} = \{\gamma y_{i}\,|\,\gamma \in \varGamma _{j}, 1\le i\le n \}$ ($j=1,\dots , 2^{m}$) we obtain a representation of the set of terms as a union $\varGamma Y = \displaystyle \bigcup _{j=1}^{2^{m}}(\varGamma Y)_{j}$.

Definition 1

A term $v\in \varGamma Y$ is called a transform of a term $u\in Y$ if and only if u and v belong to the same set $(\varGamma Y)_{j} \, (1\le j\le 2^{m})$ and $v = \gamma u$ for some $\gamma \in \varGamma _{j}$ (in particular, u and v involve the same $\sigma ^{*}$-indeterminate $y_{i}$, $1\le i\le n$). If $\gamma \ne 1$, v is said to be a proper transform of u.

Definition 2

A well-ordering of the set $\varGamma Y$ is called a ranking of the family of $\sigma ^{*}$-indeterminates $y_{1},\dots , y_{n}$ (or a ranking of the set of terms $\varGamma Y$) if it satisfies the following conditions. (We use the standard symbol $\le$ for the ranking; it will be always clear what order is denoted by this symbol.)

 

(i) :

If $u\in (\varGamma Y)_{j}$ and $\gamma \in \varGamma _{j}$ ($1\le j\le 2^{m}$), then $u\le \gamma u$.

(ii) :

If $u, v\in (\varGamma Y)_{j}$ ($1\le j\le 2^{m}$), $u\le v$ and $\gamma \in \varGamma _{j}$, then $\gamma u \le \gamma v$.

 

A ranking of the $\sigma ^{*}$-indeterminates $y_{1},\dots , y_{n}$ is called orderly if for any $j=1,\dots , 2^{m}$ and for any two terms $u, v \in \varGamma Y$, the inequality ${{\mathrm{ord}}}_{w}u < {{\mathrm{ord}}}_{w}v$ implies that $u < v$ (as usual, $v < w$ means $v\le w$ and $v\ne w$). As an example of an orderly ranking one can consider the standard ranking defined as follows: $u = \alpha _{1}^{k_{1}}\dots \alpha _{m}^{k_{m}}y_{i}\le v = \alpha _{1}^{l_{1}}\dots \alpha _{m}^{l_{m}}y_{j}$ if and only if the $(2m+2)$-tuple $(\displaystyle \sum _{\nu = 1}^{m}|k_{\nu }|, |k_{1}|,\dots , |k_{m}|, k_{1},\dots , k_{m}, i)$ is less than or equal to the $(2m+2)$-tuple $(\displaystyle \sum _{\nu = 1}^{m}|l_{\nu }|, |l_{1}|,\dots , |l_{m}|, l_{1},\dots , l_{m}, j)$ with respect to the lexicographic order on $\mathbb {Z}^{2m+2}$.

In what follows, we assume that an orderly ranking $\le$ of the set of $\sigma ^{*}$-indeterminates $y_{1},\dots , y_{n}$ is fixed. If $A\in K\{y_{1},\dots , y_{n}\}^{*}$, then the greatest (with respect to $\le$) term from $\varGamma Y$ that appears in A is called the leader of A; it is denoted by $u_{A}$. If $u = u_{A}$ and $d=\deg _{u}A$, then the $\sigma ^{*}$-polynomial A can be written as $A = I_{d}u^{d} + I_{d-1}u^{d-1}+\dots + I_{0}$ where $I_{k}$ ($0\le k\le d$) do not contain u. The $\sigma ^{*}$-polynomial $I_{d}$ is called the initial of A; it is denoted by $I_{A}$.

The ranking of the set of $\sigma ^{*}$-indeterminates $y_{1},\dots , y_{n}$ generates the following relation on $K\{y_{1},\dots , y_{n}\}^{*}$. If A and B are two $\sigma ^{*}$-polynomials, then A is said to have rank less than B (we write $A < B$) if either $A\in K, B\notin K$ or $A, B \in K\{y_{1},\dots , y_{n}\}^{*}\setminus K$ and $u_{A} < u_{B}$, or $u_{A}= u_{B} = u$ and $\deg _{u}A < \deg _{u}B$. If $u_{A} = u_{B} = u$ and $\deg _{u}A = \deg _{u}B$, we say that A and B are of the same rank and write ${{\mathrm{rk}}}\,A = {{\mathrm{rk}}}\,B$.

Let $A, B\in K\{y_{1},\dots , y_{n}\}^{*}$. The $\sigma ^{*}$-polynomial A is said to be reduced with respect to B if A does not contain any power of a transform $\gamma u_{B}$ ($\gamma \in \varGamma$) whose exponent is greater than or equal to $\deg _{u_{B}}B$. If $\mathcal {A}\subseteq K\{y_{1},\dots , y_{n}\}\setminus K$, then a $\sigma ^{*}$-polynomial $A\in K\{y_{1},\dots , y_{n}\}^{*}$, is said to be reduced with respect to $\mathcal {A}$ if A is reduced with respect to every element of the set $\mathcal {A}$.

A set $\mathcal {A}\subseteq K\{y_{1},\dots , y_{n}\}^{*}$ is said to be autoreduced if either it is empty or $\mathcal {A}\bigcap K = \emptyset$ and every element of $\mathcal {A}$ is reduced with respect to all other elements of $\mathcal {A}$. As it is shown in [9, Sect. 2.4], every autoreduced set is finite, distinct elements of an autoreduced set have distinct leaders, and one has the following result.

Theorem 5

Let $\mathcal{{A}} = \{A_{1},\dots , A_{p}\}$ be an autoreduced subset in $K\{y_{1},\dots , y_{n}\}^{*}$ and let $D\in K\{y_{1},\dots , y_{n}\}^{*}$. Furthermore, let $I(\mathcal{{A}})$ denote the set of all $\sigma ^{*}$-polynomials $B\in K\{y_{1},\dots , y_{n}\}$ such that either $B =1$ or B is a product of finitely many polynomials of the form $\gamma (I_{A_{i}})$ where $\gamma \in \varGamma ,\, i=1,\dots , p$. Then there exist $\sigma ^{*}$-polynomials $J\in I(\mathcal {A})$ and $E\in K\{y_{1},\dots , y_{n}\}$ such that E is reduced with respect to $\mathcal {A}$ and $JD\equiv E (mod\, [\mathcal {A}])$.

The transition from a $\sigma ^{*}$-polynomial D to the $\sigma ^{*}$-polynomial E (called a remainder of D with respect to $\mathcal{{A}}$) can be realized by the algorithm described in [9, p. 131]. In this case we say that D reduces to E modulo $\mathcal{{A}}$.

In what follows the elements of an autoreduced set will be always written in the order of increasing rank. If $\mathcal{{A}} = \{A_{1},\dots , A_{p}\}$ and $\mathcal{{B}} = \{B_{1},\dots , B_{q}\}$ are two autoreduced sets of $\sigma ^{*}$-polynomials, we say that $\mathcal {A}$ has lower rank than $\mathcal {B}$ and write ${{{\mathrm{rk}}}\,\mathcal{{A}}} < {{{\mathrm{rk}}}\,\mathcal{{B}}}$ if either there exists $k\in \mathbf{N},\, 1\le k\le \min \{p, q\}$, such that ${{\mathrm{rk}}}\,A_{i} = {{\mathrm{rk}}}\,B_{i}$ for $i=1,\dots , k-1$ and $A_{k} < B_{k}$, or $p > q$ and ${{\mathrm{rk}}}\,A_{i} = {{\mathrm{rk}}}\,B_{i}$ for $i=1,\dots , q$.

Mimicking the proof of [6, Chap. I, Proposition 3] we obtain that every nonempty family of autoreduced subsets contains an autoreduced set of lowest rank. In particular, if $\emptyset \ne J\subseteq K\{y_{1},\dots , y_{n}\}^{*}$, then the set J contains an autoreduced set of lowest rank called a characteristic set of J. We will need the following properties of characteristic sets that follow from Theorem 5 (see [9, Proposition 2.4.4]).

Proposition 1

Let K be an inversive difference ($\sigma ^{*}$-) field, J a $\sigma ^{*}$-ideal of the algebra of $\sigma ^{*}$-polynomials $K\{y_{1},\dots , y_{s}\}^{*}$, and $\mathcal{{A}}$ a characteristic set of J. Then  

(i) :

The ideal J does not contain nonzero $\sigma ^{*}$-polynomials reduced with respect to $\mathcal{{A}}$. In particular, if $A\in \mathcal{{A}}$, then $I_{A}\notin J$.

(ii) :

If J is a prime $\sigma ^{*}$-ideal, then $J = [\mathcal{{A}}]:\varUpsilon (\mathcal{{A}})$ where $\varUpsilon (\mathcal{{A}})$ denotes the set of all finite products of elements of the form $\gamma (I_{A})$ ($\gamma \in \varGamma , A\in \mathcal{{A}}$).

 

Proof of Theorem 4

Let P be the defining $\sigma ^{*}$-ideal of the $\sigma ^{*}$-field extension $L = K\langle \eta _{1},\dots , \eta _{n}\rangle ^{*}$, that is $P = {{\mathrm{Ker}}}(K\{y_{1},\dots , y_{n}\}^{*}\rightarrow L),\,\,\,\, y_{i}\mapsto \eta _{i}.$ Let $\mathcal{{A}} = \{A_{1},\dots , A_{d}\}$ be a characteristic set of P, let $u_{i}$ denote the leader of $A_{i}$ ($1\le i\le d$) and for every $j=1,\dots , n$, let

$$E_{j} = \{(k_{1},\dots , k_{m})\in \mathbb {Z}^{m} | \alpha _{1}^{k_{1}}\dots \alpha _{m}^{k_{m}}y_{j}\,\,\, \text {is a leader of a}\,\,\, \sigma \text {-polynomial in}\,\,\, \mathcal{{A}}\}.$$

Let $V = \{u\in \varGamma Y\,|\,u$ is not a transform of any $u_{i}$ ($1\le i\le s$)$\}$ and for every $r\in \mathbb {N}$, let $V(r) = \{u\in V\,|\,{{\mathrm{ord}}}_{w}\,u\le r\}$.

By Proposition 1, the ideal P does not contain non-zero difference polynomials reduced with respect to $\mathcal{{A}}$. It follows that for every $r\in \mathbb {N}$, the set $V_{\eta }(r) = \{v(\eta )\,|\,v\in V(r)\}$ is algebraically independent over K. Indeed, if there exists a nonzero polynomial $B\in K[X_{1},\dots , X_{k}]$ ($k> 0$) in k variables over K and elements $v_{1},\dots , v_{k}\in V_{\eta }(r)$ such that $B(v_{1}(\eta ),\dots , v_{k}(\eta )) = 0$. Then $B(v_{1},\dots , v_{k})\in P$ and this $\sigma$-polynomial is reduced with respect to $\mathcal{{A}}$, so we arrive at a contradiction.

If $A_{i}\in \mathcal{{A}}$ ($1\le i\le d$), then $A_{i}(\eta ) = 0$, hence $u_{i}(\eta )$ is algebraic over the field $K(\{\gamma \eta _{j}\,|\,\gamma y_{j} < u_{i}\, (\gamma \in \varGamma , \,1\le j\le n)\})$. Therefore, any transform $\theta u_{i}$ ($\theta \in \varGamma$) is algebraic over the field $K(\{\gamma \eta _{j}\,|\,\gamma y_{j} < \theta u_{i}\, (\gamma \in \varGamma , \,1\le j\le n)\})$. By induction on the well-ordered set $\varGamma Y$ (and using the fact that if $u, v\in \varGamma Y$ and $u < v$, then ${{\mathrm{ord}}}_{w}u\le {{\mathrm{ord}}}_{w}v$), we obtain that for every $r\in \mathbb {N}$, the field $L_{r} = K(\{\gamma \eta _{j}\,|\,\gamma \in \varGamma _{w}(r),\, 1\le j\le n\})$ is an algebraic extension of the field $K(\{v(\eta )\,|\,v\in V(r)\})$. It follows that $V_{\eta }(r)$ is a transcendence basis of $L_{r}$ over K and ${{\mathrm{trdeg}}}_{K}L_{r} = {{\mathrm{Card}}}\,V_{\eta }(r)$.

The number of terms $\alpha _{1}^{k_{1}}\dots \alpha _{m}^{k_{m}} y_{j}$ in V(r) is equal to the number of m-tuples $k = (k_{1},\dots , k_{m})\in \mathbb {Z}^{m}$ such that ${{\mathrm{ord}}}_{w}k\le r$ and k does not exceed any m-tuple in $E_{j}$ with respect to the order $\trianglelefteq$ on $\mathbb {Z}^{m}$. By Theorem 3, this number is expressed by a quasi-polynomial of degree at most m. Therefore, for all sufficiently large $r\in \mathbb {N}$ we have

$${{\mathrm{trdeg}}}_{K}L_{r} = {{\mathrm{Card}}}\,V_{\eta }(r) = \displaystyle \sum _{j=1}^{n}\phi ^{(w)}_{E_{j}}(r)$$

where $\phi ^{(w)}_{E_{j}}(t)$ is the dimension quasi-polynomial of the set $E_{j}\subseteq \mathbb {Z}^{m}$. It follows that the quasi-polynomial

$$\varPsi ^{(w)}_{\eta |K}(t) = \displaystyle \sum _{j=1}^{n}\phi ^{(w)}_{E_{j}}(t)$$

satisfies the first two conditions of Theorem 4. Since each $\phi ^{(w)}_{E_{j}}(t)$ is equal to a dimension quasi-polynomial $\chi ^{(w)}_{B_{j}}(t)$ of a subset $B_{j}\subseteq \mathbb {N}^{2m}$ (see part (iii) of Theorem 3) and by Theorem 2 each $\chi ^{(w)}_{B_{j}}(t)$ ($1\le j\le n$) is an alternating sum of Ehrhart quasi-polynomials associated with conic polytopes, $\varPsi ^{(w)}_{\eta |K}(t)$ has a similar representation and satisfies condition (iii) of Theorem 4.

If $\zeta = (\zeta _{1},\dots , \zeta _{k})$ is another system of $\sigma$-generators of the extension L/K, so that $L = K\langle \eta _{1},\dots , \eta _{n}\rangle ^{*} = K\langle \zeta _{1},\dots , \zeta _{k}\rangle ^{*}$, then there exists $q\in \mathbb {N}$ such that $\eta _{1},\dots , \eta _{n}\in K(\bigcup _{i=1}^{k}\varGamma _{w}(q)\zeta _{i})$ and $\zeta _{1},\dots , \zeta _{k}\in K(\bigcup _{i=1}^{n}\varGamma _{w}(q)\eta _{i})$. Therefore, for all sufficiently large $r\in \mathbb {N}$ (namely, for all $r\ge q$), one has

$$K(\bigcup _{i=1}^{n}\varGamma _{w}(r)\eta _{i})\subseteq K(\bigcup _{i=1}^{k}\varGamma _{w}(r+q)\zeta _{i})\,\,\, \text {and}\,\,\, K(\bigcup _{i=1}^{k}\varGamma _{w}(r)\zeta _{i})\subseteq K(\bigcup _{i=1}^{n}\varGamma _{w}(r+q)\eta _{i}),$$

that is, $\varPsi ^{(w)}_{\eta |K}(r)\le \varPsi ^{(w)}_{\zeta |K}(r+q)$ and $\varPsi ^{(w)}_{\zeta |K}(r)\le \varPsi ^{(w)}_{\eta |K}(r+q)$. It follows that the quasi-polynomials $\varPsi ^{(w)}_{\eta |K}(t)$ and $\varPsi ^{(w)}_{\zeta |K}(t)$ have equal degrees and equals leading coefficients.

In order to prove the last part of statement (iv) of our theorem, note first that if the elements $\eta _{1},\dots ,\eta _{n}$ are $\sigma$-algebraically independent over K, then one has

$$\varPsi ^{(w)}_{\eta |K}(t) = n\mu ^{(m)}_{w}(t)$$

(see Remark 1). Indeed, if $r\in \mathbb {N}$, and $\varOmega _{i}(r) = \{\omega = \alpha _{1}^{k_{1}}\dots \alpha _{m}^{k_{m}}\eta _{i}\,|\,k_{i}\in \mathbb {Z},\,\,{{\mathrm{ord}}}_{w}\xi \le r\}$ for $i = 1,\dots , n$, then $\bigcup _{i=1}^{n}\varOmega _{i}(r)$ is a transcendence basis of the field extension $K(\bigcup _{i=1}^{n}\varGamma _{w}(r)\eta _{i})/K$ and the number of elements of this basis is equal to $n{{\mathrm{Card}}}\{(k_{1},\dots , k_{m})\in \mathbb {Z}^{m}\,|\,\sum _{j=1}^{m}w_{j}|k_{j}|\le r\} = n\mu ^{(m)}_{w}(r)$. Now one can mimic the proof of the last part of [12, Theorem 4] (with the use of quasi-polynomials $\mu _{w}^{(m)}(t)$ instead of $\lambda _{w}^{(m)}(t)$) to obtain that the coefficient of $t^{m}$ in $\varPsi ^{(w)}_{\eta |K}$ can be represented as $\displaystyle \frac{a2^{m}}{m!w_{1}\dots w_{m}}$ where a is equal to the $\sigma$-transcendence degree of L/K. $\square$

Theorem 4 allows one to assign a quasi-polynomial to a system of algebraic difference equations with weighted basic translations

$$\begin{aligned} f_{i}(y_{1},\dots , y_{n}) = 0 \qquad (i=1,\dots , p) \end{aligned}$$

(3)

($f_{i},\in R = K\{y_{1},\dots , y_{n}\}$ for $i=1,\dots , p$) such that the $\sigma ^{*}$-ideal P of R generated by the $\sigma ^{*}$-polynomials $f_{1}, \dots , f_{p}$ is prime (e.g. to a system of linear difference equations). Systems of this form arise, in particular, as finite difference approximations of systems of PDEs with weighted derivatives (see, for example, [14, 15]).

Treating the quotient field $L = {{\mathrm{qf}}}(R/P)$ as a finitely generated $\sigma ^{*}$-field extension of K, $L = K\langle \eta _{1},\dots , \eta _{n}\rangle ^{*}$ where $\eta _{i}$ is the canonical image of $y_{i}$ in R/P, one can consider the $\sigma ^{*}$-dimension quasi-polynomial $\varPsi ^{(w)}(t) =\varPsi ^{(w)}_{\eta |K}(t)$ associated with this extension. This quasi-polynomial, that is called the $\sigma ^{*}$ -dimension quasi-polynomial of system (3), has a natural interpretation as the Einstein’s strength of the system of partial difference equations with weighted translations (see [9, Sect. 7.7]).

Example 2

Let K be an inversive difference field of zero characteristic with a basic set $\sigma = \{\alpha _{1}, \alpha _{2}\}$, where $\alpha _{1}$ and $\alpha _{2}$ are assigned weights 3 and 1, respectively, and let $K\{y\}^{*}$ be the ring of $\sigma ^{*}$-polynomials in one $\sigma ^{*}$-indeterminate y over K. Let us consider the $\sigma ^{*}$-equation

$$\begin{aligned}{}[a_{1}(\alpha _{1} + \alpha _{1}^{-1} -2) + a_{2}(\alpha _{2} + \alpha _{2}^{-1} - 2)]y = 0 \end{aligned}$$

(4)

where $a_{1}$ and $a_{2}$ are constants of the field K. As it is shown in [9, Example 7.8.9], the $\sigma ^{*}$-polynomials $A = [a_{1}(\alpha _{1} + \alpha _{1}^{-1} -2) + a_{2}(\alpha _{2} + \alpha _{2}^{-1} - 2)]y$, $\alpha _{1}^{-1}A = [a_{1}(1+ \alpha _{1}^{-2} - 2\alpha _{1}^{-1}) + a_{2}(\alpha _{1}^{-1}\alpha _{2} + \alpha _{1}^{-1}\alpha _{2}^{-1} - 2\alpha _{1}^{-1})]y$, and $\alpha _{1}^{-1}\alpha _{2}^{-1}A = [a_{1}(\alpha _{2}^{-1} + \alpha _{1}^{-2}\alpha _{2}^{-1} - 2\alpha _{1}^{-1}\alpha _{2}^{-1}) + a_{2}(\alpha _{1}^{-1} + \alpha _{1}^{-1}\alpha _{2}^{-2} - 2\alpha _{1}^{-1}\alpha _{2}^{-1})]y$ form a characteristic set of the prime $\sigma ^{*}$-ideal $[A]^{*}$ (clearly, it is irrelevant that all translations in [9] have weight 1). The leaders of these $\sigma ^{*}$-polynomials are the terms $\alpha _{1}y$, $\alpha _{1}^{-1}\alpha _{2}y$, and $\alpha _{1}^{-1}\alpha _{2}^{-2}y$, respectively, so the $\sigma ^{*}$-dimension polynomial of the Eq. (4) is equal to the dimension polynomial of the subset $\mathcal {M} = \{(1, 0), (-1, 1), (-1, -2)\}$ of $\mathbb {Z}^{2}$. In order to find this polynomial one can either represent it as an alternating sum of Ehrhart quasi-polynomials of conic polytopes (using a partition of the set $V_{\mathcal {M}}$ into cones and the principle of inclusion and exclusion, as it is done in [12, Example 2]) or compute the number of integer points of $V_{\mathcal {M}}$ directly (in this case $V_{\mathcal {M}}(r)$ consists of points (0, i) with $-r\le i\le r$, points (j, 0) with $-{\frac{r}{3}}\le j\le -1$, and points $(k, -1)$ with $-{\frac{r-1}{3}}\le k\le -1$). We obtain that dimension quasi-polynomial of the Eq. (4) is

$$\varPsi (t) ={\frac{8}{3}}r + \left[ 0, {\frac{1}{3}}, -{\frac{1}{3}}\right] _{r}.$$

This work was supported by the NSF grant CCF-1714425.