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 $\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\&comma;\left[\right]\right]$.

Partial factorizations of the input are not taken into account.

$\mathrm{with}\left(\mathrm{PolynomialTools}\right)\&colon;$

$\mathrm{ShiftlessDecomposition}\left(\mathrm{expand}\left(\mathrm{pochhammer}\left(x\&comma;3\right)\mathrm{pochhammer}\left(x\&comma;5\right)\right)\&comma;x\right)$

$\left[1\&comma;\left[\left[x\&comma;\left[\left[0\&comma;2\right]\&comma;\left[1\&comma;2\right]\&comma;\left[2\&comma;2\right]\&comma;\left[3\&comma;1\right]\&comma;\left[4\&comma;1\right]\right]\right]\right]\right]$

$\mathrm{ShiftlessDecomposition}\left(\left(x^6-1\right)\left(x^{10}-1\right)\left(x^{15}-1\right)\&comma;x\right)$

$\left[1\&comma;\left[\left[x-1\&comma;\left[\left[0\&comma;3\right]\&comma;\left[2\&comma;2\right]\right]\right]\&comma;\left[x^2-x+1\&comma;\left[\left[0\&comma;1\right]\&comma;\left[1\&comma;2\right]\right]\right]\&comma;\left[x^4+x^3+x^2+x+1\&comma;\left[\left[0\&comma;2\right]\right]\right]\&comma;\left[x^{12}-2x^{11}+2x^{10}-x^9+2x^7-3x^6+2x^5-x^3+2x^2-2x+1\&comma;\left[\left[0\&comma;1\right]\right]\right]\right]\right]$

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.