# Checking whether a polynomial in unimodal

Let $p(t)\in \mathbb{Z}_{\geq 0}[t]$. Write $p(t)=\sum_i a_i t^i$. Then we say $p(t)$ is unimodal if $a_0 \leq a_1 \leq ... \leq a_k \geq a_{k+1} \geq ... \geq a_n$ i.e, the sequence of coefficients increase at first and then decrease, they don't 'jump around' ; there is no phenomenon like increase then decrease then increase again. Given such a polynomial, how can we check unimodality in sage?

edit retag close merge delete

Sort by » oldest newest most voted Here is a way:

def is_unimodal(p):
coeffs = p.coefficients(sparse=False)
max_coeff_idx = max(range(len(coeffs)), key=lambda i: coeffs[i])
return all(coeffs[i] <= coeffs[i+1] for i in range(max_coeff_idx)) and \
all(coeffs[i] >= coeffs[i+1] for i in range(max_coeff_idx, len(coeffs) - 1))


Example usage:

sage: R.<t> = ZZ[]
sage: p = R.random_element(degree=4).map_coefficients(abs); p
t^4 + 4*t^3 + t^2 + t + 1
sage: p.coefficients(sparse=False)
[1, 1, 1, 4, 1]
sage: is_unimodal(p)
True

more

Actually coeffs don't take into account if some coefficient $a_k=0$ in the middle. So this works fine if there is no internal zeros, but if there is some then it gives wrong answer.

@mathstudent That wasn't written in your definition. I've updated the answer. Probably there is a faster way, but I guess speed doesn't matter much here.

No... I meant your earlier program didn't work if there was some internal zeroes

Call C the list of coefficients, removing immediate repeats.

Unimodality means there is no decrease-then-increase in C.

The package more-itertools (which can be installed with pip) enables an elegant solution:

def is_unimodal(p):
"""
Return whether this polynomial is unimodal.

EXAMPLES::

sage: R.<t> = ZZ[]
sage: is_unimodal(1 + t + t^2 + 4*t^3 + t^4)
True
sage: is_unimodal(1 + t^2 + 4*t^3 + t^4)
False
"""
from more_itertools import triplewise, unique_justseen
return all((a < b) or (b > c)
for a, b, c in triplewise(unique_justseen(p)))

more

From @rburing's answer... slightly modified since taking coefficients in the polynomial ring somehow only gives the non-zero coefficients:

t = var('t')
R = ZZ[t]
def is_unimodal(p):
coeffs = [R(p).constant_coefficient()]
for i in range(1,p.degree(t)+1):
coeffs = coeffs + [SR(p).coefficient(t^i)]
max_coeff_idx = max(range(len(coeffs)), key=lambda i: coeffs[i])
return all(coeffs[i] <= coeffs[i+1] for i in range(max_coeff_idx)) and \
all(coeffs[i] >= coeffs[i+1] for i in range(max_coeff_idx, len(coeffs) - 1))

more