The smallest root of a polynomial congruence (Q2183371)

This article deals with polynomial congruences of the type \(f(t)\cong 0(\mathrm{mod}\ k)\) with \(f\in\mathbb{Z}[t]\) of degree at least \(2\) and \(k\) a positive integer. When \(f\) is also irreducible, \textit{C. Hooley} in [Mathematika, Lond. 11, 39--49 (1964; Zbl 0123.25802)] established the equidistribution of the roots of \(f\) modulo \(k\) in the sense that for each positive integer \(k\) the sequence \(\frac{\nu_1}{k}, \ldots, \frac{\nu_{\rho(k)}}{k}\) is uniformly distributed in \([0,1)\), where \(\nu_1, \ldots, \nu_{\rho(k)}\) denote the roots of \(f\) modulo \(k\) belonging to \([0,k)\). The authors first show that Hooley's theorem holds more generally when \(f\) has no multiple roots (Theorem 1.1). Their proof is basically an adaptation of Hooley's method, since the absence of the irreducibility assumption brings in just more technicalities but no significant obstacle to Hooley's method. This approach is also exploited to provide a bound for the smallest root of \(f\) modulo \(k\) when \(f\in\mathbb{Z}[t]\) has degree at least \(2\) and no multiple roots (Theorem 1.2). More precisely, for such a polynomial \(f\) the authors prove the existence of a positive constant \(c_f\) such that, for almost all \(k\) for which \(f(t)\cong 0\pmod k\) is solvable, the least integer solution \(r\) satisfies \(r<\frac{k}{(\log k)^{c_f}}\). This upper bound is shown to be sharp up to the value of \(c_f\) in the case when \(f\) has no nonnegative integer roots. If \(f\) has a nonnegative integer root, then this upper bound is rather poor as the smallest nonnegative integer root of \(f\) is also the smallest integer root modulo \(k\) for all but finitely many \(k\)'s. Note that the equidistribution of the roots of \(f\) modulo \(k\) as \(k\) varies (Theorem 1.1) does not imply the existence of a root of \(f\) modulo \(k\) that is almost always small (Theorem 1.2). Furthermore, for a given \(f(t)\in\mathbb{Z}[t]\), the authors compare the set \(\mathscr{R}_f\) of all positive integers \(k\) for which \(f(t)\cong 0(\mathrm{mod}\ k)\) is solvable with the set \(\mathscr{Q}_f\) of all quotients \(\frac{|f(r_k)|}{k}\) where \(k\) varies over all positive integers and \(r_k\) is the least nonnegative integer root of \(f\) modulo \(k\). They establish that if \(f\) has no nonnegative integer root then \(\mathscr{Q}_f\subseteq\mathscr{R}_f\), and equality holds when \(f\) has at least two distinct roots.