Valuations of Weil Sums of Binomials

We investigate the $p$-adic valuation ${\rm val}_p$ of Weil sums of the form $W_{F,d}(a)=\sum_{x \in F} \psi(x^d -a x)$, where $F$ is a finite field of characteristic $p$, $\psi$ is the canonical additive character of $F$, the exponent $d$ is relatively prime to $|F^\times|$, and $a$ is an element of $F$. Such sums often arise in arithmetical calculations and also have applications in information theory. For each $F$ and $d$ one would like to know $V_{F,d}$, the minimum value of ${\rm val}_p(W_{F,d}(a))$ as $a$ runs through the elements of $F$. We exclude exponents $d$ that are congruent to a power of $p$ modulo $|F^\times|$ (degenerate $d$), which yield trivial Weil sums. We prove that $V_{F,d} \leq (2/3)[F\colon{\mathbb F}_p]$ for any $F$ and any nondegenerate $d$, and prove that this bound is actually reached in infinitely many fields $F$. We also prove some stronger bounds that apply when $[F\colon{\mathbb F}_p]$ is a power of $2$ or when $d$ is not congruent to $1$ modulo $p-1$, and show that each of these bounds is reached for infinitely many $F$.