ExtendedHenselConstruction - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Online Help

All Products    Maple    MapleSim


MultivariatePowerSeries

  

ExtendedHenselConstruction

  

factorize a univariate polynomial over power series

 

Calling Sequence

Parameters

Description

Examples

References

Compatibility

Calling Sequence

ExtendedHenselConstruction(u)

ExtendedHenselConstruction(u, hb, t, opt1, opt2)

Parameters

u

-

univariate square-free polynomial with power series coefficients generated by this package

hb

-

(optional) non-negative integer

t

-

(optional) variable name

opt1

-

(optional) equation of the form returnleadingcoefficient = optval, where optval is automatic, true, or false

opt2

-

(optional) equation of the form output = optval, where optval is factorization, or changeofvariables

Description

Univariate case

• 

The command ExtendedHenselConstruction(u) factorizes u over the field of univariate Puiseux series and returns the factors as a list of linear polynomials, or issues an error if this is not possible.

• 

Note that u is a univariate polynomial with univariate power series coefficients. Let x be the variable of u and y be the variable of the coefficients of u. The command ExtendedHenselConstruction(u) proceeds as follows.

– 

First, Maple checks whether u is approximately square-free or not. In the latter case, an error is thrown. If the analytic expression of u is known to be of type polynomial, then this expression is used to compute the discriminant of u. Otherwise, we use a bound b to compute an approximation of the discriminant of u up to that bound. In the case where this approximated discriminant is zero, an error is issued. It is possible to increase the bound b used for this computation, for more details, see the discussion below.

– 

Secondly, let pn be the leading coefficient of u (the power series that is the coefficient of the highest power, say n, of x). Maple verifies whether its analytic expression is known. If it is not known, or known to be different from 1 (see explanation bellow), then an appropriate transformation T is applied to make u monic; let us call the resulting polynomial v. Otherwise (if pn is known to be equal to 1), v is defined to be equal to u.

– 

Note that if the analytic expression of u is undefined,then the ApproximatelyZero function is called, with value b, to check if pn is approximately zero or not. If ApproximatelyZero returns true, then an error is returned. It is possible to rerun the ExtendedHenselConstruction(u, b) command with a greater value for b. See also the discussion of the returnleadingcoefficient option below.

– 

Next, the Newton polynomial of v is computed. When the analytic expression of v is non-polynomial, we truncate v up to degree b and try to compute its Newton polynomial. If this process fails, then an error is issued. It is possible to rerun the command with a greater value of b, ExtendedHenselConstruction(u, b).

– 

To follow, the Newton polynomial is made univariate by evaluating  y  at 1, that is letting y=1. Afterwards, the evaluated Newton polynomial is factored; its factors are called the initial factors.  To compute the approximate value of each factor of v a Hensel lifting strategy is applied; this starts by computing the so-called Yun-Moses polynomials.  

– 

Note that if one or more of the lifted factors is not linear, then the factorization process is applied to each of these non-linear factors after applying an appropriate change of variable. See Sasaki's paper. If the returnleadingcoefficient option is present (see below), then the coefficient pn is added to the list containing the output of Extended HenselFactorize.

– 

Finally, if necessary (pn different than 1), the inverse of the transform T is applied to each of the output factors.

Multivariate case

• 

The command ExtendedHenselConstruction(u, t) factorizes u w.r.t. total degree, using the total degree variable t, and returning the factors as a list of linear polynomials, or issues an error if this is not possible.

• 

Note that u is a univariate polynomial with multivariate power series coefficients. Let x be the variable of u and let x_1,...,x_m' be the variables occuring in the coefficients of u. We assume that m is at least 2. Then, the change of variables x_1=t*x_1(0), ..., x_m=t*x_m(0) is applied, where t is the input variable name. Maple now sees the coefficients of u as univariate power series in the variable t and x_1,...,x_m are seen as constants. Thus, the same process as before can now be applied.

• 

For this call, the ExtendedHenselConstruction algorithm returns a list of polynomials in the variables x and t. The variables x_1(0),...,x_m(0) are still considered as constants.

• 

If the option output = changeofvariables is included, then the change of variable t=1, x_1(0)=x_1, ..., x_m(0)=x_m is also returned together with the factorization of u. By default only the factorization of u is returned.

Optional values

• 

If the argument hb is given, its value is used for the bound b. Otherwise, the global default for bound b (10) is used (see also SetHenselBound). The bound b is used in three cases:

– 

when computing an approximated discriminant of a polynomial with non-polynomial analytic expression;

– 

when the ApproximatelyZero algorithm is called;

– 

when the Newton polynomial of u is computed, and at least one of its coefficients has a non-polynomial analytic expression.

• 

Since it is really v that is factored in the second and third steps of the algorithm above, and v and u differ by a factor of pn (the leading coefficient of u), it is necessary to include a factor corresponding to pn in order to obtain factors that multiply together to u. The returnleadingcoefficient option determines whether pn, investigated and potentially used in the first step of the algorithm, is returned with the other factors. In all cases, if pn is returned, it is converted to a univariate polynomial over power series with main variable x in order to match the type of the other factors; out of necessity, it is a constant polynomial, because it does not depend on x (it is, after all, a coefficient of x).

– 

If the option returnleadingcoefficient = true is included, then pn is always returned as the first entry in the resulting list of factors, even if it is equal to 1.

– 

If the option returnleadingcoefficient = false is included, then pn is always omitted from the resulting list of factors, even if it is different from 1. In this case, the resulting list of factors will contain only univariate polynomials over power series with Puiseux series coefficients of positive degree in x.

– 

By default (or if this behavior is requested explicitly by including the option returnleadingcoefficient = automatic), pn is returned as a entry of the resulting list of factors only if it is not known to be equal to 1, and omitted otherwise.

Remark

• 

The functions ExtendedHenselConstruction and PuiseuxFactorize both factorize a univariate polynomial over the field of univariate Puiseux series into linear factors, thus into irreducible factors. The ExtendedHenselConstruction can also factorize a univariate polynomial over multivariate Puiseux series into linear factors. In contrast, the HenselFactorize command only lifts the initial factors of the input polynomial over the ring of power series ℂ⟦y⟧, thus the factors may not be linear and, hence, may not be irreducible over the field of univariate Puiseux series.

• 

When using the MultivariatePowerSeries package, do not assign anything to the variables occurring in the power series, Puiseux series, and univariate polynomials over these series. If you do, you may see invalid results.

Examples

> 

with⁡MultivariatePowerSeries:

We create a univariate polynomial over power series from a list of power series:

> 

f≔UnivariatePolynomialOverPowerSeries⁡x3−x2⁢y2−x⁢y3+y4,x

f≔UnⅈvarⅈatⅇPolynomⅈalOvⅇrPowⅇrSⅇrⅈⅇs: y4+−y3⁢x+−y2⁢x2+1⁢x3

(1)

We compute its extended Hensel construction:

> 

F≔ExtendedHenselConstruction⁡f

F≔UnⅈvarⅈatⅇPolynomⅈalOvⅇrPuⅈsⅇuxSⅇrⅈⅇs: −y43⁢RootOf⁡_Z2−_Z+1+…+1+…⁢x,UnⅈvarⅈatⅇPolynomⅈalOvⅇrPuⅈsⅇuxSⅇrⅈⅇs: y43+…+1+…⁢x,UnⅈvarⅈatⅇPolynomⅈalOvⅇrPuⅈsⅇuxSⅇrⅈⅇs: −y43+y43⁢RootOf⁡_Z2−_Z+1+…+1+…⁢x

(2)

We can see more terms of the factors as follows:

> 

map⁡print,map⁡Truncate,F,5:

y53⁢RootOf⁡_Z2−_Z+13−y533−y23+10⁢y73⁢RootOf⁡_Z2−_Z+181−y43⁢RootOf⁡_Z2−_Z+1+37⁢y83⁢RootOf⁡_Z2−_Z+1243−37⁢y83243+x

y533−y23−10⁢y7381+y43+37⁢y83243+x

−y53⁢RootOf⁡_Z2−_Z+13−y23+10⁢y7381−10⁢y73⁢RootOf⁡_Z2−_Z+181−y43+y43⁢RootOf⁡_Z2−_Z+1−37⁢y83⁢RootOf⁡_Z2−_Z+1243+x

(3)

Let us see that we got the correct output, i.e., that f is equal to the product of the terms in F modulo the following ideal:

> 

G≔seq⁡xl⁢y6+3−l⋅4,l=0..3

G≔y18,x⁢y14,x2⁢y10,x3⁢y6

(4)

Indeed,

> 

g≔mul⁡seq⁡Truncate⁡p,pinF

g≔y53⁢RootOf⁡_Z2−_Z+13−y533−y23+10⁢y73⁢RootOf⁡_Z2−_Z+181−y43⁢RootOf⁡_Z2−_Z+1+37⁢y83⁢RootOf⁡_Z2−_Z+1243−37⁢y83243+x⁢y533−y23−10⁢y7381+y43+37⁢y83243+x⁢−y53⁢RootOf⁡_Z2−_Z+13−y23+10⁢y7381−10⁢y73⁢RootOf⁡_Z2−_Z+181−y43+y43⁢RootOf⁡_Z2−_Z+1−37⁢y83⁢RootOf⁡_Z2−_Z+1243+x

(5)
> 

r≔evala⁡Normal⁡Truncate⁡f−g

r≔−y5⁢50653⁢y3+35937⁢y2+809190⁢x+2447253⁢y14348907

(6)
> 

r≔eval⁡r,y=y3:r≔simplify⁡r,power,symbolic

r≔−5065314348907⁢y24−1331531441⁢y21−3732187⁢y18−3706561⁢x⁢y15

(7)
> 

r≔Groebner:-NormalForm⁡r,G,plex⁡x,y

r≔0

(8)

Notice that we use the command eval to evaluate y=y3. This is just to be able to use the command Groebner:-NormalForm.

We can compare this output with respect to the PuiseuxFactorize command:

> 

F≔PuiseuxFactorize⁡f,returnleadingcoefficient=false

F≔UnⅈvarⅈatⅇPolynomⅈalOvⅇrPuⅈsⅇuxSⅇrⅈⅇs: y4,UnⅈvarⅈatⅇPolynomⅈalOvⅇrPuⅈsⅇuxSⅇrⅈⅇs: 0+…+1y43⁢x,UnⅈvarⅈatⅇPolynomⅈalOvⅇrPuⅈsⅇuxSⅇrⅈⅇs: 0+…+1y43⁢x,UnⅈvarⅈatⅇPolynomⅈalOvⅇrPuⅈsⅇuxSⅇrⅈⅇs: 0+…+1y43⁢x

(9)
> 

map⁡print,map⁡Truncate,F,5:

y4

1+y133+xy43

−12−I⁢RootOf⁡_Z2−3,index=12+I⁢y13⁢RootOf⁡_Z2−3,index=16−y136+xy43

I⁢RootOf⁡_Z2−3,index=12−12−y136−I⁢y13⁢RootOf⁡_Z2−3,index=16+xy43

(10)

As a second example, consider the following polynomial.

> 

f≔UnivariatePolynomialOverPowerSeries⁡x5+x4⁢y−2⁢x3⁢y−2⁢x2⁢y2+x⁢y2−y3+y3,x

f≔UnⅈvarⅈatⅇPolynomⅈalOvⅇrPowⅇrSⅇrⅈⅇs: y3+y2−y3⁢x+−2⁢y2⁢x2+−2⁢y⁢x3+y⁢x4+1⁢x5

(11)

We compute its extended Hensel construction:

> 

F≔ExtendedHenselConstruction⁡f

F≔UnⅈvarⅈatⅇPolynomⅈalOvⅇrPuⅈsⅇuxSⅇrⅈⅇs: 0+…+1+…⁢x,UnⅈvarⅈatⅇPolynomⅈalOvⅇrPuⅈsⅇuxSⅇrⅈⅇs: 0+…+1+…⁢x,UnⅈvarⅈatⅇPolynomⅈalOvⅇrPuⅈsⅇuxSⅇrⅈⅇs: y+y2+3⁢y3+12⁢y4+55⁢y5+…+1+…⁢x,UnⅈvarⅈatⅇPolynomⅈalOvⅇrPuⅈsⅇuxSⅇrⅈⅇs: 0+…+1+…⁢x,UnⅈvarⅈatⅇPolynomⅈalOvⅇrPuⅈsⅇuxSⅇrⅈⅇs: 0+…+1+…⁢x

(12)

We can obtain more terms of each factors:

> 

map⁡print,map⁡Truncate,F,5:

y−y2−y22−105⁢y52128−3⁢y32+x

y+y328+y2−y52128+x

y2+x+y

−y−y2−y22+105⁢y52128−3⁢y32+x

−y−y328+y2+y52128+x

(13)

It is important to observe that in this particular example, the Newton polynomial of f is

> 

p≔x5−2⁢x3⁢y+x⁢y2

p≔x5−2⁢x3⁢y+x⁢y2

(14)

After evaluating in y=1 and factorizing, we get:

> 

PolynomialTools:-Splits⁡eval⁡p,y=1,x2

x+1,2,x,1,x−1,2

(15)

Hence, the initial factorization of f contains only 3 factors (two of then have degree 2). The ExtendedHenselConstruction algorithms takes care of these factors by making a recursive call in each of them.

Next, consider the following polynomial with power series coefficients in the variables y,z.

> 

f≔UnivariatePolynomialOverPowerSeries⁡x3+y−z+z2⁢x2−y+z+y2−z2⁢x+y2−z3,x

f≔UnⅈvarⅈatⅇPolynomⅈalOvⅇrPowⅇrSⅇrⅈⅇs: y2−z3+−y−z−y2+z2⁢x+y−z+z2⁢x2+1⁢x3

(16)

We compute its extended Hensel construction:

> 

F≔ExtendedHenselConstruction⁡f,t

F≔UnⅈvarⅈatⅇPolynomⅈalOvⅇrPuⅈsⅇuxSⅇrⅈⅇs: 0+…+1+…⁢x,UnⅈvarⅈatⅇPolynomⅈalOvⅇrPuⅈsⅇuxSⅇrⅈⅇs: −t⁢z⁡0+y⁡0+…+1+…⁢x,UnⅈvarⅈatⅇPolynomⅈalOvⅇrPuⅈsⅇuxSⅇrⅈⅇs: t⁢z⁡0+y⁡0+…+1+…⁢x

(17)

We can see more terms of the factors as follows:

> 

map⁡print,map⁡Truncate,F,5:

t⁢y⁡02−y⁡0−z⁡0−t2⁢z⁡06−y⁡0−z⁡0⁢z⁡0+y⁡03−3⁢t2⁢y⁡0⁢z⁡05−y⁡0−z⁡0⁢z⁡0+y⁡03−2⁢t2⁢y⁡02⁢z⁡04−y⁡0−z⁡0⁢z⁡0+y⁡03+t2⁢y⁡03⁢z⁡03−y⁡0−z⁡0⁢z⁡0+y⁡03−t2⁢y⁡04⁢z⁡02−y⁡0−z⁡0⁢z⁡0+y⁡03−2⁢t2⁢y⁡05⁢z⁡0−y⁡0−z⁡0⁢z⁡0+y⁡03+t2⁢y⁡06−y⁡0−z⁡0⁢z⁡0+y⁡03+x

−t⁢z⁡0+y⁡0−t⁢z⁡022⁢z⁡0+2⁢y⁡0+2⁢t⁢y⁡022⁢z⁡0+2⁢y⁡0+3⁢t32⁢z⁡048⁢z⁡0+y⁡052+t32⁢y⁡0⁢z⁡03z⁡0+y⁡052−t32⁢y⁡03⁢z⁡0z⁡0+y⁡052+t2⁢z⁡05⁢y⁡0z⁡0+y⁡03⁢2⁢z⁡0+2⁢y⁡0+4⁢t2⁢z⁡04⁢y⁡02z⁡0+y⁡03⁢2⁢z⁡0+2⁢y⁡0+5⁢t2⁢z⁡03⁢y⁡03z⁡0+y⁡03⁢2⁢z⁡0+2⁢y⁡0−2⁢t2⁢y⁡05⁢z⁡02⁢z⁡0+2⁢y⁡0⁢z⁡0+y⁡03+t2⁢y⁡062⁢z⁡0+2⁢y⁡0⁢z⁡0+y⁡03+73⁢t52⁢z⁡08128⁢z⁡0+y⁡0112+17⁢t52⁢y⁡0⁢z⁡078⁢z⁡0+y⁡0112+3⁢t52⁢y⁡02⁢z⁡062⁢z⁡0+y⁡0112−21⁢t52⁢y⁡03⁢z⁡058⁢z⁡0+y⁡0112−5⁢t52⁢y⁡04⁢z⁡042⁢z⁡0+y⁡0112+3⁢t52⁢y⁡05⁢z⁡032⁢z⁡0+y⁡0112−3⁢t52⁢y⁡06⁢z⁡024⁢z⁡0+y⁡0112−2⁢t52⁢y⁡07⁢z⁡0z⁡0+y⁡0112+t52⁢y⁡08z⁡0+y⁡0112+x

t⁢z⁡0+y⁡0−t⁢z⁡022⁢z⁡0+2⁢y⁡0+2⁢t⁢y⁡022⁢z⁡0+2⁢y⁡0−3⁢t32⁢z⁡048⁢z⁡0+y⁡052−t32⁢y⁡0⁢z⁡03z⁡0+y⁡052+t32⁢y⁡03⁢z⁡0z⁡0+y⁡052+t2⁢z⁡05⁢y⁡0z⁡0+y⁡03⁢2⁢z⁡0+2⁢y⁡0+4⁢t2⁢z⁡04⁢y⁡02z⁡0+y⁡03⁢2⁢z⁡0+2⁢y⁡0+5⁢t2⁢z⁡03⁢y⁡03z⁡0+y⁡03⁢2⁢z⁡0+2⁢y⁡0−2⁢t2⁢y⁡05⁢z⁡02⁢z⁡0+2⁢y⁡0⁢z⁡0+y⁡03+t2⁢y⁡062⁢z⁡0+2⁢y⁡0⁢z⁡0+y⁡03−73⁢t52⁢z⁡08128⁢z⁡0+y⁡0112−17⁢t52⁢y⁡0⁢z⁡078⁢z⁡0+y⁡0112−3⁢t52⁢y⁡02⁢z⁡062⁢z⁡0+y⁡0112+21⁢t52⁢y⁡03⁢z⁡058⁢z⁡0+y⁡0112+5⁢t52⁢y⁡04⁢z⁡042⁢z⁡0+y⁡0112−3⁢t52⁢y⁡05⁢z⁡032⁢z⁡0+y⁡0112+3⁢t52⁢y⁡06⁢z⁡024⁢z⁡0+y⁡0112+2⁢t52⁢y⁡07⁢z⁡0z⁡0+y⁡0112−t52⁢y⁡08z⁡0+y⁡0112+x

(18)

Observe that the output are polynomials in the variable x with power series in t coefficients (y⁡0 and (z⁡0 are seemed as constants).

References

  

Parisa Alvandi, Massoud Ataei, Mahsa Kazemi, Marc Moreno Maza. "On the extended Hensel construction and its application to the computation of real limit points." J. of Symbolic Computation, vol. 98, p. 120-162, 2020.

  

Sasaki, T., Kako, F. "Solving multivariate algebraic equation by Hensel construction." Jpn. J. Ind. Appl. Math, vol. 2, p. 257-285, 1999.

  

Mohammadali Asadi, Alexander Brandt, Mahsa Kazemi, Marc Moreno Maza, and Erik Postma. "Multivariate Power Series in Maple." Corless R.M., Gerhard J., Kotsireas I.S. (eds) Maple in Mathematics Education and Research. MC 2020. Communications in Computer and Information Science (CCIS), Vol. 1414 Springer (2021): 48-66.

Compatibility

• 

The MultivariatePowerSeries[ExtendedHenselConstruction] command was introduced in Maple 2023.

• 

For more information on Maple 2023 changes, see Updates in Maple 2023.

See Also

HenselFactorize

Inverse

PuiseuxFactorize

PuiseuxSeries

SetHenselBound

UnivariatePolynomialOverPowerSeries