August 17, 2024

Values of the Sum of the Liouville Lambda Function

This article is about a fun computing project, not math. The mathmatical aspects of this concept and how it connects to other (very important) topics is beyond the scope of this article and my understanding. I will link some resources, including OEIS formatted like this: A002819. This topic is very interesting so I encourage you to research this yourself.

Liouville function and its sums

The Liouville function (commonly expressed as λ(n); see A008836) is defined for a given natural number, n, as -1 raised to the power of the number of prime divisors n has, counted with multiplicity (Ω(n); see A001222).

For input n, the Liouville function will output -1 for any number with an odd big omega like primes and perfect cubes (except 1); it will output 1 for numbers with an even big omega like semiprimes and perfect squares. These examples are in no way exhaustive, the function is defined for all natural numbers.

Mathematicians have found it useful to study the partial sums of the Liouville function or its variants because it is connected the the distribution of primes thus have important consequences. Sums of λ(n)/n is studied but this page will focus on the partial sum of just the function (A002819): the sum of all Liouville function values for all natural numbers up to a value; I will refer to this as the summatory Liouville funciton, or L(n) for short.

Polya's conjecture

George Pólya showed that if most natural numbers have an odd number of prime factors (if L(n) is always negative), the Riemann hypothesis would be implied. This was proven false by C. Brian Haselgrove in 1958 and a counterexample via L(n) was found later. The smallest counterexample is L(906150257) = 1.

Program

The counterexample is pretty large which is what made me interested in it. This just seems like a pretty interesting program in general. I have written a program to calculate values of L(n).

All the code detailed explaination is here.

Naive approach

In December 2021, as one of my first projects in C, I wrote a program that naively calculates L(n). See it here (commit 1532234). The program was slow because it repeated a lot of computations.

Optimizations using memory

I will gloss over details here. Details can be found in the code and readme file.

λ is completely multiplicative so the programs keeps a big table of already computed values to speed everything up. The size of the table can be adjusted at compile-time but it's typically about 10-500 billion values. Note that each value only uses one bit.

The program spends a lot time doing trial division if a number doesn't have a small divisor, so I have implemented a prime number table, generated at start up using Sieve of Eratosthenes, that contains all 203280221 primes less than 2³². For values larger than that, I used a hashed Miller-Rabin test documented here. The program frequently checks if a number is primes.

The program also keeps 30030 value long table of GCD(1, n) for n less than 30030. Note that 30030 is a primorial (see A002110). This is used for an initial division.

Multithreading

I used the unix pthreads library. Both the main computation and the generation of the primes table is multithreaded. The program computes values in blocks to be processed by a single main thread.

Performance

A barebones version of the program can sum and store each lambda value to 1 billion in about 30 second on my Intel Core Ultra & 155H running WSL.

Note that if you just want L(n) at a specific value, you can skip a lot of values due to how the function behaves, my goal is to evaluate all values up to a certain number and isolate interesting results.

Computation goals

The program outputs a line if the following event happens. All this will be available in the sections below.

• L(n) is zero. See A028488
• L(n) hits a new maximum or minimum record. See A051470 and A002053 respectively.
• λ is the same value for a record length. Equivalently, L(n) is monotonic over the integers for a record interval. See A175201 and A175202.
• Periodic output for graphs, analysis, and checkpointing.

Also see this section of the readme.

All these events are outputted to a log file, the data will be presented below.

Computation, data integrity, and performance

I used to the free sign up credits on Google Cloud Platform and Oracle Cloud Infrastructure to run my programs. On free accounts, Google only let me run 8 vCPUs and Oracle only let me run 24, so the computation took a while. I will refer to the OCI VM as my primary computer and the GCP one as my secondary. Paying for them would've been too expensive for my level of interest in this project. Anyways, if you or your insitution have a supercomputer cluster I can borrow, let me know.

I ran my programs on both computers with a 192 billion value long table which took 24 GB. There is also the 4 billion bit prime table which is 500 MB. The programs used about 25 GB of memory.

Data integrity

Due to the nature of the function, one slient hardware error can cascade into the results. The servers running the program probably has ECC but I have implemented no integrity checks. Running the program on two independent machines mitigates most of my concern but there is still a chance that big cosmic rays is out to get me.

The most impactful error would be in low values of the primes table.

The studies on memory error rates states values all over the place, so I can't do fun estimations and weird comparisons comparing memory bit half life to uranium or something.

Values up to 604.7 billion was run on both primary and secondary computers with matching results.

Performance

Primary computation took about 980938 seconds (11.4 days) where it summed 15589 blocks of 2²⁶ values, in total about 1.046 trillion values. For the cumulative average speed of about 1.066 million values per second.

Above shows the increasing time it takes for each block to evalulated, accurate to the second. Note that the jumps happen at multiples of the tail table (192 billion).

Results

Note that THESE RESULTS ARE NOT GURANTEED TO BE CORRECT. The chances are low, but there may be invisible bugs or hardware errors that tampered with the results. Again, values up to 604.7 billion are ran twice with matching results. Additionally, outputs up to a trillion has been check against the OEIS (A090410)

Periodic values

See also: A002819 and A090410

File: Values up to 32768, every value

File: Values up to 1046000000000, sampled every 100000000

Value of the first trillion. One point every 10⁸

Value of the first 100 billion. One point every 10⁸

Zeros

See also: A028488

The 252 zeros for values up to a trillion is as follows: 2, 4, 6, 10, 16, 26, 40, 96, 586, 906150256, 906150294, 906150308, 906150310, 906150314, 906151516, 906151576, 906152172, 906154582, 906154586, 906154590, 906154594, 906154604, 906154606, 906154608, 906154758, 906154760, 906154762, 906154764, 906154766, 906154768, 906154770, 906154786, 906154788, 906154790, 906154792, 906154794, 906154798, 906154824, 906154826, 906154828, 906154830, 906154836, 906154838, 906154856, 906154858, 906154864, 906154882, 906154884, 906154886, 906154888, 906154890, 906154892, 906154894, 906154908, 906154912, 906154914, 906154928, 906154930, 906154934, 906154936, 906154946, 906154950, 906154954, 906180358, 906180362, 906180364, 906180366, 906180370, 906180374, 906180376, 906180386, 906180388, 906180390, 906180518, 906180520, 906180524, 906180534, 906180536, 906180554, 906192698, 906192700, 906192702, 906192846, 906192866, 906192904, 906192906, 906192966, 906192970, 906192972, 906192976, 906192978, 906192984, 906193228, 906193234, 906193244, 906193246, 906193248, 906193302, 906193304, 906193308, 906193310, 906193336, 906193338, 906193344, 906193418, 906193420, 906193440, 906193464, 906193466, 906193472, 906193474, 906193476, 906193478, 906194914, 906194920, 906194922, 906194924, 906194930, 906194932, 906194946, 906194948, 906194950, 906194968, 906194978, 906194980, 906195096, 906195098, 906195100, 906195104, 906195106, 906195108, 906195150, 906195152, 906195296, 906195298, 906195986, 906195988, 906195990, 906196008, 906196010, 906196014, 906196016, 906196040, 906196042, 906196044, 906196052, 906196056, 906196072, 906196074, 906196076, 906196080, 906196082, 906196092, 906196098, 906208712, 906208714, 906208730, 906208732, 906208734, 906209040, 906209064, 906209066, 906209068, 906209070, 906209224, 906209226, 906209228, 906209230, 906209232, 906209236, 906209238, 906209240, 906209242, 906209272, 906209282, 906209284, 906477702, 906477714, 906477734, 906477812, 906477818, 906477866, 906477868, 906477870, 906477900, 906477902, 906477906, 906477928, 906477932, 906477934, 906477936, 906486640, 906486804, 906486806, 906486808, 906486810, 906486812, 906486816, 906486818, 906486820, 906486832, 906486842, 906486854, 906486856, 906486908, 906486914, 906486916, 906486974, 906487002, 906487004, 906487064, 906487066, 906487068, 906487070, 906487072, 906487078, 906487084, 906487086, 906487102, 906487104, 906487180, 906487184, 906487186, 906487190, 906487192, 906487194, 906487204, 906487206, 906487258, 906487260, 906487262, 906487264, 906487270, 906487288, 906487932, 906487934, 906487936, 906487938, 906487948, 906487974, 906487994, 906488002, 906488004, 906488006, 906488008, 906488010, 906488022, 906488026, 906488066, 906488068, 906488076, 906488080

The next block of zeros is at around 351 trillion.

Minimums and maximums

See also: A002053 and A051470

File: Minimums up to a trillion (25MB)

File: Maximums up to a trillion

Within the first 1.046 trillion, the minimum value is -1038386 at 835018639060. The maximum is 829 at 906316571.

I will link files with the position and values of all minimums and maximums below.

Repeats

See also: A175201 and A175202

0 is 1 or even big omega, and 1 is -1 or odd big omega.

The position of longer repeats is roughly exponential

Raw logs and file checksums

File: primary log

File: secondary log

hsing@hsing:/mnt/c/Users/hsing/Desktop/website/main-website/liouville-lambda/resource$ du -h *.txt
384K    every.txt
16K     maxrelease.txt
25M     minrelease.txt
23M     output-gcp.txt
26M     output-oci.txt
308K    periodicrelease.txt
hsing@hsing:/mnt/c/Users/hsing/Desktop/website/main-website/liouville-lambda/resource$ md5sum *.txt
96004810c1066d4ca460ddfc2d157a6b  every.txt
c0e9397c14d50a14d36f7ba994a36f19  maxrelease.txt
e813f20e77044eb7d76d7ad177af66c4  minrelease.txt
193e86d545cfc8b161361d4cecce34ff  output-gcp.txt
f3cac0fb02febcd059906c4267d53ab8  output-oci.txt
76a401816220993958e22aec3253a6f5  periodicrelease.txt
hsing@hsing:/mnt/c/Users/hsing/Desktop/website/main-website/liouville-lambda/resource$ sha1sum *.txt
827f6d63555f66092767764eac1b126cae6e87d7  every.txt
e5ea2da8c2c039d101dab0a49a43c8f6f1ff0c59  maxrelease.txt
758d54e0b47c478d4754bce47d7b534d3141d062  minrelease.txt
9a8b5ec8df6b6ef70c6f279c78eb5cbf572587d8  output-gcp.txt
85621ba52fdf40f7b46a6a445d6d0668d4d6f73b  output-oci.txt
d173364ca47a81e9b61106b33d27c58623dc1be9  periodicrelease.txt
hsing@hsing:/mnt/c/Users/hsing/Desktop/website/main-website/liouville-lambda/resource$
    

See also

Borwein, P., Ferguson, R., & Mossinghoff, M. (2008). Sign changes in sums of the Liouville function. Mathematics of computation, 77(263), 1681-1694.

Lehman, R. S. (1960). On Liouville's function. Mathematics of Computation, 311-320.

Tanaka, M. (1980). A numerical investigation on cumulative sum of the Liouville function. Tokyo Journal of Mathematics, 3(1), 187-189.

Errors, questions, comments, concerns

Contact me at my email listed below.