MultivariatePowerSeries/HenselFactorize - Maple Help

MultivariatePowerSeries

 HenselFactorize
 Factorize a univariate polynomial over power series

 Calling Sequence HenselFactorize(u) HenselFactorize(u, lcopt)

Parameters

 u - univariate polynomial over power series generated by this package lcopt - (optional) equation of the form returnleadingcoefficient = r, where returnleadingcoefficient is a literal keyword and r is one of the values true, false, and automatic

Description

 • The command HenselFactorize(u) factorizes u over the ring of power series of the coefficients of u and returns the factors as a list. The factors may not be linear, since u is not factored over the field of Puiseux series of the coefficients of u.
 • There are two requirements on u for HenselFactorize to succeed in factorizing u. If either of these requirements is not met, an error is signaled.
 – The leading coefficient pn of u (the power series that is the coefficient of the highest power of the main variable) must be invertible. That is, its constant term (the homogeneous part of pn of degree 0) needs to be nonzero.
 – Furthermore, for each power series p that is a coefficient of u, the constant coefficient of p (that is, the homogeneous part of degree 0) divided by the constant coefficient of pn needs to be an algebraic number. That is, the coefficient needs to be of type algnum, either immediately or after applying convert/RootOf. These coefficients are exactly the coefficients of the polynomial f returned by EvaluateAtOrigin(v) in the algorithm description below.
 • The command HenselFactorize(u) proceeds as follows.
 – For the first step, let pn be the leading coefficient of u (the power series that is the coefficient of the highest power of the main variable). Maple verifies if its analytic expression is known. If it is not known, or known to be different from 1, then we multiply u by the inverse of pn; let us call the result v. Otherwise (if pn is known to be equal to 1), v is defined to be equal to u. See also the discussion of the returnleadingcoefficient option below.
 – In the second step, the polynomial f returned by EvaluateAtOrigin(v) is factored over the algebraic numbers.
 – Finally, each of the factors of f is lifted in turn, by repeated calls to the commands TaylorShift and WeierstrassPreparation.
 • The command HenselFactorize(u) is based on lazy evaluation techniques. To be precise, this command returns as soon as the factors of f are computed and all coefficients (which are power series) of the factors of u are initialized (that is, once their generators are determined).
 • Since it is really v that is factored in the second and third steps of the algorithm below, 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 the same main variable as u in order to match the type of the other factors; of necessity, it is a constant polynomial, because it does not depend on the main variable (it is, after all, a coefficient of the main variable in u).
 – 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 of positive degree in the main variable.
 – By default (or if this behavior is selected explicitly by including the option returnleadingcoefficient = automatic), pn is returned as the first entry of the resulting list of factors only if it is not known to be equal to 1, and omitted otherwise.
 • When using the MultivariatePowerSeries package, do not assign anything to the variables occurring in the power series and univariate polynomials over power series. If you do, you may see invalid results.

Examples

 > $\mathrm{with}\left(\mathrm{MultivariatePowerSeries}\right):$

We define a univariate polynomial over power series, $f$, and determine its Hensel factorization. It factors into linear factors.

 > $f≔\mathrm{UnivariatePolynomialOverPowerSeries}\left(\left(z-1\right)\left(z-2\right)\left(z-3\right)+x\left({z}^{2}+z\right),z\right):$
 > $F≔\mathrm{HenselFactorize}\left(f\right)$
 ${F}{≔}\left[\left[{UnivariatⅇPolynomialOvⅇrPowⅇrSⅇriⅇs:}\left({-1}{+}{\dots }\right){+}\left({1}\right){}{z}\right]{,}\left[{UnivariatⅇPolynomialOvⅇrPowⅇrSⅇriⅇs:}\left({-2}{+}{\dots }\right){+}\left({1}\right){}{z}\right]{,}\left[{UnivariatⅇPolynomialOvⅇrPowⅇrSⅇriⅇs:}\left({-3}{+}{\dots }\right){+}\left({1}\right){}{z}\right]\right]$ (1)

We can see more terms of the factors as follows.

 > $\mathrm{map}\left(\mathrm{print},\mathrm{map}\left(\mathrm{UpdatePrecision},F,5\right)\right):$
 $\left[{UnivariatⅇPolynomialOvⅇrPowⅇrSⅇriⅇs:}\left({-1}{+}{x}{-}{3}{}{{x}}^{{2}}{+}\frac{{27}{}{{x}}^{{3}}}{{2}}{-}\frac{{291}{}{{x}}^{{4}}}{{4}}{+}\frac{{3465}{}{{x}}^{{5}}}{{8}}{+}{\dots }\right){+}\left({1}\right){}{z}\right]$
 $\left[{UnivariatⅇPolynomialOvⅇrPowⅇrSⅇriⅇs:}\left({-2}{-}{6}{}{x}{-}{30}{}{{x}}^{{2}}{-}{402}{}{{x}}^{{3}}{-}{5610}{}{{x}}^{{4}}{-}{93390}{}{{x}}^{{5}}{+}{\dots }\right){+}\left({1}\right){}{z}\right]$
 $\left[{UnivariatⅇPolynomialOvⅇrPowⅇrSⅇriⅇs:}\left({-3}{+}{6}{}{x}{+}{33}{}{{x}}^{{2}}{+}\frac{{777}{}{{x}}^{{3}}}{{2}}{+}\frac{{22731}{}{{x}}^{{4}}}{{4}}{+}\frac{{743655}{}{{x}}^{{5}}}{{8}}{+}{\dots }\right){+}\left({1}\right){}{z}\right]$ (2)

We define a new univariate polynomial over power series, $g$. Its Hensel factorization has a linear and a quadratic factor.

 > $g≔\mathrm{UnivariatePolynomialOverPowerSeries}\left({y}^{2}+{x}^{2}+\left(y+1\right){z}^{2}+{z}^{3},z\right):$
 > $G≔\mathrm{HenselFactorize}\left(g\right)$
 ${G}{≔}\left[\left[{UnivariatⅇPolynomialOvⅇrPowⅇrSⅇriⅇs:}\left({0}{+}{\dots }\right){+}\left({0}{+}{\dots }\right){}{z}{+}\left({1}\right){}{{z}}^{{2}}\right]{,}\left[{UnivariatⅇPolynomialOvⅇrPowⅇrSⅇriⅇs:}\left({1}{+}{\dots }\right){+}\left({1}\right){}{z}\right]\right]$ (3)
 > $\mathrm{map}\left(\mathrm{print},\mathrm{map}\left(\mathrm{UpdatePrecision},G,5\right)\right):$
 $\left[{UnivariatⅇPolynomialOvⅇrPowⅇrSⅇriⅇs:}\left({{x}}^{{2}}{+}{{y}}^{{2}}{-}{{x}}^{{2}}{}{y}{-}{{y}}^{{3}}{-}{{x}}^{{4}}{-}{{x}}^{{2}}{}{{y}}^{{2}}{+}{4}{}{{x}}^{{4}}{}{y}{+}{7}{}{{x}}^{{2}}{}{{y}}^{{3}}{+}{3}{}{{y}}^{{5}}{+}{\dots }\right){+}\left({-}{{x}}^{{2}}{-}{{y}}^{{2}}{+}{2}{}{{x}}^{{2}}{}{y}{+}{2}{}{{y}}^{{3}}{+}{2}{}{{x}}^{{4}}{+}{{x}}^{{2}}{}{{y}}^{{2}}{-}{{y}}^{{4}}{-}{10}{}{{x}}^{{4}}{}{y}{-}{16}{}{{x}}^{{2}}{}{{y}}^{{3}}{-}{6}{}{{y}}^{{5}}{+}{\dots }\right){}{z}{+}\left({1}\right){}{{z}}^{{2}}\right]$
 $\left[{UnivariatⅇPolynomialOvⅇrPowⅇrSⅇriⅇs:}\left({1}{+}{y}{+}{{x}}^{{2}}{+}{{y}}^{{2}}{-}{2}{}{{x}}^{{2}}{}{y}{-}{2}{}{{y}}^{{3}}{-}{2}{}{{x}}^{{4}}{-}{{x}}^{{2}}{}{{y}}^{{2}}{+}{{y}}^{{4}}{+}{10}{}{{x}}^{{4}}{}{y}{+}{16}{}{{x}}^{{2}}{}{{y}}^{{3}}{+}{6}{}{{y}}^{{5}}{+}{\dots }\right){+}\left({1}\right){}{z}\right]$ (4)

The two examples above have leading coefficients that are known to be equal to 1. The case below has a leading coefficient equal to ${ⅇ}^{x}$ (an invertible power series). Its Hensel factorization has a linear and a quadratic factor, and the leading coefficient is also included as a factor.

 > $a≔\mathrm{PowerSeries}\left(d↦\frac{{x}^{d}}{d!},\mathrm{analytic}=\mathrm{exp}\left(x\right)\right)$
 ${a}{≔}\left[{PowⅇrSⅇriⅇs of}{{ⅇ}}^{{x}}{:}{1}{+}{\dots }\right]$ (5)
 > $b≔2\mathrm{SumOfAllMonomials}\left(\left[x,y\right]\right)$
 ${b}{≔}\left[{PowⅇrSⅇriⅇs of}\frac{{2}}{\left({1}{-}{x}\right){}\left({1}{-}{y}\right)}{:}{2}{+}{\dots }\right]$ (6)
 > $c≔\mathrm{PowerSeries}\left(d↦\mathrm{ifelse}\left(d::\mathrm{even},\frac{{\left(-1\right)}^{\frac{d}{2}}\cdot {x}^{d}}{d!},0\right),\mathrm{analytic}=\mathrm{cos}\left(x\right)\right)$
 ${c}{≔}\left[{PowⅇrSⅇriⅇs of}{\mathrm{cos}}{}\left({x}\right){:}{1}{+}{\dots }\right]$ (7)
 > $d≔\mathrm{PowerSeries}\left(d↦\mathrm{ifelse}\left(d::\mathrm{odd},\frac{{\left(-1\right)}^{\frac{d}{2}-\frac{1}{2}}\cdot {x}^{d}}{d!},0\right),\mathrm{analytic}=\mathrm{sin}\left(x\right)\right)$
 ${d}{≔}\left[{PowⅇrSⅇriⅇs of}{\mathrm{sin}}{}\left({x}\right){:}{0}{+}{\dots }\right]$ (8)
 > $h≔\mathrm{UnivariatePolynomialOverPowerSeries}\left(\left[d,c,b,a\right],z\right)$
 ${h}{≔}\left[{UnivariatⅇPolynomialOvⅇrPowⅇrSⅇriⅇs:}\left({0}{+}{\dots }\right){+}\left({1}{+}{\dots }\right){}{z}{+}\left({2}{+}{\dots }\right){}{{z}}^{{2}}{+}\left({1}{+}{\dots }\right){}{{z}}^{{3}}\right]$ (9)
 > $H≔\mathrm{HenselFactorize}\left(h\right)$
 ${H}{≔}\left[\left[{UnivariatⅇPolynomialOvⅇrPowⅇrSⅇriⅇs:}\left({1}{+}{\dots }\right)\right]{,}\left[{UnivariatⅇPolynomialOvⅇrPowⅇrSⅇriⅇs:}\left({0}{+}{\dots }\right){+}\left({1}\right){}{z}\right]{,}\left[{UnivariatⅇPolynomialOvⅇrPowⅇrSⅇriⅇs:}\left({1}{+}{\dots }\right){+}\left({2}{+}{\dots }\right){}{z}{+}\left({1}\right){}{{z}}^{{2}}\right]\right]$ (10)
 > $\mathrm{map}\left(\mathrm{print},\mathrm{map}\left(\mathrm{UpdatePrecision},H,5\right)\right):$
 $\left[{UnivariatⅇPolynomialOvⅇrPowⅇrSⅇriⅇs:}\left({1}{+}{x}{+}\frac{{{x}}^{{2}}}{{2}}{+}\frac{{{x}}^{{3}}}{{6}}{+}\frac{{{x}}^{{4}}}{{24}}{+}\frac{{{x}}^{{5}}}{{120}}{+}{\dots }\right)\right]$
 $\left[{UnivariatⅇPolynomialOvⅇrPowⅇrSⅇriⅇs:}\left({x}{+}{2}{}{{x}}^{{2}}{+}\frac{{28}{}{{x}}^{{3}}}{{3}}{+}{2}{}{{x}}^{{2}}{}{y}{+}\frac{{148}{}{{x}}^{{4}}}{{3}}{+}{18}{}{{x}}^{{3}}{}{y}{+}{2}{}{{x}}^{{2}}{}{{y}}^{{2}}{+}\frac{{4282}{}{{x}}^{{5}}}{{15}}{+}\frac{{439}{}{{x}}^{{4}}{}{y}}{{3}}{+}{26}{}{{x}}^{{3}}{}{{y}}^{{2}}{+}{2}{}{{x}}^{{2}}{}{{y}}^{{3}}{+}{\dots }\right){+}\left({1}\right){}{z}\right]$
 $\left[{UnivariatⅇPolynomialOvⅇrPowⅇrSⅇriⅇs:}\left({1}{-}{3}{}{x}{-}{3}{}{{x}}^{{2}}{-}{2}{}{x}{}{y}{-}\frac{{46}{}{{x}}^{{3}}}{{3}}{-}{2}{}{x}{}{{y}}^{{2}}{-}{8}{}{{x}}^{{2}}{}{y}{-}\frac{{473}{}{{x}}^{{4}}}{{6}}{-}\frac{{155}{}{{x}}^{{3}}{}{y}}{{3}}{-}{2}{}{x}{}{{y}}^{{3}}{-}{12}{}{{x}}^{{2}}{}{{y}}^{{2}}{-}\frac{{26779}{}{{x}}^{{5}}}{{60}}{-}{352}{}{{x}}^{{4}}{}{y}{-}\frac{{311}{}{{x}}^{{3}}{}{{y}}^{{2}}}{{3}}{-}{16}{}{{x}}^{{2}}{}{{y}}^{{3}}{-}{2}{}{x}{}{{y}}^{{4}}{+}{\dots }\right){+}\left({2}{+}{2}{}{y}{-}{x}{-}{{x}}^{{2}}{+}{2}{}{{y}}^{{2}}{-}\frac{{26}{}{{x}}^{{3}}}{{3}}{-}{{x}}^{{2}}{}{y}{+}{2}{}{{y}}^{{3}}{-}\frac{{583}{}{{x}}^{{4}}}{{12}}{-}\frac{{52}{}{{x}}^{{3}}{}{y}}{{3}}{-}{{x}}^{{2}}{}{{y}}^{{2}}{+}{2}{}{{y}}^{{4}}{-}\frac{{4271}{}{{x}}^{{5}}}{{15}}{-}\frac{{1747}{}{{x}}^{{4}}{}{y}}{{12}}{-}\frac{{76}{}{{x}}^{{3}}{}{{y}}^{{2}}}{{3}}{-}{{x}}^{{2}}{}{{y}}^{{3}}{+}{2}{}{{y}}^{{5}}{+}{\dots }\right){}{z}{+}\left({1}\right){}{{z}}^{{2}}\right]$ (11)

The first entry of the factorization is $a$, the leading coefficient of $h$. It is represented as a trivial univariate polynomial over power series.

 > $\mathrm{GetCoefficient}\left(H\left[1\right],0\right)$
 $\left[{PowⅇrSⅇriⅇs of}{{ⅇ}}^{{x}}{:}{1}{+}{x}{+}\frac{{{x}}^{{2}}}{{2}}{+}\frac{{{x}}^{{3}}}{{6}}{+}\frac{{{x}}^{{4}}}{{24}}{+}\frac{{{x}}^{{5}}}{{120}}{+}{\dots }\right]$ (12)

References

 Alexander Brandt, Mahsa Kazemi, Marc Moreno Maza "Power Series Arithmetic with the BPAS Library." Computer Algebra in Scientific Computing (CASC), Lecture Notes in Computer Science - 12291, (2020): 108-128.
 Mohammadali Asadi, Alexander Brandt, Mahsa Kazemi, Marc Moreno Maza, and Erik Postma: " Multivariate Power Series in Maple." Maple Conference 2020, Waterloo, Ontario, Canada, November 2-6, 2020, Communications in Computer and Information Science (CCIS) series - Springer 2020 (submitted).

Compatibility

 • The MultivariatePowerSeries[HenselFactorize] command was introduced in Maple 2021.