Ask Your Question
2

Checking whether a polynomial in unimodal

asked 2021-12-13 20:38:05 +0100

mathstudent gravatar image

updated 2021-12-13 20:39:20 +0100

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

3 Answers

Sort by » oldest newest most voted
1

answered 2021-12-13 21:11:50 +0100

rburing gravatar image

updated 2021-12-13 23:14:16 +0100

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

Comments

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 gravatar imagemathstudent ( 2021-12-13 21:48:53 +0100 )edit

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

rburing gravatar imagerburing ( 2021-12-13 22:34:44 +0100 )edit

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

mathstudent gravatar imagemathstudent ( 2021-12-13 22:40:00 +0100 )edit

Ah sorry, I misunderstood you. Fixed now.

rburing gravatar imagerburing ( 2021-12-13 23:10:50 +0100 )edit

Thank you very much!

mathstudent gravatar imagemathstudent ( 2021-12-13 23:38:07 +0100 )edit
1

answered 2021-12-14 18:20:27 +0100

slelievre gravatar image

updated 2022-08-10 17:25:08 +0100

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)  # coeffs: 1, 1, 1, 4, 1
        True
        sage: is_unimodal(1 + t^2 + 4*t^3 + t^4)  # coeffs: 1, 0, 1, 4, 1
        False
    """
    from more_itertools import triplewise, unique_justseen
    return all((a < b) or (b > c)
               for a, b, c in triplewise(unique_justseen(p)))
edit flag offensive delete link more
0

answered 2021-12-13 23:06:40 +0100

mathstudent gravatar image

updated 2021-12-13 23:07:17 +0100

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

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: 2021-12-13 20:38:05 +0100

Seen: 455 times

Last updated: Aug 10 '22