Celebratio Mathematica

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.

Sup­pose that \begin{equation}\label{polyf} f(u)=\sum_{i=0}^nc_iu^i \end{equation} 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 \begin{equation}\label{SSR} c_i^2 > 4c_{i-1}c_{i+1},\quad 1\leq i\leq n-1; \end{equation} see [◊]. A suf­fi­cient con­di­tion for H if \( n > 5 \) is that the coef­fi­cients of \( f \) sat­is­fy \begin{equation}\label{SHB} c_i c_{i+1}\geq (2.147\dots)c_{i-1}c_{i+2},\quad 1\leq i\leq n-2; \end{equation} 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:

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 \begin{equation}\label{HBext}f(u)=\sum_{i=0}^{j-1}u^ih_i(u^j).\end{equation} 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} \).

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 \begin{equation}\label{fourth}f(u)=-at_0-bt_1u+cu^2+au^3+bu^4.\end{equation} 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 \begin{equation}\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.\end{equation}

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 \).

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.

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 \begin{equation}\label{id1} -2\sum_j\operatorname{Re}(z_j)-\sum_jw_j=3n. \end{equation} 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 \begin{equation}\label{poly} f(x)=\sum_{i=0}^{k-1}x^ig_i(x^k), \end{equation} where \( g_i \) is a poly­no­mi­al of de­gree \( \bigl\lfloor\frac{n-i}k\bigr\rfloor \).

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) \).

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 \begin{equation}\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). \end{equation} 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.

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.

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.

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 \begin{equation}\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}}; \end{equation} 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 \).

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.