An official website of the United States government
Abstract Let Γ be a Schottky semigroup in {\mathrm{SL}_{2}(\mathbf{Z})} ,and for {q\in\mathbf{N}} , let {\Gamma(q):=\{\gamma\in\Gamma:\gamma=e~{}(\mathrm{mod}~{}q)\}} be its congruence subsemigroupof level q . Let δ denote the Hausdorff dimension of the limit set of Γ.We prove the following uniform congruence counting theoremwith respect to the family of Euclidean norm balls {B_{R}} in {M_{2}(\mathbf{R})} of radius R :for all positive integer q with no small prime factors, \#(\Gamma(q)\cap B_{R})=c_{\Gamma}\frac{R^{2\delta}}{\#(\mathrm{SL}_{2}(%\mathbf{Z}/q\mathbf{Z}))}+O(q^{C}R^{2\delta-\epsilon}) as {R\to\infty} for some {c_{\Gamma}>0,C>0,\epsilon>0} which are independent of q .Our technique also applies to give a similar counting result for the continued fractions semigroup of {\mathrm{SL}_{2}(\mathbf{Z})} ,which arises in the study of Zaremba’s conjecture on continued fractions.
more »
« less
This content will become publicly available on April 1, 2026
Hausdorff Dimension of Caloric Measure
abstract: We examine caloric measures $$\omega$$ on general domains in $$\RR^{n+1}=\RR^n\times\RR$$ (space $$\times$$ time) from the perspective of geometric measure theory. On one hand, we give a direct proof of a consequence of a theorem of Taylor and Watson (1985) that the lower parabolic Hausdorff dimension of $$\omega$$ is at least $$n$$ and $$\omega\ll\Haus^n$$. On the other hand, we prove that the upper parabolic Hausdorff dimension of $$\omega$$ is at most $$n+2-\beta_n$$, where $$\beta_n>0$$ depends only on $$n$$. Analogous bounds for harmonic measures were first shown by Nevanlinna (1934) and Bourgain (1987). Heuristically, we show that the \emph{density} of obstacles in a cube needed to make it unlikely that a Brownian motion started outside of the cube exits a domain near the center of the cube must be chosen according to the ambient dimension. In the course of the proof, we give a caloric measure analogue of Bourgain's alternative: for any constants $$0<\epsilon\ll_n \delta<1/2$ and closed set $$E\subset\RR^{n+1}$$, either (i) $$E\cap Q$$ has relatively large caloric measure in $$Q\setminus E$$ for every pole in $$F$$ or (ii) $$E\cap Q_*$$ has relatively small $$\rho$$-dimensional parabolic Hausdorff content for every $$n<\rho\leq n+2$$, where $$Q$$ is a cube, $$F$$ is a subcube of $$Q$$ aligned at the center of the top time-face, and $$Q_*$$ is a subcube of $$Q$$ that is close to, but separated backwards-in-time from $$F$$: \begin{gather*} Q=(-1/2,1/2)^n\times (-1,0),\quad F=[-1/2+\delta,1/2-\delta]^n\times[-\epsilon^2,0),\\[2pt] \text{and }Q_*=[-1/2+\delta,1/2-\delta]^n\times[-3\epsilon^2,-2\epsilon^2]. \end{gather*} Further, we supply a version of the strong Markov property for caloric measures.
more »
« less
- Award ID(s):
- 1650546
- PAR ID:
- 10645947
- Publisher / Repository:
- Project MUSE
- Date Published:
- Journal Name:
- American Journal of Mathematics
- Volume:
- 147
- Issue:
- 2
- ISSN:
- 1080-6377
- Page Range / eLocation ID:
- 465 to 502
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We prove two new results about the inability of low-degree polynomials to uniformly approximate constant-depth circuits, even to slightly-better-than-trivial error. First, we prove a tight Omega~(n^{1/2}) lower bound on the threshold degree of the SURJECTIVITY function on n variables. This matches the best known threshold degree bound for any AC^0 function, previously exhibited by a much more complicated circuit of larger depth (Sherstov, FOCS 2015). Our result also extends to a 2^{Omega~(n^{1/2})} lower bound on the sign-rank of an AC^0 function, improving on the previous best bound of 2^{Omega(n^{2/5})} (Bun and Thaler, ICALP 2016). Second, for any delta>0, we exhibit a function f : {-1,1}^n -> {-1,1} that is computed by a circuit of depth O(1/delta) and is hard to approximate by polynomials in the following sense: f cannot be uniformly approximated to error epsilon=1-2^{-Omega(n^{1-delta})}, even by polynomials of degree n^{1-delta}. Our recent prior work (Bun and Thaler, FOCS 2017) proved a similar lower bound, but which held only for error epsilon=1/3. Our result implies 2^{Omega(n^{1-delta})} lower bounds on the complexity of AC^0 under a variety of basic measures such as discrepancy, margin complexity, and threshold weight. This nearly matches the trivial upper bound of 2^{O(n)} that holds for every function. The previous best lower bound on AC^0 for these measures was 2^{Omega(n^{1/2})} (Sherstov, FOCS 2015). Additional applications in learning theory, communication complexity, and cryptography are described.more » « less
-
Abstract We consider the problem of computing the partition function $$\sum _x e^{f(x)}$$ , where $$f: \{-1, 1\}^n \longrightarrow {\mathbb R}$$ is a quadratic or cubic polynomial on the Boolean cube $$\{-1, 1\}^n$$ . In the case of a quadratic polynomial f , we show that the partition function can be approximated within relative error $$0 < \epsilon < 1$$ in quasi-polynomial $$n^{O(\ln n - \ln \epsilon )}$$ time if the Lipschitz constant of the non-linear part of f with respect to the $$\ell ^1$$ metric on the Boolean cube does not exceed $$1-\delta $$ , for any $$\delta>0$$ , fixed in advance. For a cubic polynomial f , we get the same result under a somewhat stronger condition. We apply the method of polynomial interpolation, for which we prove that $$\sum _x e^{\tilde {f}(x)} \ne 0$$ for complex-valued polynomials $$\tilde {f}$$ in a neighborhood of a real-valued f satisfying the above mentioned conditions. The bounds are asymptotically optimal. Results on the zero-free region are interpreted as the absence of a phase transition in the Lee–Yang sense in the corresponding Ising model. The novel feature of the bounds is that they control the total interaction of each vertex but not every single interaction of sets of vertices.more » « less
-
We prove that for all integers 2≤m≤d−1, there exists doubling measures on ℝd with full support that are m-rectifiable and purely (m−1)-unrectifiable in the sense of Federer (i.e. without assuming μ≪m). The corresponding result for 1-rectifiable measures is originally due to Garnett, Killip, and Schul (2010). Our construction of higher-dimensional Lipschitz images is informed by a simple observation about square packing in the plane: N axis-parallel squares of side length s pack inside of a square of side length ⌈N1/2⌉s. The approach is robust and when combined with standard metric geometry techniques allows for constructions in complete Ahlfors regular metric spaces. One consequence of the main theorem is that for each m∈{2,3,4} and s0, f(E) has Hausdorff dimension s, and μ(f(E))>0. This is striking, because m(f(E))=0 for every Lipschitz map f:E⊂ℝm→ℍ1 by a theorem of Ambrosio and Kirchheim (2000). Another application of the square packing construction is that every compact metric space 𝕏 of Assouad dimension strictly less than m is a Lipschitz image of a compact set E⊂[0,1]m. Of independent interest, we record the existence of doubling measures on complete Ahlfors regular metric spaces with prescribed lower and upper Hausdorff and packing dimensions.more » « less
-
null (Ed.)Abstract Let $$1\leq p \leq q <\infty $$ and let $$w \in \mathbb{C}$$. Weissler conjectured that the Hermite operator $$e^{w\Delta }$$ is bounded as an operator from $$L^{p}$$ to $$L^{q}$$ on the Hamming cube $$\{-1,1\}^{n}$$ with the norm bound independent of $$n$$ if and only if $$\begin{align*} |p-2-e^{2w}(q-2)|\leq p-|e^{2w}|q. \end{align*}$$It was proved in [ 1], [ 2], and [ 17] in all cases except $$2<p\leq q <3$$ and $$3/2<p\leq q <2$$, which stood open until now. The goal of this paper is to give a full proof of Weissler’s conjecture in the case $p=q$. Several applications will be presented.more » « less
