PolynomialTools - Maple Programming Help

Home : Support : Online Help : Mathematics : Algebra : Polynomials : PolynomialTools : PolynomialTools/ShiftlessDecomposition

PolynomialTools

 ShiftlessDecomposition
 compute a shiftless decomposition  of a univariate polynomial

 Calling Sequence ShiftlessDecomposition(f,x)

Parameters

 f - polynomial in x x - indeterminate

Description

 • The ShiftlessDecomposition command computes a shiftless decomposition $[c,[[\mathrm{g1},[[\mathrm{h11},\mathrm{e11}],[\mathrm{h12},\mathrm{e12}],...]],[\mathrm{g2},[[\mathrm{h21},\mathrm{e21}],[\mathrm{h22},\mathrm{e22}],...]],...]]$ of f w.r.t. x.
 It satisfies the following properties.
 $f=c{\mathrm{g1}\left(x+\mathrm{h11}\right)}^{\mathrm{e11}}{\mathrm{g1}\left(x+\mathrm{h12}\right)}^{\mathrm{e12}}...{\mathrm{g2}\left(x+\mathrm{h21}\right)}^{\mathrm{e21}}{\mathrm{g2}\left(x+\mathrm{h22}\right)}^{\mathrm{e22}}...$
 $\mathrm{g1},...$ are squarefree and pairwise shift coprime, that is, for $1\le i,j$ and all integers $h$, we have $\mathrm{gcd}\left(\mathrm{gi}\left(x\right),\mathrm{gj}\left(x+h\right)\right)\ne 1$ if and only if $i=j$ and $h=0$
 $c$ is constant w.r.t. x, and $\mathrm{g1},...$ are nonconstant primitive polynomials w.r.t. x.
 The $\mathrm{hij}$ and $\mathrm{eij}$ are non-negative integers with $0=\mathrm{hi1}<\mathrm{hi2}<\mathrm{...}$ and $0<\mathrm{eij}$ for all $i,j$.
 • The shiftless decomposition is unique up to reordering and multiplication by units. The $\mathrm{gi}$ are ordered by ascending degree in x, but the ordering within the same degree is not determined.
 • If f is constant w.r.t. x, then the return value is $\left[f,\left[\right]\right]$.
 • Partial factorizations of the input are not taken into account.

Examples

 > $\mathrm{with}\left(\mathrm{PolynomialTools}\right):$
 > $\mathrm{ShiftlessDecomposition}\left(\mathrm{expand}\left(\mathrm{pochhammer}\left(x,3\right)\mathrm{pochhammer}\left(x,5\right)\right),x\right)$
 $\left[{1}{,}\left[\left[{x}{,}\left[\left[{0}{,}{2}\right]{,}\left[{1}{,}{2}\right]{,}\left[{2}{,}{2}\right]{,}\left[{3}{,}{1}\right]{,}\left[{4}{,}{1}\right]\right]\right]\right]\right]$ (1)
 > $\mathrm{ShiftlessDecomposition}\left(\left({x}^{6}-1\right)\left({x}^{10}-1\right)\left({x}^{15}-1\right),x\right)$
 $\left[{1}{,}\left[\left[{x}{-}{1}{,}\left[\left[{0}{,}{3}\right]{,}\left[{2}{,}{2}\right]\right]\right]{,}\left[{{x}}^{{2}}{-}{x}{+}{1}{,}\left[\left[{0}{,}{1}\right]{,}\left[{1}{,}{2}\right]\right]\right]{,}\left[{{x}}^{{4}}{+}{{x}}^{{3}}{+}{{x}}^{{2}}{+}{x}{+}{1}{,}\left[\left[{0}{,}{2}\right]\right]\right]{,}\left[{{x}}^{{12}}{-}{2}{}{{x}}^{{11}}{+}{2}{}{{x}}^{{10}}{-}{{x}}^{{9}}{+}{2}{}{{x}}^{{7}}{-}{3}{}{{x}}^{{6}}{+}{2}{}{{x}}^{{5}}{-}{{x}}^{{3}}{+}{2}{}{{x}}^{{2}}{-}{2}{}{x}{+}{1}{,}\left[\left[{0}{,}{1}\right]\right]\right]\right]\right]$ (2)

References

 Gerhard, J.; Giesbrecht, M.; Storjohann, A.; and Zima, E.V. "Shiftless decomposition and polynomial-time rational summation." Proceedings International Symposium on Symbolic and Algebraic Computation, pp. 119-126. ed. J.R. Sendra. 2003.