Numerical verification of Littlewood's bounds for |L(1,χ)|
A. Languasco

In this page I collect some links concerning the computation of the values of |L(1,χ)|, where χ is a Dirichlet character mod q.
In my paper [2] I introduced a fast algorithm to compute the values of |L(1,χ)| which is based on a FFT strategy. I was able to evaluate such functions for every odd prime q up to 10⁷; using such data we verified, for q in such a range, Littlewood's estimates in [3] and the Lamzouri-Li-Soundararajan [1] effective bounds.
Previous computations were performed by Shanks [4] in 1973 and Williams-Broere [5] in 1976.

I describe here the Pari/GP scripts and the C programs we developed and used to achieve these results. More detailed instructions on how to use the programs are here: How_it_works.

I have to state the obvious fact that if you wish to use some of the softwares below for your own research, you should acknowledge the author and cite the relevant paper in which the program was used first. In other words, you can use them but you have to cite the paper of mine that contains such programs. If you are wondering why I am stating something so trivial, please have a look at P0 here: A.Languasco-Programs

Since several people started to use my programs without citing my papers, I decided to remove them from this site. (08/19/2022)
The software is now GPL-licensed and with a DOI: 10.24433/CO.2950741.v1
A Code Ocean capsule (able to run an example of use of such a program) is here:

Pari/GP scripts

MaxL-direct-final.gp: Pari/GP script. It can be used via gp2c. The function to be run is:
maxL_direct (r₁,r₂,defaultprecision).
Input: 2< r₁ < r₂, two integers; defaultprecision is the number of digits requested.
Output: the value M_q (distinguishing between even and odd characters) for every odd prime q such that r₁≤q≤r₂ and the running times.
Comment: it uses the lfun command of Pari/GP and the Conrey description of Dirichlet characters. Examples on how to use the function and computational results are collected towards the end of the file.

MaxL-loggamma-final.gp: Pari/GP script. It can be used via gp2c. The function to be run is:
maxL_logGamma (r₁,r₂,defaultprecision).
Input: 2< r₁ < r₂, two integers; defaultprecision is the number of digits requested.
Output: the value M_q (distinguishing between even and odd characters) for every odd prime q such that r₁≤q≤r₂ and the running times.
Comments: it computes first the values of log(Γ) and then obtains m_q with a trivial implementation of the sum over a, 1≤a≤q-1. Examples on how to use the function and computational results are collected towards the end of the file.

MinL-direct-final.gp: Pari/GP script. It can be used via gp2c. The function to be run is:
minL_direct (r₁,r₂,defaultprecision).
Input: 2< r₁ < r₂, two integers; defaultprecision is the number of digits requested.
Output: the value m_q (distinguishing between even and odd characters) for every odd prime q such that r₁≤q≤r₂ and the running times.
Comment: it uses the lfun command of Pari/GP and the Conrey description of Dirichlet characters. Examples on how to use the function and computational results are collected towards the end of the file.

MinL-loggamma-final.gp: Pari/GP script. It can be used via gp2c. The function to be run is:
minL_logGamma (r₁,r₂,defaultprecision).
Input: 2< r₁ < r₂, two integers; defaultprecision is the number of digits requested.
Output: the value m_q (distinguishing between even and odd characters) for every odd prime q such that r₁≤q≤r₂ and the running times.
Comments: it computes first the values of log(Γ) and then obtains m_q with a trivial implementation of the sum over a, 1≤a≤q-1. Examples on how to use the function and computational results are collected towards the end of the file.

C programs
Examples on how to use the following programs and the results obtained with them are contained in the directory: results.
Towards the end of each file are inserted the compilation instructions for some of the machines used for performing the actual computations.

Programs:
MaxLMinL_main.c: C program.
input: an odd prime q.
output: the ascii file primroot.res contains q and g, a primitive root mod q.

FFT step: (using the FFTW library): All the following programs use the FFTW-guru64 interface (which also allows to transform sequences having dimension larger than 2³¹-1).

MaxLMinL-fftwl-inplace.c: C program.
It computes M_q and m_q via FFT; it needs the fftw library; it uses the INPLACE transforms (less RAM but less reliable on small values of q). It's the long double precision version. Values of log(Γ) are computed using the internal function of the C programming language.
input: the ascii files primroot.res.
output: the values M_q and m_q (distinguishing in both cases between even and odd characters) and the running times. It also detects the characters such that |L(1,χ)| is minimal/maximal (to understand the notation, see [2], section 2.2).

MaxLMinL-fftwl-outplace.c: C program.
It computes M_q and m_q via FFT; it needs the fftw library; it uses the OUTPLACE transforms (more RAM but more reliable on small values of q). It's the long double precision version. Values of log(Γ) are computed using the internal function of the C programming language.
input: the ascii files primroot.res.
output: the values M_q and m_q (distinguishing in both cases between even and odd characters) and the running times. It also detects the characters such that |L(1,χ)| is minimal/maximal (to understand the notation, see [2], section 2.2).

run_maxLminL.sh: bash script.
Read a set of odd primes from the ascii file primes.txt; for each of these primes it runs MaxLMinL-fftwl-inplace.exe and collects the results in two csv files. More details are collected in the How_it_works file.
input: the ascii files primes.txt.
output: the files MaxL.csv, MinL.csv.

Numerical results
The numerical results presented in [2] can be retrieved as follows.
The results for m_q and M_q for every prime between 3 and 1000 are contained towards the end of each gp script.
The results for m_q and M_q for every prime between 3 and 10⁷ were obtained with the C programs (and the FFTW library) on a Dell Optiplex machine (Intel i5-7500 processor, 3.40GHz, 16 GB of RAM and running Ubuntu 18.04.5); they can be found in a csv file here: results. The analysis on this file were performed using a python3-pandas script (included here.).
In the directory plots you can find the scatter plots of m_q and M_q for every prime between 3 and 10⁷.

Proofs of Theorems 1-2 in [2]
The verification of the inequalities presented in Theorems 1-2 of [2] uses two python3 scripts on the numerical results previously mentioned. They can be downloaded here: python3-pandas scripts.

To verify Theorem 1: run the script named analysis-MaxL.py on the numerical results contained in MaxL-result.csv; the output file named analysis.txt contains the information to verify Theorem 1.
To verify Theorem 2: run the script named analysis-MinL.py on the numerical results contained in MinL-result.csv; the output file named analysis.txt contains the information to verify Theorem 2.

Algorithms for log(Γ) and psi
In sections 3 and 4 of [2] we described some algorithms to compute log Γ(x) and ψ(x), x ∈ (0,1). Here we provide their Pari/GP implementation.

ale_loggamma.gp: Pari/GP script. It can be used via gp2c. The function to be run is: ale_loggamma(x,y).
Input: reads the file primroot.res containing a prime q and g, a primitive root mod q; x,y are two integers in [0, q-2].
Output: a file named precomp_aleloggamma-x-y.res containing the values log Γ(a_k/q), a_k≡ g^k mod q, x ≤ k ≤ y.
Towards the bottom of the file you can find some examples.

ale_loggamma_dif_odd.gp: Pari/GP script. It can be used via gp2c. The function to be run is: ale_loggamma_dif_odd(x,y).
As before, but it computes log Γ(a_k/q) - log Γ(1 - a_k/q), a_k≡ g^k mod q, x ≤ k ≤ y.
Towards the bottom of the file you can find some examples.

ale_loggamma_dif_even.gp: Pari/GP script. It can be used via gp2c. The function to be run is: ale_loggamma_dif_even(x,y).
As before, but it computes log Γ(a_k/q) + log Γ(1 - a_k/q), a_k≡ g^k mod q, x ≤ k ≤ y.
Towards the bottom of the file you can find some examples.

ale_psi.gp: Pari/GP script. It can be used via gp2c. The function to be run is: ale_psi(x,y).
Input: reads the file primroot.res containing a prime q and g, a primitive root mod q; x,y are two integers in [0, q-2].
Output: a file named precomp_alepsi-x-y.res containing the values ψ(a_k/q), a_k≡ g^k mod q, x ≤ k ≤ y.
Towards the bottom of the previous file you can find some examples.

ale_psi_dif_odd.gp: Pari/GP script. It can be used via gp2c. The function to be run is: ale_psi_dif_odd(x,y).
As before, but it computes ψ(a_k/q) - ψ(1 - a_k/q), a_k≡ g^k mod q, x ≤ k ≤ y.
Towards the bottom of the file you can find some examples.

ale_psi_dif_even.gp: Pari/GP script. It can be used via gp2c. The function to be run is: ale_psi_dif_even(x,y).
As before, but it computes ψ(a_k/q) + ψ(1 - a_k/q), a_k≡ g^k mod q, x ≤ k ≤ y.
Towards the bottom of the file you can find some examples.

References

Some of the papers connected with this project are the following.

[1] Y. Lamzouri, X. Li, K. Soundararajan, Conditional bounds for the least quadratic non-residue and related problems, Math. Comp. 84 (2015), 2391--2412. Corrigendum ibid., Math. Comp. 86 (2017), 2551--2554.

[2] A. Languasco, Numerical verification of Littlewood's bounds for |L(1,χ)| , Journal of Number Theory 223 (2021), 12--34. Code Ocean capsule

[3] J. E. Littlewood, On the class number of the corpus P(sqrt{-k}), Proc. London Math. Soc. 27 (1928), 358--372.

[4] D. Shanks, Systematic Examination of Littlewood's Bounds on L(1,χ), Proc. Sympos. Pure Math., vol. 24, Amer. Math. Soc., 1973, pp. 267--283.

[5] H.C. Williams, J. Broere, A computational technique for evaluating L(1,χ) and the class number of a real quadratic field, Math. Comp. 30 (1976), 887--893.

Ultimo aggiornamento: 28.09.2024: 10:46:59

Go to the
DEI Department
Home Page

Home

Research

Divulgazione

Programs

Books

OEIS

Teaching2425

Links

Numerical verification of Littlewood's bounds for |L(1,χ)| A. Languasco

Numerical verification of Littlewood's bounds for |L(1,χ)|
A. Languasco