Fast multi-precision computation of some Euler products

Author:

Salma Ettahri

Author:

Olivier Ramaré

Author:

Léon Surel

Note

This file is a web version of the paper Fast multi-precision computation of some Euler products by the same authors and which appeared in Math. Comp. 90 (2021), no. 331, pages 2247–2265. The modifications concerns the numbering and the elements concerning the produced code.

1. Introduction

In formula (16) of [16], D. Shanks obtained the following closed expression to compute the Landau-Ramanujan constant:

(1)\[ \prod_{p\equiv 3[4]}\frac{1}{1-1/p^{s}} =\prod_{k\ge0}\biggl(\frac{\zeta(2^ks)(1-2^{-2^{k}s})}{L(2^{k}s,\chi_{1,4})}\biggr)^{1/2^{k+1}}\]

where \(s>1\) and \(\chi_{1,4}\) is the (only) non-principal Dirichlet character modulo 4. Since both \(\zeta(2^ks)\) and \(L(2^{k}s,\chi_{1,4})\) are \(1+\mathcal{O}(1/2^{s2^k})\), we only need to compute \(\mathcal{O}(\log D)\) values of \(L\)-functions (including the Riemann \(\zeta\)-function) to obtain \(D\) decimal digits. In this paper, we generalize this process in several directions, but a main feature of our work is that it applies only to Euler products over primes belonging to some special subsets of \(G=(\mathbb{Z}/q\mathbb{Z})^\times\) that we define below. We obtain closed formulas involving only values of \(L\)-functions of Dirichlet characters for rational Euler products over primes in these special sets and deduce fast ways to compute a more restricted class of such products. Let us first introduce the players.

Definition 1.

Two elements \(g_1\) and \(g_2\) of the abelian group \(G\) are said to be lattice-invariant if and only if they generate the same group. This defines an equivalence relation.

We denote the set of lattice invariant classes by \(G^\sharp\) and the set of cyclic subgroups of \(G\) by \(\mathscr{G}\). The map between \(\mathscr{G}\) and \(G^\sharp\) which, to a subgroup, associates the subset of its generators, is one-to-one.

The cardinality of \(G^\sharp\) can be swiftly inferred from Theorem 3 of [18] or from Theorem 1 of [19], both by L. Tóth. When \(\mathcal{A}\) is a subset of \(G=(\mathbb{Z}/q\mathbb{Z})^\times\), we define \(\langle{\mathcal{A}}\rangle{}\) to be the (multiplicative) subgroup generated by \(\mathcal{A}\).

For any Dirichlet character \(\chi\) modulo \(q\) and any parameter \(P\ge2\), we define

(2)\[ L_P(s,\chi)=\prod_{p\ge P}(1-\chi(p)/p^s)^{-1}\]

and correspondingly \(\zeta_P(s)=\prod_{p\ge P}(1-1/p^s)^{-1}\).

Given \(K\) a subgroup of \(G=(\mathbb{Z}/q\mathbb{Z})^\times\), we denote by \(K^\perp\) the subgroup of Dirichlet characters modulo \(q\) that take the value 1 on \(K\). When \(s\) is a real number, the number \(\prod_{\chi\in K^\perp}L_P(s,\chi)\) is indeed a positive real number because, when \(\chi\) belongs to \(K^\perp\), so does \(\overline{\chi}\).

Here is the central theorem of this paper.

Theorem 2.
Let \(q\) be some modulus and \(\mathcal{A}\) be a lattice-invariant class of \(G=(\mathbb{Z}/q\mathbb{Z})^\times\). Let \(F,H\in \mathbb R[X]\) be two polynomials satisfying \(F(0)=H(0)=1\) and let \(\Delta\ge1\) be an integer such that \((F(X)-H(X))/X^\Delta\in\mathbb{R}[X]\). Let \(\beta\ge2\) be an upper bound for the maximum modulus of the inverses of the roots of \(F\) and of \(H\). Let \(\sigma_1,\sigma_2,\cdots,\sigma_{\deg F}\) be the roots of \(F\) (a multiple root appears as many times as its multiplicity), and similarly, let \(\rho_1,\rho_2,\cdots,\rho_{\deg H}\) be the roots of \(H\). For any non-negative integer \(d\), we set

(3)\[ s_{H/F}(d)=\sum_{1\le i\le \deg H}\rho_i^{-d} -\sum_{1\le j\le \deg F}\sigma_j^{-d}.\]

Let \(P\) and \(s > 1/\Delta\) be two real parameters such that \(P^s\ge 2\beta\). We define, for any cyclic subgroup \(K\) of \(G\) and any positive integer \(m\),

(4)\[\begin{split} C_{\mathscr{A}}(K,m,F/H)=\sum_{t|m}\mu(t)s_{H/F}(m/t)\sum_{\substack{L\in \mathscr{G},\\ L^{[t]}=\langle{\mathscr{A}}\rangle{},\\ K\subset L}} \frac{\mu(|L|/|K|)}{|G/K|}\end{split}\]

where \(L^{[t]}=\{x^t, x\in L\}\) and \(\langle{\mathscr{A}}\rangle{}\) is the subgroup generated by \(\mathscr{A}\). We have

(5)\[\begin{split}\prod_{\substack{p\ge P,\\ p+q\mathbb{Z}\in\mathcal{A}}}\frac{F(1/p^s)}{H(1/p^s)} = \prod_{m\ge\Delta}\prod_{K\in\mathscr{G}} \biggl(\prod_{\chi\in K^\perp}L_P(m s,\chi)\biggr)^{{C_{\mathscr{A}}(K,m,F/H)}/{m}}.\end{split}\]

For any positive real-valued parameter \(M\), the following bound holds true:

(6)\[\begin{split}\begin{gathered} \pm\log\prod_{ m\ge M+1}\prod_{K\in\mathscr{G}} \biggl(\prod_{\chi\in K^\perp}L_P(ms,\chi)\biggr)^{\frac{C_{\mathscr{A}}(K,m,F/H)}{m}} \\\le 4(\deg F+\deg H)|\mathscr{G}|^2 (s+P) \biggl(\frac{\beta}{P^s}\biggr)^{M+1}.\end{gathered}\end{split}\]

In the case \(H/F=1-X\), the relevant identity is proved in  18 and is the heart of this paper. Our result applies in particular to \(\mathcal{A}=\{1\}\) and to \(\mathcal{A}=\{-1\}\). When \(q=4\) and \(\mathcal{A}=\{-1\}\), we readily find that only \(t=1\) matters in (4), that \(C_{\{-1\}}(\{1\},2^k,1/(1-X))=-1/2\) and that \(C_{\{-1\}}(\{\pm 1\},2^k,1/(1-X))=1\). On recalling Lemma 16, this results in (1).

Remark 3. Lemma 21 ensures that we may select

\[\beta = \max\Bigl(2, \sum_{1\le k\le\deg F}|a_k|, \sum_{1\le k\le\deg H}|b_k|\Bigr)\]

when \(F(X)=1+a_1X+\ldots+a_\delta X^\delta\) and \(H(X)=1+b_1X+\ldots+b_{\delta'} X^{\delta'}\). Notice that our assumptions imply that \(b_i=a_i\) when \(i< \Delta\).

Remark 4. The numbers \(s_{H/F}(n)\) may be computed via the Girard-Newton relations recalled in Lemma 19.

Remark 5. We prove in Lemma 22 that, when \(K\) and \(\mathscr{A}\) are fixed, the quantity \(\sum_{\substack{L\in \mathscr{G},\\ L^{[t]}=\langle{\mathscr{A}}\rangle{},\\ K\subset L}} \mu(|L|/|K|)\) depends only on \(\gcd(t,\varphi(q))\) .

Remark 6. We have \(C_{\mathscr{A}}(K,m,F/H)=-C_{\mathscr{A}}(K,m,H/F)\), a property we shall use to simplify the typography.

Remark 7. There is some redundancy in our formula as a same character \(\chi\) may appear in several sets \(K^\perp\) (for instance, the principal character appears in all of them). Disentangling these contributions leads to a slightly more complicated formula. We first have to introduce, for any cyclic subgroup \(S\) , the subset \(S^{\perp\circ}\subset S^\perp\) constituted of those elements that do not belong to any \(T^\perp\) , for \(T\varsubsetneq S\). It can be readily checked that any \(K^\perp\) is the union of \(S^{\perp\circ}\) where \(S\) ranges the subgroups that are included in \(K\). We then define

(7)\[\begin{split}C^{\circ}_{\mathscr{A}}(S,m,F/H)=\sum_{t|m}\mu(t)s_{H/F}(m/t)\sum_{\substack{L\in \mathscr{G},\\ L^{[t]}=\langle{\mathscr{A}}\rangle{},\\ S\subset L}} \frac{\varphi(|L|/|S|)}{|G/S|}.\end{split}\]

Formula (5) becomes:

\[\begin{split}\prod_{\substack{p\ge P,\\ p+q\mathbb{Z}\in\mathcal{A}}}\frac{F(1/p^s)}{H(1/p^s)} = \prod_{m\ge\Delta}\prod_{S\in\mathscr{G}} \biggl(\prod_{\chi\in S^{\perp\circ}}L_P(ms,\chi) \biggr)^{{C^\circ_{\mathscr{A}}(S,m,F/H)}/{m}}\end{split}\]

and the bound (6) holds to estimate the tail of this product, as we only shuffled terms with a fixed index \(m\).

Super fast evaluations

Corollary 8.
For every positive integer \(m\) , the constant \(C_{\mathscr{A}}(K,m,1-X)\) vanishes when one prime factor of \(m\) is coprime with \(\varphi(q)\) . As a consequence and under the hypotheses of Theorem 2 with \(\Delta=1\), the products

\[\begin{split}\prod_{\substack{p\ge P,\\ p+q\mathbb{Z}\in\mathcal{A}}}\biggl(1-\frac1{p^s}\biggr)\end{split}\]

may be computed by \(\mathcal{O}((\log D)^{r})\) computations of \(L\) -functions to get \(D\)-decimal digits, where \(r\) is the number of prime factors of \(\varphi(q)\) . The implied constant in the \(\mathcal{O}\)-symbol may depend on \(q\) .

This leads to very fast computations, and we were for instance able to produce 100 (resp. 1000, resp. 5000) digits of these products when \(q=3\) in a third of a second (resp. 12 seconds, resp. 35 minutes with \(P=400\)) on a usual desktop computer. See the implementation notes at the end of this paper. Notice however that the number of \(L\)-values required is not the only determinant: when \(q\) increases, the dependence in \(q\) matters as the character group increases in size, and when the required precision increases, each computation of an \(L\)-value may take a long time. We do not address the issue of these computations here. We present some timing data at the end of this paper.

Proof of Corollary 8. Lemma 16 tells us that \(C_{\mathscr{A}}(K,m,1-X)\) vanishes when one prime factor of \(m\) is coprime with \(\varphi(q)\). Let us decompose \(\varphi(q)\) in prime factors: \(\varphi(q)=p_1^{\alpha_1}\cdots p_r^{\alpha_r}\). Any integer \(m\le M\) such that all its prime factors divide \(q\), can be written as \(m=p_1^{\beta_1}\cdots p_r^{\beta_r}\) with \(\beta_i\le (\log M)/\log p_i\) for \(i\le r\). In particular, there are at most \(((\log M)/\log 2)^r\) such integers. By (6), the contribution of the integers \(m>M\) to the Euler product to be computed is \(1+\mathcal{O}((\beta/P^s)^M)\), which is \(1+\mathcal{O}(2^{-M})\) by the assumption \(P^s\ge2\beta\). We want this error term to be \(1+\mathcal{O}(10^{-D})\) to get about \(D+\mathcal{O}(1)\) decimal digits. This is ensured by \(M\log 2\ge D\log 10\), i.e. it is enough to take \(M=4D\). ◻

In order to extend this property to other Euler products, many of the coefficients \(C_{\mathscr{A}}(K,m,F/H)\) should vanish when \(m\) varies. This is however not likely to happen, except when \(F/H\) is a product/quotient of cyclotomic polynomials. Indeed the coefficients \(s_{H/F}(m)\) satisfy a linear recurrence (of degree at most \(\max(\deg F,\deg H)\)) and as such are expected to grow exponentially fast if they are not roots of unity. When for instance the coefficients of the recurrence belong to some number field, this is proved by Evertse in [3] and independently by van der Poorten and Schlickewei in [20]. This is the case where we may expect cancellations to happen. Since the sum defining \(C_{\mathscr{A}}(K,m,F/H)\) is of the form \(\sum_{t|m}\mu(t)r_0(t)s_{H/F}(m/t)\) for some function \(r_0(t)\) that remains bounded (it takes only a finite set of values), it is dominated by the term \(t=1\) when \(m\) is large enough; no cancellation due to the Möbius factor can be expected either. We are then left with the case of cyclotomic polynomials, but they can be easily dealt with using Corollary 8; indeed, if we denote by \(\Phi_n\) the \(n\)-th cyclotomic polynomial, the identity \(\prod_{d|n}\Phi_d(X)=X^n-1\) gets inverted to \(\Phi_n(X)=\prod_{d|n}(X^d-1)^{\mu(n/d)}\).

A Sage script

The material of this paper has been used to write the Sage script using Python 3.

The function get_euler_products(q, s, F, H, nbdecimals) gives all these Euler products. The polynomials \(F\) and \(H\) are to be given as polynomial expressions with the variable \(x\). The special function get_vs(q, s, nbdecimals) gives all the Euler products of Corollary 8.

Some historical pointers

D. Shanks in [14] (resp. [15], resp. [17]) has already been able to compute an Euler product over primes congruent to 1 modulo 4 (resp. to 1 modulo 8 in both instances), by using an identity (Lemma of section 2 for [14], Equation (5) in [15] and the Lemma of section 3 in [17]) that is a precursor of our Lemma 19.

In these three examples, the author has only been able to compute the first five digits, and this is due to three facts: the lack of an interval arithmetic package at that time, the relative weakness of the computers and the absence of a proper study of the error term. We thus complement these results by giving the first hundred decimals.

Complementary to the published papers, three influent preprints on how to compute Euler products with high accuracy have been floating on the web: [5] a memo started in 1990 in its 1996 version by Ph. Flajolet and I. Vardi, [1] by H. Cohen and [7] by X. Gourdon and P. Sebah. Comparing the desired constant with zeta-values is the overarching idea. The set of zeta-values is extended to \(L\)-values of (some) quadratic characters in the three, in some way or another, and to the values of Dedekind zeta-function in [1]. No complete error term analysis is presented, sometimes because the series used are simple enough to make this analysis rather easy. These three sources also deal with constants that are sums over primes and a similar extension of our work is possible, but kept for later. It should be noticed that Equation (20) from [5] is in fact the formula given as Equation (16) in [16] for the Landau-Ramanujan constant.

On the methodology

We decided to prove Theorem 2 directly, by giving the formula and shuffling terms. This gives a short and self-contained proof. However, we did not come up with the coefficients \(C_{\mathscr{A}}(K,m,F/H)\) by some lucky strike! There is a path leading from abelian field theory to our expression that is much closer to D. Shanks’s approach. We say more on this subject in section 4.

Application to some constants

This paper has been inspired by the wish to compute with high numerical precision two constants that appear in the paper [6] by É. Fouvry, C. Levesque and M. Waldschmidt. In the notation of that paper, they are

\[\alpha_0^{(3)} =\frac{1}{3^{1/4}\sqrt{2}}\prod_{p\equiv 2[3]}\biggl(1-\frac{1}{p^2}\biggr)^{-1/2}\]

and

(8)\[\beta_0=\frac{3^{1/4}\sqrt{\pi}}{2^{5/4}}\frac{\log(2+\sqrt{3})^{1/4}}{\Gamma(1/4)} \prod_{p\equiv 5,7,11[12]}\biggl(1-\frac{1}{p^2}\biggr)^{-1/2}.\]

Both occur in number theory as densities. The number of integers \(n\) of the shape \(n=x^2-xy+y^2\), where \(x\) and \(y\) are integers (these are the so-called Loeschian numbers, see the sequence A003136 entry in [12]) is asymptotically approximated by

(9)\[N(x)=\alpha_0^{(3)}\frac{x(1+o(1))}{\sqrt{\log x}}.\]

This motivates our interest in the first constant. The second one arises in counting the number of Loeschian numbers that are also sums of two squares (see sequence A301430 entry of [12]), namely we have

\[N'(x)=\beta_0\frac{x(1+o(1))}{(\log x)^{3/4}}.\]

From the sequence A301429 entry in [12], we know that \(\alpha_0^{(3)}=0.638909\ldots\) but we would like to know (many!) more digits. Similarly it is known that \(\beta_0=0.30231614235\ldots\).

Corollary 9.
We have

\[\begin{split}\begin{aligned} \alpha_0^{(3)}= 0.&63890\,94054\,45343\,88225\,49426\,74928\,24509\,37549\,75508\,02912 \\&33454\,21692\,36570\,80763\,10027\,64965\,82468\,97179\,11252\,86643\cdots \end{aligned}\end{split}\]

and

\[\begin{split}\begin{aligned} \beta_0=0.&30231\,61423\,57065\,63794\,77699\,00480\,19971\,56024\,12795\,18936 \\&96454\,58867\,84128\,88654\,48752\,41051\,08994\,87467\,81397\,92727\cdots \end{aligned}\end{split}\]

This follows from Theorem 2 with the choices \(q=3\) and \(\mathcal{A}=\{2\}\) for \(\alpha_0^{(3)}\), and \(q=12\) and \(\mathcal{A}=\{5,7,11\}\) for \(\beta_0\). The other parameters are uniformly selected as \(F(X)=1-X^2\), \(H(X)=1\), \(\Delta=2\), \(\beta=2\) and \(s=1\).

Corollary 10 (Shanks’ Constant).
We have

\[\begin{split}\prod_{p\equiv 1[8]}\biggl(1-\frac{4}{p}\biggr)\biggl(\frac{p+1}{p-1}\biggr)^2 =\,\begin{aligned}[t] 0.&95694\,53478\,51601\,18343\,69670\,57273\,89182\,87531 \\&74977\,29139 14789\,05432\,60424\,60170\,16444\,88885 \\&94814\,40512\,03907\,95084\cdots \end{aligned}\end{split}\]

As a consequence Shanks’ constant satisfies

\[\begin{split}\begin{aligned} I &= \frac{\pi^2}{16\log(1+\sqrt{2})}\prod_{p\equiv 1[8]}\biggl(1-\frac{4}{p}\biggr)\biggl(\frac{p+1}{p-1}\biggr)^2 \\&=\begin{aligned}[t] 0.&66974\,09699\,37071\,22053\,89224\,31571\,76440\,66883\, 70157\,43648 \\& \,24185\,73298\,52284\,52467\,99956\,45714 \,72731\,50621\,02143\,59373\cdots % RR=RealIntervalField(1000) % LaTeXForNumber(RR(pi^2/16/log(1+sqrt(2))*ss), 100,8) \end{aligned} \end{aligned}\end{split}\]

We deduce this Corollary from Theorem 2 by selecting the parameters \(q=8\), \(\mathcal{A}=\{1\}\), \(F(X)=1-2X-7X^2-4X^3\), \(H(X)=1-2X+X^2\), \(s=1\), \(\Delta=2\) and \(\beta=4\). As explained in [15], the number of primes \(\le X\) of the form \(m^4+1\) is conjectured to be asymptotically equal to \(I\cdot X^{1/4}/\log X\). The name “Shanks’ constant” comes from Chapter 2, page 90 of [4].

When using the script that we introduce below, this value is obtained by multiplying by \(\frac{\pi^2}{16\log(1+\sqrt{2})}\) the value obtained with the call

get_euler_products(8, 1, 1-2*x-7*x^2-4*x^3, 1-2*x+x^2, 110, 50, 2, 1).

A note is required here: the script evaluates loosely the required working precision in order to get say 100 correct digits at the end. The results are however presented with the precision obtained, and if we had been asking initially for 100 decimal digits, the script would issue only 94 of them. We could have implemented a mechanism that increases the precision until the result satisfies the request, but we have preferred to let the users increase the precision by themselves. When asking for 110 decimal digits, the script is able to compute 106 of them. We can get a thousand decimals for this constant in about 2 minutes on a usual desktop computer (by asking for 1010 decimal digits), see the implementation notes at the end of this paper.

Corollary 11 (Lal’s Constant).
We have

\[\begin{split}\prod_{p\equiv 1[8]}\frac{p(p-8)}{(p-4)^2} = \begin{aligned}[t] 0.&88307\,10047\,43946\,67141\,78342\,99003\,10853\,46768 \\&88834\,88097 \,34707\,19295\,15939\,52119\,46990\,65659 \\&68857\,99383\,28603\,79164\cdots \end{aligned}\end{split}\]

As a consequence Lal’s constant satisfies

\[\begin{split}\begin{aligned} \lambda &= \frac{\pi^4}{2^7\log^2(1+\sqrt{2})}\prod_{p\equiv 1[8]}\biggl(\frac{p+1}{p-1}\biggr)^4\biggl(1-\frac{8}{p}\biggr) \\&= \frac{\pi^4}{2^7\log^2(1+\sqrt{2})}\prod_{p\equiv 1[8]}\biggl(1-\frac{4}{p}\biggr)^2\biggl(\frac{p+1}{p-1}\biggr)^4\prod_{p\equiv 1[8]}\frac{p(p-8)}{(p-4)^2} %(1-4*x)^2*(1/x+1)^4/(1/x-1)^4*(1/x)*(1/x-8)/(1/x-4)^2 \\&=%0.7922082381 \begin{aligned}[t] 0.&79220\,82381\,67541\,66877\,54555\,66579\,02410\,11289\,32250\,98622 \\&11172\,27973\,45256\,95141\,54944\,12490\,66029\,53883\,98027\,52927\cdots \end{aligned} \end{aligned}\end{split}\]

We deduce the first value given in this Corollary by using Theorem :ref`2<2>` with the parameters \(q=8\), \(\mathcal{A}=\{1\}\), \(F(X)=1-8X\), \(H(X)=1-8X+16X^2\), \(s=1\), \(\Delta=2\) and \(\beta=8\). The value of Lal’s constant \(\lambda\) is then deduced by combining the value obtained in Corollary 10 together with this one. This splitting of the computation in two introduces smaller polynomials and this leads to a lesser running time. As explained in [17], the number of primes \(\le X\) of the form \((m+1)^2+1\) and such that \((m-1)^2+1\) is also prime, is conjectured to be asymptotic to \(\lambda\cdot X^{1/2}/(\log X)^2\). The name “Lal’s Constant” comes from the papers [8] and [17]. When using the script that we introduce below, the first value is obtained with the call

get_euler_products(8, 1, 1-8*x, 1-8*x+16*x^2, 110, 50, 2, 1).

If this call requires about 2 seconds on a usual desktop computer, this time increases to 4 minutes when we ask for a thousand digits. We did not try to get 5000 digits as we did for the products of Corollary 8.

We close this section by mentioning another series of challenging constants. In [10], P. Moree computes inter alia the series of constants \(A_\chi\) defined six lines after Lemma 3, page 452, by

(10)\[A_\chi= \prod_{p\ge2}\biggl(1+\frac{(\chi(p)-1)p}{(p^2-\chi(p))(p-1)}\biggr),\]

where \(\chi\) is a Dirichlet character. Our theory applies only when \(\chi\) is real valued.

A closed formula for primitive roots

Let us recall that a primitive root \(n\) modulo \(q\) is an integer such that the class of \(n\) generates \(G=(\mathbb{Z}/q\mathbb{Z})^\times\). It is a classical result that such an element exists if and only if \(q\) is equal to 2 or 4, or is equal to a prime power of an odd prime or to twice such a prime power.

Corollary 12.
Let \(\mathscr{A}_0\) be the subset of \(G=(\mathbb{Z}/q\mathbb{Z})^\times\) consisting of all the multiplicative generators of \(G\). Assume \(q\) is such that such an \(\mathscr{A}_0\) is not empty. For any real parameter \(P\ge2\) and \(s>1\), we have

\[\zeta_P(s;q,\mathscr{A}_0)= \prod_{m|q^\infty} \prod_{S\in\mathscr{G}} \biggl(\prod_{\chi\in K^{\perp\circ}}L_P(m s,\chi) \biggr)^{e(m,q,S)},\]

where \(m|q^\infty\) means that all the prime factors of \(m\) divide \(q\) and where \(e(m,q,S)=\frac{|S|\varphi(q/|S|)}{m\varphi(q)}\).

Proof. Indeed, since \(\mathscr{A}_0\) generates \(G\), the only index \(t\) in (7) is \(t=1\). Hence, only \(L=G\) is possible.

Thanks

The authors thank M. Waldschmidt for having drawn their attention to this question, P. Moree and É. Fouvry for helpful discussions on how to improve this paper and X. Gourdon for exchanges concerning some earlier computations. The referees are also to be warmly thanked for their very careful reading and for ideas on how to improve both the presentation and the corresponding script.

2. Proof of Theorem 2 when \(F/H=1/(1-X)\)

We follow the notation introduced in (4). Since here \(F/H=1/(1-X)\), this leads us to consider, for any cyclic subgroup \(K\in\mathscr{G}\), any class \(\mathscr{A}\) in \(G^\sharp\) and any positive integer \(m\), the coefficient

(11)\[\begin{split}C_{\mathscr{A}}(K,m, 1-X)=\sum_{t|m}\mu(t)\sum_{\substack{L\in \mathscr{G},\\ L^{[t]}=\langle{\mathscr{A}}\rangle{}}} \frac{\mu(|L|/|K|)}{|G/K|}\end{split}\]

where \(L^{[t]}=\{x^t, x\in L\}\). Notice that it is also a cyclic subgroup of \(G\). Let us first note a simple property.

Lemma 13.
In a finite cyclic group \(L\), the map that associates to a subgroup of \(L\) its cardinality is a one-to-one map between the set of divisors of \(|L|\) and the set of its subgroups. Furthermore, any subgroup of a cyclic group is cyclic.

Proof. We can assume that \(L=(\mathbb{Z}/\ell\mathbb{Z}, +)\). For each \(d|\ell\), the unique subgroup of order \(d\) is \(\{(\ell/d)n, 0\le n\le d-1\}\).

Here is the fundamental property satisfied by these coefficients.

Proposition 14.
For any positive integer \(\ell\), any prime \(p\) and any lattice-invariant class \(\mathscr{A}\), we have

\[\begin{split}\sum_{hm=\ell}\sum_{\substack{K\in \mathscr{G},\\ \chi\in K^\perp}} \chi\bigl(p^h\bigr)C_{\mathscr{A}}(K,m,1-X)=1\!\!\!1_{p\in\mathscr{A}}.\end{split}\]

Proof. Let \(S\) be the left-hand side sum to be evaluated. Let \(B\) be the subgroup generated by \(p\). By using the orthogonality of characters, we readily obtain

\[\begin{split}S=\sum_{hm=\ell}\sum_{\substack{K\in \mathscr{G},\\ B^{[h]} \subset K}}|G/K|C_{\mathscr{A}}(K,m,1-X).\end{split}\]

Next, we introduce the expression given in (11), shuffle the summations and get

\[\begin{split}S= \sum_{hm=\ell} \sum_{t|m}\mu(t)\sum_{\substack{L\in \mathscr{G},\\ L^{[t]}=\langle{\mathscr{A}}\rangle{}}} \sum_{\substack{K\in \mathscr{G},\\ B^{[h]} \subset K}}\mu(|L|/|K|).\end{split}\]

By Lemma 13 and the Möbius function characteristic property, the last summation vanishes when \(B^{[h]}\neq L\) and takes the value 1 otherwise. Since \((B^{[h]})^{[t]}=B^{[ht]}\), this gives us

\[\begin{split}S= \sum_{hm=\ell} \sum_{\substack{t|m,\\ B^{[ht]}=\langle{A}\rangle{}}}\mu(t).\end{split}\]

We continue in a more classical way:

\[\begin{split}S = \sum_{\substack{ath=\ell,\\B^{[ht]}=\langle{A}\rangle{}}}\mu(t) =\sum_{\substack{ab=\ell,\\B^{[b]}=\langle{A}\rangle{}}} \sum_{t|b}\mu(t)=1\!\!\!1_{B=\langle{A}\rangle{}},\end{split}\]

concluding the proof .

Corollary 15.
For any prime \(p\), any positive real number \(s\) and any lattice-invariant class \(\mathscr{A}\), we have

\[\begin{split}\prod_{m\ge1}\prod_{K\in\mathscr{G}} \biggl(\prod_{\chi\in K^\perp}\bigl(1-\chi(p)p^{-ms}\bigr) \biggr)^{-C_{\mathscr{A}}(K,m,1-X)/m}= \begin{cases} (1-p^{-s})^{-1}&\text{when $p\in\langle{\mathscr{A}}\rangle{}$,}\\ 1&\text{otherwise.} \end{cases}\end{split}\]

Proof. We first check that, for any positive integer \(m\) and any subgroup \(K\), we have

\[\exp\sum_{\chi\in K^\perp}\sum_{h\ge1}\frac{\chi(p^h)}{hp^{mhs}} =\prod_{\chi\in K^\perp}\biggl(1-\frac{\chi(p)}{p^{ms}}\biggr)^{-1}.\]

Since \(s\) is a positive real number, the right-hand side is also positive, and so can be raised to some rational power, say \(c\). The sum inside the exponential is also a real number and the equation \(\exp x=y\) leads obviously to \(\exp(cx)=y^c\). The right-hand side of our lemma may thus be written \(\exp S(p)\) where

\[S(p)=\sum_{m\ge1}\sum_{K\in\mathscr{G}} \sum_{\chi\in K^\perp}\sum_{h\ge1}\frac{\chi(p^h)C_{\mathscr{A}}(K,m,1-X)}{mhp^{mhs}}.\]

We set \(\ell=mh\) and appeal to Proposition 14 to infer that

\[S(p)=\sum_{\ell\ge1}\frac{1}{\ell p^{\ell s}}1\!\!\!1_{p\in\mathscr{A}},\]

from which our corollary follows readily. ◻

Lemma 16.
If \(m\) has a prime factor that does not divide \(\varphi(q)\), we have \(C_{\mathscr{A}}(K,m,1-X)=0\).

Proof. When \(F/H=1-X\), we have \(s_{H/F}(m)=-1\) uniformly in \(m\). If \(m=m_1p^a\) for some \(m_1\) prime to \(p\) and \(p\) prime to the order \(\varphi(q)\) of \(G\), any divisor \(t\) of \(m\) factors in \(t_1p^b\) where \(t_1|m_1\) and \(b\le a\). The Möbius coefficient reduces these choices to \(b=a\) or to \(b=a-1\) and since we have \(L^{[t]}=L^{[t_1]}\), both are possible. If we denote the contribution of \(p^at_1\) to \(C_{\mathscr{A}}(K,m,1-X)\) by \(S_1\) say, the contribution or \(p^{a-1}t_1\) is \(-S_1\), and on pairing them we get zero. ◻

Lemma 17.
Let \(f>1\) be a real parameter. We have

\[\bigl|\log \zeta_P(f)\bigr|\le \frac{1+P/(f-1)}{P^{f}}.\]

Proof. We use

\[\log \zeta_P(f) =-\sum_{ p \ge P}\sum_{k\ge1}\frac{1}{k p^{kf}}\]

hence, by using a comparison to an integral, we find that

\[\Bigl|\log \zeta_P(f)\Bigr| \le \sum_{n\ge P}\frac{1}{n^f}\le \frac{1}{P^f}+\int_{P}^\infty\frac{dt}{t^f} =\biggl(\frac{f-1}{P}+1\biggr)\frac{1}{(f-1)P^{f-1}}.\]

Theorem 18.
For every \(s>1\) and every \(P\ge2\), we have

\[\begin{split}\zeta_P(s;q,\mathcal{A}) = \prod_{\substack{p+q\mathbb{Z}\in\mathcal{A},\\ p\ge P}}(1-p^{-s})^{-1} = \prod_{m\ge1}\prod_{K\in\mathscr{G}} \biggl(\prod_{\chi\in K^\perp}L_P(ms,\chi)\biggr)^{{C_{\mathscr{A}}(K,m,1-X)}/{m}}.\end{split}\]

Proof. This is a simple consequence of Corollary 15. Indeed, we may shuffle our series to our fancy by the absolute summability ensured by the condition \(s>1\) and the bounds \(|C_{\mathscr{A}}(K,k)/k|\le |G|\), as well as \(|\mathscr{G}|\le |G|\). This last bound follows from the fact that there are at most as many cyclic subgroups as there are possible generators.

3. Proof of Theorem 2 in general

Let us recall the Witt decomposition. The readers will find in Lemma 1 of [9] a result of the same flavour. We have simply modified the proof and setting as to accommodate polynomials having real numbers for coefficients.

Lemma 19.
Let \(F(t) = 1+a_1 t+\ldots+a_{\delta}t^{\delta} \in \mathbb{R}[t]\) be a polynomial of degree \(\delta\). Let \(\alpha_{1},\ldots,\alpha_{\delta}\) be the inverses of its roots. Put \(s_{F}(k) =\alpha_{1}^{k}+\ldots+\alpha_{\delta}^{k}\). The \(s_{F}(k)\) are integers and satisfy the Newton-Girard recursion

(12)\[s_{F}(k)+a_1s_F(k-1)+\ldots+a_{k-1}s_{F}(1)+ka_{k}=0,\]

where we have defined \(a_{\delta+1} =a_{\delta+2}=\ldots=0\). Put

(13)\[b_{F}(k)=\frac{1}{k}\sum_{d|k}\mu({k}/{d})s_{F}(d).\]

Let \(\beta\ge1\) be such that \(\beta\ge\max_j|1/\alpha_j|\). When \(t\) belongs to any segment \(\subset (-\beta,\beta)\), we have

(14)\[F(t)=\prod_{j=1}^{\infty}(1-t^{j})^{b_{F}(j)}\]

where the convergence is uniform in the given segment.

Proof. Since we follow the proof of Lemma 1 of [9], we shall be rather sketchy. We write \(F(t)=\prod_{i}(1-\alpha_it)\). By logarithmic differentiation, we obtain

\[\frac{tF'(t)}{F(t)}=\sum_i\frac{\alpha_i t}{1-\alpha_it} =\sum_{k\ge1}s_F(k)t^k.\]

This series is absolutely convergent in any disc \(|t|\le b<1/\beta\) where \(\beta=\max_j(1/|\alpha_j|)\). We proceed by expressing \(s_F\) in terms of \(b_F\) via (13) in a disc of radius \(b<1/\beta\). After some shuffling of the terms, we reach the expression

\[\frac{tF'(t)}{F(t)}=\sum_{j\ge1}b_F(j)\frac{jt^j}{1-t^j}.\]

The lemma follows readily by integrating the above relation.

How does the mathematician E. Witt enter the scene? In the paper [21], \((11)\) therein is a decomposition that is the prototype of the above expansion.

Lemma 20.
We use the hypotheses and notation of Lemma 19. Let \(\beta\ge2\) be larger than the inverse of the modulus of all the roots of \(F(t)\). We have

\[|b_F(k)|\le2\deg F \cdot \beta^k/k.\]

Proof. We clearly have \(|s_F(j)|\le \deg F\cdot \beta^j,\) so that

\[\begin{split}\begin{aligned} |b_F(k)| &\le \frac{\deg F}{k}\sum_{1\le j\le k}\beta^j \le \frac{\deg F}{k}\beta\frac{\beta^k-1}{\beta-1} \\&\le\frac{\deg F}{k}\frac{\beta^k}{1-1/\beta} \le 2\deg F\frac{\beta^k}{k}. \end{aligned}\end{split}\]

There are numerous easy upper estimates for the inverse of the modulus of all the roots of \(F(t)\) in terms of its coefficients. Here is a simplistic one.

Lemma 21.
Let \(F(X)=1+a_1X+\ldots+a_\delta X^\delta\) be a polynomial of degree \(\delta\). Let \(\rho\) be one of its roots. Then either \(|\rho|\ge 1\) or \(1/|\rho|\le |a_1|+|a_2|+\ldots+|a_\delta|\).

Proof. On noticing that

\[(1/\rho)^\delta = -a_1(1/\rho)^{\delta-1} -a_2(1/\rho)^{\delta-2}-\ldots -a_\delta,\]

the conclusion follows.

Lemma 22.
The sum \(\sum_{L\in\mathcal{L}} \mu(|L|/|K|)\) where \(\mathcal{L}=\{L\in \mathscr{G}/ L^{[t]}=\langle{\mathscr{A}}\rangle{}\text{ and } K\subset L\}\) depends only on \(\gcd(t,\varphi(q))\).

Proof. Let us call this quantity \(r_0(t)\). We first check that it depends only on \(t\mod \varphi(q)\): this follows from the fact that the map \(x\mapsto x^{\varphi(q)}\) reduces to the identity over \(G\). Secondly, any prime factor of \(t\), say \(p'\), that is prime to \(\varphi(q)\), may be removed from \(t\), i.e. \(r_0(t)=r_0(t/p')\): the map \(x\mapsto x^{p'}\) is one-to-one in \(L\).

The lemma is an immediate consequence of these two remarks.

Proof of Theorem 2 . The proof requires several steps. The very first one is a direct consequence of (14), which leads to the identity

(15)\[\frac{F(t)}{H(t)}=\prod_{j=\Delta}^\infty(1-t^j)^{b_F(j)-b_H(j)}.\]

The absence of the term with \(j < \Delta\) is due to our assumption that \((F(X)- H(X))/X^\Delta\in \mathbb{R}[X]\). Up to this point (15) is only established as a formal identity. Our second step is to establish (15) for all \(t\in\mathbb{C}\) with \(|t| < 1/\beta\). By Lemma 20, we know that \(|b_F(j)-b_H(j)|\le 4\max(\deg F,\deg H)\beta^j/j\). Therefore, for any bound \(J\), we have

(16)\[\sum_{j\ge J+1}|t^j||b_F(j)-b_H(j)| \le 4\max(\deg F,\deg H)\frac{|t\beta|^{J+1}}{(1-|t\beta|)(J+1)},\]

as soon as \(|t| < 1/\beta\). We thus have

(17)\[\frac{F(t)}{H(t)}=\prod_{\Delta\le j\le J}(1-t^j)^{b_F(j)-b_H(j)}\times I_1,\]

where \(|\log I_1|\le4\max(\deg F,\deg H)|t\beta|^{J+1}/[(1-|t\beta|)(J+1)]\). Now that we have the expansion (17) for each prime \(p\), we may combine them. We readily get

\[\begin{split}\prod_{\substack{p\ge P,\\ p+q\mathbb{Z}\in\mathcal{A}}}\frac{F(1/p^s)}{H(1/p^s)} = \prod_{\substack{p\ge P,\\ p+q\mathbb{Z}\in\mathcal{A}}}\prod_{\Delta\le j\le J}(1-p^{-js})^{b_F(j)-b_H(j)}\times I_2,\end{split}\]

where \(I_2\) satisfies

\[\begin{split}\begin{aligned} \log I_2| &\le 4\max(\deg F,\deg H)\sum_{p\ge P}\frac{\beta^{J+1}}{1-\beta/P^s}\frac{1}{(J+1)p^{(J+1)s}} \\&\le \frac{4\max(\deg F,\deg H)\beta^{J+1}}{(1-\beta/P^s)(J+1)}\biggl( \frac{1}{P^{(J+1)s}}+\int_{P}^{\infty}\frac{dt}{t^{(J+1)s}}\biggr) \\&\le \frac{4\max(\deg F,\deg H) (\beta/P^s)^J\beta}{(1-\beta/P^s)(J+1)}\biggl(\frac{1}{P^s}+\frac{1}{Js+s-1}\biggr),\end{aligned}\end{split}\]

since \(P\ge2\) and \(J\ge3\). Letting \(J\) go to infinity, we see that when \(P^s > \beta\) and \(s > 1/\Delta\),

\[\begin{split}\prod_{\substack{p\ge P,\\ p+q\mathbb{Z}\in\mathcal{A}}}\frac{F(1/p^s)}{H(1/p^s)} = \prod_{ j\ge \Delta}\prod_{\substack{p\ge P,\\ p+q\mathbb{Z}\in\mathcal{A}}}(1-p^{-js})^{b_F(j)-b_H(j)}= \prod_{ j\ge 2}\zeta_P(js;q,\mathscr{A})^{b_H(j)-b_F(j)}\end{split}\]

in the notation of Theorem 18. We use this theorem to infer that

\[\begin{split}\prod_{\substack{p\ge P,\\ p+q\mathbb{Z}\in\mathcal{A}}}\frac{F(1/p^s)}{H(1/p^s)} =\prod_{ j\ge \Delta}\prod_{m\ge1}\prod_{K\in\mathscr{G}} \biggl(\prod_{\chi\in K^\perp}L_P(mjs,\chi)\biggr)^{\frac{C_{\mathscr{A}}(K,m,1-X)}{m}(b_H(j)-b_F(j))}.\end{split}\]

Notice that we have \(s_H(j)-s_F(j)=0\) (and hence \(b_H(j)-b_F(j)=0\)) when \(j<\Delta\) by our assumption on \(\Delta\). Let us glue the variables \(m\) and \(j\) in \(n\). On using the definitions (11) and (13), we see that the functions \(m\mapsto C_{\mathscr{A}}(K,m,1-X)/{m}\) and \(j\mapsto (b_H(j)-b_F(j))\) are of the form \((1\!\!\!1\star r)(m)/m\), respectively \((\mu\star(s_H-s_F))(j)/j\). Hence

\[n\sum_{jm=n}\frac{C_{\mathscr{A}}(K,m,1-X)}{m}(b_H(j)-b_F(j)) =\sum_{td=n}r(t)\bigl(s_{H}(d)-s_F(d)\bigr).\]

We replace \(r(t)\) by its value to conclude that this sum is \(C_{\mathscr{A}}(K,m,F/H)\), as defined by (4). We have reached

(18)\[\begin{split}\prod_{\substack{p\ge P,\\ p+q\mathbb{Z}\in\mathcal{A}}}\frac{F(1/p^s)}{H(1/p^s)} =\prod_{ n\ge \Delta}\prod_{K\in\mathscr{G}} \biggl(\prod_{\chi\in K^\perp}L_P(ns,\chi)\biggr)^{\frac{C_{\mathscr{A}}(K,n,F/H)}{n}}.\end{split}\]

The final task is to control the tail of this product, but prior to that, we change the variable \(n\) in (18) in \(m\) again. To control the tail, we check that, by Lemma 17,

\[\begin{split}\begin{aligned} \pm\log\prod_{ m\ge M+1}\prod_{K\in\mathscr{G}} \biggl(&\prod_{\chi\in K^\perp}L_P(ms,\chi)\biggr)^{\frac{C_{\mathscr{A}}(K,m,F/H)}{m}} \\&\le \sum_{m\ge M+1}\sum_{K\in\mathscr{G}}\frac{|C_{\mathscr{A}}(K,m,F/H)|}{m} |G/K|\frac{ms-1+P}{P^{ms}} \\&\le \sum_{m\ge M+1} \sum_{K\in\mathscr{G}}\sum_{t|m}\mu^2(t)|\mathscr{G}| (\deg F+\deg H)\beta^{m/t} \frac{ms-1+P}{mP^{ms}} \\&\le (\deg F+\deg H)|\mathscr{G}|^2 \sum_{m\ge M+1} \frac{\beta^m}{1-(1/\beta)} \frac{s+P}{P^{ms}} \\&\le (\deg F+\deg H)|\mathscr{G}|^2 \frac{\beta(s+P)}{\beta-1}\frac{1}{1-(\beta/P^s)} \biggl(\frac{\beta}{P^s}\biggr)^{M+1} \\&\le 4(\deg F+\deg H)|\mathscr{G}|^2 (s+P) \biggl(\frac{\beta}{P^s}\biggr)^{M+1}.\end{aligned}\end{split}\]

5. Timing and implementation notes

Let \(s > 1\) be a real number and \(P\ge2\) be a parameter. We consider the vector, for any positive integer \(t\):

(22)\[\Gamma_{P,s}(t)=\Bigl(\log\prod_{\chi\in G_0^\perp}L_P(ts,\chi)\Bigr)_{G_0\in\mathscr{G}}.\]

The rows of \(\Gamma_{P,s}(t)\) are indexed by the cyclic subgroups of \(G\). An approximate value of this vector is provided by the function ComponentStructure.get_gamma from the values of the Hurwitz zeta function. We next define

(23)\[V_s(t)=\bigl(\zeta_P(ts;q,\mathcal{A})\bigr)_{\mathcal{A}\in G^\sharp}.\]

The class LatticeInvariant gives the two lists: the one of the cyclic subgroups and the one of their generators, ordered similarly and in increasing size of the subgroups.

The algorithm (function get_vs):

Input

Input the four parameters q, s, nbdecimals and big_p as well as the two parameters that control the output verbose and with_laTeX.

Precomputation-1

Compute and store the algebraic quantities that we need: the tuple of cyclic subgroups of \(G=(\mathbb{Z}/q\mathbb{Z})^\times\), the tuple of its lattice-invariant classes, the exponent of \(G\), its character group, an enumeration of the elements of \(G\) and, for each cyclic subgroup of \(G\), the set of characters of \(G\) that are trivial on it. This is done by the class ComponentStructure.

Initialization

Find M so that the right-hand side of (6) is less than \(10^{-\texttt{nbdecimals}-10}\).

Precomputation-2

Build the set \(\mathscr{M}\) of integers \(m\) such that \(m\le M\) and all the prime factors of \(m\) divide \(q\). Then compute the constants \((C_{\mathscr{A}}(K,m,1-X))\) for every possible class \(\mathscr{A}\) and every \(m\) in \(\mathscr{M}\).

Main Loop

For \(m\in\mathscr{M}\), add the contribution of this index to the sum approximating \(V_s(1)\) from the right-hand side of (5) with \(P=\texttt{big_p}\).

Post-computation

Complete the products with the values for primes \(p < \texttt{big_p}\).

Output

Return the tuple of lattice-invariant classes and the tuple of couples of lower/upper bounds for the wanted Euler products.

Once the script is loaded, a typical call will be

get_vs(12, 2, 100, 110)

to compute modulo 12 the possible constants with \(s=2\), asking for 100 decimal digits and using \(P=110\). The output is self explanatory. The number of decimal digits asked for is roughly handled and one may lose precision in between, but this is indicated at the end. Note that we expect the final result to be of size roughly unity, so what we ask for is not the relative precision but the number of decimals. Hence, in the function get_gamma, we replace by an approximation of 0 the values that we know are insignificantly small. This is a true time-saver.

There are two subsequent optional parameters verbose and with_laTeX. The first one may take the values 0, 1 and 2; when equal to 0, the function will simply do its job and return the tuple of the invariant classes and the one of the computed lower and upper values. When equal to 1, the time taken will also be printed. And when equal to 2, its default value, some information on the computation is given. When the parameter verbose is at least 2 and with_laTeX is 1, the values of the constants will be further presented in a format suitable for inclusion in a LaTeX-file. The digits presented in LaTeX-format when with_laTeX \(=1\) are always accurate. For instance, the call get_vs(12, 2, 100, 100, 2, 1) is the one used to prepare the addendum [2] in which we give the first hundred decimal digits of every Euler product over a lattice invariant class when the modulus is at most 16.

The computations of the Euler products of Theorem 2 (with \(P=2\), the parameter big_p being used to decide from which point onwards we use the usual Euler product or the expression of the theorem) is implemented in:

The parameter big_p may be increased by the script to ensure that \(P\ge2\beta\) (a condition that is usually satisfied). We reused the same structure as the one for the function get_vs except that the set of indices \(m\) is now a full interval. Since the coefficients \(|b_F(j)-b_G(j)|\) may increase like \(\beta^j\), we increase the working precision by \(J\log\beta /\log 2\).

Checking

The values given here have been checked in several ways. The co-authors of this paper have run several independent scripts. We also provide the function get_vs_checker(q, s, borne = 10000) which computes approximate values of the same Euler products by simply truncating the Euler product representation. We checked with positive result the stability of our results with respect of the variation of the parameter \(P\). This proved to be a very discriminating test.

Furthermore, approximate values for Shanks’ and Lal’s constants are known (Finch in [4] gives 10 digits) and we agree with those. Finally, the web site [7] by X. Gourdon and P. Sebah, or the attached postscript file on the same page, gives in section 4.4 the first fifty digits of the constant they call \(A\) and which are

(24)\[\begin{split}\begin{aligned} \smash{\frac{\pi^2}{2}\prod_{p\equiv1[4]}\biggl(1-\frac{4}{p}\biggr)\biggl(\frac{p+1}{p-1}\biggr)^2} = 1.&95049\,11124\,46287\,07444\,65855\,65809\,55369 \\&25267 \,08497\,71894\,30550\,80726\,33188\,94627 \\&61381\,60369 \,39924\,26646\,98594\,38665\cdots \end{aligned}\end{split}\]

Our result matches that of [7].

Some observations on the running time and complexity

We tried several large computations to get an idea of the limitations of our script with the choice \(s=2\) in Corollary 8. We present five tables:

  • A first table for \(3\le q\le 100\) with the uniform choice \(P=100\) and asking for 100 decimal digits.

  • Three further tables obtained with the choice \(P=200\) and asking for a thousand decimal digits. The cases retained are \(q\le 16\), \(91\le q\le 100\) and \(200\le q\le 220\). This last interval contains the first integer \(q\) such that \(r=\omega(\varphi(q))=4\), namely \(q=211\).

  • And finally a table for \(q\in\{3,5\}\) and asking for 5000 decimal digits. The running time is given with different choices of the parameter \(P\).

Since we did not run each computation hundred times to get an average timing, these tables have to be taken with a pinch of salt. The processor was an Intel Core i5-2500 at 3.30 GHz. The first half of Table 2 may be reproduced with the call:

table_performance(3, 51, 100, 100)

In these tables, \(r=\omega(\varphi(q))\) is the number of distinct prime divisors of \(\varphi(q)\) as in Corollary 8. The time is given in tenth of a second, indicated by “s/10”. The column with the tag “\(\#m's\)” contains the number of indices \(m\le M\) such that \(m|\varphi(q)^\infty\). We otherwise follow the notation of Theorem 2.

It seems likely, when looking at Tables 2, 3, 4 and 5 that the number of values of the Hurwitz zeta-function to be computed is the main determining factor of the time consumption. This number is controlled by \(\varphi(q)\), since this is the number of characters, and by the number of \(m\)’s required, a value that is on the whole controlled by \(r=\omega(\varphi(q))\).

Time used when asking for 1000 digits for \(q \le 16\)

\(q\)

\(\varphi(q)\)

\(r\)

\(\#m's\)

\(\|G^\sharp\|\)

\(M\)

Time (s/10)

3

2

1

8

2

218

10

4

2

1

8

2

218

7

5

4

1

8

3

218

14

7

6

2

26

4

218

69

8

4

1

8

4

218

12

9

6

2

26

4

218

67

11

10

2

19

4

218

81

12

4

1

8

4

218

14

13

12

2

26

6

218

135

15

8

1

8

6

218

26

16

8

1

8

6

218

24
Time used when asking for 1000 digits for \(90 <q \le 100\)

\(q\)

\(\varphi(q)\)

\(r\)

\(\#m's\)

\(|G^\sharp|\)

\(M\)

Time (s/10)

91

72

2

26

30

219

910

92

44

2

14

8

218

286

93

60

3

47

16

219

1388

95

72

2

26

18

218

912

96

32

1

8

16

218

114

97

96

2

26

12

218

1257

99

60

3

47

16

219

1399

100

40

2

19

12

218

363
Time used when asking for 1000 digits for \(200 \le q \le 220\)

\(q\)

\(\varphi(q)\)

\(r\)

\(\#m's\)

\(\|G^\sharp\|\)

\(M\)

Time (s/10)

200

80

2

19

24

218

759

201

132

3

37

16

218

2543

203

168

3

42

24

219

3767

204

64

1

8

20

218

240

205

160

2

19

28

219

1573

207

132

3

37

16

218

2520

208

96

2

26

40

219

1259

209

180

3

47

24

219

4552

211

210

4

69

16

219

8406

212

104

2

14

12

218

743

213

140

3

31

16

218

2271

215

168

3

42

24

219

3807

216

72

2

26

24

219

930

217

180

3

47

40

219

4517

219

144

2

26

24

219

1970

220

80

2

19

24

218

753

Table 6 gives some data about the running time when asking for 5000 decimal digits, which essentially sets the horizon of the present method. The time is counted in minutes.

Time used when asking for 5000 digits

\(q\)

\(P\)

time

3

200

80m

3

400

35m

3

500

35m

5

500

72m

5

1000

70m

5

5000

72m

[1] H. Cohen, High precision computations of Hardy-Littlewood constants, preprint (1996), 1–19.

[2] S. Ettahri, O. Ramaré and L. Surel, Some Euler Products, Preprint (2020), 4p, Addendum to ’Fast multi-precision computation of some Euler products’.

[3] J.-H. Evertse, On sums of \(S\) -units and linear recurrences, Compositio Math. 53 (1984), no. 2, 225–244. MR 766298

[4] S. R. Finch, Mathematical constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, Cambridge, 2003. MR 2003519

[5] P. Flajolet and I. Vardi, Zeta function expansions of classical constants, preprint (1996), 1–10.

[6] É. Fouvry, C. Levesque and M. Waldschmidt, Representation of integers by cyclotomic binary forms, Acta Arith. 184 (2018), no. 1, 67–86. MR 3826641

[7] X. Gourdon and P. Sebah, Constants from number theory, http://numbers.computation.free.fr/Constants/constants.html (2010).

[8] M. Lal, Primes of the form \(n^{4}+1\), Math. Comp. 21 (1967), 245–247. MR 0222007

[9] P. Moree, Approximation of singular series constant and automata. with an appendix by Gerhard Niklasch., Manuscripta Matematica 101 (2000), no. 3, 385–399.

[10] P. Moree, On the average number of elements in a finite field with order or index in a prescribed residue class, Finite Fields Appl. 10 (2004), no. 3, 438–463. MR 2067608

[11] W. Narkiewicz, Elementary and analytic theory of algebraic numbers, third ed., Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2004. MR 2078267 (2005c:11131)

[12] OEIS Foundation Inc., The on-line encyclopedia of integer sequence, 2019, http://OEIS.org/.

[13] J.-P. Serre, Cours d’arithmétique, Collection SUP: “Le Mathématicien”, vol. 2, Presses Universitaires de France, Paris, 1970. MR 0255476

[14] D. Shanks, On the conjecture of Hardy & Littlewood concerning the number of primes of the form \(n^{2}+a\), Math. Comp. 14 (1960), 320–332. MR 0120203

[15] D. Shanks, On numbers of the form :math:`n^{4}+1`, Math. Comput. 15 (1961), 186–189. MR 0120184

[16] D. Shanks, The second-order term in the asymptotic expansion of \(B(x)\), Math. Comp. 18 (1964), 75–86. MR 0159174

[17] D. Shanks, Lal’s constant and generalizations, Math. Comp. 21 (1967), 705–707. MR 0223315

[18] L. Tóth, Menon’s identity and arithmetical sums representing functions of several variables, Rend. Semin. Mat. Univ. Politec. Torino 69 (2011), no. 1, 97–110. MR 2884710

[19] L. Tóth, On the number of cyclic subgroups of a finite Abelian group, Bull. Math. Soc. Sci. Math. Roumanie (N.S.) 55(103) (2012), no. 4, 423–428. MR 2963406

[20] A. J. van der Poorten and H. P. Schlickewei, Zeros of recurrence sequences, Bull. Austral. Math. Soc. 44 (1991), no. 2, 215–223. MR 1126359

[21] E. Witt, Treue Darstellung Liescher Ringe, J. Reine Angew. Math. 177 (1937), 152–160. MR 1581553