More Like this

1. On Uniform Convergence of Diagonal Multipoint Pad� Approximants For Entire Functions

   Lubinsky, Doron S (January 2019, Constructive approximation)

   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. Algebraic stability of meromorphic maps descended from Thurston’s pullback maps

   https://doi.org/10.1090/tran/8221  

   Ramadas, Rohini (January 2021, Transactions of the American Mathematical Society)

   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. Efficient Computation of a Semi-Algebraic Basis of the First Homology Group of a Semi-Algebraic Set

   https://doi.org/10.1007/s00454-024-00626-0  

   Basu, Saugata; Percival, Sarah (September 2024, Discrete & Computational Geometry)

   Let $$\R$$ be a real closed field and $$\C$$ the algebraic closure of $$\R$$. We give an algorithm for computing a semi-algebraic basis for the first homology group, $$\HH_1(S,\mathbb{F})$$, with coefficients in a field $$\FF$$, of any given semi-algebraic set $$S \subset \R^k$$ defined by a closed formula. The complexity of the algorithm is bounded singly exponentially. More precisely, if the given quantifier-free formula involves $$s$$ polynomials whose degrees are bounded by $$d$$, the complexity of the algorithm is bounded by $$(s d)^{k^{O(1)}}$$. This algorithm generalizes well known algorithms having singly exponential complexity for computing a semi-algebraic basis of the zero-th homology group of semi-algebraic sets, which is equivalent to the problem of computing a set of points meeting every semi-algebraically connected component of the given semi-algebraic set at a unique point. It is not known how to compute such a basis for the higher homology groups with singly exponential complexity. As an intermediate step in our algorithm we construct a semi-algebraic subset $$\Gamma$$ of the given semi-algebraic set $$S$$, such that $$\HH_q(S,\Gamma) = 0$$ for $q=0,1$. We relate this construction to a basic theorem in complex algebraic geometry stating that for any affine variety $$X$$ of dimension $$n$$, there exists Zariski closed subsets \[ Z^{(n-1)} \supset \cdots \supset Z^{(1)} \supset Z^{(0)} \] with $$\dim_\C Z^{(i)} \leq i$, and $$\HH_q(X,Z^{(i)}) = 0$$ for $$0 \leq q \leq i$$. We conjecture a quantitative version of this result in the semi-algebraic category, with $$X$$ and $$Z^{(i)}$$ replaced by closed semi-algebraic sets. We make initial progress on this conjecture by proving the existence of $$Z^{(0)}$$ and $$Z^{(1)}$$ with complexity bounded singly exponentially (previously, such an algorithm was known only for constructing $$Z^{(0)}$$). 

   more » « less
4. Fast Multivariate Multipoint Evaluation Over All Finite Fields

   https://doi.org/10.1109/FOCS54457.2022.00028  

   Bhargava, Vishwas; Ghosh, Sumanta; Guo, Zeyu; Kumar, Mrinal; Umans, Chris (October 2022, IEEE)

   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
5. A Geometric Approach to Polynomial and Rational Approximation

   https://doi.org/10.1093/imrn/rnae082  

   Bishop, Christopher J; Lazebnik, Kirill (April 2024, International Mathematics Research Notices)

   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