BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We present a new elementary algorithm that takes time Oε(x53(logx)53+ε) and space O(x103(logx)1013) for computing M(x)=∑n≤xμ(n), where μ(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(x1/5(logx)5/3) by the use of (Helfgott, 2020; arxiv.org:1712.09130), at the cost of letting time rise to the order of x3/5(logx).
Let g, h be a random pair of generators of G=Sym(n) or G=Alt(n). We show that, with probability tending to 1 as n→∞, (a) the diameter of G with respect to S={g,h,g−1,h−1} is at most O(n2(logn)c), and (b) the mixing time of G with respect to S is at most O(n3(logn)c). (Both c and the implied constants are absolute.) These bounds are far lower than the strongest worst-case bounds known (in Helfgott--Seress, 2013); they roughly match the worst known examples. We also give an improved, though still non-constant, bound on the spectral gap. Our results rest on a combination of the algorithm in (Babai--Beals--Seress, 2004) and the fact that the action of a pair of random permutations is almost certain to act as an expander on ℓ-tuples, where ℓ is an arbitrary constant (Friedman et al., 1998).
Given a finite group G and a set A of generators, the diameter diam(Γ(G,A)) of the Cayley graph Γ(G,A) is the smallest ℓ such that every element of G can be expressed as a word of length at most ℓ in A∪A−1. We are concerned with bounding diam(G):= maxA diam(Γ(G,A)). It has long been conjectured that the diameter of the symmetric group of degree n is polynomially bounded in n, but the best previously known upper bound was exponential in nlogn. We give a quasipolynomial upper bound, namely, diam(G)=exp(O((logn)4loglogn))=exp((loglog∣G∣)O(1)) for G = Sym(n) or G = \Alt(n), where the implied constants are absolute. This addresses a key open case of Babai's conjecture on diameters of simple groups. By standard results, our bound also implies a quasipolynomial upper bound on the diameter of all transitive permutation groups of degree n.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.