Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This started when I was examining certain families of unimodal polynomials, i.e. $\sum_{k=0}^n a_kx^k$ where $a_0\le a_1\le\cdots \le a_k\ge\cdots \ge a_n$.
(Notation: in the following, the $a_k$ depend on $n$, but writing $a_k$ instead of $a_{k,n}$ makes it easier to read.)

If for a given $n$, we display the coefficients of $f_n=f_n(x)=\sum_{k=0}^n a_kx^k$ as points $(k,a_k)$ defining a graph (say, with linear segments between) and normalize it such that it maximally fits into the rectangle with corners $(\pm1,0)$ and $(\pm1,1)$, then, as $n$ grows, for many of the "classical" families, the shapes of these graphs ressemble more or less a "Gaussian bell curve" with width $\sigma$ proportional to $1/\sqrt{n}$. So it makes sense to look at the "log graph" $\lbrace(k,\ln|a_k|)\rbrace$ instead, which we will again scale to fit into the same rectangle. This scaling "filters" out $\sigma$, and even though the coefficients normally don't yield exactly Gaussian distributions (thus no "Central limit theorem" here),

for many, if not all, of the classical families of polynomials, as $n\to\infty$, these log graphs converge to a well-defined limit curve, i.e. to the graph of a function $L:[-1,1]\to\mathbb [0,1]$.

(Note that we will extend this "log graph" definition to even and odd polynomials by displaying only the non-zero coefficients.)

An easy example is $f_n(x)=(1+x)^n$, i.e. the binomial coefficients. By Stirling's formula, we find for the limit function, after scaling,

$L(x)={\ln\left[\left(\dfrac{1+x}2\right)^{\frac{1+x}2} \left(\dfrac{1-x}2\right)^{\frac{1-x}2}\right]} \Bigl/ {\ln(\dfrac12)}=\dfrac1{\ln4}\left(\ln\dfrac4{1-x^2}+x\ln\dfrac{1-x}{1+x}\right),$

which is the red curve about half way between the parabola $y=1-x^2$ (blue - would correspond to a "Gaussian bell curve" for the $a_k$) and the upper half of the unit circle (pink). Click here for a picture.

  • Or consider the Legendre and both kinds of Chebyshev polynomials (ignoring the zero coefficients). Again by Stirling's formula, for each of the three families, we obtain the same limit curve

$L(x)=\dfrac{(x+3) \ln(x+3)-(1-x) \ln(1-x)-2 (x+1) \ln(x+1) }{4\ln(1+\sqrt{2})}.$

This is the green curve above, which has its maximum at $x=\sqrt{2}-1$ and $\lim\limits_{x\to1}L(x)=\dfrac{\ln2}{\ln(1+\sqrt{2})}\approx0.7864397.$ The convergence is numerically rather rapid.

  • More generally, it seems in fact that all Jacobi polynomials $P_n^{(\alpha,\beta)}(x)$ for fixed $\alpha,\beta\in\mathbb R$ yield this same limit curve as $n\to\infty$, independently of $\alpha$ and $\beta$.

  • Doing the same with the Hermite polynomials (again ignoring the zero coefficients) or the Bell polynomials, the convergence is much slower, as displayed below, so the limit curve is more difficult to guess due to limited computer power. I think for both the limit is nothing but the green line $y=\dfrac{1-x}2$.

IMG]http://imageshack.us/a/img706/1300/bellhermite.png[/IMG

  • If we take the above classical polynomials but shift their zeros by a constant, e.g. in PARI using $\mathtt{subst(pollegendre(n,x),x,x+1)}$, or more generally, replacing $x$ by a certain fixed polynomial, it seems like the curves converge quite rapidly, the result depending of course of this fixed polynomial. The next illustration shows e.g. what happens for the Chebyshev polynomials with $x$ replaced by $x^2-10x-10$. The $n=250$ curve showed here has no visible difference with the $n=125$ curve. image

  • The same sort of convergence happens if $f_n$ is defined by its zeros, all real, with fixed proportions of zeros randomly chosen in certain fixed intervals; e.g. in the next image for $n=200$, where $f_n$ is of degree $2n$ with $n$ zeros randomly taken in $[-50,0]$ and $n$ zeros in $[0,1]$. image

So far this is nothing very spectacular, but it is an interesting observation that in all these cases, the limit curve is concave.
This still seems to hold if $f_n$ is any "combination" of the above, as defined more formally below, including the possibility for the parameters, like $\alpha$ and $\beta$ for the Jacobi polynomials, to also depend on $n$.
On the other hand, it all breaks down if we admit e.g. the cyclotomic polynomials $\Phi_n(x)$. Well, unlike the "classical" families of polynomials, these cannot be recursively defined by, say, a three-term recurrence, and I'm wondering if this recursiveness is linked to the log-concavity of "$\lim\limits_{n\to\infty}f(n)$". So the question in its general form:

Let $f_n=P(g_1,...,g_k)$, where $P$ is a fixed multivariate polynomial and $g_1,...,g_k$ are polynomials (in $x$ or in fixed polynomials of $x$, as above) belonging to the classical families (meaning, to any family defined by a three-term recurrence) and depending on $n$. Then, as $n\to\infty$, does the limit curve of the log graph of $f_n$'s coefficients always exist, and moreover, is it always concave?

share|improve this question

1 Answer 1

up vote 5 down vote accepted

I can explain a lot of what you are seeing.

(1) If $f(x)$ has negative real roots, then the coefficients of $f$ are always log concave. Proof: Let $f(x) = \prod (x+\lambda_i)$. Then the coefficients of $f$ are the elementary symmetric polynomials $e_k(\lambda_1, \lambda_2, \ldots, \lambda_n)$. The elementary symmetric polynomials obey Newton's inequalities.

(2) Set $s(a)$ and $t(a)$ be concave functions. I don't know how to make the bounds in what I'm about to say rigorous, so I'll just say everything in the approximate sense. Suppose that $f_n(x) = \sum_{k=0}^n f_{k,n} x^k$ is a family of polynomials with $f_{k,n} \approx e^{n \cdot s(k/n)}$ and that $g_n(x)$ is a similar family of polynomials with $g_{k,n} \approx e^{n \cdot t(k/n)}$. Set $h_n(x) = f_n(x) g_n(x)$. Then the coefficient of $x^{2k}$ in $h$ is $$\sum_{\ell=0}^{2k} f_{\ell,n} g_{2k-\ell,n} \approx \sum_{\ell=0}^{2k} e^{n \cdot ( s(\ell/n) + t((2k-\ell)/n) )}$$ $$ \approx \exp( n \cdot \max_{\ell} (s(\ell/n) + t((2k-\ell)/n) )\approx \exp(n \max_{0 \leq a \leq 2k/n} s(a) + t(2k/n -a)) $$

If $s$ and $t$ are concave, then the function $$u(b) = \max_{0 \leq a \leq 2b} s(a) + t(2b-a)$$ is also concave. I think that's what you're seeing when you take "fixed proportions of zeros randomly chosen in certain fixed intervals": There is some limit curve for zeroes chosen uniformly in one interval, and choosing multiple intervals combines them by the above rule.

(3) Let $F(x,y) = \sum_n f_n(x) y^n$. If the singularities of $F$ are not too complicated, then there are good tools to extract the asymptotic behavior of the $f_{k,n}$, and those methods will "often" give convex curves of the sort you describe. I'll be more precise about what I mean by often.

$\def\CC{\mathbb{C}}$Let $\bar{U}$ be the set of $(x,y) \in \CC^2$ where $\sum f_{k,n} x^k y^n$ converges absolutely. Assume that $\bar{U}$ contains a neighborhood of $(0,0)$, and let $U$ be the interior of $\bar{U}$. Whether or not a point $(x,y)$ is in $U$ depends only on $(|x|, |y|)$. Let $D$ be the image of $U$ under $(x,y) \mapsto (\log |x|, \log |y|)$. Then $D$ is a convex set which obeys the property that $(u,v) \in D$, with $u' \leq u$ and $v' \leq v$ imply $(u', v') \in D$. See section 2 of these notes for much more.

For a positive number $a$, let $s(a) = - \sup_{(u,v) \in D} (au+v)$. Then it is often true that $\log f_{k,n} \approx n s(k/n)$. The function $\sup_{(u,v) \in D} (au+v)$ is (up to sign conventions) called the Legendre transform of the boundary of $D$.

What do I mean by often?

If we have a sequence $k_n$ with $k_n/n \to a$, it is always true that $\sup_{n \to \infty} \frac{1}{n} \log |f_{k_n,n}| \leq s(a)$. Proof: Choose $r>s(a)$. Then there is a point $(u,v) \in D$ with $au+v = -r$. Then $$f_{k_n,n} = \int_{|x| = u, |y|=v} F(x,y) x^{-k_n} y^{-n} \frac{dx dy}{x y}$$ An easy bound gives $f_{k_n, n} \leq C \exp (- k_n u - n v) = C \exp(- ((k_n/n) u +v) )$ for some constant $C$.

Conversely, suppose the following conditions hold: There is a single point $(u,v) \in \partial D$ where $au+v$ achieves its maximum. There is an open set $\Omega$ in $\CC^2$ containing the closed polydisc $\{ |x| \leq e^u,\ |y| \leq e^v \}$ such that $F$ extends to a meromorphic function on $\Omega$, with single simple pole along a divisor $\Delta \subset \Omega$. There is a single point $(x,y)$ in $\Delta$ with $(\log |x|, \log |y|) = (u,v)$, and this point is a smooth point of $\Delta$. With all these hypotheses (and perhaps some I have forgotten), $(1/n) \log |f_{k_n,n}| \to s(a)$. See Pemantle and Wilson, part 1. See also this paper where Pemantle and Wilson provide 20 applications of their method, including many of the examples you give.

If $F$ extends to a meromorphic function on some $\Omega$, but the pole set is more complicated, you need to read Pemantle and Wilson's later papers. See especially 2, 3.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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