2000 Mathematics Subject Classification. Primary 05A20, 15A04; Secondary 05A15, 15A48.Partially supported by NSF of China 10471016 . Partially supported by NSC 93-2115-M-001-002 .
<ph f="cmbx">Log-concavity and LC-positivity</ph>

### Yeong-Nan Yeh

Department of Applied Mathematics, Dalian University of Technology, Dalian 116024, China Current address : Institute of Mathematics, Academia Sinica, Taipei 11529, Taiwan E-mail address : wangyi@dlut.edu.cn Institute of Mathematics, Academia Sinica, Taipei 11529, Taiwan E-mail address : mayeh@math.sinica.edu.tw
• Abstract. A triangle $\left\{a\left(n,k\right){\right\}}_{0\le k\le n}$  of nonnegative numbers is LC-positive if for each $r$  , the sequence of polynomials ${\sum }_{k=r}^{n}a\left(n,k\right){q}^{k}$  is $q$  -log-concave. It is double LC-positive if both triangles $\left\{a\left(n,k\right)\right\}$  and $\left\{a\left(n,n-k\right)\right\}$  are LC-positive. We show that if $\left\{a\left(n,k\right)\right\}$  is LC-positive, then the log-concavity of the sequence $\left\{{x}_{k}\right\}$  implies that of the sequence $\left\{{z}_{n}\right\}$  defined by ${z}_{n}={\sum }_{k=0}^{n}a\left(n,k\right){x}_{k}$  ; and if $\left\{a\left(n,k\right)\right\}$  is double LC-positive, then the log-concavity of sequences $\left\{{x}_{k}\right\}$  and $\left\{{y}_{k}\right\}$  implies that of the sequence $\left\{{z}_{n}\right\}$  defined by ${z}_{n}={\sum }_{k=0}^{n}a\left(n,k\right){x}_{k}{y}_{n-k}$  . Examples of double LC-positive triangles include the constant triangle and the Pascal triangle. We also give a generalization of a result of Liggett that is used to prove a conjecture of Pemantle on characteristics of negative dependence.

1 Introduction

Let ${x}_{0},{x}_{1},{x}_{2},\dots$  be a sequence of nonnegative numbers and with no internal zeros. By the latter we mean that there are no three indices $i  such that ${x}_{i},{x}_{k}\ne 0$  and ${x}_{j}=0$  . We say that the sequence is log-concave (LC) if ${x}_{i-1}{x}_{i+1}\le {x}_{i}^{2}$  for all $i>0$  . It is well known that the sequence $\left\{{x}_{k}\right\}$  is log-concave if and only if ${x}_{i-1}{x}_{j+1}\le {x}_{i}{x}_{j}$  for all $j\ge i\ge 1$  (see [1,Proposition2.5.1for instance), or equivalently, all minors of order $2$  of the infinite Toeplitz matrix $M=\left({x}_{i-j}{\right)}_{i,j\ge 0}$  are nonnegative (where ${x}_{k}=0$  if $k<0$  ). For this reason a log-concave sequence with no internal zeros is also called PF ${}_{2}$  (the notation actually has a precisely motivation, see [1, 7). Log-concave sequences arise often in combinatorics, algebra, geometry, analysis, probability and statistics. There have been many attempts to develop techniques for the log-concavity problems. We refer the reader to Stanley's survey article [16and Brenti's supplement [2for details.
Let $\left\{a\left(n,k\right){\right\}}_{0\le k\le n}$  be a triangular array of nonnegative numbers. Define two linear transformations of sequences by
 $\begin{array}{ccc}{z}_{n}={\sum }_{k=0}^{n}a\left(n,k\right){x}_{k},n=0,1,2,\dots & & \end{array}$ (1.1)
and
 $\begin{array}{ccc}{z}_{n}={\sum }_{k=0}^{n}a\left(n,k\right){x}_{k}{y}_{n-k},n=0,1,2,\dots & & \end{array}$ (1.2)
respectively. We say that the linear transformation ( 1.1 ) has the PLC property if it preserves the log-concavity of sequences, i.e., the log-concavity of $\left\{{x}_{n}\right\}$  implies that of $\left\{{z}_{n}\right\}$  . We say that the linear transformation ( 1.2 ) has the double PLC property if the log-concavity of $\left\{{x}_{n}\right\}$  and $\left\{{y}_{n}\right\}$  implies that of $\left\{{z}_{n}\right\}$  . The corresponding triangle $\left\{a\left(n,k\right)\right\}$  is also called PLC and double PLC respectively. Clearly, the double PLC property implies the PLC property.
It is well known that the ordinary convolution
 $\begin{array}{ccc}{z}_{n}={\sum }_{k=0}^{n}{x}_{k}{y}_{n-k},n=0,1,2,\dots & & \end{array}$
is double PLC, which can be obtained as a consequence of the fact that the product of $T{P}_{2}$  matrices is $T{P}_{2}$  (see Karlin [7,p.394for instance). Using the same fact, Walkup can manage to prove that the binomial convolution
 $\begin{array}{ccc}{z}_{n}={\sum }_{k=0}^{n}\left(\genfrac{}{}{0}{}{n}{k}\right){x}_{k}{y}_{n-k},n=0,1,2,\dots & & \end{array}$
is double PLC ([17,Theorem1). A more general result is due to Liggett (see [10,Theorem3or §3 of the present paper). However, there is no systematic study of linear transformations that are double PLC. The possible reason for this is that very few examples of such linear transformations are known. In the present paper we develop techniques to deal with the problems of finding these kind of linear transformations and apply these techniques to generate new log-concave sequences from existing ones.
When the triangle $\left\{a\left(n,k\right)\right\}$  is PLC, the linear transformation ( 1.1 ) has to send any log-concave sequence $\left\{{x}_{k}\right\}$  to a log-concave sequence $\left\{{z}_{n}\right\}$  . So, by taking the special log-concave sequence $\left\{{x}_{k}\right\}$  , we may obtain certain necessary conditions such that $\left\{a\left(n,k\right)\right\}$  is PLC from the log-concavity of the associated sequence $\left\{{z}_{n}\right\}$  .
Example 1.1. Let the triangle $\left\{a\left(n,k\right)\right\}$  be PLC. Then for $r\in \mathbb{N}$  and $p>0$  ,
• (i) the column sequence $\left\{a\left(n,r\right){\right\}}_{n\ge r}$  is log-concave;
• (ii) the row-sum sequence $a\left(n\right)={\sum }_{k=0}^{n}a\left(n,k\right)$  is log-concave; and
• (iii) the sequence ${\mathfrak{A}}_{r}\left(n;p\right)={\sum }_{k=r}^{n}a\left(n,k\right){p}^{k}$  is log-concave for $n\ge r$  .
We can view ${\mathfrak{A}}_{r}\left(n;p\right)$  as a polynomial in $p$  . By (iii), the polynomial ${\mathfrak{A}}_{r}^{2}\left(n;p\right)-{\mathfrak{A}}_{r}\left(n-1;p\right){\mathfrak{A}}_{r}\left(n+1;p\right)$  takes nonnegative values when $p>0$  , and so that its leading coefficient ${a}^{2}\left(n,n\right)-a\left(n-1,n-1\right)a\left(n+1,n+1\right)$  has to be nonnegative. In other words, the diagonal sequence $\left\{a\left(n,n\right){\right\}}_{n\ge 0}$  is log-concave.
In order to state our sufficient conditions for $\left\{a\left(n,k\right)\right\}$  to be PLC, we introduce some terminology and notation. Let $q$  be an indeterminate and $\left\{{f}_{n}\left(q\right){\right\}}_{n\ge 0}$  a sequence of polynomials in $q$  . We say that the sequence $\left\{{f}_{n}\left(q\right){\right\}}_{n\ge 0}$  is $q$  -log-concave if for each $n\ge 1$  , ${f}_{n}^{2}\left(q\right)-{f}_{n-1}\left(q\right){f}_{n+1}\left(q\right)$  has nonnegative coefficients as a polynomial in $q$  . The concept of $q$  -log-concavity was first suggested by Stanley (see [15,p.795). We refer the reader to [3, 6, 9, 14, 15for further information about $q$  -log-concavity. Now for $0\le r\le n$  , define the polynomial
 $\begin{array}{ccc}{\mathfrak{A}}_{r}\left(n;q\right)={\sum }_{k=r}^{n}a\left(n,k\right){q}^{k}.& & \end{array}$
We say that the triangle $\left\{a\left(n,k\right)\right\}$  has the LC-positive property if for each $r\ge 0$  , the sequence of polynomials $\left\{{\mathfrak{A}}_{r}\left(n;q\right){\right\}}_{n\ge r}$  is $q$  -log-concave in $n$  . Define the reciprocal triangle $\left\{{a}^{*}\left(n,k\right)\right\}$  of $\left\{a\left(n.k\right)\right\}$  by ${a}^{*}\left(n,k\right)=a\left(n,n-k\right),0\le k\le n.$  We say that the triangle $\left\{a\left(n,k\right)\right\}$  has the double LC-positive property if both $\left\{a\left(n,k\right)\right\}$  and $\left\{{a}^{*}\left(n,k\right)\right\}$  have the LC-positive property.
Example 1.2. Consider $a\left(n,k\right)\equiv 1$  for $0\le k\le n$  . Then ${\mathfrak{A}}_{r}\left(n;q\right)={\sum }_{k=r}^{n}{q}^{k}$  for $0\le r\le n$  . It immediately follows that ${\mathfrak{A}}_{r}^{2}\left(n;q\right)-{\mathfrak{A}}_{r}\left(n-1;q\right){\mathfrak{A}}_{r}\left(n+1;q\right)={q}^{n+r},$  and so that $\left\{{\mathfrak{A}}_{r}\left(n;q\right)\right\}$  is $q$  -log-concave in $n$  . Thus the constant triangle $\left\{a\left(n,k\right)\right\}$  is LC-positive and therefore double LC-positive since ${a}^{*}\left(n,k\right)=a\left(n,k\right)$  .
Example 1.3. Consider $a\left(n,k\right)=\left(\genfrac{}{}{0}{}{n}{k}\right)$  . Then ${\mathfrak{A}}_{r}\left(n;q\right)={\sum }_{k=r}^{n}\left(\genfrac{}{}{0}{}{n}{k}\right){q}^{k}$  . We have ${\mathfrak{A}}_{r}\left(n;q\right)={\sum }_{k=r}^{n}\left[\left(\genfrac{}{}{0}{}{n-1}{k}\right)+\left(\genfrac{}{}{0}{}{n-1}{k-1}\right)\right]{q}^{k}=\left(q+1\right){\mathfrak{A}}_{r}\left(n-1;q\right)+\left(\genfrac{}{}{0}{}{n-1}{r-1}\right){q}^{r}.$  It follows that
 $\begin{array}{ccc}& & {\mathfrak{A}}_{r}^{2}\left(n;q\right)-{\mathfrak{A}}_{r}\left(n-1;q\right){\mathfrak{A}}_{r}\left(n+1;q\right)\end{array}$
 $\begin{array}{ccc}& =& {\mathfrak{A}}_{r}^{2}\left(n;q\right)-{\mathfrak{A}}_{r}\left(n-1;q\right)\left[\left(q+1\right){\mathfrak{A}}_{r}\left(n;q\right)+\left(\genfrac{}{}{0}{}{n}{r-1}\right){q}^{r}\right]\end{array}$
 $\begin{array}{ccc}& =& \left[{\mathfrak{A}}_{r}\left(n;q\right)-\left(q+1\right){\mathfrak{A}}_{r}\left(n-1;q\right)\right]{\mathfrak{A}}_{r}\left(n;q\right)-\left(\genfrac{}{}{0}{}{n}{r-1}\right){q}^{r}{\mathfrak{A}}_{r}\left(n-1;q\right)\end{array}$
 $\begin{array}{ccc}& =& \left(\genfrac{}{}{0}{}{n-1}{r-1}\right){q}^{r}{\mathfrak{A}}_{r}\left(n;q\right)-\left(\genfrac{}{}{0}{}{n}{r-1}\right){q}^{r}{\mathfrak{A}}_{r}\left(n-1;q\right)\end{array}$
 $\begin{array}{ccc}& =& {\sum }_{k=r}^{n}\left[\left(\genfrac{}{}{0}{}{n-1}{r-1}\right)\left(\genfrac{}{}{0}{}{n}{k}\right)-\left(\genfrac{}{}{0}{}{n}{r-1}\right)\left(\genfrac{}{}{0}{}{n-1}{k}\right)\right]{q}^{k+r}\end{array}$
 $\begin{array}{ccc}& =& {\sum }_{k=r}^{n}\left[\left(\genfrac{}{}{0}{}{n-1}{r-1}\right)\left(\genfrac{}{}{0}{}{n-1}{k-1}\right)-\left(\genfrac{}{}{0}{}{n-1}{r-2}\right)\left(\genfrac{}{}{0}{}{n-1}{k}\right)\right]{q}^{k+r},\end{array}$
which has nonnegative coefficients by the log-concavity of the binomial coefficients.
Hence $\left\{{\mathfrak{A}}_{r}\left(n;q\right)\right\}$  is $q$  -log-concave in $n$  . Thus the Pascal triangle $\left\{a\left(n,k\right)\right\}$  is LC-positive and therefore double LC-positive since ${a}^{*}\left(n,k\right)=a\left(n,k\right)$  .
The object of this paper is twofold. First, we show that LC-positive triangles are PLC and that double LC-positive triangles are double PLC. Second, we present some examples of PLC and double PLC triangles by showing the LC-positivity.

2 Theorems

In this section we will discuss the LC-positivity in detail and establish the relation between the (double) LC-positivity and the (double) PLC property. The following simple result will be used repeatedly in our discussion.
Lemma 2.1. Suppose that ${a}_{0},\dots ,{a}_{s}$  and ${X}_{0},\dots ,{X}_{s}$  satisfy the following conditions:
• (a) ${\sum }_{k=r}^{s}{a}_{k}\ge 0$  for all $0\le r\le s$  ;
• (b) $0\le {X}_{0}\le {X}_{1}\le \dots \le {X}_{s}$  .
Then ${\sum }_{k=0}^{s}{a}_{k}{X}_{k}\ge {X}_{0}{\sum }_{k=0}^{s}{a}_{k}\ge 0$  .
• Proof. The statement follows immediately from the Abel's partial summation ${\sum }_{k=0}^{s}{a}_{k}{X}_{k}=\left({a}_{0}+{a}_{1}+\cdots +{a}_{s}\right){X}_{0}+\left({a}_{1}+\cdots +{a}_{s}\right)\left({X}_{1}-{X}_{0}\right)+\cdots +{a}_{s}\left({X}_{s}-{X}_{s-1}\right).$
We first consider the relation between the LC-positivity and the PLC property. Let $\left\{a\left(n,k\right){\right\}}_{0\le k\le n}$  be a triangle of nonnegative numbers and $\left\{{x}_{k}{\right\}}_{k\ge 0}$  be a log-concave sequence.
It is convenient to extend the definition of ${x}_{k}$  and $a\left(n,k\right)$  by setting ${x}_{k}=0$  for $k<0$  and $a\left(n,k\right)=0$  for $k<0$  or $k>n$  . Let $\left\{{z}_{n}{\right\}}_{n\ge 0}$  be the sequence defined by ( 1.1 ) and denote ${\Delta }_{n}={z}_{n}^{2}-{z}_{n-1}{z}_{n+1}$  . Then we need that ${\Delta }_{n}\ge 0$  for each $n\ge 1$  . Note that
 $\begin{array}{ccc}{\Delta }_{n}={\left\{{\sum }_{k=0}^{n}a\left(n,k\right){x}_{k}\right\}}^{2}-\left\{{\sum }_{k=0}^{n-1}a\left(n-1,k\right){x}_{k}\right\}\left\{{\sum }_{k=0}^{n+1}a\left(n+1,k\right){x}_{k}\right\}& & \end{array}$ (2.1)
is a quadratic form in $n+2$  variables ${x}_{0},{x}_{1},\dots ,{x}_{n+1}$  . Such quadratic forms are not positive semidefinite in general. Hence the log-concavity of $\left\{{x}_{k}\right\}$  is indispensable for our purposes.
To see this let us take $a\left(n,k\right)\equiv 1$  for $0\le k\le n$  as an example. In this case we have ${\Delta }_{2}=\left({x}_{0}+{x}_{1}{\right)}^{2}-{x}_{0}\left({x}_{0}+{x}_{1}+{x}_{2}\right)={x}_{1}^{2}+{x}_{0}{x}_{1}-{x}_{0}{x}_{2}.$  Clearly, ${\Delta }_{2}$  may take negative values for nonnegative ${x}_{k}$  's, but it must be nonnegative when ${x}_{0},{x}_{1},{x}_{2}$  is log-concave.
To utilize the assumption for $\left\{{x}_{k}\right\}$  , recall that $\left\{{x}_{k}\right\}$  is log-concave if and only if ${x}_{i-1}{x}_{j+1}\le {x}_{i}{x}_{j}$  for $j\ge i\ge 1$  . In other words, the ${x}_{i}{x}_{j}$  's with the same “weight” $i+j$  are comparable.
Collect together those terms in ${\Delta }_{n}$  with the same weight $t$  and denote their sum by ${S}_{t}$  . For $0\le k\le ⌊t/2⌋$  , let ${a}_{k}\left(n,t\right)$  be the coefficient of the term ${x}_{k}{x}_{t-k}$  in ${\Delta }_{n}$  . Then ${\Delta }_{n}={\sum }_{t=0}^{2n}{S}_{t}$  and ${S}_{t}={\sum }_{k=0}^{⌊t/2⌋}{a}_{k}\left(n,t\right){x}_{k}{x}_{t-k}$  . Thus it suffices that ${S}_{t}\ge 0$  for each $0\le t\le 2n$  . Note that ${x}_{0}{x}_{t}\le {x}_{1}{x}_{t-1}\le {x}_{2}{x}_{t-2}\le \cdots$  . Hence by Lemma  2.1 , it suffices that ${\sum }_{k=r}^{⌊t/2⌋}{a}_{k}\left(n,t\right)\ge 0$  for each $0\le r\le ⌊t/2⌋$  . By ( 2.1 ), ${a}_{k}\left(n,t\right)=2a\left(n,k\right)a\left(n,t-k\right)-a\left(n-1,k\right)a\left(n+1,t-k\right)-a\left(n+1,k\right)a\left(n-1,t-k\right)$  for $k  , and ${a}_{k}\left(n,t\right)={a}^{2}\left(n,k\right)-a\left(n-1,k\right)a\left(n+1,k\right)$  for $t$  even and $k=t/2$  . Denote
 $\begin{array}{ccc}{A}_{r}\left(n,t\right)={\sum }_{k=r}^{⌊t/2⌋}{a}_{k}\left(n,t\right).& & \end{array}$ (2.2)
Then it is not difficult to see that ${A}_{r}\left(n,t\right)$  is precisely the coefficient of ${q}^{t}$  in the polynomial ${\mathfrak{A}}_{r}^{2}\left(n;q\right)-{\mathfrak{A}}_{r}\left(n-1;q\right){\mathfrak{A}}_{r}\left(n+1;q\right)$  , i.e.,
 $\begin{array}{ccc}{\mathfrak{A}}_{r}^{2}\left(n;q\right)-{\mathfrak{A}}_{r}\left(n-1;q\right){\mathfrak{A}}_{r}\left(n+1;q\right)={\sum }_{t=2r}^{2n}{A}_{r}\left(n,t\right){q}^{t}.& & \end{array}$ (2.3)
So the following lemma is immediate.
Lemma 2.2. With the notation above, the triangle $\left\{a\left(n,k\right){\right\}}_{0\le k\le n}$  is LC-positive if and only if ${A}_{r}\left(n,t\right)\ge 0$  for all $2r\le t\le 2n$  .
We can now conclude the first main result of this paper from the discussion above.
Theorem 2.3. The LC-positive triangles are PLC.
We next relate the double LC-positivity with the double PLC property.
Lemma 2.4. Let $\left\{a\left(n,k\right){\right\}}_{0\le k\le n}$  be a triangle of nonnegative numbers and $\left\{{x}_{k}{\right\}}_{k\ge 0}$  and $\left\{{y}_{k}{\right\}}_{k\ge 0}$  be two log-concave sequences. Define three triangles $\left\{b\left(n,k\right)\right\},\left\{c\left(n,k\right)\right\}$  and $\left\{d\left(n,k\right)\right\}$  by $b\left(n,k\right)=a\left(n,k\right){x}_{k},c\left(n,k\right)=a\left(n,k\right){y}_{n-k},d\left(n,k\right)=a\left(n,k\right){x}_{k}{y}_{n-k}.$  For $2r\le t\le 2n$  , define ${B}_{r}\left(n,t\right),{C}_{r}\left(n,t\right)$  and ${D}_{r}\left(n,t\right)$  similar to ${A}_{r}\left(n,t\right)$  in ( 2.2 ).
• (i) If the triangle $\left\{a\left(n,k\right)\right\}$  is LC-positive, then the triangle $\left\{b\left(n,k\right)\right\}$  is LC-positive and ${B}_{r}\left(n,t\right)\ge {A}_{r}\left(n,t\right){x}_{r}{x}_{t-r}$  .
• (ii) If the triangle $\left\{a\left(n,k\right)\right\}$  is double LC-positive, then the triangle $\left\{c\left(n,k\right)\right\}$  is LC-positive and ${C}_{r}\left(n,t\right)\ge {A}_{r}\left(n,t\right){y}_{n-t+r}{y}_{n-r}$  for $t\le n+r$  .
• (iii) If the triangle $\left\{a\left(n,k\right)\right\}$  is double LC-positive, then the triangle $\left\{d\left(n,k\right)\right\}$  is LC-positive and ${D}_{r}\left(n,t\right)\ge {A}_{r}\left(n,t\right){x}_{r}{x}_{t-r}{y}_{n-t+r}{y}_{n-r}$  for $t\le n+r$  .
• Proof. Clearly, (iii) follows from (i) and (ii), so it suffices to prove (i) and (ii).
(i) Let $0\le t\le 2n$  . It is easy to see by definition that ${b}_{k}\left(n,t\right)={a}_{k}\left(n,t\right){x}_{k}{x}_{t-k}$  for $0\le k\le ⌊t/2⌋$  . Hence for $0\le r\le ⌊t/2⌋$  ,  $\begin{array}{ccc}{B}_{r}\left(n,t\right)={\sum }_{k=r}^{⌊t/2⌋}{b}_{k}\left(n,t\right)={\sum }_{k=r}^{⌊t/2⌋}{a}_{k}\left(n,t\right){x}_{k}{x}_{t-k}.& & \end{array}$
Now $\left\{a\left(n,k\right)\right\}$  is LC-positive and ${x}_{0}{x}_{t}\le {x}_{1}{x}_{t-1}\le {x}_{2}{x}_{t-2}\le \cdots$  by the log-concavity of $\left\{{x}_{k}\right\}$  . From Lemma  2.1 it follows that ${B}_{r}\left(n,t\right)\ge {x}_{r}{x}_{t-r}{\sum }_{k=r}^{⌊t/2⌋}{a}_{k}\left(n,t\right)={A}_{r}\left(n,t\right){x}_{r}{x}_{t-r}\ge 0.$  So the triangle $\left\{b\left(n,k\right)\right\}$  is LC-positive. (ii) Let $2r\le t\le 2n$  . We need to prove ${C}_{r}\left(n,t\right)\ge 0$  . For brevity, we do this only for the case $t$  odd since the same technique is still valid for the case $t$  even.
Let $t=2s+1$  . For $0\le k\le s$  , denote  $\begin{array}{ccc}{\alpha }_{k}& =& a\left(n,k\right)a\left(n,t-k\right),\end{array}$
 $\begin{array}{ccc}{\beta }_{k}& =& a\left(n-1,k\right)a\left(n+1,t-k\right),\end{array}$
 $\begin{array}{ccc}{\gamma }_{k}& =& a\left(n+1,k\right)a\left(n-1,t-k\right),\end{array}$
and ${Y}_{k}={y}_{n-t+k}{y}_{n-k}$  . Then ${a}_{k}\left(n,t\right)=2{\alpha }_{k}-{\beta }_{k}-{\gamma }_{k}$  and  $\begin{array}{ccc}{c}_{k}\left(n,t\right)=2{\alpha }_{k}{Y}_{k}-{\beta }_{k}{Y}_{k+1}-{\gamma }_{k}{Y}_{k-1}& & \end{array}$
by definition. It follows that  $\begin{array}{ccc}{C}_{r}\left(n,t\right)& =& {\sum }_{k=r}^{s}\left(2{\alpha }_{k}{Y}_{k}-{\beta }_{k}{Y}_{k+1}-{\gamma }_{k}{Y}_{k-1}\right)\end{array}$
 $\begin{array}{ccc}& =& {\sum }_{k=r}^{s}\left(2{\alpha }_{k}-{\beta }_{k-1}-{\gamma }_{k+1}\right){Y}_{k}+{\beta }_{r-1}{Y}_{r}-{\gamma }_{r}{Y}_{r-1},\end{array}$
where we use the fact that ${Y}_{s+1}={Y}_{s}$  and ${\gamma }_{s+1}={\beta }_{s}$  . Note that $\left\{{Y}_{k}\right\}$  is nondecreasing by the log-concavity of $\left\{{y}_{k}\right\}$  and  $\begin{array}{ccc}2{\alpha }_{k}-{\beta }_{k-1}-{\gamma }_{k+1}=2{a}^{*}\left(n,n-k\right){a}^{*}\left(n,n-t+k\right)& & \end{array}$
 $\begin{array}{ccc}& & -{a}^{*}\left(n-1,n-k\right){a}^{*}\left(n+1,n-t+k\right)-{a}^{*}\left(n+1,n-k\right){a}^{*}\left(n-1,n-t+k\right)\end{array}$
 $\begin{array}{ccc}& =& {a}_{n-t+k}^{*}\left(n,2n-t\right).\end{array}$
Hence by the LC-positivity of $\left\{{a}^{*}\left(n,k\right)\right\}$  , we have  $\begin{array}{ccc}{C}_{r}\left(n,t\right)& =& {\sum }_{j=n-t+r}^{⌊\left(2n-t\right)/2⌋}{a}_{j}^{*}\left(n,2n-t\right){Y}_{j-n+t}+{\beta }_{r-1}{Y}_{r}-{\gamma }_{r}{Y}_{r-1}\end{array}$
 $\begin{array}{ccc}& \ge & {Y}_{r}{\sum }_{j=n-t+r}^{⌊\left(2n-t\right)/2⌋}{a}_{j}^{*}\left(n,2n-t\right)+{\beta }_{r-1}{Y}_{r}-{\gamma }_{r}{Y}_{r-1}\end{array}$
 $\begin{array}{ccc}& =& {Y}_{r}{\sum }_{k=r}^{s}\left(2{\alpha }_{k}-{\beta }_{k-1}-{\gamma }_{k+1}\right)+{\beta }_{r-1}{Y}_{r}-{\gamma }_{r}{Y}_{r-1}\end{array}$
 $\begin{array}{ccc}& =& {Y}_{r}{\sum }_{k=r}^{s}\left(2{\alpha }_{k}-{\beta }_{k}-{\gamma }_{k}\right)+{\gamma }_{r}\left({Y}_{r}-{Y}_{r-1}\right)\end{array}$
 $\begin{array}{ccc}& =& {A}_{r}\left(n,t\right){Y}_{r}+{\gamma }_{r}\left({Y}_{r}-{Y}_{r-1}\right).\end{array}$ (2.4)
Thus ${C}_{r}\left(n,t\right)\ge {A}_{r}\left(n,t\right){y}_{n-t+r}{y}_{n-r}\ge 0$  since ${Y}_{r}\ge {Y}_{r-1}$  , as desired.
Now we present the second main result of this paper.
Theorem 2.5. The double LC-positive triangles are double PLC.
• Proof. Let the triangle $\left\{a\left(n,k\right)\right\}$  be double LC-positive. Suppose that both $\left\{{x}_{k}\right\}$  and $\left\{{y}_{k}\right\}$  are log-concave. Then the triangle $\left\{a\left(n,k\right){x}_{k}{y}_{n-k}\right\}$  is LC-positive by Lemma  2.4 (iii) and is therefore PLC by Theorem  2.3 . Thus the row-sum sequence ${z}_{n}={\sum }_{k=0}^{n}a\left(n,k\right){x}_{k}{y}_{n-k},n=0,1,2,\dots$  is log-concave. In other words, the triangle $\left\{a\left(n,k\right)\right\}$  is double PLC.
We can give some more practical conditions that imply the LC-positivity. We have seen that Lemma  2.1 plays a key role in the proof of the LC-positivity in Lemma  2.4 . Clearly, Condition (a) in Lemma  2.1 is implied by the following two conditions:
• (a1) ${a}_{0},{a}_{1},\dots ,{a}_{s}$  changes from nonpositive to nonnegative values;
• (a2) ${\sum }_{k=0}^{s}{a}_{k}\ge 0$  .
These two conditions are easier to check than Condition (a). For example, Condition (a1) can be obtained by showing that the sequence $\left\{{a}_{k}\right\}$  is nondecreasing and eventually nonnegative. In this case the analytic tools are often effective. On the other hand, Condition (a2) is just the simplest one of inequalities appeared in Condition (a) and the methods of generating functions will be useful (see [23for details). By Lemma  2.2 , $\left\{a\left(n,k\right)\right\}$  is LC-positive if and only if the inequality ${\sum }_{k=r}^{⌊t/2⌋}{a}_{k}\left(n,t\right)\ge 0$  for all $2r\le t\le 2n$  , so the following corollary is immediate.
Corollary 2.6. Suppose that the triangle $\left\{a\left(n,k\right)\right\}$  satisfies the following two conditions:
• (A) There exists an index $m=m\left(n,t\right)$  such that ${a}_{k}\left(n,t\right)<0$  for $k  and ${a}_{k}\left(n,t\right)\ge 0$  for $k\ge m$  ;
• (B) The sequence $\left\{{\mathfrak{A}}_{0}\left(n;q\right){\right\}}_{n\ge 0}$  is $q$  -log-concave.
Then the triangle $\left\{a\left(n,k\right)\right\}$  is LC-positive and therefore PLC.
Corollary 2.7. Suppose that the triangle $\left\{a\left(n,k\right)\right\}$  satisfies Condition (A) and (B) in Corollary  2.6 and $\left\{{a}^{*}\left(n,k\right)\right\}$  satisfies Condition (A). Then $\left\{a\left(n,k\right)\right\}$  is double LC-positive and therefore double PLC.
• Proof. By Theorem  2.5 and Corollary  2.6 , it suffices to show that $\left\{{\mathfrak{A}}_{0}^{*}\left(n;q\right)\right\}$  is $q$  -log-concave.
We have  $\begin{array}{ccc}{\mathfrak{A}}_{0}^{*}\left(n;q\right)={\sum }_{k=0}^{n}a\left(n,n-k\right){q}^{k}={\sum }_{k=0}^{n}a\left(n,k\right){q}^{n-k}={q}^{n}{\mathfrak{A}}_{0}\left(n;{q}^{-1}\right).& & \end{array}$
It follows that  $\begin{array}{ccc}& & {{\mathfrak{A}}_{0}^{*}}^{2}\left(n;q\right)-{\mathfrak{A}}_{0}^{*}\left(n-1;q\right){\mathfrak{A}}_{0}^{*}\left(n+1;q\right)\end{array}$
 $\begin{array}{ccc}& =& {q}^{2n}\left[{\mathfrak{A}}_{0}^{2}\left(n;{q}^{-1}\right)-{\mathfrak{A}}_{0}\left(n-1;{q}^{-1}\right){\mathfrak{A}}_{0}\left(n+1;{q}^{-1}\right)\right],\end{array}$
which has nonnegative coefficients by the $q$  -log-concavity of $\left\{{\mathfrak{A}}_{0}\left(n;q\right)\right\}$  , as desired.

3 Applications

In this section we give some examples of PLC and double PLC triangles by showing their LC-positivity. We have shown that $a\left(n,k\right)\equiv 1$  and $a\left(n,k\right)=\left(\genfrac{}{}{0}{}{n}{k}\right)$  are double LC-positive in Example  1.2 and  1.3 respectively. So the following two propositions are immediate from Theorem  2.5 .
Proposition 3.1. If the sequences $\left\{{x}_{n}\right\}$  and $\left\{{y}_{n}\right\}$  are log-concave, then so is their ordinary convolution ${z}_{n}={\sum }_{k=0}^{n}{x}_{k}{y}_{n-k},n=0,1,2,\dots$  .
Proposition 3.2. If the sequences $\left\{{x}_{n}\right\}$  and $\left\{{y}_{n}\right\}$  are log-concave, then so is their binomial convolution ${z}_{n}={\sum }_{k=0}^{n}\left(\genfrac{}{}{0}{}{n}{k}\right){x}_{k}{y}_{n-k},n=0,1,2,\dots$  .
It is easy to extend Proposition  3.2 (by induction) to several log-concave sequences.
Corollary 3.3. If the sequences $\left\{{x}_{k}^{\left(1\right)}\right\},\left\{{x}_{k}^{\left(2\right)}\right\},\dots ,\left\{{x}_{k}^{\left(j\right)}\right\}$  are all log-concave, then so is the sequence ${X}_{n}=\sum \left(\genfrac{}{}{0}{}{n}{{k}_{1},{k}_{2},\dots ,{k}_{j}}\right){x}_{{k}_{1}}^{\left(1\right)}{x}_{{k}_{2}}^{\left(2\right)}\cdots {x}_{{k}_{j}}^{\left(j\right)},n=0,1,2,\dots ,$  where the sum is over all ${k}_{1},\dots ,{k}_{j}$  such that ${k}_{1}+{k}_{2}\cdots +{k}_{j}=n$  .
In [20, the triangle $a\left(n,k\right)=\left(\genfrac{}{}{0}{}{a+n}{b+k}\right)$  for $0\le k\le n$  is shown to satisfy Condition (A) and (B), and is therefore LC-positive. The LC-positivity of $\left\{a\left(n,k\right)\right\}$  can also be obtained by the same technique used in Example 1.2. Also, note that ${a}^{*}\left(n,k\right)=\left(\genfrac{}{}{0}{}{a+n}{b+\left(n-k\right)}\right)=\left(\genfrac{}{}{0}{}{a+n}{\left(a-b\right)+k}\right).$  Hence ${a}^{*}\left(n,k\right)$  is also LC-positive. Thus the triangle $\left\{a\left(n,k\right)\right\}$  is double LC-positive and therefore double PLC.
Proposition 3.4. Let $a,b$  be two nonnegative integers and $a\ge b$  . If the sequences $\left\{{x}_{n}\right\}$  and $\left\{{y}_{n}\right\}$  are log-concave, then so is the sequence ${z}_{n}={\sum }_{k=0}^{n}\left(\genfrac{}{}{0}{}{a+n}{b+k}\right){x}_{k}{y}_{n-k},n=0,1,2,\dots .$
We can provide a unified setting for the above three propositions. Denote by $S$  the set of sequences $\left\{{u}_{k}{\right\}}_{k\in \mathbb{Z}}$  of nonnegative numbers. Given two nonnegative numbers $\lambda ,\mu$  , define the linear operator $\mathfrak{L}=\mathfrak{L}\left[\lambda ,\mu \right]$  on $S$  by $\mathfrak{L}\left({u}_{k}\right)=\lambda {u}_{k}+\mu {u}_{k-1},k\in \mathbb{Z}.$  For $n\ge 2$  , define ${\mathfrak{L}}^{n}=\mathfrak{L}\left({\mathfrak{L}}^{n-1}\right)$  by induction. It is convenient to view ${\mathfrak{L}}^{0}$  as the identity operator. Let the sequence $\left\{{u}_{k}{\right\}}_{k\in \mathbb{Z}}$  be log-concave. Then the sequence $\left\{\mathfrak{L}\left({u}_{k}\right){\right\}}_{k\in \mathbb{Z}}$  is also log-concave since
 $\begin{array}{ccc}& & \left[\mathfrak{L}\left({u}_{k}\right){\right]}^{2}-\mathfrak{L}\left({u}_{k-1}\right)\mathfrak{L}\left({u}_{k+1}\right)\end{array}$
 $\begin{array}{ccc}& =& \left(\lambda {u}_{k}+\mu {u}_{k-1}{\right)}^{2}-\left(\lambda {u}_{k-1}+\mu {u}_{k-2}\right)\left(\lambda {u}_{k+1}+\mu {u}_{k}\right)\end{array}$
 $\begin{array}{ccc}& =& {\lambda }^{2}\left({u}_{k}^{2}-{u}_{k-1}{u}_{k+1}\right)+\lambda \mu \left({u}_{k-1}{u}_{k}-{u}_{k-2}{u}_{k+1}\right)+{\mu }^{2}\left({u}_{k-1}^{2}-{u}_{k-2}{u}_{k}\right)\end{array}$
 $\begin{array}{ccc}& \ge & 0.\end{array}$
By induction, the sequence $\left\{{\mathfrak{L}}^{n}\left({u}_{k}\right){\right\}}_{k\in \mathbb{Z}}$  is log-concave for each $n\ge 0$  .
Proposition 3.5. Given two nonnegative numbers $\lambda ,\mu$  and a log-concave sequence $\left\{{u}_{k}{\right\}}_{k\in \mathbb{Z}}$  , define $a\left(n,k\right)={\mathfrak{L}}^{n}\left[\lambda ,\mu \right]\left({u}_{k}\right)$  for $0\le k\le n$  . Then the triangle $\left\{a\left(n,k\right)\right\}$  is double LC-positive and therefore double PLC.
• Proof. Denote ${a}_{k}={\mathfrak{L}}^{n-1}\left[\lambda ,\mu \right]\left({u}_{k}\right)$  for $k\in \mathbb{Z}$  . Then the sequence $\left\{{a}_{k}{\right\}}_{k\in \mathbb{Z}}$  is log-concave and ${\mathfrak{A}}_{r}\left(n-1;q\right)={\sum }_{k=r}^{n-1}{a}_{k}{q}^{k}$  . We have  $\begin{array}{ccc}{\mathfrak{A}}_{r}\left(n;q\right)& =& {\sum }_{k=r}^{n}\mathfrak{L}\left({a}_{k}\right)\left[\lambda ,\mu \right]{q}^{k}\end{array}$
 $\begin{array}{ccc}& =& {\sum }_{k=r}^{n}\left(\lambda {a}_{k}+\mu {a}_{k-1}\right){q}^{k}\end{array}$
 $\begin{array}{ccc}& =& \lambda {\sum }_{k=r}^{n}{a}_{k}{q}^{k}+\mu {\sum }_{k=r}^{n}{a}_{k-1}{q}^{k}\end{array}$
 $\begin{array}{ccc}& =& \left(\lambda +\mu q\right){\mathfrak{A}}_{r}\left(n-1;q\right)+\lambda {a}_{n}{q}^{n}+\mu {a}_{r-1}{q}^{r},\end{array}$
and similarly,  $\begin{array}{ccc}{\mathfrak{A}}_{r}\left(n+1;q\right)=\left(\lambda +\mu q\right){\mathfrak{A}}_{r}\left(n;q\right)+\lambda \left(\lambda {a}_{n+1}+\mu {a}_{n}\right){q}^{n+1}+\mu \left(\lambda {a}_{r-1}+\mu {a}_{r-2}\right){q}^{r}.& & \end{array}$
It follows that  $\begin{array}{ccc}& & {\mathfrak{A}}_{r}^{2}\left(n;q\right)-{\mathfrak{A}}_{r}\left(n-1;q\right){\mathfrak{A}}_{r}\left(n+1;q\right)\end{array}$
 $\begin{array}{ccc}& =& {\mathfrak{A}}_{r}^{2}\left(n;q\right)-\left(\lambda +\mu q\right){\mathfrak{A}}_{r}\left(n-1;q\right){\mathfrak{A}}_{r}\left(n;q\right)\end{array}$
 $\begin{array}{ccc}& & -\left[\lambda \left(\lambda {a}_{n+1}+\mu {a}_{n}\right){q}^{n+1}+\mu \left(\lambda {a}_{r-1}+\mu {a}_{r-2}\right){q}^{r}\right]{\mathfrak{A}}_{r}\left(n-1;q\right)\end{array}$
 $\begin{array}{ccc}& =& \left(\lambda {a}_{n}{q}^{n}+\mu {a}_{r-1}{q}^{r}\right){\mathfrak{A}}_{r}\left(n;q\right)\end{array}$
 $\begin{array}{ccc}& & -\left[\lambda \left(\lambda {a}_{n+1}+\mu {a}_{n}\right){q}^{n+1}+\mu \left(\lambda {a}_{r-1}+\mu {a}_{r-2}\right){q}^{r}\right]{\mathfrak{A}}_{r}\left(n-1;q\right)\end{array}$
 $\begin{array}{ccc}& =& \lambda {\sum }_{k=r}^{n}\left(\lambda {a}_{k}+\mu {a}_{k-1}\right){a}_{n}{q}^{n+k}+\mu {\sum }_{k=r}^{n}{a}_{r-1}\left(\lambda {a}_{k}+\mu {a}_{k-1}\right){q}^{k+r}\end{array}$
 $\begin{array}{ccc}& & -\lambda {\sum }_{k=r}^{n-1}{a}_{k}\left(\lambda {a}_{n+1}+\mu {a}_{n}\right){q}^{n+k+1}-\mu {\sum }_{k=r}^{n-1}\left(\lambda {a}_{r-1}+\mu {a}_{r-2}\right){a}_{k}{q}^{k+r}\end{array}$
 $\begin{array}{ccc}& =& {\lambda }^{2}{\sum }_{k=r+1}^{n}\left({a}_{k}{a}_{n}-{a}_{k-1}{a}_{n+1}\right){q}^{n+k}+{\mu }^{2}{\sum }_{k=r}^{n}\left({a}_{r-1}{a}_{k-1}-{a}_{r-2}{a}_{k}\right){q}^{k+r}\end{array}$
 $\begin{array}{ccc}& & +\left({\lambda }^{2}{a}_{r}+2\lambda \mu {a}_{r-1}+{\mu }^{2}{a}_{r-2}\right){a}_{n}{q}^{n+r},\end{array}$ (3.1)
which has nonnegative coefficients by the log-concavity of $\left\{{a}_{k}\right\}$  . Hence the triangle $\left\{a\left(n,k\right)\right\}$  is LC-positive. On the other hand, let ${u}_{k}^{*}={u}_{-k}$  for $k\in \mathbb{Z}$  . Then the sequence $\left\{{u}_{k}^{*}{\right\}}_{k\in \mathbb{Z}}$  is log-concave and ${a}^{*}\left(n,k\right)={\mathfrak{L}}^{n}\left[\mu ,\lambda \right]\left({u}_{k}^{*}\right)$  . Thus the triangle $\left\{{a}^{*}\left(n,k\right){\right\}}_{0\le k\le n}$  is also LC-positive, and the triangle $\left\{a\left(n,k\right){\right\}}_{0\le k\le n}$  is therefore double LC-positive.
Remark 3.6. Let the triangle $\left\{a\left(n,k\right)\right\}$  be the same as Proposition  3.5 . Then by ( 2.3 ) and ( 3.1 ), ${A}_{r}\left(n,t\right)\ge \left({a}_{r-1}{a}_{t-r-1}-{a}_{r-2}{a}_{t-r}\right){\mu }^{2}$  holds for $t\le n+r$  (The equality holds when $t  ).
Remark 3.7. In Proposition  3.5 , taking $\lambda =\mu =1/2$  and ${u}_{k}\equiv 1$  leads to Proposition  3.1 ; and taking $\lambda =\mu =1$  and ${u}_{k}=\left(\genfrac{}{}{0}{}{a}{b+k}\right)$  leads to Proposition  3.4 . In particular, letting $a=b=0$  in the latter leads to Proposition  3.2 .
Proposition 3.8. Let $\alpha ,\beta$  be two nonnegative numbers and $\left\{a\left(n,k\right){\right\}}_{0\le k\le n}$  a triangle of nonnegative numbers. Suppose that each row of $\left\{a\left(n,k\right)\right\}$  is log-concave and satisfies the recurrence relation
 $\begin{array}{ccc}a\left(n,k\right)=\alpha a\left(n+1,k\right)+\beta a\left(n+1,k+1\right),k=0,1,\dots ,n.& & \end{array}$
Then the triangle $\left\{a\left(n,k\right)\right\}$  is double LC-positive and therefore double PLC.
• Proof. Denote $a\left(n+1,k\right)={v}_{k}$  for $0\le k\le n+1$  . Then the sequence $\left\{{v}_{k}\right\}$  is log-concave and ${\mathfrak{A}}_{r}\left(n+1;q\right)={\sum }_{k=r}^{n+1}{v}_{k}{q}^{k}$  . By the recurrence relation we have  $\begin{array}{ccc}{\mathfrak{A}}_{r}\left(n;q\right)& =& {\sum }_{k=r}^{n}\left(\alpha {v}_{k}+\beta {v}_{k+1}\right){q}^{k}\end{array}$
 $\begin{array}{ccc}& =& \alpha {\sum }_{k=r}^{n}{v}_{k}{q}^{k}+\beta {\sum }_{k=r+1}^{n+1}{v}_{k}{q}^{k-1}\end{array}$
 $\begin{array}{ccc}& =& \left(\alpha +\beta {q}^{-1}\right){\mathfrak{A}}_{r}\left(n+1;q\right)-\alpha {v}_{n+1}{q}^{n+1}-\beta {v}_{r}{q}^{r-1},\end{array}$
and similarly, ${\mathfrak{A}}_{r}\left(n-1;q\right)=\left(\alpha +\beta {q}^{-1}\right){\mathfrak{A}}_{r}\left(n;q\right)-\alpha \left(\alpha {v}_{n}+\beta {v}_{n+1}\right){q}^{n}-\beta \left(\alpha {v}_{r}+\beta {v}_{r+1}\right){q}^{r-1}.$  It follows that  $\begin{array}{ccc}& & {\mathfrak{A}}_{r}^{2}\left(n;q\right)-{\mathfrak{A}}_{r}\left(n-1;q\right){\mathfrak{A}}_{r}\left(n+1;q\right)\end{array}$
 $\begin{array}{ccc}& =& \left[\alpha \left(\alpha {v}_{n}+\beta {v}_{n+1}\right){q}^{n}+\beta \left(\alpha {v}_{r}+\beta {v}_{r+1}\right){q}^{r-1}\right]{\mathfrak{A}}_{r}\left(n+1;q\right)\end{array}$
 $\begin{array}{ccc}& & -\left(\alpha {v}_{n+1}{q}^{n+1}+\beta {v}_{r}{q}^{r-1}\right){\mathfrak{A}}_{r}\left(n;q\right)\end{array}$
 $\begin{array}{ccc}& =& {\alpha }^{2}{\sum }_{k=r+1}^{n}\left({v}_{k}{v}_{n}-{v}_{k-1}{v}_{n+1}\right){q}^{n+k}+{\beta }^{2}{\sum }_{k=r}^{n}\left({v}_{r+1}{v}_{k+1}-{v}_{r}{v}_{k+2}\right){q}^{r+k}\end{array}$
 $\begin{array}{ccc}& & +{v}_{r}\left({\alpha }^{2}{v}_{n}+2\alpha \beta {v}_{n+1}+{\beta }^{2}{v}_{n+2}\right){q}^{n+r},\end{array}$
which has nonnegative coefficients by the log-concavity of $\left\{{v}_{k}\right\}$  . So the triangle $\left\{a\left(n,k\right)\right\}$  is LC-positive. Clearly, the reciprocal triangle $\left\{{a}^{*}\left(n,k\right)\right\}$  possesses the same property as the triangle $\left\{a\left(n,k\right)\right\}$  does. Hence $\left\{{a}^{*}\left(n,k\right)\right\}$  is also LC-positive. Thus the triangle $\left\{a\left(n,k\right)\right\}$  is double LC-positive.
In Proposition  3.8 , taking $\alpha =\beta =1/2$  and $a\left(n,k\right)\equiv 1$  for $0\le k\le n$  leads to Proposition  3.1 ; and taking $\alpha =\beta =1$  and $a\left(n,k\right)=\left(\genfrac{}{}{0}{}{a-n}{b-k}\right)$  for $0\le k\le n$  leads to the following.
Proposition 3.9. Let $a,b\in \mathbb{N}$  and $a\ge b$  . If the sequences $\left\{{x}_{k}\right\}$  and $\left\{{y}_{k}\right\}$  are log-concave, then so is the sequence ${z}_{n}={\sum }_{k=0}^{n}\left(\genfrac{}{}{0}{}{a-n}{b-k}\right){x}_{k}{y}_{n-k},n=0,1,2,\dots .$
In what follows we generalize a result of Liggett. Let $\left\{{x}_{k}{\right\}}_{k\ge 0}$  be a sequence of nonnegative numbers and with no internal zeros. Following Pemantle [12and Liggett [10, the sequence is ultra-log-concave of order $m$  (ULC( $m$  )) if ${x}_{k}=0$  for $k>m$  and the sequence ${\left\{{x}_{k}/\left(\genfrac{}{}{0}{}{m}{k}\right)\right\}}_{k=0}^{m}$  is log-concave. The sequence $\left\{{x}_{k}{\right\}}_{k\ge 0}$  is ULC( $\infty$  ) if the sequence $\left\{k!{x}_{k}{\right\}}_{k\ge 0}$  is log-concave.
It is clear from definitions that ULC( $m$  ) implies ULC( $\ell$  ) for $0\le m\le \ell \le \infty$  . The concept of ultra-log-concavity is closely related to negatively dependent Bernoulli sequences (see [12for details). Pemantle speculates that ultra-log-concavity is characteristic of negative dependence in the exchangeable case. This leads to a conjecture that the ordinary convolution of a ULC( $m$  ) sequence and a ULC( $\ell$  ) sequence is ULC( $m+\ell$  ) where $m$  and $\ell$  may be infinity ([12,Conjecture7). It is not difficult to see that the conjecture actually consists of two parts:
• (i) The Pascal triangle $\left\{\left(\genfrac{}{}{0}{}{n}{k}\right)\right\}$  is double PLC;
• (ii) The triangle $\left\{\left(\genfrac{}{}{0}{}{n}{k}\right)\left(\genfrac{}{}{0}{}{a-n}{b-k}\right)\right\}$  is double PLC.
Liggett verified the conjecture by established a stronger result ([10,Theorem3).
Liggett Theorem. Given three log-concave sequences $\left\{{v}_{k}\right\}$  , $\left\{{x}_{k}\right\}$  and $\left\{{y}_{k}\right\}$  , let
 $\begin{array}{ccc}{z}_{n-1}& =& {\sum }_{k=0}^{n-1}\left(\genfrac{}{}{0}{}{n-1}{k}\right)\left({v}_{k}+2{v}_{k+1}+{v}_{k+2}\right){x}_{k}{y}_{n-1-k},\end{array}$
 $\begin{array}{ccc}{z}_{n}& =& {\sum }_{k=0}^{n}\left(\genfrac{}{}{0}{}{n}{k}\right)\left({v}_{k}+{v}_{k+1}\right){x}_{k}{y}_{n-k},\end{array}$
 $\begin{array}{ccc}{z}_{n+1}& =& {\sum }_{k=0}^{n+1}\left(\genfrac{}{}{0}{}{n+1}{k}\right){v}_{k}{x}_{k}{y}_{n+1-k}.\end{array}$
Then ${z}_{n-1}{z}_{n+1}\le {z}_{n}^{2}$  .
Liggett's proof for his theorem, essentially using the double LC-positivity of the Pascal triangle, is not simple. To see his idea more clearly, we show the following more general result.
Proposition 3.10. Given four nonnegative numbers $\alpha ,\beta ,\lambda ,\mu$  and four log-concave sequences $\left\{{u}_{k}{\right\}}_{k\in \mathbb{Z}}$  , $\left\{{v}_{k}{\right\}}_{k\ge 0}$  , $\left\{{x}_{k}{\right\}}_{k\ge 0}$  and $\left\{{y}_{k}{\right\}}_{k\ge 0}$  , let $a\left(n,k\right)={\mathfrak{L}}^{n}\left[\lambda ,\mu \right]\left({u}_{k}\right)$  and
 $\begin{array}{ccc}{z}_{n-1}& =& {\sum }_{k=0}^{n-1}a\left(n-1,k\right)\left({\alpha }^{2}{v}_{k}+2\alpha \beta {v}_{k+1}+{\beta }^{2}{v}_{k+2}\right){x}_{k}{y}_{n-1-k},\end{array}$
 $\begin{array}{ccc}{z}_{n}& =& {\sum }_{k=0}^{n}a\left(n,k\right)\left(\alpha {v}_{k}+\beta {v}_{k+1}\right){x}_{k}{y}_{n-k},\end{array}$
 $\begin{array}{ccc}{z}_{n+1}& =& {\sum }_{k=0}^{n+1}a\left(n+1,k\right){v}_{k}{x}_{k}{y}_{n+1-k}.\end{array}$
Then ${z}_{n-1}{z}_{n+1}\le {z}_{n}^{2}$  .
• Proof. Clearly, ${z}_{n}^{2}-{z}_{n-1}{z}_{n+1}$  can be viewed as a quadratic form in $n+2$  variables ${v}_{0}$  , ${v}_{1}$  , . . . , ${v}_{n+1}$  . Let ${z}_{n}^{2}-{z}_{n-1}{z}_{n+1}={\sum }_{t=0}^{2\left(n+1\right)}{\sum }_{k=0}^{⌊t/2⌋}{e}_{k}\left(n,t\right){v}_{k}{v}_{t-k}.$  Then we need to show that ${\sum }_{k=r}^{⌊t/2⌋}{e}_{k}\left(n,t\right)\ge 0$  for $2r\le t\le 2\left(n+1\right)$  . For brevity, we do this only for the case $t$  odd. Let $t=2s+1$  .
Define $d\left(n,k\right)=a\left(n,k\right){x}_{k}{y}_{n-k}$  for $0\le k\le n$  . For convenience, set ${x}_{k}={y}_{k}=0$  for $k<0$  and $d\left(n,k\right)=0$  for $k<0$  or $k>n$  . The triangle $\left\{a\left(n,k\right)\right\}$  is double LC-positive by Proposition  3.5 , and so is the triangle $\left\{d\left(n,k\right)\right\}$  by Lemma  2.4 . Rewrite  $\begin{array}{ccc}{z}_{n-1}& =& {\sum }_{k=0}^{n+1}\left[{\alpha }^{2}d\left(n-1,k\right)+2\alpha \beta d\left(n-1,k-1\right)+{\beta }^{2}d\left(n-1,k-2\right)\right]{v}_{k},\end{array}$
 $\begin{array}{ccc}{z}_{n}& =& {\sum }_{k=0}^{n+1}\left[\alpha d\left(n,k\right)+\beta d\left(n,k-1\right)\right]{v}_{k},\end{array}$
 $\begin{array}{ccc}{z}_{n+1}& =& {\sum }_{k=0}^{n+1}d\left(n+1,k\right){v}_{k}.\end{array}$
Then  $\begin{array}{ccc}{e}_{k}\left(n,t\right)=2\left[\alpha d\left(n,k\right)+\beta d\left(n,k-1\right)\right]\left[\alpha d\left(n,t-k\right)+\beta d\left(n,t-k-1\right)\right]& & \end{array}$
 $\begin{array}{ccc}& & -\left[{\alpha }^{2}d\left(n-1,k\right)+2\alpha \beta d\left(n-1,k-1\right)+{\beta }^{2}d\left(n-1,k-2\right)\right]d\left(n+1,t-k\right)\end{array}$
 $\begin{array}{ccc}& & -d\left(n+1,k\right)\left[{\alpha }^{2}d\left(n-1,t-k\right)+2\alpha \beta d\left(n-1,t-k-1\right)+{\beta }^{2}d\left(n-1,t-k-2\right)\right]\end{array}$
 $\begin{array}{ccc}& & ={\alpha }^{2}{P}_{k}+2\alpha \beta {Q}_{k}+{\beta }^{2}{R}_{k},\end{array}$
where  $\begin{array}{ccc}{P}_{k}=2d\left(n,k\right)d\left(n,t-k\right)-d\left(n-1,k\right)d\left(n+1,t-k\right)-d\left(n+1,k\right)d\left(n-1,t-k\right),& & \end{array}$
 $\begin{array}{ccc}{Q}_{k}=d\left(n,k\right)d\left(n,t-k-1\right)+d\left(n,k-1\right)d\left(n,t-k\right)& & \end{array}$
 $\begin{array}{ccc}& & -d\left(n-1,k-1\right)d\left(n+1,t-k\right)-d\left(n+1,k\right)d\left(n-1,t-k-1\right),\end{array}$
 $\begin{array}{ccc}{R}_{k}=2d\left(n,k-1\right)d\left(n,t-k-1\right)& & \end{array}$
 $\begin{array}{ccc}& & -d\left(n-1,k-2\right)d\left(n+1,t-k\right)-d\left(n+1,k\right)d\left(n-1,t-k-2\right).\end{array}$
Thus it suffices to show that the inequality  $\begin{array}{ccc}{\alpha }^{2}{\sum }_{k=r}^{s}{P}_{k}+2\alpha \beta {\sum }_{k=r}^{s}{Q}_{k}+{\beta }^{2}{\sum }_{k=r}^{s}{R}_{k}\ge 0.& & \end{array}$ (3.2)
Note that ${P}_{k}={d}_{k}\left(n,t\right)$  and ${R}_{k}={d}_{n-t+k+1}^{*}\left(n,2n-t+2\right)$  . Hence both  $\begin{array}{ccc}{\sum }_{k=r}^{s}{P}_{k}={D}_{r}\left(n,t\right)& & \end{array}$ (3.3)
and  $\begin{array}{ccc}{\sum }_{k=r}^{s}{R}_{k}={D}_{n-t+r+1}^{*}\left(n,2n-t+2\right)& & \end{array}$ (3.4)
are nonnegative by the double LC-positivity of the triangle $\left\{d\left(n,k\right)\right\}$  . Also,  $\begin{array}{ccc}{\sum }_{k=r}^{s}{Q}_{k}={\sum }_{k=r}^{s}\left[d\left(n,k\right)d\left(n,t-k-1\right)+d\left(n,k-1\right)d\left(n,t-k\right)& & \end{array}$
 $\begin{array}{ccc}& & -d\left(n-1,k-1\right)d\left(n+1,t-k\right)-d\left(n+1,k\right)d\left(n-1,t-k-1\right)\right]\end{array}$
 $\begin{array}{ccc}& & =\left[{d}^{2}\left(n,s\right)-d\left(n-1,s\right)d\left(n+1,s\right)\right]+{\sum }_{k=r-1}^{s-1}\left[2d\left(n,k\right)d\left(n,t-1-k\right)\end{array}$
 $\begin{array}{ccc}& & -d\left(n-1,k\right)d\left(n+1,t-1-k\right)-d\left(n+1,k\right)d\left(n-1,t-1-k\right)\right]\end{array}$
 $\begin{array}{ccc}& & +\left[d\left(n+1,r-1\right)d\left(n-1,t-r\right)-d\left(n,r-1\right)d\left(n,t-r\right)\right]\end{array}$
 $\begin{array}{ccc}& & ={D}_{r-1}\left(n,t-1\right)+\left[d\left(n+1,r-1\right)d\left(n-1,t-r\right)-d\left(n,r-1\right)d\left(n,t-r\right)\right].\end{array}$ (3.5)
Assume that $r=0$  or $t>n+r$  . Then ${\sum }_{k=r}^{s}{Q}_{k}={D}_{r-1}\left(n,t-1\right)\ge 0$  . Thus the inequality ( 3.2 ) is trivial. So let $r\ge 1$  and $t\le n+r$  .
If we can show that there exists a nonnegative number $E=E\left(n,t,r\right)$  such that  $\begin{array}{ccc}\left\{\begin{array}{cccc}{\sum }_{k=r}^{s}{P}_{k}& \ge & {\mu }^{2}& E{x}_{r}{x}_{t-r}{y}_{n-t+r}{y}_{n-r},\\ {\sum }_{k=r}^{s}{Q}_{k}& \ge & -\lambda \mu & E{x}_{r-1}{x}_{t-r}{y}_{n-t+r}{y}_{n-r+1},\\ {\sum }_{k=r}^{s}{R}_{k}& \ge & {\lambda }^{2}& E{x}_{r-1}{x}_{t-r-1}{y}_{n-t+r+1}{y}_{n-r+1},\end{array}& & \end{array}$ (3.6)
then the arithmetic-geometric mean inequality and the log-concavity of $\left\{{x}_{k}\right\}$  and $\left\{{y}_{k}\right\}$  will give ${\alpha }^{2}{\sum }_{k=r}^{s}{P}_{k}+{\beta }^{2}{\sum }_{k=r}^{s}{R}_{k}\ge -2\alpha \beta {\sum }_{k=r}^{s}{Q}_{k},$  the required inequality. So, to prove ( 3.2 ), it suffices to prove ( 3.6 ).
We use Lemma  2.4 to estimate the lower bounds for ${\sum }_{k=r}^{s}{P}_{k}$  , ${\sum }_{k=r}^{s}{Q}_{k}$  and ${\sum }_{k=r}^{s}{R}_{k}$  .
From ( 3.3 ) and Lemma  2.4 (iii) it is immediate that  $\begin{array}{ccc}{\sum }_{k=r}^{s}{P}_{k}\ge {A}_{r}\left(n,t\right){x}_{r}{x}_{t-r}{y}_{n-t+r}{y}_{n-r}.& & \end{array}$ (3.7)
Similarly, note that ${d}^{*}\left(n,k\right)={a}^{*}\left(n,k\right){y}_{k}{x}_{n-k}$  , it follows from ( 3.4 ) and Lemma  2.4 (iii) that  $\begin{array}{ccc}{\sum }_{k=r}^{s}{R}_{k}\ge {A}_{n-t+r+1}^{*}\left(n,2n-t+2\right){y}_{n-t+r+1}{y}_{n-r+1}{x}_{t-r-1}{x}_{r-1}.& & \end{array}$ (3.8)
To get an analogous lower bound for ${\sum }_{k=r}^{s}{Q}_{k}$  , let $c\left(n,k\right)=a\left(n,k\right){y}_{n-k}$  . Then $d\left(n,k\right)=c\left(n,k\right){x}_{k}$  and so ${D}_{r-1}\left(n,t-1\right)\ge {C}_{r-1}\left(n,t-1\right){x}_{r-1}{x}_{t-r}$  by Lemma  2.4 (i). However,  $\begin{array}{ccc}{C}_{r-1}\left(n,t-1\right)\ge {A}_{r-1}\left(n,t-1\right){y}_{n-t+r}{y}_{n-r+1}& & \end{array}$
 $\begin{array}{ccc}& & +a\left(n+1,r-1\right)a\left(n-1,t-r\right)\left({y}_{n-t+r}{y}_{n-r+1}-{y}_{n-t+r-1}{y}_{n-r+2}\right)\end{array}$
by the inequality ( 2.4 ). Hence we have by ( 3.5 )  $\begin{array}{ccc}{\sum }_{k=r}^{s}{Q}_{k}\ge \left[{A}_{r-1}\left(n,t-1\right){y}_{n-t+r}{y}_{n-r+1}& & \end{array}$
 $\begin{array}{ccc}& & +a\left(n+1,r-1\right)a\left(n-1,t-r\right)\left({y}_{n-t+r}{y}_{n-r+1}-{y}_{n-t+r-1}{y}_{n-r+2}\right)\right]{x}_{r-1}{x}_{t-r}\end{array}$
 $\begin{array}{ccc}& & +\left[a\left(n+1,r-1\right){x}_{r-1}{y}_{n-r+2}a\left(n-1,t-r\right){x}_{t-r}{y}_{n-t+r-1}\end{array}$
 $\begin{array}{ccc}& & -a\left(n,r-1\right){x}_{r-1}{y}_{n-r+1}a\left(n,t-r\right){x}_{t-r}{y}_{n-t+r}\right]\end{array}$
 $\begin{array}{ccc}& & =Q{x}_{r-1}{x}_{t-r}{y}_{n-t+r}{y}_{n-r+1},\end{array}$ (3.9)
where  $\begin{array}{c}Q={A}_{r-1}\left(n,t-1\right)+a\left(n+1,r-1\right)a\left(n-1,t-r\right)-a\left(n,r-1\right)a\left(n,t-r\right).\end{array}$ (3.10)
It remains to show that three coefficients ${A}_{r}\left(n,t\right)$  , ${A}_{n-t+r+1}^{*}\left(n,2n-t+2\right)$  and $Q$  in inequalities ( 3.7 ), ( 3.8 ) and ( 3.9 ) have the lower bounds of the forms in ( 3.6 ). We do this using Remark  3.6 .
Denote ${a}_{k}={\mathfrak{L}}^{n-1}\left[\lambda ,\mu \right]\left({u}_{k}\right)$  . It follows from Remark  3.6 that ${A}_{r}\left(n,t\right)\ge \left({a}_{r-1}{a}_{t-r-1}-{a}_{r-2}{a}_{t-r}\right){\mu }^{2}$  and that  $\begin{array}{ccc}Q& \ge & \left({a}_{r-2}{a}_{t-r-1}-{a}_{r-3}{a}_{t-r}\right){\mu }^{2}+\left({\lambda }^{2}{a}_{r-1}+2\lambda \mu {a}_{r-2}+{\mu }^{2}{a}_{r-3}\right){a}_{t-r}\end{array}$
 $\begin{array}{ccc}& & -\left(\lambda {a}_{r-1}+\mu {a}_{r-2}\right)\left(\lambda {a}_{t-r}+\mu {a}_{t-r-1}\right)\end{array}$
 $\begin{array}{ccc}& =& -\left({a}_{r-1}{a}_{t-r-1}-{a}_{r-2}{a}_{t-r}\right)\lambda \mu \end{array}$
by ( 3.10 ). Also, note that ${a}^{*}\left(n,k\right)={\mathfrak{L}}^{n}\left[\mu ,\lambda \right]\left({u}_{-k}\right)$  . Again by Remark  3.6 ,  $\begin{array}{ccc}{A}_{n-t+r+1}^{*}\left(n,2n-t+2\right)& \ge & \left[{a}^{*}\left(n-1,n-t+r\right){a}^{*}\left(n-1,n-r\right)\end{array}$
 $\begin{array}{ccc}& & -{a}^{*}\left(n-1,n-t+r-1\right){a}^{*}\left(n-1,n-r+1\right)\right]{\lambda }^{2}\end{array}$
 $\begin{array}{ccc}& =& \left({a}_{r-1}{a}_{t-r-1}-{a}_{r-2}{a}_{t-r}\right){\lambda }^{2}.\end{array}$
Finally, recall that the sequence $\left\{{a}_{k}{\right\}}_{k\in \mathbb{Z}}$  is log-concave, so for $r\le ⌊t/2⌋$  , $E={a}_{r-1}{a}_{t-r-1}-{a}_{r-2}{a}_{t-r}\ge 0,$  as required. This completes our proof.
Remark 3.11. Let $\left\{a\left(n,k\right)\right\}$  and $\left\{{a}^{\prime }\left(n,k\right)\right\}$  be the double LC-positive triangles in Proposition  3.5 and  3.8 respectively. Although the triangle $\left\{a\left(n,k\right){a}^{\prime }\left(n,k\right)\right\}$  is not double LC-positive in general, it is double PLC from Proposition  3.10 .
References

1. F. Brenti, Unimodal, log-concave, and Pólya frequency sequences in combinatorics, Mem. Amer. Math. Soc. no. 413 (1989). MR 0963833 (90d:05014)
2. F. Brenti, Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update, Contemp. Math. 178 (1994), 71-89. MR 1310575 (95j:05026)
3. L. M. Butler, The $q$  -log-concavity of $q$  -binomial coefficients, J. Combin. Theory Ser. A 54 (1990), 54–63. MR 1051778 (91c:05023)
4. H. Davenport and G. Pólya, On the product of two power series, Canadian J. Math. 1 (1949), 1–5. MR 0027306 (10,286b)
5. R. Ehrenborg and E. Steingrímsson, The excedance set of a permutation, Adv. Appl. Math. 24 (2000), 284–299. MR 1751147 (2001e:05003)
6. C. Krattenthaler, On the $q$  -log-concavity of Gaussian binomial coefficients, Monatsh. Math. 107 (1989), 333–339. MR 1012464 (90j:05027)
7. S. Karlin, Total Positivity, Vol.I, Stanford University Press, 1968. MR 0230102 (37 #5667)
8. D. C. Kurtz, A note on concavity properties of triangular arrays of numbers, J. Combin. Theory Ser. A 13 (1972), 135-139. MR 0304296 (46 #3431)
9. P. Leroux, Reduced matrices and $q$  -log-concavity properties of $q$  -Stirling numbers, J. Combin. Theory Ser. A 54 (1990), 64–84. MR 1051779 (91c:05024)
10. T. M. Liggett, Ultra logconcave sequence and negative dependence, J. Combin. Theory Ser. A 79 (1997), 315-325. MR 1462561 (98j:60018)
11. K. V. Menon, On the convolution of logarithmically concave sequences, Proc. Amer. Math. Soc. 23 (1969), 439–441. MR 0246012 (39 #7318)
12. R. Pemantle, Towards a theory of negative dependence, J. Math. Phys. 41 (2000), 1371–1390. MR 1757964 (2001g:62039)
13. B. E. Sagan, Inductive and injective proofs of log concavity results, Discrete Math. 68 (1988), 281-292. MR 0926131 (89b:05009)
14. B. E. Sagan, Inductive proofs of $q$  -log concavity, Discrete Math. 99 (1992), 289–306. MR 1158792 (93e:05004)
15. B. E. Sagan, Log concave sequences of symmetric functions and analogs of the Jacobi-Trudi determinants, Trans. Amer. Math. Soc. 329 (1992), 795–811. MR 1066448 (92e:05121)
16. R. P. Stanley, Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Ann. New York Acad. Sci. 576 (1989), 500–534. MR 1110850 (92e:05124)
17. D. W. Walkup, Pólya sequences, binomial convolution and the union of random sets, J. Appl. Probability 13 (1976), 76–85. MR 0494391 (58 #13258)
18. Y. Wang, A simple proof of a conjecture of Simion, J. Combin. Theory Ser. A 100 (2002), 399–402. MR 1940344 (2003i:05016)
19. Y. Wang, Proof of a conjecture of Ehrenborg and Steingrímsson on excedance statistic, European J. Combin. 23 (2002), 355–365. MR 1908656 (2004c:05016)
20. Y. Wang, Linear transformations preserving log-concavity, Linear Algebra Appl. 359 (2003), 162–167. MR 1948441 (2003m:15009)
21. Y. Wang and Y.-N. Yeh, Polynomials with real zeros and Pólya frequency sequences, J. Combin. Theory Ser. A 109 (2005), 63–74. MR 2110198
22. Y. Wang and Y.-N. Yeh, Proof of a conjecture on unimodality, European J. Combin. 26 (2005), 617–627.
23. H. S. Wilf, Generatingfunctionology, 2nd ed., Academic Press, Boston, 1994. MR 1277813 (95a:05002)

Department of Applied Mathematics, Dalian University of Technology, Dalian 116024, China Current address : Institute of Mathematics, Academia Sinica, Taipei 11529, Taiwan E-mail address : wangyi@dlut.edu.cn Institute of Mathematics, Academia Sinica, Taipei 11529, Taiwan E-mail address : mayeh@math.sinica.edu.tw