Footnotes

...<#27#>Differential!field<#27#>

<#3515#><#28#>Id est<#28#> a field which is endowed of an operation (differentiation) #math107#⋅' : k→k which satisfies, for each a, b∈k,

#math108#(a + b)' = a' + b',
#math109#(ab)' = a'b + ab'.

The elements a∈k for which a' = 0 are called <#32#>constants<#32#>. Note that, setting

b : = 0 in (1) we have 0' = 0, and
#math110#b : = 1, a≠ 0 in (2) we have 1' = 0.

It is then easy to deduce that from the equalities

#math111#(m + 1)' = m' + 1' = m',
#math112#0 = 0' = (m + (- m))' = m' + (- m)'#tex2html_wrap_inline10015#(- m)' = - (m'),
#math113#0 = (m⋅m^-1)' = m(m^-1)' + m^-1m'#tex2html_wrap_inline10017#(m^-1)' = - #tex2html_wrap_inline10018#,

satisfied by each m≠ 0, 6 that each #math114#a∈#tex2html_wrap_inline10021#Q⊂k is a constant. <#3515#>

...Y^(p)

<#3516#>And the p^th derivative of Y^(q) is Y^(q+p) for each integers p and q.<#3516#>

...it

<#3517#>which in fact (compare (3) in the remark above) is an <#100#>intersection<#100#> of differential ideals.<#3517#>

...ideal

<#3518#>The argument consists in proving that, for each $&pi#pi;&isin#in;<#101#>N<#101#>, &pi#pi;&ne#neq;0,$ and each differential polynomial $A&isin#in;k{Y_1,..., Y_n}$ the following holds:

$A^<#103#>&pi#pi;-1<#103#>A'&isin#in;[A^&pi#pi;]$;
$A^<#104#>&pi#pi;-&delta#delta;<#104#>A'^<#105#>2&delta#delta;-1<#105#>&isin#in;[A^&pi#pi;] A^<#106#>&pi#pi;-&delta#delta;-1<#106#>A'^<#107#>2&delta#delta;+1<#107#>&isin#in;[A^&pi#pi;]$, for each $&delta#delta;&isin#in;<#108#>N<#108#>$, $1&le#leq;&delta#delta;;SPMlt;&pi#pi;$,
$A'^<#109#>2&pi#pi;-1<#109#>&isin#in;[A^&pi#pi;]$,
$A&isin#in;{&Lambda#Lambda;}A'&isin#in;{&Lambda#Lambda;}.$

In fact:

$A^<#112#>&pi#pi;-1<#112#>A' = &pi#pi;^<#113#>-1<#113#>(A^&pi#pi;)'&isin#in;[A^&pi#pi;]$;
$B := (&pi#pi;-&delta#delta;)A^<#114#>&pi#pi;-&delta#delta;-1<#114#>A'^<#115#>2&delta#delta;<#115#>+ (2&delta#delta;-1)A^<#116#>&pi#pi;-&delta#delta;<#116#>A'^<#117#>2&delta#delta;-2<#117#>A;SPMquot; = (A^<#118#>&pi#pi;-&delta#delta;<#118#>A'^<#119#>2&delta#delta;-1<#119#>)'&isin#in;[A^&pi#pi;]$ so that,
#math123#
(π - δ)A^π-δ-1A'^2δ+1 = A'B - (2δ -1)A^π-δA'^2δ-1A;SPMquot;∈[A^π].
Since $A^<#124#>&pi#pi;-&delta#delta;<#124#>A'^<#125#>2&delta#delta;-1<#125#>&isin#in;[A^&pi#pi;]$ for $&delta#delta;= 1$ by (1) iteratively (2) implies
#math124#
A^π-δ-1A'^2δ+1∈[A^π]
for $&delta#delta;= &pi#pi;-1$ <#128#>id est<#128#> $A'^<#129#>2&pi#pi;-1<#129#>&isin#in;[A^&pi#pi;]$.
Let $&pi#pi;$ be such that $A^&pi#pi;&isin#in;[&Lambda#Lambda;]$; then by the previous result $A'^<#130#>2&pi#pi;-1<#130#>&isin#in;[A^&pi#pi;]&sub#subset;[&Lambda#Lambda;]$ whence $A'&isin#in;{&Lambda#Lambda;}.$

<#3518#>

...that

<#3519#>We must consider also the case $j = 0$, where, with a slight abuse of notation, we set $Y_<#140#>i0<#140#> := Y_i.$<#3519#>

...$A_i

<#195#>Of course $r &le#leq; n.$<#195#>

...a

<#3521#> In fact, since S_j is free of Y_a, we need only to treat the case in which G depends on Y_a and its derivates; denoting g the order of G in Y_a, clearly the order of D in Y_a does not exceed g and, in case its value is exactly g, the assumption that his degree δ in Y_ag is higher of the one of G implies that some term of C is divisible by #math134#Y_ag^δ so that some term of #math135#CA_j^(l) is divisible by #math136#Y_phY_pg^δ; this is a contradiction since no such term occurs neither in S_j^vG --- G has no term divisible by #math137#Y_pg^δ --- nor in D which has no term divisible by Y_ph.<#3521#>

...choices

<#3522#>This means that we must pick a reduced polynomial

#math151#

A_i∈k{V₁,…, V_d, Z₁,…, Z_i-1}[Z_i, Z_i1,^..., Z_i q-1][Z_iq]

of minimal degree in $Z_<#523#>iq<#523#>$ among all possible choices, where $q$, the order of $A_i$ in $Z_i$, is the minimal value for which

#math152#

#tex2html_wrap_indisplay10200#∩k{V₁,…, V_d, Z₁,…, Z_i-1}[Z_i, Z_i1,^..., Z_i q-1][Z_iq]≠∅.

<#3522#>

...argument

<#3523#>Ritt J.F., <#640#>Differential Algebra<#640#>, A.M.S. Colloquium Publications <#641#>33<#641#> (1950) p.84.

I just adapted the notation.<#3523#>

...ideal

<#3524#>which is $<#644#>I<#644#>_j := <#645#>I<#645#>&cap#cap;k[V_1,...,V_d,Z_1,...,Z_j]$.<#3524#>

...Thus

<#3525#>Remark that, by assumption, $B$ is a nonzero polynomial contained in $<#656#>I<#656#>'$, which is reduced with respect to ${A_1,...,A_<#657#>r<#657#>}$ and of lower rank. So we have just reached a contradiction.<#3525#>

...Then

<#3526#>$B&isin#in;k[V_1,...,V_d] B<#660#>I<#660#>$.<#3526#>

...degree

<#662#>Necessarily the degree in $Z_p$ of $B$ is lower of that of $A_p$.<#662#>

...zero

<#3527#>$D&isin#in;<#667#>I<#667#>$.<#3527#>

...linear

<#3528#><#669#>Id est<#669#> $JD&isin#in;(A_1,...,A_<#670#>p-1<#670#>) = <#671#>I<#671#>(A_1,...,A_<#672#>p-1<#672#>)$.<#3528#>

...#tex2html_wrap_inline10440#

<#3537#>We can of course assume that $A_1$ is of positive class, otherwise $<#781#>I<#781#> = (1)$ and we are through.<#3537#>

...Ritt

<#3538#>In the Preface of his book <#822#>Differential Algebra<#822#>, A.M.S. Colloquium Publications <#823#>33<#823#> (1950), p.iv<#3538#>

...book

<#3539#>Ritt J.F., <#824#>Differential Equations from the Algebraic Standpoint<#824#>, A.M.S. Colloquium Publications <#825#>14<#825#> (1932).<#3539#>

...#math210#integration

<#3540#>The reference is to J. Drach, <#828#>Essai sur la théorie général de l'integration et sur la classification des Trascendentes<#828#> Ann. Éc. Norm. $3^e$ série <#829#>15<#829#> (1898) 245--384.<#3540#>

...solver

<#3541#>Ritt J.F., <#839#>Differential Algebra<#839#>, A.M.S. Colloquium Publications <#840#>33<#840#> (1950), p.95-98.<#3541#>

...whether

<#3542#>Essentially Ritt proposes the primality test discussed in Section~35.4:

the rôle used there by the Gröbner basis $G'$ is taken here by the characteristic set $<#847#>A<#847#>^*$;
the test $<#848#>I<#848#> : I^&infin#infty;= <#849#>I<#849#>$ is not required since, in this setting
#math211#
#tex2html_wrap_indisplay10472# : I^∞ = #tex2html_wrap_indisplay10473##tex2html_wrap_indisplay10474#I(#tex2html_wrap_indisplay10477#A^*) : I^∞#tex2html_wrap_indisplay10478# : I^∞ = #tex2html_wrap_indisplay10479#I(#tex2html_wrap_indisplay10482#A^*) : I^∞ = #tex2html_wrap_indisplay10483#.

<#3542#>

...case

<#3543#>It is worthwhile to note that this formula which is today improperly attributed to Wu Wen-tsün is Equation (32) in Ritt J.F., <#862#>op. cit.<#862#> p. 98.<#3543#>

...then

<#874#>As in the prime decomposition algorithm discussed in Section~35.2<#874#>

...root

<#3544#>If $K &sup#supset;k$ is a differential field extension of $k$, $&alpha#alpha;:= (a_1,...,a_n)&isin#in;K^n$ and $f &isin#in;k{X_1,...,X_n}$ is a differential polynomial, the evaluation $f(&alpha#alpha;)$ is by definition the value $&Phi#Phi;_&alpha#alpha;(f)$, where $&Phi#Phi;_&alpha#alpha;: k{X_1,...,X_n} &rarr#to;K$ is the morphism defined by $&Phi#Phi;_&alpha#alpha;(X_<#898#>ij<#898#>) = a_i^<#899#>(j)<#899#>$ for each $i,j$. <#3544#>

...#math212#sequence!weak

<#3545#>Throughout this chapter, I will preserve the language used in the previous books; so I will substitute with the neologisms of <#931#>admissible Ritt/Lazard sequence<#931#> the terminology introduced by Lazard and his students, which is in any case reported between parenthesis.<#3545#>

...set

<#956#>Not necessarily an ideal!<#956#>

...have

<#3675#>The formula

#math213#

#tex2html_wrap_indisplay10509#Z#tex2html_wrap_indisplay10510##tex2html_wrap_indisplay10511##tex2html_wrap_indisplay10512# = #tex2html_wrap_indisplay10513#

is a specialization of $<#979#>Z<#979#>(<#980#>I<#980#> : f) = <#3549#><#981#>Z<#981#>(<#982#>I<#982#>)&setmn#setminus;<#983#>Z<#983#>({f}))<#3549#>$ --- where $<#984#>I<#984#>$ is a radical polynomial ideal and $f$ a polynomial in $k[X_1,...,X_n]$, --- whose proof is the following: for $g&isin#in;<#985#>I<#985#> : f$ and $&alpha#alpha;&isin#in;<#986#>Z<#986#>(<#987#>I<#987#>)&setmn#setminus;<#988#>Z<#988#>({f})$ we have $0 = fg(&alpha#alpha;) = f(&alpha#alpha;)g(&alpha#alpha;)$ and $f(&alpha#alpha;) &ne#neq;0$ so that $g(&alpha#alpha;) = 0$. Therefore $<#989#>Z<#989#>(<#990#>I<#990#>)&setmn#setminus;<#991#>Z<#991#>({f})&sub#subset;<#992#>Z<#992#>(<#993#>I<#993#> : f) .$

Conversely, assume $g$ satisfies $g(&alpha#alpha;) = 0$ for each $&alpha#alpha;&isin#in;<#994#>Z<#994#>(<#995#>I<#995#>)&setmn#setminus;<#996#>Z<#996#>({f}))$; in other words, for each $&alpha#alpha;&isin#in;<#997#>Z<#997#>(<#998#>I<#998#>)$, $f(&alpha#alpha;) &ne#neq;0 g(&alpha#alpha;) = 0$; thus $fg(&alpha#alpha;) = f(&alpha#alpha;)g(&alpha#alpha;) = 0$ for each $&alpha#alpha;&isin#in;<#999#>Z<#999#>(<#1000#>I<#1000#>)$; as a consequence $fg&isin#in;<#1001#>I<#1001#> = <#1002#>I<#1002#>$ and $g&isin#in;<#1003#>I<#1003#> : f$.

Thus ${g&isin#in;k[X_1,...,X_n] : g(&alpha#alpha;) = 0, &alpha#alpha;&isin#in;<#1004#>Z<#1004#>(<#1005#>I<#1005#>)&setmn#setminus;<#1006#>Z<#1006#>({f}))} &sub#subset;(<#1007#>I<#1007#> : f)$ and $<#1008#>Z<#1008#>(<#1009#>I<#1009#> : f)&sub#subset;<#1010#>Z<#1010#>(<#1011#>I<#1011#>)&setmn#setminus;<#1012#>Z<#1012#>({f}).$<#3675#>

...Lazard

<#3558#>In

Lazard D., <#1253#>

Solving zero-dimensional algebraic systems<#1253#> J. Symb. Comp. <#1254#>

15<#1254#> (1992), 117--132

Lazard D., <#1255#>

A new method for solving algebraic systems of posisitive dimension<#1255#> Disc. Appl. Math. <#1256#>

33<#1256#> (1991), 147--160

Lazard D. <#1257#>

Systems of algebraic equations (algorithms and complexity)<#1257#> Symposia Mathematica <#1258#>

34<#1258#> (1993), 84--105, Cambridge Univ. Press

<#3558#>

... that

<#3561#>we can for instance take #math223#R₀ : = L₀ : = k and #math224#S₀ : = {1}; but for #math225#k : = #tex2html_wrap_inline10570#Q we could consider instead #math226#R₀ : = #tex2html_wrap_inline10572#Z, #math227#S₀ : = #tex2html_wrap_inline10574#N #tex2html_wrap_inline10575# {0}.

The reason why we choose to represent the field elements as explicit fractions with denominators in a restricted chosen multiplicative system S₀ is in order to force uniqueness: see the note below.<#3561#>

... set

<#1350#>Each element f_i is chosen with coefficients not in L₀ but in R₀; as a consequence among all possible associated polynomials we can restrict our choice to those such that their leading coefficient is in S₀. If we take #math229#R₀ : = L₀ : = k and #math230#S₀ : = {1} this simply means to require that each f_i is monic.<#1350#>

...said

<#3562#>This concept is present in Ritt, <#1362#>op. cit.<#1362#> p.34.<#3562#>

...h

<#3563#>As a consequence $<#1397#>A<#1397#>$ is a triangular set; we therefore use the same notation as above denoting $(&pi#pi;_1,...,&pi#pi;_n)$ and $(L_0,...,L_n)$ the corresponding fields and projections.<#3563#>

...#math254#invertible

<#3564#> As a consequence $&pi#pi;_<#1407#>j-1<#1407#>(f_h)$ is squarefree.<#3564#>

...Lazard

<#3565#>Lazard D., <#1480#>A new method for solving algebraic systems of posisitive dimension<#1480#> Disc. Appl. Math. <#1481#>33<#1481#> (1991), p.151.<#3565#>

...and

<#3566#>Lazard D. <#1484#>Systems of algebraic equations (algorithms and complexity)<#1484#> Symposia Mathematica <#1485#>34<#1485#> (1993), 84--105, Cambridge Univ. Press .<#3566#>

... ideals.

<#3567#> D. Lazard, <#1624#>

Resolution of polynomial systems<#1624#> Proc. ASCM 2000, World Scientific (2000) 1--8<#3567#>

... error.

<#3569#> D. Lazard, <#1629#>On the specification for solvers of polynomial systems<#1629#> Proc. ASCM 2001, World Scientific (2001) 1--10<#3569#>

... but

<#3571#>Lazard D., <#1656#>A new method for solving algebraic systems of posisitive dimension<#1656#> Disc. Appl. Math. <#1657#>33<#1657#> (1991), p. 154 <#3571#>

... algorithm

<#3572#> <#1659#>

id est<#1659#> the version of the Euclidean Algorithm proposed by Collins and Brown and briefly discussed in Example~1.6.1 and Historical Remarks~1.6.2.

It consists, given two polynomials #math276#P₀, P₁∈D[X], where D is a domain, in producing, by means of pseudo-division algorithm, a PRS

#math277#

P₀, P₁,…, P_r = gcd(P₀, P₁)∈D[X]

which satisfes the relations

#math278#

P_i+2/c_i = b_iP_i - Q_i+1P_i+1

for suitable #math279#Q_i+1∈D[X] and b_i∈D, and predictable elements c_i∈D. These data allow also to compute (essentially as in Proposition~1.3.1) polynomials S_i, T_i satisfying the Bezout's Identities #math280#P_i = P₀S_i + P₁T_i.

In the quoted passage, the proposed approach is to apply the algorithm to #math281#π_j-1(f_i) and #math282#π_j-1(p) in #math283#L_j-1[X_j] = L_j-1[Z_i], where #math284#p∈k[X₁,…, X_j] #tex2html_wrap_inline10729# k[X₁,…, X_j-1] and X_j = Z_i is algebraic. The technical problem consists that the computation requires zero-testing; the proposal solution requires to

compute a PRS #math285#f_i, p, P₂,…, P_r of f_i and p in #math286#k[X₁,…, X_j-1][X_j],
evaluate #math287#π_j-1(P_r), π_j-1(P_r-1),… until a non-zero element #math288#π_j-1(P_ρ) is produced which therefore satisfies
#math289#
π_j-1(P_ρ) = gcd(π_j-1(f_i), π_j-1(p))∈L_j-1[X_j] = L_j-1[Z_i].

<#3572#>

...#math305#Section~#42S5#1745>

<#3574#>In particular ${V_1,...,V_d}$ (respectively ${Z_1,...,Z_r}$) is the set of the trascendental (respectively: algebraic) variables for $<#1746#>A<#1746#>$.<#3574#>

...#math306#polynomial

<#1764#>Here a Duval splitting could happen.<#1764#>

...choose

<#3577#>If we have $R_0 := L_0 := k$ and $S_0 := {1}$, this simply requires to choose $c := (r)^<#1769#>-1<#1769#>$.<#3577#>

...#math307#Section~#42S5#1778>

<#3578#>In particular ${V_1,...,V_d}$ (respectively ${Z_1,...,Z_r}$) is the set of the trascendental (respectivelty: algebraic) variables for $<#1779#>A<#1779#>$.<#3578#>

...compute

<#1820#>This can produce a Duval splitting.<#1820#>

...r}

<#3579#>Where $<#1844#>C<#1844#>^- = <#1845#>C<#1845#>&cup#cup;R_0[X_1,...,X_j]$, $j=(r)$.<#3579#>

...r₃

<#1887#>We have $(X_1^2-1)f_3-X_1X_2X_4r_2= X_2X_4+X_3(X_1^2-1)$.<#1887#>

...r₆

<#1904#>We have $(X_1^2-1)r_5-X_1X_3r_2=X_3$.<#1904#>

...or

<#3582#>$g(<#2288#>A<#2288#>)$ so that $G_i&sub#subset;(<#2289#>A<#2289#>)$ and $<#2290#>M<#2290#>(G_i)&setmn#setminus;<#2291#>A<#2291#> = {h}$.<#3582#>

...#math331##tex2html_wrap_inline10943#(h)$

<#3583#>We assume $(f) =1$ for each $f&isin#in;G$ so that $<#2296#>T<#2296#>(g)= <#2297#>T<#2297#>(h)g=h$.<#3583#>

... smallest

<#3584#>Recall that the elements in G are enumerated so that #math332##tex2html_wrap_inline10949#(g_i) ;SPMlt; #tex2html_wrap_inline10950#(g_i+1) so the 'smallest' polynomial in #math333#G_j #tex2html_wrap_inline10952# G_j-1 is also the polynomial #math334#g∈G_j #tex2html_wrap_inline10954# G_j-1 having the ;SPMlt;-minimal value #math335##tex2html_wrap_inline10957#(g).<#3584#>

... stabilization

<#2519#>Compare the discussion after Lemma~26.3.9.<#2519#>

... Theorem~26.5.4)

<#3587#>Apparently Kalkbener's Theorem~26.5.4 and the weaker Möller's Theorem~#42T4#2550> are independent.<#3587#>

...that

<#3588#>Recall that we have just proved the inclusion

#math352#

#tex2html_wrap_indisplay11005#I(#tex2html_wrap_indisplay11006#(g₁),…#tex2html_wrap_indisplay11007#(g_s-1)⊆#tex2html_wrap_indisplay11008#I(g₁,…, g_s-1) : g_s.

<#3588#>

...s

<#3589#>Remark that Proposition~#42P5#2720>(6) apparently requires, before the <#2721#>While<#2721#>-loop, to compute

a reduced Gröbner basis $G'_<#2723#>s<#2723#>$ of $<#2724#>I<#2724#>(g_1,...,g_<#2725#>s<#2725#>) : g_s^&infin#infty;)$,
a reduced Gröbner basis $G_<#2726#>s-1<#2726#>$ of $<#2727#>I<#2727#>(g_1,...,g_<#2728#>s<#2728#>)+<#2729#>I<#2729#>(g_s)$,
the triangular set decomposition of $<#2730#>I<#2730#>(G'_<#2731#>s<#2731#>)$

but this computation is trivilal and returns $G'_<#2733#>s<#2733#> = {1}$ and $G_<#2734#>s-1<#2734#> = {g_1,...,g_<#2735#>s<#2735#>}$. <#3589#>

...elements

<#3590#>For each $l&ge#geq;i$ we have

#math353#

#tex2html_wrap_indisplay11019#(g_s-i)∈#tex2html_wrap_indisplay11020#	#tex2html_wrap_indisplay11022#	g_s-i∈k[Z₁,…, Z_r-1]
	#tex2html_wrap_indisplay11025#	g_s-l∈k[Z₁,…, Z_r-1]
	#tex2html_wrap_indisplay11028#	#tex2html_wrap_indisplay11030#(g_s-l)∈#tex2html_wrap_indisplay11031#

<#3590#>

...#math367#Algorithm~35.7.1

<#3596#>Compare also Remark~#40R2#3044>.<#3596#>

...#math377##tex2html_wrap_inline11141#

<#3661#>for a set $<#3504#>G<#3504#> := (g_1,...,g_m)&sub#subset;<#3505#>Q<#3505#>[Z_1,...,Z_r]$ its height is the value $h(<#3506#>G<#3506#>) := ((c(g_i,&tau#tau;) : 1&le#leq;i &le#leq;r, &tau#tau;&isin#in;<#3507#>W<#3507#>).$<#3661#>

...$T

<#3662#>We have $h(T) = <#3509#>O<#3509#>(rhd^<#3510#>2r<#3510#>)$ and $h(N) = <#3511#>O<#3511#>(rhd^<#3512#>r<#3512#>)$ where $d = ((g_i))$ and $h = h(<#3513#>G<#3513#>)$.<#3662#>