More Like this

1. Super-polynomial accuracy of one dimensional randomized nets using the median of means

   https://doi.org/10.1090/mcom/3791  

   Pan, Zexin; Owen, Art (March 2023, Mathematics of Computation)

   Let $f$be analytic on $[0,1]$with $|f^{\left(k\right)}\left(1/2\right)|⩽<\#comment/>A{\mathrm{\alpha <\#comment/>}}^{k}k!$for some constants $A$and $\mathrm{\alpha <\#comment/>}>2$and all $k⩾<\#comment/>1$. We show that the median estimate of $\mathrm{\mu <\#comment/>}={\int <\#comment/>}_0^{1}f\left(x\right)\mathrm{d}x$under random linear scrambling with $n=2^m$points converges at the rate $O\left(n^{-<\#comment/>c\log <\#comment/>\left(n\right)}\right)$for any $c>3\log <\#comment/>\left(2\right)/{\mathrm{\pi <\#comment/>}}^2\approx <\#comment/>0.21$. We also get a super-polynomial convergence rate for the sample median of $2k-<\#comment/>1$random linearly scrambled estimates, when $k/m$is bounded away from zero. When $f$has a $p$’th derivative that satisfies a $\mathrm{\lambda <\#comment/>}$-Hölder condition then the median of means has error $O\left(n^{-<\#comment/>(p+\mathrm{\lambda <\#comment/>})+\mathrm{ϵ<\#comment/>}}\right)$for any $\mathrm{ϵ<\#comment/>}>0$, if $k\to <\#comment/>\mathrm{\infty <\#comment/>}$as $m\to <\#comment/>\mathrm{\infty <\#comment/>}$. 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
2. Products of normal subsets

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

   Larsen, Michael; Shalev, Aner; Tiep, Pham (February 2024, Transactions of the American Mathematical Society)

   In this paper we consider which families of finite simple groups $G$have the property that for each $\mathrm{ϵ<\#comment/>}>0$there exists $N>0$such that, if $|G|\ge <\#comment/>N$and $S,T$are normal subsets of $G$with at least $\mathrm{ϵ<\#comment/>}|G|$elements each, then every non-trivial element of $G$is the product of an element of $S$and an element of $T$. We show that this holds in a strong and effective sense for finite simple groups of Lie type of bounded rank, while it does not hold for alternating groups or groups of the form ${\mathrm{P}\mathrm{S}\mathrm{L}}_n\left(q\right)$where $q$is fixed and $n\to <\#comment/>\mathrm{\infty <\#comment/>}$. However, in the case $S=T$and $G$alternating this holds with an explicit bound on $N$in terms of $\mathrm{ϵ<\#comment/>}$. Related problems and applications are also discussed. In particular we show that, if $w_1,w_2$are non-trivial words, $G$is a finite simple group of Lie type of bounded rank, and for $g\in <\#comment/>G$, $P_{w_1\left(G\right),w_2\left(G\right)}\left(g\right)$denotes the probability that $g_1{g}_2=g$where $g_i\in <\#comment/>w_i\left(G\right)$are chosen uniformly and independently, then, as $|G|\to <\#comment/>\mathrm{\infty <\#comment/>}$, the distribution $P_{w_1\left(G\right),w_2\left(G\right)}$tends to the uniform distribution on $G$with respect to the $L^{\mathrm{\infty <\#comment/>}}$norm. 

   more » « less
3. Model theory and agnostic online learning via excellent sets

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

   Malliaris, M; Moran, S (November 2024, Transactions of the American Mathematical Society)

   We use algorithmic methods from online learning to explore some important objects at the intersection of model theory and combinatorics, and find natural ways that algorithmic methods can detect and explain (and improve our understanding of) stable structure in the sense of model theory. The main theorem deals with existence of $\mathrm{ϵ<\#comment/>}$-excellent sets (which are key to the Stable Regularity Lemma, a theorem characterizing the appearance of irregular pairs in Szemerédi’s celebrated Regularity Lemma). We prove that $\mathrm{ϵ<\#comment/>}$-excellent sets exist for any $\mathrm{ϵ<\#comment/>}>\frac{1}{2}$in $k$-edge stable graphs in the sense of model theory (equivalently, Littlestone classes); earlier proofs had given this only for $\mathrm{ϵ<\#comment/>}>1/2^{2^k}$or so. We give two proofs: the first uses regret bounds from online learning, the second uses Boolean closure properties of Littlestone classes and sampling. We also give a version of the dynamic Sauer-Shelah-Perles lemma appropriate to this setting, related to definability of types. We conclude by characterizing stable/Littlestone classes as those supporting a certain abstract notion of majority: the proof shows that the two distinct, natural notions of majority, arising from measure and from dimension, densely often coincide. 

   more » « less
4. A universal bound in the dimensional Brunn-Minkowski inequality for log-concave measures

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

   Livshyts, Galyna (June 2023, Transactions of the American Mathematical Society)

   We show that for any even log-concave probability measure $\mathrm{\mu <\#comment/>}$on ${\mathbb{R}}^n$, any pair of symmetric convex sets $K$and $L$, and any $\mathrm{\lambda <\#comment/>}\in <\#comment/>[0,1]$, $\mathrm{\mu <\#comment/>}\left(\right(1-<\#comment/>\mathrm{\lambda <\#comment/>})K+\mathrm{\lambda <\#comment/>}L{)}^{c_n}\ge <\#comment/>(1-<\#comment/>\mathrm{\lambda <\#comment/>}\left)\mathrm{\mu <\#comment/>}\right(K{)}^{c_n}+\mathrm{\lambda <\#comment/>}\mathrm{\mu <\#comment/>}(L{)}^{c_n},$where $c_n\ge <\#comment/>n^{-<\#comment/>4-<\#comment/>o\left(1\right)}$. 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
5. On a conjectural symmetric version of Ehrhard’s inequality

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

   Livshyts, Galyna (May 2024, Transactions of the American Mathematical Society)

   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}\left(s\right)={\int <\#comment/>}_0^s{t}^{k-<\#comment/>1}{e}^{-<\#comment/>\frac{t^2}{2}}dt$and $c_{k-<\#comment/>1}=J_{k-<\#comment/>1}(+\mathrm{\infty <\#comment/>})$, we conjecture that the function $F:[0,1]\to <\#comment/>\mathbb{R}$, given by $F\left(a\right)=\underset{k=1}{\overset{n}{\sum <\#comment/>}}{1}_{a\in <\#comment/>E_k}\cdot <\#comment/>\left({\mathrm{\beta <\#comment/>}}_k{J}_{k-<\#comment/>1}^{-<\#comment/>1}\right(c_{k-<\#comment/>1}a)+{\mathrm{\alpha <\#comment/>}}_k)$(with an appropriate choice of a decomposition $[0,1]={\cup <\#comment/>}_i{E}_i$and coefficients ${\mathrm{\alpha <\#comment/>}}_i,{\mathrm{\beta <\#comment/>}}_i$) satisfies, for all symmetric convex sets $K$and $L$, and any $\mathrm{\lambda <\#comment/>}\in <\#comment/>[0,1]$, $F\left(\mathrm{\gamma <\#comment/>}\right(\mathrm{\lambda <\#comment/>}K+(1-<\#comment/>\mathrm{\lambda <\#comment/>})L\left)\right)\ge <\#comment/>\mathrm{\lambda <\#comment/>}F\left(\mathrm{\gamma <\#comment/>}\right(K\left)\right)+(1-<\#comment/>\mathrm{\lambda <\#comment/>})F\left(\mathrm{\gamma <\#comment/>}\right(L\left)\right).$We explain that this conjecture is “the most optimistic possible”, and is equivalent to the fact that for any symmetric convex set $K$, itsGaussian concavity power $p_s(K,\mathrm{\gamma <\#comment/>})$is greater than or equal to $p_s(R{B}_2^k\times <\#comment/>{\mathbb{R}}^{n-<\#comment/>k},\mathrm{\gamma <\#comment/>})$, for some $k\in <\#comment/>\{1,\dots <\#comment/>,n\}$. We call the sets $R{B}_2^k\times <\#comment/>{\mathbb{R}}^{n-<\#comment/>k}$round $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$in ${\mathbb{R}}^n$, $p_s(K,\mathrm{\gamma <\#comment/>})\ge <\#comment/>\underset{F\in <\#comment/>L^2(K,\mathrm{\gamma <\#comment/>})\cap <\#comment/>Lip\left(K\right):\int <\#comment/>F=1}{sup}\left(2T_{\mathrm{\gamma <\#comment/>}}^F\right(K)-<\#comment/>Var(F\left)\right)+\frac{1}{n-<\#comment/>\mathbb{E}{X}^2},$where $T_{\mathrm{\gamma <\#comment/>}}^F\left(K\right)$is the $F-<\#comment/>$torsional rigidity of $K$with respect to the Gaussian measure.Moreover, the equality holds if and only if $K=R{B}_2^k\times <\#comment/>{\mathbb{R}}^{n-<\#comment/>k}$for some $R>0$and $k=1,\dots <\#comment/>,n$.As a consequence, we get $p_s(K,\mathrm{\gamma <\#comment/>})\ge <\#comment/>Q(\mathbb{E}|X{|}^2,\mathbb{E}\Vert <\#comment/>X{\Vert <\#comment/>}_K^4,\mathbb{E}\Vert <\#comment/>X{\Vert <\#comment/>}_K^2,r(K\left)\right),$where $Q$is a certain rational function of degree $2$, the expectation is taken with respect to the restriction of the Gaussian measure onto $K$, $\Vert <\#comment/>\cdot <\#comment/>{\Vert <\#comment/>}_K$is the Minkowski functional of $K$, and $r\left(K\right)$is the in-radius of $K$. The result follows via a combination of some novel estimates, the $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$whose composition with $\mathrm{\gamma <\#comment/>}\left(K\right)$is concave in the Minkowski sense for all symmetric convex sets. 

   more » « less