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.

  • 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$ – მამუკა ჯიბლაძე Oct 8 '17 at 19:01
  • 1
    $\begingroup$ Experimentally, are the absolute values moreover unimodal? $\endgroup$ – Wolfgang Oct 8 '17 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 Oct 9 '17 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 Oct 9 '17 at 9:58

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$


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

| cite | improve this answer | |
  • $\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 Oct 9 '17 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.