S Ettahri

O Ramar É

L Surel

FAST MULTI-PRECISION COMPUTATION OF SOME EULER PRODUCTS

Keywords: 2010 Mathematics Subject Classification. Primary 11Y60, Secundary 11N13, 05A Euler products, Loeschian numbers, Lal's constant

For every modulus q ≥ 3, we define a family of subsets A of the multiplicative group (Z/qZ) × for which the Euler product p+qZ∈A (1 -p -s ) can be computed with high numerical precision, where s > 1 is some given real number. We provide a Sage script to do so, and extend our result to compute Euler products p+qZ∈A F (1/p s )/H(1/p s ) where F and H are polynomials with real coefficients, when this product converges absolutely. This enables us to give precise values of several Euler products occurring in number theory.

Introduction

In formula [START_REF]The second-order term in the asymptotic expansion of B(x)[END_REF] of [START_REF]The second-order term in the asymptotic expansion of B(x)[END_REF], D. Shanks obtained the following closed expression to compute the Landau-Ramanujan constant:

(1.1) 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 = (Z/qZ) × 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.

p≡3[4] 1 1 -1/p s = k≥0 ζ(2 k s)(1 -2 -2 k s ) L(2 k s, χ 1,4 ) 1/2 k+1
Definition 1.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 and the set of cyclic subgroups of G by G . The map between G and G which, to a subgroup, associates the subset of its generators, is one-to-one.

The cardinality of G can be swiftly inferred from [START_REF] Tóth | Menon's identity and arithmetical sums representing functions of several variables[END_REF]Theorem 3] or from [19, Theorem 1], both by L. Tóth. When A is a subset of G = (Z/qZ) × , we define A to be the (multiplicative) subgroup generated by A.

For any Dirichlet character χ modulo q and any parameter P ≥ 2, we define (1.2)

L P (s, χ) = p≥P (1 -χ(p)/p s ) -1
and correspondingly ζ P (s) = p≥P (1 -1/p s ) -1 . Given K a subgroup of G = (Z/qZ) × , we denote by K ⊥ the subgroup of Dirichlet characters modulo q that take the value 1 on K. When s is a real number, the number χ∈K ⊥ L P (s, χ) is indeed a positive real number because, when χ belongs to K ⊥ , so does χ.

Here is the central theorem of this paper.

Theorem 1.2. Let q be some modulus and A be a lattice-invariant class of G = (Z/qZ) × . Let F, H ∈ R[X] be two polynomials satisfying F (0) = H(0) = 1 and let ∆ ≥ 1 be an integer such that (F (X) -H(X))/X ∆ ∈ R[X]. Let β ≥ 2 be an upper bound for the maximum modulus of the inverses of the roots of F and of H. Let σ 1 , σ 2 , • • • , σ deg F be the roots of F (a multiple root appears as many times as its multiplicity), and similarly, let ρ 1 , ρ 2 , • • • , ρ deg H be the roots of H. For any non-negative integer d, we set

(1.3) s H/F (d) = 1≤i≤deg H ρ -d i - 1≤j≤deg F σ -d j .
Let P and s > 1/∆ be two real parameters such that P s ≥ 2β. We define, for any cyclic subgroup K of G and any positive integer m, .

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

(1.6) ± log m≥M +1 K∈G χ∈K ⊥ L P (ms, χ)

C A (K,m,F /H) m ≤ 4(deg F + deg H)|G | 2 (s + P ) β P s M +1
.

In the case H/F = 1-X, the relevant identity is proved in Theorem 2.6 and is the heart of this paper. Our result applies in particular to A = {1} and to A = {-1}. When q = 4 and A = {-1}, we readily find that only t = 1 matters in (1.4), that

C {-1} ({1}, 2 k , 1/(1 -X)) = -1/2 and that C {-1} ({±1}, 2 k , 1/(1 -X)) = 1.
On recalling Lemma 2.4, this results in (1.1).

Remark 1.3. Lemma 3.3 ensures that we may select

β = max 2, 1≤k≤deg F |a k |, 1≤k≤deg H |b k | when F (X) = 1 + a 1 X + . . . + a δ X δ and H(X) = 1 + b 1 X + . . . + b δ X δ .
Notice that our assumptions imply that b i = a i when i < ∆.

Remark 1.4. The numbers s H/F (n) may be computed via the Girard-Newton relations recalled in Lemma 3.1.

Remark 1.5. We prove in Lemma 3.4 that, when K and A are fixed, the quantity

L∈G , L [t] = A , K⊂L
µ(|L|/|K|) depends only on gcd(t, ϕ(q)).

Remark 1.6. We have

C A (K, m, F/H) = -C A (K, m, H/F
), a property we shall use to simplify the typography.

Remark 1.7. There is some redundancy in our formula as a same character χ may appear in several sets K ⊥ (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 ⊥• ⊂ S ⊥ constituted of those elements that do not belong to any T ⊥ , for T S. It can be readily checked that any K ⊥ is the union of S ⊥• where S ranges the subgroups that are included in K. We then define

(1.7) C • A (S, m, F/H) = t|m µ(t)s H/F (m/t) L∈G , L [t] = A , S⊂L ϕ(|L|/|S|) |G/S| .
Formula (1.5) becomes:

(1.8)

p≥P, p+qZ∈A

F (1/p s ) H(1/p s ) = m≥∆ S∈G χ∈S ⊥• L P (ms, χ) C • A (S,m,F/H)/m
and the bound (1.6) holds to estimate the tail of this product, as we only shuffled terms with a fixed index m.

Super fast evaluations.

Corollary 1.8. For every positive integer m, the constant C A (K, m, 1 -X) vanishes when one prime factor of m is coprime with ϕ(q). As a consequence and under the hypotheses of Theorem 1.2 with ∆ = 1, the products p≥P, p+qZ∈A 1 -1 p s may be computed by O((log D) r ) computations of L-functions to get D-decimal digits, where r is the number of prime factors of ϕ(q). The implied constant in the 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 1.8. Lemma 2.4 tells us that C A (K, m, 1 -X) vanishes when one prime factor of m is coprime with ϕ(q). Let us decompose ϕ(q) in prime factors:

ϕ(q) = p α1 1 • • • p αr r .
Any integer m ≤ M such that all its prime factors divide q, can be written as m = p β1 1 • • • p βr r with β i ≤ (log M )/ log p i for i ≤ r. In particular, there are at most ((log M )/ log 2) r such integers. By (1.6), the contribution of the integers m > M to the Euler product to be computed is 1 + O((β/P s ) M ), which is 1+O(2 -M ) by the assumption P s ≥ 2β. We want this error term to be 1+O( 10 -D ) to get about D + O(1) decimal digits. This is ensured by M log 2 ≥ 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 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 [START_REF] Evertse | On sums of S-units and linear recurrences[END_REF] and independently by van der Poorten and Schlickewei in [START_REF] Van Der Poorten | Zeros of recurrence sequences[END_REF]. This is the case where we may expect cancellations to happen. Since the sum defining C A (K, m, F/H) is of the form t|m µ(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 1.8; indeed, if we denote by Φ n the n-th cyclotomic polynomial, the identity d|n Φ d (X) = X n -1 gets inverted to Φ n (X) = d|n (X d -1) µ(n/d) .

A Sage script. The material of this paper has been used to write a Sage script using Python 3 which can be found on the webpage of the second author: http://iml.univ-mrs.fr/ ~ramare/Maths/LatticeInvariantEulerProducts-06.sage

We shorten this name throughout this paper in LIEP.sage. We give some details about this script when developing the proof below. We also provide on the second author's webpage the first hundred digits of several Euler products: http://iml.univ-mrs.fr/ ~ramare/Maths/SomeEulerProducts-02.pdf

The function GetEulerProds(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 GetVs(q, s, nbdecimals) gives all the Euler products of Corollary 1.8. Some historical pointers. D. Shanks in [START_REF] Shanks | On the conjecture of Hardy & Littlewood concerning the number of primes of the form n 2 + a[END_REF] (resp. [START_REF]On numbers of the form n 4 + 1[END_REF], resp. [START_REF]Lal's constant and generalizations[END_REF]) 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 [START_REF] Shanks | On the conjecture of Hardy & Littlewood concerning the number of primes of the form n 2 + a[END_REF], Equation [START_REF] Flajolet | Zeta function expansions of classical constants[END_REF] in [START_REF]On numbers of the form n 4 + 1[END_REF] and the Lemma of section 3 in [START_REF]Lal's constant and generalizations[END_REF]) that is a precursor of our Lemma 3.1.

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: [START_REF] Flajolet | Zeta function expansions of classical constants[END_REF] a memo started in 1990 in its 1996 version by Ph. Flajolet and I. Vardi, [START_REF] Cohen | High precision computations of Hardy-Littlewood constants[END_REF] by H. Cohen and [START_REF] Gourdon | Constants from number theory[END_REF] by X. Gourdon and P. Sebah. Comparing the desired constant with zetavalues 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 [START_REF] Cohen | High precision computations of Hardy-Littlewood constants[END_REF]. 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 [START_REF] Van Der Poorten | Zeros of recurrence sequences[END_REF] from [START_REF] Flajolet | Zeta function expansions of classical constants[END_REF] is in fact the formula given as Equation ( 16) in [START_REF]The second-order term in the asymptotic expansion of B(x)[END_REF] for the Landau-Ramanujan constant.

On the methodology. We decided to prove Theorem 1.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 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 [START_REF] Fouvry | Representation of integers by cyclotomic binary forms[END_REF] by É. Fouvry, C. Levesque and M. Waldschmidt. In the notation of that paper, they are (1.9) α

(3)

0 = 1 3 1/4 √ 2 p≡2[3] 1 - 1 p 2 -1/2
and (1.10)

β 0 = 3 1/4 √ π 2 5/4 log(2 + √ 3) 1/4 Γ(1/4) p≡5,7,11[12] 1 - 1 p 2 -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 [START_REF]The on-line encyclopedia of integer sequence[END_REF]) is asymptotically approximated by

(1.11) N (x) = α (3) 0 x(1 + o(1)) √ 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 [START_REF]The on-line encyclopedia of integer sequence[END_REF]), namely we have

N (x) = β 0 x(1 + o(1)) (log x) 3/4 .
From the sequence A301429 entry in [START_REF]The on-line encyclopedia of integer sequence[END_REF], we know that α

(3) 0 = 0.638909 . . . but we would like to know (many!) more digits. Similarly it is known that β 0 = 0.30231614235 . . .. This follows from Theorem 1.2 with the choices q = 3 and A = {2} for α

(3) 0 , and q = 12 and A = {5, 7, 11} for β 0 . The other parameters are uniformly selected as

F (X) = 1 -X 2 , H(X) = 1, ∆ = 2, β = 2 and s = 1.
Corollary 1.10 (Shanks' Constant). We have We deduce this Corollary from Theorem 1.2 by selecting the parameters q = 8,

p≡1[8] 1 - 4 p p + 1 p -1 2 = 0.
I = π 2 16 log(1 + √ 2) p≡1[8] 1 - 4 p p + 1 p -1 2 = 0.
A = {1}, F (X) = 1 -2X -7X 2 -4X 3 , H(X) = 1 -2X + X 2 , s = 1, ∆ = 2
and β = 4. As explained in [START_REF]On numbers of the form n 4 + 1[END_REF], the number of primes ≤ X of the form m 4 + 1 is conjectured to be asymptotically equal to I • X 1/4 / log X. The name "Shanks' constant" comes from Chapter 2, page 90 of [START_REF] Steven | Mathematical constants[END_REF].

When using the script that we introduce below, this value is obtained by multiplying by

π 2 16 log(1+ √
2) the value obtained with the call GetEulerProds(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 prefered 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 1.11 (Lal's Constant). We have p≡1 [START_REF]Primes of the form n 4 + 1[END_REF] p(p -8) (p -4)

λ = π 4 2 7 log 2 (1 + √ 2) p≡1[8] p + 1 p -1 4 1 - 8 p = π 4 2 7 log 2 (1 + √ 2) p≡1[8] 1 - 4 p 2 p + 1 p -1 4 p≡1[8] p(p -8) (p -4) 2 = 0.
q = 8, A = {1}, F (X) = 1 -8X, H(X) = 1 -8X + 16X 2 , s = 1, ∆ = 2
and β = 8. The value of Lal's constant λ is then deduced by combining the value obtained in Corollary 1.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 [START_REF]Lal's constant and generalizations[END_REF], the number of primes ≤ X of the form (m + 1) 2 + 1 and such that (m -1) 2 + 1 is also prime, is conjectured to be asymptotic to λ • X 1/2 /(log X) 2 . The name "Lal's Constant" comes from the papers [START_REF]Primes of the form n 4 + 1[END_REF] and [START_REF]Lal's constant and generalizations[END_REF]. When using the script that we introduce below, the first value is obtained with the call GetEulerProds(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 1.8.

We close this section by mentioning another series of challenging constants. In [START_REF] Moree | On the average number of elements in a finite field with order or index in a prescribed residue class[END_REF], P. Moree computes inter alia the series of constants A χ defined six lines after Lemma 3, page 452, by (1.12)

A χ = p≥2 1 + (χ(p) -1)p (p 2 -χ(p))(p -1)
,

where χ is a Dirichlet character. Our theory applies only when χ 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 = (Z/qZ) × . 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 1.12. Let A 0 be the subset of G = (Z/qZ) × consisting of all the multiplicative generators of G. Assume q is such that such an A 0 is not empty. For any real parameter P ≥ 2 and s > 1, we have

ζ P (s; q, A 0 ) = m|q ∞ S∈G χ∈K ⊥• L P (ms, χ) e(m,q,S)
, where m|q ∞ means that all the prime factors of m divide q and where e(m, q, S) = |S|ϕ(q/|S|) mϕ(q) .

Proof. Indeed, since A 0 generates G, the only index t in (1.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 1.2 when F/H = 1/(1 -X)

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

(2.1) C A (K, m, 1 -X) = t|m µ(t) L∈G , L [t] = A µ(|L|/|K|) |G/K|
where

L [t] = {x t , x ∈ L}.
Notice that it is also a cyclic subgroup of G. Let us first note a simple property.

Lemma 2.1. 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 = (Z/ Z, +). For each d| , the unique subgroup of order

d is {( /d)n, 0 ≤ n ≤ d -1}.
Here is the fundamental property satisfied by these coefficients.

Proposition 2.2. For any positive integer , any prime p and any lattice-invariant class A , we have

hm= K∈G , χ∈K ⊥ χ p h C A (K, m, 1 -X) = 1 1 p∈A .
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

S = hm= K∈G , B [h] ⊂K |G/K|C A (K, m, 1 -X).
Next, we introduce the expression given in (2.1), shuffle the summations and get

S = hm= t|m µ(t) L∈G , L [t] = A K∈G , B [h] ⊂K µ(|L|/|K|).
By Lemma 2.1 and the Möbius function characteristic property, the last summation vanishes when B [h] = L and takes the value 1 otherwise. Since (B [h] ) [t] = B [ht] , this gives us

S = hm= t|m, B [ht] = A µ(t).
We continue in a more classical way:

S = ath= , B [ht] = A µ(t) = ab= , B [b] = A t|b µ(t) = 1 1 B= A , concluding the proof.
Corollary 2.3. For any prime p, any positive real number s and any latticeinvariant class A , we have

m≥1 K∈G χ∈K ⊥ 1-χ(p)p -ms -C A (K,m,1-X)/m = (1 -p -s ) -1 when p ∈ A , 1 otherwise.
Proof. We first check that, for any positive integer m and any subgroup K, we have

exp χ∈K ⊥ h≥1 χ(p h ) hp mhs = χ∈K ⊥ 1 - χ(p) p ms -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) = m≥1 K∈G χ∈K ⊥ h≥1 χ(p h )C A (K, m, 1 -X) mhp mhs .
We set = mh and appeal to Proposition 2.2 to infer that

S(p) = ≥1 1 p s 1 1 p∈A ,
from which our corollary follows readily.

Lemma 2.4. If m has a prime factor that does not divide ϕ(q), we have

C 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 1 p a for some m 1 prime to p and p prime to the order ϕ(q) of G, any divisor t of m factors in t 1 p b where t 1 |m 1 and b ≤ a. The Möbius coefficient reduces these choices to b = a or to b = a -1 and since we have

L [t] = L [t1]
, both are possible. If we denote the contribution of p a t 1 to C 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 2.5. Let f > 1 be a real parameter. We have

log ζ P (f ) ≤ 1 + P/(f -1) P f .
Proof. We use

log ζ P (f ) = - p≥P k≥1
1 kp kf hence, by using a comparison to an integral, we find that

log ζ P (f ) ≤ n≥P 1 n f ≤ 1 P f + ∞ P dt t f = f -1 P + 1 1 (f -1)P f -1 .
Theorem 2.6. For every s > 1 and every P ≥ 2, we have

ζ P (s; q, A) = p+qZ∈A, p≥P (1 -p -s ) -1 = m≥1 K∈G χ∈K ⊥ L P (ms, χ) C A (K,m,1-X)/m .
Proof. This is a simple consequence of Corollary 2.3. Indeed, we may shuffle our series to our fancy by the absolute summability ensured by the condition s > 1 and the bounds |C A (K, k)/k| ≤ |G|, as well as |G | ≤ |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 1.2 in general

Let us recall the Witt decomposition. The readers will find in [9, Lemma 1] a result of the same flavour. We have simply modified the proof and setting as to accomodate polynomials having real numbers for coefficients. Lemma 3.1. Let F (t) = 1 + a 1 t + . . . + a δ t δ ∈ R[t] be a polynomial of degree δ. Let α 1 , . . . , α δ be the inverses of its roots. Put s F (k) = α k 1 + . . . + α k δ . The s F (k) are integers and satisfy the Newton-Girard recursion

(3.1) s F (k) + a 1 s F (k -1) + . . . + a k-1 s F (1) + ka k = 0,
where we have defined a δ+1 = a δ+2 = . . . = 0. Put

(3.2) b F (k) = 1 k d|k µ(k/d)s F (d).
Let β ≥ 1 be such that β ≥ max j |1/α j |. When t belongs to any segment ⊂ (-β, β), we have

(3.3) F (t) = ∞ j=1 (1 -t j ) b F (j)
where the convergence is uniform in the given segment.

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

tF (t) F (t) = i α i t 1 -α i t = k≥1 s F (k)t k .
This series is absolutely convergent in any disc |t| ≤ b < 1/β where β = max j (1/|α j |).

We proceed by expressing s F in terms of b F via (3.2) in a disc of radius b < 1/β. After some shuffling of the terms, we reach the expression

tF (t) F (t) = j≥1 b F (j) 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] on Lie algebras, Witt produced in equation ( 11) therein a decomposition that is the prototype of the above expansion. Lemma 3.2. We use the hypotheses and notation of Lemma 3.1. Let β ≥ 2 be larger than the inverse of the modulus of all the roots of F (t). We have

|b F (k)| ≤ 2 deg F • β k /k. Proof. We clearly have |s F (j)| ≤ deg F • β j , so that |b F (k)| ≤ deg F k 1≤j≤k β j ≤ deg F k β β k -1 β -1 ≤ deg F k β k 1 -1/β ≤ 2 deg F β k k .
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 3.3. Let F (X) = 1 + a 1 X + . . . + a δ X δ be a polynomial of degree δ. Let ρ be one of its roots. Then either

|ρ| ≥ 1 or 1/|ρ| ≤ |a 1 | + |a 2 | + . . . + |a δ |.
Proof. On noticing that

(1/ρ) δ = -a 1 (1/ρ) δ-1 -a 2 (1/ρ) δ-2 -. . . -a δ ,
the conclusion follows. Proof. Let us call this quantity r 0 (t). We first check that it depends only on t mod ϕ(q): this follows from the fact that the map x → x ϕ(q) reduces to the identity over G. Secondly, any prime factor of t, say p , that is prime to ϕ(q), may be removed from t, i.e. r 0 (t) = r 0 (t/p ): the map x → x p is one-to-one in L.

The lemma is an immediate consequence of these two remarks.

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

(3.4) F (t) H(t) = ∞ j=∆ (1 -t j ) b F (j)-b H (j) .
The absence of the term with j < ∆ is due to our assumption that (F (X) -

H(X))/X ∆ ∈ R[X].
j≥J+1 |t j ||b F (j) -b H (j)| ≤ 4 max(deg F, deg H) |tβ| J+1 (1 -|tβ|)(J + 1)
, as soon as |t| < 1/β. We thus have

(3.6) F (t) H(t) = ∆≤j≤J (1 -t j ) b F (j)-b H (j) × I 1 ,
where

| log I 1 | ≤ 4 max(deg F, deg H)|tβ| J+1 /[(1 -|tβ|)(J + 1)
]. Now that we have the expansion (3.6) for each prime p, we may combine them. We readily get p≥P, p+qZ∈A

F (1/p s ) H(1/p s ) = p≥P, p+qZ∈A ∆≤j≤J (1 -p -js ) b F (j)-b H (j) × I 2 ,
where I 2 satisfies

| log I 2 | ≤ 4 max(deg F, deg H) p≥P β J+1 1 -β/P s 1 (J + 1)p (J+1)s ≤ 4 max(deg F, deg H)β J+1 (1 -β/P s )(J + 1) 1 P (J+1)s + ∞ P dt t (J+1)s ≤ 4 max(deg F, deg H)(β/P s ) J β (1 -β/P s )(J + 1) 1 P s + 1 Js + s -1 ,
since P ≥ 2 and J ≥ 3. Letting J go to infinity, we see that when P s > β and s > 1/∆, p≥P, p+qZ∈A

F (1/p s ) H(1/p s ) = j≥∆ p≥P, p+qZ∈A (1 -p -js ) b F (j)-b H (j) = j≥2 ζ P (js; q, A ) b H (j)-b F (j)
in the notation of Theorem 2.6. We use this theorem to infer that p≥P, p+qZ∈A

F (1/p s ) H(1/p s ) = j≥∆ m≥1 K∈G χ∈K ⊥ L P (mjs, χ) C A (K,m,1-X) m (b H (j)-b F (j))
.

Notice that we have s H (j) -s F (j) = 0 (and hence b H (j) -b F (j) = 0) when j < ∆ by our assumption on ∆. Let us glue the variables m and j in n. On using the definitions (2.1) and (3.2), we see that the functions m

→ C A (K, m, 1 -X)/m and j → (b H (j) -b F (j)) are of the form (1 1 r)(m)/m, respectively (µ (s H -s F ))(j)/j. Hence n jm=n C A (K, m, 1 -X) m (b H (j) -b F (j)) = td=n r(t) s H (d) -s F (d) .
We replace r(t) by its value to conclude that this sum is C A (K, m, F/H), as defined by (1.4). We have reached

(3.7) p≥P, p+qZ∈A F (1/p s ) H(1/p s ) = n≥∆ K∈G χ∈K ⊥ L P (ns, χ) C 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 n in (3.7) in m again. To control the tail, we check that, by Lemma 2.5,

± log m≥M +1 K∈G χ∈K ⊥ L P (ms, χ) C A (K,m,F /H) m ≤ m≥M +1 K∈G |C A (K, m, F/H)| m |G/K| ms -1 + P P ms ≤ m≥M +1 K∈G t|m µ 2 (t)|G |(deg F + deg H)β m/t ms -1 + P mP ms ≤ (deg F + deg H)|G | 2 m≥M +1 β m 1 -(1/β) s + P P ms ≤ (deg F + deg H)|G | 2 β(s + P ) β -1 1 1 -(β/P s ) β P s M +1 ≤ 4(deg F + deg H)|G | 2 (s + P ) β P s M +1
.

Link with two other sets of inequalities

In this section, we develop some elements that are contiguous to our topic.

A formula.

Lemma 4.1. Let q > 1 be a modulus. We set G 0 to be a subgroup of G = (Z/qZ) × and G ⊥ 0 be the subgroup of characters that take the value 1 on G 0 . For any integer b, we define b to be the subgroup generated by b modulo q. We have

χ∈G ⊥ 0 L P (s, χ) = G0⊂K⊂G p≥P, p G0=K 1 -p -|K/G0|s -|G/K| .
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.

Proof. We note that χ∈G

⊥ 0 (1 -χ(p)z) χ(a) = ψ∈ L(1 -ψ(p)z) f (ψ) when p = L and where (4.1) f (ψ) = χ∈G ⊥ 0 , χ|L=ψ χ(a).
The condition χ ∈ G ⊥ 0 can also be written as χ|G 0 = 1, hence we can assume that ψ|(L ∩ G 0 ) = 1. We write

χ∈G ⊥ 0 (1 -χ(p)z) χ(a) = ψ ∈ LG0, ψ |G0=1 (1 -ψ(p)z) f (ψ ) , where (4.2) f (ψ ) = χ∈G ⊥ 0 , χ|LG0=ψ χ(a).
When a lies outside LG 0 , this sum vanishes; otherwise it equals |G/(LG 0 )|ψ (a). The characters of LG 0 that are trivial on G 0 are canonically identified with the characters of the cyclic group (LG 0 )/G 0 . We thus have

ψ ∈ LG0, ψ |G0=1 (1 -ψ(p)z) = 1 -z |(LG0)/G0| ,
and this proves our formula.

Notes on the scope of Lemma 4.1. From a metholodogical viewpoint, a moment's thought discloses that two residue classes modulo q that fall inside the same lattice-invariant class cannot be distinguished by the set of identities of Lemma 4.1. This implies that we indeed extract the maximum information from our setting. This could be formalized in the following manner: consider the vector space F [G] of functions from G to C, and the sub-space generated by (1 1 G0 ) G0∈G . This subspace is clearly included in the subspace generated by (1 1 A ) A∈G . These two spaces can be shown to be equal. We end this discussion here, as we do not need this fact.

Link with abelian field theory. The case G 0 = {1} in the identity of Lemma 4.1 is classical in Dedekind zeta function theory for the field Q(ζ q ), where ζ q = exp(2iπ/q), and can be found in [START_REF] Serre | Cours d'arithmétique, Collection SUP[END_REF]Proposition 13] in a rephrased form. For the general case, we follow [START_REF] Narkiewicz | Elementary and analytic theory of algebraic numbers[END_REF]Chapter 8] by Narkiewicz. The Dedekind zeta-function associated with an abelian field K is given by

(4.3) ζ K (s) = χ∈X(K) L(s, χ)
as per [START_REF] Narkiewicz | Elementary and analytic theory of algebraic numbers[END_REF]Theorem 8.6]. The group X(K) is the group of characters attached to K, see [START_REF] Narkiewicz | Elementary and analytic theory of algebraic numbers[END_REF]Proposition 8.4]. This equality (4.3) 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 q, which excludes at least the ramified primes. Let H q (K) be the subgroup of the integers r mod q that are such that the automorphism of Q(ζ q ) defined by ζ q → ζ r q is the identity on K. The sets X(K) and H q (K) ⊥ are almost equal: X(K) is made only of primitive characters associated to the characters in H q (K) ⊥ . We may select G 0 = H q (K) in Lemma 4.1. Some work involving the decomposition law in abelian number fields, which may for instance be found in [START_REF] Narkiewicz | Elementary and analytic theory of algebraic numbers[END_REF]Theorem 8.2], gives us, when the prime factors of q are all at most P , that The proof we provide of Lemma 4.1 is much simpler, but the above analysis establishes that the identities stemming from both approaches are the same.

Timing and implementation notes

Let s > 1 be a real number and P ≥ 2 be a parameter. We consider the vector, for any positive integer t:

(5.1) Γ P,s (t) = log χ∈G ⊥ 0 L P (ts, χ)

G0∈G

.

The rows of Γ P,s (t) are indexed by the cyclic subgroups of G. An approximate value of this vector is provided by the function GetGamma of the script LIEP.sage from the values of the Hurwitz zeta function. We next define (5.2)

V s (t) = log ζ P (ts; q, A) A∈G .

The rows of V s (t) are indexed by classes. We also define

(5.3) Γ P,s (t) = log χ∈K ⊥ L P (ts, χ) K∈G .
The function GetLatticeInvariantClasses of the script LIEP.sage 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 GetVs):

Input. Input the four parameters q, s, nbdecimals and bigP as well as the two parameters that control the output Verbose and WithLaTeX.

Precomputation-1. Compute and store the algebraic quantities that we need: the tuple of cyclic subgroups of G = (Z/qZ) × , 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 function GetStructure.

Initialization. Find M so that the right-hand side of (1.6) is less than 10 -nbdecimals-10 .

Precomputation-2. Build the set M of integers m such that m ≤ M and all the prime factors of m divide q. Then compute the constants (C A (K, m, 1 -X)) for every possible class A and every m in M .

Main Loop. For m ∈ M , add the contribution of this index to the sum approximating V s (1) from the right-hand side of (1.5) with P = bigP.

Post-computation. Complete the products with the values for primes p < bigP.

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 via load('LIEP.sage'), a typical call will be GetVs(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 GetGamma, 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 WithLaTeX. 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 WithLaTeX is 1, the values of the constants will be further presented in a format suitable for inclusion in a L A T E X-file. The digits presented in L A T E X-format when WithLaTeX = 1 are always accurate. For instance, the call GetVs(12, 2, 100, 100, 2, 1) is the one used to prepare the addendum [START_REF] Ettahri | Some Euler Products[END_REF] 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 1.2 (with P = 2, the parameter bigP being used to decide from which point onwards we use the usual Euler product or the expression of the theorem) is implemented in:

GetEulerProds(q, s, F, H, nbdecimals, bigP = 100, Verbose = 2, WithLaTeX = 0).

The parameter bigP may be increased by the script to ensure that P ≥ 2β (a condition that is usually satisfied). We reused the same structure as the one for the function GetVs except that the set of indices m is now a full interval. Since the coefficients |b F (j) -b G (j)| may increase like β j , we increase the working precision by J log β/ log 2.

Checking. The values given here have been checked in several ways. The coauthors of this paper have run several independent scripts. We also provide the function GetVsChecker(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 [START_REF] Steven | Mathematical constants[END_REF] gives 10 digits) and we agree with those. Finally, the web site [START_REF] Gourdon | Constants from number theory[END_REF] Our result matches that of [START_REF] Gourdon | Constants from number theory[END_REF].

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 1.8. We present five tables:

• A first table for 3 ≤ q ≤ 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 ≤ 16, 91 ≤ q ≤ 100 and 200 ≤ q ≤ 220. This last interval contains the first integer q such that r = ω(ϕ(q)) = 4, namely q = 211.

• And finally a table for q ∈ {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 1 may be reproduced with the call:

TablePerformance(3, 51, 100, 100) In these tables, r = ω(ϕ(q)) is the number of distinct prime divisors of q as in Corollary 1.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 ≤ M such that m|ϕ(q) ∞ . We otherwise follow the notation of Theorem 1.2.

It seems likely, when looking at Tables 1, 2, 3 and 4 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 ϕ(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 = ω(ϕ(q)) Table 5 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. q ϕ(q) r #m s |G | M Time (s/10) 3

where s > 1 and χ 1 , 4

 14 is the (only) non-principal Dirichlet character modulo 4. Since both ζ(2 k s) and L(2 k s, χ 1,4 ) are 1 + O(1/2 s2 k ), we only need to compute O(log D) values of L-functions (including the Riemann ζ-function) to obtain D decimal digits.

(1. 4 )

 4 C A (K, m, F/H) = t|m µ(t)s H/F (m/t) L∈G , L [t] = A , K⊂L µ(|L|/|K|) |G/K|where L [t] = {x t , x ∈ L} and A is the subgroup generated by A . We have(1.5) p≥P, p+qZ∈A F (1/p s ) H(1/p s ) = m≥∆ K∈G χ∈K ⊥ L P (ms, χ) C A (K,m,F/H)/m

Lemma 3 . 4 .

 34 The sum L∈L µ(|L|/|K|) where L = {L ∈ G /L[t] = A and K ⊂ L} depends only on gcd(t, ϕ(q)).

  χ∈X(K) L P (s, χ) = Hq(K)⊂K⊂Gq p≥P, p Hq(K)=K 1 -p -|K/Hq(K)|s -|Gq/K| .

  We deduce the first value given in this Corollary by using Theorem 1.2 with the parameters

	79220 82381 67541 66877 54555 66579 02410 11289 32250 98622
	11172 27973 45256 95141 54944 12490 66029 53883 98027 52927 • • •

  Up to this point (3.4) is only established as a formal identity. Our second step is to establish (3.4) for all t ∈ C with |t| < 1/β. By Lemma 3.2, we know that |b F (j) -b H (j)| ≤ 4 max(deg F, deg H)β j /j.

	Therefore, for any bound
	J, we have
	(3.5)

  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 π 2 2

	p≡1[4]	1 -	4 p	p + 1 p -1	2	= 1.95049 11124 46287 07444 65855 65809 55369 25267 08497 71894 30550 80726 33188 94627
						61381 60369 39924 26646 98594 38665 • • •

Table 2 .

 2 Time used when asking for 1000 digits for q ≤ 16

		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
	q ϕ(q) r #m s |G | 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

Table 3 .

 3 Time used when asking for 1000 digits for 90 < q ≤ 100

	q ϕ(q) r #m s |G | 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 4 .

 4 Time used when asking for 1000 digits for 200 ≤ q ≤ 220


O Ramar

NOTES ON RESTRICTION THEORY IN THE PRIMES

Keywords: Restriction Theory, Selberg sieve, Envelopping sieve. 1

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction and some results

During the proof of Theorem 3 of [START_REF] Bourgain | On Λ(p)-subsets of squares[END_REF] and by using specific properties of the primes, J. Bourgain established (in Equation (4.39) therein) the estimate (1) ∀ > 2, 1 0 p≤N u p e(pα) dα

1/ N -1/ N log N p≤N |u p | 2 1/2 .
This proof was improved by B. Green in [START_REF] Green | Roth's theorem in the primes[END_REF]Theorem 1.5]. A striking feature of (1) is that it is not valid when = 2 as Parseval formula easily shows. Understanding the transition became then an open question, an answer to which is provided in Corollary 1.2 below. In the paper [START_REF] Green | Restriction theory of the Selberg sieve, with applications[END_REF], B. Green & T. Tao reduced the proof to using only sieve properties. They in fact considered a more general setting, that could be encompassed in the framework of sufficiently sifted sequences of [START_REF] Ramaré | Additive properties of dense subsets of sifted sequences[END_REF], and the same holds for our estimates. We prefer however to restrict our attention to the better known case of the prime numbers but will nonetheless present some obvious generalization to the case of primes in some interval in the last section. The methods used (essentially the large sieve and envelopping sequences) remain general enough to warrant an extension to a much more general case. The somewhat reverse situation of smooth numbers has been the subject of the work [START_REF] Harper | Minor arcs, mean values, and restriction theory for exponential sums over smooth numbers[END_REF] by A.J. Harper, to which we borrow an idea (see around Equation 17 below).

Explicit values for the constants are provided for three reasons: it avoids us saying that these are independant of the involved parameters; it puts forward that our argument is elementary enough; and finally, it shows that some work is still required to improve on them and to determine what are the optimal ones. We did not work overmuch on these constants.

Here is our first result.

Theorem 1.1. Let X be a δ-well spaced subset of R/Z. Assume N ≥ 10 11 and let h > 0. We have .

Let us recall that a set X ⊂ R/Z is said to be δ-well spaced when min x =x ∈X |xx | Z ≥ δ, where |y| Z = min k∈Z |y -k| denotes in a rather unusual manner the distance to the nearest integer. On taking

X = {β + k/N, 0 ≤ k ≤ N -1}
and integrating over β in [0, 1/N ], we get the corollary we advertised above.

Corollary 1.2. Assume N ≥ 10 11 and let h > 0. We have

1 0 p≤N u p e(pα) 2+h dα ≤ 10 7 (1 + 3 2 log N ) h + 1/h N 2N log N p≤N |u p | 2 1+h/2
. This result offers an optimal (save for the implied constants) transition to the case h = 0. Indeed, on selecting h = 1/ log N , this corollary implies that, when |u p | ≤ 1, we have te optimal

1 0 p≤N u p e(pα) 2+h dα p≤N |u p | 2 .
In the same line, but maybe more strickingly, our result implies a uniform Hardy-Littlewood majorant property, in the sense for instance of the paper [START_REF] Green | On the Hardy-Littlewood majorant problem[END_REF] In other words, the constant C( ) in Theorem 1.5 of [START_REF] Green | Roth's theorem in the primes[END_REF] is uniformly bounded, and in fact by 10 7 . Guessing and getting the optimal constant is open, whether under the L ∞ -condition |u p | ≤ 1 or under the L 2 -condition we use.

At the heart of B. Green & T. Tao's result lies an estimate close to our next theorem. The main difference (aside from the fact that we state it in dual format, Theorem 4.1 below being its true analogue) is that the dependence in |X | is not |X | ε , but log(2|X |). This positive ε came from some average of restricted divisors. A more precise proof led to exp c log |X | log log |X | for some constant c > 0, but to nothing better. Theorem 1.4. Let X be a δ-well spaced subset of R/Z and N ≥ 10 11 . Let (u p ) p≤N be a sequence of complex numbers. We have

x∈X 1≤p≤N u p e(xp) 2 ≤ 10 6 N + δ -1 log N p≤N |u p | 2 log(2|X |).
This result should be compared with Theorem 5.3 of [START_REF] Ramaré | Arithmetical aspects of the large sieve inequality[END_REF] where the summation is over the points a/q for q ≤ Q 0 ≤ √ N :

(2)

q≤Q 0 a mod * q n u n e(na/q) 2 ≤ 7 N log Q 0 log N n |u n | 2
provided u n vanishes as soon as n has a prime factor less than √ N . A way to compare both results is to state the maximal estimate we can now get.

Corollary 1.5. Let N ≥ 10 11 and Q 0 ∈ [2, √ N ].
Let (u p ) p≤N be a sequence of complex numbers. We have

q≤Q 0 a mod * q max |α-a q |≤ 1 qQ 0 1≤p≤N
u p e(αp)

2 ≤ 10 7 N log Q 0 log N p≤N |u p | 2 .
From a methological viewpoint, our main innovation lies in the introduction of a preliminary sieving in the envelopping sieve. This completely eliminates any restricted divisors estimate. It has also the effect of reducing the proof sizeably.

Acknowledgment. This work has been completed when the author was enjoying the hospitality of the Hausdorff Research Institute for Mathematics in Bonn in june 2021.

Some averages of multiplicative functions

We define P (z 0 ) = p<z 0 p and

(3) G d (y; z 0 ) = ≤y, ( ,dP (z 0 ))=1 µ 2 ( ) ϕ( ) , G(y; z 0 ) = G 1 (y; z 0 ).
We bound it from below in an effective manner, via some steps based of Rankin's trick. We start with some estimates due to J.B. We assume that log y ≥ S > 0. Then

n≤y, k(n)|P (z) µ 2 (n)f (n) ≥ p≤z (1 + f (p)) 1 -exp - log z log y K log y S
where k(n) = p|n p and

K(t) = log t -1 + 1/t. Lemma 2.3. We have, when z ≥ 1 d≤z µ 2 (d) ϕ(d) = log z + c 0 + O * (3.95/ √ z)
where

c 0 = γ + p≥2 log p p(p-1) . Also d≤z µ 2 (d) ϕ(d) ≤ log z + 1.4709.
Proof. The first estimate is taken from [8, Theorem 1.2] while the second one is [9, Lemma 3.5, (1)]

Lemma 2.4. When 320 ≤ z 0 ≤ z, we have G(z; z 0 ) ≥ 3 40 log z log z 0 . When 2 ≤ z 0 ≤ z and z ≥ 320, we have G(z; z 0 ) ≥ 1 111 log z log z 0 .
Proof. We define the auxiliary function

G(y, z; z 0 ) = d≤y, k(n)|P (z)/P (z 0 ) µ 2 (d) ϕ(d)
.

We readily find that

G(∞, z; z 0 ) = z 0 ≤p<z 1 - 1 p -1
.

By Lemma 2.1, we obtain a lower estimate for this product:

G(∞, z; z 0 ) ≥ log z log z 0 1 - 1 2(log z 0 ) 2 2 ≥ 0.97 log z log z 0 . In Lemma 2.2 with f (n) = µ 2 (n)1 1 k(n)≥z 0 /ϕ(n), we find that S = z 0 ≤p<z log p p = log z z 0 + O * 2 log z 0
where we appealed to Lemma 2.1 for the approximate estimate. Notice that S ≤ log z since -log z 0 + 2/ log z 0 ≤ 0. We thus get

G(y, z; z 0 ) ≥ G(∞, z; z 0 ) 1 -exp - log z log y K(3)
as soon as log y ≥ 3 log z since then, K((log y)/S) ≥ K(2) = 0.4319 • • • , and thus, in particular,

G(y, z; z 0 ) ≥ G(∞, z; z 0 )(1 -e -0.4319 ) ≥ 0.34 log z log z 0 .
We complete this estimate with

G(z 3 , z; z 0 ) -G(z, z; z 0 ) = z<d≤z 2 , z 0 ≤k(n)<z µ 2 (d) ϕ(d) ≤ z<d≤z 2 µ 2 (d) ϕ(d) ≤ 3 + 8 √ z ≤ 3.45 by Lemma 2.3. Whence G(z, z; z 0 ) ≥ 0.34 log z log z 0 -3.45.
Since also G(z, z; z 0 ) ≥ 1 (by considering the contribution of d = 1), we find that

G(z, z; z 0 ) ≥ min c≥1 max 0.34 - 3.45 c , 1 c log z log z 0 ≥ 3 40 log z log z 0 .
This yields the first estimate of the lemma. The second one is simply infered from this through

G(z; z 0 ) ≥ G(z; 320) ≥ 3 log 2 40 log 320 log z log z . Lemma 2.5. Let h > 0. We have d≤D µ 2 (d) ϕ(d) 1+h ≥ 1 -D -h h .
Proof. We first notice that

d≤D µ 2 (d) ϕ(d) 1+h ≥ d≤D µ 2 (d) d 1+h p|d k≥0 1 p k 1+h ≥ d≤D µ 2 (d) d 1+h p|d k≥0 1 p k(1+h) = q≥1, k(q)≤D 1 q 1+h ≥ q≤D 1 q 1+h .
Concerning this last quantity, we write

q≤D 1 q 1+h = D 1 q≤t 1 (1 + h)dt t 2+h + [D] D 1+h ≥ D 1 (t -1) (1 + h)dt t 2+h + D -1 D 1+h = h + 1 h 1 - 1 D h + D -1 D 1+h ≥ 1 -D -h h + 1 - 1 D 1+h ≥ 1 -D -h h as required.
3. An enveloping sieve

We fix two real parameters z 0 ≤ z and first consider the sole case of prime numbers. It is easy to reproduce the analysis of [START_REF] Ramaré | Additive properties of dense subsets of sifted sequences[END_REF]Section 3] as far as exact formulae are concerned, but one gets easily sidetracked towards slightly different formulae. The reader may for instance compare [9, Lemma 4.2] and [11, (4.1.14)]. Similar material is also the topic of [START_REF] Ramaré | Arithmetical aspects of the large sieve inequality[END_REF]Chapter 12]. So we present a path leading to [11, (4.1.14)] in our special case.

Following the notation of Section 2, we set (4)

β z 0 ,z (n) = d|n λ d 2 , λ d = 1 1 (d,P (z 0 ))=1 µ(d)dG d (z/d; z 0 ) ϕ(d)G(z; z 0 ) .
Section 3 of [START_REF] Ramaré | Additive properties of dense subsets of sifted sequences[END_REF] corresponds to z 0 = 1. We introduce

(5) λ = µ 2 ( )1 1 ( ,P (z 0 ))=1 ϕ( ) M z 0 (z/ ) G(z; z 0 ) , M z 0 (y) = m≤y, (m,P (z 0 ))=1 µ(m).
We readily check that ( 6)

λ d = µ(d) d| λ , λ = µ( ) |d λ d ,
and a further simple verification leads to

(7) ∀n ≥ 2, d|n λ d = / ( ,n)=1 λ .
We explained in [START_REF] Ramaré | Arithmetical aspects of the large sieve inequality[END_REF]Chapter 11] why working with (λ ) leads to more regular formulae than working with (λ d ) d . We write

β z 0 ,z (n) = d|n λ d 2 = (n, )=1 λ 2 = 1 , 2 λ 1 λ 2 1 1 (n,[ 1 , 2 ])=1 .
Let us now notice the exact formula

(8) ∀n ≥ 2, 1 1 (n,r)=1 = ϕ(r) r q|r µ(q)c q (n) ϕ(q) .
On using this expression, we reach

β z 0 ,z (n) = 1 , 2 λ 1 λ 2 ϕ([ 1 , 2 ]) [ 1 , 2 ] q|[ 1 , 2 ] µ(q)c q (n) ϕ(q) = q q|[ 1 , 2 ] λ 1 λ 2 ϕ([ 1 , 2 ]) [ 1 , 2 ]
µ(q)c q (n) ϕ(q) = q≤z 2 , (q,P (z 0 ))=1 µ(q) ϕ(q) w q c q (n). ( 9)

The formula for w q that emerges from the above reads: [START_REF] Ramaré | Arithmetical aspects of the large sieve inequality[END_REF]

w q = q|[ 1 , 2 ] λ 1 λ 2 ϕ([ 1 , 2 ]) [ 1 , 2 ] .
We plug [START_REF] Green | Roth's theorem in the primes[END_REF] in this to get

G(z; z 0 ) 2 w q = q|[ 1 , 2 ] 1 ϕ( 1 ) 2 ϕ( 2 ) ϕ([ 1 , 2 ]) [ 1 , 2 ] M z 0 (z/ 1 )M z 0 (z/ 2 ) = q|[ 1 , 2 ] ( 1 , 2 ) ϕ(( 1 , 2 )) M z 0 (z/ 1 )M z 0 (z/ 2 ).
We notice that r ϕ(r) = δ|r

1 ϕ(δ) , whence (11)
G(z; z 0 ) 2 w q = δ≤z, (δ,P (z 0 ))=1 µ 2 (δ) ϕ(δ) δ| 1 ,δ| 2 , q|[ 1 , 2 ] M z 0 (z/ 1 )M z 0 (z/ 2 )
where we are now just a moment's away from the expression [START_REF] Rosser | Approximate formulas for some functions of prime numbers[END_REF] G(z; z 0 ) 2 w q = δ≤z, (δ,P (z 0 ))=1 µ 2 (δ) ϕ(δ) ρ z 0 ,z (q, δ) with (13) ρ z 0 ,z (q, δ) = q/(δ,q)=q 1 q 2 q 3 , (q 1 ,q 2 )=(q 2 ,q 3 )=(q 1 ,q 3 )=1, max(q 1 q 3 δ,q 2 q 3 δ)≤z, (δ,P (z 0 ))=1

(-1) ω(q 3 ) .

Reaching this expression for ρ z 0 ,z (q, δ) is done exactly as in [10, Lemma 12.1] or as next to [11, (4.1.14)].

Lemma 3.1. When 2 ≤ z 0 ≤ z and z ≥ 320, we have w q ϕ(q) ≤ 11500 log z 0 √ q log z .

Proof. We deduce from (13) the estimate |ρ z 0 ,z (q, δ)| ≤ 3 ω(q) , and thus

(14) |G(z; z 0 )w q | ≤ 3 ω(q) .
We use Lemma 2.4 to get ≤ 330 000

w q ϕ(q) ≤ p max 3 √ p p -1 , 1 1 G(z; z 0 ) √ q ≤ 11500 log z 0 √ q log z .
(N + δ -1 ) f 2 2 log(2 f 2 1 / f 2 2 ) log N .
Proof. Let z = N 1/4 ≥ 320 and

z 0 = 2 f 2 1 f 2 2 2 ≥ 2.
We have

z 0 ≤ z when f 2 1 / f 2 2 ≤ N 1/8 /2.
When this condition is not met, we use the dual of the usual large sieve inequality to infer that

1≤p≤N b∈B f (b)e(bp) 2 ≤ (N + δ -1 ) f 2 2 ≤ (N + δ -1 ) f 2 2 log(2 f 2 1 / f 2 2 ) log(N 1/8 /2)
.

Some numerical analysis shows that this establishes our inequality in this case. Henceforth, we assume that z 0 ≤ z. We first notice that

1≤p≤z b∈B f (b)e(bp) 2 ≤ z f 2 1 ≤ N 3/8 f 2 2 /2 ≤ N f 2 2 log(2 f 2 1 / f 2 2 ) log N log N N 5/8 log 2 ≤ 1 53000 N f 2 2 log(2 f 2 1 / f 2 2 ) log N .
Let us now call W the quantity to be studied with z < p ≤ N . We bound above the characteristic function of those primes by our enveloping sieve and further majorize the characteristic function of the interval [1, N ] by a function ψ of non-negative Fourier transform supported by [-δ 1 , δ 1 ] where δ 1 = min(δ, 1/(2z 4 )). This leads to

W ≤ q≤z 2 , (q,P (z 0 ))=1 w q ϕ(q) a mod * q b 1 ,b 2 f (b 1 )f (b 2 ) n∈Z e((b 1 -b 2 )n)e(an/q)ψ(n).
We split this quantity according to whether q < z 0 or not:

W = W (q < z 0 ) + W (q ≥ z 0 ).
When q ≥ z 0 , Poisson summation formula tells us that the inner sum is also m∈Z ψ(b 1 -b 2 -(a/q) + m). The sum over b 1 , b 2 and n is thus

≤ (N + δ -1 1 ) b 1 ,b 2 f (b 1 )f (b 2 )# (a/q)/ b 1 -b 2 + a/q < δ 1 .
Given (b 1 , b 2 ), at most one a/q may work, since 1/z 4 > 2δ 1 . By bounding above w q by Lemma 3.1, we see that

W (q ≥ z 0 ) ≤ 11500(N + δ -1 1 ) f 2 1 log z 0 √ z 0 log z ≤ 11500 √ 2 (N + δ -1 1 )
f 2 2 log z 0 log z .

When q < z 0 , only q = 1 remains. This yields

W (q < z 0 ) ≤ (N + δ -1 1 )
111 f 2 2 log z 0 log z .

We check that (N + δ -1 1 ) ≤ N +4N N (N + δ -1 ). We finally get

1≤p≤N b∈B f (b)e(bn) 2 ≤ 1 53000 + 5 × 2 × 4 × 11500 √ 2 + 111 × (N + δ -1 ) f 2 2 log(2 f 2 1 / f 2 2 ) log N .
The proof of the Theorem follows readily.

5. On moments. Proof of Theorem 1.1

Lemma 5.1. Assume y/ log y ≤ t with y ≥ 2 and t ≥ 10 7 . Then y ≤ 2t log t.

Proof. Our property is trivial when y ≤ 10 7 . Notice that the function f : y → y/ log y is non-increasing when y ≥ e. We find that f (2t log t) ≥ t ≥ f (y), whence 2t log t ≥ y as sought.

Proof of Theorem 1.1. For typographical simplification, we define

(15) B = N + δ -1 log N p≤N |u p | 2 1/2 .
We also set = 2 + h. For any ξ > 0, we examine the set

(16) X ξ = x ∈ X / p≤N u p e(xp) ≥ ξB .
By Lemma 2.1, we see that ξ ≤ c 1 = min(5/4, 1 + 3 2 log N ) or else, the set X ξ is empty. We consider (as in [START_REF] Harper | Minor arcs, mean values, and restriction theory for exponential sums over smooth numbers[END_REF], bottom of page 1141) We apply Cauchy's inequality to this expression to get

Γ(ξ) 2 ≤ p≤N |u p | 2 p≤N x∈X ξ c(x)e(xp) 2 ≤ 330 000 B 2 |X ξ | log(2|X ξ |)
by Theorem 4.1. It follows from this upper bound that

ξ 2 |X ξ | 2 B 2 ≤ Γ(ξ) 2 ≤ 330 000 B 2 |X ξ | log(2|X ξ |) whence 2|X ξ |/ log(2|X ξ |) ≤ 660 000 /ξ 2 .
which we convert with Lemma 5.1 in 2|X ξ | ≤ 10 6 ξ -2 log(10 6 /ξ 2 ).

We can now turn towards the proof of the stated inequality and select ξ j = c 1 /c j for some c > 1 that we will select later. We get

x∈X p≤N u p e(xp) /B ≤ j≥0 c 1 c j (|X ξ j | -|X ξ j+1 |) ≤ 10 6 2 j≥0 c -2 1 (log(10 6 ) -2 log c 1 + 2j log c) c ( -2)j . ≤ 10 6 2 j≥0 c -2 1 (14 + 2j log c) c ( -2)j .
We note that

10 6 2 j≥0 c -2 1 × 14 c ( -2)j = 10 6 × 14 × c -2 1 1 -c 2- and 10 6 2 j≥1 c -2 1 j 2 log c c ( -2)j ≤ 10 6 (log c) c -2 c -2 1 j≥1 j c ( -2)(j-1) ≤ 10 6 × (c 1 /c) -2 log c (1 -c 2-) 2 .
When ≥ 3, we select c = 2, getting

x∈X p≤N u p e(xp) 2+h ≤ (14•10 6 (1+ 3 2 log N ) h +10 6 ) N + δ -1 log N p≤N |u p | 2 1+h/2
.

When ∈ (2, 3), we select c = exp(1/h), getting

x∈X p≤N u p e(xp) 2+h ≤ 10 7 (1+ 3 2 log N ) h + 10 6 h N + δ -1 log N p≤N |u p | 2 1+h/2
.

Our theorem follows readily.

6. Large sieve bound on small sets. Proof of Theorem 1.4

Proof of Theorem 1.4. We write

W = x∈X 1≤p≤N
u p e(xp)

2 = x∈X p≤N u p S(x)
where S(x) = 1≤p≤N u p e(xp). On using the Cauchy-Schwarz inequality, we get

W 2 ≤ p≤N |u p | 2 p≤N x∈X S(x)e(xp) 2 .
We invoque Theorem 4.1 and notice that

x∈X |S(x)| 2 ≤ |X | x∈X |S(x)| 2 .
This leads to

W 2 ≤ 330 000 N + δ -1 log N p≤N |u p | 2 x∈X |S(x)| 2 log(2|X |).
On simplifying by x∈X |S(x)| 2 (after discussing whether it vanishes or not), we get our estimate. The argument employed at the bottom of page 1626 of [START_REF] Green | Roth's theorem in the primes[END_REF] by B. Green is not enough for us. Instead, we got our inspiration from the argument developped by R.C. Vaughan in [START_REF] Vaughan | The L 1 mean of exponential sums over primes[END_REF]. It runs as follows. We first notice that

a mod * q S a q + β ≤ a mod * q S a q + β 1/ a mod * q 1 ( -1)/
.

A direct inspection shows that

a mod * q S a q + β = µ(q)S(β) + T (q, β)
where T (q, β) = p|q e(pβ)(c q (p) -µ(q)). The bound |c q (n)| ≤ ϕ((n, q)) for the Ramanujan sum c q (n) (use for instance the von Sterneck expression for c q (n)) gives us

(19) |T (q, β)| ≤ p|q (p -1 + 1) ≤ q.
The last inequality follows from the trivial property that a sum of positive integers is certainly not more than its product. We next get a lower bound for S(β) by writing

1 -e(βp) = 2iπ βp 0 e(t)dt whence (20) |S(β)| ≥ S(0) -2πβN S(0) ≥ (1 -2πβN )S(0) ≥ (1 -2πβN ) N log N by Lemma 2.1. When |β| ≤ 1/(7N ), this leads to |S(β)| ≥ c 2 N/ log N with c 2 = 1 -2π/7,
and, when q is squarefree and not more than

√ N , to (21) µ(q)
S(β) + T (q, β) ≥ c 2 N log N - √ N ≥ N 10 log N .
We thus get, when |β| ≤ 1/(7N ),

a mod * q S a q + β ≥ µ 2 (q) ϕ(q) -1 |S(β) + T (q, β)| ≥ µ 2 (q) ϕ(q) -1 N 10 log N . Thus 1 0 |S(α)| dα ≥ q≤ √ N a mod * q µ 2 (q) a q + 1 7N a q -1 7N S a q + β dβ ≥ 2 7N q≤ √ N µ 2 (q) ϕ(q) -1 N 10 log N .
By Lemma 2.5, we conclude that

1 0 |S(α)| dα ≥ 1 - √ N 2- - 2 2 7N
N 10 log N .

We thus find that

K(2 + h) = 10 7 (1 + 3 2 log N ) h + 1/h N 2N 2 (log N ) 2 /2 h 1 - √ N -h 7N 2 N 10 log N - = 10 7 (1 + 3 2 log N ) h + 1/h 2 /2 h 1 - √ N -h 7 2 10
.

When h ≥ 1, this is readily bounded above by 10 8 • 20 . Else, it is bounded above by 3

• 10 12 h h 1 - √ N -h = 3 • 10 12 1 - √ N -h .
This is bounded above by 10 13 when h ≥ 1/ log N . When 0 ≤ h ≤ 1/ log N , we use

K(2 + h) = 5/4 N N log N h log N 1 - √ N -h 7N 2 N 10 log N - ≤ 7
F (Q 0 ) = a q , 1 ≤ a ≤ q ≤ Q 0 , (a, q) = 1 (23) = 0 < x 1 < x 2 < . . . < x K = 1 in F 1 (Q 0 ) = {x 2i , 1 ≤ i ≤ K/2} union F 2 (Q 0 ) = {x 2i+1 , 1 ≤ 0 ≤ (K -1)/2}.
We recall that the distance between two consecutive points a/q and a /q in F (Q 0 ) is 1/(qq ); this is at least as large as

1 qQ 0 + 1 q Q 0 by the known property q+q ≥ Q 0 . Hence two intervals [ a 1 q 1 -1 q 1 Q 0 , a 1 q 1 + 1 q 1 Q 0 ] and [ a 2 q 2 -1 q 2 Q 0 , a 2 q 2 + 1 q 2 Q 0 ] with a 1 q 1 , a 2 q 2 ∈ F 1 (Q 0 ) are separated by at least 1/Q 2 0 .
We check this is also true when seen on the unit circle: the largest point of F (Q 0 ) is 1 and its smallest is

1 [Q 0 ] . The same applies to F 2 (Q 0 ). We finally notice that |F (Q 0 )| ≤ Q 0 (Q 0 + 1)/2 ≤ Q 2 0 . To prove our corollary, for every x 2i ∈ F 1 (Q 0 ), we select a point x2i such that (24) p≤N u p e(p x2i ) = max |x-x 2i |≤ 1 qQ 0 p≤N u p e(px)
and apply Theorem 1.4 to the set X1 = {x 2i }. We proceed similarly with F 2 (Q 0 ). The last details are left to the readers.

Extension to primes in intervals

We discuss here how our results extend from the case of primes in the initial interval to primes in [M +1, M +N ] for some non-negative M . During the proof of Theorem 4.1, we used the property that our sequence has at most N 1/4 elements below N 1/4 , and that the remaining ones are prime to any integer below N 1/4 . This is certainly still true when looking at intervals. Theorem 9.1. Let N ≥ 2 • 10 10 . Let B be a δ-well spaced subset of R/Z. For any function f on B, we have

M +1≤p≤M +N b∈B f (b)e(bp) 2 ≤ 330 000(N + δ -1 ) f 2 2 log(2 f 2 1 / f 2 2 ) log N .
When defining c 1 in the proof of Theorem . Modifying the proof of Theorem 1.3 is more delicate as it requires bounding the trigonometric polynomial S from below in (20) to discard the contribution of T (q, β). A simple solution is to assume that all elements of our sequence are further larger than √ N , which is readily granted by assuming that M ≥ √ N . We can assume that S(0) ≥ 1. On following the proof of Theorem 1.3, we readily reach, when |β| ≤ 1/(7N ),

a mod * q S a q + β ≥ µ 2 (q) ϕ(q) -1 S(0) . The factor ( h2 h +1

This again leads to

1-√ N

-h ) 1/ is bounded when h ∈ [1/ log N, ∞). We treat separately the case h ∈ [0, 1/ log N ]. However, Theorem 1.4 and Corollary 1.5 go through with no modifications, and are in this manner closer to (2). Theorem 9.5. Let X be a δ-well spaced subset of R/Z and N ≥ 10 11 . Let (u p ) M +1≤p≤M +N be a sequence of complex numbers. We have

1 /

 1 of B. Green & I. Ruzsa. Theorem 1.3. Assume N ≥ 10 11 and let ≥ 2. We have as soon as p≤N |u p | 2 ≤ p≤N 1.

4 .

 4 The fundamental estimate Theorem 4.1. Let N ≥ 2 • 10 10 . Let B be a δ-well spaced subset of R/Z. For any function f on B, we have 1≤p≤N b∈B f (b)e(bp) 2

  u p e(xp) .We write is as Γ(ξ) = x∈X ξ c(x) p≤N u p e(xp) for some c(x) of modulus 1 and develop it inΓ(ξ) =p≤N u p x∈X ξ c(x)e(xp).

7 .

 7 Optimality and uniform boundedness. Proof of Theorem 1.3 We assume that N ≥ 10 11 and set (18) S(α) = p≤N e(pα).

|u p | 2 / 2 N

 22 log N N -1 log N which leads to (22) with

Theorem 9 . 4 . 1 /

 941 There exists a constant C > 0 such that the following holds. Assume N ≥ 10 11 , M ≥ √ N and let ≥ 2. as soon as M +1≤p≤M +N |u p | 2 ≤ M +1≤p≤M +N 1 = R. So the uniform Hardy-Littlewood majorant property holds for primes in the interval [M + 1, M + N ] provided the number of such primes is N/ log N . Proof of Theorem 9.4. We set (25) S(α) = M +1≤p≤M +N e(pα).

1 0

 1 M +1≤p≤M +N u p e(pα) dα ≤ 10 8 2 h + 1

x∈X M +1≤p≤M +N u p e(xp) 2 ≤Corollary 9 . 6 . 2 ≤

 2962 10 6 N + δ -1 log N M +1≤p≤M +N |u p | 2 log(2|X |). Let N ≥ 10 11 and Q 0 ∈ [2, √ N ].Let (u p ) M +1≤p≤M +N be a sequence of complex numbers. We haveq≤Q 0 a mod * q max |α-a q |≤ 1 qQ 0 M +1≤p≤M +N u p e(αp) 10 7 N log Q 0 log N M +1≤p≤M +N |u p | 2 .

  1.1, we used an upper bound for the number of elements in our set. The version of the Brun-Titchmarsh inequality proved by H. Montgomery & R.C. Vaughan in[START_REF] Montgomery | Hilbert's inequality[END_REF] enables us to use c 1 = 2. After some trivial modifications, we reach the following.

					1+h/2
				|u p | 2
				M +1≤p≤M +N
	1 0 M +1≤p≤M +N u p e(pα)	2+h dα ≤ 10 8 2 h + 1/h N	log N 2N	M +1≤p≤M +N |u p | 2	1+h/2

Theorem 9.2. Let X be a δ-well spaced subset of R/Z. Assume N ≥ 10 11 and let h > 0. We have

x∈X M +1≤p≤M +N u p e(xp) 2+h ≤ 10 8 2 h +1/h N + δ -1 log N .

Corollary 9.3. Assume N ≥ 10 11 and let h > 0. We have


Olivier Ramaré

ACCURATE COMPUTATIONS OF EULER PRODUCTS OVER PRIMES IN ARITHMETIC PROGRESSIONS

Keywords: Euler products. 2020 Mathematics Subject Classification, primary, 11Y60; secondary, 11N13, 05A

This note provides accurate truncated formulae with explicit error terms to compute Euler products over primes in arithmetic progressions of rational fractions. It further provides such a formula for the product of terms of the shape F (1/p, 1/p s ) when F is a two-variable polynomial with coefficients in C and satisfying some restrictive conditions.

Introduction and results

Our primary concern in this paper is to evaluate Euler products of the shape

p≡a[q]
1 -1 p s when s is a complex parameter satisfying s > 1. Such computations have attracted some attention as these values occur when s is a real number as densities in number theory. D. Shanks in [START_REF] Shanks | On the conjecture of Hardy & Littlewood concerning the number of primes of the form n 2 + a[END_REF] (resp. [START_REF] Shanks | On numbers of the form n 4 + 1[END_REF], resp. [START_REF] Shanks | Lal's constant and generalizations[END_REF]) has already computed accurately an Euler product over primes congruent to 1 modulo 8 (resp. to 1 modulo 4, resp. 1 modulo 8). His method has been extended by S. Ettahri, L. Surel and the present author in [START_REF] Ettahri | Fast multi-precision computation of some euler products[END_REF] in an algorithm that converges very fast (double exponential convergence) but this extension covers only some special values for the residue class a, or some special bundle of them; it is further limited to real values of s. We will use logarithms, and since the logarithm of a product is not a priori the sum of the logarithms, we need to clarify things before embarking in this project. First, in this paper the log-function always corresponds to what is called the principal branch of the logarithm. We recognize it because its argument vanishes when we restrict it to the real line and we consider it undefined on the non-positive real numbers. The second point is contained in the next elementary proposition. Proposition 1. Associate to each prime p a complex number a p such that |a p | < p and a p ε p ε for every ε > 0. We consider the Euler product defined when s > 1 by:

D(s) = p 2 1 - a p p s -1 . (1)
In this same domain we have

log D(s) = p 2 k 1 a k p kp ks . (2)
This is simply because, by using the expansion of the principal branch of the logarithm in Taylor series, namely -log(1 -z) = k 1 z k /k valid for any complex z inside the unit circle, we find that C(s) =p 2 log(1 -a p /p s ) verifies exp C(s) = D(s), so that C(s) is indeed a candidate for log D(s). The second remark is that D(s) approaches 1 when s goes to infinity while our choice for log D(s) indeed approaches 0 and no other multiple of 2iπ. These two remarks are enough justification of this proposition.

Remark 1.1. To be axiomatically correct, we should specify that our definition of log D(s) depends a priori on the chosen product representation, and thus on the choice of the coefficients (a p ) p 2 . However, since the development in Dirichlet series is unique, we find that the coefficients in (2) are uniquely defined; this implies in particular that our definition does nor depend on the chosen product representation (as it is unique!).

We assume here that the values of the Dirichlet L-series L(s, χ) may be computed with arbitrary precision when s > 1. Our aim is thus to reduce our computations to these ones. Here is an identity to do so.

Theorem 2. Let a be prime to the modulus q 1 and let G q be the group of Dirichlet characters modulo q. We have

- p≡a[q], p P log(1 -1/p s ) = 1 -1 ϕ(q) d| µ(d) χ∈ Gq χ(a) log L P ( s, χ d )
where

L P (s, χ) = p P (1 -χ(p)/p s ) -1 . (3)
If finding this identity has not been immediate, checking it is only a matter of calculations that we reproduce in Section 2. A partial identity of this sort has already been used by K. Williams in [START_REF] Williams | Mertens' theorem for arithmetic progressions[END_REF] and more recently by A. Languasco and A. Zaccagnini in [START_REF] Languasco | On the constant in the Mertens product for arithmetic progressions. I. Identities[END_REF][START_REF] Languasco | On the constant in the Mertens product for arithmetic progressions[END_REF], and [8, (2-5)] is a related formula. It is worth noticing that, with our conventions, we have the obvious

log L P (s, χ) = log L(s, χ) - p<P log(1 -χ(p)/p s ).
This leads to the next immediate corollary.

Corollary 3. Let a be prime to the modulus q 1 and let G q be the group of Dirichlet characters modulo q. Let further two integer parameters P 2 and L 2 be chosen. We have

p P, p≡a[q] 1 - 1 p s = exp Y P (s; q, a|L) + O * 1 P L s
where

Y P (s; q, a|L) = L 1 d| µ(d) χ∈ Gq χ(a) ϕ(q) log L P ( s, χ d ) (4)
and where f = O * (g) means |f | g.

Extension to one variable rational fractions

Once we have such an approximation, we can reuse the machinery of [START_REF] Ettahri | Fast multi-precision computation of some euler products[END_REF] to reach Euler products of the shape p P, p≡a

(1 + R(p s ))

where R is a rational fraction.

Theorem 4. Let F and G be two polynomials of C[t]. We assume that G(0) = 1 and that F (0) = F (0) = 0. Let β 2 be larger than the inverse of the roots of G and of G -F . Let P 2β be an integer parameter. Then, for any integer parameter L 2, we have

p P, p≡a[q] 1 - F (1/p) G(1/p) = exp 2 j J b G-F (j) -b G (j) Y P (j; q, a|L) + I
where the integers b G-F (j) and b G (j) are defined in Lemma 6,

|I| 8 max(deg(G -F ), deg G)β 2 (β/P ) 2L
and Y (s; q, a|L) is defined by (4).

We obtained in [START_REF] Ettahri | Fast multi-precision computation of some euler products[END_REF] an approximation that is much better but only valid for rational fractions with real coefficients and some residue classes.

One can write a similar theorem for the Euler product p P, p∈A

1 - F (1/p s ) G(1/p s ) .

Extension to two variables rational fractions

The general form of Euler products that one has to treat in practice is of the shape

p P, p≡a[q] (1 + R(p, p s ))
where R is a rational fraction of two variables. When s takes a specific rational value, typically 2, 3/2 or 4/3, this question reduces to the above one though each of the values of s requires a new rational fraction; this covers most of the cases when we have to compute a single special constant. In the general case however, for instance when s = 2+i, such a trick fails. The theoretical understanding of this situation is also limited even for q = 1. For instance, if the case of a rational fraction of one variable is covered by the theorem of T. Esterman in [START_REF] Estermann | On Certain Functions Represented by Dirichlet Series[END_REF] and extended by G. Dalhquist in [START_REF] Dahlquist | On the analytic continuation of Eulerian products[END_REF], no such result is known in the general situation. This question has been addressed in the context of enumerative algebra, for instance by M. du Sautoy and F. Grünewald in [START_REF] Sautoy | Zeta functions of groups: zeros and friendly ghosts[END_REF]. The lecture notes [START_REF] Sautoy | Zeta functions of groups and rings[END_REF] by M. du Sautoy and L. Woodward contain material in this direction. There are several continuations of Esterman's work; for instance, one may consider Euler products of the shape R(p s1 , p s2 ) (with the hope of being able to specify s 1 ), see for instance [START_REF] Delabarre | Extension of Estermann's theorem to Euler products associated to a multivariate polynomial[END_REF] by L. Delabarre, but these results do not apply to our case.

We are able to handle some rational fractions by reducing them to the case treated in the next theorem.

Theorem 5. Let s be a complex number with s = σ > 1. Let (a ) k be a sequence of complex numbers and (u ) k and (v ) k be two sequences of real numbers. We assume that u σ + v > 0 and we define A = max(1, max(|a |)). Let q be a modulus, a be an invertible residue class modulo q and P 2kA and L k be two integer parameters. We have

p P, p≡a[q] 1 - 1 k a p u s+v = exp -(Z + I)
where

Z = m1,...,m k 0, 1 m1+...+m k L M (m 1 , . . . , m k ) f F κ f ( k a m ) f Y P k m (u s + v ); q, a|L (5)
where M (m 1 , m 2 , . . . , m k ) is defined at (18), κ f is defined at (23), Y (s; q, a|L) is defined by (4) and finally where

|I| 2 k • A L k!P L (L + k) k + 1 + log L + 3kA L . (6)
Hence this theorem provides us with an exponentially decreasing error term. More complicated terms may be handled through this theorem by writing

1 + F (p, p s ) G(p, p s ) = (F + G)(p, p s ) p As+B p As+B G(p, p s ) = 1 + (F + G)(p, p s ) -p As+B p As+B 1 + G(p, p s ) -p As+B p As+B -1
.

This would function when G has a clearly dominant monomial. It typically works for G(p, p s ) = p 2s (p 2 + 1) but fails for G(p, p s ) = p 2s (p + 1). Our most important additional tool, namely Lemma 11, may be used to obtain results on analytic continuation, but since we use logarithms elsewhere, the general effect is unclear.

We however provide the next example:

D(s) = p 2 1 + 1 p s - 1 p 2s-1 . (7)
Lemma 11 gives us the decomposition

D(s) = m1,m2 0, m1+m2 1
p 2 1 - (-1) m1 p (m1+2m2)s-m2 M (m1,m2)
.

We check that M (1, 0) = M (0, 1) = 1 and that M (m, 0) = M (0, m) = 0 when m 2, whence

D(s) = ζ(2s -1) ζ(2s) ζ(s) m1,m2 1 p 2 1 - (-1) m1 p (m1+2m2)s-m2 M (m1,m2) . ( 8
)
This writing offers an analytic continuation of D(s) to the domain defined by s > 1/2. This analysis can be extended to

p 2 1 - C 1 p s - C 2 p 2s-1
when C 1 and C 2 are integers. In general, Lemma 11 transfers to problem to the analytic continuation of p (1 -c/p s ) for some c but even the case c = √ 2 is difficult.

Proof of Theorem 2 and its corollary

Proof of Theorem 2. We have to simplify the expression

S = 1 1 ϕ(q) d| µ(d) χ∈ Gq χ(a) p P k 1 χ(p) dk kp k s . (9)
We readily check that, when h 1 and p are fixed, we have and the theorem follows directly.

Proof of Corollary 3. A moment thought discloses that

| log L P (s, χ)| log ζ P (σ)
where σ = s. We have furthermore

log ζ P (σ) n P 1 n σ ∞ P dt t σ = 1 (σ -1)P σ-1 .
by our assumptions. We next check that

>L 1 ϕ(q) d| µ(d) χ∈ Gq χ(a) log L P ( s, χ d ) >L 2 ω( ) P ( σ -1)P σ .
Here ω( ) denotes the number of prime factors of (without multiplicity). We use the simplistic bounds 2 ω( ) and σ -1 2. This yields the upper bound P 2P Lσ (P σ -1) which is no more than 1/P Lσ . We finally recall that e x -1 8 7 x when x ∈ [0, 1/4] as the function (e x -1)/x is non-decreasing (its expansion in power series has non-negative coefficients).

Proof of Theorem 4

We first need to extend [START_REF] Ettahri | Fast multi-precision computation of some euler products[END_REF]Lemma 16] to cover the case of polynomials with complex coefficients. The ancestor of this Lemma is [10, Lemma 1].

Lemma 6. Let H(t) = 1 + a 1 t + . . . + a δ t δ ∈ C[t] be a polynomial of degree δ. Let α 1 , . . . , α δ be the inverses of its roots. Put s H (k) = α k 1 + . . . + α k δ . The s H (k) satisfy the Newton-Girard recursion s F (k) + a 1 s F (k -1) + . . . + a k-1 s F (1) + ka k = 0, (10)
where we have defined a δ+1 = a δ+2 = . . . = 0. We define

b H (k) = 1 k d|k µ(k/d)s H (d). (11)
Lemma 7. Let F and G be two polynomials of C[t]. We assume that G(0) = 1 and that F (0) = 0. Let β 1 be larger than the inverse of the roots of G and of G -F . When z is a complex number such that |z| < β and |1 -(F/G)(z)| < 1.

We have

log 1 - F (z) G(z) = j 1 b G-F (j) -b G (j) log(1 -z j ). (12)
Proof. We adapt the proof of [10, Lemma 1]. We write (G -F )(t) = i (1 -α i t).

We have

(G -F ) (t) (G -F )(t) = i α i t 1 -α i t = k 1 s G-F (k)t k-1 .
This series is absolutely convergent in any disc |t| b < 1/β where β = max j (1/|α j |).

We may also decompose (G -F ) (t)/(G -F )(t) in Lambert series as

(G -F ) (t) (G -F )(t) = j 1 b G-F (j) jt j-1 1 -t j
as some series shuffling in any disc of radius b < min(1, 1/β) shows. The comparison of the coefficients justifies the formula [START_REF] Shanks | On the conjecture of Hardy & Littlewood concerning the number of primes of the form n 2 + a[END_REF]. We may do the same for G instead of G -F (or use the case F = 0). We find that

G -F G -F - G G = -(F G -F G ) G(G -F ) = -(F G -F G ) G 2 k 0 F G k
and by formal integration, this gives us the identity

- k 1 (F/G)(t) k k = - j 1 b G-F (j) -b G (j) log(1 -t j ).
This readily extends into an equality between analytic function in the domain where |(F/G)(z) -1| < 1 and |z| < β. The lemma follows readily.

Here is now [6, Lemma 17], though for polynomials with complex coefficients.

Lemma 8. We use the hypotheses and notation of Lemma 6. Let β 2 be larger than the inverse of the modulus of all the roots of H(t). We have

|b H (k)| 2 deg H • β k /k.
And we finally recall [START_REF] Ettahri | Fast multi-precision computation of some euler products[END_REF]Lemma 18] that yields easy upper estimates for the inverse of the modulus of all the roots of F (t) in terms of its coefficients. Lemma 9. Let H(X) = 1 + a 1 X + . . . + a δ X δ be a polynomial of degree δ. Let ρ be one of its roots. Then either |ρ| 1 or

1/|ρ| |a 1 | + |a 2 | + . . . + |a δ |.
Proof of Theorem 4. The proof requires several steps. We start from Lemma 7, i.e. from the identity

log 1 - F (z) G(z) = j 2 b G-F (j) -b G (j) log(1 -z j ), (13)
in the domain |z| < β and |1 -(F/G)(z)| < 1. The fact that the term with j = 1 vanishes comes from our assumption that F (0) = F (0) = 0. To control the rate of convergence, we notice that, by Lemma 8, we know that

|b G-F (j) -b G (j)| 4 max(deg(G -F ), deg G)β j /j.
Therefore, for any bound J, we have

j J+1 |t j ||b G-F (j) -b G (j)| 4 max(deg(G -F ), deg G) |tβ| J+1 (1 -|tβ|)(J + 1) , (14)
if |t| < 1/β. Furthermore, we deduce that | log(1-z)/z| log(1-1/2)/(1/2) 3/2 when |z| 1/2 by looking at the Taylor expansion. Thus we have

log 1 - F (z) G(z) = 2 j J b G-F (j) -b G (j) log(1 -z j ) + I 1 (15)
where

|I 1 | 6 max(deg(G -F ), deg G)|zβ| J+1 /(1 -|zβ|)
. Now that we have the expansion (15) at our disposal for each prime p, we may combine them. We readily get

p P, p≡a[q] log 1 - F (1/p) G(1/p) = 2 j J b G-F (j) -b G (j) p P, p≡a[q] log(1 -1/p j ) + I 2 ,
where I 2 satisfies

|I 2 | 6 max(deg(G -F ), deg G) p P β J+1 (1 -β/P )(J + 1) 1 p J+1 6 max(deg(G -F ), deg G)β J+1 (1 -β/P )(J + 1) 1 P J+1 + ∞ P dt t J+1 6 max(deg(G -F ), deg G)(β/P ) J β (1 -β/P )(J + 1) 1 P + 1 J ,
since P 2 and J 3. We now approximate each sum over p by using Corollary 3 and obtain

p P, p≡a[q] log 1 - F (1/p) G(1/p) = 2 j J b G-F (j) -b G (j) Y P (j; q, a|L) + I 3
where I 3 satisfies

|I 3 | 2 j J |b G-F (j) -b G (j)| 1 P Lj + |I 2 | 2 j J 4 max(deg F, deg G) β j j 1 P Lj + |I 2 |.
Therefore (and since r 2)

|I 3 | 2 max(deg F, deg G) β 2 (β/P ) 2L 1 -β/P + 3(β/P ) J β (1 -β/P )(J + 1) 1 P + 1 J , (16)
and the choice J = 2L ends the proof.

Proof of Theorem 5

Lemma 10. We have

dN dm 1 ,••• ,dm k N m 1 ,••• ,m k d . Proof. The coefficient dN dm 1 ,••• ,dm k
is the number of partitions of a set of dN elements in parts of dm 1 , • • • , dm k elements. The product partitions are partitions.

In [START_REF] Witt | Treue Darstellung Liescher Ringe[END_REF] Witt proved a generalization of the Necklace Identity which we present in the next lemma.

Lemma 11. For k 1, we have

1 - k i=1 z i = m1,...,m k 0, m1+...+m k 1 (1 -z m1 1 • • • z m k k ) M (m1,...,m k ) , (17)
where the integer M (m 1 , . . . , m k ) is defined by

M (m 1 , . . . , m k ) = 1 N d| gcd(m1,m2,...,m k ) µ(d) (N/d)! (m 1 /d)! • • • (m k /d)! (18)
with

N = m 1 + . . . + m k . We have M (m 1 , . . . , m k ) k N /N .
Proof. Only the bound needs to be proved as the identity may be found in [START_REF] Witt | Treue Darstellung Liescher Ringe[END_REF]. Each occuring multinomial is not more than N 0 or not for some parameter N 0 k that we will choose later. We readily find that, when p 2A, log m1,...,m k 0,

m1+...+m k >N0 1 - c(m 1 , m 2 , . . . , m k ) p k m (u s+v ) M (m1,...,m k ) 3 2 m1,...,m k 0, m1+...+m k >N0 M (m 1 , . . . , m k ) A N p N 3 2 N >N0 N + k k (kA) N N p N
as the number of solutions to m 1 + . . . + m k = N is the N -th coefficient of the power series 1/(1 -z) k which happens to be equal to (1/k!) d dz k 1/(1 -z). We next check that, with N = N 0 + n + 1, we have (n + 1 + N 0 + k) (N 0 + n + 1) 2 since N 0 k, and thus

N +k k N n+k k = (n + 1 + N 0 + k)(n + N 0 + k) • • • (n + N 0 + 2) (n + k)(n + k -1) • • • (n + 1) • (N 0 + n + 1) N 0 + k k .
Hence, when p 2kA, we have

N >N0 N + k k (kA) N N p N = (kA) N0+1 p N0+1 N 0 + k k n 0 n + k k (kA) n p n N 0 + k k (kA) N0+1 p N0+1 1 (1 -1/2) k .
On summing over p, this yields

Π = I 1 m1,...,m k 0, 1 m1+...+m k N0 p P, p≡a[q] 1 - c(m 1 , m 2 , . . . , m k ) p k m (u s+v ) M (m1,...,m k ) , (20)
where

| log I 1 | 2 k 3 2 N 0 + k k (kA) N0+1 P N0 1 P + 1 N 0 . (21)
We next note the following identity

k 1 d k kp kw = f 1 κ f (d) f g 1 1 gp f gw (22)
where

κ f (d) = c when f = 1, c f -c f -1 when f > 1. (23)
We truncate identity (22) at f F where F is an integer, getting

k 1 d k kp kw = f F κ f (d) f g 1 1 gp f gw + O * - f >F max(1, |d|) f f log 1 -p -f w .
We next use -log(1 -x) 3x/2 when 0 x 1/2. We assume that p w 1/2 and p w 2 max(1, |d|) to get

- f >F max(1, |d|) f f log 1 -p -f w 3 2 f >F max(1, |d|) f f p f w
3 max(1, |d|) F +1 (F + 1)p (F +1) w .

We have reached (F + 1)P (F +1)N 1 + P F N .

We now take F = L. The error term is bounded above by (since P 2kA)

kA L P L 2 k k! (1 + log L) + 3 • 2 k A k!(L + 1)P 1 + P L .
We select N 0 = L and we gather our estimates to end the proof.

  )χ(p) = ϕ(q)1 1 p≡a[q]

N

  m1,••• ,m k by Lemma 10. The multinomial Theorem concludes.Proof of Theorem 5. Let Π be the product to be computed. By employing Lemma 11, we find that 1 -1 k a p u s+v = m1,...,m k 0, m1+...+m k 1 1 -c(m 1 , m 2 , . . . , m k ) p k m (u s+v ) M (m1,...,m k ) , with c(m 1 , . . . , m k ) given by c(m 1 , m 2 , . . . , m k ) = k a m .(19)Each coefficient c(m 1 , . . . , m k ) is not more, in absolute value, than A N , where m 1 + . . . + m k = N . Note that, for each , we have (u s + v ) > 1, so that k m (u s + v ) m 1 + . . . + m k = N . It thus seems like a good idea to truncate the infinite product in (20) whetherm 1 + • • • + m k = N

  1 , m 2 , . . . , m k )p k m (u s+v ) = expf F κ f (c(m 1 , m 2 , . . . , m k )) f p P, p≡a[q] log 1 -p -f k m (u s+v ) + O * 3 max(1, |c(m 1 , m 2 , . . . , m k )|) F +1 (F + 1)P (F +1) k m (u σ+v ) 1 , m 2 , . . . , m k ) p k m (u s+v ) = expf F κ f (c(m 1 , m 2 , . . . , m k )) f p P, p≡a[q] log 1 -p -f k m (u s+v ) + 3A N (F +1) (F + 1)P (F +1)N 1 + P F N .We approximate the sum of the logs by Corollary 3 and getp P, p≡a[q] 1 -c(m 1 , m 2 , . . . , m k ) p k m (u s+v ) = expf F κ f (c(m 1 , m 2 , . . . , m k )) f Y P k m (u s + v ); q, a|L + O * A N F (1 + log F ) P LN + 3A N (F +1) (F + 1)P (F +1)N 1 + P F N .We then raise that to the power M (m 1 , m 2 , . . . , m k ) and sum over the m i 's, getting, on recalling (5),Π/I 1 = exp -Z + O * m1,...,m k 0, 1 m1+...+m k N0 M (m 1 , . . . , m k )A N F (1 + log F ) P LN + m1,...,m k 0, 1 m1+...+m k N0 3M (m 1 , . . . , m k )A N (F +1)