Fractal Geometry

On absolute continuity and maximal Garsia entropy for self-similar measures with algebraic contraction ratio

We consider the self-similar measure \nu_\lambda=\mathrm{law}\left(\sum_{j \geq 0} \xi_j \lambda^j\right) on \mathbb{R}, where |\lambda|<1 and the \xi_j \sim \nu are independent, identically distributed with respect to a measure \nu finitely supported on \mathbb{Z}. One example of this are Bernoulli convolutions. It is known that for certain combinations of algebraic \lambda and \nu uniform on an interval, \nu_\lambda is absolutely continuous and its Fourier transform has power decay; in the proof, it is exploited that for these combinations, a quantity called the Garsia entropy h_{\lambda}(\nu) is maximal.

In this paper, we show that the phenomenon of h_{\lambda}(\nu) being maximal is equivalent to absolute continuity of a self-affine measure \mu_\lambda, which is naturally associated to \lambda and projects onto \nu_\lambda. We also classify all combinations for which this phenomenon occurs: We find that if an algebraic \lambda without a Galois conjugate of modulus exactly one has a \nu such that h_{\lambda}(\nu) is maximal, then all Galois conjugates of \lambda must be smaller in modulus than one and \nu must satisfy a certain finite set of linear equations in terms of \lambda. Lastly, we show that in this case, the measure \mu_\lambda is not only absolutely continuous but also has power Fourier decay, which implies the same for \nu_\lambda.

Link to paper.

Homogeneous Dynamics

Non-Concentration of Primes in Γ∖PSL_2(ℝ)

This paper generalizes the result of Sarnak and Ubis (“The horocycle flow at prime times”, 2011) about non-concentration of primes in horocycle orbits on PSL_2(\mathbb{Z}) \backslash PSL_2(\mathbb{R}) to any lattice in PSL_2(\mathbb{R}). The proof combines the asymptotic result of Strömbergsson („On the deviation of ergodic averages for horocycle flows“, 2013) and Venkatesh’s method („Sparse equidistribution problems, period bounds, and subconvexity“, 2005) with the approach of Sarnak and Ubis of approximating horocycle pieces with periodic horocycles. The key step is to establish a dichotomy between \{\xi h(t), t \in [0, T] \} having good equidistribution in \Gamma \backslash PSL_2(\mathbb{R}) and it being approximable by closed horocycle pieces with small period. In a follow-up paper, a similar approach will be used to show equidistribution of \xi h(n^{1+\gamma}) for small \gamma>0, generalizing Venkatesh’s result in his aforementioned paper to non-compact \Gamma.

 

Link to paper.

Analysis of Boolean Functions

Low-degree learning and the metric entropy of polynomials (with A. Eskenazis and P. Ivanisvili)

Let \mathscr{F}_{n,d} be the class of all functions f:\{-1,1\}^n\to[-1,1] on the n-dimensional discrete hypercube of degree at most d. In the first part of this paper, we prove that any (deterministic or randomized) algorithm which learns \mathscr{F}_{n,d} with L_2-accuracy ε requires at least \Omega((1-\sqrt{\varepsilon})2^d\log n) queries for large enough n, thus establishing the sharpness as n\to\infty of a recent upper bound of Eskenazis and Ivanisvili (2021). To do this, we show that the L_2-packing numbers \mathsf{M}(\mathscr{F}_{n,d},\|\cdot\|_{L_2},\varepsilon) of the concept class \mathscr{F}_{n,d} satisfy the two-sided estimate

c(1-\varepsilon)2^d\log n \leq \log \mathsf{M}(\mathscr{F}_{n,d},\|\cdot\|_{L_2},\varepsilon) \leq \frac{2^{Cd}\log n}{\varepsilon^4}

for large enough n, where c, C>0 are universal constants. In the second part of the paper, we present a logarithmic upper bound for the randomized query complexity of classes of bounded approximate polynomials whose Fourier spectra are concentrated on few subsets. As an application, we prove new estimates for the number of random queries required to learn approximate juntas of a given degree, functions with rapidly decaying Fourier tails and constant depth circuits of given size. Finally, we obtain bounds for the number of queries required to learn the polynomial class \mathscr{F}_{n,d} without error in the query and random example models.

Link to paper.