Izvestiya: Mathematics
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Guidelines for authors
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Izv. RAN. Ser. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Izvestiya: Mathematics, 2024, Volume 88, Issue 2, Pages 225–235
DOI: https://doi.org/10.4213/im9467e
(Mi im9467)
 

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
References:
Abstract: For a polynomial $f(x)\in \mathbb Z[x]$ we study an analogue of Jacobsthal function defined by $j_f(N) =\max_{m}\{$for some $x \in \mathbb N$ the inequality $(x+f(i),N)>1$ holds for all $i\leqslant m\}$. We prove the lower bound
$$ j_f(P(y))\gg y(\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)}, $$
where $P(y)$ is the product of all primes $p$ below $y$, $\ell_f$ is the number of distinct linear factors of $f(x)$, $h_f$ is the number of distinct non-linear irreducible factors and $M(f)$ is the average size of the maximal preimage of a point under a map $f\colon \mathbb F_p\to \mathbb F_p$. The quantity $M(f)$ is computed in terms of certain Galois groups.
Keywords: Jacobsthal function, sieve, polynomial, Galois group.
Funding agency Grant number
Ministry of Science and Higher Education of the Russian Federation 075-15-2022-265
This work was performed at the Steklov International Mathematical Center and supported by the Ministry of Science and Higher Education of the Russian Federation (agreement no. 075-15-2022-265). The first author was supported by the basic research program of the National Research University Higher School of Economics.
Received: 09.02.2023
Revised: 12.06.2023
Russian version:
Izvestiya Rossiiskoi Akademii Nauk. Seriya Matematicheskaya, 2024, Volume 88, Issue 2, Pages 33–43
DOI: https://doi.org/10.4213/im9467
Bibliographic databases:
Document Type: Article
UDC: 511.33+511.31+511.23
MSC: 11N25; 11N32
Language: English
Original paper language: English

§ 1. Introduction and main results

Let $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

$$ \begin{equation*} P(y)=\prod_{p\leqslant y}p. \end{equation*} \notag $$
Then
$$ \begin{equation*} j(P(y))\gg y\frac{\ln y\ln\ln\ln y}{\ln\ln y}=(1+o_{y\to \infty}(1))\ln P(y)\frac{\ln\ln P(y)\ln\ln\ln\ln P(y)}{\ln\ln\ln P(y)}. \end{equation*} \notag $$
In particular, for $X\geqslant e^{16}$,
$$ \begin{equation*} \max_{p_{n+1}\leqslant X}(p_{n+1}-p_n)\gg \ln X\frac{\ln\ln X\ln\ln\ln\ln X}{\ln\ln\ln X}. \end{equation*} \notag $$

As for the upper bounds for $j(N)$, Iwaniec showed [2] that the following holds.

Theorem B. For all natural $N$,

$$ \begin{equation*} j(N)\ll \ln^2 N. \end{equation*} \notag $$

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

$$ \begin{equation*} \sum_{p\leqslant X}\frac{M_p(f)}{p}=M\ln\ln X+O(1) \end{equation*} \notag $$
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$,

$$ \begin{equation*} \begin{aligned} \, j_f(P(y)) &\gg y(\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)} \\ &=(1+o_{y\to\infty}(1))\ln P(y)(\ln\ln P(y))^{\ell_f-1} \\ &\qquad\times\biggl(\frac{(\ln\ln\ln P(y))^2}{\ln\ln\ln\ln P(y)}\biggr)^{h_f} \biggl(\frac{\ln\ln P(y)\ln\ln\ln\ln P(y)}{(\ln\ln\ln P(y))^2}\biggr)^{M(f)}. \end{aligned} \end{equation*} \notag $$

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

$$ \begin{equation*} j_f(P(y))\gg y\frac{(\ln\ln y)^2}{\ln\ln\ln y}\frac{\ln y\ln\ln\ln y}{(\ln\ln y)^2}=y\ln y. \end{equation*} \notag $$
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

$$ \begin{equation*} m(G,H;X)=\frac{1}{|G|}\sum_{g\in G}\max_{h\in H}|X^{hg}|. \end{equation*} \notag $$

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

$$ \begin{equation*} M(f)=m(G_f,G_f^+;X). \end{equation*} \notag $$

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 theorem

To 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)$,

$$ \begin{equation*} \sum_{n\equiv 0\ (\operatorname{mod} d)}a_n=g(d)X/d+r_d, \end{equation*} \notag $$
where $g(d)$ is a multiplicative function with $g(p)\leqslant \kappa$, $g(p)<p$ for all primes $p$, $|r_d|\leqslant g(d)$ and $z\ll X$. Then
$$ \begin{equation*} \mathcal S(a,z)=\sum_{(n,P(z))=1}a_n\ll_{\kappa} XV(z), \end{equation*} \notag $$
where
$$ \begin{equation*} V(z)=\prod_{p\leqslant z}\biggl(1-\frac{g(p)}{p}\biggr). \end{equation*} \notag $$

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

$$ \begin{equation*} S(X,\Omega)\ll XV(z). \end{equation*} \notag $$

Proof. To see this, we set, for any $p\leqslant z$,
$$ \begin{equation*} P(z;p)=\frac{P(z)}{p} \end{equation*} \notag $$
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$,

$$ \begin{equation*} \sum_{p\leqslant x}\frac{r_p(f)}{p}=\ln\ln x+c_1+O\bigl(\exp\bigl\{-c_2\sqrt{\ln x} \,\bigr\}\bigr). \end{equation*} \notag $$

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
$$ \begin{equation*} f(i)+x_p\equiv 0 \pmod p. \end{equation*} \notag $$
For the first step, let us choose
$$ \begin{equation*} x_p=0 \ \text{ for }\ p\leqslant z_0\ \text{ and for }\ z_1<p<\frac{y}2. \end{equation*} \notag $$
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
$$ \begin{equation*} \Psi(O(m),z_1)\ll \frac{m}{(\ln y)^{\ell_f+M(f)+2}}=o\biggl(\frac{y}{\ln y}\biggr). \end{equation*} \notag $$
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

$$ \begin{equation*} R\leqslant \frac{y}{3\ln y} \end{equation*} \notag $$
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
$$ \begin{equation*} S(m,\Omega)\leqslant \frac{y}{4\ln y}, \end{equation*} \notag $$
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

$$ \begin{equation*} m_np+O(\sqrt p\,). \end{equation*} \notag $$

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

$$ \begin{equation*} \sigma_{\mathfrak p}x\equiv x^p \pmod{\mathfrak{p}} \end{equation*} \notag $$
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$,

$$ \begin{equation*} \pi(x;G_K,C)=\frac{|C|}{|G_K|}\operatorname{li}(x)+O\bigl(x\exp\bigl\{-c_K\sqrt{\ln x}\,\bigr\}\bigr). \end{equation*} \notag $$

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
$$ \begin{equation*} gh_2(x_1,\dots,x_n)=h_1(x_1,\dots,x_n). \end{equation*} \notag $$
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$,
$$ \begin{equation*} M_p(f)=(p-1,d). \end{equation*} \notag $$
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
$$ \begin{equation*} (d,p-1)=\sum_{d_1\,|\, (d,p-1)}\varphi(d_1), \end{equation*} \notag $$
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$

$$ \begin{equation*} \max_{h\in G_f^+}|X^{gh}|=|X^e|=d, \end{equation*} \notag $$
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

$$ \begin{equation*} Y=c_f\ln X(\ln\ln X)^{\ell_f-1}\biggl(\frac{(\ln\ln\ln X)^2}{\ln\ln\ln\ln X}\biggr)^{h_f} \biggl(\frac{\ln\ln X\ln\ln\ln\ln X}{(\ln\ln\ln X)^2}\biggr)^{M(f)}, \end{equation*} \notag $$
$\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]$.

Acknowledgements

We 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.


Bibliography

1. K. Ford, B. Green, S. Konyagin, J. Maynard, and T. Tao, “Long gaps between primes”, J. Amer. Math. Soc., 31:1 (2018), 65–105  crossref  mathscinet  zmath
2. H. Iwaniec, “On the problem of Jacobsthal”, Demonstr. Math., 11:1 (1978), 225–231  crossref  mathscinet  zmath
3. R. A. Rankin, “The difference between consecutive prime numbers”, J. London Math. Soc., 13:4 (1938), 242–247  crossref  mathscinet  zmath
4. R. Dietmann, C. Elsholtz, A. Kalmynin, S. Konyagin, and J. Maynard, “Longer gaps between values of binary quadratic forms”, Int. Math. Res. Not. IMRN, 2023:12 (2023), 10313–10349  mathnet  crossref  mathscinet  zmath
5. H. Halberstam and H.-E. Richert, Sieve methods, London Math. Soc. Monogr., 4, Academic Press, Inc., London–New York, 1974  mathscinet  zmath
6. J. C. Lagarias and A. M. Odlyzko, “Effective versions of the Chebotarev density theorem”, Algebraic number fields: L-functions and Galois properties (Univ. Durham, Durham, 1975), Academic Press, Inc., London–New York, 1977, 409–464  mathscinet  zmath
7. B. J. Birch and H. P. F. Swinnerton-Dyer, “Note on a problem of Chowla”, Acta Arith., 5 (1959), 417–423  crossref  mathscinet  zmath
8. J.-P. Serre, Topics in Galois theory, Res. Notes Math., 1, 2nd ed., A. K. Peters, Wellesley, MA, 2007  mathscinet  zmath
9. D. Hilbert, “Ueber die Irreduбibilität ganzer rationaler Funбtionen mit ganzzahligen ‘oeffiбienten”, J. Reine Angew. Math., 1892:110 (1892), 104–129  crossref  mathscinet  zmath

Citation: A. B. Kalmynin, S. V. Konyagin, “A polynomial analogue of Jacobsthal function”, Izv. RAN. Ser. Mat., 88:2 (2024), 33–43; Izv. Math., 88:2 (2024), 225–235
Citation in format AMSBIB
\Bibitem{KalKon24}
\by A.~B.~Kalmynin, S.~V.~Konyagin
\paper A polynomial analogue of Jacobsthal function
\jour Izv. RAN. Ser. Mat.
\yr 2024
\vol 88
\issue 2
\pages 33--43
\mathnet{http://mi.mathnet.ru/im9467}
\crossref{https://doi.org/10.4213/im9467}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4727548}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2024IzMat..88..225K}
\transl
\jour Izv. Math.
\yr 2024
\vol 88
\issue 2
\pages 225--235
\crossref{https://doi.org/10.4213/im9467e}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=001202745700002}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85193736120}
Linking options:
  • https://www.mathnet.ru/eng/im9467
  • https://doi.org/10.4213/im9467e
  • https://www.mathnet.ru/eng/im/v88/i2/p33
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Известия Российской академии наук. Серия математическая Izvestiya: Mathematics
    Statistics & downloads:
    Abstract page:497
    Russian version PDF:25
    English version PDF:63
    Russian version HTML:51
    English version HTML:227
    References:28
    First page:11
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024