skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: Super-polynomial accuracy of one dimensional randomized nets using the median of means
Let f f be analytic on [ 0 , 1 ] [0,1] with | f ( k ) ( 1 / 2 ) | ⩽<#comment/> A α<#comment/> k k ! |f^{(k)}(1/2)|\leqslant A\alpha ^kk! for some constants A A and α<#comment/> > 2 \alpha >2 and all k ⩾<#comment/> 1 k\geqslant 1 . We show that the median estimate of μ<#comment/> = ∫<#comment/> 0 1 f ( x ) d x \mu =\int _0^1f(x)\,\mathrm {d} x under random linear scrambling with n = 2 m n=2^m points converges at the rate O ( n −<#comment/> c log ⁡<#comment/> ( n ) ) O(n^{-c\log (n)}) for any c > 3 log ⁡<#comment/> ( 2 ) / π<#comment/> 2 ≈<#comment/> 0.21 c> 3\log (2)/\pi ^2\approx 0.21 . We also get a super-polynomial convergence rate for the sample median of 2 k −<#comment/> 1 2k-1 random linearly scrambled estimates, when k / m k/m is bounded away from zero. When f f has a p p ’th derivative that satisfies a λ<#comment/> \lambda -Hölder condition then the median of means has error O ( n −<#comment/> ( p + λ<#comment/> ) + ϵ<#comment/> ) O( n^{-(p+\lambda )+\epsilon }) for any ϵ<#comment/> > 0 \epsilon >0 , if k →<#comment/> ∞<#comment/> k\to \infty as m →<#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
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 formulate and prove a Conner–Floyd isomorphism for the algebraic K-theory of arbitrary qcqs derived schemes. To that end, we study a stable ∞<#comment/> \infty -category of non- A 1 \mathbb {A}^1 -invariant motivic spectra, which turns out to be equivalent to the ∞<#comment/> \infty -category of fundamental motivic spectra satisfying elementary blowup excision, previously introduced by the first and third authors. We prove that this ∞<#comment/> \infty -category satisfies P 1 \mathbb {P}^1 -homotopy invariance and weighted A 1 \mathbb {A}^1 -homotopy invariance, which we use in place of A 1 \mathbb {A}^1 -homotopy invariance to obtain analogues of several key results from A 1 \mathbb {A}^1 -homotopy theory. These allow us in particular to define a universal oriented motivic E ∞<#comment/> \mathbb {E}_\infty -ring spectrum M G L \mathrm {MGL} . We then prove that the algebraic K-theory of a qcqs derived scheme X X can be recovered from its M G L \mathrm {MGL} -cohomology via a Conner–Floyd isomorphism\[ M G L ∗<#comment/> ∗<#comment/> ( X ) ⊗<#comment/> L Z [ β<#comment/> ±<#comment/> 1 ] ≃<#comment/> K ∗<#comment/> ∗<#comment/> ( X ) , \mathrm {MGL}^{**}(X)\otimes _{\mathrm {L}{}}\mathbb {Z}[\beta ^{\pm 1}]\simeq \mathrm {K}{}^{**}(X), \]where L \mathrm {L}{} is the Lazard ring and K p , q ( X ) = K 2 q −<#comment/> p ( X ) \mathrm {K}{}^{p,q}(X)=\mathrm {K}{}_{2q-p}(X) . Finally, we prove a Snaith theorem for the periodized version of M G L \mathrm {MGL}
    more » « less
  2. We formulate a plausible conjecture for the optimal Ehrhard-type inequality for convex symmetric sets with respect to the Gaussian measure. Namely, letting J k −<#comment/> 1 ( s ) = ∫<#comment/> 0 s t k −<#comment/> 1 e −<#comment/> t 2 2 d t J_{k-1}(s)=\int ^s_0 t^{k-1} e^{-\frac {t^2}{2}}dt and c k −<#comment/> 1 = J k −<#comment/> 1 ( + ∞<#comment/> ) c_{k-1}=J_{k-1}(+\infty ) , we conjecture that the function F : [ 0 , 1 ] →<#comment/> R F:[0,1]\rightarrow \mathbb {R} , given by F ( a ) = ∑<#comment/> k = 1 n 1 a ∈<#comment/> E k ⋅<#comment/> ( β<#comment/> k J k −<#comment/> 1 −<#comment/> 1 ( c k −<#comment/> 1 a ) + α<#comment/> k ) \begin{equation*} F(a)= \sum _{k=1}^n 1_{a\in E_k}\cdot (\beta _k J_{k-1}^{-1}(c_{k-1} a)+\alpha _k) \end{equation*} (with an appropriate choice of a decomposition [ 0 , 1 ] = ∪<#comment/> i E i [0,1]=\cup _{i} E_i and coefficients α<#comment/> i , β<#comment/> i \alpha _i, \beta _i ) satisfies, for all symmetric convex sets K K and L L , and any λ<#comment/> ∈<#comment/> [ 0 , 1 ] \lambda \in [0,1] , F ( γ<#comment/> ( λ<#comment/> K + ( 1 −<#comment/> λ<#comment/> ) L ) ) ≥<#comment/> λ<#comment/> F ( γ<#comment/> ( K ) ) + ( 1 −<#comment/> λ<#comment/> ) F ( γ<#comment/> ( L ) ) . \begin{equation*} F\left (\gamma (\lambda K+(1-\lambda )L)\right )\geq \lambda F\left (\gamma (K)\right )+(1-\lambda ) F\left (\gamma (L)\right ). \end{equation*} We explain that this conjecture is “the most optimistic possible”, and is equivalent to the fact that for any symmetric convex set K K , itsGaussian concavity power p s ( K , γ<#comment/> ) p_s(K,\gamma ) is greater than or equal to p s ( R B 2 k ×<#comment/> R n −<#comment/> k , γ<#comment/> ) p_s(RB^k_2\times \mathbb {R}^{n-k},\gamma ) , for some k ∈<#comment/> { 1 , …<#comment/> , n } k\in \{1,\dots ,n\} . We call the sets R B 2 k ×<#comment/> R n −<#comment/> k RB^k_2\times \mathbb {R}^{n-k} round k k -cylinders; they also appear as the conjectured Gaussian isoperimetric minimizers for symmetric sets, see Heilman [Amer. J. Math. 143 (2021), pp. 53–94]. In this manuscript, we make progress towards this question, and show that for any symmetric convex set K K in R n \mathbb {R}^n , p s ( K , γ<#comment/> ) ≥<#comment/> sup F ∈<#comment/> L 2 ( K , γ<#comment/> ) ∩<#comment/> L i p ( K ) : ∫<#comment/> F = 1 ( 2 T γ<#comment/> F ( K ) −<#comment/> V a r ( F ) ) + 1 n −<#comment/> E X 2 , \begin{equation*} p_s(K,\gamma )\geq \sup _{F\in L^2(K,\gamma )\cap Lip(K):\,\int F=1} \left (2T_{\gamma }^F(K)-Var(F)\right )+\frac {1}{n-\mathbb {E}X^2}, \end{equation*} where T γ<#comment/> F ( K ) T_{\gamma }^F(K) is the F −<#comment/> F- torsional rigidity of K K with respect to the Gaussian measure.Moreover, the equality holds if and only if K = R B 2 k ×<#comment/> R n −<#comment/> k K=RB^k_2\times \mathbb {R}^{n-k} for some R > 0 R>0 and k = 1 , …<#comment/> , n k=1,\dots ,n .As a consequence, we get p s ( K , γ<#comment/> ) ≥<#comment/> Q ( E | X | 2 , E ‖<#comment/> X ‖<#comment/> K 4 , E ‖<#comment/> X ‖<#comment/> K 2 , r ( K ) ) , \begin{equation*} p_s(K,\gamma )\geq Q(\mathbb {E}|X|^2, \mathbb {E}\|X\|_K^4, \mathbb {E}\|X\|^2_K, r(K)), \end{equation*} where Q Q is a certain rational function of degree 2 2 , the expectation is taken with respect to the restriction of the Gaussian measure onto K K , ‖<#comment/> ⋅<#comment/> ‖<#comment/> K \|\cdot \|_K is the Minkowski functional of K K , and r ( K ) r(K) is the in-radius of K K . The result follows via a combination of some novel estimates, the L 2 L2 method (previously studied by several authors, notably Kolesnikov and Milman [J. Geom. Anal. 27 (2017), pp. 1680–1702; Amer. J. Math. 140 (2018), pp. 1147–1185;Geometric aspects of functional analysis, Springer, Cham, 2017; Mem. Amer. Math. Soc. 277 (2022), v+78 pp.], Kolesnikov and the author [Adv. Math. 384 (2021), 23 pp.], Hosle, Kolesnikov, and the author [J. Geom. Anal. 31 (2021), pp. 5799–5836], Colesanti [Commun. Contemp. Math. 10 (2008), pp. 765–772], Colesanti, the author, and Marsiglietti [J. Funct. Anal. 273 (2017), pp. 1120–1139], Eskenazis and Moschidis [J. Funct. Anal. 280 (2021), 19 pp.]), and the analysis of the Gaussian torsional rigidity. As an auxiliary result on the way to the equality case characterization, we characterize the equality cases in the “convex set version” of the Brascamp-Lieb inequality, and moreover, obtain a quantitative stability version in the case of the standard Gaussian measure; this may be of independent interest. All the equality case characterizations rely on the careful analysis of the smooth case, the stability versions via trace theory, and local approximation arguments. In addition, we provide a non-sharp estimate for a function F F whose composition with γ<#comment/> ( K ) \gamma (K) is concave in the Minkowski sense for all symmetric convex sets. 
    more » « less
  3. We show that for primes N , p ≥<#comment/> 5 N, p \geq 5 with N ≡<#comment/> −<#comment/> 1 mod p N \equiv -1 \bmod p , the class number of Q ( N 1 / p ) \mathbb {Q}(N^{1/p}) is divisible by p p . Our methods are via congruences between Eisenstein series and cusp forms. In particular, we show that when N ≡<#comment/> −<#comment/> 1 mod p N \equiv -1 \bmod p , there is always a cusp form of weight 2 2 and level Γ<#comment/> 0 ( N 2 ) \Gamma _0(N^2) whose ℓ<#comment/> \ell th Fourier coefficient is congruent to ℓ<#comment/> + 1 \ell + 1 modulo a prime above p p , for all primes ℓ<#comment/> \ell . We use the Galois representation of such a cusp form to explicitly construct an unramified degree- p p extension of Q ( N 1 / p ) \mathbb {Q}(N^{1/p})
    more » « less
  4. We prove and extend the longest-standing conjecture in ‘ q , t q,t -Catalan combinatorics,’ namely, the combinatorial formula for ∇<#comment/> m s μ<#comment/> \nabla ^m s_{\mu } conjectured by Loehr and Warrington, where s μ<#comment/> s_{\mu } is a Schur function and ∇<#comment/> \nabla is an eigenoperator on Macdonald polynomials. Our approach is to establish a stronger identity of infinite series of G L l GL_l characters involvingSchur Catalanimals; these were recently shown by the authors to represent Schur functions s μ<#comment/> [ −<#comment/> M X m , n ] s_{\mu }[-MX^{m,n}] in subalgebras Λ<#comment/> ( X m , n ) ⊂<#comment/> E \Lambda (X^{m,n})\subset \mathcal {E} isomorphic to the algebra of symmetric functions Λ<#comment/> \Lambda over Q ( q , t ) \mathbb {Q} (q,t) , where E \mathcal {E} is the elliptic Hall algebra of Burban and Schiffmann. We establish a combinatorial formula for Schur Catalanimals as weighted sums of LLT polynomials, with terms indexed by configurations of nested lattice paths callednests, having endpoints and bounding constraints controlled by data called aden. The special case for Λ<#comment/> ( X m , 1 ) \Lambda (X^{m,1}) proves the Loehr-Warrington conjecture, giving ∇<#comment/> m s μ<#comment/> \nabla ^m s_{\mu } as a weighted sum of LLT polynomials indexed by systems of nested Dyck paths. In general, for Λ<#comment/> ( X m , n ) \Lambda (X^{m,n}) our formula implies a new ( m , n ) (m,n) version of the Loehr-Warrington conjecture. In the case where each nest consists of a single lattice path, the nests in a den formula reduce to our previous shuffle theorem for paths under any line. Both this and the ( m , n ) (m,n) Loehr-Warrington formula generalize the ( k m , k n ) (km,kn) shuffle theorem proven by Carlsson and Mellit (for n = 1 n=1 ) and Mellit. Our formula here unifies these two generalizations. 
    more » « less
  5. We show that for any even log-concave probability measure μ<#comment/> \mu on R n \mathbb {R}^n , any pair of symmetric convex sets K K and L L , and any λ<#comment/> ∈<#comment/> [ 0 , 1 ] \lambda \in [0,1] , μ<#comment/> ( ( 1 −<#comment/> λ<#comment/> ) K + λ<#comment/> L ) c n ≥<#comment/> ( 1 −<#comment/> λ<#comment/> ) μ<#comment/> ( K ) c n + λ<#comment/> μ<#comment/> ( L ) c n , \begin{equation*} \mu ((1-\lambda ) K+\lambda L)^{c_n}\geq (1-\lambda ) \mu (K)^{c_n}+\lambda \mu (L)^{c_n}, \end{equation*} where c n ≥<#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