skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


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
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. 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
  2. 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
  3. Consider the linear transport equation in 1D under an external confining potential \begin{document}$$ \Phi $$\end{document}: \begin{document}$$ \begin{equation*} {\partial}_t f + v {\partial}_x f - {\partial}_x \Phi {\partial}_v f = 0. \end{equation*} $$\end{document} For \begin{document}$$ \Phi = \frac {x^2}2 + \frac { \varepsilon x^4}2 $$\end{document} (with \begin{document}$$ \varepsilon >0 $$\end{document} small), we prove phase mixing and quantitative decay estimates for \begin{document}$$ {\partial}_t \varphi : = - \Delta^{-1} \int_{ \mathbb{R}} {\partial}_t f \, \mathrm{d} v $$\end{document}, with an inverse polynomial decay rate \begin{document}$$ O({\langle} t{\rangle}^{-2}) $$\end{document}. In the proof, we develop a commuting vector field approach, suitably adapted to this setting. We will explain why we hope this is relevant for the nonlinear stability of the zero solution for the Vlasov–Poisson system in \begin{document}$ 1 $$\end{document}D under the external potential \begin{document}$$ \Phi $$\end{document}$. 
    more » « less
  4. Any \begin{document}$ C^d $$\end{document} conservative map \begin{document}$$ f $$\end{document} of the \begin{document}$$ d $$\end{document}-dimensional unit ball \begin{document}$$ {\mathbb B}^d $$\end{document}, \begin{document}$$ d\geq 2 $$\end{document}, can be realized by renormalized iteration of a \begin{document}$$ C^d $$\end{document} perturbation of identity: there exists a conservative diffeomorphism of \begin{document}$$ {\mathbb B}^d $$\end{document}, arbitrarily close to identity in the \begin{document}$$ C^d $$\end{document} topology, that has a periodic disc on which the return dynamics after a \begin{document}$$ C^d $$\end{document} change of coordinates is exactly \begin{document}$$ f $$\end{document}$. 
    more » « less
  5. We consider the derivative \begin{document}$$ D\pi $$\end{document} of the projection \begin{document}$$ \pi $$\end{document} from a stratum of Abelian or quadratic differentials to Teichmüller space. A closed one-form \begin{document}$$ \eta $$\end{document} determines a relative cohomology class \begin{document}$$ [\eta]_\Sigma $$\end{document}, which is a tangent vector to the stratum. We give an integral formula for the pairing of \begin{document}$$ D\pi([\eta]_\Sigma) $$\end{document} with a cotangent vector to Teichmüller space (a quadratic differential). We derive from this a comparison between Hodge and Teichmüller norms, which has been used in the work of Arana-Herrera on effective dynamics of mapping class groups, and which may clarify the relationship between dynamical and geometric hyperbolicity results in Teichmüller theory. 
    more » « less