Fact-checked by Grok 2 weeks ago

Mertens function

The Mertens function, denoted M(n), is a function in number theory defined as the partial sum of the Möbius function \mu(k) over the positive integers up to n:
M(n) = \sum_{k=1}^n \mu(k),
where \mu(k) equals 1 if k is a square-free positive integer with an even number of prime factors, −1 if it has an odd number, and 0 otherwise.^[1] This definition captures the balance between square-free numbers with even and odd parity of prime factors up to n, providing a measure of their oscillatory distribution.^[1] Introduced by the Austrian mathematician Franz Mertens in 1897 as part of his studies on arithmetic functions associated with primes, the Mertens function has become central to analytic number theory due to its intimate connections with the distribution of prime numbers and the Riemann zeta function.^[1] Mertens computed extensive tables of \mu(n) and M(n) to explore patterns, which informed his broader work on prime-related sums. A key aspect of the Mertens function is its asymptotic behavior, which is linked to the prime number theorem and the Riemann hypothesis (RH). It is known that M(n) = o(n) as n \to \infty, implying that the average value of \mu(n) tends to zero, a consequence of the prime number theorem.^[2] Under the RH, stronger bounds hold, such as M(n) = O(\sqrt{n} \exp(c \sqrt{\log n \log \log n})) for some constant c > 0, reflecting the function's slow, irregular growth with oscillations in both positive and negative directions.^[3] Mertens himself conjectured in 1897 that |M(n)| \leq \sqrt{n} for all n > 1, a bound that would have implied the RH but was empirically verified only up to relatively small values at the time.^[4] This Mertens conjecture stood for nearly a century before being disproved in 1985 by Andrew Odlyzko and Herman te Riele, who used computational methods and properties of zeta function zeros to show that |M(n)| > \sqrt{n} for infinitely many n, with the first counterexample occurring around n \approx 10^{30}. The disproof highlighted the function's chaotic fluctuations and spurred further research into its exact order of growth, which remains an active area tied to unresolved problems like the RH.^[5] Additional properties include integral representations relating it to the Riemann zeta function, relations to sieve theory, where sums involving M(n) appear in estimates for the number of primes in arithmetic progressions.^[1] The function also equals the determinant of the n \times n Redheffer matrix, linking it to combinatorial number theory.^[1] Overall, the Mertens function serves as a probe for deep structures in the primes, with its study revealing both the subtleties and limitations of classical conjectures in analytic number theory.

Definition and Basics

Definition

The Mertens function, denoted M(n), for a positive integer n is defined as the partial sum of the Möbius function:

M(n) = \sum_{k=1}^n \mu(k),

where the Möbius function \mu(k) is an arithmetic function given by \mu(k) = 0 if k has a repeated prime factor, \mu(k) = 1 if k is a square-free positive integer with an even number of distinct prime factors, and \mu(k) = -1 if k has an odd number of distinct prime factors.^[6] For real numbers x > 0, the Mertens function is extended in the natural way by M(x) = M(\lfloor x \rfloor), where \lfloor x \rfloor is the greatest integer less than or equal to x.^[7] The function is named after the Austrian mathematician Franz Mertens, who introduced it in his 1897 paper "Über eine zahlentheoretische Funktion," where he explored its connections to properties of the Riemann zeta function.^[6] The Mertens function quantifies the oscillatory balance between square-free integers up to n that have an even number of distinct prime factors and those with an odd number.

Small values

The Mertens function M(n), defined as the sum \sum_{k=1}^n \mu(k) where \mu is the Möbius function, yields the following values for small n, computed via cumulative summation after determining \mu(k) using a linear sieve that identifies square-free integers and counts their distinct prime factors.^[8]^[1]

n	M(n)
1	1
2	0
3	-1
4	-1
5	-2
6	-1
7	-2
8	-2
9	-2
10	-1
11	-2
12	-2
13	-3
14	-2
15	-1
16	-1
17	-2
18	-2
19	-3
20	-3
21	-2
22	-1
23	-2
24	-2
25	-2
26	-1
27	-1
28	-1
29	-2
30	-3

These initial values show M(n) starting positive at n=1, immediately reaching zero and then negative values, with minor fluctuations such as recoveries to -1 at several points (e.g., n=6, 10, 15).^[8] The underlying Möbius function contributes to this behavior: \mu(p) = -1 for each prime p, decreasing the running sum by 1; \mu(pq) = 1 for distinct primes p and q, increasing it by 1; and \mu(n) = 0 for any n with a repeated prime factor, leaving the sum unchanged. To obtain \mu(k) via sieving, an array is initialized, primes are generated iteratively (as in the Sieve of Eratosthenes), and for each multiple of a prime, the value is set to 0 if squared or alternated in sign based on the prime count.^[9]^[1] Over the first few hundred terms, M(n) illustrates its oscillatory nature by remaining non-positive from n=2 to n=93, then turning positive at n=94 where M(94) = 1, before continuing to fluctuate with increasing amplitude and more frequent sign changes, though displaying an early negative bias.^[8] This early pattern of slow variation and sporadic recoveries highlights the function's connection to the distribution of square-free numbers.^[1]

Representations

Integral representation

The Mertens function M(x) = \sum_{n \leq x} \mu(n), where \mu(n) is the Möbius function, admits an integral representation derived from Perron's formula applied to the Dirichlet series \sum_{n=1}^\infty \mu(n) n^{-s} = 1/\zeta(s) for \operatorname{Re}(s) > 1. Perron's formula expresses the partial sum as M(x) = \frac{1}{2\pi i} \int_{c - iT}^{c + iT} \frac{1}{\zeta(s)} \frac{x^s}{s} \, ds + O\left( \frac{x^c}{T} \log x \right) for c > 1 and large T, with the error term vanishing as T \to \infty.^[10] To obtain an exact expression, the contour is shifted to the left, enclosing the poles of the integrand. The function $1/\zeta(s) has simple poles at the zeros \rho of \zeta(s), with residue $1/\zeta'(\rho) at each simple non-trivial zero \rho. The integrand also has poles at s=0 from the $1/s factor and at the trivial zeros of \zeta(s) (negative even integers). Evaluating the residues via the residue theorem yields the explicit formula assuming simple zeros:

M(x) = \sum_{\rho} \frac{x^{\rho}}{\rho \zeta'(\rho)} - 2 + \sum_{n=1}^{\infty} (-1)^{n-1} \frac{(2\pi)^{2n}}{(2n)! \, n \, \zeta(2n+1) \, x^{2n}},

where the first sum is over the non-trivial zeros \rho of \zeta(s), the constant -2 arises from the residue at s=0 and adjustments near s=1, and the infinite series accounts for residues at the trivial zeros s = -2n.^[10]^[11] This representation, first derived in detail by Titchmarsh using contour integration, links the oscillatory behavior of M(x) directly to the distribution of the non-trivial zeros of \zeta(s). The sum over \rho captures the main irregular fluctuations of M(x), reflecting the deep connections between the Mertens function and the primes through the zeta function, while the series term provides a rapidly convergent correction for large x. Extensions of this formula without assuming zero simplicity have been established by evaluating higher-order residues.^[10]^[11]

Farey sequence sum

The Mertens function M(n) possesses a discrete combinatorial representation as a finite sum over the terms of the Farey sequence of order n. This sequence \mathcal{F}_n comprises all irreducible fractions a/b (with $0 \leq a \leq b \leq n and \gcd(a, b) = 1) arranged in increasing order from $0/1 to $1/1. The formula is given by

M(n) = -1 + \sum_{a \in \mathcal{F}_n} e^{2\pi i a},

where the sum is complex-valued but real, as the imaginary parts cancel due to the symmetry of \mathcal{F}_n around $1/2. This expression enables exact computation of M(n) using the approximately $3n^2/\pi^2 terms in \mathcal{F}_n, offering a practical alternative for numerical evaluation up to moderate n. The derivation proceeds from the definition M(n) = \sum_{k=1}^n \mu(k), where \mu is the Möbius function, combined with the structure of \mathcal{F}_n. Grouping terms by denominator b, the contribution for each b \geq 2 is the sum over coprime numerators $1 \leq a \leq b-1 with \gcd(a, b) = 1 of e^{2\pi i a/b}, which equals the Ramanujan sum c_b(1) = \mu(b). Adding the endpoint terms e^{2\pi i \cdot 0/1} = 1 and e^{2\pi i \cdot 1/1} = 1 for b=1 yields $2 + \sum_{b=2}^n \mu(b) = 1 + M(n), so rearranging gives the formula. This relies on Möbius inversion to express the coprimality indicator and the Euler totient function implicitly through the count of terms per denominator. Geometrically, this sum connects to the enumeration of visible lattice points in the plane. Each fraction a/b \in \mathcal{F}_n corresponds to the direction from the origin to the point (b, a), visible if no other lattice points lie along the line segment, equivalent to \gcd(a, b) = 1. The exponential term e^{2\pi i a/b} encodes a phase shift proportional to the angle of this vector, linking the oscillatory behavior of M(n) to the distribution of these coprime pairs within the region $1 \leq x \leq n, $0 \leq y \leq n. This perspective highlights how fluctuations in M(n) reflect irregularities in the visibility horizon of lattice points.^[12]

Determinant form

The Mertens function M(n) can be expressed as the determinant of the n \times n Redheffer matrix A_n, a square (0,1)-matrix defined by entries a_{i,j} = 1 if j = 1 or i divides j, and a_{i,j} = 0 otherwise.^[13] This representation provides a matrix-theoretic interpretation of M(n) = \sum_{k=1}^n \mu(k), where \mu is the Möbius function.^[14] The Redheffer matrix encodes the inclusion-exclusion principle through its divisibility structure, reflecting the arithmetic relations among integers up to n that underpin the Möbius function's role in inverting the divisor sum. Specifically, the first column consists entirely of 1s, corresponding to the unit element in the poset of positive integers under divisibility, while the remaining entries capture the partial order of division, analogous to the zeta function in the incidence algebra. The determinant arises from permutations in its Leibniz expansion that form division chains, directly yielding the signed sum over square-free integers via Möbius inversion.^[14] This construction links the finite matrix to the Euler product for the reciprocal of the Riemann zeta function, as M(n) approximates the truncated product \prod_{p \leq n} (1 - 1/p) up to lower-order terms, encoding the exclusion of prime multiples.90401-U) Introduced by Redheffer in 1977 as part of an explicitly solvable optimization problem, this matrix form was developed to analyze approximations of the zeta function and explore bounds related to its poles, particularly in the context of the Riemann hypothesis.^[13] The determinant's explicit computation via M(n) facilitates numerical verification of such approximations without direct summation of \mu(k).^[14]

Properties

Arithmetic properties

The Mertens function M(n) = \sum_{k=1}^n \mu(k), where \mu is the Möbius function, is not multiplicative. For instance, M(4) = -1, whereas multiplicativity would require M(4) = M(2)^2 = 0^2 = 0. This non-multiplicativity arises because the partial sum of the Möbius function does not preserve the multiplicative structure of \mu, even though \mu itself is multiplicative.^[1] A key arithmetic interpretation of the Mertens function relates it to square-free integers. Specifically, M(n) equals the number of square-free positive integers up to n with an even number of distinct prime factors minus the number with an odd number. The total count of square-free integers up to n is then \sum_{k=1}^n |\mu(k)| = S_{\text{even}}(n) + S_{\text{odd}}(n), where S_{\text{even}}(n) and S_{\text{odd}}(n) are the respective counts. This difference highlights the balancing role of even and odd parity in square-free numbers.^[15] An important identity stemming from the properties of the Möbius function, which directly impacts the Mertens function as its partial sum, is

\sum_{k=1}^n \mu(k) \left\lfloor \frac{n}{k} \right\rfloor = 1

for all positive integers n. This follows from Möbius inversion applied to the fact that \sum_{d \mid m} \mu(d) = [m=1], where [ \cdot ] is the Iverson bracket, leading to a count of exactly one term when m = 1 up to n. The property \sum_{d \mid m} \mu(d) = 0 for m > 1 is implied here and ensures the sum vanishes for non-trivial divisors. This identity is used in computational number theory to verify values of \mu and M. The Mertens function also connects to the Euler totient function \phi through related summatory identities. One such convolution arises from inverting the relation n = \sum_{d \mid n} \phi(d), yielding the partial sum formula

\sum_{k=1}^n \phi(k) = \sum_{k=1}^n \mu(k) \cdot \frac{1}{2} \left\lfloor \frac{n}{k} \right\rfloor \left( \left\lfloor \frac{n}{k} \right\rfloor + 1 \right).

This expresses the summatory totient in terms of the Möbius function, and thus indirectly via M(n) for efficient computation in ranges where partial sums are precomputed. The form reflects the arithmetic interplay between coprimality counts in \phi and inclusion-exclusion in \mu.^[16] Regarding sign changes, the Mertens function begins positive at M(1) = 1, drops to zero at n=2, and becomes negative at n=3 with M(3) = -1. It remains non-positive through n=93, crossing zero again at n=39 and n=40 (where M(39) = M(40) = 0), before turning positive at n=94 with M(94) = 1, the first such occurrence after n=1. These early sign changes illustrate the oscillatory nature of M(n), which is known to change sign infinitely often.^[17]^[18]

Analytic properties

The analytic properties of the Mertens function are derived from the generating function for the Möbius function \mu(n), of which M(n) is the partial summatory function. The Dirichlet series for \mu(n) is

\sum_{n=1}^\infty \frac{\mu(n)}{n^s} = \frac{1}{\zeta(s)}

for \Re(s) > 1, where \zeta(s) is the Riemann zeta function.^[19] This equality follows from the Euler product representation of \zeta(s) = \prod_p (1 - p^{-s})^{-1}, so that the reciprocal is \prod_p (1 - p^{-s}). The function $1/\zeta(s) admits a meromorphic continuation to the entire complex plane \mathbb{C}, with singularities consisting of simple poles located precisely at the zeros of \zeta(s).^[3] Assuming the zeros of \zeta(s) are simple (as conjectured by the Riemann hypothesis), these poles are simple; the trivial zeros of \zeta(s) at the negative even integers s = -2, -4, \dots correspond to poles of $1/\zeta(s) there, while the non-trivial zeros in the critical strip $0 < \Re(s) < 1 give rise to poles in that region. At s=1, where \zeta(s) has a simple pole, $1/\zeta(s) has a simple zero. The Mertens function M(x) is linked to this generating function via complex analysis through Perron's inversion formula, which expresses the partial sum as a contour integral:

M(x) = \frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} \left( \sum_{n=1}^\infty \frac{\mu(n)}{n^s} \right) \frac{x^s}{s}\, ds = \frac{1}{2\pi i} \int_{c-i\infty}^{c+i\infty} \frac{1}{\zeta(s)} \frac{x^s}{s}\, ds,

where c > 1 is a real number ensuring the integral converges.^[19] Shifting the contour of integration to the left across the critical strip captures residues at the poles of $1/\zeta(s), thereby relating M(x) directly to the zeros of \zeta(s). A key manifestation of these properties is the explicit formula for M(x), which represents it as a sum over the non-trivial zeros \rho of \zeta(s):

M(x) = \sum_{\rho} \frac{x^{\rho}}{\rho \zeta'(\rho)} + \sum_{n=1}^\infty \frac{x^{-2n}}{-2n \zeta'(-2n)} + O\left( x^{\frac{1}{2} + \epsilon} \right),

where the sum over \rho is taken over zeros with |\Im(\rho)| < T for suitable T \to \infty, and the trivial zeros contribute the second sum; the error term holds under suitable assumptions on the zeros.^[20] This formula underscores how the oscillatory behavior of M(x) is governed by the distribution of the zeta zeros in the complex plane. Regarding mean values, the Mertens function has average order zero in the sense that

\frac{1}{x} \int_1^x M(t)\, dt = o(1)

as x \to \infty, reflecting the cancellation inherent in the partial sums of \mu(n).^[21] This follows from the analytic continuation and residue contributions in the Perron integral, without relying on growth estimates for M(x) itself. Moment estimates for integrals involving powers of M(x), such as \int_1^x |M(t)|^k\, dt for k \geq 2, can be obtained via similar contour shifts, yielding expressions in terms of multiple sums over zeta zeros, though explicit forms depend on the multiplicity and location of those zeros.^[20]

Asymptotics

Asymptotic expansions

The asymptotic behavior of the Mertens function M(x) for large x is captured by an explicit formula analogous to von Mangoldt's formula for the Chebyshev function \psi(x). This formula expresses M(x) as a sum over the non-trivial zeros \rho of the Riemann zeta function \zeta(s), truncated at some height T > 0:

M(x) = \sum_{|\Im \rho| \leq T} \frac{x^\rho}{\rho \zeta'(\rho)} + E(x, T),

where the sum runs over non-trivial zeros with |\Im \rho| \leq T, and the error term E(x, T) satisfies E(x, T) = O\left( \frac{x}{T^{1-\epsilon}} \right) for any fixed \epsilon > 0 and sufficiently large T, assuming the non-trivial zeros are simple. Truncating the sum at T = \exp(c \sqrt{\log x}) for a suitable constant c > 0 yields the main asymptotic M(x) \sim \sum_{\rho} \frac{x^\rho}{\rho}, with an unconditional error term of size O\left( x \exp\left( -c' \sqrt{\log x} \right) \right) for some absolute constants c, c' > 0. This approximation highlights the oscillatory nature of M(x), driven by the terms x^\rho / \rho where \Re \rho = 1/2 under the Riemann hypothesis, leading to growth on the order of \sqrt{x} (\log x)^{O(1)}.^[22] The full explicit formula incorporates contributions from the trivial zeros of \zeta(s) at s = -2k for k = 1, 2, \dots, as well as the pole arising from the $1/s factor in the Perron summation formula. Specifically,

M(x) = \sum_{|\Im \rho| \leq T} \frac{x^\rho}{\rho \zeta'(\rho)} + \sum_{k=0}^\infty \operatorname{Res}_{s=-k} \left( \frac{x^s}{s \zeta(s)} \right) + E(x, T),

where the residue at s=0 contributes -2, and the residues at the trivial zeros s = -2k form a convergent power series in x^{-2}:

\sum_{k=1}^\infty \frac{x^{-2k}}{-2k \zeta'(-2k)}.

The derivatives \zeta'(-2k) are related to Bernoulli numbers via the functional equation of \zeta(s), yielding coefficients with alternating signs reminiscent of the Bernoulli series expansion, such as \zeta'(-2k) = (-1)^{k+1} \frac{(2\pi)^{2k} |B_{2k}|}{2 (2k)!} up to sign conventions. This series provides a smooth, decaying correction for large x, analogous to the arithmetic series in von Mangoldt's formula for \psi(x). The overall formula thus combines the primary oscillatory sum over non-trivial zeros with this explicit power series over trivial contributions.^[22] An important average order arises from integrating the explicit formula. Under the Riemann hypothesis,

\int_1^x \frac{M(t)}{t} \, dt = O\left( x^{1/2} (\log x)^2 \right),

derived by applying partial summation to the explicit formula and bounding the resulting sums over zeros using known zero-density estimates. This integral represents a smoothed version of M(x), emphasizing its sublinear growth on average, and serves as a key unconditional measure of the function's oscillatory behavior.^[23]

Connection to the Riemann hypothesis

The Riemann hypothesis implies a strong bound on the growth of the Mertens function M(x). Specifically, assuming the hypothesis holds, M(x) = O(x^{1/2 + \epsilon}) for every \epsilon > 0. This bound is in fact equivalent to the Riemann hypothesis: the hypothesis is true if and only if |M(x)| < x^{1/2 + \epsilon} for any \epsilon > 0 and all sufficiently large x.^[24] Equivalent statements of the hypothesis, such as bounds on prime gaps like p_{n+1} - p_n = O(\sqrt{p_n} \log p_n), are thus tied to the behavior of M(x) through this reformulation. Unconditionally, Charles Jean de la Vallée Poussin established in 1899 that M(x) = O\left(x \exp\left(-c \sqrt{\log x}\right)\right) for some constant c > 0, derived from the prime number theorem with a zero-free region for the Riemann zeta function. This bound has been refined over time, with improvements to the exponent in the error term, such as those by N. G. Chudakov (1948) and later by A. A. Karatsuba and others, yielding stronger zero-free regions and thus sharper estimates for M(x). Recent works have provided explicit versions of these bounds; for example, Lee and Leong (2024) established M(x) \ll x \exp\left( -0.209 (\log x)^{3/5} (\log \log x)^{-1/5} \right) for x \geq 3.^[20]

Bounds and Conjectures

Upper bounds

The Mertens function M(x) satisfies the classical bound M(x) = O\left( \frac{x}{\log^h x} \right) for any fixed h > 0, a result obtained using methods from the prime number theorem with suitable error terms developed in the 1930s. This bound reflects the sublinear growth of M(x), highlighting the cancellation in the sum of the Möbius function due to the distribution of primes. Modern explicit improvements have sharpened this to concrete inequalities. In particular, Ramaré established that |M(x)| < 0.6437752 \frac{x}{\log x} for all x > 1. This provides a precise constant for the leading term in the upper bound, improving upon earlier explicit estimates and facilitating applications in sieve theory and analytic number theory. Further refinements compare M(x) to short partial sums. Lee and Leong proved new explicit bounds, including |M(x)| < c_1(x_0) x \exp\left( -c_2(x_0) \sqrt{\log x} \right) for x \geq x_0 \geq e^{363.11}, where the constants c_1 and c_2 depend on x_0 (e.g., c_1 \approx 0.4188, c_2 \approx 0.1148 at the base value), and similar exponential forms with (\log x)^{3/5} (\log \log x)^{-1/5} terms.^[20] These results, updated through 2024, relate M(x) to truncated sums involving the non-trivial zeros of the Riemann zeta function, offering tighter control for large x without assuming the Riemann hypothesis.^[20]

Mertens conjecture and counterexamples

The Mertens conjecture, proposed by Franz Mertens in 1897, asserts that the absolute value of the Mertens function satisfies |M(x)| ≤ √x for all x ≥ 1.^[4] This statement suggested a tight bound on the growth of M(x), aligning with early observations of its oscillatory behavior near zero relative to √x.^[4] In 1985, Andrew M. Odlyzko and Herman J. J. te Riele disproved the conjecture through an indirect argument relying on extensive numerical computations of the low-lying zeros of the Riemann zeta function.^[25] Their analysis established that lim inf_{x→∞} M(x)/√x < -1.009 and lim sup_{x→∞} M(x)/√x > 1.004, implying that the inequality |M(x)| ≤ √x must fail infinitely often.^[25] Although their method did not yield explicit counterexamples, it confirmed the existence of violations for sufficiently large x. Computational verifications have since confirmed that the conjecture holds up to x ≈ 10^{14}, with the first counterexamples occurring for much larger values.^[4] Recent advancements have refined the location of the smallest counterexample. In February 2025, Kim and Nguyen established a new upper bound showing that the smallest x where |M(x)| > √x satisfies x < exp(1.96 × 10^{19}).^[26] This improves upon prior estimates and highlights ongoing efforts to pinpoint the scale of the disproof using advanced lattice reduction techniques. Regarding the maximal growth of M(x), Steven M. Gonek conjectured that the true order is captured by lim sup_{x→∞} |M(x)| / [√x (log log log x)^{5/4}] = O(1), suggesting slightly larger oscillations than the original conjecture allowed.^[27]

Computation

Algorithms

The Mertens function M(x) = \sum_{k=1}^{\lfloor x \rfloor} \mu(k), where \mu is the Möbius function, can be computed naively by evaluating \mu(k) for each k \leq x using trial division, but this is inefficient at O(x^{3/2}) time. A more practical basic approach employs a linear sieve to compute all \mu(k) up to x in O(x \log \log x) time and O(x) space, followed by a simple prefix sum in O(x) time. The sieve initializes an array for \mu and primes, marking multiples of each prime while ensuring each number is processed only once to determine if it is square-free and count its prime factors. This method is suitable for moderate x up to around $10^8 but becomes prohibitive for larger values due to linear scaling.^[28] For larger x, advanced combinatorial algorithms based on the Meissel-Lehmer method, adapted for the Möbius function, achieve sublinear time. The seminal work of Deléglise and Rivat (1996) provides an elementary algorithm running in O(x^{2/3} (\log \log x)^{1/3}) time and O(x^{1/3} (\log \log x)^{2/3}) space, using sieving up to x^{1/3}, recursive summation over residue classes, and combinatorial identities to reduce the number of terms evaluated. This was a significant improvement over prior elementary methods and enabled computations up to x = 10^{16}. A further refinement by Helfgott and Thompson (2021) introduces a faster elementary algorithm with time complexity O_\epsilon (x^{3/5} (\log x)^{3/5 + \epsilon}) and space O(x^{3/10} (\log x)^{13/10}), or alternatively O(x^{3/5} \log x) time with reduced space O(x^{1/5} (\log x)^{5/3}); it optimizes the recursion depth and sieve segmentation, marking the first asymptotic improvement in the exponent since 1985. These methods trade increased implementation complexity for substantial speedups, with the 2021 algorithm being roughly twice as fast in practice for x \approx 10^{20}.^[29]^[30] Analytic algorithms offer even better asymptotic performance for very large x, leveraging approximations to the Riemann zeta function and Perron's formula. The Lagarias-Odlyzko method (1987), originally for prime counting and adaptable to M(x) via the explicit formula involving zeros of \zeta(s), achieves O(x^{1/2 + \epsilon}) time for any \epsilon > 0 with sufficient precomputation of zeta values; it requires contour integration in the complex plane but demands high-precision arithmetic.^[31] Practical variants incorporate FFT for accelerating the summation over zeta approximations, enabling computations for x > 10^{30} where elementary methods falter. Segment sieving enhances these by computing local μ values in blocks of size \sqrt{x}, reducing memory while maintaining O(\sqrt{x} \polylog x) effective time in hybrid approaches. Specialized techniques suit smaller scales. For n \leq 1000, the Redheffer matrix—a lower-triangular n \times n matrix with 1s on the diagonal, first column, and positions where the row index divides the column index—yields M(n) as its determinant, computable in O(n^3) time via Gaussian elimination, though sparsity allows optimizations to O(n^2). This determinant representation, while theoretically elegant, is impractical beyond n \approx 10^4 due to matrix size. Complexity trade-offs are central: elementary methods like Helfgott-Thompson balance time and space favorably for $10^{15} < x < 10^{25}, using O(x^{1/3}) auxiliary storage, whereas analytic approaches excel asymptotically but incur overhead from numerical stability and prefactoring primes up to \sqrt{x}. For instance, Deléglise-Rivat's higher time exponent is offset by simpler constants, making it preferable in some mid-range implementations, while FFT-augmented segment sieves minimize space to O(\sqrt{x}) at the cost of logarithmic factors. Selection depends on hardware, with modern GPUs accelerating parallelizable sieving in both paradigms.^[30]^[29]

Records

Early computations of the Mertens function played a crucial role in the disproof of the Mertens conjecture. In 1985, Odlyzko and te Riele utilized extensive numerical evaluations involving the non-trivial zeros of the Riemann zeta function up to heights around $3 \times 10^{10}, equivalent in scale to direct computations of M(x) up to approximately $10^{13}, to establish that \liminf_{x \to \infty} M(x)/\sqrt{x} < -1.009. This implied that |M(x)|/\sqrt{x} > 1.009 for infinitely many x, providing the first theoretical evidence of bound violations despite no explicit counterexample at that time.^[32] By the early 2000s, advances in algorithmic efficiency allowed computations of M(x) to extend to x = 10^{20}, enabling detailed studies of the function's oscillatory behavior over vast ranges. In 2011, Oliveira e Silva et al. further extended this using GPU-accelerated methods to compute M(x) up to $10^{22}. The current record was set in 2021 by Helfgott and Thompson, who computed M(x) up to x = 10^{23} using an optimized elementary algorithm with time complexity O(x^{3/5 + \epsilon}). Their work confirmed numerous sign changes in M(x) at extreme scales—for instance, M(10^{19}) = 899990187 > 0 while M(10^{21}) = -3395895277 < 0—and observed values approaching the theoretical bounds, with the maximal computed |M(x)|/\sqrt{x} \approx 1.009 occurring near x \approx 10^{22}, consistent with the predicted growth and violations from earlier theoretical disproofs. These results highlight the function's erratic fluctuations and support the asymptotic predictions derived from zeta function computations.^[33]^[34] No larger-scale computations have been reported as of November 2025, though earlier demonstrations of GPU-based methods suggest potential for accelerated future records. For reference, the Online Encyclopedia of Integer Sequences provides A002321 for tabulated values of M(n) up to moderate n and A028442 for the integers where M(n) = 0.^[33]^[8]^[35]

References

[1]
Mertens Function -- from Wolfram MathWorld
The Mertens function is the summary function M(n)=sum_(k=1)^nmu(k), where mu(n) is the Möbius function (Mertens 1897; Havil 2003, p. 208).Missing: definition | Show results with:definition
[2]
The Estimation of the Mertens Function
The first formula was done by Mertens himself without a proof. The ... In 1897, Mertens based on empirical evidence claimed |M(n)|≤√n , n>1 named ...Missing: original | Show results with:original
[3]
growth of the Mertens function and the Riemann Hypothesis - arXiv
Jan 25, 2021 · Next we study the local properties of the Mertens function dictated by the Mobius coefficients restricted to the square-free numbers.
[4]
Mertens Conjecture -- from Wolfram MathWorld
251). Mertens (1897) verified the conjecture for n<10000 , and this was subsequently extended to n<500000 by von Sterneck (1912; ...
[5]
(PDF) Disproof of the Mertens Conjecture - ResearchGate
Aug 6, 2025 · It took nearly a century for this conjecture to be disproved, by Odlyzko and te Riele [OtR85] in 1985. Their argument consisted of certain ...
[6]
Franz Mertens - Biography - MacTutor - University of St Andrews
Franz Mertens was a Polish-born mathematician who made contributions to a wide variety of areas. He formulated the Mertens conjecture which (had it been true) ...
[7]
Computations of the Mertens Function and Improved Bounds ... - arXiv
Oct 26, 2016 · The Mertens function is defined as M(x) = \sum_{n \leq x} \mu(n), where \mu(n) is the Möbius function. The Mertens conjecture states |M(x)/\sqrt ...
[8]
A002321 - OEIS
The first positive value of Mertens's function for n > 1 is for n = 94. The graph seems to show a negative bias for the Mertens function which is eerily ...
[9]
[PDF] arXiv:1612.01394v2 [math.NT] 15 Dec 2016
Dec 15, 2016 · 1. Introduction. The Mertens function M(n) is important in number theory, especially the calculation. of this function when its argument is ...
[10]
[PDF] RIEMANN ZETA-FUNCTION
Library of Congress Cataloging in Publication Data. Titchmarsh, E. C. (Edward Charles), 1899-. The theory of the Riemann zeta-functwn. Bibliography: p. 1.
[11]
https://doi.org/10.1016/j.camwa.2008.04.033
[12]
[PDF] The Farey Sequence - School of Mathematics
Mar 15, 2012 · The sum of the function at the points in the Farey sequence can be related to Mertens function by the following equality: L(n). X v=1 f(rv) ...
[13]
Eine explizit lösbare Optimierungsaufgabe - SpringerLink
About this chapter. Cite this chapter. Redheffer, R. (1977). Eine explizit lösbare Optimierungsaufgabe. In: Collatz, L., Meinardus, G., Wetterling, W. (eds) ...
[14]
[math/0408263] The Redheffer matrix of a partially ordered set - arXiv
Aug 19, 2004 · Abstract: R. Redheffer described an n\times n matrix of 0's and 1's the size of whose determinant is connected to the Riemann Hypothesis.Missing: 1977 | Show results with:1977
[15]
Properties of Mertens Function - Mathematics Stack Exchange
Feb 27, 2013 · M(n) is the count of square-free integers up to n that have an even number of prime factors, minus the count of those that have an odd number.Prime numbers theorem via Mertens' function - Math Stack ExchangeQuestions on a formula for the Mertens functionMore results from math.stackexchange.com
[16]
Totient Summatory Function -- from Wolfram MathWorld
Phi(n) of the totient function phi(n) is defined by. Phi(n), = sum_(k=1)^(n)phi(k). (1). = sum_(m=1)^(n)msum_(d|m). (2). = sum_(d=1)^(n)mu(d)sum_(. (3). = 1/ ...Missing: floor( | Show results with:floor(
[17]
Mertens function - OeisWiki
Jun 25, 2017 · In 1897, Mertens made the following bold conjecture: Conjecture (Mertens conjecture, 1897). ... The first positive value of Mertens ...
[18]
Sign of Mertens function - MathOverflow
Jun 6, 2013 · Sign of Mertens function ... changes sign infinitely many times when N→+∞. Question: Is there a proof of this statement without Riemann zeta ...How often does the Mertens function vanish? - MathOverflowOscillation of the summatory Möbius function - MathOverflowMore results from mathoverflow.net
[19]
Mertens equimodular matrices of Redheffer type - ScienceDirect.com
Jul 1, 2019 · An infinite matrix whose nth leading principal minor is equal to M ( n ) for all n ≥ 1 is called a Mertens equimodular matrix. We use Riordan ...Missing: exact | Show results with:exact
[20]
New explicit bounds for Mertens function and the reciprocal ... - arXiv
Aug 12, 2022 · In this paper, we establish new explicit bounds for the Mertens function M(x). In particular, we compare M(x) against a short-sum over the non-trivial zeros of ...
[21]
On the mean values of the error terms in Mertens' theorems
Jun 16, 2025 · If 1 / 2 < Θ < 1 , or if Θ = 1 and Assumption 1 holds, then ∫ 2 X E 3 ( x ) d x changes sign infinitely often. The proof of Theorem 1 relies on ...
[22]
[PDF] arXiv:2109.06665v2 [math.NT] 16 Mar 2023
Mar 16, 2023 · summatory function of the Möbius function is the Mertens function ... Analytic properties of Dedekind zeta functions. In this section, we ...
[23]
[PDF] The Distribution of the Summatory Function of the M&#x00F6
In the same spirit as Theorems 1 and 2 we prove that a strong form of the weak. Mertens conjecture is true. ... The inner sum is analyzed by splitting the sum ...
[24]
[PDF] Notes on the Riemann Hypothesis - IMJ-PRG
to have the estimate for the Mertens function M(x), for every > 0,. M(x) = X. 1≤n≤x. µ(n) = O(x1/2+ ) . Unfortunately, nobody has even been able to prove ...
[25]
(PDF) On some reasons for doubting the Riemann hypothesis
Several arguments against the truth of the Riemann hypothesis are extensively discussed. These include the Lehmer phenomenon, the Davenport-Heilbronn ...
[26]
On the mean values of the error terms in Mertens' theorems - arXiv
Nov 28, 2024 · Let E_i(x) denote the error term in each of the three theorems of Mertens on the asymptotic distribution of prime numbers.Missing: Springer | Show results with:Springer
[27]
[PDF] Disproof of the Mertens conjecture - CORE
Odlyzko and te Riele, Disproof of the Mertens conjecture. 139. (cf. [9]) and it led Mertens to publish in 1897 a paper [27] with a 50-page table of. µ(n) and M ...
[28]
https://cp-algorithms.com/algebra/prime-sieve-linear.html
[29]
On the Order of the Mertens Function - ResearchGate
Aug 10, 2025 · The primary objective for Mertens behind introducing the function M(x) (As defined in (1)) was its underlying relation to the location of the ...Missing: Franz | Show results with:Franz<|control11|><|separator|>
[30]
[PDF] A Formula for Mertens' Function and Its Applications - m-hikari.com
Feb 18, 2022 · Von Mangoldt [1897] first proved this relation using a neat /δ type proof. (See Landau [1899] for details and [1909, Vol. II, p. 588] for ...
[31]
Linear Sieve - Algorithms for Competitive Programming
Nov 25, 2023 · The standard way of solving a task is to use the sieve of Eratosthenes. This algorithm is very simple, but it has runtime.Missing: Möbius | Show results with:Möbius
[32]
Computing the Summation of the M¨obius Function P - Project Euclid
Deléglise and Rivat: Computing the Summation of the Möbius Function. 293. For both S1(x; u) and S2(x; u) the number of terms in the sum is at most. X m u p x=m ...
[33]
None
**Abstract and Algorithm Complexity Summary**
[34]
Mertens' function in time O(√x) - MathOverflow
May 2, 2012 · Sieving techniques can determine the Möbius function for all these numbers fast and the time it will take to calculate that sum is of the ...nt.number theory - calculating Möbius function - MathOverflowComputing the Mertens function - MathOverflowMore results from mathoverflow.net
[35]
Disproof of the Mertens conjecture. - EuDML
Odlyzko, A.M., and Riele, H.J.J. te. "Disproof of the Mertens conjecture.." Journal für die reine und angewandte Mathematik 357 (1985): 138-160.Missing: disproved | Show results with:disproved
[36]
[2101.08773] Summing $μ(n)$: a faster elementary algorithm - arXiv
Jan 21, 2021 · Summing μ(n): a faster elementary algorithm. Authors:Harald A. Helfgott, Lola Thompson.
[37]
[1108.0135] Computing the Mertens function on a GPU - arXiv
Jul 31, 2011 · Abstract:A GPU implementation of an algorithm to compute the Mertens function in O(x2/3+{\ko}) time is discussed.
[38]
A028442 - OEIS
- **Definition**: A028442 lists numbers $ k $ where Mertens's function $ M(k) $ (from A002321) equals zero.

n	M(n)
1	1
2	0
3	-1
4	-1
5	-2
6	-1
7	-2
8	-2
9	-2
10	-1
11	-2
12	-2
13	-3
14	-2
15	-1
16	-1
17	-2
18	-2
19	-3
20	-3
21	-2
22	-1
23	-2
24	-2
25	-2
26	-1
27	-1
28	-1
29	-2
30	-3

n	M(n)
1	1
2	0
3	-1
4	-1
5	-2
6	-1
7	-2
8	-2
9	-2
10	-1
11	-2
12	-2
13	-3
14	-2
15	-1
16	-1
17	-2
18	-2
19	-3
20	-3
21	-2
22	-1
23	-2
24	-2
25	-2
26	-1
27	-1
28	-1
29	-2
30	-3

n	M(n)
1	1
2	0
3	-1
4	-1
5	-2
6	-1
7	-2
8	-2
9	-2
10	-1
11	-2
12	-2
13	-3
14	-2
15	-1
16	-1
17	-2
18	-2
19	-3
20	-3
21	-2
22	-1
23	-2
24	-2
25	-2
26	-1
27	-1
28	-1
29	-2
30	-3