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

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 $$$$\left\vert \sum _{k=0} ^{q - 2} \omega ^{k^2} \chi (\alpha ^k ) \right\vert.$$$$ 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 $$$$\left\vert \sum _{c\in\mathbb{F}_q^*} \psi _c (c) \chi (c) \right\vert.$$$$ 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 $$$$tr(a) = a+a^p + \cdots + a^{p^{n-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 $$$$\chi_\alpha : \beta \mapsto \exp\left( {\frac{2\pi i \left\langle \alpha ,\beta \right\rangle }{p }} \right)$$$$ 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 $$$$f(x) = \begin{cases} q \psi_x(x) & \text{if } x \neq 0 \\ 0 & \text{if } x = 0 \\ \end{cases}$$$$ then the sum you are considering is equal to the Fourier transform of $$f$$ i.e. $$$$\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)$$$$ see definition 4.6 in Tao.

We apply the Hausdorff-Young inequality theorem 4.8 in Tao to get that $$$$\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}}$$$$ 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

$$$$\sum_{\alpha \in \mathbb{F} _q }\left| \hat f(\alpha)\right|^{2} \leq q\sum_{c \in \mathbb{F} _q^* } |\psi_c (c) |^2$$$$ which is equivalent to saying that $$$$\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.$$$$

Finally, if you can prove that at least $$n$$ many $$\alpha$$ give a value $$| \hat f(a)| \geq \sqrt b$$ then you get that $$$$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)$$$$

which gives you that the maximum value is at most

$$$$\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}$$$$

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