More Like this

1. Some complexity results in the theory of normal numbers

   https://doi.org/10.4153/S0008414X20000723  

   Airey, Dylan; Jackson, Steve; Mance, Bill (February 2022, Canadian Journal of Mathematics)

   Abstract Let $$\mathcal {N}(b)$$ be the set of real numbers that are normal to base b . A well-known result of Ki and Linton [19] is that $$\mathcal {N}(b)$$ is $$\boldsymbol {\Pi }^0_3$$ -complete. We show that the set $${\mathcal {N}}^\perp (b)$$ of reals, which preserve $$\mathcal {N}(b)$$ under addition, is also $$\boldsymbol {\Pi }^0_3$$ -complete. We use the characterization of $${\mathcal {N}}^\perp (b),$$ given by Rauzy, in terms of an entropy-like quantity called the noise . It follows from our results that no further characterization theorems could result in a still better bound on the complexity of $${\mathcal {N}}^\perp (b)$$ . We compute the exact descriptive complexity of other naturally occurring sets associated with noise. One of these is complete at the $$\boldsymbol {\Pi }^0_4$$ level. Finally, we get upper and lower bounds on the Hausdorff dimension of the level sets associated with the noise. 

   more » « less
2. Higher-Order Cheeger Inequality for Partitioning with Buffers

   Makarychev, Konstantin; Makarychev, Yury; Shan, Liren; Vijayaraghavan, Aravindan (January 2024, SODA 2024)

   We prove a new generalization of the higher-order Cheeger inequality for partitioning with buffers. Consider a graph G=(V,E). The buffered expansion of a set S⊆V with a buffer B⊆V∖S is the edge expansion of S after removing all the edges from set S to its buffer B. An ε-buffered k-partitioning is a partitioning of a graph into disjoint components Pi and buffers Bi, in which the size of buffer Bi for Pi is small relative to the size of Pi: |Bi|≤ε|Pi|. The buffered expansion of a buffered partition is the maximum of buffered expansions of the k sets Pi with buffers Bi. Let hk,εG be the buffered expansion of the optimal ε-buffered k-partitioning, then for every δ>0, hk,εG≤Oδ(1)⋅(logkε)⋅λ⌊(1+δ)k⌋, where λ⌊(1+δ)k⌋ is the ⌊(1+δ)k⌋-th smallest eigenvalue of the normalized Laplacian of G. Our inequality is constructive and avoids the ``square-root loss'' that is present in the standard Cheeger inequalities (even for k=2). We also provide a complementary lower bound, and a novel generalization to the setting with arbitrary vertex weights and edge costs. Moreover our result implies and generalizes the standard higher-order Cheeger inequalities and another recent Cheeger-type inequality by Kwok, Lau, and Lee (2017) involving robust vertex expansion. 

   more » « less
3. Cantor spectrum of graphene in magnetic fields

   Becker, Simon; Han, Rui; Jitomirskaya, Svetlana (October 2019, Inventiones mathematicae)

   We consider a quantum graph as a model of graphene in magnetic fields and give a complete analysis of the spectrum, for all constant fluxes. In particular, we show that if the reduced magnetic flux $$\Phi/2\pi$$ through a honeycomb is irrational, the continuous spectrum is an unbounded Cantor set of Lebesgue measure zero. 

   more » « less
4. Sparse confidence sets for normal mean models

   https://doi.org/10.1093/imaiai/iaad003  

   Ning, Yang; Cheng, Guang (March 2023, Information and Inference: A Journal of the IMA)

   Abstract In this paper, we propose a new framework to construct confidence sets for a $$d$$-dimensional unknown sparse parameter $${\boldsymbol \theta }$$ under the normal mean model $${\boldsymbol X}\sim N({\boldsymbol \theta },\sigma ^{2}\bf{I})$$. A key feature of the proposed confidence set is its capability to account for the sparsity of $${\boldsymbol \theta }$$, thus named as sparse confidence set. This is in sharp contrast with the classical methods, such as the Bonferroni confidence intervals and other resampling-based procedures, where the sparsity of $${\boldsymbol \theta }$$ is often ignored. Specifically, we require the desired sparse confidence set to satisfy the following two conditions: (i) uniformly over the parameter space, the coverage probability for $${\boldsymbol \theta }$$ is above a pre-specified level; (ii) there exists a random subset $$S$$ of $$\{1,...,d\}$$ such that $$S$$ guarantees the pre-specified true negative rate for detecting non-zero $$\theta _{j}$$’s. To exploit the sparsity of $${\boldsymbol \theta }$$, we allow the confidence interval for $$\theta _{j}$$ to degenerate to a single point 0 for any $$j\notin S$$. Under this new framework, we first consider whether there exist sparse confidence sets that satisfy the above two conditions. To address this question, we establish a non-asymptotic minimax lower bound for the non-coverage probability over a suitable class of sparse confidence sets. The lower bound deciphers the role of sparsity and minimum signal-to-noise ratio (SNR) in the construction of sparse confidence sets. Furthermore, under suitable conditions on the SNR, a two-stage procedure is proposed to construct a sparse confidence set. To evaluate the optimality, the proposed sparse confidence set is shown to attain a minimax lower bound of some properly defined risk function up to a constant factor. Finally, we develop an adaptive procedure to the unknown sparsity. Numerical studies are conducted to verify the theoretical results. 

   more » « less
5. Differential operators and families of automorphic forms on Unitary groups of arbitrary signature

   Eischen, Ellen; Fintzen, Jessica; Mantovan, Elena; Varma, Ila (June 2018, Documenta mathematica)

   In the 1970's, Serre exploited congruences between q-expansion coefficients of Eisenstein series to produce p-adic families of Eisenstein series and, in turn, p-adic zeta functions. Partly through integration with more recent machinery, including Katz's approach to p-adic differential operators, his strategy has influenced four decades of developments. Prior papers employing Katz's and Serre's ideas exploiting differential operators and congruences to produce families of automorphic forms rely crucially on q-expansions of automorphic forms. The overarching goal of the present paper is to adapt the strategy to automorphic forms on unitary groups, which lack q-expansions when the signature is of the form (a,b), a≠b. In particular, this paper completely removes the restrictions on the signature present in prior work. As intermediate steps, we achieve two key objectives. First, partly by carefully analyzing the action of the Young symmetrizer on Serre-Tate expansions, we explicitly describe the action of differential operators on the Serre-Tate expansions of automorphic forms on unitary groups of arbitrary signature. As a direct consequence, for each unitary group, we obtain congruences and families analogous to those studied by Katz and Serre. Second, via a novel lifting argument, we construct a p-adic measure taking values in the space of p-adic automorphic forms on unitary groups of any prescribed signature. We relate the values of this measure to an explicit p-adic family of Eisenstein series. One application of our results is to the recently completed construction of p-adic L-functions for unitary groups by the first named author, Harris, Li, and Skinner. 

   more » « less