Alexander Gasnikov
email: gasnikov@yandex.ru

Pavel Dvurechensky
email: pavel.dvurechensky@gmail.com

Eduard Gorbunov
email: eduard.gorbunov@phystech.edu

Evgeniya Vorontsova
email: vorontsovaea@gmail.com

Daniil Selikhanovych
email: selihanovich.do@phystech.edu

César A Uribe
email: cauribe@mit.edu

C A Gasnikov

Optimal Tensor Methods in Smooth Convex and Uniformly Convex Optimization

Keywords: Convex optimization, unconstrained minimization, tensor methods, worst-case complexity, global complexity bounds, condition number

come   L'archive ouverte pluridisciplinaire

Introduction

In this paper, we consider the unconstrained convex optimization problem

f (x) → min x∈R n , (1)
where f has p-th Lipschitz-continuous derivative with constant M p . For p = 1, first-order methods are commonly used to solve this problem, i.e., gradient descent. The lower bound for the complexity of these methods was proposed in [START_REF] Nemirovsky | Problem Complexity and Method Efficiency in Optimization[END_REF][START_REF] Nesterov | Introductory Lectures on Convex Optimization: a basic course[END_REF], and an optimal method was introduced in [START_REF] Nesterov | A method of solving a convex programming problem with convergence rate o(1/k 2 )[END_REF]. The case of p = 2, i.e., Newton-type methods, was well understood only recently. A nearly optimal method was proposed in [START_REF] Yu | Accelerating the cubic regularization of newton's method on convex problems[END_REF], an optimal method was proposed in [START_REF] Monteiro | An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods[END_REF], and a lower bound was obtained in [START_REF] Agarwal | Lower bounds for higher-order convex optimization[END_REF][START_REF] Arjevani | Oracle complexity of second-order methods for smooth convex optimization[END_REF]. The idea of using higher order derivatives (starting from p ≥ 3) in optimization is known at least since 1970's, see [START_REF] Hoffmann | Higher-order necessary conditions in abstract mathematical programming[END_REF]. Recently this direction of research became of interest from the point of view of complexity bounds. In the unpublished preprint [START_REF] Baes | Estimate sequence methods:extensions and approximations[END_REF], extending the estimating functions technique of [START_REF] Nesterov | Introductory Lectures on Convex Optimization: a basic course[END_REF], proposes accelerated high-order (tensor) methods for convex problems with complexity O

MpR p+1 ε 1 p+1
, where p ≥ 1, ε is the accuracy of the obtained solution x, i.e., f (x)f * ≤ ε, M p is the Lipschitz constant of the p-th derivative, and R is an estimate for the distance between a starting point and the closest solution. Nevertheless, the author doubts that the obtained methods are implementable since the auxiliary problem on each iteration is possibly non-convex. [START_REF] Agarwal | Lower bounds for higher-order convex optimization[END_REF]; [START_REF] Arjevani | Oracle complexity of second-order methods for smooth convex optimization[END_REF] construct lower complexity bounds O respectively for the case f having Lipschitz p-th derivative and conjecture that the upper bound can be improved. [START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF] proposes implementable tensor methods showing that an appropriately regularized Taylor expansion of a convex function is again a convex function, thus making auxiliary problems on each iteration of the tensor methods tractable. The author also provides an accelerated scheme with complexity bound O

MpR p+1 ε 1 p+1
, shows that the complexity of each iteration for p = 3 is of the same order as for the case p = 2, and conjectures the existence of an optimal scheme with complexity bound O

MpR p+1 ε 2 3p+1
.

The optimal method for the case p = 1 has complexity O [START_REF] Nesterov | A method of solving a convex programming problem with convergence rate o(1/k 2 )[END_REF] and [START_REF] Monteiro | An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods[END_REF], but the question of existence of optimal methods for p ≥ 3 remains open. In this paper we extend the framework of [START_REF] Monteiro | An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods[END_REF] and propose optimal tensor methods for all p ≥ 1. Our approach is also based on regularized Taylor step of [START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF], and, thus, our optimal method for p = 2 is different from [START_REF] Monteiro | An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods[END_REF].

M 1 R 2 ε 1 2
for p = 2 has the complexity O M 2 R 3 ε 2 7
We also consider problem (1) under additional assumption that f is uniformly convex, i.e., there exist 2 ≤ q ≤ p + 1 and σ q > 0 s.t.

f (y) ≥ f (x) + ∇f (x), y -x + σ q q y -x q 2 , ∀x, y ∈ Q.
Under this additional assumption, we show, how the restart technique can be applied to accelerate our method to obtain complexity

O M p σ p+1 2 3p+1 log 2 ∆ 0 ε , q = p + 1; O      M p (∆ 0 ) p+1-q q σ p+1 q q   2 3p+1 + log 2 ∆ 0 ε    , q < p + 1,
where f (x 0 )f * ≤ ∆ 0 . This bound suggests a natural generalization of first-and second-order condition number [START_REF] Yu | Accelerating the cubic regularization of newton's method on convex problems[END_REF]. If f is such that q = p+1, then the complexity of our algorithm depends only logarithmically on the starting point and is proportional to

(γ p ) 2 3p+1 ,
where γ p = Mp σ p+1 is the p-th order condition number. [START_REF] Nemirovsky | Problem Complexity and Method Efficiency in Optimization[END_REF]; [START_REF] Nesterov | Introductory Lectures on Convex Optimization: a basic course[END_REF] and [START_REF] Arjevani | Oracle complexity of second-order methods for smooth convex optimization[END_REF] propose lower bounds for particular cases of strongly convex functions (i.e., q = 2) with p = 1 and p = 2 respectively. Our upper bounds match them.

As a related work, we also mention [START_REF] Birgin | Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models[END_REF]; [START_REF] Cartis | Improved second-order evaluation complexity for unconstrained nonlinear optimization using high-order regularized models[END_REF], who study complexity bounds for tensor methods for finding approximate stationary points with the main focus on non-convex optimization, which we do not consider in our work. Also the work in [START_REF] Wibisono | A variational perspective on accelerated methods in optimization[END_REF] considers tensor methods from the variational perspective and obtains similar bounds to those in [START_REF] Baes | Estimate sequence methods:extensions and approximations[END_REF]. The first version of this paper appeared in arXiv on September 2, 2018. In December 2018, two months after that, [START_REF] Jiang | An optimal high-order tensor method for convex optimization[END_REF]; [START_REF] Bubeck | Near-optimal method for highly smooth convex optimization[END_REF] proposed an algorithm, which is very similar to our Algorithm 1. Unlike them, we also analyze the case of uniformly convex functions and propose an algorithm, which is faster in this case, see our Algorithm 3. Moreover, we are the first to make a numerical study of tensor methods for p = 3 and show that they work in practice.

Our contributions.

• We propose a new optimal tensor method and analyze its iteration complexity.

• We generalize this method for the case of uniformly convex objectives and propose a definition of p-th order condition number.

• We make a numerical study of the proposed method and show that our optimal method is faster than accelerated tensor method [START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF] in practice. We also compare the performance of tensor methods for p = 2 and p = 3 and show that the 3rd-order method is superior to the 2nd-order method in practice.

Notations and generalities. For p ≥ 1, we denote by ∇ p f (x)[h 1 , ..., h p ] the directional derivative of function f at x along directions h i ∈ R n , i = 1, ..., p. ∇ p f (x)[h 1 , ..., h p ] is symmetric p-linear form and its norm is defined as

∇ p f (x) 2 = max h 1 ,...,hp∈R n {∇ p f (x)[h 1 , ..., h p ] : h i 2 ≤ 1, i = 1, ..., p}
or equivalently

∇ p f (x) 2 = max h∈R n {|∇ p f (x)[h, ..., h]| : h 2 ≤ 1, i = 1, ..., p}.
Here, for simplicity, • 2 is standard Euclidean norm, but our algorithm and derivations can be generalized for the Euclidean norm given by general a positive semi-definite matrix B. We consider convex, p times differentiable on R functions satisfying Lipschitz condition for p-th derivative

∇ p f (x) -∇ p f (y) 2 ≤ M p x -y 2 , x, y ∈ R n .
(2)

Optimal Tensor Method

Given a function f , numbers p ≥ 1 and M ≥ 0, define

T f p,M (x) ∈ Arg min y∈R n    p r=0 1 r! ∇ r f (x) [y -x, ..., y -x] r + M (p + 1)! y -x p+1 2    . ( 3
)
and given a number L ≥ 0 and point z ∈ R n , we define

F L,z (x) f (x) + L 2 x -z 2 2 . (4) Theorem 1 Let sequence (x k , y k , u k ), k ≥ 0 be generated by Algorithm 1. Then f (y N ) -f * ≤ cM p y 0 -x * p+1 2 N 3p+1 2 , c = 2 3(p+1) 2 +4 4 (p + 1) p! .
Note that this bound allows to obtain an O

MpR p+1 ε 2 3p+1
iteration complexity. The implementability and cost of each iteration is discussed below in Section 2.3. The proof of Theorem 1 is based on the framework of [START_REF] Monteiro | An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods[END_REF], which is presented in the next subsection.

Algorithm 1 Optimal Tensor Method

Input: u 0 , y 0 -starting points; N -iteration number;

A 0 = 0 Output: y N 1: for k = 0, 1, 2, . . . , N -1 do 2: Choose L k such that 1 2 ≤ 2(p + 1)M p p!L k y k+1 -x k p-1 2 ≤ 1, (5)
where

a k+1 = 1/L k + 1 L 2 k + 4A k /L k 2 , A k+1 = A k + a k+1 , {note that L k a 2 k = A k+1 } x k = A k A k+1 y k + a k+1 A k+1 u k , y k+1 = T F L k ,x k p,pMp (x k ).
3:

u k+1 = u k -a k+1 ∇f (y k+1
) 4: end for 5: return y N 2.1. Accelerated hybrid proximal extragradient method [START_REF] Monteiro | An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods[END_REF] introduced Algorithm 2 for convex optimization problems. To find y k+1 on each iteration, the authors use gradient type method for the case p = 1 and a trust region Newton-type method for the case p = 2. Their analysis of the algorithm is based on the following Theorem.

Theorem 2 ( (Monteiro and Svaiter, 2013, Theorem 3.6 ) ) Let sequence (x k , y k , u k ), k ≥ 0 be generated by Algorithm 2 and define R := y 0x * 2 . Then, for all N ≥ 0,

1 2 u N -x * 2 2 + A N • f y N -f (x * ) + 1 4 N k=1 A k L k-1 y k -x k-1 2 2 ≤ R 2 2 , ( 6
)
f y N -f (x * ) ≤ R 2 2A N , u N -x * 2 ≤ R, (7)
N k=1 A k L k-1 y k -x k-1 2 2 ≤ 2R 2 . ( 8
)
We also need the following Lemma.

Lemma 3 ( (Monteiro and Svaiter, 2013, Lemma 3.7 a))) Let sequences {A k , L k }, k ≥ 0 be generated by Algorithm 2. Then, for all N ≥ 0,

A N ≥ 1 4 N k=1 1 L k-1 2 . ( 9
)
Algorithm 2 Accelerated hybrid proximal extragradient method Input: u 0 , y 0 -starting point; N -iteration number; A 0 = 0 Output:

y N 1: for k = 0, 1, 2, . . . , N -1 do 2: Choose L k and y k+1 s.t. ∇F L k ,x k y k+1 2 ≤ L k 2 y k+1 -x k 2 ,
where

a k+1 = 1/L k + 1 L 2 k + 4A k /L k 2 , A k+1 = A k + a k+1 , x k = A k A k+1 y k + a k+1 A k+1 u k .
3: [START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF], Lemma 1),

u k+1 = u k -a k+1 ∇f y k+1 . 4: end for 5: return y N 2.2. Proof of Theorem 1 It follows from Algorithm 1 that y k+1 = T F L k ,x k p,pMp (x k ), thus by
∇F L k ,x k y k+1 2 ≤ (p + 1) M p p! y k+1 -x k p 2 .
At the same time, by the condition in step 2 of Algorithm, 1,

2(p + 1)M p p!L k y k+1 -x k p-1 2 1.
Hence,

∇F L k ,x k y k+1 2 ≤ L k 2 y k+1 -x k 2
and we can apply the framework of the previous subsection. What remains is to estimate the growth of A N , which is our next step. By the condition in step 2 of Algorithm, 1,

1 L k y k+1 -x k p-1 2 ≥ θ, (10)
where θ = p! 4(p+1)Mp . Using this inequality, we prove that

N k=1 A k L p+1 p-1 k-1 ≤ 2R 2 θ -2 p-1 . (11)
Indeed, from ( 8) and ( 10) we have that

θ 2 p-1 N k=1 A k L p+1 p-1 k-1 ≤ N k=1 A k L 1+ 2 p-1 k-1 1 L k-1 y k -x k-1 p-1 2 2 p-1 = N k=1 A k L k-1 y k -x k-1 2 2 ≤ 2R 2 . ( 12
)
Further, from (11) it follows that

N k=1 1 L k-1 ≥ θ 1 p+1 (2R 2 ) p-1 2(p+1) N k=1 A p-1 3p+1 k 3p+1 2(p+1) . ( 13
)
To prove that, let us introduce new variables z k = 1 L k-1 and consider the following optimization problem to find the worst possble value of the l.h.s. in ( 13)

min N k=1 z k s.t. N k=1 A k z -γ k ≤ C, (14)
where in accordance with (11)

γ = 2 p + 1 p -1 , C = 2R 2 θ -2 p-1 .
Since the objective and constraints are separable, this problem can be solved explicitly by the Lagrange principle

z k =   1 C N j=1 A 1 γ+1 j   1/γ A 1 γ+1 k . Hence, min N k=1 A k z -γ k ≤C N k=1 z k = 1 C 1/γ N k=1 A 1 γ+1 k γ+1 γ
.

From this inequality, ( 9) and ( 13), we have

A N ≥ 1 4 θ 2 p+1 (2R 2 ) p-1 p+1 N k=1 A p-1 3p+1 k 3p+1 p+1 . ( 15
)
From this inequality, we obtain that there exists a number c such that, for all N ≥ 0,

A N ≥ 1 cM p R p-1 N 3p+1 2 . ( 16
)
The derivation of exact value of the constant c can be found in Lemma 5 in Appendix. This finishes the proof.

Implementation details

First of all, Theorem 1 in [START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF] says that, by the appropriate choice M = pM p in (3), the subproblem for finding y k+1 in step 2 of Algorithm 1 is convex and, thus is tractable. Moreover, for p = 2 this step corresponds to the step of cubic regularized Newton method of [START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF] and, as it is shown there, can be computed with the same complexity as solving a linear system. For the case p = 3, [START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF] showed that this step can be also computed efficiently.

In both cases the complexity of calculating y k+1 is Õ n 2.37 . Let us now discuss the process of finding such L k that the inequality (5) holds. By construction,

y k+1 = arg min y∈R n      p r=0 1 r! ∇ r f x k y -x k , ..., y -x k r + pM p (p + 1)! y -x k p+1 2 + L k 2 y -x k 2 2      .
This problem is strongly convex and, thus, has a unique solution for each L k > 0. Hence, y k+1 is uniquely defined by L k . At the same time, if L k → 0, y k+1 → ỹk with ỹk ∈ Arg min

y∈R n      p r=0 1 r! ∇ r f x k y -x k , ..., y -x k r + pM p (p + 1)! y -x k p+1 2     
being a fixed point. Whence,

2(p + 1)M p p!L k y k+1 -x k p-1 2 → +∞.
On the other hand, if L k → +∞, y k+1 → x k and

2(p + 1)M p p!L k y k+1 -x k p-1 2 → 0.
By the continuity of the dependence of y k+1 from L k , we see that there exists such L k that inequality (5) holds. Appropriate value of L k can be found by an extended line-search procedure as in (Monteiro and Svaiter, 2013, Section 7). The details of complexity of the line-search can be found in [START_REF] Jiang | An optimal high-order tensor method for convex optimization[END_REF]; [START_REF] Bubeck | Near-optimal method for highly smooth convex optimization[END_REF], where the authors prove a bound of Õ(1) calls of

T F L k ,x k
p,pMp (x k ) on each iteration.

Extension for Uniformly Convex Case

In this section, we additionally assume that the objective function is uniformly convex of degree q ≥ 2, i.e., there exists σ q > 0 s.t.

f (y) ≥ f (x) + ∇f (x), y -x + σ q q y -x q 2 , ∀x, y ∈ Q. ( 17
)
We also assume that q ≤ p + 1. As a corollary,

f (y) ≥ f (x * ) + σ q q y -x * q 2 , ∀y ∈ Q, (18)
where x * is a solution to problem (1). We show, how the restart technique can be used to accelerate Algorithm 1 under this additional assumption.

Algorithm 3 Restarted Optimal Tensor Method

Input: p, M p , q, σ q , z 0 , ∆ 0 s.t. f (z 0 ) -f * ≤ ∆ 0 . 1: for k = 0, 1, ... do 2: Set ∆ k = ∆ 0 • 2 -k and N k = max             2cM p q p+1 q σ p+1 q q ∆ p+1-q q k   2 3p+1      , 1      . (19) 3:
Set z k+1 = y N k as the output of Algorithm 1 started from z k and run for N k steps.

4:

Set k = k + 1. 5: end for Output: z k .

Theorem 4 Let sequence z k , k ≥ 0 be generated by Algorithm 3. Then

σ q q z k -x * q 2 ≤ f (z k ) -f * ≤ ∆ 0 • 2 -k ,
and the total number of steps of Algorithm 1 is bounded by (c is defined in (16))

2cq p+1 q 2 3p+1 M 2 3p+1 p σ 2(p+1) q(3p+1) q (∆ 0 ) 2(p+1-q) q(3p+1) • k i=0 2 -i 2(p+1-q) q(3p+1) + k.
Proof Let us prove the first statement of the Theorem by induction. For k = 0 it holds. If it holds for some k ≥ 0, by the choice of N k , we have that

cM p N 3p+1 2 k q∆ k σ q p+1 q ≤ ∆ k 2 .
By ( 18),

z k -x * p+1 2 ≤ q(f (z k ) -f * ) σ q p+1 q ≤ q∆ k σ q p+1 q
since, by our assumption, q ≤ p + 1. Combining the above two inequalities and Theorem 1, we obtain

f (z k+1 ) -f * ≤ cM p z k -x * p+1 2 N 3p+1 2 k ≤ ∆ k 2 = ∆ k+1 .
It remains to bound the total number of steps of Algorithm 1. Denote c = 2cq

p+1 q 2 3p+1 . k i=0 N i ≤ c M 2 3p+1 p σ 2(p+1) q(3p+1) q k i=0 (∆ 0 • 2 -i ) 2(p+1-q) q(3p+1) + k ≤ c M 2 3p+1 p σ 2(p+1) q(3p+1) q (∆ 0 ) 2(p+1-q) q(3p+1) • k i=0 2 -i 2(p+1-q) q(3p+1) + k.
Let us make several remarks on the complexity of the restarted scheme in different settings. It is easy to see from Theorem 4 that, to achieve an accuracy ε, i.e. to find a point x s.t. f (x)f * ≤ ε, the number of tensor steps in Algorithm 3 is

O   M 2 3p+1 p σ 2(p+1) q(3p+1) q (∆ 0 ) 2(p+1-q) q(3p+1) + log 2 ∆ 0 ε   , q < p+1, and O     M 2 3p+1 p σ 2(p+1) q(3p+1) q + 1   log 2 ∆ 0 ε   , q = p+1.
Theorem 4 suggests a natural generalization of first-and second-order condition number [START_REF] Yu | Accelerating the cubic regularization of newton's method on convex problems[END_REF]. If f is such that q = p+1, then the complexity of Algorithm 3 depends only logarithmically on the starting point and is proportional to (γ p ) 2 3p+1 , where γ p = Mp σ p+1 is the p-th order condition number. Unfortunately, if q < p + 1, the complexity depends polinomially on the initial objective residual ∆ 0 , which, in general, is not controlled.

An interesting special case is when q = 2 and p ≥ 2, and, as a consequence, q < p + 1. As it can be seen from Theorem 2 (see also [START_REF] Bubeck | Near-optimal method for highly smooth convex optimization[END_REF]), the sequence, generated by Algorithm 1 is bounded by some R = O( x 0x * 2 ). Hence, the constant M 2 can be estimated as M 2 ≤ M p R p-2 . At the same time, in (Nesterov, 2008, Sect.6), it is shown that the Cubic regularized Newton method [START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF] has the region of quadratic convergence given by {x :

f (x) -f * ≤ σ 2 2 2M 2 2 ≤ σ 2 2 2M 2 p R 2(p-2) }. To enter this region, Algorithm 3 requires O   M 2 3p+1 p σ p+1 3p+1 2 (∆ 0 ) p-1 3p+1 + log 2 ∆ 0 M 2 p R 2(p-2) σ 2 2   = O   M 2 3p+1 p σ p+1 3p+1 2 (∆ 0 ) p-1 3p+1 + log 2 M 2 p ∆ p-1 0 σ p 2   , (20)
where we used inequality R 2 ≤ 2∆ 0 σ 2 , which follows from (18). After entering the region of quadratic convergence, Algorithm 3 can be switched to the Cubic regularized Newton method [START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF], which has final stage complexity, (Nesterov and Polyak, 2006, Sect. 6)

O log 3/2 log 4 σ 3 2 M 2 2 ε = O log 3/2 log 4 σ 3 2 M 2 p R 2(p-2) ε .
Summing this inequality and ( 20) we obtain the total complexity of this switching procedure to obtain small accuracy ε. Note, that the second term in ( 20) is typically dominated by the first one, so we can ignore it without loss of generality.

Finally, let us compare our upper bound with known lower bounds. For the case p = 1, q = 2, our complexity bound coincides with lower bound for first-order methods [START_REF] Nemirovsky | Problem Complexity and Method Efficiency in Optimization[END_REF]; [START_REF] Nesterov | Introductory Lectures on Convex Optimization: a basic course[END_REF]. [START_REF] Arjevani | Oracle complexity of second-order methods for smooth convex optimization[END_REF] propose lower bounds for second-order methods for the case p = 2, q = 2 and our complexity bound coincides with their lower bound up to a change of D = ∆ 0 σ 2 , which is natural as, in this case f is strongly convex.

Numerical Analysis

In this section, we analyze and compare the performance of Algorithm 1 with the accelerated tensor method proposed in Nesterov ( 2018).

We study the numerical performance for two classes of functions. Initially, an universal parametric family of objective functions, which are difficult for all tensor methods Nesterov (2018) defined as

f m (x) = η p+1 (A m x) -x 1 , (21)
where, for integer parameter p ≥ 1,

η p+1 (x) = 1 p+1 n i=1 |x i | p+1 , 2 ≤ m ≤ n, x ∈ R n , A m is the n × n block diagonal matrix: A m = U m 0 0 I n-m , with U m =        1 -1 0 . . . 0 0 1 -1 . . . 0 . . . . . . . . . . . . 0 0 . . . 1 -1 0 0 . . . 0 1        , (22)
and I n is the identity n × n-matrix. For a detailed description of the high-order derivatives of this class of functions, and its optimality properties see [START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF].

Figure 1 shows the normalized optimality gap of the iterations generated by the accelerated tensor method from [START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF] in Figure1(a), and Algorithm 1 in Figure1(b). We denote the minimum function value as f * . For both results we have used p = 3, and n = k = {5, 10, 15, 20, 25}. These numerical results show that Algorithm 1 requires a much smaller number of iterations than the accelerated tensor method from [START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF] to reach the same optimality gap, namely 1 • 10 -15 , for the class of "bad" functions described in [START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF]. For example, for the case where n = k = 25, Algorithm 1 has reached the desired accuracy in about 100 iterations, while the accelerated tensor method requires about 1 • 10 4 .

Iterations

|f (x k )-f * | |f (x 1 )-f * | Algorithm 1 n = k = 5 n = k = 10 n = k = 15 n = k = 20 n = k = 25 (b)
Figure 1: A performance comparison between the accelerated tensor method in Nesterov (2018) (shown in (a)) and Algorithm 1 (shown in (b)). We minimize an instance of the family of functions in ( 21) with p = 3 and various values of dimension n and k. Note that the x-axis scaling on both figures is different.

As a second set of numerical results we study the performance of the proposed method for the non-regularized logistic regression problem. For this problem we are given a set of d data pairs {y i , w i } for 1 ≤ i ≤ d, where y i ∈ {1, -1} is the class label of object i, and w i ∈ R n is the set of features of object i. We are interested in finding a vector x that solves the following optimization problem

1 d d i=1 ln 1 + exp -y i w i , x → min x∈R n . (23)
Figure 2 shows the simulation results for the logistic regression problem in (23) for various datasets. Similarly as in Figure 1, we compare the performance of Algorithm 1, and the accelerated tensor method in [START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF]. In Figure 2(a) and Figure 2(b), we generate synthetic data, where, initially we define a vector x ∈ [-1, 1] with every entry is chosen uniformly at random. The set of features for each i, i.e., w i ∈ [-1, 1] n has also every entry chosen uniformly at random, finally each label is computed as y i = sign( w i , x ). For Figure 2 For the logistic regression problem, we don't have access to the optimal value function in general, thus, we plot only the cost function evaluated at the current iterate. As expected by the theoretic results, Algorithm 1 requires one order of magnitude less iterations than the accelerated tensor method from [START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF] to achieve the same function value.

In Appendix B, we numerically compare the performance of the accelerated tensor method from [START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF] for p = 2 and p = 3, as well as its accelerated and non-accelerated versions. (Nesterov,2018) Algorithm 1 In Figure 4, we consider the behaviour of the same set of methods as in Figure 3, but for logistic regression problem defined in (23) on Covertype dataset [START_REF] Dheeru | UCI machine learning repository[END_REF]. And again, we notice that in both cases non-accelerated version works better in our experiments First of all, we point out that tensor methods in general are non-trivial in implementation, so, it is interesting direction of the future work to get better implementation. Secondly, we conjecture that slow convergence that we see in our experiments is because of large M p that we use. Due to tuning of the parameters one can obtain better convergence in practice.

  Figure2shows the simulation results for the logistic regression problem in (23) for various datasets. Similarly as in Figure1, we compare the performance of Algorithm 1, and the accelerated tensor method in[START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF]. In Figure2(a) and Figure2(b), we generate synthetic data, where, initially we define a vector x ∈ [-1, 1] with every entry is chosen uniformly at random. The set of features for each i, i.e., w i ∈ [-1, 1] n has also every entry chosen uniformly at random, finally each label is computed as y i = sign( w i , x ). For Figure2(a) we set n = 10 and d = 100, while in Figure 2(b) we set n = 100 and d = 1000. Figure 2(c) uses the mushroom dataset (n = 8124 and d = 112) Dheeru and Karra Taniskidou (2017), and Figure 2(d) uses the a9a dataset (n = 32561 and d = 123) Dheeru and Karra Taniskidou (2017).For the logistic regression problem, we don't have access to the optimal value function in general, thus, we plot only the cost function evaluated at the current iterate. As expected by the theoretic results, Algorithm 1 requires one order of magnitude less iterations than the accelerated tensor method from[START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF] to achieve the same function value.In Appendix B, we numerically compare the performance of the accelerated tensor method from[START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF] for p = 2 and p = 3, as well as its accelerated and non-accelerated versions.

Figure 2 :

 2 Figure 2: Performance comparison for the non-regularized logistic regression problem between the accelerated tensor method from Nesterov (2018) and Algorithm 1. (a) Uses synthetic data with n = 10 and d = 100, (b) uses synthetic data with n = 100 and d = 1000, (c) uses the mushroom dataset (d = 8124 and n = 112) Dheeru and Karra Taniskidou (2017), and (d) uses the a9a dataset (d = 32561 and n = 123) Dheeru and Karra Taniskidou (2017).

Acknowledgments

The authors are grateful to Yurii Nesterov for fruitful discussions. The work of A. Gasnikov was supported by RFBR 18-29-03071 mk and was prepared within the framework of the HSE University Basic Research Program and funded by the Russian Academic Excellence Project '5-100', the work of P. Dvurechensky and E. Vorontsova was supported by RFBR 18-31-20005 mol-a-ved and the work of E. Gorbunov was supported by the grant of Russian's President MD-1320MD- .2018.1 .1

Optimal Tensor Methods in Smooth Convex and Uniformly Convex Optimization: Supplementary Material Appendix A. Technical lemmas Lemma 5 Consider the sequence {A k } k≥0 of non-negative numbers such that

where p ≥ 3, θ = p! 4(p+1)Mp and M p , R > 0. Then for all N ≥ 0 we have

where

Proof We prove (25) by induction. For k = 1 we have

.

The last inequality implies (25) for p ≥ 3. Now let us assume that for all k ≤ N inequality (25) holds and N ≥ 1. Next we will establish (25) for k = N + 1. We have

.

If N > 1 we can write

x is convex and, as a consequence, we get

Using this fact we continue:

For all N > 1 we have

.

From this and ( 28) we obtain that for all N ≥ 1

It remains to show that (26) implies

which is exactly what we have in ( 26).

Appendix B. Comparison of the accelerated tensor method from Nesterov (2018) for p = 2 and p = 3.

In this appendix, we numerically compare the performance of the accelerated tensor method proposed in [START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF], for p = 2 and p = 3. We also compare the accelerated and nonaccelerated version of this method. Similarly as in Figure 1 and Figure 2, we present the numerical results for the class of bad functions defined in ( 21) and one instance of the logistic regression problem.

In Figure 3, we compare the behavior of the following methods: 1) tensor method Nesterov (2018) for p = 3; 2) accelerated tensor method Nesterov (2018) for p = 3; 3) tensor method Nesterov (2018) for p = 2; 4) accelerated tensor method [START_REF] Nesterov | Implementable tensor methods in unconstrained convex optimization[END_REF] for p = 2. Again, the optimal function value is denoted by f * . Interestingly, we obtain that the non-accelerated method outperforms the accelerated method for the first m iterations. Since Theorem 4 from Nesterov (2018) works only for k ≤ m we don't study the behaviour of the methods for larger number of iterations. Even in this simple setting it is still non-trivial how to implement tensor methods for such bad examples of functions.


Jie Wu

ON VALUES TAKEN BY THE LARGEST PRIME FACTOR OF SHIFTED PRIMES

Keywords: Mathematics Subject Classification. 11N05, 11N25, 11N36 Shifted prime, Friable integer, Sieve

Denote by P the set of all prime numbers and by P (n) the largest prime factor of positive integer n 1 with the convention P (1) = 1. In this paper, we prove that for each η ∈ ( 32 17 , 2.1426 . . . ), there is a constant c(η) > 1 such that for every fixed non-zero integer a ∈ Z * the set {p ∈ P : p = P (q -a) for some prime q with p η < q c(η)p η } has relative asymptotic density 1 in P. This improves a similar result due to Banks & Shparlinski [2, Theorem1.1], which requires η ∈ ( 32 17 , 2.0606 . . . ) in place of η ∈ ( 32 17 , 2.1426 . . . ).

Introduction

The largest prime factors of shifted primes appears in many well-known arithmetic questions (such as the Fermat last theorem, the twin prime conjecture, RSA schemes of cryptology, etc), and their distribution plays a key role. The study of this problem has received much attention. Denote by P the set of all prime numbers and by P (n) the largest prime factor of the positive integer n 1 with the convention P (1) = 1. For example, we are interested in the greatest value of θ for which there is a positive proportion of primes p such that P (p -a) p θ (see [START_REF] Goldfeld | On the number of primes p for which p + a has a large prime factor[END_REF][START_REF] Fouvry | Théorème de Brun-Titichmarsh; application au théorème de Fermat[END_REF][START_REF] Baker | The Brun-Titchmarsh theorem on average[END_REF][START_REF] Zhang | Bounded gaps between primes[END_REF][START_REF] Rivest | Are 'Strong' Prime Needed for RSA ? Cryptology ePrint Archive[END_REF]). For given θ ∈ (0, 1), we also considered the relative asymptotic density of such primes in P (see [START_REF] Luca | On shifted primes with large prime factors and their products[END_REF][START_REF] Chen | On the largest prime factor of shifted primes[END_REF][START_REF] Feng | On the density of shifted primes with large prime factors[END_REF]). Motived by these questions, Liu, Wu & Xi [START_REF] Liu | Primes in arithmetic progressions with friable indices[END_REF] studied the distribution of primes in arithmetic progressions with friable indices, i.e., {a + mq} m friable (recall that a positive integer m is friable if its all prime factors are small), and established analogues of classical Siegel-Walfisz theorem, Bombieri-Vinogradov theorem and Brun-Titchmarsh theorem.

In [START_REF] Banks | On values taken by the largest prime factor of shifted primes[END_REF], Banks & Shparlinski studied the related problem of estimating the number of primes p that occur as the largest prime factor of a shifted prime q -a when q ∈ P lies in a certain interval determined by p. It is worthy to note that this question has applications in theoretical computer science and has been considered by Vishnoi [START_REF] Vishnoi | Theoretical aspects of randomization in computation[END_REF] (in a different form).

For a ∈ Z * , real numbers c > 1 and η > 0, define P a,c,η := {r ∈ P : r = P (q -a) for some prime q with r η < q cr η } and π a,c,η (x) := |{r x : r ∈ P a,c,η }|, π(x) := |{r x : r ∈ P}|.

Banks & Shparlinski [2, Theorem 1.1] proved that for every η ∈ ( 32 17 , 1 + 3 4 √ 2), there exists a constant c = c(η) > 1 such that the asymptotic formula

(1.1) π a,c,η (x) = π(x) + O A,a,c,η x (log x) A
holds for each fixed non-zero integer a ∈ Z * and any constant A > 1. Moreover for 2 η < 1 + 3 4 √ 2, this estimate holds for any constant c > 1. The aim of this paper is to improve the result of Banks-Shparlinski by etending the domain of η. Our result is as follows.

Theorem 1. Let η 0 ≈ 2.1426 be the unique solution of the equation

(1.2) η -1 -4η log(η -1) = 0.
For each real number η ∈ ( 32 17 , η 0 ), there exists a constant c = c(η) > 1 such that the asymptotic formula (1.1) holds for every fixed non-zero integer a ∈ Z * and any A > 1, where the implied constant depends only on A, a, c and η. Moreover for 2 η < η 0 , this asymptotic formula holds for any constant c > 1.

For comparaison, we have y<q cy q≡a(mod r), P (q-a)>r 1 than [START_REF] Banks | On values taken by the largest prime factor of shifted primes[END_REF]Formula (9) or Page 143, line 2] of Banks & Shparlinski, who obtained 8η(η -2) in place of 4η log(η-1) η-1

. In view of the inequality log(1 + t) < t for t > 0, we see that

η > 2 ⇒ log(η -1) η -1 < η -2 η -1 < η -2.
Therefore our bound must be better. This improvement comes from the following two observations: (i) In many arithmetic applications, the linear sieve is more powerful than the sieve of dimension 2;

(ii) With the help of the Chen-Iwaniec switching principle [START_REF] Chen | On the representation of a large even integer as the sum of a prime and the product of at most two primes[END_REF][START_REF] Iwaniec | Primes of the type φ(x, y) + A where φ is a quadratic form[END_REF] and our theorem of Bombieri-Vinogradov type (see Proposition 3.2 below), we can sieve the sequence of convolution defined as in (4.1) below by the linear sieve, instead of fixing k and sieving {n(knr + a)} n by the sieve of dimension 2 as in [START_REF] Banks | On values taken by the largest prime factor of shifted primes[END_REF].

2. Banks-Shparlinski's argument and sketch of the proof of Theorem 1

In this section, we shall present the sketch of the proof of Theorem 1 by simplifying the Banks-Shparlinski argument [START_REF] Banks | On values taken by the largest prime factor of shifted primes[END_REF]. In view of the Banks-Shparlinski result (1.1), it suffices to prove Theorem 1 for η ∈ (2, η 0 ). The letters p, q, r and are always used to denote prime numbers, and d, m, and n always denote positive integers. In what follows, let a and A be as in Theorem 1 and η ∈ (2, η 0 ). Let δ be a sufficiently small positive constant and let c > 1 be a parameter to be chosen later. Let x 0 (A, a, η, δ, c) be a large constant depending on A, a, η, δ, c at most. For x x 0 (A, a, η, δ, c) and r ∈ ( The Bombieri-Vinogradov theorem plays an important role in the Banks-Shparplinski argument. This theorem can be stated as follows: For any A > 0, there exists a constant B = B(A) > 0 such that (2.1)

d x 1/2 (log x) -B max z x max (a,d)=1 π(z; d, a) - π(z) ϕ(d) A x (log x) A
for all x 2, where ϕ(n) denotes the Euler totient function and the implied constant depends on A only.

For z x 1/2 (log x) -B , put D(x; z) := d z : π(x; d, a) - π(x) ϕ(d) δ π(x) ϕ(d) .
By using (2.1) with A + 1 in place of A, we deduce that, for every d ∈ D(x; z), remove

δ π(x) z |D(x; z)| A x (log x) A+1 , which gives immediately (2.2) |D(x; z)| A,δ z (log x) A • Define R(x) := 1 2 x < r x : π(y; r, a) (1 + δ) π(y) ϕ(r) and π(cy; r, a) (c -δ) π(y) ϕ(r) . Since η > 2, we have r = y 1/η y 1/2 (log y) -B . Thus the last estimation in (2.2) with (x, z) = (y, x) implies that (2.3) |R(x)| = π(x) -π( 1 2 x) + O A,a,η,δ,c x (log x) A (x 2).
For every prime r ∈ R(x), define

(2.4) Q 1 (r) := y<q cy P (q-a)=r
Q 1 (r) = π(cy; r, a) -π(y; r, a) -Q 2 (r) (c -1 -2δ) π(y) ϕ(r) -Q 2 (r).
The following result gives us the required upper bound for Q 2 (r), which constitutes the key to our improvement. Proposition 2.1. Under the previous notation, for r ∈ P ∩ [ 1 2 x, x] we have

(2.6) Q 2 (r) (c -1 + 2δ) 4η log(η -1) η -1 • π(y) ϕ(r) 1 + O 1 3 √ log r for x x 0 (A, a, η, δ, c).
In Section 4, we shall prove this proposition. Now we suppose this proposition and complete the proof of Theorem 1.

Inserting (2.6) into (2.5), it follows that

Q 1 (r) c -1 -2δ η -1 η -1 -4η log(η -1) • c -1 + 2δ c -1 -2δ π(y) ϕ(r) • Taking c = 1 + 2 √ δ, we can find that Q 1 (r) 2 √ δ -δ η -1 η -1 -4η log(η -1) • 1 + √ δ 1 - √ δ π(y) ϕ(r) = G(η) + O √ δ 2 √ δ 1 - √ δ η -1 • π(y) ϕ(r) ,
where

(2.7) G(η) := η -1 -4η log(η -1).
It is easy to see that G(η) is decreasing on [2, ∞) and G(2) = 1. Therefore there is a unique real number η 0 ∈ (2, ∞) such that G(η 0 ) = 0 and for η ∈ [2, η 0 ) we have the inequality

(2.8) Q 1 (r) A,a,η,δ π(y) ϕ(r)
for x x 0 (A, a, η, δ, c). From (2.8), we deduce that

R(x) ⊆ P a,c,η ∩ ( 1 2 x, x]. Combining this with (2.3) lead to π a,c,η (x) -π a,c,η ( 1 2 x) = π(x) -π( 1 2 x) + O A,a,η,δ,c x (log x) A .
This implies the required asymptotic formula (1.1). The proof of Theorem 1 is completed assuming Proposition 2.1.

Linear sieve and mean value theorem

The aim of this section is devoted to present two tools and a preliminary lemma. They will be needed in the proof of Proposition 2.1 above.

3.1.

The Rosser-Iwaniec linear sieve. The first one is the Rosser-Iwaniec linear sieve [START_REF] Iwaniec | Rosser's sieve[END_REF][START_REF] Iwaniec | A new form of the error term in the linear sieve[END_REF]. As usual, denote by µ(n) the Möbius function. and

d|P (z) λ + d w(d) d p z p∈P 1 - w(p) p F (s) + O e √ L-s 3 √ log D (3.2) d|P (z) λ - d w(d) d p z p∈P 1 - w(p) p f (s) + O e √ L-s 3 √ log D (3.3)
for any z ∈ [2, D], s = (log D)/ log z, set of prime numbers P and multiplicative function w satisfying

0 < w(p) < p (p ∈ P), (3.4) u<p v, p∈P 1 - w(p) p -1 log v log u 1 + L log u (2 u v), (3.5)
where P (z) := p z, p∈P p and the implied O-constants are absolute. Here F, f are defined by the continuous solutions to the system

(sF (s)) = f (s -1) (s > 2) (sf (s)) = F (s -1) (s > 2)
with the initial condition

sF (s) = 2e γ (1 s 2) sf (s) = 0 (0 < s 2)
where γ is the Euler constant.

A mean value theorem of Bombieri-Vinogradov type.

In order to control the error term coming from the linear sieve in our case, we need a mean value theorem of Bombieri-Vinogradov type. For this, we consider non-negative arithmetic functions κ, which satisfy the properties (A ), (B) and (C ) as introduced by Motohashi [

13]:

(A ) There is a positive constant C such that κ(n) τ (n) C , where τ (n) is the classical divisor function. (C ) If the conductor of a non-trivial Dirichlet character χ is O((log x) D ) for some D > 0, then

n x κ(n)χ(n) x(log x) -3D .
(C ) For any A > 0, there exists a constant B = B(A) > 0 such that

d x 1/2 (log x) -B max z x max (a,d)=1 n z n≡a(mod d) κ(n) - 1 ϕ(d) q z (d,n)=1 κ(n) x (log x) A
for all x 3. In [13, Theorem 1], Motohashi proved the following result: If f and g have the properties (A ), (B) and (C ), then so does the multiplicative convolution f * g.

The following proposition will play a key role in the proof of Proposition 2.1 above. Evidently it is of independent interest and should have other applications. Proposition 3.2. Let κ 1 (m) and κ 2 (m) be the characteristic functions of the odd integers and of even integers, respectively. Then for any A > 0, there is a constant B = B(A) > 0 such that the inequality

d x 1/2 (log x) -B 2 d max z x max (a,d)=1 mp z mp≡a(mod d) κ i (m) - 1 ϕ(d) mp z (d,mp)=1 κ i (m) A x (log x) A holds for all x 3.
Proof. In view of the Bombieri-Vinogradov theorem (2.1), the characteristic function of the primes has the properties (A ), (B) and (C ). According to Motohashi's result mentioned above, it is sufficient to verify that κ 1 and κ 2 satisfy (A ), (B) and (C ).

The property (A ) is obvious for these two functions.

Since n → χ(n) is completely multiplicative, we have

n x κ 2 (n)χ(n) = χ(2) m x/2 χ(m) (log x) D x(log x) -3D .
This shows that κ 2 has the property (B). Defining 1(n) := 1 for n 1 and noticing that κ 1 = 1 -κ 2 , the function κ 1 also has the property (B). It remains to prove that κ i satisfies the property (C ). For 2 d, we have

n z (n,d)=1 κ 2 (n) = m z/2 (m,d)=1 1 = m z/2 d |(m,d) µ(d ) = d |d µ(d ) m z/(2d ) 1 = ϕ(d) 2d z + O(τ (d)).
Thus

n z n≡a(mod d) κ 2 (n) - 1 ϕ(d) n x (n,d)=1 κ 2 (n) = m z/2 m≡2a(mod d) 1 - z 2d + O τ (d) ϕ(d) 1,
where 2 is the inverse of 2 modulo d. From this we deduce immediately

d x 1/2 (log x) -B 2 d max z x max (a,d)=1 n z n≡a(mod d) κ 2 (n) - 1 ϕ(d) n z (n,d)=1 κ 2 (n) x 1/2 (log x) B •
This proves that the function κ 2 (n) has the property (C ). A similar argument shows that the function 1 has the property (C ). Since κ 1 (n) = 1(n) -κ 2 (n) for all integers n 1, the sequence {κ 1 (n)} n 1 satisfies the property (C ).

3.3.

A preliminary lemma. Lemma 3.3. For each positive integer n 1, define

(3.6) ψ(n) := 2<p|n p -1 p -2 •
Then we have

n x ψ(n) = Ξ -1 2 x + O x log x for x 2, where (3.7) Ξ 2 := p>2 1 - 1 (p -1) 2 . Proof. Since the function n → ψ(n) is strongly multiplicative such that ψ(2 ν ) = 1 and ψ(p ν ) = p -1 p -2 (p odd prime),
for e s > 1 we can write

n 1 ψ(n) n s = p 1 + ν 1 ψ(p ν ) p νs = 1 1 -2 -s p>2 1 + p -1 p -2 p -s 1 -p -s = ζ(s) p>2 1 + 1 (p -2)p s , where ζ(s) := p (1 -p -s ) -1 is the Riemann ζ-function. Using [15, Theorem II.5.3],
we obtain the required result.

Proof of Proposition 2.1

As indicated in the introduction, our method is different from [START_REF] Banks | On values taken by the largest prime factor of shifted primes[END_REF]. If a prime number q is counted in Q 2 (r), then we can write q -a = k r, where is the largest prime factor of q -a. Since > r ∈ ( 1 2 x, x] and y < q cy, we have k (cy -a)/( r) 2cr η-2 . On the other hand, noticing that , r and q = k r + a are odd, we must have 2 (a + k).

For simplicity of notation, we put

c 1 := 1 -δ, c 2 := c + δ.
By the Chen-Iwaniec switching principle [START_REF] Chen | On the representation of a large even integer as the sum of a prime and the product of at most two primes[END_REF][START_REF] Iwaniec | Primes of the type φ(x, y) + A where φ is a quadratic form[END_REF], we see that Q 2 (r) does not exceed the number of primes in the sequence µ(d).

By using Lemma 3.1, it follows that

Q 2 (r)
k 2cr η-2 , 2 (a+k) c 1 y/(kr)< c 2 y/(kr) d|(k r+a,P 2r (z))

λ + d = d|P 2r (z) λ + d k 2cr η-2 , 2 (a+k) c 1 y/(kr)< c 2 y/(kr) k r≡-a(mod d) 1 = d|P 2r (z) λ + d k 2cr η-2 , 2 (a+k) c 1 y/(kr)< c 2 y/(kr) k ≡-ar(mod d) 1,
where r is the inverse of r module d, i.e., rr ≡ 1 (mod d).

Introducing the notation

E(t; d, b) := k 2cr η-2 , 2 (a+k) t/(kr) k ≡b(mod d) 1 - 1 ϕ(d) k 2cr η-2 , 2 (a+k) t/(kr) (k ,d)=1 1, we write k 2cr η-2 , 2 (a+k) c 1 y/(kr)< c 2 y/(kr) k ≡-ar(mod d) 1 = 1 ϕ(d) k 2cr η-2 , 2 (a+k) c 1 y/(kr)< c 2 y/(kr) (k ,d)=1 1 + E(c 2 y; d, -ar) -E(c 1 y; d, -ar).
Inserting into the preceding formula, it follows that On the other hand, the Mertens formula allows us to deduce that Noticing that > r > 1 2 x and that and r are primes, we have ψ(k r) ψ(k)ψ( )ψ(r) = {1 + O(x -1 )}ψ(k).

p z, p 2m 1 - 1 p -1 = 2<p z 1 - 1 p -1 2<p|m p -1 p -2 = 2<p z 1 - 1 (p -1) 2 2<p|m p -1 p -2 2<p z 1 - 1 p = 2Ξ 2 ψ(m)e -γ log z 1 + O 1 log z ,

1 2 x

 2 , x], put y := r η . As usual, for (a, d) = 1 define π(x; d, a) := p x, p≡a(mod d) 1.

1 and Q 2

 12 (r) := y<q cy q≡a(mod r), P (q-a)>r1,Then the definition of R(x) allows us to write(2.5)

Lemma 3 . 1 .

 31 Let D 2. There are two sequences {λ ± d } d 1 , vanishing for d > D or µ(d) = 0, verifying |λ ± d | 1, such that (

(4. 1 )r+a is prime 1 k 1 =k

 111 k r + a : k 2cr η-2 , 2 (a + k), c 1 y/(kr) < c 2 y/(kr) .We shall sieve this sequence by the set of primes P 2r := {p ∈ P : p 2r}. Define P 2r (z) := p<z, p 2r p with z := (y/r) 1/4 (log(y/r)) -B(3) < r and denote by µ(n) the Möbius function. The inversion formula of Möbius allows us to write thatQ 2 (r) k 2cr η-2 , 2 (a+k) c 1 y/(kr)< c 2 y/(kr)k 2cr η-2 , 2 (a+k) c 1 y/(kr)< c 2 y/(kr) (k r+a,P 2r (z))=1 2cr η-2 , 2 (a+k) c 1 y/(kr)< c 2 y/(kr) d|(k r+a,P 2r (z))

(4. 2 )k

 2 Q 2 (r) M(r) + E(r), where M(r) := d|P 2r (z) 2cr η-2 , 2 (a+k) c 1 y/(kr)< c 2 y/(kr) (k ,d)=1 1, E(r) := d|P 2r (z) λ + d (E(c 2 y, d, -ar) -E(c 1 y, d, -ar)).

Firstly, by inversion

  of summations and Lemma 3.1 with w(d) = d/ϕ(d), D := z 2 , P = {p ∈ P : p 2k r}, it follows that M(r) = k 2cr η-2 , 2 (a+k) c 1 y/(kr)< c 2 y/(kr) d|P 2k r (z)

where Ξ 2 c 1

 21 and ψ(m) are defined as in (3.7) and(3.6), respectively. Inserting it into the preceding relation and using the fact that F (2) = e γ , we find y/(kr)< c 2 y/(kr) ψ(k r).

2Ξ 2 (c 2 - 2 4

 2224 c 1 )y r(log z) log(y/r) S(r),whereS(r) := k 2cr η-2 2 (a+k) ψ(k) k(1 -(log k)/ log(y/r))•With the help of Lemma 3.3, a simple partial integration leads to is defined as in (3.7). Combining it with the preceding formula, it follows that(-1 + 2δ)η log(η -1) η -1 π(y) ϕ(r) •With the help of Proposition 3.2, it is easy to see that (4.4) E(r) y r(log y) A • Inserting (4.3) and (4.4) into (4.2), we obtain the required inequality (2.6).

Acknowledgements. The author is supported in part by NSFC No. 11771121.


Tristan Bonargent
email: tristan.bonargent@unicaen.fr

Eric Pigeon

Tristan Martin

Mathieu Pouliquen

Olivier Gehan

Tomas Menard

Mohammed M'saad

Identification of quantifiers related to circadian rhythm variations

Keywords: Circadian rhythm, least square algorithm, COSINOR, jet lag, hypergravity, rats

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche

I. INTRODUCTION

The circadian rhythm reflects the temporal organization of the biology and behavior of every life forms to anticipate and optimally deal with predictable variation of their environment [START_REF] Reinberg | Chronobiologic perspectives of black time-Accident risk is greatest at night: An opinion paper[END_REF]. The day/night variations induced by Earth rotation contribute to their acclimation by synchronizing the circadian rhythm on a period of 24 hours [START_REF] Refinetti | The circadian rhythm of body temperature[END_REF]. The circadian rhythm promotes wake state to optimally conduct our daily activity during the active time, and promotes restoration and repair during rest time. Indeed, it has a great influence on the behavior, the physical conditions, the cognitive performance, the muscular power, the sleep or even the perception of human being and some animals [START_REF] Reilly | Altered sleep-wake cycles and physical performance in athletes[END_REF]. The easiest physiological variable allowing to measure and to identify the circadian rhythm of a living being is its internal temperature [START_REF] Refinetti | The circadian rhythm of body temperature[END_REF].

Nowadays, to ensure the best physical performances of night shift workers [START_REF] Burgess | Bright light, dark and melatonin can promote circadian adaptation in night shift workers[END_REF] or to speed up the recovery due to jet lag disturbances [START_REF] Samuels | Jet Lag and Travel Fatigue: A Comprehensive Management Plan for Sport Medicine Physicians and High-Performance Support Teams[END_REF], the synchronization of the circadian rhythm has become an important topic. In particular, it is important to determine if it is possible to modify the adaptation speed of the circadian rhythm with external stimuli after a disturbance like jet lags. For that reason, several quantifiers are required in order to estimate the speed and time of resynchronization of the circadian rhythm after stimuli.

Several approaches have been considered in the literature in order to analyze the circadian rhythm, by using the internal temperature, as the frequency approach using periodograms, the statistical method or some methods from the field of signal processing [START_REF] Refinetti | Procedures for numerical analysis of circadian rhythms[END_REF]. The most popular approach is probably the Lomb and Scargle algorithm [START_REF] Lomb | Least-squares frequency analysis of unequally spaced data[END_REF] which is used to compute the periodicity of the cycle with a frequency approach. It uses a sliding window that can filter out variations in high-frequency signals but does not provide any parameters other than periodicity. A statistical analysis, called ANOVA, is employed to determine the parameters of the circadian cycle. The ANOVA method is a post-processing tool with does not work in real-time. In contrast, a recursive least square algorithm, from the field of signal processing, can be used to fit the circadian rhythm in real-time with a model [START_REF] Hickey | Analysis of circadian rhythms by fitting a least squares sine curve[END_REF]. One of the most commonly used models to represent circadian rhythm, with this approach, is the COSINOR. Unfortunately, this purely sinusoidal model cannot take into account disturbances coming from the external environment, which leads to a bias on the results. To the authors best knowledge, no study explicitly incorporates external disturbances into the model, and are then able to provide accurate quantifiers for the adaptation speed of the circadian rhythm from external stimuli.

In this article, we propose an algorithm that provides, in real-time, quantifiers giving informations on the adaptation speed of the studied living being, namely, the resynchronization time and the speed of convergence and delay. An extended COSINOR model, taking into account external disturbances, is first proposed, whose parameters are estimated in real-time by using a modified least square algorithm that permits to give unbiased estimation of the parameters even if the persistent excitation condition is not always met. The quantifiers related to the dynamic of the circadian rhythm variations are then calculated in real-time by filtering the parameters estimates.

The paper is organized as follows. The proposed algorithm, providing estimation of the considered quantifiers, is presented in section II. In section III, the experiment conducted, by the COMETE laboratory, on rats, is detailed. The proposed approach is then applied on the measurements obtained from the experiment, in section IV, and an interpretation of the results, in order to validate the proposed quantifiers, is given. Finally section V concludes the paper.

II. METHODOLOGY

In this section, one describes the algorithm which estimates some quantifiers related to the speed of the circadian rhythm adaptation when facing perturbations. First, the extended COSINOR model and the corresponding modified least square algorithm are presented in subsection II-A. Then, the considered quantifiers are presented in subsection II-B together with an estimation algorithm which extracts characteristic informations on the circadian rhythm adaptation.

A. Estimation of circadian rhythm parameters 1) Reminder on the circadian rhythm:

The circadian rhythm is a biological rhythm that can be described as a repetition of oscillations of a physical variable. The oscillations occur periodically. This phenomenon can be characterized with physical quantities as shown on Fig. 1 and enumerated in the following paragraph:

• the MESOR (Midline Estimating Statistic Of Rhythm)
is the mean value of the signal during one period. • the Amplitude is the half of the difference between the maximum value and the minimum value of the signal. • the Period is the length of one oscillation.

• Acrophases are the instants corresponding to the maximum values of the signal contrary to the Batyphases which are the instants corresponding to the minimum values. Internal temperature measurements are usually analyzed using the COSINOR model [START_REF] Halberg | Circadian System Phase -An Aspect of Temporal Morphology; Procedures and Illustrative Examples[END_REF]. The parameters can be estimated with a recursive least square algorithm. The aim of this algorithm is to determine the set of parameters that minimizes the quadratic error between the internal temperature of the subject and the output of the model. Since the COSINOR model only considers stable circadian rhythm, we present next an extended COSINOR model that takes into account the effects of an external stimuli on the circadian rhythm and then the internal temperature.

2) Extended COSINOR model:

The COSINOR model [START_REF] Hickey | Analysis of circadian rhythms by fitting a least squares sine curve[END_REF] is conventionally defined as follows:

Θ(t) = M + A cos(2πf t + ϕ) (1)
with Θ(t) the temperature, M the mesor, A the amplitude, ϕ the phase, f the frequency and t the discrete time. In this study, the frequency f is considered to be known with a value of 1/24 hours -1 . In the classical case, the least To improve the model, two signals v(t) and e(t), representing respectively the external stimuli and other nonmodeled inputs, are introduced. The extended COSINOR is hence defined as follows:

Θ(t) = M + A cos (2πf t + ϕ) + B(q -1 )v(t) + C(q -1 )e(t) (2) with B(q -1 ) = b 0 + b 1 q -1 + b 2 q -2 + • • • + b n b q -n b , C(q -1 ) = 1 + c 1 q -1 + c 2 q -2 + • • • + c nc q -nc
, n b and n c represent respectively the order of B(q -1 ) and C(q -1 ). q -1 is the shift operator such that q -1 x(t) = x(t -1).

The signal e(t) is assumed to be a white noise that represents the effects of the external environment on the internal temperature and v(t) is a centered binary signal that represents the presence of a stimuli.

As the cosine function is not a linear combination of the parameters, it is linearized as follows :

Θ(t) = M + α cos (2πf t) + ρ sin (2πf t) + B(q -1 )u(t) + C(q -1 )e(t) (3) with α = A cos (ϕ) and ρ = A sin (ϕ).
The parameter vector θ and the regression vector φ(t) are respectively defined by:

θ = [M α ρ b 0 b 1 . . . c 1 c 2 . . .] φ T (t) = [1 cos (2πf t) sin (2πf t) v(t) . . . v(t -n b ) e(t -1) . . . e(t -n c )] (4)
Using the previous definitions, equation [START_REF] Reilly | Altered sleep-wake cycles and physical performance in athletes[END_REF] can be re-written under the following matrix standard form :

Θ(t) = φ T (t)θ + e(t) (5)
3) Adaptation of the recursive least square algorithm: The vector θ(t) containing the estimated parameters is defined as follows

θ(t) = M α ρ b0 b1 . . . ĉ1 ĉ2 . . . (6)
The signal e(t) cannot be measured since it corresponds to un-modeled inputs, as a consequence, e(t -i) is replaced by the a posteriori error ε(t -i/t -i), which is defined as follows

ε(t -i/t -i) = Θ(t -i) -φT (t -i) θ(t -i) (7)
This leads to the following definition of the substituted regression vector φ(t)

φT (t) = [1 cos (2πf t) sin (2πf t) v(t) . . . v(t -n b ) . . . ε(t -1/t -1) . . . ε(t -n c /t -n c )] (8)
The least square algorithm proposed in this study is defined as follows [START_REF] Pouliquen | Identification Scheme for Hammerstein Output Error Models With Bounded Noise[END_REF], [START_REF] Saad | Adaptation Paramétrique aux moindres carrés[END_REF]:

                                   ε(t/t -1) = Θ(t) -φT (t) θ(t -1) δ(ε(t/t -1)) = 0 if |ε(t/t -1)| < γ w 1 - γw |ε(t/t-1)| otherwise Γ(t) = δ(ε(t/t-1))F (t) φ(t) 1+δ(ε(t/t-1)) φT (t)F (t) φ(t) θ(t) = θ(t -1) + Γ(t)ε(t/t -1) F (t + 1) = (1 -β)(I n -F (t) φT (t))F (t) + βF 0 (9) with n = 3 + n b + n c + 1, β ∈ R +
relatively small that respect 0 < β < 1, γ w an infimum of the imperfection of the model and F 0 the initial value of the matrix F (t) which is chosen very large.

This algorithm is a robust modification of the standard extended least square algorithm. It permits to ensure an unbiased convergence of the parameters even if the persistent excitation conditions are not always met [START_REF] Ljung | System Identification: Theory for the User[END_REF].

The role of δ(ε(t/t -1)) is to freeze the adaptation if the a priori error is below the threshold γ w . In the other case, δ(ε(t/t -1)) progressively increases while the error increases until it approaches 1. In this least square algorithm, the matrix F (t) is computed with a filtering action controlled by β.

B. Estimation of the quantifiers

The aim of the present work is to determine characteristic factors of the resynchronization of the circadian rhythm after a disturbance. These factors are obtained from the phase ϕ of the circadian rhythm. Indeed, this variable seemed to be the best physical quantity to perceive the adaptation. Therefore, two methods are proposed to compute the factors. The first one estimates the resynchronization time by estimating the convergence time of the phase ϕ. The second one estimates two factors: a speed of convergence and a delay corresponding to the time before the beginning of the phase shift.

1) Resynchronization time approach:

The resynchronization time can be obtained from an estimation of the derivative of the phase. A Luenberger observer [START_REF] Luenberger | An introduction to observers[END_REF] is implemented based on the following design model that contains the phase and its first derivative as state variables

x(t + 1) = Ax(t) Θ(t) = Cx(t) (10)
with

A = 1 T e 0 1 , C = 1 0 , x(t) = x 1 (t) x 2 (t) T ∈
R 2 is the state vector, Θ(t) = x 1 (t) ∈ R the phase and T e the sampling period. Please note that x 2 (t) represents the first derivative of Θ(t) and hence the signal to be estimated.

Based on the model ( 10), the Luenberger observer that provides a consistent estimation x(t) = x1 (t) x2 (t)

T of x(t) is given by

x(t + 1) = Ax(t) -K( Θ(t) -Θ(t)) (11)
where the gain K ∈ R 2×1 is calculated to adjust the eigenvalues of the matrix (A -KC) in the stability domain and to ensure a compromise between the speed of convergence and the observer sensitivity to the noise measurement.

The time of resynchronization is inferred form a threshold calculated from the derivative of the phase. Indeed, the value of the threshold is computed from the maximum of the derivative of the phase between the interval [t 1 , t 2 ], with t 1 corresponds to the time of convergence of the least square algorithm and t 2 the time of the stimuli.

The convergence time is finally obtained by computing the last instant for which the derivative of the phase is above the threshold. The resynchronization time corresponds to the convergence time minus the perturbation time. This method is illustrated Fig. 2.

2) Speed of convergence and delay approach:

The second method provides an estimation of the speed of convergence to the new rhythm and the delay taken to begin the phase shift. This is done by fitting on the estimated phase a second order model with a delay and a zero. The equation of the model is given in equation [START_REF] Saad | Adaptation Paramétrique aux moindres carrés[END_REF].

G(s) = K p -T z + s 1 + 2ζ ω0 s + ( s ω0 ) 2 e -T d s ( 12
)
with K p the static gain, ζ the damping, ω o the natural frequency, T d the delay that is related to the time taken before the shift and T z the zero. In this model, the natural frequency ω o is related to the bandwidth and thus to the speed of convergence and T d to the time taken before the beginning of the phase shift. The zero T z was added to obtain a better fit of the model. In fact, the zero in the frequency domain doesn't disturb the second order model because of its small value. The curve is considered as a step response of a delayed second order model as illustrated on Fig. 3. This second method consists in identifying the delay and the natural frequency of this model.

III. DESCRIPTION OF THE EXPERIMENT

Besides from light information, the vestibular system plays an important role in the synchronization of circadian rhythms [START_REF] Lomb | Least-squares frequency analysis of unequally spaced data[END_REF]. It is an organ that sens every head acceleration in all directions and thus gives sense of balance and gravity. The vestibular system is sensitive and can be affected with external perturbations. An experiment was conducted on rats to highlight the effects of jet lags and vestibular stimulation by hypergravity on circadian rhythms adaptation to jet lag. This experiment was set up in the COMETE UMR-S 1075 INSERM laboratory.

The vestibular system plays an important role in the circadian rhythm [START_REF] Fuller | Genetic evidence for a neurovestibular influence on the mammalian circadian pacemaker[END_REF]. It is a sensor that gives a spatial orientation and a sense of balance. The vestibular system is sensitive and can be affected by external perturbations. Research is being carried out to determine factors that can modify the rate of adaptation of this rhythm. An experiment was conducted on rats to highlight the effects of jet lags and hypergravity on circadian rhythm. This experiment was set up in the COMETE UMR-S 1075 INSERM laboratory of CAEN University .

Two different groups of rats were used. The first one was called bilateral vestibular loss (BVL) induced using an injection of chemicals products. The perception of movement by the inner ear was then abolished permanently. The second group was called SHAM. This group underwent the same operation than the BVL but were injected with a placebo.

The two groups of rats were separated in three sub-groups. Each sub-group endured different perturbations. The three sub-groups are called JET LAG, 2G and JET LAG+2G. Their protocols are described as follow:

1) JET LAG: This first group was exposed to a 6 hours jet lag. This was done by changing the time of the cycle Day-Night of the experiment room. The rats were used to have their lights turning off at 8 p.m. When the perturbation began, the darkness occurred at 2 p.m. It is a phase advance of 6 hours. 2) 2G: The rats of the 2G group underwent a hypergravity representing the double of the earth gravity. The material used was a centrifuge for small animal. This was done once a day at a fixed hour during the Acrophase. 3) JET LAG+2G: The rats in this last group endured the two types of perturbations exposed in 1) and 2) at the same time. The physical quantity acquired during the experiment was the internal temperature of the rats. Thermometers contained in pills were given to the rodents to monitor the temperature. It was measured 7 days before the perturbation and until the end of the experiment. 14 rats were used in each subgroup and each sub-group was divided by two with BVLs and SHAMs.

IV. RESULTS OF THE EXPERIMENTATION

A. Implementation of the selected algorithm

The presented algorithm has been used on data corresponding to experiments conducted by the COMETE laboratory. The different aspects that need to be considered are described in the following.

The signal v(t) that represents the stimuli is defined here as the centrifuge impact on the rats behavior. The signal, before being centered, takes the value 1 when the centrifuge is on and 0 otherwise. The signal e(t) represents here other perturbations corresponding to various activities, such as for example when the rats eat.

The threshold of the first method of quantification is increased by 40% to have a suitable estimation of the resynchronization time for all rats.

The input of the model is different for the three groups because of the nature of the perturbation. It is described in the following paragraph.

1) Jet lag (SHAM and BVL) and Jet lag + 2G (only BVL) For this group, the model is computed after the convergence time t 1 of the least square algorithm. The input was set to 0 before the time perturbation time t 2 and to 1 after. This is illustrated on Fig. 3. 2) 2G and Jet lag + 2G (only SHAM)

For these groups, no model was calculated due to the impact of the centrifuge on the phase. The algorithm has been validated to ensure the unbiased convergence of estimated parameters for this experiment with the autocorrelation rate of the residuals [START_REF] Ljung | System Identification: Theory for the User[END_REF].

The results of the proposed methodology applied to the rat experiment are now presented. All results are given with their mean values and their standard deviations . 2) 2G group (SHAM) In this group, the rats were placed in a centrifuge once a day for one hour, during one week. SHAMs see their phase falling during the centrifuge time. Their resynchronization time are 8.92 (2.09) days thus they take 1.92 days to stabilize their phase after the last centrifuge Fig. 5.

3) JET LAG+2G group (BVL)

This group experience a jet lag of 8 hours and a centrifuge at the same time. The BVLs have the same variation as the JET LAG group. Thus, the BVLs seems to not feel the centrifuge as the SHAM. They have a bandwidth of 0.24 (0.05) rad/s, a delay of 5.67 (0.95) days and a resynchronization time of 17.02 (3.30) days. The results are summarized in the Table I. A comparison between the BVL of the first group and the last group shows that the rats of the third group take less time to begin their phase shift but their speed of convergence is lower than the first group.

V. CONCLUSION

The problem of defining quantifiers characterizing the dynamics of circadian rhythm variations has been considered in this paper. To this purpose, an extended COSINOR model has been proposed to take into account stimuli and external sources of disturbance. Its parameters have been estimated with a modified Least Square Algorithm that is less sensitive to the lack of persistent excitation. Based on the estimated parameters, two quantification methods have been set up to assess the dynamics of the phase. The first one, based on the phase derivative, allows to estimate a time of resynchronization. The second one allows to estimate a convergence speed, considering the phase as a step response of a second order model with a delay and a zero. Finally, the proposed method has been tested on data issued from experiments performed on rats under specific conditions.

Fig. 1 .

 1 Fig. 1. Representation of the circadian rhythm

Fig. 2 .

 2 Fig. 2. Estimation of the time of convergence

Fig. 3 .

 3 Fig. 3. Estimation of a model: Jet lag (SHAM and BVL) and Jet lag plus 2G (only BVL)

Fig. 4 .

 4 Fig. 4. Evolution of the phase of the JET LAG group during the experiment (BVL)

Fig. 5 .Fig. 6 .

 56 Fig. 5. Evolution of the phase of the 2G group during the experiment. (SHAM)

  1) JET LAG group (BVL)The rats in this group were subject to an 8 hours JET LAG. The phase evolves progressively to the new referenced hour, after a delay. The mean bandwidth is 0.34 (0.17) rad/s, the resynchronization time is 15.65(3.29), and the delay is 6.73 (2.48) days. The evolution of the phase for BVLs and SHAMs is presented below on Fig.4.

TABLE I QUANTIFIERS

 I RELATED TO CIRCADIAN RHYTHM VARIATIONS


Jie Wu
email: jie.wu@math.cnrs.fr

TWO GENERALISATIONS OF THE TITCHMARSH DIVISOR PROBLEM

Keywords: Mathematics Subject Classification. 11N05, 11N25, 11N36 Shifted prime, Friable integer, Sieve

In this paper, we considered two generalisations of the classical Titchmarsh divisor problem: friable variant and short intervals.

Introduction

As usual, denote by τ (n) the number of divisors of the integer n and by ϕ(n) the Euler totient function. The letter p is used to denote primes. The Titchmarsh divisor problem consists to evaluate the asymptotic behaviour of the counting function p x τ (p -a) for x → ∞, where a ∈ Z * is a fixed non-zero integer. This problem was studied initially by Titchmarsh [START_REF] Titchmarsh | A divisor problem[END_REF], who showed, under the Generalised Riemann Hypothesis (GRH) for the Dirichlet L-functions, .

Linnik [START_REF] Yu | The dispersion method in binary additive problems[END_REF] removed GRH by his dispersion methd. The best known result is due to Fouvry [START_REF] Fouvry | Sur le problme des diviseurs de Titchmarsh[END_REF] and Bombieri-Friedlander-Iwaniec [START_REF] Bombieri | Primes in arithmetic progressions to large moduli[END_REF], who proved, independently, for any A > 1,

p x τ (p -a) = C a x + D a x 2 dt log t + O A x (log x) A ,
where D a is certain constant depending on a. Diverse generalisations were studied by different authors. Here we only present two such generalisations:

(i) Very recently Xi [START_REF] Xi | A quadratic analogue of Titchmarsh divisor problem[END_REF] considered a quadratic analogue of (1.1) and established the following inequalities (ii) Pollack [START_REF] Pollack | A Titchmarsh divisor problem for elliptic curves[END_REF] studied analogues of (1.1) for elliptic curves and proved the following two results:

-For the CM elliptic curve E : y 2 = x 3 -x, there is an explicite constant C such that p x p≡1(mod 4) τ (|E(F p )|) ∼ Cx, as x → ∞, where |E(F p )| is the order of the group of points of the reduction at p of E.

-Let E be a non-CM elliptic curve over Q. Assume the GRH for Dedekind zetafunctions. Then for x → ∞, we have

p x * τ (|E(F p )|) E x,
where * means that the sum is restricted to primes of good reduction and the implied constants depend on E.

In this paper, we shall consider two other generalisations of the classic Titchmarsh divisor problem: friable variant and short intervals.

Firstly let us fix some notation. As usual, denote by P + (n) the largest prime factor of integer n with the convention P + (1) = 1. We say that an integer n is y-friable if P + (n) y. Let ρ(u) be the Dickman function, which is defined as the unique continuous solution of the differential-difference equation

ρ(u) = 1 (0 u 1), uρ (u) = -ρ(u -1) (u > 1).
For x 1 and y > 1, we use systematically the notation

(1.3) u := log x log y • For a ∈ Z * , q ∈ N such that (a, q) = 1 and x 1, y > 1, define π(x, y; d, a) := p x p≡a(mod d) P + ((p-a)/d) y 1,
which counts the number of primes p x in the arithmetic progression with friable indices {a + md} m y-friable . A key point to study friable variant of the Titchmarsh divisor problem (1.1) is that we need a theorem of Bombieri-Vinogradov type for π(x, y; d, a). It seems that this is a very interesting and rather difficult question, since Pomerance's conjecture (see [START_REF] Pomerance | Popular values of Euler's function[END_REF])

(1.4) π(x, y; 1, a) ∼ π(x)ρ(u)
is still open, where u := (log x)/ log y and π(x) is the number of primes x. Granville [5, Section 5.3] announced that (1.4) follows from the Elliott-Halberstam conjecture without proof. Very recently Wang [START_REF] Wang | Autour des plus grands facteurs premiers d'entiers consécutifs voisins d'un entier criblé[END_REF] gave a detailed proof of such result: Let a ∈ Z * be a fixed non-zero integer. Assuming that for any A > 0 and ε > 0 there is a positive number η = η(A, ε) such that

(EH[η]) d x 1-η p x p≡a(mod d) 1 - π(x) ϕ(d) a,A,ε
x (log x) A , then we have (1.5)

p x P + (p-a) y 1 = π(x)ρ(u){1 + O a (ε)}
for x y x ε , where the implied constant depends on a only.

Our result on the friable variant of the classic Titchmarsh divisor problem (1.1) is as follows, which is comparable with (1.5).

Theorem 1. Let a ∈ Z * be a fixed non-zero integer. For any ε > 0, there exists a positive number η = η(ε) such that if we assume the Elliott-Halberstam conjecture EH[η], we have

(1.6) p x P + (p-a) y τ (p -a) = C a π(x)(log y)(ρ * ρ)(u){1 + O a (ε)}
uniformly for x 2 and x y x ε , where the convolution of ρ and ρ is defined by

(1.7) (ρ * ρ)(u) := u 0 ρ(v)ρ(u -v) dv
and the implied constant depends on a only.

About the generalisation of (1.1) to short intervals, we have the following result.

Theorem 2. Let a ∈ Z * a fixed non-zero integer and 3 5 < θ 1. Then for x → ∞ and y = x θ , we have

(1.8) C † a (θ)y 1 + O a,θ log 2 x log x x<p x+y τ (p -a) C a (θ)y 1 + O a,θ log 2 x log x ,
where log k is the k-fold iterated logarithm,

C † a (θ) := (2θ -1)C a , C a (θ) := (2θ -1 -4 log(2θ -1))C a ,
and the implied O-constants depend on a and θ at most.

Since C † a (1) = C a (1) = C a , the inequalities (1.8) with θ = 1 become the classic asymptotic formula (1.1). The key tool for the proof of this theorem is a Bombieri-Vinogradov theorem in short intervals (see Lemma 5.1 below).

Some preliminary lemmas

Firstly we prove a preliminary lemma, which will be needed later.

Lemma 2.1. Let a ∈ Z * be a fixed non-zero integer. Then for any ε ∈ (0, 1), we have

(2.1) d x, (a,d)=1 P + (d) y 1 ϕ(d) = C a π(x)(log y) u 0 ρ(v) dv 1 + O a,ε log(u + 1) log y uniformly for (H ε ) x 3 and exp{(log 2 x) 5/3+ε } y x,
where u := (log x)/ log y and the implied constants depend on a and ε.

Proof. Define

f (d) := d/ϕ(d) if (a, d) = 1, 0
otherwise. We shall apply Lemma 2.2 below to prove (2.2)

d x P + (d) y f (d) = C a ρ(u)x 1 + O a,ε log(u + 1) log y uniformly for (x, y) ∈ H ε .
To this end, it is sufficient to verify that the function f verifies the conditions of Lemma 2.2.

With the help of the prime number theorem, it is easy to see that

p z f (p) log p = p z, p a p log p p -1 = p z log p + O a (log z) = z + O a ze -c(log z) 3/5 (log 2 z) -1/5 and p ν 2 f (p ν ) p ν p,ν 2 1 p ν (1 -p -1 ) 2π 2 3 •
This shows that f satisfies the conditions (2.3) and (2.4) of Lemma 2.2. Thus the asymptotic formula (2.2) is a particular case of this general lemma. Now the required result (2.1) follows from (2.2) by a simple partial summation.

Next we cite four lemmas, which are useful. The first one is a particular case of [14, Théorème 2.1] with κ = 1 and R(z) = e c(log z) 3/5-ε , which has been used in the proof of Lemma 2.1 above. Lemma 2.2. Let A > 0, C > 0, η ∈ (0, 1 2 ) and ε > 0. Suppose that arithmetic function f : N → R + verifies the following conditions

p z f (p) log p -z Cze -(log z) 3/5-ε , (2.3) p ν 2 f (p ν ) p (1-η)ν A. (2.4)
Then we have (2.5)

n x P + (n) y f (n) = C(f )xρ(u) 1 + O ε log(u + 1) log y uniformly for (x, y) ∈ (H ε ), where C(f ) := p (1 -1/p) ν 0 f (p ν )/p ν .
The second lemma is an elegant Brun-Titchmarsh inequality, due to Montgomery-Vaughan [START_REF] Montgomery | On the large sieve[END_REF].

Lemma 2.3. We have

(2.6) x<p x+y p≡a(mod d) 1 < 2y ϕ(d) log(y/d) uniformly for 1 < d < y x and (a, d) = 1.
The third lemma is essentially due to Lachand and Tenenbaum [START_REF] Lachand | Note sur les valeurs moyennes criblées de certaines fonctions arithmétiques[END_REF]. * Lemma 2.4. Let µ(n) be the Möbius function and let P -(n) be the largest prime factor with the convention P -(1) = ∞. For any ε > 0, we have

n x P -(n)>y µ(n) n = ρ(u) + O ε e -(log y) 3/5-ε
uniformly in

(G ε ) x 3 and exp{(log x) 2/5+ε } y x,
where u := log x/ log y and the implied constant depends on ε only.

The last lemma is due to Iwaniec [6, Lemma 3] (see also [START_REF] Fouvry | Répartition statistique des entiers sans grand facteur premier dans les progressions arithmétiques[END_REF]Lemme 4.1]). and

d|P (z) λ + d w(d) d p z p∈P 1 - w(p) p F (s) + O e √ L-s 3 √ log D (2.8) d|P (z) λ - d w(d) d p z p∈P 1 - w(p) p f (s) + O e √ L-s 3 √
log D (2.9) * In the original version of [START_REF] Lachand | Note sur les valeurs moyennes criblées de certaines fonctions arithmétiques[END_REF], there is a supplementary error term O ε exp{-(log y) 3/5-ε } . Recently de la Bretèche & Fiorilli [START_REF] De La Bretèche | Entiers friables dans des progressions arithmétiques de grand module[END_REF] have succeeded to remove this superfluous error term.

for any z ∈ [2, D], s = (log D)/ log z, the set P of primes and the multiplicative function w satisfying 0 < w(p) < p (p ∈ P), (2.10)

u<p v p∈P 1 - w(p) p -1 log v log u 1 + L log u (2 u v), (2.11)
where P (z) := p z, p∈P p, the implied O-constants are absolute and F, f are defined by the continuous solutions to the system

         sF (s) = 2e γ (1 s 2), sf (s) = 0 (0 < s 2), (sF (s)) = f (s -1) (s > 2), (sf (s)) = F (s -1) (s > 2).
Here γ is the Euler constant.

A variant of Bombieri-Vinogradov theorem

The asymptotic behaviours of π(x, y; d, a) should be an interesting new subject in the prime number theory. An initial study on this counting function can be found in a recent work of Liu, Wu & Xi [START_REF] Liu | Primes in arithmetic progressions with friable indices[END_REF]. The aim of this section is to establish (3.1) below by following their argument. We will see that it will play a key role in the proof of Theorem 1.

Proposition 3.1. Let a ∈ Z * be a fixed non-zero integer, η ∈ (0, 1), ε > 0 and A > 0. Assuming the Elliott-Halberstam conjecture EH[η], the following estimate

(3.1) d √ x (a,d)=1 P + (d) y π(x, y; d, a) - π(x) ϕ(d) ρ log(x/d) log y a,A,ε x (log x) A + π(x)(log y)ηu u/2 0 ρ(v) dv
holds uniformly for η ∈ (0, 1) and (x, y) ∈ G ε , where the implied constant depends on a, A and ε only. Firstly we treat π 1 (x, y; d, a). We note, via writing q = d ,

(3.3) d √ x (a,d)=1 P + (d) y π 1 (x, y; d, a) - x 1-η /d P -( )>y µ( ) ϕ(d ) π(x) q x 1-η (a,q)=1
τ (q) π(x; q, a) -π(x) ϕ(q) .

Trivially, for all q x 1-η , we have π(x; q, a) + π(x) ϕ(q)

x q • Hence q x 1-η (a,q)=1 τ (q) 2 π(x; q, a) -π(x) ϕ(q) x q x 1-η τ (q) 2 q x(log x) 4 . Noticing that (d, ) = 1 and using Lemma 2.4, we can write Inserting it into the proceeding relation, it follows that

By (3.3) and the

π(x) ϕ(d) x 1-η /d P -( )>y µ( ) ϕ( ) = π(x) ϕ(d) x 1-η /d P -( )>y µ( ) 1 + O 1 y = π(x) ϕ(d) ρ log(x 1-η /d) log y 1 + O ε log(u +
(3.5) π(x) ϕ(d) x 1-η /d P -( )>y µ( ) ϕ( ) = π(x) ϕ(d) ρ log(x/d) log y {1 + O(ηu log(u + 1))} for all (x, y) ∈ G ε and d √ x.
With the help of (2.1), a simple partial integration gives us

(3.6) d √ x (a,d)=1 P + (d) y 1 ϕ(d) ρ log(x/d) log y = π(x) √ x-a 1- ρ log(x/t) log y d d t, (a,d)=1 P + (d) y 1 ϕ(d) = C a π(x)(log y) u/2 0 ρ(v)ρ(u -v) dv 1 + O a,ε log(u + 1) log y = C a 2 π(x)(log y)(ρ * ρ)(u) 1 + O a,ε log(u + 1) log y
for (x, y) ∈ H ε , we have used the trivial relation

u/2 0 ρ(v)ρ(u -v) dv = 1 2 u 0 ρ(v)ρ(u -v) dv = 1 2 (ρ * ρ)(u).
Combining (3.5) with (3.4) and using (3.6) to bound the contribution of the error term in (3.5), we can find

(3.7) d √ x (a,d)=1 P + (d) y π 1 (x, y; d, a) - π(x) ϕ(d) ρ log(x/d) log y a,A,ε x (log x) A + π(x)(log y)(ρ * ρ)(u)ηu log(u + 1)
for all (x, y) ∈ G ε and η ∈ (0, 1), provided we assume EH [η].

We now turn to π 2 (x, y; d, a). For p -a = d m, we have (a, m) = 1 and m x η subject to the restrictions in π 2 (x, y; d, a). We have trivially

|π 2 (x, y; d, a)| x 1-η /d< (x-a)/d P -( )>y π(x; d , a) m x η (a,m)=1 p x, p≡a(mod dm) P -((p-a)/dm)>y 1.
We are now in a position to apply sifting arguments subject to the target sequence A(x; dm, a) := {(p -a)/dm : p x and p ≡ a (mod dm)}.

Trivially we have, with the notation P 2 (y) := 2<p y p,

|π 2 (x, y; d, a)| m x η (a,m)=1 n∈A(x;dm,a) (n,P 2 (y))=1
1.

Let {λ + q } q 1 be an upper bound sieve of level Q as in Lemma 2.5, so that

|π 2 (x, y; d, a)| m x η (a,m)=1 n∈A(x;dm,a) q|(n,P 2 (y)) λ + q = q Q q|P 2 (y) λ + q m x η (a,m)=1
π(x; dmq; a).

We may take Q = x 1/2-2η such that √ xQx η = x 1-η . As before, we may approximate π(x; dmq; a) on average over d, m, q and apply the the Elliott-Halberstam conjecture EH[η]. Similar to (3.3), we can prove

d √ x (a,d)=1 P + (d) y q Q q|P 2 (y) |λ + q | m x η (a,m)=1 π(x; dmq; a) - π(x) ϕ(dmq) a,A x (log x) A
for all x 2 and y > 1. It now follows that

d √ x (a,d)=1 P + (d) y |π 2 (x, y; d, a)| π(x) d √ x (a,d)=1 P + (d) y m x η (a,m)=1 1 ϕ(dm) q Q q|P 2 (y) λ + q ϕ(q) + O a,A x (log x) A .
From Lemma 2.5, Mertens' formula and the inequality ϕ(dm) ϕ(d)ϕ(m), we derive

(3.8) d √ x (a,d)=1 P + (d) y |π 2 (x, y; d, a)| a,A π(x) d √ x P + (d) y m x η 1 ϕ(dm) 2<p<y p -2 p -1 + x (log x) A a,A π(x) log y d √ x P + (d) y 1 ϕ(d) m x η 1 ϕ(m) + x (log x) A a,A,ε π(x)(log y)ηu u/2 0 ρ(v) dv + x (log x) A
for all (x, y) ∈ H ε and η ∈ (0, 1). Now the required result follows from (3.7)-(3.8) and the trivial inequality

(3.9) (ρ * ρ)(u) 2ρ u 2 u/2 0 ρ(v) dv 1 log(u + 1) u/2 0 ρ(v) dv.
This completes the proof of Proposition 3.1.

Proof of Theorem 1

In view of the symmetry of divisors of integer n, we have 2) and using (3.9), we find that (4.6) for some constant λ > 0. Define

p x P + (p-a) y τ (p -a) = C a π(x)(log y)(ρ * ρ)(u) 1 + O a,ε log(u + 1) log y + O a,A,ε x (log x) A + π(x)(log y)ηu
H(z, h, d, a, ) := p z+h p≡a(mod d) 1 - p z p≡a(mod d) 1 - 1 ϕ(d) (z+h)/ z/ dt log t •
Then for any 3 5 < θ 1 and A > 0, there exists a constant B = B(θ, A) > 0 such that the inequality

(5.2) d D max (a,d)=1 max h y max x/2<z x L, ( ,d)=1 g( )H(z, h, d, a, ) θ,ε y (log x) A holds for x 3, D := x θ-1/2 /(log x) B and L = x (5θ-3)/2 .
In view of (4.1), we have trivially 1.

τ (n) =
In the preceding subsection, we have proved that (5.9) M + R = (θ -1 2 )C a y 1 + O log 2 x log x .

On the other hand, by the Brun-Titchmarsh inequality (2.6), it follows that S < New the upper bound in (1.6) follows from (5.9), (5.10) and (5.8). This completes the proof of Theorem 2.

τ

  (p -a) ∼ C a x for x → ∞, where C a

Lemma 2 . 5 .D 2 .

 252 Let There are two sequences {λ ± d } d 1 , vanishing for d > D or µ(d) = 0, verifying |λ ± d | 1, such that (

  Proof. Let P := y<p (x-a)/d p. The Möbius inversion formula allows us to write (3.2) π(x, y; d, a) = p x p≡a(mod d) |(P,(p-a)/d) µ( ) = (x-a)/d P -( )>y µ( )π(x; d , a) = π 1 (x, y; d, a) + π 2 (x, y; d, a), where π 1 (x, y; d, a) := x 1-η /d P -( )>y µ( )π(x; d , a), π 2 (x, y; d, a) := x 1-η /d< (x-a)/d P -( )>y µ( )π(x; d , a).

  Cauchy-Schwarz inequality, this bound and the Elliott-Halberstam conjecture EH[η] with 2A + 4 in place of A allow us to derive that (3.4) d √ x (a,d)=1 P + (d) y π 1 (x, y; d, a)x 1-η /d P -x) A for all x 1 and y > 1.

  + (p-a) y τ (p -a) = 2 d (x-a) 1/2 (a,d)=1, P + (d) y p x p≡a(mod d) P ((p-a)/d) y 1 + p x P + (p-a) y δ (p -b)= 2(M + R 1 ) + R 2 ,whereM := d √ x-a (a,d)=1, P + (d) y d)=1, P + (d) y π(x, y; d, a) -π(x) ϕ(d) ρ log(x/d) log y , R 2 := p x P + (p-a) y δ (p -b).By noticing that δ (p -b) = 1 ⇒ p -b = n 2 , we have trivially (4.3) R 2 2 √ x uniformly for x 1 and y > 1. According to Proposition 3.1, we have (4.4) R 1 a,A,ε x (log x) A + xρ u 2 ηu uniformly for (x, y) ∈ G ε . Finally according to (3.6), we have (4.5) M = C a 2 π(x)(log y)(ρ * ρ)(u) 1 + O a,ε log(u + 1) log y for (x, y) ∈ H ε . Now inserting (4.4), (4.3) and (4.5) into (4.

u/ 2 0 5 .5. 1 .Lemma 5 . 1 .

 25151 ρ(v) dv uniformly for (x, y) ∈ G ε and η ∈ (0, 1). Clearly (4.6) implies the required result (1.6) Proof of Theorem 2 Lower bound. Firstly we prove the lower bound in (1.6). Our principal tool is a mean value theorem of Bombieri-Vinogradov type in short intervals, due to Wu [17, Théorme 1.2]. Let g( ) be an arithmetic function satisfying the condition (5.1) x |g( )| 2 / (log x) λ (x 2)

5 . 2 .

 52 By using (2.1) with y = x, it follows that (5.7)M = (θ -1 2 )C a log x + O(log 2 x) and (5.6) into (5.3), we obtain the lower bound in (1.6). Upper bound. Now we prove the bound bound in (1.6). By (4.1), we write (5.8) x<p x+y τ (p -a) 2 x<p x+y d|(p-a) d< √+ R + S + √ x),where M and R are defined as in (5.4)-(5.5) andS := x θ-1/2/(log x) B <d √ 3x x<p x+y p≡a(mod d)

x θ- 1 / 2 / 5

 125 (log x) B <d √ 3x 2y ϕ(d) log(y/d) = 2y log y x θ-1/2 /(log x) B <d √ 3x 1 ϕ(d)(1 -(log d)/ log y) •In view of (2.1) with y = x, a simple partial integration allows us to deduce that (log 2 x log x 2 log(2θ -1) -1 C a y.

Acknowledgement. This work is partially supported by NSFC (Grant N • 11771121).


J Wu
email: jie.wu@math.cnrs.fr

ON A SUM INVOLVING THE EULER TOTIENT FUNCTION

Keywords: Mathematics Subject Classification. 11N36, 11L05. Key words and phrases. Euler totient function, exponential sums, exponent pair

In this short note, we prove that 4 π 2 x log x + O(x)

for x → ∞, where ϕ(n) is the Euler totient function and [t] is the integral part of real t. This improves recent results of Bordellès-Heyman-Shparlinski and of Dai-Pan.

Introduction

As usual, denote by ϕ(n) the Euler totient function and by [t] the integral part of real t. Very recently, Bordellès, Heyman and Shparlinski [START_REF] Bordellès | On a sum involving the Euler function[END_REF] studied the asymptotic behaviour of the summatory function They also posed a question: Is it true that (1.4) S(x) = 6 π 2 + o(1) x log x as x → ∞ ? Some numerical evidences were given. The aim of this short note is to improve Bordellès, Heyman and Shparlinski's (1.2) and (1.3), by refining their method. Our result is as follows.

Theorem 1. We have

(1.5) 4 π 2 x log x + O(x) S(x) 1 3 + 4 π 2 x log x + O(x) for x → ∞.
For comparison, we have    [START_REF] Bordellès | On a sum involving the Euler function[END_REF], the proof of (1.2) is rather elementary. But the lower bound (1.3) uses a much deeper approach relying on the theory of exponential pairs. In particular, to obtain the numerically stronger result, they used the recently discovered exponent pair ( 13 84 + ε, 55 84 + ε) by Bourgain [START_REF] Bourgain | Decoupling, exponential sums and the Riemann zeta function[END_REF]. We infer the reader to [START_REF] Graham | Van der Corput's Method of Exponential sums[END_REF]Chapter 3,page 31] for the definition of the exponent pair.

Let ψ(t) := t -[t] -1 2 and δ ∈ {0, 1}. For x 2 and 1 D x, define (1.6)

S δ (x, D) := D<d 2D ϕ(d)ψ x d + δ .
The key of Bordellès, Heyman and Shparlinski's method is to find θ as large as possible such that

(1.7) S δ (x, x θ ) x.
They shew that θ = 2629 4009 ≈ 0.65577 is admissible and obtained the constant θ 6 π 2 in the lower bound (1.3).

Our improvements come from two simple observations: (a) Firstly we give a more careful treatment for the related exponential sum (see Proposition 2.1 below). This allows us to show that θ = 2 3 ≈ 0.66666 is admissible for (1.7) and to get a better lower bound. It is worth to note that our argument is simpler and that we do not need to use Bourgain's new exponent pair. In fact we only use the simplest exponent pair ( 12 , 1 2 ), i.e. van der Corput inequality. (b) Our argument about upper bound part is different from [START_REF] Bordellès | On a sum involving the Euler function[END_REF]. In order to improve upper bound (1.2), we introduce exponential sum technique to show that the constant in the upper bound can be improved to 1 -θ + θ 6 π 2 with θ = 2 3 . It is clear that Bordellès-Heyman-Shparlinski 's conjecture is equivalent to (1.7) with θ = 1. This seems rather difficult to prove, since this requires a square root cancellation in S δ (x, x). (By (3.4) below, the trivial upper bound of S δ (x, x) is O(x 2 ).) However it should be possible to further improve slightly the constants in Theorem 1 by applying combinatorial identity on the Möbius function and more sophistic methods of multiple exponential sums (see [START_REF] Fouvry | Exponential sums with monomials[END_REF][START_REF] Wu | Almost primes in short intervals[END_REF]).

When we redact our manuscript, we note that Lixia Dai & Hao Pan [START_REF] Dai | Note on a sum involving the Euler function[END_REF] also have remarked (b) above and obtained a better upper bound constant 1380 4009 + 2629 4009 6 π 2 ≈ 0.74288 than (1.2) by using Bordellès, Heyman and Shparlinski's θ = 2629 4009 value.

A key estimate

The aim of this section is to prove the following bound for S δ (x, D), which plays a key role in the proof of Theorem 1.

Proposition 2.1. Under the previous notation, we have

(2.1) S δ (x, D) (x κ D 1+λ ) 1/(κ+1) + x κ D 1-2κ+λ log x + x -1 D 3 ,
where (κ, λ) is an exponent pair.

Two preliminary lemmas.

In order to prove Proposition 2.1, we need two standard lemmas in the exponential sum theory. The first one is due to Vaaler (see [START_REF] Graham | Van der Corput's Method of Exponential sums[END_REF]Theorem A.6] or [1, Lemma 4.1]).

Lemma 2.2. For x 1 and H 1, we have

ψ(x) = - 1 |h| H Φ h H + 1 e(hx) 2πih + R H (x),
where e(t) := e 2πit , Φ(t) := πt(1 -|t|) cot(πt) + |t| and the error term R H (x) satisfies

|R H (x)| 1 2H + 2 0 |h| H 1 - |h| H + 1 e(hx).
The second lemma is [START_REF] Graham | Van der Corput's Method of Exponential sums[END_REF]Lemma 2.4]. With the help of Lemma 2.2 (separating the terms with h = 0 or h = 0 in R H (x)) and noticing the fact that 0 < Φ(t) < 1 (0 < |t| < 1), we can derive

Lemma 2.3. Let L(Q) := J j=1 C j Q c j + K k=1 D k Q -d k , where C j , c j , D k , d k > 0. For any Q Q > 0, there exists some Q 1 ∈ [Q , Q] such that L(Q 1 ) J j=1 K k=1 (C d k j D c j k ) 1/(c j +d k ) + J j=1 C j Q c j + K k=1 D k Q -d k .
S δ (x, D, m, N ) N H + h H 1 h D/m<n N e hx mn + δ for D/m < N 2D/m and 1 H N .
Applying the exponent pair (κ, λ) to the inner sum over n, we find that

S δ (x, D, m, N ) N H + h H 1 h hx mN 2 κ N λ + mN 2 hx H -1 N + x κ H κ m -κ N -2κ+λ + x -1 mN 2 for all H ∈ [1, N ]. According to Lemma 2.3, there is a H ∈ [1, N ] such that S δ (x, D, m, N ) (x κ m -κ N -κ+λ ) 1/(κ+1) + x κ m -κ N -2κ+λ + x -1 mN 2 (x κ D -κ+λ m -λ ) 1/(κ+1) + x κ D -2κ+λ m κ-λ + x -1 D 2 m -1 .
Inserting it into (2.2), we obtain the required result.

Proof of Theorem 1: Upper bound

Let 1 N < √ x be a parameter to be chosen later. We write

(3.1) S(x) = S 1 (x) + S 2 (x) with S 1 (x) := n N ϕ x n , S 2 (x)
S 2 (x) = d x/N ϕ(d) x/(d+1)<n x/d 1 = d x/N ϕ(d) x d -ψ x d - x d + 1 + ψ x d + 1 = x d x/N ϕ(d) d(d + 1) + d x/N ϕ(d) ψ x d + 1 -ψ x d .
It is well known that (3.4)

n x ϕ(n) n 2 = 6 π 2 log x + O(1), n x ϕ(n) = 3 π 2 x 2 + O(x log x).
With the help of these, it follows that (3.5)

d x ϕ(d) d(d + 1) = d x ϕ(d) d 2 1 + O 1 d = 6 π 2 log x + O(1)
and

(3.6) d √ x ϕ(d) ψ x d + 1 -ψ x d 2 d √ x ϕ(d) x.
It remains to bound

E(x, N ) := √ x<d x/N ϕ(d) ψ x d + 1 -ψ x d .
Let D k := x/(2 k N ) and let K be the integer such that D K+1 < √ x D K . By a simple dyadic split and by Proposition 2.1 with (κ, λ) = ( 12 , 1 2 ) (see [START_REF] Graham | Van der Corput's Method of Exponential sums[END_REF]Theorem 3.10 or 2.2]), it follows that

(3.7) |E(x, N )| 1 k K+1 (|S 0 (x, D k )| + |S 1 (x, D k )|) 1 k K+1 x 1/3 D k + x 1/2 D 1/2 k log x + x -1 D 3 k x 1/3 (x/N ) + x 1/2 (x/N ) 1/2 log x + x -1 (x/N ) 3 x 4/3 N -1 + xN -1/2 log x + x 2 N -3 .
Inserting (3.5), (3.6) and (3.7) into (3.3), we find

(3.8) S 2 (x) 6 π 2 x log(x/N ) + O x 4/3 N -1 + xN -1/2 log x + x 2 N -3 .
C. End of the proof Inserting (3.2) and (3.8) into (3.1), we find that

S(x) x log N + 6 π 2 x log(x/N ) + O x 4/3 N -1 + xN -1/2 log x + x 2 N -3 + x ,
which becomes, with the optimal choice of N = x 1/3 , S(x) The required result follows from the optimal choice of D = x 2/3 .

1 3 + 4 π 2 x log x + O(x).

2

 2 + o(1) x log x (x → ∞). (1.3)

2. 2 .

 2 Proof of Proposition 2.1. As usual, denote by µ(n) the Möbius function. By using the relation ϕ(d) = mn=d µ(m)n and by a simple partial summation, we can write (2.2) S δ (x, D) =

  N + O(x). B. Upper bound of S 2 (x) In order to bound S 2 (x), we put d = [x/n]. Then x/n -1 < d x/n and x/(d + 1) < n x/d.

4 . 2 x 2 k 3 k x 1 / 3 D

 422313 Proof of Theorem 1: Lower bound Similar to (3.3), we can write S(x) = d x ϕ(d) x/(d+1)<n x/d log D + O(x) + R(x, D), where R(x, D) Let D k := D/2 k and let K be the integer such that D K+1 < 1 D K . By a simple dyadic split and by Proposition 2.1 with (κ, λ) = ( 1 2 , 1 2 ), it follows that (4.2)|R(x, D)| 1 k K+1 (|S 0 (x, D k )| + |S 1 (x, D k )|) 1 k K+1 x 1/3 D k + x 1/2 D 1/log x + x -1 D + x 1/2 D 1/2 log x + x -1 D 3 .Inserting (4.2) into (4.1), we find S(x) 6 π 2 x log D + O x 1/3 D + x 1/2 D 1/2 log x + x -1 D 3 .

Acknowledgements. This work is supported in part by Scientific Research Innovation Team Project Affiliated to Yangtze Normal University (No. 2016XJTD01). The author is thankful to Lixia Dai at Nanjing Normal University (China) for drawing his attention to Bordellès, Heyman and Shparlinski's paper [1].