On Product Sets of Arithmetic Progressions

Max Wenqiang Xu Supported by the Cuthbert C. Hurd Graduate Fellowship in Mathematics, Stanford Yunkun Zhou Supported by NSF GRFP Grant DGE-1656518

Abstract

We prove that the size of the product set of any finite arithmetic progression $\mathcal{A}\subset\mathbb{Z}$ satisfies

|\mathcal{A}\cdot\mathcal{A}|\geq\frac{|\mathcal{A}|^{2}}{(\log|\mathcal{A}|)^{2\theta+o(1)}},

where $2\theta=1-(1+\log\log 2)/(\log 2)$ is the constant appearing in the celebrated Erdős multiplication table problem. This confirms a conjecture of Elekes and Ruzsa from about two decades ago.

If instead $\mathcal{A}$ is relaxed to be a subset of a finite arithmetic progression in integers with positive constant density, we prove that

|\mathcal{A}\cdot\mathcal{A}|\geq\frac{|\mathcal{A}|^{2}}{(\log|\mathcal{A}|)^{2\log 2-1+o(1)}}.

This solves the typical case of another conjecture of Elekes and Ruzsa on the size of the product set of a set $\mathcal{A}$ whose sumset is of size $O(|\mathcal{A}|)$ .

Our bounds are sharp up to the $o(1)$ term in the exponents. We further prove asymmetric extensions of the above results.

\dajAUTHORdetails

title = On Product Sets of Arithmetic Progressions, author = Max Wenqiang Xu and Yunkun Zhou, plaintextauthor = Max Wenqiang Xu, Yunkun Zhou, \dajEDITORdetailsyear=2023, number=10, received=4 January 2022, published=25 July 2023, doi=10.19086/da.84267, [classification=text]

1 Introduction

The celebrated Erdős multiplication table problem asks to estimate how many numbers can be represented as the product of two positive integers which are at most $N$ . It is a classical result [10] that there are $o(N^{2})$ such numbers, which can be proved by simply considering the typical number of prime factors of an integer $n\leq N$ . Erdős [8] first determined the answer up to a $(\log N)^{o(1)}$ factor:

\Big{|}[N]\cdot[N]\Big{|}=\frac{N^{2}}{(\log N)^{2\theta+o(1)}},

(1.1)

where $[N]=\{1,\ldots,N\}$ , $\theta=1-\frac{1+\log\log 4}{\log 4}$ (which implies that $2\theta=1-\frac{1+\log\log 2}{\log 2}$ ), and $\mathcal{A}\cdot\mathcal{A}$ is defined to be $\{aa^{\prime}:a,a^{\prime}\in\mathcal{A}\}$ for any set $\mathcal{A}$ . The finer-order term was improved later by Tenenbaum [32]. Remarkably, Ford [12] has determined the quantity up to a constant factor:

\Big{|}[N]\cdot[N]\Big{|}\asymp\frac{N^{2}}{(\log N)^{2\theta}(\log\log N)^{3/2}}.

(1.2)

There is also work on generalizations of the Erdős multiplication table problem to higher dimensions: see [16] for references.

In this paper, we are interested the same problem but with $[N]$ replaced by an arbitrary arithmetic progression $\mathcal{A}$ of $N$ integers. In some cases the size of the product set can be as large as the trivial upper bound $\binom{N+1}{2}$ , which is of order $N^{2}$ . One example that achieves this bound is $\{1+kd:k\in[N]\}$ where $d>2N$ . It is interesting to know whether the size of the product set of any arithmetic progression with given length $N$ can be substantially smaller than the bound in (1.1). Elekes and Ruzsa [7] conjectured that it cannot. In this paper, we prove their conjecture.

Theorem 1.1.

Let $\mathcal{A}\subseteq\mathbb{Z}$ be a finite arithmetic progression and $\theta=1-\frac{1+\log\log 4}{\log 4}$ . Then

|\mathcal{A}\cdot\mathcal{A}|\geq|\mathcal{A}|^{2}(\log|\mathcal{A}|)^{-2\theta-o(1)}.

The strongest lower bound we can prove is $|\mathcal{A}|^{2}(\log|\mathcal{A}|)^{-2\theta}(\log\log|\mathcal{A}|)^{-7-o(1)}$ (Theorem 7.1), which is sharp up to a power of $\log\log|A|$ .

We also prove an asymmetric version of the conjecture, which strengthens Theorem 1.1.

Theorem 1.2.

Let $\mathcal{A},\mathcal{B}\subseteq\mathbb{Z}$ be two finite arithmetic progressions with lengths $2\leq|\mathcal{B}|\leq|\mathcal{A}|$ and $\theta=1-\frac{1+\log\log 4}{\log 4}$ . Then

|\mathcal{A}\cdot\mathcal{B}|\geq{|\mathcal{A}||\mathcal{B}|}{(\log|\mathcal{A}|)^{-\theta-o(1)}(\log|\mathcal{B}|)^{-\theta}},

where the $o(1)$ terms go to zero as $|\mathcal{A}|$ tends to infinity.

Remark.

The two theorems above are sharp up to a $(\log|\mathcal{A}|)^{o(1)}$ factor. The proof we present gives the error term in the form $\exp(O(\sqrt{\log\log|\mathcal{A}|}\log\log\log|\mathcal{A}|))$ . In fact, a stronger bound up to a $(\log\log|\mathcal{A}|)^{O(1)}$ factor can be obtained. We leave details of the proof to the stronger error term to Appendix A.

A particular structural property of arithmetic progressions $\mathcal{A}$ is that it has small sumset. The celebrated sum-product conjecture [9] states that for any $\mathcal{A}\subseteq\mathbb{Z}$ ,

\max\{|\mathcal{A}+\mathcal{A}|,|\mathcal{A}\cdot\mathcal{A}|\}\gg|\mathcal{A}|^{2-o(1)},

(1.3)

where $\mathcal{A}+\mathcal{A}=\{a+a^{\prime}:a,a^{\prime}\in\mathcal{A}\}$ and $\ll$ is to denote up to a multiplicative constant. There has been much progress towards this conjecture (see [23] for the current record), though it is still wide open. One extremal case of the sum-product conjecture is the case where one of the sumset and product set is very small, in which, the conjecture is known to be true. Indeed, Chang [4] proved that

|\mathcal{A}\cdot\mathcal{A}|\ll|\mathcal{A}|\implies|\mathcal{A}+\mathcal{A}|\gg|\mathcal{A}|^{2},

which is sharp up to a multiplicative constant factor. See [19, 22] for discussions in other settings.

We are interested in the other extremal case where $|\mathcal{A}+\mathcal{A}|/|\mathcal{A}|$ is bounded, which seems to be much more challenging. In contrast to Chang’s result [4], even if the doubling number (i.e. $|\mathcal{A}+\mathcal{A}|/|\mathcal{A}|$ ) is at most $2$ , the product set can still be smaller than $|\mathcal{A}|^{2}$ by a polylogarithmic factor (see (1.2)). Nathanson and Tenenbaum proved [20] that if $|\mathcal{A}+\mathcal{A}|<3|\mathcal{A}|-4$ , then $|\mathcal{A}\cdot\mathcal{A}|\gg|\mathcal{A}|^{2}/(\log|\mathcal{A}|)^{2}$ . This result was later generalized by Chang [3] to $h$ -fold product sets. Finally, Elekes and Ruzsa [7] proposed the following conjecture.

Conjecture 1.3 (Elekes and Ruzsa [7]).

Let $\mathcal{A}\subseteq\mathbb{Z}$ be a finite set. Then the following holds.

|\mathcal{A}+\mathcal{A}|\ll|\mathcal{A}|\implies|\mathcal{A}\cdot\mathcal{A}|\geq|\mathcal{A}|^{2}(\log|\mathcal{A}|)^{1-2\log 2-o(1)}.

Elekes and Ruzsa [7] showed that if $|\mathcal{A}+\mathcal{A}|\ll|\mathcal{A}|$ , then $|\mathcal{A}\cdot\mathcal{A}|\gg|\mathcal{A}|^{2}(\log|\mathcal{A}|)^{-1}$ when $\mathcal{A}$ is a finite set of integers. As a corollary of Solymosi’s remarkable result [28], the same implication holds when $\mathcal{A}$ is a finite set of reals. We remark that their proofs did not use specific properties of the integers, and we improve their bounds by taking the arithmetic information of integers into account. Indeed, the $2\log 2-1$ exponent has a natural arithmetic interpretation. By the Sathe-Selberg formula [25], the number of $n\leq N$ with $\Omega(n)=(2+o(1))\log\log N$ is about $N/(\log N)^{2\log 2-1+o(1)}$ , where $\Omega(n)$ is the number of prime factors of $n$ . Further we claim that the bound in Conjecture 1.3 is optimal up to $o(1)$ factor in the exponent. One simple example is to take $\mathcal{A}\subset[N]$ containing set of all numbers $n$ with $\Omega(n)=(1+o(1))\log\log N$ . By the Hardy-Ramanujan theorem one has $|\mathcal{A}|=(1+o(1))N$ . Since $A\cdot A$ is contained in the set of integers with $\Omega(n)=(2+o(1))\log\log N$ , combining this with the previously mentioned application of Sathe-Selberg’s formula, the claim follows.

We believe that to get the conjectured exponent $2\log 2-1$ , one has to take the arithmetic information into account. We also remark that for similar arithmetic reasons, the constant $2\log 2-1$ appears in recent work [5, 18, 29].

By the Freiman-Ruzsa theorem [15, 24], every set with constant doubling number is a dense subset of a generalized arithmetic progression of constant dimension. A natural case is that $\mathcal{A}$ is a dense subset of an arithmetic progression. In fact, in some sense this is also the typical case [1, 2]. In this paper, we prove that the Elekes-Ruzsa conjecture is true in this case.

Theorem 1.4.

Let $\delta\in(0,1]$ and $\mathcal{A}$ be a subset of an arithmetic progression $\mathcal{P}\subseteq\mathbb{Z}$ with $|\mathcal{A}|\geq\delta|\mathcal{P}|$ , then

|\mathcal{A}\cdot\mathcal{A}|\gg_{\delta}|\mathcal{A}|^{2}(\log|\mathcal{A}|)^{1-2\log 2-o(1)}.

We remark that Pomerance and Sárközy [21] proved a special case of Theorem 1.4 $(\mathcal{P}=[N])$ . We also prove a more general asymmetric version.

Theorem 1.5.

Let $\delta\in(0,1]$ and $\mathcal{A},\mathcal{B}$ be two subsets of two finite arithmetic progressions $\mathcal{P}_{1},\mathcal{P}_{2}\subseteq\mathbb{Z}$ , and $|\mathcal{A}|\geq\delta|\mathcal{P}_{1}|$ , $|\mathcal{B}|\geq\delta|\mathcal{P}_{2}|$ , then

|\mathcal{A}\cdot\mathcal{B}|\gg_{\delta}|\mathcal{A}||\mathcal{B}|(\log|\mathcal{A}|)^{\frac{1}{2}-\log 2-o(1)}(\log|\mathcal{B}|)^{\frac{1}{2}-\log 2-o(1)}.

Although Theorem 1.4 does not solve Conjecture 1.3 completely, it can be used to prove the case for doubling number up to $4$ (in terms of difference set). In this case, Eberhard, Green and Manners [6, Theorem 6.4] proved that $\mathcal{A}$ must be a subset of an arithmetic progression with positive density, and thus the following corollary can be deduced from Theorem 1.4 immediately.

Corollary 1.6.

Let $\varepsilon>0$ . Let $\mathcal{A}\subseteq\mathbb{Z}$ be a finite set with $|A-A|\leq(4-\varepsilon)|A|$ , then

|\mathcal{A}\cdot\mathcal{A}|\gg_{\varepsilon}|\mathcal{A}|^{2}(\log|\mathcal{A}|)^{1-2\log 2-o(1)}.

In Theorem 1.5, one can relax the condition that $\mathcal{A},\mathcal{B}$ are dense subsets of arithmetic progressions $\mathcal{P}_{1},\mathcal{P}_{2}$ , to the condition that $\mathcal{A}$ intersects an arithmetic progression $\mathcal{P}_{1}$ (with sizes $|\mathcal{P}_{1}|=\Theta(|\mathcal{A}|)$ ) with positive density, and a similar condition holds for $\mathcal{B}$ and $\mathcal{P}_{2}$ . Such $\mathcal{A}$ and $\mathcal{B}$ may have large sumsets.

Our Theorem 1.5 also easily implies the following observation. Consider the restricted sumsets

\mathcal{A}+_{G}\mathcal{B}:=\{a+b:(a,b)\in G)\},\quad|G|\geq(1-\varepsilon)|\mathcal{A}||\mathcal{B}|,

where $\varepsilon$ is a small absolute constant. If the restricted sumset is small, then one can get similar lower bounds on $|\mathcal{A}\cdot\mathcal{B}|$ as in Theorem 1.5. The proof simply consists of using the structural results in [17, 26] to conclude that such set $\mathcal{A},\mathcal{B}$ must overlap with some arithmetic progressions $\mathcal{P}_{1},\mathcal{P}_{2}$ heavily, and then applying Theorem 1.5 to conclude the proof. We leave the details for the interested reader.

We prove Theorems 1.2 and 1.5 by bounding the multiplicative energy from above.

Definition 1.7 (Multiplicative energy).

Let $\mathcal{A},\mathcal{B}$ be two finite subsets of integers. The multiplicative energy between $\mathcal{A},\mathcal{B}$ is defined as

E_{\times}(\mathcal{A},\mathcal{B}):=\left|\{(a_{1},a_{2},b_{1},b_{2})\in\mathcal{A}\times\mathcal{A}\times\mathcal{B}\times\mathcal{B}:a_{1}b_{1}=a_{2}b_{2}\}\right|.

When $\mathcal{A}=\mathcal{B}$ , we write $E_{\times}(\mathcal{A}):=E_{\times}(\mathcal{A},\mathcal{A})$ , which is called the multiplicative energy of $\mathcal{A}$ .

The first main theorem is about the multiplicative energy of any finite arithmetic progression.

Theorem 1.8.

Let $\mathcal{A}\subseteq\mathbb{Z}$ be a finite arithmetic progression. Then there exists a subset $\mathcal{A}^{\prime}\subseteq\mathcal{A}$ with size $|\mathcal{A}^{\prime}|\geq|\mathcal{A}|(\log|\mathcal{A}|)^{-\theta-o(1)}$ such that $E_{\times}(\mathcal{A}^{\prime})\ll|\mathcal{A}^{\prime}|^{2}.$

A stronger version in terms of the $o(1)$ term is achieved in Appendix A. The second main theorem is about the multiplicative energy of a dense subset of any finite arithmetic progression.

Theorem 1.9.

Let $\delta\in(0,1]$ and let $\mathcal{A}$ be a subset of a finite arithmetic progression $\mathcal{P}\subseteq\mathbb{Z}$ such that $|\mathcal{A}|\geq\delta|\mathcal{P}|$ . Then there exists a subset $\mathcal{A}^{\prime}\subseteq\mathcal{A}$ with size $|\mathcal{A}^{\prime}|\gg_{\delta}|\mathcal{A}|$ such that

E_{\times}(\mathcal{A}^{\prime})\ll_{\delta}|\mathcal{A}|^{2}(\log|\mathcal{A}|)^{2\log 2-1+o(1)}.

1.1 Proof ideas

Our main focus will be on Theorem 1.8 and Theorem 1.9, and all the rest of our results will follow from them fairly straightforwardly (See Section 2).

Theorem 1.8 and Theorem 1.9 are well understood when the arithmetic progression is just the first $N$ integers (See [31, 8, 13] for the special case of Theorem 1.8 and [21] for the special case of Theorem 1.9.) The classical proofs of both special cases involve estimates on $\pi_{k}(x)$ (the number of integers up to $x$ with $k$ distinct prime factors) and tools like Shiu’s Theorem on bounding mean values of multiplicative functions. The original arguments cannot be directly generalized because these tools are not applicable to general arithmetic progressions. Our main novelty is the deduction of the general case in the case where the parameters of the arithmetic progression lie in a certain range such that all classical tools are applicable. The deduction is completed by proving the desired upper bounds for multiplicative energies in the other cases via elementary counting arguments. After the deduction steps, we carefully employ and adapt the method developed in [13, 8, 12, 14] to conclude the proof of both Theorem 1.8 and Theorem 1.9.

1.2 Organization

We organize the paper as follows. In Section 2 we prove Theorems 1.1, 1.2, 1.4 and 1.5 assuming Theorems 1.8 and 1.9. This is done by applying Cauchy-Schwarz type arguments (see Lemma 2.1). The remaining sections are devoted to proving the main Theorems 1.8 and 1.9. To prove Theorem 1.9, we first do a sequence of reduction steps in Section 3 as a preparation to proving the essential case of Theorem 1.9 in Section 4. We study the number of elements with a fixed number of prime factors in arithmetic progressions in Section 5 and crucially use it to complete the proof of Theorem 1.8 in Section 6. Finally in Section 7 we make conjectures about both problems.

1.3 Notations

For two functions $f,g:\mathbb{R}\to\mathbb{R}$ , we write $f\ll g,g\gg f,g=\Omega(f)$ or $f=O(g)$ if there exists a positive constant $C$ such that $f\leq Cg$ , and we write $f\asymp g$ or $f=\Theta(g)$ if $f\ll g$ and $g\gg f$ . We write $f=o(g)$ if $f(x)\leq\epsilon g(x)$ for any $\epsilon>0$ when $g(x)$ is sufficiently large. We write $\ll_{\delta}$ or $\gg_{\delta}$ if the implicit constant depends on $\delta$ . Throughout the paper, $\theta$ always denotes the constant $1-\frac{1+\log\log 4}{\log 4}\approx 0.043...$ . For two sets $\mathcal{A}$ and $\mathcal{B}$ , we write $\mathcal{A}\mathcal{B}=\mathcal{A}\cdot\mathcal{B}=\{ab:a\in\mathcal{A},b\in\mathcal{B}\}$ . When $\mathcal{A}=\{a\}$ is a singleton, we write $a\mathcal{B}=\{a\}\cdot\mathcal{B}$ . For positive integer $n$ , $\omega(n)$ denotes the number of distinct prime factors of $n$ and $\phi(n)$ is the Euler’s totient function. All logarithms are base $e$ .

2 Reduction to multiplicative energy estimates

In this section, we show that Theorems 1.8 and 1.9 imply all the other main results. The implications follow from the Cauchy-Schwarz inequality (see Lemma 2.1). The proof of Lemma 2.1 is standard (e.g., see [30] Corollary 2.10 for an additive version): we include it here for completeness.

Lemma 2.1.

Let $\mathcal{A},\mathcal{B}$ be nonempty sets of nonzero integers. Then we have

1.

$|\mathcal{A}\cdot\mathcal{B}|\geq\frac{|\mathcal{A}|^{2}|\mathcal{B}|^{2}}{E_{\times}(\mathcal{A},\mathcal{B})}.$
2.

$E_{\times}(\mathcal{A},\mathcal{B})\leq\sqrt{E_{\times}(\mathcal{A})E_{\times}(\mathcal{B})}$ .

Proof.

For any two sets of integers $\mathcal{X},\mathcal{Y}\subset\mathbb{Z}\backslash\{0\}$ , we define

r_{\mathcal{X}\cdot\mathcal{Y}}(m):=|(x,y)\in\mathcal{X}\times\mathcal{Y}:xy=m|,

and similarly define define ratio representation functions $r_{\mathcal{X}/\mathcal{Y}}(m)$ for $m\in\mathbb{Q}$ . By Definition 1.7 and the Cauchy-Schwarz inequality,

|\mathcal{A}\cdot\mathcal{B}|\cdot E_{\times}(\mathcal{A},\mathcal{B})=\sum_{m\in\mathcal{A}\cdot\mathcal{B}}1\cdot\sum_{m\in\mathcal{A}\cdot\mathcal{B}}r_{\mathcal{A}\cdot\mathcal{B}}(m)^{2}\geq\left(\sum_{m\in\mathcal{A}\cdot\mathcal{B}}r_{\mathcal{A}\cdot\mathcal{B}}(m)\right)^{2}=|\mathcal{A}|^{2}|\mathcal{B}|^{2}.

This gives (1). By Definition 1.7, and noting that $a_{1}a_{2}=a_{1}^{\prime}a_{2}^{\prime}$ is equivalent to $\frac{a_{1}}{a_{1}^{\prime}}=\frac{a_{2}^{\prime}}{a_{2}}$ , we have

E_{\times}(\mathcal{A})=\left|\{(a_{1},a_{2};a_{1}^{\prime},a_{2}^{\prime})\in\mathcal{A}^{4}:a_{1}a_{2}=a_{1}^{\prime}a_{2}^{\prime}\}\right|=\sum_{m\in\mathbb{Q}}r_{\mathcal{A}/\mathcal{A}}(m)^{2}.

We have a symmetric equation for $\mathcal{B}$ . By the Cauchy-Schwarz inequality, we have

E_{\times}(\mathcal{A})E_{\times}(\mathcal{B})=\left(\sum_{m\in\mathbb{Q}}r_{\mathcal{A}/\mathcal{A}}(m)^{2}\right)\cdot\left(\sum_{m\in\mathbb{Q}}r_{\mathcal{B}/\mathcal{B}}(m)^{2}\right)\geq\left(\sum_{m\in\mathbb{Q}}r_{\mathcal{A}/\mathcal{A}}(m)r_{\mathcal{B}/\mathcal{B}}(m)\right)^{2}.

The right hand side is the square of the following counting

\left|\{(a_{1},a_{2};b_{1},b_{2})\in\mathcal{A}\times\mathcal{A}\times\mathcal{B}\times\mathcal{B}:a_{1}/a_{2}=b_{1}/b_{2}\}\right|=E_{\times}(\mathcal{A},\mathcal{B}).

The equality is because $a_{1}/a_{2}=b_{1}/b_{2}$ is equivalent to $a_{1}b_{2}=a_{2}b_{1}$ . Hence we have (2). ∎

Assuming Theorems 1.8 and 1.9, we prove all the theorems regarding product sets (Theorems 1.1, 1.2, 1.4 and 1.5) via Lemma 2.1. Before we proceed to the proof, we remark that the condition in Lemma 2.1 that $\mathcal{A},\mathcal{B}$ do not contain $0$ is a mild technical restriction, as deleting one single element changes the size of product sets by at most $O(|\mathcal{A}|+|\mathcal{B}|)$ , and changes multiplicative energy by at most $O(|\mathcal{A}||\mathcal{B}|)$ , which are negligible for our purpose.

Proof of Theorems 1.1 and 1.2 assuming Theorem 1.8.

By Theorem 1.8, there exist subsets $\mathcal{A}^{\prime}\subseteq\mathcal{A}$ and $\mathcal{B}^{\prime}\subseteq\mathcal{B}$ with sizes $|\mathcal{A}^{\prime}|\gg|\mathcal{A}|(\log|\mathcal{A}|)^{-\theta-o(1)},|\mathcal{B}^{\prime}|\gg|\mathcal{B}|(\log|\mathcal{B}|)^{-\theta-o(1)},$ such that $E_{\times}(\mathcal{A}^{\prime})\ll|\mathcal{A}^{\prime}|^{2},E_{\times}(\mathcal{B}^{\prime})\ll|\mathcal{B}^{\prime}|^{2}.$ These energy bounds give

E_{\times}(\mathcal{A}^{\prime},\mathcal{B}^{\prime})\leq\sqrt{E_{\times}(\mathcal{A}^{\prime})E_{\times}(\mathcal{B}^{\prime})}\ll|\mathcal{A}^{\prime}||\mathcal{B}^{\prime}|,

where the first inequality is due to (2) of Lemma 2.1. By (1) of Lemma 2.1 we conclude that

|\mathcal{A}\cdot\mathcal{B}|\geq|\mathcal{A}^{\prime}\cdot\mathcal{B}^{\prime}|\geq\frac{|\mathcal{A}^{\prime}|^{2}|\mathcal{B}^{\prime}|^{2}}{E_{\times}(\mathcal{A}^{\prime},\mathcal{B}^{\prime})}\geq\frac{|\mathcal{A}||\mathcal{B}|}{(\log|\mathcal{A}|)^{\theta+o(1)}(\log|\mathcal{B}|)^{\theta+o(1)}}.

We thereby prove Theorem 1.2. Taking $\mathcal{B}=\mathcal{A}$ in Theorem 1.2 gives Theorem 1.1. ∎

Proof of Theorems 1.4 and 1.5 assuming Theorem 1.9.

By applying Theorem 1.9 to $\mathcal{A}$ and $\mathcal{B}$ , we get subsets $\mathcal{A}^{\prime}\subseteq\mathcal{A}$ and $\mathcal{B}^{\prime}\subseteq\mathcal{B}$ with sizes $|\mathcal{A}^{\prime}|\gg_{\delta}|\mathcal{A}|,|\mathcal{B}^{\prime}|\gg_{\delta}|\mathcal{B}|,$ and energy bounds

E_{\times}(\mathcal{A}^{\prime})\ll_{\delta}|\mathcal{A}|^{2}(\log|\mathcal{A}|)^{2\log 2-1+o(1)},\quad E_{\times}(\mathcal{B}^{\prime})\ll_{\delta}|\mathcal{B}|^{2}(\log|\mathcal{B}|)^{2\log 2-1+o(1)}.

By applying (2) of Lemma 2.1 we get

E_{\times}(\mathcal{A},\mathcal{B})\ll_{\delta}|\mathcal{A}||\mathcal{B}|(\log|\mathcal{A}|)^{\log 2-\frac{1}{2}+o(1)}(\log|\mathcal{B}|)^{\log 2-\frac{1}{2}+o(1)}.

Now Theorem 1.5 follows by (1) of Lemma 2.1. Taking $\mathcal{B}=\mathcal{A}$ in Theorem 1.5 gives Theorem 1.4. ∎

3 Proof of Theorem 1.9: reduction to the essential case

In this section, we want to reduce Theorem 1.9 to the following case, which is proved in the Section 4.

Theorem 3.1.

Let $\delta\in(0,1]$ . Let $\mathcal{P}=\{a+id:0\leq i<L\}$ be an arithmetic progression with common difference $d$ and length $L$ , with $L,d>0$ , $L\log L>a\geq dL$ , and $\operatorname{gcd}(a,d)=1$ . If $\mathcal{A}\subseteq\mathcal{P}$ is a subset of size at least $\delta L$ containing only square-free elements and $L$ is sufficiently large with respect to $\delta$ , then there exists a subset $\mathcal{A}^{\prime}\subseteq\mathcal{A}$ with $|\mathcal{A}^{\prime}|\gg|\mathcal{A}|$ such that

E_{\times}(\mathcal{A}^{\prime})\ll L^{2}(\log L)^{2\log 2-1+o(1)}.

(3.1)

We start by giving an upper bound on the multiplicative energy in some special cases. When $\operatorname{gcd}(a,d)=1$ , we have the following observation on the multiplicative energy.

Lemma 3.2.

Let $\mathcal{P}=\{a+id:0\leq i<L\}$ be an arithmetic progression with $\operatorname{gcd}(a,d)=1$ and $a>0,d>0$ . For any $\mathcal{A}\subseteq\mathcal{P}$ , we have $E_{\times}(\mathcal{A})\leq 2|\mathcal{A}|^{2}+4\frac{L^{3}}{a}(1+\log L).$

Proof.

The number of solutions $(a_{1},a_{2};a_{3},a_{4})\in\mathcal{A}^{4}$ to $a_{1}a_{2}=a_{3}a_{4}$ with $\{a_{1},a_{2}\}=\{a_{3},a_{4}\}$ is at most $2|\mathcal{A}|^{2}$ . We next estimate the number of off diagonal solutions.

We begin by parameterizing solutions $(a_{1},a_{2};a_{3},a_{4})$ . Write $x_{1}=\operatorname{gcd}(a_{1},a_{3})$ and $a_{1}=x_{1}y_{1}$ , $a_{3}=x_{1}y_{2}$ . As a result, $a_{2}/y_{2}=a_{4}/y_{1}$ , which we denote as $x_{2}$ . Therefore we derive a tuple $(x_{1},x_{2};y_{1},y_{2})$ such that $x_{i}y_{j}\in\mathcal{A}$ for all $i,j\in\{1,2\}$ . As $\{a_{1},a_{2}\}\neq\{a_{3},a_{4}\}$ , one has $x_{1}\neq x_{2}$ and $y_{1}\neq y_{2}$ . By symmetry we may assume that $x_{1}<x_{2}$ and $y_{1}<y_{2}$ and thereby decrease the number of such tuples by a factor of $4$ , i.e. $E_{\times}(\mathcal{A})-2|\mathcal{A}|^{2}$ is at most $4|X|$ where

X:=\{(x_{1},x_{2};y_{1},y_{2}):x_{i}y_{j}\in\mathcal{A}\;\leavevmode\nobreak\ \leavevmode\nobreak\ \forall\;i,j\in\{1,2\},0<x_{1}<x_{2},0<y_{1}<y_{2}\}.

Fix a choice of $x_{1}$ . Since elements in $\mathcal{A}$ are included in the interval $[a,a+dL)$ , one has that $\frac{x_{2}}{x_{1}}=\frac{x_{2}y_{1}}{x_{1}y_{1}}<1+\frac{dL}{a}$ . Together with $x_{2}>x_{1}$ , it implies $x_{2}\in(x_{1},x_{1}+x_{1}dL/a)$ . Since all elements in $\mathcal{A}$ are coprime to $d$ , $x_{i}$ and $y_{j}$ are also coprime to $d$ . As a result, $x_{1}y_{1}\equiv a\equiv x_{2}y_{1}\pmod{d}$ implies that $x_{1}$ and $x_{2}$ are both congruent to $ay_{1}^{-1}$ mod $d$ , and thus the number of choices for $x_{2}$ is at most $\lfloor\frac{x_{1}L}{a}\rfloor$ .

Similarly, $y_{i}\in[\frac{a}{x_{1}},\frac{a}{x_{1}}+\frac{dL}{x_{1}})$ as $x_{1}y_{i}\in[a,a+dL)$ . By the fact $y_{1}<y_{2}$ and $y_{1}\equiv y_{2}\mod d$ , there is no valid choice for $(y_{1},y_{2})$ if $\frac{L}{x_{1}}\leq 1$ . If $\frac{L}{x_{1}}>1$ , then the number of choices for $(y_{1},y_{2})$ is at most

\frac{1}{2}\left\lceil\frac{L}{x_{1}}\right\rceil\cdot\left(\left\lceil\frac{L}{x_{1}}\right\rceil-1\right)\leq\frac{L^{2}}{x_{1}^{2}}.

In summary, any such valid tuple satisfies $\frac{a}{L}\leq x_{1}<L$ . Once $x_{1}$ is fixed, the number of such tuples is at most $\frac{L^{3}}{ax_{1}}$ . By summing over all choices of $x_{1}$ , we conclude that

E_{\times}(\mathcal{A})\leq 2|\mathcal{A}|^{2}+4\sum_{x_{1}<L}\frac{L^{3}}{ax_{1}}\leq 2|\mathcal{A}|^{2}+\frac{4L^{3}}{a}(1+\log L).

∎

The above lemma gives the following corollary immediately.

Corollary 3.3.

Let $\mathcal{P}=\{a+id:0\leq i<L\}$ be an arithmetic progression with $\operatorname{gcd}(a,d)=1$ and $a>0,d>0$ . Suppose $\mathcal{A}\subseteq\mathcal{P}$ . If $a=\Omega(L\log L)$ , then $E_{\times}(\mathcal{A})=O(L^{2})$ .

Our next step is to reduce the problem to the case that the elements are all square free.

Lemma 3.4 (Square-free reduction).

Let $\mathcal{P}=\{a+id:0\leq i<L\}$ be an arithmetic progression with $\operatorname{gcd}(a,d)=1$ and $a,d>0$ . Suppose $a+dL<\frac{\delta^{2}}{9}L^{2}$ and $d\leq L$ . If $\mathcal{A}$ is an arithmetic progression with density $\delta$ , then we can find a subset $\mathcal{B}_{0}\subseteq\mathcal{A}$ such that $|\mathcal{B}_{0}|\gg_{\delta}|\mathcal{A}|$ , and all elements in $\mathcal{B}_{0}$ have the same largest square factor. In particular, after dividing all elements in $\mathcal{B}_{0}$ by their common largest square factor, the resulting set, denoted by $\mathcal{B}$ , contains only square-free elements.

To prove this, we use the Pigeonhole Principle. We first show that most elements in $\mathcal{P}$ with relatively small $a$ and $d$ are not divisible by large perfect squares.

Lemma 3.5.

Let $\mathcal{P}=\{a+id:0\leq i<L\}$ be an arithmetic progression with $\operatorname{gcd}(a,d)=1$ and $a,d>0$ . Let $T>0$ be a positive integer. The number of elements in $\mathcal{P}$ divisible by a square greater than $T^{2}$ is at most $\sqrt{a+dL}+\frac{L}{T}$ .

Proof.

Let $n=\lfloor\sqrt{a+dL}\rfloor$ . Clearly if an element in $\mathcal{P}$ is divisible by $t^{2}$ , then $t\leq n$ (or otherwise $t^{2}$ is larger than any element in $\mathcal{P}$ ). We claim that for each $t$ , the number of elements in $\mathcal{P}$ divisible by $t^{2}$ is at most $\lceil\frac{L}{t^{2}}\rceil$ . Since $\operatorname{gcd}(a,d)=1$ , if $t^{2}$ divides $a+i_{1}d$ and $a+i_{2}d$ , then $\operatorname{gcd}(t,d)=1$ . This implies that $t^{2}|(i_{1}-i_{2})$ , so $t^{2}$ divides at most one element in every $t^{2}$ consecutive elements in $\mathcal{P}$ . We conclude that the number of elements in $\mathcal{P}$ divisible by a square greater than $T^{2}$ is at most

\sum_{t=T+1}^{n}\left\lceil\frac{L}{t^{2}}\right\rceil\leq\sum_{t=T+1}^{n}\left(1+\frac{L}{t^{2}}\right)\leq n+L\sum_{t=T+1}^{n}\frac{1}{t^{2}}\leq n+\frac{L}{T}.

We conclude with the desired bound by noting that $n\leq\sqrt{a+dL}$ . ∎

Proof of Lemma 3.4.

As $a+dL<\frac{\delta^{2}}{9}L^{2}$ , by taking $T=\lceil\frac{3}{\delta}\rceil$ in Lemma 3.5, there are at least $\frac{\delta}{3}L$ elements left in $\mathcal{A}$ that are not divisible by squares greater than $T^{2}$ . By the Pigeonhole Principle, there exists some $1\leq t\leq T$ such that there are at least $\frac{\delta L}{3T}\geq\frac{\delta^{2}}{18}L$ elements in $\mathcal{A}$ that are divisible by $t^{2}$ and are square-free after divided by $t^{2}$ . We shall let $\mathcal{B}_{0}$ be the set of such elements. ∎

Proof of Theorem 1.9 assuming Theorem 3.1.

First, we may assume that $L\geq|\mathcal{A}|$ is sufficiently large with respect to $\delta$ , or otherwise we may choose $\mathcal{A}^{\prime}=\mathcal{A}$ and we have $E_{\times}(\mathcal{A})\ll|\mathcal{A}|^{4}\ll_{\delta}1$ .

We finish proof by combining all results from above. Our setup is the following. Let $\mathcal{P}=\{a+id:0\leq i<L\}$ be an arithmetic progression with common difference $d$ and length $L$ . Let $\mathcal{A}\subseteq\mathcal{P}$ with density $\frac{|\mathcal{A}|}{|\mathcal{P}|}\geq\delta$ for some constant $\delta\in(0,1)$ . We begin by noticing the following simple observation.

Observation

Let $\phi$ be a non-trivial dilation operation (multiply by a nonzero constant) on the set $\mathcal{P}$ , then the operation $\phi$ preserves the multiplicative energy of any subset of $\mathcal{P}$ . If Theorem 1.9 holds for $(\mathcal{A}_{0},\mathcal{P}_{0})$ where $\phi(\mathcal{A}_{0})\subseteq\mathcal{A}$ and arithmetic progression $\phi(\mathcal{P}_{0})\subseteq\mathcal{P}$ with $|\mathcal{A}_{0}|\gg_{\delta}|\mathcal{A}|$ , then the conclusion must also hold for $(\mathcal{A},\mathcal{P})$ .

Based on the above observation, we do a set of reduction steps to reduce to $(\mathcal{A}^{\prime},\mathcal{P}^{\prime})$ . At the same time, we trace the change of density from $\delta$ to $\delta^{\prime}$ in each step and $L^{\prime}$ to $L$ in each step.

Step 1: Assume all elements are positive. Without loss of generality, we may assume that at least $\frac{1}{3}$ of the elements in $\mathcal{A}$ are positive, or we shall replace $\mathcal{A}$ by $-\mathcal{A}$ . Let $\mathcal{A}_{+}=\mathcal{A}\cap\mathbb{Z}_{>0}$ be the set of positive elements. Then it is sufficient to prove the statement for $\mathcal{A}_{+}$ , i.e., one can find a subset of $\mathcal{A}_{+}$ with small multiplicative energy $\ll L^{2}(\log L)^{1-2\log 2+o(1)}$ .

In this step, we set $\mathcal{A}_{1}=\mathcal{A}_{+}$ . It is clear that by doing this, the density $\delta_{1}>\delta/3$ . We also make the enclosing arithmetic progression contain only positive elements. This does not decrease the density $\delta_{1}$ , while the length of the enclosing arithmetic progression becomes $L_{1}:=|\mathcal{P}\cap\mathbb{Z}_{>0}|\geq|\mathcal{A}_{1}|=\Omega(\delta L)$ . In summary, we can find an arithmetic progression $\mathcal{P}_{1}=\{a_{1}+id_{1}:0\leq i<L_{1}\}$ and a subset $\mathcal{A}_{1}\subseteq\mathcal{P}_{1}$ such that $E_{\times}(\mathcal{A})\geq E_{\times}(\mathcal{A}_{1})$ , $a_{1},d_{1}>0$ , and $L_{1}=\Omega(\delta L)$ , $\delta_{1}=\frac{|\mathcal{A}_{1}|}{|\mathcal{P}_{1}|}\geq\delta/3$ .

Step 2: Divide all elements by GCD. We may divide all elements in $\mathcal{A}_{1}$ by $\operatorname{gcd}(a_{1},d_{1})$ , giving set $A_{2}$ . The density and the length do not change $\delta_{2}=\delta_{1}>\delta/3$ and $L_{2}=L_{1}=\Omega(\delta L)$ . The new common difference is $d_{2}=\frac{d_{1}}{\operatorname{gcd}(a_{1},d_{1})}$ and the initial term becomes $a_{2}=\frac{a_{1}}{\operatorname{gcd}(a_{1},d_{1})}$ . Moreover this map $(\times\operatorname{gcd}(a_{1},d_{1}))$ from subsets of $\mathcal{A}_{2}$ to subsets of $\mathcal{A}_{1}$ preserves multiplicative energy.

Step 3: Assume all elements lie in dyadic interval \texorpdfstring $[x,2x)$ [x, 2x). Let $I_{t}:=\{a_{2}+id_{2}:L_{2}/2^{t+1}\leq i<L_{2}/2^{t}\}$ for $t\geq 0$ and consider the dyadic partition (ignore the single element $\{a\}$ )

\{a_{2}+id_{2}:0<i<L_{2}\}=\bigcup_{t\geq 0}I_{t}.

We may set $t_{0}=O(1+\log\frac{1}{\delta_{2}})$ such that $\sum_{t\geq t_{0}}|I_{t}|\leq\delta_{2}(L_{2}-1)/2$ . It implies that

\left|\mathcal{A}_{2}\cap\bigcup_{t<t_{0}}I_{t}\right|\geq\delta_{2}(L_{2}-1)/2.

This means that $\mathcal{A}_{2}$ contains at least $\delta_{2}/2$ fraction of elements in $\bigcup_{t<t_{0}}I_{t}$ . In particular there exists some $0\leq t_{1}<t_{0}$ such that

|\mathcal{A}\cap I_{t_{1}}|\geq\frac{\delta_{2}}{2}|I_{t_{1}}|.

Note that $I_{t_{1}}=\{a_{2}+id_{2}:L_{2}/2^{t_{1}+1}\leq i<L_{2}/2^{t_{1}}\}$ can be written as an arithmetic progression $\mathcal{P}_{3}=\{a_{3}+id_{3}:0\leq i<L_{3}\}$ with $a_{3}\geq a_{2}+d_{2}L_{2}/2^{t_{1}+1}$ , $d_{3}=d_{2}$ , and $L_{3}\leq L_{2}/2^{t_{1}+1}$ . We conclude that we can find sets $\mathcal{A}_{3},\mathcal{P}_{3}$ such that $\mathcal{P}_{3}=\{a_{3}+id_{3}:0\leq i<L_{3}\}$ with $a_{3}>d_{3}L_{3}$ , $L_{3}=\Omega(L_{2}/2^{t_{0}})=\delta_{2}^{O(1)}L_{2}$ and $\mathcal{A}_{3}=\mathcal{A}_{2}\cap\mathcal{P}_{3}$ with $|\mathcal{A}_{3}|\geq\frac{\delta_{2}}{2}L_{3}=:\delta_{3}L_{3}$ . Thus, by the observation made at beginning, it suffices to study $(\mathcal{A}_{3},\mathcal{P}_{3})$ .

Step 4: Eliminate extremal cases. After step $3$ , we may assume that $d_{3}L_{3}<a_{3}$ . Applying Lemma 3.2, we may assume that $d_{3}L_{3}<a_{3}<L_{3}\log L_{3}$ , otherwise we directly have $E_{\times}(\mathcal{A}_{3})\ll_{\delta}|\mathcal{A}_{3}|^{2}$ .

Step 5: Assume all elements are square-free. After reduction in step 2, the condition in Lemma 3.4 is satisfied and by applying Lemma 3.4 we get a set $\mathcal{A}_{5}$ with size at least $\frac{\delta_{3}^{2}}{18}L_{3}$ containing only square-free elements. Moreover, there is some constant $T=O(1/\delta)$ such that $T^{2}\mathcal{A}_{5}\subseteq\mathcal{A}_{3}$ and $\operatorname{gcd}(T,d_{3})=1$ . Clearly $\mathcal{A}_{5}$ is also contained in an arithmetic progression of length $L_{5}=\Theta(L_{3}/T^{2})=\Omega(\delta^{2}L_{3})$ . Also note that $L_{5}\leq L_{3}$ , so we have $\delta_{5}\geq\frac{\delta_{3}^{2}}{18}$ . By applying the observation made at the beginning again, it is valid to make the deduction.

Summary. Combing the five reduction steps above, we conclude that either we find a subset $\mathcal{A}^{\prime}\subseteq\mathcal{A}$ with $|\mathcal{A}^{\prime}|\gg_{\delta}|\mathcal{A}|$ and $E_{\times}(\mathcal{A}^{\prime})\ll_{\delta}|\mathcal{A}|^{2}$ (which is more than what we need), or we get a set $\mathcal{B}=\mathcal{A}_{5}$ containing only square-free integers, with density $\delta_{5}=\Omega(\delta^{2})$ in an arithmetic progression $\mathcal{P}^{\prime}=\{a^{\prime}+id^{\prime}:0\leq i<L^{\prime}\}$ satisfying that $L^{\prime}\log L^{\prime}>a^{\prime}>d^{\prime}L^{\prime}>0$ where $L^{\prime}=L_{5}=\Omega(\delta^{O(1)}L)$ . Applying Theorem 3.1 on $\mathcal{B}$ , there exists a subset $\mathcal{B}^{\prime}\subseteq\mathcal{B}$ with size $|\mathcal{B}^{\prime}|\gg|\mathcal{B}|$ such that

E_{\times}(\mathcal{B}^{\prime})\ll|\mathcal{B}|^{2}(\log|\mathcal{B}|)^{2\log 2-1+o(1)}.

Moreover, it is guaranteed that there is a nonzero integer $m$ such that $m\mathcal{B}:=\{m\}\cdot\mathcal{B}\subseteq\mathcal{A}$ . Then $\mathcal{A}^{\prime}=m\mathcal{B}^{\prime}$ is a subset of $\mathcal{A}$ of size at least $\delta_{5}L^{\prime}\gg_{\delta}|\mathcal{A}|$ , and

E_{\times}(\mathcal{A}^{\prime})=E_{\times}(\mathcal{B}^{\prime})\ll|\mathcal{B}|^{2}(\log|\mathcal{B}|)^{2\log 2-1+o(1)}\ll_{\delta}|\mathcal{A}|^{2}(\log|\mathcal{A}|)^{2\log 2-1+o(1)},

as desired.∎

4 Proof of Theorem 3.1: the essential case

In this section we prove Theorem 3.1. Let us restate the theorem for convenience. See 3.1

In fact we prove the following more explicit and stronger statement.

Theorem 4.1.

For any $\delta,\epsilon\in(0,1]$ , there exists $L_{0}=L_{0}(\delta,\epsilon)$ such that the following holds. Let $\mathcal{P}=\{a+id:i\in 0\leq i<L\}$ be an arithmetic progression with common difference $d$ and length $L$ , with $L>L_{0},d>0$ , $L\log L>a\geq dL$ , and $\operatorname{gcd}(a,d)=1$ . If $\mathcal{A}\subseteq\mathcal{P}$ is a subset of size at least $\delta L$ containing only square-free elements, then there exists a subset $\mathcal{A}^{\prime}\subseteq\mathcal{A}$ with $|\mathcal{A}^{\prime}|\geq|\mathcal{A}|/2$ such that

E_{\times}(\mathcal{A}^{\prime})\ll L^{2}\left(1+\frac{L}{a}(\log L)^{2\log 2-1+\epsilon}\right).

(4.1)

As $a\geq dL\geq L$ , (4.1) implies (3.1). Thus, Theorem 3.1 follows from Theorem 4.1. To prove Theorem 4.1, we need the following result of Shiu [27].

Theorem 4.2 (Theorem 1 in [27]).

Let $f(n)$ be a non-negative multiplicative function such that $f(p^{\ell})\leq A_{1}^{\ell}$ for some positive constant $A_{1}$ and for any $\varepsilon>0$ , $f(n)\leq A_{2}n^{\varepsilon}$ for some $A_{2}=A_{2}(\varepsilon)$ . Let $\alpha,\beta\in(0,1/2]$ , integer $a$ satisfying $\operatorname{gcd}(a,k)=1$ . Then as $x\to\infty$ we have

\sum_{\begin{subarray}{c}x-y\leq n<x\\ n\equiv a\;(\mathrm{mod}\;k)\end{subarray}}f(n)\ll\frac{y}{\phi(k)}\frac{1}{\log x}\exp\left(\sum_{p\leq x,p\nmid k}\frac{f(p)}{p}\right),

provided that $k<y^{1-\alpha}$ and $x^{\beta}<y<x$ , where the implicit constant depends only on $A_{1},A_{2},\alpha,\beta$ and the summation on the right hand side is taken over prime $p$ .

Let $\omega(n)$ be the number of distinct prime factors of $n$ . Consider the family of nonnegative multiplicative functions $M=\{z^{\omega(n)}:z\in(0,2]\}$ . Note that Theorem 4.2 is applicable to any $f\in M$ with a universal choice of $A_{1}$ and $A_{2}$ , by observing that $f(p^{\ell})\leq 2$ , and $f(n)\leq 2^{\omega(n)}=n^{O(1/\log\log n)}$ . To evaluate the summation inside the exp on the right hand side, we need the following estimate.

Theorem 4.3 (Merten’s estimate, e.g. see [32, Theorem 1.10]).

For $x\geq 2$ , $\sum_{p\leq x}\frac{1}{p}=\log\log x+O(1).$

Using these, we estimate the number of elements in $\mathcal{P}$ with a large number of distinct prime factors.

Lemma 4.4.

Let $\mathcal{P}=\{a+id:0\leq i<L\}$ be an arithmetic progression satisfying $L^{2}>a+dL>a>0$ and $\operatorname{gcd}(a,d)=1$ . As $a+dL\to\infty$ , if $t>0$ satisfies $t=o(\log\log(a+dL))$ , then

|\{n\in\mathcal{P}:\omega(n)\geq\log\log(a+dL)+t\}|\ll\frac{dL}{\phi(d)}\exp\left(-\left(\frac{1}{2}+o(1)\right)\frac{t^{2}}{\log\log(a+dL)}\right).

Proof.

Let $\ell=\log\log(a+dL)+t$ and $z=\frac{\ell}{\log\log(a+dL)}=1+o(1)\in(1,2]$ . As $z>1$ , we use bounds $z^{\omega(n)-\ell}\geq 1$ when $\omega(n)\geq\ell$ and $z^{\omega(n)-\ell}>0$ otherwise, to get that

|\{n\in\mathcal{P}:\omega(n)\geq\ell\}|\leq\sum_{n\in\mathcal{P}}z^{\omega(n)-\ell}=z^{-\ell}\sum_{n\in\mathcal{P}}z^{\omega(n)}.

As $\ell=z\log\log(a+dL)$ , we have $z^{-\ell}=e^{-z\log z\log\log(a+dL)}=(\log(a+dL))^{-z\log z}$ . Note that we can write $\mathcal{P}=\{a\leq n<a+dL:n\equiv a\pmod{d}\}$ . By $L^{2}>a+dL>a>0$ , we may take $x=a+dL$ , $y=dL$ , and $k=d$ , and they satisfy the conditions for Theorem 4.2 with $\alpha=\beta=1/2$ . It implies

z^{-\ell}\sum_{n\in\mathcal{P}}z^{\omega(n)}\ll\frac{dL}{\phi(d)}(\log(a+dL))^{z-1-z\log z}.

The implicit constant here is uniform for all $z\in(1,2]$ . If we write $\lambda:=z-1=o(1)$ , then we have

-1-z\log z+z=-1-(1+\lambda)\log(1+\lambda)+(1+\lambda)=-\frac{\lambda^{2}}{2}+O(\lambda^{3})=-\left(\frac{1}{2}+o(1)\right)\lambda^{2}.

By definition, we have $\lambda=\frac{t}{\log\log(a+dL)}$ , and the desired inequality follows. ∎

Note that $\frac{d}{\phi(d)}=O(\log\log d)=O(\log\log(a+dL))$ . We can choose $t=(\log\log(a+dL))^{2/3}$ , such that $o(L)$ elements have more than $T=\log\log(a+dL)+(\log\log(a+dL))^{2/3}$ distinct prime factors. Therefore we have the following lemma.

Lemma 4.5.

For any $\varepsilon\in(0,1]$ , there exists $a_{0}=a_{0}(\varepsilon)$ such that the following holds. For any $a>a_{0}$ , if $\mathcal{P}=\{a+id:0\leq i<L\}$ is an arithmetic progression with common difference $d$ and length $L$ satisfying $L^{2}>a+dL>a>0$ and $\operatorname{gcd}(a,d)=1$ , then for $T=\log\log(a+dL)+(\log\log(a+dL))^{\frac{2}{3}}$ ,

|\{n\in\mathcal{P}:\omega(n)\leq T\}|\geq(1-\varepsilon)L.

(4.2)

Let $\mathcal{A}^{\prime}$ be the subset of elements of $\mathcal{A}$ with at most $T$ distinct prime factors, i.e.

\mathcal{A}^{\prime}:=\{a\in\mathcal{A}:\omega(n)\leq T=\log\log(a+dL)+(\log\log(a+dL))^{\frac{2}{3}}\}.

(4.3)

By Lemma 4.5, we have $|\mathcal{A}^{\prime}|\geq|\mathcal{A}|/2$ when $a>a_{0}(\delta/2)$ .

Proof of Theorem 4.1.

By choosing a sufficiently large constant in (3.1), we may assume that $a>dL\geq L>|\mathcal{A}|$ is sufficiently large. In particular $d<\frac{a}{L}<\log L<L^{1/3}$ . By Lemma 4.5, we may assume that $a\geq a_{0}(\delta/2)$ . Now at most $\varepsilon L=\frac{\delta}{2}L$ elements in $\mathcal{P}$ have more than $T=\log\log(a+dL)+(\log\log(a+dL))^{\frac{2}{3}}$ distinct prime factors. Similar to the proof of Lemma 3.2, we estimate the size of

X:=\{(x_{1},x_{2};y_{1},y_{2}):x_{i}y_{j}\in\mathcal{A}^{\prime}\;\leavevmode\nobreak\ \leavevmode\nobreak\ \forall\;i,j\in\{1,2\},0<x_{1}<x_{2},0<y_{1}<y_{2},x_{1}\leq y_{1}\}.

By the same argument as in the proof of Lemma 3.2 (here we use an extra symmetry between $x$ and $y$ ), we have that $E_{\times}(\mathcal{A}^{\prime})\leq 2|\mathcal{A}^{\prime}|^{2}+8|X|$ .

Fix $x_{1}$ . As all elements in $\mathcal{A}^{\prime}$ are congruent to $a$ mod $d$ , they are all coprime to $d$ . Therefore $x_{i}$ and $y_{j}$ are also coprime to $d$ . As a result, $a\equiv x_{1}y_{1}\equiv x_{2}y_{1}\equiv x_{1}y_{2}\pmod{d}$ implies that $x_{2}$ is congruent to $x_{1}$ mod $d$ and $y_{1}$ and $y_{2}$ are both congruent to $ax_{1}^{-1}$ mod $d$ . Since all elements in $\mathcal{A}^{\prime}$ are included in the interval $[a,a+dL)$ , one has $\frac{x_{2}}{x_{1}}=\frac{x_{2}y_{1}}{x_{1}y_{1}}<1+\frac{dL}{a}$ . Since $x_{2}>x_{1}$ , we know that $x_{2}\in(x_{1},x_{1}+x_{1}dL/a)$ . As $x_{2}\equiv x_{1}\pmod{d}$ , the number of choices for $x_{2}$ is at most $\lfloor\frac{x_{1}L}{a}\rfloor$ . In particular, if $\frac{x_{1}L}{a}<1$ then there is no valid tuple in $X$ .

Similarly, as $x_{1}y_{i}\in[a,a+dL)$ , we know that $y_{i}\in[\frac{a}{x_{1}},\frac{a}{x_{1}}+\frac{dL}{x_{1}})$ . As $y_{1}<y_{2}$ and they are congruent mod $d$ , we know that there is no valid choice for $(y_{1},y_{2})$ if $\frac{L}{x_{1}}<1$ . Otherwise if $\frac{L}{x_{1}}\geq 1$ , then the number of choices is at most

\frac{1}{2}\left\lceil\frac{L}{x_{1}}\right\rceil\cdot\left(\left\lceil\frac{L}{x_{1}}\right\rceil-1\right)\leq\frac{L^{2}}{x_{1}^{2}}.

Therefore, for each $x_{1}$ , the number of choices for $(x_{2};y_{1},y_{2})$ is at most $\frac{L^{3}}{ax_{1}}$ .

Let $X_{1}$ be the set of such tuples with $x_{1}\leq\frac{ea^{2}}{L^{2}}$ . We first estimate $|X_{1}|$ . As we sum $\frac{L^{3}}{ax_{1}}$ over $1\leq x_{1}\leq\frac{ea^{2}}{L^{2}}$ , we conclude that $|X_{1}|\leq\frac{L^{3}}{a}\left(\log\frac{ea^{2}}{L^{2}}+1\right)\leq L^{2}\left(2\frac{L}{a}+2\frac{L}{a}\log\frac{a}{L}\right)\leq 4L^{2}.$

It remains to estimate the size of $X_{2}=X\setminus X_{1}$ . It consists of tuples with $x_{1}>\frac{ea^{2}}{L^{2}}$ . Note that $x_{1}^{2}\leq x_{1}y_{1}<a+dL$ , we know that $\frac{ea^{2}}{L^{2}}<x_{1}<\sqrt{a+dL}$ . For each fixed $x_{1}=x\in(\frac{ea^{2}}{L^{2}},\sqrt{a+dL})$ , we consider tuples $(x_{1},x_{2};y_{1},y_{2})\in X_{2}$ . As argued above, we know that $x_{2}$ is an element in $(x_{1},x_{1}dL/a)$ with $x_{2}\equiv x_{1}\pmod{d}$ , and $y_{1},y_{2}$ are elements in $[\frac{a}{x_{1}},\frac{a}{x_{1}}+\frac{dL}{x_{1}})$ with $y_{1}\equiv y_{2}\equiv ax_{1}^{-1}\pmod{d}$ .

Next we use the fact that all elements in $\mathcal{A}^{\prime}$ having at most $T$ distinct prime factors and are square-free, which implies that $\omega(x_{i})+\omega(y_{j})=\omega(x_{i}y_{j})\leq T$ for $i,j\in\{1,2\}$ . Therefore for each $(x_{1},x_{2};y_{1},y_{2})\in X_{2}$ , we have

\left(\frac{1}{\sqrt{2}}\right)^{\omega(x_{1}y_{1})+\omega(x_{1}y_{2})+\omega(x_{2}y_{1})+\omega(x_{2}y_{2})-4T}\geq 1.

Using the above bound and that $\omega(x_{i}y_{j})=\omega(x_{i})+\omega(y_{j})$ since $x_{i}y_{j}\in\mathcal{A}^{\prime}$ is square-free, we have

\begin{split}|X_{2}|&\leq\sum_{(x_{1},x_{2};y_{1},y_{2})\in X_{2}}2^{-\omega(x_{1})-\omega(x_{2})-\omega(y_{1})-\omega(y_{2})+2T}\\ &\leq 2^{2T}\sum_{\frac{ea^{2}}{L^{2}}<x_{1}<\sqrt{a+dL}}2^{-\omega(x_{1})}\sum_{\begin{subarray}{c}x_{1}<x_{2}<x_{1}\frac{a+dL}{a}\\ x_{2}\equiv x_{1}\;(\mathrm{mod}\;d)\end{subarray}}2^{-\omega(x_{2})}\left(\sum_{\begin{subarray}{c}\frac{a}{x_{1}}\leq y<\frac{a+dL}{x_{1}}\\ y\equiv ax_{1}^{-1}\;(\mathrm{mod}\;d)\end{subarray}}2^{-\omega(y)}\right)^{2}.\end{split}

(4.4)

We now apply Theorem 4.2 to two factors on the right hand side of (4.4). Note that for $x^{\prime}=x_{1}\frac{a+dL}{a}$ and $y^{\prime}=x_{1}dL/a$ , we have $y^{\prime}>\frac{ea^{2}}{L^{2}}\frac{dL}{a}=\frac{ea}{L}d\geq ed^{2}>d^{2}$ (where we use the assumption that $a\geq dL$ ) and $x^{\prime}>y^{\prime}$ . Finally we have $(y^{\prime})^{2}=x_{1}^{2}d^{2}L^{2}/a^{2}>ex_{1}d^{2}\geq ex_{1}>x^{\prime}$ . Therefore parameters $(x,y,d,f)=(x^{\prime},y^{\prime},k,2^{-\omega(\cdot)})$ satisfy the conditions of Theorem 4.2 with $\alpha=\beta=1/2$ and $A_{1}=A_{2}=1$ . By Theorem 4.3, we have $\sum_{p\leq x^{\prime},p\nmid d}f(p)/p\leq\frac{\log\log x^{\prime}+C}{2}$ for $f(x)=2^{-\omega(x)}$ , and further

\sum_{\begin{subarray}{c}x_{1}<x_{2}<x_{1}\frac{a+dL}{a}\\ x_{2}\equiv x_{1}\;(\mathrm{mod}\;d)\end{subarray}}2^{-\omega(x_{2})}\ll\frac{x_{1}\frac{dL}{a}}{\phi(d)}\left(\log\frac{x_{1}(a+dL)}{a}\right)^{-\frac{1}{2}}\leq\frac{x_{1}dL}{a\phi(d)}(\log x_{1})^{-\frac{1}{2}}.

(4.5)

Similarly as $x_{1}<\sqrt{a+dL}\leq\sqrt{2L\log L}<L^{\frac{2}{3}}$ for $L$ sufficiently large, one can verify that for $(x^{\prime},y^{\prime})=(\frac{a+dL}{x_{1}},\frac{dL}{x_{1}})$ , we have $(y^{\prime})^{2}=d^{2}\frac{L^{2}}{x_{1}^{2}}>d^{2}L^{\frac{2}{3}}>d^{4}$ , $x^{\prime}>y^{\prime}$ , and $\frac{(y^{\prime})^{2}}{x^{\prime}}=\frac{d^{2}L^{2}}{x_{1}(a+dL)}>\frac{d^{2}L^{2}}{(a+dL)^{3/2}}>1$ . Hence by Theorem 4.2 with the same $(\alpha,\beta,A_{1},A_{2})$ and by the same estimate due to Theorem 4.3, we have

\sum_{\begin{subarray}{c}\frac{a}{x_{1}}\leq y<\frac{a+dL}{x_{1}}\\ y\equiv ax_{1}^{-1}\;(\mathrm{mod}\;d)\end{subarray}}2^{-\omega(y)}\ll\frac{\frac{dL}{x_{1}}}{\phi(d)}\left(\log\frac{a+dL}{x_{1}}\right)^{-\frac{1}{2}}\leq\sqrt{2}\frac{dL}{x_{1}\phi(d)}(\log(a+dL))^{-\frac{1}{2}}.

(4.6)

Here in the second inequality we use $\frac{a+dL}{x_{1}}\geq\sqrt{a+dL}$ . Put (4.5) and (4.6) back to (4.4). We get

\begin{split}|X_{2}|&\ll 2^{2T}\sum_{\frac{ea^{2}}{L^{2}}<x_{1}<\sqrt{a+dL}}2^{-\omega(x_{1})}\cdot\frac{d^{3}L^{3}}{x_{1}a\phi(d)^{3}}(\log x_{1})^{-\frac{1}{2}}(\log(a+dL))^{-1}\\ &=\frac{d^{3}L^{3}}{a\phi(d)^{3}}2^{2T}(\log(a+dL))^{-1}\sum_{\frac{ea^{2}}{L^{2}}<x_{1}<\sqrt{a+dL}}2^{-\omega(x_{1})}\frac{(\log x_{1})^{-\frac{1}{2}}}{x_{1}}.\end{split}

(4.7)

Here the implicit constant is absolute. To estimate the second line of (4.7), we partition the interval dyadically over $x_{1}\in(e^{k},e^{k+1})$ for $1\leq\lfloor\log\frac{ea^{2}}{L^{2}}\rfloor\leq k\leq\lfloor\log\sqrt{a+dL}\rfloor$ . In each interval we have

\sum_{e^{k}<x_{1}<e^{k+1}}2^{-\omega(x_{1})}\frac{(\log x_{1})^{-\frac{1}{2}}}{x_{1}}\leq\sum_{e^{k}<x_{1}<e^{k+1}}2^{-\omega(x_{1})}\frac{k^{-\frac{1}{2}}}{e^{k}}\ll e^{k}(k+1)^{-\frac{1}{2}}\frac{k^{-\frac{1}{2}}}{e^{k}}\ll k^{-1},

where in the second inequality we use Theorem 4.2 with $(x,y,d,a)=(e^{k+1},e^{k+1}-e^{k},1,1)$ and parameters $\alpha=\beta=1/2$ and $A_{1}=A_{2}=1$ . Summing over all values of $k$ , we have for large enough $L$ ,

\sum_{\frac{ea^{2}}{L^{2}}<x_{1}<\sqrt{a+dL}}2^{-\omega(x_{1})}\frac{(\log x_{1})^{-\frac{1}{2}}}{x_{1}}\ll\sum_{k=\lfloor\log\frac{ea^{2}}{L^{2}}\rfloor}^{\lfloor\log\sqrt{a+dL}\rfloor}k^{-1}\leq 2\log\log(a+dL).

(4.8)

Noting that $T=\log\log(a+dL)+(\log\log(a+dL))^{\frac{2}{3}}$ and by choosing $L_{0}$ sufficiently large, we have

2^{2T}=(\log(a+dL))^{(2\log 2)\left(1+(\log\log(a+dL))^{-\frac{1}{3}}\right)}<(\log(a+dL))^{2\log 2+\epsilon/3}.

(4.9)

Put (4.8) and (4.9) back to (4.7). Noting that $\log\log(a+dL)<(\log(a+dL))^{\epsilon/3}$ , $\frac{d}{\phi(d)}=O(\log\log d)\leq(\log(a+dL))^{\epsilon/9}$ , and $a+dL\leq 2L\log L\leq L^{2}$ as $L\geq L_{0}$ is sufficiently large, we conclude that

|X_{2}|\ll\frac{L^{3}}{a}\left(\frac{d}{\phi(d)}\right)^{3}(\log(a+dL))^{2\log 2-1+\epsilon/3}(\log(a+dL))^{\epsilon/3}\ll\frac{L^{3}}{a}(\log L)^{2\log 2-1+\epsilon}.

Here the implicit constant factor is absolute. It follows that

E_{\times}(\mathcal{A}^{\prime})\leq 2|\mathcal{A}^{\prime}|^{2}+8(|X_{1}|+|X_{2}|)\ll L^{2}\left(1+\frac{L}{a}(\log L)^{2\log 2-1+\epsilon}\right).

Recall that $|\mathcal{A}^{\prime}|\geq|\mathcal{A}|/2$ . We have the desired subset $\mathcal{A}^{\prime}$ . ∎

5 Elements with a fixed number of primes factors in arithmetic progressions

In this section, we make some preparations for the proof of Theorem 1.8 in Section 6. Let $\mathcal{A}$ be an arithmetic progression satisfying $0<dL\leq a\leq L\sqrt{\log L}$ . For any positive integer $n$ , we denote the sequence of distinct prime factors of $n$ by $p_{1}(n)<p_{2}(n)<\cdots<p_{\omega(n)}(n)$ . For parameters $\alpha,\beta\in\mathbb{R}$ and $k\in\mathbb{N}$ , we define

\mathcal{N}_{k}(\mathcal{A};\alpha,\beta):=\{n\in\mathcal{A}:n\textrm{ square-free},\;\omega(n)=k,\;\log\log p_{j}(n)\geq\alpha j-\beta\;\leavevmode\nobreak\ \leavevmode\nobreak\ \forall\;1\leq j\leq k\}

(5.1)

and let $N_{k}(\mathcal{A};\alpha,\beta)=|\mathcal{N}_{k}(\mathcal{A};\alpha,\beta)|$ . Our goal is to give a lower bound on $N_{k}(\mathcal{A};\alpha,\beta)$ . This is a natural generalization of [8, 11, 31] where the object studied is the special arithmetic progression $\mathcal{A}=[N]$ . Our proof uses ideas from [8, 31] and in Appendix A we give a stronger estimate following [14].

First we estimate the number of primes in an arithmetic progression using the following theorem of Siegel and Walfisz. For a finite $\mathcal{A}\subseteq\mathbb{N}$ , let $\pi(\mathcal{A})$ be the number of primes in $\mathcal{A}$ .

Theorem 5.1 (Siegel-Walfisz, see Section II.8. in [32]).

Let $\pi(x;q,a)$ be the number of primes up to $x$ with $p\equiv a\pmod{q}$ . Then for any $A>0$ , uniformly for $(a,q)=1$ and $1\leq q\leq(\log x)^{A}$ , we have

\pi(x;q,a)=\frac{x}{\phi(q)\log x}+O\left(\frac{x}{\phi(q)(\log x)^{2}}\right).

(5.2)

Lemma 5.2.

If $\mathcal{A}=\{a+id:0\leq k<L\}$ satisfies that $L$ is sufficiently large, and $0<dL<a<10L\sqrt{\log L}$ and $\operatorname{gcd}(a,d)=1$ , then $\pi(\mathcal{A})\geq\frac{dL}{2\phi(d)\log L}$ .

Proof.

First note that we can write $\pi(\mathcal{A})=\pi(a+dL-1;d,a)-\pi(a-1;d,a)$ . From our assumption we know that $d<10\sqrt{\log L}$ and $a+dL>a>L$ , so we may take $A=1$ in Theorem 5.1 and $L>e^{100}$ such that $1\leq d<\log(a-1)<\log(a+dL-1)$ . Hence we apply (5.2) to have

\pi(\mathcal{A})=\frac{a+dL-1}{\phi(d)\log(a+dL-1)}-\frac{a-1}{\phi(d)\log(a-1)}+O\left(\frac{a-1}{\phi(d)(\log(a-1))^{2}}+\frac{a+dL-1}{\phi(d)(\log(a+dL-1))^{2}}\right).

To estimate the main term, noticing that $a-1\leq a+dL-1\leq 2a-2$ , we have

\frac{a+dL-1}{\phi(d)\log(a+dL-1)}=\frac{a+dL-1}{\phi(d)\log(a-1)}+O\left(\frac{a+dL-1}{\phi(d)(\log(a-1))^{2}}\right).

This shows that

\pi(\mathcal{A})=\frac{dL}{\phi(d)\log(a-1)}+O\left(\frac{a-1}{\phi(q)(\log(a-1))^{2}}+\frac{a+dL-1}{\phi(d)(\log(a+dL-1))^{2}}+\frac{a+dL-1}{\phi(d)(\log(a-1))^{2}}\right).

Clearly $\frac{a+dL-1}{\phi(d)(\log(a-1))^{2}}$ is the largest among the three summands in the error term. As $L\leq dL<a\leq 10L\sqrt{\log L}$ , we can bound the error terms by

\frac{a+dL-1}{\phi(d)(\log(a-1))^{2}}\leq\frac{20dL\sqrt{\log L}}{\phi(d)(\log L)^{2}}=O\left(\frac{dL}{\phi(d)(\log L)^{\frac{3}{2}}}\right).

As $L$ is sufficiently large, we may assume that the error term is at most $\frac{1}{6}\frac{dL}{\phi(d)\log L}$ . Also note that $a-1\leq 10L\sqrt{\log L}\leq L^{\frac{3}{2}}$ when $L$ is sufficiently large. This gives the desired estimate

\pi(\mathcal{A})\geq\frac{2}{3}\frac{dL}{\phi(d)\log L}-\frac{1}{6}\frac{dL}{\phi(d)\log L}=\frac{dL}{2\phi(d)\log L}.

∎

Using this, we can estimate $N_{k}(\mathcal{A};\alpha,\beta)$ with a specific choice of the parameters motivated by [8].

Proposition 5.3.

If $\mathcal{A}=\{a+id:0\leq i<L\}$ is an arithmetic progression satisfying that $L$ is sufficiently large, $0<dL\leq a\leq L\sqrt{\log L}$ , and $\operatorname{gcd}(a,d)=1$ , then for $k=\left\lfloor\frac{\log\log L}{\log 4}-5\sqrt{\log\log L}\right\rfloor-4$ ,

N_{k}(\mathcal{A};\log 4,1)\gg{L}{(\log L)^{-\theta-o(1)}}.

Proof.

To obtain a lower bound, we count elements $n\in\mathcal{N}_{k}(\mathcal{A};\log 4,1)$ with $p_{1}(n)p_{2}(n)\cdots p_{k-1}(n)<\sqrt{a}$ . Once we fixed such a choice of $(p_{1},p_{2},\dots,p_{k-1})$ with $\log\log p_{j}\geq j\log 4-1$ for all $1\leq j\leq k-1$ , we count the number of $p_{k}$ with $p_{k}>p_{k-1}$ and $p_{1}p_{2}\cdots p_{k}\in\mathcal{A}$ . Let $q=p_{1}p_{2}\cdots p_{k-1}$ . Clearly if $qp\in\mathcal{A}$ for some prime $p$ , then $p\geq\frac{a}{q}>\sqrt{a}>q>p_{k-1}$ . Moreover we have

\log\log p>\log\log\sqrt{L}=\log\log L-\log 2>k\log 4-1,

so any such choice of prime $p$ would give a valid choice for $p_{k}$ as defined in (5.1).

For any such fixed choice of $q$ , if $\operatorname{gcd}(q,d)>1$ , then any element in $\mathcal{A}$ is not a multiple of $q$ , so there is no such choice of $p_{k}$ . If $\operatorname{gcd}(q,d)=1$ , then $q|a+id$ is equivalent to $i\equiv-ad^{-1}\pmod{q}$ and there is an unique such $i=i_{0}$ with $0\leq i_{0}<q$ . Then the multiples of $q$ in $\mathcal{A}$ are of the form

\left\{a+(i_{0}+k^{\prime}q)d:0\leq k^{\prime}<\frac{L-i_{0}}{q}\right\}\supseteq\{a+(i_{0}+k^{\prime}q)d:0\leq k^{\prime}<\lfloor L/q\rfloor\},

and the inclusion follows from $\frac{L-i_{0}}{q}>\lfloor L/q\rfloor-1$ . Hence any element $p\in\mathcal{A}_{q}:=\{a^{\prime}+k^{\prime}d:0\leq k^{\prime}<L^{\prime}\}$ with $a^{\prime}=\frac{a+i_{0}d}{q}$ and $L^{\prime}=\lfloor L/q\rfloor$ would satisfy $pq\in\mathcal{A}$ . It is sufficient to estimate the number of primes from $\mathcal{A}_{q}$ , which itself is an arithmetic progression. As $\operatorname{gcd}(a^{\prime},d)\leq\operatorname{gcd}(a+i_{0}d,d)=\operatorname{gcd}(a,d)=1$ , we have $\operatorname{gcd}(a^{\prime},d)=1$ . Moreover, we know that $dL^{\prime}\leq\frac{dL}{q}<\frac{a}{q}\leq a^{\prime}$ and $a^{\prime}<10L^{\prime}\sqrt{\log L^{\prime}}$ when $L$ is sufficiently large. Note that $L^{\prime}\geq\frac{L}{q}-1>\frac{L^{\frac{1}{2}}}{(\log L)^{\frac{1}{4}}}-1$ is also sufficiently large. By invoking Lemma 5.2, the number of choices for $p_{k}$ is at least

\pi(\mathcal{A}_{q})\geq\frac{dL^{\prime}}{2\phi(d)\log L^{\prime}}\geq\frac{dL/q}{4\phi(d)\log L}.

(5.3)

Summing (5.3) up over all possible $(p_{1},\dots,p_{k-1})$ , we have

N_{k}(\mathcal{A};\log 4,1)\geq\frac{dL}{4\phi(d)\log L}\cdot\sum_{\begin{subarray}{c}p_{1}<\cdots<p_{k-1},p_{1}\cdots p_{k-1}<\sqrt{a}\\ p_{j}\nmid d,\log\log p_{j}\geq j\log 4-1\;\forall\;1\leq j\leq k-1\end{subarray}}\frac{1}{p_{1}\cdots p_{k-1}}.

(5.4)

Since $L\leq a\leq L^{2}$ , the condition in Lemma 5.4 is satisfied with our choice of $k$ , and it implies that

\begin{split}N_{k}(\mathcal{A};\log 4,1)&\geq\frac{dL}{4\phi(d)\log L}(e\log 4)^{k-1}(\log\sqrt{a})^{-o(1)}\geq\frac{L}{(\log L)^{\theta+o(1)}},\end{split}

where we use that $\frac{d}{\phi(d)}\geq 1$ , $k=(1+o(1))\frac{\log\log L}{\log 4}$ , and the constant $\frac{1}{4}$ is absorbed in the $o(1)$ term. ∎

Lemma 5.4.

For any $x$ large enough, $k\leq\frac{\log\log x}{\log 4}-5\sqrt{\log\log x}$ , $d=O(\log x)$ , we have

\sum_{\begin{subarray}{c}p_{1}<\cdots<p_{k},p_{1}\cdots p_{k}<x\\ p_{j}\nmid d,\log\log p_{j}\geq j\log 4\;\forall\;1\leq j\leq k\end{subarray}}\frac{1}{p_{1}\cdots p_{k}}\geq(e\log 4)^{k}(\log x)^{-o(1)}.

(5.5)

Proof.

Let $h=\left\lfloor\frac{\sqrt{\log\log x}}{\log 4}\right\rfloor$ , and $J=\lfloor k/h\rfloor=\sqrt{\log\log x}-O(1)$ . For each $j\geq 1$ , we define

I_{j}:=\left[e^{e^{j\sqrt{\log\log x}}},e^{e^{(j+1)\sqrt{\log\log x}}}\right).

By Theorem 4.3, we know that $\sum_{p\in I_{j}}1/p=\sqrt{\log\log x}+O(1)$ . Therefore $\sum_{p\in P_{j}}1/p=\sqrt{\log\log x}-O(\log\log\log x)$ where $P_{j}$ is the set of primes in $I_{j}$ which are not factors of $d$ , and the $O(\log\log\log x)$ term bounds the contribution from those primes which are factors of $d$ . In the summation in (5.5), we consider only the tuples $(p_{1},\dots,p_{k})$ with $h$ primes in $P_{j}$ for each $1\leq j\leq J$ and $(k-Jh)$ primes in $P_{J+1}$ . Noting that $k-Jh\leq h\leq e^{h}\leq e^{\sqrt{\log\log x}}$ , a straightforward computation shows that

p_{1}\cdots p_{k}\leq\exp\left(\sum_{j=1}^{J}he^{(j+1)\sqrt{\log\log x}}+(k-Jh)e^{(J+2)\sqrt{\log\log x}}\right)<e^{e^{(J+4)\sqrt{\log\log x}}}<x

where in the last step we use that $J+4<\sqrt{\log\log x}$ for $x$ large. Hence, any such tuple would satisfy $p_{1}\cdots p_{k}<x$ . Moreover, we know that $\log\log p_{j}\geq\lceil j/h\rceil\sqrt{\log\log x}>j\log 4$ . Therefore any such tuple contributes to a summand on the left hand side of (5.5). Then the left hand side of (5.5) is at least

\prod_{j=1}^{J}\left(\sum_{p_{1}<\cdots<p_{h}\in P_{j}}\frac{1}{p_{1}\cdots p_{h}}\right)\cdot\left(\sum_{p_{1}<\cdots<p_{k-Jh}\in P_{J+1}}\frac{1}{p_{1}\cdots p_{k-Jh}}\right).

(5.6)

Factors in (5.6) are of the same form. We estimate each of them as follows. For $1\leq t\leq h$ and $j\geq 1$ ,

\sum_{p_{1}<\cdots<p_{t}\in P_{j}}\frac{1}{p_{1}\cdots p_{t}}=\frac{1}{t!}\sum_{p_{1}\in P_{j}}\frac{1}{p_{1}}\sum_{\begin{subarray}{c}p_{2}\in P_{j}\\ p_{2}\neq p_{1}\end{subarray}}\frac{1}{p_{2}}\cdots\sum_{\begin{subarray}{c}p_{t}\in P_{j}\\ p_{t}\neq p_{1},\dots,p_{t-1}\end{subarray}}\frac{1}{p_{t}}\geq\frac{1}{t!}\left(\sum_{p\in P_{j}}\frac{1}{p}-\frac{t}{e^{e^{j\sqrt{\log\log x}}}}\right)^{t}.

(5.7)

Note that $t\leq h\leq\sqrt{\log\log x}/\log 4\leq e^{e^{j\sqrt{\log\log x}}}$ , so the term inside the parenthesis on the right hand side of (5.7) is $\sqrt{\log\log x}-O(\log\log\log x)$ . We shall apply Stirling’s formula and obtain that, when $x$ is sufficiently large, the right hand side of (5.7) is at least

\begin{split}\textrm{RHS of }\eqref{eqn:sum-of-re-each}&\geq\left(\frac{\sqrt{\log\log x}-O(\log\log\log x)-1}{t/e}\right)^{t}\cdot(\log\log x)^{-1/4-o(1)}\\ &\geq\left(e\log 4-O\left(\log\log\log x/\sqrt{\log\log x}\right)\right)^{t}\cdot(\log\log x)^{-1/4-o(1)}\\ &\geq(e\log 4)^{t}\cdot(\log\log x)^{-C}\end{split}

for some absolute constant $C>0$ . Applying this bound to (5.7) with $t=h$ and $t=k-Jh$ , we have

\begin{split}\textrm{LHS of }\eqref{eqn:sum-of-reciprocal}\geq\eqref{eqn:sum-of-re-1}&\geq(e\log 4)^{Jh}(\log\log x)^{-CJ}\cdot(e\log 4)^{k-Jt}(\log\log x)^{-C}\\ &=(e\log 4)^{k}\cdot(\log\log x)^{-O(\sqrt{\log\log x})}\end{split}

Thus, noting that the $(\log\log x)^{-O(\sqrt{\log\log x})}=(\log x)^{-o(1)}$ , we finish the proof. ∎

6 Proof of Theorem 1.8

Following the argument in Section 3, we may only focus on the case where our arithmetic progression $\mathcal{A}=\{a+id:0\leq i<L\}$ satisfies $0<dL<a<L\log L$ . Moreover by Theorem 4.1 with $\epsilon=\frac{3}{2}-2\log 2$ , we may further assume that $a<\frac{1}{2}L\sqrt{\log L}$ . In particular, we have the following reduction.

Proposition 6.1.

If $\mathcal{A}=\{a+id:0\leq i<L\}$ is an arithmetic progression with length $L$ and common difference $d$ with $a>0$ , $L$ sufficiently large, and $L\sqrt{\log L}\leq a+dL$ , then there exists a subset $\mathcal{A}^{\prime}\subseteq\mathcal{A}$ satisfying $|\mathcal{A}^{\prime}|\gg|\mathcal{A}|$ and $E_{\times}(\mathcal{A}^{\prime})\ll|\mathcal{A}|^{2}$ .

Therefore we may reduce to the case where $\mathcal{A}=\{a+id:0\leq i<L\}$ with $2dL\leq dL+a\leq L\sqrt{\log L}$ . Inspired by [14], we set $A^{\prime}=\mathcal{N}_{k}(\mathcal{A};\log 4,\beta)$ where parameters are as in Proposition 5.3. This gives the desired lower bound on $|\mathcal{A}^{\prime}|$ . We show that $E_{\times}(\mathcal{N}_{k}(\mathcal{A};\log 4,\beta))$ is small.

Proposition 6.2.

Let $\mathcal{A}=\{a+id:0\leq i<L\}$ be an arithmetic progression with $L\sqrt{\log L}>a>dL>0$ and $\mathcal{A}^{\prime}=\mathcal{N}_{k}(\mathcal{A};\log 4,\beta)$ be defined as in (5.1) with $\beta\in\mathbb{R}$ . Then for some absolute constant $C$ we have

E_{\times}(\mathcal{A}^{\prime})\leq CL^{2}(\log L)^{-2+\frac{1}{\log 2}}\cdot\log\log L\cdot(\log 4)^{2k}2^{2\beta}.

Lemma 6.3.

For any finite $\mathcal{A}\subseteq\mathbb{R}$ , there exists $\mathcal{A}^{\prime}\subseteq\mathcal{A}$ with $|\mathcal{A}^{\prime}|\geq\frac{|\mathcal{A}|^{3}}{2E_{\times}(\mathcal{A})}$ and $E_{\times}(\mathcal{A}^{\prime})\leq 4|\mathcal{A}^{\prime}|^{2}$ .

Proof of Theorem 1.8 assuming Proposition 6.2 and Lemma 6.3.

We may assume that $L$ is sufficiently large and choose $\mathcal{A}^{\prime\prime}=\mathcal{N}_{k}(\mathcal{A};\log 4,1)$ where $k=\left\lfloor\frac{\log\log L}{\log 4}-5\sqrt{\log\log L}\right\rfloor-4=(1+o(1))\frac{\log\log L}{\log 4}$ . By Proposition 5.3, we know that $|\mathcal{A}^{\prime\prime}|\geq{L}{(\log L)^{-\theta-o(1)}}.$ By Proposition 6.2, noting that $(\log 4)^{2k}=(2\log 2)^{(1+o(1))\frac{\log\log L}{\log 2}}=(\log L)^{1+\frac{\log\log 2}{\log 2}+o(1)}$ , we have

E_{\times}(\mathcal{A}^{\prime\prime})\leq L^{2}(\log L)^{-2+\frac{1}{\log 2}+1+\frac{\log\log 2}{\log 2}+o(1)}=L^{2}(\log L)^{-2\theta+o(1)}.

We apply Lemma 6.3 to find $\mathcal{A}^{\prime}\subseteq\mathcal{A}^{\prime\prime}$ of size at least $\frac{|\mathcal{A}^{\prime\prime}|^{3}}{2E_{\times}(\mathcal{A}^{\prime\prime})}\geq L(\log L)^{-\theta-o(1)}$ , as desired. ∎

The proof of Lemma 6.3 uses the probabilistic method. A similar application appears in [14].

Proof of Lemma 6.3.

Fix $p=\frac{|\mathcal{A}|^{2}}{E_{\times}(\mathcal{A})}\in(0,1)$ . We choose a random subset $\mathcal{A}^{\prime}\subseteq\mathcal{A}$ by keeping each element in $\mathcal{A}$ independently with probability $p$ . Then we have $\mathbb{E}|\mathcal{A}^{\prime}|^{2}\geq p^{2}|\mathcal{A}|^{2}$ . Note that for tuples $(a_{1},a_{2};a_{3},a_{4})\in(\mathcal{A}^{\prime})^{4}$ with $a_{1}a_{2}=a_{3}a_{4}$ , there are at most $2|\mathcal{A}^{\prime}|^{2}$ of them with $\{a_{1},a_{2},a_{3},a_{4}\}$ containing at most $2$ elements. For all other ones, they come from a tuple $(a_{1},a_{2};a_{3},a_{4})\in\mathcal{A}^{4}$ with at least $3$ distinct elements, and they are included in $(\mathcal{A}^{\prime})^{4}$ with probability at most $p^{3}$ . Therefore we have

\mathbb{E}E_{\times}(\mathcal{A}^{\prime})\leq\mathbb{E}2|\mathcal{A}^{\prime}|^{2}+p^{3}E_{\times}(\mathcal{A})=2p^{2}|\mathcal{A}|^{2}+p^{3}E_{\times}(\mathcal{A})=3p^{2}|\mathcal{A}|^{2}.

This shows that there exists $\mathcal{A}^{\prime}$ such that $4|\mathcal{A}^{\prime}|^{2}-E_{\times}(\mathcal{A}^{\prime})\geq\mathbb{E}[4|\mathcal{A}^{\prime}|^{2}-E_{\times}(\mathcal{A}^{\prime})]=p^{2}|\mathcal{A}|^{2}$ . In particular we know that $|\mathcal{A}^{\prime}|^{2}\geq\frac{p^{2}|\mathcal{A}|^{2}}{4}=\frac{|\mathcal{A}|^{6}}{4(E_{\times}(\mathcal{A}))^{2}}$ and $E_{\times}(\mathcal{A}^{\prime})\leq 4|\mathcal{A}^{\prime}|^{2}$ . ∎

The proof of Proposition 6.2 is similar to that of Theorem 4.1 but with two undetermined parameters that need to be optimized.

Proof of Proposition 6.2.

By letting the constant $C$ large, we may assume that $L$ is sufficiently large. Similar to the proof of Lemma 3.2, we upper bound the size of

X:=\{(x_{1},x_{2};y_{1},y_{2}):x_{i}y_{j}\in\mathcal{A}^{\prime}\;\leavevmode\nobreak\ \leavevmode\nobreak\ \forall\;i,j\in\{1,2\},0<x_{1}<x_{2},0<y_{1}<y_{2},x_{1}\leq y_{1}\}.

By the same argument as in Lemma 3.2 (here we use an extra symmetry between $x$ and $y$ ), we have that $E_{\times}(\mathcal{A}^{\prime})\leq 2|\mathcal{A}^{\prime}|^{2}+8|X|$ . It remains to estimate $|X|$ .

Fix $x_{1}$ . As all elements in $\mathcal{A}^{\prime}$ are congruent to $a$ mod $d$ , they are all coprime to $d$ . Therefore $x_{i}$ and $y_{j}$ are also coprime to $d$ . As a result, $x_{1}y_{1}\equiv a\equiv x_{1}y_{2}\pmod{d}$ implies that $x_{1}$ and $x_{2}$ are congruent mod $d$ . Moreover, $y_{1}$ and $y_{2}$ are both congruent to $ax_{1}^{-1}$ mod $d$ . Also note that elements in $\mathcal{A}^{\prime}$ are included in the interval $[a,a+dL)$ , we know that $\frac{x_{2}}{x_{1}}=\frac{x_{2}y_{1}}{x_{1}y_{1}}<1+\frac{dL}{a}$ . Hence also note that $x_{2}>x_{1}$ , we know that $x_{2}\in(x_{1},x_{1}+x_{1}dL/a)$ . Since $x_{2}\equiv x_{1}\pmod{d}$ , there is no valid tuple in $X$ for $\frac{x_{1}L}{a}\leq 1$ . Thus any valid tuple satisfies $x_{1}>a/L$ . Similarly, as $x_{1}y_{i}\in[a,a+dL)$ , we know that $y_{i}\in[\frac{a}{x_{1}},\frac{a}{x_{1}}+\frac{dL}{x_{1}})$ , and $y_{1},y_{2}$ are congruent mod $d$ . By the extra symmetry, we have $x_{1}\leq\sqrt{x_{1}y_{1}}<\sqrt{a+dL}$ .

The goal is to apply Theorem 4.2 to bound the number of choices for $x_{i}$ and $y_{j}$ . For each fixed $x_{1}=x\in(L/a,\sqrt{a+dL})$ , we would like to compute the number of tuples $(x_{1},x_{2};y_{1},y_{2})\in X$ . Let us denote the set of such tuples by $X(x_{1})$ .

By definition, any $m\in\mathcal{A}^{\prime}$ satisfies that $\omega(m)=k$ and $\omega(m,t)\leq f(t):=\frac{\log\log t}{\log 4}+\beta$ for all $t\in\mathbb{N}$ . Here $\omega(m,t):=\#\{p|m:p\leq t\}.$ Note that we have $x_{i}y_{j}\in\mathcal{A}^{\prime}$ . As $\mathcal{A}^{\prime}$ consists of square-free elements having $k$ distinct prime factors, we know that for any $(i,j)$ , $k=\omega(x_{i}y_{j})=\omega(x_{i})+\omega(y_{j})$ , and $\omega(x_{i},t)+\omega(y_{j},t)=\omega(x_{i}y_{j},t)\leq f(t)$ . Let $\lambda,\xi\in(0,1)$ to be determined. Then we have for each $(x_{1},x_{2};y_{1},y_{2})\in X_{2}$ ,

(\lambda^{2})^{\omega(x_{1})}(\lambda^{2})^{\omega(x_{2})}(\lambda^{2})^{\omega(y_{1})}(\lambda^{2})^{\omega(y_{2})}\lambda^{-4k}=\lambda^{\omega(x_{1}y_{1})+\omega(x_{1}y_{2})+\omega(x_{2}y_{1})+\omega(x_{2}y_{2})-4k}=1,

and for any $t\in\mathbb{N}$ ,

(\xi^{2})^{\omega(x_{1},t)}(\xi^{2})^{\omega(x_{2},t)}(\xi^{2})^{\omega(y_{1},t)}(\xi^{2})^{\omega(y_{2},t)}\xi^{-4f(t)}=\xi^{\omega(x_{1}y_{1},t)+\omega(x_{1}y_{2},t)+\omega(x_{2}y_{1},t)+\omega(x_{2}y_{2},t)-4f(t)}\geq 1.

For each $x_{1}$ , as $x_{2}<\frac{a+dL}{a}x_{1}<2x_{1}$ , if we choose $t=2x_{1}$ , then $\omega(x_{i},t)=\omega(x_{i})$ for $i=1,2$ . Hence

\begin{split}|X(x_{1})|\leq\lambda^{-4k+2\omega(x_{1})}\xi^{-4f(2x_{1})+2\omega(x_{1})}\sum_{\begin{subarray}{c}x_{1}<x_{2}<x_{1}\frac{a+dL}{a}\\ x_{2}\equiv x_{1}\;(\mathrm{mod}\;d)\end{subarray}}\left(\lambda^{2}\xi^{2}\right)^{\omega(x_{2})}\left(\sum_{\begin{subarray}{c}\frac{a}{x_{1}}\leq y<\frac{a+dL}{x_{1}}\\ y\equiv ax_{1}^{-1}\;(\mathrm{mod}\;d)\end{subarray}}\left(\lambda^{2}\right)^{\omega(y)}\left(\xi^{2}\right)^{\omega(y,2x_{1})}\right)^{2},\end{split}

First we try to estimate the inner summation by Theorems 4.2 and 4.3. To see that Theorem 4.2 is applicable with $\alpha=\beta=1/2$ and $A_{1}=A_{2}=1$ , note that we have $x^{\prime}=\frac{a+dL}{x_{1}}$ and $y^{\prime}=\frac{dL}{x_{1}}$ , and clearly $y^{\prime}>x^{\prime}$ . Since $x_{1}\leq\sqrt{a+dL}\leq\sqrt{2L\log L}$ , we have $\frac{(y^{\prime})^{2}}{x^{\prime}}=\frac{d^{2}L^{2}}{x_{1}(a+dL)}\leq\frac{d^{2}L^{2}}{(2L\log L)^{3/2}}>1$ for $L$ sufficiently large. Meanwhile we have $\frac{y^{\prime}}{d^{2}}=\frac{dL}{d^{2}x_{1}}\leq\frac{dL}{d^{2}\sqrt{2L\log L}}>1$ as $d<\sqrt{\log L}$ when $L$ sufficiently large. Note that $g(y)=\left(\lambda^{2}\right)^{\omega(y)}\left(\xi^{2}\right)^{\omega(y,2x_{1})}$ takes value $g(p)=\lambda^{2}$ for $2x_{1}<p<\frac{a+dL}{x_{1}}$ and $g(p)=\lambda^{2}\xi^{2}$ for $p<2x_{1}$ . Therefore by Theorem 4.2,

\begin{split}\sum_{\begin{subarray}{c}\frac{a}{x_{1}}\leq y<\frac{a+dL}{x_{1}}\\ y\equiv ax_{1}^{-1}\;(\mathrm{mod}\;d)\end{subarray}}\left(\lambda^{2}\right)^{\omega(y)}\left(\xi^{2}\right)^{\omega(y,2x_{1})}&\ll\frac{\frac{dL}{x_{1}}}{\phi(d)}\frac{1}{\log\frac{a+dL}{x_{1}}}\exp\left(\sum_{p\leq 2x_{1}}\frac{\lambda^{2}\xi^{2}-\lambda^{2}}{p}+\sum_{p<\frac{a+dL}{x_{1}}}\frac{\lambda^{2}}{p}\right)\\ &\ll\frac{dL}{x_{1}\phi(d)}(\log(a+dL))^{-1+\lambda^{2}}(\log x_{1})^{\lambda^{2}\xi^{2}-\lambda^{2}}.\end{split}

Here in the second line we use Theorem 4.3 to get $\sum_{p<\frac{a+dL}{x_{1}}}\frac{\lambda^{2}}{p}\leq\lambda^{2}\log\log\frac{a+dL}{x_{1}}+O(1)$ , and simiarly $\sum_{p<2x_{1}}\frac{\lambda^{2}\xi^{2}-\lambda^{2}}{p}\leq(\lambda^{2}\xi^{2}-\lambda^{2})\log\log 2x_{1}+O(1)=(\lambda^{2}\xi^{2}-\lambda^{2})\log\log x_{1}+O(1)$ .

For the outer summation, we argue that Theorem 4.2 is applicable when $x_{1}>\frac{ea^{2}}{L^{2}}$ . In this case we have $x^{\prime}=x_{1}\frac{a+dL}{a}>y^{\prime}=x_{1}\frac{dL}{a}$ . Moreover $\frac{(y^{\prime})^{2}}{x^{\prime}}=\frac{x_{1}d^{2}L^{2}}{(a+dL)a}>\frac{x_{1}d^{2}L^{2}}{2a^{2}}>1$ when $x_{1}=\frac{2ea^{2}}{L^{2}}$ . At the same time, we have $\frac{y^{\prime}}{d^{2}}=\frac{x_{1}L}{ad}>\frac{ea}{dL}>1$ . Hence Theorem 4.2 is applicable with $\alpha=\beta=1/2$ , so

\sum_{\begin{subarray}{c}x_{1}<x_{2}<x_{1}\frac{a+dL}{a}\\ x_{2}\equiv x_{1}\;(\mathrm{mod}\;d)\end{subarray}}\left(\lambda^{2}\xi^{2}\right)^{\omega(x_{2})}\ll\frac{x_{1}\frac{dL}{a}}{\phi(d)}\left(\log\frac{x_{1}(a+dL)}{a}\right)^{-1+\lambda^{2}\xi^{2}}\leq\frac{x_{1}dL}{a\phi(d)}(\log x_{1})^{-1+\lambda^{2}\xi^{2}}.

(6.1)

Here in the second inequality we use Theorem 4.3 to get $\sum_{p<x_{1}\frac{a+dL}{a}}\frac{\lambda^{2}\xi^{2}}{p}\leq\lambda^{2}\xi^{2}\log\log\frac{x_{1}(a+dL)}{a}+O(1)$ . Let $X_{1}$ be the collection of tuples in $X$ with $x_{1}<\frac{ea^{2}}{L^{2}}$ , and $X_{2}=X\setminus X_{1}$ . Summing over $x_{1}>ea^{2}/L^{2}$ , noting that $\log L<\log(a+dL)\leq\log(2L^{2})\leq 3\log L$ and that $\xi^{-4f(2x_{1})}=\xi^{-4\beta}\xi^{-4\frac{\log\log 2x_{1}}{\log 4}}\ll\xi^{-4\beta}(\log x_{1})^{\frac{2\log 1/\xi}{\log 2}}$ , we have

|X_{2}|\ll\lambda^{-4k}\xi^{-4\beta}\sum_{\frac{ea^{2}}{L^{2}}<x_{1}<\sqrt{a+dL}}\frac{d^{3}L^{3}}{ax_{1}\phi(d)^{3}}(\log x_{1})^{\frac{2\log 1/\xi}{\log 2}-1+3\lambda^{2}\xi^{2}-2\lambda^{2}}(\log L)^{-2+2\lambda^{2}}(\lambda^{2}\xi^{2})^{\omega(x_{1})}.

We partition integers $x_{1}$ in the interval $(\frac{ea^{2}}{L^{2}},\sqrt{a+dL})$ into $x_{1}\in(e^{t},e^{t+1})$ for $\lfloor\log\frac{ea^{2}}{L^{2}}\rfloor\leq t\leq\lfloor\log\sqrt{a+dL}\rfloor$ . Note that by our choice $t\geq\lfloor\log\frac{ea^{2}}{L^{2}}\rfloor\geq 1$ . In each interval we have

\begin{split}&\sum_{e^{t}<x_{1}<e^{t+1}}\frac{d^{3}L^{3}}{ax_{1}\phi(d)^{3}}(\log x_{1})^{\frac{2\log 1/\xi}{\log 2}-1+3\lambda^{2}\xi^{2}}(\log L)^{-2+2\lambda^{2}-2\lambda^{2}\xi^{2}}(\lambda^{2}\xi^{2})^{\omega(x_{1})}\\ [e^{t}<x_{1}<e^{t+1}]\ll&\frac{d^{3}L^{3}}{ae^{t}\phi(d)^{3}}t^{\frac{2\log 1/\xi}{\log 2}-1+3\lambda^{2}\xi^{2}-2\lambda^{2}}(\log L)^{-2+2\lambda^{2}}\sum_{e^{t}<x_{1}<e^{t+1}}(\lambda^{2}\xi^{2})^{\omega(x_{1})}\\ [\mbox{by Theorem}\leavevmode\nobreak\ \ref{lem:Shiu}]\ll&\frac{d^{3}L^{3}}{ae^{t}\phi(d)^{3}}t^{\frac{2\log 1/\xi}{\log 2}-1+3\lambda^{2}\xi^{2}-2\lambda^{2}}(\log L)^{-2+2\lambda^{2}}\cdot e^{t}(e-1)(t+1)^{-1+\lambda^{2}\xi^{2}}\\ \ll&\frac{d^{3}L^{3}}{a\phi(d)^{3}}t^{\frac{2\log 1/\xi}{\log 2}-2+4\lambda^{2}\xi^{2}-2\lambda^{2}}(\log L)^{-2+2\lambda^{2}}.\end{split}

Optimizing the parameters by choosing $\lambda=\frac{1}{\sqrt{\log 4}}$ and $\xi=\frac{1}{\sqrt{2}}$ , we have

\begin{split}|X_{2}|&\ll\lambda^{-4k}\xi^{-4\beta}\sum_{t=\lfloor\log\frac{ea^{2}}{L^{2}}\rfloor}^{\lfloor\log\sqrt{a+dL}\rfloor}\frac{d^{3}L^{3}}{a\phi(d)^{3}}t^{\frac{2\log 1/\xi}{\log 2}-2+4\lambda^{2}\xi^{2}-2\lambda^{2}}(\log L)^{-2+2\lambda^{2}}\\ &=(\log 4)^{2k}2^{2\beta}\frac{d^{3}L^{3}}{a\phi(d)^{3}}(\log L)^{-2+\frac{1}{\log 2}}\sum_{t=\lfloor\log\frac{ea^{2}}{L^{2}}\rfloor}^{\lfloor\log\sqrt{a+dL}\rfloor}t^{-1}\\ &\ll L^{2}(\log L)^{-2+\frac{1}{\log 2}}\cdot\log\log L\cdot(\log 4)^{2k}2^{2\beta},\end{split}

where in the last step we use that $\frac{d^{3}L^{3}}{a\phi(d)^{3}}\leq\frac{d^{2}}{\phi(d)^{3}}L^{2}\ll L^{2}$ .

It remains to estimate $|X_{1}|$ . Note that (6.1) no longer holds, so we replace it by the trivial bound

\sum_{\begin{subarray}{c}x_{1}<x_{2}<x_{1}\frac{a+dL}{a}\\ x_{2}\equiv x_{1}\;(\mathrm{mod}\;d)\end{subarray}}\left(\lambda^{2}\xi^{2}\right)^{\omega(x_{2})}\leq\sum_{\begin{subarray}{c}x_{1}<x_{2}<x_{1}\frac{a+dL}{a}\\ x_{2}\equiv x_{1}\;(\mathrm{mod}\;d)\end{subarray}}1\leq\frac{x_{1}L}{a}.

Also by the choice of $\lambda$ we have $\lambda^{-4k+2\omega(x_{1})}\leq\lambda^{-4k}=(\log 4)^{2k}$ and $\xi^{-4f(2x_{1})}=\xi^{-4\beta}\xi^{-4\frac{\log\log 2x_{1}}{\log 4}}\ll\xi^{-4\beta}(\log x_{1})^{2\frac{\log 1/\xi}{\log 2}}=2^{2\beta}\log x_{1}$ . As a consequence, we have (again noting that $\log(a+dL)=\Theta(\log L)$ )

\begin{split}|X_{1}|&\ll(\log 4)^{2k}2^{2\beta}\sum_{\frac{a}{L}<x_{1}<\frac{ea^{2}}{L^{2}}}\frac{d^{2}L^{3}}{a\phi(d)^{2}x_{1}}(\log L)^{-2+2\lambda^{2}}(\log x_{1})^{1+2\lambda^{2}\xi^{2}-2\lambda^{2}}\\ &=(\log 4)^{2k}2^{2\beta}L^{2}(\log L)^{-2+\frac{1}{\log 2}}\frac{d^{2}}{\phi(d)^{2}}\frac{L}{a}\sum_{\frac{a}{L}<x_{1}<\frac{ea^{2}}{L^{2}}}\frac{(\log x_{1})^{1+\frac{1}{\log 4}}}{x_{1}}.\end{split}

Note that we have

\sum_{\frac{a}{L}<x_{1}<\frac{ea^{2}}{L^{2}}}\frac{(\log x_{1})^{1+\frac{1}{\log 4}}}{x_{1}}\ll\left(\log\frac{ea^{2}}{L^{2}}\right)^{2+\frac{1}{\log 4}}\ll\sqrt{a/L}.

Moreover we have $\frac{d^{2}}{\phi(d)^{2}}\sqrt{\frac{L}{a}}\leq\frac{d^{\frac{3}{2}}}{\phi(d)^{2}}\ll 1$ . We conclude that $|X_{1}|\ll L^{2}(\log L)^{-2+\frac{1}{\log 2}}(\log 4)^{2k}2^{2\beta}$ . Combining with the previous estimate on $|X_{2}|$ , we have the desired upper bound $|X|=|X_{1}|+|X_{2}|\ll L^{2}(\log L)^{-2+\frac{1}{\log 2}}\cdot\log\log L\cdot(\log 4)^{2k}2^{2\beta}$ . ∎

7 Concluding remarks

As we mentioned in the introduction, the best bound we can get in Theorem 1.1 is the following.

Theorem 7.1.

Let $\mathcal{A}\subseteq\mathbb{Z}$ be a finite arithmetic progression and $\theta=1-\frac{1+\log\log 4}{\log 4}$ . Then

|\mathcal{A}\cdot\mathcal{A}|\geq\frac{{|\mathcal{A}|^{2}}}{{(\log|\mathcal{A}|)^{2\theta}(\log\log|\mathcal{A}|)^{7+o(1)}}}.

The proof of Theorem 7.1 is identical to the proof of Theorem 1.1 but we need a stronger estimate on the set $\mathcal{N}_{k}(\mathcal{A};\log 4,\beta)$ for $k$ with slightly larger size than the choice in Proposition 5.3. The stronger estimate requires ideas from the generalized Smirnov statistics [11] which is deferred to Appendix A.

We make the following conjecture on the sharp lower bound in Theorem 1.1.

Conjecture 7.2.

Let $\mathcal{A}$ be a finite arithmetic progression in integers. Then for $|\mathcal{A}|$ sufficiently large,

|\mathcal{A}\cdot\mathcal{A}|\gg\frac{|\mathcal{A}|^{2}}{(\log|\mathcal{A}|)^{2\theta}(\log\log|\mathcal{A}|)^{3/2}}.

This conjecture, if true, would be tight up to a constant factor by considering $\mathcal{A}=[N]$ . We believe that this cannot be done by only estimating the multiplicative energy of a subset.

We also extend Conjecture 1.3 to the $h$ -fold product case.

Conjecture 7.3.

Let $\mathcal{A}$ be a set of integers and $\mathcal{A}^{h}:=\{a_{1}\cdots a_{h}:a_{i}\in\mathcal{A},\;\forall\;1\leq i\leq h\}$ . If $|\mathcal{A}+\mathcal{A}|\ll|\mathcal{A}|$ . Then

|\mathcal{A}^{h}|\geq|\mathcal{A}|^{h}(\log|\mathcal{A}|)^{-h\log h+h-1-o(1)}.

One way to achieve this lower bound is by choosing $\mathcal{A}=\{1\leq n\leq N:\omega(n)=(1+o(1))\log\log N\}$ .

Acknowledgments

We would like to thank Yifan Jing and Cosmin Pohoata for helpful discussions about Conjecture 1.3. We are indebted to Kevin Ford for his helpful comments and corrections to earlier versions of the paper. We are grateful to Kannan Soundararajan for discussions about Shiu’s Theorem [27] and work of Tenenbaum [31] and Ford [12]. We thank Fernando Xuancheng Shao for pointing out reference [6] after reading an earlier draft of the paper. We appreciate Huy Tuan Pham for his interest in and discussions on the problem. We thank Dimitris Koukoulopoulos for pointing out a mistake in the reference and Marc Munsch for pointing out a missing reference. We also thank the anonymous referee for valuable comments and feedback. Finally, we are indebted to Jacob Fox for encouraging us to write this paper and for carefully reading through earlier drafts of the paper and for useful suggestions.

References

[1] M. Campos, On the number of sets with a given doubling constant, Israel J. Math. 236 (2020), no. 2, 711–726. MR 4093901
[2] M. Campos, M. Coulson, O. Serra, and M. Wötzel, The typical approximate structure of sets with bounded sumset, 2021.
[3] M.-C. Chang, Product sets of arithmetic progressions, Unpublished manuscript.
[4] M.-C. Chang, The Erdős-Szeméredi problem on sum set and product set, Ann. of Math. (2) 157 (2003), no. 3, 939–957. MR 1983786
[5] R. de la Bretèche, M. Munsch, and G. Tenenbaum, Small Gál sums and applications, arXiv e-prints (2019), arXiv:1906.12203.
[6] S. Eberhard, B. Green, and F. Manners, Sets of integers with no large sum-free subset, Ann. of Math. (2) 180 (2014), no. 2, 621–652. MR 3224720
[7] Gy. Elekes and I. Z. Ruzsa, Few sums, many products, Studia Sci. Math. Hungar. 40 (2003), no. 3, 301–308. MR 2036961
[8] P. Erdős, An asymptotic inequality in the theory of numbers, Vestnik Leningrad. Univ. 15 (1960), no. 13, 41–49. MR 0126424
[9] P. Erdős and E. Szemerédi, On sums and products of integers, Studies in pure mathematics, Birkhäuser, Basel, 1983, pp. 213–218. MR 820223
[10] P. Erdős, Some remarks on number theory, Riveon Lematematika 9 (1955), 45–48. MR 73619
[11] K. Ford, Generalized Smirnov statistics and the distribution of prime factors, Funct. Approx. Comment. Math. 37 (2007), no. part 1, 119–129. MR 2357313
[12] , The distribution of integers with a divisor in a given interval, Ann. of Math. (2) 168 (2008), no. 2, 367–433. MR 2434882
[13] , Sharp probability estimates for generalized Smirnov statistics, Monatshefte fur Mathematik 153 (2008), no. 3, 205–216.
[14] , Extremal properties of product sets, Proc. Steklov Inst. Math. 303 (2018), no. 1, 220–226, Published in Russian in Tr. Mat. Inst. Steklova 303 (2018), 239–245. MR 3920222
[15] G. A. Freĭman, Foundations of a structural theory of set addition, Translations of Mathematical Monographs, Vol 37, American Mathematical Society, Providence, R.I., 1973, Translated from the Russian. MR 0360496
[16] D. Koukoulopoulos, On the number of integers in a generalized multiplication table, J. Reine Angew. Math. 689 (2014), 33–99. MR 3187928
[17] V. F. Lev, Restricted set addition in groups. III. Integer sumsets with generic restrictions, Period. Math. Hungar. 42 (2001), no. 1-2, 89–98. MR 1832697
[18] D. Mastrostefano, On maximal product sets of random sets, J. Number Theory 224 (2021), 13–40. MR 4221525
[19] B. Murphy, M. Rudnev, I. Shkredov, and Y. Shteinikov, On the few products, many sums problem, J. Théor. Nombres Bordeaux 31 (2019), no. 3, 573–602. MR 4102615
[20] M. B. Nathanson and G. Tenenbaum, Inverse theorems and the number of sums and products, Astérisque 258 (1999), xiii, 195–204, Structure theory of set addition. MR 1701198
[21] C. Pomerance and A. Sárközy, On products of sequences of integers, Number theory, Vol. I (Budapest, 1987), Colloq. Math. Soc. János Bolyai, vol. 51, North-Holland, Amsterdam, 1990, pp. 447–463. MR 1058228
[22] M. Rudnev, G. Shakan, and I. D. Shkredov, Stronger sum-product inequalities for small sets, Proc. Amer. Math. Soc. 148 (2020), no. 4, 1467–1479. MR 4069186
[23] M. Rudnev and S. Stevens, An update on the sum-product problem, 2021.
[24] I. Z. Ruzsa, Generalized arithmetical progressions and sumsets, Acta Math. Hungar. 65 (1994), no. 4, 379–388. MR 1281447
[25] A. Selberg, Note on a paper by L. G. Sathe, J. Indian Math. Soc. (N.S.) 18 (1954), 83–87. MR 67143
[26] X. Shao and W. Xu, A robust version of Freiman’s $3k-4$ theorem and applications, Math. Proc. Cambridge Philos. Soc. 166 (2019), no. 3, 567–581. MR 3933910
[27] P. Shiu, A Brun-Titchmarsh theorem for multiplicative functions, J. Reine Angew. Math. 313 (1980), 161–170. MR 552470
[28] J. Solymosi, Bounding multiplicative energy by the sumset, Adv. Math. 222 (2009), no. 2, 402–408. MR 2538014
[29] K. Soundararajan and M. W. Xu, Central limit theorems for random multiplicative functions, arXiv e-prints (2022), arXiv:2212.06098.
[30] T. Tao and V. Vu, Additive combinatorics, Cambridge Studies in Advanced Mathematics, vol. 105, Cambridge University Press, Cambridge, 2006. MR 2289012
[31] G. Tenenbaum, Sur la probabilité qu’un entier possède un diviseur dans un intervalle donné, Compositio Math. 51 (1984), no. 2, 243–263. MR 739737
[32] , Introduction to analytic and probabilistic number theory, third ed., Graduate Studies in Mathematics, vol. 163, American Mathematical Society, Providence, RI, 2015, Translated from the 2008 French edition by Patrick D. F. Ion. MR 3363366

Appendix A Number of elements with a fixed number of primes factors in arithmetic progressions via generalized Smirnov statistics

In this section, we give a stronger estimate on size of $\mathcal{N}_{k}(\mathcal{A};\alpha,\beta)$ , than the bound in Proposition 5.3 (Section 5). This is the key ingredient in proving Theorem 7.1. Notably, our choice of $k$ here (see Proposition A.1) is slightly larger than the one we used in Proposition 5.3. The rest proof strategy of Theorem 7.1 is identical to the proof of Theorem 1.1. By applying Proposition 6.2 and Lemma 6.3 to give corresponding upper bounds on multiplicative energy, an application of Cauchy-Schwartz inequality gives lower bounds on product sets.

Recall that the set we are interested in Section 5 is the following:

\mathcal{N}_{k}(\mathcal{A};\alpha,\beta):=\{n\in\mathcal{A}:n\textrm{ square-free},\;\omega(n)=k,\;\log\log p_{j}(n)\geq\alpha j-\beta\;\leavevmode\nobreak\ \leavevmode\nobreak\ \forall\;1\leq j\leq k\}.

(A.1)

Let $N_{k}(\mathcal{A};\alpha,\beta)=|\mathcal{N}_{k}(\mathcal{A};\alpha,\beta)|$ . Our goal is to give a better lower bound on $N_{k}(\mathcal{A};\alpha,\beta)$ , comparing to Proposition 5.3. The proof uses ideas in [11].

Proposition A.1.

There exists an absolute constant $\gamma$ such that the following holds. If $\mathcal{A}=\{a+id:0\leq i<L\}$ is an arithmetic progression satisfying that $L$ is sufficiently large and $0<dL\leq a\leq L\sqrt{\log L}$ , and $\operatorname{gcd}(a,d)=1$ , then

N_{k}(\mathcal{A};\log 4,\gamma\log\log\log\log L)\gg\frac{L}{(\log L)^{\theta}}(\log\log L)^{-3/2}(\log\log\log L)^{-C_{0}}

for $k=\left\lfloor\frac{\log\log L}{\log 4}\right\rfloor$ and some fixed $C_{0}>0$ .

Proof of Proposition A.1 assuming Lemma A.4.

Let $\beta=\gamma\log\log\log\log L$ , and we may write
$\mathcal{N}_{k}=\mathcal{N}_{k}(\mathcal{A};\log 4,\beta)$ as the inputs are clear from the context. To obtain a lower bound, we consider elements $n\in\mathcal{N}_{k}$ with $p_{1}(n)p_{2}(n)\cdots p_{k-1}(n)<\sqrt{a}$ .

Once we fix such a choice of $(p_{1},p_{2},\dots,p_{k-1})$ with $p_{1}\cdots p_{k-1}<\sqrt{a}$ and $\log\log p_{j}\geq j\log 4-\beta$ for all $1\leq j\leq k-1$ , we count the number of $p_{k}$ with $p_{k}>p_{k-1}$ and $p_{1}p_{2}\cdots p_{k}\in\mathcal{A}$ . Let $q=p_{1}p_{2}\cdots p_{k-1}$ . Clearly if $qp\in\mathcal{A}$ for some prime $p$ , then $p\geq\frac{a}{q}>\sqrt{a}>q>p_{k-1}$ . Moreover we have $\log\log p>\log\log\sqrt{L}=\log\log L-\log 2>\alpha k-\beta$ when $\beta$ is sufficiently large, so any such choice of prime $p$ would give a valid choice for $p_{k}$ as defined in (A.1).

For any such fixed choice of $q$ , if $\operatorname{gcd}(q,d)>1$ , then any element in $\mathcal{A}$ is not a multiple of $q$ , so there is no such choice of $p_{k}$ .

If $\operatorname{gcd}(q,d)=1$ , we know that $q|a+id$ is equivalent to $i\equiv-ad^{-1}\pmod{q}$ . There is a unique such $i_{0}$ with $0\leq i_{0}<q$ . Then the multiples of $q$ in $\mathcal{A}$ are of the form

\left\{a+(i_{0}+k^{\prime}q)d:0\leq k^{\prime}<\frac{L-i_{0}}{q}\right\}\supseteq\{a+(i_{0}+k^{\prime}q)d:0\leq k^{\prime}<\lfloor L/q\rfloor\}.

The inclusion is because $\frac{L-i_{0}}{q}>\lfloor L/q\rfloor-1$ . Hence any element $p\in\mathcal{A}_{q}:=\{a^{\prime}+k^{\prime}d:0\leq k^{\prime}<L^{\prime}\}$ where $a^{\prime}=\frac{a+i_{0}d}{q}$ and $L^{\prime}=\lfloor L/q\rfloor$ would satisfy $pq\in\mathcal{A}$ . It is sufficient to estimate the number of primes from $\mathcal{A}_{q}$ , which itself is an arithmetic progression. As $\operatorname{gcd}(a^{\prime},d)\leq\operatorname{gcd}(a+i_{0}d,d)=\operatorname{gcd}(a,d)=1$ , we have $\operatorname{gcd}(a^{\prime},d)=1$ . Moreover, we know that $dL^{\prime}\leq\frac{dL}{q}<\frac{a}{q}\leq a^{\prime}$ and $a^{\prime}<10L^{\prime}\sqrt{\log L^{\prime}}$ when $L$ is sufficiently large. We also have that $L^{\prime}\geq\frac{L}{q}-1>\frac{L^{\frac{1}{2}}}{(\log L)^{\frac{1}{4}}}-1$ is also sufficiently large. Hence by Lemma 5.2, the number of choices for $p_{k}$ is at least

\pi(\mathcal{A}_{q})\geq\frac{dL^{\prime}}{2\phi(d)\log L^{\prime}}\geq\frac{dL/q}{4\phi(d)\log L}.

(A.2)

Hence by summing (A.2) up, we have

N_{k}(\mathcal{A};\log 4,\beta)\geq\frac{dL}{4\phi(d)\log L}\cdot\sum_{\begin{subarray}{c}p_{1}<\cdots<p_{k-1},p_{1}\cdots p_{k-1}<\sqrt{a}\\ p_{j}\nmid d,\log\log p_{j}\geq j\log 4-\beta\;\forall\;1\leq j\leq k-1\end{subarray}}\frac{1}{p_{1}\cdots p_{k-1}}.

(A.3)

To estimate the sum on the right hand side of (A.3), we use Lemma A.4. Let $\gamma^{\prime},C^{\prime}$ be the constants in Lemma A.4, and let $(x^{\prime},k^{\prime},d^{\prime},\beta^{\prime})=(\sqrt{a},k-1,d,\beta)$ . We verify that the assumptions are met. First, as $x^{\prime}\geq\sqrt{a}\geq\sqrt{L}$ , we may assume that $x^{\prime}$ is sufficiently large by setting $L$ large enough. As $L$ is sufficiently large, we have $L^{2}\geq a\geq L$ , so $L\geq x^{\prime}\geq\sqrt{L}$ . Hence $\log\log x^{\prime}=\log\log L+O(1)$ , and

k^{\prime}=k-1=\frac{\log\log L}{\log 4}+O(1)=\frac{\log\log x^{\prime}}{\log 4}+O(1).

Also we have $d\leq 10\sqrt{\log L}\leq 10\sqrt{\log(x^{\prime})^{2}}=O(\log x^{\prime})$ . By choosing $\gamma=\gamma^{\prime}$ , we have $\beta^{\prime}=\beta=\gamma\log\log\log\log L\geq\gamma\log\log\log\log x^{\prime}$ . Therefore we may apply Lemma A.4 with $a$ being polynomial in $L$ to get that there exists a constant $C_{0}>0$ such that, by recalling the definition of $\theta$ ,

\begin{split}N_{k}(\mathcal{A};\log 4,\beta)&\gg\frac{dL}{\phi(d)\log L}\cdot(\log L)^{\frac{1+\log\log 4}{\log 4}}(\log\log L)^{-3/2}(\log\log\log L)^{-C_{0}}\\ &\gg\frac{L}{(\log L)^{\theta}}(\log\log L)^{-3/2}(\log\log\log L)^{-C_{0}},\end{split}

where in the last inequality we use that $\frac{d}{\phi(d)}\geq 1$ . ∎

Theorem A.2 (Theorem 1 in [13]).

Let $\{U_{i}\}_{i=1}^{n}$ be independent uniform random variables on $[0,1]$ and $\mathbf{1}_{E}$ be the indicator function for event $E$ . Uniformly for $n\in\mathbb{N}$ and $u,w>0$ , we have

\Pr\left(\sum_{i=1}^{n}\mathbf{1}_{U_{i}\leq t}\leq(n+w-u)t+u\;\forall\;t\in[0,1]\right)=1-e^{-\frac{2uw}{n}}+O\left(\frac{u+w}{n}\right).

(A.4)

Corollary A.3.

There exists a sufficiently large constant $C$ such that the following holds. Uniformly for $\beta\geq C\alpha>0$ and $C\leq\frac{N-\alpha n+\beta}{\alpha}$ , we have

\operatorname{Vol}\left\{(x_{1},\dots,x_{n}):\begin{matrix}0\leq x_{1}\leq\cdots\leq x_{n}\leq N,\\ x_{j}\geq\alpha j-\beta\;\forall\;1\leq j\leq n\end{matrix}\right\}\leq 3\frac{N^{n}}{n!}\frac{\beta(N-\alpha n+\beta)}{n\alpha^{2}}.

Moreover, if we further have that $\frac{\beta(N-\alpha n+\beta)}{n\alpha^{2}}\leq 1$ , then

\operatorname{Vol}\left\{(x_{1},\dots,x_{n}):\begin{matrix}0\leq x_{1}\leq\cdots\leq x_{n}\leq N,\\ x_{j}\geq\alpha j-\beta\;\forall\;1\leq j\leq n\end{matrix}\right\}\geq\frac{1}{4}\frac{N^{n}}{n!}\frac{\beta(N-\alpha n+\beta)}{n\alpha^{2}}.

Proof.

We may shrink the region by $N$ along each dimension. Now $(N,\alpha,\beta)=(1,\frac{\alpha}{N},\frac{\beta}{N})$ . As the volume of $\{x_{i}=x_{j}\}$ is zero, we may assume that they are all distinct without affecting the volume. Then we know that the volume of the desired region is $\frac{1}{n!}$ of the volume of the following region:

R^{\prime}:=\{x_{1},\dots,x_{n}\in[0,1]^{n}:\textrm{the $j$-th smallest element is at least $(\alpha j-\beta)/N$ for all $1\leq j\leq n$}\}.

As $\operatorname{Vol}\{x_{j}=(\alpha j-\beta)/N\}=0$ for each $j$ , we can rewrite $R^{\prime}$ as

R^{\prime\prime}:=\left\{x_{1},\dots,x_{n}\in[0,1]^{n}:\textrm{the number of elements $\leq t$ is at most $\frac{Nt+\beta}{\alpha}$ for all $t\in[0,1]$}\right\}

without affecting the volume, i.e. $\operatorname{Vol}(R^{\prime\prime})=\operatorname{Vol}(R^{\prime})$ . Compare it with Theorem A.2. Choose $u=\frac{\beta}{\alpha}\geq C$ and $w=\frac{N-\alpha n+\beta}{\alpha}\in[C,n/u]$ . We denote the left hand side of (A.4) by $Q_{n}(u,w)$ . We have $\operatorname{Vol}(R^{\prime})=\operatorname{Vol}(R^{\prime\prime})=Q_{n}(u,w)$ . By Theorem A.3, there exists an absolute constant $C_{0}$ such that

\left|Q_{n}(u,w)-\left(1-e^{-\frac{2uw}{n}}\right)\right|\leq C_{0}\frac{u+w}{n}.

Pick $C>8C_{0}$ . Then $C_{0}\frac{u+w}{n}\leq\frac{1}{4}\frac{uw}{n}$ . Since $1-x\leq e^{-x}$ , we conclude that

\operatorname{Vol}(R^{\prime})=Q_{n}(u,w)\leq 1-e^{-\frac{2uw}{n}}+C_{0}\frac{u+w}{n}\leq\frac{2uw}{n}+\frac{1}{4}\frac{uw}{n}<3\frac{uw}{n}=3\frac{\beta(N-\alpha n+\beta)}{n\alpha^{2}}.

With the extra condition that $\frac{\beta(N-\alpha n+\beta)}{n\alpha^{2}}\leq$ , we have $\frac{uw}{n}\leq 1$ . Also note that for $x\in[0,2]$ , $e^{-x}\leq 1-\frac{x}{4}$ . Therefore we conclude that, as $\frac{2uw}{n}\in[0,2]$ ,

\operatorname{Vol}(R^{\prime})=Q_{n}(u,w)\geq\frac{uw}{2n}-C_{0}\frac{u+w}{n}\geq\frac{uw}{4n}=\frac{1}{4}\frac{\beta(N-\alpha n+\beta)}{n\alpha^{2}}.

Putting back the factor $\frac{N^{n}}{n!}$ , we get the desired statements. ∎

Lemma A.4.

There exist constants $\gamma$ and $C_{0}>0$ so that for any $x$ large enough, $k=\frac{\log\log x}{\log 4}+O(1)$ , $d=O(\log x)$ , and $\beta\geq\gamma\log\log\log\log x$ , we have

\sum_{\begin{subarray}{c}p_{1}<\cdots<p_{k},p_{1}\cdots p_{k}<x\\ p_{j}\nmid d,\log\log p_{j}\geq j\log 4-\beta\;\forall\;1\leq j\leq k\end{subarray}}\frac{1}{p_{1}\cdots p_{k}}\geq(\log x)^{\frac{1+\log\log 4}{\log 4}}(\log\log x)^{-3/2}(\log\log\log x)^{-C_{0}}

(A.5)

First let us explain the intuition behind the right hand side of (A.5). If we replace the conditions by that $p_{j}<x$ and $p_{j}\nmid d$ for all $1\leq j\leq k$ , then the sum would be

\left(\sum_{p<x,p\nmid d}\frac{1}{p}\right)^{k}=(\log\log x-O(\log\log\log d))^{k}=(\log\log x)^{k}(\log\log d)^{-O(1)}=(\log\log x)^{k-o(1)}.

Here we repeat each term on the left hand side of (A.5) by exactly $k!$ times. Thus we should expect a formula of the form $\frac{(\log\log x)^{k-o(1)}}{k!}$ . Now we aim to show that, with these extra conditions on the choices of $(p_{1},\dots,p_{k})$ , the sum stays roughly the same.

Proof.

Motivated by [11], we partition primes in $\mathcal{P}=\{p:p\nmid d\}$ into consecutive parts. Fix $\lambda_{0}=1.9$ , and for $j\geq 1$ let $\lambda_{j}$ to be the largest prime such that

\sum_{p\leq\lambda_{j}:p\nmid d}\frac{1}{p}\leq j.

Let $\mathcal{P}_{j}=\{p:\lambda_{j-1}<p\leq\lambda_{j},p\nmid d\}$ . First we can estimate the size of $\lambda_{j}$ . By maximality of $\lambda_{j}$ we have

j-1<j-\frac{1}{\lambda_{j}}<\sum_{p\leq\lambda_{j}:p\nmid d}\frac{1}{p}\leq\sum_{p\leq\lambda_{j}}\frac{1}{p}

(A.6)

Meanwhile note that $\sum_{p|d}\frac{1}{p}=O(\log\log\omega(d))=O(\log\log\log\log x)$ , so we have

\sum_{p\leq\lambda_{j}}\frac{1}{p}\leq\sum_{p\leq\lambda_{j}:p\nmid d}\frac{1}{p}+\sum_{p|d}\frac{1}{p}\leq j+O(\log\log\log\log x).

By Merten’s estimate (e.g. see Theorem 1.10 in [32]), we have

\sum_{p\leq\lambda_{j}}\frac{1}{p}=\log\log\lambda_{j}+O(1).

Thus we conclude that for some absolute constant $C>0$ ,

j-C<\log\log\lambda_{j}<j+C\log\log\log\log x.

Moreover, we know that by (A.6) we have

\sum_{p\in\mathcal{P}_{j}}\frac{1}{p}=\sum_{p\leq\lambda_{j}:p\nmid d}\frac{1}{p}-\sum_{p\leq\lambda_{j-1}:p\nmid d}\frac{1}{p}\geq j-\frac{1}{\lambda_{j}}-(j-1)=1-\frac{1}{\lambda_{j}}.

(A.7)

Fix positive integers $t_{1}\leq t_{2}\leq\dots\leq t_{k}$ .

\mathcal{P}(t_{1},\dots,t_{k}):=\{(p_{1},\dots,p_{k})\in\mathcal{P}^{k}:p_{1}<\cdots<p_{k},\quad p_{j}\in\mathcal{P}_{t_{j}},\quad\forall 1\leq j\leq k\}.

We would like to reduce the summation in (A.5) over $(p_{1},\dots,p_{k})$ into summation over $(t_{1},\dots,t_{k})$ . Thus we would like to impose some restrictions on $(t_{1},\dots,t_{k})$ so that the conditions $p_{1}\cdots p_{k}<x$ , $p_{j}\nmid d$ , and $\log\log p_{j}\geq j\log 4-\beta$ are all satisfied. Clearly $p_{j}\nmid d$ is satisfied for all $j$ . Note that we have

\log\log p_{j}\geq\log\log\lambda_{t_{j}-1}\geq t_{j}-1-C,

so the condition $\log\log p_{j}\geq j\log 4-\beta$ is satisfied if we require that $t_{j}\geq j\log 4-(\beta-1-C)$ . Meanwhile, we also need $p_{1}\cdots p_{k}<x$ . Note that we have

\sum_{j=1}^{k}\log p_{j}\leq\sum_{j=1}^{k}\log\lambda_{t_{j}}\leq\sum_{j=1}^{k}e^{t_{j}+C\log\log\log\log x}.

Hence if we define $M=\log\log x-C\log\log\log\log x$ , then $p_{1}\cdots p_{k}<x$ if

\sum_{j=1}^{k}e^{t_{j}}\leq e^{M}.

(A.8)

Now we impose the restriction that $t_{j}$ ’s are not concentrated at small values or large values: if many $t_{j}$ ’s are small, then it is hard to take distinct $p_{j}$ ’s from the same $\mathcal{P}_{t}$ ; if many of them are large then (A.8) is disobeyed. Let $T$ be a sufficiently large constant to be determined. We choose our $t_{j}$ so that they only take values in $[T+1,M-T]$ , and $t_{mT+1}\geq T+m+1$ and $t_{k-mT}\leq M-T-m$ for all positive integers $m<\frac{k}{T}$ . Let $b_{t}$ be the number of $1\leq j\leq k$ with $t_{j}=T+t$ for $1\leq t\leq M-2T$ . As $t_{1}\leq\cdots\leq t_{k}$ , the numbers $t_{1},\dots,t_{k}$ are uniquely determined by $b_{1},\dots,b_{M-2T}$ . Moreover, by our previous restriction, we know that $b_{t}\leq\min(Tt,T(M-2T-t+1),k)$ for all $1\leq t\leq M-2T$ . First we argue that by choosing $T$ sufficiently large, (A.8) is satisfied. Indeed,

\sum_{j=1}^{k}e^{t_{j}}=\sum_{t=1}^{M-2T}b_{t}e^{T+t}\leq\sum_{t=1}^{M-2T}T(M-2T-t+1)e^{T+t}=\sum_{s=1}^{M-2T}Tse^{M-T+1-s}<Te^{M-T+1}

(A.9)

which is less than $e^{M}$ if we take $T>2$ . Now we have

\begin{split}\sum_{(p_{1},\dots,p_{k})\in\mathcal{P}(t_{1},\dots,t_{k})}\frac{1}{p_{1}\cdots p_{k}}&=\prod_{t=1}^{M-2T}\frac{1}{b_{t}!}\left(\sum_{p_{1}\in\mathcal{P}_{t+T}}\frac{1}{p_{1}}\sum_{\begin{subarray}{c}p_{2}\in\mathcal{P}_{t+T}\\ p_{2}\neq p_{1}\end{subarray}}\frac{1}{p_{2}}\cdots\sum_{\begin{subarray}{c}p_{b_{t}}\in\mathcal{P}_{t+T}\\ p_{b_{t}}\neq p_{1},\dots,p_{b_{t}-1}\end{subarray}}\frac{1}{p_{b_{t}}}\right)\\ &\geq\prod_{t=1}^{M-2T}\frac{1}{b_{t}!}\left(\sum_{p\in\mathcal{P}_{t+T}}\frac{1}{p}-\frac{b_{t}-1}{\lambda_{t+T-1}}\right)^{b_{t}}\\ [\mbox{by }\eqref{eqn:P_j-lower}]\quad&\geq\prod_{t=1}^{M-2T}\frac{1}{b_{t}!}\left(1-\frac{b_{t}}{\lambda_{t+T-1}}\right)^{b_{t}}\\ [\mbox{by }b_{t}\leq tT]\quad&\geq\prod_{t=1}^{M-2T}\frac{1}{b_{t}!}\left(1-\frac{tT}{\exp\exp(t+T-1-C)}\right)^{tT}\\ &\geq\frac{1}{2}\prod_{t=1}^{M-2T}\frac{1}{b_{t}!}\end{split}

(A.10)

where the last inequality is derived by picking $T$ sufficiently large. Omitting the coefficient $1/2$ , (A.10) is the volume of the region

R(t_{1},\dots,t_{k}):=\left\{(x_{1},\dots,x_{k})\in\mathbb{R}^{k}:\begin{matrix}0\leq x_{1}\leq x_{2}\leq\cdots\leq x_{k}\leq M-2T,\\ t_{j}-T-1\leq x_{j}\leq t_{j}-T\;\forall\;1\leq j\leq k\end{matrix}\right\}.

Recall that $t_{j}$ satisfies the following conditions: $t_{j}\geq j\log 4-(\beta-1-C)$ for any $1\leq j\leq k$ , and $t_{k-mT}\geq T+m+1$ and $t_{k-mT}\leq M-T-m$ for all positive integers $m<\frac{k}{T}$ . Therefore we conclude that the union of $R(t_{1},\dots,t_{k})$ over these choices of $(t_{1},\dots,t_{k})$ contains the following region

R:=\left\{(x_{1},\dots,x_{k})\in\mathbb{R}^{k}:\begin{matrix}0\leq x_{1}\leq x_{2}\leq\cdots\leq x_{k}\leq M-2T,\\ x_{j}\geq j\log 4-(\beta-1-C)\;\forall\;1\leq j\leq k,\\ x_{mT+1}\geq T+m,x_{k-mT}\leq M-T-m\;\forall\;1\leq m<k/T\end{matrix}\right\}.

For simplicity let $\beta^{\prime}=\beta-1-C$ . Let us define

R_{0}:=\left\{(x_{1},\dots,x_{k})\in\mathbb{R}^{k}:0\leq x_{1}\leq x_{2}\leq\cdots\leq x_{k}\leq M-2T,x_{j}\geq j\log 4-\beta^{\prime}\;\forall\;1\leq j\leq k\right\},

and for $1\leq m<\frac{k}{T}$ ,

V_{1}(m)=\operatorname{Vol}(R_{0}\cap\{x_{mT+1}<m\});\quad V_{2}(m)=\operatorname{Vol}(R_{0}\cap\{x_{k-mT}>M-2T-m\}).

Then we have $R=R_{0}\setminus\left(\bigcup_{1\leq m<k/T}V_{1}(m)\cup V_{2}(m)\right)$ , so

\operatorname{Vol}(R)\geq\operatorname{Vol}(R_{0})-\sum_{1\leq m<k/T}V_{1}(m)-\sum_{1\leq m<k/T}V_{2}(m).

(A.11)

First we estimate $\operatorname{Vol}(R_{0})$ . By Corollary A.3, we may set $(\alpha,\beta,N,n)=(\log 4,\beta^{\prime},M-2T,k)$ . When $\gamma>C$ and $x$ is sufficiently large, we have $\beta^{\prime}>\log 4>0$ and

(M-2T)-k\log 4+\beta^{\prime}=(\gamma-C)\log\log\log\log x+O(1).

(A.12)

Hence the assumptions of Corollary A.3 are met, so

\operatorname{Vol}(R_{0})\gg\frac{(M-2T)^{k}}{k!}\frac{(\log\log\log\log x)^{2}}{k}.

For each $V_{1}(m)$ , we notice that the first $mT+1$ coordinates contribute volume at most $\frac{m^{mT+1}}{(mT+1)!}$ , so

V_{1}(m)\leq\frac{m^{mT+1}}{(mT+1)!}\cdot\operatorname{Vol}\{0\leq x_{mT+2}\leq\cdots\leq x_{k}\leq M-2T:x_{j}\geq\alpha j-\beta^{\prime}\leavevmode\nobreak\ \leavevmode\nobreak\ \forall\leavevmode\nobreak\ mT+2\leq j\leq k\}.

By changing the variables, we shall rewrite as $V_{1}(m)\leq\frac{m^{mT+1}}{(mT+1)!}S_{1}(m)$ where

S_{1}(m):=\operatorname{Vol}\left\{\begin{matrix}0\leq y_{1}\leq y_{2}\leq\cdots\leq y_{k-mT-1}\leq M-2T:\\ y_{j}\geq(j+mT+1)\log 4-\beta^{\prime}\leavevmode\nobreak\ \leavevmode\nobreak\ \forall\leavevmode\nobreak\ 1\leq j\leq k-mT-1\end{matrix}\right\}.

Similarly for $V_{2}(m)$ we have $V_{2}(m)\leq\frac{m^{mT+1}}{(mT+1)!}S_{2}(m)$ where

S_{2}(m):=\operatorname{Vol}\left\{\begin{matrix}0\leq y_{1}\leq y_{2}\leq\cdots\leq y_{k-mT-1}\leq M-2T:y_{j}\geq j\log 4-\beta^{\prime}\leavevmode\nobreak\ \leavevmode\nobreak\ \forall\leavevmode\nobreak\ 1\leq j\leq k-mT-1\end{matrix}\right\}.

By comparing the definition of $S_{1}(m)$ and $S_{2}(m)$ , we see that $(j+mT+1)\log 4-\beta^{\prime}>j\log 4-\beta^{\prime}$ , so the region of $S_{1}(m)$ is a subset of that of $S_{2}(m)$ . Therefore $S_{1}(m)\leq S_{2}(m)$ . We next give an upper bound on $S_{2}(m)$ . Since $\beta\geq\gamma\log\log\log\log x$ , the conditions in Corollary A.3 is satisfied once $x$ is sufficiently large (which is true as long as $L$ is large enough). By applying Corollary A.3 we have that

S_{2}(m)\leq\frac{(M-2T)^{k-1-mT}}{(k-1-mT)!}\cdot\frac{\beta^{\prime}(M-2T-\log 4(k-1-mT)+\beta^{\prime})}{(k-1-mT)\alpha^{2}}.

By using (A.12), the upper bound can be simplified as

\leq\frac{(M-2T)^{k-1-mT}}{(k-1-mT)!}\cdot\frac{\beta^{\prime}(\gamma-C)\log\log\log\log x+\beta^{\prime}(mT+O(1))}{k-1-mT}.

We next use the binomial identity $\binom{k}{mT+1}=\frac{k!}{(mT+1)!(k-1-mT)!}$ to get upper bound

\frac{(M-2T)^{k}}{k!}\cdot\frac{(mT+1)!}{(M-2T)^{mT+1}}\cdot\binom{k}{mT+1}\cdot\frac{(\log\log\log\log x+mT)\log\log\log\log x}{k-1-mT},

and now we proceed by estimating binomial coefficients to get

S_{2}(m)\leq\frac{(M-2T)^{k}}{k!}\cdot(mT+1)!\left(\frac{k}{e(M-2T)mT}\right)^{mT+1}\cdot(\log\log\log\log x+mT)\log\log\log\log x.

For $i=1,2$ , as $V_{i}(m)\leq\frac{m^{mT+1}}{(mT+1)!}S_{i}(m)\leq\frac{m^{mT+1}}{(mT+1)!}S_{2}(m)$ , we have

\begin{split}V_{i}(m)&\leq\frac{(M-2T)^{k}}{k!}\cdot\left(\frac{k}{e(M-2T)T}\right)^{mT+1}\cdot(\log\log\log\log x+mT)\log\log\log\log x\\ &\leq\frac{(M-2T)^{k}}{k!}\cdot\frac{1}{T^{mT+1}}\cdot(\log\log\log\log x)^{2}(mT)^{2}.\end{split}

We next sum up all $V_{i}(m)$ over $m<k/T$ , and compare the sum with $\operatorname{Vol}(R_{0})$ . One has

\frac{1}{\operatorname{Vol}(R_{0})}\sum_{1\leq m<k/T}V_{i}(m)\leq\sum_{m\geq 1}\frac{(mT)^{2}}{T^{mT+1}}\leq\frac{1}{2^{T}}

for any $T\geq 8$ . Thus, by choosing $T=8$ , we conclude that for $i=1,2$ ,

\sum_{m\leq k/T}V_{i}(m)<\frac{1}{4}\operatorname{Vol}(R_{0}).

Plugging these two bounds in (A.11), we get

\operatorname{Vol}(R)\geq\frac{1}{2}\operatorname{Vol}(R_{0})\gg\frac{(M-16)^{k}}{k!}\frac{(\log\log\log\log x)^{2}}{k}.

Recall that $M=\log\log x-C\log\log\log\log x$ . By using Stirling formula, there exists some positive constants $C_{1},C_{2}>0$ such that

\begin{split}\operatorname{Vol}(R)&\gg\left(\frac{e\log 4\log\log x-C_{1}\log\log\log\log x}{\log\log x}\right)^{\frac{\log\log x}{\log 4}}\frac{(\log\log\log\log x)^{2}}{(\log\log x)^{3/2}}\\ &\gg(\log x)^{\frac{1+\log\log 4}{\log 4}}\cdot\frac{(\log\log\log x)^{C_{2}}(\log\log\log\log x)^{2}}{(\log\log x)^{3/2}},\end{split}

which completes the proof. ∎

{dajauthors}

{authorinfo}

[maxxu] Max Wenqiang Xu
Department of Mathematics,
Stanford University, Stanford, CA 94305, USA
maxxu\imageatstanford\imagedotedu

{authorinfo}

[yunkunzhou] Yunkun Zhou
Department of Mathematics,
Stanford University, Stanford, CA 94305, USA
yunkunzhou\imageatstanford\imagedotedu