The Brun–Hooley sieve for 𝔽₂[X] and squarefree shifts of integer polynomials

Abstract

Let f(x) and g(x) be polynomials in $\mathbb F_{2}[x]$ with ${\rm deg}\text{ } f=n$. It is shown that for $n\gg 1$, there is an $g_{1}(x)\in \mathbb F_{2}[x]$ with ${\rm deg}\text{ } g_{1}\leqslant \max\{{\rm deg}\text{ } g, 6.7\log n\}$ and $g(x)-g_{1}(x)$ having $ \lt 6.7\log n$ terms such that $\gcd(f(x), g_{1}(x))=1$. As an application, it is established using a result of Dubickas and Sha that given $f(x)\in \mathbb F_{2}[x]$ of degree $n\geqslant 1$, there is a separable $g(x)\in 2[x]$ with ${\rm deg}\text{ } g= {\rm deg}\text{ } f$ and satisfying that $f(x)-g(x)$ has $\leqslant 6.7\log n$ terms. As a simple consequence, the latter result holds in $\mathbb Z[x]$ after replacing ‘number of terms’ by the L₁-norm of a polynomial and $6.7\log n$ by $6.8\log n$. This improves the bound $(\log n)^{\log 4 +\operatorname{\varepsilon}}$ obtained by Filaseta and Moy.

1. Introduction

For $f(x)\in \mathbb Z[x]$ of degree n, let $L_{1}(f)$ denote the sum of the absolute values of the coefficients of f(x). This is the L ₁-norm on the $(n+1)$-dimensional real vector space U_n of real polynomials of degree $\leqslant n$. Let $V_{n}= U_{n}\cap \mathbb Z[x]$. Further, let $I_{n}\subset V_{n}$ be the set of polynomials in V_n that are irreducible over the rationals. It is well-known that asymptotically, a $100\%$ polynomials in V_n are irreducible over the rationals in the sense that

\begin{equation*} \lim_{B\to \infty}\frac{\#\{f(x)\in I_{n}: L_{1}(f)\leqslant B\}}{\#\{f(x)\in V_{n}: L_{1}(f)\leqslant B\}}=1 \end{equation*}

Thus, given $f(x)\in \mathbb Z[x]$ of degree n, one can naturally expect to be able to find a polynomial $g(x)\in I_{n}$, such that $L_{1}(f-g)$ is ‘small’. Let C(n) denote the smallest positive integer such that for every $f(x)\in \mathbb Z[x]$ with ${\rm deg}\text{ } f=n$, there is an $g(x)\in I_{n}$ such that $L_{1}(f-g)\leqslant C(n)$. It is easy to see that Eisenstein’s criterion with p = 2 implies that C(n) exists and that $C(n)\leqslant n+2$. Pál Turán proposed the problem of showing that C(n) is absolutely bounded. For each odd n > 1, the example $f(x)=x^{n}$ shows that $C(n)\geqslant 2$. Similarly, for every even n > 2, the polynomial $x^{n-2}(x^{2}-x-1)$ suggests that $C(n)\geqslant 2$. Filaseta [5] conjectured that $C(n)\leqslant 5$ for all n. In the same paper, he alludes to the possibility that $C(n)\leqslant 2$ cannot be ruled out.

Turán’s conjecture remains open for n > 40. Bérczes and Hajdu [1, 2] have verified Turán’s conjecture with $C(n)\leqslant 4$, for all polynomials $f(x)\in \mathbb Z[x]$ with ${\rm deg}\text{ } f \leqslant 24$. Filaseta and Mossinghoff [6] have extended their results to all $f(x)\in \mathbb Z[x]$ with ${\rm deg}\text{ } f \leqslant 40$ and with $C(n)\leqslant 5$.

Turán’s conjecture is believed to be difficult. For instance, whether it is possible to do better than $C(n)\leqslant n+2$ is unknown. The present paper is a byproduct of our attempts to improve this bound. Although we fell short in this pursuit, our approach considerably improved the corresponding bound in the squarefree analogue of Turán’s conjecture. We discuss them next.

We begin with our initial idea to improve the bound on C(n). For $f(x)\in 2[x]$, let L(f) denote the number of terms of f(x). Now, consider Turán’s problem in $2[x]$, where the distance between f(x) and g(x) is now taken to be $L(f-g)$. Let $C_{2}(n)$ denote the counterpart for C(n) in this case. We claim that $C(n)\leqslant C_{2}(n)+1$ provided that ${\rm deg}\text{ } g ={\rm deg}\text{ } f=n$. To see this, for an $f(x)\in \mathbb Z[x]$ with ${\rm \deg}\text{ } f =n$, let $\delta\in \{0,1\}$ be such that $f_{\delta}(x)=\delta x^{n}+f(x)$ has an odd leading coefficient. Let $\overline{f_{\delta}}(x)\in \mathbb F_{2}[x]$ denote the polynomial obtained by reducing the coefficients of $f_{\delta}(x)$ modulo 2. Observe that ${\rm \deg}\text{ } \overline{f_{\delta}} =n$. Now, suppose that there is an $g(x)\in \mathbb F_{2}[x]$, irreducible in $\mathbb F_{2}[x]$ with ${\rm \deg}\text{ } g = n$, such that $L(\overline{f_{\delta}}-g)\leqslant C_{2}(n)$. Consider the polynomial

\begin{equation*} g_{\delta}(x) = f_{\delta}(x) -\overline{f_{\delta}}(x) +g(x) = f(x) -\overline{f}(x) + g(x) \in \mathbb Z[x] \end{equation*}

where, by abuse of notation, we now consider $\overline{f_{\delta}}(x)$, $\overline{f}(x)$ and g(x) as polynomials in $\mathbb Z[x]$. If a denotes the leading coefficient of f(x), then the leading coefficient of $g_{\delta}(x)$ is

\begin{equation*} a - \overline{a} + 1 \equiv 1\pmod{2}. \end{equation*}

In particular, $g_{\delta}(x)$ has degree n. Additionally, $g_{\delta}(x)\equiv g(x)\pmod{2}$ implies that $g_{\delta}(x)$ is irreducible over the rationals. Furthermore,

\begin{equation*} L_{1}(f-g_{\delta}) \leqslant 1 + L_{1}(\overline{f_{\delta}}-g)=1+L(\overline{f_{\delta}}-g)\leqslant 1+C_{2}(n). \end{equation*}

The assertion follows.

In view of the last observation above, it suffices to bound $C_{2}(n)$. For $n\geqslant 1$, let $C'_{2}(n)$ denote the smallest positive integer such that given f(x) and g(x) in $2[x]$ with ${\rm \deg}\text{ } f = n$, there is a polynomial $g_{1}(x)\in 2[x]$ with

\begin{equation*} {\rm \deg}\text{ } g_{1}\leqslant \max\{{\rm \deg}\text{ } g, C'_{2}(n)\},\quad L(g-g_{1})\leqslant C'_{2}(n) \end{equation*}

such that $\gcd(f(x), g_{1}(x))=1$. The better part of the paper is devoted to developing a method to establishing that $C'_{2}(n)\ll \log n$.

Now, suppose for the moment that we have achieved $C'_{2}(n) \leqslant \theta \log n$ for some θ > 0. Let ${\rm \deg}\text{ } g=m\geqslant 1$, and set $\ell =\lfloor m/2\rfloor$. Take f(x) to be the product of all irreducible polynomials of degree $\leqslant \ell$ in $2[x]$. By Lemma 3.2, [7], we have ${\rm \deg}\text{ } f \leqslant 2^{\ell+1}$. The hypothesis on $C'_{2}(n)$ would then imply that there is a polynomial $g_{1}(x)\in 2[x]$ with ${\rm \deg}\text{ } g_{1}\leqslant {\rm \deg}\text{ } g$ and satisfies

\begin{equation*} L(g-g_{1})\leqslant C'_{2}({\rm \deg}\text{ } f) \leqslant \theta(\ell+1)\log 2 \leqslant \frac{\theta(m+2)\log 2}{2} \end{equation*}

such that $\gcd(f(x), g_{1}(x))=1$. The last condition implies that $g_{1}(x)$ has no irreducible factor of degree $\leqslant {\rm \deg}\text{ } g/2$. Since ${\rm \deg}\text{ } g_{1}\leqslant {\rm \deg}\text{ } g$, it would then follow that $g_{1}(x)$ is irreducible in $ 2[x]$. A suitably small θ would then give a better bound on C(m) than m + 2. In fact, any $\theta \lt 2/\log 2 = 2.885\ldots$ would give the first non-trivial improvement on C(m). Our main result establishes that $C'_{2}(n)\ll \log n$.

Theorem 1. Let f(x) and g(x) be polynomials in $ 2[x]$ with ${\rm \deg}\text{ } f=n$. For $n\gg 1$, there is a polynomial $g_{1}(x)\in \mathbb F_{2}[x]$ with ${\rm \deg}\text{ } g_{1}\leqslant \max\{{\rm \deg}\text{ } g, 6.7\log n\}$ and $L(g-g_{1}) \lt 6.7\log n$ such that $\gcd(f(x), g_{1}(x))=1$.

Next, we discuss the squarefree analogue of Turán’s conjecture. We refer to a polynomial $f(x)\in \mathbb Z[x]$ as squarefree if it has no multiple roots. For a positive integer n, let S_n denote the set of squarefree polynomials in V_n. Since $I_{n}\subset S_{n}$, it follows that the asymptotic density of squarefree polynomials in V_n is 1. Naturally, one is prompted to investigate the squarefree analogue Turán’s problem. Dubickas and Sha [4] were the first to study this problem. For a positive integer n, let D(n) denote the smallest positive integer such that given any $f(x)\in \mathbb Z[x]$ with ${\rm \deg}\text{ } f =n$, there is an $g(x)\in S_{n}$ with $L_{1}(f-g)\leqslant D(n)$. It is easily seen that $D(n)\leqslant C(n)$. Dubickas and Sha [4] conjecture that $D(n)\leqslant 2$. They further showed that $D(n)\geqslant 2$ for every $n\geqslant 15$ (in fact, their result is much more explicit). Thus, the conjectured value is $D(n)=2$. In some contrast to $C(n)\leqslant n+2$, Filaseta and Moy [7] have obtained the bound

\begin{equation*} D(n)\leqslant (\log n)^{2\log2 +\operatorname{\varepsilon}} \end{equation*}

for $n\gg_{\operatorname{\varepsilon}}1$. As a simple application of Theorem 1, we will establish that $D(n)\ll \log n$.

Theorem 2. For every $f(x)\in \mathbb F_{2}[x]$ of degree $n\gg 1$, there is a squarefree $g(x)\in 2[x]$ satisfying ${\rm \deg}\text{ } g = n$ and $L(f-g)\leqslant 6.7\log n$.

Arguing as we did to establish that $C(n)\leqslant C_{2}(n)+1$ above (in the case that ${\rm \deg}\text{ } g = n$), we obtain the following.

Corollary 1. For every $f(x)\in \mathbb Z[x]$ of degree $n\gg 1$, there is a squarefree $g(x)\in \mathbb Z[x]$ satisfying ${\rm \deg}\text{ } g = n$ and $L_{1}(f-g)\leqslant 1+ 6.7\log n \lt 6.8 \log n$.

The proof of Theorem 1 is based on a function field analogue of Brun–Hooley sieve (see Theorem 3, § 2). Although this is identical to the usual Brun–Hooley sieve in almost every aspect needing only minor adjustments, there is no evidence of a suitable reference in the existing literature. This prompted the authors to establish a function field analogue of the Brun–Hooley sieve in its full rigour. This is presented in § 2. For an exhaustive account of the usual Brun–Hooley sieve, the reader may refer to Halberstam–Richert [9] or Bateman–Diamond [3]. Apart from these references, the authors have found the nice exposition by Kevin Ford [8] particularly useful. For general arithmetic in function fields, we refer the reader to Rosen [10].

We clarify some of the basic notation to be followed in the remainder of the paper. Throughout, $\operatorname{\bf{A}}$ denotes the ring $ 2[x]$. The set of non-zero elements of $\operatorname{\bf{A}}$ will be denoted by $\operatorname{\bf{A}}^{\ast}$. Typically, in our proofs, we will use uppercase letters A, D, F and G to denote the elements of $\operatorname{\bf{A}}$ where $D\in \operatorname{\bf{A}}^{\ast}$, generally, will denote a divisor of some element in $\operatorname{\bf{A}}$. The letter P is reserved for a non-zero prime (irreducible) in $\operatorname{\bf{A}}$. Following [10], we define the norm $\lvert A\rvert$ of $A\in \operatorname{\bf{A}}^{\ast}$ as

\begin{equation*} \lvert A \rvert =2^{{\rm \deg}\text{ } A}. \end{equation*}

As it turns out, $\lvert A \rvert$ is the correct analogue for the size of an integer in $\mathbb Z$. Sometimes, for A and $A'$ in $\operatorname{\bf{A}}$, we will use $(A,A')$ to denote $\gcd(A,A')$. The function $\nu(A)$ will denote the number of distinct prime factors of $A\in \operatorname{\bf{A}}^{\ast}$ with $\nu(1)=0$. For a squarefree $A\in \operatorname{\bf{A}}^{\ast}$, the Möbius function $\mu(A)=(-1)^{\nu(A)}$. Otherwise, $\mu(A)=0$. For a real number x > 0, we will denote by $\log_{2} x$ the base-2 logarithm of x, and $\log x$ denotes the natural logarithm of x.

The paper is organized as follows. We develop the necessary technical details, namely the Brun–Hooley sieve for $\operatorname{\bf{A}}$, in § 2. Theorem 1 and Theorem 2 are respectively proved in § 3 and § 4.

2. Brun–Hooley sieve for $\mathbb F_{2}[x]$

Let $\mathcal A\subset \operatorname{\bf{A}}$ with $\#\mathcal A = X$. Let z be a real number satisfying $2\leqslant z\leqslant X$. Let

(2.1)\begin{equation} \mathscr P=\mathscr P(z):=\{P\in \operatorname{\bf{A}}^{\ast}\,\,\text{is prime}: \lvert P\rvert\leqslant z\}, \end{equation}

and define

(2.2)\begin{equation} \Pi=\Pi(z):=\prod_{P\in \mathscr P}P. \end{equation}

We fix a total order $\prec$ on $\operatorname{\bf{A}}$. For instance, for F and G in $\operatorname{\bf{A}}$, we say that $F\prec G$ if $F(2) \lt G(2)$ when F(x) and G(x) are considered as polynomials in $\mathbb R[x]$. Observe that F and G, when considered as polynomials in $\mathbb R[x]$, have coefficients in $\{0,1\}$, so that

\begin{equation*} F(2)\neq G(2) \quad \Longleftrightarrow \quad F(x)\neq G(x), \end{equation*}

as polynomials in $\mathbb R[x]$. Hence, if F ≠ G in $\operatorname{\bf{A}}$, then exactly one of $F\prec G$ and $G\prec F$ holds. It is easy to see that $\prec$ thus defined is a total order in $\operatorname{\bf{A}}$. In particular, every squarefree A ≠ 1 can be uniquely expressed as the product

\begin{equation*} A=P_{1}P_{2}\cdots P_{r}, \end{equation*}

where P ₁, P ₂, $\ldots$, P_r are primes in $\operatorname{\bf{A}}^{\ast}$ satisfying

\begin{equation*} P_{1}\prec P_{2}\prec \cdots \prec P_{r}. \end{equation*}

Additionally, for A as above, define $p^{-}(A)=P_{1}$ and $p^{+}(A)=P_{r}$. We also set $p^{-}(1)=1=p^{+}(1)$.

For each $D\in \operatorname{\bf{A}}^{\ast}$, let

\begin{equation*} \mathcal A_{D}:=\{A\in\mathcal A: D\mid A\}, \end{equation*}

with the understanding that $\mathcal A_{1}=\mathcal A$. We suppose that there is a real-valued function ω satisfying

(Ω)\begin{equation} \omega(1)=1, \quad 0\leqslant \omega(P)\leqslant 1 \end{equation}

for every prime $P\in \operatorname{\bf{A}}^{\ast}$. Next, extend ω multiplicatively to all of $\operatorname{\bf{A}}^{\ast}$ by defining

\begin{equation*} \omega(D):=\prod_{P\mid D}\omega(P). \end{equation*}

For a $D\in \operatorname{\bf{A}}^{\ast}$, we denote by r_D the quantity

\begin{equation*} r_{D}:=\#\mathcal A_{D} - \frac{\omega(D)}{\lvert D\rvert}X. \end{equation*}

We assume that

(r)\begin{equation} \vert r_{D}\rvert \leqslant \omega(D), \quad D\in \operatorname{\bf{A}}^{\ast}. \end{equation}

Further, define

(2.3)\begin{equation} W=W(z):=\prod_{P\in \mathscr P}\left(1-\frac{\omega(P)}{\lvert P\rvert}\right), \end{equation}

and let

\begin{equation*} S(\mathcal A; z):=\#\left\{A\in \mathcal A: (A, \Pi)=1\right\}. \end{equation*}

Our main result in this section is the following.

Theorem 3. (Brun–Hooley sieve for $ 2[x]$) Let $\mathcal A$, X, z, W and $S(\mathcal A;z)$ be as defined above. Let ω be a multiplicative function on $\operatorname{\bf{A}}^{\ast}$ satisfying (Ω) and (r). Then for $z\gg 1$, one has

1. (i) $S(\mathcal A;z) \geqslant 0.0001XW - z^{4.6385}$ and

2. (ii) $S(\mathcal A;z) \leqslant eXW + z^{3.6385}$.

The proof of the next lemma is identical to its integer counterpart.

Lemma 1. For every $A\in A^{\ast}$, one has

\begin{equation*} \sum_{D\mid A}\mu(D)= \begin{cases} 1 \quad &\text{if}\quad A=1\\ 0 \quad &\text{otherwise}. \end{cases} \end{equation*}

Lemma 2. Let $\mathfrak f$ be a real-valued multiplicative function defined on $\operatorname{\bf{A}}^{\ast}$, and let $A\in \operatorname{\bf{A}}^{\ast}$ be squarefree. Then for every integer $k\geqslant 0$, one has

\begin{equation*} \sum_{\substack{D\mid A\\ \nu(D)\leqslant k}}\mu(D)\mathfrak f(D)= \sum_{D\mid A}\mu(D)\mathfrak f(D) +(-1)^{k}\sum_{\substack{D\mid A\\ \nu(D)= k+1}}\mathfrak f(D) \prod_{\substack{P\in \mathscr P \\ P\prec p^{-}(D)}}(1-\mathfrak f(P)), \end{equation*}

where an empty product is equal to 1.

Proof. Consider the terms in the sum on the right corresponding to D with $\nu(D)\geqslant k+1$. Every such D can be uniquely expressed as

\begin{equation*} D=D_{1}D_{2}, \end{equation*}

where $\nu(D_{1})=k+1$, and D ₂ is either 1 or $p^{+}(D_{2})\prec p^{-}(D_{1})$. It follows that

\begin{align*} \sum_{D\mid A}\mu(D)\mathfrak f(D) - \sum_{\substack{D\mid A \\ \nu(D)\leqslant k}}\mu(D)\mathfrak f(D) &= \sum_{\substack{D\mid A \\ \nu(D)\geqslant k+1}}\mu(D)\mathfrak f(D)\\ &= \sum_{\substack{D_{1}\mid A \\ \nu(D_{1})= k+1}}\mu(D_{1})\mathfrak f(D_{1}) \sum_{\substack{D_{2}\mid A \\ p^{+}(D_{2})\prec p^{-}(D_{1})}}\mu(D_{2})\mathfrak f(D_{2})\\ &= (-1)^{k+1}\sum_{\substack{D\mid A \\ \nu(D)= k+1}}\mathfrak f(D)\prod_{\substack{P\in \mathscr P \\ P\prec p^{-}(D)}}(1-\mathfrak f(P)). \end{align*}

The lemma follows.

Corollary 2. Let $\mathfrak f$ be a multiplicative function defined on $\operatorname{\bf{A}}^{\ast}$ satisfying $0\leqslant \mathfrak f(P)\leqslant 1$ for every prime P, and let $A\in \operatorname{\bf{A}}^{\ast}$ be squarefree. Then for every even integer $k\geqslant 0$, one has

\begin{equation*} \sum_{D\mid A}\mu(D)\mathfrak f(D) \leqslant \sum_{\substack{D\mid A \\ \nu(D)\leqslant k}}\mu(D)\mathfrak f(D) \leqslant \sum_{D\mid A}\mu(D)\mathfrak f(D) +\sum_{\substack{D\mid A \\ \nu(D)= k+1}}\mathfrak f(D). \end{equation*}

Let $z\geqslant 2$ be as defined earlier, and let $2=z_{t+1} \lt z_{t} \lt \cdots \lt z_{1}=z$. Partition $\mathscr P=\mathscr P_{1} \cup \mathscr P_{2}\cup \cdots \cup \mathscr P_{t}$ such that if $P\in \mathscr P_{j}$, then $z_{j+1} \lt \lvert P\rvert \leqslant z_{j}$ if j < t and $z_{t+1}\leqslant \lvert P\rvert\leqslant z_{t}$ if j = t. Set

\begin{equation*} \Pi_{j}=\prod_{P\in \mathscr P_{j}}P, \end{equation*}

so that

\begin{equation*} \prod_{j=1}^{t}\Pi_{j}=\Pi. \end{equation*}

In proving Theorem 1, we will need both upper and lower bounds on $S(\mathcal A;z)$. As is usually the case, achieving a lower bound is relatively more difficult. We next embark on this pursuit. To this end, we begin with Hooley’s lemma (for proof, see Lemma 12.6, [3]), which is the key step in the usual Brun–Hooley lower bound sieve.

Lemma 3. Suppose that $0\leqslant x_{j}\leqslant y_{j}$ for $1\leqslant j \leqslant t$. Then one has

\begin{equation*} x_{1}x_{2}\cdots x_{t}=y_{1}y_{2}\cdots y_{t} - \sum_{\ell=1}^{t}(y_{\ell}-x_{\ell}) \prod_{\substack{j=1 \\ j\neq \ell}}^{t}y_{j}. \end{equation*}

Let k ₁, k ₂, $\ldots$, k_t be a sequence of even non-negative integers. For each $j\in \{1,2,\ldots, t\}$ and $A\in \mathcal A$, set

\begin{equation*} x_{j}=\sum_{D\mid (A, \Pi_{j})}\mu(D), \quad y_{j}= \sum_{\substack{D\mid (A, \Pi_{j}) \\ \nu(D)\leqslant k_{j}}}\mu(D). \end{equation*}

Setting $\mathfrak f\equiv 1$ and $A=(A, \Pi_{j})$ in Corollary 2, we find that $x_{j}\leqslant y_{j}$ for every j. Furthermore, since k_j is even, setting $\mathfrak f\equiv 1$ in Corollary 2 again, we get

\begin{equation*} y_{\ell}-x_{\ell}\leqslant \sum_{\substack{D\mid (A, \Pi_{\ell})\\ \nu(D)= k_{\ell}+1}}1. \end{equation*}

Thus, by Lemma 3, we have

\begin{align*} \sum_{D\mid(A, \Pi)}\mu(D) &\geqslant \prod_{j=1}^{t}\sum_{\substack{D\mid(A, \Pi_{j}) \\ \nu(D)\leqslant k_{j}}}\mu(D) -\sum_{\ell=1}^{t}\sum_{\substack{D\mid (A, \Pi_{\ell}) \\\nu(D)= k_{\ell}+1}}\left(\prod_{\substack{j=1\\ j\neq \ell}}^{t} \left( \sum_{\substack{D\mid (A, \Pi_{j}) \\ \nu(D)\leqslant k_{j}}}^{t}\mu(D)\right)\right)\\ &=\sum_{\substack{D_{1}, D_{2}, \ldots, D_{t} \\ D_{j}\mid (A,\Pi_{j}) \\ \nu(D_{j})\leqslant k_{j}}} \mu(D_{1}D_{2}\cdots D_{t}) -\sum_{\ell=1}^{t} \left( \sum_{\substack{D_{1}, D_{2}, \ldots, D_{t} \\ D_{j}\mid (A,\Pi_{j}) \\\nu(D_{j})\leqslant k_{j}, j\neq \ell \\ \nu(D_{\ell})=k_{\ell}+1}}\mu\left(\frac{D_{1}D_{2}\cdots D_{t}}{D_{\ell}}\right)\right). \end{align*}

Now, using Lemma 1 and the last lower bound above, we obtain

\begin{align*} S(\mathcal A; z)&=\sum_{A\in \mathcal A}\sum_{D\mid(A, \Pi)}\mu(D)\\ &\geqslant \sum_{A\in \mathcal A}\sum_{\substack{D_{1}, D_{2}, \ldots, D_{t} \\ D_{j}\mid (A,\Pi_{j}) \\ \nu(D_{j})\leqslant k_{j}}} \mu(D_{1}D_{2}\cdots D_{t}) - \sum_{A\in \mathcal A} \sum_{\ell=1}^{t} \left( \sum_{\substack{D_{1}, D_{2}, \ldots, D_{t} \\ D_{j}\mid (A,\Pi_{j}) \\\nu(D_{j})\leqslant k_{j}, j\neq \ell \\ \nu(D_{\ell})=k_{\ell}+1}}\mu\left(\frac{D_{1}D_{2}\cdots D_{t}}{D_{\ell}}\right)\right)\\ &=\sum_{\substack{D_{1}, D_{2}, \ldots, D_{t} \\ D_{j}\mid \Pi_{j} \\\nu(D_{j})\leqslant k_{j}}} \mu(D_{1}D_{2}\cdots D_{t})\#\mathcal A_{D_{1}D_{2}\cdots D_{t}}\\ &\quad\qquad - \sum_{\ell=1}^{t} \left( \sum_{\substack{D_{1}, D_{2}, \ldots, D_{t} \\ D_{j}\mid \Pi_{j} \\ \nu(D_{j})\leqslant k_{j}, j\neq \ell \\ \nu(D_{\ell})=k_{\ell}+1}}\mu\left(\frac{D_{1}D_{2}\cdots D_{t}}{D_{\ell}}\right) \#\mathcal A_{D_{1}D_{2}\cdots D_{t}}\right). \end{align*}

Setting above

\begin{equation*} \#\mathcal A_{D_{1}D_{2}\cdots D_{t}} =\frac{\omega(D_{1}D_{2}\cdots D_{t})}{\lvert D_{1}D_{2}\cdots D_{t}\rvert}X + r_{D_{1}D_{2}\cdots D_{t}}, \end{equation*}

we get

\begin{equation*} S(\mathcal A;z)\geqslant X\Sigma - R, \end{equation*}

where

(2.4)\begin{equation} \Sigma = \sum_{\substack{D_{1}, D_{2}, \ldots, D_{t} \\ D_{j}\mid \Pi_{j} \\ \nu(D_{j})\leqslant k_{j}}} \prod_{j=1}^{t}\mu(D_{j})\frac{\omega(D_{j})}{\lvert D_{j}\rvert} -\sum_{\ell=1}^{t} \left( \sum_{\substack{D_{1}, D_{2}, \ldots, D_{t} \\ D_{j}\mid \Pi_{j} \\\nu(D_{j})\leqslant k_{j}, j\neq \ell \\ \nu(D_{\ell})=k_{\ell}+1}}\frac{\omega(D_{\ell})}{\lvert D_{\ell}\rvert} \prod_{\substack{j=1 \\ j\neq \ell}}^{t}\mu(D_{j})\frac{\omega(D_{j})}{\lvert D_{j}\rvert}\right), \end{equation}

and

\begin{equation*} R=\sum_{\substack{D_{1}, D_{2}, \ldots, D_{t} \\ D_{j}\mid \Pi_{j} \\ \nu(D_{j})\leqslant k_{j}}}\lvert r_{D_{1}D_{2}\cdots D_{t}}\rvert + \sum_{\ell=1}^{t} \left( \sum_{\substack{D_{1}, D_{2}, \ldots, D_{t} \\ D_{j}\mid \Pi_{j} \\ \nu(D_{j})\leqslant k_{j}, j\neq \ell \\ \nu(D_{\ell})=k_{\ell}+1}} \lvert r_{D_{1}D_{2}\cdots D_{t}}\rvert\right). \end{equation*}

By assumptions (Ω) and (r), we have $\lvert r_{D}\rvert \leqslant \omega(D)\leqslant 1$. Therefore,

\begin{equation*} R\leqslant \sum_{\substack{D_{1}, D_{2}, \ldots, D_{t} \\ D_{j}\mid \Pi_{j} \\ \nu(D_{j})\leqslant k_{j}}} 1 + \sum_{\ell=1}^{t} \left( \sum_{\substack{D_{1}, D_{2}, \ldots, D_{t} \\ D_{j}\mid \Pi_{j} \\ \nu(D_{j})\leqslant k_{j}, j\neq \ell \\ \nu(D_{\ell})=k_{\ell}+1}} 1\right). \end{equation*}

The above sum is over all D ₁, D ₂, $\ldots$, D_t satisfying $D_{j}\mid \Pi_{j}$, and either $\nu(D_{j})\leqslant k_{j}$ for all j, or $\nu(D_{j})\leqslant k_{j}$ for all but one j for which $\nu(D_{j})=k_{j}+1$. This is bounded by

\begin{equation*} \sum_{\lvert D\rvert\leqslant z_{1}^{k_{1}+1}z_{2}^{k_{2}}\cdots z_{t}^{k_{t}}}\mu^{2}(D) \lt 2z_{1}^{k_{1}+1}z_{2}^{k_{2}}\cdots z_{t}^{k_{t}}. \end{equation*}

Thus,

(2.5)\begin{equation} R \lt Z:=2z_{1}^{k_{1}+1}z_{2}^{k_{2}}\cdots z_{t}^{k_{t}}. \end{equation}

Next, for each $j\in \{1,2,\ldots, t\}$, define

\begin{equation*} U_{j}:=\sum_{\substack{D\mid \Pi_{j} \\ \nu(D)\leqslant k_{j}}}\mu(D)\frac{\omega(D)}{\lvert D\rvert},\quad W_{j}:= \sum_{D\mid \Pi_{j}}\mu(D)\frac{\omega(D)}{\lvert D\rvert} =\prod_{P\in \mathscr P_{j}}\left(1-\frac{\omega(P)}{\lvert P\rvert}\right). \end{equation*}

Then

(2.6)\begin{equation} \sum_{\substack{D_{1}, D_{2}, \ldots, D_{t} \\ D_{j}\mid \Pi_{j} \\ \nu(D_{j})\leqslant k_{j}}} \prod_{j=1}^{t}\mu(D_{j})\frac{\omega(D_{j})}{\lvert D_{j}\rvert} =U_{1}U_{2}\cdots U_{t}, \end{equation}

and

(2.7)\begin{equation} \sum_{\ell=1}^{t} \left( \sum_{\substack{D_{1}, D_{2}, \ldots, D_{t} \\ D_{j}\mid \Pi_{j} \\ \nu(D_{j})\leqslant k_{j}, j\neq \ell \\ \nu(D_{\ell})=k_{\ell}+1}}\frac{\omega(D_{\ell})}{\lvert D_{\ell}\rvert} \prod_{\substack{j=1 \\ j\neq \ell}}^{t}\mu(D_{j})\frac{\omega(D_{j})}{\lvert D_{j}}\right) = U_{1}U_{2}\cdots U_{t}\sum_{\ell=1}^{t}\frac{1}{U_{\ell}} \sum_{\substack{D_{\ell}\mid \Pi_{\ell} \\ \nu(D_{\ell})=k_{\ell}+1}}\frac{\omega(D_{\ell})}{\lvert D_{\ell}\rvert}. \end{equation}

From Equations (2.4), (2.6) and (2.7), we have

(2.8)\begin{equation} \Sigma=U_{1}U_{2}\cdots U_{t}\left(1-\sum_{\ell=1}^{t}\frac{1}{U_{\ell}} \sum_{\substack{D_{\ell}\mid \Pi_{\ell} \\ \nu(D_{\ell})=k_{\ell}+1}} \frac{\omega(D_{\ell})}{\lvert D_{\ell}\rvert} \right). \end{equation}

By Corollary 2,

\begin{equation*} U_{j}\geqslant W_{j}, \quad j=1, 2,\cdots, t, \end{equation*}

so that

\begin{equation*} U_{1}U_{2}\cdots U_{t}\geqslant W_{1}W_{2}\cdots W_{t}:= W. \end{equation*}

Next, in order to estimate the expression following the negative sign in Equation (2.8), we will make use of the following lemma.

Lemma 4. We have

\begin{equation*} \sum_{\substack{D\mid \Pi_{\ell} \\ \nu(D)= k_{\ell}+1}} \frac{\omega(D)}{\lvert D\rvert} \leqslant \frac{I_{\ell}^{k_{\ell}+1}}{(k_{\ell}+1)!}, \end{equation*}

where

\begin{equation*} I_{\ell}=\log\frac{1}{W_{\ell}} =-\sum_{P\mid \Pi_{\ell}}\log\left(1-\frac{\omega(P)}{\lvert P\rvert}\right). \end{equation*}

Proof. Let $\mathscr P_{\ell}=\{P_{1}, P_{2}, \ldots, P_{T}\}$ with

\begin{equation*} P_{1}\prec P_{2}\prec \cdots\prec P_{T}. \end{equation*}

For $D\mid \Pi_{\ell}$, set $\mathfrak f(D)=\omega(D)/\lvert D\rvert$. Thus, $0\leqslant \mathfrak f(D) \lt 1$. By the multinomial theorem, we have

\begin{align*} \left(\sum_{P\in \mathscr P_{\ell}}\mathfrak f(P)\right)^{k_{\ell}+1} &=\sum_{\substack{m_{1}+m_{2}+\cdots +m_{T}=k_{\ell}+1 \\ m_{j}\geqslant 0}} \frac{(k_{\ell}+1)!}{m_{1}!m_{2}!\cdots m_{T}!}\prod_{j=1}^{T}\mathfrak f(P_{j})^{m_{j}}\\ & \gt (k_{\ell}+1)! \sum_{P_{e_{1}}\prec P_{e_{2}}\prec \cdots \prec P_{e_{k_{\ell}+1}}} \mathfrak f(P_{e_{1}})\mathfrak f(P_{e_{2}})\cdots \mathfrak f(P_{e_{k_{\ell}+1}})\\ & =(k_{\ell}+1)! \sum_{\substack{D\mid \Pi_{\ell} \\ \nu(D)= k_{\ell}+1}}\mathfrak f(D). \end{align*}

On the other hand, since $0\leqslant \mathfrak f(P) \lt 1$, we have

\begin{equation*} \sum_{P\in \mathscr P_{\ell}}\mathfrak f(P) \leqslant \sum_{P\in \mathscr P_{\ell}}-(\log(1-\mathfrak f(P))) = \log \frac{1}{W_{\ell}} = I_{\ell}. \end{equation*}

This finishes the proof of the lemma.

Now, by the estimate of Lemma 4, we have

\begin{equation*} \sum_{\substack{D\mid \Pi_{\ell} \\ \nu(D)= k_{\ell}+1}} \frac{\omega(D_{\ell})}{\lvert D_{\ell}\rvert} \leqslant W_{\ell}\left(\frac{W_{\ell}^{-1}I_{\ell}^{k_{\ell}+1}}{(k_{\ell}+1)!}\right) = W_{\ell}\left(\frac{e^{I_{\ell}}I_{\ell}^{k_{\ell}+1}}{(k_{\ell}+1)!}\right). \end{equation*}

Recalling that $U_{\ell}\geqslant W_{\ell}$, we get

\begin{equation*} \frac{1}{U_{\ell}}\sum_{\substack{d_{\ell}\mid \Pi_{\ell} \\ \nu(d_{\ell})=k_{\ell}+1}}\frac{\omega(D_{\ell})}{\lvert D_{\ell}\rvert} \leqslant \frac{e^{I_{\ell}}I_{\ell}^{k_{\ell}+1}}{(k_{\ell}+1)!}. \end{equation*}

Observe that if $k_{\ell}=0$ for some $\ell$, then $U_{\ell}=1$. Accordingly, in this case, the expression on the left side of the last display is then bounded by

\begin{equation*} W_{\ell}\left(\frac{e^{I_{\ell}}I_{\ell}^{k_{\ell}+1}}{(k_{\ell}+1)!}\right) =W_{\ell}e^{I_{\ell}}I_{\ell}=I_{\ell}. \end{equation*}

From these estimates, we deduce from Equation (2.8) that

(2.9)\begin{equation} \Sigma \geqslant \left(1-E\right)W,\quad E=\sum_{\ell=1}^{t}\frac{\psi(\ell)I_{\ell}^{k_{\ell}+1}}{(k_{\ell}+1)!}, \end{equation}

where

(2.10)\begin{equation} \psi(\ell)= \begin{cases} e^{I_{\ell}} \quad&\text{if} \quad k_{\ell}\neq 0\\[3pt] 1 \quad&\text{if} \quad k_{\ell}= 0. \end{cases} \end{equation}

As such,

(2.11)\begin{equation} S(\mathcal A; z)\geqslant X(1-E)W - Z, \end{equation}

where Z is as defined in Equation (2.5). Next, we obtain an upper bound on $S(\mathcal A;z)$. In this case, from Corollary 2, we have

\begin{equation*} \sum_{D\mid (a, \Pi)}\mu(D)=\prod_{j=1}^{t}\sum_{D_{j}\mid (a, \Pi_{j})}\mu(D_{j}) \leqslant \prod_{j=1}^{t}\sum_{\substack{D_{j}\mid (a, \Pi_{j}) \\ \nu(D_{j})\leqslant k_{j}}}\mu(D_{j}). \end{equation*}

Accordingly, we have, using Lemma 1, that

\begin{align*} S(\mathcal A; z)&=\sum_{A\in \mathcal A}\sum_{D\mid(A, \Pi)}\mu(D)\\ &\leqslant \sum_{A\in \mathcal A}\sum_{\substack{D_{1}, D_{2}, \ldots, D_{t} \\ D_{j}\mid (A,\Pi_{j}) \\ \nu(D_{j})\leqslant k_{j}}} \mu(D_{1}D_{2}\cdots D_{t})\\ &= \sum_{\substack{D_{1}, D_{2}, \ldots, D_{t} \\ D_{j}\mid \Pi_{j} \\ \nu(D_{j})\leqslant k_{j}}} \mu(D_{1}D_{2}\cdots D_{t})\#\mathcal A_{D_{1}D_{2}\cdots D_{t}}\\ &= X\Sigma+ R, \end{align*}

where

\begin{equation*} \Sigma = \sum_{\substack{D_{1}, D_{2}, \ldots, D_{t} \\ D_{j}\mid \Pi_{j} \\ \nu(D_{j})\leqslant k_{j}}} \prod_{j=1}^{t}\mu(D_{j})\frac{\omega(D_{j})}{\lvert D_{j}\rvert} =\prod_{j=1}^{t}\sum_{\substack{D\mid \Pi_{j} \\ \nu(D)\leqslant k_{j}}}\mu(D)\frac{\omega(D)}{\lvert D\rvert}, \end{equation*}

and

\begin{equation*} R= \sum_{\substack{D_{1}, D_{2}, \ldots, D_{t} \\ D_{j}\mid \Pi_{j} \\ \nu(D_{j})\leqslant k_{j}}} \mu(D_{1}D_{2}\cdots D_{t})r_{D_{1}D_{2}\cdots D_{t}}. \end{equation*}

Working as before,

\begin{equation*} |R|\leqslant \sum_{\substack{D_{1}, D_{2}, \ldots, D_{t} \\ D_{j}\mid \Pi_{j} \\ \nu(D_{j})\leqslant k_{j}}} 1 \leqslant 2z_{1}^{k_{1}}z_{2}^{k_{2}}\cdots z_{t}^{k_{t}} = \frac{Z}{z_{1}}=\frac{Z}{z}. \end{equation*}

Appealing again to Corollary 2, we have

\begin{align*} \sum_{\substack{D_{j}\mid \Pi_{j} \\ \nu(D_{j})\leqslant k_{j}}}\mu(D_{j})\frac{\omega(D_{j})}{\lvert D_{j}\rvert} &\leqslant \sum_{D_{j}\mid \Pi_{j}}\mu(D_{j})\frac{\omega(D_{j})}{\lvert D_{j}\rvert} +\sum_{\substack{D_{j}\mid \Pi_{j} \\ \nu(D_{j})= k_{j}+1}}\mu(D_{j})\frac{\omega(D_{j})}{\lvert D_{j}\rvert}\\ &=W_{j}+\sum_{\substack{D_{j}\mid \Pi_{j} \\ \nu(D_{j})= k_{j}+1}}\mu(D_{j})\frac{\omega(D_{j})}{\lvert D_{j}\rvert}. \end{align*}

Proceeding as in the proof of Lemma 4, we get

\begin{equation*} \sum_{\substack{D_{j}\mid \Pi_{j} \\ \nu(D_{j})= k_{j}+1}}\mu(D_{j})\frac{\omega(D_{j})}{\lvert D_{j}\rvert} \leqslant \frac{I_{j}^{k_{j}+1}}{(k_{j}+1)!}. \end{equation*}

Therefore,

\begin{equation*} \sum_{\substack{D_{j}\mid \Pi_{j} \\ \nu(D_{j})\leqslant k_{j}}}\mu(D_{j})\frac{\omega(D_{j})}{\lvert D_{j}\rvert} \leqslant W_{j}\left(1+ \frac{e^{I_{j}}I_{j}^{k_{j}+1}}{(k_{j}+1)!}\right). \end{equation*}

However, if $k_{j}=0$ for some j, then the left side of the last display is equal to 1, and consequently, it is bounded by $W_{j}(1+I_{j})$ since $W_{j}\geqslant 1$. Thus,

\begin{equation*} \Sigma\leqslant \prod_{j=1}^{t}W_{j}\left(1+ \frac{\psi(j)I_{j}^{k_{j}+1}}{(k_{j}+1)!}\right) \leqslant W \prod_{j=1}^{t}\exp\left( \frac{\psi(j)I_{j}^{k_{j}+1}}{(k_{j}+1)!}\right)=W\exp(E), \end{equation*}

where E and $\psi(j)$ are as defined by Equations (2.9) and (2.10), respectively. In conclusion,

(2.12)\begin{equation} S(\mathcal A;z)\leqslant XW\exp(E)+ \frac{Z}{z}, \end{equation}

where Z is as defined in Equation (2.5).

Next, we choose the parameters z ₂, z ₃, $\ldots$, z_t and k ₁, k ₂, $\ldots$, k_t optimally to obtain explicit upper and lower bounds on $S(\mathcal A;z)$ suitable for our purposes. Set c = 0.26249. For each $j\in \{1,2,\ldots, t\}$, set

\begin{equation*} \alpha_{j}=\exp\left(c(j-1)^{2}\right), \end{equation*}

and $z_{j}=z^{1/\alpha_{j}}$. Let t be the maximal positive integer such that

\begin{equation*} z^{1/\alpha_{t}} \gt 2. \end{equation*}

That is,

\begin{equation*} t=\left\lceil\sqrt{\frac{1}{c}\log\log_{2} z}\right\rceil, \end{equation*}

where, for a real number x, we denote by $\lceil{x}\rceil$, the integer m satisfying $m-1 \lt x \leqslant m$. Next, set $k_{j}=2(j-1)$. In order to make the bounds (2.11) and (2.12) explicit, we need to find suitable upper bounds on E and Z. To this end, we begin by estimating $I_{\ell}$.

Lemma 5. We have

\begin{equation*} I_{\ell}\le \begin{cases} \sum_{\log_{2} z_{\ell+1} \lt {\rm \deg}\text{ } P \leqslant \log_{2} z_{\ell}}\frac{1}{\lvert P\rvert} +\frac{1}{\lvert P\rvert^{2}}\quad &\text{if}\quad \ell \lt t\\[3pt] \sum_{1\leqslant {\rm \deg}\text{ } P \leqslant \log_{2} z_{\ell}}\frac{1}{\lvert P\rvert} +\frac{1}{\lvert P\rvert^{2}}\quad &\text{if}\quad \ell=t. \end{cases} \end{equation*}

Proof. Since $\lvert P\rvert \geqslant 2$ for every $P\in \mathscr P_{\ell}$, we have

\begin{equation*} \log \left(1-\frac{\omega(P)}{\lvert P\rvert}\right)^{-1} = \omega(P)\sum_{j=1}^{\infty}\frac{1}{j\lvert P\rvert^{j}} \leqslant \frac{1}{\lvert P\rvert} +\frac{1}{\lvert P\rvert^{2}}. \end{equation*}

The lemma follows after recalling the definition of $I_{\ell}$.

For an integer $d\geqslant 1$, recall that M_d, the number of irreducible polynomials in $\operatorname{\bf{A}}$ of degree d, satisfies $M_{d}\leqslant 2^{d}/d$. Since $z_{\ell+1}\geqslant 2$, it follows from Lemma 5 that for every $\ell \lt t$,

\begin{align*} I_{\ell}&\leqslant\sum_{\log_{2} z_{\ell+1} \lt d \leqslant \log_{2} z_{\ell}}\left(\frac{1}{d} +\frac{1}{d2^{d}}\right)\\[3pt] &\leqslant \log\frac{\alpha_{\ell+1}}{\alpha_{\ell}} +\sum_{\log_{2} z_{\ell+1} \lt d \leqslant \log_{2} z_{\ell}}\int_{0}^{1/2}x^{d-1}\,\mathrm{d}x \\[3pt] &\leqslant c(2\ell -1) +\sum_{\log_{2} z_{\ell+1} \lt d \leqslant \log_{2} z_{\ell}}\int_{0}^{1/2}x^{d-1}\,\mathrm{d}x. \end{align*}

We estimate the second sum above as follows. For $x\in (0,1/2]$, one has

\begin{equation*} \sum_{\log_{2} z_{\ell+1} \lt d \leqslant \log_{2} z_{\ell}} x^{d-1} \leqslant 2x^{\log_{2} z_{\ell+1}-1}. \end{equation*}

Thus,

\begin{align*} \sum_{\log_{2} z_{\ell+1} \lt d \leqslant \log_{2} z_{\ell}}\int_{0}^{1/2}x^{d-1}\,\mathrm{d}x &= \int_{0}^{1/2} \left(\sum_{\log_{2} z_{\ell+1} \lt d \leqslant \log_{2} z_{\ell}} x^{d-1}\right) \,\mathrm{d}x\\ &\leqslant 2\int_{0}^{1/2}x^{\log_{2} z_{\ell+1}-1} \,\mathrm{d}x\\ &= \frac{2}{z_{\ell+1}\log_{2} z_{\ell+1}}\\ & \leqslant \frac{2}{z_{\ell+1}}, \end{align*}

since $z_{\ell+1}\geqslant 2$. It follows that

(2.13)\begin{equation} I_{\ell} \leqslant c(2\ell -1) + \frac{2}{z_{\ell+1}}. \end{equation}

Working similarly, for $\ell=t$, we obtain from Lemma 5 that

\begin{align*} I_{t}&\leqslant \sum_{1\leqslant {\rm \deg}\text{ } P \leqslant \log_{2} z_{t}}\left(\frac{1}{\lvert P\rvert}+\frac{1}{\lvert P\rvert^{2}}\right)\\[3pt] & \leqslant \sum_{1\leqslant d \leqslant \frac{\log_{2} z}{\alpha_{t}}}\left(\frac{1}{d}+\frac{1}{d2^{d}}\right)\\[3pt] & \lt 2+ \left(\log\log_{2} z -\log \alpha_{t}\right)\\[3pt] &=2+ \left(\log \log_{2} z -c(t-1)^{2}\right). \end{align*}

Next, recall that

\begin{equation*} t=\left\lceil\sqrt{\frac{1}{c}\log\log_{2} z} \right\rceil \geqslant \sqrt{\frac{1}{c}\log\log_{2} z}, \end{equation*}

so that

\begin{equation*} ct^{2} \gt \log \log_{2} z. \end{equation*}

Using the last estimate, we deduce that

\begin{equation*} I_{t}\leqslant 2+ c(2t-1) \lt 0.27(2t-1), \end{equation*}

for $t\gg 1$. Thus, for $z\gg 1$ (so that $t\gg 1$), the contribution of $\ell=t$ in the sum for E in Equation (2.9) is bounded by

(2.14)\begin{equation} \frac{e^{0.27(2t-1)} \left(0.27(2t-1)\right)^{2t -1}}{(2t -1)!} \lt \left(0.27 e^{1.27}\right)^{2t-1} \lt (0.97)^{2t-1}, \end{equation}

where, we have used that $(2t-1)^{2t-1}/(2t-1)! \lt e^{2t-1}$.

We will next estimate E by separately considering the contributions from terms corresponding to $\ell \lt t$ for which $\alpha_{\ell+1}\leqslant \sqrt{\log z}$ and $\alpha_{\ell+1} \gt \sqrt{\log z}$. First, consider the case that $\alpha_{\ell+1}\leqslant \sqrt{\log z}$. In this case,

\begin{equation*} z_{\ell+1}=z^{1/\alpha_{\ell+1}}\geqslant z^{1/\sqrt{\log z}}=e^{\sqrt{\log z}}. \end{equation*}

Thus, from Equation (2.13) and the above, we get that

\begin{equation*} I_{\ell}\leqslant c(2\ell-1) +\frac{2}{e^{\sqrt{\log z}}}. \end{equation*}

Additionally, $\alpha_{\ell+1}\leqslant \sqrt{\log z}$ implies that $c\ell^{2}\leqslant (\log\log z)/2$. That is,

\begin{equation*} \ell \leqslant 1.5\sqrt{\log \log z}. \end{equation*}

Let ψ be as defined in Equation (2.10). Note that $\psi(1)=1$. For $1 \lt \ell\leqslant 1.5\sqrt{\log\log z}$ and for $z\gg 1$, using the estimates for $I_{\ell}$ from Equation (2.13), we have

\begin{align*} \frac{\psi(\ell)I_{\ell}^{2\ell-1}}{(2\ell-1)!} &\leqslant e^{2/\exp(\sqrt{\log z})} e^{c(2\ell -1)} \frac{\left(c(2\ell-1)+\frac{2}{e^{\sqrt{\log z}}}\right)^{2\ell -1}}{(2\ell-1)!}\\[3pt] &\leqslant e^{c(2\ell -1)}\left(1+O(e^{-\sqrt{(\log z)}})\right) \frac{\left((c(2\ell-1))^{2\ell-1}+(2\ell-1)^{2\ell-1}e^{-\sqrt{\log z}}3^{2\ell-1}\right)}{(2\ell-1)!}\\[3pt] &\leqslant e^{c(2\ell -1)}\left(1+O(e^{-\sqrt{(\log z)}})\right)\left(\frac{(c(2\ell-1))^{2\ell-1}}{(2\ell-1)!} +O(e^{3(2\ell-1)}e^{-\sqrt{\log z}})\right)\\[3pt] &= e^{c(2\ell -1)}\left(1+O(e^{-\sqrt{(\log z)}})\right)\left(\frac{(c(2\ell-1))^{2\ell-1}}{(2\ell-1)!} +O(e^{-\sqrt{\log z}/2})\right)\\[3pt] & = \frac{e^{c(2\ell -1)}(c(2\ell-1))^{2\ell-1}}{(2\ell-1)!} + O(e^{-\sqrt{\log z}/3}), \end{align*}

where, to obtain the bound in the second line above, we have used the binomial theorem as follows:

\begin{align*} \left(c(2\ell-1)+\frac{2}{e^{\sqrt{\log z}}}\right)^{2\ell -1} &\leqslant (c(2\ell-1))^{2\ell-1} +\sum_{j=1}^{2\ell-1}{2\ell -1 \choose j}(c(2\ell-1))^{2\ell-1-j} 2^{j}\\ & \lt (c(2\ell-1))^{2\ell-1} + (2\ell-1)^{2\ell-1}(2+c)^{2\ell-1}\\ & \lt (c(2\ell-1))^{2\ell-1} + (2\ell-1)^{2\ell-1}3^{2\ell-1}. \end{align*}

Thus, the contribution to the sum E from the terms corresponding to $\alpha_{\ell+1}\leqslant \sqrt{\log z}$ is bounded above by

(2.15)\begin{align} I_{1}&+\sum_{\ell \gt 1} \frac{e^{c(2\ell -1)}(c(2\ell-1))^{2\ell-1}}{(2\ell-1)!} +O(\sqrt{\log\log z}e^{-\sqrt{\log z}/3}) \\ & \lt c + \sum_{\ell \gt 1} \frac{e^{c(2\ell -1)}(c(2\ell-1))^{2\ell-1}}{(2\ell-1)!} + O(e^{-\sqrt{\log z}/4})\nonumber\\ & \lt 0.9997 + O(e^{-\sqrt{\log z}/4}).\nonumber \end{align}

Next, consider the case that $\alpha_{\ell+1} \gt \sqrt{\log z}$. In this case, $\ell \gt \sqrt{\log\log z}$. Since $z_{\ell+1}\geqslant 2$, for $\sqrt{\log\log z} \lt \ell \lt t$, we have from Equation (2.13) that

\begin{equation*} I_{\ell}\leqslant c(2\ell-1) +\frac{2}{z_{\ell+1}}\leqslant c(2\ell-1)+1, \end{equation*}

since $z_{\ell+1}\geqslant 2$. Thus, for $\ell$ as above and z sufficiently large, we have

\begin{align*} \frac{\psi(\ell)I_{\ell}^{2\ell-1}}{(2\ell-1)!} &\leqslant e^{c(2\ell-1)+1}\frac{(c(2\ell-1)+1)^{2\ell-1}}{(2\ell-1)!}\\[3pt] & \lt e^{0.27(2\ell-1)}\frac{(0.27(2\ell-1))^{2\ell-1}}{(2\ell-1)!}\\[3pt] & \lt (0.27e^{1.27})^{2\ell-1} \lt 0.97^{2\ell-1}. \end{align*}

Thus, the contribution to the sum E from the terms corresponding to the $\ell$ under consideration is less than

\begin{equation*} \sum_{\ell \gt \sqrt{\log\log z}}(0.97)^{2\ell-1}=O(0.97^{\sqrt{\log\log z}}). \end{equation*}

From the last estimate above and Equation (2.15), we deduce that

\begin{equation*} E \lt 0.9999 \end{equation*}

for $z\gg 1$.

It remains to estimate

\begin{equation*} Z:= 2z_{1}^{k_{1}+1}z_{2}^{k_{2}}\cdots z_{t}^{k_{t}} =2\exp\left(\log z\left(\frac{1}{\alpha_{1}}+\frac{2}{\alpha_{2}}+\cdots +\frac{2(t-1)}{\alpha_{t}}\right)\right). \end{equation*}

The exponent of z above is bounded by

\begin{equation*} 1+ \sum_{n=1}^{\infty}\frac{2n}{\exp\left({0.26249 n^{2}}\right)} \lt 4.63833. \end{equation*}

We now obtain (i) and (ii) of Theorem 3 by putting the estimates E < 0.9999 and $Z \lt z^{4.6385}$ (for $z\gg 1$) in Equations (2.11) and (2.12), respectively.

3. A proof of Theorem 1

Let f(x) and g(x) be as stated in Theorem 1 with ${\rm \deg}\text{ } f=n$. Let $t:=\lfloor 4.64\log_{2} n\rfloor$, and set $X:=2^{t}$. Observe that $t\leqslant 4.64\log_{2} n \lt 6.7\log n$. For future reference, we make a note of the fact that

\begin{equation*} n \lt 2^{\frac{t+1}{4.64}} \lt 2X^{\frac{1}{4.64}}. \end{equation*}

Let

\begin{equation*} \mathcal A:=\{g+u: u\in \operatorname{\bf{A}}, {\rm \deg}\text{ } u \lt t\}. \end{equation*}

Thus, $\#\mathcal A=X$. We will establish that for $n\gg 1$, there is some $g_{1}\in \mathcal A$ satisfying $\gcd(f,g_{1})=1$. If $g_{1}=g+u$, then

\begin{equation*} {\rm \deg}\text{ } g_{1}\leqslant \max\{{\rm \deg}\text{ } g, {\rm \deg}\text{ } u\}\leqslant \max\{{\rm \deg}\text{ } g, 6.7\log n\}, \end{equation*}

and

\begin{equation*} L(g-g_{1}) =L(u)\leqslant {\rm \deg}\text{ } u +1 \leqslant t \lt 6.7\log n, \end{equation*}

as is required to be shown.

Let $P\in \operatorname{\bf{A}}^{\ast}$ be irreducible. If $P\mid f$, and ${\rm \deg}\text{ } P \gt t$, then P divides at most one polynomial in $\mathcal A$. Thus, at most n polynomials in $\mathcal A$ have a common prime factor of degree greater than t with f.

For every irreducible $P\in \operatorname{\bf{A}}^{\ast}$ with ${\rm \deg}\text{ } P\leqslant t$, we define $\omega(P)=1$ if P divides some element of $\mathcal A$, and $\omega(P)=0$, otherwise. We extend ω multiplicatively to all of $\operatorname{\bf{A}}^{\ast}$ by defining

\begin{equation*} \omega(D):=\prod_{P\mid D}\omega(P), \quad D\in \operatorname{\bf{A}}^{\ast}. \end{equation*}

For $D\in \operatorname{\bf{A}}^{\ast}$, let

\begin{equation*} \mathcal A_{D}:= \{A\in \mathcal A: D\mid A\}. \end{equation*}

Observe that if ${\rm \deg}\text{ } D\leqslant t$, then $\omega(D)=1$ implies that

\begin{equation*} \#\mathcal A_{D}= 2^{t-{\rm \deg}\text{ } D}=\frac{\omega(D)}{\lvert D\rvert}X. \end{equation*}

If ${\rm \deg}\text{ } D \gt t$ and $\omega(D)=1$, then $\#\mathcal A_{D}=1$; while, $\omega(D)=0$ implies $\#\mathcal A_{D}=0$. Define

\begin{equation*} r_{D}:=\lvert \mathcal A_{D}\rvert - \frac{\omega(D)}{\lvert D\rvert}X. \end{equation*}

Then $r_{D}=0$ if either ${\rm \deg}\text{ } D\leqslant t$ or $\omega(D)=0$. If ${\rm \deg}\text{ } D \gt t$ and $\omega(D)=1$, then

\begin{equation*} r_{D}=1-2^{t-{\rm \deg}\text{ } D} \lt 1. \end{equation*}

Thus, in any case, $0\leqslant r_{D}\leqslant \omega(D)$. In particular, $\omega(D)$ and r_D satisfy (Ω) and (r). Let

\begin{equation*} \mathcal P_{f}=\{P\,\text{is irreducible}:P\mid f, \omega(P)=1\}, \end{equation*}

and

\begin{equation*} \Pi_{f}=\prod_{P\in \mathcal P_{f}} P. \end{equation*}

Note that ${\rm \deg}\text{ } \Pi_{f}\leqslant {\rm \deg}\text{ } f$, and if $A\in \mathcal A$, then $(f,A)=1$ if and only if $(A,\Pi_{f})=1$. So, without loss of any generality, we may and do assume that $f=\Pi_{f}$. Specifically, $\omega(P)=1$ for every $P\mid f$.

Next, set $z=X^{\frac{1}{4.64}}$ in Theorem 3. We have

\begin{equation*} z = 2^{\frac{t}{4.64}}=2^{\frac{\lfloor{4.64\log_{2} n}\rfloor}{4.64}}\leqslant n. \end{equation*}

Let $\mathscr P$, Π and W have the same meaning as implied in Equations (2.1), (2.2) and (2.3), respectively. Then the conclusion (i) of Theorem 3 implies that

(3.1)\begin{equation} S(\mathcal A; X^{\frac{1}{4.64}})\geqslant 0.0001XW - X^{\frac{4.6385}{4.64}}, \end{equation}

for $n\gg 1$. Let $\mathcal A'$ denote the set $\{A\in \mathcal A: (A, \Pi)=1\}$. Thus, the norm of each irreducible factor of every polynomial in $\mathcal A'$ is $\geqslant X^{\frac{1}{4.64}}$, and $\# \mathcal A'= S(\mathcal A; X^{\frac{1}{4.64}})$.

If $A\in \mathcal A'$ has a common prime factor P with f, then

\begin{equation*} {\rm \deg}\text{ } P\geqslant \log_{2} X^{\frac{1}{4.64}} =\frac{\log_{2} X}{4.64}. \end{equation*}

Let S ₁ denote the number of elements in $\mathcal A'$ that have a common prime factor of degree $\geqslant \frac{2\log_{2} X}{4.64}$ with f, and S ₂ the same for prime factors having degrees in $\left[\frac{\log_{2} X}{4.64}, \frac{2\log_{2} X}{4.64}\right)$. If n_d denotes the number of distinct irreducible factors of f of degree d, then

(3.2)\begin{align} S_{1}&\leqslant \sum_{\substack{{\rm \deg}\text{ } P\geqslant \frac{2\log_{2} X}{4.64} \\ P\mid f}}\#\mathcal A_{P}\\ \nonumber &= \sum_{\substack{\frac{2\log_{2} X}{4.64}\leqslant {\rm \deg}\text{ } P\leqslant t \\ P\mid f}}\#\mathcal A_{P} + \sum_{\substack{{\rm \deg}\text{ } P \gt t \\ P\mid f}}\#\mathcal A_{P}\\ \nonumber &\leqslant X\sum_{\substack{\frac{2\log_{2} X}{4.64}\leqslant {\rm \deg}\text{ } P \leqslant t \\ P\mid f}}\frac{1}{\lvert P\rvert} + n\\ \nonumber &\leqslant X\sum_{d\geqslant \frac{2\log_{2} X}{4.64}}\frac{n_{d}}{2^{d}} + n\\ \nonumber &\leqslant \frac{X}{2^{\frac{2\log_{2} X}{4.64}}}\sum_{d\geqslant \frac{2\log_{2} X}{4.64}}n_{d} +n\\ \nonumber &\leqslant X^{\frac{2.64}{4.64}}\frac{4.64n}{2\log_{2} X}+n\\ \nonumber & \lt \frac{4.64X^{\frac{3.64}{4.64}}}{\log_{2} X} +2X^{\frac{1}{4.64}} \lt \frac{5X^{\frac{3.64}{4.64}}}{\log_{2} X},\nonumber \end{align}

for $n\gg 1$.

We now turn to estimating S ₂. We begin by observing that

\begin{equation*} \frac{2\log_{2} X}{4.64} = \frac{2t}{4.64} \lt t, \end{equation*}

so that if ${\rm \deg}\text{ } P \lt \frac{2\log_{2} X}{4.64}$, then

\begin{equation*} \#\mathcal A_{P} =\frac{\omega(P)}{\lvert P\rvert}X. \end{equation*}

We will apply Theorem 3, (ii) to the sets $\mathcal A_{P}$ where P is a prime factor of f with ${\rm \deg}\text{ } P$ in $\left[\frac{\log_{2} X}{4.64}, \frac{2\log_{2} X}{4.64}\right)$. In what follows, we assume that $P\mid f$ with ${\rm \deg}\text{ } P\in \left[\frac{\log_{2} X}{4.64}, \frac{2\log_{2} X}{4.64}\right)$. Observe that for every P under consideration, we have $\omega(P)=1$ so that

\begin{equation*} \#\mathcal A_{P}=\frac{X}{\lvert P\rvert} \gt X^{\frac{2.64}{4.64}} \gt z. \end{equation*}

Let $\omega(D)$ be as defined earlier in this section. For $D\in \operatorname{\bf{A}}^{\ast}$, define

\begin{equation*} r'_{D}:=\#\mathcal A_{DP} -\frac{\omega(D)}{\lvert D\rvert}\#\mathcal A_{P} =\#\mathcal A_{DP}-\frac{\omega(D)}{\lvert D\rvert}\frac{X}{\lvert P\rvert}. \end{equation*}

If $P\mid D$, then $\omega(DP)=\omega(D)$ whence, $r'_{D}=r(DP)$. Next, consider that $P\nmid D$. If $\omega(D)=1$, then since $\omega(P)=1$, we have

\begin{equation*} \omega(DP)=\omega(D)\omega(P)=1=\omega(D). \end{equation*}

Conversely, if $\omega(DP)=1$, then obviously $\omega(D)=1$. It follows that $\omega(DP)=\omega(D)$, and as such,

\begin{equation*} r'_{D}=r_{DP}. \end{equation*}

Thus,

\begin{equation*} \lvert r'_{D}\rvert =\lvert r_{DP}\rvert \leqslant \omega(DP) = \omega(D). \end{equation*}

Thus, $\mathcal A_{P}$ and ω satisfy all the assumptions of Theorem 3. By Theorem 3 (ii), we now have for $n\gg 1$ that

\begin{equation*} S(\mathcal A_{P};X^{\frac{1}{4.64}})\leqslant e\frac{X}{\lvert P\rvert}W + X^{\frac{3.6385}{4.64}}. \end{equation*}

Since $\lvert P\rvert \gt 2^{\frac{\log_{2} X}{4.64}}$, hence

(3.3)\begin{equation} S(\mathcal A_{P};X^{\frac{1}{4.64}}) \leqslant eX^{\frac{3.64}{4.64}}W + X^{\frac{3.6385}{4.64}}. \end{equation}

Thus,

(3.4)\begin{align} S_{2}& = \sum_{\substack{P\mid f \\ \frac{\log_{2} X}{4.64}\leqslant {\rm \deg}\text{ } P \lt \frac{2\log_{2} X}{4.64}}} S(\mathcal A_{P};X^{\frac{1}{4.64}})\\ \nonumber & \leqslant \left(eX^{\frac{3.64}{4.64}}W + X^{\frac{3.6385}{4.64}}\right)\sum_{\substack{P\mid f \\ \frac{\log_{2} X}{4.64}\leqslant {\rm \deg}\text{ } P \lt \frac{2\log_{2} X}{4.64}}} 1\\ \nonumber & \leqslant \left(eX^{\frac{3.64}{4.64}}W + X^{\frac{3.6385}{4.64}}\right)\frac{4.64 n}{\log_{2} X}\\ \nonumber & \leqslant 10e\frac{XW}{\log_{2} X} + 10\frac{X^{\frac{4.6385}{4.64}}}{\log_{2} X}, \nonumber \end{align}

since $n \leqslant 2X^{\frac{1}{4.64}}$. Now, from Equations (3.2) and (3.4), we have

(3.5)\begin{equation} S_{1}+S_{2} \leqslant 10 e\frac{XW}{\log_{2} X} + 15\frac{X^{\frac{4.6385}{4.64}}}{\log_{2} X}. \end{equation}

If every polynomial in $\mathcal A'$ has a non-trivial gcd with f, then

\begin{equation*} S_{1}+S_{2}\geqslant \#\mathcal A' =S(\mathcal A; X^{\frac{1}{4.64}}). \end{equation*}

Substituting from Equations (3.1) and (3.5) in the last estimate above, we get

\begin{equation*} 10e\frac{XW}{\log_{2} X} + 15\frac{X^{\frac{4.6385}{4.64}}}{\log_{2} X} \geqslant 0.0001XW - X^{\frac{4.6385}{4.64}}. \end{equation*}

Rearranging terms, we have

(3.6)\begin{equation} XW\left(0.0001 - \frac{10e}{\log_{2} X}\right) \leqslant 16 X^{\frac{4.6385}{4.64}}. \end{equation}

Observe that

\begin{equation*} W\geqslant V:=\prod_{P\in \mathscr P}\left(1-\frac{1}{\lvert P \rvert}\right). \end{equation*}

Now, if M_d denotes the number of irreducible polynomials in $\operatorname{\bf{A}}$ of degree d, then

\begin{align*} -\log V&=\sum_{\substack{P-\text{a prime} \\ \lvert P \rvert\leqslant z}}-\log\left(1-\frac{1}{\lvert P \rvert}\right)\\ &=\sum_{\substack{P-\text{a prime} \\\lvert P \rvert\leqslant z}}\sum_{j=1}^{\infty}\frac{1}{j\lvert P \rvert^{j}}\\ &=\sum_{d\leqslant \log_{2} z}M_{d}\sum_{j=1}^{\infty}\frac{1}{j2^{dj}}. \end{align*}

Using an earlier estimate that $M_{d}\leqslant 2^{d}/d$, we get

\begin{align*} -\log V&\leqslant \sum_{d\leqslant \log_{2} z}\frac{2^{d}}{d}\sum_{j=1}^{\infty}\frac{1}{j2^{dj}}\\ &=\sum_{d\leqslant \log_{2} z} \frac{1}{d} + E', \end{align*}

where

\begin{align*} E'&= \sum_{d\leqslant \log_{2} z}\frac{2^{d}}{d}\sum_{j=2}^{\infty}\frac{1}{j2^{dj}}\\ & \lt \sum_{d\leqslant \log_{2} z}\frac{2^{d}}{2d}\sum_{j=2}^{\infty}\frac{1}{2^{dj}}\\ &=\sum_{d\le\log_{2} z} \frac{2^{d}}{2d}\frac{1}{2^{d}(2^{d}-1)}\\ & \lt \sum_{d\leqslant \log_{2} z} \frac{1}{d2^{d}} \lt 1. \end{align*}

Therefore,

\begin{equation*} -\log V \lt \sum_{d\leqslant \log_{2} z}\frac{1}{d} + 1 \lt \log(\log_{2} z) +2. \end{equation*}

Upon exponentiating, we get

\begin{equation*} V \gt \frac{1}{e^{2}\log_{2} z}=\frac{4.64}{e^{2}\log_{2} X} \gt \frac{0.6}{\log_{2} X}. \end{equation*}

Now, using the above estimate in Equation (3.6), we obtain

\begin{equation*} \frac{0.6X}{\log_{2} X}\left(0.0001 - \frac{10e}{\log_{2} X}\right) \leqslant 16 X^{\frac{4.6385}{4.64}}. \end{equation*}

The last inequality is impossible for $n\gg 1$ (whence $X\gg 1$). Therefore, for $n\gg 1$, there is an $g_{1}=g+u$ in $\mathcal A$ such that $\gcd(f,g_{1})=1$, as asserted. This concludes the proof of Theorem 1.

4. A proof of Theorem 2

Let $f(x)\in \mathbb{F}_{2}[x]$ with ${\rm \deg}\text{ } f = n$. There are unique polynomials $f_{e}(x)$ and $f_{o}(x)$ in $ 2[x]$ such that f(x) can be expressed as

\begin{equation*} f(x)=f_{e}(x^{2})+xf_{o}(x^{2}). \end{equation*}

Let $m:=\max\{{\rm \deg}\text{ } f_{e}, {\rm \deg}\text{ } f_{o}\}=\lfloor n/2\rfloor$. The proof of Theorem 2 rests upon the following result (Lemma 5.1) from [4] (also see Lemma 3.1, [7]).

Lemma 6. Let $h(x)\in \mathbb{F}_{2}[x]$ be of degree at least 2. Then h(x) is squarefree if and only if $\gcd(h_{e}(x), h_{o}(x))=1$.

Let $u(x)\in \{f_{e}(x), f_{o}(x)\}$ be defined as

\begin{equation*} u(x)= \begin{cases} f_{e}(x) \quad &\text{if}\quad {\rm \deg}\text{ } f \equiv 0\pmod{2}\\ f_{o}(x) \quad &\text{if}\quad {\rm \deg}\text{ } f \equiv 1\pmod{2}. \end{cases} \end{equation*}

Thus, ${\rm \deg}\text{ } u =m$. Let $v(x)\in \{f_{e}(x), f_{o}(x)\}$ denote the other polynomial. By Theorem 1, for $n\gg 1$, there is an $v_{1}(x)\in \mathbb{F}_{2}[x]$ with ${\rm \deg}\text{ } v_{1}\leqslant \max\{{\rm \deg}\text{ } v, 6.7\log n\}$ and $L(v-v_{1}) \lt 6.7\log m$ such that $\gcd(u(x), v_{1}(x))=1$. In particular, ${\rm \deg}\text{ } v_{1}\leqslant {\rm \deg}\text{ } v \leqslant {\rm \deg}\text{ } u =m$. Set

\begin{equation*} g(x)= \begin{cases} u(x^{2})+xv_{1}(x^{2}) \quad \text{if}\quad u(x)=f_{e}(x)\\ v_{1}(x^{2})+xu(x^{2}) \quad \text{if}\quad u(x)=f_{o}(x). \end{cases} \end{equation*}

Then g(x) is squarefree by Lemma 6. Furthermore,

\begin{equation*} L(f-g)=L(v-v_{1}) \lt 6.7\log m \lt 6.7\log n, \end{equation*}

as required. We conclude by clarifying that ${\rm \deg}\text{ } g ={\rm \deg}\text{ } f$. Assuming ${\rm \deg}\text{ } f = 2m$ is even, we have $u(x)=f_{e}(x)$ with ${\rm \deg}\text{ } f_{e}=m$. Furthermore, ${\rm \deg}\text{ } v \lt m$ in this case. Consequently ${\rm \deg}\text{ } v_{1} \lt m$ (for $n\gg 1$). It follows that

\begin{equation*} {\rm \deg}\text{ } g = \max\{2{\rm \deg}\text{ } u, 1+2{\rm \deg}\text{ } v_{1}\} = \max\{2m, 1+2{\rm \deg}\text{ } v_{1}\} = 2m. \end{equation*}

Similarly, if ${\rm \deg}\text{ } f$ is odd, say, ${\rm \deg}\text{ } f =2m +1$, then $u(x)=f_{o}(x)$ with ${\rm \deg}\text{ } f_{o}=m$. Then,

\begin{equation*} {\rm \deg}\text{ } g = \max\{2{\rm \deg}\text{ } v_{1}, 1+2{\rm \deg}\text{ } u\} = 2m+1 ={\rm \deg}\text{ } f. \end{equation*}