Monday, April 27, 2015

"On Liouville's Function" by Lehman, 1960

I calculate some of the results in the paper On Liouville's Function, R. Sherman Lehman, Math. Comp. 14 (1960), 311-320 with Mathematica. I find this paper interesting because it is an old paper that used a computer to find an explicit counterexample to a conjecture of Polya. I also find it interesting because thinking about how to compute number theoretic functions helps to understand the formulas better. The names of the sections below are the same as in the paper. Equation numbers refer to the equations in the paper.

1. Introduction

This section is clear. I found that in this paper it is shown that 906,150,257 is the smallest value for which \( L(x)>0 \). Lehman got thus very close to the minimal \( x \).

2. Background and Heuristic Considerations

Formula (1) can be easily calculated if one does not pay attention to the form of the error term and the behaviour of the Mellin-integral at infinity. I now calculate by brute force how many zeros to use for several values of \( T\).

For \( T = 100 \), I need 29 zeros, because the 30'th zero is the first zero with imaginary part more than 100.
Similarly, for \( T = 200 \), I need 79 zeros.
For \(T = 500\), I need 269 zeros.
For \(T = 1000\), I need 649 zeros
Here is an implementation of the function \(A_T(u) \) . The formulas are taken directly from the first page in the paper.

As a check, I calculate some values from page 2. The first calculation is slow, but because the functions \( \alpha \) and \(\gamma\) remember their values, subsequent function calls are fast.

On page 2, Lehman writes that he first calculated the function over the interval 12.5(0.01)20.69. He does not show a figure; but here is a figure anyway.

I now reproduce figure 1; I get indeed a very similar figure as the one in the paper.

3. A Formula for Calculating \( L(x) \)

Formula (4) follows easily from a special case of theorem 2.4.1 in Murty in combination with exercise 1.1.11 in the same book.

4. Numerical Computations

The preliminary Computations: a table of \( \lambda(n) \) and \( L(n) \) for \( n<= 10^6 \), and also a preliminary table for \(\xi(l) \), note that I only calculate this for \( x/w = 1000 \). I do these calculations by brute force, Mathematica needs only around 30 seconds for each table, so it is not worthwhile now to think how to make the calculations faster.
I implement the function \( L(x) \) using the formula in Theorem 1. I do not use the more efficient formula on the top of page 5. Lehman mentions on page 6 that he took special care when calculating \( \lfloor \sqrt{y} \rfloor \) when \( \sqrt{y} \) is an integer. I do not take this extra care; I just hope Mathematica is sufficiently accurate. A final minor difference between the calculation below and the paper is that I take \( v \) to be always an integer, because otherwise the code to sum over integers \( <v \) looks ugly. I check the values in table 1 and I also calculate the timing. Most time seems to be spend in the double sum in term1.

Finally, I check \( L(906180359) = 1 \)


  • In this paper, there is more background and also more calculations.
  • I made this file by copy/pasting individual cells from a Mathematica notebook to a png file. Is there a faster way to convert a notebook to a blog post?
  • Please ask if you would like to have the Mathematica file.
  • The calculations were performed in Mathematica 10 Home Edition.

No comments:

Post a Comment