On counterexamples to the Mertens conjecture

Seungki Kim, Phong Q. Nguyen · 2025

Read On counterexamples to the Mertens conjecture by Seungki Kim, Phong Q. Nguyen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-21021.txt.

Introduction

Seungki Kim and Phong Nguyen wrote a mathematics paper in two thousand twenty-five tightening the hunt for a counterexample to the Mertens conjecture. The conjecture, a once-plausible claim about the Mertens function's growth, is known to be false, but no explicit counterexample has ever been exhibited. Knowing where the smallest one must lie guides the search.

Using state-of-the-art lattice algorithms, the authors improved the upper bound on the lowest counterexample. The new bound sits near exp of about two times ten to the nineteenth. That is far below the earlier conjectured scale set by Kotnik and van de Lune, near exp of about five times ten to the twenty-third. The improvement shrinks the range in which the first violation can hide.

Catalog record

CREATORSeungki Kim, Phong Q. Nguyen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-21021

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On counterexamples to the Mertens conjecture Seungki Kim, Phong Q. Nguyen Abstract . We use state-of-art lattice algorithms to improve the upper bound on the lowest counterexample to the Mertens conjecture to ≈ exp ⁡ ( 1.96 × 10 19 ) \approx\exp(1.96\times 10^{19}) , which is significantly below the conjectured value of ≈ exp ⁡ ( 5.15 × 10 23 ) \approx\exp(5.15\times 10^{23}) by Kotnik and van de Lune [ KvdL04 ] . 1. Introduction The Mertens conjecture [ M97 ] , dating back to 1897, is a statement about the growth rate of the Mertens function M(x):=\sum_{1\leq n\leq x}\mu(n), where \mu(n) is the Möbius function \mu(n)=\begin{cases}(-1)^{k}&\mbox{if $n$ is squarefree, and has $k$ distinct prime factors,}\\ 0&\mbox{if $n$ is not squarefree.}\end{cases} The size of M(x) is of interest in number theory, since it is closely related to the size of the real parts of the zeroes of the Riemann zeta function \zeta(s) . For example, a short argument (See e.g. [ OtR85 , Sec. 2] ) shows that if M(x)=O(x^{\theta}) , then the Riemann zeta function \zeta(s) has no zeroes on the half-plane \mathrm{Re}\,s>\theta . For \theta=1/2+\varepsilon for arbitrarily small \varepsilon>0 , the latter statement is the famous Riemann hypothesis. The Mertens conjecture is a much bolder claim that (1.1) |M(x)|<x^{1/2}\mbox{ for all }x>1. It took nearly a century for this conjecture to be disproved, by Odlyzko and te Riele [ OtR85 ] in 1985. Their argument consisted of certain insights from classical analytic number theory, and, perhaps surprisingly, the use of a lattice reduction algorithm. No alternative (dis)proof that does not rely on lattice reduction is known to this day. A natural follow-up is to ask about the size of the smallest counterexample \mathfrak{x} to the Mertens conjecture ( 1.1 ). This is also related to the estimation of the growth rate of M(x) , for which several different conjectures exist. For example, the experimental work by Kotnik and van de Lune [ KvdL04 ] suggests that (1.2) |M(x)x^{-1/2}|\approx 1/2\cdot\sqrt{\log\log\log x} along the local extrema of M(x)/x^{1/2} , from which they derive the conjecture that (1.3) \mathfrak{x}\approx\exp(5.15\times 10^{23}), since 1/2\cdot\sqrt{\log\log(5.15\times 10^{23})}\approx 1 . It is also possible to give rigorous upper bounds on \mathfrak{x} , thanks to Pintz [ P87 ] . The original data of Odlyzko and te Riele [ OtR85 ] , under the theorem of Pintz [ P87 ] , translates to the statement that \mathfrak{x}<\exp(3.21\times 10^{64}) . The later more extensive set of experiments by Kotnik and te Riele [ KtR06 ] led to the improvement \mathfrak{x}<\exp(1.59\times 10^{40}) . Saouter and te Riele [ StR14 ] refined the estimates given in [ P87 ] , and also ran more experiments of the same kind, which resulted in \mathfrak{x}<\exp(1.004\times 10^{33}) . [ OtR85 ] states that their achievement was possible thanks to a then-breakthrough in lattice reduction, the LLL algorithm due to Lenstra, Lenstra, and Lovász [ LLL82 ] . [ KtR06 ] and [ StR14 ] also used LLL, and so did the relatively recent works such as Hurst [ H18 , Theorem 6.1] . However, over the last decade, there has been a huge amount of progress in lattice reduction techniques — largely motivated by the emergence of post-quantum cryptography based on computationally hard lattice problems. Noticing this, one would naturally be inclined to apply them to the context of the Mertens conjecture. Kim and Rozmarynowycz [ KR23 ] was the first to point this out and to partially implement this idea, by simply replacing LLL with the BKZ algorithm ( [ SE94 ] , [ CN11 ] ). As a result, they obtained a further improvement that \mathfrak{x}<\exp(1.017\times 10^{29}) . [ KR23 ] was, however, still far from taking the full advantage of the recent advances in lattice problems. In this work, we employ state-of-art lattice point enumeration techniques [ LN13 , GNR10 ] in search of a tighter upper bound on the lowest counterexample to the Mertens conjecture ( 1.1 ). As explained in Section 3 below, this is a much more natural and efficient strategy than running lattice reduction hundreds to thousands of times, which has been the method chosen by all the previous works mentioned above. We also give a careful consideration to the family of the lattices under question, since such an understanding is important for both predicting the outcome and improving the performance of the algorithm. As a result, we improve the choice of the lattice made by [ OtR85 ] in a couple of ways, for the first time in the past 38 years. Moreover, we notice that our lattices are extremely orthogonal, with one unusually short vector; we adapt the enumeration algorithm accordingly to exploit this special shape, effectively speeding up our search by a factor of a few millions. Thereby we were able to find a number of data points that beat the previous record and even the conjecture ( 1.3 ) by several orders of magnitude. The best we found, which took us barely half a day on a single core, implies that (1.4) \mathfrak{x}<\exp(1.96\times 10^{19}), which is below ( 1.3 ) by a factor of \approx 26276 in the exponent. This would substantially impact the credibility of ( 1.2 ). A more extensive application of the methods of the present paper may help search for an alternative estimate on the growth rate of M(x) — see Section 4.2 below. There exist also numerous other applications of the computational aspect of lattices to number theory than the Mertens conjecture, see e.g. Simon [ S10 ] . We hope that our work helps inform the community of the recent advances in lattice computations, and encourages revisiting some of the old problems with the new arsenal. Organization In Section 2, we briefly review the method of Odlyzko-te Riele [ OtR85 ] and other works in the literature, in order to help the reader understand and put our work into perspective. In Section 3, we describe our experiment in detail. We conclude the paper in Section 4 with a discussion on further research directions to which the methods introduced herein may be applied. Reproducibility The present work involves significant data. Data files and/or source codes allowing to reproduce the data are available on https://zenodo.org/records/10775723 . 2. A review of the previous works 2.1. The original argument of [ OtR85 ] Resorting to proof by contradiction, let us assume the truth of the Mertens conjecture. As explained in [ OtR85 , Sec. 2] , this implies in particular that all nontrivial zeroes \rho of \zeta(s) satisfy \mathrm{Re}\,\rho=1/2 (the Riemann hypothesis), and that they are all simple zeroes. For each such \rho with \mathrm{Im}\,\rho>0 , let us write \gamma:=\mathrm{Im}\,\rho , \alpha:=|\rho\zeta^{\prime}(\rho)|^{-1} , \psi:=\mathrm{arg}(\rho\zeta^{\prime}(\rho)) ; conversely, whenever we write \gamma , \alpha , or \psi , we are referring to the corresponding zero \rho of \zeta(s) . Then, for a certain increasing sequence \{T_{n}\} with n\leq T_{n}\leq n+1 , it holds that (see e.g. [ KtR06 , (3) and (4)] or [ KvdL04 , Sec. 2 and 3] ) (2.1) q(x):=\frac{M(x)}{x^{1/2}}=2\lim_{n\rightarrow\infty}\sum_{0<\gamma<T_{n}}\alpha\cos(\gamma y-\psi)+O(x^{-1/2}), where we write y:=\log x for short. Recall that the Mertens conjecture states that |q(x)|<1 for x>1 . ( 2.1 ) suggests one possible strategy for disproving (

Read the complete text