Linear Functional Equations and Twisted Polynomials

Moumouni Djassibo Woba

Unité de Formation et de Recherche/Sciences et Techniques, Université de Ouahigouya, Mèra, Burkina Faso.

DOI: 10.4236/jamp.2024.124090                

Abstract

A certain variety of non-switched polynomials provides a uni-figure representation for a wide range of linear functional equations. This is properly adapted for the calculations. We reinterpret from this point of view a number of algorithms.

Keywords

Functional Equations, Twisted Polynomials, Rings, Morphisms, Euclidian Division

1. Introduction

The functional equations were introduced to 1820 in the previous century by Euler and Alembert and were fashionable [1] .

The resolution of algebraic equations is a very old problem that has shaped many mathematical works [2] . This article is composed of three sections:

In the first section, we will present a unified framework for the manipulation of linear systems linking derivatives $f_i^{\left(j\right)}\left(x\right)$ , offices $f_i\left(x+j\right)$ , or substitutions $f_i\left(q^{i}x\right)$ of unknown functions $f_i\left(x\right)$ . To this end, we will introduce new families of polynomials in an indeterminate having the property that this indeterminate does not commute with the coefficients of the polynomials.

This defection of repeat re-folds a kind of law of Leibniz.

In the second section, we are brought to consider simultaneously the functions x and functions of another variable.

In the third section and the following, we will support them with particular properties of the ring polymers ring when the ring A has construction is a body, which we consider of the form $\mathbb{Q}\left(x\right)$ .

2. Ease of Use

Non-commutative polynomials to calculate with linear operators

Let’s remember of Leibniz relationship for two functions by noting the derivation operator [3] :

$fetg:{\left(fg\right)}^{\prime }\left(x\right)=f^{\prime }\left(x\right)g\left(x\right)+f\left(x\right)g^{\prime }\left(x\right).$ (1)

Noting D the derivation operator, M one who has a function f associated with the function given by:

$M\left(f\right)\left(x\right)=xf\left(x\right),$

The identity operator on functions and, the composition of operators, the rule of Leibniz given, for $f\left(x\right)=x$ and g any,

$\left(D\circ M\right)\left(g\right)=D\left(M\left(g\right)\right)=M\left(D\left(g\right)\right)+g=\left(M\circ D+id\right)\left(g\right).$

The identity being verified by any function g, we obtain equality:

$D\circ M=M\circ D+id$ .

between differential linear operators.

Other operators check analogues of the rule of Leibniz: the operator Δ of finite difference, defined by:

$\Delta \left(f\right)\left(x\right)=f\left(x+1\right)-f\left(x\right);$

the operator:

$S=\Delta +id$

Offset, defined by:

$S\left(f\right)\left(x\right)=f\left(x+1\right);$

For a constant q fixed other than 0 and 1, the operator H of expansion, defined by:

$H\left(f\right)\left(x\right)=f\left(qx\right).$ (2)

We have the relationships:

$\Delta \left(fg\right)\left(x\right)=f\left(x+1\right)\Delta \left(g\right)\left(x\right)+\Delta \left(f\right)\left(x\right)g\left(x\right),$

$\left(fg\right)\left(x+1\right)=f\left(x+1\right)g\left(x+1\right),$

$\left(fg\right)\left(qx\right)=f\left(qx\right)g\left(qx\right),$

That leads n relationship rate:

$\begin{array}{l}\Delta \circ M=\left(M+id\right)\circ \Delta +id,\\ S\circ M=\left(M+id\right)\circ S,\\ H\circ M=Q\circ M\circ H\end{array}$

Between linear operators, after having introduced a new operator Q given by $Q\left(f\right)\left(x\right)=qf\left(x\right).$

The following definition provides the same algebraic framework for these different operator contexts.

2.1. Definition

Either A a commutative ring of characteristic zero, which we assume has an injective endomorphism σ and a σ-derivation δ, in the sense that for a and for b of A,

$\begin{array}{l}\sigma \left(a+b\right)=\sigma \left(a\right)+\sigma \left(b\right),\\ \sigma \left(ab\right)=\sigma \left(a\right)\sigma \left(b\right),\\ \delta \left(ab\right)=\sigma \left(a\right)\delta \left(b\right)+\delta \left(a\right)b.\end{array}$ (3)

For undetermined news $\partial$ , we call ring of twisted polynomials the algebra on A generated by $\partial$ and relationships, for everything a of A, $\partial a=\sigma \left(a\right)\partial +\delta \left(a\right).$

We note this ring A $\langle \partial ;\sigma ,\delta \rangle$ [4] .

An immediate consequence of the definition is that any element f of a twisted polynomial ring admits a canonical recreation of the shape $f=a_r{\partial }^r+\cdots +a_0$ .

For some $a_i$ in A, with $a_r$ not zero unless the sum does not include any term (and so f = 0). The $a_i$ the whole r thus defined (exe = except for f = 0) are unique and r has the properties of a degree In particular, the degree of a product is the sum of the degrees of its factors. This results from the in jectivity of σ and integrity, by the form:

$\left(a{\partial }^r+\cdots \right)\left(b{\partial }^s+\cdots \right)=a{\sigma }^r\left(b\right){\partial }^{r+s}+\cdots$

because $a{\sigma }^r\left(b\right)$ it is zero if and only if a or b the east. Adequate choices of σ and δ make the few examples given above. For simplifying the rating, we assume that A can be bound to a good function of functions [5] .

Noting 0, the application that has any function, combines the current zero function. All algebra-operations are at coefficients in $Q\left(x\right)$ ; we also have analogues for $A=Q\left[x\right]$ and, when σ, S, for $A=Q\left[x,x^{-1}\right]$ . Paying attention to the rating. If the composition between operators is noted by $\circ$ , we will only make a juxtaposition for the product of twisted polynomials, and we note 1 the neutral element for the product of twisted polynomials. However, we will abuse the notation to note the derivation with respect to an x in the same way, Dx, whatever the ring A,and id, without clue, for the identity of any A. Moreover, we will simply note x for M. The case $\delta =0$ is common, and we then write $A\langle \partial ;\sigma \rangle$ , without reference to 0. Just as in the commutative case, we define the polynomials of Laurent, whose algebra is noted $A\left[X,X^{-1}\right]$ , and in which

$X{X}^{-1}=X^{-1}X=1$ ,

In case, σ is invertible and other than identity makes it possible to represent operators, which have an inverse. In this case, we will note $A\langle \partial ,{\partial }^{-1};\sigma \rangle$ , the algebra where:

$\partial a=\sigma \left(a\right)\partial ,{\partial }^{-1}a={\sigma }^{-1}\left(a\right){\partial }^{-1},\partial {\partial }^{-1}={\partial }^{-1}\partial =1$ .

2.2. Ideals, Modules, and Actions

The rings of twisted polynomials have been denied by their switching rule, without reference to any operator their interpretation as algebragitors, as well as the properties of the calculations in the following sections, expresses better in terms of some non-switched algebraic structures that we figure in this section The algebraic structures that will be used in the frame of the general rings, that is to say, non-switched: a ring R is the data of a set of a first internal law + called addition, which makes it a switching group of neutral 0, as well as a second internal law called multiplication and denoted by juxtaposition, which makes it a monoid of neutral and is distributive to the left and right on the addition. The “switched rings” already used in the previous chapters and in the definition 1.2 of the “ring of twisted polynomials” are rings (in the general sense that has just been indicated) which requires the multiplication or switchable. A ring polyreels is a particular ring [6] .

Just as the switching rings have ideals, definised as subsets closed by multiplication on the left and right by any element of the ring, the general rings have ideals, but we do not usually learn in the closing of one side. An ideal on the left I of a ring R is a subgroup of R (for add) such as $fg\in I$ for everything $f\in R$ and everything $g\in I$ . A notation of ideal on the right could be defined in an analogous way: in all that follows, we will say simple ideal for ideal on the left. For a finished family $g_1,\cdots ,g_s$ elements of R, the sums $f_1{g}_1+\cdots +f_s{g}_s$ for the coefficients $f_i\in R$ constituent an ideal noted $R{g}_1+\cdots +R{g}_s$ , called ideal generated by $g_1,\cdots ,g_s$ . Any ring R perhaps seen as an ideal of himself. A model on the left M on a ring R an additive group with an addition + and a neutral 0, stable under the action of an external multiplication law on the left by the elements of R, called scalar multiplication, distributive to the left on the addition of R and to the right on the addition of M, and such that for all r and s of R and m of M, $\left(rs\right)\cdot m=r\cdot \left(s\cdot m\right)$ and $1\cdot m=m$ . A notion of module on the right could be decimated in a similar manner; In all of the following, we will just say module for module on the left. This notion generalizes the ideal: an ideal I and R is a module on R, obtained by taking the multiplication of R as a scalar multiplication. For a finie family $g_1,\cdots ,g_s$ elements of module M fixed, the sums $f_1{g}_1+\cdots +f_s{g}_s$ for coefficients $f_i\in R$ constitute a module S note $R{g}_1+\cdots +R{g}_s$ , called generated module by $g_1,\cdots ,g_s$ . It is a sub-module of M on R, in the sense that it is a module over obtained by restriction to S addition of M and scalar multiplication. There is also action of R on M the scalar multiplication law of a module M. For a given module M on R, let G be a family ${\left(g_i\right)}_{\in I}$ of elements of M. The family G is a system of generators M if for everything $m\in M$ , there is a family finie ${g^{\prime }}_1,\cdots ,{g^{\prime }}_s$ of G and coefficients $f_i\in R$ such as $m={f^{\prime }}_s{g^{\prime }}_1+\cdots +{f^{\prime }}_s{g^{\prime }}_s$ [7] .

The family G The family is free if any linear dependence relationship.

${f^{\prime }}_1{g^{\prime }}_1+\cdots +{f^{\prime }}_s{g^{\prime }}_s=0$ obtained for a subfolder finie ${g^{\prime }}_1,\cdots ,{g^{\prime }}_s$ of G implication that all $f_i$ are zero.

The family G is a basis for M whether it is a system of generators and if it is free. A module is said to be free if it has a base. For the rings R that interest us, namely the switching rings and the ring of rich polynomials at coeffiients in a switching ring, if a free module on R a database, the cardinal of this base is independent of the choice of the base. In the case of drastic bases, this cardinal is called the module rank. A special important case is that of the cartesian product $R_n$ for $n\in \mathbb{N}$ , which provides a module for coordinated addition to coordinate and for scalar multiplication obtained by multiplying each coordinate by the same element of R. It is a free module of rank n, basic constituted by the elements $e_i=\left(0,\cdots ,0,1,0,\cdots ,0\right)$ , Where the unique 1 is in position i [8] . To connect rings of twisted polynomials and algebras of operators, we now make the rings of twisted polynomials act on these function spaces, in the sense of the action of a ring on a module. But a ring of twisted polynomials has no unique action on a given function space, so we adopt the conventions force throughout the rest of the article:

· A ring of the shape A $\langle \partial ;\sigma \rangle$ acts by $\partial \cdot f=\sigma \left(f\right)$ for a suitable extension of σ.

· A ring of the shape A $\langle \partial ;\sigma ,\delta \rangle$ acts by $\partial \cdot f=\delta \left(f\right)$ for a suitable extension of δ.

· The coefficients in A act by simple multiplication, $a\cdot f=af$ .

Note that the algebra of sequence $A^{\mathbb{N}}$ cannot be seen as a module on the ring A $\langle \partial ,{\partial }^{-1};\sigma \rangle$ when σ is the forward shift. In fact, the action of $\partial$ on the sequence worth 1 in 0 and then zero gives the sequence zero: the action of $\partial$ cannot therefore be reversed. This technical problem can be circumvented by considering the classes of sequences identified when they are equal after a certain rank (which depends on the two sequences). (We speak of “seed of sequence to infinity”). But we then lose the possibility of expressing certain sequences, those with finite support, precisely.

3. Morphisms between Rings of Twisted Polynomials

In this section, we are led to consider simultaneously functions of x and functions of another variable. Therefore, we will indicate the variable to which these objects refer in subscripts of $D,S,\partial ,\sigma ,\delta$ , etc. In addition, the A rings used to construct the rings of twisted polynomials are of the form $\mathbb{Q}\left[x\right]$ or $\mathbb{Q}\left[x,x^{-1}\right]$ .

3.1. Differentially Finite Generator Series and Suite

We’ve already seen that when a series of $f={\displaystyle {\sum }_{n\ge 0}{u}_n{x}^n}$ differentially finite, its coefficients verify a finite recurrence relation. In other words, the following $u={\left(u_n\right)}_{n\ge 0}$ is polynomially recurrent. Evidence rests on identities:

$xf={\displaystyle {\sum }_{n\ge 1}{u}_{n-1}{x}^n}={\displaystyle {\sum }_{n\ge 1}\left({\partial }_n^{-1}\cdot u\right)\left(n\right)x^n}$ (4)

and

$D_x\left(f\right)=f^{\prime }={\displaystyle {\sum }_{n\ge 1}\left(n+1\right)u_{n+1}{x}^n}={\displaystyle {\sum }_{n\ge 1}\left(\left(n+1\right){\partial }_n\cdot u\right)\left(n\right)x^n}$

where we introduced the ring $\mathbb{Q}\left[n\right]\langle {\partial }_n,{\partial }_n^{-1};S_n\rangle$ [9] .

Par recurrence, this or that

$\begin{array}{c}{x}^{\alpha }{D}_x^{\beta }\left(f\right)=\underset{n\ge \alpha }{{\displaystyle \sum }}\left({\partial }_n^{-\alpha }\left(\left(n+1\right){\partial }_n^{\beta }\right)\cdot u\right)\left(n\right)x^n\\ =\underset{n\ge \alpha }{{\displaystyle \sum }}\left(\left(n+1-\alpha \right)\cdots \left(n+\beta -\alpha \right){\partial }_n^{\beta -\alpha }\cdot u\right)\left(n\right)x^n.\end{array}$

For a series f solution of the differential equation,

$a_r\left(x\right)f^{\left(r\right)}\left(x\right)+\cdots +a_0\left(x\right)f\left(x\right)=0$

Either $a_i$ in $\mathbb{Q}\left[x\right]$ , this gives us a recurrence on u, valid for n big enough. This recurrence is expressed in terms of twisted polynomials as follows. The differential operator associated with the equation is represented by the twisted polynomial $L=a_r\left(x\right){\partial }_x^r+\cdots +a_0\left(x\right)$ in $\mathbb{Q}\left[x\right]\langle {\partial }_r,\text{id};D_x\rangle$ on $\mathbb{Q}$ .

In this way, the differential equation is written $L\cdot f=0$ , also introduces algebra $\mathbb{Q}\left[n\right]\langle {\partial }_n,{\partial }_n^{-1};S_n\rangle$ and the morphism of algebras µ defined by:

$\mu \left(x\right)={\partial }_n^{-1}\text{et}\mu \left(\partial x\right)=\left(n+1\right){\partial }_n$ . (5)

So, the sequence u of the coefficients is the solution for n large enough of the recurrence represented by the image $\mu \left(L\right)$ [10] .

To understand for which n, this recurrence is valid, let’s write:

$\mu \left(L\right)=b_p\left(n\right){\partial }_n^p+\cdots +b_q\left(n\right){\partial }_n^q$ for $p\le q$ and $b_p{b}_q\ne 0$ ,

so that the recurrence takes the form:

$\left(\mu \left(L\right)\cdot u\right)\left(n\right)=b_p\left(n\right)u_{n+p}+\cdots +b_q\left(n\right)u_{n+p}=0$ and is true for all.

n if $p\ge 0$ and for all $n\ge -p$ if $p<0$ .

Dually, a polynomially recurring sequence u has a generating series $f={\displaystyle {\sum }_{n\ge 0}{u}_n{x}^n}$ differentially finite, which we will find in terms of twisted polynomials. For this point, we actually assume that the sequence u is extended to negative indices by $u_n=0$ for $n<0$ , and that it is polynomially recurrent over the entire Z. This does not constitute any loss of generality. A recurrence valid for the initial sequence becomes valid for the extended sequence after multiplication by a polynomial of the form $\left(n+1\right)\left(n+2\right)\cdots \left(n+r\right)$ . The formulas:

${\displaystyle {\sum }_{n\in \mathbb{Z}}n{u}_n{x}^n}=x{\partial }_x\cdot f$ and ${\displaystyle {\sum }_{n\in \mathbb{Z}}{u}_{n+1}{x}^n}=x^{-1}f$

Give by recurrence:

${\displaystyle {\sum }_{n\ge 0}{n}^{\alpha }{u}_{n+\beta }{x}^n}={\left(x{\partial }_x\right)}^{\alpha }{x}^{-\beta }\cdot f=x^{-\beta }{\left(x{\partial }_x-\beta \right)}^{\alpha }\cdot f$ ,

and provide another morphism, ν, de $\mathbb{Q}\left[n\right]\langle {\partial }_n;S_n\rangle$ in $\mathbb{Q}\left[x,x^{-1}\right]\langle {\partial }_r,\text{id};D_x\rangle$ , given by $\nu \left(n\right)=x{\partial }_x$ and by $\nu \left({\partial }_n\right)=x^{-1}$ . For a sequence u solution on Z of the recurrence equation,

$b_p\left(n\right)u_{n+p}+\cdots +b_0\left(n\right)u_n=0$

where $b_i$ is in $\mathbb{Q}\left[n\right]$ , we introduce the twisted polynomial $P=b_p\left(n\right){\partial }_n^p+\cdots +b_0\left(n\right)$ de $\mathbb{Q}\left[n\right]\langle {\partial }_n;S_n\rangle$ .

To obtain a differential relation on the generating series f, we consider $\nu \left(P\right)$ which we write $\nu \left(P\right)=a_0\left(x\right)+\cdots +a_r\left(x\right){\partial }_x^r$ .

Then, as ${\displaystyle {\sum }_{n\ge 0}\left(P\cdot u\right)\left(n\right)x^n}=0$ , the f series verifies the differential relationship:

$a_0\left(x\right)f\left(x\right)+\cdots +a_r\left(x\right)f^{\left(r\right)}\left(x\right)=0.$

Algebraically, the preceding properties are expressed by the fact that μ extends into an isomorphism of algebras between $Q\left[x,x^{-1}\right]\langle {\partial }_x,id;D_x\rangle$ and $Q\left[n\right]\langle {\partial }_n,{\partial }_n^{-1};S_n\rangle$ , the inverse of which extends ν [11] . This morphism verifies $\mu \left(x^i\right)={\partial }_n^{-i}$ and

$\mu \left({\partial }_x^{-i}\right)={\left(\left(n+1\right){\partial }_n\right)}^i=\left(n+1\right)\cdots \left(n+i\right){\partial }_n^{-1}.$ (6)

Both isomorphic algebras can be seen as acting naturally on $\mathbb{Q}((x))=\left\{x^{r}f|r\in \mathbb{N},f\in \mathbb{Q}[[x]]\right\}$ , which is none other than the algebra of sequences on Z null for indices n strictly less than an integer-r (depending on the sequence considered).

3.2. Changes in Variables

When a differentially finite series f(x) is the solution of a differential equation $L\cdot f=0$ given by a twisted polynomial,

$L=L\left(x,{\partial }_x\right)=a_r\left(x\right){\partial }_n^{r}x+\cdots +a_0\left(x\right),$ (7)

for any constant λ ≠ 0, the series $g\left(x\right)=f\left(\lambda x\right)$ checked $g^{\left(i\right)}\left(x\right)={\lambda }^i{f}^{\left(i\right)}\left(\lambda x\right)$ for each $i\in \mathbb{N}$ . Substituting λx for x in $L\cdot f=0$ , we obtain that g is the solution of the differential equation associated with:

$L\left(\lambda x,{\lambda }^{-1}{\partial }_x\right)=a_r\left(\lambda x\right){\lambda }^{-r}{\partial }_x^r+\cdots +a_0\left(\lambda x\right).$

This is again the result of a morphism of algebras, Λ, defined this time by $\Lambda \left(x\right)=\lambda x$ and $\Lambda \left({\partial }_x\right)={\lambda }^{-1}{\partial }_x$ . When f is a differentially finite function, the $z\mapsto f\left(1/z\right)$ is also differentially finite, this time in z, as long as the compound function makes sense. Indeed, for any function g, let us note $\tilde{g}\left(z\right)=g\left(1/z\right)$ (with the same reservation of definition). Since $g\left(x\right)=\tilde{g}\left(1/x\right)$ , by derivation, we have $g^{\prime }\left(x\right)=-{\tilde{g}}^{\prime }\left(1/x\right)/x^2$ , what is the evaluation in $z=1/xde-z^2{\partial }_z\cdot \tilde{g}$ . In other words, we have ${\tilde{g}}^{\prime }=-z^2{\partial }_z\cdot \tilde{g}$ , check from where by recurrence:

$\widetilde{g^{\left(\beta \right)}}={\left(-z^2{\partial }_z\right)}^{\beta }\cdot \tilde{g}.$

Thus, $\tilde{f}$ is differentially finite, given as satisfying the differential equation associated with the image of L by the morphism of $Q\left[x\right]\langle {\partial }_x,id;D_x\rangle$ in $Q\left[Z,Z^{-1}\right]\langle {\partial }_Z,id;D_Z\rangle$ who sends x on $Z^{-1}$ and ${\partial }_x$ on $-Z^2{\partial }_Z$ .

4. Euclidien Division

In this and the following sections, we rely on special properties of rings of twisted polynomials when the ring A of the construction is a field, which we will take from the form $Q\left(x\right)$ [12] . The commutation $\partial a=\sigma \left(a\right)\partial +\delta \left(a\right)$ in $Q\left(x\right)\langle \partial ;\sigma ,\delta \rangle$ allows you to write any twisted polynomial as $a_0\left(x\right)+\cdots +a_r\left(x\right){\partial }^r$ , for rational fractions $a_i$ of $Q\left(x\right)$ Unique. A consequence of the injectivity of σ is the existence of a well-defined degree in $\partial$ : the integer r of the previous writing when a_r is non-zero. In particular, the degree of a product $L_1{L}_2$ of twisted polynomials is the sum of the degrees of the $L_i$ . It follows that the Euclidean division of the commutative case, and the whole theory derived from it, is transposed with few alterations into the twisted case.

4.1. Division Process

The main difference with the commutative case is that there is a distinction between Euclidean division on the left and Euclidean division on the right. Given our interpretation in terms of linear operators, we will only consider right-hand division, which is done by subtracting left-hand multiples [13] . Or to be divided $A=a_r\left(x\right){\partial }^r+\cdots +a_0\left(x\right)$ of degree r by $B=b_s\left(x\right){\partial }^s+\cdots +b_0\left(x\right)$ of degree s. We assume $s\le r$ . So, ${\partial }^{r-s}B={\sigma }^{r-s}\left(b_s\left(x\right)\right){\partial }^r$ lower-order terms, where the power of σ represents one iteration (by composition), and so $A-a_r\left(x\right){\sigma }^{r-s}{\left(b_s\left(x\right)\right)}^{-1}{\partial }^{r-s}B$ is of degree strictly less than r. This reduction step is the elementary step of Euclidean division. By iterating the process, we arrive at a remainder R of degree strictly less than s. By grouping the left-hand factors, we get a left-hand quotient Q such that $A=QB+R$ .

4.2. Example (Division Process)

Consider the ring $Q\left(n\right)\langle {\partial }_n;S_n\rangle$ twisted polynomials representing offset operators [14] . The division of

$A=\left(n^2-1\right){\partial }_n^2-\left(n^3+3n^2+n-2\right){\partial }_n+\left(n^3+3n^2+2n\right)$ ,

that cancels out linear combinations of n! and n, by

$B=n{\partial }_n^2-\left(n^2+3n+1\right){\partial }_n+\left(n^2+2n+1\right),$

that cancels out linear combinations of n! and 1, is written:

$A=n^{-1}\left(n^2-1\right)B-n^{-1}\left(n^2+n+1\right){\partial }_n-\left(n+1\right).$

The rest is a multiple of ${\partial }_n-\left(n+1\right)$ , which represents recurrence $u_n=\left(n+1\right)u_n$ , verified by the factorial. Note a property of this division: if A is multiplied on the left by a factor $m\left(x\right)$ without B being changed, then Q and R are multiplied on the left by the same factor $m\left(x\right)$ . This is no longer (usually) true for a factor involving $\partial$ .

4.3. Power Reduction of ∂

Euclidean division gives us a new interpretation of the calculus of the N-the term of a polynomially recurring sequence $u=\left(u_n\right)$ relative to ring $\mathbb{Q}\left(n\right)\langle {\partial }_n;S_n\rangle$ . Suppose u is the solution of the recurrence equation,

$a_r\left(n\right)u_{n+r}+\cdots +a_0\left(n\right)u_n=0.$ (8)

By unrolling the recurrence, we see that $u_n$ may, for any N, unless undue cancellation of $a_r$ , get into the form:

${\alpha }_{r-1,N}{u}_{r-1}+\cdots +{\alpha }_{0,N}{u}_0$ .

More generally, we have a relationship that rewrites $u_{n+N}$ in terms of $u_{n+r-1},\cdots ,u_n$ . To get it, let’s associate the twisted polynomial with the recurrence on u $P=a_r\left(n\right){\partial }_n^r+\cdots +a_0\left(n\right)$ . For a given N, the Euclidean division of ${\partial }_n^N$ by P is written ${\partial }_n^N=Q_N\left(n\right)P+{\alpha }_{r-1,N}\left(n\right){\partial }_n^{r-1}+\cdots +{\alpha }_{0,N}\left(n\right)$ for rational fractions ${\alpha }_{i,N}\left(n\right)$ . After applying to you and evaluating in u, we get:

$u_{n+N}=0+{\alpha }_{r-1,N}\left(n\right)u_{n+r-1}+\cdots +{\alpha }_{0,N}\left(n\right)u_n$

Hence, the result announced for ${\alpha }_{i,N}={\alpha }_{i,N}\left(0\right)$ [15] .

5. Solution Finding and Operator Factoring

As for the usual commutative polynomial rings, a notion of factorization is present for the rings of twisted polynomials. An important nuance lies in the relationship between the “zeros” of twisted polynomials and the position of the factors. We will see that the factorization of twisted polynomials is related to the algorithms seen in this book for the search for polynomial, rational, and hypergeometric solutions in the case of recurrences. Moreover, there is no longer any uniqueness of the factors, even with order and modulo multiplication by units. An example is given in the differential case by the infinity of factorizations:

${\partial }^2=\left(\partial +\frac{1}{x+r}\right)\left(\partial -\frac{1}{x+r}\right)$

when r is a constant.

In the case of a commutative polynomial w factoring in the form uv for polynomial factors of degree at least 1, any zero of you and any zero of v is zero of w; Conversely, if we are to place ourselves in an algebraic enclosure, any zero α of W provides a factor $x-\alpha$ and an exact quotient $u\left(x\right)$ such that $w\left(x\right)=u\left(x\right)\left(x-\alpha \right)$ . The phenomenon is different in the twisted case, as evidenced by inequality:

${\partial }^2\ne \left(\partial +\frac{1}{x+r}\right)\left(\partial -\frac{1}{x+r}\right)$

when r is a constant. More generally, a factorization $L=PQ$ in A $\langle \partial ;\sigma ,\delta \rangle$ (where A is a body) has different properties depending on the factor: a solution f of the equation $Q\cdot f=0$ is still a solution of $L\cdot f=0$ , because $L\cdot f=P\cdot \left(Q\cdot f\right)=P\cdot 0=0$ ; but a solution g of P gives rise to solutions f of L only by the relation $Q\cdot f=g$ [16] .

Conversely, a solution f of L gives rise to a right-factor of ordre 1 of L, provided that we extend A by f and al its iterations by σ and δ. This factor is of the form $\partial -\left(\partial \cdot f\right)/f$ , i.e. $\partial -\delta \left(f\right)/f$ or $\partial -\sigma \left(f\right)/f$ depending on the action of the ring of twisted polynomials on the functions. Algorithms for finding solutions in particular classes therefore implicitly provide, for each solution found, a right-factor of order 1. They therefore naturally act as the basis for factorization algorithms. Specifically, in the differential case, a polynomial or rational solution f of an equation $L\cdot f=0$ for L in the ring $Q\left[x\right]\langle {\partial }_x;S_x\rangle$ provides a straight factor $D={\partial }_x-\left(D_x\cdot f\right)/f$ where $\left(D_x\cdot f\right)/f$ is rational; in the recurrence case, a polynomial, rational, or hypergeometric solution f of an equation $L\cdot f=0$ for L in the ring $Q\left[x\right]\langle {\partial }_x;S_x\rangle$ provides a straight factor $D={\partial }_x-S_x\left(f\right)/f$ où $S_x\left(f\right)/f$ is rational. In both cases, the quotient Q such that L = QD also has rational coefficients.

5.1. Example (Solution Finding and Operator Factoring 1)

A simple example, in reality without a strict extension of A, is given in $A=Q\left(x\right)\langle {\partial }_x;id,D_x\rangle$ by operator:

$L=x^2\left(4x^2+5\right){\partial }_x^3-x\left(8x^4+14x^2-5\right){\partial }_x^2-\left(4x^4+17x^2+5\right){\partial }_x-2x^3\left(4x^2+9\right),$

of which a particular solution is $f=\exp x^2$ . This solution can be verified from:

$Dx\cdot f=2xf,D_x^2\cdot f=\left(4x^2+2\right)f\text{and}{D}_x^3\cdot f=\left(8x^3+12x\right)f$

by declaring null and void:

$\begin{array}{l}{x}^2\left(4x^2+5\right)\left(8x^3+12x\right)-x\left(8x^4+14x^2-5\right)\left(4x^2+2\right)\\ -\left(4x^4+17x^2+5\right)\left(2x\right)-2x^3\left(4x^2+9\right)\end{array}$

By Euclidian division, we find:

$L=x^2\left(4x^2+5\right){\partial }_x^2-x\left(4x^2-5\right){\partial }_x+4x^4+13x^2-5\left({\partial }_x-2x\right)$

It is shown that L has no other unitary non-trivial right factor.

5.2. Example (Solution Finding and Operator Factoring 2)

The Operator $L=2\left(2x+3\right){\partial }_x^2+3\left(5x+7\right){\partial }_x+9\left(x+1\right)$ provides another example, for $A=Q\left[x\right]\langle {\partial }_x;S_x\rangle$ . As a particular solution is ${\left(-3\right)}^x$ , which is obtained by Petkovšek’s algorithm and can be established simply by observing the nullity of L in ${\partial }_x=-3$ , a right factor of L is ${\partial }_x+3$ , and a Euclidean division shows:

$L=\left(2\left(2x+3\right){\partial }_x+3\left(x+1\right)\right)\left({\partial }_x+3\right).$

It is shown that L has no other unitary non-trivial right factor. Euclid’s algorithm: It is classical that Euclidean commutative rings:

· Those in which the existence of a degree allows a Euclidean division;

· Are principal: Any ideal can be generated by a single generator. This is the case with rings of commutative polynomials with coefficients in a field. The pgcd p of two polynomials f and g is then the only unitary polynomial giving rise to the ideal (f, g), the sum of the ideals (f) and (g). It is calculated as the last non-zero remainder by Euclid’s algorithm. For a ring of twisted polynomials $A=K\langle \partial ;\sigma ,\delta \rangle$ on a field K, the situation is the same if we take care to consider only left-hand ideals, i.e. Euclid’s algorithm extended in a ring of twisted polynomials [17] .

Entrée F and F’ in $A=K\langle \partial ;\sigma ,\delta \rangle$ .

Sortie a pgcdd G of F and F’, the cofactors you and V of a Bézout relation $G=UF+V{F}^{\prime }$ , of the cofactors R and S giving a ppcmg:

$RF=-S{F}^{\prime }\mathrm{.1.}{P}_0:=F;U_0:=1;V_0:=0;P_1:=F^{\prime };U_1:=0;V_1:=1;i:=1.$

1) As long as $P_i$ is non-zero:

a) Calculate the Quotient $Q_{i-1}$ and the rest $P_{i+1}$ of the Euclidean division to the right of $P_{i-1}$ by $P_i$ , so that $P_{i-1}:=Q_{i-1}{P}_i+P_{i+1}$ ;

b) $U_{i+1}:=U_{i-1}-Q_i{U}_i$ ; $V_{i+1}:=V_{i-1}-Q_i{V}_i$ ;

c) $i:=i+1$ .

2) Send back $G=R_{i-1}$ , $\left(U,V\right)=\left(U_{i-1},V_{i-1}\right)$ and $\left(R,S\right)=\left(U_i,V_i\right)$ with the fence by multiplying on the left by the elements of A. The resulting notions are Euclidean divisions on the right and greater common divisors on the right (pgcdd).

Eithers P₀ and P₁ two polynomials of A. if P₁ is not zero, we write the Euclidean division of P₀ and P₁, form $P_0=Q_0{P}_1+P_2$ . As long as $P_{i+2}$ is not zero, we reiterate by dividing $P_{i+1}$ by $P_{i+2}$ .

Either j the final value of i, such as $P_{j+1}=0$ and $P_{j+2}=0$ .

So:

$\left(\begin{array}{c}{P}_0\\ P_1\end{array}\right)=\left(\begin{array}{cc}{Q}_0& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}{P}_1\\ P_2\end{array}\right)=\cdots =\left(\begin{array}{cc}{Q}_0& 1\\ 1& 0\end{array}\right)\cdots \left(\begin{array}{cc}{Q}_j& 1\\ 1& 0\end{array}\right)\left(\begin{array}{c}{P}_{j+1}\\ 0\end{array}\right),$ (9)

from which it is deduced that $P_{j+1}$ split P₀ and P₁ to the right:: $P_0=F{P}_{j+1}$ and $P_1=G{P}_{j+1}$ for twisted polynomials F and G adéquats. Then, inverting the matrices:

$\left(\begin{array}{c}{P}_{j+1}\\ 0\end{array}\right)=\left(\begin{array}{cc}U& V\\ R& S\end{array}\right)\left(\begin{array}{c}{P}_0\\ P_1\end{array}\right)$ for

$\left(\begin{array}{cc}U& V\\ R& S\end{array}\right)=\left(\begin{array}{cc}0& 1\\ 1& -Q_j\end{array}\right)\cdots \left(\begin{array}{cc}0& 1\\ 1& -Q_0\end{array}\right)\text{.}$

Especially, $P_{j+1}=U{P}_0+V{P}_1$ is part of the ideal on the left $A{P}_0+A{P}_1$ . Any element $L=M{P}_0+N{P}_1$ is also a multiple of $P_{j+1}$ : $L=\left(MF+NG\right)P_{j+1}$ . By normalizing $P_{j+1}$ for make it unitary, we therefore obtain a pgcdd distinguished from P₀ and P₁. On the other hand, the twisted polynomial $R{P}_0=-S{P}_1$ is a common smallest multiple on the left (ppcmg) P₀ and P₁, by the same argument as in the commutative case, closely following the degrees throughout the algorithm. This discussion leads to the previous Algorithm. We have seen that the algorithms of closure by addition between differentially finite functions or between polynomially recurring sequences return a common multiple to the left of the twisted polynomials Lf and Lg describing the two objects f and g to be added. Since these algorithms operate in increasing degrees, the returned polynomial is of minimum degree in $\partial$ , among those that cancel the sum f + g. The cancelling polynomial of the sum f + g returned by these algorithms is therefore the ppcmg of Lf and Lg.

5.3. Example (Solution Finding and Operator Factoring 3)

We use polynomials A and B from example 3.2 to compute a pgcdd and a ppcmg. Let’s ask $P_0=A$ , $P_1=B$ ; we already have $P_2=-n^{-1}\left(n^2+n+1\right)\left({\partial }_n-\left(n+1\right)\right)$ with $P_0=-n^{-1}\left(n^2-1\right)P_1+P_2$ . He comes next:

$P_1=\frac{-n\left(n+1\right)}{n^2+3n+3}{\partial }_n+\frac{n\left(n+1\right)}{n^2+n+1}{P}_2+0$

Thus, the unitary pgcdd is ${\partial }_n-\left(n+1\right)$ .

Notice that it cancels out the common solutions of A and B, namely the multiples of n!. The unit ppcmg is obtained by renormalizing $P_0=-S{P}_1$ when $R=-Q_1$ and $S=Q_1{Q}_0$ :

${\partial }_n^3-\frac{n^3+6n^2+8n+5}{n^2+n+1}{\partial }_n^2+\frac{2n^3+9n^2+13n+7}{n^2+n+1}{\partial }_n-\frac{\left(n^2+3n+3\right)\left(n+1\right)}{n^2+n+1}.$

Note that its solutions are all solutions of A and B: the linear combinations of n!, n, and 1 [18] .

6. Conclusion

The ring structure of twisted polynomials was introduced and studied by Ore in the 1930s, with the explicit intention of dealing with linear functional systems. In this work, twisted polynomials are simply referred to as “non-commutative”. In modern literature, we often speak of “polynomials” or “Ore operators”, and again of “pseudo-linear operators”. Our terminology of “twisted polynomial” is the translation of the English “skew polynomial”, where “skew” means “slanted”, or “oblique”. Some authors have proposed the translation “left-hand polynomial”, where “left” has the meaning of “veiled”, as opposed to “plane”.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Ore, O. (1933) Theory of Non-Commutative Polynomials. Annals of Mathematics, 34, 480-508. https://doi.org/10.2307/1968173
[2]	Hong, H. (2001) Ore Principal Subresultant Coefficients in Solutions. Applicable Algebra in Engineering, Communication and Computing, 11, 227-237. https://doi.org/10.1007/s002000000041
[3]	Ore, O. (1931) Linear Equations in Non-Commutative Fields. Annals of Mathematics, 32, 463-477. https://doi.org/10.2307/1968245
[4]	Bronstein, M. and Petkovšek, M. (1994) On Ore Rings, Linear Operators and Factorisation. Programmir Ovanie, 1, 27-44.
[5]	Bronstein, M. and Petkovšek, M. (1996) An Introduction to Pseudo-Linear Algebra. Theoretical Computer Science, 157, 3-33. https://doi.org/10.1016/0304-3975(95)00173-5
[6]	Cartier, P. (1992) Démonstration “automatique” d’identités et fonctions hypergéométriques. Séminaire Bourbaki, 34, 41-91. http://www.numdam.org/article/SB_1991-1992__34__41_0.pdf
[7]	Grigoriev, D.Yu. (1990) Complexity of Factoring and Calculating the GCD of Linear Ordinary Differential Operators. Journal of Symbolic Computation, 10, 7-37. https://doi.org/10.1016/S0747-7171(08)80034-X
[8]	Put, M. and Singer, M.F. (2003) Galois Theory of Linear Differential Equations. Springer-Verlag, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-55750-7
[9]	Berkovich, L.M. and Tsirulik, V.G. (1986) The Differential Resultant and Some of Its Applications. Differentsial’nye Uravneniya, 22, 750–757.
[10]	Hong, H. (2001) Ore Subresultant Coefficients in Solutions. Applicable Algebra in Engineering, Communication and Computing, 12, 421-428. https://doi.org/10.1007/s002000100082
[11]	Put, M. and Singer, M.F. (1997) Galois Theory of Difference Equations. Springer-Verlag, Berlin.
[12]	Bostan, A., Chyzak, F., Cluzeau, T. and Salvy, B. (2006) Low Complexity Algorithms for Linear Recurrences. ISSAC’06: Proceedings of the 2006 International Symposium on Symbolic and Algebraic Computation, Genoa, July 2006, 31-38. https://doi.org/10.1145/1145768.1145781
[13]	Chardin, M. (1991) Differential Resultants and Subresultants. In: Budach, L., Ed., Fundamentals of Computation Theory, Springer, Berlin, Heidelberg, 180-189. https://doi.org/10.1007/3-540-54458-5_62
[14]	Li, Z.M. (2000) Greatest Common Right Divisors, Least Common Left Multiples, and Subresultants of Ore Polynomials. In: Gao, X.S. and Wang, D.M., Eds., Mathematics Mechanization and Applications, Academic Press, San Diego, CA, 297-324. https://doi.org/10.1016/B978-012734760-8/50013-2
[15]	Bronstein, M. (1992) Linear Ordinary Differential Equations: Breaking through the Order 2 Barrier. ISSAC’92: International Symposium on Symbolic and Algebraic Computation, Berkeley, August 1992, 42-48. https://doi.org/10.1145/143242.143264
[16]	Chyzak, F. and Salvy, B. (1998) Non-Commutative Elimination in Ore Algebras Proves Multivariate Holonomic Identities. Journal of Symbolic Computation, 26, 187-227. https://doi.org/10.1006/jsco.1998.0207
[17]	Singer, M.F. (2007) Introduction to the Galois Theory of Linear Differential Equations. arXiv: 0712.4124. https://arxiv.org/abs/0712.4124
[18]	Takayama, N. (1989) Gröbner Basis and the Problem of Contiguous Relations. Japan Journal of Applied Mathematics, 6, 147-160. https://doi.org/10.1007/BF03167920