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. Adaptive Out-Orientations with Applications

   https://doi.org/10.1137/1.9781611977912.110  

   Chekuri, Chandra; Christiansen, Aleksander Bjørn; Holm, Jacob; van der Hoog, Ivor; Quanrud, Kent; Rotenberg, Eva; Schwiegelshohn, Chris. (January 2024, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024)

   Woodruff, David P. (Ed.)

   We give improved algorithms for maintaining edge-orientations of a fully-dynamic graph, such that the maximum out-degree is bounded. On one hand, we show how to orient the edges such that maximum out-degree is proportional to the arboricity $$\alpha$$ of the graph, in, either, an amortised update time of $$O(\log^2 n \log \alpha)$$, or a worst-case update time of $$O(\log^3 n \log \alpha)$$. On the other hand, motivated by applications including dynamic maximal matching, we obtain a different trade-off. Namely, the improved update time of either $$O(\log n \log \alpha)$$, amortised, or $$O(\log ^2 n \log \alpha)$$, worst-case, for the problem of maintaining an edge-orientation with at most $$O(\alpha + \log n)$$ out-edges per vertex. Finally, all of our algorithms naturally limit the recourse to be polylogarithmic in $$n$$ and $$\alpha$$. Our algorithms adapt to the current arboricity of the graph, and yield improvements over previous work: Firstly, we obtain deterministic algorithms for maintaining a $$(1+\varepsilon)$$ approximation of the maximum subgraph density, $$\rho$$, of the dynamic graph. Our algorithms have update times of $$O(\varepsilon^{-6}\log^3 n \log \rho)$$ worst-case, and $$O(\varepsilon^{-4}\log^2 n \log \rho)$$ amortised, respectively. We may output a subgraph $$H$$ of the input graph where its density is a $$(1+\varepsilon)$$ approximation of the maximum subgraph density in time linear in the size of the subgraph. These algorithms have improved update time compared to the $$O(\varepsilon^{-6}\log ^4 n)$$ algorithm by Sawlani and Wang from STOC 2020. Secondly, we obtain an $$O(\varepsilon^{-6}\log^3 n \log \alpha)$$ worst-case update time algorithm for maintaining a $$(1~+~\varepsilon)\textnormal{OPT} + 2$$ approximation of the optimal out-orientation of a graph with adaptive arboricity $$\alpha$$, improving the $$O(\varepsilon^{-6}\alpha^2 \log^3 n)$$ algorithm by Christiansen and Rotenberg from ICALP 2022. This yields the first worst-case polylogarithmic dynamic algorithm for decomposing into $$O(\alpha)$$ forests. Thirdly, we obtain arboricity-adaptive fully-dynamic deterministic algorithms for a variety of problems including maximal matching, $$\Delta+1$$ colouring, and matrix vector multiplication. All update times are worst-case $$O(\alpha+\log^2n \log \alpha)$$, where $$\alpha$$ is the current arboricity of the graph. For the maximal matching problem, the state-of-the-art deterministic algorithms by Kopelowitz, Krauthgamer, Porat, and Solomon from ICALP 2014 runs in time $$O(\alpha^2 + \log^2 n)$$, and by Neiman and Solomon from STOC 2013 runs in time $$O(\sqrt{m})$$. We give improved running times whenever the arboricity $$\alpha \in \omega( \log n\sqrt{\log\log n})$$. 

   more » « less