12
$\begingroup$

Let $f$ be a nonconstant polynomial of degree $d$. Let $\psi$ be a character of the additive group of $\mathbb F_p$. By Weil, we have:

$$ \left| \sum_{x\in \mathbb F_p} \psi ( f(x)) \right| \leq (d-1) \sqrt{p} $$

Trivially, we have:

$$ \left| \sum_{x\in \mathbb F_p} \psi ( f(x)) \right| \leq p $$

So the first bound is better for $d < \sqrt{p}+1$ , and the second bound is better for $d > \sqrt{p}+1$.

I want to know how tight the combination of these two upper bounds is. So let

$$M(p,d)= \sup \left\{ \left| \sum_{x\in \mathbb F_p} \psi ( f(x)) \right|,f \operatorname{ of degree d} \right\}$$

I want to find lower bounds on $M(p,d)$. I can prove a bound that looks like:

$$M(p,d) \geq C \sqrt{d}\sqrt{p} $$

Can one do better?

Here's my argument: Let $n=d/2$, then we estimate the average over $f$ of $\left| \sum_{x\in \mathbb F_p} \psi ( f(x)) \right|^n$. Rearranging, this is the sum over $2n$-tuples $x_1,\dots,x_{2n}$ of the average over $f$ of

$$\psi(f(x_1)+\dots + f(x_n)- f(x_{n+1})-\dots - f(x_{2n}))$$

This term is $1$ if $x_{n+1}$ through $x_{2n}$ is a permutation of $x_1$ through $x_n$ and $0$ otherwise. So the average is just a count of the number of times this happens. This is certainly at least $ \frac{ p! n!}{(p-n)!}$, the number of pairs of $n$-tuples of elements of $\mathbb F_p$ without repetitions, one a permutation of the other. Since the average value is that, the value must be attained for at least one $f$. That $f$ must satisfy $\left| \sum_{x\in \mathbb F_p} \psi ( f(x)) \right| \geq \left(\frac{p!}{(p-n)!}\right)^{1/2n} n!^{1/2n}$ which is a constant times $\sqrt{p}\sqrt{n}$, hence a constant times $\sqrt{p}\sqrt{d}$. (This is not quite correct, because we must remove constant polynomials from the average, but the contribution to the average from constant polynomials is $p^2n/p^{d-1}=p$ and so can be ignored.)

$\endgroup$
1
  • $\begingroup$ If I recall correctly, in Konyagin's famous paper about Guassian sums and Heilbornn conjecture, he shows existence of plenty combinations of $d$ and $(a,p)$, where $p$ is slightly larger than $d$ (less then $d\ln d$ or something, but not by much), and there's a lower bound for the Gaussian sum $| S_{d}(a,p) | \geq p(1-\frac{1}{\ln d})$. $\endgroup$
    – Asaf
    Oct 5, 2014 at 10:54

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.