Writing a polynomial as a product of t-numbers

edit

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(p, t):
    r"""
    Return the ``t``-factorisation of ``p`` seen as a ``t``-number.
    """
    d = p.degree()
    for mu in Partitions(d):
        nu = Partition([k + 1 for k in mu])
        if prod((t^k - 1)//(t - 1) for k in nu) == p:
            return 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}