The Multiplication table for Smooth integers
Marzieh Mehdizadeh
math.NT 11N25


All-electric single electron spin initialization
    G. Skowron
    December 30, 2023
================================================





The Erdős multiplication table problem asks what is the number of distinct integers appearing in the N× N multiplication table. The order of magnitude of this quantity was determined by Ford  <cit.>. In this paper we study the number of y-smooth entries of the N× N multiplication table that is to say entries with no prime factors greater than y.




§ INTRODUCTION

The multiplication table problem involves estimating 

    A(x):=#{ab: a,b≤√(x),   and   a,b ∈ℕ}.
  
This interesting question, posed by Erdős, has been studied by many authors. Erdős in   <cit.>, showed that for all ε>0, we have

    x/(log x)^δ+ϵ≤ A(x)≤x/(log x)^δ-ε   (x→∞),

where

    δ=1-1+loglog 2/log 2= 0.0860… .

 In <cit.>, Hall and Tenenbaum improved the upper bound  (<ref>) as follows

    A(x)≤c_1 x/(log x)^δ√(loglog x),

for some absolute constant c_1>0, where  δ is defined in (<ref>).

A key step in determining the order of magnitude of A(x) is to estimate the number of representations of integers as products of ab with a,b≤√(x). 

The best estimate of A(x) is a result due to Kevin Ford  <cit.>. He proved the following estimate, that significantly improved the order of magnitude of A(x) as follows

    A(x)≍x/(log x)^δ(loglog x)^3/2.



Notation: In this paper, we use the notation  f(x) ≍ g(x) if both f(x)≪ g(x) and g(x)≪ f(x) hold, where f(x)≪ g(x) or f(x)=O(g(x)) interchangeably to mean that |f(x)| ≤ cg(x) holds with some constant c for all x in a range which will normally be clear from the context. Also, the notation f(x)∼ g(x) means that f(x)/g(x)→ 1 as x→∞, and f(x)=o(g(x)) means that f(x)/g(x)→ 0 as x→∞.

Also, u is defined as

    u:=log x/log y     x≥ y≥ 2,

and we let log_k x denote the k-fold iterated logarithm, defined by log_1x:= log x and log_k x= loglog_k-1x, for k>1.



The bounds for A(x) are intimately connected with bounds for the function H(x,y,2y), which is the number of integers n≤ x having have a divisor in the interval (y, 2y]. More formally 

    H(x,y,2y):= #{n≤ x : ∃  d|n ,   y<d ≤ 2y}.

This function, which its study was initiated by Besicovitch, has an intimate connection to the multiplication table problem via this inequality:

    H(x/2,√(x)/4,√(x)/2)≤ A(x)≤∑_k≥ 0 H(x/2^k,√(x)/2^k+1,√(x)/2^k).

Hence, studying  A(x) boils down to understanding H(x, y, 2y), which is slightly easier to study. Ford <cit.> proved 

    H(x,y,2y)≍x/(log x)^δ(loglog x)^3/2,

and he subsequently deduced (<ref>) from (<ref>). 

It is worth mentioning that Koukoulopoulos in his Ph.D thesis  <cit.> extended the multiplication table problem to higher dimensional table. 

Motivated by this background, in this paper we investigate the multiplication table problem for smooth integers. The set of y-smooth numbers, is defined by

    S(x,y):= {n≤ x : P(n)≤ y},

where P(n) denotes the largest prime factor of an integer n ≥ 2, with the convention P(1)=1. Set

    Ψ(x,y):= |S(x,y) |.

Our main aim in this work is to study

    A(x,y):= #{ab: a,b∈ S(√(x),y) }.

Hence computing A(x,y) is equivalent to estimating the size of  S(√(x),y)· S(√(x),y).

If we define H(x,y;z,2z) as the number of all y-smooth integers having at least one divisor in the given interval (z,2z], then by a simple argument one can arrive at the following inequalities for y-smooth integers,

    H(x/2,y;√(x)/4,√(x)/2)≤ A(x,y)≤∑_k≥ 0 H(x/2^k,y; √(x)/2^k+1,√(x)/2^k),

where x≥ y >2. Thus one would be tempted to estimate A(x,y) by achieving upper and lower bounds for H(x,y;z,2z), The motivation of this paper is to understand the behaviour of the function A(x,y) directly instead of considering H(x,y;z,2z).


This is a good moment to digress slightly to explain a connection between estimating A(x,y) and sum-product problem in additive combinatorics. For any non-empty subset A of integers, the sumset and productset of A are defined as

    A· A={a_1a_2: a_i∈ A},     A+A={a_1+a_2: a_i∈ A}.

  A famous conjecture of Erdős and Szemerédi states that the sumset and productset of a finite set of integers cannot both be small, more formally 

    max{|A· A|, |A+A|}≫_ε |A|^2-ε.


A simple approximation of Ψ(x,y) proved by Canfield, Erdős and Pomerance  <cit.> states that for a fixed ϵ>0, we have

    Ψ(x,y)= x u^-u(1+o(1))  as    u→∞,

for u≤ y^1-ϵ, that is y≥ (log x)^1+ϵ.

By estimate (<ref>), one can see that for u large (or y small), the value of Ψ(x,y) is small. It counts the integers having large number of prime factors. Since in this case every n has a lot of small prime factors, we can find a and b such that n=ab and a,b≤√(x).


If u is small (which means that y is large), then by (<ref>), one can deduce that the value of Ψ(x,y) is large compared to x. In this case, S(x,y) contains integers with large prime factors and we expect the size of S(√(x),y)· S(√(x),y) to be small.


It is good to mention that by a connection to sum-product problem, Banks and Covert  <cit.> by invoking combinatorial tools,  have considered the behaviour of A(x^2,y)= |S(x,y)· S(x,y)| in different ranges of y, particularly for the cases when y is relatively small or large. 

 By using combinatorial techniques, they could show that 

    |S(x,y)· S(x,y)|= Ψ(x,y)^1+o(1)  as   x→∞,

when y=o(log x), and


    |S(x,y)· S(x,y)|= Ψ(x,y)^2+o(1)  as   x→∞.

when y/(log x) →∞.


By  <cit.> they could prove that 

    Ψ(x^2/y,y) ≤ |S(x,y)· S(x,y)| ≤Ψ(x^2,y),
also they could show that 
    Ψ(x^2,y)= Ψ(x,y)^1+o(1)  as   x→∞,
  
when y≥ 2 and y=o(log x). Therefore


    |S(x,y) · S(x,y)| = Ψ(x,y)^1+o(1),

If we replace x by √(x) in (<ref>), we get

    Ψ(x/y,y)≤ A(x,y)≤Ψ(x,y).

Here we first present a simple argument to prove that the y-smooth integers up to x/y can be represented as a product of two y-smooth integers less than √(x), and by a lemma we will show that

    Ψ(x/y,y) ∼Ψ(x,y)    (x→∞),

when y=o(log x). Combining these up, gives the following theorem

Here we present a simple idea to prove that A(x,y) has a same size as Ψ(x,y) when y is small compared to log x. Let  n≤x/y be a y-smooth number. If n ≤√(x) then trivially we have n∈ A(x,y). Thus, we assume that √(x)≤ n.  Let p_1≤ p_2≤⋯≤ p_k be prime factors of n. Consider the following sequence obtained by prime factors of n:  

    n_0=1,     n_j= ∏ _i=1^j p_i,      1≤ j ≤ k.

 Since n≥√(x) then there exists a unique integer s, with 0≤ s <k such that n_s< √(x)≤ n_s+1. Each prime factor of n is less than y, therefore
 
    n_s ≤√(x)≤ n_s+1≤ n_s y.

 Set  d=n_s, then
 
    √(x)/y≤ d≤√(x).

 Since n≤ x/y, then we easily conclude that 
 
    n/d≤√(x).

 Therefore,
 
    Ψ(x/y,y) ≤ A(x,y) ≤Ψ(x,y),

and by a simple argument one can deduce that as x,y →∞ then Ψ(x/y,y) ∼Ψ(x,y) when y=o(log x), (see Lemma <ref>).
This argument leads us to state the following theorem.

 
 If y=o(log x) then we have
 
    A(x,y) ∼Ψ(x,y)   as   x,y→∞.

 
 The problem gets harder, and hence, more interesting when y takes larger values compared to log x. We shall prove the following theorem for small values of y compared to x.
  We have

    A(x,y)∼Ψ(x,y)   as   x,y→∞,

when u and y satisfy the range

    ulog u/(log y log_2 y log_3 y)^2→∞ ,  which implies,    y≤exp{(log x)^1/3/(log_2 x)^1/3 +ϵ},

for ϵ>0 arbitrarily small.

 Theorem <ref> is proved in Section 3. The proof relies on some probabilistic arguments and recent estimates for Ψ(x/p,y) where p is a prime factor of n.



If y takes values very close to x, which implies u is small compared to loglog y, then we will show the following theorem.
 
Let ϵ>0 is arbitrarily small, then we have

    A(x,y)= o(Ψ(x,y))   as   x,y→∞,

where u and y satisfying the range

    u < (L-ϵ)log_2 y,   which implies,    y ≥exp{log x/(L-ϵ)log_2 x},

where L:= 1-log 2/log 2.
  
Theorem <ref> is proved in Section 4, by applying an Erdős' idea <cit.>, suitably modified for y-smooth integers.
 

In what follows, we will give a heuristic argument that predicts the behaviour of A(x,y) in ranges (<ref>) and (<ref>).

We define the function τ(n; A,B) to be the number of all divisors of n in the interval (A,B]. In other words.

    τ(n; A,B) :=#{d: d|n ⇒ A< d ≤ B}.

Let n∈ S((1-η)x,y) be a square-free number with k prime factors, where η→ 0 as x→∞. Assume that the set 

    D(n):={log d: d|n}
 
is uniformly distributed in the interval [0, log n]. So 

    P(d∈ (A,B)):=τ(n)  log B- log A/log n,

where the sample space is defined by

    S:= { n≤ x: ω(n)= k },

and n being chosen uniformly at random. By this assumption, the expected value of the function τ(n,(1-η)√(x),√(x)) is as follows

    𝔼[τ(n,(1-η)√(x),√(x))]=
    2^k log (1/(1-η))/log√(x)≍2^k/ulog y.

 Alladi and Hildebrand in  <cit.> and  <cit.> showed that the normal number of prime factors of y-smooth integers is very close to its expected value u+log_2 y in different ranges of y. Hence, from (<ref>), we deduce that
 
    𝔼[τ(n,(1-η)√(x),√(x))] ≍2^u+log_2 y/log y.

If 2^u+log_2 y/log y→∞, then we expect that n will have a divisor d in the interval ((1-η)√(x),√(x)].
 We know n≤ (1-η) x. Thus, n/d ≤√(x), and we can deduce that n∈ A(x,y), this means that 

    Ψ((1-η)x,y) ≤ A(x,y).

Trivially A(x,y)≤Ψ(x,y). So by  this argument, we obtain 

    A(x,y)∼Ψ(x,y),

when η→ 0 as x→∞. 


On the other hand, if  2^u+log_2 y/log y → 0, then we expect that none of integers in  S((1-η)x,y) have a divisor in ((1-η)√(x), √(x)] (except a set with density 0), this means that 

    A(x,y)=o(Ψ(x,y))   as   x,y→∞.

This heuristic gives an evidence for the following conjecture: 

 If L:= 1-log 2/log 2, then we have the following dichotomy


  * : If u-Llog_2 y→+∞, which implies 

    y≤exp{log x/Llog_2 x},
 
 Then, we have

    A(x,y)∼Ψ(x,y)   as   x,y→∞.


  * : If u- Llog_2 y →-∞, which implies that for small ϵ>0
 
    y≥exp{log x/(L-ϵ)log_2 x},
 
Then, we have 

    A(x,y)=o(Ψ(x,y))   as   x,y→∞ .

  

Theorem <ref> and Theorem <ref> are in the direction of the first case and the second case of Conjecture (<ref>) respectively, but the claimed ranges in the conjecture are stronger than the claimed ranges in Theorem <ref> and Theorem <ref>, and the reason stems from uniformity assumption about D(n).


Acknowledgement 


I would like to thank Andrew Granville and Dimitris Koukoulopoulos for all their advice and encouragement as well as their valuable comments on the earlier version of the present paper. I am also grateful to Sary Drappeau, Farzad Aryan and Oleksiy Klurman for helpful conversations.  



§ PRELIMINARIES
 
In this section, we review some results used in the proof of our main theorems. We first fix some notation.
In this chapter ρ(u) is the Dickman-de Bruijn function, as we defined in the introduction. By  <cit.> we have the following estimate for ρ(u)
 
    ρ(u) = (e+o(1)/ulog u)^u   as   u→∞.

  The estimate 

    Ψ(x,y)=xρ(u)(1+O_ϵ(log (u+1)/log y))

holds uniformly in the range

    x≥ 3,     1≤ u ≤log x/(log_2 x)^5/3+ϵ,   that is,   y≥exp((log_2 x)^5/3+ϵ),

where ϵ is any fixed positive number.

Combining (<ref>) with the asymptotic formula (<ref>), one can arrive at the following simple corollary

We have

    Ψ(x,y) = xu^-(u+o(u)),

as y and u tend to infinity, uniformly in the range (<ref>), for any fixed ϵ>0.



We will apply this estimate in the proof of Theorem <ref>. However this estimate of Ψ(x,y) is not very sharp for large values of u, for which the saddle point method is more effective.

Let α:=α(x,y) be a real number satisfying

    ∑_p≤ ylog p/p^α-1=log x.
 
One can show that α is unique. This function will play an essential role in this work, so we briefly recall some fundamental facts of this function that are used frequently. By <cit.> we have the following estimates for α.


    α(x,y)= log(1+y/log x)/log y{1+O(log_2 y/log y)}     x≥ y≥ 2.

For any ϵ>0, we have the particular cases

    α(x,y)= 1-ξ(u)/log y +O(1/L_ϵ (y)+ 1/u(log y)^2)     if    y≥ (log x)^1+ϵ,

where 

    L_ϵ(y)=exp{(log y)^3/5-ϵ},

and ξ(t) is the unique real non-zero root of the equation

    e^ξ(t)= 1+tξ(t).

Also for small values of y, we have

    α(x,y)= log (1+y/log x)/log y{1+O(1/log y)}   if    2≤ y≤ (log x)^2.









We now turn to another ingredient related to the behaviour of Ψ(x,y). The following estimate is a special case of a general result of
de La Breteche and Tenenbaum <cit.>. 


There exist constants b_1 and b_2 and a function b=b(x,y,d) satisfying b_1≤ b≤ b_2 such that the following equation holds uniformly for all 2≤ y ≤ x: 

    Ψ(x/d,y)= {1+O(1/u_y+t/u)}(1-t^2/u^2+u̅^2)^bu̅Ψ(x,y)/d^α.



If d≤ y, then uniformly for x≥ y ≥ 2 we have

    Ψ(x/d,y) ={1+ O(1/u+log y/y)}Ψ(x,y)/d^α.






 
 






 
 We can deduce the following lemma by Theorem <ref> which completes the proof of Theorem <ref> 

If y≥ 2 and y=o(log x), then we have

    Ψ(x/y, y)∼Ψ(x,y)   as   x→∞.




(i): Let y≥ (log_2 x)^2 and y=o(log x). By applying (<ref>), if d=y, we obtain

    Ψ(x/y,y)=Ψ(x,y)/ y^α{ 1+O(log y/y)}.

 By combination of the above estimate along with  (<ref>), we get

    Ψ(x/y,y) = Ψ(x,y)/(1+y/log x)^1+O(1/log y){1+O( log y/y)}.

We remark again that y=o(log x), so we obtain 

    1/(1+y/log x)^1+O(1/log y)→ 1    when     x →∞.

Also, we have

    log y/y→ 0   when   x→∞,

since y≥ (log_2 x)^2. Thus, by (<ref>), we conclude 

    Ψ(x/y,y)/Ψ(x,y)→ 1   when   x→∞.

(ii): Let 2≤  y ≤ (log_2x)^2, then by recalling Ennola's theorem <ref>, we get

    Ψ(x/y,y)   = 1/π(y)!∏_p≤ ylog x/y/log p{ 1+O(y^2/log x log y) }
        =1/π(y)!∏_p≤ ylog x/log p∏_p≤ y (1-log y/log x){ 1+O(y^2/log x log y) }
        =Ψ(x,y) (1+ O(π(y) log y/log x))
       = Ψ(x,y)( 1+O(y/log x)),

which gives that

    Ψ(x/y,y) ∼Ψ(x,y)   as   x→∞,

and this completes the proof.



Finally, we define

    θ (x,y,z) := #{ n≤ x : p|n ⇒ z≤ p≤ y } .

This function has been studied extensively in the literature. Namely   Friedlander <cit.> and Saias <cit.> gave several estimates for θ(x,y,z) in different ranges. The following theorem is due to Saias <cit.> which is used in Section 4.
 
There exists a constant c>0 such that for x≥ y≥ z≥ 2 we have


    θ(x,y,z) ≤ cΨ(x,y)/log z.



 



§ PROOF OF THEOREM <REF>
 We begin this section by setting some notation. Let η be defined by

    η := 1/log_3 y,

and set

    N:=⌊log_2 y -logη/log 2+2⌋,

which play an essential role in process of the proof.

The idea of the proof of Theorem <ref> is a combination of some probabilistic and combinatorial techniques. Before going through the details, we give a sketch of proof here.

The first step of proving Theorem <ref> is to study the number of all prime factors of n in the narrow intervals 

    J_i:=[(1-κ)y^1-1/2^i,y^1-1/2^i],      1≤ i≤ N,

of multiplicative length (1-κ)^-1, where κ is defined as

    κ := η/2N.

Also, we define the tail interval 

    J_∞:= [(1-κ)y,y].

Let ω_i(n) be the number of prime factors of n in J_i for each i∈{1,2,…,N,∞}, more formally

    ω_i(n):= #{ p|n : p∈ J_i}.



We define μ_i(x,y) to be the expectation of ω_i(n), defined by

    μ_i(x,y):=1/Ψ(x,y)∑_n∈ S(x,y)ω_i(n),
 
 In Proposition <ref>, we will prove that for almost all y-smooth integers the value of ω_i(n) exceeds μ_i(x,y)/2. We establish this by applying the Chebyshev's inequality

    #{n∈ S(x,y): ω_i(n)≤μ_i(x,y)/2}/Ψ(x,y)≤4σ_i^2(x,y)/μ_i^2(x,y),

where 

    σ_i^2(x,y):=1/Ψ(x,y)∑_n∈ S(x,y)(ω_i(n)-μ_i(x,y))^2,

is the variance of ω_i(n) and i∈{1,2,…,N,∞}. We will conclude that there is at least one prime factor p_i in each J_i for 1≤ i≤ N and N prime factors q_1,…, q_N in J_∞. Then by using the product of these prime factors in Corollary <ref>, we will find a divisor D_j of n such that 

    (1-κ)^N y^N-j/2^N≤ D_j ≤ y^N-j/2^N,
 
for an integer j in {0,1,… 2^N-1 }.

Then, we fix an integer n in S((1-η)x,y), and by defining m:= n/∏_i=1^Np_i q_i, we will easily show that there is a divisor d_j of n, such that

    √(n)/y^Ny^ j/2^N <d_j< √(n)/y^N y^(j+1)/2^N.

Multiplying D_j and d_j and using the definitions of η, κ and N, gives a new divisor d of n that helps us to write n as the product of two divisors less than √(x).



Before stating technical lemmas we get an estimate for the expected value of ω_i(n) for all 1≤ i≤ N and i=∞. By changing the order of summation in (<ref>), we can easily see that 

    μ_i(x,y)=∑_p∈ J_iΨ(x/p,y)/Ψ(x,y).

By (<ref>), we have the following estimate 


    μ_i(x,y)   =∑_p∈  J_i1/p^α(1+O(1/u+ log y/y)),

 for all 1≤ i ≤ N and x≥ y≥ 2.
 Also, we obtain the following estimate for μ_i(x/q,y), where q is a prime divisor of n.

    μ_i(x/q,y)=∑_p∈ J_i1/p^α_q{1+O(1/u_q+ log y/y)},

where u_q:= u-log q/log y. By substitution we obtain x/q =y^u_q. Set the saddle point α_q:=α (x/q,y), defined as the unique real number satisfying in 

    ∑_p≤ ylog p/p^α_q-1=log(x/q).




We are ready to prove the following lemma that shows the difference between μ_i(x/q,y) and μ_i(x,y) is small.  
 Let q be a prime divisor of n∈ S(x,y), then we have

    |μ_i(x/q,y)-μ_i(x,y)|≪μ_i(x,y)/u.


 
We use the estimate

    0<-α'(u):= -dα(u)/du≍u̅/u^2 log y,

established in  <cit.>, where u̅:= min{u, y/log y}.  By (<ref>), we deduce 


    |α^'(u)| ≪1/ulog y.

Then applying (<ref>), gives that

    α -α_q ≤∫_u_q^u|α^'(v)| dv    ≪∫_u^u_qdv/vlog y
       = 1/log ylog(u/u_q) ≍log q/log y log x.

By expanding μ_i(x/q,y)-μ_i(x,y) and using (<ref>) and (<ref>), we get

    |μ_i(x/q,y)-μ_i(x,y)|    = |∑_p∈ J_i(Ψ(x/pq,y)/Ψ(x/q,y)- Ψ(x/p,y)/Ψ(x,y))| 
       ≤∑_p∈ J_i1/p^α{| p^α -α_q-1 |+O(1/u+ log y/y)}.

By the Taylor expansion of the exponential function and invoking (<ref>) we obtain

    exp{(α-α_q)log p}-1 ≪log p log q/log y log x.

We recall that p,q ≤ y for 1≤ i≤ N and i=∞. From this we infer that 

    | p^α-α_q-1|≪1/u,

this finishes the proof. 

In the following lemma we shall find an upper bound for σ_i^2(x,y) (defined in (<ref>)) for each i∈{1,2,…, N,∞}.

We have 

    σ_i^2 (x,y) ≪μ_i(x,y)+ μ_i^2(x,y)/u,

where i∈{1,2,… ,N,∞}.


By the definition of σ_i^2 (x,y) in (<ref>), we have

    σ_i^2(x,y) =1/Ψ(x,y)∑_n∈ S(x,y)[ ω_i^2(n)-2μ_i(x,y)ω_i(n)+μ_i^2(x,y)].

Using the definition of ω_i(n) in (<ref>), gives

    ∑_n∈ S(x,y)ω_i(n)=∑_n∈ S(x,y)∑_ p∈ J_i1_p|n = ∑_p∈ J_iΨ(x/p,y),

where the indicator function 1_p|n is 1 or 0 according to the prime p divides n or not. By the definition of μ_i(x,y) in  (<ref>), one can deduce that

    ∑_n∈ S(x,y)ω_i(n)= Ψ(x,y) μ_i(x,y).

 By applying (<ref>) and the equation above, we obtain



    Ψ(x,y)σ_i^2(x,y)    =∑_n∈ S(x,y)[ ω_i^2(n)-2μ_i(x,y)ω_i(n)+μ_i^2(x,y)] 
       =∑_n∈ S(x,y)ω_i^2(n)-2Ψ(x,y)μ_i^2(x,y)+ψ(x,y)μ_i^2(x,y)
        =(∑_p,q ∈ J_j
     p≠ qΨ(x/pq,y))- Ψ(x,y)μ_i^2(x,y)
    +∑ _p∈ J_iΨ(x/p,y)
       :=S_1 +S_2,

where S_1:=∑_p,q ∈ J_j
 p≠ qΨ(x/pq,y)- Ψ(x,y)μ_i^2(x,y) and S_2:= ∑ _p∈ J_iΨ(x/p,y).
 We next find an upper bound for each S_i. We first consider S_1, by using  (<ref>) we can get

    ∑_p,q ∈ J_i
     p≠ qΨ(x/pq,y)-
    Ψ(x,y)μ_i^2(x,y) ≤∑_p∈ J_iΨ(x/p,y)(μ_i(x/p,y)-μ_i(x,y)).
 
By Lemma <ref> and using (<ref>), we obtain the following upper bound for S_1

    S_1≤ C Ψ(x,y)μ_i^2(x,y)/u,

where C is a positive constant. It remains to estimate S_2, from (<ref>) we have

    S_2= Ψ(x,y)μ_i(x,y).

By substituting the upper bounds for S_1 and S_2,  we get

    σ_i^2(x,y) = S_1+S_2/Ψ(x,y)≪( μ_i(x,y)+μ_i^2(x,y)/u),

and the proof is complete.


Now we give an order of magnitude for μ_i(x,y), where i∈{1,2,…, N, ∞}

We have

    μ_i(x,y) ≍κY^1-1/2^i/log y,

where  i∈{1,2,…, N,∞}, and 
    Y:= y^1-α.



By the definition of each J_i, we obtain the following simple inequalities
 
    1/y^α(1-1/2^i)#{ p∈ J_i}≤∑_p∈ J_i1/p^α≤1/(1-κ)y^α(1-1/2^i)#{ p∈ J_i}.
 
 By applying the prime number theorem, we obtain

    #{p: p ∈ J_i}   =π(y^1-1/2^i)-π((1-κ)y^1-1/2^i)
       =y^1-1/2^i/log(y^1-1/2^i)-(1-κ)y^1-1/2^i/log((1-κ)y^1-1/2^i)+O(y^1-1/2^i/log^2 y) 
       = y^1-1/2^i/(1-1/2^i) log y-(1-κ)y^1-1/2^i/(1-1/2^i)log y(1+O( log (1-κ)/log y))
       = κ y^1-1/2^i/(1-1/2^i)log y(1+o(1)),

The last equality is true, since the given values of κ and N in (<ref>) and (<ref>) imply

    κ≍ 1/(log_2 y log_3 y).

By substituting (<ref>) in (<ref>) we have

    μ_i(x,y)≍κ Y^1-1/2^i/log y,


By the above lemmas, we are now ready for proving the following proposition.
 If u and y satisfy in range given in(<ref>), we have

    #{n∈ S(x,y): ω_i(n)> μ_i(x,y)/2  ∀ i∈{1,…,N,∞}}∼Ψ(x,y)   as   x,y→∞,



 By the Chebyshev's inequality in (<ref>) and using the upper bound for σ_i^2(x,y) in lemma (<ref>), we get
 
    #{n∈ S(x,y): ω_i(n)≤μ_i(x,y)/2}≪Ψ(x,y)(1/μ_i(x,y)+ 1/u).

 By the above inequality, we obtain an upper bound for the following set
 
    M    := #{n∈ S(x,y): ∃ i ∈{1,…,N,∞}  such that   ω_i(n)≤μ_i(x,y)/2}
       ≪Ψ(x,y)[1/μ_∞(x,y)+N/u+∑_i=1^N1/μ_i(x,y)].

Our main task that finishes the proof is to find a range such that M/Ψ(x,y) tends to 0.

By using Lemma <ref> and substituting the order of magnitude of μ_i(x,y) in (<ref>), we get

    M≪Ψ(x,y) [log y/κ Y+ N/u+ log y/κ∑_i=1^N1/Y^1-1/2^i].

In what follows, we find a lower bound for Y in two different ranges of y 
 

(𝐢): If y≤ (log x)^2, then by (<ref>) α≤ 1/2+ o(1) as y→∞. Therefore,


    Y≥ y^1/2-o(1) ≥ y^1/3.

By substituting this lower bound in (<ref>) and using the precise value of N in (<ref>), we have


    M   ≪Ψ(x,y) [log y/κ y^1/3+ N/u+log y/κ y^1/3∑_i=1^Ny^1/3(2^i)]
       ≪Ψ(x,y)[log_2 y/u+ y^1/6log y/κ y^1/3(1+ O(Ny^-1/12))]
       ≪Ψ(x,y)log y/κ y^1/6,

By using the asymptotic value of κ in (<ref>), we obtain

    M ≪Ψ(x,y) log y log_2 y log_3 y/y^1/6,

and clearly we have
 
    M=o(Ψ(x,y))   as   x,y→∞,

this finishes the proof for the case y ≤ (log x)^2.


(𝐢𝐢): If y≥ (log x)^2, by applying (<ref>), we have

    1-α = ξ(u)/log y +O(1/L_ϵ (y)+ 1/u(log y)^2).

Using  <cit.>, we have the following estimate of ξ


    ξ(t) =log (tlog t)+ O(log_2 t/log t)   if   t>3.

Therefore,

    1-α = log (ulog u)/log y+ O(log_2 u/log y log u),

Thus, we get

    Y    = u log u [1+O(log_2 u/log u)]
       ≍ u log u.


 We now find an estimate for Y, when y≥log x. By applying the estimate in (<ref>), we have


    Y    = exp{log y -log (1+log y/log x) +O(log(1+ y/log x)loglog y/log y)}
        =y/1+y/log x{1+ O(log (y/log x)loglog y/log y)}
       = y/1+y/log x{1+O(loglog y)}
       ≍y log_2 y/1+y/log x.

When y≥log x we have the following bounds for Y


    log x loglog y ≪ Y ≪ y loglog y.


By combining the above with the estimate in (<ref>), and using the value of N in (<ref>), we get 


    M    ≪Ψ(x,y) [ log y/κ u log u+ N/u+ log y/κ u log u∑_i=1^N (u log u)^1/2^i]
       ≪Ψ(x,y) [ N/u+ log y/κ u log u((ulog u)^1/2 + (ulog u )^1/2^2+...+(ulog u)^1/2^N)]
       ≪Ψ(x,y)[N/u+ log y/κ(ulog u)^1/2(1+O( N(ulog u)^-1/4))]
       ≪Ψ(x,y) [ log_2 y/u+ log y/κ(ulog u)^1/2],

By using the order of κ in (<ref>), one can arrive at the following upper bound of M

    M≪Ψ(x,y)log y log_2 y log_3 y/(u log u)^1/2.

So there exists a constant c such that for all i∈{1,…, N, ∞}, we have

    #{ n∈ S(x,y) : ω_i(n)> μ_i (x,y)/2   ∀ i }≥Ψ(x,y)(1-clog y log_2 y log_3 y/ (u log u)^1/2),
 
and this finishes the proof by letting 
    ulog u/(log y log_2 y log_3 y)^2 →∞.

 

If x and y satisfy the range (<ref>), then almost all n in S(x,y) are divisible by at least one prime factor p_i in J_i, and N prime factors q_1,..., q_N in J_∞. Moreover, the product ∏_i=1^Np_i q_i has a divisor D_j in each of intervals [(1-κ)^N y^N-j/2^N,y^N-j/2^N], where j∈{0,1,...,2^N-1}.
 
 
 
The first part of Corollary is a direct conclusion of Proposition <ref>.

 For the second part, let n be a y-smooth integer satisfying the first part of Corollary. We fix the following divisor of n
 
    D:=∏_i=1^N p_i q_i,

where p_i ∈ J_i and q_1,...,q_N ∈ J_∞.

Let j be an arbitrary integer in {0,1,...,2^N-1}. Moreover, we define 

    a_0:= N-∑_i=1^Na_i,

where a_i's get the values 0 or 1 such that 

    ∑_i=1^Na_i/2^i = j/2^N.

 We now define the divisor of D_j of D with the following form
  
    D_j:= ∏_i=1^N p_i^a_i∏_i=1^a_0 q_i,

By using the bounds of  p_is and q_is, one can get the following bounds for D_j.

    (1-κ)^N y^N-∑_i=1^Na_i/2^i≤ D_j ≤ y^N-∑_i=1^Na_i/2^i,
 
By using (<ref>), we have

    (1-κ)^N y^N-j/2^N≤ D_j ≤  y^N-j/2^N,

and this finishes our proof.

We are ready now to prove Theorem <ref>.
 
 Let n≤ (1-η)x be a y-smooth integer with at least one prime factor p_i in each  J_i , where i=1,..,N, and N prime divisors q_1,q_2, ...,q_N in J_∞. Set
 
    m:= n/∏_i=1^N p_i q_i.
 
 By this definition, we get
  
    n/∏_i=1^N p_iq_i≥n/y^2N >√(n),
  
 when 4N≤ u. Thus,
 
    m>√(n).

 Let {r_v} be the increasing sequence of prime factors of m and set d_v=r_1...r_v.

Clearly, m has at least one divisor bigger than √(n)/y^N. We suppose  that l is the smallest integer such that d_l ≥√(n)/y^N, and evidently we have  
    d_l-1≤√(n)/y^N,
 
So, we arrive at the following bounds for d_l


    √(n)/y^N≤ d_l ≤ yd_l-1≤√(n)/y^N-1,

We pick k ∈{0,1,2...,2^N-1} such that 

    √(n)/y^N y^k/2^N≤ d_l ≤√(n)/y^Ny^(k+1)/2^N.

By the second part of Corollary <ref>, for every k in {0,1,...,2^N-1} there exists a divisor D_k such that
 
    (1-κ)^Ny^N-k/2^N≤ D_k ≤ y^N- k/2^N,

 We define d:= d_l D_k, we have

    (1-κ)^N√(n)≤ d ≤ y^1/2^N√(n),

 By using the values of N in (<ref>) and κ in (<ref>), we have

    e^-η/2√(n)≤ d ≤ e^η/2√(n).

Applying the Taylor expansion for exponential functions, gives 

    (1-η +η^2/2+O(η^3))^1/2√(n)≤ d ≤(1+η +η^2/2+O(η^3))^1/2√(n).

By using the assumption n≤ (1-η)x in the upper bound and lower bound above, we obtain 

    d≤(1-η^2/2+O(η^3))^1/2√(x)≤√(x),

 and 

    n/d≤(1+η+η^2/2+ O(η^3))^1/2√(n)≤(1-η^2/2+O(η^3))^1/2√(x)≤√(x).

Thus, we can write n∈ S((1-η)x,y) as the product of two divisors less than √(x), and we can deduce that 

    Ψ((1-η)x,y)≤ A(x,y) ≤Ψ(x,y),

By using (<ref>), we have


    Ψ((1-η)x,y)/Ψ(x,y) = (1-η)^α{ 1+O(1/u +log y/y)}→ 1   as   x,y→∞,

this finishes the proof.
 

 
  
 
 

§ PROOF OF THEOREM<REF>


 In this section, we shall study the behaviour  of A(x,y) for large values of y. When y takes values very close to x, then the set of y-smooth integers contains integers having large prime factors. As we explained in the heuristic argument, one can expect that A(x,y)= o(Ψ(x,y)). To show this assertion, we recall the idea of Erdős used to prove the multiplication table problem for integers up to x.

We start our argument by giving an upper bound for A^*(x), defined by

    A^*(x):= #{ ab: a,b≤√(x)  and   (a,b)=1}.

We shall find an upper bound of A^*(x) by considering the number of prime factors of a and b. We first define 

    π_k(x) := #{n≤ x: ω(n)= k}

Therefore,

    A^*(x)   ≤∑_kmin{π_k(x) , ∑_j=1^k-1π_j(√(x)) π_k-j (√(x))}
       ≤∑_kmin{cx/log x(log_2x)^k-1/(k-1)!, ∑_j=1^k-1c√(x)/log√(x)(log_2 √(x))^j-1/(j-1)!c√(x)/log√(x)(log_2 √(x))^k-j-1/(k-j-1)!},

where in the last inequality, we used the well-known result of Hardy and Ramanujan that states there are absolute constants C and c such that

    π_k(x) ≤cx/log x(log_2x+C)^k-1/(k-1)!  for   k=0,1,2,..   and   x≥ 2.

By simplifying the upper bound in (<ref>) and using Stirling's formula

    n!∼ n^n+1/2e^-n

we obtain

    A^*(x)   ≤∑_kmin{cx/log x(log_2 x)^k-1/(k-1)! , 4c^2 x/(log x)^2∑_j=0^k-21/(k-2)!k-2  j(log_2 √(x))^k-2}
       = ∑_kmin{cx/log x(log_2 x)^k-1/(k-1)! ,4c^2 x/(log x)^2(2log_2 √(x))^k-2/(k-2)!}
       = ∑_k≤log_2x/log 24c^2 x/(log x)^2(2log_2√(x))^k-2/(k-2)!  
    +  ∑_k> log_2 x/log 2cx/log x(log_2 x)^k-1/(k-1)!
       ≪x/(log x)^1-1+loglog 2/log 2(log_2x)^1/2→ 0   as   x→∞.


 We shall get the same upper bound for A(x). Let n≤ x and there are a and b less than √(x) such that n=ab. If (a,b)= 1 then n is counted by A(x) , and if (a,b)=d>1 then we can write n as n= a^' b^'d^2 such that (a^',b^')=1. So, n/d^2≤x/d^2, and n/d^2 will be counted by A(x/d^2). Therefore,

    A(x) ≤∑_d ≤√(x)A^*(x/d^2) ≪ A^*(x)

By (<ref>), we get

    A(x) ≪x/(log x)^1-1+loglog 2/log 2(log_2x)^1/2.

Thus,

    A(x)=o(x)   as   x→∞.




 Motivated by Erdős' idea for the multiplication table of integers up to x, we apply a similar method to find an upper bound for A(x,y).

 As we mentioned in introduction, Alladi and Hildebrand proved that the number of prime divisors of y-smooth integers is normally about u+loglog y (the expectation value of Ω(n)). So if u is smaller than loglog y, then by Alladi and Hildebrand's results, the value of Ω(n) in this range will be normally about loglog y. If u ≤loglog y, then y takes large values bigger than x^1/(loglog x), and we expect a same upper as (<ref>) bound for the following function

    Π(x,y;k):= ∑ _n∈ S(x,y)
    Ω(n)=k1.


 The first step of proof is to study the following function which plays a crucial role in this section. Let

    N_k(x,y,z) :=#{n∈ S(x,y): Ω_z(n)=k},

where Ω_z(n) is the truncated version of Ω(n), only counting divisibility by primes not exceeding z with their multiplicities. In other words

    Ω_z(n):= ∑ _p^v||n
    p≤ zv.

In the following lemma, by using induction on k, we shall find an upper bound of type (<ref>) for N_k(x,y,z). The reason of applying truncation is to sieve out prime factors exceeding some power of y which are the cause of big error terms as k increases in each step of induction. The upper bound of N_k(x,y,z) leads us to generalize Erdős' idea for y-smooth integers in a certain range of y.



Let u ≤ (C-ϵ)loglog y, where C is a positive constant and ϵ>0 is arbitrarily small. Set the parameter z such that

    loglog z≪ u.

Then, there are constants A and B such that the inequality

    N_k(x,y,z)≤AΨ(x,y)/log z(loglog z+B)^k/k!

holds for every integer k>0.
























 


When k=0, by (<ref>), evidently we have

    N_0 (x,y,z) = θ(x,y,z) ≤ cΨ(x,y)/log z,

where c>0 is a constant.
When k=1, we can represent n as n=pm, where p≤ z and every prime factor q of m is between z and y, then using the definition of θ(x,y,z) we have


    N_1(x,y,z)=∑_p≤ z∑_m≤ x/p
     q|m ⇒ z≤ q≤ y1=∑_p≤ zθ(x/p,y,z).

By applying the estimate (<ref>) and (<ref>), there is constant c such that



    N_1(x,y,z) ≤∑_p≤ zcΨ(x/p,y)/log z = cΨ(x,y)/log z∑_p≤ z1/p^α{1+O(1/u)}.


 For the last summand we have


    ∑_p≤ z1/p^α   = ∑_p≤ z1/p(p^1-α)
       = ∑_p≤ z1/p{1+O((1-α)log p)},

since  (1-α)log p ≤ (1-α)log z, and (1-α)log z is bounded in our range (see (<ref>)). Therefore,

    ∑_p≤ z1/p^α= log_2 z + O((1-α) log z),

By using the estimate of α in (<ref>) and the upper bound of z, we get 

    (1-α)log z≪log u/log ylog z ≪log u/log_2 y≪log_3 y/log_2 y,

and we obtain

    ∑_p≤ z1/p^α= log_2 z +O(log _3 y/log _2 y).

Thus,

    ∑_p≤ z1/p^α{ 1+O(1/u)} = loglog z+ O(1),

since we have loglog  z ≪ u. 

Substituting (<ref>) in the upper bound of N_1(x,y,z), gives 

    N_1(x,y,z) ≤cΨ(x,y)/log z(log_2z+O(1)).

 We will show the lemma with A=c and B=O(1).
 We argue by induction: we assume that the estimate in (<ref>) is true for any positive integer k, we now prove it for n∈ S(x,y) with Ω_z(n)=k+1. There are k+1 ways to write n as n=pm_1m_2 such that p≤ z and Ω_z(m_1)=k and every prime factor of m_2 is greater than z. Then we have

    N_k+1(x,y,z)   = 1/(k+1)∑_p≤ z∑_m_1∈ S(x/(p),y)
    Ω_z(m_1)=k 
     m_2 ∈ S(x/(pm_1),y)
    q|m_2 ⇒ q>z 1
     ≤1/(k+1)∑_p≤ z∑_m_1∈ S(x/(p),y)
    Ω_z(m_1)=k 1
       = 1/(k+1)∑_p≤ zN_k(x/p , y, z)

By the assumption for Ω_z(n)=k and (<ref>), we get


    N_k+1(x,y,z)   ≤A(log_2z+B)^k/log z(k+1)!∑_p≤ zΨ(x/p,y) 
        =AΨ(x,y)/log z(log_2z+B)^k/(k+1)!∑_p≤ z1/p^α{1+O(1/u)}.

 By applying the estimate in (<ref>), we arrive at the following bound for N_k+1(x,y,z)


    N_k+1(x,y,z)≤AΨ(x,y)/log z(log_2z+B)^k+1/(k+1)!,

 so we derived our desired result.





















For a small ϵ>0, we set u < (λ/log 2-ϵ)log_2 y, where λ is a fixed real number in the open interval (1-2log 2 , 1-log 2).
  We now set z satisfying

    loglog z= log 2/λ u,

 so the given ranges of u and z satisfy the conditions of Lemma <ref>.

By the definition of A(x,y), we have the following evident bound of A(x,y)

    A(x,y) ≤∑_kmin{∑_n∈ S(x,y)
    Ω_z(n)=k1 , ∑_j=1^k-1∑_a∈ S(√(x),y)
    Ω_z(a)=j1∑ _b∈ S(√(x),y)
    Ω_z(b)=k-j1}.

 We set  

    L=⌊ H log_2 z⌋,

where 

    H:= 1-λ/log 2.

We have 1-2log 2 < λ< 1-log 2. Thus, 1<H<2.


By using (<ref>), we write the following bound for A(x,y)

    A(x,y)    ≤#{ n∈ S(x,y): Ω_z(n)> L} +#{ ab: a,b ∈ S(√(x),y), Ω_z(a)+Ω_z(b)≤ L}
       = ∑_k>LN_k(x,y,z) + ∑_ k≤ L∑_j=0^k N_j(√(x),y,z)N_k-j(√(x),y,z).

By applying Lemma <ref>, we have 

    A(x,y)    ≪∑_k> LΨ(x,y)/log z(log_2z+c)^k/k!+ ∑_k≤ L∑_j=0^kΨ^2(√(x),y)/log ^2 z(log_2 z +c)^j/j!(log_2 z+c)^k-j/(k-j)!
        =∑_k>LΨ(x,y)/log z(log_2 z+c)^k/k!+ ∑_k≤ LΨ^2(√(x),y)/log ^2 z∑_j=0^k1/k!k j(log_2 z+ c)^k
       =∑_k>LΨ(x,y)/log z(log_2 z+c)^k/k!+∑_k≤ LΨ^2(√(x),y)/log ^2 z(2log_2 z+c)^k/k!.

By applying the simple form of Ψ(x,y) in Corollary <ref>, and using the assumption (<ref>), we get

    Ψ^2(√(x),y)/Ψ(x,y)≍ (log z)^λ  as   u,y→∞.

 Thus,

    A(x,y)≪Ψ(x,y)/log z∑_k>L(log_2 z+c)^k/k!+ (log z)^λΨ(x,y)/log ^2 z∑_k≤ L(2log_2 z+c)^k/k!.

The maximum values of functions in the above summands (with respect to k) are attained at k=⌊log_2 z⌋ and k=⌊2log_2 z⌋ respectively. We have loglog z < L < 2 loglog z, so the function in the first summation in (<ref>) in decreasing for k>L, and by using Stirling's formula k!∼ k^k+1/2e^-k, we have


    ∑_k> L(log_2z)^k/k!   = ∑_Hlog_2 z<k≤ elog_2 z(log_2 z)^k/k!+∑_elog_2z < k ≤ 2elog_2z(log_2z)^k/k!+∑_k> 2elog_2 z(log_2 z)^k/k!
       ≪ (log_2z)((e/H)^Hlog_2z +1)
       ≪1/(log z)^Hlog H-H.

The function in the second summation in (<ref>) is increasing for k≤ L, and we have

    ∑_k≤ L(2log_2 z+c)^k/k!≪ (log_2 z)(2e/H)^Hlog_2z= 1/(log z)^Hlog H -H -Hlog 2

 Substituting the upper bounds obtained in (<ref>) and (<ref>) in  (<ref>), and using the definition of H, gives

    A(x,y) ≪Ψ(x,y)/(log z)^ G(H),

where 

    G(H) := 1+Hlog H -H.

The function G(H) is an increasing function in the interval (1,2) with a zero at H=1. Thus, for any arbitrary 1-2log 2 < λ < 1-log 2, we have
 
    A(x,y)= o(Ψ(x,y))   as   x,y→∞,
 
 so we obtained our desired result.



plain


