Mathematics

G. I. Perel’muter

AN ESTIMATE OF A SUM WITH PRIME NUMBERS

(Presented by Academician I. M. Vinogradov, 19 XII 1961)

In paper (1), p. 305, I. M. Vinogradov pointed out the possibility of estimating the sum
\[ S=\sum_{p\le N}\chi(f(p)), \]
where \(\chi\) is a nonprincipal character modulo the prime \(q\), and \(f(x)\) is an integral polynomial. In the present note, by I. M. Vinogradov’s method, an estimate is derived for a sum of the more general form
\[ \sum_{p\le N}\chi(R_1(p))\exp\left(\frac{2\pi i}{q}R_2(p)\right), \]
where \(R_1,R_2\) are rational functions modulo \(q\). The paper uses A. Weil’s estimates (2) in a strengthened form.

Let \(f_1,g_1,f_2,g_2\) be polynomials with integral rational coefficients, with \((f_i,g_i)=1\), and let the leading coefficients of the polynomials \(f_1,g_1\) be equal to \(1\); let \(q\) be a prime \(>q_0\), where \(q_0\) is a sufficiently large positive integer depending on \(f_i,g_i\); let \(\chi\) be a nonprincipal character modulo \(q\); \(\chi(x/y)=\chi(xy')\), where \(yy'\equiv 1\pmod q\), if \(q\nmid y\); \(\chi(x/y)=0\), if \(q\mid y\); \(R_i(x)\) are “rational functions modulo \(q\),” defined for every integer \(a,\ q\nmid g_i(a)\), from the condition \(R_i(a)g_i(a)\equiv f_i(a)\pmod q\); over the prime field \(\Pi_q\) they define the ratios
\[ \frac{f_i(x)}{g_i(x)}\in\Pi_q \]
for \(g_i(x)\ne 0,\ x\in\Pi_q\). We shall also put \(R_i(a)=0\), if \(q\mid g_i(a)\). Let
\[ \varphi(x)=\chi(R_1(x))\exp\left(\frac{2\pi i}{q}R_2(x)\right); \]
\(\bar z\) is the value complex conjugate to \(z\); \(\varepsilon\) is an arbitrary small positive number; the symbols \(A=O(B)\) or \(A\ll B\) mean that \(|A|\le c|B|\), where \(c\) is a constant depending on \(f_i,g_i,\varepsilon\).

Theorem. Let \(f_1,g_1,f_2,g_2\) be polynomials with integral rational coefficients such that, if
\[ \frac{f_2}{g_2}=ax+b, \]
then
\[ \frac{f_1}{g_1}\ne x,\ \frac{1}{x},\ \mathrm{const}, \]
and the polynomial \(f_1g_1\) has no multiple roots; let \(q\) be a prime number, \(\chi\) a nonprincipal character modulo \(q\); let \(p\) run through the consecutive prime numbers; and let \(N\) be a positive integer.

Then, for any independent \(\varepsilon>0,\ \frac16\ge \varepsilon_0>0\), we have:
\[ S=\sum_{p\le N}\varphi(p) =\sum_{p\le N}\chi(R_1(p))\exp\left(\frac{2\pi i}{q}R_2(p)\right) \]
\[ =O\left( N^{1+\varepsilon}q^\varepsilon \sqrt{ \frac{1}{\sqrt q} + \frac{\sqrt q}{N^{1/2+\varepsilon_0}} + N^{-\varepsilon_0} } \right). \tag{1} \]

The proof of the theorem is based on six lemmas.

Lemma A. Let \(R_1(x),R_2(x)\) be rational functions modulo \(q\), and let \(\chi\) be a nonprincipal character modulo \(q\), with at least one of the conditions being satisfied: 1) \(\chi(R_1(x))\ne \mathrm{const}\); 2) \(R_2(x)\ne \mathrm{const}\). Then
\[ \sum_{a=0}^{q-1}\varphi(a)\ll \sqrt q. \]

The proof is obtained by combining the ideas of Hasse’s work (3) with A. Weil’s theorem on the zeros of the zeta-function of algebraic curves.

In all that follows it is assumed that the polynomials \(f_i,g_i\) satisfy the conditions of the theorem.

Lemma 1. Let \(N, Y, X\) be integers, \(Y<0,\ 0<X<q\); \(a,b\) integers, \((a,q)=1\); \(d_1,d_2\) integers independently running through the interval \((N,N+Y)\). Then:

\[ 1)\quad \sum_{x=0}^{q-1}\varphi(ax)\exp\left(\frac{2\pi i}{q}bx\right)\ll \sqrt q, \]

\[ 1')\quad \sum_{x=N}^{N+X}\varphi(ax)\ll \sqrt q\ln q \]

uniformly with respect to \(a,b,N,X\);

\[ 2)\quad \sum_{x=0}^{q-1}\varphi(ad_1x)\overline{\varphi(ad_2x)} \exp\left(\frac{2\pi i}{q}bx\right)\ll \sqrt q, \]

\[ 2')\quad \sum_{x=N}^{N+X}\varphi(ad_1x)\overline{\varphi(ad_2x)} \ll \sqrt q\ln q \]

uniformly with respect to \(a,b,d_1,d_2,N,X\) for all pairs \(d_1,d_2\), with the possible exception of

\[ \ll Y+\frac{Y^2}{q} \]

pairs.

Proof. Estimate 1) follows from Lemma A. 1′) follows from 1) and a well-known lemma of I. M. Vinogradov.

If \((d_1d_2,q)=1\), then the conditions of Lemma A for the sum 2) can fail to hold only for those pairs \(d_1,d_2\) for which the following congruences of polynomials modulo \(q\) hold simultaneously:

\[ f_1(ad_1x)g_1(ad_2x)=cf_1(ad_2x)g_1(ad_1x)\pmod q, \]

\[ f_2(ad_1x)g_2(ad_2x)-f_2(ad_2x)g_2(ad_1x) =(c_1+b_1x)g_2(ad_1x)g_2(ad_2x)\pmod q, \]

where \(c,c_1,b_1\) are integers. It is easy to show that on the interval \((N,N+Y)\) the number of such pairs is

\[ \ll Y+\frac{Y^2}{q}. \]

Therefore 2), 2′) are obtained in the same way as 1), 1′).

Lemma 2. Let \(M,N,X,Y\) be integers, \(X>0,\ Y>0,\ (a,q)=1\);

\[ S_a=\sum_{x=M}^{M+X}\sum_{y=N}^{N+Y}\xi(x)\eta(y)\varphi(axy), \qquad 0\le \xi(x)\le \alpha,\quad 0\le \eta(y)\le \beta. \]

Then

\[ S_a\ll \alpha\beta q^{\varepsilon_1}XY \sqrt{\frac{1}{\sqrt q}+\frac{\sqrt q}{X}+\frac{1}{Y}} \]

uniformly with respect to \(a\).

Proof.

\[ |S_a|^2\ll \alpha^2\beta^2X \sum_{d_1=N}^{N+Y}\sum_{d_2=N}^{N+Y}\sum_{x=M}^{M+Y} \varphi(ad_1x)\overline{\varphi(ad_2x)}; \]

with the exception of

\[ \ll Y+\frac{Y^2}{q} \]

pairs \(d_1,d_2\), by 2), 2′) of Lemma 1 the inner sum will be

\[ \ll \frac{X}{q}\sqrt q+\sqrt q\ln q. \]

Consequently,

\[ |S_a|^2\ll \alpha^2\beta^2X^2Y^2q^{\varepsilon_1} \left(\frac{1}{\sqrt q}+\frac{\sqrt q}{X}+\frac{1}{Y}\right). \]

Lemma 3. Let \(cu<u'\le 2u,\ 1<c<2,\ (a,q)=1\);

\[ S_a=\sum_x\sum_y \xi(x)\eta(y)\varphi(axy), \]

where the summation extends over the domain

\[ xy\le N,\qquad u<x\le u'; \qquad 0\le \xi(x)\ll N^{\varepsilon_2},\quad 0\le \eta(y)\ll N^{\varepsilon_2}. \]

Then

\[ S_a\ll N^{1+\varepsilon_2}q^{\varepsilon_3} \sqrt{\frac{1}{\sqrt q}+\frac{\sqrt q}{u}+\frac{u'}{N}} \]

uniformly with respect to \(a\).

Lemma 3 is proved by the “exhaustion” method on the basis of Lemma 2, in the same way as Lemma 4 in the work of I. M. Vinogradov \((^1)\), p. 219.

Lemma 4. Let \(x, y, m\) run through values belonging to three increasing sequences; \(1<u_1<u_2\leqslant N\),

\[ S=\sum_x \sum_y \sum_m \varphi(xym), \]

where the summation extends over the domain

\[ u_1<x\leqslant u_2,\qquad xym\leqslant N,\qquad (x,y)=1. \]

Then

\[ S\ll N^{1+\varepsilon_4}q^{\varepsilon_4} \sqrt{\frac{1}{\sqrt q}+\frac{\sqrt q}{u_1}+\frac{u_2}{N}}. \]

Proof. We find \(S=\sum_d \mu(d)S_d\), where \(d\) runs through the positive integers simultaneously dividing the numbers in at least one of the possible pairs \(x,y\);

\[ S_d=\sum_{x'}\sum_{y'}\sum_m \varphi(d^2x'y'm), \]

where \(x',y'\) run through the quotients obtained by dividing by \(d\) the values \(x,y\) divisible by \(d\), and the summation extends over the domain:

\[ \frac{u_1}{d}<x'\leqslant \min\left(\frac{u_2}{d},\frac{N}{d^2}\right),\qquad x'y'm\leqslant \frac{N}{d^2}. \]

This domain can be subdivided into \(\ll \ln N\) domains of the form

\[ \frac{u}{d}<x'\leqslant \frac{u'}{d},\qquad x'y''\leqslant \frac{N}{d^2}, \tag{2} \]

where \(u_1\leqslant u<u'\leqslant \min\left(2u,u_2,\frac{N}{d}\right)\), \(y''=y'm\). Since the number \(\eta(y'')\) of pairs \(y',m\) with the condition \(y'm=y''\), for \(y''\leqslant N\), will be \(\ll N^{\varepsilon_2}\), putting \(\xi(x')=1\) if \(x'\) is an admissible value, and \(\xi(x')=0\) otherwise, we may write the part \(S_d'\) of the sum \(S_d\) corresponding to one of the distinguished domains in the form

\[ S_d'=\sum_{x'}\sum_{y''}\xi(x')\eta(y'')\varphi(d^2x'y''), \]

where the summation extends over the domain (2).

If \((d,q)=1\), then, applying Lemma 3, we obtain

\[ S_d\ll \left(\frac{N}{d^2}\right)^{1+\varepsilon_3} q^{\varepsilon_3} \sqrt{\frac{1}{\sqrt q}+\frac{\sqrt q\,d}{u}+\frac{u'd^2}{Nd}} \ll \frac{N^{1+\varepsilon_3}q^{\varepsilon_3}}{d} \sqrt{\frac{1}{\sqrt q}+\frac{\sqrt q}{u_1}+\frac{u_2}{N}}. \]

If \((d,q)=q\), then, estimating \(S_d\) trivially, we have

\[ S_d\ll N^{\varepsilon_2}\sum_{x'}\sum_{y''\leqslant \frac{N}{d^2}}1 \ll \frac{N^{1+\varepsilon_3}}{d^2}. \]

Since all values of \(d\) simultaneously dividing the numbers in one of the possible pairs \(x,y\) do not exceed \(\sqrt N\), we have

\[ S\leqslant \sum_{d\leqslant \sqrt N}|S_d| = \sum_{\substack{(d,q)=1\\ d\leqslant \sqrt N}}|S_d| + \sum_{\lambda\leqslant \frac{\sqrt N}{q}}|S_{\lambda q}| \ll \]

\[ \ll N^{1+\varepsilon_4}q^{\varepsilon_4} \sqrt{\frac{1}{\sqrt q}+\frac{\sqrt q}{u_1}+\frac{u_2}{N}} + \sum_{\lambda\leqslant \frac{\sqrt N}{q}} \frac{N^{1+\varepsilon_3}}{q^2\lambda^2} \ll N^{1+\varepsilon_4}q^{\varepsilon_4} \sqrt{\frac{1}{\sqrt q}+\frac{\sqrt q}{u_1}+\frac{u_2}{N}}. \]

Lemma 5. Let \(0<\varepsilon_0\leqslant \frac16\), \(0<h<\varepsilon_0\); let \(N\) be a sufficiently large positive integer; and let \(P\) be the product of certain primes not exceeding \(N^{1/2-\varepsilon_0}\).

Then the divisors \(d\) of the number \(P\) not exceeding \(N\) can be distributed

among \(<D\) classes, where \(D=(\ln N)^{\ln\ln N/\ln(1+h)}\), and for all \(d\) of one and the same class \(\mu(d)\) retains a constant value.

Some of these classes include only values \(d\) satisfying \(d\leqslant N^{1/2+h}\). For each of the remaining classes there exists a positive integer \(H\) and two increasing sequences \((x)\) and \((y)\) of positive integers satisfying \(N^{1/2}<x\leqslant N^{1-\varepsilon_0+h}\) such that all the numbers of the class, each \(H\) times, are obtained if from all products we choose only those satisfying the conditions

\[ xy\leqslant N,\qquad (x,y)=1 . \]

Lemma 5 is an insignificant modification of a special case of Lemma 6 in the paper of I. M. Vinogradov (1), p. 221.

Proof of the theorem. Let \(P\) be the product of all primes \(p\) distinct from \(q\) and satisfying \(p\leqslant N^{1/2-\varepsilon_0}\); let \(Q\) be the product of all primes \(p\) distinct from \(q\) and satisfying \(N^{1/2-\varepsilon_0}<p\leqslant N\).

We find (\(p_1,p_2\) run through prime numbers):

\[ S=\sum_{d\mid P}\sum_{\substack{md\leqslant N\\(m,q)=1}}\mu(d)\varphi(md) - \sum_{\substack{p_1\mid Q\\ p_1p_2\leqslant N}} \sum_{\substack{p_2\mid Q\\(p_1,p_2)=1}} \varphi(p_1p_2)+O(N^{1/2}). \tag{3} \]

Taking some \(h\) satisfying \(0<h<\varepsilon_0\), we divide all values \(d\) into \(\leqslant N^{\varepsilon_5}\) classes, as indicated in Lemma 5. First estimate the first double sum on the right-hand side of equality (3). The part \(S'\) of this sum corresponding to one of the classes for which \(d\leqslant N^{1/2+h}\) is equal to

\[ S'=\sum_d\sum_{md\leqslant N}\mu(d)\varphi(md) - \sum_d\sum_{\substack{md\leqslant N\\(m,q)=q}}\mu(d)\varphi(md) =S'_1-S'_2 . \]

By 1), 1′) of Lemma 1 we have:

\[ S'_1\ll \sum_{\substack{d\leqslant N^{1/2+h}\\ q\nmid d}} \left|\sum_{\substack{m\leqslant N/d\\(m,q)=1}}\varphi(md)\right| \ll \sum_{d<N^{1/2+h}} \left(\frac{N}{dq}\sqrt q+\sqrt q\ln q\right) \ll \]

\[ \ll \frac{N^{1+\varepsilon_5}}{\sqrt q} +q^{\varepsilon_5}N^{1/2+h}\sqrt q \ll N^{1+\varepsilon_5+h}q^{\varepsilon_5} \left(\frac1{\sqrt q}+\sqrt{\frac qN}\right); \]

\[ S'_2\ll \sum_{d\leqslant N}\sum_{m\leqslant N/(dq)}1 \ll \frac{N^{1+\varepsilon_5}}q . \]

Consequently,

\[ S'\ll N^{1+\varepsilon_5+h}q^{\varepsilon_5} \left(\frac1{\sqrt q}+\sqrt{\frac qN}\right). \]

The part \(S''\) of the sum under consideration corresponding to one of the remaining classes, according to Lemmas 5 and 4 \((u_1=N^{1/2},\ u_2=N^{1-\varepsilon_0+h})\), will be

\[ \ll N^{1+\varepsilon_4}q^{\varepsilon_4} \sqrt{\frac1{\sqrt q}+\sqrt{\frac qN}+\frac{N^{1-\varepsilon_0+h}}N} \ll \]

\[ \ll N^{1+\varepsilon_4+h}q^{\varepsilon_4} \sqrt{\frac1{\sqrt q}+\sqrt{\frac qN}+N^{-\varepsilon_0}} . \]

Finally, the second double sum on the right-hand side of equality (3), according to Lemma 4 \((u_1=N^{1/2-\varepsilon_0},\ u_2=N^{1/2+\varepsilon_0},\ (x)=(p_1),\ (y)=(p_2),\ (m)=(1))\), will be

\[ \ll N^{1-\varepsilon_4}q^{\varepsilon_4} \sqrt{\frac1{\sqrt q}+\frac{\sqrt q}{N^{1/2-\varepsilon_0}}+N^{-1/2+\varepsilon_0}} . \]

Considering that

\[ \frac1{\sqrt q}+\sqrt{\frac qN}<1, \]

and that \(\varepsilon_4,\varepsilon_5,\varepsilon_6,h\) are sufficiently small, we obtain (1).

Received
11 XII 1961

CITED LITERATURE

1. I. M. Vinogradov, Selected Works, Moscow, 1952.
2. A. Weil, Proc. Nat. Acad. Sci., Washington, 34, No. 5, 204 (1948).
3. H. Hasse, J. f. reine u. angew. Math., 172, 37 (1935).
4. A. Weil, Proc. Nat. Acad. Sci., 27, 345 (1941).