LMOpLCLM¶

lowest common left multiple for linear Mahler operators¶

Calling sequence:¶

$\operatorname{LMOpLCLM}({\mathit Lset}, x, M, b)$

Parameters:¶

  • ${\mathit Lset}$, list or set of linear Mahler operators
  • $x$, a name
  • $M$, the name of the Mahler operator
  • $b$, the radix of the Mahler operator
  • optionally a name as a fifth parameter to assign to it the list of cofactors, assuming that ${\mathit Lset}$ was given as a list
  • option ${\mathit output}$' = '$\mathit{polynomial}$' / '$\mathit{monic}$'

Description:¶

  • $\operatorname{LMOpLCLM}({\mathit Lset}, x, M, b)$ returns the LCLM of the operators given in the input.
  • The LCLM is the lowest common multiple which lies in ${\mathbb k}[x]\langle M\rangle$ (where $\mathbb k$ is the ground field) and has content wrt $M$ equal to $1$. As a consequence, the LCLM is defined up to a constant, and the use of the definite article is strictly speaking incorrect. A supplementary constraint is necessary to obtain the uniqueness, for example that the LCLM be monic.
  • The keyword parameter '${\mathit output}$' permits the user to choose between two forms for the output: either polynomial in $M$ and in $x$ too, or monic with respect to $M$ (hence possibly with rational functions coefficients in $x$).

References:¶

  • Philippe Dumas (1993). Récurrences mahlériennes, suites automatiques, études asymptotiques. Thèse de doctorat, Université Bordeaux I.
  • Alin Bostan, Frédéric Chyzak, Ziming Li, and Bruno Salvy (2012). Fast Computation of Common Left Multiples of Linear Ordinary Differential Operators. ISSAC ’12.

Example:¶

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

We define two simple linear Mahler operators.

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

$$$$

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

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

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

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

In [6]:
 LL := [L1, L2];
Out[6]:

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

We compute their lowest common left multiple.

In [7]:
 L := LMOpLCLM(LL, x , M, b);
Out[7]:

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

Euclidean division confirms that we have a common multiple.

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

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

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

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

The Euclidean divisions provide us with the cofactors of each linear Mahler operator. It is possible to obtain them directly with a name as fifth argument given to $\operatorname{LMOpLCLM}$.

In [10]:
 L := LMOpLCLM(LL, x, M, b, 'kof');
Out[10]:

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

Let us compare the obtained expressions.

In [11]:
 kof;
Out[11]:

$$[\left(-3 x^{9}+1\right) M +3 x^{7}-x^{6}+3 x^{5}-x^{4}+3 x^{3}-x^{2}, \left(-2 x^{9}+1\right) M +2 x^{7}-x^{6}+2 x^{5}-x^{4}+2 x^{3}-x^{2}]$$

In [12]:
 Q1 := collect(Q1, M, factor);
Out[12]:

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

In [13]:
 Q2 := collect(Q2, M, factor);
Out[13]:

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

In order to impose uniqueness on the lowest common left multiple, we can impose that it be monic (wrt $M$).

In [14]:
 LMOpLCLM(LL, x, M, b, 'kof', 'output' = 'monic');
Out[14]:

$$M^{2}-\frac{\left(6 x^{12}+6 x^{10}-5 x^{9}+6 x^{8}-5 x^{7}+7 x^{6}-5 x^{5}+x^{4}-5 x^{3}+x^{2}+1\right) M}{6 x^{18}-5 x^{9}+1}+\frac{x^{2} \left(6 x^{6}-5 x^{5}+7 x^{4}-5 x^{3}+7 x^{2}-5 x +1\right)}{6 x^{18}-5 x^{9}+1}$$

In [15]:
 kof;
Out[15]:

$$\left[-\frac{M}{2 x^{9}-1}+\frac{x^{2} \left(3 x^{5}-x^{4}+3 x^{3}-x^{2}+3 x -1\right)}{6 x^{18}-5 x^{9}+1}, -\frac{M}{3 x^{9}-1}+\frac{x^{2} \left(2 x^{5}-x^{4}+2 x^{3}-x^{2}+2 x -1\right)}{6 x^{18}-5 x^{9}+1}\right]$$