Product of polynomial values being large power

Abstract

Erdös and Selfridge first showed that the product of consecutive integers cannot be a perfect power. Later, this result was generalized to polynomial values by various authors. They demonstrated that the product of consecutive polynomial values cannot be the perfect power for a suitable polynomial. In this article, we consider a related problem to the product of consecutive integers. We consider all sequences of polynomial values from a given interval whose products are almost perfect powers. We study the size of these powers and give an asymptotic result. We also define a group theoretic invariant, which is a natural generalization of the Davenport constant. We provide a non-trivial upper bound of this group theoretic invariant.

1. Introduction

In [10], Erdös and Selfridge solved a long standing conjecture by showing that the product of consecutive integers cannot be a perfect power. In particular, they proved that for a fixed non-negative integer t,

(1)\begin{align} (n+d_1)(n+d_2)\cdots(n+d_k)=x^{l}, \end{align}

where $1=d_1 \lt d_2 \lt \cdots \lt d_k\leq k+t$ and l > 1, has only finite number of solutions. If t = 0 then equation (1) has no solution. After Erdös and Selfridge’s work, similar results were studied in an arithmetic progression. In [24], Saradha extended their result for an arithmetic progression. She proved that for integers $(n,d)=1$, $1\leq d\leq 6$, $k\geq 3$, $l\geq 2$, $n\geq 1$ and $y\geq 1$ the equation:

(2)\begin{align} n(n+d)\cdots (n+(k-1)d)=y^l, \end{align}

has no integral solution. Later, Saradha’s result was improved by extending the ranges of $d, k$ and l. Ultimately, Bennett and Siksek gave a complete solution to equation (2) in [3]. Specifically, they showed that, for a large positive integer k, there are at most finitely many solutions to equation (2) in the positive integers $n,d,y$, and l, where $l\geq 2$ and gcd$(n,d)=1$.

A more general setting of this problem can be formulated as follows: Let $P\in \mathbb{Z}[x]$ with positive leading coefficients. Consider the equation

(3)\begin{align} \prod_{k=1}^mP(k)=y^l. \end{align}

The question is whether the Diophantine equation (3) has solution or not. Clearly, for an arbitrary polynomial P(x) the problem is wide open. For some particular polynomials P(x) the solutions of equation (3) are known. For example, in equations (1) and (1.2), the cases of linear polynomials $P(x)=x+n$ and $P(x)=ax+b$ are given. Also, solutions of equation (3) are known for some non-linear polynomials P(x) when the power l = 2. Cilleruelo investigated the quadratic polynomial $P(x)=x^2+1$ in [6]. Following the result in [6] many authors studied the problem and gave solutions for the polynomials $4x^2+1$, $2x(x-1)+1$, $ax^2+bx+c$, and $x^l+m^l$ for $m\in \mathbb{N}$ and $l\geq 2$.

In [9], Erdös, Malouf, Sellfridge, and Szekeres considered a related problem to equation (3). They investigated when the product of integers from a given interval has perfect power. They showed that in any interval of a certain length there are integers whose product is perfect power. This naturally raises the question: if at an interval there are sets of integers whose products are perfect powers, what is the maximal value of such a power? More specifically, the problem can be formulated as follows: Let $[1,N]\subset \mathbb{N}$ be a given interval. Consider all possible integers $x_1, x_2, x_3,\dots, x_m, y$ from the above interval, and $l\in \mathbb{N}$ so that

(4)\begin{align} x_1x_2x_3\cdots x_m=y^l. \end{align}

Let L(N) be the maximum value of all l satisfied equation (4). So what will be the supremum of L(N) in terms of N? In [25], Skalba first considered this problem and gave upper and lower bounds for $L(N$). Later Goudout [13] improves the upper bound of L(N) given in [25]. If we combine the Skalba and Goudout results, then one has

\begin{align*} L(N)=N\exp(-(\sqrt{2}+o(1))\sqrt{\log N \log\log N}), \end{align*}

as $N\to\infty$.

In this article, we will consider sequences $\{x_i\}$’s with certain restrictions. In particular, we will take all sequences $\{x_i\}$’s those are some polynomial values, but the product of $\{x_i\}$’s are perfect powers. We can rewrite this problem in the following way: Let $P(x)\in \mathbb{Z}[x]$ be a polynomial with a positive leading coefficient. Then for any given interval $[1,N]\cap \mathbb{N}$ we consider all possible products of the form:

(5)\begin{align} P(x_1)P(x_2)\cdots P(x_m)=y^{\omega}, \end{align}

where $P(x_i)$’s are taken from the interval $[1,N]\cap \mathbb{N}$. Let $\omega_P(N)$ be the maximum value of all ω satisfies equation (5). What are the infimum and supremum of $\omega_P(N)$? In general finding such bounds for a general polynomial P(x) are difficult.

Here we will obtain such bounds for some specific polynomials. First, we consider the following product:

(6)\begin{align} P(x_1)P(x_2)\cdots P(x_m)=by^{\omega}, \end{align}

for integers $P(x_i), y$, b in $ [1,N]$ and $\operatorname{gcd}(b,y)=1$.

Let $\omega_P(N)$ be the maximum value of all ω satisfies equation (6). Our first result is an asymptotic of $\omega_P(N)$ when P(x) is a linear polynomial generate integers those are in arithmetic progression.

Theorem 1.1. Let a and q be two integers with $(a,q)=1$ and $P(x)=ax+q$. Let ${\omega}_P(N)$ be the largest possible integer so that

\begin{align*} P(x_1)P(x_2)\cdots P(x_k)=by^{{\omega}_P(N)}, \end{align*}

when $P(x_i)$, b, and y are integer in $[1,N]$, and $\operatorname{gcd}(b,y)=1$. Then uniformly for,

\begin{equation*}\log q\leq c\sqrt{\log N\log\log N},\end{equation*}

we have

\begin{align*} {\omega}_P(N)\sim\frac{N}{q\exp((\sqrt{2}+o(1))\sqrt{\log N\log\log N})}, \end{align*}

as $N\to \infty$.

In our next result, we give bounds for ${\omega}_P(N)$ when P(x) is not a linear polynomial but some other suitable polynomials.

Theorem 1.2. Let ${\omega}_P(N)$ be the largest possible integer so that

\begin{align*} P(x_1)P(x_2)\cdots P(x_k)=by^{{\omega}_P(N)}, \end{align*}

for $P(x_i), b$, and y are in teger in $[1,N]$ and $\operatorname{gcd}(b,y)=1$.

1. (1) Let a and q be two fixed positive integer and $P(x)=x(ax+q)$. Then for any ϵ > 0, there exist constants C ₁ and C ₂ depends on ϵ, a, and b such that

   \begin{align*} \frac{C_1N^{1-\epsilon}}{\log N} \leq {\omega}_P(N)\leq C_2N^{1-\epsilon}. \end{align*}

2. (2) Let $P(x)=x^2+1$. Then there exist constants C ₁ and C ₂ depends on ϵ such that

   \begin{align*} \frac{C_1N^{\frac{30}{179}-\epsilon}}{\log N} \leq {\omega}_P(N)\leq C_2N^{\frac{179}{328}-\epsilon}. \end{align*}

3. (3) Let $P(x)=(x+1)(x+2)\cdots(x+l)$ for some positive integer l. Then for sufficiently large N there exist a constants C ₁ and C ₂ depends on ϵ and l such that

   \begin{align*} \frac{C_1N^{1-\exp(-1/l)-\epsilon}}{\log N} \leq {\omega}_P(N)\leq C_2N^{1+\exp(-1/l)-\epsilon}, \end{align*}

   provided none of the $P(x_i)$ has any common factors.

2. Preliminaries

2.1. Davenport constant

Our argument depends on the Davenport constant, which is a group-theoretic invariant. Let G be a finite abelian multiplicative group with the identity element 1. Then the Davenport constant D(G) of the group G is the minimal integer such that every sequence of length D(G) from G has a sub-sequence whose product is equal to the identity elements of the group. A trivial bound of the Davenport constant is $D(G)\leq |G|$. Due to its various implications, from the decomposition of irreducible integers in the ideal class group (see [8]) to the proof of the infinitude of Carmichael numbers (see [1]), a great deal of work has been done on obtaining the best possible bound of the Davenport constant. Let $\mathbb{M}_n$ denote the cyclic group of order n. Then any finite abelian group G can be written as $G=\mathbb{M}_{n_1}\times \mathbb{M}_{n_2}\times \cdots\times \mathbb{M}_{n_d}$ where $n_1, n_2, \dots, n_d$ are unique integers with $n_1\geq 2$ and $n_i\mid n_{i+1}$ for $1\leq i\leq d$. Here, the integers d and n_d are the rank and the exponent of the group G, respectively. If $G=\mathbb{M}_n$ is a cyclic group, then $D(G)=n$. This can be seen by just considering the sequence $(a,a,\cdots,a)$ where a is a generator of G. In [21, 22], Olson proved that if G is a finite p-group then

(7)\begin{align} D(G)=(n_1+n_2+\cdots+n_d)-d+1, \end{align}

and $D(G)=n_1+n_2-1$ when the rank of G is 2. It is still unknown whether the equality equation (7) holds for any finite abelian group of rank greater than 2. Boas [27] and Gao [12] showed that equality equation (7) holds for a wide class of finite abelian groups of rank 3. In particular, finding the right size of Davenport constant is still an open problem. In [20], Narkiewicz conjectured that $D(G)\leq (n_1+n_2+\cdots+n_d)$. The best upper bound of D(G) is

(8)\begin{align} D(G)\leq \exp(G)\left(1+\log \frac{|G|}{\exp(G)}\right), \end{align}

which is due to Van Emde Boas and Kruyswijk [26], Meshulam [19], and Alford, Granville and Pomerance [1]. Here $\exp(G)$ is the the exponent of the group G. Various generalizations of the Davenport constant are studied in the literature.

Now we will define a generalization of the Davenport constant.

Definition 2.1. Let A be a subgroup of G and e be the identity element of G. We define the A-relative Davenport Constant of G by the least positive integer $\ell$ such that every sequence $(\bar{x}_1,\cdots,\bar{x}_{\ell})$of $G/A$ of length $\ell$ has a non-trivial sub-sequence $ (\bar{x}_{i_1},\cdots,\bar{x}_{i_r})$ such that $\prod_{j=1}^{r} \bar{x}_{i_j} = \bar{e}$.

In the rest of the paper, we will use the notation $D^{(A)}(G)$ for the A-relative Davenport constant. Note that, $D^{(A)}(G)=D(G)$ when $A=\{e\}$.

In the next lemma, we will give a non-trivial upper bound of $D^{(A)}(G)$.

Lemma 2.2. Let G be a finite abelian group and A be a subgroup of G. Then one has

\begin{align*} D^{(A)}(G) \le \exp(G) \left(1+\log \frac{|G|}{\exp(G)}-\frac{D(A)-1}{\exp(G)}\right). \end{align*}

Proof. It is enough to prove for a non-trivial subgroup A of G. Let e be the identity element. We will show that

(9)\begin{align} D^{(A)}(G)\leq D(G)-D(A)+1. \end{align}

Let $(a_1,a_2,\cdots,a_m)$ be a sequence from A of length $D(A)-1$ such that there is no sub-sequence whose product is e. To arrive a contradiction, we consider $D^{(A)}(G) \gt D(G)-D(A)+1$. Note that, by the definition $D^{(A)}(G)\leq D(G)$. Let $(x_1,x_2,\cdots,x_l)$ be a sequence of length $D^{(A)}(G)-1$ such that there is no sub-sequence whose product is in A. Next, we consider the sequence $(a_1,a_2,\cdots,a_m, x_1,x_2,\cdots,x_l)$. Since this sequence has length at least D(G) then there exists a sub-sequence $(a_{s_1}, a_{s_2},\cdots,a_{s_q},x_{r_1},x_{r_2},\cdots,x_{r_t})$ such that

\begin{align*} a_{s_1}a_{s_2}\dots a_{s_q}x_{r_1}x_{r_2}\dots x_{r_t}=e. \end{align*}

This shows $x_{r_1}x_{r_2}\dots x_{r_t}\in A$. This gives us a contradiction. Combining equation (9) with equation (8) we have the result of the lemma.

2.2. Smooth polynomial values

Consider the set of y-smooth integers

\begin{align*} S(x,y)=\{n\leq x: p^+(n)\leq y\}, \end{align*}

where $p^+(n)$ denotes the largest prime factor of n. It is well known that the cardinality of the set $S(x,y)$, which is denoted by $\Psi(x,y)$, is

\begin{align*} \Psi(x,y)=\left(1+o(1)\right)\rho(u)x, \end{align*}

where $u=\frac{\log x}{\log y}$ and ρ is the Dickman-de Brujin function satisfies the following differential equation:

\begin{align*} u\rho'(u)+\rho(u-1)=0. \end{align*}

We need the following asymptotic results. The most important special case of smooth number estimate is (see [16, p. 270])

Lemma 2.3. Let $L(x)=\exp(\sqrt{\log x\log\log x})$. Then

\begin{align*} \psi(x,L(x)^c)=\frac{x}{L(x)^{1/2c+o(1)}} \end{align*}

as $x\to\infty$.

One generalization of y-smooth number is polynomial values having prime factor no greater than y. Consider the polynomial ring $\mathbb{Z}[x]$. Let $P(x)\in \mathbb{Z}[x]$ and define the set

\begin{align*} S_P(x,y)=\{n\leq x: p^+\left(P(n)\right)\leq y\}. \end{align*}

Let $\Psi_P(x,y)$ denote the cardinality of the set $S_P(x,y)$. For a linear polynomial $P(x)=ax+q$ Chowla and Vijayaraghavan [5] and Buchstab [4] gave an estimate of $\Psi_P(x,y)$ for a fixed f and u. Later, Ramaswami [23] gave an uniform version of Buchstab’s results. Fouvry and Tenenbaum [11] and Granville [14, 15] made significant improvement of Ramaswami’s uniform result. The following result can be found in [11, 14, 15]. See also Hildebrand and Tenenbaum [18, Sec. 6]

Lemma 2.4. Let $(a,q)=1$ and $P(x)=ax+q$. Then

\begin{align*} \Psi_P(x,y)=\frac{x}{qu^{u+o(u)}}, \end{align*}

for $x\geq 3$, $1\leq u\leq e^{c\sqrt{\log y}}$, and $q\leq e^{c\sqrt{\log y}}$.

For degree 2 polynomial Balog ans Ruzsa [2] gave bounds of $\Psi_P(x,y)$.

Lemma 2.5. Let $a, b\in \mathbb{Z}$ and $P(x)=x(ax+b)$. Then for all α > 0

\begin{align*} \Psi_P(x,x^{\alpha})\asymp_{P,\alpha}x. \end{align*}

For degree 2 irreducible polynomial we have little weaker result. Dartyge [7] showed that

Lemma 2.6. Let $P(x)=(x^2+1)$ and $\alpha \gt {\frac{149}{179}}$. Then

\begin{align*} \Psi_P(x,x^{\alpha})\asymp_{\alpha,P} x \end{align*}

holds for all large x.

Now, if $P(x)\in \mathbb{Z}$ is a completely reducible polynomial of any degree then Hildebrand [17] computed bounds of $\Psi_P(x,y)$. In particular, Hildebrand [17] proved the following. A set $A\subset \mathbb{N}$ is said to be stable if for each fixed $t\in \mathbb{N}$, $n\in A\Rightarrow tn\in A$. Define the lower asymptotic density of the set A by

\begin{align*} d(A)=\liminf_{x\to\infty}\frac{1}{x}\#\{n\leq x:n\in A\}. \end{align*}

Then

Lemma 2.7. Let $k\geq 2$ be an integer and $\alpha_k=\frac{k-2}{k-1}$. Then any stable set $A\subset \mathbb{N}$ with $d(A) \gt \alpha_k$ satisfies

\begin{align*} d(\{n:n+i \in A, i=0,1,2,\dots,k\}) \gt 0. \end{align*}

In particular if we take

\begin{align*} A=\{n:p^{+}(n) \gt y\}, \end{align*}

then for $P(x)=(x+1)(x+2)\cdots(x+k)$ and $\alpha \gt e^{-\frac{1}{k-1}}$ one has

(10)\begin{align} \Psi_P(x,x^{\alpha})\asymp_{\alpha,P} x \end{align}

for all large x.

3. Proof of Theorem 1.1

3.1. Lower bound

Let $\mathbb{Q}_{+}$ be the set of all positive rational numbers and

\begin{align*} \mathbb{Q}_{+}^{\omega}=\{q^{\omega}:q \in \mathbb{Q}_{+}\} \end{align*}

for some positive integer ω which will be chosen later. Then $\mathbb{Q}_{+}/ \mathbb{Q}_{+}^{\omega}$ form a multiplicative group. Let y be a fixed positive integer and $\{p_1,p_2,\cdots,p_t\}$ are primes in $[1,y]$. Clearly, $t=\pi(y)$. Let us denote $\overline{p_i}$ be the image of the prime p_i in the quotient group $\mathbb{Q}_{+}/ \mathbb{Q}_{+}^{\omega}$ and G be the finite abelian subgroup of $\mathbb{Q}_{+}/ \mathbb{Q}_{+}^{\omega}$ generated by the elements $\{\overline{p_1}, \overline{p_2},\cdots,\overline{p_t}\}$. Hence,

(11)\begin{align} G\cong \underbrace{\mathcal{C}_{\omega}\times \mathcal{C}_{\omega}\times\cdots\times\mathcal{C}_{\omega}}_{t \mathrm{times}}., \end{align}

where $\mathcal{C}_{\omega}$ is the cyclic group of the order ω > 2. Let S be the set of all y-smooth integer from $[1,N]$ and $S_P=S\cap \{P(n):1\leq n\leq N\}$, where $P(x)=ax+q$. Let us consider $S_P=\{P(n_1), P(n_2), \cdots,P(n_s)\}$. Note that $\overline{P(n_i)}\in G$. Now we choose ω such that

(12)\begin{align} (\omega-1)y\log N\leq s. \end{align}

Clearly for large N, one has $s\geq \omega\pi(y)\log(\omega)-1=\omega t\log(\omega)-1\geq D^{(A)}(G)$ for some non-trivial subgroup A of G. Then by Lemma 2.2, there exists a subgroup A of G such that

\begin{align*} \overline{P(n_{r_1})}\cdot\overline{P(n_{r_2})}\cdots\overline{P(n_{r_k})}=\overline{b} \end{align*}

for some $\overline{b}\in A$ and hence

\begin{align*} {P(n_{r_1})}\cdot{P(n_{r_2})}\cdots{P(n_{r_k})}\in b\mathbb{Q}_{+}^{\omega}. \end{align*}

Therefore

\begin{align*} {P(n_{r_1})}\cdot{P(n_{r_2})}\cdots{P(n_{r_k})}= bl^{\omega}, \end{align*}

for some integer l with $\operatorname{gcd}(b,l)=1$. Now, form the right side of equation (12), one has

\begin{align*} \log\omega\geq \log s-\log y-\log\log N. \end{align*}

From the lemma 2.4 we can choose $y=\exp(\sqrt{\log N\log\log N/2})$ and hence $\log s=\log N-\log q-(u+o(u))\log u$. Therefore

\begin{align*} \log \omega&\geq \log N-\log q-(u+o(u))\log u-\sqrt{\log N\log\log N/2}-\log\log N\\ &\geq \log N-\log q-\frac{\log N}{\log y}(\log\log N-\log\log y)-\sqrt{\log N\log\log N/2}\\ &\hspace{8cm}-\log\log N+o(u)\log u\\ &\geq \log N-\log q-\sqrt{2\log N\log\log N}+o(\sqrt{\log N\log\log N}). \end{align*}

In the penultimate step above we have used the definition

\begin{align*} u=\frac{\log N}{\log y}. \end{align*}

Hence, we obtain

\begin{align*} \omega\geq \frac{N}{q\exp((\sqrt 2+o(1))\sqrt{\log N\log\log N})}. \end{align*}

3.2. Upper bound

Let us consider

\begin{align*} P(x_1)P(x_2)\cdots P(x_m)=bl^{\omega}, \end{align*}

and p be the largest prime factor of l ^ω. Clearly, p ^ω is a factor of $p^{\nu_p(bl^{\omega})}$. Here $\nu_p(x)$ is the p-adic valuation of the integer x. Next we consider the set

\begin{align*} A=\{P(n):P(n)\leq N, P(n)\text{ is }p\text{-smooth}, p\mid P(n)\}. \end{align*}

Hence $|A|\leq \psi_P(N/p,p)$. One can check if k is the largest value for which $p^k\leq N$ then $k\leq \log N/\log p$. Put all these information together with Lemma 2.4 we have

(13)\begin{align} \omega\leq \nu_p(bl^{\omega}) &\leq \psi_P\left(\frac{N}{p},p\right)\frac{\log N}{\log p}\nonumber\\ &\leq \frac{1}{q}L(p), \end{align}

where $L(p)=\frac{N}{p}v^{-v+o(v)}\frac{\log N}{\log p}$ and $v=\frac{\log N/p}{\log p}$. Now we will maximize the function L(p). Note that

(14)\begin{align} \log L(p)&=\log N-\log p\nonumber\\ &\quad+\left(1-\frac{\log N}{\log p}\right)\left(\log\log N-\log\log p+\log(1-\log p/\log N)\right)+o(v\log v). \end{align}

To maximize equation (14) one needs to choose p so that $\log p$ and

\begin{align*} \frac{\log N}{\log p}\left(\log\log N-\log\log p\right), \end{align*}

are of same size. Let us set

\begin{align*} p=\exp\left(\left(\frac{1}{\sqrt{2}}+o(1)\right)\sqrt{\log N\log\log N}\right). \end{align*}

Therefore

(15)\begin{align} \log p+\frac{\log N}{\log p}\left(\log\log N-\log\log p\right)&=\left(\frac{1}{\sqrt{2}}+o(1)\right)\sqrt{\log N\log\log N}\nonumber\\ &\quad+\frac{\log N}{2\log p}\log\log N+O\left(\sqrt{\log N\log\log N}\right)\nonumber\\ &=\left(\sqrt{2}+o(1)\right)\sqrt{\log N\log\log N}. \end{align}

Hence from equations (14) and (15) we have

(16)\begin{align} \operatorname{max}_p L(p)=N\exp\left(-\left(\sqrt{2}+o(1)\right)\sqrt{\log N\log\log N}\right). \end{align}

Substituting equation (16) in equation (13) will give the required upper bound.

4. Proof of Theorem 1.2

Proof of Theorem 1.2 is similar to the proof of Theorem 1.1.

Lower bounds: Consider the set S be the set of all y-smooth integers in $[1,N]$. Let us define $S_P=S\cap \{P(n):1\leq n\leq N\}$ for a polynomial P(x). Let us denote $S_P=\{P(n_1), P(n_2), \cdots,P(n_s)\}$. Clearly $\overline{P(n_i)}\in G$, where G is defined in equation (11). Similar to the previous section we consider

(17)\begin{align} (\omega-1)y\log N\leq s\leq \omega y\log N. \end{align}

Hence $s\geq \omega\pi(y)\log(\omega)-1=\omega t\log(\omega)-1\geq D^{(A)}(G)$ for some non-trivial subgroup A of G. Then by Lemma 2.2 we have

\begin{align*} \overline{P(n_{r_1})}\cdot\overline{P(n_{r_2})}\cdots\overline{P(n_{r_k})}=\overline{b}, \end{align*}

where $\overline{b}\in A$ Therefore there exists an integer l with gcd$(b,l)=1$ such that

\begin{align*} {P(n_{r_1})}\cdot{P(n_{r_2})}\cdots{P(n_{r_k})}= bl^{\omega}. \end{align*}

From the inequality equation (17) we have

\begin{align*} \log\omega\geq \log s-\log y-\log\log N. \end{align*}

1. (1) Let us consider the polynomial $P(x)=x(ax+q)$. By Lemma 2.5 we have that for all α > 0, $s\geq C_{\alpha}N$ when $y=N^{\alpha}$. Therefore,

   \begin{align*} w\geq C_{\alpha}\frac{N^{1-\alpha}}{\log N}. \end{align*}

2. (2) Next we consider the polynomial $P(x)=x^2+1$. By Lemma 2.6 we have for all $\alpha \gt 149/179$, $s\geq C_{\alpha}N$ when $y=N^{\alpha}$. Set $\alpha=\frac{149}{179}+\epsilon$. Therefore,

   \begin{align*} w\geq C_{\epsilon}\frac{N^{\frac{30}{179}-\epsilon}}{\log N}. \end{align*}

3. (3) Lastly, we consider the polynomial of degree l defined by $P(x)=(x+1)(x+2)\dots$$(x+l)$. From the equation (10) and for $\alpha \gt e^{-\frac{1}{l-1}}$ we have $s\geq C_{\alpha}N$ when $y=N^{\alpha}$. Take $\alpha=e^{-\frac{1}{l-1}}\epsilon$ and one has

   \begin{align*} w\geq C_{\epsilon}\frac{N^{1-\exp(-1/l)-\epsilon}}{\log N}. \end{align*}

Upper bounds: From the inequality equation (13) we find

(18)\begin{align} \omega\leq \psi_P\left(\frac{N}{p},p\right)\frac{\log N}{\log p} \end{align}

for any polynomial P. From Lemmas 2.5, 2.6, and equation (10) one finds that the right side of equation (12) maximizes when $p=N^{\frac{\alpha}{\alpha+1}}$ for a suitable α. Hence

\begin{align*} w\leq C_{\alpha}N^{\frac{1}{\alpha+1}}. \end{align*}

Now we choose any α > 0, $\alpha=\frac{149}{179}+\epsilon$, and $\alpha=e^{-\frac{1}{l-1}}+\epsilon$ respectively for $P(x)=x(ax+q)$, $P(x)=x^2+1$, and $P(x)=(x+1)(x+2)\dots(x+l)$. This will give the desired upper bounds and which completes the proof of the theorem.