Ask Your Question
1

Writing a polynomial as a product of t-numbers

asked 2022-02-28 21:38:21 +0100

mathstudent gravatar image

updated 2022-02-28 23:39:56 +0100

slelievre gravatar image

I have a function which produces a polynomial in $t$ with positive integer coefficients, and I know that these factor as product of $t-$ numbers of the form $[k]_t = 1+t+...+t^{k-1}$ . Is there a way to factor the polynomials in sage which readily give the factorization in terms of the $t-$numbers?

For example, I have a polynomial $(t^2-t+1)(t^2+t+1)(t+1)^2=(t^5+t^4+t^3+t^2+t+1)(t+1)$. I want the program to return $[6]_t[2]_t$.

edit retag flag offensive close merge delete

2 Answers

Sort by » oldest newest most voted
2

answered 2022-03-01 01:19:34 +0100

slelievre gravatar image

updated 2022-03-01 03:49:18 +0100

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}
edit flag offensive delete link more

Comments

Thank you, this is very nice.

mathstudent gravatar imagemathstudent ( 2022-03-01 09:59:14 +0100 )edit
2

answered 2022-03-01 01:59:14 +0100

Max Alekseyev gravatar image

updated 2022-03-01 04:47:29 +0100

Solution via factorization over $\mathbb{C}$:

def factor_in_t(f):
    D = {}
    for r,m in f.roots(ring=CC):
        a = CC(r.argument()/(2*pi)).algdep(1)
        if a[0]==-1:
            D[a[1]] = D.get(a[1],0) + m
    ft = {}
    K = sorted(D.keys())[::-1]
    for k in K:
        if D[k]>0:
            ft[k] = D[k]
            for d in divisors(k):
                if d>1:
                    D[d] -= ft[k]
    return ft

For example, running

R.<t> = ZZ[]
factor_in_t( (t^2 - t + 1)*(t^2 + t + 1)*(t + 1)^2 )

returns a dict {6:1, 2:1}, which is interpreted as $([6]_t)^1\cdot ([2]_t)^1$.

edit flag offensive delete link more

Comments

Nice function! I took inspiration from it, using polynomial division rather than roots.

slelievre gravatar imageslelievre ( 2022-03-01 12:32:19 +0100 )edit

It implies uniqueness of the required factorization, btw.

Max Alekseyev gravatar imageMax Alekseyev ( 2022-03-01 17:45:23 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2022-02-28 21:38:21 +0100

Seen: 222 times

Last updated: Mar 01 '22