Revisions - MathOverflow

Return to Answer

Improve case coverage

view source

edited Jul 22 2010 at 19:05

Ryan Reich
4,010●1●11●25

Each $b_n$ is a linear combination of $a_0, \dots, a_n$; i.e. we have an upper-triangular infinite matrix $F$, not depending on $a_n$, such that (writing $\vec{a} = (a_n), \vec{b} = (b_n)$) $\vec{b} = F \vec{a}$. $F$ is injective, since if Suppose for now that $F p(0), r'(0) \vec{a} = neq 0$; then $p(x) A(r(x)) = 0$F$ has a nonzero diagonal, and so $p(x) = r(x) = 0$. Since its rows are finite, this means that it is invertible.

Now we remove the assumptions that $p(0), r'(0) \neq 0$. If $x^k$ divides $p(x)$, then replacing $p(x)$ by $p(x)/x^k$ does not change positivity of the coefficients. Now suppose the bottom exponent of $r(x)$ is $x^m$ with positive coefficient; then in $\mathbb{R}[[x]]$ we can write $r(x) = s(x)^m$, and if we denote $A_m(x) = A(x^m)$, we have $A(r(x)) = A_m(s(x))$. Clearly, $A_m$ has nonnegative coefficients if and only if $A$ does, and $s'(0) \neq 0$, so the previous proof applies and $s(x)$ is a multiple of $x$, i.e. $r(x)$ is a multiple of $x^m$, and $p(x)$ is a multiple of $x^k$.

Rewrite and change conclusion

view source

edited Jul 22 2010 at 13:51

Ryan Reich
4,010●1●11●25

I sort of worked

It is impossible, and not just for rational functions. To see thisout as I wrote it, so the answer is at let's consider the bottom. Consider it a whodunnit coefficients $b_n$ of sorts.

Let us do some explicit computations. Suppose $p(x) = \sum_{n \geq 0} p_n x^n$ and A(r(x))$ as functions of the $r(x) = \sum_{n \geq 0} r_n x^n$, with a_n$, the coefficients of $r_0 A(x)$. Since $r(0) = 0$ . Now, (as it must be) we just grindsee that:

Each $p(x) A(r(x)) = (\sum_k p_k x^k) \sum _n a_n (\sum_l r_l x^l)^n = b_n$ is a linear combination of $a_0, \sum_n a_n (\sum_k p_k x^k) dots, a_n$; i.e. we have an upper-triangular infinite matrix $F$, not depending on $a_n$, such that (\sum_l r_l x^l)^n$writing $\vec{a} = \sum_n a_n \sum_m (\sum_{k + l_1, \dots, l_n = m} p_k r_{l_1} a_n), \dots r_{l_n}) x^m vec{b} = \sum_m (\sum_n f(m,n) a_n) x^m$,

where I have written b_n)$) $f(m,n) = \sum_{k + l_1, \dots, l_n \vec{b} = m} p_k r_{l_1} F \dots r_{l_n}$. I require only one fact: $f(m,n) = 0$ if vec{a}$. $n > m$F$ is injective, since $r_0 = 0$. Thus, if we write $F \vec{a} = [f(m,n)]$ as an infinite upper-triangular matrix and 0$ then $\bar{a} p(x) A(r(x)) = [a_n]$ as an infinite column vector0$, we have so $p(x) A(r(x)= r(x) = \sum_m (F \bar{a})_m x^m$0$. You seek the condition:Since its rows are finite, this means that it is invertible.

If $F \bar{a} = \vec{b} \bar{b}$ (equivalently, geq 0$ for all $\bar{a} = F^{-1} \vec{a} \bar{b}$), geq 0$, then the entries in particular this is true of $\bar{a}$ are nonnegative if and only if those the columns of $\bar{b}$ are.

Choosing $\bar{a}$ and F$, taking $\bar{b}$ \vec{a}$ to be the infinite "basis" vectors. Conversely, we see have equivalently that $\vec{a} = F^{-1} \vec{b}$, so if $\vec{a} \geq 0$ for all $\vec{b} \geq 0$ this means that must be true of the entries columns of $F^{-1}$. We conclude that both $F$ and $F^{-1}$ are necessarily all have nonnegative entries.It is easy (for me

Lemma in linear algebra: ) ) to prove by induction that if $F$ is therefore diagonal (with positive entries there).

How can this happen? We must upper-triangular and both it and $F^{-1}$ have nonnegative real entries, then $\sum_{k + l_1 + \dots + l_n = m} p_k r_{l_1} \dots r_{l_n} = 0$ if F$ is diagonal. Proof by induction: true for $m 1 \neq n$times 1$ matrices vacuously. In general, by induction we may assume that the upper-left and $> 0$ if lower-right $(n - 1) \times (n = m$.

For - 1)$ blocks of $m = n$F$ are diagonal, we get $p_0 r_1^n > 0$ for all $n$, so only the $p_0, r_1 > 0$.

For (1,n)$ entry of $m = n + 1$, F$ is nonzero off the diagonal. Then we get $p_1 r_1^n + p_0 r_1^{n - 1} r_2 = 0$, and therefore have $r_2 (F^{-1})_{1n} = -(p_1/p_0) r_1$F_{1n} F_{nn}/F_{11}$.

For $m = n + 2$, we get Since $p_2 r_1^n + p_1 r_1^{n - 1} r_2 + p_0(r_1^{n - 1} r_3 + r_1^{n - 2} r_2^2) = 0$, F_{11}$ and we observe the occurrence of $(p_1 r_1 + p_0 r_2)r_1^{n - 2} r_2 = f(n + 1F_{nn}$ are both positive, n)r_1^{-1} r_2 = $F_{1n}, (F^{-1})_{1n} \geq 0$ , which we eliminate to obtain implies $p_2 r_1^n + p_0 r_1^{n - 1} r_3 F_{1n} = 0$.Solving

This is also true of infinite matrices, since we get $r_3 = -(p_2/p_0) r_1$can compute the finite upper-left blocks independently of the rest of the matrix.

More generally

However, if $F$ is diagonal then we (or I, at any rate) havesee that $f(n + k, n) p(x)A(r(x)) = p_k r_1^n + \sum_{i = 1}^{k - 1} f(n + i, nsum a_n p(x) r_1^{-1} r_{k - i + 1} + p_0 r_1^{n - 1r(x)^n = \sum F_{nn} r_{k + 1}$,a_n x^n$ for all choices of $a_n$, so by induction we have (for example, taking $r_{k + 1} a_n = -(p_k/p_0) r_1$. It follows that:

The pairs of functions t^n$ for a new variable $p(x), r(x)$ answering your question are exactly those of the form t$ and rewriting both sides as power series in $t$) we have $p(x) r(x)^n = p_0(1 + xq(x))$F_{nn} x^n$ for all $n$ (and some $F_{nn} > 0$). That is, $r(x) (r(x)/x)^n = r_1(x - x^2q(x))$ with F_{nn} p(x)^{-1}$ for all $p_0, r_1 > 0$n$, so in fact $r(x)/x = F_{11}/F_{00}$ is constant, and finally, $q(x) \in \mathbb{Q}[[x]]$.p(x)$ is constant as well.

Fix an index

view source

edited Jul 22 2010 at 5:48

Ryan Reich
4,010●1●11●25

I sort of worked this out as I wrote it, so the answer is at the bottom. Consider it a whodunnit of sorts.

Let us do some explicit computations. Suppose $p(x) = \sum_{n \geq 0} p_n x^n$ and $r(x) = \sum_{n \geq 0} r_n x^n$, with $r_0 = 0$. Now, we just grind:

$p(x) A(r(x)) = (\sum_k p_k x^k) \sum _n a_n (\sum_l r_l x^l)^n = \sum_n a_n (\sum_k p_k x^k) (\sum_l r_l x^l)^n$

$= \sum_n a_n \sum_m (\sum_{k + l_1, \dots, l_n = m} p_k r_{l_1} \dots r_{l_n}) x^m = \sum_m (\sum_n f(m,n) a_n) x^m$,

where I have written $f(m,n) = \sum_{k + l_1, \dots, l_n = m} p_k r_{l_1} \dots r_{l_n}$. I require only one fact: $f(m,n) = 0$ if $n > m$, since $r_0 = 0$. Thus, if we write $F = [f(m,n)]$ as an infinite upper-triangular matrix and $\bar{a} = [a_n]$ as an infinite column vector, we have $p(x) A(r(x)) = \sum_m (F \bar{a})_m x^m$. You seek the condition:

If $F \bar{a} = \bar{b}$ (equivalently, $\bar{a} = F^{-1} \bar{b}$), then the entries of $\bar{a}$ are nonnegative if and only if those of $\bar{b}$ are.

Choosing $\bar{a}$ and $\bar{b}$ to be the infinite "basis" vectors, we see that this means that the entries of $F$ and $F^{-1}$ are necessarily all nonnegative. It is easy (for me :) ) to prove by induction that $F$ is therefore diagonal (with positive entries there).

How can this happen? We must have

$\sum_{k + l_1 + \dots + l_n = m} p_k r_{l_1} \dots r_{l_n} = 0$ if $m \neq n$, and $> 0$ if $n = m$.

For $m = n$, we get $p_0 r_1^n > 0$ for all $n$, so $p_0, r_1 > 0$.

For $m = n + 1$, we get $p_1 r_1^n + p_0 r_1^{n - 1} r_2 = 0$, and therefore $r_2 = -(p_1/p_0) r_1$.

For $m = n + 2$, we get $p_2 r_1^n + p_1 r_1^{n - 1} r_2 + p_0(r_1^{n - 1} r_3 + r_1^{n - 2} r_2^2) = 0$, and we observe the occurrence of $(p_1 r_1 + p_0 r_2)r_1^{n - 2} r_2 = f(n + 1, n)r_1^{-1} r_2 = 0$, which we eliminate to obtain $p_2 r_1^n + p_0 r_1^{n - 1} r_3 = 0$. Solving, we get $r_3 = -(p_2/p_0) r_1$.

More generally, we (or I, at any rate) have

$f(n + k, n) = p_k r_1^n + \sum_{i = 1}^{k - 1} f(n + i, n) r_1^{-1} r_{i r_{k - i + 1} + p_0 r_1^{n - 1} r_{k + 1}$,

so by induction we have $r_{k + 1} = -(p_k/p_0) r_1$. It follows that:

The pairs of functions $p(x), r(x)$ answering your question are exactly those of the form $p(x) = p_0(1 + xq(x))$, $r(x) = r_1(x - x^2q(x))$ with $p_0, r_1 > 0$, and $q(x) \in \mathbb{Q}[[x]]$.

view source

answered Jul 22 2010 at 5:09

Ryan Reich
4,010●1●11●25

I sort of worked this out as I wrote it, so the answer is at the bottom. Consider it a whodunnit of sorts.

Let us do some explicit computations. Suppose $p(x) = \sum_{n \geq 0} p_n x^n$ and $r(x) = \sum_{n \geq 0} r_n x^n$, with $r_0 = 0$. Now, we just grind:

$p(x) A(r(x)) = (\sum_k p_k x^k) \sum _n a_n (\sum_l r_l x^l)^n = \sum_n a_n (\sum_k p_k x^k) (\sum_l r_l x^l)^n$

$= \sum_n a_n \sum_m (\sum_{k + l_1, \dots, l_n = m} p_k r_{l_1} \dots r_{l_n}) x^m = \sum_m (\sum_n f(m,n) a_n) x^m$,

If $F \bar{a} = \bar{b}$ (equivalently, $\bar{a} = F^{-1} \bar{b}$), then the entries of $\bar{a}$ are nonnegative if and only if those of $\bar{b}$ are.

How can this happen? We must have

$\sum_{k + l_1 + \dots + l_n = m} p_k r_{l_1} \dots r_{l_n} = 0$ if $m \neq n$, and $> 0$ if $n = m$.

For $m = n$, we get $p_0 r_1^n > 0$ for all $n$, so $p_0, r_1 > 0$.

For $m = n + 1$, we get $p_1 r_1^n + p_0 r_1^{n - 1} r_2 = 0$, and therefore $r_2 = -(p_1/p_0) r_1$.

More generally, we (or I, at any rate) have

$f(n + k, n) = p_k r_1^n + \sum_{i = 1}^{k - 1} f(n + i, n) r_1^{-1} r_{i + 1} + p_0 r_1^{n - 1} r_{k + 1}$,

so by induction we have $r_{k + 1} = -(p_k/p_0) r_1$. It follows that:

The pairs of functions $p(x), r(x)$ answering your question are exactly those of the form $p(x) = p_0(1 + xq(x))$, $r(x) = r_1(x - x^2q(x))$ with $p_0, r_1 > 0$, and $q(x) \in \mathbb{Q}[[x]]$.