# Character sum of a type of “almost linear” surjective mappings over finite fields

Let $F$ be a finite field of characteristic a prime $p$ with $q$ elements and let $E/F$ be a finite extension of degree $n > 1$ over $F$. Let $\chi$ be the additive canonical character on $F$ defined by $\chi(x) = e^{2\pi \sqrt{-1}T(x)/p}$, where $T : F \to \mathbb{F}_p$ is the ($\mathbb{F}_p$-linear surjective) trace map $T(x) = \sum_{i=0}^{n-1} x^{p^i}$.

The class of polynomials $f : E \to F$ that I'm interested in have the following two properties:

(1) $f$ is surjective;

(2) There exists an integer $m$ such that $f(cx) = c^m f(x)$ for every $c \in F$.

Question: Is it known a good upper bound for $$S = \left| \sum_{x \in E} \chi(f(x))\right|?$$

Remark: Of course we have a general upper bound for these sums, the so called Weil bound $S \leq (\deg(f) - 1)q^{n/2}$. However from some computer experiments I have tried it seems possible this should be a lot lower. In particular when $\gcd(m, q-1) = 1$, it seems that $S = 0$ always. This should have to do with the fact that the mapping $x \mapsto x^m$ permutes $F$ if and only if $\gcd(m, q-1) = 1$. In any case I think there should be some dependency of $S$ on $\gcd(m, q-1)$. Hopefully someone has seen these things before! Thanks!

• if $f(x)=\sum_{i=1}^{Q-1} f_ix^i$, $Q=q^n$, then the condition (2) implies that $i\equiv m\pmod{q-1}$ whenever $f_i\neq0$. The condition $f:E\to F$ implies that $f_i=f_{qi}$, where $qi$ is calculated modulo $Q-1$. Don't know about condition (1). Anyway, we can typically then write $T(f(x))=T^E_F(g(x)$, where $T^E_F:E\to F$ is the relative trace, and $g(x)$ is a polynomial consisting of those terms of $f(x)$, where we select the lowest degree term from each $q$-cyclotomic coset. Typically $\deg g$ is much less than $\deg f$. There may be problems with cyclotomic cosets having $<n$ numbers. – Jyrki Lahtonen Jul 31 '15 at 13:21
• Instead of writing $T(f(x)) = T_F^E(g(x))$, don't you mean that we must write $f(x) = T_F^E(g(x))$ instead? This way $S$ becomes $\sum_{x \in E} \psi(g(x))$ where $\psi$ is canonical additive character of $E$ (by the transitivity of the trace function). Then we could hopefully apply Weil's bound to a better version. This I think is called the trace representation of a function, the coefficients of $g(x)$ being Fourier coefficients of $f(x)$. – user152169 Aug 2 '15 at 20:21
• Still I'm not sure how this could prove a better bound, although, as you say, the degree of $g(x)$ obtained through this method could be often low. – user152169 Aug 2 '15 at 20:27
• Oops. Yes, that's what I was thinking, but writing... Thinking about the rest. What kind of polynomials did you check? – Jyrki Lahtonen Aug 2 '15 at 20:49
• Another possibility is that when $\gcd(m,q-1)$, and $c$ ranges over $F^*$ the elements $f(cx)=c^mf(x)$ do the same unless they are all zero. This gives us a lot of cancellation in the sum, but there may be problems with those zeros (also because the sum over $F^*$ gives a non-cancelled $-1$. – Jyrki Lahtonen Aug 2 '15 at 20:52

I have some doubts now that $$S_m := \sum_{x \in E} \chi(f_m(x)) = 0$$ whenever $(m, q-1) = 1$ in general, but nevertheless here are some calculations that might be of help in certain cases.

For now let $m$ be any integer. Clearly for any $k \in E^*$, $x \mapsto kx$ is a permutation of $E$. Let $e(z) := e^{2\pi \sqrt{-1}z}$. Thus \begin{align} (p-1) S_m &= \sum_{c \in \mathbb{F}_p^*}\sum_{x \in E} \chi(f_m(x)) = \sum_{c \in \mathbb{F}_p^*}\sum_{x \in E} \chi(f_m(cx)) = \sum_{x \in E}\sum_{c \in \mathbb{F}_p^*}\chi(f_m(cx))\\ &= \sum_{x \in E}\sum_{c \in \mathbb{F}_p^*}\chi(c^m f_m(x)) = \sum_{x \in E} \sum_{c \in \mathbb{F}_p^*} \chi(f_m(x))^{c^m} = \sum_{x \in E} \left( -1 + \sum_{c \in \mathbb{F}_p} e\left( \dfrac{T(f_m(x)) c^m)}{p} \right) \right)\\ &= -q^n + p N_m + \sum_{x \in E \setminus K_m} \sum_{c \in \mathbb{F}_p} e\left( \dfrac{T(f_m(x)) c^m)}{p} \right) \end{align} where $$K_m := \{x \in E \mid f_m(x) \in \ker(T)\}$$ and $N_m := \#K_m$.

Some things to notice now.

(1) Note that
$$N_m = \dfrac{1}{p}\#\{ (x, y) \in E \times F \mid f_m(x) = y^p - y \}.$$

(2) In the case that $(m, p-1) = 1$ (which happens if $(m, q-1) = 1$) we have $$G_m := \sum_{c \in \mathbb{F}_p} e\left( \dfrac{T(f_m(x)) c^m)}{p} \right) = 0.$$ Thus $S_m \in \mathbb{Q}$ here.

Moreover, when $(m, p-1) = 1$, we have $S_m = 0$ if and only if $$\#\{ (x, y) \in E \times F \mid f_m(x) = y^p - y \} = \#E := q^n.$$ I believe $G_m$ is known also when $m = 2$ or $m = 3$ (quadratic and cubic Gauss sums) but it seems that a good upper bound is not known in the general case of $m$. See Section 6.1 here:

https://people.math.ethz.ch/~kowalski/exp-sums.pdf

(3) Assume $(m, q-1) = 1$. Further assume that $p \nmid n$. It follows that \begin{align} (q - 1)S_m &= \sum_{c \in F^*} \sum_{x \in E} \chi(f_m((cn)^{1/m} x)) = \sum_{c \in F^*} \sum_{x \in E}\chi(c nf_m(x)) = \sum_{c \in F^*} \sum_{x \in E}\chi( T_F^E (cf_m(x))) \\ &= \sum_{x \in E} \sum_{c \in F^*} \psi(cf_m(x)), \end{align} where $\psi$ is the canonical additive character of $E$. By the orthogonality relations it follows that $$(q-1)S_m = -q^n + q \cdot \#\{x \in E \mid f_m(x) = 0\}.$$ Thus we get $$(q - p)S_m = q \cdot \#\{x \in E \mid f_m(x) = 0\} - p \cdot \#\{x \in E \mid f_m(x) \in \ker(T_{q|p})\}.$$ If $q \neq p$, then $S_m = 0$ if and only if $$\#\{x \in E \mid f_m(x) \in \ker(T_{q|p})\} = \dfrac{q}{p} \cdot \#\{x \in E \mid f_m(x) = 0\}.$$