when given a system of differential equations , one might be interested in finding the common solutions of these equations . in order to do so
, one can compute another differential equation whose solution space is the intersection of the solution spaces of the equations in the original system .
one way to do this is to translate the equations into operators and use the euclidean algorithm to compute their greatest common right divisor .
the solution space of the greatest common right divisor then consists of the desired elements .
similarly , given a sequence of numbers ( tn)n{0,1 ,  } that satisfies two different recurrence equations , the euclidean algorithm is used in applications to find a reasonable candidate for the least order equation of which ( tn)n{0,1 ,  } is a solution .
carrying out euclids algorithm applied to two polynomials over a domain d usually requires a prediction of the denominators that might appear in the coefficients of the remainders in order to bypass costly computations in the quotient field of d. while such a prediction can be done easily , the growth of the coefficients of the remainders can be tremendous , which might result in an unnecessary high running time .
this can be avoided by dividing out possible content of the remainders to make their coefficients as small as possible . for commutative polynomials as well as for non - commutative operators ,
different ways have been extensively studied to find factors of the content in the sequence of remainders without computing the gcd of the coefficients of each element of the sequence .
most notably in this respect are subresultant sequences , where the growth of the coefficients can be reduced from exponential to linear in the number of reduction steps in the euclidean algorithm . when taking generic ,
randomly generated input , the coefficient size in the subresultant sequence is usually optimal , but when taking the input from applications in e.g. combinatorics or physics , the remainders still have non - trivial content in many cases . for commutative polynomials ,
we generalize two of these results to ore polynomials and we also give a new proof for the commutative case that is based on the structure of subresultants as matrix determinants .
furthermore , we use these results to derive a new bound for the coefficient size of the content - free remainders . in section 2 the basic notions of ore polynomial rings are stated . a precise definition and examples of polynomial remainder sequences
are given in section 3 and further details on the subresultant sequence are then presented in section 4 . the main results of this article can be found in sections 5 and 6 , where we first describe how additional content in the subresultant sequence can emerge and then use these results to improve on the euclidean algorithm and to get a new bound for the size of the coefficients .
the algebraic framework for different kinds of operators that we consider here are ore polynomial rings , which were introduced by ystein ore in the 1930s .
we provide an overview of some basic facts that suffice our needs and that can be found in ore ( 1933 ) and bronstein and petkovek ( 1996 ) .
definition 1let d be a commutative domain , d[x ] the set of univariate polynomials over d and let :dd be an injective endomorphism.1.a map :dd is called pseudo - derivation w.r.t .
 , if for any a , bd,(a+b)=(a)+(b )  and  (ab)=(a)(b)+(a)b.2.suppose that  is a pseudo - derivation w.r.t .
. we define the ore polynomial ring ( d[x],+, ) with componentwise addition and the unique distributive and associative extension of the multiplication rulexa=(a)x+(a)for any ad , to arbitrary polynomials in d[x ] .
to clearly distinguish this ring from the standard polynomial ring over d , we denote it by d[x;, ] .
let d be a commutative domain , d[x ] the set of univariate polynomials over d and let :dd be an injective endomorphism.1.a map :dd is called pseudo - derivation w.r.t .
 , if for any a , bd,(a+b)=(a)+(b )  and  (ab)=(a)(b)+(a)b.2.suppose that  is a pseudo - derivation w.r.t .
. we define the ore polynomial ring ( d[x],+, ) with componentwise addition and the unique distributive and associative extension of the multiplication rulexa=(a)x+(a)for any ad , to arbitrary polynomials in d[x ] .
to clearly distinguish this ring from the standard polynomial ring over d , we denote it by d[x;, ] .
. we define the ore polynomial ring ( d[x],+, ) with componentwise addition and the unique distributive and associative extension of the multiplication rulexa=(a)x+(a)for any ad , to arbitrary polynomials in d[x ] . to clearly distinguish this ring from the standard polynomial ring over d
elements of an ore polynomial ring are called operators and are denoted by capital letters .
we refer to the leading coefficient of an operator a as lc(a ) , to the coefficient of x0 in a as tc(a ) and to the polynomial degree of a in x as the order da of a. example 1commonly used ore polynomial rings are:1.d[x]=d[x;1,0 ] , the ring of commutative polynomials over d.2.c(y)[d;1,ddy ] , the ring of linear ordinary differential operators.3.if sn : c(n)c(n ) is the forward shift in n , i.e. sn(a(n))=a(n+1 ) , then c(n)[s;sn,0 ] is the ring of linear ordinary recurrence operators.4.if :c(q)(y)c(q)(y ) is the q - shift in y , i.e. (a(y))=a(qy ) , then c(q)(y)[j;,ddy ] is the ring of jacksons q - derivative operators . commonly used ore polynomial rings are:1.d[x]=d[x;1,0 ] , the ring of commutative polynomials over d.2.c(y)[d;1,ddy ] , the ring of linear ordinary differential operators.3.if sn : c(n)c(n ) is the forward shift in n , i.e. sn(a(n))=a(n+1 ) , then c(n)[s;sn,0 ] is the ring of linear ordinary recurrence operators.4.if :c(q)(y)c(q)(y ) is the q - shift in y , i.e. (a(y))=a(qy ) , then c(q)(y)[j;,ddy ] is the ring of jacksons q - derivative operators .
d[x]=d[x;1,0 ] , the ring of commutative polynomials over d. c(y)[d;1,ddy ] , the ring of linear ordinary differential operators . if sn : c(n)c(n ) is the forward shift in n , i.e. sn(a(n))=a(n+1 ) , then c(n)[s;sn,0 ] is the ring of linear ordinary recurrence operators .
if :c(q)(y)c(q)(y ) is the q - shift in y , i.e. (a(y))=a(qy ) , then c(q)(y)[j;,ddy ] is the ring of jacksons q - derivative operators . in this article
, we consider the following situation : let d be a euclidean domain with degree function deg and let d[x;, ] be an ore polynomial ring where  is an automorphism . for any operator ad[x;, ] , we define a to be the maximal coefficient degree of a. the content cont(a ) of a is the greatest common divisor of all the coefficients of a and it is defined to be lc(a ) if d is a field .
it is possible to extend d[x;, ] to an ore polynomial ring over the quotient field k of d by setting (a1)=(a)1 and (a / b)=(b(a)a(b))/(b(b ) ) for a , bd , b0 ( see li ( 1996 ) , proposition 2.2.1 ) .
we will denote this ring by k[x;, ] without making it explicit that the automorphism and the pseudo - derivation are extensions of the functions used in d[x;, ] .
it is well known that for any two operators a , bk[x;, ] , there exists a greatest common right divisor ( gcrd ) and it can be made unique ( up to units in d ) by setting gcrd(a , b ) to a nonzero k - left multiple of any gcrd of a and b that has coefficients in d but does not have any content in d. throughout this article , we let a , b , gd[x;, ] , b0 be such that dadb and g is the gcrd of a and b. definition 2for ad and nn , n(a ) is obtained by applying n times  to a and n(a):=(1)n(a ) , where 1 is the inverse map of . the nth -factorial of ad is defined as the producta[n]:=i=0n1i(a ) . for ad and nn , n(a ) is obtained by applying n times  to a and n(a):=(1)n(a ) , where 1 is the inverse map of . the nth -factorial of ad is defined as the producta[n]:=i=0n1i(a ) .
the greatest common right divisor of a and b can be computed by using the euclidean algorithm .
if we multiply any intermediate result that appears during the execution of the algorithm by an element of k{0 } , the final output will be a k - left multiple of g. this amount of freedom allows us to optimize the running time by choosing these factors appropriately . in order to be able to formulate improvements of this kind ,
each element of such a sequence corresponds to a remainder computed in one iteration of the euclidean algorithm .
definition 3let ( ri)i{0,  ,+1 } and ( qi)i{1,  , } be sequences in k[x;, ] , ( di)i{0,  , } a sequence in n and let ( i)i{1,  , } and ( i)i{1,  , } be sequences in k such thatr0=a , r1=b , di = dri,iri1=qiri+iri+1,di+1<di , and all ri are nonzero except for r+1 .
we call the sequence ( ri)i{0,  ,+1 } a polynomial remainder sequence ( prs ) of a and b. it is called normal if di1=di+1 for 1i. let ( ri)i{0,  ,+1 } and ( qi)i{1,  , } be sequences in k[x;, ] , ( di)i{0,  , } a sequence in n and let ( i)i{1,  , } and ( i)i{1,  , } be sequences in k such thatr0=a , r1=b , di = dri,iri1=qiri+iri+1,di+1<di , and all ri are nonzero except for r+1 .
we call the sequence ( ri)i{0,  ,+1 } a polynomial remainder sequence ( prs ) of a and b. it is called normal if di1=di+1 for 1i. a prs of a and b is uniquely determined by specifying the i and i .
whenever we talk about a prs ( ri)i{0,  ,+1 } , we allow ourselves to refer to the related sequences ( qi)i{1,  , } , ( di)i{0,  , } etc . as in the above definition without explicitly introducing them . in order to efficiently compute g ,
one wants to make sure that all the remainders are elements of d[x;, ] rather than k[x;, ] .
this can be achieved by choosing the i in a way such that the quotient of any two consecutive remainders has coefficients in d. to this extent , for 1i set i:=lc(ri)[di1di+1 ] and division with remainder yields qi and ri+1 in d[x;, ] with:(1)iri1=qiri+ri+1,di+1<di .
we call pquo(ri1,ri):=qi the pseudo - quotient of ri1 and ri and prem(ri1,ri):=ri+1 the pseudo - remainder of ri1 and ri .
the i are used to make sure that computations can be done in d[x;, ] and the i control the coefficient growth in a prs .
we want i to contain as many factors of the content of ri+1 as possible without much computational overhead needed to obtain these factors .
this is called the pseudo prs of a and b. here , no content will be divided out.2.i=cont(ri+1 ) .
this is called the primitive prs of a and b. the coefficients of the remainders will be as small as possible , but it is necessary to compute the gcd of the coefficients of each remainder in order to get the i.3.the subresultant prs of a and b ( see section 4 ) is given byi={(1)[d0d1],if
i=1,lc(ri1)(i)[di1di],if 2i , wherei={1,if i=1,(lc(ri1))[di2di1](i1)[di2di11],if 2i. in this prs , the content that is generated systematically by pseudo - remaindering will be cleared from the remainders .
this is called the pseudo prs of a and b. here , no content will be divided out.2.i=cont(ri+1 ) .
this is called the primitive prs of a and b. the coefficients of the remainders will be as small as possible , but it is necessary to compute the gcd of the coefficients of each remainder in order to get the i.3.the subresultant prs of a and b ( see section 4 ) is given byi={(1)[d0d1],if
i=1,lc(ri1)(i)[di1di],if 2i , wherei={1,if i=1,(lc(ri1))[di2di1](i1)[di2di11],if 2i. in this prs , the content that is generated systematically by pseudo - remaindering will be cleared from the remainders .
this is called the pseudo prs of a and b. here , no content will be divided out .
this is called the primitive prs of a and b. the coefficients of the remainders will be as small as possible , but it is necessary to compute the gcd of the coefficients of each remainder in order to get the i .
i=1,lc(ri1)(i)[di1di],if 2i , wherei={1,if i=1,(lc(ri1))[di2di1](i1)[di2di11],if 2i. in this prs , the content that is generated systematically by pseudo - remaindering will be cleared from the remainders .
while in all of the above prss the remainders are elements of d[x;, ] , the degrees of the coefficients differ drastically , as illustrated in the following example .
it can be shown that the degrees of the coefficients in the pseudo prs grow exponentially with i , which renders this prs practically useless .
the growth in the subresultant and primitive prs is linear in i. example 3assume we are given a finite sequence of rational numbers that comes from a sequence ( tn)n{0,1 ,  } which admits a linear recurrence equation with polynomial coefficients .
if the amount of data is sufficiently large , we are able to guess recurrence operators of some fixed order and maximal coefficient degree that annihilate ( tn)n{0,1 ,  } , i.e. the operators applied to the sequence give zero .
( for details on guessing and a mathematica implementation of the method , see kauers ( 2009 ) . ) for example , considertn=k=0n(2n+4k)+(2nk)!+k3 .
given the first 300 terms of this sequence , we can find two operators a and b in q[n][s;sn,0 ] with da=14 , db=13 and maximal coefficient degree a=5 , b=6 respectively . both operators annihilate the given sequence , but
none of them is of minimal order . to get an annihilating minimal order operator , we compute the gcrd of a and b in q(n)[s;sn,0 ] .
table 1 shows the maximal coefficient degrees of the remainders for different prss of a and b.the example confirms that the degrees in the pseudo prs grow exponentially , whereas the subresultant prs and the primitive prs show linear growth . at the same time , the degrees in the subresultant prs are not as small as possible .
this behavior is typical not only for this pair a and b , but in general for operators coming from applications . for randomly generated operators ,
our goal is to understand the difference between randomly generated input and the operators a and b as above and to identify the source of some ( and most often all ) of the additional content in the subresultant prs . to make use of this knowledge
, we will then adjust the formulas for i and i from example 2.3 so that we get a prs with smaller degrees without having to compute the content of every remainder .
assume we are given a finite sequence of rational numbers that comes from a sequence ( tn)n{0,1 ,  } which admits a linear recurrence equation with polynomial coefficients .
if the amount of data is sufficiently large , we are able to guess recurrence operators of some fixed order and maximal coefficient degree that annihilate ( tn)n{0,1 ,  } , i.e. the operators applied to the sequence give zero .
( for details on guessing and a mathematica implementation of the method , see kauers ( 2009 ) . ) for example , considertn=k=0n(2n+4k)+(2nk)!+k3 .
given the first 300 terms of this sequence , we can find two operators a and b in q[n][s;sn,0 ] with da=14 , db=13 and maximal coefficient degree a=5 , b=6 respectively .
both operators annihilate the given sequence , but none of them is of minimal order .
to get an annihilating minimal order operator , we compute the gcrd of a and b in q(n)[s;sn,0 ] .
table 1 shows the maximal coefficient degrees of the remainders for different prss of a and b. the example confirms that the degrees in the pseudo prs grow exponentially , whereas the subresultant prs and the primitive prs show linear growth . at the same time , the degrees in the subresultant prs are not as small as possible .
this behavior is typical not only for this pair a and b , but in general for operators coming from applications . for randomly generated operators , the subresultant prs and the primitive prs usually coincide .
our goal is to understand the difference between randomly generated input and the operators a and b as above and to identify the source of some ( and most often all ) of the additional content in the subresultant prs . to make use of this knowledge
, we will then adjust the formulas for i and i from example 2.3 so that we get a prs with smaller degrees without having to compute the content of every remainder .
for commutative polynomials , the theory of subresultants was intensively studied by brown ( 1978 ) , brown and traub ( 1971 ) , collins ( 1967 ) and loos ( 1982 ) .
the main idea is to translate relations between the elements of a prs like the bzout relation or the ( pseudo-)remainder formula into linear algebra .
a central tool in this context is the sylvester matrix , which , roughly speaking , contains the coefficients of all the monomial multiples of the input polynomials that are necessary to compute remainders of any possible degree .
the remainders in the subresultant sequence turn out to be polynomials whose coefficients are determinants of certain submatrices of this matrix .
the sylvester matrix syl(a , b ) is defined to be the matrix of size ( da+db)(da+db ) with the following entries : if 1idb and 1jda+db , the entry in the ith row and jth column is the ( da+dbj)th coefficient of xdbia .
if db+1ida+db and 1jda+db , the entry in the ith row and jth column is the ( da+dbj)th coefficient of xda(idb)b ( see fig .
1 ) . for i , jn with 0jidb , the matrix syli , j(a , b ) is obtained from syl(a , b ) by removing the rows 1 to i , the rows db+1 to db+i , the columns 1 to i and the last i+1 columns except for the column da+dbj ( see fig .
2 ) . definition 4for 0idb , the polynomialsresi(a , b):=j=0idet(syli , j(a , b))xj is called the ith ( polynomial ) subresultant of a and b. if the order of sresi(a , b ) is strictly less than i , the ith subresultant of a and b is called defective , otherwise it is called regular . the subresultant sequence of a and b of the first kind is the subsequence of(a , b , sresdb1(a , b),sresdb2(a , b),  ,sres0(a ,
b),0 ) that contains a , b , the trailing zero and all nonzero sresi(a , b ) for which sresi+1(a , b ) is regular . for 0idb
, the polynomialsresi(a , b):=j=0idet(syli , j(a , b))xj is called the ith ( polynomial ) subresultant of a and b. if the order of sresi(a , b ) is strictly less than i , the ith subresultant of a and b is called defective , otherwise it is called regular .
the subresultant sequence of a and b of the first kind is the subsequence of(a , b , sresdb1(a , b),sresdb2(a , b), 
,sres0(a , b),0 ) that contains a , b , the trailing zero and all nonzero sresi(a , b ) for which sresi+1(a , b ) is regular .
theorem 1(see 
 li ( 1998 ) . ) the polynomial remainder sequence given by 
 i 
 and 
 i 
 as in 
 example 2.3 , the subresultant prs , is equal to the subresultant sequence of a and b of the first kind .
( see 
 li ( 1998 ) . ) the polynomial remainder sequence given by 
 i 
 and 
 i 
 as in 
 example 2.3 , the subresultant prs , is equal to the subresultant sequence of a and b of the first kind .
the representation of subresultants in terms of determinants of the matrices syli , j(a , b ) makes it possible to identify content by exploiting the special form of these matrices as well as the correspondence between rows of the sylvester matrix and monomial multiples of a and b. for the case of commutative polynomials , some results are known for detecting such additional content .
is a generalization of an observation mentioned in brown ( 1978 ) , which carries over quite easily to the ore case .
the second ( theorem 4 ) usually performs better in terms of coefficient size of the remainders , but a heuristic argument is necessary to use it algorithmically ( see section 6 ) .
theorem 2with 
 t:=gcd(db1(lc(a)),da1(lc(b ) ) ) 
 and 
 i:=i(t ) 
 for 
 0idb1 , we get:i|cont(sresi(a , b ) ) . with 

t:=gcd(db1(lc(a)),da1(lc(b ) ) ) 
 and 
 i:=i(t ) 
 for 
 0idb1 , we get:i|cont(sresi(a , b ) ) .
the coefficients of sresi(a , b ) are the determinants of the matrices syli , j(a , b ) for 0ji .
the coefficients of sresi(a , b ) are the determinants of the matrices syli , j(a , b ) for 0ji .
 not all of the subresultants of a and b are in the subresultant prs of a and b. to make use of theorem 2 for a new prs , we need a minor specialization of the statement : corollary 1let 
 ( ri)i{0,  ,+1 } 
 be the subresultant prs of a and b ( not necessarily normal ) .
if we chooset = gcd(db1(lc(a)),da1(lc(b))),2=db+1(t)andi=di2di1(i1)for2<i , 
 then 
 i|cont(ri ) 
 for 
 2i. 
 proofsuppose ri is the jth subresultant of a and b. then , by the definition of the subresultant sequence of the first kind and theorem 1 , the ( j+1)st subresultant of a and b is regular .
because of this and the subresultant block structure ( see li ( 1998 ) ) , ri1 is of order j+1 and so j is equal to di11 . by theorem 2 ,
it is easy to see that di1 + 1(t ) is equal to i . 
 let 
 ( ri)i{0,  ,+1 } 
 be the subresultant prs of a and b ( not necessarily normal ) .
if we chooset = gcd(db1(lc(a)),da1(lc(b))),2=db+1(t)andi=di2di1(i1)for2<i , 
 then 
 i|cont(ri ) 
 for 
 2i. suppose ri is the jth subresultant of a and b. then , by the definition of the subresultant sequence of the first kind and theorem 1 , the ( j+1)st subresultant of a and b is regular . because of this and the subresultant block structure ( see li ( 1998 ) ) ,
ri1 is of order j+1 and so j is equal to di11 . by theorem 2 ,
it is easy to see that di1 + 1(t ) is equal to i . 
 in the commutative case , a second source of additional content was determined , although this result is not widely known .
the following theorem can be found in knuth ( 1981 ) : theorem 3let 
 a , bd[x ] 
 be such that the subresultant prs of a and b is normal , and let g be the gcd of a and b. then 
 lc(g)2(i1)|cont(ri ) 
 for 
 2i. let 
 a , bd[x ] 
 be such that the subresultant prs of a and b is normal , and let g be the gcd of a and b. then 
 lc(g)2(i1)|cont(ri ) 
 for 
 2i. a generalization of theorem 3 to ore polynomials is not straightforward , as example 4 shows .
example 4example 3 cont.if we take a and b as in example 3 , then the leading coefficient of the gcrd of a and b is ( n+9)p(n ) , where p(n ) is a polynomial of degree 17 .
the subresultant prs of a and b turns out to be normal and r2 is of order d2=12 . by theorem 3 ,
if the polynomials were elements of d[x ] , cont(r2 ) would be divisible by lc(g)2 and a naive translation of the theorem to the non - commutative case suggests divisibility by a polynomial of degree at least 36 .
the ( monic ) content of r2 , however , is only ( n+16)(n+17 ) , which is contained in , but not equal to , 7(lc(g ) ) .
if we take a and b as in example 3 , then the leading coefficient of the gcrd of a and b is ( n+9)p(n ) , where p(n ) is a polynomial of degree 17 .
the subresultant prs of a and b turns out to be normal and r2 is of order d2=12 . by theorem 3 ,
if the polynomials were elements of d[x ] , cont(r2 ) would be divisible by lc(g)2 and a naive translation of the theorem to the non - commutative case suggests divisibility by a polynomial of degree at least 36 .
the ( monic ) content of r2 , however , is only ( n+16)(n+17 ) , which is contained in , but not equal to , 7(lc(g ) ) . again in the commutative case , let qa , qbd[x ] be such that a = qag and b = qbg .
knuth ( 1981 ) proves theorem 3 by showing that if ( ri)i{0,  ,+1 } is the subresultant prs of a and b and ( ri)i{0,  ,+1 } is the subresultant prs of qa , qb , then qi = lc(g)2(i1)ri .
this approach is problematic for ore polynomials , because there the qis and the ris have coefficients in k and not necessarily in d. this means that even after showing that a quotient qi is a d - left multiple of some subresultant ri of qa and qb , the left factor and the denominators in the coefficients of ri might not be coprime and thus lead to cancellation .
therefore we will not only describe why in the non - commutative case only some factors of lc(g ) appear as content , but we also present a new proof of theorem 3 that makes it more explicit where the additional content comes from .
] , if a is a multiple of the primitive polynomial g , then their quotient will always have coefficients in d , and therefore , the leading coefficient of a contains all the factors of the leading coefficient of g. for ore polynomials , this is not necessarily true , since the quotient of a and g might be an element of k[x;,]d[x;, ] .
still , different left multiples of g in d[x;, ] may share some common factors in their leading coefficients , as described in lemma 1 .
lemma 1let 
 dtn 
 be fixed , let 
 id[x;, ] 
 be a left ideal and let t be any element of 
 i 
 of order 
 dt 
 such that , among all the operators of order 
 dt 
 in 
 i , its leading coefficient t is minimal with respect to the degree .
then t is independent of the choice of t ( up to multiplication by units in 
 d ) and for any 
 li 
 with 
 dldt 
 we have 
 dldt(t)|lc(l ) .
let 
 dtn 
 be fixed , let 
 id[x;, ] 
 be a left ideal and let t be any element of 
 i 
 of order 
 dt 
 such that , among all the operators of order 
 dt 
 in 
 i , its leading coefficient t is minimal with respect to the degree .
then t is independent of the choice of t ( up to multiplication by units in 
 d ) and for any 
 li 
 with 
 dldt 
 we have 
 dldt(t)|lc(l ) .
proofassume there are t , li for which the claim dldt(t)|lc(l ) does not hold .
hence the operator lqt is an element of i whose leading coefficient has degree less than deg(t ) .
this contradicts the choice of t.for the uniqueness , let ti be any other operator of order dt with minimal leading coefficient degree . by what was just shown above
, we get lc(t)|t and t|lc(t ) , so t and lc(t ) are associates . 
 assume there are t , li for which the claim dldt(t)|lc(l ) does not hold .
hence the operator lqt is an element of i whose leading coefficient has degree less than deg(t ) .
this contradicts the choice of t. for the uniqueness , let ti be any other operator of order dt with minimal leading coefficient degree . by what was just shown above , we get lc(t)|t and t|lc(t ) , so t and lc(t ) are associates . 
the shift dt(t ) of the leading coefficient of t is called the essential part of i at order dt .
if there is no operator in i for some order n , the essential part of i at order n is defined to be 1 .
consider i , t and t from lemma 1 . the shift dt(t ) of the leading coefficient of t is called the essential part of i at order dt .
if there is no operator in i for some order n , the essential part of i at order n is defined to be 1 .
let lc[y][d;1,ddy ] and i = ic[y][d;1,ddy ] where ic(y)[d;1,ddy ] is the left ideal generated by l. we give an informal explanation of essential parts of i in terms of solutions of l , i.e. functions that are annihilated by l. any non - removable singularity of a solution of l corresponds to a root of the leading coefficient of l , but not for any root of lc(l ) there has to be a solution with a non - removable singularity at that point .
any solution of l is also a solution of every operator in i and it can happen that there are nonzero k - left multiples of l in i that have strictly smaller leading coefficient degree than l. if such a desingularized operator exists , it means that some of the roots of lc(l ) can be removed by multiplying l with another operator from the left .
these removable roots are called the apparent singularities of l. it is shown in jaroschek ( in preparation ) that there exists a unique minimal ( w.r.t .
degree ) essential part of i that appears in the essential parts of i at every order greater than dl .
this minimal essential part of i is a polynomial whose roots are exactly the non - apparent singularities of l , and it turns out that for each root of the essential part of i , there is at least one solution of l that does not admit an analytic continuation at that point .
a more detailed description of desingularization and apparent singularities of differential equations can be found in ince ( 1926 ) .
further references and recent results on desingularization of ore operators can be found in chen et al .
note that for commutative polynomials , by gau lemma , the essential part of a nonzero ideal at any order is equal to the leading coefficient of the primitive greatest common divisor of the ideal elements . for
the remaining part of this article , let id[x;, ] be the left ideal generated by a and b. we formulate our ore generalization of theorem 3 , where now some of the essential parts of i play the role of the leading coefficient of the gcrd of a and b. theorem 4let 
 i{0,  ,db1 } 
 and 
 :=da+db2i .
if 
 tk 
 is the essential part of 
 i 
 at order k for 
 i < k+i1 , then(k = i+1+i1tk)|cont(sresi(a , b ) ) .
let 
 i{0,  ,db1 } 
 and 
 :=da+db2i . if 
 tk 
 is the essential part of 
 i 
 at order k for 
 i < k+i1 , then(k = i+1+i1tk)|cont(sresi(a , b ) ) .
,i } , syli , j(a , b ) is of size  and if the last column is removed , the resulting matrix does not depend on j anymore . for n{1,  ,1 } , let mi , n be the set of all nn matrices obtained by removing the last n columns and any n rows from syli , j(a , b ) .
the jth coefficient of sresi(a , b ) is the determinant of syli , j(a , b ) and laplace expansion along the last column shows that it is a d - linear combination of the elements of mi,1 . by induction on n
we show that the determinant of any element of mi , n is divisible by t+int+i(n1)  t+i1 .
the theorem is then proven by setting n=1.for n=1 , the only entry in a matrix in mi,1 is either zero or the leading coefficient of a monomial left multiple of a or b of order +i1 , so the claim follows from lemma 1.now suppose the claim is true for 1n<1 and let m be any element of mi , n+1 .
if the determinant of m is zero , then there is nothing to show . consider the case where det(m)0 .
the jth component vj of v is of the form pj / det(m ) where pjd is the determinant of some element of mi , n . by induction hypothesis it is divisible by t+int+i(n1)  t+i1 .
every row in m corresponds to an operator of the form xka or xkb for kn , minus some of the lower order terms . for the jth row , 1jn+1
so if we setv:=det(m)t+int+i(n1)  t+i1vdn+1 and l=j=0n+1vjlj , then l is an element in i of order +i(n+1 ) and its leading coefficient is det(m)/(t+int+i(n1)  t+i1)d .
lemma 1 yields that lc(l ) is divisible by t+i(n+1 ) , so we get in total t+i(n+1)t+in 
,i } , syli , j(a , b ) is of size  and if the last column is removed , the resulting matrix does not depend on j anymore . for n{1,  ,1 } , let mi , n be the set of all nn matrices obtained by removing the last n columns and any n rows from syli , j(a , b ) . the jth coefficient of sresi(a , b ) is the determinant of syli , j(a , b ) and laplace expansion along the last column shows that it is a d - linear combination of the elements of mi,1 . by induction on n
we show that the determinant of any element of mi , n is divisible by t+int+i(n1)  t+i1 .
the only entry in a matrix in mi,1 is either zero or the leading coefficient of a monomial left multiple of a or b of order +i1 , so the claim follows from lemma 1 .
now suppose the claim is true for 1n<1 and let m be any element of mi , n+1 .
the jth component vj of v is of the form pj / det(m ) where pjd is the determinant of some element of mi , n . by induction hypothesis
every row in m corresponds to an operator of the form xka or xkb for kn , minus some of the lower order terms . for the jth row , 1jn+1
so if we setv:=det(m)t+int+i(n1)  t+i1vdn+1 and l=j=0n+1vjlj , then l is an element in i of order +i(n+1 ) and its leading coefficient is det(m)/(t+int+i(n1)  t+i1)d .
lemma 1 yields that lc(l ) is divisible by t+i(n+1 ) , so we get in total t+i(n+1)t+in 
t+i1|det(m ) .   in practice , the essential parts of i will most likely be the same at every order n with dgnda+db . in that case ,
theorem 4 is equivalent to the following simplification , where only the essential part of i at order da+db needs to be known .
corollary 2let 
 i{0,  ,db1 } 
 and 
 :=da+db2i . if t is the essential part of 
 i 
 at order 
 da+db , theni+1(t)[1]|cont(sresi(a , b ) ) .
let 
 i{0,  ,db1 } 
 and 
 :=da+db2i . if t is the essential part of 
 i 
 at order 
 da+db , theni+1(t)[1]|cont(sresi(a , b ) ) .
proofaccording to lemma 1 , j(t ) divides the essential part of i at order j for any dgjda+db .
if i < dg , then the ith subresultant of a and b is zero .
+i1(t)=i+1(t)[1]. according to lemma 1 , j(t ) divides the essential part of i at order j for any dgjda+db .
if i < dg , then the ith subresultant of a and b is zero .
+i1(t)=i+1(t)[1]. like for theorem 2 , an adjustment of corollary 2 to the block structure of the subresultant sequence of the first kind is needed in order to construct a new prs .
corollary 3let 
 ( ri)i{0,  ,+1 } 
 be the subresultant prs of a and b ( not necessarily normal ) and let t be the essential part of 
 i 
 at order 
 da+db . if we set 
 2=db(t)[dadb+1 ] 

andi=di1(t)[di2di1]i1da+dbdi2 + 1(t)[di2di1]for2<i , 
 then 
 i|cont(ri ) 
 for 
 2i. let 
 ( ri)i{0,  ,+1 } 
 be the subresultant prs of a and b ( not necessarily normal ) and let t be the essential part of 
 i 
 at order 
 da+db .
if we set 
 2=db(t)[dadb+1 ] 
 andi=di1(t)[di2di1]i1da+dbdi2 + 1(t)[di2di1]for2<i , 
 then 
 i|cont(ri ) 
 for 
 2i. proofsuppose ri is the jth subresultant of a and b. as in the proof of corollary 1 , we have that j is equal to di11 .
so by corollary 2 , the content of ri is divisible by di1(t)[da+db2di1 + 1 ] .
 suppose ri is the jth subresultant of a and b. as in the proof of corollary 1 , we have that j is equal to di11 .
so by corollary 2 , the content of ri is divisible by di1(t)[da+db2di1 + 1 ] .
we now derive formulas for the i and i that take into account the potential additional content characterized by theorems 2 and 4 . for this
we need the following lemma : lemma 2for 
 1,2k : 
 pquo(1a,2b)2=12[dadb+1]pquo(a , b ) . for 
 1,2k : 
 pquo(1a,2b)2=12[dadb+1]pquo(a , b ) .
proofby lemma 2.3 in li ( 1998 ) , the pseudo - remainder of 1a and 2b is the ( db1)st subresultant of 1a and 2b ( up to sign ) . consequently , its coefficients are determinants of submatrices of syl(1a,2b ) that contain one row corresponding to the operator 1a and dadb+1 rows corresponding to operators of the form xi2b , 0idadb .
thus , by lemma 2.2 in li ( 1998 ) , it follows that ( up to sign)(2)prem(1a,2b)=12[dadb+1]prem(a , b ) .
the pseudo - remainder formula ( 1 ) applied to 1a and 2b islc(2b)[dadb+1]1a = pquo(1a,2b)2b+prem(1a,2b ) . combining this with ( 2 ) and
dividing the resulting equation by 12[dadb+1 ] from the left gives the desired result . 
 by lemma 2.3 in li ( 1998 ) , the pseudo - remainder of 1a and 2b is the ( db1)st subresultant of 1a and 2b ( up to sign )
. consequently , its coefficients are determinants of submatrices of syl(1a,2b ) that contain one row corresponding to the operator 1a and dadb+1 rows corresponding to operators of the form xi2b , 0idadb .
thus , by lemma 2.2 in li ( 1998 ) , it follows that ( up to sign)(2)prem(1a,2b)=12[dadb+1]prem(a , b ) .
the pseudo - remainder formula ( 1 ) applied to 1a and 2b islc(2b)[dadb+1]1a = pquo(1a,2b)2b+prem(1a,2b ) .
combining this with ( 2 ) and dividing the resulting equation by 12[dadb+1 ] from the left gives the desired result . 
 this now allows us to state i and i for improved polynomial remainder sequences : theorem 5suppose 
 ( ri)i{0,  ,+1 } 
 is the subresultant prs of a and b and 
 ( i)i{0,  ,+1 } 
 is any sequence in 
 k{0 } 
 with 
 0=1=1 .
then 
 ( ri)i{0,  ,+1 } 
 is a prs of a and b with:i = lc(ri)[di1di+1],i={(1)[d0d1]2,ifi=1,lc(ri1)(i)[di1di]i[di1di+1]i+1,if2i , 
 wherei={1,ifi=1,(i1lc(ri1))[di2di1](i1)[di2di11],if2i. suppose 
 ( ri)i{0,  ,+1 } 
 is the subresultant prs of a and b and 
 ( i)i{0,  ,+1 } 
 is any sequence in 
 k{0 } 
 with 
 0=1=1
then 
 ( ri)i{0,  ,+1 } 
 is a prs of a and b with:i = lc(ri)[di1di+1],i={(1)[d0d1]2,ifi=1,lc(ri1)(i)[di1di]i[di1di+1]i+1,if2i , 
 wherei={1,ifi=1,(i1lc(ri1))[di2di1](i1)[di2di11],if2i. prooffrom the definition of ri and the equationsiri1=qiri+iri+1andi=i[di1di+1]i , it follows that(3)i[di1di+1]i1iri1=qiiri+ii+1ri+1 . for the first summand on the right hand side ,
for the second summand , observe that since ilc(ri ) equals lc(ri ) , we have that i equals i for all 1i. thus(5)ii+1=i[di1di+1]i1i . the proof is concluded by combining ( 3 ) , ( 4 ) and ( 5 ) and dividing the resulting equation by i[di1di+1]i1 from the left . 
for the first summand on the right hand side , lemma 2 yields(4)qii=i[di1di+1]i1qi . for the second summand ,
observe that since ilc(ri ) equals lc(ri ) , we have that i equals i for all 1i. thus(5)ii+1=i[di1di+1]i1i .
the proof is concluded by combining ( 3 ) , ( 4 ) and ( 5 ) and dividing the resulting equation by i[di1di+1]i1 from the left . 
 two possible choices for ( i)i{i,  ,+1 } were presented in corollary 1 and 3 .
the computation of i in corollary 1 is straightforward , but in corollary 3 , the essential part of i ( the ideal generated by a and b ) at order da+db is usually not known .
a simple heuristic can solve this problem in most cases : as was shown in lemma 1 , the essential part of i at order da+db appears in a shifted version in the leading coefficient of every nonzero ideal element with order less than or equal to da+db . in particular it is contained in lc(a ) and lc(b ) .
thus , if t is the essential part of i at order da+db , we have(6)da(t)|gcd(lc(a),dadb(lc(b ) ) ) and in most cases , we not only have divisibility but equality . in fact
, in all the examples we looked at that came from combinatorics or physics , this guess for the essential part turned out to be correct .
example 5example 4 cont.we now use theorem 5 and corollaries 1 and 3 to compute new prss of a and b as in example 3 . the essential part of i at order da+db is ( n+3 ) , so da(n+3)=(n+17 ) , which is also the guess given by the right hand side of ( 6 ) . applying corollary 1 yields the factors2=n+17,3=n+18, 
the improvements from corollary 1 are marginal , while the degrees in the improved prs with the results from corollary 3 are equal to the degrees in the primitive prs , except for the very last step ( see table 2 ) .
we now use theorem 5 and corollaries 1 and 3 to compute new prss of a and b as in example 3 .
the essential part of i at order da+db is ( n+3 ) , so da(n+3)=(n+17 ) , which is also the guess given by the right hand side of ( 6 ) .
the improvements from corollary 1 are marginal , while the degrees in the improved prs with the results from corollary 3 are equal to the degrees in the primitive prs , except for the very last step ( see table 2 ) .
example 6although the remainders in the prs based on corollary 3 are usually primitive when starting from randomly generated operators or operators that come from some applications , it is not guaranteed that this is always the case . as an example , considera , bq[y][x],a = x4+yx2+yx+y , b = x3+yx2 .
the second subresultant of a and b is sres2(a , b)=(y+y2)x2+yx+y , so cont(sres2(a , b))=y , but in the improved prs , no content will be found.as mentioned , it may also happen that the guess for the essential part of i at order da+db is too large , for example : a , bq(y)[d,1,ddx],a=(y+1)d4+d3+d2+yd+1,b=(y+1)d3+d2 + 1 .
here , cont(r3 ) in the subresultant prs is ( y+1 ) , but a factor ( y+1)2 is predicted . the mistake in predicting the essential part can be noticed on the fly during the execution of the algorithm as soon as a remainder with coefficients in q(y ) appears .
it is then possible to either switch to another prs or to refine the guess of the essential part .
one strategy to do so is to remove all the factors from the guess that could be responsible for the appearance of denominators .
let t be the guess for the essential part of i at da+db and let c be the non - trivial common denominator of the coefficients of a remainder ri in the improved prs .
update ri , i and t withricri,iic , ttgcd(t,mmm(c)),i+1didb(t)[da+db2di+1 ] , and continue the computation with these new values . for differential operators in c(y)[d;1,ddy ] , we have m={0 } and for recurrence operators in c(n)[sn;sn,0 ] , m contains all the integer roots of the polynomial resn(c(n+m),t ) .
although the remainders in the prs based on corollary 3 are usually primitive when starting from randomly generated operators or operators that come from some applications , it is not guaranteed that this is always the case . as an example , considera , bq[y][x],a = x4+yx2+yx+y , b = x3+yx2
the second subresultant of a and b is sres2(a , b)=(y+y2)x2+yx+y , so cont(sres2(a , b))=y , but in the improved prs , no content will be found .
as mentioned , it may also happen that the guess for the essential part of i at order da+db is too large , for example : a , bq(y)[d,1,ddx],a=(y+1)d4+d3+d2+yd+1,b=(y+1)d3+d2 + 1 .
here , cont(r3 ) in the subresultant prs is ( y+1 ) , but a factor ( y+1)2 is predicted . the mistake in predicting the essential part can be noticed on the fly during the execution of the algorithm as soon as a remainder with coefficients in q(y ) appears .
it is then possible to either switch to another prs or to refine the guess of the essential part .
one strategy to do so is to remove all the factors from the guess that could be responsible for the appearance of denominators .
let t be the guess for the essential part of i at da+db and let c be the non - trivial common denominator of the coefficients of a remainder ri in the improved prs .
update ri , i and t withricri,iic , ttgcd(t,mmm(c)),i+1didb(t)[da+db2di+1 ] , and continue the computation with these new values . for differential operators in c(y)[d;1,ddy ] , we have m={0 } and for recurrence operators in c(n)[sn;sn,0 ] , m contains all the integer roots of the polynomial resn(c(n+m),t ) .
example 7we can guess two operators a and b in q[n][s;sn,0 ] of order da=16 , db=14 , respectively that annihilate the sequencetn=(7n3 + 5n2+n+1)7((n+1/7)12)7(2n)!3(3n)!2 .
the gcrd of a and b is of order 1 and the essential part of i at da+db is of degree 4 .
the essential part of i at order 11 , however , is of degree 11 , so here we are in the rare case where the essential part of i at order da+db is only contained but not equal to the essential part at lower orders .
formula ( 6 ) only predicts the essential part of i at order da+db and during the gcrd computation , content that comes from lower order essential parts emerges ( see table 3 ) .
it is possible to guess the essential part of i at lower orders and then use theorem 4 to get the primitive remainders , but like in the direct computation of the primitive prs , gcd computations in the base ring would be necessary after each division step .
we can guess two operators a and b in q[n][s;sn,0 ] of order da=16 , db=14 , respectively that annihilate the sequencetn=(7n3 + 5n2+n+1)7((n+1/7)12)7(2n)!3(3n)!2 .
the gcrd of a and b is of order 1 and the essential part of i at da+db is of degree 4 .
the essential part of i at order 11 , however , is of degree 11 , so here we are in the rare case where the essential part of i at order da+db is only contained but not equal to the essential part at lower orders .
formula ( 6 ) only predicts the essential part of i at order da+db and during the gcrd computation , content that comes from lower order essential parts emerges ( see table 3 ) .
it is possible to guess the essential part of i at lower orders and then use theorem 4 to get the primitive remainders , but like in the direct computation of the primitive prs , gcd computations in the base ring would be necessary after each division step . as another consequence of theorem 4 , we can give a new bound for the coefficient degrees of the primitive prs in terms of the essential parts of the left ideal generated by a and b. theorem 6let 
 ( ri)i{0,  ,+1 } 
 be the primitive prs of a and b. fix 
 i{0,  , } 
 and let 
 bn 
 be such that 
 maxk{0, 
if 
 tj 
 denotes the essential part of 
 i 
 at order 
 jn , thenri(da+db2(di11))bj = di1da+dbdi1 + 1deg(tj ) . let 
 ( ri)i{0,  ,+1 } 
 be the primitive prs of a and b. fix 
 i{0,  , } 
 and let 
 bn 
 be such that 
 maxk{0, 
,dbdi1}(xka)b 
 and 
 maxk{0,  ,dadi1}(xkb)b . if 
 tj 
 denotes the essential part of 
 i 
 at order 
 jn , thenri(da+db2(di11))bj = di1da+dbdi1 + 1deg(tj ) .
proofthe bound follows directly from hadamards inequality , the subresultant block structure and corollary 3 . 
 the bound follows directly from hadamards inequality , the subresultant block structure and corollary 3 . 
 polynomial remainder sequences contain the intermediate results of the euclidean algorithm when applied to ( non-)commutative polynomials . 
 the running time of the algorithm is dependent on the size of the coefficients of the remainders . 
 different ways have been studied to make these as small as possible . 
 the subresultant sequence of two polynomials is a polynomial remainder sequence in which the size of the coefficients is optimal in the generic case , but when taking the input from applications , the coefficients are often larger than necessary . 
 we generalize two improvements of the subresultant sequence to ore polynomials and derive a new bound for the minimal coefficient size . 
 our approach also yields a new proof for the results in the commutative case , providing a new point of view on the origin of the extraneous factors of the coefficients . 
Introduction
Preliminaries
Polynomial remainder sequences for Ore polynomials
Subresultant theory for Ore polynomials
Identifying content of polynomial subresultants
Improved polynomial remainder sequence