User neil dickson - MathOverflow

Can Convergence Radii of Padé Approximants Always Be Made Infinite?

2010-08-30T08:09:42Z

I've found (as have others), that for some analytic functions, a Padé approximant of it has an infinite convergence radius, whereas its associated Taylor series has a finite convergence radius. $f(x)=\sqrt{1+x^2}$ appears to be one such function. My questions are:

1) Is there any function where the Taylor series has the largest convergence radius of all associated Padé approximants? If so, is the Taylor series radius strictly larger, or only equal to the convergence radius of other Padé approximants (i.e. excluding the Taylor series itself)?

2) If not, is there any function that is analytic everywhere, and yet for which there is no (limit of) Padé approximant(s) that has an infinite convergence radius?

It would be both very cool and very useful if there is always a (limit of) Padé approximant(s) that has an infinite convergence radius for any function that is analytic everywhere, though I haven't the slightest how one checks/analyzes convergence of Padé approximants if the degrees of numerator and denominator both approach infinity. :)

One extra question, if there is always such a Padé approximant:

3) Is there always a numerically stable method of computing this approximant up to a finite order?

Answer by Neil Dickson for Simple/efficient representation of Stirling numbers of the first kind

2010-08-30T06:32:29Z

If Stirling numbers of the first kind are the numbers associated with the Stirling series, if there is a "sufficiently simple-to-compute" representation of them, you can factor integers in time polynomial in the number of their bits, using a simple property presented in a blog post by Richard Lipton and a particular rational/exponential approximation to $n!$ that's based on the Stirling series. I spent some time looking for such a representation once, without any luck, though.

It's believed by many that there is no such algorithm to factor integers, (although Richard has written several posts suggesting that it's still rather uncertain), so if they're right, there is no "sufficiently simple-to-compute" representation of the Stirling numbers of the first kind.

Answer by Neil Dickson for Asymptotic growth of a certain integer sequence

2010-08-29T11:25:27Z

While I have no idea how to put an upper bound on it, I seem to have at least found a loose linear lower bound. I started by noticing that it takes a sufficiently large $k$ for $k^n$ to be smaller than the sum of the smaller numbers in the set. If the entire rest of the set can't sum to equal that one element, there clearly can't be an equal partition.

Since you've shown that there is always a solution, for a given $n$, there is some smallest integer $k^\star$ such that:

$\sum_{i=1}^{k^\star-1} i^n \ge k^{\star n}$

Since $k^\star$ is the smallest such integer,

$\sum_{i=1}^{k^\star-2} i^n < (k^\star-1)^n$

and therefore:

$2 (k^\star-1)^{n} > \sum_{i=1}^{k^\star-1} i^n \ge k^{\star n}$

For n>0, this gives:

$2^{1/n} > \frac{k^*}{k^\star-1}$

$2^{-1/n} < 1-\frac{1}{k^\star}$

$k^\star > \frac{1}{1-2^{-1/n}} = \sum_{i=0}^{\infty}2^{-i/n} > \frac{n}{2} + 1$

(My apologies if the latex doesn't parse correctly, the preview seems to show it only some of the time.)

Comment by Neil Dickson

2010-09-09T07:58:01Z

While I completely agree that it is uncommon for undergraduates to publish any papers, and nobody here has explicitly discouraged publication of this work, I would strongly encourage wider publishing of undergraduate work. As with this case, undergraduates are often quite interdisciplinary in their research, which has been greatly lacking in some fields. For example, in quantum computing, many publications disregard basic concepts of physics, whereas many other publications disregard basic concepts of computer science. A fresh perspective could help bring fields together.

Comment by Neil Dickson

2010-09-09T07:23:21Z

Touché about the example I gave. It is quite odd and curious that I've been working lately with a ton of such functions whose Padé approximants appear to have infinite convergence along the real axis, but clearly do not converge infinitely along the imaginary axis. I suppose I shouldn't be too surprised, since they come from recursively applying a real, non-negative perturbation to rational functions. However, I was expecting that, like with the Taylor series of them, the rational perturbation would only be valid up to a finite value of the parameter. Anyway, I'm just rambling now.

Comment by Neil Dickson

2010-09-09T07:09:05Z

Thanks for the insights! It seems reasonable that if M is fixed, there would be some function for which the approximant sequence doesn't fully converge. It's very interesting that it also happens for M=L on some function.

Comment by Neil Dickson

2010-08-31T05:40:03Z

Touché. :) <a href="en.wikipedia.org/wiki/… are related, of course,</a> but probably not enough to make my above assertion.

Comment by Neil Dickson

2010-08-29T20:49:50Z

Yep, that's correct! The Lagrange-Bürmann formula specifically, but as you noted above, someone else already pointed that out on sci.math. Thanks a bunch anyway! :) I'll have to make my future contests harder, haha.

Comment by Neil Dickson

2010-08-29T20:35:30Z

While that is a general formula for <i>any</i> composition of two functions, I'd already worked that much out. What I'd like is proof whether or not the formula I listed above is equivalent to that for the case of the less general composition $f(xg(x))$. That's the part I spent a few days on before giving up. :)