skip to main content


Title: Super-polynomial accuracy of one dimensional randomized nets using the median of means

Letffbe analytic on[0,1][0,1]with|f(k)(1/2)|⩽<#comment/>Aα<#comment/>kk!|f^{(k)}(1/2)|\leqslant A\alpha ^kk!for some constantsAAandα<#comment/>>2\alpha >2and allk⩾<#comment/>1k\geqslant 1. We show that the median estimate ofμ<#comment/>=∫<#comment/>01f(x)dx\mu =\int _0^1f(x)\,\mathrm {d} xunder random linear scrambling withn=2mn=2^mpoints converges at the rateO(n−<#comment/>clog⁡<#comment/>(n))O(n^{-c\log (n)})for anyc>3log⁡<#comment/>(2)/π<#comment/>2≈<#comment/>0.21c> 3\log (2)/\pi ^2\approx 0.21. We also get a super-polynomial convergence rate for the sample median of2k−<#comment/>12k-1random linearly scrambled estimates, whenk/mk/mis bounded away from zero. Whenffhas app’th derivative that satisfies aλ<#comment/>\lambda-Hölder condition then the median of means has errorO(n−<#comment/>(p+λ<#comment/>)+ϵ<#comment/>)O( n^{-(p+\lambda )+\epsilon })for anyϵ<#comment/>>0\epsilon >0, ifk→<#comment/>∞<#comment/>k\to \inftyasm→<#comment/>∞<#comment/>m\to \infty. The proof techniques use methods from analytic combinatorics that have not previously been applied to quasi-Monte Carlo methods, most notably an asymptotic expression from Hardy and Ramanujan on the number of partitions of a natural number.

 
more » « less
Award ID(s):
2152780
NSF-PAR ID:
10513780
Author(s) / Creator(s):
;
Publisher / Repository:
American Mathematical Society
Date Published:
Journal Name:
Mathematics of Computation
Volume:
92
Issue:
340
ISSN:
0025-5718
Page Range / eLocation ID:
805 to 837
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. We show that for primesN,p≥<#comment/>5N, p \geq 5withN≡<#comment/>−<#comment/>1modpN \equiv -1 \bmod p, the class number ofQ(N1/p)\mathbb {Q}(N^{1/p})is divisible bypp. Our methods are via congruences between Eisenstein series and cusp forms. In particular, we show that whenN≡<#comment/>−<#comment/>1modpN \equiv -1 \bmod p, there is always a cusp form of weight22and levelΓ<#comment/>0(N2)\Gamma _0(N^2)whoseℓ<#comment/>\ellth Fourier coefficient is congruent toℓ<#comment/>+1\ell + 1modulo a prime abovepp, for all primesℓ<#comment/>\ell. We use the Galois representation of such a cusp form to explicitly construct an unramified degree-ppextension ofQ(N1/p)\mathbb {Q}(N^{1/p}).

     
    more » « less
  2. We show that for any even log-concave probability measureμ<#comment/>\muonRn\mathbb {R}^n, any pair of symmetric convex setsKKandLL, and anyλ<#comment/>∈<#comment/>[0,1]\lambda \in [0,1],μ<#comment/>((1−<#comment/>λ<#comment/>)K+λ<#comment/>L)cn≥<#comment/>(1−<#comment/>λ<#comment/>)μ<#comment/>(K)cn+λ<#comment/>μ<#comment/>(L)cn,\begin{equation*} \mu ((1-\lambda ) K+\lambda L)^{c_n}\geq (1-\lambda ) \mu (K)^{c_n}+\lambda \mu (L)^{c_n}, \end{equation*}wherecn≥<#comment/>n−<#comment/>4−<#comment/>o(1)c_n\geq n^{-4-o(1)}. This constitutes progress towards the dimensional Brunn-Minkowski conjecture (see Richard J. Gardner and Artem Zvavitch [Tran. Amer. Math. Soc. 362 (2010), pp. 5333–5353]; Andrea Colesanti, Galyna V. Livshyts, Arnaud Marsiglietti [J. Funct. Anal. 273 (2017), pp. 1120–1139]). Moreover, our bound improves for various special classes of log-concave measures.

     
    more » « less
  3. For each odd integern≥<#comment/>3n \geq 3, we construct a rank-3 graphΛ<#comment/>n\Lambda _nwith involutionγ<#comment/>n\gamma _nwhose realC∗<#comment/>C^*-algebraCR∗<#comment/>(Λ<#comment/>n,γ<#comment/>n)C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda _n, \gamma _n)is stably isomorphic to the exotic Cuntz algebraEn\mathcal E_n. This construction is optimal, as we prove that a rank-2 graph with involution(Λ<#comment/>,γ<#comment/>)(\Lambda ,\gamma )can never satisfyCR∗<#comment/>(Λ<#comment/>,γ<#comment/>)∼<#comment/>MEEnC^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )\sim _{ME} \mathcal E_n, and Boersema reached the same conclusion for rank-1 graphs (directed graphs) in [Münster J. Math.10(2017), pp. 485–521, Corollary 4.3]. Our construction relies on a rank-1 graph with involution(Λ<#comment/>,γ<#comment/>)(\Lambda , \gamma )whose realC∗<#comment/>C^*-algebraCR∗<#comment/>(Λ<#comment/>,γ<#comment/>)C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )is stably isomorphic to the suspensionSRS \mathbb {R}. In the Appendix, we show that theii-fold suspensionSiRS^i \mathbb {R}is stably isomorphic to a graph algebra iff−<#comment/>2≤<#comment/>i≤<#comment/>1-2 \leq i \leq 1.

     
    more » « less
  4. Proving the “expectation-threshold” conjecture of Kahn and Kalai [Combin. Probab. Comput. 16 (2007), pp. 495–502], we show that for any increasing propertyF\mathcal {F}on a finite setXX,\[pc(F)=O(q(F)log⁡<#comment/>ℓ<#comment/>(F)),p_c(\mathcal {F})=O(q(\mathcal {F})\log \ell (\mathcal {F})),\]wherepc(F)p_c(\mathcal {F})andq(F)q(\mathcal {F})are the threshold and “expectation threshold” ofF\mathcal {F}, andℓ<#comment/>(F)\ell (\mathcal {F})is the maximum of22and the maximum size of a minimal member ofF\mathcal {F}.

     
    more » « less
  5. Let(R,m)(R,\mathfrak {m})be a Noetherian local ring of dimensiond≥<#comment/>2d\geq 2. We prove that ife(R^<#comment/>red)>1e(\widehat {R}_{red})>1, then the classical Lech’s inequality can be improved uniformly for allm\mathfrak {m}-primary ideals, that is, there existsε<#comment/>>0\varepsilon >0such thate(I)≤<#comment/>d!(e(R)−<#comment/>ε<#comment/>)ℓ<#comment/>(R/I)e(I)\leq d!(e(R)-\varepsilon )\ell (R/I)for allm\mathfrak {m}-primary idealsI⊆<#comment/>RI\subseteq R. This answers a question raised by Huneke, Ma, Quy, and Smirnov [Adv. Math. 372 (2020), pp. 107296, 33]. We also obtain partial results towards improvements of Lech’s inequality when we fix the number of generators ofII.

     
    more » « less