We prove that for most entire functions f in the sense
of category, a strong form of the BakerGammelWills Conjecture
holds. More precisely, there is an inÖnite sequence S of positive
integers n, such that given any r > 0, and multipoint PadÈ approximants Rn to f with interpolation points in fz : jzj rg, fRngn2S
converges locally uniformly to f in the plane. The sequence S
does not depend on r, nor on the interpolation points. For entire
functions with smooth rapidly decreasing coe¢ cients, full diagonal
sequences of multipoint PadÈ approximants converge.
more »
« less
Exact Interpolation, Spurious Poles, and Uniform Convergence of Multipoint Pade Approximants
We prove that for most entire functions f in the sense of category, a strong form of the BakerGammelWills Conjecture holds. More precisely, there is an infinite sequence S of positive integers n, such that given any r>0, and multipoint Padé approximants R_{n} to f with interpolation points in {z:z≤r}, {R_{n}}_{n∈S} converges locally uniformly to f in the plane. The sequence S does not depend on r, nor on the interpolation points. For entire functions with smooth rapidly decreasing coefficients, full diagonal sequences of multipoint Padé approximants converge.
more »
« less
 Award ID(s):
 1800251
 NSFPAR ID:
 10092097
 Date Published:
 Journal Name:
 Sbornik : Mathematics
 Volume:
 209
 ISSN:
 14684802
 Page Range / eLocation ID:
 432448
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


null (Ed.)Let ϕ : S 2 → S 2 \phi :S^2 \to S^2 be an orientationpreserving branched covering whose postcritical set has finite cardinality n n . If ϕ \phi has a fully ramified periodic point p ∞ p_{\infty } and satisfies certain additional conditions, then, by work of Koch, ϕ \phi induces a meromorphic selfmap R ϕ R_{\phi } on the moduli space M 0 , n \mathcal {M}_{0,n} ; R ϕ R_{\phi } descends from Thurston’s pullback map on Teichmüller space. Here, we relate the dynamics of R ϕ R_{\phi } on M 0 , n \mathcal {M}_{0,n} to the dynamics of ϕ \phi on S 2 S^2 . Let ℓ \ell be the length of the periodic cycle in which the fully ramified point p ∞ p_{\infty } lies; we show that R ϕ R_{\phi } is algebraically stable on the heavylight Hassett space corresponding to ℓ \ell heavy marked points and ( n − ℓ ) (n\ell ) light points.more » « less

Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate multipoint evaluation over any finite field F that outputs the evaluations of an mvariate polynomial of degree less than d in each variable at N points in time (dm + N)1+o(1) · poly(m, d, log F) for all m ∈ N and all sufficiently large d ∈ N. A previous work of Kedlaya and Umans (FOCS 2008, SICOMP 2011) achieved the same time complexity when the number of variables m is at most d^{o(1)} and had left the problem of removing this condition as an open problem. A recent work of Bhargava, Ghosh, Kumar and Mohapatra (STOC 2022) answered this question when the underlying field is not too large and has characteristic less than d^{o(1)}. In this work, we remove this constraint on the number of variables over all finite fields, thereby answering the question of Kedlaya and Umans over all finite fields. Our algorithm relies on a nontrivial combination of ideas from three seemingly different previously knownalgorithms for multivariate multipoint evaluation, namely the algorithms of Kedlaya and Umans, that of Björklund, Kaski and Williams (IPEC 2017, Algorithmica 2019), and that of Bhargava, Ghosh, Kumar and Mohapatra, together with a result of Bombieri and Vinogradov from analytic number theory about the distribution of primes in an arithmetic progression. We also present a second algorithm for multivariate multipoint evaluation that is completely elementary and in particular, avoids the use of the Bombieri–Vinogradov Theorem. However, it requires a mild assumption that the field size is bounded by an exponentialtower in d of bounded height.more » « less

We strengthen the classical approximation theorems of Weierstrass, Runge, and Mergelyan by showing the polynomial and rational approximants can be taken to have a simple geometric structure. In particular, when approximating a function $f$ on a compact set $K$, the critical points of our approximants may be taken to lie in any given domain containing $K$, and all the critical values in any given neighborhood of the polynomially convex hull of $f(K)$.more » « less

The noise sensitivity of a Boolean function f: {0,1}^n  > {0,1} is one of its fundamental properties. For noise parameter delta, the noise sensitivity is denoted as NS_{delta}[f]. This quantity is defined as follows: First, pick x = (x_1,...,x_n) uniformly at random from {0,1}^n, then pick z by flipping each x_i independently with probability delta. NS_{delta}[f] is defined to equal Pr [f(x) != f(z)]. Much of the existing literature on noise sensitivity explores the following two directions: (1) Showing that functions with low noisesensitivity are structured in certain ways. (2) Mathematically showing that certain classes of functions have low noise sensitivity. Combined, these two research directions show that certain classes of functions have low noise sensitivity and therefore have useful structure. The fundamental importance of noise sensitivity, together with this wealth of structural results, motivates the algorithmic question of approximating NS_{delta}[f] given an oracle access to the function f. We show that the standard sampling approach is essentially optimal for general Boolean functions. Therefore, we focus on estimating the noise sensitivity of monotone functions, which form an important subclass of Boolean functions, since many functions of interest are either monotone or can be simply transformed into a monotone function (for example the class of unate functions consists of all the functions that can be made monotone by reorienting some of their coordinates [O'Donnell, 2014]). Specifically, we study the algorithmic problem of approximating NS_{delta}[f] for monotone f, given the promise that NS_{delta}[f] >= 1/n^{C} for constant C, and for delta in the range 1/n <= delta <= 1/2. For such f and delta, we give a randomized algorithm performing O((min(1,sqrt{n} delta log^{1.5} n))/(NS_{delta}[f]) poly (1/epsilon)) queries and approximating NS_{delta}[f] to within a multiplicative factor of (1 +/ epsilon). Given the same constraints on f and delta, we also prove a lower bound of Omega((min(1,sqrt{n} delta))/(NS_{delta}[f] * n^{xi})) on the query complexity of any algorithm that approximates NS_{delta}[f] to within any constant factor, where xi can be any positive constant. Thus, our algorithm's query complexity is close to optimal in terms of its dependence on n. We introduce a novel descendingascending view of noise sensitivity, and use it as a central tool for the analysis of our algorithm. To prove lower bounds on query complexity, we develop a technique that reduces computational questions about query complexity to combinatorial questions about the existence of "thin" functions with certain properties. The existence of such "thin" functions is proved using the probabilistic method. These techniques also yield new lower bounds on the query complexity of approximating other fundamental properties of Boolean functions: the total influence and the bias.more » « less