$\def\FF{\mathbb{F}}$There is a detail that I can't get, but I need to move on to other projects. Subject to that, I can get arbitrarily close to $1/2$, for a
fields of the order $2^{\ell_k}$ where $\ell_k \to \infty$. More
precisely, let $r=2^k$ and let $\phi_0(x) = x^{r+1}$.

**Theorem:**
$$\lim_{m \to \infty} \max_a |\phi_a(\FF_{2^{2km}})|/2^{2k m} =
\frac{r+2}{2r+2}.$$

Taking $k=1$, so $r=2$, we recover Seva's results on $x^3$. In
particular, for each $k$, we can choose $m_k$ large enough that
$\max_a |\phi_a(\mathbb{F}_{2^{2 k m_k}})|/2^{2k m_k} \leq
\frac{r+3}{2r+2}$, and letting $\ell_k = 2 m k$ gives the conclusion.

The actual Theorem we will be proving is slightly more precise and
treats the cases of $a=0$ and $a \neq 0$ separately.

**Theorem:**
For any $a$ and $b$ nonzero elements of $\FF_q$, we have
$|\phi_a(\FF_{q})|=|\phi_b(\mathbb{F}_q)|$, a value we will term
$\phi_{\neq 0}(\FF_q)$. We have
$$\lim_{m \to \infty} \phi_{\neq 0}(\FF_{2^{km}})/2^{km} = \frac{r+2}{2r+2}.$$
Meanwhile,
$$\phi_0(\FF_{2^{km}})/2^{km} = \begin{cases} 1/(r+1) & m\
\mbox{even} \\ 1 & m\ \mbox{odd} \end{cases}$$

The key will be to use Theorem 2 in the paper of Birch and
Swinnerton-Dyer cited by Peter Mueller. Since this result is
stated less precisely than we need, and in a slightly incorrect way,
we rephrase. Let $f \in \FF_q[x]$ be a separable polynomial of degree
$d$, and let $G$ be the Galois group of the splitting field of
$f(x)-y$ over $F(y)$. Let $\FF_{q^s}$ be the algebraic closure of
$\FF_q$ in this splitting field. Then we get a natural surjection
$\pi: G \to \mathrm{Gal}(\FF_{q^s} / \FF_q) \cong \mathbb{Z}/s$.
Define the kernel of this surjection to be $G^+$. Note that
$\mathrm{Gal}(\FF_{q^s} / \FF_q)$ has a canonical generator, the
Frobenius map $\mathrm{Frob}$. Note also that $G$ naturally embeds in
$S_d$. We may thus say that an element of $G$ has no fixed points,
meaning it has no fixed points under this embedding.

**Theorem (Birch and Swinnerton-Dyer)** There are constants
$\lambda_0$, $\lambda_1$, ..., $\lambda_{s-1}$ such that
$$|f(\FF_{q^{ms+i}})| = \lambda_i q^{ms+i} + O(q^{(ms+i)/2}).$$
Explicitly, $\lambda_i$ is the probability that a random element of
$\pi^{-1}(\mathrm{Frob}^i)$ has a fixed point, and the constant in the
big $O$ depends only on $d$, $G$ and $G^+$.

The paper does not give an explicit recipe for $\lambda_i$, and does
not note the need to use $s$ different lambdas, but this is what I got
when I traced through their proof. As a sanity check, let $q \equiv 2
\bmod 3$ and let $f(x)=x^3$. Then $G=S_3$, $G^{+}=A_3$ and $s=2$. We
predict that all of the elements in $\FF_{q^{2m+1}}$ are cubes, but
only $1/3$ of the elements in $\FF_{q^{2m}}$; this is true.

Our actual result will be the following:
**Theorem** Let $\phi(x) = x^{r+1}$ as before and work over the
ground field $\FF_r$. When $f=\phi_a$ for $a \neq 0$, then
$G=G^{+}=PGL_2(\FF_r)$, acting on $r+1$ elements by the natural action
on $\mathbb{P}^1(\FF_r)$. When $a=0$, we have $G=\mathbb{Z}/2
\ltimes \mathbb{Z}/(r+1)$, acting on $r+1$ elements by the dihedral
action, and $G^{+} = \mathbb{Z}/(r+1)$.

We then must compute the proportion of elements in each case which
have fixed points.

So, let's prove that the Galois group is as stated. First, for $a \neq
0$, the change of variables $x'=a^{1/r} x$ turns $\phi_a(x)$ into
$a^{-(r+1)/r} \phi_1(x')$. (Since we are working in finite fields, we
can always take $r$-th roots.) So it is enough to consider $\phi_0$
and $\phi_1$.

**The Galois group of $\phi_0$** We are interested in the splitting
field of adjoining an $(r+1)$-st root of $y$ to $\FF_r(y)$. The
$(r+1)$-st roots of unity live in $\FF_{r^2}$, and
$\mathrm{Gal}(\FF_{r^2}/\FF_r)$ acts on them by inversion. So
$G=\mathbb{Z}/2 \ltimes \mathbb{Z}/(r+1)$ and $G^{+} =
\mathbb{Z}/(r+1)$ as claimed.

**The Galois group of $\phi_1$** We first explain the bijection
between the roots of $x^{r+1}+x=y$ and $\mathbb{P}^1(\FF_r)$.
Consider the roots of the equation $z^{r^2}+z^r=yz$. Clearly, they
form an $\FF_{r}$ vector space under the ordinary operations of
addition and multiplication; call this vector space $V$. It has
dimension $2$. For $z$ any nonzero element of $V$, the element
$x=z^{r-1}$ is a root of $x^{r+1} + x=y$. Moreover, if $z'$ is a
scalar multiple of $z$, then $z^{r-1} = (z')^{r-1}$. So roots of
$x^{r+1} + x=y$ label lines in $V$.

This construction is natural enough to prove that $G \subseteq PGL(V)
\cong PGL_2(\FF_r)$. We now need to show $G^{+} = PGL_2$, and thus that $G=G^{+}$ as well.

Here is the **missing detail**. There is a very similar result of Serre, published as an appendix in a paper of Abhyankar, that the splitting field of $z^{r+1} - wz+1$ is $PSL_2(\FF_r)$. I feel like there should be some simple monomial change of variables that turns $(z,w)$ into $(x,y)$ and let's us deduce our result from Serre's. (Note that $PGL_2=PSL_2=SL_2$ in characteristic $2$.) But I keep not getting it to work.

So, we now need to count the number of fixed points for the dihedral and the $PGL_2$ action.

**The dihedral action** Since $r+1$ is odd, every reflection fixes a point, explaining the $1$ for $m$ odd. Nontrivial rotations do not have fixed points, explaining the $1/(r+1)$.

**The $PGL_2$ action** We use the isomorphism $PGL_2 = PSL_2 = SL_2$.

There are $r+1$ conjugacy classes in $SL_2$, namely

- The identity.
- $\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}$. This class has order $r^2-1$.
- $\begin{pmatrix} t & 0 \\ 0 & t^{-1} \end{pmatrix}$ for $t \neq 1$. There are $r/2-1$ such conjugacy classes, each of order $r^2+r$.
- Matrices that are diagonalizable over $\FF_{r^2}$ with eigenvalues $(t, t^r)$, for $t$ a nontrivial $(r+1)$-st root of unity. There are $r/2$ such conjugacy classes, each of order $r^2-r$.

The first three have fixed points, and the last doesn't. Putting it all together, the probability that an element in $PGL_2(\FF_r)$ has a fixed point is $(r+2)/(2r+2)$.

for any choice of $\varphi_0$, there exists $a$ with $|\varphi_a({\mathbb F})|>q/2$. – Seva Jul 21 '12 at 6:04badchoice, as in this case $\max_a|\varphi_a({\mathbb F})|$ is large. The question is, howsmallcan one make this maximum choosing $\varphi_0$ appropriately. – Seva Jul 22 '12 at 18:28