\begin{document}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{definition}{Definition}
\newtheorem{question}[theorem]{Open Question}

\def{\mathcal A}{{\mathcal A}}
\def{\mathcal B}{{\mathcal B}}
\def{\mathcal C}{{\mathcal C}}
\def{\mathcal D}{{\mathcal D}}
\def{\mathcal E}{{\mathcal E}}
\def{\mathcal F}{{\mathcal F}}
\def{\mathcal G}{{\mathcal G}}
\def{\mathcal H}{{\mathcal H}}
\def{\mathcal I}{{\mathcal I}}
\def{\mathcal J}{{\mathcal J}}
\def{\mathcal K}{{\mathcal K}}
\def{\mathcal L}{{\mathcal L}}
\def{\mathcal M}{{\mathcal M}}
\def{\mathcal N}{{\mathcal N}}
\def{\mathcal O}{{\mathcal O}}
\def{\mathcal P}{{\mathcal P}}
\def{\mathcal Q}{{\mathcal Q}}
\def{\mathcal R}{{\mathcal R}}
\def{\mathcal S}{{\mathcal S}}
\def{\mathcal T}{{\mathcal T}}
\def{\mathcal U}{{\mathcal U}}
\def{\mathcal V}{{\mathcal V}}
\def{\mathcal W}{{\mathcal W}}
\def{\mathcal X}{{\mathcal X}}
\def{\mathcal Y}{{\mathcal Y}}
\def{\mathcal Z}{{\mathcal Z}}

\def{\mathbb A}{{\mathbb A}}
\def{\mathbb B}{{\mathbb B}}
\def{\mathbb C}{{\mathbb C}}
\def{\mathbb D}{{\mathbb D}}
\def{\mathbf E}{{\mathbb E}}
\def{\mathbb F}{{\mathbb F}}
\def{\mathbb G}{{\mathbb G}}
\def{\mathbb H}{{\mathbb H}}
\def{\mathbb I}{{\mathbb I}}
\def{\mathbb J}{{\mathbb J}}
\def{\mathbb K}{{\mathbb K}}
\def{\mathbb L}{{\mathbb L}}
\def{\mathbb M}{{\mathbb M}}
\def{\mathbb N}{{\mathbb N}}
\def{\mathbb O}{{\mathbb O}}
\def{\mathbb P}{{\mathbb P}}
\def{\mathbb Q}{{\mathbb Q}}
\def{\mathbb R}{{\mathbb R}}
\def{\mathbb S}{{\mathbb S}}
\def{\mathbb T}{{\mathbb T}}
\def{\mathbb U}{{\mathbb U}}
\def{\mathbb V}{{\mathbb V}}
\def{\mathbb W}{{\mathbb W}}
\def{\mathbb X}{{\mathbb X}}
\def{\mathbb Y}{{\mathbb Y}}
\def{\mathbb Z}{{\mathbb Z}}

\def{\mathbf E}{{\mathbf E}}
\def{\mathbb F}p{{\mathbb F}_p}
\def{\mathbf{e}}_p{{\mathbf{e}}_p}
\def{\mathbb B}n{{\mathfrak B}_n}

\def\scriptstyle{\scriptstyleiptstyle}
\def\cr{\cr}
\def\leqslantft({\leqslantft(}
\def\right){\right)}
\def\leqslantft[{\leqslantft[}
\def\right]{\right]}
\def\langle{\langle}
\def\rangle{\rangle}
\def\fl#1{\leqslantft\lfloor#1\right\rfloor}
\def\rf#1{\leqslantft\lceil#1\right\rceil}
\def\leqslant{\leqslantqslant}
\def\geqslant{\geqslantqslant}
\def{\mathbf{e}}_ps{\varepsilon}
\def\qquad\mbox{and}\qquad{\qquad\mbox{and}\qquad}

\def\vec#1{\mathbf{#1}}
\def\inv#1{\overline{#1}}
\def\vol#1{\mathrm{vol}\,{#1}}

\newcommand{\comm}[1]{\marginpar{
\vskip-\baselineskip 
\raggedright\footnotesize
\itshape\hrule
#1\par
\hrule}}

\def\vskip5pt\hrule\vskip5pt{\vskip5pt\hrule\vskip5pt}

\title{\bf On the Distribution of  Kloosterman 
Sums}

\author{ 
{\sc Igor E. Shparlinski} \cr
{Department of Computing, Macquarie University} \cr
{Sydney, NSW 2109, Australia} \cr
{igor@ics.mq.edu.au}}

\date{\today}
\pagenumbering{arabic}

\maketitle

\begin{abstract}
For   a   prime $p$, we consider Kloosterman 
sums
$$
K_{p}(a) = \sum_{x\in {\mathbb F}_p^*} \exp( 2 \pi i (x + ax^{-1})/p), \qquad a \in {\mathbb F}_p^*,  
$$
over a finite field of $p$ elements.
It is well known that  due to results of Deligne, Katz and Sarnak, 
the distribution of the sums $K_{p}(a)$ when $a$ runs through ${\mathbb F}_p^*$
is in accordance with the Sato--Tate conjecture. 
Here we show that the same holds where $a$ runs through the sums
$a = u+v$ for $u \in {\mathcal U}$, $v \in {\mathcal V}$ for any two sufficiently large
sets ${\mathcal U}, {\mathcal V} \subseteq {\mathbb F}_p^*$. 

We also improve  a recent bound on the 
nonlinearity of a Boolean function associated with the sequence of
signs of Kloosterman sums. 
\end{abstract}

\section{Introduction}
\label{sec:intro}

For a prime $p$ we use ${\mathbb F}_p$ to denote the finite field of $p$ 
elements.  

For $a \in {\mathbb F}_p^*$ we consider the Kloosterman 
sum
$$
K_{p}(a) = \sum_{x\in {\mathbb F}_p^*} {\mathbf{e}}_p(x + ax^{-1}), 
$$
where
$$
{\mathbf{e}}_p(z) = \exp( 2 \pi i z/p)
$$
(we identify  ${\mathbb F}_p$ with the set $\{0, 1, \ldots, p-1\}$).
Since for the complex conjugated sum we have
$$
\inv{ K_{p}(a)}  = \sum_{x\in {\mathbb F}_p^*} {\mathbf{e}}_p(-x - ax^{-1}) =  K_{p}(a) 
$$
the values of $K_{p}(a)$ are real. 

Accordingly to the Weil bound, see~\cite{LN}, 
$$
\leqslantft| K_{p}(a)\right| \leqslant 2 \sqrt{p}, \qquad a \in {\mathbb F}_p^*. 
$$
Therefore,  we can  define the angles $\psi_{p}(a)$ 
by the relations
$$
 K_{p}(a) = 2\sqrt{p} \cos \psi_{p}(a) \qquad\mbox{and}\qquad 0 \leqslant \psi_{p}(a)  \leqslant \pi.
$$

The famous \emph{Sato--Tate} conjecture asserts that 
for any fixed non-zero integer $a$, when $p$ varies,  the angles
$\psi_{p}(a)$ are distributed accordingly to  the
\emph{Sato--Tate  density}
$$
 \mu_{ST}(\alpha,\beta) = \frac{2}{\pi}\int_\alpha^\beta  \sin^2 \gamma\, d \gamma, 
$$
see~\cite{Adolph,ChaLi,FoMic1,FoMic2,FMRS,Katz,KatzSar,Lau,Mich1,Mich2,Nied}
for various 
modifications and generalisations of this conjecture and further references.

It is also known that when a sufficiently large prime $p$ is fixed  
and $a$ runs through ${\mathbb F}_p^*$, then, as has been shown by Katz~\cite[Chapter~13]{Katz}, 
the work of Deligne on the \emph{Weil conjecture}  implies that the  
distribution of  the sums $K_{p}(a)$ is in accordance with the 
Sato--Tate density, 
see also~\cite{KatzSar}. Furthermore, a quantitative form of 
this result is given by Niederreiter~\cite{Nied}. 
Namely, if  ${\mathcal A}_p(\alpha,\beta)$ is the set  
of $a \in {\mathbb F}_p^*$  with $ \alpha \leqslant \psi_{p}(a) \leqslant \beta$ 
then by the main result of Niederreiter~\cite{Nied}, we have: 
\begin{equation}
\label{eq:Nied Bound}
\max_{0 \leqslant \alpha < \beta \leqslant \pi} 
\leqslantft|\# {\mathcal A}_p(\alpha,\beta) - \mu_{ST}(\alpha,\beta) p  \right| \ll p^{3/4}.
\end{equation}

Combining  results of  Fouvry, Michel, Rivat and S{\'a}rk{\"o}zy~\cite[Lemma~2.3]{FMRS} 
(with $r=1$)  and of Niederreiter~\cite[Lemma~3]{Nied}  one can show that elements of
${\mathcal A}_p(\alpha,\beta) $ are uniformly distributed, 
in the following sense. For any $\lambda \in {\mathbb F}_p^*$
and  integer $M$ with  $1 \leqslant  M \leqslant p-1$
we put 
$$
{\mathcal A}_p(\lambda, M;\alpha,\beta) = \{a \in {\mathcal A}_p(\alpha,\beta) \ : \ \lambda a \in [1,M]\}. 
$$
Then for $1 \leqslant M \leqslant p-1$, the following bound holds:
\begin{equation}
\label{eq:FMRS-Nied Bound}
\max_{\lambda \in {\mathbb F}_p^*}\, \max_{0 \leqslant \alpha < \beta \leqslant \pi} 
\leqslantft|\# {\mathcal A}_p(\lambda, M;\alpha,\beta)  - \mu(\alpha,\beta) M  \right|
 \ll M^{1/2} p^{1/4} (\log p)^{1/2} .
\end{equation}

Fouvry, Michel, Rivat and S{\'a}rk{\"o}zy~\cite{FMRS} also remark that
combining a result of Fouvry and Michel~\cite{FoMic1}  with the technique of 
Vaaler~\cite{Vaal} one can show that
$$
 \max_{0 \leqslant \alpha < \beta \leqslant \pi} 
\leqslantft|\# {\mathcal Q}_p(\alpha,\beta)  - \mu_{ST}(\alpha,\beta) p  \right| \ll p^{3/4} 
$$
where
$$
{\mathcal Q}_p(\alpha,\beta)   = \{a \in {\mathbb F}_p : \ a^2 \in {\mathcal A}_p(\alpha,\beta)\}. 
$$
The same bound can also be immediately obtained if one applies  the 
result of Niederreiter~\cite[Lemma~3]{Nied} to the bound  
of  Michel~\cite[Corollary~2.4]{Mich2} 
(see also~\cite[Lemma~2.1]{FoMic1}). 
 

Here we show that the same type of distribution is preserved when $a$ runs through the sums
$a = u + v$  where $u \in {\mathcal U}$, $v \in {\mathcal V}$ for any two sufficiently large
sets ${\mathcal U}, {\mathcal V} \subseteq {\mathbb F}_p^*$. 
Namely, for any two sets ${\mathcal U}, {\mathcal V} \subseteq {\mathbb F}_p^*$, we put 
$$
{\mathcal W}_p({\mathcal U}, {\mathcal V};\alpha,\beta) = \{(u,v) \in {\mathcal U}\times {\mathcal V}\ : \ u+v
\in {\mathcal A}_p(\alpha,\beta)\}. 
$$
In particular, we obtain an asymptotic formula for 
$\#{\mathcal W}_p({\mathcal U}, {\mathcal V};\alpha,\beta) $ which is nontrivial whenever 
\begin{equation}
\label{eq:Threshold}
\# {\mathcal U} \# {\mathcal V} \geqslant p^{3/2 + \varepsilon}
\end{equation} 
for any fixed $\varepsilon > 0$ and sufficiently large $p$. 

Then, we also improve the upper bound of~\cite{Shp} on the
\emph{nonlinearity} of the Boolean function
associated with the sequence  of signs of Kloosterman sums, that is
for the function
\begin{equation}
\label{eq:Bool}
f(a) = \leqslantft\{  \begin{array}{ll}
0,& \quad \text{if}\  K(a) > 0\ \text{or}\ a=0 , \cr
1, & \quad \mbox{if}\ K(a) < 0,
\end{array} \right. \qquad a = 0, 1, \ldots\,2^{n-1}, 
\end{equation}
where $n$ is defined  by the inequalities
$$
2^n \leqslant  p < 2^{n+1}.
$$

We denote by ${\mathbb B}n$ the $n$-dimensional 
Boolean cube ${\mathbb B}n = \{0,1\}^n$  and in a natural 
way identify 
its elements with the integers in the range $0 \leqslant a \leqslant 2^n -1$
(and thus with a subset of ${\mathbb F}_p$). 

We define the {\it Fourier
coefficients\/} of $f(a)$ as 
$$
{\widehat f}(r) = 2^{-n} \sum_{a \in{\mathbb B}n}
(-1)^{  f(a) + \langle h, r  \rangle}  , \qquad r \in {\mathbb B}n, 
$$
where   $\langle a,  r \rangle$ denote the inner product of
$a,r \in{\mathbb B}n$. Furthermore, we recall that 
$$
N(f) =  2^{n-1} -  2^{n-1} \max_{r \in {\mathbb B}n}\leqslantft| {\widehat f}(r)  \right|
$$
is called the {\it nonlinearity\/} of $f$ and is an important
cryptographic  characteristic, for example, see~\cite{CarDing}. 
In particular, it is   the smallest 
possible Hamming distance between the vector of values of $f$ and the vector 
of values of a linear function in $n$ variables over the ${\mathbb F}_2$.

Several results about some  measures of pseudorandomess 
of the sequence  of signs of Kloosterman sums have recently 
been obtained by 
Fouvry, Michel, Rivat and S{\'a}rk{\"o}zy~\cite{FMRS}.
Motivated by (and actually  using) the results of~\cite{FMRS}, 
the bound 
$$
N(f) = 2^{n-1} \leqslantft(1  + O\leqslantft( 2^{-n/24} n^{1/12} \right)\right).
$$
has been obtained in~\cite{Shp}.  
Here we again use some results of~\cite{FMRS}, 
but in a slightly different way and  improve this bound.

\section{Distribution of Elements of ${\mathcal A}_p(\alpha,\beta)$}
\label{sec:prep}
 

For a sequence of
$N$ real numbers $\gamma_1,\ldots,\gamma_N\in[0,1)$ the  \emph{discrepancy} is
defined by
$$
D =\max_{0\leqslant \gamma  \leqslant 1}\leqslantft|\frac{T(\gamma,N)}{N}-\gamma \right|,
$$
where  $T(\gamma,N)$ is the number of  
$n\leqslant N$ such that $\gamma_n\leqslant \gamma$. 

We also recall our agreements that the elements of ${\mathbb F}_p$ have 
canonical representation as integers of the interval $[0,p-1]$.
Thus for any field element $c \in{\mathbb F}_p$ we interpret $c/p$ as
a rational number in the interval $[0,1]$. 
Hence, for $\lambda \in {\mathbb F}_p^*$ we can define
the discrepancy $D_p(\lambda;\alpha,\beta)$ of the sequence
$$
\frac{\lambda a}{p}, \quad  a \in {\mathcal A}_p(\alpha,\beta). 
$$ 
Then  the bound~\eqref{eq:FMRS-Nied Bound} implies that
$$
\max_{1 \leqslant M \leqslant p-1}\, 
\max_{\lambda \in {\mathbb F}_p^*}\, \max_{0 \leqslant \alpha < \beta \leqslant \pi} 
\leqslantft|\# {\mathcal A}_p(\lambda, M;\alpha,\beta)  - \mu(\alpha,\beta) M  \right|
 \ll p^{3/4} (\log p)^{1/2}  
$$
which can be reformulated 
in the following form:

\begin{lemma}
\label{lem:Discr} We have,
$$
 \max_{\lambda \in {\mathbb F}_p^*}\,\max_{0 \leqslant \alpha < \beta \leqslant \pi} D_p(\lambda;\alpha,\beta) \ll 
p^{-1/4} (\log p)^{1/2} .
$$
\end{lemma}

Our main tool is a bound of exponential sums
 with elements
of ${\mathcal A}_p(\alpha,\beta)$. For $\lambda \in {\mathbb F}_p^*$ we define
$$
S_p(\lambda;\alpha,\beta) = \sum_{a \in {\mathcal A}_p(\alpha,\beta)} {\mathbf{e}}_p(\lambda a).
$$

\begin{lemma}
\label{lem:Exp Sum} We have,
$$
 \max_{\lambda \in {\mathbb F}_p^*}\,\max_{0 \leqslant \alpha < \beta \leqslant \pi}
\leqslantft|S_p(\lambda;\alpha,\beta)\right| \ll  p^{3/4} (\log p)^{1/2} .
$$
\end{lemma}

\begin{proof} 
We  recall that for any real smooth function $F(\gamma)$ defined on 
the interval $[0,1]$ 
and any  sequence of
$N$ real numbers $\gamma_1,\ldots,\gamma_N\in[0,1]$ of discrepancy $D$, 
we have
$$
 \frac{1}{N} \sum_{n =1}^N F(\gamma_n) = \int_0^1 F(\gamma) d\, \gamma + O(D\max_{0\leqslant \gamma  \leqslant
1}\leqslantft|F'(\gamma) \right|),
$$
see~\cite[Chapter~2, Theorem~5.4]{KuNi}. 
Writing 
$$
S_p(\lambda;\alpha,\beta) =  \sum_{a \in {\mathcal A}_p(\alpha,\beta)} \cos\leqslantft(2\pi \frac{\lambda a}{p}\right)
+ i \sum_{a \in {\mathcal A}_p(\alpha,\beta)} \sin\leqslantft(2\pi \frac{\lambda a}{p}\right)
$$
and applying Lemma~\ref{lem:Discr},  we obtain the desired bound. 
\end{proof}

\section{Sato--Tate Conjecture for Sum Sets}
\label{sec:main}

\begin{theorem}
\label{thm:Set W} For any two sets ${\mathcal U}, {\mathcal V} \subseteq {\mathbb F}_p^*$, we have
$$
\max_{0 \leqslant \alpha < \beta \leqslant \pi} 
\leqslantft|\# {\mathcal W}_p({\mathcal U}, {\mathcal V};\alpha,\beta)   - \mu_{ST}(\alpha,\beta) \#{\mathcal U}\# {\mathcal V}  \right| \leqslant 
 \sqrt{\# {\mathcal U} \# {\mathcal V}} p^{3//4}  (\log p)^{1/2}. 
$$
\end{theorem}

\begin{proof}
Using the identity
\begin{equation}
\label{eq:Ident}
\frac{1}{p}\sum_{\lambda \in {\mathbb F}_p } {\mathbf{e}}_p(\lambda c)=
\leqslantft\{\begin{array}{ll}
1&\quad\text{if $c=0$,}\cr
0&\quad\text{if $c \in {\mathbb F}_p^*$,}
\end{array}
\right.
\end{equation}
we write 
\begin{eqnarray*}
 \# {\mathcal W}_p({\mathcal U}, {\mathcal V};\alpha,\beta) & = &\sum_{u \in {\mathcal U}} \sum_{v \in {\mathcal V}}
 \sum_{a \in {\mathcal A}_p(\alpha,\beta)} \frac{1}{p}\sum_{\lambda
\in
{\mathbb F}_p }
{\mathbf{e}}_p(\lambda(u + v -a) 
\cr & = &  \frac{1}{p}\sum_{\lambda
\in
{\mathbb F}_p } S_p(-\lambda;\alpha,\beta)  \sum_{u \in {\mathcal U}}{\mathbf{e}}_p(\lambda u) \sum_{v \in {\mathcal V}}
{\mathbf{e}}_p(\lambda v). 
\end{eqnarray*} 
Separating the term $\# {\mathcal A}_p(\alpha,\beta)\# {\mathcal U} \# {\mathcal V}/p$ corresponding 
to $\lambda = 0$,  we derive 
\begin{equation}
\label{eq:W and R}
 \# {\mathcal W}_p({\mathcal U}, {\mathcal V};\alpha,\beta) = \frac{\# {\mathcal A}_p(\alpha,\beta)\# {\mathcal U} \# {\mathcal V}}{p} +  O\leqslantft( R\right),
\end{equation}
where
$$
R = \frac{1}{p} \sum_{\lambda \in {\mathbb F}_p^* }  
\leqslantft|S_p(-\lambda;\alpha,\beta)\right|
 \leqslantft| \sum_{u \in {\mathcal U}}{\mathbf{e}}_p(\lambda u) \right| 
\leqslantft| \sum_{v \in {\mathcal V}} {\mathbf{e}}_p(\lambda v)\right|.
$$
Using Lemma~\ref{lem:Exp Sum} and the the Cauchy inequality, 
we obtain  
\begin{eqnarray*}
R  & \leqslant  & p^{-1/4} (\log p)^{1/2} \sum_{\lambda \in {\mathbb F}_p^* }   
 \leqslantft| \sum_{u \in {\mathcal U}}{\mathbf{e}}_p(\lambda u) \right| 
\leqslantft| \sum_{v \in {\mathcal V}} {\mathbf{e}}_p(\lambda v)\right|\cr
& \leqslant  & p^{-1/4} (\log p)^{1/2} \leqslantft(\sum_{\lambda \in {\mathbb F}_p^* }   
 \leqslantft| \sum_{u \in {\mathcal U}}{\mathbf{e}}_p(\lambda u) \right|^2\right)^{1/2}
 \leqslantft(\sum_{\lambda \in {\mathbb F}_p^* }    
\leqslantft| \sum_{v \in {\mathcal V}} {\mathbf{e}}_p(\lambda v)\right|^2\right)^{1/2}.
\end{eqnarray*} 
Furthermore, by~\eqref{eq:Ident} we see that
$$
\sum_{\lambda \in {\mathbb F}_p^* } \leqslantft| \sum_{u \in {\mathcal U}}{\mathbf{e}}_p(\lambda u) \right|^2
\leqslant  \sum_{\lambda \in {\mathbb F}_p}   
 \leqslantft| \sum_{u \in {\mathcal U}}{\mathbf{e}}_p(\lambda u) \right|^2 =
\sum_{\lambda \in {\mathbb F}_p }   
  \sum_{u_1,u_2 \in {\mathcal U}}{\mathbf{e}}_p(\lambda (u_1 - u_2)   = p \# {\mathcal U}.
$$ 
Similarly, 
$$
\sum_{\lambda \in {\mathbb F}_p^* } \leqslantft| \sum_{v \in {\mathcal V}}{\mathbf{e}}_p(\lambda v) \right|^2\leqslant p \# {\mathcal V}.
$$
Collecting the above estimates together, 
we obtain 
$$
R \leqslant \sqrt{\# {\mathcal U} \# {\mathcal V}}  p^{3/4} (\log p)^{1/2}
$$
which after substitution in~\eqref{eq:W and R} and using~\eqref{eq:Nied Bound}
leads us to the bound 
\begin{eqnarray*}
\leqslantfteqn{
\leqslantft|\# {\mathcal W}_p({\mathcal U}, {\mathcal V};\alpha,\beta)   - \mu_{ST}(\alpha,\beta) \#{\mathcal U}\# {\mathcal V}  \right|}\cr 
& & \qquad \qquad \qquad \ll   \#{\mathcal U}\# {\mathcal V}  p^{-1/4}+  \sqrt{\# {\mathcal U} \# {\mathcal V}}  p^{3/4}
(\log p)^{1/2}.
\end{eqnarray*}
It remains to note that 
$$
 \#{\mathcal U}\# {\mathcal V}  p^{-1/4} \leqslant   \sqrt{\# {\mathcal U} \# {\mathcal V}}  p^{3/4}
$$
thus the first term never dominates. 
\end{proof}

Clearly the asymptotic formula of Theorem~\ref{thm:Set W} is nontrivial 
under the condition~\eqref{eq:Threshold}.

 
\section{Nonlinearity} 

 \begin{theorem}
\label{thm:Nonlin}
For the  nonlinearity  $N(f)$ of the Boolean function  $f(h) $, 
given by~\eqref{eq:Bool},  we have
$$
N(f) = 2^{n-1} \leqslantft(1  + O\leqslantft( 2^{-n/16} n^{1/8} \right)\right).
$$
\end{theorem}

\begin{proof} We estimate the Fourier coefficients ${\widehat f}(k)$ of $f$
by using the result  that for any integers $M$, $h_1$, $h_2$ with 
$0 \leqslant M \leqslant M+c_1 < M+ c_2 < 2^n$ we have 
$$
\sum_{b=0}^{M-1} (-1)^{f(b+c_1)+ f(b+c_2)}  \ll 
M^{2/3} p^{1/6} (\log p)^{1/3} + p^{1/2} \log p , 
$$
which is a combination of~\cite[Lemma~2.3]{FMRS} 
with a special case $r = 2$  of~\cite[Lemma~4.4]{FMRS}. 
In fact, the above bound can be simplified as 
\begin{equation}
\label{eq:Corr}
\sum_{b=0}^{M-1} (-1)^{f(b+c_1)+ f(b+c_2)}  \ll M^{2/3} p^{1/6} (\log p)^{1/3}  
\end{equation}
(since for $M \leqslant  p^{1/2} \log p $ the bound~\eqref{eq:Corr} 
is trivial and for $M >  p^{1/2} \log p $ we also have 
$ M^{2/3} p^{1/6} (\log p)^{1/3} >  p^{1/2} \log p$). 
  
 We now fix some $m \leqslant n$  and write  $a,r \in {\mathbb B}n$ as 
$$
a = b + 2^m  c  \qquad \text{and} \qquad r = s + 2^m t, 
$$
with $0 \leqslant b,s< 2^m$ and  $0 \leqslant c,t < 2^{n-m}$. In particular
$$
\langle a,r  \rangle = \langle b,s\rangle + \langle c,t \rangle.
$$
Therefore, 
\begin{eqnarray*}
|{\widehat f}(r)|  & =  &|{\widehat f}(s + 2^m t )| = \leqslantft|2^{-n} \sum_{b = 0}^{2^{m} -1} \sum_{c =
0}^{2^{n - m} -1}  (-1)^{ f( b + 2^m  c ) + \langle b,s \rangle + \langle c,t  \rangle} 
\right|\cr
 & \leqslant  &2^{-n}  \sum_{b = 0}^{2^{m} -1} 
\leqslantft| \sum_{c= 0}^{2^{n - m} -1}  (-1)^{  f( b + 2^m  c ) +\langle c,t \rangle }  \right|. 
\end{eqnarray*}
By the Cauchy inequality, we obtain 
\begin{eqnarray*}
|{\widehat f}(r)|^2 
& \leqslant  &2^{m-2n }  \sum_{b = 0}^{2^{m} -1} 
\leqslantft| \sum_{j = 0}^{2^{n - m} -1}   (-1)^{  f( b + 2^m  c ) +\langle c,t \rangle }  \right|^2\cr
& =  &2^{m-2n }  \sum_{b = 0}^{2^{m} -1} 
\sum_{c_1, c_2 = 0}^{2^{n - m} -1}   (-1)^{ f( b + 2^m  c_1 )+    f(b + 2^m  c_2) 
+ \langle c_1, t \rangle + \langle c_2,t \rangle }  \cr
& \leqslant &   
2^{m-2n }\sum_{c_1, c_2 = 0}^{2^{n - m} -1}    \leqslantft| \sum_{b = 0}^{2^{m} -1}  
 (-1)^{ f( b + 2^m  c _1)+    f(b + 2^m  c_2) }\right|.
\end{eqnarray*}
For $2^{n-m}$ choices of $c_1= c_2$ the sums over $b$ is equal to $2^m$.
For the other choices  of $c_1$ and $c_2$ we can use the bound~\eqref{eq:Corr}, 
getting 
\begin{eqnarray*}
|{\widehat f}(r)| ^2& =& O\leqslantft( 2^{m-2n }\leqslantft(2^{n-m} 2^m + 2^{2(n-m)} 2^{2m/3} 2^{n/6} n^{1/3}\right)\right)\cr
& =& O\leqslantft( 2^{m-n}+  2^{n/6 - m/3} n^{1/3}\right).
\end{eqnarray*} 
We now define $m$ by the inequalities 
$2^{m}  \leqslant  2^{7n/8} n^{1/4}  < 2^{m+ 1} $, 
and after simple calculations  conclude the proof. 
  \end{proof}

\section{Comments}

It seems very plausible that~\cite[Corollary~2.4]{Mich2} can be used to derive 
a nontrivial estimate for sums 
$$
T_p(\chi;\alpha,\beta) = \sum_{a \in {\mathcal A}_p(\alpha,\beta)} \chi(a),
$$
with a nonprincipal multiplicative character $\chi$ of ${\mathbb F}_p^*$. 
In this case one can obtain a multiplicative analogue
of our results and study the  set
$$
{\mathcal Z}_p({\mathcal U}, {\mathcal V};\alpha,\beta) = \{(u,v) \in {\mathcal U}\times {\mathcal V}\ : \ uv
\in {\mathcal A}_p(\alpha,\beta)\}. 
$$
Multidimensional analogues of our results which involve joint distributions
of Kloosterman sums can be obtained as well. 

Also, as curiosity, we mention that Theorem~\ref{thm:Set W}
can be combined with the technique of~\cite{BaSh1,BaSh2,BaSh3} to study
sets of  elements of \emph{Beatty} sequence 
$\fl{\vartheta m + \rho}$ (where  $\vartheta > 0$ and $\rho$ are real) which belong to
${\mathcal A}_p(\alpha,\beta)$, that is, sets  of the form 
$$
{\mathcal B}_p(\vartheta, \rho, M;\alpha,\beta) = \{m \in [1, M] \ : \ 
\fl{\vartheta m + \rho} \in
{\mathcal A}_p(\alpha,\beta)\} .
$$

\end{document}