More Like this

1. Analysis of stochastic Lanczos quadrature for spectrum approximation

   Chen, Tyler; Trogdon, Thomas; Ubaru, Shashanka (January 2021, Proceedings of the 38th International Conference on Machine Learning)

   The cumulative empirical spectral measure (CESM) $$\Phi[\mathbf{A}] : \mathbb{R} \to [0,1]$$ of a $$n\times n$$ symmetric matrix $$\mathbf{A}$$ is defined as the fraction of eigenvalues of $$\mathbf{A}$$ less than a given threshold, i.e., $$\Phi[\mathbf{A}](x) := \sum_{i=1}^{n} \frac{1}{n} {\large\unicode{x1D7D9}}[ \lambda_i[\mathbf{A}]\leq x]$$. Spectral sums $$\operatorname{tr}(f[\mathbf{A}])$$ can be computed as the Riemann–Stieltjes integral of $$f$$ against $$\Phi[\mathbf{A}]$$, so the task of estimating CESM arises frequently in a number of applications, including machine learning. We present an error analysis for stochastic Lanczos quadrature (SLQ). We show that SLQ obtains an approximation to the CESM within a Wasserstein distance of $$t \: | \lambda_{\text{max}}[\mathbf{A}] - \lambda_{\text{min}}[\mathbf{A}] |$$ with probability at least $$1-\eta$$, by applying the Lanczos algorithm for $$\lceil 12 t^{-1} + \frac{1}{2} \rceil$$ iterations to $$\lceil 4 ( n+2 )^{-1}t^{-2} \ln(2n\eta^{-1}) \rceil$$ vectors sampled independently and uniformly from the unit sphere. We additionally provide (matrix-dependent) a posteriori error bounds for the Wasserstein and Kolmogorov–Smirnov distances between the output of this algorithm and the true CESM. The quality of our bounds is demonstrated using numerical experiments. 

   more » « less
2. Borel and Volume Classes for Dense Representations of Discrete Groups

   https://doi.org/10.1093/imrn/rnab078  

   Farre, James (April 2021, International Mathematics Research Notices)

   Abstract We show that the bounded Borel class of any dense representation $$\rho : G\to{\operatorname{PSL}}_n{\mathbb{C}}$$ is non-zero in degree three bounded cohomology and has maximal semi-norm, for any discrete group $$G$$. When $n=2$, the Borel class is equal to the three-dimensional hyperbolic volume class. Using tools from the theory of Kleinian groups, we show that the volume class of a dense representation $$\rho : G\to{\operatorname{PSL}}_2{\mathbb{C}}$$ is uniformly separated in semi-norm from any other representation $$\rho ^{\prime}: G\to{\operatorname{PSL}}_2 {\mathbb{C}}$$ for which there is a subgroup $$H\le G$$ on which $$\rho $$ is still dense but $$\rho ^{\prime}$$ is discrete or indiscrete but stabilizes a point, line, or plane in $${\mathbb{H}}^3\cup \partial{\mathbb{H}}^3$$. We exhibit a family of dense representations of a non-abelian free group on two letters and a family of discontinuous dense representations of $${\operatorname{PSL}}_2{\mathbb{R}}$$, whose volume classes are linearly independent and satisfy some additional properties; the cardinality of these families is that of the continuum. We explain how the strategy employed may be used to produce non-trivial volume classes in higher dimensions, contingent on the existence of a family of hyperbolic manifolds with certain topological and geometric properties. 

   more » « less
3. Increasing subsequences, matrix loci and Viennot shadows

   https://doi.org/10.1017/fms.2024.75  

   Rhoades, Brendon (January 2024, Forum of Mathematics, Sigma)

   Abstract Let$${\mathbf {x}}_{n \times n}$$be an$$n \times n$$matrix of variables, and let$${\mathbb {F}}[{\mathbf {x}}_{n \times n}]$$be the polynomial ring in these variables over a field$${\mathbb {F}}$$. We study the ideal$$I_n \subseteq {\mathbb {F}}[{\mathbf {x}}_{n \times n}]$$generated by all row and column variable sums and all products of two variables drawn from the same row or column. We show that the quotient$${\mathbb {F}}[{\mathbf {x}}_{n \times n}]/I_n$$admits a standard monomial basis determined by Viennot’s shadow line avatar of the Schensted correspondence. As a corollary, the Hilbert series of$${\mathbb {F}}[{\mathbf {x}}_{n \times n}]/I_n$$is the generating function of permutations in$${\mathfrak {S}}_n$$by the length of their longest increasing subsequence. Along the way, we describe a ‘shadow junta’ basis of the vector space ofk-local permutation statistics. We also calculate the structure of$${\mathbb {F}}[{\mathbf {x}}_{n \times n}]/I_n$$as a graded$${\mathfrak {S}}_n \times {\mathfrak {S}}_n$$-module. 

   more » « less
4. The unbounded denominators conjecture

   https://doi.org/10.1090/jams/1053  

   Calegari, Frank; Dimitrov, Vesselin; Tang, Yunqing (February 2025, Journal of the American Mathematical Society)

   We prove the unbounded denominators conjecture in the theory of noncongruence modular forms for finite index subgroups of ${\mathrm{SL}}_2<\#comment/>\left(\mathbf{Z}\right)$. Our result includes also Mason’s generalization of the original conjecture to the setting of vector-valued modular forms, thereby supplying a new path to the congruence property in rational conformal field theory. The proof involves a new arithmetic holonomicity bound of a potential-theoretic flavor, together with Nevanlinna second main theorem, the congruence subgroup property of ${\mathrm{SL}}_2<\#comment/>\left(\mathbf{Z}\right[1/p\left]\right)$, and a close description of the Fuchsian uniformization $D(0,1)/{\mathrm{\Gamma <\#comment/>}}_N$of the Riemann surface $\mathbf{C}\setminus <\#comment/>{\mathrm{\mu <\#comment/>}}_N$. 

   more » « less
5. Discrepancy in modular arithmetic progressions

   https://doi.org/10.1112/s0010437x22007758  

   Fox, Jacob; Xu, Max Wenqiang; Zhou, Yunkun (November 2022, Compositio Mathematica)

   Celebrated theorems of Roth and of Matoušek and Spencer together show that the discrepancy of arithmetic progressions in the first $$n$$ positive integers is $$\Theta (n^{1/4})$$ . We study the analogous problem in the $$\mathbb {Z}_n$$ setting. We asymptotically determine the logarithm of the discrepancy of arithmetic progressions in $$\mathbb {Z}_n$$ for all positive integer $$n$$ . We further determine up to a constant factor the discrepancy of arithmetic progressions in $$\mathbb {Z}_n$$ for many $$n$$ . For example, if $n=p^k$ is a prime power, then the discrepancy of arithmetic progressions in $$\mathbb {Z}_n$$ is $$\Theta (n^{1/3+r_k/(6k)})$$ , where $$r_k \in \{0,1,2\}$$ is the remainder when $$k$$ is divided by $$3$$ . This solves a problem of Hebbinghaus and Srivastav. 

   more » « less