UDC 511.9

A. A. KARATSUBA

ON TRIGONOMETRIC SUMS

(Presented by Academician I. M. Vinogradov, 21 III 1969)

In the paper [2] Hua Loo-keng proved:

If \(n \geqslant 2\), \((a,q)=1\), \(1 \leqslant P \leqslant q\), then

\[ S(a,P;q)=\sum_{1\leqslant x\leqslant P}\exp 2\pi i\,\frac{ax^n}{q} = Pq^{-1}S(a,q;q)+O\left(q^{1/2+\varepsilon}\right), \tag{1} \]

where \(\varepsilon>0\) is arbitrary, and the constant in \(O\) depends only on \(n\) and \(\varepsilon\).

This asymptotic formula for a trigonometric sum; formula (1) is nontrivial if the complete sum \(S(a,q;q)\) is “large,” i.e. its modulus is greater than \(q^{1/2+\varepsilon}\); the latter occurs only when \(q\) contains “many” prime factors to a “high” power. We note that, even in the best case, (1) is an asymptotic formula for \(q^{1/2+\varepsilon}\ll P\leqslant q\), i.e. if the original sum \(S(a,P;q)\) is “sufficiently long.” In [3, 4] the author obtained an asymptotic formula for “short” sums \(S(a,P;q)\), if \(q\) is a “high” power of a prime number. However, Theorem 1 in [3] and Lemma 4 in [4] were formulated incorrectly. In the present article new asymptotic formulas will be obtained when \(q\) is a power of a prime number.

Notation and conditions on the parameters used.
\(k,l,m,n,t,P,P_1,a,a_1,\ldots,a_n,b\) are integers; \(n\geqslant 20\); \(r\) is a real number, with \(1\leqslant r\leqslant 0.1n\); \(t\geqslant 4rn\); \(C,C_1,\ldots,\gamma,\gamma_1,\ldots\) are positive absolute constants; \(\varepsilon>0\) is an arbitrarily small number; \(p\) is a prime number, \(p>\exp cn\ln n\), \(p/\ln p>t\); \(q=p^t\); \(P=q^{1/r}\); \((a,p)=1\); \(\delta_n(x)=1\) or \(0\), according as \(x\equiv 0\pmod n\) or \(x\not\equiv 0\pmod n\); the constants in the signs \(O\) and \(\ll\) depend only on \(n\); as above,

\[ S(a,P;q)=\sum_{1\leqslant x\leqslant P}\exp 2\pi i\,\frac{ax^n}{q}. \]

Theorem 1. There exist \(\varphi(q)(1-2q^{-\varepsilon})\) values of \(a\) such that, for every \(P\), the asymptotic formula holds

\[ S(a,P;q)=Pq^{-1}S(a,q;q)+O\left(\sqrt{Pq^{\varepsilon}\ln^3 q}+P^{3/4}\right). \]

Theorem 2. For every \(a\) the equality holds:

\[ S(a,P;q)=Pq^{-1}S(a,q;q)+O\left(P^{1-\gamma/r^2}\right). \]

Proof of Theorem 1. Let \(a\) be arbitrary, \((a,q)=1\).

1. Separation of the principal term. Define integers \(s\) and \(m\) from the conditions \(2^s\leqslant P<2^{s+1}\), \(p^{m-1}\leqslant 2^{0.5s}<p^m\). Then \(s=\left[\frac{t}{r}\log p\right]\), \(m-1=(0.5s/\log p)\); \(m-1<t/2r\leqslant m+1/2t\); moreover, \(p^m\ll P^{3/4}\). Therefore we have

\[ S(a,P;q)= \sum_{1\leqslant x\leqslant P_1p^m} \exp 2\pi i\,\frac{ax^n}{q} +O\left(P^{3/4}\right) = \]

\[ = \sum_{0\leqslant b\leqslant P_1-1} \sum_{1\leqslant x\leqslant p^m} \exp 2\pi i\,\frac{a(x+bp^m)^n}{q} +O\left(P^{3/4}\right). \tag{2} \]

Let us now consider the inner sum

\[ S^*(a)=\sum_{1\leq x\leq p^m}\exp 2\pi i\,\frac{a(x+bp^m)^n}{q}. \]

Let \(t=t_1n+t_2,\ 0\leq t_2\leq n-1,\ t_1=[t/n];\ r_m=t/m\); then \(r_m\leq 2.001r\) and \(r_m\geq t/(t/2r+1)\geq 1\). We split the sum \(S^*(a)\) into \(t_1-\delta_n(t)+1\) sums, grouping together the terms with \(x\) not divisible by \(p\), divisible by \(p\) but not by \(p^2\), divisible by \(p^2\) but not by \(p^3\), etc. From the definition of \(r_m\) and the conditions on \(t\) and \(r_m\) we obtain: \(r_m=t/m\leq 0.2001n,\ m\geq 5t/n-1/2t>t_1+1;\ n(t_1-\delta_n(t)+1)\geq t\). Consequently,

\[ S^*(a)=p^{m-t_1+\delta_n(t)-1}+\sum_{0\leq \nu\leq t_1-\delta_n(t)} S_\nu^*(a), \tag{3} \]

where

\[ S_\nu^*(a)= \sum_{\substack{1\leq x\leq p^{m-\nu}\\ (x,p)=1}} \exp 2\pi i\,\frac{a(x+bp^{m-\nu})^n}{p^{t-\nu n}}, \qquad \nu=0,1,\ldots,t_1-\delta_n(t). \]

Now we split the sum over \(\nu\) in (3) into two parts:

a) \[ 0\leq \nu\leq \nu_0= \left[\frac{t}{n-1}\left(1-\frac{1}{r_m}\right)\right]; \]

b) \[ \nu_0+1\leq \nu\leq t_1-\delta_n(t). \]

Each of the intervals a) and b) is nonempty. Indeed, case a) is trivial. In case b) we have:
\[ \nu_0+1\leq \frac{t}{n-1}\left(1-\frac{1}{r_m}\right)+1 \leq \frac{t}{n}\left(1+\frac{1}{n-1}\times\right) \]
\[ \times\left(1-\frac{1}{2.001r}\right)<\frac{t}{n}-1\leq t_1-\delta_n(t). \]

Consider case b). Then \(m-\nu\geq t-\nu n\); indeed, this follows from the inequality
\[ \nu\geq (t-m)/(n-1)=t(1-1/r_m)/(n-1). \]
Consequently, \(S_\nu^*(a)\) is a complete sum, and

For any \(l\geq 2\) we have the equality:

\[ S_\nu^*(a)= \sum_{\substack{1\leq x\leq p^{t-\nu n}\\ (x,p)=1}} \exp 2\pi i\,\frac{ax^n}{p^{t-\nu n}}. \]

\[ \sum_{\substack{1\leq x\leq p^l\\ (x,p)=1}} \exp \frac{ax^n}{p^l}=0 \]

(see, for example, (1), p. 270). Consequently, only \(S_{t_1}^*(a)\) can be different from zero, and this will occur only when \(t_2=1\), i.e.

\[ S_{t_1}^*(a)=\delta_n(t-1)p^{m-t_1-1} \sum_{x=1}^{p-1}\exp 2\pi i\,\frac{ax^n}{p} = \delta_n(t-1)p^{m-t_1-1}(S(a,p;p)-1). \]

Thus,

\[ S^*(a)=p^{m-t_1+\delta_n(t)-1} +\delta_n(t-1)p^{m-t_1-1}(S(a,p;p)-1)+ \]
\[ +\sum_{0\leq \nu\leq \nu_0}S_\nu^*(a) =p^m q^{-1}S(a,q;q)+\sum_{0\leq \nu\leq \nu_0}S_\nu^*(a), \]

which also follows from (1), p. 270. From the last formula, the definition of \(S_\nu^*(a)\), and (2) we find

\[ S(a,P;q)=Pq^{-1}S(a,q;q)+R(a,P;q)+O(P^{3/4}), \tag{4} \]

where

\[ R(a,P;q)=\sum_{1\leq x\leq P}^{\prime}\exp 2\pi i\,\frac{ax^n}{q}, \]

and the prime on the sum means that the summation is over \(x\not\equiv 0\pmod{p^{\nu_0+1}}\).

2. Estimate of the remainder. The quantity \(|R(a,P;q)|\) depends essentially on \(P\). We shall now pass to a larger quantity which will depend only

on \(n, a\), and \(q\). Note that \(\nu_0\) depends only on \(n, t\), and \(s\). We have

\[ R(a,P;q)=2^{-s-1}\sum_{1\le x\le 2^{s+1}}' \exp 2\pi i\,\frac{ax^n}{q} \sum_{0\le b\le 2^{s+1}} \sum_{y\le P} \exp 2\pi i\,\frac{b(x-y)}{2^{s+1}}, \]

where the prime, as before, means that \(x\not\equiv 0 \pmod {p^{\nu_0+1}}\). Separating the term with \(b=0\), summing over \(y\), and passing to inequalities, we obtain

\[ |R(a,P;q)|\ll \sum_{0\le b\le 2^{s+1}} \frac{1}{b+1} \left| \sum_{1\le x\le 2^{s+1}}' \exp 2\pi i\left(\frac{ax^n}{p^t}-\frac{bx}{2^{s+1}}\right) \right|. \]

Consequently,

\[ |R(a,P;q)|^2\ll \log q \sum_{0\le b\le 2^{s+1}} \frac{1}{b+1} \left| \sum_{1\le x\le 2^{s+1}}' \exp 2\pi i\left(\frac{ax^n}{p^t}-\frac{bx}{2^{s+1}}\right) \right|^2, \]

\[ P^{-1}|R(a,P;q)|^2\ll 2^{-s-1}\log q \sum_{0\le b\le 2^{s+1}} \frac{1}{b+1} \left| \sum_{1\le x\le 2^{s+1}}' \exp 2\pi i\left(\frac{ax^n}{p^t}-\frac{bx}{2^{s+1}}\right) \right|^2 \]

\[ \ll \log q \sum_{0\le s\le \log q} 2^{-s-1} \sum_{0\le b\le 2^{s+1}} \frac{1}{b+1} \left| \sum_{1\le x\le 2^{s+1}}' \exp 2\pi i\left(\frac{ax^n}{p^t}-\frac{bx}{2^{s+1}}\right) \right|^2 =\log q\cdot \Phi, \]

where \(\Phi=\Phi(a,q)=\Phi(n,a,q)\ge 0\) and depends only on \(n,a\), and \(q\).

Arrange \(\Phi(a,q)\) in increasing order:
\(\Phi(a_1,q)\le \Phi(a_2,q)\le \cdots\le \Phi(a_\varkappa,q)\),
\(\varkappa=\varphi(q)\). For \(1\le \omega<\varkappa\) we have

\[ \Phi(a_\omega,q)\ll \frac{1}{\varkappa-\omega+1}\sum_{\omega\le m\le \varkappa}\Phi(a_m,q) \ll \frac{1}{\varkappa-\omega+1}\sum_{1\le m\le \varkappa}\Phi(a_m,q)\ll \]

\[ \ll \frac{1}{\varkappa-\omega+1} \sum_{0\le s\le \log q} 2^{-s-1} \sum_{0\le b\le 2^{s+1}}\frac{1}{b+1}\,qT_s, \]

where \(T_s\) is the number of solutions of the congruence
\(x^n\equiv y^n \pmod {p^t}\),
\(1\le x,y\le 2^{s+1}\),
\(x\not\equiv 0\pmod {p^{\nu_0+1}}\),
\(y\not\equiv 0\pmod {p^{\nu_0+1}}\).
Since \(2^{s+1}p^{-\nu_0}\ll p^{t-\nu_0 n}\), it follows that

\[ T_s\ll \sum_{0\le \nu\le \nu_0} 2^{s+1}p^{-\nu}\ll 2^{s+1}, \qquad \Phi(a_\omega,q)\ll \frac{q\log^2 q}{\varkappa-\omega+1}. \]

If now we take \(\omega=\varkappa-q^{1-\varepsilon}\), then

\[ \Phi(a_\omega,q)\ll q^\varepsilon\log^2 q,\qquad P^{-1}|R(a_\nu,P;q)|^2\ll q^\varepsilon\log^3 q \]

for \(\nu=1,2,\ldots,\varphi(q)-q^{1-\varepsilon}\). From this and from (4) we obtain the assertion of Theorem 1.

For the proof of Theorem 2 we shall need the following

Lemma. Let \(q_1=p^k\), \(n\le k\le t\), \(1\le u\le 0.5n\); \(P_1^u=q_1\),
\((a_1,p)=(a_2,p)=\cdots=(a_n,p)=1\),

\[ S=\sum_{1\le x\le P_1} \exp 2\pi i\,\frac{a_1x+a_2px^2+\cdots+a_np^{\,n-1}x^n}{q_1}. \]

Then

\[ |S|\le c_1P_1^{\,1-\gamma_1/u^2}. \]

This is one of the variants of the theorem of [5], p. 239.

Proof of Theorem 2. Estimate \(|R(a,P;q)|\) in (4) (see the proof of Theorem 1). We have

\[ R(a,P;q)=\sum_{1\le x<P}' \exp 2\pi i\,\frac{ax^n}{q} = \sum_{0\le h<P_1-1}\sum_{0\le \nu\le \nu_0}S_\nu^*(a)+O(P^{3/4}). \]

In the sum \(S_\nu^*(a)\) make the change of summation variable of the form
\(x=py+z\), \(1\le z\le p-1\), \(0\le y\le p^{m-\nu-1}-1\); then
\(ax^n=a(py+z)^n=a_0+a_1py+\cdots+a_np^ny^n\), where
\((a_0,p)=\cdots=(a_n,p)=1\) for every \(z\), \(1\le z\le p-1\). Further,

\[ |S_\nu^*(a)|\le \sum_{1\le z\le p-1} \left| \sum_{0\le y\le p^{m-\nu-1}} \exp 2\pi i\,\frac{a_1y+a_2py^2+\cdots+a_np^{\,n-1}y^n}{p^{t-\nu n-1}} \right|. \]

The estimate of the lemma is applicable to the last sum. Let us verify that the conditions of the lemma are satisfied:

\(k=t-\nu n-1;\quad k\leq t;\quad k\geq t-\nu_0 n-1\geq t-1-\)

\[ -\,t\left(1+\frac{1}{n-1}\right)\left(1-\frac{1}{r_m}\right) \geq t-1-t\left(1+\frac{1}{n-1}\right)\left(1-\frac{1}{2.001r}\right)\geq n; \]

let \(u=(t-\nu n-1)/(m-\nu-1)\), then \(u\geq 1\), since \(\nu\leq (t-m)/(n-1)=t(1-1/r_m)/(n-1)\); moreover,
\(u=r_m(t-\nu n+1)/(t-\nu r_m-r_m)\leq 2r_m\), which follows from the inequality
\(r_m\leq \frac12(\nu n+t+1)/(\nu+1)=\frac12(n+(t+1-n)/(\nu+1))\).
Thus, always \(1\leq u\leq 2r_m\leq 4.002\,r<0.5\,n\). Applying the estimate of the lemma, we obtain:

\[ |S_\nu^*(a)|\ll p\cdot p^{(m-\nu-1)(1-\gamma_2/u^2)} = p^{(m-\nu)(1-\gamma_3/u^2)} = p^{(m-\nu)(1-\gamma_4/r_m^2)}. \]

Thus,

\[ |R(a,P;q)|\ll P_1\sum_{0\leq \nu\leq \nu_0} p^{(m-\nu)(1-\gamma_1/r_m^2)} + P^{3/4} \ll \]

\[ \ll P_1p^{m(1-\gamma_1/r_m^2)} + P^{3/4} \ll P^{1-\gamma/r^2}. \]

From (4) and the last estimate, the assertion of Theorem 2 follows.

Remark 1. Theorem 1 can be proved for a wider interval of variation of the values of \(P\), namely \(1\leq r\leq 0.5n\).

Remark 2. Hua Lo-keng’s theorem and Theorems 1 and 2 establish the asymptotics of the corresponding trigonometric sums for \(1\leq r\leq 2\), \(1\leq r\leq 0.1n\), and \(1\leq r\leq c\sqrt n\), respectively.

Remark 3. Theorems 1 and 2 can be generalized to a broader class of trigonometric sums.

Mathematical Institute named after V. A. Steklov
Academy of Sciences of the USSR
Moscow

Received
11 III 1969

CITED LITERATURE

1. I. M. Vinogradov, Selected Works, Publishing House of the Academy of Sciences of the USSR, 1952.
2. Hua Lo-keng, On Exponential Sums, Science Record, 1, 1, 1957, p. 1.
3. A. A. Karatsuba, DAN, 169, No. 1, 9 (1966).
4. A. A. Karatsuba, Tr. Moscow Math. Soc., 18, 77 (1968).
5. A. A. Karatsuba, Izv. Academy of Sciences of the USSR, 28, 1, 237 (1964).