.. LoeschianConstant-NS-04-MCOMP:
.. |begthm| raw:: html
.. |midthm| raw:: html
.. |endthm| raw:: html
=======================================================
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.
.. role:: raw-latex(raw)
:format: latex
..
1. Introduction
===============
In formula (16) of `[16]`_, D. Shanks obtained
the following closed expression to compute the Landau-Ramanujan
constant:
.. math::
:label: mirs
\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 :math:`s>1` and :math:`\chi_{1,4}` is the (only) non-principal
Dirichlet character modulo 4. Since both :math:`\zeta(2^ks)` and
:math:`L(2^{k}s,\chi_{1,4})` are :math:`1+\mathcal{O}(1/2^{s2^k})`, we
only need to compute :math:`\mathcal{O}(\log D)` values of
:math:`L`-functions (including the Riemann :math:`\zeta`-function) to
obtain :math:`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 :math:`G=(\mathbb{Z}/q\mathbb{Z})^\times` that we define
below. We obtain closed formulas involving only values of
:math:`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.
.. admonition:: **Definition** _`1`.
:name: li
*Two elements* :math:`g_1` *and* :math:`g_2` *of
the abelian group* :math:`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* :math:`G^\sharp`
*and the set of cyclic subgroups of* :math:`G` by :math:`\mathscr{G}`.
*The map between* :math:`\mathscr{G}` *and* :math:`G^\sharp` *which, to a
subgroup, associates the subset of its generators, is one-to-one.*
The cardinality of :math:`G^\sharp` can be swiftly inferred from
Theorem 3 of `[18]`_ or from
Theorem 1 of `[19]`_, both by L. Tóth. When
:math:`\mathcal{A}` is a subset of
:math:`G=(\mathbb{Z}/q\mathbb{Z})^\times`, we define
:math:`\langle{\mathcal{A}}\rangle{}` to be the (multiplicative)
subgroup generated by :math:`\mathcal{A}`.
For any Dirichlet character :math:`\chi` modulo :math:`q` and any
parameter :math:`P\ge2`, we define
.. math::
:label: eq-11
L_P(s,\chi)=\prod_{p\ge P}(1-\chi(p)/p^s)^{-1}
and correspondingly :math:`\zeta_P(s)=\prod_{p\ge P}(1-1/p^s)^{-1}`.
Given :math:`K` a subgroup of :math:`G=(\mathbb{Z}/q\mathbb{Z})^\times`,
we denote by :math:`K^\perp` the subgroup of Dirichlet characters
modulo :math:`q` that take the value 1 on :math:`K`. When :math:`s` is a
real number, the number :math:`\prod_{\chi\in K^\perp}L_P(s,\chi)`
is indeed a positive real number because, when
:math:`\chi` belongs to :math:`K^\perp`, so does
:math:`\overline{\chi}`.
Here is the central theorem of this paper.
.. container:: thm
|begthm| Theorem _`2`.
|midthm| Let :math:`q` be some modulus and :math:`\mathcal{A}`
be a lattice-invariant class of
:math:`G=(\mathbb{Z}/q\mathbb{Z})^\times`. Let
:math:`F,H\in \mathbb R[X]` be two polynomials satisfying
:math:`F(0)=H(0)=1` and let :math:`\Delta\ge1` be an integer such
that :math:`(F(X)-H(X))/X^\Delta\in\mathbb{R}[X]`. Let
:math:`\beta\ge2` be an upper bound for the maximum modulus of the
inverses of the roots of :math:`F` and of :math:`H`. Let
:math:`\sigma_1,\sigma_2,\cdots,\sigma_{\deg F}` be the roots of
:math:`F` (a multiple root appears as many times as its
multiplicity), and similarly, let
:math:`\rho_1,\rho_2,\cdots,\rho_{\deg H}` be the roots of :math:`H`.
For any non-negative integer :math:`d`, we set
.. math::
:label: defsHF
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 :math:`P` and :math:`s > 1/\Delta` be two real parameters such that
:math:`P^s\ge 2\beta`. We define, for any cyclic subgroup :math:`K`
of :math:`G` and any positive integer :math:`m`,
.. math::
:label: defCAKkbis
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|}
where :math:`L^{[t]}=\{x^t, x\in L\}` and
:math:`\langle{\mathscr{A}}\rangle{}` is the subgroup generated by
:math:`\mathscr{A}`. We have
.. math::
:label: exact
\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}}.
For any positive real-valued parameter :math:`M`, the following bound
holds true:
.. math::
:label: fineq
\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}
|endthm|
In the case :math:`H/F=1-X`, the relevant identity is proved in
:ref:`18<18>` and is the heart of this paper. Our
result applies in particular to :math:`\mathcal{A}=\{1\}` and to
:math:`\mathcal{A}=\{-1\}`. When :math:`q=4` and
:math:`\mathcal{A}=\{-1\}`, we readily find that only :math:`t=1`
matters in :eq:`defCAKkbis`, that
:math:`C_{\{-1\}}(\{1\},2^k,1/(1-X))=-1/2` and that
:math:`C_{\{-1\}}(\{\pm 1\},2^k,1/(1-X))=1`. On recalling
Lemma 16, this results in :eq:`mirs`.
.. container:: remark
*Remark 3*. Lemma :ref:`21<21>` ensures that we may select
.. math:: \beta = \max\Bigl(2, \sum_{1\le k\le\deg F}|a_k|, \sum_{1\le k\le\deg H}|b_k|\Bigr)
when :math:`F(X)=1+a_1X+\ldots+a_\delta X^\delta` and
:math:`H(X)=1+b_1X+\ldots+b_{\delta'} X^{\delta'}`. Notice that our
assumptions imply that :math:`b_i=a_i` when :math:`i< \Delta`.
.. container:: remark
*Remark 4*. The numbers :math:`s_{H/F}(n)` may be computed via the
Girard-Newton relations recalled in Lemma :ref:`19<19>`.
.. container:: remark
*Remark 5*. We prove in Lemma :ref:`22<22>` that, when
:math:`K` and :math:`\mathscr{A}` are fixed, the quantity
:math:`\sum_{\substack{L\in
\mathscr{G},\\ L^{[t]}=\langle{\mathscr{A}}\rangle{},\\ K\subset L}}
\mu(|L|/|K|)` depends only on :math:`\gcd(t,\varphi(q))` .
.. container:: remark
*Remark 6*. We have
:math:`C_{\mathscr{A}}(K,m,F/H)=-C_{\mathscr{A}}(K,m,H/F)`, a
property we shall use to simplify the typography.
.. container:: remark
*Remark 7*. There is some redundancy in our formula as a same
character :math:`\chi` may appear in several sets :math:`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 :math:`S` , the subset :math:`S^{\perp\circ}\subset S^\perp`
constituted of those elements that do not belong to any
:math:`T^\perp` , for :math:`T\varsubsetneq S`. It can be readily
checked that any :math:`K^\perp` is the union of
:math:`S^{\perp\circ}` where :math:`S` ranges the subgroups that are
included in :math:`K`. We then define
.. math::
:label: defCAKkbiscirc
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|}.
Formula :eq:`exact` becomes:
.. math::
\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}}
and the bound :eq:`fineq` holds to estimate the tail of this
product, as we only shuffled terms with a fixed index :math:`m`.
Super fast evaluations
----------------------
.. container:: cor
:name: superfast
|begthm| Corollary _`8`.
|midthm| For every positive integer :math:`m` , the constant
:math:`C_{\mathscr{A}}(K,m,1-X)` vanishes when one prime factor of
:math:`m` is coprime with :math:`\varphi(q)` . As a consequence and
under the hypotheses of Theorem :ref:`2<2>` with
:math:`\Delta=1`, the products
.. math::
\prod_{\substack{p\ge P,\\
p+q\mathbb{Z}\in\mathcal{A}}}\biggl(1-\frac1{p^s}\biggr)
|endthm|
may be computed by :math:`\mathcal{O}((\log D)^{r})` computations of
:math:`L` -functions to get :math:`D`-decimal digits, where :math:`r`
is the number of prime factors of :math:`\varphi(q)` . The implied
constant in the :math:`\mathcal{O}`-symbol may depend on :math:`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
:math:`q=3` in a third of a second (resp. 12 seconds, resp. 35 minutes
with :math:`P=400`) on a usual desktop computer. See the implementation
notes at the end of this paper. Notice however that the number of
:math:`L`-values required is not the only determinant: when :math:`q`
increases, the dependence in :math:`q` matters as the character group
increases in size, and when the required precision increases, each
computation of an :math:`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.
.. container:: proof
*Proof of Corollary* :ref:`8<8>`.
Lemma :ref:`16<16>` tells us that
:math:`C_{\mathscr{A}}(K,m,1-X)` vanishes when one prime factor
of :math:`m` is coprime with :math:`\varphi(q)`. Let us decompose
:math:`\varphi(q)` in prime factors:
:math:`\varphi(q)=p_1^{\alpha_1}\cdots
p_r^{\alpha_r}`. Any integer :math:`m\le M` such that all its prime
factors divide :math:`q`, can be written as
:math:`m=p_1^{\beta_1}\cdots
p_r^{\beta_r}` with :math:`\beta_i\le (\log M)/\log p_i` for
:math:`i\le r`. In particular, there are at most
:math:`((\log M)/\log 2)^r` such integers. By :eq:`fineq`,
the contribution of the integers :math:`m>M` to the Euler product to
be computed is :math:`1+\mathcal{O}((\beta/P^s)^M)`, which is
:math:`1+\mathcal{O}(2^{-M})` by the assumption :math:`P^s\ge2\beta`.
We want this error term to be :math:`1+\mathcal{O}(10^{-D})` to get
about :math:`D+\mathcal{O}(1)` decimal digits. This is ensured by
:math:`M\log 2\ge D\log 10`, i.e. it is enough to take
:math:`M=4D`. ◻
In order to extend this property to other Euler products, many of the
coefficients :math:`C_{\mathscr{A}}(K,m,F/H)` should vanish
when :math:`m` varies. This is however not likely to happen, except when
:math:`F/H` is a product/quotient of cyclotomic polynomials. Indeed the
coefficients :math:`s_{H/F}(m)` satisfy a linear recurrence (of degree
at most :math:`\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
:math:`C_{\mathscr{A}}(K,m,F/H)` is of the form
:math:`\sum_{t|m}\mu(t)r_0(t)s_{H/F}(m/t)` for some function
:math:`r_0(t)` that remains bounded (it takes only a finite set of
values), it is dominated by the term :math:`t=1` when :math:`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 :math:`\Phi_n` the :math:`n`-th cyclotomic
polynomial, the identity :math:`\prod_{d|n}\Phi_d(X)=X^n-1` gets
inverted to :math:`\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 :math:`F` and :math:`H` are to be given
as polynomial expressions with the variable :math:`x`. The special
function ``get_vs(q, s, nbdecimals)`` gives all the Euler products of
Corollary :ref:`8<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 :math:`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 :ref:`2<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
:math:`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
.. math::
\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
.. math::
:label: eq-12
\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
:math:`n` of the shape :math:`n=x^2-xy+y^2`, where :math:`x` and
:math:`y` are integers (these are the so-called Loeschian numbers, see
the sequence A003136 entry in `[12]`_) is
asymptotically approximated by
.. math::
:label: eq-1
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
.. math:: N'(x)=\beta_0\frac{x(1+o(1))}{(\log x)^{3/4}}.
From the sequence A301429 entry in `[12]`_, we know
that :math:`\alpha_0^{(3)}=0.638909\ldots` but we would like to know
(many!) more digits. Similarly it is known that
:math:`\beta_0=0.30231614235\ldots`.
.. container:: cor
|begthm| Corollary _`9`.
|midthm| We have
.. math::
\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}
and
.. math::
\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}
|endthm|
This follows from Theorem :ref:`2<2>` with the choices
:math:`q=3` and :math:`\mathcal{A}=\{2\}` for :math:`\alpha_0^{(3)}`,
and :math:`q=12` and :math:`\mathcal{A}=\{5,7,11\}` for :math:`\beta_0`.
The other parameters are uniformly selected as :math:`F(X)=1-X^2`,
:math:`H(X)=1`, :math:`\Delta=2`, :math:`\beta=2` and :math:`s=1`.
.. container:: cor
:name: sha
|begthm| Corollary _`10` (Shanks’ Constant).
|midthm| We have
.. math::
\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}
As a consequence Shanks’ constant satisfies
.. math::
\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}
|endthm|
We deduce this Corollary from Theorem :ref:`2<2>` by selecting
the parameters :math:`q=8`, :math:`\mathcal{A}=\{1\}`,
:math:`F(X)=1-2X-7X^2-4X^3`, :math:`H(X)=1-2X+X^2`, :math:`s=1`,
:math:`\Delta=2` and :math:`\beta=4`. As explained in
`[15]`_, the number of primes :math:`\le X` of the
form :math:`m^4+1` is conjectured to be asymptotically equal to
:math:`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 :math:`\frac{\pi^2}{16\log(1+\sqrt{2})}` the value
obtained with the call
.. container:: center
``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.
.. container:: cor
|begthm| Corollary _`11` (Lal’s Constant).
|midthm| We have
.. math::
\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}
As a consequence Lal’s constant satisfies
.. math::
\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}
|endthm|
We deduce the first value given in this Corollary by using
Theorem :ref`2<2>` with the parameters :math:`q=8`,
:math:`\mathcal{A}=\{1\}`, :math:`F(X)=1-8X`, :math:`H(X)=1-8X+16X^2`,
:math:`s=1`, :math:`\Delta=2` and :math:`\beta=8`. The value of Lal’s
constant :math:`\lambda` is then deduced by combining the value obtained
in Corollary :ref:`10<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 :math:`\le X` of the
form :math:`(m+1)^2+1` and such that :math:`(m-1)^2+1` is also prime, is
conjectured to be asymptotic to :math:`\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
.. container:: center
``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 :ref:`8<8>`.
We close this section by mentioning another series of challenging
constants. In `[10]`_, P. Moree computes inter
alia the series of constants :math:`A_\chi` defined six lines after
Lemma 3, page 452, by
.. math::
:label: eq-3
A_\chi= \prod_{p\ge2}\biggl(1+\frac{(\chi(p)-1)p}{(p^2-\chi(p))(p-1)}\biggr),
where :math:`\chi` is a Dirichlet character. Our theory applies only
when :math:`\chi` is real valued.
A closed formula for primitive roots
------------------------------------
Let us recall that a *primitive root* :math:`n` modulo :math:`q` is an
integer such that the class of :math:`n` generates
:math:`G=(\mathbb{Z}/q\mathbb{Z})^\times`. It is a classical result that
such an element exists if and only if :math:`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.
.. container:: cor
|begthm| Corollary _`12`.
|midthm| Let :math:`\mathscr{A}_0` be the subset of
:math:`G=(\mathbb{Z}/q\mathbb{Z})^\times` consisting of all the
multiplicative generators of :math:`G`. Assume :math:`q` is such that
such an :math:`\mathscr{A}_0` is not empty. For any real parameter
:math:`P\ge2` and :math:`s>1`, we have
.. math::
\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 :math:`m|q^\infty` means that all the prime factors of
:math:`m` divide :math:`q` and where
:math:`e(m,q,S)=\frac{|S|\varphi(q/|S|)}{m\varphi(q)}`.
|endthm|
.. container:: proof
*Proof.* Indeed, since :math:`\mathscr{A}_0` generates :math:`G`, the
only index :math:`t` in :eq:`defCAKkbiscirc` is
:math:`t=1`. Hence, only :math:`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.
.. _proof-of-theorem-pm1-when-fh11-x:
2. Proof of Theorem :ref:`2<2>` when :math:`F/H=1/(1-X)`
========================================================
We follow the notation introduced in :eq:`defCAKkbis`.
Since here :math:`F/H=1/(1-X)`, this leads us to consider, for any
cyclic subgroup :math:`K\in\mathscr{G}`, any class :math:`\mathscr{A}`
in :math:`G^\sharp` and any positive integer :math:`m`, the coefficient
.. math::
:label: defCAKk
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|}
where :math:`L^{[t]}=\{x^t, x\in L\}`. Notice that it is also a cyclic
subgroup of :math:`G`. Let us first note a simple property.
.. container:: lem
:name: cyclic
|begthm| Lemma _`13`.
|midthm| In a finite cyclic group :math:`L`, the map that
associates to a subgroup of :math:`L` its cardinality is a one-to-one
map between the set of divisors of :math:`|L|` and the set of its
subgroups. Furthermore, any subgroup of a cyclic group is cyclic.
|endthm|
.. container:: proof
*Proof.* We can assume that :math:`L=(\mathbb{Z}/\ell\mathbb{Z}, +)`.
For each :math:`d|\ell`, the unique subgroup of order :math:`d` is
:math:`\{(\ell/d)n, 0\le n\le d-1\}`.
Here is the fundamental property satisfied by these coefficients.
.. container:: prop
:name: funda
|begthm| Proposition _`14`.
|midthm| For any positive integer :math:`\ell`, any prime
:math:`p` and any lattice-invariant class :math:`\mathscr{A}`, we
have
.. math::
\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}}.
|endthm|
.. container:: proof
*Proof.* Let :math:`S` be the left-hand side sum to be evaluated. Let
:math:`B` be the subgroup generated by :math:`p`. By using the
orthogonality of characters, we readily obtain
.. math::
S=\sum_{hm=\ell}\sum_{\substack{K\in \mathscr{G},\\ B^{[h]}
\subset K}}|G/K|C_{\mathscr{A}}(K,m,1-X).
Next, we introduce the expression given in :eq:`defCAKk`,
shuffle the summations and get
.. math::
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|).
By Lemma :ref:`13<13>` and the Möbius function
characteristic property, the last summation vanishes when
:math:`B^{[h]}\neq L` and takes the value 1 otherwise. Since
:math:`(B^{[h]})^{[t]}=B^{[ht]}`, this gives us
.. math::
S= \sum_{hm=\ell}
\sum_{\substack{t|m,\\ B^{[ht]}=\langle{A}\rangle{}}}\mu(t).
We continue in a more classical way:
.. math::
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{}},
concluding the proof .
.. container:: cor
:name: life
|begthm| Corollary _`15`.
|midthm| For any prime :math:`p`, any positive real number
:math:`s` and any lattice-invariant class :math:`\mathscr{A}`, we
have
.. math::
\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}
|endthm|
.. container:: proof
*Proof.* We first check that, for any positive integer :math:`m` and
any subgroup :math:`K`, we have
.. math::
\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 :math:`s` is a positive real number, the right-hand side is
also positive, and so can be raised to some rational power, say
:math:`c`. The sum inside the exponential is also a real number and
the equation :math:`\exp x=y` leads obviously to
:math:`\exp(cx)=y^c`. The right-hand side of our lemma may thus be
written :math:`\exp S(p)` where
.. math::
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 :math:`\ell=mh` and appeal to
Proposition :ref:`14<14>` to infer that
.. math:: S(p)=\sum_{\ell\ge1}\frac{1}{\ell p^{\ell s}}1\!\!\!1_{p\in\mathscr{A}},
from which our corollary follows readily. ◻
.. container:: lem
:name: simpi
|begthm| Lemma _`16`.
|midthm| If :math:`m` has a prime factor that does not divide
:math:`\varphi(q)`, we have :math:`C_{\mathscr{A}}(K,m,1-X)=0`.
|endthm|
.. container:: proof
*Proof.* When :math:`F/H=1-X`, we have :math:`s_{H/F}(m)=-1`
uniformly in :math:`m`. If :math:`m=m_1p^a` for some :math:`m_1`
prime to :math:`p` and :math:`p` prime to the order
:math:`\varphi(q)` of :math:`G`, any divisor :math:`t` of :math:`m`
factors in :math:`t_1p^b` where :math:`t_1|m_1` and :math:`b\le a`.
The Möbius coefficient reduces these choices to :math:`b=a` or to
:math:`b=a-1` and since we have :math:`L^{[t]}=L^{[t_1]}`, both are
possible. If we denote the contribution of :math:`p^at_1` to
:math:`C_{\mathscr{A}}(K,m,1-X)` by :math:`S_1` say, the contribution
or :math:`p^{a-1}t_1` is :math:`-S_1`, and on pairing them we
get zero. ◻
.. container:: lem
:name: basic
|begthm| Lemma _`17`.
|midthm| Let :math:`f>1` be a real parameter. We have
.. math::
\bigl|\log \zeta_P(f)\bigr|\le
\frac{1+P/(f-1)}{P^{f}}.
|endthm|
.. container:: proof
*Proof.* We use
.. math::
\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
.. math::
\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}}.
.. container:: thm
:name: mainspe
|begthm| Theorem _`18`.
|midthm| For every :math:`s>1` and every :math:`P\ge2`, we
have
.. math::
\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}}.
|endthm|
.. container:: proof
*Proof.* This is a simple consequence of
Corollary :ref:`15<15>`. Indeed, we may shuffle our series
to our fancy by the absolute summability ensured by the condition
:math:`s>1` and the bounds :math:`|C_{\mathscr{A}}(K,k)/k|\le |G|`,
as well as :math:`|\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.
.. _proof-of-theorem-pm1-in-general:
3. Proof of Theorem :ref:`2<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.
.. container:: lem
:name: Wittpoly
|begthm| Lemma _`19`.
|midthm| Let
:math:`F(t) = 1+a_1 t+\ldots+a_{\delta}t^{\delta} \in \mathbb{R}[t]`
be a polynomial of degree :math:`\delta`. Let
:math:`\alpha_{1},\ldots,\alpha_{\delta}` be the inverses of its
roots. Put
:math:`s_{F}(k) =\alpha_{1}^{k}+\ldots+\alpha_{\delta}^{k}`. The
:math:`s_{F}(k)` are integers and satisfy the Newton-Girard recursion
.. math::
:label: recursionbis
s_{F}(k)+a_1s_F(k-1)+\ldots+a_{k-1}s_{F}(1)+ka_{k}=0,
where we have defined :math:`a_{\delta+1} =a_{\delta+2}=\ldots=0`.
Put
.. math::
:label: bfk
b_{F}(k)=\frac{1}{k}\sum_{d|k}\mu({k}/{d})s_{F}(d).
Let :math:`\beta\ge1` be such that
:math:`\beta\ge\max_j|1/\alpha_j|`. When :math:`t` belongs to any
segment :math:`\subset (-\beta,\beta)`, we have
.. math::
:label: Fhatb
F(t)=\prod_{j=1}^{\infty}(1-t^{j})^{b_{F}(j)}
where the convergence is uniform in the given segment.
|endthm|
.. container:: proof
*Proof.* Since we follow the proof of
Lemma 1 of `[9]`_, we shall be rather sketchy. We
write :math:`F(t)=\prod_{i}(1-\alpha_it)`. By logarithmic
differentiation, we obtain
.. math::
\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
:math:`|t|\le b<1/\beta` where :math:`\beta=\max_j(1/|\alpha_j|)`. We
proceed by expressing :math:`s_F` in terms of :math:`b_F`
via :eq:`bfk` in a disc of radius :math:`b<1/\beta`. After
some shuffling of the terms, we reach the expression
.. math::
\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]`_,
:math:`(11)` therein is a decomposition that is the prototype of the above
expansion.
.. container:: lem
:name: apriorimaj
|begthm| Lemma _`20`.
|midthm| We use the hypotheses and notation of
Lemma :ref:`19<19>`. Let :math:`\beta\ge2` be larger
than the inverse of the modulus of all the roots of :math:`F(t)`. We
have
.. math:: |b_F(k)|\le2\deg F \cdot \beta^k/k.
|endthm|
.. container:: proof
*Proof.* We clearly have :math:`|s_F(j)|\le \deg F\cdot \beta^j,` so
that
.. math::
\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}
There are numerous easy upper estimates for the inverse of the modulus
of all the roots of :math:`F(t)` in terms of its coefficients. Here is a
simplistic one.
.. container:: lem
:name: easybeta
|begthm| Lemma _`21`.
|midthm| Let :math:`F(X)=1+a_1X+\ldots+a_\delta X^\delta` be a
polynomial of degree :math:`\delta`. Let :math:`\rho` be one of its
roots. Then either :math:`|\rho|\ge 1` or
:math:`1/|\rho|\le |a_1|+|a_2|+\ldots+|a_\delta|`.
|endthm|
.. container:: proof
*Proof.* On noticing that
.. math::
(1/\rho)^\delta =
-a_1(1/\rho)^{\delta-1}
-a_2(1/\rho)^{\delta-2}-\ldots -a_\delta,
the conclusion follows.
.. container:: lem
:name: boundedt
|begthm| Lemma _`22`.
|midthm| The sum :math:`\sum_{L\in\mathcal{L}} \mu(|L|/|K|)`
where :math:`\mathcal{L}=\{L\in
\mathscr{G}/ L^{[t]}=\langle{\mathscr{A}}\rangle{}\text{ and } K\subset L\}`
depends only on :math:`\gcd(t,\varphi(q))`.
|endthm|
.. container:: proof
*Proof.* Let us call this quantity :math:`r_0(t)`. We first check
that it depends only on :math:`t\mod \varphi(q)`: this follows from
the fact that the map :math:`x\mapsto x^{\varphi(q)}` reduces to the
identity over :math:`G`. Secondly, any prime factor of :math:`t`, say
:math:`p'`, that is prime to :math:`\varphi(q)`, may be removed from
:math:`t`, i.e. :math:`r_0(t)=r_0(t/p')`: the map
:math:`x\mapsto x^{p'}` is one-to-one in :math:`L`.
The lemma is an immediate consequence of these two remarks.
.. container:: proof
*Proof of Theorem* :ref:`2<2>` . The proof requires
several steps. The very first one is a direct consequence
of :eq:`Fhatb`, which leads to the identity
.. math::
:label: formal-FG
\frac{F(t)}{H(t)}=\prod_{j=\Delta}^\infty(1-t^j)^{b_F(j)-b_H(j)}.
The absence of the term with :math:`j < \Delta` is due to our
assumption that :math:`(F(X)- H(X))/X^\Delta\in \mathbb{R}[X]`. Up to
this point :eq:`formal-FG` is only established as a
formal identity. Our second step is to
establish :eq:`formal-FG` for all :math:`t\in\mathbb{C}`
with :math:`|t| < 1/\beta`. By Lemma :ref:`20<20>`, we
know that :math:`|b_F(j)-b_H(j)|\le 4\max(\deg F,\deg H)\beta^j/j`.
Therefore, for any bound :math:`J`, we have
.. math::
:label: tailJ
\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 :math:`|t| < 1/\beta`. We thus have
.. math::
:label: true-FG
\frac{F(t)}{H(t)}=\prod_{\Delta\le j\le J}(1-t^j)^{b_F(j)-b_H(j)}\times I_1,
where
:math:`|\log I_1|\le4\max(\deg F,\deg H)|t\beta|^{J+1}/[(1-|t\beta|)(J+1)]`.
Now that we have the expansion :eq:`true-FG` for each
prime :math:`p`, we may combine them. We readily get
.. math::
\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,
where :math:`I_2` satisfies
.. math::
\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}
since :math:`P\ge2` and :math:`J\ge3`. Letting :math:`J` go to
infinity, we see that when :math:`P^s > \beta` and :math:`s > 1/\Delta`,
.. math::
\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)}
in the notation of Theorem :ref:`18<18>`. We use this
theorem to infer that
.. math::
\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))}.
Notice that we have :math:`s_H(j)-s_F(j)=0` (and hence
:math:`b_H(j)-b_F(j)=0`) when :math:`j<\Delta` by our assumption on
:math:`\Delta`. Let us glue the variables :math:`m` and :math:`j` in
:math:`n`. On using the definitions :eq:`defCAKk`
and :eq:`bfk`, we see that the functions
:math:`m\mapsto C_{\mathscr{A}}(K,m,1-X)/{m}` and
:math:`j\mapsto (b_H(j)-b_F(j))` are of the form
:math:`(1\!\!\!1\star r)(m)/m`, respectively
:math:`(\mu\star(s_H-s_F))(j)/j`. Hence
.. math::
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 :math:`r(t)` by its value to conclude that this sum is
:math:`C_{\mathscr{A}}(K,m,F/H)`, as defined
by :eq:`defCAKkbis`. We have reached
.. math::
:label: aux
\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}}.
The final task is to control the tail of this product, but prior to
that, we change the variable :math:`n` in :eq:`aux` in
:math:`m` again. To control the tail, we check that, by
Lemma :ref:`17<17>`,
.. math::
\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}
.. _More:
4. Link with two other sets of inequalities
===========================================
In this section, we develop some elements that are contiguous to our
topic.
A formula
---------
.. container:: lem
:name: dede
|begthm| Lemma _`23`.
|midthm| Let :math:`q>1` be a modulus. We set :math:`G_0` to be
a subgroup of :math:`G=(\mathbb{Z}/q\mathbb{Z})^\times` and
:math:`G_0^\perp` be the subgroup of characters that take the value 1
on :math:`G_0`. For any integer :math:`b`, we define
:math:`\langle{b}\rangle{}` to be the subgroup generated by :math:`b`
modulo :math:`q`. We have
.. math::
\prod_{\chi\in G_0^\perp}L_P(s,\chi)
=
\prod_{\substack{G_0\subset K\subset G}}
\prod_{\substack{p\ge P,\\ \langle{p}\rangle{}{} G_0=K}}
\Bigl(1-p^{-|K/G_0|s}\Bigr)^{-|G/K|}.
|endthm|
The right-hand side of this formula contains products of the kind we
seek and, if we were to start from such a set of formulas, the problem
would be to *invert* them in some sense.
.. container:: proof
*Proof.* We note that
:math:`\prod_{\chi\in G_0^\perp}(1-\chi(p)z)^{\chi(a)} =\prod_{\psi\in\hat{L}}(1-\psi(p)z)^{f(\psi)}`
when :math:`\langle{p}\rangle{}=L` and where
.. math::
:label: eq-6
f(\psi)=\sum_{\substack{\chi\in G_0^\perp,\\ \chi|L = \psi}}\chi(a).
The condition :math:`\chi\in G_0^\perp` can also be written as
:math:`\chi|G_0=1`, hence we can assume that :math:`\psi|(L\cap
G_0)=1`. We write
.. math::
\prod_{\chi\in G_0^\perp}(1-\chi(p)z)^{\chi(a)}
=\prod_{\substack{\psi'\in\widehat{L{} G_0},\\ \psi'|G_0=1}}(1-\psi(p)z)^{f'(\psi')},
where
.. math::
:label: eq-76
f'(\psi')=\sum_{\substack{\chi\in G_0^\perp,\\ \chi|L{} G_0 = \psi}}\chi(a).
When :math:`a` lies outside :math:`L{} G_0`, this sum vanishes;
otherwise it equals :math:`|G/(L{} G_0)|\psi'(a)`. The characters of
:math:`L{} G_0` that are trivial on :math:`G_0` are canonically
identified with the characters of the cyclic group
:math:`(L{} G_0)/G_0`. We thus have
.. math::
\prod_{\substack{\psi'\in\widehat{L{} G_0},\\ \psi'|G_0=1}}(1-\psi(p)z)
=
1-z^{|(L{} G_0)/G_0|},
and this proves our formula. ◻
.. _notes-on-the-scope-of-lemma-dede:
Notes on the scope of Lemma :ref:`23<23>`
-----------------------------------------
From a metholodogical viewpoint, a moment’s thought discloses that two
residue classes modulo :math:`q` that fall inside the same
lattice-invariant class cannot be distinguished by the set of identities
of Lemma :ref:`23<23>`. This implies that we indeed extract the
maximum information from our setting. This could be formalized in the
following manner: consider the vector space :math:`\mathscr{F}[G]` of
functions from :math:`G` to :math:`\mathbb{C}`, and the sub-space
generated by :math:`(1\!\!\!1_{G_0})_{G_0\in\mathscr{G}}`. This subspace
is clearly included in the subspace generated by
:math:`(1\!\!\!1_{\mathcal{A}})_{\mathcal{A}\in G^\sharp}`. These two
spaces can be shown to be equal. We end this discussion here, as we do
not need this fact.
.. _linkaft:
Link with abelian field theory
------------------------------
The case :math:`G_0=\{1\}` in the identity of Lemma :ref:`23<23>`
is classical in Dedekind zeta function theory for the field
:math:`\mathbb{Q}(\zeta_q)`, where :math:`\zeta_q=\exp(2i\pi/q)`, and
can be found in Proposition 13 of `[13]`_ in a
rephrased form. For the general case, we follow Chapter 8 of
`[11]`_ by Narkiewicz. The Dedekind
zeta-function associated with an abelian field :math:`K` is given by
.. math::
:label: defZetaDedekind
\zeta_K(s)=\prod_{\chi\in X(K)}L(s,\chi)
as per Theorem 8.6 of `[11]`_. The group
:math:`X(K)` is the group of characters attached to :math:`K`, see
Proposition 8.4 of `[11]`_. This
equality :eq:`defZetaDedekind` is proved prime per
prime, and we can restrict to ideals whose norm is prime to some
integer. In particular, we can restrict it to the primes that are prime
to :math:`q`, which excludes at least the ramified primes. Let
:math:`H_q(K)` be the subgroup of the integers :math:`r\mod q` that are
such that the automorphism of :math:`\mathbb{Q}(\zeta_q)` defined by
:math:`\zeta_q\mapsto \zeta_q^r` is the identity on :math:`K`. The sets
:math:`X(K)` and :math:`H_q(K)^\perp` are almost equal: :math:`X(K)` is
made only of primitive characters associated to the characters in
:math:`H_q(K)^\perp`. We may select :math:`G_0=H_q(K)` in
Lemma `23<23>`. Some work involving the decomposition law in
abelian number fields, which may for instance be found in Theorem 8.2
`[11]`_, gives us, when the prime
factors of :math:`q` are all at most :math:`P`, that
.. math::
\prod_{\chi\in X(K)}L_P(s,\chi)
=
\prod_{\substack{H_q(K)\subset K\subset G_q}}
\prod_{\substack{p\ge P,\\ \langle{p}\rangle{}{H_q(K)} =K}}
\Bigl(1-p^{-|K/H_q(K)|s}\Bigr)^{-|G_q/K|}.
The proof we provide of Lemma :ref:`23<23>` is much simpler, but
the above analysis establishes that the identities stemming from both
approaches are the same.
5. Timing and implementation notes
==================================
Let :math:`s > 1` be a real number and :math:`P\ge2` be a parameter. We
consider the vector, for any positive integer :math:`t`:
.. math::
:label: defGammaoft
\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 :math:`\Gamma_{P,s}(t)` are indexed by the cyclic subgroups
of :math:`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
.. math::
:label: defVsoft
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.
.. container:: mdframed
The algorithm (function ``get_vs``):
.. rubric:: Input
:name: input
:class: unnumbered
Input the four parameters ``q``, ``s``, ``nbdecimals`` and ``big_p``
as well as the two parameters that control the output ``verbose`` and
``with_laTeX``.
.. rubric:: Precomputation-1
:name: precomputation-1
:class: unnumbered
Compute and store the algebraic quantities that we need: the tuple of
cyclic subgroups of :math:`G=(\mathbb{Z}/q\mathbb{Z})^\times`, the
tuple of its lattice-invariant classes, the exponent of :math:`G`,
its character group, an enumeration of the elements of :math:`G` and,
for each cyclic subgroup of :math:`G`, the set of characters
of :math:`G` that are trivial on it. This is done by the class
``ComponentStructure``.
.. rubric:: Initialization
:name: initialization
:class: unnumbered
Find ``M`` so that the right-hand side of :eq:`fineq` is
less than :math:`10^{-\texttt{nbdecimals}-10}`.
.. rubric:: Precomputation-2
:name: precomputation-2
:class: unnumbered
Build the set :math:`\mathscr{M}` of integers :math:`m` such that
:math:`m\le M` and all the prime factors of :math:`m`
divide :math:`q`. Then compute the constants
:math:`(C_{\mathscr{A}}(K,m,1-X))` for every possible class
:math:`\mathscr{A}` and every :math:`m` in :math:`\mathscr{M}`.
.. rubric:: Main Loop
:name: main-loop
:class: unnumbered
For :math:`m\in\mathscr{M}`, add the contribution of this index to
the sum approximating :math:`V_s(1)` from the right-hand side
of :eq:`exact` with :math:`P=\texttt{big_p}`.
.. rubric:: Post-computation
:name: post-computation
:class: unnumbered
Complete the products with the values for primes
:math:`p < \texttt{big_p}`.
.. rubric:: Output
:name: output
:class: unnumbered
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
.. container:: center
``get_vs(12, 2, 100, 110)``
to compute modulo 12 the possible constants with :math:`s=2`, asking for
100 decimal digits and using :math:`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`` :math:`=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 :ref:`2<2>`
(with :math:`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
:math:`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 :math:`m` is now a full interval. Since the coefficients
:math:`|b_F(j)-b_G(j)|` may increase like :math:`\beta^j`, we increase
the working precision by :math:`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 :math:`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 :math:`A` and which are
.. math::
:label: eq-7
\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}
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 :math:`s=2` in
Corollary :ref:`8<8>`. We present five tables:
- A first table for :math:`3\le q\le 100` with the uniform choice
:math:`P=100` and asking for 100 decimal digits.
- Three further tables obtained with the choice :math:`P=200` and
asking for a thousand decimal digits. The cases retained are
:math:`q\le 16`, :math:`91\le q\le 100` and :math:`200\le q\le 220`.
This last interval contains the first integer :math:`q` such that
:math:`r=\omega(\varphi(q))=4`, namely :math:`q=211`.
- And finally a table for :math:`q\in\{3,5\}` and asking for 5000
decimal digits. The running time is given with different choices of
the parameter :math:`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 <#HundredDigits>`__ may be reproduced with the call:
``table_performance(3, 51, 100, 100)``
In these tables, :math:`r=\omega(\varphi(q))` is the number of distinct
prime divisors of :math:`\varphi(q)` as in
Corollary :ref:`8<8>`. The time is given in tenth of a
second, indicated by “s/10”. The column with the tag “\ :math:`\#m's`"
contains the number of indices :math:`m\le M` such that
:math:`m|\varphi(q)^\infty`. We otherwise follow the notation of
Theorem :ref:`2<2>`.
It seems likely, when looking at
Tables `2 <#HundredDigits>`__, `3 <#ThousandDigits>`__, `4 <#ThousandDigitsbis>`__
and `5 <#ThousandDigitster>`__ 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 :math:`\varphi(q)`, since this
is the number of characters, and by the number of :math:`m`\ ’s
required, a value that is on the whole controlled by
:math:`r=\omega(\varphi(q))`.
.. container::
:name: ThousandDigits
.. table:: Time used when asking for 1000 digits for :math:`q \le 16`
+-----------+---------------------+-----------+---------------+---------------------+-----------+---------+
| | | | | | | Time |
| :math:`q` | :math:`\varphi(q)` | :math:`r` | :math:`\#m's` | :math:`\|G^\sharp\|`| :math:`M` | (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 |
+-----------+---------------------+-----------+---------------+---------------------+-----------+---------+
.. container::
:name: ThousandDigitsbis
.. table:: Time used when asking for 1000 digits for :math:`90 `__ 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.
.. container::
:name: FiveThousandDigits
.. table:: Time used when asking for 5000 digits
========= ========= ====
:math:`q` :math:`P` time
========= ========= ====
3 200 80m
3 400 35m
3 500 35m
5 500 72m
5 1000 70m
5 5000 72m
========= ========= ====
.. container:: thebibliography
_`[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* :math:`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* :math:`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* :math:`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*
:math:`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