1 | initial version |
Not sure Sage has such a function built in.
One way would be to try partitions one by one.
Here is a function that does that:
def q_factor(poly, t):
r"""
Return a partition such that ``p`` is the product of
the corresponding ``t``-parts.
"""
d = poly.degree()
for p in Partitions(d):
pp = Partition([k + 1 for k in p])
if prod((t^k - 1)//(t - 1) for k in pp) == poly:
return pp
raise ValueError('could not factor as product of t-numbers')
Usage:
sage: t = polygen(ZZ, 't')
sage: p = (t^2 - t + 1)*(t^2 + t + 1)*(t + 1)^2
sage: q_factor(p, t)
[6, 2]
2 | No.2 Revision |
Not sure Sage has such a function built in.
One way would be to try partitions one by one.
Here is a function that does that:
def q_factor(poly, q_factor(p, t):
r"""
Return the ``t``-factorisation of ``p`` seen as a partition such that ``p`` is the product of
the corresponding ``t``-parts.
``t``-number.
"""
d = poly.degree()
p.degree()
for p mu in Partitions(d):
pp nu = Partition([k + 1 for k in p])
mu])
if prod((t^k - 1)//(t - 1) for k in pp) nu) == poly:
p:
return pp
nu
raise ValueError('could not factor as product of t-numbers')
Usage:
sage: t = polygen(ZZ, 't')
sage: p = (t^2 - t + 1)*(t^2 + t + 1)*(t + 1)^2
sage: q_factor(p, t)
[6, 2]
Smarter: trial-division by t
-numbers
in decreasing order, starting from degree + 1.
def q_factor(p, t):
r"""
Return the ``t``-factorisation of ``p`` seen as a ``t``-number.
"""
from collections import defaultdict
f = defaultdict(int)
d = p.degree() + 1
while d - 1:
dt = (t^d - 1) // (t - 1)
if p % dt:
d -= 1
else:
f[d] += 1
p //= dt
d = min(d, p.degree() + 1)
return dict(f)
Usage:
sage: t = polygen(ZZ, 't')
sage: p = (t^2 - t + 1)*(t^2 + t + 1)*(t + 1)^2
sage: q_factor(p, t)
{6: 1, 2: 1}