skip to main content

Attention:

The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 11:00 PM ET on Friday, July 12 until 2:00 AM ET on Saturday, July 13 due to maintenance. We apologize for the inconvenience.


Title: 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 Baker-Gammel-Wills 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
NSF-PAR ID:
10092097
Author(s) / Creator(s):
Date Published:
Journal Name:
Sbornik : Mathematics
Volume:
209
ISSN:
1468-4802
Page Range / eLocation ID:
432-448
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We prove that for most entire functions f in the sense of category, a strong form of the Baker-Gammel-Wills 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
  2. null (Ed.)
    Let ϕ : S 2 → S 2 \phi :S^2 \to S^2 be an orientation-preserving branched covering whose post-critical 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 self-map 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 heavy-light Hassett space corresponding to ℓ \ell heavy marked points and ( n − ℓ ) (n-\ell ) light points. 
    more » « less
  3. 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 m-variate 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 non-trivial 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 exponential-tower in d of bounded height. 
    more » « less
  4. 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
  5. 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 noise-sensitivity 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 descending-ascending 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