# Celebratio Mathematica

## Thomas Milton Liggett

### Approximating multiples of strong Rayleigh random variables

#### by Thomas M. Liggett

Thomas Lig­gett’s last pa­per was un­pub­lished at the time of his death in 2020. The text that fol­lows is an ed­ited draft of that pa­per, pre­pared by Wen­pin Tang, who also provided the an­nota­tions throughout. Note: Strong Rayleigh ran­dom vari­ables are also called Pois­son bi­no­mi­al ran­dom vari­ables. Some res­ults in this pa­per are presen­ted in Sec­tion 4 of the sur­vey art­icle of W. Tang and F. Tang (“The Pois­son bi­no­mi­al dis­tri­bu­tion — old & new” (2019), arX­iv:1908.10024), which provides fur­ther ref­er­ences.

#### 1. Introduction

Sup­pose that $$\label{polyf} f(u)=\sum_{i=0}^nc_iu^i$$ is a poly­no­mi­al with pos­it­ive coef­fi­cients $$c_i > 0$$.1 Then:

1. $$f$$ is said to be strong Rayleigh (SR) if all of its roots are real (and hence neg­at­ive). This is equi­val­ent to say­ing that $$f$$ can be factored in­to poly­no­mi­als of de­gree 1 with pos­it­ive coef­fi­cients.
2. $$f$$ is said to be Hur­witz (H) if all of its roots have neg­at­ive real part. Since $(u-z)(u-\bar z)=u^2-2u\operatorname{Re}(z)+|z|^2,$ this is equi­val­ent to say­ing that $$f$$ can be factored in­to poly­no­mi­als of de­gree at most 2 with pos­it­ive coef­fi­cients.

In this pa­per we con­sider the fol­low­ing ques­tion: When can $$f$$ be factored in­to poly­no­mi­als of de­gree at most $$j$$ with pos­it­ive coef­fi­cients? We will call this prop­erty $$P_j$$.

One mo­tiv­a­tion for this is the fol­low­ing: Ex­cept for the nor­mal­iz­a­tion $$f(1)=1$$, the $$f$$ in \eqref{polyf} is the prob­ab­il­ity gen­er­at­ing func­tion (pgf) $$Eu^X$$ of a ran­dom vari­able $$X$$ with dis­tri­bu­tion $$c_i=P(X=i)$$. If it2 has prop­erty $$P_j$$, then there are in­de­pend­ent ran­dom vari­ables $$X_i$$ with val­ues in $$\{0,1,\dots, j\}$$ so that $$X$$ and $$\sum_iX_i$$ have the same dis­tri­bu­tion. This prop­erty was ex­ploited in [◊] in the case $$j=1$$ in or­der to ob­tain vari­ous prob­ab­il­ist­ic lim­it the­or­ems.

An­oth­er mo­tiv­a­tion comes from [◊]. In our con­sid­er­a­tion of mul­tivari­ate cent­ral lim­it the­or­ems for SR vec­tors, we raised the fol­low­ing ques­tion: if $$X$$ has an SR pgf and $$j,k\geq 1$$, how well can one ap­prox­im­ate $$\frac jk X$$ by an SR ran­dom vari­able? We were able to solve this prob­lem for $$j=1$$, show­ing that $$\bigl\lfloor \frac 1k X\bigr\rfloor$$ is SR. It turns out that $$\bigl\lfloor\frac 2k X\bigr\rfloor$$ is very far from be­ing SR, in the sense that the ima­gin­ary parts of some roots of the pgf are large. Nev­er­the­less, we will see that a com­bin­a­tion of the res­ults in [◊] with the Hermite–Biehler the­or­em (see [◊] for ex­ample) im­plies that $$\bigl\lfloor\frac 2k X\bigr\rfloor$$ is H. We then spec­u­late about pos­sible ex­ten­sions of this to $$j\geq 3$$. For the ap­plic­a­tions we have in mind, this prop­erty is gen­er­ally as use­ful as SR.

A suf­fi­cient con­di­tion for SR is that the coef­fi­cients of $$f$$ sat­is­fy $$\label{SSR} c_i^2 > 4c_{i-1}c_{i+1},\quad 1\leq i\leq n-1;$$ see [◊]. A suf­fi­cient con­di­tion for H if $$n > 5$$ is that the coef­fi­cients of $$f$$ sat­is­fy $$\label{SHB} c_i c_{i+1}\geq (2.147\dots)c_{i-1}c_{i+2},\quad 1\leq i\leq n-2;$$ see [◊].

These suf­fi­cient con­di­tions are quite re­strict­ive. For ex­ample, if $$f(u)=(u+1)^n$$, so that $$c_i=\binom ni$$, then $\frac {c_i^2}{c_{i-1}c_{i+1}}=\frac{i+1}i\frac{n-i+1}{n-i}.$ There­fore $\lim_{i\rightarrow\infty}\lim_{n\rightarrow\infty}\frac {c_i^2}{c_{i-1}c_{i+1}}=1,$ so \eqref{SSR} fails for large $$n$$.

The Hermite–Biehler the­or­em gives an NASC3 for H:

The­or­em 1: (Hermite–Biehler)4 Giv­en a poly­no­mi­al $$f$$ as in \eqref{polyf} with pos­it­ive coef­fi­cients, write $f(u)=\sum_{i=0}^{1}u^ih_i(u^2).$ Then $$f$$ has prop­erty $$P_2$$ if and only if the roots of $$h_0,h_1$$ are neg­at­ive and in­ter­lace, with the largest of these be­ing a root of $$h_0$$.

By ana­logy with this res­ult, we con­sider the fol­low­ing: Giv­en a poly­no­mi­al $$f$$ as in \eqref{polyf} with pos­it­ive coef­fi­cients, write $$\label{HBext}f(u)=\sum_{i=0}^{j-1}u^ih_i(u^j).$$ We will say that $$f$$ has prop­erty $$Q_j$$ if the roots of $$h_0,h_1,\dots, h_{j-1}$$ are neg­at­ive and in­ter­lace, with the largest be­ing a root of $$h_0$$, the second largest be­ing a root of $$h_1$$, etc.

Note that $$Q_1=P_1$$. The Hermite–Biehler the­or­em is the state­ment that $$Q_2=P_2$$. However, $$Q_3\neq P_3$$ as the fol­low­ing ex­ample shows. Let $f(u)=u^5+u^4+u^3+2u^2+\textstyle\frac32 u+\frac13.$ By defin­i­tion \eqref{HBext}, we have \begin{equation*} h_0(u) = u + \textstyle\frac{1}{3}, \quad h_1(u) = u + \frac{3}{2}, \quad h_2(u) = u+2. \end{equation*} The roots of $$f$$ are $$z_1$$, $$\bar z_1$$, $$z_2$$, $$\bar z_2$$, $$w$$, where the (roun­ded) val­ues are $z_1=-.725+.100i,z_2=.435+1.137i, w=-.420.$ Then $(u-w)(u-z_2)(u-\bar z_2)=.623+1.116u-.449u^2+u^3,$ so $$f$$ is not $$P_3$$. However, the roots of $$h_0,h_1,h_2$$ are $$-\frac13$$, $$-\frac32$$, $$-2$$ re­spect­ively, which do in­ter­lace cor­rectly. We are not aware of a use­ful cri­terion for $$P_j$$ for $$j\geq 3$$.

In the fol­low­ing sec­tion, we prove that $$\bigl\lfloor\frac2kX\bigr\rfloor$$ is $$P_2$$5 if $$X$$ is $$P_1$$, and spec­u­late about the likely situ­ation for $$\bigl\lfloor\frac3kX\bigr\rfloor$$. In par­tic­u­lar, we con­jec­ture that $$\bigl\lfloor\frac34X\bigr\rfloor$$ is $$P_3$$. $$\bigl\lfloor\frac35X\bigr\rfloor$$ is not $$P_3$$, but we con­jec­ture that it is nearly so, in that the pgf can be factored in­to poly­no­mi­als of de­gree at most 3 with at most one of the factors hav­ing a neg­at­ive coef­fi­cient. We will call this situ­ation al­most $$P_3$$. More gen­er­ally, it may be the case that $$\bigl\lfloor\frac3kX\bigr\rfloor$$ is $$P_3$$ if $$k\equiv1 \pmod{3}$$ and al­most $$P_3$$ if $$k\equiv2 \pmod{3}$$.

#### 2. Some examples

Sup­pose the roots of $$h_0,h_1,h_2$$ are neg­at­ive and in­ter­lace. Let these roots be de­noted by $t_m < t_{m-1} < \dots < t_0 < 0.$ Then $f(u)=h_0(u^3)+uh_1(u^3)+u^2h_2(u^3),$ where $$h_0$$ has roots $$t_0,t_3,\dots,$$ and $$h_1$$ has roots $$t_1,t_4,\dots,$$ and $$h_2$$ has roots $$t_2,t_5,\dots.$$ The de­gree of $$f$$ is $$m+3$$.

We be­gin with the case $$m=1$$, so $h_0(y)=a(y-t_0),\quad h_1(y)=b(y-t_1),\quad h_2(y)=c,$ with $$a,b,c > 0$$. Then $$\label{fourth}f(u)=-at_0-bt_1u+cu^2+au^3+bu^4.$$ If we write $f(u)=(u+d)(c_3u^3+c_2u^2+c_1u+c_0)$ and solve, we get $c_3=b,\quad c_2=a-bd,\quad c_1=c-ad+bd^2,\quad c_0=-bt_1-dc+ad^2-bd^3,$ where $$f(-d)=0$$. Now we seek the con­di­tion un­der which $$f \in P_3$$. For the coef­fi­cients to be non­neg­at­ive, we need $b \geq0,\quad a-bd\geq0,\quad c-ad+bd^2\geq0,\quad -bt_1-dc+ad^2-bd^3\geq 0.$ Writ­ing $f(-d)=d(bd^3-ad^2+cd+bt_1)-at_0=d^2(bd^2-ad+c)-(-bdt_1+at_0),$ we see that these in­equal­it­ies are equi­val­ent to $a-bd\geq0,\quad -bt_1d+at_0\geq0.$

A ne­ces­sary and suf­fi­cient con­di­tion for the ex­ist­ence of a $$d > 0$$ so that6 $f(-d)=0,\quad\frac{at_0}{bt_1}\leq d\leq \frac ab,$ is that $$f$$ take on op­pos­ite signs (in­clud­ing 0) at two points in the in­ter­val $\bigg(-\frac{at_0}{bt_1},-\frac ab\bigg).$ To find a use­ful suf­fi­cient con­di­tion, write $b^3f\bigg(-\gamma\frac ab\bigg)=a^2bc\gamma^2-ab^3(-\gamma t_1+t_0)-\gamma^3(1-\gamma)a^4.$ If $$\gamma=1$$, this is $a b[ac-b^2(-t_1+t_0)].$ This is $$\geq0$$ if and only if $$-t_1+t_0\leq ac/b^2$$. It is $$\leq 0$$ if $$\gamma t_1\leq t_0$$ and $$bc\leq \gamma(1-\gamma)a^2$$. There­fore, a suf­fi­cient con­di­tion for the ex­ist­ence of the re­quired $$d$$ is that there ex­ist a $$\gamma\in [0,1]$$ so that $$\label{suff4}t_0-t_1\leq\frac{ac}{b^2},\quad \gamma t_1\leq t_0,\quad\text{and}\quad bc\leq\gamma(1-\gamma)a^2.$$

When is $$Q_3$$ sat­is­fied? If $$n=3$$, $$P_3$$ and $$Q_3$$ are both auto­mat­ic. If $$n=4$$, $$Q_3$$ is equi­val­ent to $$c_1c_3\geq c_0c_4$$.7 If $$f$$ is $$P_3$$ but not $$P_2$$, then \eqalign{ f(u)&=(a_0+a_1u)(b_0+b_1u+b_2u^2+b_3u^3), \cr c_1c_3-c_0c_4&=a_1^2b_0b_2+a_0a_1b_1b_2+a_0^2b_1b_3, } so $$f$$ is $$Q_3$$. However, $$P_2$$ does not im­ply $$Q_3$$. For ex­ample, $$f(u)=(1+u^2)^2$$ is $$P_2$$ but not $$Q_3$$, since $$c_1c_3-c_0c_4=-1$$. More gen­er­ally, if $f(u)=(a_0+a_1u+a_2u^2)(b_0+b_1u+b_2u^2),$ then $c_1c_3-c_0c_4=(a_0b_1+a_1b_0)(a_1b_2+a_2b_1)-a_0a_2b_0b_2.$ This is non­neg­at­ive if $$a_0a_2\leq 4a_1^2$$, $$b_0b_2\leq 4b_1^2$$.8

If $$n=5$$, $$Q_3$$ is equi­val­ent to $$c_1c_3\geq c_0c_4$$ and $$c_2c_4\geq c_1c_5$$.9 If $f(u)=(a_0+a_1u+a_2u^2)\bigl(\textstyle\frac{25}2+\frac12 u^2+u^3\bigr),$ then $c_1c_3-c_0c_4=\textstyle\frac{25}2(a_1^2-a_0a_2).$ In this case, $$f$$ is $$P_3$$ but not $$P_2$$, but it may not be $$Q_3$$.

#### 3. The approximations

We be­gin by show­ing that in gen­er­al, $$X$$ be­ing SR does not im­ply that $$\bigl\lfloor\frac{2}3X\bigr\rfloor$$ is SR, and in fact that this is very far from be­ing the case.

The­or­em 2: Sup­pose $$X$$ is $$B\bigl(3n,\frac12\bigr)$$, and $$z_i$$ are the roots of the pgf of $$\bigl\lfloor\frac{2}3X\bigr\rfloor$$. Then $\max [\operatorname{Im}(z_i)]^2\geq\textstyle\frac12 (9n^2-9n-1).$

Proof.  Up to a con­stant mul­tiple, the pgf of $$\bigl\lfloor\frac{2}3X\bigr\rfloor$$ is $f(u)=\sum_{i= 0}^{3n}\binom {3n}iu^{\lfloor 2i/3\rfloor}=\sum_{i\geq 0}\binom{3n+1}{3i+1}u^{2i}+\sum_{i\geq 0}\binom{3n}{3i+2}u^{2i+1},$ which has de­gree $$d=2n$$. Let $$z_1,z_2,\dots$$ be the com­plex roots with pos­it­ive ima­gin­ary part and $$w_1,w_2,\dots$$ be the real roots. Then $f(u)=\prod_j(u^2-2u\operatorname{Re}(z_j)+|z_j|^2)\prod_j(u-w_j).$ Both of these ex­pres­sions have $$u^d$$ coef­fi­cients equal to 1. Identi­fy­ing the coef­fi­cients of $$u^{d-1}$$ gives $$\label{id1} -2\sum_j\operatorname{Re}(z_j)-\sum_jw_j=3n.$$ Identi­fy­ing the coef­fi­cients of $$u^{d-2}$$ gives $4\sum_{i < j}\operatorname{Re}(z_i)\operatorname{Re}(z_j)+\sum_j|z_j|^2 +2\sum_j\operatorname{Re}(z_j)\sum_iw_i+\sum_{i < j}w_iw_j=\binom{3n+1}{3n-2}.$ Com­bin­ing this with \eqref{id1} leads to $\sum_i[\operatorname{Im}(z_i)]^2-\sum_i[\operatorname{Re}(z_i)]^2-{\textstyle\frac12}\sum_iw_i^2 =\textstyle\frac12 n(9n^2-9n-1).$ There­fore, since there are at most $$n$$ pairs of com­plex con­jug­ate roots, $n\max [\operatorname{Im}(z_i)]^2\geq\sum_i[\operatorname{Im}(z_i)]^2\geq \textstyle\frac12 n(9n^2-9n-1). \quad ◻$

Here is the res­ult from [◊] that we used to show that $$\bigl\lfloor \frac 1k X\bigr\rfloor$$ is SR if $$X$$ is SR. For a poly­no­mi­al $$f$$ of de­gree $$n$$, write $$\label{poly} f(x)=\sum_{i=0}^{k-1}x^ig_i(x^k),$$ where $$g_i$$ is a poly­no­mi­al of de­gree $$\bigl\lfloor\frac{n-i}k\bigr\rfloor$$.

The­or­em 3: ([◊],Theorem 4.3)  If $$f$$ is SR with de­gree $$n$$, the cor­res­pond­ing poly­no­mi­als $$g_i$$ are SR as well. Fur­ther­more, their roots are in­ter­laced in the sense that if the col­lec­tion of all $$n-k+1$$ roots $$s_j$$ of the $$g_i$$’s are placed in in­creas­ing or­der, $s_{n-k} < \cdots < s_4 < s_3 < s_2 < s_1 < s_0 < 0,$ then the roots of $$g_i$$ are $$s_i$$, $$s_{i+k}$$, $$s_{i+2k}, \dots.$$

This state­ment is il­lus­trated in the fol­low­ing ar­ray, in the case $$k=3$$: $\begin{pmatrix} &\cdots&s_{6}&s_{5}&s_{4}&s_{3}&s_{2}&s_{1}&s_0&0\\\\ g_0&\cdots&0&+&+&0&-&-&0&+\\ g_1&\cdots&+&+&0&-&-&0&+&+\\ g_2&\cdots&+&0&-&-&0&+&+&+ \end{pmatrix}.$ Note that each row is peri­od­ic of peri­od 6, and each row is ob­tained from the pre­vi­ous row via a shift. The proof in [◊] is by in­duc­tion on the de­gree of $$f$$. The pgf of $$\bigl\lfloor\frac 1k X\bigr\rfloor$$ is $$\sum_ig_i$$, which al­tern­ates signs at the points $$s_{mk}$$. There­fore, it has a root in each of the in­ter­vals $$(s_{(m+1)k},s_{mk})$$, thus show­ing that $$\bigl\lfloor \frac 1k X\bigr\rfloor$$ is SR $$(=P_1)$$.

The­or­em 4: If $$X$$ is $$P_1$$, then $$\bigl\lfloor\frac 2k X\bigr\rfloor$$ is $$P_2$$.

Proof.  It suf­fices to prove the res­ult for $$k$$ odd. If $$k$$ is odd, the pgf of $$\bigl\lfloor \frac 2k X\bigr\rfloor$$ is $$\label{2x/k} \sum_{i=0}^{(k-1)/2}g_i(u^2)+u\sum_{i=(k+1)/2}^{k-1}g_i(u^2).$$ By the Hermite–Biehler the­or­em, all roots of \eqref{2x/k} have neg­at­ive real parts if and only if all the roots of $\sum_{i=0}^{(k-1)/2}g_i(-u^2)\quad\text{and}\quad\sum_{i=(k+1)/2}^{k-1}g_i(-u^2)$ are neg­at­ive and in­ter­lace, with the largest of these be­ing a root of $\sum_{i=0}^{(k-1)/2}g_i(-u^2).$

If $$k=3$$, one can see from the above ar­ray that $g_0(\,\cdot\,)+g_1(\,\cdot\,)\text{ has a root in each of the intervals }\cdots (s_7,s_6),(s_4,s_3),(s_1,s_0)$ and $g_2(\,\cdot\,)\text{ has a root in each of the intervals }\cdots (s_9,s_7),(s_6,s_4),(s_3,s_1),$ since the val­ues of the func­tion at the two en­d­points of each in­ter­val have op­pos­ite signs. There­fore, the neg­at­ive roots in­ter­lace. For lar­ger odd $$k$$, the ar­gu­ment is sim­il­ar. Now $\sum_{i=0}^{(k-1)/2}g_i(\,\cdot\,)\text{ has a root in each of the intervals }\cdots (s_{(k-1)/2+2k},s_{2k}),(s_{(k-1)/2+k},s_k),(s_{(k-1)/2},s_0)$ and $\sum_{i=(k+1)/2}^{k-1}g_i(\,\cdot\,)\text{ has a root in each of the intervals }\cdots (s_{3k-1},s_{(k+1)/2+2k}),(s_{2k-1},s_{(k+1)/2+k}),(s_{k-1},s_{(k+1)/2}).$ It fol­lows that $$\bigl\lfloor \frac 2k X\bigr\rfloor$$ is H $$(=P_2)$$.  ◻

The situ­ation for the case $$\bigl\lfloor \frac 3k X\bigr\rfloor$$, where $$k$$ is not a mul­tiple of 3, is sim­il­ar. Its pgf is $h_0(u)+uh_1(u)+u^2h_2(u),$ where $h_0(u)=\sum_{i=0}^{\lfloor k/3\rfloor}g_i(u),\quad h_1(u)=\sum_{\lceil k/3\rceil}^{\lfloor 2k/3\rfloor}g_i(u),\quad h_2(u)=\sum_{i=\lceil 2k/3\rceil}^{k-1}g_i(u).$ Then \eqalign{ &h_0\text{ has a root in each of the intervals } (s_{\lfloor k/3\rfloor+ik},s_{ik})\text{ for }i\geq 0, \cr &h_1\text{ has a root in each of the intervals } (s_{\lfloor 2k/3\rfloor+ik},s_{\lceil k/3\rceil+ik})\text{ for }i\geq 0, \cr &h_2\text{ has a root in each of the intervals } (s_{k-1+ik},s_{\lceil 2k/3\rceil+ik})\text{ for }i\geq 0. } In a few cases, the in­ter­val is of the form $$(a,a)$$, which is in­ter­preted as the singleton $$\{a\}$$. So, the roots of $$h_0,h_1,h_2$$ are neg­at­ive and in­ter­lace. Un­for­tu­nately, as was poin­ted out earli­er, this prop­erty does not im­ply $$P_3$$.

The case of $$\bigl\lfloor \frac 3k X\bigr\rfloor$$ is more chal­len­ging, since for each root with pos­it­ive real part, one must find a neg­at­ive root that com­pensates for it. It is not simply a mat­ter of prov­ing some prop­erty for each root, as was the case for $$P_1$$ and $$P_2$$. All we can of­fer at this point is spec­u­la­tion based on com­pu­ta­tions of roots in spe­cial cases. If $$f$$ is $$P_3$$ but not $$P_2$$, $$f$$ will have com­plex roots of pos­it­ive real part. For a neg­at­ive real root $$w$$ and a con­jug­ate pair of roots $$z,\bar z$$ with pos­it­ive real part, let $\langle z,w\rangle=(u-w)(u-z)(u-\bar z).$ For this cu­bic poly­no­mi­al to have pos­it­ive coef­fi­cients, it is ne­ces­sary and suf­fi­cient that $z+\bar z\leq -w\leq\frac{z \bar z}{z+\bar z}.$

Here is what seems to be the case. Let $$w_1,w_2,\dots$$ be the real roots of $$f$$ ordered in in­creas­ing or­der of their ab­so­lute val­ues, and $$z_1,z_2,\dots$$ be the roots with pos­it­ive real and ima­gin­ary parts, ordered in in­creas­ing or­der of the real parts. As­sume that $$X$$ is SR and takes val­ues $$0,1,\dots,n$$.

Let $$f$$ be the pgf of $$\bigl\lfloor\frac 34X\bigr\rfloor$$. The de­gree of $$f$$ is $$d=\bigl\lfloor\frac34 n\bigr\rfloor$$. Then $$f$$ ap­pears to be $$P_3$$ in gen­er­al. The num­ber of $$z_i$$’s and the num­ber of $$w_i$$’s are close to $$\frac n4$$. This has been checked in a num­ber of cases, in­clud­ing $$X\sim B(n,p)$$ for $$n=54$$ and 75, and $$p=\frac1{100}$$, $$\frac12$$ and $$\frac{100}{101}$$.10 If $$X\sim B\bigl(n,\frac12\bigr)$$, the pgf of $$\bigl\lfloor\frac 34X\bigr\rfloor$$ is $$P_2$$ for $$n\leq 9$$. If $$10\leq n\leq 30$$, it is $$P_3$$ and can be factored in­to $$\bigl\lfloor\frac n4\bigr\rfloor$$ ir­re­du­cible cu­bics, with an ex­tra lin­ear factor if $$d\equiv 1\mod 3$$ and an ex­tra ir­re­du­cible quad­rat­ic factor if $$d\equiv 2\bmod 3$$. Here ir­re­du­cible means that it can­not be fur­ther factored in­to poly­no­mi­als with pos­it­ive coef­fi­cients. The ap­pro­pri­ate pair­ing of real and com­plex roots is $$w_i$$ with $$z_i$$. This pic­ture con­tin­ues to hold for many $$X$$’s that are sums of in­de­pend­ent Bernoulli ran­dom vari­ables with ran­domly chosen para­met­ers.

Here is some more de­tail when $$X$$ is $$B\bigl(n,\frac12\bigr)$$ and $$f$$ is the pgf of $$\bigl\lfloor\frac 34X\bigr\rfloor$$, omit­ting mul­ti­plic­at­ive con­stants: \eqalign{ &n=2:\quad f(u)=u+3 \text{ is } P_1, \cr &n=3:\quad f(u)=u^2+3u+4 \text{ is } P_2, \cr &n=4:\quad f(u)=u^3+4u^2+6u+5=(u+a)(u^2+bu+c) \text{ is } P_2, \cr &\phantom{n=4:}\quad f(-a)=0,\quad b=4-a,\quad c=\textstyle\frac 5a,\quad f(0)=5,\quad f(-4)=-19, } so $$f(-a)=0$$ for some $$0 < a < 4$$. There­fore $$f$$ is $$P_2$$. It is not $$P_1$$ since the dis­crim­in­ant of the quad­rat­ic factor is $$< 0$$ for $$0 < a < 4$$. The ac­tu­al val­ues are $$a=2.35$$, $$b=1.65$$, $$c=2.12$$. \eqalign{ &n=5:\quad \textstyle f(u)=u^3+\frac53 u^2+\frac 53 u+1=(u+a)(u^2+bu+c) \text{ is } P_2, \cr &\phantom{n=5:}\quad f(-a)=0,\quad c=\textstyle\frac 1a,\quad b=\frac53-a,\quad f(0)=1,\quad f\bigl(-\frac 53\bigr)=-\frac{16}9, } so $$f(-a)=0$$ for some $$0 < a < \frac53$$. Again, $$f$$ is $$P_2$$ but not $$P_1$$. The ac­tu­al val­ues are $$a=1$$, $$b=\frac23$$, $$c=1$$. \eqalign{ &n=6:\quad f(u)=u^4+21u^3+20 u^2+15 u+7=(u+a)(u+b)(u^2+cu+d) \text{ is } P_2, \cr &\phantom{n=6:}\quad f(-a)=f(-b)=0,\quad d=\textstyle\frac 7{ab},\quad c=21-a-b. } Com­put­ing $$f(x+iy)$$ with $$y\neq 0$$ and set­ting it $$=0$$ leads to $f(x)-\textstyle \frac12 f^{\prime\prime}(x)y^2+y^4=0,\quad f^{\prime}(x)-\textstyle\frac16 y^2f^{\prime\prime\prime}(x)=0.$ Solv­ing the second equa­tion for $$y^2$$ and us­ing that in the first equa­tion leads to $f(x) [f^{\prime\prime\prime}(x)]^2-3f^{\prime\prime}(x)f^{\prime}(x)f^{\prime\prime\prime}(x)+36[f^{\prime}(x)]^2=0.$ Ex­pand­ing this yields a poly­no­mi­al in $$x$$, all of whose coef­fi­cients are neg­at­ive, so $$x < 0$$. It fol­lows that $$f$$ is $$P_2$$. The ac­tu­al val­ues are $$a=20.04, b=.66,c=.30,d=.53$$.

The first case that is $$P_3$$ is $$n=10$$. Now \eqalign{ f(u)&=11 + 45 u + 120 u^2 + 462 u^3 + 210 u^4 + 120 u^5 + 55 u^6 + u^7 \cr& =(u+53)(u^3+.24u^2+.10u+.03)(u^3+1.96u^2+3.23u+7.69). } Set­ting $$f(x+iy)=0$$ for $$y\neq 0$$ gives $\sum_{j=0}^3\frac{(-1)^jf^{(2j)}(x)y^{2j}}{(2j)!}=0,\quad \sum_{j=0}^3\frac{(-1)^jf^{(2j+1)}(x)y^{2j}}{(2j+1)!}=0.$

Con­sider small $$n$$ with $$X$$ gen­er­al. Use $$e_j$$ for the ele­ment­ary sym­met­ric func­tions.

For $$n=3$$, $f(u)=u^2e_0+ue_1+(e_2+e_3)$ is $$P_2$$.

For $$n=4$$, $f(u)=u^3e_0+u^2e_1+ue_2+(e_3+e_4)$ is $$P_3$$, but may not be $$P_2$$.

For $$n=5$$, $f(u)=u^3(e_0+e_1)+u^2e_2+ue_3+(e_4+e_5)$ is $$P_3$$, but may not be $$P_2$$.

For $$n=6$$, $f(u)=u^4e_0+u^3(e_1+e_2)+u^2e_3+ue_4+(e_5+e_6).$ Set­ting this equal to $(u+w)(u^3+a u^2+b u+c)$ with $$w\geq 0$$ gives $$f(-w)=0$$ and \eqalign{ w^3a&=w^2e_3-we_4+e_5+e_6=w^3(e_1+e_2-e_0w), \cr w^2b&=we_4-e_5-e_6, \cr wc&=e_5+e_6. } So that $$a,b,c\geq 0$$, we need $\frac{e_5+e_6}{e_4}\leq w\leq\frac{e_1+e_2}{e_0}.$ Com­pute $\displaylines{ e_0^2f\biggl(-\frac{e_1+e_2}{e_0}\biggr)=e_1(e_1e_3-e_0e_4)+e_2(2e_1e_3-e_0e_4)+e_2^2e_3+e_0^2(e_5+e_6)\geq 0, \cr 16e_0^3f\biggl(-\frac{e_1+e_2}{2e_0}\biggr)=-e_1^4-4e_1^2(e_1^2-e_0e_3)-8e_0^2(e_1e_4-2e_0e_5), \cr -2e_1e_2(3e_1e_2-4e_0e_3)-8e_0^2(e_2e_4-2e_0e_6)-4e_2^2(e_1e_2-4e_0e_3)-e_2^4\leq 0. }$ Since $\frac{e_5+e_6}{e_4}\leq\frac{e_1+e_2}{2e_0},$ it fol­lows that $$f$$ has a root $$-w$$ which makes $$a,b,c\geq0$$. The in­equal­it­ies above fol­low from the New­ton in­equal­it­ies $\frac16\frac{e_1}{e_0}\geq\frac 25\frac{e_2}{e_1}\geq\frac34\frac{e_3}{e_2}\geq\frac43\frac{e_4}{e_3}\geq\frac52\frac{e_5}{e_4}\geq\frac61\frac{e_6}{e_5}.$ It fol­lows that $$f$$ is $$P_3$$.

For $$n=7$$, $f(u)=u^5e_0+u^4e_1+u^3(e_2+e_3)+u^2e_4+ue_5+(e_6+e_7).$ Set this equal to $(u^2+au+b)(u^3+cu^2+du+g).$ Solv­ing for the coef­fi­cients gives \eqalign{ c&=e_1-a, \cr d&=a^2-b-ae_1+e_2+e_3, \cr g&=-a^3+2ab+a^2e_1-be_1-a(e_2+e_3)+e_4, } with $b^2-b[3a^2+(e_2+e_3)-2ae_1)]+a^4-a^3e_1+a^2(e_2+e_3)-ae_4+e_5=0$ and $(e_1-2a)b^2+b[a^3-a^2e_1+a(e_2+e_3]-e_4]+(e_6+e_7)=0.$ Com­bin­ing these two equa­tions gives (and noth­ing is lost if $$e_1\neq 2a$$) $b=\frac{2a^5-3e_1a^4+[e_1^2+2(e_2+e_3)]a^3-[e_1(e_2+e_3)+2e_4]a^2+(e_1e_4+2e_5)a-[(e_1e_5-(e_6+e_7)]}{5a^3-6e_1a^2+[2e_1^2+(e_2+e_3)]a-[e_1(e_2+e_3)-e_4]}.$ Us­ing this value of $$b$$ in either of those equa­tions im­plies that $$a$$ must be a root of a de­gree-10 poly­no­mi­al $$H(a)$$. Also, let­ting $D=5a^3-6e_1a^2+[2e_1^2+(e_2+e_3)]a-[e_1(e_2+e_3)-e_4],$ we have \eqalign{ Dd&=3a^5-8e_1a^4+[7e_1^2+4(e_2+e_3)]a^3-[2e_1^3+7e_1(e_2+e_3)-3e_4]a^2 \cr&\quad +[(e_2+e_3)(e_2+e_3+3e_1^2)-2(e_1e_4+e_5)]a \cr&\qquad -[e_1(e_2+e_3)^2-e_4(e_2+e_3)-e_1e_5+(e_6+e_7)] } and \eqalign{ Dg&=-a^6+3e_1a^5-[3e_1^2+2(e_2+e_3)]a^4+[e_1^3+4e_1(e_2+e_3)]a^3 \cr&\quad -[(e_2+e_3)(e_2+e_3+2e_1^2)+(e_1e_4-4e_5)]a^2+[e_1(e_2+e_3)^2+e_1^2e_4-4e_1e_5+2(e_6+e_7)]a \cr&\qquad -[e_1e_4(e_2+e_3)-e_4^2-e_1^2e_5+e_1(e_6+e_7)]. } Us­ing Poly­no­mi­alRe­duce, $H(a)=[a^4-a^3e_1+a^2(e_2+e_3)-ae_4+e_5]Dg-\textstyle\frac 13(e_6+e_7)[13Dd+K(a)],$ where \eqalign{ K(a)&=29e_1a^4-2[20e_1^2+17(e_2+e_3)]a^3+[14e_1^3+61(e_2+e_3)-24e_4]a^2 \cr&\quad -[27e_1^2(e_2+e_3)+10(e_2+e_3)^2-17e_1e_4-20e_5]a \cr&\qquad +10[e_1(e_2+e_3)^2-e_4(e_2+e_3)-e_1e_5+e_6+e_7]. } Now the New­ton in­equal­it­ies are $\frac17\frac{e_1}{e_0}\geq\frac 26\frac{e_2}{e_1}\geq\frac35\frac{e_3}{e_2}\geq\frac44\frac{e_4}{e_3}\geq\frac53\frac{e_5}{e_4}\geq\frac62\frac{e_6}{e_5}\geq\frac71\frac{e_7}{e_6}.$

Un­for­tu­nately, the pgf of $$f$$ $$\bigl\lfloor\frac 35X\bigr\rfloor$$ is not ne­ces­sar­ily $$P_3$$. Take $$X$$ to be $$B\bigl(n,\frac12\bigr)$$. For $$n\leq 16$$, $$f$$ is $$P_2$$, and for $$17\leq n\leq 20$$ is $$P_3$$. For $$n=21$$, $$d=12$$, and there are 4 $$w_i$$’s and 4 $$z_j$$’s. For $$f$$ to be $$P_3$$, there would have to be a pair­ing of the $$w_i$$’s and $$z_j$$’s so that for each such pair, $$\langle z_i,w_j\rangle$$ has pos­it­ive coef­fi­cients. But, no such pair­ing ex­ists, since $$\langle w_1,z_i\rangle$$ has a neg­at­ive quad­rat­ic coef­fi­cient for $$i=1,2,3,4$$, so $$f$$ is not $$P_3$$. However, $$\langle z_i,w_i\rangle$$ and $$\langle z_{i-1},w_i\rangle$$ have pos­it­ive coef­fi­cients for $$i=2,3,4$$, so one can choose a fac­tor­iz­a­tion of $$f$$ so that only one factor has a neg­at­ive coef­fi­cient. Note that it is not $$P_4$$ either. It is $$P_6$$, since $(u-w_1)(u-w_2)(u-z_1)(u-\bar z_1)(u-z_2)(u-\bar z_2)$ has pos­it­ive coef­fi­cients. This may or may not be use­ful.

However, all is not lost, due to the fol­low­ing res­ult.

Pro­pos­i­tion 5: Sup­pose $$U$$ and $$V$$ are non­neg­at­ive in­teger-val­ued ran­dom vari­ables with $$P(U=m)=p_m$$ and $$P(V=m)=q_m$$ whose pgf’s sat­is­fy $Eu^U=Eu^V(au^3+bu^2+cu+d).$ If $$b+c+d\geq 0$$, $$c+d\geq 0$$, $$d\geq 0$$, then $$U,V$$ can be coupled so that $$U\leq V+3$$ and then $E(V+3-U)=b+2c+3d.$

Proof.  The dis­tri­bu­tions of $$U,V$$ sat­is­fy $p_m=aq_{m-3}+bq_{m-2}+cq_{m-1}+dq_m.$ Since $$a+b+c+d=1$$, sum­ming gives $P(U\leq m)=P(V\leq m-3)+(b+c+d)q_{m-2}+(c+d)q_{m-1}+dq_m.$ There­fore, if $$b+c+d\geq 0$$, $$c+d\geq 0$$, $$d\geq 0$$, $$U$$ and $$V$$ can be coupled so that $$U\leq V+3$$ al­most surely.11 Com­put­ing the first mo­ment, we see that \eqalign{ EU&=\sum_m m[aq_{m-3}+bq_{m-2}+cq_{m-1}+dq_m] \cr& =a(EV+3)+b(EV+2)+c(EV+1)+dEV=EV+(3a+2b+c), } so us­ing again $$a+b+c+d=1$$, we con­clude that $E(V+3-U)=b+2c+3d. \quad ◻$

For the above ex­ample, $$X\sim B\bigl(21,\frac12\bigr)$$, we in­dic­ate the situ­ation be­low, with the $$(i,j)$$ entry cor­res­pond­ing to $$\langle z_i,w_j\rangle$$. If the entry is $$+$$, all coef­fi­cients of $$\langle z_i,w_j\rangle$$ are pos­it­ive. Oth­er­wise, the entry in­dic­ates which coef­fi­cient is neg­at­ive, and gives the value of $$b+2c+3d$$: $\begin{pmatrix} b;.036&+&c;.48&c; .92\\ b;.61\phantom{0}&+&+&c;1.5\\ b;1.80&b;1.99&+&+\\ b;2.01&b;2.20&+&+ \end{pmatrix}.$ Writ­ing $f=\prod_{i=1}^4\langle z_i,w_i\rangle,$ we see that there is a coup­ling of $$\bigl\lfloor\frac35X\bigr\rfloor$$ with $$V$$, a sum of three in­de­pend­ent ran­dom val­ues with val­ues $$0,1,2,3$$, so that $$\bigl\lfloor\frac35X\bigr\rfloor\leq V+3$$ and $\textstyle E\bigl(V+3-\bigl\lfloor\frac35X\bigr\rfloor\bigr)=.035\dots.$

Let $$f$$ be the pgf of $$\bigl\lfloor\frac 35X\bigr\rfloor$$ where $$X$$ is a gen­er­al SR ran­dom vari­able tak­ing val­ues $$0,1,\dots,n$$. The de­gree of $$f$$ is $$d=\bigl\lfloor\frac35 n\bigr\rfloor$$. Then the fol­low­ing ap­pears to be the case. There is a (not in gen­er­al unique) in­dex $$m$$ so that $$\langle z_i,w_{i+1}\rangle$$ has pos­it­ive coef­fi­cients if $$i < m$$ and $$\langle z_i,w_{i}\rangle$$ has pos­it­ive coef­fi­cients if $$i > m$$. Then the pro­pos­i­tion can be ap­plied to the case $$\langle z_m,w_1\rangle$$. In many cases, this par­ti­tion of the $$z_i$$’s is not ne­ces­sary, and $$f$$ is ac­tu­ally $$P_3$$. This ap­pears to be the case, for ex­ample, if $$X$$ is $$B(21,p)$$ for $$p$$ close to 0 or 1. In one of these cases, $$\langle z_i,w_{i+1}\rangle$$ has pos­it­ive coef­fi­cients for all $$i$$, and in the oth­er $$\langle z_i,w_{i}\rangle$$ has pos­it­ive coef­fi­cients for all $$i$$.

For $$21\leq n\leq 26$$, one can choose all but one factor to have pos­it­ive coef­fi­cients, and the (nor­mal­ized) cu­bics cor­res­pond­ing to $$w_1$$ are \eqalign{ n&=21:\quad .015+.984u-.002u^2+.003u^3, \cr n&=22:\quad .013+.990u-.011u^2+.007u^3, \cr n&=23:\quad .012+.997u-.024u^2+.015u^3, \cr n&=24:\quad .011+1.003u-.040u^2+.026u^3, \cr n&=25:\quad .011+1.007u-.059u^2+.042u^3, \cr n&=26:\quad .010+1.008u-.0819u^2+.063u^3. }

Here is a lar­ger ex­ample, with $$X$$ $$B\bigl(33,\frac12\bigr)$$, $$d=19$$. Now there are 7 $$w_i$$’s and 6 $$z_i$$’s: $\begin{pmatrix} - & + & - & - & - & - & -\\ - & b & + & c & - & - & -\\ b & b & + & + & c & c & c\\ b & b & b & + & + & c & c\\ b & b & b & b & + & c & c\\ b & b & b & b & b & + & c \end{pmatrix}.$ Now, $$+$$ means that all four coef­fi­cients are pos­it­ive, $$b$$ or $$c$$ means that the coef­fi­cient is neg­at­ive, but the hy­po­theses of the pro­pos­i­tion are sat­is­fied, and $$-$$ means that the hy­po­theses of the pro­pos­i­tion are not sat­is­fied at all. In the con­text of the last para­graph, the pos­sible val­ues of $$m$$ are 2, 3, 4, 5.

From the ex­amples we have looked at, it ap­pears that the pgf of $$\bigl\lfloor\frac 3kX\bigr\rfloor$$ “usu­ally” sat­is­fies $$P_3$$, and when it does not, it can be factored in­to cu­bics that have pos­it­ive coef­fi­cients ex­cept for one. That one can be treated us­ing the pro­pos­i­tion. Typ­ic­ally, the way this arises is that $$\langle z_i,w_i\rangle$$ has pos­it­ive coef­fi­cients for one range of $$i$$’s, and $$\langle z_i,w_{i+1}\rangle$$ has pos­it­ive coef­fi­cients for a com­ple­ment­ary range of $$i$$’s. The ex­cep­tion­al factor ap­pears in a trans­ition from one range to the oth­er.

Write $$z_i\sim w_j$$ to mean that $$\langle z_i,w_j\rangle$$ has pos­it­ive coef­fi­cients. Take $$X$$ to be $$B\bigl(n,\frac12\bigr)$$.

If $$n=33$$, $$d=19$$, and $$\bigl\lfloor\frac 35X\bigr\rfloor$$ sat­is­fies \eqalign{ z_i&\sim w_{i+1}&\quad&\text{for }1\leq i\leq 4, \cr z_i&\sim w_{i}&\quad&\text{for }3\leq i\leq 6. } If $$n=51$$, $$d=30$$, and $$\bigl\lfloor\frac 35X\bigr\rfloor$$ sat­is­fies \eqalign{ z_i&\sim w_{i+1}&\quad&\text{for }1\leq i\leq 6, \cr z_i&\sim w_{i}&\quad&\text{for }4\leq i\leq 10. } In neither case is $$P_3$$ sat­is­fied.

If $$n=105$$, $$d=45$$, and $$\bigl\lfloor\frac 37X\bigr\rfloor$$ sat­is­fies \eqalign{ z_i&\sim w_{i+1}&\quad&\text{for }i=14, \cr z_i&\sim w_{i}&\quad&\text{for }1\leq i\leq 14, \cr z_i&\sim w_{i-1}&\quad&\text{for }i=14,15, } so $$P_3$$ is sat­is­fied. We do not have a counter­example to $$P_3$$ for $$\bigl\lfloor\frac 37X\bigr\rfloor$$.

If $$n=105$$, $$d=39$$, and $$\bigl\lfloor\frac 38X\bigr\rfloor$$ sat­is­fies \eqalign{ z_i&\sim w_{i+1}&\quad&\text{for }1\leq i\leq 9, \cr z_i&\sim w_{i}&\quad&\text{for }5\leq i\leq 13, \cr z_i&\sim w_{i-1}&\quad&\text{for }i=13, } so $$P_3$$ is not sat­is­fied.

#### 4. The sufficient conditions

Mo­tiv­ated by the suf­fi­cient con­di­tions \eqref{SSR} and \eqref{SHB}, we con­sider poly­no­mi­als $f(u)=\sum_{i=0}^nc_iu^i$ sat­is­fy­ing12 $c_i^2=ac_{i-1}c_{i+1},\quad c_0=c_n.$ Then for $$n=2$$ $f\text{ is } \begin{cases} P_1&\text{if }a\geq 4,\\ P_2&\text{if }a < 4. \end{cases}$ If $$n=3$$, $f(z)=c_0(1+az+az^2+z^3)=c_0(z+1)(z^2+(a-1)z+1),$ so $f\text{ is } \begin{cases} P_1&\text{if }a\geq 3,\\ P_2&\text{if }1\leq a < 3,\\ P_3&\text{if }a < 1. \end{cases}$ At the trans­ition cases, ex­cept for the factor of $$c_0$$, $f(z)= \begin{cases} (z+1)^3&\text{if }a=3,\\ (z+1)(z^2+1)&\text{if }a=1,\\ (z^3+1)&\text{if }a=0. \end{cases}$

If $$n=4$$, $f(z)=c_0(1+b^3z+b^4z^2+b^3z^3+z^4),$ where $$a=b^2$$, so $f\text{ is } \begin{cases} P_1&\text{if }a > 3.236,\\ P_2&\text{if }\sqrt 2 < a < 3.236,\\ P_4&\text{if }a < \sqrt 2. \end{cases}$ If $$a=3.236$$, $$f(z)$$ has double roots at $$-2.513$$ and $$-.398$$. If $$a=\sqrt 2$$, $f(z)=c_0(1+z^2)(1+2^{3/4}z+z^2).$

If $$n=5$$, \eqalign{ f(z)&=c_0(1+a^2z+a^3z^2+a^3z^3+a^2z^4+z^5) \cr& =c_0(z+1)[z^4+(a^2-1)z^3+(a^3-a^2+1)z^2+(a^2-1)z+1], } so $f\text{ is } \begin{cases} P_1&\text{if }a > 3.234,\\ P_2&\text{if }1.465 < a < 3.234,\\ P_3&\text{if }1\leq a < 1.465,\\ P_4&\text{if } a < 1. \end{cases}$

If $$a=1$$, $(z)=c_0(1+z^3)(1+z+z^2).$

If $$n=6$$, $f(z)=c_0(1+b^5z+b^8z^2+b^9z^3+b^8z^4+b^5z^5+z^6),$ where $$a=b^2$$, so for vari­ous val­ues of $$a$$ $0 < P_6 < 1.019 < P_4 < 1.091 < P_2 < 1.341 < P_1.$ This sug­gests the fol­low­ing gen­er­al con­jec­ture.

Con­jec­ture 6: If $$c_i^2\geq\sqrt 2 c_{i-1} c_{i+1}$$ (or $$c_{i-1}c_{i+1}\geq ac_{i-2}c_{i+2}$$ for some $$a$$), then $$f$$ is $$P_3$$.

Giv­en the poly­no­mi­al $f(u)=\sum_{i=0}^nc_iu^i$ and a $$b > 0$$, define a poly­no­mi­al $g(u)=\sum_{i=0}^nc_iu^{\lfloor bi\rfloor}=\sum_{j=0}^{\lfloor bn\rfloor}d_ju^j,\quad d_j=\sum_{i:j\leq bi < j+1}c_i.$

If $$f$$ is the pgf of $$X$$, then $$g$$ is the pgf of $$\lfloor bX\rfloor$$. Then $d_j^2-ad_{j-1}d_{j+1}=\sum_m\biggl[\sum_{\substack{ j\leq bi < j+1\\bm-j-1 < bi\leq bm-j}}c_ic_{m-i}-a\sum_{\substack{ j-1\leq bi < j\\bm-j-2 < bi\leq bm-j-1}}c_ic_{m-i}\biggr].$ We will say that the coef­fi­cients $$c_i$$ sat­is­fy the New­ton in­equal­it­ies if $$\label{Newton} \frac{c_i^2}{\binom ni^2}\geq \frac{c_{i-1}}{\binom n{i-1}}\frac{c_{i+1}}{\binom n{i+1}};$$ see [◊], for ex­ample.

If $$b=\frac1k$$, $d_j^2-ad_{j-1}d_{j+1}=\sum_{i=0}^{k-1}\sum_{l=0}^{k-1}[c_{kj+i}c_{kj+l}-ac_{kj+i-k}c_{kj+l+k}].$ As poin­ted out earli­er, even if $$k=1$$ and $$c_i=\binom ni$$, \eqref{SSR} fails for large $$n$$.

#### Acknowledgment

The ed­it­or thanks Subhro Ghosh for re­view­ing the pa­per, and for his vari­ous sug­ges­tions which im­proved the present­a­tion of the pa­per.