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.

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, [Reference Batemann and Diamond3]), 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 [Reference Dubickas and Sha4] (also see Lemma 3.1, [Reference Filaseta and Moy7]).

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*}