Upper bound for an exponential sum involving characters of a finite field

Question

Let $q = p^n $ be a prime power, $\alpha\in\mathbb{F}_{q} $ a primitive element of the finite field $\mathbb{F}_q$ and denote by $\chi $ a non-trivial additive character of $\mathbb{F}_{q} $. Set $\omega = \exp\lbrace { i\frac{2\pi} {q - 1} } \rbrace $, I am looking for an upperbound on the following sum \begin{equation} \left\vert \sum _{k=0} ^{q - 2} \omega ^{k^2} \chi (\alpha ^k ) \right\vert. \end{equation} If we denote by $\psi _c $ the multiplicative character of $\mathbb{F}^* _{q} = \mathbb{F}_{q}\setminus\lbrace 0\rbrace =\lbrace \alpha ^0 ,\cdots,\alpha^{q-2}\rbrace$ corresponding to $c\in\mathbb{F}_q ^* $ then the sum can be written as \begin{equation} \left\vert \sum _{c\in\mathbb{F}_q^*} \psi _c (c) \chi (c) \right\vert. \end{equation} The second sum looks much like a Gaussian sum over finite fields, however in this one the multiplicative character changes as well.

ps: The multiplicative character is given by $\psi _{\alpha ^l} (\alpha ^k ) = \omega ^{lk} = \exp\lbrace i\frac{2\pi}{q-1} lk \rbrace $ . The additive character corresponding to an element $a\in\mathbb{F}_{p^n} $ is given by $\chi _a (b) = \exp\lbrace i\frac{2\pi}{p} tr(ab) \rbrace $ for all $b\in\mathbb{F}_{p^n} $, where the trace $tr : \mathbb{F}_{p^n} \rightarrow \mathbb{F}_p $ is defined by \begin{equation} tr(a) = a+a^p + \cdots + a^{p^{n-1}}. \end{equation}

Answer 1

I am going to assume that by an additive character you mean

an irreducible representation $\chi_\alpha : \mathbb{F}^n_q \longrightarrow \mathbb{C}$, i.e. a group homomorphism from the additive group $(\mathbb{F}^n_q ,+)$ to the multiplicative group $(\mathbb{C},*)$

which we can prove must all take the form \begin{equation}\chi_\alpha : \beta \mapsto \exp\left( {\frac{2\pi i \left\langle \alpha ,\beta \right\rangle }{p }} \right)\end{equation} where $ \left\langle \alpha ,\beta \right\rangle = \sum_i \alpha_i \beta_i $, see chapter 4 of Tao for a proof of some of these statements and see ch.2 of Serre or ch.2 of Fulton & Harris for a general (non-abelian) overview of the representation theory perspective on characters. The point is the following

If we let \begin{equation} f(x) = \begin{cases} q \psi_x(x) & \text{if } x \neq 0 \\ 0 & \text{if } x = 0 \\ \end{cases} \end{equation} then the sum you are considering is equal to the Fourier transform of $f$ i.e. \begin{equation} \hat{f}(\alpha) = \frac{1}{q} \sum_{c \in \mathbb{F} _q } f(c) \chi_\alpha(c) = \sum_{c \in \mathbb{F} _q^* } \psi_c (c) \chi_\alpha(c) \end{equation} see definition 4.6 in Tao.

We apply the Hausdorff-Young inequality theorem 4.8 in Tao to get that \begin{equation} \left(\sum_{\alpha \in \mathbb{F} _q }\left| \hat f(\alpha)\right|^{p'} \right)^{\frac{1}{p'}} \leq \left(\sum_{\alpha \in \mathbb{F} _q } |f(\alpha)|^p\right)^{\frac{1}{p}} = q\left( \sum_{c \in \mathbb{F} _q^* } |\psi_c (c) |^p\right)^{\frac{1}{p}} \end{equation} where the LHS is the $l^{q}$-norm, the RHS is the $l^p$-norm, and $p$ satisfies the following $p^{-1} +q^{-1} = 1 \land 1 \leq p\leq 2$. Plugging in $p = 2$ we get that

\begin{equation} \sum_{\alpha \in \mathbb{F} _q }\left| \hat f(\alpha)\right|^{2} \leq q\sum_{c \in \mathbb{F} _q^* } |\psi_c (c) |^2 \end{equation} which is equivalent to saying that \begin{equation} \mathbb{Var}[\hat f] = \frac{1}{q}\sum_{\alpha \in \mathbb{F} _q }\left| \hat f(\alpha)\right|^{2} \leq \sum_{c \in \mathbb{F} _q^* } |\psi_c (c) |^2\leq q-1. \end{equation}

Finally, if you can prove that at least $n$ many $\alpha$ give a value $ | \hat f(a)| \geq \sqrt b$ then you get that \begin{equation} nb +\sup_{\alpha \in \mathbb{F} _q }\left| \hat f(a)\right|^2 \leq \sum_{\alpha \in S}\left| \hat f(\alpha)\right|^{2} + \sup_{\alpha \in \mathbb{F} _q }\left| \hat f(a)\right|^2 \leq \sum_{\alpha \in \mathbb{F} _q }\left| \hat f(\alpha)\right|^{2} \leq q(q-1) \end{equation}

which gives you that the maximum value is at most

\begin{equation} \sup_{\alpha \in \mathbb{F} _q }\left|\sum_{c \in \mathbb{F} _q^* } \psi_c (c) \chi_\alpha(c) \right| = \sup_{\alpha \in \mathbb{F} _q }\left| \hat f(a)\right| \leq \sqrt{q(q-1)-nb} \end{equation}

Essentially we reduced the problem of finding an upper bound to that of finding a lower bound.