# Irreducibility of Random Polynomials of [X]

Pierre-Alexandre Bazin

► To cite this version:

Pierre-Alexandre Bazin. Irreducibility of Random Polynomials of [X]. International Mathematics Research Notices, 2025, 2025 (11), 10.1093/imrn/rnf136. hal-05179588

HAL Id: hal-05179588

https://hal.science/hal-05179588v1

Submitted on 23 Jul 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Irreducibility of random polynomials of $\mathbb{Z}[X]$

Pierre-Alexandre Bazin*

## Abstract

In [1], Bary-Soroker, Koukoulopoulos and Kozma proved that when A is a random monic polynomial of $\mathbb{Z}[X]$ of deterministic degree $n$ with coefficients $a_j$ drawn independently according to measures $\mu_j$, then A is irreducible with probability tending to 1 as $n \to \infty$ under a condition of near-uniformity of the $\mu_j$ modulo four primes (which notably happens when the $\mu_j$ are uniform over a segment of $\mathbb{Z}$ of length $N \ge 35$.) We improve here the speed of convergence when we have the near-uniformity condition modulo more primes. Notably, we obtain the optimal bound

$$P(A \text{ irreducible}) = 1 - O(1/\sqrt{n})$$

when we have near-uniformity modulo twelve primes, which notably happens when the $\mu_j$ are uniform over a segment of length $N \ge 10^8$.

# 1 Introduction

## 1.1 Main results

We consider A a random monic polynomial in $\mathbb{Z}[X]$ of determinisitic degree $n$ with independently chosen coefficients. Formally, we introduce measures $(\mu_j)_{0 \le j < n}$ on $\mathbb{Z}$ (generally taken all equal to the same measure $\mu$), and we define our random monic polynomial

$$A(X) = \sum_{j=0}^{n} a_j X^j \in \mathbb{Z}[X],$$

with $a_n = 1, a_j \sim \mu_j$ for all $j < n$ and the $a_j$ are independent.

When the $\mu_j$ are all taken equal to the same $\mu$ uniform over $\{0, 1\}$, the problem of the irreducibility of A when $n \to \infty$ has been first studied by Konyagin [5]. The latest results, given below, have been achieved by Bary-Soroker, Koukoulopoulos and Kozma [1].

**Theorem 1.1.1** (Bary-Soroker, Koukoulopoulos and Kozma [1]). Assume the $\mu_j$ are all the same and uniform over a segment $[a, a + N - 1]$ of length $N \ge 2$. Then there are absolute constants $c, K, \delta > 0$ such that when $n \ge (\log(a + N))^3$,

$$P(A \text{ has a factor of degree } \le cn) \le P(a_0 = 0) + Kn^{-\delta}.$$

When $N \ge 35$, we further get

$$P(A \text{ reducible}) \le P(a_0 = 0) + Kn^{-\delta}.$$

**Remark.** The $P(a_0 = 0)$ term corresponds to the probability that X divides A, which does not depend on $n$ (and is equal to 0 or $1/N$ depending on a).

Building on the ideas from this paper, we achieve a better convergence speed, namely

**Theorem 1.1.2.** Assume the $\mu_j$ are all the same and uniform over a segment $[a, a + N - 1]$ of length $N \ge 2$. Then there are absolute constants $c, K > 0$ such that when $n \ge (\log(|a| + N))^3$,

$$P(A \text{ has a factor of degree } \le cn) \le P(a_0 = 0) + K/\sqrt{n}.$$

When $N \ge 10^8$, we further get

$$P(A \text{ reducible}) \le P(a_0 = 0) + K/\sqrt{n}.$$

<footnote>*Université Paris Cité, Sorbonne Université, CNRS</footnote>

<footnote>Institut de Mathématiques de Jussieu-Paris Rive Gauche, 75013 Paris, France.</footnote>

<footnote>Email: bazin@imj-prg.fr</footnote>
The $O(1/\sqrt{n})$ bound here is optimal: indeed, $X+1$ divides $A$ with probability $P(A(-1) = 0)$, which decreases as $1/\sqrt{n}$ when $N$ is fixed. It can thus be useful to treat small cyclotomic factors (which, like $X+1$, have high probability of appearing) separately in order to obtain better convergence speeds. Indeed, Breuillard and Varjú [3] proved the following result assuming the Generalised Riemann Hypothesis (GRH) (their result is given for general measure $\mu$, but we specify it here for $\mu$ uniform over a segment).

**Theorem 1.1.3** (Breuillard and Varjú [3], Corollary 3). Assume GRH and assume the $\mu_j$ are all equal to the same measure $\mu$ of finite second moment, not supported on a singleton. Fix $C > 0$ and let $U_C$ the finite subset of $\mathbb{C}$ consisting of 0 and all roots of unity $\omega$ such that $[\mathbb{Q}(\omega) : \mathbb{Q}] < C$. Then for all $n$,

$$P(A \text{ reducible}) = P(\exists \omega \in U_C : A(\omega) = 0) + O_{\mu,C}(n^{-C/2}).$$

We used here the usual big-Oh notation: we write $f(n) = O_C(g(n))$ when $n \ge n_0$ if for some constant $K$ depending only on $C$, $|f(n)| \le K|g(n)|$ for all $n \ge n_0$. We will also note $f(n) = O(n^{C+o(1)})$ when $f(n) = O_\delta(n^{C+\delta})$ for all $\delta > 0$.

Without the Riemann hypothesis, we achieve here the same precision as Theorem 1.1.3 when $\mu$ is uniform over a segment large enough compared to $C$.

**Theorem 1.1.4.** Assume the $\mu_j$ are all the same and uniform over a segment $[a, a + N - 1]$ of length $N \ge 2$. Fix $C > 0$ and let $U_C$ the finite subset of $\mathbb{C}$ consisting of 0 and all roots of unity $\omega$ such that $[\mathbb{Q}(\omega) : \mathbb{Q}] < C$. We then have constants $\delta$ and $N_0$ depending only on $C$ such that when $n \ge (\log(|a| + N))^3$,

* when $N \ge N_0$, $P(A \text{ reducible}) = P(\exists \omega \in U_C : A(\omega) = 0) + O_C(n^{-C/2})$;

* in the general case $N \ge 2$, we only get

$$P(A \text{ has a factor of degree } \le \delta n) = P(\exists \omega \in U_C : A(\omega) = 0) + O_C(n^{-C/2}).$$

When $C = 0.01$, we can take $N_0 = 35$ which gives back Theorem 1.1.1 (and decreasing $C$ does not decrease $N_0$ further); when $C = 1$, we can take $N_0 = 10^8$. In general, values of $N_0$ are given by equation (11). Theorem 1.1.2 then immediately follows from Theorem 1.1.4 with $C = 1$.

## 1.2 A master theorem

We give the main result with general measures $\mu_j$, from which we will derive Theorem 1.1.4. We first recall a definition

**Definition 1.2.1.** For a measure $\mu$ on $\mathbb{Z}$, we note

$$\hat{\mu} : \theta \in \mathbb{R}/\mathbb{Z} \mapsto \mathbb{E}_{\mu} (e^{2i\pi\theta Y}) = \sum_{j \in \mathbb{Z}} \mu(j) e^{2i\pi\theta j}$$

its Fourier transform.

**Theorem 1.2.1.** Let $A$ a random monic polynomial of degree $n$ with independent coefficients following probability measures $\mu_j$ and $P = p_1 \dots p_r$ a product of $r \ge 4$ distinct primes.

Assume we can find an integer $s \ge 1$ (independent of $n$) such that for all $j$ and $Q, R, \ell$ with $QR = P, Q > 1$ and $\ell \in \mathbb{Z}/RZ$, we have

$$\sum_{k \in \mathbb{Z}/Q\mathbb{Z}} |\hat{\mu}_j(k/Q + \ell/R)|^s \le \left(1 - \frac{1}{\log n}\right) \sqrt{Q}. \quad (1)$$

Then when $n \ge P^4$ and $n_1 \le n/2s$, we have

$$P(\exists D | A \text{ of degree } \in [n_1, n/2s]) = O_{r,s} \left( n_1^{-rQ \left( \frac{1-1/r}{\log 2} \right) + o(1)} \right),$$

with $Q(t) := t \log t - t + 1 = \int_1^t \log u \, du$.

Bary-Soroker, Koukoulopoulos and Kozma [1, Theorem 7] obtained the same result with a bound $O_s(n^{-c})$; the key difference is that we are able to achieve an upper bound that scales with the number $r$ of primes that are considered.

Here, the condition (1) on the $\hat{\mu}_j$ translates to a kind of near-uniformity modulo $P$: indeed, the sum is minimised when $\mu$ is uniform mod $P$, in which case we have $|\hat{\mu}_j(a/P)| = 0$ for all $a \ne 0$ mod $P$. We will show in Section 3.2 that (1) is verified with $s = 1$ when the $\mu_j$ are uniform over a segment of length $N$ large enough in terms of $P$.

To prove Theorems 1.1.2 and 1.1.4 though, Theorem 1.2.1 is not sufficient: indeed, it only gives a useful bound when $n_1$ grows to infinity with $n$. Thus, we need to exclude the possibility of small degree factors separately. These have already been treated by Konyagin [5] for polynomials with coefficients in $\{0, 1\}$. In the more general setting of Theorem 1.1.4, we can use the result proved in [1, §7].
**Proposition 1.2.2** ([1], §7). Suppose all the $\mu_j$ have support in $[-H, H]$ for some $H > 0$, and do not take any value with probability higher than $1-c$ for some $c > 0$. Then for $n \ge (\log H)^3$,

$$ \mathbb{P}(A \text{ has a non-X, non-cyclotomic irreducible factor of degree } \le n^{1/10}) = O_c(e^{-\sqrt{n}}). $$

**Remark.** This result is not directly stated anywhere in [1], but appears in the proof of [1, proposition 2.1], which combines it with a weaker result on cyclotomic divisors. However, in order to achieve the better precision in Theorem 1.1.4 we need a stronger result on cyclotomic divisors, given below.

**Lemma 1.2.3.** Assume all the $\mu_j$ do not take any value with probability higher than $1-c$ for some $c > 0$. Then for $\Phi_d$ the $d$-th cycloctomic polynomial (of degree $\varphi(d)$), we have

$$ \mathbb{P}(\Phi_d|A) \le \left(\frac{Kn}{cd}\right)^{\varphi(d)/2} $$

for some absolute constant $K$.

**Remark.** When all $\mu_j$ are equal, this is [3, lemma 45] with a more precise dependence in $\mu$. The proof for general $\mu_j$ is given in Section 3.1.

Using Theorem 1.2.1 with $n_1 = n^{1/10}$ together with Proposition 1.2.2 is sufficient to prove Theorem 1.1.4, but does not give the best values of $N_0(C)$ (and, in particular, would only achieve a $O(n_1^{-1/2}) = O(n^{-1/20})$ error term when $\mu$ is uniform over a segment of length $N = 10^8$, instead of $O(n^{-1/2})$). The trick in order to achieve the better values of $N_0$ is to first use Theorem 1.2.1 with $n_1 = n^{1/10}$ and large values of $r$ and $s$ in order to rule out factors in $[n^{1/10}, \varepsilon n]$ for some $\varepsilon > 0$, and then use Theorem 1.2.1 again, this time with a smaller value of $r$ (for which we can take $s = 1$) together with $n_1 = \varepsilon n$ in order to rule out factors in $[\varepsilon n, n/2]$. The detailed argument is given in Section 3.2.

## 1.3 Definitions and notations

We now give definitions that will be useful for the proof of Theorem 1.2.1. When $p$ is a prime, we note $\mathbb{F}_p[X]^u$ the set of monic polynomials of $\mathbb{F}_p[X]$, and $\mathbb{F}_p[X]^u$ the set of monic polynomials of $\mathbb{F}_p[X]$ of degree $n$. We now fix $p_1, \dots, p_r$ distinct primes and define

$$ \mathcal{P} := \prod_{i=1}^{r} \mathbb{F}_{p_i}[X]^u $$

the set of $r$-uples of monic polynomials each in $\mathbb{F}_{p_i}[X]$. We then define multiplication and divisibility in $\mathcal{P}$ pointwise (that is, $\mathbf{D} = (D_1, \dots, D_r)$ divides $(A_1, \dots, A_r)$ if and only if each $D_i$ divides $A_i$ in $\mathbb{F}_{p_i}[X]$. As usual, we use **bold characters** to denote $r$-uples.

**Remark.** Here, we restricted ourselves to monic polynomials, as we are only interested in the multiplicative structure of $\mathcal{P}$.

For $\mathbf{A} = (A_1, \dots, A_r) \in \mathcal{P}$, we then define its degree $\deg \mathbf{A} := (\deg A_1, \dots, \deg A_r)$, and its total degree

$$ \mathrm{Deg} \mathbf{A} := \sum_{i=1}^{r} \deg A_i $$

as well as its norm

$$ \| \mathbf{A} \| := \prod_{i=1}^{r} p_i^{\deg A_i}. $$

For a fixed degree $\mathbf{d} = (d_1, \dots, d_r)$, we then define

$$ \mathcal{P}_{\mathbf{d}} := \prod_{i=1}^{r} \mathbb{F}_{p_i}[X]_{d_i}^{u} $$

the set of degree-$\mathbf{d}$ elements in $\mathcal{P}$. Notice all elements in $\mathcal{P}_{\mathbf{d}}$ have the same norm $\prod_i p_i^{d_i}$, which is also the cardinality of $\mathcal{P}_{\mathbf{d}}$.

Here, any element of $(\mathcal{P}, \cdot)$ can be uniquely factorised as a product of irreducibles, where an irreducible of $\mathcal{P}$ is an element of the form $(1, \dots, 1, I_i, 1, \dots, 1)$ with $I_i$ irreducible in $\mathbb{F}_{p_i}[X]$ (indeed, the factorisation is obtained
as the product of factorisations of each component). For $\mathbf{I}$ an irreducible of $\mathcal{P}$ and $\mathbf{A} \in \mathcal{P}$, we note $\nu_{\mathbf{I}}(\mathbf{A})$ the number of times $\mathbf{I}$ appears as a factor in $\mathbf{A}$. We also note

$$ \tau(\mathbf{A}) := \prod_{\mathbf{I} \text{ irreducible}} (\nu_{\mathbf{I}}(\mathbf{A}) + 1) $$

the number of divisors of $\mathbf{A}$ in $\mathcal{P}$.

We denote by

$$ \mathbf{X}_i = (1, \dots, 1, X \in \mathbb{F}_{p_i}[X], 1, \dots, 1) $$

the irreducible obtained for $I_i = X$ above. In particular, for any $i$, we have $\text{Deg} \mathbf{X}_i = 1$, $\|\mathbf{X}_i\| = p_i$, and $\mathbf{X}_i$ divides $\mathbf{B} \in \mathcal{P}$ if and only if $X$ divides $B_i$ in $\mathbb{F}_{p_i}[X]$. We note $\mathcal{P}^X$ (resp. $\mathcal{P}_d^X$) the set of elements of $\mathcal{P}$ (resp. $\mathcal{P}_d$) that are not divisible by any $\mathbf{X}_i$.

We give now a few more definitions.

**Definition 1.3.1.** Given $\mathbf{A} = (A_1, \dots, A_r)$ a random variable in $\mathcal{P}$, we define the discrepancy to uniformity modulo polynomials of degree $\le m$ of $\mathbf{A}$ by

$$ \Delta_{\mathbf{A}}(m) := \sum_{\substack{\mathbf{B} \in \mathcal{P}^X \\ \max \deg \mathbf{B} \le m}} \left| \mathbb{P}(\mathbf{B}|\mathbf{A}) - \frac{1}{\|\mathbf{B}\|} \right|. \quad (2) $$

Here, $\max \deg \mathbf{B}$ is the maximum of the $\deg B_i$ for $1 \le i \le r$.

**Remark.** We need to exclude here the factors $\mathbf{B}$ multiples of some $\mathbf{X}_i$ from the sum, as they would otherwise contribute too much when the $A_i$ are taken equal to $A \mod p_i$ where $A$ is the random polynomial from Theorem 1.2.1.

**Definition 1.3.2.** For a fixed degree $m \in \mathbb{N}$, we define $\mathcal{I}_m$ the set of irreducibles of $\mathcal{P}$ of degree $\le m$ and not of the form $\mathbf{X}_i$, and

$$ \Sigma_m := \sum_{\mathbf{I} \in \mathcal{I}_m} \frac{1}{\|\mathbf{I}\|}, $$

$$ \Pi_m := \prod_{\mathbf{I} \in \mathcal{I}_m} \left( 1 - \frac{1}{\|\mathbf{I}\|} \right). $$

For $\mathbf{A} \in \mathcal{P}$, we then define its m-friable part

$$ \mathbf{A}_{\le m} = \prod_{\mathbf{I} \in \mathcal{I}_m} \mathbf{I}^{\nu_{\mathbf{I}}(\mathbf{A})}, $$

and its m-sieved part

$$ \mathbf{A}_{>m} = \mathbf{A}/\mathbf{A}_{\le m} = \prod_{\mathbf{I} \notin \mathcal{I}_m} \mathbf{I}^{\nu_{\mathbf{I}}(\mathbf{A})}. $$

We say $\mathbf{A}$ is m-friable if $\mathbf{A} = \mathbf{A}_{\le m}$ (that is, all its irreducible factors are in $\mathcal{I}_m$).

Finally, when $\mathbf{A}$ is a random variable in $\mathcal{P}$, we define the event $\mathcal{E}_m$ "$\mathbf{A}$ does not have many factors of low degree" by

$$ \mathcal{E}_m := \left\{ \text{Deg} \mathbf{A}_{\le m} \le m(\Sigma_m - 2), \tau(\mathbf{A}_{\le m}) \le e^{(1-1/r)\Sigma_m} \right\}. \quad (3) $$

**Remark.** Here, we needed to exclude the $\mathbf{X}_i$ factors from the m-friable part as our bound on $\Delta_{\mathbf{A}}(m)$ gives no control over these.

## 1.4 Outline of the proof of Theorem 1.2.1

Our proof follows the ideas of Bary-Soroker, Koukouloopoulos and Kozma [1]. If $D$ is a factor of $A$ of degree $k$, this will also be true modulo any prime $p$. Thus, when we fix $p_1, \dots, p_r$ distinct primes and define

$$ \mathbf{A} = A_P := (A \mod p_i)_{1 \le i \le r} \in \mathcal{P}_{(n, \dots, n)}, $$

if $A$ has a factor $D$ of degree in $[n_1, n_2]$, then $\mathbf{A}$ has a factor $\mathbf{D} = D_P$ of degree $(k, \dots, k)$ for some $k \in [n_1, n_2]$.

We are thus interested in the presence of factors of degree $(k, \dots, k)$ of a random variable in $\mathcal{P}$. It is well known that the multiplicative structure of $\mathbb{F}_p[X]^u$ is analogous to that of integers, and $\mathcal{P}$ is a concatenation of $r$ spaces $\mathbb{F}_{p_i}[X]^u$. In the case of integers, Ford [4] achieved a precise estimate on the presence of factors in an interval $[2^k, 2^{k+1}]$ (which corresponds to degree $k$ in the polynomial-integer analogy):
**Theorem 1.4.1** (Ford, [4]). If a random integer taken uniformly in $[1, x]$ with $x \ge 2^{2k}$, then

$$ \mathbb{P}(a \text{ has a factor in } [2^k, 2^{k+1}]) \asymp k^{-Q(1/\log 2)}(\log k)^{-3/2}. $$

As we are only interested in a precision up to a $k^{o(1)}$ term in Theorem 1.2.1, we will not need such a precise result in $\mathcal{P}$. Still, this tells us we can expect a $O(k^{-rQ(1/\log 2)+o(1)})$ bound on $\mathbb{P}(\mathbf{A} \text{ has a factor of degree } (k, \dots, k))$ when $\mathbf{A}$ is uniform in $\mathcal{P}_{(n, \dots, n)}$ with $n \ge 2k$, which happens for $\mathbf{A} = A_P$ when the $\mu_j$ are uniform modulo $P = p_1 \dots p_r$. Here, we got an extra $r$ in the exponent of the bound as we want a factor modulo $r$ different primes. When $\mathbf{A}$ is not exactly uniform in $\mathcal{P}_{(n, \dots, n)}$, we will get an extra error term controlled by some $\Delta_{\mathbf{A}}(k + o(k))$.

Summing on $k$, we can then expect a $O(n_1^{1-rQ(1/\log 2)})$ bound on Theorem 1.2.1 when $r \ge \left\lfloor \frac{1}{Q(1/\log 2)} \right\rfloor = 12$. However, it turns out we do not need that many primes. Indeed, [2] and then [1] achieved a result with only $r = 4$ primes. We first explain the argument of Bary-Soroker, Koukoulopoulos and Kozma that allowed them to achieve this lower value of $r$, and then explain how we modify it to obtain better bounds for large values of $r$.

Pick $p$ a prime, $m \le k \le n/2$ and $A$ uniformly distributed in $\mathbb{F}_p[X]_n^u$. Then, conditionally on its $m$-friable part $A_{\le m}$, the expected number of factors of degree $k$ of $A$ is about $m^{-1}\tau(A_{\le m})$. The underlying reason for the proportionality with $\tau(A_{\le m})$ is that when $D$ is a factor of $A$, there are $\tau(A_{\le m})$ choices for $D_{\le m}$ (the contribution of the case $\deg A_{\le m} > k$ is negligible when $m$ is small enough - taking $m \ll k/\log k$ will be sufficient).

Now, note that $\tau(A_{\le m})$ behaves roughly like $2^W$ where $W$ follows a Poisson law of parameter $\log m$ (which corresponds to the behaviour of $\omega(A_{\le m})$). In particular, while the average value of $\tau(A_{\le m})$ is around $m$, its typical value is around $2^{\log m}$. This means, while the average number of factors of degree $k$ is one, there are very few polynomials (those with $\tau(A_{\le m}) \gg m$) which contribute mostly to that average, and the others are unlikely to have factors of degree $k$, for all $k \gg m^{1+\epsilon}$. In particular there is a significant overlap between the events "A has a factor of degree $k$" for all large $k$.

Bary-Soroker, Koukoulopoulos and Kozma [1] then considered $\mathbf{A} = (A_1, \dots, A_r) \in \mathcal{P}$ with $r \ge 4 > \frac{1}{1-1/\log 2}$ and a dyadic interval $[v, 2v]$ with $v \asymp m^{1+\epsilon}$, and considered two cases.

* Either one of the $A_j$ has more than $(\log m)^{\frac{1-1/r-\epsilon}{\log 2}}$ irreducible factors of degree $\le m$. This happens with probability $\ll m^{-2\epsilon} \ll v^{-\epsilon}$ when $\epsilon$ is small enough since $1 - 1/r > \log 2$.

* Or all of the $A_j$ have less than $(\log m)^{\frac{1-1/r-\epsilon}{\log 2}}$ irreducible factors of degree $\le m$. In that case, for all $k$ in $[v, 2v]$, the expected number of factors of $A_j$ of degree $k$ is $\le m^{-1}2^{(\log m)^{\frac{1-1/r-\epsilon}{\log 2}}} = m^{-1/r-\epsilon}$ (the case where $(A_j)_{\le m}$ is not squarefree does not significantly affect the computation). In particular, assuming all $A_j$ are independent, for fixed $k$ the probability that all $A_j$ have a factor of degree $k$ is $\le m^{-1-r\epsilon}$. Summing on $k \in [v, 2v]$ and since $v \asymp m^{1+\epsilon}$, we get that $\mathbf{A}$ has a factor of degree $(k, \dots, k)$ for some $k$ in $[v, 2v]$ with probability less than $v^{-\epsilon}$ in this case.

This proves $\mathbb{P}(\exists k \in [v, 2v], \mathbf{A} \text{ has a factor of degree } (k, \dots, k)) \ll v^{-\epsilon}$ when $r \ge 4$, which can then be summed on $v$. We now want to make the heuristic argument above more precise in order to achieve a bound $O(v^{-rQ(\frac{1-1/r}{\log 2})+o(1)})$ instead of $O(v^{-\epsilon})$.

First, we note that when all $A_j$ are independent, the expected number of factors of degree $(k, \dots, k)$ of $\mathbf{A}$ conditionally on $A_{\le m}$ is roughly

$$ \prod_{i=1}^{r} \mathbb{E} \left( \exists D_j \mid A_j \text{ of degree } k \mid (A_j)_{\le m} \right) \approx m^{-r} \tau(\mathbf{A}_{\le m}) $$

(the error terms will be precised later when proving Proposition 1.4.2), so that in order to bound the probability of the existence of factors of degree $(k, \dots, k)$ we in fact only need a bound on the average $\tau(\mathbf{A}_{\le m})$ rather than on all the $\tau((A_j)_{\le m})$. We now consider a range $[v, 2v]$ with $v = m^{1+o(1)}$, and estimate

$$ \begin{align*} \mathbb{P} \left( \exists \mathbf{D} \in \bigcup_{v \le k \le 2v} \mathcal{P}_{(k, \dots, k)}, \mathbf{D} | \mathbf{A} \right) &= \mathbb{E} \left( \mathbb{P} \left( \exists \mathbf{D} \in \bigcup_{v \le k \le 2v} \mathcal{P}_{(k, \dots, k)}, \mathbf{D} | \mathbf{A} \mid \mathbf{A}_{\le m} \right) \right) \\ &\le \mathbb{E} \left( \min \left\{ 1; \sum_{v \le k \le 2v} \mathbb{E} \left( \exists \mathbf{D} \in \mathcal{P}_{(k, \dots, k)}, \mathbf{D} | \mathbf{A} \mid \mathbf{A}_{\le m} \right) \right\} \right) \\ &\approx \mathbb{E} \left( \min \left\{ 1; vm^{-r} \tau(\mathbf{A}_{\le m}) \right\} \right) \\ &= v^{-rQ(\frac{1-1/r}{\log 2})+o(1)} \end{align*} $$
when $v = m^{1+o(1)}$ and $\tau(A_{\le m})$ behaves like $2^W$ with $W$ following a Poisson law of parameter $r \log m$.

For a general random variable $\mathbf{A}$ in $\mathcal{P}$, we prove in Section 2 the following result. This improves [1, proposition 2.2] by giving a bound that improves with the number $r$ of primes considered.

**Proposition 1.4.2.** Let $\mathbf{A}$ a random variable in $\mathcal{P}$ such that $\mathbb{P}(\mathbf{X}_i^{\nu}|\mathbf{A}) \le (1 - 1/L)^\nu$ for some $L$ and for all $i, \nu$. Then for $n_1 \le n_2$,

$$ \mathbb{P}\left(\exists \mathbf{D} \in \bigcup_{n_1 \le k \le n_2} \mathcal{P}_{(k, \dots, k)}, \mathbf{D}|\mathbf{A}\right) = O_r\left(L^r n_1^{-rQ\left(\frac{1-1/r}{\log 2}\right)+o(1)} + n_2^{5r} \Delta_{\mathbf{A}}\left(n_2 + n_2/(\log n_2)^3\right)\right). $$

In Proposition 1.4.2, we have an error term controlled by some $\Delta_{\mathbf{A}}(n_2 + o(n_2))$ (which does not control the factors that are multiples of the $\mathbf{X}_i$), and a separate condition on the $\mathbb{P}(\mathbf{X}_i^{\nu}|\mathbf{A})$. This is so that Proposition 1.4.2 can be applied when $\mathbf{A} = A_P = (A \operatorname{mod} p_i)_i$ with $A$ the random polynomial from Theorem 1.2.1. To bound the $\Delta_{\mathbf{A}}$ error term, we use the results obtained by Bary-Soroker, Koukoulopoulos and Kozma in [1, proposition 2.3], given below.

**Proposition 1.4.3** ([1], proposition 2.3). Let $A$ a random monic polynomial of degree $n$ with independent coefficients following probability measures $\mu_j$ and $P = p_1 \dots p_r$ a product of $r$ distinct primes, with $P \le n^{1/4}$. If $s \le \log n$ and $\gamma \ge 1/2$ are such that for all $j$ and $Q, R, \ell$ with $QR = P, Q > 1$ and $\ell \in \mathbb{Z}/RZ$, we have

$$ \sum_{k \in \mathbb{Z}/QZ} |\hat{\mu}_j(k/Q + \ell/R)|^s \le \left(1 - \frac{1}{\log n}\right) Q^{1-\gamma}, $$

then with $\mathbf{A} := (A \operatorname{mod} p_i)_{1 \le i \le r}$, we have

$$ \Delta_{\mathbf{A}}(\gamma n/s + n/(\log n)^3) \le e^{-n^{1/10}}. $$

**Remark.** The proposition 2.3 as written in [1] only bounds this error term for degree up to $\gamma n/s + n^{0.88}$; however, to obtain the constant $rQ(\frac{1-1/r}{\log 2})$ in Theorem 1.2.1, we need to go up to $\gamma n/s + n^{1-o(1)}$. To cover these higher degrees, notice the relevant bound at the end of the proof of [1, proposition 2.3] to cover degree $L = \gamma n/s + \varepsilon(n) > \gamma n/s$ is to have $P^{\varepsilon(n)} \alpha^{n/s}$ small enough, where $\alpha := 1 - 1/\log n$ is the term in front of $Q^{1-\gamma}$ in the condition on the $\hat{\mu}_j$ (which was taken equal to $1 - n^{-1/10}$ in [1]).

Here when $\varepsilon(n) \le n/(\log n)^3$ and $\alpha = 1 - 1/\log n$, we indeed have as $P \le n^{1/4}$ and $s \le \log n$,

$$ P^{\varepsilon(n)} \alpha^{n/s} \le e^{\frac{n \log P}{(\log n)^3} - \frac{n}{s \log n}} \le e^{-\frac{3}{4} \frac{n}{(\log n)^2}}, $$

hence our version of the proposition holds.

We can now prove Theorem 1.2.1 combining Propositions 1.4.2 and 1.4.3.

**Proof of Theorem 1.2.1.** Here, we can assume $n$ is large enough compared to $r$ and $s$, as the result for the smaller values of $n$ can be made trivial adjusting the implicit constant of the big-Oh term. As we also assumed $n \ge P^4$, Proposition 1.4.3 applies with $\gamma = 1/2$ and gives us with $n_2 := n/2s$,

$$ \Delta_{\mathbf{A}}(n_2 + n_2/(\log n_2)^3) \le \Delta_{\mathbf{A}}(n/2s + n/(\log n)^3) \le e^{-n^{1/10}} \le n^{-5r}, $$

where $\mathbf{A} = A_P = (A \operatorname{mod} p_i)_{1 \le i \le r}$.

Moreover, we have for all $i, \nu$, if the $a_j$ are the coefficients of $A$ (drawn independently according to the $\mu_j$),

$$ \mathbb{P}(\mathbf{X}_i^{\nu}|\mathbf{A}) = \prod_{0 \le j < \nu} \mathbb{P}(a_j \equiv 0 \operatorname{mod} p_i) \le (1 - 1/4s)^{\nu} $$

(see [1, relation (2.8)] for this bound on the $\mathbb{P}(a_j \equiv 0 \operatorname{mod} p_i)$ under the condition of Theorem 1.2.1 on the $\hat{\mu}_i$). Thus, we can apply Proposition 1.4.2 with $L = 4s$ to get

$$ \begin{aligned} \mathbb{P}(\exists D | A \text{ of degree } \in [n_1, n_2]) &\le \mathbb{P}(\exists \mathbf{D} | A \text{ of degree } (k, \dots, k) \text{ for some } k \in [n_1, n_2]) \\ &= O_r \left( s^r n_1^{-rQ\left(\frac{1-1/r}{\log 2}\right)+o(1)} + n_2^{5r} \Delta_{\mathbf{A}}\left(n_2 + n_2/(\log n_2)^3\right) \right) \\ &= O_{r,s} \left( n_1^{-rQ\left(\frac{1-1/r}{\log 2}\right)+o(1)} \right). \end{aligned} $$

□
**Remark.** Given Ford's result, we expect the estimate in Proposition 1.4.2 to be only an overestimate by a $n_1^{o(1)}$ factor when it comes to the main term. This means we cannot further reduce the number of primes $r$ (depending on $C$) required to obtain Theorem 1.1.4. Moving on to the dependency between $N_0$ and $P = p_1 \dots p_r$ given by equation (11), it likely cannot be improved by a lot either. Indeed, heuristically, when the coefficients of $A$ are drawn in a segment of length $N \le \sqrt{P}$ and $B$ has degree $n/2$ in each component, $A = A_P$ has only $N^n \le P^{n/2} = \|B\|$ possible values which means we cannot estimate $P(B|A)$ by $1/\|B\|$ and thus cannot control our error term $\Delta_A(n/2 + o(n))$.

## 2 Ruling out factors of degree $(k, \dots, k)$ in $\mathcal{P}$

We show $A \in \mathcal{P}$ is unlikely to have a factor of degree $(k, \dots, k)$ for some $k$ when the number of divisors of $A_{\le m}$ is low for some $m$ small compared to $k$.

**Proposition 2.0.1.** Let $m > 0$ and $v \ge 6m\Sigma_m$. Let $A$ a random variable in $\mathcal{P}$, and assume there is an $L > 0$ such that for all $i, v$, $P(X_i^v|A) \le (1 - 1/L)^v$. Then

$$ \mathbb{P}\left(\left(\exists \mathbf{D} \in \bigcup_{v \le k \le 2v} \mathcal{P}_{(k, \dots, k)}, \mathbf{D} | A\right) \cap \mathcal{E}_m\right) = O_r\left(\frac{v}{m}(L \log m)^r m^{-rQ(\frac{1-1/r}{\log 2})} + m^{5r}\Delta_A(2v + 5m\Sigma_m)\right), $$

where we recall $\mathcal{E}_m$ is defined by (3),

$$ \mathcal{E}_m := \{ \text{Deg} A_{\le m} \le m(\Sigma_m - 2), \tau(A_{\le m}) \le e^{(1-1/r)\Sigma_m} \}. $$

As the typical values of $\tau(A_{\le m})$ are concentrated around $2^{\Sigma_m}$, the $\mathcal{E}_m$ are unlikely when $r \ge 4 > \frac{1}{1-\log 2}$ and this will allow us to prove Proposition 1.4.2.

### 2.1 Preliminary results

We first estimate $\Sigma_m$ and $\Pi_m$ using the Prime Polynomial Theorem.

**Lemma 2.1.1.** We have $r(\log m - 2) \le \Sigma_m \le r(\log m + 1)$, and $\Pi_m \le e^{2r}m^{-r}$.

*Proof.* For any prime $p$, the Prime Polynomial Theorem gives the estimate

$$ p^k/k - 2p^{k/2}/k \le \#\{I \in \mathbb{F}_p[X] \text{ monic irreducible of degree } k\} \le p^k/k $$

on the number of irreducibles of degree $k$. We thus have

$$ \begin{aligned} \Sigma_m &= \sum_{i=1}^{r} \sum_{k=1}^{m} \frac{1}{p_i^k} \#\{I \in \mathbb{F}_{p_i}[X] \text{ monic irreducible of degree } k, I \neq X\} \\ &= \sum_{i=1}^{r} \sum_{k=1}^{m} \left( \frac{1}{k} - \varepsilon_{k,i} \right), \end{aligned} $$

with $0 \le \varepsilon_{k,i} \le 2p_i^{-k/2}/k \le p_i^{-k/2}$ when $k \ge 2$ and $\varepsilon_{1,i} = 1/p_i \le p_i^{-1/2}$ when $k = 1$ (here we treated separately $k = 1$ in order to exclude the polynomial $X$), so that

$$ 0 \le \sum_{i=1}^{r} \sum_{k=1}^{m} \varepsilon_{k,i} \le \sum_{i=1}^{r} \frac{1}{\sqrt{p_i} - 1} \le \frac{r}{\sqrt{2} - 1}. $$

As we always have $r(\log m + \gamma) \le \sum_i \sum_k \frac{1}{k} \le r(\log m + 1)$, we get

$$ r(\log m - 2) \le \Sigma_m \le r(\log m + 1). $$

Then we have

$$ \Pi_m \le \prod_{I \in \mathcal{I}_m} e^{-1/\|I\|} = e^{-\Sigma_m} \le e^{2r}m^{-r}. $$

We will then need a sieve lemma (similar to [1, lemma 8.2]) to estimate

$$ \mathbb{P}(\mathbf{D}|\mathbf{A}; (\mathbf{A}/\mathbf{D})_{\le m} = 1) = \mathbb{P}(\mathbf{D}_{>m}|\mathbf{A}; \mathbf{A}_{\le m} = \mathbf{D}_{\le m}) $$

with an error term depending on some $\|P(\mathbf{B}|\mathbf{A}) - \|\mathbf{B}\|^{-1}\|$ with $\mathbf{B}$ of small enough degree (so that it can be bounded by some $\Delta_A$ term).
**Lemma 2.1.2.** For any fixed $\mathbf{D} \in \mathcal{P}$, we have

$$ \mathbb{P}(\mathbf{D}|\mathbf{A}; (\mathbf{A}/\mathbf{D})_{\le m} = 1) \le 2 \cdot \frac{1}{\|\mathbf{D}\|} \Pi_m + \sum_{\substack{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_\ell \\ \ell \le 4\Sigma_m + 2}} \left| \mathbb{P}(\mathbf{D}\mathbf{G}|\mathbf{A}) - \frac{1}{\|\mathbf{D}\mathbf{G}\|} \right|, $$

where the sum is on all products $\mathbf{G}$ of $\ell \le 4\Sigma_m + 2$ distinct irreducible factors of $\mathcal{I}_m$ (notably, $\mathbf{G}$ will always have total degree $\le m(4\Sigma_m + 2)$).

*Proof.* By the inclusion-exclusion principle, we get

$$ \mathbb{1}_{\mathbf{D}|\mathbf{A}; (\mathbf{A}/\mathbf{D})_{\le m} = 1} = \sum_{J \subset \mathcal{I}_m} (-1)^{\#J} \mathbb{1}_{\mathbf{D} \cap \prod_{I \in J} \mathbf{I}|\mathbf{A}} = \sum_{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_\ell} (-1)^\ell \mathbb{1}_{\mathbf{D}\mathbf{G}|\mathbf{A}}. $$

This sum however includes some terms with $\mathbf{G}$ of very large degree (up to $m|\mathcal{I}_m|$). We thus need to cut the sum, using the fact that an inclusion-exclusion always oscillates between both sides of its final value as we add and subtract terms: thus, for any cutting point $\ell_0 \in \mathbb{N}$, we have

$$ \sum_{\substack{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_\ell \\ \ell \le 2\ell_0-1}} (-1)^\ell \mathbb{1}_{\mathbf{D}\mathbf{G}|\mathbf{A}} \le \mathbb{1}_{\mathbf{D}|\mathbf{A}; (\mathbf{A}/\mathbf{D})_{\le m} = 1} \le \sum_{\substack{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_\ell \\ \ell \le 2\ell_0}} (-1)^\ell \mathbb{1}_{\mathbf{D}\mathbf{G}|\mathbf{A}}. $$

We thus get

$$ \sum_{\substack{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_\ell \\ \ell \le 2\ell_0-1}} (-1)^\ell \mathbb{P}(\mathbf{D}\mathbf{G}|\mathbf{A}) \le \mathbb{P}(\mathbf{D}|\mathbf{A}; (\mathbf{A}/\mathbf{D})_{\le m} = 1) \le \sum_{\substack{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_\ell \\ \ell \le 2\ell_0}} (-1)^\ell \mathbb{P}(\mathbf{D}\mathbf{G}|\mathbf{A}), $$

and similarly

$$ \sum_{\substack{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_\ell \\ \ell \le 2\ell_0-1}} (-1)^\ell \frac{1}{\|\mathbf{D}\mathbf{G}\|} \le \frac{1}{\|\mathbf{D}\|} \Pi_m \le \sum_{\substack{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_\ell \\ \ell \le 2\ell_0}} (-1)^\ell \frac{1}{\|\mathbf{D}\mathbf{G}\|}. $$

We then get

$$ \begin{aligned} \mathbb{P}(\mathbf{D}|\mathbf{A}; (\mathbf{A}/\mathbf{D})_{\le m} = 1) &\le \sum_{\substack{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_\ell \\ \ell \le 2\ell_0}} (-1)^\ell \mathbb{P}(\mathbf{D}\mathbf{G}|\mathbf{A}) \\ &\le \sum_{\substack{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_\ell \\ \ell \le 2\ell_0}} (-1)^\ell \frac{1}{\|\mathbf{D}\mathbf{G}\|} + \sum_{\substack{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_\ell \\ \ell \le 2\ell_0}} \left| \mathbb{P}(\mathbf{D}\mathbf{G}|\mathbf{A}) - \frac{1}{\|\mathbf{D}\mathbf{G}\|} \right| \\ &\le \frac{1}{\|\mathbf{D}\|} \Pi_m + \sum_{\substack{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_\ell \\ \ell = 2\ell_0}} \frac{1}{\|\mathbf{D}\mathbf{G}\|} + \sum_{\substack{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_\ell \\ \ell \le 2\ell_0}} \left| \mathbb{P}(\mathbf{D}\mathbf{G}|\mathbf{A}) - \frac{1}{\|\mathbf{D}\mathbf{G}\|} \right| \\ &= \frac{1}{\|\mathbf{D}\|} \Pi_m + \frac{1}{\|\mathbf{D}\|} \sum_{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_{2\ell_0}} \frac{1}{\|\mathbf{G}\|} + \sum_{\substack{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_\ell \\ \ell \le 2\ell_0}} \left| \mathbb{P}(\mathbf{D}\mathbf{G}|\mathbf{A}) - \frac{1}{\|\mathbf{D}\mathbf{G}\|} \right|. \end{aligned} $$

To conclude, we then need to bound $S_{2\ell_0} := \sum_{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_{2\ell_0}} \frac{1}{\|\mathbf{G}\|}$ by $\Pi_m$ (where the sum is on products of $2\ell_0$ distinct irreducibles of $\mathcal{I}_m$) for $\ell_0 := \lceil 2\Sigma_m \rceil$. To do this, notice we have

$$ \Sigma_m^{2\ell_0} \ge (2\ell_0)! S_{2\ell_0} $$

(by developing the sum $\Sigma_m$ and keeping only the terms obtained by multiplying $2\ell_0$ distinct terms of the sum), so that

$$ \begin{aligned} S_{2\ell_0} &\le \frac{(\Sigma_m)^{2\ell_0}}{(2\ell_0)!} \le \frac{(\ell_0/2)^{2\ell_0}}{(2\ell_0)!} \le (e/4)^{2\ell_0} \le (e/4)^{4\Sigma_m} \\ &= \prod_{\mathbf{I} \in \mathcal{I}_m} (e/4)^{4/\|\mathbf{I}\|} \le \prod_{\mathbf{I} \in \mathcal{I}_m} (1 - 1/\|\mathbf{I}\|) = \Pi_m, \end{aligned} $$

as needed. $\square$

We also need a technical lemma of irrelevance of non-squarefree terms in $\mathcal{P}$ which will allow us to estimate the distribution of $\tau$.
**Lemma 2.1.3.** We have for all $t \in \mathbb{R}$,

$$S_t := \sum_{\mathbf{I} \in \mathcal{P}} \sum_{\text{irreducible } \nu \ge 2} \frac{(\nu + 1)^t}{\|\mathbf{I}\|^{\nu}} < \infty.$$

*Proof.* We have

$$\begin{align*}
\sum_{\mathbf{I} \in \mathcal{P}} \sum_{\text{irreducible } \nu \ge 2} \frac{(\nu + 1)^t}{\|\mathbf{I}\|^\nu} &= \sum_{i=1}^r \sum_{j=1}^\infty \sum_{\mathbf{I} \in \mathcal{F}_{p_i}[X]^u_j} \sum_{\text{irreducible } \nu \ge 2} \frac{(\nu + 1)^t}{p_i^{j\nu}} \\
&\le \sum_{i=1}^r \sum_{j=1}^\infty \sum_{\nu \ge 2} \frac{p_i^j (\nu + 1)^t}{j p_i^{j\nu}} \\
&\le r \sum_{\nu=2}^\infty \sum_{j=1}^\infty \frac{(\nu + 1)^t}{2^{j(\nu-1)}} \\
&\le r \sum_{\nu=2}^\infty \frac{(\nu + 1)^t}{2^{\nu-1} - 1} < \infty.
\end{align*}$$

□

## 2.2 Proof of Proposition 2.0.1

We first bound the probability of $\mathbf{A}$ having a factor of given degree $\mathbf{k} = (k_1, \dots, k_r)$ without a $\mathbf{X}_i$ factor when $\mathbf{A}_{\le m}$ is known. We recall the notation $\mathcal{P}_{\mathbf{k}}^X$ for the set of elements of $\mathcal{P}$ of degree $\mathbf{k}$ without any $\mathbf{X}_i$ factor.

**Lemma 2.2.1.** Let $m > 0$, $\mathbf{B}$ a $m$-friable element of $\mathcal{P}$ and $\mathbf{k} = (k_1, \dots, k_r)$ with

$$\min \mathbf{k} \ge \text{Deg} \mathbf{B} + m(4\Sigma_m + 2).$$

Then for $\mathbf{A}$ a random variable in $\mathcal{P}$, we have

$$\mathbb{P}((\exists \mathbf{D} \in \mathcal{P}_{\mathbf{k}}^X, \mathbf{D}|\mathbf{A}) \cap (\mathbf{A}_{\le m} = \mathbf{B})) \le \frac{4\Pi_m^2 \tau(\mathbf{B})}{\|\mathbf{B}\|} + R_{\mathbf{B}},$$

with an error term

$$R_{\mathbf{B}} := \sum_{\mathbf{F}|\mathbf{B}} \sum_{\mathbf{E} \in \mathcal{P}_{\mathbf{k}-\text{deg}\mathbf{F}}^X} \sum_{\substack{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_\ell \\ \ell < 4\Sigma_m + 2 \\ \mathbf{I}_j \in \mathcal{I}_m \text{ distinct}}} \left| \mathbb{P}(\mathbf{B}\mathbf{E}|\mathbf{A}) - \frac{1}{\|\mathbf{B}\mathbf{E}\|} \right|.$$

*Proof.* We use the fact that when $\mathbf{B}$ has few factors, there are few choices of $\mathbf{D}_{\le m}$ for $\mathbf{D}$ dividing $\mathbf{A}$, as $\mathbf{D}_{\le m}$ must then divide $\mathbf{B} = \mathbf{A}_{\le m}$. We thus write

$$\begin{align}
\mathbb{P}((\exists \mathbf{D} \in \mathcal{P}_{\mathbf{k}}^X, \mathbf{D}|\mathbf{A}) \cap (\mathbf{A}_{\le m} = \mathbf{B})) &\le \sum_{\mathbf{D} \in \mathcal{P}_{\mathbf{k}}^X} \mathbb{P}(\mathbf{D}|\mathbf{A} \cap (\mathbf{A}_{\le m} = \mathbf{B})) \nonumber \\
&= \sum_{\mathbf{F}|\mathbf{B}} \sum_{\substack{\mathbf{E} \in \mathcal{P}_{\mathbf{k}-\text{deg}\mathbf{F}}^X \\ \mathbf{E}_{\le m} = 1}} \mathbb{P}(\mathbf{E}|\mathbf{A} \cap (\mathbf{A}_{\le m} = \mathbf{B})) \nonumber \\
&\le \sum_{\mathbf{F}|\mathbf{B}} \sum_{\substack{\mathbf{E} \in \mathcal{P}_{\mathbf{k}-\text{deg}\mathbf{F}}^X \\ \mathbf{E}_{\le m} = 1}} \frac{2\Pi_m}{\|\mathbf{B}\mathbf{E}\|} + R_{\mathbf{B}}, \tag{4}
\end{align}$$

where we introduced the change of variable $\mathbf{F} = \mathbf{D}_{\le m}; \mathbf{E} = \mathbf{D}_{\ge m}$ and then used Lemma 2.1.2 to bound $\mathbb{P}(\mathbf{E}|\mathbf{A} \cap (\mathbf{A}_{\le m} = \mathbf{B})) = \mathbb{P}(\mathbf{B}\mathbf{E}|\mathbf{A} \cap [(\mathbf{A}/\mathbf{B}\mathbf{E})_{\le m} = 1])$ which gives the error term $R_{\mathbf{B}}$.

To bound the main term, note that for any $\mathbf{F}$ dividing $\mathbf{B}$, if $\mathbb{P}_0$ uniform on $\mathcal{P}_{\mathbf{k}-\text{deg}\mathbf{F}}$, Lemma 2.1.2 gives us

$$\sum_{\substack{\mathbf{E} \in \mathcal{P}_{\mathbf{k}-\text{deg}\mathbf{F}} \\ \mathbf{E}_{\le m} = 1}} \frac{1}{\|\mathbf{E}\|} = \mathbb{P}_0(\mathbf{E}_{\le m} = 1) \le 2\Pi_m + \sum_{\substack{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_\ell \\ \ell < 4\Sigma_m + 2 \\ \mathbf{I}_j \in \mathcal{I}_m \text{ distinct}}} \left| \mathbb{P}_0(\mathbf{G}|\mathbf{E}) - \frac{1}{\|\mathbf{G}\|} \right|. \quad (5)$$

However, when $\mathbf{G} = \mathbf{I}_1 \dots \mathbf{I}_\ell$ is a product of $\ell \le 4\Sigma_m + 2$ distinct factors of $\mathcal{I}_m$, we have

$$\max \text{deg} \mathbf{G} \le m\ell \le \min \mathbf{k} - \text{Deg} \mathbf{B} \le \min(\mathbf{k} - \text{deg} \mathbf{F})$$
(as we assumed $\min \mathbf{k} \ge \text{Deg} \mathbf{B} + m(4\Sigma_m + 2)$), so that $\mathbb{P}_0(\mathbf{G}|\mathbf{E}) = 1/\|\mathbf{G}\|$ for all these $G$ and (5) becomes

$$ \sum_{\substack{\mathbf{E} \in \mathcal{P}_{\mathbf{k}-\text{deg} \mathbf{F}} \\ \mathbf{E}_{\le m} = 1}} \frac{1}{\|\mathbf{E}\|} = \mathbb{P}_0(\mathbf{E}_{\le m} = 1) \le 2\Pi_m. $$

Coming back to (4), we then have

$$ \begin{aligned} \mathbb{P}((\exists \mathbf{D} \in \mathcal{P}_{\mathbf{k}}^X, \mathbf{D}|\mathbf{A}) \cap (\mathbf{A}_{\le m} = \mathbf{B})) &\le \sum_{\mathbf{F}|\mathbf{B}} \sum_{\substack{\mathbf{E}=\mathbf{k}-\text{deg} \mathbf{F} \\ \mathbf{E}_{\le m} = 1}} \frac{2\Pi_m}{\|\mathbf{B}\|} + R_{\mathbf{B}} \\ &\le \sum_{\mathbf{F}|\mathbf{B}} \frac{4\Pi_m^2}{\|\mathbf{B}\|} + R_{\mathbf{B}} \\ &= \frac{4\Pi_m^2 \tau(\mathbf{B})}{\|\mathbf{B}\|} + R_{\mathbf{B}}. \end{aligned} $$

□

We can now move on to the proof of Proposition 2.0.1.

**Proof of Proposition 2.0.1.** Our assumptions tell us for all $i$, $\mathbb{P}(\mathbf{X}_i^{[L\Sigma_m]}|\mathbf{A}) \le (1-1/L)^{L\Sigma_m} \le e^{-\Sigma_m}$ so that

$$ \mathbb{P}(\exists i, \mathbf{X}_i^{[L\Sigma_m]}|\mathbf{A}) \le r e^{-\Sigma_m}. $$

We now consider the case where $\mathbf{X}_i^{[L\Sigma_m]}$ does not divide $\mathbf{A}$ for any $i$. Then, if $\mathbf{D}$ is a factor of $\mathbf{A}$ of degree $(k, \dots, k)$ for some $k \in [v, 2v]$, defining $\mathbf{D}_X := \prod_i \mathbf{X}_i^{\nu_{\mathbf{x}_i}(\mathbf{D})}$ and $\ell = \text{deg} \mathbf{D}_X$, we get $\max \ell < L\Sigma_m$ (as $\mathbf{D}_X$ divides $\mathbf{A}$) and $\mathbf{D}/\mathbf{D}_X$ is a factor of $\mathbf{A}$ of degree $\mathbf{k}' = (k - \ell_1, \dots, k - \ell_r)$ without any $\mathbf{X}_i$ factor. Let

$$ K = \{\mathbf{k} = (k_1, \dots, k_r), \min \mathbf{k} > v - L\Sigma_m, \max \mathbf{k} \le 2v, \max \mathbf{k} - \min \mathbf{k} < L\Sigma_m\} $$

the set of such possible $\mathbf{k}'$, of cardinality $\le (v + L\Sigma_m)(L\Sigma_m)^r$.

When $m > L$, $\mathbf{k} \in K$ and $\mathbf{B}$ is a $m$-friable element of $\mathcal{E}_m$, we always have $\text{Deg} \mathbf{B} = \text{Deg} \mathbf{B}_{\le m} \le m(\Sigma_m - 2)$, so that

$$ \min \mathbf{k} \ge v - L\Sigma_m \ge 5m\Sigma_m \ge \text{Deg} \mathbf{B} + m(4\Sigma_m + 2) $$

and Lemma 2.2.1 applies. We thus have

$$ \begin{aligned} & \mathbb{P}\left(\left(\exists \mathbf{D} \in \bigcup_{v \le k \le 2v} \mathcal{P}_{(k, \dots, k)}, \mathbf{D}|\mathbf{A}\right) \cap \mathcal{E}_m\right) \\ &\le \sum_{\mathbf{k} \in K} \sum_{\substack{\mathbf{B}=\mathbf{B}_{\le m} \\ \mathbf{B} \in \mathcal{E}_m}} \mathbb{P}((\exists \mathbf{D} \in \mathcal{P}_{\mathbf{k}}^X, \mathbf{D}|\mathbf{A}) \cap (\mathbf{A}_{\le m} = \mathbf{B})) + \mathbb{P}(\exists i, \mathbf{X}_i^{[L\Sigma_m]}|\mathbf{A}) \\ &\le \#K \cdot \sum_{\substack{\mathbf{B}=\mathbf{B}_{\le m} \\ \tau(\mathbf{B}) \le e^{(1-1/r)\Sigma_m}}} \frac{4\Pi_m^2 \tau(\mathbf{B})}{\|\mathbf{B}\|} + R + r e^{-\Sigma_m}, \end{aligned} \quad (6) $$

with an error term coming from Lemma 2.2.1

$$ R := \sum_{\substack{\mathbf{B}=\mathbf{B}_{\le m} \\ \mathbf{B} \in \mathcal{E}_m}} R_{\mathbf{B}} = \sum_{\substack{\mathbf{B}=\mathbf{B}_{\le m} \\ \mathbf{B} \in \mathcal{E}_m}} \sum_{\mathbf{F}|\mathbf{B}} \sum_{\mathbf{k} \in K} \sum_{\substack{\mathbf{E} \in \mathcal{P}_{\mathbf{k}-\text{deg} \mathbf{F}}^X \\ \mathbf{E}_{\le m} = 1}} \sum_{\substack{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_\ell \\ \ell < 4\Sigma_m + 2 \\ \mathbf{I}_j \in \overline{\mathcal{I}}_m \text{ distinct}}} \left| \mathbb{P}(\mathbf{B}\mathbf{E}\mathbf{G}|\mathbf{A}) - \frac{1}{\|\mathbf{B}\|} \right|. $$
To bound the main term, we use Rankin's trick. We have for all $t > 0$,

$$
\begin{align*}
\sum_{\substack{\mathbf{B}=\mathbf{B}_{\le m} \\ \tau(\mathbf{B}) \le e^{(1-1/r)\Sigma_m}}} \frac{\tau(\mathbf{B})}{\|\mathbf{B}\|} &\le \sum_{\mathbf{B}=\mathbf{B}_{\le m}} \frac{\tau(\mathbf{B})^{1-t} e^{(1-1/r)\Sigma_m t}}{\|\mathbf{B}\|} \\
&= e^{(1-1/r)\Sigma_m t} \prod_{\mathbf{I} \in \mathcal{I}_m} \sum_{\nu \ge 0} \frac{(\nu+1)^{1-t}}{\|\mathbf{I}\|^\nu} \\
&\le \exp\left( (1-1/r)\Sigma_m t + \sum_{\mathbf{I} \in \mathcal{I}_m} \sum_{\nu \ge 1} \frac{(\nu+1)^{1-t}}{\|\mathbf{I}\|^\nu} \right) \\
&\le e^{(1-1/r)\Sigma_m t + 2^{1-t}\Sigma_m + S_{1-t}} = O_{r,t} \left( e^{((1-1/r)t + 2^{1-t})\Sigma_m} \right)
\end{align*}
$$

(where $S_{1-t}$ comes from Lemma 2.1.3 and depends only on $r$ and $t$.)

Picking the optimal $t := 1 - (\log \frac{1-1/r}{\log 2}) / \log 2$, we get (as $t$ depends only on $r$)

$$
\sum_{\substack{\mathbf{B}=\mathbf{B}_{\le m} \\ \tau(\mathbf{B}) \le e^{(1-1/r)\Sigma_m}}} \frac{\tau(\mathbf{B})}{\|\mathbf{B}\|} = O_r \left( e^{\Sigma_m [2-2Q(\frac{1-1/r}{2\log 2})]} \right). \quad (7)
$$

To bound the error term $R$, we regroup based on the value of $\mathbf{C} = \mathbf{BEG}$, noting that for each value of $\mathbf{C}$ there is at most one choice of $\mathbf{E}$ (namely, $\mathbf{E} = \mathbf{C}_{>m}$) and $\tau(\mathbf{C}_{\le m})$ choices for the pair $(\mathbf{B}, \mathbf{G})$ that yield $\mathbf{BEG} = \mathbf{C}$. Also, given we excluded the $\mathbf{X}_i$ factors from the $m$-friable part in Definition 1.3.2, we always have $\mathbf{C} \in \mathcal{P}^X$ when $\mathbf{E} = \mathbf{C}_{>m} \in \mathcal{P}^X$.

$$
\begin{align*}
R &= \sum_{\substack{\mathbf{B}=\mathbf{B}_{\le m} \\ \mathbf{B} \in \mathcal{E}_m}} \sum_{\mathbf{F}|\mathbf{B}} \sum_{\mathbf{k} \in K} \sum_{\substack{\mathbf{E} \in \mathcal{P}_{\mathbf{k}-\deg \mathbf{F}}^X \\ \mathbf{E}_{\le m}=1}} \sum_{\substack{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_l \\ l < 4\Sigma_m + 2 \\ \mathbf{I}_j \in \bar{\mathcal{I}}_m \text{ distinct}}} \left| \mathbf{P}(\mathbf{BEG}|\mathbf{A}) - \frac{1}{\|\mathbf{BEG}\|} \right| \\
&\le \sum_{\substack{\mathbf{B}=\mathbf{B}_{\le m} \\ \text{Deg } \mathbf{B} \le m(\Sigma_m - 2) \\ \tau(\mathbf{B}) \le e^{(1-1/r)\Sigma_m}}} \tau(\mathbf{B}) \sum_{\substack{\mathbf{E} \in \mathcal{P}^X \\ \max \text{deg } \mathbf{E} \le 2v \\ \mathbf{E}_{\le m}=1}} \sum_{\substack{\mathbf{G}=\mathbf{G}_{\le m} \\ \text{Deg } \mathbf{G} \le m(4\Sigma_m + 2) \\ \tau(\mathbf{G}) \le 2^{4\Sigma_m + 2}}} \left| \mathbf{P}(\mathbf{BEG}|\mathbf{A}) - \frac{1}{\|\mathbf{BEG}\|} \right| \\
&\le \sum_{\substack{\mathbf{C} \in \mathcal{P}^X \\ \text{Deg } \mathbf{C}_{\le m} \le 5m\Sigma_m \\ \text{Deg } \mathbf{C}_{> m} \le 2v \\ \tau(\mathbf{C}_{\le m}) \le 4e^{(1-1/r+4 \log 2)\Sigma_m}}} \tau(\mathbf{C}_{\le m}) \cdot e^{(1-1/r)\Sigma_m} \left| \mathbf{P}(\mathbf{C}|\mathbf{A}) - \frac{1}{\|\mathbf{C}\|} \right| \\
&\le 4e^{(2-2/r+4 \log 2)\Sigma_m} \Delta_{\mathbf{A}}(2v + 5m\Sigma_m).
\end{align*}
$$

Combining this with (7) into (6) and using that $\Pi_m \le e^{-\Sigma_m}$, $\Sigma_m = r(\log m + O(1))$ from Lemma 2.1.1 and $2Q(\frac{1-1/r}{2\log 2}) = \frac{1}{r} + Q(\frac{1-1/r}{\log 2})$, we get

$$
\begin{align*}
& \mathbb{P} \left( \left( \exists \mathbf{D} \in \bigcup_{v \le k \le 2v} \mathcal{P}_{(k, \dots, k)}, \mathbf{D} | \mathbf{A} \right) \cap \mathcal{E}_m \right) \\
& \le (v + L\Sigma_m)(L\Sigma_m)^r \cdot 4\Pi_m^2 \cdot O_r \left( e^{\Sigma_m [2-2Q(\frac{1-1/r}{2\log 2})]} \right) + 4e^{(2-2/r+4\log 2)\Sigma_m} \Delta_{\mathbf{A}}(2v + 5m\Sigma_m) + r e^{-\Sigma_m} \\
& \le O_r \left( v(L\Sigma_m)^r m^{-2rQ(\frac{1-1/r}{2\log 2})} + m^{5r} \Delta_{\mathbf{A}}(2v + 5m\Sigma_m) + m^{-r} \right) \\
& = O_r \left( \frac{v}{m} (L \log m)^r m^{-rQ(\frac{1-1/r}{\log 2})} + m^{5r} \Delta_{\mathbf{A}}(2v + 5m\Sigma_m) \right).
\end{align*}
$$

When $m \le L$, we have $\mathbb{P}((\exists \mathbf{D} \in \bigcup_{n_1 \le k \le n_2} \mathcal{P}_{(k, \dots, k)}, \mathbf{D} | \mathbf{A}) \cap \mathcal{E}_m) \le 1 \le L^r m^{-r}$ so the conclusion still holds. $\square$

## 2.3 Ruling out large $A_{\le m}$

We now want to bound the probability of $\overline{\mathcal{E}}_m$. We start by bounding the probability of the condition $\text{Deg } \mathbf{A}_{\le m} \ge m(\Sigma_m - 2)$.
**Lemma 2.3.1.** Let $C > 0$ a constant. For all $u$, we get

$$ \mathbb{P}(\text{Deg} \mathbf{A}_{\le m} \ge um) \le O_{r,C}(m^{2r}e^{-Cu}) + \Delta_{\mathbf{A}}((u+1)m). $$

Notably with $C = 3$ and $u = \Sigma_m - 2$, we get

$$ \mathbb{P}(\text{Deg} \mathbf{A}_{\le m} \ge m(\Sigma_m - 2)) \le O_r(m^{2r}e^{-3\Sigma_m}) + \Delta_{\mathbf{A}}(m(\Sigma_m - 1)) \le O_r(m^{-r}) + \Delta_{\mathbf{A}}(m\Sigma_m) $$

(as $\Sigma_m = r(\log m + O(1))$) by Lemma 2.1.1 and $\Delta_{\mathbf{A}}$ is increasing).

The lemma above is a generalisation of [1, lemma 9.1] working with $r$ primes instead of one. The proof, given below, follows the same steps as the reference above.

*Proof.* If $\text{Deg} \mathbf{A}_{\le m} \ge um$, then consider $\mathbf{D}$ a factor of $\mathbf{A}_{\le m}$ of total degree $\ge um$, but of minimal total degree among these. As all irreducible factors of $\mathbf{A}_{\le m}$ have total degree $\le m$, this is also true for $\mathbf{D}$. Thus, if $\mathbf{D}$ had total degree $\ge (u+1)m$, we could remove from it an irreducible factor and keep a factor of degree $\ge um$, contradicting the minimality of $\mathbf{D}$. Thus, when $\text{Deg} \mathbf{A}_{\le m} \ge um$, $\mathbf{A}$ always has a $m$-friable factor $\mathbf{D}$ of total degree between $um$ and $(u+1)m$.

We can then bound

$$ \begin{aligned} \mathbb{P}(\text{Deg} \mathbf{A}_{\le m} \ge um) &\le \sum_{\substack{um \le \text{Deg} \mathbf{D} \le (u+1)m \\ \mathbf{D}=\mathbf{D}_{\le m}}} \mathbb{P}(\mathbf{D}|\mathbf{A}) \\ &\le \sum_{\substack{um \le \text{Deg} \mathbf{D} \\ \mathbf{D}=\mathbf{D}_{\le m}}} \frac{1}{\|\mathbf{D}\|} + \sum_{\substack{\text{Deg} \mathbf{D} \le (u+1)m \\ \mathbf{D}=\mathbf{D}_{\le m}}} \left| \mathbb{P}(\mathbf{D}|\mathbf{A}) - \frac{1}{\|\mathbf{D}\|} \right| \\ &\le \sum_{\substack{um \le \text{Deg} \mathbf{D} \\ \mathbf{D}=\mathbf{D}_{\le m}}} \frac{1}{\|\mathbf{D}\|} + \Delta_{\mathbf{A}}((u+1)m) \end{aligned} $$

(note here the $\mathbf{D} = \mathbf{D}_{\le m}$ condition implies the $\mathbf{X}_i$ do not divide $\mathbf{D}$ as we excluded these factors from the $m$-friable part in Definition 1.3.2, which allows to bound the error term by a $\Delta_{\mathbf{A}}$ term.)

We then use Rankin's trick to bound the main term. Adjusting the implicit constant of the big-Oh term in the final result, we can suppose $m \ge 3C$ and get

$$ \begin{aligned} \sum_{\substack{um \le \text{Deg} \mathbf{D} \\ \mathbf{D}=\mathbf{D}_{\le m}}} \frac{1}{\|\mathbf{D}\|} &\le \sum_{\mathbf{D}=\mathbf{D}_{\le m}} \frac{e^{C \text{Deg} \mathbf{D}/m - Cu}}{\|\mathbf{D}\|} \\ &= e^{-Cu} \prod_{\mathbf{I} \in \mathcal{I}_m} \left( 1 - \frac{e^{C \text{Deg} \mathbf{I}/m}}{\|\mathbf{I}\|} \right)^{-1}, \end{aligned} $$

where we indeed have $\frac{e^{C \text{Deg} \mathbf{I}/m}}{\|\mathbf{I}\|} \le (e^{C/m}/2)^{\text{Deg} \mathbf{I}} \le (e^{1/3}/2)^{\text{Deg} \mathbf{I}} < 1$ for all $\mathbf{I} \in \mathcal{I}_m$ which justifies the convergence of the series and the last equality.

Moreover, for all $x \in [0, e^{1/3}/2]$, we have $-\log(1-x) \le 2x$ so that

$$ \begin{aligned} \log \prod_{\mathbf{I} \in \mathcal{I}_m} \left( 1 - \frac{e^{C \text{Deg} \mathbf{I}/m}}{\|\mathbf{I}\|} \right)^{-1} &\le 2 \sum_{\mathbf{I} \in \mathcal{I}_m} \frac{e^{C \text{Deg} \mathbf{I}/m}}{\|\mathbf{I}\|} \\ &\le 2 \sum_{\mathbf{I} \in \mathcal{I}_m} \frac{1 + (e^C - 1) \text{Deg} \mathbf{I}/m}{\|\mathbf{I}\|} \\ &= 2 \sum_{i=1}^r \sum_{j=1}^m \frac{\#\{I \in \mathbb{F}_{p_i}[X] \text{ irreducible of degree } j, I \ne X\}}{p_i^j} (1 + (e^C - 1)j/m) \\ &\le 2r \sum_{j=1}^m \frac{1 + (e^C - 1)j/m}{j} \\ &\le 2r(\log m + e^C), \end{aligned} $$

so that

$$ \sum_{\substack{um \le \text{Deg} \mathbf{D} \le (u+1)m \\ \mathbf{D}=\mathbf{D}_{\le m}}} \frac{1}{\|\mathbf{D}\|} \le e^{-Cu} \prod_{\mathbf{I} \in \mathcal{I}_m} \left( 1 - \frac{e^{C \text{Deg} \mathbf{I}/m}}{\|\mathbf{I}\|} \right)^{-1} \le e^{2re^C} e^{-Cu} m^{2r} $$

as we want.

□
We now show that the number of distinct irreducible factors of $\mathbf{A}_{\le m}$ is unlikely to be very large. This will be useful to bound the error term when trying to estimate the distribution of $\tau(\mathbf{A}_{\le m})$.

**Lemma 2.3.2.** We have when $u > 1$,

$$ \mathbb{P}(\omega(\mathbf{A}_{\le m}) \ge u\Sigma_m) \le O_{u,r}(e^{(1-Q(u))\Sigma_m}) + \Delta_{\mathbf{A}}(mu\Sigma_m), $$

where $\omega(\mathbf{B})$ is the number of distinct irreducible factors of $\mathbf{B}$ for $\mathbf{B} \in \mathcal{P}$.

*Proof.* As in the proof of Lemma 2.3.1, we start by noting that if $\omega(\mathbf{A}_{\le m}) \ge u\Sigma_m$, then $\mathbf{A}_{\le m}$ has a factor $\mathbf{B}$ which is a product of $\lfloor u\Sigma_m \rfloor$ distinct irreducible factors. This factor then has a total degree $\text{Deg} \mathbf{B} \le mu\Sigma_m$, and verifies $\omega(\mathbf{B}) = \lfloor u\Sigma_m \rfloor \ge u\Sigma_m - 1$, so that

$$ \begin{aligned} \mathbb{P}(\omega(\mathbf{A}_{\le m}) \ge u\Sigma_m) &\le \sum_{\substack{\mathbf{B}=\mathbf{B}_{\le m} \\ \omega(\mathbf{B}) \ge u\Sigma_m - 1 \\ \text{Deg} \mathbf{B} \le mu\Sigma_m}} \mathbb{P}(\mathbf{B}|\mathbf{A}) \\ &\le \sum_{\substack{\mathbf{B}=\mathbf{B}_{\le m} \\ \omega(\mathbf{B}) \ge u\Sigma_m - 1}} \frac{1}{\|\mathbf{B}\|} + \sum_{\substack{\mathbf{B}=\mathbf{B}_{\le m} \\ \text{Deg} \mathbf{B} \le mu\Sigma_m}} \left| \mathbb{P}(\mathbf{B}|\mathbf{A}) - \frac{1}{\|\mathbf{B}\|} \right| \\ &\le \sum_{\substack{\mathbf{B}=\mathbf{B}_{\le m} \\ \omega(\mathbf{B}) \ge u\Sigma_m - 1}} \frac{1}{\|\mathbf{B}\|} + \Delta_{\mathbf{A}}(mu\Sigma_m). \end{aligned} $$

To bound the main term, we use Rankin's trick. For $t > 0$, we have

$$ \begin{aligned} \sum_{\substack{\mathbf{B}=\mathbf{B}_{\le m} \\ \omega(\mathbf{B}) \ge u\Sigma_m - 1}} \frac{1}{\|\mathbf{B}\|} &\le \sum_{\mathbf{B}=\mathbf{B}_{\le m}} \frac{e^{t(\omega(\mathbf{B})-u\Sigma_m+1)}}{\|\mathbf{B}\|} \\ &= e^{-tu\Sigma_m+t} \prod_{\mathbf{I} \in \mathcal{I}_m} \left(1 + \sum_{\nu \ge 1} \frac{e^t}{\|\mathbf{I}\|^\nu}\right) \\ &\le e^{-tu\Sigma_m+e^t\Sigma_m+S_t+t} \end{aligned} $$

(where $S_t$ comes from Lemma 2.1.3 and we bounded $e^t \le (\nu+1)^t$ for $\nu \ge 2$.)

Taking the optimal $t := \log u > 0$ (when $u > 1$), we get the desired bound

$$ e^{(1-Q(u))\Sigma_m + S_{\log u} + \log u} = O_{r,u}(e^{(1-Q(u))\Sigma_m}). $$

□

We now have everything we need to bound $\mathbb{P}(\mathcal{E}_m)$.

**Proposition 2.3.3.** We have when $r \ge 4, m > 0$ and $\mathbf{A}$ is a random variable in $\mathcal{P}$,

$$ \mathbb{P}(\mathcal{E}_m) = O_r \left( m^{-rQ\left(\frac{1-1/r}{\log 2}\right)} + m^{5r}\Delta_{\mathbf{A}}(5m\Sigma_m) \right). $$

*Proof.* We have

$$ \mathbb{P}(\mathcal{E}_m) \le \mathbb{P}(\text{Deg } \mathbf{A}_{\le m} \ge m(\Sigma_m - 2)) + \mathbb{P}(\omega(\mathbf{A}_{\le m}) \ge 3\Sigma_m) \\ + \mathbb{P}(\tau(\mathbf{A}_{\le m}) \ge e^{(1-1/r)\Sigma_m}; \text{Deg } \mathbf{A}_{\le m} \le m(\Sigma_m - 2), \omega(\mathbf{A}_{\le m}) \le 3\Sigma_m) \quad (8) $$

with by Lemma 2.3.1,

$$ \mathbb{P}(\text{Deg } \mathbf{A}_{\le m} \ge m(\Sigma_m - 2)) \le O_r(m^{-r}) + \Delta_{\mathbf{A}}(m\Sigma_m), $$

and by Lemma 2.3.2,

$$ \mathbb{P}(\omega(\mathbf{A}_{\le m}) \ge 3\Sigma_m) \le O_r(e^{(1-Q(3))\Sigma_m}) + \Delta_{\mathbf{A}}(3m\Sigma_m). $$
We can now estimate the main term $P(\tau(\mathbf{A}_{\le m}) \ge e^{(1-1/r)\Sigma_m}; \text{Deg } \mathbf{A}_{\le m} \le m(\Sigma_m - 2), \omega(\mathbf{A}_{\le m}) \le 3\Sigma_m)$ using our sieve lemma 2.1.2:

$$
\begin{align*}
& P(\tau(\mathbf{A}_{\le m}) \ge e^{(1-1/r)\Sigma_m}; \text{Deg } \mathbf{A}_{\le m} \le m(\Sigma_m - 2), \omega(\mathbf{A}_{\le m}) \le 3\Sigma_m) \\
&= \sum_{\substack{\mathbf{B}=\mathbf{B}_{\le m} \\ \tau(\mathbf{B}) \ge e^{(1-1/r)\Sigma_m} \\ \text{Deg } \mathbf{B} \le m(\Sigma_m - 2) \\ \omega(\mathbf{B}) \le 3\Sigma_m}} P(\mathbf{A}_{\le m} = \mathbf{B}) \\
&\le \sum_{\substack{\mathbf{B}=\mathbf{B}_{\le m} \\ \tau(\mathbf{B}) \ge e^{(1-1/r)\Sigma_m}}} 2 \frac{\Pi_m}{\|\mathbf{B}\|} + \sum_{\substack{\mathbf{B}=\mathbf{B}_{\le m} \\ \text{Deg } \mathbf{B} \le m(\Sigma_m - 2) \\ \omega(\mathbf{B}) \le 3\Sigma_m}} \sum_{\substack{\mathbf{G}=\mathbf{I}_1...\mathbf{I}_\ell \\ I_j \in \mathcal{I}_m \text{ distinct} \\ \ell \le 4\Sigma_m + 2}} \left| P(\mathbf{B}\mathbf{G}|\mathbf{A}) - \frac{1}{\|\mathbf{B}\mathbf{G}\|} \right|.
\end{align*}
$$

To bound the main term, we use Rankin's trick again. We have for all $t > 0$,

$$
\begin{align*}
\sum_{\substack{\mathbf{B}=\mathbf{B}_{\le m} \\ \tau(\mathbf{B}) \ge e^{(1-1/r)\Sigma_m}}} \frac{1}{\|\mathbf{B}\|} &\le \sum_{\substack{\mathbf{B}=\mathbf{B}_{\le m} \\ \tau(\mathbf{B}) \ge e^{(1-1/r)\Sigma_m}}} \frac{\tau(\mathbf{B})^t e^{-t(1-1/r)\Sigma_m}}{\|\mathbf{B}\|} \\
&= e^{-t(1-1/r)\Sigma_m} \prod_{\mathbf{I} \in \mathcal{I}_m} \sum_{\nu \ge 0} \frac{(\nu+1)^t}{\|\mathbf{I}\|^\nu} \\
&\le \exp \left( -t(1-1/r)\Sigma_m + \sum_{\mathbf{I} \in \mathcal{I}_m} \sum_{\nu \ge 1} \frac{(\nu+1)^t}{\|\mathbf{I}\|^\nu} \right) \\
&\le e^{-t(1-1/r)\Sigma_m + 2t\Sigma_m + S_t} = O_{r,t} \left( e^{((1-1/r)t+2^t)\Sigma_m} \right),
\end{align*}
$$

where $S_t$ comes from Lemma 2.1.3. Taking the optimal value $t = \frac{\log \frac{1-1/r}{\log 2}}{\log 2} > 0$ (as $r \ge 4 > \frac{1}{1-\log 2}$), we get

$$
\sum_{\substack{\mathbf{B}=\mathbf{B}_{\le m} \\ \tau(\mathbf{B}) \ge e^{(1-1/r)\Sigma_m}}} 2 \frac{\Pi_m}{\|\mathbf{B}\|} = O_r \left( 2\Pi_m e^{\left[1 - Q\left(\frac{1-1/r}{\log 2}\right)\right]\Sigma_m} \right) = O_r \left( e^{-Q\left(\frac{1-1/r}{\log 2}\right)\Sigma_m} \right).
$$

To bound the error term, we regroup based on the value of $C = BG$. We then have

$$
\sum_{\substack{\mathbf{B}=\mathbf{B}_{\le m} \\ \text{Deg } \mathbf{B} \le m(\Sigma_m - 2) \\ \omega(\mathbf{B}) \le 3\Sigma_m}} \sum_{\substack{\mathbf{G}=\mathbf{I}_1 \dots \mathbf{I}_\ell \\ I_j \in \mathcal{I}_m \text{ distinct} \\ \ell \le 4\Sigma_m + 2}} \left| \mathbf{P}(\mathbf{B}\mathbf{G}|\mathbf{A}) - \frac{1}{\|\mathbf{B}\mathbf{G}\|} \right| \le \sum_{\substack{\mathbf{C}=\mathbf{C}_{\le m} \\ \text{Deg } \mathbf{C} \le 5m\Sigma_m \\ \omega(\mathbf{C}) \le 7\Sigma_m + 2}} \#\{\mathbf{G}|\mathbf{C} \text{ square-free}\} \left| \mathbf{P}(\mathbf{C}|\mathbf{A}) - \frac{1}{\|\mathbf{C}\|} \right| \\
\le 2^{7\Sigma_m + 2} \Delta_{\mathbf{A}}(5m\Sigma_m),
$$

remembering $C = C_{\le m}$ implies $C$ has no $\mathbf{X}_i$ factor (given Definition 1.3.2) and as such the sum on $C$ can be bounded by a $\Delta_{\mathbf{A}}$ term.

Combining this and the results from Lemmas 2.3.1 and 2.3.2 in (8), we get

$$
\begin{align*}
\mathbb{P}(\bar{\mathcal{E}}_m) &\le O_r(m^{-r}) + \Delta_{\mathbf{A}}(m\Sigma_m) + O_r\left(e^{(1-Q(3))\Sigma_m}\right) + \Delta_{\mathbf{A}}(3m\Sigma_m) \\
&\quad + O_r\left(e^{-Q\left(\frac{1-1/r}{\log 2}\right)\Sigma_m}\right) + 2^{7\Sigma_m+2}\Delta_{\mathbf{A}}(5m\Sigma_m) \\
&= O_r\left(m^{-r}Q\left(\frac{1-1/r}{\log 2}\right) + m^{5r}\Delta_{\mathbf{A}}(5m\Sigma_m)\right),
\end{align*}
$$

as $\Sigma_m = r(\log m + O(1))$ by Lemma 2.1.1, $Q(3) - 1 \ge Q(1/\log 2) \ge Q(\frac{1-1/r}{\log 2})$ and $\Delta_{\mathbf{A}}(m\Sigma_m) \le \Delta_{\mathbf{A}}(3m\Sigma_m) \le \Delta_{\mathbf{A}}(5m\Sigma_m)$. $\square$

## 2.4 Proof of Proposition 1.4.2

We can now combine Propositions 2.0.1 and 2.3.3 to prove Proposition 1.4.2.

*Proof of Proposition 1.4.2.* For $v > 0$, fix $m = m(v) := v/(\log v)^5$. When $n_1$ is large enough compared to $r$ (which we can assume adjusting the implicit constant of the final big-Oh term), we then have $5m\Sigma_m \le v/(\log v)^3$
and $v \ge 6m\Sigma_m$ as long as $v \ge n_1/2$ by Lemma 2.1.1. Then, Propositions 2.0.1 and 2.3.3 give for these $v$,

$$
\begin{align*}
& \mathbb{P} \left( \exists \mathbf{D} \in \bigcup_{v \le k \le 2v} \mathcal{P}_{(k, \dots, k)}, \mathbf{D} | \mathbf{A} \right) \\
& \le \mathbb{P} \left( \left( \exists \mathbf{D} \in \bigcup_{v \le k \le 2v} \mathcal{P}_{(k, \dots, k)}, \mathbf{D} | \mathbf{A} \right) \cap \mathcal{E}_{m(v)} \right) + \mathbb{P} \left( \overline{\mathcal{E}_{m(v)}} \right) \\
& = O_r \left( \frac{v}{m} (L \log m)^r m^{-rQ(\frac{1-1/r}{\log 2})} + m^{5r} \Delta_A (2v + 5m\Sigma_m) \right) + O_r \left( m^{-rQ(\frac{1-1/r}{\log 2})} + m^{5r} \Delta_A (5m\Sigma_m) \right) \\
& = O_r \left( L^r v^{-rQ(\frac{1-1/r}{\log 2}) + o(1)} + v^{5r} \Delta_A (2v + v/(\log v)^3) \right).
\end{align*}
$$

Applying for $v_j = n_2/2^j$ and summing on $1 \le j \le 1 + \frac{\log \frac{n_1}{n_2}}{\log 2}$ (so that the intervals $[v_j, 2v_j]$ cover $[n_1, n_2]$ and we always have $n_1/2 \le v_j \le n_2/2$), we get

$$
\mathbb{P} \left( \exists \mathbf{D} \in \bigcup_{n_1 \le k \le n_2} \mathcal{P}_{(k, \dots, k)}, \mathbf{D} | \mathbf{A} \right) = O_r \left( L^r n_1^{-rQ(\frac{1-1/r}{\log 2})+o(1)} + n_2^{5r} \Delta_A (n_2 + n_2/(\log n_2)^3) \right).
$$

□

3 Proofs of the main results

We now come back to the settings of the introduction, with $A \in \mathbb{Z}[X]$ a random monic polynomial of fixed degree $n$ and with coefficients drawn independently according to the $\mu_j$.

3.1 Factors of small degree

We prove in this section Lemma 1.2.3. We use the following result.

**Lemma 3.1.1** (Kolmogorov-Rogozin, [6]). Let $Q(Y; \delta) := \sup_x P(|Y - x| \le \delta)$. Then if $X_1, \dots, X_k$ are inde-
pendent and $S := \sum_{i=1}^k X_i$, we have for $L \ge \ell$,

$$
Q(S; L) \le K \frac{L}{\ell} \left( \sum_{i=1}^{k} (1 - Q(X_i; \ell)) \right)^{-1/2}
$$

for some absolute constant $K$.

*Proof of Lemma 1.2.3.* As $\Phi_d$ divides $X^d - 1$, we have

$$
A \equiv \sum_{i=0}^{d-1} a'_i X^i \quad \mod \Phi_d,
$$

where

$$
a'_{i} = \sum_{j \equiv i \bmod d} a_j.
$$

Now, as $\Phi_d$ has degree $\varphi(d)$, for any choice of the $a'_i$, $i \ge \varphi(d)$, there is only one choice of the $a'_i$, $i < \varphi(d)$ such that $\Phi_d|A$. As the $a'_i$ are independent, we thus get

$$
\mathbb{P}(\Phi_d|A) \le \prod_{i=0}^{\varphi(d)-1} \sup_x \mathbb{P}(a'_i = x).
$$

Now, as the $a_j$ take values in $\mathbb{Z}$ for all $j$, we get $Q(a_j, 1/2) = \sup_x P(a_j = x) \le 1 - c$. Lemma 3.1.1 then gives for all $i$, as $a'_i$ is a sum of $n/d + O(1)$ variables $a_j$,

$$
\sup_x \mathbb{P}(a'_i = x) = Q(a'_i, 1/2) \le \sqrt{\frac{Kd}{cn}}
$$

for a constant $K$, so that

$$
\mathbb{P}(\Phi_d|A) \le \prod_{i=0}^{\varphi(d)-1} \sup_x \mathbb{P}(a'_i = x) \le \left(\frac{Kd}{cn}\right)^{\varphi(d)/2}.
$$

□
From this and Proposition 1.2.2, we can deduce the following.

**Proposition 3.1.2.** Assume all the $\mu_j$ have support in $[-H, H]$ for some $H > 0$, and do not take any value with probability higher than $1-c$ for some $c > 0$. Fix then $C > 0$ and let $U_C$ the finite subset of $\mathbb{C}$ consisting of 0 and all roots of unity $\omega$ such that $[Q(\omega) : Q] < C$. Then for $n \ge (\log H)^3$,

$$ \mathbb{P}(A \text{ has a factor of degree } \le n^{1/10}) = \mathbb{P}(\exists \omega \in U_C : A(\omega) = 0) + O_{C,c}(n^{-C/2}). \quad (9) $$

*Proof.* We treat non-cyclotomic, small cyclotomic and large cyclotomic factors separately. Note that $U_C$ contain exactly the complex roots of $X$ and cyclotomic factors of degree $< C$, so that

$$ \begin{aligned} 0 \le \mathbb{P}(A \text{ has a factor of degree } \le n^{1/10}) - \mathbb{P}(\exists \omega \in U_C : A(\omega) = 0) & \\ \le \mathbb{P}(A \text{ has a non-}X, \text{ non-cyclotomic factor of degree } \le n^{1/10}) + \sum_{C \le \varphi(d) \le n^{1/10}} \mathbb{P}(\Phi_d|A). \end{aligned} $$

Using Proposition 1.2.2 to bound $\mathbb{P}(A \text{ has a non-}X, \text{ non-cyclotomic factor of degree } \le n^{1/10})$, it is thus sufficient to prove

$$ \sum_{C \le \varphi(d) \le n^{1/10}} = O_{C,c}(n^{-C/2}). $$

But using Lemma 1.2.3 and the fact probabilities are always smaller than one, we have

$$ \begin{aligned} \sum_{C \le \varphi(d) \le n^{1/10}} \mathbb{P}(\Phi_d|A) & \le \sum_{C \le \varphi(d) \le n^{1/10}} \left( \min \left\{ 1; \frac{Kd}{cn} \right\} \right)^{\varphi(d)/2} \\ & \le \sum_{C \le \varphi(d) < 2C} \left( \frac{Kd}{cn} \right)^{C/2} + \sum_{2C \le \varphi(d) \le n^{1/10}} \left( \frac{Kd}{cn} \right)^{C} = O_{C,c}(n^{-C/2}). \end{aligned} $$

□

## 3.2 The case of a segment

We now fix all $\mu_j$ equal to $\mu$ uniform over a segment $[a, a+N-1]$ of length $N$ in order to prove Theorems 1.1.4 and 1.1.2. We first prove $\hat{\mu}$ verifies (1) in this case.

**Proposition 3.2.1.** Let $\mu$ an uniform measure over a segment $[a, a+N-1]$ of $\mathbb{Z}$ of length $N$, and $Q$ a positive integer. Then for any $\theta_0 \in \mathbb{R}/\mathbb{Z}$, we have

$$ \sum_{k \in \mathbb{Z}/Q\mathbb{Z}} |\hat{\mu}(k/Q + \theta_0)| \le 1 + \frac{Q \cdot (\log(Q-1) + 2)}{N}. $$

*Proof.* Here, for $\theta \ne 0 \bmod 1$, we have

$$ \hat{\mu}(\theta) = \frac{1}{N} \sum_{j=a}^{a+N-1} e^{2i\pi j\theta} = \frac{1}{N} e^{2i\pi a\theta} \frac{1 - e^{2i\pi N\theta}}{1 - e^{2i\pi\theta}}, $$

so that

$$ |\hat{\mu}(\theta)| \le \frac{2}{N|1 - e^{2i\pi\theta}|} = \frac{1}{N|\sin \pi\theta|}. $$

We also always have $|\hat{\mu}(\theta)| \le \frac{1}{N} \sum_{j=a}^{a+N-1} |e^{2i\pi j\theta}| = 1$ for all $\theta$.

Now, note that the sum we want to bound does not change when $\theta_0$ is translated by a multiple of $1/Q$. Thus, we can suppose without loss of generality that $\theta_0 \in ]-1/2Q, 1/2Q]$, so that when $k \in [-Q/2, Q/2]$ with $|k| \ge 1$, we have

$$ |\sin \pi(k/Q + \theta_0)| \ge \min_{(k-1/2)/Q \le \theta \le (k+1/2)/Q} |\sin \pi\theta| = \sin \pi \frac{|k| - 1/2}{Q} \ge \frac{2|k| - 1}{Q} $$

(using $\sin x \ge \frac{2}{\pi}x$ in $[0, \pi/2]$).
Then, rewriting the sum over $Z/QZ$ as a sum over integers in $]-Q/2, Q/2]$, we get

$$
\begin{align*}
\sum_{k \in \mathbb{Z}/QZ} |\hat{\mu}(k/Q + \theta_0)| &\le |\hat{\mu}(\theta_0)| + \sum_{1 \le |k| \le Q/2} \frac{1}{N \sin \pi(k/Q + \theta_0)} \\
&\le 1 + \sum_{1 \le |k| \le Q/2} \frac{Q}{N(2|k| - 1)} \\
&= 1 + 2 \frac{Q}{2N} \sum_{k=1}^{[Q/2]} \frac{1}{k - 1/2} \\
&\le 1 + \frac{Q}{N} \left( 2 + \int_{1/2}^{Q/2-1/2} \frac{1}{t} \, dt \right) = 1 + \frac{Q \cdot (\log(Q-1) + 2)}{N}.
\end{align*}
$$

□

We can now prove Theorem 1.1.4.

*Proof of Theorem 1.1.4.* We start by proving the second statement of the theorem. Here, Proposition 3.1.2 applies with $c = 1/2$ since the $\mu_j$ are uniform over a segment of length $N \ge 2$. Thus, it is sufficient to show

$$ \mathbb{P}(A \text{ has a factor of degree } \in [n^{1/10}, \delta n]) = O_C(n^{-C/2}) $$

for some $\delta$ depending only on $C$.

Fix $r_1 \ge 4$ such that $r_1 Q \left( \frac{1-1/r_1}{\log 2} \right) > 5C$ (this is possible since $rQ \left( \frac{1-1/r}{\log 2} \right) \asymp r \to \infty$ when $r \to \infty$), and $P = p_1 \dots p_r$ the product of the $r_1$ smallest prime numbers.

Now, let $\mu$ the uniform measure on $[a, a+N-1]$ (which depends on $N$ and $a$), and note that for all $\theta \ne 0$ mod 1, we have $\max_{N \ge 2} |\hat{\mu}(\theta)| < 1$ (this is a max because $|\hat{\mu}(\theta)|$ does not depend on $a$ and tends to 0 when $N \to \infty$), so that $|\hat{\mu}(\theta)|^s \to 0$ when $s \to \infty$, uniformly in $N$ and $a$. Thus, for any fixed $Q, R = P/Q, \ell \in \mathbb{Z}/RZ$, for $s$ large enough (depending only on $Q, R, \ell$), we have

$$ \sum_{k \in \mathbb{Z}/QZ} |\hat{\mu}_j(k/Q + \ell/R)|^s \le \left(1 - \frac{1}{4 \log P}\right) \sqrt{Q}. $$

As $P$ has a finite number of divisors, we can then fix $s$ (depending only on $P$, which depends only on $C$) which verifies the condition above for all $Q$ dividing $P$ and $\ell \in \mathbb{Z}/RZ$. Then with $\delta := 1/2s$, Theorem 1.2.1 with $n_1 = n^{1/10}$ gives us for $n \ge P^4$,

$$ \mathbb{P}(A \text{ has a factor of degree } \in [n^{1/10}, \delta n]) = O_{r_1, s} \left( n^{-\frac{1}{10} r_1 Q \left( \frac{1-1/r_1}{\log 2} \right) + o(1)} \right) = O_C(n^{-C/2}) $$

by definition of $r_1$, as desired. As $P$ depends only on $C$ and $\varepsilon$, and probabilities are always bounded by 1, we can adjust the implicit constant of the big-Oh term to extend it to the values of $n \le P^4$ as well.

We now prove the first statement. This time, our starting point is the second statement (which we just proved), which tells us

$$ \mathbb{P}(A \text{ has a factor of degree } \le \delta n) = \mathbb{P}(\exists \omega \in U_C : A(\omega) = 0) + O_C(n^{-C/2}) \quad (10) $$

for some $\delta$ depending only on $C$.

Now, fix $r \ge 4$ such that $rQ \left( \frac{1-1/r}{\log 2} \right) > C/2$ and $P = p_1 \dots p_r$ the product of the $r$ smallest primes, and

$$ N_0 \ge f(P) := \frac{P \cdot (\log(P-1) + 2)}{0.99\sqrt{P} - 1} \quad (11) $$

(the constant 0.99 here is arbitrary, and $N_0$ depends only on $C$ as $P$ does. As a matter of fact, when $C=1$, these constraints are satisfied with $r=12$, $P=2 \cdot 3 \dots 37 \simeq 7.4 \cdot 10^{12}$ and $N_0 = 10^8$.)

For $N \ge N_0$ and $2 \le Q \le P$, as $f$ is increasing on $[2, +\infty[$, we then have $N \ge N_0 \ge f(P) \ge f(Q)$ and then by Proposition 3.2.1, for all $\theta_0$,

$$ \sum_{k \in \mathbb{Z}/QZ} |\hat{\mu}(k/Q + \theta_0)| \le 1 + \frac{Q \cdot (\log(Q-1) + 2)}{N} \le 1 + \frac{Q \cdot (\log(Q-1) + 2)}{f(Q)} = 0.99 \sqrt{Q}, $$

where $\mu$ uniform over $[a, a+N-1]$.
Thus, Theorem 1.2.1 applies with $s = 1$ for $n \ge \max\{P^4, e^{100}\}$ and gives us

$$P(A \text{ has a factor of degree } \in [\delta n, n/2]) = O_{r,s}\left((\delta n)^{-rQ(\frac{1-1/r}{\log 2})+o(1)}\right) = O_C(n^{-C/2}),$$

a result which can again be extended to smaller values of $n$ adjusting the implicit constant of the big-Oh term. Combining with (10) concludes the proof. □

# 4 Acknowledgments

This work was the result of my research for my master's thesis, under supervision of Régis de la Bretèche (Université Paris Cité). I would like to thank him for presenting me the topic and guiding me throughout the writing of this paper, as well as his useful review and commentaries on it. I would also like to thank the anonymous reviewer for their valuable remarks on the paper.

# References

[1] L. Bary-Soroker, D. Koukoulopoulos, and G. Kozma. Irreducibility of random polynomials: General measures. *Invent. Math.* 233(3):1041–1120, 2023.

[2] L. Bary-Soroker and G. Kozma. Irreducible polynomials of bounded height. *Duke Math. J.* 169(4):579–598, 2020.

[3] E. Breuillard and P. P. Varjú. Irreducibility of random polynomials of large degree. *Acta Math.* 223(2):195–249, 2019.

[4] K. Ford. Integers with a divisor in $(y, 2y]$. *Anatomy of Integers. CRM Proc. and Lecture Notes* 46:65–80, 2008.

[5] S. Konyagin. On the number of irreducible polynomials with 0, 1 coefficients. *Acta Arith.* 88(4):333–350, 1999.

[6] B. Rogozin. An estimate for Concentration functions. *Theory Probab. Appl.* 6(1):94–97, 1961.