Abstract Generated abstract
This note studies the distribution, over residues modulo a prime p, of very short exponential sums of the form \(\sum_{x=0}^{h}\exp(2\pi i ag^x/p)\), where \(g\geq 2\) is fixed and \(h\) grows but remains at most one half of \(\log p/\log g\). Using Markov’s method of moments, it computes the limiting moments of the normalized squared modulus by reducing the relevant congruence to an equality of sums of powers of \(g\), whose number of solutions is asymptotic to \(r!h^r\). The paper concludes that the proportion of residues \(a\) for which the absolute value of the sum is less than \(\lambda\sqrt h\) tends to \(1-\exp(-\lambda^2)\).
Full Text
MATHEMATICS
A. G. POSTNIKOV
ON A VERY SHORT EXPONENTIAL RATIONAL TRIGONOMETRIC SUM
(Presented by Academician I. M. Vinogradov on 15 IV 1960)
The present paper is an analogue of the work of M. P. Mineev (¹) and is a new application of A. A. Markov’s method of moments* to number-theoretic problems.
Let \(g \geqslant 2\) be a natural number. Let \(p\) be a prime number, and \(h=h(p)\) some integer-valued function; \(h\to\infty\) as \(p\to\infty\); \(h(p)\leqslant \dfrac{1}{2}\dfrac{\log p}{\log g}\). Let \(\lambda>0\) be a constant. Denote by \(N_p(\lambda)\) the number of integers \(a\), \(0\leqslant a\leqslant p-1\), for which
\[ \left|\sum_{x=0}^{h}\exp\left[2\pi i\,\frac{ag^x}{p}\right]\right|<\lambda\sqrt{h}. \]
Theorem. As \(p\to\infty\),
\[ \lim_{p\to\infty}\frac{N_p(\lambda)}{p}=1-e^{-\lambda^2}. \]
Proof. For fixed \(p\) and, consequently, \(h\), consider the random variable \(\xi_p\), taking the values
\[ \frac{1}{h}\left|\sum_{x=0}^{h}\exp\left[2\pi i\,\frac{ag^x}{p}\right]\right|^2,\qquad a=0,1,\ldots,p-1, \]
with probability equal to \(1/p\). The distribution function of this random variable is \(N_p(\lambda^2)/p\).
Let us compute the \(r\)-th moment of this distribution function:
\[ \frac{1}{p}\sum_{a=0}^{p-1}\frac{1}{h^r} \left|\sum_{x=0}^{h}\exp\left[2\pi i\,\frac{ag^x}{p}\right]\right|^{2r} = \]
\[ =\frac{1}{ph^r} \sum_{x_1=0}^{h}\cdots\sum_{x_r=0}^{h} \sum_{y_1=0}^{h}\cdots\sum_{y_r=0}^{h} \exp\left[ 2\pi i\,\frac{a\left(g^{x_1}+\cdots+g^{x_r}-g^{y_1}-\cdots-g^{y_r}\right)}{p} \right] =\frac{1}{h^r}M_r(p), \]
where \(M_r(p)\) is the number of solutions of the congruence
\[ g^{x_1}+\cdots+g^{x_r}\equiv g^{y_1}+\cdots+g^{y_r}\pmod p \tag{1} \]
in the integers \(0\leqslant x_i,y_i\leqslant h\), \(i=1,2,\ldots,r\). But since \(0\leqslant x_i,y_i\leqslant h\leqslant \dfrac{1}{2}\dfrac{\log p}{\log g}\), we have \(r\leqslant g^{x_1}+\cdots+g^{x_r}\leqslant r\sqrt p\).
* An application of the method of moments similar in idea is found in the works (², ³).
If \(p>r^2\), then
\[ 0<g^{x_1}+\ldots+g^{x_r}<p, \]
and the congruence of the two sides of (1) means equality. Therefore \(M_r(p)\) is equal to the number of solutions of the equation
\[ g^{x_1}+\ldots+g^{x_r}=g^{y_1}+\ldots+g^{y_r} \tag{2} \]
in numbers \(0\leq x_i,y_i\leq h\).
Let \(r\) be fixed, \(p\to\infty\) (and hence \(h\to\infty\)). The number of solutions of equation (2) is expressed by the formula
\[ M_r(p)=r!\,h^r+O\left(h^{r-1}\right) \]
(a more general assertion was proved in paper \({}^{4}\)).
Thus,
\[ \lim_{p\to\infty}\frac1p\sum_{a=0}^{p-1}\frac1{h^r} \left|\sum_{x=0}^{h}\exp\left[2\pi i\frac{ag^x}{p}\right]\right|^{2r}=r! \]
Applying the second limit theorem of probability theory in the way this was done in paper \({}^{1}\), we obtain
\[ \lim_{p\to\infty}\frac{N_p(\lambda^2)}{p}=1-e^{-\lambda}, \]
which is what was required to prove.
Mathematical Institute named after V. A. Steklov
Academy of Sciences of the USSR
Received
14 IV 1960
REFERENCES
\({}^{1}\) M. P. Mineev, UMN, 14, no. 3, 169 (1959).
\({}^{2}\) H. Davenport, P. Erdős, Publ. Math., 2, 252 (1952).
\({}^{3}\) I. P. Kubilius, Yu. V. Linnik, Izv. Higher Educational Institutions, Mathematics, no. 6, 88 (1959).
\({}^{4}\) M. P. Mineev, Matem. sbornik, 46 (88), 4, 451 (1958).