2
$\begingroup$

Question : Letting $k,n$ be positive integers, let's define a sequence $\{a_i\}\ (i=0,1,\cdots, kn)$ as $$(1+x+\cdots+x^k)^n=\sum_{i=0}^{kn}a_ix^i.$$ Then, is the 'special' difference-sequence $\{d^Na_i\}$ a unimodal sequence for every non-negative integer $N$? If the answer is yes, then prove that. If the answer is no, then find a counterexample.

Definition :

1. Let's call a sequence $\{a_i\}\ (i=0,1,\cdots,kn)$ which satisfies the following condition 'a unimodal sequence'.

Condition : $\ $There exists an integer $t$ such that $$a_0\le a_1\le \cdots\le a_t\ge a_{t+1}\ge a_{t+2}\ge\cdots.$$

2. Let's define $\{d^Na_i\}\ (N\in\mathbb N)$ as the following:

$$d^Na_i=\max(d^{N-1}a_i-d^{N-1}a_{i-1},0)\ \ \ (i=0,1,\cdots, kn),$$ $$d^0a_i=a_i, \ a_{-1}=0.$$

Please note that this is not an usual difference-sequence. (we may call this 'a special difference-sequence')

Motivation :

When I saw Pascal's triangle, I found this property about $a_i=\ _nC_i$. Then, I generalized this property.

Example : Let's see the $(k,n)=(1,8)$ case.

$$a_i(=d^0a_i) : 1\ \ 8\ \ 28\ \ 56\ \ 70\ \ 56\ \ 28\ \ 8\ \ 1$$

$$d^1a_i : 1\ \ 7\ \ 20\ \ 28\ \ 14\ \ 0\ \ 0\ \ 0\ \ 0$$

$$d^2a_i : 1\ \ 6\ \ 13\ \ 8\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0$$

$$d^3a_i : 1\ \ 5\ \ 7\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0$$

$$d^4a_i : 1\ \ 4\ \ 2\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0$$

$$d^5a_i : 1\ \ 3\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0$$

$$d^6a_i : 1\ \ 2\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0$$

$$d^7a_i : 1\ \ 1\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0$$

$$d^Na_i (N\ge 8): 1\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0\ \ 0$$

Hence, we can see that $\{d^N{_8C_i}\}\ (i=0,1,\cdots,8)$ is a unimodal sequence for every non-negative integer $N$.

Remark : This question has been asked previously on math.SE without receiving any complete answers: https://math.stackexchange.com/questions/492651/about-the-unimodality-of-the-coefficients-sequence-of-1x-cdotsxkn

The above definition about 'difference-sequences' might be somewhat unusual, but I won't change its definition. This is because this definition would keep the unimodality. If we define $d^Na_i=d^{N-1}a_i-d^{N-1}a_{i-1} (i=0,1,\cdots)$ as usual, then we get

$$d^1a_i : 1\ \ 7\ \ 20\ \ 28\ \ 14\ \ -14\ \ -28\ \ -20\ \ -7$$

in the above example, which is not unimodal.

$\endgroup$
  • $\begingroup$ Please change the title! What the title asks is standard stuff, what the body asks not, as far as I know. Also please use a different symbol than $\Delta$ for the truncated finite difference operator, in particular since you use that symbol before givin a non-standard definition of it; this is bound to confuse readers. $\endgroup$ – Marc van Leeuwen Sep 19 '13 at 9:17
  • $\begingroup$ @MarcvanLeeuwen: You are right. Thank you so much. $\endgroup$ – mathlove Sep 19 '13 at 9:35
8
$\begingroup$

UPDATE I now have a complete proof. I'll start with the Pascal's triangle case.

For any sequence of real numbers $r=(r_1, r_2, \ldots, r_k)$, define the number of sign changes of $r$ as follows: Delete all zeroes from $r$, then count how many times the signs of the resulting sequence changes. Recall that Descartes Rule of Signs says that the number of positive roots of $\sum f_k x^k$ is bounded by the number of sign changes of $(f_0, \ldots, f_k)$. My first lemma is a strengthening of Descartes Rule of Signs when all the roots are real.

Claim 1: Let $\sum f_k x^k$ be a polynomial all of whose roots all real. Let $p$ be the number of positive roots, counted with multiplicity. Then the sequence $f_k$ has precisely $p$ sign alternations.

Proof: See, for example, Theorem 1 here. $\square$

Claim 2: Let $f(x) = \sum f_k x^k$ be a polynomial all of whose roots are real. Suppose that $f_i$, $f_{i+1}$, $f_{i+2}$, ..., $f_j$ all have the same sign. Then $f_i$, $f_{i+1}$, ..., $f_j$ is unimodal.

Proof: Let $p$ be the number of positive roots of $f$. By Claim 1, $f_k$ has precisely $p$ sign changes. Define $\ell_0 \leq r_0 < \ell_1 \leq r_1< \ell_2 \leq r_2 < \cdots < \ell_p \leq r_p$ to be the unique indices such that $(-1)^i f_k \geq 0$ for $k \in [\ell_i, r_i]$, and $f_{\ell_i}$ and $f_{r_i}$ are not zero.

Define $g(x) = (1-x) f(x)$. So $g$ has $p+1$ positive roots, and all of its roots are real. Claim 1 tells us that $g_k$ has $p+1$ sign changes. Now, $(-1)^i g_{\ell_i} >0$ and $(-1)^i g_{r_i +1} < 0$. So $g_k$ has a sign change between $\ell_i$ and $r_{i}+1$ for each $i$. There are $p+1$ values of $i$ we can use, and $g_k$ has $p+1$ sign changes, so there must be only one sign change of $g_k$ in each interval $(\ell_i, r_{i}+1)$. Thus, $f$ is unimodal for $k$ in $[\ell_i, r_i]$. $\square$

Let $f(x) = (1+x)^m (1-x)^n$. Let $f_k$ be positive for $0 \leq k \leq r$. (So $r$ is $r_0$ in the terminology of the previous proof.) Since all the roots of $f$ are real, Claim 2 shows that $f_0$, $f_1$, ..., $f_r$ is unimodal. The sequence $(f_0, f_1, \ldots, f_r)$ is precisely $d^m \binom{n}{k}$ in the terminology of the question.


UPDATE I can now do the general case. For $f(x)$ a polynomial with real coefficients, let $V(f(x))$ denote the number of sign alternations of the coefficients of $f$.

Lemma $V((1-x) f(x)) \geq V(f(x))+1$.

Proof This is a standard lemma proved in the course of proving Descartes rule of signs. See, for example, this proof. $\square$

Lemma For $m \leq n$, we have $V((1+x+\cdots + x^k)^n (1-x)^m)=m$.

Proof Our proof is by reverse induction. For $m=n$, we have $(1+x+\cdots + x^k)^n (1-x)^m= (1-x^{k+1})^n$ which has $n$ sign alternations. Now assume the lemma for $m$ and we will show that it follows for $m-1$.

By the previous lemma, $V((1+x+\cdots + x^k)^n (1-x)^m) \geq V((1+x+\cdots + x^k)^n (1-x)^{m-1})+1$. So $V((1+x+\cdots + x^k)^n (1-x)^{m-1}) \leq m-1$. But also, $V((1+x+\cdots + x^k)^n (1-x)^{m-1}) \geq V((1+x+\cdots+x^k)^n)+m-1=m-1$. So $V((1+x+\cdots + x^k)^n (1-x)^{m-1})=m-1$ as desired. $\square$

The rest of the argument follows as before. We don't need to go past $m=n$ because, when $m=n$, the truncated partial difference sequence is already shortened to length $1$.

In fact, not only have we shown that these sequences are unimodal, we have shown that they are log convex. Set $h(x) = V((1+x+\cdots + x^k)^n (1-x)^m)$. We showed that the coefficients of $h$ are unimodal in any string of constant sign. But, in fact, the same argument shows $h(rx)$ has the same property for any $r>0$. Saying that $(h_i r^i, h_{i+1} r^{i+1}, \ldots, h_j r^j)$ is unimodal for all positive $r$ is the same as saying that $(h_i, h_{i+1}, \ldots, h_j)$ is log convex.

$\endgroup$
3
$\begingroup$

Yes, because convolutions of log-concave sequences are log-concave. Products of polynomials are convolutions of their coefficient sequence. Search on these keywords and you'll find tons of references.

$\endgroup$
  • $\begingroup$ This answers the question in the title, but not the one in the body. The title must be changed. $\endgroup$ – Marc van Leeuwen Sep 19 '13 at 9:15
  • $\begingroup$ @Brendan McKay : I'm sorry. My title was not what I would like to ask. $\endgroup$ – mathlove Sep 19 '13 at 9:36

Your Answer

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

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