| Izvestiya: Mathematics |
|
|
|
|
|
A polynomial analogue of Jacobsthal function A. B. Kalmyninab, S. V. Konyagina a Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia b National Research University Higher School of Economics, Moscow, Russia
Russian version:
Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya, 2024, Volume 88, Issue 2, DOI: https://doi.org/10.4213/im9467 
Bibliographic databases:
    § 1. Introduction and main resultsLet $N$ be a natural number. The Jacobsthal function $j(N)$ is defined as the length of the largest gap between numbers which are coprime to $N$. In other words,
$$
\begin{equation*}
j(N)=\max_{m}\{\text{for some } x\in \mathbb N \text{ the inequality } (x+i,N)>1 \text{ holds for all }i\leqslant m\}.
\end{equation*}
\notag
$$
Estimates for $j(N)$ are used to establish results on large gaps between consecutive primes. For instance, the current best lower bound for $p_{n+1}-p_n$ is Theorem A (see [1]). Let $y\geqslant 19$ and Then In particular, for $X\geqslant e^{16}$, As for the upper bounds for $j(N)$, Iwaniec showed [2] that the following holds. In this paper, we study a polynomial analogue of the Jacobsthal function. Namely, let $f(x)$ be a non-constant polynomial with integer coefficients. Define the function $j_f(x)$ by
$$
\begin{equation*}
j_f(N)=\max_{m}\{\text{for some } x\in \mathbb N \text{ the inequality } (x+f(i),N)>1 \text{ holds for all }i\leqslant m\}.
\end{equation*}
\notag
$$
So, instead of the intervals not containing numbers coprime to $N$ we study shifts of polynomial sequences. Here, we are going to present a lower bound for $j_f(P(y))$ similar to the classical Rankin’s bound [3]. To formulate the resulting statement, let us first define a number $M(f)$, which one can call an average size of the maximal preimage of a non-zero point under a map $f\colon \mathbb F_p\to \mathbb F_p$. Definition 1. Suppose that $f(x)\in \mathbb Z[x]$. If $p$ is a prime number, denote by $M_p(f)$ the maximal number of solutions $x\in \mathbb F_p$ to the equation $f(x)=y$ for fixed $y\in \mathbb F_p\setminus\{0\}$. The quantity $M(f)$ is defined as a unique $M$ with for all real $X\geqslant 2$ if such a number $M$ exists. It is easy to see that if $f_d(x)=x^d$, then $M(f_1)=1$ and $M(f_2)=M(f_3)=2$. In the third section, we will express $M(f)$ in terms of certain Galois groups associated with $f(x)$. We compute $M(f_d)$ explicitly for all $d$ and also $M(f)$ for a typical polynomial of degree $d$. The second section is devoted to the proof of the following bound for $j_f(P(y))$. Theorem 1. Suppose that, for a polynomial $f\in \mathbb Z[x]$, the factorization of $f$ contains $\ell_f$ distinct linear and $h_f$ distinct non-linear factors. Then, for $y\geqslant 19$, Remark 1. Let us observe that the value of $j_f$ is invariant under shifts by a constant, that is, for all $n\in \mathbb Z$ we have $j_f=j_{f+n}$. Choosing $n=-f(0)$, we can always force our polynomial to be divisible by $x$. In particular, for a polynomial $f$ of degree at least $2$ we always have Indeed, since $M(f)\geqslant 1$, for $\ell_f\geqslant 2$ or $\ell_f=1$ and $h_f\geqslant 1$, we get the desired inequality. The last remaining case is $\ell_f=1$, $h_f=0$, that is, $f=c(ax+b)^d$ for some $a,b,c\in \mathbb Z$, $ac\neq 0$. In the last section we show that $M(f_d)=\tau(d)\geqslant 2$ for $f_d(x)=x^d$, $d\geqslant 2$, hence, in our case, $M(f)=M(f_d)\geqslant 2$, and the inequality follows. It turns out that the value $M(f)$ always exists and is rational. To formulate our result on $M(f)$, let us first introduce the quantity $m(G,H;X)$. Definition 2. Let $G$ be a finite group acting on a set $X$ and $H$ be a subgroup of $G$. For $g\in G$, denote by $X^g$ the set of fixed points of $g$. Then Theorem 2. For a field $L$, let $L_f$ denote the splitting field of the polynomial $f(x)- y$ over the field $L(y)$ of rational functions over $L$. Denote by $K$ the intersection of $\mathbb Q_f$ and $\overline{\mathbb Q}$, that is, the maximal constant subfield of $\mathbb Q_f$. Let $G_f$ and $G_f^+$ be the Galois groups of $\mathbb Q_f=K_f$ over $\mathbb Q(y)$ and $K(y)$, respectively. These groups have a natural action on the set $X$ of all solutions to $f(x)=y$ and $G_f^+$ may be viewed as a subgroup of $G_f$ fixing $K$. We have Our study of $j_f$ is motivated by Theorem 5 in [4]. This result gives an upper bound for the least integer $\gamma_k>0$ such that all the numbers $\gamma_k+j^d$ for $1\leqslant j\leqslant k$ are not sums of two squares. The problem of estimating $\gamma_k$ was raised by the first two authors. § 2. Proof of the main theoremTo prove our main result, we are going to choose $x$ such that $x+f(i)$ is not coprime to $P(y)$ for many first values of $i$ by choosing residues $x_p \mod p$ for all $p\leqslant y$. We will choose $x_p \mod p$ for primes $p\leqslant y$ so that, for all $i=1,\dots,m$ there is some $p\leqslant y$ for which $f(i)+x_p \equiv 0\pmod{p}$. Next, we take $x$ to be a solution of the simultaneous congruences $x\equiv x_p\pmod{p}$ for $p\leqslant y$. It now follows that $j_f(P(y)) \geqslant m$. In the proof, we will use the following well-known result on sifted sets. Lemma 1. Suppose that $\kappa>0$, $z\geqslant 2$. Assume that $\{a_n\}$ is a sequence of non- negative real numbers such that, for all $d \,|\, P(z)$, This result is a version of the fundamental lemma of sieve theory (see, for example, Theorem 2.2 in [5]). In particular, we have the following corollary. Corollary 1. Let $\kappa$, $z$, $g(d)$, $V(z)$, and $X$ be as above. Suppose that, for any $p\leqslant z$, the set $\Omega_p\subset \mathbb Z/p\mathbb Z$ contains $g(p)$ elements. Let $S(X,\Omega)$ be the number of $n\leqslant X$ such that $n\, \operatorname{mod} p \notin \Omega_p$ for all $p\leqslant z$. Then Proof. To see this, we set, for any $p\leqslant z$, and let $Q(z;p)$ be the least positive integer solution to the congruences
$$
\begin{equation*}
Q(z;p)\equiv P(z;p) \pmod p\quad \text{and}\quad Q(z;p)\equiv -1 \pmod{P(z;p)}.
\end{equation*}
\notag
$$
Setting
$$
\begin{equation*}
a_m=\begin{cases} 1 &\text{if }m={\displaystyle\prod_{p\leqslant z}\prod_{r \in \Omega_p}\bigl(P(z;p)n+rQ(z;p)\bigr)} \text{ for some }n\leqslant X, \\ 0 &\text{otherwise}, \end{cases}
\end{equation*}
\notag
$$
it is easily seen that $(m,P(z))=1$ and $a_m=1$ if and only if the corresponding $n$ does not lie in any $\Omega_p$ for $p\leqslant z$. The conditions of Lemma 1 also clearly hold. Corollary is proved. We also need the following well-known consequence of Chebotarev’s density theorem. Lemma 2. Let $f$ be an irreducible polynomial with integer coefficients. If $r_p(f)$ is the number of roots of $f$ in $\mathbb F_p$, then there are two constants $c_1,c_2>0$ such that, for $x\geqslant 3$, Proof. Let $K$ be the splitting field of $f$ over $\mathbb Q$. Galois group $G$ of $K$ over $\mathbb Q$ acts on the set of roots of $f$, this action is transitive. It is easy to see that, for large enough $p$, the number $r_p(f)$ is equal to the number of fixed points of this action for the associated Frobenius conjugacy class. Therefore, by Chebotarev’s theorem, the proportion of the primes $p$ for which $r_p(f)=k$ is equal to that of the elements of $G$ with exactly $k$ fixed points. By Burnside’s lemma, the average number of fixed points for a transitive action is equal to $1$, therefore, the average of $r_p(f)$ over primes is also $1$. Asymptotic formulas with required remainder terms follow from the effective version of Chebotarev’s density theorem for $K/\mathbb Q$, see Theorem 1.3 in [6]. Lemma 2 is proved. Let us now prove Theorem 1. Proof of Theorem 1. Let $A$ be a large constant and $B$ be an even larger constant. We set
$$
\begin{equation*}
\begin{gathered} \, m=\frac{y}{B}(\ln y)^{\ell_f-1}\biggl(\frac{(\ln\ln y)^2}{\ln\ln\ln y}\biggr)^{h_f} \biggl(\frac{\ln y\ln\ln\ln y}{(\ln\ln y)^2}\biggr)^{M(f)}, \\ z_0=(\ln y)^A,\qquad z_1=\exp\biggl(\frac{\ln\ln \ln y\ln y}{A\ln\ln y}\biggr). \end{gathered}
\end{equation*}
\notag
$$
We are going to choose $x_p$ in three steps. After the first two steps, we compute the number of unsifted numbers $i\leqslant m$. To be more precise, if we have an already chosen $x_p$ for some values of $p$, then the number $i$ is called sifted if, among the used primes, there is a $p$ such that For the first step, let us choose Now, suppose that the number $i\leqslant m$ is not sifted after the first step. Let $k(x)$ be a factor of $f(x)$ of degree $1$. Then $k(i)$ has no prime factors $p\in [2,z_0]\cup (z_1,y/2)$. Since $k(i)\ll m\ll y(\ln y)^{\ell_f+M(f)}$, for large enough $A$ we conclude that $|k(i)|$ is either a prime or a $z_1$-smooth number. For large enough $A$, the number of $z_1$-smooth numbers that are $\ll m$ can be estimated as For the second step, let us choose $x_p$ for all $z_0<p\leqslant z_1$ as follows: by the definition of $M(f)$, for any such $p$ there is a non-zero $y_p\in \mathbb F_p\setminus \{0\}$ such that the congruence $f(i)\equiv y_p \pmod p$ has $M_p(f)$ solutions. We set $x_p\equiv -y_p \ (\operatorname{mod} p)$.
Next, we are going to estimate the number $R$ of $i\leqslant m$ that remain unsifted after these two steps. Our goal will be to establish the inequality for all large $y$ if $A$ and $B$ are taken to be large enough. For $p\leqslant \sqrt{y}$, let $\Omega_p^{\mathrm{I}}$ consist of all residues $t \ \operatorname{mod} p$ such that $k(t)\equiv 0 \ (\operatorname{mod} p)$ for some linear factor $k(x)$ of $f$. Next, if $p\in [2,z_0]\cup (z_1,\sqrt{y})$, we set
$$
\begin{equation*}
\Omega_p^{\mathrm{II}}\,{=}\,\{t \ \operatorname{mod} p\colon \exists\,\text{non-linear irreducible factor }q(x)\text{ of }f(x)\text{ with }q(t)\equiv 0 \ (\operatorname{mod} p)\}.
\end{equation*}
\notag
$$
For $p\notin[2,z_0]\cup(z_1,\sqrt{y})$, we define $\Omega_p^{\mathrm{II}}=\varnothing$. Finally, for $z_0<p\leqslant z_1$ we set
$$
\begin{equation*}
\Omega_p^{\mathrm{III}}=\{t\ \operatorname{mod} p\colon f(t)\equiv y_p\ (\operatorname{mod} p)\}
\end{equation*}
\notag
$$
and $\Omega_p^{\mathrm{III}}=\varnothing$ for other values of $p$. Set $\Omega_p=\Omega_p^{\mathrm{I}}\cup \Omega_p^{\mathrm{II}}\cup \Omega_p^{\mathrm{III}}$. We claim that if $i\leqslant m$ is unsifted after two steps, then either $i\ll \sqrt{y}$ or $k(i)$ is $z_1$-smooth for some linear factor $k(x)$ of $f$ (the number of such $i$ is $o(y/\ln y)$ by the choice of $A$) or $i\mod p\notin \Omega_p$ for any $p\leqslant \sqrt{y}$. Indeed, suppose that $i\ \operatorname{mod} p\in \Omega_p$ for some $p$. There are three cases to consider.
Case 1: $k(i)$ is divisible by $p$ for some linear factor $k(x)$ of $f$. In this case, either $k(i)=\pm p$ and $i\ll \sqrt{y}$, or $|k(i)|$ is not a prime number, hence $k(i)$ must be $z_1$-smooth or else $i$ must be sifted after the first step. Case 2: $p\in [2,z_0]\cup (z_1,\sqrt{y})$ and for some irreducible non-linear factor $q(x)$ of $f(x)$, we have $q(i)\equiv 0\ (\operatorname{mod} p)$. Then $f(i)$ is also divisible by $p$, hence $p$ must be sifted after the first step. Case 3: $z_0<p\leqslant z_1$ and $f(i)\equiv y_p$. Then $i$ is sifted after the second step. From this we conclude that
$$
\begin{equation*}
R\leqslant S(m,\Omega)+O\bigl(\sqrt{y}+\Psi(O(m),z_1)\bigr)=S(m,\Omega)+o\biggl(\frac{y}{\ln y}\biggr)
\end{equation*}
\notag
$$
by our choice of $A$. We will now apply Corollary 1 to estimate $S(m,\Omega)$. Let $g(p)=|\Omega_p|$. If, for some $p\leqslant \sqrt{y}$, we have $g(p)=p$, then, clearly, $S(m,\Omega)=0$. Otherwise notice that all three parts of $\Omega_p$ contain at most $d=\deg f$ elements, hence Corollary 1 is applicable for $\kappa=3d$. Hence
$$
\begin{equation*}
S(m,\Omega)\ll m\prod_{p\leqslant \sqrt{y}}\biggl(1-\frac{g(p)}{p}\biggr)\ll m\exp\biggl(-\sum_{p\leqslant \sqrt{y}}\frac{g(p)}{p}\biggr).
\end{equation*}
\notag
$$
Now, let $k_1(x),\dots,k_{\ell_f}(x)$ and $q_1(x),\dots,q_{h_f}(x)$ be all the linear and non-linear irreducible factors of $f(x)$, respectively. Each two fixed irreducible polynomials have no common roots modulo large enough primes. Therefore, there is a constant $p_0$ such that, for $p>p_0$, the sets $\Omega_p^{\mathrm{I}}$, $\Omega_p^{\mathrm{II}}$ and $\Omega_p^{\mathrm{III}}$ are pairwise disjoint. Moreover, taking $p_0$ large enough, we can assure that $|\Omega_p^{\mathrm{I}}|=\ell_f$ for all $p>p_0$ and $|\Omega_p^{\mathrm{II}}|=r_p(q_1)+\dots+r_p(q_{h_f})$ for $p\in (p_0,z_0]\cup (z_1,\sqrt{y})$. Also, by definition, $|\Omega_p^{\mathrm{III}}|=M_p(f)$ for all $z_0<p\leqslant z_1$. Consequently,
$$
\begin{equation*}
\sum_{p\leqslant \sqrt{y}}\frac{g(p)}{p}=\sum_{p_0<p\leqslant \sqrt{y}}\frac{\ell_f}{p}+\sum_{h\leqslant h_f}\, \sum_{p\in (p_0,z_0]\cup (z_1,\sqrt{y})}\frac{r_p(q_h)}{p}+\sum_{z_0<p\leqslant z_1}\frac{M_p(f)}{p}.
\end{equation*}
\notag
$$
By the Mertens theorem, the first sum is
$$
\begin{equation*}
\sum_{p_0<p\leqslant \sqrt{y}}\frac{\ell_f}{p}=\ell_f \ln\ln y+O(1).
\end{equation*}
\notag
$$
Lemma 2 gives, for every $h\leqslant h_f$,
$$
\begin{equation*}
\sum_{p\in (p_0,z_0]\cup (z_1,\sqrt{y})}\frac{r_p(q_h)}{p}=\ln\ln y-\ln\ln z_1+\ln\ln z_0+O(1).
\end{equation*}
\notag
$$
Finally, by the definition of $M(f)$, the third sum can be evaluated as
$$
\begin{equation*}
\sum_{z_0<p\leqslant z_1}\frac{M_p(f)}{p}=M(f)(\ln\ln z_1-\ln\ln z_0)+O(1).
\end{equation*}
\notag
$$
Plugging all of this into our estimate, we get
$$
\begin{equation*}
\begin{aligned} \, S(m,\Omega) &\ll m(\ln y)^{-\ell_f}\biggl(\frac{\ln z_1}{\ln y\ln z_0}\biggr)^{h_f} \biggl(\frac{\ln z_0}{\ln z_1}\biggr)^{M(f)} \\ &=m(\ln y)^{-\ell_f}\biggl(\frac{\ln\ln\ln y}{A^2(\ln\ln y)^2}\biggr)^{h_f} \biggl(\frac{A^2(\ln\ln y)^2}{\ln y\ln\ln\ln y}\biggr)^{M(f)}=\frac{A^{2M(f)-2h_f}y}{B\ln y}. \end{aligned}
\end{equation*}
\notag
$$
Since the implied constant does not depend on $A$ and $B$, we can take $B$ large enough to obtain so that
$$
\begin{equation*}
R\leqslant S(m,\Omega)+o\biggl(\frac{y}{\ln y}\biggr)\leqslant \frac{y}{3\ln y}.
\end{equation*}
\notag
$$
Since for the third step we have $\pi(y)-\pi(y/2)=y/((2+o(1))\ln y)$ primes $p\leqslant y$ left, one can sift one of remaining numbers at a time to ensure that every number $i\leqslant m$ is sifted out in these three steps. This concludes the proof of Theorem 1. § 3. Computation of $M(f)$In this section, we prove Theorem 2 on the value of $M(f)$. The quantity $M(f)$ is the logarithmic average of $M_p(f)$ over prime values of $p$. The number $M_p(f)$ is defined as the maximal number of solutions for $f(x)=y$ with $x\in \mathbb F_p$ for a fixed non-zero $y\in \mathbb F_p$. We will show that $M(f)$ always exists and is a rational number, and we also reduce its computation to group actions. In the introduction, we associated $f(x)$ with several Galois groups, which have a natural action on the set $X$ of all roots of the equation $f(x)-y$, where $y$ is a formal variable. Namely, $G_f$ is the Galois group of $f(x)-y$ over $\mathbb Q(y)$ and $G_f^+$ is the Galois group of the same polynomial over $K(y)$. It is easy to see that $G_f^+$ is a normal subgroup of $G_f$. Indeed, it is clear that $K$ is a finite normal extension of $\mathbb Q$. If $G_f^0$ is its Galois group, then there is a natural surjective homomorphism $\pi\colon G_f\to G_f^0$. More precisely, every automorphism of the splitting field of $f(x)-y$ over $\mathbb Q(y)$ sends constants to constants. Such an automorphism is an automorphism over $K(y)$ if and only if all the constant elements are fixed, hence $G_f^+=\ker \pi$ is a normal subgroup. Birch and Swinnerton-Dyer [7] were able to reduce the question on the number of solution of $f(x)=y$ to certain other Galois groups. Lemma 3. Let $G_p^+$ be the Galois group of $f(x)-y$ over $\overline{\mathbb F}_p(y)$ and $G_p$ be the Galois group of the same polynomial over $\mathbb F_p(y)$. For $n\leqslant d=\deg f$, let $m_n$ be the number of $G_p$-invariant orbits of action of $G_p^+$ on ordered $n$-tuples of distinct roots of $f(x)=y$. Then, for $m_n=0$, the system $f(x_1)=f(x_2)=\dots=f(x_n)$ has no solutions in $\mathbb F_p$ with $x_i\neq x_j$ for $i\neq j$, and, for $m_n>0$, the number of solutions is For convenience, let us formulate Chebotarev’s density theorem. First, define the Frobenius element. Definition 3. Let $K/\mathbb Q$ be a finite Galois extenstion, $\mathcal O_K$ be its ring of integers, and $G_K$ be its Galois group. Suppose that $p$ is an unramified rational prime number and $\mathfrak p\subset \mathcal O_K$ is a prime ideal lying over $p$. The Frobenius element of $\mathfrak p$ is an element $\sigma_{\mathfrak p}\in G_K$ with for all $x\in \mathcal O_K$. For different prime ideals $\mathfrak p$ lying over fixed prime number $p$ Frobenius elements are conjugated, therefore, up to conjugation, we can define the Frobienus element $\sigma_p$. The following lemma is a consequence of Chebotarev’s density theorem. Lemma 4. Let $K/\mathbb Q$ be a finite Galois extension with Galois group $G_K$. Suppose that $C\subset G_K$ is a conjugacy class and $\pi(x;K,C)$ is the number of primes $p\leqslant x$ such that the Frobenius element $\sigma_p$ lies in $C$. Then, for some $c_K>0$, For a proof, see [6]. Let us now prove Theorem 2. Proof of Theorem 2. In [7], it is proved that, for large enough $p$, the group $G_p^+$ can be identified with the Galois group of $f(x)-y$ over $\mathbb C(y)$. It is easy to see that this group coincides with $G_f^+$. Next, large primes $p$ are unramified in $K$, so we fix some prime ideal $\mathfrak p$ lying over $p$ in $\mathcal O_K$ and consider the corresponding Frobenius element $\sigma_{\mathfrak p}$. The largest constant subfield of $(\mathbb F_p)_f$ can be identified with $\mathcal O_K/\mathfrak p$. Moreover, $G_p$ acts on constants via Frobenius automorphism and its powers. For large $p$, the group $G_p$ is generated by $G_f^+$ and the preimage of $\sigma_{\mathfrak p}$, that is,
$$
\begin{equation*}
G_p=\langle \pi_p^{-1}(\sigma_{\mathfrak p}),G_f^+ \rangle,
\end{equation*}
\notag
$$
where $\pi_p$ is the homomorphism of restriction of $G_p$-action on constants (its image is the Galois group of $\mathcal O_K/\mathfrak p$ over $\mathbb F_p$), which allows us to consider $G_p$ as a subgroup of $G_f$. Let $g$ be any element of $\pi_p^{-1}(\sigma_{\mathfrak p})$. Let us show that, in this case, the maximal $n$ with $m_n>0$ is equal to $\max_{h\in G_f^+}|X^{hg}|$. Indeed, $G_f^+$ is normal in $G_p$, hence the latter group is generated by $g$ and $G_f^+$, so a $G_f^+$-orbit is $G_p$-invariant if and only if it is $g$-invariant. This means that if our orbit takes form $G_f^+(x_1,\dots, x_n)$, then, for any $h_1\in G_f^+$, there exists $h_2\in G_f^+$ such that The subgroup $G_f^+$ is normal, so there exists $h_3$ with $gh_2=h_3g$. Therefore, our condition is equivalent to the following: for any $h_3$ one can find $h_1$ such that $x_1,\dots,x_n$ are fixed by $hg$, where $h=h_1^{-1}h_3$. This proves the desired identity. Thus, for large $p$ the number $M_p(f)$ is equal to $\max_{h\in G_f^+}|X^{hg}|$, where $g\in \pi_p^{-1}(\sigma_{\mathfrak p})\subset \pi_p^{-1}(\sigma_p)=:C$ and $\sigma_p$ is the conjugacy class of $\sigma_{\mathfrak p}$ in $G_f^0$. Since $G_f^+$ is normal, this number does not depend on the choice of $g$ and $\mathfrak p$. Chebotarev’s density theorem shows that
$$
\begin{equation*}
\begin{aligned} \, \sum_{p\leqslant x}M_p(f) &=\sum_{C, g_0\in C}\frac{|C|}{|G_f^0|}\max_{h\in G_f^+} |X^{h\pi_p^{-1}(g_0)}| \operatorname{li}(x)+O\bigl(x\exp\bigl\{-c_K\sqrt{\ln x}\,\bigr\}\bigr) \\ &=\operatorname{li}(x)\frac{1}{|G_f^0|}\sum_{g_0\in G_f^0}\max_{h\in G_f^+} |X^{h\pi_p^{-1}(g_0)}|+O\bigl(x\exp\bigl\{-c_K\sqrt{\ln x}\,\bigr\}\bigr), \end{aligned}
\end{equation*}
\notag
$$
where $C$ in the first sum runs over all conjugacy classes of $G_f^0$. Next, $G_f^0=G_f/G_f^+$ and the value $\max_h |X^{hg}|$ depends only on the class of $g\in G_f$ in the quotient $G_f/G_f^+$. This means that the last sum is equal to $m(G_f,G_f^+;X)$. Therefore,
$$
\begin{equation*}
\sum_{p\leqslant x}M_p(f)=m(G_f,G_f^+;X)\operatorname{li}(x)+O\bigl(x\exp\bigl\{-c_K\sqrt{\ln x}\,\bigr\}\bigr)
\end{equation*}
\notag
$$
and, by partial summation, we obtain
$$
\begin{equation*}
\sum_{p\leqslant x}\frac{M_p(f)}{p}=m(G_f,G_f^+;X)\ln\ln x+O(1),
\end{equation*}
\notag
$$
which concludes the proof. Theorem 2 is proved. Remark 2. For a few natural examples, the number $m(G,H;X)$ turns out to be integer, at least when $H$ is normal in $G$ and actions of both $G$ and $H$ are faithful and transitive. However, there are examples of non-integrality: the group $G=S_4\times \mathbb Z/2\mathbb Z$ acts transitively on a set $X$ with $6$ elements. Taking $H=A_4$, we obtain $m(G,H;X)=7/2$. This example was found by P. Kosenko, who also managed to find some examples of non-integrality for $|X|$ equals $8$, $9$, and $10$. Incidentally, $S_4\times \mathbb Z/2\mathbb Z$ is the Galois group of generic even sextic polynomial. Unfortunately, we were not able to produce examples of polynomials $f(x)$ of degree $6$ with $G_f=S_4\times \mathbb Z/2\mathbb Z$ and $G_f^+=A_4$. Since now we have a tool for computation of $M(f)$, let us find $M(f)$ for $f_d$ and for a typical polynomial of degree $d$. We call a polynomial of degree $d$ generic if $G_f^+\cong S_d$. Theorem 3. Let $d$ be an integer. (i) $M(x^d)=\tau(d)$, where $\tau(d)$ is the divisor function. (ii) $M(f)=d$, for any generic polynomial $f(x)$ of degree $d$. Proof. To prove the first part, we note that, for $f(x)=x^d$, Indeed, in this case it is easy to see that if $y\neq 0$ and $x^d=y$ has at least one solution, then the number of solutions is equal to the number or $d$th roots of unity in $\mathbb F_p$. Next, using the identity we get, for any $x\geqslant 2$,
$$
\begin{equation*}
\sum_{p\leqslant x}\frac{M_p(f_d)}{p} =\sum_{p\leqslant x}\frac{(d,p-1)}{p}=\sum_{p\leqslant x} \frac{\sum_{d_1\,|\, (d,p-1)}\varphi(d_1)}{p} =\sum_{d_1\,|\, d}\varphi(d_1)\sum_{\substack{p\leqslant x\\ p\equiv 1\ (\operatorname{mod} {d_1})}}\frac{1}{p}.
\end{equation*}
\notag
$$
Next, from Prime Number Theorem for primes in arithmetic progressions we find
$$
\begin{equation*}
\sum_{\substack{p\leqslant x\\ p\equiv 1\ (\operatorname{mod} {d_1})}}\frac{1}{p}=\frac{\ln\ln x}{\varphi(d_1)}+O(1).
\end{equation*}
\notag
$$
Substituting this identity into the above formula, we get the desired identity: the factors $\varphi(d_1)$ and $1/\varphi(d_1)$ cancel out and we are left with the sum $\sum_{d_1\,|\, d}1=\tau(d)$. This proof does not rely on Theorem 2, but can be easily reformulated in terms of the natural action of the affine group $\mathrm{Aff}(\mathbb Z/ d\mathbb Z)$ on $\mathbb Z/d\mathbb Z$. Indeed, in our case $K=\mathbb Q(\zeta_d)$ is the cyclotomic field. Every automorphism of $\mathbb Q_f$ sends $\zeta_d$ to $\zeta_d^a$ for some $a\in (\mathbb Z/d\mathbb Z)^*$ and $y$ to $\zeta_d^b y$ for some $b\in \mathbb Z/d\mathbb Z$. The map $(a,b)\mapsto (x\mapsto ax+b)$ is an isomorphism $G_f\cong \mathrm{Aff}(\mathbb Z/d\mathbb Z)$. Since $G_f^+$ fixes $\zeta_d$, we also see that $G_f^+$ corresponds to the shift subgroup $y\mapsto y+b$ and is isomorphic to $\mathbb Z/d\mathbb Z$.
As for generic polynomials, we have $G_f^+\cong S_d$, hence $G_f=G_f^+$ and for all $g\in G_f$ as needed. Theorem 3 is proved.The paper [7] contains, among other things, some criteria for $f(x)$ to be generic. In particular, authors prove that if $f'(x)$ has simple roots and $f(\alpha)\neq f(\beta)$ for any two distinct roots, then $f(x)$ is generic. Of course, this means that the coefficients of any non-generic polynomial must satisfy a certain polynomial relation. This, in turn, implies that most polynomials of degree $d$ are generic. It is also clear that our proof of $M(f)=d$ for generic polynomials uses only $G_f=G_f^+$. Obviously, the latter condition is actually equivalent to $M(f)=d$. Since $G_f^0=G_f/ G_f^+$, it is also equivalent to $K=\mathbb Q$, that is, all the constants in $\mathbb Q_f$ must be rational. Let us call such polynomials ordinary. Currently, we are not aware of any simple way to test whether a given polynomial is ordinary, besides more narrow criteria of Birch and Swinnerton-Dyer. The polynomials that we call generic are called Morse functions by J.-P. Serre in his book on Galois theory (see § 4.4 in [8]). It is also mentioned that Hilbert established an isomorphism $G_f\cong S_n$ for all such polynomials, see also [9]. Similarly to the results on gaps between primes, our results imply the following. Corollary 2. For any $f(x)\in \mathbb Z[x]$, there exists a constant $c_f>0$ such that, for all $X\geqslant e^{16}$, there is a positive integer $n\leqslant X$ with $\Omega(n+f(m))>A(n)$ for all $1\leqslant m\leqslant Y$, where $\Omega$ is the number of prime factors counted with multiplicity, and $A(n)$ is the number of irreducible factors of $f(x)+n$. It is also worth noting that our proofs can be extended to integer-valued polynomials $f(x)$ which are not necessarily in $\mathbb Z[x]$. AcknowledgementsWe would like to thank Peter Kosenko for providing an abstract example of non-integrality of $m(G,H;X)$ (see Remark 2) and Mathoverflow user Joachim König for providing the main idea for the proof of Theorem 2: https://mathoverflow.net/a/430001/101078. We also thank anonymous referees for correcting several inaccuracies, especially in § 3, and for pointing out the references to Serre and Hilbert. 
Citation in format AMSBIB
\Bibitem{KalKon24} |
|
||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|