1 Introduction

For a prime \(p\), let \({\mathbb F}_p\) denote the finite field with \(p\) elements, which we always assume to be represented by the set \(\{0, \ldots , p-1\}\).

Given a rational function

$$\begin{aligned} \psi (X) = \frac{f(X)}{g(X)}\in {\mathbb F}_p(X) \end{aligned}$$

where \(f, g\in {\mathbb F}_p[X]\) are relatively prime polynomials, and an ‘interesting’ set \({\mathcal S}\subseteq {\mathbb F}_p\), it is natural to ask how the value set

$$\begin{aligned} \psi ({\mathcal S}) = \{\psi (x){:}\;x \in {\mathcal S}, \ g(x) \ne 0\} \end{aligned}$$

is distributed. For instance, given another ‘interesting’ set \({\mathcal T}\), our goal is to obtain nontrivial bounds on the size of the intersection

$$\begin{aligned} N_\psi ({\mathcal S},{\mathcal T}) = \#\left( \psi ({\mathcal S}) \cap {\mathcal T}\right) . \end{aligned}$$

In particular, we are interested in the cases when \(N_\psi ({\mathcal S},{\mathcal T})\) achieves the trivial upper bound

$$\begin{aligned} N_\psi ({\mathcal S},{\mathcal T}) \le \min \{\#{\mathcal S}, \# {\mathcal T}\}. \end{aligned}$$

Typical examples of such sets \({\mathcal S}\) and \({\mathcal T}\) are given by intervals \({\mathcal I}\) of consecutive integers and multiplicative subgroups \({\mathcal G}\) of \({\mathbb F}_p^*\). For large intervals and subgroups, a standard application of bounds of exponential and multiplicative character sums leads to asymptotic formulas for the relevant values of \(N_\psi ({\mathcal S},{\mathcal T})\), see [7, 11, 19]. Thus only the case of small intervals and groups is of interest.

For a polynomial \(f \in {\mathbb F}_p[X]\) and two intervals \({\mathcal I}= \{u+1, \ldots , u+H\}\) and \({\mathcal J}= \{v+1, \ldots , v+H\}\) of \(H\) consecutive integers, various bounds on the cardinality of the intersection \(f({\mathcal I}) \cap {\mathcal J}\) are given in [7, 11]. To present some of these results, for positive integers \(d\), \(k\) and \(H\), we denote by \(J_{d,k}(H)\) the number of solutions to the system of equations

$$\begin{aligned} x_1^{\nu }+\cdots +x_k^{\nu }=x_{k+1}^{\nu }+\cdots +x_{2k}^{\nu }, \quad \nu = 1, \ldots , d, \end{aligned}$$

in positive integers \(x_1,\ldots ,x_{2k}\le H\). Then by [11, Theorem 1], for any \(f \in {\mathbb F}_p[X]\) of degree \(d \ge 2\) and two intervals \({\mathcal I}\) and \({\mathcal J}\) of \(H<p\) consecutive integers, we have

$$\begin{aligned} N_f({\mathcal I},{\mathcal J}) \le H (H/p)^{1/2\kappa (d)+o(1)} + H^{1- (d-1)/2\kappa (d)+o(1)}, \end{aligned}$$

as \(H\rightarrow \infty \), where \(\kappa (d)\) is the smallest integer \(\kappa \) such that for \(k \ge \kappa \) there exists a constant \(C(d,k)\) depending only on \(k\) and \(d\) and such that

$$\begin{aligned} J_{d,k}(H) \le C(d,k) H^{2k - d(d+1)/2+o(1)} \end{aligned}$$

holds as \(H\rightarrow \infty \), see also [7] for some improvements and results for related problems. In [7, 11] the bounds of Wooley [22, 23] are used that give the presently best known estimates on \(\kappa (d)\) (at least for a large \(d\)), see also [24] for further progress in estimating \(\kappa (d)\).

It is easy to see that the argument of the proof of [11, Theorem 1] allows to consider intervals of \({\mathcal I}\) and \({\mathcal J}\) of different lengths as well and for intervals

$$\begin{aligned} {\mathcal I}= \{u+1, \ldots , u+H\} \quad \text{ and }\quad {\mathcal J}= \{v+1, \ldots , v+K\} \end{aligned}$$

with \(1 \le H, K < p\) it leads to the bound

$$\begin{aligned} N_f({\mathcal I},{\mathcal J}) \le H^{1+o(1)} \left( (K/p)^{1/2\kappa (d)} + (K/H^d)^{1/2\kappa (d)}\right) , \end{aligned}$$

see also a more general result of Kerr [15, Theorem 3.1] that applies to multivariate polynomials and to congruences modulo a composite number.

Furthermore, let \(K_\psi (H)\) be the smallest \(K\) for which there are intervals \({\mathcal I}= \{u+1, \ldots , u+H\}\) and \({\mathcal J}= \{v+1, \ldots , v+K\}\) for which \(N_\psi ({\mathcal I},{\mathcal J}) = \#{\mathcal I}\). That is, \(K_\psi (H)\) is the length of the shortest interval, which may contain \(H\) consecutive values of \(\psi \in {\mathbb F}_p(X)\) of degree \(d\).

Defining \(\kappa ^*(d)\) in the same way as \(\kappa (d)\), however with respect to the more precise bound

$$\begin{aligned} J_{d,k}(H) \le C(d,k) H^{2k - d(d+1)/2} \end{aligned}$$

[that is, without \(o(1)\) in the exponent] we can easily derive that for any polynomial \(f \in {\mathbb F}_p[X]\) of degree \(d\),

$$\begin{aligned} K_f(H) \ge c(d) H^d, \end{aligned}$$
(1)

for some constant \(c(d)> 0\) that depends only on \(d\). To see that the bound (1) is optimal it is enough to take \(f(X) = X^d\) and \(u=0\). Note that the proof of (1) depends only on the existence of \(\kappa ^*(d)\) rather than on its specific bounds. However, we recall that Wooley [22, Theorem 1.2] shows that for some constant \(\mathfrak S(d,k)> 0\) depending only on \(d\) and \(k\) we have

$$\begin{aligned} J_{d,k}(H) \sim \mathfrak S(d,k) H^{2k - d(d+1)/2} \end{aligned}$$

for any fixed \(d\ge 3\) and \(k\ge d^2 + d + 1\). In particular, \(\kappa ^*(d) \le d^2 + d + 1\).

Here we concentrate on estimating \(N_\psi ({\mathcal I}, {\mathcal G})\) for an interval \({\mathcal I}\) of \(H\) consecutive integers and a multiplicative subgroup \({\mathcal G}\subseteq {\mathbb F}_p^*\) of order \(T\). This question has been mentioned in [11, Section 4] as an open problem.

We remark that for linear polynomials \(f\) the result of [4, Corollary 34] have a natural interpretation as a lower bound on the order of a subgroup \({\mathcal G}\subseteq {\mathbb F}_p^*\) for which \(N_f({\mathcal I}, {\mathcal G}) = \#{\mathcal I}\). In particular, we infer from [4, Corollary 34] that for any linear polynomials \(f(X) = aX + b\in {\mathbb F}_p[X]\) and fixed integer \(\nu =1, 2, \ldots \), for an interval \({\mathcal I}\) of \(H \le p^{1/(\nu ^2-1)}\) consecutive integers and a subgroup \({\mathcal G}\), the equality \(N_f({\mathcal I}, {\mathcal G}) = \#{\mathcal I}\) implies \(\# {\mathcal G}\ge H^{\nu + o(1)}\).

We also remark that the results of [5, Section 5] have a similar interpretation for the identity \(N_f({\mathcal I}, {\mathcal G}) = \#{\mathcal I}\) with linear polynomials, however apply to almost all primes \(p\) (rather than to all primes).

Furthermore, a result of Bourgain [3, Theorem 2] gives a nontrivial bound on the intersection of an interval centered at \(0\), that is, of the form \({\mathcal I}= \{0, \pm 1, \ldots , \pm H\}\) and a co-set \(a{\mathcal G}\) (with \(a \in {\mathbb F}_p^*\)) of a multiplicative group \({\mathcal G}\subseteq {\mathbb F}_p^*\), provided that \(H < p^{1-\varepsilon }\) and \(\#{\mathcal G}\ge g_0(\varepsilon )\), for some constant \(g_0(\varepsilon )\) depending only on an arbitrary \(\varepsilon > 0\).

We note that several bounds on \( \#\left( f({\mathcal G}) \cap {\mathcal G}\right) \) for a multiplicative subgroup \({\mathcal G}\subseteq {\mathbb F}_p^*\) are given in [19], but they apply only to polynomials \(f\) defined over \({\mathbb Z}\) and are not uniform with respect to the height (that is, the size of the coefficients) of \(f\). Thus the question of estimating \(N_f({\mathcal G}, {\mathcal G})\) remains open. On the other hand, a number of results about points on curves and algebraic varieties with coordinates from small subgroups, in particular, in relation to the Poonen Conjecture, have been given in [6, 8–10, 17, 18, 20, 21].

We recall that the notations \(U = O(V)\), \(U \ll V\) and \(V \gg U\) are all equivalent to the statement that the inequality \(|U| \le c\,V\) holds with some constant \(c> 0\). Throughout the paper, any implied constants in these symbols may occasionally depend, where obvious, on \(d=\deg f\) and \(e=\deg g\), but are absolute otherwise.

2 Preparations

2.1 Absolute irreducibility of some polynomials

As usual, we use \(\overline{{\mathbb F}}_p\) to denote the algebraic closure of \({\mathbb F}_p\) and \(X, Y\) to denote indeterminate variables. We also use \(\overline{{\mathbb F}}_p(X)\), \(\overline{{\mathbb F}}_p(Y)\), \(\overline{{\mathbb F}}_p(X,Y)\) to denote the corresponding fields of rational functions over \(\overline{{\mathbb F}}_p\).

We recall that the degree of a rational function in the variables \(X,Y\)

$$\begin{aligned} F(X,Y) = \frac{s(X,Y)}{t(X,Y)}\in \overline{{\mathbb F}}_p(X,Y),\quad \gcd (s(X,Y), t(X,Y))= 1, \end{aligned}$$

is \(\deg F= \max \{\deg s, \deg t\}\).

It is also known that if \(R(X)\in \overline{{\mathbb F}}_p(X)\) is a rational function then

$$\begin{aligned} \deg (R\circ F) = \deg R \deg F, \end{aligned}$$
(2)

where \(\circ \) denotes the composition.

We use the following result of Bodin [1, Theorem 5.3] adapted to our purposes. Also, see [16] for results in fields of zero characteristic.

Lemma 1

Let \(s(X,Y),t(X,Y)\in {\mathbb F}_p[X,Y]\) be polynomials such that there does not exist a rational function \(R(X)\in \overline{{\mathbb F}}_p(X)\) with \(\deg R > 1\) and a bivariate rational function \(G(X,Y)\in \overline{{\mathbb F}}_p[X,Y]\) such that,

$$\begin{aligned} F(X,Y) = \frac{s(X,Y)}{t(X,Y)} = R(G(X,Y)). \end{aligned}$$

The number of elements \(\lambda \) such that the polynomial \(s(X,Y)-\lambda t(X,Y)\) is reducible over \(\overline{{\mathbb F}}_p[X,Y]\) is at most \((\deg F)^2\).

We say that a rational function \(f\in \overline{{\mathbb F}}_p(X)\) is a perfect power of another rational function if and only if \(f(X) = (g(X))^n\) for some rational function \(g(X)\in \overline{{\mathbb F}}_p(X)\) and integer \(n\ge 2\). Because \(\overline{{\mathbb F}}_p\) is an algebraic closed field, it is trivial to see that if \(f(X)\) is a perfect power, then \(af(X)\) is also a perfect power for any \(a\in \overline{{\mathbb F}}_p\). We need the following easy technical lemma.

Lemma 2

Let \(P_1(X), Q_1(X)\in \overline{{\mathbb F}}_p[X]\) and \(P_2(Y),Q_2(Y)\in \overline{{\mathbb F}}_p[Y]\) be two pairs of relatively prime polynomials. Then the following bivariate polynomial

$$\begin{aligned} F_{r,s}(X,Y) = r P_1(X)Q_2(Y) - s Q_1(X)P_2(Y),\quad \end{aligned}$$

is not divisible by any univariate polynomial for all \(r,s\in \overline{{\mathbb F}}_p^*\),

Proof

Suppose that this polynomial is divisible by an univariate polynomial \(d(X)\). Take any root \(\alpha \in \overline{{\mathbb F}}_p\) of the polynomial \(d\) and substitute \(X = \alpha \) in \(F_{r,s}(X,Y)\), getting

$$\begin{aligned} r P_1(\alpha )Q_2(Y) - s Q_1(\alpha )P_2(Y) =0. \end{aligned}$$

Here, we have two different possibilities:

  • If \( r P_1(\alpha )=0\), then \(Q_1(\alpha )=0\), and we get a contradiction,

  • In other case, \(\gcd (Q_2(Y),P_2(Y))\ne 1\), contradicting our hypothesis.

This finishes the proof. \(\square \)

Now, we prove the following result about irreducibility.

Lemma 3

Given relatively prime polynomials \( f,g\in \overline{{\mathbb F}}_p[X]\) and if a rational function \(f(X)/g(X)\in \overline{{\mathbb F}}_p(X)\) of degree \(D\ge 2\) is not a perfect power then \(f(X)g(Y) - \lambda f(Y)g(X)\) is reducible over \(\overline{{\mathbb F}}_p[X,Y]\) for at most \(4D^2\) values of \(\lambda \in \overline{{\mathbb F}}_p^*\).

Proof

First we describe the idea of the proof. Our aim is to show that the condition of Lemma 1 holds for the polynomial \(f(X)g(Y)-\lambda f(Y)g(X)\). Indeed, we show that if

$$\begin{aligned} \frac{f(X)g(Y)}{g(X)f(Y)} = R(G(X,Y)), \end{aligned}$$
(3)

with a rational function \(R\in \overline{{\mathbb F}}_p(X)\) of degree \(\deg R\ge 2\) and a bivariate rational function \(G(X,Y) \in \overline{{\mathbb F}}_p(X,Y)\), then there exists another \(\widetilde{R}\in \overline{{\mathbb F}}_p(X)\) and \(\widetilde{G}(X,Y) \in \overline{{\mathbb F}}_p(X,Y)\)

$$\begin{aligned} \frac{f(X)g(Y)}{g(X)f(Y)} = \left( \widetilde{R}\left( \widetilde{G}(X,Y)\right) \right) ^m, \end{aligned}$$

for an appropriate integer \(m\ge 2\). Comparing coefficients, it is easy to arrive at the conclusion that \(f(X)/g(X)\) is a perfect power.

Without loss of generality, we suppose \(R(0)=0\). Indeed, we can take any root of \(R(X)\) and replace \(R(X)\) with \(R(X+\alpha )\) and \(G(X,Y)\) with \(G(X,Y)-\alpha \).

So, indeed we have

$$\begin{aligned} R(X) = a \frac{X\prod _{i=2}^{k} (X-r_i)}{\prod _{j=1}^{m} (X-s_j)}. \end{aligned}$$

Writing \(G(X,Y)= G_1(X,Y)/G_2(X,Y)\) in its lowest terms and by hypothesis, we have that the fraction on the right of this inequality,

$$\begin{aligned} \frac{f(X)g(Y)}{g(X)f(Y)}&= a \frac{G_2(X,Y)^{N-k}}{G_2(X,Y)^{N-m}}\\&\times \frac{G_1(X,Y)\prod _{i=2}^{k} (G_1(X,Y)-r_i(G_2(X,Y))}{\prod _{j=1}^{m} (G_1(X,Y)-s_jG_2(X,Y))}, \end{aligned}$$

where

$$\begin{aligned} N = \max \{k,m\} \end{aligned}$$

is in its lowest terms. This means that \(G_1(X,Y) = P_1(X)P_2(Y)\) and \(G_2(X,Y) = s_1^{-1}(P_1(X)P_2(Y)-Q_1(X)Q_2(Y))\), where \(P_1,P_2,Q_1, Q_2\) are divisors of \(f\) or \( g\). Because \(\gcd (G_1(X,Y),G_2(X,Y)) = 1\), we have that

$$\begin{aligned} \gcd (P_1(X),Q_1(X))=\gcd (P_2(Y),Q_2(Y))=1. \end{aligned}$$

Lemma 2 implies that \(m= k\) as otherwise \(G_2(X,Y)\) is divisible by an univariate polynomial. This implies,

$$\begin{aligned} \frac{f(X)g(Y)}{g(X)f(Y)} = a \frac{G_1(X,Y)\prod _{i=2}^{m} (G_1(X,Y)-r_iG_2(X,Y))}{\prod _{j=1}^{m} (G_1(X,Y)-s_jG_2(X,Y))}. \end{aligned}$$

Now, suppose that there exists another value

$$\begin{aligned} s\in \{r_2,\ldots , r_m,s_2,\ldots , s_m\}, \quad s\ne 0,s_1. \end{aligned}$$

Then, the following polynomial

$$\begin{aligned} G_1(X,Y)-sG_2(X,Y) = \left( 1-s s_1^{-1}\right) P_1(X)P_2(Y) + s_1^{-1}Q_1(X)Q_2(Y) \end{aligned}$$

is divisible by an univariate polynomial which contradicts Lemma 2. So, this means that \(R(X)\) can be written in the following form,

$$\begin{aligned} R(X) = \left( \frac{X}{X-s_1}\right) ^{m}, \end{aligned}$$

and this concludes the proof. \(\square \)

Notice that the condition that \(f(X)/g(X)\) is not a perfect power of a polynomial is necessary, indeed if \(f(X) = (h(X))^n\) and \(g(X)=1\) with \(f(X), h(X) \in \overline{{\mathbb F}}_p[X]\) then \(f(X) - \lambda ^n f(Y)\) is divisible by \(h(X)-\lambda h(Y)\) for any \(\lambda \in \overline{{\mathbb F}}_p\).

2.2 Integral points on affine curves

We need the following estimate of Bombieri and Pila [2] on the number of integral points on polynomial curves.

Lemma 4

Let \({\mathcal C}\) be a plane absolutely irreducible curve of degree \(n\ge 2\) and let \(H\ge \exp (n^6)\). Then the number of integral points on \({\mathcal C}\) inside of the square \([0,H]\times [0,H]\) is at most \(H^{1/n}\exp (12\sqrt{n\log H\log \log H})\).

2.3 Small values of linear functions

We need a result about small values of residues modulo \(p\) of several linear functions. Such a result has been derived in [12, Lemma 3.2] from the Dirichlet pigeon-hole principle. Here use a slightly more precise and explicit form of this result which is derived in [13] from the Minkowski theorem.

First we recall some standard notions of the theory of geometric lattices.

Let \({\mathbf {b}}_1,\ldots ,{\mathbf {b}}_r\) be \(r\) linearly independent vectors in \({{\mathbb R}}^s\). The set

$$\begin{aligned} {\mathcal L}=\{\mathbf {z} : \mathbf {z}=c_1\mathbf {b}_1+\cdots + c_r\mathbf {b}_r,\quad c_1, \ldots , c_r\in {\mathbb Z}\} \end{aligned}$$

is called an \(r\) -dimensional lattice in \({\mathbb R}^s\) with a basis \(\{ {\mathbf {b}}_1,\ldots , {\mathbf {b}}_r\}\).

To each lattice \({\mathcal L}\) one can naturally associate its volume

$$\begin{aligned} {\mathrm {vol\,}}{{\mathcal L}} = \left( \det \left( B^tB\right) \right) ^{1/2}, \end{aligned}$$

where \(B\) is the \(s\times r\) matrix whose columns are formed by the vectors \({\mathbf {b}}_1,\ldots ,{\mathbf {b}}_r\) and \(B^t\) is the transposition of \(B\). It is well known that \({\mathrm {vol\,}}{{\mathcal L}}\) does not depend on the choice of the basis \(\{{\mathbf {b}}_1,\ldots ,{\mathbf {b}}_r\}\), we refer to [14] for a background on lattices.

For a vector \(\mathbf {u}\), let

$$\begin{aligned} \Vert \mathbf {u}\Vert _\infty = \max \{|u_1|, \ldots , |u_s|\} \end{aligned}$$

denote its infinity norm of \(\mathbf {u}= (u_1, \ldots , u_s) \in {\mathbb R}^s\).

The famous Minkowski theorem, see [14, Theorem 5.3.6], gives an upper bound on the size of the shortest nonzero vector in any \(r\)-dimensional lattice \({\mathcal L}\) in terms of its volume.

Lemma 5

For any \(r\)-dimensional lattice \({\mathcal L}\) we have

$$\begin{aligned} \min \left\{ \Vert \mathbf {z}\Vert _\infty :\ \mathbf {z} \in {\mathcal L}\setminus \{\mathbf {0}\}\right\} \le \left( {\mathrm {vol\,}}{{\mathcal L}}\right) ^{1/r}. \end{aligned}$$

For an integer \(a\) we use \({\left\langle a\right\rangle }_p\) to denote the smallest by absolute value residue of \(a\) modulo \(p\), that is

$$\begin{aligned} {\left\langle a\right\rangle }_p = \min _{k\in {\mathbb Z}} |a - kp|. \end{aligned}$$

The following result is essentially contained in [13, Theorem 2]. We include here a short proof.

Lemma 6

For any real numbers \(V_1,\ldots , V_{s} \) with

$$\begin{aligned} p> V_1,\ldots , V_{s} \ge 1 \quad \text{ and }\quad V_1\ldots V_{s} > p^{s-1} \end{aligned}$$

and integers \(b_1, \ldots , b_{s}\), there exists an integer \(v\) with \(\gcd (v,p) =1\) such that

$$\begin{aligned} {\left\langle b_i v\right\rangle }_p \le V_i, \quad i =1, \ldots , s. \end{aligned}$$

Proof

Without loss of the generality, we can take \(b_1=1\). We introduce the following notation,

$$\begin{aligned} V = \prod _{i=1}^{s}V_i \end{aligned}$$
(4)

and consider the lattice \({\mathcal L}\) generated by the columns of the following matrix

$$\begin{aligned} B = \left( \begin{matrix} b_sV/V_s &{} 0 &{}\ldots &{}0 &{} pV/V_s \\ b_{s-1}V/V_{s-1} &{} 0 &{}\ldots &{} pV/V_{s-1} &{} 0 \\ \vdots &{} \vdots &{}\vdots &{}\vdots &{} \vdots \\ b_2V/V_2 &{} pV/V_2 &{} \ldots &{} 0 &{} 0\\ V/V_1 &{} 0 &{} \ldots &{}0 &{} 0\\ \end{matrix}\right) . \end{aligned}$$

Clearly the volume of \({\mathcal L}\) is

$$\begin{aligned} {\mathrm {vol\,}}{{\mathcal L}} = \frac{V}{V_1} \prod _{j=2}^s \frac{pV}{V_j} = V^{s-1}p^{s-1} \le V^s \end{aligned}$$

by (4) and the conditions on the size of the product \(V_1\ldots V_{s}\). Consider a nonzero vector with the minimum infinity norm inside \({\mathcal L}\). By the definition of \({\mathcal L}\), this vector is a linear combination of the columns of \(B\) with integer coefficients, that is, it can be written in the following way

$$\begin{aligned} \left( \frac{c_1V}{V_1}, \frac{(c_1b_2+c_2p)V}{V_2},\ldots , \frac{(c_1b_s+c_sp)V}{V_s}\right) ,\quad c_1,\ldots , c_s\in {\mathbb Z}. \end{aligned}$$

By Lemma 5 and the bound on the volume of \({\mathcal L}\), the following inequality holds,

$$\begin{aligned} \max \left\{ \left| \frac{c_1V}{V_1}\right| , \left| \frac{(c_1b_2+c_2p)V}{V_2}\right| ,\ldots , \left| \frac{(c_1b_s+c_sp)V}{V_s}\right| \right\} \le V. \end{aligned}$$

From here, it is trivial to check that if we choose \(v = c_1\), then

  • \({\left\langle v\right\rangle }_p= {\left\langle c_1\right\rangle }_p \le V_1\),

  • \({\left\langle v b_i\right\rangle }_p = {\left\langle c_1 b_i\right\rangle }_p \le V_i, \quad i =2, \ldots , s\),

which finishes the proof. \(\square \)

3 Main results

Theorem 7

Let \(\psi (X) = f(X)/g(X)\) where \(f,g\in {\mathbb F}_p[X]\) relatively prime polynomials of degree \(d\) and \(e\) respectively with \(d+e\ge 1\). We define

$$\begin{aligned} \ell = \min \{d,e\}, \quad m = \max \{d,e\} \end{aligned}$$

and set

$$\begin{aligned} k=(\ell +1)\left( \ell m - \ell ^2 + m^2 + m\right) \quad \text{ and }\quad s = 2m\ell +2m- \ell ^2. \end{aligned}$$

Assume that \(\psi \) is not a perfect power of another rational function over \(\overline{{\mathbb F}}_p\). Then for any interval \({\mathcal I}\) of \(H\) consecutive integers and a subgroup \({\mathcal G}\) of \({\mathbb F}_p^*\) of order \(T\), we have

$$\begin{aligned} N_\psi ({\mathcal I}, {\mathcal G})\ll (1 + H^{\rho } p^{-\vartheta }) H^{\tau +o(1)} T^{1/2}, \end{aligned}$$

where

$$\begin{aligned} \vartheta = \frac{1}{2s}, \quad \rho = \frac{k}{2s}, \quad \tau = \frac{1}{2(\ell +m)}, \end{aligned}$$

and the implied constant depends on \(d\) and \(e\).

Proof

Clearly we can assume that

$$\begin{aligned} H \le c p^{2\vartheta /(2\rho -1)} \end{aligned}$$
(5)

for some constant \(c>0\) which may depend on \(d\) and \(e\) as otherwise one easily verifies that

$$\begin{aligned} H^{\rho +\tau }p^{-\vartheta } \ge H^{\rho } p^{-\vartheta }\gg H^{1/2}, \end{aligned}$$

and hence the desired bound is weaker than the trivial estimate

$$\begin{aligned} N_\psi ({\mathcal I}, {\mathcal G})\ll \min \{H,T\} \le H^{1/2} T^{1/2}. \end{aligned}$$

Making the transformation \(X \mapsto X+u\), we can assume that \({\mathcal I}= \{1, \ldots , H\}\). Let \(1 \le x_1 < \cdots < x_r \le H\) be all \(r=N_\psi ({\mathcal I}, {\mathcal G})\) values of \(x \in {\mathcal I}\) with \(\psi (x) \in {\mathcal G}\).

Let \(\Lambda \) be the set of exceptional values of \(\lambda \in \overline{{\mathbb F}}_p\) described in Lemma 3. We see that there are only at most \(4m^3r\) pairs \((x_i,x_j)\), \(1 \le i,j \le r\), for which \(\psi (x_i)/\psi (x_j)\in \Lambda \). Indeed, if \(x_j\) is fixed, then \(\psi (x_i)\) can take at most \(4m^2\) values of the form \(\lambda \psi (x_j)\), with \(\lambda \in \Lambda \),

Furthermore, each value \(\lambda \psi (x_j)\) can be taken by \(\psi (x_i)\) for at most \(D\) possible values of \(i=1, \ldots , r\).

We now assume that \(r > 8m^3\) as otherwise there is nothing to prove. Therefore, there is \(\lambda \in {\mathcal G}\setminus \Lambda \) such that

$$\begin{aligned} \psi (x) \equiv \lambda \psi (y) \pmod p \end{aligned}$$
(6)

for at least

$$\begin{aligned} \frac{r^2 -4m^3r}{T} \ge \frac{r^2}{2T} \end{aligned}$$
(7)

pairs \((x,y)\) with \(x,y \in \{1, \ldots , H\}\).

Let

$$\begin{aligned} f(X)g(Y) - \lambda f(Y) g(X) = \sum _{i=0}^m \sum _{j=0}^m b_{i,j} X^iY^j. \end{aligned}$$

Let

$$\begin{aligned} {\mathcal H}=\{(i,j){:}\;i,j=0, \ldots , m, \ i+j \ge 1, \min \{i,j\} \le \ell \}. \end{aligned}$$

Clearly the noncostant terms \(b_{i,j} X^iY^j\) of \(f(X)g(Y) - \lambda f(Y) g(X)\) are supported only on the subscripts \((i,j) \in {\mathcal H}\). We have

$$\begin{aligned} \#{\mathcal H}= 2(m+1)(\ell +1) - (\ell +1)^2 -1 = s \end{aligned}$$

We now apply Lemma 6 with \(s = \# {\mathcal H}\) and the vector \(\left( b_{i,j}\right) _{(i,j) \in {\mathcal H}}\).

We also define the quantities \(U\) and \(V_{i,j}\), \((i,j) \in {\mathcal H}\) by the relations

$$\begin{aligned} V_{i,j}H^{i+j} = U, \quad (i,j) \in {\mathcal H}, \end{aligned}$$

thus

$$\begin{aligned} \prod _{(i,j) \in {\mathcal H}} V_{i,j} = 2p^{s-1}. \end{aligned}$$

By Lemma 6 there is an integer \(v\) with \(\gcd (v,p)=1\) such that

$$\begin{aligned} {\left\langle b_{i,j}v\right\rangle }_p \le V_{i,j} \end{aligned}$$

for every \((i,j) \in {\mathcal H}\).

We have

$$\begin{aligned} \sum _{(i,j) \in {\mathcal H}} (i +j)&= 2 \sum _{i=0}^m \sum _{j=0}^\ell (i+j) -\sum _{i=0}^\ell \sum _{j=0}^\ell (i+j) \\&= 2 \sum _{i=0}^m \left( (\ell +1)i+\frac{\ell (\ell +1)}{2}\right) - \sum _{i=0}^\ell \left( (\ell +1)i+\frac{\ell (\ell +1)}{2}\right) \\&= 2\left( \frac{(\ell +1)m(m+1)}{2} + \frac{\ell (\ell +1)(m+1)}{2}\right) \\&- \frac{\ell (\ell +1)^2}{2}- \frac{\ell (\ell +1)^2}{2} = k. \end{aligned}$$

Certainly it is easy to evaluate \(V_{i,j}\), \((i,j) \in {\mathcal H}\) explicitly, however it is enough for us to note that we have

$$\begin{aligned} U^{s} H^{-k} = 2p^{s-1}. \end{aligned}$$

Hence

$$\begin{aligned} U = 2^{1/s}p^{1-1/s} H^{k/s}. \end{aligned}$$
(8)

We also assume that the constant \(c\) in (5) is small enough so the condition

$$\begin{aligned} \max _{(i,j) \in {\mathcal H}} \left\{ V_{i,j}\right\} = UH^{-1} <p \end{aligned}$$

is satisfied.

Let \(F(X,Y) \in {\mathbb Z}[X]\) and \(G(X,Y) \in {\mathbb Z}[X]\) be polynomials with coefficients in the interval \([-p/2,p/2]\), obtained by reducing \(vf(X)g(Y)\) and \(v\lambda f(Y)g(X)\) modulo \(p\), respectively. Clearly (6) implies

$$\begin{aligned} F(x,y) \equiv G(x,y) \pmod p. \end{aligned}$$
(9)

Furthermore, since for \(x,y\in \{1, \ldots , H\}\), we see from (8) and the trivial estimate on the constant coefficients [that is, \(|F(0)|, |G(0)| \le p/2\)] that

$$\begin{aligned} |F(x,y)-G(x,y)| \ll U+p \ll p^{1-1/s} H^{k/s} + p, \end{aligned}$$

which together with (9) implies that

$$\begin{aligned} F(x,y) = G(x,y) + zp \end{aligned}$$
(10)

for some integer \(z \ll p^{-1/s} H^{k/s}+1\).

Clearly, for any integer \(z\) the reducibility of \(F(X,Y) - G(X,Y)-pz\) over \({\mathbb C}\) implies the reducibility of \(F(X,Y) - G(X,Y)\) over \(\overline{{\mathbb F}}_p\), or equivalently \(f(X)g(Y) -\lambda f(Y)g(X)\) over \(\overline{{\mathbb F}}_p\), which is impossible because \(\lambda \not \in \Lambda \).

Because \(F(X,Y) - G(X,Y)-pz\in {\mathbb C}[X,Y]\) is irreducible over \({\mathbb C}\) and has degree \(d\), we derive from Lemma 4 that for every \(z\) the Eq. (10) has at most \(H^{1/(d+e)+o(1)}\) solutions. Thus the congruence (6) has at most \(O\left( H^{1/(d+e)+o(1)} \left( p^{-1/s} H^{k/s}+1\right) \right) \) solutions. This, together with (7), yields the inequality

$$\begin{aligned} \frac{r^2}{2T} \ll H^{1/(d+e)+o(1)} \left( p^{-1/s} H^{k/s}+1\right) , \end{aligned}$$

and concludes the proof. \(\square \)

Clearly, in the case when \(e=0\), that is, \(\psi =f\) is a polynomial of degree \(d\ge 2\), the bound of Theorem 7 takes form

$$\begin{aligned} N_\psi ({\mathcal I}, {\mathcal G})\ll \left( 1 + H^{(d+1)/4} p^{-1/4d}\right) H^{1/2d+o(1)} T^{1/2}. \end{aligned}$$

4 Comments

Clearly Theorem 7 also provides a bound for the case where rational function \(\psi = \varphi ^s\), with \(\varphi \in \overline{{\mathbb F}}_p(X)\). This comes from the fact that

$$\begin{aligned} \psi (x)\in {\mathcal G}\implies \varphi (x)\in {\mathcal G}_0, \end{aligned}$$

where \({\mathcal G}_0\) is a multiplicative subgroup of \(\overline{{\mathbb F}}_p\) of order bounded by \(sT\). However the resulting bound depends now on the degrees of the polynomials associated with \(\varphi \) rather than that of \(\psi \).

Another consequence from Theorem 7 is the following: given an interval \({\mathcal I}\) and a subgroup \({\mathcal G}\subseteq {\mathbb F}_p^*\), satisfying \(N_\psi ({\mathcal I}, {\mathcal G})= \#{\mathcal I}\) then

$$\begin{aligned} \#{\mathcal G}\gg \min \{(\# {\mathcal I})^{2 - 2 \tau +o(1)}, (\# {\mathcal I})^{1-2\rho - 2\tau +o(1)}p^{2\vartheta } \} \end{aligned}$$

where the implied constant depends only on \(d\) and \(e\). However, we believe that this bound is very unlikely to be tight.