Mathematical Notes, vol. 76, no. 2, 2004, pp. 244–263. Translated from Matematicheskie Zametki, vol. 76, no. 2, 2004, pp. 265–285. c Original Russian Text Copyright 2004 by N. M. Timofeev, M. B. Khripunova.
The Concentration Function of Additive Functions with Special Weight N. M. Timofeev † and M. B. Khripunova Received November 10, 2001
Abstract—Suppose that g(n) is an additive real-valued function, 1 W (N ) = 4 + min λ2 + min(1, (g(p) − λ log p)2 ) , p λ
E(N ) = 4 +
p
1 . p
p
In this paper, we prove the existence of constants C1 , C2 such that the following inequalities hold: C N sup |{n, m, k : m, k ∈ Z, n ∈ N, n + m2 + k2 = N , g(n) ∈ [a, a + 1)}| ≤ 1 , a W (N ) C N . sup |{n, m, k : m, k ∈ Z, n ∈ N, n + m2 + k2 = N , g(n) = a}| ≤ 2 a E(N ) The obtained estimates are order-sharp. Key words: concentration function of additive functions, prime divisor, coprime integers, Ruzsa’s inequality, Dirichlet character.
1. INTRODUCTION AND STATEMENT OF THE RESULTS Suppose that g(n) is an additive function, τ (n) is the number of divisors of n , and r(n) is the number of representations of n as the sum of the squares of two integers. In a previous paper, using results from Rusza’s paper [1] and ideas and methods from the papers by Elliott [2] and Timofeev [3], we proved the following theorem. Theorem [4, Theorem 1]. There exists an absolute constant C such that for any additive function g(n) the following inequality is valid : sup a
where
τ (N − n) ≤
n
CN log(2N ) , W (N )
1 min(1, (g(p) − λ log p)2 ) . W (N ) = 4 + min λ2 + λ p p
It was proved in Theorem 1 [4] that N log(2N ) . sup |{n, m, k : n, m, k ∈ N, N = n + mk, g(n) ∈ [a ; a + 1)}| ≤ C a W (N ) 244
0001-4346/2004/7612-0244
c 2004 Plenum Publishing Corporation
THE CONCENTRATION FUNCTION OF ADDITIVE FUNCTIONS
245
It is readily seen from this theorem that (see [4, Corollary 1]) N log(2N ) sup |{n, m, k : n, m, k ∈ N, N = n + mk, g(n) = a}| ≤ C , a E(N ) where E(N ) =
1 + 4. p
p
The goal of the present paper is to prove the following theorem. Theorem 1. There exists an absolute constant C such that for any additive function g(n) the following inequality is valid :
sup a
n
N . r(N − n) ≤ C W (N )
In Theorem 1, an estimate is given for the number of solutions of the following binary problem: N = n + m2 + k 2 ,
where
g(n) ∈ [a ; a + 1),
m, k ∈ Z ;
here the obtained estimate is uniform in a and g . From Theorem 1, we obtain the following consequence (see [4, Proof of Corollary 1]). Corollary 1. There exists an absolute constant such that
sup a
n
N r(N − n) ≤ C . E(N )
Here, in the same way as in [4], we shall prove this in the most complicated case. Somewhat simpler is the proof of the following assertion. Theorem 2. Suppose that b = 0 is an integer. There exists a constant depending only on b such that for any additive function g(n) the following inequality is valid :
sup a
0
N . r(n + b) ≤ C W (N )
From this theorem, we obtain the following assertion. Corollary 2. There exists a constant C depending only on b such that for any additive function g(n) the following inequality is valid : sup a
r(n + b) ≤ C(b)
0
N E(N )
.
We can show that these results cannot, in general, be improved. Indeed, Theorem 1 from [5] asserts that, for k ≤ (2 − ε) log log N , the following relation is valid: ν(N , k) := |{n : N = n + m2 + l2 , m, l ∈ Z, Ω(n) = k}| ∼ C(N , k) MATHEMATICAL NOTES
Vol. 76
No. 2
2004
N (log log N )k−1 , log N (k − 1)!
246
N. M. TIMOFEEV, M. B. KHRIPUNOVA
where Ω(n) is the number of prime divisors of n , counting multiplicity. If k = [log log N ] , then C(N , k) ≥ c1 > 0 , and hence from Stirling’s formula we have N N (log log N )k−1 , ≥ c2 √ log N (k − 1)! log log n
c2 > 0 ;
this yields ν(N , k) ≥ c1 c2 √
N . log log N
In the case g(n) = Ω(n) , we have W (N ) = E(N ) = log log N , i.e., the estimates in Theorem 1 and Corollaries 1 are order-sharp. 2. AUXILIARY RESULTS By p(n) and q(n) we denote the largest and smallest prime divisors of n , respectively. Let p(1) = q(1) = 1 . Lemma 1. Suppose that 2 ≤ r ≤ x . Then
log x . |{n : n ≤ x, p(n) ≤ r}| x exp − 2 log r
The proof of this lemma is given, for example, in [6, Chapter III.5, Theorem 1]. Lemma 2. Suppose that r ≥ 2 , z ≥ 2 . Then 1 1 log z exp − log r, n 2 log r
p(n)≤r , n>z
p(n)≤r , n>z
1 1 log z exp − log2 r. ϕ(n) 4 log r
Proof. Using Lemma 1, we obtain p(n)≤r , n>z
1 1 ≤ |{n : n ≤ 2k+1 z , p(n) ≤ r}| n 2k z k≥0
k≥0
1 log z 1 log z log 2 k + 1 exp − exp − log r. exp − 2 log r 2 log r 2 log r
We prove the second relation of Lemma 2. Suppose that y = exp(log z/(4 log r)) . We have p(n)≤r , n>z
n 1 = ϕ(n) n
p(n)≤r , n>z
1 µ2 (δ) µ2 (δ) ≤ n ϕ(δ) δϕ(δ) δ|n
δ≤y
1 log z log2 r. exp − 4 log r
Lemma 2 is proved.
p(n)≤r , n>z/y
1 µ2 (δ) 1 1 + n y ϕ(δ) n p(δ)≤r
p(n)≤r
Lemma 3. Suppose that χ is a nonprincipal Dirichlet character modulo 4 and log m r log r , r ≥ 2 . Then χ(n) log y log m = 1 + O exp − log r + . n 2 log r r n≤y , (n,m)=1, q(n)>r
MATHEMATICAL NOTES
Vol. 76
No. 2
2004
THE CONCENTRATION FUNCTION OF ADDITIVE FUNCTIONS
247
Proof. Let m(r, y) be the product of prime divisors of m such that r < p ≤ y . Hence
:=
χ(l)µ(l) χ(n) = n l
n≤y , (n,m)=1, q(n)>r
Since
l≤y , p(l)≤r
χ(n) n≤t
n
we obtain
χ(l)µ(l) = l l≤y , p(l)≤r
δ≤y/l, δ|m(r ,y)
=
p
δ≤y/l, δ|m(r ,y)
χ(p) 1− p
−1
χ(δ)µ(δ) δ
n≤y/(lδ)
χ(n) . n
1 +O , t
−1 χ(p) 1 χ(δ)µ(δ) 1− +O δ p y p
−1 χ(p) 1− +O = p p>r
1 1 + l l
l>y , p(l)≤r
l≤y , p(l)≤r
δ|m(r ,y)
1
l≤y , δ≤y/l, p(l)≤r δ|m(r ,y)
1 1 − 1 + 1 . δ y l≤y , p(l)≤r
The product on the right-hand side of the last relation is equal to 1 χ(p) χ(p) exp − = exp +O . log 1 − p p r p>r p>r Since (see, for example, [7, Corollary 1, p. 154]) χ(p) = 1− p≤t
p≤t, p≡1 (mod 4)
1 = O(t exp(−c
log t )),
p≤t, p≡3 (mod 4)
where c > 0 , after the Abel summation we find that the product is equal to c > 0. 1 + O(exp(−c log r )), Since
δ|m(r ,y)
1 log m 1 − 1 exp −1 , δ p r log r p|m, p>r
applying Lemmas 1 and 2, we obtain Lemma 3 is proved.
1 log y log m = 1 + O exp − log r + . 2 log r r
From [8, Theorem 3.4], we obtain the following assertion. Lemma 4. Suppose that k ≤ xα , 0 < α < 1 , and 2 ≤ z log z ≤ |{n : n ≡ l (mod k), p(n) ≥ z}|
√
x1−α . Then
x . ϕ(k) log z
By H(x, y , z) we denote the number of positive integers n ≤ x having at least one divisor d , y < d ≤ z . Then from [9, Theorem 21] (see also [9, inequality 2.2, p. 28]), we obtain the following assertion. MATHEMATICAL NOTES
Vol. 76
No. 2
2004
248
N. M. TIMOFEEV, M. B. KHRIPUNOVA
Lemma 5. If 3 ≤ y ≤
√
x , then H(x, y , 2y)
(log y)β
x √
log log y
,
where β = 1 − (1 + log log 2)/ log 2 = 0.08607 . . . . Lemma 6. Suppose that χ is a√nonprincipal Dirichlet character of the modulus of k . Then for √ 2 ≤ ∆ ≤ x1/10 , y(x, m) = m∆/ x , or x/∆ we have (log(∆ log x))3/2 χ(d) x . (log x)β/2 (log log x)1/2 √ m≤x y(x,m)
Proof. To prove the lemma, we use the Hooley method (see [10, Chap. 5]). Applying Cauchy’s inequality, we obtain χ(d) ≤ , 1 2 √ m≤x y(x,m)
where
1
For
1,
x √ , x∆ , := H x, ∆ √
2
=
√ m≤x y(x,m)
2 χ(m) .
we have
1
√ √ √ √ √ x x √ x , x + H(x, x, x ∆) ≤ 2H x, 2 , x + ≤ H x, ∆ ∆ log x ∆ log x √ √ x x x j j+1 ,2 + , H x, 2 2 ≤2 2 ∆ log x ∆ log x ∆ log x 0≤j≤J
where J = O(log(∆ log x)) . Applying Lemma 5, we obtain 1
x(log(∆ log log x) √ . (log x)β log log x
(1)
√ After squaring and rearranging the order of summation, for y(x, m) = m∆/ x we obtain 2
where
=
χ(d1 )χ(d2 )
√
√ x ∆
1,
m≤z(x,d1 ,d2 ), m≡0 (mod [d1 ,d2 ])
√ √ √ √ d1 x d2 x d1 x d2 x , , x = min , . z(x, d1 , d2 ) = min ∆ ∆ ∆ ∆
Therefore, we have 2
= √
√ x ∆
χ(d1 )χ(d2 )
z(x, d1 , d2 ) + O(1) . [d1 , d2 ]
MATHEMATICAL NOTES
Vol. 76
No. 2
2004
THE CONCENTRATION FUNCTION OF ADDITIVE FUNCTIONS
249
Let δ = (d1 , d2 ) . Then d1 = δm1 , d2 = δm2 , (m1 , m2 ) = 1 , [d1 , d2 ] = δm1 m2 , and χ(m1 )χ(m2 ) = z(x, δm1 , δm2 ) + O(1) . 2 δm1 m2 √ √ √ x x∆ δ≤ x ∆
, δ∆
The sum obtained by summing O(1) is
x
√
δ≤∆4
√ x/(δ∆)≤m1 ≤ x ∆/δ
Abel summation yields
1 1 + x∆2 x log2 ∆. 2 δm1 δ 4 δ>∆
χ(m) 1 . m u
u
Therefore,
u
χ(m) χ(d)µ(d) = m d d|a
τ (a) χ(m) . m u
u/d
(2)
Taking (2) into account, we find that the first sum has the upper bound √ x χ(m2 ) √ χ(m1 ) 2 + x∆ √ √ ∆ m2 √ δ≤ x ∆
√
x/(δ∆)
x ∆
√ √ δ≤ x ∆ m1 ≤ x ∆
√ τ (m1 ) √ x + x∆ m1 ∆
2
log x +
√
x ∆ log (∆ log x) 2
√
δ≤ ∆ logx2 x
δ
x log (∆ log x). 2
Thus,
2
x log2 (∆ log x)
and, therefore, taking (1) into account, we obtain the assertion of Lemma 6. If y(x, m) = then z(x, d1 , d2 ) = x , and again applying (2), we obtain 2
x
√ δ≤ x ∆
x
1 δ√
√
x δ≤ ∆4 log 4x
√ x/(δ∆)≤m1 ≤ x ∆/δ
τ (m1 ) + x log2 ∆ m21
1 1 log2 x + δ ∆3 log4 x
√ √ x ≤δ≤ x ∆ ∆4 log4 x
1 + log2 ∆ δ
√
x/∆ ,
x log2 (∆ log x). Hence, taking (1) into account, we again obtain the assertion of the lemma. Lemma 6 is proved. Lemma 7. Suppose that {an } , {bm } are sequences of complex numbers such that an = 0 for n ≤ z1 , bm = 0 for m ≤ z2 , and d1 , d2 are positive integers, with p(d1 ) ≤ z , q(d2 ) > z . Then 1 max an bm − an bm ∆(Q) := ϕ(d2 ) (a,d)=1 d=d1 d2 ≤Q
MATHEMATICAL NOTES
nm≤x, nm≡a (mod d)
Vol. 76
No. 2
2004
nm≤x, (nm,d2 )=1, nm≡a (mod d1 )
250
N. M. TIMOFEEV, M. B. KHRIPUNOVA
1 logA x +
k≤2x
2 1/2 |an bm |
nm=k
|k−x|≤x/(logA x)
1/2 √ (Q + x log3/2 x) |an bm | 2
nm=k
1/2 1 2 2 |an | |bm | + (log log x) max y≤x x n≤y m≤x/y √ x x x x x 2 log Q + (log Q) log , × Q x log + √ +√ z1 z2 z2 z1 z z1 z2 where A is an arbitrary positive constant. The proof of this lemma was given in [4]. We shall need the Halasz theorem. We present it in the form proved in [6, Chap. 4, Corollary 6.3]. Lemma 8. There exists an absolute constant c such that for any multiplicative function f , |f (n)| ≤ 1 , the following inequality is valid : 1 − Re f (p)p−it 1 1 f (n) ≤ cx exp − min . +√ 2 |t|≤T p T n≤x
p≤x
The following two lemmas were proved in [4, Lemmas 3, 4]. Lemma 9. Let |f (p)| ≤ 1 for all primes p . Suppose that there exists a primitive character of the modulus of δ , δ ≤ log2 N , and a real number λ0 , |λ0 | ≤ log2 N , such that 1 1 (1 − Re f (p)p−iλ0 χδ (p)) ≤ log log N. p 100 p≤N
Then, for |λ| ≤ log2 N , all the Dirichlet characters χd , with d ≤ log2 N , not generated by χδ satisfy the inequality 1 1 (1 − Re f (p)p−iλ χd (p)) ≥ log log N + O(1). p 2 p≤N
Lemma 10. There exists an absolute constant c > 0 such that for any multiplicative function f , |f (n)| ≤ 1 , the following inequality holds: 1/2 1 + log d 1 ϕ(N ) 1 −1/4 |f (p) − 1| . f (n) − f (n) ≤ cx (log x) exp N d 2 p n≤x, (n,N )=1
n≤x
p≤x
d|N
Finally, we need the Rusza Theorem [1] whose analogs are the results in [2–4] and in the present paper. Lemma 11. There exists an absolute constant such that for any additive function the following inequality is valid : 1 c , sup |{n : n ≤ x, a ≤ g(n) < a + 1}| ≤ x a W (x) where
1 2 2 min(1, (g(p) − λ log p) ) . W (x) = 4 + min λ + λ p p≤x
MATHEMATICAL NOTES
Vol. 76
No. 2
2004
THE CONCENTRATION FUNCTION OF ADDITIVE FUNCTIONS
251
3. PROOF OF THEOREM 1 Let P1 be the set of positive integers all of whose prime divisors are congruent to 1 modulo 4, to 3 and let P3 be the set of positive integers that are divisible by 2 and by primes congruent
modulo 4. Further, let L = log N . It is well known that r(n) = 4r1 (n) , where r1 (n) = d|n χ(d) , χ is a nonprincipal Dirichlet character modulo 4. We have
S(N ) :=
r(N − n) = 4
n
r1 (δ)
δ∈P3
n∈A(N ,g ,a,δ)
r1
N −n , δ
where N −n ∈ P1 , g(n) ∈ [a ; a + 1) . A(N , g , a, δ) = n : n < N , n ≡ N (mod δ), δ Note that if m ∈ P1 , then r1 (m) = τ (m) , and we estimate the part of the sum S(N ) in which δ ≥ u = log3 L . Since (see, for example, [9, Theorem 0.1]) m∈P1 , m≤x
x τ (m) log x
1+
∞ τ (pr ) r=1
p≡1 (mod 4), p≤x
pr
x,
we find that this part of the sum S(N ) is
r1 (δ)
δ≥log3 L
∞ N N N r1 (pr ) 1+ . 2r/3 δ log L p log L p r=1
Since τ (m · n) ≤ τ (m) · τ (n) , we have S(N ) ≤ 4
δ≤u, δ∈P3
r1 (δ)
τ (k)
s|(N ,δ) k∈P1 , k|N
N N/(sk) − n s +O , τ δ log L
n∈A1 (N/(ks),gks ,a−g(ks),δ/s)
where gks (n) = g(nks) − g(ks) is an additive function of n and A1 (N , g , a, δ) = {n : n ∈ A(N , g , a, δ), (n, N ) = 1}. The part of the last sum in which k ≥ v = exp(10 log2 L) is
r1 (δ)
δ≤u
s|δ k|N , k≥v
τ (k)
N L. δk
Let α = log−1 L . Then α τ (k) 1 τ (k) 1 p L ≤ α + 2 1−α exp(−10 log L) exp 2 k v k 1−α p L log L
k≥v , k|N
p≤L
k|N
exp(−10 log L + 2 e log log L + 2 e log−1 L) L−9 . MATHEMATICAL NOTES
Vol. 76
No. 2
2004
252
N. M. TIMOFEEV, M. B. KHRIPUNOVA
Therefore, the estimated part of the sum is O(N L−6 ) . Thus, we have N N δ , , gks + O , r1 (δ) τ (k)X sup S(N ) ≤ 4 ks s log L a δ≤u, δ∈P3
where u = log3 L , function of n , and
(3)
s|(N ,δ) k|N , k∈P1 , k≤v
v = exp(10 log2 L) ,
L = log N ,
N −n . τ δ
X(N , g , δ) := sup a
gks (n) = g(ksn) − g(ks) is an additive
n∈A1 (N ,g ,a,δ)
Let us show that, to prove Theorem 1, it suffices to prove the inequality 2 N 1− , X(N , g , δ) p ϕ(δ) W (N , g)
(4)
p|N , p≡1 (mod 4)
where
1 min(1, (g(p) − λ log p)2 ) . W (N , g) = 4 + min λ2 + λ p p≤N
Since gks (p) = g(p) , for (p, ks) = 1 we have N , gks = W (N , g) + Θ W ks N
uv ≤p≤N
1 1 + , p p p|ks
where |Θ| ≤ 1 . Hence 1
N W ks
1 1+ . − W (N , g) W (N , g) p , gks p|ks 1
1
Therefore, it follows from (4) that N N δ , , gks X δ ks s ksϕ s W (N , g)
p|N , p≡1 (mod 4)
1−
2 p
3 · . 1+ p p|ks
Since sϕ(δ/s) ≥ ϕ(δ) , substituting the last estimate into (3), we obtain 2 r1 (δ) 3 N 1− 1+ sup S(N ) p ϕ(δ) p a W (N , g) δ∈P3 p|N , s|δ p|s p≡1 (mod 4)
τ (k) N N 3 + 1+ . × k p log L W (N , g) k|N , p|k k∈P1
Thus, inequality (4) yields the assertion of Theorem 1. Note that 2 1 (log L)−3/2 , 1− p W (N , g) p|N , p≡1 (mod 4)
MATHEMATICAL NOTES
Vol. 76
No. 2
2004
THE CONCENTRATION FUNCTION OF ADDITIVE FUNCTIONS
253
and δ ≤ log3 L ; therefore, the parts of the sum X(N , g , δ) , which are equal to N N or O , O ϕ(δ) log3/2 L log9/2 L are equal to O(R(N , δ)) , where R(N , δ) =
ϕ(δ) W (N , g)
N
p|N , p≡1 (mod 4)
2 1− p
is the right-hand side of relation (4). Suppose that p(n) and g(n) are the largest and smallest prime divisors of n , respectively. We express n as n = n1 n2 , with p(n1 ) ≤ z3 and g(n2 ) > z3 , where z3 = exp(LΘ ) , 1/2 < Θ < 1 . Let us split X(n, g , δ) into four sums. In the first sum, n1 ≤ z1 = exp(Lσ ),
0 < σ < Θ − 1/2 ;
in the second sum, log z4 = 16LΘ log L ;
n 1 > z4 , in the third sum,
n2 ≤ z2 = N L−10 /(δz4 ) ;
n1 ≤ z4 , and in the fourth sum,
z1 < n1 ≤ z 4 ,
n 2 > z2 .
Let n1 n1 ≡ 1 (mod dδ) . Then, applying Lemma 4, we find that the first sum is √ N N L log z1 1 R(N , δ). n1 dδ log z3 δ log z3 √ n1 n2
n1 ≤z1 d≤N , d∈P1
To estimate the second sum, we first apply Cauchy’s inequality and then Lemma 1. We find that the second sum is 1/2 1/2 1 log z4 2 L2 R(N , δ). 1 τ (m) N exp − ≤ 4 log z 3 N n2
m
2
Similarly, the third sum is found to be ≤
1/2
1
n1
1/2 τ (m) R(N , δ). 2
m
Therefore, we have
X(N , g , δ) ≤ sup a
n∈A2 (N ,g ,a,δ)
N −n τ δ
+ R(N , δ),
where A2 (N , g , a, δ) = {n : n ∈ A1 (N , g , a, δ), n = n1 n2 , z1 < n1 ≤ z4 , n2 > z2 }. MATHEMATICAL NOTES
Vol. 76
No. 2
2004
254
N. M. TIMOFEEV, M. B. KHRIPUNOVA
Let us get rid of the condition g(n) ∈ [a ; a + 1) . To do this, we use the relation
1
−1
sin(u/2) u/2
(1 − |t|) eitu dt =
and the inequalities 4 ≤ π2
sin(u/2) u/2
2
2 ≤ 1,
which hold for |u| ≤ 2 . Moreover, from τ ((N − n)/δ) we again return to r1 ((N − n)/δ) . We obtain π2 X(N , g , δ) ≤ sup 4 a
1
(1 − |t|) e
it(g(n)−a)
n∈A3 (N ,δ)
−1
dt r1
N −n δ
+ O(R(N , δ)),
where A3 (N , δ) = n : n = n1 n2 < N , z1 < n1 ≤ z4 , n2 ≥ z2 , N −n ≡ 1 (mod 4) . (n, N ) = 1, n ≡ N (mod δ), δ Let us split r1 (m) , which is the sum of χ(d) over d | m = (N − n)/δ , into three sums. In the first sum, N 1 d< ; δ ∆ in the second sum,
N 1 ≤d< δ ∆
and in the third sum,
d≥
N ∆; δ
N ∆, δ
where ∆ = L10 . If (N −n)/δ = ds and d ≥ N/δ∆ , then s ≤ N/δ/∆ , and since (N −n)/δ ≡ 1 (mod 4) , it follows that χ(d) = χ(s) . Therefore, we have r1 (m) = 2
1
χ(d) +
2
χ(d) −
3
χ(d) −
4
χ(d),
where the summation in is extended to d | m , d < N/δ/∆ ; in 1 2 , it is extended to d | m ,
, to N/δ/∆ ≤ d < N/δ ∆ ; in 3 d | m, and in
4,
to d | m,
d∈
N 1 ; δ ∆
N δ N ∆ ∩ m∆ ; ∆ ; δ N δ
N 1 δ N 1 ∩ m∆ ; . d ∈ 1; δ ∆ N δ ∆ MATHEMATICAL NOTES
Vol. 76
No. 2
2004
THE CONCENTRATION FUNCTION OF ADDITIVE FUNCTIONS
255
Returning to X(N , g , δ) , we obtain π2 sup 2 a
X(N , g , δ) ≤
1
−1
+O
d<
5
√
χ(d)
eitg(n) dt
n∈A4 (N ,δ ,d)
N/δ/∆
χ(d) + χ(d) + 1 ,
2
n
where the summation in
(1 − |t|) e−ita
5
(5)
4
is extended to
N −n δ N N −n , ≤d< ∆, d| δ δ N δ A4 (N , δ , d) = {n : n ∈ A3 (N , δ), n ≡ N (mod d)}. To estimate the first two sums under the sign of O(. . . ) , we apply Lemma 6, finding that they are
N (log L)5/4 L−β/2 O δ The third sum is
≤
τ (m)
m
R(N , δ).
N · L R(N , δ). δL20
If n ∈ A4 (N , δ , d) , then n ≡ N (mod δd) and n ≡ N − δ (mod 4δ) . Suppose that d = d1 d2 , with p(d1 ) ≤ z and p(d2 ) > z , where z = L10 . Then these two congruences are equivalent to the congruence n ≡ N − δd1 d2 d1 d2 (mod 4δd1 d2 ) , where d1 d1 ≡ 1 (mod 4) and d2 d2 ≡ 1 (mod 4) . Note that (d, 2) = 1 . By choosing d1 and d2 in this way, we have N − δd1 d2 d1 d2 ≡ N − δd1 d1 (mod 4δd1 ) . Since (n, N ) = 1 , it follows that (δd, N ) = (δd, N − δd1 d2 d1 d2 ) = 1 . The following cases are possible: (1) N − δd1 d2 d1 d2 = M is an odd number; (2) 2 | M , but 4 M ; (3) 4 | M . In each of these cases, by dividing both sides of the congruence by the corresponding power of 2, we can make the modulus and the remainder coprime. Consider the case in which 2 M . Recall that δ ≤ log3 L and z = L10 , i.e., δ < z . Let Q = N/δ/∆ . We have
χ(d)
d=d1 d2 ≤Q, (d,N )=1
+
eitg(n) =
1 ϕ(d2 )
χ(d)
d=d1 d2 ≤Q, (d,N )=1
χ(d1 d2 )
d=d1 d2 ≤Q, (d,N )=1
n∈A4 (N ,δ ,d)
eitg(n)
n∈A4 (N ,δ ,d), (n,d2 )=1
eitg(n1 n2 )
z1
1 − ϕ(d2 )
MATHEMATICAL NOTES
Vol. 76
No. 2
2004
z1
eitg(n1 n2 ) .
256
N. M. TIMOFEEV, M. B. KHRIPUNOVA
Using Lemma 7 for A = 20 , we find that the second sum on the right-hand side of the last relation is √ √ √ 1 1√ N N N √ 3/2 + log L L2 N δ 10 + N L Nδ NL+ √ + √ 10 L L L z2 z1 N N N L log R(N , δ). + z z1 z2 δL Substituting these estimates into (5), we obtain π2 X(N , g , δ) ≤ sup 2 a
1
−1
d1 ≤
×
(1 − |t|) e−ita
χ(d1 )
N/δ/∆
eitg(n)
n∈A4 (N ,δ ,d1 )
√
√
d2 ≤ N/δ/(∆d1 ), (d2 ,N n)=1
χ(d2 ) dt + O(R(N , δ)). ϕ(d2 )
(6)
If q(m) > z , log m = O(z) , then 1 m log m = 1 + O exp −1 =1+O . ϕ(m) p z p|m, p>z
We can assume that, on the right-hand side of (6), d1 ≤ z5 = exp 50 log2 L . Indeed, by Lemma 2, the part of the sum over d1 > z5 is 1 log z5 N 1 N R(N , δ). (7) L log L exp − L δ d1 δ 2 log z z5
Therefore, using Lemma 3, we have √
d2 ≤ N/δ/∆, (d2 ,N n)=1
χ(d2 ) = ϕ(d2 )
√
d2 ≤ N/δ/∆, (d2 ,N n)=1
1 1 χ(d2 ) =1+O +O 8 d2 L δL
and, therefore, π2 X(N , g , δ) ≤ sup 2 a
1 −1
(1 − |t|)e−ita
d≤z5 , p(d)≤z
χ(d)
eitg(n) dt + R(N , δ),
(8)
n∈A5 (N ,δ ,d)
where A5 (N , δd) = {n : n < N , (n, N ) = 1, n ≡ N (mod δd)}. Here we replace the condition n ∈ A4 (N , δ , d) by n ∈ A5 (N , δd) ⊃ A4 (N , δ , d) . This can be done, since 1 χ(d) ≥ 0 and (1 − |t|)eit(g(n)−a) dt ≥ 0. d|m, p(d)≤z
−1
As we have seen earlier, (see (7)), the condition d ≤ z5 , can be discarded. MATHEMATICAL NOTES
Vol. 76
No. 2
2004
THE CONCENTRATION FUNCTION OF ADDITIVE FUNCTIONS
257
To decrease the interval of variation of d , we again repeat the previous arguments. We express n as n = n1 n2 ,
where
p(n1 ) ≤ z3 = exp(log5 L),
q(n2 ) > z3 .
Suppose that z1 = exp(log2 L) and z4 = exp(log15 L) , and let us split the sum over n into four sums. In the first sum, n1 ≤ z1 ; in the second sum, n1 > z4 ; in the third sum, n1 ≤ z4 , n2 ≤ z2 = N/(δz4 L10 ) ; and in the fourth sum, z1 < n1 ≤ z4 , n2 > z2 . Then the sum under the integral on the right-hand side of (8) will also be split into four sums. Applying Lemma 4, we find that the first sum is
p(d)≤z n1 ≤z1
N N log−2 L R(N , δ). ϕ(δd)n1 log z3 ϕ(δ)
Using Lemma 1, we find that the second and third sums are N 1 log z4 ·L+ · log z5 R(N , δ). z5 N exp − 2 log z3 δL10 Suppose that z = log20 L . We express d as d = d1 d2 , with p(d1 ) ≤ z , p(d2 ) ≤ z . Then the fourth sum can be expressed as
χ(d1 )
d=d1 d2 ≤z5 , (d2 ,N )=1
χ(d2 ) ϕ(d2 )
d=d1 d2 ≤z5 , (d2 ,N )=1
where
eitg(n)
n∈A6 (N ,δd1 ), (n,d2 )=1
+
z < q(d2 ) , and
n∈A6 (N ,δd)
1 eitg(n) − ϕ(d2 )
eitg(n) ,
n∈A6 (N ,δd1 ), (n,d2 )=1
A6 (N , m) = {n : n ∈ A5 (N , m), n = n1 n2 , z1 < n1 ≤ z4 , n2 > z2 }.
Using Lemma 7, with Q = z5 u , A = 20 , z1 = z1 , z2 = z2 , and z = z , we find that the second sum is N N log z5 u log17 L N log R(N , δ). + N L z1 z2 log22 L log22 L In the first sum, we again pass to n ∈ A5 (N , δd1 ) . Moreover, we can assume that d1 ≤ z5 = exp((log log L)3 ) . Indeed, by Lemma 2, the part of the sum over d1 > z5 is
d1 >z5 , p(d1 )≤z
1 log z5 N N log z log z R(N , δ). exp − δd1 log z δ 2 log z
Further, using the second inequality in Lemma 2, we obtain d2 ≤z5 /d1 , (d2 ,N n)=1
χ(d2 ) = ϕ(d2 )
1+ z
χ(p)p (p − 1)(p − χ(p))
×
1+O
1 d2
d2 |n, d2 >z
MATHEMATICAL NOTES
Vol. 76
No. 2
2004
· 1+
p|N
χ(p)p (p − 1)(p − χ(p))
1 log z5 + exp − log2 z . 5 log z
−1
258
N. M. TIMOFEEV, M. B. KHRIPUNOVA
Note that χ(p)p 1, (p − 1)(p − χ(p)) z
p|N , z
p|N , p>z
Moreover, we have
d1 ≤z5 n∈A6 (N ,δd1 )
d2 |n, z
N 1 1 R(N , δ). d2 δd1 d22 d1 ≤z5
d2 >z
Therefore, returning to relation (8), we obtain χ(p) X(N , g , δ) ≤ 1− |X1 (N , g , δ)| + R(N , δ), p
(9)
p|N , p>z
where X1 (N , g , δ) =
1
−1
χ(d)
d≤z5 ,
p(d)≤z
χδd (N )
χδd
1 ϕ(δd)
χδd (n)eitg(n) (1 − |t|)e−ita dt.
(10)
n
Let us recall that z5 = exp (log log L)3 , δ ≤ log3 L, L = log N , p(δd) ≤ log22 L = z . δd ≤ log3 L exp (log log L)3 ,
z = log22 L,
We split [−1 ; 1] into two sets U1 and U2 . For t ∈ U1 , there exists a λ(t) = λ , such that |λ| ≤ T = exp (log log L)4 , and a Dirichlet character χm , m = m(t) ≤ T , p(m) ≤ z , such that 1 (1 − Re χm (p)eitg(p) p−iλ ) (log log L)4 . p
(11)
p
We have the set U2 = [−1 ; 1] \ U1 . Applying Lemma 8, we obtain 1 1 itg(n) 4 χδd (n)e dt N z5 exp − (log log L) R(N , δ). ϕ(δd) χ 2 U2 d≤z5
δd
n
Thus, the problem reduces to estimating the integral over U1 . Denote by l = l(t) the modulus of the primitive character generating the Dirichlet character χm occurring in inequality (11). Obviously, χ∗l satisfies (11) as well. Applying Lemmas 9 and 8, we find that all the characters χδd not generated by χ∗l satisfy the inequality itg(n) χ e N L−1/4 . δd n
MATHEMATICAL NOTES
Vol. 76
No. 2
2004
THE CONCENTRATION FUNCTION OF ADDITIVE FUNCTIONS
259
Therefore, only the characters generated by χ∗l can be retained in the sum over the characters χδd on the right-hand side of (10). Let l = l1 l2 , where δ = l1 δ1 , (δ1 , l2 ) = 1 . In that case, if (n, δd1 ) = 1 , then χδl2 d1 (n) = χδl2 (n) . Thus, we have χ(δl2 d1 ) itg(n) X1 (N , g , δ) = e χδl2 (N ) χδl2 (n) (1 − |t|)e−ita dt ϕ(δl d ) 2 1 U1 d1 ≤z5 /l2 , p(l2 d1 )
n
+ O(R(N , δ)). For t ∈ U1 such that l2 ≥ log3 L , the modulus of the integrand is
N (log L)−1 (log log L)3 R(N , δ) ; ϕ(δ)
therefore, we can assume that l2 ≤ log3 L . Using Lemma 2 and noting the fact that (n, N ) = 1 and (δl2 , nN ) = 1 , we have 1 χ(p)p χ(d1 ) p(p − 1) = 1+ 2 ϕ(δl2 d1 ) ϕ(δl2 ) (p − 1)(p − χ(p)) p − p + χ(p) p≤z
z
d1 ≤ l 5 , 2
p|δl2
p(d1 )
1− × p|nN , p≤z
χ(p)p p2 − p + χ(p)
1 . +O ϕ(δl2 ) log2 L
Returning to relations (9) and (10), we obtain χ(p) |X2 (N , g , δ)| + R(N , δ), 1− X(N , g , δ) p
(12)
p|N
where X2 (N , g , δ) =
U1
1 p(p − 1) , χδl2 (N ) 2 ϕ(δl2 ) p − p + χ(p) p|δl2
χδl2 (n)eitg(n) F (n)(1 − |t|)e−ita dt, (13)
n
s(p) , 1+ √ F (n) = 3 p p|n, p≤z
We have χδl2 (n)F (n)eitg(n) =
d≤log9 L, p(d)≤z
n
√ p 3 p χ(p) . s(p) = − 2 p − p + χ(p)
s(d) χδl2 (d)eitg(d) √ 3 d
χδl2 (n)eitgd (n) + O(log−2 L),
n
where s(d) = p|d s(p) and gd (n) = g(nd) − g(d) is an additive function of n . It follows from inequality (11) that 1 (1 − Re χδl2 (p)eitgd (p) p−iλ ) ≤ (log log L)4 + O(log log L). p
p
MATHEMATICAL NOTES
Vol. 76
No. 2
2004
(14)
260
N. M. TIMOFEEV, M. B. KHRIPUNOVA
Applying Abel summation, we obtain eitgd (n) χδl2 (n) = n
eitgd (n) χδl2 (n)n−iλ eiλ log N
n
N/d
− iλ 1
eitgd (n) χδl2 (n)n−iλ eiλ log u
n
du . u
Since |λ| ≤ exp (log log L)4 , it follows from (14) that 1 |1 − χδl2 (p)eitgd (p) p−iλ | ≤ 2 log L (log log L)2 . p
p
Combining this with Lemma 10, we obtain ϕ(N ) N eitgd (n) χδl2 (n) − eitgd (n) χδl2 (n) L−1/5 . N d n
n
Therefore, relations (12) and (13) become χ(p) + 1 |X3 (N , g , δ)| + R(N , δ), 1− X(N , g , δ) p
(15)
p|N
where
X3 (N , g , δ) = U1
1 χδl2 (N )Π(δl2 ) χδl2 (n)eitg(n) F (n)(1 − |t|)e−ita dt. ϕ(δl2 )
(16)
n
Here Π(m) =
p|m
p2
p(p − 1) . − p + χ(p)
To prove Theorem 1, it now suffices to show that X3 (N , g , δ)
N . ϕ(δ) log L
Recalling the definition of F (n) , we can write 1 |X3 (N , g , δ)| ϕ(δ) where
N 1 N √ , gd , δ + , X4 3 d ϕ(δ) log L d
d≤log3 L
X4 N , gd , δ ≤ d
itgd (n) e χδl2 (n) dt.
U1 n
The subsequent arguments almost totally repeat the concluding part of the proof of Theorem 1 in [4]. The presence of the sum over d ≤ log3 L involves an additional difficulty. Consider the case d = 1 . Applying Lemma 8, we obtain 1 1 1 N itg(p) −iλ X4 (N , g , δ) N (1 − Re e , exp − min p χδ (p)) dt + χ ,λ 2 ∆ p log L −1 p
MATHEMATICAL NOTES
Vol. 76
No. 2
2004
THE CONCENTRATION FUNCTION OF ADDITIVE FUNCTIONS
261
where the minimum is taken over |λ| ≤ log2 L and χ∆ , ∆ ≤ log6 L . Recall that δ ≤ log3 L and l2 ≤ log3 L . We denote M (t) = min
χ∆ ,λ
1 (1 − Re eitg(p) p−iλ χ∆ (p)), p
p
Ek = {t : t ∈ [−1 ; 1], M (t) ≤ k}, Hence X4 (N , g , δ) N
1≤k≤K
k = 1, 2, . . . ,
K = 4[log log L].
k m(Ek ) + N (log L)−1 . exp − 2
Suppose that for all 1 ≤ k ≤ K the following inequality holds: 200k . m(Ek ) ≤ √ log L Then we obtain X4 (N , g , δ) N
k≥1
k k log−1/2 L N log−1/2 L. exp − 2
The additive functions gd (n) and g(n) differ only by p | d ; therefore, applying Lemma 8, we find in this case that for all d ≤ log3 L the following inequality holds: 1 N N 1 1 N itgd (p) −iλ , gd , δ (1 − Re e exp − min p χ∆ (p)) dt + X4 δ d −1 2 χ∆ ,λ p d log L p
Therefore, X3 (N , g , δ)
1 ϕ(δ)
N N τ (d) . log−1/2 L 2 d ϕ(δ) W (N ) d≤log3 L
Suppose that there exists a k , 1 ≤ k ≤ K , for which 200k . m(Ek ) > √ log L The set Ek is symmetric with respect to zero and contains zero; therefore, (see, for example, Lemma 5.3 [1]) each number t ∈ [−1 ; 1] can be expressed as t1 + · · · + tr , where tj ∈ Ek and r = [12/m(Ek )] . Recall that if tj ∈ Ek , then there exists a λi , |λj | ≤ log2 L , and χ∆j , ∆j ≤ log6 L , such that the following inequality is valid: 1 (1 − Re eitj g(p) χ∆j (p)p−iλj ) ≤ k, p
j = 1, . . . , r.
p
Suppose that zj , j = 1, . . . , r , are complex numbers, with |zj | ≤ 1 . Then (see, for example, [4]) by induction we can prove the following inequality: 1 − Re z1 . . . zr ≤ r
2
r j=1
MATHEMATICAL NOTES
Vol. 76
No. 2
2004
(1 − Re zj ).
(17)
262
N. M. TIMOFEEV, M. B. KHRIPUNOVA
Let t = t1 + · · · + tr , λ = λ1 + · · · + λr , and χ∆ = χd1 . . . χdr . It follows from the previous two inequalities that for any t ∈ [−1 ; 1] there exists a λ = λ(t) and a χ∆ such that 1 log L log L (1 − Re eitg(p) χ∆ (p)p−iλ ) ≤ r2 k ≤ 132 . 2 p 200 k 102
(18)
p
Note that |λ| ≤ r log2 L ≤ log3 L,
∆(t) ≤ log6r L ≤ log6
√
log L
L,
p(∆) ≤ log6 L.
Let us show that χ∆(t) is the principal character. Consider any t1 , t2 ∈ [−1 ; 1] for which we have t1 + t2 ∈ [−1 ; 1] . We prove that the character χm = χ∆(t1 +t2 ) χ∆(t1 ) χ∆(t1 ) is the principal character. Using inequalities (18) and (17), we obtain 1 log L log L (1 − Re χm (p)p−i(λ(t1 +t2 )−λ(t1 )−λ(t2 )) ) ≤ 9 . p 102 10
p
Let σN = 1 + 1/ log N . Then the left-hand side of the inequality is equal to log ζ(σN ) − log |L(σN + i(λ(t1 + t2 ) − λ(t1 ) − λ(t2 )), χm )| + O(1). If χm is not the principal character, then it is equal to (see, for example, [7]) log L + O(1) + O(log |∆|(|λ(t1 + t2 ) − λ(t1 ) − λ(t2 )| + 2)) = log L + O
log L log log L .
Hence we obtain a contradiction. Thus, χd(t1 +t2 ) χd(t1 ) χd(t2 ) is the principal character. Let H=
s p
,
where
s≤
log L .
p≤log6 L
Then the moduli of all the characters discussed above will divide H . By χ ∆ we denote the character modulo H generated by χ∆ . Then, for all t1 , t2 ∈ [−1 ; 1] , where t1 + t2 ∈ [−1 ; 1] , we ∆(t1 ) · χ ∆(t2 ) , and hence χ ∆(t) = ( χ∆(t/h) )h = χ 0 , where h = ϕ(H) . Thus, we have χ ∆(t1 +t2 ) = χ have proved that χ ∆(t) is the principal character. Since ∆(t) | H and 1 p|H
p
≤ 12 log log log L,
using inequality (18), we find that for any t ∈ [−1 ; 1] there exists a λ = λ(t) , |λ| ≤ log3 L , such that 1 log L (1 − Re eitg(p) p−iλ ) ≤ . p 100 p
It follows from Lemma 9 that the primitive character χ∗l(t) generating the characters χδd is the principal one, i.e., l = l1 · l2 = 1 , and relation (15) takes the form X3 (N , g , δ) =
1 χ (N )Π(δ) ϕ(δ) δ
1
−1 n
eitg(n) F (n)(1 − |t|)e−ita dt + O(R(N , δ)).
MATHEMATICAL NOTES
Vol. 76
No. 2
2004
THE CONCENTRATION FUNCTION OF ADDITIVE FUNCTIONS
263
Therefore, we obtain 2 N s(d) sin(gd (n) − a)/2 √ + 3 ϕ(d) log3 L d n
1 X3 (N , g , δ) ϕ(δ)
Noting that gd (p) = g(n) only for p | d and using Lemma 11, we can write X3 (N , g , δ)
1 ϕ(δ)
d≤log9 L
1 s(d) N N √ . · 3 dd W (N ) p|d p ϕ(δ) W (N )
As was noted earlier, this estimate yields the assertion of Theorem 1. ACKNOWLEDGMENTS This research was supported by the Russian Foundation for Basic Research under grant no. 0201-00368. REFERENCES 1. I. Ruzsa, “On the concentration of additive functions,” Acta Math. Acad. Sci. Hungar., 36 (1980), 215–232. 2. P. D. T. A. Elliott, “The concentration function of additive functions on shifted primes,” Acta Math., 173 (1994), 1–35. 3. N. M. Timofeev, “The Erd¨ os–Kubilus conjecture on the distribution of values of of additive functions on sequences of shifted primes,” Acta Arithmetica, 58 (1991), no. 2, 113–131. 4. N. M. Timofeev and M. B. Khripunova, “The concentration function of additive functions with nonmultiplicative weight,” Mat. Zametki [Math. Notes], 75 (2004), no. 6, 877–894. 5. N. M. Timofeev, “The Hardy–Littlewood problem for numbers with given number of simple divisors” Izv. Ross. Akad. Nauk Ser. Mat. [Russian Acad. Sci. Izv. Math.], 59 (1995), no. 6, 181–206. 6. G. Tenenbaum, Introduction a ` la th´eorie analytique et probabiliste des nombres, Institut Elie Cartan, 13. Universit´e de Nancy I, 1990. 7. A. A. Karatsuba, Foundations of the Analytic Theory of Numbers [in Russian], Second edition, Nauka, Moscow, 1983. 8. H. Halberstam and H. E. Richert, Sieve Methods, Academic Press, London–New York, 1974. 9. R. Hall and G. Tenenbaum, 90 Divisors, Cambridge University Press, Cambridge, 1988. 10. C. Hooley, Applications of Sieve Methods to the Theory of Numbers, Cambridge Tracts in Mathematics, no. 70, Cambridge University Press, Cambridge–New York–Melbourne, 1976. Vladimir State Pedagogical University E-mail : hripunova@vgpu.vladimir.ru
MATHEMATICAL NOTES
Vol. 76
No. 2
2004
