More Like this

1. Elementary abelian Sylow subgroups of the multiplicative group

   https://doi.org/10.1016/j.jnt.2025.09.021  

   Morales, S; Polanco, G; Pollack, P (April 2026, Journal of Number Theory)

   Erd\H{o}s and Pomerance have shown that $$\varphi(n)$$ typically has about $$\frac{1}{2}(\log\log{n})^2$$ distinct prime factors. More precisely, $$\omega(\varphi(n))$$ has normal order $$\frac{1}{2}(\log\log{n})^2$$. Since $$\varphi(n)$$ is the size of the multiplicative group $$(\Z/n\Z)^{\times}$$, this result also gives the normal number of Sylow subgroups of $$(\Z/n\Z)^{\times}$$. Recently, Pollack considered specifically noncyclic Sylow subgroups of $$(\Z/n\Z)^{\times}$$, showing that the count of those has normal order $$\log\log{n}/\log\log\log{n}$$. We prove that the count of noncyclic Sylow subgroups that are elementary abelian of a fixed rank $$k\ge 2$$ has normal order $$\frac{1}{k(k-1)} \log\log{n}/\log\log\log{n}$$. So for example, (typically) among the primes $$p$$ for which the $$p$$-primary component of $$(\Z/n\Z)^{\times}$$ is noncyclic, this component is $$\Z/p\Z \oplus \Z/p\Z$$ about half the time. Additionally, we show that the count of $$p$$ for which the $$p$$-Sylow subgroup of $$(\Z/n\Z)^{\times}$$ is not elementary abelian has normal order $$2\sqrt{\pi} \sqrt{\log\log{n}}/\log\log\log{n}$$. 

   more » « less
2. Improved Parallel Construction of Wavelet Trees and Rank/Select Structures

   Shun, Julian (January 2020, Information and computation)

   Existing parallel algorithms for wavelet tree construction have a work complexity of $$O(n\log\sigma)$$. This paper presents parallel algorithms for the problem with improved work complexity. Our first algorithm is based on parallel integer sorting and has either $$O(n\log\log n\lceil\log\sigma/\sqrt{\log n\log\log n}\rceil)$$ work and polylogarithmic depth, or $$O(n\lceil\log\sigma/\sqrt{\log n}\rceil)$$ work and sub-linear depth. We also describe another algorithm that has $$O(n\lceil\log\sigma/\sqrt{\log n} \rceil)$$ work and $$O(\sigma+\log n)$$ depth. We then show how to use similar ideas to construct variants of wavelet trees (arbitrary-shaped binary trees and multiary trees) as well as wavelet matrices in parallel with lower work complexity than prior algorithms. Finally, we show that the rank and select structures on binary sequences and multiary sequences, which are stored on wavelet tree nodes, can be constructed in parallel with improved work bounds, matching those of the best existing sequential algorithms for constructing rank and select structures. 

   more » « less
3. Fully Dynamic Connectivity in $$O(\log n(\log\log n)^2)$$ Amortized Expected Time

   https://doi.org/10.46298/theoretics.23.6  

   Huang, Shang-En; Huang, Dawei; Kopelowitz, Tsvi; Pettie, Seth; Thorup, Mikkel (May 2023, TheoretiCS)

   Dynamic connectivity is one of the most fundamental problems in dynamic graphalgorithms. We present a randomized Las Vegas dynamic connectivity datastructure with $$O(\log n(\log\log n)^2)$$ amortized expected update time and$$O(\log n/\log\log\log n)$$ worst case query time, which comes very close to thecell probe lower bounds of Patrascu and Demaine (2006) and Patrascu and Thorup(2011). 

   more » « less
4. Counting points on smooth plane quartics

   https://doi.org/10.1007/s40993-022-00397-8  

   Costa, Edgar; Harvey, David; Sutherland, Andrew V. (March 2023, Research in Number Theory)

   Abstract We present efficient algorithms for counting points on a smooth plane quartic curve X modulo a prime p . We address both the case where X is defined over  $${\mathbb {F}}_p$$ F p and the case where X is defined over $${\mathbb {Q}}$$ Q and p is a prime of good reduction. We consider two approaches for computing $$\#X({\mathbb {F}}_p)$$ # X ( F p ) , one which runs in $$O(p\log p\log \log p)$$ O ( p log p log log p ) time using $$O(\log p)$$ O ( log p ) space and one which runs in $$O(p^{1/2}\log ^2p)$$ O ( p 1 / 2 log 2 p ) time using $$O(p^{1/2}\log p)$$ O ( p 1 / 2 log p ) space. Both approaches yield algorithms that are faster in practice than existing methods. We also present average polynomial-time algorithms for $$X/{\mathbb {Q}}$$ X / Q that compute $$\#X({\mathbb {F}}_p)$$ # X ( F p ) for good primes $$p\leqslant N$$ p ⩽ N in $$O(N\log ^3 N)$$ O ( N log 3 N ) time using O ( N ) space. These are the first practical implementations of average polynomial-time algorithms for curves that are not cyclic covers of $${\mathbb {P}}^1$$ P 1 , which in combination with previous results addresses all curves of genus $$g\leqslant 3$$ g ⩽ 3 . Our algorithms also compute Cartier–Manin/Hasse–Witt matrices that may be of independent interest. 

   more » « less
5. Summing $$\mu (n)$$: a faster elementary algorithm

   https://doi.org/10.1007/s40993-022-00408-8  

   Helfgott, Harald Andrés; Thompson, Lola (March 2023, Research in Number Theory)

   Abstract We present a new elementary algorithm that takes $$ \textrm{time} \ \ O_\epsilon \left( x^{\frac{3}{5}} (\log x)^{\frac{8}{5}+\epsilon } \right) \ \ \textrm{and} \ \textrm{space} \ \ O\left( x^{\frac{3}{10}} (\log x)^{\frac{13}{10}} \right) $$ time O ϵ x 3 5 ( log x ) 8 5 + ϵ and space O x 3 10 ( log x ) 13 10 (measured bitwise) for computing $$M(x) = \sum _{n \le x} \mu (n),$$ M ( x ) = ∑ n ≤ x μ ( n ) , where $$\mu (n)$$ μ ( n ) is the Möbius function. This is the first improvement in the exponent of x for an elementary algorithm since 1985. We also show that it is possible to reduce space consumption to $$O(x^{1/5} (\log x)^{5/3})$$ O ( x 1 / 5 ( log x ) 5 / 3 ) by the use of (Helfgott in: Math Comput 89:333–350, 2020), at the cost of letting time rise to the order of $$x^{3/5} (\log x)^2 \log \log x$$ x 3 / 5 ( log x ) 2 log log x . 

   more » « less