The Möbius Function and Mertens Function

I had come across the Möbius function before but didn't see it as all that important. However, I was reminded of it recently when I encountered a Numberphile video on Mertens conjecture (uploaded 23rd January 2020).

In number theory, we define the Mertens function as:$$M(n) = \sum_{1\le k \le n} \mu(k)$$where \( \mu (k)\) is the Möbius function. The Mertens conjecture is that for all \(n > 1\): $$\left| M(n) \right| < \sqrt { n }$$To quote from Wikipedia:

In mathematics, the Mertens conjecture is the disproven statement that the Mertens function \(M(n)\) is bounded by \( \sqrt {n}\), which implies the Riemann hypothesis. It was conjectured by Thomas Joannes Stieltjes in an 1885 letter to Charles Hermite (reprinted in Stieltjes (1905)) and Franz Mertens (1897), and disproved by Andrew Odlyzko and Herman te Riele (1985). It is a striking example of a mathematical proof contradicting a large amount of computational evidence in favour of a conjecture.

I set about writing a program in SageMath to plot the first million values of the Mertens function. I managed to execute it in SageMathCell but the code was clunky as I had to get the program to determine the values of -1, 0 and 1 based on the factorisation. Later I realised that the Möbius function would replace the need for this. In SageMath, the spelling is moebius and moebius(1) --> 1 etc. So let's define the Möbius function:

For any positive integer n, \(μ(n)\) has values in {−1, 0, 1} depending on the factorisation of \(n\) into prime factors:$$\mu(n) =
  \begin{cases}
    1       & \quad \text{if } n \text{ is a square-free positive integer with an even number of prime factors}\\
   -1  & \quad \text{if } n \text{ is a square-free positive integer with an odd number of prime factors}\\
0  & \quad \text{if } n \text{ has a squared prime factor}
  \end{cases}$$Figure 1 shows the results of plotting the first one million values of the Möbius function. Here is the permalink to the SageMathCell calculation.

Figure 1

The square root of \( \pm \) 1,000,000 is \( \pm \) 1,000 and as can be seen the function is well within those bounds. However, as mentioned earlier, the bounds are eventually exceeded. Sometimes, instead of \(M(n) \), the function \(m(n) \) is used where:$$m(n)=\frac{M(n)}{\sqrt{n}}$$For the Mertens conjecture to hold, the following condition would be necessary: \(-1 <m(n)<1\). However, for enormously large values of \(n\), it has been shown that \(m(n)<-1.837625 \) and \(m(n)>1.826054\) are possible.

Proth Numbers

Today I turned 25857 days old and was surprised to come across a number property in Numbers Aplenty that I hadn't encountered before. Or so I thought. The property referred to Proth Numbers and the previous such number was 25601 that occurred on May 7th 2019. On that occasion, I'd chosen to ignore it for whatever reason.

Proth numbers are named after a French mathematician François Proth (1852–1879). He was a French self-taught mathematician farmer who lived near Verdun, France. He doesn't earn an entry in the MacTutor History of Mathematics archive. However, David Wells mentions him in his book Prime Numbers: The Most Mysterious Figures in Math. Figures 1 and 2 contain the reference:

Figure 1

He continues on the next page:

Figure 2

In the case of 25857, the number can be represented as \( 101 \times 2^8 + 1 \) but it is not prime because it factorises to \( 3^2 \times 13^2 \times 17 \). The previous Proth number 25601 however, is a Proth prime and can be represented as \( 25 \times 2^{10}+1 \). I downloaded the proth.exe program referred to in Wells' book and ran it on my Mac using Wine. The program hasn't been updated since May of 2004 but it still does the job. A result, identifying 25601 as a prime, is shown in Figure 3:

Figure 3

The \( a =19\) refers to the fact that when N is prime, then:$$ a^{\frac{N-1}{2}}+1 \equiv 0 \mod{N}$$So when \(N = 25601\) we have:$$ 19^{\frac{25601-1}{2}}+1 \equiv 0 \mod{25601}$$The Wikipedia page on Proth primes has some interesting references including the following in reference to the primality test:

This test is a Las Vegas algorithm: it never returns a false positive but can return a false negative; in other words, it never reports a composite number as "probably prime" but can report a prime number as "possibly composite".

The Wikipedia link to the Las Vegas algorithm states that:

Las Vegas algorithms were introduced by László Babai in 1979, in the context of the graph isomorphism problem, as a dual to Monte Carlo algorithms. Babai introduced the term "Las Vegas algorithm" alongside an example involving coin flips: the algorithm depends on a series of independent coin flips, and there is a small chance of failure (no result). However, in contrast to Monte Carlo algorithms, the Las Vegas algorithm can guarantee the correctness of any reported result.

The next Proth number after today's 25857 is 26113 and it is also a Proth prime with \(a=7\). This will occur on Wednesday, September 30th 2020. Thus:$$7^{\frac{26113-1}{2}}+1 \equiv 0 \mod{26113}$$