Ask Your Question

Revision history [back]

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]

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}