LMOpRightEuclideanDivision¶

Euclidean division of linear Mahler operators¶

Calling sequence:¶

$\operatorname{LMOpRightEuclideanDivision}(L_1, L_2, x, M, b)$

Parameters:¶

  • $L_1$, a linear Mahler operator
  • $L_2$, a linear Mahler operator
  • $x$, a name
  • $M$, the name of the Mahler operator
  • $b$, a posint not smaller than $2$ (a radix)

Description:¶

  • $\operatorname{LMOpRightEuclideanDivision}$ performs the Euclidean division of linear Mahler operators, that is given $L_1$ and $L_2$ two polynomials in $M$ with rational functions in $x$ coefficients, it provides a sequence of two linear Mahler operators $Q$ and $R$ (the quotient and the remainder) such that $L_1 = Q L_2 + R$ with either $R = 0$, or the order of $R$ (its degree with respect to $M$) is smaller than the order of $L_2$. Let us remind that the product is not commutative in the context, so that this is a right Euclidean division.
  • The procedure is extended to the case of linear Mahler operators whose coefficients are ramified rational functions.

References:¶

  • Philippe Dumas (1993). Récurrences mahlériennes, suites automatiques, études asymptotiques. Thèse de doctorat, Université Bordeaux I.
  • Frédéric Chyzak and Bruno Salvy (1998). Non-commutative elimination in Ore algebras proves multivariate identities. Journal of Symbolic Computation, 26(2):187--227.

Example:¶

In [1]:
libname := libname, FileTools:-JoinPath(["maple","lib","dcfun.mla"],base=homedir):
In [2]:
 with(dcfun):
Out[2]:

Let us consider the lowest common left multiple $L$ of two simple linear Mahler operators $L_1$ and $L_2$.

In [3]:
 b := 2;
Out[3]:

$$2$$

In [4]:
 L1 := RamRatPolyToLMOp(1/(1 - 2*x), x, M , b);
Out[4]:

$$2 x -1-\left(2 x^{2}-1\right) M$$

In [5]:
 L2 := RamRatPolyToLMOp(1/(1 - 3*x), x, M , b);
Out[5]:

$$-1+3 x -\left(3 x^{2}-1\right) M$$

In [6]:
 L := LMOpLCLM([L1,L2],x , M, b);
Out[6]:

$$\left(6 x^{8}-5 x^{4}+1\right) M^{2}+\left(-6 x^{6}-6 x^{5}-x^{4}+5 x^{3}+4 x^{2}-x -1\right) M +6 x^{4}+x^{3}-4 x^{2}+x$$

We perform the divisions of $L$ by $L_1$ and $L_2$. As expected, we find that both remainders $R_1$ and $R_2$ are zero.

In [7]:
 Q1, R1 := LMOpRightEuclideanDivision(L, L1, x, M, b);
Out[7]:

$$\left(-3 x^{4}+1\right) M +3 x^{3}+2 x^{2}-x, 0$$

In [8]:
 Q2, R2 := LMOpRightEuclideanDivision(L, L2, x, M, b);
Out[8]:

$$\left(-2 x^{4}+1\right) M +2 x^{3}+x^{2}-x, 0$$

In [9]:
 [R1, R2];
Out[9]:

$$[0, 0]$$

Let us now consider a case where we use ramified rational functions in the coefficients. We search for the order $1$ right factors of a given linear Mahler operator $L$.

In [10]:
 b := 3;
Out[10]:

$$3$$

In [11]:
 L := (x^3 + 2*x - 1)*(x^6 - x^3 + 1)*(x^6 + x^3 + 1)*M^2 - (x^2 + 1)*(x^10 + x^9 + 2*x^5 + x - 1)*M + x*(x^9 + 2*x^3 - 1);
Out[11]:

$$\left(x^{3}+2 x -1\right) \left(x^{6}-x^{3}+1\right) \left(x^{6}+x^{3}+1\right) M^{2}-\left(x^{2}+1\right) \left(x^{10}+x^{9}+2 x^{5}+x -1\right) M +x \left(x^{9}+2 x^{3}-1\right)$$

In [12]:
 ric_sol := LMOpSolve(L, x, M, b, 'output' = 'riccati', 'free' = K);
Out[12]:

$$\left\{\frac{K_{2} x^{\frac{9}{2}}-x^{3} K_{1}-K_{2} x^{\frac{3}{2}}-K_{1}}{\left(x^{2}+x +1\right) \left(x^{2}-x +1\right) \left(K_{2} x^{\frac{3}{2}}-K_{1} x -K_{2} \sqrt{x}-K_{1}\right)}\right\}$$

We find one parametrization, the parameter $(K_1:K_2)$ being in the projective space ${\mathbb P}_1(\mathbb Q)$. The parametrization appears as a ramified rational function of $x$.

In [13]:
 u := op(ric_sol);
Out[13]:

$$\frac{K_{2} x^{\frac{9}{2}}-x^{3} K_{1}-K_{2} x^{\frac{3}{2}}-K_{1}}{\left(x^{2}+x +1\right) \left(x^{2}-x +1\right) \left(K_{2} x^{\frac{3}{2}}-K_{1} x -K_{2} \sqrt{x}-K_{1}\right)}$$

Let us verify that we actually have a right factor.

In [14]:
 Q, R := LMOpRightEuclideanDivision(L, M - u, x, M, b);
Out[14]:

$$-\frac{\left(x^{\frac{39}{2}} K_{2}-x^{18} K_{1}+2 x^{\frac{35}{2}} K_{2}-2 x^{\frac{33}{2}} K_{2}-2 x^{16} K_{1}-2 x^{\frac{29}{2}} K_{2}+2 K_{2} x^{\frac{27}{2}}-2 x^{13} K_{1}+2 x^{\frac{23}{2}} K_{2}-2 x^{\frac{21}{2}} K_{2}-2 x^{10} K_{1}-2 x^{\frac{17}{2}} K_{2}+2 x^{\frac{15}{2}} K_{2}-2 x^{7} K_{1}+2 x^{\frac{11}{2}} K_{2}-2 K_{2} x^{\frac{9}{2}}-2 x^{4} K_{1}-2 x^{\frac{5}{2}} K_{2}+K_{2} x^{\frac{3}{2}}-2 K_{1} x +K_{1}\right) M}{-K_{2} x^{\frac{9}{2}}+x^{3} K_{1}+K_{2} x^{\frac{3}{2}}+K_{1}}-\frac{3 x^{\frac{13}{2}} K_{2}+2 x^{9} K_{1}-2 x^{\frac{19}{2}} K_{2}+x^{\frac{25}{2}} K_{2}+x^{11} K_{1}-x^{\frac{31}{2}} K_{2}+x^{15} K_{1}+2 x^{\frac{17}{2}} K_{2}-2 x^{\frac{15}{2}} K_{2}+2 x^{7} K_{1}+x^{13} K_{1}-x^{\frac{23}{2}} K_{2}+x^{\frac{21}{2}} K_{2}+x^{\frac{29}{2}} K_{2}-K_{2} x^{\frac{27}{2}}+x^{14} K_{1}+x^{12} K_{1}-3 x^{\frac{11}{2}} K_{2}+x^{5} K_{1}-x^{\frac{7}{2}} K_{2}+x^{\frac{5}{2}} K_{2}+x^{10} K_{1}+2 x^{8} K_{1}+x^{4} K_{1}+x^{6} K_{1}-K_{1} x^{2}+3 K_{2} x^{\frac{9}{2}}-x^{3} K_{1}-K_{2} x^{\frac{3}{2}}-K_{1} x}{-K_{2} x^{\frac{9}{2}}+x^{3} K_{1}+K_{2} x^{\frac{3}{2}}+K_{1}}, 0$$

In [15]:
 R;
Out[15]:

$$0$$

The remainder is $0$, as expected.