Differential Algebra Glossary
This glossary provides definitions for terms that are commonly used in the DifferentialAlgebra package documentation. Certain terms (for example, order and derivative) may have both technical and common meanings. A term is italicized when its technical meaning is used.
attribute: In this package, an attribute is a property of a regular differential chain. Seven attributes are defined: differential, prime, primitive, squarefree, coherent, autoreduced, and normalized. The two first attributes provide properties of the ideal defined by the regular differential chain. The other attributes provide properties of the differential polynomials that constitute the chain.
autoreduced: An attribute of regular differential chains. It indicates that the regular differential chain is autoreduced, in the sense that, for all differential polynomials p and q of the chain, the degree of p in the leading derivative of q is less than the degree of q in its leading derivative.
BLAD (Bibliotheques Lilloises d'Algebre Differentielle): Open source libraries, which are written in the C programming language and dedicated to differential elimination. The DifferentialAlgebra package uses the BLAD libraries for most computations.
block: A list of dependent variables plus a block-keyword. Blocks appear in the definition of rankings.
block-keyword: A keyword, which makes the ranking of a block precise. Five block-keywords are defined: grlexA, grlexB, degrevlexA, degrevlexB, and lex.
characteristic set: A particular case of a regular differential chain.
coherent: An attribute of regular differential chains. It indicates that the regular differential chain is coherent. This concept is described in the Regular Differential Chains section below.
component: In an intersection of differential ideals, presented by regular differential chains, one of the components of the intersection.
constant: An expression whose derivatives are all equal to zero.
degrevlexA: One of the block-keywords.
degrevlexB: One of the block-keywords.
Delta-polynomial: The Δ-polynomial defined by two differential polynomials is important for testing the coherence property of systems of partial differential equations. It plays the same role as the S-polynomials of the Groebner bases theory. Let Ai and Aj be two differential polynomials, whose leading derivatives vi and vj are derivatives of some same dependent variable u. Denote θi and θj the derivation operators associated to vi and vj and θi,j their least common multiple.
If θi,j is different from both θi and θj, then the Δ-polynomial defined by Ai and Aj is the differential polynomial Si θi,jθj Aj - Sj θi,jθi Ai, where Si and Sj denote the separants of Ai and Aj and the left multiplication by a derivation operator stands for a differentiation.
If θi,j is equal to θj (as an example), then the Δ-polynomial defined by Ai and Aj is the pseudo-remainder of Aj by θjθi Ai with respect to vj.
dependent variable: A variable that depends on the independent variables, for example, a function of the independent variables. In the classical books of differential algebra, it would be called a differential indeterminate.
dependent variable associated to a derivative: If v is a derivative of a dependent variable u, then u is said to be the dependent variable associated to v.
derivation: In this package, derivations are taken with respect to independent variables and are supposed to commute. The set of the derivations generates the monoid (semigroup) of the derivation operators, which are denoted multiplicatively. In the classical books of differential algebra, derivations are simply abstract operations which satisfy the axioms of derivations.
derivation operator: A power product of independent variables denoting iterated derivations. For example, differentiating a differential polynomial p, with respect to the derivation operator x2⁢y, consists of differentiating p twice with respect to x, then once with respect to y. The identity derivation operator is denoted as 1.
derivation operator associated to a derivative: If v is a derivative of a dependent variable u, then there exists a derivation operator, θ, such that differentiating u with respect to θ gives v. The derivation operator θ is called the derivation operator associated to v.
derivative: A derivative of a dependent variable.
differential: One of the attributes of regular differential chains. It indicates that the ideal defined by the chain is differential. The presence of differential implies the presence of squarefree, and coherent in the partial differential case.
differential algebra: The mathematical theory that provides the theoretical basis for this package.
differential ideal: Mathematically, an ideal which contains the derivatives of some element p, whenever it contains p. In this package, a differential ideal is a polynomial ideal which is presented either by a single regular differential chain or by a list of regular differential chains. Lists of regular differential chains represent the intersection of the differential ideals defined by the chains. These are called the components of the intersection. The chains in a list must belong to the same differential polynomial ring. The empty list denotes the unit differential ideal. The zero differential ideal can be represented by a regular differential chain. The concept of differential ideals is described in the Differential Ideals section below.
differential indeterminate: An abstract symbol standing for a function, over which the derivations act. In this package, the expression dependent variable is preferred.
differential polynomial: A polynomial, with (usually) rational coefficients, whose variables are either derivatives or independent variables. In some contexts, the field of coefficients may be a non-trivial differential field.
differential ring: Mathematically, a ring endowed with finitely many derivations, which (in our case) are supposed to commute. In this package, a differential ring is a data structure representing a polynomial differential ring, endowed with a ranking, and other minor features. In the case of only one derivation, the ring is said to be ordinary. In the case of two or more derivations, it is said to be partial. In this package, a ring may be endowed with no derivation. In this case, it is no longer differential, and, the use of other packages, such as RegularChains or Groebner is recommended.
grlexA: One of the block-keywords.
grlexB: One of the block-keywords.
inconsistent: An inconsistent system of differential polynomials is a system which has no solution. The differential ideal generated by an inconsistent system is the unit ideal, which is presented, in this package, by the empty list.
independent variable: A variable, with respect to which derivations are taken. Unless stated otherwise, a dependent variable is supposed to depend on all of the independent variables. Common examples are the time t, and the space variables x, y, z.
initial: The initial of a non-numeric differential polynomial p is the leading coefficient of p, regarded as a univariate polynomial with respect to its leading derivative.
irredundant: A representation of an ideal J as an intersection of ideals I1, ..., In is said to be irredundant if, given any two different indices j,k the ideal Ij is not included in the ideal Ik. In general, the representations computed by the RosenfeldGroebner algorithm are redundant. This issue is addressed in a following section.
leading derivative: The leading derivative v of a non-numeric differential polynomial p, is the highest derivative, with respect to some given ranking, such that the degree of p in v is positive. In this package, the leading derivative of differential polynomials which only depend on independent variables is defined.
leading rank: The leading rank of a differential polynomial p is the rank vd such that v is the leading derivative of p, and, d is the degree of p in v. In this package, the leading rank of differential polynomials which do not depend on any derivative is defined. In particular, the leading rank of 0 is 0, the one of any other rational number is 1.
lex: One of the block-keywords.
normalized: An attribute of regular differential chains. It indicates that the regular differential chain is normalized, in the sense that, the initials of the differential polynomials of the chain do not depend on any leading derivative of any element of the chain. The presence of normalized implies the presence of autoreduced and primitive. Regular differential chains which hold these three attributes are canonical representatives of the ideals that they define (in the sense that they only depend on the ideal and on the ranking).
numeric: A numeric differential polynomial is a differential polynomial which does not depend on any derivative or any independent variable.
order: The order of a derivative is the total degree of its associated derivation operator. The order of a differential polynomial is the maximum of the orders of the derivatives it depends on.
orderly: A ranking is orderly if, for all derivatives u and v, u is higher than v whenever the order of u is greater than the order of v.
ordinary: An ordinary differential ring is a ring endowed with a single derivation.
partial: A partial differential ring is a ring endowed with two or more derivations.
prime: An ideal is prime if, whenever it involves some product p⁢q, it involves at least one the factors. Any prime ideal is radical. A prime differential ideal is a differential ideal, which is prime.
prime: One of the attributes of regular differential chains. It indicates that the ideal defined by the chain is prime. The presence of prime implies the presence of squarefree. The changing of ranking that can be performed using RosenfeldGroebner, for example, only apply to prime ideals. Many computations on regular differential chains are simplified, when the ideal that they define are known to be prime.
primitive: An attribute of regular differential chains. It indicates that each differential polynomial of the chain is primitive, in the sense that the gcd of its coefficients is equal to 1. Chain differential polynomials are regarded as univariate polynomials in their leading derivatives. Their coefficients are viewed as multivariate polynomials over the ring of the integers.
proper derivative: A derivative v is said to be a proper derivative of a derivative u, if v is a derivative of u and is different from u.
radical: An ideal I of a ring R is said to be radical if it involves some element p whenever it involves any power pd of p, where d is any non-negative integer. The radical of an ideal I is the set of all the elements p of R, a power of which belongs to I. The radical of an ideal is an ideal. The radical of a differential ideal is a differential ideal.
rank: A derivative, or, an independent variable, raised to some positive integer. In addition, the two special ranks 0 and 1 are defined. Any ranking extends to a total ordering on ranks: 0 is less than 1, which is less than any other rank. Two ranks un and vm are compared by comparing, first, u and v, then, the exponents n and m.
ranking: Any total ordering over the set of the derivatives, which satisfies the two axioms of rankings. In this package, rankings are extended to the set of the independent variables. This concept is described in the Rankings section below.
redundant: Not irredundant. See the Irredundant definition above.
redundant component: In an intersection of a differential ideal, a component which contains another component.
regular differential chain: A data structure containing a list of differential polynomials sorted by increasing rank, plus some minor features. A few variants of regular differential chain are implemented. These variants can be selected by customizing the attributes of the chain. This concept is described in the Regular Differential Chains section below.
saturation: If I is an ideal of a ring R and M is a multiplicative family of R, then the saturation of I by M is the set J of all the elements p of R such that, m⁢p belongs to I, for some m of M. The saturation of an ideal is an ideal. The saturation of a differential ideal is a differential ideal.
separant: The separant of a non-numeric differential polynomial p, is the partial derivative of p with respect to its leading derivative.
squarefree: An attribute of regular differential chains. It indicates that the regular differential chain is squarefree. This concept is described in the Regular Differential Chains section.
tail: The tail of a non-numeric differential polynomial p, is equal to p−c⁢vd where c is the initial of p and vd is its leading rank.
This section describes some of the concepts mentioned in the glossary in more detail.
A ranking is any total ordering over the set of the derivatives (in this package, rankings are extended to the independent variables), which satisfies the two axioms of rankings:
Each derivative u is less than any of its proper derivatives.
If u and v are derivatives, such that u is less than v and x is any independent variable, then the derivative of u with respect to x is less than the derivative of v with respect to x.
In this package, rankings are defined by the list x1 > ... > xp of the independent variables plus a list b1 >> ... >> bn of blocks. Each block b is defined by a list u1 > ... > um of dependent variables plus a block-keyword, which is grlexA, grlexB, degrevlexA, degrevlexB or lex. Any dependent variable must appear in exactly one block.
The >> operator between blocks indicates a block elimination ranking: if bi >> bj are two blocks, vi is any derivative of any dependent variable occurring in bi, and, vj is any derivative of any dependent variable occurring in bj, then vi > vj.
Within a given block b = u1 > ... > um, in the ordinary differential case (only one derivation), the derivatives are ordered by the unique orderly ranking such that u1 > ... > um.
Within a given block b = u1 > ... > um, in the partial differential case (two or more derivations), the block-keyword of b is necessary to precise the ranking. Consider two derivatives vi and vj of two dependent variables ui and uj, such that i >= j. Denote θi and θj as the derivation operators associated to these two derivatives. In the sequel, θj<θi (lex) means that θj<θi with respect to the lexicographical order of the Groebner bases theory, defined by x1 > ... > xp, while, θj<θi (degrevlex) means that θj<θi with respect to the degree reverse lexicographic order. Depending on the block-keyword of b, listed below, one has vj<vi if the following condition is satisfied:
grlexA. If the order of vi is greater than the one of vj else, if the orders are equal and i<j else, if the orders are equal and i=j and θj<θi (lex).
grlexB. If the order of vi is greater than the one of vj else, if the orders are equal and θj<θi (lex) else, if θi=θj and i<j.
degrevlexA. If the order of vi is greater than the one of vj else, if the orders are equal and i<j else, if the orders are equal and i=j and θj<θi (degrevlex).
degrevlexB. If the order of vi is greater than the one of vj else, if the orders are equal and θj<θi (degrevlex) else, if θi=θj and i<j.
lex. If θj<θi (lex) else, if θi=θj and i<j.
Regular Differential Chains
Regular differential chains generalize the regular chains of the non-differential polynomial algebras (see the RegularChains package and [ALM99]) and the characteristic sets of classical differential algebra. In the sequel, one assumes that a ranking is fixed, and therefore that each non-numeric differential polynomial admits a leading derivative.
A regular differential chain appears as a list of differential polynomials A1, ..., Ar with rational numbers for coefficients. Each differential polynomial Ai admits a leading derivative, vi which is a derivative. The list A1, ..., Ar is sorted by increasing leading rank.
The set A1, ..., Ar is differentially triangular and partially autoreduced:
Given any two different indices i,j, the leading derivative vi is not a derivative of vj.
Given any two indices i,j, the differential polynomial Ai does not depend on any proper derivative of vi.
At this stage, one needs to introduce the polynomial ring R0 = k [v1, ..., vr], which is obtained by moving into the base field, all the independent variables and derivatives, the Ai depend on, but which are not the leading derivative of any Ai.
The set A1, ..., Ar is a squarefree regular chain:
Given any index i, the initial of Ai is an invertible element of R0/I where I denotes the ideal generated by A1, ..., Ai−1 in the ring R0.
Given any index i, the separant of Ai is an invertible element of R0/I where I denotes the ideal generated by A1, ..., Ai in the ring R0.
At this stage, the polynomial system Av must be introduced, where v is a derivative. It is the set of all the derivatives of the differential polynomials Ai whose leading derivatives are strictly less than v. The ring Rv must also be introduced. It is obtained by moving into the base field of the polynomials, all the independent variables and the derivatives, the elements of Av depend on, but which are not the leading derivative of any element of Av.
In the case of partial differential systems, the set A1, ..., Ar is coherent: given any two different indices i,j, such that vi and vj are derivatives of some same dependent variable u, the Δ-polynomial defined by Ai and Aj is zero in the ring Rθi,j⁢u/I where θi,j⁢u is least common derivative of vi and vj and I denotes the ideal generated by Aθi,j⁢u in Rθi,j⁢u.
Every regular differential chain A1, ..., Ar, of a polynomial differential ring R, defines a differential ideal I, which is the set of all the differential polynomials F such that, for some power product H of the initials and the separants of the Ai, the differential polynomial H⁢F is a finite linear combination of the derivatives of the Ai, with differential polynomials of R for coefficients.
One stresses the fact the chain A1, ..., Ar is not a generating family of I. However, it completely defines I and permits to compute a normal form of the residue class of any differential polynomial in R/I. See NormalForm. In particular:
It permits to decide membership in I, that is, zero in R/I: a differential polynomial F belongs to I if and only if its normal form is 0.
It permits to decide if a differential polynomial F is regular modulo I, that is, a non-zero divisor in R/I.
Given any system of differential polynomials F1, ..., Fs and any ranking, it is possible to compute a representation of the radical J of the differential ideal generated by this system, as a finite intersection of radical differential ideals I1, ..., In, presented by regular differential chains C1, ..., Cn. See RosenfeldGroebner [BLOP95,BLOP09]. See also [W98,LW99,H00,BKM01]. This representation permits to decide membership in J: a differential polynomial F belongs to J if and only if it belongs to each differential ideal Ik, i.e., if and only if its normal forms, with respect to all the regular differential chains Ck, are all 0. See BelongsTo.
One stresses the fact that, in general, the computed representation C1, ..., Cn is redundant. Indeed, the problem of deciding whether two differential ideals presented by regular differential chains are included in each other, is still open. In the particular case of a differential ideal generated by a single differential polynomial, this problem is, however, solved, thanks to the Low Power Theorem. See RosenfeldGroebner and its singsol = essential option [H99].
During the decomposition process, in general, the coefficients of the differential polynomials are assumed to lie in the field Q (x1, ..., xp) obtained by adjoining the independent variables to the field of the rational numbers. In particular, the computed regular differential chains do not involve any differential polynomial which only depends on the independent variables. In this package, it is, however, possible to compute decompositions of radical differential ideals generated by differential polynomials with coefficients in more sophisticated differential fields.
Let C be a regular differential chain of a differential polynomial ring R and F be a differential polynomial of R. Let I be the differential ideal defined by C. The normal form of F with respect to C is a rational differential fraction P/Q such that
Q is regular (that is, a non-zero divisor) in R/I.
P/Q is equivalent to F modulo I, in the sense that Q⁢F−P belongs to I.
P is reduced with respect to C, in the sense that, given any leading rank vd of any element of C, it does not depend on any proper derivative of v, and, has degree less than d, in v.
Q does not depend on any derivative of v, where v denotes any leading derivative of any element of C.
The normal form P/Q of F with respect to C is a canonical representative of the residue class of F in R/I, in the sense that
P/Q is 0 if and only if F belongs to I.
If F is equivalent to H modulo I, then the normal forms of F and H, with respect to C, are equal.
The normal form of F can be computed by means of the NormalForm function [BL00].
Let us extend the above definition and consider a rational differential fraction F/G, where F and G are differential polynomials of R. The NormalForm function can be used to compute a normal form of F/G, with respect to C. If it succeeds, then it returns a rational differential fraction P/Q such that
P/Q is equivalent to F/G modulo I, in the sense that Q⁢F−G⁢P belongs to I.
P is reduced with respect to C.
Q does not depend on any derivative of any leading derivative of C.
If it succeeds, then G is regular in R/I, and the normal form P/Q is a canonical representative of the residue class of F/G in the total fraction ring of R/I, in the sense that
If F/G is equivalent to H/K modulo I (with K regular modulo I), then the normal forms of F/G and H/K with respect to C are equal.
The NormalForm function may fail to compute a normal form of F/G in the following cases:
If G is zero in R/I.
If G is a zero-divisor in R/I.
If the function is led to invert another zero-divisor in R/I, during the normal form computation.
However, for each rational differential fraction F/G, it is possible to split C into finitely many regular differential chains C1, ..., Cn, Cn+1, ..., Cn+p such that, denoting Ik the radical differential ideal defined by Ck
The normal form of F/G can be computed, with respect to Ck, for 1 <= k <= n.
G is zero in R/Ik, for n+1 <= k <= n+p.
The differential ideal I is equal to the intersection of the differential ideals Ik, for 1 <= k <=