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}


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.