%\documentstyle[amscd,amssymb,verbatim,12pt]{amsart}
%\hoffset   -0.25in
%\textheight 8.52in
%\textwidth  5.5in
%\vfuzz      1.25pt
%\hfuzz      1.25pt
%\tolerance  500

%\documentstyle[amscd,amssymb,verbatim,10pt]{amsart}

\documentclass[11pt]{article}
\textwidth=6.25in
\textheight=9.0in
\evensidemargin=10pt
\oddsidemargin=10pt
\topmargin=10pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9

\newcommand{\qed}{\hfil $\Box$}

\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{verbatim}
\usepackage{amscd}
\usepackage{theorem}

\newcommand{\alp}{\alpha}
\newcommand{\eps}{\varepsilon}
\renewcommand{\phi}{\varphi}

\newcommand{\oZ}{{\bar Z}}

\newcommand{\F}{{\mathbb F}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\R}{{\mathbb R}}

\newcommand{\Fp}{\F_p}
\newcommand{\Fpz}{\Fp^\times}
\newcommand{\seq}{\subseteq}
\newcommand{\stm}{\setminus}
\newcommand{\longc}{,\dotsc,}
\newcommand{\longp}{+\dotsb+}
\newcommand{\mmod}[1]{\!\!\pmod{#1}}
\newcommand{\e}[1]{e^{2\pi i #1}}

%\theoremstyle{plain}
\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}

\newcommand{\refl}[1]{~\ref{l:#1}}
\newcommand{\reft}[1]{~\ref{t:#1}}
\newcommand{\refc}[1]{~\ref{c:#1}}
\newcommand{\refs}[1]{~\ref{s:#1}}
\newcommand{\refb}[1]{\cite{b:#1}}
\newcommand{\refe}[1]{~\eqref{e:#1}}

%\subjclass{Primary: 11B75; Secondary: 11D04, 11L07, 11P99, 11B25, 11D72}

\begin{document}
\begin{center}
{\bf ON THE DISTRIBUTION OF EXPONENTIAL SUMS}
\vskip 20pt
{\bf Sergei V. Konyagin}\\
{\smallit Department of Mechanics and Mathematics,
Moscow State University, Moscow 119899, Russia}\\
{\tt kon@nw.math.msu.su}\\
\vskip 10pt
{\bf Vsevolod F. Lev\footnote{Supported in part
by the Edmund Landau Center for Research in 
Mathematical Analysis and Related Areas, sponsored
by the Minerva Foundation (Germany)}}\\
{\smallit Institute of Mathematics, Hebrew 
University, Jerusalem 91904, Israel}\\
{\tt seva@math.huji.ac.il}\\
\end{center}
\vskip 30pt
\centerline{\smallit Received: 9/3/99, Accepted: 10/12/99, Published: 5/19/00}
\vskip 30pt

\centerline{\bf Abstract}

\noindent
We discuss three problems of the following kind: given a set $A\seq\Fp$ of
$n:=|A|$ residues modulo a prime $p$, how are the absolute values $|S_A(z)|$ of
the corresponding exponential sums
  $$ S_A(z):=\sum_{a\in A}\e{\frac{az}p};\qquad z\in\Fp $$
distributed in the interval $[0,n]$?

\pagestyle{myheadings}

\markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF 
COMBINATORIAL NUMBER THEORY \smalltt 0 (2000), \#A01 \hfill}
\thispagestyle{empty}
\baselineskip=15pt
\vskip 30pt
\section*{\normalsize 1. Introduction}
One of the most popular tools in number theory, exponential sums, are usually
studied from the following point of view only: given a particular set $A$ of
$n=|A|$ residues, integers, or real numbers, show that the absolute values of
the exponential sums corresponding to this set are small. In this note we adopt
a more general standpoint, trying to understand the distribution of the
absolute values of the exponential sums in the interval $[0,n]$. Moreover, we
are interested not in the sets $A$ of some special arithmetic structure, but
rather in the common properties of the exponential sums, independent of the
structure of $A$. This is primarily a survey note: we review several known
results and pose some new problems.

We stick with the case of residues modulo a prime $p$. For a set $A\seq\Fp$ of
$n=|A|$ residues we write
  $$  S_A(z):=\sum_{a\in A}\e{\frac{az}p};\qquad z\in\Fp. $$
(More generally, one can consider character sums in any locally compact Abelian
group. Local compactness implies the existence of Haar measure on the group of
characters, and we can ask ``how many'' characters with a given property
are there.) To avoid trivialities, we often assume tacitly that
$2\le n\le p-1$.

The basic observation is that $0<|S_A(z)|\le n$ and moreover, $|S_A(z)|=n$ if
and only if $z=0$. (The reason why $S_A(z)$ is not $0$ is that it can be
considered as a polynomial of a $p$th root of unity, and this polynomial is
not divisible by the minimal polynomial $x^{p-1}+ \cdots + x+1$.) Furthermore,
Parseval's identity gives

\begin{equation}\label{e:pars}
  \sum_{z\in\Fp} |S_A(z)|^2=np.
\end{equation}

Below we address the following three questions.

\begin{itemize}
\item[1)]
As we have noticed, $|S_A(z)|$ are distinct from $0$, but how close to $0$ can
they be?

\item[2)]
How many of the $p$ sums $|S_A(z)|$ can be close to $0$?

\item[3)]
How many of the $p$ sums $|S_A(z)|$ can be close to $n$?
\end{itemize}

(The answer to the missed question ``How large $|S_A(z)|$ can be?'' is
immediate: it can be equal to $n$, if $z=0$, and plainly the next largest value
is $|\sin(\pi n/p)/\sin(\pi/p)|$, attained when $A$ is an arithmetic
progression $\mmod p$.)

We discuss these three questions in Sections 2 -- 4,
respectively.
\vskip 30pt
\section*{\normalsize 2. How Small Can Exponential Sums Be?}

The first question of this sort was probably first raised in 1975 by Gerry
Myerson (see [M86]), who introduced the function $f(n,N)$, the least
absolute value of a sum of $n$ $N$th roots of unity. Myerson allowed the
roots of unity to be equal and proved several estimates for the case of $N$ even. In this note we confine ourselves to $N$ prime and require the roots
to be pairwise distinct.

\begin{theorem}\label{t:1}
Suppose that $A\seq\Fp$ is a set of $n=|A|\in[3,p-1]$ residues $\mmod p$, and
let $z\in\Fpz$. Then
  $$ |S_A(z)| > n^{-\frac{p-3}4}. $$
\end{theorem}

\noindent
{\it Proof.}
For any fixed $z_0\in\Fpz$, the sum $S_A(z_0)$ is an algebraic integer of the
norm $\prod_{z\in\Fpz} S_A(z)$.
This product is, therefore, at least $1$ in absolute value, whence by the
arithmetic-geometric means inequality and \refe{pars} we have

\begin{equation*}
\begin{aligned}
  1 & \le \prod_{z\in\Fpz}|S(z)|^2 = |S_A(z_0)|^4 \,
%             \prod
%             \begin{substack}
%                z\in\Fpz \\ z\neq\pm z_0
%             \end{substack}
%             |S(z)|^2 \\
        \underset{z \neq \pm z_0}{\prod_{z \in \Fpz}} |S(z)|^2 \\
    & \le |S_A(z_0)|^4 \, \Bigg( \frac{1}{p-3}
%             \sum
%             \begin{substack}
%                z\in\Fpz \\ z\neq\pm z_0
%              \end{substack}
         \underset{z \neq \pm z_0}{\sum_{z \in \Fpz}} |S(z)|^2
              \Bigg)^{p-3} \\
    & <   |S_A(z_0)|^4 \left( \frac{n(p-n)}{p-3} \right)^{p-3} \\
    & \le n^{p-3} \, |S_A(z_0)|^4. \\
\end{aligned}
\end{equation*}
\hfill \qed

On the other hand, we were able to prove the following.

\begin{theorem}\label{t:2}
For any $n=2^k<p/20$ (where $k$ is a positive integer) there exists $A\seq\Fp$ 
of the cardinality $n$ such that
  $$ |S_A(1)| < n^{-\frac{\ln p}{2\ln 2}}. $$
\end{theorem}

\noindent
{\it Proof.} 
Let $p'=(p-1)/2$ and define $A$ to be the set of all the subset sums of
  $$ \{p'+1,p'+2,p'+4\longc p'+2^{k-1}\}\seq\Fp. $$
We first show that all these subset sums are distinct, and therefore $|A|=2^k$.

We assume that
\begin{equation}\label{e:loc1}
  \sum_{i\in I} (p'+2^i) \equiv \sum_{j\in J} (p'+2^j) \mmod p
\end{equation}
for two subsets $I,J\seq\{0\longc k-1\}$ and we prove that $I=J$. Define
$\xi := \sum_{i\in I}2^i$ and $\eta := \sum_{j\in J} 2^j$. Then
  $$ 0\le \xi,\eta,|I|,|J|\le 2^k-1 < p/20 $$
and \refe{loc1} implies
\begin{equation*}
\begin{split}
  2\xi-|I| &\equiv 2\eta-|J| \mmod p, \\
  2\xi-|I| &= 2\eta-|J|.
\end{split}
\end{equation*}

\noindent
Next, it is easily seen that

\begin{equation*}
\begin{split}
|I| &= \xi - \left\lfloor \frac{\xi}{2} \right\rfloor
     - \left\lfloor \frac{\xi}{4} \right\rfloor - \dots, \\
|J| &= \eta - \left\lfloor \frac{\eta}{2} \right\rfloor
     - \left\lfloor \frac{\eta}{4} \right\rfloor - \dots,\\
\end{split}
\end{equation*}
whence
$$
\xi + \left\lfloor \frac{\xi}{2} \right\rfloor
+\left\lfloor \frac{\xi}{4} \right\rfloor + \dots
= \eta + \left\lfloor \frac{\eta}{2} \right\rfloor
+ \left\lfloor \frac{\eta}{4} \right\rfloor + \dots.
$$
As $x+\lfloor x/2\rfloor+\lfloor x/4\rfloor+\dots$ is a strictly increasing
function of $x$, we obtain $\xi=\eta$ and therefore $I=J$.

It follows that
  $$ S_A(1)=\prod_{j=0}^{k-1} \left(1+\e{\frac{p'+2^j}p}\right), $$
and the absolute value of this product is easy to estimate:
\begin{equation*}
\begin{split}
%\begin{align*}
  |S_A(1)|
    &= 2^k\prod_{j=0}^{k-1}\Big|\cos\pi\,\frac{p-1+2^{j+1}}{2p}\,\Big| \\
    &= 2^k\prod_{j=1}^k \Big|\sin\frac{\pi}{2p}\,(2^j-1)\,\Big| \\
    &< \left(\frac\pi p\right)^k 2^{\frac{k(k+1)}2} \\
    &= n^{-\frac{\ln(p/\pi\sqrt 2)}{\ln 2}+\frac{\ln n}{2\ln 2}} \\
    &< n^{-\frac{\ln p}{2\ln 2}}.
%\end{align*}
\end{split}
\end{equation*}
\hfill \qed

It is clear from the proof that $\ln p/(2\ln 2)$ in the exponent can be
replaced with $(1-\eps)\ln p/\ln 2$ for any positive $\eps$. However, the
gap between the estimates of Theorems \reft{1} and \reft{2} makes refinements
of this sort senseless.
\vskip 30pt
\section*{\normalsize 3. How Many Small Sums Are There?}

Suppose that $Z\seq\Fp$ is a set of residues such that $|S_A(z)|$ is ``small''
for all $z\in Z$. Then the sum $\sum_{z\in Z}|S_A(z)|^2$ is small also. We
normalize this sum letting
  $$ G(Z) := \frac{1}{|Z|}\,\sum_{z\in Z}|S_A(z)|^2. $$
A way to express the fact that not too many of the exponential sums are small
is to bound $G(Z)$ from below for $|Z|$ large enough. As $G(\Fp)=n$ by
\refe{pars}, one could expect that $G(Z)\gg n^c$ with a positive constant $c$ 
and assuming that $|Z|$ is large. This, however, is not the case. In fact, it 
is easy to show (see Theorem \reft{ex1} below) that for any $\eps\in(0,1)$, 
any positive integer $n$, and sufficiently large $p$, there exist $A$ and $Z$ 
with $|A|=n$ and $|Z|\ge(1-\eps)p$ such that $G(Z)\le1/\eps$. Moreover, there 
is no $\delta>0$ such that $G(Z)\ge\delta$ holds for all $A,Z\seq\Fp$ with 
$|Z|\ge p/2$ (see Theorem 6). It is reasonable to expect that 
$G(Z)\gg n^{-\delta}$ for any $\delta>0$ and $|Z|>\delta p$; however, the 
estimate we were able to prove is considerably weaker.

\begin{theorem}
Let $Z\seq\Fp$, and suppose that $|Z|\ge(1-\eps)p$, where $\eps\in(0,1)$. Then
  $$ G(Z) > \frac1e\,n^{-\frac\eps{1-\eps}}. $$
\end{theorem}

\noindent
{\it Proof.}
Using the inequality between arithmetic and geometric means, we get
  $$ (G(Z))^{|Z|} \ge \prod_{z\in Z}|S_A(z)|^2
             = \prod_{z\in\Fp}|S_A(z)|^2\;\prod_{z\notin Z}|S_A(z)|^{-2}. $$
The first product in the right-hand side is $|S_A(0)|^2=n^2$ times the norm
of a non-zero algebraic integer, whence
  $$ (G(Z))^{|Z|} > \prod_{z\notin Z}|S_A(z)|^{-2} $$
and therefore using the arithmetic-geometric means inequality once again and taking into account \refe{pars} we obtain
\begin{gather}
  (G(Z))^{-|Z|}
        < \left(\frac1{p-|Z|}\sum_{z\notin Z}|S_A(z)|^2\right)^{p-|Z|}
           < \left(\frac{np}{p-|Z|}\right)^{p-|Z|}, \notag\\
  G(Z) > \left(\frac{np}{p-|Z|}\right)^{-\frac{p-|Z|}{|Z|}} \label{e:G}.
\end{gather}
Write $\alp=(p-|Z|)/|Z|$. Then
  $$ \left(\frac p{p-|Z|}\right)^{-\frac{p-|Z|}{|Z|}}
            =\left(1+\frac1\alp\right)^{-\alp} > e^{-1}, $$
and the result follows from \refe{G} since
$$ \frac{p-|Z|}{|Z|}\le\frac\eps{1-\eps}.$$ $\hfill  \Box$ 

A continuous analog of the quantity $G(Z)$ was considered by Pichorides, who
proved the following.
\begin{theorem}{\rm ([P80, Lemma\,\, 1])}
%\begin{theorem}[\cite[Lemma 1]{b:p}]
Let $S(z)=1+\sum_{j=1}^k a_j\e{jz}$, where $a_j$ are real coefficients. For
a set $Z\seq[0,1)$ of measure $\mu(Z)>0$ define
  $$ G_1(Z) := \frac1{\mu(Z)}\int_Z |S(z)|\,dz. $$
Suppose that $\mu(Z)<1$ and let $\oZ$ be the complement of $Z$ in $[0,1)$. Then
  $$ (G_1(Z))^{\mu(Z)}\,(G_1(\oZ))^{\mu(\oZ)} \ge 1. $$
\end{theorem}

We now show that $G(Z)$ can be rather small even for $|Z|$ large.

\begin{theorem}\label{t:ex1}
For any $\eps\in(0,1)$, any positive integer $n$, and $p$ sufficiently large, 
there exist $A,Z\seq\Fp$ such that $|A|=n,\,|Z|\ge(1-\eps)p$, and 
$G(Z)\le1/\eps$.
\end{theorem}

\noindent
{\it Proof.}
Consider the trigonometric polynomial
  $$ P(x)=\sum_{j=0}^{n-1}\e{jx}. $$
For $0<x<1/2$ we have
  $$ |P(x)|=\left|\frac{\e{nx}-1}{\e{x}-1}\right|
               =\frac{|\sin(\pi nx)|}{\sin(\pi x)}
                                     \le\frac1{\sin(\pi x)}<\frac1{2x}, $$
whence
\begin{equation}\label{e:Int}
  \int_{\eps/2}^{1/2}|P(x)|^2dx
               <\int_{\eps/2}^{1/2}\frac{dx}{4x^2}=\frac1{2\eps}-\frac12.
\end{equation}
Denote
  $$ E=[\eps/2, 1-\eps/2] $$
and
  $$ E_\delta=[\eps/2-\delta, 1-\eps/2+\delta] $$
for $\delta>0$. By \refe{Int},
  $$ \int_E|P(x)|^2dx
% =\int_{\eps/2}^{1/2}|P(x)|^2dx+\int_{1/2}^{1-\eps/2}|P(x)|^2dx
                            =2\int_{\eps/2}^{1/2}|P(x)|^2dx<\frac1{\eps}-1, $$
and therefore for sufficiently small $\delta>0$ we have
\begin{equation}\label{e:Int2}
  \int_{E_\delta}|P(x)|^2dx<\frac1{\eps}-1.
\end{equation}
Let $A=\{0\longc n-1\}$. For any $p$ put $Z=\{z:z/p\in E_\delta\}$, so that
\begin{equation}\label{e:SizeZ}
  |Z|\ge(1-\eps)p
\end{equation}
for $p$ large enough. Also,
  $$ \lim_{p\to\infty}\sum_{z\in Z}|S_A(z)|^2/p=\int_{E_\delta}|P(x)|^2dx, $$
and it follows from \refe{Int2} that for sufficiently large $p$
\begin{equation}\label{e:Sum}
  \sum_{z\in Z} |S_A(z)|^2 < p\left(\frac1{\eps}-1\right).
\end{equation}
Inequalities \refe{SizeZ} and \refe{Sum} readily imply the required estimate 
$G(Z)\le1/\eps$.
\hfill \qed

The following theorem is the main result of [K97].

\begin{theorem}{\rm (cf. [K97])}
For any $\delta>0$ there exist a prime number $p$ and sets $A,Z\seq\Fp$ such
that $|Z|>p/2$ and $G(Z)<\delta$.
\end{theorem}

\noindent
{\it Sketch of proof. } 
The main part of the proof is a construction of a trigonometric polynomial 
$P(x)=\sum_{a\in A}\e{ax}$ (where $A$ is a finite set of integers) and a set $E\in[0,1]$ such that $E$ is the union of finitely many segments,
\begin{equation}\label{e:mu}
  \mu(E)>1/2,
\end{equation}
and
\begin{equation}\label{e:Int3}
  \int_E|P(x)|^2dx<\delta/2.
\end{equation}
Once $P$ and $E$ are constructed, it is easy to complete the proof using the 
same kind of argument as in Theorem \reft{ex1}.

%We use the scheme of the proof of the theorem in \refb{k}.
We can assume that $\delta<1$. Let $\eta_0,\eta_1,\dots$ be independent 
random variables, distributed uniformly in $[0,1]$. We define 
$\xi_j=2\cos(\pi\eta_j)$ and $\psi_j=\ln|\xi_j|$, and we observe that 
$\psi_j$ are independent and satisfy
  $$ {\bf E}\psi_j=0,\ {\bf E}|\psi_j|^3<\infty. $$
It follows from the Berry-Essen theorem (see [B76, Theorem 12.4])
that there exists a constant $C>0$ such that for any positive integer $m$
\begin{equation}\label{e:be1}
  \Pr\left(\sum_{j=0}^{m-1}\psi_j\le C\right)>1/2
\end{equation}
and moreover,
\begin{equation}\label{e:be2}
  \Pr\left(-\ln(4/\delta)\le\sum_{j=0}^{m-1}\psi_j\le C\right)
                                                          <\delta/(4e^{2C})
\end{equation}
for $m$ sufficiently large.

We denote by $(\Omega,\nu)$ the probability space and by $F\subset\Omega$ the 
event $\sum_{j=0}^{m-1}\psi_j\le C$. By \refe{be1},
\begin{equation}\label{e:F1}
  \nu(F)>1/2
\end{equation}
and from \refe{be2} (see [K97] for details)
  $$ \int_F\exp\left(\sum_{j=0}^{m-1}\psi_j\right)d\nu<\delta/2, $$
or equivalently
\begin{equation}\label{e:F2}
  \int_F\prod_{j=0}^{m-1}|\xi_j|d\nu<\delta/2.
\end{equation}
Using weak convergence of the distribution function of the random vectors
$(2\cos(2\pi x),$\\
$2\cos(2\pi lx),\dots,2\cos(2\pi l^{m-1}x))$ to the distribution 
function of $(\xi_0,\xi_1,\dots,\xi_{m-1})$ as $l\to\infty$ (cf. [K97])), we
get weak convergence of the distribution function of
$\prod_{j=0}^{m-1}2\cos(2\pi l^jx)$ to the distribution function of 
$\prod_{j=0}^{m-1}\xi_j$ as $l\to\infty$. Therefore, for the $2^m$-term 
trigonometric polynomial
  $$ P(x)=\prod_{j=0}^{m-1}\left(1+\e{l^jx}\right) $$
and for the set
  $$ E=\{x\in[0,1]:|P(x)|\le e^C\}, $$
using the identity
  $$ |P(x)|=\prod_{j=0}^{m-1}|2\cos(\pi l^jx)| $$
one can deduce from \refe{F1} and \refe{F2} the required inequalities \refe{mu} 
and \refe{Int3}, provided that $l$ is large enough.
\hfill \qed

Analysis of the proof shows that if $n$ is a power of $2$, then one can have 
$G(Z)\ll(\ln n)^{-1/2}$ with $|Z|>p/2$ and 
$G(Z)\ll\exp(-c(\alp)(\ln n)^{1/2})$ with $|Z|\ge\alp p,\,0<\alp<1/2$. Also, 
for arbitrary $n\ge2$ we can give examples with the same estimates for $G(Z)$ 
under weaker restrictions for $|Z|$: $G(Z)\ll(\ln n)^{-1/2}$ with $|Z|>p/4$ 
and $G(Z)\ll\exp(-c(\alp)(\ln n)^{1/2})$ with $|Z|\ge\alp p,\,0<\alp<1/4$.
\vskip 30pt
\section*{\normalsize 4. Large Exponential Sums}

For exponential sums corresponding to a set $A$ of {\em integers}, a rather
precise estimate for the number of ``large'' sums was obtained by Yudin in [Y73]. Yudin proved that
\begin{equation}\label{e:y}
  {\rm mes}\,\{z\in[0,1)\colon |S_A(z)|>(1-\eps)n\}
                        \le \frac{2\sqrt 6}\pi\,\frac1n\,\eps^{1/2}(1+o(1)),
\end{equation}
where
  $$ S_A(z)=\sum_{a\in A}\e{az}\,;\quad z\in\R $$
and assuming that $n\to\infty$ and $\eps=o(1)$. Equality is attained when $A$
is an arithmetic progression. In [B99], Besser replaced the assumption
$\eps=o(1)$ by $\eps<c$ with an absolute constant $c>0$; this required numerous
fresh ideas and the final result differs considerably from \refe{y}.

Yudin's argument was based on a ``rearrangement theorem'' due to Hardy and
Littlewood. In [L00, Theorem 1], the second of the present authors was 
able to obtain residue analogs of the results of Hardy and Littlewood, which 
allowed him to extend Yudin's theorem onto the residues case.

We now return back to our original notation, assuming $A\seq\Fp$ and $z\in\Fp$.
It turns out that a convenient way to measure the number of large exponential
sums is provided by the function
  $$ T_A(\phi) := \{z\in\Fp^\times\colon |S_A(z)|>n\cos\phi\};
                                                    \quad 0\le\phi\le\pi/2. $$
Evidently, $T_A(\phi)$ is piecewise constant, monotonically increasing, and
satisfies $T_A(0)=0$ and $T_A(\pi/2)=p-1$. A non-trivial property of
$T_A(\phi)$ which explains why it arises naturally in this context is its
sup-additivity, expressed in the following lemma.

\begin{lemma}{\rm ([L00, Lemma 1])}
%\begin{lemma}[{\cite[Lemma 1]{b:l2}}]
Suppose that $\phi_1,\phi_2\ge 0$ and $\phi_1+\phi_2\le\pi/2$. Then
  $$ T_A(\phi_1+\phi_2) \ge \min\{T_A(\phi_1)+T_A(\phi_2),\,p-1\}. $$
\end{lemma}
(A parallel lemma for sets of integers is implicit in [Y73].)

Assume for a moment that the assertion of the lemma can be strengthened to
\begin{equation}\label{e:wrong}
   T_A(\phi_1+\phi_2) \ge T_A(\phi_1)+T_A(\phi_2).
\end{equation}
By induction, it follows then that $T_A(j\phi_0)\ge jT_A(\phi_0)$ provided
$j\phi_0\le\pi/2$. Choosing $j=\lfloor \phi/\phi_0\rfloor$ and taking into
account that $T_A(\phi)\ge T_A(j\phi_0)$ as $T_A$ is increasing, we obtain

\begin{corollary}{\rm ([L00, Lemma 2])}
%\begin{corollary}[{\cite[Lemma 2]{b:l2}}]\label{c:T}
Suppose that $0<\phi,\phi_0\le\pi/2$. Then
  $$ T_A(\phi) \ge \left\lfloor \frac\phi{\phi_0} \right\rfloor T_A(\phi_0). $$
\end{corollary}

Though it can be shown that \refe{wrong} {\em does not} hold in general,
Corollary 1 is true and is established in [L00]. In conjunction with
a rearrangement theorem for residues, it was used to prove the following
analog of \refe{y}.

\begin{theorem}{\rm ([L00, Theorem 5])}
%\begin{theorem}[{\cite[Theorem 5]{b:l2}}]\label{t:TA}
For any set $A\seq\Fp$ of $n=|A|\ge 4$ residues modulo a prime $p$ and any
$\phi\in[0,\pi/6]$ we have
  $$ T_A(\phi) \le \frac{2\sqrt3}{\pi}\,\frac pn\,\phi\,
                                          (1+n^{-2})(1+2\phi^{2/3}). $$
\end{theorem}
This theorem is sharp in the sense that equality is attained asymptotically
(for $n\to\infty$ and $\phi\to 0$) if $A$ is an arithmetic progression modulo
$p$.

We conclude by outlining the proof of Theorem 7.

\noindent
{\it Sketch of proof. }
For brevity we drop below the subscript $A$ in $S_A(z)$ and $T_A(\phi)$, and
we define
  $$ A_0:=\{0\longc n-1\},\ S_0(z):=S_{A_0}(z),\ T_0(z):=T_{A_0}(z). $$
For $k\ge 1$ consider the moments
  $$ \frac1p\sum_{z\in\Fp}|S(z)|^{2k}\quad \text{and}
                              \qquad  \frac1p\sum_{z\in\Fp}|S_0(z)|^{2k}. $$
The former is the number of solutions of the equation
$a_1\longp a_k=a_1'\longp a_k'$ in the variables $a_i,a_i'\in A$, the latter
is the number of solutions of the same equation in the variables
$a_i,a_i'\in A_0$. By [L00, Theorem 1], the number of solution is
maximized when the variables range over an arithmetic progression; thus,
  $$ \sum_{z\in\Fp}|S(z)|^{2k} \le \sum_{z\in\Fp}|S_0(z)|^{2k}, $$
and partial integration allows one to rewrite it as
  $$ \int_0^{\pi/2} T(\phi)\cos^{2k-1}\phi\,\sin\phi\,d\phi
           \le  \int_0^{\pi/2} T_0(\phi)\cos^{2k-1}\phi\,\sin\phi\,d\phi. $$
Furthermore, $T_0(\phi)$ can be estimated explicitly and it can be shown that 
the integral at the right does not exceed
  $$ \sqrt{\frac6\pi}\,\frac pn\,(2k)^{-3/2}(1+o(1)) $$
(as $n,k\to\infty$). As to the integral at the left, we use Corollary 1 
to estimate it from below by
  $$ T(\phi_0) \int_0^{\pi/2} \left\lfloor\frac\phi{\phi_0}\right\rfloor
                                          \cos^{2k-1}\phi\,\sin\phi\,d\phi
        \ge \frac{T(\phi_0)}{\phi_0}\,\sqrt{\frac\pi2}\,(2k)^{-3/2}(1+o(1)) $$
for any fixed $\phi_0$.
Therefore,
  $$  \frac{T(\phi_0)}{\phi_0}\,\sqrt{\frac\pi2}\,(2k)^{-3/2}
                       \le \sqrt{\frac6\pi}\,\frac pn\,(2k)^{-3/2}(1+o(1)) $$
and the result follows.
\hfill \qed
\vskip 30pt
\section*{\normalsize Acknowledgment}

The work on this paper was initiated in July 1999 when the authors attended
the ``Paul Erd\H os and his mathematics'' conference in Budapest and its
satellite workshop on combinatorial number theory. Our visit was partially 
supported by the Erd\H os center. It is our pleasure to thank the Erd\H os 
center for its hospitality and the excellent working environment.

%\begin{thebibliography}{9}
%\bibitem[B76]{b:br} {\sc R.~N.~Bhattacharya, R.~Rao}, Normal approximation and 
%  asymptotic expansions, John Wiley \& Sons, New York, 1976.
%\bibitem[B99]{b:b} {\sc A.~Besser}, Sets of integers with large trigonometric
%  sums, {\em Ast\'erisque} {\bf 258} (1999), 35--76.
%\bibitem[K97]{b:k} {\sc S.~V.~Konyagin}, On a question of Pichorides,
%  {\em C. R. Acad. Sci. Paris Ser. I Math.} {\bf 324} (1997), 385--388.
%\bibitem[L98]{b:l1} {\sc V.F.~Lev}, On the number of solutions of a linear
%  equation over finite sets, {\em J.~Comb. Theory, Ser.~A} {\bf 83} (1998),
%  251--267.
%\bibitem[L00]{b:l2} {\sc V.F.~Lev}, Moments of exponential sums and linear
%  equations over $\Fp$, {\em Submitted}.
%\bibitem[M86]{b:m} {\sc G.~Myerson}, How small can a sum of roots of unity be?
%  {\em American Math. Monthly} {\bf 93 } (1986) , 457--459.
%\bibitem[P80]{b:p} {\sc S.K.~Pichorides}, On the $L^1$-norm of exponential
%  sums, {\em Annales de l'Inst. Fouier} {\bf 30} (2) (1980), 79--89.
%\bibitem[Y73]{b:y} {\sc A.A.~Yudin}, On the measure of large values of a
%  trigonometric sum, {\em in:} Number Theory (under the edition of
%  G.A.~Freiman, A.M.~Rubinov, E.V.~Novosyolov), Kalinin State Univer.,
%  Moscow (1973), 163--174.
%\end{thebibliography}
\vskip 30pt
\section*{\normalsize References}

\baselineskip=5pt
[B76]{\sc R.~N.~Bhattacharya, R.~Rao}, Normal approximation and 
  asymptotic expansions, John Wiley \& Sons, New York, 1976.

\noindent
[B99] {\sc A.~Besser}, Sets of integers with large trigonometric
  sums, {\em Ast\'erisque} {\bf 258} (1999), 35--76.

\noindent
[K97] {\sc S.~V.~Konyagin}, On a question of Pichorides,
  {\em C. R. Acad. Sci. Paris Ser. I Math.} {\bf 324} (1997), 385--388.

\noindent
[L98] {\sc V.F.~Lev}, On the number of solutions of a linear
  equation over finite sets, {\em J.~Comb. Theory, Ser.~A} {\bf 83} (1998),
  251--267.

\noindent
[L00] {\sc V.F.~Lev}, Linear
  equations over $\F_p$ and moments of
exponential sums, Duke Math. Journal, {\it to appear}.

\noindent
[M86] {\sc G.~Myerson}, How small can a sum of roots of unity be?
  {\em American Math. Monthly} {\bf 93 } (1986) , 457--459.

\noindent
[P80] {\sc S.K.~Pichorides}, On the $L^1$-norm of exponential
  sums, {\em Annales de l'Inst. Fouier} {\bf 30} (2) (1980), 79--89.

\noindent
[Y73] {\sc A.A.~Yudin}, On the measure of large values of a
  trigonometric sum, {\em in:} Number Theory (under the edition of
  G.A.~Freiman, A.M.~Rubinov, E.V.~Novosyolov), Kalinin State Univer.,
  Moscow (1973), 163--174.

\end{document}