Checking whether a polynomial in unimodal

polynomials

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

mathstudent
121 ●1 ●4 ●17

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

add a comment

1

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

rburing

10919 ●4 ●80 ●218 https://www.rburing.nl/

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

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 ( 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 ( 2021-12-13 22:34:44 +0100 )edit

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

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

Ah sorry, I misunderstood you. Fixed now.

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

Thank you very much!

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

add a comment

1

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

slelievre
17684 ●22 ●160 ●349 http://carva.org/samue...

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

add a comment

0

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

mathstudent
121 ●1 ●4 ●17

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

add a comment

Checking whether a polynomial in unimodal

3 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

Checking whether a polynomial in unimodal edit

3 Answers

Comments

Your Answer

Question Tools

Stats

Related questions

Checking whether a polynomial in unimodal