ISSN 1064–5624, Doklady Mathematics, 2006, Vol. 74, No. 2, pp. 744–747. © Pleiades Publishing, Inc., 2006. Original Russian Text © N.G. Moshchevitin, 2006, published in Doklady Akademii Nauk, 2006, Vol. 410, No. 6, pp. 730–733.
MATHEMATICS
On Numbers with Missing Digits: Solvability of the Comparison x1x2 ∫ l(modp) N. G. Moshchevitin Presented by Academician V.V. Kozlov March 20, 2006 Received March 30, 2006
DOI: 10.1134/S1064562406050322
was shown in [7] to satisfy the estimate
STATEMENTS OF THE RESULTS Let s and k be positive integers, and let D = {d0, d1, …, dk} ⊂ N0 = N ∪ {0} with 0 = d0 < d1 < … < dk < s, 1 ≤ k ≤ s – 2 be a fixed set of digits in the s-base number system such that (d1, d2, …, dk) = 1. Consider sets of the form ⎧ D K s ( N ) = ⎨ x ∈ N 0 : x < N, x = ⎩
h
∑δ s , δ j
j
j=0
j
⎫ ∈ D ⎬. ⎭
D
The arithmetic properties of K s (N) have been examined in numerous works (see, e.g., [1–6]). For example, the idea of [1, 2] was developed in [5], where it was proved that, given a prime number p and an arbitrary positive ε such that (p, s) = 1 in the case l ≥ 3, the number Tl(N, p, λ) of solutions to the comparison x 1 x 2 … x l ≡ λ ( mod p ),
x j ∈ K s ( N ), D
where (λ, p) = 1 and N ≥ pσ for sufficiently large σ, satisfies the asymptotic formula l
l
– --- + 1 + lε K s ( N, p ) ⎛ 2 ⎞⎞ , - 1 + O⎛ p T l ( N , p, λ ) = -------------------------⎝ ⎠⎠ p–1 ⎝ p → ∞, D
where | K s (N, p)| is the number of elements in the set D
K s ( N , p ) = { x ∈ K s ( N ): ( x, p ) = 1 }. D
D
ε
B p ( ε = ε ( σ ) → 0, σ → ∞ ). Recently, Moshchevitin and I.D. Shkredov have extended the above results to the case of a composite modulo m (instead of a prime p) and have corrected the inaccuracies in the results announced in [5]. Note that, in [3, 5], the sums of characters modulo p D over the set K s (N) were estimated in the case of a prime p, while Moshchevitin and Shkredov estimated them modulo m, where m is a composite number. In this paper, an asymptotic formula is derived for the number T2(N, p, λ) of solutions to the comparison x 1 x 2 ≡ λ ( mod p ),
λ ≠ x 1 x 2 ( mod p ),
(1)
Theorem 1. Given a fixed positive ε, let M = sa be 1 --- + ε 2
such that | K s (M)| ≥ p and N = sb, where b ≥ σ ln p and σ is sufficiently large. Then, for any λ satisfying (λ, p) = 1, the number T(M, N, p, λ) of solutions to the comparison D
x 1 x 2 ≡ λ ( mod p ),
x 1 ∈ K s ( M ), D
x2 ∈ K s ( N ) D
is given by the asymptotic formula
x 1, x 2 ∈ K s ( N , p ) } D
Faculty of Mechanics and Mathematics, Moscow State University, Leninskie gory, Moscow, 119899 Russia e-mail:
[email protected]
D
modulo prime p for N ≥ pσ, and the solvability of comparison (1) is proved for N = p and a sufficiently “large” set D. The case of composite modulo is not considered. In what follows, we mean that p → ∞ in all the asymptotic formulas.
In the case l = 2, the cardinality of the exceptional set B = { λ ( mod p ): ( λ, p ) = 1,
x j ∈ Ks ( N )
Ks (M) Ks ( N ) –δ ( 1 + O ( p ) ), T ( M, N , p, λ ) = ---------------------------------------p δ = δ ( ε, σ ) > 0. D
D
Corollary. Given a sufficiently large σ and an arbitrary positive integer N ≥ pσ, for any λ satisfying 744
ON NUMBERS WITH MISSING DIGITS
(λ, p) = 1, the number T2(N, p, λ) of solutions to comparison (1) is given by the asymptotic formula
x 1 x 2 ≡ λ ( mod p ),
ν
(2)
ln p ν = --------- . ln s
Theorem 2. Given ε > 0, there exists a sufficiently 1 small positive η = η(ε) ∈ ⎛ -0, --- ⎞ with the following ⎝ 2⎠ properties. If (i) the positive integer M and the set D of digits (containing more than one element) are such that 1 --- + ε 2
| K s (M)| ≥ p and (ii) for some positive integers s, r, and h, it is true that D
( 8s
1 1 + --r 1–η
)
⎛ s ≤ h ≤ min ⎜ s – 1, ⎛ ---⎞ ⎝ ⎠ 4 ⎝
1 1 + --r⎞
⎟, ⎠
(3)
then, for every λ that is not divided by p, the number W(λ) of solutions to the comparison x0 ∈
1 – 2ε 0 – ε 1 K (H) *1 + ε - ≥ p W 2 ( λ ) ≥ --------------------; 1 p
moreover, the right-hand side of (6) tends to infinity as p → ∞. Once again, we note that all the elements of the set K∗(H) involved in the corollary lie in the interval from 0 to p – 1. To deduce this corollary from Theorem 2, we need to choose parameters r and h satisfying (5). Since ε0 is small, they satisfy the inequality rh ≤ H. This implies the relations rD∗(h) ⊆ D∗(H) and rK∗(h) ⊆ K∗(H), in which case the solutions to comparison (4) generate the solutions to comparison (6). ESTIMATES OF KLOOSTERMAN’S SUMS In what follows, A ⊂ Zp plays the role of a “large” set (|A| > p
1 --- + ε 1 2
, where ε1 > 0) and B ⊂ Zp is a “small” set
ε2
(|B| > p , where ε2 > 0). Consider the trigonometric sum
a ∈ A, b ∈ B a + b 0 ( mod p )
S m ( A, B ) ≤ A B ∆,
x 1, x 2, …, x r ∈ K * ( h )
1 -----
(4)
Ks ( M) K (h) –δ * - ( 1 + O ( p ) ), W ( λ ) = ---------------------------------------p δ = δ ( ε, η ) > 0.
p p 2l ∆ l ⎛ ---------------l + -------⎞ . ⎝A B A⎠
r
D
Corollary. If M =
For example, conditions (3) are satisfied if s≥2 ,
r =
m ( a + b )* exp ⎛ 2πi -------------------------⎞ . ⎝ ⎠ p
Here and below, x* denotes the inverse of x modulo p. Lemma 1. Given an arbitrary positive integer l < p and arbitrary sets A, B ⊂ Zp, for m 0 (modp), the trigonometric sum satisfies the estimate
is given by the asymptotic formula
14 -----η
∑
S ( A, B ) =
where
x 0 ( x 1 + x 2 + … + x r ) ≡ λ ( mod p ), D K s ( M ),
2 --- , η
h =
64s
η 1 – --2
.
(5)
Corollary. There exists a sufficiently large positive integer s0 and sufficiently small positive ε0 and ε1 (such that 2ε0 + ε1 < 1) that have the following property. If s ≥ s0 and H is a positive integer in the interval s DOKLADY MATHEMATICS
Vol. 74
(6)
2
D * ( h ) = { 0, 1, …, h – 1 }, D*
x 1, x 2 ∈ K * ( H )
satisfies the estimate
Theorem 1 and its corollary hold for an arbitrary set D, but one of the numbers M and N (or both) must be greater than p. A solvability result for the comparison can also be derived for small values of M and N but under additional constraints imposed on D. We do not state and prove the corresponding result in the general case. Consider a typical situation. Let
K * ( h ) = K s ( s ),
H ≤ s – 2, then, for every λ that is not divided by p, the number W2(λ) of solutions to the comparison
2
Ks ( N ) –δ ( 1 + O ( p ) ), T 2 ( N , p, λ ) = --------------------p δ = δ ( σ ) > 0. D
745
No. 2
1 – ε0
2006
≤
sa
is such that
D | K s (M)|
≥ p
1 --- + ε 2
,
D D then the set K s (M) can be represented as K s (M) = D D K s (M') + sa' K s (M''), where M' = sa' and M'' = sa''. More1 --- + ε' D D 2 over, | K s (M')| ≥ p , | K s (M'')| ≥ pε'', and the appli-
cation of Lemma 1 gives the estimate
∑ D
x ∈ K s ( M ), x 0 ( mod p )
mx* D –δ exp ⎛ 2πi ----------⎞ K s ( M ) p , ⎝ p ⎠ δ > 0.
746
MOSHCHEVITIN
The proof of Lemma 1 can be commented on as follows. Recall Weyl’s celebrated estimate for a rational trigonometric sum. Let P(x) and Q(x) be polynomials over the ring Zp[x] that are relatively prime modulo p and have different degrees. The Weyl estimate is given by
∑
1≤x≤ p Q ( x ) 0 ( mod p )
P ( x ) ( Q ( x ) )* exp ⎛ 2πi --------------------------------⎞ ⎝ ⎠ p
⎛ ≤ ⎜r – 2 + ⎝
Lemma 3. Suppose that η > 0; p is a prime number; s, h, and r are positive integers satisfying condition (3); and K∗(h) is defined in (2). Then p–1
m = 0 x ∈ K*(h)
p–1 ν–1
σ = ⎞
r
∑ d ⎟⎠ j
p,
m 0 ( mod p ). TRIGONOMETRIC SUMS OVER THE SET
D K s (N)
∑∑
m If we consider the s-ary decomposition ---- = p 0.µ1µ2…µν…, it is easy to see that, for any set µ1µ2…µν of s-ary digits, there is at least one and at most s fracm tions ---- whose s-ary decomposition begins with the set p µ1µ2…µν.
g ≤ 2s h
r – ----------r+1
D
The trigonometric sums over the set K s (N) can be estimated using the approach of [8] or Konyagin’s results. To prove Theorem 1, it is more convenient to use Konyagin’s lemma from [2], more exactly, its consequence. The following result is implied by Lemma 1 from [2]. Lemma 2. Let p ≥ s. For w ≥ 2r, it is true that
≤
D b Ks (s )
xm exp ⎛ 2πi -------⎞ ⎝ p⎠
⎛ ⎞ ⎛ ⎞ ⎜ ⎟ ⎜ ln p ⎟ ⎜ exp ⎜ γ 1 ⋅ ------------------------⎟ – 1⎟ . γ 2b⎞ ⎟ ⎜ ⎟ ⎜ exp ⎛ -------⎝ ⎠ ⎝ ⎝ ln p⎠ ⎠
where γν = γν(s) (ν = 1, 2) are positive constants. Corollary. Given any positive η, for sufficiently large positive σ and for N ≥ pσ, we have η
S p, w K s ( N ) p . D
r
r ⎧ ⎫⎞ ⎜ ⎪ 1 ⎪⎟ ≤ . ⎜ min ⎨ h, ---------------j ⎬⎟ ⎜ ⎟ ⎪ 2 ms ⎪ m=0j=0 -------- ⎭⎠ ⎝ ⎩ p
Let g = 2
∑
j
ms d exp ⎛ 2πi -------------j⎞ ⎝ p ⎠
p–1 ν–1⎛
j=1
1 ≤ m ≤ p – 1 x ∈ K D ( sb ) s
∑∏ ∑
m = 0 j = 0 d j ∈ D*
P( x) 1 1 1 1 ----------- = m ⎛ -------------- + … + -------------- – -------------- – … – --------------⎞ , ⎝ Q( x ) x + b1 x + bν x + b '1 1 + b 'ν⎠
∑
mx r η exp ⎛ 2πi -------⎞ ≤ s K ( h ) p . ⎝ * p⎠
Proof sketch of Lemma 3. Obviously,
P( x ) where r is the number of different poles of ------------ and dj Q( x ) is the multiplicity of the jth pole (it is assumed that f (x) is reduced modulo p; the pole at infinity is also taken into account). Lemma 1 is deduced by standard reasoning from the Weyl estimate as applied to the function
S p, w =
r
∑ ∑
σ =
The following result refines the lemmas from [9].
1 r – ----------- – ----------r+1 r+1
h
s . In view of (3), we have 2 ≤
s ≤ sη < --- . 2
Given a real number ξ, if its first digit ξ1 following the point in the s-ary decomposition lies in the range g g–1 – 1 ≤ ξ1 ≤ s – g, then ||ξ|| ≥ ----------- . Thus, if µj belongs to s j –1 ms ≥ g----------the interval [g – 1, s – g], then ------. Note that s p there are exactly C ν (s – 2g)t(2g)ν – t sets µ1µ2…µν in which exactly t digits µj belong to the interval (g – 1, s – g). Consequently, the estimate of the sum in question can be extended as t
ν
σ≤s
∑
C ν ( s – 2g ) ( 2g ) t
t
rt s r(ν – t) --------------------⎞ h ⎝ 2 ( g – 1 )⎠
ν – t⎛
t=0
⎛ ⎞ν r ν 8s ( s – 2g )s r ⎟ - + 2g⎞ ≤ s K ( h ) ⎜ ---------≤ sh --------------------------r ⎟ ⎜ ---------⎝ 2r ( g – 1 )r hr ⎠ * ⎝ h r + 1⎠ νr ⎛
≤ s K (h) p * r
η
(where we used (3)). The lemma is proved. DOKLADY MATHEMATICS
Vol. 74
No. 2
2006
ON NUMBERS WITH MISSING DIGITS
PROOF SKETCHES OF THEOREMS 1 AND 2 Theorem 1 is proved by expanding the characteristic function of divisibility δp(·) in a finite Fourier series and using estimates (7) and (8): D
∑
= D
D
K s (M, p) K s ( N ) 1 - ≤ --– -----------------------------------------p p D
p–1
∑ D
x 2 ∈ K s ( M, p )
REFERENCES
⎛
∑ ⎜⎝ ∑
m=1
×
The author is grateful to I.D. Shkredov, who read the manuscript and made several helpful remarks.
δ p ( x 1 – λx *2 )
x 1 ∈ K s ( N ), x 2 ∈ K s ( M, p ) D
ACKNOWLEDGMENTS
This work was supported by a grant from the President of the Russian Federation (MD-3003.2006.1), by the Russian Foundation for Basic Research (project no. 06-01-00518), and by INTAS (project no. 03-51-5070).
K s ( M, p ) K s ( N ) T ( M, N , p, λ ) – ---------------------------------------------p D
747
D
b
x 1 ∈ K s (s )
x 1 m⎞ exp ⎛2πi -------⎝ p ⎠
2. S. Konyagin, Period. Math. Hung. 42 (1/2), 145–162 (2001).
mλx * ⎞ exp ⎛ 2πi -------------2-⎞ ⎟ ⎝ p ⎠⎠
3. W. D. Banks, A. Conflitti, and I. E. Shparlinski, Illinois J. Math. 46, 819–836 (2002).
Ks (M) Ks (M) Ks ( N ) - --------------------------------------- S p, w × ------------------ 1+δ 1+δ–η p p D
D
D
4. W. D. Banks and I. E. Shparlinski, Acta Arith. 112, 313– 332 (2004). 5. N. G. Moshchevitin, Dokl. Math. 65, 350–352 (2002) [Dokl. Akad. Nauk 384, 167–170 (2002)].
Ks (M) Ks ( N ) ---------------------------------------1 + δ/2 p D
D
6. N. G. Moshchevitin, Chebyshev. Sb. 3 (3), 93–99 (2002).
δ if η ≤ --- . Theorem 2 is proved in a similar manner by 2 using inequality (7) and the estimate from Lemma 3.
DOKLADY MATHEMATICS
Vol. 74
1. P. Erdös, C. Mauduit, and A. Sarközy, J. Number Theory 70, 99–120 (1998).
No. 2
2006
7. I. D. Shkredov, Candidate’s Dissertation in Mathematics and Physics (Moscow, 2005). 8. W. Schmidt, Pacific J. Math. 10, 661–672 (1960).
