An official website of the United States government
We show that if a finitely generated group $$G$$ has a nonelementary WPD action on a hyperbolic metric space $$X$$ , then the number of $$G$$ -conjugacy classes of $$X$$ -loxodromic elements of $$G$$ coming from a ball of radius $$R$$ in the Cayley graph of $$G$$ grows exponentially in $$R$$ . As an application we prove that for $$N\geq 3$$ the number of distinct $$\text{Out}(F_{N})$$ -conjugacy classes of fully irreducible elements $$\unicode[STIX]{x1D719}$$ from an $$R$$ -ball in the Cayley graph of $$\text{Out}(F_{N})$$ with $$\log \unicode[STIX]{x1D706}(\unicode[STIX]{x1D719})$$ of the order of $$R$$ grows exponentially in $$R$$ .
more »
« less
Counting conjugacy classes of fully irreducibles: double exponential growth
Inspired by results of Eskin and Mirzakhani (J Mod Dyn 5(1):71–105, 2011) counting closed geodesics of length at most L in the moduli space of a fixed closed surface, we consider a similar question in the Out(Fr) setting. The Eskin-Mirzakhani result can be equivalently stated in terms of counting the number of conjugacy classes (within the mapping class group) of pseudo-Anosovs whose dilatations have natural logarithm at most L. Let N(L) denote the number of Out(Fr)-conjugacy classes of fully irreducibles satisfying that the natural logarithm of their dilatation is at most L. We prove for r>2 that as L goes to infinity, the number N(L) has double exponential (in L) lower and upper bounds. These bounds reveal behavior not present in the surface setting or in classical hyperbolic dynamical systems.
more »
« less
- Award ID(s):
- 1905641
- PAR ID:
- 10491258
- Publisher / Repository:
- Springer
- Date Published:
- Journal Name:
- Geometriae Dedicata
- Volume:
- 218
- Issue:
- 2
- ISSN:
- 0046-5755
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract In her thesis, Mirzakhani showed that the number of simple closed geodesics of length$$\leq L$$on a closed, connected, oriented hyperbolic surfaceXof genusgis asymptotic to$$L^{6g-6}$$times a constant depending on the geometry ofX. In this survey, we give a detailed account of Mirzakhani’s proof of this result aimed at non-experts. We draw inspiration from classic primitive lattice point counting results in homogeneous dynamics. The focus is on understanding how the general principles that drive the proof in the case of lattices also apply in the setting of hyperbolic surfaces.more » « less
-
We revisit the much-studied problem of space-efficiently estimating the number of triangles in a graph stream, and extensions of this problem to counting fixed-sized cliques and cycles, obtaining a number of new upper and lower bounds. For the important special case of counting triangles, we give a $$4$$-pass, $$(1\pm\varepsilon)$$-approximate, randomized algorithm that needs at most $$\widetilde{O}(\varepsilon^{-2}\cdot m^{3/2}/T)$$ space, where $$m$$ is the number of edges and $$T$$ is a promised lower bound on the number of triangles. This matches the space bound of a very recent algorithm (McGregor et al., PODS 2016), with an arguably simpler and more general technique. We give an improved multi-pass lower bound of $$\Omega(\min\{m^{3/2}/T, m/\sqrt{T}\})$$, applicable at essentially all densities $$\Omega(n) \le m \le O(n^2)$$. We also prove other multi-pass lower bounds in terms of various structural parameters of the input graph. Together, our results resolve a couple of open questions raised in recent work (Braverman et al., ICALP 2013). Our presentation emphasizes more general frameworks, for both upper and lower bounds. We give a sampling algorithm for counting arbitrary subgraphs and then improve it via combinatorial means in the special cases of counting odd cliques and odd cycles. Our results show that these problems are considerably easier in the cash-register streaming model than in the turnstile model, where previous work had focused (Manjunath et al., ESA 2011; Kane et al., ICALP 2012). We use Tur{\'a}n graphs and related gadgets to derive lower bounds for counting cliques and cycles, with triangle-counting lower bounds following as a corollary.more » « less
-
Cai and Hemachandra used iterative constant-setting to prove that Few ⊆ ⊕P (and thus that FewP ⊆ ⊕P). In this paper, we note that there is a tension between the nondeterministic ambiguity of the class one is seeking to capture, and the density (or, to be more precise, the needed “nongappy”-ness) of the easy-to-find “targets” used in iterative constant-setting. In particular, we show that even less restrictive gap-size upper bounds regarding the targets allow one to capture ambiguity-limited classes. Through a flexible, metatheorem-based approach, we do so for a wide range of classes including the logarithmic-ambiguity version of Valiant’s unambiguous nondeterminism class UP. Our work lowers the bar for what advances regarding the existence of infinite, P-printable sets of primes would suffice to show that restricted counting classes based on the primes have the power to accept superconstant-ambiguity analogues of UP. As an application of our work, we prove that the Lenstra–Pomerance–Wagstaff Conjecture implies that all O(log log n)-ambiguity NP sets are in the restricted counting class RC_PRIMES .more » « less
-
Abstract If G is permutation group acting on a finite set $$\Omega $$ , then this action induces a natural action of G on the power set $$\mathscr{P}(\Omega )$$ . The number $s(G)$ of orbits in this action is an important parameter that has been used in bounding numbers of conjugacy classes in finite groups. In this context, $$\inf ({\log _2 s(G)}/{\log _2 |G|})$$ plays a role, but the precise value of this constant was unknown. We determine it where G runs over all permutation groups not containing any $${{\textrm {A}}}_l, l> 4$$ , as a composition factor.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1007/s10711-024-00885-4
