Tutorial Euler Product

Introduction and principles

The main object of this software is to compute in a very fast manner Euler products with rational local factors over primes in some collections of arithmetic progressions modulo some fixed modulus \(q\). The computations are done with interval arithmetic, the results are certified and given in the form (lower_bound, upper_bound). An Euler product is a product over all the (positive integer) primes, possibly in some subsequence. Here are two examples \(E_1=\prod_{p\equiv 3,5[7]}(1-1/p^2)\), where the product is taken over every prime \(p\) congruent to 3 or 5 modulo 7, and \(E_2 = \prod_{p\equiv 1[8]}\bigl(1-\frac{4}{p}\bigr)\bigl(\frac{p+1}{p-1}\bigr)^2\), the so-called Shanks’s constant, where the product is taken over every prime congruent to 1 modulo 8.

During the computations, Euler products over rational functions such as \(E_2\) are inferred from simpler Euler products of the shape

\[\prod_{p\in\mathcal{A}\mod q}(1-1/p^s),\]

by following the 2021 paper of Ettahri, Surel and Ramaré, where

  • \(\mathcal{A}\) is some subset of \(G=(\mathbb{Z}/q\mathbb{Z})^\times\). The subset \(\mathcal{A}\) has to be the union of “lattice invariant classes”, as described below.

  • \(q\) is a positive integer, the so-called “modulus”. We have \(q=7\) for \(E_1\).

  • \(s\) is a real parameter that is strictly positif and *in this example* strictly larger than 1. A typical choice is \(s=2\). Technically, it should be an exact type, like 2 or 21/10, or an element of a RealIntervalField(...) with enough precision. Since this precision is given in binary digits, using 10 times the number of decimals asked for the final result is a safe choice. Notice that one may have to import RealNumber from sage.all and that RealIntervalField(1000)(2.1) is maybe not what one would expect: 2.1 is understood as a float with 53 binary digits, then extended by adding enough binary digits 0, the result being somewhat different in decimal expansion.

See also

The mathematical proof of this software is taken from the paper ** Fast multi-precision computation of some Euler products ** by Salma Ettahri, Olivier Ramaré and Léon Surel, published in 2021, in volume 90 of *Mathematics of Computations*, pages 2247 to 2265.

In case \(q = 1\), the notion of lattice invariant classes is trivial. Let us start by describing this case.

Euler Product over every primes

from euler_product.lattice_invariant_euler_products import get_euler_products
get_euler_products(1, 21/10 , 1-x^2, 1+x^3, 103, 20, verbose = 0, with_Latex = 0, digits_offset = 10)

This computes the Euler product \(\prod_{p\ge2}\frac{1-1/p^{2s}}{1+1/p^{3s}}\) where \(s = 2.1\) with potentially 103 correct digits and by computing directly the Euler product for all the primes less than \(P=20\). This value of \(P\) is 300 by default. The level of comments verbose can be set to 0, 1 or 2. The additional parameter with_Latex is either equal to 1 or not equal to 1, with an obvious meaning. If the output does not have enough correct digits, the user is asked to increase the value 103 to 110 for instance. We decided not to automate this behaviour.

On the effect of the choice of \(s\), notice that the two calls

get_euler_products(1, 1 , 1-x^4, 1, 103)
get_euler_products(1, 2 , 1-x^2, 1, 103)

give the same answer, which is readily seen to be an approximation of \(1/\zeta(4)\), where \(\zeta\) is the Riemann-zeta function. Recall that we have \(\zeta(4)=\pi^4/90\), a fact that we may use to check our code.

Lattice Invariant Classes modulo \(q\)

  • Definition of Lattice Invariant Classes

We subdivide the multiplicative group \(G=(\mathbb{Z}/q\mathbb{Z})^\times\) in classes called Lattice Invariant Classes. Two points are in the same class if and only if they generate the same subgroup modulo \(q\).

When \(q = 15\) these classes are obtained by

LatticeInvariant(15)[1]
(frozenset({1}), frozenset({4}), frozenset({11}), frozenset({14}), frozenset({8, 2}), frozenset({13, 7}))
from euler_product.utils_euler_product import LatticeInvariant
LatticeInvariant(15)
((frozenset({1}), frozenset({1, 4}), frozenset({1, 11}), frozenset({1, 14}), frozenset({8, 1, 2, 4}), frozenset({1, 4, 13, 7})),
 (frozenset({1}), frozenset({4}), frozenset({11}), frozenset({14}), frozenset({8, 2}), frozenset({13, 7})))

The output is a couple whose first element is the tuple of the monogenic subgroups of \(G=(\mathbb{Z}/q\mathbb{Z})^\times\) and whose second element is the tuple of lattice invariant classes.

  • Low level tools

from euler_product.utils_euler_product import ComponentStructure
mystructure = ComponentStructure(3)

This class proposes several quantities. It is used by the high level function get_vs and get_euler_products, so the user does not have to worry about it. However the quantities computed may have interest.

  • mystructure.q: the modulus \(q\).

  • mystructure.phi_q: the value of the Euler phi-function at \(q\).

  • mystructure.the_exponent: the exponent of the group \(G=(\mathbb{Z}/q\mathbb{Z})^\times\).

  • mystructure.invertibles: the tuple of invertibles in \((\mathbb{Z}/q\mathbb{Z})\), i.e. an enumeration of \(G=(\mathbb{Z}/q\mathbb{Z})^\times\).

  • mystructure.the_SG_tuple: the tuple of the subgroups of \(G=(\mathbb{Z}/q\mathbb{Z})^\times\) that are generated by a single element. Such subgroups are also called *monogenic* subgroups.

  • mystructure.the_Class_tuple: the tuple of the lattice invariant classes.

  • mystructure.nb_class: the number of lattice invariant classes.

  • mystructure.character_group: the character group of \(G=(\mathbb{Z}/q\mathbb{Z})^\times\).

  • mystructure.invariant_characters: for each monogenic subgroup in mystructure.the_SG_tuple, the list of (the indices of) the characters that has this subgroup in its kernel. The order of mystructure.invariant_characters is the same as the one in mystructure.the_SG_tuple.

  • Some methods are also available.

Euler Product over primes in arithmetic progression

We start with the three data:

  • A modulus q\(\ge 1\).

  • A rational fraction given in the form \(F(x)/H(x)\) where \(F(x)\) and \(H(x)\) are two polynomials with real coefficients and such that \(F(0)=H(0)=1\).

  • A parameter s.

  • A wanted precision nb_decimals, given as a number of decimal digits.

We have access to the lattice invariant classes, as per the preceding paragraph. For each of these classes \((\mathcal{A})\), we compute

\[\prod_{p\in\mathcal{A}}\frac{F(1/p^s)}{H(1/p^s)}.\]

There is a condition for this product to converge absolutely: on writing \(F(x)-H(x)=x^\Delta T(x)\) for a \(\Delta\ge1\) and a polynomial \(T(x)\), we need that \(\Delta s >1\). We assume this condition to hold.

from euler_product.lattice_invariant_euler_products import get_euler_products
get_euler_products(q, s, F(x) , H(x), nb_decimals, big_p = 300, verbose = 0, with_Latex = 0, digits_offset = 10)

answers a couple whose first component is the tuple of the lattice invariant classes \((\mathcal{A})\), and second component is the tuple of the values \(\prod_{p\in\mathcal{A}}\frac{F(1/p^s)}{H(1/p^s)}\), for example

from euler_product.lattice_invariant_euler_products import get_euler_products
result = get_euler_products(5, 1, 1-x^2 , 1+x^3, 100, 300, 0)

result[0][0]
frozenset({1})
result[1][0]
(0.9884028950453419692925625250954713121182210521345380891771586345550561301333511982564965807673436742857698303688419181730105231677449, 0.9884028950453419692925625250954713121182210521345380891771586345550561301333511982564965807673437490090286957966947966907374203853849),

which means that

\[ \begin{align}\begin{aligned}0.&9884028950453419692925625250954713121182210521345380891771586345550561301333511982564965807673436742857698303688419181730105231677449\\&\le \prod_{p\equiv 1[5]} \frac{1-1/p^2}{1+1/p^3}\\&\le 0.9884028950453419692925625250954713121182210521345380891771586345550561301333511982564965807673437490090286957966947966907374203853849\end{aligned}\end{align} \]

With verbose = 1 or verbose = 2, the results are more explicitly written.

To compute the specific quantities \(\prod_{p\in\mathcal{A}}(1-1/p^s)^{-1}\) where the rational fraction is thus fixed, we have a shortcut:

from euler_product.lattice_invariant_euler_products import get_vs
get_vs(q, s, nb_decimals = 100, big_p = 100, verbose = 2, with_laTeX = 0, digits_offset = 10)

The output is similar to the one of get_euler_products, with the same effect of the available parameters. However, there is the additional possible value verbose = -1. In that case the output takes the shape

[big_p, phi_q, r, nb_invariant_class, big_m, time_end - time_start, difference]

which is rather explicit. The parameter big_m is introduced in the reference paper and r is the number of values of \(m\), as per Eq. (5) of the reference paper, that are being used. The timing is given in seconds, and difference is an approximation of the number of correct decimals given.

  • Auxiliaries

We finally provide two auxiliary functions.

from euler_product.lattice_invariant_euler_products import table_performance
table_performance(min_q, max_q, nb_decimals = 100, big_p = 300)

This gives some timing info for get_vs(q, 2, nb_decimals, big_p, -1). The output has a LaTeX format of an array, the columns being q, phi_q, nb_prime_factors_phi_q, r, nb_invariant_class, big_m and finally time_end - time_start in seconds / 10. The meanings are the same as in get_vs.

from euler_product.lattice_invariant_euler_products import get_vs_checker
get_vs_checker(q, s, borne = 10000):

This is a simple sanity check. The output get_vs displays the Euler products computed by get_vs, except that these products are only approximated by the truncated Euler product up to borne.