Efficiently computing partial sums of arithmetic functions

Abstract

Primes are arguably the most important objects in analytic number theory. The prime-counting function (denoted by π(x)) counts the number of primes less than or equal to x, while the summatory Liouville function (denoted by L(x)) records the difference between positive integers up to x with an even number of prime factors and those with an odd number. Both functions encode deep arithmetic information and are closely tied to the distribution of prime numbers and the multiplicative structure of the integers. However, obtaining exact values of π(x) and L(x) is difficult, due to the irregular patterns of the prime numbers. In this thesis, we explore both combinatorial (Deléglise, Rivat 1996) and analytic (Platt 2013) approaches to the computation of π(x). We also discuss the inherent difficulties in summing arithmetic functions over primes and highlight the challenges to make further improvements in the prime-counting algorithms. We then turn to the Liouville function and investigate L(x). Building on recent results (Helfgott, Thompson 2023), we develop a combinatorial algorithm to compute L(x) in roughly O(x^3/5) operations using roughly O(x^3/10) memory. This appears to be a new result in the literature. Finally, we generalize the condition under which the Helfgott-Thompson method can be effectively applied, thereby expanding the scope of this powerful technique.