Ramachandran Balasubramanian

Olivier Ramar É

Priyamvad Srivastav
email: priyamvads@gmail.com

EXPLICIT BOUNDS FOR PRODUCTS OF PRIMES IN AP

Keywords: 2000 Mathematics Subject Classification. Primary: 11N13, 11A41, Secondary: 11N37, 11B13 Primes in arithmetic progressions, Least prime quadratic residue, Linnik's Theorem

For all q ≥ 2 and for all invertible residue classes a modulo q, there exists a natural number that is congruent to a modulo q and that is the product of exactly three primes, all of which are below (10 15 q) 5/2 .

Introduction and results

In this paper we investigate the representation of reduced residue classes modulo q by a product of exactly three small primes. We improve on [START_REF] Ramaré | Products of primes in arithmetic progressions[END_REF][START_REF] Ramaré | Products of primes in arithmetic progressions: a footnote in parity breaking[END_REF] by introducing an explicit vertical Brun-Titchmarsh inequality in Theorem 1.4. Its proof takes most of our efforts and Theorem 6.1 has no predecessor. Please note that this result is new even if one omits the explicit aspect.

Theorem 1.1. For any q ≥ 2 and any invertible residue class a modulo q, there exists a natural number that is congruent to a modulo q and that is the product of exactly three primes, all of which are below (10 15 q) 5/2 . We thus go beyond the bound O(q 3 ) that was a barrier in [START_REF] Ramaré | Products of primes in arithmetic progressions[END_REF]. Varying the constant 10 15 is the subject of Theorem 13.2 where it is for instance proved that, for q ≥ 10 88 , the primes may be assumed to be below (30q) 5/2 . We present in Section 12 some computations for small values of the parameter q. Here is one result that is established there. Theorem 1.2. For every q ∈ [5208, 2•10 7 ], every invertible class modulo q contains a product of three primes, each of which being of size at most q(log q) 2 .

To prove Theorem 1.1, we first prove an explicit version of a vertical Brun-Titchmarsh Theorem, i.e. an almost-everywhere, in a-aspect, individual upper bound in the Brun-Titchmarsh style. The result in itself is essentially due to Hooley in [8, Theorem 5], but since our phrasing is more precise, we prefer to state it explicitly.

Theorem 1.3 (Hooley [START_REF] Hooley | On the Brun-Titchmarsh theorem[END_REF]). Let q ≥ 1 be an integer. Let X ≥ q 3/2 (log q) 12 be some real number. For every invertible class a modulo q, we have p≤X, p≡a [q] 1 ≤

2(1 + ϵ(a)) • X φ(q) log(X/ √ q) where a mod * q ϵ(a) 2 ≪ φ(q)/ log q where "p ≡ a[q]" means that p is congruent to a modulo q while "a mod * q" means that a ranges through a complete set of reduced residue classes modulo q.

Our proof differs from the one of Hooley and is closer to the work [START_REF] Motohashi | On some improvements of the Brun-Titchmarsh theorem[END_REF] by Motohashi. However, a noticeable distinction is that we avoid using the fourth power moment upper bound for L-functions. For efficiency on the explicit side, we prove a smoothed version of Theorem 1.3. From now on, the symbols η * and κ shall be kept for the functions defined by (1)

η * (t) =          3t 2 , 0 ≤ t ≤ 1/3, -6t 2 + 6t -1, 1/3 < t ≤ 2/3, 3(1 -t) 2 , 2/3 < t ≤ 1, 0, otherwise ,
κ(t) =          -3t 2 , 0 ≤ t ≤ 1/3, 6t 2 -1, 1/3 < t ≤ 2/3, 3(1 -t 2 ), 2/3 < t ≤ 1, 0, otherwise.
This choice is explained in Section 2. We have ∥η * ∥ 1 = 2/9. A large part of this paper is dedicated to the proof of the next theorem.

Theorem 1.4. Let q ≥ 2 • 10 7 be an integer. Let X ≥ (10 13 q) 5/2 be some real number. For every invertible class a modulo q, we have

p≡a[q]
η * (p/X) ≤ 2(1.004 + ϵ(a)) • 2X/9 φ(q) log X 10 9 √ q where a mod * q ϵ(a) 2 ≤ φ(q)/4250.

The proof uses directly the Parseval identity for Mellin transforms rather than the more usual result by Gallagher, namely [7, Theorem 1]. A major input is Theorem 6.1 that gives a sharp upper bound for S(z) = n ( [d1,d2]=n |λ d1 λ d1 |) 2 where the λ d 's are closely related to some Selberg parameters. We modify these though and this modification is instrumental in our proof. Let us mention that the trivial bound for S(z) is of size z 2 (log z) 8 while the bound we prove is of order z 2 /(log z) 3 . Computations described in Section 7 support the fact that S(z)(log z) 3 /z 2 is indeed asymptotic to some positive constant. Theorem 13.1 presents variants of Theorem 1.4.

We recall the definition of the Mellin transform:

(2) η(s) = ∞ 0 η(x)x s-1 dx and further introduce a notation: f = O * (g) is equivalent to |f | ≤ g.

Smoothings

Let us quote from Rényi's book [START_REF] Rényi | Probability theory[END_REF] the formula:

1

( * m) [-1,1] (t) =        ⌊(m+|t|)/2⌋ j=0 (-1) j (m -1)! m j (m + |t| -2j) m-1 when 0 ≤ |t| ≤ m, 0 when m < |t|.
Guessing this expression is not obvious, but checking it by recursion is only a matter of routine. The Fourier transform of 1 [-1,1] is sin(2πu)/(πu), so the transform of 1 [START_REF] Balasubramanian | Products of three primes in large arithmetic progressions[END_REF] is sin(2πu) m /(πu) m . In the previous paper [START_REF] Ramaré | Products of primes in arithmetic progressions[END_REF], we used the above with m = 2, but we need a smoother function here. By specifying m = 3, we get 1

( * m) [-1,
( * 3) [-1,1] (t) =      3 -t 2 when 0 ≤ |t| < 1, (3 -|t|) 2 /2 when 1 ≤ |t| < 3, 0 when 3 ≤ |t|.
As indicated in the introduction, the symbol η * shall be kept for the function defined by

(3) η * (t) = 1 ( * 3) [-1,1] (6t -3)/6.
In this section, we use the Bernoulli polynomials (B m ) m≥0 that are defined by

te xt e t -1 = m≥0 B m (x) t n n! .
It is straightforward to compute the first of these:

B 0 (x) = 1, B 1 (x) = x -1 2 , B 2 (x) = x 2 -x + 1 6 , B 3 (x) = x 3 -3 2 x 2 + 1 2
x. The Bernoulli functions are then defined by b m (x) = B m ({x}) where {x} is the fractional part of x. These functions are periodic modulo 1, and their Fourier series expansion is well-known.

Lemma 2.1. We have, when m ≥ 1,

n≥1 1 ( * m) 2n X -1 m = 2 m-1 X m - (2m) m-1 X m-1 m! 0≤k≤m (-1) m-k m k b m 2kX/m . Proof. Indeed the Fourier transform of g(u) = 1 ( * m) ((2(u/X) -1)m) is given by ĝ(v) = ∞ -∞ 1 ( * m) ((2(u/X) -1)m)e(uv)du = X 2m ∞ -∞ 1 ( * m) (w)e Xvw 2m + Xv 2 dw = X 2m e(Xv/2) 2m sin πXv m πXv m .
By the Poisson summation formula, we get

S = n≥1 1 ( * m) 2n X -1 m = X 2m (2m) m X m ℓ∈Z e(Xℓ/2) sin πXℓ m πℓ m .
Next notice that, with x = Xℓ/(2m),

(2i) m e(mx)(sin 2πx) m = e(mx) 0≤k≤m (-1) m-k m k e((2k -m)x) = 0≤k≤m (-1) m-k m k e(2kx). Hence with y = X/m S = 2 m-1 X m + X 2m (2m) m X m 1 (2iπ) m ℓ∈Z, ℓ̸ =0 0≤k≤m (-1) m-k m k e(2kyℓ) ℓ m = 2 m-1 X m - X 2m (2m) m X m m! 0≤k≤m (-1) m-k m k b m 2kX/m .
This completes the proof. □

This lemma may be compared with [START_REF] Treviño | The least inert prime in a real quadratic field[END_REF]Lemma 3.1] which corresponds to the case m = 2. We now concentrate on the case m = 3.

Lemma 2.2. With ρ 3 (y) = 0≤k≤3 (-1) k 3 k b 3 (ky), we have ρ 3 (y) = -6{y} 3 when {y} ≤ 1/3, 3(1 -2{y})({y} 2 -4{y} + 1) when 1/3 < {y} ≤ 1/2,
and ρ 3 (1 -y) = -ρ 3 (y).
Here {y} is the fractional part of y. In particular this quantity lies in [3(11

-5 √ 5)/2, 3(5 √ 5 -11)/20]. Proof. The property of the Bernoulli polynomials B m (1 -X) = (-1) m B m (X) implies that b m (1 -y) = (-1) m b m (y)
, so we may restrict our attention to the case 0 ≤ y ≤ 1/2. When y ∈ [0, 1/3), we find that

2ρ 3 (y) = -3(2y 3 -3y 2 + y) + 3(16y 3 -12y 2 + 2y) -(54y 3 -27y 2 + 3y) = -12y 3 .
We continue with the case y ∈ [1/3, 1/2) where {2y} = 2y but {3y} = 3y -1. Therefore 2ρ 3 (y) = -3(2y 3 -3y 2 + y) + 3(16y 3 -12y 2 + 2y)

-(2(3y -1) 3 -3(3y -1) 2 + 3y -1) = 6(1 -2y)(y 2 -4y + 1).
The derivative of ρ 3 (y) with respect to y in this interval is 18(-y 2 + 3y -1). The minimum is at y 0 = (3 -√ 5)/2 with value 3(11 -5 √ 5)/2, and this concludes the proof of this lemma. □

On collecting (3), Lemma 2.1 and with Lemma 2.2, we obtain the next lemma.

Lemma 2.3. We have 2X 9 - θ X 2 ≤ m≥1 η * (m/X) ≤ 2X 9 + θ X 2
where θ = 3(5 √ 5 -11)/2 ≤ 0.28.

Lemma 2.4. When X ≥ 3 • 10 7 and X ≥ q, we have

(p,q)=1 η * (p/X) ≥ (1 -0.003) 2X/9 log X .
Proof. Let us call S the sum on the left side. We first find that, as η * has its support within [0, 1], we have

(p,q)=1 η * (p/X) log X = (p,q)=1 η * (p/X) log p + log X p ≥ (p,q)=1 η * (p/X) log p.
We next notice that

(p,q)=1 η * (p/X) log p ≥ p η * (p/X) log p -∥η * ∥ ∞ p|q log p
and this last summand is at most (log X)/2. Hence, with the notation ϑ(t) = p≤t log p, we find that

(S + 1 2 ) log X ≥ p≥1 log p - 1 p/X η * ′ (t)dt ≥ - 1 0 ϑ(tX)η * ′ (t)dt = - X 0 ϑ(u)η * ′ (u/X)du/X.
We note that -η * ′ (t) is non-positive when t ≤ 1/2 and non-negative afterwards, hence we need an upper bound for ϑ(u) when u ≤ X/2 and a lower bound when u ≥ X/2. Concerning the upper bound, we recall [20, equation (5.1)]:

(4) ϑ(u) = p≤u log p ≤ 1.001102u (u > 0)
and concerning the lower bound, we use [20, equation (5.2)]:

(5)

ϑ(u) ≥ (1 -0.0013156)u (u ≥ 1 319 007).
We mention here that a better lower bound may be found in [START_REF] Broadbent | Sharper bounds for the Chebyshev function θ(x)[END_REF]. We set ϵ * = 0.0013156 and on assuming X/2 ≥ 1 319 007, we get

(S + 1 2 ) log X ≥ - X 0 uη * ′ (u/X) du X -ϵ * X 0 |uη * ′ (u/X)| du X ≥ -X 1 0 tη * ′ (t)dt -ϵ * X 1 0 |η * ′ (t)|dt = X 1 0 η * (t)dt -ϵ * η * (1/2)X = 2 9 - ϵ * 2 X.
This gives us a lower estimates for S. □ 2.1. Mellin transforms.

Lemma 2.5. We have κ(s) = (s + 1) η * (s).

Proof. Indeed, by summation by parts, we find that η * (s) = The lemma follows readily. □

Some auxiliary lemmas

Lemma 3.1. Let f be an absolutely continuous function on [0, 1] such that f (0) = 0. For y, c ≥ 0, we have

n≤cy f (n/y) = y c 0 f (t)dt + ({cy} -1 2 )f (c) + c 0 ({ty} -1 2 )f ′ (t)dt
where {u} denotes the integer part of u.

Proof. Since f is absolutely continuous, we have

f (x) = f (c) - c x f ′ (t)dt.
The next steps are routine:

n≤cy f (n/y) = - c 0 n≤ty f ′ (t)dt+[y]f (c) = - c 0 ty -1 2 -{ty}+ 1 2 f ′ (t)dt+[y]f (c).
The lemma follows readily. □ Lemma 3.2. For v > 0, we have

n≤1/v |κ(nv)| ≤ 2 √ 6 9v + 4.
Proof. We use Lemma 3.1 with c = 1 and f (t) = |κ(t)|. We readily check that

1 0 |κ(t)|dt = 2 √ 6/9. Furthermore |κ| ′ (t) =                6t, 0 ≤ t ≤ 1/3, -12t, 1/3 < t ≤ 1/ √ 6, 12t, 1/ √ 6 < t ≤ 2/3, -6t, 2/3 ≤ t ≤ 1, 0, otherwise.
and, after a short calculation, this readily implies that

1 0 ||κ| ′ (t)|dt = 8. □ 3.1. Constant recognition.
Here is an abstraction of an idea contained in [5, Lemma 2.9].

Lemma 3.3. Let D(s) = n≥1 u n /n s be a Dirichlet series that is absolutely convergent for ℜs > 1, has a simple pole of residue ρ at s = 1 and is analytically continuable to ℜs > c for some c ∈ (0, 1). We assume that n≤X u n = ρX + O(X c ).

Then for ℜs = σ > c, we have

n≤X u n n s = ρ (1 -s)X s-1 + D(s) + O(X c-σ ).
Proof. We first notice that D(s)

equals n≤X u n n s + s ∞ X X<n≤t u n -ρt s t s+1 dt + sρ (s -1)X s-1 .
We infer from this expression that

D(s) = n≤X u n n s - n≤X u n X s + s ∞ X n≤t u n -ρt dt t s+1 + sρ (s -1)X s-1 = n≤X u n n s + ρ (s -1)X s-1 - n≤X u n -ρX X s + s ∞ X n≤t u n -ρt dt t s+1 .
This is valid at first for ℜs > 1, but by analytic continuation and since n≤t u nρt ≪ t c , also when ℜs > c. In particular, when c < ℜs < 1, we have

n≤X u n n s = ρ (1 -s)X s-1 + D(s) + O(X c-σ ) as required. □ 3.2.
On squarefree numbers. The next lemma is proved, for the first part in [START_REF] Moser | The error term for the squarefree integers[END_REF] and for the second one in [START_REF] Cohen | Explicit estimates for summatory functions linked to the Möbius µ-function[END_REF].

Lemma 3.4. When x ≥ 1, we have n≤x µ 2 (n) = 6 π 2 x + O * ( √ x) while, when x ≥ 438653, we have n≤x µ 2 (n) = 6 π 2 x + O * (0.02767 √ x).
For a better error term in the range x ∈ [0, 10 18 ], we refer the reader to [START_REF] Mossinghoff | The distribution of k-free numbers[END_REF]

µ 2 (n) n 2/3 ≤ 6 π 2 • 3y 1/3 .
Proof. We readily check that

S = n≤y µ 2 (n) n 2/3 = y 1 n≤t µ 2 (n) 2dt/3 t 5/3 + n≤y µ 2 (n) y 2/3 = 6 π 2 3y 1/3 -2 + ∞ 1 r(t) 2dt/3 t 5/3 - ∞ y r(t) 2dt/3 t 5/3 + r(y) y 2/3
where n≤t µ 2 (n) = When a ≥ 8, the initial computations that we ran were not enough to make the 'error term' negligible. This explains why our values increase from this point onwards.

There is little doubt that heavier computations would cure this defect.

Proof. We numerically checked that, when 1

≤ x ≤ 10 8 , 1 a! x n≤x µ 2 (n) log x n a ≤               
0.6715 when a = 1, 0.6365 when a = 2, 0.6227 when a = 3, 0.6161 when a = 4, 0.6127 when a = 5,

              
0.6108 when a = 6, 0.6097 when a = 7, 0.6091 when a = 8, 0.6087 when a = 9, 0.6077 when a = 10.

Let us comment somewhat on this script. We enumerate the squarefree integers together with their prime factorisation through the forsquarefree-loop of Pari/GP. At each of them, we compute the vector ( ℓ≤n µ 2 (ℓ)(log ℓ) a ) a≤10 . We then study the extrema of the functions ℓ≤n µ 2 (ℓ)(log(x/ℓ)) a /x between two squarefree integers, say n and its successor n + , a problem which is readily seen as computing the zeros of a polynomial of degree a. As a good amount of time may be spent computing logarithms, we store them and compute them when needed: after an initial precomputation till n = 10 5 , we compute and store the log p when new n = p and otherwise get log n through p|n log p.

For larger values of x, we employ summation by parts in the form

n≤x µ 2 (n) log x n a = x 1 n≤x/t µ 2 (n) a log a-1 t t dt ≤ 6x π 2 x 1 a log a-1 (x/t) t 2 dt + √ x x 1 a log a-1 (x/t) t 3/2 dt ≤ 6x π 2 • a! 1 + 2 a π 2 6 √ x .
This is enough when a ≤ 5. Otherwise, we have to resort to a somewhat more sophisticated bound (with x 0 = 450000 and ε = 0.02767):

n≤x µ 2 (n) log x n a = x/x0 1 n≤x/t µ 2 (n) a log a-1 t t dt + x x/x0 n≤x/t µ 2 (n) a log a-1 t t dt ≤ 6x • a! π 2 + ε √ x x 1 a log a-1 t t 3/2 dt + (1 -ε) √ x x x/x0 a log a-1 t t 3/2 dt ≤ 6x • a! π 2 + ε √ x2 a a! + (1 -ε) x0 1 log x u a-1 adu u 3/2 ≤ 6x • a! π 2 + √ xa! ε • 2 a + 1 -ε 2 (log x) a-1 (a -1)! √ x .
These lines suffice to establish that the maximum of our function is attained below 10 8 when a ∈ {6, 7} and to prove the announced values otherwise. □

On quadratic subgroups.

Here is a consequence of Axer's method and the Pólya-Vinogradov inequality that we take from [START_REF] Ramaré | Products of primes in arithmetic progressions[END_REF]Lemma 3.3].

Lemma 3.8. Let q ≥ 3 and χ be a nontrivial quadratic character modulo q. Then, there is a prime p ≤ 25 q 2 , such that χ(p) = 1. This is far from being optimal even from an explicit viewpoint but this result is already more than enough for us as the bound q 5/2 would do. We refer to [START_REF] Pollack | The smallest prime that splits completely in an abelian number field[END_REF] by P. Pollack for asymptotic bounds on this question.

On the λ d 's

We modify slightly the Selberg coefficients λ d to allow a better control of the error term that arises. We define [START_REF] Gallagher | A large sieve density estimate near σ = 1[END_REF]

λ d =    µ(d) log z d log z , d ≤ z, 0, otherwise.
Please note that, as in [START_REF] Ramaré | Products of primes in arithmetic progressions[END_REF], this choice is independent of q. Part of the quality of our explicit evaluations comes from this feature. We define

(8) S = S(z) = n≤z 2   [d1,d2]=n |λ d1 ||λ d2 |   2 then (9) S = S(z) = n≤z 2   [d1,d2]=n |λ d1 ||λ d2 |   2 /n
and finally

(10) 1/G(z) = d1,d2≤z λ d1 λ d2 [d 1 , d 2 ] .
In the setting of the Selberg sieve, this quantity is readily evaluated through using the general theory of averages of non-negative multiplicative functions. No such simplification occurs with our choice but the theory of explicit estimates for the Möbius function is nowadays sufficiently developed to allow our choice of λ d .

Lemma 4.1. Let z > 1 be a real number. We have 1/G(z) ≤ 1.00303 log z . Proof. Some classical manipulations give us that

1/G(z) = δ≤z µ 2 (δ)φ(δ) δ 2 (log z) 2 ℓ≤z/δ, (ℓ,δ)=1 µ(ℓ) log z/δ ℓ ℓ 2 .
By [14, Corollary 1.10], the inner sum is non-negative and at most 1.00303δ/φ(δ), hence

1/G(z) ≤ 1.00303 (log z) 2 m≤z µ 2 (m) log(z/m) m ℓδ=m µ(ℓ) = 1.00303 log z
as announced. □

A flexible setting

Sums with F (log x n ). Let us start with a lemma that sets the scene of this section. Lemma 5.1. Let F : R ≥0 → R ≥0 be differentiable with F ′ ≥ 0 and let x ≥ y ≥ 1. Let (u n ) be a sequence of non-negative real numbers for which we have, for any integer d ≥ 1, any t ≥ 0 and some α ∈ [0, 1),

m≤t u dm m α ≤ ρt 1-α /(1 -α)
for some non-negative real parameter ρ. Then we have

n≤y n≡0[d] u n n α F log x n ≤ ρ y 1-α d (T 1-α F ) log x y ,
where the operator T β is defined by

(T β G)(X) = ∞ 0 e -βt G(X + t) dt.
We also set T 1 = T .

The operator T β can also be defined on polynomials by

T β (X j ) = 0≤ℓ≤j j ℓ ℓ!β -ℓ-1 X j-ℓ .
One of the difficulties, when we apply this lemma, is that the assumption on u n should hold as soon as t ≥ 1, and this often leads to larger values of ρ than we would like. In our present case of study, the sequence u n is the characteristic function of the squarefree numbers. We would like to take ρ = 6/π 2 , and this is for instance possible when α = 2/3 by Lemma 3.6 but we are often forced to select ρ = 1. We present in Lemma 5.2 a way to recover from this loss.

Proof. We see that

n≤y n≡0[d] u n n α F log x n ≤ m≤y/d u dm (dm) α F log x/d m
which reduces to the case d = 1. By considering F 1 (t) = F (log(x/y)+t), we further reduce the question to the case y = x. In this special case, and with β = 1 -α, we find that

n≤x u n n α F log x n ≤ n≤x u n n α log(x/n) 0 F ′ (t)dt + F (0) n≤x u n n α ≤ log x 0 n≤xe -t u n n α F ′ (t)dt + ρx β β F (0) ≤ log x 0 ρ β (xe -t ) β F ′ (t)dt + ρx β β F (0) ≤ ρ β F (log x) + ρx β log x 0 e -βt F (t)dt.
Since F is non-decreasing, we have

x β ∞ log x e -βt F (t)dt ≥ xF (log x)/β, hence n≤x u n F log x n ≤ ρx ∞ 0 e -t F (t)dt. □ Lemma 5.2.
Let T ♭ be the linear operator defined on polynomials of degree at most 10 by

T ♭ (X a ) = 0≤r≤a a r r!c r X a-r
where the structure constants c r are defined in Lemma 3.7. For any real polynomial F of degree at most 10 and with non-negative coefficients, for any x ≥ y > 0 and any d ≥ 1, we have

n≤y, n≡0[d] µ 2 (n)F log x n ≤ y d T ♭ F log x y .
Proof. We see that

n≤y, n≡0[d] µ 2 (n)F log x n ≤ m≤y/d µ 2 (m)F log x/d m
(we have omitted the coprimality condition (m, d) = 1), which reduces our problem to the case d = 1. By linearity and the non-negativity of the coefficients of F , it suffices to prove the result for F (y) = y a , for a ≤ 10. To do so, we simply note that

n≤y µ 2 (n) log x n a = 0≤r≤a a r log x y a-r n≤y µ 2 (n) log y n r ≤ 0≤r≤a a r log x y a-r
r!c r • y by Lemma 3.7. The lemma follows swiftly. □ Lemma 5.3. Let A(X) be a real polynomial and B(X) = A(X/3). The linear operator V :

A → T 1/3 T 1/3 T 1/3 B(0) maps X j to 27 2 (j + 2)!. Proof. We rapidly check that V (X j ) = ∞ 0 ∞ 0 ∞ 0 e -u 1 +u 2 +u 3 3 u 1 + u 2 + u 3 3 j du 1 du 2 du 3 . Put u i = 3v i for i ∈ {1, 2, 3} and v = v 1 + v 2 + v 3 . Then V (X j ) = 27 ∞ 0 e -v v j ∞ 0 ∞ 0 u1+u2≤v du 1 du 2 dv = 27 2 ∞ 0 e -v v j+2 dv = 27 2 (j + 2)!
as announced. □ Lemma 5.4. When F ≥ 0 is C 1 and non-decreasing, and y ≥ 1, we have

n≤y µ 2 (n)τ (n) n 2/3 F log y n ≤ 6 π 2 y 1/3 6 π 2 log y + 1.166 T 1/3 F (0).
Proof. We use the non-negativity of F to write

n≤y µ 2 (n)τ (n) n 2/3 F log y n ≤ ℓ≤y µ 2 (ℓ) ℓ 2/3 m≤y/ℓ µ 2 (m) m 2/3 F log y/ℓ m ≤ 6 π 2 y 1/3 ℓ≤y µ 2 (ℓ) ℓ T 1/3 F (0)
and we conclude by bounding above the sum over ℓ through Lemma 3.5. □ Sums over squarefree n's of F (log n)/n α . Lemma 5.5. For any x ≥ 1, d ≥ 1 and for any polynomial F with non-negative coefficients and degree at most 10, we have

n≥x n≡0[d] µ 2 (n) F (log n) n 3/2 ≤ 1.088 T 1/2 F (log x) d √ x .
Proof. It is enough to establish this inequality when d = 1 and on monomials

F (u) = u a for u ∈ {0, 1, • • • , 10}. We then notice that ∞ x (log t) a dt t 3/2 = 1 √ x 0≤r≤a a r (log x) a-r ∞ 1 (log u) r du u 3/2 = 1 √ x 0≤r≤a a r (log x) a-r ∞ 0 t r e -t/2 dt = 1 √ x 0≤r≤a a r 2 r+1 (log x) a-r r! = T 1/2 X a (log x) √ x .
This expression also proves that x → T 1/2 X a (log x)/ √ x is increasing in x. When x ≥ A = exp(2a/3) + 1, the usual sum-integral comparison tells us that

Σ(x) = n≥x µ 2 (n) (log n) a n 3/2 ≤ ∞ x-1 (log t) a dt t 3/2 = x x -1 ∞ x (log( x-1 x u)) a du u 3/2 ≤ x x -1 ∞ x (log u) a du u 3/2 .
This is enough for large values of x, i.e. when x ≥ 1/(1 -(1.088) -2 ). For smaller values of x, we proceed as follows. Say x ∈ (N -1, N ], where N is an integer. We need to compare Σ(N ) to ∞ N (log u) a du u 3/2 . Pari/GP numerical integration for such functions is reliable. We majorize Σ(x) by using direct summation when n ≤ 10 5 and by majorizing the tail by ignoring the squarefree condition and using some Pari/GP inbuilt acceleration of convergence. Here is our Pari/GP script.

{Check( a = 4, expo = 3/2) = my(bornesup = ceil(2*exp(a/expo) + 1000), intsup, sommesup, coeff = sqrt(bornesup/(bornesup-1)), wheremax, hardmax = 10^5); intsup = intnum(t = bornesup, oo, (log(t))^a/t^expo); sommesup = sum(n = bornesup, hardmax, if(issquarefree(n), log(n)^a/n^expo,0)) + sumpos(n = hardmax + 1, log(n)^a/n^expo,0); coeff = max(coeff, sommesup/intsup); forstep(n = bornesup-1, 1, -1, intsup += intnum(t = n, n+1, (log(t))^a/t^expo); sommesup += if(issquarefree(n), (log(n))^a/n^expo, 0); if(coeff < sommesup/intsup, coeff = sommesup/intsup; wheremax = n,)); print("*** sum_{n >= N} mu^2(n)(log n)^", a, "/n^(", expo, ") <= "); print(coeff," x int(t = N, oo, (log(t))^", a, "/t^(", expo,"))"); print(" --reached around N = ", wheremax); } □ Lemma 5.6. For any x ≥ 1, d ≥ 1 and for any polynomial F with non-negative coefficients and degree at most 10, we have

n≥x n≡0[d] µ 2 (n) F (log n) n 2 ≤ 1.520 T F (log x) d x .
Proof. It is again enough to establish this inequality when d = 1 and on monomials

F (u) = u a for u ∈ {0, 1, • • • , 10}. When x ≥ A = exp(2a/3
) + 1, we note that the usual sum-integral comparison tells us that we have

n≥x µ 2 (n) (log n) a n 2 ≤ ∞ x-1 (log t) a dt t 2 = x x -1 ∞ N (log( x-1 x u)) a du u 2 ≤ x x -1 ∞ x (log u) a du u 2 .
We then proceed as in Lemma 5.5, though with the choice expo = 2 in the associated Pari/GP script. □

Estimation of the sum S(z)

Recall that we have defined

S = S(z) = n≤z 2 [d1,d2]=n |λ d1 ||λ d2 | 2 .
Theorem 6.1. When z > 1, we have S ≤ 278 000 z 2 6 π 2 log z + 1.166 (log z) 4 .

The computations leading to Lemma 7.1 tend to accredit the idea that S is indeed of order z 2 /(log z) 3 , though the constant in front should be much smaller than our 6 π 2 278000.

Proof of Theorem 6.1. Let F 0 (x) = x 4 . Define functions F 1 , F 2 , F 3 , F 4 and F 5 by ( 11)

F j+1 = T ♭ F j , 0 ≤ j ≤ 5
where T ♭ is defined in Lemma 5.2. Though it is not required for the following, we directly check that

                 F 1 (x) = x 4 +
1 d 1 d 2 d 3 F 1 log z d 4 .
For a fixed g ≤ z 2 and g 1 g 2 = g 3 g 4 = g with g 1 , g 2 , g 3 , g 4 ≤ z, the inside sum over the d j 's is at most

S ′ = d3≤d2≤d1≤z gi|di 1 d 1 d 2 d 3 d4≤d3 g4|d4 F 1 log z d 4 ≤ 1 g 4 d3≤d2≤d1≤z gi|di 1 d 1 d 2 F 2 log z d 3 . Note that we have [d 1 d 2 , d 3 d 4 ] = D ≤ zd 4 , hence d 1 d 2 d 3 d 4 /g ≤ zd 4 which simplifies to d 1 d 2 d 3 ≤ zg.
Taking this condition into consideration, we find that

S ′ ≤ 1 g 4 d2≤d1≤z gi|di 1 d 1 d 2 d3≤min{d2, zg d 1 d 2 } g3|d3 F 2 log z d 3 .
The next is to split the resulting upper bound in three parts as follows:

S ′ ≤ 1 g 4 d1≤(zg) 1/3 g1|d1 d2≤d1 g2|d2 1 d 1 d 2 d3≤d2 g3|d3 F 2 log z d 3 + 1 g 4 (zg) 1/3 <d1≤z g1|d1 d2≤ zg d 1 1/2 g2|d2 1 d 1 d 2 d3≤d2 g3|d3 F 2 log z d 3 + 1 g 4 (zg) 1/3 <d1≤z g1|d1 zg d 1 1/2 <d2≤d1 g2|d2 1 d 1 d 2 d3≤ zg d 1 d 2 g3|d3 F 2 log z d 3 = S ′ 1 + S ′ 2 + S ′ 3 .
The sum S ′ 1 may treated in a rather straightforward manner:

S ′ 1 ≤ 1 g d1≤(zg) 1/3 g1|d1 1 d 1 d2≤d1 g2|d2 F 3 log z d 2 ≤ 1 gg 2 d1≤(zg) 1/3 g1|d1 F 4 log z d 1 ≤ (zg) 1/3 g 2 F 5 log z (zg) 1/3 ≤ (zg) 1/3 g 2 F 5 1 3 log z 2 g .
Next, the treatment of S ′ 2 starts similarly as the one of S ′ 1 but differs from the second line onwards:

S ′ 2 ≤ 1 g (zg) 1/3 <d1≤z g1|d1 1 d 1 d2≤ zg d 1 1/2 g2|d2 F 3 log z d 2 ≤ (zg) 1/2 gg 2 (zg) 1/3 <d1≤z g1|d1 1 d 3/2 1 F 4 log zd 1/2 1 (zg) 1/2 = (zg) 1/2 gg 2 (zg) 1/3 <d1≤z g1|d1 1 d 3/2 1 F 4 1 2 log zd 1 g ≤ 1.088 (zg) 1/3 g 2 ( T1/2 F 4 ) 1 3 log z 2 g
on denoting by T1/2 the operator that, to F , associates T 1/2 (G), where G(X) = F (X/2).

The last inequality comes from invoking Lemma 5.5 with F (u) = F 4 ( 1 2 u + 1 2 log(z/g)). We continue with a bound for S ′ 3 :

S ′ 3 = 1 g 4 (zg) 1/3 <d1≤z g1|d1 zg d 1 1/2 <d2≤d1 g2|d2 1 d 1 d 2 d3≤ zg d 1 d 2 g3|d3 F 2 log z d 3 ≤ 1 g (zg) 1/3 <d1≤z g1|d1 zg d 1 1/2 <d2≤d1 g2|d2 1 d 1 d 2 zg d 1 d 2 F 3 log d 1 d 2 g ≤ 1.52 zg gg 2 (zg) 1/3 <d1≤z g1|d1 1 d 2 1 d 1/2 1 (zg) 1/2 T F 3 1 2 log zd 1 g
by Lemma 5.6. We shuffle some terms and continue:

S ′ 3 ≤ 1.52 (zg) 1/2 gg 2 (zg) 1/3 <d1≤z g1|d1 1 d 3/2 1 T F 3 1 2 log zd 1 g ≤ 1.52 × 1.088 (zg) 1/3 g 2 ( T1/2 T F 3 ) 1 3 log z 2 g .
Therefore, from the above and ( 13), we have

(14) S ≤ 3z 4/3 2(log z) 4 g≤z 2 τ * (g) 2 g 2/3 H log z 2 g ,
where H(x) = F 5 (x/3) + 1.088 ( T1/2 F 4 )(x/3) + 1.52 × 1.088 ( T1/2 T F 3 )(x/3) and

τ * (g) = g1g2=g gi≤z 1.
During the proof of [3, Lemma 2.1], the authors proved that τ * (g) 2 is also the number of solutions of g = abcd with ab, cd, ac, bd ≤ z. Since this number in invariant under the changes a ↔ d and b ↔ c, we may assume that c ≤ b (with an extra factor 2). Thus

S ≤ 3z 4/3 (log z) 4 a≤z b≤z/a (a,b)=1 c≤b d≤z/b 1 (abcd) 2/3 H log z 2 abcd .
Please notice the 'd ≤ z/b'. We do the d-sum, then the c-sum, getting

S ≤ 3z 5/3 (log z) 4 a≤z b≤z/a (a,b)=1 1 (ab) 2/3 T 1/3 T 1/3 H log z 2 ab = 3ρ 2 z 5/3 (log z) 4 n≤z µ 2 (n)τ (n) n 2/3 (T 1/3 T 1/3 H) log z n ≤ 3ρ 3 z 2 (log z) 4
by Lemma 5.4 with ρ = 6/π 2 for the last inequality. We also have

T 1/3 T 1/3 T 1/3 H(0) = V (F 5 + 1.088 (T 1/2 F 4 ) + 1.52 × 1.088 (T 1/2 T F 3 )) = 412082.980 • • • .
This gives (the ρ 3 has been taken into account) (15) S ≤ 277 760 z 2 6 π 2 log z + 1.166 (log z) 4 .

The proof of our theorem is complete. □

Computing S(z)

This part is not required a priori. We produce it to support our belief that S(z) is indeed of size z 2 /(log z) 3 , a fact that is far from obvious from its expression. Lemma 7.1. When z ≤ z 0 = 15000, we have S(z) ≤ 3.3 z 2 /(log z) 3 while S(z 0 ) ≥ 3.28 z 2 0 /(log z 0 ) 3 . We numerically observed that the function S(z)(log z) 3 /z 2 is non-decreasing in the range z ≤ z 0 . A plot with sample values taken every 50 is given in Figure 3. To run the required computations, we need precise and sparse expressions. We use the notation δ j = log d j and restrict the variables d j to be squarefree. We expand S(z) into

S(z) = [d1,d2]=[d3,d4], d1,d2,d3,d4≤z 1 - δ 1 + δ 2 + δ 3 + δ 4 log z + δ 1 δ 2 + δ 3 δ 4 + (δ 1 + δ 2 )(δ 3 + δ 4 ) (log z) 2 - δ 1 δ 2 (δ 3 + δ 4 ) + (δ 1 + δ 2 )δ 3 δ 4 ) (log z) 3 + δ 1 δ 2 δ 3 δ 4 (log z) 4
i.e. after shuffling the terms,

S(z) = [d1,d2]=[d3,d4], d1,d2,d3,d4≤z 1 - 4δ 1 log z + 2δ 1 δ 2 + 4δ 1 δ 3 (log z) 2 - 4δ 1 δ 2 δ 3 (log z) 3 + δ 1 δ 2 δ 3 δ 4 (log z) 4 = S 0 (z) - S 1 (z) log z + S 2 (z) (log z) 2 - S 3 (z) (log z) 3 + S 4 (z) (log z) 4 .
Let us assume that z is an integer. When going from z to z + 1, the sum S(z) changes only when one of the d i can take the value z + 1, hence z + 1 has to be squarefree. We proceed as follows:

• Set Local variations. We have to find the maximal absolute value of

d 1 = z + 1. For each d 2 ≤ z + 1,
S 0 (z) - S 1 (z) log z + S 2 (z) (log z) 2 - S 3 (z) (log z) 3 + S 4 (z) (log z) 4 /z 2
when z varies in an interval [z 0 , z 0 + 1) for some integer z 0 . The derivative times z 3 is given by, with w = 1/ log z,

-2S 0 (z) + 2S 1 (z)w + (S 1 (z) -2S 2 (z))w 2 + (-2S 2 (z) + 2S 3 (z))w 3 -(-3S 3 (z) + 2S 4 (z))w 4 -4S 4 (z)w 5
Final remarks. The previous notes are enough to build an algorithm. Let us specify that we precomputed all the logarithms of the natural numbers up to the final bound z 0 and that we used the forfactored-loop of Pari/GP to speed up computations. The script is available on request.

Estimation of the sum S(z)

Recall that we have defined

S = S(z) = n≤z 2 [d1,d2]=n |λ d1 ||λ d2 | 2 /n.
Lemma 8.1. We define the linear operator T on polynomials by T [Y j ] = Y j /j!. For every integer a ≥ 1 and every real number x ≥ 1, we have

n≤x µ 2 (n)a ω(n) n ≤ T [( 6 π 2 Y + 1.166) a ](log x).
To be precise, we expand the polynomial ( 6 π 2 Y + 1.166) a , apply the operator T to this expansion and finally evaluate the result at Y = log x.

Proof. We proceed by recursion on a, the case a = 1 being recorded in Lemma 3.5. Let us prove the recursion step. We employ the identity (a + 1) ω(n) = kℓ=n a ω(k) valid when n is squarefree to infer that

n≤x µ 2 (n)(a + 1) ω(n) n ≤ kℓ≤x µ 2 (k)µ 2 (ℓ)a ω(k) kℓ ≤ k≤x µ 2 (k)a ω(k) k 6 π 2 log x k + 1.166 = S 1 + S 2
where

S 1 = 6 π 2 k≤x µ 2 (k)a ω(k) k x k dt t ≤ 6 π 2 x 1 T [( 6 π 2 Y + 1.166) a ](log t) dt t
by the recursion hypothesis. We now notice that

x 1 T [Y j ](log t) dt t = T [Y j+1
](log x), which implies that, for any polynomial P , we have . Note also that this inequality is optimal when d 1 = d 2 . This implies that, for squarefree n, we have

x 1 T [P (Y )](log t)dt/t = T [P (Y )Y ](log x). This leads to S 1 ≤ T [( 6 π 2 Y + 1.166) a 6 π 2 Y ](log x),
[d1,d2]=n λ d1 λ d2 ≤ 1 4(log z) 2 [d1,d2]=n log z 2 d 1 d 2 2 ≤ 1 4(log z) 2 [d1,d2]=n log z 2 n 2 = 1 4(log z) 2 log z 2 n 2 3 ω(n) since, when n is squarefree, we have [d1,d2]=n 1 = 3 ω(n) . This implies that S ≤ 1 16(log z) 4 n≤z 2 µ 2 (n)9 ω(n) n log z 2 n 4 .
We set y = z 2 and notice that log y n

4 = 4 y n log y t 3 dt t .
On using this and Lemma 8.1 and its notation with the shortcut ρ = 6/π 2 , we get

S ≤ 1 4(log z) 4 y 1 n≤t µ 2 (n)9 ω(n) n log y t 3 dt t ≤ 4 (log y) 4 y 1 T [(ρY + 1.166) 9 ](log t) log y t 3 dt t .
We recall the classical formula for the Euler beta-function:

y 1 (log t) a log y t b dt t = a!b! (a + b + 1)! (log y) a+b+1 .
We expand T [(ρY + 1.166) 9 ], and get

S ≤ 4 (log y) 4 0≤k≤9 9 k ρ k 1.166 9-k 1 k! 6 • k! (k + 4)! (log y) k+4 ≤ 24 0≤k≤9 9 k ρ k 1.166 9-k (log y) k (k + 4)! .
This gives us S ≤ 7 • 10 -6 (log z) 9 + 6 π 2 when z ≥ 1000. □ Let us now introduce the explicit expression of κ given in Lemma 2.6, and recall that χ(0) = 0. We pair ℓ and -ℓ and note that

         κ(x/π) + κ(-x/π) = 12 sin x/3 x 2 cos 2x 3 - sin x/3 x 3 cos x 2 , κ(x/π) -κ(-x/π) = 12 -i sin x/3 x 2 sin 2x 3 + i sin x/3 x 3 sin x 2 .
The main feature of these expressions lies in the fact that they vanish when x = 0. We use Lemma 3.1 with c = ∞ and

f ε (x) = |κ(x/π) + εκ(-x/π)| for ε ∈ {±1}. We find that | √ rS/y| ≤ r πy ∞ 0 |f ε (x)|dx + 1 2 ∞ 0 |f ′ ε (x)|dx.
Numerical integration gives us

1 π ∞ 0 |f ε (x)|dx ≤ 0.9918 when ε = 1, 0.9872 when ε = -1, ∞ 0 |f ′ ε (x)|dx ≤ 2.4 when ε = 1, 3.6 when ε = -1.
For this last computation, we need explicit expressions for f ′ ε , and here they are:

f ′ + (x)/12 = - 2 3 sin 2x 3 sin x/3 x 2 + 1 2 sin x 2 sin x/3 x 3 + 2 3 cos x 3 cos 2x 3 sin x/3 x 2 - 1 x cos x 3 cos x 2 sin x/3 x 2 - 2 x cos 2x 3 sin x/3 x 2 + 3 x cos x 2 sin x/3 x 3 , and
if ′ -(x)/12 = 2 3 cos 2x 3 sin x/3 x 2 - 1 2 cos x 2 sin x/3 x 3 + 2 3 sin x 3 cos 2x 3 sin x/3 x 2 - 1 x sin x 3 cos x 2 sin x/3 x 2 - 2 x sin 2x 3 sin x/3 x 2 + 3 x sin x 2 sin x/3 x 3 . □ Lemma 9.2. When χ is a primitive Dirichlet character of conductor r > 1, we have 1 2π 1 2 +i∞ 1 2 -i∞ (s + 1) η * (s)L(s, χ) 2 |ds| ≤ 1.1 max(r, 10 7 ).
Proof. We have

(16) (s + 1) η * (s)L(s, χ) = κ(s)L(s, χ) = ∞ 0 n≤1/v χ(n)κ(vn)v s dv v
which identifies (s + 1) η * (s) as a Mellin transform. By the Parseval identity for Mellin transforms, we find that 1 2π

1 2 +i∞ 1 2 -i∞ (s + 1) η * (s)L(s, χ) 2 |ds| = ∞ 0 n≤1/v κ(vn)χ(n) 2 dv = ∞ 0 n≤t κ(n/t)χ(n) 2 dt t 2 .
We are now in a position to apply Lemma 9.1, and this leads us to 1 2π

1 2 +i∞ 1 2 -i∞ (s + 1) η * (s)L(s, χ) 2 |ds| ≤ T 1 2 √ 6t 9 + 4 2 dt t 2 + ∞ T max(r, 10 7 ) 2 dt t 2 ≤ 24T 81 + 16 √ 6 9
log T + 16 + max(r, 10 7 ) T .

We take T = 9 2 √ 6 max(r, 10 7 ) and get the bound

1 2π 1 2 +i∞ 1 2 -i∞ (s + 1) η * (s)L(s, χ) 2 |ds| ≤ 1.089 √ r + 4.4 log(1.84 √ r) + 16 ≤ 1.1 max(r, 10 7 ).
This ends the proof. □ Proof of Theorem 1.4. In this proof, we shall use the Dirichlet polynomial

(17) K(s, χ) = d1,d2 λ d1 λ d2 χ([d 1 , d 2 ]) [d 1 , d 2 ] s , u n = [d1,d2]=n λ d1 λ d2
where the (λ d )'s come from [START_REF] Gallagher | A large sieve density estimate near σ = 1[END_REF]. We proceed as in the proof of Theorem 1.5 and 1.6 in [16, Section 6], with H = {1}. This results in having only primitive characters below. We thus reach

p≥1, p≡a[q] η * (p/X) ≤ n≥1, n≡a[q] η * (n/X) d|n λ d 2 + p<z, p≡a[q] η * (p/X) ≤ d1,d2 λ d1 λ d2 1 φ(q) r|q χ mod * r χ(a) n≥1, [d1,d2]|n χ(n)η * (n/X) + zq -1 + 1 2 ≤ 1 φ(q) d1,d2 λ d1 λ d2 m≥1 η * ([d 1 , d 2 ]m/X) + E(a) + zq -1 + 1 2 (18)
where ( 19)

E(a) = 1 φ(q) 1<r|q χ mod * r χ(a) 1 2iπ 2+i∞ 2-i∞ L(s, χ)K(s, χ)X s η * (s)ds.
Contribution of the principal character. The term in ( 18) is easily dealt with. Let [START_REF] Rosser | Sharper bounds for the Chebyshev Functions ϑ(x) and ψ(x)[END_REF] M (q, η * , X) = 1 φ(q) d1,d2

λ d1 λ d2 m≥1 η * ([d 1 , d 2 ]m/X).
We find that M (q, η * , X) -2X 9φ(q) d1,d2

λ d1 λ d2 [d 1 , d 2 ] ≤ θ X 2 φ(q) d1,d2 |λ d1 λ d2 |[d 1 , d 2 ] 2 ≤ θ X 2 φ(q) d d 2 |λ d | 2 ≤ θz 6 X 2 φ(q)(log z) 2
where θ is defined in Lemma 2.3, and where we have used Lemma 4.1. Whence, when z 2 ≤ X/100 and z ≥ 100, we find that [START_REF] Treviño | The least inert prime in a real quadratic field[END_REF] M (q, η * , X) ≤ 2X 9φ(q) log z 1.00303 + 9 × 0.28 z 6 2X 3 (log z) 3 ≤ 1.004 2X/9 φ(q) log z .

Contribution of the non-principal characters. We now concentrate on E(a) for which we seek an L 2 -average upperbound. We first shift the line of integration to ℜs = 1/2 and get

φ(q) 2 a mod * q E(a) 2 = a mod * q 1<r|q, χ mod * r χ(a) 1 2iπ 1 2 +i∞ 1 2 -i∞ L(s, χ)K(s, χ)X s η * (s)ds 2 .
We note that, for arbitrary complex numbers (f (χ)) χ , we have

a mod * q 1<r|q, χ mod * r χ(a)f (χ) 2 = φ(q) 1<r|q, χ mod * r |f (χ)| 2
simply because, when a is prime to q, there is no difference between the primitive character modulo r and its induced version modulo q. We continue with Cauchy's inequality and Lemma 9.2 to write successively φ(q)

a mod * q E(a) 2 ≤ X 4π 2 1<r|q, χ mod * r 1 2 +i∞ 1 2 -i∞ |(s + 1) η * (s)L(s, χ)| 2 |ds| 1 2 +i∞ 1 2 -i∞ K(s, χ) 2 dt |s + 1| 2 ≤ 1.1 X √ q 2π 1<r|q, χ mod * r 1 2 +i∞ 1 2 -i∞ K(s, χ) 2 dt |s + 1| 2 ≤ 1.1 X √ q ∞ 0 1<r|q, χ mod * r v n≤1/v nu n χ(n) 2 dv since K(s) s + 1 = ∞ 0 v n≤t nu n v s-1 dv v .
We continue by using the orthogonality of the characters and get φ(q)

a mod * q E(a) 2 ≤ 1.1 X √ q ∞ 0 n≤t n 2 u 2 n (t + q) dt t 4 ≤ 1.1 X √ q n≤z 2 n 2 u 2 n z 2 n dt t 3 + z 2 ∞ z 2 dt t 4 + q ∞ n dt t 4 ≤ 1.1 X √ q n≤t u 2 n 1 2 - n 2 6z 4 + q 3n .
On neglecting the term n 2 /6z 4 , we reach φ(q) X √ q a mod * q E(a) 2 ≤ 0.55 2 where ϵ(a) = φ(q)E(a) log z 2X/9 .

n≥1 |u n | 2 + 0.367q n≥1 |u n | 2 n . Let ∆ = 1 φ(q) a mod * q ϵ(a)
By Theorems 6.1 and 8.2, we find that, when z ≥ 10 27 , ∆ ≤ 0.55 278000 z 2 6 π 2 log z + 1.166 (log z) 4 + 0.367q 7 log 9 z 10 7 + 6 π 2

√ q log 2 z 4X/81 .

We use (22) z = X 10 9 √ q , X ≥ (10 7 q) 5/2 .

The hypothesis q ≥ 10 30 ensures that z ≥ 10 32 , hence ∆ ≤ 1.95 • 10 6 10 9 log(10 35/4 q/10 9/2 ) + 248 log 2 (10 6 q/10 9/2 ) 10 35/2 q 2 • 10 -7 2 log 10 35/4 q 10 9/2 9 + 6 π 2 .

A numerical application concludes that ∆ ≤ 1/42804. We finally have to take care of the additional factor (zq -1 + 1)/2. We introduce δ = (z + q)(log z)/(4X/9) ≥ φ(q) zq -1 + 1 2 log z 2X/9 .

We have δ ≤ 10 -50 . We find that 1 φ(q)

a mod * q (ϵ(a) + δ) 2 ≤ ∆ + 2δ √ ∆ + δ 2 ≤ 1/42500
as claimed, by renaming ϵ(a) + δ by ϵ(a). □ 10. A Brun-Titchmarsh inequality for cosets Theorem 1.6 of [START_REF] Ramaré | Products of primes in arithmetic progressions[END_REF] has the condition q ≤ y 1/3 /900. This was introduced only to get better numerics, as the proof indeed allows for y ξ for any ξ ≤ 2/5. At this level we can even save a bit, as shown in the next result.

In this section, we use

(23) η(t) =      2t, 0 ≤ t ≤ 1/2, 2(1 -t), 1/2 ≤ t ≤ 1, 0,
otherwise.

Lemma 10.1. When z ≥ 6, we have d≤z µ 2 (d)/φ(d) ≥ log z + 1.24.

The bound follows from [18, Theorem 3.1] when z ≥ 700. We complete the proof by a direct inspection. The constant 1.24 is forced by the case z = 29. Lemma 10.2. Let y 1/5 ≥ √ q ≥ 3000 and η be as in (23). Let G q = (Z/qZ) × and let H ⊆ G q be a subgroup of index 5. Then for any class u in G q .

If we guarantee y 30 √ q > y 4/5 , and since the total weight (given by Lemma 10.3) is indeed y/(2 log y), this ensures an accumulation per coset which is strictly less than half the total number of primes. From this we shall deduce that at least three cosets contain primes.

Proof. We modify the end of the proof of [START_REF] Ramaré | Products of primes in arithmetic progressions[END_REF]Theorem 1.6] starting from equation (17) therein as follows and using Lemma 10.1 above rather than G(z) ≥ log z as in [START_REF] Ramaré | Products of primes in arithmetic progressions[END_REF]Lemma 4.2]. We first deduce a more precise inequality from these assumptions:

Y log y y/2 π η (y; q, uH) ≤ log y log z + 1.24 + 2zY log y y + √ q 2Y z 2 log y y(log z + 1.24)

A + A = G.
Proof of Theorem 1.1. Let P(y) be the set of primes below y that do not divide q and let A be the image of P(y) in G q = (Z/qZ) × . We seek to show that A • A • A = G q . Recall that we assume that (25) 10 30 ≤ q ≤ y 2/5 /10

(p,q)=1 η * (p/y) = a mod * q p≡a[q]
η * (p/y) ≤ a∈A (U + ξ(a))2y/9 φ(q) log y where (27) J = log y log y 10 9 √ q ≤ 1.303, U = 2.008J, ξ(a) = 2ϵ(a)J Lemma 12.2. For every q ≤ 200 and q / ∈ {2, 3, 4, 5, 6, 10}, every invertible class modulo q contains a product of three primes, each of which of size at most q.

If we replace the bound q by 2q, then no exception would occur. We then go farther step by step to take care of the irregularities occuring at small values.

Lemma 12.3. For every q ∈ [200, 30 000], every invertible class modulo q contains a product of three primes, each of which being of size at most B(q), where

Step-1. B(q) = q/2 when q ∈ [200, 600],

Step-2. B(q) = q/4 when q ∈ [600, 1000],

Step-3. B(q) = q/5 when q ∈ [1000, 2000],

Step-4. B(q) = q/8 when q ∈ [2000, 3000],

Step-5. B(q) = q/10 when q ∈ [3000, 4500],

Step-6. B(q) = q/14 when q ∈ [4500, 5200],

Step-7. B(q) = q 5/7 when q ∈ [5200, 10 000],

Step-8. B(q) = q 2/3 when q ∈ [10 000, 24 000],

Step-9. B(q) = q 13/20 when q ∈ [24 000, 30 000].

It is expected that one should be able to reach B(q) = q 1/3+δ for any arbitrary small positive δ. If this is true, our numerical trials show that the asymptotic regime is slow to become dominant. This explains why this line of approach yields less slower results than the one with products of two primes. A better algorithm would aim at a lesser bound for B(q) and handle the exceptional q's and the classes not represented in a special way, but we did not attempt such dedicated programming. 12.3. Products of three primes below q(log q) 2 . Proof of Theorem 1.2. The previous strategies require large tables and are impractical when q starts to be somewhat large. We relax these conditions in Theorem 1.2. Our algorithmic strategy is to first find the smallest prime congruent to 1 modulo q and then to check that each class modulo q contains an integer that has at most three prime factors and is indeed of size at most q(log q) 2 . We then precompute the integers that have more than four many prime factors and use the Set data-structure to determine quickly whether an integer belongs to this list. With the Pari/GP script below compiled with gp2c, we reach the bound 2 • 10 7 in about 30 minutes of a standard laptop. Increasing the bound 2 • 10 7 would require an increase of the memory by the same factor, and we already use nearly 8Gb.

The bound for the required primes outputed by this script varies slowly but does not tend to decrease and for instance, we need primes up to more that 0.95 q(log q) 2 for some q ∈ [19900000, 19950000]. If we need a statement valid for every q ≥ 3 (resp. q ≥ 2), we only have to replace q(log q) 2 by 2q(log q) 2 (resp. 4q(log q) 2 ). for(q = borneinf, bornesup, if(q % whentotell == 0, print("When ", max(borneinf, q -whentotell) , " <= q < ", q, " --> locmax = ", locmax); maxgot = max(maxgot, locmax); locmax = 0); btt = q*log(q)^2; pmax = 0; /* Ensure we can find a prime congruent to 1 */ forprimestep(p = q + 1, q^2, q, if(p % q == 1, pmax = p; break)); if(pmax == 0, print("Error!!"); return(0), locmax = max( locmax, pmax / btt)); /* Find a product of at most three primes in each class: */ for(n = 16, q -1, if(gcd(n, q) == 1, while(((n <= multi*bornesup)&&(setsearch(setbadn, n))) ||(bigomega(n) >= 4), n += q); locmax = max( locmax, n / btt)))); if(bornesup % whentotell != 0, print("When ", max(borneinf-1, floor(bornesup/whentotell)*whentotell), " <= q <= ", bornesup, " --> locmax = ", locmax)); maxgot = max(maxgot, locmax); return(maxgot);} 13. Changing the constants in Theorems 1.4 and 1.1

On reading patiently the proof of Theorem 1.4, we obtain the following.

Theorem 13.1. Let q ≥ q 0 ≥ 2 • 10 7 be an integer. Let X ≥ (Cq) 5/2 be some real number. For every invertible class a modulo q, we have p≡a[q] η * (p/X) ≤ 2(1.004 + ϵ(a)) • 2X/9 φ(q) log X R √ q where a mod * q ϵ(a) 2 ≤ φ(q)/4250, where the constants (q 0 , C, R) may be chosen from Table 2. q 0 2 • 10 Proof. We follow the proof of Theorem 1.4. Lemma 9.2 can be used here as there since q 0 ≥ 10 7 . Inequality (21) requires 10 4 ≤ z 2 ≤ X/100. Theorems 6.1 and 8.2 ask for the stronger condition: z ≥ 1000. Proceeding, we modify (22) in (28) z = X R √ q , X ≥ (Cq) 5/2 .

We thus get z 2 ≥ (C 5/2 /R)q 2 . We have to take care of some monotonicity condition.

In particular, we want √ q(log z) 11 /X to be non-increasing in z 2 = X/(R √ q). We may rewrite this expression as (11/2) 11 ((log(z 2/11 )/z 2/11 ) 11/2 so it is enough to assume that z ≥ exp(11/2) which is small enough. The upper bound for ∆ reduces to, with L = log z and X = (Cq)

R

provided that C 5/2 q 2 0 ≥ 10 6 R. A numerical application yields the values of Table 2. □ Theorem 13.2. For any q ≥ q 0 and any invertible residue class a modulo q, there exists a natural number that is congruent to a modulo q and that is the product of exactly three primes, all of which are below (Cq) 5/2 , where q 0 and C may be obtained from Table 3. q 0 2 • 10 Table 3: possible values in Theorem 13.2.

The present method would not allow to take primes only ≥ q 5/2 however large q, due the usage of Lemma 10.2.

Proof. We follow the proof of Theorem 1.1 and assume that the constants q 0 , C and R are admissible in Theorem 13.1. The condition that emerges is (29) J = log y log y R √ q ≤ 1.3054 where y = (Cq) 5/2 . This is required so that we may reach c ≥ 0.380. This condition reads 1.3054 log R -2 × 1.3054 -5 2 log q ≤ 0.3054 5 2 log C.

We next swiftly build Table 3, though it is to be noticed that C has to be taken as large as 30 for using Lemma 10.2. The proof is complete. □

Figure 2 .κ 1 =

 21 Figure 1. η * (t) Figure 2. κ(t)

Figure 3 .

 3 Figure 3. Plot of max x≤z S(x)(log x) 3 /x 2 for 10 ≤ z ≤ 15000

9 . 4 Lemma 9 . 1 .

 9491 Proof of Theorem 1.We have n≤y κ(n/y)χ(n) Let us denote our sum by S. The first inequality comes from Lemma 3.2. We then use the identity τ (χ)χ(m) = 1≤a<r χ(a)e(am/r) where τ (χ) is here the Gauss sum attached to χ, and get

  {check(borneinf, bornesup, whentotell = 50000) = my(pmax, maxgot = 0, multi = 3, btt, locmax = 0, curindex, nbbadn = 0, setbadn); for(n = 1, multi*bornesup, if(bigomega(n) > 3, nbbadn++)); setbadn = Set(Vecsmall([1.. nbbadn])); curindex = 1; for(n = 1, multi*bornesup, if(bigomega(n) > 3, setbadn[curindex] = n; curindex++));

7 10 10 10 15 10 20 10 30 10 88 C 10 15 10 15 10 14 10 13 10 11 30 R 10 9 10 9 10 9 10 9 5 •

 885 10 8 2 • 10 8

  by Mossinghoff, Oliveira e Silva and Trudgian.

	Lemma 3.6. When y ≥ 1, we have
		n≤y
	Lemma 3.5. When x ≥ 1, we have	n≤x	µ 2 (n) n	≤	6 π 2 log x + 1.166.
	See [15, Lemma 3.4].

Table 1

 1

	6 π 2 t + r(t). We apply Lemma 3.3. In our case, this means that
	the constant we seek is ζ(2/3)/ζ(4/3), which is negative! We have thus proved that
	S =	6 π 2 3y 1/3 +	ζ(2/3) ζ(4/3)	+ O * (5/y 1/6 )
	by using the simple bound of Lemma 3.4. Pari-GP gives us that ζ(2/3)/ζ(4/3) =
	-0.679 • • • . This ensures us that our error term is negative when y ≥ 160000. This
	last range is easily covered by direct computations.

□ Lemma 3.7. When 1 ≤ a ≤ 10 and x ≥ 1, we have n≤x µ 2 (n) log x n a ≤ a!c a x where c 1 0.6715 c 6 0.6108 c 2 0.6365 c 7 0.6097 c 3 0.6227 c 8 0.6101 c 4 0.6161 c 9 0.6127 c 5 0.6127 c 10 0.6175 .

  2.686 x 3 + 7.638 x 2 + 14.9448 x + 14.7864, F 2 (x) = x 4 + 5.372 x 3 + 20.686• • • x 2 + 50.405 • • • x + 59.366 • • • , F 3 (x) = x 4 + 8.058 x 3 + 39.146 • • • x 2 + 113.648 • • • x + 154.405 • • • , Since [d 1 , d 2 ]= n, we replace d i by gd i , where g = gcd(d 1 , d 2 ) so that gd 1 d 2 = n. The proof starts by noting the following chain of inequalities: the inequality log A • log B ≤ (log AB) 2 /4. Notice this inequality is sharp when A = B, or, in our case of application, when d 1 = d 2 . Moreover, since n = gd 1 d 2 and both gd 1 and gd 2 are ≤ z, it follows that[START_REF] Motohashi | On some improvements of the Brun-Titchmarsh theorem[END_REF] n ≤ zd i , i = 1, 2.From now on and until the end of this section, the variables n, d i , g and g i , and later a, b, c and d, refer exclusively to squarefree positive integers. Then we can take y = zd 4 /D in Lemma 5.1 and apply it with F = F 0 , to get Further, we assume that (d 1 , d 3 d 4 ) = g 1 and (d 2 , d 3 d 4 ) = g 2 , so that g 1 g 2 = g. Similarly define g 3 = (d 3 , d 1 d 2 ) and g 4 = (d 4 , d 1 d 2 ), so that one has g 3 g 4 = g. Now, owing to the symmetry of d 1 , d 2 , d 3 , we can assume d 3 ≤ d 2 ≤ d 1 ≤ z with an extra 3!.

	[d1,d2]=n	|λ d1 ||λ d2 | =	gd1d2=n	log z gd1 log z	•	log z gd2 log z	≤	1 4(log z) 2	gd1d2=n	log	g 2 d 1 d 2 z 2	2
					≤	1 4		log z 2 n log z	2	d1d2|n	1,
	where we used Therefore
	S ≤	1 16(log z) 4	n≤z 2		log	z 2 n		4	d1d2|n	1 =	1 16(log z) 4	d1,...,d4≤z n≤zdi	log	n z 2	4
													d3d4|n	n≡0[D]
	≤	1 16(log z) 4	d1,...,d4≤z n≤zdi/D	log	z 2 nD
					S ≤	1 4(log z) 4	d4≤di≤z	zd 4 D	F 1 log	z d 4	.
														We can
	then rewrite the sum as
	(13)		S ≤	3z 2(log z) 4	g≤z 2	g	g1g2=g g3g4=g	d4≤d3≤d2≤d1≤z gi|di

F 4 (x) = x 4 + 10.744 x 3 + 63.017

• • • x 2 + 211.940 • • • x + 325.447 • • • , F 5 (x) = x 4 + 13.43 x 3 + 92.299 • • • x 2 + 352.549 • • • x + 602.915 • • • .

4 where D = [d 1 d 2 , d 3 d 4 ]. Without loss of generality (and an extra factor of 4), we assume d 4 is the smallest. We suppose that g = (d 1 d 2 , d 3 d 4 ), so that D = d 1 d 2 d 3 d 4 /g.

  build all the couples (d 3 , d 4 ), with each being ≤ z + 1, and add what has to be added to the S i . • Assume henceforth that d 1 ≤ z, set d 2 = z + 1, and again all the couples (d 3 , d 4 ), with each being ≤ z + 1, and add what has to be added. • Assume then that d 1 and d 2 are bounded above by z and set d 3 = z + 1. For each d 4 ≤ z + 1, build all the couples (d 1 , d 2 ) and add what is to be added. • Finally, do the same with d 4 = z + 1 and d 1 , d 2 and d 3 being bounded above by z.

  while by the recursion hypothesis, we have S 2 ≤ 1.166 T [(6π 2 Y + 1.166) a ](log x). This gives the required upper bound for S 1 + S 2 and concludes the proof.

	Proof. Note that us log(z/d 1 ) log(z/d 2 ) ≤ 1 √ ab ≤ a+b 2 . With a = log(z/d 1 ) and b = log(z/d 2 ), this gives 2 log z 2 d1d2

□ Theorem 8.2. When z ≥ 1000, we have S ≤ 7 • 10 -7 (log z) 9 + 6 π 2 .

  7 .

	Let us obtain a lower bound for |A|. From Lemma 10.3 and Theorem 1.4, we get
	(26)	2y/9 log y	≤	p≤y

Table 2 :

 2 7 2 • 10 7 2 • 10 7 10 10 10 15 10 20 10 30 10 30 10 9 10 9 5 • 10 8 10 9 possible values in Theorem 13.1.

	C	10 13	3000	1	10 10 10 6	90	10 8	1/1000
	R	10 9	10 10	10 13	10 9

  which we want to be at most 1/42800. The first term is dominant and asks for π2 6 RL ≥ 42800 × 3096225. When log z ≥ 10 35 , the value R = 10 9 is enough. This explains the choice made in Theorem 1.[START_REF] Cohen | Explicit estimates for summatory functions linked to the Möbius µ-function[END_REF]. In general we need to satisfy the inequality

				5/2 ,
	∆ ≤	3096225 ( 6 π 2 L + 1.166) RL 2	+	7.44L 2 qC 5/2 2	L 9 10 7 +	6 π 2
	3096225 ( 6 π 2 L + 1.166) RL 2	+	7.44L 2 q 0 C 5/2 7	L 9 10 7 +	6 π 2 ≤	1 42800	L =	1 2	log	C 5/2 q 2 0

π 2 log z + 1.166 T 1/3 T 1/3 T 1/3 H(0)

The first and second authors have been partly supported by the Indo-French Centre for the Promotion of Advanced Research -CEFIPRA, project No 5401-1. The first author acknowledges the financial support by the Indian National Science Academy through a distinguished professorship. The second author was supported by the joint FWF-ANR project Arithrand: FWF: I 4945-N and ANR-20-CE91-0006.

whence, with c = |A|/φ(q), φ(q) ≤ a∈A (U + ξ(a)) ≤ 2.0008 • J|A| + |A| 1/2 a∈A ξ(a) 2 1/2 ≤ cφ(q)2.008J + cφ(q) φ(q) 42500 J 2 ≤ (2.008c + 0.00486 √ c)φ(q)J.

This and (27) imply that c ≥ 0.380. Lemma -o(1), this would guarantee us only two classes in a subgroup of index 5, which is not enough (they could be {0, 1} in (Z/5Z, +), whose three-fold sum does not cover Z/5Z). We need to go simply beyond 2/5 but we do not need to increase the exponent, since a bound of the shape 0.4 + ϵ(q) for some positive ϵ(q) is enough, even if ϵ(q) tends to 0, and this is exacty what Lemma 10.2 gives us. On reasoning as in [START_REF] Ramaré | Products of primes in arithmetic progressions[END_REF], we get λ ≥ 3 which is enough to conclude this proof. □

Some computations for small values of the modulus

For a modulus q, let P (q) be the largest over the invertible residue class a modulo q, of the smallest prime congruent to a modulo q. The paper [START_REF] Li | A lower bound for the least prime in an arithmetic progression[END_REF] contains in Appendix A the report of some numerical computations that implies that P (q) ≤ 2.2q(log q) 2 when q ≤ 10 6 .

Our problem is somewhat distinct, and we consider three situations.

12.1. Products of two primes below q. Let P 2 (q) be the smallest X of the largest over the invertible residue class a modulo q that are product of two primes, each prime being at most X in size. A brute force Pari/GP script simply producing products of two primes and collecting the classes obtained yields the next lemma.

Lemma 12.1. For every q ∈ [402, 50 000], we have P 2 (q) ≤ q. The class 385 modulo the prime 401 does not contain any product of two primes, each being below 400. When q ∈ [3404, 50 000], we have P 2 (q) ≤ q/2. When q ∈ [11 742, 50 000], we have P 2 (q) ≤ q/3. When q ∈ [35 072, 50 000], we have P 2 (q) ≤ q/4.

The reader should notice that every time we decrease the bound we aim for (hence aiming at a better theoretical result), we shorten the computation. As the bad cases are rare enough, we first aim at q/5 for instance when q ≥ 20 000 and, if it does not work, we try q/4 and so on. A conjecture of Erdős recalled in [6, Section 2] says that, when q > q 0 for some q 0 , every invertible class modulo q contains a product of two primes, each of which is of size at most q. The above lemma hints that one can maybe take q 0 = 401. 12.2. Products of three primes below q. A Pari/GP script simply producing products of three primes and collecting the classes obtained yields the initial step of our ladder.


Evelyne Benoit

Aurélie Couesnon

Jirí Lindovsky

Bogdan I Iorga

Armen Zakarian

Denis Servent

Jordi Molgó
email: jordi.molgo@inaf.cnrs-gif.fr

In vivo and in vitro pinnatoxins A and G reversibly block

Keywords: pinnatoxin A, pinnatoxin G, neuromuscular system, in vivo, muscle contraction, synaptic transmission, nicotinic acetylcholine receptors

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

In vivo and in vitro pinnatoxins A and G reversibly block transmission at the skeletal neuromuscular junction

Evelyne Benoit, Aurélie Couesnon, Jiri Lindovsky, Bogdan Iorga, Armen The dinoflagellate Vulcanodinium rugosum, first isolated from Ingril, a French Mediterranean lagoon, is known to produce the pinnatoxins (PnTXs) and the portimines. PnTXs (A-H) constitute an emerging family of phycotoxins belonging to the cyclic imine group. Interest has been focused on these fast-acting highly-potent toxins because they are widely found in contaminated shellfish. Despite their highly complex molecular structure, PnTXs have been chemically synthetized by the Zakarian's group, and demonstrated to act on various nicotinic acetylcholine receptors (nAChRs). To the best of our knowledge, neither PnTX-A nor PnTX-G and analogs, obtained by chemical synthesis with high degree of purity (> 98%), have been studied in vivo or in vitro on adult mouse and isolated nerve-muscle preparations expressing the mature muscletype (a1)2b1de nAChR. Our results show that PnTX-A and PnTX-G acted on the neuromuscular system of anesthetized mice and blocked the compound muscle action potential (CMAP) in a dose-and time-dependent manner with similar ID50 values (dose required to block 50% of the CMAP), as determined using an in vivo minimally invasive electrophysiological method. The decrease of CMAP induced by both toxins in vivo was reversible within 6-8 h. PnTX-A and PnTX-G, applied to isolated extensor digitorum longus (EDL) nerve-muscle preparations, blocked reversibly isometric twitches evoked by nerve stimulation. Both toxins exerted no direct action on the contractile machinery of muscle fibers, as revealed by direct muscle stimulation. In addition, PnTX-A and PnTX-G blocked synaptic transmission at mouse neuromuscular junctions. PnTX-A aminoketone analog (containing an open form of the imine ring) had no effect on neuromuscular transmission. These results indicate the importance of the cyclic imine for interacting with adult mammalian muscle-type nAChR. Supported in part by NIH/NIGMS grant GM R01-077379 (to A.Z.) and by the CNRS/CEA.

  Zakarian, Denis Servent, Jordi Molgó To cite this version: Evelyne Benoit, Aurélie Couesnon, Jiri Lindovsky, Bogdan Iorga, Armen Zakarian, et al.. In vivo and in vitro pinnatoxins A and G reversibly block transmission at the skeletal neuromuscular junction. PHYCOTOX 2019 -GDR Annual Conference on Toxic Microalgae, May 2019, Plouzané, France. . hal-04467214


Ramachandran Balasubramanian

Olivier Ramaré
email: olivier.ramare@univ-amu.fr

Priyamvad Srivastav
email: priyamvads@imsc.res.in

Footnote-Asymptotic-06-IJNT Product of three primes in large arithmetic progressions

Keywords: Mathematics Subject Classification 2010: 11N13, 11A41, Secondary: 11N37, 11B13 Primes in arithmetic progressions, Least prime quadratic residue, Linnik's Theorem

For any ϵ > 0, there exists q 0 (ϵ) such for any q ≥ q 0 (ϵ) and any invertible residue class a modulo q, there exists a natural number that is congruent to a modulo q and that is the product of exactly three primes, all of which are below q 3 2 +ϵ . If we restrict our attention to odd moduli q that do not have prime factors congruent to 1 mod 4, we can find such primes below q 11 8 +ϵ . If we further restrict our set of moduli to prime q that are such that (q -1, 4

we can find such primes below q 6 5 +ϵ . Finally, for any ϵ > 0, there exists q 0 (ϵ) such that when q ≥ q 0 (ϵ), there exists a natural number that is congruent to a modulo q and that is the product of exactly four primes, all of which are below q(log q) 6 .

Introduction and results

In this paper we investigate the representation of reduced residue classes modulo q by a product of exactly three small primes, and exceptionally by four of them in Theorem 1.4. We develop the approach initiated in [START_REF] Ramaré | Products of primes in arithmetic progressions: a footnote in parity breaking[END_REF], and followed up in [START_REF] Ramaré | Products of primes in arithmetic progressions[END_REF], borrowing several results from the latter paper.

We input three new arguments: some vertical Brun-Titchmarsh inequalities (e.g. Theorems 5.1 and 6.1), the usage of P 2 -numbers, see Theorem 3.2 and some additive combinatorics of sum-free sets in Section 4.

When using Kneser's theorem, we encounter two hurdles: the need to prove that the set of classes of small primes modulo q is dense enough, this is the job of the different versions of the Brun-Titchmarsh inequalities we employ, and the need to show that these primes do not stay in some union of cosets of some subgroup of small index in (Z/qZ) × . By following the strategy of P.D.T.A. Elliott in [START_REF] Elliott | The least prime k -th-power residue[END_REF], we prove that subgroups of index 5 contain small primes (we prove more, see Theorem 2.4). Finally Theorem 3.2 asserts that every coset of a small index subgroup contains either a small prime or a product of two of them. This is a consequence of the weighted sieve when using the approach we already put to work for the coset Brun-Titchmarsh inequality in [START_REF] Ramaré | Products of primes in arithmetic progressions[END_REF]. The surprise is that, though we seem to be using the same kind of sieve argument as when bounding the density from above, the additive consequences are distinct. The additive combinatorial problem that emerges is investigated in Section 4. It relies on the combinatorics of sum-free sets.

Theorem 1.1. Let ϵ > 0. There exists q 0 such that for all q ≥ q 0 and for all invertible residue classes a modulo q, there exists an integer congruent to a modulo q that is the product of exactly three primes, all of which are below q 3 2 +ϵ . When q is cube-free, we can find such primes below q 4 3 +ϵ .

The main interest in the above result is that 3 2 < 2 while it is unknown whether there is such a small prime in any given arithmetic progression modulo q, the best bound for Linnik's constant under the Generalized Riemann Hypothesis being 2+ϵ.

We encounter two obstructions during the proof: the parity phenomenom and the large subgroups problem (arising from the usage of Kneser's theorem). We can avoid the second one by specializing the modulus q to a well-behaved family.

Theorem 1.2. Let ϵ > 0. There exists q 0 such that for every modulus q ≥ q 0 all whose prime factors are congruent to 3 modulo 4, and for all invertible residue classes a modulo q, there exists an integer congruent to a modulo q that is the product of exactly three primes, all of which are below q 11 8 +ϵ .

The same applies to integers q of the form q = 4q ′ or q = 8q ′ when all the prime factors of q ′ are congruent to 3 modulo 4. Notice for comparison that 11/8 = 1.375. We can reach a smaller exponent for a general modulus by taking products of four primes, rather than of three.

Theorem 1.4. There exist q 0 such that for all modulus q ≥ q 0 and for all invertible residue classes a modulo q, there exists an integer congruent to a modulo p that is the product of exactly four primes, all of which are below q(log q) 6 .

In [START_REF] Erdős | On the residues of products of prime numbers[END_REF], P. Erdős, A. Odlyzko and A. Sárközy proved that under the Generalized Riemann Hypothesis, we can find such a product of only two primes, and that under a weaker but still unproven hypothesis, we can find such a product of three primes. It is unclear to us how their method would work for products of four primes in case of the presence of a Siegel zero.

Thanks are due to the referee for his/her careful reading of this paper.

Primes in large subgroups modulo q

Lemma 2.1.

• Given ϵ > 0, there exists c(ϵ) > 0 such that, for all real characters χ modulo q, we have |L(1, χ)| > c(ϵ) q -ϵ . • There exists a constant c > 0, such that for all complex characters χ modulo q, we have |L(1, χ)| ≥ c/ log q.

Lemma 2.2 (Burgess). Let χ be a non-trivial character to modulus q. Then for all X, H ≥ 1, and for all r ∈ {1, 2, 3}, we have the following: Given ϵ > 0, there exists c(ϵ), such that

X<n≤X+H χ(n) ≤ c(ϵ)H 1-1 r q r+1 4r 2 +ϵ .
Further, if q is cube-free, one can take r to be any natural number.

The following is a consequence of the Burgess bounds.

Lemma 2.3. For every character modulo q, we have

• If y ≥ q 1/3+ϵ , there is a δ > 0 such that n≤y χ(n) n = L(1, χ) + O(q -δ ).
The factor 1/3 can be replaced by 1/4 when q is cube-free.

August 10, 2022 9:38 Footnote-Asymptotic-06-IJNT Product of three primes in large arithmetic progressions 5

• Let r ∈ {1, 2, 3} and suppose that 0 < σ < 1 -1/r. Then

n≤y χ(n) n s ≪ y 1-σ-1 r 1 -σ -1/r q r+1 4r 2 +ϵ |s|.
Again, we can take any r ≥ 1 when q is cubefree.

Theorem 2.4. Let q be sufficiently large and H ⊆ G q = (Z/qZ) * be a subgroup of index Y . Then, there exists a prime p ≤ c 0 (ϵ, Y ) • q Y -1

3 +ϵ 0 , such that p(mod q) ∈ H. Further, if q is cube-free, one can replace the exponent (Y -1)/3 by (Y -1)/4.

In [START_REF] Elliott | The least prime k -th-power residue[END_REF], P.D.T.A. Elliott proved the same result when H is the set of invertible Yth powers modulo prime q. Our proof follows along the similar lines. When Y = 2, the paper [START_REF] Vinogradov | Hypoelliptic curves and the least prime quadratic residue[END_REF] of A.I. Vinogradov & Y. Linnik tells us that there is a prime ≪ q 1/4+ε in a quadratic subgroup modulo q when q is prime, a condition that has been removed by P. Pollack in [START_REF] Pollack | The smallest prime that splits completely in an abelian number field[END_REF]. In the case Y ∈ {3, 4} and q is prime, pertinent bounds may be found in [START_REF] Nagell | Sur les restes et les non-restes cubiques[END_REF] by T. Nagell and [START_REF] Benli | Small prime kth power residues for k = 2, 3, 4: a reciprocity laws approach[END_REF] by B. Kübra and P. Pollack.

Remark 2.1. To be more precise, the bound we obtain in Theorem 2.4 is of the

form c 1 (ϵ) • Y 3 q 1/3+ϵ 0 Y -1 .
To unfold the proof, we need to introduce the Dirichlet series given in (2.6), and this requires some preliminaries. The subgroup {χ ∈ Ĝq : χ| H = 1} may be identified with characters on G q /H. We further set K = G q /H. Let x > 1 be such that none of the primes p ≤ x falls into the subgroup H modulo q,

We define a multiplicative function g(n)as follows. Let

g(p) = 1 Y χ∈ K χ(p) = 1, p ∈ H, 0, otherwise, (2.1)
and g(p α ) = 0 for all primes p and α ≥ 2. Our hypothesis on x implies that g(p) = 0, for all primes p ≤ x.

(2.2)

We let g(1) = 1. The Dirichlet series of g(n) is given by

f (s) = ∞ n=1 g(n) n s = p 1 + g(p) p s = p   1 + 1 Y χ∈ K χ(p) p s   . (2.3)
We find that

f (s) Y = ω(s) χ∈ K L(s, χ),
where ω(s) is Dirichlet series that is analytic for σ > 1/2. In fact

ω(s) = p   1 + g(p) p s Y χ∈ K 1 - χ(p) p s   . (2.4) Let g = g * • • • * g Y times , so that f (s) Y = n g(n) n s . (2.5)
From (2.2), it follows that g(p) = 0 for all primes p ≤ x and therefore g(n) = 0 for all 1 < n ≤ x, except for g(1) = 1.

We now aim to obtain an asymptotic formula for the partial sums related to g(n) using the Perron's formula. Since we are only interested in the sum of g(n) with n not exceeding x, we find it convenient to consider the Dirichlet series obtained by truncating the L-functions at the parameter x (rather than considering f (s) Y )

F (s) = ω(s)L(s, χ 0,q )(s) χ∈ K χ̸ =χ0   n≤x χ(n) n s   . (2.6)
With this notation in hand, we may unfold our series of lemmas.

Lemma 2.5. For 1/2 < σ ≤ 1, we have ζ(2σ) -2Y ≤ |ω(s)| ≤ ζ(2σ) 2Y .
Proof. We have

log ω(s) = Y p log 1 + g(p) p s + χ∈ K p log 1 - χ(p) p s = Y ∞ j=1 (-1) j-1 j p g(p) j p js - ∞ j=1 1 j p 1 p js χ∈ K χ(p) j .
The contribution from j = 1 cancels out. Now, use the fact that g(p) and χ(p) are bounded by 1, to obtain

| log ω(s)| ≤ 2Y ∞ j=2 1 j p 1 p jσ ≤ 2Y ∞ j=1 1 2j p 1 p 2σj + 1 2j + 1 p 1 p σ(2j+1) ≤ 2Y log ζ(2σ). Lemma 2.6. Let s = σ + it. When 1/2 < σ = ℜs < 2/3, we have F (s) ≪ ζ 2 (2σ) x 2/3-σ 2/3 -σ q 1/9+ϵ 0 Y -1 (1 + |t|) Y -1 2 .
Proof. Using Lemma 2.3(b) with r = 3 and the bound

|L(s, χ 0,q )(s)| ≪ q ϵ 0 |t| 1-σ 2
≪ q ϵ 0 |t| 1/2 , as well as the bound for ω(s) from Lemma 2.5, we find that

F (s) ≪ ζ 2 (2σ) x 2/3-σ 2/3 -σ q 1/9+ϵ 0 Y -1 (1 + |t|) Y -1 2 .
Product of three primes in large arithmetic progressions 7

The proof of the lemma is complete.

Proof of Theorem 2.4. Let g = g * • • • * g Y times
be as in (2.5). We have seen that g(1) = 1 and g(n) = 0 for all 1 < n ≤ x owing to the hypothesis (2.2). Therefore

S = 1 ℓ! n≤x g(n) log x n ℓ = (log x) ℓ ℓ! , (2.7)
for any integer ℓ ≥ 0.

On the other hand, we use the following version of Perron's formula (assume y ̸ = 1 and c > 1):

1 2πi c+i∞ c-i∞ y s s ℓ+1 ds =    (log y) ℓ ℓ! , y > 1, 0, otherwise.
As a result and with ℓ = Y + 1, we find that

S = 1 2πi 2+i∞ 2-i∞ F (s) x s s ℓ+1 ds.
Moving the line of integration to ℜ(s) = σ (1/2 < σ < 2/3) and collecting the residue at s = 1, we get

S = Res s=1 F (s) x s s ℓ+1 + 1 2iπ ℜ(s)=σ F (s)
x s s ℓ+1 ds.

(2.8)

The main term above is controlled by Lemma 2.1:

Res s=1 F (s) x s s ℓ+1 = xω(1) φ(q) q χ∈ K χ̸ =χ0,q   n≤x χ(n) n   ≫ x ζ(2) -2Y log log q χ∈ K χ̸ =χ0q L(1, χ) + O(q -δ ) ≫ xq -ϵ ,
where we have used φ(q) q ≫ 1 log log q and the lower bound for L(1, χ) from Lemma 2.1. The implied constant depends on Y and ϵ. Choose

σ = 2/3 -δ, with δ = 1 log q .
(2.9) Using (2.6), the second term in (2.8) is at most On the other hand, we have from (2.7), that S = (log x) ℓ ℓ!

≪ x 2/3-δ ζ 2 (4/3 -2δ) δ -1 x δ q 1/9+ϵ Y -1 ∞ 1 dt |t| 3/2 ≪ x 2/3+δ(Y -2) 13 δ -1 q 1/9+ϵ Y -1 ≪ x 2/3+ Y log q 0 13q 1/9+ϵ log q Y -1 ≪ xq -2ϵ , August
= (log x) Y +1 (Y +1)! ≪ x ϵ , whenever Y = o(log x) (which is true since Y log x ≪ 1 log q )
. This leads to a contradiction and completes the proof.

Almost primes in cosets of large subgroups modulo q

Lemma 3.1 (Heath-Brown [START_REF] Heath-Brown | Hybrid bounds for Dirichlet L-functions[END_REF], Petrow & Young [START_REF] Petrow | The weyl bound for dirichlet l-functions of cubefree conductor[END_REF]). Let χ be a Dirichlet character of conductor r > 1. When 1/2 ≤ σ = ℜs, we have

L(s, χ) ≪ ε (r(|t| + 1)) 3(1-σ) + 8
+ε valid for any ε > 0. Here (1 -σ) + = max(0, 1 -σ). When r is cube-free, one may replace 3/8 by 1/3.

Theorem 3.2.

There is a constant C > 0 such that, for every subgroup H of (Z/qZ) × of index Y and every coset b • H, there exists a P 2 -number that is of size not more than C • Y 9/2 q 0.768 , where C is some effective constant. When q is cube-free, this size may be reduced to C • Y 9/2 q 0.683 .

By a "P 2 -number", we mean an integer that has at most two prime factors. In [START_REF] Heath-Brown | Almost-primes in arithmetic progressions and short intervals[END_REF], R. Heath-Brown proves that, for any a prime to q, there is a P 2 -number of size ≪ q 2-0.035 congruent to a modulo q, where the implied constant does not depend on a. We obtain an exponent < 1 for the cosets.

Proof. Let us use again the setting of the previous section. We start with a subgroup H ⊂ G q = (Z/qZ) × of (small) index Y . Consider {χ ∈ Ĝq : χ| H = 1}. This can be identified with characters on K = G q /H. Let b ∈ G q . To find a small P 2number in b • H, we shall be using a special case of the main result of G. Greaves in [START_REF] Greaves | The weighted linear sieve and Selberg's λ 2 -method[END_REF] (or Chapter 5 of [START_REF] Greaves | Sieves in number theory[END_REF]) which we now state. Let A ⊂ [1, X * ] be a subset of integers. Assume that

#{a ∈ A, d divides a} = Xρ(d) d + R(A, d) with ρ(d) = 1 when (d, q) = 1, 0 otherwise. (3.1)
Let y be a level of distribution, i.e. a real number such that

d≤y 3 ω(d) |R(A, d)| ≪ X log 2 X . (3.2)
Then, if X * ≤ y g where g = 2 -0.004456, then there exists a ∈ A having at most two prime factors. Define X * = q φ(q) Y X and

A = a : a ≤ X * , a falls inside b • H . (3.3)
Product of three primes in large arithmetic progressions 9

Let us verify the conditions of the result of Greaves.

We decompose the characteristic function of b • H through multiplicative characters, i.e. we write

1 1 b•H = 1 Y χ∈ K χ(b)χ.
On defining A d (s) = d|n≥1 1 1 A (n)/n s , the truncated Perron summation formula gives us n∈A, d|n

1 = 1 2iπ κ+iT κ-iT A d (s) X * s ds s + O X * log 2 X * dT
provided that 1 ≤ T 2 ≤ X * /d and where κ = 1 + 1/(log X * ). This expands into n∈A, d|n

1 = 1 Y χ∈ K χ(b)χ(d) 1 2iπ κ+iT κ-iT L(s, χ) X * s ds d s s + O X * log 2 X * dT .
We recall Lemma 3.1, and deduce that n∈A, d|n

1 - 1 Y φ(q) q X * d 1 1 (d,q)=1 ≪ X * log 2 X * dT + (qT ) 3/16+ε √ X * √ d .
With R(A, d) defined in (3.1), we deduce from the above that

d≤y 3 ω(d) |R(A, d)| ≪ yX * (T q) 3/16+ε + X * log 9 (yX * ) T (3.4)
for any positive ε. In particular we can choose δ > 0 and take T = Y (log q)(log X * ) 11 together with y = X/(Y 1+3/8 q δ+3/8 ) ≥ 1 and obtain

d≤y 3 ω(d) |R(A, d)| ≪ δ X/(log X) 2 . (3.5)
As a conclusion, we can find a P 2 in A provided that

g = log X * log y ≤ 2 -0.044560 (3.6) i.e. X ≥ Y 11 8
3-0.044560 1-0.044560 q ( 3 8 +δ) 2-0.044560 1-0.044560 . (3.7)

We find that 3 8 × 2-0.044560 1-0.044560 = 0.7674 • • • ≤ 4/5 and 11 8 × 3-0.044560 1-0.044560 = 4.2532 • • • ≤ 9/2. When q is cube-free, we use the refined bound also recalled in Lemma 3.1.

Some additive combinatorics

Our final results involves usage of additive combinatorics, but the additive combinatorics problem we address can be formulated independently. We do so, as it leads to a better understanding of what we do/don't know how to prove.

We thus start with a finite abelian group G written additively. We also recall for completeness that, when A and B are two subsets of some abelian group G, the sum A + B is defined by

A + B = {a + b / a ∈ A, b ∈ B}.
In particular, the number of representations of a given element is not taken into account. We use the shortcuts 2A = A + A and 3A = A + A + A. The stabilizer, say H, of a subset C of G is the subgroup defined by

H = {g ∈ G / ∀c ∈ C, g + c ∈ C}.
Lemma 4.1. A subset C of a finite abelian group is a union of cosets modulo its stabilizer.

Proof. On denoting by H this stabilizer, it is enough to check that, given any element c from C, we indeed have c + H ⊂ C. This follows from the definition of the stabilizer. In group theoretical parlance, C is saturated modulo H. The lemma follows swiftly. Lemma 4.2. Let A be a subset of a finite abelian group and let H be the stabilizer of A + A. Then A + A + A is also a union of cosets modulo H.

Proof. This follows from the equation A +

A + A = A + 2A = A + (2A + H).

Auxiliary lemmas

Lemma 4.3. Let A be a subset of a finite abelian group G. Let H be the stabilizer of A + A. Suppose that A meets λ cosets of H. Then

|A + A| ≥ (2λ -1)|H|.
This is [14, Corollary A.2], a corollary of the famous Kneser's Theorem. While Lemma 4.3 is used when the sets we add have a somewhat small cardinality, the next lemma is tailored for very large sets. For any subgroup H of index Y , assume A meets at least λ(Y ) cosets. Then

A + A + A = G.
As Let us now turn to the non-trivial case Y ≤ 1/(3η -1). By Lemma 4.1, the set 2A is a union of cosets modulo H, and by Lemma 4.3, of at least 2λ -1 of them. This implies that A + A + A contains at least 3λ -2 cosets modulo H. Let us write Y = 3y+a for a ∈ {0, 1, 2}. We have ⌈ηY ⌉ > y+ a 3 , and thus ⌈ηY ⌉ ≥ y+1 = Y 3 + 3-a 3 . This implies that 3λ -2 ≥ Y + 1 -a. When a ∈ {0, 1}, this is at least Y , meaning that A + A + A = G. When Y ≡ 2 [START_REF] Erdős | On the residues of products of prime numbers[END_REF], i.e. when a = 2, and Y ≤ 1/(3η -1), our hypothesis gives us the better bound λ ≥ ⌈ηY ⌉ + 1. This is enough to complete the proof.

Setting the problem and preliminary conclusions

Let A be a subset of G such that

|A| ≥ η|G|, η > 1/3. ( 4.1)
Our problem is to find hypotheses that will lead to the conclusion that 3A = G. Having Lemma 4.3 in mind, we consider the stabilizer H of 2A = A + A. Here are some facts and further definitions:

(1) 2A and 3A are both a union of H-cosets, by Lemma 4.1 and 4.2.

(2) On setting

G * = G/H and A * = A/H, it is enough to show that 3A * = G * .
This is true even if H does not stabilize A, since we readily check that 3A = 3A + H = 3(A + H). As a conclusion of Lemma 4.5 and given η, only a finite number of values of Y , the index of H, are to be considered, and they are all congruent to 2 modulo 3. Once these general considerations are set, let us turn to the hypotheses we are ready to assume. Here are the first two:

[C 0 ] The subset A generates G. This is an obvious hypothesis which is in fact implied by our other assumptions. [C 1 ] The subset A has a non-empty intersection with every coset of any subgroup of index 2.

Here are two additional series of hypotheses we are considering:

[C 2 (Y 0 )] The subset A intersects every subgroup of index at most Y 0 and congruent to 2 mod 3. [C 3 (Y 0 )] Let K be a subgroup of G of index at most Y 0 and congruent to 2 mod 3. The subset A 2A has a non-empty intersection with every coset modulo K.

Please notice that hypothesis [C 2 (Y 0 )] does not ask anything concerning the coset u + K when u / ∈ K, while hypothesis [C 3 (Y 0 )] ensures that an element of A or of 2A belongs to it. Note that the third condition tells us that A * is a sum-free set of the finite abelian group G * . Moreover, the fifth one is a consequence of the first four. Such sets have been studied, for instance in [START_REF] Yap | Maximal sum-free sets in finite abelian groups[END_REF] and in [START_REF] Green | Sum-free sets in abelian groups[END_REF]. We ran some numerical experiments when G * is the cyclic group with ℓ elements say to detect the existence of the second case of the above lemma. We found that the situation is quite rigid but not completely so. Here are some examples:

• A * = {2, 3} mod 5 is our basic example.

• We explored ℓ ≤ 29 with Sage [START_REF] Stein | Sage Mathematics Software (Version 5.9)[END_REF] and here are the size of the sets A * that are possible: which we assume to be non-empty. Let g ∈ Γ. Since g -A * has no intersection with 2A * , it has to be included within A * . But since the cardinalities of A * and of g -A * are the same, we have g -A * = A * . Let g 1 and g 2 be two elements of Γ. We have g 1 -(g 2 -A * ) = (g 1 -g 2 )+A * on the one hand, while g 1 -(g 2 -A * ) = g 1 -A * = A * on the other one. This means that g 1 -g 2 stabilizes A * , hence it stabilizes 2A * , which means that it vanishes. We have thus proved that Γ is reduced to a single point, say g 0 . We have

ℓ
A * ∩ 2A * = g 0 -A * ∩ 2A * = ∅.
We also find that g 0 -2A * = 2A * and that 2A * = (g 0 -A * ) + (g 0 -A * ) = 2g 0 -2A * . This implies that 2A * = g 0 +(g 0 -2A * ) = g 0 +2A * , i.e. that g 0 stabilizes 2A * . It is thus equal to 0, i.e. 3A * = G * \ {0}. Furthermore, Kneser's Theorem (Lemma 4. The previous two papers [START_REF] Ramaré | Products of primes in arithmetic progressions: a footnote in parity breaking[END_REF] and [START_REF] Ramaré | Products of primes in arithmetic progressions[END_REF] relied on this result. Theorem 4.9. Let A ⊂ G be a subset of the finite abelian group G that is such that

|A|/|G| = η > 1/3. Set Y 0 = 1/(3η -1). On assuming [C 0 ], [C 1 ], [C 2 (Y 0 )] and [C 3 (Y 0 )], we have 3A = G.
Remark 4.1. This theorem shows that in our setting when G = (Z/qZ) × and A = {p ≤ q 1+ε , (p, q) = 1}, the Lindelöf hypothesis in q-aspect for the Dirichlet L-functions is enough to obtain the conclusion, as we prove Assumption [C 3 (Y 0 )] in Theorem 3.2, when q is large enough, and the proof of Theorem 2.4 easily gets adapted to show that [C 2 (Y 0 )] also holds, again when q is large enough.

Proof of Theorem 1.2. Again, let P(y) be the set of primes below y that do not divide q and let A be the image of P(y) in G q = (Z/qZ) × . We seek to show that A • A • A = G q . We select X = q 11/8+ϵ . We compute that log(X/q 3/8 ) 2 log X = 4 11 + 12ϵ 121 + 88ϵ .

(5.3)

We proceed as for the proof of Theorem 1.1 with Lemma 5.1. We find that |A| φ(q) > 4/11.

(5.4) Theorem 4.8 applies, the hypotheses again being met by Theorem 2.4 with Y = 2, then with Y = 5 and by Theorem 3.2 for index Y = 5. The special hypothesis concerning the 2-part of A is ensured by the our assumption on q.

Proof of Theorem 1.3. We take X ≥ p Since 1/(3 × 11 32 -1) = 32, the only Y giving trouble are congruent to 2 modulo 3 and ≤ 32. Theorem 4.9 asks for [C 3 (32)], which is granted by Theorem 3.2, and for [C 2 (32)]. We check numerically that this may happen only when Y ∈ {8, 11, 14, 17, 20, 23, 26, 29, 32}. Our hypothesis on p excludes all these cases, as Y has to be a divisor of φ(p) = p -1.

6. Four primes. Proof of Theorem 1.4

Mikawa in [START_REF] Mikawa | On the Brun-Titchmarsh Theorem[END_REF] proved the next result (be careful: on page 31, the theorem is stated with a power (log x) -A but the -sign faded. The correct result is on page 33, line -3). Lemma 6.1 (Mikawa [10]). Let ϵ ′ > 0 and A > 5 be given. For almost all a modulo q ≥ q 0 (ϵ ′ , A), we have π(x; q, a) ≤

(2 + ϵ ′ )x/φ(q) log(x 2/3 /q 1/9 ) , x 6/7 ≤ q ≤ x/(log x) A .

Proof of Theorem 1.4. As in the proof of Theorem 1.1, let P(y) be the set of primes below y that do not divide q and let A be the image of P(y) in G q = (Z/qZ) × .

We seek to show that A•A•A•A = G q . We set X = q(log q) 6 . Hence q ≤ X/(log X) 5 if q is large enough. By Lemma 6.1, we have |A|/φ(q) ≥ log(x 2/3 /q 1/9 ) (2 + ϵ ′ ) log x -ε ≥ 5 log(X log X) 9(2 + ϵ ′ ) log X -ε ≥

Theorem 1 . 3 .

 13 Let ϵ > 0. There exists p 0 such that for every prime p ≥ p 0 such that (p -1, 4• 7 • 11 • 17 • 23 • 29) = 2and for all invertible residue classes a modulo p, there exists an integer congruent to a modulo p that is the product of exactly three primes, all of which are below p 6 5 +ϵ .

1 3

 1 10, 2022 9:38 Footnote-Asymptotic-06-IJNT 8 R. Balasubramanian, O. Ramaré, P. Srivastav as soon as x ≫ q Y -+ϵ . Hence S ≫ xq -ϵ .

Lemma 4 . 4 . 11 Lemma 4 . 5 .

 441145 Let A and B be two subsets of a finite abelian group G satisfying |A| + |B| > |G|. Then A + B = G. This is [14, Lemma 5.1]. August 10, 2022 9:38 Footnote-Asymptotic-06-IJNT Product of three primes in large arithmetic progressions Let A be a subset of a finite abelian group G such that |A| ≥ η|G|, with η > 1/3. Define, for any integer Y , λ(Y ) = ⌈ηY ⌉ + 1 when Y ≡ 2[3] and 2 ≤ Y ≤ 1/(3η -1), ⌈ηY ⌉ otherwise.

( 3 )

 3 Notice that 2A * has a trivial stabilizer in G * . (4) We set Y = |G/H| = |G * | and λ = |A/H| so that |2A * | ≥ 2λ-1 by Lemma 4.3.

Lemma 4 . 6 .

 46 Let A * be a subset of a finite abelian group G * satisfying A * ∪ 2A * = G * and such that the stabilizer of 2A * is {0}. Then either 3A * = G * or we have the five conditions • 0 / ∈ A * and A * = -A * , • The stabilizer of A * is {0}, • A * ∩ 2A * = ∅, • |A * | ≤ (|G * | + 1)/3, • 3A * = G * \ {0}. In any case, when |G * | > 2, we have 4A * = G * .

Proof.

  If 0 ∈ A * , the assumption A * ∪ 2A * = G * readily implies that 3A * = G * . Let us consider Γ = g/(g -A * ) ∩ 2A * = ∅ = G * \ 3A * August 10, 2022 9:38 Footnote-Asymptotic-06-IJNT Product of three primes in large arithmetic progressions 13

  3 is enough) tells us that |2A * | ≥ 2|A * | -1, and since |A * | + |2A * | = |G * |, we get |A * | ≤ (|G * | + 1)/3. This upper bound also implies that 2|2A * | ≥ 2(2|G * | -1)/3 > |G * | when |G * | > 2.

4. 3 .

 3 ResultsTheorem 4.7. Let A ⊂ G be a subset of the finite abelian group G that is such that |A|/|G| > 2/5. On assuming [C 0 ] and [C 1 ], we have 3A = G.

Proof.

  Let us set η = |A|/|G|. As 1/(3η -1) is less than 5, Lemma 4.5 tells us that only subgroups of index 2 may give rise to a difficulty, but this is avoided by [C 0 ] and [C 1 ]. Theorem 4.8. Let A ⊂ G be a subset of the finite abelian group G that is such that |A|/|G| > 3/8. On assuming [C 0 ], [C 1 ], [C 2 (5)] and [C 3 (5)], we have 3A = G. This is the main novelty of the present paper on the additive combinatorics side. Proof. Let us set η = |A|/|G|. As 1/(3η -1) is less than 8, Lemma 4.5 tells us that only subgroups of index 2 or 5 may give a difficulty. The case Y = 2 is ruled out by [C 0 ] and [C 1 ]. In case Y = 5, by [C 3 (5)], Lemma 4.6 applies. It tells us that H A = ∅, which is assumed to be false by [C 2 (5)].

6 5

 6 +ϵ and p large enough in terms of ϵ. We find thatη = |A|/φ(p) > 11 32.

5 18 -

 18 O(ε) ≥ 0.2777 since 5/18 = 0.2777 . . . and by selecting ϵ sufficiently small. Let H be the stabilizer of A • A, with index Y and define |A/H| = n ≥ ⌈0.2777 • Y ⌉. By using Lemma 4.3,

  |A|/|H| ≥ ηY , the subset A always meets at least ⌈ηY ⌉ cosets modulo H.

Proof. Let H be the stabilizer of 2A. By Lemmas 4.3 and 4.4, we have 3A = G as soon as |A| + |A + A| > |G|, hence as soon as

|A| + (2λ -1)|H| > |G|.

Since |A|/H ≥ ηY , this is certainly true if ηY + 2λ -1 > Y , and, since λ ≥ ηY , this holds when Y > 1/(3η -1). This explains the change of definition of λ(Y ) according to whether Y is smaller or larger than 1/(3η -1). When Y is larger, we only use the rather trivial value λ(Y ) = ⌈ηY ⌉.

R. Balasubramanian, O. Ramaré, P. Srivastav

R. Balasubramanian, O. Ramaré, P. Srivastav

The first and second authors have been partly supported by the Indo-French Centre for the Promotion of Advanced Research -CEFIPRA, project No 5401-1. The first author acknowledges the financial support by the Indian National Science Academy through a distinguished professorship. The second author was supported by the joint FWF-ANR project Arithrand: FWF: I 4945-N and ANR-20-CE91-0006.

Proof. The proof of Theorem 4.8 is immediately adapted to this case.

The above results can be sharpened when looking more closely at the structure of small examples. Here is such a sharpening. Theorem 4.10. Let A ⊂ G be a subset of the finite abelian group G that is such that |A|/|G| = η > 4/11. On assuming [START_REF] Heath-Brown | Hybrid bounds for Dirichlet L-functions[END_REF]] and that the 2-part of G is isomorphic to (Z/2Z) r for some r ≥ 0, we have 3A = G.

Proof. We adapt the proof of Theorem 4.9 and readily discover that we only have to worry about the case Y = 8. Our assumption imples that G * = G/H is isomorphic to (Z/2Z) 3 . By Lemma 4.6, we may have difficulties when A * = A/H has cardinality 3. But since A * generates G * that may be viewed as a vector space of dimension 3, A * is thus a basis of G * , which would contradict the fact that

5. Three primes. Proof of Theorems 1.1, 1.2 and 1.3 By using the techniques of Iwaniec in [9, Section 2] (as noted by H. Mikawa in [START_REF] Mikawa | On the Brun-Titchmarsh Theorem[END_REF]), one can prove the next lemma.

Lemma 5.1 (Iwaniec [9]). Let ε ∈ (0, 1/200) and ϵ ′ > 0 be given. For almost all a modulo q ≥ q 0 (ε, ϵ ′ ) and q 6 5 +ε ≤ X, we have π(x; q, a) ≤ 2(1 + ϵ ′ )X/φ(q) log(X/q 3/8 ) .

Proof of Theorem 1.1. Let P(y) be the set of primes below y that do not divide q and let A be the image of P(y) in G q = (Z/qZ) × . We seek to show that A•A•A = G q .

We select X = q 3/2+ϵ . We compute that log(X/q 3/8 ) 2 log X = 3 8 + ϵ 12 + 8ϵ .

(5.1)

We use Lemma 5.1. Outside of a set of density ϵ ′′ , we have the stated inequality from which we infer find that

on selecting ϵ ′ and ϵ ′′ properly. To be precise, on assuming ϵ ≤ 1 and ϵ ′ ≤ 1/2, we find that 3

We select ϵ ′ = ϵ ′′ = ϵ/100. Theorem 4.9 applies, the hypotheses being met by Theorem 2.4 with Y = 2, then with Y = 5, and by Theorem 3.2 for index Y = 5.

we get