# Writing a polynomial as a product of t-numbers

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 close merge delete

Sort by » oldest newest most voted

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}

more

Thank you, this is very nice.

( 2022-03-01 09:59:14 +0200 )edit

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$.

more

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

( 2022-03-01 12:32:19 +0200 )edit

It implies uniqueness of the required factorization, btw.

( 2022-03-01 17:45:23 +0200 )edit