More Like this

1. Rigid automorphisms of linking systems

   https://doi.org/10.1017/fms.2021.17  

   Glauberman, George; Lynd, Justin (January 2021, Forum of Mathematics, Sigma)

   null (Ed.)

   Abstract A rigid automorphism of a linking system is an automorphism that restricts to the identity on the Sylow subgroup. A rigid inner automorphism is conjugation by an element in the center of the Sylow subgroup. At odd primes, it is known that each rigid automorphism of a centric linking system is inner. We prove that the group of rigid outer automorphisms of a linking system at the prime $$2$$ is elementary abelian and that it splits over the subgroup of rigid inner automorphisms. In a second result, we show that if an automorphism of a finite group G restricts to the identity on the centric linking system for G , then it is of $p'$ -order modulo the group of inner automorphisms, provided G has no nontrivial normal $p'$ -subgroups. We present two applications of this last result, one to tame fusion systems. 

   more » « less
2. Khintchine-type recurrence for 3-point configurations

   https://doi.org/10.1017/fms.2022.97  

   Ackelsberg, Ethan; Bergelson, Vitaly; Shalom, Or (January 2022, Forum of Mathematics, Sigma)

   Abstract The goal of this paper is to generalise, refine and improve results on large intersections from [2, 8]. We show that if G is a countable discrete abelian group and $$\varphi , \psi : G \to G$$ are homomorphisms, such that at least two of the three subgroups $$\varphi (G)$$ , $$\psi (G)$$ and $$(\psi -\varphi )(G)$$ have finite index in G , then $$\{\varphi , \psi \}$$ has the large intersections property . That is, for any ergodic measure preserving system $$\textbf {X}=(X,\mathcal {X},\mu ,(T_g)_{g\in G})$$ , any $$A\in \mathcal {X}$$ and any $$\varepsilon>0$$ , the set $$ \begin{align*} \{g\in G : \mu(A\cap T_{\varphi(g)}^{-1} A \cap T_{\psi(g)}^{-1} A)>\mu(A)^3-\varepsilon\} \end{align*} $$ is syndetic (Theorem 1.11). Moreover, in the special case where $$\varphi (g)=ag$$ and $$\psi (g)=bg$$ for $$a,b\in \mathbb {Z}$$ , we show that we only need one of the groups $aG$ , $bG$ or $(b-a)G$ to be of finite index in G (Theorem 1.13), and we show that the property fails, in general, if all three groups are of infinite index (Theorem 1.14). One particularly interesting case is where $$G=(\mathbb {Q}_{>0},\cdot )$$ and $$\varphi (g)=g$$ , $$\psi (g)=g^2$$ , which leads to a multiplicative version of the Khintchine-type recurrence result in [8]. We also completely characterise the pairs of homomorphisms $$\varphi ,\psi $$ that have the large intersections property when $$G = {{\mathbb Z}}^2$$ . The proofs of our main results rely on analysis of the structure of the universal characteristic factor for the multiple ergodic averages $$ \begin{align*} \frac{1}{|\Phi_N|} \sum_{g\in \Phi_N}T_{\varphi(g)}f_1\cdot T_{\psi(g)} f_2. \end{align*} $$ In the case where G is finitely generated, the characteristic factor for such averages is the Kronecker factor . In this paper, we study actions of groups that are not necessarily finitely generated, showing, in particular, that, by passing to an extension of $$\textbf {X}$$ , one can describe the characteristic factor in terms of the Conze–Lesigne factor and the $$\sigma $$ -algebras of $$\varphi (G)$$ and $$\psi (G)$$ invariant functions (Theorem 4.10). 

   more » « less
3. 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
4. On the edit distance function of the random graph

   https://doi.org/10.1017/S0963548321000353  

   Martin, Ryan R.; Riasanovsky, Alex W. (March 2022, Combinatorics, Probability and Computing)

   Abstract Given a hereditary property of graphs $$\mathcal{H}$$ and a $$p\in [0,1]$$ , the edit distance function $$\textrm{ed}_{\mathcal{H}}(p)$$ is asymptotically the maximum proportion of edge additions plus edge deletions applied to a graph of edge density p sufficient to ensure that the resulting graph satisfies $$\mathcal{H}$$ . The edit distance function is directly related to other well-studied quantities such as the speed function for $$\mathcal{H}$$ and the $$\mathcal{H}$$ -chromatic number of a random graph. Let $$\mathcal{H}$$ be the property of forbidding an Erdős–Rényi random graph $$F\sim \mathbb{G}(n_0,p_0)$$ , and let $$\varphi$$ represent the golden ratio. In this paper, we show that if $$p_0\in [1-1/\varphi,1/\varphi]$$ , then a.a.s. as $$n_0\to\infty$$ , \begin{align*} {\textrm{ed}}_{\mathcal{H}}(p) = (1+o(1))\,\frac{2\log n_0}{n_0} \cdot\min\left\{ \frac{p}{-\log(1-p_0)}, \frac{1-p}{-\log p_0} \right\}. \end{align*} Moreover, this holds for $$p\in [1/3,2/3]$$ for any $$p_0\in (0,1)$$ . A primary tool in the proof is the categorization of p -core coloured regularity graphs in the range $$p\in[1-1/\varphi,1/\varphi]$$ . Such coloured regularity graphs must have the property that the non-grey edges form vertex-disjoint cliques. 

   more » « less
5. Tight Bounds for ℓ ₁ Oblivious Subspace Embeddings

   https://doi.org/10.1145/3477537  

   Wang, Ruosong; Woodruff, David P. (January 2022, ACM Transactions on Algorithms)

   An \ell _p oblivious subspace embedding is a distribution over r \times n matrices \Pi such that for any fixed n \times d matrix A , \[ \Pr _{\Pi }[\textrm {for all }x, \ \Vert Ax\Vert _p \le \Vert \Pi Ax\Vert _p \le \kappa \Vert Ax\Vert _p] \ge 9/10,\] where r is the dimension of the embedding, \kappa is the distortion of the embedding, and for an n -dimensional vector y , \Vert y\Vert _p = (\sum _{i=1}^n |y_i|^p)^{1/p} is the \ell _p -norm. Another important property is the sparsity of \Pi , that is, the maximum number of non-zero entries per column, as this determines the running time of computing \Pi A . While for p = 2 there are nearly optimal tradeoffs in terms of the dimension, distortion, and sparsity, for the important case of 1 \le p \lt 2 , much less was known. In this article, we obtain nearly optimal tradeoffs for \ell _1 oblivious subspace embeddings, as well as new tradeoffs for 1 \lt p \lt 2 . Our main results are as follows: (1) We show for every 1 \le p \lt 2 , any oblivious subspace embedding with dimension r has distortion \[ \kappa = \Omega \left(\frac{1}{\left(\frac{1}{d}\right)^{1 / p} \log ^{2 / p}r + \left(\frac{r}{n}\right)^{1 / p - 1 / 2}}\right).\] When r = {\operatorname{poly}}(d) \ll n in applications, this gives a \kappa = \Omega (d^{1/p}\log ^{-2/p} d) lower bound, and shows the oblivious subspace embedding of Sohler and Woodruff (STOC, 2011) for p = 1 is optimal up to {\operatorname{poly}}(\log (d)) factors. (2) We give sparse oblivious subspace embeddings for every 1 \le p \lt 2 . Importantly, for p = 1 , we achieve r = O(d \log d) , \kappa = O(d \log d) and s = O(\log d) non-zero entries per column. The best previous construction with s \le {\operatorname{poly}}(\log d) is due to Woodruff and Zhang (COLT, 2013), giving \kappa = \Omega (d^2 {\operatorname{poly}}(\log d)) or \kappa = \Omega (d^{3/2} \sqrt {\log n} \cdot {\operatorname{poly}}(\log d)) and r \ge d \cdot {\operatorname{poly}}(\log d) ; in contrast our r = O(d \log d) and \kappa = O(d \log d) are optimal up to {\operatorname{poly}}(\log (d)) factors even for dense matrices. We also give (1) \ell _p oblivious subspace embeddings with an expected 1+\varepsilon number of non-zero entries per column for arbitrarily small \varepsilon \gt 0 , and (2) the first oblivious subspace embeddings for 1 \le p \lt 2 with O(1) -distortion and dimension independent of n . Oblivious subspace embeddings are crucial for distributed and streaming environments, as well as entrywise \ell _p low-rank approximation. Our results give improved algorithms for these applications. 

   more » « less