Bounds for Substituting Algebraic Functions into D-finite Functions
Manuel Kauers Gleb Pogudin










2


Bounds for Substituting Algebraic Functions into D-finite Functions
    
 Manuel KauersSupported by the Austrian Science Fund (FWF): Y464, F5004.

  Institute for Algebra / Johannes Kepler University

  4040 Linz, Austria

  manuel.kauers@jku.at
 Gleb PogudinSupported by the Austrian Science Fund (FWF): Y464.

  Institute for Algebra / Johannes Kepler University

  4040 Linz, Austria

  gleb.pogudin@jku.at

    
======================================================================================================================================================================================================================================================================================================================================================




  It is well known that the composition of a D-finite function with an algebraic function is again D-finite.
  We give the first estimates for the orders and the degrees of annihilating operators for the compositions.
  We find that the analysis of removable singularities leads to an order-degree curve which is much more
  accurate than the order-degree curve obtained from the usual linear algebra reasoning. 




§ INTRODUCTION


A function f is called D-finite if it satisfies an ordinary linear differential equation 
with polynomial coefficients, 

    p_0(x)f(x)+p_1(x)f'(x)+⋯+p_r(x)f^(r)(x)=0.

A function g is called algebraic if it satisfies a polynomial equation with polynomial
coefficients,

    p_0(x)+p_1(x)g(x) + ⋯ + p_r(x)g(x)^r=0.




It is well known <cit.> that when f is D-finite and g is algebraic,
the composition f∘ g is again D-finite. For the special case f=id this reduces to Abel's theorem, which says
that every algebraic function is D-finite. This particular case was investigated closely
in <cit.>, where a collection of bounds was given for the orders and degrees of the
differential equations satisfied by a given algebraic function. It was also pointed out in <cit.>
that differential equations of higher order may have significantly lower degrees,
an observation that gave rise to a more efficient algorithm for transforming an algebraic equation
into a differential equation. Their observation has also motivated the study of order-degree
curves: for a fixed D-finite function f, these curves describe the boundary of the region of all pairs (r,d)∈ N^2
such that f satisfies a differential equation of order r and degree d.

 We have fixed some randomly chosen operator
  L∈ C[x][∂] of order r_L=3 and degree d_L=4
  and a random 

  -1.7[b].6
   polynomial P∈ C[x][y] of y-degree r_P=3 and x-degree d_P=4.
  For some prescribed orders r, we computed the smallest degrees d such that there is an operator M
  of order r and degree d that annihilates f∘ g for all solutions f of L
  and all solutions g of P.
  The points (r,d) are shown in the figure on the right.-.25em
  -.6em
    [yscale=.46,scale=1.1]
      [->] (0,0)–(0,5) node[left] d;
      [->] (0,0)–(1.5,0) node[right] r;
      in 1,...,4 (0,)–(-.1,) node[left] 00;
      in 1,...,1 (,0)–(,-.1) node[below] 00;
      (.5,0)–(.5,-.1) node[below] 50;
      (-1,-1) rectangle (1.5,5);
      
      
(.10,3.16) node ·
(.11,2.40) node ·
(.12,2.02) node ·
(.13,1.79) node ·
(.14,1.64) node ·
(.15,1.53) node ·
(.16,1.45) node ·
(.17,1.38) node ·
(.18,1.33) node ·
(.19,1.29) node ·
(.20,1.26) node ·
(.21,1.23) node ·
(.22,1.20) node ·
(.23,1.18) node ·
(.24,1.16) node ·
(.25,1.14) node ·
(.26,1.13) node ·
(.27,1.12) node ·
(.28,1.10) node ·
(.29,1.09) node ·
(.30,1.08) node ·
(.31,1.07) node ·

(.33,1.06) node ·
(.34,1.05) node ·
(.35,1.04) node ·

(.37,1.03) node ·

(.39,1.02) node ·

(.41,1.01) node ·


(.44,1.00) node ·


(.47,.99) node ·


(.50,.98) node ·



(.54,.97) node·




(.59,.96) node·






      (.66,.95) node·
      (.74,.94) node·      
      (.85,.93) node·   
      (1.00,.92) node·   
      (1.23,.91) node·
      (1.61,.90) node·
      ;
    


Experiments suggested that order-degree curves are often just simple hyperbolas. A priori knowledge of these
hyperbolas can be used to design efficient algorithms. For the case of creative 
telescoping of hyperexponential functions and hypergeometric terms, as well as for 
simple D-finite closure properties (addition, multiplication, Ore-action), bounds for order-degree curves
have been derived <cit.>. However, it turned out that these bounds are often not
tight. 

A new approach to order-degree curves has been suggested in <cit.>,
where a connection was established between order-degree curves and apparent
singularities. Using the main result of this paper, very accurate order-degree
curves for a function f can be written down in terms of the number and the
cost of the apparent singularities of the minimal order annihilating operator
for f. However, when the task is to compute an annihilating operator
from some other representation, e.g., a definite integral, then the information
about the apparent singularities of the minimal order operator is only a
  posteriori knowledge. Therefore, in order to design efficient algorithms using the result of <cit.>,
we need to predict the singularity structure of the output operator in terms of
the input data. This is the program for the present paper.

First (Section <ref>), we derive an order-degree bound for
D-finite substitution using the classical approach of considering a suitable
ansatz over the constant field, comparing coefficients, and balancing variables
and equations in the resulting linear system. This leads to an order-degree
curve which is not tight. Then (Section <ref>) we estimate the
order and degree of the minimal order annihilating operator for the composition
by generalizing the corresponding result of <cit.> from f=id
to arbitrary D-finite f. The derivation of the bound is a bit more tricky in
this more general situation, but once it is available, most of the subsequent
algorithmic considerations of <cit.> generalize
straightforwardly. Finally (Section <ref>) we turn to the analysis of the
singularity structure, which indeed leads to much more accurate results. The
derivation is also much more straightforward, except for the required
justification of the desingularization cost. In practice, it is almost always
equal to one, and although this is the value to be expected for generic input,
it is surprisingly cumbersome to give a rigorous proof for this expectation.



Throughout the paper, we use the following conventions: 


  * C is a field of characteristic zero, C[x] is the usual commutative ring of 
   univariate polynomials over C. We write C[x][y] or C[x,y] for the commutative 
   ring of bivariate polynomials and C[x][∂] for the non-commu­ta­tive ring of linear
   differential operators with polynomial coefficients. In this latter ring, the multiplication
   is governed by the commutation rule ∂ x=x∂ +1.

-
  * L∈ C[x][∂ ] is an operator of order r_L:=_∂(L) 
   with polynomial coefficients of degree at most d_L:=_x(L).

-
  * P∈ C[x,y] is a polynomial of degrees r_P:=_y(P) and d_P:=_x(P).
   It is assumed that P is square-free as an element of C(x)[y] and that 
   it has no divisors in C̅[y], where C̅ is the algebraic closure of C.

-
  * M∈ C[x][∂ ] is an operator such that for every solution f of L
   and every solution g of P, the composition f∘ g is a solution of M.
   The expression f ∘ g can be understood either as a composition of analytic functions
   in the case C = ℂ, or in the following sense.
   We define M such that for every α∈ C, for every solution g ∈ C[[x - α]] of P
   and every solution f ∈ C[[x - g(α)]] of L, M annihilates f∘ g, which is a well-defined
   element of C[[x - α]]. In the case C = ℂ these two definitions coincide.






§ ORDER-DEGREE-CURVEBY LINEAR ALGEBRA


Let g be a solution of P, i.e., suppose that P(x,g(x))=0, and let f be a
solution of L, i.e., suppose that L(f)=0. Expressions involving g and f can
be manipulated according to the following three well-known observation:


  *  (Reduction by P) For each polynomial Q∈ C[x,y] with _y(Q)≥ r_P
  there exists a polynomial Q̃∈ C[x,y] with _y(Q̃)≤_y(Q)-1 and _x(Q̃)≤_x(Q)+d_P
  such that
  
    Q(x,g)= 1/_y(P)Q̃(x,g).

  The polynomial Q̃ is the result of the first step of computing the pseudoremainder of Q by P w.r.t. y.

  *  (Reduction by L) There exist polynomials v,q_j,k∈ C[x] of degree at most d_Ld_P such that
  
    f^(r_L)∘ g=1/v∑_j=0^r_P-1∑_k=0^r_L-1 q_j,kg^j · (f^(k)∘ g).

  To see this, write L=∑_k=0^r_Ll_k∂ ^k for some polynomials l_k∈ C[x] of degree at most d_L. Then we have
  
    f^(r_L)∘ g = -1/l_r_L∘ g∑_k=0^r_L-1(l_k∘ g) · (f^(k)∘ g).

  By the assumptions on P, the denominator l_r_L∘ g cannot be zero. In other words, (P(x,y),l_r_L(y))=1 in C(x)[y].
  For each k=0,…,r_L-1, consider an ansatz AP+Bl_r_L=l_k for polynomials A,B∈ C(x)[y] of
  degrees at most d_L-1 and r_P-1, respectively, and compare coefficients with respect to y.
  This gives k inhomogeneous linear systems over C(x) with r_P+d_L variables and equations, which
  only differ in the inhomogeneous part but have the same matrix M=Syl_y(P,l_r_L) for every k.   
  The claim follows using Cramer's rule, taking into account that the coefficient matrix of the system
  has d_L many columns with polynomials of degree d_P and r_P many columns with polynomials of degree _x l_k(y)=0
  (which is also the degree of the inhomogeneous part). Note that v=(M) does not depend on k.

  *  (Multiplication by g') For each polynomial Q∈ C[x,y] with _y(Q)≤ r_P-1
  there exist polynomials q_j∈ C[x] of degree at most _x(Q)+2r_Pd_P such that
  
    g' Q(x,g) = 1/w_y(P)∑_j=0^r_P-1q_jg^j,

  where w∈ C[x] is the discriminant of P.
  To see this, first apply Observation <ref> (Reduction by P) to rewrite -QP_x as T=1/_y(P)∑_j=0^2r_P-2t_j y^j
  for some t_j∈ C[x] of degree _x(Q)+d_P.
  Then consider an ansatz AP+BP_y=_y(P)T with unknown polynomials A,B∈ C(x)[y] of degrees
  at most r_P-2 and r_P-1, respectively, and compare coefficients with respect to y.
  This gives an inhomogeneous linear system over C(x) with 2r_P-1 variables and equations.
  The claim then follows using Cramer's rule. 



  Let u = vw_y(P)^r_P, where v and w are as in the Observations <ref> and <ref> above.
  Let f be a solution of L and g be a solution of P.
  Then for every ℓ∈ N there are polynomials e_i,j∈ C[x] of degree at most ℓ(u) such that
  
    ∂ ^ℓ (f∘ g) = 1/u^ℓ∑_i=0^r_P-1∑_j=0^r_L-1 e_i,j g^i · (f^(j)∘ g).



This is evidently true for ℓ=0. Suppose it is true for some ℓ. Then

     ∂^ℓ+1 (f∘g) =
  ∑_i=0^r_P-1∑_j=0^r_L-1 (e_i,j/u^ℓ g^i ·(f^(j)∘g))'

     =
  ∑_i=0^r_P-1∑_j=0^r_L-1 (
  e_i,j'u - ℓe_i,ju'/u^ℓ+1 g^i ·(f^(j)∘g) 

         +
  e_i,j/u^ℓ(i g^i-1 ·(f^(j)∘g) + g^i ·(f^(j+1)∘g)) g'
  ).

The first term in the summand expression already matches the claimed bound. To complete the proof, we
show that

    (i g^i-1· (f^(j)∘ g) + g^i · (f^(j+1)∘ g)) g'=1/u∑_k=0^r_P-1q_kg^k

for some polynomials q_k of degree at most (u). Indeed, the only critical term is f^(r_L)∘ g. According to
Observation <ref>, f^(r_L)∘ g can be rewritten as 1/v∑_j=0^r_P-1∑_k=0^r_L-1q_j,kg^j · (f^(k)∘ g)
for some q_j,k∈ C[x] of degree at most d_Ld_P. This turns the left hand side of (<ref>) into an expression
of the form 1/v∑_j=0^2r_P-2q̃_j,kg^j · (f^(k)∘ g) for some polynomials
q̃_j,k∈ C[x] of degree at most d_Ld_P. An (r_P-1)-fold application of Observation <ref> 
brings this expression to the form 1/v_y (P)^r_P-1∑_j=0^r_P-1q̅_j,kg^j · (f^(k)∘ g)
for some polynomials q̅_j,k∈ C[x] of degree at most d_Ld_P+(r_P-1)d_P. Now Observation <ref>
completes the induction argument.



Let r,d∈ N be such that

    r ≥ r_Lr_P
      and  
    d ≥r(3r_P+d_L-1)d_P r_L r_P/r+1-r_L r_P.

Then there exists an operator M∈ C[x][∂ ] of order ≤ r and degree ≤ d
such that for every solution g of P and every solution f of L the composition
f∘ g is a solution of M.
In particular, there is an operator M of order r=r_Lr_P and degree
(3r_P+d_L-1)d_P r_L^2 r_P^2 = Ø((r_P+d_L)d_P r_L^2 r_P^2).



Let g be a solution of P and f be a solution of L. 
Then we have P(x,g(x))=0 and L(f) = 0, and we seek an operator
M=∑_i=0^d∑_j=0^r c_i,j x^i ∂ ^j∈ C[x][∂ ] such that
M(f∘ g)=0. Let r≥ r_Lr_P and consider an ansatz

    M=∑_i=0^d∑_j=0^r c_i,jx^i∂ ^j

with undetermined coefficients c_i,j∈ C.

Let u be as in Lemma <ref>. Then applying M to f∘ g and multiplying by u^r gives an expression
of the form

    ∑_i=0^d+r(u)∑_j=0^r_P-1∑_k=0^r_L-1 q_i,j,kx^i g^j · (f^(k)∘ g),

where
the q_i,j,k are C-linear combinations of the undetermined coefficients c_i,j. Equating all the q_i,j,k
to zero leads to a linear system over C with at most (1+d+r(u))r_Lr_P equations and exactly (r+1)(d+1)
variables. This system has a nontrivial solution as soon as

               (r+1)(d+1)    > (1+d+r(u))r_L r_P 

          (r+1-r_L r_P)(d+1)    > r r_Lr_P(u) 

          d     > -1 + r r_Lr_P(u)/r+1-r_Lr_P.

The claim follows because (u)≤ d_Pd_L+(2r_P-1)d_P+r_Pd_P=(3r_P+d_L-1)d_P. 






§ A DEGREE BOUND FORTHE MINIMAL OPERATOR


According to Theorem <ref>, there is
operator M of order r=r_Lr_P and degree d=Ø((r_P+d_L)d_Pr_L^2r_P^2).
Usually there is no operator of order less than r_Lr_P, but if such an operator
accidentally exists, Theorem <ref> makes no statement about its degree.
The result of the present section (Theorem <ref> below) is a degree bound
for the minimal order operator, which also applies when its order is less than r_Lr_P,
and which is better than the bound of Theorem <ref> if the minimal order
operator has order r_Lr_P.

The following Lemma is a variant of Lemma <ref> in which g is allowed to appear
in the denominator, and with exponents larger than r_P-1. This allows us to keep the
x-degrees smaller. 


  Let f be a solution of L and g be a solution of P.
  For every ℓ∈ N, there exist polynomials E_ℓ, j∈ C[x, y] for 0 ≤ j < r_L 
  such that _x E_ℓ, j≤ℓ(2d_P - 1) and _y E_ℓ, j≤ℓ(2r_P+ d_L - 1) for all 0 ≤ j < r_L, and
  
    ∂^ℓ( f ∘ g) = 1/U(x, g)^ℓ∑_j = 0^r_L - 1 E_ℓ,j(x, g) (f^(j)∘ g),

  where U(x, y) = P_y^2(x, y) l_r_L(y).



  This is true for ℓ = 0. Suppose it is true for some ℓ. Then
  
    ∂^ℓ + 1(f ∘ g) = ( 1/U(x, g)^ℓ∑_j = 0^r_L - 1 E_ℓ, j(x, g) (f^(j)∘ g) )^'
    
        = ∑_j = 0^r_L - 1( ℓ(U_x + g' U_y)/U^ℓ + 1 E_i, j· (f^(j)∘ g) 
    
        + 1/U^ℓ((E_ℓ, j)_x + g' · (E_ℓ, j)_y) (f^(j)∘ g) + 1/U^ℓ E_ℓ, j g' · (f^(j + 1)∘ g) )


  We consider the summands separately. 
  In ℓ(U_x + g' U_y)/U^ℓ + 1, U_x is already a polynomial in x and g of bidegree at most (2d_p - 1, 2r_P + d_L - 1).
  Since g' = -P_x(x, g)/P_y(x, g) and U_y is divisible by P_y, g' U_y is also a polynomial with the same bound for the bidegree.
 
  Futhermore, we can write
  
    (E_ℓ, j)_x + g' · (E_ℓ, j)_y = 1/U (U(E_ℓ, j)_x - P_xP_yl_r_L(g)(E_ℓ, j)_y),

  where the expression in the parenthesis satisfies the stated bound.
  
  For j + 1 < r_L, the last summand can be written as 
  
    1/U^ℓ E_ℓ, j g' · (f^(j + 1)∘ g) = P_xP_yl_r_l(g)/U^ℓ + 1E_ℓ, j· (f^(j + 1)∘ g).

  For j = r_L + 1, due to Observation <ref>
  
    g' · (f^(r_L)∘ g) = -P_xP_y/U∑_j = 0^r_L - 1 l_j(g) (f^(j)∘ g).

  Right-hand sides of both (<ref>) and (<ref>) satisfy the bound.


Let f_1, …, f_r_L be C-linearly independent solutions of L, and let g_1, …, g_r_P be distinct solutions of P.
By r we denote the C-dimension of the C-linear space V spanned by f_i ∘ g_j for all 1 ≤ i ≤ r_L and 1 ≤ j ≤ r_P.
The order of the operator annihilating V is at least r.
We will construct an operator of order r annihilating V using Wronskian-type matrices.


  There exists a matrix A(x,y)∈ C[x,y]^(r + 1) × r_L such that 
  the bidegree of every entry of the i-th row of A(x, y) does not exceed (2rd_P - i + 1, r(2r_P + d_L - 1)) and 
  f ∈ V if and only if the vector (f, …, f^(r))^T lies in 
  the column space of the (r + 1) × r_Lr_P matrix [   A(x, g_1)           ⋯ A(x, g_r_P) ].



  With the notation of Lemma <ref>, let 
  A(x, y) be the matrix whose (i, j)-th entry is E_i - 1, j - 1(x, y) U(x, y)^r + 1 - i.
  Then A(x, y) meets the stated degree bound.

  By W_i we denote the (r + 1) × r_L Wronskian matrix for f_1 ∘ g_i, …, f_r_L∘ g_i.
  Then f ∈ V if and only if the vector (f, …, f^(r))^T lies in the column space of the matrix [   W_1     ⋯ W_r_P ].
  Hence, it is sufficient to prove that W_i and A(x, g_i) have the same column space.
  The following matrix equality follows from the definition of E_i, j
  
    W_i = 1/U(x, g_i)^rA(x, g_i)
      [            f_1 ∘ g_i                    ⋯           f_r_L∘ g_i;           f_1' ∘ g_i                    ⋯           f_r_L∘ g_i;                    ⋮                    ⋱                    ⋮;   f_1^(r_L - 1)∘ g_i                    ⋯ f_r_L^(r_L - 1)∘ g_i ].

  The latter matrix is nondegenerate since it is a Wronskian matrix for the C-linearly independent power series 
  f_1 ∘ g_i, …, f_r_L∘ g_i with respect to the derivation (g_i')^-1∂.
  Hence, W_i and A(x, g_i) have the same column space.


In order to express the above condition of lying in the column space in terms of vanishing of a single determinant, we want to “square” the matrix [ A(x, g_1), ⋯, A(x, g_r_P) ].


  There exists a matrix B(y)∈ C[y]^(r_L r_P - r) × r_L such that the degree of every entry does
  not exceed r_P - 1 and the (r_Lr_P + 1)× r_Lr_P matrix
  
    C =
        [   A(x, g_1)           ⋯ A(x, g_r_P);      B(g_1)           ⋯    B(g_r_P) ]

  has rank r_Lr_P.



  Let D be the Vandermonde matrix for g_1, …, g_r_P,
  and let I_r_L denote the identity matrix.
  Then C_0 = D ⊗ I_r_L is nondegenerate and has the form [ B_0(g_1), …, B_0(g_r_P) ], 
  for some B_0(y)∈ C[y]^r_Lr_P × r_L with entries of degree at most r_P - 1.
  Since C_0 is nondegenerate, we can choose r_Lr_P - r rows which span a complimentary subspace to the row space of [ A(x, g_1), …, A(x, g_r_P) ].
  Discarding all other rows from B_0(y), we obtain B(y) with the desired properties.


By C_ℓ (A_ℓ(x, y), resp.) we will denote the matrix C (A(x, y), resp.) without the ℓ-th row.


  For every 1 ≤ℓ≤ r + 1 the determinant of C_ℓ is divisible by ∏_i < j (g_i - g_j)^r_L



  We show that C_ℓ is divisible by (g_i - g_j)^r_L for every i ≠ j.
  Without loss of generality, it is sufficient to show this for i = 1 and j = 2.
  We have
  
    C_ℓ =
        A_ℓ(x, g_1)-A_ℓ(x, g_2)   A_ℓ(x, g_2)   ⋯   A_ℓ(x, g_r_P)
    B(g_1)-B(g_2)   B(g_2)   ⋯   B(g_r_P).

  Since for every polynomial p(y) we have g_1 - g_2 | p(g_1) - p(g_2), every entry of the first r_L columns in the above matrix is divisible by g_1 - g_2.
  Hence, the whole determinant is divisible by (g_1 - g_2)^r_L.



  The minimal operator M ∈ C[x][∂] annihilating f ∘ g for every f and g such that L(f) = 0 and P(x, g(x)) = 0
  has order r ≤ r_Lr_P and degree at most
  
       2r^2d_P - 12(r-2)(r-1) + rd_Pr_L (2r_P + d_L - 1) - d_P r_L (r_P-1)

       =Ø(r d_Pr_L(d_L+r_P)).
  



  We construct M using C_ℓ for 1 ≤ℓ≤ r + 1.
  We consider some f and by F we denote the (r_Lr_P + 1)-dimensional vector (f, …, f^(r), 0, …, 0)^T.
  If f ∈ V, then the first r + 1 rows of the matrix [ C F ] are linearly dependent, so it is degenerate.
  On the other hand, if this matrix is degenerate, then Lemma <ref> implies that F is a linear combination of the columns of C,  so Lemma <ref> implies that f ∈ V.
  Hence f ∈ V ⇔ C_1f ±⋯ + (-1)^r  C_r + 1f^(r) = 0.
  Due to Lemma <ref>, the latter condition is equivalent to c_1f + ⋯ + c_r + 1f^(r) = 0,
  where c_ℓ= (-1)^ℓ - 1 C_ℓ/∏_i < j (g_i - g_j)^r_L.
  Thus we can take M = c_1 + ⋯ + c_r + 1∂^r.
  It remains to bound the degrees of the coefficients of M.

  Combining lemmas <ref>, <ref>, and <ref>, we obtain
  
    d_X    := _x c_ℓ≤∑_i ≠ℓ (2rd_P+1-i) ≤ 2r^2d_P - 12(r-2)(r-1), 
     
       d_Y    := _g_i c_ℓ≤ rr_L (2r_P + d_L - 1) - r_L(r_P - 1).

  Since c_ℓ is symmetric with respect to g_1, …, g_r_P, it can be written as an element of C[x, s_1, …, s_r_P] 
  where s_j is the j-th elementary symmetric polynomial in g_1, …, g_r_P, 
  and the total degree of c_ℓ with respect to s_j's does not exceed d_Y.
  Substituting s_j with the corresponding coefficient of 1/_y PP(x, y) and clearing denominators, we obtain a polynomial
  in x of degree at most d_X + d_Yd_P.

  Since the order of M is equal to the dimension of the space of all compositions of the form f ∘ g, 
  where L(f) = 0 and P(x, g) = 0, M is the minimal annihilating operator for this space.



  The proof of Theorem <ref> is a generalization of the proof of <cit.>.
  Specializing r_L = 1, d_L = 0 in Theorem <ref> gives a sightly larger bound as the
  bound in <cit.>, but with the same leading term. 


Although the bound of Theorem <ref> for r=r_Lr_P beats the bound of Theorem <ref>
for r=r_Lr_P by a factor of r_P, it is apparently still not tight. Experiments
we have conducted with random operators lead us to conjecture that in fact, at least
generically, the minimal order operator of order r_Lr_P has degree Ø(r_L r_P d_P  (d_L + r_L r_P)).
By interpolating the degrees of the operators we found in our computations,
we obtain the expression in the following conjecture.


  For every r_P,r_L,d_P,d_L≥2 there exist L and P such that the corresponding
  minimal order operator M has order r_Lr_P and degree
   
        r_L^2 (2 r_P(r_P-1) + 1) d_P 
    +r_L r_P (d_P(d_L+1) + 1)
    +d_L d_P

               
    -r_L^2 r_P^2
    -r_L d_L d_P,
  
  and there do not exist L and P for which the corresponding minimal operator M
  has order r_Lr_P and larger degree. 






§ ORDER-DEGREE-CURVEBY SINGULARITIES


A singularity of the minimal operator M is a root of its leading coefficient polynomial _∂(M)∈ C[x].
In the notation and terminology of <cit.>, a factor p of this polynomial is called removable at cost n if there exists an operator
Q∈ C(x)[∂] of order _∂(Q)≤ n such that QM∈ C[x][∂] and (_∂(QM),p)=1.
A factor p is called removable if it is removable at some finite cost n∈ N, and non-removable otherwise. 
The following theorem <cit.> translates information about the removable singularities of a minimal operator
into an order-degree curve.

 Let M∈ C[x][∂], and let p_1,…,p_m∈ C[x] be pairwise coprime
  factors of _∂(M) which are removable at costs c_1,…,c_m, respectively. Let r≥_∂(M)
  and
  
    d≥_x(M)-⌈∑_i=1^m(1-c_i/r-_∂(M)+1)^+_x(p_i)⌉,

  where we use the notation (x)^+:=max{x,0}. Then there exists an operator Q∈ C(x)[∂] such that
  QM∈ C[x][∂] and _∂(QM)=r and _x(QM)=d. 


The order-degree curve of Theorem <ref> is much more accurate than that of Theorem <ref>.
However, the theorem depends on quantities that are not easily observable when only L and P are known.
From Theorem <ref> (or Conj. <ref>), we have a good bound for _x(M). In the
the rest of the paper, we discuss bounds and plausible hypotheses for the degree and the cost of the removable factors.
The following example shows how knowledge about the degree of the operator and the degree and cost of its removable
singularities influence the curve. 


  The figure below compares the data of Example <ref> with the curve obtained from Theorem <ref>
  using m=1, _x(M_min)=544, _x(p_1)=456, c_1=1.
  This curve is labeled (a) below. Only for a few orders r, the curve slightly overshoots.
  In contrast, the curve of Theorem <ref>, labeled (b) below, overshoots significantly
  and systematically.
  
  The figure also illustrates how the parameters affect the accuracy of the estimate.
  The value _x(M_min)=544 is correctly predicted by Conjecture <ref>. If we
  use the more conservative estimate _x(M_min)=1568 of Theorem <ref>,
  we get the curve (e). 
  For curve (d) we have assumed a removability degree of _x(p_1)=408, as predicted by Theorem <ref>
  below, instead of the true value _x(p_1)=456.
  For (c) we have assumed a removability cost c_1=10 instead of c_1=1.
  

    [yscale=.6,xscale=1.2,scale=1]
      
      
      
      
      
      [->] (0,0)–(0,8) node[left] d;
      [->] (0,0)–(4,0) node[right] r;
      in 1,...,7 (0,)–(-.1,) node[left] 00;
      in 1,...,3 (,0)–(,-.1) node[below] 00;
      (-1,-1) rectangle (5,8);
      [ultra thin, variable=,̊domain=.09:2,samples=50]
        plot (,432*/̊(100*-̊8));
        plot (,.08*(-31+1100*)̊/(100*-̊8));
        plot (,min(5.44,.08*(482+1100*)̊/(100*-̊8)));
        plot (,1.36*(-5+100*)̊/(100*-̊8));
        plot (,8*(.97+11.00*)̊/(100*-̊8));
      
      [ultra thin, variable=,̊domain=2:4,samples=5]
        plot (,432*/̊(100*-̊8));
        plot (,.08*(-31+1100*)̊/(100*-̊8));
        plot (,.08*(482+1100*)̊/(100*-̊8));
        plot (,1.36*(-5+100*)̊/(100*-̊8));
        plot (,8*(.97+11.00*)̊/(100*-̊8));
      
      [ultra thin] (.50,5.14286) – ++(.33,.5) node[above right,xshift=-2pt,yshift=-2pt] b;
      [ultra thin] (.50,1.96571) – ++(.33,.5) node[above right,xshift=-2pt,yshift=-2pt] c;
      [ultra thin] (.50,1.45714) – ++(.33,.5) node[above right,xshift=-2pt,yshift=-2pt] d;
      [ultra thin] (.60,1.16077) – ++(-.33,-.5) node[below left,xshift=2pt,yshift=2pt] e;
      [ultra thin] (1.5,.912113) – ++(.33,-.5) node[below right,xshift=-2pt,yshift=2pt] a;
      
      (.09,5.44) node ·
(.10,3.16) node ·
(.11,2.40) node ·
(.12,2.02) node ·
(.13,1.79) node ·
(.14,1.64) node ·
(.15,1.53) node ·
(.16,1.45) node ·
(.17,1.38) node ·
(.18,1.33) node ·
(.19,1.29) node ·
(.20,1.26) node ·
(.21,1.23) node ·
(.22,1.20) node ·
(.23,1.18) node ·
(.24,1.16) node ·
(.25,1.14) node ·
(.26,1.13) node ·
(.27,1.12) node ·
(.28,1.10) node ·
(.29,1.09) node ·
(.30,1.08) node ·
(.31,1.07) node ·

(.33,1.06) node ·
(.34,1.05) node ·
(.35,1.04) node ·

(.37,1.03) node ·

(.39,1.02) node ·

(.41,1.01) node ·


(.44,1.00) node ·


(.47,.99) node ·


(.50,.98) node ·



(.54,.97) node·




(.59,.96) node·






      (.66,.95) node·
      (.74,.94) node·      
      (.85,.93) node·   
      (1.00,.92) node·   
      (1.23,.91) node·
      (1.61,.90) node·
      ;
    
  







 §.§ Degree of Removable Factors



  Let P(x, y)∈ C[x, y] be a polynomial with _y P = d, and R(x) = _y(P, P_y).
  Assume that α∈C̅ is a root of R(x) of multiplicity k.
  Then the squarefree part
  
    S(y) = P(α, y)/( P(α, y), P_y(α, y) )

  of P(α, y) has degree at least d - k.



  Let M(x) be the Sylvester matrix for P(x, y) and P_y(x, y) with respect to y.
  The value R^(k)(α) is of the form ∑ M_i(α), where every M_i(x) has
  at least 2d - 1 - k common columns with M(x). Since R^(k)(α) ≠ 0, at least one of 
  these matrices is nondegenerate. Hence, M(α) ≤ k.
  On the other hand, M(α) is equal to the dimension of the space of pairs of polynomials
  (a(y), b(y)) such that a(y)P(α, y) + b(y)P_y(α, y) = 0 and b(y) < d.
  Then b(y) is divisible by S(y), and for every b(y) divisible by S(y) there exists exactly one a(y).
  Hence, M(α) = d -  S(y) ≤ k.


Let M be the minimal order operator annihilating all compositions f∘ g of a solution of P with a solution of L.
The leading coefficient q = _∂(M)∈ C[x] can be factored as q = q_q_, 
where q_ and q_ are the products of all removable and all nonremovable factors of _∂(M), respectively.


  q_≤ d_P(4r_Lr_P - 2r_L + d_L).



  For α∈C̅ by π_α (λ_α, μ_α, resp.) we denote r_P
  (r_L or _∂ M, resp.) 
  minus the number of solutions of P(x, g(x)) = 0 (the dimension of the solutions set of Lf(x) = 0 or Mf(x) = 0, resp.)
  in C̅[[x - α]].

  Corollary 4.3 from <cit.> implies that _α q_ (the minimal order at α in _α_α(M) in notation of <cit.>)
  is equal to μ_α (_α B_α(M) - (s_α + 1) in notation of <cit.>).
  Summing over all α, we have ∑_α∈C̅μ_α =  q_.
  Bounding the degree of the nonremovable part of _∂ (L) by d_L, we also have ∑_α∈C̅λ_α≤ d_L.
  
  Let R(x) be the resultant of P(x, y) and P_y(x, y) with respect to y.
  Let α be a root of R(x) of multiplicity k.
  Lemma <ref> implies that the degree of the squarefree part of P(α, y) is at least r_P - k.
  So, at most k roots are multiple, so at least r_P - 2k roots are simple.
  Hence, P(x, y) = 0 has at least r_P - 2k solutions in C̅[[x - α]].
  Thus ∑_α∈C̅π_α≤ 2 R ≤ 2d_P(2r_P - 1).

  Let α∈C̅ and let g_1(x), …, g_r_P - π_α(x) ∈C̅[[x - α]] 
  be solutions of P(x, g(x)) = 0.
  Let β_i = g_i(0) for all 1 ≤ i ≤ r_P - π_α.
  Since the composition of a power series in x - β_i with g_i(x) is a power series in x - α,
  
    μ_α≤ r_L π_α + ∑_i = 1^r_P - π_αλ_β_i.

  We sum (<ref>) over all α∈C̅.
  The number of occurrences of λ_β in this sum for a fixed β∈C̅ is equal to the number
  of distinct power series of the form
  g(x) = β + ∑ c_i (x - γ)^i such that P(x, g(x)) = 0.
  Inverting these power series, we obtain distinct Puiseux series solutions of P(x, y) = 0 at y = β, so this number does not exceed d_P.
  Hence
  
    ∑_α∈C̅μ_α≤ r_L ∑_α∈C̅π_α + d_P ∑_β∈C̅λ_β≤ 2r_L d_P(2r_P - 1) + d_Pd_L.-1ex



In order to use Theorem <ref>, we need a lower bound for q_.
Theorem <ref> gives us an upper bound for _x M, but we must also estimate the difference _x M - _∂ M.
By N_α we denote the Newton polygon for M at α∈C̅∪{∞}
(for definitions and notation, see <cit.>).
By H_α, we denote the difference of the ordinates of the highest and the smallest vertices of N_α,
and we call this quantity the height of the Newton polygon.
Note that H_∞≤_x M - _∂ M.
This estimate together with the Lemma above implies
q_≥_x(M)-H_∞-d_P(4r_Lr_P - 2r_L + d_L). 

The equation P(x, y) = 0 has r_P distinct Puiseux series solutions g_1(x), …, g_r_P(x) at infinity.
For 1 ≤ i ≤ r_P, let β_i = g_i(∞) ∈C̅∪{∞}, and let ρ_i be the order of
zero of g_i(x) - β_i (1/g_i(x), resp.) at infinity if β_i ∈C̅ (β_i  = ∞, resp.).
The numbers ρ_1, …, ρ_r_P are positive rationals and can be read off from Newton polygons of P (see <cit.>).


  H_∞≤∑_i=1^r_Pρ_i H_β_i.



  Writing L as L(x, ∂) ∈ C[x][∂], we have
  
    M = ( L(g_1, 1/g_1'∂), …, L( g_r_P, 1/g_r_P'∂) ).

    Hence, the set of edges of N_∞ is a subset of the union of sets of edges of Newton polygons of the operators L(g_i,1/g_i'∂),
  so the height of N_∞ is bounded by the sum of the heights of the Newton polygons of these operators.
  Consider g_1 and assume that β_1 ∈C̅.
  Then the Newton polygon for L at β_1 is constructed from the set of monomials of L written as an element of C(x - β_1)[(x - β_1)∂].
  Let L(x, ∂) = L̃(x - β_1, (x- β_1)∂), then
  
    L(g_1, 1/g_1'∂)
      = L̃( g_1 - β_1, g_1-β_1/g_1'∂)
      = L̃( x^-ρ_1h_1(x), xh_2(x) ∂),

  where h_1(∞) and h_2(∞) are nonzero elements of C̅.
  Since h_1 and h_2 do not affect the shape of the Newton polygon at infinity, the Newton polygon at infinity for L(g_1, 1/g_1'∂) 
  is obtained from the Newton polygon for L at β_1 by stretching it vertically by the factor ρ_1,
  so its height is equal to ρ_1H_β_1.

  The case β_1 = ∞ is analogous using L = L̃( 1/x, -x∂).



  Generically, the β_i's will be ordinary points of L, so it is
  fair to expect H_β_i=0 for all i in most situations.


The following theorem is a consequence of Theorem <ref> and the discussion above.


  Let ρ_1, …, ρ_r_P be as above.
  Assume that all removable singularities of M are removable at cost at most c.
  Let δ = ∑_i = 1^r_Pρ_i H_β_i + d_P(4r_Lr_P - 2r_L + d_L).
  Let r ≥_∂ M + c - 1 and
  
    d ≥δ·(1-c/r-_∂(M)+1) + _x M ·c/r - _∂ (M) + 1.

  Then there exists an operator Q ∈ C(x)[∂] such that QM ∈ C[x][∂] and _∂ (QM) = r and _x (QM) = d.


Note that _x(M) may be replaced with the expression from Theorem <ref>
or Conjecture <ref>.





 §.§ Cost of Removable Factors


The goal of this final section is to explain why in the case r_P > 1 one can almost always choose c=1 in Theorem <ref>.

For a differential operator L ∈ C[x][∂], by M(L) we denote the minimal operator M such that Mf(g(x)) = 0 whenever L f = 0 and P(x, g(x)) = 0.
We want to investigate the possible behaviour of a removable singularity at α∈ C when L varies and P with r_P>1 is fixed.
Without loss of generality, we assume that α = 0.

We will assume that:

  
  (S1) P(0, y) is a squarefree polynomial of degree r_P;

  -
  (S2) g(0) is not a singularity of L for any root g(x) of P;

  -
  (G) Roots of P(x, g(x)) = 0 at zero are of the form g_i(x) = α_i + β_i x + γ_i x^2 + …, where β_2, …, β_r_P are nonzero, 
  and either β_1 or γ_1 is nonzero.


Conditions [s1](S1) and [s2](S2) ensure that zero is not a potential true singularity of M(L).
Condition [g](G) is an essential technical assumption on P.
We note that it holds at all nonsingular points (not just at zero) for almost all P, because this condition is violated at α iff some root of P(α, y) = P_x(α, y) = 0 (this means that at least one of β_i is zero) is also a root of either P_xx(α, y) = 0 (then γ_i is also zero) or P_xy(α, y) = 0 (then there are at least two such β's).
For a generic P this does not hold. 

Under these assumptions we will prove the following theorem.
Informally speaking, it means that if M(L) has an apparent singularity at zero, then it almost surely is removable at cost one.


  Let d_L be such that d_L ≥ (r_Lr_P - r_L + 1)r_P.
  By V we denote the (algebraic) set of all L ∈C̅[x][∂] of order r_L and degree ≤ d_L 
  such that the leading coefficient of L does not vanish at α_1, …, α_r_P.
  We consider two (algebraic) subsets in V
  
          X    = { L ∈V | M(L) has an apparent singularity at 0},

          Y    = { L ∈V | M(L) has an apparent singularity at 0

                which is not removable at cost one }.
   
   Then, X >  Y as algebraic sets. 

   
For α∈C̅, by _α(r, d) we denote the space of differential operators in C̅[x - α][∂] of order at most r and degree at most d.
By _α(r, d) ⊂_α(r, d) we denote the set of L such that L = r and (_∂ L) (α) ≠ 0. 
Then 
    V ⊂_α_1(r_L, d_L) ∩…∩_α_r_P (r_L, d_L).


To every operator L ∈_α(r, d_0) and d_1 ≥ r, we assign a fundamental matrix of degree d_1 at α, denote it by F_α(L, d_1).
It is defined as the r × (d_1 + 1) matrix such that the first r columns constitute the identity matrix I_r, 
and every row consists of the first d_1 + 1 terms of some power series solution of L at x = α.
Since L ∈_α(r, d_0), F(L, d_1) is well defined for every d_1.

By F(r, d) we denote the space of all possible fundamental matrices of degree d for operators of order r.
This space is isomorphic to 𝔸^r(d + 1 - r).
The following proposition says that a generic operator has generic and independent fundamental matrices, so we can work with these matrices instead of working with operators.


  Let φ V →( F(r_L, r_Lr_P) )^r_P be the map sending L ∈ V to F_α_1(L, r_Lr_P) ⊕…⊕ F_α_r_P(L, r_Lr_P).
  Then φ is a surjective map of algebraic sets, and all fibers of φ have the same dimension.


For the proof we need the following lemma.

  Let ψ_α(r, d) → F(r, d + r) be the map sending L to F_α(L, d + r).
  Then ψ is surjective and all fibers have the same dimension.



  First we assume that L is of the form L = ∂^r_L + a_r_L - 1(x) ∂^r_L - 1 + … + a_0(x), 
  and a_j(x) = a_j, dx^d + … + a_j, 0, where a_j, i∈C̅.
  We also denote the truncated power series corresponding to the j + 1-st row of F(L, d + r_L) by f_j and write it as
  
    f_j = x^j + ∑_i = 0^d b_j, i x^r_L + i,  where  b_j, i∈C̅.

  We will prove the following claim by induction on i:
          
  Claim. For every 0 ≤ j ≤ r_L - 1 and every 0 ≤ i ≤ d, b_j, i can be written as a polynomial in a_p, q with q < i and a_j, i.
  And, vice versa, a_j, i can be written as a polynomial in b_p, q with q < i and b_j, i.
  
  The claim would imply that ψ defines an isomorphism of algebraic varieties between F_α(r_P, d + r) and the subset of monic operators in _α(r, d).
      
  For i = 0, looking at the constant term of L (f_j), we obtain that j! a_j, 0 + r_L! b_j, 0 = 0.
  This proves the base case of the induction.
  
  Now we consider i > 0 and look at the constant term of ∂^i L(f_j).
  The operator ∂^i L can be written as
  
    ∂^i L    =
    ∂^i + r_L + a_r_L - 1^(i)(x) ∂^r_L - 1 + …+ a_0^(i)(x)

           + ∑_k < i, l < i + r_L, s ≤d c_k, l, s a_s^(k)(x) ∂^l 
  
  Applying this to f_j, we obtain the following expression for the constant term:
  
    (i + r_L)! b_j, i + j! i! a_j, i + ∑_k < i, l < i + r_L, s ≤ dc̃_k, l, s a_s, k b_j, l - r_L = 0.

  Applying the induction hypothesis to the equalities
  
    b_j, i = -1/(i + r_L)!( j! i! a_j, i + ∑_k < i, l < i + r_L, s ≤ dc̃_k, l, s a_s, k b_j, l - r_L)

  
    a_j, i = -1/i! j!( (i + r_L)! b_j, i + ∑_k < i, l < i + r_L, s ≤ dc̃_k, l, s a_s, k b_j, l - r_L)

  we prove the claim.

  The above proof also implies that F(L, d + r) is completely determined by the truncation of L at degree d + 1.
  So, for arbitrary L ∈_α(r, d), F(L, d) = F(L̃, d), where L̃ is the truncation of 1/_∂ L L at degree d + 1,
  which is monic in ∂.
  Hence, every fiber of ψ is isomorphic to the set of all polynomials of degree at most d with nonzero constant term.
  This set is isomorphic to C̅^*×C̅^d.



  Let d_0=r_Lr_P - r_L.
  We will factor φ as a composition 
  
    V ⊕_i=1^r_P_α_i(r_L, d_0)
           F(r_L, r_Lr_P)^r_P,

  where φ_2 is a component-wise application of F_α_i(∗, d_0) and φ_1 sends L ∈ V to 
  a vector whose i-th coordinate is the truncation at degree d_0 + 1 of L written as an element of C̅[x - α_i][∂].
  We will prove that both these maps are surjective with fibers of equal dimension.

  The map φ_1 can be extended to 
    φ_1_0(r_L, d_L) →_α_1(r_L, d_0) ⊕…⊕_α_r_P(r_L, d_0).

  This map is linear, so it is sufficient to show that the dimension of the kernel is equal to the difference of the dimensions of the source space and the target space.
  The latter number is equal to (d_L + 1)(r_L + 1) - (d_0 + 1)(r_L + 1)r_P.
  Let L ∈φ_1.
  This is equivalent to the fact that every coefficient of L is divisible by (x - α_i)^d_0 + 1 for every 1 ≤ i ≤ r_P.
  The dimension of the space of such operators is equal to (r_L + 1)(d_L + 1 - r_P(d_0 + 1)) ≥ 0, so φ_1 is surjective.

  Lemma <ref> implies that φ_2 is also surjective and all fibers are of the same dimension.





Let g_1(x), …, g_r_P(x) ∈C̅[[x]] be solutions of P(x, y) = 0 at zero.   
Recall that g_i(x) = α_i + β_i x + … for all 1 ≤ i ≤ r_P, and by [g](G) we can assume that β_2, …, β_r_P are nonzero.

Consider A ∈ F(r_L, d), assume that its rows correspond to truncations of power series f_1, …, f_r_L∈C̅[[x - α_i]].
By ε(g_i, A) we denote the r_L × (d + 1)-matrix whose rows are truncations of f_1∘ g_i, …, f_r_L∘ g_i ∈C̅[[x]] at degree d + 1.


  We can write ε(g_i, A) = A · T(g_i),
  where T(g_i) is an upper triangular (d + 1) × (d + 1)-matrix depending only on g_i
  with 1, β_i, …, β_i^d on the diagonal.

  Futhermore, if β_i = 0 and g_i(x) = α_i + γ_i x^2 + …, then the i-th row of T(g_i)
  is zero for i ≥d + 3/2,
  and starts with 2(i - 1) zeroes and γ_i^i - 1 for i<d+3/2.



  Let the j-th row of A correspond to a polynomial f_j(x - α_i) = x^j - 1 + O(x^r_L).
  The substitution operation f_j → f_j ∘ g_i is linear with respect to coefficients of f_i, so ε(g_i, A) = A · T(g_i) for some matrix T(g_i).
  Since the coefficient of x^k in f_j ∘ g_i is a linear combination of coefficients of (x - α_i)^l with l ≤ k in f_j, the matrix T(g_i) is upper triangular.
  Since (x - α_i)^k ∘ g_i = β_i^k x^k + O(x^k + 1), T(g_i) has 1, β_i, …, β_i^d on the diagonal.

  The second claim of the lemma can be verified by a similar computation.



  If β_i ≠ 0, then the matrix ε(g_i, A) has the form (A_0  A_1), where A_0 is an upper triangular matrix over C̅, and the entries of A_1 are linearly independent linear forms in the entries of A.


An element of the affine space W = ( F(r_L, r_L r_P))^r_P is a tuple of matrices N_1, …, N_r_P∈ F(r_L, r_Lr_P), where
every N_i has the form N_i = (E_r_L Ñ_i).
Entries of Ñ_1, …, Ñ_r_P are coordinates on W, so we will view entries of Ñ_i as a set X_i of algebraically independent variables.
We will represent N as a single (r_L r_P) × (r_L r_P + 1)-matrix

    N = [   N_1;     ⋮; N_r_P ], and set ε(N) = [     ε(g_1, N_1);               ⋮; ε(g_r_P, N_r_P) ].


For any matrix A, by A_(1) and A_(2) we denote A without the last column and without the last but one column, respectively.
By π we denote the composition ε∘φ.
Since π(L) represents solutions of M(L) at zero truncated at degree r_Lr_P + 1, properties of the operator L ∈ V can be described in terms of the matrix π(L):

  
  * M(L) has order less than r_L r_P or has an apparent singularity at zero iff π(L)_(1) is degenerate;
  
  * M(L) has order less than r_L r_P or has an apparent singularity at zero which is either not removable at cost one or of degree greater than one iff both π(L)_(1) and π(L)_(2) are degenerate.

Let X_0 = { L ∈ V |π(L)_(1) = 0} and Y_0 = { L ∈ V |π(L)_(2) = 0},
then X_0 ∖ Y_0 ⊂ X ⊂ X_0 and Y ⊂ Y_0.


  φ(X_0) is an irreducible subset of W, and φ(Y_0) is a proper algebraic subset of φ(X_0).



  The above discussion and the surjectivity of φ imply that φ(X_0) = { N ∈ W |ε(N)_(1) = 0}.
  Hence, we need to prove that ε(N)_(1) is a nonzero irreducible polynomial in R = C̅[ X_1, …, X_r_P ].
  We set A = ε(N)_(1).
  
  We claim that there is a way to reorder columns and rows of A such that it will be of the form
  
    [   B C_1; C_2   D ],

  where B and D are square matrices, and
  
    
  * B is upper triangular with nonzero elements of C̅ on the diagonal;
    
  * entries of D are algebraically independent over the subalgebra generated in R by entries of B, C_1, and C_2.
  
  In order to prove the claim we consider two cases:
  
    
  * β_1 ≠ 0. By Corollary <ref>, A is already of the desired form with B being an r_L × r_L-submatrix.
    
  * β_1 = 0. Then [g](G) implies that g_1(x) = α_1 + γ_1 x^2 + … with γ_1 ≠ 0.
    Then Lemma <ref> implies that the following permutations would give us the desired block structure with B being an ⌊ 3r_L / 2 ⌋×⌊ 3r_L / 2 ⌋-submatrix,
    for columns:
    
    1, 3, …, 2r_L - 1, 2, 4, …, 2⌊ r_L / 2⌋, ∗,

    and for rows:
    
    1, 2, …, r_L,r_L + 2, r_L + 4, …, r_L + 2⌊ r_L / 2 ⌋,∗,

    where ∗ stands for all other indices in any order.
  
  Using elementary row operations, we can bring A to the form
  
    [ B ∗; 0 D ],

  where the entries of D are still algebraically independent.
  Hence, A is proportional to D which is irreducible.

  In order to prove that φ(Y_0) is a proper subset of φ(X_0) it is sufficient to prove that ε(N)_(2) is not divisible by ε(N)_(1).
  This follows from the fact that these polynomials are both of degree r_Lr_P - r_L with respect to (algebraically independent) 
  entries of Ñ_2, …, Ñ_r_P, but involve different subsets of this variable set.


Now we can complete the proof of Theorem <ref>.
Proposition <ref> implies that φ(X_0) > φ(Y_0).
Since all fibers of φ have the same dimension, X_0 >  Y_0.
Hence, X ≥ (X_0 ∖ Y_0) =  X_0 >  Y_0 ≥ Y.


  Theorem <ref> is stated only for points satisfying [s1](S1) and [s2](S2).
  However, the proof implies that every such point is generically nonsingular.
  We expect that the same technique can be used to prove that generically no removable singularities occur
  in points violating conditions [s1](S1) and [s2](S2).
  This expectation agrees with our computational experiments with random operators and random polynomials.
  We think that these experimental results and Theorem <ref> justify the choice c = 1 in Theorem <ref>
  in most applications. 



  On the other hand, neither Theorem <ref> nor our experiments support the choice c=1 in the
  case r_P=1. Instead, it seems that in this case the cost for removability is systematically larger. To
  see why, consider the special case P=y-x^2 of substituting the polynomial g(x)=x^2 into a 
  solution f of a generic operator L. If the solution space of L admits a basis of the form
  
       1       + a_1,r_Lx^r_L       + a_1,r_L+1x^r_L+1 + ⋯,

       x       + a_2,r_Lx^r_L       + a_2,r_L+1x^r_L+1 + ⋯,

       ⋮

       x^r_L-1       + a_r_L-1,r_Lx^r_L       + a_r_L-1,r_L+1x^r_L+1 + ⋯,
  
  and M is the minimal operator for the composition, then its solution space obviously has the basis
  
       1       + a_1,r_Lx^2r_L       + a_1,r_L+1x^2r_L+2 + ⋯,

       x^2       + a_2,r_Lx^2r_L       + a_2,r_L+1x^2r_L+2 + ⋯,

       ⋮

       x^2(r_L-1)       + a_r_L-1,r_Lx^2r_L       + a_r_L-1,r_L+1x^2r_L+2 + ⋯,
  
  and so the indicial polynomial of M is λ(λ-2)⋯(λ-2(r_L-1)).
  According to the theory of apparent singularities <cit.>, M has a removable
  singularity at the origin and the cost of removability is as high as r_L.

  More generally, if g is a rational function and α is a root of g', so that
  g(x)=c+Ø((x-α)^2), a reasoning along the same lines confirms that such
  an α will also be a removable singularity with cost r_L.




Acknowledgement. We thank the referees for their constructive critizism.

plain


