skip to main content


Title: A proof of the conjectured run time of the Hafner-McCurley class group algorithm

We present a proof under a generalization of the Riemann Hypothesis that the class group algorithm of Hafner and McCurley runs in expected time \begin{document}$ e^{\left(3/\sqrt{8}+o(1)\right)\sqrt{\log d\log\log d}} $\end{document} where \begin{document}$ -d $\end{document} is the discriminant of the input imaginary quadratic order. In the original paper, an expected run time of \begin{document}$ e^{\left(\sqrt{2}+o(1)\right)\sqrt{\log d\log\log d}} $\end{document} was proven, and better bounds were conjectured. To achieve a proven result, we rely on a mild modification of the original algorithm, and on recent results on the properties of the Cayley graph of the ideal class group.

 
more » « less
Award ID(s):
1846166
NSF-PAR ID:
10324557
Author(s) / Creator(s):
;
Date Published:
Journal Name:
Advances in Mathematics of Communications
Volume:
0
Issue:
0
ISSN:
1930-5346
Page Range / eLocation ID:
0
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Experiments with diblock co-polymer melts display undulated bilayers that emanate from defects such as triple junctions and endcaps, [8]. Undulated bilayers are characterized by oscillatory perturbations of the bilayer width, which decay on a spatial length scale that is long compared to the bilayer width. We mimic defects within the functionalized Cahn-Hillard free energy by introducing spatially localized inhomogeneities within its parameters. For length parameter \begin{document}$ \varepsilon\ll1 $\end{document}, we show that this induces undulated bilayer solutions whose width perturbations decay on an \begin{document}$ O\!\left( \varepsilon^{-1/2}\right) $\end{document} inner length scale that is long in comparison to the \begin{document}$ O(1) $\end{document} scale that characterizes the bilayer width.

     
    more » « less
  2. For any finite horizon Sinai billiard map \begin{document}$ T $\end{document} on the two-torus, we find \begin{document}$ t_*>1 $\end{document} such that for each \begin{document}$ t\in (0,t_*) $\end{document} there exists a unique equilibrium state \begin{document}$ \mu_t $\end{document} for \begin{document}$ - t\log J^uT $\end{document}, and \begin{document}$ \mu_t $\end{document} is \begin{document}$ T $\end{document}-adapted. (In particular, the SRB measure is the unique equilibrium state for \begin{document}$ - \log J^uT $\end{document}.) We show that \begin{document}$ \mu_t $\end{document} is exponentially mixing for Hölder observables, and the pressure function \begin{document}$ P(t) = \sup_\mu \{h_\mu -\int t\log J^uT d \mu\} $\end{document} is analytic on \begin{document}$ (0,t_*) $\end{document}. In addition, \begin{document}$ P(t) $\end{document} is strictly convex if and only if \begin{document}$ \log J^uT $\end{document} is not \begin{document}$ \mu_t $\end{document}-a.e. cohomologous to a constant, while, if there exist \begin{document}$ t_a\ne t_b $\end{document} with \begin{document}$ \mu_{t_a} = \mu_{t_b} $\end{document}, then \begin{document}$ P(t) $\end{document} is affine on \begin{document}$ (0,t_*) $\end{document}. An additional sparse recurrence condition gives \begin{document}$ \lim_{t\downarrow 0} P(t) = P(0) $\end{document}.

     
    more » « less
  3. We show that for any even log-concave probability measureμ<#comment/>\muonRn\mathbb {R}^n, any pair of symmetric convex setsKKandLL, and anyλ<#comment/>∈<#comment/>[0,1]\lambda \in [0,1],μ<#comment/>((1−<#comment/>λ<#comment/>)K+λ<#comment/>L)cn≥<#comment/>(1−<#comment/>λ<#comment/>)μ<#comment/>(K)cn+λ<#comment/>μ<#comment/>(L)cn,\begin{equation*} \mu ((1-\lambda ) K+\lambda L)^{c_n}\geq (1-\lambda ) \mu (K)^{c_n}+\lambda \mu (L)^{c_n}, \end{equation*}wherecn≥<#comment/>n−<#comment/>4−<#comment/>o(1)c_n\geq n^{-4-o(1)}. 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
  4. By discretizing an argument of Kislyakov, Naor and Schechtman proved that the 1-Wasserstein metric over the planar grid{0,1,…<#comment/>,n}2\{0,1,\dots , n\}^2hasL1L_1-distortion bounded below by a constant multiple oflog⁡<#comment/>n\sqrt {\log n}. We provide a new “dimensionality” interpretation of Kislyakov’s argument, showing that if{Gn}n=1∞<#comment/>\{G_n\}_{n=1}^\inftyis a sequence of graphs whose isoperimetric dimension and Lipschitz-spectral dimension equal a common numberδ<#comment/>∈<#comment/>[2,∞<#comment/>)\delta \in [2,\infty ), then the 1-Wasserstein metric overGnG_nhasL1L_1-distortion bounded below by a constant multiple of(log⁡<#comment/>|Gn|)1δ<#comment/>(\log |G_n|)^{\frac {1}{\delta }}. We proceed to compute these dimensions for⊘<#comment/>\oslash-powers of certain graphs. In particular, we get that the sequence of diamond graphs{Dn}n=1∞<#comment/>\{\mathsf {D}_n\}_{n=1}^\inftyhas isoperimetric dimension and Lipschitz-spectral dimension equal to 2, obtaining as a corollary that the 1-Wasserstein metric overDn\mathsf {D}_nhasL1L_1-distortion bounded below by a constant multiple oflog⁡<#comment/>|Dn|\sqrt {\log | \mathsf {D}_n|}. This answers a question of Dilworth, Kutzarova, and Ostrovskii and exhibits only the third sequence ofL1L_1-embeddable graphs whose sequence of 1-Wasserstein metrics is notL1L_1-embeddable.

     
    more » « less
  5. This paper studies a family of generalized surface quasi-geostrophic (SQG) equations for an active scalar \begin{document}$ \theta $\end{document} on the whole plane whose velocities have been mildly regularized, for instance, logarithmically. The well-posedness of these regularized models in borderline Sobolev regularity have previously been studied by D. Chae and J. Wu when the velocity \begin{document}$ u $\end{document} is of lower singularity, i.e., \begin{document}$ u = -\nabla^{\perp} \Lambda^{ \beta-2}p( \Lambda) \theta $\end{document}, where \begin{document}$ p $\end{document} is a logarithmic smoothing operator and \begin{document}$ \beta \in [0, 1] $\end{document}. We complete this study by considering the more singular regime \begin{document}$ \beta\in(1, 2) $\end{document}. The main tool is the identification of a suitable linearized system that preserves the underlying commutator structure for the original equation. We observe that this structure is ultimately crucial for obtaining continuity of the flow map. In particular, straightforward applications of previous methods for active transport equations fail to capture the more nuanced commutator structure of the equation in this more singular regime. The proposed linearized system nontrivially modifies the flux of the original system in such a way that it coincides with the original flux when evaluated along solutions of the original system. The requisite estimates are developed for this modified linear system to ensure its well-posedness.

     
    more » « less