21
$\begingroup$

In answering another MathOverflow question, I stumbled across the sequence of polynomials $Q_n(p)$ defined by the recurrence $$Q_n(p) = 1-\sum_{k=2}^{n-1} \binom{n-2}{k-2}(1-p)^{k(n-k)}Q_k(p).$$ Thus:

$Q_{2}(p) = 1$

$Q_{3}(p) = -p^2 + 2 p$

$Q_{4}(p) = -2 p^5 + 9 p^4 - 14 p^3 + 8 p^2$

$Q_{5}(p) = 6 p^9 - 48 p^8 + 162 p^7 - 298 p^6 + 318 p^5 - 189 p^4 + 50 p^3$

Numerical calculations up to $n=60$ suggest that:

  1. The lowest-degree term of $Q_n(p)$ is $2n^{n-3}p^{n-2}$.
  2. The coefficients of $Q_n(p)$ alternate in sign.

Are these true for all $n$?

As the title indicates, I'm especially puzzled about 2. Indeed, the original inspiration for the polynomials $Q_n(p)$ comes from a classic paper of E. N. Gilbert (Random graphs, Ann. Math. Stat. 30, 1141-1144 (1959); ZBL0168.40801) where the author studies the sequence of polynomials $P_n(p)$ given by the similar recurrence $$P_n(p) = 1 - \sum_{k=1}^{n-1} \binom{n-1}{k-1}(1-p)^{k(n-k)}P_k(p),$$ which do not have alternating coefficients.

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ Don't know how this might help but in fact it seems that $Q_n(1-x)$ is $(1-x)^{n-2}(1+x)$ times a polynomial with positive integer coefficients and constant term 1 (with leading coefficient $(n-2)!$ and of degree $\frac{n(n-3)}2$ starting from $n=4$) $\endgroup$
    – მამუკა ჯიბლაძე
    Commented Oct 8, 2017 at 19:01
  • 1
    $\begingroup$ Experimentally, are the absolute values moreover unimodal? $\endgroup$
    – Wolfgang
    Commented Oct 8, 2017 at 20:23
  • 10
    $\begingroup$ Perhaps the stronger result is true that every zero of $Q_n(x)$ has nonnegative real part. I have only checked up to $n=10$. $\endgroup$
    – Richard Stanley
    Commented Oct 9, 2017 at 0:41
  • 3
    $\begingroup$ R. Stanley's suggestion with the observations below suggest that your polynomial (after a rotation) has all roots in the lower half plane. Such polynomials are called 'stable', and there is a bunch of results on how to prove stability, see e.g. works of P. Bränden and J. Borcea. $\endgroup$
    – Per Alexandersson
    Commented Oct 9, 2017 at 9:58

2 Answers 2

Reset to default
12
$\begingroup$

To illustrate the suggestion of Richard Stanley about positivity of real parts of zeroes, here are the zeroes of $Q_{20}$. The pattern seems to be the same for all of them.

enter image description here

Another empirical observation: seems that $$ \frac{Q_n(1-x)}{(1-x)^{n-2}(1+x)}=1+(n-3)x+\left(\binom{n-2}2+1\right)x^2 +\left(\binom{n-1}3+n-3\right)x^3+\left(\binom n4+\binom{n-2}2+1\right)x^4+...+\left(\binom{n+k-4}k+\binom{n+k-6}{k-2}+\binom{n+k-8}{k-4}+...\right)x^k+O(x^{k+1})$$for $n>k+1$

Improve this answer
$\endgroup$
7
$\begingroup$

To add to the preceding answer: The absolute values of the coefficients appear normal (in particular, unimodal): Which means that the technology developed, in, eg,

Lebowitz, J.L.; Pittel, B.; Ruelle, D.; Speer, E.R., Central limit theorems, Lee-Yang zeros, and graph-counting polynomials, J. Comb. Theory, Ser. A 141, 147-183 (2016). ZBL1334.05065.

May be relevant.

enter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ Supposing the coefficients have such a "close to normal" distribution, there should be a way to approximate the "coefficient curve" itself by some polynomial with only negative real zeros (and appropriate degree), and if this is numerically stable enough, look at how those zeros behave as n grows. BTW, I have no idea whether those zeros are in any way related to "Lee-Yang zeros" (never heard about the latter before). $\endgroup$
    – Wolfgang
    Commented Oct 9, 2017 at 8:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .